Ch7 Synchronization Examples

7.1 Classic Problems of Synchronization

• Bounded-Buffer Problem
• Reader and Writers Problem
• Dining-Philosophers Problem

7.1.1 The Bounded-Buffer Problem

/*初始設定*/
int n; //有n個buffer 每個可以裝一個東西
semaphore mutex = 1; //提供 mutual exclusion
semaphore empty = n; //空的buffer 
semaphore full = 0;//滿的buffer

/*Producer*/
do {
    ...
    /* produce an item in n e x t _ p r o d u c e d */
    ...
    wait ( empty );
    wait ( mutex );
    ...
    /* add next produced to the buffer */
    ...
    signal ( mutex );
    signal ( full );
    
} while ( true );

/*Consumer*/
do {
    wait ( full );
    wait ( mutex );
    ...
    /* remove an item from buffer to n e x t _ c o n s u m e d */
    ...
    signal ( mutex );
    signal ( empty );
    ...
    /* consume the item in next consumed */
    ...
} while ( true );

7.1.2 The Readers – Writers Problem

假設有一份資料同時(concurrent)有很多process取用。有些人想寫writer，有些人只讀reader。同時有兩個reader沒關係，但是同時有writer跟reader的時候，同步會出問題，因此我們要求writer在寫入時只能有他自己。

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

/*writer*/
while (true) {
    wait(rw_mutex);  // 取得寫入權限
    . . .
    /* writing is performed */
    . . .
    signal(rw_mutex);  // 釋放寫入權限
}

/*reader*/
while (true) {
    wait(mutex);  // 保護 read_count，避免多個 reader 同時修改
    read_count++;
    
    if (read count == 1)  
        wait(rw_mutex);  // 第一個 reader 進來時，鎖住writer
    signal(mutex);  // 釋放 read_count 的 mutex
    . . .
    /* reading is performed */
    . . .
    wait(mutex); // 再次鎖住 mutex，準備修改 read_count
    read count--;
    
    if (read count == 0)
        signal(rw mutex);  // 最後一個讀者離開時，允許寫者進入
    signal(mutex); // 釋放 mutex
}

問題: Writer will be starvation

7.1.3 The Dining-Philosophers Problem

一桌的哲學家要吃飯，只會做兩件事:

1. 吃飯（需要左右的筷子）
2. 思考

7.1.3.1 Semaphore Solution

/* 第i個科學家 */
while (true) {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    . . .
    /* eat for a while */
    . . .
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    . . .
    /* think for awhile */
    . . .
}

每支筷子都用一個semaphore表示，初始值設定1，表示都可以拿。這個解法雖然保證mutual exclusion，但是會造成deadlock。舉例:五個人同時餓了都拿起左邊的筷子。

解法：

1. 最多只允許 4 位哲學家同時吃飯。
2. 只有在左右筷子都可用時，才能拿起。
3. 奇數號哲學家：先拿左邊，偶數號哲學家，先拿右邊。

7.1.3.2 Monitor Solution

限制只有在左右筷子都可用時，才能拿起。列舉他們的狀態：

enum { THINKING, HUNGRY, EATING } state[5];

再判斷左右有沒有在吃飯

state[(i + 4) % 5] != EATING   // 左邊鄰居
state[(i + 1) % 5] != EATING   // 右邊鄰居

缺點：會有starvation