操作系统 - 看完这篇还读不懂《银行家算法》那我也没办法了

Source

故事背景

为什么想到总结一篇从 0-1 学习银行家算法,读这篇至少要有死锁的概念,网上很多文章根本没讲解当中的一些小概念,连概念和算法过程都不了解,直接上题目怎么看得懂?

原理讲解

非剥夺资源的竞争和进程的不恰当推进顺序会导致死锁,而银行家算法就是为了解决死锁问题——避免死锁。

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

那么此时会有一个问题,如何判断系统是否处于安全状态?算法流程将用下面一张图来表示。

首先是银行家算法中的进程

  1. 包含进程Pi的需求资源数量(也是最大需求资源数量,MAX)
  2. 已分配给该进程的资源A(Allocation)
  3. 还需要的资源数量N(Need=M-A)

Available为空闲资源数量,即资源池(注意:资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量)

假设资源P1申请资源,银行家算法先试探的分配给它(当然先要看看当前资源池中的资源数量够不够),若申请的资源数量小于等于Available,然后接着判断分配给P1后剩余的资源,能不能使进程队列的某个进程执行完毕,若没有进程可执行完毕,则系统处于不安全状态(即此时没有一个进程能够完成并释放资源,随时间推移,系统终将处于死锁状态)。

若有进程可执行完毕,则假设回收已分配给它的资源(剩余资源数量增加),把这个进程标记为可完成,并继续判断队列中的其它进程,若所有进程都可执行完毕,则系统处于安全状态,并根据可完成进程的分配顺序生成安全序列(如{P0,P3,P2,P1}表示将申请后的剩余资源Work先分配给P0–>回收(Work+已分配给P0的A0=Work)–>分配给P3–>回收(Work+A3=Work)–>分配给P2–>······满足所有进程),如此就可避免系统存在潜在死锁的风险。

数据结构与算法

  • 数据结构

可用资源向量:Available,是一个数组,表示现在系统中总共还有多少可用的资源。

例如:A B C 的 Available 是 [1,2,3]

表示现在系统中还有 A 类资源 1 个,B 类资源 2 个,C 类资源 3 个。

最大需求:Max,是一个矩阵,表示某进程最多需要多少某资源,一行代表一个进程,一列代表一个资源。例如

	A B C
 P1 1 2 3
 P2 4 5 6
 P3 7 8 9

// P3 进程最多需要 C 类资源 9 个
// P2 进程最多需要 B 类资源 5 个

分配矩阵:Allocation 表示系统中现在某类资源分配给某进程的数量

	A B C
 P1 1 2 3
 P2 4 5 6
 P3 7 8 9

// P3 进程现在已经分配了 C 类资源 9 个
// P1 进程现在已经分配了 A 类资源 1 个

需求矩阵:Need,表示现在进程中尚需的各类资源数

	A B C
 P1 1 2 3
 P2 4 5 6
 P3 7 8 9

// P1 进程现在还需要 C 类资源 3 个
// P2 进程现在还需要 B 类资源 5 个

Need 矩阵 = Max 矩阵 - Allocation 矩阵;(请一定要理解这条很好理解的原则)

Need 矩阵 = Max 矩阵 - Allocation 矩阵;(请一定要理解这条很好理解的原则)

Need 矩阵 = Max 矩阵 - Allocation 矩阵;(请一定要理解这条很好理解的原则)

也很好理解,最多需要的数量减去现在已经给的数量就是还需要的数量。矩阵的减法直接 对应位置 相减即可。

一般情况下,Max 矩阵和 Alocation 矩阵都是已知条件,求出 Need 矩阵是解题的第一步

  • 算法(银行家——整个过程)

设 request 是进程 P 的请求向量,request[A] = K 表示进程 P 需要 A 类资源 K 个。

当 P 发出资源请求后,系统按照以下步骤进行检查。

  1. 如果 request[A] 的值小于 need[P,A],也就是说如果现在请求的数量小于 need 矩阵中规定的他所需要的数量,那么就转到步骤 2 ;否则认为出错,因为他所请求的数量已经超过了他所宣布的最大值。

  2. 如果 request[A] 的值小于 available[A],也就是说请求的值小于现在系统中有的值,则转向步骤 3 ;否则表示尚足够资源,进程 P 需要等待。

  3. 系统 试探 着把资源分配给进程 P,并修改下面数据结构中的值:

    • 更新可用:Available = Available - request
    • 更新已分配:Allocation[P,A] = Allocation[P,A] + request[A]
    • 更新所需:Need[P,A] = Need[P,A] - request[A];
  4. 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态,若安全才将资源分配给进程 P;否则此次的试探分配作废,恢复原来的资源分配状态,让进程 P 等待。

接下来看一下安全性算法是什么?

  • 算法(银行家——安全性)
  1. 初始时 安全序列 为空
  2. 从 Need 矩阵中找到符合下面条件的行:该行对应的进程不在安全序列中,而且该行小于等于 Available 向量,找到后,把对应的进程加入 安全序列;若找不到,则执行步骤 4
  3. 进程 P 进入 安全序列 后,可顺利执行,直至完成,并释放分配给它的资源,故应执行 Available = Available + Allocation[P],其中 Allocation[P] 表示进程 P 在 Allocation 矩阵中对应的行,返回步骤 2
  4. 若此时安全序列中已有所有进程,则系统处于安全状态,否则处于不安全状态

下面以一个例子来看一下

假定系统中有 5 个进程 {P0,P1,P2,P3,P4} 和 3 类资源 {A,B,C},各类资源的数量分别是 10,5,7,在 T0 时刻的资源分配表如下

  • Tips:起始 Available[A,B,C] = [10,5,7] - Sum(Allocation[A,B,C]) = [3,3,2]([2,3,0])
  • 这个提示我不得不在这里说明下,之前很多人一开始看对这里会有疑问,这个 [3,3,2] 是怎么得到的?这个起始资源 [10,5,7] 又有什么用?

强化练习

  • 题1

  •  题2

  • 题3

Tips:这题不瞒你说,网上很多一开始就放这题,我敢说,没上面概念的铺垫,你让谁在这里加加减减找规律,非常痛苦~现在的你看到这还会觉得“银行家算法”难吗?!