目錄

• 1 死鎖的基本概念
• 2 死鎖的必要條件
• 3 死鎖預(yù)防
• • 3.1 抑制死鎖發(fā)生的必要條件
• 4 死鎖避免
• • 4.1 資源分配圖法
  • 4.2 銀行家算法
• 5 死鎖的檢測
• • 5.1 每一種資源類型只有一個實例
  • 5.2 一個資源類型的多個實例
  • 5.3 處理死鎖

1 死鎖的基本概念

死鎖 (Deadlock) 指的是計算機(jī)系統(tǒng)中多道程序并發(fā)執(zhí)行時，兩個或兩個以上的進(jìn)程由于競爭資源而造成的一種互相等待的現(xiàn)象（僵局），如無外力作用，這些進(jìn)程將永遠(yuǎn)不能再向前推進(jìn)。

下面是一個現(xiàn)實中過橋的例子，如圖所示橋比較窄，只能同時通過一輛車，此時有兩輛車面對面都想要通過橋，而兩輛車互不相讓，導(dǎo)致都無法通過，這就是現(xiàn)實中“死鎖”的例子。我們可以把橋看作是資源，對于車來說是共享的，當(dāng)死鎖發(fā)生時，要解決死鎖其中一種解決方法是讓其中某輛車后退，現(xiàn)假設(shè)讓右邊的車后退，則它后面的所有車都要后退，若每次都是右邊的車讓道的話，右邊有些車就一直不能通行，就會造成饑餓現(xiàn)象。

死鎖現(xiàn)象產(chǎn)生的本質(zhì)就是供小于求，也就是資源滿足不了進(jìn)程的需求，每一個進(jìn)程如下的利用資源：

• 申請 (Request)： 如果申請不能立即被允許，那么進(jìn)程必須等待直到能獲取資源。（通過系統(tǒng)調(diào)用或者信號量來進(jìn)行資源的申請和釋放）；
• 使用 (Use)： 進(jìn)程使用資源進(jìn)行相關(guān)操作；
• 釋放 (Release) ：進(jìn)程釋放資源。

---

除了對資源的競爭會產(chǎn)生死鎖外，P，V操作順序的不當(dāng)也會產(chǎn)生死鎖，如現(xiàn)有進(jìn)程 $P_0$ 和 $P_1$，他們都要申請信號量A和信號量B，他們的操作如下表：

時間$P_0$$P_1$

$t_1$	wait(A);	wait(B);
$t_2$	wait(B);	wait(A);

在 $t_1$ 時刻，$P_0$ 和 $P_1$ 分別申請了信號量A和信號量B，那么在$t_2$時刻由于信號量B已經(jīng)被$P_1$申請，所以$P_0$申請不到信號量B，同理$P_1$也申請不到信號量A，這時就發(fā)生了死鎖。

總結(jié)來說，產(chǎn)生死鎖的原因如下：

• 競爭資源引起死鎖：當(dāng)系統(tǒng)中供多個進(jìn)程所使用的資源，不足以同時滿足它們的需要時，引起它們對資源的競爭而產(chǎn)生死鎖；
• 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖：在多道程序系統(tǒng)中，并發(fā)執(zhí)行的進(jìn)程推進(jìn)序列不可預(yù)測，有些推進(jìn)順序，進(jìn)程可以順利完成，有的推進(jìn)順序會引起進(jìn)程無限期地等待永遠(yuǎn)不會發(fā)生的條件而不能向前推進(jìn)，造成死鎖。

2 死鎖的必要條件

死鎖的產(chǎn)生是有必要條件的，當(dāng)下面四個條件同時出現(xiàn)，死鎖將會發(fā)生：

互斥 (Mutual exclusion)：一次只有一個進(jìn)程可以使用一個資源，因為有些資源的使用是必須獨占的；

占有并等待 (Hold and wait)：一個至少持有一個資源的進(jìn)程等待獲得額外的由其他進(jìn)程所持有的資源，又叫請求與保持；

不可搶占 (No preemption)：一個資源只有當(dāng)持有它的進(jìn)程完成任務(wù)后才自由的釋放，也就是非剝奪。若可以搶占的話，別的進(jìn)程需要某個資源可以直接搶，就不存在死鎖問題了；

環(huán)路等待 (Circular wait)：等待資源的進(jìn)程之間存在環(huán)，舉個例子來說進(jìn)程1要獲得進(jìn)程2手中的資源才能執(zhí)行結(jié)束，進(jìn)程2要獲得進(jìn)程3手中的資源才能運行結(jié)束，進(jìn)程3要獲得進(jìn)程1手中的資源才能運行結(jié)束，這樣就形成了一個等待環(huán)，誰也無法運行結(jié)束離開這個環(huán)。

---

死鎖指的是一組進(jìn)程對一組資源使用時的某種狀態(tài)，那么描述這個狀態(tài)有如下參數(shù)：

• 資源類型：可以用 $R$ 來表示，如 $R_1$，$R_2$，$R_3$ 表示CPU 周期，內(nèi)存空間， I/O 設(shè)備；
• 實例：每個資源可能有多個實例，用 $W$ 表示；
• 進(jìn)程：用 $P$ 來表示。

此時狀態(tài)就可以用資源分配圖來表示，在數(shù)據(jù)結(jié)構(gòu)中，圖是由一組頂點的集合V和邊的集合E組成，在資源分配圖中有兩種類型的節(jié)點：

• P：系統(tǒng)中全部的進(jìn)程構(gòu)成的節(jié)點；
• R：系統(tǒng)中全部的資源構(gòu)成的節(jié)點。

進(jìn)程和資源之間的邊也存在著兩種邊：

• 請求邊：即某個進(jìn)程 $P_i$ 要請求某個資源 $R_j$ 的邊，箭頭是從進(jìn)程指向資源；
• 分配邊：即某個資源 $R_j$ 已經(jīng)被分配給某個進(jìn)程 $P_i$ 的邊，箭頭是從資源指向進(jìn)程。

可以把進(jìn)程表示為圓點，把資源表示成方形，把資源中的實例表示為更小的方形，如下圖所示：

上述兩種邊就可以表示為如下形式：

有了上面的方法就可以方便的描述進(jìn)程和資源的分配關(guān)系，如某時刻的關(guān)系如下圖所示：

從資源分配圖中，可以得出如下結(jié)論：

• 如果圖沒有環(huán)，那么不會有死鎖；
• 如果圖有環(huán)，若每一種資源類型只有一個實例，那么一定會死鎖。若每種資源類型有多個實例，可能死鎖。

3 死鎖預(yù)防

處理死鎖有忽略、預(yù)防、避免、檢測、解除五種措施，對于忽略，即假裝系統(tǒng)中從未出現(xiàn)過死鎖。這個方法被大部分的操作系統(tǒng)采用，包括 UNIX 中的鴕鳥策略。預(yù)防死鎖，避免死鎖則是確保系統(tǒng)永遠(yuǎn)不會進(jìn)入死鎖狀態(tài)。死鎖檢測和解除則是允許系統(tǒng)進(jìn)入死鎖狀態(tài)，然后恢復(fù)系統(tǒng)。

鴕鳥策略：鴕鳥都遇到危險時會將頭埋在沙子里，這里比喻像鴕鳥一樣對死鎖視而不見，因為處理死鎖的代價很大，而且常常給用戶帶來許多不便的限制，大多數(shù)用戶寧可在極偶然的情況下發(fā)生死鎖，也不愿限制每個用戶只能創(chuàng)建一個進(jìn)程、只能打開一個文件等等，于是不得不在方便性和正確性之間作出折衷。

3.1 抑制死鎖發(fā)生的必要條件

對于互斥條件來講，是不可以打破的，因為在某些條件下，必須互斥訪問，詳細(xì)內(nèi)容可以參考我的這篇文章 操作系統(tǒng)原理第六章：進(jìn)程同步。

對于占有并等待條件，要打破這個條件的話必須保證進(jìn)程申請資源的時候沒有占有其他資源，要做到這一點有如下兩種方式：

• 要求進(jìn)程在執(zhí)行前一次申請全部的資源，這樣的話后續(xù)就不會再有資源的申請了；
• 沒有資源時，可以申請資源。在申請更多其它資源之前，需要釋放已有資源。

實際上這兩種方法都是代價不小的，比如第一種方法，進(jìn)程使用資源不是一次性全部使用的，而是有次序的使用的，這樣就導(dǎo)致某些資源明明現(xiàn)在用不到，卻占有著，而其他著急使用該資源的進(jìn)程要等待。

對于非搶占式，打破這個條件就是運行搶占，搶占的方式是如果一個進(jìn)程的申請沒有實現(xiàn)，它要釋放所有占有的資源，搶占的資源放入進(jìn)程等待資源列表中，只有進(jìn)程能夠重新得到舊的資源和新申請的資源時，才可以重新開始。

對于環(huán)路等待條件，打破這個條件可以將所有的資源類型放入資源列表中，并且要求進(jìn)程按照資源表申請資源，也就是把每個資源編個號，所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的次序提出，如已經(jīng)申請了1號資源CPU和2號資源打印機(jī)，那么后面再申請資源必須按次序3、4、5等等。總有一個進(jìn)程占據(jù)了較高序號的資源，它繼續(xù)請求的資源必然是空閑的，可以一直向前推進(jìn)。在資源分配圖中不可能出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件，這種策略可以提高資源利用率，但在進(jìn)程使用各類資源的順序與系統(tǒng)規(guī)定的順序不同時會造成資源浪費的情況。

總結(jié)來說上述預(yù)防死鎖的方法通過限制資源請求來打破死鎖的四個必要條件之一，從而預(yù)防死鎖的發(fā)生，但可能帶來副作用，如降低設(shè)備利用率和吞吐量，可能有進(jìn)程饑餓等。

4 死鎖避免

死鎖避免不會去限制資源的使用，而是允許進(jìn)程動態(tài)地申請資源，但在系統(tǒng)進(jìn)行資源分配之前，先計算資源分配的安全性，若此次分配不會導(dǎo)致系統(tǒng)從安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換，便可將資源分配給進(jìn)程；否則不分配資源，進(jìn)程必須阻塞等待。

安全狀態(tài)是指系統(tǒng)的一種狀態(tài)，在此狀態(tài)下，系統(tǒng)能按某種順序（例如 $P_1$，$P_1$，…，$P_n$）來為各個進(jìn)程分配其所需資源，直至最大需求，使每個進(jìn)程都可順序地一個個地完成。這個序列（$P_1$，$P_1$，…，$P_n$）稱為安全序列。 如果存在一個安全序列系統(tǒng)處于安全態(tài)，若某一時刻不存在一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。

死鎖屬于不安全狀態(tài)，是不安全狀態(tài)的一個子集，它們之間關(guān)系如下圖所示：

如果一個系統(tǒng)在安全狀態(tài)，就沒有死鎖；如果系統(tǒng)死鎖，則處于不安全狀態(tài)；如果一個系統(tǒng)處于不安全狀態(tài)，就有可能死鎖；那么既然要避免死鎖，那就要避免系統(tǒng)進(jìn)入不安全狀態(tài)。

避免死鎖有兩種常用方式：

• 當(dāng)資源有單個實例的時候，可以用之前提到的資源分配圖來實現(xiàn)，若圖中出現(xiàn)了環(huán)，這表示出現(xiàn)了死鎖，那么可以檢測資源分配圖判斷是否有環(huán)來避免死鎖；
• 當(dāng)資源有多個實例的時候，使用銀行家算法，第五節(jié)會詳細(xì)介紹。

4.1 資源分配圖法

在第二節(jié)也提到過資源分配圖，在用資源分配圖法避免死鎖時，添加了一條新的邊叫做需求邊，即表示進(jìn)程 $P_i$ 可能會申請到資源 $R_j$，箭頭從進(jìn)程指向資源，但是箭頭圖形為虛線。當(dāng)一個進(jìn)程申請資源的時候，需求邊轉(zhuǎn)化為請求邊；當(dāng)資源被進(jìn)程釋放的時候，分配邊轉(zhuǎn)化為需求邊；當(dāng)然系統(tǒng)中的資源必須被事先聲明。

用資源分配圖法來避免死鎖的過程如下，當(dāng)進(jìn)程 $P_i$ 申請資源 $R_j$ 時，把圖中的所有需求邊轉(zhuǎn)換為分配邊，看圖中是否出現(xiàn)環(huán)路，只有不出現(xiàn)環(huán)路，才實施資源分配，如下圖：

4.2 銀行家算法

在現(xiàn)實世界中，銀行的利益方式之一是提供貸款，當(dāng)銀行給某人提供貸款時，會考查他是否有能力償還貸款，以此來判斷貸出去的這筆錢是否是安全的。那么銀行家算法就是借助這個思想，當(dāng)某個進(jìn)程需要分配資源的時候，操作系統(tǒng)會判斷這個進(jìn)程能不能把資源安全的歸還，如果可以的話操作系統(tǒng)就分配，否則不分配。

銀行家算法適用于多個實例的情況，每一個進(jìn)程必須事先聲明使用的最大量，當(dāng)一個進(jìn)程請求資源 ， 它可能要等待，當(dāng)一個進(jìn)程得到所有的資源，它必須在有限的時間釋放它們。

---

在實現(xiàn)銀行家算法時，需要定義如下的參數(shù)：

• n 為進(jìn)程的數(shù)目，m 為資源類型的數(shù)目；
• Available：系統(tǒng)中有多少個可用資源，由于銀行家算法用在多實例中，則如果 available[ j ]=k，表示資源 $R_j$ 有 k 個實例有效；
• Max：每個進(jìn)程最多需要請求的資源個數(shù)，如果 Max[ i, j ]=k，那么進(jìn)程 $P_i$ 可以最多請求資源 $R_j$ 的 k 個實例；
• Allocation：每個進(jìn)程已經(jīng)分配了多少資源，如果 Allocation[ i, j ]=k，那么進(jìn)程 $P_i$ 當(dāng)前分配了 k 個資源 $R_j$ 的實例；
• Need：每個進(jìn)程還需要多少資源，如果 Need[ i, j ]=k，那么進(jìn)程 $P_i$ 還需要 k 個資源 $R_j$ 的實例。上面幾個參數(shù)也存在這樣的關(guān)系：Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]，表示還需要的等于最多需要的減去已經(jīng)擁有的；
• Request：進(jìn)程當(dāng)前要申請多少資源，如果 Request[ i, j ]=k，那么進(jìn)程 $P_i$ 現(xiàn)在想申請 k 個資源 $R_j$ 的實例。

---

銀行家算法具體的實現(xiàn)過程如下：

若 Request <= Need，執(zhí)行下一步，否則不執(zhí)行，意思是進(jìn)程當(dāng)前想申請的資源必須是小于它實際所需要的，不能超出實際所需要的；

若 Request <= Available，執(zhí)行下一步，意思是當(dāng)前申請的資源數(shù)量，系統(tǒng)是否可以滿足，若滿足不了，則需要等待，直到系統(tǒng)可以滿足為止；

試著去給該進(jìn)程分配資源，會執(zhí)行如下操作 Available=Available-Request，Allocation=Allocation+Request，Need=Need-Request；

用安全算法檢查，看系統(tǒng)是否處于安全狀態(tài)，如果安全就分配資源，否則不分配并讓之前執(zhí)行的三個操作回到原來狀態(tài)。

---

在安全算法中，有兩個參數(shù)：

• Work：Work=Available 表示當(dāng)前系統(tǒng)中可提供資源的數(shù)量；
• Finish：它為一個布爾變量，描述進(jìn)程是否執(zhí)行結(jié)束，如 Finish[ i ]=false 表示進(jìn)程 $P_i$ 還沒有執(zhí)行結(jié)束或還沒有執(zhí)行。

在進(jìn)程序列中，若進(jìn)程 $P_i$ 滿足如下條件：

• Finish[ i ]=false，這個進(jìn)程還沒執(zhí)行完；
• Need <= Work，進(jìn)程 $P_i$ 所需的資源數(shù)量是小于系統(tǒng)可用資源數(shù)量的，換句話說就是系統(tǒng)是可以滿足該進(jìn)程的需求的。

則執(zhí)行 Work=Work+Allocation，Finish[ i ]=true，這兩句的意思是進(jìn)程 $P_i$ 執(zhí)行完后把它的 Allocation 給釋放掉，然后標(biāo)明 Finish 為已經(jīng)執(zhí)行完。然后按照該步驟依次檢查所有的進(jìn)程，如果最后所有進(jìn)程的 Finish 都為 true 則代表所有進(jìn)程都能順利結(jié)束，那么說明系統(tǒng)為安全狀態(tài)。

---

銀行家算法舉例：現(xiàn)假設(shè)有五個進(jìn)程 $P_0$ ~ $P_4$，三個資源類型A（10個實例），B（5個實例），C（7個實例），下表是在 $T_0$ 時刻系統(tǒng)的狀態(tài)：

進(jìn)程Allocation（已分配）Max（總需求）Available（當(dāng)前可分配）

	A B C	A B C	A B C
$P_0$	0 1 0	7 5 3	3 3 2
$P_1$	2 0 0	3 2 2
$P_2$	3 0 2	9 0 2
$P_3$	2 1 1	2 2 2
$P_4$	0 0 2	4 3 3

要判斷當(dāng)前是否處于安全狀態(tài)，要計算 Need，如下表：

進(jìn)程N(yùn)eed（還需的資源數(shù)）=Max-Allocation

	A B C
$P_0$	7 4 3
$P_1$	1 2 2
$P_2$	6 0 0
$P_3$	0 1 1
$P_4$	4 3 1

此時使用安全算法來驗證是否有安全序列，初始條件下 Work = available = (3，3，2)，Finish[ i ]=false (i=0..4)：

進(jìn)程WorkNeedAllocationFinish

	A B C	A B C	A B C	T/F
$P_1$	3 3 2	1 2 2	2 0 0	T
$P_3$	5 3 2	0 1 1	2 1 1	T
$P_4$	7 4 3	4 3 1	0 0 2	T
$P_2$	7 4 5	6 0 0	3 0 2	T
$P_0$	10 4 7	7 4 3	0 1 0	T

所以存在安全序列（$P_1$，$P_3$，$P_4$，$P_2$，$P_0$），系統(tǒng)處于安全狀態(tài)。

注意：安全序列有時不是唯一的，但只要找到一個，就認(rèn)為系統(tǒng)是安全的。

5 死鎖的檢測

死鎖的檢測分為兩種情況，一種是每一種資源類型只有一個實例，另一種是一個資源類型的多個實例。

5.1 每一種資源類型只有一個實例

通過把資源分配圖轉(zhuǎn)換成維護(hù)等待圖，來看維護(hù)等待圖中是否出現(xiàn)了環(huán)來看當(dāng)前系統(tǒng)是否出現(xiàn)了死鎖。在維護(hù)等待圖中只有一種節(jié)點就是進(jìn)程，若進(jìn)程 $P_i$ 指向進(jìn)程 $P_j$，則表示 $P_i$ 在等待 $P_j$，如下圖左邊為資源分配圖，右邊為轉(zhuǎn)換的維護(hù)等待圖：

可以發(fā)現(xiàn)維護(hù)等待圖中是存在環(huán)的，所以表明當(dāng)前系統(tǒng)出現(xiàn)死鎖了。

5.2 一個資源類型的多個實例

這里用到的算法叫做死鎖檢測算法，類似于之前講過的安全算法，死鎖檢測算法定義了如下參數(shù)：

• Available：每種資源可用的資源數(shù)量；
• Allocation：每個進(jìn)程已經(jīng)分配的資源數(shù)量；
• Request：進(jìn)程請求的資源數(shù)量。
• Work：Work = Available；
• Finish：這里的Finish和之前的安全算法有所不同，這里當(dāng) Allocation != 0 則 Finish = false 否則 Finish = true ，也就是若某進(jìn)程的 Allocation = 0 時說明這個進(jìn)程沒有被分配到資源，也就這個進(jìn)程是不參與死鎖的，所以 Finish = true 。

找到某進(jìn)程滿足如下條件：

• Finish = false；
• Request <= Work：當(dāng)前請求的資源數(shù)量小于系統(tǒng)可分配資源的數(shù)量；

該進(jìn)程能執(zhí)行結(jié)束，執(zhí)行結(jié)束后執(zhí)行 Work = Work + Allocation， Finish = true，也就是把資源給釋放掉，把所有的進(jìn)程按如上操作遍歷結(jié)束后檢查會不會有一個進(jìn)程的 Finish = false ，也就是某個進(jìn)程無法結(jié)束，那么就發(fā)生了死鎖，并且可以根據(jù) Finish 的下標(biāo)找到是哪一個進(jìn)程發(fā)生了死鎖。

---

檢測死鎖算法的例子：現(xiàn)假設(shè)有五個進(jìn)程 $P_0$ ~ $P_4$，三個資源類型A（7個實例），B（2個實例），C（6個實例），下表是在 $T_0$ 時刻系統(tǒng)的狀態(tài)：

進(jìn)程Allocation（已分配）Request（當(dāng)前請求）Available（當(dāng)前可分配）

	A B C	A B C	A B C
$P_0$	0 1 0	0 0 0	0 0 0
$P_1$	2 0 0	2 0 2
$P_2$	3 0 3	0 0 0
$P_3$	2 1 1	1 0 0
$P_4$	0 0 2	0 0 2

所以存在安全序列（$P_0$，$P_2$，$P_3$，$P_1$，$P_4$），當(dāng)前是沒有死鎖的。

現(xiàn)在假設(shè)進(jìn)程 $P_2$ 請求 C 的一個實例，如下表：

進(jìn)程Request（當(dāng)前請求）

	A B C
$P_0$	0 0 0
$P_1$	2 0 1
$P_2$	0 0 1
$P_3$	1 0 0
$P_4$	0 0 2

此時可以歸還 $P_0$ 所有的資源，但是資源不夠完成其他進(jìn)程的請求，所以死鎖存在，包括進(jìn)程 $P_1$，$P_2$，$P_3$，$P_4$。

5.3 處理死鎖

當(dāng)系統(tǒng)出現(xiàn)死鎖，通常有如下三種方式：

• 操作員人工處理
• 進(jìn)程終止
• 資源搶占

其中進(jìn)程終止和資源搶占是由操作系統(tǒng)來完成的，進(jìn)程終止的方法如下：

• 終止所有的死鎖進(jìn)程；
• 一次終止一個進(jìn)程直到死鎖環(huán)消失；
• 選擇終止順序，比如按照進(jìn)程的優(yōu)先級來終止，先終止優(yōu)先級低的進(jìn)程，或者按照進(jìn)程計算了多少時間，還需要多長時間來選擇終止。

資源搶占的方法如下：

• 選擇一個犧牲品：最小化代價；
• 回退：返回到安全的狀態(tài)，然后重新開始進(jìn)程；

但是會造成饑餓，因為同一個進(jìn)程可能總是被選中，包括在回退時。

總結(jié)

以上是生活随笔為你收集整理的操作系统原理第七章：死锁的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。