ABA in lock free algorithms

Question

I understand the ABA problem. But the thing which I am unable to comprehend is: they say that in languages having automatic garbage collection it may not exhibit. So my questions are:

• How automatic garbage collection prevents ABA problem in happening?
• Is it possible in java and if yes, how?
• Is it possible to prevent this from happening?

Answer 1

• When automatic garbage collection is enabled ,no two objects can be allocated with the same reference and co-exist at the same time,that's because as long as there is a reference count greater then 0 the reference itself will not be released and re-used.

  so you cannot "switch" the reference contents to "point" for different object while someone still has the old reference.

Answer 2

The ABA problem is orthogonal to garbage collection. For instance, applications can move objects from a linked list to a free list and then reuse them back right away. Therefore the object is never actually released before it is re-used. With that said, the ABA problem can happen in this way:

Thread1:
    prevHead = head;

Thread2:
    prevHead = head;
    newHead = getFromFreeList();
    if (cas(&head, prevHead, newHead)) addToFreeList(prevHead);

Thread3:
    prevHead = head;
    newHead = getFromFreeList(); // Get the same object 'released' by Thread2
    cas(&head, prevHead, newHead) // succeeds and put back what was removed by Thread2

Thread1:
    newHead = getFromFreeList();
    if (cas(&head, prevHead, newHead)) addToFreeList(prevHead);
    // CAS will succeed although it shouldn't since there were
    // a modification on the head done by 'Thread3' in between.

Answer 3

How automatic garbage collection prevents ABA problem in happening? See the "The Art of Multiprocessor Programming" by Herlihy Shavit. Quote: It (the ABA Problem) shows up often, especially in dynamic memory algorithm.

So of course the ABA Problem can appear in Java, but since in most of the cases the problem appears in dynamic memory algorithm and you do not implement such algorithm in java very often, you won't see this error in java very often.

Is it possible in java and if yes, how? The Book "The Art of Multiprocessor Programming" gives an example in java for this Problem related to memory reclamation for a lock free concurrent queue.

Is it possible to prevent this from happening? Quote: Avoid ABA by testing not wether a value is the same at two points in time, but wether the value has ever changed between those points. One way to do this is to use AtomicStampedReference

Answer 4

In the book "The Art of Multiprocessor Programming", the authors discuss situations in which programmers may want to implement their own pool of resources (e.g., a pool of list nodes) in Java. Then, programmers directly managing the pool circumvent garbage collection, which improves performance. Nonetheless, caution must be taken to avoid the ABA problem.

Here is the core of the Java code for memory management in Java:

ThreadLocal<Node> freeList = new ThreadLocal<Node>() {
    protected Node initialValue() { return null; };
};

The full code of LockFreeQueueRecycle.java is available here:

http://booksite.elsevier.com/9780123705914/exercises/07~Chapter_10.zip

See slides and code for chapter 10 at:

http://booksite.elsevier.com/9780123705914/?ISBN=9780123705914