開篇

死鎖是操作系統(tǒng)中的重要概念，和操作系統(tǒng)中的其他重要概念一樣，對它的正確理解將幫助你寫出更加高效、優(yōu)秀的程序。

這里沒有晦澀的定義，只有易懂的描述和生動(dòng)的例子。相信你看了之后會(huì)有所收獲。

什么是死鎖

簡單的說，死鎖就是電腦里的硬件資源或者軟件資源不夠用了。

為什么會(huì)有這種情況呢？比如說A占有資源m，請求資源n。B占有資源n請求資源m。進(jìn)程A和B都會(huì)因?yàn)檎埱蟛坏阶约旱馁Y源而睡眠。

下面將進(jìn)一步介紹。

更形象的描述-死鎖建模：

為了能對死鎖進(jìn)行更好的分析，我們?yōu)樗梨i建模。就是用一個(gè)有向圖來表示進(jìn)程和資源的使用情況，圓形節(jié)點(diǎn)表示進(jìn)程，方形節(jié)點(diǎn)表示資源。

資源指向進(jìn)程的邊表示該進(jìn)程占有該資源，進(jìn)程指向資源表示進(jìn)程請求分配資源。

如圖： 

 

 

a): 進(jìn)程A占有資源R。b)進(jìn)程B申請資源S。

c):進(jìn)程D占有資源T，申請資源U

　 進(jìn)程C占有資源U，申請資源T。

如上c) 出現(xiàn)死鎖。進(jìn)程C等待著資源T，資源T被進(jìn)程D占有，進(jìn)程D有等待進(jìn)程C占有的資源U。這樣兩個(gè)進(jìn)程就這么等待下去。

死鎖的定義

有了上面的基礎(chǔ)，現(xiàn)在來看死鎖的規(guī)范定義：

A set of processes is deadlocked if each process in the set is waiting for an
event that only another process in the set can cause.

一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只有該進(jìn)程集合中的進(jìn)程才能引發(fā)的事件

死鎖產(chǎn)生的條件：

1、互斥條件：每個(gè)資源要么已經(jīng)分配給一個(gè)進(jìn)程，要么是可用的。

2、占有和等待條件:已經(jīng)占有資源的進(jìn)程可以申請其他資源。

3、不可搶占條件：已經(jīng)被占有的資源不能被其他的進(jìn)程搶占， 只有占有它的進(jìn)程才能顯示釋放。

4、環(huán)路等待條件：死鎖發(fā)生時(shí)，系統(tǒng)中有兩個(gè)或兩個(gè)以上的進(jìn)程一條環(huán)路，該環(huán)路中的每一個(gè)進(jìn)程都在等待下一個(gè)進(jìn)程所占有的資源。

　　死鎖發(fā)生時(shí)，以上的四個(gè)條件必須同時(shí)滿足，如果有其中的一個(gè)條件不滿足，死鎖就不會(huì)發(fā)生。

那么 ，只要讓上面的條件不滿足就能避免死鎖的發(fā)生了嗎？是的，這將在下文死鎖的預(yù)防中討論.

死鎖的檢測

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

通過上面的描述，應(yīng)該對死鎖有了一些認(rèn)識(shí)了吧。那么，如何檢測一個(gè)進(jìn)程集合中是否會(huì)存在死鎖呢？

有了上面的經(jīng)驗(yàn)，只要吧進(jìn)程集合中的每個(gè)進(jìn)程和各自占有和請求的資源用剛才的死鎖建模表示出來，然后再判斷，如果存在圈，

就能證明里面有死鎖的存在了。 

用實(shí)例能更好的說明問題：里面有A到G七個(gè)進(jìn)程，R到W六中資源；

1、進(jìn)程A占有資源R，請求資源S

2、進(jìn)程B不占有任何資源，請求資源T

3、進(jìn)程C不占任何資源，請求資源S

4、D占有資源U，請求資源S和T

5、E有資源T，請求資源V

6、F有資源W，請求資源S

7、G有資源V，需要資源U

 以上進(jìn)程集合和資源的關(guān)系可用下圖表示：

很直觀的，就能看到圖中存在一個(gè)圈，所以存在死鎖。

還是簡單的分析下吧 ：從D點(diǎn)入手，D需要T，T被E占有，E需要V，V被G占有，G需要U，U被D占有。圈里的每個(gè)進(jìn)程都在等待他的下一個(gè)

所占有的資源，所有的進(jìn)程就無限的等待下去。顯然， 上述進(jìn)程集合發(fā)生了死鎖。

所以對于這種情況，可以記錄下進(jìn)程集合中各個(gè)進(jìn)程和資源的關(guān)系，通過判斷圖中是否存在圈的方法來檢測是否存在死鎖。

判斷圖中是否存在圈可以用圖的深度優(yōu)先搜索來實(shí)現(xiàn)，可以參考前面的博文：圖的深度優(yōu)先搜索詳解/Depth-first search/C++

大家可能已經(jīng)注意到了，從開始到現(xiàn)在我們討論的資源都有一個(gè)特點(diǎn)，就是每一種類型的資源只有一個(gè)。如上面的例子中，資源R只有1個(gè)，

S也是一樣只有一個(gè)。對于計(jì)算機(jī)中的某些資源，某些資源可能確實(shí)只有一個(gè)，比如打印機(jī)，掃描儀等等，而還有很多類型的資源，可以存在多個(gè)。比如內(nèi)存空間，寄存器等。

剛才分析了每種類型資源只有一個(gè)的死鎖的情況，下面看每種類型資源有多個(gè)的情況:

每種類型多個(gè)資源的死鎖檢測：

對于這種情況，就需要另外的一種表示方法了。對于任何問題的分析，總是要先把它表述出來。

下面對資源和進(jìn)程分開討論；

資源：

對于一個(gè)資源，它要么被某個(gè)進(jìn)程占有，要么可以被申請占有。這里假設(shè)資源類型編號為1、2、、、、m的資源。

資源的總數(shù)用E1，E2、、、Em來表示

剩余的資源用A1，A2、、、Am來表示 

比如資源類型E2表示掃描儀，那么E2=1就表示系統(tǒng)中有一臺(tái)掃描儀。A2=0表示剩余的掃描儀為0；

進(jìn)程：假設(shè)進(jìn)程集合中有編號為1、2、、、、n的進(jìn)程。

由于我們考慮的是死鎖，對于一個(gè)進(jìn)程，我們要記錄的是它占有的資源，它需要的資源。

這里用兩個(gè)矩陣表示：Cij 的值表示進(jìn)程i占有資源j的數(shù)目。Rij表示進(jìn)程i需要資源j的個(gè)數(shù)；

參見下圖：

每種資源的總數(shù)=已被進(jìn)程占有的數(shù)量+剩余數(shù)量     根據(jù)上圖，用數(shù)學(xué)表達(dá)式表述為：

 對于任意的一個(gè)進(jìn)程 i 如果Ri1,Ri2、、、Rim都小于對應(yīng)的A1，A2、、、、Am，說明這個(gè)進(jìn)程可以被執(zhí)行，所以可以先看進(jìn)程集合里面有沒有這中可以被執(zhí)行的進(jìn)程，讓他們執(zhí)行，完成后釋放所占有的資源。這時(shí)候剩余資源變多了，在判斷進(jìn)程集合中是否還有可以被執(zhí)行的進(jìn)程，如果有，就執(zhí)行，然后釋放資源。重復(fù)以上過程，如果最后進(jìn)程集合中所有進(jìn)程都被執(zhí)行了，說明不存在死鎖，反之，如果最后進(jìn)程集合中還有不能被執(zhí)行的進(jìn)程，那么進(jìn)程集合存在死鎖。光說理論太枯燥了，而且不容易理解。下面用實(shí)例說話;

先看資源和進(jìn)程的狀態(tài)圖吧：

圖中共有四種資源，總數(shù)和剩余數(shù)量分別用E和A表示出來了

共有3個(gè)進(jìn)程，他們占有的資源和需要的資源分別用矩陣C和R表示。

進(jìn)程1：需要第一種資源2個(gè)，第四種資源1個(gè)，而第四資源沒有了，所以進(jìn)程1不能被先執(zhí)行。

進(jìn)程2：需要第一種資源1個(gè)，第三種資源1個(gè)，剩余資源也不能滿足需要，所以不能執(zhí)行。

進(jìn)程3：需要第一種資源2個(gè)，第二種資源1個(gè)，剩余資源可滿足請求，所以進(jìn)程3執(zhí)行。

進(jìn)程3執(zhí)行后，釋放占有資源。更新A:(2,2,2,0),這時(shí)進(jìn)程2可以執(zhí)行了，繼而進(jìn)程1也能執(zhí)行 ，所以該進(jìn)程集合不存在死鎖。

假如圖中情況有所改變，進(jìn)程2需要第四種資源1個(gè)，資源二1個(gè)和資源一兩個(gè)，那么所有的請求都得不到滿足，系統(tǒng)進(jìn)入死鎖。

 

這篇博文主要闡述了死鎖的定義和死鎖的檢測、

死鎖的恢復(fù)、死鎖的避免、死鎖的預(yù)防將在下一篇博文中闡述。