技術文章 » 什麼是死鎖，死鎖的原因及解決辦法（含四個必要條件）

什麼是死鎖，死鎖的原因及解決辦法（含四個必要條件）

2020-07-16 10:04:35
在多道程式環境中，多個進程可以競爭有限數量的資源。當一個進程申請資源時，如果這時沒有可用資源，那麼這個進程進入等待狀態。有時，如果所申請的資源被其他等待進程佔有，那麼該等待進程有可能再也無法改變狀態。這種情況稱為死鎖。

或許，死鎖的最好例證是 Kansas 立法機構在 20 世紀初通過的一項法律，其中說到“當兩列列車在十字路口逼近時，它們應完全停下來，並且在一列列車開走之前另一列列車不能再次啟動。”

系統模型

有一個系統擁有有限數量的資源，需要分配到若干競爭進程。這些資源可以分成多種型別，每種型別有一定數量的範例。資源型別有很多，如 CPU 週期、檔案、I/O 裝置（印表機和 DVD 驅動器）等。如果一個系統有兩個 CPU，那麼資源型別 CPU 就有兩個範例。類似地，資源型別印表機可能有 5 個範例。

如果一個進程申請某個資源型別的一個範例，那麼分配這種型別的任何範例都可滿足申請。否則，這些範例就不相同，並且資源分類沒有定義正確。例如，一個系統有兩台印表機。如果沒有人關心哪台印表機列印哪些輸出，那麼這兩台印表機可定義為屬於同樣的資源型別。然而，如果一台印表機在九樓，而另一台在底樓，那麼九樓的使用者就不會認為這兩台印表機是相同的，這樣每個印表機就可能需要定義成屬於單獨的型別。

各種同步工具如互斥鎖和號誌，也應作為系統資源，它們是常見的死鎖源。然而，一個鎖通常與保護某個特定的資料結構相關聯，即一個鎖可用於保護佇列的存取，另一個鎖保護存取連結列表的存取，等等。由於這個原因，每個鎖通常有自己的資源型別，並且這種定義不是一個問題。

進程在使用資源前應申請資源，在使用資源之後應釋放資源。一個進程可能要申請許多資源，以便完成指定任務。顯然，申請的資源數量不能超過系統所有資源的總和。換言之，如果系統只有兩台印表機，那麼進程就不能申請三台印表機。

在正常操作模式下，進程只能按如下順序使用資源：
  • 申請：進程請求資源。如果申請不能立即被允許（例如，申請的資源正在被其他進程使用)，那麼申請進程應等待，直到它能獲得該資源為止。
  • 使用：進程對資源進行操作（例如，如果資源是印表機，那麼進程就可以在印表機上列印了）。
  • 釋放：進程釋放資源。

當進程或執行緒每次使用核心管理的資源時，作業系統會檢查以確保該進程或執行緒已經請求並獲得了資源。系統表記錄每個資源是否是空閒的或分配的。對於每個已分配的資源，該錶還記錄了它被分配的進程。如果進程申請的資源正在為其他進程所使用，那麼該進程會新增到該資源的等待佇列上。

當一組進程內的每個進程都在等待一個事件，而這一事件只能由這一組進程的另一個進程引起，那麼這組進程就處於死鎖狀態。這裡所關心的主要事件是資源的獲取和釋放。資源可能是物理資源（例如，印表機、磁帶驅動器、記憶體空間和 CPU 週期）或邏輯資源（例如，號誌、互斥鎖和檔案）。然而，其他型別的事件也會導致死鎖（例如 IPC 功能）。

為說明死鎖狀態，假設一個系統具有三個 CD 燒錄機。假定有三個進程，每個進程都佔用了一台 CD 燒錄機。如果每個進程現在需要另一台燒錄機，那麼這三個進程會處於死鎖狀態。每個進程都在等待事件“CD燒錄機被釋放”，這僅可能由一個等待進程來完成。這個例子說明了涉及同一種資源型別的死鎖。

死鎖也可能涉及不同資源型別。例如，假設一個系統有一台印表機和一台 DVD 驅動器。假如進程 Pi 佔有 DVD 驅動器而進程 P2 占有印表機。如果 Pi 申請印表機而 Pj 申請 DVD 驅動器，那麼就會出現死鎖。

多執行緒應用程式的開發人員應始終警惕可能的死鎖。多執行緒應用程式容易死鎖，因為多執行緒可能競爭共用資源。

死鎖特徵

發生死鎖時，進程永遠不能完成，系統資源被阻礙使用，以致於阻止了其他作業開始執行。在討論處理死鎖問題的各種方法之前，我們首先深入討論一下死鎖特點。

必要條件

如果在一個系統中以下四個條件同時成立，那麼就能引起死鎖：
  1. 互斥：至少有一個資源必須處於非共用模式，即一次只有一個進程可使用。如果另一進程申請該資源，那麼申請進程應等到該資源釋放為止。
  2. 佔有並等待：—個進程應佔有至少一個資源，並等待另一個資源，而該資源為其他進程所佔有。
  3. 非搶占：資源不能被搶占，即資源只能被進程在完成任務後自願釋放。
  4. 迴圈等待：有一組等待進程 {P0，P1，…，Pn}，P0 等待的資源為 P1 佔有，P1 等待的資源為 P2 佔有，……，Pn-1 等待的資源為 Pn 佔有，Pn 等待的資源為 P0 佔有。
我們強調所有四個條件必須同時成立才會出現死鎖。迴圈等待條件意味著佔有並等待條件，這樣四個條件並不完全獨立。

資源分配圖

通過稱為系統資源分配圖的有向圖可以更精確地描述死鎖。該圖包括一個節點集合 V 和一個邊集合 E。節點集合 V 可分成兩種型別：P={P1，p2,…，Pn}（系統所有活動進程的集合）和 R={R1，R2，…，Rm}（系統所有資源型別的集合）。

從進程 Pi 到資源型別 Rj 的有向邊記為 Pi->Rj，它表示進程 Pi 已經申請了資源型別 Rj 的一個範例，並且正在等待這個資源。從資源型別 Rj 到進程 Pi 的有向邊記為 Rj->Pi，它表示資源型別 Rj 的一個範例已經分配給了進程 Pi。有向邊 Pi->Rj 稱為申請邊，有向邊 Rj->Pi 稱為分配邊。

在圖形上，用圓表示進程 Pi，用矩形表示資源型別 Rj。由於資源型別 Rj 可能有多個範例，所以矩形內的點的數量表示範例數量。注意申請邊只指向矩形 Rj，而分配邊應指定矩形內的某個圓點。

當進程 Pi 申請資源型別 Rj 的一個範例時，就在資源分配圖中加入一條申請邊。當該申請可以得到滿足時，那麼申請邊就立即轉換成分配邊。當進程不再需要存取資源時，它就釋放資源，因此就刪除了分配邊。

資源分配圖
圖 1 資源分配圖