iT邦幫忙

2021 iThome 鐵人賽

DAY 25
0
自我挑戰組

杰哥的考研紀錄系列 第 25

Day-25 Deadlock

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 Process Synchronization


上一篇
Day-24 Thread
下一篇
Day-26 Process Synchronization
系列文
杰哥的考研紀錄30

尚未有邦友留言

立即登入留言