一、实验目的

1、 理解死锁产生的基本原理，以及死锁的必要条件；
2、 掌握死锁避免的基本原理与思路。

二、实验内容

试利用银行家算法对死锁避免算法进行模拟，确保系统在冬天申请资源的同时，永远不会陷入不安全状态。具体要求如下：
（1）程序中进程数量、资源种类数在程序运行时由用户输入；
（2）程序中的资源状态表结构根据输入的进程数量、资源种类数由程序动态生成；
（3）资源状态表中的数量既可以通过随机函数自动产生，也可以由用户手工输入；
（4）程序首先判断系统是否安全，然后在系统安全的前提下，由用户手动完成资源申请，其方法是：先输入或选择进程，然后输入该进程的资源申请要求；
（5）针对用户输入的资源申请，系统应视情况不同给出如下四种执行结果：
1）显示“资源申请不合理”；
2）显示“资源申请超过最大可用资源数，资源不够分配”；
3）显示“找不到安全序列，进程资源申请不予满足”；
4）先显示所找到的安全序列，进而告知用户资源已被分配，并同步修改资源状态表中相关数据。

三、实验要求

1、 写出程序，并调试程序，要给出测试数据和实验结果。
2、 整理上机步骤，总结经验和体会。
3、 完成实验报告和上交程序。

四、实验代码

结果展示

全部代码

import numpy as np

def get_data(types_of_resources, process_nums):
    print(types_of_resources, process_nums)
    Max = np.zeros((process_nums,types_of_resources))
    Allocation = np.zeros((process_nums,types_of_resources))
    Need = np.zeros((process_nums,types_of_resources))
    Available = np.zeros(types_of_resources)

    print("请输入当前可用的各资源数目： ",end=" ")
    nums_cnt = input().split()
    nums_cnt = [int(i) for i in nums_cnt]
    for i in range(types_of_resources):
        Available[i]=nums_cnt[i]

    for i in range(process_nums):
        print(f"请输入P{i}的需要的最大资源数目：",end=" ")
        nums_cnt = input().split()
        nums_cnt = [int(i) for i in nums_cnt]
        for j in range(types_of_resources):
            Max[i][j] = nums_cnt[j]

    for i in range(process_nums):
        print(f"请输入P{i}已经分配的资源数目：", end=" ")
        nums_cnt = input().split()
        nums_cnt = [int(i) for i in nums_cnt]
        for j in range(types_of_resources):
            Allocation[i][j] = nums_cnt[j]

    # 求取Need矩阵
    for i in range(process_nums):
        for j in range(types_of_resources):
            Need[i][j] = Max[i][j] - Allocation[i][j]

    draw_resource_map(Max, Allocation, Need, Available,types_of_resources, process_nums)

    return Max, Allocation, Need, Available

def draw_resource_map(Max,Allocation,Need,Available,types_of_resources, process_nums):
    kg_num = int(types_of_resources/2)+1
    print("|---"+'-'*kg_num+"进程"+"--"+"最大需求"+"--"*kg_num+"已占有资源数目"+"--"*kg_num+"最多还需要分配"+"--"*kg_num+"各资源剩余数目"+"--|")
    for i in range(process_nums):
        print("| "*kg_num+"P"+str(i)+" "*kg_num+str(list(Max[i]))+" "*kg_num+str(list(Allocation[i]))+" "*kg_num+str(list(Need[i]))+str(list(Available))+"  |")

    return None

def main_banker_algorithm(Max, Allocation, Need, Available,types_of_resources, process_nums):
    process_sequence = input("请输入请求分配的进程的序号（从0开始）：")
    process_sequence = int(process_sequence)
    # 请求各个资源的数目
    Requests = np.zeros(types_of_resources)
    print("请输入请求的各个资源的数目：",end=" ")
    nums_cnt = input().split()
    nums_cnt = [int(i) for i in nums_cnt]
    for j in range(types_of_resources):
        Requests[j] = nums_cnt[j]

    # 判断申请是否超过之前声明的最大需求出
    # 检查此时系统剩余的可用资源是否满足这次请求
    flag,Need_cnt,Allocation_cnt,Available_cnt = is_initial_conditions(Need,Allocation,Available,Requests,process_sequence,types_of_resources)

    if not flag:
        print("main~无法找到安全序列")
    else:
        # 先试着分配，看效果
        analog_distribution(Max,Need_cnt,Allocation_cnt,Available_cnt,types_of_resources, process_nums)

    return None

def is_initial_conditions(Need,Allocation,Available,Requests,process_sequence,types_of_resources):
    Need_cnt = Need
    Available_cnt = Available
    Allocation_cnt = Allocation
    for i in range(types_of_resources):
        # 判断申请是否超过之前声明的最大需求出
        if Requests[i] > Need[process_sequence][i]:
            print("申请超过之前声明的最大需求")
            return False
        else:
            Need_cnt[process_sequence][i]-=Requests[i]

        # 检查此时系统剩余的可用资源是否满足这次请求
        if Requests[i]>Available[i]:
            print("此时系统剩余的可用资源不能满足这次请求")
            return False
        else:
            Available_cnt[i]-=Requests[i]

        Allocation_cnt[process_sequence][i]+=Requests[i]

    return True,Need_cnt,Allocation_cnt,Available_cnt

def analog_distribution(Max,Need_cnt,Allocation_cnt,Available_cnt,types_of_resources, process_nums):
    # 先找出满足现在当前序列的排在第一个进程
    the_first_process = []
    for i in range(process_nums):
        flag = 0
        for j in range(types_of_resources):
            if (Available_cnt[j]>=Need_cnt[i][j]):
                flag+=1
        if(flag==types_of_resources):
            the_first_process.append(i)

    if len(the_first_process)==0:
        print("没有找到安全序列")
    else:
        for rank in the_first_process:
            Need, Allocation, Available = Need_cnt,Allocation_cnt,Available_cnt
            # 记录进程是否执行完毕
            process_over = [0]*process_nums
            other = [i for i in range(process_nums) if i!=rank]
            # 例子，剩下的三种，一共有6种排序方法，这里使用暴力大法（其实这里可以改善，不过没想到好的方法，嘻嘻）
            # 应该是n！个方法
            # 如果强行使用n！的暴力方法的话，我感觉是绕园路了，试下走一步弄一部吧

            # 满足该进程后，彻底回收该进程使用的资源
            for i in range(types_of_resources):
                Available[i]+=Allocation[rank][i]
            # 该进程执行完毕
            process_over[rank] += 1

            # 当前路径下的名称
            road_name=[]
            road_name.append(rank)
            # 根据后面的序列判断是否存在合理的程序
            isRight=True
            # 用递归的方式查找对应的序列
            look_for_reods(Need, Allocation, Available,process_over,len(other),road_name,isRight,types_of_resources, process_nums)
            road_name.pop(-1)
            process_over[rank] -= 1
            for i in range(types_of_resources):
                Available[i] -= Allocation[rank][i]


def look_for_reods(Need, Allocation, Available,process_over,geshu,road_name,isRight,types_of_resources, process_nums):
    if isRight:
        isRight_cnt=isRight
        geshu_cnt = geshu
        # 先找出满足现在当前序列的排在第一个进程
        the_first_process = []
        for i in range(process_nums):
            if process_over[i]==0:
                flag = 0
                for j in range(types_of_resources):
                    if (Available[j] >= Need[i][j]):
                        flag += 1
                if (flag == types_of_resources):
                    the_first_process.append(i)

        if len(the_first_process) == 0 and len(road_name)!=process_nums:
            print(str(list(road_name))+"没有找到安全序列")
            isRight_cnt=False

        for rank in the_first_process:
            Need_cnt, Allocation_cnt, Available_cnt = Need.copy(), Allocation.copy(), Available.copy()

            # 满足该进程后，彻底回收该进程使用的资源
            for i in range(types_of_resources):
                Available_cnt[i] += Allocation[rank][i]
            # 该进程执行完毕
            process_over[rank] += 1
            road_name.append(rank)
            geshu_cnt=geshu-1

            if(geshu_cnt==0):
                print("安全序列为：",end=" ")
                print(road_name)

            if isRight_cnt:
                look_for_reods(Need_cnt, Allocation_cnt, Available_cnt, process_over, geshu_cnt, road_name, isRight_cnt,types_of_resources, process_nums)
                road_name.pop(-1)
                process_over[rank]-=1


def main():
    types_of_resources , process_nums = input("请输入资源种类和进程数目：").split(" ")
    types_of_resources, process_nums = int(types_of_resources) , int(process_nums)
    Max, Allocation, Need, Available = get_data(types_of_resources, process_nums)
    while True:
        main_banker_algorithm(Max, Allocation, Need, Available,types_of_resources, process_nums)

    return None

if __name__ == '__main__':
    main()