---
# System prepended metadata

title: Classic Problems of Synchronization
tags: [CSIE, OS]

---

# 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
``` c=1
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
``` c=1
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

``` clike=1
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

``` clike=1
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~

```clike=1
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`