第六章同步与死结-RSWiki.ppt

* /80 * 死結預防 死結的發生要 4 個條件同時成立。 互斥 佔用與等待 禁止搶先 循環等待 只要破除死結的任一個條件就可以預防死結的發生。 * /80 * 互斥 互斥的條件只存在於不能共享的資源上。 如印表機不能同時列印兩份不同的文件。 可以共享的資源能夠允許多個行程同時使用，因此可以共享的資源不可能造成死結的發生。 但是，我們無法讓不可共享的資源變成可共享，因此無法利用資源的互斥條件來預防死結的發生。 * /80 * 佔用與等待 不讓佔用與等待的情形在系統中發生，必須要讓所有的行程在取得某項資源時不得先持有任何其他的資源。 行程在執行前必須要一次取得所有需要的資源，但是這個作法比較沒有效率。 或是行程在取得任何資源之前必須要釋放所有持有的資源。 可能造成資源使用率降低或是發生飢餓現象。 * /80 * 禁止搶先 禁止搶先是指資源一旦配置給行程，就必須等到行程使用完，資源才會被釋放，要解除禁止搶先可以使用以下作法： 當行程持有某些資源並要求新的資源，如果所要求的資源正被使用而必須等待，該行程必須釋放所有持有的資源。 當行程 A 要求某些資源，如果所要求的資源可以使用，就立即配置；但是如果所要求的資源已經配置給其他的行程 B，檢查 B 是否正在等待其他的資源，如果是的話便將 A 所要求的資源由 B 回收並配置給 A。 * /80 * 循環等待 要使循環等待的條件不會發生，我們可以將系統中的所有資源類型都事先編號。 規定所有行程必須按照編號順序（如由小而大）取得資源。 行程必須要先釋放所持有編號較大的資源，才能要求編號較小的資源。 會有資源使用率降低的問題。 * /80 * 第六章 同步與死結 行程同步 臨界區 號誌 同步的經典問題 臨界區域與監督程式 死結簡介 死結預防 死結避免 安全狀態 資源配置圖演算法 銀行家演算法 摘要 * /80 * 死結避免 預防死結的方法大多會降低資源的使用率，而導致系統的效能降低。 死結避免雖然不完全排除死結發生的條件，但能有效地偵測系統可能發生死結的狀態，進而避免死結的發生。 需要系統提供行程額外的資訊。 當有行程要求資源，系統會利用這些資訊判斷是否要將資源配置給行程或者是讓行程等待以避免死結的發生。 * /80 * 安全狀態 (1/2) 安全狀態是指存在某種順序，可以讓系統按照該順序將資源配置給所需要的行程，而不會發生死結。 系統正處於安全狀態，存在一組安全序列。 如果系統不存在一組安全序列，則表示系統正處於不安全狀態中，即系統可能會發生死結。 不安全狀態不一定就會發生死結，但是處於安全狀態絕對不會發生死結，這是因為系統使用資源的真正時間是無法確定的。 * /80 * 安全狀態 (2/2) 假設系統中有 3 個行程及 13 項 R 資源，目前的行程與資源狀況如下。 目前存在安全序列＜P1、P2、P0＞與 ＜P1、P0、P2＞ 。 但是系統不應該配置 2 項 R 資源給 P2。 行程 需要R資源數目 已持有R數目 目前需要R數目 未配置R資源數目 P0 10 5 5 3 P1 5 3 2 P2 6 2 4 * /80 * 資源配置圖演算法 資源配置圖演算法在系統配置某項資源給行程之前 先將配置圖中的箭號反向。 然後使用偵測迴圈的演算法檢查新的配置圖中是否會出現迴圈。 如果不會，則代表配置該資源後系統仍處於安全狀態，所以不會發生死結。 反之，則代表配置該資源後，系統會進入不安全狀態而可能發生死結，因此系統不應該配置該項資源給該行程。 不適用於有多項同種資源的系統之中。 * /80 * (不)安全狀態的資源配置 R1 R2 P1 P2 R1 R2 P1 P2 R1 R2 P1 P2 R1 R2 P1 P2 * /80 * 銀行家演算法 每一個新進入到系統的行程必須要先註冊所需要的各種資源的最大數量。 當行程要求某些資源時，系統便判斷這樣的配置是否會導致系統進入不安全狀態。 使用安全演算法來測試系統是否處在安全狀態。 使用資源要求演算法來決定是否允許資源的要求。 * /80 * 安全演算法（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