® 实时调度理论 李曦 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