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

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.

Answer 2

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

Answer 3

S Kr Here is an explanation. Take a stack which looks like this.. top -> A -> B -> C.
Take two threads, Th1 and Th2. They are using non blocking compare and set (CAS) for pop operations.
Th1: set return = A, next = B.. but gets moved out of running state
Th2:
- pop A: return = A, next = B, CAS(A, B).. so now top = B
- pop B: return = B, next = C, CAS(B, C).. so now top = C
- push A (same oblect as earlier satisfying ==, because lets say it was cached somewhere): .. so now top is A, and stack looks like this.. top -> A -> C
Th1: back in action.. and resumes.. CAS(A, B).. this succeeds!! Stack now looks like this.. top -> B -> C.. but.. but.. B was already removed from stack by thread 2 and it magically comes back! Bad.
Moral of story: use AtomicStampedReference. AtomicMarkableReference is a special case of AtomicStampedReference.

Bonus: think of a sorted linked list, and multiple threads working on it. Try to insert C in A -> B -> D -> E, and figure out a similar ABA problem.