deadlock avoidance 中，thread 何时只有 claim edges？

结论

只要线程当前没有持有资源，也没有尚未满足的资源请求，与它关联的边就可以全部是 claim edges。这种状态可以在线程执行期间反复出现。

最典型的情况是，线程请求并使用资源后，释放了所有资源。按照这个算法，释放资源会使 assignment edge 恢复为 claim edge。线程因此可以回到“只有 claim edges”的状态，并在此时声明将来可能需要的新资源。

线程也可以先执行一段计算代码，再请求图中管理的资源。因此，“尚未请求资源”并不表示线程尚未执行或尚未获得 CPU 时间。

原因：边会随着资源状态转换

这里讨论的 Resource-Allocation Graph 算法要求每种资源类型只有一个实例。线程 Ti 与资源 Rj 之间的边有以下含义：

边随请求、分配和释放操作转换：

claim edge
    │ Ti 请求 Rj
    ▼
request edge
    │ 系统批准分配
    ▼
assignment edge
    │ Ti 释放 Rj
    ▼
claim edge

释放资源后，assignment edge 恢复为 claim edge，原来的声明仍然保留，表示线程以后还可能再次请求该资源。能否添加新的 claim edge，取决于线程当前的资源状态，过去是否请求过资源并不能决定这一点。

一个执行过程示例

假设线程先使用 R1 完成一个阶段，释放后进行计算，再进入可能需要 R2 的下一个阶段。用概念性伪代码表示如下，函数名不代表实际操作系统 API：

declare_claim(Ti, R1)
# 当前：Ti → R1 是 claim edge

request(Ti, R1)
# 当前：Ti → R1 是 request edge

# 系统检查分配是否安全；只有获准后，线程才继续
await_grant(Ti, R1)
# 当前：R1 → Ti 是 assignment edge

use(R1)

release(Ti, R1)
# 当前：Ti → R1 恢复为 claim edge
# 假设没有其他持有的资源，也没有未满足的请求，
# 此时与 Ti 关联的所有边都是 claim edges

compute_without_managed_resources()

declare_claim(Ti, R2)
# 允许添加：
# Ti → R1 和 Ti → R2 都是 claim edges

另一个更直接的例子是，线程启动后先做计算，尚未请求图中的任何资源。计算期间，与它关联的边也可以全部是 claim edges。

为什么放宽条件仍然可行

如果与 Ti 关联的所有边都是 claim edges，这些边就都从 Ti 指向资源，没有边指向 Ti。此时添加一条新的 Ti → Rj，无法形成经过 Ti 的有向环，因为不存在返回 Ti 的路径。

允许线程在持有资源时随意增加声明，则可能破坏此前的安全判断。例如，图中原来有：

R1 → T1    assignment edge
T2 → R1    claim edge
R2 → T2    assignment edge

如果此时允许持有 R1 的 T1 新增 claim edge T1 → R2，就会出现：

R1 → T1 → R2 → T2 → R1

当两个线程都提出对应请求时，就可能各自等待对方持有的资源。要求线程回到“只有 claim edges”的状态后再增加声明，可以避免线程在持有资源期间扩大需求。

添加声明后，后续请求仍须经过算法检查：只有将 request edge 转换为 assignment edge 不会形成环时，系统才批准分配。

实际判断时要注意什么

检查线程 Ti 时，可以按以下顺序判断：

1. 检查是否存在指向 Ti 的 assignment edge。只要仍持有任何一个资源，就不满足条件。
2. 检查是否存在从 Ti 出发的 request edge。只要仍有未满足的请求，也不满足条件。
3. 如果剩余边全部是 claim edges，就允许添加新的 claim edge。

这里的资源仅指该图管理的资源。线程是否正在 CPU 上运行、是否被调度器暂停，与这个条件没有直接对应关系。

没有未满足的请求时，线程仍可能持有资源；刚释放一个资源时，也可能还持有其他资源。这两种情况都需要继续检查。如果线程没有任何关联边，同样满足“所有关联边都是 claim edges”的条件。

这一解释适用于这里的单实例 Resource-Allocation Graph 算法。每种资源类型存在多个实例时，不能直接套用上述环路判定规则。

备注：内容仅供参考。