面试题：并发与同步之下的操作系统死锁检测基本原理

Question

请阐述在操作系统并发与同步环境中，死锁检测的常用算法（如资源分配图算法）的基本原理，并举例说明如何运用该算法检测系统是否处于死锁状态。

Answer 1

资源分配图算法基本原理

1. 资源分配图：由进程节点（用圆圈表示）和资源节点（用方框表示）组成。从进程节点到资源节点的有向边表示进程请求该资源；从资源节点到进程节点的有向边表示该资源已分配给此进程。
2. 算法核心步骤：
   • 化简资源分配图：在图中寻找一个既不阻塞又非孤立的进程节点。若存在这样的进程节点$P_i$，则可以释放它所占有的全部资源，这就意味着可以删除与$P_i$相关的所有边，从而使图得到化简。重复这个过程，直到无法再找到这样的进程节点。
   • 判断死锁状态：若经过化简后，所有进程节点都成为孤立节点，则系统没有死锁；若化简后仍存在不能被化简的进程节点（即图中存在环），则系统处于死锁状态，这些不能被化简的进程就是死锁进程。

举例说明

假设有三个进程$P_1$、$P_2$、$P_3$，两种资源$R_1$、$R_2$。

1. 资源分配情况：
   • 进程$P_1$已分配到一个$R_1$资源，且请求一个$R_2$资源。
   • 进程$P_2$已分配到一个$R_2$资源，且请求一个$R_1$资源。
   • 进程$P_3$已分配到一个$R_1$资源。
2. 构建资源分配图：
   • 画出三个进程节点$P_1$、$P_2$、$P_3$和两个资源节点$R_1$、$R_2$。
   • 从$R_1$到$P_1$和$P_3$分别画一条有向边，表示资源分配；从$P_1$到$R_2$画一条有向边，表示请求；从$R_2$到$P_2$画一条有向边，表示分配；从$P_2$到$R_1$画一条有向边，表示请求。
3. 运用算法检测：
   • 首先看进程$P_3$，它既不阻塞（因为没有请求资源），也非孤立，所以可以删除与$P_3$相关的边（即从$R_1$到$P_3$的边）。
   • 此时，对于进程$P_1$，它请求$R_2$资源，而$R_2$资源被$P_2$占用，$P_1$阻塞；对于进程$P_2$，它请求$R_1$资源，而$R_1$资源部分被$P_1$占用，$P_2$阻塞。无法再找到可化简的进程节点。
   • 因为图中存在环（$P_1 \rightarrow R_2 \rightarrow P_2 \rightarrow R_1 \rightarrow P_1$），所以系统处于死锁状态，死锁进程为$P_1$和$P_2$。