競爭條件與互斥鎖 (Race Conditions and Mutexes)

Overview Table

共享資料的問題:不變量被破壞

共享資料的麻煩全來自「修改」:若所有資料唯讀,任何執行緒讀到的都一樣,毫無問題。一旦有執行緒修改,就可能讓其他執行緒看到不變量的中間狀態。

以雙向鏈結串列為例:不變量是「A 的 next 指向 B,則 B 的 prev 指回 A」。刪除節點 N 需要分別更新兩側指標——只更新完一側時,不變量已被破壞:

刪除節點 N 的步驟:
a. 找到節點 N
b. N->prev 的 next 改指 N->next   ← 此刻不變量已破壞!
c. N->next 的 prev 改指 N->prev   ← 到這裡才恢復
d. 刪除 N

  [A] <──> [N] <──> [B]
   │                 ↑
   └── 步驟 b 後:A.next→B,但 B.prev 仍→N(不一致)

• 另一執行緒此刻遍歷串列:可能讀到已刪一半的節點、跳過節點
• 若第二個執行緒同時刪相鄰節點:資料結構永久損壞、程式崩潰

競爭條件:良性 vs 惡性

競爭條件指結果取決於多個執行緒操作的相對執行順序(如搶電影票:座位取決於購買順序)。

• 惡性競爭出現機率低、難重現:CPU 指令序需恰好交錯才觸發
• 時間敏感:負載增加時更易出現;除錯模式常讓 bug 消失(改變了時序)

避免惡性競爭條件的三種方式

1. 保護機制(鎖):最簡單——確保只有修改中的執行緒能看到不變量中間狀態;其他執行緒看到的修改「不是還沒開始,就是已經完成」
2. 無鎖 (lock-free) 編程:修改資料結構與不變量的設計,使修改成為一系列不可分割的變更——很難寫對,記憶體模型的細微差異都會放大工作量(見第7章)
3. 軟體交易記憶體 (STM):像資料庫交易一樣記錄-合併-提交,衝突則重來——C++ 標準無直接支援(僅有技術規範 TS)

std::mutex 與 std::lock_guard

存取共享資料前上鎖、結束後解鎖;其他執行緒必須等鎖釋放才能存取。不建議直接呼叫 lock()/unlock()——必須在每個出口(含例外路徑)配對解鎖,改用 RAII 類 std::lock_guard。

std::list<int> some_list;
std::mutex some_mutex;

void add_to_list(int v) {
    std::lock_guard<std::mutex> guard(some_mutex);  // 建構上鎖、解構解鎖
    some_list.push_back(v);
}
bool list_contains(int v) {
    std::lock_guard<std::mutex> guard(some_mutex);  // 與上面互斥
    return std::find(some_list.begin(), some_list.end(), v) != some_list.end();
}

• 兩函式共用同一 mutex → list_contains() 絕不會看到 add_to_list() 修改到一半的串列
• C++17 模板參數推導 (CTAD):可簡寫 std::lock_guard guard(some_mutex);,也可用加強版 std::scoped_lock guard(some_mutex);
• 物件導向慣例:mutex 與受保護資料應包成同一類別的 private 成員,而非全域變數;所有成員函式上鎖後操作、返回前解鎖

不要傳出受保護資料的指標或引用

只要有任何成員函式把受保護資料的指標或引用傳到鎖的作用域之外(回傳值、輸出參數、或傳給使用者提供的函式),保護就被繞過:

class data_wrapper {
    some_data data;  std::mutex m;
public:
    template<typename Function>
    void process_data(Function func) {
        std::lock_guard<std::mutex> l(m);
        func(data);   // 危險:把「受保護」資料交給使用者函式
    }
};
some_data* unprotected;
void malicious_function(some_data& d) { unprotected = &d; }  // 偷走引用
// 之後 unprotected->do_something() 就在無鎖狀態下存取資料

介面固有的競爭條件:stack 的 empty/top/pop

即使每個成員函式都上了鎖,介面設計本身仍可能有競爭條件——這與實作方式無關(無鎖實作同樣中招)。以 std::stack 介面為例:

stack<int> s;
if (!s.empty()) {              // 1 檢查非空
    int const value = s.top(); // 2 之間可能被別的執行緒 pop 光 → UB
    s.pop();                   // 3 之間可能被別的執行緒也 pop → 語義錯亂
    do_something(value);
}

• empty→top 競爭:單執行緒下安全;共享物件時,①②之間另一執行緒可能 pop() 掉最後一個元素,空堆疊上呼叫 top() 是未定義行為
• top→pop 競爭:兩執行緒交錯執行時可能「同一值被處理兩次、另一值被丟棄從未處理」——看起來沒有錯誤,比崩潰更難定位:

為什麼 std::stack 要把 top 和 pop 分開?

例外安全考量(Tom Cargill 的問題):若 pop() 直接回傳彈出值,stack<vector<int>> 在複製回傳值時可能拋出 std::bad_alloc——值已從堆疊移除、複製卻失敗,資料就永久遺失。分成 top()(取值)+pop()(移除)可避免;但這個分割正是製造介面競爭的元兇。

解決選項

threadsafe_stack(採選項 1+3)

struct empty_stack : std::exception { const char* what() const throw(); };

template<typename T>
class threadsafe_stack {
    std::stack<T> data;
    mutable std::mutex m;          // mutable:const 成員函式也要上鎖
public:
    void push(T v);                // 上鎖後 push
    std::shared_ptr<T> pop();      // 空則拋 empty_stack;先 make_shared 再 pop
    void pop(T& value);            // 空則拋 empty_stack;先賦值再 pop
    bool empty() const;
    threadsafe_stack& operator=(const threadsafe_stack&) = delete;
};

• 削減介面換取最大安全:五個操作縮成三個(push/pop/empty),無 top()、無 swap()、刪除賦值
• pop() 內部先檢查空、先建好回傳值make_shared)、最後才 data.pop( → 檢查與彈出在同一把鎖內完成,且例外安全
• 複製建構函式在函式本體內先鎖 other.m 再複製(不能用成員初始化列表,否則複製時未持鎖)

Exam/Test Patterns

Related Notes

• 03-Sharing-Data/02-Deadlock-and-Lock-Management
• 03-Sharing-Data/03-Alternative-Data-Protection
• 03-Sharing-Data/Practice-Sharing-Data
• 05-Memory-Model-and-Atomics/01-Memory-Model-Basics — 資料競爭與未定義行為的記憶體模型細節
• 06-Lock-Based-Data-Structures/02-Thread-Safe-Stack-and-Queue — threadsafe_stack 的完整發展