操作系统中死锁的避免----谈谈银行家算法

在操作系统的设计中，我们往往无法回避一个问题，那就是进程对有限资源的占用问题。在计算机系统中有很多独占性的资源，在任一时刻，它们都只能被一个进程使用。常见的有打印机、磁带驱动器等。例如：两个进程同时打印会引起打印混乱。鉴于此，操作系统全都具有授权一进程（临时）独占地访问某一种资源的能力。

在很多情形中，需要一个进程独占地访问若干种资源而不是一种。例如将一个大文件由磁带拷贝至打印机，进程需要同时访问磁带驱动器和打印机，并且不允许其他进程这时访问它们。在只有一个进程的系统中，该进程可以要求任何它所需要的资源，然后进行工作。但是，在一个多道程序系统中，就有可能出现严重的问题。例如，两个进程分别准备打印一个非常大的磁带文件。进程A申请打印机，并得到授权。进程B申请磁带机，也得到授权。现在，A申请磁带机，但该请求在B释放磁带机前会被拒绝。不幸的是，B非但不放弃磁带机，而且去申请打印机，而A在申请到磁带机之前也不会释放打印机。这时，两个进程都被阻塞，并且保持下去，这种状况就是死锁（deadlock）.

下面系统阐述一下死锁的定义：所谓死锁，就是多个进程循环等待它方占有的资源而无限期的僵持下去的局面。显然，如果没有外力的作用，那么死锁涉及到的各个进程都将永远处于封锁状态。

计算机系统产生死锁的根本原因就是资源有限且操作不当。即：一种原因是系统提供的资源太少了，远不能满足并发进程对资源的需求。这种竞争资源引起的死锁是我们要讨论的核心。例如：消息是一种临时性资源。某一时刻，进程A等待进程B发来的消息，进程B等待进程C发来的消息，而进程C又等待进程A发来的消息。消息未到，A，B，C三个进程均无法向前推进，也会发生进程通信上的死锁。

我们可以对资源进行以下分类：
可重用资源(reusable resource)：每个时刻只有一个进程使用，但不会耗尽，在宏观上各个进程轮流使用。如CPU、主存和辅存、I/O通道、外设、数据结构如文件、数据库和信号量。有可能剥夺资源：由高优进程剥夺低优进程，或OS核心剥夺进程。

P1	P2
...	...
Request(A)	Request(B)
Request(B)	Request(A)
Request(B)	Request(A)
Request(A)	Requsst(B)

可重用资源死锁
死锁发生：双方都拥有部分资源，同时在请求对方已占有的资源。如次序：P1 P2 P1 P2

非可剥夺资源(consumable resource)：可以动态生成和消耗，一般不限制数量。如硬件中断、信号、消息、缓冲区内的数据。

P1	P2
...	...
Receive(P2,M);	Receive(P1,Q);
Send(P2,N);	Send(P1,R);

非可剥夺资源死锁

死锁发生：双方都等待对方去生成资源，如次序：P1 P2

总的来说，死锁和不可剥夺资源有关。我们讨论的重点放在不可剥夺资源。

使用一资源事件的顺序如下：申请资源，使用资源，释放资源。

另一种原因是由于进程推进顺序不合适引发的死锁。资源少也未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。

下面简述一下产生死锁的必要条件 ：

如果在计算机系统中同时具备下面四个必要条件时，那么会发生死锁。换句话说，只要下面四个条件中有一个不具备，系统就不会出现死锁。

1．互斥条件：即某个资源在一段时间内只能由一个进程占有，不能同时被两个或两个以上的进程占有。

2．不可抢占条件：进程所获得的资源在未使用完毕之前，资源申请者不能强行地从资源占有者手中夺取资源，而只能由该资源的占有者进程自行释放。

3．占有且申请条件：进程至少已经占有一个资源，但又申请新的资源；由于该资源已被另外进程占有，此时该进程阻塞；但是，它在等待新资源之时，仍继续占用已占有的资源。

4．循环等待条件 ：存在一个进程等待序列{P1,P2,…,Pn},其中P1等待P2所占有的某一资源，P2等待P3所占有的某一资源，……，而Pn等待P1所占有的某一资源，形成一个进程循环等待环。

死锁的有向图表示

面我们提到的这四个条件在死锁时会同时发生。也就是说，只要有一个必要条件不满足，则死锁就可以排除。

处理死锁的基本方法可归结为以下3种：

方法	资源分配策略	各种可能模式	主要优点	主要缺点
预防 Prevention	保守的；宁可资源闲置	一次请求所有资源<条件1> 资源剥夺 <条件3> 资源按序申请 <条件4>	适用于作突发式处理的进程；不必剥夺 适用于状态可以保存和恢复的资源 可以在编译时（而不必在运行时）就进行检查	效率低；进程初始化时间延长 剥夺次数过多；多次对资源重新起动 不便灵活申请新资源
避免 Avoidance	是“预防”和“检测”的折衷（在运行时判断是否可能死锁	寻找可能的安全的运行顺序	不必进行剥夺	必须知道将来的资源需求；进程可能会长时间阻塞
检测 Detection	宽松的；只要允许，就分配资源	定期检查死锁是否已经发生	不延长进程初始化时间；允许对死锁进行现场处理	通过剥夺解除死锁，造成损失

关于死锁的预防、检测与恢复，不是本文讨论的话题，感兴趣的读者可翻阅相关资料查找到这些信息。在这里，我们着重谈一谈死锁的避免。

我们说死锁预防是排除死锁的静态策略，它使产生死锁的四个必要条件不能同时具备，从而对进程申请资源的活动加以限制，以保证死锁不会发生；而死锁的避免是排除死锁的动态策略，它不限制进程有关申请资源的命令，而是对进程所发出的每一个申请资源的命令加以动态地检查，并根据检查结果决定是否进行资源分配。就是说，在资源分配过程中若预测有发生死锁的可能性，则加以避免。这种方法的关键是确定资源分配的安全性。 那么，是否存在一种算法，总能做出正确的选择从而避免死锁呢？答案是肯定的，但条件是必须事先获得一些特定的信息。

Dijkstra 于1965年提出了一个经典的避免死锁的算法----银行家算法（banker’s algorithm）。

其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满足。

怎样得知一个状态是否安全呢？

所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，…，Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。

更通俗一点地讲，检查状态是否安全的方法是看它是否有足够的剩余资源满足一个距最大需求最近的客户。如果有，那么这比投资被认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，那么该状态是安全的，最初的请求可以批准。
需要指出的是，不安全状态并不一定引起死锁，因为客户并不一定申请其最大贷款额度，但银行家不敢抱有这种侥幸心理。

在此，我们引入了两个向量：Resourse（资源总量）、Available（剩余资源量） 以及两个矩阵：Claim（每个进程的最大需求量）、Allocation（已为每个进程分配的数量）。它们共同构成了任一时刻系统对资源的分配状态。

向量模型：

R1

R2

R3

矩阵模型：

	R1	R2
P1
P2
P3

这里，我们设置另外一个矩阵：各个进程尚需资源量（Need）,可以看出

Need = Claim – Allocation

因此，我们可以这样描述银行家算法：

设Request[i]是进程Pi的请求向量。如果Request[i , j]=k，表示Pi需k个Rj类资源。当Pi发出资源请求后，系统按下述步骤进行检查:

(1) if (Request[i]<=Need[i]) goto (2);
        else error(“over request”);
(2) if (Request[i]<=Available[i]) goto (3);
        else wait();

(3) 系统试探性把要求资源分给Pi（类似回溯算法）。并根据分配修改下面数据结构中的值。

Available[i] = Available[i] – Request[i] ；

Allocation[i] = Allocation[i] + Request[i]；

Need[i] = Need[i]-Request[i];

(4) 系统执行安全性检查，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程以完成此次分配；若不安全，试探方案作废，恢复原资源分配表，让进程Pi等待。

系统所执行的安全性检查算法可描述如下：

设置两个向量：Free、Finish

工作向量Free是一个横向量，表示系统可提供给进程继续运行所需要的各类资源数目，它含有的元素个数等于资源数。执行安全算法开始时，

Free = Available.

标记向量Finish是一个纵向量，表示进程在此次检查中中是否被满足，使之运行完成，开始时对当前未满足的进程做Finish[i] = false；当有足够资源分配给进程(Need[i]<=Free)时，Finish[i]=true，Pi完成，并释放资源。

(1)从进程集中找一个能满足下述条件的进程Pi

① Finish[i] == false(未定)

② Need[i] <= Free (资源够分)

(2)当Pi获得资源后，认为它完成，回收资源:

Free = Free + Allocation[i] ;

Finish[i] = true ;

Go to step(1);

试探此番若可以达到Finish[0..n]:=true，则表示系统处于安全状态，然后再具体为申请资源的进程分配资源。否则系统处于不安全状态。

我们还举银行家的例子来说明：设有客户A、B、C、D，单一资源即为资金（R）。

下列状态为安全状态，一个安全序列为：C->D->B->A

A	1	6
B	1	5
C	2	4
D	4	7

Available = (2) ; Resourse = (10) ;

可以看出，银行家算法从避免死锁的角度上说是非常有效的，但是，从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。因此，在实际中，如果有，也只有极少的系统使用银行家算法来避免死锁。