Ch8 Deadlock
8.1 System Model
在正常操作模式下，Thread只能按照以下順序利用資源(Resource)：
- Request：要求資源
- Use：使用資源
- Release：釋放資源
Deadlock定義：
當一組 threads 中的每一個 thread，都在等待某個事件，而該事件只能由同一組中的其他 thread 所觸發時，這組 threads 就處於 deadlock 狀態。
8.2 Deadlock in Multithreaded Applications
範例：
/* thread one runs in this function */
void *do work one(void *param)
{
pthread mutex lock(&first mutex);
pthread mutex lock(&second mutex);
/**
* Do some work
*/
pthread mutex unlock(&second mutex);
pthread mutex unlock(&first mutex);
pthread exit(0);
}
/* thread two runs in this function */
void *do work two(void *param)
{
pthread mutex lock(&second mutex);
pthread mutex lock(&first mutex);
/**
* Do some work
*/
pthread mutex unlock(&first mutex);
pthread mutex unlock(&second mutex);
pthread exit(0);
}
8.2.1 Livelock
Livelock 是另一種 liveness failure（活性失敗），與 deadlock 類似，但原因不同。
Livelock 的正式定義:
當一個 thread 持續嘗試某個動作，但該動作不斷失敗，導致無法前進時，就發生了 livelock。
舉例： 兩個人在狹窄走廊相遇：
- 一個往右閃
- 另一個往左閃，還是擋住
- 接著反方向再閃
兩人一直在動，但誰也沒真正通過
8.3 Deadlock Characterization
8.3.1 Necessary Conditions
要發生deadlock一定會有下列情形：
Mutual exclusion：一次只有一個process可以存取一個資源。Hold and wait：每個process手上都一定要有至少一個資源才能請求其他資源。No preemption：資源只能被自願釋放，不能用搶的。Circular wait：等待資源會繞成一圈（T1 -> T2 -> T3 -> T1）。