操作系统概述.pptx

第十讲第十讲 死锁死锁 目的与要求目的与要求：了解死锁的定义，掌握死了解死锁的定义，掌握死锁预防，了解死锁避免，死锁检测，死锁预防，了解死锁避免，死锁检测，死锁恢复的方法。锁恢复的方法。重点与难点重点与难点：死锁预防法则的使用。死锁预防法则的使用。作业作业：2121，22224.4 4.4 死锁死锁 4.4.1 4.4.1 死锁示例死锁示例 日常生活中的例子日常生活中的例子进程死锁的例子进程死锁的例子竞争外部设备竞争外部设备竞争辅存空间竞争辅存空间编程错的例子编程错的例子4.4.2 4.4.2 死锁定义及性质死锁定义及性质 死锁定义在一个进程集合中，若在一个进程集合中，若每个进程每个进程都在都在等待某些事件（指：等待某些事件（指：释放资源释放资源）的发）的发生，而这些事件又必须由生，而这些事件又必须由这个进程集这个进程集合合中的某些进程来产生，就称该进程中的某些进程来产生，就称该进程集合处于死锁状态集合处于死锁状态。死锁定义及性质死锁定义及性质出现死锁的系统必须同时满足下列四个必出现死锁的系统必须同时满足下列四个必要条件要条件互斥互斥：必须存在需要互斥使用的资源：必须存在需要互斥使用的资源 占有等待：占有等待：一定有占有资源而又等待其它资一定有占有资源而又等待其它资源的进程源的进程非剥夺：非剥夺：系统中进程占有的资源未主动释放系统中进程占有的资源未主动释放时不可以剥夺时不可以剥夺 循环等待：循环等待：进程集合进程集合P0,P1,P0,P1,Pn,Pn，PiPi等待等待Pi+1Pi+1，PnPn等待等待P0P0 死锁定义及性质死锁定义及性质资源分配图定义资源分配图定义资源分配图由如下部件组成：资源分配图由如下部件组成：如如果果各各类类资资源源数数为为1 1，则则系系统统出出现现死死锁锁的的充充要条件是资源分配图含圈要条件是资源分配图含圈 Pi.死锁研究的主要内容死锁研究的主要内容 死锁防止死锁防止死锁避免死锁避免死锁检测死锁检测死锁恢复死锁恢复 无死锁系统无死锁系统允许死锁、允许死锁、出现排除出现排除 4.4.3 4.4.3 死锁防止死锁防止 逻辑公式：逻辑公式：DC1C2C3C4DC1C2C3C4 C1C1 C2C2 C3C3 C4 C4 D D 破坏互斥占用条件破坏互斥占用条件 让资源都能共享使用（但有些资源必须让资源都能共享使用（但有些资源必须互斥使用）互斥使用）破坏占有等待条件破坏占有等待条件将将进进程程所所要要资资源源一一次次性性分分给给进进程程，要要么么没没分分到到一一个个资资源源，要要么么全全部部满满足足（适适合廉价资源的分配合廉价资源的分配,如外存空间分配）如外存空间分配）进进程程在在下下一一轮轮申申请请资资源源时时，释释放放所所占占的所有资源的所有资源 (用完一个再用下一个用完一个再用下一个)破坏非剥夺条件破坏非剥夺条件(用于内存管理、用于内存管理、CPUCPU管理管理等等)当进程当进程PiPi申请申请riri类资源时，若有则分类资源时，若有则分配，若没有则剥夺（释放）配，若没有则剥夺（释放）PiPi占有的所占有的所有资源；有资源；当进程当进程PiPi申请申请riri类资源时，若有则分类资源时，若有则分配，若无则剥夺（淘汰）占有配，若无则剥夺（淘汰）占有riri类资源类资源进程所占的进程所占的riri类资源分配给类资源分配给PiPi；或看占；或看占用用riri类资源的类资源的PkPk处于什么状态，若处于处于什么状态，若处于等资源状态，则剥夺其资源，否则让等资源状态，则剥夺其资源，否则让PiPi等待等待,等于剥夺等于剥夺PiPi的资源。的资源。破坏循环等待条件破坏循环等待条件 采采用用资资源源顺顺序序分分配配方方法法：给给每每类类资资源源编编号号，进进程程只只能能按按序序号号由由小小到到大大的的顺顺序申请资源，若不满足则拒绝分配。序申请资源，若不满足则拒绝分配。反证：若出现循环等待，则必会有反证：若出现循环等待，则必会有小序号资源序号小序号资源序号 大序号资源序号。大序号资源序号。4.4.4 4.4.4 死锁避免死锁避免银行家算法银行家算法(在系统处理资源申请时，判断在系统处理资源申请时，判断在满足申请时，系统是否还处于安全状态？是在满足申请时，系统是否还处于安全状态？是则满足本次资源申请则满足本次资源申请 ，否则拒绝。依此引导进，否则拒绝。依此引导进程运行次序程运行次序)单单类类资资源源系系统统安安全全状状态态定定义义：设设系系统统中中有有n n个个进进程程，若若存存在在一一个个序序列列P1P1，2 2n n使使得得Pi(iPi(i1 1，2 2n)n)以以后后还还需需要要的的资资源源可可以以通通过过系系统统现现有有资资源源加加上上所所有有Pj(jPj(ji)i)占占有有的的资资源源来来满满足足 ，则则称称这这个个系系统统处处于于安安安安全全全全状状状状态态态态,序序列列，n n称为称为安全序列安全序列安全序列安全序列。举例举例 设银行家有设银行家有1010万贷款，万贷款，P,Q,RP,Q,R分别需要分别需要8,3,98,3,9万元搞项目（假设任何人满足资金总额后万元搞项目（假设任何人满足资金总额后都会归还所有贷款），如果都会归还所有贷款），如果P P已申请到了已申请到了4 4万，万，Q Q要申请要申请2 2万，显然，如果满足万，显然，如果满足Q Q的申请，的申请，有安全序列有安全序列 /。但如果但如果R R要申请要申请4 4万，显然，如果满足万，显然，如果满足R R的申的申请，则不存在安全序列。请，则不存在安全序列。扩展的银行家算法描述扩展的银行家算法描述 n n：系统中的进程个数。：系统中的进程个数。m m：系统中的资源类型数。：系统中的资源类型数。Available(1:m):Available(1:m):Available(1:m):Available(1:m):现有资源向量现有资源向量现有资源向量现有资源向量。Available(j)=kAvailable(j)=k表示有表示有k k个未分配的个未分配的j j类资源。类资源。Max(1:n,1:m):Max(1:n,1:m):Max(1:n,1:m):Max(1:n,1:m):资源最大申请量矩阵资源最大申请量矩阵资源最大申请量矩阵资源最大申请量矩阵。Max(i,j)=kMax(i,j)=k表示第表示第i i个进程对第个进程对第j j类资源的最大申请量为类资源的最大申请量为k.k.Allocation(1:n,1:m):Allocation(1:n,1:m):Allocation(1:n,1:m):Allocation(1:n,1:m):资源分配矩阵资源分配矩阵资源分配矩阵资源分配矩阵。Allocation(i,j)=kAllocation(i,j)=k表示进程表示进程i i已占有已占有k k个个j j类资源。类资源。Need(1:n,1:m):Need(1:n,1:m):Need(1:n,1:m):Need(1:n,1:m):进程以后还需要的资源矩阵。进程以后还需要的资源矩阵。进程以后还需要的资源矩阵。进程以后还需要的资源矩阵。Need(i,j)=kNeed(i,j)=k表示第表示第i i个进程以后还需要个进程以后还需要k k个第个第j j类类资源。显然资源。显然Need=Max-AllocationNeed=Max-AllocationRequest(1:n,1:m):Request(1:n,1:m):Request(1:n,1:m):Request(1:n,1:m):进程申请资源矩阵进程申请资源矩阵进程申请资源矩阵进程申请资源矩阵。Request(i,j)=kRequest(i,j)=k表示进程表示进程i i申请申请k k个第个第j j类资源。类资源。资源分配程序的工作过程：资源分配程序的工作过程：当进程提出资源申请时，系统首先检当进程提出资源申请时，系统首先检查该进程对资源的申请量是否超过其最大查该进程对资源的申请量是否超过其最大需求量及系统现有资源能否满足进程需要。需求量及系统现有资源能否满足进程需要。若能则进一步检查：若把资源分给该进程若能则进一步检查：若把资源分给该进程系统能否处于安全状态。若安全则分配，系统能否处于安全状态。若安全则分配，否则置该进程为等待资源状态。否则置该进程为等待资源状态。为简单起见，记为简单起见，记AiAi为为A(i,1),A(i,2)A(i,1),A(i,2)A(i,m)A(i,m)。其中。其中A A为为nmnm矩阵。矩阵。定义长度为定义长度为m m的向量的向量 X X、Y Y间的关系为：间的关系为：XYXY当且仅当当且仅当X(i)Y(i)(i=1,2X(i)Y(i)(i=1,2m)m)1 1、如果、如果RequestRequesti iNeedNeedi i则报错返回。则报错返回。2 2、如果、如果RequestRequesti i Available,Available,则进程则进程i i进入等待进入等待 资源状态，返回。资源状态，返回。3 3、假设进程、假设进程i i的申请已获准，于是修改系统状态：的申请已获准，于是修改系统状态：Available=Available-RequestAvailable=Available-Requesti i AllocationAllocationi i=Allocation=Allocationi i+Request+Requesti i Need Needi i=Need=Needi i-Request-Requesti i 4 4、调用安全状态检查算法。、调用安全状态检查算法。设进程设进程i i申请资源，申请资源向量为申请资源，申请资源向量为RequestRequesti i，则有如下的资源分配过程：，则有如下的资源分配过程：（续）（续）5 5、若系统处于安全状态，则将进程、若系统处于安全状态，则将进程i i申请的资源申请的资源分配给进程分配给进程i i，返回。，返回。6 6、若系统处于不安全状态，则进程、若系统处于不安全状态，则进程i i进入等待资进入等待资源状态，并恢复系统状态后返回：源状态，并恢复系统状态后返回：Available=Available+RequestAvailable=Available+Requesti i AllocationAllocationi i=Allocation=Allocationi i-Request-Requesti i NeedNeedi i=Need=Needi i+Request+Requesti i安全状态检查算法安全状态检查算法：设设Work(1:m)Work(1:m)为临时工作向量。初始时为临时工作向量。初始时Work=Available.Work=Available.令令N=1N=1，2 2nn1 1、寻找、寻找jNjN使其满足使其满足NeedNeedj jWork,Work,若不存若不存 在这样的在这样的j j则转则转(3)(3)2 2、Work=Work+AllocationWork=Work+Allocationj j N=N-j,N=N-j,转转(1)(1)3 3、如果、如果N N为空则返回为空则返回(系统安全系统安全)；如果；如果N N 不为空不为空则返回则返回(系统不安全系统不安全)。举例Allocation Max RequestAllocation Max Request availableavailableP1 1 2 4 2 5 8 1 2 1 1 3 3P1 1 2 4 2 5 8 1 2 1 1 3 3P2 0 3 3 4 4 4 3 0 0P2 0 3 3 4 4 4 3 0 0P3 4 1 1 5 4 4 1 2 2P3 4 1 1 5 4 4 1 2 2如果如果p1p1先申请，无安全序列。先申请，无安全序列。如果如果p3p3申请，可有安全序列申请，可有安全序列或或。4.4.5 4.4.5 死锁检测死锁检测资源分配图的简化过程：资源分配图的简化过程：1.1.在图中找一个进程顶点在图中找一个进程顶点i,Pii,Pi的请求边的请求边 均能立即满足。均能立即满足。2.2.若找到这样的若找到这样的PiPi则将与则将与i i相连的边全部相连的边全部 删去，转删去，转(1)(1)；否则化简过程结束。；否则化简过程结束。采用化简资源分配图的方法可以检测系采用化简资源分配图的方法可以检测系统中有无进程处于死锁状态。统中有无进程处于死锁状态。如果化简后所有的进程顶点都成了孤立如果化简后所有的进程顶点都成了孤立点，则称该图可完全化简；否则称该图点，则称该图可完全化简；否则称该图是不可完全化简的。是不可完全化简的。系统中有死锁的充分必要条件是资源分系统中有死锁的充分必要条件是资源分配图不可完全化简。配图不可完全化简。死锁检测算法死锁检测算法 设设Work(1:m)Work(1:m)为临时工作向量。初始时为临时工作向量。初始时Work=Available.Work=Available.令令N=1N=1，2 2nn1 1寻找寻找jNjN使其满足使其满足RequestRequestj jWork,Work,若若不存在这样的不存在这样的j j则转则转(3)(3)2 2Work=Work+AllocationWork=Work+Allocationj j N=N-j,N=N-j,转转(1)(1)3 3如果如果N N为空则无死锁；如果为空则无死锁；如果N N不为空不为空则则有死锁，有死锁，N N就是处于死锁状态的进程集就是处于死锁状态的进程集合合4.4.6 4.4.6 死锁恢复死锁恢复检测出死锁后的处理检测出死锁后的处理破坏循环等待（杀掉有关进程）破坏循环等待（杀掉有关进程）4.4.7 4.4.7 死锁的综合处理死锁的综合处理 把系统中的资源分成几大类，整体上采用把系统中的资源分成几大类，整体上采用资源顺序分配法，再对每类资源根据其特点资源顺序分配法，再对每类资源根据其特点选择最适合的方法。选择最适合的方法。例如：例如：（1 1）主存、处理机）主存、处理机 -剥夺法剥夺法 （2 2）辅存）辅存 -预分配法预分配法 （3 3）其他）其他 -死锁检测死锁检测交通死锁的示例让路！让路！让路！让路！进程A进程B 申请输入设备申请输出设备 申请输出设备申请输入设备 释放输入设备释放输出设备 释放输出设备释放输入设备 如果执行次序为：进程A进程B.，则发生死锁。输入设备输出设备BA输入设备输出设备占有占有等待等待 A在干什么？B在干什么？竞争外设死锁示例ABCDELMNOPQFGHIJKAABBCCDDFGHILLMMNNOOFGHISPOOLing系统死锁示例输出井进程B进程C 满啦！不够！不够！不够！进程A