死鎖產生的必要條件，如何有效地避免死鎖

計算機系統中的死鎖：

死鎖的起因，通常源于多個進程對資源的爭奪， 不僅對不可搶占資源進行爭奪時會引起死鎖，而且對可消耗資源進行爭奪時，也會引起死鎖。

可搶占資源:

可把系統中的資源分成兩類，一類是可搶占性資源，是指某進程在獲得資源后，資源可以被其他進程或或系統搶占。例如優先級高的高的資源可以搶占優先級低的進程處理機。又可以把一個進程從一個存儲區轉移到另一個存儲區，在內存緊張時，還可將一個進程從內存調出到外存上，即搶占該進程的內存空間，即cpu和主存均屬于可搶占性資源，對于這類資源是不會引起死鎖的。

不可搶占資源:

另一類資源是不可搶占資源，即一旦系統把某資源分配給進程后，就不能將它強行收回，只能在進程用完后自行釋放，例如，當一個進程已開始刻錄光盤時，如果突然將刻錄機分配給另一個進程，其結果必然將損壞正在刻錄的光盤，因此只能等刻好光盤以后由進程自己釋放刻錄機，另外磁帶機，打印機等也屬于不可搶占資源。

1.競爭不可搶占資源引起的死鎖：

通常系統中所有的不可搶占資源其數量不足以滿足多個進程運行的需要，是的進程在運行過程中，會因爭奪資源陷入僵局，例如，系統中有兩個進程p1,p2，他們都準備寫兩個文件f1,f2，這兩者都屬于可重用和不可搶占資源，進程p1打開f1，然后再打開文件f,后打開f1,。

兩個進程在并發執行時，如果p1先打開f1和f2，然后p2再打開f1（或f2），由于文件f1或f2，由于f1（f2）已被p1打開，故p2處于會被阻塞，當p1寫完文件f1(或f2)而關閉f1(或f2時，p2就會由阻塞狀態轉為就緒狀態，被調度執行后重新打開文件f1（或f2），在這種情況下，p1和p2都能正常運行下去，。

但如果p1打開文件f1的同時，p2去打開f2，每個進程都占有一個打開的文件， 此時就可能出現問題，。因為p1試圖打開f2，p2試圖打開f1時，這兩個進程就會因都會因文件被打開而被阻塞，他們希望對方關閉自己所需要的文件，但誰也無法運行，因此兩個進程將會無限地等待下去，而形成死鎖。

2.競爭可消耗資源引起的死鎖

在利用消息通信機制進行通信時引起的死鎖情況，若m1,m2,m3是可消耗性資源，

P1:..send(p2,m1); receive(p3,m3);..

                                                  P2:..send(p3,m2); receive(p1,m1);..

                                                  P3:..send(p1,m3); receive(p2,m2);..

這三個進程都可將消息發送給下一個進程，相印地，他們也能夠接受從上一個進程發送來的消息，因此三個進程可以順利地運行下去，而不會發生死鎖，但若先執行receive操作，然后執行send操作，即按下述運行順序

p1:receive(p3,m3);..P1:..send(p2,m1)

p2:receive(p1,m1);..P2:..send(p3,m2);

                                                 p3:receive(p2,m2);....send(p1,m3);

則這三個進程將永久地阻塞他們的receive操作，等待一條永遠不會發出的消息，于是發生 了死鎖。

產生死鎖的必要條件：

（1）互斥條件。進程對所分配到的資源進行排他性使用，即在一段時間內，某資源只能被一個進程占用，如果此時還有其他進程請求該資源，則請求進程只能等待，直至占用該資源的進程用必釋放。

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

（3）不可搶占條件。進程已獲得的資源在未使用完之前不能被搶占，只能在進程使用完時自己釋放。

（4）循環等待條件。在發生死鎖時，必然存在一個進程-資源的循環鏈，即進程集合{p1,p2,p3...pn}中的p0正在等待一個p1占有的資源，p1正在等待p2占有的資源，...pn正在等待p0占有的資源。

處理死鎖的方法

（1）預防死鎖

（2）避免死鎖

（3）檢測死鎖

（4）解除死鎖

避免死鎖的方法（銀行家算法）

最具有代表性的避免死鎖的算法是dijkstra的銀行家算法，起這樣的名字是由于該算法原本是為銀行系統設計的，以確保在銀行發放現金貸款時，不會發生不能滿足所有客戶需要的情況。

1.銀行家算法的數據結構

（1）可利用資源向量Available.代表可利用資源的數目，起初始值是系統中配置該類全部可用資源數目，其數值隨隨該類資源的分配和回收動態地變化。

（2）最大需求MAX，這是一個n*m的矩陣，如果MAX[i,j]=k,則代表進程i需要Rj類資源最大數目為k.

（3）分配矩陣Allcoation。這也是一個n*m矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數，如果Need[i,j]=k，則表示進程i還需要Rj類資源方可完成任務。

Need[i,j]=MAX[i,j]-Allcoation[i,j]

2.銀行家算法

設Request是進程p1的請求向量，如果Request[j]=k,表示進程p需要Rj類型的資源，當p發出資源請求后，系統按下述步驟檢查

（1）如果Request[j]<=Need[i,j],便轉向步驟2，否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。

（2）如果Request[j]<=Available[j],變轉向步驟3，否則，表示尚無足夠資源，p1需要等待。

（3）系統試探著把資源分配給進程p1,并修改數據結構中的數值。

Available[j]=Available[j]-Request[j]

Allocation[i,j]=Allocation[i,j]+Request[i,j]

Need[i,j]=Need[i,j]-Request[j]

（4）系統執行安全性算法，檢查此次資源分配后是否處于安全狀態，若安全，正式分配給進程，完成此次分配，否則此次分配失敗，恢復原來分配資源狀態。