# Chp 7 Synchronization Examples

###### tags: `作業系統`

## P.5,6 Bounded-Buffer Problem

又被稱為Producer-consumer problem
生產者產生資料丟到buffer裡面，消費者從buffer拿資料出來
緩衝區滿了的話生產者停止生產，緩衝區空的則消費者停止消費
* n buffers, each can hold one item
* Semaphore **mutex** initialized to **1**(binary)
* Semaphore **full** initialized to **0**(binary)
* Semaphore **empty** initialized to **n**

這個解法用了三個semaphore來避免deadlock跟racing的問題
full與empty用來解決死鎖，而mutex則用來確保一次只有一個執行緒可以修改buffer的內容避免racing
### Producer

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

### Consumer

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

## P.7~10 Readers-Writers Problem

Problem :
allow **multiple readers** to read at the same time
**Only one single writer** can access the shared data at the same time

* Semaphore **rw_mutex** initialized to 1
* Semaphore **mutex** initialized to 1
* Integer **read_count** initialized to 0

### Writer

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

### Reader

do {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex); //writer等待
    signal(mutex);
    ...
    /* reading is performed */
    ...
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex); //讓writer可以執行
    signal(mutex);
} while (true);

Readers-Writers Problem有三種variation

**1.readers-preference**
上面列出的程式碼是第一種，從reader的程式碼可以看到只要第一個讀檔案的reader有等到檔案(第5行)，剩下新來的reader都不用執行第五行就可以直接read，所以稱為readers-preference

**2.writers-preference**
這個的作法就是把跟1.一樣的機制也加到writer上，前面的writer有拿到資源後後面的writer都不用跟reader排隊，只是要等其他writer釋放資源之後才可以寫入。

**3.third readers–writers problem**
這個就是添加了避免1跟2仍然可能會發生的starvation的機制

以上三種，詳細的內容[維基百科](https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem#First_readers%E2%80%93writers_problem)有寫

## Dining-Philosophers Problem


### Algorithm 1

* **會有deadlock**

do {
        wait (chopstick[i] );//同時拿取左邊的筷子時，會造成deadlock
         wait (chopStick[ (i + 1) % 5] );
// eat
         signal (chopstick[i] );
         signal (chopstick[ (i + 1) % 5] );
// think
    } while (TRUE);
    

### Algorithm 2 Monitor Solution

* 沒deadlock，但仍可能有starvation
這個解法也被稱為Arbitrator solution，詳細也請參考[維基百科](https://en.wikipedia.org/wiki/Dining_philosophers_problem#Resource_hierarchy_solution)
當有人要吃飯的時候服務生會等到你左右兩邊的人都沒有要吃的時候才會准你吃就對了

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

}

### Dining-Philosophers歷屆考古
* 107年
* The OS TAs wrote a simple code to simulate the Dining philosophers problem with pthread. The following code is their code. Please check if TAs used mutex lock correctly or not. (10%) And explain if the output is reasonable or not. (Why Philosopher 4 was the first one to think and eat? Could Philosopher 4 and Philosopher 1 eat at the same time?
* 

* Ans.
* 兩種答案:
* 正確: mutex 放置的位置正確或程式邏輯正確，程式可以運行
* 錯誤: deadlock 或其他可能出現的問題(當 5 個 thread 取得左手邊筷子的時間極為接近時)
* 1、4可以同時吃飯

* 106年
* Please describe Dining-Philosophers Problem. (5%) And complete the test function of the monitor below to solve this problem. (10%)
* 
* 

* Ans.
* 
* 若干個哲學家坐在圓桌一起用餐，若其中一人想要進食，就必須同時持有左右兩邊的筷子才行，若在場所有哲學家都持有左手邊的筷子遲遲不放，痴痴地等待右手邊的筷子釋出，便會發生大家都在等待(deadlock)，因此要約定只在左右兩邊的筷子都可用時才能進食

void test(int i){
    if ((state[(i+4)%5]!=EATING)&& 
        (state[(i+1)%5]!=EATING)&&
        (state[i] == HUNGRY)){
            state[i] = EATING;
            self[i].signal();
    }
}

## P.21 Pthreads Synchronization

>[color=#FF00FF]這一頁提到Pthread api有提供的一些東西，像是mutex locks，project2可能會用到
>[name=Neko]