第1章认识电脑系统

第6章死結(Deadlock)基本觀念很多人都有堵車的經驗打了死結的路口被堵住的車流也擋住了其他車道的車流，大家都動彈不得作業系統發生的死結(deadlock)也是類似的情況，處理元就像是車子，處理元掌握的資源就像車子占有的車道，處理元所需要的資源剛好掌握在別的處理元手上，而自己所占有的資源又剛好是別的處理元正需要的死結(deadlock)多工的環境中容許多個程式同時執行，這可以看成是一種多個處理元同步執行的現象，同步會產生死結的處理問題死結的一般情況是指兩個或更多的處理元擁有其他處理元需要的資源，請求資源(requestforresource)的動作使處理元進入阻絕(blocked)的狀態，必須等資源得到之後才能繼續執行假如所等待的資源無法取得，處理元就會一直處於阻絕的狀態死結處理的方式預防(prevention)避免(avoidance)偵測(detection)與復原(recovery)自行解決(manualhandling)處理元產生死結應用系統與作業系統產生死結處理元取得與使用資源的動作請求(request)使用(use)釋出(release)資源(resources)的涵義可以分成實體資源(physicalresources)與邏輯資源(logicalresources)印表機、記憶體空間與CPU都算是實體資源檔案、semaphores與monitors則算是邏輯資源發生死結的4個必要條件互斥(mutualexclusion)占有與等待(holdandwait)循環等待(circularwait)不間斷(nopreemption)系統資源分配圖(systemresource-allocationgraph)用集合來表示圖型處理死結的方法透過協定(protocol)來預防或避免死結的發生，確定系統永遠不會進入死結的狀態(deadlockstate)。允許系統進入死結的狀態，但是必須能夠偵測死結，回復系統。完全忽略有死結的問題。死結的預防(prevention)策略(1)處理元分配得到某種資源的使用權以後，就有了完全的使用權利(exclusiveuse)，其他的處理元無法再使用這種資源有的資源原本就具有互斥的特性，無法避免，例如印表機就是很典型的無法分享的資源。唯讀的檔案(read-onlyfiles)則是可分享的資源，所以不必要求互斥死結的預防(prevention)策略(2)處理元可以占有某種資源同時請求使用另外一種資源假如要避免這種情形發生，通常有兩種方式，一種是要求處理元在執行以前必須先取得所需要的資源，另外一種方式是要求處理元必須在沒有擁有任何資源的情況下才能請求使用資源死結的預防(prevention)策略(3)一個處理元p1擁有資源R1，請求使用資源R2。而剛好處理元p2擁有資源R2，請求使用資源R1。這就是循環等待也有可能發生兩個以上的處理元形成循環等待的情況。要避免循環等待的發生可以採用下面的方法，先將所有的資源類型加以排序並且編號，然後要求處理元在請求使用資源時必須按照資源類型編號的遞增順序例如處理元已經擁有編號1與3的資源類型，則接下來不能請求使用編號為2的資源類型，因為2小於3，理論上可以證明這樣能預防的發生循環等待死結的預防(prevention)策略(4)資源的釋出只能透過處理元自行發出的動作，無法由外界強制取得這包括處理元請求使用資源的狀況，所以若是資源無法釋出，處理元也無法取消其請求要避免這種情況可以要求無法取得資源的處理元先釋出自己擁有的資源，等於是中斷了這些資源的使用，對於這個處理元來說，這些釋出的資源都成為自己等待取得的資源假如擁有資源的處理元並沒有請求並等待其他的資源，我們不會要求該處理元釋出其已經擁有的資源死結的避免(avoidance)策略死結的預防(prevention)限制處理元請求的送出，原則是確定死結形成的4個要件不會同時發生不過可能產生的副作用是資源的使用率降低、系統的完成率(throughput)也降低另外一種避免死結發生的方式是預先了解處理元對於資源的使用狀況，例如處理元將要使用資源的順序、以及將釋出資源的順序，則系統就能判定是否有進入死結狀態的可能性死結的避免(avoidance)資源分配圖型演算法(Resource-Allocation-Graphalgorithm)班克演算法(Banker’salgorithm)加入claimedge的資源分配圖型系統的狀態班克演算法(Banker’salgorithm)

資料結構中的數值死結的偵測(detection)採用偵測與復原的策略可以讓資源的分配大膽一些，因為避免死結發生的方法只要碰到系統可能在不安全的狀態(unsafestate)下，就絕不會分配資源，其實不一定會造成死結在偵測與復原的方法中，系統可以儘量地把資源分配出去，假如發現有處理元長久停滯，即可執行偵測演算法(detectionalgorithm)，若是真正發生死結，只有使用復原(recovery)的方法把系統還原到沒有死結的狀態死結的偵測(detection)方法資源類型只有單一案例的情況資源類型只有多個案例的情況資源類型只有單一案例的情況死結的復原(recovery)死結偵測的演算法發現有死結存在之後，有幾種處理的方式，其中一種是通知管理者來處理，另外一種則是讓系統透過復原來解決死結的問題打破死結最直接的方式是終止一些處理元的執行，或是中斷某些資源的使用處理元的終止(processtermination)中斷所有參與死結的處理元一次中斷一個處理