李坤芩 熊琰 王磊 田丰

（贵州商学院计算机与信息工程学院 贵州省贵阳市 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]；……