Chapter 7 死結(Deadlocks) 7.1 系統模型 7.2 死結的特性 7.3 處理死結的方法 7.4 預防死結 7.5 避免死結 7.6 死結的偵測 7.7 自死結恢復

7.1 系統模型 (System Model) 在正常運作的模式之下，一個行程只能依據下列的順序來使用資源︰ 1.要求(request)︰行程要求資源。若此要求不能立即 被認可，則行程必須等候以獲得此資源。 2.使用(use)︰行程能夠使用此資源。 3.釋放(release)︰行程釋放資源。

7.2 死結的特性(Deadlock Characterization)

佔用與等候(hold and wait):必須存在一個至少已佔用一個資源且還等候其它已被佔用資源之行程。 7.2.1 必要條件 死結問題發生的四個充要條件︰ 互斥(mutual exclusion):至少有一資源必須是不可共用的型式，換言之，一次只有一個行程可使用此資源。若有另一行程想使用這資源，則必須延遲至此資源被釋放後才可以。 佔用與等候(hold and wait):必須存在一個至少已佔用一個資源且還等候其它已被佔用資源之行程。 不可搶先(no preemption):資源無優先權;因此，一個資源只能被佔用它的行程在完成工作目標之後，才被釋放。 循環式等候(circular wait):必須存在一等候行程的集合{P0, P1, ...,Pn}，其中P0等候的資源已被P1佔用，P1所等候的資源已被P2佔用，Pn-1所等後的資源已被Pn佔用，而Pn所等候的資源已被P0佔用。

7.2.2 資源配置圖(Resource-Allocation Graph) (instances)

If graph contains no cycles  no deadlock If graph contains a cycle  if only one instance per resource type, then deadlock if several instances per resource type, possibility of deadlock

7.3 處理死結的方法(Methods for Handling Deadlocks) 在理論上，有三種不同處理死結的方法 1.可以使用某一協議，以預防或避免死結，並保證系統絕不會進入死結狀態。 2.可以允許系統進入死結狀態，偵測出來再想辦法恢復之。 3.可以忽視此問題，假裝系統從沒發生過死結。 預防死結 (deadlock prevention)是一組可以確保死結四個必要條件至少有一項不會發生的方法。這些方法藉由限制對資源的要求來避免死結發生。 避免死結(deadlock avoidance)則要求作業系統預先能取得，一個行程在它的生命期將會要求及使用那些資源。有了這些資訊之後，我們可以決定，此行程的每一要求是否該等待。

7.4 預防死結 (Deadlock Prevention) 互斥(mutual exclusion) 對不可共用的資源型式來說互斥的條件必定成立。 佔用與等候 必須保證一個行程在要求一項資源時，不可以佔用任何其它的資源。 不可搶先 已經配置出去的資源不可被別的行程搶先佔用。 循環式等候 確保循環式等候的條件不成立，我們對所有的資源型式強迫安排一個線性的順序。

7.5 避免死結(Deadlock Avoidance) 安全狀態(Safe State) 系統能以某種順序將其資源分配給各行程且仍能避免死結者，則稱其狀態為安全 (safe)狀態。

資源配置圖演算法(Resource-Allocation Graph Algorithm) Single instance of a resource type Claim edge Pi  Rj indicated that process Pj may request resource Rj; represented by a dashed line Suppose that process Pi requests a resource Rj The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph

銀行家演算法 Multiple instances of a resource type

Example of Banker’s Algorithm 5 processes P0 through P4; 3 resource types: A (10 instances), B (5 instances), and C (7 instances) Snapshot at time T0: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 12

The content of the matrix Need is defined to be Max – Allocation Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety criteria 13

Example: P1 Request (1,0,2) Check that Request  Available (that is, (1,0,2)  (3,3,2)  true Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2> satisfies safety requirement Can request for (3,3,0) by P4 be granted? Can request for (0,2,0) by P0 be granted? 14

7.6 死結的偵測 (Deadlock Detection) 具單一例證的資源型式(Single Instance of Each Resource Type) Maintain wait-for graph Nodes are processes Pi  Pj if Pi is waiting for Pj Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph

具有多個例證的資源型式(Several Instances of a Resource Type)

Example of Detection Algorithm Five processes P0 through P4; three resource types A (7 instances), B (2 instances), and C (6 instances) Snapshot at time T0: Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 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 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i 17

7.7 自死結恢復(Recovery from Deadlock) 行程的終止(Process Termination) 1. 取消所有死結中的行程: 顯然這樣會終止死結循環，但是代價很大，因為這些行程可能已經計算很長的一段時間，而這部份的計算結果必須被拋除，並且稍 後可能要再重新計算。 2. 一次取消一個行程直到死結循環被消除為止: 此方法需要可觀的超額費用，因為在每個行程被取消後，必須求助於死結偵測演算法決定是否有任何行程仍然在死結中。

資源的優先權(Resource Preemption) 選擇犧牲者(select a victim): minimize cost 就是決定那一個資源與那一個行程需先行奪取之? 在行程被終止時，我們必須決定優先權次序以減少費用。影響費用的因素可能包 括死結行程在其執行期間所佔用的資源以及時間浪費的多寡。 回撤(rollback): return to some safe state, restart process for that state 如果從某一行程處搶取資源，對這行程有那些事要做呢?很明顯地，該行程已無法再正常執行;它缺少了某些必要的資源。必須將其撤回到某一安全狀態，再從這狀態重新開始。一般說來決定什麼是安全的狀態是很困難的。最簡單的方法就是全部撤回(total rollback):將行程中斷，以後再重新開始。然而較有效率的做法是將該行程撤回到能解開死結的狀態。換句話說此方法要求系統必須將每一個行程執行中的狀態儲存起來。 飢餓(starvation): same process may always be picked as victim, include number of rollback in cost factor 要如何才能確定飢餓的情形不會發生呢?也就是說，如何才能保證資源不會總是被同一行程處優先搶得?