View Post
银行家算法
银行家算法是最有代表性的避免死锁的算法。为实现银行家算法，需要设置若干个数据结构。
1.银行家算法中的数据结构
（1）可利用的资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该资源的分配和回收而动态地改变。如果Available[j]=K，则表示系统中现有Rj类资源K个。
（2）最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
（3）分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源当前已非配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
（4）需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
上述三个矩阵间存在的关系：
Need[i,j]=Max[i,j]-Allocation[i,j]
2.银行家算法
设Request(i)是进程P(i)的请求向量，如果Request(i)[j]=K，表示进程P(i)需要K个Rj类型的资源。当P（i）发出资源请求后，系统按下述步骤进行检查：
（1）如果Request(i)[j]<=Need[i,j]，便转向步骤（2）；否则认为出错，因为它所需要的资源超出了它宣布的最大值。
（2）如果Request(i)[j]<=Avaiable[j]，便转向步骤（3）；否则表示尚无足够资源，P(i)须等待。
（3）系统试探着把资源非配给进程P(i)，并修改下面数据结构中的数值：
Available[j]=Available[j]-Request(i)[j];
Allocation[i,j]=Allocation[i,j]+Request(i)[j];
Need[i,j]=Need[i,j]-Request(i)[j];
（4）系统执行安全性算法，检查此资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程P(i)，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程P(i)等待。
3.安全性算法
系统所执行的安全性算法可描述如下：
（1）设置两个向量；
工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available
Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够的资源分配给进程时，再令Finish[i]=true。
（2）从进程集合中找到一个能满足下述条件的进程：
Finish[i]=false;
Need[i,j]<=Work[j];若找到，执行步骤（3），否则执行步骤（4）。
（3）当进程P(i)获得资源后，可顺序执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j]=Work[j]+Allcation[i,j];
Finish[i]=true;
go to step 2;
（4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。