admin 管理员组文章数量: 887017
1、概述
1.1 死锁
死锁是多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
1.2 死锁产生的原因和条件
原因：（1）竞争资源；（2）进程间推进顺序非法
条件:（1）互斥条件；（2）请求和保持条件;（3）不剥夺条件；（4）环路等待条件
1.3 死锁的处理策略
（1）死锁预防
破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。
- 互斥条件：所有资源允许共享，则系统不会进入死锁状态，但是打印机等临界资源不适用
- 请求和保持条件：采用预先静态分配方法，即进程运行前一次申请完所需要的资源，在资源未满足前，进程不执行，进程一旦执行，不再提出其他资源请求，这样就不会死锁
- 不剥夺条件：当一个已经保持了某些不可剥夺资源的进程，请求新资源得不到满足时，它必须释放已经保持的所有资源，待以后需要时重新申请
- 环路等待条件（循环等待）：为了破坏循环等待条件，可釆用顺序资源分配法。
（2）死锁避免（银行家算法）
在资源的动态分配中，用某种方法防止系统进入不安全状态，从而避免死锁
（3）死锁的检测及解除
无需釆取任何限制性措施，允许进程在运行过程中发生死锁。通过系统的检测机构及时 地检测出死锁的发生，然后采取某种措施解除死锁，通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。
死锁解除的主要方法有：
1) 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
3) 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。
2、银行家算法
主要思想是避免系统进入不安全状态。在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，如果有，则先进行分配，并对分配后的新状态进行安全性检查。如果新状态安全，则正式分配上述资源，否则就拒绝分配上述资源。这样，它保证系统始终处于安全状态，从而避免死锁现象的发生。
（1）具体数据项
最大需求矩阵Max
需求矩阵Need
分配矩阵Allocation
可利用资源矢量Available
存在关系：Need = Max-Allocation
（2）银行家算法描述
设request是进程Pi的请求矢量，当P发出资源请求后，系统按照以下步骤进行检查：
- 如果满足Request[i,j] <= Need[i, j],则继续以下步骤，否则，认为它所需资源数已超过宣布的最大值
- 如果满足Request[i,j] <= Available[i, j]，则继续以下步骤，否则，尚无足够资源，Pi需等待。
- 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
Available[j] = Available[j] - Requesti[j];
Allocation[i, j] = Allocation[i, j] + Requesti[ j];
Need[i, j] = Need[i, j] - Requesti[j];
- 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的分配作废，恢复原来的资源分配状态，让进程Pi等待。
（3）系统安全状态（安全状态算法）
安全状态是指系统能按某种进程推进顺序( P1, P2, ..., Pn)，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称 P1, P2, ..., Pn 为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。
工作矢量Work；它表示系统可提供给进程继续运行所需的各类资源数目，它含有所个元素，在执行安全算法开始时，Work=Available;
Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时 Finish[i]=false；当有足够资源分配给进程 Pi 时，再令 Finish[i]=true。
3、死锁实例
3.1 银行家算法实例
case 1：系统有五个进程P1、P2、P3、P4、P5，三种资源R1、R2、R3，在T0时刻的状态如图所示，回答下列问题：
| 已分配资源数量（Allocation） | 最大资源需求数量（Max） | |||||
| R1 | R2 | R3 | R1 | R2 | R3 | |
| P1 | 0 | 0 | 1 | 0 | 0 | 1 |
| P2 | 2 | 0 | 0 | 2 | 7 | 5 |
| P3 | 0 | 0 | 3 | 6 | 6 | 5 |
| P4 | 1 | 1 | 5 | 4 | 3 | 5 |
| P5 | 0 | 3 | 3 | 0 | 6 | 5 |
| R1 | R2 | R3 | |
| 剩余资源数（Available） | 3 | 3 | 0 |
（1）T0时刻是否为安全状态？为什么？
（2）若这时P4请求资源（1,2,0），是否实施资源分配？，为什么？
（3）在上面基础上，若进程P3请求资源（0,1,0），是否能实施资源分配？为什么？
答：（1）T0时刻是安全状态，序列为P1->P4->P5->P2->P3
| Allocation | Need（Max-Allocation） | Available+Allocation(初始（3,3,0）) | 状态 | |||||||
| R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | Finish | |
| P1 | 0 | 0 | 1 | 0 | 0 | 0 | 3 | 3 | 1 | True（核对Need矩阵，P4，320(need)<331(Available)） |
| P4 | 1 | 1 | 5 | 3 | 2 | 0 | 4 | 4 | 6 | True（核对Need矩阵,P5，032(need)<446(Available)） |
| P5 | 0 | 3 | 3 | 0 | 3 | 2 | 4 | 7 | 9 | True（核对Need矩阵,P2，075(need)<479(Available)） |
| P2 | 2 | 0 | 0 | 0 | 7 | 5 | 6 | 7 | 9 | True（核对Need矩阵,P3，662(need)<679(Available)） |
| P3 | 0 | 0 | 3 | 6 | 6 | 2 | 6 | 7 | 12 | end，最后资源6,7,12 |
（2）P4请求（1,2,0），则Request=（1,2,0），
比较：Request<=Need(1,2,0<=3,2,0)
Request<=Available(1,2,0<=3,3,0)
更新：Need = Need-Request（3,2,0-1,2,0=2,0,0）
Available = Available -Request（3,3,0-1,2,0=2,1,0）
Aollcation = Aollcation+Request（1,1,5+1,2,0=2,3,5）
| 已分配资源数量（Allocation） | 最大资源需求数量（Max） | Need | |||||||
| R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | |
| P1 | 0 | 0 | 1 | 0 | 0 | 1 | |||
| P2 | 2 | 0 | 0 | 2 | 7 | 5 | |||
| P3 | 0 | 0 | 3 | 6 | 6 | 5 | |||
| P4 | 2 | 3 | 5 | 4 | 3 | 5 | 2 | 0 | 0 |
| P5 | 0 | 3 | 3 | 0 | 6 | 5 | |||
| R1 | R2 | R3 | |
| 剩余资源数（Available） | 2 | 1 | 0 |
安全序列为P1->P4->P5->P2->P3
| Allocation | Need（Max-Allocation） | Available+Allocation(初始（3,3,0）) | 状态 | |||||||
| R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | Finish | |
| P1 | 0 | 0 | 1 | 0 | 0 | 0 | 2 | 1 | 0 | True（核对Need矩阵，P4，200(need)<210(Available)） |
| P4 | 2 | 3 | 5 | 2 | 0 | 0 | 4 | 4 | 6 | True（核对Need矩阵,P5，032(need)<446(Available)） |
| P5 | 0 | 3 | 3 | 0 | 3 | 2 | 4 | 7 | 9 | True（核对Need矩阵,P2，075(need)<479(Available)） |
| P2 | 2 | 0 | 0 | 0 | 7 | 5 | 6 | 7 | 9 | True（核对Need矩阵,P3，662(need)<679(Available)） |
| P3 | 0 | 0 | 3 | 6 | 6 | 2 | 6 | 7 | 12 | end，最后资源6,7,12 |
（3）在上面基础上，P3请求（1,1,0），则Request=（1,1,0），
比较：Request<=Need(1,1,0<=6,6,2)
Request<=Available(1,1,0<=2,1,0)
更新：Need = Need-Request（6,6,2-1,1,0=5,5,2）
Available = Available -Request（2,1,0-1,1,0=1,0,0）
Aollcation = Aollcation+Request（0,0,3+1,1,0=1,1,3）
| 已分配资源数量（Allocation） | 最大资源需求数量（Max） | Need | |||||||
| R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | |
| P1 | 0 | 0 | 1 | 0 | 0 | 1 | |||
| P2 | 2 | 0 | 0 | 2 | 7 | 5 | |||
| P3 | 1 | 1 | 3 | 6 | 6 | 5 | 5 | 5 | 2 |
| P4 | 2 | 3 | 5 | 4 | 3 | 5 | 2 | 0 | 0 |
| P5 | 0 | 3 | 3 | 0 | 6 | 5 | |||
| R1 | R2 | R3 | |
| 剩余资源数（Available） | 1 | 0 | 0 |
不为安全序列
| Allocation | Need（Max-Allocation） | Available+Allocation(初始（3,3,0）) | 状态 | |||||||
| R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | Finish | |
| P1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | True（核对Need矩阵，P4，100(need)<101(Available)） |
| P4 | 2 | 3 | 5 | 2 | 0 | 0 | 以下均不满足 | |||
| P5 | 0 | 3 | 3 | 0 | 3 | 2 | ||||
| P2 | 2 | 0 | 0 | 0 | 7 | 5 | ||||
| P3 | 0 | 0 | 3 | 6 | 6 | 2 | ||||
3.2 死锁检测例题
case 1：设有进程P1和P2并发执行，都要使用R1和R2，使用资源情况如表所示，试判断是否会产生死锁，并说明原因
| 进程P1 | 进程P2 |
| 申请资源R1 | 申请资源R2 |
| 申请资源R2 | 申请资源R1 |
| 释放资源R1 | 释放资源R2 |
答：（可能会死锁）当进程P1和P2分别申请完R1和R2，当P1再去申请R2时，P2未将R2资源释放，P1处于等待状态，因此，P1和P2都申请不到资源而造成死锁
case 2：系统有同类资源m个，供n个进程共享，若每个进程对资源的最大需求量为k，试问，当m,n,k的值分别为下列情况时，是否会发生死锁？
| 序号 | m | n | k | 是否死锁（（k-1）*n+1<=m） | 说明 |
| 1 | 6 | 3 | 3 | (3-1)*3+1=7>6 (可能死锁) | |
| 2 | 9 | 3 | 3 | (3-1)*3+1=7<9 (不会死锁) | |
| 3 | 13 | 6 | 3 | (3-1)*6+1=13==13(不会死锁) |
case 3：有三个进程P1，P2，P3并发工作。进程P1需要资源S3和S1，进程P2需要资源S2和S1，进程P3需要S3和S2，问
（1）若对资源分配不加限制，会发生什么情况？为什么？
（2）为保证进程正确运行，应采用怎样的分配策略？
答：
（1）可能会发生死锁。满足发生死锁的4大条件，例如，P1占有S1申请S3，P2占有S2申请S1，P3占有S3申请S2。
（2）方法一：静态分配（由于执行前已获得所需的全部资源，因此不会出现占有资源又等待别的资源的现象）
方法二：按序分配（不会出现循环等待资源的现象）
方法三：银行家算法（因为在分配时，保证了系统处于安全状态）
版权声明：本文标题：操作系统——死锁（银行家算法） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727376131h1110820.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论