死锁

计算机中有很多独占 resource，在任一时刻它们只能被一个进程使用，因此 OS 需要授权一个进程临时地、排他地访问某一 resource 的能力。一般进程会排他性地访问若干资源，假设进程 A 在先使用扫描仪的情况请求蓝光光盘刻录机，而进程 B 在先使用蓝光光盘刻录机的情况下请求扫描仪，由于两个进程都占有一定 resouce 且不会释放，并且互相请求了对方的 Resource，而造成这两个进程无限阻塞下去，这样的状态被称为 死锁 (deadlock)。请不要单纯理解只有一台机器才会产生 deadlock，在多台机器同时访问局域网下的多个独占 resource 时也可能发生。

资源

我们将需要排他访问的对象称为 资源 (resource)，资源可以是硬件设备或一组信息，通常有多种资源同时存在，且一些类型的资源存在若干实例 (打印店在同一局域网下会存在多台打印机)。

还记得学习进程与线程时所说的，scheduling algorithm 分为两类： 抢占式 (preemptable) 与 非抢占式 (nonpreemptable)，这里我们也将 resource 分为这两类，且意义相同。比如说 RAM 就是 preemptable resource，一个进程可以在使用时被 OS 换出 RAM；而蓝光刻录机则是 nonpreemptable resource，将正在刻录的蓝光刻录机分配给另一个进程可能造成蓝光光盘的损坏。不过需要思考一个问题，如果这台计算机不支持交换和页面调度，那么内存也就变为了 nonpreemptable resource。因此区分 preemptable / nonpreemptable resource 取决于上下文环境。

preemptable resource 的 deadlock 可以通过 resource 的重新配分而化解，因此 deadlock 主要与 nonpreemptable resource 有关。若 resource 变得不可用，则请求进程将不可用，有的 OS 在这时会阻塞该进程，直到 resource 可用时再次唤醒；有些 OS 则会返回一个错误代码，请求进程自己处理这个错误。但是大部分进程会选择请求、休眠、再请求的方式进行循环，这与被阻塞没什么两样，因此假设 OS 在 resource 不可用时阻塞进程。

死锁

如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么该集合就是死锁的。

进程的数量、占有或请求的资源数量与种类都是无关紧要的，无论资源是何种类型，硬件还是软件，当该集合进程无法引发事件供集合使用时，他们就是 deadlock，当然这是 资源死锁 (resource deadlock)。resource deadlock 并不是唯一的死锁类型，但这是最常见的一种。

Coffman 等人在 1971 年发表的论文 System Deadlocks 中总结了 Resource Deadlock 发生的四个必要条件：

1. 互斥，每个资源要么已分配给了一个进程，要么是可用的。
2. 占有与等待，已经得到了某个资源的进程可以再次请求新的资源。
3. 不可抢占，已分配的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
4. 环路等待，死锁发生时系统中必定存在两个或以上的进程组成的环路，该环路中每个进程都在等待下一个进程所占有的资源。

需要注意的是，deadlock 发生时这四个条件必定同时满足，如果有一个不成立那么死锁不会发生。Holt 则在 1972 年发表的论文 Some Deadlock Properties of Computer Systems 中描述了如何用有向图对上述四个条件进行建模。有向图中 圆形 表示进程，方形 表示资源，资源到进程的有向边则表示该资源已授权并被进程占用，进程到资源的有向边则表示请求且还未占有。

可以大胆的猜测，当进程集合中的所有进程都以严格的串行运行，那么该集合就不会发生死锁。但是问题时，没有并行的系统性能极低，是不可接受的。如果所有进程都不进行 IO，那么 SJF 比轮询更好，此时的串行运行是最优解，但现实不是这样。

既然死锁是四个必要条件，那么对其进行破坏不就可以解除死锁了吗。Holt 在建模的同时，提出了四种处理死锁的策略：

1. 鸵鸟算法，即忽略死锁。如果你忽略死锁，死锁也会忽略你。
2. 检测死锁并恢复。让死锁发生，检测它们是否发生，发生时采取行动解决问题。
3. 仔细对资源进行分配，动态避免死锁。
4. 通过破坏四个必要条件之一，防止死锁产生。

死锁的检测与恢复

每种类型一个资源的死锁检测

我们可以为这样的系统构造一张资源分配图，这是一个有向图，当图中存在一个以上的环时即可说明死锁的存在。而在环上的资源与进程则是死锁所涉及的，最终我们将死锁检测转换为对有向环路的检测。

每种类型多个资源的死锁检测

如果一个类型有多个资源时，便不能使用有向图来检测是否死锁。现在提供一种基于矩阵的算法来检测 \(P_1\) 到 \(P_n\) 这 n 个进程的死锁。假设资源的类型数量为 m，资源 \(E_1\) 到 \(E_m\) 代表了不同的资源。E 是 现有资源向量 (Existing Resource Vector)，代表每种已存在资源的总数；A 是 可用资源向量 (Available Resource Vector)，代表每种资源当前可用的数量。现在有 C 为 当前分配矩阵 (Current Allocation Matrix)，R 为 请求矩阵 (Request Matrix)。C 中第 \(i\) 行代表进程 \(P_i\) 当前所持有的资源数量，所以 \(C_{ij}\) 代表了 \(P_i\) 持有资源 \(E_j\) 的数量，而 \(R_{ij}\) 代表了 \(P_i\) 所需资源 \(R_j\) 的数量。

这四种 data structure 之间有一个重要的恒等式，具体地说，某种资源要么已分配要么可用： \[\sum_{i=1}^{n} CAM_{ij} + ARV_{j} = ERV_{j}.\]

换言之，如果我们将所有已分配的资源 j 的数量加起来再和所有可供使用的资源相加，结果就是该资源的总数。死锁检测算法就是基于向量的比较，当且仅当 \(A_{i} \leq B_{i} (0 \leq i \leq m)\) 时 \(A \leq B\)。当个进程起初都是没有标记过的，算法开始会对进程做标记，进程被标记后就表明它们能够被执行，不会进入死锁。当算法结束时，任何没有被标记的进程都是死锁的。

死锁检查算法如下：

1. 寻找一个没有标记的进程 \(P_{i}\) ，对于它而言 \(RM_{i} \leq ARV\)。
2. 如果找到了一个这样的进程，那么 \(ARV += CRM_{i}\)，标记该进程并重新执行第一步。
3. 如果没有这样的进程，那么算法停止。

你可能注意到了第二步中只是简单的将占有资源加到了可用资源中，没有做其他处理。因为我们这里只是对死锁进行检查，无需处理其他情况，因此该进程可以被满足时就认为不会死锁，并将其算为可用资源并计算其他进程的资源。

我们知道了如何检测死锁，现在的问题是何时检测死锁。一般可以选择在资源请求时进行死锁检测，这样可以更早地发现存在的死锁，但是也会消耗大量的 CPU。另一种方法是每隔一段时间进行一次检测，或者当 CPU 的使用率降到某一语支时进行检测，这样考虑到 CPU 使用率的问题，如果死锁的进程数达到一定数量后，就没有多少进程可以运行了，所以 CPU 会经常空闲。

从死锁中恢复

我们需要利用一些手段，将检测到的死锁恢复，从而使系统恢复正常。

利用抢占恢复

在某些情况下，可能会临时将某个资源从它的当前所有者那里转移给另一个进程。在不通知进程的情况下，将某一资源从一个进程强行取走给另一个进程使用接着再送回，这种做法是否可行主要取决于该资源本身的特性。用这种方法恢复通常比较困难或不太可能，若选择挂起某个进程，则在很大程度上取决于哪个进程拥有比较容易回收的资源。

利用回滚恢复

如果系统设计人员以及主机操作员了解到死锁有可能发生，他们就可以周期性地对进程进行检查点 (checkpointed) 检查。进程检查点检查就是将进程的状态写入一个文件以备以后重启。该检查点中不仅包括存储映像，还包括资源状态，即哪些资源分配给了该进程。为了使这一过程更有效，新的检查点不应覆盖原有的文件，而应写入新的文件。

当检测到死锁时，就很容易发现需要哪些资源。为了进行恢复，要从一个较早的检查点上开始，这样拥有所需要资源的进程会回滚到一个时间点，在此时间点之前该进程获得了一些其他的资源。在该检查点之后所做的所有工作都丢失。接着可以将这个资源分配给一个死锁进程，当该进程再次试图获取资源的控制时，就必须一直等待直到可用。

通过杀死进程恢复

最直接、简单且有效的方法就是杀死一个或若干个进程，这些进程都是死锁环路上的一个，若杀死进程依然不行的话则继续杀死其他进程，直到打破死锁环。当然还可以牺牲环外的进程用以释放相关资源，供死锁环上的进程使用。当然选择杀死的进程应该具有 幂等性，这样它再次运行时与第一次则会产生相同的结果。

死锁避免

还记着检测死锁的四个 structure 吗，我们假设的是一次请求所有的资源，但大多数系统一次只能请求一个资源。系统必须能够判断分配资源是否安全，且只能在保证安全的条件下进行资源分配。

资源轨迹图

避免死锁的主要算法是基于一个安全状态的概念，在描述算法前，先讨论关于安全的概念。

假设现在我们有两个进程与绘图仪、打印机，我们使用一个轨迹图来描述它们。横轴表示进程 A 执行的指令，纵轴则为进程 B 执行的指令。进程 A 在 \(I_1\) 处请求一台打印机并在 \(I_3\) 处释放，在 \(I_2\) 处请求一台绘图仪，在 \(I_4\) 处释放；进程 B 则是 \(I_5 \sim I_7\) 之间使用绘图仪，\(I_6 \sim I_8\) 之间使用打印机。

资源轨迹图中的每个点代表两个进程的连接状态。初始点 p 表示没有进程执行任何指令。如果调度程序先选择 A 运行，那么 A 执行一段指令后到达 q，此时调度程序开始选中 B 执行。渐变部分是死锁状态，而 \(I_1\)、\(I_2\)、\(I_5\) 和 \(I_6\) 围成的矩形区域一旦进入，一定会进入渐变区造成死锁，因此整个矩形都是不安全区域。唯一的办法就是在 t 点开始调度程序一直让 A 运行直到 \(I_4\)。一旦过了不安全区域，调度程序即可以任意方式到达中断。

安全与不安全状态

在任何时刻，系统状态包含了 E (Existing)、A (Available)、 C (Current) 和 R (Request)。如果没有死锁发生，且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。在其他序列中，进程可能先占有一个资源而使其他进程无法完成需求，但进程可能先释放一个资源，从而使其他进程可以优先完成，从而避免死锁。因此需要注意的是，不安全状态不意味着死锁，而是安全状态系统保证所有进程都可以完成，但不安全状态无此保证。

银行家算法

我们十分熟悉的大神 Dijkstra 于 1965 年发表的算法，该模型基于一个小镇的银行家，他向一群客户分别承诺了一定的贷款额度。算法要做的是判断对请求的满足是否会导致进入不安全状态。如果是则拒绝请求，反之满足请求后系统仍是安全的，就给予分配。当然我们可以将银行家算法推广到多个资源的死锁预防。

现在我们现在系统中有 6 台磁带机、3 台绘图仪、4 台打印机和 2 台蓝光光驱，5 个进程对其的占有与请求如下图。

检查一个状态是否安全的算法如下：

1. 查找 Request 中是否有一行，请求的资源数小于或等于 Available Resource。如果不存在这样的行则认为系统将会死锁，因为任何进程都无法结束运行。
2. 若找到满足条件的行，那么可以认为其获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到 Available 上。
3. 重复以上两步，或者直到所有进程都标记为终止，其初始状态是安全的；或者所有进程资源都无法得到满足，发生死锁。

虽然 Banker Algorithm 十分强大，但由于很少有进程在运行初期就知道所需资源的最大值，且进程数与资源数是动态变化的，因此实际上很少有系统使用该算法避免死锁。但一些系统会从该算法之类的启发式方法来避免死锁。

死锁预防

虽然无法避免死锁，但我们还是可以从最初的四个必要条件说起，毕竟只需要破坏一个就可以保证死锁不会发生。

破坏互斥条件

如果一个资源不被进程所独占，那么死锁不会发生，但是允许两个进程同时使用某些资源，难免会发生混乱，比如打印机。因此反过来，如果任何时候都只有一个进程使用该资源，那么也不会造成 deadlock。想想之前所说过的 spooling 技术，仅允许 daemon 对资源进行请求，而其他进程以请求 daemon 的方式使用资源。并且 daemon 不再请求其他资源，因此不会造成 daedlock。

破坏占有等待条件

我们可以要求进程在开始时请求自己所需的全部资源，而在运行时将不再申请资源，这样的进程运行时一定不会发生死锁。当然我们还可以要求进程在请求资源时，首先释放当前已占有的所有资源，再请求所需的全部资源。

破坏不可抢占条件 :

破坏环路条件

我们可以对系统中的资源规定从小到大的统一编号，并且定义规则，所有请求必须按资源编号的升序提出。如果按照此规则进行实现，资源分配图中就不会出现环。当然在某些时刻，比如一些抽象资源会使编号变得很大，以至于根本无法使用编号。

其他问题

虽然在一般情况下避免死锁和预防死锁并不是很有希望，但一些特殊应用会有很优秀的算法应对死锁。

两阶段加锁

在数据库系统中，一个需要经常锁住一些记录，然后更新所有锁住的记录。当同时有很多进程运行时，就会出现死锁的危险。在此最常用的方法是 两阶段加锁 (two-phase locking)。第一阶段进程试图对所有所需的记录进行加锁，一次锁一个记录。如果第一阶段加锁成功则进行第二阶段，完成更新后释放锁。如果需要加锁的记录已被加锁，则需要释放该进程刚刚所加的所有锁。第一阶段的全部记录都被加锁后，进行第二阶段，即真正的修改数据阶段。当然这在实时系统中是不可接受的。

通信死锁

资源死锁是 竞争性同步 问题，这是最普遍但不是唯一一种死锁。而两个或以上进程利用发送消息来通信时也可能发生死锁。普遍的情况是：进程 A 想进程 B 发送请求信息然后等待进程 B 回复，当请求丢失后 A 将阻塞等待回复，而 B 会阻塞等待一个向其发送命令的请求。虽然进程 A 与 B 没有占用对方所需的资源，但它们依然发生了死锁，这种死锁一般被称为 通信死锁 (communication deadlock)。通信死锁是 协同同步 的异常情况，这种死锁中的进程如果是各自独立执行的，则无法完成服务。

由于没有资源，所以针对资源排序或安排调度来避免死锁是行不通的，幸运的是其可以使用 超时 来中断死锁。在大多数网络通信中，只要一个消息被发送且期待回信，通常会同时启动一个 Timer，如果 Timer 发生中断时回复消息还没有到达则认为发送的消息丢失。当然超时不仅可以用在通信死锁上，资源死锁也可以使用这种策略。

活锁

在某些情况下，当进程意识到它不能获取所需要的下一个锁时，自主地释放已经获得的锁，然后等待 1ms 并再次尝试。从理论上来说这是一种检测并预防死锁的好方法，但如果另一个进程也在同时刻做相同的事情，那么两个进程就永远的相遇并为对方让步，导致双方都无法前进。这种情况被称之为 活锁 (livelock)。在处理 livelock 时，我们尝尝为进程等待一个可接受范围内的随机时间，这样极大程度地避免 livelock 的发生。

饥饿

饥饿 (starvation) 与 deadlock / livelock 非常相似。在动态运行的系统中，任何时刻都有可能请求资源，在就需要策略来决定什么时候由谁获取资源。虽然这个策略表面上很合理，但某些进程可能永远得不到服务。

考虑进程调度的 SJF 算法，最短的作业总是被最先执行，而需要时间长的作业被放到之后完成。如果大量小型作业不停涌入，大作业将一直得不到服务。这个大作业就产生了 starvation。

当然我们可以在其上加入 FCFS 的思想，所有作业都会变老，而最老的作业将被服务，从而缓解系统的 starvation 现象。