# Deadlock

###### tags: `IT鐵人`

## 介紹

Deadlock是Multi-process常產生的問題，如果多個process同時在運作，那麼會產生爭奪Resource的行為，而這樣的行為可能就會導致Deadlock。

以下圖來說，每台車子都在等另一台開走，最終導致4台車都無法往前，這就是簡單的Deadlock概念。

## 原因

產生Deadlock有四個必要條件，只有滿足下面四個條件，Deadlock才可能發生，反之四個條件成立不一定會發生Deadlock。

|條件|敘述|範例|
|-|-|-|
|Mutual Exclusion|如果Resource在任何時間點，最多只允許一個process持有(使用)。|大多數Resource : CPU, Memory, I/O Device, etc|
|Hold & Wait|Process持有部分Resource且等待其他process有的Resource。|
|No Preemption|Process不可任意搶奪其他process持有的Resource，必須等待對方**自願釋放**後才有機會取得。|
|Circular Waiting|一組process形成循環等待的關係。||

## 與Starvation比較

Deadlock跟Starvation同樣導致process無法執行，不過兩者有不小的區別，以下做出比較：

|Deadlock|Starvation|
|-|-|
|系統中存在一組process形成Circular waiting造成這些process皆無法向下執行|process因為長期無法取得完工所需之Resource，以至於遲遲無法完工，有機會完工，只是機會渺茫|
|成立有4個必要條件|容易發生在不公平對待環境，且若有Preemption則更容易發生|
|若陷入Deadlock的process很多，則系統之產能低落|Starvation發生與效能無必然關係(SRTF)|

## 解決方法

要解決Deadlock有四種方針，以下依序討論：

### Prevention

我們可以想辦法破除必需的四個條件以確保Deadlock不會發生，不過有的條件破除的難度太高，以下把每一個條件各討論一次。

|條件|可行性|
|-|-|
|Mutual Exclusion|不行。太多Resource天生性質無法破除。|
|Hold & Wait|可行。規定只有可以一次拿到所有需要的Resource才可以擁有；要申請其他Resource前，要先放棄手中Resource。|
|No Preemption|可行。改為Preemptive即可，依優先權決定誰可以搶Resource。|
|Circular Waiting|可行。賦予Resource ID，必須依照ID順序持有。(解釋比較麻煩XDD)|

### Avoidance

不是破除Deadlock條件，而是在申請Resource時，OS會判斷有沒有可能發生Deadlock，假如有可能擇否決申請。

至於判斷的方式，是執行一個稱為Banker's Algorithm，這個做法先對process定義5個參數，Request代表申請的各式Resource數量，MAX代表完成工作所需之最大各式Resource數量，Allocation代表目前持有的各式Resource數量，Need代表尚需的各式Resource數量，Available代表OS目前可用的Resource數量。

如果Request的數量小於Need數量，則代表申請合理，反之直接無情拒絕；再判斷Request是否小於Available，可以才會進行下一步計算，反之則要求process等待。


前面的流程大概是這樣，至於下一步的計算因為較為麻煩，就不在這邊說明了，概念上是計算如果給予process申請的Resource，如果是safe state才可以執行，反之可能造成Deadlock的unsafe state則暫時拒絕之。

### Deadlock Detection & Recovery

這種做法就是不多加限制，讓Process任意取得Resource，不過OS要能夠偵測目前是否有Deadlock存在，如果發現有則執行Recovery破除Deadlock，恢復正常狀況。

不過偵測的方式牽涉到比較麻煩的演算法，就不特別說明了。而復原的方式則是一個一個終止process直到破除Deadlock，或是把某個process的Resource搶過來，並將她回復到拿到Resource之前。

### Ignore

這個就是完全不理會Deadlock，發生卡住的狀況OS就直接介入終止程式之類的。

雖然這個做法聽起來超不負責任，不過UNIX系統基本上都採用這種方式，畢竟Deadlock發生的頻率少之又少，忽視的影響也很小，也可以省去其他方法耗費的大量成本。

Deadlock的內容就到這邊為止了，因為程式執行的時間很迅速，以至於現實生活中很少發生Deadlock，但還是要討論一下啦><，剩下的下篇見囉。

|上一篇|下一篇|
|--|--|
|[Thread](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/BymiTFdmK)|[Process Synchronization](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/BJezizwVY)