Deadlock pretention預防死結

1.Mutual exclusion:對不可共用的資源類型而言，互斥一定成立，而可共用的資源類型，因為可以同時讀取相同檔案，所以一定不會產生。
2.Hold and Wait:process必須保證一個行程在要求一項資源時，不可以佔用任何其它的資源。
3.No preemption:只要某個處理元要不到所要求的資源時，便把它已經擁有的資源釋放，然後再重新要求所要資源。
4.Circular Wait:確保循環式等候的條件不成立，我們對所有的資源型式強迫安排一個線性的順序。

Deadlock Avoidance死結的避免

為了確保死結不會發生，我們定義一個安全的狀態--能夠分配給所有process資源而不會造成死結，在不安全的狀態下則有可能發生死結，假設我們知道系統目前可用的資源數量(Available)、各process對資源的最大需求量(max)、各process目前持有的資源量(allocation)、各系統還需多少資源(need) = max - allocation

Safety演算法:

定義:

1.Work[1..m]: 表示系統目前可用資源數量之累計

2.Finish[i]的值: True：Pi已完成工作

              False：尚未完成工作

判斷:

step

1.Work = Available

Finish[i] = False, 1≤i≤n

2.找出Pi，滿足兩個條件:

(1)Finish[i] = False

(2)Needi≤Work

若可以找到，到step3，否則到step 4

3.設定Finish[i] = True且Work = Work + Allocationi

到step2

4.檢查Finish陣列，若皆為True，則系統處於Safe State，否則處於Unsafe State

Note:

存在≥1組"Safe Sequence"使得processes依此順序執行，皆可完成工作就是安全的狀態，如果找不出一組Safe Sequence就是在不安全的狀態。

Resource_Allocation_Graph演算法結論:

在資源為多樣(multiple instances):

沒有循環就沒有死結，有循環不一定有死結，但如果所有資源皆為單一量(single instance)，則有cycle就有死結。

Banker's演算法:

假設n為process數目，m為resource數目

定義:

1.Request_i[1..m] :Process_i的資源申請量
EX:Request_i[j] = k，表Pi申請k個Resourcej(Rj)

2.MAX[1..n,1..m] :表示各process對各類資源的最大需求量
EX:MAX[i,j] = k，表示Process_i對於Resourcej(Rj)的最大需求量為k

3.Allocation[1..n,1..m] :表示各process目前持有的資源量
EX:Allocation[i,j] = k，表示processi(Pi)目前持有k個Resourcej(Rj)

4.系統資源總量 Available[1..m]

Available_i = 資源總量- Allocation_i

5.Process需求量Need[1..n,1..m]

Need_i = MAX_i - Allocation_i

判斷:

Steps:

1.檢查Request_i ≤ Need_i
若不成立，則OS終止此process
否則到step2

2.檢查Request_i ≤ Available
若不成立，則Process_i必須wait直到Resource Available
否則到step3

3.計算
Allocation_i = Allocation_i + Request_i
Need_i = Need_i - Request_i
Available = Available – Request_i

4.執行"Safety Algorithm"
如果系統判斷會處於Safe state則核准申請，不行則否決此次申請，稍後再重新申請

此演算法所需時間太多，不可能應用在實務上，共花費:O(nnm)