Dead Lock 定義

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

系統中存在一組 Processes 陷入 “互相等待對方所擁有之資源” 的情況 (即: Circular Waiting) ，造成所有 Processes 皆無法往下執行，使得 CPU 利用度及産能大幅降低。

Example:

  • 假設一個系統中有兩個資源 \(R_1\) 與 \(R_2\) ，而且該系統產生出兩個行程 \(P_1\) 與 \(P_2\)
  • \(R_1\) 已配置給 \(P_2\) ， \(R_2\) 已配置給 \(P_1\) ，但這兩個行程在執行過程中又向對方要求對方正在使用中的資源，因此造成系統打結

Dead Lock vs. Starvation

  • 相同點:
    • 皆為系統資源分配不當所造成
  • 相異點:

形成 Dead Lock 的四個必要條件

以下四個條件缺一不可：

  • Mutual exclusion (互斥)
    • 某些資源在同一個時間點，最多只能被一個 Process 使用，不能有多個 Processes 同時使用此資源。其它欲使用此資源的 Process 則必須等待，直到該資源被釋放為止。
    • e.g.: Printer, CPU
    • 反例：Read-only File
  • Hold and wait (持有並等待)
    • Process 持有部份資源，且在等待其它 Process 所持有的資源。
  • No preemption (不可搶先)
    • Process 不可任意搶奪其它 Process 所持有的資源，必須等待其它 Process 自願釋放這些資源才可以使用。
  • Circular waiting (循環式等候)
    • 系統中存在一組 Processes {\(P_0, P_1, …, P_n\)} ，其 \(P_0\) 正在等待 \(P_1\) 所持有的資源， \(P_1\) 正在等待 \(P_2\) 所持有的資源，…, \(P_n\) 正在等待 \(P_0\) 所持有的資源， \(P_0\)~\(P_n\) 形成 Circular Waiting。
    • 因此，死結不會發生在 Single process 環境中

死結的處理方法

一共有三種:

  • Dead Lock Prevention
    • 優點： 保証系統絕不會進入死結狀態
    • 缺點：資源利用度低，系統 Throughput 低
  • Dead Lock Avoidance
    • 優點： 保証系統絕不會進入死結狀態
    • 缺點：資源利用度低，系統 Throughput 低
  • Dead Lock Detection & Recovery
    • 優點： 資源利用度相對較高
    • 缺點：
      • 系統可能會發生死結，∴ 必須要 Detection，若死結存在，則要做 Recovery
      • Cost 極高 (因為要不斷 Detection)