银行家算法(操作系统)

前言:银行家算法就真的是银行家算法。可以用银行贷款的实例来类比银行家算法。

一、银行贷款问题

假设有一家银行有一笔m亿的资金,n个客户需要贷款,他们都和银行签订了贷款协议,每个客户所需要贷款的资金不同,且都不超过m亿,但是他们加起来的总贷款和远远超过了m亿。那银行怎样贷款给客户才能使之运转正常呢?

二、银行家算法

1、银行家算法基本思想

在资源分配前,判断系统是否处于安全的状态。若处于安全的状态,就把资源分配给申请的进程,如果处于不安全的状态则令申请资源分配的进程阻塞,不响应其资源申请。

安全状态就是系统按照,为每个相交往的进程分配所需的资源,使每个进程都能在有限的时间内结束。

2、银行家算法的数据结构

  1. 可利用资源向量Available:这是含有m个元素的数组,表示当前系统还有多少可以利用的资源可供分配。
  2. 最大需求矩阵Max:这是一个n*m的矩阵,定义了n个进程中的每一个进程对m类资源的最大需求。
  3. 分配矩阵Allocation:这是一个n*m的矩阵,表示系统中每一类资源已分配给每一个进程的资源数。
  4. 需求矩阵Need:这是一个n*m的矩阵,表示每一个进程尚需的各类资源数。
  5. 资源申请向量Requesti[j]:表示进程pi申请k个j类资源。

3、银行家算法

  1. 如果 Request + Allocation <= Max成立,接着执行步骤2,;否则说明进程的j类资源申请超过了其最大需求量,报错中断返回。
  2. 如果 Request <= Available成立,接着执行步骤3;否则说明系统中现有的j类资源不能满足进程pi的资源申请。结束算法返回。
  3. 系统试探着把资源分配给进程,并修改下面数据结构中的值:
    • Available = Available - Request
    • Allocation = Allocation + Request
    • Need = Need - Request
  4. 调用系统安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,满足进程pi的资源申请;否则,将本次试探分配作废,恢复原来资源分配的状态,不响应进程pi的资源申请,让pi等待。

4、安全性算法

(1)设置两个向量

  1. 工作向量Work:表示系统可提供给进程继续运行所需的各类资源数目,在算法开始时,Work = Available。
  2. Finish:表示是否有足够的资源分配给进程,使之运行完成。有就true,没有就false。

(2)在进程集合中找到满足以下条件的进程:

  1. Finish[i] = false;
  2. Need[i,j] <=Work[j];

如果找到了,接着执行步骤(3)

(3)当进程pi获得资源后,可以顺利执行,完毕后释放所分配的资源。

  1. Work = Work + Allocation
  2. Finish = true

(4)如果所有进程的finish都为true,表示系统处于安全状态。

三、总结

  1. 了解系统当前可分配的资源数目,进程已经分配的资源数目,进程还需分配的资源数目,进程一共需要的资源数目。
  2. 向系统提交申请资源的请求,系统先试着分配给所有的进程(找到一个安全序列)如果申请满足系统的约定,则分配;否则不分配。
  3. 调用系统安全分配算法,看是否安全(找到了安全序列),就真的分配给进程。
版权声明:玥玥 发表于 2021-04-02 0:00:20。
转载请注明:银行家算法(操作系统) | 女黑客导航