死锁的避免与解决

死锁的定义

死锁是指两个或多个线程因争夺资源而造成的一种互相等待的僵局，若无外力作用，它们都将无法向前推进。

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

死锁的发生必须同时满足以下四个条件：

互斥条件（Mutual Exclusion）：资源一次只能被一个线程使用。
持有并等待（Hold and Wait）：线程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他线程占有，此时请求线程被阻塞，但对已获得的资源保持不放。
不可剥夺条件（No Preemption）：线程已获得的资源，在未使用完之前，不能被强行剥夺，只能在使用完后由自己释放。
循环等待（Circular Wait）：存在一种线程资源的循环等待链，链中每个线程已获得的资源同时被下一个线程所请求。

--- title: 死锁的产生条件与预防方法 --- graph TD A["死锁"] --> B["产生条件"] A --> C["预防方法"] A --> D["解决方法"] B --> B1["互斥条件"] B --> B2["持有并等待"] B --> B3["不可剥夺条件"] B --> B4["循环等待"] C --> C1["破坏互斥条件"] C --> C2["破坏持有并等待"] C --> C3["破坏不可剥夺条件"] C --> C4["破坏循环等待"] D --> D1["死锁检测与恢复"] D --> D2["死锁避免"] D --> D3["编程最佳实践"]

死锁发生的时序示例

--- title: 死锁发生的时序图 --- sequenceDiagram participant T1 as 线程1 participant R1 as 资源A participant T2 as 线程2 participant R2 as 资源B T1->>R1: 请求资源A R1-->>T1: 分配资源A T2->>R2: 请求资源B R2-->>T2: 分配资源B T1->>R2: 请求资源B T2->>R1: 请求资源A R1-->>T1: 等待（资源A被线程2请求） R2-->>T2: 等待（资源B被线程1请求） Note over T1,T2: 死锁发生

预防死锁的方法

预防死锁是通过破坏死锁的四个必要条件中的一个或多个来实现的。

1. 破坏互斥条件

使资源同时可访问（例如，使用只读数据）
但实际上，很多资源本身性质就是互斥的（如打印机），所以这种方法往往不现实

2. 破坏持有并等待条件

一次性申请所有资源：线程在开始运行前，一次性申请其在整个运行过程中所需要的全部资源
资源申请失败时释放已持有资源：当一个线程申请资源失败时，它必须释放已经持有的所有资源

3. 破坏不可剥夺条件

允许资源被抢占：当一个已经持有了某些资源的线程在申请新的资源失败时，它可以释放已经持有的所有资源，然后再重新尝试申请所有资源
优先级抢占：为资源分配优先级，当高优先级的线程申请资源时，可以从低优先级线程那里抢占资源

4. 破坏循环等待条件

资源有序分配法：将系统中的所有资源类型进行线性排序，并规定每个线程必须按序号递增的顺序申请资源
资源分配图：通过资源分配图检测并避免循环等待

解决死锁的方法

1. 死锁检测与恢复

死锁检测：定期检查系统是否出现了死锁
- 资源分配图法
- 银行家算法
死锁恢复：当检测到死锁时，采取措施解除死锁
- 进程终止：终止一个或多个死锁进程
- 资源抢占：从一个或多个死锁进程那里抢占资源

--- title: 死锁状态转换图 --- stateDiagram-v2 [*] --> 运行运行 --> 请求资源: 线程需要资源请求资源 --> 获得资源: 资源可用请求资源 --> 等待: 资源被占用获得资源 --> 运行: 继续执行等待 --> 死锁: 循环等待形成死锁 --> [*]: 外部干预

2. 死锁避免

银行家算法：在资源分配前，判断分配后系统是否仍处于安全状态
安全状态：系统能够按某种顺序为每个进程分配其所需的最大资源，并避免死锁

3. 实际编程中的最佳实践

尽量减少锁的使用：使用无锁数据结构或算法
避免嵌套锁：尽量不使用嵌套锁，如果必须使用，确保所有线程以相同的顺序获取锁
使用定时锁：使用tryLock()方法设置超时时间，避免无限等待
使用锁的替代方案：
- 读写锁（ReadWriteLock）
- 乐观锁（如版本号机制）
- 无锁数据结构（如原子变量AtomicInteger等）
使用高级并发工具：
- 使用线程池（ExecutorService）
- 使用并发集合（ConcurrentHashMap等）
- 使用同步器（CountDownLatch, CyclicBarrier, Semaphore等）