1。银行家算法介绍

银行家算法是最著名的死锁避免算法。当一个进程第一次申请资源时，它应该测试它对资源的最大需求。如果系统中的现有资源能够满足其最大需求，则根据当前的应用数量分配资源，否则，分配将被延迟。

2。数据结构描述

2.1，可用资源向量available

m个元素的数组，其中每个元素代表一个类的可用资源的数量。Available[j]=k，表示系统中有k个Rj资源。

2.2，最大需求矩阵Max

对于n×m矩阵，定义了系统中n个进程的每一个对M个资源的最大需求。Max[i，j]=K，这意味着进程I需要的Rj资源的最大数量是K。

2.3，分配矩阵

n×m矩阵定义了当前分配给系统中每种资源类型的每个进程的资源数量。Allocation[i，j]=K，这意味着进程I当前分配的Rj类资源数为K。

2.4、需求矩阵需要

是n×m矩阵，表示每个进程需要的各类资源数量，Need[i，j]=K，表示进程I需要的Rj资源数量为K。

3。银行家算法的描述

3.1。银行家算法

设Request i为进程Pi的请求向量，如果Request i[j]=K，则表示进程Pi需要K个Rj资源。当Pi发出资源请求时，系统按照以下步骤进行检测:

1、如果Request i[j] ≤Need[i，j]，便转向步骤2，否则认为出错，因为它所需的资源数超过了它所宣布的最大值。2、如果Request i[j] ≤Available[i，j]，便转向步骤3，否则，表示尚无足够资源，Pi须等待3、系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available[j]=Availabe[j]-Request i[j]Allocation[i,j]=Allocation[i,j]+Request i[j]Need[i,j]=Need[i,j]-Request i[j]4、系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

3.2，安全算法

1.设置两个向量。

工作矢量Work；它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available；Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时Finish[i]=false；当有足够资源分配给进程Pi时，再令Finish[i]=true;

2.从进程集中找到满足以下条件的进程:

Finish[i]=false;Need[i,j]=Work[j];

如果是，转到下一步，否则，转到步骤4。

3.当进程Pi获得资源后，可以成功执行，直到完成，分配给它的资源被释放。应该一起执行:

Work[j]=Work[j]+Allocation[i,j];Finish[i]=true;go to step (2)

4.如果满足所有进程的Finish[i]=true，则说明系统处于安全状态；否则，系统将处于不安全状态。

4。银行家算法的例子

假设系统中有5个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻资源分配情况见下表：

假设系统中有五个进程{P0，P1，P2，P3，P4}和三种资源{A，B，C}，每种资源的数量分别为10，5，7。T0时的资源分配见下表:

T0时的资源分配

利用安全算法分析T0时刻的资源分配，从下表可以看出，T0时刻存在一个安全序列{P1，P3，P4，P2，P0}，因此系统是安全的。

P1请求资源:P1发出请求向量Request 1(1，0，2)。系统根据银行家算法进行检查:

Request 1(1,0,2)≤Need 1(1,2,2)Request 1(1,0,2)≤Available1(3,3,2)系统先假定可为P1分配资源，并修改Available 1、Allocation 1和Need 1矢量，由此形成的资源变化情况可见下表。再利用安全性检查此时系统是否安全。

P4请求资源:P4发出请求向量Request 4(3，3，0)，系统根据银行家算法进行检查:

Request 4(3,3,0)≤Need 4(4,3,1)Request 4(3,3,0)＞Available(2,3,0)，让P4等待

P0请求资源:P0发出请求向量Request 0(0，2，0)，系统根据银行家算法进行检查:

Request 0(0,2,0)≤Need 0(7,4,3)Request 0(0,2,0)≤Available(2,3,0)

系统暂时假设可以为P0分配资源，并修改相关数据，如下表所示。

安全检查显示可用的(2，1，0资源(2，1，0)已经不能满足任何进程的需要，所以系统进入不安全状态，此时系统不分配资源。