操作系统：银行家算法避免死锁

银行家算法是用来避免死锁的，该方法将系统的状态分为安全和不安全，只要系统处于安全状态，便可避免死锁的发生。之所以成为银行家算法，是由于该算法能用于银行系统现金贷款的发放而得名。

安全状态的定义为：系统按照某种进程顺序，如，来为进程分配资源，直到最大需求，使每个进程都能顺序完成，此时称系统处于安全状态。

银行家算法是由大牛Dijkstra提出的，为实现银行家算法，系统中应该设置若干数据结构：

1）可用资源向量Available

2）最大需求矩阵Max

3）分配矩阵Allocation

4）需求矩阵Need

其中Need=Max-Allocation

当进程pi发出资源请求Requesti后，系统将按银行家算法执行检测，并决定是否将资源分配给pi进程，具体如：

1）如果Requesti<=need，执行2），否则认为出错

2）如果Requesti<=Available，执行3），否则进程必须等待

3）试探分配

Available[j]=Available[j]- Requesti[j];

Allocation[i,j]=Allocation[i,j]+Requesti[j];

Nedd[i,j]=Nedd[i,j]-Requesti[j];

4）系统执行安全检测算法，检测此次资源分配后系统是否处于安全状态，若安全则分配该进程资源，否则本次试探数据作废，进程pi等待

安全检测算法如下:

1）设置两个工作向量：工作向量work其初值为Available表示系统可提供给进程继续运行的各类资源数，工作向量finish其初值为false表示是否有足够的资源分配给各进程，以使其顺利完成。

2）从进程中找到一个序列使其顺序执行时，能满足如下条件：

finish[i]=false;

need<=work;

3）当进程获得资源顺序执行，直至完成，并释放出分配给它的资源，故应执行

work[j]=work[j]-allocation[i,j];

finish[i]=true;

4）若找到一个序列满足finish=true，则表示系统处于安全状态，否则处于不安全状态。