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有四種方針，以下依序討論：

Prevention

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

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，但還是要討論一下啦><，剩下的下篇見囉。