作業系統 – 同步機制(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。

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

臨界區間設計(Critical Section Design)

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

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

臨界區間問題

  1. 互斥(mutual exclusion): 如果有一行程正在臨界區間內執行,則其它的行程不能在其臨界區間內執行。
  2. 進行(Progress): 如果沒有行程在臨界區間內執行,同時有些行程想要進入臨界區間,在外面等待的行程必須在有限的時間內進入臨界區。
    必須同時滿足下方兩個要件:
    a. 不想進入C.S.的Process不可以阻礙其它Process進入C.S.
    b. 必須在有限的時間內,自那些想進入C.S.的Process之中,挑選出一個Process進入C.S. (隱含:避免Deadlock)
  3. 限制住的等待(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)的硬體指令,主要有兩種方式:

  1. 測試記憶體字元組或設定數值 (test_and_set 指令)
  2. 交換兩個記憶體字元組的內容 (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滿足此一問題設計。

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


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

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

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

號誌的用法

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

號誌製作

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

典型的同步問題

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

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

有限緩衝區問題

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);

哲學家進餐

image 48 作業系統 - 同步機制(Synchronization)
  • 哲學家一次只能拿一枝筷子
  • 需要兩枝筷子才能吃,吃完同時放下兩枝筷子
  • 在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);
0 0 評分數
Article Rating
訂閱
通知
guest

0 Comments
在線反饋
查看所有評論