並行程式設計（Concurrency with pthreads）

多核心時代，讓程式「同時做多件事」是效能的必經之路——但也打開了一整類 全新的 bug：race condition、死鎖、資料撕裂。這些 bug 不確定性重現、 難以除錯，因此並行程式設計的重點不是「會開執行緒」，而是正確共享資料。 本單元用 POSIX pthreads（macOS/Linux 通用）從零建立：執行緒生命週期、 互斥鎖、條件變數與生產者-消費者模式。K&R 成書於單核年代，本單元為現代補充。

學習目標

• 分清 process 與 thread：共享什麼、隔離什麼
• 會用 pthread_create/pthread_join 建立與回收執行緒，傳參數、收回傳值
• 能親手重現 race condition，並解釋它為什麼發生
• 會用 pthread_mutex_t 保護共享資料（critical section）
• 理解條件變數 pthread_cond_t 的等待/喚醒語意，實作生產者-消費者
• 認識死鎖的四要件與避免策略
• 知道 C11 threads.h/stdatomic.h 的定位（macOS 無 threads.h，用 pthreads）

對照章節 / 參考來源

• K&R 無此主題（成書早於 POSIX threads），本單元為現代補充
• POSIX.1-2017 pthreads：man pthread_create、man pthread_mutex_lock
• 《Programming with POSIX Threads》(David Butenhof)
• C11 標準 §7.26（threads.h）、§7.17（stdatomic.h）

觀念講解

1. Process vs Thread

Process A                     Process B
┌─────────────────────┐      ┌─────────────┐
│ 位址空間（獨立）      │      │ 位址空間     │
│  code / heap / data │      │  ...        │
│ ┌───────┐ ┌───────┐ │      │ ┌───────┐   │
│ │thread1│ │thread2│ │      │ │thread1│   │
│ │ stack │ │ stack │ │      │ │ stack │   │
│ │ regs  │ │ regs  │ │      │ └───────┘   │
│ └───────┘ └───────┘ │      └─────────────┘
└─────────────────────┘

	Process	Thread
位址空間	各自獨立	同一個（共享 heap/全域變數）
建立成本	高（fork 整個空間）	低（只要新堆疊＋暫存器）
通訊	pipe/socket/共享記憶體	直接讀寫共享變數（危險也在此）
一個掛掉	其他不受影響	整個 process 一起掛

執行緒共享 heap 與全域變數、各自擁有堆疊——所以區域變數天然安全， 共享資料才需要同步。

2. 建立與回收

#include <pthread.h>

void *worker(void *arg)           /* 執行緒進入點：void* 進、void* 出 */
{
    struct task *t = arg;         /* 轉回真正的型別 */
    /* ... */
    return result;                /* 或 pthread_exit(result) */
}

pthread_t tid;
pthread_create(&tid, NULL, worker, &task);   /* 開跑 */
void *result;
pthread_join(tid, &result);                  /* 等它結束並收回傳值 */

編譯要加 -pthread。傳參數的鐵律：arg 指向的資料必須活得比執行緒久 ——傳迴圈變數的位址給多個執行緒是經典錯誤（大家看到同一個、且不斷變動的 i）。 正確做法：每個執行緒一個獨立的參數結構（陣列元素）。

3. Race condition：親眼看它出錯

counter++ 看似一步，機器層面是三步：讀取→加一→寫回。 兩個執行緒交錯執行時，彼此的更新會互相覆蓋：

thread A               thread B            counter
read 5                                        5
                       read 5                 5
add  -> 6                                     5
                       add  -> 6              5
write 6                                       6
                       write 6                6   ← 兩次 ++ 只加了 1！

範例程式讓 4 個執行緒各做 10 萬次 counter++，結果幾乎永遠少於 40 萬， 而且每次執行的錯誤量都不一樣——這就是 race 難抓的原因：它取決於時序。

4. Mutex：互斥鎖

把「讀-改-寫」包進臨界區（critical section），一次只讓一個執行緒進入：

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_lock(&lock);
counter++;                        /* 臨界區：同一時間只有一人 */
pthread_mutex_unlock(&lock);

原則： - 鎖保護的是「資料」不是「程式碼」：想清楚哪些資料是共享的、由哪把鎖負責。 - 臨界區越短越好；絕不在臨界區內做 I/O 或睡眠。 - 計數器這種單一變數，stdatomic.h 的原子操作更輕量（範例一併示範）。

5. 條件變數與生產者-消費者

「等到某條件成立才繼續」不能用忙等（busy-wait 燒 CPU）。 條件變數讓執行緒睡著等，由改變條件的人喚醒：

/* 消費者：等佇列非空 */
pthread_mutex_lock(&m);
while (queue_empty())             /* 必須用 while，不能用 if！ */
    pthread_cond_wait(&cv, &m);   /* 自動放鎖睡覺；被喚醒時自動重新拿鎖 */
item = dequeue();
pthread_mutex_unlock(&m);

/* 生產者：放資料並喚醒 */
pthread_mutex_lock(&m);
enqueue(item);
pthread_cond_signal(&cv);         /* 叫醒一個等待者 */
pthread_mutex_unlock(&m);

用 while 重驗條件的原因：(1) 可能有「假喚醒」（spurious wakeup）； (2) 從被喚醒到重新拿到鎖之間，別的執行緒可能已把資料搶走。 生產者-消費者（bounded buffer）是條件變數的教科書應用： 緩衝滿時生產者等 not_full，空時消費者等 not_empty。

6. 死鎖（Deadlock）

兩個執行緒互相等待對方手上的鎖，全部卡死：

thread 1: lock(A) ──> 等 B
thread 2: lock(B) ──> 等 A      ← 誰也動不了

四個必要條件：互斥、持有並等待、不可搶奪、循環等待。 最實用的預防法：全域鎖序——所有執行緒都按同一順序拿鎖 （例如永遠先 A 後 B），循環等待就不可能形成。 其他工具：pthread_mutex_trylock（拿不到就放棄重來）、一次拿齊所有鎖。

7. C11 threads.h 與 stdatomic.h

C11 定義了可攜的 threads.h（thrd_create/mtx_lock/cnd_wait）， API 與 pthreads 幾乎一一對應，但 macOS 至今沒有提供這個標頭， Linux 也要 glibc 2.28+。因此實務（與本教材）仍以 pthreads 為準。 stdatomic.h 則到處可用：無鎖計數器、旗標、以及記憶體序 （memory ordering）控制，範例中用 atomic_int 對照 mutex 版本。

範例程式

（本單元所有程式編譯需加 -pthread）

檔案	內容	編譯 / 執行
01_threads_basic.c	create/join、傳參數結構、收回傳值、多執行緒平行分段加總	cc -std=c11 -Wall -Wextra -pthread -o out 01_threads_basic.c && ./out
02_race_and_mutex.c	race condition 實錄（無鎖 vs mutex vs atomic 三版對照與計時）	cc -std=c11 -Wall -Wextra -pthread -o out 02_race_and_mutex.c && ./out
03_producer_consumer.c	條件變數：兩生產者＋兩消費者共享有界緩衝區；含死鎖說明	cc -std=c11 -Wall -Wextra -pthread -o out 03_producer_consumer.c && ./out

常見錯誤與陷阱

1. 把迴圈變數位址傳給執行緒：pthread_create(..., &i) 之後 i 繼續變動， 每個執行緒看到的值不可預測。用參數陣列，一人一格。
2. 忘記 join（或 detach）：main 先 return，整個 process 結束， 執行緒做到一半被砍；join 也負責回收資源，不 join 會累積 zombie thread。
3. cond_wait 用 if 不用 while：假喚醒或條件被別人搶先消費後， 直接往下執行就 GG。醒來必須重新驗證條件。
4. 回傳區域變數的位址：return &local; 執行緒結束堆疊即回收， join 拿到懸空指標。回傳 malloc 的記憶體或寫進參數結構。
5. 鎖的粒度失衡：一把大鎖鎖住全部＝退化成單執行緒； 鎖太細＝拿多把鎖引發死鎖風險。先求正確（粗鎖），量測後再細化。

練習題

1. 【易】開 8 個執行緒各印自己的編號與 pthread_self()，觀察輸出交錯。
2. 【易】把 01_threads_basic.c 的分段加總改成「每執行緒回傳部分和的 malloc 指標」，main 收集後加總並釋放。
3. 【中】用 pthread_mutex_trylock 寫「搶鎖統計」：4 個執行緒搶一把鎖， 統計每人成功/失敗次數。
4. 【中】為 03_producer_consumer.c 加上「毒藥丸」（poison pill）關閉協定： 生產者結束時放入 N 個特殊值，讓每個消費者收到後優雅退出。
5. 【難】親手做出一個死鎖（兩把鎖、相反順序），用 lldb attach 觀察卡住的 兩條執行緒；再用「固定鎖序」修好它。
6. 【難】用 stdatomic.h 實作單生產者單消費者（SPSC）無鎖環形緩衝區， 與 mutex 版本比較吞吐量。

延伸閱讀

• 《Programming with POSIX Threads》(Butenhof)——pthreads 聖經
• 《The Little Book of Semaphores》(Downey，免費 PDF)——同步問題集
• C11 記憶體模型與 stdatomic.h：cppreference "Atomic operations"
• ThreadSanitizer（-fsanitize=thread）：自動抓 race 的工具
• Herb Sutter, "The Free Lunch Is Over"（為什麼必須學並行）