# 【資工考研】 OS: Critical Section Design

1. Software solution
2. Hardware support
3. Semaphore
4. Monitor

## 學習架構圖

<table>
<tr>
<th style="text-align:center;">Level</th>
<th colspan="2" style="text-align:center;">內容</th>
<th style="text-align:center;">考點</th>
</tr>
<tr>
<td>高階<br>(programming language level)</td>
<td colspan="2" style="text-align:center;">Monitor</td>
<td rowspan="2" style="text-align:center;">解決著名同步問題</td>
</tr>
<tr>
<td>中階<br>(OS system call level)</td>
<td style="text-align:center;">Mutex lock</td>
<td style="text-align:center;">semaphore</td>
</tr>
<tr>
<td>基礎</td>
<td style="text-align:center;">Software solution</td>
<td style="text-align:center;">Hardware instructions support</td>
<td style="text-align:center;">CS design 3 個性質之滿足</td>
</tr>
</table>

## The Critical Section Problem

會存取到共享變數的那段程式碼即 Critical Section
> A critical section, in which the process may be accessing and updating data that is shared with at least one other process.

剩餘的程式碼區間被稱作 Remainder Section

Process 內的 CS 並未說只能有一個，我們要設計的問題是要讓 processes 之間可以安全共享及存取共享變數
我們會需要同時設計 entry section 與 exit section 之控制

- Entry section: process 想進入 CS 時需要先經過這段，用以視作申請進入 CS
- Exit seciton: process 走出 CS 時必須先經過這段

有三大性質必須滿足：

1. Mutual exclusion
2. Progess
3. Bounded waiting

> We must make **no assumption** concerning the relative speed of the `n` processes.

### Mutual Exclusion

最好理解的，任意時間點，我們只能允許一個 process 在 CS 內執行，其他 processes 絕不允許亦在 CS 內執行

### Progress

1. 僅有不在 RS 內執行的 processes 可以參與「挑選 process 進入 CS 」之決策
2. 不能大家一起死，誰都進不去 CS (No deadlock)

### Bounded waiting

對於任一個想進入 CS 內執行的 process ，其自提出申請直至進入 CS 內的等待次數必須為有限的
要公平，不能總輪不到某些 processes (No starvation)
如果嚴格公平以待，則 `n` 個 processes 皆想進入 CS 時，任一 process 至多等待 `n-1` 次即可進入 CS

## Busy Waiting & Non-busy Wating

Busy waiting 通常是用迴圈之類的方式讓 process 卡在那段程式碼，看起來忙得要死，實際上卻是在等待 (真的就是等得很忙)
相反， Non-busy waiting 則是會把等待中的 Process 從 running state 轉到 waiting state，這個作法的優點很明顯，我們避免了 waiting processes 持續爭奪 CPU 資源；不過代價就是我們需要付出兩次 context switch 的時間

兩種技巧的優劣也就看當前情境下，如果 busy waiting 等沒很久 ($\lt 2$ 次 context switch 的時間) 則此方法有利；反之，不利

### 相似概念比較

<table>
<tr>
<th>System / Solving Race Condition</th>
<th>Disable Interrupt</th>
<th>Spinlock (其實就 CS design)</th>
</tr>
<tr>
<td>Uni-processor</td>
<td>適合</td>
<td>不適合</td>
</tr>
<tr>
<td>Multi-processor</td>
<td>不適合</td>
<td>適合</td>
</tr>
</table>

***

<table>
<tr>
<th style="text-align: center;">判斷誰更有例</th>
<th style="text-align: center;">條件成立</th>
<th style="text-align: center;">條件不成立</th>
</tr>
<tr>
<td>Busy waiting time < 2 * Context switch time ？</td>
<td>Busy waiting</td>
<td>Non-busy waiting</td>
</tr>
</table>

## Software solution

考試通常會給你程式碼，但要你自己判斷是否有違反 CS design 的三個性質

### Peterson's Solution

以下為適用於 2 processes 情境之 solution
不失一般性稱兩 process 的 id 為 `i`, `j`

// shared variables
bool flag[2] = {false, false};
int turn = 0;

// Peterson's solution

while(true)
{
    flag[i] = true;
    turn = j;
    
    while (flag[i] && turn == j);
    
    /**
     * CS
     */
    
    flag[i] = false;
    
    /**
     * RS
     */
}

證明其正確性要會證，不過證明手法採用模擬說明即可
重點在於程式碼跟 3 大性質定義的熟悉度

我是覺得很好懂，所以就不說明了

### Lamport's Bakery Algorithm

上面是 `2` 個 process ，以下是 `n` 個 process

//Shared variables
bool choosing[n] = {false};
int number[n] = {0};

/**
 * @breif Struct to represent a ticket
 */
struct Ticket
{
    int num;
    int id;
    
    bool operator<(const Ticket& other) const
    {
        return (num < other.num) || (num == other.num && id < other.id);
    }
};

// Lamport's Bakery Algorithm
while(true)
{
    choosing[i] = true;
    number[i] = *max_element(number, number + n) + 1;
    choosing[i] = false;
    
    for (int j = 0; j < n; ++j)
    {
        while (choosing[j]);
        
        Ticket other = {number[j], j};
        Ticket curr = {number[i], i};
        while(number[j] && other < curr);
        
        /**
         * CS
         */
        
        number[i] = 0;
        
        /**
         * RS
         */
    }
}

這演算法的精神很形象，就是去麵包店取號碼牌
最小號碼牌支持有者方可進入；若同號則比身分證字號 (pid) ，最小者優先

pid 我們知道，肯定會是唯一的 (unique)，所以我們總會比得出誰最小

***

這種 SW solution 有個問題，現代電腦為了程式執行的效能最佳化，可能會採用 reorder 的技術
但是大佬想出來的精簡寫法亂交換行就肯定會出錯
也就是說我們無法保證其實際運行時的正確性

例如，如果將 Peterson's solution 進行如下 reordering：

while(true)
{
    // 下面這兩行對調了
    turn = j;
    flag[i] = true;
    while (flag[j] && turn == j);
    
    flag[i] = false;
}

則我們思考一遍會發現，如此一來竟違反了 mutual exclusion

## Hardware Support

- Memory Barriers
- Hardware Instructions
- Test-and-set
- Compare-and-set
- Atomic Variables

### Memory Bariers

當某個 processor 所執行的 process 對記憶體內容做出修改，有兩種可能：

1. 其他 processors 也能立刻看到該改變
2. 其他 processors 不一定能看到該改變

Memory barriers 能確保 processors 對 main memory 進行任何操作時，嚴格遵照一定的順序

因此它能：

1. 防止 reordering
2. 確保 processores 所作的操作之可見性

Memory barriers 大致可分為

1. Load (Read) Barriers
2. Store (Write) Barriers
3. Full Barriers
4. Acquire and Release Barriers

要記住，這是硬體支援

### Hardware Instructions

許多系統會提供特殊的硬體指令，這些指令執行時不會被中斷 (保證 atomically)

#### Test-and-set

傳回舊值，並同時寫入 `1` (`true` 的概念)，保證 atomically executed

使用 C 語言的形式來說明上述行為會像是：

bool test_and_set(bool *lock)
{
    bool old_value = *lock;
    *lock = true;
    
    return old_value;
}

假設我們有 test-and-set 指令能用來解 CS Design ，則應該會像是：

 //Shared variables
bool lock = false;
bool waiting[n] = {false};

while(true)
{
    waiting[i] = true;
    bool key = true;
    
    while (waiting[i] && key)
        key = test_and_set(&lock);
    
    waiting[i] = false;
    
    /**
     * CS
     */
    
    int j = (i + 1) % n;
    while (j != i && !waiting[j])
        j = (j + 1) % n;
    
    if (j == i)
        lock = false;
    else
        waiting[j] = false;
    
    /**
     * RS
     */
}

#### Compare_and_set

傳回舊值，如果舊值等於 `expected` 則將其設為新值，保證 atomically executed

使用 C 語言來描述其行為：

int cas(int *value, int expected, int new_value)
{
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    
    return temp;
}

假設有 CAS 指令，我們可以這樣解 CS Design
基本就上面的 code 抄下來改

// Shared variables
bool lock = false;
bool waiting[n] = {false};

while(true)
{
    waiting[i] = true;
    int key = 1;
    
    while (waiting[i] && key == 1)
        key = cas(&lock, 0, 1);
    
    waiting[i] = false;
    
    /**
     * CS
     */
    
    int j = (i + 1) % n;
    while (j != i && !waiting[j])
        j = (j + 1) % n;
    
    if (j == i)
        lock = 0;
    else
        waiting[j] = false;
    
    /**
     * RS
     */
}

### Atomic Variables

像 CAS 這樣的指令並不直接提供互斥，而是作為一個工具來解決設計問題

Atomic variables 如其名，對這樣的變數進行操作都會是 atomic operation

在 C++ 11 之後，標準庫提供了強大的 memory model 包括 `std::atomic`
雖然這是軟體方面的支援，但 `std::atomic` types 的背後便是 hardware-supported atomic instructions

std::atomic<int> counter = 0;

counter.fetch_add(1); // Atomic increment
counter.store(0);     // Atomic store
int value = counter.load(); // Atomic load

## Mutex Lock

互斥鎖，如其名 (Mutex 是 mutual exclusion 的簡稱)

在某個時間，僅能有一個 process or thread 持有鎖

C++ 11 後亦有引入 mutex lock，如 `std::mutex` 等

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx; // Mutex to protect shared resource
int counter = 0;

void increment() 
{
    for (int i = 0; i < 1000; ++i)
    {
        std::lock_guard<std::mutex> lock(mtx); // RAII-style mutex locking
        ++counter;
    }
}

int main() 
{
    std::thread t1(increment);
    std::thread t2(increment);

    t1.join();
    t2.join();

    std::cout << "Counter: " << counter << "\n";
    return 0;
}

回到 OS 提供的 mutex lock ，這是最簡單的工具，我們一樣的可以用軟體實作的方式說明：

std::atomic<bool> lock_flag(false);

void acquire()
{
    while (lock_flag.exchange(true, std::memory_order_acquire));
}

void release()
{
    while (lock_flag.store(false, std::momory_order_release));
}

// example

int counter = 0;

void increment()
{
    for (int i = 0; i < 1000; ++i)
    {
        acquire();
        ++counter;
        release();
    }
}

int main() 
{
    std::thread t1(increment);
    std::thread t2(increment);

    t1.join();
    t2.join();

    std::cout << "Counter: " << counter << "\n";
    return 0;
}

***

在 Linux ，我們有 POSIX threads (pthreads) 可以來使用
考試基本上懂 Linux 這邊提供的東西就好，Windows 有興趣的話請自行研究，我沒用過🫣

註：下面雖然是 C++ code ，但除了 `nullptr` 外基本都是 C 的寫法，考試要給應該會是給 pure C code

#include <pthread.h>

// Mutex to protect shared resource
pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;

int counter = 0;

void* increment(void* arg) 
{
    pthread_mutex_lock(&mtx);
    ++counter;
    pthread_mutex_unlock(&mtx);

    return nullptr;
}

int main() 
{
    pthread_t thread1, thread2;

    pthread_create(&thread1, nullptr, increment, nullptr);
    pthread_create(&thread2, nullptr, increment, nullptr);

    pthread_join(thread1, nullptr);
    pthread_join(thread2, nullptr);

    // Clean up the mutex (optional since we're using a global initializer)
    pthread_mutex_destroy(&mtx);

    return 0;
}

## Semaphore

也是 OS 提供的工具，它會用一個計數器來追蹤可用資源的數量，並提供下列操作：

1. Acquire (P/Wait/Decrement): Decrease the counter, blocking if no resources available
2. Release (V/Signal/Increment): Increase the counter, signaling other threads that a resource is now available

課本上是用 wait / signal 這組稱呼

Semaphore 可以分成兩種：

1. Binary semaphore: 跟 mutex 差不多的行為，counter 只會是 `0` or `1`
2. Counting semaphore: counter 值會是非負值，表示複數資源

使用 semaphore 時需要注意不要誤用，例如寫反 wait 跟 signal 的順序，或是多個 semaphores 使用時的順序安排不當

具體點說，寫反 wait 跟 signal ，會違反互斥；全都寫成 wait 會造成 deadlock 也就是違反 progress

在 C++ 20 以後引入了 semaphore


(看不清楚圖片、使用 edge 的同學把滑鼠一到圖片上按兩次 `Ctrl` 即可縮放)

### 使用 Semaphore 解決知名同步問題

#### Bounded-Buffer Producer/Consumer Problem

std::atomic<bool> running(true);

std::binary_semaphore mtx(1); // Mutex for thread-safe access to the buffer
std::counting_semaphore<N> full(0);
std::counting_semaphore<N> empty(N);

int buffer[N]; // Shared bounded buffer
int in = 0, out = 0;

void producer(int id)
{
    while (running.load())
    {
        // Produce an item
        int item = id; // Just for simplicity
        
        empty.acquire();
        
        mtx.acquire();
        // Add the item to the buffer
        buffer[in] = item;
        in = (in + 1) % N;
        mtx.release();
        
        full.release();
    }
}

void consumer(int id) 
{
    while (running.load()) 
    {
        full.acquire();

        int item;
        
        mtx.acquire();
        // Remove the item from the buffer
        item = buffer[out];  
        out = (out + 1) % N;
        mtx.release();

        empty.release();
    }
}

#### First Reader-Writer Problem

Reader: only read
Writer: both read & write

基本的同步條件：

1. Writer 跟 Writer 或 Reader 間皆互斥
2. Readers 之間不用互斥

在 First R/W 問題中，除非存在某 Writer 已經申請通過，正在執行，否則任何 Reader 皆無須 waiting
這意思就是如果 `R1` is reading `W1` 後面來的要 wait
在 `W1` 後陸續來了`R2`, `R3`, ... 因為 Readers 間不用互斥，所以這些後面來的 Readers 可以直接 read
如果後續仍不斷有 Reader 抵達，則 `W1` 有可能會餓死

- Readers can access the shared resource concurrently if no writers are currently writing.
- A Writer has exclusive access to the shared resource, meaning no other readers or writers can access the resource during writing.

std::atomic<bool> running(true);

std::binary_semaphore mtx(1);
std::binary_semaphore rwMtx(1);
int readerCnt;

void reader(int id)
{
    while (running.load())
    {
        // Readers acquire the mtx to update readerCnt atomically
        mtx.acquire();
        ++readerCnt;
        
        if (readCnt == 1)
            // First reader locks the rwMtx to prevent writers
            rwMtx.acquire();
        // Release the mtx for other readers to enter
        mtx.release();
        
        /**
         * Reading (CS)
         */
        
        // Readers acquire the mtx again to update readerCnt atomically
        mtx.acquire();
        --readerCnt;
        
        if (readerCnt == 0)
            // Last reader releases the rwMtx for writers
            rwMtx.release();
        // Release the mtx for other readers to enter
        mtx.release();
    }
}

void writer(int id)
{
    while (running.load())
    {
        rwMtx.acquire();
        
        /**
         * Writing (CS)
         */
        
        rwMtx.release();
    }
}

這邊可以看出比較需要用心想的是 reader 的部份

#### Second Reader-Writer Problem

- Multiple readers can read concurrently, but only one writer can write, and writers are given priority.
- If there are any writers waiting, no new readers are allowed to enter.

跟 First R/W 顯著的差別是變成 Reader 有可能餓死

std::atomic<bool> running(true);

std::binary_semaphore rwMtx(1);  
std::binary_semaphore x(1);      // Protect readerCnt
std::binary_semaphore y(1);      // Protect writerCnt
std::binary_semaphore z(1);      // Delay readers   
std::binary_semaphore rsem(1);   // Block new readers

int readerCnt = 0;  
int writerCnt = 0;  

void reader(int id) 
{
    while (running.load()) 
    {
        // Ensure no writer is waiting
        z.acquire();
        rsem.acquire();
        x.acquire();
        
        ++readerCnt;
        
        if (readerCnt == 1) 
            // First reader locks rwMtx to prevent writers from accessing the resource
            rwMtx.acquire();
        
        x.release();
        rsem.release();
        z.release();  // Allow other readers to enter

        /**
         * Reading (CS)
         */
        
       
        x.acquire();
        
        --readerCnt;
        
        if (readerCnt == 0) 
            // Last reader releases rwMtx to allow writers
            rwMtx.release();
        
        x.release();
    }
}

void writer(int id) 
{
    while (running.load()) 
    {
        // Writer waits for entry and ensures mutual exclusion
        y.acquire();
        
        ++writerCnt;
        
        if (writerCnt == 1)
            // First writer blocks readers by locking z
            rsem.acquire();
        
        y.release();
        
        /**
         * Writing (CS)
         */
        
 
        y.acquire();
        
        writerCnt--;
        
        if (writerCnt == 0)
            // Last writer releases z, allowing readers to enter
            rsem.release();
        
        y.release();
    }
}

#### The Sleeping Barber Problem

std::atomic<bool> running(true);

std::binary_semaphore barberReady(0);
std::binary_semaphore customerReady(0);
std::binary_semaphore mtx(1);

int waiting = 0;

void barber(int id)
{
    while (running.load())
    {
        customerReady.acquire();
        mtx.acquire();
        --waiting;  
        mtx.release();
        
        /**
         * Barber is cutting hair
         */
        
        barberReady.release();
    }
    
    /**
     * Barber is closing the shop
     */
}

void customer(int id)
{
    mtx.acquire();
    if (waiting < N) // If ther are free chairs
    {
        ++waiting; // Take a seat
        
        mtx.release();
        customerReady.release(); // Notify the barber
        barberReady.acquire();
        
        /**
         * Customer got a hiarcut
         */
    }
    else
        mtx.release(); // No chairs available, leave
}

#### Dining-Philosophers Problem (chopsticks version)

五位哲學家坐在餐桌上，兩兩之間擺一根筷子
哲學家可是三種狀態：思考、飢餓、正在吃

##### Naive Implementation

std::atomic<bool> running(true);

const int N = 5;
std::binary_semaphore chopsticks[N] {1, 1, 1, 1, 1};

void philosopher(int id)
{
    while (running.load())
    {
        /**
         * Thinking
         */
        
        /**
         * Hungry now
         */
        
        chopsticks[id].acquire();
        chopsticks[(id + 1) % N].acquire();
        
        /**
         * Eating
         */
        
        chopsticks[(id + 1) % N].release();
        chopsticks[id].release();
    }
}

上述 code 有個問題，那就是可能發生 deadlock
那避免的方法就跟破除 deadlock 的方法相同

##### Deadlock-Free Solution

(e.g. breaks the circular waiting condition)

std::atomic<bool> running(true);

const int N = 5;
std::binary_semaphore chopsticks[N] {1, 1, 1, 1, 1};


void philosopher(int id)
{
    while (running.load())
    {
        /**
         * Thinking
         */
        
        /**
         * Hungry now
         */
        if (id == N - 1) // Last philosopher picks up right first
        {
            chopsticks[(id + 1) % N].acquire();
            chopsticks[id].acquire();
        }
        else
        {
            chopsticks[id].acquire();
            chopsticks[(id + 1) % N].acquire();
        }
        
        /**
         * Eating
         */
        
        chopsticks[(id + 1) % N].release();
        chopsticks[id].release();
    }
}

### 使用 Binary semaphore 實作 Counting semaphore

class CountingSemahpore
{
private:
    int m_cnt;
    std::binary_semaphore m_mtx;
    std::binary_semaphore m_cntSem;
    
public:
    CountingSemaphore(int cnt) : m_cnt(cnt), m_mtx(0), m_cntSem(1) 
    {
        assert(m_cnt >= 0);
    }
    
    void acquire()
    {
        m_cntSem.acquire();
        if (--m_cnt < 0)
        {
            m_cntSem.release();
            m_mtx.acquire();
        }
        else
            m_cntSem.release();
    }
    
    void release()
    {
        m_cntSem.acquire();
        if (++m_cnt <= 0)
            m_mtx.release();
        m_cntSem.release();
    }
};

## Monitor

Mointor 是一種高階的同步機制，將共享資源及其操作封裝，以確保互斥存取與同步條件

我們可以把 Mointor 視作一個模組，就很像物件導向程式設計中的 class 那樣
其中的共享變數無法被外部直接存取，就像 class 的 private data
操作這些共享變數的 operations 就像 class 的 method

我們說過，semaphore 雖然已經相當方便好用了，但 programmer 誤用的話仍是災難

Monitor 因其特性，本身就保證了互斥：

同一時間至多允許一個 process (or thread) 可以呼叫 monitor 中的某個 function，這確保共享資源之存取不會發生 race condition
站在 programmer 的立場，只需要處理同步條件即可，所以 monitor 比起 semaphore 還要容易使用

### Condition Synchronization

條件尚未滿足時，thread 進入 wait ，直到條件滿足再繼續執行
Monitor 使用 condition variable 來實現該功能，包括以下兩個操作：

1. `wait`
2. `signal`

### Monitor 的種類

依照 `signal` 的語意不同大概可分為四種：

1. SC (Signal-and-continue)
2. SW (Signal-and-wait)
3. Hoare (Signal-and-urgent-wait)
4. SW + signaling thread have priority to reenter

這部分也算是 `condition variables` 設計上的不同：

1. Blocking Condition Variables
2. Non-blocking Condition Variables

#### Blocking Condtion Variables

Signal-and-urgent-wait 跟 Signal-and-wait 正是屬於 blocking condition variable 這類
他們的特色是 signaling thread 必須要在 monitor 外至少等到 signaled thread 放棄佔據 monitor 或著又再次被 condition variable 卡住
因為是由 Hoare 等人提出的，所以 Signal-and-urgent-wait 類型的 monitor 通常被稱作 Hoare-style monitors
這是理論上很優秀的設計

然而，當有 condition variable is signaled 且至少有一個 thread 正為此 condition variable 而 waiting
Signaling thread 釋出 monitor 給 signaled thread 這一動作必須做到無縫銜接
這部分是有實作難度的

Hoare-style 跟 SW 的差別在於 monitor object 內除了 entrance queue 外，Hoare-style 還會有個 queue 是給 signaled thread 的，這個的優先級會高於 entrance queue

包括 condition variable 的 waiting queue 在內，這些 queues 通常保證是公平的，有些實作還會保證其遵守一般認知中 queue 具有的 FIFO 性質

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Monitor_%28synchronization%29-SU.png/400px-Monitor_%28synchronization%29-SU.png" alt="Hoare-style monitor" style="display: block;margin-left: auto;margin-right: auto;">

#### Non-blocking condition variables

SC 或者與之類似的 Masa style 與 Hoare-style 的策略不同，signaling thread 並不會在發 signal 後而失去 monitor 的霸佔權，signaled thread 必須乖乖去 queue 排隊

在 non-blocking condition variable 中 signal 的動作通常被稱作 notify

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/1/15/Monitor_%28synchronization%29-Mesa.png/400px-Monitor_%28synchronization%29-Mesa.png" alt="Mesa-style monitor" style="display: block;margin-left: auto;margin-right: auto;">

在 Java 中需要 mutual exclusion 的 method 需要加上 `synchronized` 的 keyword
沒記錯的話， Java 更細節的實作方法好像也被 C# 拿去用
不過這些細節我們不用知道更多

<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Monitor_%28synchronization%29-Java.png/400px-Monitor_%28synchronization%29-Java.png" alt="Java style monitor" style="display: block;margin-left: auto;margin-right: auto;">

***

課本雖然說 monitor 對 programmer 更容易 (考試請記這樣)，但就我自己查資料下來，monitor 的誕生反映出來的應該是物件導向程式設計的浪潮

如果能像 OOP 那樣把互斥這些性質封裝好，那肯定是優雅的
所以其實並不是說只用 mutex 之類的就不行 只是顯然這樣就不夠優雅 對吧

C++ 標準庫並未支援 monitor 不過他有提供了 condition variable
我自己的解讀是：更高層次的抽象化就交給你們自己了

我們就用 mutex 和 condition variable 來模擬 monitor ，並再次解決 Dining Philosophers Problem 吧

### Solve Dining Philosophers Problem Again

enum class PhilosopherState
{
    THINKING,
    HUNGRY,
    EATING,
};

constexpr int N = 5;

class DiningPhilosophers
{
private:
    std::array<std::mutex, N> chopsticks;
    std::array<std::condition_variable, N> self;
    std::array<PhilosopherState, N> states;
    std::mutex mtx;
    
    void test(int phID)
    {        
        const int left = (phID + 4) % N;
        const int right = (phID + 1) % N;
        
        if (states[phID] == PhilosopherState::HUNGRY &&
            states[left] != PhilosopherState::EATING &&
            states[right] != PhilosopherState::EATING)
        {
            states[phID] = PhilosopherState::EATING;
            chopsticks[left].unlock();
            chopsticks[right].unlock();
            self[phID].notify_one();
        }
    }
public:
    DiningPhilosophers() : chopsticks(), self(), states(), mtx() 
    {
        states.fill(PhilosopherState::THINKING);
    }

     void pickup(int phID)
     {
        std::unique_lock<std::mutex> lock(mtx);
         
        states[phID] = PhilosopherState::HUNGRY;
        test(phID);
         
        if (states[phID] != PhilosopherState::EATING)
            self[phID].wait(lock);
     }
    
    void putdown(int phID)
    {
        std::unique_lock<std::mutex> lock(mtx);
        states[phID] = PhilosopherState::THINKING;
        
        const int left = (phID + 4) % N;
        const int right = (phID + 1) % N;
        
        test(left);
        test(right);
    }
};

使用方式 (example)：

void philosopher(DiningPhilosophers& dp, int id)
{
  
    std::cout << "Philosopher " << id << " is thinking\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));
        
    std::cout << "Philosopher " << id << " is hungry now\n";
    dp.pickup(id);
        
    std::cout << "Philosopher " << id << " is eating\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(1000)); 
        
    dp.putdown(id); 
}

### Implemantation of a Monitor Using Semaphores

提供一個大致想法輪廓

class Monitor 
{
private:
    std::binary_semaphore m_mtx{1};
    std::binary_semaphore m_next{0};
    std::binary_semaphore m_otherSem{0};
    int m_nextCnt = 0;
    int m_otherCnt = 0;

protected:
    void enter() { m_mtx.acquire(); }

    void leave() 
    {
        if (m_nextCnt > 0)
            m_next.release();  
        else
            m_mtx.release(); 
    }

    void wait() 
    {
        ++m_otherCnt;
        if (m_nextCnt > 0) 
            m_next.release(); 
        else
            m_mtx.release();
        
        m_otherSem.acquire(); 
        --m_otherCnt;
    }

    void signal() 
    {
        if (m_otherCnt > 0) 
        {
            ++m_nextCnt; 
            m_otherSem.release(); 
            m_next.acquire();  
            --m_nextCnt;
        }
    }

public:
    Monitor() = default;
    virtual ~Monitor() = default;

    class MonitorGuard 
    {
    private:
        Monitor& monitor;

    public:
        explicit MonitorGuard(Monitor& m) : monitor(m) { monitor.enter(); }
        ~MonitorGuard() { monitor.leave(); }
    };
};

這邊要知道的是， monitor 跟 semaphore 解決 CS design problem 的能力是等價的
這是選擇題的重要考點