避免死锁 —— 银行家算法

综述以下概念引用与百度百科银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。做作业时遇到银行家算法的题，同时本着想要加深一下对于避免死锁和银行家算法的理解，所以选择用程序实现一下该算法。本来想使用C++进行编写，毕

筱翼深凉

4054人浏览 · 2022-04-17 21:50:37

筱翼深凉 · 2022-04-17 21:50:37 发布

综述

以下概念引用与百度百科

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

做作业时遇到银行家算法的题，同时本着想要加深一下对于避免死锁和银行家算法的理解，所以选择用程序实现一下该算法。本来想使用C++进行编写，毕竟老ACM选手了，但是学完Python之后没怎么用过，所以就用Python实现了。

算法

操作时需要使用到矩阵，用Python本身带的列表创建矩阵有点麻烦，所以使用numpy包所带的矩阵进行创建。
Pycharm没有带有numpy包，使用需要到File > Setting > Project:Study > Python Interpreter中添加numpy包。
算法中所需要的数据结构

可利用资源向量 $A v a i l a b l e$
是个含有 $m$ 个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果 $A v a i l a b l e [j] = K$ ，则表示系统中现有Rj类资源K个。
最大需求矩阵 $M a x$
这是一个 $n \times m$ 的矩阵，它定义了系统中 $n$ 个进程中的每一个进程对m类资源的最大需求。如果 $M a x [i, j] = K$ ，则表示进程i需要Rj类资源的最大数目为 $K$ 。
分配矩阵 $A l l o c a t i o n$
这也是一个 $n \times m$ 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 $A l l o c a t i o n [i, j] = K$ ，则表示进程i当前已分得 $R_j$ 类资源的数目为K。
需求矩阵 $N e e d$ 。
这也是一个 $n \times m$ 的矩阵，用以表示每一个进程尚需的各类资源数。如果 $N e e d [i, j] = K$ ，则表示进程i还需要 $R_j$ 类资源 $K$ 个，方能完成其任务。
$N e e d [i, j] = M a x [i, j] - A l l o c a t i o n [i, j]$

安全检查

设置两个工作向量Work=AVAILABLE;FINISH
从进程集合中找到一个满足下述条件的进程，
FINISH==false;
NEED<=Work;
如找到，执行（3)；否则，执行（4)
设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work=Work+ALLOCATION;
Finish=true;
GOTO 2
如所有的进程 $F i n i s h = t r u e$ ，则表示安全；否则系统不安全。

代码

def check():
    work = Available.copy()
    finish = [False for it in range(n)]

    ans = "安全序列为："
    for num in range(n):
        for it in range(n):
            if not finish[it]:
                cnt = 0
                for jt in range(m):
                    if Need[it][jt] <= work[jt]:
                        cnt = cnt + 1

                if cnt == m:
                    ans = ans + str(it)
                    finish[it] = True
                    for jt in range(m):
                        work[jt] += Allocation[it][jt]

    if False in finish:
        return "系统处于不安全状态"
    else:
        return ans

银行家算法

设进程 $c u s n e e d$ 提出请求 $R E Q U E S T [i]$ ，则银行家算法按如下规则进行判断。

如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。
如果REQUEST [cusneed] [i]<= AVAILABLE[i]，则转(3)；否则，等待。
系统试探分配资源，修改相关数据：
AVAILABLE[i]-=REQUEST[cusneed][i];
ALLOCATION[cusneed][i]+=REQUEST[cusneed][i]
NEED[cusneed][i]-=REQUEST[cusneed][i];
系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

代码

def request():
    t = int(input("请输入哪个进程请求资源："))
    Request = input("请输入请求的资源数，用字符串输入：").split(' ')
    Request = [int(it) for it in Request]

    for it in range(m):
        if Request[it] > Need[t][it]:
            return "需要资源数超过它所需求的最大值"

    for it in range(m):
        if Request[it] > Available[it]:
            return "尚无足够资源"

    for it in range(m):
        Available[it] -= Request[it]
        Allocation[t][it] += Request[it]
        Need[t][it] -= Request[it]

    if check() == "系统处于不安全状态":
        Available[it] += Request[it]
        Allocation[t][it] -= Request[it]
        Need[t][it] += Request[it]
        return "分配后系统处于不安全状态"
    else:
        return "已分配"

总代码

# 编写人: 筱翼深凉
# 创建时间: 2022/4/16 17:48
# 编写人: 筱翼深凉
# 创建时间: 2022/4/16 16:28

import numpy as np


def check():
    work = Available.copy()
    finish = [False for it in range(n)]

    ans = "安全序列为："
    for num in range(n):
        for it in range(n):
            if not finish[it]:
                cnt = 0
                for jt in range(m):
                    if Need[it][jt] <= work[jt]:
                        cnt = cnt + 1

                if cnt == m:
                    ans = ans + str(it)
                    finish[it] = True
                    for jt in range(m):
                        work[jt] += Allocation[it][jt]

    if False in finish:
        return "系统处于不安全状态"
    else:
        return ans


def request():
    t = int(input("请输入哪个进程请求资源："))
    Request = input("请输入请求的资源数，用字符串输入：").split(' ')
    Request = [int(it) for it in Request]

    for it in range(m):
        if Request[it] > Need[t][it]:
            return "需要资源数超过它所需求的最大值"

    for it in range(m):
        if Request[it] > Available[it]:
            return "尚无足够资源"

    for it in range(m):
        Available[it] -= Request[it]
        Allocation[t][it] += Request[it]
        Need[t][it] -= Request[it]

    if check() == "系统处于不安全状态":
        Available[it] += Request[it]
        Allocation[t][it] -= Request[it]
        Need[t][it] += Request[it]
        return "分配后系统处于不安全状态"
    else:
        return "已分配"


n = int(input("请输入进程数："))  # 进程个数
m = int(input("请输入临界资源数："))  # 临界资源数

# Max最大资源需求数，Need需要的资源数，Allocation已分配的资源数，Available空闲的资源数
Max, Allocation, Need = np.zeros([n, m], int), np.zeros([n, m], int), np.zeros([n, m], int)
Max.tolist(), Need.tolist(), Allocation.tolist()

for i in range(n):
    data1 = input("请输入第" + str(i) + "个进程最大资源需求数，用字符串输入：").split(' ')
    data2 = input("请输入第" + str(i) + "个进程已分配的资源数，用字符串输入：").split(' ')
    for j in range(m):
        Max[i][j] = int(data1[j])
        Allocation[i][j] = int(data2[j])
        Need[i][j] = int(data1[j]) - int(data2[j])

Available = input("请输入可利用资源数，用字符串输入：").split(' ')
Available = [int(x) for x in Available]

while True:
    option = input("请输入操作（Q 退出，C 检查是否安全，R 请求资源）")
    if option == 'Q':
        break
    elif option == 'C':
        print(check())
    elif option == 'R':
        print(request())
    else:
        print("输入错误")