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

Presentation on theme: "第八章 死锁 死锁的基本概念 死锁的解决方案 （预防，避免，检测及解除） 资源分配图."— Presentation transcript:

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

2 死锁的现象

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19 4. 死锁避免

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34 银行家算法

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

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

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

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

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

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

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

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

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

44 有环有死锁

45 有环无死锁

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

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

48 【作业：】 已分配的资源 最大需求量 A B C A B C P P P P P 剩余资源 A B C

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