基於鎖的併發資料結構練習題 (Practice - Lock-Based Data Structures)

多執行緒併發存取(執行相同或不同操作)時:無資料遺失或損毀(所有資料維持原樣)、任何執行緒看不到不變量被破壞的狀態、且無競爭條件。另需註明:建構/解構必須獨占存取,且「安全」可能限定於特定的併發使用方式(如不同操作併發安全、相同操作需序列化)。

互斥鎖之下同一時間只有一個執行緒能取得鎖,執行緒輪流(串行)存取資料,這就是序列化。核心思想:讓序列化存取最小化、讓真實併發最大化——縮小保護區域、把操作移出鎖外、用不同的鎖保護不同區域、區分讀/寫保護級別。

分離的 top()/pop()(以及 empty()+pop())存在介面固有的競爭條件:兩個呼叫之間其他執行緒可能改變堆疊。解法是提供完整操作:pop() 在鎖內檢查空(拋 empty_stack)、取值、刪除一次完成,並以 std::shared_ptr<T> 回傳或寫入引用參數。

資料仍在佇列裡,但其他等待執行緒不會再被喚醒,永遠沉睡。三種解法:(1) 改用 notify_all()——但多數執行緒醒來發現佇列仍空,浪費資源;(2) 拋異常時補呼叫 notify_one(),讓另一執行緒去取值;(3) 佇列改存 std::shared_ptr<T>,make_shared 移到 push()——拷貝 shared_ptr 不拋異常(推薦,且有效能紅利)。

沒有 dummy node 時,單元素佇列 head == tail,head->next 與 tail->next 是同一物件,push 與 try_pop 會在不同鎖的保護下碰同一資料 → 資料競爭。dummy node 永遠在佇列尾端:空佇列時 head/tail 都指向它(判空用 head.get() == tail),push 只碰 tail、try_pop 只碰 head,兩把互斥鎖(head_mutex/tail_mutex)得以分工。代價是多一層間接指標。

二元樹:每次操作都經過根節點,根節點的鎖成瓶頸,不比單鎖好;有序陣列最糟:無法預知目標位置,只能鎖整個陣列;雜湊表最佳:鍵經雜湊函式落入固定的桶,每桶一把 std::shared_mutex 可獨立上鎖,併發度提升 N 倍(N=桶數)。19 是質數——雜湊表在質數個桶時工作效率最高;桶數固定也讓 get_bucket() 可無鎖呼叫。

此操作需要鎖住所有桶(否則快照不一致)。做法:用 std::vector<std::unique_lock<std::shared_mutex>> 依遞增桶索引的固定順序逐一上鎖,全部鎖住後再逐桶複製。因為所有執行緒都以相同順序取鎖,不可能形成循環等待 → 無死結。這正是第3章「固定上鎖順序」原則的應用。

get_tail() 在 head_mutex 範圍外呼叫:等待 head_mutex 期間,其他執行緒可能已 push(tail 移動)或 pop(head 移動),old_tail 可能已不是尾節點、甚至已不在串列中。比較結果失去意義,更新 head 時可能把 head 移到 tail 之後,破壞資料結構。正解(代碼 6.6):先鎖 head_mutex,在其保護範圍內呼叫 get_tail()——保證比較期間 head 不被修改,tail 只會因新增節點而正向移動。

併發度:單鎖版任一時刻只有一個執行緒工作(6.3 已把 make_shared 移到鎖外,是重要改良);細粒度版 push 與 try_pop 可真正並行,且節點/資料配置全在鎖外、兩把鎖持有時間極短。複雜度:單鎖版直接複用 std::queue,簡單直觀;細粒度版須自建串列、維護 6 條不變量、小心 get_tail 的呼叫位置——推理難度高得多。異常安全:兩者都能做到——細粒度版靠「配置交給智慧指標 + 鎖內只做不拋異常的指標賦值」。取捨:競爭激烈、push/pop 頻繁的多生產者多消費者場景才值得細粒度版;否則單鎖版的簡單性更有價值。

無死結:所有操作一律從 head 出發、先鎖下一節點才釋放當前節點,全部執行緒上鎖順序一致,不可能循環等待。唯一微妙處在 remove_if 刪節點:先解鎖 next_lk 再銷毀節點(銷毀上鎖的 mutex 是 UB),且因仍持有前一節點的鎖,無其他執行緒能到達被刪節點 → 安全。併發度:不同執行緒可同時在串列的不同節點上工作(for_each/find/remove 並行),遠勝整條串列一把鎖。極限:上鎖順序固定 → 執行緒不能超車,若某執行緒在一個節點上耗時久(使用者函式慢),後面的執行緒全部排隊;且持鎖呼叫使用者代碼,行為不良的謂詞(再取鎖、存引用)會引入死結/競爭——責任交給使用者。