Enter your search text in the box above

Select a result to preview

死結與鎖管理 (Deadlock and Lock Management)

#cpp-concurrency #concept #data-sharing #deadlock #lock-granularity

Overview Table

概念 重點
死結 (deadlock) 兩個以上執行緒互相等待對方持有的鎖,誰都動不了
std::lock / std::scoped_lock 一次鎖住多個 mutex,全有或全無,無死結風險
避免死結四大指導 避免嵌套鎖 / 持鎖不呼叫外部程式碼 / 固定順序上鎖 / 鎖層級
hierarchical_mutex 執行期檢查鎖層級,違反即拋例外——死結不可能發生
std::unique_lock 靈活的 RAII 鎖:延遲上鎖、手動 lock/unlock、可移動轉移所有權
鎖粒度 (lock granularity) 一把鎖保護的資料量;持鎖時間應盡可能短

死結:問題描述

比喻:玩具鼓需要鼓與鼓錘才能玩。兩個小孩各搶到一件,都不肯放手——誰也玩不成。執行緒版本:一對執行緒各持有一個 mutex,並等待對方的 mutex 解鎖:

執行緒 1                     執行緒 2
lock(A) ── 成功              lock(B) ── 成功
lock(B) ── 阻塞 ─┐           lock(A) ── 阻塞 ─┐
        │ 等執行緒 2 釋放 B          │ 等執行緒 1 釋放 A
        └──────── 循環等待 → 死結 ────────┘
死結四條件(作業系統經典理論,補充)

死結需同時滿足:互斥 (mutual exclusion)、持有並等待 (hold and wait)、不可搶占 (no preemption)、循環等待 (circular wait)。破壞任何一條即可避免死結——本章各技巧本質上都在破壞「持有並等待」或「循環等待」。

固定順序也可能失效

一般建議「兩個 mutex 永遠以相同順序上鎖」(先 A 後 B)。但當多個 mutex 保護同一類別的不同實例時,「第一個參數的鎖先上」這種固定規則會適得其反:

swap 的陷阱

執行緒 1 呼叫 swap(a, b)、執行緒 2 同時呼叫 swap(b, a) ——兩者都「先鎖第一個參數」,結果一個先鎖 a、一個先鎖 b,又死結了。這正是 std::lock 要解決的場景。

std::lock 與 std::scoped_lock:同時上鎖

std::lock() 可一次性鎖住多個 mutex(兩個以上),不會死結:

friend void swap(X& lhs, X& rhs) {
    if (&lhs == &rhs) return;              // 同一實例重複上鎖是 UB,先檢查
    std::lock(lhs.m, rhs.m);               // 1 一次鎖住兩個
    std::lock_guard<std::mutex> a(lhs.m, std::adopt_lock);  // 2 接管已上鎖的 mutex
    std::lock_guard<std::mutex> b(rhs.m, std::adopt_lock);  // 3
    swap(lhs.some_detail, rhs.some_detail);
}

C++17 std::scoped_lock<>:可變參數版的 RAII 模板,建構時如 std::lock 般上鎖、解構時解鎖,一行搞定:

std::scoped_lock guard(lhs.m, rhs.m);  // C++17 CTAD,等價 std::scoped_lock<std::mutex,std::mutex>
Tip

C++17 環境下可用 std::scoped_lock 取代所有 std::lock + adopt_lock 樣板,減少出錯機會。

限制

std::lock/std::scoped_lock 只在「同時獲取多個鎖」時救你;若各鎖是分開先後獲取的,仍要靠開發者的紀律(以下指導)避免死結。

避免死結的進階指導

核心心法:不要謙讓(別讓執行緒互相等待有機會形成環)。

1. 避免嵌套鎖

已持有一個鎖時,別再獲取第二個。每執行緒最多持一鎖,死結不可能發生。真需要多個鎖時,用 std::lock 一次取得。

2. 避免在持鎖時呼叫外部(使用者提供的)程式碼

外部程式碼可能做任何事——包括獲取鎖,就會違反指導 1。通用程式碼(如 threadsafe_stack,參數型別由外部定義)有時無法避免,需其他指導配合。

3. 使用固定順序獲取鎖

必須分開獲取兩個以上的鎖且無法用 std::lock 時,所有執行緒以相同順序上鎖。鏈結串列的「手遞手 (hand-over-hand)」鎖法:先鎖住當前節點,才能鎖下一個節點,之後釋放前一個——但必須規定遍歷方向:

執行緒 1(正向遍歷)              執行緒 2(反向遍歷)
鎖住 A ─► 嘗試鎖 B(阻塞)        鎖住 C ─► 鎖住 B ─► 嘗試鎖 A(阻塞)
                    互等 → 死結!(圖 3.2)

4. 使用鎖層級 (lock hierarchy)

把應用分層,每個 mutex 指定層級數字;執行緒只能獲取比目前已持有層級更低的鎖——違反即執行期報錯:

hierarchical_mutex high_level_mutex(10000);
hierarchical_mutex low_level_mutex(5000);
hierarchical_mutex other_mutex(6000);
// OK:先鎖 10000 再鎖 5000(遞減)
// 錯誤:已持 6000 再想鎖 10000 → 拋出例外

hierarchical_mutex 實作要點(非標準庫,但容易自寫):

執行期偵測、無時間依賴

層級鎖不必等死結真的發生才發現問題——只要違反層級就立刻報錯,即使當下沒有其他執行緒競爭。

層級鎖的限制

同一層級的多個 mutex 不能同時持有 → 「手遞手」模式要求鏈上每個 mutex 層級遞減,某些設計下無法實現。

超越鎖的延伸

死結也發生在任何等待循環:持鎖時等待另一個執行緒(它可能正需要你的鎖)、互相 join()。建議:執行緒也分層——只等待層級比自己低的執行緒;在同一函式內啟動並 join 的執行緒天然滿足。

std::unique_lock:靈活的鎖

std::unique_lock 是比 std::lock_guard 更靈活的 RAII 鎖,不必總是擁有關聯的 mutex:

能力 std::lock_guard std::scoped_lock (C++17) std::unique_lock
一次鎖多個 mutex 否 是(內建防死結) 配合 std::lock()
延遲上鎖 defer_lock 否 否 是
手動 lock()/unlock()/try_lock() 否 否 是
所有權轉移(可移動) 否 否 是
空間/速度成本 最小 最小 較大(需存旗標、檢查旗標) 
std::unique_lock<std::mutex> lock_a(lhs.m, std::defer_lock);  // 建構但不上鎖
std::unique_lock<std::mutex> lock_b(rhs.m, std::defer_lock);
std::lock(lock_a, lock_b);   // 這裡才一起上鎖(unique_lock 有 lock/try_lock/unlock)

不同作用域間轉移 mutex 所有權

std::unique_lock 可移動、不可複製——鎖的所有權可跨函式轉移:

std::unique_lock<std::mutex> get_lock() {
    extern std::mutex some_mutex;
    std::unique_lock<std::mutex> lk(some_mutex);
    prepare_data();
    return lk;                       // 自動變數直接回傳,編譯器套用移動
}
void process_data() {
    std::unique_lock<std::mutex> lk(get_lock());  // 接手鎖,資料保證未被動過
    do_something();
}

鎖粒度 (Lock Granularity)

鎖粒度描述一把鎖保護的資料量:細粒度鎖保護少量資料、粗粒度鎖保護大量資料。超市結帳比喻:結帳到一半才跑去拿蔓越莓醬,全隊的人都得等你。

void get_and_process_data() {
    std::unique_lock<std::mutex> my_lock(the_mutex);
    some_class data = get_next_data_chunk();
    my_lock.unlock();                 // process() 不碰共享資料,不需持鎖
    result_type result = process(data);
    my_lock.lock();                   // 寫回結果前再上鎖
    write_result(data, result);
}

粒度變細的語義代價

若操作只需一次持有一把鎖,可縮短持鎖時間、消除死結,但語義可能改變:

friend bool operator==(Y const& lhs, Y const& rhs) {
    if (&lhs == &rhs) return true;
    int const lhs_value = lhs.get_detail();  // 各自短暫上鎖讀值
    int const rhs_value = rhs.get_detail();  // ← 兩次讀取之間值可能已變
    return lhs_value == rhs_value;
}
微妙的語義變化

上例回傳 true 只代表「某時刻的 lhs 值 == 另一時刻的 rhs 值」,兩值在讀取後可能被任意修改甚至互換——比較可能在「兩值其實從未同時相等」的情況下回傳 true。持鎖時間未覆蓋整個操作,就是把自己暴露在競爭條件中;若需要「同一時刻相等」的語義,必須用 std::lock 同時鎖兩者。

Exam/Test Patterns

情境/關鍵字 答案
「兩個執行緒互相 join()」 無鎖也會死結——任何等待循環都算
「swap(a,b) 與 swap(b,a) 同時執行死結」 固定「第一參數先鎖」失效 → std::lock / std::scoped_lock
「一次要鎖兩個以上 mutex」 std::lock()(全有或全無)或 C++17 std::scoped_lock
「std::adopt_lock」 接管已上鎖的 mutex,只負責解構時解鎖
「std::defer_lock」 建構時不上鎖,之後由 lock() 或 std::lock() 上鎖(限 unique_lock)
「需要提前解鎖/中途再鎖/轉移鎖所有權」 std::unique_lock(可移動、有 owns_lock 旗標)
「執行期檢查上鎖順序、違反即拋例外」 層級鎖 hierarchical_mutex(thread_local 記錄當前層級)
「手遞手鎖住鏈結串列,兩方向遍歷」 死結 → 規定固定遍歷/上鎖順序
「持鎖做檔案 I/O」 粒度過粗;持鎖時間應最短化
「一次一鎖比較兩物件的值」 語義變化:兩值取自不同時間點