跳到主要内容

死锁理论基础

用 CDG 判据和破环理论分析网络死锁

核心要点：

  • 死锁充要 = 资源依赖图成环
  • CDG 无环 ⟺ 确定性路由无死锁
  • 自适应路由下环不必然死锁（Duato）
  • 逃生通道无环即可兜底无死锁
  • Turn Model 禁转向破环，零额外 VC

前置阅读：

死锁要满足哪些条件才会发生？​

死锁成立需同时满足 Coffman 四个必要条件，破坏任一条件即可阻止死锁（在单实例资源系统中四条件亦为充分条件）[1]。

条件操作系统语义互联网络对应
互斥（Mutual Exclusion）资源不能被两个进程同时占有缓冲 / 通道一次只服务一个报文
占有并等待（Hold and Wait）持有资源同时申请新资源flit 占着当前缓冲、等待下一跳缓冲
不可抢占（No Preemption）资源不能被强制释放wormhole 路由下已占通道不能被抢占
循环等待（Circular Wait）进程构成等待环通道依赖图（CDG）出现环

@tbl-deadlock-theory-coffman Coffman 四条件与互联网络的对应

网络死锁与操作系统死锁本质相同，差异在资源的粒度与跨度。wormhole 路由（虫洞路由）把报文切成 flit 流水转发，头 flit 探路、后续 flit 跟随，因此一个报文的 flit 链可同时横跨多跳、占用多跳缓冲——「占有并等待」天然成立，「不可抢占」也是 wormhole 的固有性质。前三个条件在 wormhole 网络中难以攻击，工程破环几乎都瞄准第四个条件——消除循环等待，即让依赖图无环。后续所有理论都是「如何保证依赖图无环」的不同回答。

如何判定确定性路由会不会死锁？​

通道依赖图（CDG）无环，是确定性 wormhole 路由无死锁的充要判据[2]。

CDG 刻画「占用一个通道后还可能申请哪个通道」的关系：

  • 节点：网络中每条（虚拟或物理）通道
  • 有向边：若路由函数允许报文占用通道 $c_i$ 后接着申请通道 $c_j$，则连边 $c_i \rightarrow c_j$

边集合完全由路由函数决定——路由允许的每一种转弯都对应一条依赖边。CDG 有环意味着一组通道互相等待（循环等待成立）；无环则可对通道做拓扑排序，报文总能沿排序方向前进。

虚拟通道（VC）是 Dally-Seitz 给出的破环工具：把一条物理链路复用为多条逻辑通道、各有独立缓冲，再强制报文按 VC 编号递增的顺序使用通道，CDG 中就不可能出现回到低编号的边，环被打断。典型应用是 torus 的 wraparound 环——物理上首尾相连必然成环，把每条链路分成 VC0 / VC1、报文跨越 dateline 时从 VC0 切到 VC1，CDG 即无环（dateline 路由实现见 05-dor）。代价是每条物理链路要额外缓冲，且报文受 VC 编号顺序约束——这正是 Duato 理论要放宽的地方。单 VC 成环与 VC0/VC1 dateline 破环的对比见 @fig-deadlock-cdg-vc。

单 VC 下 wraparound 使 CDG 成环（左）；VC0/VC1 + dateline 强制编号递增使 CDG 无环（右）@fig-deadlock-cdg-vc

为什么自适应路由有环也不一定死锁？​

Duato 证明：在自适应路由中，通道依赖图存在环并不足以导致死锁[3]。这是反直觉的突破——Dally-Seitz 的「全图无环」判据对自适应路由过度保守，会禁掉大量本可安全使用的路径。

关键是扩展通道依赖图（extended CDG）与路由子函数给出的充要条件：

一个连通的路由函数无死锁，当且仅当存在一个连通的路由子函数，其扩展通道依赖图无环。

这个无环子函数对应的通道集合就是逃生通道（escape channel）：只要报文被阻塞时总能退回到一组本身无环的通道继续前进，整体就不死锁，即使自适应通道之间存在环。

工程上催生了主流的 VC 划分范式：自适应 VC 允许通道间存在环、报文优先在其上自由选路均衡负载；逃生 VC 构成无环子网（如用 DOR 规则），报文在自适应 VC 阻塞时退入，保证有一条无死锁路径到达任意目的。该范式被 Cray T3E、Alpha 21364 等采用，比 Dally-Seitz 的全图无环宽松得多（自适应路由转发细节见 04-自适应路由）。

不增加虚拟通道能破环吗？​

Turn Model 不加任何虚拟或物理通道，仅通过禁止部分转向打破环[4]。

核心洞察：网络中的环由特定「转向」组合而成。以 2D mesh 为例，报文有 8 种可能转向，分别构成顺时针和逆时针两类潜在环。只要从每类环中各禁掉恰当的一个转向，就能打破所有环，且禁的转向数量最小（保留最大自适应性）。Glass-Ni 给出三个经典实例（均针对 2D mesh）：

  • west-first：先向西走完，之后不允许再向西转
  • north-last：向北是最后一步，向北后不再转向
  • negative-first：先走负方向（西 / 南），之后不再向负方向转

Turn Model 的优势是零额外缓冲开销（不需要 VC），代价是流量分布可能不均衡（被禁转向使某些路径不可用），自适应性也低于 Duato 范式，更适合缓冲受限的片上网络（NoC）。

三类破环手段如何取舍？​

手段理论依据需额外 VC自适应性缓冲开销代表系统
VC 编号序Dally-Seitz（CDG 无环）是无（确定性）高（每链路多 VC）torus 机器、IB 路由引擎
逃生通道Duato（扩展 CDG）是（自适应 + 逃生）高中高Cray T3E、Alpha 21364
Turn ModelGlass-Ni（禁转向破环）否中（部分转向被禁）低片上网络（NoC）

@tbl-deadlock-theory-compare 三类路由破环手段对比

三者不互斥：实际系统常组合使用——逃生通道的无环子网本身可用 DOR 或 turn model 规则构造。共同的理论内核只有一条：让起决定作用的依赖图无环。Dally-Seitz 要求全图无环，Duato 放宽到「存在无环逃生子图」，Turn Model 是构造无环图的一种具体方法。这套工具是后续所有 fabric（06-fabric死锁对比）与流控（03-流控与无损可丢）死锁处理的基础。

开放问题​

  • 列出 2D mesh 8 个转向的完整禁用矩阵，对照三个 turn model 实例
  • 调研 Duato 理论的后续扩展（odd-even turn model、conditional forwarding flow control）

Takeaway​

理论年份判据破环工具
Coffman 四条件1971四条件同时成立才死锁破坏任一条件（网络中攻击循环等待）
Dally-Seitz1987CDG 无环 ⟺ 确定性路由无死锁VC 按编号递增使用
Duato1993存在无环逃生子图即无死锁自适应 VC + 逃生 VC
Glass-Ni Turn Model1992禁最小转向打破所有环禁转向（零额外 VC）

@tbl-deadlock-theory-takeaway 死锁理论与破环工具速查

参考资料​

  1. Coffman, Elphick & Shoshani, System Deadlocks, ACM Computing Surveys, 1971. http://infolab.stanford.edu/~daswani/quals/Coffman71%20-%20System%20Deadlocks.htm
  2. Dally & Seitz, Deadlock-Free Message Routing in Multiprocessor Interconnection Networks, IEEE TC, 1987. https://doi.org/10.1109/TC.1987.1676929
  3. Duato, A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks, IEEE TPDS, 1993. https://ieeexplore.ieee.org/document/250114
  4. Glass & Ni, The Turn Model for Adaptive Routing, ISCA 1992 / ACM SIGARCH CAN Vol.20. https://dl.acm.org/doi/10.1145/146628.140384

延伸阅读​