執行緒安全堆疊與佇列 (Thread-Safe Stack and Queue)

#cpp-concurrency #concept #lock-based-ds #thread-safe-stack #thread-safe-queue

Overview Table

概念	重點
`threadsafe_stack`(代碼 6.1)	單一 mutex + `std::lock_guard` 保護所有成員函式;pop 合併 top+pop 消除介面競爭
堆疊的異常安全分析	逐一檢查:上鎖、push、make_shared、pop——修改資料前拋異常都安全
堆疊的侷限	等待元素只能輪詢 `empty()`/接異常,浪費資源 → 需要條件變數
`threadsafe_queue`(代碼 6.2)	mutex + 條件變數;`push()` 之後 `notify_one()`,`wait_and_pop()` 阻塞等待
`notify_one()` 異常安全問題	被喚醒者拋異常 → 其他等待者永遠沉睡;三種解法
`shared_ptr` 存儲版(代碼 6.3)	佇列存 `std::shared_ptr<T>`:pop 不再拋異常,且配置移到鎖外提升效能

threadsafe_stack:使用鎖的堆疊

第3章的執行緒安全堆疊(仿 std::stack<>):單一 std::mutex,每個成員函式第一件事就是 std::lock_guard 上鎖,保證同一時間只有一個執行緒存取資料。

std::shared_ptr<T> pop() {
    std::lock_guard<std::mutex> lock(m);
    if (data.empty()) throw empty_stack();          // 鎖內檢查空
    std::shared_ptr<T> const res(
        std::make_shared<T>move(data.top())); // 合併 top+pop
    data.pop();
    return res;
}

消除介面競爭:empty() 與 pop() 之間雖有競爭,但 pop() 在鎖內顯式檢查是否為空(拋 empty_stack),不是惡性競爭
pop() 直接回傳彈出值(shared_ptr 或引用參數兩種重載),避免 std::stack<> 中 top() 與 pop() 分離造成的競爭
拷貝建構函式也上鎖(鎖 other.m);賦值運算子直接 delete

異常安全分析(逐點檢查)

異常源	是否安全	理由
互斥鎖上鎖拋異常	安全	是每個函式的第一個操作,尚未修改任何資料
`data.push()` 拋異常(拷貝/移動或記憶體不足)	安全	`std::stack<>` 自身保證安全性
`make_shared` 建立 `res` 拋異常	安全	記憶體不足或拷貝/移動建構失敗時,堆疊尚未被修改;執行時期庫保證無記憶體洩漏
引用版 `value = std::move(data.top())` 拋異常	安全	在 `data.pop()` 之前,資料結構未被修改
`data.pop()`、解鎖、`empty()`	安全	保證不拋異常

潛在死結:鎖內呼叫使用者代碼

持鎖時會呼叫使用者型別的拷貝/移動建構、拷貝/移動賦值、自訂 new 運算子。若這些使用者代碼又去呼叫堆疊的成員函式(再次取鎖),就可能死結。這是使用者的責任:放進堆疊的型別不得如此行事。

建構/解構不是執行緒安全的

使用者必須保證:堆疊完成建構前、開始銷毀後,沒有其他執行緒存取它。

堆疊的侷限:無法等待

當堆疊為空、執行緒想「等待元素出現」時,只能定期輪詢 empty()/pop() 並處理 empty_stack 異常——浪費資源檢查資料,或要求使用者自行寫等待/通知代碼,讓內部鎖失去意義。解法:改用條件變數 (condition variable) 的佇列。

threadsafe_queue:鎖 + 條件變數

代碼 6.2 重新實作第4章的執行緒安全佇列(仿 std::queue<>),成員:mutable std::mutex mut、std::queue<T> data_queue、std::condition_variable data_cond。

void push(T data) {
    std::lock_guard<std::mutex> lk(mut);
    data_queue.pushmove(data);
    data_cond.notify_one();               // 通知一個等待者
}
void wait_and_pop(T& value) {
    std::unique_lock<std::mutex> lk(mut);
    data_cond.wait(lk, [this]{ return !data_queue.empty(); });
    value = std::move(data_queue.front());
    data_queue.pop();
}

wait_and_pop():data_cond.wait() 直到佇列有元素才返回——不必擔心空佇列,且互斥鎖保護資料;不變量未變,不增加新的競爭條件或死結
try_pop():非阻塞版,空時回傳 false 或空的 shared_ptr(NULL)
其餘分析與堆疊相同(介面無固有競爭、異常安全)

notify_one() 的異常安全問題

多個執行緒都在 wait_and_pop() 等待時,push() 的 data_cond.notify_one() 只喚醒一個。若被喚醒的執行緒在鎖內拋出異常(例如建構 std::shared_ptr<> 時),資料仍在佇列中,但沒有任何其他執行緒會再被喚醒——它們永遠沉睡。

解法	做法	代價
1. `notify_all()`	喚醒所有等待執行緒	大多數執行緒發現佇列仍空,白白醒來又睡,耗費資源
2. 異常時補通知	`wait_and_pop()` 拋異常時再呼叫一次 `notify_one()`,讓另一執行緒去取值	需要 try/catch 補救邏輯
3. 存 `shared_ptr`(推薦)	`std::shared_ptr<>` 的初始化移到 `push()`,佇列改存 `std::shared_ptr<T>`;拷貝 `shared_ptr` 出佇列不會拋異常	需解引用取值;整體反而更快(見下)

代碼 6.3:持有 shared_ptr 的佇列

佇列改為 std::queue<std::shared_ptr<T>> data_queue:

void push(T new_value) {
    std::shared_ptr<T> data(
        std::make_shared<T>move(new_value)); // 配置在鎖外!
    std::lock_guard<std::mutex> lk(mut);
    data_queue.push(data);
    data_cond.notify_one();
}

引用版 pop 需解引用:value = std::move(*data_queue.front())
shared_ptr 版 pop 直接回傳 data_queue.front(),不需再 make_shared

意外的效能紅利

新實例的記憶體配置在 push() 上鎖之前完成(代碼 6.2 只能在 pop 持鎖時配置)。記憶體配置代價高昂,把它移出鎖外縮短了互斥鎖持有時間——其他執行緒可在配置的同時操作佇列,效能大幅提升。

單一互斥鎖仍是瓶頸

6.2/6.3 都用一把 mutex 保護整個資料結構,任一時間仍只有一個執行緒真正工作。因底層是 std::queue<>,無法對內部做更細的控制——要更高併發度,必須自建結構、使用細粒度鎖(見下一篇)。

Exam/Test Patterns

情境/關鍵字	答案
「為何 pop 要直接回傳值而非分離 top/pop?」	消除介面固有競爭條件——檢查空、取值、刪除須為單一完整操作
「`threadsafe_stack::pop` 中 `make_shared` 拋異常怎麼辦?」	安全:此時堆疊尚未被修改,不變量維持
「持鎖時呼叫使用者代碼的風險?」	拷貝/移動建構、賦值、自訂 `new` 可能再取鎖 → 死結
「空堆疊如何等待新元素?」	單鎖堆疊只能輪詢(浪費資源);應改用條件變數的 `wait_and_pop()`
「`notify_one` 後被喚醒執行緒拋異常」	其他等待者永遠沉睡;解法:notify_all / 異常時補 notify_one / 佇列改存 shared_ptr
「為何存 `shared_ptr<T>` 比存 `T` 快?」	`make_shared` 移到 push 的鎖外執行,縮短持鎖時間
「`try_pop` 與 `wait_and_pop` 差異」	`try_pop` 立即返回(空 → false/NULL);`wait_and_pop` 以條件變數阻塞至有資料