® 实时调度理论 李曦 llxx@ustc.edu.cn 计算机系计算机应用研究室
实时调度理论 李曦 llxx@ustc.edu.cn 计算机系计算机应用研究室
Architecture model of CPS Round Robin Fixed Priority EDF Output Events ECU ECU ECU wwo Communication Bus
Architecture model of CPS
Task model:one function one task Implementation Abstract model task body Pl is Interval constant Duration :=5.0; Next_Time Time; begin Next Time :Clock Interval; loop tiont delay until Next Time; T =C,T,D,O Next Time :Next Time Interval; end loop; end Pi; task body P2 is Interval constant Duration :7.0; Next Time Time; begin Next Time :Clock Interval; T2 t2={C2,T,D2,02} 100p Action; delay until Next Time; Next Time :Next Time Interval; end loop; end P2;
Task model：one function = one task
任务特征：按调度复杂性 01 级—一到达时间的可预测性 一纯周期，无异步事件，且计算要求不变 一小导弹，无人驾驶靶机 。 2级 大部分是周期的，少量异步事件和“突发”计算负载（错误恢复，外 部命令) 一航电，空间系统 ·3级 一异步的（或事件驱动），周期处理少 -通讯，雷达 ·两种调度方法：周期执行法(1级)，多任务处理法(3级) 任务 任务执行 复杂共享数据 可预测性 周期法 同步、顺序 非抢占 难（执行顺序决定） 好 多任务 异步、并发 可抢占 易（同步原语） 难
任务特征：按调度复杂性 • 1级——到达时间的可预测性 – 纯周期，无异步事件，且计算要求不变 – 小导弹，无人驾驶靶机 • 2级 – 大部分是周期的，少量异步事件和“突发”计算负载（错误恢复，外 部命令） – 航电，空间系统 • 3级 – 异步的（或事件驱动），周期处理少 – 通讯，雷达 • 两种调度方法：周期执行法（1级），多任务处理法（3级） 任务 任务执行 复杂共享数据 可预测性 周期法 同步、顺序 非抢占 难（执行顺序决定） 好 多任务 异步、并发 可抢占 易（同步原语） 难
内容提要 ·实时任务类型与约束模型 -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
内容提要 • 实时任务类型与约束模型 – 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
状态（队列）、定时、ETTT BLOCKED 0 等待队列 signal wait dispatching ·就绪队列（运行队列) activation termination READY RUNNING active arrive release? preemption ACTIVE -active：任务被激活（创建） ·“make ready a new task,either immediately or at some future point in time"(Kopetz P220) -Arrive:TT的任务到达，或ET的事件到达 。=release=start Arrival Release Completion (invocation)） 邮州州 Time Release Time Jitter Execution
状态（队列）、定时、ET/TT？ • 等待队列 • 就绪队列（运行队列） • active = arrive = release？ – active ：任务被激活（创建） • “make ready a new task，either immediately or at some future point in time”（Kopetz P220） – Arrive：TT的任务到达，或ET的事件到达 • = release=start
任务：Tasks,jobs,三类 A task T=1,J2,...,Jn is a set of related jobs that together perform some operation A Job is a unit of work scheduled and executed by the system (the unit of concurrency) If jobs occur on a regular cycle,the task is periodic A sporadic task is an aperiodic task where the jobs have deadlines once released ·存在“最小到达间隔”！ If jobs have unpredictable release times,a task is termed aperiodic Appear once only?Have average deadlines (soft-RT)? 一非周期两种类型：到达模式，软硬实时性(DL) Deadline 州料糊 Computation time Period
任务：Tasks，jobs，三类 • A task T= {J1,J2,…,Jn} is a set of related jobs that together perform some operation • A Job is a unit of work scheduled and executed by the system（the unit of concurrency） – If jobs occur on a regular cycle, the task is periodic – A sporadic task is an aperiodic task where the jobs have deadlines once released • 存在“最小到达间隔”！ – If jobs have unpredictable release times, a task is termed aperiodic • Appear once only? Have average deadlines（soft-RT）？ – 非周期两种类型：到达模式，软硬实时性（DL）
Constraints on Tasks (RTOS view Arrival Release Completion 0 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):基于msg 。 Resource constraints Data dependence? Mutual exclusion constraints Resource access protocols
Constraints on Tasks（RTOS view） • Timing(定时) constraints – Release time • Relative to arriving time – Deadline • Absolute deadline • Precedence( Precedence(优先) constraints ) constraints，偏序 – Temporal order：Temporal dependence • temporal distance： “完成时间”之差 – Causal order：Causal dependence • Happen-before(Lamport)：基于msg • Resource constraints – Data dependence？ – Mutual exclusion constraints • Resource access protocols
任务的定时模型timing model a: 到达时刻arrival/request C 下切换时间 s.调度开始时刻start e:调度结束时刻/release ai S e f d C:capacity/执行时间/Workload 天 完成时刻 当T=0且Jitter=0时：Arrival=Start=Release R响应时间 截止期deadline relative deadline D:slack;=d-f 绝对d(时刻) 相对D(时长) ti 松弛时间slack, 裕度laxity a d 延迟Lateness:d-f absolute deadline response time Ri (di=a;+R) 开始时限 Delay? 抖动jitter 10/41
任务的定时模型timing model a：到达时刻arrival/request T: 切换时间 s: 调度开始时刻start e: 调度结束时刻/release C: capacity/执行时间/Workload f： 完成时刻 R：响应时间 当T=0 且 Jitter=0 时：Arrival = Start = Release 10/41 R：响应时间 截止期deadline 绝对d（时刻） 相对D（时长） 松弛时间slack，裕度laxity 延迟Lateness：d – f 开始时限 Delay？ 抖动jitter
周期任务的定时模型 Static task parameters: C,(undisturbed)WCET :period ={Ci.T.D.O) D,:(relative)deadline O:(absolute)time offset t O(phase):the interval between a periodic thread creation and its first release time. T 可用于指定任务的执行顺序。 注意：未考虑调度切换开销！ 截止时间D可以等于或不等于周期T! 11/41
周期任务的定时模型 注意：未考虑调度切换开销！ 11/41 O(phase): the interval between a periodic thread creation and its first release time。 可用于指定任务的执行顺序。 截止时间D可以等于或不等于周期T！