软考知识点12：死锁、进程资源图
## 简介 进程死锁（Deadlock）是指一组进程在等待彼此持有的资源，导致所有进程都无法继续执行
渲染中...
## 简介
进程死锁（Deadlock）是指一组进程在等待彼此持有的资源，导致所有进程都无法继续执行的情况。这种相互等待的状态使得所有相关进程都被永久阻塞。
进程资源图是资源分配图的另一种称谓，是用有向图表示系统中进程与资源之间的请求和分配关系的图。
软考中，这两个考点都是关于死锁的。
> 关注公众号“**月上老狗**”，发送“**软件设计师**”，获取历年软件设计师软考真题。
>
> 
<!-- more -->
## 进程死锁
### 死锁产生的四个必要条件
死锁的产生需要同时满足以下四个条件：
- 互斥条件（Mutual Exclusion）：至少有一个资源是被独占使用的。
- 占有并等待条件（Hold and Wait）：一个进程已经占有了至少一个资源，同时又在等待另一个资源。
- 不剥夺条件（No Preemption）：进程已获得的资源在未使用完之前，不能被强制剥夺，只能由该进程主动释放。
- 环路等待条件（Circular Wait）：存在一个进程等待链，链中每个进程都在等待下一个进程所占有的资源。
如何判断进程会不会死锁？
判断进程是否会陷入死锁，常用的方法包括：
### 资源分配图
资源分配图（Resource Allocation Graph, RAG）：
- 定义：RAG是一种有向图，用于表示进程和资源的分配和请求情况。
- 组成：图中包含两类节点：进程节点（圆形）和资源节点（方形），以及两类边：请求边（从进程指向资源）和分配边（从资源指向进程）。
### 死锁相关计算
要计算导致死锁的资源数，需要分析如下几个数字：
1. 系统资源的总数。
2. 已分配的资源数。
3. 每个进程当前所需的资源数。
有了这几个数字之后，即可确定系统资源是否满足进程运行，从而是否造成死锁、死锁最小的进程等等。
这里计算时，我们可以认为：**如果只需要额外引入一个资源即可满足所有进程的运行，则这个系统不会死锁，否则。则会死锁。**
有了这个条件，就可以利用小学只是计算死锁相关的问题了。
#### 例题
如：已知共有8个资源，相同的N个进程，每个进程需要3个资源，则最大可以运行多少个进程？
计算：`(8 + 1) / 3 = 3` 刚好等于3，所以3个进程可以正常运行，4个进程则会死锁。
如果每个线程占用4个资源呢？
`(8 + 1) / 4 = 2.25`，不到3，则最大能运行2个进程，3个进程就会造成死锁。
- 反之：已知共有2个进程，那每个进程最大占用多少资源不会死锁呢？
`8 + 1 / 2 = 4.5`，则占用4个资源不会死锁，5个则会死锁。
## 进程资源图
### 组成
进程组原图一般是线框图，其中节点代表进程（`Process`）和资源（`Resource`），箭头表示已分配资源或请求组员，具体介绍：
- 节点：进程（`常用圆形图标，字母P表示，如：P1, P2, ...`）和资源（`常用矩形图标，字母R表示，如：R1, R2, ...`）。
- 箭头：
- 从进程指向资源，表示进程请求资源。
- 从资源指向进程，表示资源已分配给进程。
### 如何判断进程资源图中是否存在死锁？
判断进程资源图中是否存在死锁，可以通过以下步骤：
1. 构建资源分配图：将当前系统的进程和资源关系绘制成图。添加请求边和分配边。
2. 检测环路：使用环检测算法（如深度优先搜索DFS）在资源分配图中检测是否存在环。若存在环，并且每个资源只有一个实例，则该环表示死锁。若某些资源有多个实例，需要进一步检查环中的资源实例分配情况，以确定是否真的存在死锁。
实际例子
假设系统中有两个进程P1和P2，以及两个资源R1和R2。P1持有R1，等待R2。P2持有R2，等待R1。则资源分配图如下：
```console
P1 → R2（P1请求R2分配资源）
R1 → P1（R1已分配资源给P1）
P2 → R1（P2请求R1分配资源）
R2 → P2（R2已分配资源给P2）
```
分析：
- 互斥条件：R1和R2是独占的。
- 占有并等待条件：P1占有R1，等待R2；P2占有R2，等待R1。
- 不剥夺条件：资源不能被强制剥夺。
- 环路等待条件：存在P1 -> R2 -> P2 -> R1 -> P1的环路。
因此，该资源分配图中存在环路，且所有资源都是独占的，因此系统存在死锁。
## 总结
- 进程死锁是进程间互相等待资源导致的永久阻塞状态。
- 四个必要条件：互斥、占有并等待、不剥夺、环路等待。
- 资源分配图用节点和有向边表示进程和资源的关系，通过环检测判断死锁。
通过理解这些概念和方法，可以有效地分析和处理进程死锁问题。END
评论
登录后查看和发表评论
前往登录