作者 : 陳鍾誠 單位 : 金門技術學院資管系 URL : 日期 : 2016/7/21 行程的同步 註：本章學術性較重，但考試常考。

2 陳鍾誠 /7/21 為何要同步 ? 避免競爭情況 (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#

3 陳鍾誠 /7/21 競爭情況 (Race Condition) while (true) { while (counter == BUFFER_SIZE) ; buffer[in] = nextProduced; in = (in+1) % BUFFER_SIZE; counter = counter + 1; } while (true) { while (counter == 0) ; nextConsumed = buffer[out]; out = (out+1) % BUFFER_SIZE; counter = counter - 1; } Producer Consumer

4 陳鍾誠 /7/21 競爭情況 (Race Condition) LOAD register, counter; ADD register, 1 STORE counter, register LOAD register, counter; SUB register, 1 STORE counter, register Producer : counter++Consumer : counter-- P:LOAD register, counter; P:ADD register, 1 C:LOADregister, counter C:SUBregister, 1 P:STORE counter, register C:STOREcounter, register register = 5 ; register = 6 register = 5 register = 4 counter = 5 counter = 4 If counter = 5 then counter may be After execution

5 陳鍾誠 /7/21 避免競爭 1 : 臨界區間 上述的會產生競爭情況的段落，不能讓多個程式同時執行 為了確保執行順序不會出問題，我們可以採用臨界區間的方式 do { entry section critical section exit section exit section remainder section } while (1)

6 陳鍾誠 /7/21 競爭情況的解決方法 方法一：用硬體解決 單一 CPU : 在一個關鍵段落還沒完成之前，禁止中斷的發生 (Intel 80x86,ARM … ) 利用 test and set 等硬體指令 多個 CPU : ( 雙核心以上 ) 必須加上旋轉鎖機制 (Linux, Windows) (busy waiting) 方法二：用軟體解決 交替演算法 (Turn Algorithm) 旗標演算法 (Flag Algorithm) 綜合演算法 (Combination Algorithm) 麵包店演算法 (Bakery Algorithm)

7 陳鍾誠 /7/21 競爭情況的解決方法必需滿足 下列條件 互斥 (Mutual Exclusion) 進行 (Progress) 有限等待 (Bounded Waiting)

8 陳鍾誠 /7/21 交替演算法 兩個行程 P i 及 P j 之間的臨界區演算法。 共用一個變數 turn ，指出目前允許進入臨界區的是 哪一個行程。 只記錄系統目前的狀態，但是並不記錄行程個別的 狀態。 如果 turn = i ，代表行程 P i 可以進入臨界區之中。 滿除臨界區互斥的條件，但是不能滿足進行的條件。

9 陳鍾誠 /7/21 交替演算法 ( 續 ) 行程 P i 的程式結構如下： do { while (turn != i) ; critical section turn = j; remainder section } while (1);

10 陳鍾誠 /7/21 旗標演算法 兩個行程 P i 及 P j 之間的臨界區演算法。 將交替演算法中共有的變數 turn 改為共有的陣列 flag ，記錄系統中個別行程的狀態。 如果 P i 要進入臨界區，則將 flag[i] 設為 TRUE 。 當 P i 離開臨界區後，再將 flag[i] 設為 FALSE 。 滿足臨界區互斥的條件，但是仍然無法滿足進行的 條件。

11 陳鍾誠 /7/21 旗標演算法 ( 續 ) 行程 P i 的程式結構如下： do { flag[i] = TRUE; while (flag[j]) ; critical section flag[i] = false; remainder section } while (1);

12 陳鍾誠 /7/21 綜合演算法 兩個行程 P i 及 P j 之間的正確臨界區演算法。 綜合交替演算法與旗標演算法。 以 flag 陣列記錄個別行程是否想要進入臨界區；而 turn 變數指出目前系統允許哪個行程進入臨界區。 同時滿足互斥、有限等待與進行三個條件。

13 陳鍾誠 /7/21 綜合演算法 ( 續 ) 行程 P i 的程式結構如下： do { flag[i] = TRUE; turn = j; while (flag[j] && turn == j) ; critical section flag[i] = false; remainder section } while (1);

14 陳鍾誠 /7/21 麵包店演算法 多個行程間的臨界區演算法。 以行程取到的號碼牌，由小而大地讓行程進入臨界 區中。 若有行程取到相同號碼，則以行程的 ID 大小決定 先後順序， ID 較小的優先。 同時滿足互斥、有限等待與進行三個條件。

15 陳鍾誠 /7/21 麵包店演算法 ( 續 ) 行程 P i 的程式結構如下： do { choosing[i] = TRUE; number[i] = max(number[0], number[1], …, number[n – 1]) + 1; choosing[i] = FALSE; for (j = 0; j < n; j++) { while (choosing[j]) ; while ((number[j] != 0) && ((number[j], j) < (number[i], i))) ; } critical section number[i] = 0; remainder section } while (1);

作者 : 陳鍾誠 單位 : 金門技術學院資管系 URL : 日期 : 2016/7/21 硬體支援

17 陳鍾誠 /7/21 硬體支援 1 : 禁止中斷 單 CPU 的系統 讓行程在修改共用的變數時停止接受中斷而解決同 步的問題。 多 CPU 的系統 加上旋轉鎖等忙碌等待機制 (busy waiting)

18 陳鍾誠 /7/21 硬體支援 2 : Test-and-Set 指令 在執行完整個指令之前都不會被中斷。 Test-and-Set 指令會傳回參數 target 目前的值， 並同時將 target 的值設為 TRUE 。 可以利用 Test-and-Set 指令實作多行程的臨界 區演算法。 boolean Test-and-Set (Boolean &target) { Boolean rv = target; target = true; return rv; }

19 陳鍾誠 /7/21 硬體支援 3 : Swap 硬體指令 在執行完整個指令之前都不會被中斷。 Swap 指令會交換參數 a 與 b 兩個字元組的內 容。 Void Swap (Boolean &a, Boolean &b) { Boolean temp = a; a = b; b = temp; }

20 陳鍾誠 /7/21 避免競爭 2 : 號誌 Semaphore 號誌是十分常用的同步工具，可以簡單地解決較為複 雜的同步問題。 大部分的作業系統都已經實作了號誌，作為行程間同步的工 具。 號誌包含一個數值，該值在初始化之後就只能經由 signal() 與 wait() 兩個不可被中斷的函式去存取。 當一個行程在存取號誌的值時，其他行程無法存取同一個號 誌的值。

21 陳鍾誠 /7/21 計數號誌的使用 (1) 解決臨界區間的問題 do { wait(mutex); critical section signal(mutex); remainder section }

22 陳鍾誠 /7/21 計數號誌的使用 (2) 解決同步的問題 wait(mutex) S1; S2 signal(mutex) P1 P2

23 陳鍾誠 /7/21 計數號誌 – 忙碌等待版 計數號誌 Counting Semaphore void wait(s) { while (s<=0) ; s--; } void signal(s) { s++; }

24 陳鍾誠 /7/21 計數號誌 – 非忙碌版 void wait(s) { S.value - -; if (S.value < 0) block() ; } void signal(S) { S.value++; if (S.value <=0) wakeup(p); }

25 陳鍾誠 /7/21 二元號誌 利用硬體實作對二元號誌的支援，簡單又快。 利用二元號誌再實作計數號誌。

26 陳鍾誠 /7/21 利用二元號誌實作計數號誌 void wait(S) { wait(S1) C--; if (C < 0) { signal(S1); wait(S2); } signal(S1); } void signal(s) { wait(S1); C++; if (C<=0) signal(S2); else signal(S1); }

27 陳鍾誠 /7/21 以號誌實作生產者 - 消費者問題 empty 初始化為 nfull 初始化為 0 do { … 產生一個新的項目放在 nextp … wait(empty); wait(mutex); … 將 nextp 加入到緩衝區中 … signal(mutex); signal(full); } while(1); do { wait(full); wait(mutex); … 將一個項目由緩衝區中 移到 nextc … signal(mutex); signal(empty); … 消耗放在 nextc 中的項目 … } while(1); 生 產 者生 產 者消 耗 者消 耗 者

28 陳鍾誠 /7/21 臨界區域 (Critical Region) 一種高階的同步方法 語法 region V when B do S; V : shared T; 注意 : 必須小心 B 的條件設定，條件相同者不能保證 其執行的先後順序 例如： R1 : region V when true do S1 R2 : region V when true do S2 則 R1, R2 不一定誰會先被執行。

29 陳鍾誠 /7/21 以臨界區域實作 : 生產者 - 消費者 region buffer when (count < n) { pool[in] = nextp; in = (in + 1) % n; count ++; } region buffer when (count > 0) { nextc = pool[out]; out = (out + 1) % n; count --; } Producer Consumer

30 陳鍾誠 /7/21 監督程式 (Monitor) 監督程式是另外一種高階的同步工具。 對較複雜的同步問題提供了更一般性的實作工具。 由一些變數宣告及函式所組成，變數的值定義了監 督程式的狀態。 保證只有一個行程在監督程式中執行所定義的函式。 在監督程式中，程式設計師不需要撰寫有關同步的 程式碼，但是可以利用條件變數來定義自己的同步 機制。 哲學家晚餐問題可以利用監督程式來實作。

31 陳鍾誠 /7/21 結語 行程不同步可能會產生競爭情況 為了避免競爭情況必需保護臨界區間 臨界區間的保護可用行程同步的方式 Mutex Semaphore

32 陳鍾誠 /7/21 比較 - 臨界區域 v.s. 臨界區間 請注意，臨界區域 (Critical Region) 與 臨界區 間 (Critical Section) 不同 臨界區間 (Critical Section) 指的是不可同時執行的該區間

33 陳鍾誠 /7/21 競爭狀況的範例 - RaceCondition.java import java.util.Random; class RaceCondition { public static void main(String[] args) throws Exception { StepThread.test(); } class StepThread extends Thread { public static void test() throws Exception { StepThread a = new StepThread("A", 1); StepThread b = new StepThread("B", -1); a.start(); b.start(); a.join(); b.join(); System.out.println("counter="+StepThread.counter); System.out.println("lines=\n"+StepThread.lines); }

34 陳鍾誠 /7/21 競爭狀況的範例 - RaceCondition.java static StringBuffer lines = new StringBuffer(); static int counter=0; int step; String name; StepThread(String pName, int pStep) { step = pStep; name = pName; } int register; public void run() { for (int i=0; i<10; i++) { String line = name+" i="+i+" step="+step+"\t before:counter="+counter; // counter = counter + step; register = counter; register = register + step; counter = register; line += " after:counter="+counter; // Y[ synchronized hBLX counter | Race Condition lines.append(line+"\n"); // System.out.println(line); // } }

35 陳鍾誠 /7/21 競爭狀況的範例 - RaceCondition.java