📚 课程目录第1章死锁基础

1. 死锁基础：死锁的四个必要条件与经典Coffman条件

死锁（Deadlock）是并发系统中两个或多个执行单元（线程/进程）因竞争资源而彼此等待，导致所有执行单元都无法继续推进的状态。在Android内核与驱动开发中，死锁是导致系统无响应（ANR）、内核Panic、设备重启的常见根因。理解死锁的四个必要条件——即Coffman条件——是排查与预防死锁的理论基石。

1.1 死锁的四个必要条件（Coffman条件）

1971年，Edward G. Coffman Jr. 等人系统性地归纳了死锁发生的四个必要条件。这四个条件必须同时满足，死锁才会发生；破坏其中任意一个，即可解除或预防死锁。

条件	英文名称	含义	内核/驱动中的典型场景
互斥	Mutual Exclusion	资源一次只能被一个执行单元占用	自旋锁、互斥锁、硬件寄存器独占访问
持有并等待	Hold and Wait	执行单元已持有一个资源，同时等待获取另一个资源	驱动中先获取锁A，再请求锁B
不可剥夺	No Preemption	资源不能被强制从持有者手中剥夺，只能由持有者主动释放	内核锁一旦获取，除非解锁，否则不能被其他线程抢走
循环等待	Circular Wait	存在一个执行单元集合 {T1, T2, …, Tn}，T1等待T2持有的资源，T2等待T3持有的资源，…，Tn等待T1持有的资源	两个驱动模块互相等待对方持有的锁

排查要点： 在Android内核死锁排查中，最常被忽视的是“持有并等待”和“循环等待”两个条件。驱动开发者往往只关注互斥锁的正确使用，却忽略了锁的获取顺序和嵌套深度。

1.2 死锁的图形化表示

下图展示了两个线程（Thread A 和 Thread B）与两个资源（Resource X 和 Resource Y）之间的死锁循环。每个线程持有一个资源，同时等待对方持有的资源，形成闭环。

1.3 四个条件的详细分析

1.3.1 互斥（Mutual Exclusion）

互斥是资源本身的属性。在内核中，大多数硬件资源（如DMA通道、中断控制器寄存器、I2C总线）和内核对象（如task_struct、文件描述符表）都要求互斥访问。驱动开发者无法改变资源的互斥性，但可以通过设计减少互斥资源的竞争粒度。

  内核视角： 自旋锁（spinlock）和互斥锁（mutex）是实现互斥的两种基本原语。自旋锁用于中断上下文，互斥锁用于进程上下文。错误地混用两者是驱动死锁的常见原因。

1.3.2 持有并等待（Hold and Wait）

当一个执行单元已经持有一个资源，又在不释放该资源的情况下请求另一个资源时，就满足了“持有并等待”条件。这是驱动开发中最容易引入死锁的环节。

/* 危险示例：持有锁A，等待锁B */
void driver_function_A(void)
{
    mutex_lock(&lock_A);    /* 持有锁A */
    /* ... 临界区操作 ... */
    mutex_lock(&lock_B);    /* 等待锁B —— 如果此时另一个线程持有锁B等待锁A，则死锁 */
    /* ... */
    mutex_unlock(&lock_B);
    mutex_unlock(&lock_A);
}

1.3.3 不可剥夺（No Preemption）

内核锁一旦被线程获取，除非该线程主动释放，否则其他线程无法强制剥夺。这与用户态不同——内核态没有“锁超时强制释放”的机制。不可剥夺性意味着死锁一旦形成，系统无法自动恢复，只能通过外部干预（如看门狗复位）或人工介入。

注意： 在Android内核中，某些驱动会尝试使用 mutex_trylock() 或 spin_trylock() 来规避不可剥夺条件。但这只能降低死锁概率，不能完全消除，因为trylock失败后需要设计合理的回退策略。

1.3.4 循环等待（Circular Wait）

循环等待是四个条件中最直观、也最容易通过静态分析检测的条件。它要求存在一个等待环路：T1→R1→T2→R2→…→Tn→Rn→T1。在驱动代码中，循环等待通常表现为锁的获取顺序不一致。

场景	锁获取顺序	是否可能死锁
一致顺序	所有线程都先获取锁A，再获取锁B	否（不会形成循环）
不一致顺序	线程1：A→B；线程2：B→A	是（形成循环等待）
嵌套深度不同	线程1：A→B→C；线程2：C→A	是（部分循环）

1.4 死锁的数学表示与资源分配图

资源分配图（Resource Allocation Graph, RAG）是分析死锁的经典工具。它由两类节点（线程节点T和资源节点R）和两类边（分配边和请求边）组成：

分配边：从资源节点指向线程节点，表示该资源已分配给该线程。
请求边：从线程节点指向资源节点，表示该线程正在请求该资源。

当资源分配图中存在环时，系统可能处于死锁状态。但需要注意：有环不一定死锁（如果环中资源类型有多个实例），但每个资源类型只有一个实例时，有环则必然死锁。

1.5 死锁与活锁、饥饿的对比

在驱动稳定性工程中，需要区分死锁与另外两种并发问题：

问题类型	特征	是否阻塞	能否自动恢复	典型驱动场景
死锁	线程互相等待，永不释放	是，永久阻塞	不能	两个驱动各持一锁，互相等待
活锁	线程不断重试，但始终无法获取资源	否（CPU仍在运行）	可能（随机退避）	trylock失败后立即重试，导致CPU空转
饥饿	低优先级线程长期得不到资源	否（其他线程正常运行）	可能（优先级提升）	中断处理函数长期占用锁，阻塞进程上下文

工程实践： 在Android BSP开发中，死锁排查最有效的工具是 lockdep（内核锁依赖检测器）。它能在运行时检测锁的获取顺序是否一致，并在发现潜在死锁时打印警告。建议在开发阶段始终开启 CONFIG_LOCKDEP 和 CONFIG_DEBUG_LOCK_ALLOC。

1.6 经典Coffman条件的现代扩展

随着多核处理器和复杂SoC的普及，死锁的表现形式也在演化。除了经典的四个条件，现代内核中还出现了以下变体：

优先级反转死锁：低优先级线程持有锁，高优先级线程等待，中优先级线程抢占导致低优先级线程无法释放锁。虽然不满足经典四条件，但同样导致系统无响应。
中断上下文死锁：进程上下文持有锁，中断处理函数尝试获取同一把锁（spinlock），导致自旋等待死锁。这本质上是“持有并等待”在中断场景的变体。
RCU死锁：在RCU（Read-Copy-Update）临界区内调用可能睡眠的函数，或嵌套RCU锁，导致同步原语死锁。