资源分配图

1. 资源分配图 (RAG) 的构成

资源分配图是一个有向图，由两类节点和两种有向边构成：

• 两类节点:

  1. 进程节点 (Process Node): 通常用圆形表示，内部写有进程的标识符（如 P1, P2）。

  2. 资源节点 (Resource Node): 通常用矩形表示，内部写有资源的标识符（如 R1, R2）。矩形框中的小圆点或方点代表该类资源的实例数量。例如，一个矩形内有2个点，表示该类资源有2个实例（如系统有2台打印机）。

• 两种有向边:

  1. 请求边 (Request Edge): 从进程指向资源的有向边 (P_i \rightarrow R_j)。它表示进程 Pi 正在请求一个 Rj 类的资源实例，但尚未获得，正处于等待状态。

  2. 分配边 (Assignment Edge): 从资源实例指向进程的有向边 (R_j \rightarrow P_i)。它表示 Rj 类中的一个资源实例已经被分配给了进程 Pi，Pi 正在持有并使用它。

3. 如何用资源分配图检测死锁

使用资源分配图检测死锁的规则，根据资源实例的数量分为两种情况，

情况一：每类资源只有一个实例

当系统中每种类型的资源都只有一个实例时，检测规则非常简单：

规则: 图中存在环路 (Cycle) 是死锁发生的充分必要条件。

• 有环路 ⇒ 必有死锁

• 有死锁 ⇒ 必有环路

情况二：某些资源类型有多个实例

当系统中存在拥有多个实例的资源类型时，情况变得复杂：

规则: 图中存在环路是死锁发生的必要不充分条件。

• 有环路 ⇒ 不一定有死锁 (这是你问题的关键)

• 有死锁 ⇒ 必有环路

4. 为什么“有环路”不一定是死锁？(考点与难点)

这种情况的本质在于：虽然一个进程 P_i 在环路中等待的资源 R_j 被另一个进程 P_j 占用，但 R_j 可能还有其他空闲的实例，或者环路外的某个进程可能释放一个 R_j 的实例来满足 P_i 的请求。

另一种无死锁的环路情况:

即使 R1 没有空闲实例，但如果有一个不在环路中的进程 P4 持有 R1 的一个实例，并且 P4 无需再申请其他资源即可运行完毕。那么当 P4 运行完并释放 R1 后，P1 的请求也能被满足，环路同样被打破。

如何判断这种复杂情况？——图简化法 (Graph Reduction)

为了在多实例场景下准确判断死锁，我们需要尝试简化资源分配图：

1. 首先找到一个不被阻塞的进程 Pi（即它的所有请求边指向的资源 Rj 都有空闲的实例）。

2. 如果找不到这样的进程，则图无法简化，图中所有剩余进程都是死锁进程。

3. 如果找到了，就去掉该进程 Pi 的所有请求边和分配边，假装它已运行完毕并释放了所有资源。

4. 重复步骤1，继续寻找新的不被阻塞的进程。

5. 如果最终能消除图中所有的边，则说明系统没有发生死锁；否则，发生了死锁。

总结:

• 单实例资源: 环路 ⇔ 死锁，检测非常简单。

• 多实例资源: 死锁 ⇒ 环路，但环路 ⇒ 不一定死锁。必须通过图简化法或类似银行家算法的死锁检测算法来最终确认。这是因为环路中的进程所等待的资源，可能由空闲实例或环路外即将结束的进程来满足。