作業系統中的銀行家演算法

---

在計算機系統中，銀行家演算法用於避免死鎖，以便可以安全地將資源分配給每個程序。之所以這樣命名，是因為它可以用於銀行系統，以確保銀行永遠不會分配其可用現金，以至於無法滿足所有客戶的要求。

在本文中，我們將詳細討論銀行家演算法。但在那之前，讓我們瞭解一個與其類似的現實世界情況。

銀行家演算法：它是如何工作的？

讓我們假設一家銀行有“n”個賬戶，“M”是銀行的總現金。如果客戶申請貸款，則銀行首先從可用的總現金中減去貸款金額，然後驗證現金差額必須大於總現金“M”才能批准貸款。此過程幫助銀行在沒有任何限制的情況下管理和執行所有銀行業務。

同樣，銀行家演算法在計算機系統的作業系統中也適用。在計算機系統中，當一個新程序進入系統時。然後，該程序必須宣告其可能需要執行的最大數量的每種資源型別的例項。此數字不得超過系統中資源的總數。現在，當一個新程序請求資源時，系統必須計算分配請求的資源是否會使計算機系統處於安全狀態。如果是，則程序將獲得分配的請求資源，否則它必須等待直到其他一些程序釋放請求的資源。

透過遵循此實踐，銀行家演算法避免了死鎖並安全地分配了資源。因此，在作業系統中它也被稱為死鎖檢測演算法或死鎖避免演算法。

銀行家演算法中使用的資料結構

在計算機系統中，如果程序數等於“n”，資源型別數等於“m”。實現銀行家演算法需要以下四種資料結構：

• Available（可用） - 它是一個長度為“m”的向量，指示系統中每種型別的可用資源數量。如果 Available [j] = k，則“k”為系統中可用資源型別 R_j 的例項數。

• Max（最大） - 它是一個 [n × m] 矩陣，定義每個程序的最大資源需求。當 Max [I, j] = k 時，程序 P_i 可以請求資源型別 R_j 的最大 k 個例項。

• Allocation（分配） - 它也是一個 [n × m] 矩陣，定義當前分配給每個程序的每種型別的資源數量。因此，如果 Allocation [i, j] = k，則程序 P_i 當前分配了資源型別 R_j 的“k”個例項。

• Need（需求） - 它是一個 [n × m] 矩陣，表示每個程序剩餘的資源需求。當 Need [i, j] = k 時，程序 P_i 可能需要資源型別 R_j 的“k”個更多例項才能完成分配的任務。

• Finish（完成） - 它是一個長度為“m”的矩陣。它包含一個布林值，即 TRUE 或 FALSE，以指示是否已將程序分配給所需的資源，或者在完成分配的工作後所有資源是否都已釋放。

此外，需要注意的是，

Need [i, j] = Max [i, j] – Allocation [i, j]

銀行家演算法是兩種演算法的組合，即安全演算法和資源請求演算法。這兩種演算法共同控制程序並避免系統死鎖。

安全演算法

安全演算法用於確定系統是否處於安全狀態。它遵循銀行家演算法中的以下安全順序：

步驟 1

• 考慮兩個分別命名為 Work 和 Finish 的向量，長度分別為“m”和“n”。

• 初始化：Work = Available

• Finish [i] = false；對於 i = 0, 1, 2, 3, 4, 5 … n。

步驟 2

• 找到“i”，使得 Finish [i] = false 且 Needi ≤ Work

• 如果不存在這樣的“i”，則轉到步驟 4。

步驟 3

• Work = Work + Allocation

• Finish [i] = true

• 轉到步驟 2。

步驟 4

• 如果 Finish [i] 對所有“i”都為 true，則表示系統處於安全狀態，否則處於不安全狀態。

• 該演算法需要 (m × n2) 次操作才能確定狀態是安全還是不安全。

現在，讓我們討論資源請求演算法。

資源請求演算法

此演算法確定系統在程序請求系統中每種型別的資源時如何執行。

讓我們考慮一個程序 P_i 的請求向量 Requesti。當 Requesti [j] = k 時，程序 P_i 需要資源型別 R_j 的 k 個例項。

當程序 Pi 請求資源時，將遵循以下順序：

步驟 1

如果 Requesti ≤ Need_i，則轉到步驟 2。否則，由於程序已超過其對資源的最大索取，因此給出錯誤。

步驟 2

如果 Requesti ≤ Available，則轉到步驟 3。否則，程序 P_i 必須等待直到資源可用。

步驟 3

如果透過如下修改狀態，將請求的資源分配給程序 Pi：

Available = Available – Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;

如果生成的資源分配狀態安全，則將請求的資源分配給程序 P_i。如果新狀態不安全，則程序 P_i 必須等待 Requesti，並且恢復舊的資源分配狀態。