前言

計算機系統中有很多獨占性的資源，在同一時刻隻能每個資源隻能由一個進程使用，我們之前經常提到過打印機，這就是一個獨占性的資源，同一時刻不能有兩個打印機同時輸出結果，否則會引起文件系統的癱瘓。所以，操作系統具有授權一個進程單獨訪問資源的能力。

兩個進程獨占性的訪問某個資源，從而等待另外一個資源的執行結果，會導緻兩個進程都被阻塞，并且兩個進程都不會釋放各自的資源，這種情況就是 死鎖(deadlock)。

死鎖可以發生在任何層面，在不同的機器之間可能會發生死鎖，在數據庫系統中也會導緻死鎖，比如進程 A 對記錄 R1 加鎖，進程 B 對記錄 R2 加鎖，然後進程 A 和 B 都試圖把對象的記錄加鎖，這種情況下就會産生死鎖。

下面我們就來讨論一下什麼是死鎖、死鎖的條件是什麼、死鎖如何預防、活鎖是什麼等。

首先你需要先了解一個概念，那就是資源是什麼

資源

大部分的死鎖都和資源有關，在進程對設備、文件具有獨占性（排他性）時會産生死鎖。我們把這類需要排他性使用的對象稱為資源(resource)。資源主要分為 可搶占資源和不可搶占資源

可搶占資源和不可搶占資源

資源主要有可搶占資源和不可搶占資源。可搶占資源(preemptable resource) 可以從擁有它的進程中搶占而不會造成其他影響，内存就是一種可搶占性資源，任何進程都能夠搶先獲得内存的使用權。

不可搶占資源(nonpreemtable resource) 指的是除非引起錯誤或者異常，否則進程無法搶占指定資源，這種不可搶占的資源比如有光盤，在進程執行調度的過程中，其他進程是不能得到該資源的。

死鎖與不可搶占資源有關，雖然搶占式資源也會造成死鎖，不過這種情況的解決辦法通常是在進程之間重新分配資源來化解。所以，我們的重點自然就會放在了不可搶占資源上。

下面給出了使用資源所需事件的抽象順序

如果在請求時資源不存在，請求進程就會強制等待。在某些操作系統中，當請求資源失敗時進程會自動阻塞，當自資源可以獲取時進程會自動喚醒。在另外一些操作系統中，請求資源失敗并顯示錯誤代碼，然後等待進程等待一會兒再繼續重試。

請求資源失敗的進程會陷入一種請求資源、休眠、再請求資源的循環中。此類進程雖然沒有阻塞，但是處于從目的和結果考慮，這類進程和阻塞差不多，因為這類進程并沒有做任何有用的工作。

請求資源的這個過程是很依賴操作系統的。在一些系統中，一個 request 系統調用用來允許進程訪問資源。在一些系統中，操作系統對資源的認知是它是一種特殊文件，在任何同一時刻隻能被一個進程打開和占用。資源通過 open 命令進行打開。如果文件已經正在使用，那麼這個調用者會阻塞直到當前的占用文件的進程關閉文件為止。

資源獲取

對于一些數據庫系統中的記錄這類資源來說，應該由用戶進程來對其進行管理。有一種管理方式是使用信号量(semaphore) 。這些信号量會初始化為 1 。互斥鎖也能夠起到相同的作用。

這裡說一下什麼是互斥鎖(Mutexes):

在計算機程序中，互斥對象(mutex) 是一個程序對象，它允許多個程序共享同一資源，例如文件訪問權限，但并不是同時訪問。需要鎖定資源的線程都必須在使用資源時将互斥鎖與其他線程綁定（進行加鎖）。當不再需要數據或線程結束時，互斥鎖設置為解鎖。

下面是一個僞代碼，這部分代碼說明了信号量的資源獲取、資源釋放等操作，如下所示

typedef int semaphore; semaphore aResource; void processA(void){ down(&aResource); useResource(); up(&aResource); }

上面顯示了一個進程資源獲取和釋放的過程，但是一般情況下會存在多個資源同時獲取鎖的情景，這樣該如何處理？如下所示

typedef int semaphore; semaphore aResource; semaphore bResource; void processA(void){ down(&aResource); down(&bResource); useAResource(); useBResource(); up(&aResource); up(&bResource); }

對于單個進程來說，并不需要加鎖，因為不存在和這個進程的競争條件。所以單進條件下程序能夠完好運行。

現在讓我們考慮兩個進程的情況，A 和 B ，還存在兩個資源。如下所示

typedef int semaphore; semaphore aResource; semaphore bResource; void processA(void){ down(&aResource); down(&bResource); useBothResource(); up(&bResource); up(&aResource); } void processB(void){ down(&aResource); down(&bResource); useBothResource(); up(&bResource); up(&aResource); }

在上述代碼中，兩個進程以相同的順序訪問資源。在這段代碼中，一個進程在另一個進程之前獲取資源，如果另外一個進程想在第一個進程釋放之前獲取資源，那麼它會由于資源的加鎖而阻塞，直到該資源可用為止。

在下面這段代碼中，有一些變化

typedef int semaphore; semaphore aResource; semaphore bResource; void processA(void){ down(&aResource); down(&bResource); useBothResource(); up(&bResource); up(&aResource); } void processB(void){ down(&bResource); // 變化的代碼 down(&aResource); // 變化的代碼 useBothResource(); up(&aResource); // 變化的代碼 up(&bResource); // 變化的代碼 }

這種情況就不同了，可能會發生同時獲取兩個資源并有效地阻塞另一個過程，直到完成為止。也就是說，可能會發生進程 A 獲取資源 A 的同時進程 B 獲取資源 B 的情況。然後每個進程在嘗試獲取另一個資源時被阻塞。

在這裡我們會發現一個簡單的獲取資源順序的問題就會造成死鎖，所以死鎖是很容易發生的，所以下面我們就對死鎖做一個詳細的認識和介紹。

死鎖

如果要對死鎖進行一個定義的話，下面的定義比較貼切

如果一組進程中的每個進程都在等待一個事件，而這個事件隻能由該組中的另一個進程觸發，這種情況會導緻死鎖。

簡單一點來表述一下，就是每個進程都在等待其他進程釋放資源，而其他資源也在等待每個進程釋放資源，這樣沒有進程搶先釋放自己的資源，這種情況會産生死鎖，所有進程都會無限的等待下去。

換句話說，死鎖進程結合中的每個進程都在等待另一個死鎖進程已經占有的資源。但是由于所有進程都不能運行，它們之中任何一個資源都無法釋放資源，所以沒有一個進程可以被喚醒。這種死鎖也被稱為資源死鎖(resource deadlock)。資源死鎖是最常見的類型，但不是所有的類型，我們後面會介紹其他類型，我們先來介紹資源死鎖

資源死鎖的條件

針對我們上面的描述，資源死鎖可能出現的情況主要有

• 互斥條件：每個資源都被分配給了一個進程或者資源是可用的
• 保持和等待條件：已經獲取資源的進程被認為能夠獲取新的資源
• 不可搶占條件：分配給一個進程的資源不能強制的從其他進程搶占資源，它隻能由占有它的進程顯示釋放
• 循環等待：死鎖發生時，系統中一定有兩個或者兩個以上的進程組成一個循環，循環中的每個進程都在等待下一個進程釋放的資源。

發生死鎖時，上面的情況必須同時會發生。如果其中任意一個條件不會成立，死鎖就不會發生。可以通過破壞其中任意一個條件來破壞死鎖，下面這些破壞條件就是我們探讨的重點

死鎖模型

Holt 在 1972 年提出對死鎖進行建模，建模的标準如下：

• 圓形表示進程
• 方形表示資源

從資源節點到進程節點表示資源已經被進程占用，如下圖所示

在上圖中表示當前資源 R 正在被 A 進程所占用

由進程節點到資源節點的有向圖表示當前進程正在請求資源，并且該進程已經被阻塞，處于等待這個資源的狀态

在上圖中，表示的含義是進程 B 正在請求資源 S 。Holt 認為，死鎖的描述應該如下

這是一個死鎖的過程，進程 C 等待資源 T 的釋放，資源 T 卻已經被進程 D 占用，進程 D 等待請求占用資源 U ，資源 U 卻已經被線程 C 占用，從而形成環。

總結一點：吃着碗裡的看着鍋裡的容易死鎖

那麼如何避免死鎖呢？我們還是通過死鎖模型來聊一聊

假設有三個進程 (A、B、C) 和三個資源(R、S、T) 。三個進程對資源的請求和釋放序列如下圖所示

操作系統可以任意選擇一個非阻塞的程序運行，所以它可以決定運行 A 直到 A 完成工作；它可以運行 B 直到 B 完成工作；最後運行 C。

這樣的順序不會導緻死鎖（因為不存在對資源的競争），但是這種情況也完全沒有并行性。進程除了在請求和釋放資源外，還要做計算和輸入/輸出的工作。當進程按照順序運行時，在等待一個 I/O 時，另一個進程不能使用 CPU。所以，嚴格按照串行的順序執行并不是最優越的。另一方面，如果沒有進程在執行任何 I/O 操作，那麼最短路徑優先作業會優于輪轉調度，所以在這種情況下串行可能是最優越的

現在我們假設進程會執行計算和 I/O 操作，所以輪詢調度是一種合理的調度算法。資源請求可能會按照下面這個順序進行

下圖是針對上面這六個步驟的資源分配圖。

這裡需要注意一個問題，為什麼從資源出來的有向圖指向了進程卻表示進程請求資源呢？筆者剛開始看也有這個疑問，但是想了一下這個意思解釋為進程占用資源比較合适，而進程的有向圖指向資源表示進程被阻塞的意思。

在上面的第四個步驟，進程 A 正在等待資源 S；第五個步驟中，進程 B 在等待資源 T；第六個步驟中，進程 C 在等待資源 R，因此産生了環路并導緻了死鎖。

然而，操作系統并沒有規定一定按照某種特定的順序來執行這些進程。遇到一個可能會引起死鎖的線程後，操作系統可以幹脆不批準請求，并把進程挂起一直到安全狀态為止。比如上圖中，如果操作系統認為有死鎖的可能，它可以選擇不把資源 S 分配給 B ，這樣 B 被挂起。這樣的話操作系統會隻運行 A 和 C，那麼資源的請求和釋放就會是下面的步驟

下圖是針對上面這六個步驟的資源分配圖。

在第六步執行完成後，可以發現并沒有産生死鎖，此時就可以把資源 S 分配給 B，因為 A 進程已經執行完畢，C 進程已經拿到了它想要的資源。進程 B 可以直接獲得資源 S，也可以等待進程 C 釋放資源 T 。

有四種處理死鎖的策略：

• 忽略死鎖帶來的影響（驚呆了）
• 檢測死鎖并回複死鎖，死鎖發生時對其進行檢測，一旦發生死鎖後，采取行動解決問題
• 通過仔細分配資源來避免死鎖
• 通過破壞死鎖産生的四個條件之一來避免死鎖

下面我們分别介紹一下這四種方法

鴕鳥算法

最簡單的解決辦法就是使用鴕鳥算法(ostrich algorithm)，把頭埋在沙子裡，假裝問題根本沒有發生。每個人看待這個問題的反應都不同。數學家認為死鎖是不可接受的，必須通過有效的策略來防止死鎖的産生。工程師想要知道問題發生的頻次，系統因為其他原因崩潰的次數和死鎖帶來的嚴重後果。如果死鎖發生的頻次很低，而經常會由于硬件故障、編譯器錯誤等其他操作系統問題導緻系統崩潰，那麼大多數工程師不會修複死鎖。

死鎖檢測和恢複

第二種技術是死鎖的檢測和恢複。這種解決方式不會嘗試去阻止死鎖的出現。相反，這種解決方案會希望死鎖盡可能的出現，在監測到死鎖出現後，對其進行恢複。下面我們就來探讨一下死鎖的檢測和恢複的幾種方式

每種類型一個資源的死鎖檢測方式

每種資源類型都有一個資源是什麼意思？我們經常提到的打印機就是這樣的，資源隻有打印機，但是設備都不會超過一個。

可以通過構造一張資源分配表來檢測這種錯誤，比如我們上面提到的

的算法來檢測從 P1 到 Pn 這 n 個進程中的死鎖。假設資源類型為 m，E1 代表資源類型1，E2 表示資源類型 2 ，Ei 代表資源類型 i (1 <= i <= m)。E 表示的是 現有資源向量(existing resource vector)，代表每種已存在的資源總數。

現在我們就需要構造兩個數組：C 表示的是當前分配矩陣(current allocation matrix) ，R 表示的是 請求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數。所以，Cij 表示 Pi 持有資源 j 的數量。Rij 表示 Pi 所需要獲得的資源 j 的數量

一般來說，已分配資源 j 的數量加起來再和所有可供使用的資源數相加 = 該類資源的總數。

死鎖的檢測就是基于向量的比較。每個進程起初都是沒有被标記過的，算法會開始對進程做标記，進程被标記後說明進程被執行了，不會進入死鎖，當算法結束時，任何沒有被标記過的進程都會被判定為死鎖進程。

上面我們探讨了兩種檢測死鎖的方式，那麼現在你知道怎麼檢測後，你何時去做死鎖檢測呢？一般來說，有兩個考量标準：

• 每當有資源請求時就去檢測，這種方式會占用昂貴的 CPU 時間。
• 每隔 k 分鐘檢測一次，或者當 CPU 使用率降低到某個标準下去檢測。考慮到 CPU 效率的原因，如果死鎖進程達到一定數量，就沒有多少進程可以運行，所以 CPU 會經常空閑。

從死鎖中恢複

上面我們探讨了如何檢測進程死鎖，我們最終的目的肯定是想讓程序能夠正常的運行下去，所以針對檢測出來的死鎖，我們要對其進行恢複，下面我們會探讨幾種死鎖的恢複方式

通過搶占進行恢複

在某些情況下，可能會臨時将某個資源從它的持有者轉移到另一個進程。比如在不通知原進程的情況下，将某個資源從進程中強制取走給其他進程使用，使用完後又送回。這種恢複方式一般比較困難而且有些簡單粗暴，并不可取。

通過回滾進行恢複

如果系統設計者和機器操作員知道有可能發生死鎖，那麼就可以定期檢查流程。進程的檢測點意味着進程的狀态可以被寫入到文件以便後面進行恢複。檢測點不僅包含存儲映像(memory image)，還包含資源狀态(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測點，而是每出現一個檢測點都要把它寫入到文件中，這樣當進程執行時，就會有一系列的檢查點文件被累積起來。

為了進行恢複，要從上一個較早的檢查點上開始，這樣所需要資源的進程會回滾到上一個時間點，在這個時間點上，死鎖進程還沒有獲取所需要的資源，可以在此時對其進行資源分配。

殺死進程恢複

最簡單有效的解決方案是直接殺死一個死鎖進程。但是殺死一個進程可能照樣行不通，這時候就需要殺死别的資源進行恢複。

另外一種方式是選擇一個環外的進程作為犧牲品來釋放進程資源。

死鎖避免

我們上面讨論的是如何檢測出現死鎖和如何恢複死鎖，下面我們探讨幾種規避死鎖的方式

單個資源的銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調度算法，它本身是一種死鎖的調度算法。它的模型是基于一個城鎮中的銀行家，銀行家向城鎮中的客戶承諾了一定數量的貸款額度。算法要做的就是判斷請求是否會進入一種不安全的狀态。如果是，就拒絕請求，如果請求後系統是安全的，就接受該請求。

比如下面的例子，銀行家一共為所有城鎮居民提供了 15 單位個貸款額度，一個單位表示 1k 美元，如下所示

城鎮居民都喜歡做生意，所以就會涉及到貸款，每個人能貸款的最大額度不一樣，在某一時刻，A/B/C/D 的貸款金額如下

上面每個人的貸款總額加起來是 13，馬上接近 15，銀行家隻能給 A 和 C 進行放貸，可以拖着 B 和 D、所以，可以讓 A 和 C 首先完成，釋放貸款額度，以此來滿足其他居民的貸款。這是一種安全的狀态。

如果每個人的請求導緻總額會超過甚至接近 15 ，就會處于一種不安全的狀态，如下所示

這樣，每個人還能貸款至少 2 個單位的額度，如果其中有一個人發起最大額度的貸款請求，就會使系統處于一種死鎖狀态。

這裡注意一點：不安全狀态并不一定引起死鎖，由于客戶不一定需要其最大的貸款額度，但是銀行家不敢抱着這種僥幸心理。

銀行家算法就是對每個請求進行檢查，檢查是否請求會引起不安全狀态，如果不會引起，那麼就接受該請求；如果會引起，那麼就推遲該請求。

類似的，還有多個資源的銀行家算法，讀者可以自行了解。

破壞死鎖

死鎖本質上是無法避免的，因為它需要獲得未知的資源和請求，但是死鎖是滿足四個條件後才出現的，它們分别是

• 互斥
• 保持和等待
• 不可搶占
• 循環等待

我們分别對這四個條件進行讨論，按理說破壞其中的任意一個條件就能夠破壞死鎖

破壞互斥條件

我們首先考慮的就是破壞互斥使用條件。如果資源不被一個進程獨占，那麼死鎖肯定不會産生。如果兩個打印機同時使用一個資源會造成混亂，打印機的解決方式是使用 假脫機打印機(spooling printer) ，這項技術可以允許多個進程同時産生輸出，在這種模型中，實際請求打印機的唯一進程是打印機守護進程，也稱為後台進程。後台進程不會請求其他資源。我們可以消除打印機的死鎖。

後台進程通常被編寫為能夠輸出完整的文件後才能打印，假如兩個進程都占用了假脫機空間的一半，而這兩個進程都沒有完成全部的輸出，就會導緻死鎖。

因此，盡量做到盡可能少的進程可以請求資源。

破壞保持等待的條件

第二種方式是如果我們能阻止持有資源的進程請求其他資源，我們就能夠消除死鎖。一種實現方式是讓所有的進程開始執行前請求全部的資源。如果所需的資源可用，進程會完成資源的分配并運行到結束。如果有任何一個資源處于頻繁分配的情況，那麼沒有分配到資源的進程就會等待。

很多進程無法在執行完成前就知道到底需要多少資源，如果知道的話，就可以使用銀行家算法；還有一個問題是這樣無法合理有效利用資源。

還有一種方式是進程在請求其他資源時，先釋放所占用的資源，然後再嘗試一次獲取全部的資源。

破壞不可搶占條件

破壞不可搶占條件也是可以的。可以通過虛拟化的方式來避免這種情況。

破壞循環等待條件

現在就剩最後一個條件了，循環等待條件可以通過多種方法來破壞。一種方式是制定一個标準，一個進程在任何時候隻能使用一種資源。如果需要另外一種資源，必須釋放當前資源。對于需要将大文件從磁帶複制到打印機的過程，此限制是不可接受的。

另一種方式是将所有的資源統一編号，如下圖所示

進程可以在任何時間提出請求，但是所有的請求都必須按照資源的順序提出。如果按照此分配規則的話，那麼資源分配之間不會出現環。

盡管通過這種方式來消除死鎖，但是編号的順序不可能讓每個進程都會接受。

其他問題

下面我們來探讨一下其他問題，包括 通信死鎖、活鎖是什麼、饑餓問題和兩階段加鎖

兩階段加鎖

雖然很多情況下死鎖的避免和預防都能處理，但是效果并不好。随着時間的推移，提出了很多優秀的算法用來處理死鎖。例如在數據庫系統中，一個經常發生的操作是請求鎖住一些記錄，然後更新所有鎖定的記錄。當同時有多個進程運行時，就會有死鎖的風險。

一種解決方式是使用 兩階段提交(two-phase locking)。顧名思義分為兩個階段，一階段是進程嘗試一次鎖定它需要的所有記錄。如果成功後，才會開始第二階段，第二階段是執行更新并釋放鎖。第一階段并不做真正有意義的工作。

如果在第一階段某個進程所需要的記錄已經被加鎖，那麼該進程會釋放所有鎖定的記錄并重新開始第一階段。從某種意義上來說，這種方法類似于預先請求所有必需的資源或者是在進行一些不可逆的操作之前請求所有的資源。

不過在一般的應用場景中，兩階段加鎖的策略并不通用。如果一個進程缺少資源就會半途中斷并重新開始的方式是不可接受的。

通信死鎖

我們上面一直讨論的是資源死鎖，資源死鎖是一種死鎖類型，但并不是唯一類型，還有通信死鎖，也就是兩個或多個進程在發送消息時出現的死鎖。進程 A 給進程 B 發了一條消息，然後進程 A 阻塞直到進程 B 返回響應。假設請求消息丢失了，那麼進程 A 在一直等着回複，進程 B 也會阻塞等待請求消息到來，這時候就産生死鎖。

盡管會産生死鎖，但是這并不是一個資源死鎖，因為 A 并沒有占據 B 的資源。事實上，通信死鎖并沒有完全可見的資源。根據死鎖的定義來說：每個進程因為等待其他進程引起的事件而産生阻塞，這就是一種死鎖。相較于最常見的通信死鎖，我們把上面這種情況稱為通信死鎖(communication deadlock)。

通信死鎖不能通過調度的方式來避免，但是可以使用通信中一個非常重要的概念來避免：超時(timeout)。在通信過程中，隻要一個信息被發出後，發送者就會啟動一個定時器，定時器會記錄消息的超時時間，如果超時時間到了但是消息還沒有返回，就會認為消息已經丢失并重新發送，通過這種方式，可以避免通信死鎖。

但是并非所有網絡通信發生的死鎖都是通信死鎖，也存在資源死鎖，下面就是一個典型的資源死鎖。

當一個數據包從主機進入路由器時，會被放入一個緩沖區，然後再傳輸到另外一個路由器，再到另一個，以此類推直到目的地。緩沖區都是資源并且數量有限。如下圖所示，每個路由器都有 10 個緩沖區（實際上有很多）。

假如路由器 A 的所有數據需要發送到 B ，B 的所有數據包需要發送到 D，然後 D 的所有數據包需要發送到 A 。沒有數據包可以移動，因為在另一端沒有緩沖區可用，這就是一個典型的資源死鎖。

活鎖

你會發現一個很有意思的事情，死鎖就跟榆木腦袋一樣，不會轉彎。我看過古代的一則故事：

如果說死鎖很癡情的話，那麼活鎖用一則成語來表示就是 弄巧成拙。

某些情況下，當進程意識到它不能獲取所需要的下一個鎖時，就會嘗試禮貌的釋放已經獲得的鎖，然後等待非常短的時間再次嘗試獲取。可以想像一下這個場景：當兩個人在狹路相逢的時候，都想給對方讓路，相同的步調會導緻雙方都無法前進。

現在假想有一對并行的進程用到了兩個資源。它們分别嘗試獲取另一個鎖失敗後，兩個進程都會釋放自己持有的鎖，再次進行嘗試，這個過程會一直進行重複。很明顯，這個過程中沒有進程阻塞，但是進程仍然不會向下執行，這種狀況我們稱之為 活鎖(livelock)。

饑餓

與死鎖和活鎖的一個非常相似的問題是 饑餓(starvvation)。想象一下你什麼時候會餓？一段時間不吃東西是不是會餓？對于進程來講，最重要的就是資源，如果一段時間沒有獲得資源，那麼進程會産生饑餓，這些進程會永遠得不到服務。

我們假設打印機的分配方案是每次都會分配給最小文件的進程，那麼要打印大文件的進程會永遠得不到服務，導緻進程饑餓，進程會無限制的推後，雖然它沒有阻塞。

總結

死鎖是一類通用問題，任何操作系統都會産生死鎖。當每一組進程中的每個進程都因等待由該組的其他進程所占有的資源而導緻阻塞，死鎖就發生了。這種情況會使所有的進程都處于無限等待的狀态。

死鎖的檢測和避免可以通過安全和不安全狀态來判斷，其中一個檢測方式就是銀行家算法；當然你也可以使用鴕鳥算法對死鎖置之不理，但是你肯定會遭其反噬。

也可以在設計時通過系統結構的角度來避免死鎖，這樣能夠預防死鎖；也可以破壞死鎖的四個條件來破壞死鎖。資源死鎖并不是唯一性的死鎖，還有通信間死鎖，可以設置适當的超時時間來完成。

活鎖和死鎖的問題有些相似，它們都是一種進程無法繼續向下執行的狀态。由于進程調度策略導緻嘗試獲取進程的一方永遠無法獲得資源後，進程會導緻饑餓的出現。

尾聲

提出一個勘誤，已反饋給出版社

,