Linux 死鎖概念與銀行家演算法python 實現
摘要：
一 . 死鎖的概念
接上篇 http://shaobaobaoer.cn/archives/680/linux-process-manager-note
在之前的哲學家吃飯的問題中，當每個哲學家都想進餐的時候，他們都會佔用左手邊的筷子。當他們想要拿起右手邊的筷子的時候，因為沒有資源...
一 . 死鎖的概念
接上篇 http://shaobaobaoer.cn/archives/680/linux-process-manager-note
在之前的哲學家吃飯的問題中，當每個哲學家都想進餐的時候，他們都會佔用左手邊的筷子。當他們想要拿起右手邊的筷子的時候，因為沒有資源了。所以程式會進入無線等待的狀態，這就是死鎖。
我們可以來想想一個更加簡單的例子。比如說有兩個訊號量集，一個是掃描機，一個是印表機。P1程式佔用印表機，P2程式佔用掃描機。當P1程式在執行的時候想要獲取掃描機的訊號量，同時P2程式想要在執行的時候獲取印表機的訊號量的時候。就會發生死鎖。
概括而言。我們可以發現死鎖的會有如下共性：
- 參與死鎖的程序至少有兩個
- 每個參與死鎖的程序都要等待資源
- 參與死鎖的程序中至少有兩個程序佔用資源
可見，死鎖之所以產生，是因為每個程序都要競爭資源。由於 系統資源不足，並且推程序序不當 ，因此產生了死鎖
二 . 死鎖例項演示
在之前的消費者和生產者問題中，如果改變了 生產者的 訊號量處理方法，則會產生死鎖。具體例項如下所示，程式碼參考 producer_and_consumer-dead-lock.c
直接執行程式，可以發現程式是直接卡死的。這裡的解決辦法就是Provider 下方的 usleep(1000) 。讓消費者先行一步。即可避免死鎖。
三 . 銀行家演算法
鄙人C語言程式設計能力有限，不知道如何將銀行家演算法的問題和具體作業系統中的實際死鎖避免問題聯絡起來。
只給出一個python版本的矩陣操作來模擬銀行家演算法。
翻了翻谷歌，看到一篇前輩寫的銀行家演算法c實現，也同樣是模擬而不是和實際問題相互結合具體可以看看： ofollow,noindex" target="_blank">銀行家演算法（C語言實現）
銀行家演算法是DJ提出的，最具代表性的避免死鎖演算法。假設系統中有 n個程序 P1-Pn 和 m類資源 R1-Rm，那麼建立以下形式的資料結構：
銀行家演算法的資料結構
- 可用資源向量 Available 長度為 m 。代表所有資源 A[i] 表示第i+1類資源現有的資源數量。
- 最大需求矩陣 Max 。n * m 的矩陣。定義每個程序對 m 類資源的最大需求數。 比如 M[i][j] 表示第 i 個程序最多需要的 m 類資源的數目。
- 分配矩陣 Allocation 。 n * m 的矩陣。定義每個程序 已經分配 的資源數目。
- 需求矩陣 Need 。 n * m 的矩陣。定義每個程序 還需分配 的資源數目。
- 請求向量 $request_i$ 。長度未 m 的向量。代表單次某程序請求的資源量
對此，有關係如下:
銀行家演算法的演算法描述
- 發出請求向量 $request_i$
- 判斷 $request_i$ 是否小於等於 $need_i$ 否則報錯（需要的東西太多了！）
- 判斷 $request_i$ 是否小於等於 $available_i$ 否則等待 （資源不夠用）
- 先對所有的資源進行預分配，修改為如下的值：
- $Allocation_i = Allocation_i + Request_i$
- $Available = Available -Request_i$
- $Need_i = Need_i - Request_i$
- 之後對修改的向量進行安全性演算法。安全則修改，不安全則回退之前的狀態
安全性演算法
- 建立 Work[m] 和 Finish[n]。初始化如下
- $Work = Available; Finish = [False] * n$
- 查詢 i 滿足如下條件
- $Finish[i] = false ; Need_i <= Work$
- 滿足則執行 $Work = Work + Allocation_i ; Finish[n] = True$
- 注意這裡是查詢，而不是順序執行。
- 如果Finish都是True。則允許修改。
銀行家演算法 py 實現
定義資料結構
def __init__(self, n=4, m=3):
self.n = n# 程序數量
self.m = m# 資源有多少類
self.Available = []# 可用資源向量
self.Max = {}# 最大需求矩陣
for i in range(0, self.n):
self.Max["P{}".format(i)] = []
self.Allocation = {}# 分配矩陣
for i in range(0, self.n):
self.Allocation["P{}".format(i)] = []
self.Need = {}# 需求矩陣
for i in range(0, self.n):
self.Need["P{}".format(i)] = []
self.Request = {}
for i in range(0, self.n):
self.Request["P{}".format(i)] = []
請求部分
def sendRequest(self, Px, vector):
'''
:param Px: 字串...P0-P4
:param vector: 請求向量，為一個列表
:return:
'''
self.checkRequestInputValid()
self.Request[Px] = vector
print(self.Request)
for i in range(0, self.m):
if self.Request[Px][i] > self.Need[Px][i]:
raise CommonError("{}申請的資源數目Available[{}]不應該超過它的需求數目".format(Px, i))
if self.Request[Px][i] > self.Available[i]:
raise CommonError("{}需要等待，因為目前可用資源 Available[{}] 不夠".format(Px, i))
tmp_Available = self.Available
tmp_Allocation = self.Allocation
tmp_Need = self.Need
for i in range(0, self.m):
tmp_Available[i] = tmp_Available[i] - self.Request[Px][i]
tmp_Allocation[Px][i] = tmp_Allocation[Px][i] + self.Request[Px][i]
tmp_Need[Px][i] = tmp_Need[Px][i] - self.Request[Px][i]
if self.checkTmpMatrixSafe(tmp_Available, tmp_Allocation, tmp_Need) is True:
print("[+] Check safe ; Format changed")
self.Allocation = tmp_Allocation
self.Available = tmp_Available
self.Need = tmp_Need
安全性校驗
# 這裡的查詢不是很好實現。我的做法是找到一個可用的之後回退，再找一次前面的，方法比較low。可能思路有些不太對。不知道作業系統裡是如何實現的
def checkTmpMatrixSafe(self, tmp_Available, tmp_Allocation, tmp_Need):
Work = tmp_Available
Finish = [False] * self.n
# finding valid i
def helperChecker(tmp_Need_Px, Work, m):
tag = True
for i in range(0, m):
if tmp_Need_Px[i] > Work[i]:
tag = False
return tag
for i in range(0, self.n):
if Finish[i] is True:
continue
if Finish[i] is False and helperChecker(tmp_Need["P{}".format(i)], Work, self.m):
print("[*] Finding P{} safe".format(i))
for j in range(0, self.m):
Work[j] = Work[j] + tmp_Allocation["P{}".format(i)][j]
Finish[i] = True
print(Work)
# ... #
「將上述操作重複一邊，範圍是 (0,i) 感覺這裡有可以優化的地方」
# ... #
if Finish == [True] * self.n:
# tmp_Available = __tmp_Available
return True
else:
return False
樣例
按照書上的寫了個兩個樣例。執行通過～
self.Available = [1, 1, 2]
self.Max = {
"P0": [3, 2, 2],
"P1": [6, 1, 3],
"P2": [3, 1, 4],
"P3": [4, 2, 2]
}
self.Allocation = {
"P0": [1, 0, 0],
"P1": [5, 1, 1],
"P2": [2, 1, 1],
"P3": [0, 0, 2]
}
self.getNeed()
def example1():
try:
Bancker = BankerAlgorithm()
Bancker.exampleInit1()
Bancker.sendRequest("P1", [1, 0, 1])
except Exception as e:
print(e)
{'P2': [], 'P1': [1, 0, 1], 'P0': [], 'P3': []}
[*] Finding P1 safe
[6, 2, 3]
[*] Finding P0 safe
[1, 0, 0] 0
[7, 2, 3]
[*] Finding P2 safe
[9, 3, 4]
[*] Finding P3 safe
[9, 3, 6]
[+] Check safe ; Format changed