第三章 处理器调度与死锁

《第三章 处理器调度与死锁》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章　处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的层次3.1.1高级调度1．作业和作业步(1)作业(Job)程序、数据、作业说明书。在批处理系统中，是以作业为基本单位从外存调入内存的。(2)作业步(JobStep)。每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。(

2、3)作业流。若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。2．作业控制块JCB(JobControlBlock)JCB通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU繁忙型、I/O繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业

3、类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。在作业运行期间，系统就按照JCB中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。3．作业调度作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。有时也把作业调度称为接纳调度(AdmissionScheduling)。每个系统在选

4、择作业调度算法时，既应考虑用户的要求，又能确保系统具有较高的效率。每次作业调度必须做出如下决定：1)决定接纳多少个作业作业调度每次要接纳多少个作业进入内存，取决于多道程序度(DegreeofMultiprogramming)，即允许多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。2)决定接纳哪些作业应将哪些作业从外存调入内存，这将取决于所采用

5、的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比高者优先”的调度算法。在批处理系统中，作业进入系统后，总是先驻留在外存的后备队列上，因此需要有作业调度的过程，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都是被直接送入内存的，因而无需再配置上述的作业调度机制，但也需要有某些限制性措施来

6、限制进入系统的用户数。即，如果系统尚未饱和，将接纳所有授权用户，否则，将拒绝接纳。类似地，在实时系统中通常也不需要作业调度。3.1.2低级调度进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。1．低级调度的功能低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。低级调度的主要功能如下：(1)保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应

7、单元。(2)按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。(3)把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。2．进程调度中的三个基本机制为了实现进程调度，应具有如下三个基本机制：(1)排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式

8、排成一个或多个队列，以便调度程序能最快地找到它。(2)分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出，然后进行