死鎖概念以及預防解決方法簡介 多執行緒上篇（八）
在前面不止一次的提到過死鎖。
所謂死鎖(Deadlock)
是指多個程序在執行過程中因爭奪資源而造成的一種僵局(DeadlyEmbrace)，當程序處於這種僵持狀態時，若無外力作用，它們都將無法再向前推進。
死鎖的定義： 集合中的每一個程序都在等待只能由本集合中的其他程序才能引發的事件，那麼該組程序是死鎖的。
也就是說集合中的人需要等待本集合中的其他人來幫忙， 但是，可怕的是所有的人都是這狀態。
引起死鎖的主要原因是： “ 需要採用互斥方法訪問的、不可以被搶佔的資源 “。
因為需要互斥，所以就產生了競爭，出現了競爭就會出現等待，但是資源又不可被搶佔，所以可能會被別人一直佔有，那麼就可能無限的等待，這就形成了死鎖。
資源角度
計算機資源可以從兩個維度進行劃分，重用性以及搶佔性。
不管是可重用資源還是消耗性資源，他們都不是可以任意請求的
系統中可重用資源的個數相對來說比較固定，消耗性資源儘管是個數不固定，動態的，但是某瞬間也都是有個數的，所以也不是可以任意請求的。
所以不管是否可重用，只要有競爭訪問，就可能出現死鎖。
對於不可搶佔資源，一旦被請求了，如果不能夠釋放，那麼別人就必須要等待。
可搶佔資源即使被分配，仍舊可以被搶佔，所以這類資源不會引起死鎖。
所以，從資源的角度看，只需要關注是否是可搶佔資源，如果不可搶佔，那麼就有可能出現死鎖。
資源分配圖
為了直觀的分析死鎖的情況，可以使用資源分配圖
是一種描述資源申請與分配關係的圖
使用圓圈表示程序，矩形表示資源；
箭頭表示資源的申請與釋放，資源->程序表示分配，程序->資源表示資源申請。
如下圖所示，表示P1獲得了R1在等待R2，P2獲得了R2 在等待R1
死鎖產生情況
競爭不可搶佔資源
P1 P2
wait(R1) wait(R2)
wait(R2) wait(R1)
如上所示，程序P1和P2，一個先申請資源R1，一個先申請資源R2，一旦資源R1和R2同時被兩個不同的程序獲得，將會進入死鎖狀態。
如果一個結束之後，另一個開始，那麼就不會出現死鎖。
競爭可消耗資源
設有程序P1、P2、P3，有可消耗資源R1、R2、R3
如果如下順序推進
P1: send(p2, R1); receive(p3, R3);
P2: send(p3, R2); receive(p1, R1);
P3: send(p1, R3); receive(p2, R2);
如下圖所示，每個程序都先生產資源給別人，然後才會等待別人的資源，每個人最終都能夠獲得資源
如果是
P1: receive(p3, R3); send(p2, R1);
P2: receive(p1, R1); send(p3, R2);
P3: receive(p2, R2); send(p1, R3);
所有的人都在等待別人的資源，才會生產訊息，形成了死鎖。
程序推進順序不當
下圖中，橫座標為程序1，縱座標為程序2
程序1的活動過程有Request(R1) Request(R2) Release(R1) Release(R2)
程序2的活動過程有Request(R2) Request(R1) Release(R2) Release(R1)
顯然，圖中的陰影區域D，陰影區域的左下角表示程序1申請了資源R1，程序2申請了資源R2，如果此時程序1申請R2或者程序2申請R1或者兩者都有，必然會發生死鎖
如果避開這個區域，比如一個程序結束後另一個開始，1號曲線或者2號曲線，或者程序1釋放了R1後，程序2才開始申請R2就不會進入死鎖
通過這種活動順序圖，可以推測出來可能會出現死鎖的時空區域。
《計算機作業系統 第四版》 圖3-14
死鎖必要條件
前面從資源以及場景的角度分析了死鎖，其根本也還是“ 需要採用互斥方法訪問的、不可以被搶佔的資源 ”。
死鎖形成有四大必要條件，也就是說如果死鎖了必然存在這些。
如果不互斥，大家都可以訪問，就沒可能死鎖；
如果沒有請求和保持，比如一次性分配，如果分配不到等待別人使用後釋放即可，保持和請求必然會導致“拿走了比人需要的，還等待別人”的場景；
如果可以搶佔，即使已經死鎖，肯定會被打破；
如果沒有迴圈等待，終究會有一個程序會自己完成，完成後便會釋放自己持有的資源，整個系統就會被啟用。
所以說，想要處理死鎖，或者說避免死鎖，關鍵點就是這幾個條件，只要條件被打破，就不會存在繼續死鎖下去的可能。
死鎖解決方法
從預防-避免-檢測-解除，對死鎖的防範程度依次減弱，但是對應的資源的利用率依次提高，也就是併發程度依次變高。
預防就像接種疫苗，可能你這輩子都不會接觸到病毒。
避免就是在可能出事情的地方，做一些保障處理，比如發現有些場合人員混亂，全是二手菸，那就不進房間了。
檢測就好像是定期的體檢，沒問題繼續生活，有什麼小問題就去治療一下。
解除就是真的去看病了。
預防死鎖
預防就是事先前的準備，如同疫苗，死鎖的預防通常就是增加限制，破壞必要條件。
破壞“請求和保持”
所有的資源必須一次性分配，或者不分配，這樣能夠保障一個程序要麼就等待，要麼就可以獲得全部的資源，而不會出現保持了資源，然後再去請求的可能。
但是很顯然，資源利用率低，併發程度低
比如說有一個任務三個階段，每個階段一種資源，每個階段十分鐘，如果一次性分配的話，每個資源都會有二十分鐘的閒置，極大地浪費。
這種方案可以進一步優化，分階段處理，而不是一次性，還是剛才的示例，每個階段僅僅申請該階段的資源，使用完畢後，將資源釋放，然後再去獲取下一階段的資源
也就是說需要合理的劃分階段，一個完整任務中的一個子任務（也就是一個階段）一次性分配資源，使用完畢後釋放，再去請求，就不存在保持請求了。
破壞“不可搶佔”
如果資源是可搶佔的，自然就不會死鎖，終究會自動解鎖，如果能夠合理的將不可搶佔資源轉換為“可搶佔”那麼就可以預防死鎖
當一個程序持有了某些資源後，如果又提出了新的請求，如果該請求並不能滿足，那麼他必須釋放已有的資源，也就可以說是被搶佔了
不過這個思路實現複雜，可能會付出很大的代價，比如印表機開始處理了，你現在要切換，肯定不會很容易。
破壞“迴圈等待”
將資源按照一定的順序進行申請，可以保證資源的有序性，也就可以破壞迴圈等待，正是因為資源的順序很隨意，所以才導致很容易死鎖
比如所有的程序全部都是R1然後R2，就永運不會死鎖
所以可以採取對系統內資源編號的形式，所有的資源申請必須是從小到大的順序。
如此，就肯定不會迴圈成環。
但是，號碼如何編？到底誰大誰小？要統計下平時資源的申請順序進行編號
然後如果新增加裝置？
另外如果有些程序就是跟系統的排序不同怎麼辦？
避免死鎖
在死鎖避免方法中，把系統的狀態分為安全狀態和不安全狀態。
安全狀態就是可以找到資源分配的有序序列， 各程序可以順利推進完成。
不安全狀態如果找不到一個合理的資源分配的有序序列，不能保障各程序可以順利完成，那麼就是不安全。
當系統處於安全狀態時，可避免發生死鎖。反之，當系統處於不安全狀態時，則可能進入到死鎖狀態。
簡言之，避免死鎖就是在資源分配時，藉助於演算法對資源分配進行計算評估，相當於風險評估機構。
經典的演算法有Dijkstra提出的銀行家演算法
死鎖檢測
死鎖的檢測也是藉助於演算法進行處理，想要檢測死鎖
首先，系統中必須能夠記錄資源的請求和分配記錄，其次需要提供一種演算法，通過對請求和分配記錄進行分析，計算出當前的狀態。
死鎖解除
如果檢測出死鎖，那麼必須進行解除，常用的解除方式有兩種，搶佔資源和終止程序，本質都是強行將資源奪回到系統中。
終止程序的話最簡單的就是全部終止，將涉及的死鎖程序全部都終止掉，顯然全部終止就好像將一臺工作中的電腦強行重啟一樣，代價很大
所以還可以逐個終止，直到死鎖解除。
總結
本文對作業系統中死鎖的概念進行了簡單的介紹，不僅僅程序有死鎖，執行緒的執行仍舊也會有死鎖。
多執行緒程式設計中也會出現死鎖，在這些場景中，死鎖的概念是相同的---都是同一個集合中的執行緒都在等待本集合中的執行緒
對於作業系統對死鎖的處理與解決，對於程式設計中不無借鑑之處，我們應該深刻理解死鎖形成的條件，才能夠在程式設計中儘可能的避免死鎖。
原文地址: 死鎖概念以及預防解決方法簡介 多執行緒上篇（八）