面试题：并发与同步：死锁预防方法之资源分配图算法相关

Question

在死锁预防中，资源分配图算法是一种重要方法。请简述资源分配图算法检测死锁的基本步骤，以及如何通过修改资源分配图来预防死锁。

Answer 1

资源分配图算法检测死锁的基本步骤

1. 化简资源分配图：
   • 寻找一个既不阻塞又非孤立的进程节点$P_i$。即$P_i$所请求的资源数量小于等于系统中可用资源数量，且$P_i$不是孤立节点（存在与资源节点的请求或分配边）。
   • 若找到这样的进程节点$P_i$，则将与$P_i$相连的边全部删除，$P_i$成为孤立节点。
   • 重复上述过程，直到找不到满足条件的进程节点。
2. 判断死锁状态：
   • 若最终所有进程节点都成为孤立节点，则资源分配图是可完全化简的，系统不存在死锁。
   • 若化简后仍存在非孤立节点，则资源分配图不可完全化简，系统存在死锁，这些非孤立节点构成死锁环。

通过修改资源分配图预防死锁的方法

1. 破坏死锁的必要条件 - 占有并等待：
   • 方法一：一次性分配：进程在运行前一次性申请其所需的全部资源。若系统能满足，则分配给进程，进程运行结束后再释放资源。这样在资源分配图中，不会出现进程一边占有资源，一边又请求其他资源的情况，从根本上破坏了占有并等待条件。例如，进程$P$需要资源$R1$、$R2$、$R3$，在运行前一次性申请，若系统资源足够，将这三个资源对应的分配边直接连接到$P$，避免了分步请求造成的死锁可能。
   • 方法二：剥夺式分配：当一个进程已占有部分资源，又提出新的资源请求而不能满足时，必须释放它已占有的所有资源，以后需要时再重新申请。这就改变了资源分配图中进程对资源的占有和请求情况，破坏占有并等待条件。例如，进程$P$占有资源$R1$，请求$R2$但系统无$R2$可用，此时$P$释放$R1$，$R1$的分配边从$P$断开，避免了死锁。
2. 破坏死锁的必要条件 - 不可剥夺：
   • 允许系统剥夺死锁进程占有的资源。当检测到死锁环时，从死锁环中的某个进程开始，剥夺其占有的资源分配给其他进程，以打破死锁环。在资源分配图上表现为删除死锁进程与资源的分配边，重新连接到其他进程。例如，死锁环中有进程$P1$、$P2$、$P3$，$P1$占有资源$R1$，$P2$占有资源$R2$，$P3$占有资源$R3$且$P1$请求$R2$，$P2$请求$R3$，$P3$请求$R1$，此时可剥夺$P1$的$R1$分配给$P3$，删除$P1$与$R1$的分配边，连接$P3$与$R1$的分配边，破坏死锁环。
3. 破坏死锁的必要条件 - 循环等待：
   • 资源分配图算法中可采用资源分配顺序算法：为系统中的资源类型分配一个线性顺序，如$R1 < R2 < R3$。进程只能按照递增的顺序请求资源，若进程请求资源$Rj$，则它之前不能请求过编号大于$Rj$的资源。在资源分配图中，按照这种规则请求资源，不会形成资源请求的循环等待环。例如，进程$P$若请求资源$R3$，那么它不能先请求过$R4$等编号更大的资源，避免了因循环请求资源造成的死锁。