Deadlock

约 4621 个字 9 张图片 预计阅读时间 15 分钟

Outline

• 什么是死锁问题：死锁问题的定义
• 建模资源分配模型并得出死锁的条件：系统模型与资源分配
• 如何处理死锁问题：死锁的处理策略

死锁问题

定义：A set of blocked process each holding a resource and waiting to acquire a resource held by another process in the set.

大多数操作系统并不预防或者处理死锁。很多都采用鸵鸟的解决方式——忽略死锁问题并且假装死锁从来没有在操作系统中发生过。

系统模型与资源分配

1. 系统模型

一个系统拥有优先数量的资源亟待分配给若干个竞争线程，这些资源可以分成多种类型，每种类型的资源有多个实例。资源类型很多，比如 CPU、文件和 I/O 设备等等。如果一个线程申请某一个资源类型的一个实例，那么分配这种资源类型的任何实例也可以满足申请，否则这些实例就不相同，我们也没有正确定义资源分类。类似的，信号量和互斥锁也是资源的一种，这也是现代计算机系统最常见的死锁来源。

线程在使用资源前必须请求资源，使用后必须释放资源，线程可以请求执行指定任务所需的尽可能多的资源。正常操作模式下，线程可以仅按照以下顺序使用资源：

• 申请：线程请求资源，如果申请不能立刻被允许，申请线程必须一直等待，直到资源可用。
• 使用：线程对资源进行操作。
• 释放：线程释放资源。

当线程每次使用内核管理的资源时，操作系统会检查以确保该线程已经请求并获得了资源，系统表记录每个资源是否是空闲的或者已分配的，对于每个已经分配的资源，申请表记录它被分配的线程，如果线程申请的资源正在被其他线程占用，该线程就会被添加到该资源的等待队列中。

2. 系统资源分配图

通过成为系统资源分配图/Resource Allocation Graph 的有向图可以精准描述死锁。系统资源分配图包括节点集合 \(V = P \cup R\) 和边集合 \(E\)，其中 \(P\) 是线程的集合，\(R\) 是资源的集合，\(P\) 和 \(R\) 互斥，\(E\) 是线程和资源之间的边。

从线程 \(P_i\) 到资源 \(R_j\) 的边表示线程 \(P_i\) 请求资源 \(R_j\)，也就是申请边/Request Edge；从资源 \(R_j\) 到线程 \(P_i\) 的边表示资源 \(R_j\) 分配给线程 \(P_i\)，也就是分配边/Assignment Edge。

在资源分配图上，我们使用圆表示线程，使用方块表示资源类型，由于资源类型可能有多个实例，所以矩形内的点的数量表示实例数量，申请边应该从线程指向资源类型，分配边应该从资源类型内的实例指向线程。

3. 死锁的条件

如果在一个系统中下面四个条件同时成立，那么就能引起死锁：

• 互斥/Mutual Exclusion：如果一个资源必须处于非共享模式，也就是一次只有一个线程可以使用。如果另一个线程申请该资源，那么申请线程必须等到资源被释放。
• 占有并等待/Hold and Wait：一个线程应该占有至少一个资源，并等待另一个资源，而该资源被其他线程占有。
• 非抢占/No Preemption：资源不能被抢占，只能被线程完成任务后自愿释放。
• 循环等待/Circular Wait：有一组等待线程 \(P_1, P_2, \cdots, P_n\)，其中 \(P_1\) 等待 \(P_2\) 占有的资源，\(P_2\) 等待 \(P_3\) 占有的资源，\(P_n\) 等待 \(P_1\) 占有的资源。

只有所有四个条件同时满足才会出现死锁。四个条件并不是完全独立的，其中循环等待蕴含着占有并等待。

放到资源分配图上看：如果资源分配图上没有环，系统就不处于死锁状态；若有环，系统可能会也可能不会处于死锁状态。

• 如果每个资源类型刚好有一个实例，那么有环就等价于死锁；
• 如果环上只涉及一组资源类型，且环上的资源类型每个就只有一个实例，那么有环就等价于死锁；
• 如果环上的资源类型有多个实例，那么有环不一定等价于死锁，某个资源实例可以释放并且分配给环上的其他线程，这就盘活了系统。

死锁的例子

第一个的确锁上了，第二个没锁上，等 \(P_2\) 或 \(P_4\) 释放资源就活了。

死锁的处理

1. 死锁预防

死锁预防/Deadlock Prevention 方案确保至少有一个死锁的必要条件不成立，这些方法通过限制如何申请资源的方法预防死锁。

1. 互斥：互斥条件必须成立，系统至少有一个资源应是非共享的，而共享资源不要求互斥访问，因此不会参与死锁。
2. 占有并等待：保证每一个进程在申请资源的时候不占有别的资源。一个方法是线程在执行前申请所有可能需要的资源，但是这种策略对大多数应用程序是不切实际的。另一种是只允许线程在没有资源的时候才可以申请资源，一个线程可以申请一些资源并且使用他们，但是在申请新的资源之前应该将这些资源全部释放再申请。这两种方法的统一问题都是资源利用率很低，并且可能会引起饥饿。
3. 非抢占：如果一个线程申请一个另一个不能立刻分配的资源，那么其持有的所有资源都可以被抢占（也就是隐式释放掉所有资源），被抢占的资源被加到它等待的资源列表上，只有当线程获得其原有资源和所有等待资源的时候，其才可以继续执行。问题还是很大，这通常用于状态可以轻松保存和稍后恢复的资源，比如 CPU 寄存器，但是对于诸如信号量和互斥锁之类的资源不能应用。
4. 循环等待：对所有资源类型进行完全排序，要求每个进程按照递增顺序申请资源。若是进程申请了某个资源，那么其应该先释放持有的比该资源更高序的所有资源，在此之后申请该资源。如果申请同一资源的多个实例，需要同时申请所有实例。很多操作系统都实现了这个方案，但是如果程序员不听话，这个方案也是无效的，这种方法也可能影响资源利用率。

解决循环等待的方案本身没有问题，除了程序员的问题和利用率的问题之外，还有一个就是很多场合下并不能完全排序资源。并且开发排序或层级结构本身并不能防止死锁；如果可以动态获取锁，那么加强锁排序并不能保证防止死锁。

2. 死锁避免

死锁避免/Deadlock Avoidance 要求操作系统事先得到有关线程申请资源和使用资源的额外信息，有了这些信息，系统可以确定对于每个申请，线程是否应该等待。最简单且最有用的方案是每个线程应该声明其可能需要的资源的最大数量，基于这个先验信息，我们就有可能构造一个算法，使得可以合适规划资源分配，使得系统不会进入死锁状态。

首先，我们需要知道什么是安全状态：如果系统可以按照一定的顺序为每个线程分配资源，同时避免死锁，我们就说系统的状态是安全的。若是存在一个线程序列 \(\{ P_1, P_2, \cdots, P_n \}\) 使得对于每个线程 \(T_i\)，其可以申请的资源小于当前可用资源加上前面的线程 \(T_j\) 所占有的资源， 那么就称这个线程序列是安全的。只有存在一个安全序列/Safe Sequence，系统才是安全的。

安全状态不是死锁状态，死锁状态是非安全状态，非安全状态就有可能出现死锁。这很直观：使用归纳法，如果线程 \(T_i\) 的要求不能立刻被满足，那么其等待前面的线程 \(T_j\) 全部完成，这样 \(T_i\) 就可以获取全部资源了。

基于安全状态，我们可以定义避免算法，基本想法是确保系统始终处于安全状态：最初，系统一定处于安全状态，只有当一个线程申请一个可用资源的时候，系统应该确定进行这个资源分配之后系统仍然处于安全状态，如果不是，那么线程应该等待。

对于每种资源类型只有一个实例的资源分配系统，我们可以使用资源分配图算法来避免死锁：除了申请边和分配边之外，我们新定义需求边/Claim Edge，从线程 \(P_i\) 到资源 \(R_j\) 的需求边使用虚线表示，代表可能在将来某个时刻线程 \(P_i\) 会请求资源 \(R_j\)。当线程申请资源的时候的时候，需求边就变成了申请边；当资源被分配给线程的时候，申请边就变成了分配边；当线程释放资源的时候，分配边就变成了需求边。

使用死锁避免的时候，系统资源的需求应该提前说明，当线程 \(T_i\) 开始执行的时候，所有的需求边都应该处于资源分配图之内。假设某个 \(T_i\) 申请资源 \(R_j\)，我们只有将申请边 \(T_i \to R_j\) 变成分配边 \(R_j \to T_i\) 之后不形成环才可以将资源分配给 \(T_i\)，否则就要让这个线程等待。下面的资源分配就是错误的：

对于每种资源类型不只有一个实例的资源分配系统，我们需要引入银行家算法：首先需要下面的数据结构。

• Available：一个长度为 \(m\) 的向量，表示每种资源类型的可用实例数量；
• Max：一个 \(n \times m\) 的矩阵，表示每个进程最大需要的资源数量；
• Allocation：一个 \(n \times m\) 的矩阵，表示每个进程已经分配的资源数量，具体而言，第 \(i\) 行表示进程 \(P_i\) 已经分配的资源数量；
• Need：一个 \(n \times m\) 的矩阵，表示每个进程还需要的资源数量，数值等于 Max - Allocation。
• Work：一个长度为 \(m\) 的向量；
• Finish：一个长度为 \(n\) 的向量，表示每个进程是否可以继续执行。

定义检测安全算法为：

1. 初始化 Work 为 Available，Finish 为 false；
2. 找到一个进程 \(P_i\)，满足 Finish[i] == false 且 \(Need_i \leq Work\)，如果找不到这样的进程，跳到第 4 步；
3. 让 \(Work = Work + Allocation_i\)，Finish[i] == true，转到第 2 步。
4. 如果所有进程都满足 Finish[i] == true，那么系统是安全的，反之系统是不安全的。

设 \(Request_i\) 为进程 \(P_i\) 的请求向量，如果 \(Request[i][j] = k\)，那么 \(P_i\) 请求 \(R_j\) 的 \(k\) 个资源，定义资源分配算法：

1. 如果 \(Request_i \leq Need_i\)，转到第 2 步，否则进程 \(P_i\) 请求资源超过了其最大需求，出错；
2. 如果 \(Request_i \leq Available\)，转到第 3 步，否则进程 \(P_i\) 请求资源超过了系统可用资源，进程 \(P_i\) 必须等待；
3. 假定系统可以分配给 \(P_i\) 资源，按照下面方式修改状态：Available = Available - Request_i，Allocation_i = Allocation_i + Request_i，Need_i = Need_i - Request_i。然后使用检测安全算法检查系统是否是安全的，如果是，那么资源分配给 \(P_i\)，否则资源不分配给 \(P_i\)，\(P_i\) 必须等待并且回滚资源分配状态。

PPT 上的例子

第一个产生了下面的安全序列，第二个就无论如何都找不到安全序列了。

3. 死锁检测

我们允许系统既不采用死锁预防算法和死锁避免算法来防止系统进入死锁的状态，但是我们需要检测死锁并且从死锁状态恢复。这要求系统提供：

• 一个用来检查系统状态从而确定是否出现死锁的算法；
• 一个用来从死锁状态中恢复的算法。

检测死锁的一种方法是维护一个资源分配图的变种：等待图/Wait-for Graph。从资源分配图删除所有的资源类型节点，合并适当边，就可以得到等待图：

确切来讲，等待图中从进程 \(P_i\) 到进程 \(P_j\) 的边表示 \(P_i\) 等待 \(P_j\) 释放一个资源。当且仅当在等待图中有一个环的时候系统死锁。在图里找环的时间复杂度是 \(O(V + E)\) 的，最坏情况是 \(O(n^2)\) 的复杂度。

对于每种资源类型有多个实例的情况，我们使用很类似于银行家算法的算法解决：对于有 m 个资源类型和 n 个进程的情况，我们需要下面的数据结构

• Available：一个长度为 \(m\) 的向量，表示每种资源类型的可用实例数量；
• Allocation：一个 \(n \times m\) 的矩阵，表示每个进程已经分配的资源数量，具体而言，第 \(i\) 行表示进程 \(P_i\) 已经分配的资源数量；
• Request：一个 \(n \times m\) 的矩阵，表示每个进程还需要的资源数量；
• Work：一个长度为 \(m\) 的向量；
• Finish：一个长度为 \(n\) 的向量，表示每个进程是否可以继续执行。

算法的步骤如下：

1. 初始化 Work 为 Available，Finish 为 false；
2. 找到一个进程 \(P_i\)，满足 Finish[i] == false 且 \(Request_i \leq Work\)，如果找不到这样的进程，跳到第 4 步；
3. 让 \(Work = Work + Allocation_i\)，Finish[i] == true，转到第 2 步。
4. 如果所有进程都满足 Finish[i] == true，那么系统不死锁，反之系统死锁。

也就是一旦确定 \(Request_i \leq Work\)，我们就知道线程 \(P_i\) 不参与死锁，也就是它不需要更多的资源来完成任务，并且返回已经分配的所有资源，因此就收回进程 \(P_i\) 的资源，然后继续检查其他进程。

PPT 上的例子

第一个是没锁上的例子，第二个例子不存在一个安全的分配序列，会产生死锁。

检测算法的使用：取决于死锁发生的频率和死锁发生时有多少线程会受到影响。

4. 死锁恢复

死锁恢复有两种选择：一个是简单地终止一个或多个线程来打破循环等待，另一个是从一个或多个死锁线程中抢占资源。

终止进程有两种选项：

• 终止所有死锁进程：代价很大；
• 一次终止一个进程，知道死循环消除为止：开销也很大，因为每次终止进程之后都需要调用死锁检测算法，并且我们需要考虑终止哪个进程。

首先，终止进程并不简单：终止进程应该维护终止时的状态，并且很有可能计算一些内容，避免重复的副作用。比如如果进程正在更新文件，终止进程就会让文件处于错误的状态；如果进程正在持有互斥锁的同时更新数据，我们就必须将锁的状态恢复到可持有的，但是我们显然难以保证共享数据的完整性。

其次，我们该如何选择终止的进程呢？这个问题基本上是经济问题，需要考虑下面因素：

• 进程的优先级；
• 进程已经计算了多久，并且在完成之前还要花多久；
• 进程使用了多少数量的哪些资源；
• 还需要终止多少进程；
• 这个进程是交互式进程/interactive 还是批处理进程/batch process。

如果通过资源抢占来消除死锁，我们应该不断抢占一些进程的资源来让给别的进程使用，直到死锁循环被打破为止。我们需要考虑下面的问题：

• 选择牺牲进程：需要抢占哪些进程的哪些资源，这个问题和终止进程的问题类似；
• 回滚：我们需要好好安排被抢占资源的进程，显然这个进程不能继续正常执行，我们应该将这个进程回滚/Rollback 回到一个安全状态，以便在该状态重启进程。一般来说，很难界定什么是安全状态，最简单的方法就是完全回滚，也就是终止进程并且重新执行，更有效的方法是回滚进程到足够打破死锁，但是这种方法要求系统维护相关进程足够的状态信息。
• 饥饿：如何确保资源不会总是从同一个进程被抢占？

如果一个系统是基于代价选择牺牲进程，那么同一进程很可能总是被选择成被牺牲的，那么这个进程很可能永远也不会完成任务，所有实际系统都必须处理这种情况，应该确保一个进程只能有限次被选择成牺牲进程，最常用的办法就是在代价因素中加上回滚次数。