3.1 Dijkstra（1965）的臨界區問題與信號（semaphore）#

併發問題的誕生#

當兩條執行緒共享資料，最平凡的程式也會出錯。考慮最簡單的計數器遞增：

counter++;   // 「一行」程式碼 ≠ 一條機器指令

它在機器層是三步：載入（load counter 到暫存器）→ 加一 → 存回（store）。若兩條執行緒在各執行一次 counter++，且交錯順序為「A載入、B載入、A加一存回、B加一存回」，最終 counter 只加了一次而非兩次——更新遺失（lost update）。

這不是抽象的學術問題：1960 年代初的分時系統與多處理機系統（如 Burroughs B5000，1961，硬體原生支援多處理器）一出現，共享佇列、共享記憶體表格的競爭狀況（race condition）就成為系統當機的主因。「程式結果取決於執行緒交錯順序」這種不確定性 bug 最陰險之處在於：它往往在測試時不發作，上線後才爆發。

臨界區問題（Critical Section Problem）#

Edsger W. Dijkstra 在 1965 年發表的論文〈Cooperating Sequential Processes〉（荷蘭文原版 1965，英譯 1968）正式提出了互斥（mutual exclusion）問題：多個協作行程都需要執行一段臨界區（critical section）——存取共享資源的程式碼，任何時刻必須至多一個行程在臨界區內。正確的協議需滿足三個條件：

互斥（Mutual Exclusion）：不同行程的臨界區不重疊。
進展（Progress）：臨界區空著時，想進的行程不能被無關行程無限拖延。
有限等待（Bounded Waiting）：想進的行程等待次數有上界，不會飢餓。

Dijkstra 並給出歷史上第一個純軟體的解（後經 Knuth 等人修正為 \(n\) 行程版本），而 1960 年由荷蘭數學家 T. J. Dekker 提出的 Dekker 演算法是兩行程互斥的第一個正確軟體解。Peterson（1981）的演算法更簡潔，成為教科書標準：

// Peterson 演算法：兩執行緒，i 為自己，j 為對方
int turn = 0;                    // 輪到誰
bool flag[2] = {false, false};   // 我想進的意願

void lock(int i) {
    flag[i] = true;
    turn = j;                    // 謙讓：把優先權讓給對方
    while (flag[j] && turn == j) // 對方想進且輪到對方 → 等
        ;                        // 忙碌等待
    // 進入臨界區
}
void unlock(int i) {
    flag[i] = false;
}

Peterson 演算法的精妙在「謙讓行」turn = j：即使兩人同時表示意願，turn 只會留下最後一個寫入者，保證至少一人能進。注意：這個軟體解假設順序一致性（sequential consistency）的記憶體模型——現代亂序 CPU 與編譯器最佳化都會破壞它，必須加上記憶體屏障（memory fence）才真正正確。這是「理論演算法在真實硬體上失效」的經典教訓，也直接連到 3.2 節的硬體支援。

信號（Semaphore）：Dijkstra 的抽象#

同一篇 1965 年的工作中，Dijkstra 提出了作業系統史上最重要的同步抽象之一：信號（semaphore）。靈感來自鐵路的旗號系統——一個由核心維護的原子計數器 \(S\) ，配兩個不可分割的操作：

P(S)（荷蘭語 Proberen，測試；又稱 wait/down）： \(S\) 減 1；若結果為負則呼叫者阻塞。
V(S)（Verhogen，增加；又稱 signal/up）： \(S\) 加 1；若有等待者則喚醒一個。

typedef struct {
    int value;
    struct queue *waiters;   // 阻塞中的行程佇列
} semaphore;

void P(semaphore *s) {       // 核心內實作，須原子
    disable_interrupts();    // 單處理機：關中斷即原子
    s->value--;
    if (s->value < 0) {
        block(current, s->waiters);  // 睡覺，不燒 CPU
    }
    enable_interrupts();
}
void V(semaphore *s) {
    disable_interrupts();
    s->value++;
    if (s->value <= 0) {
        wakeup(dequeue(s->waiters)); // 叫醒一個
    }
    enable_interrupts();
}

與 Peterson 式的忙碌等待（busy waiting / spinlock）相比，semaphore 的關鍵優勢是等待者睡覺而非空轉——在單處理機上空轉尤其荒謬：持有鎖的行程需要 CPU 才能解鎖，等待者卻在搶佔 CPU 燒圈圈。多處理機上短臨界區用自旋仍有利（免了兩次 context switch），這個「自旋多久才放棄去睡」的取捨催生了兩階段鎖（adaptive mutex，Solaris）：先自旋一下，不行再睡。

二元信號與計數信號#

計數信號：初始值 \(N\) ，代表 \(N\) 份資源， \(N\) 個使用者可同時進入。典型：限制資料庫連線數、bounded buffer 的槽位計數。
二元信號： \(S \in \{0,1\}\) ，等價於 mutex。Dijkstra 的原始設計甚至不保證歸還者必須是取得者（V 可以由任何執行緒呼叫），這使 semaphore 可以表達「事件通知」；而 mutex 則規範「誰鎖誰解」，語意更強、更不容易寫錯。

三大經典同步問題#

Dijkstra 之後，教科書上沉澱出三個試金石問題，它們並非玩具：每個都是真實系統模式的縮影。

1. 生產者—消費者（有界緩衝）#

semaphore empty = N;   // 空槽數
semaphore full  = 0;   // 滿槽數
semaphore mutex = 1;   // 保護緩衝區本身

void *producer(void *_) {
    while (1) {
        item = produce();
        P(&empty);          // 沒空槽就等
        P(&mutex);
        insert(item);
        V(&mutex);
        V(&full);           // 通知消費者
    }
}
void *consumer(void *_) {
    while (1) {
        P(&full);
        P(&mutex);
        item = remove();
        V(&mutex);
        V(&empty);
        consume(item);
    }
}

細節警示：兩個 P 的順序不能顛倒。若先 P(&mutex) 再 P(&empty)，緩衝區滿時生產者會抱著鎖睡覺，消費者永遠拿不到鎖——死結。這個陷阱是第 3.3 節「持有並等待」條件的活教材。

2. 讀者—寫者問題（Courtois、Heymans、Parnas，1971）#

資料庫式的場景：讀者可並行、寫者須獨佔。核心是「第一個讀者鎖門、最後一個讀者開門」的計數技巧；其變體（讀者優先/寫者優先）展示優先權設計如何造成飢餓。檔案系統、RCU（Linux 核心的 read-copy-update，讀者零開銷的極致演化）都是它的後代。

3. 理髮師問題（Dijkstra，1965）#

\(N\) 個座位、客人、理髮師的協調，本質是「多生產者—單消費者＋容量限制」，訓練 semaphore 的組合能力。

monitor：更高階的抽象#

semaphore 很強，但容易用錯（P/V 配對靠紀律）。1972 年 Per Brinch Hansen 在 Concurent Pascal 中、1974 年 Tony Hoare 在論文中提出監視器（monitor）：把共享資料與其所有操作封裝成一個物件，語言層保證同一時刻至多一個行程在物件內執行，另配條件變數（condition variable）的 wait/signal 表達「等某條件成立」。

這是「把正確性從程式師紀律升級為語言保證」的轉折，直接影響：Java 的 synchronized/wait/notify（每個物件即一個 monitor）、POSIX 的 pthread_cond_t，以及整個「以物件為同步單位」的 OOP 併發文化。Hoare 論文中條件變數使用的 Mesa vs. Hoare 語意（被喚醒後條件是否必然成立）至今仍是面試與實務的重點：Mesa 語意（Java、pthreads）要求喚醒後重查條件（while (!cond) wait();），因為喚醒只代表「可能有戲」。

小結#

Dijkstra 1965 年的工作把「多行程合作」從工匠技藝變成可分析的科學：臨界區三條件給了正確性的定義，semaphore 給了第一個通用機制，三大經典問題給了檢驗的試金石。但 semaphore 的原子性終究需要硬體兜底（單機關中斷只對單處理機有效），多處理機時代需要 CPU 指令級的原子操作——這是下一節的主題。