通用面試：什麼是 CAS 的 ABA 問題，如何避免？

題幹與適用場景

CAS 會在共享位置仍等於預期值時原子寫入新值。ABA 發生在：執行緒 T1 讀到 A 後暫停，T2 把 A 改成 B 又改回 A，T1 只比較目前值仍是 A，因此 CAS 成功，卻不知道中間發生過狀態變化。

無鎖堆疊、無鎖佇列與樂觀更新都可能遇到此問題。Oracle 的 AtomicReference.compareAndSet 按參照相等判斷，AtomicStampedReference 則把參照與整數 stamp 一起原子比較；C++ 的 compare_exchange 也是無鎖結構常用的基本原語。核心分類是 general，考察並發原理與取捨，不因示例使用 Java 或 C++ 改成語言分類。

面試官考察點

• 能否用明確時序說明「值回到 A」不等於「狀態沒有改變」。
• 能否解釋 CAS 只比較收到的預期表示，不會自動驗證完整歷史。
• 能否區分 ABA、資料競爭、記憶體可見性與物件生命週期問題。
• 能否比較版本戳、不可變物件、hazard pointer/epoch reclamation 與鎖的邊界。
• 能否說明修復方案的溢位、成本、回收與進度保證。

回答前需要釐清的問題

• CAS 比較的是值、參照還是帶版本的複合狀態？不同表示決定能否觀察變化。
• 共享物件是否會被回收或重用位址？ABA 與記憶體回收通常要一起討論。
• 目標是 lock-free 還是只要正確？加鎖可能更簡單、易審查。
• 版本戳是否可能溢位？若會，需定義足夠寬的計數器或回繞策略。
• 是否需要回傳具體節點、維護順序或只更新一個標量？風險範圍不同。
• 採用哪種記憶體模型？原子性不自動等於欄位發布與生命週期安全。

30 秒回答框架

「ABA 是 T1 看到 A 後暫停，T2 完成 A→B→A，T1 再用舊預期 A 做 CAS 並成功。CAS 證明目前表示仍匹配，不證明期間沒有改變。修復通常把版本戳與參照組成原子狀態，每次修改遞增戳；也可以用安全記憶體回收避免節點位址過早重用，或直接加鎖。我會先確認物件生命週期、進度目標與版本溢位，再選擇 AtomicStampedReference、帶標籤指標或鎖。」

分步驟深入解答

第一步：用無鎖堆疊還原時序。

堆疊頂端從 A -> B。T1 讀取 head = A 與 A.next，準備把 head CAS 成 A.next。T1 暫停後，T2 彈出 A、處理 B，再把同一個 A 或重用位址的節點壓回頂端。此時 head 表示又是 A，T1 的 CAS 可能成功，卻寫入來自舊快照的 next。

第二步：指出錯誤不在 CAS 原子性。

CAS 本身是原子的；問題是預期值攜帶的資訊太少。它比較參照或標量目前表示，沒有比較「這個表示經歷幾次修改」或節點是否仍屬於同一邏輯狀態。

第三步：區分相關概念。

資料競爭是未同步存取造成的語言層錯誤；ABA 可以在 CAS 原子且沒有資料競爭時發生。可見性決定執行緒讀到什麼，ABA 關注讀到的值雖相同但歷史不同。物件回收則決定舊指標能否安全解參照。

第四步：使用參照加版本戳。

state = (reference: A, stamp: 7)
T1 reads (A, 7)
T2 changes (A, 7) -> (B, 8) -> (A, 9)
T1 CAS expected (A, 7) -> (C, 8)  // fails

Java 的 AtomicStampedReference.compareAndSet 會同時比較 reference 與 stamp；C++ 可用雙寬原子、指標低位標籤或平台支援的複合 CAS，但必須確認平台真的提供所需原子性。

第五步：處理生命週期與位址重用。

版本戳只能發現表示變化，不能自動讓節點安全回收。非 GC 語言還需 hazard pointer、epoch-based reclamation、參照計數或延遲回收，確保執行緒不會解參照已釋放節點。GC 語言也要確認物件參照不會錯誤重用成同一邏輯狀態。

第六步：評估版本溢位。

有限寬度 stamp 最終會回繞。若執行緒長時間持有舊快照，回繞後仍可能再次匹配；需要足夠寬的版本、限制快照壽命、使用不會重用的代數，或採用更強同步。不能把「加一個 int」當成無條件證明。

第七步：比較替代方案。

加鎖把複合讀取、修改與生命週期放在同一臨界區，通常更簡單；不可變資料結構用新物件表達新狀態，降低原地修改風險；交易或資料庫版本欄位則在持久化層提供類似樂觀版本檢查。選擇依競爭度、延遲、複雜度與可審計性。

第八步：驗證並發正確性。

構造可控測試暫停 T1，再讓 T2 執行 A→B→A，確認無戳 CAS 錯誤成功、有戳 CAS 失敗。再測高並發、stamp 回繞邊界、節點回收與 CAS 重試。單執行緒測試不能證明無鎖演算法正確。

高品質示範回答

「ABA 是狀態變化被值比較隱藏的情況。T1 讀到堆疊頂端 A 並暫停；T2 把 A 彈出、完成 A→B→A，再把 A 放回；T1 只看到目前仍是 A，於是 CAS 成功，卻可能用舊 next 覆蓋新結構。CAS 原子性沒有失效，失效的是預期表示缺少版本資訊。我會把參照與單調 stamp 組成原子狀態，每次修改都遞增 stamp；Java 可用 AtomicStampedReference，C++ 則確認雙寬 CAS 或標籤指標的實際支援。同時，非 GC 環境必須配合 hazard pointer 或 epoch 回收。若競爭不高或正確性優先，我會選擇加鎖，並用強制 A→B→A 時序和回收壓力測試驗證。」

常見錯誤

• 說 ABA 是 CAS 不原子 → 誤解原語保證 → 指出比較表示缺少歷史資訊。
• 只比較節點值 → 不同版本可能值相同 → 比較參照加版本戳。
• 只加 stamp 不談回收 → 仍可能解參照已釋放節點 → 補充生命週期方案。
• 把資料競爭等同 ABA → 混淆記憶體模型與演算法缺陷 → 分別定義並說明關係。
• 忽略 stamp 溢位 → 長時間執行仍有匹配窗口 → 定義寬度、壽命或回繞策略。
• 宣稱 Java/C++ API 自動解決所有問題 → API 只提供原子比較 → 說明複合狀態與回收邊界。
• 給出不可移植的指標位元技巧 → 平台對齊或原子寬度可能不滿足 → 先核對目標平台。
• 只做單執行緒測試 → 無法觸發 ABA 時序 → 加入可控暫停與並發壓力。

追問及應對

追問一：T2 把 A 改成 B 再改回 A，為什麼 CAS 還會成功？

因為普通 CAS 只比較目前預期表示。若表示只是參照 A 或數值 A，目前相等就滿足條件；它不會自動記錄中間的 B。

追問二：版本戳一定能解決 ABA 嗎？

在版本未回繞且參照與 stamp 原子更新的前提下，它能檢測 A→B→A。若 stamp 溢位、複合更新不原子或節點已釋放，仍需額外設計。

追問三：AtomicReference 與 AtomicStampedReference 有何差別？

前者原子比較參照並更新參照；後者把參照與整數 stamp 作為一對狀態，同時比較與更新。後者增加封裝與 stamp 管理成本，換取版本變化檢測。

追問四：為什麼不可變節點有幫助？

不可變節點不會原地改變 next 或業務欄位，新狀態用新物件表達，降低舊快照與新狀態共享可變內容的機會。但節點回收與參照重用仍需處理。

追問五：hazard pointer 解決 ABA 還是回收？

它主要保護執行緒正在讀取的節點不被回收。若位址重用仍可能讓同一指標表示不同邏輯節點，仍需版本、標籤或其他 ABA 防護。

追問六：為什麼不總是加鎖？

加鎖通常最容易證明與維護，但可能帶來阻塞、優先權反轉或競爭延遲。低競爭、重視可維護性的場景優先加鎖；只有明確需要無鎖進度或極低延遲時才承擔複雜度。

追問七：如何證明無鎖堆疊的修復正確？

定義堆疊頂端複合狀態、CAS 線性化點、節點生命週期與不變量；用 A→B→A 排程、CAS 失敗重試、stamp 邊界與回收壓力測試驗證，再結合目標語言記憶體模型審查發布與取得順序。