OS - Ch6 同步問題 Synchronization

同步問題是滿重要的章節，semaphore 操作要熟悉，一些經典的同步問題也很重要~ enjoy it!

2015.1.15 初版

2017.8.22 二版

一、同步問題簡介

The Critical Section Problem：提供對共享變數之存取的互斥控制，確保資料的正確性。

entry section
Critical section
exit section
remainder section

Solution to Critical-Section Problem :

Mutual exclusion：任一時間點，只允許一個 process 進入他自已的 critical section 內活動。
Progress：必須同時滿足下面2個要件：

不想進入 critical section 的 process 不可以阻礙其它 process 進入 critical section，即不可參與進入 critical section 的決策過程。
必須在有限的時間從想進入 critical section 的 process 中，挑選其中一個 process 進入 critical section，隱含No Deadlock。

tips: 有空位時讓「想進的人」「馬上」進入。

Bound waiting：自 process 提出進入 critical section 的申請到獲准進入 critical section 的等待時間是有限的。即若有 n 個 processes 想進入，則任一 process 至多等待 n-1 次即可進入，隱含 No starvation。

二、Peterson's solution — software solution

Two process solution. Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted.

Share variables :

turn：整數，存放的値為 i 或 j，誰擁有此值誰就有資格進入。
flag[i]：布林陣列，表示 i 想不想進去。

do{
 flag[i] = TRUE;
 turn = j; //禮讓的概念

 while ( flag[j] && turn == j); //想進去且輪到他進去

 CRITICAL SECTION

 flag[i] = FALSE;

 REMAINDER SECTION

} while (TRUE);

1. Mutual exclusion

若 $P_i$ 與 $P_j$ 皆想進入自已的 C.S.，代表 flag[i] = flag[j] = true，而且會分別執行到 turn = i 及 turn = j 之設定，只是先後次序不同，turn 的值僅會是 i 或 j，絶不會兩者皆是。

2. Progressive

若 $P_i$ 不想進入 C.S.，則表示flag[i] = false。此時若 $P_j$ 想進入自已的 C.S.，必可通過 while(flag[i] and turn = i) do no-op 這個空迴圈而進入其 C.S.，不會被 $P_i$ 阻礙。

若 $P_i$ 與 $P_j$ 皆想進入自已的 C.S.，則在有限的時間內，$P_i$ 與 $P_j$ 會分別執行到 turn = i 及 turn = j 之設定 (只是先後次序不同)，turn 値必為 i 或是 j。因此 $P_i$ (或 $P_j$) 會在有限的時間內進入自已的 C.S. (No Deadlock)。

3. Bounded-waiting

$P_i$ 離開 C.S. 後又企圖立刻進入自已的 C.S.，此時 $P_i$ 一定會執行 turn = j，使得 $P_i$ 無法再搶先於 $P_j$ 進入自已的 C.S.。所以 $P_j$ 至多等待一次即可進入 C.S.。

1. Failed Algorithm 1 : Only Turn

repeat
 while(turn!=i)do no-op
  C.S.
 turn = j;
  R.S.
until False

違反 Progress (違反條件1)： 假設目前 turn 值為 i ，但 $P_i$ 不想進入 critical section。若此時 $P_j$ 想進critical section $P_j$ 卻無法進入被 $P_i$ 阻礙，因為只有 $P_i$ 才有資格將 turn 值改為 j (想進入無法馬上進入)。

2. Failed Algorithm 2 : Only Flag

repeat
 flag[i] = True
 while( flag[j] ) do no-op;
  C.S.
 flag[i] = False
  R.S.
until False

Progress違反(違反條件2)： 如 $P_i, P_j$ 依下列順序執行，則 $P_i, P_j$ 皆無法進入 critical section 形成 Deadlock 。

lag[i] = True;
lag[j] = True;
while( flag[j] );
while( flag[i] ); // 太有禮貌，大家都想進都進不了

三、Disable interrupt — hardware instructions support

1. TestAndSet：檢查並設置是一種不可中斷的基本 (原子) 運算 (atomically)，它會寫值到某個記憶體位置並傳回其舊值。

2. Swap：a, b 兩值互換。

hardware solution 缺點 (特指 TAS 和 SWAP)

只有kernel mode 能用
need time
多處理機上會失效，單處理機上不好(busy waiting)
starvation

[感覺] 簡易解法違反 bounded waiting：未規範order使得次序以亂數決定。

/* Test_and_Set C.S. example */
repeat
 while(Test_and_Set(Lock)) do no-op; //entry
  C.S.
 Lock = False; //exit
  R.S.
until false

/* SWAP C.S. example */
Repeat
 key = true;
 repeat
  SWAP(Lock, key);
 until key = False;
  C.S.
 Lock = False;
  R.S.
Until false

[用心去感覺] Software & Hardware solution 整理

Uniprocessor

Interrupt disabling

Only available in kernel space
Increase interrupt latency

Spin lock (test and set, swap)

Waste CPU cycles

Multiprocessor

Interrupt disabling

Too costly to broadcast interrupt disabling
Does not work if two involved processes run on different processors

Spin lock

Waste CPU cycle, but seem to be the only choice

四、Semaphore

Semaphore 是一個同步物件，用於保持在 0 至指定最大值之間的一個計數值。(Semaphore do not require busy waiting, using waiting queue)

當執行緒完成一次對該 semaphore 物件等待 (wait(S) / P(S)) 時，該計數值 S-1；
當執行緒完成一次對semaphore 物件釋放 (signal(S) / V(S)) 時，計數值 S+1。
當計數值為 0，則執行緒等待該 semaphore 物件直至該 semaphore 物件變成 signaled (>0)狀態。

用途設置：

Sequencing (event) : value = 0
Mutex : value = 1
Capacity control : value = n_capacity

[感覺] Semaphore 發明者 Dijkstra 是荷蘭人，所以 P(), V() 意思就是英文的 wait(), signal()。

1. 例題 : Sequencing

傑克和羅絲相約去看電影，兩人約在電影院門口見面，如果有人先到的話要等另一人到了才可以進入電影院。

R=0;J=0;
jack(){
   signal(J); //自己到了，一定要先 signal 再 wait 不然會有 deadlock。
   wait(R); //等 
   // see the movie
}
ross() { 
   signal(R); 
   wait(J);
   // see the movie
}

2. 例題 : Mutex 和 Capacity control

A DMA controller offers 4 DMA channels for simultaneous data transfers.

S=4; T=1; c[4]={F,F,F,F};

proc() { 
wait(S);  //容量控制(一個房間最多4人)
wait(T);  //保護c[4]避免複寫(一次只有一個人找位子坐)

// pick one unused channel among c[0],c[1],c[2],c[3] 
// setup DMA transfer 

signal(T);

// wait for DMA completion 

signal(S);

五、Classical Problem of Synchronization

1. Bounded-Buffer Problem

N 個 buffers，Producer 製造項目，Consumer 消耗項目。

Shared data：

N Buffer initial mutex = 1 ：互斥鎖，避免同時複寫
initial full = 0：producer signal，consumer wait
initial empty = N：producer wait，consumer signal

[感覺1] consumer「製造空白」

[感覺2] 如果 mutex 在 full, empty semaphore scope 之外，則當全空或全滿時會形成 deadlock。

/* P1 : producer */

do{
 wait(empty); // producer 吃掉 "empty"
 wait(mutex);

 // add a item to the buffer

 signal(mutex);
 signal(full); //producer 排出 "full"

}while(1);


/* P2 : comsumer */

do{
 wait(full); // comsumer 吃掉 "full"
 wait(mutex);

 // remove an item from buffer

 signal(mutex);
 signal(empty); //comsumer 排出 "empty"

}while(1);

2. Readers-Writers Problem

Allow multiple readers to read at the same time. Only one single writer can access the shared data at the same time.

Readers – only read the data set; they do not perform any updates
Writers – can both read and write.

Shared Data :

data set
int readcount = 0
Semaphore mutex = 1 (in order to protect readcount)
Semaphore wrt = 1

/* writer */

do{
 wait(wrt);
 
 // writing is performed
 
 signal(wrt);

}while(true);


/* reader */

do{
 wait(mutex);
 readcount++;
 if(readercount == 1) wait(wrt); 
 signal(mutex)

  // reading is performed
 
 wait(mutex);
 readcount--;
 if(readcount == 0) signal(wrt); 
 signal(mutex);

}while(true)

[感覺] 這個排程對 reader 有利

reader 一直來 writer 會 starvation. (眾 reader 相當於是一個很愛佔位的 writer)
No readers will wait until the writer locked the shared object.
Readers need not to sync with each other.

3. Philosophers Problem

每個哲學家有 3 種狀態：

thinking — 不想吃飯，思考中。
hungry — 想吃飯。
eating — 取得左右筷子，可吃飯。

Shared variables：

data set
chopstick[0...4] of semaphore

repeat
 wait(chopstick[i]); 
 wait(chopstick[i+1] mod 5);

  //eating 

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

until False;

錯誤版本！此程式並不正確，會有 Dead Lock 問題 (循環取得左邊筷子)。

Alternatives :

One person get the left stick first, the rest get the right stick first (avoid circular waiting)
Allow up to 2 people having sticks (more semaphore)
Two sticks are picked simultaneously (low concurrency)

4. Sleeping Barber Problem

有兩種process ：

Barber — 沒有客人則等待，否則一個一個剪。
Customer — 若有椅子可坐，則坐下等待，否則離開店內。

Shared variables :

initial Semaphore custReady = 0：event，表示有無等待的 customer。
initial Semaphore barberReady = 0：event，表示 barber 是否準備就緒。
initial int accessWRSeats = N：店內有幾張椅子

# The first two are mutexes (only 0 or 1 possible)
Semaphore barberReady = 0
Semaphore accessWRSeats = 1     # if 1, the number of seats in the waiting room can be incremented or decremented
Semaphore custReady = 0         # the number of customers currently in the waiting room, ready to be served
int numberOfFreeWRSeats = N     # total number of seats in the waiting room


def Barber():
  while true:                   # Run in an infinite loop.
    wait(custReady)             # Try to acquire a customer - if none is available, go to sleep.
    wait(accessWRSeats)         # Awake - try to get access to modify # of available seats, otherwise sleep.

    numberOfFreeWRSeats += 1    # One waiting room chair becomes free.
    
    signal(barberReady)         # I am ready to cut.
    signal(accessWRSeats)       # Don't need the lock on the chairs anymore.

    # (Cut hair here.)


def Customer():
    wait(accessWRSeats)         # Try to get access to the waiting room chairs.

    if numberOfFreeWRSeats > 0: # If there are any free seats:
      numberOfFreeWRSeats -= 1  #   sit down in a chair
      signal(custReady)         #   notify the barber, who's waiting until there is a customer
      signal(accessWRSeats)     #   don't need to lock the chairs anymore
      wait(barberReady)         #   wait until the barber is ready

      # (Have hair cut here.)

    else:                       # otherwise, there are no free seats; tough luck --
      signal(accessWRSeats)     #   but don't forget to release the lock on the seats!
      
      # (Leave without a haircut.)

# may lead to starvation of a customer

六、Monitors

Monitors 是一個用來解決同步問題的高階資料結構(物件導向)。(Semaphore and monitor have the same power in solving synchronization problem.)

Monitors 的組成 :

共享變數宣告區
一組程序
初始區

特色 :

宣告在 monitor 的變數只有 monitor 的 procedure 可以存取 (類似class中的private區)。
monitor 中有 condition 型態的變數，提供 programmer 設計同步問題之用(for sync policy)。
monitor 直接保障 monitor 中變數和程序的互斥性質(mutex, not sync policy)，不可有多個 process 呼叫 monitor 的某個程序 (在 semaphore 中要多加許多 mutex 保護變數)。

monitor name{
 
 // share variable declarations

 pro1(){...}
 pro2(){...}

 init code(){...}
}

References

Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720

聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/

洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057

Pages

2017年8月22日星期二