前言

計(jì)算機(jī)系統(tǒng)中有很多獨(dú)占性的資源，在同一時(shí)刻只能每個(gè)資源只能由一個(gè)進(jìn)程使用，我們之前經(jīng)常提到過打印機(jī)，這就是一個(gè)獨(dú)占性的資源，同一時(shí)刻不能有兩個(gè)打印機(jī)同時(shí)輸出結(jié)果，否則會(huì)引起文件系統(tǒng)的癱瘓。所以，操作系統(tǒng)具有授權(quán)一個(gè)進(jìn)程單獨(dú)訪問資源的能力。

兩個(gè)進(jìn)程獨(dú)占性的訪問某個(gè)資源，從而等待另外一個(gè)資源的執(zhí)行結(jié)果，會(huì)導(dǎo)致兩個(gè)進(jìn)程都被阻塞，并且兩個(gè)進(jìn)程都不會(huì)釋放各自的資源，這種情況就是 死鎖(deadlock)。

死鎖可以發(fā)生在任何層面，在不同的機(jī)器之間可能會(huì)發(fā)生死鎖，在數(shù)據(jù)庫(kù)系統(tǒng)中也會(huì)導(dǎo)致死鎖，比如進(jìn)程 A 對(duì)記錄 R1 加鎖，進(jìn)程 B 對(duì)記錄 R2 加鎖，然后進(jìn)程 A 和 B 都試圖把對(duì)象的記錄加鎖，這種情況下就會(huì)產(chǎn)生死鎖。

下面我們就來討論一下什么是死鎖、死鎖的條件是什么、死鎖如何預(yù)防、活鎖是什么等。

首先你需要先了解一個(gè)概念，那就是資源是什么

資源

大部分的死鎖都和資源有關(guān)，在進(jìn)程對(duì)設(shè)備、文件具有獨(dú)占性（排他性）時(shí)會(huì)產(chǎn)生死鎖。我們把這類需要排他性使用的對(duì)象稱為資源(resource)。資源主要分為 可搶占資源和不可搶占資源

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

資源主要有可搶占資源和不可搶占資源?？蓳屨假Y源(preemptable resource) 可以從擁有它的進(jìn)程中搶占而不會(huì)造成其他影響，內(nèi)存就是一種可搶占性資源，任何進(jìn)程都能夠搶先獲得內(nèi)存的使用權(quán)。

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

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

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

如果在請(qǐng)求時(shí)資源不存在，請(qǐng)求進(jìn)程就會(huì)強(qiáng)制等待。在某些操作系統(tǒng)中，當(dāng)請(qǐng)求資源失敗時(shí)進(jìn)程會(huì)自動(dòng)阻塞，當(dāng)自資源可以獲取時(shí)進(jìn)程會(huì)自動(dòng)喚醒。在另外一些操作系統(tǒng)中，請(qǐng)求資源失敗并顯示錯(cuò)誤代碼，然后等待進(jìn)程等待一會(huì)兒再繼續(xù)重試。

請(qǐng)求資源失敗的進(jìn)程會(huì)陷入一種請(qǐng)求資源、休眠、再請(qǐng)求資源的循環(huán)中。此類進(jìn)程雖然沒有阻塞，但是處于從目的和結(jié)果考慮，這類進(jìn)程和阻塞差不多，因?yàn)檫@類進(jìn)程并沒有做任何有用的工作。

請(qǐng)求資源的這個(gè)過程是很依賴操作系統(tǒng)的。在一些系統(tǒng)中，一個(gè) request 系統(tǒng)調(diào)用用來允許進(jìn)程訪問資源。在一些系統(tǒng)中，操作系統(tǒng)對(duì)資源的認(rèn)知是它是一種特殊文件，在任何同一時(shí)刻只能被一個(gè)進(jìn)程打開和占用。資源通過 open 命令進(jìn)行打開。如果文件已經(jīng)正在使用，那么這個(gè)調(diào)用者會(huì)阻塞直到當(dāng)前的占用文件的進(jìn)程關(guān)閉文件為止。

資源獲取

對(duì)于一些數(shù)據(jù)庫(kù)系統(tǒng)中的記錄這類資源來說，應(yīng)該由用戶進(jìn)程來對(duì)其進(jìn)行管理。有一種管理方式是使用信號(hào)量(semaphore) 。這些信號(hào)量會(huì)初始化為 1 ?；コ怄i也能夠起到相同的作用。

這里說一下什么是互斥鎖(Mutexes):

在計(jì)算機(jī)程序中，互斥對(duì)象(mutex) 是一個(gè)程序?qū)ο?，它允許多個(gè)程序共享同一資源，例如文件訪問權(quán)限，但并不是同時(shí)訪問。需要鎖定資源的線程都必須在使用資源時(shí)將互斥鎖與其他線程綁定（進(jìn)行加鎖）。當(dāng)不再需要數(shù)據(jù)或線程結(jié)束時(shí)，互斥鎖設(shè)置為解鎖。

下面是一個(gè)偽代碼，這部分代碼說明了信號(hào)量的資源獲取、資源釋放等操作，如下所示

typedef int semaphore;
semaphore aResource;

void processA(void){
  
  down(&aResource);
	useResource();
  up(&aResource);
  

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

typedef int semaphore;
semaphore aResource;
semaphore bResource;

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

對(duì)于單個(gè)進(jìn)程來說，并不需要加鎖，因?yàn)椴淮嬖诤瓦@個(gè)進(jìn)程的競(jìng)爭(zhēng)條件。所以單進(jìn)條件下程序能夠完好運(yùn)行。

現(xiàn)在讓我們考慮兩個(gè)進(jìn)程的情況，A 和 B ，還存在兩個(gè)資源。如下所示

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);
  
}

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

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

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); // 變化的代碼 
  
}

這種情況就不同了，可能會(huì)發(fā)生同時(shí)獲取兩個(gè)資源并有效地阻塞另一個(gè)過程，直到完成為止。也就是說，可能會(huì)發(fā)生進(jìn)程 A 獲取資源 A 的同時(shí)進(jìn)程 B 獲取資源 B 的情況。然后每個(gè)進(jìn)程在嘗試獲取另一個(gè)資源時(shí)被阻塞。

在這里我們會(huì)發(fā)現(xiàn)一個(gè)簡(jiǎn)單的獲取資源順序的問題就會(huì)造成死鎖，所以死鎖是很容易發(fā)生的，所以下面我們就對(duì)死鎖做一個(gè)詳細(xì)的認(rèn)識(shí)和介紹。

死鎖

如果要對(duì)死鎖進(jìn)行一個(gè)定義的話，下面的定義比較貼切

如果一組進(jìn)程中的每個(gè)進(jìn)程都在等待一個(gè)事件，而這個(gè)事件只能由該組中的另一個(gè)進(jìn)程觸發(fā)，這種情況會(huì)導(dǎo)致死鎖。

簡(jiǎn)單一點(diǎn)來表述一下，就是每個(gè)進(jìn)程都在等待其他進(jìn)程釋放資源，而其他資源也在等待每個(gè)進(jìn)程釋放資源，這樣沒有進(jìn)程搶先釋放自己的資源，這種情況會(huì)產(chǎn)生死鎖，所有進(jìn)程都會(huì)無限的等待下去。

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

資源死鎖的條件

針對(duì)我們上面的描述，資源死鎖可能出現(xiàn)的情況主要有

• 互斥條件：每個(gè)資源都被分配給了一個(gè)進(jìn)程或者資源是可用的
• 保持和等待條件：已經(jīng)獲取資源的進(jìn)程被認(rèn)為能夠獲取新的資源
• 不可搶占條件：分配給一個(gè)進(jìn)程的資源不能強(qiáng)制的從其他進(jìn)程搶占資源，它只能由占有它的進(jìn)程顯示釋放
• 循環(huán)等待：死鎖發(fā)生時(shí)，系統(tǒng)中一定有兩個(gè)或者兩個(gè)以上的進(jìn)程組成一個(gè)循環(huán)，循環(huán)中的每個(gè)進(jìn)程都在等待下一個(gè)進(jìn)程釋放的資源。

發(fā)生死鎖時(shí)，上面的情況必須同時(shí)會(huì)發(fā)生。如果其中任意一個(gè)條件不會(huì)成立，死鎖就不會(huì)發(fā)生?？梢酝ㄟ^破壞其中任意一個(gè)條件來破壞死鎖，下面這些破壞條件就是我們探討的重點(diǎn)

死鎖模型

Holt 在 1972 年提出對(duì)死鎖進(jìn)行建模，建模的標(biāo)準(zhǔn)如下：

• 圓形表示進(jìn)程
• 方形表示資源

從資源節(jié)點(diǎn)到進(jìn)程節(jié)點(diǎn)表示資源已經(jīng)被進(jìn)程占用，如下圖所示

在上圖中表示當(dāng)前資源 R 正在被 A 進(jìn)程所占用

由進(jìn)程節(jié)點(diǎn)到資源節(jié)點(diǎn)的有向圖表示當(dāng)前進(jìn)程正在請(qǐng)求資源，并且該進(jìn)程已經(jīng)被阻塞，處于等待這個(gè)資源的狀態(tài)

在上圖中，表示的含義是進(jìn)程 B 正在請(qǐng)求資源 S 。Holt 認(rèn)為，死鎖的描述應(yīng)該如下

這是一個(gè)死鎖的過程，進(jìn)程 C 等待資源 T 的釋放，資源 T 卻已經(jīng)被進(jìn)程 D 占用，進(jìn)程 D 等待請(qǐng)求占用資源 U ，資源 U 卻已經(jīng)被線程 C 占用，從而形成環(huán)。

總結(jié)一點(diǎn)：吃著碗里的看著鍋里的容易死鎖

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

假設(shè)有三個(gè)進(jìn)程 (A、B、C) 和三個(gè)資源(R、S、T) 。三個(gè)進(jìn)程對(duì)資源的請(qǐng)求和釋放序列如下圖所示

操作系統(tǒng)可以任意選擇一個(gè)非阻塞的程序運(yùn)行，所以它可以決定運(yùn)行 A 直到 A 完成工作；它可以運(yùn)行 B 直到 B 完成工作；最后運(yùn)行 C。

這樣的順序不會(huì)導(dǎo)致死鎖（因?yàn)椴淮嬖趯?duì)資源的競(jìng)爭(zhēng)），但是這種情況也完全沒有并行性。進(jìn)程除了在請(qǐng)求和釋放資源外，還要做計(jì)算和輸入/輸出的工作。當(dāng)進(jìn)程按照順序運(yùn)行時(shí)，在等待一個(gè) I/O 時(shí)，另一個(gè)進(jìn)程不能使用 CPU。所以，嚴(yán)格按照串行的順序執(zhí)行并不是最優(yōu)越的。另一方面，如果沒有進(jìn)程在執(zhí)行任何 I/O 操作，那么最短路徑優(yōu)先作業(yè)會(huì)優(yōu)于輪轉(zhuǎn)調(diào)度，所以在這種情況下串行可能是最優(yōu)越的

現(xiàn)在我們假設(shè)進(jìn)程會(huì)執(zhí)行計(jì)算和 I/O 操作，所以輪詢調(diào)度是一種合理的調(diào)度算法。資源請(qǐng)求可能會(huì)按照下面這個(gè)順序進(jìn)行

下圖是針對(duì)上面這六個(gè)步驟的資源分配圖。

這里需要注意一個(gè)問題，為什么從資源出來的有向圖指向了進(jìn)程卻表示進(jìn)程請(qǐng)求資源呢？筆者剛開始看也有這個(gè)疑問，但是想了一下這個(gè)意思解釋為進(jìn)程占用資源比較合適，而進(jìn)程的有向圖指向資源表示進(jìn)程被阻塞的意思。

在上面的第四個(gè)步驟，進(jìn)程 A 正在等待資源 S；第五個(gè)步驟中，進(jìn)程 B 在等待資源 T；第六個(gè)步驟中，進(jìn)程 C 在等待資源 R，因此產(chǎn)生了環(huán)路并導(dǎo)致了死鎖。

然而，操作系統(tǒng)并沒有規(guī)定一定按照某種特定的順序來執(zhí)行這些進(jìn)程。遇到一個(gè)可能會(huì)引起死鎖的線程后，操作系統(tǒng)可以干脆不批準(zhǔn)請(qǐng)求，并把進(jìn)程掛起一直到安全狀態(tài)為止。比如上圖中，如果操作系統(tǒng)認(rèn)為有死鎖的可能，它可以選擇不把資源 S 分配給 B ，這樣 B 被掛起。這樣的話操作系統(tǒng)會(huì)只運(yùn)行 A 和 C，那么資源的請(qǐng)求和釋放就會(huì)是下面的步驟

下圖是針對(duì)上面這六個(gè)步驟的資源分配圖。

在第六步執(zhí)行完成后，可以發(fā)現(xiàn)并沒有產(chǎn)生死鎖，此時(shí)就可以把資源 S 分配給 B，因?yàn)?A 進(jìn)程已經(jīng)執(zhí)行完畢，C 進(jìn)程已經(jīng)拿到了它想要的資源。進(jìn)程 B 可以直接獲得資源 S，也可以等待進(jìn)程 C 釋放資源 T 。

有四種處理死鎖的策略：

• 忽略死鎖帶來的影響（驚呆了）
• 檢測(cè)死鎖并回復(fù)死鎖，死鎖發(fā)生時(shí)對(duì)其進(jìn)行檢測(cè)，一旦發(fā)生死鎖后，采取行動(dòng)解決問題
• 通過仔細(xì)分配資源來避免死鎖
• 通過破壞死鎖產(chǎn)生的四個(gè)條件之一來避免死鎖

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

鴕鳥算法

最簡(jiǎn)單的解決辦法就是使用鴕鳥算法(ostrich algorithm)，把頭埋在沙子里，假裝問題根本沒有發(fā)生。每個(gè)人看待這個(gè)問題的反應(yīng)都不同。數(shù)學(xué)家認(rèn)為死鎖是不可接受的，必須通過有效的策略來防止死鎖的產(chǎn)生。工程師想要知道問題發(fā)生的頻次，系統(tǒng)因?yàn)槠渌虮罎⒌拇螖?shù)和死鎖帶來的嚴(yán)重后果。如果死鎖發(fā)生的頻次很低，而經(jīng)常會(huì)由于硬件故障、編譯器錯(cuò)誤等其他操作系統(tǒng)問題導(dǎo)致系統(tǒng)崩潰，那么大多數(shù)工程師不會(huì)修復(fù)死鎖。

死鎖檢測(cè)和恢復(fù)

第二種技術(shù)是死鎖的檢測(cè)和恢復(fù)。這種解決方式不會(huì)嘗試去阻止死鎖的出現(xiàn)。相反，這種解決方案會(huì)希望死鎖盡可能的出現(xiàn)，在監(jiān)測(cè)到死鎖出現(xiàn)后，對(duì)其進(jìn)行恢復(fù)。下面我們就來探討一下死鎖的檢測(cè)和恢復(fù)的幾種方式

每種類型一個(gè)資源的死鎖檢測(cè)方式

每種資源類型都有一個(gè)資源是什么意思？我們經(jīng)常提到的打印機(jī)就是這樣的，資源只有打印機(jī)，但是設(shè)備都不會(huì)超過一個(gè)。

可以通過構(gòu)造一張資源分配表來檢測(cè)這種錯(cuò)誤，比如我們上面提到的

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

現(xiàn)在我們就需要構(gòu)造兩個(gè)數(shù)組：C 表示的是當(dāng)前分配矩陣(current allocation matrix) ，R 表示的是 請(qǐng)求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數(shù)。所以，Cij 表示 Pi 持有資源 j 的數(shù)量。Rij 表示 Pi 所需要獲得的資源 j 的數(shù)量

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

死鎖的檢測(cè)就是基于向量的比較。每個(gè)進(jìn)程起初都是沒有被標(biāo)記過的，算法會(huì)開始對(duì)進(jìn)程做標(biāo)記，進(jìn)程被標(biāo)記后說明進(jìn)程被執(zhí)行了，不會(huì)進(jìn)入死鎖，當(dāng)算法結(jié)束時(shí)，任何沒有被標(biāo)記過的進(jìn)程都會(huì)被判定為死鎖進(jìn)程。

上面我們探討了兩種檢測(cè)死鎖的方式，那么現(xiàn)在你知道怎么檢測(cè)后，你何時(shí)去做死鎖檢測(cè)呢？一般來說，有兩個(gè)考量標(biāo)準(zhǔn)：

• 每當(dāng)有資源請(qǐng)求時(shí)就去檢測(cè)，這種方式會(huì)占用昂貴的 CPU 時(shí)間。
• 每隔 k 分鐘檢測(cè)一次，或者當(dāng) CPU 使用率降低到某個(gè)標(biāo)準(zhǔn)下去檢測(cè)?？紤]到 CPU 效率的原因，如果死鎖進(jìn)程達(dá)到一定數(shù)量，就沒有多少進(jìn)程可以運(yùn)行，所以 CPU 會(huì)經(jīng)?？臻e。

從死鎖中恢復(fù)

上面我們探討了如何檢測(cè)進(jìn)程死鎖，我們最終的目的肯定是想讓程序能夠正常的運(yùn)行下去，所以針對(duì)檢測(cè)出來的死鎖，我們要對(duì)其進(jìn)行恢復(fù)，下面我們會(huì)探討幾種死鎖的恢復(fù)方式

通過搶占進(jìn)行恢復(fù)

在某些情況下，可能會(huì)臨時(shí)將某個(gè)資源從它的持有者轉(zhuǎn)移到另一個(gè)進(jìn)程。比如在不通知原進(jìn)程的情況下，將某個(gè)資源從進(jìn)程中強(qiáng)制取走給其他進(jìn)程使用，使用完后又送回。這種恢復(fù)方式一般比較困難而且有些簡(jiǎn)單粗暴，并不可取。

通過回滾進(jìn)行恢復(fù)

如果系統(tǒng)設(shè)計(jì)者和機(jī)器操作員知道有可能發(fā)生死鎖，那么就可以定期檢查流程。進(jìn)程的檢測(cè)點(diǎn)意味著進(jìn)程的狀態(tài)可以被寫入到文件以便后面進(jìn)行恢復(fù)。檢測(cè)點(diǎn)不僅包含存儲(chǔ)映像(memory image)，還包含資源狀態(tài)(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測(cè)點(diǎn)，而是每出現(xiàn)一個(gè)檢測(cè)點(diǎn)都要把它寫入到文件中，這樣當(dāng)進(jìn)程執(zhí)行時(shí)，就會(huì)有一系列的檢查點(diǎn)文件被累積起來。

為了進(jìn)行恢復(fù)，要從上一個(gè)較早的檢查點(diǎn)上開始，這樣所需要資源的進(jìn)程會(huì)回滾到上一個(gè)時(shí)間點(diǎn)，在這個(gè)時(shí)間點(diǎn)上，死鎖進(jìn)程還沒有獲取所需要的資源，可以在此時(shí)對(duì)其進(jìn)行資源分配。

殺死進(jìn)程恢復(fù)

最簡(jiǎn)單有效的解決方案是直接殺死一個(gè)死鎖進(jìn)程。但是殺死一個(gè)進(jìn)程可能照樣行不通，這時(shí)候就需要?dú)⑺绖e的資源進(jìn)行恢復(fù)。

另外一種方式是選擇一個(gè)環(huán)外的進(jìn)程作為犧牲品來釋放進(jìn)程資源。

死鎖避免

我們上面討論的是如何檢測(cè)出現(xiàn)死鎖和如何恢復(fù)死鎖，下面我們探討幾種規(guī)避死鎖的方式

單個(gè)資源的銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調(diào)度算法，它本身是一種死鎖的調(diào)度算法。它的模型是基于一個(gè)城鎮(zhèn)中的銀行家，銀行家向城鎮(zhèn)中的客戶承諾了一定數(shù)量的貸款額度。算法要做的就是判斷請(qǐng)求是否會(huì)進(jìn)入一種不安全的狀態(tài)。如果是，就拒絕請(qǐng)求，如果請(qǐng)求后系統(tǒng)是安全的，就接受該請(qǐng)求。

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

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

上面每個(gè)人的貸款總額加起來是 13，馬上接近 15，銀行家只能給 A 和 C 進(jìn)行放貸，可以拖著 B 和 D、所以，可以讓 A 和 C 首先完成，釋放貸款額度，以此來滿足其他居民的貸款。這是一種安全的狀態(tài)。

如果每個(gè)人的請(qǐng)求導(dǎo)致總額會(huì)超過甚至接近 15 ，就會(huì)處于一種不安全的狀態(tài)，如下所示

這樣，每個(gè)人還能貸款至少 2 個(gè)單位的額度，如果其中有一個(gè)人發(fā)起最大額度的貸款請(qǐng)求，就會(huì)使系統(tǒng)處于一種死鎖狀態(tài)。

這里注意一點(diǎn)：不安全狀態(tài)并不一定引起死鎖，由于客戶不一定需要其最大的貸款額度，但是銀行家不敢抱著這種僥幸心理。

銀行家算法就是對(duì)每個(gè)請(qǐng)求進(jìn)行檢查，檢查是否請(qǐng)求會(huì)引起不安全狀態(tài)，如果不會(huì)引起，那么就接受該請(qǐng)求；如果會(huì)引起，那么就推遲該請(qǐng)求。

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

破壞死鎖

死鎖本質(zhì)上是無法避免的，因?yàn)樗枰@得未知的資源和請(qǐng)求，但是死鎖是滿足四個(gè)條件后才出現(xiàn)的，它們分別是

互斥

保持和等待

不可搶占

循環(huán)等待

我們分別對(duì)這四個(gè)條件進(jìn)行討論，按理說破壞其中的任意一個(gè)條件就能夠破壞死鎖

破壞互斥條件

我們首先考慮的就是破壞互斥使用條件。如果資源不被一個(gè)進(jìn)程獨(dú)占，那么死鎖肯定不會(huì)產(chǎn)生。如果兩個(gè)打印機(jī)同時(shí)使用一個(gè)資源會(huì)造成混亂，打印機(jī)的解決方式是使用 假脫機(jī)打印機(jī)(spooling printer) ，這項(xiàng)技術(shù)可以允許多個(gè)進(jìn)程同時(shí)產(chǎn)生輸出，在這種模型中，實(shí)際請(qǐng)求打印機(jī)的唯一進(jìn)程是打印機(jī)守護(hù)進(jìn)程，也稱為后臺(tái)進(jìn)程。后臺(tái)進(jìn)程不會(huì)請(qǐng)求其他資源。我們可以消除打印機(jī)的死鎖。

后臺(tái)進(jìn)程通常被編寫為能夠輸出完整的文件后才能打印，假如兩個(gè)進(jìn)程都占用了假脫機(jī)空間的一半，而這兩個(gè)進(jìn)程都沒有完成全部的輸出，就會(huì)導(dǎo)致死鎖。

因此，盡量做到盡可能少的進(jìn)程可以請(qǐng)求資源。

破壞保持等待的條件

第二種方式是如果我們能阻止持有資源的進(jìn)程請(qǐng)求其他資源，我們就能夠消除死鎖。一種實(shí)現(xiàn)方式是讓所有的進(jìn)程開始執(zhí)行前請(qǐng)求全部的資源。如果所需的資源可用，進(jìn)程會(huì)完成資源的分配并運(yùn)行到結(jié)束。如果有任何一個(gè)資源處于頻繁分配的情況，那么沒有分配到資源的進(jìn)程就會(huì)等待。

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

還有一種方式是進(jìn)程在請(qǐng)求其他資源時(shí)，先釋放所占用的資源，然后再嘗試一次獲取全部的資源。

破壞不可搶占條件

破壞不可搶占條件也是可以的?？梢酝ㄟ^虛擬化的方式來避免這種情況。

破壞循環(huán)等待條件

現(xiàn)在就剩最后一個(gè)條件了，循環(huán)等待條件可以通過多種方法來破壞。一種方式是制定一個(gè)標(biāo)準(zhǔn)，一個(gè)進(jìn)程在任何時(shí)候只能使用一種資源。如果需要另外一種資源，必須釋放當(dāng)前資源。對(duì)于需要將大文件從磁帶復(fù)制到打印機(jī)的過程，此限制是不可接受的。

另一種方式是將所有的資源統(tǒng)一編號(hào)，如下圖所示

進(jìn)程可以在任何時(shí)間提出請(qǐng)求，但是所有的請(qǐng)求都必須按照資源的順序提出。如果按照此分配規(guī)則的話，那么資源分配之間不會(huì)出現(xiàn)環(huán)。

盡管通過這種方式來消除死鎖，但是編號(hào)的順序不可能讓每個(gè)進(jìn)程都會(huì)接受。

其他問題

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

兩階段加鎖

雖然很多情況下死鎖的避免和預(yù)防都能處理，但是效果并不好。隨著時(shí)間的推移，提出了很多優(yōu)秀的算法用來處理死鎖。例如在數(shù)據(jù)庫(kù)系統(tǒng)中，一個(gè)經(jīng)常發(fā)生的操作是請(qǐng)求鎖住一些記錄，然后更新所有鎖定的記錄。當(dāng)同時(shí)有多個(gè)進(jìn)程運(yùn)行時(shí)，就會(huì)有死鎖的風(fēng)險(xiǎn)。

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

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

不過在一般的應(yīng)用場(chǎng)景中，兩階段加鎖的策略并不通用。如果一個(gè)進(jìn)程缺少資源就會(huì)半途中斷并重新開始的方式是不可接受的。

通信死鎖

我們上面一直討論的是資源死鎖，資源死鎖是一種死鎖類型，但并不是唯一類型，還有通信死鎖，也就是兩個(gè)或多個(gè)進(jìn)程在發(fā)送消息時(shí)出現(xiàn)的死鎖。進(jìn)程 A 給進(jìn)程 B 發(fā)了一條消息，然后進(jìn)程 A 阻塞直到進(jìn)程 B 返回響應(yīng)。假設(shè)請(qǐng)求消息丟失了，那么進(jìn)程 A 在一直等著回復(fù)，進(jìn)程 B 也會(huì)阻塞等待請(qǐng)求消息到來，這時(shí)候就產(chǎn)生死鎖。

盡管會(huì)產(chǎn)生死鎖，但是這并不是一個(gè)資源死鎖，因?yàn)?A 并沒有占據(jù) B 的資源。事實(shí)上，通信死鎖并沒有完全可見的資源。根據(jù)死鎖的定義來說：每個(gè)進(jìn)程因?yàn)榈却渌M(jìn)程引起的事件而產(chǎn)生阻塞，這就是一種死鎖。相較于最常見的通信死鎖，我們把上面這種情況稱為通信死鎖(communication deadlock)。

通信死鎖不能通過調(diào)度的方式來避免，但是可以使用通信中一個(gè)非常重要的概念來避免：超時(shí)(timeout)。在通信過程中，只要一個(gè)信息被發(fā)出后，發(fā)送者就會(huì)啟動(dòng)一個(gè)定時(shí)器，定時(shí)器會(huì)記錄消息的超時(shí)時(shí)間，如果超時(shí)時(shí)間到了但是消息還沒有返回，就會(huì)認(rèn)為消息已經(jīng)丟失并重新發(fā)送，通過這種方式，可以避免通信死鎖。

但是并非所有網(wǎng)絡(luò)通信發(fā)生的死鎖都是通信死鎖，也存在資源死鎖，下面就是一個(gè)典型的資源死鎖。

當(dāng)一個(gè)數(shù)據(jù)包從主機(jī)進(jìn)入路由器時(shí)，會(huì)被放入一個(gè)緩沖區(qū)，然后再傳輸?shù)搅硗庖粋€(gè)路由器，再到另一個(gè)，以此類推直到目的地。緩沖區(qū)都是資源并且數(shù)量有限。如下圖所示，每個(gè)路由器都有 10 個(gè)緩沖區(qū)（實(shí)際上有很多）。

假如路由器 A 的所有數(shù)據(jù)需要發(fā)送到 B ，B 的所有數(shù)據(jù)包需要發(fā)送到 D，然后 D 的所有數(shù)據(jù)包需要發(fā)送到 A 。沒有數(shù)據(jù)包可以移動(dòng)，因?yàn)樵诹硪欢藳]有緩沖區(qū)可用，這就是一個(gè)典型的資源死鎖。

活鎖

你會(huì)發(fā)現(xiàn)一個(gè)很有意思的事情，死鎖就跟榆木腦袋一樣，不會(huì)轉(zhuǎn)彎。我看過古代的一則故事：

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

某些情況下，當(dāng)進(jìn)程意識(shí)到它不能獲取所需要的下一個(gè)鎖時(shí)，就會(huì)嘗試禮貌的釋放已經(jīng)獲得的鎖，然后等待非常短的時(shí)間再次嘗試獲取?？梢韵胂褚幌逻@個(gè)場(chǎng)景：當(dāng)兩個(gè)人在狹路相逢的時(shí)候，都想給對(duì)方讓路，相同的步調(diào)會(huì)導(dǎo)致雙方都無法前進(jìn)。

現(xiàn)在假想有一對(duì)并行的進(jìn)程用到了兩個(gè)資源。它們分別嘗試獲取另一個(gè)鎖失敗后，兩個(gè)進(jìn)程都會(huì)釋放自己持有的鎖，再次進(jìn)行嘗試，這個(gè)過程會(huì)一直進(jìn)行重復(fù)。很明顯，這個(gè)過程中沒有進(jìn)程阻塞，但是進(jìn)程仍然不會(huì)向下執(zhí)行，這種狀況我們稱之為 活鎖(livelock)。

饑餓

與死鎖和活鎖的一個(gè)非常相似的問題是 饑餓(starvvation)。想象一下你什么時(shí)候會(huì)餓？一段時(shí)間不吃東西是不是會(huì)餓？對(duì)于進(jìn)程來講，最重要的就是資源，如果一段時(shí)間沒有獲得資源，那么進(jìn)程會(huì)產(chǎn)生饑餓，這些進(jìn)程會(huì)永遠(yuǎn)得不到服務(wù)。

我們假設(shè)打印機(jī)的分配方案是每次都會(huì)分配給最小文件的進(jìn)程，那么要打印大文件的進(jìn)程會(huì)永遠(yuǎn)得不到服務(wù)，導(dǎo)致進(jìn)程饑餓，進(jìn)程會(huì)無限制的推后，雖然它沒有阻塞。

總結(jié)

死鎖是一類通用問題，任何操作系統(tǒng)都會(huì)產(chǎn)生死鎖。當(dāng)每一組進(jìn)程中的每個(gè)進(jìn)程都因等待由該組的其他進(jìn)程所占有的資源而導(dǎo)致阻塞，死鎖就發(fā)生了。這種情況會(huì)使所有的進(jìn)程都處于無限等待的狀態(tài)。

死鎖的檢測(cè)和避免可以通過安全和不安全狀態(tài)來判斷，其中一個(gè)檢測(cè)方式就是銀行家算法；當(dāng)然你也可以使用鴕鳥算法對(duì)死鎖置之不理，但是你肯定會(huì)遭其反噬。

也可以在設(shè)計(jì)時(shí)通過系統(tǒng)結(jié)構(gòu)的角度來避免死鎖，這樣能夠預(yù)防死鎖；也可以破壞死鎖的四個(gè)條件來破壞死鎖。資源死鎖并不是唯一性的死鎖，還有通信間死鎖，可以設(shè)置適當(dāng)?shù)某瑫r(shí)時(shí)間來完成。

活鎖和死鎖的問題有些相似，它們都是一種進(jìn)程無法繼續(xù)向下執(zhí)行的狀態(tài)。由于進(jìn)程調(diào)度策略導(dǎo)致嘗試獲取進(jìn)程的一方永遠(yuǎn)無法獲得資源后，進(jìn)程會(huì)導(dǎo)致饑餓的出現(xiàn)。

以上就是死鎖詳解的詳細(xì)內(nèi)容，更多關(guān)于死鎖的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論