基于银行家算法的综述
未经允许，严禁转载与抄袭
摘要
银行家算法是一个避免死锁的著名算法，它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在操作系统中也可用来实现避免死锁。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。
关键词
操作系统 死锁 银行家算法 数据机构
引言
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。那么银行家算法是如何避免死锁的，其中涉及的数据结构又有哪些？
1 总体分析
1.1 算法概述
最有代表性的避免死锁的算法是Dijkstra的银行家算法。起这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放贷款时，不会发生不能满足所有客户需要的情况。在OS中也可以用它来实现避免死锁。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
为实现银行家算法，每一个新进程在进入系统时，它必须申明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的资源总量。当进程请求一组资源时，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算在将这些资源分配给进程后，是否会使系统处于不安全状态。如果不会，才将资源分配给它，否则让进程等待。
1.2 安全状态
假设系统中存在n个并发进程，分别为P1，P2，P3……Pn，每个进程完成后必须将其资源返还给系统，以便下一个进程可以使用，使得n个进程都能顺利完成资源的分配，则该序列称为安全系列，此时系统处于安全状态。
如果系统无法找到这样一个安全系列，则称系统处于不安全状态。在死锁的避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避免发生死锁；反之，当系统处于不安全状态时，则有可能进入到死锁状态。因此，避免死锁的实质在于系统在进行资源分配时，因此系统进入安全状态，不进入不安全状态。
1.3 死锁
1.3.1 死锁的定义
在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。或者说每个进程所等待的事件是该组中其他进程释放所占有的资源。但由于所有这些进程已都无法运行，因此这些进程都不能释放资源，致使没有任何一个进程可被唤醒。这样这组进程只能无限期的等待下去。由此可以给出所作出如下的定义：
如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。
1.3.2 产生死锁的必要条件
虽然进程在运行过程中可能会发生死锁，但产生进程死锁是必须具备一定的条件的，综上所述不难看出产生死锁必须同时具备下面4个必要条件，只要其中任何一个条件不成立，死锁就不会发生。
（1）互斥条件。进程对所分配到的资源进行排它性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其它进程请求该资源，则请求进程只能等待，直至占有该资源的进程使用完毕释放。
（2）请求和保持条件。进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
（3）不可抢占条件。进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放。
（4）循环等待条件。在发生死锁时，必然存在一个进程——资源的循环链，即进程集合{P0，P1，P2，……，Pn}中的P0正在等待一个P1占用的资源，P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
1.3.3 处理死锁的方法
目前处理死锁的方法可归结为4种
（1）预防死锁。预防死锁是一种较简单和直观的事先预防方法。该方法是通过设置某些限制条件，去破坏产生死锁4个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。
（2）避免死锁。避免死锁同样是属于事先预防策略，但它并不是事先采取各种限制性措施，去破坏产生死锁的4个必要条件，而是在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。
（3）检测死锁。检测死锁无需事先采取任何限制性措施，允许进程在运行过程中发生死锁，但可以通过检测机构及时地检测出死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。
（4）解脱死锁。当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用的方法是撤销一些进程，回收进程的资源，将进程分配给已处于阻塞状态的进程，使其能继续运行。
上述的4种方法，从1到4，对此所的防范程度逐渐减弱，但对应的是资源利用率的提高，以及进程资源因素而堵塞的频度下降&#
本文链接：https://my.lmcjl.com/post/8289.html
4 评论