ABA 問題（ABA problem）

ABA 問題是一個會咬到天真無鎖程式碼的狡猾臭蟲。比較並交換的運作方式是檢查「這個值還是我上次看到的那個嗎？」，是才提交。沒明說的假設是：若值沒變，那期間就沒發生什麼要緊的事。ABA 問題正是這個假設不成立的情況：你讀到時值是 A，另一個執行緒把它改成 B 又改回 A，等你的 CAS 來檢查時看到 A，便高高興興地成功——儘管你腳下的世界其實真的變了。

以下是無鎖堆疊上經典的具體失敗。執行緒 1 讀取頂端節點、記住它是節點 A，打算把它彈出（把 top 設成 A 的後繼）。在執行緒 1 的 CAS 執行前，執行緒 2 彈出 A、彈出下一個節點，然後又把 A 推回頂端——可能重用了 A 被釋放的記憶體，而關鍵在於這個節點此刻位於一個不同的後繼之上。執行緒 1 醒來，它的 CAS 檢查「top 還是 A 嗎？」——是的——於是 CAS 成功，把 top 設成執行緒 1 記得的那個後繼，而那個後繼如今已過時或已被釋放。堆疊被破壞了。指標值相符，但它所指向的結構已被重建。

標準的解法全都加上資訊，使「A 然後又是 A」變得可區分。標記指標（或版本計數器）把一個單調遞增的計數器與指標打包在一起、用 CAS 同時換兩者，於是即使指標回到 A，計數器也已前進，CAS 便正確地失敗——這就是雙倍寬度的比較並交換，或某些 CPU 上的載入連結／條件儲存指令，只要該位置被寫過就失敗。安全的記憶體回收方案（危害指標、基於紀元的回收）則防止重用記憶體的那種變體，做法是確保一個節點不會在還有別的執行緒可能仍引用它時被釋放並回收。教訓令人謙卑：在無鎖程式碼裡，一個值相等，不等於「什麼都沒變」，而忘了這點，是最常見、也最難重現的並行臭蟲之一。