# Dead lock
:::danger
複習用
:::spoiler

[TOC]
:::

## 定義

可以運用汽車塞車了

process之間互相搶奪資源，雙方都無法運行，造成了CPU效能大幅度下降
### Dead lock & Starvation
:::info

**Dead lock**:必須要等到 前面 process 用完成之後或是放棄了下一個才能使用
:::
:::info
**Starvation**: 會有優先順位的差別
如果這是又是可以搶先的那情況就會更亂了
:::
## Dead lock 四項必要條件
### Mutual exclutoin (resource are non-shareable)
:::info
可以用列表機來想 一次只能列印一份文件
在一個時間內，只能有一個行程在使用資源
:::
### Hold and wait (持有並等待)
:::warning
排隊排到了才能上車
:::
### No preemption (不可搶先)
:::warning
不能當流氓插隊
:::
### Circular waiting (循環式等待)
**single process 不會發生**

## 處理方法
### Dead-Lock Prevention(預防)

:::warning

太預防&保護造成性能下降
:::
:::info

魚與熊掌 一次只能吃得一個
:::
:::warning
利用反證法來說明
**只要以上方法可以愈deadlock的發生**
:::
#### 優缺點
:::danger
**優點:保證系同不會有死結發生
缺點:系統效能低(Utilization)**
:::
:::success

### Dead-Lock Avoidance (避免)
:::info
房屋貸款是否合理
當提出不合理要求時 OS 會kill請求(unsafe 得情況就會發生 deadlock)
所以下方會產生 banker algo
:::
##### Banker Algo
[银行家算法](https://zh.wikipedia.org/wiki/%E9%93%B6%E8%A1%8C%E5%AE%B6%E7%AE%97%E6%B3%95)
設所有 process 在 set P 中；n 為 process 數目，m 為資源種類。

一維陣列：
:::info

- Requests_i[m] : process i 提出的資源申請量。
- Available[m] : 系統目前各類資源的可用數量。
- Finish[n] : 各個 process 是否完成。
:::
二維陣列：
:::info
- Allocation[n,m] : 目前各 process 持有的資源量。
- Max[n,m] : 各 process 需要多少資源才可以完成工作。
- Need[n,m] : 還要多少資源才可以完成工作。 (Need = Max - Alloc)
:::

###### 虛擬碼:

while( Finish is not all TRUE ){
    found = FALSE;
    foreach (i in process set P) {
        if ( Need[i,:] <= Avail ) {
             Avail = Avail + Alloc[i,:];
             P = P - {i};
             found = TRUE;
        }
    }
    if (!found) return FAIL;
}
return OK;

###### 例題：
:::spoiler

// 基本變數設置

 Allocation　　　Max　　　Available
 　　ＡＢＣＤ　　ＡＢＣＤ　　ＡＢＣＤ
 P1　００１４　　０６５６　　１５２０　
 P2　１４３２　　１９４２　
 P3　１３５４　　１３５６
 P4　１０００　　１７５０

// 算出 need

 NEED
 ＡＢＣＤ
 ０６４２　
 ０５１０
 ０００２
 ０７５０

// 宣告確認是否完成的變數

 FINISH
 false
 false
 false
 false

// loop : 持續找出可以釋放的 process 並更新 finish
// 直到找不到或 finish 全為 true

 NEED　  　Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ０５１０<-
 ０００２
 ０７５０

 NEED　　  Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ００００　＋１４３２
 ０００２－－－－－－－
 ０７５０　　２９５２

 FINISH
 false
 true
 false
 false

:::
### Dead Lock Avoidance的重要定理
:::success
假設系統包含m個單一種類的Resources，且被n個Process共用。如果
下列兩個條件滿足，則系統無死結存在 (Dead Lock Free)。

1 ≤ Maxi ≤ m
ΣMaxi < m + n

:::warning
有6部印表機提供給n個process使用，每個process之最大需求量為2。
在系統不發生Dead Lock的情況下，最多允許多少個process在系統內
執行? (求n的最大値)
:::spoiler
$7<n$
:::
### Deadlock Detection

:::success
Allow system to enter deadlock state.

Detection algorithm :
:::info
Single instance : topological sort (using wait-for graph)
- 使用 adjcent matrix : O(n^2^)
- 使用 adjcent list : O(V+E)
:::
###### Several instance : 用 Banker algorithm 判斷系統是否已經在 unsafe state

### Recovery scheme
:::info
- 終止 process (成本都高)
1. 全部刪除
2. 一次刪一個process，直到打破 deadlock。
- 哪個行程我們應該先中斷?
:::
:::info
- 資源搶奪
1. 剝奪 victim process 資源 (可能造成 starvation)
2. 恢復無該資源前狀態 (cost 高)
:::
#### Resource preemption
:::info
- 選一個受害者去preempt
- which one to preempt?
- rollback
- checkpoint
- 部份rollback或全部rollback?
- starvation
- 可以同一個行程被preempted?
:::
### [重要] Resource allocation graph
:::success
Some facts about RAG :

- If graph contains no cycles => no deadlock.
- If graph contains a cycle
- one instance <=> deadlock.
- several instances, possibility of deadlock. ( deadlock => cycle )