® 嵌入式软件设计 实时任务调度 李曦 ixx@ustc.edu.cn 计算机系计算机应用研究室
嵌入式软件设计 实时任务调度 李曦 llxx@ustc.edu.cn 计算机系计算机应用研究室 UnRegistered
内容提要 ·实时任务约束模型 Assumptions about task timing,interaction 。 任务调度算法Scheduling Algorithm Scheduling mode and selection function ·Timeliness:deadline,worst response time,。。。 efficiency:average response time,makespan -Prioritized goals Temporal predictability first,performance second ● 可调度分析Schedulability Test Prediction of worst-case behavior 一 基于CPU利用率(workload analysis) for preemptive and strictly periodic tasks? WCRT(Response time analysis) ·for preemptively feasible task sets with D≤T ·Timing Analysis(WCET分析)
内容提要 • 实时任务约束模型 – Assumptions about task timing, interaction • 任务调度算法Scheduling Algorithm – Scheduling mode and selection function • Timeliness: deadline，worst response time，。。。 • efficiency: average response time，makespan – Prioritized goals • Temporal predictability first，performance second • 可调度分析Schedulability Test – Prediction of worst-case behavior – 基于CPU利用率(workload analysis) • for preemptive and strictly periodic tasks？ – WCRT(Response time analysis) • for preemptively feasible task sets with D ≤ T • Timing Analysis(WCET分析) UnRegistered
参考文献 ,《嵌入式系统设计嵌入式CPS系统基础》，2版，2011 -Peter Marwedel(TU Dortmund教授)。译错较多⑧ 《Real-Time Systems》,Jane W.S.Liu,2000 1973年，C.L.Liu(刘炯朗)和Layland提出RM,并证明RM和EDF 的最优性 1994年，J.W.S.Lu(張韻詩)定义优先级驱动系统的可预测性 ·即：任务执行时间可预测 REAL-TIME 嵌入式系统设计 5y5T15 信息物理系统， 0,S. ⊙山惠出感相 3/100
3/100 参考文献 • 《嵌入式系统设计·嵌入式CPS系统基础》，2版，2011 – Peter Marwedel（TU Dortmund教授）。译错较多L • 《Real-Time Systems》，Jane W. S. Liu，2000 – 1973年，C. L. Liu（刘炯朗）和Layland提出RM，并证明RM和EDF 的最优性 – 1994年，J. W. S. Liu（張韻詩）定义优先级驱动系统的可预测性 • 即：任务执行时间可预测 UnRegistered
2.How are they programmed? /Perform the convolut..to. for (int i=0;i<10;i+)i x[i]=a[i]*b【j-i /Notify listerezs. notify(x[i]): 1.What are Real- 3.How to verify Time Systems? the real-time constraints?
UnRegistered
The multi-step design 》 Functional Model Software Tasks Model ◇ Task gen. Synchronous approach:控制工程师采用 Asynchronous approach:计算机L程师采用 Task mapping Architecture Model CPU1 CPU2 意童而 CPUk 40
The multi-step design Synchronous approach：控制工程师采用 Asynchronous approach：计算机工程师采用 UnRegistered
RTOS view of Reaction event response to event -response interval process made interrupt available processing real-time dispatch latency process execution conflicts dispatch Arrival Release Completion (invocation) ∩Deadline d Time Jitter Execution Computation time Period Response Time
RTOS view of Reaction UnRegistered
Constraints on Tasks (OS view Arrival Release Completion ·Timing(定时)constraints (invocation)】 -Release time Relative to arriving time Time -Deadline Jitter Execution ·Absolute deadline Response Time o Precedence(优先)constraints,偏序 Temporal order:Temporal dependence ·temporal distance:“完成时间"之差 - Causal order:Causal dependence Happen-before(Lamport) Resource constraints Data dependence ·Mutual exclusion Resource access protocols
Constraints on Tasks（OS view） • Timing(定时) constraints – Release time • Relative to arriving time – Deadline • Absolute deadline • Precedence(优先) constraints，偏序 – Temporal order：Temporal dependence • temporal distance： “完成时间”之差 – Causal order：Causal dependence • Happen-before(Lamport) • Resource constraints – Data dependence • Mutual exclusion • Resource access protocols UnRegistered
非周期任务的定时模型(tos) Arrival Release Completion (invocation) Time Si e f d Release Time Jitter Execution 当T=O和Uter=0时：Arrival=Release=Start Response Time a:到达时刻arrival/request relative deadline D, s:开始调度时刻stat e; 调度结束时刻/release 天完成时刻 a d 下：切换时间 absolute deadline C.执行时间Workload response time Ri (di=ai+Ri) R:响应时间 截止期：绝对d(动态，时刻)，相对D(静态，时间)，开始时限 延迟Lateness:f-d 8/41
8/41 非周期任务的定时模型(rtos) a：到达时刻arrival/request s: 开始调度时刻start e: 调度结束时刻/release f： 完成时刻 T: 切换时间 C: 执行时间/Workload R：响应时间 截止期：绝对d（动态，时刻），相对D（静态，时间），开始时限 延迟Lateness：f – d 当T=0 和 Jitter=0 时：Arrival = Release = Start UnRegistered
松弛时间slack(裕度laxity)、WCE D Si R siacki=di-f 延迟Lateness:=f'-d AET (Actual Execution Time) siack 2 {1) Task Task ■■■■■■■■■■■■ 0 Deadline=Period BCET (Best Case Execution Time)WCET (Worst Case Execution Time)
松弛时间slack（裕度laxity）、WCET 延迟Lateness=f ‘– d f' L UnRegistered
Arrival Release Completion (invocation) Types of Jitter Time Finishing-time Jitter Release Time Jitter Execution ti f Start-time Jitter T Sil Si.2 Si.3 Completion-time Jitter (I/O Jitter) Si1 fil S1,2 fi2 Si.3
Types of Jitter UnRegistered