Dead Lock Prevention

發表於 Disqus：
文章字數： 788 所需閱讀時間 ≈ 1 分鐘

概念: 打破四個必要條件其中之一，就可以保証死結永不發生。

  1. 打破 “Mutual Exclusion”
    • ∵ 互斥是某些資源與生倶來的性質 ∴ 無法打破
  2. 打破 “No Preemptive”
    • 允許 Process 可以搶奪其它 Waiting Process 手中的資源。(即：改為 Preemptive)
      • 頂多只會有 Starvation，但 No Dead Lock (可以採用 Aging 技術解決)
  3. 打破 “Hold and Wait”

可採取下列作法之一：

  1. 規定： 除非 Process 可以一次取得完成工作所需的全部資源，才允許 Process 持有資源，否則 Process 不准持有任何資源
    • 若一次取得全部資源 ⇒ “Wait”不成立
    • 若無法取得全部資源，則全都不拿 ⇒ “Hold” 不成立
    • 全有全無
    • 系統産能低
  2. Process 在執行之初可持有部份資源，但若要再申請資源之前，必須先釋放手中所有資源，才可以提出申請
    • 一開始可取部份資源執行 ⇒ “Wait”不成立
    • 再申請時，需放掉手中所有資源 ⇒ “Hold” 不成立
    • 系統産能低
  3. 打破 “Circular Waiting”

O.S.需採取下列措施：

  • 為毎個不同類型的資源賦予一個獨一無二的資源編碼 (Unique ID)
  • 規定 Process 必須按照資源編號遞增 (遞減) 的方式提出資源申請

證明( 反證法 ) :

假設在 O.S. 採取前述兩個措施後，系統仍存在一組 Processes 造成 Circular Waiting 如下：

\(r_i: 資源本身 , R_i: 資源編碼\)

  • 令一組行程 \(P_0\)~\(P_n\) 分別持有資源 \(r_0, r_1, …, r_n\)，且資源類型皆不相同 (即：編號不同)
  • 根據遞增申請規則，上述 Circular Waiting 會推出 \(r_0 < r_1 < … < r_n < r_0\) 。其中竟導出 \(r_0 < r_0\) 此一矛盾的式子(即：相同的資源，其編號不同)
  • ∴ 假設不成立，不會有 Circular Waiting 狀況產生