About Deadlock

今天就來整理一下，這個在求職階段經常會遇到的面試考題－死結 (Deadlock)

Deadlock，簡單來說就是一個怎麼都解不開的鎖，發生的情境為 process 之間在執行時，互相競爭需求的系統資源，在資源互不相讓的情況下，造成死結的發生，而互不相讓的程度需要滿足以下四個必要條件 :

1. Mutual Exclusion
2. Hold and Wait
3. No Preemption
4. Circular Wait

必須要滿足這四個條件，這個結才算是解不開的死結，缺少一個項目，系統還有辦法調配被 process 占用的資源，下面我們就來細講這四個條件。

Mutual Exclusion — 互斥

這裡的互斥指的是資源互斥，亦即一個資源一次只能夠被一個 process 使用，這個條件隱含的問題是，當資源先被占用，其他的 process 就必須等占用資源的 process 執行完畢後，才有機會獲得資源使用。

Get Ying Tung Wu’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

這裡舉一個銀行的例子，ATM 每天凌晨會暫停提款服務，並在該時段進行資料同步，而銀行之所以設定凌晨更新，是因為資料同步會占用大量資源，且資料同步是不能夠被中斷的，所以才挑選 ATM 服務使用率較低的時間點進行，若是資料同步發生在白天，提款機使用率高峰期進行同步，這樣所有資源都因資料同步而鎖定，這時候就會有 ATM 無法讀寫資料，而服務停擺的情況。

Hold and Wait — 持有並等待

這裡指的是 process 的行為，當 process 順利取得資源之後，發現要完成任務需要取得另外一項資源，才有辦法繼續後面的流程，這時候有兩個情況，如果所需的另一項資源沒人使用，process 就可以很順利的取得另一個資源進行後續流程；相反地，若是另一項資源正在被占用，那該 process 也只能執行禮貌運動，乖乖地去排隊等待另一項資源被釋放。說到著，最一開始 process 持有的資源還在手上，並未釋放也未使用，同時他又在排隊等待另一項資源，粗俗一點的說法，這個行為就是...占著茅坑不拉屎的概念。

No Preemption — 誰都不准搶

我們可以把 process 看做胖虎，今天胖虎不肯把麥克風給別人，誰都別想搶。也就是 process 跟 process 之間，誰都不能搶走誰的資源的情況下，再加上前述兩個條件，根本就是 process 流氓了。

Circular Wait — 循環等待

前述三個條件滿足的情況下，還不能算是死結的原因在於，事情總有完成的時候吧，事情完成後 process 就會釋放資源，釋放資源後下一個 process 就可以承接資源，接力完成任務。但若是 process 之間所需的資源被握在對方手上，如下方例子，形成誰也不可能先完成任務並釋放資源的局面，再加上胖虎的強勢，造就死結的發生。

process 1 : 持有資源 A、等待資源 B

process 2 : 持有資源 B、等待資源 A

以上四點，就是死結發生的必要條件說明。其實面試的時候能夠寫出這四項，基本上這題應該就得分了，只是這四個條件用背的，常常在寫的時候就是少一項… (這絕對是我個人的問題)，求職時，面試考題基本上，還是跟我碩士畢業時考得差不多，當年練到當申論題寫，現在已經不能相信自己的金魚惱了，所以用理解的可能對求職永續發展會更好…? 雖然這東西在工作上經常性是用不到的，但可能還是想看看大家有沒有好好研讀恐龍本吧。

下回見