面试题：并发与同步：死锁预防算法中的资源分配图算法理解

Question

请简述资源分配图算法（如资源分配图简化算法）在死锁预防中的作用及工作原理，假设存在一个包含多个进程和多种资源类型的系统，如何利用该算法判断系统是否处于死锁状态，并举例说明。

Answer 1

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

资源分配图算法通过对系统资源分配状态进行分析，避免系统进入死锁状态。它能动态检测系统资源分配情况，在死锁形成前发现潜在死锁风险，通过调整资源分配策略来预防死锁。

资源分配图简化算法工作原理

1. 初始化：构建资源分配图，图中节点包括进程节点和资源节点，有向边表示资源分配关系（从资源节点指向进程节点）或请求关系（从进程节点指向资源节点）。
2. 寻找可简化进程：在资源分配图中，查找一个进程，该进程的所有请求边都能立即满足（即对应资源的可用数量大于等于进程请求数量）。
3. 简化进程：如果找到这样的进程，将其所有请求边和分配边都删除，这相当于该进程获得所需资源并执行完成，释放所占用资源。
4. 重复上述步骤：持续重复步骤2和步骤3，直到无法找到可简化进程。

判断系统是否处于死锁状态

若最终资源分配图中所有节点（进程和资源）都被简化（即所有边都被删除），则系统不存在死锁；若存在未被简化的节点，即存在进程无法获得足够资源继续执行，此时系统处于死锁状态。

举例说明

假设系统中有三个进程P1、P2、P3，两种资源类型R1（2个实例）、R2（2个实例）。

• 初始状态：
  • P1已分配1个R1，请求1个R2。
  • P2已分配1个R2，请求1个R1。
  • P3已分配1个R1和1个R2，无请求。
  • 资源分配图为：R1有2个实例，1个分配给P1，1个分配给P3；R2有2个实例，1个分配给P2，1个分配给P3；P1请求1个R2，P2请求1个R1。
• 简化过程：
  • 首先P3无请求，可简化，删除P3的分配边和请求边（因为无请求边），此时R1有1个空闲实例，R2有1个空闲实例。
  • 接着P1请求1个R2，此时R2有空闲实例，P1可简化，删除P1的分配边和请求边，R1有2个空闲实例，R2有2个空闲实例。
  • 最后P2请求1个R1，也可满足，P2可简化，删除P2的分配边和请求边。
  • 最终资源分配图所有边都被删除，说明系统不存在死锁。

假设另一种初始状态：

• P1已分配1个R1，请求1个R2。
• P2已分配1个R2，请求1个R1。
• P3无分配资源，请求1个R1和1个R2。
• 资源分配图为：R1有2个实例，1个分配给P1；R2有2个实例，1个分配给P2；P1请求1个R2，P2请求1个R1，P3请求1个R1和1个R2。
• 简化过程：
  • 此时找不到可立即满足所有请求的进程，无法进行简化，说明系统处于死锁状态。