《处理机调度与死锁讲课资料》由会员分享，可在线阅读，更多相关《处理机调度与死锁讲课资料（171页珍藏版）》请在金锄头文库上搜索。
1、第三章处理机调度与死锁,3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,处理机调度与死锁(Scheduling and Deadlock ),教学目的： 在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。为了改善系统资源的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多
2、道程序系统重要的研究课题。,教学要求：,熟悉处理机三级调度概念和处理机调度模型，掌握作业的状态和作业调度的功能。 掌握进程调度的方式和功能，熟悉调度方式和算法的选择准则，掌握各种调度算法及适合范围。 掌握死锁的定义和产生死锁的原因，掌握死锁的四个必要条件；熟悉预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理，熟悉解除死锁的方法。,3.1处理机调度的层次,3.1.1高级调度 1作业和作业步 (1) 作业(Job)。作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统
3、中，是以作业为基本单位从外存调入内存的。,(2) 作业步(Job Step)。通常，在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，我们把其中的每一个加工步骤称为一个作业步，各作业步之间存在着相互联系，往往是把上一个作业步的输出作为下一个作业步的输入。例如，一个典型的作业可分成三个作业步： “编译”作业步，通过执行编译程序对源程序进行编译，产生若干个目标程序段； “连结装配”作业步，将“编译”作业步所产生的若干个目标程序段装配成可执行的目标程序； “运行”作业步，将可执行的目标程序读入内存并控制其运行。 (3) 作业流。若干个作业进入系统后，被依次存放在
4、外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。,作业的状态: 作业从进入到运行结束，一般需要经历“提交”、“后备”、“运行”和“完成”四个阶段。 提交状态 一个作业被提交给机房后正在通过SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态。 后备状态 作业已经过SPOOLing系统输入到磁盘输入井，等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个作业控制块（JCB）。作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个后备作业队列。,运行状态 一个在后备作
5、业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程运行态、内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作业运行状态。 完成状态 当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序将负责善后处理。,作业状态的转换: 作业调度 作业调度程序按一定算法从后备作业队列中选一个满足资源要求的作业，分配它所要求的资源，建立一组相应的进程，设置该进程状态为就绪态，并将该进程插入内存就绪队列，参加CPU争夺。 终止作业 当进程正常运行结束或因发生错误终止时，调用终止作业程序，它负责将输出文件缓冲输
6、出到输出井，并调用SPOOLing系统输出进程将作业输出文件在打印机输出。同时回收作业所使用内、外存、I/O设备等各种资源，最后调用记帐程序结清作业费用。,2作业控制块JCB(Job Control Block) 为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在JCB中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源
7、需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。,每当作业进入系统时，系统便为每个作业建立一个JCB，根据作业类型将它插入相应的后备队列中。作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。在作业运行期间，系统就按照JCB中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。,3作业调度 作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们
8、创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。因此，有时也把作业调度称为接纳调度(Admission Scheduling)。,对用户而言，总希望自己作业的周转时间尽可能的少，最好周转时间就等于作业的执行时间。然而对系统来说，则希望作业的平均周转时间尽可能少，有利于提高CPU 的利用率和系统的吞吐量。为此，每个系统在选择作业调度算法时，既应考虑用户的要求，又能确保系统具有较高的效率。在每次执行作业调度时，都须做出以下两个决定。,1) 决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多道程序度(Degree of Multiprogramming)，即允许
9、多少个作业同时在内存中运行。当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低，因此，多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷。,2) 决定接纳哪些作业 应将哪些作业从外存调入内存，这将取决于所采用的调度算法。最简单的是先来先服务调度算法，这是指将最早进入外存的作业最先调入内存；较常用的一种算法是短作业优先调度算法，是将外存上最短的作业最先调入内存；另一种较常用的是基于作业优先级的调度算法，该算法是将外存上优先级最高的作业优先调入内存；比较好的一种算法是“响应比
10、高者优先”的调度算法。我们将在后面对上述几种算法作较为详细的介绍。,在批处理系统中，作业进入系统后，总是先驻留在外存的后备队列上，因此需要有作业调度的过程，以便将它们分批地装入内存。然而在分时系统中，为了做到及时响应，用户通过键盘输入的命令或数据等都是被直接送入内存的，因而无需再配置上述的作业调度机制，但也需要有某些限制性措施来限制进入系统的用户数。即，如果系统尚未饱和，将接纳所有授权用户，否则，将拒绝接纳。类似地，在实时系统中通常也不需要作业调度。,3.1.2 低级调度 通常也把低级调度(Low Level Scheduling)称为进程调度或短程调度(ShortTerm Schedulin
11、g)，它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。 1低级调度的功能 低级调度用于决定就绪队列中的哪个进程(或内核级线程，为叙述方便，以后只写进程)应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。,低级调度的主要功能如下： (1) 保存处理机的现场信息。在进程调度进行调度时，首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。 (2) 按某种算法选取进程。低级调度程序按某种算法如优先数算法、轮转法等，从就绪队列中选
12、取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。 (3) 把处理器分配给进程。由分派程序(Dispatcher)把处理器分配给进程。此时需为选中的进程恢复处理机现场，即把选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。,2进程调度中的三个基本机制 为了实现进程调度，应具有如下三个基本机制： (1) 排队器。为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列，以便调度程序能最快地找到它。 (2) 分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出
13、该进程，然后进行上下文切换，将处理机分配给它。,(3) 上下文切换机制。当对处理机进行切换时，会发生两对上下文切换操作。在第一对上下文切换时，操作系统将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行；在第二对上下文切换时，将移出分派程序，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。,应当指出，上下文切换将花去不少的处理机时间，即使是现代计算机，每一次上下文切换大约需要花费几毫秒的时间，该时间大约可执行上千条指令。为此，现在已有通过硬件(采用两组或多组寄存器)的方法来减少上下文切换的时间。一组寄存器供处理机在系统态时使用，另一组寄存器供应用程序使用。在这种条件下的
14、上下文切换只需改变指针，使其指向当前寄存器组即可。,3进程调度方式 进程调度可采用下述两种调度方式。 1) 非抢占方式(Nonpreemptive Mode) 在采用这种调度方式时，一旦把处理机分配给某进程后，不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。,在采用非抢占调度方式时，可能引起进程调度的因素可归结为如下几个： (1) 正在执行的进程执行完毕，或因发生某事件而不能再继续执行； (2) 执行中的进程因提出I/O请求
15、而暂停执行； (3) 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。 这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。,2) 抢占方式(Preemptive Mode) 这种调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占方式的优点是，可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求
16、的实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。抢占调度方式是基于一定原则的，主要有如下几条：,(1) 优先权原则。通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时，如果其优先权比正在执行进程的优先权高，便停止正在执行(当前)的进程，将处理机分配给优先权高的新到的进程，使之执行；或者说，允许优先权高的新到进程抢占当前进程的处理机。 (2) 短作业(进程)优先原则。当新到达的作业(进程)比正在执行的作业(进程)明显的短时，将暂停当前长作业(进程)的执行，将处理机分配给新到的短作业(进程)，使之优先执行； 或者说，短作业(进程)可以抢占当前较长作业(进程)的处理机。 (3) 时间片原则。各进程按时间片轮流运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数的实时系统，以及要求较高的批处理系统。,3.1.3 中级调度 中级调度(Intermediate Level Scheduling)又称中程调度(Medium-Term Scheduling)。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。为
