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等待。
上一篇:ASP.net+sqlserver超市管理系统设计+源代码
下一篇:ASP.net+sqlserver网上商城的设计+源代码

基于Apriori算法的电影推荐

基于PageRank算法的网络数据分析

基于神经网络的验证码识别算法

python基于决策树算法的球赛预测

加密与解密算法的研究【1931字】

一種删除准则的NOMA资源联...

vc++几种排序算法演示软件实现

公寓空调设计任务书

志愿者活动的调查问卷表

神经外科重症监护病房患...

AT89C52单片机的超声波测距...

国内外图像分割技术研究现状

10万元能开儿童乐园吗,我...

中国学术生态细节考察《...

医院财务风险因素分析及管理措施【2367字】

承德市事业单位档案管理...

C#学校科研管理系统的设计