《《处理机调度与死锁》PPT课件》由会员分享，可在线阅读，更多相关《《处理机调度与死锁》PPT课件（145页珍藏版）》请在金锄头文库上搜索。
1、第三章处理机调度与死锁 第三章处理机调度与死锁 3.1 处理机调度的层次处理机调度的层次3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 调度算法调度算法3.4 实时调度实时调度 3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.6 预防死锁的方法预防死锁的方法3.7 死锁的检测与解除死锁的检测与解除 第三章处理机调度与死锁 处理机调度的层次处理机调度的层次 高级、中级和低级调度高级、中级和低级调度高级调度（高级调度（High Level Scheduling)High Level Scheduling)作业调度或长程调度（作业调度或长程调度（LongTerm Schedu
2、lingLongTerm Scheduling）1 1作业和作业步作业和作业步(1) 作业作业(Job)。作业不仅包含了通常的程序和数据程序和数据，而且还应配有一份作业说明书作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。在批处理系统中，是以作业为基本单位从外存调入内存的。 第三章处理机调度与死锁 (2) (2) 作作业业步步(Job (Job Step)Step)。作作业业的的每每一一个个顺顺序序加加工工步步骤骤称称为为一一个个作作业业步步，各各作作业业步步之之间间存存在在着着相相互互联联系系，往往往往是是把把上上一个作业步的输出作为下
3、一个作业步的输入。一个作业步的输出作为下一个作业步的输入。例例如如，一一个个典典型型的的作作业业可可分分成成三三个个作作业业步步： “编编译译”作作业业步步，通通过过执执行行编编译译程程序序对对源源程程序序进进行行编编译译，产产生生若若干干个个目目标标程程序序段段； “连连结结装装配配”作作业业步步，将将“编编译译”作作业业步步所所产产生生的的若若干干个个目目标标程程序序段段装装配配成成可可执执行行的的目目标标程程序序； “运运行行”作作业业步步，将将可可执执行行的的目目标标程程序序读读入入内内存存并并控控制制其其运行。运行。(3) 作业流。作业流。若干个作业进入系统后，被依次存放在外存上，这
4、便形成了输入的作业流输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流处理作业流。 第三章处理机调度与死锁 2 2作业控制块作业控制块JCB(Job Control Block)JCB(Job Control Block)作业控制块是作业在系统中存在的标志，其中保存了系作业控制块是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。统对作业进行管理和调度所需的全部信息。在在JCB中通常应包含的内容有：中通常应包含的内容有：作业标识、用户名称、用户帐户、作业类作业标识、用户名称、用户帐户、作业类型型(CPU 繁忙型、繁忙型、I/O 繁忙型、批量型、终
5、端型繁忙型、批量型、终端型)、作业状态、调度信息、作业状态、调度信息(优优先级、作业已运行时间先级、作业已运行时间)、资源需求、资源需求(预计运行时间、要求内存大小、要求预计运行时间、要求内存大小、要求I/O设备的类型和数量等设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。作业退出时间、资源使用情况等。 作业进入系统建立作业进入系统建立JCB，插入相应的队列。作业调度程，插入相应的队列。作业调度程序调度作业装入内存。在作业运行期间，按照序调度作业装入内存。在作业运行期间，按照JCB中的信息对中的信息对作业进
6、行控制。作业执行结束时，系统负责回收分配给它的作业进行控制。作业执行结束时，系统负责回收分配给它的资源，撤消它的作业控制块。资源，撤消它的作业控制块。 第三章处理机调度与死锁 3 3作业调度作业调度作业调度的主要功能是根据作业控制块中的信息，审查根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，系统能否满足用户作业的资源需求，以及按照一定的算法，从从外存外存的后备队列中选取某些作业的后备队列中选取某些作业调入内存调入内存，并为它们创建，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。
7、列，准备执行。因此，有时也把作业调度称为接纳调度有时也把作业调度称为接纳调度(Admission Scheduling)。 第三章处理机调度与死锁 在每次执行作业调度时，都须做出以下两个决定。在每次执行作业调度时，都须做出以下两个决定。 1) 决定接纳多少个作业决定接纳多少个作业取决于多道程序度取决于多道程序度(Degree of Multiprogramming)，即允，即允许多少个作业同时在内存中运行。许多少个作业同时在内存中运行。 当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，当内存中同时运行的作业数目太多时，可能会影响到系统的服务质量，比如，使周转时间太长。但如果在内存
8、中同时运行作业的数量太少时，又比如，使周转时间太长。但如果在内存中同时运行作业的数量太少时，又会导致系统的资源利用率和系统吞吐量太低。会导致系统的资源利用率和系统吞吐量太低。 多道程序度的确定应根据系统的规模和运行速度等情况做多道程序度的确定应根据系统的规模和运行速度等情况做适当的折衷适当的折衷。 2) 决定接纳哪些作业决定接纳哪些作业 取决于所采用的调度算法取决于所采用的调度算法。第三章处理机调度与死锁 在在批处理系统中批处理系统中，需要有作业调度需要有作业调度的过程，以便将它们的过程，以便将它们分批地装入内存。分批地装入内存。分时系统中无需配置作业调度机制分时系统中无需配置作业调度机制，但
9、需要有某些限制，但需要有某些限制性措施来限制进入系统的用户数。即，如果系统尚未饱和，性措施来限制进入系统的用户数。即，如果系统尚未饱和，将接纳所有授权用户，否则，将拒绝接纳。将接纳所有授权用户，否则，将拒绝接纳。在在实时系统中通常也不需要作业调度实时系统中通常也不需要作业调度。 第三章处理机调度与死锁 3.1.2 3.1.2 低级调度（低级调度（Low Level Scheduling)Low Level Scheduling)进程调度、短程调度进程调度、短程调度( (ShortTermShortTerm Scheduling) Scheduling)调度的对象是进程调度的对象是进程( (或内
10、核级线程或内核级线程) )1 1低级调度的功能低级调度的功能调调度度用用于于决决定定就就绪绪队队列列中中的的哪哪个个进进程程( (或或内内核核级级线线程程，为为叙叙述述方方便便，以以后后只只写写进进程程) )应应获获得得处处理理机机，然然后后再再由由分分派派程程序序执执行把处理机分配给该进程的具体操作。行把处理机分配给该进程的具体操作。低低级级调调度度程程序序是是操操作作系系统统最最为为核核心心的的部部分分，低低级级调调度度策策略略的优劣直接影响到整个系统的性能的优劣直接影响到整个系统的性能第三章处理机调度与死锁 低级调度的过程如下：低级调度的过程如下： (1) (1) 保保存存处处理理机机的
11、的现现场场信信息息。如程序计数器、多个通用寄存器中的内容等，将它们送入该进程的进程控制块(PCB)中的相应单元。(2) 按某种算法选取进程。按某种算法选取进程。低级调度程序按某种算法，从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。 (3) 把处理器分配给进程。把处理器分配给进程。由分派程序由分派程序(Dispatcher)把处把处理器分配给进程。此时需为选中的进程恢复处理机现场，理器分配给进程。此时需为选中的进程恢复处理机现场，即把即把选中进程的进程控制块内有关处理机现场的信息装入处理器相选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，应的各
12、个寄存器中，把处理器的控制权交给该进程，让它从取把处理器的控制权交给该进程，让它从取出的断点处开始继续运行。出的断点处开始继续运行。 第三章处理机调度与死锁 2 2进程调度中的三个基本机制进程调度中的三个基本机制（1 1） 排队器。排队器。（2） 分派器分派器(分派程序分派程序)。（3）上上下下文文切切换换机机制制。当当对对处处理理机机进进行行切切换换时时，会会发发生生两两对对上上下下文文切切换换操操作作。在在第第一一对对上上下下文文切切换换时时，操操作作系系统统将将保保存存当当前前进进程程的的上上下下文文，而而装装入入分分派派程程序序的的上上下下文文，以以便便分分派派程程序序运运行行；在在第
13、第二二对对上上下下文文切切换换时时，将将移移出出分分派派程程序序，而而把把新新选选进进程程的的CPU现现场场信信息息装装入入到到处处理理机机的的各各个个相相应应寄寄存存器器中中。 应当指出，上上下下文文切切换换将将花花去去不不少少的的处处理理机机时时间间，即使是现代计算机，每一次上下文切换大约需要花费几毫秒的时间，该时间大约可执行上千条指令。第三章处理机调度与死锁 3 3进程调度方式进程调度方式进程调度可采用下述两种调度方式。1) 1) 非抢占方式非抢占方式(Nonpreemptive Mode)(Nonpreemptive Mode)在采用这种调度方式时，一旦把处理机分配给某进程后，一旦把处
14、理机分配给某进程后，不管它要运行多长时间，都一直让它运行下去不管它要运行多长时间，都一直让它运行下去，决不会因为时钟中断等原因而抢占正在运行进程的处理机，也不允许其它进程抢占已经分配给它的处理机。直至该进程完成，自愿直至该进程完成，自愿释放处理机，或发生某事件而被阻塞时，才再把处理机分配释放处理机，或发生某事件而被阻塞时，才再把处理机分配给其他进程。给其他进程。 第三章处理机调度与死锁 在采用非抢占调度方式时，可可能能引引起起进进程程调调度度的的因因素素可可归归结为如下几个：结为如下几个：(1) (1) 正正在在执执行行的的进进程程执执行行完完毕毕，或或因因发发生生某某事事件件而而不不能能再再
15、继续执行；继续执行；(2) (2) 执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；(3) (3) 在在进进程程通通信信或或同同步步过过程程中中执执行行了了某某种种原原语语操操作作，如如P P操作操作(wait(wait操作操作) )、BlockBlock原语等。原语等。这种调度方式的优点这种调度方式的优点是实现简单，系统开销小，适用于大实现简单，系统开销小，适用于大多数的批处理系统环境多数的批处理系统环境。但它难以满足紧急任务的要求立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式实时系统中，不宜采用这种调度方式。 第
16、三章处理机调度与死锁 2) 2) 抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)这种调度方式允许调度程序根据允许调度程序根据某种原则某种原则去暂停某个正去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一在执行的进程，将已分配给该进程的处理机重新分配给另一进程。进程。 抢占方式的优点是，抢占方式的优点是，可以防止一个长进程长时间占用处可以防止一个长进程长时间占用处理机，能为大多数进程提供更公平的服务，特别是能满足对理机，能为大多数进程提供更公平的服务，特别是能满足对响应时间有着较严格要求的实时任务的需求。响应时间有着较严格要求的实时任务的需求。但抢占方式比非抢占方式调度所需付出的开销较大。但抢占方式比非抢占方式调度所需付出的开销较大。第三章处理机调度与死锁 抢占调度方式是基于一定原则的，主要有如下几条：抢占调度方式是基于一定原则的，主要有如下几条： (1) (1) 优优先先权权原原则则。就就绪绪的的优优先先权权高高的的进进程程有有权权抢抢占占低低优优先先权进程的处理机。权进程的处理机。(2) 短作业短作业(进程进程)优先原则。优先原则。
