# Deadlock Detection

## Deadlock Detection

* 系統必須提供一個演算法去檢視是否有deadlock發生
* 需要一個演算法來回復deadlock

### single instance

* 當有cycle的時候會發生deadlock
* an edge from P~i~ to P~j~ 代表 P~i~ 在等 P~j~ 釋放一個 P~i~ 需要的資源
* 圖(b)叫做 wait-for graph


### several instance
* data structure
* Available
* Allocation
* Request
* $n \times m$ matrix
* `Request[i, j] = k` 代表P~i~ 正請求k個R~j~

1. Initialize

    Work = Available;
    for (i = 1; i <= n; i++)
        if (Allocation[i] != 0)
            Finish[i] = false;
        Finish[i] = true;

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

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

4. If `Finish[i] == false` , for some i, 1 ≤ i ≤ n, then the system is in deadlock state
* `Finish[i] == false` → P~i~ is deadlocked

---

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

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

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