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