基于银行家算法的安全序列分析

李坤芩 熊琰 王磊 田丰

（贵州商学院计算机与信息工程学院 贵州省贵阳市 550014）

操作系统调度算法有很多，如FCFS、SJF、RR 算法、银行家算法等[1]。避免死锁的最具代表性算法——银行家算法，银行能把资金贷给所有需要的客户，不会发生不满足的情况。在操作系统中，利用银行家算法的思想来避免死锁，即所有进程都必须保证能利用系统最大数量的资源，运行完成后将其资源释放给系统。

1 安全序列

系统有两种状态，即安全和不安全。当系统处在安全状态时，可以避免死锁；当系统处在不安全状态时，可能会发生死锁的发生[1]。系统能够按照某种进程推进顺序（P1,P2,...,Pn）为所有进程分配其所需要的资源，使所有进程都能如期完成，则系统处于安全状态，便不会进入死锁状态，（P1,P2,...,Pn）为安全序列[1]。如果系统不能找到一个安全序列，则系统处于不安全状态[1]，有可能进入死锁状态。因此，避免死锁的本质就是使系统不要进入不安全状态。

2 银行家算法的数据结构

算法中有Available、Max、Allocation 和Need 四个数据结构，还存在以下关系：Need=Max-Allocation，详情如下：

（1）可分配资源向量Available，系统最后还剩下的可利用资源个数[2]。

（2）最大需求矩阵Max，某个进程一共需要的资源个数[2]。

（3）分配矩阵Allocation，某个进程已经占有的资源个数[2]。

（4）需求矩阵Need，某个进程还需要的资源个数[2]。

3 银行家算法

假设系统中有进程M 个，当进程Pi 申请（Requesti）资源时，资源分配如下：

（1）如果Requesti≤Needi，则转向第（2）步；反之出错返回。

（2）如果Requesti≤Available，则转向第（3）步；反之进程Pi等待。

（3）假定进程Pi得到资源分配并修改以下参数[3]：

Available=Available-Requesti

Allocationi=Allocationi+Requesti

Needi=Needi-Requesti

（4）安全性算法检查：如果系统能找到安全序列，说明系统安全，可以顺利进行[3]；反之进程Pi等待[3]。

4 安全性算法

（1）工作向量Work，初始值为Available 的值；Finish，初始值为False，如果存在充足的资源，那么Finishi的值为True。

（2）找到进程符合以下要求[1]：

Finishi=False

Needi≤Work

如果能找到符合以上条件的进程，则转向下面的第（3）步，否则，转向第（4）步。

（3）假设进程Pi获得资源，修改以下参数：

Work=Work+Allocation

Finishi=True

继续执行第（3）步；

（4）当所有进程的Finishi=True，表明安全；反之，表明不安全。

从银行家算法和安全性算法可知，如果系统能找到一个安全序列，说明系统是安全的，才能分配资源。

5 银行家算法的安全序列分析

系统中有3 种资源A、B、C 和5 个进程，A、B、C 种资源个数分别为17、5、20。T0时刻，系统资源分配表如表1所示。

请分析：

（1）在T0时刻系统是否安全？请写出判断过程。

（2）假如进程P2请求Request2(0,3,4)，将如何进行资源分配？请写出判断过程。

（3）在进程P2请求Request2(0,3,4) 后，进程P4再请求Request4(2,0,1)，将如何进行资源分配？请写出判断过程。

解：T0时刻，由题可知:

AvailableA=原有-分配=17-（2+4+4+2+3）=2，AvailableB=5-（1+0+0+0+1）=3，AvailableC=20-（2+2+5+4+4）=3，Need=Max-Allocation，Need1=（3，4，7），Need2=（1，3，4），Need3=（0，0，6），Need4=（2，2，1），Need5=（1，1，0），可得T0时刻资源分配表如表2所示。

（1）安全性算法分析如表3所示。

通过以上分析，{P4,P3,P2,P5,P1}是安全序列，系统安全。因为安全序列有很多个，因此安全序列号并不唯一。

（2）进程P2请求Request2(0,3,4)，分析如下：

①Request2(0,3,4)≤Need2(1,3,4)；

②Request2(0,3,4)>Available(2,3,3)，故系统不能将资源分配给它，此时P2必须等待。

（3）进程P2请求Request2(0,3,4)后，进程P4再请求Request4(2,0,1)，分析如下：

①Request4(2,0,1)≤Need4(2,2,1)；

②Request4(2,0,1)≤Available(2,3,3)；

③假定进程P2得到资源分配并修改以下参数：

Available=Available-Request4=(2,3,3)-(2,0,1)=(0,3,2)

表1：资源分配表

表3：安全性检查

Allocation4=Allocation4+Request4=(2,0,4)+(2,0,1)=(4,0,5)

Need4=Need4-Request4=(2,2,1)-(2,0,1)=(0,2,0)

④安全性检查：Available=（0,3,2），Work=Available=（0,3,2），找5 个进程中Need 小于Work 的进程，可以找到进程P4满足Need4(0,2,0)≤Work，因此可以满足P4的运行。P4运行结束后，系统的状态如表4所示。

通过以上分析，{P4,P2,P3,P5,P1}是安全序列，系统安全，可以进行资源分配。

从以上的举例可知，安全性算法检查完成后，最后的Work+Allocation 资源个数还是和初始的资源个数一致。如果在安全性算法判断Need≤Work 错误，选错进程找到一个安全序列，最后资源个数也和初始的资源个数一致，但是找到的这个序列号是错误的。因此，在安全性算法时，需要注意这一点。

6 结束语

本文详细介绍了避免死锁的最具代表性算法——银行家算法，并通过举例讲述了银行家算法的安全序列需要注意的问题。通过分析，得出在安全性算法检查时，要特别注意需求矩阵Need 和工作向量Work 的比较，必须选择满足Need≤Work 的进程，切勿选错进程。