您现在的位置：程式師世界 >> 編程語言 > >> 更多編程語言 >> Python

銀行家算法之Python實現[操作系統實驗]

編輯：Python

銀行家算法

銀行家算法是著名的死鎖避免算法，其思想是：把操作系統視為銀行家，操作系統管理的資源相當於銀行家管理的資金，進程向操作系統請求分配資源相當於用戶向銀行家貸款。操作系統按照銀行家制定的規則為進程分配資源。進程運行之前先聲明對各種資源的最大需求量，當進程在執行中繼續申請資源時，先測試該進程已占用的資源數與本次申請的資源數之和是否超過該進程聲明的最大需求量。若超過則拒絕分配資源，若未超過則再測試系統現存的資源能否滿足該進程尚須的最大資源量，若能滿足則按當前的申請量分配資源，否則也要推遲分配。

問題描述

設計程序模擬避免死鎖的銀行家算法的工作過程。假設系統中有n個進程： P 1 , P 2 , … , P n P_1,P_2,\dots,P_n P1,P2,…,Pn，有m類可分配資源 R 1 , … , R m R_1,\dots,R_m R1,…,Rm，在某時刻，進程 P i P_i Pi已分配到的j類資源為 A l l o c a t i o n [ i ] [ j ] Allocation[i][j] Allocation[i][j]個，還需要j類資源 n e e d [ i ] [ j ] need[i][j] need[i][j]個，目前系統剩余j類資源 A v a i l a b l e [ j ] Available[j] Available[j]個。

實驗要求

判斷當前狀態是否安全。若安全，給出安全序列；若不安全，給出理由。
對於下一個時刻，某個進程提出資源請求Request(R1,…,Rm)，使用銀行家算法作為判讀是否相應該響應該請求的決策依據。
輸入某時刻的資源分配表和進程請求信息，輸出安全序列分析，給出決策方案。

數據結構描述

系統可用資源向量 A v a i l a b l e [ m ] Available[m] Available[m]
最大需求矩陣 M a x [ n ] [ m ] Max[n][m] Max[n][m]
分配矩陣 A l l o c a t i o n [ n ] [ m ] Allocation[n][m] Allocation[n][m]
需求矩陣 N e e d [ n ] [ m ] Need[n][m] Need[n][m]

其中，n是進程數量，m是資源種類數量。

算法描述

輸入：T0時刻的資源分配表
輸出：Pi發出資源請求後，進行的安全序列分析表和安全序列。若不安全，則給出不安全產生的原因。

進程Pi發出請求 R e q u e s t i Request_i Requesti，首先檢查其合法性，若 R e q u e s t i ≤ N e e d [ i ] Request_i\le Need[i] Requesti≤Need[i]則繼續進行，否則報錯；
若 R e q u e s t i ≤ A v a i l a b l e Request_i\le Available Requesti≤Available，則繼續進行，否則認為當前資源不足，不響應當前請求；
系統試探性把資源分配給進程Pi：
A v a i l a b l e − = R e q u e s t i Available-=Request_i Available−=Requesti
A l l o c a t i o n [ i ] + = R e q u e s t i Allocation[i]+=Request_i Allocation[i]+=Requesti
N e e d [ i ] − = R e q u e s t i Need[i]-=Request_i Need[i]−=Requesti
使用銀行家算法進行安全性檢查，檢查此次資源分配後，系統是否處於安全狀態，若安全才正式將資源分配給進程Pi；否則本次的試探作廢，Pi繼續等待。安全性檢查算法如下：
1. 設置工作量 W o r k [ m ] Work[m] Work[m]，表示系統中剩余的可用資源數目。在安全性檢查開始時，置Work=Available；
2. 初始時安全序列為空；
3. 遍歷Need矩陣行，找出一行k，該行對應的Pk不在安全序列中，且 N e e d [ k ] ≤ W o r k Need[k]\le Work Need[k]≤Work，將對應Pk插入安全序列，若找不到則跳過下一步；
4. 更新 W o r k = W o r k + A l l o c a t i o n [ k ] Work=Work+Allocation[k] Work=Work+Allocation[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()