计算机考研专业课难点辅导：银行家算法

银行家算法是一种具有代表性的避免死锁的算法，是由Dijkstra给出的一个算法。在学习银行家算法之前，我们要先简单地了解死锁的基本知识。

　　死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁。我们形象的解释为，死锁就是进程之间“互相等待、互相不放弃”，也就是说，A进程占有X资源，正等待B进程所占有的Y资源，而B进程也正等待着A进程的X资源，它们之间谁也不愿意先放弃，由此僵持下去，就死锁了。

　　造成死锁的原因是进程之间竞争资源和推进顺序不合适，但是，最根本原因就是系统的资源不足。死锁发生的必要条件有以下4个：

　　(1)互斥条件：即一个资源每次只能被一个进程使用，在操作系统中这是真实存在的情况。

　　(2)保持和等待条件：有一个进程已获得了一些资源，但因请求其他资源被阻塞时，对已获得的资源保持不放。

　　(3)不可剥夺条件：有些系统资源是不可剥夺的，当某个进程已获得这种资源后，系统不能强行收回，只能由进程使用完时自己释放。

　　(4)环路等待条件：若干个进程形成环形链，每个都占用对方要申请的下一个资源。

[page] 有了上述基础知识后，我们再来讨论银行家算法。简单地说，我们可以这么理解银行家算法：银行在放贷时，需要考虑所放的贷款是否能收回来，是否会导致银行无法运营下去。具体到进程上，就是系统给进程分配资源的时候，需要考虑资源分配之后，是否能避免死锁的发生。

　　为了实现银行家算法，系统中需要设置一些数据结构。我们假设系统中有n个进程(P1，P2，…，Pn)，m类资源(R1，R2，…，Rm)，银行家算法中使用的数据结构如下：

　　(1)可利用资源数组(Available)，其每个元素代表一类资源的空闲资源数目，初始值是系统中所配置的这类资源的数目，该数目随该类资源的分配和回收而动态地改变。如果Available(j)=k，则表示系统中现有k个Rj类空闲资源。

　　(2)进程最大需求矩阵(Max)，定义系统中每一个进程对m类资源的最大需求数目，因此，这是一个n×m的矩阵，如果Max(i，j)=k，则表示进程Pi需要Rj类资源的个数为k。

　　(3)分配矩阵(Allocation)，也是一个n×m的矩阵，表示系统中每一类资源当前已经分配给每一个进程的数目。如果Allocation(i，j)=k，则表示进程Pi当前已分配到Rj类资源的数目为k。

　　(4)需求矩阵(Need)，也是一个n×m的矩阵，表示系统中每一个进程还需要的各类资源数目。如果Need(i，j)=k，则表示进程Pi还需要k个Rj类资源，才能完成任务。

　　根据以上的介绍，显然，进程最大需求矩阵、分配矩阵和需求矩阵之间的关系如下：

　　Need(i，j) = Max(i，j)- Allocation(i，j)

[page]
银行家算法的具体描述如下：

　　设Requesti是进程Pi的请求向量，Requesti(j)=k表示进程Pi请求分配Rj类资源k个。当Pi发出资源请求后，系统按下述步骤进行检查：

　　(1)如果Requesti≤Needi，则转向步骤(2);否则出错，因为进程所申请的资源数目已经超过了它所实际所需要的数目。

　　(2)如果Requesti≤Availablei，则转向(3);否则，表示系统中没有足够的资源满足进程Pi的申请，Pi必须等待。

　　(3)系统尝试把申请的资源分配给进程Pi，并修改下面数据结构中的数值：

　　Availablei = Availablei – Requesti;
　　Allocationi = Allocationi + Requesti;
　　Needi = Needi – Requesti;

　　(4)系统执行安全性算法，检查此次尝试资源分配后，系统是否处于安全状态。如果安全，则正式把资源分配给进程Pi，完成本次分配;否则，将尝试分配做废，恢复原来的资源分配状态，让Pi等待。

　　系统所执行的安全性算法描述如下：

　　(1)设置2个数组Work和Finish。其中：
　　① Work表示系统可提供给进程继续运行的各类资源的空闲资源数目，它含有m个元素，执行安全性算法开始时，Worki=Availablei。
　　② Finish表示系统是否有足够的资源分配给进程，使之运行完成，开始时，Finishi=false;当有足够资源分配给进程Pi时，令Finishi=true。

　　(2)从进程集合中找到一个资源满足下述条件的进程：

　　Finishi==false;
　　Needi≤ Work;

　　如找到则执行步骤(3)，否则执行步骤(4)。

　　(3)当进程Pi获得资源后，可顺利执行直到完毕，并释放出分配给它的资源，所以应执行：

　　Worki = Worki + Allocationi;
　　Finishi = true;
　　Goto Step (2);

　　(4)如果所有进程的Finishi都为True，则表示系统处于安全状态;否则，系统处于不安全状态。

[page] 如果只通过学习上述文字和伪代码描述的银行家算法，考生可能感觉银行家算法十分抽象。这不是大家所希望的，也不是跨考教育辅导的方法，跨考教育强调通过实际例子来帮助学员对相关理论知识的消化，“理论实例化，难点简易化，抽象通俗化”是跨考教育对辅导老师的要求。为了遵循跨考教育的这一传统做法，下面，我们通过一个例子来加深对银行家算法的理解。

　　假设系统中有4个进程P1、P2、P3、P4，三类资源R1、R2、R3，数量分别为9、3、6，在T0时刻的资源分配情况如表1所示。

表1 TO时刻资源分配表

进程﹨资源

Max

Allocation

Need

Available

(1)T0时刻的安全性分析

　　利用安全性算法对T0时刻的资源分配情况进行分析，可得表2所示的T0时刻的安全性分析结果。

[page]

表2 TO时刻安全性分析

进程﹨资源

Work

Need

Allocation

Work+Allocation

Finish

点击右侧咨询或直接前往了解更多

考研院校专业选择和考研复习计划
2023备考学习	2023线上线下随时学习	34所自划线院校考研复试分数线汇总
	2022考研复试最全信息整理	全国各招生院校考研复试分数线汇总
	2023全日制封闭训练	全国各招生院校考研调剂信息汇总
2023考研先知	考研考试科目有哪些？	如何正确看待考研分数线？
	不同院校相同专业如何选择更适合自己的	从就业说考研如何择专业？
	手把手教你如何选专业？	高校研究生教育各学科门类排行榜

当前位置: 首页> 考研专业课> 正文

考研专业课相关栏目

考研真题备考资料考试大纲复习指导时政热点马原毛中特近现代史纲要

考研热点