# Deadlock avoidance

## Deadlock avoidance
* 可以利用演算法避免deadlock
* safe state
* a save sequence {P~1~, P~2~, ..., P~n~}
* P~i~最多可以請求的資源數 = available resources + resources held by all P~j~ , with j < i
* unsafe state
* may lead to a deadlock
* not all unsafe states are deadlocks




* Ex: P~2~在t~1~時多拿了一個資源

## Resource-Allocation-Graph Algorithm

* For **one instance** of each resource type only
* A direct edge from P~i~ → R~j~ is called a request edge
* A direct edge from R~j~ → P~i~ is called a assignment edge
* claim edge
* P~i~ → R~j~ 代表 P~i~ 未來某個時間點可以請求 R~j~
* 虛線表示
* 當P~i~請求R~j~，P~i~ → R~j~會轉換成request edge(實線)
* 當P~i~釋放R~j~， assignment edge R~j~ → P~i~ 會轉換成claim edge
* P~i~ 開始執行之前，所有的claim edge都要出現在圖上

* 如果edge的方向轉換後會造成cycle，就不能讓請求成立


## Banker's Algorithm
* For **multiple instance** of each resource type

* Data structure

* n = number of processes
* m = number of resources types
* Available
* 長度為 m 的一維陣列
* `Available[j] = k` 代表R~j~有k個可用資源
* Max
* $n \times m$ 的二維陣列
* `Max[i, j] = k` 代表P~i~最多可以請求 k 個 R~j~ 資源
* Allocation
* $n \times m$ 的二維陣列
* `Allocation[i, j] = k` 代表 P~i~ 已經有 k 個 R~j~
* Need
* $n \times m$ 的二維陣列
* `Need[i, j] = k` 代表 P~i~ 需要再 k 個 R~j~ 才能完成任務

* `Need[i, j] = Max[i, j] - Allocation[i, j]`
* P~i~ 需要的 R~j~ 資源數 = P~i~ 最多可以請求的 R~j~ 數 - P~i~ 已經有的 R~j~ 數

### Safety algorithm
* 用來決定一個<font color="orange">特定狀態是不是safe</font>

1. Initialize
* Let Work and Finish be vectors of length m and n
* `Work = Available`
* `Finish[i] = false`, i = 0, 1, ..., n-1

2. Find an i
* `Finish[i] = false` && Need~i~ ≤ Work
* 如果i不存在，跳到4

3. 可以執行
* `Work = Work + Allocation[i]` process釋放資源
* `Finish[i] = true` 工作完成
* 回到2

4. 如果 `Finish`中全部都是 true，代表系統現在是 safe state

### Resource-request algorithm

* 用來決定一個<font color="orange">新的請求是不是safe</font>，如果是safe就讓它執行

1. If Request~i~ ≤ Need~i~ go to step 2
* Request~i~不能比Need~i~大，否則會超過P~i~最多可請求的資源數

2. If Request~i~ ≤ Available~i~ go to step 3
* If not, P~i~ must wait

3. $Available = Available - Request_i \\ Allocation_i = Allocation_i + Request_i \\ Need_i = Need_i - Request_i$
* 可用資源被該process請求資源扣掉
* 該process所佔有的資源增加
* 該process還需要的資源減少
* 如果結果是safe → 把資源給P~i~
* 如果結果是unsafe → wait

---

##### last edit
> [name=dot] [time=Tue, Jul 28, 2020 10:38 PM]

[HOME PAGE](/bKDZoNkrT9SOBnTvY_aj2Q?edit) :no_entry_sign:

{%hackmd theme-dark %}
###### tags: `OS` `CSIE`