Enter your search text in the box above

Select a result to preview

併發資料結構設計指南 (Concurrent Design Guidelines)

#cpp-concurrency #concept #lock-based-ds

Overview Table

概念 重點
執行緒安全 (thread-safe) 多執行緒併發存取下無資料遺失/損毀、不變量維持原樣、無競爭條件
序列化 (serialization) 互斥鎖迫使執行緒輪流存取資料;是安全的代價,也是併發的敵人
設計面向一:確保安全 不變量、介面競爭、異常安全、死結——四大檢查點
設計面向二:真正併發 鎖外操作、分區保護、保護級別、結構微調——四個提問
核心指導思想 讓序列化存取最小化,讓真實併發最大化

執行緒安全的定義

一個資料結構若在多執行緒併發存取(執行相同或不同操作)之下,仍能滿足以下條件,就稱為「執行緒安全」的資料結構:

「安全」有程度之分

一個結構可能只在「多執行緒執行不同操作」時安全,而多執行緒併發執行同樣操作時出問題;也可能某些操作需要單執行緒獨占存取。宣稱執行緒安全時,必須說明「在什麼樣的併發使用方式下」安全。

序列化 (Serialization) 與真正併發

互斥鎖 (mutex) 透過顯式阻止併發存取來保護資料——同一時間只有一個執行緒能取得鎖。執行緒因此輪流存取資料,這種串行存取就是序列化 (serialization)。

單一互斥鎖(序列化)                 細粒度設計(真併發)
T1 ─[lock]──工作──[unlock]─→        T1 ─[lock A]──工作──[unlock A]─→
T2 ──────等待───────[lock]──→       T2 ─[lock B]──工作──[unlock B]─→
        (T2 閒置浪費)                       (T1、T2 同時進行)

設計面向一:確保存取安全(四大檢查點)

延續第3章的指導方針,設計時逐條檢查:

檢查點 說明
不變量 確保沒有執行緒能看到「不變量被破壞」時的中間狀態
介面競爭 小心介面間固有的競爭條件——提供完整操作的函式,而非分離的操作步驟(如 empty()+top()+pop() 應合併)
異常安全 注意操作拋出異常時,不變量是否仍維持原樣
死結 將死結 (deadlock) 機率降到最低:限制鎖的範圍、避免巢狀鎖

還要考慮使用上的限制:當一個執行緒透過某函式存取資料結構時,其他執行緒還能安全呼叫哪些函式?

建構與解構的特殊性

建構函式與解構函式必然需要獨占存取——使用者必須保證:物件完成建構前、開始解構後,不得有其他執行緒存取。此外若支援 swap()、拷貝建構、賦值等操作,設計者也要保證它們在併發下安全(或明確要求獨占存取)。

設計面向二:提升併發度(四個提問)

確保安全之後,思考「如何提供真正併發的機會」,自問:

  1. 鎖範圍內的操作,是否有部分可以移到鎖外執行?(如記憶體配置)
  2. 資料結構的不同區域,能否用不同互斥鎖保護?
  3. 所有操作都需要同級別的保護嗎?(讀 vs 寫可否區別對待)
  4. 能否對資料結構做簡單修改,增加併發存取的機率?(如加入 dummy node)
一個常見模式

「允許多執行緒併發讀取、但修改必須獨占」的結構很常見——正對應 std::shared_mutex 的讀寫鎖語意。同樣地,「支援多執行緒的不同操作併發、相同操作序列化」也是常見設計結果。

基於鎖的結構:總體原則

Exam/Test Patterns

情境/關鍵字 答案
「什麼是執行緒安全的資料結構?」 多執行緒併發存取下無資料遺失/損毀、不變量維持、無競爭條件
「mutex 保護了資料,為何效能差?」 互斥鎖造成序列化 (serialization)——執行緒輪流存取,阻止真正併發
「併發資料結構設計的兩個面向?」 一是確保存取安全,二是提供真正併發的機會
「介面設計如何避免競爭?」 提供完整操作的單一函式(如 pop 同時檢查空+取值+刪除),而非分離步驟
「如何降低死結機率?」 限制鎖的範圍、避免巢狀鎖;需多把鎖時固定上鎖順序
「建構/解構函式是執行緒安全的嗎?」 不是——需要獨占存取,由使用者保證建構前/解構後無人存取
「讀多寫少的保護策略?」 用 std::shared_mutex:多讀者或單一寫者