不会做，求清晰的银行家算法解题过程程

来源：蜘蛛抓取(WebSpider) 时间：2017-01-05 01:36 标签： 银行家算法解题过程

专业文档是百度文库认证用户/机构上传的专业性文档，文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“专业文档”标识的文档便是该类文档。

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取，非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档。

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取，非会员用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档。

付费文档是百度文库认证用户/机构上传的专业性文档，需要文库用户支付人民币获取，具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档。

共享文档是百度文库用户免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定。只要带有以下“共享文档”标识的文档便是该类文档。

嘿嘿，今晚心血来潮，在宿舍把银行家算法实现了。

主要的思想是 舍大取小，先满足小的，最后才满足大的。 // 进程运行状态标志 // version 2 采用动态分配数组，为了函数调用的方便，使用全局指针 // 检测此时的分配状态是否安全 （核心函数） // 所有进程状态置零 // 以第一类资源为基准，选取该资源需求量最小的进程 // 如果资源能够分配了，那么进程就能够运行结束，然后释放资源，这里需要回收资源 // 释放所有的内存空间 // 释放所有的内存空间

安全状态指的是系统能按某种进程推进顺序(P1,P2,…,Pn)为每个进程分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时，序列(P1,P2,…,Pn)为安全序列。如果系统无法找到这样一个序列，则称系统处于不安全状态。
虽然并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态，就有可能进入死锁。反之，只要系统处于安全状态，就不会进入死锁状态。因此，避免死锁的实质在于，系统在进行资源分配时，应使系统不进入安全状态。

所以，只要存在一种分配序列时，系统就是安全的。
假设系统中有三个进程P1，P2，P3，共有12台磁带机。进程P1总共要求10台磁带机，进程P2要求4台磁带机，进程P3总共要求9台磁带机。假设在T0时刻，进程P1，P2，P3分别已经获得5、2、2台，尚有3台为分配。如下所示：
这样的系统在T0时刻是安全的，存在一个安全序列P2->P1->P3。过程：将剩余的磁带机取出2台分给P2，使之继续运行，待P2完成后便可释放4台磁带机，此时可用资源为4+(3-2)=5，然后将这5台资源分配给P1，待P1运行完成后可释放10台，P3便可以获得足够的资源，从而使得P1，P2，P3每个进程都能完成。

具有代表性的解决死锁的问题的算法是银行家算法，起名原因是以确保银行在发放现金贷款时，不会发生不能满足客户需要的情况。

为实现银行家算法，每一个进程进入系统的时候，该进程必须告诉系统，在运行的过程中可能需要每种资源类型的最大单元数目，其数目不能超过系统所拥有的资源总量。当进程请求某一资源的时候，系统必须首先确定是否有足够的资源分配给该进程。若有，就会计算将这些资源分配给该进程后，系统会不会处于不安全状态。如果不会处于不安全状态，系统才会将资源分配给它，否则就会让进程等待。

1.银行家算法中的数据结构
可利用资源向量，是一个含有m个元素的数组，其中每一个元素代表一类可利用的资源数目，初始值是系统中所分配的该类全部可用资源的数目，其数值随该类资源的分配和回收而改变。
最大需求矩阵，是一个n*m的矩阵，定义了系统中n个进程中的每一个进程对m类资源的最大需求。
分配矩阵，是一个n*m的矩阵，定义了系统中每一类资源当前分配给每一进程的资源数。
需求矩阵，是一个n*m的矩阵，表示每一个进程尚需的各类资源数。

设Request_i是进程Pi的请求向量，如果Request_i[j]=K，表示进程Pi需要K个Rj的类型的资源。当PI发出资源请求后，系统按下述步骤进行检查：
（1）如果Request_i[j]<=Need[i,j]，便转向（2）；否则，出错，因为所需的资源已经超过宣布的最大值。
（3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成此次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

（1）设置两个向量，工作向量work，表示可提供给进程继续运行所需的各类资源数目，含有m个元素，在执行安全算法开始时，work:=Available;finish，表示系统是否有足够的资源分配给进程，使之运行完成。开始finish[i]:=false，当有资源分配给它时，finish[i]:=true。
（2）从进程集合中找到一个能满足下述条件的进程：
若找到，执行（3）；否则，执行（4）。
（3）当进程Pi获得资源后，可顺序执行，直至完成，并释放出分配给它的资源，故应执行：
（4）如果所有进程finish[i]=true都满足，则系统处于安全状态；否则，系统处于不安全状态。

我要回帖

更多关于 银行家算法解题过程 的文章

 

随机推荐