同步、互斥與死結：讓並行工作安全前進
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
死結
也會看到：deadlock、死鎖多個工作各自占著資源又互等對方釋放，因而永遠無法前進。
- 生活例子：
- 兩台車在窄巷互不退讓，彼此都卡住。
- 別搞混：
- 等待很久不一定是死結；死結有形成環狀等待等特定條件。
互斥鎖與號誌
也會看到：mutex、lock、semaphore、互斥鎖、信號量互斥鎖限制同一時間只有一人進入；號誌則用計數控制可同時使用的名額。
- 生活例子：
- 廁所鑰匙像 mutex，三格停車位的剩餘名額像 semaphore。
- 別搞混：
- semaphore 不一定只允許一人，mutex 也不等同所有同步方法。
行程與執行緒
也會看到：process、thread、行程、執行緒行程是有獨立資源的執行容器，執行緒是容器內可被排程的工作路線。
- 生活例子：
- 一間餐廳像一個行程，裡面的多位廚師像多條執行緒。
- 別搞混：
- 共享同一行程資源不代表執行緒彼此不會衝突。
競爭條件
也會看到：race condition、data race多個工作同時碰同一資料，結果因執行先後不同而不穩定。
- 生活例子：
- 兩位店員同時修改同一張庫存表，最後數字可能覆蓋彼此。
- 別搞混：
- 多執行緒不必然有 race；關鍵是共享狀態且缺乏正確協調。
同步與活性問題
也會看到：critical section、livelock、starvation、busy waiting、Banker's algorithm同步保護共享區域；活性問題則包含大家互讓卻沒進展、某人長期拿不到資源或持續空轉等待。
- 生活例子：
- 像多人同時過窄門可能撞上、一直互相禮讓，或總有人被插隊。
- 別搞混：
- Livelock 仍在動但沒進展；starvation 是特定工作長期得不到機會，和 deadlock 不同。
從 race condition、critical section、mutex、semaphore 建立同步基本模型，再區分 deadlock、livelock、starvation 與 Banker's safety check。
先抓住這幾件事
- 以 interleaving 說明 race condition
- 區分 mutual exclusion 與 broader synchronization
- 列出 deadlock 四個必要條件
- 區分 deadlock、livelock、starvation、busy waiting
- 說明 Banker's algorithm 檢查 safe state 的目的
先想像這個場景
共用廚房的兩組廚師
兩組廚師共用一把刀、一個爐台和有限烤盤。沒有規則時會重複改同一張訂單；鎖太多又可能各拿一件工具互等，或不斷互相禮讓卻沒人下鍋。
先別急著往下看，花十秒想一想：
甲拿刀等爐、乙拿爐等刀；兩人都還在等待。這是一般排隊、starvation，還是 deadlock？若兩人不停互讓工具又立刻拿回呢？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 兩人同時修改同一張訂單 | Race condition | |
| 同一時間只准一人使用刀 | Mutex 與 critical section | |
| 三個烤盤最多供三組使用 | Counting semaphore | |
| 各持一件工具並等待對方手上的工具 | Circular wait 與 deadlock | |
| 不停互讓但始終沒完成料理 | Livelock |
題目出現這些字，先想到
- 看到 shared read-modify-write 結果不穩：找 race condition 與 critical section。
- 看到 semaphore purpose：同步／控制 permits；binary 可互斥，counting 可管理多份資源。
- 看到 processes 持續回應卻無 useful work：livelock；被卡住互等才是 deadlock。
- 看到 Banker's algorithm：deadlock avoidance、safe-state check，不是 CPU scheduling 或 detection。
1.Race condition 來自結果依賴不可控 interleaving
多個 threads 對 shared state 執行 read-modify-write，若操作非 atomic，不同 interleaving 可能產生不同結果。Critical section 是存取共享資源、需要控制同時進入的程式區段。
- Race 不要求真的同時執行
- 單核心也可因 context switch 發生
- Atomic operation 不會被觀察到中間狀態
- 先找 shared mutable state
2.Mutex 與 semaphore 解決的問題不完全相同
Mutex 通常有 ownership，同一時間只讓一個執行單元進 critical section。Semaphore 是整數同步原語，以 atomic wait/P 與 signal/V 調整 permits；binary semaphore 可做互斥，counting semaphore 可限制同時使用某類資源的數量或表達事件順序。
- Wait 在無 permit 時阻塞或等待
- Signal 釋放 permit／通知進度
- 鎖範圍過大降低 concurrency
- 同步設計不當仍可能 deadlock、starvation 或 livelock
3.Deadlock 四條件同時成立才可能形成
Coffman conditions 為 mutual exclusion、hold and wait、no preemption、circular wait。破壞任一必要條件可預防 deadlock；avoidance 則在每次配置前檢查是否仍能保持 safe state。Deadlock 中工作彼此等待，沒有任何一個能前進。
- 必要條件不是單獨充分條件
- 固定 lock ordering 可破壞 circular wait
- 一次申請全部資源可破壞 hold and wait
- 允許搶占只適合可安全復原的資源
4.Livelock、starvation 與 busy waiting 要分開
Livelock 中工作持續改變狀態、互相回應但沒有 useful progress；starvation 是特定工作長期得不到資源；busy waiting 是等待期間持續消耗 CPU 檢查條件。它們都影響 liveness，但機制不同。
- Deadlock 通常 blocked 且形成等待循環
- Livelock 活動中但不前進
- Fairness 可降低 starvation
- Spinlock 是有目的的短期 busy waiting
5.Banker's algorithm 問的是安全序列，不是當下是否 deadlock
Banker's algorithm 在 tentative allocation 後，檢查 available resources 是否能依某個順序滿足所有 processes 的 remaining maximum needs。存在 safe sequence 才核准配置；unsafe state 不等於已 deadlock，而是無法保證未來避免 deadlock。
- 需要知道 maximum claim
- Safe state 保證存在完成順序
- Unsafe 不代表現在已僵住
- 這是 avoidance，不是 detection
一起拆題目
範例 1：x=0，兩 threads 都執行 temp=x; temp=temp+1; x=temp。為何結果可能是 1？
- T1 與 T2 都先讀到 0
- 兩者各自在 temp 算成 1
- 兩次寫回都寫 1
- 其中一次 increment 被覆蓋
所以答案是：read-modify-write 非 atomic，發生 lost update race；應保護 critical section。
範例 2：P1 持有 A 等 B，P2 持有 B 等 A。辨識 deadlock 條件並給一種預防法。
- A、B 互斥使用
- 兩者 hold and wait
- 資源不可強制搶占
- 等待形成 P1→B→P2→A→P1 cycle
所以答案是：四條件皆成立；可規定所有 processes 一律先鎖 A 再鎖 B，破壞 circular wait。
這裡最容易選錯
- 把 mutual exclusion 與 synchronization 完全畫等號
- 認為用了 semaphore 就不可能 deadlock
- 把 livelock 說成 blocked 不動
- 把 unsafe state 直接說成已 deadlock
- 列出 Coffman conditions 卻說任何一條單獨就足夠
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1Race condition 的核心判斷是什麼？
多個執行單元存取 shared mutable state，結果會因不可控的 execution interleaving 而不同。
Read-modify-write 若非 atomic，可能發生 lost update；critical section 需受同步保護。
2Binary semaphore 與 counting semaphore 的用途差異？
Binary semaphore 可控制單一 permit、常用於互斥；counting semaphore 追蹤多個 permits，可限制有限資源的同時使用量。
Wait/P 與 signal/V 必須是 atomic；semaphore 也能表達事件順序。
3Deadlock 的四個 Coffman necessary conditions 是什麼？
Mutual exclusion、hold and wait、no preemption、circular wait。
四者同時成立才可能 deadlock；破壞任一條件可用於 prevention。
4Banker's algorithm 在配置資源前檢查什麼？
檢查 tentative allocation 後是否仍存在讓所有 processes 完成的 safe sequence，只在 safe state 才核准。
它是 deadlock avoidance；unsafe state 不表示當下已經 deadlock。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Computer Science: An Overview, 13th Edition — J. Glenn Brookshear
- 作業系統 — 周志遠