银行家算法

1. 银行家算法概念

1.1 介绍

银行家算法(Banker’s Algorithm)是一个避免操作系统死锁(Deadlock)的著名算法,属于事先预防策略。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。

死锁:当两个以上的运算单元,双方都在等待对方停止执行,以获取系统资源,但是没有一方提前退出时,就称为死锁。

产生死锁必须同时满足以下四个条件:

  • 禁止抢占(no preemption):系统资源不能被强制从一个进程中退出。

  • 持有和等待(hold and wait):一个进程可以在等待时持有系统资源。

  • 互斥(mutual exclusion):资源只能同时分配给一个行程,无法多个行程共享。

  • 循环等待(circular waiting):一系列进程互相持有其他进程所需要的资源。

因此,预防死锁需要打破其中一项。

1.2 概括

当一个进程申请使用资源的时候,银行家算法通过先 试探 分配给该进程资源,然后通过安全性算法判断分配后的系统是否处于安全状态,若判断结果为安全,则给该进程分配资源,若不安全则试探分配作废,让该进程阻塞。

安全系列不唯一,但只要存在一个就是安全策略,一定不会发生死锁

2. 银行家算法具体实现

2.1 术语概念

available:可用资源向量,记录系统中各类资源的当前可利用数目

allocation:记录每个进程中对各类资源当前的占有量

max:记录每个进程对各类资源的最大需求量

need: 记录每个进程中对各类资源当前的需求量,等于max-allocation

request: 请求向量,记录某个进程当前对各类资源的申请量,是银行家算法的入口参数。

2.2 过程

2.2.1 先决条件过程

  1. request[i,j]<need[i,j],否则进程出错
  2. request[i,j]<available[i,j],否认进程阻塞

2.2.2 试探分配过程

  1. 系统试着把资源分配给进程P,并对相应数据结构作如下修改:

    • available[i,j] -request[i,j]

    • allocation[i,j]+request[i,j]

    • need[i,j]-request[i,j]

  2. 系统执行安全性检测子算法,以判断试分配后系统状态是否安全;

  3. 若第4步返回逻辑真值,即“安全”,则完成本次分配,返回;

  4. 否则,撤销此次(即第3步中的)试分配,进程P阻塞。