一、死锁的数学定义与图论模型
各位同学，今天我们来聊聊RTOS里最让人头疼的问题之一——死锁。
说实话，我入行第三年就栽过一次。当时做一个工业控制器的任务调度，四个任务互相等资源，系统直接卡死。现场工程师打电话说设备不动了，我远程一看，嗯，典型的死锁。从那以后，我对死锁的数学模型就特别上心。
1.1 死锁的数学定义
死锁，用数学语言怎么说？
我习惯这样定义：一组任务中，每个任务都在等待另一个任务释放资源，而这个资源又被该组中其他任务持有，导致所有任务都无法继续执行。
说白了，就是一群人围成一圈，每个人手里都拿着别人需要的东西，谁也不肯先放手。结果就是——大家一起卡死。
死锁的数学形式化描述：
设任务集合 T = {T₁, T₂, ..., Tₙ}，资源集合 R = {R₁, R₂, ..., Rₘ}
若存在一个任务子集 S ⊆ T，使得：
- ∀Tᵢ ∈ S，Tᵢ 正在等待某个资源 Rⱼ
- 而 Rⱼ 被 S 中的另一个任务 Tₖ 持有
- 且 S 中所有任务都无法继续推进
则称系统处于死锁状态。
你想想看，这个定义其实很直观。但真正难的是——怎么在系统运行时就发现它？这就得靠图论模型了。
1.2 资源分配图
我个人最喜欢用资源分配图来分析死锁。它就像一张关系网，把任务和资源之间的「谁持有谁、谁等谁」画得清清楚楚。
资源分配图的构成：
- 顶点：两类节点——任务节点（圆圈）和资源节点（方框）
- 有向边：两种边——请求边（任务→资源）和分配边（资源→任务）
举个例子：任务T₁持有资源R₁，同时请求资源R₂；任务T₂持有R₂，请求R₁。画出来就是一个环。
我的经验：在项目里，我习惯把资源分配图打印出来贴在工位上。每次新增任务或资源，先画一画，看看有没有形成环。这招帮我避过至少三次死锁。
1.3 等待图
资源分配图其实可以简化。怎么简化？把资源节点去掉，只看任务之间的等待关系。
等待图就是资源分配图的简化版：
- 每个任务是一个节点
- 如果任务T₁正在等待T₂持有的资源，就画一条T₁→T₂的有向边
为什么要简化？因为资源分配图里资源节点多了，图会变得很乱。等待图只关注任务间的依赖关系，一眼就能看出有没有循环等待。
注意：等待图里出现环，不一定就是死锁。但死锁一定会在等待图里形成环。这个「充分必要条件」的关系，大家要记清楚。
1.4 死锁的四个必要条件
说到死锁，就绕不开这四个条件。我记得当年面试时，面试官问我：「死锁的四个必要条件是什么？」我脱口而出，然后他追问：「缺一个行不行？」
答案是：缺一个就不叫死锁。
| 条件 | 说明 | 我的理解 |
|---|---|---|
| 互斥 | 资源一次只能被一个任务使用 | 比如串口、打印机，同一时刻只能一个人用 |
| 持有并等待 | 任务拿着已有资源，同时等待其他资源 | 手里抓着不放，眼睛还盯着别人的 |
| 非剥夺 | 资源不能被强制拿走，只能由持有者主动释放 | 系统不能强行回收，得等任务自己放手 |
| 循环等待 | 存在一个任务链，每个任务都在等下一个的资源 | 就是等待图里的那个环 |
这四个条件必须同时满足，才会发生死锁。缺一个，系统就能自己解开。
避坑指南：我曾经在一个项目中，以为只要打破「循环等待」就能解决所有死锁。结果发现，互斥条件在某些硬件资源上是无法避免的。后来我学乖了——四个条件都要检查，哪个能打破就打破哪个。
1.5 知识体系图
下面这张图，是我自己总结的死锁知识体系。你看一眼，就能把这一章的内容串起来。
1.6 小结
这一章我们讲了死锁的数学定义、资源分配图、等待图，还有那四个绕不开的必要条件。
我个人觉得，理解死锁的关键不在于背定义，而在于能一眼看出系统里有没有「环」。你想想看，不管是资源分配图还是等待图，核心都是找环。找到环，就找到了死锁的嫌疑犯。
下一章我们会聊怎么用这些模型来检测死锁。嗯，到时候我会分享一个我踩过的坑——当时用等待图分析一个五任务系统，差点被绕晕。
公众号:蓝海资料掘金营，微信deep3321