银行家算法安全性序列分析

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

2、，随该类资源的分配和回收，其数值发生动态地改变。如果availablej=k，那么，系统中当前存在k个rj类资源。（2） 最大需求矩阵max。max矩阵是n×m维的，该矩阵定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果maxi,j=k，那么，进程i需要rj类资源的最大数量的多少为k。（3） 分配矩阵allocation。allocation矩阵是n×m维的，该矩阵定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocationi,j=k，那么，进程i当前已分得rj类资源的数量的多少为k。（4） 需求矩阵need。need矩阵是n×m维的，

3、该矩阵定义了所有进程仍然需求的各类资源数。如果needi,j=k，那么，为了能够完成其任务，进程i还需要rj类资源k个。 needi,j=maxi,j-allocationi,j2. 银行家算法设requesti是进程pi的请求向量，如果requestij=k，表示进程pi需要k个rj类型的资源。当pi发出资源请求后，系统按下述步骤进行检查：（1） 如果requestijneedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数大于它仍然需要的最大值。（2） 如果requestijavailablej，便转向步骤（3）；否则， 表示尚无足够资源，pi须等待。（3） 系统试探着把资源分配给

4、进程pi，并修改下面数据结构中的数值： availablej=availablej-requestij; allocationi,j=allocationi,j+requestij; needi,j=needi,j-requestij;（4） 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。如果安全，就正式将资源分配给进程pi，从而实现本次分配；反之，取消这次的试探分配，保持上一次的资源分配状态，让进程pi等待。3. 安全性算法 （1） 设置两个向量： 工作向量work：它表示系统可提供给进程继续运行所需的各类资源数量的多少，它含有m个元素，在执行安全算法开始时，work=ava

5、ilable； finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做finishi=false；当有足够资源分配给进程时， 再令finishi=true。（2） 从进程集合中找到一个能满足下述条件的进程： finishi=false； needi,jworkj； 如果找到，那么，执行步骤（3）， 否则，执行步骤（4）。（3） 当进程pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： workj=worki+allocationi,j; finishi=true; go to step 2;（4） 如果所有进程的finishi=true都满足， 则表

6、示系统处于安全状态；否则，系统处于不安全状态。4. 银行家算法安全性序列分析之例 假定系统中有五个进程p0, p1, p2, p3, p4和三类资源a, b, c，各种资源的数量分别为10、5、7，在t0时刻的资源分配情况如表1 所示。表1 t0时刻的资源分配表资源情况进程maxallocationneedavailablea b ca b ca b ca b cp07 5 30 1 07 4 33 3 2p13 2 22 0 01 2 2p29 0 23 0 26 0 0p32 2 22 1 10 1 1p44 3 30 0 24 3 1（1）t0时刻的安全性： 表2 t0时刻的安全序列资源

7、情况进程workneedallocationwork+allocationfinisha b ca b ca b ca b cp13 3 21 2 22 0 05 3 2truep35 3 20 1 12 1 17 4 3truep47 4 34 3 10 0 27 4 5truep27 4 56 0 03 0 210 4 7truep010 4 77 4 30 1 010 5 7true（2） p1请求资源：p1发出请求向量request1（1，0，2），系统按银行家算法进行检查： request1（1, 0, 2）need1（1, 2, 2） request1（1, 0, 2）availa

8、ble1（3, 3, 2） 系统先假定可为p1分配资源，并修改available, allocation1和need1向量，由此形成的资源变化情况如表2所示。表2 系统先假定可为p1分配资源时刻的资源分配表资源情况进程maxallocationneedavailablea b ca b ca b ca b cp07 5 30 1 07 4 32 3 0p13 2 23 0 20 2 0p29 0 23 0 26 0 0p32 2 22 1 10 1 1p44 3 30 0 24 3 1 再利用安全性算法检查此时系统是否安全。表3 p1申请资源时的安全性检查资源情况进程workneedalloc

9、ationwork+allocationfinisha b ca b ca b ca b cp12 3 00 2 03 0 25 3 2truep35 3 20 1 12 1 17 4 3truep47 4 34 3 10 0 27 4 5truep27 4 56 0 03 0 210 4 7truep010 4 77 4 30 1 010 5 7true（3） p4请求资源：p4发出请求向量request4（3，3，0），系统按银行家算法进行检查： request4（3, 3, 0）need4（4, 3, 1）; request4（3, 3, 0） <available（2, 3, 0），让p4等待。参考文献：1 崔建平. 深入探讨银行家算法j. 科技信息(学术研究), 2008,(17) . 2 侯刚. 深入解析银行家算法j. 潍坊学院学报, 2006,(02) . 3