跳到主要内容

死锁

死锁是指一组进程互相持有对方需要的资源,导致全部永久阻塞而无法推进的现象。它是并发系统设计的核心问题之一,与竞争条件、活锁、饥饿同属资源分配难题。

死锁四必要条件​

Coffman 条件指出,死锁同时成立才可能发生:

  1. 互斥:资源一次只能被一个进程占用。
  2. 占有并等待:进程已持有资源,仍可申请新资源。
  3. 不可剥夺:资源只能由持有者主动释放,内核不能强制回收。
  4. 循环等待:存在一个进程-资源的有向环,P1 等 P2 持有的资源,P2 等 P3,...,Pn 等 P1。

四条同时满足时,死锁可能发生;破坏任意一条即可避免。

预防与避免​

预防通过静态规则破坏某一条件。常见做法:要求进程一次性申请全部资源(破坏占有并等待)、对资源编号并强制按序申请(破坏循环等待)。代价是资源利用率与并发度下降。

避免则在运行时动态检查安全性,典型代表是银行家算法:系统在分配前模拟一次分配,若仍能找到一个安全序列使所有进程完成,则允许分配,否则拒绝。

Available: 当前可分配资源
Need[i]:   进程 i 还需多少
Work = Available
Finish[i] = false
repeat
    找 i 满足 Finish[i]=false 且 Need[i] <= Work
    if 找到: Work += Allocation[i]; Finish[i] = true
    else:    break
until 所有 Finish[i] = true

银行家算法要求事先声明最大需求,在通用 OS 中过于严苛,多见于嵌入式或教学场景。

检测与恢复​

允许死锁发生,但周期性地用资源分配图或类似算法检测。一旦发现环路,选择牺牲者:终止代价最小的进程、或者回滚到检查点。数据库与分布式系统常采用此策略。

活锁与饥饿​

活锁是进程始终在"尝试-失败-重试"循环中推进,逻辑上在跑、实际上无事可做(两人走廊侧身反复避让)。可通过退避抖动(backoff)或优先级提升缓解。

饥饿是某进程长期得不到资源(如低优先级进程被高优先级持续抢占)。可通过老化(aging)、公平队列等机制缓解。

死锁、活锁、饥饿三者常被混淆,关键区别在于"是否真的在等待"与"是否有机会被调度"。