跳转至

Lecture 17. 死锁（31 页）

资源 resource

  • 资源 resource，是指 不可共享 的东西。进程或者线程需要获取资源才能运行。
  • 等待进程/线程的队列可以与每种资源类型相关联。一个类别中的所有资源都是等效的，任何可用实例都可以满足对该类别中资源的请求。==？==

对于系统管理的资源，会有一个 system table，维护每一个资源是 free 的还是被使用的。如果被使用，被谁使用。

应用程序可能会拥有属于自己的 user level 的资源。系统可以监测系统资源是否存在死锁，但是无法监测那些 user level 的。比如，Windows 操作系统无法检测 JVM 里面的资源。

因此，程序员在写并行代码的时候必须格外小心，不要让死锁发生。用完资源就要及时释放掉。分配资源的时候也要指定一个好策略。

对于资源，有主要三种操作：

  • 请求 request，也就是 open()，acquire()，malloc() 之类的。如果请求的资源暂时不可用，就等
  • 使用 use，也就是处理资源
  • 释放 release，也就是 close()，release()，free() 之类的。

资源分配图 resource allocation graph

是一种有向图。可以用来描述死锁。

  • 这种图里面的节点有两种类型，圆圈表示活动的进程，方块表示某一类型的资源。
  • 资源方块里面可能有一些小点点，表示这个资源有多少个 instance
  • 进程向资源连边，表示这个进程正在等待这个资源。
  • 资源向进程连边，表示这个资源已经被分配给了这个进程

当且仅当这个图当中存在一个环，死锁才会存在。

那么如何判断一个有向图当中是否存在环？可以使用 Tarjan 算法，时间复杂度 $O(n+m)$，但这有点杀鸡用牛刀的感觉。直接随便选一个点开始 dfs，如果访问到了之前访问过的点，那么就是有环。

比如上图，不存在环，所以不会有死锁。但是下图 P3 向 R2 连边了，于是就可能有死锁了。

注意，并不是只要有环就一定会死锁。比如下图虽然存在环，但是只要 P4 释放了资源 R2，就相当于破环了。

死锁

定义：A set of processes is in a deadlock state when every process in the set is waiting on an event that can be caused only by another process in the set. 一个集合当中的进程，每一个进程都在等待只能由其他进程所引起的事件（比如资源释放）。那么，这一组进程，就处于死锁状态。

死锁的四个必要条件 necessary conditions

以下四个条件，必须同时满足，才会出现死锁的状况。

  • 互斥 mutual exclusion：存在至少一个资源要处于非共享模式，即一次只有一个进程可以使用的模式。如果另一个进程想要申请这个资源，就必须等到释放。
  • 占有并等待 hold and wait：一个进程本身占有了一个资源，同时还在等待另一个进程的资源。
  • 非抢占 no preemption：资源只能是被一个进程用完之后主动释放掉，不能是中途被抢占
  • 循环等待 circular wait：进程 P0 等 P1 释放，P1 等 P2 释放，P2 等 P3，P3 等 P0，构成一个环

死锁的处理方法

  1. 确保系统不会进入死锁
    1. 预防 prevention
    2. 避免 avoidance
  2. 允许系统进入死锁，然后检测并恢复 recover
  3. 忽视这个问题，就当死锁一定不会发生（as in Unix）

预防死锁

刚才不是说死锁有四个必要条件吗，只要想方设法让其中一个条件无法成立，那就相当于预防了死锁。

通常的办法是限制资源的请求。

  1. 互斥，这个条件必须满足，不能破。考虑其他三个条件能不能破。
  2. 占有并等待，这个好破。只要把所有资源放在一起申请就好了。但是可能会饥饿。
  3. 非抢占，这个好破，需要资源的时候，如果被别的进程占用了，那就直接抢过来
  4. 循环等待，能破，但是麻烦一点：对所有资源类型进行排序。假如一个进程需要 1 5 12 三个资源，那么必须按顺序申请。假如已有了 12 还想要 5，必须先释放掉 12 再重新申请 5 12。可以用反证法证明，这个做法确实能破第四个条件。

避免死锁

刚才通过限制四个条件之一的方法来预防死锁，有副作用，就是会降低设备使用率和系统吞吐率。

避免死锁，需要额外信息，即如何申请资源。系统在分配资源的时候会 more cautiously，会考虑现在的可用资源、现在已经分配给每个进程的资源、每个进程将来会申请和释放的资源。

安全状态 safe vs unsafe

安全状态的定义是：如果系统能够按照一定的顺序，为每个进程分配资源（不超过最大需求），可以避免死锁，那么这个系统就处于安全的状态。

形式化的讲，进程序列 $\langle P_1, P_2, \cdots, P_n \rangle$ 处于安全状态是指：对于第 $i$ 个进程，它仍然可以申请的资源的总量，小于所有在他前面的进程所占有的资源的总量，加上当前可用资源总量，即 $$(它仍然需要申请的资源) < (所有在他前面的进程所占有的资源) + (当前可用资源)$$，也就是说，即使当前暂时无法申请资源，等前面所有进程释放掉之后，就能申请了。

假如对于一组进程，找不到这样的安全状态，那么这个系统就处于非安全状态（unsafe）。

安全的不死锁。非安全的不一定会导致死锁（你可以全部释放然后重新规划资源分配），但是死锁一定是非安全的。三者关系如图所示。

银行家算法 banker's algorithm

顾名思义，有一个银行家，遇到了很多借钱（可能还要借房子、借大金链子、借车等等等等）的请求。对于每个请求，银行家需要考虑，借出去之后还能不能再满足其他人的借钱请求。

顺便：如果你去银行，说借五百块钱，买水泥，用来准备盖房子。那么银行可能不愿意鸟你。假如你说借十万块钱，买水泥买钢筋买砖块顺便装修，那么银行可能愿借给你钱。

假设有 $n$ 个进程和 $m$ 种资源。银行家算法需要如下数据：

  • int available[m]，表示第 $i$ 种资源的可用的 instance 的数量
  • int max[n][m]，表示第 $i$ 个进程的整个生命周期内，最多用多少个 $j$ 类型的资源
  • int allocation[n][m]，表示第 $i$ 个进程已经分配到了多少个类型 $j$ 的资源
  • int need[n][m]，表示第 $i$ 个进程可能还需要多少个 $j$ 类型资源，满足 max[i][j] = allo[i][j] + need[i][j]。

示例：有 ABC 三个资源，数量总共分别是 10 5 7，在初始时刻五个进程已分配到的资源以及它们所需要的最大资源量如下表所示：

那么此时，ABC 就还剩 3 3 2 个。

可以找到一个序列 $\langle P_1, P_3, P_4, P_2, P_0 \rangle$，避免死锁。

银行家算法的具体描述

具体算法过程可以参考课件 18~27 页。也可以参考 这篇文章。不知道期末考试会不会有这个计算题，最好看看还是。

死锁检测和恢复

需要两个算法。一个检测资源分配图当中是否存在环（是否可能有死锁），另一个算法负责从死锁当中恢复。

当然了，不能所有时候都检查一下是否存在死锁，要不然性能肯定会下降！所以只有在特定情况下才进行检测。比如，CPU usage 低于阈值且有进程未完成的时候，或者资源繁忙（busy）无法进行分配的时候。

恢复死锁比较简单，通常有两种方式，一种是直接打断某个引起死锁的进程，另一种是让一个进程直接抢占资源。

打断或者终止进程：

  • 可以是打断所有的死锁进程，但是代价太大了。
  • 也可以是一次终止一个，然后检测死锁还有没有，如果有继续终止。但是根据什么因素决定终止进程是谁？优先级还是占用资源的数量？不好说。

抢占资源：

  • 从哪个进程那边抢？怎样让代价尽量小？不好说。
  • 被抢的那个进程怎么办？需要给他设置好 checkpoint，将来用于回滚 rollback。