C++ 併發速查表 (Quick Reference)
用法
每節標題附 → 筆記連結,查到條目後點入概念筆記看完整推理;文末「必背公式與模式」集中所有公式。
併發基礎(第1章)
併發概念 → 何謂併發
| 概念 | 重點 |
|---|---|
| 併發的定義 | 兩個以上獨立活動同時發生;電腦中 = 單一系統同時執行多個獨立任務 |
| 任務切換 vs 硬體併發 | 單核任務切換 = 併發假象;多核硬體併發 = 真正平行;上限 = 硬體執行緒數 |
| Context switch 成本 | 保存 CPU 狀態/指令指標 → 選擇並載入新任務 → 快取重填延遲 |
| 多行程 vs 多執行緒 | 行程:IPC 複雜慢 + OS 保護;執行緒:共享位址空間 + 低開銷 + 需自保資料一致;C++ 標準只支援多執行緒 |
為什麼與何時使用 → 為什麼使用併發
| 概念 | 重點 |
|---|---|
| 兩大理由 | 分離關注點 (SoC) 與效能;SoC 的執行緒數依概念設計而非核心數 |
| 任務平行 vs 資料平行 | 拆單一任務降低總時間 vs 不同資料塊做相同操作 |
| 不用併發的成本 | 啟動開銷、32-bit + 1MB 堆疊約 4096 執行緒耗盡位址空間、context switch、複雜度 |
C++ 支援演進 → C++ 併發支援與首個程式
| 概念 | 重點 |
|---|---|
| 演進 | C++98 無執行緒 → 平台 API + Boost → C++11 記憶體模型 + 執行緒庫 → C++14 新互斥鎖 → C++17 平行演算法 |
| 抽象懲罰 | 標準庫目標極低開銷,高階工具 ≈ 手寫;瓶頸常是設計(鎖爭用)而非庫 |
native_handle() |
以平台 API 直接操作底層實作(平台相依) |
執行緒管理(第2章)
啟動與等待 → 啟動與等待執行緒
| 概念 | 重點 |
|---|---|
| 啟動 | 建構 std::thread 即啟動;可傳函式/函式物件(被複製)/lambda |
| join vs detach | 解構前必須二選一,否則 std::terminate();join 只能一次,以 joinable() 檢查 |
| RAII thread_guard | 解構中 if (t.joinable()) t.join();,拷貝 =delete,例外路徑也保證匯入 |
| 守護執行緒 | detach() 後不可再 join,適合 fire-and-forget |
傳參與所有權 → 傳遞參數與轉移所有權
| 概念 | 重點 |
|---|---|
| 傳參規則 | 參數一律拷貝進執行緒再以右值傳遞;傳參考用 std::ref(data);成員函式 f, &obj, args... |
| 只可移動型別 | std::unique_ptr 等命名變數需 std::move();臨時物件自動隱式移動 |
| thread 所有權 | 可移動不可拷貝;移動賦值給已關聯執行緒的物件 → std::terminate() |
| scoped_thread / jthread | 建構期接管所有權並檢查 joinable,解構無條件 join;C++20 = std::jthread |
數量與標識 → 執行緒數量與標識
| 概念 | 重點 |
|---|---|
| 執行緒數公式 | num_threads = min(hardware_concurrency()(0 則取 2), (length+min_per_thread-1)/min_per_thread) |
| parallel_accumulate | 只啟動 num_threads−1 條(主執行緒處理最終塊);結果以 std::ref(results[i]) 傳出 |
std::thread::id |
get_id() / this_thread::get_id();支援全序比較與 std::hash,可當容器鍵 |
共享資料(第3章)
競爭條件與互斥鎖 → 競爭條件與互斥鎖
| 概念 | 重點 |
|---|---|
| 資料競爭 = UB | 未同步併發修改同一物件即 data race → 未定義行為;良性競爭(不變量未破壞)可接受 |
| RAII 上鎖 | std::lock_guard<std::mutex> 建構鎖/解構解;C++17 可 CTAD 或 std::scoped_lock |
| 引用外洩準則 | 切勿將受保護資料的指標/引用傳出鎖作用域 |
| threadsafe_stack 介面 | 合併檢查+取值+移除於同一鎖內:pop(T&) 與 shared_ptr<T> pop() |
死結與鎖管理 → 死結與鎖管理
| 概念 | 重點 |
|---|---|
| 同時鎖多個 mutex | std::lock(m1,m2) 全有或全無 + adopt_lock;C++17 一行 std::scoped_lock guard(m1,m2) |
| 避免死結四指導 | 避免嵌套鎖 / 持鎖不呼叫外部程式碼 / 固定順序上鎖 / 鎖層級(thread_local 記錄層級) |
| unique_lock 三大彈性 | defer_lock 延遲上鎖、手動 lock/unlock、可移動轉移所有權 |
| 鎖粒度 | 持鎖時間最短化;耗時操作(檔案 I/O)絕不持鎖做 |
其他保護方式 → 其他資料保護方式
| 概念 | 重點 |
|---|---|
| 一次性初始化 | std::call_once(once_flag, f) 保證恰好完整執行一次 |
| 單例最簡解 | C++11 起函式內 static 區域變數初始化保證執行緒安全 |
| 讀寫鎖 | 讀者 std::shared_lock<std::shared_mutex>;寫者 lock_guard/unique_lock;C++17 才有 shared_mutex |
同步操作(第4章)
條件變數 → 條件變數與執行緒安全佇列
| 概念 | 重點 |
|---|---|
| 等待 | cv.wait(unique_lock, predicate);wait 期間解鎖、喚醒後重新上鎖再查條件 |
| notify_one vs notify_all | 一份資料一人處理用 notify_one;全體回應用 notify_all |
| threadsafe_queue | front+pop 合併為 try_pop / wait_and_pop;互斥鎖宣告 mutable |
Future 與非同步任務 → Future 與非同步任務
| 概念 | 重點 |
|---|---|
| 三種建立方式 | std::async / packaged_task(打包調度)/ promise(顯式 set_value/set_exception) |
| 啟動策略 | launch::async 必開新執行緒;launch::deferred 延遲到 get/wait;預設由實作選 |
| 例外傳遞 | 任務拋例外存入 future、get() 重拋;promise 未設值解構 → broken_promise |
| shared_future | future 只移動、get 一次;多執行緒各持 shared_future 副本才安全 |
限時等待 → 限時等待
| 概念 | 重點 |
|---|---|
| 三種時鐘 | system_clock(可調 → 不穩)/ steady_clock(超時用)/ high_resolution_clock |
| duration / time_point | duration<Rep, ratio>;duration_cast 截斷不捨入;_for 配 duration、_until 配 time_point |
| 超時函式回傳 | future wait 回傳 ready / timeout / deferred |
FP 與訊息傳遞 → 函數式與訊息傳遞風格
| 概念 | 重點 |
|---|---|
| FP 平行快排 | lower 半部 std::async、higher 本執行緒遞迴;partition 仍串行 |
| CSP/Actor | 無共享資料、執行緒 = 狀態機、訊息佇列通訊;不匹配訊息丟棄 |
持續性與同步原語 → 持續性、Latch 與 Barrier
| 概念 | 重點 |
|---|---|
.then() |
就緒自動接續;參數是就緒 future 本身;原 future 失效 |
| when_all / when_any | 全部/任一就緒觸發;搭 .then 免輪詢 |
| latch vs barrier | latch 一次性 count_down、不限誰遞減;barrier 可重用、每執行緒每週期一次 |
| flex_barrier | 完成函式由單一執行緒執行(串行區);回傳值可改下一週期人數 |
記憶體模型與原子操作(第5章)
基礎 → 記憶體模型基礎
| 概念 | 重點 |
|---|---|
| 記憶體位置 | 每物件至少一個位置;相鄰位元欄位共享同一位置;寬度 0 未命名欄位可切開 |
| 資料競爭 | 同一位置無序併發存取且至少一寫 → UB |
| 修改順序 | 每個物件一條全體執行緒認可的寫入序列;讀值不可倒退 |
原子型別 → 原子型別與操作
| 概念 | 重點 |
|---|---|
| lock-free 查詢 | is_lock_free() / C++17 is_always_lock_free;唯一保證無鎖:std::atomic_flag |
| CAS | weak 有偽失敗須配迴圈;strong 內含迴圈;失敗序禁 release/acq_rel |
| 回傳值規則 | fetch_xxx()/exchange() 回舊值;複合賦值運算子回新值且固定 seq_cst |
atomic<UDT> 條件 |
trivially copyable(無虛函式/虛基類);比較用 memcmp(padding/浮點陷阱) |
同步關係 → 同步發生與先行發生
| 概念 | 重點 |
|---|---|
| 關係鏈 | sequenced-before(執行緒內)+ synchronizes-with(原子間)→ inter-thread happens-before,可傳遞 |
| 旗標發布模式 | 寫資料 → release 旗標 ↔ acquire 讀旗標 → 讀資料 |
記憶體順序 → 記憶體順序選項
| 概念 | 重點 |
|---|---|
| 三種模型 | seq_cst = 全局總順序(預設);acquire-release = 成對同步;relaxed = 僅單一變數修改順序 |
| acquire-release 配對 | release store 與「讀到其值」的 acquire load 同步;RMW 用 acq_rel 才雙向 |
| consume | 只同步資料依賴鏈;C++17 不建議 → 一律改用 acquire |
| 架構成本 | x86/x86-64:acq-rel 幾乎免費、seq_cst 僅 store 有額外開銷 |
釋放序列與柵欄 → 釋放序列與柵欄
| 概念 | 重點 |
|---|---|
| 釋放序列 | store(release) 後同變數 RMW 鏈;acquire 讀鏈上任一值即與最初 store 同步 |
| 柵欄配方 | atomic_thread_fence(release) 置兩 store 之間 + fence(acquire) 置 load 之後 |
| 鎖語義 | lock()=acquire、unlock()=release;thread join、mutex、promise/future 皆建立同步;CV 本身不提供 |
基於鎖的資料結構(第6章)
設計指南 → 併發設計指南
| 概念 | 重點 |
|---|---|
| 執行緒安全三要件 | 無資料遺失/損毀、不變量維持、無競爭條件 |
| 序列化 vs 真併發 | 鎖迫使輪流存取;目標 = 序列化最小化、真併發最大化 |
| 四大檢查點 | 不變量、介面競爭、異常安全、死結 |
棧與佇列 → 執行緒安全棧與佇列
| 概念 | 重點 |
|---|---|
| pop 合併介面 | 鎖內檢查空+取值+刪除一次完成;shared_ptr 或引用參數回傳 |
| notify_one 異常三解法 | notify_all / 異常時補 notify_one / 佇列改存 shared_ptr(推薦) |
| shared_ptr 紅利 | make_shared 移到 push() 上鎖之前,縮短持鎖時間 |
細粒度佇列 → 細粒度鎖佇列
| 概念 | 重點 |
|---|---|
| dummy node | 虛擬節點永遠在隊尾,push 只碰 tail、try_pop 只碰 head;判空 head.get() == tail |
| get_tail 位置 | 必須在 head_mutex 保護範圍內呼叫 |
| 雙鎖順序 | 固定先 head_mutex 後 tail_mutex,不會死結 |
查詢表與串列 → 查詢表與鏈結串列
| 概念 | 重點 |
|---|---|
| 雜湊表 | 每桶一把 std::shared_mutex,桶數預設 19(質數);get_bucket 無鎖 |
| hand-over-hand | 先鎖下一節點、再解鎖當前節點;順序固定無死結,但不能超車 |
| remove_if | 先解鎖 next_lk 再銷毀節點 — 銷毀仍上鎖的 mutex 是 UB |
無鎖資料結構(第7章)
概念 → 無鎖概念與取捨
| 概念 | 重點 |
|---|---|
| 非阻塞三層級 | obstruction-free ⊃ lock-free(至少一執行緒有進展)⊃ wait-free(有限步驟完成) |
| 自旋鎖 | 非阻塞但有鎖,不是 lock-free |
| 利弊 | 利:最大化併發、無死結;弊:活結、原子操作昂貴、須實測 |
無鎖棧 → 無鎖棧
| 概念 | 重點 |
|---|---|
| CAS push | while(!head.compare_exchange_weak(new_node->next,new_node)); 失敗自動更新期望值 |
| weak vs strong | 迴圈中用 weak;失敗代價高(重設 hazard pointer)才用 strong |
| 異常安全回傳 | node 內存 shared_ptr<T>,回傳不拋例外 |
記憶體回收 → 記憶體回收策略
| 概念 | 重點 |
|---|---|
| 三策略 | 待刪鏈 + threads_in_pop(低負載限定)/ hazard pointer(掃表)/ 引用計數(需 DWCAS) |
| hazard pointer 協定 | hp.store(old_head) 後重讀 head 驗證;刪前掃全表 |
| split count | 讀指標時 external +1;成功者 internal_count.fetch_add(external−2),總和 0 才刪 |
無鎖佇列與內存序 → 無鎖佇列與記憶體順序
| 概念 | 重點 |
|---|---|
| 放寬法則 | CAS 失敗分支一律 relaxed;push release ↔ 讀端 acquire;RMW 鏈構成釋放序列 |
| 歸零者補 acquire | fetch_sub 減到 0 者補 load(acquire) 再 delete |
| helping | next 原子化;CAS 失敗者代設 next 與 set_new_tail |
設計指導 → 無鎖設計指導建議
| 概念 | 重點 |
|---|---|
| 四條建議 | 先 seq_cst 再放寬;規劃回收方案;小心 ABA;識別忙等待用 helping |
| ABA 解法 | 指標附帶世代計數器,CAS 對「值+計數」整體操作 |
併發設計(第8章)
工作劃分 → 執行緒間劃分工作
| 概念 | 重點 |
|---|---|
| 三種劃分策略 | 塊狀(資料量已知)/ 遞迴(如快排)/ 按任務類型(管線) |
| 限量遞迴劃分 | hardware_concurrency() 定上限 + 執行緒安全堆疊派工;等待時自己取塊 |
| 管線 | 輸入長度未知/需穩定輸出節奏用;總時間較長但輸出平滑 |
性能因素 → 影響性能的因素
| 概念 | 重點 |
|---|---|
| 超額申請 | 就緒執行緒 > 硬體執行緒 → 切換開銷 |
| 快取乒乓 | 「讀-改-寫」使 cache line 所有權在處理器間反覆搬移 |
| 偽共享 | 不同變數同住一條 cache line;C++17 <new> 提供 destructive/constructive interference size |
資料結構設計 → 為性能設計資料結構
| 概念 | 重點 |
|---|---|
| 三大考量 | 爭用、偽共享、資料鄰近性 |
| 矩陣塊狀劃分 | 100×100 塊只讀 200,000 元素 vs 整行劃分 1,010,000 |
| 偽共享測試法 | 資料間塞大 padding,變快 ⇒ 偽共享存在 |
異常安全與擴展性 → 異常安全與可擴展性
| 概念 | 重點 |
|---|---|
| 異常安全三步 | packaged_task/future 轉移異常 → join_threads RAII → std::async 遞迴版天然安全 |
| Amdahl | P = 1/(fs + (1-fs)/N);上限 1/fs |
| 響應能力 | GUI 專用事件執行緒 + atomic<bool> 取消旗標 |
演算法案例 → 平行演算法案例
| 概念 | 重點 |
|---|---|
| parallel_for_each | std::async 遞迴對半版最簡潔且不超額申請 |
| parallel_find | atomic<bool> done flag 提前結束;promise 存首個結果;join 後查 flag 防死等 |
| parallel_partial_sum | 逐段傳播 O(N) vs barrier + 2 的冪距離 O(N log N)、log₂N 步 |
進階執行緒管理(第9章)
執行緒池 → 執行緒池
| 概念 | 重點 |
|---|---|
| worker 迴圈 | while(!done) 中 try_pop → task(),否則 yield() |
| function_wrapper | packaged_task 只可移動、std::function 要求可複製 → 自製只可移動的型別擦除包裝 |
| run_pending_task | 等待子任務時順手執行佇列任務,解「池內任務等池內任務」死結 |
工作竊取 → 工作竊取與佇列爭用
| 概念 | 重點 |
|---|---|
| thread_local 本地佇列 | 池內執行緒各有本地佇列;外部執行緒 submit 進全域佇列 |
| 兩端分工 | 擁有者前端 LIFO(快取親和);竊取者後端 FIFO(減少競爭) |
| 取任務順序 | 本地 → 全域 → 竊取他人,成本由低到高 |
中斷執行緒 → 中斷執行緒
| 概念 | 重點 |
|---|---|
| interruption_point() | 檢查 thread_local interrupt_flag,已設定 → 拋 thread_interrupted;協作式中斷 |
| 中斷 CV 等待 | condition_variable:wait_for(1ms) 輪詢;condition_variable_any:custom_lock 消除通知遺失 |
| 優雅退出 | 先全部 interrupt() 再逐一 join();C++20 對應 std::jthread + std::stop_token |
平行演算法(第10章)
執行策略 → 執行策略
| 概念 | 重點 |
|---|---|
| 三種策略 | seq 單執行緒不交錯;par 多執行緒可用 mutex/atomic;par_unseq 可交錯、禁止任何同步 |
| 異常行為 | 標準策略下異常逃逸一律 std::terminate(含 seq);無策略版本才傳播 |
| UB 是靜態屬性 | par 下的 data race 即使實作單執行緒執行仍是 UB |
使用平行演算法 → 使用平行演算法
| 概念 | 重點 |
|---|---|
| 迭代器要求 | 策略版一律要求前向迭代器 |
| accumulate vs reduce | accumulate 無平行版;std::reduce 需結合律+交換律 |
| 鎖粒度與策略 | 元素內部 mutex → 只能 par;容器級外鎖 → 可 par_unseq |
測試與除錯(第11章)
Bug 類型 → 併發 Bug 類型
| 概念 | 重點 |
|---|---|
| 兩大類 | 不必要的阻塞(死結/活結/I/O 阻塞)與競爭條件(資料競爭/破壞不變量/生命週期) |
| 死結 vs 活結 | 都卡住;死結 CPU 低(阻塞),活結 CPU 高(迴圈檢查) |
定位與測試 → 定位與測試併發 Bug
| 概念 | 重點 |
|---|---|
| 定位法 | 單執行緒化仍出錯 → 一般 bug;單核消失、多核出現 → 併發 bug |
| 三種測試技術 | 蠻力測試 / 組合模擬(窮舉排程)/ 專用庫檢測(鎖序記錄) |
| go 信號模式 | promise<void> go + shared_future ready;異常時先 go.set_value() 再重拋 |
附錄(A–C)
C++11 特性 → C++11 語言特性
| 概念 | 重點 |
|---|---|
| 只移動型別 | thread/unique_lock/future/promise/packaged_task;std::move 只是轉型 |
| 完美轉發 | template<typename... Args> void f(Args&&... args){ gforward<Args>(args)...; } |
| lambda 捕獲 | [=] 建立時複製、[&] 呼叫時取值、成員需 [this]、C++14 移動捕獲 |
| thread_local | 三類變數;程式退出時仍在執行的執行緒不呼叫解構子 |
庫對比 → 併發庫對比
| 概念 | 重點 |
|---|---|
| 四庫×四維 | 啟動=ch2、互斥=ch3、等待謂詞=ch4、原子=ch5;原子操作僅 C++11 與 Java 提供 |
| Java wait/notify | Object 的方法,必須在 synchronized 區塊內 |
ATM 範例 → ATM 訊息傳遞範例
| 概念 | 重點 |
|---|---|
| dispatch 鏈 | wait().handle<M>(f) 鏈尾解構時才等待;dynamic_cast 匹配,不符沿 prev 回溯 |
| 結束機制 | close_queue 訊息 → dispatch 擲例外 → run() catch;解構子 noexcept(false) |
| 狀態機模式 | 成員函式指標 state + 主迴圈 (this->*state)(); |
附錄D(API 參考)
依 學習地圖 non-core policy 不建筆記;逐條 API 請查原書 pp. 402–542。
必背公式與模式
| 公式/模式 | 內容 | 出處 |
|---|---|---|
| 執行緒數公式 | min(hardware_concurrency()(0→2), (length+min_per_thread-1)/min_per_thread) |
執行緒數量與標識 |
| Amdahl 定律 | P = 1/(fs + (1-fs)/N);N→∞ 上限 1/fs |
異常安全與可擴展性 |
| CAS 迴圈 | while(!head.compare_exchange_weak(expected, desired)); 失敗自動更新 expected |
無鎖棧 |
| CV 等待模板 | cv.wait(lk, []{ return ready; });(unique_lock + predicate) |
條件變數與執行緒安全佇列 |
| 旗標發布 | 寫資料 → flag.store(true, release) ↔ flag.load(acquire) → 讀資料 |
同步發生與先行發生 |
| 柵欄配對 | store 前 fence(release) ↔ load 後 fence(acquire) |
釋放序列與柵欄 |
| 多鎖獲取 | std::scoped_lock guard(m1, m2);(C++17)或 std::lock + adopt_lock |
死結與鎖管理 |
| split reference count | 讀時 external+1;成功者 internal += external−2;歸零才刪 |
記憶體回收策略 |
| 測試 go 信號 | 全員 set ready promise → wait shared_future go → 主執行緒 go.set_value() |
定位與測試併發 Bug |