2017年8月22日 星期二

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





技術提供:Blogger.