死锁的定义

一组进程中，每个进程都无限等待被该组进程中另一进程所占用的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

活锁和饥饿

  • 活锁：一组进程既无进展也没有阻塞，由于某些条件不满足导致一直在轮询。
  • 饥饿：资源分配策略导致的错误。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public void process_A() {
        enter_region(&resource_1);
        enter_region(&resource_2);
        use_both_resources();
        leave_region(&resource_2);
        leave_region(&resoutce_1);
    }

    public void process_B() {
        enter_region(&resource_2);
        enter_region(&resource_1);
        use_both_resources();
        leave_region(&resource_1);
        leave_region(&resoutce_2);
    }

死锁产生的必要条件

产生死锁需要满足四个条件：

  1. 互斥使用（资源独占）：一个资源每次只能给一个进程使用。
  2. 占有且等待（请求和保持）：进程在申请新的资源的同时保持对原有资源的占用。
  3. 不可抢占：资源申请者不能强行的从资源占有者手中夺取资源，资源只能等待占有者自愿释放。
  4. 循环等待：多个进程组成一个环路，环路中的每个进程都在等待下一个进程所占用的资源。

资源分配图

系统由若干类资源构成：

  • 资源类：某一类资源称为一个资源类，用方框表示；
  • 资源实例：每个资源类中包含若干个同种资源，称为资源实例；

image.png
如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。

资源分配图的化简

  1. 找一个非孤立、且只有分配边的进程结点，去掉分配边，将其变为孤立结点。
  2. 再把相应的资源分配给一个等待该资源的进程，即将该进程的申请边变为分配边。

如果一个图可完全化简（所有的资源和进程都变成孤立的点），则不会产生死锁；如果一个图不可完全化简（即图中还有边存在），则会产生死锁。

死锁预防

在设计系统时，通过确定资源分配算法，排除发生死锁的可能性。
只要防止产生死锁的四个必要条件中的任何一个条件发生即可。

破坏“互斥使用”条件

把独占资源变为共享资源。例如 SPOOLing 技术把所有用户进程的输出都送入输出井，然后再由输出进程完成打印工作，而输出井在磁盘上，为共享设备。这样，SPOOLing技术就把打印机等独占设备改造成立共享设备。

破坏“占有且等待”条件

  • 实现方案一：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。
    • 问题：资源利用率低，会出现饥饿现象。
  • 实现方案二：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。

破坏“不可抢占”条件

当一个进程申请的资源被其他进程占用时，可以通过操作系统抢占这一资源（两个进程的优先级不同）。

局限性：适用于状态易于保存和恢复的资源，例如内存。

破坏“循环等待”条件

通过定义资源类型的线性顺序实现。

把系统中的所有资源编号，进程在申请资源时必须严格按照资源编号的递增次序进行，否则操作系统不予分配。

通常会按照资源使用的频繁编号。

死锁避免

在系统运行的过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统发生死锁或可能发生死锁，则不予分配，否则予以分配。

安全状态

如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
image.png
例如从图 a 开始出发，先让 B 拥有所需的所有资源（图b），运行结束后释放 B，此时 Free 变为5（图c)；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 是安全状态。

不安全状态

如下图所示，图 b 即为不安全状态，因为它不能满足让后续的进程运行完毕。
image.png

银行家算法

单个资源条件

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
image.png
上图中，图 c 是一个不安全的状态。因为无论如何都不能满足任何一个客户的请求，所以算法会拒绝之前的请求，避免进入不安全状态。

多个资源条件

image.png 上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 为三个向量，分别表示：总资源、已分配资源以及可用资源。例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。 检查一个状态是否安全的算法如下：
  • 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
  • 如果存在这样一行，将该进程标记为终止，并将其左图中的已分配资源加到 A 中。
  • 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，算法需要拒绝进入这个状态。

死锁检测与解除

  • 允许死锁的发生，但是操作系统会不断监视系统进展情况，判断死锁是否真的发生。
  • 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。

    检测时机：

    1. 当进程由于资源请求不满足而等待时检测死锁
    2. 定时检测
    3. 系统资源利用率下降时检测死锁

死锁检测

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

判断资源分配图是否满足环路等待条件，具体来说是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
image.png

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

同多个资源条件时的银行家算法。
image.png

死锁解除

  • 利用撤销所有死锁进程解除
  • 利用抢占解除
  • 利用回滚再启动解除
  • 通过杀死进程解除

鸵鸟算法

鸵鸟：把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。
大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

哲学家进餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。
image.png
错误解法：如果所有的哲学家同时拿起了左边的筷子，那么所有哲学家都没有办法拿起右边的筷子，导致死锁。

1
2
3
4
5
6
7
8
9
10
11
12
#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // 拿起左边的筷子
        take((i+1)%N); // 拿起右边的筷子
        eat();
        put(i);
        put((i+1)%N);
    }
}

防止死锁发生的解法：

  • 最多允许 4 个哲学家同时坐在桌子周围。
  • 仅当一个哲学家左右两边的筷子都可以使用时，才允许他拿筷子。
  • 给所有的哲学家编号，奇数哲学家必须首先拿左边的筷子，偶数哲学家反之。

参考

  1. CS-Note：死锁
  2. 北京大学操作系统原理（Operating Systems）
  3. Modern operating systems