1、非抢占调度算法 假设：任务的执行一定会终止 ● 非抢占式轮转(Round-Robin)调度算法 一个任务执行完再执行下一个 ·适用于实时性要求不太严格的场合！ 也可以按时间片（称tick scheduling)或CPU使用率轮转 进程7 进程8 非抢占式优先级调度算法 进程6 进程 适用于要求较为严格的场合！ 处理器 算法较简单 进程5 进程2 进程4 进程3 llxx@ustc.edu.cn
llxx@ustc.edu.cn 26/41 1、非抢占调度算法 • 假设：任务的执行一定会终止 • 非抢占式轮转（Round-Robin）调度算法 – 一个任务执行完再执行下一个 • 适用于实时性要求不太严格的场合！ – 也可以按时间片（称tick scheduling）或CPU使用率轮转 • 非抢占式优先级调度算法 – 适用于要求较为严格的场合！ • 算法较简单 UnRegistered
非抢占式调度图 实时进程要求调度 调度实时进程运行 轮转调度 进程1 进程2 进程n 实时进程 Round-Robin/ tick scheduling 调度时间 实时进程请求调度 当前进程运行完成 优先级调度 当前进程 实时进程 调度时间 llxx@ustc.edu.cn 27/41
llxx@ustc.edu.cn 27/41 非抢占式调度图 轮转调度 Round-Robin/ tick scheduling 优先级调度 UnRegistered
2、抢占式调度算法 e》 1.基于时钟的抢占式优先权调度算法 某高优先级任务到达后并不立即抢占，而等下一个 时钟中断时抢占。 也称：“抢占式时间片调度、Round-Robin(或称 “比例共享式”，FCFS+time quantum) 2.立即抢占的优先权调度算法 一旦出现外部中断，只要当前任务未处于临界区 (critical sections),就立即抢占处理机。 llxx@ustc.edu.cn 28/41
llxx@ustc.edu.cn 28/41 2、抢占式调度算法 1. 基于时钟的抢占式优先权调度算法 某高优先级任务到达后并不立即抢占，而等下一个 时钟中断时抢占。 也称： “抢占式时间片调度” 、 Round-Robin（或称 “比例共享式” ，FCFS+ time quantum） 2. 立即抢占的优先权调度算法 一旦出现外部中断，只要当前任务未处于临界区 (critical sections) UnRegistered ，就立即抢占处理机
抢占式调度图 实时进程请求调度时钟中断到来时 时钟中断抢占 当前进程 实时进程 异步式 “抢占式时间片调度” “Round-Robin.系统” 调度时间 当前Tick结束 实时进程请求调度 实时进程抢占当前 进程，并立即执行 立即抢占 当前进程 实时进程 同步式 调度时间 critical sections结束 llxx@ustc.edu.cn 29/41
llxx@ustc.edu.cn 29/41 抢占式调度图 时钟中断抢占 异步式 “抢占式时间片调度” “Round-Robin系统” 立即抢占 同步式 critical sections结束 当前Tick结束 UnRegistered
Preemptive or Non-Preemptive re》 Non-Preemptive,co-operative State-space needed is smaller:Lower imp:(mem)cost Less overhead at run-time Preemptive:Context switching is significant -Cache pollution,memory size -Certification authorities tend to support this form of scheduling The scheduler is simpler. ·Testing is easier. ·任务执行时间可预测 一Liu:“当任务不可抢占时，没有最优的online调度算法。” 。 Preemptive =1 B 一高优先级任务响应快 D D 一D -Makespan.小 1134 5614↓通1丝日45塔日出的t ·Hybrid scheduling -B可抢占，其它co-operative A-B-A c-B -C D Time
30 Preemptive or Non-Preemptive • Non-Preemptive，co-operative – State-space needed is smaller：Lower impl（mem） cost – Less overhead at run-time • Preemptive: Context switching is significant – Cache pollution, memory size – Certification authorities tend to support this form of scheduling. • The scheduler is simpler. • Testing is easier. • 任务执行时间可预测 – Liu： “当任务不可抢占时，没有最优的online调度算法。” • Preemptive – 高优先级任务响应快 – Makespan小 • Hybrid scheduling – B可抢占，其它co-operative UnRegistered