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?

Transcendentalistic

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.

Known

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.

Edelstein

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

Takeshi

Please give the writings from the book here so that everybody can follow. And you can give that url as reference. – Transcendentalistic

@gstackoverflow, not only is "read this book" polite, it's a very powerful and generous answer. It gives you the means to develop your own strength. What a shame that you couldn't appreciate that and behaved with such ingratitude. Now I'd understand if you read the book and it was not good, but even then one must appreciate the spirit to offer not just a brief opinion but an in-depth, authoritative treatment. Read and learn and show some respect, please. – Chrome

@Lew Bloch, If I have not this book I have not another way to get response? If person understand book correct - it can explain theme explained at this vook – Lovato

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

Kaitlin