# Classic Problems of Synchronization

## Bounded-Buffer Problem
* 兩個 process shared 下列變數

* 假設一個 pool 中有 n 個 buffer

* mutex semaphore 提供mutex exclusion
* 初始值為1

* empty and full semaphore 計算有幾個空的和滿的 buffer
* empty 初始值為 n

* full 初始值為 0

* producer process

do    {
    ...
    /* produce an item in next_produced */
    ...
    wait(empty);
    wait(mutex);
    ...
    /* add next_produced to the buffer */
    ...
    signal(mutex);
    signal(full);

} while(ture);

* consumer process

do    {
    wait(full);
    wait(mutex);
    ...
    /* removed an item from buffer to next_consumed */
    ...
    signal(mutex);
    signal(empty);
    ...
    /* consumed the item in next_consumed */
    ...
} while(true);

---

## Readers-Writers Problem

* readers(只想看的人)
* writers(想要更新的人，看+寫)
* 兩種行程的優先權變化會衍生不同類型的問題
* 討論兩種問題
1. 所有的reader都不需要等待，除非有writers得到權限
* 這個問題是指當writer在執行時其他reader不能執行
* readers們要等writer好了才能看

2. 一旦writer準備好了，他馬上就要執行
* writer優先權高過reader
* 當writer準備好了，沒有reader可以開始讀

### 第一種 reader-writer
* readers 間共用下列變數
* semaphore rw_mutex = 1;
* 也和 writers 共用
* mutual exclusive for the writers
* 第一個和最後一個 reader 進入 critical section 時也會用到

* semaphore mutex = 1;
* mutual exclusive for updating ``read_count``

* int read_count = 0;
* 有幾個 reader 在讀
* READER

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

* WRITER

do    {

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

* 小結

1. 如果writer在critical section 內，外面有n個reader在等
* 第一個reader會被queue在rw_mutex
* 其他的會被queue在mutex

2. 當writer執行signal(rw_mutex)時
* 其他在外面等的reader或是一個writer就可以進繼續執行

3. writer may starve
* 第一個reader想進去的時候，rw_mutex = 1，reader進去
* 並且之後每個進去的reader wait掉mutex後，因為read_count != 1，所以接著又可以把mutex signal，讓後面的reader可以依序進入
* writer進不去(因為rw_mutex = 0)，但reader可以進去
* writer要等到所有reader都出來它才能進去
---

## Dining-Philosophers Problem

* 多個process對多個資源的存取
* Solution
* 每個筷子當作semaphore
* 拿起筷子 = wait()
* 放下筷子 = signal()
* the structure of philosoper ~i~

do    {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    ...
    /* eat for a while */
    ...
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    ...
    /* think for a while */
    ...
    
} while(true);

* deadlock happened

* 當所有哲學家同時肚子餓，且都拿起左手邊的筷子

* 所有的「筷子的值」 = 0

* 當他們都想拿起右邊的筷子時

* deadlock 發生

* deadlock 解決辦法
1. 最多允許四個哲學家同時坐在餐桌前

2. 只允許可以同時拿兩邊筷子的哲學家拿筷子(直接進入 critical section)

3. 奇數位子的人先拿左邊的筷子再拿右邊的筷子; 偶數位子的人先拿右邊的筷子再拿左邊的筷子

* deadlock-free solution does not necessarily eliminate the possibility of starvation

---

##### last edit
> [name=dot] [time=Wed, Dec 25, 2019 5:33 PM]

[HOME PAGE](/bKDZoNkrT9SOBnTvY_aj2Q?edit) :thought_balloon:

{%hackmd theme-dark %}
###### tags: `OS` `CSIE`