银行家算法安全系统性序列分析报告报告材料

1、银行家算法安全性序列分析摘要：在操作系统的处理机调度的过程中，由于竞争资源或者进程间推进顺 序非法，都会导致死锁的发生。本文主要研究如何利用银行家算法可以避免死锁， 并分析银行家算法安全性序列。关键词：银行家算法；安全性序列；避免死锁引言处理死锁的方法主要包括预防死锁、 避免死锁、检测死锁和解除死锁。而利 用银行家算法可以避免死锁，在这一避免死锁的过程中，银行家算法安全性序列 分析是尤为重要的。1银行家算法中的数据结构(1) 空闲资源向量Available。这是一个数组，它里面包括m个元素，这 些元素都可以分别用来表示一种空闲的资源的数量的多少，系统中存储的这种全 部空闲的资源的数量的多少为它

2、的初始值，随该类资源的分配和回收，其数值发 生动态地改变。如果Available j =K，那么，系统中当前存在K个Rj类资源。(2) 最大需求矩阵Max。Max矩阵是nXm维的，该矩阵定义了系统中 n个进程中的每一个进程对 m类资源的最大需求。如果 Max i,j =K，那么， 进程i需要Rj类资源的最大数量的多少为 K。(3) 分配矩阵Allocation 。Allocation 矩阵是n Xm维的，该矩阵定义了 系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation i,j =K， 那么，进程i当前已分得Rj类资源的数量的多少为K。(4) 需求矩阵Need。Need矩阵

3、是n Xm维的，该矩阵定义了所有进程 仍然需求的各类资源数。如果 Need i,j =K，那么，为了能够完成其任务，进 程i还需要Rj类资源K个。Need i,j =Max i,j -Allocation i,j2银行家算法设Requesti是进程Pi的请求向量，如果 Requesti j =K，表示进程 Pi 需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：(1) 如果Requesti j WNeed便转向步骤 2 ;否则认为出错， 因为它所需要的资源数大于它仍然需要的最大值。(2) 如果 Requesti j Available j ，便转向步骤(3);否则， 表 示

4、尚无足够资源，Pi须等待。(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Available j ： =Available j -Requesti j ;Allocationi,j： =Allocation i,j +Requesti j;Need i,j： =Need i,j -Requesti j;(4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 如果安全，就正式将资源分配给进程 Pi，从而实现本次分配；反之，取消这次 的试探分配，保持上一次的资源分配状态，让进程 Pi等待。3.安全性算法(1) 设置两个向量： 工作向量 Work :它表示系统可提

5、供给进程继续 运行所需的各类资源数量的多少，它含有 m个元素，在执行安全算法开始时， Work : =Available :Finish :它表示系统是否有足够的资源分配给进程，使 之运行完成。开始时先做Finish i：=false ;当有足够资源分配给进程时，再 令 Finish i： =true 。(2) 从进程集合中找到一个能满足下述条件的进程： Finish i =false ； Need i,jwWork j；如果找到，那么，执行步骤(3),否则，执行步骤(4) o(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它 的资源，故应执行：Work j ： = Work

6、 i +Allocation i,j ;Finish i ： = true;go to step 2;(4) 如果所有进程的Finish i =true都满足，则表示系统处于安全状 态；否则，系统处于不安全状态。4银行家算法安全性序列分析之例假定系统中有五个进程 PO, P1, P2, P3, P4 和三类资源 A, B, C，各种资源的数量分别为10、5、7,在T0时刻的资源分配情况如表1所示表1 T0时刻的资源分配表资源情况MaxAllocati onNeedAvailable进程ABCABCABCABCP07530 1 0743332P13222 0 01 2 2P29023026 0

7、0P32 2 22 1 10 1 1P44330 0 2431(1) TO时刻的安全性:表2 TO时刻的安全序列鴻情况 进程、WorkNeedAllocati onWork+Allocati onFi nishABCABCABCABCP1332122200532TRUEP3532011211743TRUEP4743431002745TRUEP27456003021047TRUEP01047430101057TRUE7(2) P1请求资源：P1发出请求向量Requestl (1 , 0, 2),系统按银行家算法进行检查： Requestl ( 1,0, 2 )<Need1 (1,2, 2

8、) Request1 (1,0, 2 )wAvailable1 (3, 3, 2 ) 系统先假定可为P1分配资源，并修改 Available, Allocation1和Need1向量，由此形成的资源变化情况如表 2所示。表2系统先假定可为P1分配资源时刻的资源分配表资源情况MaxAllocati onNeedAvailable进程、ABCABCABCABCP07530 1 0743230P13223020 2 0P290230 26 0 0P32 2 22 1 10 1 1P44330 0 2431再利用安全性算法检查此时系统是否安全。表3 P1申请资源时的安全性检查快情况 进程WorkNee

9、dAllocati onWork+Allocati onFi nishABCABCABCABCP1230020302532TRUEP3532011211743TRUEP4743431002745TRUEP27456003021047TRUEP01047430101057TRUE7(3) P4请求资源：P4发出请求向量Request4 (3，3，0)，系统按银行 家算法进行检查： Request4 (3, 3, 0 ) <Need4 (4, 3,1 ); Request4 (3, 3, 0 ) vAvailable (2, 3, 0 )，让 P4 等待。 参考文献：1 崔建平深入探讨银行家算法J.科技信息(学术研究),2008,(17).2 侯刚.深入解析银行家算法J.潍坊学院学报，