無鎖資料結構（lock-free data structure）

無鎖資料結構讓許多執行緒在不使用鎖的情況下並行地讀取與修改它。它不說「等你的輪次，鎖在我手上」，而是每個執行緒樂觀地做完自己的工作，再用一個原子的比較並交換把它提交；若別的執行緒搶先一步，它就帶著新的現實單純地重試。背後的顧慮是：鎖可能成為瓶頸或隱患——持鎖時被暫停（或當掉）的執行緒會無限期擋住其他所有人，而在繁忙的結構上，執行緒把時間花在排隊而非工作。無鎖設計藉由根本不彼此阻塞來迴避這點。

「無鎖」有精確的技術涵義，不只是「沒有鎖」：它是一種進展保證。一個結構若是無鎖的，意思是：每當多個執行緒在它上面操作時，其中至少有一個總能在有限步數內取得進展——整個系統永不停滯，即使某些個別執行緒被反覆迫使重試。這完全排除了死結（根本沒有鎖可持有），也排除了一個卡住的執行緒凍結所有人的情況。標準的基本構件是比較並交換的重試迴圈：讀取目前狀態、算出你想要的新狀態、再用 CAS 把改動換進去；若 CAS 因別的執行緒在此期間改了狀態而失敗，就重新從剛觀察到的狀態再試一次。例如無鎖堆疊的推入，就是用 CAS 把 head 指標從舊的頂端換成新節點。

誠實的現實是：無鎖程式碼困難，且很容易出現難以察覺的錯誤。重試迴圈必須精心設計，且容易遭遇 ABA 問題——一個值從 A 變成 B 又變回 A，天真的 CAS 便誤以為什麼都沒發生。安全地回收記憶體（知道何時不再有執行緒可能仍在讀取你想釋放的節點）是出了名的難題，靠危害指標（hazard pointers）或基於紀元的回收等技術解決。無鎖並不自動比一把好鎖快——在低競爭下，單純的互斥鎖往往勝出——而且它不保證任何個別執行緒會完成（那個更強的承諾叫免等待）。在競爭真正激烈、或你無法容忍一個執行緒被另一個持鎖者擋住之處才使用它。