循环

跨线程阻塞

当前，用于跨线程阻塞的接口按如下方式工作：

• 当线程 T1 想要阻塞等待另一个线程 T2 正在执行的查询 Q 时，它会调用 Runtime::try_block_on。这个调用会检查是否存在循环。假设没有检测到循环，它就会阻塞 T1，直到 T2 完成 Q。此时 T1 会被唤醒。不过，我们并不知道执行 Q 的结果，所以 T1 现在必须“重试”（retry）。通常这会成功读到缓存值。
• 当 T1 被阻塞时，运行时会把它的查询栈（一个 Vec）移动到共享依赖图数据结构中。当 T1 被唤醒时，它会在 try_block_on 返回前重新取回这份查询栈的所有权。

检测循环

当线程 T1 试图执行查询 Q 时，它会尝试从记忆化表中加载 Q 的值。如果发现一个 InProgress 标记，就表示 Q 当前正在计算中。这说明可能存在循环。接着 T1 会尝试阻塞等待查询 Q：

• 如果 Q 也是由 T1 在计算，那么就存在循环。
• 否则，如果 Q 是由另一个线程 T2 在计算，我们就必须检查 T2 是否（传递地）阻塞在 T1 上。如果是，就存在循环。

这两种情况都由 Runtime::try_block_on 在内部处理。检测线程内循环比较容易；为了检测跨线程循环，运行时维护了一张线程之间的依赖 DAG（线程以 RuntimeId 标识）。在把一条边 T1 -> T2（也就是 T1 阻塞等待 T2）加入 DAG 之前，它会先检查从 T2 到 T1 是否已经存在一条路径。如果存在，就说明形成了循环，这条边不能加入（否则 DAG 就不再是无环的）。