iT邦幫忙

1

【小黑馬作業系統教室】(17) (Ch7)Deadlock(死結)

嗨嗨,大家好,我是心原一馬,
今天要介紹作業系統裡的一個重要議題: Deadlock(死結)

deadlock圖解

簡單來說,deadlock就是在process之間,
相互等待其它process資源的情況,
以致於所有的process都無法繼續執行。
上課投影片有一張交通阻塞圖,
非常生動的比喻了deadlock的情況。

https://ithelp.ithome.com.tw/upload/images/20200102/20117114K8Sc5dP0BW.png

看看這些在十字路口的車輛,形成了一種
「我等你過,你等他過,他等我過」的局面,
所有車輛都動不了。

deadlock的四個必要條件

deadlock要發生要滿足以下四個必要條件(也就是若缺少一項就不可能會deadlock):

  • Mutual exclusion: 同一時間同個資源只能被一個process所用
  • Hold and wait: process手上可以握有資源並等待其它process的資源
  • No preemption: process手上的資源只能是自願放掉的,不能被其它process搶走
  • Circular wait: 存在多個process(P0, P1, ..., Pn)互相等待資源的情形(P0等P1的資源,P1等P2的資源,…,Pn等P0的資源)

我們可以用上方的「交通阻塞圖」,
生活化地解釋這四個必要條件:

  • mutual exclusion: 路寬只能有一輛車通行
  • Hold and wait: 車子占領十字路口,並等待橫向車輛先過去
  • No preemption: 車子不準插隊(不像現實中救護車、消防車可以直接插隊)
  • Circular wait: 不同路段的車子循環的等待

如何預防deadlock?

在課堂中,共介紹三種預防deadlock的方法,
分別是:

  • Deadlock prevention
  • Deadlock avoidance
    雖說從英文看這兩個詞相當接近,
    但是指不同預防deadlock的方式。

1. Deadlock prevention

Deadlock prevention指的是透過避開Deadlock的四個必要條件,
來阻止deadlock的發生。

  • 避開 Mutual exclusion:在一些允許共享資源的程式上,可不需要Mutual exclusion,例如read-only file。
  • 避開 Hold and wait:所有程式不允許手上占著資源,程式必須一次拿走工作所需的資源。但缺點是資源利用率會很底。
  • 避開 Preemption: 讓process手上的資源是允許被其它程式搶走的
  • 避開 Circular waiting:假設我們有R0,R1,…,Rn這n+1種資源,process在申請要資源Rk之前,必須把編號大於k的資源都放掉,避免循環等待。

2. Deadlock avoidance

Deadlock avoidance又細分為以下兩種:

Resource-allocation graph algorithm

我們可以將程式之間擁有資源及等待資源的關係,
以圖示視覺化的畫出來。
例如:
https://ithelp.ithome.com.tw/upload/images/20200102/20117114UV3TkHKo3N.png
這張圖表示有三個process P1,P2,P3,
有四種資源 R1,R2,R3,R4,
其中R1與R3各有一個,
R2有兩個,
R4有三個。

箭頭P->R(圖中的紫色箭頭)表示P在等待資源R,
箭頭R->P(圖中的綠色箭頭)表示P擁有資源R。

Resource-allocation graph algorithm指的便是檢查這張graph是否有形成cycle,
只有沒有cycle,即確定不可能產生deadlock(也就是程式之間不會互等)。
以本圖為例是沒有cycle的。(P1在等P2,P2在等P3)

(重要)Banker's algorithm

當程式提出資源的申請時,
透過一個叫做「Banker's algorithm」的演算法檢查程式是否會進入「unsafe state」,
如圖示:

https://ithelp.ithome.com.tw/upload/images/20200102/20117114h4qyUJtkfZ.png

safe state是絕對不可能發生deadlock的情形,
unsafe state是有可能發生deadlock的情形,
若允許程式提出資源的申請會進入「unsafe state」,
便拒絕該程式的申請。

進一步說,safe state指的是至少存在一個順序可以保證讓所有程式依序執行完畢(當程式執行完便會歸還資源),
這個能讓所有程式依序執行完畢的順序稱為「safe sequence」。

舉例說明:
假設我們全部共有- 資源A: 5個、資源B: 5個,資源C: 5個,
P0,P1,P2,P3四支程式,
對於每支程式最大需求的資源及目前手上握有的資源如下表:

程式 Max Allocation
A B C A B C
P0 4 2 3 2 1 1
P1 2 5 3 0 0 2
P2 3 5 1 0 1 0
P3 3 2 1 2 0 0

此時P3申請要資源「A: 1個、C: 1個」,
能不能夠通過申請呢?
此例是可以的,
詳細過程如下:

若P3申請要資源「A: 1個、C: 1個」通過,
此時四支程式「最大需求的資源」及「目前手上握有的資源」及「最多需要拿多少資源」如下表:

程式 Max Allocation Need
A B C A B C A B C
P0 4 2 3 2 1 1 2 1 2
P1 2 5 3 0 0 2 2 5 1
P2 3 5 1 0 1 0 3 4 1
P3 3 2 1 3 0 1 0 2 0

扣掉四支程式手上擁有的資源,目前剩下「資源A: 0個、資源B: 3個,資源C: 1個」。
接下來存在safe sequence <P3,P0,P2,P1>,
步驟1. P3最多需要資源「A: 0個、B: 2個、C: 0個」,當前有資源「A: 0個、B: 3個、C: 1個」,
資源足夠,先給P3用,P3用完之後歸還手上資源,此時共有「A: 3個、B: 3個,C: 2個」
步驟2. P0最多需要資源「A: 2個、B: 1個、C: 2個」,當前有資源「A: 3個、B: 3個、C: 2個」,
資源足夠,給P0用,P0用完之後歸還手上資源,此時共有「A: 5個、B: 4個,C: 3個」
步驟3. P2最多需要資源「A: 3個、B: 4個、C: 1個」,當前有資源「A: 5個、B: 4個、C: 3個」,
資源足夠,給P2用,P2用完之後歸還手上資源,此時共有「A: 5個、B: 5個,C: 3個」
步驟4. P1最多需要資源「A: 2個、B: 5個、C: 1個」,當前有資源「A: 5個、B: 5個、C: 3個」,
資源足夠,給P1用,P1用完之後歸還手上資源。

因此,程式必定能夠以<P3,P0,P2,P1>的順序執行完畢,為safe sequence。


尚未有邦友留言

立即登入留言