和春技術學院資訊管理系 九十三學年度第一學期 系統程式 第三章 死結(Deadlock) 教學投影片 課程網頁 講師：毛立仁

第三章 死結(Deadlock) 3-1 死結的定義與發生之條件 3-2 死結的預防(Deadlock Prevention) 3-1　死結的定義與發生之條件 3-2　死結的預防(Deadlock Prevention) 3-3　死結的避免(Deadlock Avoidance) 3-4　死結的偵察(Deadlock Detection) 3-5　死結的復原 (Deadlock Recovery)

3-1 死結的定義與發生之條件 1.在一個資源有限的多程式系統中，因同時有多個處理單元在系統內執行，而處理單元彼此間又競相爭用系統內的資源，造成處理單元彼此間所需求的資源相互被對方所佔，卻又無法釋放，致使所有等特資源的處理單元皆無法繼續執行，這種現象稱這些處理單元處於死結狀態 (Deadlock)。

用簡要的方式定義死結如下： 在多程式系統中，有一群處理單元 (至少2個) 皆在等待某個事件 (Event)的發生，但每個處理單元所等待的事件卻只能由其它的處理單元來產生，造成所有的處理單元都在等待，導致所有的處理單元永遠停滯的現象。

死結發生的四項必要條件 (必須四項均發生才會發生死結，缺少其中一項便不會產生死結)： (1)互斥條件(Mutual Exclusion Conditon)：至少含有一資源 (Resource) 為非共享的 (Nom- Sharable)；即每次僅允許一個處理單元獨佔該資源，直到工作完成才釋出該資源。 (2)持有並等待條件 (Hold and Wait Condition)：處理單元把持已分配給它的資源，而又正在等待其它處理單元所佔用的資源。

(3)不可搶用條件 (Nonpreemptive Condition)：除非處理單元已完成其工作，並釋放出資源；否則，其已經分配得到的資源無法被其它的處理單元所奪取。 (4)循環等待條件 (Circular Wait Conditon)：處理單元各自佔用一些資源，而彼此間又互相在等待對方的資源。例如：有三個處理單元P1 , P2與P3，其中 P1 在等待 P2 所佔有的資源，P2 在等待 P3 所佔有的資源，而 P3 卻在等待 P1 的資源。

3.死結的處理：當系統發生死結後，系統內的某些處理單元將永遠停滯，造成系統效能降低，甚至於整個系統停滯，此時可能需要藉助於系統操作員強制刪除某些處理單元，甚至於必須要關閉系統重新開機。

3-2 死結的預防(Prevention) 1. 在系統內要發生死結必須讓互斥、持有並等待、不可搶用與循環等待四個條件同時發生，所以只要四讓個條件中的任何一個條件不成立，則死結便無從發生。死結預防的就是藉此觀念，只要使四個死結發生條件中的任一條件不成立，使得死結不會發生。

2. 預防死結發生的方式即是否定四個死結發生條件中的任何一個，但無需四個全部否定掉。在此所謂的預防就是對四個死結發生的條件中資源使用的方式加以規範，只要處理單元使用資源時能依循環此規範，則保證不會發生死結。對於每個條件的否定方式分述如下：

(1)使互斥條件不成立：某些資源的本質便是不具有共享性的 (Sharable)，故此條件有時是無法除去的。例如：印表機無法被兩個處理單元同時執行列印。

(2)使等待條件不成立：處理單元必須一次取得所有需求的資源才能執行；否則，必須等待並釋出目前所持有的資源。例如：處理單元A在執行時需要光碟機、硬碟機與印表機，它依序已取得光碟機與硬碟機，當它再要求印表機時，系統發現印表機已經配置給正在執行中的處理單元B，此時，處理單元A先前所取得之光碟機與硬碟機必須全部釋出，並使處理單元A進入等待狀態。

(3)使不可搶用條件不成立：若某處理單元所需之資源正被另一個等待中的處理單元所佔用，則此資源允許被搶用。即處於等待中的處理單元其所佔用的資源皆可被搶用。例如：處理單元A在執行時需要光碟機、硬碟機與印表機，它依序取得光碟機與硬碟機，同時，處理單元B已取得印表機，如果處理單元B因為需從外界輸入資料而進入等待狀態。此時，如果處理單元A要求系統給予印表機，則處理單元B原先配置的印表機可被處理單元A所搶用。

(4)否定循環等待條件：將各資源型態依序予以編號，當處理單元要求某一資源時，則其所要求資源之編號必須大於任何一個已分配給該處理單元之資源編號；否則，該處理單元必須釋出所有已分配的資源。這種技術稱為資源順位法 (Resource Ordering)。

如果有某個處理單元其在執行時會使用到光碟機、硬碟機與印表機，則其在要求資源時必須按照光碟機、硬碟機、印表機之順序才能順利取得所需的三種資源。如果是先取得硬碟機，再取得印表機後，最後才要求光碟機，則其之前所取得之硬碟機與印表機皆必須釋放出來，並重新依順取得硬碟機與印表機。

<補充說明>：在一般正常狀態下，處理單元利用系統資源的過程為: (1)處理單元要求(Request)、 (2)系統配置資源(Allocation)、 (3)處理單元使用資源 (Use) 與(4)處理單元釋放資源 (Release)。 (1)要求資源 (Request)：處理單元在使用資源前必須對系統發出要求，如果該要求資源已被其它的處理單元所佔用，致使要求無法馬上獲准，則該處理單元必須等待直至該要求獲准。 (2)配置資源 (Allocation)：處理單元所要求的資源已獲准，系統將處理單元要求的資源提供予處理單元。 (3)使用資源 (Use)：處理單元取得系統配置的資源後，便可對該資源進行操作。 (4)釋放資源 (Release)：當處理當元不再需要該資源或處理單元執行完畢時，會將資源歸還予系統。

3-3 死結的避免(avoidance) 由於死結預防的主要觀念是於對資源使用上的限制，導致資源的使用率不佳。死結的避免(avoidance)則是允許死結發生的條件存在，但隨時注意在分配資源時，必須避免死結的發生。一個簡單而有效的模式便是要求每個處理單元於執行前必須先聲明其所需要每種型式資源的最大需求量，並在要使用資源時先向系統提出請求，則系統可定義出避免死結的方法，又可動態地檢查資源配置的狀態，以確保系統不會產生循環等待的狀況。

3-3 死結的避免(avoidance) (1)每個處理單元需事先聲明所需要各種型式資源的最大需求量。 最著名的死結避免方法即是戴斯卓拉 (Dijkstra) 的銀行家演算法 (Banker‘s Algorithm)。其方式如下所述： (1)每個處理單元需事先聲明所需要各種型式資源的最大需求量。 (2)若處理單元所需要之各種型式資源之最大需求量皆小於目前該型式資可使用的總數量，則系統可接受其需求。 (3) 在分配資源給處理單元時，必須先檢查分配後是否使系統處於安全狀態。若可使系統處於安全狀態，則分配資源給該處理單元；否則，令該處理單元進入等待狀態。

死結的避免(avoidance) (Banker‘s Algorithm)

銀行家演算法 (Banker‘s Algorithm)安全狀態 對於上述之安全狀態的判定方式如下： a. Allocation (i)：表示第 i 個處理單元目前已分配到的資源數目。 b. Max (i)：表示第 i 個處理單元所要求資源的總數量。 c. Need (i)：表示第 i 個處理單元尚需要的資源數量；即 Need (i) = Max (i) - Allocation (i)。

d. Available：表示系統中尚未使用的資源數目。即 e. 若對每一個處理單元 Pi，使得 則表示系統內這幾個處理單元是處於安全狀態。

<註>：(e) 之涵義為若是目前系統內尚未使用的資源數量 Available 可以滿足系統內某一個處理單元 Pj 完成工作尚需要的資源數量 Need (j)，則一旦 Pj 完成工作後，會釋放出其原先已分配的資源數量 Allocation (j)，使得系統內尚未使用的資源數量變為 Allocation (j) + Available。依此類推 若能逐一滿足系統內每一個處理單元 Pi 完成工作尚需要的資源數量 Need (i)，則此系統是處於一個安全狀態 (Safe State)。

P 則， Available = 10 - (1+4+3) = 2。 處理單元 P 已配置 最大需求量 (Process) (Allocation) (Max) A 1 4 B 6 C 3 8 則， Available = 10 - (1+4+3) = 2。

(Need = (Max - Allocation)) 處理單元 需 求 量 (Need) (Process) (Need = (Max - Allocation)) A 3 = (4-1) B 2 = (6-4) C 5 = (8-3) 依目前系統的可用資源數量檢查 Available = 10 - (1+4+3) = 2 ，可發現執行順序為 BCA 或 BAC 時，可滿足安全狀態。 而 對每一個處理單元 Pi，使得: 則表示系統內這幾個處理單元是處於安全狀態。

如果此時處理單元 C 要求給予 2 部磁碟機，系統是否會答應其請求呢？答案是不會的。因為如果給予處理單元 C 所要求的 2 部磁碟機，則系統狀況為: 因系統內所有磁碟皆已配置 Available = 10 - (1+4+5) = 0 ，已無任何磁碟機可再供使用，導致處理單元A、B與C皆無法繼續執行。故如果答應處理單元 C 之請求，則將造成系統進入不安全狀態。

<補充說明>：何謂安全狀態 (Safe State) 呢？它是指系統將目前系統所擁有之可用資源，並將資源依循著某一種次序配置給每一個處理單元，可以讓每一個處理單元皆順利執行完成，而不會產生死結。反之，系統目前剩餘之資源無法依循某一次序配置資源給每個處理單元，讓每個處理單元都能順利執行完畢，此種情況則稱之為不安全狀態。 系統只要處於安全狀態必定不會產生死結，只要是系統產生死結時，系統必定處於不安全狀態。但是系統處於不安全狀態時，是否會發生死結呢？答案是不一定。

 範例：若系統中含有 10部磁碟機，３個處理單元共同使用這些磁碟機，其情況如下表所述： 得知，Available = 10-(1 + 1 + 6) = 2 此時，若處理單元 C 發出給予一部磁碟機之請求，系統經檢查不會導致不安全狀態，故配置一部磁碟機給處理單元 C。 之後 Available = 10-(1 + 1 + 7) = 1 Need for A, B , C = 4-1, 6-1, 7-7 = 3, 5 , 0

Available = 10-(1 + 1 + 7) = 1 假設處理單元 C 需執行相當長的時間才能執行完畢，在此時處理單元 B 也發出給予一部磁碟機之請求，系統發現目前僅一部磁碟機可用(因處理單元C仍在執行尚未釋放出佔用的7部磁碟機)，系統依目前狀況檢查發現，如答應處理單元 B 之請求，將導致系統進入不安全狀況。試想如果系統答應處理單元 B 之請求並配置一台磁碟機給處理單元B，雖然系統進入了不安全狀態，但也只是暫時性的，一旦處理單元 C 執行完畢，又會回到安全狀態。所以不安全狀態並不意味著死結的發生。

上述之銀行家演算法是針對單一種資源型態之測試方式，但如果系統中有多種資源型態時，則上述之演算法應修改如下：若系統中有 m 種資源，n 個處理單元 (Process) 正在執行，則所需要的資料結構為: a. Available 陣列，長度為 m。Available [j] = k 表資源 j 尚有 k 個可用。 b. Max 矩陣，其大小為 n × m。它用來定義各處理單元對各種資源的最大需求量。Max [i,j] = k，表示處理單元 Pi 要求資源 j 之最大數量為 k。 c. Allocation 矩陣，其大小為 n × m。它用來定義現在每一處理單元所佔用各類型資源的數量。Allocation [i,j] = k，表處理單元 Pi 佔用 k 個資源 j。 d. Need 矩陣，其大小為 n×m。它用來表示出每一處理單元剩餘的需求量。若 Need [i,j] = k，表示處理單元 Pi 還需要 k 個資源 j。 e. Need [i,j] = Max [i,j] - Allocation [i,j] Allocationi 為一向量 (Vector)，表示 Pi 佔用各種資源的數量。 Needi 為一向量，表示 Pi 還需要各種資源的數量。 Requesti 為一向量，表示 Pi 現在要求再給予各種資源的數量。

範例：系統內有 A, B, C 與 D四種資源，有P1、P2 與P3 三個處理單元，已知系統內 A, B, C與 D 四種資源(Available)之數量分別為9, 8, 7 與 6。 P1對 A, B, C 與 D四種資源之最大需求量(Max)分別為1, 2, 3, 4 P2對 A, B, C 與 D四種資源之最大需求量(Max)分別為2, 1, 2, 1 P3對 A, B, C 與 D四種資源之最大需求量(Max)分別為4, 3, 2, 1 假設目前系統已配置 A, B, C 與 D 四種資源給 P1、P2 與 P3 之情況為(Allocation)： P1已配置 A, B, C 與 D 四種資源的數量分別為 1, 1, 1, 1 P2已配置 A, B, C 與 D 四種資源的數量分別為 1, 0, 1, 0 P3已配置 A, B, C 與 D 四種資源的數量分別為 2, 2, 0, 0 在某個時候，P3 請求系統給予1個 A 資源、2個B資源及1個D資源。

Allocation1 = (1, 1, 1, 1)，表示目前P1已配置 A, B, C 與 D四種資源的數量分別為1, 1, 1, 1 Request3 = (1, 2, 0, 1)，表示 P3 對系統要求給予A, B, C與 D資源數量各為1, 2, 0, 1

當處理單元 Pi 要求再給予資源時，其處理之方式如下： 1 若 Requesti ≦ Needi , Goto 2，否則發出錯誤訊息； 2 若 Requesti ≦ Available , Goto 3，否則令處理單元 Pi 等待； 3 Available = Available - Requesti Allocationi = Allocationi + Requesti； Needi：= Needi - Requesti； 再利用下述安全演算法 (Safety Algorithm) 檢查是否為安全狀態。若安全，則配置資源給 Pi ；否則 Pi 必須保持舊有的狀態，等待 Requesti 的滿足。 <註>：Requesti ≦ Needi 所表示的意思為 Requesti 向量內的每一個元素皆小於等於 Needi 向量內相對應位置上的元素。如： (1, 2, 3, 4) ≦ (1, 3, 4, 5) 成立。 (1, 2, 3, 4) ≦ (4, 1, 5, 9) 不成立。 同理，對於 Reuuesti 與 Available 之比較亦是相同之觀念。

安全演算法 (Safety Algorithm):假設 Work 陣列長度 m，Finish 陣列長度為 n，其中 m 為系統資源的種類，而 n 為系統內處理單元的數量。 Work 也是一個向量，它是安全演算法運算過程中用來紀錄在目前之狀況下整個系統各種資源可用的數量。例如：有A, B 與 C三種資源，其目前可用的數量分別為1, 2 與 3，則Work = (1, 2, 3)。 Finish 也是一個向量，它是用來紀錄目前系統中所有的處理單元是否完成。例如：有4個處理單元P1、P2、P3 與P4，若目前P1與P4　已完成，而P2與P3未完成，則Finish = (true, false, false, true)。

安全狀態演算法 Safety Algorithm 1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work = Available Finish [i] = false for i - 1,3, …, n. 2. Find an i such that both: (a) Finish [i] = false (b) Needi  Work If no such i exists, go to step 4. 3. Work = Work + Allocationi Finish[i] = true go to step 2. 4. If Finish [i] == true for all i, then the system is in a safe state.

 安全演算法步驟如下: (1)令 i = 1,2,...,m (m 個資源), Work [i] = Available [i]； 對於所有的 j = 1,2,...,n (n process),Finish[j] = false； (先預設每一處理單元皆未完成) (2)任意尋找一個 i 滿足 (Ⅰ) Finish [i] = false 且 (Ⅱ) Needi ≦ Work (即找尋一個尚未完成的處理單元，且目前系統內的可用資源足以供應其需求),若 i 不存在，則 Goto (4) (3)Work = Work + Allocationi；(即將目前可用資源與處理單元 i 所釋出的資源相加，成為處理單元 i 完成後系統中可使用的數量) Finish [i] = true (將處理單元i 設定為完成) Goto (2) (4)對於所有的 i，若 Finish [i] = true，則此系統處於安全狀態 (即所有的處理單元皆可順利完成)；否則，此系統處於不安全狀態。 <註>： Finish[i] = true 表示處理單元 Pi 可以順利完成其工作。所以，當所有的 Finish[i] (i=1,2,...,n) 皆為 true 時，表示所有的工作皆能順利完成。

 範例：假設系統中有4個處理單元 P1、P2、P3 與 P4，3種資源 A，B與 C，其數量分別為 9，6 與 7。其目前各個處理單元之最大需求，配置與需求描述如下：

可求得 Available = (4，4，5)，若目前 P2 向系統請求給予 A，B與 C 資源之數量分別為 1，1，1，則系統是否會答應其請求？ 先假設系統答應其請求之狀況如下：

則 Available = (3，3，4) 依循安全演算法之步驟演算如下：  Work = Available = (3，3，4) Finish = (false，false，false，false)  選取 P4  Work = (4，3，4)，finish = (false，false，false，true)  選取 P2  Work = (7，4，5)，finish = (false，true，false，true)  選取 P1  Work = (7，5，5)，finish = (true，true，false，true)  選取 P3  Work = (9，6，7)，finish = (true，true，true，true) 所有的處理單元 P1、P2、P3 與 P4 皆可順利完成，系統處於安全狀態。 因此系統可以答應 P2 之請求。

 範例：若系統中含有 3 種型態之資源 A，B 與 C，其數量分別為 11，6，8。假設有 5 個處理單元 (Process) 正於此系統中使用這些資源，其狀態如下： Allocation Max A B C 1 2 7 6 3 4 9 5 則 Available [A] = 11 - (3 + 3 + 2) = 3 Available [B] = 6 - (2 + 1) = 3 Available [C] = 8 - (2 + 1 + 1) = 3

發現存在一個執行順序 24531 可以滿足安全狀態。 而每個處理單元尚需之各資源為 Process Need A B C 1 7 4 3 2 6 5 發現存在一個執行順序 24531 可以滿足安全狀態。

3-4 死結的偵察 系統內如果為了防止死結的發生，可採用死結預防的方式，但卻會造成資源使用率降低的缺失﹔如採用死結避免的方式，則處理單元必須事先宣告資源的最大使用量，似乎不太實際，所以有些系統並無採用防止死結發生的措施，而是當死結發生後再行處理。

在系統內若無採取死結預防或死結避免的措施來防止死結的發生時，則必須在死結發生時能予以偵查並恢復，以使系統能正常的運作。但什麼時候應該進行死結偵查呢？系統內是否有死結發生是難以確切得知的，所以死結的偵測一般是定期性的偵測或是當系統效能降至某一警戒值時便啟動死結偵察。

死結偵察之方法通常僅檢測循環等待的條件是否成立，但允許其他三項死結條件的發生。其目的在於尋找出發生問題之處理單元與資源，再藉由死結復原之方式將死結從系統中清除，藉以消除死結。 死結的偵察一般是採用資源分配圖 來觀察是否有循環等待的情況發生，藉以判斷是否有死結形成 (但只適用於各種型態資源的數量都只有一個) 。在資源分配圖形中，方形節點表示處理單元，大圓圈節點表示同一型態之資源，大圓圈內小圓圈的數量表示該型態資源之數量。

茲以下列四個圖例說明處理單元與資源間的關係。

2.死結偵察的方法： (1)偵察的方法是採用圖形化簡 (Graph Reduce) 的方式來檢測。若一個處理單元所要求的資源能夠滿足，則將資源分配給處理單元的箭號去除，再移掉由處理單元至資源的箭號，依此步驟重覆操作，若圖形中所有的處理單元均可化簡，則表示不會產生死結狀態；否則，表示會造成死結。

 範例：下圖每個處理單元均可順利的化簡，故不會產生死結。

<註>：若同一型態資源的數量都只有一個時，則一旦發現有循環等待必表示發生了死結。若同一型態資源的數量有一個以上時，則發現有循環等待未必表示發生了死結；反之，發現了死結必表示有循環等待的情況發生。

(2)另一種方式是將資源分配圖轉換成等待圖再進行檢查等待圖中是否有循環等待的情況發生 (只能用於各種資源數量都為1)。至於如何將資源分配圖轉換成等待圖的方式則描述如下：

 範例： 請將下述之資源分配圖轉換成等待圖。

根據上述 (a)、(b) 兩個規則，可轉換成如下之等待圖

3-5 死結的復原(recovery) 死結復原的做法是取消某一個或多個處理單元的執行，以中止循環等待之情況。但是如果隨意的中止 (或刪除) 處理單元，可能中止 (或刪除) 的並非是形成死結的處理單元，造成資源的浪費 (因處理單元之前所執行的全都無效了)，所以，配合死結偵察決定出形成循環等待之處理單元，再對該些處理單元逐一中止，直至循環等待不復存在。

但這也有可能面臨到另一個問題，可能每次形成死結時，所中止的處理單元都是同一個 (被中止的處理單元可能優先次序(Priority) 較低，每次都是被犧牲者)，而產生飢餓現象(Starvation) (即無限延遲)。

要具有死結復原的功能，則系統中應具有中止/恢復 (Suspend/Resume) 之功能。當死結發生時可暫時的中止 (Suspend) 一些處理單元，等待系統無死結之顧慮時，再予以恢復 (Resume) (因處理單元被中止後，經過一段時間又會再被執行，所以必須將該處理單的PCB儲存，以便再執行時能接續之前被中斷之處)。這便是檢查點/重新開始 (Checkpoint/Restsart) 特性。

(1)檢查點 (Checkpoing)： 在中止 (Suspend) 時，將系統目前之狀態予以儲存，以便從新開始 (Restart) 時使用。 (3)餓死 (Starvation)：在選擇犧牲者時，可能某一處理單元總是被選中，使得這個處理單元可能永遠無法完成它的工作稱為餓死。

(4)無限期延遲 (Indefinite Postponement)： 系統分配資源或安排處理單元優先順序時，可能因偏重某些處理單元，使得其它的處理單元一直在等待，而無法執行的情況，稱為無限期延遲。此種情形和死結一樣嚴重，但是該處理單元仍有機會完成其工作，而死結則是永遠無機會完成其工作。