面试题：并发与同步之资源图状态转换中的死锁预防

Question

假设一个系统的资源图中有多种类型的资源和多个进程，描述如何利用资源分配图算法来预防死锁，在资源图状态转换过程中，怎样动态检测并调整以确保系统不会进入死锁状态？

Answer 1

利用资源分配图算法预防死锁

1. 资源分配图简化算法：
   • 首先，在资源分配图中寻找一个既不阻塞又非孤立的进程节点 (P_i)。一个进程不阻塞是指它所请求的资源数量小于等于系统中该资源类型的可用资源数量；非孤立是指该进程节点至少有一条边与其他节点相连。
   • 若找到这样的进程 (P_i)，则可以消除与 (P_i) 相连的所有边，即 (P_i) 获得它所需的资源并运行完成后释放其占用的所有资源，这就相当于对资源分配图进行了一次简化。
   • 重复上述步骤，不断寻找可简化的进程节点并进行简化。如果最终能将整个资源分配图简化为一个空图，即所有进程节点都被消除，那么系统处于安全状态，不会发生死锁；否则，系统处于不安全状态，可能会发生死锁。
2. 资源分配策略：
   • 基于资源分配图简化算法的结果，在进行资源分配时，只允许那些能使资源分配图保持可简化状态的分配操作。也就是说，每次分配资源前，先假设进行该分配操作，然后检查资源分配图是否仍能通过简化算法变为空图。如果可以，则进行分配；否则，拒绝该分配请求，这样就能预防死锁的发生。

动态检测并调整确保系统不进入死锁状态

1. 定期检测：
   • 系统定期运行资源分配图简化算法，检查当前资源分配图的状态。检测的时间间隔可以根据系统的负载和稳定性要求来确定，例如在系统负载较低时适当延长检测间隔，在负载较高时缩短检测间隔。
2. 检测到不安全状态时的调整：
   • 剥夺资源：当检测到系统处于不安全状态时，从某些进程中剥夺部分资源。选择剥夺资源的进程可以基于多种策略，比如选择优先级较低的进程、已占用资源较多的进程或者预计剩余运行时间较长的进程等。将剥夺的资源分配给那些能使资源分配图重新回到安全状态的进程，即通过资源分配图简化算法检查，分配资源后能使资源分配图可简化为空图的进程。
   • 进程回滚：另一种方法是让某些进程回滚到之前的某个状态，释放它们在后续运行过程中占用的资源。选择回滚的进程同样可以依据一定策略，回滚后重新按照资源分配策略为进程分配资源，使系统回到安全状态。
   • 拒绝新的资源请求：在系统处于不安全状态时，暂时拒绝新进程的资源请求，直到系统通过调整回到安全状态后，再考虑处理新的请求。这样可以避免因新的资源分配导致系统进一步陷入死锁。