Usecase of using AtomicStampedReference & AtomicMarkableReference

Question

I am looking for a example of AtomicStampedReference and/or AtomicMarkableReference, that could help me understand these classes and their functions.

I am not able to get any quality examples over the web.

I can think of using these in garbage collection, but a quality example will help me understand these better.

Answer 1

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