处理策略总览

死锁处理有三类策略：

900

策略 发生时机 核心思想
预防死锁 分配规则设计阶段 破坏死锁四个必要条件之一
避免死锁 每次资源分配之前 判断分配后是否仍处于安全状态
检测与解除 允许死锁发生之后 检测死锁进程，再采取措施解除

预防最保守，避免需要提前知道进程最大资源需求，检测与解除允许系统先冒险运行。

预防死锁

预防死锁就是破坏四个必要条件的若干个。

破坏条件 方法 代价
互斥条件 把独占资源改造成共享资源，如 SPOOLing 把打印机逻辑上改造成共享设备 很多资源无法共享，强行共享会破坏正确性
不剥夺条件 请求新资源失败时释放已有资源；或由系统强行剥夺某些资源 实现复杂，可能造成工作失效，也可能导致饥饿
请求并保持条件 静态分配：进程运行前一次申请全部资源，满足后才投入运行 资源利用率低，可能长期占有暂时不用的资源
循环等待条件 顺序资源分配法：给资源编号，进程只能按递增顺序申请资源。 资源编号不灵活，进程实际使用顺序可能不匹配
Note

顺序资源分配法的想法是让资源请求方向单调。若进程只能从小编号资源申请到大编号资源，那么持有大编号资源的进程不可能再回头请求小编号资源，循环等待就无法形成。

# 避免死锁

避免死锁在每次分配资源之前判断：如果现在同意这个请求，系统会不会进入不安全状态。

安全序列

安全序列是一个进程序列。若系统能按这个顺序让每个进程依次获得所需资源、执行完成并归还资源，则这个序列是安全序列。

  • 能找到安全序列：系统处于安全状态，一定不会发生死锁。
  • 找不到安全序列：系统处于不安全状态，但不一定发生死锁。
  • 已经发生死锁：一定处于不安全状态。

不安全状态不等于死锁。它只是说明系统已经没有把握保证所有进程都能顺利完成。

银行家算法

银行家算法用于在资源分配前判断本次分配是否会使系统进入不安全状态。

需要维护的数据结构：

数据结构 含义
Available[m] 每类资源当前还剩多少可用实例
Max[n][m] 每个进程声明的最大资源需求
Allocation[n][m] 当前已经分配给每个进程的资源数
Need[n][m] 每个进程最多还需要多少资源，Need = Max - Allocation
Request_i[m] 进程 P_i 本次请求的资源数

一次请求的检查流程：

  1. 检查 Request_i <= Need_i。若不满足，说明进程请求超过事先声明的最大需求。

  2. 检查 Request_i <= Available。若不满足，说明当前资源不够，进程等待。

  3. 试探分配：

    1
    2
    3
    Available = Available - Request_i
    Allocation_i = Allocation_i + Request_i
    Need_i = Need_i - Request_i

  4. 执行安全性算法。若能找到安全序列，才正式分配；否则撤销试探分配，让进程等待。

安全性算法的核心动作是反复寻找一个 Need_i <= Available 的进程。找到后，假定它能执行完成，并把它的 Allocation_i 加回 Available。如果所有进程都能加入安全序列，系统安全。

例如系统共有三类资源 $A,B,C$，资源总数为 $(10,5,7)$。某时刻可用资源为 Available = (3,3,2)：

进程 Max Allocation Need
P0 (7,5,3) (0,1,0) (7,4,3)
P1 (3,2,2) (2,0,0) (1,2,2)
P2 (9,0,2) (3,0,2) (6,0,0)
P3 (2,2,2) (2,1,1) (0,1,1)
P4 (4,3,3) (0,0,2) (4,3,1)

从 Available = (3,3,2) 开始，P1 和 P3 的 Need 都能被满足。若先让 P1 完成，系统回收 (2,0,0)，Available 变为 (5,3,2)；再让 P3 完成，回收 (2,1,1)，Available 变为 (7,4,3)。此后 P0、P2、P4 都可以依次完成，所以存在安全序列：

1
P1 -> P3 -> P0 -> P2 -> P4

银行家算法处理一次请求时，还要先做试探分配。例如 P0 请求 Request_0 = (2,1,1)：

  1. Request_0 <= Need_0，没有超过 P0 声明的最大需求。

  2. Request_0 <= Available，当前资源可以满足这次请求。

  3. 试探分配后：

    1
    2
    3
    Available = (1,2,1)
    Allocation_0 = (2,2,1)
    Need_0 = (5,3,2)

  4. 再执行安全性算法。如果找不到安全序列，就撤销上面的三处修改，让 P0 等待。

检测死锁

如果系统既不预防死锁，也不避免死锁，就需要提供死锁检测与解除机制。

检测死锁需要两部分：

  • 保存资源请求和资源分配信息的数据结构。
  • 根据这些信息判断是否已经死锁的算法。

常用表示方式是资源分配图。

资源分配图

资源分配图是一张有向图：

图中元素 含义
圆形结点 P_i 进程
矩形结点 R_j 一类资源
矩形中的小圆点 该类资源的一个实例
P_i -> R_j P_i 正在请求 R_j
R_j -> P_i R_j 的某个实例已经分配给 P_i

资源分配图保存的是“谁占有资源、谁还在等资源”。检测算法不直接猜测将来调度顺序，而是不断问一个问题：当前可用资源是否足以让某个进程完成？

检测思想是化简资源分配图：

  1. 找到一个既不阻塞又不是孤点的进程。它的请求可以被当前可用资源满足。
  2. 假定该进程能执行结束，删除它所有请求边和分配边，并回收它占有的资源。
  3. 回收资源后，可能使其他阻塞进程变为可完成进程，继续化简。
  4. 若最终所有边都能删除，资源分配图可完全简化，没有死锁。
  5. 若最终不能完全化简，则系统发生死锁；剩余连着边的进程就是死锁进程。

死锁定理：某时刻资源分配图不可完全简化，则此时系统发生死锁。

解除死锁

检测出死锁后，需要把系统从死锁状态中解脱出来。常见方法有三种。

方法 做法 主要代价
资源剥夺法 挂起某些死锁进程，抢占它们的资源，分配给其他死锁进程 要防止被挂起进程长期得不到资源而饥饿
撤销进程法 强制终止部分或全部死锁进程，回收资源 实现简单，但可能损失大量已完成工作
进程回退法 让一个或多个死锁进程回退到足以避免死锁的位置 需要记录历史信息和设置还原点

解除死锁时不一定要处理系统中所有进程。用检测算法化简资源分配图后，最终还连着边的那些进程才是死锁进程。

选择剥夺、撤销或回退对象时，通常考虑进程优先级、已运行时间、还需运行时间、已占资源数量、回退代价和对其他进程的影响。