作業系統-2.4-死鎖

1.死鎖的概念

1.1什么是死鎖

話不多說，先上圖：

死鎖：在并發環境下，各行程因競爭資源而造成的一種互相等待對方手里的資源，導致各行程都阻塞，都無法向前推進的現象，就是“死鎖”，發生死鎖后若無外力干涉,這些行程都將無法向前推進，

1.2死鎖，饑餓，死回圈的區別

• 死鎖：各行程互相等待對方手里的資源，導致各行程都阻塞，無法向前推進的現象，
• 饑餓：由于長期得不到想要的資源，某行程無法向前推進的現象，比如：在短行程優先（SPF）演算法中，若有源源不斷的短行程到來，則長行程將一直得不到處理機，從而發生長行程“饑餓”，
• 死回圈：某行程執行程序中一直跳不出某個回圈的現象，有時是因為程式邏輯bug 導致的，有時是程式員故意設計的，

詳細區別見下表：

1.3死鎖產生的必要條件

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

1. 互斥條件，只有對必須互斥使用的資源的爭搶才會導致死鎖（如哲學家的筷子、列印機設備），像記憶體、揚聲器這樣可以同時讓多個行程使用的資源是不會導致死鎖的（因為行程不用阻塞等待這種資源），
2. 不剝奪條件，行程所獲得的資源在未使用完之前，不能由其他行程強行奪走，只能主動釋放，
3. 請求和保持條件，行程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他行程占有，此時請求行程被阻塞，但又對自己已有的資源保持不放，
4. 回圈等待條件，存在一種行程資源的回圈等待鏈，鏈中的每一個行程已獲得的資源同時被下一個行程所請求，

注意：發生死鎖時一定有回圈等待，但是發生回圈等待時未必死鎖（回圈等待是死鎖的必要不充分條件），
如果同類資源數大于1，則即使有回圈等待，也未必發生死鎖，但如果系統中每類資源都只有一個，那回圈等待就是死鎖的充分必要條件了，

1.4什么時候發生死鎖

1. 對系統資源的競爭，各行程對不可剝奪的資源（如列印機）的競爭可能引起死鎖，對可剝奪的資源(CPU）的競爭是不會引起死鎖的，
2. 行程推進順序非法，請求和釋放資源的順序不當，也同樣會導致死鎖，例如，并發執行的行程P1、P2分別申請并占有了資源R1、R2，之后行程p1又緊接著申請資源R2，而行程p2又申請資源R1，兩者會因為申請的資源被對方占有而阻塞，從而發生死鎖，
3. 信號量的使用不當也會造成死鎖，如生產者-消費者問題中，如果實作互斥的P操作在實作同步的P操作之前，就有可能導致死鎖，(可以把互斥信號量、同步信號量也看做是一種抽象的系統資源)，

總之，對不可剝奪資源的不合理分配，可能導致死鎖，

1.5死鎖的處理策略

1. 預防死鎖，破壞死鎖產生的四個必要條件中的一個或幾個，
2. 避免死鎖，用某種方法防止系統進入不安全狀態，從而避免死鎖（銀行家演算法)，
3. 死鎖的檢測和解除，允許死鎖的發生，不過作業系統會負責檢測出死鎖的發生，然后采取某種措施解除死鎖，

1.6總結

2.死鎖的處理策略-預防死鎖

2.1破壞互斥條件

• 互斥條件：只有對必須互斥使用的資源的爭奪才會導致死鎖，
• 如果把只能互斥使用的資源改造為允許共享使用，則系統不會進入死鎖狀態，比如: SPOOLing技術，作業系統可以采用SPoOLing技術把獨占設備在邏輯上改造成共享設備，比如，用SPooLing技術將列印機改造為共享設備…
• 該策略的缺點：并不是所有的資源都可以改造成可共享使用的資源，并且為了系統安全，很多地方還必須保護這種互斥性，因此，很多時候都無法破壞互斥條件，

2.2破壞不剝奪條件

• 不剝奪條件：行程所獲得的資源在未使用完之前，不能由其他行程強行奪走，只能主動釋放，
• 破壞不剝奪條件：
  1. 方案一：當某個行程請求新的資源得不到滿足時，它必須立即釋放保持的所有資源，待以后需要時再重新申請，也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件，
  2. 方案二：當某個行程需要的資源被其他行程所占有的時候，可以由作業系統協助，將想要的資源強行剝奪，這種方式一般需要考慮各行程的優先級（比如：剝奪調度方式，就是將處理機資源強行剝奪給優先級更高的行程使用)，
• 該策略的缺點：
  1. 實作起來比較復雜，
  2. 釋放已獲得的資源可能造成前一階段作業的失效，因此這種方法一般只適用于易保存和恢復狀態的資源，如CPU，
  3. 反復地申請和釋放資源會增加系統開銷，降低系統吞吐量，
  4. 若采用方案一，意味著只要暫時得不到某個資源，之前獲得的那些資源就都需要放棄，以后再重新申請，如果一直發生這樣的情況，就會導致行程饑餓，

2.3破壞請求和保持條件

• 請求和保持條件：行程已經保持了至少一個資源，但又提出了新的資源請求，而該資源又被其他行程占有，此時請求行程被阻塞，但又對自己已有的資源保持不放，
• 可以采用靜態分配方法，即行程在運行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運行，一旦投入運行后，這些資源就一直歸它所有，該行程就不會再請求別的任何資源了，
• 該策略實作起來簡單，但也有明顯的缺點:
  有些資源可能只需要用很短的時間，因此如果行程的整個運行期間都一直保持著所有資源，就會造成嚴重的資源浪費，資源利用率極低，另外，該策略也有可能導致某些行程饑餓，

2.4破壞回圈等待條件

• 回圈等待條件：存在一種行程資源的回圈等待鏈，鏈中的每一個行程已獲得的資源同時被下一個行程所請求
• 可采用順序資源分配法，首先給系統中的資源編號，規定每個行程必須按編號遞增的順序請求資源，同類資源（即編號相同的資源）一次申請完，
• 原理分析:一個行程只有已占有小編號的資源時，才有資格申請更大編號的資源，按此規則，已持有大編號資源的行程不可能逆向地回來申請小編號的資源，從而就不會產生回圈等待的現象，
• 該策略的缺點:
  1. 不方便增加新的設備，因為可能需要重新分配所有的編號;
  2. 行程實際使用資源的順序可能和編號遞增順序不一致，會導致資源浪費;
  3. 必須按規定次序申請資源，用戶編程麻煩，

2.5總結

3.死鎖的處理策略-避免死鎖

3.1安全序列，不安全狀態，死鎖的聯系

安全序列：就是指如果系統按照這種序列分配資源，則每個行程都能順利完成，只要能找出一個安全序列，系統就是安全狀態，當然，安全序列可能有多個，

如果分配了資源之后，系統中找不出任何一個安全序列，系統就進入了不安全狀態，這就意味著之后可能所有行程都無法順利的執行下去，當然，如果有行程提前歸還了一些資源，那系統也有可能重新回到安全狀態，不過我們在分配資源之前總是要考慮到最壞的情況，

如果系統處于安全狀態，就一定不會發生死鎖，如果系統進入不安全狀態，就可能發生死鎖（處于不安全狀態未必就是發生了死鎖，但發生死鎖時一定是在不安全狀態），
因此可以在資源分配之前預先判斷這次分配是否會導致系統進入不安全狀態，以此決定是否答應資源分配請求，這也是“銀行家演算法”的核心思想，

3.2銀行家演算法

核心思想：在行程提出資源申請時，先預判此次分配是否會導致系統進入不安全狀態，如果會進入不安全狀態，就暫時不答應這次請求，讓該行程先阻塞等待，

4.死鎖的處理策略-檢測和解除

4.1死鎖的檢測

為了能對系統是否已發生了死鎖進行檢測，必須：

①用某種資料結構來保存資源的請求和分配資訊;
②提供一種演算法，利用上述資訊來檢測系統是否已進入死鎖狀態，

注：一般用矩形表示資源結點，矩形中的小圓代表該類資源的數量，

演算法思想：如果系統中剩余的可用資源數足夠滿足行程的需求，那么這個行程暫時是不會阻塞的，可以順利地執行下去，如果這個行程執行結束了把資源歸還系統，就可能使某些正在等待資源的行程被激活，并順利地執行下去，相應的，這些被激活的行程執行完了之后又會歸還一些資源，這樣可能又會激活另外一些阻塞的行程…
如果按上述程序分析，最終能消除所有邊，就稱這個圖是可完全簡化的，此時一定沒有發生死鎖（相當于能找到一個安全序列)，
如果最終不能消除所有邊，那么此時就是發生了死鎖，最侄訓連著邊的那些行程就是處于死鎖狀態的行程，

死鎖定理：如果某時刻系統的資源分配圖是不可完全簡化的，那么此時系統死鎖，

4.2死鎖的解除

一旦檢測出死鎖的發生，就應該立即解除死鎖，
補充：并不是系統中所有的行程都是死鎖狀態，用死鎖檢測演算法化簡資源分配圖后，還連著邊的那些行程就是死鎖行程，
解除死鎖的主要方法有:
1．資源剝奪法：掛起（暫時放到外存上）某些死鎖行程，并搶占它的資源，將這些資源分配給其他的死鎖行程，但是應防止被掛起的行程長時間得不到資源而饑餓，
2．撤銷行程法（或稱終止行程法）：強制撤銷部分、甚至全部死鎖行程，并剝奪這些行程的資源，這種方式的優點是實作簡單，但所付出的代價可能會很大，因為有些行程可能已經運行了很長時間，已經接近結束了，一旦被終止可謂功虧一簣，以后還得從頭再來，
3．行程回退法：讓一個或多個死鎖行程回退到足以避免死鎖的地步，這就要求系統要記錄行程的歷史資訊，設定還原點，

4.3總結