在多道程序環境中，多個進程可以競争有限數量的資源。當一個進程申請資源時，如果這時沒有可用資源，那麼這個進程進入等待狀态。有時，如果所申請的資源被其他等待進程占有，那麼該等待進程有可能再也無法改變狀态。這種情況稱為死鎖。

死鎖、饑餓、死循環的區别

生活中的死鎖現象

生活中的死鎖

有一個系統擁有有限數量的資源，需要分配到若幹競争進程。這些資源可以分成多種類型，每種類型有一定數量的實例。資源類型有很多，如 CPU 周期、文件、I/O 設備（打印機和 DVD 驅動器）等。如果一個系統有兩個 CPU，那麼資源類型 CPU 就有兩個實例。類似地，資源類型打印機可能有 5 個實例。如果一個進程申請某個資源類型的一個實例，那麼分配這種類型的任何實例都可滿足申請。否則，這些實例就不相同，并且資源分類沒有定義正确。例如，一個系統有兩台打印機。如果沒有人關心哪台打印機打印哪些輸出，那麼這兩台打印機可定義為屬于同樣的資源類型。然而，如果一台打印機在九樓，而另一台在底樓，那麼九樓的用戶就不會認為這兩台打印機是相同的，這樣每個打印機就可能需要定義成屬于單獨的類型。各種同步工具如互斥鎖和信号量，也應作為系統資源，它們是常見的死鎖源。然而，一個鎖通常與保護某個特定的數據結構相關聯，即一個鎖可用于保護隊列的訪問，另一個鎖保護訪問鍊接列表的訪問，等等。由于這個原因，每個鎖通常有自己的資源類型，并且這種定義不是一個問題。進程在使用資源前應申請資源，在使用資源之後應釋放資源。一個進程可能要申請許多資源，以便完成指定任務。顯然，申請的資源數量不能超過系統所有資源的總和。換言之，如果系統隻有兩台打印機，那麼進程就不能申請三台打印機。在正常操作模式下，進程隻能按如下順序使用資源：

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

當進程或線程每次使用内核管理的資源時，操作系統會檢查以确保該進程或線程已經請求并獲得了資源。系統表記錄每個資源是否是空閑的或分配的。對于每個已分配的資源，該表還記錄了它被分配的進程。如果進程申請的資源正在為其他進程所使用，那麼該進程會添加到該資源的等待隊列上。當一組進程内的每個進程都在等待一個事件，而這一事件隻能由這一組進程的另一個進程引起，那麼這組進程就處于死鎖狀态。這裡所關心的主要事件是資源的獲取和釋放。資源可能是物理資源（例如，打印機、磁帶驅動器、内存空間和 CPU 周期）或邏輯資源（例如，信号量、互斥鎖和文件）。然而，其他類型的事件也會導緻死鎖（例如 IPC 功能）。為說明死鎖狀态，假設一個系統具有三個 CD 刻錄機。假定有三個進程，每個進程都占用了一台 CD 刻錄機。如果每個進程現在需要另一台刻錄機，那麼這三個進程會處于死鎖狀态。每個進程都在等待事件“CD刻錄機被釋放”，這僅可能由一個等待進程來完成。這個例子說明了涉及同一種資源類型的死鎖。死鎖也可能涉及不同資源類型。例如，假設一個系統有一台打印機和一台 DVD 驅動器。假如進程 Pi 占有 DVD 驅動器而進程 P2 占有打印機。如果 Pi 申請打印機而 Pj 申請 DVD 驅動器，那麼就會出現死鎖。多線程應用程序的開發人員應始終警惕可能的死鎖。多線程應用程序容易死鎖，因為多線程可能競争共享資源。

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

如果在一個系統中以下四個條件同時成立，那麼就能引起死鎖：

1. 互斥(mutual exclusion)：至少有一個資源必須處于非共享模式，即一次隻有一個進程可使用。如果另一進程申請該資源，那麼申請進程應等到該資源釋放為止。
2. 占有并等待(hold and wait)：—個進程應占有至少一個資源，并等待另一個資源，而該資源為其他進程所占有。
3. 非搶占(no preemption)：資源不能被搶占，即資源隻能被進程在完成任務後自願釋放。
4. 循環等待(circular wait)：有一組等待進程 {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 資源分配圖

圖 1 的資源分配圖表示了如下情況：

1.集合 P、R 和 E：

• P={P1,P2,P3}

• R={R1,R2,R3,R4}

• E={P1 -> R1,P2 -> R3,R1 -> P2,R2 -> P2,R2 -> P1,R3 -> P3}

2.資源實例：

• 資源類型 R1 有 1 個實例；
• 資源類型 R2 有 2 個實例；
• 資源類型 R3 有 1 個實例；
• 資源類型 R4 有 3 個實例；

3.進程狀态：

• 進程 P1 占有資源類型 R2 的 1 個實例，等待資源類型 R1 的 1 個實例。
• 進程 P2 占有資源類型 R1 的 1 個實例和資源類型 R2 的 1 個實例，等待資源類型 R3 的 1 個實例。
• 進程 P3 占有資源類型 R3 的 1 個實例。

根據資源分配圖的定義，可以證明：如果分配圖沒有環，那麼系統就沒有進程死鎖。如果分配圖有環，那麼可能存在死鎖。如果每個資源類型剛好有一個實例，那麼有環就意味着已經出現死鎖。如果環上的每個類型隻有一個實例，那麼就出現了死鎖。環上的進程就死鎖。在這種情況下，圖中的環就是死鎖存在的充分且必要條件。如果每個資源類型有多個實例，那麼有環并不意味着已經出現了死鎖。在這種情況下，圖中的環就是死鎖存在的必要條件而不是充分條件。為了說明這點，下面回到圖 1 所示資源分配圖。假設進程 P3 申請了資源類型 R2 的一個資源。由于現在沒有資源實例可用，所以就增加了有向邊 P3 -> R2（圖 2)。

圖 2 存在死鎖的資源分配圖

這時，系統有兩個最小環：

P1—> R1—> P2一> R3—> P3—> R2—> P1 P2—> R3—> P3—> R2—> P2

進程 P1、P2 和 P3 死鎖了。進程 P2 等待資源類型 R3，而它又被進程 R3 占有。進程 P3 等待進程 P1 或進程 P2 以釋放資源類型 R2。另外，進程 P1 等待進程 P2 釋放資源 R1。

圖 3 具有環的并未死鎖的資源分配圖

現在考慮圖 3 所示的資源分配圖。在這個例子中，也有一個環：

P1—> R1—> P3—> R2—> P1

然而，并沒有死鎖。注意，進程 P4 可能釋放資源類型 R2 的實例。這個資源可分配給進程 P3，從而打破環。總而言之，如果資源分配圖沒有環，那麼系統就不處于死鎖狀态。如果有環，那麼系統可能會也可能不會處于死鎖狀态。在處理死鎖問題時，這點是很重要的。

一般來說，處理死鎖問題有三種方法：

1. 通過協議來預防或避免死鎖，确保系統不會進入死鎖狀态。

2. 可以允許系統進入死鎖狀态，然後檢測它，并加以恢複。

3.可以忽視這個問題，認為死鎖不可能在系統内發生。

第三種解決方案為大多數操作系統所采用，包括 Linux 和 Windows。因此，應用程序開發人員需要自己編寫程序，以便處理死鎖。

接下來，我們簡要闡述每種死鎖處理方法。在進行之前，我們應該提一下，有些研究人員認為，這些基本方法不能單獨用于處理操作系統的所有資源分配問題。然而，可以将這些基本方法組合起來，為每種系統資源選擇一種最佳方法。

死鎖預防或死鎖避免為了确保死鎖不會發生，系統可以采用死鎖預防或死鎖避免方案。

死鎖預防方法确保至少有一個必要條件不成立。這些方法通過限制如何申請資源的方法來預防死鎖。死鎖避免要求，操作系統事先得到有關進程申請資源和使用資源的額外信息。有了這些額外信息，系統可以确定對于每個申請，進程是否應等待。為了确定當前申請是允許還是延遲，系統應考慮現有的可用資源、已分配給每個進程的資源及每個進程将來申請和釋放的資源。

如果系統不使用死鎖預防或死鎖避免算法，那麼死鎖情況可能發生。在這種情況下，系統可以提供一個算法來檢查系統狀态以确定死鎖是否發生，提供另一個算法來從死鎖中恢複（如果死鎖确實已經發生）。 當沒有算法用于檢測和恢複死鎖時，可能出現這樣的情況，系統處于死鎖，而又沒有方法檢測到底發生了什麼。在這種情況下，未被發現的死鎖會導緻系統性能下降，因為資源被不能運行的進程占有，而越來越多的進程會因申請資源而進入死鎖。最後，整個系統會停止工作，且需要人工重新啟動。 雖然這看起來似乎不是一個解決死鎖問題的可行方法，但是它卻為大多數操作系統所采用，許多系統死鎖很少發生，因此與使用頻繁的并且開銷昂貴的死鎖預防、死鎖避免和死鎖檢測與恢複相比，這種方法更為便宜。此外，在有些情況下，系統處于凍結狀态而不是死鎖狀态。例如，一個實時進程按最高優先級來運行（或其他進程在非搶占調用程序下運行），并且不将控制返回到操作系統。因此，系統應有人工方法可從這些狀态中恢複過來，這些方法也可用于死鎖恢複。

參考資料：《操作系統概念 operating system concepts》

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!