CH3处理机调度与死锁

1、第三章第三章 处理机调度与死锁处理机调度与死锁在多道程序环境下，进程数目往往多于处理机数在多道程序环境下，进程数目往往多于处理机数目。目。这就要求系统能够按某种算法，动态的把处理机这就要求系统能够按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能，在很大程度上取决于的利用率及改善系统性能，在很大程度上取决于处理机调度的性能。处理机调度的性能。因此，处理机调

2、度便成为因此，处理机调度便成为OS设计的中心问题之设计的中心问题之一。一。3.1 处理机调度的层次处理机调度的层次 一个批处理型作业，从进入系统并驻留在一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完外存的后备队列上开始，直至作业运行完毕，可能要经历下述毕，可能要经历下述。3.1.1 高级调度（高级调度（High Scheduling）又称为又称为作业调度作业调度或或长程调度长程调度（Long-Term Scheduling），用于决定把外存上处于后备），用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建队列中的哪些作业调入内存，并为它们创建进程、分配必要的

3、资源，然后，再将新创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。的进程排在就绪队列上，准备执行。因此有时也称作业调度为因此有时也称作业调度为接纳调度接纳调度（Admission Scheduling）。）。3.1.1 高级调度（高级调度（High Scheduling）1、作业作业：是比程序更为广泛的概念。：是比程序更为广泛的概念。作业作业=程序程序+数据数据+作业说明书作业说明书v在批处理系统中，是在批处理系统中，是以作业为基本单位从外存调入以作业为基本单位从外存调入内存的内存的2、作业步作业步：作业执行中每一个加工步骤作业执行中每一个加工步骤称为一个作称为一个作

4、业步。业步。v“编译编译”作业步作业步-“连接装配连接装配”作业步作业步-“运行运行”作作业步业步3、作业流作业流：若干个作业进入系统后，被依次存放在：若干个作业进入系统后，被依次存放在外存，形成输入的作业流；在操作系统控制下，逐外存，形成输入的作业流；在操作系统控制下，逐个作业进行处理，就形成了处理作业流个作业进行处理，就形成了处理作业流3.1.1 高级调度（高级调度（High Scheduling）v作业控制块作业控制块JCB：是作业在系统中存在的标是作业在系统中存在的标志志，其中保存了系统对作业进行管理和调度，其中保存了系统对作业进行管理和调度所需的全部信息。所需的全部信息。v每当作业进

5、入系统时，系统变为每个作业建每当作业进入系统时，系统变为每个作业建立一个立一个JCB，根据作业类型将其插入到相应，根据作业类型将其插入到相应的后备队列中。的后备队列中。3.1.1 高级调度（高级调度（High Scheduling）在在批处理系统批处理系统中，因作业进入系统后先驻留中，因作业进入系统后先驻留在外存，故在外存，故需要有作业调度需要有作业调度。在在分时系统分时系统中为做到及时响应，作业被直接中为做到及时响应，作业被直接送入内存，故送入内存，故不需作业调度不需作业调度。在在实时系统实时系统中，通常也中，通常也不需作业调度不需作业调度。3.1.1 高级调度（高级调度（High Sche

6、duling）在每次执行作业调度时，都须作出两个决定：在每次执行作业调度时，都须作出两个决定：每次接纳多少作业进入内存，每次接纳多少作业进入内存，取决于取决于多道程序度多道程序度，即允许多少个作业同时在内，即允许多少个作业同时在内存中运行。存中运行。 多道程序度的确定应根据系统的规模和运行速度多道程序度的确定应根据系统的规模和运行速度等情况综合考虑。等情况综合考虑。应接纳哪些作业从外存调入内应接纳哪些作业从外存调入内存，取决于所采用的调度算法。存，取决于所采用的调度算法。 如先来先服务，短作业优先等，在如先来先服务，短作业优先等，在3.3中详细介绍。中详细介绍。3.1.2 低级调度（低级调度（

7、Low Level Scheduling）通常也称为通常也称为进程调度进程调度或或短程调度短程调度（Short-Term Scheduling），用来决定就绪队列中），用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程的哪个进程应获得处理机，然后再由分派程序把处理机分配给该进程。序把处理机分配给该进程。进程调度是最基本的一种调度，在三种进程调度是最基本的一种调度，在三种OS中中都有。都有。1、低级调度的功能、低级调度的功能v低级调度用于决定就绪队列中哪个进程应获低级调度用于决定就绪队列中哪个进程应获得处理机得处理机，然后再由分派程序执行把处理机，然后再由分派程序执行把处理机分配给该进程。

8、分配给该进程。v主要功能：主要功能：1、保存处理机的现场信息、保存处理机的现场信息2、按某种算法选取进程、按某种算法选取进程3、把处理机分配给进程、把处理机分配给进程2、进程调度中的三个基本机制、进程调度中的三个基本机制v排队器排队器：将系统中所有就绪进程按照一定方法排成：将系统中所有就绪进程按照一定方法排成一个或多个队列。一个或多个队列。v分派器分派器：把由进程调度程序所选定的进程，从就绪：把由进程调度程序所选定的进程，从就绪队列中取出，进行上下文切换，并将处理器分配给队列中取出，进行上下文切换，并将处理器分配给它。它。v上下文切换机制上下文切换机制：当对处理机进行切换时，会发生：当对处理机

9、进行切换时，会发生两对上下文切换操作。两对上下文切换操作。1、操作系统将保存当前进程的上下文，装入分派程、操作系统将保存当前进程的上下文，装入分派程序的上下文；序的上下文；2、将移出分派程序，把新选进程的、将移出分派程序，把新选进程的CPU现场信息装现场信息装入到处理机的各个相应寄存器中。入到处理机的各个相应寄存器中。3、进程调度方式、进程调度方式进程调度可采用下述两种调度方式：进程调度可采用下述两种调度方式：v非抢占方式非抢占方式（Non-preemptive Mode） 采用这种调度方式时，一旦把处理机分配给采用这种调度方式时，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进某进程

10、后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才把处理程完成或发生某事件而被阻塞时，才把处理机分配给其他进程，决不允许其它进程抢占机分配给其他进程，决不允许其它进程抢占已分配出去的处理机。已分配出去的处理机。 优点是优点是实现简单、系统开销小实现简单、系统开销小，适用于大多，适用于大多数的批处理数的批处理OS，但在要求比较严格的实时系，但在要求比较严格的实时系统中，不宜采用这种调度方式。统中，不宜采用这种调度方式。3、进程调度方式、进程调度方式v抢占方式抢占方式（Preemptive Mode） 这种调度方式允许调度程序根据某种原则，去暂这种调度方式允许调度程序根据某种原则，去

11、暂停某个正在执行的进程，将以分配给该进程的处停某个正在执行的进程，将以分配给该进程的处理机重新分配给另一进程。理机重新分配给另一进程。v抢占的原则有：抢占的原则有：v优先权原则。优先权原则。优先权高的可以抢占优先级低的进优先权高的可以抢占优先级低的进程的处理机。程的处理机。v短作业（进程）优先原则短作业（进程）优先原则。短作业（进程）可以。短作业（进程）可以抢占长作业（进程）的处理机。抢占长作业（进程）的处理机。1.时间片原则时间片原则。各进程按时间片运行，一个时间片。各进程按时间片运行，一个时间片用完时，停止该进程执行重新进行调度。用完时，停止该进程执行重新进行调度。3.1.3 中级调度（中

12、级调度（Intermediate-Level Scheduling）中级调度又称中级调度又称中程调度中程调度（Medium-Term Scheduling）引入中级调度的目的，是为了提高内）引入中级调度的目的，是为了提高内存利用率和系统吞吐量。存利用率和系统吞吐量。为此，应使那些暂时不能运行的进程不再占用宝贵为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调之外存去等待，把此时的的内存资源，而将它们调之外存去等待，把此时的进程状态称为进程状态称为就绪驻外存状态或挂起状态就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲当这些进程重又具备运行条件、且内存又稍有

13、空闲时，时，由中级调度来决定把外存上的哪些又具备运行由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存条件的就绪进程，重新调入内存，并修改其状态为，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。就绪状态，挂在就绪队列上等待进程调度。 高级、中级和低级调度高级、中级和低级调度 三种调度中，三种调度中，进程调度进程调度的运行频率最高，在的运行频率最高，在分时系统中通常是分时系统中通常是10100ms便进行一次进便进行一次进程调度，因而程调度，因而进程调度算法不能太复杂进程调度算法不能太复杂，以，以免占用太多的免占用太多的CPU时间。时间。作业调度作业调度是发生在一个作业运行

14、完毕，退出是发生在一个作业运行完毕，退出系统，而需要重新调度一个作业进入内存时，系统，而需要重新调度一个作业进入内存时，故故作业调度的周期较长作业调度的周期较长，大约几分钟一次。，大约几分钟一次。 中级调度中级调度的运行频率，基本上介于上述两种的运行频率，基本上介于上述两种调度之间。调度之间。3.2 调度队列模型和调度准则调度队列模型和调度准则 不论高级、中级或者低级调度，都涉及到进不论高级、中级或者低级调度，都涉及到进程队列，由此形成了三种类型的调度队列程队列，由此形成了三种类型的调度队列模型。模型。v仅有进程调度的调度队列模型仅有进程调度的调度队列模型v具有高级和低级调度的调度队列模型具有

15、高级和低级调度的调度队列模型1.同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型1、仅有进程调度的调度队列模型、仅有进程调度的调度队列模型在在分时系统分时系统中，通常仅设置进程调度，用中，通常仅设置进程调度，用户键入的命令和数据，都直接送入内存，户键入的命令和数据，都直接送入内存，对于命令，是由对于命令，是由OS为之创建一个进程。为之创建一个进程。系统可以系统可以把处于就绪状态的进程组织成栈、把处于就绪状态的进程组织成栈、树或一个无序链表树或一个无序链表，形式取决于，形式取决于OS类型和类型和所采用的调度算法。所采用的调度算法。在在分时系统中就绪进程组织成分时系统中就绪进程组织成F

16、IFO队列形队列形式，按时间片轮转方式运行式，按时间片轮转方式运行。每个进程在执行时可能出现下列三种情况：每个进程在执行时可能出现下列三种情况：仅有进程调度的调度队列模型仅有进程调度的调度队列模型v任务在给定的时间片内已经完成，该进程任务在给定的时间片内已经完成，该进程便在释放处理机后进入完成状态；便在释放处理机后进入完成状态；v任务在本次分得的时间片内尚未完成，任务在本次分得的时间片内尚未完成，OS便将该任务再放入就绪队列的末尾；便将该任务再放入就绪队列的末尾；v在执行期间，进程因为某事件而被阻塞后，在执行期间，进程因为某事件而被阻塞后，被被OS放入阻塞队列。放入阻塞队列。仅有进程调度的调度

17、队列模型仅有进程调度的调度队列模型下图示仅有进程调度的调度队列模型。下图示仅有进程调度的调度队列模型。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完等待事件等待事件进程完成进程完成交互用户交互用户事件出现事件出现2、具有高级和低级调度的调度队列、具有高级和低级调度的调度队列模型模型在批处理系统中，不仅需要在批处理系统中，不仅需要进程调度进程调度，而且，而且还需要还需要作业调度。作业调度。作业调度按一定的作业调度算法，从外存的作业调度按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程

18、们建立进程，送入就绪队列，然后才由进程调度算法按照一定的进程调度算法，选择一调度算法按照一定的进程调度算法，选择一个进程，把处理机分配给该进程。个进程，把处理机分配给该进程。下图示出具有高、低两级调度的调度队列模下图示出具有高、低两级调度的调度队列模型。型。具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型CPU就就 绪绪 队队 列列时间片完时间片完等待事件等待事件1进程完成进程完成后备队列后备队列等待事件等待事件2等待事件等待事件n事件事件1出现出现事件事件2出现出现事件事件n出现出现具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 具有高低两级调度的调度模型与

19、仅有进程具有高低两级调度的调度模型与仅有进程调度的调度模型的主要区别在于：调度的调度模型的主要区别在于：v就绪队列的形式就绪队列的形式。在批处理系统中，最常。在批处理系统中，最常用的是用的是，因此最，因此最常用的就绪队列形式是优先权队列。常用的就绪队列形式是优先权队列。1.设置多个阻塞队列设置多个阻塞队列。对于小型系统可只设。对于小型系统可只设置一个，但对于较大系统要置一个，但对于较大系统要以保证效率。以保证效率。3、同时具有三级调度的调度队列模型、同时具有三级调度的调度队列模型当在当在OS中引入中级调度后，可以把进程的就中引入中级调度后，可以把进程的就绪状态分为绪状态分为内存就绪内存就绪和和

20、外存就绪外存就绪。也可以把阻塞状态分为也可以把阻塞状态分为内存阻塞内存阻塞和和外存阻塞外存阻塞两种状态。两种状态。在调出操作的作用下，可使进程状态由内存在调出操作的作用下，可使进程状态由内存就绪转变为外存就绪，由内存阻塞转变为外就绪转变为外存就绪，由内存阻塞转变为外存阻塞；存阻塞；在中级调度的作用下，又可使外存就绪转变在中级调度的作用下，又可使外存就绪转变为内存就绪。为内存就绪。同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型CPUCPU就就 绪绪 队队 列列时间片完时间片完进程完进程完成成后备队列后备队列等待事件等待事件事件出现事件出现批量作业批量作业交互型作业交互型作业就绪、挂

21、起队列就绪、挂起队列事件出现事件出现阻阻 塞、挂塞、挂 起起 队队 列列挂起挂起阻阻 塞塞 队队 列列挂起挂起3.2.2 选择调度方式和调度算法的若干选择调度方式和调度算法的若干准则准则在一个在一个OS的设计中，应如何选择调度方式和的设计中，应如何选择调度方式和算法，很大程度上取决于算法，很大程度上取决于OS的类型和目标。的类型和目标。如在批处理系统、分时系统和实时系统中，如在批处理系统、分时系统和实时系统中，通常都采用不同的调度方式和算法。通常都采用不同的调度方式和算法。选择的准则，有的是选择的准则，有的是面向用户的面向用户的，有的是，有的是面面向系统的向系统的。1、面向用户的准则、面向用户

22、的准则(1)、周转时间短、周转时间短 周转时间周转时间指作业提交给系统开始，到作业完成指作业提交给系统开始，到作业完成为止的这段时间间隔。为止的这段时间间隔。包括：包括： 作业在外存后备队列上作业在外存后备队列上等待作业调度的时间等待作业调度的时间；进；进程在就绪队列上程在就绪队列上等待进程调度的时间等待进程调度的时间；进程在；进程在CPU上上执执行的时间行的时间；等待等待I/O操作完成的时间操作完成的时间。 平均周转时间平均周转时间： ，其中，其中Ti作业作业i 的的周转时间周转时间 11niiTnT1、面向用户的准则、面向用户的准则 带权周转时间带权周转时间：W=作业周转时间作业周转时间T

23、i / 系统为作业系统为作业提供的实际服务时间提供的实际服务时间Tsi ，通常通常W 1 平均带权周转时间平均带权周转时间： 用户一般希望自己作业的周转时间最短，用户一般希望自己作业的周转时间最短，11nisiiTTnT(2)、响应时间快、响应时间快 响应时间响应时间 是从用户通过键盘提交一个请求开始，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或说直到在屏直至系统首次产生响应为止的时间，或说直到在屏幕上显示出结果为止的一段时间间隔。幕上显示出结果为止的一段时间间隔。它包括：它包括： 从键盘输入的请求信息传送到处理机的时间；从键盘输入的请求信息传送到处理机的时间； 处理机

24、对请求信息进行处理的时间；处理机对请求信息进行处理的时间； 将所形成的响应回送到终端显示器的时间。将所形成的响应回送到终端显示器的时间。 ，是选，是选择分时系统中进程调度算法的重要准则之一择分时系统中进程调度算法的重要准则之一。(3)、截止时间的保证、截止时间的保证截止时间截止时间是指某任务必须开始执行或必须完成的是指某任务必须开始执行或必须完成的最迟时间。最迟时间。，因而，因而是选择实时调度算法的重要准则。是选择实时调度算法的重要准则。对于严格的对于严格的实时系统实时系统，其调度方式和调度算法必，其调度方式和调度算法必须保证这点。须保证这点。 (4)、优先权准则、优先权准则在任一种在任一种O

25、S调度算法中，都可引用优先权准则，调度算法中，都可引用优先权准则，以便紧急的作业得到及时的处理。以便紧急的作业得到及时的处理。在要求较严格的场合，还需选择抢占调度方式。在要求较严格的场合，还需选择抢占调度方式。2、面向系统的准则、面向系统的准则v系统吞吐量高系统吞吐量高 系统吞吐量指在单位时间内所完成的作业数。这系统吞吐量指在单位时间内所完成的作业数。这是是，是选择批处理，是选择批处理作业调度的重要准则。作业调度的重要准则。v 处理机利用率好处理机利用率好 & & 各类资源的平衡利用各类资源的平衡利用 大、中型多用户系统大、中型多用户系统中，既要求充分利用价格昂中，既要求充分利

26、用价格昂贵的处理机，又需要有效地利用其它各类资源，选贵的处理机，又需要有效地利用其它各类资源，选择适当的调度方式和算法对这两者起着十分重要的择适当的调度方式和算法对这两者起着十分重要的作用。作用。 对于微型机和某些实时系统，这两个准则并不重对于微型机和某些实时系统，这两个准则并不重要。要。 3.3 调度算法调度算法在在OS中调度的实质是一种资源分配，因而调度算法中调度的实质是一种资源分配，因而调度算法是指：是指：根据系统的资源分配策略所规定的资源分配根据系统的资源分配策略所规定的资源分配算法算法。对于不同的系统和系统目标，通常采用不同的调度对于不同的系统和系统目标，通常采用不同的调度算法。算法

27、。在在批处理系统批处理系统中为照顾为数众多的短作业，应采用中为照顾为数众多的短作业，应采用短作业优先的调度算法短作业优先的调度算法；在在分时系统分时系统中，为了保证系统具有合理的响应时间，中，为了保证系统具有合理的响应时间，应采用应采用轮转法进行调度轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但有些算法作业调度，有的算法适用于进程调度；但有些算法作业调度和进程调度都可以采用。调度和进程调度都可以采用。3.3.1 先来先服务调度算法先来先服务调度算法FCFS和短作业（进程）优先调度算法和短作业（进程）优先调

28、度算法 1、 FCFS是一种最简单的调度算法。是一种最简单的调度算法。用于作业调度用于作业调度：选择一个或多个最先进入后备作业队列的作：选择一个或多个最先进入后备作业队列的作业，调入内存，为之分配资源、创建进程，然后放入就绪队业，调入内存，为之分配资源、创建进程，然后放入就绪队列。列。用于进程调度用于进程调度：每次调度是选择一个最先进入就绪队列的进：每次调度是选择一个最先进入就绪队列的进程，把处理机分配给它，使之投入运行。该进程一直运行到程，把处理机分配给它，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。完成或发生某事件而阻塞后才放弃处理机。列列队队进程（或作业）进程（或

29、作业）先来先服务调度算法先来先服务调度算法vFCFS算法比较算法比较，而，而不利于短作业（进程）。不利于短作业（进程）。v下表列出了下表列出了A、B、C、D四个作业分别到达四个作业分别到达系统的时间、要求服务的时间、开始执行系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的时间及各自的完成时间，并计算出各自的的周转时间周转时间和和带权周转时间带权周转时间。先来先服务调度算法先来先服务调度算法进程进程名名到达到达时间时间服务服务时间时间开始开始执行执行时间时间完成完成时间时间周转周转时间时间带权带权周转周转时间时间A01B1100C21D31000111110110011

30、011021001001022021991.99先来先服务调度算法先来先服务调度算法进程进程名名到达到达时间时间服务服务时间时间开始开始执行执行时间时间完成完成时间时间周转周转时间时间带权带权周转周转时间时间A010111B110011011001C21101102100100D31001022021991.99先来先服务调度算法先来先服务调度算法v从上表可以看出，其中从上表可以看出，其中短作业短作业C的带权周转时间竟的带权周转时间竟高达高达100，这是不能容忍的，这是不能容忍的v而而长作业长作业D的带权周转时间仅为的带权周转时间仅为1.99。v据此可知，据此可知，FCFS调度算法有利于调度算

31、法有利于CPU繁忙型的作繁忙型的作业，而不利于业，而不利于I/O繁忙型的作业（进程）。繁忙型的作业（进程）。zCPU繁忙型作业：繁忙型作业：该类作业需要大量的该类作业需要大量的CPU时间进时间进行计算而很少请求行计算而很少请求I/O。如通常的科学计算。如通常的科学计算。zI/O繁忙型作业：繁忙型作业：指指CPU进行处理时，需频繁的请进行处理时，需频繁的请求求I/O。目前大多数事务处理都属于。目前大多数事务处理都属于I/O繁忙型作业。繁忙型作业。作业情况作业情况调度算法调度算法 进程名进程名ABCDE平均平均到达时间到达时间01234服务时间服务时间43524FCFS完成时间完成时间471214

32、18周转时间周转时间带权周转时间带权周转时间FCFS调度实例调度实例图中有五个进程图中有五个进程A、B、C、D和和E，它们到达时间分别是，它们到达时间分别是0、1、2、3和和4，所要求的服务时间分别是所要求的服务时间分别是4、3、5、2和和4，由图可看出，由图可看出，A、B、C、D和和E的完成时间分别是的完成时间分别是4、7、12、14和和18。从每个进程的从每个进程的，进而可以算出每个进程的进而可以算出每个进程的。A 0 4 7 12 14 18调调度度顺顺序序BCDE作业情况作业情况调度算法调度算法 进程名进程名ABCDE平均平均到达时间到达时间01234服务时间服务时间43524FCFS

33、完成时间完成时间47121418周转时间周转时间461011149带权周转时间带权周转时间1225.53.52.8A 0 4 7 12 14 18调调度度顺顺序序BCDE3.3.1 先来先服务和短作业（进程）优先来先服务和短作业（进程）优先调度算法先调度算法vSJ(P)F:是指对短作业或短进程优先调度的算法。是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。它们可以分别用于作业调度和进程调度。，是从后备队列中，是从后备队列中选择一个或若干个选择一个或若干个估计运行时间估计运行时间最短的作业，将最短的作业，将它们调入内存运行。它们调入内存运行。则是从就绪队列中则是从就绪队列

34、中选出一估计运行时间最短的进程，将处理机分配选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。某事件而被阻塞放弃处理机时，再重新调度。短作业（进程）优先调度算法短作业（进程）优先调度算法SJ(P)F FCFS与与SPF的的比比较较作业情况作业情况调度算法调度算法 进程名进程名ABCDE平均平均到达时间到达时间01234服务时间服务时间43524FCFS完成时间完成时间47121418周转时间周转时间461011149带权周转时间带权周转时间1225.53.52.8SJ(P)F完成

35、时间完成时间4918613周转时间周转时间带权周转时间带权周转时间0 4 6 9 13 18调调度度顺顺序序A D B E C 4188/31616/533/299/482.1短作业（进程）优先调度算法短作业（进程）优先调度算法SJ(P)F FCFS与与SPF的的比比较较作业情况作业情况调度算法调度算法 进程名进程名ABCDE平均平均到达时间到达时间01234服务时间服务时间43524FCFS完成时间完成时间47121418周转时间周转时间461011149带权周转时间带权周转时间1225.53.52.8SJ(P)F完成时间完成时间4918613周转时间周转时间4816398带权周转时间带权周

36、转时间12.67 3.11.52.252.10 4 6 9 13 18调调度度顺顺序序A D B E C 3.3.1 先来先服务和短作业（进程）优先来先服务和短作业（进程）优先调度算法先调度算法v 通过上表可以看出，采用通过上表可以看出，采用SJF算法后，不论算法后，不论是平均周转时间还是平均带权周转时间，都是平均周转时间还是平均带权周转时间，都有较明显的改善，尤其是对短作业有较明显的改善，尤其是对短作业D，其周，其周转时间由原来的转时间由原来的11降为降为3v带权周转时间从带权周转时间从5.5降到了降到了1.5。而平均带权周。而平均带权周转时间从转时间从2.8降到了降到了2.1。v这说明这说

37、明SJF调度算法能有效的降低作业的平调度算法能有效的降低作业的平均等待事件，提高系统吞吐量均等待事件，提高系统吞吐量。3.3.1 先来先服务和短作业（进程）优先来先服务和短作业（进程）优先调度算法先调度算法SJF调度算法的优缺点：调度算法的优缺点：v优点优点：有效降低作业的平均等待时间，提高系统：有效降低作业的平均等待时间，提高系统吞吐量。吞吐量。v缺点缺点： 1. 对长作业不利。对长作业不利。 2. 该算法完全未考虑作业的紧迫程度，因而不能该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会被及时处理。保证紧迫性作业（进程）会被及时处理。 3. 由于作业（进程）的长短含主观因素，

38、不一定由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。能真正做到短作业优先。课后思考题课后思考题v假如有四道作业，它们的进入时间和运行时间由下表给出，假如有四道作业，它们的进入时间和运行时间由下表给出，在单道程序环境下，分别填写在单道程序环境下，分别填写先来先服务先来先服务和和短作业优先短作业优先情况情况的完成时间、周转时间、带权周转时间以及平均周转时间和的完成时间、周转时间、带权周转时间以及平均周转时间和平均带权周转时间。平均带权周转时间。作业作业号号进入时间进入时间(时时)运行时间运行时间(小时小时)完成时间完成时间(时时)FCFSSJF周转时周转时间间(小时小时)带权周带权

39、周转时间转时间(小时小时)周转时周转时间间(小时小时)带权周带权周转时间转时间(小时小时)110:000.4210:101310:200.6410:300.2平均平均3.3.2 高优先权优先调度算法高优先权优先调度算法FPFv优先权调度算法的类型优先权调度算法的类型1、非抢占式优先权算法非抢占式优先权算法：系统一旦把处理机分配给：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程就一直执就绪队列中优先权最高的进程后，该进程就一直执行下去直至完成。主要用于批处理系统中或某些实行下去直至完成。主要用于批处理系统中或某些实时性要求不高的实时系统中。时性要求不高的实时系统中。2、抢占式优先权调

40、度算法抢占式优先权调度算法：进程执行中若出现另一：进程执行中若出现另一个优先权更高的进程，则系统将停止当前进程的执个优先权更高的进程，则系统将停止当前进程的执行，重新将处理机分配给新到的优先权更高的进程。行，重新将处理机分配给新到的优先权更高的进程。一般用于要求比较严格地实时系统中，以及对性能一般用于要求比较严格地实时系统中，以及对性能要求较高的批处理和分时系统中。要求较高的批处理和分时系统中。 优先权调度算法的关键在于采用优先权调度算法的关键在于采用，还是，还是，以及如何确定进程的优先权。，以及如何确定进程的优先权。优先权的类型优先权的类型 静态优先权是在创建进程时确定的，且规定它在进程的整

41、个静态优先权是在创建进程时确定的，且规定它在进程的整个运行期间保持不变。确定进程优先权的依据有：运行期间保持不变。确定进程优先权的依据有： 进程类型：进程类型：系统进程（如接收进程、对换进程、磁盘系统进程（如接收进程、对换进程、磁盘I/O进程）进程）的优先权高于一般用户进程。的优先权高于一般用户进程。 进程对资源的需求：进程对资源的需求：通常对估计执行时间短及内存需要量少的通常对估计执行时间短及内存需要量少的进程，赋予较高的优先权。进程，赋予较高的优先权。 根据用户要求：根据用户要求：由用户进程的紧迫程度及用户所付费用的多少由用户进程的紧迫程度及用户所付费用的多少来确定进程的优先权。来确定进程

42、的优先权。 特点：特点：简单易行、系统开销小，但不够精确简单易行、系统开销小，但不够精确。很可能出现。很可能出现优先权低的作业长期没有被调度的情况。适用在要求不太高的系优先权低的作业长期没有被调度的情况。适用在要求不太高的系统中。统中。 动态优先权动态优先权是指在创建进程时所赋予的优先权，可以随进是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。例如，规定在就程的推进而改变，以便获得更好的调度性能。例如，规定在就绪队列中的进程，随等待时间的增长，优先权以速率绪队列中的进程，随等待时间的增长，优先权以速率a增加。增加。 若所有进程具有相同的优先权初值，则最先进入就绪

43、队列的若所有进程具有相同的优先权初值，则最先进入就绪队列的进程将最先获得处理机，这便成为进程将最先获得处理机，这便成为FCFS算法。算法。 若所有就绪进程具有各不相同的优先权初值，若所有就绪进程具有各不相同的优先权初值，对优先权初值对优先权初值低的进程，在等待足够的时间后就可能因为优先权升为最高而低的进程，在等待足够的时间后就可能因为优先权升为最高而获得处理机执行获得处理机执行。 采用抢占式优先权调度算法时，如再规定正在执行的进程，采用抢占式优先权调度算法时，如再规定正在执行的进程，其优先权以速率其优先权以速率a下降，可防止一个长作业长期地垄断处理机。下降，可防止一个长作业长期地垄断处理机。

44、3.3.2 高优先权优先调度算法高优先权优先调度算法v确定进程优先权的依据有如下三个方面：确定进程优先权的依据有如下三个方面：v进程类型：一般来说进程类型：一般来说系统进程高于用户进系统进程高于用户进程程。v进程对资源的需求：如进程的估计时间及进程对资源的需求：如进程的估计时间及内存需要量的多少，对内存需要量的多少，对要求少的进程赋予要求少的进程赋予较高优先权较高优先权。1.用户要求：由用户要求：由用户进程的紧迫程度及用户用户进程的紧迫程度及用户所付费用的多少来确定优先权的所付费用的多少来确定优先权的。3.3.2 高优先权优先调度算法高优先权优先调度算法v高响应比优先调度算法高响应比优先调度算

45、法 在批处理系统中，短作业优先算法是一种比较好的在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足是长作业的运行得不到保证。算法，其主要不足是长作业的运行得不到保证。 我们为每个作业引入我们为每个作业引入动态优先权动态优先权，并使作业的优先，并使作业的优先级随着等待时间的增加而以速率级随着等待时间的增加而以速率a提高，则可解决提高，则可解决问题。见下式：问题。见下式： 由于等待时间与服务时间之和就是系统的响应时间，由于等待时间与服务时间之和就是系统的响应时间，故上式又表示为：故上式又表示为：由上式可以看出：由上式可以看出：v如如作业等待时间相同，则要求服务的时间作业等待时间相同，则要

46、求服务的时间愈短优先权愈高愈短优先权愈高，所以该算法利于短作业。，所以该算法利于短作业。v当要求当要求服务的时间相同，作业优先权的高服务的时间相同，作业优先权的高低决定于其等待时间的长短低决定于其等待时间的长短，所以是先来，所以是先来先服务。先服务。 1.对于长作业，对于长作业，作业的优先级可以随等待时作业的优先级可以随等待时间的增加而提高间的增加而提高，当其等待时间足够长也，当其等待时间足够长也可获得处理机。可获得处理机。既照顾了短作业，又考虑了作业到达的先后次既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。序，不会使长作业长期得不到服务。3.3.3 基于时间片的轮转

47、调度算法基于时间片的轮转调度算法在分时系统中，为保证能及时响应用户的请在分时系统中，为保证能及时响应用户的请求，必须求，必须采用基于时间片的轮转式进程调度采用基于时间片的轮转式进程调度算法算法。在早期，分时系统中采用的是简单的时间片在早期，分时系统中采用的是简单的时间片轮转法，进入轮转法，进入90年代后，广泛采用多级反馈年代后，广泛采用多级反馈队列调度算法。队列调度算法。下面分开介绍这两种方法并比较性能。下面分开介绍这两种方法并比较性能。时间片轮转法时间片轮转法系统将所有的就绪进程按先来先服务的原则系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把排成一个队列，每次调度时，把C

48、PU分配给分配给首进程，并令其首进程，并令其执行一个时间片执行一个时间片。时间片的大小从几时间片的大小从几ms到几百到几百ms。当执行的时间片用完时，停止该进程的执行当执行的时间片用完时，停止该进程的执行并将其送往就绪队列的末尾。并将其送往就绪队列的末尾。这样就可以保证就绪队列中这样就可以保证就绪队列中所有进程在一定所有进程在一定时间内均能获得一时间片的处理机执行时间时间内均能获得一时间片的处理机执行时间也就是说系统能在给定的时间内响应所有用也就是说系统能在给定的时间内响应所有用户的请求。户的请求。多级反馈队列调度算法多级反馈队列调度算法前面介绍的各种进程调度的算法都有一定的局限性。前面介绍的

49、各种进程调度的算法都有一定的局限性。这里介绍一种目前被公认为较好的进程调度算法这里介绍一种目前被公认为较好的进程调度算法多级反馈队列调度算法。多级反馈队列调度算法。实施过程如下：实施过程如下：（1）应设置多个队列并为各个队列赋予不同的优先应设置多个队列并为各个队列赋予不同的优先级级。第一个最高，依次降低。第一个最高，依次降低。 该算法赋予各个队列中进程执行时间片的大小也不该算法赋予各个队列中进程执行时间片的大小也不相同，优先权越高，时间片越短。相同，优先权越高，时间片越短。 如第一个队列时间片为如第一个队列时间片为Nms,第二个队列的时间片为第二个队列的时间片为2Nms,第三个队列的时间片为第

50、三个队列的时间片为3Nms多级反馈队列调度算法多级反馈队列调度算法（2）当一个新进程进入内存后，首先将它放入第一当一个新进程进入内存后，首先将它放入第一个队列的末尾，按个队列的末尾，按FCFS原则排队等待调度原则排队等待调度。 当轮到该进程执行时，如它能在该时间片内完成，当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；便可准备撤离系统； 如果它在一个时间片结束时尚未完成，调度程序便如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，在同样地按将该进程转入第二队列的末尾，在同样地按FCFS原则等待调度执行；原则等待调度执行； 如果它在第二队列中运行一个时间片后仍

51、未完成，如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，再依次将它放入第三队列，如此下去，当一个如此下去，当一个长作业（进程）从第一队列依次将到第长作业（进程）从第一队列依次将到第n队列后，队列后，在第在第n队列中便采取按时间片轮转的方式运行队列中便采取按时间片轮转的方式运行。多级反馈队列调度算法多级反馈队列调度算法（3）仅当第一队列空闲时，调度程序才调度第二队仅当第一队列空闲时，调度程序才调度第二队列中的进程运行，仅当第列中的进程运行，仅当第1（i-1）队列均空时，才）队列均空时，才会调度第会调度第i队列中的进程运行队列中的进程运行。 如果处理机正在第如果处理机正在第i队

52、列中为某进程服务时，又有新队列中为某进程服务时，又有新进程进入优先权较高的队列（第进程进入优先权较高的队列（第1（i-1）中的任何）中的任何一个队列），则此时一个队列），则此时新进程将抢占正在运行进程的新进程将抢占正在运行进程的处理机处理机，即由调度程序把正在运行的进程放回到第，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。队列的末尾，把处理机分配给新到的高优先权进程。S2就绪队列就绪队列2至至CPU就绪队列就绪队列3S3至至CPU就绪队列就绪队列1S1至至CPU就绪队列就绪队列nSn至至CPU（时间片：（时间片： S1S2 S3 Sn ）调度算法示意图调

53、度算法示意图多级反馈队列调度算法的性能多级反馈队列调度算法的性能 多级反馈队列调度算法具有较好的性能，能多级反馈队列调度算法具有较好的性能，能较好的满足各种类型用户的需要。较好的满足各种类型用户的需要。v终端型作业用户终端型作业用户。大多属于较小的交互性作。大多属于较小的交互性作业，只要能使作业在第一队列的时间片内完业，只要能使作业在第一队列的时间片内完成，便可令用户满意。成，便可令用户满意。v短批处理作业用户短批处理作业用户。周转时间仍然较短，至。周转时间仍然较短，至多在第二到三队列即可完成。多在第二到三队列即可完成。v长批处理作业用户长批处理作业用户。将依次在。将依次在1n级队列中级队列中

54、轮转执行，不必担心作业长期得不到处理。轮转执行，不必担心作业长期得不到处理。3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件 在多道程序系统中，虽可借助于多个进程的在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险系统的吞吐量，但可能发生一种危险死死锁。锁。 死锁（死锁（Deadlock）,是指多个进程在运行过是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，它们都将处于这种状态时，若无外力作用，它们都将无法再向前推

55、进。无法再向前推进。3.5.1 产生死锁的原因产生死锁的原因3.5.1 产生死锁的原因产生死锁的原因 产生死锁的原因产生死锁的原因 竞争资源（根本原因）竞争资源（根本原因）：因为系统资源的不足（有限因为系统资源的不足（有限资源），当系统中供多个进程所共享的资源，不足以同资源），当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起对资源的竞争而产生死锁。时满足它们的需要时，引起对资源的竞争而产生死锁。 进程推进顺序非法进程推进顺序非法：进程在运行过程中，请求和释放：进程在运行过程中，请求和释放资源的顺序不当导致死锁。资源的顺序不当导致死锁。 死锁的现象死锁的现象3.5.1 产生死锁的

56、原因产生死锁的原因 可剥夺和非剥夺性资源可剥夺和非剥夺性资源 系统有两类资源：系统有两类资源：可剥夺资源和非剥夺性资源可剥夺资源和非剥夺性资源。一类资源是可剥夺的一类资源是可剥夺的，如处理机（高优先权的进程剥，如处理机（高优先权的进程剥夺低优先权进程的处理机）和内存区（存储器管理程夺低优先权进程的处理机）和内存区（存储器管理程序可以把一个进程从一个存储区移至另一个存储区，序可以把一个进程从一个存储区移至另一个存储区，甚至调出到外存上）。甚至调出到外存上）。另一类资源是不可剥夺的另一类资源是不可剥夺的，当系统把这类资源分配给，当系统把这类资源分配给某进程后再不能强行收回，只能在进程用完后自动某进

57、程后再不能强行收回，只能在进程用完后自动释放，如磁带机、打印机等。释放，如磁带机、打印机等。 1 竞争资源引起死锁竞争资源引起死锁 竞争非剥夺性资源引起死锁竞争非剥夺性资源引起死锁 若系统中只有一台打印机若系统中只有一台打印机R1和一台磁带机和一台磁带机R2，可供进程，可供进程P1和和P2共享。共享。假定假定P1已占用了打印机已占用了打印机R1，P2占占用了磁带机用了磁带机R2。此时，若此时，若P2继续要求打印机，继续要求打印机，P2将阻塞；将阻塞；P1若又要求磁带机，若又要求磁带机，P1也将阻塞。也将阻塞。于是，于是，P1与与P2之间便形成了之间便形成了僵局僵局，两个进程都在等待对方释放出自

58、两个进程都在等待对方释放出自己所需的资源；但它们又都因不己所需的资源；但它们又都因不能获得所需的资源而不能继续推能获得所需的资源而不能继续推进，从而也不能释放出自己已占进，从而也不能释放出自己已占有的资源。有的资源。这时这时P1、P2和和R1、R2间已经形成间已经形成一个一个环路环路。以至进入死锁状态。以至进入死锁状态。竞争资源引起死锁竞争资源引起死锁 R1R2P1P2竞争临时性资源引起死锁竞争临时性资源引起死锁 临时性资源，这是指由一临时性资源，这是指由一个进程产生，被另一个进程使个进程产生，被另一个进程使用一短暂时间后便无用的资源，用一短暂时间后便无用的资源，故也称之为消耗资源，它同样故也

59、称之为消耗资源，它同样可能引起死锁。可能引起死锁。 进程进程P1、P2和和P3分别产生消分别产生消息息S1、S2和和S3，P1要求从要求从P3接收接收S3，P3需要从需要从P2接收接收S2，P2又需要接收又需要接收S1。如果按下述运行顺序，则可能如果按下述运行顺序，则可能发生死锁。发生死锁。 P1:.Request(S3);Release(S1);. P2:.Request(S1);Release(S2);. P3:.Request(S2);Release(S3);.竞争资源引起死锁竞争资源引起死锁 S2P3P2S1S3P1由于进程具有异步性，这就由于进程具有异步性，这就可能使进程按下述两种顺

60、序可能使进程按下述两种顺序向前推进。向前推进。 进程推进顺序合法：进程推进顺序合法：在在进程进程P1和和P2并发执行时，如并发执行时，如果按照右图中的曲线果按照右图中的曲线、所示的顺序推进，两进程所示的顺序推进，两进程均能顺利完成。均能顺利完成。 P1Rel(R2)P2Req(R1) Req(R2) Rel(R1)Req(R1)Req(R2)Rel(R1)Rel(R2)D进程推进顺序非法进程推进顺序非法：若并若并发进程发进程P1和和P2按曲线按曲线所示所示的顺序推进，它们将进入不的顺序推进，它们将进入不安全区安全区D内。此时内。此时P1保持了保持了资源资源R1，P2保持了资源保持了资源R2，系统处于不安全状态