银行家算法

来自计算思维百科
跳转至: 导航搜索
银行家算法.png

银行家算法是计算机处理机调度中最有代表性的避免死锁的算法,是由Dijkstra提出来的,算法得名源于该算法能用于银行系统先进贷款的发放而得名。

基本概念

在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比操作系统,资金就是资源,客户就相当于要申请资源的进程。

我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。

为保证资金的安全,银行家规定:

(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客;

(2) 顾客可以分期贷款,但贷款的总数不能超过最大需求量;

(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款;

(4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金.

操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源,若能满足则按当前的申请量分配资源,否则也要推迟分配。

应用范围

银行家算法常用于解决如何合理安排资源避免资源出现竞争浪费的问题,例如银行系统现金贷款的发放,高校选课课程教室安排等。

使用方法及步骤

  1. 找到问题中的资源管理者、资源和资源请求者
  2. 引入4个向量,用来表示每一类可利用资源的数量、资源请求者的对每一类资源的最大需求数量、每一类资源已分配的数量以及资源请求者还需要的每一类资源数量
  3. 每当有新的请求者提出请求时,若请求者请求的资源数量小于或等于其最大需求量,则转向第4步;否则推迟分配;
  4. 若需要的资源数量小于或等于现有资源数量,则转向第5步;否则推迟或拒绝分配;
  5. 管理者试着把资源分配给请求者,并将步骤2 中对应的资源数量减去当前分配的数量;
  6. 重复步骤3、4、5

应用案例

应用1-银行贷款的发放及收回

案例:某银行最近新增了几个贷款的客户,客户A和客户B分别要借贷60万和50万,客户A先来银行借的钱,客户A和客户B都是一次性借款和还款。现银行有100万可供借贷。为了保证客户A和客户B都能借到相应的款项,银行应该如何处理客户的借贷申请?

解决步骤:

  1. 银行有100万可供借贷,客户A先申请贷款60万元,则银行给客户A 发放60万元的贷款,此时银行可供借贷的钱为100-60=40万元;
  2. 客户B要借款50万,银行只有40万,则客户B必须等待客户A将借款还给银行才能借,此时银行可供借贷的资金仍为40万元。
  3. 客户A还给银行60万元,银行此时可借贷的资金为100万元,银行给客户B发放50万元的款项,银行剩余50万元。
  4. 客户B还给银行50万元,银行可供借贷的资金又变回100万元。

在这个过程中,由于遵循了银行家算法的原则,客户A和客户B都顺利地借到了钱,而不会因为借贷的总额是110万元而都借不到。

应用2-高校选修教室分配

案例:有5门高校选修课程A、B、C、D、E,课程A和B选课的学生有50个,课程C和D,选课的学生有30个,课程E选课的学生有20个。上课时间如下表所示,空闲的教室只有2个,分别为教室H1(容纳60人)、H2(容纳30人)。假设其他教室的使用时间都已经被安排好了,应该如何安排教室才能保证每门课程都能在对应的上课时间使用教室?

课程

周一

周二

周三

周四

周五

第1,2节

 

 

 

 

 

第3,4节

 

 

 

 

 

第5,6节

 

 

 

 

 

第7,8节

 

 

 

 

 

第9,10节

 

课程A(50人)、课程C(30人)

 

课程D

(30人)

 

第11,12节

 

 

 

 

课程B(50人)课程E(20人)

解决步骤:

  1. 课程A和课程C在同一时间上课,教室H1能容纳60个人,课程A选课的人数是50<60,课程A应该分配教室H1, 课程C有30个学生选,教室H2能容纳30人,应该分配教室H2
  2. 课程D没有和其他四门课在同一时间上课,选课的人有30个,应该选教室H2
  3. 课程B和课程E在同一时间上课,教室H1能容纳60个人,课程A选课的人数是50<60,课程A应该分配教室H1, 教室H2能容纳30人,课程E有20个学生选,应该分配教室H2
课程

周一

周二

周三

周四

周五

第1,2节

 

 

 

 

 

第3,4节

 

 

 

 

 

第5,6节

 

 

 

 

 

第7,8节

 

 

 

 

 

第9,10节

 

课程A—教室H1

课程C—教室H2

 

课程D—教室H2

 

 

第11,12节

 

 

 

 

课程B—教室H1

课程E—教室H2

可以体现的计算思维

银行家算法是一个动态策略排除死锁的算法,体现了计算思维中的规划和调度特点,它能有效合理地安排有限资源的使用顺序和数量分配,使得每一个资源请求者都可以顺利使用资源,从而保证所有事件得到顺利执行。