作業系統 - 同步機制(Synchronization)

最後更新於 2021 年 10 月 17 日

建議先了解 IPC 再繼續閱讀：作業系統 – Process溝通方式(IPC)

在 Share Memory 方式下可能之問題：Race Condition ( 競爭情況 )

競爭情況

一組Processes在Shared Memory溝通方式下，若未對共享變數提供互斥存取等同歩機制，則會造成共享變數之最終結果値因Processes之間執行順序不同而有所不同，導致不可預期之錯誤發生。

例：有兩個Processes P1及P2，共享一個Count變數，且該變數目前的値為10。現在，P1 及P2各作一次Count加1與減1之動作，則Count可能有不止一種結果。

為維護資料的一致性需要機制以確保合作行程間有次序地執行，並且同時段只能有一個Process使用該變數。

解決競爭情況之策略：

Disable Interrupt (停止使用中斷)
Critical Section Design (臨界區間設計)

停止使用中斷(Disable Interrupt)

為了確保對共享變數進行存取時不會被中斷，所以在該指令敘述執行之前先 Disable Interrupt，完成敘述後再Enable Interrupt。

優點：簡單，易於實施
缺點：只適用於Single Processor環境，不適用於Multiprocessor 環境。(∵Performance變差，且風險性增加)
- 因為在Multiprocessor環境下關掉單顆CPU的中段功能沒有用，要全部的CPU中斷功能都關掉才有用。
- Disable Interrupt的作法會導致其它更緊急的工作無法執行。

臨界區間設計(Critical Section Design)

臨界區間：在程式中，針對共享變數進行存取之指令敘述所形成之集合。

當一個行程在臨界區間時，不允許其它的行程在該臨界區間。
非 Critical Section(C.S.) 之指令敘述集合稱為 Remainder Section (剩餘區間:R.S.)
每一個行程必須要求允許才能進入臨界區間的入口區段，緊跟著臨界區間的出口區段(exit section) ，然後是剩餘區段(remainder section)

臨界區間問題

互斥(mutual exclusion)：如果有一行程正在臨界區間內執行，則其它的行程不能在其臨界區間內執行。
進行(Progress)：如果沒有行程在臨界區間內執行，同時有些行程想要進入臨界區間，在外面等待的行程必須在有限的時間內進入臨界區。
必須同時滿足下方兩個要件：
a. 不想進入C.S.的Process不可以阻礙其它Process進入C.S.
b. 必須在有限的時間內，自那些想進入C.S.的Process之中，挑選出一個Process進入C.S. (隱含：避免Deadlock)
限制住的等待(bound waiting)：在一個行程已經要求進入其臨界區間，而此要求尚未被答應之前，允許其它的行程進入其臨界區間的次數有一個限制。
- 自Process提出進入C.S.之申請，到它獲准進入C.S.之等待時間是有限的。即：若有 n 個Processes想進入C.S.，則任一Process至多等待 n-1次，即可進入C.S. (隱含：No Starvation)

解決臨界區間問題的方法

Peterson演算法

假設有兩個process不可中斷，共享兩個變數：

int turn // 代表輪到誰進入臨界區間
Boolean flag[2] // 用來標示哪個行程準備就緒進入臨界區間

flag[i] = true 表示Pi準備進入它的臨界區間。

do { 
  flag[i] = true; 
  turn = j; 
  while (flag[j] && turn == j); 
    critical section 
  flag[i] = false; 
    remainder section 
 } while (true);

證明

互斥性存在
進行的要求能被滿足
限制性的等待要求亦能符合

分析

滿足Mutual Exclusion
turn值僅會是 i 或 j 不會兩者皆是。
若Pi想要執行，則 flag[j] = false 或 turn = i (代表 j 不想執行，或是優先權在 i 手上)。
滿足Progress
以 Pj 要執行為前提，可能發生三種情況：
- Pi不想執行 Pj 直接進入
- Pi、Pj 同時想執行，優先權在i手上(turn = i)，Pi 先執行
- Pi、Pj 同時想執行，優先權在j手上(turn = j)，Pj 先執行
滿足Bounded Waiting
假設Pi 與Pj 皆想進入自已的C.S. ，且此時Pi 已先進入C.S.，而Pj 卡在while loop 等待。若Pi 離開C.S.後又企圖立刻進入自已的C.S.，此時Pi 一定會執行 turn = j 之設定，使得Pi 無法再搶先於Pj 進入自已的C.S.而被卡在while loop 等待。所以對Pj 而言，它至多等待一次即可進入C.S.。

同步硬體

許多系統對於臨界區間程式碼提供硬體支援
所有的解都是以鎖(locking)為前提
- 藉由鎖保護臨界區間

目前的機器提供特殊不可分割(Atomic)的硬體指令，主要有兩種方式：

測試記憶體字元組或設定數值 (test_and_set 指令)
交換兩個記憶體字元組的內容 (compare_and_swap 指令)

do { 
	acquire lock 
		critical section 
	release lock 
		remainder section 
} while (true);

test_and_set 指令

把值寫到一個新的地方，回傳舊值
test_and_set Instruction不會被中斷，以下是他的定義：

boolean test_and_set (boolean *target)
{
         boolean rv = *target;
         *target = true;
         return rv:
}

共用 boolean 變數 lock一開始設為 false

解決方法：

do {
         while (test_and_set(&lock)); // do nothing 
         /* critical section */ 
         lock = false; 
         /* remainder section */ 
} while (true);

lock是共享的變數，當執行test_and_set(&lock)，會將lock變數記憶體的位置傳入test_and_set()這時會被上鎖，等執行完後lock才會被解鎖。

compare_and_swap 指令

compare_and_swap指令不可被中斷，下方為它的定義：

int compare and swap(int *value, int expected, int new value) { 
   int temp = *value; 
   if (*value == expected) 
      *value = new value; 
   return temp; 
}

共用 boolean 變數 lock一開始設為 false; 每一個行程有一個區域Boolean變數 key

解決方法：

do {
  while (compare and swap(&lock, 0, 1) != 0); /* do nothing */ 
  /* critical section */ 
  lock = 0; 
  /* remainder section */ 
} while (true);

lock是共享變數，初始值為0 (0代表不能進去，1代表可以進去)，當執行compare_and_swap(&lock , 0 , 1)，會去比對lock跟expected的值，如果相同就會把值做交換。

互斥鎖(Mutex Lock)

前面的解答很複雜，並且應用程式人員無法接觸到。
OS設計者可以建立軟體工具來解決臨界區間的問題。
最簡單的是互斥鎖(mutex lock)。
行程在進入臨界區間前必須呼叫函數acquire()取得鎖；離開臨界區間前呼叫函數release()釋放鎖。
- Boolean變數available用來表示鎖是否可以使用。
acquire()和release()必須是不可中斷的函數。
- 通常藉由硬體的不可分割指令製作。
但這個解答要求忙碌等待(busy waiting)。
- 這種型態的互斥鎖被稱為自旋鎖(spinlock)。

acquire() {
   while (!available); /* busy wait */ 
   available = false;; 
} 

release() { 
   available = true; 
} 

do { 
   acquire lock
      critical section
   release lock 
      remainder section 
} while (true);

號誌(Semaphore)

不需要忙碌等待的同步工具
號誌 S –整數變數
兩個標準操作修改 S: wait() and signal()
- 原先稱為 P() 和 V()
比較不複雜
只能藉由2個不可不分割(atomic)的運算存取

wait (S) { 
    while (S <= 0);	 // busy wait
    S--;
}
signal (S) { 
    S++;
}

利用wait()和signal()來改變，當執行完wait()則S減1，而執行完signal()則S加1。當S = 0時，就要等到執行完signal()才能再執行wait()。

簡單的同步問題

假設有P1和P2兩個 Current Execution的Processes如下：今規定“S1的敘述一定要在S2敘述之前執行”，請利用Semaphore滿足此一問題設計。

Ans:
宣告一個共享變數S: Semaphore，初値為0。

因為當 S = 0 時需要等待，直到 signal(S) 執行後 S++，S不再 <= 0 的時候才能去執行 S2。

號誌的用法

計數號誌(Counting semaphore ) – 範圍不受限制的整數值
二元號誌(Binary semaphore) – 數值可以是0或1
- 可以用來取代互斥鎖

號誌製作

必須保證沒有兩個行程可以對相同的號誌同時執行 wait() 和 signal()。
因此，製作變成臨界區間問題，wait 和signal 程式碼被放在臨界區間。
應用程式可能耗費很多時間在臨界區間，因此這不是一個好的解結方法。

典型的同步問題

典型的同步問題被用來測試每一個新提出的同步技術

有限緩衝區問題
讀取者-寫入者問題
哲學家進餐的問題

有限緩衝區問題

n個緩衝區,每一個緩衝區保存一項資料

號誌 mutex 一開始設定為 1
號誌 full 一開始設定為 0
號誌 empty 一開始設定為 n

生產者行程的結構

do { 
      ...   /* produce an item in next_produced */ 
      ... 
   wait(empty); 
   wait(mutex); 
      ...   /* add next produced to the buffer */ 
      ... 
   signal(mutex); 
   signal(full); 
} while (true);

消費者行程的結構

do { 
   wait(full); 
   wait(mutex); 
      ...   /* remove an item from buffer to next_consumed */ 
      ... 
   signal(mutex); 
   signal(empty); 
      ...   /* consume the item in next consumed */ 
      ...
} while (true);

讀取者-寫入者問題

一個資料集可以被一些並行的行程所共用
- 讀取者– 只能讀取資料集;它們不能執行資料集
- 寫入者– 可以讀和寫資料集
問題
- 同一時間只有一個寫入者可以存取資料
讀取者和寫入者如何被對待有許多不同的方法，所有的方法都牽涉到優先權
共用資料
- 資料集
- 號誌 rw_mutex 一開始設定為 1
- 號誌 mutex 一開始設定為 1
- 整數 read_count 一開始設定為 0

寫入者行程的結構

do {
      wait(rw mutex); 
      ...   /* writing is performed */ 
      ... 
   signal(rw mutex); 
} while (true);

讀取者行程的結構

do {
      wait(mutex);
      read count++;
      if (read count == 1) 
      wait(rw mutex); 
      signal(mutex); 
      ... 
        /* reading is performed */ 
      ... 
      wait(mutex);
      read count--;
      if (read count == 0) 
      signal(rw mutex); 
      signal(mutex); 
} while (true);

哲學家進餐

哲學家一次只能拿一枝筷子
需要兩枝筷子才能吃，吃完同時放下兩枝筷子
在5哲學家的情況，共用資料：
- 碗裡的飯(資料集)
- 號誌 chopstick [5] 開始時設定為1

哲學家 i 的結構

do  { 
         wait ( chopstick[i] );
	     wait ( chopStick[ (i + 1) % 5] );
	             //  eat
	     signal ( chopstick[i] );
	     signal (chopstick[ (i + 1) % 5] );
                 //  think
} while (true);