多资源银行家算法研究与实现

摘要：在通常情况下，计算机的资源有限，比如只有一台打印机或者只有有限的内存，并且很多资源是独占性的资源，在任意时刻这些资源只能被一个程序所占用，一旦这些资源被多个程序同时访问，就会引发程序对资源的竞争，容易引起“死锁”现象。银行家算法便是针对死锁问题而诞生的。该文简介了死锁的原理，对解决多个资源下死锁问题的银行家算法进行了讨论，并用C语言对其进行了简单的模拟。

关键词：死锁；多资源竞争；银行家算法

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2013）18-4229-05

在计算机系统中，一个运行的程序被抽象成一个进程，能利用的内存、磁盘储存空间、显示屏等则可以被抽象成资源。一般来说，资源都是有限的，而操作系统中存在的进程对资源的需求却经常大大超出了实际的资源量，并且很多进程具有排他性，资源也具有独占性。此时，一旦若干个进程对某些相同的资源有需求，这些进程间便产生了竞争。在竞争的过程中，若有排他性的进程占有了独占性的资源，导致其他的进程得不到该资源，同时该进程也同样无法获取被其他排他性进程占有的独占性资源，由此产生的结果，就是所有与此有关的进程都无法满足自已的需求，这些进程也就进入了阻塞状态。如果这一状态无法转变，这最终会导致计算机程序永远进入了等待状态，无法运行，即死锁状态。

产生死锁的原因和条件其实是比较明确的，并且针对死锁这一灾难性问题，人们也想出了很多解决方案。下面，让我们先来详细地研究一下多资源背景下的死锁问题。

1 多资源死锁问题分析

大部分的死锁问题都和资源有关。

在计算机设备中，资源可分为两类，一类是可抢占资源，另一类是不可抢占资源。可抢占资源是指可以从占有它的进程中被任意释放出来并且不会引起任何不良后果的一类资源，这类资源通常不会引起死锁问题，因为一旦产生死锁的迹象，此类资源可以立即被释放，从而为其他进程所用，使得进程不会永久保持阻塞状态。不可抢占资源则正好相反，此类资源一旦被进程所占有，则无法被释放，除非占有它的进程主动释放。

所以准确来说，大部分的死锁问题和不可抢占资源有关。

对于一个进程来说，使用一个资源一般经历如下三个阶段：请求资源、使用资源、释放资源。当请求资源失败时，进程一般会进入等待状态，也就是阻塞状态，直到该资源可用。

在正在运行的操作系统中，会存在很多个进程，这些进程共同组成了一个进程集合。对于这个进程集合来说，若其中的每个进程都在等待只能由其他进程才能引发的事件，则该进程集合就陷入了死锁状态。这是由于每个进程都在等待，所以没有一个进程能引发唤醒其他进程的事件，由此，所有的进程都会无限期地等待下去。从图论的角度来说，这个进程集合形成了一个环。

正如前文所述，大部分的死锁问题都和不可抢占资源有关，这是因为部分进程占有着不可被其他进程抢占的资源，同时这些进程也无法得到被其他进程占有的不可抢占资源，于是，所有的进程都在等待其他进程使用完资源，等待资源被释放，此时便陷入了死锁境地。

在1971年，Coffman等人总结了资源死锁的四个必要条件，具体如下：

1）互斥条件，即每个资源的状态要么为已经分配给一个进程，要么就是可用的；

2）占有和等待条件，即已经得到某些资源的进程可以在请求新的资源；

3）不可抢占条件，即已经分配给某进程的资源不能强制性的被抢占，只能被占有它的进程显示地抢占；

4）环路等待条件；即系统中有两个或两个以上的进程组成的一条环路，改环路中每个进程都在等待下一个进程释放资源。

当死锁发生时，以上四个条件必须全部满足。

所以一般来说，要想将解决死锁问题，就可以从破坏这四个条件中的一个入手。下面我们来分析一下多资源背景下的银行家算法。

2 多资源银行家算法

多资源银行家算法是由单资源银行家算法推导而来，所以先来分析一下单资源的情况。

银行家算法来自于银行家向客户提供贷款的模型。假设一个银行家有10个单位的资源，有4个客户A、B、C、D要向其贷款，其已贷款数和最大需求如图1所示：

在这里，客户可以在做生意的同时只贷款一部分，并且贷款数不超过最大需求量，客户在贷款到了最大需求后可以做成生意，便可以还贷款。这里可以将客户看成进程，而将银行家看成资源。

当贷款一定时间后，每个客户的贷款数如下所示：

此时银行家手里只剩2个单位的贷款数，毫无疑问，此时若客户A将最后的2个单位的贷款借走，则A由于没有达到其最大需求，因此无法完成生意，也就无法还款，其他的客户也就无法接到贷款，由此便陷入了死锁状态。然而同样毫无疑问，若银行家贷款给C，则一切好办。

由上可知，单资源银行家算法事先了解了进程的资源需求，然后在作出最佳决策来分配资源，最终防止死锁。

多资源银行家算法是对其的推广。在这个算法里，使用一个矩阵H来记录和描述每个进程已分配的资源，使用另一个矩阵N来记录和描述每个进程仍需要的资源，使用向量E来表示每种资源的总数，用向量P来表示已分配的资源数，用A来表示空闲的资源数。

例如，有3个进程a、b、c，有四个资源i、j、k、l，则H可以如表1示：

例如，矩阵H中的第一行表示a已经占有3个资源i，1个资源k，1个资源l，其他以此类推。

此外，E=（7654），P=（6312），A=（1342），A=E-P。

多资源的银行家算法步骤如下：

1） 查找矩阵N中是否有一行，其需要的资源数小于等于A，若不存在，则会发生死锁。

2） 若有这样的一行，则可以假设它所需的资源可以全部被满足，将其标记为结束，并将其所占有的资源数加到A上。

3） 重复以上两步，直到所有的进程都标记为终止，这说明其状态是安全的。或者总有进程的需求无法得到满足，此时发生死锁。

可以看出，多资源情况下的银行家算法的本质和单资源情况下的银行家算法本质是相同的，即先收集所有与进程和资源有关的情况，然后通过对每个进程的需求和所剩资源进行分析，来推断是否会造成死锁状态，在确定可以分配资源后再分配，否则宣布无解，最终会产生死锁状态。

以上便是银行家算法在多资源的情况下的算法步骤，经过分析，作者对其用C语言进行了模拟，并进行了检验。

3 基于C语言的银行家算法模拟

作者根据上文对多资源情况下的银行家算法的分析，假设有四个资源，有三个进程，每个进程的任务是当自已所需的资源得到满足后，便在屏幕上打印出相关的字符。其源代码如下：

在这里，作者设定的数值是不会发生死锁的情况，最终三个线程按顺序打印出了自已的字符数组；而死锁情况则最终不会打印出三行字符，并显示产生死锁。

4 总结

本文探讨了以资源为基础的死锁问题以及解决多资源死锁问题的银行家算法，并给出了C语言实现的模拟程序。

然而不得不说的是，死锁问题从本质上来说是无法解决的，因为需求大于提供这一根本问题其实无法解决。此外，银行家算法本身的假设就不是很实用，由前文的分析知，银行家算法必须提前知道每个进程被分配的资源数以及一系列与资源数有关的数据，但是在计算机操作系统实际运行时，收集具体的资源利用情况是很困难的，更不用说利用资源数据去决定最佳分配方案。不过银行家算法依旧有可取之处，其为优化资源分配问题仍提供了很好的启发。

参考文献：

[1] Russinovich M，Solomon D，Ionescu A.深入解析windows操作系统[M].北京：人民邮电出版社，2013.

[2] Stallings W.操作系统-精髓与设计原理[M].北京：机械工业出版社，2010.

[3] Silberschatz A，Galvin P B，Gagne G.操作系统概念[M].北京：高等教育出版社，2010.

[4] Smith J E， Nair R.虚拟机系统与进程的通用平台[M].北京：机械工业出版社，2009.