【經典結構】死鎖
死鎖
1.概念
一個很通俗易懂的例子：假設有紅藍兩把鑰匙開紅藍兩個門，兩個人分別執行六條指令，最後要能夠都把兩扇門打開。 注意紅藍鑰匙都各只有一把，也就是說兩個人共享這對鑰匙。
比如下面這幅圖的解法：
兩個人同時執行，A能夠順利把門打開，因為它正好在第3步的時候能拿到B歸還後的紅鑰匙，但是對B就不一樣了，因為A沒有及時歸還藍鑰匙，在最後才想起來還，那B在第四步的時候想要拿到藍鑰匙，需要等A在第6步把藍鑰匙還了才行，也就是得等著A完事以後B才能完事，所以兩個人完成時間並不相同(也就是兩個執行緒A先結束，B再結束),但終究還是都完成了。
那再看下面這個解法：
兩個人A和B在第三步的時候，A想要獲取紅鑰匙，等著B歸還紅鑰匙；B想要獲取藍鑰匙，等著A歸還藍鑰匙，那這兩個人永遠在這卡著，進行不下去了，這就是死鎖。
問：什麼是死鎖？
死鎖就是多個執行緒在運行的時候互相搶奪資源，造成了一種僵持的阻塞狀態。比如執行緒AB分別握著鎖a和鎖b，但是這時候兩個執行緒又都想獲得對方的鎖，又誰都不鬆手，這時候就形成了僵局，成了阻塞狀態。
2.條件
上面想開兩扇門其實有很多種解法，那什麼時候會出現死鎖，比如同樣的問題解法1就不會死鎖，解法2就會死鎖。一般來說，死鎖有四個必要條件：
問：死鎖產生的條件？
- 互斥條件：某資源某一時刻只能被一個執行緒佔用。–只有一對鑰匙；
- 請求與保持條件：當一個執行緒請求新的資源而阻塞後，對已經獲得的資源保持不放。 –A拿著紅鑰匙又想要藍鑰匙，還不歸還紅鑰匙；
- 不剝奪條件：一個執行緒拿到資源後不能被剝奪，只能由自己釋放。 –人除非自己主動歸還鑰匙，不然就一直占著；
- 環路等待條件：在發生死鎖時，必然存在著執行緒之間頭尾相連循環等待資源的關係；比如執行緒P0等待著P1的資源，P1等待著P2的資源，…，Pn等待著P0的資源。 –拿著紅鑰匙的A在等藍鑰匙，拿著藍鑰匙的B在等紅鑰匙；
上面是產生死鎖的四個必要條件,那如果想要避免，只需破壞其中一個就可以。
問：如何避免死鎖？
- 破壞互斥條件：這個條件沒辦法進行破壞，因為我們用鎖的目的就是想讓它們互斥。
- 破壞請求與保持條件：只要有一個資源得不到分配，那也不給這個執行緒分配其他資源。 –一個人拿到一把鑰匙後，只有還了才能去請求下一把；
- 破壞不剝奪條件：當某執行緒拿著資源，但是得不到其他資源，那就釋放自己的資源。 –比如可以設置A拿著鑰匙等了十分鐘還是執行不了下一步，那就自動歸還自己的鑰匙；
- 破壞環路等待條件：每類資源都申請一個編號，每個執行緒按順序申請資源，按相反順序釋放資源。 –上面產生死鎖一定是A和B都先拿了不同的鑰匙，比如可以規定任何執行緒都只能先拿紅鑰匙再拿藍鑰匙。
問：在實際中採用什麼方法解決死鎖？
- 銀行家演算法；
- 順序加鎖：確保執行緒按照相同的順序獲得鎖(上面提到的4)；
- 限時加鎖：執行緒在嘗試獲取鎖的時候加一個超時時間，超過這個時間就放棄該請求，並把自己獲得的鎖釋放(上面提到的3)；
問：銀行家演算法是什麼，具體流程？
一句話概括：當一個進程申請使用資源的時候，銀行家演算法通過先試探性的分配給該進程資源，然後通過安全性演算法判斷分配後的系統是否處於安全狀態。
四種結構
- 最大需求資源數量Max(例如Max[j]=4,表示當前進程i對資源j的最大需求量為4)；
- 已分配給進程的資源Allocation(例如Allocation[j]=4,表示當前進程i已經分配的資源j數量為4)；
- 還需要的資源數量Need(例如Need[j]=4,表示當前進程i還需要資源j的數量為4)；Need[j]=Max[j]-Allocation[j]
- 空閑資源數量Available(例如Available[j]=4,表示當前資源j的空閑數量為4)；
過程
- 1.假設進程P1申請資源，銀行家演算法先試探性的分配給他(當然先看看當前資源池中的資源數量夠不夠)
- if申請的資源數量<=Available(作業系統(銀行家))所有的資源,那就執行2；
- if申請的資源數量>Available–>不安全；
- 2.判斷分配給P1後剩餘的資源，能不能使進程隊列中的某個進程執行完畢；
- if有進程可執行完畢，那就執行3；
- if沒有進程可執行完畢，那系統處於不安全狀態(即此時沒有一個進程能夠完成並釋放資源，隨時間推移，系統終將處於死鎖)；
- 3.經過2判斷後有進程可執行完畢，則假設回收已經分配給它的資源(剩餘資源數量增加)，並把這個進程標記為可完成，然後接著判斷隊列中的其他進程；
- 4.如果所有進程都可執行完畢，那系統就處於安全狀態，並根據剛才的順序生成安全序列(例如{P0,P3,P2,P1}表示將申請後的資源work先分配給P0->回收P0(原work+進程P0已分配的Allocation=新work)->分配給P3->回收P3->…
注意
- 安全狀態：如果存在一個由系統中所有進程構成的安全序列，那系統安全狀態，安全狀態一定沒有死鎖；
- 不安全狀態：不存在一個安全序列。不安全狀態不一定死鎖；
例子
比如當前出現下述資源分配：
上文一共有4種資源，例如P0 1號資源已經分配的為0；3號資源分配的為3；
問：該狀態是否安全？
根據上面的過程可以列出下面的表：
work指的是資源池裡可以利用的資源，根據上面的Available，發現其能滿足P0的need，然後求出回收P0的新work，接著發現能滿足P3，…，就這樣不斷進行；最後能找到一個序列{P0,P3,P4,P1,P2},所以系統是安全的。
問：if 進程P2提出請求Request(1,1,2,2),系統能分配給它嗎？
檢查步驟：
- 1.Request2(1,1,2,2)<=Need2(2,3,4,5)
- 2.Request2(1,2,2,2)<=Available(1,6,2,2)
- 3.兩者都滿足，那就先假設為P2分配資源，然後修改Available，Allocation，Need2；
Available(0,4,0,0)
Allocation2(2,5,7,6)
Need2(1,1,3,4) - 4.這時候再進行檢查，Available(0,4,0,0) 誰也滿足不了了，系統進入不安全狀態，所以不能分配給P2資源。
