银行家算法原理及代码实现

银行家算法原理

简介

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

数据结构

可利用资源向量Available:这是一个含有m个元素的数组，每一个元素代表每一类资源可利用的资源数目。如Available[j]=k表示j类资源还有k个可利用。
最大需求矩阵Max：这是一个n*m的矩阵，它定义了n个进程对m个元素的最大需求。如Max[i][j]=k,表示系统第i个进程对第j个元素的最大需求为k。
分配矩阵Allocation:这是一个n*m的矩阵，它定义了系统中每一个进程当前获得的资源数。如Allocation[i][j]=k，表示系统第i个进程已经分配了j资源k个。
需求矩阵Need:这是一个n*m的矩阵，它定义了系统中每一个进程尚需的资源数。如Need[i][j]=k,表示系统第i个进程尚需资源j k个。
Need[i][j]=Max[i][j]-Allocation[i][j]

银行家算法

银行家算法基本思想是，如果系统中一个进程发出一个资源请求，在请求合理的情况下，先把资源预分配给进程。随后检查预分配后系统的状态是否为安全状态（即没有死锁），若不安全则撤回预分配的资源。其实现原理如下：
先定义一个Request（i）向量表示系统第i个进程请求的资源数。如Request（i）[j]=k，表示系统第i个向量请求j资源k个。当第i个进程发出请求后按如下步骤检查：
1.如果Request（i）[j]<=Need[i][j]便转向步骤2，否则认为出错。
2.如果Request（i）[j]<=Available[i][j]便转向步骤3，否则没有足够资源需等待。
3.请求合理，此时预分配：
Available[i][j=Available[i][j]-Request（i）[j]
Allocation[i][j]=Allocation[i][j]+Request（i）[j]
Need[i][j]=Need[i][j]-Request（i）[j]
4.系统执行安全性算法，检查此次资源分配是否安全。

安全性算法

1.设置两个向量：工作向量Work，具有m个元素，表示系统可提供给进程继续运行所需的各类资源数目，执行算法前Work=Available。Finish向量，含有m个元素，它表示系统是否有足够资源分配给进程使之运行完成。开始时Finish[i]=false,当有足够资源时Finish[i]=ture。
2.从进程集合中找到一个能满足下列条件的进程：
Finish[i]=false
Need[i][j]<=Work[j]
若找到执行步骤3，否则执行步骤4。
3.当进程获得资源后，可顺利运行并完成释放资源，故执行：
Work[j]=Work[j]+Allocation[i][j]
Finish[i]=ture
go to step 2
4.如果所有进程的Finish[i]=ture都满足，则系统处于安全状态，否则处于不安全状态。

代码实现

因为没学过python，所以基本边学边写，然后发现二维数组赋值时总出问题。对二位数组的[i][j]元素赋值时二维数组中所有一维数组的[j]元素都会被赋值。后来发现是定义时候出了问题。一开始我使用 A=[[0]*n]*m 定义一个n行m列所有元素都为0的数组，这样会导致所有一维数组都是一个[0]*n的映射，所以改变一个就都会改变。
话不多说上代码：

def request_():
    request = Available.copy()
    x = int(input("请输入请求的进程："))
    x = x - 1
    print("请输入请求的资源数：")
    for j in range(m):
        request[j] = int(input())
        if (request[j] <= Need[x][j] and request[j] <= Available[j]):
            Available[j] = Available[j] - request[j]
            Allocation[x][j] = Allocation[x][j] + request[j]
            Need[x][j] = Need[x][j] - request[j]
        else:
            print("请求不合理")

def security():
    Work = Available.copy()
    Finish = [0]*n##开始全为false
    seq=[]
    for k in range(n):
        for i in range(n):
            flag = 1
            for j in range(m):
                if Need[i][j] > Work[j]:
                    flag = 0
                    break
            if flag == 1 and Finish[i] == 0:
                for j in range(m):
                    Work[j] = Work[j] + Allocation[i][j]
                Finish[i] = 1
                seq.append(i)
    for i in range(n):
        if Finish[i]!=1:
            print("不安全")
            return False
    print("存在安全序列：")
    for i in range(n):
        print(seq[i])
    return True

if __name__ == '__main__':

    ##初始化
    n = int(input("请输入进程数："))
    m = int(input("请输入资源数："))
    Available = [0] * m
    Max = [[0]*m for _ in range(n)]
    Allocation = [[0]*m for _ in range(n)]
    Need = [[0]*m for _ in range(n)]
    for i in range(n):
        print("请输入第{:x}个程序的各个值：".format(i + 1))
        print("Max向量：")
        for j in range(m):
            Max[i][j] = int(input())
        print("Allocation向量：")
        for j in range(m):
            Allocation[i][j] = int(input())
    print("请输入Available向量的值：")
    for i in range(m):
        Available[i] = int(input())
    for i in range(n):
        for j in range(m):
            Need[i][j] = Max[i][j] - Allocation[i][j]
    ##初始化结束
    request_()
    security()

"""
    #测试样例
    n=5
    m=3
    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],]
    Need = [[7,4,3],
           [1,2,2],
           [6,0,0],
           [0,1,1],
           [4,3,1],]
    Available=[3,3,2]
    security()
"""

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始