计算机操作系统
第4章 死锁处理
1
本章知识点
4.1 死锁问题概述 4.2 死锁处理 4.3 哲学家用餐问题
2
内容
•何为死锁? •死锁的必要条件：四条 •死锁的预防：预先静态分配法,有序资源使用法 •死锁的避免：银行家算法 •死锁的检测：资源分配图 •死锁的恢复：强制性撤消进程,挂起和解挂机构
3
死锁的现象
19
4.2.1 死锁预防
破坏死锁的必要条件之一，消除产生死锁的可能性， 严格地防止死锁的出现。 死锁的必要条件: 互斥条件 不可抢占条件 部分分配条件 循环等待条件 防止死锁发生 控制多个进程互斥访问资源 强迫进程暂时释放资源 “预先静态分配法” “有序资源使用法”
对资源限制严格，使资源利用率和进程执行效率大大降低， 是以降低处理速度作为代价的。
没有环，就不会死锁。
15
资源分配图示例
R1 R3
•
•
P1
P2
P3
• •
R2
P2 R3 P3 R2 P2
cycle, deadlock
16
资源分配图示例
R1
• •
P2
P1
P3
P 1 R 1 P 3 R 2 P 1
cycle, no deadlock • •
P4
17
4.2 死锁处理
破坏产生死锁的四个必要条件之一, 死锁的预防:预先静态分配法,有序资源使用法 死锁的避免:银行家算法 或者允许死锁产生，但当死锁发生时能检测出死锁， 并有能力实现恢复。 死锁的检测:资源分配图 死锁的恢复:强制性撤消进程,挂起和解挂机构
18
4.2 死锁处理
系统不发生死锁，必须设法破坏产生死锁的四个必 要条件之一, 或者允许死锁产生，但当死锁发生时能检测出死锁， 并有能力实现恢复。
P1
P2
资源
R1
•
• •
R2
(2 个实例)
有向边Байду номын сангаас申请边：从进程外部指向资源。 分配边：从资源内部指向进程。
13
资源分配图示例
R1 R2
•
•
P1
P2
P3
• •
R3
• • •
R4
14
资源分配图
如果资源分配图出现环（有循环） • 如果每类资源只有一个实例，则定会死锁。 • 如果每类资源有多个实例，则可能会死锁。
20
4.2.1 死锁预防
1. 互斥 破坏第一个条件，使资源可以同时访问而不是互 斥使用，这是个简单的方法，但在进程并发执行 的情况下,往往有许多资源是不能同时访问的（写 操作），所以这种做法不是都可行的。
• 只能对可共享的资源（如只读文件）这样做。 • 不适合非共享资源，例如为写而打开的文件，打印机 等。
(c)
B
10
(d)
B 1 P 4（4） Q 2（1） R 3（6）
(e)
不安全状态
B 3 P 4（4） R 3（6）
(f)
32
课堂练习：
用银行家算法判断下述每个状态是否安全。如果一个状态是安全 的，说明所有进程是如何能够运行完毕的。如果一个状态是不安 全的，说明为什么可能出现死锁。 状态A 状态B ————————————— ————————————— 占有台数 最大需求 占有台数 最大需求 ————————————— ————————————— 用户1 2 6 用户1 4 8 用户2 4 7 用户2 3 9 用户3 5 6 用户3 5 8 用户4 0 2 可供分配的台数 2 可供分配的台数 1
26
4.2.2 死锁避免
1.避免启动新进程
执行一个新进程，当且仅当当前所有进程和新进程 的最大资源需求量之和能被系统满足时，才能启动一个新 的进程。 这个方法并不是最优的，因为它考虑的是最坏的情况， 即所有的进程都使用它们最大的资源需求量。
这会导致很多实际上可以运行的进程，被剥夺了运行 的权利 。
11
4.1.3 产生死锁的条件
所有四个条件必须同时满足才会出现死锁。 四个条件并不完全独立
• 循环等待条件意味着占有并等待条件 • 分开考虑这些条件是有用的（参见后面的 死锁防止）
12
资源分配图
死锁问题可以用称为系统资源分配图的有 向图进行更为精确地描述。
图形方式表示： 进程
Q进程
释放A
A申请
释放B
P和 Q 申请 A P和 Q 申请 B
获得A
B申请
获得B
获得A
释放A
获得B
释放B
P进程
9
A申请
B申请
图4.1进程推进的顺序
Q进程
.
释放A
P和 Q 申请 A
A申请
释放B 获得A
死锁 不可避免
P和 Q 申请 B
B申请
获得B
获得A
获得B
释放A
释放B
P进程
A申请
B申请
10
4.1.3 产生死锁的条件
优点： 对状态容易保留和恢复的资源较为方便。 缺点： 实现困难，恢复现场代价高； 导致过多的不必要抢占； 易导致循环重启。
23
4.2.1 死锁预防
4. 破坏“循环等待 ”条件
采用资源定序方法，将所有资源按类型线性排队，并按 递增规则编号。进程只能以递增方式申请资源，因而 不会导致循环等待。 优点：
Work：一个长度为m的工作数组。 Finish：一个长度为n状态标志数组，Finish[i]=true表示进程Pi能获 得足够的资源执行完毕，并能释放全部资源的状态。
35
银行家算法
当进程Pi发出资源请求Request[i,j]后：
1、如果Request[i,j] > C[i,j] - A[i,j], 表示出错；
资源的申请与分配逐步进行，比预分配策略的资源利用 率高； 易实现编译期间的检查； 无须执行时间，在系统设计阶段问题就已解决。
缺点：
严格限制资源的顺序性，不允许增加资源请求； 在使用资源的顺序与系统规定不一致时，资源利用率降 低； 不能抢占。
24
死锁预防示例—按序分配破坏循环等待
4
何为死锁
死锁 是由于进程间,相互竞争系统资源或通信,而引起的一种阻 塞现象。 如果操作系统不采取特别的措施，这种阻塞将永远存在，最 终可能导致整个系统处于瘫痪状态。
因此，死锁问题是操作系统中需要考虑的重要问题。
原因:
(1)系统资源不足; (2)进程推进的顺序不合适.
5
资源的概念
资源的分类：
下面是使用消耗型资源而发生死锁的例子：
P1 … Receive(P2, M)； … Send(P2, N)； P2 … Receive(P1, Q)； … Send(P1, R)；
如果Receive阻塞就会发生死锁。
实际应用中导致死锁的事件的组合很少出现， 有时会在很长的运行之后才出现死锁。
8
图4.1进程推进的顺序
34
多资源的银行家算法
现假定系统中有n个进程，m类资源
数据结构
Resource：系统拥有的资源数。 Available：系统当前可用的资源数，Av [j]=k,表明系统现 有k个Rj类资源。 Claim：一个n×m矩阵，每个进程对每类资源需求的最 大数，如果C[i,j] = k,表示进程Pi需要申请k个Rj类资源。 Allocation：一个n×m矩阵，当前分配给每个进程每类 资源的数目,A[i,j]=k，表示进程Pi当前已分得k个Rj类资 源。
21
4.2.1 死锁预防
2. 破坏“占用并等待”条件（部分分配）
采用资源的静态预分配策略，一次申请所有的资源。 优点：
简单安全，易于实施； 在进程的活动较单一时性能好； 无须抢占。
缺点：
资源利用率低； 启动进程慢，效率低； 有“饥饿”现象存在。
22
4.2.1 死锁预防
3. 破坏“非抢占”条件
方法1：若拥有某种资源的进程，在申请其他资源时遭到 拒绝，则它必须释放其占用的资源，以后再申请。 方法2：当一进程申请的资源正被其他进程占用时，可通 过操作系统抢占该资源，此方法在两个进程优先级相 同时，不能防止死锁。
1: CPU
5: floppy drive
10: printer
P1: 占有 CPU, 可以申请软驱和打印机 P2: 占有软驱，可以申请打印机但不能申请 CPU
P3: 占有软驱和打印机，要申请 CPU 必须先释放 打印机和软驱
25
4.2.2 死锁避免
预防: Prevention
破坏死锁必要条件之一,保证死锁不发生
2、如果Request[i,j] > Av[j] ，进程Pi等待； 3、否则，系统进行试探分配，并修改系统状态：
Av[j] ：= Av[j] - Request[i,j]
A[i,j]：= A[i,j] + Request[i,j] 4、系统调用安全性算法，判断试探性分配后的状态,是否安全状 态，若是，把资源j分配给Pi，否则，恢复原状态，Pi等待。 Av[j] ：= Av[j] + Request[i,j] A[i,j] ：= A[i,j] - Request[i,j]
27
4.2.2 死锁避免
2.避免分配资源
避免死锁算法也称作Banker(银行家)算法。
Banker算法的主要思想： 1. 2. 3. 4. 若进程Pi的申请超过了其申报的最大需求数，则报错； 若进程Pi的申请超过了可用资源数，则Pi必须等待； 系统暂时为进程Pi分配其所需要的资源，修改资源分配状 态； 调用安全算法检查系统当前状态，若导致不安全状态， 则推迟这种分配（为什么？） 。
“可重用资源”，“消耗型”资源 “可抢占”资源, “不可抢占”资源 “共享”资源, “独享”资源 资源的共同性质: