第八章 死锁 死锁的基本概念 死锁的解决方案 （预防，避免，检测及解除） 资源分配图

死锁的现象

一、死锁的基本概念 1.死锁的定义 一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程 死锁（Deadlock） 饥饿（Starvation）

关于死锁的一些结论 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃 参与死锁的进程最少是两个 （两个以上进程才会出现死锁） 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃

2. 资源 永久性资源：可以被多个进程多次使用（可再用资源） * 可抢占资源 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请--分配--使用--释放”模式

3. 产生死锁的四个必要条件 互斥使用（资源独占） 不可强占（不可剥夺） 请求和保持（部分分配，占有申请） 循环等待

1) 互斥使用（资源独占） 一个资源每次只能给一个进程使用 2) 不可强占（不可剥夺） 资源申请者不能强行的从资源占有者手中夺取资源，资源只能由占有者自愿释放

3) 请求和保持 （部分分配，占有申请） 一个进程在申请新的资源的同时保持对原有资源的占有 （只有这样才是动态申请，动态分配）

4) 循环等待 存在一个进程等待队列 {P1 , P2 , … , Pn}, 其中P1等待P2占有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路

二、死锁的解决方案 1. 产生死锁的例子 申请不同类型资源产生死锁 P1： P2： … … 申请打印机 申请扫描仪 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪 P2： … 申请扫描仪 申请打印机 使用 释放打印机 释放扫描仪

申请同类资源产生死锁（如内存） 设有资源R，R有m个分配单位，由n个进程P1,P2,…,Pn（n > m）共享。假设每个进程对R的申请和释放符合下列原则： * 一次只能申请一个单位 * 满足总申请后才能使用 * 使用完后一次性释放

m=2，n=3 资源分配不当导致死锁产生

2. 解决死锁的方法 不考虑此问题（鸵鸟政策） 不让死锁发生 静态策略：设计合适的资源分配算法，不让死锁发生 动态策略： 让死锁发生

3. 死锁预防 定义： 在系统设计时确定资源分配算法，保证不发生死锁 具体的做法是破坏产生死锁的四个必要条件之一

死锁预防 破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请

死锁预防 破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配

死锁预防 破坏“循环等待”条件 采用资源有序分配法： 把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配 （哲学家就餐问题）

破坏“循环等待”条件 例如：1，2，3，…，10 P1： 申请1 申请3 申请9 … P2： 申请2 申请5 P3 …… P10

4. 死锁避免

A申请 B申请 释放A 释放B 获得A 获得B Q进程 P 和 Q 申请 A 死锁 不可避免 申请 B P进程

Q进程 释放A 释放B 获得A 获得B A申请 B申请 P 和 Q 申请 A 申请 B P进程

死锁避免定义 定义： 在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配

安全状态与不安全状态 安全状态： 如果存在一个由系统中所有进程构成的安全序列P1，…Pn，则系统处于安全状态

死锁避免 安全序列： 一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处于安全状态 (安全状态一定是没有死锁发生的)

安全状态与不安全状态 不安全状态:不存在一个安全序列，不安全状态一定导致死锁

银行家算法 n：系统中进程的总数 m：资源类总数 Available: ARRAY[1..m] of integer; Max: ARRAY[1..n,1..m] of integer;

银行家算法 Allocation: ARRAY[1..n,1..m] of integer; Need: Request:

银行家算法 简记符号： Available Max[i] Allocation[i] Need[i] Request[i]

银行家算法 当进程pi提出资源申请时，系统执行下列步骤： （1）若Request[i]≤Need[i],转（2）； 否则错误返回 （2）若Request[i]≤Available, 转（3）；否则进程等待

(3）假设系统分配了资源，则有： Available:=Available-Request[i]; Allocation[i]:= Allocation[i]+Request[i]; Need[i]:=Need[i]-Request[i] 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，进程等待

银行家算法 为进行安全性检查，定义数据结构： Work:ARRAY[1..m] of integer; Finish:ARRAY[1..n] of Boolean;

银行家算法 安全性检查的步骤： (1) Work:=Available; Finish:=false; (2) 寻找满足条件的i： a.Finish[i]=false; b.Need[i]≤Work; 如果不存在，则转(4)

银行家算法 (3) Work:=Work+Allocation[i]; Finish[i]:=true; 转(2) (4) 若对所有i,Finish[i]=true,则系统处于安全状态，否则处于不安全状态

银行家算法

5.死锁的检测与解除 死锁检测： 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行

死锁的检测与解除 检测时机： 当进程等待时检测死锁 （其缺点是系统的开销大） 定时检测 系统资源利用率下降时检测死锁

死锁的检测与解除 死锁检测算法 * 每个进程和资源指定唯一编号 * 设置一张资源分配表 记录各进程与其占用资源之间的关系 * 设置一张进程等待表 记录各进程与要申请资源之间的关系

死锁的检测与解除 死锁检测算法 资源分配表 进程等待表 r1 p2 p1 r1 r2 p5 p2 r3 r3 p4 p4 r4 r4 p1 资源分配表 进程等待表 r1 p2 p1 r1 r2 p5 p2 r3 r3 p4 p4 r4 r4 p1 … … … …

死锁的解除 重要的是以最小的代价恢复系统的运行。方法如下： 1）重新启动 2）撤消进程 3）剥夺资源 4）进程回退

三、资源分配图 用有向图描述进程的死锁 准确、形象 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例

资源分配图 二元组G=（V，E） V：结点集，分为P，R两部分 P={p1,p2,…,pn} R={r1,r2,…,rm} (pi,rj)或(rj,pi)

资源分配图 表示法 资源类（资源的不同类型） 用方框表示 资源实例（存在于每个资源中） 用方框中的黑圆点表示 进程 用圆圈中加进程名表示

资源分配图 分配边： 资源实例进程的一条有向边 申请边： 进程资源类的一条有向边

有环有死锁

有环无死锁

资源分配图 死锁定理 如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁 如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件

资源分配图 资源分配图化简： 1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点 2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边

【作业：】 已分配的资源 最大需求量 A B C A B C P1 0 1 0 7 5 3 P2 2 0 0 3 2 2 P3 3 0 2 9 0 2 P4 2 1 1 2 2 2 P5 0 0 2 4 3 3 剩余资源 A B C 3 3 2

问题:此状态是否为安全状态，如果 是, 则找出安全序列 在此基础上 P2 申请（1，0，2）能否分配？为什么？ P5 申请（3，3，0）能否分配？为什么？ P1 申请（0，2，0）能否分配？为什么？