C语言银行家算法的实现与应用(2)
2.银行家算法的原理分析
2.1 银行家算法的基本思想
计算机系统中软硬件资源是有限的，而运行进程对资源的要求是非常多的，绝大多数情况下，系统往往不能满足当前运行进程的所有资源需求之和。但可以采取各个击破的方法，在情况允许下先满足部分进程的需求，等这些进程运行结束后，把资源释放给系统，系统再进行分配资源给剩下的进程。最后所有进程都得到满足。银行家算法就是这种思想的具体体现。Dijkstra提出的银行家算法就是在银行发放一笔贷款前，预测该笔贷款是否会引起银行资金周转困难。可以把操作系统看作是银行家，操作系统管理的资源就相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。银行家能预测一笔贷款业务对银行是否安全，也能预测一次资源分配对计算机系统是否安全。要解释银行家算法，必须先解释操作系统中安全状态和不安全状态。安全状态是指：如果存在一个由系统中所有进程构成的安全序列P1，，Pn，则系统处于安全状态。安全状态一定没有死锁发生。反之，如果系统中不存在一个安全序列则系统处于不安全状态。当然，不安全状态也并不意着一定会导致死锁。为了实现银行家算法，系统中必须设置若干数据结构。
2.2 银行家算法的数据结构和描述
（1）数据结构
① 最大需求矩阵ZD：它是一个s×t 的二文数组,它定义了系统中s个进程中的每个进程对t类资源的最大需求。如果ZD[i,j]=K,则表示process[i]需要Rj类资源的最大数目为K。
② 需求矩阵XQ：它是一个s×t 的二文数组,它用来表示每个进程尚需的各类资源数目。如果XQ[i,j] = K,则表示process[i]还需要Rj类资源K个,才能顺利完成任务。
③ 已分配矩阵FP：它是一个s×t 的二文数组,它定义了系统中每类资源当前已分配给每个进程的资源数。如果FP[i,j] = K,则表示process[i]当前已分得Rj类资源的数目为K。
④ 当前可用资源集合DQ：它是一个含有t 个元素的一文数组, 其中的每个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，计算机系统中有处理器资源、存储器资源、I/O设备资源和应用软件、文件系统等资源。如果DQ[j] = K,则表示系统中现有Rj类资源K个。
并且上述三个矩阵之间有如下关系：
XQ[i,j] = ZD[i,j] —FP[i,j]
（2）算法流程描述
银行家算法的流程大致分为三步进行，分别是：资源的预分配；系统的安全性检查；资源的正式分配。例如当一个进程Pi发出资源请求后,系统按下述步骤对进程Pi进行检查，银行家算法流程图如图1：
① 如果进程Pi的请求资源数目是小于等于进程Pi的需求资源数目，就执行第二步；否则认为是非法的。
② 如果进程Pi的请求资源数目是小于等于进程Pi的当前可用资源数目，就执行第三步；否则就表示当前系统中没有足够的资源供进程i使用，进程i须要阻塞等待。
③ 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值:
DQ[j] = DQ[j]-Requesti[j]；
FP[i,j] = FP[i,j]+Requesti[j]；
XQ[i,j] = XQ[i,j]-Requesti[j]；
其中Requesti[j]表示进程Pi发出的对Rj类资源的请求数目。
④ 预分配后，系统执行安全性检查,安全性检查流程图如图2。检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程,以完成本次分配；否则，将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。