银行家算法
算法思想
银行家算法:银行家算法是从当前状态出发,按照系统各类资源剩余量逐个检查各进程需要申请的资源量,找到一个各类资源申请量均小于等于系统剩余资源量的进程P1。然后分配给该P1进程所请求的资源,假定P1完成工作后归还其占有的所有资源,更新系统剩余资源状态并且移除进程列表中的P1,进而检查下一个能完成工作的客户,......。如果所有客户都能完成工作,则找到一个安全序列,银行家才是安全的。若找不到这样的安全序列,则当前状态不安全。
相关数据结构
可利用资源向量Available。这是一个含有m个元素的数组,其中的而每一个元素代表一类可利用资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态的改变。如果Available[j]=K,则表示系统中现有Rj类资源K个。
最大需求矩阵Max。这是一个n*m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K;则表示进程i需要Rj类资源的最大数目为K。
分配矩阵Allocation。这也是一个n*m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K,则表示进程i当前已分得Rj类资源的数目为K。
需求矩阵Need。这也是一个n*m的矩阵,用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程i还需要Rj类资源K个,方能完成任务。
上述三个矩阵间存在下述关系:Need[i,j]=Max[i,j]-Allocation[i,j]
例子
银行家算法实例
当前系统状态
从图中数据我们可以利用银行家算法的四个数据结构,来描述当前的系统状态:
因为系统总资源R=(17,5,20),所以可以计算出可利用资源向量Available=R-Allocation(P1,P2,P3,P4,P5)=(2,3,3)
分配资源
根据目前状态,用Available向量每一个进程的Need向量相比,发现Available>=P5.Need
,所以可以将目前的资源分配给P5向量(P4也可以,不唯一)。当P5获得所需的所有向量后执行完毕,之后释放其占有的所有资源。此时更新系统资源:
Available=R-Allocation(P1,P2,P3)=(7,4,11)
按照上述同样的方法,P4 也可以安全运行,以及P3,P2,P1也能按顺序运行。因此,在T0时刻,存在安全序列:P5,P4,P3,P2,P1
(并不唯一)