作業系統中的死鎖檢測演算法

---

引言

死鎖是指在計算機系統中，兩個或多個程序阻塞並等待彼此釋放資源，從而導致僵局的一種情況。

這是作業系統中一個嚴重的問題，因為它可能導致整個系統凍結或崩潰。因此，檢測和解決死鎖對於任何計算機系統的平穩執行至關重要。

死鎖檢測演算法用於識別計算機系統中死鎖的存在。這些演算法檢查系統的程序和資源，以確定是否存在可能導致死鎖的迴圈等待情況。如果檢測到死鎖，該演算法可以採取措施來解決它並防止它在將來再次發生。有幾種流行的死鎖檢測演算法。在這裡，我們將探討死鎖的必要條件、死鎖檢測演算法的目的，以及詳細介紹這些演算法中的每一個以及它們最有效的應用場景。

死鎖檢測演算法的目的

• 死鎖檢測演算法的目的是識別和解決計算機系統中的死鎖。

• 它透過識別死鎖的發生、確定涉及的程序和資源、採取糾正措施來打破死鎖以及恢復正常的系統操作來實現這一點。

• 該演算法透過防止死鎖導致系統凍結或崩潰，在確保系統穩定性和可靠性方面發揮著至關重要的作用。

死鎖檢測演算法

1. 資源分配圖 (RAG) 演算法

• 構建RAG − 第一步是構建一個資源分配圖 (RAG)，該圖顯示系統中資源的分配和請求。每種資源型別都由一個矩形表示，每個程序都由一個圓圈表示。

• 檢查迴圈 − 在RAG中查詢迴圈。如果存在迴圈，則表示系統處於死鎖狀態。

• 識別死鎖程序 − 識別參與迴圈的程序。這些程序處於死鎖狀態，並等待其他程序持有的資源。

• 確定資源型別 − 確定死鎖中涉及的資源型別，以及每個程序持有的和請求的資源。

• 採取糾正措施 − 透過釋放資源、中止程序或搶佔資源來採取糾正措施以打破死鎖。一旦死鎖被打破，系統就可以繼續進行正常操作。

• 重新檢查迴圈 − 採取糾正措施後，重新檢查RAG是否存在迴圈。如果沒有更多迴圈，則系統不再處於死鎖狀態，可以恢復正常操作。

優點

• 易於理解和實現

• 可以處理多種型別的資源

• 有助於識別參與死鎖的程序

缺點

• 對於大型系統來說可能很耗時

• 如果對同一資源有多個請求，則可能出現誤報。

• 假設所有資源都是預先分配的，這在某些系統中可能並非如此。

示例

考慮一個具有兩個程序 P1 和 P2 以及兩個資源 R1 和 R2 的系統。

程序	R1	R2
P1	1	0
P2	0	1

此係統的RAG可以表示如下：------

P1 -> R1

P2 -> R2

R1 -> P2

R2 -> P1

P1 和 P2 之間存在迴圈，表明潛在的死鎖。為了確認是否存在死鎖，我們可以對RAG使用迴圈檢測演算法。該演算法將檢測迴圈並識別P1和P2之間潛在的死鎖。然後，我們可以採取適當的措施來解決死鎖並防止其在將來再次發生。

2. 等待圖 (WFG) 演算法

• 構建WFG − 第一步是構建一個等待圖 (WFG)，該圖顯示程序之間的等待關係。每個程序都由一個圓圈表示，如果前一個程序正在等待後一個程序持有的資源，則在兩個程序之間畫一條箭頭。

• 檢查迴圈 − 在WFG中查詢迴圈。如果存在迴圈，則表示系統處於死鎖狀態。

• 識別死鎖程序 − 識別參與迴圈的程序。這些程序處於死鎖狀態，並等待其他程序持有的資源。

• 確定資源型別 − 確定死鎖中涉及的資源型別，以及每個程序持有的和請求的資源。

• 採取糾正措施 − 透過釋放資源、中止程序或搶佔資源來採取糾正措施以打破死鎖。一旦死鎖被打破，系統就可以繼續進行正常操作。

• 重新檢查迴圈 − 採取糾正措施後，重新檢查WFG是否存在迴圈。如果沒有更多迴圈，則系統不再處於死鎖狀態，可以恢復正常操作。

優點

• 可以處理多種型別的資源

• 適用於具有大量程序的系統

• 提供死鎖的清晰視覺化

缺點

• 對於大型系統來說可能很耗時

• 如果對同一資源有多個請求，則可能出現誤報。

• 假設所有資源都是預先分配的，這在某些系統中可能並非如此。

示例

三個程序 P1、P2 和 P3 以及兩個資源 R1 和 R2。

程序	R1	R2
P1	1	0
P2	0	1
P3	1	1

此係統的等待圖 (WFG) 可以表示如下：

P1 -> P3

P3 -> P2

P2 -> P3

P2 和 P3 之間存在迴圈，表明潛在的死鎖。為了確認是否存在死鎖，我們可以對WFG使用迴圈檢測演算法。該演算法將檢測迴圈並識別P2和P3之間潛在的死鎖。然後，我們可以採取適當的措施來解決死鎖並防止其在將來再次發生。

3. 銀行家演算法

它可以用作死鎖檢測演算法。事實上，它是作業系統中最著名的死鎖檢測演算法之一。

它使用3個數據結構：

• Available −

• 長度為m的向量

• 它指示每種型別的可用資源有多少。

• Allocation −

• 大小為n*m的矩陣

• A[i,j]指示分配給第i個程序的第j種資源型別的數量。

• Request −

• 大小為n*m的矩陣

• 指示每個程序的請求。

• Request[i,j]表示Pi程序請求的第j種資源型別的例項數量。

演算法

• 步驟1 −

• 令Work（向量）長度 = m

• Finish（向量）長度 = n

• 初始化 Work = Available。

• 對於 i = 0, 1, …., n-1，如果 Allocation_i = 0，則 Finish[i] = true；否則，Finish[i] = false。

• 步驟2 −

• 找到一個索引 i，使得：

• Finish[i] == false

• Request_i <= Work

• 如果沒有這樣的i存在，則轉到步驟4。

• 步驟3 −

• Work = Work + Allocation_i

• Finish[i] = true

  轉到步驟2。

• 步驟4 −

• 如果對於某些 i，0 <= i < n，Finish[i] == false，則系統處於死鎖狀態。此外，如果 Finish[i] == false，則程序 Pi 處於死鎖狀態。

• 否則，沒有死鎖。

示例

程序	Allocation (ABC)	Request (ABC)	Available (ABC)
P0	010	000	000
P1	200	202
P3	303	000
P4	211	100
P5	002	002

解決方案

• 步驟1 −

  Work = [0,0,0] &

  Finish = [false, false, false, false, false]。

• 步驟2 −

  選擇 i=0，因為 Finish[0]=false 且 [0,0,0] <= [0,0,0]。

• 步驟3 −

  Work = [0,0,0] + [0,1,0] => [0,1,0] &

  Finish = [true, false, false, false, false]。

• 步驟4 −

  選擇 i=2，因為 Finish[2] = false 且 [0,0,0] <= [0,1,0]。

• 步驟5 −

  Work = [0,1,0] + [3,0,3] => [3,1,3] &

  Finish = [true, false, false, false, false]。

• 步驟6 −

  選擇 i=1，因為 Finish[1] = false 且 [2,0,2] <= [3,1,3]。

• 步驟7 −

  Work = [3,1,3] + [2,0,0] => [5,1,3] &

  Finish = [true, true, true, false, false]。

• 步驟8 −

  選擇 i=3，因為 Finish[3] = false 且 [1,0,0] <= [5,1,3]。

• 步驟9 −

  Work = [5,1,3] + [2,1,1] => [7,2,4] &

  Finish = [true, true, true, true, false]。

• 步驟10 −

  選擇 i=4，因為 Finish[4] = false 且 [0,0,2] <= [7,2,4]。

• 步驟11 −

  Work = [7,2,4] + [0,0,2] => [7,2,6] &

  Finish = [true, true, true, true, true]。

現在我們可以看到 Finish（一個向量）包含所有真值，這意味著在這個例子中沒有死鎖。

優點

• 透過確保程序在執行前獲取所有必需的資源來防止死鎖

• 可以處理多種資源型別

• 提供安全有效的資源分配方法

缺點

• 對於具有大量程序和資源的系統可能不可行

• 假設資源需求是預先知道的，這在某些系統中可能並非如此

• 如果資源被保留但未使用，則可能導致資源利用率低。

結論

死鎖檢測演算法是維護計算機系統穩定性和可靠性的重要工具。可以使用不同的實現策略。每種演算法都有其自身的優缺點，選擇使用哪種演算法將取決於被檢查系統的特定需求。總的來說，死鎖檢測演算法在確保複雜計算環境中作業系統的可靠性和效能方面發揮著至關重要的作用。