银行家算法

一句话

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

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

一张图

首先是银行家算法中的进程：
- 包含进程Pi的需求资源数量（也是最大需求资源数量，MAX）
- 已分配给该进程的资源A（Allocation）
- 还需要的资源数量N（Need= M - A）
Available为空闲资源数量，即资源池（注意：资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量）

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

若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其他进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0, P3, P2, P1}表示将申请后的剩余资源Work先分配给P0 -> 回收（Work+已分配给P0的A0=Work） -> 分配给P3 -> 回收（Work + A3 = Work）-> 分配给P2 -> ...... 满足所有进程）。

如此就可避免系统存在潜在死锁的风险。

来个例子

在银行家算法中，若出现下述资源分配情况：

注：题中共四种资源，P0的Allocation为（0，0， 3， 2）表示已分配给P0的第一种资源和第二种资源为0个，第三种资源3个，第四种资源2个。

该状态是否安全？
若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？
利用安全性算法对上面的状态进行分析（见下表），找到一个安全序列{P0, P3, P4, P1, P2}，故系统是安全的。
P2发出请求向量Request(1,2,2,2)，系统按银行家算法进行检查:
1. Request2(1,2,2,2) <= Need2(2,3,5,6)
2. Request2(1,2,2,2) <= Available(1,6,2,2)
3. 系统先假定可为P2分配资源，并修改Available，Allovation2和Need2向量：
  1. Available = （0，4，0，0）
  2. Allocation2 = （2，5，7，6）
  3. Need2 = （1，1，3，4）
  此时在进行安全检查，发现Available=(0, 4, 0, 0)，不能满足任何一个进程，所以判定系统进入不安全状态，即不能分配给P2相应的Request(1,2,2,2)。

简单伪代码

P - 进程的集合

Mp - 进程p的最大的请求数目

Cp - 进程p当前被分配的资源

A - 当前可用的资源

while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
            // Mp - Cp就是Need
        if (Mp − Cp ≤ A) {
             /* p可以获得他所需的资源。假设他得到资源后执行；执行终止，并释放所拥有的资源。*/
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;