死結的處理 日期 : 2018/11/14

死結簡介 許多行程會共同競爭系統中有限的資源。 當行程所要求的資源正被其他的行程所使用時，該行程就必須要等待。 等待的行程可能會因為所要求的資源也被其他正在等待的行程所持有，而無限期地等待，這種情形稱為死結。 2 陳鍾誠 - 2018/11/14

死結特性 (1) 系統中行程共同競爭的有限資源可以分為幾種不同的類型，而每種類型又會有不同數目的資源。 一個行程可以對一個資源進行要求、使用、釋放等 3 種動作。 行程不能要求比系統擁有數目更多的資源。 當行程要求了某種資源時，作業系統會先檢查系統的資源配置表，如果該種資源都正被其他行程所使用，作業系統會將目前要求的這個行程加入所等待資源的等待串列中。 3 陳鍾誠 - 2018/11/14

死結特性 (2) 死結的定義如下，系統中的每一個行程都在等待著某些資源，而這些資源卻已經配置給其他正在等待的行程，因而所有的行程都進入無限期地等待而無法完成工作。 死結只有在下列 4 種條件都同時成立下才會發生： 互斥 佔用與等待 禁止搶先 循環等待 4 陳鍾誠 - 2018/11/14

死結特性 (3) 我們可以使用系統資源配置圖來描述系統中行程與資源間的狀態。 圓代表系統中的一個行程，圓中寫著行程的名稱。 方塊代表系統中的一種資源，方塊中黑點的數量表示該種資源的數目。 箭號所代表的意義有兩種。 由資源指向行程的箭號表示該資源目前被該行程所持有。 由行程指向資源的箭號則代表該行程目前正在等待該項資源。 5 陳鍾誠 - 2018/11/14

資源配置圖 P1 P2 P3 R2 R1 6 陳鍾誠 - 2018/11/14

死結偵測 如果系統中所有類型的資源都只有一項的話，我們可以利用資源配置圖來偵測死結。 利用偵測迴圈的演算法來檢查資源配置圖中是否有迴圈存在，就能知道目前系統中是否有死結發生。 使用這種方法的系統必須要持續地更新資源配置圖，並且要定期地執行偵測迴圈的演算法以偵測死結。 如果系統中各類型資源的數目不只一項的話，可以使用死結偵測演算法來偵測死結。 7 陳鍾誠 - 2018/11/14

死結解除 當偵測到死結發生，有兩種方法可以解除死結。 終止行程的作法中，可以選擇終止所有行程或是一次只終止一個行程，直到死結的狀態解除。 終止一些行程，使循環等待的條件不成立。 由發生死結的行程中回收一些資源給其他行程，使禁止搶先的條件不成立。 終止行程的作法中，可以選擇終止所有行程或是一次只終止一個行程，直到死結的狀態解除。 終止所有行程的作法雖然比較簡單，但是行程的工作必須重新或是部分執行，會浪費較多的 CPU 時間。 一次終止一個行程所浪費的 CPU 時間較少，但是每終止一個行程之後都必須要執行一次偵測死結的動作來判定死結是否已經解除。 8 陳鍾誠 - 2018/11/14

死結解除 (續) 用回收資源的作法來解除死結，必須持續地由一些行程回收資源，並將回收的資源配置給其他的行程，直到死結的狀態解除。這個作法有幾點需要注意： 選定行程的方法 回溯 飢餓現象 9 陳鍾誠 - 2018/11/14

第六章 同步與死結 行程同步 臨界區 號誌 同步的經典問題 臨界區域與監督程式 死結簡介 死結預防 死結避免 摘要 互斥 佔用與等待 禁止搶先 循環等待 死結避免 摘要 10 陳鍾誠 - 2018/11/14

死結預防 死結的發生要 4 個條件同時成立。 只要破除死結的任一個條件就可以預防死結的發生。 互斥 佔用與等待 禁止搶先 循環等待 11 陳鍾誠 - 2018/11/14

死結預防 -互斥 互斥的條件只存在於不能共享的資源上。 如印表機不能同時列印兩份不同的文件。 可以共享的資源能夠允許多個行程同時使用，因此可以共享的資源不可能造成死結的發生。 但是，我們無法讓不可共享的資源變成可共享，因此無法利用資源的互斥條件來預防死結的發生。 12 陳鍾誠 - 2018/11/14

死結預防 - 互斥 某些裝置可共享 某些裝置不可共享 節論：無法利用資源互斥的條件壁免死結 如檔案 如印表機 13 陳鍾誠 - 2018/11/14

死結預防 -佔用與等待 不讓佔用與等待的情形在系統中發生，必須要讓所有的行程在取得某項資源時不得先持有任何其他的資源。 行程在執行前必須要一次取得所有需要的資源，但是這個作法比較沒有效率。 或是行程在取得任何資源之前必須要釋放所有持有的資源。 可能造成資源使用率降低或是發生飢餓現象。 14 陳鍾誠 - 2018/11/14

死結預防 - 佔用與等待 規定行程必須在執行前一次取得所有資源 規定行程在取得任何資源前必需先釋放所有資源 沒效率，系統使用率大幅降低 飢餓現像 15 陳鍾誠 - 2018/11/14

死結預防 -禁止搶先 禁止搶先是指資源一旦配置給行程，就必須等到行程使用完，資源才會被釋放，要解除禁止搶先可以使用以下作法： 當行程持有某些資源並要求新的資源，如果所要求的資源正被使用而必須等待，該行程必須釋放所有持有的資源。 當行程 A 要求某些資源，如果所要求的資源可以使用，就立即配置；但是如果所要求的資源已經配置給其他的行程 B，檢查 B 是否正在等待其他的資源，如果是的話便將 A 所要求的資源由 B 回收並配置給 A。 16 陳鍾誠 - 2018/11/14

死結預防 - 禁止搶先 如果要求的資源正被使用而必需等待時，必需先釋放所有資源 搶先、收回等待中行程的資源 A B A B Ri Rx Ri 17 陳鍾誠 - 2018/11/14

死結預防 -循環等待 要使循環等待的條件不會發生，我們可以將系統中的所有資源類型都事先編號。 規定所有行程必須按照編號順序（如由小而大）取得資源。 行程必須要先釋放所持有編號較大的資源，才能要求編號較小的資源。 會有資源使用率降低的問題。 18 陳鍾誠 - 2018/11/14

死結預防 - 循環等待 用編號的方式，取得資源的方式是 先取編號小的資源 ex : R3 取得後才能取得編號大的資源 ex : R5 19 陳鍾誠 - 2018/11/14

死結避免 日期 : 2018/11/14

死結避免 預防死結的方法大多會降低資源的使用率，而導致系統的效能降低。 死結避免雖然不完全排除死結發生的條件，但能有效地偵測系統可能發生死結的狀態，進而避免死結的發生。 需要系統提供行程額外的資訊。 當有行程要求資源，系統會利用這些資訊判斷是否要將資源配置給行程或者是讓行程等待以避免死結的發生。 21 陳鍾誠 - 2018/11/14

安全狀態 安全狀態是指存在某種順序，可以讓系統按照該順序將資源配置給所需要的行程，而不會發生死結。 系統正處於安全狀態，存在一組安全序列。 如果系統不存在一組安全序列，則表示系統正處於不安全狀態中，即系統可能會發生死結。 不安全狀態不一定就會發生死結，但是處於安全狀態絕對不會發生死結，這是因為系統使用資源的真正時間是無法確定的。 22 陳鍾誠 - 2018/11/14

資源配置圖演算法 資源配置圖演算法在系統配置某項資源給行程之前 先將配置圖中的箭號反向。 然後使用偵測迴圈的演算法檢查新的配置圖中是否會出現迴圈。 如果不會，則代表配置該資源後系統仍處於安全狀態，所以不會發生死結。 反之，則代表配置該資源後，系統會進入不安全狀態而可能發生死結，因此系統不應該配置該項資源給該行程。 不適用於有多項同種資源的系統之中。 23 陳鍾誠 - 2018/11/14

(不)安全狀態的資源配置 R1 R2 P1 P2 R1 R2 P1 P2 24 陳鍾誠 - 2018/11/14

銀行家演算法 每一個新進入到系統的行程必須要先註冊所需要的各種資源的最大數量。 當行程要求某些資源時，系統便判斷這樣的配置是否會導致系統進入不安全狀態。 使用安全演算法來測試系統是否處在安全狀態。 使用資源要求演算法來決定是否允許資源的要求。 25 陳鍾誠 - 2018/11/14

安全演算法 （Safety Algorithm） 宣告兩個長度分別為 m 與 n 的陣列 Work 與 Finish，並將 Work 初始化為 Available，Finish 陣列中所有元素初始為 FALSE。 尋找 i 使得 Finish[i] = FALSE 而且 NEED[i]  WORK[i]，如果找不到這樣的 i，執行步驟 4。 Work[i] = Work[i] + Allocation[i]; Finish[i] = TRUE; 執行步驟 2。 如果 Finish 陣列中所有元素都為 TRUE，則系統目前處於安全狀態中。 26 陳鍾誠 - 2018/11/14

資源要求演算法 （Resource Request Algorithm） 宣告 n × m 的 Request 陣列存放行程所要求各項資源的數量，如 Request[i, j] = 3 表示行程 Pi 要求 3 項資源 Rj。 如果 Request[i]  Need[i]，執行步驟 3；否則因為行程要求過多的資源而發生錯誤。 如果 Request[i]  Available[i]，則執行步驟 4；否則因為目前系統中尚未配置的資源不足，行程 Pi 必須等待。 作以下的運算： Available[i] = Available[i] – Request[i]; Allocation[i] = Allocation[i] + Requset[i]; Need[i] = Need[i] – Request[i]; 使用安全演算法檢驗運算後的結果，如果處於安全狀態則允許配置該資源給 Pi；否則Pi 必須等待，並且回存步驟 4 執行前的結果。 27 陳鍾誠 - 2018/11/14

行程與資源的配置 Max Allocation Available 行程 需要資源數目 持有資源數目 系統未配置資源數目 A B C A B C A B C P1 8 0 2 5 0 0 3 1 2 P2 5 2 1 3 1 0 P3 1 2 2 0 1 2 P4 7 6 4 2 5 2 P5 3 3 5 0 2 3 28 陳鍾誠 - 2018/11/14

行程與資源的配置 – 解 A B C A B C A B C P1 8 0 2 5 0 0 3 1 2 P2 5 2 1 3 1 0 Max Allocation Available 行程 需要資源數目 持有資源數目 系統未配置資源數目 A B C A B C A B C P1 8 0 2 5 0 0 3 1 2 P2 5 2 1 3 1 0 P3 1 2 2 0 1 2 P4 7 6 4 2 5 2 P5 3 3 5 0 2 3 3 0 2 2 1 1 1 1 0 5 1 2 3 1 2 0 1 1 12 4 7 7 4 5 4 3 5 14 9 9 4 2 3 29 陳鍾誠 - 2018/11/14