死锁：定义、必要条件及避免方法

蚂蚁一面没过QAQ,不知道是存储岗对学历要求比较高还是怎么样，唉，反正确实项目这一块回答的确实不好，等下周的腾讯和快手吧

1. 死锁的定义

死锁（Deadlock）是指多个进程或线程因互相等待对方持有的资源而无法继续执行，导致所有相关进程/线程永久阻塞的状态。

  • 类比：类似多个线程在访问跳表或B+树时，各自持有部分节点锁并等待对方释放，形成循环等待。

2. 死锁产生的四个必要条件

死锁发生需要以下四个条件同时满足（缺一不可）：

  1. 互斥条件（Mutual Exclusion）：

    • 资源（如锁、文件）一次只能被一个进程/线程独占。
    • 示例：互斥锁（Mutex，上下文回答）保护跳表节点，同一时间仅一个线程可操作。
    • 类比：B+树节点加锁，禁止并发修改。

  2. 持有并等待条件（Hold and Wait）：

    • 进程/线程持有至少一个资源，同时等待其他进程/线程持有的资源。
    • 示例：线程A持有跳表节点1的锁，等待节点2的锁；线程B持有节点2的锁，等待节点1的锁。
    • 类比：进程持有数据库连接，等待另一个进程的连接池资源。

  3. 不可抢占条件（No Preemption）：

    • 资源不能被强制抢占，只能由持有者主动释放。
    • 示例：Mutex锁只能由持有线程释放，操作系统无法强制解锁。
    • 类比：B+树节点锁在分裂完成前无法被其他线程抢占。

  4. 循环等待条件（Circular Wait）：

    • 进程/线程形成闭合的资源等待链，每个进程/线程等待下一个持有的资源。
    • 示例：线程A等待线程B的资源，线程B等待线程C的资源，线程C等待线程A的资源。
    • 类比：跳表多线程插入时，节点锁形成循环依赖。

3. 如何避免死锁

避免死锁的核心是破坏上述四个必要条件之一。以下是具体方法：

破坏互斥条件

  • 方法：尽量使用共享资源代替独占资源。
  • 适用场景：读多写少场景使用读写锁（RWLock，上下文回答），允许多线程并发读。
  • 局限性：许多资源（如文件、数据库记录）本质上需要互斥，难以完全破坏。
  • 类比：B+树查询使用读锁，减少独占需求。

破坏持有并等待条件

  • 方法：
    • 一次性获取所有资源：线程在开始前申请所有所需资源，失败则不持有任何资源。
    • 释放已持有资源：申请新资源失败时，释放已持有的资源后重试。
  • 实现：在代码中检查资源可用性，或使用事务机制。
  • 示例：线程更新跳表前，检查所有节点锁是否可用，否则回滚。
  • 类比：数据库事务确保所有资源可用后再执行。

破坏不可抢占条件

  • 方法：允许操作系统或程序强制抢占资源。
  • 实现：
    • 设置超时机制，超时后释放资源。
    • 使用可中断锁（如Java的Lock.tryLock()）。
  • 示例：线程尝试获取Mutex失败后，超时释放已有锁。
  • 类比：B+树分裂时，超时释放节点锁，允许其他线程介入。
  • 局限性：抢占可能导致数据不一致，需额外恢复机制。

破坏循环等待条件

  • 方法：对资源编号，强制按序获取资源（如按资源ID从小到大）。
  • 实现：
    • 定义全局资源顺序，所有线程按相同顺序申请锁。
    • 伪代码：
      1
      2
      3
      // 按资源ID顺序获取锁
      lock(resource[min_id]);
      lock(resource[max_id]);
  • 示例：跳表节点按内存地址或索引排序，线程按序加锁。
  • 类比：B+树节点按键值顺序加锁，防止循环。
  • 优势：简单有效，广泛用于数据库和并发系统。

其他通用方法

  • 死锁检测与恢复：
    • 使用资源分配图检测循环等待。
    • 恢复方式：终止部分进程/线程，或回滚操作。
    • 类比：跳表并发插入时，检测锁依赖图，终止冲突线程。
  • 使用高级同步机制：
    • 条件变量（上下文回答）协调线程，避免忙等待。
    • 信号量（上下文回答）限制资源访问，减少竞争。
  • 无锁编程：
    • 使用原子操作（如CAS，上下文回答中的跳表实现）替代锁。
    • 类比：跳表无锁插入，减少死锁可能性。
  • 线程池/协程：
    • 减少线程数，使用线程池（如上下文中的线程池优化）或协程，降低资源竞争。
    • 类比：B+树操作使用固定线程池，限制并发。

4. 结合上下文

  • 与同步机制：
    • Mutex：易导致死锁（如线程A、B互相等待Mutex）。
    • RWLock：读写分离降低死锁概率，但写锁仍可能循环等待。
    • 条件变量：通过等待/通知避免忙等，减少死锁（如生产者-消费者）。
    • 信号量：限制并发线程，降低资源竞争导致的死锁。
  • 与跳表/B+树：
    • 跳表插入/删除需锁节点，易形成循环等待，建议按节点地址排序加锁。
    • B+树分裂/合并涉及多节点锁，使用读写锁或按键值顺序加锁避免死锁。
  • 与上下文切换：死锁增加线程阻塞，上下文切换开销（上下文回答，1-10μs）累积，影响性能。

5. 总结

  • 定义：死锁是多进程/线程因互相等待资源而永久阻塞。
  • 四个必要条件：互斥、持有并等待、不可抢占、循环等待。
  • 避免方法：
    • 破坏互斥：使用读写锁。
    • 破坏持有并等待：一次性获取或释放资源。
    • 破坏不可抢占：超时或可中断锁。
    • 破坏循环等待：按序加锁。
    • 其他：死锁检测、无锁编程、线程池。
  • 建议：优先使用按序加锁（简单高效），结合无锁机制（如CAS）或条件变量优化高并发场景（如跳表/B+树）。