第四章处理机调度与死锁

第四章处理机调度与死锁第一页，共四十八页，编辑于2023年，星期五4.1处理机调度一、分级调度处理机调度可分为四级：作业调度（宏观调度或高级调度）：负责从后备作业中选择若干作业调到内存，并为它们分配相应的资源，当作业运行完毕时，负责回收资源。交换调度（中级调度）：负责外存交换区域内存中的就绪状态或等待状态的进程进行交换。进程调度（微观调度或低级调度）负责选取适当的进程占有处理机线程调度第二页，共四十八页，编辑于2023年，星期五4.1处理机调度二、作业调度1、主要功能审查系统能否满足用户作业的资源要求，较容易，只要通过调用相应的资源管理程序的有关部分，审核其表中是否能满足作业说明书中的要求即可。按照一定的算法丛输入井中的后备作业中选取作业。第三页，共四十八页，编辑于2023年，星期五4.1处理机调度

调度的关键在选择恰当的算法2、调度算法的评价调度实质上是一个策略问题，设定的目标往往是相互冲突的。目标：单位时间内运行尽可能多的作业是处理机尽可能保持“忙碌”使各种I/O设备得以充分利用对所有的作业都是公平合理的要设计一个理想的调度算法是一件十分困难的事，在实际系统中，调度算法往往折衷考虑第四页，共四十八页，编辑于2023年，星期五4.1处理机调度设计调度算法时应考虑的因素：调度算法应与系统设计目标保持一致注意系统资源均衡使用保证提交的作业在截止时间内完成设法缩短作业平均周转时间

大多数操作系统都采用比较简单的调度算法第五页，共四十八页，编辑于2023年，星期五4.1处理机调度3、调度算法性能的衡量（1）作业平均周转时间：假定某一作业进入“输入井”的时间为Si，它被选中执行，得到计算结果的时间为Ei，它的周转时间为Ti=Ei-Si则作业平均周转时间为：T=（）×1/n

其中，n为被测定作业流中的作业数

第六页，共四十八页，编辑于2023年，星期五4.1处理机调度（2）平均带权某周转时间

W=（）×1/n

其中，ri为作业i的实际执行时间T：衡量不同调度算法对同一个作业流的性能W：同一调度算法对不同作业流的性能衡量第七页，共四十八页，编辑于2023年，星期五4.1处理机调度4、系统进行作业调度的决策因素作业到达时间预先为作业确定的优先级第八页，共四十八页，编辑于2023年，星期五4.1处理机调度三、常见的批处理作业调度算法1、先来先服务（FCFS:FirstComeFirstServe)2、最短作业优先算法（SJF:ShortestJobFirst)3、最高响应比优先算法（HRN:HighestResponseRatioNext)响应比R=作业周转时间/作业处理时间

=（作业处理时间+作业等待时间）/作业处理时间

=1+作业等待时间/作业处理时间第九页，共四十八页，编辑于2023年，星期五4.1处理机调度4、基于优先数调度算法（HPF：HeghestPriorityFirst）（1）由用户规定优先数（外部优先数）用户提交作业时，根据急迫程度规定适当的优先数。作业调度程序根据JCB优先数决定适当的优先数（2）由系统计算优先数（内部优先数）例：可按如下公式计算作业的优先数：优先数=用户规定优先数-作业处理时间+作业等待时间-输出量第十页，共四十八页，编辑于2023年，星期五4.1处理机调度5、轮转法基本思路：让每个进程在就绪队列中的等待时间与享受服务的时间成正比。时间片的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。表示为：q=R/Nmax只能用来调度那些可以抢占的资源。该方法不用于作业调度第十一页，共四十八页，编辑于2023年，星期五4.1处理机调度6、均衡调度算法（分类排队算法）基本思想：根据系统运行情况和作业属性将作业分类轮流从不同的作业类中挑选作业目标：力求均衡地利用各种系统资源，发挥资源使用效率力求使用户满意第十二页，共四十八页，编辑于2023年，星期五4.1处理机调度例1：将待处理作业分成如下队列：队列1：计算量大的作业队列2：I/O量大的作业队列3：计算量与I/O量均衡的作业调度时，在三个队列中各取一些作业 在内存中的作业有的使用处理机 有的使用外部设备使得系统的各种资源能得到充分利用第十三页，共四十八页，编辑于2023年，星期五4.1处理机调度例2：将待处理作业分成如下三个队列：队列1：长作业队列2：中等长度作业队列3：短作业调度时 取队列1一作业，队列2一作业，队列3一作业长作业用户和短作业用户均比较满意第十四页，共四十八页，编辑于2023年，星期五4.1处理机调度四、调度算法举例例1：假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间第十五页，共四十八页，编辑于2023年，星期五4.1处理机调度先来先服务：第十六页，共四十八页，编辑于2023年，星期五4.1处理机调度短作业优先：第十七页，共四十八页，编辑于2023年，星期五4.1处理机调度最高响应比优先：第十八页，共四十八页，编辑于2023年，星期五4.1处理机调度例2：在两道环境下有四个作业已知它们进入系统的时间、估计运行时间系统采用短作业优先作业调度算法，作业被调度运行后不再退出当一新作业投入运行后，可按照作业运行时间长短调整作业执行的次序请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间第十九页，共四十八页，编辑于2023年，星期五4.1处理机调度短作业优先：四个作业的执行时间序列为：JOB1：10：00—10：05，10：40—11：05JOB2：10：05—10：25JOB3：10：25—10：30JOB4：10：30—10：40第二十页，共四十八页，编辑于2023年，星期五4.1处理机调度在两道批处理系统中，短作业优先算法的分析：10：00，JOB1进入，只有一作业，JOB1被调入执行10：05，JOB2到达，最多允许两作业同时进入所以JOB2也被调入内存中有两作业，哪一个执行？题目规定当一新作业运行后，可按作业运行时间长短调整执行次序即基于优先数可抢占式调度策略 优先数是根据作业估计运行时间大小来决定的 由于JOB2运行时间（20分）比JOB1少 （到10：05，JOB1还需25分钟） 所以JOB2运行，而JOB1等待第二十一页，共四十八页，编辑于2023年，星期五4.1处理机调度五、多道程序对平均周转时间的影响：作业流在多道环境下运行平均周转时间、带权平均周转时间比单道环境下都有明显改善不是任意作业组合都能改善调度性能有时甚至可能变坏第二十二页，共四十八页，编辑于2023年，星期五4.1处理机调度例：四个各需两小时作业同时投入运行，I/O等待时间均占25%，即占CPU时间各为1.5小时根据计算公式，CPU的空转率为0采用简单轮转法调度，每小时各作业分别占用25%的CPU时间，算得该作业组合的平均周转时间约为6小时，而平均带权周转时间约为3但是，若以单道程序方式运行：平均周转时间T=（2+4+6+8）/4=5小时平均带权周转时间W=（1+2+3+4）/4=2.5第二十三页，共四十八页，编辑于2023年，星期五4.1处理机调度课堂作业：教材P1084.6题第二十四页，共四十八页，编辑于2023年，星期五4.2死锁乙甲AB第二十五页，共四十八页，编辑于2023年，星期五4.2死锁一、死锁的概念死锁是两个或两个以上的进程中的每一个进程都在等待其中另一个进程释放资源而被封锁，它们都无法向前推进，这种现象称为死锁。第二十六页，共四十八页，编辑于2023年，星期五二、资源

1、永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源不可抢占资源2、临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式第二十七页，共四十八页，编辑于2023年，星期五三、死锁的四个必要条件1、死锁的起因死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所需要的该类资源数。显然，由于资源的有限性，我们不可能为所要求资源的进程无限制地提供资源。但是，我们可以采用适当的资源分配算法，以达到消除死锁的目的。第二十八页，共四十八页，编辑于2023年，星期五2、产生死锁的必要条件互斥使用：在一段时间内，一个资源只能由一个进程独占使用，若别的进程也要求该资源，则须等待直至其占用者释放，如：打印机；部分分配：允许进程在不释放其已分得的资源的情况下请求并等待分配新的资源；第二十九页，共四十八页，编辑于2023年，星期五不可剥夺条件：进程所获得的资源在未使用完之前，不能被其它进程强行夺走，而只能由其自行释放；循环等待：存在一个等待进程集合，P0正在等待一个P1占用的资源，P1正在等待一个P2占用的资源，……..Pn正在等待一个P0占用的资源。第三十页，共四十八页，编辑于2023年，星期五3、关于死锁的进一步说明死锁是进程之间的一种特殊关系，是由资源竞争引起的僵局关系，因此，当我们提到死锁时，至少涉及到两个进程。虽然单个进程也可能锁住自己，但那是程序设计错误而不是死锁；当出现死锁时，首先要弄清楚被锁的是哪些进程，因竞争哪些资源被锁；第三十一页，共四十八页，编辑于2023年，星期五在多数情况下，一系统出现死锁，是指系统内的一些而不是全部进程被锁，它们是因竞争某些而不是全部资源而进入死锁的，若系统的全部进程都被锁住，我们称系统处于瘫痪状态；系统瘫痪意味着所有进程都进入了睡眠（阻塞）状态，但所有进程都睡眠了，如果其中至少有一个进程可由I/O中断唤醒的话，这并不一定就是瘫痪状态。第三十二页，共四十八页，编辑于2023年，星期五四、死锁的表示1、死锁的表示死锁可以用有向图来表示，有向图形成环路则形成死锁。例如，有甲，乙两个进程，共享一台打印机资源A和一台输入机B，在工作使用时，共享资源被独占。死锁的有向示意图见图。第三十三页，共四十八页，编辑于2023年，星期五2、死锁定理如果不出现任何环，则此时系统内不存在死锁；如果出现了环，且处于此环中的每类资源均只有一个实体时，则有环就出现死锁，此时，环是系统存在死锁的充分必要条件；如果系统资源分配图中出现了环，但处于此环中的每类资源的个数不全为1，则环的存在只是产生死锁的必要条件而不是充分条件。第三十四页，共四十八页，编辑于2023年，星期五五、解决死锁问题的基本方法解决死锁的方法一般可分为预防、避免、检测与恢复等三种。1、死锁预防死锁预防的方法主要是打破造成死锁的四个必要条件中的一个，如允许进程同时访问某些资源，然而，这种方法不能解决访问那些不允许被同时访问的资源带来的死锁问题，比如打印机等。第三十五页，共四十八页，编辑于2023年，星期五①静态分配法：则是打破资源的部分分配这个死锁产生的必要条件。即预先分配各并发进程所需要的全部资源。②有序资源分配法：另一种死锁的预防方法是打破死锁的环路条件。即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。如有M中资源，则列出R1<R2<…….<Rm。若进程Pi保持了资源Ri，则它只能申请比Ri级别更高的资源Rj（Ri<Rj）。释放资源时必须是Rj先于Ri被释放，从而避免环路的产生。第三十六页，共四十八页，编辑于2023年，星期五③银行家算法：安全状态：是指系统能按某种进程顺序（P1，P2，…Pn）（称〈P1，P2，…Pn〉序列为安全序列）来为每个进程分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。并不是所有的不安全状态都是死锁状态，但当系统进入不安全状态后，就有可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免死锁状态。第三十七页，共四十八页，编辑于2023年，星期五单种资源法：n：系统中进程的总数m：资源类总数Available:ARRAY[1..m]ofinteger;//可利用资源Max:ARRAY[1..n,1..m]ofinteger;//最大需求量Allocation:ARRAY[1..n,1..m]ofinteger;//已分配资源Need:ARRAY[1..n,1..m]ofinteger;//还需资源Request:ARRAY[1..n,1..m]ofinteger;//请求资源当进程Pi提出资源申请时，系统执行下列步骤：第三十八页，共四十八页，编辑于2023年，星期五（1）若Request[i]≤Need[i],转（2）；否则错误返回（2）若Request[i]≤Available,

转（3）；否则进程等待（3）假设系统分配了资源，则有：Available:=Available-Request[i];Allocation[i]:=Allocation[i]+Request[i];Need[i]:=Need[i]-Request[i]第三十九页，共四十八页，编辑于2023年，星期五若系统新状态是安全的，则分配完成；若系统新状态是不安全的，则恢复原状态，进程等待进行安全性检查。定义数据结构：Work:ARRAY[1..m]ofinteger;Finish:ARRAY[1..n]ofBoolean;安全性检查的步骤：第四十页，共四十八页，编辑于2023年，星期五(1)Work:=Available;Finish:=false;(2)寻找满足条件的i：

Finish[i]=false;Need[i]≤Work;如果不存在，则转(4)（3)当进程Pi获得资源后，可顺利执行计算，直至完成，并释放出分配给它的资源：

Work:=Work+Allocation[i];Finish[i]:=true;

转(2)(4)若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态第四十一页，共四十八页，编辑于2023年，星期五AllocationMaxNeedP1143P2462P3583Available2进程资源情况第四十二页，共四十八页，编辑于2023年，星期五多种资源法：

Allocation Need ABC A B C P1 0 1 0 7 5 3 P2 2 0 0 3 2 2 P3 3 0 2 9 0 2 P4 2 1 1 2 2 2 P5 0 0 24 3 3 Available：A B C 332 第四十三页，共四十八页，编辑于2023年，星期五2、死锁避免静态预先分配所有资源算法。即事先静态说明而后静态分配，破坏部分分配条件，但这种方法的资源利用率低。受控资源分配法：1969年由Haberman提出，分配资源前先检查会不会发生死锁，要求各进程说明所需资源，将资源分类，按不同策略分配，又称为静态说明动态分配。第四十四页，共四十八页，编辑于2023年，星期五3、死锁检测与恢复