第05讲_进程调度

1、1第第 五五 讲讲清华大学软件学院清华大学软件学院22.6 进程调度进程调度在多道系统当中，往往有多个进程同时在内存中在多道系统当中，往往有多个进程同时在内存中运行。在任何时刻，一个进程只可能是以下三种运行。在任何时刻，一个进程只可能是以下三种状态之一：状态之一：v 运行状态：该进程正在运行状态：该进程正在CPU上运行，每个上运行，每个CPU 上最多只能有一个进程在运行；上最多只能有一个进程在运行；v 就绪状态：进程已经就绪，随时可以运行；就绪状态：进程已经就绪，随时可以运行；v 阻塞状态：如在某个信号量上被阻塞，等待阻塞状态：如在某个信号量上被阻塞，等待I/O与此相对应，操作系统会维护相应的

2、状态队列。与此相对应，操作系统会维护相应的状态队列。3就绪队列和各种就绪队列和各种I/O设备队列设备队列（本图摘自（本图摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）选择谁去运行？选择谁去运行？4 在操作系统中，负责去做这个选择的那在操作系统中，负责去做这个选择的那 部分程序，称为部分程序，称为调度程序调度程序(scheduler)； 调度程序在决策过程中所采用的算法，调度程序在决策过程中所采用的算法， 称为是称为是调度算法调度算法； 调度程序是调度程序是CPU资源的管理者；资源的管理者； 调度的对象是进程，也可以是

3、线程，大调度的对象是进程，也可以是线程，大 多数的调度问题对两者都是适用的。多数的调度问题对两者都是适用的。52.6.1 关于调度的若干问题关于调度的若干问题1. 历史背景q 在早期的简单批处理系统当中，调度算法很简在早期的简单批处理系统当中，调度算法很简 单：选择磁带上的下一个作业运行；单：选择磁带上的下一个作业运行；q 随着分时系统的出现，同时有多个用户在等待随着分时系统的出现，同时有多个用户在等待 服务，使得调度算法变得越来越复杂。有些大服务，使得调度算法变得越来越复杂。有些大 型机系统还把批处理与分时结合在一起，更增型机系统还把批处理与分时结合在一起，更增 大了难度。由于当时的大了难度

4、。由于当时的CPU时间是一种稀缺资时间是一种稀缺资 源，因此调度算法的好坏将直接影响到系统的源，因此调度算法的好坏将直接影响到系统的 性能和用户的满意度，算法的设计很受重视。性能和用户的满意度，算法的设计很受重视。6q 随着个人计算机时代的到来，形势发生了变化。随着个人计算机时代的到来，形势发生了变化。 首先，在首先，在PC上通常只有一个进程在活动，这样，上通常只有一个进程在活动，这样， 调度程序无事可做。其次，计算机变得越来越快调度程序无事可做。其次，计算机变得越来越快, CPU已不是稀缺资源了，哪个程序先运行或运行已不是稀缺资源了，哪个程序先运行或运行, 已经不重要了。因此，调度算法的作用

5、已经显得已经不重要了。因此，调度算法的作用已经显得 微不足道了。微不足道了。q 不过，对于那些高端联网工作站和服务器而言，不过，对于那些高端联网工作站和服务器而言， 多个进程需要同时竞争多个进程需要同时竞争CPU的使用权，因此调度的使用权，因此调度 问题又出现了。首先，调度程序要选择合适的进问题又出现了。首先，调度程序要选择合适的进 程去运行，因为对于不同的进程，用户期望的响程去运行，因为对于不同的进程，用户期望的响 应时间和要求是不同的；其次，调度程序要注意应时间和要求是不同的；其次，调度程序要注意 CPU的使用效率，因为进程切换的开销很大。的使用效率，因为进程切换的开销很大。72. 进程的

6、行为 CPU繁忙（繁忙（CPU-bound）的进程：大部分时间的进程：大部分时间 处于运行和就绪状态；处于运行和就绪状态； I/O繁忙（繁忙（I/O-bound）的进程：大部分时间处的进程：大部分时间处 于阻塞状态。于阻塞状态。8（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）CPU繁忙与繁忙与I/O繁忙繁忙CPU繁忙繁忙I/O繁忙繁忙9 内部因素：进程自身的功能决定了它的各种工内部因素：进程自身的功能决定了它的各种工作量。例如，矩阵相乘进程的计算量大，文件作量。例如，矩阵相乘进程的计算量大，文件管理进程的管理进程的I/O需

7、求很大；需求很大； 外部因素：计算机系统的运行速度决定了完成外部因素：计算机系统的运行速度决定了完成这些工作量所需要的时间长短。工作量和工作这些工作量所需要的时间长短。工作量和工作时间是两回事，判断一个进程是属于时间是两回事，判断一个进程是属于CPU繁忙繁忙还是属于输入输出繁忙，主要看它的计算时间还是属于输入输出繁忙，主要看它的计算时间和输入输出时间；和输入输出时间； I/O设备的运行速度较慢，设备的运行速度较慢，CPU的运行速度较的运行速度较快，而且更新换代的速度快，将来进程都趋向快，而且更新换代的速度快，将来进程都趋向于于I/O繁忙。繁忙。CPU繁忙还是繁忙还是I/O繁忙？繁忙？10 VC

8、D播放软件；播放软件； WORD文字编辑器；文字编辑器； 磁盘碎片整理工具磁盘碎片整理工具defrag。CPU繁忙还是繁忙还是I/O繁忙？（续）繁忙？（续）113. 何时调度？1. 当一个新的进程被创建时，是执行新进程还当一个新的进程被创建时，是执行新进程还是继续执行父进程？是继续执行父进程？2. 当一个进程运行完毕时；当一个进程运行完毕时；3. 当一个进程由于当一个进程由于I/O、信号量或其他的某个原、信号量或其他的某个原因被阻塞时；因被阻塞时；4. 当一个当一个I/O中断发生时，表明某个中断发生时，表明某个I/O操作已经操作已经完成，而等待该完成，而等待该I/O操作的进程转入就绪状态；操作

9、的进程转入就绪状态；5. 在分时系统中，当一个时钟中断发生时。在分时系统中，当一个时钟中断发生时。12不可抢占调度方式不可抢占调度方式：一个进程若被选中，就：一个进程若被选中，就一直运行下去，直到它被阻塞（一直运行下去，直到它被阻塞（I/O，或正在，或正在等待其他的进程），或主动地交出等待其他的进程），或主动地交出CPU。以。以上的情形上的情形13均可发生调度；均可发生调度；可抢占调度方式可抢占调度方式：当一个进程在运行时，调：当一个进程在运行时，调度程序可以打断它。以上的情形度程序可以打断它。以上的情形15均可发均可发生调度，另外，在其他的一些情形下，如就生调度，另外，在其他的一些情形下，如

10、就绪队列中有进程的优先级高于当前运行进程绪队列中有进程的优先级高于当前运行进程的优先级，也可能立即进行调度。的优先级，也可能立即进行调度。两种调度方式两种调度方式134. 调度算法的类别不同的不同的OS有不同的目标，对调度程序有不同的有不同的目标，对调度程序有不同的要求，因此需要不同类型的调度算法。要求，因此需要不同类型的调度算法。批处理系统：无须及时的用户响应，采用不批处理系统：无须及时的用户响应，采用不可抢占的调度方式，或时间间隔很长的可抢可抢占的调度方式，或时间间隔很长的可抢占调度方式，从而允许进程能长时间运行，占调度方式，从而允许进程能长时间运行，减少进程的切换次数，提高系统的性能；减

11、少进程的切换次数，提高系统的性能；交互式系统：及时的用户响应非常重要，必交互式系统：及时的用户响应非常重要，必须采用可抢占的调度方式。以防单个进程占须采用可抢占的调度方式。以防单个进程占用太多用太多CPU时间，影响到其他进程的运行。时间，影响到其他进程的运行。实时系统：对响应时间要求苛刻，每个进程实时系统：对响应时间要求苛刻，每个进程运行时间很短，可采用可抢占的调度方式。运行时间很短，可采用可抢占的调度方式。145. 调度算法的目标算法调度的目标是多元的，有些是可以共存的，算法调度的目标是多元的，有些是可以共存的，也有些是相互牵制的，对于一个实际的调度算法也有些是相互牵制的，对于一个实际的调度

12、算法来说，有一个综合权衡的过程。来说，有一个综合权衡的过程。所有系统普遍适用的目标：所有系统普遍适用的目标： 公平：大致相当的两个进程所得到的公平：大致相当的两个进程所得到的CPU时间时间 也应是大致相同的；也应是大致相同的； 对已制订的调度策略必须能贯彻执行；对已制订的调度策略必须能贯彻执行； 均衡：尽可能使整个系统的各部分都忙起来，均衡：尽可能使整个系统的各部分都忙起来， 提高系统资源的使用效率。提高系统资源的使用效率。15批处理系统中调度算法的评价指标：批处理系统中调度算法的评价指标： 吞吐量吞吐量（Throughput）：单位时间内所完成的）：单位时间内所完成的 作业数，与作业本身特性

13、和调度算法有关；作业数，与作业本身特性和调度算法有关； 周转时间周转时间（Turnaround time）：一个批处理作）：一个批处理作 业从提交到完成（得到结果）所经历的时间。业从提交到完成（得到结果）所经历的时间。 包括：在收容队列中等待，包括：在收容队列中等待，CPU上执行，就绪上执行，就绪 队列和阻塞队列中等待，结果输出等待；队列和阻塞队列中等待，结果输出等待；C 平均周转时间：一批作业的周转时间的平均值；平均周转时间：一批作业的周转时间的平均值；C 平均带权周转时间：权值是实际执行时间的倒数平均带权周转时间：权值是实际执行时间的倒数; CPU的利用率的利用率：大中型主机的：大中型主机

14、的CPU较贵，所以较贵，所以 让它时刻不停地转着。让它时刻不停地转着。16周转时间：周转时间：iiiSET（Ei表示作业表示作业i完成时间，完成时间， Si表示作业表示作业i提交时间）提交时间）平均周转时间：平均周转时间：NiiTNT11(N表示作业的个数表示作业的个数)平均带权周转时间：平均带权周转时间：NiiirTNW11(ri表示作业表示作业i的实际执行时间的实际执行时间)17交换式系统中调度算法的评价指标：交换式系统中调度算法的评价指标： 响应时间：用户输入一个请求（如击键）到系统响应时间：用户输入一个请求（如击键）到系统 给出首次响应（如屏幕显示）的时间。响应时间给出首次响应（如屏幕

15、显示）的时间。响应时间 越短越好，优先考虑交互式进程；越短越好，优先考虑交互式进程； 相称性：满足用户对程序运行时间的期望值。相称性：满足用户对程序运行时间的期望值。实时系统中调度算法的评价指标：实时系统中调度算法的评价指标： 实时响应：必须严格地遵守时间期限；实时响应：必须严格地遵守时间期限； 可预测性：在实时多媒体系统中，信号的播放必可预测性：在实时多媒体系统中，信号的播放必 须连贯，不能时断时续。须连贯，不能时断时续。182.6.2 批处理系统中的调度算法批处理系统中的调度算法1. 先来先服务 先来先服务先来先服务（First Come First Served，FCFS； First

16、In First Out，FIFO）：按照作业到达的）：按照作业到达的 先后次序进行调度；先后次序进行调度； 不可抢占方式：当前进程占用不可抢占方式：当前进程占用CPU，直到执行，直到执行 完或被阻塞，才让出完或被阻塞，才让出CPU给另外一个进程；给另外一个进程； 在进程被唤醒后（如在进程被唤醒后（如I/O完成），并不立即恢复完成），并不立即恢复 执行，而是放在就绪队列的末尾；执行，而是放在就绪队列的末尾； 优点：简单、公平，易于理解也易于实现。优点：简单、公平，易于理解也易于实现。 现实生活中应用广泛：排队。现实生活中应用广泛：排队。19问题问题1. 平均周转时间取决于各作业到达的顺序，若平

17、均周转时间取决于各作业到达的顺序，若短作业位于长作业之后，将增大平均周转时间。短作业位于长作业之后，将增大平均周转时间。例如，三个作业例如，三个作业A、B、C的运行时间为的运行时间为24、3、3时间时间 24 27 30ABC平均周转时间平均周转时间(24+27+30)/327平均等待时间平均等待时间(0+24+27)/317时间时间 3 6 30ABC平均周转时间平均周转时间(3+6+30)/313平均等待时间平均等待时间(0+3+6)/3320问题问题2. 无法充分利用无法充分利用CPU繁忙的作业与繁忙的作业与I/O繁忙的繁忙的作业之间的互补关系。如果作业之间的互补关系。如果CPU繁忙的作

18、业独占很繁忙的作业独占很长时间的长时间的CPU，使得，使得I/O设备空闲，也使得设备空闲，也使得I/O繁忙繁忙的作业无法运行。的作业无法运行。作业作业A作业作业BCPUI/O作业作业A作业作业B时间时间t0t1 t2t3t4212. 短作业优先 短作业优先短作业优先（Shortest Job First，SJF），设计），设计 目标是改进目标是改进FCFS算法，减少平均周转时间；算法，减少平均周转时间； SJF算法要求作业在开始执行时预计执行时间，算法要求作业在开始执行时预计执行时间， 对预计执行时间短的作业优先分派处理器；对预计执行时间短的作业优先分派处理器； 两种实现方案：两种实现方案：Q

19、 不可抢占方式：当前作业在运行时不会被打不可抢占方式：当前作业在运行时不会被打 断，只有运行完毕或阻塞时，才让出断，只有运行完毕或阻塞时，才让出CPU；Q 可抢占方式：如果一个新的短作业到来，其可抢占方式：如果一个新的短作业到来，其 运行时间小于当前正在运行作业的剩余时间，运行时间小于当前正在运行作业的剩余时间， 则抢占则抢占CPU运行，称为运行，称为SRTF（Shortest Remaining Time First）。）。22 可以证明：对于一组同时到达的作业，采用可以证明：对于一组同时到达的作业，采用SJF 算法将得到一个算法将得到一个最小最小的平均周转时间。的平均周转时间。D时间时间A

20、Ca a+b a+b+c a+b+c+d 例如，考察例如，考察4个作业个作业A、B、C、D，其运行时间分，其运行时间分别为别为a、b、c、dBA、B、C、D的周转时间分别为的周转时间分别为a、a+b、a+b+c和和a+b+c+d，因此平均周转时间为：，因此平均周转时间为：(4a+3b+2c+d)/4显然，当显然，当a b c d时，平均周转时间最小。时，平均周转时间最小。23取得最优解的前提之一：这组作业必须同时到达；取得最优解的前提之一：这组作业必须同时到达；例如：例如：进程进程到达时间到达时间运行时间运行时间P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（不可抢占）

21、：（不可抢占）：P1P3P2P403781216平均周转时间：平均周转时间：(7 + 10 + 4 + 11) / 4 = 8平均等待时间：平均等待时间：(0 + 6 + 3 + 7) / 4 = 4若按若按P2,P3,P4,P1顺序顺序, 平均周转和等待时间平均周转和等待时间7.75, 3.7524进程进程到达时间到达时间运行时间运行时间P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4SJF（可抢占）：（可抢占）：P1P3P2P4P2P1027411165平均周转时间：平均周转时间：(16 + 5 + 1 + 6) / 4 = 7平均等待时间：平均等待时间：(9 + 1 +

22、0 + 2) / 4 = 325前提条件之二：需要事先估计作业的运行时间前提条件之二：需要事先估计作业的运行时间如何知道作业的运行时间？如何知道作业的运行时间？% 该时间只可能是一个估计值；该时间只可能是一个估计值；% 让提交该作业的用户来提供。不太实用；让提交该作业的用户来提供。不太实用；% 使用前面的使用前面的CPU运行时间来预测后面的运行时间来预测后面的CPU运运 行时间，通过过去的行为来预测将来的行为。行时间，通过过去的行为来预测将来的行为。C 如果一个作业已经运行很长时间了，那它可能如果一个作业已经运行很长时间了，那它可能 还会运行更长的时间；还会运行更长的时间；C 使用指数平均值函

23、数来预测下一段使用指数平均值函数来预测下一段CPU时间时间;26指数平均值函数方法指数平均值函数方法.1 1nnnt1. tn 第第n个个CPU运行时间的实际长度；运行时间的实际长度；2. n+1 下一个下一个CPU运行时间的预测长度；运行时间的预测长度；3. 定义系数定义系数 ，0 14. 定义：定义：273. 三层调度模型（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）28 准入调度：决定哪一些作业能够进入系统运行。准入调度：决定哪一些作业能够进入系统运行。 在这个层次上的调度算法主要有短作业优先进入在这个层次上的调度算

24、法主要有短作业优先进入, 以及把以及把CPU繁忙的作业和繁忙的作业和I/O繁忙的作业混合在繁忙的作业混合在 一起提交给系统；一起提交给系统； 存储调度：决定哪一些进程应该留在内存中，哪存储调度：决定哪一些进程应该留在内存中，哪 一些进程应该保存在磁盘上。需要考虑的因素包一些进程应该保存在磁盘上。需要考虑的因素包 括该进程呆在内存或磁盘上的时间长短，它所用括该进程呆在内存或磁盘上的时间长短，它所用 的的CPU时间以及它的优先级等；时间以及它的优先级等； CPU调度：从内存当中，选择一个已经就绪的进调度：从内存当中，选择一个已经就绪的进 程去运行。程去运行。批处理系统中的三层调度模型批处理系统中的

25、三层调度模型292.6.3 交互式系统中的调度算法交互式系统中的调度算法1. 时间片轮转法 在在时间片轮转算法时间片轮转算法（Round-Robin，RR）中，将）中，将 所有的就绪进程按照所有的就绪进程按照FCFS原则，排成一个队列；原则，排成一个队列； 每次调度时将处理器分派给队首进程，让其执行每次调度时将处理器分派给队首进程，让其执行 一小段一小段CPU时间（时间片）；时间（时间片）； 在一个时间片结束时，如果进程还没有执行完的在一个时间片结束时，如果进程还没有执行完的 话，将发生时钟中断，在时钟中断中，进程调度话，将发生时钟中断，在时钟中断中，进程调度 程序将暂停当前进程的执行，并将其

26、送到就绪队程序将暂停当前进程的执行，并将其送到就绪队 列的末尾，然后执行当前的队首进程；列的末尾，然后执行当前的队首进程； 如果一个进程在它的时间片用完之前就已结束或如果一个进程在它的时间片用完之前就已结束或 被阻塞，那么立即让出被阻塞，那么立即让出CPU。30开始时，进程开始时，进程B位于队列之首，因此被调度执行。当位于队列之首，因此被调度执行。当它的时间片用完后，就把它送到就绪队列的末尾。它的时间片用完后，就把它送到就绪队列的末尾。同时，进程同时，进程F成为队首进程，被调度运行。成为队首进程，被调度运行。（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Oper

27、ating Systems” ）31Round robin, too.32 优点：优点：e 公平性公平性：各个就绪进程平均地分配：各个就绪进程平均地分配CPU的使用的使用 时间。假设有时间。假设有n个就绪进程，时间片大小为个就绪进程，时间片大小为q， 那么每个进程将得到那么每个进程将得到1/n的的CPU时间；时间；e 活动性活动性：每个进程最多等待：每个进程最多等待(n-1)q时间就能够时间就能够 再次得到再次得到CPU去运行；去运行；e 一般来说，平均周转时间较一般来说，平均周转时间较SJF算法为长，但算法为长，但 能够得到能够得到较短的平均响应时间较短的平均响应时间； 缺点：缺点：q的大小

28、难以确定的大小难以确定（一般在（一般在2050ms）。）。e q太大：退化为太大：退化为FCFS算法，进程在一个时间片算法，进程在一个时间片 内都执行完，响应时间长。如内都执行完，响应时间长。如q=100ms；e q太小：每个进程都需要更多的时间片才能处理太小：每个进程都需要更多的时间片才能处理 完，进程切换次数增加，增大系统开销。如完，进程切换次数增加，增大系统开销。如q=4ms时间片轮转法的特点时间片轮转法的特点33进程进程CPU时间时间P153 P2 17 P368 P4 24一个例子：时间片长度一个例子：时间片长度q20P1P2P3P4P1P3P4P1P3P30 20 37 57 77

29、 97 117 121 134 154 162平均周转时间：平均周转时间：(134 + 37 + 162 + 121) / 4113.5SJF的平均周转时间：的平均周转时间： (94 + 17 + 162 + 41) / 478.5342. 优先级算法1 轮转法有一个缺省的前提，即各进程同等重要；轮转法有一个缺省的前提，即各进程同等重要；1 “人人生而平等人人生而平等”？ 恐怕不太现实！同样，并恐怕不太现实！同样，并 不是每个进程都同等重要，不是每个进程都同等重要， 怎么办？分等级！怎么办？分等级！1 优先级算法优先级算法（Priority Scheduling）：给每个进）：给每个进 程设置

30、一个优先级，然后在所有就绪进程中选择程设置一个优先级，然后在所有就绪进程中选择 优先级最高的那个进程去运行；优先级最高的那个进程去运行；1 SJF就是一个优先级算法，每个进程的优先级是就是一个优先级算法，每个进程的优先级是 它的它的CPU运行时间（时间越短，优先级越高）；运行时间（时间越短，优先级越高）；1 分为分为可抢占可抢占和和不可抢占不可抢占两种方式；各进程优先级两种方式；各进程优先级 的确定方式可分为的确定方式可分为静态静态和和动态动态两种。两种。35静态优先级方式静态优先级方式 确定优先级的依据：确定优先级的依据： 进程类型（系统进程优先级高于用户进程，进程类型（系统进程优先级高于用

31、户进程，交互式进程高于批处理进程）；交互式进程高于批处理进程）； 对系统资源的需求（对对系统资源的需求（对CPU和内存需求较少和内存需求较少的进程，优先级较高）；的进程，优先级较高）； 用户要求（用户级别和付费情况，如军用电用户要求（用户级别和付费情况，如军用电脑、商用电脑）。脑、商用电脑）。 静态方式的缺点：高优先级的进程一直占用静态方式的缺点：高优先级的进程一直占用CPU，低优先级的进程，低优先级的进程“饥饿饥饿”。 静态优先级方式静态优先级方式是指在创建进程时确定进程优先级，是指在创建进程时确定进程优先级，并保持不变到进程结束。并保持不变到进程结束。36动态优先级方式动态优先级方式 为防

32、为防“饥饿饥饿”, 根据运行时间和等待时间调整优先根据运行时间和等待时间调整优先级级 进程每执行一个时间片就降低其优先级。当一进程每执行一个时间片就降低其优先级。当一个进程持续执行时，其优先级降低到让出个进程持续执行时，其优先级降低到让出CPU； 在就绪队列中，等待时间延长则优先级提高，在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。其优先级提高到可被调度执行。 为了让为了让I/O忙起来，可提高忙起来，可提高I/O繁忙进程的优先级。繁忙进程的优先级。但如何判定一个进程是但如何判定一个进程是I

33、/O繁忙的？可把进程优先繁忙的？可把进程优先级设为级设为1/f，f是在上一个时间片中所用的时间比例是在上一个时间片中所用的时间比例动态优先级方式动态优先级方式是指在创建进程时赋予给进程的优是指在创建进程时赋予给进程的优先级，在进程运行过程中可以动态改变，以便获得先级，在进程运行过程中可以动态改变，以便获得更好的调度性能。更好的调度性能。37优先级类别优先级类别（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）可以把进程按照不同的优先级别分组，然后在不同可以把进程按照不同的优先级别分组，然后在不同级别之间使用优先级算法，而在同一

34、级别的各个进级别之间使用优先级算法，而在同一级别的各个进程之间使用时间片轮转法。程之间使用时间片轮转法。383. 多级队列算法多级队列算法多级队列算法（Multilevel Queue）引入多个就绪）引入多个就绪队列，通过各个队列的区别对待，达到一个综合的队列，通过各个队列的区别对待，达到一个综合的调度目标。调度目标。K 根据进程的性质或类型的不同，将就绪队列再分根据进程的性质或类型的不同，将就绪队列再分 为为若干个子队列若干个子队列，如系统进程、用户交互进程、，如系统进程、用户交互进程、 批处理进程等；批处理进程等；K 不同的队列可以有不同的队列可以有不同的优先级不同的优先级；K 不同的队列

35、可以采用各自不同的队列可以采用各自不同的调度算法不同的调度算法，如前，如前 台的交互式进程可采用台的交互式进程可采用RR算法，后台的批处理进算法，后台的批处理进 程可采用程可采用FCFS算法。算法。39K 在各个队列之间也必须进行调度：在各个队列之间也必须进行调度： 固定优先级调度固定优先级调度：按照各种类型的进程的优先：按照各种类型的进程的优先 级别从高到低地进行，先运行最高优先级的所级别从高到低地进行，先运行最高优先级的所 有进程，再运行次一级所有进程，依此类推。有进程，再运行次一级所有进程，依此类推。 问题：可能导致问题：可能导致“饥饿饥饿”； 时间片方法时间片方法：把：把CPU时间按比

36、例分配给不同的时间按比例分配给不同的 队列，然后再由各个队列的调度算法去调度，队列，然后再由各个队列的调度算法去调度， 如如80给前台的交互式进程队列（给前台的交互式进程队列（RR算法），算法）， 20给后台的批处理进程队列（给后台的批处理进程队列（FCFS）。）。40（本图摘自（本图摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”）多级队列算法的一个例子多级队列算法的一个例子414. 多级反馈队列算法J 多级队列算法把每个进程按照它的类型多级队列算法把每个进程按照它的类型固定固定在一在一 个队列中，但问题是如何来确定进

37、程的类型？个队列中，但问题是如何来确定进程的类型？ 而且有的进程其类型可能动态变化，怎么办？而且有的进程其类型可能动态变化，怎么办？ “路遥知马力，日久见人心路遥知马力，日久见人心”！J 多级反馈队列算法多级反馈队列算法 (Multilevel Feedback Queue) 即根据一个进程的运行反馈信息，即根据一个进程的运行反馈信息，动态地动态地调整它调整它 所在的队列。所在的队列。F 反馈反馈（Feedback）：即进程在运行当中的表）：即进程在运行当中的表 现，例如，它是否需要整个的时间片用于计现，例如，它是否需要整个的时间片用于计 算，或者它是否经常地执行算，或者它是否经常地执行I/O

38、操作？操作？42J 如何实现多级反馈队列算法？需要确定以下的一如何实现多级反馈队列算法？需要确定以下的一 些参数：些参数：F 队列的个数；队列的个数；F 每个队列所用的调度算法；每个队列所用的调度算法；F 用来确定何时给一个进程用来确定何时给一个进程“升级升级”的方法；的方法；F 用来确定何时给一个进程用来确定何时给一个进程“降级降级”的方法；的方法；F 用来确定一个进程的初始队列的方法；用来确定一个进程的初始队列的方法；43多级反馈队列算法的一个例子多级反馈队列算法的一个例子 三种优先级别，三种优先级别，3最高、最高、1最低，三个就绪队列。时间片长度最低，三个就绪队列。时间片长度 分别为分别

39、为N、2N和和4N； 新进程进入内存后，优先级为新进程进入内存后，优先级为3，加入队列，加入队列3的末尾，按的末尾，按FCFS 算法调度；若一个时间片内未能执行完，则优先级降为算法调度；若一个时间片内未能执行完，则优先级降为2，加，加 入到队列入到队列2的末尾，同样按的末尾，同样按FCFS算法调度；依此类推。算法调度；依此类推。 如果进程在时间片用完之前即被阻塞，则增加它的优先级；如果进程在时间片用完之前即被阻塞，则增加它的优先级； 仅当较高优先级的队列为空，才调度较低优先级的队列中的进仅当较高优先级的队列为空，才调度较低优先级的队列中的进 程执行。若进程执行时有新进程进入较高优先级的队列，则

40、抢程执行。若进程执行时有新进程进入较高优先级的队列，则抢 先执行新进程。先执行新进程。优先级优先级32144多级反馈队列算法是时间片轮转算法和优先级算多级反馈队列算法是时间片轮转算法和优先级算法法的综合和发展。其特点是：的综合和发展。其特点是： 为提高系统吞吐量和缩短平均周转时间而照顾短为提高系统吞吐量和缩短平均周转时间而照顾短进程：新进程一进来即赋予最高优先级。进程：新进程一进来即赋予最高优先级。 为获得较好的为获得较好的I/O设备利用率和缩短响应时间而设备利用率和缩短响应时间而照顾了照顾了I/O繁忙的进程：繁忙的进程： I/O繁忙进程：让其进入最高优先级队列，以及时启繁忙进程：让其进入最高

41、优先级队列，以及时启动动I/O操作。通常只需一个小时间片，即可处理完一操作。通常只需一个小时间片，即可处理完一次次I/O请求，然后转入到阻塞队列。请求，然后转入到阻塞队列。 CPU繁忙进程：每次都执行完时间片，进入更低级队繁忙进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。列。最终采用最大时间片来执行，减少调度次数。 不必估计进程的执行时间，动态调节，能够适应不必估计进程的执行时间，动态调节，能够适应一个进程在不同时间段的不同运行特点。一个进程在不同时间段的不同运行特点。452.6.4 实时系统中的调度算法实时系统中的调度算法 在实时系统中，对时间的要求是非常

42、严格的。典在实时系统中，对时间的要求是非常严格的。典 型的例子是：一个或多个外部的物理设备定期或型的例子是：一个或多个外部的物理设备定期或 不定期地生成激励信号，而计算机必须在一定的不定期地生成激励信号，而计算机必须在一定的 时间期限内做出恰当的反应。时间期限内做出恰当的反应。 硬实时硬实时：有一个绝对的时间期限，计算机的反应：有一个绝对的时间期限，计算机的反应 动作必须在此期限之前完成，如核电站的控制系动作必须在此期限之前完成，如核电站的控制系 统；统；软实时软实时：偶尔错过一次期限虽然是令人不快：偶尔错过一次期限虽然是令人不快 的，但也是可以容忍的，如的，但也是可以容忍的，如VCD的播放系统；的播放系统； 实时调度算法可以是实时调度算法可以是静态的静态的或或动态的动态的，前者在系，前者在系 统开始运行之前即已做好调度决策；而后者是在统开始运行之前即已做好调度决策；而后者是在 运行中做出调度决策。运行中做出调度决策。462.6.5 线程调度线程调度在进程调度中，如果每个进程都带有多个的在进程调度中，如果每个进程都带有多个的线程，那么我们就有了两个层面上的并行关线程，那么我们就有了两个层面上的并行关