3. 死锁原理：四个必要条件与资源分配图
在 QTI 平台 HAL 层多线程/多进程交互中，死锁是导致系统无响应、ANR 甚至整机重启的常见根因。理解死锁的数学模型是后续使用 Perfetto 进行 trace 分析的理论基础。本节从死锁的四个必要条件、资源分配图以及死锁与活锁/饥饿的区别三个维度展开。
3.1 死锁的四个必要条件（Coffman 条件）
死锁的发生必须同时满足以下四个条件（缺一不可）：
| 条件 | 定义 | HAL 层典型场景 |
|---|---|---|
| 互斥（Mutual Exclusion） | 资源一次只能被一个线程/进程占用 | Camera HAL 的 buffer 队列、Audio HAL 的 DSP 共享内存 |
| 持有并等待（Hold and Wait） | 线程已持有一个资源，同时等待获取其他线程持有的资源 | Display HAL 持有 fence 同步对象，等待 GPU 渲染完成回调 |
| 非剥夺（No Preemption） | 资源不能被系统强制剥夺，只能由持有者主动释放 | Binder 线程持有 mutex 锁，等待另一个 Binder 服务响应 |
| 循环等待（Circular Wait） | 存在一个线程-资源的闭合等待链：T1→R1→T2→R2→…→Tn→Rn→T1 | Sensor HAL 与 Power HAL 互相调用对方接口形成环路 |
排查要点： 在 Perfetto trace 中，如果发现多个线程长时间处于
blocked 或 uninterruptible sleep 状态，且调用栈指向锁获取函数（如 pthread_mutex_lock、futex），应优先检查是否满足上述四个条件。
3.2 资源分配图（RAG）
资源分配图（Resource Allocation Graph）是描述线程与资源之间请求和分配关系的有向图，用于死锁的检测与预防。图中包含两类节点和两类边：
- 线程节点（圆形）：表示进程或线程，如 T1、T2。
- 资源节点（方形）：表示资源类型，如 R1、R2，内部圆点表示资源实例数量。
- 分配边（资源→线程）：资源已分配给该线程。
- 请求边（线程→资源）：线程正在等待该资源。
下图展示了一个典型的死锁资源分配图：
死锁检测规则： 如果资源分配图中存在有向环，且环中每个资源节点只有一个实例，则系统必然处于死锁状态。上图中 T1→R2→T2→R1→T1 构成环路，满足循环等待条件。
3.3 死锁 vs 活锁 vs 饥饿
在 HAL 层并发问题排查中，死锁、活锁和饥饿的表现形式不同，但都可能导致系统性能下降或功能异常。下表从多个维度进行对比：
| 维度 | 死锁（Deadlock） | 活锁（Livelock） | 饥饿（Starvation） |
|---|---|---|---|
| 线程状态 | 阻塞等待，不消耗 CPU | 持续运行但无进展，消耗 CPU | 可运行但长期得不到调度 |
| 资源占用 | 持有资源不释放 | 反复释放和重试 | 始终无法获取资源 |
| Perfetto 特征 | 线程长时间 blocked，调用栈停在锁函数 |
线程频繁 running 但无有效输出，调度次数异常高 |
线程长时间 runnable 但未获得 CPU |
| HAL 层案例 | Camera HAL 与 ISP HAL 互相等待 buffer | 两个 Binder 服务检测到冲突后同时回退重试 | 低优先级 Audio 线程被高优先级 Display 线程持续抢占 |
| 恢复方式 | 需外部干预（重启/超时回滚） | 可能自行恢复（随机退避） | 调整优先级或调度策略 |
下图展示了三者在线程状态机上的区别：
Perfetto 实战提示： 在分析 HAL 层 trace 时，如果发现线程处于
Uninterruptible Sleep (D) 状态且调用栈指向 mutex_lock 或 futex，优先怀疑死锁；如果线程频繁在 Running 和 Runnable 之间切换但无实际 I/O 或计算输出，考虑活锁；如果低优先级线程长期处于 Runnable 但从未获得 CPU，则属于饥饿。