《操作系统》PPT电子课件教案- 第七章 死锁.ppt

第七章 死 锁,1 死锁的产生 2 资源分配图及死锁定理 3 预防死锁 4 避免死锁 5 检测与解除死锁, 死锁的产生,假设系统中有这样一个资源集合（，），其中（，）为临界资源；又设有进程集合（， , ），其中每个进程都至少要求使用中的某两个资源 ，且以下面的方式要求资源：,即每个进程pi都是先申请ri,后申请rimodn+1。 如果进程pi在进程pimodn+1到达l之前到达l,那么pi就能获得它所要求的资源ri和rimodn+1,从而可以继续运行下去。但是,由于各进程都是异步前进的,如果没有一个进程pi 先于进程pimodn+1到达l之前到达l,即所有进程同时处于l1l之间,此时任一进程到达l都将被阻塞,它们都在等待本集合中另一进程已占用但又无法释放的资源。于是进程集合p陷入了死锁。,假设资源（如内存）有个分配单位，进程集合（，）共享，且和满足关系式。如果各进程对的申请和释放都以一个分配单位进行，并且均采取如下方式：,当有个进程均处于之间时，由于的个单位已全部被占用，它们中的任一个到达时均要被阻塞。而其余个进程将在处被阻塞。于是进程集合因共享资源而陷入死锁。 在进程通讯中曾说过，若不适当地使用、操作容易导致死锁。例如在生产崐者与消费者算法中，如果把生产者进程的两个操作执行次序调换一下，即先执行p(mutex)，后执行p(empty)。那么，当缓冲区已满且消费者不在临界区中，即有empty.v=0及mutexv=1。 若此时生产者希望进入临界区，它先执行p(mutex)，使mutex v=0，当它执行p(empty)时被阻塞。以后,当消费者执行p(mutex)也被阻塞。于是两个进程无限止地相互等待对方来唤醒自己，陷入了死锁,产生死锁的四个必要条件： （）互斥条件：进程访问的是临界资源，即一个资源一次只能被一个进程所 使用。 （）请求和保持条件：一进程在请求新的资源的同时，保持对某些资源的占有。 （）不剥夺条件：一个资源仅能被占有它的进程所释放，而不能被其他进程剥夺。 （）环路等待条件：存在一个进程的环路，环路中每一个进程占有着某个或 某些资源，又在等待被环路中的另一个进程占有的资源。, 资源分配图及死锁定理,首先，我们引入用来表示资源使用状态的资源分配图rag(resources allocation graph)。一个可定义为一个二 元组，即（，），其中是节点集合（），是有向边集合（）。又包含两个子集合，（，），子集 p，p2，p是进程集合，每个元素p表示一个进程，在图形中用矩形框表示；子集，是资源集合 ，每个元素表示一类资源，在图形中用圆圈表示，某类资源可能有多个 分配单位，这在图形中用圆圈中的小圆圈表示。边集中的每个元素是p或，这也可用有序偶表示，即，或，其中 p,rjr。,若，则在图形中存在一条从节点指向节点的有向边，称作请求边，它表示进程请求分配资源或中的一个单位；若，则在图形中存在一条从节点指向节点的有向边，称作分配边，它表示资源或中的一个单位已分配给了进程。 当进程请求分配资源或的一个单位时，一条请求边被加入中，只要这个请求是可满足的，则该请求边便立即转换成分配边；当进程释放了某个资源时，则删除中相应的分配边。,图- 示例,集合、分别为：,资源单位数为：,进程状态为： 进程p已占用了类资源的一个单位，正在等待再获得类资源 ； 进程p已占用了类资源和一个单位的类资源，且正在等待获得r3资源。 进程p3已占用了r3类资源。,这里假定，在某个时刻系统中有一组进程使用一组资源的状态为s, 是状态所对应的图，于是 （）若中未出现任何环路，则为非死锁状态，或称安全状态。 （）若中出现了环路，且该环路中的各资源均为单单位资源（只有一个分配单位），则为死锁状态。换言之，由若干单单位资源构成的环路，是为死锁状态的充分必要条件。 （）若中出现了环路，但该环路中的各资源不全为单单位资源，则不一定是死锁状态。换言之，由若干不全为单单位资源构成的环路，是为死锁状态的必要条件但非充分条件。,化简方法如下： （）从中找一个只有分配边的，或虽有请求边但该请求边能立刻转换为分配边（即该请求能立即得到满足）的非孤立节点，然后消去的全部有向边，即释放进程所占用的全部资源，使之成为孤立节点。 （）假定是进程节点释放的某个资源节点，则另一进程节点关于的请求边就可转换成分配边，即进程释放的资源可分配给进程所使用；如果经一系列转换后只有分配边，则再使成为孤立节点。,（）在实施一系列化简后，若可消去中全部有向边，使全部进程节点都成为孤立节点，则称该图是可完全化简的，否则称该图是不可完全化简的。显然，不可完全化简的中必定存在环路。 于是有死锁定理的另一种描述：状态为死锁状态的充分必要条件是当且仅当 状态的是不可完全化简的。,图- 的化简,（）预防死锁：这种方法从四个死锁必要条件出发，通过设置一些限制来破坏其中的至少一个条件，从而防止死锁的发生。 （）避免死锁：这种方法不是预先加上各种限制条件以预防产生死锁的可能 性，而是允许有逼近死锁的可能性，但当接近死锁状态时，采取一些有效的措施加以避免，使死锁不致于最终发生。 （）检测及解除死锁：它允许在系统运行过程中发生死锁，但一旦发生后便能立即检测出来，然后采取适当措施解除死锁。, 预 防 死 锁,.防止“请求和保持”条件的出现 系统要求任一进程必须预先申请它所需要的全部资源，而且仅当该进程的全部资源要求都能得到满足时，系统才给予一次性分配，然后启动该进程运行。进程在整个生存期间，不再请求新的资源。因此，“请求和保持”条件不会出现，死锁也就不可能发生。,防止“不剥夺”条件的出现 在允许进程动态申请资源的前提下，规定一个进程在请求新资源不能立即得到满足而变为等待状态之前，它必须释放已占有的全部资源；若需要，再重新申请新资源和已释放的资源。换言之，一个进程在使用某资源过程可以暂时放弃该资源，即允许其他进程剥夺使用该资源，从而破坏了“不剥夺”条件的出现。 该策略实现起来相当困难，为了保护在自动放弃资源时的现场以及以后的恢复现场，需要付出很高的代价。特别是可能出现进程反复地申请和释放某些资源而被无限延迟执行的现,.防止“环路等待”条件的出现 采用资源顺序使用法，其基本思想是：把系统中所有资源按类型线性排队，并按递增规则赋予每类资源以唯一的编号。例如输入机，打印机，磁带机，磁盘机等等。进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配。由于在任何时刻，总有一个进程占有较高编号的资源，它继续请求资源的要求必然可获满足，因此，一定不会出现环路等待条件。, 避 免 死 锁,. 系统资源分配状态,在某个时刻，系统的资源分配状态（）定义为：系统中的可用资源数和已分配资源数以及各进程对资源的最大需求量的当前情况。此后，如果系统能够按某种次序为每个进程分配它们所需的资源，并满足各进程的最大需求而不会造成死锁，那么称状态（）是安全的。更形式化的定义可以是：系统状态（）是安全的，仅当存在一个安全的进程序列，。,序列，是安全的是指，对于每一个进程（，）其资源剩余需求数（即的最大资源需求数减去它的已占用数）均可由系统当前的可用资源数与所有其它进程（）当前已占用的资源数之和来满足，即便进程的所需资源不能立即被满足，但在所有（）运行完毕后一定可满足；当完成后，也可获得所需资源；最终该序列中的每个进程的资源需求均可获得满足而完成各自的运行任务。如果不存在这样的进程序列，则称系统状态（）是不安全的。,假定系统中有单位总数为的某类资源，三个进程、和共享且它们的最大需求数分别为、。 设在时刻，系统关于的分配状态（）如图-（）所示。,图- 同类资源分配状态举例,图- 同类资源的分配过程举例,. 避免死锁算法,在银行家算法中要用到下列数据结构，令是系统中的进程数，是资源类数。 可用资源向量a(available) 向量a的长度为m，向量元素aj(j=1,2,m)，为系统中资源类rj的当前可用数。 最大需求矩阵m(max) m是一个m的矩阵，矩阵元素m(i,j)为进程pi关于资源类rj的最大需求数，每个进程必须预先申报。 资源占用矩阵u(used) u也是一个的矩阵，元素ui,j是进程pi关于资源类rj的当前占用数。 剩余需求矩阵n(need) n也为矩阵，元素ni,j是进程pi还需要的资源类rj的单位数，显然有：ni,j=mi,j-ui,j。,为了简化对算法的表述，对上述数据结构采用如下简记法： 令x和y 均是长度为的向量，说x，当且仅当对任意的（，）有；，则且。 对于的矩阵，表示的第个行向量，。,银行家算法描述如下： 令是长度为的向量，称为进程的资源请求向量，元素（，）是进程希望请求分配的资源类的单位数。当进程向系统提交一个资源请求向量时，系统调用银行家算法执行下述工作： （）若，则有（），即进程请求的资源类的单位数大于它申报的最大需求数，故请求无效并作出错处理；否则继续下一步骤。,（）若，即系统不能满足当前请求，则进程必须等待；否则继续下一步骤。 (3)系统进行假分配，即对资源分配状态作如下修改：,（）调用安全算法检查修改后的现行状态是否安全。安全算法描述如下 ： 设向量（）和（ ），和的长度分别为和，并作如下初始化：=，（，）。 找到这样的一个（），有 如果这样的不存在，则转去执行步骤。, 执行：,转去执行步骤。,对任意的（，），若，则现行状态是安全的，否则是不安全的。 （）如果假分配后资源分配状态仍是安全的，就实施真分配以满足进程的当前资源请求；否则系统拒绝分配，恢复假分配前的原资源分配状态，并令进程等待。,设有五个进程，共享三类资源，和，且有，和。若在时刻关于它们的状态（）如图-（）所示，（）是安全状态，有安全序列，。 现假定进程的当前请求向量为（，），即请求分配资源的一个单位和资源的两个单位。对此，银行家算法的执行过程如下：,图- 不同类资源分配状态举例,（）有，即（，）（，），继续下一步。 （）有，即（，）（，），继续下一步。 （）进行假分配：,（）执行安全算法：,.于是进程的当前请求可满足，系统实施真分配。 对于图-（）的新状态，假定进程提出请求（，），虽然，但执行银行家算法后可知如果按该请求实施分配将导致系统处于不安全状态，故应拒绝分配以避免发生死锁。, 检测与解除死锁,. 检测死锁,基于资源分配图与死锁定理的检测死锁算法。 该算法用到下列数据结构，它们与银行家算法中用到的数据结构非常类似。 可用资源向量 长度为系统中的资源类 数，元素（，）表示中资源节点的当前空闲单位数。,资源分配矩阵 元素，（ ，）表示中资源节点指向进程节点 的分配边，若，k，则表示有条这种分配边。 资源请求矩阵 元素，表示中进程节点指向资源节点的请求边，若，则表示有条这样的请求边。,该算法的执行过程实际上就是化简的过程，算法描述如下： （）设置长度分别为和的向量和，并对它们初始化：；对任意的（，），若则false，否则true。 （）找到这样一个进程节点号，有 ，且 即在中存在这样的进程节点，它有分配边但无请求边，或有请求边但它的请求边可立即转换成分配边，换言之，进程的资源请求可立即得到满足。 若不存在这样的，则转步骤（