处理机调度与死锁1

处理机调度与死锁Operating System3.4 死锁死锁定义多个进程在运行过程中因争夺资源而造成的僵局称为死锁，当进程处于这种僵持状态时，若无外力作用，它们都将无法向前推进3.5.1 产生死锁的原因竞争资源进程间推进顺序非法竞争资源引起死锁共享资源数目难以满足各进程的需求时，诸进程会竞争资源，导致死锁♋资源分类：可剥夺资源和非可剥夺资源；永久性资源和临时性资源۩竞争非剥夺资源：进程对非剥夺资源的长期占用或争夺导致死锁产生۩竞争临时性资源：临时性资源由一个进程产生，被另一个进程使用很短时间后失效死锁环路（竞争非剥夺资源）方块代表非剥夺资源，圆圈代表进程；箭头从进程指向资源时，表示进程申请该资源；箭头从资源指向进程时，表示该资源已经分配给该进程；若形成环路，则出现死锁死锁环路（竞争临时资源）若S1、S2、S3均为临时资源，分别由进程P1、P2、P3生成，且P1申请S3、P2申请S1、P3申请S2，则按照下述顺序进行时会产生不同结果♋P1:release(S1);request(S3);P2:release(S2);request(S1);P3:release(S3);request(S2);♋P1:request(S3);release(S1);P2:request(S1);release(S2);P3:request(S2);release(S3);进程推进顺序不当引起死锁进程运行过程中请求和释放资源的顺序不当会导致死锁进程运行具有异步性特征，使得进程推进顺序可能有合法与非法两种情况产生♋合法推进顺序：不会产生死锁的推进顺序♋非法推进顺序：可能导致死锁的推进顺序进程推进顺序导致死锁产生死锁的必要条件互斥条件进程对得到的资源进行排他性使用，只有本身完成对资源的使用才释放请求和保持条件某进程无法得到所请求的资源时阻塞自身且不放弃对已获取的其他资源的控制权不剥夺条件进程已获得资源在自身没有主动释放时不可被他人剥夺环路等待条件发生死锁时，必然存在一个进程－资源的环形等待链，即进程集合{P0,P1,…,P n }中的P0等待P1占用的资源，P1等待P2占用的资源，……，P n等待P0占用的资源产生死锁的必要条件设某系统中现有20个进程竞争65个同类资源，其申请方式是逐个进行的，一旦某进程完成工作就立即释放所有占用的资源，且每个进程最多使用3个该类资源，则这个系统是否会在该资源上产生死锁？产生死锁的必要条件设某系统中有一类资源的总数目为8，它们由N个进程竞争，每个进程最多需要3台该资源，则N为多少时不会产生死锁？处理死锁的基本方法预防死锁避免死锁检测死锁解除死锁预防死锁通过设置限制条件破坏产生死锁的四个必要条件中的一个或几个来预防死锁的产生该方法实现简单，应用广泛，但限制条件的过于严格会导致系统资源利用率和系统吞吐量的降低避免死锁在资源动态分配过程中使用某种方法防止系统进入不安全状态以避免死锁发生该方法只需采取较弱的限制，便可获得较高的资源利用率和系统吞吐量，但实现较麻烦检测死锁此方法允许系统运行过程中产生死锁，但系统中设置的检测机构可以及时检测出死锁的发生，并精确确定与其有关的进程和资源，以便采取适当的措施清除死锁解除死锁当检测机构发现系统中存在死锁时，须将进程从死锁状态中解脱出来♋挂起或撤销某些进程以回收资源，以便将其分配给等待这些资源的其他阻塞进程，使之能够转为就绪态，进而获得执行死锁的检测和解除措施实现难度最大，但系统资源利用率和吞吐量较好3.5.2 预防和避免死锁的方法预防死锁产生死锁的四个条件中，互斥条件是系统自身需求，不可改变♋摒弃“请求和保持”条件♋摒弃“不剥夺”条件♋摒弃“环路等待”条件避免死锁使系统始终处于安全状态来避免死锁产生摒弃“请求和保持”条件采用此方法的系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程中所需的全部资源♋摒弃请求条件：进程运行时不必再提出资源申请♋摒弃保持条件：只要有一个资源不能得到，其他资源也不会分配给它，在等待期间并不占有资源优点：简单易行、安全性高缺点：资源严重浪费、进程延迟执行摒弃“不剥夺”条件采用此方法的OS规定进程逐个提出对资源的要求，当已经保持了一定资源的进程无法立即得到新申请的资源时，必须释放它所保持的其他所有资源，待以后需要时再进行申请此方法实现复杂且代价较大对当前资源的被迫释放可能会导致前期工作的失效或前后两次运行信息的不连续性，反复的申请与释放资源会延误进程执行，增加系统开销摒弃“环路等待”条件采用此方法的OS将所有资源按类型线性排队，并赋予不同序号，所有进程对资源的请求必须严格按照资源序号递增的次序提出，以避免环路出现此方法中总有一个进程占据了较高序号的资源，以后它所申请的资源必然是空闲的，因此可以正常进行摒弃“环路等待”条件此方法对资源利用率和系统吞吐量都有较明显改善缺点♋各类资源的序号相对稳定，限制了新类型设备的增加♋作业使用各类型资源的顺序与系统规定的顺序不符，造成资源浪费♋增加用户编程复杂性避免死锁在避免死锁方法中，允许进程动态的申请资源，但每次系统进行资源分配前，应先计算此次资源分配是否会导致系统进入不安全状态，若不会产生不安全，则为其分配所需资源；否则，令进程等待安全状态系统能按某种进程的安全序列为每个进程P i分配其所需资源，直至满足每个进程对资源的最大需求，使其全部能顺利完成；若不存在这样的序列，则称系统处于不安全状态处于不安全状态的系统可能会产生死锁，避免死锁就是避免系统进入不安全状态如果某状态是非安全的，仅表示资源管理器“失去控制”，死锁与否将由进程以后的活动来决定安全状态Eg:系统中有进程P1、P2、P3和12台磁带驱动器，各进程对此资源的需求和分配情况如下表所示，此时按照安全序列< P2, P1, P3 >分配资源可以保证各进程都顺利完成安全状态分配资源时若不按照安全序列的顺序，可能会导致OS由安全状态进入不安全状态eg：在上例中，为进程P3分配一台磁带机，系统进入不安全状态，此时再也找不到一个安全序列避免死锁的利器——银行家算法银行家算法中的数据结构♋可利用资源向量Available۩含有m个元素的数组，每个元素代表一类可利用资源的数目，其初值为系统中该类资源的全部可用数目，“资源R j的当前可用数目为K”可表示为Available[j]=K ♋最大需求矩阵Max۩一个n*m的矩阵，表示n个进程分别对m类资源的最大需求量，“进程i需要R j类资源的最大数目为K”可以表示为Max[i,j]=K避免死锁的利器——银行家算法银行家算法中的数据结构♋分配矩阵Allocation۩n*m的矩阵，表示当前n个进程分别获得的m类资源的数目，“进程i当前已分得R j类资源的数目为K”可以表示为Allocation[i,j]=K♋需求矩阵Need۩n*m的矩阵，表示n个进程还需要的各类资源数目，“进程i还需要R j类资源K个”可以表示为Need[i,j]=K这些数据结构存在下列关系Need[i,j]=Max[i,j]-Allocation[i,j]银行家算法设Request i是进程P i的请求向量，“进程P i需要K个R j类资源”表示为Request i[j]=K。

当P i发出资源请求后，系统按下述步骤进行检查1）若Request i[j] ≤Need[i,j]，转向步骤2；否则进程所需资源数已超过它所宣布的最大值，出错2）若Request i[j] ≤Available[j]，转向步骤3；否则表示系统中无足够资源，进程P i需要等待银行家算法3）系统尝试把资源分配给进程P i，并按照下式修改数据结构中的相应数值：Available[j]:= Available[j]- Request i[j]Allocation[i,j]:= Allocation[i,j] + Request i[j]Need[i,j]:= Need[i,j]-Request i[j]4) 系统执行安全性检查，若系统在此次分配后处于安全状态，正式将资源分配给请求进程；否则，本次分配作废，恢复原来的系统状态，进程P i等待安全性算法算法描述♋设置向量W ork:array[1,2,…,m] of integerFinish:array[1,2,…,n] of boolean安全性算法算法步骤1）Work[j]:=Available[j]，Finish[j]:=false2）寻找满足Finish[j]=false和Need[i,j]≤Work[j]的进程，若找到转向3，否则转向43）当进程P i获得资源后，可顺利执行到完成并释放分配到的资源，其执行序列为Work[j] := Work[j] + Allocation[i,j];Finish[j] := true;go to step 2;4）若所有进程的Finish[j]=true均满足，则系统处于安全状态，否则为不安全状态银行家算法说明性实例设系统中有五个进程｛P, P1, P2, P3, P4}和三类资源{A,B,C},各资源数量分别为10、5、7，在T0时刻的资源分配如下银行家算法说明性实例T0时刻的安全性：使用安全性算法对T0时刻的资源情况分析可知存在安全序列｛P1, P3, P4, P2, P0}，故系统安全银行家算法说明性实例设T1时刻有Request1(1,0,2)，按银行家算法要求可知1）Request1(1,0,2) ≤Need1(1,2,2)2）Request1(1,0,2) ≤Available1(3,3,2)3）按P1请求尝试性分配资源后，资源变化如后表所示4）再利用安全性算法检查此时系统是否安全银行家算法说明性实例T1时刻的系统安全性：存在安全序列｛P1, P3, P4, P2, P0}，因此可以将P1申请的资源分配给它银行家算法说明性实例设T2时刻有Request4(3,3,0)，按银行家算法要求可知1）Request4(3,3,0) ≤Need4(4,3,1)2）Request4(3,3,0) ＞Available1(2,3,0)，P4等待银行家算法说明性实例设T时刻有Request0(0,2,0)按银行家算法要求可知31）Request0(0,2,0) ≤Need1(7,4,3)2）Request1(0,2,0) ≤Available1(2,3,0)3）按P0请求尝试性分配资源后，资源变化如后表所示4）再利用安全性算法检查此时系统是否安全银行家算法说明性实例T时刻的系统安全性：不存在安全序列，因此系统不会为它分配资源3结论安全序列并不唯一银行家算法的每一轮运算应该包括:根据进程提出的资源请求判断是否可以尝试为其分配资源、安全性检查、真正分配资源并纪录新的资源分配状态作业：将P0发出的请求向量改为Request0(0,1,0) ，系统是否可以分配资源？死锁的检测与解除使用检测和解除死锁机制的OS应♋保存资源请求和分配信息♋提供死锁检测算法回顾♋资源分配图资源分配图该图用来精确的描述死锁问题图中有一个节点集合V和一个边的集合E，其中V又分为表示系统活动进程的集合P和表示系统所有资源类型的集合R有向边P i→R j表示进程P i已经申请了资源类型R j的一个实例，并正在等待资源，称为申请边；有向边R j→P i表示资源R j的一个实例已经分配给进程P i，称为分配边资源分配图图中的方块和圆圈分别表示资源和进程，资源的实例以方块中的圆点表示资源分配图死锁定理若资源分配图中没有环出现，则不会产生进程死锁；如果有环，可能存在死锁♋若每个资源类型均只有一个实例，有环一定有死锁♋若每个资源类型有多个实例，有环并不意味着已经出现了死锁资源分配图进程P3申请资源R2，此时系统中有两个最小环，进程P1、P2、P3死锁资源分配图本图中存在环，但是没有死锁，进程P4不必等待，可以顺利执行至任务完成并释放资源，最终打破环路死锁检测算法在资源分配图中找到一个即占用资源又不阻塞的进程结点P i，当该进程顺利完成后，释放资源，图中与之相连的所有边均可消去，使之成为孤立结点寻找因获取进程P i释放出的资源而得以执行的进程，继续上一步操作，直至无法再消除若此时图中所有结点均为孤立结点，则称该图为可完全简化的，否则为不可完全简化的死锁检测算法死锁定理可表述为“当且仅当某状态的资源分配图是不可完全简化的时，才有可能产生死锁”死锁检测算法的数据结构与银行家算法类似♋Available：表示各类资源的可用数目♋L：记录不占用资源的进程死锁检测算法算法步骤♋将不占用资源的进程计入L♋从进程集合中找到一个Request≤Work的进程，将其资源分配图简化，释放出资源，i增加可用资源数量Work:=Work+Allocation i，并将该进程计入L中♋若所有的进程都计入了L，表明该图可完全简化，不会发生死锁；否则，该系统状态将发生死锁死锁检测算法的应用死锁检测算法的应用取决于两个因素♋死锁发生的频率：经常发生死锁的系统需要经常调用检测算法♋死锁影响的进程数量：参与死锁循环的进程数量可能会不断增加经常性的调用死锁检测算法会增加系统计算开销，另一个不太昂贵的方法是在一个不频繁的时间间隔中调用或由人工方式确定激活策略死锁解除检测到死锁后可以采用多种措施解除♋进程终止۩终止所有死锁进程：代价大，被终止进程的前期工作必须放弃۩一次终止一个进程直到取消死锁循环为止：系统开销大，每次终止进程时都要调用死锁检测算法确定进程是否仍处于死锁♋资源抢占۩逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止，此方法需要考虑选择最小代价牺牲品、如何回滚至安全状态、如何避免饥饿等问题教学重点知道处理机调度的分类熟练掌握常用调度算法思想及其性能评价方式知道实时调度算法掌握死锁产生的必要条件。