® 实时调度 李曦 llxx@ustc.edu.cn 计算机系计算机应用研究室
实时调度 李曦 llxx@ustc.edu.cn 计算机系计算机应用研究室
内容提要 ·实时任务约束模型 -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 ·多处理器调度：优先级贪心调度，Pfair调度 ·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 • 多处理器调度：优先级贪心调度，Pfair调度 • Timing Analysis(WCET分析)
参考文献 USTC 各a 《嵌入式系统设计·嵌入式CPS系统基础》， 嵌入式系统设计一横入式 信息物理系基础 第2版，2011 -Peter Marwedel(TU Dortmund教授)。译错多⑧ Giorgio C Buttazzo,RETIS Lab,TeCIP Insitute, Pisa,Italy Hard Real-Time Computing Systems:Predictable GergChinsoo Hard Real-Time Scheduling Algorithms and Applications,第三版， Computing Systems 2011 Multiprocessor Scheduling for Real-Time Systems,2015 REAL-TIE SYSTBI6 Multiprocessor Scheduling for Real-Time Systems 0.5. 种e 3/100
参考文献 • 《嵌入式系统设计·嵌入式CPS系统基础》， 第2版，2011 – Peter Marwedel（TU Dortmund教授）。译错多 • Giorgio C Buttazzo，RETIS Lab, TeCIP Insitute， Pisa, Italy – Hard Real-Time Computing Systems: Predictable 3/100 – Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications，第三版， 2011 – Multiprocessor Scheduling for Real-Time Systems，2015
Multiprocessor/distributed Multiprocessors systems is a set of autonomous processors which have software to coordinate them self and share resources Share the same clock - Share the same main memory o Distributed systems is a set of autonomous processors that are connected by a network and which have software to coordinate themself or share resources -No shared memory.Message passing communication. -A clock for each processor
Multiprocessor/distributed • Multiprocessors systems – is a set of autonomous processors which have software to coordinate them self and share resources – Share the same clock – Share the same main memory • Distributed systems – is a set of autonomous processors that are connected by a network and which have software to coordinate themself or share resources – No shared memory. Message passing communication. – A clock for each processor
Multiprocessors/MultiCore Arch. 》 homogeneous processors processors have the same computing capability and run task at the same rate heterogeneous processors PE PE PE PE ● Cluster Heterogeneous MPSoCs Shared -ARM的big.LITTLE架构 Shared Shared Cortex-A15 MPCore+Cortex-A7 气月9。tur年可 ReGourco ·理论上可以使电池的使用寿命延长高达70%
Multiprocessors/MultiCore Arch. • homogeneous processors – processors have the same computing capability and run task at the same rate • heterogeneous processors • Cluster Heterogeneous MPSoCs – ARM的big.LITTLE架构 • Cortex-A15 MPCore+Cortex-A7 • 理论上可以使电池的使用寿命延长高达70%
multiprocessor scheduling ·Vhere and When Global scheduling on-ine:为任务分配/抢占一个空闲的处理器。可迁移 the level of migration:Task/Job level migration Global scheduling 一可迁移造成分析困难 -适于多处理器系统：优先级贪心调度，Pair调度 expect optimal processor usage busy processors,less preemptions .. Partitioning scheduling -off-line:每个处理器一个任务队列。非迁移 - “bin-packing”problem:NP-hard -适于分布式系统(ARINC653) expect minimize the number of processors,the number of communications,latencies,.. Partitioning hierarchical scheduling ·heuristic
multiprocessor scheduling • Where and When • Global scheduling – on-line：为任务分配/抢占一个空闲的处理器。可迁移 • the level of migration：Task/Job level migration – 可迁移造成分析困难 – 适于多处理器系统：优先级贪心调度，Pfair调度 – expect optimal processor usage • busy processors, less preemptions ... • Partitioning scheduling – off-line：每个处理器一个任务队列。非迁移 – “bin-packing” problem：NP-hard – 适于分布式系统（ARINC 653） – expect minimize the number of processors, the number of communications, latencies, ... • hierarchical scheduling • heuristic
多处理器优先约束：优先级调度法 J10/3 Release time 0 J20/1 J30/2 J40/2 Execution time 0 0 J4/2 J60/4 activation dispatching termination Execution J70/4 J30/1 scheduling preemption ·P1、P2两个处理器 一任务基于共享内存通信（因此，通信开销可忽略） · Priority-Driven Scheduling:任务号i小，则优先级高 The schedulers keep one common priority queue of ready jobs 一贪心：尽量不让处理器空闲。局部最优。 ·所有任务可抢占：ET? -调度时刻：任务就绪(ready)或完成 ·注意：因为存在优先约束，ready#release
多处理器优先约束：优先级调度法 • P1、P2两个处理器 – 任务基于共享内存通信（因此，通信开销可忽略） • Priority-Driven Scheduling：任务号i小，则优先级高 – The schedulers keep one common priority queue of ready jobs – 贪心：尽量不让处理器空闲。局部最优。 • 所有任务可抢占：ET？ – 调度时刻：任务就绪（ready）或完成 • 注意：因为存在优先约束，ready≠release
Priority-Driven Scheduling List Time Not yet Released but not Ready to run P1 P Completed released yet ready to run 0 1 2 3 4 5 6 1 8 9 8 10 8 8 11 Execution time 2 ,04
Priority-Driven Scheduling List
Theorem (Richard Graham,1976) ● Brittleness In general,all thread scheduling algorithms are brittle:Small changes can have big,unexpected consequences. ·Richard's Anomalies If a task set with fixed priorities,execution times, and precedence constraints is scheduled according to priorities on a fixed number of processors,then increasing the number of processors,reducing execution times,or weakening precedence constraints can increase the schedule length
Theorem (Richard Graham, 1976) • Brittleness – In general, all thread scheduling algorithms are brittle: Small changes can have big, unexpected consequences. • Richard’s Anomalies – If a task set with fixed priorities, execution times, and precedence constraints is scheduled according to priorities on a fixed number of processors, then increasing the number of processors, reducing execution times, or weakening precedence constraints can increase the schedule length
A Priority-based 3 processor schedule C1=3① ⑨Cg=9 9 tasks with precedences and the shown execution times,where lower numbered tasks have higher C2=2② 8C8=4 priority than higher numbered tasks.Priority-based 3 processor schedule: C3=2③ ,⑦C,=4 1 proc1 9 C4=24 6)C6=4 proc2 4 5 7 proc3 3 6 8 5⑤C=4 time 6 8 10121416 Priority-.based scheduling is“greedy” .What happens if you increase the number of processors to four?
A Priority-based 3 processor schedule 1 2 3 4 9 8 9 tasks with precedences and the shown execution times, where lower numbered tasks have higher priority than higher numbered tasks. Priority-based 3 processor schedule: 7 6 C1 = 3 C2 = 2 C3 = 2 C4 = 2 C9 = 9 C8 = 4 C7 = 4 C6 = 4 •Priority-based scheduling is “greedy” •What happens if you increase the number of processors to four? 5 C5 = 4