這幾天的核心想法幾乎都是：
多個 Thread 會碰到 Shared State，那就建立 Synchronization Rule，避免大家毫無限制地同時操作。例如使用 Mutex：

pthread_mutex_lock(&mutex);
counter++;
pthread_mutex_unlock(&mutex);

可以避免：同時修改 counter造成的 Race Condition。所以看起來 Lock 越多，程式應該越安全才對。
但不是這樣
假設系統裡只有lockA、B，而thread 1、2都分別持有lockA、B，下一步卻要互換，這時：誰都不會動了。
這就是：Deadlock

1. Deadlock 到底是什麼？它和「程式跑很慢」有什麼不同？

它描述的是一組執行者彼此等待某些資源或事件，而形成一個無法自行繼續的等待關係。
這次要講的就是： (Circular Wait)

• Thread A
  持有 Lock 1
  等待 Lock 2
• Thread B
  持有 Lock 2
  等待 Lock 1

(2)Deadlock 是怎麼一步一步形成的？假設：

pthread_mutex_t lockA;
pthread_mutex_t lockB;

Thread 1：
pthread_mutex_lock(&lockA);
pthread_mutex_lock(&lockB);
/* do something */
pthread_mutex_unlock(&lockB);
pthread_mutex_unlock(&lockA);

Thread 2：
pthread_mutex_lock(&lockB);
pthread_mutex_lock(&lockA);
/* do something */
pthread_mutex_unlock(&lockA);
pthread_mutex_unlock(&lockB);

-1假設執行順序是：Thread 1
lock(A) → 成功 (B → Free)
-2接著 Scheduler 讓 Thread 2 執行：Thread 2
lock(B) → 成功
-3接著 Thread 1：lock(B)，但是 B 在 Thread 2 手上，Thread 1 被 Block。
-4接著 Thread 2：lock(A)，但是 A 在 Thread 1 手上。問題正式形成。

2. 但是Bug 是否發生，可能和 Thread Interleaving 有關。

如果執行順序稍微不同，Thread 1 可能已經先把兩把 Lock 都拿到並釋放，程式就完全正常。
只有某些 Interleaving(也就是上面的例子)：
T1：拿 A
T2：拿 B
T1：等 B
T2：等 A
才會 Deadlock，這個部分和之前的 Race Condition 有一個共同的討厭之處，都有可能和Thread Interleaving有關。

3. Deadlock 的四個必要條件是講什麼？

Deadlock 有四個非常經典的必要條件，通常稱為 Coffman Conditions：

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

為什麼這四件事情同時存在，Deadlock 才有可能形成？

• 第一個 Mutual Exclusion：某項資源在同一時間不能被所有人任意共享使用。
  例如 Mutex：假設一個資源可以被所有人同時使用：
  Lock A
  │
  ├── Thread 1 可以持有
  │
  └── Thread 2 想拿 → 必須等
  也就是：有人拿到之後，其他競爭者必須等待。

如果**彼此不排斥，就不會因為「誰佔有這個資源」形成這類 Deadlock。**所以 Deadlock 需要某些：Exclusive Resource

• 第二個 Hold and Wait：一個執行者已經持有某些資源，同時又繼續等待其他資源。
  Thread 1：
  Hold A
  Wait B
  │
  ▼
  Thread 2：
  Hold B
  Wait A
  環就開始形成了。

• 第三個 No Preemption：系統不能直接把已經分配出去的某些資源強制從持有者手上搶走，而必須等持有者自己釋放。例如：
  Thread A：持有 Mutex A
  Thread B 很需要 A。
  系統不能直接說：Thread A，你的 Mutex 我先沒收，現在給 Thread B。
  如果這時硬把 Lock 搶走：可能處於不一致狀態
  所以 Mutex 一般需要：Owner 自己 unlock
  這就是 No Preemption。

• 第四個 Circular Wait：存在一圈等待關係。
  Thread A
  等待 B 的 Resource

Thread B
等待 C 的 Resource

Thread C
等待 D 的 Resource

Thread D
等待 A 的 Resource

A → B → C → D
↑ │
└───────────┘
只要這一圈裡：每個人都必須等下一個人，就沒有人能先完成。

它們是必要條件，不是「只要看到其中一個就一定 Deadlock」。

4.Deadlock 到底要怎麼處理？

(1)Deadlock Prevention：

直接破壞必要條件。既然 Deadlock 需要四個必要條件，那最直接的想法就是：
我保證至少有一個條件不成立。
最常見的方式之一：固定 Lock Ordering
-Thread 1：
lock(A)
lock(B)
-Thread 2 也：
lock(A)
lock(B)
這樣就比較不容易形成：Thread 1：A → 等 B / Thread 2：B → 等 A
這其實是在破壞：Circular Wait形成的可能性。

(2)Deadlock Avoidance：

每次分配前先判斷會不會走進危險狀態，Avoidance 的思路不同，**在真正分配 Resource 前，先判斷這次分配之後，系統是否仍然處於可以安全完成所有工作的狀態。**OS 課本最經典的就是：

Banker's Algorithm

1.目前有多少 Resource？
2.每個 Process 已經拿多少？
3.最多還可能需要多少？
4.如果現在再分配，剩下的資源能不能讓某些 Process 完成？
如果分配後仍然存在一個可以讓所有 Process 最終完成的順序，稱為：Safe State
否則可能進入：Unsafe State

注意：

Unsafe State 不等於「現在已經 Deadlock」。

它代表的是：系統已經失去「保證所有工作都能完成」的安全性，未來某些資源請求順序可能導致 Deadlock。

(3)Detection + Recovery：

我不事先阻止所有可能的 Deadlock，但我會檢查是否真的發生。例如系統偵測到：
Process A
Process B
Process C形成無法解除的等待。
接著可能採取 Recovery：終止某個 Process。或是回收 / 搶占某些 Resource、Rollback 某些工作，藉此打破等待關係。
當然這些方法都有代價：例如直接殺掉 Process，工作可能遺失 / 資料可能需要復原

5. Deadlock、Starvation、Livelock 解釋一下關係

我剛開始學的時候會把Deadlock、Starvation的構成事件搞混....

(a)Deadlock：大家互相等，沒人能前進

(b)Starvation：別人一直有飯吃，只有你餓死

假設今天系統有：
Thread A
Thread B
Thread C
大家都在搶一個 Resource。Scheduler 或 Lock 的策略一直讓：
A → 成功
B → 成功
A → 成功
B → 成功
A → 成功
Thread C：我呢？？？C 長時間甚至無限期拿不到自己需要的執行機會或資源。這叫：Starvation

(c)Livelock：大家都很忙，但事情就是做不完

假設系統裡有theadA、B
Thread A：
發現衝突
→ 釋放資源
→ Retry

Thread B：
發現衝突
→ 釋放資源
→ Retry

Thread A：
又衝突
→ Retry

Thread B：
又衝突
→ Retry

一直有動作，但沒有有效 Progress

今天的結論

(1)Deadlock 不是單純：程式卡住，而是一種特定的資源等待問題
(2)而經典的四個必要條件是：

1. Mutual Exclusion
   → 資源不能任意同時共享

2. Hold and Wait
   → 拿著一些資源，又等待其他資源

3. No Preemption
   → 已分配資源不能隨便強制搶走

4. Circular Wait
   → 等待關係形成一個環
   **四個條件同時成立Deadlock → 才有可能形成 **

(3)處理 Deadlock 的思路可以是：
Prevention
→ 直接破壞必要條件

Avoidance
→ 分配前判斷是否仍處於 Safe State

Detection
→ 允許發生，再偵測

Recovery
→ 發生後終止、回收或復原

(4)三個OS常發生的問題比較
Deadlock
→ 大家互相等，無法自行前進

Starvation
→ 別人一直前進，某個人一直拿不到機會

Livelock
→ 大家一直動，但沒有真正完成progress

回到 OS 最重要的工作之一：CPU Scheduling
下一篇：

Day 14｜CPU Scheduling：100 個 Thread 都想跑，OS 到底先選誰？