讲述银行家算法

前言

​ 银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行，这种算法的提出能保证银行在发送贷款的时候，不会发生不满足所有用户需要的情况。

算法介绍

参数

• 可用资源向量 Available, 此时系统的资源保有量及还剩下多少资源
• 最大需求矩阵 Max ，每个线程所需要的各资源总量
• 分配矩阵 Allocation 每个线程已经占有的资源数
• 需求矩阵 Need 此时每个线程还需要的资源数

Need = Max - Allocation

银行家算法的计算过程

假设，此时一个线程发出了资源请求，Request(a,b,c) 及假设中资源一共有3个，而此线程此时请求各需要 a,b,c

1. 首先，我们判断Request是否小于Need 中各资源，如果大于说明它不符合之前提供的最大需求量，报错。小于则跳转到第二步
2. 其次，我们判断Request是否小于Available ,true -----> 第三步，否则失败，此时资源不够
3. 系统试探的把资源分配给此线程，并修改如下几个参数
   • Available[] = Available[] - Request[]
   • Allocation[] = Allocation[] + Request[]
   • Need[] = Need[] - Request[]
4. 系统经过安全性检测，判断是否安全来决定是否分配。

安全性检测

(1) 设置两个工作向量WORK:=AVAILABLE；FINISH[i]=FALSE ；

(2) 从进程集合中找到一个满足下述条件的线程

a. FINISH[i]=FALSE

b. NEED<=WORK

如找到，执行(3)；否则，执行(4)。

(3) 当线程获得资源，可顺利执行，直至完成，从而释放资源。

WORK:=WORK+ALLOCATION ;

FINISH[i]:=TRUE ;

GO TO (2)

(4) 如所有的线程FINISH[i]=TRUE，则表示安全；否则系统处于不安全状态。

总结

简单的说，银行家算法是在线程提供自己需求总量基础上进行的，并根据需求总量Max - 占有量Allocation = 需求量Need。并试探性的分配资源，通过安全性检测判断是否可以形成一个安全序列，最终得到是否分配的结果。