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.