银行家算法

银行家算法是著名的死锁避免算法，其思想是：把操作系统视为银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源。进程运行之前先声明对各种资源的最大需求量，当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量。若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚须的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。

问题描述

设计程序模拟避免死锁的银行家算法的工作过程。假设系统中有n个进程： $P_1,P_2,\dots,P_n$ ，有m类可分配资源 $R_1,\dots,R_m$ ，在某时刻，进程 $P_i$ 已分配到的j类资源为 $A l l o c a t i o n [i] [j]$ 个，还需要j类资源 $n e e d [i] [j]$ 个，目前系统剩余j类资源 $A v a i l a b l e [j]$ 个。

实验要求

判断当前状态是否安全。若安全，给出安全序列；若不安全，给出理由。
对于下一个时刻，某个进程提出资源请求Request(R1,…,Rm)，使用银行家算法作为判读是否相应该响应该请求的决策依据。
输入某时刻的资源分配表和进程请求信息，输出安全序列分析，给出决策方案。

数据结构描述

系统可用资源向量 $A v a i l a b l e [m]$
最大需求矩阵 $M a x [n] [m]$
分配矩阵 $A l l o c a t i o n [n] [m]$
需求矩阵 $N e e d [n] [m]$

其中，n是进程数量，m是资源种类数量。

算法描述

输入：T0时刻的资源分配表
输出：Pi发出资源请求后，进行的安全序列分析表和安全序列。若不安全，则给出不安全产生的原因。

进程Pi发出请求 $Request_i$ ，首先检查其合法性，若 $Request_i\le Need[i]$ 则继续进行，否则报错；
若 $Request_i\le Available$ ，则继续进行，否则认为当前资源不足，不响应当前请求；
系统试探性把资源分配给进程Pi：
$Available-=Request_i$
$Allocation[i]+=Request_i$
$Need[i]-=Request_i$
使用银行家算法进行安全性检查，检查此次资源分配后，系统是否处于安全状态，若安全才正式将资源分配给进程Pi；否则本次的试探作废，Pi继续等待。安全性检查算法如下：
1. 设置工作量 $W o r k [m]$ ，表示系统中剩余的可用资源数目。在安全性检查开始时，置Work=Available；
2. 初始时安全序列为空；
3. 遍历Need矩阵行，找出一行k，该行对应的Pk不在安全序列中，且 $Need[k]\le Work$ ，将对应Pk插入安全序列，若找不到则跳过下一步；
4. 更新 $W o r k = W o r k + A l l o c a t i o n [k]$ ，表征Pk获取资源并运行结束后，将资源释放的过程。返回上步，继续寻找下一个可以分配资源的进程；
5. 此时，安全序列中若存在所有进程，则系统处于安全状态，否则系统不安全。

算法流程图

在这里插入图片描述

结果分析

设置n=5；m=3
T0时刻资源分配表
Available: [3 3 2]
P Allocation Need
0 [0 1 0] [7 4 3]
1 [2 0 0] [1 2 2]
2 [3 0 2] [6 0 0]
3 [2 1 1] [0 1 1]
4 [0 0 2] [4 3 1]

（1）P1请求资源，Request1 = [1, 0, 2]
?VALID CHECK PASSED!
?RESOURCE CHECK PASSED!
通过合法性和资源检查，假定为P1分配资源，然后进行安全性检查：
P Work Need Allocation Work+Allocation
1 [2 3 0] [0 2 0] [3 0 2] [5 3 2]
3 [5 3 2] [0 1 1] [2 1 1] [7 4 3]
0 [7 4 3] [7 4 3] [0 1 0] [7 5 3]
2 [7 5 3] [6 0 0] [3 0 2] [10 5 5]
4 [10 5 5] [4 3 1] [0 0 2] [10 5 7]
?SAFE CHECK PASSED!
Secured Sequence is [1, 3, 0, 2, 4].
通过安全性检查，为P1分配资源，输出当前资源分配信息：
Available: [2 3 0]
P Allocation Need
0 [0 1 0] [7 4 3]
1 [3 0 2] [0 2 0]
2 [3 0 2] [6 0 0]
3 [2 1 1] [0 1 1]
4 [0 0 2] [4 3 1]

（2）T1时刻，P4继续请求资源：
Request4 = [3, 3, 0]
?VALID CHECK PASSED!
??REQUEST EXCEEDS AVAILABLE!
Request4<=Need[4]，但Request4>Available，资源检查失败，P4等待分配资源

（3）T2时刻，P0请求资源：
Request0 = [0, 2, 0]
?VALID CHECK PASSED!
?RESOURCE CHECK PASSED!
??SAFE CHECK FAILED!
通过合法性和资源检验，假设为P0分配资源，此时Available不满足银行家算法，安全性检验失败，若为P0分配资源会导致死锁，故返回原始状态。

（4）T3时刻，P3请求资源：
Request3 = [0, 2, 1]
??Exception: ERROR!P3 REQUEST EXCEEDS ITS NEED!
报错，因为请求资源大于了需求量！

在这里插入图片描述

附录：代码

# @Sylvan Ding 2022.05.31


import numpy as np


def err(P):
    raise Exception("ERROR!P{} REQUEST EXCEEDS ITS NEED!".format(P))


def valid_check(P, Request, Need):
    if np.sum(Request > Need[P, :]):
        err(P)
    print("\033[0;32mVALID CHECK PASSED!\033[0m")


def resource_check(Request, Available):
    if np.sum(Request > Available):
        print("\033[0;31mREQUEST EXCEEDS AVAILABLE!\033[0m")
        return False
    else:
        print("\033[0;32mRESOURCE CHECK PASSED!\033[0m")
        return True


def safe_check(Work, Need, Allocation, n):
    Q = []
    while True:
        i = 0
        while i < n:
            if i not in Q and not np.sum(Need[i, :] > Work):
                Q.append(i)
                temp = Work.copy()
                Work = Work + Allocation[i, :]
                print_safe_check(i, temp, Need, Allocation, Work)
                break
            i = i + 1
        if i == n:
            break
    if len(Q) < n:
        print("\033[0;31mSAFE CHECK FAILED!\033[0m")
        return False
    else:
        print("\033[0;32mSAFE CHECK PASSED!\nSecured Sequence is {}.\033[0m".format(Q))
        return True


def try_allocate(Available, Allocation, Need, Request, P):
    Available = Available - Request
    Allocation[P, :] = Allocation[P, :] + Request
    Need[P, :] = Need[P, :] - Request
    return Available, Need, Allocation


def print_safe_check(k, Work, Need, Allocation, Work_Allocation):
    print("{}\t {}\t {}\t {}\t {}".format(k,
                                          Work,
                                          Need[k, :],
                                          Allocation[k, :],
                                          Work_Allocation))


def print_resource(Available, Need, Allocation, n):
    print("Current resource information: ")
    print("Available: {}".format(Available))
    print("P\t Allocation\t Need")
    for i in range(n):
        print("{}\t {}\t {}".format(i, Allocation[i, :], Need[i, :]))


def print_request_info(P, Request):
    print("\033[0;33mP{} requests {}.\033[0m".format(P, Request))


def Banker(n, Available, Max, Allocation, P, Request):
    """
    :param n: int
    :param Available: array[n][m]
    :param Max: array[n][m]
    :param Allocation: array[n][m]
    :param P: index of process to request
    :param Request: array[m]
    :return: Available, Need, Allocation
    """
    print_request_info(P, Request)
    Available = np.asarray(Available)
    Max = np.asarray(Max)
    Allocation = np.asarray(Allocation)
    Request = np.asarray(Request)
    Need = Max - Allocation
    print_resource(Available, Need, Allocation, n)
    valid_check(P, Request, Need)
    if (resource_check(Request, Available) and
            safe_check(*try_allocate(Available.copy(),
                                     Allocation.copy(),
                                     Need.copy(),
                                     Request, P), n)):
        Available, Need, Allocation = try_allocate(Available.copy(),
                                                   Allocation.copy(),
                                                   Need.copy(),
                                                   Request, P)
        print_resource(Available, Need, Allocation, n)
    return Available, Need, Allocation


def BankerAlgorithm():
    n = 5
    # m = 3
    Available = [3, 3, 2]
    Max = [[7, 5, 3],
           [3, 2, 2],
           [9, 0, 2],
           [2, 2, 2],
           [4, 3, 3]]
    Allocation = [[0, 1, 0],
                  [2, 0, 0],
                  [3, 0, 2],
                  [2, 1, 1],
                  [0, 0, 2]]

    P1 = 1
    Request1 = [1, 0, 2]
    Available, Need, Allocation = Banker(n, Available, Max, Allocation, P1, Request1)

    P4 = 4
    Request4 = [3, 3, 0]
    Available, Need, Allocation = Banker(n, Available, Max, Allocation, P4, Request4)

    P0 = 0
    Request0 = [0, 2, 0]
    Available, Need, Allocation = Banker(n, Available, Max, Allocation, P0, Request0)

    P3 = 3
    Request3 = [0, 2, 1]
    Banker(n, Available, Max, Allocation, P3, Request3)


if __name__ == '__main__':
    BankerAlgorithm()