第6章 死結(Deadlock)

基本觀念 很多人都有堵車的經驗 打了死結的路口被堵住的車流也擋住了其他車道的車流，大家都動彈不得 作業系統發生的死結(deadlock)也是類似的情況，處理元就像是車子，處理元掌握的資源就像車子占有的車道，處理元所需要的資源剛好掌握在別的處理元手上，而自己所占有的資源又剛好是別的處理元正需要的

死結(deadlock) 多工的環境中容許多個程式同時執行，這可以看成是一種多個處理元同步執行的現象，同步會產生死結的處理問題 死結的一般情況是指兩個或更多的處理元擁有其他處理元需要的資源，請求資源(request for resource)的動作使處理元進入阻絕(blocked)的狀態，必須等資源得到之後才能繼續執行 假如所等待的資源無法取得，處理元就會一直處於阻絕的狀態

死結處理的方式 預防(prevention) 避免(avoidance) 偵測(detection)與復原(recovery) 自行解決(manual handling)

處理元產生死結

應用系統與作業系統產生死結

處理元取得與使用資源的動作 請求(request) 使用(use) 釋出(release)

資源(resources)的涵義 可以分成實體資源(physical resources)與邏輯資源(logical resources) 印表機、記憶體空間與CPU都算是實體資源 檔案、semaphores與monitors則算是邏輯資源

發生死結的4個必要條件 互斥(mutual exclusion) 占有與等待(hold and wait) 循環等待(circular wait) 不間斷(no preemption)

系統資源分配圖(system resource-allocation graph)

用集合來表示圖型

處理死結的方法 透過協定(protocol)來預防或避免死結的發生，確定系統永遠不會進入死結的狀態(deadlock state)。 允許系統進入死結的狀態，但是必須能夠偵測死結，回復系統。 完全忽略有死結的問題。

死結的預防(prevention)策略(1) 處理元分配得到某種資源的使用權以後，就有了完全的使用權利(exclusive use) ，其他的處理元無法再使用這種資源 有的資源原本就具有互斥的特性，無法避免，例如印表機就是很典型的無法分享的資源。唯讀的檔案(read-only files)則是可分享的資源，所以不必要求互斥

死結的預防(prevention)策略(2) 處理元可以占有某種資源同時請求使用另外一種資源 假如要避免這種情形發生，通常有兩種方式，一種是要求處理元在執行以前必須先取得所需要的資源，另外一種方式是要求處理元必須在沒有擁有任何資源的情況下才能請求使用資源

死結的預防(prevention)策略(3) 一個處理元p1擁有資源R1，請求使用資源R2。而剛好處理元p2擁有資源R2，請求使用資源R1。這就是循環等待 也有可能發生兩個以上的處理元形成循環等待的情況。要避免循環等待的發生可以採用下面的方法，先將所有的資源類型加以排序並且編號，然後要求處理元在請求使用資源時必須按照資源類型編號的遞增順序 例如處理元已經擁有編號1與3的資源類型，則接下來不能請求使用編號為2的資源類型，因為2小於3，理論上可以證明這樣能預防的發生循環等待

死結的預防(prevention)策略(4) 資源的釋出只能透過處理元自行發出的動作，無法由外界強制取得 這包括處理元請求使用資源的狀況，所以若是資源無法釋出，處理元也無法取消其請求 要避免這種情況可以要求無法取得資源的處理元先釋出自己擁有的資源，等於是中斷了這些資源的使用，對於這個處理元來說，這些釋出的資源都成為自己等待取得的資源 假如擁有資源的處理元並沒有請求並等待其他的資源，我們不會要求該處理元釋出其已經擁有的資源

死結的避免(avoidance)策略 死結的預防(prevention)限制處理元請求的送出，原則是確定死結形成的4個要件不會同時發生 不過可能產生的副作用是資源的使用率降低、系統的完成率(throughput)也降低 另外一種避免死結發生的方式是預先了解處理元對於資源的使用狀況，例如處理元將要使用資源的順序、以及將釋出資源的順序，則系統就能判定是否有進入死結狀態的可能性

死結的避免(avoidance) 資源分配圖型演算法(Resource-Allocation-Graph algorithm) 班克演算法(Banker’s algorithm)

加入claim edge的資源分配圖型

系統的狀態

班克演算法(Banker’s algorithm) 資料結構中的數值

死結的偵測(detection) 採用偵測與復原的策略可以讓資源的分配大膽一些，因為避免死結發生的方法只要碰到系統可能在不安全的狀態(unsafe state)下，就絕不會分配資源，其實不一定會造成死結 在偵測與復原的方法中，系統可以儘量地把資源分配出去 ，假如發現有處理元長久停滯，即可執行偵測演算法(detection algorithm)，若是真正發生死結，只有使用復原(recovery)的方法把系統還原到沒有死結的狀態

死結的偵測(detection)方法 資源類型只有單一案例的情況 資源類型只有多個案例的情況

資源類型只有單一案例的情況

死結的復原(recovery) 死結偵測的演算法發現有死結存在之後，有幾種處理的方式，其中一種是通知管理者來處理，另外一種則是讓系統透過復原來解決死結的問題 打破死結最直接的方式是終止一些處理元的執行，或是中斷某些資源的使用

處理元的終止(process termination) 中斷所有參與死結的處理元 一次中斷一個處理元直到死結解套

選擇中斷的處理元時要考量的一些因素 處理元的優先順序。 處理元已經執行了多久？ 處理元使用了多少資源？資源是否容易中斷？ 處理元還需要多少資源才能繼續執行。 有多少處理元需要中斷？ 處理元是批次作業還是互動的？

中斷資源時考量的問題 資源與處理元的選擇 回復(rollback)的處理 饑餓(starvation)的問題