OS8(死锁))

Lifang20101/37操作系统3.4死锁问题(DEADLOCK)P1033.4.1概述3.4.2死锁的预防3.4.3死锁的避免3.4.4死锁的检测3.4.5死锁的解除Lifang20102/37操作系统3.4.1概述死锁指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。1.死锁发生原因（1）竞争资源（2）进程推进顺序非法Lifang20103/37操作系统资源分类：可剥夺资源——CPU、主存非剥夺资源——磁带机、打印机永久性资源——可顺序重复使用的资源如：打印机等临时性资源——可以动态生成和消耗。如：硬件中断、消息等(1)竞争资源引起死锁Lifang20104/37操作系统...Request(B);aRequest(A);bRelease(A);Release(B);P2...Request(A);aRequest(B);bRelease(B);Release(A);P1死锁发生：双方都拥有部分资源，同时在请求对方已占有的资源。如次序：P1aP2aP1bP2bA.竞争非剥夺资源引起死锁Lifang20105/37操作系统...Receive(P1,Q);aSend(P1,R);bP2...Receive(P2,M);aSend(P2,N);bP1死锁发生：双方都等待对方去生成资源，如次序：P1aP2aB.竞争临时性资源引起死锁Lifang20106/37操作系统详见书P104图3-13,图3-14P1R2P2R1P1PP2s2s3s1从资源出发的箭头表示该资源已分配,如R1已分配给P1从进程出发的箭头表示进程正在申请资源,如P1正申请R2S1—P1:表示由P1产生的消息S1,即:S1隶属于P1P1—S2表示由P1要求接收消息S2,S2是另一个进程产生的。Lifang20107/37操作系统(2)进程推进顺序不当引起死锁ProcessQReleaseAReleaseBGetAGetBGetAGetBReleaseAReleaseBProcessPdeadlockinevitable123456P105图3-15Lifang20108/37操作系统2.死锁发生条件死锁的发生必须具备下列4个必要条件：–互斥：任一时刻只允许一个进程使用资源–请求和保持：进程在请求其余资源时，不主动释放已经占用的资源–非剥夺：进程已经占用的资源，不会被强制剥夺–环路等待：环路中的每一条边是进程在请求另一进程已经占有的资源。Lifang20109/37操作系统3.处理死锁的基本方法1.预防死锁：破坏四个必要条件中的一个或几个条件；易于实现，但会导致资源利用率和系统吞吐量降低2.避免死锁：用某种方法在资源动态分配过程中，防止系统进入不安全状态。实现有难度，但可获得较高的资源利用率和系统吞吐量。3.检测死锁：允许死锁发生。通过检测机构检测，然后采取措施，清除死锁。4.解除死锁：与检测配套完成。常通过撤销或挂起一些进程实现。Lifang201010/37操作系统3.4.2死锁的预防预防是采用某种策略，限制并发进程对资源的请求，使系统在任何时刻都不满足死锁的必要条件。预防死锁的3种策略：–摒弃“请求和保持”条件：要求所有进程一次性申请所需全部资源，保证不等待资源；简单、易于实现，但：降低了对资源的利用率，降低进程的并发程度；进程延迟运行；有可能无法预先知道所需资源；Lifang201011/37操作系统对于已经保持了某些资源的进程，当他再提出新的资源要求而不能立即满足时，必须释放已保持的所有资源，待以后需要时重新申请。–摒弃“环路等待”条件：把资源分类按顺序排列，所有进程对资源的请求必须严格按照资源序号递增的次序提出，保证不形成环路；改善了资源利用率和系统吞吐量，但：1.限制了新设备类型的增加2.进程申请资源的顺序很难与系统为资源分配的序号总保持一致。3.限制了用户简单、自主的编程-摒弃“不剥夺”条件：Lifang201012/37操作系统3.4.3死锁的避免用预防死锁的方法解决死锁问题，是通过增加了较强的限制条件来完成的，实现简单，但严重损害了系统的性能。避免死锁来解决死锁问题，可施加较弱的条件，获得令人满意的系统性能。避免死锁在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。Lifang201013/37操作系统1.系统的安全状态（见书107）如果系统能够按照某种顺序为每个进程分配其所需资源，直至最大需求，则当前状态为安全状态。否则…进程推进的顺序称为安全序列.可为资源分配提供借鉴：当有进程提出资源请求时，若分配后能够安全，则执行资源分配。否则不予分配，将进程阻塞Lifang201014/37操作系统安全状态举例进程最大需求To时刻获得资源状态(已分配)可用P11053P242P392假定系统有三个进程P1,P2,P3,12台磁带机。1、当前是否为安全状态?2、若进程2提出2个资源需求是否可以分配？3、若进程3提出1个资源需求是否可以分配？是，P2，P1，P3Lifang201015/37操作系统2.利用银行家算法避免死锁银行家算法（Dijkstra,1965）问题一个银行家把他的固定资金（capital）贷给若干顾客。只要不出现一个顾客借走所有资金后还不够，银行家的资金应是安全的。银行家需一个算法保证借出去的资金在有限时间内可收回。具体步骤如下：假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额。顾客的借款操作依次顺序进行，直到全部操作完成；银行家对当前顾客的借款操作进行判断，以确定其安全性（能否支持顾客借款，直到全部归还）；安全时，贷款；否则，暂不贷款。Lifang201016/37操作系统银行家算法的实现：可利用资源向量Available:m个元素的数组；最大需求矩阵Max：nm矩阵；分配矩阵Allocation:nm矩阵；需求矩阵Need:nm矩阵；设系统中有n个进程，m种资源：三个矩阵间的关系：Need[i,j]=Max[i,j]-Allocation[i,j]算法中用到的数据结构：Lifang201017/37操作系统银行家算法P109假设用Requesti[j]=k表示并发执行时进程i提出请求j类资源k个。系统按下述步骤进行检查：(1)如果Requesti≤Needi则继续以下检查，否则显示需求申请超出最大需求值的错误。(2)如果Requesti≤Available则继续以下检查，否则显示系统无足够资源，Pi阻塞等待。(3)系统试探性的把要求的资源分配给进程i并修改有关数据结构的值：Available=Available-Requesti；Allocationi=Allocationi+Requesti；Needi=Needi-Requesti；(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程i，以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。Lifang201018/37操作系统安全性算法:安全性算法执行步骤如下：A.初始化设置工作向量Work[m]表示系统可提供的各类资源数目，用以保护原数据结构有关值。Work=Available；设置完成标志向量Finish[n]。Finish[i]=false表示进程i尚末完成，如值为true则表示进程i已完成(可以顺利推进)。B.从进程集合n中找到一个能满足下述二个条件:Finish[i]=false和Necdi≤Work，如找到则执行步骤C，如找不到同时满足以上二条件的进程则执行步骤D。C.当进程i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：work=work+Allocationi；Finish[i]=true；转执行步骤B。D.如果所有的Finish[i]＝true，则表示系统处于安全状态，否则系统处于不安全状态。Lifang201019/37操作系统银行家算法例：P110假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型资源{A、B、C}，每一种资源的数量分别为10、5、7。各进程的最大需求、T0时刻资源分配情况如下所示。试问：1.T0时刻是否安全？2.P1请求资源Request1(1,0,2)是否允许？3.P4请求资源Request4(3,3,0)是否允许？4.P0请求资源Request(0,2,0)是否允许？MaxABCAllocationABCNeedABCAvailableABCP0P1P2P3P4753322902222433010200302211002743122600011431332Lifang201020/37操作系统332743122600011431010200302211002753322902222433P0P1P2P3P4AvailableABCNeedABCAllocationABCMaxABC资源情况进程T0时刻的资源分配表falsefalsefalsefalsefalse010200302211002743122600011431P0P1P2P3P4FinishWork+AllocationABCAllocationABCNeedABCWorkABC资源情况进程T0时刻的安全序列1、T0时刻的安全性133253225327433743753truetruetrue47531055true510551057trueP1P3P0P2P4Lifang201021/37操作系统332743122600011431010200302211002753322902222433P0P1P2P3P4AvailableABCNeedABCAllocationABCMaxABC资源情况进程T0时刻的资源分配表TrueTrueTrueTrueTrue532743745104710572002110023020101220114316007433325327437451047P1P3P4P2P0FinishWork+AllocationABCAllocationABCNeedABCWorkABC资源情况进程T0时刻的另一个安全序列1、T0时刻的安全性（2）Lifang201022/37操作系统P1发出请求向量Request(1,0,2),系统按银行家算法进行检查：2、P1请求资源发现可以找到一个安全序列{P1，P3，P4，P0，P2}，因此系统是安全的，可以立即将P1所申请的资源分配给它。（1）Request1(1,0,2)≤Need(1,2,2)（2）Request1(1,0,2)≤Available(3,3,2)（3）系统假定可为P1分配资源，并修改Available,Allocation1和Need向量。（4）检查此时系统是否安全。Lifang201023/37操作系统P4发出请求向量Request4(3,3,0),系统按银行家算法进行检查：（1）Request4(3,3,0)≤Need4(4,3,1)（2）Request4(3,3,0)≮Available(2,3,0),让P4等待。3、P4请求资源Lifang201024/37操作系统P0发出请求向量Request0(0,2,0),系统按银行家算法进行检查：210723020600011431030302302211002P0P1P2P3P4AvaiableABCNeedABCAllocationABC资源情况进程为P0分配资源后的有关资源数据4、P0请求资源（1）Request0(0,2,0)≤Need0(7,4,3)（2）Request0(0,2,0)≤Available(2,3,0)（3）系统暂时假定可为P0分配资源，并修改有关数据，下表所示。（4）进行安全性检查，发现可用资源Available(2,