http://15418.courses.cs.cmu.edu/spring2013/article/46 explains ABA in the specific context of a … lockfree stack. To counter ABA problem, It uses CAS2 i.e. CAS on a group of two objects — the original object + a stamp.
Java CAS2? I believe AtomicStampedReference is designed specifically 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 but in the last section it doesn’t clearly explain the benefit of get().
Also, the retry need a loop.
The stamp is a plain old integer. The all-important “Increment Control” is not by some sophisticated magic inside the library, but by your own hand-written logic.
====Actually, many ABA illustrations are simplistic. Consider this typically simplistic illustration of a CAS stack:
- Thread 0 begins a POP and sees “A” as the top, followed by “B”. Thread saves “A” and “B”, before committing anything.
- Thread 1 begins and completes a POP , returning “A”.
- Thread 1 begins and completes a Push of “D”.
- Thread 1 begins and completes a Push of the same “A”. So now the actual stack top has A above D above B, i.e. with D inserted just below the original top-dog “A”
- Thread 0 sees that “A” is “still” on top and returns “A”, setting the new top to “B”. Therefore, 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 detect that the A sitting at stack top is now at a higher position than observed earlier, detecting a symptom of 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 non-trivial to implement if we have two shared mutable things to update via CAS: 1) the stackTopPosition integer variable and 2) the (null) ptr in the next slot of the vector.
However, if Thread 1 replaces B with D, keeping the stack size unchanged, then the ABA would be undetectable by position check alone.
— with a linked list implementation, I think we only have 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.