简介

进程死锁（Deadlock）是指一组进程在等待彼此持有的资源，导致所有进程都无法继续执行的情况。这种相互等待的状态使得所有相关进程都被永久阻塞。

进程资源图是资源分配图的另一种称谓，是用有向图表示系统中进程与资源之间的请求和分配关系的图。

软考中，这两个考点都是关于死锁的。

关注公众号“月上老狗”，发送“软件设计师”，获取历年软件设计师软考真题。

进程死锁

死锁产生的四个必要条件

死锁的产生需要同时满足以下四个条件：

• 互斥条件（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的环路。 因此，该资源分配图中存在环路，且所有资源都是独占的，因此系统存在死锁。

总结

• 进程死锁是进程间互相等待资源导致的永久阻塞状态。
• 四个必要条件：互斥、占有并等待、不剥夺、环路等待。
• 资源分配图用节点和有向边表示进程和资源的关系，通过环检测判断死锁。

通过理解这些概念和方法，可以有效地分析和处理进程死锁问题。