死鎖的原理

定義

一組進程中，其中每個進程因等待事件而阻塞，且所等待的事件只能被這組進程中的另一阻塞進程激發稱之為死鎖。

舉例如下

四個車輛希望緊迫的希望能很快通過，每輛車需要兩個象限的資源，然而四個車都只得到一個象限的資源，每輛車都過不去，此時就會發生阻塞。

死鎖的原因

并發進程的資源競爭

• 資源數目不足
• 資源分配策略，如動態分配
• 進程對資源使用要互斥訪問

有關資源的競爭，比如上圖中四輛車過交叉路口、著名的哲學家就餐問題，還有在之前的章節中，我們講解互斥和同步的時候也舉了很多由于資源競爭的例子，這里不再贅述。

并發進程執行的順序

這里舉了一個雙進程的例子，理解執行順序對死鎖的影響

有兩個進程P、Q需要互斥地訪問A、B一段時間，各自的偽代碼如右圖所示

---

下圖是進程訪問圖示（圖中總共有6種路線，中間的/和\區域需要互斥訪問）

• 1、2號線，表示Q進程先拿到了A和B的資源，P進程拿不到，只能等到Q進程釋放資源。同理，對于5、6號線路P進程先拿到資源，然后是Q進程等待，不會引發死鎖。

• 3、4號線路是死鎖不可避免，兩者只是順序不同，所以我們就只看其中一條線路即可。3號線路中，其中P擁有A，Q擁有B。由于不能走到互斥訪問區域，所以接下來不管怎么走，P和Q兩個都會走到死鎖區域的邊界點，即圖中的（GetB，GetA）。
  

解決方案

此時，可以通過修改P進程的代碼實現互斥，將Get B和release A交換順序，可以避免死鎖
這樣資源的訪問圖如下

兩者的不可訪問區域沒有重疊，進程對資源的獲得有隙可乘，就可以實現互斥訪問了

資源分類

• 可重用資源的死鎖：內存，信號量等
• 可消耗資源：中斷信號、message（消息）、I/O緩沖區

資源分配圖

箭頭表示資源的供給關系，左圖P1需要Ra資源，右圖P1占有Ra資源

圖c是資源數目不夠，然后形成了回路，相互得不到資源。
而圖d是資源數目充足，雖然表面是回路，但是下一時刻資源可以分配，也就沒有死鎖。

死鎖的條件

• Mutual exclusion 互斥
  任一時刻只允許一個進程使用資源
• Hold-and-wait 保持和請求
  進程在請求其余資源時，不主動釋放已經占用的資源
• No preemption 不可剝奪
  進程已經占用的資源，不會被強制剝奪
• Circular wait 循環等待
  資源分配圖不能化簡，存在一個進程之間的封閉環路。（注意：循環等待不一定導致死鎖，但是死鎖一定有循環等待）

這四個條件都是必要條件，只不過一般情況下，根據循環等待判斷死鎖，往往比較有充分性。