今天楊柳颱風來，大家還好嗎
台南這邊就真的很有颱風的感覺，路上騎車就是一直瘋狂飄移

在現代作業系統中，程式不只是單獨執行。為了更有效率地利用硬體資源，多個程式（或程式中的執行緒）經常會並發（Concurrent）或平行（Parallel）地執行。這帶來了一個經典的挑戰：當多個程式同時存取並修改同一份共享資料時，如果不加以控制，就可能導致資料混亂或錯誤。

補充（前面有提到）

• 並發：一顆 CPU 上切換多個 process(快速 context switch)
• 平行：多核心同時執行多個 process

Producer & Consumer 問題

這邊我們以Producer & Consumer（生產者與消費者）問題為例：

想像一下，你有一個共享緩衝區（Buffer），它的容量是固定的。

• Producer（生產者）：負責生產物品，並將它們放入緩衝區。
• Consumer（消費者）：負責從緩衝區取出物品進行消費。
  兩者都獨立運行，但共享同一個緩衝區。

// 緩衝區資料
#define BUFFER_SIZE 10
int buffer[BUFFER_SIZE];
int in = 0;   // 負責寫入的位置
int out = 0;  // 負責讀取的位置
int count = 0;  // 緩衝區中物品的數量

Producer 的程式碼：

// Producer
while (true) {
    // 檢查緩衝區是否已滿
    while (count == BUFFER_SIZE) ; 
    
    // 如果未滿，將新物品放入緩衝區
    buffer[in] = next_produced;
    
    // 更新寫入位置
    in = (in + 1) % BUFFER_SIZE;
    
    // 更新物品總數
    count++;
}
// 這段程式碼看起來很直觀：當緩衝區滿了，Producer 就會停下來等待。如果還有空間，它就把東西放進去，並將物品總數 count 加一。

Producer 的程式碼：

// Consumer
while (true) {
    // 檢查緩衝區是否為空
    while (count == 0) ;
    
    // 如果不為空，取出物品
    next_consumed = buffer[out];
    
    // 更新讀取位置
    out = (out + 1) % BUFFER_SIZE;
    
    // 更新物品總數
    count--;
}
// 同樣地，Consumer 的程式碼也很簡單：當緩衝區空了，它就停下來等待。如果有東西，它就取出來，並將物品總數 count 減一。

乍看之下，這兩段程式碼似乎沒有問題。然而，當 Producer 和 Consumer 同時執行時，一個嚴重的問題就產生了，這被稱為Race Condition（競爭條件）。問題的關鍵在於：程式碼中的 count++ 和 count-- 並非單一的原子操作。在實際的 CPU 執行中，一個簡單的加法或減法指令，往往會被拆解成多個步驟。

以 count++ 為例，它可能被翻譯成以下三個步驟：

• register1 = count：將 count 的值從記憶體載入到一個 CPU 暫存器 register1。
• register1 = register1 + 1：在暫存器中將值加一。
• count = register1：將加一後的值寫回記憶體中的 count 變數。
  count-- 的過程也是類似的：
• register2 = count：將 count 的值從記憶體載入到另一個 CPU 暫存器 register2。
• register2 = register2 - 1：在暫存器中將值減一。
• count = register2：將減一後的值寫回記憶體中的 count 變數。

假設目前緩衝區中有 5 個物品，也就是 count = 5。此時 Producer 正在執行 count++，而 Consumer 正在執行 count--。

• T0：producer: register1 = count → 5
• T1：producer: register1 = register1 + 1 → 6
• T2：consumer: register2 = count → 5
• T3：consumer: register2 = register2 - 1 → 4
• T4：producer: count = register1 → count = 6
• T5：consumer: count = register2 → count = 4 ❌ 覆蓋前面的結果

競爭狀況(Race Condition)

競爭狀況（Race Condition）是並發程式設計中一個最常見、也最難以捉摸的錯誤來源。當兩個或更多的thread或process同時存取並試圖修改相同的共享資料時，就會出現Race Condition。在這種情況下，最終的結果變得不可預測（unpredictable）且非決定性（nondeterministic）。這意味著程式碼每次執行的結果都可能不同，取決於這些操作在時間上的交錯順序。

為什麼會發生競爭狀況？

競爭狀況的發生並非偶然，它源於以下幾個關鍵因素：
第一，缺乏同步機制（Lack of Synchronization）：這是問題的根本原因。如果沒有任何保護措施，多個執行緒或行程可以同時進入操作共享資料的程式碼區塊（我們稱之為臨界區 Critical Section）。

第二，非原子操作（Non-Atomic Operations）：原子操作（Atomic Operation）指的是一個不可被中斷的操作。它要麼完全執行，要麼完全不執行，沒有中間狀態。然而count++ 這樣看似簡單的程式碼，在底層的機器指令中卻是由多個步驟組成的。

• 將 count 的值從記憶體載入到 CPU 暫存器。
• 在暫存器中將值加一。
• 將新值寫回記憶體。

這三個步驟中的任何一個，都可能在執行的過程中被作業系統中斷，並將 CPU 資源分配給另一個執行緒。這就為錯誤的發生創造了機會。

第三，執行順序不固定（Non-Deterministic Execution Order：在一個並發執行的系統中，作業系統的排程器會動態地決定哪個執行緒在何時獲得 CPU 的執行權。

如何解決競爭狀況？

為了避免競爭狀況，我們必須引入同步機制，核心思想是互斥（Mutual Exclusion），即在任何給定時間，只允許一個執行緒進入操作共享資料的臨界區。常用的解決方案包括：互斥鎖（Mutex Lock）、Semaphore與Monitor。

這些機制就像是為臨界區設置的「單行道」或「門禁」，確保每次只有一個執行緒可以通過，從根本上杜絕了競爭狀況的發生。

臨界區問題（The Critical-Section Problem）

Critical-Section指的是一段會讀取或修改共享資料（shared data）的程式碼區塊。由於這段程式碼操作的資料是共享的，因此在任何給定的時間點，只能有一個process或thread能夠在臨界區內執行。這就是我們設計同步機制的根本目標。

而解決臨界區問題的目的是為了：

1. 確保資料一致性（Data Consistency）：防止多個執行緒同時修改資料，導致資料混亂或錯誤。
2. 避免競爭狀況（Race Condition）：透過嚴格的單一進入原則，從根本上杜絕因執行順序不確定而引發的錯誤。

每個參與共享資料操作的行程，其程式碼結構都可以分為四個部分：

1. 進入區段（Entry Section）：這是程式碼的「門口」。一個行程若想進入臨界區，必須先在這裡嘗試取得資源，例如鎖（lock）。如果資源已被其他行程持有，它就必須等待。
2. 臨界區（Critical Section）：這是核心區域，行程在這裡執行讀取或修改共享資料的任務。這個區域必須受到嚴格的同步保護。
3. 退出區段（Exit Section）：當行程完成在臨界區的任務後，會在這裡釋放資源（例如解鎖），允許其他正在等待的行程進入臨界區。
4. 剩餘區段（Remainder Section）：行程在這裡執行其他與共享資料無關的任務，例如計算、列印訊息、等待使用者輸入等。這部分程式碼不需要同步保護。

解決臨界區問題的三大同步條件

在談同步之前，要先了解Critical Section三大同步條件：
第一，互斥（Mutual Exclusion）：如果有一個行程正在其臨界區內執行，那麼其他任何行程都不能進入它們的臨界區。這個條件從根本上防止了競爭狀況的發生。它保證了在任何時刻，都只有一個行程能夠操作共享資料，從而確保了資料的完整性和一致性。

第二，進度（Progress）：如果沒有任何行程在其臨界區內執行，且有一些行程想要進入其臨界區，那麼只有這些想要進入的行程可以參與選擇，並在有限時間內選出一個行程進入。選擇的過程不能無限期地拖延。它防止了死鎖（deadlock）或無限等待的情況。如果沒有人使用資源，想要使用的人就不能被無限期地阻擋在門外。

第三，有限等待（Bounded Waiting）：對於一個想要進入臨界區的行程，它必須保證，從它發出請求到它實際被允許進入臨界區的這段時間內，其他行程進入臨界區的次數是有限的。它確保了公平性。每個行程都不會被無限期地「餓著」，永遠得不到進入臨界區的機會。例如，如果有一個行程已經等待很久，它不應該被新來的行程不斷地插隊。

總結來說，一個成功的同步機制必須同時滿足這三個條件。互斥確保了正確性，而進度與有限等待則確保了系統的效率與公平性。在後續的討論中，我們將會看到各種同步工具（如鎖、號誌）是如何設計來滿足這三大條件的。