银行家算法

✍ dations ◷ 2025-04-04 11:10:45 #操作系统技术,荷兰发明

银行家算法(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 - 当前可用的资源

相关

  • 诺贝尔生理学与医学奖诺贝尔生理学或医学奖(瑞典语:Nobelpriset i fysiologi eller medicin),通常合称诺贝尔生理医学奖,由诺贝尔基金会管理,该奖项每年颁发一次,用于表彰在生理学或医学领域作出重要发
  • 裂谷热裂谷热(英语:Rift Valley fever)又称作里夫谷热,是一种由病毒引起的人畜共通病,它的症状程度从轻微到严重都有。轻微的症状包括:发烧、肌肉疼痛、以及头痛(常持续数天到一周);严重的
  • 丹尼尔·伯努利丹尼尔·伯努利(Daniel Bernoulli,1700年2月8日-1782年3月17日),生于荷兰格罗宁根,著名数学家,约翰·伯努利之子,为伯努利家族代表人物之一。其伯努利定律适用于沿着一条流线的稳定
  • Netscape 6Netscape 6是网景通信的跨平台网络包,因为Netscape 5实质上被废弃,所以6是承接之前的网景通信家族4.8版。此版本和之后的Netscape 7单纯是修改自Mozilla Suite。整个包包含Nav
  • 非对称性二甲基精氨酸非对称性二甲基精氨酸(英文:Asymmetric dimethylarginine,简称ADMA)是一种自然存在于血浆内的化合物。它是在人体细胞内细胞质中发生的蛋白质修饰过程产生的代谢副产物,与精氨酸
  • Course in General Linguistics《普通语言学教程》(法语:Cours de linguistique générale)是由索绪尔的学生查尔斯巴利和薛施蔼基于他们老师1906年和1911年在日内瓦大学几年之间的讲座笔记而编辑的语言学著
  • 莫莱-明托改革莫莱-明托改革(Morley-Minto Reforms, Government of India Act 1909)即“1909年印度政府法案”,因由当时印度事务大臣、自由党(Liberal Party)政治家兼作家约翰·莫莱和时任总督
  • 尖音库蚊尖音库蚊(学名:Culex pipiens),又称淡色库蚊、家蚊、混杂家蚊或地下家蚊,是蚊科的一种吸血蚊子。这个物种是一些疾病的载体,如日本脑炎、脑膜炎、荨麻疹,在美国,它传播西尼罗河病毒
  • 阳明堡机场阳明堡机场位于山西省忻州市代县阳明堡镇小茹解村村南一带,是一个已经废弃的军用机场,1937年9月建成,但不久后即被日军占领,作为日军占领山西各地的基地。1937年10月19日,八路军
  • 威尔与格蕾丝《威尔与格蕾丝》(Will & Grace)是一部美国情景喜剧,根据《威廉·杜鲁门与格蕾丝·阿德勒之间的关系》改编,故事被设定发生在纽约市。该剧自1998年9月21日起在美国全国广播公司