第四章处理机调度与死锁优秀PPT.ppt

第四章处理机调度与死锁第一页，本课件共有48页4.1 处理机调度一、分级调度处理机调度可分为四级：v作业调度（宏观调度或高级调度）：负责从后备作业中选择若干作业调到内存，并为它们分配相应的资源，当作业运行完毕时，负责回收资源。v交换调度（中级调度）：负责外存交换区域内存中的就绪状态或等待状态的进程进行交换。v进程调度（微观调度或低级调度）负责选取适当的进程占有处理机v线程调度第二页，本课件共有48页4.1 处理机调度二、作业调度1、主要功能v审查系统能否满足用户作业的资源要求，较容易，只要通过调用相应的资源管理程序的有关部分，审核其表中是否能满足作业说明书中的要求即可。v按照一定的算法丛输入井中的后备作业中选取作业。第三页，本课件共有48页4.1 处理机调度 调度的关键在选择恰当的算法调度的关键在选择恰当的算法2、调度算法的评价调度实质上是一个策略问题，设定的目标往往是相互冲突的。目标：v单位时间内运行尽可能多的作业v是处理机尽可能保持“忙碌”v使各种I/O设备得以充分利用v对所有的作业都是公平合理的要设计一个理想的调度算法是一件十分困难的事，要设计一个理想的调度算法是一件十分困难的事，在实际系统中，调度算法往往折衷考虑在实际系统中，调度算法往往折衷考虑第四页，本课件共有48页4.1 处理机调度设计调度算法时应考虑的因素：v调度算法应与系统设计目标保持一致v注意系统资源均衡使用v保证提交的作业在截止时间内完成v设法缩短作业平均周转时间 大多数操作系统都采用比较简单的调度算法大多数操作系统都采用比较简单的调度算法第五页，本课件共有48页4.1 处理机调度3、调度算法性能的衡量（1）作业平均周转时间：假定某一作业进入“输入井”的时间为Si，它被选中执行，得到计算结果的时间为Ei，它的周转时间为Ti=Ei-Si则作业平均周转时间为：T=（）1/n 其中，n为被测定作业流中的作业数 第六页，本课件共有48页4.1 处理机调度（2）平均带权某周转时间 W=（）1/n 其中，ri为作业i的实际执行时间 T：衡量不同调度算法对同一个作业流的性能：衡量不同调度算法对同一个作业流的性能W：同一调度算法对不同作业流的性能衡量：同一调度算法对不同作业流的性能衡量第七页，本课件共有48页4.1 处理机调度4、系统进行作业调度的决策因素v 作业到达时间v 预先为作业确定的优先级第八页，本课件共有48页4.1 处理机调度三、常见的批处理作业调度算法1、先来先服务（FCFS:First Come First Serve)2、最短作业优先算法（SJF:Shortest Job First)3、最高响应比优先算法（HRN:Highest Response Ratio Next)响应比R=作业周转时间/作业处理时间 =（作业处理时间+作业等待时间）/作业处理时间 =1+作业等待时间/作业处理时间第九页，本课件共有48页4.1 处理机调度4、基于优先数调度算法（HPF：Heghest Priority First）（1）由用户规定优先数（外部优先数）v 用户提交作业时，根据急迫程度规定适当的优先数。v作业调度程序根据JCB优先数决定适当的优先数（2）由系统计算优先数（内部优先数）例：可按如下公式计算作业的优先数：优先数优先数=用户规定优先数用户规定优先数-作业处理时间作业处理时间+作业等待时间作业等待时间-输出量输出量第十页，本课件共有48页4.1 处理机调度5、轮转法v基本思路：让每个进程在就绪队列中的等待时间与享受服务的时间成正比。v时间片的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。表示为：q=R/Nmaxv只能用来调度那些可以抢占的资源。该方法不用于作业调度该方法不用于作业调度第十一页，本课件共有48页4.1 处理机调度6、均衡调度算法（分类排队算法）基本思想：v根据系统运行情况和作业属性将作业分类v轮流从不同的作业类中挑选作业目标：v力求均衡地利用各种系统资源，发挥资源使用效率v力求使用户满意第十二页，本课件共有48页4.1 处理机调度例1：将待处理作业分成如下队列：队列1：计算量大的作业 队列2：I/O量大的作业 队列3：计算量与I/O量均衡的作业v调度时，在三个队列中各取一些作业在内存中的作业有的使用处理机有的使用外部设备v使得系统的各种资源能得到充分利用第十三页，本课件共有48页4.1 处理机调度例2：将待处理作业分成如下三个队列：队列1：长作业 队列2：中等长度作业 队列3：短作业v调度时取队列1一作业，队列2一作业，队列3一作业v长作业用户和短作业用户均比较满意第十四页，本课件共有48页4.1 处理机调度四、调度算法举例例1：假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间第十五页，本课件共有48页4.1 处理机调度先来先服务：第十六页，本课件共有48页4.1 处理机调度短作业优先：第十七页，本课件共有48页4.1 处理机调度最高响应比优先：第十八页，本课件共有48页4.1 处理机调度例2：在两道环境下有四个作业已知它们进入系统的时间、估计运行时间系统采用短作业优先作业调度算法，作业被调度运行后不再退出当一新作业投入运行后，可按照作业运行时间长短调整作业执行的次序请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间第十九页，本课件共有48页4.1 处理机调度短作业优先：四个作业的执行时间序列为：四个作业的执行时间序列为：JOB1：10：0010：05，10：4011：05JOB2：10：0510：25JOB3：10：2510：30JOB4：10：3010：40第二十页，本课件共有48页4.1 处理机调度在两道批处理系统中，短作业优先算法的分析：10：00，JOB1进入，只有一作业，JOB1被调入执行10：05，JOB2到达，最多允许两作业同时进入 所以JOB2也被调入v内存中有两作业，哪一个执行？题目规定当一新作业运行后，可按作业运行时间长短调整执行次序v即基于优先数可抢占式调度策略优先数是根据作业估计运行时间大小来决定的由于JOB2运行时间（20分）比JOB1少（到10：05，JOB1还需25分钟）所以JOB2运行，而JOB1等待第二十一页，本课件共有48页4.1 处理机调度五、多道程序对平均周转时间的影响：作业流在多道环境下运行v平均周转时间、带权平均周转时间 比单道环境下都有明显改善v不是任意作业组合都能改善调度性能 有时甚至可能变坏第二十二页，本课件共有48页4.1 处理机调度例：四个各需两小时作业同时投入运行，I/O等待时间均占25%，即占CPU时间各为1.5小时根据计算公式，CPU的空转率为0采用简单轮转法调度，每小时各作业分别占用25%的CPU时间，算得该作业组合的平均周转时间约为6小时，而平均带权周转时间约为3但是，若以单道程序方式运行：v平均周转时间T=（2+4+6+8）/4=5小时v平均带权周转时间W=（1+2+3+4）/4=2.5第二十三页，本课件共有48页4.1 处理机调度课堂作业：教材P108 4.6题第二十四页，本课件共有48页4.2 死锁乙甲AB第二十五页，本课件共有48页4.2 死锁一、死锁的概念一、死锁的概念 死锁是两个或两个以上的进程中的每一个进程都在等待其中另一个进程释放资源而被封锁，它们都无法向前推进，这种现象称为死锁。第二十六页，本课件共有48页二、资源二、资源1、永久性资源：永久性资源：可以被多个进程多次使用（可再用资源）v 可抢占资源v 不可抢占资源2、临时性资源：、临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请-分配-使用-释放”模式第二十七页，本课件共有48页三、死锁的四个必要条件三、死锁的四个必要条件1、死锁的起因、死锁的起因 死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所需要的该类资源数。显然，由于资源的有限性，我们不可能为所要求资源的进程无限制地提供资源。但是，我们可以采用适当的资源分配算法，以达到消除死锁的目的。第二十八页，本课件共有48页2、产生死锁的必要条件、产生死锁的必要条件v互斥使用：在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放，如：打印机；v部分分配：允许进程在不释放其已分得的资源的情况下请求并等待分配新的资源；第二十九页，本课件共有48页v不可剥夺条件：进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由其自行释放；v循环等待：存在一个等待进程集合，P0正在等待一个P1占用的资源，P1正在等待一个P2占用的资源，.Pn正在等待一个P0占用的资源。第三十页，本课件共有48页3、关于死锁的进一步说明、关于死锁的进一步说明v死锁是进程之间的一种特殊关系，是由资源竞争引起的僵局关系，因此，当我们提到死锁时，至少涉及到两个进程。虽然单个进程也可能锁住自己，但那是程序设计错误而不是死锁；v当出现死锁时，首先要弄清楚被锁的是哪些进程，因竞争哪些资源被锁；第三十一页，本课件共有48页v在多数情况下，一系统出现死锁，是指系统内的一些而不是全部进程被锁，它们是因竞争某些而不是全部资源而进入死锁的，若系统的全部进程都被锁住，我们称系统处于瘫痪状态；v系统瘫痪意味着所有进程都进入了睡眠（阻塞）状态，但所有进程都睡眠了，如果其中至少有一个进程可由I/O中断唤醒的话，这并不一定就是瘫痪状态。第三十二页，本课件共有48页四、死锁的表示四、死锁的表示1、死锁的表示、死锁的表示 死锁可以用有向图来表示，有向图形成环路则形成死锁。例如，有甲，乙两个进程，共享一台打印机资源A和一台输入机B，在工作使用时，共享资源被独占。死锁的有向示意图见图。第三十三页，本课件共有48页2、死锁定理、死锁定理v如果不出现任何环，则此时系统内不存在死锁；v如果出现了环，且处于此环中的每类资源均只有一个实体时，则有环就出现死锁，此时，环是系统存在死锁的充分必要条件；v如果系统资源分配图中出现了环，但处于此环中的每类资源的个数不全为1，则环的存在只是产生死锁的必要条件而不是充分条件。第三十四页，本课件共有48页五、解决死锁问题的基本方法五、解决死锁问题的基本方法 解决死锁的方法一般可分为预防、避免、检测与恢复等三种。1、死锁预防死锁预防 死锁预防的方法主要是打破造成死锁的四个必要条件中的一个，如允许进程同时访问某些资源，然而，这种方法不能解决访问那些不允许被同时访问的资源带来的死锁问题，比如打印机等。第三十五页，本课件共有48页静态分配法：静态分配法：则是打破资源的部分分配这个死锁产生的必要条件。即预先分配各并发进程所需要的全部资源。有序资源分配法：有序资源分配法：另一种死锁的预防方法是打破死锁的环路条件。即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。如有M中资源，则列出R1R2.Rm。若进程Pi保持了资源Ri，则它只能申请比Ri级别更高的资源Rj（RiRj）。释放资源时必须是Rj先于Ri被释放，从而避免环路的产生。第三十六页，本课件共有48页银行家算法：银行家算法：安全状态：是指系统能按某种进程顺序（安全状态：是指系统能按某种进程顺序（P1，P2，Pn）（称）（称 P1，P2，Pn序列为安全序列）序列为安全序列）来为每个进程分配其所需资源，直至满足每个进程对资来为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。无法找到这样一个安全序列，则称系统处于不安全状态。并不是所有的不安全状态都是死锁状态，但当系统并不是所有的不安全状态都是死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态；反之，只要进入不安全状态后，就有可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免死锁状态。系统处于安全状态，系统便可避免死锁状态。第三十七页，本课件共有48页单种资源法：单种资源法：n：系统中进程的总数m：资源类总数Available:ARRAY1.m of integer;/可利用资源Max:ARRAY1.n,1.m of integer;/最大需求量Allocation:ARRAY1.n,1.m of integer;/已分配资源Need:ARRAY1.n,1.m of integer;/还需资源Request:ARRAY1.n,1.m of integer;/请求资源当进程Pi提出资源申请时，系统执行下列步骤：第三十八页，本课件共有48页（1）若RequestiNeedi,转（2）；否则错误返回（2）若RequestiAvailable,转（3）；否则进程等待（3）假设系统分配了资源，则有：Available:=Available-Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi-Requesti第三十九页，本课件共有48页若系统新状态是安全的，则分配完成；若系统新状态是不安全的，则恢复原状态，进程等待进行安全性检查。定义数据结构：Work:ARRAY1.m of integer;Finish:ARRAY1.n of Boolean;安全性检查的步骤：第四十页，本课件共有48页(1)Work:=Available;Finish:=false;(2)寻找满足条件的i：Finishi=false;NeediWork;如果不存在，则转(4)（3)当进程Pi 获得资源后，可顺利执行计算，直至完成，并释放出分配给它的资源：Work:=Work+Allocationi;Finishi:=true;转(2)(4)若对所有i,Finishi=true,则系统处于安全状态，否则处于不安全状态第四十一页，本课件共有48页AllocationMaxNeedP1143P2462P3583Available2进程资源情况第四十二页，本课件共有48页v多种资源法：多种资源法：Allocation Need A B C A B CP1 0 1 0 75 3P2 2 0 0 32 2P3 3 0 2 90 2P4 2 1 1 22 2P5 0 0 2 43 3Available：ABC 3 3 2第四十三页，本课件共有48页2、死锁避免、死锁避免v静态预先分配所有资源算法。即事先静态说静态预先分配所有资源算法。即事先静态说明而后静态分配，破坏部分分配条件，但这明而后静态分配，破坏部分分配条件，但这种方法的资源利用率低。种方法的资源利用率低。v受控资源分配法：受控资源分配法：1969年由年由Haberman提出，提出，分配资源前先检查会不会发生死锁，要求各分配资源前先检查会不会发生死锁，要求各进程说明所需资源，将资源分类，按不同策进程说明所需资源，将资源分类，按不同策略分配，又称为静态说明动态分配。略分配，又称为静态说明动态分配。第四十四页，本课件共有48页3、死锁检测与恢复死锁检测与恢复 死锁的检测算法当进程进行资源请求死锁的检测算法当进程进行资源请求时检查并发进程组是否构成资源的请求和保时检查并发进程组是否构成资源的请求和保持环路。有限状态转移图和持环路。有限状态转移图和petriNet等技术等技术都可用来有效地判断死锁的发生。死锁的恢都可用来有效地判断死锁的发生。死锁的恢复办法很多。最简单的办法是终止各锁住进复办法很多。最简单的办法是终止各锁住进程，或按一定的顺序中止进程序列，直至已程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程为止，释放到有足够的资源来完成剩下的进程为止，另外，也可以从被锁住进程强迫剥夺资源以另外，也可以从被锁住进程强迫剥夺资源以解除死锁。解除死锁。第四十五页，本课件共有48页4、处理死锁的综合措施处理死锁的综合措施 Howard在在1973年提出将解决死锁的基本方法年提出将解决死锁的基本方法组合起来，并对由不同类资源竞争所引起的死锁采组合起来，并对由不同类资源竞争所引起的死锁采用对它来说是最佳的方法来解决，以此来全面解决用对它来说是最佳的方法来解决，以此来全面解决死锁问题。这一个思想是基于以下事实：系统内的死锁问题。这一个思想是基于以下事实：系统内的全部资源可按层次分成若干类，对于每一类，可以全部资源可按层次分成若干类，对于每一类，可以使用最适合它的办法来解决死锁问题。由于使用了使用最适合它的办法来解决死锁问题。由于使用了资源分层技术，在一个死锁环中，通常只包含某一资源分层技术，在一个死锁环中，通常只包含某一层次的资源，每一个层次可以使用一种基本的方法。层次的资源，每一个层次可以使用一种基本的方法。因此，整个系统就不会受控于死锁了。因此，整个系统就不会受控于死锁了。第四十六页，本课件共有48页（1）资源分类内部资源：由系统本身使用的资源，例如，进程控制块PCB；（b）主存储器：主要指用户态程序空间；（c）作业资源：可分配的设备（如磁带机）和文件；（d）交换空间：存放用户作业的后援存储器空间。第四十七页，本课件共有48页（2）解决死锁的综合措施 对内部资源通过破坏“循环等待”条件，即给资源以线性编序的方法预防死锁；对主存储器通过剥夺资源的办法以防止死锁的产生。因为一个进程总是可以被对换出去的，并且主存储器空间本质上是可以被剥夺的；对作业资源使用死锁避免算法，关于作业要求多少资源的信息可以从作业控制卡中获得；对交换空间可以采用预分配措施。因为存储空间的最大需求量通常是知道的。第四十八页，本课件共有48页