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

Question

请描述资源分配图算法（如资源分配图化简法）在死锁预防中的作用和具体步骤。在一个简单场景中，有三个进程P1、P2、P3，以及三种资源R1、R2、R3，已知资源分配情况和进程请求情况，如何利用资源分配图算法判断系统是否会发生死锁，以及如果可能发生死锁，如何通过该算法进行预防？

Answer 1

资源分配图算法在死锁预防中的作用

1. 作用：资源分配图算法（如资源分配图化简法）通过对系统当前资源分配状态进行分析，能够判断系统是否处于死锁状态，若处于死锁状态，可找出死锁进程集合。同时，它还能预测系统中进程请求资源时是否会导致死锁，从而提前采取措施预防死锁的发生。

资源分配图化简法的具体步骤

1. 寻找孤立进程：在资源分配图中，检查是否存在既不占用资源也不请求资源的进程（孤立进程）。若有，将其从图中移除，这一步对死锁判断无影响，只是简化图形。
2. 寻找可化简进程：查找满足以下条件的进程：该进程请求的资源数量小于等于系统中可用该资源的数量（考虑已分配资源释放后），且该进程占用的资源可全部释放。找到这样的进程后，将其从资源分配图中移除，并将其占用的资源归还给系统，这相当于模拟该进程执行完毕并释放资源。
3. 重复化简：不断重复步骤2，直到找不到可化简进程为止。
4. 判断死锁：若最终资源分配图中所有进程都被移除（即图为空），则系统没有死锁；若图中仍有进程存在，这些进程即为死锁进程，系统发生死锁。

在给定简单场景中的应用

1. 已知情况：有三个进程P1、P2、P3，以及三种资源R1、R2、R3，已知资源分配情况和进程请求情况。
2. 判断是否死锁：
   • 首先，初始化系统资源总量，根据资源分配情况计算出当前可用资源数量。
   • 按照资源分配图化简法步骤，从寻找孤立进程开始，若没有孤立进程则查找可化简进程。例如，假设进程P1请求资源R1，系统中当前可用R1资源数量大于等于P1请求数量，且P1占用的资源可释放，那么P1就是可化简进程，移除P1并更新可用资源。
   • 持续重复该过程，若最终所有进程都能从图中移除，系统不会发生死锁；若存在进程无法移除，系统会发生死锁。
3. 死锁预防：
   • 静态预防：在进程启动前，根据资源需求和系统资源总量，计算是否会出现死锁。若预测到可能死锁，可拒绝某些进程的启动请求，或调整进程资源需求。
   • 动态预防：当进程请求资源时，利用资源分配图算法先模拟分配资源，若模拟后资源分配图可化简（即不会导致死锁），则实际分配资源；若模拟后出现死锁，则拒绝资源分配请求，直到其他进程释放足够资源使系统不会死锁为止。