静态调度：Cyclic scheduler Start Time 0 调度表(table-driven):只存储major cycle Task in milli Seconds T 0 一“重复”预定的调度 T2 3 ·所有任务周期的最小公倍数LCM Ts 10 Ta 12 ·最好包含各frame的slack times 17 -major cycle被划分成frame(=minor cycle),需考虑： ·上下文切换最小：任务尽量在一个frae中完成 ·最小化调度表：主周期应包含整数个rame Task Number Frame Number ·满足deadline:dl至少应为一个完整的frame T3 F1 ·Periodic timer:用于确定rame的开始 Ti F2 调度点：frame的边界（选择任务，检查超时） T3 F3 - Periodic task:frame开始处开始执行 T4 F2 sporadic/.aperiodic:利用frame的slack time Major Cycle Major Cyele Minor cycle fl f2 f3 f4 f4n f4n+1 f4n+2 f4n+3 Figure 6:Major and Minor Cycles in a Cyclic Scheduler
静态调度：Cyclic scheduler • 调度表（table-driven）：只存储major cycle – “重复”预定的调度 • 所有任务周期的最小公倍数LCM • 最好包含各frame的slack times – major cycle被划分成frame (=minor cycle)，需考虑： • 上下文切换最小：任务尽量在一个frame中完成 • 最小化调度表：主周期应包含整数个frame • 满足deadline： dl至少应为一个完整的frame • Periodic timer：用于确定frame的开始 • 调度点：frame的边界（选择任务，检查超时） – Periodic task: frame开始处开始执行 – sporadic/aperiodic: 利用frame的slack time UnRegistered
Task Number Frame Number A Cyclic Scheduler T3 F1 TI F2 cyclic-scheduler(){ T3 F3 current-task T Schedule-Table[k]; T4 F2 k=k+1; k =k mod N; /N is the total.number of tasks //in the schedule table dispatch-current-Task(T); schedule-sporadic-tasks(); //Current task T completed early, //sporadic tasks can be taken up. schedule-aperiodic-tasks();//At the end of the frame,the running //task is preempted,if not complete. idle(), /No task to run,idle. pi rejection M M Sporadic Acceptance Jobs Test Ti(l)Ti(2) Ti(k-1) Ti(k)Ti(k+1) Ti(2k-1) Periodic Φ Jobs Processor time- Aperiodic Figure 4:Major Cycle When A Task Ti Has Non-Zero Phasing Jobs llxx@ustc.edu.cn 22/41
llxx@ustc.edu.cn 22/41 A Cyclic Scheduler UnRegistered
Priority-Driven Scheduling 》 J10/3 Release time 0 J20/1 J30/2 J40/2 Execution time Q →0 J54/2 J60/4 activation 0 dispatching termination Execution J20/4 J30/1 scheduling O preemption Jobs are scheduled on two processors P1 and P2 。 Jobs communicate via shared memory,so communication cost is negligible All jobs are preemptabie scheduling decisions are made whenever some job becomes ready for execution or a job completes ·优先级分配策略：小，优先级高 The schedulers keep one common priority queue of ready jobs ·贪心：尽量不让处理器空闲。局部最优
Priority-Driven Scheduling • Jobs are scheduled on two processors P1 and P2 • Jobs communicate via shared memory, so communication cost is negligible • All jobs are preemptable – scheduling decisions are made whenever some job becomes ready for execution or a job completes • 优先级分配策略：i小，优先级高 – The schedulers keep one common priority queue of ready jobs • 贪心：尽量不让处理器空闲。局部最优。 UnRegistered
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 8 9 8 10 8 Execution time 04 12
Priority-Driven Scheduling List UnRegistered
Scheduling Objective ·User-oriented Criteria·System-oriented -Response time Criteria Turnaround time Throughput -Deadline CPU utilization Fairness Algorithm Decision Mode Priority Function Arbitration Rule FCFS non-preemptive P(r)=T Random S.JF non-preemptive P(t)=-t FIFO/Random preemptive SRT P(a,t)=a-t FIFO/Random (at job arrival) RR preemptive P()=k Cyclic (at quantum) MLF preemptive P(a),n-levels FIFO/Cyclic at quantum）
Scheduling Objective • User-oriented Criteria – Response time – Turnaround time – Deadline • System-oriented Criteria – Throughput – CPU utilization – Fairness UnRegistered