第4章 调度与死锁

第四章调度与死锁,在多道程序系统中，一个作业从提交到执行，通常都要经过多级调度，而系统运行的性能在很大程度上取决于调度，因此调度便成为操作系统设计的一个中心问题之一。,本章介绍内容：调度的类型和模型调度算法批处理调度、分时调度和实时调度死锁的基本概念死锁的预防和避免死锁的检测和解除,4.1调度的类型和模型,1、调度的分类,按调度的层次,高级调度,按OS的类型,中级调度,低级调度,批处理调度,分时和实时调度,多处理机调度,4.1调度的类型和模型,决定把那些后备队列中的作业调入内存，并为其创建进程，分配必要的资源，最后将所创建的进程挂在就绪队列上，准备执行。,（1）高级调度=作业调度,2、高级、低级和中级调度,作业调度的任务：接纳多少个作业：取决于允许多少个作业同时在内存中运行接纳哪些作业：取决于所采用的调度算法,批处理系统中配有作业调度分时和实时系统中通常没有作业调度作业调度的运行效率较低，几分钟才调度一次,4.1调度的类型和模型,决定就绪队列中哪个进程先获得处理机，然后再由分派程序执行将处理机分配给进程的操作。,（2）低级调度=进程调度,进程调度运行效率很高，典型情况是几十毫秒一次批处理系统、分时系统和实时系统中必须配置进程调度,工作方式：非抢占方式：适用于批处理系统，实现简单、系统开销小抢占方式：时间片原则、优先权原则、短作业优先原则,4.1调度的类型和模型,作用：按一定算法在内存和外存之间进行进行对换,（3）中级调度=进程对换,目的：提高内存的利用率和系统的吞吐量,任务：是将内存中处于阻塞状态的某些进程换至外存，腾出内存空间以便将外存上已具备执行条件的进程换入内存。,4.1调度的类型和模型,3、调度队列模型,（1）仅有进程调度的调度队列模型,（2）具有高级和低级调度的调度队列模型,（3）同时具有三级调度的调度队列模型,4.1调度的类型和模型,周转时间短周转时间：从作业提交开始到完成止的这段时间间隔包括：（1）作业在外存后备队列上等待进入内存的时间；（2）在就绪队列上等待获得处理机的时间；（3）在CPU上的执行时间；（4）等待I/O操作完成的时间。,4、选择调度方式和算法的准则,面向用户的准则,响应时间快响应时间：指从提交一个请求开始到首次产生响应为止（显示出结果）的一段时间间隔。包括：（1）把请求信息从键盘传送到计算机的时间；（2）计算机对请求进行处理的时间；（3）再将响应送回终端的时间。,周转时间短,响应时间快,截止时间的保证,优先权准则,4.1调度的类型和模型,4、选择调度方式和算法的准则,面向系统的准则,系统吞吐量高,处理机利用率好,各类资源的平衡利用,4.2调度算法调度的基本概念,2、后备作业队列,是由作业控制块用表格或链指针组成的队列可按优先数大小和作业到达系统的时间顺序排列,3、进程调度,作业调度：是按照某种调度算法从后备队列中挑选作业进入主存中运行（在实时系统中通常不需要）。功能：挑选作业、分配资源、建立进程、构造作业表、结束处理,1、作业调度,进程调度：决定就绪队列中的那个进程获得处理机。在三种类型的操作系统中都必须配置这级调度。,指根据系统的资源分配策略所规定的资源分配算法。,4.2调度算法先来先服务调度算法(FCFS),原理,就绪队列按进入的先后次序排列，调度时，选队首进程投入运行。,特点：简单、易于实现、服务质量不佳较有利于CPU繁忙型的作业，不利于I/O繁忙型作业,4.2调度算法短作业(进程)优先调度算法,指对短作业或短进程优先调度的算法。可分别用于作业调度和进程调度。,（1）SJF,从后备队列中选出一个或若干个估计运行时间最短的作业，将它们调入内存。,（2）SPF,从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它以便运行进程。,特点,能有效地降低作业的平均等待时间能提高系统的吞吐量对长作业非常不利未考虑作业的紧迫程度不一定能真正做到短作业优先调度,4.2调度算法时间片轮转调度算法,就绪队列中的所有进程在一给定时间内，均可获得一个时间片的处理机执行时间。,(1)系统对响应时间的要求,响应时间T用户进程数目N时间片qT=Nqq正比于系统要求的响应时间,(2)就绪队列中进程的数目,就绪队列上所有的进程数，是随着在终端上机的用户数目而改变的。Q反比于分时系统所配置的终端数目,(3)系统的处理能力,是必须保证用户键入的常用命令能在一个时间片内处理完毕，否则将无法保证得到满意的响应时间，而且会使平均周转时间及带权周转时间都很长。,时间片大小的确定（p104),4.2调度算法优先权调度算法,是在批处理系统和实时系统中常用的一种调度算法是把处理机分配给就绪队列中具有最高优先权的进程,(1)静态优先权,在创建进程时确定在整个运行期间不改变确定优先权的依据：进程类型进程对资源的要求用户要求的优先级、,(2)动态优先权,基于某种原则，使进程的优先权随时间而改变。,(3)算法的两种方式,非抢占优先权算法：处理机分配给就绪队列优先权最高的进程抢占优先权调度算法：出现另一个优先权高的进程时停止原来,确定进程优先权的方法,4.2调度算法高响应比优先调度算法,短作业优先算法+动态优先调度算法,(1)算法描述,等待时间+要求服务时间响应时间优先权=-=-要求服务时间要求服务时间,(2)特点,如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业；当要求服务的时间相同时，作业的优先权决定于等待时间，因而是实现了先来先服务；对于长作业，当其等待时间足够长时，其优先权便可升到很高，从而也可获得处理机调度之前都需先进行响应比的计算，增加了系统的开销。,4.2调度算法高响应比优先调度算法,试问在单道环境下，采用高响应比优先调度算法，作业的执行顺序是什么？,例：设有一组作业，它们的提交及所需运行时间如下所示：,平均周转时间？平均带权周转时间？,4.2调度算法多级队列调度算法,实际计算机系统都配置了几种类型的操作系统。例如：既配置了批处理系统，用于批处理作业；又配置了分时操作系统来处理交互型作业。,通常批处理作业-后台就绪队列-优先权高优先调度算法交互型作业-前台就绪队列-时间片轮转调度算法,4.2调度算法多级反馈队列调度算法,多级反馈队列：是设置了多个就绪队列，并赋予各队列不同的优先权。,1、调度算法,（1）设置多个就绪队列，并为各个队列赋予不同的优先权（2）赋予各个队列中进程执行时间片的大小也各不相同优先权-高时间片-小（3）新进程进入内存后，放在第一队列未尾，先来先服务（4）按队列顺序运行,2、性能,该算法具有较好的性能，能较好地满足各种类型用户的需要。终端型用户、短批处理作业用户、长批处理作业用户,4.2调度算法多级反馈队列调度算法,例：有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。,列出所有作业进入内存时间及结束时间。,平均周转时间？平均带权周转时间？,4.3实时系统调度算法,实时进程或任务往往带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊的要求。一、对实时系统的要求提供必要的调度信息就绪时间截止时间处理时间资源要求优先级调度方式抢占调度方式具有快速响应外部中断的能力快速任务分派,4.3实时系统调度算法,二、实时调度算法（注意各种算法的优缺点）时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占优先权调度算法立即抢占三、实时调度的实例具有开始截止时间的非周期实时任务的调度具有完成截止时间的周期性实时任务的调度,4.4多处理机调度,前面讲的都是单处理机环境下的进程调度，当系统中有多处理机时，进程调度就变得复杂起来。此外，在系统中引入线程后，调度的基本单位已是线程，本节主要介绍对线程的调度问题。一、进程调度在多处理机系统中，进程的调度与系统结构有关。1同构形多处理机中的进程调度静态分配：这是指一个进程从开始执行直至完成，都被固定的分配到一台处理机上运行。特点：每一台处理机都有一个就绪进程队列。优点：进程的调度开销小。缺点：各处理机的忙闲不均。缺点：调度开销大,4.4多处理机调度,动态分配：为防止系统中多个处理机忙闲不均，在系统中设置一个公共就绪队列，系统中的所有就绪进程都放在该队列中。分配处理机时，对一进程而言，可分配到任意一台处理机上。特点：系统中所有的就绪进程都放在一个公共的就绪队列中。优点：消除了处理机忙闲不均的现象自调度：在系统中设置一个就绪队列，系统中的所有进程都挂在该队列上。自调度方式是由每一个处理机自己去查看公共就绪队列，从中选择一个进程令其执行。、异构型多处理机系统中的进程调度OS大多采用主从式OS，即OS的核心驻留在主机上，而从机只是执行用户程序，进程调度只有主机执行。优点：主机独自处理，同步问题简单。缺点：主机一旦故障，会使整个系统瘫痪。主机太忙，形成系统瓶颈。,4.4多处理机调度,二、调度方式有代表性的进（线）程调度方式有：自调度方式：系统中有一个公共的线程或进程队列，所有的处理机在空闲时，都可自己从该队列中取出一个进程或线程运行。成组调度：系统将一组相关的进程或线程同时分配到一组处理机上运行，在应用程序未结束之前，处理机专用于处理这组线程。专用处理机分配方式：它是将同属于一个应用程序的一组线程，分配到一组处理机上运行，在应用程序未结束前，处理机专用于处理这组线程。有代表性的三种自调度算法：FCFS2最小优先数优先的算法枪占式最小优先数优先算法,4.6死锁的的基本概念产生死锁的原因,指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。,（1）可剥夺和非剥夺性资源可剥夺资源：处理机、内存非剥夺资源：磁带机、打印机（2）竞争非剥夺性资源如：进程P1、P2，共享打印机（R1）和磁带机（R2）P1-占有打印机（R1）-要求磁带机P2-占有磁带机（R2）-要求打印机,1、竞争资源引起死锁,进程P1,进程P2,打印机R1,磁带机R2,（3）竞争临时性资源永久性资源：可顺序重复使用的资源临时性资源：指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源。例：进程之间通信时的死锁,进程P1,进程P2,消息S3,消息S1,进程P3,消息S2,P1:产生S1；接收S3P2:产生S2；接收S1P3:产生S3；接收S2,P1:接收S3；产生S1P2:接收S1；产生S2P3:接收S2；产生S3,死锁,4.6死锁的的基本概念产生死锁的原因,2、进程推进顺序不当引起死锁,进程推进顺序合法进程推进顺序非法,P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2),P2Req(R1),P2Req(R2),D,P2Rel(R1),P2Rel(R2),4.6死锁的必要条件,1、互斥条件,要求在一段时间内某资源仅被一进程占用。,2、请求和保持条件,当进程因请求资源而阻塞时，对已获得的资源保持不放,3、不剥夺条件,进程已获得的资源，只能在使用完时自行释放。,4、环路等待条件,在发生死锁时，必然存在一个进程-资源的环行链。,防止死锁发生的根本办法是使上述必要条件之一永不存在！,综上所述可以看出，在同时具备下列四个必要条件时，就会产生死锁,4.6死锁的必要条件处理死锁的基本方法,1、预防死锁,通过设置某些限制条件，以破坏产生死锁的四个必要条件之一的一个或几个条件，来防止发生死锁。由于施加条件严格，可能导致资源利用率很低。,2、避免死锁,在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。可获得较高的资源利用率和系统吞吐量，但难度较大。,3、检测死锁,通过系统设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后采取适当措施，从系统中将已发生的死锁清除掉。,4、解除死锁,是与检测死锁配套的一种措施，用于将进程从死锁状态下解脱出来。,4.7死锁的预防和避免死锁的预防,1、预先静态分配法-摒弃“请求和保持”条件,系统要求所有进程要依次性地申请在整个运行过程所需要的全部资源。摒弃请求条件：进程在整个运行期间，不会再提出资源要求摒弃保持条件：等待期间的进程未占有任何资源优点：简单、易于实现、且安全缺点：（1）资源严重浪费（2）进程延迟运行,2、摒弃“不剥夺”条件,进程已占有的资源在运行过程中可被剥夺；实现难度较大，且要付出很大代价。,3、有序资源使用法-摒弃“环路等待”条件,系统将所有的资源按类型进行线性排队，并赋予不同的序号。使得资源利用率和系统吞吐量都有显著提高缺点：限制了新设备类型的增加，造成资源的浪费，限制用户的自主编程。,4.7死锁的预防和避免死锁的预防,1、安全状态,安全状态：指系统能按某种进程推进顺序，来为每个进程分配其所需资源，直至最大需求，使每个进程都能顺利完成不安全状态：不存在安全序列的状态只要系统处于安全状态，系统便可避免进入死锁状态。,2、安全状态实例,假定系统有三个进程P1、P2、P3，共有12台磁带机。进程最大需求已分配可用P11053P242P392安全序列：P2，P1，P3,3、由安全状态向不安全状态转换,不能向进程随便分配资源,4.7死锁的预防和避免银行家算法避免死锁,1、银行家算法中的数据结构,（1）可利用资源向量Available,是一个含有m个元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目。其值随资源的分配和回收而动态地改变。,（2）最大需求矩阵Max,是一个n*m的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。,（3）分配矩阵Allocation,是一个n*m的矩阵，定义了系统中每一类资源当前已分配给每一进程的资源数。,（4）需求矩阵Need,是一个n*m的矩阵，表示每一个进程尚需的该类资源数。,4.7死锁的预防和避免银行家算法避免死锁,2、银行家算法：设Request是进程Pi的请求向量,Request=Need,Request=Available,等待,系统把要求的资源试探分配给进程Pi,Available:=Available-Requesti;Allocation:=Allocationi+Requesti;Needi:=Needi-Requesti,系统执行安全算法,出错,Y,Y,N,N,分配资源给进程,试探分配作废,4.7死锁的预防和避免银行家算法避免死锁,3、安全性算法：,（1）设置两个向量,工作向量work:表示系统可提供给进程继续运行所需的各类资源数目。Finish:表示系统是否有足够的资源分配给进程，使之运行初始：Finishi=false当有足够资源时，令：Finishi=true,（2）从进程集合中找到一个能满足下述条件的进程：,Finishi=falseNeedi=work,（3）执行：,Work:=Work+Allocationi;Finishi:=true;gotostep(2);,（4）安全与否,如果：Finishi=true则安全,4.7死锁的预防和避免银行家算法避免死锁,4、银行家算法的优缺点：,（1）优点,提高了资源利用程度系统总是处于安全状态,（2）缺点,被分配的每类资源的数量是固定不变的-难以实现用户数保持固定不变-分时环境用户数是变化的仅保证所有用户的要求在有限时间内得到满足-实时用户要求用户事先说明其最大资源要求-不方便,4.8死锁的检测和解除资源分配图及其化简,当系统为进程分配资源时，若未采取任何限制措施，则系统必须提供检测和解除死锁的手段。为此系统必须有：（1）保存有关资源的请求和分配信息；（2）提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。,可简化的和不可简化的资源分配图,当且仅当系统某状态S所对应的资源分配图是不可化简的，则S是死锁状态，而不可化简的进程是被死锁的进程。,1、资源分配图：,进程P1,进程P2,2、死锁定理：,4.8死锁的检测和解除资源分配图及其化简,3、死锁检测中的数据结构,（1）可利用资源向量Available：表示了资源的可用数目（2）把不占用资源的进程向量Allocation:=0记入表L中（3）从进程集合中找到一个Requesti=Work的进程，将其资源分配图简化，释放出资源，增加工作向量：Work:=Work+Allocationi将它记入L表中（4）若不能把所有进程都记入L表中，该系统状态将发生死锁,Work:=Available;L:=L|Allocationi=0Requesti=0forallLLdobeginforallRequesti=WorkdobeginWork:=Work+Allocation;LL;endenddeadlock:=(L=p1,p2,pn),4.8死锁