操作系统课件第三章2

第三章处理机调度与死锁操作系统Page12023/2/3第三章处理机调度与死锁处理机调度的基本概念

调度算法实时调度

多处理机系统中的调度产生死锁的原因和必要条件

预防死锁的方法死锁的检测与解除Page22023/2/3产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page32023/2/3死锁的基本概念死锁例子一个由于申请不同类型资源而产生死锁的例子设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。用信号量S1表示R1是否可用，用信号量S2表示R2是否可用，S1、S2初值为1。Page42023/2/3死锁的基本概念这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才不会发生死锁？Page52023/2/3死锁的基本概念死锁的概念指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。Page62023/2/3死锁的基本概念关于死锁的一些结论参与死锁的进程最少是两个

参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。Page72023/2/3死锁的基本概念永久性资源和临时性资源永久性资源：可以被多个进程多次使用（可再用资源）可抢占资源：CPU不可抢占资源：打印机临时性资源：只可使用一次的资源；即由一个进程产生，被另一进程使用后就再也无用的资源，也称为消耗性资源如信号量,中断信号，同步信号等（可消耗性资源）“申请--分配--使用--释放”模式Page82023/2/3产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page92023/2/33.5产生死锁的原因和必要条件3.5.1产生死锁的原因竞争资源。当系统中供多个进程所共享的资源，不足以同时满足它们的需要时，引起它们对资源的竞争而产生死锁。

(2)进程间推进顺序非法。

进程在运行过程中，请求和释放资源的顺序不当，导致了进程死锁。

所谓死锁（Deadlock），是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。Page102023/2/3产生死锁的原因竞争资源引起进程死锁可剥夺和非剥夺性资源可剥夺性资源是指进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，如处理机、内存等非剥夺性资源是指当系统把这类资源分配给某个进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等竞争非剥夺性资源系统中的非剥夺性资源由于数量有限而不能满足进程运行的需要，进程在运行过程中因争夺这些资源而限入僵局竞争临时性资源Page112023/2/3产生死锁的原因I/O设备共享时的死锁情况

若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。R1R2P1P2分配分配请求请求Page122023/2/3产生死锁的原因

进程之间通信时的死锁S2P1S3P3S1P2产生P2产生P3产生要求接收要求接收要求接收Page132023/2/3产生死锁的原因进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④D不安全区Page142023/2/3产生死锁的原因若并发进程P1和P2按曲线④所示的顺序推进，它们将进入不安全区D内。此时P1保持了资源R1,P2保持了资源R2,系统处于不安全状态。因为，这时两进程再向前推进，便可能发生死锁。例如，当P1运行到P1:Request(R2)时，将因R2已被P2占用而阻塞；当P2运行到P2:Request(R1)时，也将因R1已被P1占用而阻塞，于是发生了进程死锁Page152023/2/3产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page162023/2/3产生死锁的必要条件互斥条件

进程对所分配到的资源进行排它性的使用请求和保持条件

进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有不剥夺条件进程已获得的资源在未使用完之前不能被剥夺环路等待条件在发生死锁时，必然存在一个进程--资源循环等待的环形链Page172023/2/3产生死锁的原因和必要条件死锁的基本概念产生死锁的原因产生死锁的必要条件处理死锁的基本方法Page182023/2/3处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁Page192023/2/33.5.3处理死锁的基本方法

目前用于处理死锁的方法可归结为以下四种：1、预防死锁通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。2、避免死锁不须采用各种限制措施去破坏产生死锁的必要条件，防止系统进入不安全状态，从而避免发生死锁，只需在事先加以较弱的限制条件。3、检测死锁不须检查系统是否已进入不安全区，允许系统在运行过程中发生死锁。4、解除死锁常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。Page202023/2/3处理死锁的基本方法方法资源分配策略各种可能模式主要优点主要缺点预防Prevention保守的；宁可资源闲置（从机制上使死锁条件不成立，即摒弃三个必要条件）一次请求所有资源<条件2>适用于作突发式处理的进程；不必剥夺效率低；进程初始化时间延长剥夺次数过多；多次对资源重新起动不便灵活申请新资源资源剥夺<条件3>适用于状态可以保存和恢复的资源资源按序申请<条件4>避免Avoidance是“预防”和“检测”的折衷（在运行时判断是否可能死锁）寻找可能的安全的运行顺序不必进行剥夺使用条件：必须知道将来的资源需求；进程可能会长时间阻塞检测Detection宽松的；只要允许，就分配资源定期检查死锁是否已经发生不延长进程初始化时间；允许对死锁进行现场处理通过剥夺解除死锁，造成损失可以在编译时（而不必在运行时）就进行检查Page212023/2/3第三章处理机调度与死锁处理机调度的基本概念

调度算法实时调度

多处理机系统中的调度产生死锁的原因和必要条件

预防死锁的方法死锁的检测与解除Page222023/2/3预防死锁的方法预防死锁系统安全状态利用银行家算法避免死锁Page232023/2/3产生死锁的必要条件互斥条件

进程对所分配到的资源进行排它性的使用请求和保持条件

进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又已被其他进程占有不剥夺条件进程已获得的资源在未使用完之前不能被剥夺环路等待条件在发生死锁时，必然存在一个进程--资源循环等待的环形链Page242023/2/3预防死锁摒弃“请求和保持”条件所有进程在开始运行之前必须一次性的申请整个运行过程所需的全部资源简单、易于实现、安全资源浪费严重进程延迟运行Page252023/2/3预防死锁摒弃“不剥夺”条件进程逐个地申请所需资源当一个已经保持了某些资源的进程申请新资源而不能得到满足时，必须放弃所有已保持的资源实现复杂、代价高昂延长了进程的周转时间，还增加了系统开销，降低了系统的吞吐量Page262023/2/3预防死锁摒弃“环路等待”条件系统将所有资源按类型分配序号并排队所有进程申请资源必须按序号递增的顺序资源利用率和系统吞吐量较高但在资源管理和资源申请方面仍有问题Page272023/2/3预防死锁存在问题：资源的需求顺序不等于序号，仍存在资源浪费。Page282023/2/3预防死锁摒弃“环路等待”条件其资源利用率和系统吞吐量，都有较明显的改善，但也存在下述严重问题：（1）资源所分配的序号，必须相对稳定，这就限制了新设备类型的增加。（2）进程使用各资源的顺序，与系统规定的顺序不同，造成对资源的浪费。（3）按规定次序申请资源的方法，必然会限制了用户简单、自主地编程。Page292023/2/3处理死锁的基本方法方法资源分配策略各种可能模式主要优点主要缺点预防Prevention保守的；宁可资源闲置（从机制上使死锁条件不成立，即摒弃三个必要条件）一次请求所有资源<条件2>适用于作突发式处理的进程；不必剥夺效率低；进程初始化时间延长剥夺次数过多；多次对资源重新起动不便灵活申请新资源资源剥夺<条件3>适用于状态可以保存和恢复的资源资源按序申请<条件4>避免Avoidance是“预防”和“检测”的折衷（在运行时判断是否可能死锁）寻找可能的安全的运行顺序不必进行剥夺使用条件：必须知道将来的资源需求；进程可能会长时间阻塞检测Detection宽松的；只要允许，就分配资源定期检查死锁是否已经发生不延长进程初始化时间；允许对死锁进行现场处理通过剥夺解除死锁，造成损失可以在编译时（而不必在运行时）就进行检查Page302023/2/3预防死锁的方法预防死锁系统安全状态利用银行家算法避免死锁Page312023/2/3产生死锁的原因进程推进顺序不当引起死锁P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1)P1Rel(R2)①②③④DPage322023/2/3系统安全状态安全状态在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待所谓安全状态，是指系统能按某种进程顺序(P1,P2,…，Pn)(称〈P1,P2,…,Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态Page332023/2/32.安全状态之例我们通过一个例子来说明安全性。假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：29P324P23510P1可用已分配最大需求进程415100109312存在安全序列：P2-P1-P3，系统处于安全状态。Page342023/2/33.由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。32404不安全状态Page352023/2/3预防死锁的方法预防死锁系统安全状态利用银行家算法避免死锁Page362023/2/33.6.3利用银行家算法避免死锁1.银行家算法中的数据结构(1)可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。

Page372023/2/3(2)最大需求矩阵Max。这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。

(3)分配矩阵Allocation。这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，表示进程i当前已分得Rj类资源的数目为K。

(4)需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need[i,j]=Max[i,j]–Allocation[i,j]Page382023/2/3

2.银行家算法设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1)如果Requesti[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

(2)如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。Page392023/2/3(3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j]:=Available[j]-Requesti[j];

Allocation[i,j]:=Allocation[i,j]+Requesti[j];

Need[i,j]:=Need[i,j]-Requesti[j];

(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。Page402023/2/33.安全性算法(1)设置两个向量：

①工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available;②Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false;当有足够资源分配给进程时，再令Finish[i]:=true。Page412023/2/3(2)从进程集合中找到一个能满足下述条件的进程：

①Finish[i]=false;②Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。

(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]:=Work[i]+Allocation[i,j];

Finish[i]:=true;

gotostep2;(4)如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。Page422023/2/34.银行家算法之例

假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-15所示。图3-15T0时刻的资源分配表2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMaxNeed[i,j]=Max[i,j]–Allocation[i,j]Page432023/2/3(1)T0时刻的安全性：图3-16T0时刻的安全序列truetruetruetruetrueFinish77532C54443B02210C10010B30112C40312B75322C44433B100710P07047P45213P110367P27205P3AAAAWork+AllocationAllocationNeedWork存在安全序列：P1-P3-P4-P2-P0，系统在T0时刻处于安全状态。Page442023/2/3(2)P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：

①Request1(1,0,2)≤Need1(1,2,2)

②Request1(1,0,2)≤Available1(3,3,2)Page452023/2/3③系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量，由此形成的资源变化情况如图3-15中的圆括号所示。Request1(1，0，2)2C3B11023C31024B21200C01001B32223C32025B404P4639P23707P0022P3123P1AAAAAvailableNeedAllocationMax322000032Page462023/2/3④再利用安全性算法检查此时系统是否安全。truetruetruetruetrueFinish75532C55443B20212C01010B03110C04312B55320C54433B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork图3-17P1申请资源时的安全性检查存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足P1资源分配请求。Page472023/2/3(3)P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查：

①Request4(3,3,0)≤Need4(4,3,1);

②Request4(3,3,0)≤Available(2,3,0)，让P4等待。/Page482023/2/3(4)P0请求资源：P0发出请求向量Request0(0，2，0)，系统按银行家算法进行检查：

①Request0(0,2,0)≤Need0(7,4,3);

②Request0(0,2,0)≤Available(2,3,0);Page492023/2/3③系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。Request0(0，2，0)723210030图3-18为P0分配资源后的有关资源数据不安全状态Page502023/2/3(5)P0请求资源：P0发出请求向量改为Request0(0,1,0)，系统按银行家算法进行检查：

①Request0(0,1,0)≤Need0(7,4,3);

②Request0(0,1,0)≤Available(2,3,0);Page512023/2/3③系统先假定可为P0分配资源，并修改Available,Allocation0和Need0向量，由此形成的资源变化情况如图所示。Request0(0,1,0)0C3B11003C31024B21220C01001B32223C32025B404P4639P22707P0022P3033P1AAAAAvailableNeedAllocationMax733220020Page522023/2/3④再利用安全性算法检查此时系统是否安全。truetruetruetruetrueFinish75532C55332B20212C02010B03110C03312B55320C53322B10367P27047P45302P17077P07205P3AAAAWork+AllocationAllocationNeedWork图3-17P1申请资源时的安全性检查存在安全序列：P1-P3-P4-P0-P2，系统处于安全状态，可以满足P0资源分配请求。Page532023/2/3第三章处理机调度与死锁处理机调度的基本概念

调度算法实时调度

多处理机系统中的调度产生死锁的原因和必要条件

预防死锁的方法

死锁的检测与解除Page542023/2/3死锁的检测与解除死锁的检测死锁的解除Page552023/2/3死锁的检测

允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行Page562023/2/3死锁的检测检测时机当进程等待时检测死锁其缺点是系统的开销大定时检测系统资源利用率下降时检测死锁Page572023/2/33.7死锁的检测与解除3.7.1死锁的检测

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：（1）保存有关资源的请求和分配信息；（2）提供一种算法，以利用这些信息来检测系统是否进入死锁状态。Page582023/2/3死锁的检测资源分配图(ResourceAllocationGraph)

用有向图描述进程的死锁优点：准确、形象系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例Page592023/2/33.7死锁的检测与解除

系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G=（N，E），具有下述形成的定义和限制：（1）N被分为两个互斥的子集，一组进程结点P=（p1，p2，…，pn），一组资源结点R={r1，r2，…，rn}，N=P∪R。在图3-19所示的例子中：1.资源分配图(ResourceAllocationGraph)Page602023/2/33.7死锁的检测与解除3.7.1死锁的检测1.资源分配图(ResourceAllocationGraph)图3-19每类资源有多个时的情况P={p1，p2}，R={r1，r2}，N={r1，r2}∪{p1，p2}P1P2r1r2Page612023/2/3死锁的检测资源分配图表示法:资源类:用方框表示（资源的不同类型）资源实例:用方框中的圆点表示（存在于每个资源中）进程:用圆圈中加进程名表示分配边：资源实例进程的一条有向边申请边：进程资源类的一条有向边P1P2r1r2获得申请Page622023/2/3死锁的检测死锁定理如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。Page632023/2/3死锁的检测死锁定理有环有死锁Page642023/2/3死锁的检测死锁定理有环无死锁Page652023/2/3死锁的检测死锁定理——资源分配图化简找出一个既不阻塞又非独立的进程结点pi，在顺利的情况下pi可获得资源而继续运行，再释放所有资源。消去pi所有的请求边和分配边，将其变为孤立结点再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边在进行一系列化简后若能消去图中所有的边，使所有进程结点成为孤立结点，则称该图是可完全简化的；否则是不可完全简化的已经证明：所有的化简顺序都得到相同的不可简化图。同样可以证明，S为死锁的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理Page662023/2/3死锁的检测死锁定理资源分配图的简化Page672023/2/3死锁的检测死锁检测中的数据结构可利用资源向量Available它表示了m类资源中每一类资源的可用数目把不占用资源的进程(向量Allocation:=0)记入L表中，即Li∪L从进程集合中找到一个Requ