1.概念
deadlock
1.a set of blocked process each holding a resource and
2. waiting to acquire a resource held by another process in the set
deadlock characterization
發生deadlock時以下四個特性會同時出現
mutual exclusion(互斥): 資源在同一時間只允許一個process使用
no preemption: 其他process無法強制取得資源
hold and wait: p1要使用一些資源,但部份資源要等到其他process用完,造成p1暫時無法執行
circular wait(循環等待): p1等待p2資源,p2等待p3資源,p3等待p1資源
………………………………………………..
resource-allocation graph
用來檢查是否有deadlock的方法
若形成cycle,會有deadlock的風險
若形成cycle,並符合deadlock4特性的其中一種,會發生deadlock
常用於deadlock avoidance algorithm
resource-allocation graph定義
圖形由以下集合構成
vertices V
edges E
V有以下兩類型
P={P1,P2,…Pn} 表示process
R={R1,R2,…Rn} 表示resource
動作
process要求resource時,Pi->Rj
process正使用resource時, Pi<-Rj
…
wait-for graph
類似resource-allocation graph
但vertices V中只有process
常用於deadlock detection algorithm
…………………………………………………………………
2.handling deadlock 策略
主要有以下大三種
1無法進入deadlock狀態
deadlock prevention
deadlock avoidance
2允許deadlock發生,但會事後補救的做法
deadlock detection and recovery
3忽略
大部份作業系統採該方法
………………………
deadlock prevention
可避免deadlock，但resource utilization會降低
主要方法為避免deadlock各特性的其中一種成立
如下
mutual exclusion prevention
有些資源無法適用該方法
該方法很困難
hold and wait prevention
not wait: process要有能力一次取得所需要的所有資源，才可申請資源
not hold: process要釋放掉所資資源後，才可申請資源
no preemption prevention
改為preemption讓process可preemption
ps:preemtpion可能引發starvation問題
可應用在cpu register或memory space等資源
較難應用在printer或磁帶機等資源
circular wait prevention
給各resource唯一的ID，process只能以遞增的方式申請resource
ex:p已有resource3，那p不能申請resource1,2，只能申請4之後的resource
………………………
deadlock avoidance
透過algorithms動態的檢查state，以確保不發生deadlock
state包括
safe state:不會發生deadlocks的情況
unsafe state:可能發生deadlock和會發生deadlock兩種的情況
依resource type有以下兩種avoidance algorithms
single instance
resource-allocation graph algorithm
multiple instances
banker’s algorithm
banker’s algorithm
需要O(m*n^2)，較耗時
資料結構
available[r]：各resource還有多少可用
max[p,r]：各process各需要幾個resource
allocation[p,r]：各process各自擁有的resource，會隨時間變化而變動
need[p,r]：目前各process還各需要幾個resource，會隨時間變化而變動
主要流程
1. resource-request algorithm 決定資源的分配
2. safe algorithm 判斷是否仍在安全狀態
ex:
所有資源為10,5,7，而各process需求如下
p: allocation/max = need
p0: 0,1,0/7,5,3 = 7,4,3
p1: 2,0,0/3,2,2 = 1,2,2
p2: 3,0,2/9,0,2 = 6,0,0
p3: 2,1,1/2,2,2 = 0,1,1
p4: 0,0,2/4,3,3 = 4,3,1
計算方式如下
available: 3,3,2 =10-(0+2+3+2+0),5-(1+0+0+1+0),7-(0+0+2+1+2)
step1
1) available3,3,2 > p1的1,2,2 所以配給p1
2) p1完成後歸還資源2,0,0
3) available: 5,3,2 =10-(0+0+3+2+0),5-(1+0+0+1+0),7-(0+0+2+1+2)
step2
1) available5,3,2 > p3的0,1,1 所以配給p3
2) p3完成後歸還資源2,1,1
3) available: 7,4,3 =10-(0+0+3+0+0),5-(1+0+0+0+0),7-(0+0+2+0+2)
step3
1) available7,4,3 > p4的4,3,1 所以配給p4
2) p4完成後歸還資源0,0,2
3) available: 7,4,5 =10-(0+0+3+0+0),5-(1+0+0+0+0),7-(0+0+2+0+0)
step4
1) available7,4,5 > p0的7,4,3 所以配給p0
2) p0完成後歸還資源0,1,0
3) available: 7,5,5 =10-(0+0+3+0+0),5-(0+0+0+0+0),7-(0+0+2+0+0)
step5
1) available7,5,5 > p2的6,0,0 所以配給p2
2) p0完成後歸還資源3,0,2
3) available: 10,5,7 =10-(0+0+0+0+0),5-(0+0+0+0+0),7-(0+0+0+0+0)
最後根據safe algorithm檢查
配置順序若為p1,p3,p4,p0,p2屬於safe state
………………………
deadlock detection and recovery
資源utilzation較高,throughput可提昇
偵測時機
當process無法立刻要到資源
定期偵測:ex:每小時偵測一次
cpu使用率低的時候 ex:cpu使用率低於20％時
依resource type有以下兩種方法
single instance
週期性的搜尋是否在wait-for graph有cycle
演算法複雜度為n^2
several instance
使用detection algorithmI(類似bank’s algorithm)
detection algorithm
data structure
available[r]
allocation[p,r]
request[p,r]
ex:
所有資源為7,2,6，而各process需求如下
p: allocation/request
p0: 0,1,0 / 0,0,0
p1: 2,0,0 / 2,0,2
p2: 3,0,3 / 0,0,0
p3: 2,1,1 / 1,0,0
p4: 0,0,2 / 0,0,2
偵測p0,p2,p3,p1,p4順序是否正常
計算如下
p0,request=0,
釋放p0資源, work(0,1,0)=work(0,0,0)+allocation(0,1,0),finsh[0]=1
p2,request=0,
釋放p2資源﹑ work(3,1,3)=work(0,1,0)+allocation(3,0,3),finsh[2]=1
p3,request!=0,且request(1,0,0) 釋放p3資源,work(5,2,4)=work(3,1,3)+allocation(2,1,1),finsh[3]=1
p1,request!=0,且request(2,0,0) 釋放p1資源,work(7,2,4)=work(5,2,4)+allocation(2,0,0),finsh[1]=1
p4,request!=0,且request(0,0,2) 釋放p4資源,work(7,2,6)=work(7,2,6)+allocation(0,0,2),finsh[4]=1
finish[0]~finish[4]都為1，該序列無deadlock
recovery from deadlock
若detection algorithm偵測到deadlock則解決
主要有以下兩方法
process termination
中斷所有deadlock process
中斷所有process直到deadlock被排除
resource preemption
rollback回到safe state