Lock-free 中的 ABA 問題

文章內容來自：https://woboq.com/blog/introduction-to-lockfree-programming.html

這兒僅作翻譯。

The ABA problem

此例中，執行緒 1 要拿出一個節點。它取得 A 的位址並且做 testAndSet 來將 head 由 A 變成 B。但這時 OS 排程將它在要做 atomic 操作時踢出去，換另個執行緒取得執行。

當執行緒 1 在睡覺時，執行緒 2 取出一個節點，故這時 A 並不在 stack 之中。

假如執行緒 1 在這時被喚醒，因為 head 已經不再是 A 了，故其 atomic 操作會失敗。但實際上這只是假如，執行緒 1 並沒有被喚醒，仍是執行緒 2 做事。

這時候執行緒 2 放入一個 C 節點。再一次假如這時候執行緒 1 被喚醒，head 仍然不是 A，不會有問題。但事實是執行緒 1 還沒醒。

接著執行緒 2 將節點 A 放回 stack 中。

這時，執行緒 1 終於醒了，然後 testAndSet 過了（因為 A 是 head 了），這時候它將 stack head 改成 B。於是 C 就被漏掉了。如果執行緒 2 曾經拿出 B 過，情況會更糟。

解法有不少種，呃…大家自己查吧。