Concurrent linked queue use CAS

Question

I found this code segment about concurrent linked queue in IBM Developer.

But I can't understand a part of them. Which is

while(true){
    ...
    if(curTail == Tail.get()){
        if(residue == null){
            ...
        }
    }
}

According to the define of curTail and residue, I think curTail is a copy of Tail and curTail is a pointer equals Tail.next .

I concern that function compareAndSet will judge if the caller object is equal to the first param, why must judge them before call this function? I think the code below can so the same thing well.

        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
                if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                    tail.compareAndSet(curTail, newNode) /* D */ ;
                    return true;
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }

Any help would be appreciated. Thanks.

public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;
        Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }
    private AtomicReference<Node<E>> head
        = new AtomicReference<Node<E>>(new Node<E>(null, null));
    private AtomicReference<Node<E>> tail = head;
    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> residue = curTail.next.get();
            if (curTail == tail.get()) {
                if (residue == null) /* A */ {
                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {
                        tail.compareAndSet(curTail, newNode) /* D */ ;
                        return true;
                    }
                } else {
                    tail.compareAndSet(curTail, residue) /* B */;
                }
            }
        }
    }
}

I guess the code try to avoid calling "compareAndSet" as possible. Probably it cost more... some link I found https://stackoverflow.com/questions/4183202/java-compare-and-swap-semantics-and-performance and https://stackoverflow.com/questions/4187914/average-latency-of-atomics-cmpxchg-instructions-on-intel-cpus — Surely, Dec 25 '18 at 13:44
@Surely Thanks for your tips. I just focus the logic of the code but neglect the cost of CAS....... — Y.L, Dec 26 '18 at 02:56
I am not quite sure whether it is the case though. Waiting for someone who is better at this topic to answer. — Surely, Dec 26 '18 at 04:19

score 2 · Accepted Answer · answered Dec 29 '18 at 21:36

For reference: example, code explanations of the algorithm are available on this page from the IBM Developer website.

The page linked above will give you the purposes of each operation A, B, C and D, and why they are required to allow what is referenced therein as constructive interference between threads concurrently updating the tail of the queue.

Your change corrupts the algorithm. The else clause must not be executed when C is unsuccessful. The role it plays instead is to reproduce the operation D when a thread intercepts an uncompleted [*] update of the tail from another thread.

[*]: That is, after C but before D.

To understand why and when it fails, consider the following scenario.

while (true) {
   Node<E> curTail = tail.get();
   Node<E> residue = curTail.next.get();

   /* (i) */

   if (curTail.next.compareAndSet(null, newNode)) /* C */ {
     tail.compareAndSet(curTail, newNode) /* D */ ;
     return true;
   } else {
      tail.compareAndSet(curTail, residue) /* B */;
   }
}

Two threads T1 and T2 start simultaneously at position (i). Their stack holds the same references for curTail and residue. residue is supposed null (i.e. the queue is supposed to be in quiescent state).
T1 completes the first CAS C successfully. It does not execute D yet.
T2 fails the CAS C, enters the else, executes CAS B successfully, since the reference tail hasn't changed.
T1 fails the CAS D, since the reference assigned to tail has been set to null by C. There is no fallback, and the method exits. Element from T2 is not inserted.
Second attempt for T1, the reference assigned to tail is null and curTail.next throws a NullPointerException. The data structure is corrupted.

To summarize, A and B works in pairs. They exist to ensure interfering threads can help the convergence of the queue to a normal state and recover from a queue left in an intermediate state. Imagine a thread executes C but gets killed before having a chance to run D. Without A and B, the queue would be forever corrupted. A and B ensures the state can be reconstructed and the unfinished insertion completed.

Yes you are right. Thanks very much for the detailed explain. — Y.L, Dec 31 '19 at 09:29

Concurrent linked queue use CAS

1 Answers1