http://15418.courses.cs.cmu.edu/spring2013/article/46 explains ABA in the specific context of a lockfree stack. It uses CAS2 to counter ABA problem.
Java CAS2? I believe AtomicStampedReference is designed for it.
http://tutorials.jenkov.com/java-util-concurrent/atomicstampedreference.html#atomicstampedreference-and-the-a-b-a-problem explains the AtomicStampedReference solving the ABA problem
Actually, many ABA illustrations are simplistic. Consider this illustration:
- Thread 0 begins a POP and sees “A” as the top, followed by “B”. Thread saves “A” and “B” before committing.
- Thread 1 begins and completes a POP , returning “A”.
- Thread 1 begins and completes a push of “D”.
- Thread 1 pushes “A” back onto the stack and completes. So now the actual stack top has A above D above B.
- Thread 0 sees that “A” is on top and returns “A”, setting the new top to “B”.
- Node D is lost.
— With a vector-of-pointer implementation, Thread 0 needs to save integer position within the stack. At Step 5, it should then notice the A sitting at stack top is now at a higher position than before, and avoid ABA.
The rest is simple. Thread 0 should then query the new item (D) below A. Lastly, the CAS would compare current stack top position with the saved position, before committing.
However, in reality I think a vector-of-ptr is extremely complex to implement if we have two shared mutable things to update via CAS: 1) the stackTopPosition integer and 2) the (null) ptr in the next slot of the vector.
— with a linked list implementation, I think we only have the node addresses, so at Step 5, Thread 0 can’t tell that D has been inserted between A and B.
You may consider using stack size as a second check, but it would be similar complexity as CAS2 but less reliable.