學習目標
- 理解死結的定義和發生條件
- 掌握死結的四個必要條件（Coffman's Conditions）
- 理解死結的預防與避免策略
- 能夠判斷資源分配是否會導致死結
- 理解原子指令 (Atomic Instruction) 的概念
1. 什麼是死結？
1.1 定義
死結 (Deadlock) 是指一組行程 (Processes) 處於僵持狀態，其中每個行程都在等待一個僅能由該組中另一個行程才能釋放的資源。
1.2 生活化例子
想像一個十字路口，四輛車分別從四個方向駛來： - 車 A 需要車 B 讓路才能通過 - 車 B 需要車 C 讓路才能通過 - 車 C 需要車 D 讓路才能通過 - 車 D 需要車 A 讓路才能通過
結果：所有車都無法前進，形成死結！
1.3 電腦系統中的例子
假設有兩個行程 P1 和 P2，以及兩個資源 R1 和 R2：
時間點 1: P1 取得 R1
時間點 2: P2 取得 R2
時間點 3: P1 請求 R2（但 R2 被 P2 佔有，P1 等待）
時間點 4: P2 請求 R1（但 R1 被 P1 佔有，P2 等待）
結果：P1 等待 P2 釋放 R2，P2 等待 P1 釋放 R1，形成死結！
2. 死結發生的四個必要條件
死結的發生必須同時滿足以下四個條件，這四個條件被稱為 Coffman's Conditions：
2.1 相互排斥 (Mutual Exclusion)
定義： 資源一次只能被一個行程使用。
說明： - 如果資源可以被多個行程同時使用，就不會發生死結 - 例如：讀取鎖（Read Lock）允許多個行程同時讀取，但寫入鎖（Write Lock）只能被一個行程使用
範例： - 印表機：一次只能被一個行程使用 - 檔案寫入：一次只能被一個行程寫入
2.2 佔有與等待 (Hold and Wait)
定義： 行程已持有一個資源，同時又在等待其他行程持有的資源。
說明： - 如果行程必須在取得所有資源後才開始執行，或是一次只能持有一個資源，就不會發生死結
範例：
行程 A: 持有資源 R1，等待資源 R2
行程 B: 持有資源 R2，等待資源 R1
2.3 不可搶佔 (No Preemption)
定義： 資源不能被強制從持有它的行程中搶走，只能由該行程自願釋放。
說明： - 如果系統可以強制搶佔資源，就不會發生死結 - 但搶佔可能導致資料不一致或工作進度丟失
範例： - 如果行程 A 正在使用印表機，系統不能強制中斷並將印表機分配給行程 B - 如果行程正在寫入檔案，不能強制中斷寫入操作
2.4 循環等待 (Circular Wait)
定義： 存在一個行程集合 {P₀, P₁, ..., Pₙ}，使得： - P₀ 等待 P₁ 的資源 - P₁ 等待 P₂ 的資源 - ... - Pₙ 等待 P₀ 的資源
說明： - 這是一個循環的等待鏈 - 如果沒有循環，就不會發生死結
範例：
P0 → 等待 R1 (被 P1 持有) → P1
P1 → 等待 R2 (被 P2 持有) → P2
P2 → 等待 R0 (被 P0 持有) → P0
形成循環：P0 → P1 → P2 → P0
3. 死結的處理策略
3.1 預防 (Prevention)
定義： 透過破壞上述四個必要條件之一來確保死結永遠不會發生。
方法：
方法 1: 破壞「佔有與等待」
- 策略: 要求行程一次請求所有需要的資源
- 優點: 簡單直接
- 缺點:
- 資源利用率低（資源可能長時間閒置）
- 行程可能不知道未來需要哪些資源
方法 2: 破壞「不可搶佔」
- 策略: 允許系統搶佔資源
- 優點: 可以打破死結
- 缺點:
- 可能導致資料不一致
- 需要保存和恢復狀態，開銷大
- 不適用於所有資源類型（如印表機）
方法 3: 破壞「循環等待」
- 策略: 對資源進行排序，要求行程按順序請求資源
- 優點: 有效防止循環等待
- 缺點:
- 可能導致資源利用率降低
- 需要事先知道資源順序
預防策略的缺點： - 較嚴格，可能導致資源利用率降低 - 可能限制系統的靈活性
3.2 避免 (Avoidance)
定義： 系統在分配資源前，會先檢查這次分配是否會導致系統進入「不安全狀態 (Unsafe State)」。若會，則延遲分配。
不安全狀態 (Unsafe State)
定義： 系統處於一種狀態，雖然目前沒有死結，但存在某種資源分配序列可能導致死結。
注意： 不安全狀態不一定會導致死結，但有可能導致死結。
銀行家演算法 (Banker's Algorithm)
原理： - 模擬資源分配，檢查分配後系統是否仍處於安全狀態 - 只有在安全狀態下才進行實際分配
需要的資訊： - 可用資源 (Available): 系統目前可用的資源數量 - 最大需求 (Max): 每個行程最多需要多少資源 - 已分配 (Allocation): 每個行程目前已分配到的資源 - 需求 (Need): 每個行程還需要多少資源（Need = Max - Allocation）
安全狀態檢查步驟： 1. 尋找一個行程，其 Need ≤ Available 2. 假設該行程完成，釋放其資源 3. 更新 Available = Available + Allocation 4. 重複步驟 1-3，直到所有行程都能完成（安全狀態）或找不到這樣的行程（不安全狀態）
範例：
假設系統有 12 個資源，三個行程：
| 行程 | Max | Allocation | Need | Available |
|---|---|---|---|---|
| P0 | 10 | 5 | 5 | 3 |
| P1 | 4 | 2 | 2 | |
| P2 | 9 | 2 | 7 |
檢查： 1. P1 的 Need (2) ≤ Available (3)，可以完成 - 完成後，Available = 3 + 2 = 5 2. P0 的 Need (5) ≤ Available (5)，可以完成 - 完成後，Available = 5 + 5 = 10 3. P2 的 Need (7) ≤ Available (10)，可以完成
結論： 系統處於安全狀態
避免策略的優點： - 比預防策略更靈活 - 允許更高的資源利用率
避免策略的缺點： - 需要行程預先宣告其最大資源需求 - 演算法複雜度高 - 需要知道未來的資源需求
3.3 偵測與恢復 (Detection and Recovery)
定義： 允許死結發生，但系統會定期檢查是否有死結，一旦發現就進行恢復。
偵測方法： - 使用資源分配圖 (Resource-Allocation Graph) - 檢查是否存在循環
恢復方法： 1. 終止行程: 終止一個或多個死結中的行程 2. 搶佔資源: 從死結中的行程搶佔資源
4. 資源分配圖 (Resource-Allocation Graph)
4.1 圖形表示法
符號： - 圓圈 (○): 代表行程 (Process) - 方框 (□): 代表資源 (Resource) - 方框內的點: 代表資源的實例 (Instance) - 從資源指向行程的箭頭: 代表「持有」關係（資源被行程佔有） - 從行程指向資源的箭頭: 代表「請求」關係（行程等待資源）
4.2 繪製步驟
步驟 1: 分析資源請求 列出每個行程持有 (Hold) 與請求 (Request) 的資源。
範例： - 行程 A: 持有檔案 1，請求檔案 2 - 行程 B: 持有檔案 3，請求檔案 1 - 行程 C: 持有檔案 2，請求檔案 3
步驟 2: 繪製圖形
檔案1 ──→ A ──→ 檔案2
↑ │
│ ↓
└──────── C ←── 檔案3
↑
│
B
步驟 3: 判斷是否存在循環 檢查圖中是否存在循環路徑。
此例中存在循環：
A → 檔案2 → C → 檔案3 → B → 檔案1 → A
步驟 4: 判斷死結 - 如果存在循環，且每個資源類型只有一個實例，則死結已經發生 - 如果存在循環，但資源有多個實例，則可能發生死結（需要進一步檢查）
4.3 判斷死結的條件
死結發生的充分必要條件： 1. 資源分配圖中存在循環 2. 循環中的每個資源類型只有一個實例
為什麼需要兩個條件？ - 如果資源有多個實例，即使有循環，其他實例可能滿足等待的需求
5. 原子指令 (Atomic Instruction)
5.1 定義
原子指令 (Atomic Instruction) 是不可中斷的指令，一旦開始執行，就會完整執行完畢，期間不會被任何其他行程或事件打斷。
5.2 特性
- 不可分割性: 要麼完全執行，要麼完全不執行
- 不可中斷性: 執行過程中不能被其他行程或中斷打斷
- 可見性: 執行結果對所有行程立即可見
5.3 用途
原子指令主要用於實現同步機制，如： - 號誌 (Semaphores) - 鎖 (Locks) - 互斥鎖 (Mutex)
5.4 為什麼需要原子指令？
問題：競態條件 (Race Condition)
考慮以下情況（不使用原子指令）：
// 共享變數
int counter = 0;
// 行程 A
void process_A() {
int temp = counter; // 讀取 counter = 0
temp = temp + 1; // temp = 1
counter = temp; // 寫回 counter = 1
}
// 行程 B（同時執行）
void process_B() {
int temp = counter; // 讀取 counter = 0（在 A 寫回之前）
temp = temp + 1; // temp = 1
counter = temp; // 寫回 counter = 1
}
結果： 兩個行程都執行完畢後，counter 應該是 2，但實際上可能是 1！
原因： 「讀取-修改-寫回」這三個操作不是原子的，可能被中斷。
解決方案：使用原子指令
// 使用原子指令
atomic_increment(counter); // 這個操作是原子的，不可中斷
5.5 原子指令與死結的關係
原子指令透過確保「檢查並設置」等操作的原子性，可以： 1. 防止競態條件: 確保共享資源的正確存取 2. 實現相互排斥: 正確地實現鎖機制 3. 管理共享資源: 這是避免死結問題的基礎
範例：實現鎖
// 使用原子指令實現鎖
bool lock = false;
void acquire_lock() {
while (atomic_test_and_set(&lock)) {
// 如果鎖已被佔有，等待
// atomic_test_and_set 是原子操作：
// 1. 檢查 lock 是否為 false
// 2. 如果是，設置為 true 並返回 false
// 3. 如果不是，返回 true
// 這個操作是原子的，不會被中斷
}
}
void release_lock() {
atomic_clear(&lock); // 原子地清除鎖
}
6. 實際範例：判斷死結
範例 1
資源分配情況： - 行程 A: 持有資源 R1，請求資源 R2 - 行程 B: 持有資源 R2，請求資源 R1
繪製資源分配圖：
R1 ──→ A ──→ R2
↑ │
└──────── B ←┘
判斷： - 存在循環：A → R2 → B → R1 → A - 每個資源只有一個實例 - 結論：死結已發生
範例 2
資源分配情況： - 行程 A: 持有資源 R1，請求資源 R2 - 行程 B: 持有資源 R2，請求資源 R3 - 行程 C: 持有資源 R3，請求資源 R1 - 資源 R1 有 2 個實例，R2 和 R3 各有 1 個實例
繪製資源分配圖：
R1(2個) ──→ A ──→ R2(1個)
↑ │
│ ↓
└──────── C ←── R3(1個)
↑
│
B
判斷： - 存在循環：A → R2 → B → R3 → C → R1 → A - 但 R1 有 2 個實例，可能不會死結（如果另一個實例可用） - 需要進一步檢查：可能發生死結
7. 練習題
練習題 1
請說明死結發生的四個必要條件。
參考答案： 1. 相互排斥: 資源一次只能被一個行程使用 2. 佔有與等待: 行程已持有一個資源，同時又在等待其他資源 3. 不可搶佔: 資源不能被強制搶走 4. 循環等待: 存在循環的等待鏈
練習題 2
請比較死結的「預防」和「避免」策略。
參考答案： - 預防: 破壞四個必要條件之一，確保死結永遠不會發生。較嚴格，可能導致資源利用率降低。 - 避免: 在分配資源前檢查是否會導致不安全狀態。需要預先知道資源需求，使用銀行家演算法。
練習題 3
判斷以下資源分配是否會導致死結： - 行程 P1: 持有 R1，請求 R2 - 行程 P2: 持有 R2，請求 R3 - 行程 P3: 持有 R3，請求 R1
參考答案： 繪製資源分配圖，存在循環 P1 → R2 → P2 → R3 → P3 → R1 → P1。如果每個資源只有一個實例，則死結已發生。
8. 考試重點提醒
- 四個必要條件要記熟: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait
- 預防 vs 避免: 要能清楚區分兩者的差異
- 資源分配圖: 要能正確繪製並判斷是否存在循環
- 原子指令: 理解其定義、用途和與死結的關係
- 銀行家演算法: 理解安全狀態檢查的基本概念