Enter your search text in the box above

Select a result to preview

無鎖概念與利弊權衡 (Lock-Free Concepts and Tradeoffs)

#cpp-concurrency #concept #lock-free-ds #lock-free #wait-free

Overview Table

概念 重點
阻塞 vs 非阻塞 呼叫阻塞函式庫(mutex、條件變數、future)會掛起執行緒;不用阻塞函式庫的結構稱非阻塞 (non-blocking)
自旋鎖 (spinlock) 非阻塞但不是無鎖——仍有鎖,一次只允許一個執行緒
obstruction-free(無阻礙) 其他執行緒全部暫停時,任一執行緒能在有限時間完成操作
lock-free(無鎖) 多執行緒併發操作時,至少一個執行緒能在有限時間完成(系統整體有進展)
wait-free(無等待) 每個執行緒都能在有限步驟內完成,不受其他執行緒影響
優點 最大化併發、強健性 (robustness)、無死結 (deadlock)
缺點 複雜度高、原子操作昂貴、快取乒乓、可能出現活結 (livelock)、整體效能未必更好

阻塞 vs 非阻塞

使用互斥鎖 (mutex)、條件變數 (condition variable)、future 同步時,函式庫會呼叫阻塞操作掛起執行緒(作業系統將其時間片交給別人),直到解鎖、通知或 future 就緒才解除阻塞。不使用阻塞函式庫呼叫的資料結構與演算法稱為非阻塞結構。

第 5 章用 std::atomic_flag 實作的自旋鎖就是典型例子:

class spinlock_mutex {
    std::atomic_flag flag;
public:
    spinlock_mutex(): flag(ATOMIC_FLAG_INIT) {}
    void lock()   { whilememory_order_acquire); }
    void unlock() { flag.clearmemory_order_release; }
};

lock() 沒有任何阻塞呼叫,只是在迴圈中自旋——所以它是非阻塞的;但它仍是一把鎖、一次只能有一個執行緒進入,所以不是無鎖結構。

常見混淆

「非阻塞 (non-blocking)」是最寬的類別;自旋鎖屬於「非阻塞—有鎖」。無鎖 (lock-free) 是非阻塞的子集,需要額外的進展保證。

非阻塞的三個層級

層級 定義 進展保證 備註
obstruction-free(無阻礙) 若其他執行緒都暫停,任一執行緒可在有限時間完成 最弱(孤立執行時才保證) 實務少用;常用來描述一個失敗的 lock-free 實作
lock-free(無鎖) 多執行緒同時操作,經過有限時間其中一個執行緒必完成 系統整體有進展;個別執行緒可能飢餓 典型形式:compare_exchange 重試迴圈
wait-free(無等待) 每個執行緒都在有限步驟內完成,不管其他執行緒怎麼做 每執行緒都有進展上限 最難正確實作;不允許無上限的重試迴圈 
                包含關係(由寬到窄)

  非阻塞 (non-blocking)
  ├── 非阻塞—有鎖(如:自旋鎖)
  └── obstruction-free 無阻礙
        └── lock-free 無鎖        ← 至少一個執行緒有進展
              └── wait-free 無等待 ← 每個執行緒都有進展

無鎖結構的利

代價:不變量的維護更難

沒有鎖就無法「鎖住整個結構再修改」。必須用原子操作限制修改、注意其他執行緒看到修改的順序(記憶體順序),否則就是資料競爭與未定義行為。

無鎖結構的弊

「無鎖結構不會死結」有例外情境要注意

無死結不代表無活結;且 wait-free 依定義步驟有上限,才真正免疫活結。另外,某些平台上 std::atomic<> 的實作內部使用鎖(可用 is_lock_free() 檢查),此時「無鎖」演算法實際上基於鎖完成。

決策準則

使用無鎖結構的兩大理由:最大化併發與強健性。若只是想「更快」,請先量測——基於鎖的結構常常更快也更容易寫對。

Exam/Test Patterns

情境/關鍵字 答案
「自旋鎖是無鎖結構嗎?」 不是——它非阻塞,但仍是鎖(非阻塞—有鎖)
「其他執行緒都暫停時才保證完成」 obstruction-free(無阻礙)
「保證至少一個執行緒有進展」 lock-free(無鎖)
「每個執行緒都在有限步驟內完成」 wait-free(無等待)
「CAS 迴圈重試無上限」是哪一級? lock-free 但非 wait-free(可能飢餓)
「執行緒持鎖時被 kill,結構壞掉」 無鎖結構的強健性優勢:資料不會因此損壞
「兩執行緒互相讓對方重試、無限循環」 活結 (livelock);無鎖結構可能發生,wait-free 不會
「無鎖一定比有鎖快?」 否——原子操作與快取乒乓可能拉低整體效能,必須實測
「怎麼確認 std::atomic 真的無鎖?」 呼叫 is_lock_free()(某些平台內部用鎖)