死鎖的概念以及産生死鎖的原因

一、死鎖的定義

在多道程式系統中，由于多個程序的并發執行，改善了系統資源的使用率并提高了系統 的處理能力。然而，多個程序的并發執行也帶來了新的問題——死鎖。所謂死鎖是指多個進 程因競争資源而造成的一種僵局（互相等待），若無外力作用，這些程序都将無法向前推進。

下面我們通過一些執行個體來說明死鎖現象。

先看生活中的一個執行個體，在一條河上有一座橋，橋面很窄，隻能容納一輛汽車通行。如 果有兩輛汽車分别從橋的左右兩端駛上該橋，則會出現下述的沖突情況。此時，左邊的汽車 占有了橋面左邊的一段，要想過橋還需等待右邊的汽車讓出橋面右邊的一段；右邊的汽車占 有了橋面右邊的一段，要想過橋還需等待左邊的汽車讓出橋面左邊的一段。此時，若左右兩 邊的汽車都隻能向前行駛，則兩輛汽車都無法過橋。

在計算機系統中也存在類似的情況。例如，某計算機系統中隻有一台列印機和一台輸入 裝置，程序P1正占用輸入裝置，同時又提出使用列印機的請求，但此時列印機正被程序P2 所占用，而P2在未釋放列印機之前，又提出請求使用正被P1占用着的輸入裝置。這樣兩個程序互相無休止地等待下去，均無法繼續執行，此時兩個程序陷入死鎖狀态。

二、死鎖産生的原因

1) 系統資源的競争

通常系統中擁有的不可剝奪資源，其數量不足以滿足多個程序運作的需要，使得程序在 運作過程中，會因争奪資源而陷入僵局，如錄音帶機、列印機等。隻有對不可剝奪資源的競争 才可能産生死鎖，對可剝奪資源的競争是不會引起死鎖的。

2) 程序推進順序非法

程序在運作過程中，請求和釋放資源的順序不當，也同樣會導緻死鎖。例如，并發程序 P1、P2分别保持了資源R1、R2，而程序P1申請資源R2，程序P2申請資源R1時，兩者都 會因為所需資源被占用而阻塞。

信号量使用不當也會造成死鎖。程序間彼此互相等待對方發來的消息，結果也會使得這 些程序間無法繼續向前推進。例如，程序A等待程序B發的消息，程序B又在等待程序A 發的消息，可以看出程序A和B不是因為競争同一資源，而是在等待對方的資源導緻死鎖。

3) 死鎖産生的必要條件

産生死鎖必須同時滿足以下四個條件，隻要其中任一條件不成立，死鎖就不會發生。

互斥條件：程序要求對所配置設定的資源（如列印機）進行排他性控制，即在一段時間内某 資源僅為一個程序所占有。此時若有其他程序請求該資源，則請求程序隻能等待。

不剝奪條件：程序所獲得的資源在未使用完畢之前，不能被其他程序強行奪走，即隻能 由獲得該資源的程序自己來釋放（隻能是主動釋放)。

請求和保持條件：程序已經保持了至少一個資源，但又提出了新的資源請求，而該資源 已被其他程序占有，此時請求程序被阻塞，但對自己已獲得的資源保持不放。

循環等待條件：存在一種程序資源的循環等待鍊，鍊中每一個程序已獲得的資源同時被 鍊中下一個程序所請求。即存在一個處于等待狀态的程序集合{Pl, P2, ..., pn}，其中Pi等 待的資源被P(i+1)占有（i=0, 1, ..., n-1)，Pn等待的資源被P0占有，如圖2-15所示。

直覺上看，循環等待條件似乎和死鎖的定義一樣，其實不然。按死鎖定義構成等待環所 要求的條件更嚴，它要求Pi等待的資源必須由P(i+1)來滿足，而循環等待條件則無此限制。 例如，系統中有兩台輸出裝置，P0占有一台，PK占有另一台，且K不屬于集合{0, 1, ..., n}。

Pn等待一台輸出裝置，它可以從P0獲得，也可能從PK獲得。是以，雖然Pn、P0和其他 一些程序形成了循環等待圈，但PK不在圈内，若PK釋放了輸出裝置，則可打破循環等待, 如圖2-16所示。是以循環等待隻是死鎖的必要條件。

資源配置設定圖含圈而系統又不一定有死鎖的原因是同類資源數大于1。但若系統中每類資 源都隻有一個資源，則資源配置設定圖含圈就變成了系統出現死鎖的充分必要條件。

轉載位址：http://c.biancheng.net/cpp/html/2604.html