Download presentation
Presentation is loading. Please wait.
1
CPU调度(Scheduling) 主讲教师：夏莹杰
2
相关基本概念 引入多程序设计，目的是提高计算机资源利用率，尤其是CPU利用率(CPU utilization)
CPU密集 – I/O密集的循环 进程的执行，呈现出CPU运行和I/O等待的交替循环 CPU密集型，I/O密集型
3
CPU运行和I/O等待的交替循环
4
CPU调度器的使命 CPU调度器(Scheduler) 从内存中一堆准备就绪的进程中（就绪队列中的就绪进程），选取一个进程；
后者也可以由dispatcher完成，见后面讨论
5
CPU调度器的操作对象 Scheduler
6
CPU调度器的操作时机 调用CPU调度器的时机，通常发生在： 1. 某一进程从执行状态转为等待状态 2. 某一进程从执行状态转为就绪状态
1. 某一进程从执行状态转为等待状态 2. 某一进程从执行状态转为就绪状态 3. 某一进程从等待状态转为就绪状态 4. 某一进程终止 注意，调度时机不限于此4种情况。例如？ 第1种情形和第4种情形称作“非抢占式” (nonpreemptive)调度。见后续讨论。 第2种情形和第3种情形称作“抢占式” (preemptive)调度。见后续讨论。
7
CPU分配器(Dispatcher) CPU调度器决定了将CPU分配给谁。后续操作就是，CPU分配器将CPU控制权移交给该进程。操作内容通常包括： 上下文切换(switching context) 从内核态(kernel mode)转移至用户态(user mode) 跳转至用户程序中PC寄存器所指示的位置 分配延迟(Dispatch latency) – CPU分配器暂停前一进程，启动后一进程所经历的时间
8
CPU调度器追求指标 CPU利用率(CPU utilization) 吞吐率(Throughput) – 单位时间内完成执行的进程数
周转时间(Turnaround time) – 执行某一进程所耗用的CPU累积时间 等待时间(Waiting time) – 某一进程等待在就绪队列里面的累积时间 响应时间(Response time) – 某一进程从发出调度请求，到其得到CPU调度器响应，其间所经历的时间
9
优异的指标，当然是 Maximize CPU utilization Maximize throughput
Minimize turnaround time Minimize waiting time Minimize response time
10
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 平均等待时间：( )/3 = 17 P1 P2 P3 24 27 30
11
FCFS调度算法 (续) 假设进程到达就绪队列的顺序： P2 , P3 , P1 FCFS调度算法的调度结果有显著变化，如甘特图：
平均等待时间：( )/3 = 3，改善非常多 ！ 启示：短进程先于长进程，会得到意外效果 P1 P3 P2 6 3 30
12
Shortest-Job-First (SJF) 调度算法
算法要求： 进入就绪队列的进程预告需要多长CPU时间才能完成本次执行 算法思想： 选取就绪队列中，“需要CPU时间”最短的进程
13
举例：非抢占式(Non-Preemptive) SJF
Process Arrival Time Burst Time P P P P SJF (非抢占式) 平均等待时间 = ( )/4 = 4 P1 P3 P2 7 3 16 P4 8 12
14
举例：抢占式(Preemptive) SJF
Process Arrival Time Burst Time P P P P SJF (抢占式) 平均等待时间 = ( )/4 = 3 P1 P3 P2 4 2 11 P4 5 7 16
15
两种SJF策略比较 非抢占式(Non-Preemptive) – 一旦CPU分配给了某个进程，就不能“抢过来”，除非该进程主动放弃CPU（CPU burst cycle结束，或者进程转去做I/O操作） 抢占式(Preemptive) – 上述描述的“非” 当一个进程进入就绪队列，如果它的CPU时间小于当前拥有CPU的进程的剩余“预估”时间，前者抢占后者的CPU。此算法称作Shortest-Remaining-Time-First (SRTF)
16
关于SJF算法的结论 SJF是最优算法 – why SJF算法有致命缺陷 – To Be Cont
17
进入就绪队列的进程怎么“预估”CPU时间？
不可能准确地预测，为什么？(e.g. 等待输入数据) 只能根据过去的CPU burst cycles拟合 例如，指数平均Exponential average思想
18
图，“指数平均”求进程的下一个CPU Burst Cycle
19
假如设计一个新算法: HRN (Highest response Ratio Next)
HRN = (W + T) / T W代表等待时间，T代表预估CPU时间，用HRN评估调度的优先级。 Process Arrival Time Burst Time P P P P
20
优先权法(Priority Scheduling)
每个进程都有一个优先数(priority number)，通常是个整型数 选取就绪队列中，优先权最高的进程 （假设：最小优先数 最高优先权） Preemptive，高优先权的进程到达时引起调度 Nonpreemptive，高优先权的进程到达时不触发一次调度 当优先权定义为进程“需要的CPU时间”时，SJF算法就是优先权法
21
Process Burst Time Priority
举例：优先权法(非抢占式) Process Burst Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P 甘特图 平均等待时间 = ( )/5 = 8.2 P2 P1 P5 6 1 P4 16 18 P3 19
22
优先权算法的一个缺陷 Issue 进程饥饿(Starvation) – 优先权较低的就绪进程可能永远得不到CPU
Solution Aging思想 – 就绪进程等在就绪队列里的时间，折算叠加到进程优先权。因此，等待在就绪队列里的进程，其优先权单调递增
23
轮转法(Round Robin，RR) 每个就绪进程获得一小段CPU时间(时间片，time quantum)，通常10ms -100ms
当然，进程在时间片用毕之前其Burst Cycle结束，也（主动）交出CPU 假设n个就绪进程，时间片q，任何就绪进程最多等待 (n-1)q单位时间
24
RR算法举例，时间片设定20个单位 Process Burst Time 甘特图 162 P1 53 P2 17 P3 68 P4 24
20 37 57 77 97 117 121 134 154 162
25
轮转法(续) 平均周转时间通常优于SJF 响应时间一定优于SJF 性能分析 q large FCFS
q small 上下文切换开销太大，q 必须远远大于上下文切换时间
26
时间片与上下文切换时间的关系
27
周转时间受时间片的影响
28
多层队列(Multilevel Queue)
把就绪队列拆分成几个队列 例如： 要求交互的进程，在前台队列 可以批处理的进程，在后台队列 每个队列有其自己的调度算法。例如， 前台就绪队列 – RR 后台就绪队列 – FCFS
29
多层队列调度示例
30
设计多层队列 就绪进程进入就绪队列时，决定去哪儿？ CPU怎么在队列间分配？ 固定优先权法。例如，先前台队列，再后台队列。
时间片办法。例如，80%的CPU时间给前台队列，20%的CPU时间给后台进程
31
多层反馈队列(Multilevel Feedback Queue)
基本上类似于多层队列算法 另外考虑了，进程可以在就绪队列之间“迁移”
32
多层反馈队列示例 三层队列 Q0 – 用RR算法，时间片 8 ms Q1 –用RR算法，时间片 16 ms Q2 – 用FCFS算法
33
多层反馈队列示例(续)
34
多层反馈队列示例(续) 调度场景 一个就绪进程进入Q0 层。当它分配到CPU，可执行 8 ms。如果它 8 ms后没有执行完毕，则迁移至Q1层。否则，它离开就绪队列，该干嘛干嘛。 在Q1层，当它分配到CPU，可执行 16 ms。如果它 16 ms后没有执行完毕，则迁移至Q2层。否则，它离开就绪队列，该干嘛干嘛。
35
设计多层反馈队列 队列个数 每层队列它自己的调度算法 一个算法，将就绪进程升级至高层次队列 一个算法，将就绪进程降级至低层次队列
一个算法，决定当一个就绪进程进入就绪队列时，去哪层
36
实时调度 硬实时系统 – 调度机制能够确保一个关键任务在给定的时间点前完成
软实时计算 – 调度机制尽量给予关键任务最高优先级，尽量在预定时间点前完成
37
调度算法评估 确定模型法(Deterministic modeling) –采用事先设定的特定负荷，计算在给定负荷下每个算法的性能
排队模型(Queueing models) 编程实现该算法，观察其执行情况 仿真
38
仿真
39
习题分析
40
习题分析
41
作业 随堂练习 习题作业 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（徐小高， ）。 文件名以“姓名+学号+专业”命名。
42
习题作业
43
习题作业
44
习题作业
45
习题作业
46
习题作业
47
END
Similar presentations
