锁顺序与死锁预防 (Lock Ordering & Deadlock Prevention)

本文档详细阐述了死锁（Deadlock）的成因，并为 comix 内核建立了一套必须严格遵守的锁获取顺序规则，以从根本上预防死锁的发生。

1. 死锁问题详解

死锁，或称“死锁拥抱”（Deadly Embrace），是多任务系统中一个经典且致命的问题。当两个或更多的执行流（任务或中断）各自持有一个锁，并试图获取对方持有的锁时，它们将陷入无限的等待循环，导致系统部分或全部功能瘫痪。

典型死锁场景

假设我们有两个任务（任务A，任务B）和两个锁（锁L1，锁L2）。

任务A 获取了 锁L1。
任务B 获取了 锁L2。
此时，任务A 尝试获取 锁L2，但因为任务B持有该锁，任务A进入等待状态。
接着，任务B 尝试获取 锁L1，但因为任务A持有该锁，任务B也进入等待状态。

至此，任务A在等待任务B释放L2，而任务B在等待任务A释放L1。两者都无法继续执行来释放自己持有的锁，从而形成永久的僵局。

2. 解决方案：建立严格的锁顺序

预防死锁最简单有效的方法是资源排序（Resource Ordering）。我们为系统中的所有锁定义一个全局的、唯一的获取顺序。任何代码，在任何时候，如果需要获取多个锁，都必须按照这个预定义的顺序来获取。

通过强制执行这个规则，我们打破了死锁形成的循环等待条件。在上面的例子中，如果规定必须先获取L1再获取L2，那么任务B的执行路径 lock(L2); lock(L1); 将是不被允许的，它必须改为 lock(L1); lock(L2);。这样，当任务A持有L1时，任务B会直接在尝试获取L1时阻塞，而不会先获取L2，从而避免了死锁。

3. `comix` 内核锁顺序规则

根据 comix 内核的现有实现，我们定义以下从 高到低 的锁获取层级。获取锁时，必须从高层级的锁向低层级的锁获取。严禁在持有低层级锁的情况下，尝试获取一个更高层级的锁。

层级	锁	保护对象	备注
1	`TASK_MANAGER` 全局锁	全局任务列表 `tasks` 和 `tid_allocator`	最高级别的锁，用于任务的创建和全局查找。应极力缩短持有时间。
2	`WaitQueue` 内部锁 (`queue.lock`)	`WaitQueue` 中的任务队列 `tasks`	由于需要修改任务调度状态，必须在内部持有SCHEDULER锁。
3	`SCHEDULER` 全局锁	调度器的运行队列 `run_queue` 和其他调度状态	负责任务的调度、睡眠和唤醒。持有此锁时可以修改任务状态。
4	`CPU` 本地数据锁 (`current_cpu().lock()`)	`Cpu` 结构，主要是 `current_task` 指针	用于安全地获取或修改当前CPU正在运行的任务。
5	单个 `Task` 实例锁 (`task.lock()`)	`Task` 结构体的独占内部字段（如 `state`, `context`）	用于修改单个任务的内部状态。
6	`Task` 字段锁 (`children.lock`)	`Task` 中的可变共享字段 `tasks`	用于修改线程间共享的状态。

核心规则详解

严禁逆序：最核心的规则。例如，你不能在持有 task.lock() (层级4) 的情况下，去尝试获取 SCHEDULER 锁 (层级2)。
TASK_MANAGER 优先：任何需要遍历全局任务列表的操作，都必须首先获取 TASK_MANAGER 锁。通常，操作完成后应尽快释放它。

调度器 (SCHEDULER) 锁：当需要修改运行队列（如添加、移除任务）或批量改变任务状态时，应获取此锁。调度器在持有此锁时，可以进一步获取单个 Task 的锁 (层级4) 来修改其 state 字段。

正确示例 (rr_scheduler.rs::wake_up):

#![allow(unused)]
fn main() {
// 1. 获取 SCHEDULER 锁 (隐式地，因为在 &mut self 方法内)
// 2. 获取 task 锁 (层级4)
task.lock().state = TaskState::Running;
// 3. 将 task 添加到 run_queue
self.run_queue.add_task(task);
}

SleepLock 与 WaitQueue 的特殊模式：
- SleepLock 在判断需要让任务睡眠时，会获取 WaitQueue 的内部锁 (层级5)，将任务添加到等待队列，然后 立即释放 WaitQueue 锁。
- 在释放了所有锁之后，才会调用 sleep_task() 和 schedule() 等可能引起任务调度的函数。
- 这是至关重要的模式：决不能在持有任何自旋锁的情况下调用会导致当前任务睡眠或调度的函数，否则会造成持有锁的CPU被切换走，其他CPU或任务将永远无法获得该锁，导致系统死锁。

实践中的例子

场景：终止一个任务 (`terminate_task`)

terminate_task 首先通过 current_cpu().lock() (层级3) 获取到当前任务的句柄 task。
然后获取 task.lock() (层级4) 来修改任务状态为 Stopped。
释放 task.lock()。
最后调用 schedule()，此时已不持有任何锁。schedule() 内部会获取 SCHEDULER 锁 (层级2) 来将该任务从调度系统中移除。

这个流程严格遵守了从高到低（虽然这里没有跨层级获取）的顺序和不在持锁状态下调度的原则。

场景：创建一个内核线程 (`kthread_spawn`)

kthread_spawn 调用 TASK_MANAGER.lock() (层级1) 来分配 tid 和创建 Task 对象。
在持有 TASK_MANAGER 锁期间，它可能会初始化 Task 的部分数据。
创建完成后，它调用 SCHEDULER.lock() (层级2) 的 add_task 方法，将新任务加入运行队列。
- 注意：这里是先释放了层级1的锁，再获取层级2的锁，是安全的。如果需要同时持有，必须先获取 TASK_MANAGER 再获取 SCHEDULER。

通过在整个内核中强制实施这套简单的层级规则，可以从设计上根除绝大多数死锁问题，极大地提升系统的稳定性和可维护性。

Comix 内核文档