死锁的定义

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

死锁与活锁的区别

活锁指的是一组进程既无进展也没有阻塞 ，由于某些条件没有满足，导致一直重复尝试并失败。例如错误地使用Pertonson算法：

活锁

产生死锁的必要条件

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

资源分配图

系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。用方框表示资源类，用方框中的黑圆点表示资源实例，用圆圈中加进程名表示进程。如果资源分配图中没有环路，则系统中没有死锁， 如果图中存在环路则系统中可能存在死锁。

RAG

资源分配图化简

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

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

死锁预防

防止产生死锁的四个必要条件中任何一个条件发生，以此排除发生死锁的可能性。

破坏“互斥使用”条件

把独占资源变为共享资源。例如在SPOOLing系统中，实际上并没有为任何进程分配这台打印机，而只是在输入井和输出井中，为进程分配一存储区和建立一章I/O请求表。这样，便把独占设备改造为共享设备。

破坏“占有且等待”条件

实现方案一：要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。

实现方案二：在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资 源，若需要再重新申请。

破坏“不可抢占”条件

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

破坏“循环等待”条件

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

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

死锁避免

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

安全状态

如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态

例如，图a的第二列Has表示已拥有的资源数，第三列Max表示总共需要的资源数，Free表示还有可以使用的资源数。从图a开始出发，先让B拥有所需的所有资源（图b），运行结束后释放B，此时Free变为5（图c）；接着以同样的方式运行C和A，使得所有进程都能成功运行，因此可以称图a所示的状态时安全的。

单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

bank

由图可知，状态b进入状态c是进入了一个不安全的状态，因此恢复原来状态，避免了进入不安全状态。

多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的E、P以及A分别表示：总资源、已分配资源以及可用资源。

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

  1. 查找右边的矩阵是否存在一行小于等于向量A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
  2. 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到A 中。
  3. 重复以上两步，直到所有进程都标记为终止，则状态是安全的。

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

bank

死锁检测与解除

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

死锁的检测

死锁的检测与银行家算法几乎一样，此处不再阐述。

死锁的解除

  • 利用抢占恢复
  • 利用回滚恢复
  • 通过杀死进程恢复

鸵鸟算法

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

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

哲学家就餐问题

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

哲学家就餐问题

下面是一种错误的解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。

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个哲学家同时坐在桌子周围。
  • 规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。

参考资料