06. 同步 (Synchronization)

 

 共筆大綱:

  • Race Condition
  • Critical Section
  • Bakery Algorithm
    麵包師傅烘焙麵包 和 麵包盤

  • Hardware - lock

  • Semaphores : Busy Waiting ( spin lock ), Time Dependent Error ( Deadlock )
    * Explain Codes

  • Producer Consumer Problem
    * Explain Codes

  • Reader Writer Problem
     * Explain Codes

  • Dining Pilosiphers Problem
    哲學家吃飯問題

 

 架構:

  • Race Condition

          什麼是 Race Condition? 想像有一張雙人共用的提款卡,當兩個人同時提款和存款的時候,會發生一個狀況:假設目前提款卡餘額剩下1000元,A, B 兩人分別同時提款與存款:

A

B

 

  1. 信用卡剩下 1000 元
    mov eax, 1000

  2. A 提出 500元
    addi eax, eax, -500

  3. 存回銀行資料庫,餘額 500 元

 

 

  1. 信用卡剩下 1000 元
    mov eax, 1000
  2. B 存入 800 元
    addi eax, eax, 800

  3. 存回銀行資料庫,餘額 1800 元

 

因為 A, B process 不會同時占用 CPU,A,B 的 1, 2, 3 步會交錯進行,假設排程時,B3 比 A3 晚一點,最後提款卡的金額會變成 1800 元,和我們預期的 1000 – 500 + 800 = 1300 元有出入。

 

從上面的例子我們看到在兩個工作同時存記憶體 context switch 的過程中,並不會即時更新記憶體的資料,造成最後用舊的資料計算,產生錯誤的結果。因此我們接下來要開始討論同步的問題,以下會介紹一些解決的方法。

 

  • Critical Section

     從剛剛的問題出發,如果可以等 A 完成提款,再換 B 存款,就可以解決 A, B 同時提款資料沒有即時更新的問題。Critical section 的作法是當有多個 process 要工作,同一時間若有一個 process 在 critical section 的話,其他 process 不能進入,也就是說當 A 在提款的時候,B 不能同時存款。以下是解決 critical-section 問題須滿足的三個條件:

  1. Mutual Exclusion (互斥):
    當有一個 process 佔住 critical-section 時,其他 process 不能進入 critical section,不會有兩個 process 同時間在 critical-section 中工作。

  2. Progress:
    當沒有 process 要在 critical-section 中執行時,不能阻擋其他想要進入 critical section 工作的 process 進入 critical-section,要選擇其中一個候選 process 進入 critical-section,不能空在那邊。(延遲:postponed)

  3. Bounded Waiting:
    等待 critical-section 的時間,不能是無窮大的時間,是有個界線。也就是說,不能佔住了critical-section 就不出來了。

 

 

解決 critical-section 問題的方法:

 

Peterson's Solution

軟體方式解決,假設有兩個process,共享兩個變數。

int turn(代表輪到誰進入critical section)

boolean flag[2](代表誰準備好進入critical section)

其中load 和store兩個指令為atomic,是不可被中斷的。

 

一樣要滿足Mutual Exclusion, Progress, Bounded Waiting三個條件。

 

舉例 Process i 的部分來說。

do {

       flag[i] = true;                               //process i 準備好進入critical section

       turn = j;                                               // 如果 context switch 發生在這裡
                                                                      // 軟體方式無法解決這個問題

       while (flag[j] && turn = = j);       //在process j 尚未執行完,process i 不得進入critical section.   

      //上面三行為entry section

       critical section

       flag[i] = false;                            //exit section

       remainder section

} while (true);

 

Synchronization Hardware

硬體方式解決,藉由 lock 來保護 critical section。
目前主要使用 atomic hardware instruction. 意味著某些 inctruction 不可中斷。

主要有兩種方法,利用 test memory word and set value (測試和設值) 和 swap contents of two memory words (交換內容)來做到 lock 的功能。

 

  1. test_and_set Instruction(atomic,不會被中斷)

boolean test_and_set (boolean *target) {

 

              boolean rv = *target;

              *target = TRUE;                         //進來的value設成true

              return rv:

}

 

使用 test_and_set Instruction,lock=false.

 

do {
         while (test_and_set(&lock))

 

            ; /* do nothing */

 

                /* critical section */                     //變到1就可以進去

 

         lock = false;

 

                /* remainder section */

} while (true);

────────────────────────

       2.  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;

    }

 

// “lock”  initialized to 0

do {
        while (compare_and_swap(&lock, 0, 1) != 0)

           ; /* do nothing */

         /* critical section */

      lock = 0;

         /* remainder section */

     } while (true);

 

Mutex Locks(spinlock)

用acquire()取得lock,和release()釋放lock,來保護critical section.

若無法取得lock,則進入busy waiting.

 

Semaphore

有一個整數變數Semaphore S,有兩個指令,wait ()和signal()。也是個spinlock.

必需要保證沒有兩個process可以同時執行wait ()和signal(),也就是說要把wait ()和signal()也放入critical section

 

/*S<=0時做busy wait,若S>0則減一*/

wait(S) {

   while (S <= 0)

      ; // busy wait

   S--;

}

 /*單純S加一*/

signal(S) {

   S++;

}

 

Semaphore without waiting queue

有兩個operation,

block:放入process

wakeup:移出process

 

wait(semaphore *S) {

  S->value--;

  if (S->value < 0) {
     add this process to S->list;

     block();

  }

}


signal(semaphore *S) {

  S->value++;

  if (S->value <= 0) {
     remove a process P from S->list;

     wakeup(P);

  }

}

 

 經典問題:

 

Bounded-Buffer Problem

假設有n個buffer,三個semaphore初值分別為mutex=1;empty=n;full=0;

 

processing process 

要將資料放進buffer裡。

do {

         ...
       /* produce an item in next_produced */

         ...

       wait(empty);

       wait(mutex);

          ...
       /* add next produced to the buffer */

          ...

       signal(mutex);

       signal(full);

    } while (true);

 

comsumer process

移出資料。

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

 

兩者順序不同。

 

Readers and Writers Problem

有一個檔案或資料,有很多process要平行存取。

readers:只能讀data set,只能讀,不能更新。可允許同時讀資料。

writers:可同時讀寫。同一時間只能有一個writer取得分享資料。

Semaphore rw_mutex= 1 ,mutex = 1; Integer read_count = 0

 

//writer

do {
         wait(rw_mutex);

              ...
         /* writing is performed */

              ...

         signal(rw_mutex);

    } while (true);
單純等rw_mutex,做完再+1。

 

//reader

do {
          wait(mutex);
          read_count++;
          if (read_count == 1)

             wait(rw_mutex);  //有人在write

          signal(mutex);

              ...
          /* reading is performed */

              ...

          wait(mutex);   //read完後,看write有沒有做完。
          read count--;
          if (read_count == 0)

          signal(rw_mutex);

          signal(mutex);

      } while (true);

 

First  variation – 除非writer可以使用shared object,不然不能讓reader等待。

Second variation – 當writer已經ready後,就立刻write.

以上兩種都可能會造成starvation

解決法:部分作業系統由核心的kernel提供。

 

 

Dining-Philosophers Problem

五個哲學家,五個筷子,每個哲學家的動作只有思考和吃飯。

In the case of 5 philosophers

Shared data Bowl of rice (data set)

Semaphore chopstick [5] initialized to 1

do {

   wait (chopstick[i] );

 wait (chopStick[ (i + 1) % 5] );

            //  eat

 

 signal (chopstick[i] );

 signal (chopstick[ (i + 1) % 5] );

                //  think


} while (TRUE);

若每個人都拿右手邊的筷子,就會發生deadlock.

 

解決deadlock:

1.只能允許4個人同時吃。

2.左右筷子都空下來才能吃。

3.非對稱式:奇數偶數,奇數的人先取左邊筷子再取右邊筷子,偶數的人先取右邊筷子再取左邊筷子。

semaphore不保證沒有deadlock和starvation.

 

Monitors:

高階的處理同步的方式,Abstract data type。並非所有作業系統都支援。一個時間內只有一個process在Monitor.

一樣不能解決所有問題。

 

在share data裡有condition x, y;

x.wait() – 等到x.signal()才能執行。

x.signal() – 恢復 x.wait(),如果沒有x.wait(),則沒什麼作用。

 

用monitor解決dinner philosophers的問題

monitor DiningPhilosophers

{

enum { THINKING; HUNGRY, EATING) state [5] ;             //三種狀態

condition self [5];

//拿起筷子

void pickup (int i) {

      state[i] = HUNGRY;

      test(i);

      if (state[i] != EATING) self[i].wait;

}

 //放下筷子

  void putdown (int i) {

      state[i] = THINKING;

                  // test left and right neighbors

       test((i + 4) % 5);

       test((i + 1) % 5);

}

//測試左右有沒有拿筷子 

void test (int i) {

       if ((state[(i + 4) % 5] != EATING) &&

       (state[i] == HUNGRY) &&

       (state[(i + 1) % 5] != EATING) ) {

            state[i] = EATING ;

   self[i].signal () ;

       }

  }


      initialization_code() {

      for (int i = 0; i < 5; i++)

      state[i] = THINKING;

    }

}

 

*每一個哲學家只有可能有三種狀態

1.拿起筷子

2.吃

3.放下 

可解決deadlock,但還是有可能starvation.(沒有排進排程)

 應用:

openmp

OpenMP提供的這種對於並行描述的高層抽象降低了並行編程的難度和複雜度,這樣程序員可以把更多的精力投入到並行算法本 身,而非其具體實現細節。對基於數據分集的多線程程序設計,OpenMP是一個很好的選擇。同時,使用OpenMP也提供了更強的靈活性,可以較容易的適 應不同的並行系統配置。線程粒度和負載平衡等是傳統多線程程序設計中的難題,但在OpenMP中,OpenMP庫從程序員手中接管了部分這兩方面的工作。