- Deadlock
- Deadlock’s 4 necesary condition
- Deadlock v.s. Starvation
- Resource Allocation Graph (R.A.G)
- Deadlock prevention
- Deadlock avoidance
- Deadlock detection & recovery
Deadlock basic
一組Processes彼此形成Circular waiting之情況，造成這些Processes皆無法往下執行，並降低Throughput 之現象，稱為Deadlock。
Deadlock’s 4 necesary condition
以下4個必要條件(necesary condition)缺少一個，死結必不發生。
反之，若滿足這4大條件也不一定有Deadlock。
- Mutual Exclusion
這是對Resource而言，具有此性質的Resource，在任何時間點，”最多只允許一個Process持有/使用，不可多個Processes同時持有/使用 ”，例:大多數的資源皆具有此性質 : 例:CPU、Memory、Disk、Printer…，不過 Read only file 不算在內
2. Hold & Wait
Process持有部分資源，且又在等待其他Process所持有的資源
3. 不可搶先(No Preemption)
Process不可任意剝奪其他Process所特有的資源，必須等對方自願釋放資源後，才有機會取得資源
Note : 若為preemptive，必無Deadlock，頂多只有Starvation
4. Circular Waiting
System中存在一組Process形成循環等待之情況。
Deadlock v.s. Starvation
Resource Allocation Graph
令 G=(V,E)為有向圖，代表RAG
其中，
- 圓圈代表Process
- 方框代表Resource，而方框內的點即為資源數量
- Edge分為兩種 :
<Some facts about RAG>
- 如果RAG內，沒有cycle →沒有Deadlock
- 如果RAG內，有cycle
→ Only one instance ，必有 deadlock
→ Several instances， 不一定有deadlock
Deadlock 的處理方法
- Deadlock prevention
- Deadlock avoidance
- Deadlock detection & recovery
Deadlock Prevention
只要使deadlock's 4 個必要條件之一無法成立，便能夠預防deadlock。
- Mutual Exclusion
無法，因為Resource”與生俱來(Inherent)”之性質無法破除
2. Hold & Wait :
[法一] 規定:除非Process可一次取得全部所需資源，才准許持有資源，否則不得持有任何資源。
[法二] 規定:Process可先持有部分資源，但當Process要申請其他資源時，必須先釋放持有的部分資源，才可提出申請
3. No Preemption
改為Preemption即可，Ex: Based on priority-level(根據priortiy拿資源)
Note 可能會造成 starvation。
4. Circular Waiting
[方法] — " Resource ordering "
(1) OS會賦予每一類型資源一個unique(唯一的)Resource ID
(2) OS會規定Process必須依照資源ID Ascending(遞增)方式對資源提出申請
e.g.
<prove it works>
Deadlock Avoidance
當 process 提出資源申請時，OS 會執行Banker algorithm 來判斷系統在「假設核准該申請後」是否處於 Safe state，是則核准，否則process 等待。
- safe state : 存在 safe sequence
- unsafe state : 可能有 deadlock
Banker Algorithm
設所有 process 在 set P 中；n 為 process 數目，m 為資源種類。
一維陣列：
- Request[m] : process i 提出的資源申請量。
- Available[m] : 系統目前各類資源的可用數量。
- Finish[n] : 各個 process 是否完成。
二維陣列：
- Allocation[n,m] : 目前各 process 持有的資源量。
- Max[n,m] : 各 process 需要多少資源才可以完成工作。
- Need[n,m] : 還要多少資源才可以完成工作。 (Need = Max-Alloc)
<Procedure>
l. Check Request[i] ≤Need[i] ?[要的會不會太過分]
若成立，則goto 2，否則，終止Pi(因為申請不合格)
2. Check Request[i] ≤Available[i] ? [系統可以給嗎 ?]
若成立，則 goto3，否則，Pi waits until Resource available.
3.[試算]… [那就給給看]
Allocation[i] = Allocation[i] + Request[i]
Need[i] = Need[i]-Request[i]
Available[i] = Available[i]- Request[i]
4.依上述試算值，執行” Safety Algorithm” [給看看之後看會不會影響大家]
若回傳” SafeState ”，則核准Pi此申請
若回傳” UnsafeState”，則否決Pi之申請，Pi需等一段時間，才能再重新提出申請。
Safety Algorithm
除了上述之外，另外加入:
l. int : Work [1:m]=> 表示System目前可用Resource 之累積數量
2. Boolean : Finish [1:m] => True表Pi可以完工; False表Pi無法完工
<Procedure>
1.設定初值 Work= Available, Finish[i]皆為 False (1 <is n)
2.看可否找到Pi滿足(1)Finish[i]為 False,且(2)Need[i]≤ Work,若可以找
到,則 goto 3.; 否則 goto 4.
3.設定 Finish[i]=True, 且 Work = Work + Allocation, then go to 2.
4. Check Finish array,若皆為True,則傳回”Safe”State,否則回傳”Unsafe”
State
Example
Deadlock Detection&Recovery
如果放任Resource使用較無限制,雖然Utilization 高,但System有可能進入 Deadlock而不自知,所以需要一個Deadlock偵測演算法,及萬一偵測出有Deadlock,如何破除Deadlock(也就是Recovery)的作法。
Deadlock Detection Algorithm
基本上與上述Banker+safety Algorithm十分雷同，
Recovery 作法
1. Kill process in the Deadlock :
[法一] kill all processes in the Deadlock(成本太高、先前工作成果作廢)
[法二] kill process one-by-one : kill 一個process後,再跑偵測演算法,若仍有 Deadlock存在,再重覆kill。(一樣是成本太高:且loop次數*偵測成本)
2. Resource Preemption :
(1)選擇”Victim” Process
(2)剝奪他們身上的資源
(3)回復此Process當初未取得此剝奪資源的狀態:困難、成本太高、也可能會 Starvation
Example.以下都有可能可以解決Dead lock
- Kill some ready process
- Delete some files from the disk
- Swap out some inactive processes
