# Chp 8 Deadlock

###### tags: `作業系統`

## P.5 Deadlock Characterization
<font color='red'>必考</font>
1. **Mutual exclusion**
only one process at a time can use a resource
2. **Hold and wait**
HOLD resources & WAIT to acquire resources held by the others
3. **No preemption**
The resources can only be released after the process completes its task.
4. **Circular wait**
$P_0\text{ waits }P_1, P_1\text{ waits }P_2,...,P_n\text{ waits }P_0$

## P.7~11 Resource-Allocation Graph

### Definition
* set of process $P$ and set of resource $R$ form vertices
* Edges
- request edge $P_i \rightarrow R_i$
- assignment edge $P_i \leftarrow R_i$

>[color=#00a000]
>
>下2張圖的差異在circular wait是否可以被打破(?)
>[name=Omnom]

>[color=#FF00FF]回樓上
>不是，下面兩張圖是在說就算是有cycle的情形，只要resource不只一個instance，就不全然會發生deadlock。
>對於只有一個instance的resource來說，只要有cycle就必然會發生deadlock。第12頁有簡單的列出幾項原則。
>[name=Neko]



## P.13

>[color=#00a000]
>
>第3種方法能說是handle嗎www
>[name=Omnom]

>[color=#FF00FF]回樓上:
>然而他是最被廣泛使用的方式
>附帶一提，他有一個專有名稱叫做鴕鳥演算法，Ostrich algorithm
>[name=Neko]

>[color=#00a000]
>
>回樓上：
>沒想到這也是種演算法😮
>此外[維基的參考](https://zh.wikipedia.org/wiki/鸵鸟算法)我給過😂
>[name=Omnom]

## P.14, 15 Deadlock Prevention

避免滿足[前面](#P.5-Deadlock-Characterization)所提到的四種deadlock必要條件

1. Mutual Exclusion: 針對不可share的資源一定要遵守
2. Hold and Wait: 必須保證process在要求資源的時候他沒有持有任何其他資源。
3. No Preemption: 當process持有某資源並要求其他無法馬上取得的資源時，他必須放下所持有的所有其他資源並重新要求。
4. Circular Wait: 對所有資源強行安排一個順序並規定Process要按照資源的順序發出要求。

## P.16, 17

Deadlock formed by Line 3,4 & Line 12,13

/* 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);
}

透過lock ordering避免deadlock

void transaction(Account from, Account to, double amount) {
   mutex lock1, lock2;
   lock1 = get_lock(from);
   lock2 = get_lock(to);
   acquire(lock1);
      acquire(lock2);
         withdraw(from, amount);
         deposit(to, amount);
      release(lock2);
   release(lock1);
}

## P.18 Deadlock Avoidance

Deadlock prevention是指想辦法使deadlock發生的四要素至少一個不要出現。
Deadlock avoidance則是指系統在分配資源的時候參考resource allocation的狀況等等資訊，決定是否要將資源分配給某些Process。接下來要描述的就是deadlock avoidance的一種實踐。

## P.19~21 Safe state

通俗的說safe state就是這個系統可以在沒有發生死鎖的情況下將資源給有需要的process。

比較正式的說法如下：
If $\exists$ sequence $\{P_i\}_{i=1}^n ~ s.t. ~ \forall P_i$, "available resources" + "resources held by all $P_j$ with $j<i$" meet the request from $P_i$

也就是說這個系統可以找到一個process sequence，使得序列中的某個process $P_i$ 可以得到$P_i$自己已經持有的以及在$P_i$之前的process結束執行後所釋放的資源。

要注意的是，safe state的system為deadlock free，但是unsafe system不一定會發生死鎖。

>[color=#00a000]
>
>透過講義圖示以及簡單的if-then敘述可以得知
>[name=Omnom]

## P.23~26 Resource-Allocation Graph Algorithm
針對只有一個instance的resourceRAG可以參考[前面](#P.7~11-Resource-Allocation-Graph)
這個方式要能夠運作的前提是，Process在能夠要求任何資源之前就要把他可能會要求的所有資源畫上claim edge，在執行的過程中也只能對已經畫上claim edge的資源發要求。


當process釋放掉資源的時候，會由assignment edge轉為claim edge
當process要求資源的時候，會由claim edge轉為request edge
只有在由request edge轉為assignment edge不會產生cycle的時候才能將資源給該process。

>[color=#00a000]
>
>這裡弱弱地問一下，
>所以系統在判斷時，會允許process先發送request，然後再判斷是否有cycle嗎？
>[name=Omnom]

>[color=#00a000]
>
>虛線部分是claim edge，
>assign的時候會將虛線變成反向的實線
>可以看到如果將$R_2$優先給$P_2$，
>則可能產生deadlock。
>因此應當先將$R_2$優先給$P_1$
>[name=Omnom]

## P.27~33 Banker’s Algorithm (by Dijkstra) (待修)

## P.36 Wait-for Graph
Only set of Process forms vertex set