Semaphore（信號量）

信號量（Semaphore）是作業系統提供的一種「軟體層級」的同步工具，用於管理對共享資源的訪問。它本質上是一個整數變數，並搭配兩個原子性的操作：wait() 和 signal()。這使得它不僅可以實現互斥，還能用來處理資源共享和程序間通知等更廣泛的同步問題。

核心組成與操作

wait(S) 操作：

• 又稱 P() 或 down()。
• 當執行緒需要資源時，呼叫此操作。
• 它會先將信號量的值減 1 (S--)。
• 如果 S 的值小於零，代表目前沒有可用的資源，執行緒會被阻塞（block），進入睡眠狀態並被加入一個等待佇列中，讓出 CPU。
• 如果 S 的值大於或等於零，代表仍有資源可用，執行緒可以繼續執行。

signal(S) 操作：

• 又稱 V() 或 up()。
• 當執行緒使用完資源後，呼叫此操作來釋放資源。
• 它會將信號量的值加 1 (S++)。
• 如果 S 的值小於或等於零，這表示有其他執行緒正在等待資源。此時，signal() 會從等待佇列中喚醒一個被阻塞的執行緒，讓它能夠繼續執行。

這兩個操作（wait() 和 signal()）的原子性至關重要。這意味著當一個執行緒正在執行其中一個操作時，其他執行緒不能同時干擾它。這通常需要底層硬體的支援來確保。

信號量的類型

根據信號量初始值的不同，信號量可以分為兩種類型：

二元信號量（Binary Semaphore）：

• 初始值為 1。
• 它的功能與互斥鎖（Mutex）非常相似，因為它只允許一個執行緒在給定時間內訪問臨界區。當一個執行緒獲取鎖後，信號量的值變為 0，阻止其他執行緒進入。
• 主要用於實現互斥，保護共享資源。

計數信號量（Counting Semaphore）：

• 初始值大於 1。
• 它可以用來控制對多個同類資源的訪問。例如，一個信號量初始值為 5，代表有 5 個資源可用。當一個執行緒取得資源時，信號量的值減 1；當它釋放資源時，值加 1。只有當信號量的值為零時，新的請求才會被阻塞。
• 主要用於實現資源計數和資源限制。

改進版信號量：避免忙等

前面版本使用了 while (S <= 0) 的忙等（busy-wait）迴圈，這在單核心系統上會浪費 CPU 資源。而改進版信號量則加入了等待佇列（queue），有效解決了這個問題。當資源不可用時，執行緒會被加入佇列並進入睡眠狀態（sleep()），讓出 CPU。當資源被釋放時，signal() 會從佇列中喚醒一個等待的執行緒（wakeup()），實現更高效的資源利用。

// 改進版 Semaphore 實作核心
wait(semaphore *S) {
    S->value--; // 資源數減一
    if (S->value < 0) {
        add this process to S->list; // 將當前執行緒加入等待佇列
        sleep();                     // 進入睡眠狀態，讓出 CPU
    }
}

signal(semaphore *S) {
    S->value++; // 資源數加一
    if (S->value <= 0) {
        P = remove a process from S->list; // 從佇列中移除一個執行緒
        wakeup(P);                       // 喚醒該執行緒
    }
}

以三大同步條件回顧信號量

• ✅互斥（Mutual Exclusion）: 信號量可以透過二元信號量來保護臨界區，確保同一時間只有一個（或固定數量）的執行緒可以訪問共享資源。
• ✅進度（Progress）: 如果沒有執行緒在臨界區，且有執行緒正在等待，signal() 操作會保證喚醒一個等待者，讓它能繼續執行，從而推動系統進度。
• ✅有限等待（Bounded Waiting）: 標準的信號量實作不保證有限等待，可能導致某些執行緒永遠無法取得資源（飢餓，Starvation）。然而，若將其與**先進先出（FIFO）**等公平的等待佇列機制結合，則能完全滿足這個條件。這也是你提供的改進版信號量實作所做到的。

Monitor

Monitor 是一種高階、語言層級的同步工具，旨在簡化並強化執行緒間的同步操作。它將共享資料、操作共享資料的函式，以及同步機制（如鎖和條件變數）封裝在一個單一的物件中。其核心優勢是內建了「互斥保護機制」，可以大幅減少因手動管理鎖而產生的常見錯誤。

Semaphore/Mutex 的常見問題

手動使用信號量（Semaphore）或互斥鎖（Mutex）時，程式設計師很容易犯下以下錯誤，這些錯誤可能導致嚴重的同步問題，例如死鎖（deadlock）或資料不一致：

• signal() 寫在 wait() 前：可能造成資源在沒有人等待時被釋放，後續需要資源的執行緒將會被錯誤地允許進入臨界區，導致多人同時訪問共享資源。
• wait() 寫錯地方：若不小心呼叫兩次 wait()，執行緒會被永久阻塞，無法繼續執行。
• 忘了寫 signal()：當一個執行緒完成對共享資源的操作後，若忘記釋放鎖，所有其他等待該資源的執行緒將會永遠等不到通知，導致死鎖。

Monitor 的目的正是要解決這些問題。它將鎖的管理交由語言或編譯器自動處理，確保在執行 Monitor 內部程式碼時，永遠只有一個執行緒可以進入。

Monitor 的組成與結構

Monitor 通常由以下三個部分組成：

• 共享資料（Shared Data）：這是 Monitor 內部要保護的私有變數和資源。只有 Monitor 內部的成員函式可以訪問它們。
• 成員函式（Member Functions）：這些是操作共享資料的公有函式。Monitor 的核心特性是，每次只允許一個執行緒進入並執行這些函式。這個互斥鎖機制是自動且隱藏的。
• 條件變數（Condition Variables）：這是 Monitor 的一個關鍵組件。當一個執行緒無法繼續執行（例如，因為所需資源不足），它會呼叫條件變數上的 wait() 操作，將自己暫停。當其他執行緒滿足了條件後，可以透過 signal() 來喚醒等待的執行緒。

// Monitor 的邏輯結構範例
monitor MonitorName {
    // 共享資料，只能由 Monitor 內部的函式存取
    shared_data_type buffer[BUFFER_SIZE];
    int count = 0;

    // 條件變數，用於管理等待的執行緒
    condition full, empty;

    // 成員函式，自動受互斥鎖保護
    void produce(item_type item) { // 自動加鎖
        while (count == BUFFER_SIZE) {
            full.wait(); // 如果緩衝區已滿，進入等待狀態
        }
        buffer[count++] = item;
        empty.signal(); // 通知有空間可以取用
    } // 自動解鎖

    void consume(item_type &item) { // 自動加鎖
        while (count == 0) {
            empty.wait(); // 如果緩衝區為空，進入等待狀態
        }
        item = buffer[--count];
        full.signal(); // 通知有空間可以生產
    } // 自動解鎖

    // 初始化函式
    initialization() { ... }
}

Monitor 呼叫邏輯與排程策略

當 Monitor 內部的一個執行緒（A）呼叫 x.signal() 來喚醒另一個正在等待的執行緒（B）時，只有一個執行緒能留在 Monitor 內執行。這時，就會產生一個關鍵的排程問題：A 和 B 誰該繼續執行？常見的解決策略有三種：

第一，Signal-and-Wait（Hoare-style）：

• A 喚醒 B 後，A 立即進入等待狀態，將 CPU 控制權交給 B。
• B 會立即被喚醒並執行。
• 優點：這種方式保證了在 signal() 時，條件（例如緩衝區有空間）是真實的，且 B 可以立刻執行。但實作較為複雜。

第二，Signal-and-Continue（Mesa-style）：

• A 喚醒 B 後，A 繼續執行，直到它離開 Monitor。
• B 被喚醒後，並不會立即執行，而是被放入一個就緒佇列中，等待 A 離開 Monitor 後才能競爭進入。
• 優點：實作簡單，開銷較小。但缺點是，B 醒來時條件可能已不再成立（例如，在 A 離開前，另一個執行緒搶先進入並消耗了資源），因此 B 通常需要再次檢查條件（如使用 while 迴圈）。這也是最常見的實作方式。

第三，Compromise（折衷方案）：

• A 在呼叫 signal() 後，立即退出 Monitor，讓 B 能夠立即接手。這種方式試圖結合前兩者的優點，常見於 Mesa-style 的某些變體。

以三大同步條件回顧 Monitor

• ✅互斥（Mutual Exclusion）：Monitor 內建互斥機制，保證同一時間只有一個執行緒能進入其內部。這是由編譯器和底層系統自動管理的。
• ✅進度（Progress）：如果沒有任何執行緒在執行 Monitor 內部，則等待進入的執行緒將會被允許進入，確保系統可以持續推進。
• ✅有限等待（Bounded Waiting）：這取決於 Monitor 的具體實作。Hoare-style 的實作因為其嚴格的排程策略，可以保證有限等待。然而，更常見的 Mesa-style 實作不保證先來先服務，這可能導致某些執行緒因競爭而出現飢餓（Starvation）。

存活性（Liveness）

存活性（Liveness）是指在一個並行系統中，所有執行緒（或程序）最終都能夠繼續執行，不會因為等待特定條件而無限期地停止。如果一個程式發生無限等待，它就違反了同步機制中的進度（Progress）或有限等待（Bounded Waiting）條件。兩種最常見的存活性問題是死結和優先權反轉。

死結 (Deadlock)

死結是指兩個或多個執行緒彼此互相等待對方所持有的資源，導致所有執行緒都無法繼續執行。這就像一個僵局，沒有人願意讓步。

// 佔用且等待和循環等待
// P0
wait(S); // 持有資源S，等待資源Q

// P1
wait(Q); // 持有資源Q，等待資源S
// P0 等待 P1 釋放 Q，而 P1 等待 P0 釋放 S，形成一個封閉的循環，雙方都無法前進。

優先權反轉 (Priority Inversion)

優先權反轉是指一個高優先權的執行緒被一個低優先權的執行緒間接拖延，導致其無法及時完成工作。這會嚴重影響即時系統（Real-time System）的效能和可靠性。

假設系統中有三個執行緒，優先權由低到高為：L < M < H。

1. 低優先權執行緒 L 取得了某個共享資源的鎖（例如，一個 Mutex）。
2. 高優先權執行緒 H 想要使用同一個資源，但因為鎖被 L 佔用，H 必須等待 L 釋放鎖。
3. 此時，中優先權執行緒 M 開始執行。根據優先權排程，M 的優先權比 L 高，所以 M 會搶佔 CPU 時間，讓 L 無法繼續執行。
4. 因為 M 持續佔用 CPU，L 始終沒有機會執行完畢並釋放鎖。
5. 結果，H 雖然是最高優先權，卻被間接卡住，等待一個無法執行的低優先權執行緒。這就是「優先權反轉」。

解決優先權反轉最常見且有效的方案是優先權繼承 (Priority Inheritance)

當一個低優先權的執行緒（L）佔有高優先權執行緒（H）所需的資源時，它會暫時繼承 H 的高優先權。這讓 L 能夠在最短時間內執行完其臨界區內的程式碼，並盡快釋放資源。一旦資源被釋放，L 的優先權會恢復到原來的等級。這樣就能確保 H 不會被不必要的拖延，從而維持系統的存活性。