6.1 死锁的引入

在之前我们或多或少都涉及到了死锁，最直接的例子就是哲学家就餐筷子，如果每一个哲学家都拿起了他的右手的筷子，现在都在等左边的筷子。这样一直绕下去，从而产生了死锁。

6.1.1 资源问题

在系统中存在着很多不同类型的资源，其中可以引起的死锁的主要是需要采用互斥访问方法的、不可以被抢占的资源、

6.1.1.1 可重用性资源和消耗性资源

可重用性资源

可重用性资源是一种可供用户重复使用多次的资源，它具有以下性质：

  1. 每一个可重用性资源中的单位只能分配给一个进程使用，不允许多个进程共享
  2. 进程在使用可重用性资源时，须按照这样的顺序：请求资源 -> 使用资源 -> 释放资源
  3. 系统中每一类可重用性资源中的单元数目是相对固定的，进程在运行期间既不能创建也不能删除它

可消耗性资源

可消耗性资源又称为临时性资源，它是在进程运行期间，由进程动态的创建和消耗的，它具有以下性质：

  1. 每一类可消耗性资源的单元数目在进程运行期间是可以不断变化的，有时它可以有很多，有时可能为0
  2. 进程在运行过程中，可以不断地创造可消耗性资源的单元，将它们放入该资源类的缓冲区中，以增加该资源类的单元数目
  3. 进程在运行过程中，可以请求若干个可消耗性资源单元，用于进程自己的消耗，不再将它们返回给该资源类中

6.1.1.2 可抢占性资源和不可抢占性资源

可抢占性资源

可把系统中的资源分为两类，一类是可抢占性资源，是指某进程在获得这类资源后，该资源可以再被其它进程或系统抢占

不可抢占性资源

另一类资源是不可抢占资源，一旦系统把某资源分配给该进程之后，就不能将它强行回收，只能在进程用完后自行释放

6.1.2 死锁的起因

6.1.2.1 竞争不可抢占性资源引起的死锁

通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。

一个很简单的例子，进程$P_1$和$P_2$在并发执行，他们都要写两个文件$F_1$和$F_2$。其中$P_1$和$P_2$的代码分别为：

1
2
3
4
5
6
7
8
9
   P1
  ....
Open(f1, w);
Open(f2, w);

   P2
  ....
Open(f2, w);
Open(f1, w);

如果这两个进程在并发执行的时候，如果$P_1$先打开$F_1$和$F_2$，然后$P_2$才去打开$F_1$(或$F_2$)，由于文件$F_1$(或$F_2$)已经被打开，因此$P_2$会被阻塞。当$P_1$使用完$F_1$(或$F_2$)，这时$P_2$才可以去打开$F_1$(或$F_2$)，这样程序继续运行下去。

但是如果在$P_1$打开$F_1$的同时，$P_2$去打开$F_2$，每个进程都占有一个打开的文件，此时就可能出现问题。因为当$P_1$试图去打开$F_2$,而$F_2$试图去打开$F_1$时，这两个进程都会因文件已被打开而阻塞，因此这两个进程将会无限期地等待下去，从而形成死锁。
共享文件时的死锁情况

6.1.2.2 竞争可消耗资源引起的死锁

进程之间通信时的死锁
如图所示，$m_1$、$m_3$、$m_3$是可消耗资源。进程$P_1$一方面产生消息$m_1$，利用send(p2,m1)将它发送给$P_2$，另一方面，有要求从$P_3$接受消息$m_2$；而$P_2$、$P_3$依次类推。

如果三个进程按以下顺序进行：

1
2
3
P1:   ...send(p2, m1);    receive(p3, m3);...
P2:   ...send(p3, m2);    receive(p1, m1);...
P3:   ...send(p1, m3);    receive(p2, m2);...

这三个进程都可以先将消息发送给下一个进程，相应地他们也都能都接收到从上一个进程发来的消息，因此三个进程都可以顺利的进行下去，不会发生死锁。

但是如果三个进程都先执行receive，在执行send，按下面的顺序运行：

1
2
3
P1:   ...receive(p3, m3);    send(p2, m1);...
P2:   ...receive(p1, m1);    send(p3, m2);...
P3:   ...receive(p2, m2);    send(p1, m3);...

那么这三个进程就会永远阻塞在它们的receive操作上，就会产生死锁。

6.2 死锁的定义、必要条件和处理方法

6.2.1 死锁的定义

如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。

6.2.2 产生死锁的必要条件

产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生：

  1. 互斥条件。进程对所分配的资源进行排他性使用。即该资源只允许一个进程使用，其他进程如果请求该资源只能等待。
  2. 请求和保持条件。进程已经保持一至少一个资源，但又提出了新的资源请求，而新资源已被其他进程占有，导致进程被阻塞。
  3. 不可抢占条件。 进程已获得的资源在为使用完之前不能被抢占，只有进程在使用完之后才能释放。
  4. 循环等待条件。发生死锁时，必然存在一个进程资源循环链，即进程集合$[P_0, P_1, P_2, ···, P_n]$中$P_0$正在等待一个$P_1$占用的资源，$P_1$正在等待一个$P_2$占用的资源，……，$P_n$正在等待一个$P_0$占用的资源

6.2.3 处理死锁的办法

目前处理死锁的方法可归结为四种：

  1. 预防死锁。通过设置某些限制，去破坏产生死锁四个必要条件中的一个或几个来预防死锁。
  2. 避免死锁。在资源的动态分配过程中，用某种方法阻止系统进入不安全状态，从而避免发生死锁。
  3. 检测死锁。该方法允许进程在运行过程中发生死锁，但可通过检测机构及时地检测出死锁的发生，然后采取适当措施，把进城从死锁中解脱出来。
  4. 解除死锁。当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。

6.3 预防死锁

预防死锁时通过破坏产生死锁四个必要条件中的一个或几个，以避免发生死锁。

6.3.1 破坏“请求和保持”条件

当一个进程在请求资源时，他不能持有不可抢占资源。可通过一下两种不同的协议实现：

6.3.1.1 第一种协议

所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。此时若系统中有足够的资源分配给某进程，便可把其需要的所有资源分配给它。这样，该进程在整个运行期间，便不会再提出资源要求，从而破坏了“请求”条件。系统在分配资源时，只要有一种资源不能满足进程的要求，即使其所需的其他资源都空闲也不分配给它，而让该进程等待。由于该进程在等待期间未占有任何资源，于是破坏了“保持”条件，从而可以预防死锁的发生。

这种协议的优点是简单、易行且安全。但是缺点也极其明显：

  1. 资源被严重浪费，严重的恶化了资源的利用率。
  2. 使进程经常的发生饥饿现象。

6.3.1.2 第二种协议

该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行的过程中再逐步释放已分配给自己的、且已用毕的全部资源，然后再请求新的所需资源。

6.3.2 破坏“不可抢占”条件

为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，他必须释放已经保持的所有资源，待以后需要时再重新申请。这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。

6.3.3 破坏“循环等待”条件

一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不同的序号。排序后，便可以采用这样的预防协议：规定每个进程必须按照序号的地址顺序来请求资源。一个进程在开始时，可以请求资源$R_i$的单元，以后，当且仅当$F(R_j)>F(R_i)$，进程才可以请求资源$R_j$。如果需要多个同类资源单元，则必须一起请求。

  • 优点：资源利用率和系统吞吐量都有比较明显的改善。
  • 缺点：
    1. 系统中各类资源所规定的序号必须稳定，这就限制了新类型设备的增加
    2. 可能会发生作业使用各类资源的顺序与系统规定的不同，造成资源的浪费。
    3. 这种按照规定次序申请资源的方法会限制用户简单，自主的编程。

6.4 避免死锁

6.4.1 系统安全状态

在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。

在该方法中，允许进程动态的申请资源吗，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则，另进程等待。

安全状态是指系统能按某种进程推进顺序为每个进程分配其所需资源，直至满足每个进程对资源的最大需求。如果无法找到这样一个序列，则称系统处于不安全状态。

6.4.2 利用银行家算法避免死锁

为实现银行家算法，每一个新进程在进入系统时，他必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才分配资源。

6.4.2.1 银行家算法中的数据结构

  1. 可利用资源向量Available。代表系统中目前已有的可分配的该种资源的最大数。
  2. 最大需求矩阵Max。代表该进程对该资源的最大需求数。
  3. 分配矩阵Allocation。代表目前已经分配给该进程的该资源的数目。
  4. 需求矩阵Need。代表该进程还需要该资源的数目。

6.4.2.2 银行家算法

设$Request_i$是进程$P_i$的请求向量，如果$Request_i[j]=K$，表示进程$P_i$需要$K$个$R_j$类型的资源。当$P_i$发出资源请求后，系统按下述步骤进行检查：

  1. 如果$Request_i[j] \le Need[i, j]$，便转向步骤2；否则任务出错，因为它所需要的资源数已超过它所宣布的最大值。
  2. 如果$Request_i[j] \le Available[j]$，便转向步骤3；否则，表示尚无足够资源，$P_i$需等待。
  3. 系统试探着把资源分配给进程$P_i$，并修改下面数据结构中的数值：$Available[j] = Available[j] - Request_i[j]$
    $Allocation[i,j] = Allocation[i,j] + Request_i[j]$
    $Need[i,j] = Need[i,j] - Request_i[j]$
  4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程$P_i$，已完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程$P_i$等待。

6.4.2.3 安全性算法

  1. 设置两个向量：①工作向量Work，他表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，$Word = Available$；②FInish：他表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做$Finish[i] = false$；当有足够资源分配给进程时，再令$Finish[i] = true$。
  2. 从进程集合中找到一个能满足下述条件的进程：①$Finish[i]=false$；②$Need[i,j] \le Work[j]$；若找到则执行步骤3，否则执行步骤4.
  3. 若进程$P_i$获得资源后，可顺利执行，直至完成，并释放出分配给他的资源，故应执行：
    $Word[j] = Work[j] + Allocation[i,j];$
    $Finish[i]=true;$
    go to step 2;
  4. 如果所有进程的$Finish[i]=true$都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

6.4.2.4 银行家算法例子

题目

假定系统中有五个进程${P_0, P_1, P_2, P_3, P_4}$和三类资源${A, B, C}$，各种资源的数量分别为10、5、7，在$T_0$时刻的资源分配情况如图所示：
T0时刻的资源分配表

在$T_0$时刻的安全性

利用安全性算法对$T_0$时刻的资源分配情况进行分析可知，在$T_0$时刻存在着一个安全序列${P_1,P_3,P_4,P_2,P_0}$，故系统是安全的。
T0时刻的安全序列

$P_1$请求资源

$P_1$发出请求向量$Request_1(1,0,2)$，系统按银行家算法进行检查：
①$Request_1(1,0,2) \le Need_1(1,2,2)$；
②$Request_1(1,0,2) \le Available_1(3,3,2)$；
③系统先假定可为$P_1$分配资源，并修改$Avaliable$，$Allocation_1$和$Need_1$向量，由此形成的资源变化情况如1图中的圆括号所示；
④再利用安全性算法检查此时系统是否安全，如图所示
P1申请资源时的安全性检查

有所进行的安全性检查得知，可以找到一个安全序列${P_1,P_3,P_4,P_2,P_0}$。因此，系统是安全的，可以立即将$P_1$所申请的资源分配给它。

$P_4$请求资源

$P_4$发出请求向量$Request_4(3,3,0)$，系统按银行家算法进行检查：
①$Request_4(3,3,0) \le Need_4(4,3,1)$；
②$Request_4(3,3,0) \ge Available(2,3,0)$，让$P_4$等待。

$P_0$请求资源

$P_0$发出请求向量$Request_0(0,2,0)$，系统按银行家算法进行检查：
①$Request_0(0,2,0) \le Need_0(7,4,3)$；
②$Request_0(0,2,0) \le Available(2,3,0)$；
③系统暂时先假定可为$P_0$分配资源，并修改有关数据，如图所示。
为P0分配资源后的有关资源数据

进入安全性检查

可用资源$Available(2,1,0)$已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。