CPU调度(Scheduling) 主讲教师：夏莹杰 xiayingjie@zju.edu.cn

相关基本概念 引入多程序设计，目的是提高计算机资源利用率，尤其是CPU利用率(CPU utilization) CPU密集 – I/O密集的循环 进程的执行，呈现出CPU运行和I/O等待的交替循环 CPU密集型，I/O密集型

CPU运行和I/O等待的交替循环

CPU调度器的使命 CPU调度器(Scheduler) 从内存中一堆准备就绪的进程中（就绪队列中的就绪进程），选取一个进程； 后者也可以由dispatcher完成，见后面讨论

CPU调度器的操作对象 Scheduler

CPU调度器的操作时机 调用CPU调度器的时机，通常发生在： 1. 某一进程从执行状态转为等待状态 2. 某一进程从执行状态转为就绪状态 1. 某一进程从执行状态转为等待状态 2. 某一进程从执行状态转为就绪状态 3. 某一进程从等待状态转为就绪状态 4. 某一进程终止 注意，调度时机不限于此4种情况。例如？ 第1种情形和第4种情形称作“非抢占式” (nonpreemptive)调度。见后续讨论。 第2种情形和第3种情形称作“抢占式” (preemptive)调度。见后续讨论。

CPU分配器(Dispatcher) CPU调度器决定了将CPU分配给谁。后续操作就是，CPU分配器将CPU控制权移交给该进程。操作内容通常包括： 上下文切换(switching context) 从内核态(kernel mode)转移至用户态(user mode) 跳转至用户程序中PC寄存器所指示的位置 分配延迟(Dispatch latency) – CPU分配器暂停前一进程，启动后一进程所经历的时间

CPU调度器追求指标 CPU利用率(CPU utilization) 吞吐率(Throughput) – 单位时间内完成执行的进程数 周转时间(Turnaround time) – 执行某一进程所耗用的CPU累积时间 等待时间(Waiting time) – 某一进程等待在就绪队列里面的累积时间 响应时间(Response time) – 某一进程从发出调度请求，到其得到CPU调度器响应，其间所经历的时间

优异的指标，当然是 Maximize CPU utilization Maximize throughput Minimize turnaround time Minimize waiting time Minimize response time

First-Come, First-Served (FCFS) Scheduling Process Burst Time P1 24 P2 3 P3 3 假设进程到达就绪队列的顺序：P1 , P2 , P3 FCFS调度算法的调度结果如甘特图(Gantt Chart)： 等待时间(Waiting time) P1 = 0; P2 = 24; P3 = 27 平均等待时间：(0 + 24 + 27)/3 = 17 P1 P2 P3 24 27 30

FCFS调度算法 (续) 假设进程到达就绪队列的顺序： P2 , P3 , P1 FCFS调度算法的调度结果有显著变化，如甘特图： 平均等待时间：(6 + 0 + 3)/3 = 3，改善非常多 ！ 启示：短进程先于长进程，会得到意外效果 P1 P3 P2 6 3 30

Shortest-Job-First (SJF) 调度算法 算法要求： 进入就绪队列的进程预告需要多长CPU时间才能完成本次执行 算法思想： 选取就绪队列中，“需要CPU时间”最短的进程

举例：非抢占式(Non-Preemptive) SJF Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (非抢占式) 平均等待时间 = (0 + 6 + 3 + 7)/4 = 4 P1 P3 P2 7 3 16 P4 8 12

举例：抢占式(Preemptive) SJF Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 SJF (抢占式) 平均等待时间 = (9 + 1 + 0 +2)/4 = 3 P1 P3 P2 4 2 11 P4 5 7 16

两种SJF策略比较 非抢占式(Non-Preemptive) – 一旦CPU分配给了某个进程，就不能“抢过来”，除非该进程主动放弃CPU（CPU burst cycle结束，或者进程转去做I/O操作） 抢占式(Preemptive) – 上述描述的“非” 当一个进程进入就绪队列，如果它的CPU时间小于当前拥有CPU的进程的剩余“预估”时间，前者抢占后者的CPU。此算法称作Shortest-Remaining-Time-First (SRTF)

关于SJF算法的结论 SJF是最优算法 – why SJF算法有致命缺陷 – To Be Cont

进入就绪队列的进程怎么“预估”CPU时间？ 不可能准确地预测，为什么？(e.g. 等待输入数据) 只能根据过去的CPU burst cycles拟合 例如，指数平均Exponential average思想

图，“指数平均”求进程的下一个CPU Burst Cycle

假如设计一个新算法: HRN (Highest response Ratio Next) HRN = (W + T) / T W代表等待时间，T代表预估CPU时间，用HRN评估调度的优先级。 Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4

优先权法(Priority Scheduling) 每个进程都有一个优先数(priority number)，通常是个整型数 选取就绪队列中，优先权最高的进程 （假设：最小优先数  最高优先权） Preemptive，高优先权的进程到达时引起调度 Nonpreemptive，高优先权的进程到达时不触发一次调度 当优先权定义为进程“需要的CPU时间”时，SJF算法就是优先权法

Process Burst Time Priority 举例：优先权法(非抢占式) Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 甘特图 平均等待时间 = (6 + 0 + 16 + 18 + 1)/5 = 8.2 P2 P1 P5 6 1 P4 16 18 P3 19

优先权算法的一个缺陷 Issue  进程饥饿(Starvation) – 优先权较低的就绪进程可能永远得不到CPU Solution  Aging思想 – 就绪进程等在就绪队列里的时间，折算叠加到进程优先权。因此，等待在就绪队列里的进程，其优先权单调递增

轮转法(Round Robin，RR) 每个就绪进程获得一小段CPU时间(时间片，time quantum)，通常10ms -100ms 当然，进程在时间片用毕之前其Burst Cycle结束，也（主动）交出CPU 假设n个就绪进程，时间片q，任何就绪进程最多等待 (n-1)q单位时间

RR算法举例，时间片设定20个单位 Process Burst Time 甘特图 162 P1 53 P2 17 P3 68 P4 24 20 37 57 77 97 117 121 134 154 162

轮转法(续) 平均周转时间通常优于SJF 响应时间一定优于SJF 性能分析 q large  FCFS q small  上下文切换开销太大，q 必须远远大于上下文切换时间

时间片与上下文切换时间的关系

周转时间受时间片的影响

多层队列(Multilevel Queue) 把就绪队列拆分成几个队列 例如： 要求交互的进程，在前台队列 可以批处理的进程，在后台队列 每个队列有其自己的调度算法。例如， 前台就绪队列 – RR 后台就绪队列 – FCFS

多层队列调度示例

设计多层队列 就绪进程进入就绪队列时，决定去哪儿？ CPU怎么在队列间分配？ 固定优先权法。例如，先前台队列，再后台队列。 时间片办法。例如，80%的CPU时间给前台队列，20%的CPU时间给后台进程

多层反馈队列(Multilevel Feedback Queue) 基本上类似于多层队列算法 另外考虑了，进程可以在就绪队列之间“迁移”

多层反馈队列示例 三层队列 Q0 – 用RR算法，时间片 8 ms Q1 –用RR算法，时间片 16 ms Q2 – 用FCFS算法

多层反馈队列示例(续)

多层反馈队列示例(续) 调度场景 一个就绪进程进入Q0 层。当它分配到CPU，可执行 8 ms。如果它 8 ms后没有执行完毕，则迁移至Q1层。否则，它离开就绪队列，该干嘛干嘛。 在Q1层，当它分配到CPU，可执行 16 ms。如果它 16 ms后没有执行完毕，则迁移至Q2层。否则，它离开就绪队列，该干嘛干嘛。

设计多层反馈队列 队列个数 每层队列它自己的调度算法 一个算法，将就绪进程升级至高层次队列 一个算法，将就绪进程降级至低层次队列 一个算法，决定当一个就绪进程进入就绪队列时，去哪层

实时调度 硬实时系统 – 调度机制能够确保一个关键任务在给定的时间点前完成 软实时计算 – 调度机制尽量给予关键任务最高优先级，尽量在预定时间点前完成

调度算法评估 确定模型法(Deterministic modeling) –采用事先设定的特定负荷，计算在给定负荷下每个算法的性能 排队模型(Queueing models) 编程实现该算法，观察其执行情况 仿真

仿真

习题分析

习题分析

作业 随堂练习 习题作业 http://jpkc.scezju.com/czxtyl/redir.php?catalog_id=105808 书后习题3.2、4.1、4.3、4.4、4.8、5.4、5.5、5.7、5.10 10月29日晚上12点前发邮件给TA（徐小高， 18942247086@163.com ）。 文件名以“姓名+学号+专业”命名。

习题作业

习题作业

习题作业

习题作业

习题作业

END