银行家算法

✍ dations ◷ 2025-07-12 16:59:33 #操作系统技术,荷兰发明

银行家算法(Banker's Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

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

      Allocation   Max   Available    ABCD    ABCD  ABCD P1   0014    0656  1520  P2  1432    1942  P3  1354    1356 P4  1000    1750

我们会看到一个资源分配表,要判断是否为安全状态,首先先找出它的Need,Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源),计算结果如下:

   NEED ABCD 0642  0510 0002 0750

然后加一个全都为false的字段

 FINISH false false false false

接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)

   NEED    Available ABCD  ABCD 0642  1520 0510<- 0002 0750

P2的需求小于能用的,所以配置给他再回收

  NEED     Available ABCD  ABCD 0642  1520 0000 +1432 0002------- 0750  2952

此时P2 FINISH的false要改成true(己完成)

 FINISH false true false false

接下来继续往下找,发现P3的需求为0002,小于能用的2952,所以资源配置给他再回收

  NEED      Available ABCD  A B C D 0642  2 9 5 2 0000 +1 3 5 4 0000---------- 0750  3 12 10 6


依此类推,做完P4→P1,当全部的FINISH都变成true时,就是安全状态。

如果所有过程有可能完成执行(终止),则一个状态(如上述范例)被认为是安全的。由于系统无法知道什么时候一个过程将终止,或者之后它需要多少资源,系统假定所有进程将最终试图获取其声明的最大资源并在不久之后终止。在大多数情况下,这是一个合理的假设,因为系统不是特别关注每个进程运行了多久(至少不是从避免死锁的角度)。此外,如果一个进程终止前没有获取其它能获取的最多的资源,它只是让系统更容易处理。

基于这一假设,该算法通过尝试寻找允许每个进程获得的最大资源并结束(把资源返还给系统)的进程请求的一个理想集合,来决定一个状态是否是安全的。不存在这个集合的状态都是不安全的。

P - 进程的集合

Mp - 进程p的最大的请求数目

Cp - 进程p当前被分配的资源

A - 当前可用的资源

相关

  • 表观因素表观遗传学(英语:epigenetics)又译为表征遗传学、拟遗传学、表遗传学、外遗传学以及后遗传学,在生物学和特定的遗传学领域,其研究的是在不改变DNA序列的前提下,通过某些机制引起可
  • 纯合纯合子(英语:homozygote),亦称同型合子,在遗传学上,二倍体生物的某个基因座上拥有相同的等位基因,而基因型和基因的表现型也是完全相同和对等。例如“AA”、“OO”。
  • 天文单位天文单位(缩写的标准符号为AU,也写成au、a.u.或ua)是天文学上的长度单位,曾以地球与太阳的平均距离定义。2012年8月,在中国北京举行的国际天文学大会(IAU)第28届全体会议上,天文学家
  • 尤文图斯队尤文图斯足球俱乐部(Juventus Football Club S.p.A)简称尤文(Juve),是一家位于意大利皮埃蒙特大区都灵市的足球俱乐部。尤文图斯传统上的主场球衣是黑白相间的上衣配上黑色或白色
  • 保加利亚共和国面积以下资讯是以2018年估计家用电源国家领袖国内生产总值(购买力平价) 以下资讯是以2018年估计国内生产总值(国际汇率) 以下资讯是以2018年估计人类发展指数 以下资讯是以2018
  • 王国之心 χ《王国之心 χ》是由史克威尔艾尼克斯及华特迪士尼互动工作室共同开发的角色扮演游戏,王国之心系列作品之一,平台是网页浏览器, 并在2013年7月18日于日本推出,其在雅虎游戏、Han
  • 赫鲁晓夫楼赫鲁晓夫楼(俄语:Хрущёвка,转写:Khrushchyovka)是一种造价低廉、盒子式或砌体结构三至五层公寓的公寓楼,苏联在20世纪60年代的尼基塔·赫鲁晓夫执政时期大量兴建,并以他的
  • 邢台大地震邢台大地震发生于1966年3月8日5时29分,震中位于河北省邢台隆尧县东,震级达里氏6.8级。震源深度10千米,震中烈度为9度,同年3月22日在宁晋县东南分别发生了6.7级和7.2级地震各一次
  • 贝特西·罗斯贝特西·罗斯(英语:Betsy Ross;1752年1月1日 - 1836年1月30日;娘家名:伊丽莎白·格里斯科姆;再婚名:伊丽莎白·阿什本;第三次再婚名伊丽莎白·科莱珀尔)被美国公众广泛认作美国国旗的
  • 抽象与具体抽象和具体(英语:Abstract and concrete)是这样一种分类,标志着一个术语描述的对象是否有物理上的指示物(英语:referent)。抽象对象(抽象客体,英语:abstract object)没有物理的实指,但是