1
第 4章 死锁处理
本章知识点：
? 4.1 死锁问题概述
? 4.2 死锁处理
? 4.3 哲学家用餐问题
2
4.1 死锁问题概述
死锁是由于进程间相互竞争系统资源或
通信而引起的一种阻塞现象。如果操作
系统不采取特别的措施，这种阻塞将永
远存在，最终可能导致整个系统处于瘫
痪状态。因此，死锁问题是操作系统中
需要考虑的重要问题 。
3
4.1.1 可重用资源
下面是一个使用可重用资源而发生死锁的例子。两个
进程 P1和 P2竞争必须互斥访问的磁盘文件 D和磁带机 T，
程序重复地执行以下操作：
P1 P2
repeat repeat
… …
Request(D)； Request(T)；
… …
Request(T)； Request(D)；
… …
Release(T)； Release(D)；
… …
Release(D)； Release(T)；
… …
forever forever
4
4.1.2 消耗型资源
下面是使用消耗型资源而发生死锁的例子：
P1 P2
… …
Receive(P2,M)； Receive(P1,Q)；
… …
Send(P2,N)； Send(P1,R)；
如果 Receive阻塞就会发生死锁 。
5
4.1.3 产生死锁的条件
系统产生死锁有四个必要条件,
? 互斥 。
? 占用并等待
? 非强占
? 循环等待
6
4.2 死锁处理
为了使系统不发生死锁，必须设法破坏
产生死锁的四个必要条件之一,或者允许
死锁产生，但当死锁发生时能检测出死
锁，并有能力实现恢复。
7
4.2.1 死锁预防
死锁预防是设法至少破坏产生死锁的必
要条件之一（除互斥条件之外），从而
消除产生死锁的任何可能性，严格地防
止死锁的出现。但方法过于保守，对资
源限制严格，使资源利用率和进程执行
效率大大降低，它是以降低处理速度作
为代价的。
8
4.2.1 死锁预防
1,互斥
可用第 3章介绍的解决互斥问题的思想和
技术来解决有关由于互斥条件不满足而
产生的死锁问题。
9
4.2.1 死锁预防
2,破坏“占用并等待”条件
采用资源的静态预分配策略, 一次申请所有的资
源 。
优点：
?简单安全, 易于实施；
?在进程的活动较单一时性能好；
?无须抢占 。
缺点：
?资源利用率低；
? 启动进程慢, 效率低；
? 有, 饥饿, 现象存在 。
10
4.2.1 死锁预防
3,破坏“非抢占”条件
方法 1：若拥有某种资源的进程在申请其他资源时遭到
拒绝，则它必须释放其占用的资源，以后若有必要可
再次申请上述资源。方法 2：当一进程申请的资源正被
其他进程占用时，可通过操作系统抢占该资源，此方
法在两个进程优先级相同时，不能防止死锁。
优点：
?对状态容易保留和恢复的资源较为方便 。
缺点：
?实现困难, 恢复现场代价高；
? 导致过多的不必要抢占；
? 易导致循环重启 。
11
4.2.1 死锁预防
4,破坏, 循环等待, 条件
采用资源定序方法, 将所有资源按类型线性排队, 并按
递增规则编号 。 进程只能以递增方式申请资源, 因而
不会导致循环等待 。
优点：
?资源的申请与分配逐步进行, 比预分配策略的资源利用
率高；
?易实现编译期间的检查；
?无须执行时间, 在系统设计阶段问题就已解决 。
缺点：
?严格限制资源的顺序性, 不允许增加资源请求；
? 在使用资源的顺序与系统规定不一致时, 资源利用率
降低；
? 不能抢占 。
12
4.2.2 死锁避免
死锁避免方法并不是严格限制产生死锁
必要条件的存在，只是防止系统进入不
安全状态，从而避免死锁的发生。死锁
避免算法就是避免系统进入不安全状态
的算法。银行家（ Banker） 算法是最著
名的死锁避免算法。
13
4.2.2 死锁避免
1.避免启动新进程
执行一个新进程，当且仅当当前所有进
程和新进程的最大资源需求量之和能被系
统满足时，才能启动一个新的进程。这个
方法并不是最优的，因为它考虑的是最坏
的情况，即所有的进程都使用它们最大的
资源需求量。这会导致很多实际上可以运
行的进程被剥夺了运行的权利 。
14
4.2.2 死锁避免
2.避免 分配资源
避免分配资源也称作 Banker(银行家 )算法。
Banker算法的主要思想：
1,若进程 Pi的申请超过了其申报的最大需求数, 则
报错；
2,若进程 Pi的申请超过了可用资源数, 则 Pi必须等
待；
3,系统暂时为进程 Pi分配其所需要的资源, 修改资
源分配状态；
4,调用安全算法检查系统当前状态, 若导致不安全
状态, 则推迟这种分配 。
15
4.2.2 死锁避免
优点：
?无须抢占；
?比死锁预防限制少, 允许更多的进程并发执行 。
缺点：
?必须知道未来的资源请求信息, 要预先声明资
源的最大需求量；
?进程必须是独立的, 其执行顺序不受同步要求
的约束；
? 资源和进程的数目必须固定；
? 可能导致进程的长时间阻塞 。
16
4.2.3 死锁检测
基本思想：在某时刻 t,求得系统中各类可利
用资源的数目向量 w(t),对于系统中的一组
进程 {p1,p2,…p i,…p n },找出那些对各类资
源请求数目均小于系统现在所拥有的各类资
源数目的进程。这样的进程能够获得它们所
需要的全部资源并运行结束。当它们运行结
束后释放所占有的全部资源，从而使可用资
源数目增加，这样的进程加入到可运行结束
的进程序列 L中，然后对剩下的进程再作上述
考查。如果一组进程 {p1,p2,…p n }中有几个
进程不属于序列 L中，那么它们会被死锁。
17
4.2.3 死锁检测
优点：
? 不会推迟进程的启动；
? 在线处理比较便利 。
缺点：
? 丢失了固有的抢占；
? 执行检测算法需要一定的 CPU开销 。
18
4.2.4 死锁恢复
一旦检测到死锁，就要有恢复的方法，
恢复死锁的基本方法是剥夺。通常恢复
方法是人工抽去一些作业，释放它们占
有的资源，再重新启动系统。
19
4.2.5 处理死锁的综合方法
处理死锁的方法有多种，它们各有优缺
点，在不同的环境中使用不同的方法就
比只用一种方法要好得多。
? 对资源进行分类
? 对不同类型资源，使用资源定序的方法。
? 对同一类资源，使用最佳的处理方法。
20
4.3 哲学家用餐问题
哲学家用餐问题 是一个死锁和饥饿的典型问题，
也是一大类并发控制所面临的问题。
方法 1,每个哲学家先拿其左边的筷子然后再
拿右边的筷子。哲学家用完餐后再将筷子放回
原来的位置。这种解决方法将导致死锁。
方法 2,为避免死锁，可以只允许不超过 4个哲
学家同时用餐。这样就至少有一个哲学家可以
得到两根筷子 。这个方法可避免死锁和饥饿。
21
The end
Thanks!
第 4章 死锁处理
本章知识点：
? 4.1 死锁问题概述
? 4.2 死锁处理
? 4.3 哲学家用餐问题
2
4.1 死锁问题概述
死锁是由于进程间相互竞争系统资源或
通信而引起的一种阻塞现象。如果操作
系统不采取特别的措施，这种阻塞将永
远存在，最终可能导致整个系统处于瘫
痪状态。因此，死锁问题是操作系统中
需要考虑的重要问题 。
3
4.1.1 可重用资源
下面是一个使用可重用资源而发生死锁的例子。两个
进程 P1和 P2竞争必须互斥访问的磁盘文件 D和磁带机 T，
程序重复地执行以下操作：
P1 P2
repeat repeat
… …
Request(D)； Request(T)；
… …
Request(T)； Request(D)；
… …
Release(T)； Release(D)；
… …
Release(D)； Release(T)；
… …
forever forever
4
4.1.2 消耗型资源
下面是使用消耗型资源而发生死锁的例子：
P1 P2
… …
Receive(P2,M)； Receive(P1,Q)；
… …
Send(P2,N)； Send(P1,R)；
如果 Receive阻塞就会发生死锁 。
5
4.1.3 产生死锁的条件
系统产生死锁有四个必要条件,
? 互斥 。
? 占用并等待
? 非强占
? 循环等待
6
4.2 死锁处理
为了使系统不发生死锁，必须设法破坏
产生死锁的四个必要条件之一,或者允许
死锁产生，但当死锁发生时能检测出死
锁，并有能力实现恢复。
7
4.2.1 死锁预防
死锁预防是设法至少破坏产生死锁的必
要条件之一（除互斥条件之外），从而
消除产生死锁的任何可能性，严格地防
止死锁的出现。但方法过于保守，对资
源限制严格，使资源利用率和进程执行
效率大大降低，它是以降低处理速度作
为代价的。
8
4.2.1 死锁预防
1,互斥
可用第 3章介绍的解决互斥问题的思想和
技术来解决有关由于互斥条件不满足而
产生的死锁问题。
9
4.2.1 死锁预防
2,破坏“占用并等待”条件
采用资源的静态预分配策略, 一次申请所有的资
源 。
优点：
?简单安全, 易于实施；
?在进程的活动较单一时性能好；
?无须抢占 。
缺点：
?资源利用率低；
? 启动进程慢, 效率低；
? 有, 饥饿, 现象存在 。
10
4.2.1 死锁预防
3,破坏“非抢占”条件
方法 1：若拥有某种资源的进程在申请其他资源时遭到
拒绝，则它必须释放其占用的资源，以后若有必要可
再次申请上述资源。方法 2：当一进程申请的资源正被
其他进程占用时，可通过操作系统抢占该资源，此方
法在两个进程优先级相同时，不能防止死锁。
优点：
?对状态容易保留和恢复的资源较为方便 。
缺点：
?实现困难, 恢复现场代价高；
? 导致过多的不必要抢占；
? 易导致循环重启 。
11
4.2.1 死锁预防
4,破坏, 循环等待, 条件
采用资源定序方法, 将所有资源按类型线性排队, 并按
递增规则编号 。 进程只能以递增方式申请资源, 因而
不会导致循环等待 。
优点：
?资源的申请与分配逐步进行, 比预分配策略的资源利用
率高；
?易实现编译期间的检查；
?无须执行时间, 在系统设计阶段问题就已解决 。
缺点：
?严格限制资源的顺序性, 不允许增加资源请求；
? 在使用资源的顺序与系统规定不一致时, 资源利用率
降低；
? 不能抢占 。
12
4.2.2 死锁避免
死锁避免方法并不是严格限制产生死锁
必要条件的存在，只是防止系统进入不
安全状态，从而避免死锁的发生。死锁
避免算法就是避免系统进入不安全状态
的算法。银行家（ Banker） 算法是最著
名的死锁避免算法。
13
4.2.2 死锁避免
1.避免启动新进程
执行一个新进程，当且仅当当前所有进
程和新进程的最大资源需求量之和能被系
统满足时，才能启动一个新的进程。这个
方法并不是最优的，因为它考虑的是最坏
的情况，即所有的进程都使用它们最大的
资源需求量。这会导致很多实际上可以运
行的进程被剥夺了运行的权利 。
14
4.2.2 死锁避免
2.避免 分配资源
避免分配资源也称作 Banker(银行家 )算法。
Banker算法的主要思想：
1,若进程 Pi的申请超过了其申报的最大需求数, 则
报错；
2,若进程 Pi的申请超过了可用资源数, 则 Pi必须等
待；
3,系统暂时为进程 Pi分配其所需要的资源, 修改资
源分配状态；
4,调用安全算法检查系统当前状态, 若导致不安全
状态, 则推迟这种分配 。
15
4.2.2 死锁避免
优点：
?无须抢占；
?比死锁预防限制少, 允许更多的进程并发执行 。
缺点：
?必须知道未来的资源请求信息, 要预先声明资
源的最大需求量；
?进程必须是独立的, 其执行顺序不受同步要求
的约束；
? 资源和进程的数目必须固定；
? 可能导致进程的长时间阻塞 。
16
4.2.3 死锁检测
基本思想：在某时刻 t,求得系统中各类可利
用资源的数目向量 w(t),对于系统中的一组
进程 {p1,p2,…p i,…p n },找出那些对各类资
源请求数目均小于系统现在所拥有的各类资
源数目的进程。这样的进程能够获得它们所
需要的全部资源并运行结束。当它们运行结
束后释放所占有的全部资源，从而使可用资
源数目增加，这样的进程加入到可运行结束
的进程序列 L中，然后对剩下的进程再作上述
考查。如果一组进程 {p1,p2,…p n }中有几个
进程不属于序列 L中，那么它们会被死锁。
17
4.2.3 死锁检测
优点：
? 不会推迟进程的启动；
? 在线处理比较便利 。
缺点：
? 丢失了固有的抢占；
? 执行检测算法需要一定的 CPU开销 。
18
4.2.4 死锁恢复
一旦检测到死锁，就要有恢复的方法，
恢复死锁的基本方法是剥夺。通常恢复
方法是人工抽去一些作业，释放它们占
有的资源，再重新启动系统。
19
4.2.5 处理死锁的综合方法
处理死锁的方法有多种，它们各有优缺
点，在不同的环境中使用不同的方法就
比只用一种方法要好得多。
? 对资源进行分类
? 对不同类型资源，使用资源定序的方法。
? 对同一类资源，使用最佳的处理方法。
20
4.3 哲学家用餐问题
哲学家用餐问题 是一个死锁和饥饿的典型问题，
也是一大类并发控制所面临的问题。
方法 1,每个哲学家先拿其左边的筷子然后再
拿右边的筷子。哲学家用完餐后再将筷子放回
原来的位置。这种解决方法将导致死锁。
方法 2,为避免死锁，可以只允许不超过 4个哲
学家同时用餐。这样就至少有一个哲学家可以
得到两根筷子 。这个方法可避免死锁和饥饿。
21
The end
Thanks!
