银行家算法流程图+C++源代码+实验报告 第2页
Receive(P2,M); <a> Receive(P1,Q); <a>
Send(P2,N); <b> Send(P1,R); <b>
非可剥夺资源死锁
死锁发生：双方都等待对方去生成资源，如次序：P1<a> P2<a>
总的来说，死锁和不可剥夺资源有关。我们讨论的重点放在不可剥夺资源。
使用一资源事件的顺序如下：申请资源，使用资源，释放资源。
另一种原因是由于进程推进顺序不合适引发的死锁。资源少也未必一定产生死锁。就如同两个人过独木桥，如果两个人都要先过，在独木桥上僵持不肯后退，必然会因竞争资源产生死锁；但是，如果两个人上桥前先看一看有无对方的人在桥上，当无对方的人在桥上时自己才上桥，那么问题就解决了。所以，如果程序设计得不合理，造成进程推进的顺序不当，也会出现死锁。
其模型基于一个小城镇的银行家，他向一群客户分别承诺了一定金额的贷款，而他知道不可能所有客户同时都需要最大的贷款额。在这里，我们可将客户比作进程，银行家比作操作系统。银行家算法就是对每一个客户的请求进行检查，检查如果满足它是否会引起不安全状态。假如是，那么不满足该请求；否，那么便满足。
怎样得知一个状态是否安全呢？
所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，…，Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。
更通俗一点地讲，检查状态是否安全的方法是看它是否有足够的剩余资源满足一个距最大需求最近的客户。如果有，那么这比投资被认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，那么该状态是安全的，最初的请求可以批准。
需要指出的是，不安全状态并不一定引起死锁，因为客户并不一定申请其最大贷款额度，但银行家不敢抱有这种侥幸心理。
在此，我们引入了两个向量：Resourse（资源总量）、Available（剩余资源量） 以及两个矩阵：Claim（每个进程的最大需求量）、Allocation（已为每个进程分配的数量）。它们共同构成了任一时刻系统对资源的分配状态。
向量模型：
R1 R2 R3
矩阵模型：
R1 R2P1
P2
P3
这里，我们设置另外一个矩阵：各个进程尚需资源量（Need）,可以看出
Need = Claim – Allocation
因此，我们可以这样描述银行家算法：
设Request[i]是进程Pi的请求向量。如果Request[i , j]=k，表示Pi需k个Rj类资源。当Pi发出资源请求后，系统按下述步骤进行检查:
e．if (Request[i]<=Need[i]) goto (2);
else error(“over request”);
f．if (Request[i]<=Available[i]) goto (3);
else wait();
系统试探性把要求资源分给Pi（类似回溯算法）。并根据分配修改下面数据结构中的值。
Available[i] = Available[i] – Request[i] ；
Allocation[i] = Allocation[i] + Request[i]；
Need[i] = Need[i]-Request[i];
系统执行安全性检查，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程以完成此次分配；若不安全，试探方案作废，恢复原资源分配表，让进程Pi等待。
系统所执行的安全性检查算法可描述如下：
设置两个向量：Free、Finish
工作向量Free是一个横向量，表示系统可提供给进程继续运行所需要的各类资源数目，它含有的元素个数等于资源数。执行安全算法开始时，
Free = Available.
标记向量Finish是一个纵向量，表示进程在此次检查中中是否被满足，使之运行完成，开始时对当前未满足的进程做Finish[i] = false；当有足够资源分配给进程(Need[i]<=Free)时，Finish[i]=true，Pi完成，并释放资源。
从进程集中找一个能满足下述条件的进程Pi
① Finish[i] == false(未定)
② Need[i] <= Free (资源够分)
当Pi获得资源后，认为它完成，回收资源:
Free = Free + Allocation[i] ;
Finish[i] = true ;
Go to step(1);
试探此番若可以达到Finish[0..n]:=true，则表示系统处于安全状态，然后再具体为申请资源的进程分配资源。否则系统处于不安全状态。
我们还举银行家的例子来说明：设有客户A、B、C、D，单一资源即为资金（R）。
下列状态为安全状态，一个安全序列为：C->D->B->A
A 1 6
B 1 5
C 2 4
D 4 7
Available = (2) ; Resourse = (10) ;
可以看出，银行家算法从避免死锁的角度上说是非常有效的，但是，从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，而且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原本可用的资源也可能突然间变成不可用（如磁带机可能坏掉）。因此，在实际中，如果有，也只有极少的系统使用银行家算法来避免死锁。
5、程序运行界面
6、结束语
银行家算法是避免死锁的一种重要方法，用高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用：第二个为等待条件，即一个进程请求资源不能满足时，它必须等待，但它仍继续保持已得到的所有其他资源：第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可用解决生活中的实际问题,如银行贷款等.
参考文献:
汤子瀛.《计算机操作系统》.西安:西安电子科技大学出版社,2003.
严蔚敏.《数据结构(C语言版) 》.北京:清华大学出版社,1999
朱福喜.《Java语言程序设计》.北京:清华大学出版社,2005.
谢桂芳.《浅析用P、V操作实现进程的同步与互斥》.四川教育学院学报,2004
上一页 [1] [2] [3] [4] 下一页
银行家算法流程图+C++源代码+实验报告 第2页下载如图片无法显示或论文不完整，请联系qq752018766
