银行家算法

算法目的：预防死锁

数据结构

假设有m个资源，n个进程。

1. 可利用资源数组Available[m]，Availabe[i]为i类资源现可用的数目；
2. 最大需求矩阵Max[n*m]，Max[i,j]为进程i需要j资源的最大数目；
3. 分配矩阵Allocation[n*m]，Allocation[i,j]为进程i当前已分配到j资源的数目；
4. 需求矩阵Need[n*m]，Need[i,j]为进程i还需要多少j资源才能完成。

银行家算法

1. 找到一个所需的资源不大于现有资源的进程；
2. 系统进行试探，把资源分配给该进程，更新Available、Allocation、Need数组；
3. 执行安全性算法。

安全性算法

设置两个数组，work和finish。work = Available，finish[i] = 0。

1. 从进程集合中找到一个能满足以下条件的进程：
   • finish[i] = 0
   • Need[I,*] <= work[*]
2. 找到进程i获得资源后可顺利执行，直至完成，并释放分配给它的资源，执行以下步骤：
   • work[j] = work[j] + Allocation[i,j]
   • finish[i] = 1
   • go to step 1
3. 如果finish全为1则处于安全状态。

代码：

Available = []
Max = []
Allocation = []
Need = []


def find_i(finish, ne, work):
    for i in range(len(finish)):
        flag = 0  # 记录每个进程可被满足资源的数量
        for j in range(len(work)):
            if finish[i] == 0:
                if work[j] < ne[i][j]:
                    continue
                else:
                    flag += 1
        if flag == len(work):  # 如果全都满足则可以运行该进程
            return I
    return -1


def safety(av, al, ne, choice):
    work = av[:]
    finish = [0] * m
    list = []
    while True:
        i = find_i(finish, ne, work)
        if i != -1:
            for j in range(len(work)):
                work[j] = work[j] + al[i][j]
            
            finish[i] = 1
            list.append(i)
        else:
            if len(finish) == len(tuple(finish)) and finish[0] == 1:
                if choice == 0:
                    print('该时刻存在的安全序列:', list)
                    return 1
                else:
                    return list
            else:
                return 0


if __name__ == '__main__':
    f = open('银行家.txt', 'r')
    lines = f.readlines()
    m = len(lines) - 1  # 进程数量
    # m = int(input('输入进程数量:'))
    Max = [[]] * m
    Allocation = [[]] * m
    Need = [[]] * m
    # n = int(input('输入资源数量:'))
    print(lines[0])
    lines[0] = list(map(lambda x: int(x), lines[0].split()))
    n = len(lines[0])  # 资源数量
    Available = lines[0]
    # for i in range(n):
    #     # Available.append(int(input('输入第'+str(i+1)+'个资源的数量:')))
    #     for j in range(m):
    #         Max[j].append(int(input('输入第'+str(j+1)+'个进程对该资源的最大需求:')))
    #         Allocation[j].append(int(input('输入第'+str(j+1)+'个进程已分配到的该资源:')))
    #         Need[j].append(int(input('输入第'+str(j+1)+'个进程还需多少该资源才能完成:')))
    lines = lines[1:]
    for i in range(len(lines)):
        lines[i] = list(map(lambda x: int(x), lines[i].split()))
        Max[i] = lines[i][:n]
        Allocation[i] = lines[i][n:2*n]
        Need[i] = lines[i][2*n:]
    for i in range(n):
        a = 0
        for j in range(m):
            a += Allocation[j][I]
        Available[i] -= a
    print(Available)
    list = []  # 安全序列

    while len(list) < m or not list:
        a = int(input('输入请求资源还是直接输出安全序列？'))
        if a == 0:
            flag = 1
            request = [int(i) for i in input('输入请求资源的进程及资源的数量:').split()]
            i = request[0]
            k = request[1:]  # 该进程对所有资源对需求
            av = Available[:]
            al = Allocation[:]
            ne = Need[:]
            for j in range(n):
                if k[j] <= Need[i][j] and k[j] <= Available[j]:
                    av[j] -= k[j]
                    al[i][j] += k[j]
                    ne[i][j] -= k[j]

                    # print(av)
                else:
                    print('没有足够的资源!')
                    flag = 0
            if safety(av, al, ne, 0) and flag:
                Allocation = al
                Available = av
                Need = ne
                list.append(i)
                print(list)
            else:
                print('不能分配！')
        else:
            list = safety(Available, Allocation, Need, 1)
            print(list)

可以选择自己输入还是读取本地文件。
本地文件内容如下：

10 5 7  # 有三个资源，每个资源可用的数量。
7 5 3 0 1 0 7 4 3  # 每个进程占一行，读文件的时候把注释删掉。
3 2 2 2 0 0 1 2 2  # 具体情况如下图所示。
9 0 2 3 0 2 6 0 0
2 2 2 2 1 1 0 1 1
4 3 3 0 0 2 4 3 1

计算机操作系统（第四版）113页