面试题：并发与同步：死锁避免的关键条件理解

Question

请简述死锁避免中资源分配图算法的基本原理，以及该算法是如何通过检测和调整资源分配来避免死锁的。请举例说明在一个简单的系统中，如何运用这个算法判断是否会产生死锁，并采取相应措施。

Answer 1

资源分配图算法基本原理

资源分配图算法是基于有向图的概念，系统的状态由资源分配图（RAG）来表示。图中的节点分为进程节点（$P_i$）和资源节点（$R_j$），有向边分为请求边（$P_i \to R_j$，表示进程$P_i$请求资源$R_j$）和分配边（$R_j \to P_i$，表示资源$R_j$已分配给进程$P_i$） 。算法通过对资源分配图进行化简操作来判断系统是否处于死锁状态。

通过检测和调整资源分配避免死锁

1. 检测：尝试对资源分配图进行化简。若所有进程节点都能被化简掉，即每个进程都能获得所需资源并运行完成，此时系统是安全的，不存在死锁；若化简后仍有进程节点无法被化简，则系统处于死锁状态。
2. 调整：当检测到死锁时，需要打破死锁。常见的方法是剥夺某些进程已分配的资源，分配给其他进程，以打破死锁循环。

简单系统示例

假设有一个系统，包含3个进程$P_1$、$P_2$、$P_3$，2种资源$R_1$（2个实例）、$R_2$（1个实例）。当前资源分配情况如下：

• 进程$P_1$已分配1个$R_1$实例，且请求1个$R_2$实例。
• 进程$P_2$已分配1个$R_2$实例，且请求1个$R_1$实例。
• 进程$P_3$请求1个$R_1$实例。

此时构建资源分配图：

• 有3个进程节点$P_1$、$P_2$、$P_3$，2个资源节点$R_1$、$R_2$。
• 从$R_1$到$P_1$有分配边，从$P_1$到$R_2$有请求边。
• 从$R_2$到$P_2$有分配边，从$P_2$到$R_1$有请求边。
• 从$P_3$到$R_1$有请求边。

进行化简：

• 进程$P_1$因请求$R_2$未得到满足，不能化简。
• 进程$P_2$因请求$R_1$未得到满足，不能化简。
• 进程$P_3$因请求$R_1$未得到满足，不能化简。 所以系统处于死锁状态。

采取措施：

• 剥夺$P_1$已分配的$R_1$资源给$P_3$，此时$P_3$可以运行完成，释放其占用的$R_1$资源。
• 然后$P_1$或$P_2$可以获得$R_1$资源继续运行，打破死锁。