交替演算法.PPT

作業系統 第六章 同步與死結 第六章 同步與死結 行程同步 臨界區 號誌 同步的經典問題 臨界區域與監督程式 死結簡介 死結預防 死結避免 摘要 行程同步 多個行程同時去存取相同的資料時，會因為不同的指令執行順序而得到不同結果的現象 稱為競爭情況。 為了避免競爭情況的發生 同一時間只能讓一個行程去存取一個變數。 行程之間需要互相同步，讓一個行程更改資料的動作不會影響到其他行程的執行結果。 第六章 同步與死結 行程同步 臨界區 交替演算法 旗標演算法 綜合演算法 麵包店演算法 硬體支援 號誌 同步的經典問題 臨界區域與監督程式 死結簡介 死結預防 死結避免 摘要 臨界區 臨界區是一段不能讓多個行程同時執行的程式碼。 系統中的某個行程在執行臨界區的這段程式時，其他的行程不能在這段時間內進入同一個臨界區執行。 可以解決因行程共享資料而造成資料可能不一致的問題。 必須同時符合互斥、進行與有限等待三項條件。 臨界區 (續) 位在臨界區之前負責協調行程的程式碼稱之為入口區。 在臨界區之後會接著一個出口區，負責處理出臨界區後的動作。 而剩餘的程式部分則稱之為剩餘區。 交替演算法 兩個行程 Pi 及 Pj 之間的臨界區演算法。 共用一個變數 turn，指出目前允許進入臨界區的是哪一個行程。 只記錄系統目前的狀態，但是並不記錄行程個別的狀態。 如果 turn = i，代表行程 Pi 可以進入臨界區之中。 滿除臨界區互斥的條件，但是不能滿足進行的條件。 交替演算法 (續) 行程 Pi 的程式結構如下： 旗標演算法 兩個行程Pi 及 Pj之間的臨界區演算法。 將交替演算法中共有的變數 turn 改為共有的陣列 flag，記錄系統中個別行程的狀態。 如果 Pi 要進入臨界區，則將 flag[i] 設為 TRUE。 當 Pi 離開臨界區後，再將 flag[i] 設為 FALSE。 滿足臨界區互斥的條件，但是仍然無法滿足進行的條件。 旗標演算法 (續) 行程 Pi 的程式結構如下： 綜合演算法 兩個行程 Pi 及 Pj 之間的正確臨界區演算法。 綜合交替演算法與旗標演算法。 以 flag 陣列記錄個別行程是否想要進入臨界區；而 turn 變數指出目前系統允許哪個行程進入臨界區。 同時滿足互斥、有限等待與進行三個條件。 綜合演算法 (續) 行程 Pi 的程式結構如下： 麵包店演算法 多個行程間的臨界區演算法。 以行程取到的號碼牌，由小而大地讓行程進入臨界區中。 若有行程取到相同號碼，則以行程的 ID 大小決定先後順序，ID 較小的優先。 同時滿足互斥、有限等待與進行三個條件。 麵包店演算法 (續) 行程 Pi 的程式結構如下： 硬體支援 在單 CPU 的系統中，可以很簡單地讓行程在修改共用的變數時停止接受中斷而解決同步的問題。 但是在多 CPU 的系統中並不合適，因為停止所有 CPU 的中斷除了很耗時間之外，也會增加行程進入臨界區所花費的時間。 除了利用程式技巧來達到同步之外，可以將同步的機制設計在硬體上。 撰寫同步程式變得更加方便，並同時提升系統效率。 許多機器實作了特殊的硬體指令，可以不被中斷地檢查並設定一個字元組的內容、或是交換兩個字元組的內容。 利用這些指令可以很簡單地解決臨界區的問題。 Test-and-Set 硬體指令 在執行完整個指令之前都不會被中斷。 Test-and-Set 指令會傳回參數 target 目前的值，並同時將 target 的值設為 TRUE。 可以利用 Test-and-Set 指令實作多行程的臨界區演算法。 Swap 硬體指令 在執行完整個指令之前都不會被中斷。 Swap 指令會交換參數 a 與 b 兩個字元組的內容。 第六章 同步與死結 行程同步 臨界區 號誌 計數號誌 二元號誌 同步的經典問題 臨界區域與監督程式 死結簡介 死結預防 死結避免 摘要 號誌 號誌是十分常用的同步工具，可以簡單地解決較為複雜的同步問題。 大部分的作業系統都已經實作了號誌，作為行程間同步的工具。 號誌包含一個數值，該值在初始化之後就只能經由 signal() 與 wait() 兩個不可被中斷的函式去存取。 當一個行程在存取號誌的值時，其他行程無法存取同一個號誌的值。 計數號誌 (1) 計數號誌的值像一個計數器，記錄著有多少行程可以再進入臨界區。 號誌的值只能利用 signal() 與 wait() 存取。 signal() 會將號誌的值加 1。 wait() 則會先測試號誌的值，如果號誌的值大於零，會將該值減 1，否則 wait() 會等待到該值大於零再繼續執行。 解決多行程臨界區的問題。 達到