交替演算法-系统程式.ppt

行程的同步 註：本章學術性較重，但考試常考。 為何要同步? 為何要同步? 避免競爭情況 (Race Condition) 方法：鎖定臨界區間 (Critical Section) 低階的同步方法 交替演算法 (Turn Algorithm) 旗標演算法 (Flag Algorithm) 綜合演算法 (Combination Algorithm) 麵包店演算法 (Bakery Algorithm) 硬體支援 (Hardware Support) 禁止中斷 (在臨界區間內) 硬體的 Test and set 指令 硬體的 swap指令 高階的同步方法 號誌 (Semaphore) 計數號誌 (Counting Semaphore) 二元號誌 (Binary Semaphore) -- Java 臨界區域 (Critical Region) 監督程式 (Monitor) – C# 競爭情況 (Race Condition) 競爭情況 (Race Condition) 避免競爭 1 : 臨界區間 上述的會產生競爭情況的段落，不能讓多個程式同時執行 為了確保執行順序不會出問題，我們可以採用臨界區間的方式 競爭情況的解決方法 方法一：用硬體解決 單一CPU : 在一個關鍵段落還沒完成之前，禁止中斷的發生 (Intel 80x86,ARM…) 利用 test and set 等硬體指令 多個CPU : (雙核心以上) 必須加上旋轉鎖機制 (Linux, Windows) (busy waiting) 方法二：用軟體解決 交替演算法 (Turn Algorithm) 旗標演算法 (Flag Algorithm) 綜合演算法 (Combination Algorithm) 麵包店演算法 (Bakery Algorithm) 競爭情況的解決方法必需滿足下列條件 互斥 (Mutual Exclusion) 進行 (Progress) 有限等待 (Bounded Waiting) 交替演算法 兩個行程 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 的程式結構如下： 硬體支援 硬體支援1 : 禁止中斷 單 CPU 的系統 讓行程在修改共用的變數時停止接受中斷而解決同步的問題。 多 CPU 的系統 加上旋轉鎖等忙碌等待機制 (busy waiting) 硬體支援2 : Test-and-Set 指令 在執行完整個指令之前都不會被中斷。 Test-and-Set 指令會傳回參數 target 目前的值，並同時將 target 的值設為 TRUE。 可以利用 Test-and-Set 指令實作多行程的臨界區演算法。 硬體支援3 : Swap 硬體指令 在執行完整個指令之前都不會被中斷。 Swap 指令會交換參數 a 與 b 兩個字元組的內容。 避免競爭 2 : 號誌 Semaphore 號誌是十分常用的同步工具，可以簡單地解決較為複雜的同步問題。 大部分的作業系統都已經實作了號誌，作為行程間同步的工具。 號誌包含一個數值，該值在初始化之後就只能經由 signal() 與 wait() 兩個不可被中斷的函式去存取。 當一個行程在存取號誌的值時，其他行程無法存取同一個號誌的值。 計數號誌的使用 (1) 解決臨界區間的問題