細粒度鎖佇列 (Fine-Grained Locking Queue)

#cpp-concurrency #concept #lock-based-ds #thread-safe-queue #fine-grained-locking

Overview Table

概念	重點
單執行緒佇列(代碼 6.4)	單鏈結串列:`unique_ptr<node> head` + 裸指標 `tail`;直接加兩把鎖行不通
兩把鎖的問題	單元素時 `head == tail`,`head->next` 與 `tail->next` 是同一物件 → push/pop 相撞
虛擬節點 (dummy node)(代碼 6.5)	預先配置一個無資料節點永遠在隊尾 → push 只碰 tail、pop 只碰 head,分離存取
細粒度鎖版(代碼 6.6)	`head_mutex` + `tail_mutex`;`get_tail()` 必須在 `head_mutex` 範圍內呼叫
不變量分析	6 條不變量;push 只改 tail 端、維持不變量
可等待版(代碼 6.7–6.10)	加條件變數:`wait_for_data()` 回傳 `unique_lock`;引用版取值須在鎖內、刪節點前

單執行緒佇列(基礎版)

最簡單的佇列是單鏈結串列:head 指向第一個元素,每個元素的 next 指向下一個;tail 指向最後一個元素。pop 把 head 移到下一個節點;push 從尾端加入(改 tail->next 再更新 tail);空串列時 head/tail 皆為 NULL。

head ──> [A] ──> [B] ──> [C] ──> NULL
                          ^
                        tail

用 std::unique_ptr<node> head 管理節點鏈(自動刪除、免手動 delete),node* tail 為裸指標
節點內含 T data 與 std::unique_ptr<node> next

為何直接加兩把鎖行不通

即使 head、tail 各配一把互斥鎖,仍有問題:

push() 在空佇列時同時修改 head 與 tail → 需要同時鎖兩把(還不算最糟)
致命傷:單元素時 head == tail,head->next 與 tail->next 是同一個物件——push() 寫 tail->next、try_pop() 讀 head->next,兩者鎖的卻是不同的 mutex → 資料競爭

虛擬節點 (Dummy Node):分離資料實現併發

預先配置一個不存資料的虛擬節點,確保它永遠在佇列最後,用來分離 head 與 tail 能觸及的節點:

空佇列:                          push 一個元素後:
head ──> [dummy] <── tail        head ──> [A] ──> [dummy] <── tail
(head==tail,非 NULL)             (head、tail 指向不同節點)

空佇列時 head、tail 都指向虛擬節點(而非 NULL);判空改為 head.get() == tail
try_pop() 空佇列時不再存取 head->next;佇列非空時 head 與 tail 指向不同節點,head->next 與 tail->next 不再撞在同一物件上
push() 流程:堆上建 shared_ptr<T> 資料 → 建新的空節點(成為新 dummy)→ 把資料塞進舊 dummy → 舊 dummy 的 next 指向新 dummy → 更新 tail
節點的 data 改為 std::shared_ptr<T>(用 std::make_shared 避免二次配置);pop 直接檢索指標,不需建構 T 的新實例
代價:多一層間接指標(dummy node 本身)

結果:push() 只存取 tail,try_pop() 主要存取 head(只在開頭比較一次 tail)→ 一把鎖護 head、一把鎖護 tail 即可。

代碼 6.6:細粒度鎖版 threadsafe_queue

成員:std::mutex head_mutex; std::unique_ptr<node> head; std::mutex tail_mutex; node* tail;

node* get_tail() {
    std::lock_guard<std::mutex> tail_lock(tail_mutex);
    return tail;
}
std::unique_ptr<node> pop_head() {
    std::lock_guard<std::mutex> head_lock(head_mutex);
    if (head.get() == get_tail()) return nullptr;   // 鎖內比較!
    std::unique_ptr<node> old_head = std::move(head);
    head = std::move(old_head->next);
    return old_head;
}

push():資料與新節點的配置都在鎖外;之後 lock_guard 鎖 tail_mutex,做指標賦值直到函式結束
try_pop():鎖 head_mutex 直到 head 更新完;回傳結果(old_head->data)時已不持鎖
get_tail() 內的 tail_mutex 與 push() 鎖同一把 → 為兩個操作規定了順序:get_tail 要嘛看到舊 tail、要嘛看到 push 後的新 tail,值一定有效

有缺陷的寫法:在 head_mutex 外呼叫 get_tail()

若先 get_tail() 取得 old_tail、再鎖 head_mutex:等鎖期間 head 與 tail 可能都變了——old_tail 可能已不在串列中,head.get()==old_tail 的比較失去意義,更新 head 時可能把 head 移到 tail 之後,破壞整個資料結構。正確寫法:get_tail() 必須在 head_mutex 保護範圍內呼叫,保證期間無人動 head,tail 只會朝正確方向移動(新增節點)。

不變量分析(6.1.1 指南的實際應用)

#	不變量
1	`tail->next == nullptr`
2	`tail->data == nullptr`(尾端永遠是 dummy)
3	`head == tail` 意味著空串列
4	單元素串列:`head->next == tail`
5	串列中每個節點 `x`(`x != tail`):`x->data` 指向 T 實例、`x->next` 指向下一節點;`x->next == tail` 表示 x 是最後一個有資料的節點
6	從 head 沿著 next 走,最終必到達 tail

push() 只修改 tail_mutex 保護的資料:新尾節點是空節點、舊 dummy 的 data 與 next 都設好才更新 tail → 維持不變量
異常安全:try_pop 只有取鎖可能拋異常(取到鎖前不修改資料);push 中的堆配置可能拋異常,但全部交給智慧指標,異常時自動釋放;取鎖後只做不拋異常的指標賦值
死結:唯一需要兩把鎖的是 pop_head(),永遠先 head_mutex 後 tail_mutex 的固定順序 → 不會死結
併發度:配置(最耗時的操作)全在鎖外;push 與 try_pop 可真正並行;tail_mutex 持有時間極短

可等待版:加入條件變數(代碼 6.7–6.10)

wait_and_pop() 的等待條件是「佇列非空」= head != tail。利用既有邏輯:比較 head.get() != get_tail() 只需持有 head_mutex。

std::unique_lock<std::mutex> wait_for_data() {
    std::unique_lock<std::mutex> head_lock(head_mutex);
    data_cond.wait(head_lock, [&]{ return head.get() != get_tail(); });
    return std::move(head_lock);     // 把鎖交還呼叫者
}

push() 末尾(釋放 tail_lock 之後)呼叫 data_cond.notify_one()——鎖外通知,避免被喚醒的執行緒醒來又卡在鎖上
wait_for_data() 用 Lambda 等待,並把 unique_lock 回傳給呼叫者,確保 wait_pop_head() 後續刪節點時仍持有同一把鎖
輔助函式分工:pop_head()(純刪頭節點)、wait_pop_head()、try_pop_head();empty() 只需鎖 head_mutex 檢查 head.get() == get_tail()

引用版重載的異常安全

若先把節點移出串列、解鎖後才 value = old_head 的值 拷貝賦值:拷貝拋異常時資料就永久丟失(回不去佇列)。解法:當 T 沒有不拋異常的移動賦值/交換時,必須把可能拋異常的取值 value = std::move(*head->data) 放在鎖內、且在節點移出串列之前(wait_pop_head(T&) 正是如此)。

無限佇列 vs 有限佇列

本實作是無限佇列(可無限 push),它也是第7章無鎖佇列的基礎。有限佇列 (bounded queue) 建立時就固定最大長度,滿載時 push 失敗或阻塞——很容易擴充:讓 push() 也等待條件變數「元素數 < 上限」即可;對第8章的任務分配可減少執行緒間的開銷。

Exam/Test Patterns

情境/關鍵字	答案
「鏈結串列佇列直接 head/tail 各一把鎖,行嗎?」	不行:單元素時 `head->next` 與 `tail->next` 是同一物件,兩把鎖護不住同一資料
「dummy node 的作用?」	讓空佇列時 head/tail 指向虛擬節點,push 只碰 tail、pop 只碰 head,分離存取實現細粒度鎖
「dummy node 版如何判空?」	`head.get() == tail`(head 永不為 NULL,不能檢查空指標)
「為何 `get_tail()` 要在 `head_mutex` 內呼叫?」	否則等 head_mutex 期間 tail 可能已失效,head 可能被移到 tail 之後,破壞結構
「pop_head 需要兩把鎖,會死結嗎?」	不會:唯一取兩鎖處,固定先 head 後 tail 順序
「細粒度版效能提升在哪?」	節點/資料配置全在鎖外;push 與 try_pop 可真正並行;鎖持有時間極短
「wait_for_data 為何回傳 unique_lock?」	確保後續刪節點時仍持有同一把鎖(等待與彈出為一個原子過程)
「引用版 pop 的拷貝賦值拋異常 → 資料丟失」	取值必須放在鎖內、節點移出串列之前