银行家算法

✍ dations ◷ 2025-04-26 03:46: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 - 当前可用的资源

相关

  • 物理有机化学物理有机化学是路易斯·哈米特(Louis Hammett)于1940年创造的一个术语,是指关注化学结构与反应性之间关系的有机化学学科,尤其是将物理化学的实验工具应用于有机分子的研究。
  • 现代文学现代主义文学,又称现代派文学或现代文学,是1890年-1950年间流行于欧美各国的一个国际文学思潮。在纵向上,前承古典主义文学、浪漫主义文学和现实主义文学,后接后现代主义文学。在
  • 鸭鸣报Maurice Maréchal Jeanne Maréchal Henri-Paul Deyvaux-GassierÉrik Emptaz Louis-Marie Horeau鸭鸣报(法语:Le Canard enchaîné)是法国一份以讽刺而闻名的周报,逢星期三
  • 邻苯二甲酸二(2-丙基庚)酯邻苯二甲酸二(2-丙基庚)酯(英语:Di(2-propylheptyl) phthalate,或bis(2-propylheptyl) benzene-1,2-dicarboxylate,di(propylheptyl) orthophthalate,缩写DPHP),是一种化学式为C28H
  • 红糟红糟或红酒糟是红曲酒发酵后,榨去酒液经过筛滤后所剩下的酒糟(酒滓)。红糟拥有天然红色色泽跟独特的酒香和微酸,是中国南方广东、福建一带的一种调味品。 红糟不是红曲米(红曲),
  • 鲁尔区北莱茵-威斯特法伦州鲁尔区是位于德国西部北莱茵-威斯特法伦境内的城市群,它拥有580万人口和4435平方公里的面积。他是莱因-鲁尔城市群的一部分,整个城市群一共拥有超过1000万
  • DeNADeNA株式会社(株式会社ディー・エヌ・エー,Kabushikigaisha Dī-Enu-Ē)是一家日本网络公司(英语:Dot-com company),创立之初以电子商务起家,现在营运范围涵盖社交媒体、电子商务、
  • 韩光渭韩光渭(英语:Kuang-Wei Han,1930年-2019年6月1日),中华民国海军少将退役,山东省即墨县人,已退休工程科学博士,是中华民国重要国防武器雄风导弹一型、二型计划主持人,被称为“雄风导弹
  • 亚特兰大奥运第二十六届夏季奥林匹克运动会(英语:the Games of the XXVI Olympiad,法语:les Jeux de la XXVIe Olympiade),于1996年7月19日至8月4日在美国的亚特兰大举行,先前的世界杯也在同一
  • 邦加槟港邦加槟港又称槟港、邦加槟榔(印尼语:Pangkal Pinang)是印尼邦加岛的最大市镇,也是邦加-勿里洞省的首府。位于南纬2度10分、东经106度8分,在邦加岛东岸中部。1990年时,人口有108,411