《现代操作系统》的学习笔记，这一章是死锁。

死锁

死锁发生的情况

假设现在有两个进程A和B，以及两个资源M和N。现在A进入临界区操控M，B在N的临界区操控N。这时，在临界区中的A需要使用N，但是由于N被B使用着，所以A必须等待。而巧的是，B这时也需要M，于是B等待A释放M，而A却等待B释放N，双方都在等待对方释放资源，从而无法继续执行进程，这就叫做死锁。

书上的定义如下：

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

进程死锁需要以下四个条件：

互斥条件：一个资源要么被分配给了一个进程，要么没被分配。
占有和等待条件：已经得到某个资源的进程可以要求新的资源
不可抢占条件：进程的资源不能被抢占，只能由进程主动释放
环路条件：死锁发生时，系统中一定有两个或者两个以上的进程组成环路。组成环路的进程是死锁的。

这里解释一下资源的可抢占性，资源分为两种：可抢占的和不可抢占的。可抢占的意思就是在进程使用这个资源的时候，另一个进程可以把资源抢过来而不经过原进程的同意。不可抢占的就是不能抢过来，只能由持有进程自己释放。显然可抢占资源并不会造成死锁。

这里的环路条件也是我们判断进程是否死锁的方法：简单来说，我们需要一个进程资源图来表示系统中某一时刻的进程和资源的情况，比如下面这个：

进程资源占用图

这里方的是进程，圆的是资源。从进程指向资源的箭头（橘色的）表示进程在请求这个资源。从资源指向进程的箭头（绿色的）表示这个资源被这个进程拥有。

判断是否死锁的方式就是找图中有没有回路，显然B，C，S，R构成了回路，所以B和C死锁了。

死锁的解决办法

大体上有两种解决办法：发生死锁想办法去解决它和直接避免死锁。

死锁检测和死锁恢复

先来说明死锁发生之后再解决的方法。这叫做死锁恢复。那么显然，要死锁恢复的话必须先知道有没有死锁，所以得先了解死锁检测算法。

死锁检测

每种类型一种资源

先考虑当每种类型的资源只有一个的时候，这个时候我们可以绘制出进程资源图，然后遍历这个图，如果遍历到了已经遍历过的节点，那么显然存在环路，也就存在死锁。

进程资源图2

每种类型多个资源

这个时候需要用矩阵来解决，首先存在$E$向量，是存放着不同种类资源的资源数目的向量：

     磁带机 绘图仪 扫描仪 CD-ROM
E = [  4     2     3      1]

然后存在一个$C$矩阵，是当前所有进程占用资源的情况： $$ C= \begin{bmatrix} 0 & 0 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ 0 & 1 & 2 & 0 \\ \end{bmatrix} $$ 列是和E相对应的资源，行是进程。也就是说，第一行$\begin{bmatrix}0 & 0 & 1 & 0\end{bmatrix}$就是进程1所占用的资源，分别是0个磁带机，0个绘图仪，1个扫描仪和0个CD-ROM。

然后通过C矩阵和E向量，我们可以很快速得到当前剩余资源向量A： $$ A= \begin{bmatrix} 2 & 1 & 0 & 0 \end{bmatrix} $$ 最后是当前时刻所有进程的请求矩阵$R$ $$ R= \begin{bmatrix} 2 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 \\ \end{bmatrix} $$ 第一行就表示进程1要请求2个磁带机和1个CD-ROM。

想要找出死锁，就需要一步一步满足请求矩阵R。首先进程1的请求不能被满足，因为已经没有CD-ROM了。进程2也不行，因为没有扫描仪了。但是进程3可以，于是系统将资源分配给进程3，进程3使用完之后返还资源，于是现在的各个图变成这样： $$ A = \begin{bmatrix}2 & 2 & 2 & 0 \end{bmatrix} C = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} R= \begin{bmatrix} 2 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$ 然后资源就可以分配给进程2，进程2使用完之后返还资源，再次分配给进程1即可。所以这整个过程中没有死锁。

如果出现了哪一步所有进程都没办法分配资源的话，就会导致死锁。

死锁恢复

恢复的方式有三种，都是很好理解的：

利用抢占恢复：如果资源是可抢占的，可直接抢占。
利用回滚恢复：当进程进入临界区之前保存进程状态，如果存在死锁，则恢复到进入临界区之前的状态。
通过杀死进程恢复：将死锁的进程搞死也是一种方法。

可以看出，无论哪种其实效果都不是很好。所以处理死锁最好的方法就是避免死锁。

死锁避免

进程资源轨迹图

避免死锁主要是依靠安全状态。首先来看一个人可以识别的方法（机器几乎不能，考试专用方法）：绘制进程资源轨迹图：

进程资源轨迹图

横坐标是A占用资源的时间，纵坐标是B占用资源的时间。右上角的u点是A和B都在这个资源上工作完毕的事件。我们的目标就是从原点p到达u点。在I1到I3时间点内，A需要占用打印机，在I2到I4时间内，A需要占用绘图机。而B则是在I5到I7时间之间占用绘图机，在I6到I8之间占用打印机。

虚线是资源的被占用状态，比如p到q资源一直在A轴上移动，代表资源被A占用。而q到r则在B轴方向上移动，代表资源被B占用。

那么显然，不能让资源走到由I2，I3，I6，I7围成的公共区域S中，因为这个区域中A占用着打印机却请求绘图机，B占用绘图机却请求打印机，会产生死锁。所以这个让资源从p到u的不死锁路径就是绕过公共区域S的路径。

单种类资源的银行家算法

现在假设只存在一种种类的资源，并且我们知道当前资源的占有情况和每个进程所需资源的最大情况：

资源占有情况

假设现在是图(a)的情况，A进程占有3个资源，最大需要9个资源，B占有2个，最大需要4个，C占有2个，最大需要7个。并且系统现在有3个剩余资源。

银行家算法的思想就是：存不存在一种分配方法，使得所有进程都可以顺利完成自己的工作。

这里我们将剩余的3个资源中的2个先分配给B，这样就到达图(b)，B利用完资源后返回，到达图(c)，这个时候就有5个多余资源，那么分配给C，到达图(d)，C使用完之后返还资源，到达图(e)。那么显然最后A可以分配，所有进程都可以完成自己的工作。

安全状态就是指资源分配后可以保证下一步的资源分配（也就是不造成死锁），上图的5个步骤都是安全的。不安全就是指分配资源后会引发死锁。比如我第一步将3个资源分配各A，那么显然后续就没办法进行下去了。

多种类资源的银行家算法

其实也很简单，这里需要用到“每种类型多个资源”一节中的E，A，C，R图：

多种资源类型的银行家算法

分配的算法很简单：将E向量减去每一行的资源占用向量，如果存在负数部分，表示分配给这个进程后会死锁，就不分配，直到找到结果各分部都大于0的行，分配给这个行所代表的进程，进程用完资源后回收，标记这个进程已经结束，然后再次进行下一轮分配。

死锁预防

显然死锁避免是不可能的，因为根据死锁避免算法，系统需要知道死锁的最大资源请求数量，也就是说系统得知道进程未来的资源请求情况。这是不现实的。

在真正实践中，一般是通过打破死锁的四个必要条件中的一个或多个来预防死锁。

活锁

活锁和死锁差不多，只不过不是进程被阻塞，而是由于轮询机制导致的无休止的等待。比如下面的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void process_A(){
  enter_region(resource_1);
  enter_region(resource_2);
  do_something_with_resources();
  leave_region(resource_2);
  leave_region(resource_2);
}

void process_B(){
  enter_region(resource_2);
  enter_region(resource_1);
  do_something_with_resources();
  leave_region(resource_1);
  leave_region(resource_2);
}

当A进入resource1时B进入resource2，那么会产生活锁：两个进程通过论讯的方式不停地要求资源2和资源1。

饥饿

饥饿是指在论讯的过程中，总是有进程一直得不到资源。比如优先级最高算法，优先级高的进程先使用资源，那么低优先级的进程将可能等待很长一段时间，这就是饥饿。

操作系统-6-死锁