处理机调度与死锁.ppt

《处理机调度与死锁.ppt》由会员分享，可在线阅读，更多相关《处理机调度与死锁.ppt（171页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章处理机调度与死锁 处理机调度与死锁 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第三章处理机调度与死锁 处理机处理机调度与调度与死锁死锁(Scheduling and Deadlock)教学目的：教学目的：在多道程序系统中，一个作业从提交到执行完在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏要影响系统的运成，要经历多级调度，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。为了改善系行性能，因此调度是多道系统的关键。为了改善

2、系统统资源资源的利用率和提高系统处理能力，多道程序系的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也可能发生死统中采用多个进程的并发执行，但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用预防锁的危险，研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多道程序系统重要的研究课题。防止死锁是多道程序系统重要的研究课题。第三章处理机调度与死锁 教学要求：教学要求：熟悉熟悉处理机三级调度处理机三级调度概念和概念和处理机调度模型处理机调度模型，掌，掌握作业的状态和作业握作业的状态和作业调度的

3、功能。调度的功能。掌握进程调度的方式和功能，掌握进程调度的方式和功能，熟悉熟悉调度方式和算调度方式和算法的选择准则，法的选择准则，掌握各种掌握各种调度算法及适合范围。调度算法及适合范围。掌握掌握死锁的定义和产生死锁的原因，死锁的定义和产生死锁的原因，掌握掌握死锁的死锁的四个必要条件；熟悉四个必要条件；熟悉预防死锁的方法，熟练掌握预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理，分配图的简化及其死锁定理，熟悉熟悉解除死锁的方解除死锁的方法。法。第三章处理机调度与死锁 3.1处理机调度的层次处理机调度的层次 3.1

4、.13.1.1高级调度高级调度1 1作业和作业步作业和作业步(1)(1)作业作业(Job)(Job)。作业是一个比程序更为广泛的。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。从外存调入内存的。第三章处理机调度与死锁(2)(2)作作业业步步(Job(Job Step)Step)。通通常常，在在作作业业运运行行期期间间，每每个

5、个作作业业都都必必须须经经过过若若干干个个相相对对独独立立，又又相相互互关关联联的的顺顺序序加加工工步步骤骤才才能能得得到到结结果果，我我们们把把其其中中的的每每一一个个加加工工步步骤骤称称为为一一个个作作业业步步，各各作作业业步步之之间间存存在在着着相相互互联联系系，往往往往是是把把上上一一个个作作业业步步的的输输出出作作为为下下一一个个作作业业步步的的输输入入。例例如如，一一个个典典型型的的作作业业可可分分成成三三个个作作业业步步：“编编译译”作作业业步步，通通过过执执行行编编译译程程序序对对源源程程序序进进行行编编译译，产产生生若若干干个个目目标标程程序序段段；“连连结结装装配配”作作业

6、业步步，将将“编编译译”作作业业步步所所产产生生的的若若干干个个目目标标程程序序段段装装配配成成可可执执行行的的目目标标程程序序；“运运行行”作作业业步步，将可执行的目标程序读入内存并控制其运行。将可执行的目标程序读入内存并控制其运行。(3)(3)作业流。若干个作业进入系统后，被依次存作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作的控制下，逐个作业进行处理，于是便形成了处理作业流。业流。第三章处理机调度与死锁 作业调度作业调度 作业运行状态作业运行状态 外存外存 外

7、存外存(盘盘)交换区交换区作作业业后后备备状态状态作作业业提提交交状态状态作作业业完完成状态成状态终止终止作业作业就就 绪绪态态阻阻 塞塞态态主存主存 进程调度进程调度运运 行行态态就绪态就绪态阻阻 塞塞态态调出调出调进调进第三章处理机调度与死锁 作业的状态作业的状态:作业从进入到运行结束，一般需要经历作业从进入到运行结束，一般需要经历“提交提交”、“后备后备”、“运行运行”和和“完成完成”四个阶段。四个阶段。提交状态提交状态 一个作业被提交给机房后正在通过一个作业被提交给机房后正在通过SPOOLingSPOOLing系统进行输入或用户通过终端向计算机中键系统进行输入或用户通过终端向计算机中键

8、入其作业时所处于的状态为提交状态。入其作业时所处于的状态为提交状态。后备状态后备状态 作业已经过作业已经过SPOOLingSPOOLing系统输入到磁盘输系统输入到磁盘输入井，等待调入内存运行，此时作业处于后备状态。入井，等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个作业控制为了管理和调度作业，为每个作业设置一个作业控制块（块（JCBJCB）。作业控制块记录了作业类型和资源要求）。作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个等有关信息。作业控制块按作业类型组成一个或多个后备作业队列。后备作业队列。第三章处理机调度与死锁 运行状

9、态运行状态 一个在后备作业队列的作业被作业调度程序选一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态调入内存，该作业就进入运行状态。进程各状态（进程运行态、内存进程就绪态、内存阻塞态、外（进程运行态、内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作业运存进程就绪态、外存进程阻塞态等）都对应作业运行状态。行状态。完成状态完成状态 当进程正常运行结束或因发生错误而终止时，当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序将负责善后处理。

10、作业进入完成状态。终止作业程序将负责善后处理。第三章处理机调度与死锁 第三章处理机调度与死锁 作业状态的转换作业状态的转换:作业调度作业调度 作业调度程序按一定算法从后备作业队列中选一作业调度程序按一定算法从后备作业队列中选一个满足资源要求的作业，分配它所要求的资源，建立个满足资源要求的作业，分配它所要求的资源，建立一组相应的进程，设置该进程状态为就绪态，并将该一组相应的进程，设置该进程状态为就绪态，并将该进程插入内存就绪队列，参加进程插入内存就绪队列，参加CPUCPU争夺。争夺。终止作业终止作业 当进程正常运行结束或因发生错误终止时，调用当进程正常运行结束或因发生错误终止时，调用终止作业程序

11、，它负责将输出文件缓冲输出到输出井，终止作业程序，它负责将输出文件缓冲输出到输出井，并调用并调用SPOOLingSPOOLing系统输出进程将作业输出文件在打印系统输出进程将作业输出文件在打印机输出。同时回收作业所使用内、外存、机输出。同时回收作业所使用内、外存、I/OI/O设备等设备等各种资源，最后调用记帐程序结清作业费用。各种资源，最后调用记帐程序结清作业费用。第三章处理机调度与死锁 2 2作业控制块作业控制块JCB(Job Control Block)JCB(Job Control Block)为了管理和调度作业，在多道批处理系统中为每为了管理和调度作业，在多道批处理系统中为每个作业设置

12、了一个作业控制块，如同进程控制块是进个作业设置了一个作业控制块，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在的全部信息。在JCB中所包含的内容因系统而异，通中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、常应包含的内容有：作业标识、用户名称、用户帐户、作业类型作业类型(CPU 繁忙型、繁忙型、I/O 繁忙型、批量型、终端型繁忙型、批量型、终端型)、作业状态、调度信息、作业状态、调度信息(优先级、作

13、业已运行时间优先级、作业已运行时间)、资源需求资源需求(预计运行时间、要求内存大小、要求预计运行时间、要求内存大小、要求I/O设设备的类型和数量等备的类型和数量等)、进入系统时间、开始处理时间、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。作业完成时间、作业退出时间、资源使用情况等。第三章处理机调度与死锁 每当作业进入系统时，系统便为每个作业建立每当作业进入系统时，系统便为每个作业建立一个一个JCB，根据作业类型将它插入相应的后备队列，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，中。作业调度程序依据一定的调度算法来调度它们，被调度到

14、的作业将会装入内存。在作业运行期间，被调度到的作业将会装入内存。在作业运行期间，系统就按照系统就按照JCB中的信息对作业进行控制。当一个中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。给它的资源，撤消它的作业控制块。第三章处理机调度与死锁 3 3作业调度作业调度作业调度的主要功能是根据作业控制块中的信作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作按照一定的算法，从外存的

15、后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度因此，有时也把作业调度称为接纳调度(Admission Scheduling)。第三章处理机调度与死锁 对用户而言，总希望自己作业的周转时间尽可能对用户而言，总希望自己作业的周转时间尽可能的少，最好周转时间就等于作业的执行时间。然而对的少，最好周转时间就等于作业的执行时间。然而对系统来说，则希望作业的平均周转时间尽可能少，有系统来说，则希望作业的平均周转时间尽可能

16、少，有利于提高利于提高CPU 的利用率和系统的吞吐量。为此，每的利用率和系统的吞吐量。为此，每个系统在选择作业调度算法时，既应考虑用户的要求，个系统在选择作业调度算法时，既应考虑用户的要求，又能确保系统具有较高的效率。在每次执行作业调度又能确保系统具有较高的效率。在每次执行作业调度时，都须做出以下两个决定。时，都须做出以下两个决定。第三章处理机调度与死锁 1)1)决定接纳多少个作业决定接纳多少个作业作业调度每次要接纳多少个作业进入内存，取作业调度每次要接纳多少个作业进入内存，取决于多道程序度决于多道程序度(Degree of Multiprogramming)，即，即允许多少个作业同时在内存中

17、运行。当内存中同时允许多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存中同质量，比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，因此，多道程序度的确定用率和系统吞吐量太低，因此，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。应根据系统的规模和运行速度等情况做适当的折衷。第三章处理机调度与死锁 2)2)决定接纳哪些作业决定接纳哪些作业应将哪些作业从外存调入内存，这

18、将取决于所应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是最高的作业优先调入内存；比较好的一种算法是“响应比高者优先响应比

19、高者优先”的调度算法。我们将在后面对上的调度算法。我们将在后面对上述几种算法作较为详细的介绍。述几种算法作较为详细的介绍。第三章处理机调度与死锁 在批处理系统中，作业进入系统后，总是先驻在批处理系统中，作业进入系统后，总是先驻留在外存的后备队列上，因此需要有作业调度的过留在外存的后备队列上，因此需要有作业调度的过程，以便将它们分批地装入内存。然而在分时系统程，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令中，为了做到及时响应，用户通过键盘输入的命令或数据等都是被直接送入内存的，因而无需再配置或数据等都是被直接送入内存的，因而无需再配置上述的作业调度机制，但

20、也需要有某些限制性措施上述的作业调度机制，但也需要有某些限制性措施来限制进入系统的用户数。即，如果系统尚未饱和，来限制进入系统的用户数。即，如果系统尚未饱和，将接纳所有授权用户，否则，将拒绝接纳。类似地，将接纳所有授权用户，否则，将拒绝接纳。类似地，在实时系统中通常也不需要作业调度。在实时系统中通常也不需要作业调度。第三章处理机调度与死锁 3.1.2 3.1.2 低级调度低级调度通通常常也也把把低低级级调调度度(Low(Low Level Level Scheduling)Scheduling)称称为为进进程程调调度度或或短短程程调调度度(ShortTerm(ShortTerm Schedul

21、ing)Scheduling)，它它所所调调度度的的对对象象是是进进程程(或或内内核核级级线线程程)。进进程程调调度度是是最最基基本本的的一一种种调调度度，在在多多道道批批处处理理、分分时时和和实实时时三三种种类类型型的的OSOS中，都必须配置这级调度。中，都必须配置这级调度。1 1低级调度的功能低级调度的功能低低级级调调度度用用于于决决定定就就绪绪队队列列中中的的哪哪个个进进程程(或或内内核核级级线线程程，为为叙叙述述方方便便，以以后后只只写写进进程程)应应获获得得处处理理机机，然然后后再再由由分分派派程程序序执执行行把把处处理理机机分分配配给给该该进进程程的的具体操作。具体操作。第三章处理

22、机调度与死锁 低级调度的主要功能如下：低级调度的主要功能如下：(1)(1)保保存存处处理理机机的的现现场场信信息息。在在进进程程调调度度进进行行调调度度时时，首首先先需需要要保保存存当当前前进进程程的的处处理理机机的的现现场场信信息息，如如程程序序计计数数器器、多多个个通通用用寄寄存存器器中中的的内内容容等等，将将它它们们送入该进程的进程控制块送入该进程的进程控制块(PCB)(PCB)中的相应单元。中的相应单元。(2)(2)按某种算法选取进程。低级调度程序按某种按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一算法如优先数算法、轮转法等，从就绪队列中选取一个进

23、程，把它的状态改为运行状态，并准备把处理机个进程，把它的状态改为运行状态，并准备把处理机分配给它。分配给它。(3)(3)把处理器分配给进程。由分派程序把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。点处开始继续运行。第三章处理机调度

24、与死锁 2 2进程调度中的三个基本机制进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：为了实现进程调度，应具有如下三个基本机制：(1)(1)排排队队器器。为为了了提提高高进进程程调调度度的的效效率率，应应事事先先将将系系统统中中所所有有的的就就绪绪进进程程按按照照一一定定的的方方式式排排成成一一个或多个队列，以便调度程序能最快地找到它。个或多个队列，以便调度程序能最快地找到它。(2)(2)分派器分派器(分派程序分派程序)。分派器把由进程调度。分派器把由进程调度程序所选定的进程，从就绪队列中取出该进程，然程序所选定的进程，从就绪队列中取出该进程，然后进行上下文切换，将处理机分配

25、给它。后进行上下文切换，将处理机分配给它。第三章处理机调度与死锁(3)(3)上下文切换机制。当对处理机进行切换时，上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。在第一对上下文切换会发生两对上下文切换操作。在第一对上下文切换时，操作系统将保存当前进程的上下文，而装入分时，操作系统将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行；在第二对上派程序的上下文，以便分派程序运行；在第二对上下文切换时，将移出分派程序，而把新选进程的下文切换时，将移出分派程序，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。现场信息装入到处理机的各个相应寄存器中。第三章处理机调

26、度与死锁 应当指出，上下文切换将花去不少的处理机时应当指出，上下文切换将花去不少的处理机时间，即使是现代计算机，每一次上下文切换大约需间，即使是现代计算机，每一次上下文切换大约需要花费几毫秒的时间，该时间大约可执行上千条指要花费几毫秒的时间，该时间大约可执行上千条指令。为此，现在已有通过硬件令。为此，现在已有通过硬件(采用两组或多组寄存采用两组或多组寄存器器)的方法来减少上下文切换的时间。一组寄存器供的方法来减少上下文切换的时间。一组寄存器供处理机在系统态时使用，另一组寄存器供应用程序处理机在系统态时使用，另一组寄存器供应用程序使用。在这种条件下的上下文切换只需改变指针，使用。在这种条件下的上

27、下文切换只需改变指针，使其指向当前寄存器组即可。使其指向当前寄存器组即可。第三章处理机调度与死锁 3 3进程调度方式进程调度方式进程调度可采用下述两种调度方式。进程调度可采用下述两种调度方式。1)1)非抢占方式非抢占方式(Nonpreemptive Mode)(Nonpreemptive Mode)在采用这种调度方式时，一旦把处理机分配给在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运某进程后，不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配

28、行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。直至该进程完成，自愿释放处理机，给它的处理机。直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其或发生某事件而被阻塞时，才再把处理机分配给其他进程。他进程。第三章处理机调度与死锁 在在采采用用非非抢抢占占调调度度方方式式时时，可可能能引引起起进进程程调调度度的的因素可归结为如下几个：因素可归结为如下几个：(1)(1)正正在在执执行行的的进进程程执执行行完完毕毕，或或因因发发生生某某事事件件而不能再继续执行；而不能再继续执行；(2)(2)执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执

29、行；(3)(3)在在进进程程通通信信或或同同步步过过程程中中执执行行了了某某种种原原语语操操作，如作，如P P操作操作(wait(wait操作操作)、BlockBlock原语、原语、WakeupWakeup原语等。原语等。这种调度方式的优点是实现简单，系统开销小，这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急适用于大多数的批处理系统环境。但它难以满足紧急任务的要求任务的要求立即执行，因而可能造成难以预料的立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。用这种调度

30、方式。第三章处理机调度与死锁 2)2)抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)这种调度方式允许调度程序根据某种原则去暂这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占方式的优点是，可以机重新分配给另一进程。抢占方式的优点是，可以防止一个长进程长时间占用处理机，能为大多数进防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。但抢占方式比非着

31、较严格要求的实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。抢占调度方式抢占方式调度所需付出的开销较大。抢占调度方式是基于一定原则的，主要有如下几条：是基于一定原则的，主要有如下几条：第三章处理机调度与死锁(1)(1)优优先先权权原原则则。通通常常是是对对一一些些重重要要的的和和紧紧急急的的作作业业赋赋予予较较高高的的优优先先权权。当当这这种种作作业业到到达达时时，如如果果其其优优先先权权比比正正在在执执行行进进程程的的优优先先权权高高，便便停停止止正正在在执执行行(当当前前)的的进进程程，将将处处理理机机分分配配给给优优先先权权高高的的新新到到的的进进程程，使使之之执执行行；或

32、或者者说说，允允许许优优先先权权高高的的新新到到进进程程抢抢占当前进程的处理机。占当前进程的处理机。(2)(2)短作业短作业(进程进程)优先原则。当新到达的作业优先原则。当新到达的作业(进程进程)比正在执行的作业比正在执行的作业(进程进程)明显的短时，将暂停明显的短时，将暂停当前长作业当前长作业(进程进程)的执行，将处理机分配给新到的短的执行，将处理机分配给新到的短作业作业(进程进程)，使之优先执行；，使之优先执行；或者说，短作业或者说，短作业(进程进程)可以抢占当前较长作业可以抢占当前较长作业(进程进程)的处理机。的处理机。(3)(3)时间片原则。各进程按时间片轮流运行，当时间片原则。各进程

33、按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处理系统。以及要求较高的批处理系统。第三章处理机调度与死锁 3.1.3 3.1.3 中级调度中级调度中级调度中级调度(Intermediate Level Scheduling)又称又称中程调度中程调度(Medium-Term Scheduling)。引入中级调度。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。的主要目的是为了提高内存利用率和系统吞吐量。为此，应使

34、那些暂时不能运行的进程不再占用宝贵为此，应使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件且内存又稍有空闲时，由些进程重又具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的中级调度来决定把外存上的那些又具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就挂在就绪队列上等待进程调度。中级调

35、度实际上就是存储器管理中的对换功能，我们将在第四章中做是存储器管理中的对换功能，我们将在第四章中做详细阐述。详细阐述。第三章处理机调度与死锁 在上述三种调度中，进程调度的运行频率最高，在上述三种调度中，进程调度的运行频率最高，在分时系统中通常是在分时系统中通常是10100 ms便进行一次进程调便进行一次进程调度，因此把它称为短程调度。为避免进程调度占用度，因此把它称为短程调度。为避免进程调度占用太多的太多的CPU时间，进程调度算法不宜太复杂。作业时间，进程调度算法不宜太复杂。作业调度往往是发生在一个调度往往是发生在一个(批批)作业运行完毕，退出系作业运行完毕，退出系统，而需要重新调入一个统，而

36、需要重新调入一个(批批)作业进入内存时，故作业进入内存时，故作业调度的周期较长，大约几分钟一次，因此把它作业调度的周期较长，大约几分钟一次，因此把它称为长程调度。由于其运行频率较低，故允许作业称为长程调度。由于其运行频率较低，故允许作业调度算法花费较多的时间。中级调度的运行频率基调度算法花费较多的时间。中级调度的运行频率基本上介于上述两种调度之间，因此把它称为中程调本上介于上述两种调度之间，因此把它称为中程调度。度。第三章处理机调度与死锁 3.2 调度队列模型和调度准则调度队列模型和调度准则 3.2.13.2.1调度队列模型调度队列模型1 1仅有进程调度的调度队列模型仅有进程调度的调度队列模型

37、在分时系统中，通常仅设置了进程调度，用户键在分时系统中，通常仅设置了进程调度，用户键入的命令和数据都直接送入内存。对于命令，是由入的命令和数据都直接送入内存。对于命令，是由OS为之建立一个进程。系统可以把处于就绪状态的进程为之建立一个进程。系统可以把处于就绪状态的进程组织成栈、树或一个无序链表，至于到底采用其中哪组织成栈、树或一个无序链表，至于到底采用其中哪种形式，则与种形式，则与OS类型和所采用的调度算法有关。例如，类型和所采用的调度算法有关。例如，在分时系统中，常把就绪进程组织成在分时系统中，常把就绪进程组织成FIFO队列形式。队列形式。每当每当OS创建一个新进程时，便将它挂在就绪队列的末

38、创建一个新进程时，便将它挂在就绪队列的末尾，然后按时间片轮转方式运行。尾，然后按时间片轮转方式运行。第三章处理机调度与死锁 每个进程在执行时都可能出现以下三种情况：每个进程在执行时都可能出现以下三种情况：(1)(1)任任务务在在给给定定的的时时间间片片内内已已经经完完成成，该该进进程程便便在释放处理机后进入完成状态；在释放处理机后进入完成状态；(2)(2)任任务务在在本本次次分分得得的的时时间间片片内内尚尚未未完完成成，OSOS便便将该任务再放入就绪队列的末尾；将该任务再放入就绪队列的末尾；(3)(3)在在执执行行期期间间，进进程程因因为为某某事事件件而而被被阻阻塞塞后后，被被OSOS放入阻塞

39、队列。放入阻塞队列。图图3-1示出了仅具有进程调度的调度队列模型。示出了仅具有进程调度的调度队列模型。第三章处理机调度与死锁 图图 3-1仅具有进程调度的调度队列模型仅具有进程调度的调度队列模型 第三章处理机调度与死锁 2 2具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型在批处理系统中，不仅需要进程调度，而且还在批处理系统中，不仅需要进程调度，而且还需有作业调度，由后者按一定的作业调度算法，从需有作业调度，由后者按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按们建立进程

40、，送入就绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分照一定的进程调度算法选择一个进程，把处理机分配给该进程。图配给该进程。图3-2示出了具有高、低两级调度的调示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如度队列模型。该模型与上一模型的主要区别在于如下两个方面。下两个方面。第三章处理机调度与死锁(1)(1)就绪队列的形式。在批处理系统中，最常用就绪队列的形式。在批处理系统中，最常用的是最高优先权优先调度算法，相应地，最常用的的是最高优先权优先调度算法，相应地，最常用的就绪队列形式是优先权队列。进程在进入优先级队就绪队列形式是优先权队列。进程在进

41、入优先级队列时，根据其优先权的高低，被插入具有相应优先列时，根据其优先权的高低，被插入具有相应优先权的位置上，这样，调度程序总是把处理机分配给权的位置上，这样，调度程序总是把处理机分配给就绪队列中的队首进程。在最高优先权优先的调度就绪队列中的队首进程。在最高优先权优先的调度算法中，也可采用无序链表方式，即每次把新到的算法中，也可采用无序链表方式，即每次把新到的进程挂在链尾，而调度程序每次调度时，是依次比进程挂在链尾，而调度程序每次调度时，是依次比较该链中各进程的优先权，从中找出优先权最高的较该链中各进程的优先权，从中找出优先权最高的进程，将之从链中摘下，并把处理机分配给它。显进程，将之从链中摘

42、下，并把处理机分配给它。显然，无序链表方式与优先权队列相比，这种方式的然，无序链表方式与优先权队列相比，这种方式的调度效率较低。调度效率较低。第三章处理机调度与死锁 图图 3-2具有高、低两级调度的调度队列模型具有高、低两级调度的调度队列模型 第三章处理机调度与死锁(2)(2)设置多个阻塞队列。对于小型系统，可以只设置多个阻塞队列。对于小型系统，可以只设置一个阻塞队列；但当系统较大时，若仍只有一设置一个阻塞队列；但当系统较大时，若仍只有一个阻塞队列，其长度必然会很长，队列中的进程数个阻塞队列，其长度必然会很长，队列中的进程数可以达到数百个，这将严重影响对阻塞队列操作的可以达到数百个，这将严重影

43、响对阻塞队列操作的效率。故在大、中型系统中通常都设置了若干个阻效率。故在大、中型系统中通常都设置了若干个阻塞队列，每个队列对应于某一种进程阻塞事件。塞队列，每个队列对应于某一种进程阻塞事件。第三章处理机调度与死锁 3 3同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型当在当在OS中引入中级调度后，人们可把进程的就中引入中级调度后，人们可把进程的就绪状态分为内存就绪绪状态分为内存就绪(表示进程在内存中就绪表示进程在内存中就绪)和外存和外存就绪就绪(进程在外存中就绪进程在外存中就绪)。类似地，也可把阻塞状态。类似地，也可把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操进一步分成

44、内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由内存就绪转为外存就绪，作的作用下，可使进程状态由内存就绪转为外存就绪，由内存阻塞转为外存阻塞；在中级调度的作用下，又由内存阻塞转为外存阻塞；在中级调度的作用下，又可使外存就绪转为内存就绪。图可使外存就绪转为内存就绪。图3-3示出了具有三级示出了具有三级调度的调度队列模型。调度的调度队列模型。第三章处理机调度与死锁 图图 3-3具有三级调度时的调度队列模型具有三级调度时的调度队列模型 第三章处理机调度与死锁 3.2.23.2.2选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则1 1面向用户的准则面向用户的准则 (1)(

45、1)周周转转时时间间短短。通通常常把把周周转转时时间间的的长长短短作作为为评评价价批批处处理理系系统统的的性性能能、选选择择作作业业调调度度方方式式与与算算法法的的重重要要准准则则之之一一。所所谓谓周周转转时时间间，是是指指从从作作业业被被提提交交给给系系统统开开始始，到到作作业业完完成成为为止止的的这这段段时时间间间间隔隔(称称为为作作业业周周转转时时间间)。它它包包括括四四部部分分时时间间：作作业业在在外外存存后后备备队队列列上上等等待待(作作业业)调调度度的的时时间间，进进程程在在就就绪绪队队列列上上等等待待进进程程调调度度的的时时间间，进进程程在在CPU上上执执行行的的时时间间，以以及

46、及进进程程等等待待I/O操操作作完完成成的的时时间间。其其中中的的后后三三项项在在一一个个作作业的整个处理过程中可能会发生多次。业的整个处理过程中可能会发生多次。第三章处理机调度与死锁 对每个用户而言，都希望自己作业的周转时间最对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望能使平短。但作为计算机系统的管理者，则总是希望能使平均周转时间最短，这不仅会有效地提高系统资源的利均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满意。可把平均用率，而且还可使大多数用户都感到满意。可把平均周转时间描述为：周转时间描述为：第三章处理机调度与死锁

47、 作业的周转时间作业的周转时间T与系统为它提供服务的时间与系统为它提供服务的时间Ts之比，即之比，即W=T/Ts，称为带权周转时间，而平均带，称为带权周转时间，而平均带权周转时间则可表示为：权周转时间则可表示为：第三章处理机调度与死锁(2)(2)响应时间快。常把响应时间的长短用来评响应时间快。常把响应时间的长短用来评价分时系统的性能，这是选择分时系统中进程调度价分时系统的性能，这是选择分时系统中进程调度算法的重要准则之一。所谓响应时间，是从用户通算法的重要准则之一。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说

48、，直到屏幕上显示出结果为止为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。它包括三部分时间：从键盘输入的一段时间间隔。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。到终端显示器的时间。第三章处理机调度与死锁(3)(3)截截止止时时间间的的保保证证。这这是是评评价价实实时时系系统统性性能能的的重重要要指指标标，因因而而是是选选择择实实时时调调度度算算法法的的重重要要准准则则。所所谓谓截截止止时时间间，是是指指

49、某某任任务务必必须须开开始始执执行行的的最最迟迟时时间间，或或必必须须完完成成的的最最迟迟时时间间。对对于于严严格格的的实实时时系系统统，其其调调度度方方式式和和调调度度算算法法必必须须能能保保证证这这一一点点，否否则则将将可能造成难以预料的后果。可能造成难以预料的后果。(4)(4)优先权准则。在批处理、分时和实时系统优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求较严格的某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢占式调度方式，才能保证紧场合，往往还须选择抢占式

50、调度方式，才能保证紧急作业得到及时处理。急作业得到及时处理。第三章处理机调度与死锁 2 2面向系统的准则面向系统的准则这这是是为为了了满满足足系系统统要要求求而而应应遵遵循循的的一一些些准准则则。其中，较重要的有以下几点：其中，较重要的有以下几点：(1)(1)系统吞吐量高。这是用于评价批处理系统系统吞吐量高。这是用于评价批处理系统性能的另一个重要指标，因而是选择批处理作业调性能的另一个重要指标，因而是选择批处理作业调度的重要准则。由于吞吐量是指在单位时间内系统度的重要准则。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度所完成的作业数，因而它与批处理作业的平均长度具有