執行緒安全查詢表與鏈結串列 (Lookup Table and Linked List)

Overview Table

執行緒安全查詢表:介面設計

查詢表(字典)把鍵值 (key) 映射到資料 (value),對應 std::map<>、std::unordered_map<> 等。與堆疊/佇列不同:幾乎每個操作都修改堆疊/佇列,而查詢表讀多寫少。

• 最大問題是迭代器:迭代器引用的元素被其他執行緒刪除時就出問題 → 第一次介面削減就是繞過迭代器
• 基本操作:新增鍵值對、修改指定鍵的資料、刪除、依鍵取值;輔助操作:判空、鍵值列表快照、完整快照
• **合併「新增」與「修改」**為一個成員函式(add_or_update_mapping),消除兩執行緒同時新增的介面競爭
• 「取值」不回傳引用,幾種介面選擇:
  • get_value(key, default_value):查無此鍵回傳預設值
  • 回傳 std::pair<mapped_type, bool>:bool 表示鍵是否存在
  • 回傳智慧指標:NULL 表示鍵不存在

為細粒度鎖選擇底層結構

每桶用一把 std::shared_mutex(多讀者/單寫者),併發度提升 N 倍(N = 桶數)。雜湊函式可用 std::hash<> 模板(可特化),或仿標準無序容器把雜湊函式型別當作模板參數。

代碼 6.11:threadsafe_lookup_table

結構:std::vector<std::unique_ptr<bucket_type>> buckets,每個 bucket_type 內含一個 std::list<std::pair<Key, Value>> 與 mutable std::shared_mutex mutex。

Value value_for(Key const& key, Value const& default_value) const {
    std::shared_lock<std::shared_mutex> lock(mutex);   // 讀:共享鎖
    bucket_iterator const found_entry = find_entry_for(key);
    return (found_entry == data.end()) ? default_value
                                       : found_entry->second;
}
// add_or_update_mapping / remove_mapping 則用:
// std::unique_lock<std::shared_mutex> lock(mutex);    // 寫:獨占鎖

• 桶數在建構時指定,預設 19(可為任意質數——雜湊表在質數個桶時效率最高)
• 桶數固定不變 → get_bucket()(hasher(key) % buckets.size())可以無鎖呼叫,三個公開函式也無需額外的表級鎖
• 讀操作(value_for)取共享所有權;寫操作(add_or_update_mapping、remove_mapping)取唯一所有權
• 每桶內用 find_entry_forfind_if 比對 key定位項目

異常安全分析

代碼 6.12:取得整表快照 get_map()

把整個查詢表複製成 std::map<Key, Value> 需要鎖住所有桶(一般操作只需鎖一個桶,此操作要求獨占整個容器):

• 用 std::vector<std::unique_lock<std::shared_mutex>> 依序收集所有桶的鎖
• 以相同順序(遞增桶索引)上鎖 → 不會死結
• 全部鎖住後,逐桶把項目 insert 進結果 map

執行緒安全鏈結串列:每節點一把鎖

支援迭代的鏈結串列若提供 STL 式迭代器,迭代器需持有容器內部引用──容器被其他執行緒修改時引用必須仍有效,實際上等於要迭代器持有鎖,非常糟糕。替代方案:把迭代做成容器的成員函式(如 for_each),由容器負責上鎖。

需要的操作:push_front(加入元素)、remove_if(條件刪除)、find_first_if(條件查找)、for_each(逐元素處理/更新、可複製到其他容器)。指定位置插入等功能查詢表用不到,故省略。

細粒度鎖思路:每個節點都擁有一把互斥鎖(串列長 → 鎖很多)。好處:串列的不同部分可真正並行操作;持有「感興趣的節點」的鎖,移往下一節點時釋放當前的鎖。

代碼 6.13:threadsafe_list 結構與交錯上鎖

節點:struct node { std::mutex m; std::shared_ptr<T> data; std::unique_ptr<node> next; };,以一個預設建構的 node 作為 head(data 為空,類似 dummy)。

• push_front():鎖外配置新節點 → 只鎖 head.m → 接上 head.next。只鎖一把 → 無死結;慢速的記憶體配置在鎖外

交錯上鎖 (hand-over-hand locking) 的迭代模式(for_each 核心):

      [head]      [A]        [B]        [C]
步驟1  lock ─────────────────────────────────  持 head
步驟2  lock       lock                          先鎖 A(下一個)
步驟3  unlock     hold                          再放 head
步驟4             hold  f(A) lock               處理 A;鎖 B
步驟5             unlock     hold  f(B) ...     放 A;處理 B ...

node* current = &head;
std::unique_lock<std::mutex> lk(head.m);
while (node* const next = current->next.get()) {
    std::unique_lock<std::mutex> next_lk(next->m); // 先鎖下一個
    lk.unlock();                                   // 再放當前的
    f(*next->data);
    current = next;
    lk = std::move(next_lk);                       // 鎖的所有權交接
}

• find_first_if():同 for_each,但謂詞回傳 true 時立即回傳找到的資料(shared_ptr),不再往下走
• remove_if():謂詞為 true 時——保持當前節點的鎖,把 current->next 接到 next->next(移除節點),先 next_lk.unlock() 再讓 unique_ptr 銷毀節點(銷毀仍上鎖的 mutex 是未定義行為);謂詞為 false 時照常交接前進

安全性與併發度分析

• 無死結:迭代一律從 head 出發、先鎖下一節點才放開當前節點 → 所有執行緒上鎖順序相同,不可能交叉持鎖
• 無競爭條件:唯一可疑處是 remove_if 刪除節點——因仍持有前一節點的鎖,其他執行緒無法前進到被刪節點,不會有執行緒嘗試取得它的鎖 → 安全(前提:使用者的函式/謂詞行為良好)
• 併發度:不同執行緒可同時在不同節點上工作(各自做 for_each/find/remove);但因上鎖順序固定,執行緒不能超車——一個執行緒在某節點耗時久,後面的執行緒就得排隊等它離開

Exam/Test Patterns

Related Notes

• 06-Lock-Based-Data-Structures/01-Concurrent-Design-Guidelines
• 06-Lock-Based-Data-Structures/02-Thread-Safe-Stack-and-Queue
• 06-Lock-Based-Data-Structures/03-Fine-Grained-Locking-Queue
• 06-Lock-Based-Data-Structures/Practice-Lock-Based-Data-Structures
• 03-Sharing-Data/03-Alternative-Data-Protection
• 08-Designing-Concurrent-Code/03-Designing-Data-Structures-for-Performance