Usecase of using AtomicStampedReference & AtomicMarkableReference

AtomicMarkableReference and AtomicStampedReference are used to solve ABA problem:

In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and "value is the same" is used to indicate "nothing has changed". However, another thread can execute between the two reads and change the value, do other work, then change the value back, thus fooling the first thread into thinking "nothing has changed" even though the second thread did work that violates that assumption.

Initially: x = 0
Thread1: read x // sees x = 0
Thread2: x = 1
Thread3: x = 0
Thread1: read x // again sees x = 0, thinking that nothing has changed

To solve the above problem, we can maintain a stamp that should be updated(incremented) whenever a thread changes some state:

Initially: x = 0, stamp = 0
Thread1: read stamp // sees stamp = 0
Thread2: x = 1, stamp = 1
Thread3: x = 0, stamp = 2
Thread1: read stamp,x // sees stamp = 2 which is != 0 hence do some processing

Practical examples (Complicated)

For AtomicMarkableReference:

https://github.com/arunmoezhi/ConcurrentKaryST

For AtomicStampedReference

https://github.com/arunmoezhi/LockFreeBST

Simple example:

In a binary tree if you want to change a child of a parent node atomically, then compareAndSwap on an AtomicMarkableReference can be used.

In a binary tree lets say you want to flag a node atomically. Then AtomicStampedReference can be used.

The above complicated real life implementations use these two class types.