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

背景

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

进程

1
2
3
4
5
6
     Allocation   Max   Available
   ABCD   ABCD  ABCD
P1 0014   0656  1520 
P2  1432   1942 
P3  1354   1356
P4  1000   1750

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

1
2
3
4
5
6
  NEED
ABCD
0642 
0510
0002
0750

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

1
2
3
4
5
FINISH
false
false
false
false

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

1
2
3
4
5
6
  NEED    Available
ABCD  ABCD
0642  1520
0510<-
0002
0750

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

1
2
3
4
5
6
 NEED     Available
ABCD  ABCD
0642  1520
0000 +1432
0002-------
0750  2952

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

1
2
3
4
5
FINISH
false
true
false
false

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

1
2
3
4
5
6
 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时,就是安全状态。

安全和不安全的状态

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

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

评论