中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn Fall 2013 第四讲 CPU调度（part II） 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn Fall 2013

内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

先来先服务算法 先来先服务算法FCFS First Come, First Served 是一种最简单的调度算法 可用于作业调度、进程调度 按照请求处理的时间先后顺序，先来先服务 通过采用一个FIFO的PCB队列来实现 可用于作业调度、进程调度 前者每次调度时从后备作业队列中，选择一个或者多个最先进入该队列的作业 后者每次从就绪队列中，选择一个最先进入该队列的进程

先来先服务算法举例（1） 由此可知，FCFS算法比较有利于长作业，而不利于短作业 进程 名 到达 时间 服务 开始执 行时间 完成 周转 带权周 转时间 A 1 B 100 101 C 2 102 D 3 202 199 1.99 太大了

先来先服务算法举例（2） 对于进程P1、P2和P3， 到达时间均为0 若到达顺序为P1、P2、P3，则按照FCFS调度算法得到的甘特图为： 而平均等待时间为(0+24+27)/3=17

若到达顺序为P2、P3、P1，则按照FCFS调度算法得到的甘特图为：

思考： 定义：CPU繁忙型作业：是指需要大量的CPU时间进行计算，而很少请求I/O的作业。 常见于用于科学计算的作业 定义：I/O繁忙型作业：是指CPU进行处理时，又需频繁地请求I/O，而每次I/O的操作时间却又很短。 常见于用于事务处理的作业 请问：当采用FCFS算法时，对这两种作业有何影响？ 阅读参考书：Operating System Concepts，P159页，掌握名词“convoy effect”（即护卫效应） 即：FCFS算法有利于CPU繁忙型作业，而不利于I/O繁忙型作业

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

短作业优先调度 使得短作业（进程）能够比长作业（进程）优先执行 两种实现方案：抢占和非抢占 短作业优先调度（Shortest Job First，SJF） 调度时从后备队列中选择一个或者若干个估计运行时间最短的作业 短进程优先调度（Shortest Process First，SPF） 调度时，从就绪队列中选择一个估计运行时间最短的进程 两种实现方案：抢占和非抢占 阅读：Operating System Concepts，P160，了解SJF算法更细致的定义

SJF算法举例（1）：考虑非抢占方案 饿死现象： 由于某种原因，导致进程长期得不到调度的现象 可以看出：采用SJF算法， 进程名 A B C D E 平均 到达时间 1 2 3 4 服务时间 5 SJF 完成时间 9 18 6 13 周转时间 8 16 带权周转时间 2.67 3.1 1.5 2.25 2.1 FCFS 7 12 14 10 11 5.5 3.5 2.8 可以看出：采用SJF算法， 平均周转时间和平均带权周转时间均有明显改善 对短作业，改善 对长作业，恶化，甚至饿死 饿死现象： 由于某种原因，导致进程长期得不到调度的现象

SJF算法举例（2）：考虑非抢占方案 给定4个进程P1、P2、P3、P4 按照SJF算法，可以得到如下甘特图 则4个进程的等待时间依次是：3、16、9、0 其平均为：7 若采用FCFS算法，假设到达顺序为1、2、3、4， 则等待时间依次为：0、6、14、21， 其平均为：10.25

SJF算法的缺点：除了对长作业不利，甚至产生饿死现象之外： 性质： 可以证明，短作业优先调度算法在最小平均等待时间上可以达到最优 SJF算法的缺点：除了对长作业不利，甚至产生饿死现象之外： 完全没有考虑作业的紧迫程度，无法保证紧迫性作业会得到及时的处理 作业时间由用户主观评估，无法得到保证。

阅读： Operating System Concepts，P160-161， 了解SJF的实现难点， 了解执行时间的评估方法， 了解抢占和非抢占的SJF算法

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

基于优先权的调度算法： Priority scheduling 每个进程具有一个优先数（整数） 具有最高优先权的进程得到调度 优先数 VS. 优先权 一般方案：low : high If equal, FCFS Two schemes Preemptive Nonpreemptive

非抢占举例 Priority (nonpreemprive) E.g.: Priority (nonpreemprive) Average waiting time = (6 + 0 + 16 + 18 + 1) /5 = 8.2 Process Burst Time Priority P1 10 3 P2 1 P3 2 P4 4 P5 5

How to define the priorities 优先权调度的难点 How to define the priorities Internally or Externally Possible Starvation（饿死） Low priority processes may never execute Solution Aging – as time progresses increase the priority of the process.

优先权的类型 静态 vs. 动态 静态优先权： 动态优先权： 创建时确定，进程生命期内不变 上面讲的aging

优先级调度算法的包容性 SJF is a priority scheduling where priority is the predicted next CPU burst time FCFS

高响应比优先调度 等待时间 + 要求服务时间 优先权 = ------------------------------------ 优先权 = ------------------------------------ 要求服务时间 Rp  响应比： 等待时间 + 要求服务时间 响应时间 Rp = ------------------------------------ = ------------------- 要求服务时间 要求服务时间 该调度算法大大改进了FCFS和SJF算法的缺点。

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

时间片轮转调度算法 每个进程 计算最长等待时间Max(Twait) Gets a small unit of CPU time (time quantum，时间片), 通常 10-100 ms 时间片到期，进程被抢占，插入就绪队列的最后 计算最长等待时间Max(Twait) 若有N个进程就绪，时间片长度为q Max(Twait)≤ (n-1) q

Example: RR with Time Quantum = 20 Arrival time = 0 Time quantum =20 The Gantt chart is Typically, higher average turnaround than SJF, but better response Process Burst Time P1 53 P2 17 P3 68 p4 24 P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 20 37 57 77 97 117 121 134 154 162

The performance of RR depends heavily on the size of time quantum 过大时， = FCFS 过小时（图）: Hardware: Process sharing Software: context switch, high overhead, low CPU utilization Must be large with respect to context switch

How a Smaller Time Quantum Increases Context Switches

Turnaround Time Varies With The Time Quantum Will the average turnaround time improve as q increase? 80% CPU burst should be shorter than q

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

Multilevel Queue多级队列 Ready queue is partitioned into separate queues: Foreground, interactive, RR & background, batch, FCFS A process is permanently assigned to one queue Each queue has its own scheduling algorithm Preemptive Scheduling must be done between the queues. Fixed priority scheduling i.e.: serve all from foreground then from background Possibility of starvation（饿死） Time slice Each queue gets a certain amount of CPU time which it can schedule among its processes i.e.: 80% VS. 20%

Multilevel Queue Scheduling

Multilevel Feedback Queue多级反馈队列 A process can move between the various queues; aging can be implemented this way Multilevel-feedback-queue scheduler defined by the following parameters: number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service

Example of Multilevel Feedback Queue Three queues: Q0 – time quantum 8 milliseconds, FCFS Q1 – time quantum 16 milliseconds, FCFS Q2 – FCFS

Scheduling A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1. At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.

调度算法 FCFS SJF RR Priority－based 多级队列（及反馈）调度 优先级倒转问题及其解决方案

Priority inversion (优先级倒转 ) When the higher-priority process needs to read or modify kernel data that are currently being accessed by another, lower-priority process The high-priority process would be waiting for a lower-priority one to finish

E.g.: Priority: P1<PRT3<PRT2 PRT3 preempt P1; PRT2 waits for P1; PRT2 waits for PRT3 （图）

PRT2 抢占 PRT3 抢占 P1

Priority inversion (cont.) Solution Priority-inheritance (lending) 优先级继承 PRT2 lends its priory to P1, thus PRT3 could not preempt P1 Priority inheritance must be transitive E.g.: Priority: P1<PRT3<PRT2

另外一种方法： 优先级置顶（天花板协议） 考虑所有可能访问资源的进程优先级 设置置顶优先级（即天花板） 只要有进程被分配到该资源，该进程的优先级就上升到置顶优先级 释放资源时，降回原来的优先级继续运行

回顾 调度的类型 调度的队列模型 调度的准则 调度的算法

作业： 从调度的层次上看，有哪几种调度？试画出同时具有这几种调度的队列模型图。 在选择调度的方式和算法时，面向用户的调度准则有哪些？面向系统的呢？ Ppt中的思考题。

第三次上机： 上机作业： 实现基于静态优先级的调度算法。 （附加，可不做）在上述算法之上，实现FCFS算法和SJF算法。