Are these lines in a lock-free queue not necessary?

Here is some code from a lock-free queue using compareAndSet (in Java):

public void enq(T value) {
    Node newNode = new Node(value);
    while(true) {
        Node last = tail.get();
        Node next = last.next.get();

        if(last != tail.get())
            continue;   //???       

        if (next != null) { //improve tail
            tail.compareAndSet(last, next);
            continue;
        }

        if (last.next.compareAndSet(null, newNode)) {   //update last node
            tail.compareAndSet(last, newNode);  //update tail
            return;
        }
    }
}

public T deq() throws EmptyException {
    while(true) {
        Node first = head.get();
        Node last = tail.get();
        Node next = first.next.get();

        if(first != head.get())
            continue;   //???

        if(first == last) {
            if (next == null)
                throw new EmptyException();

            tail.compareAndSet(last, next);
            continue;
        }

        T value = next.value;
        if (head.compareAnsdSet(first, next)) {
            return value;
        }
    }
}

(head and tail are the members of the queue)

In both the deq and enq function, the first check seems unnecessary to me. (The ones commented with "???") I suspect it's there just for some kind of optimization.

Am I missing something here? Do these checks affect the correctness of the code?

(The code is taken from the "Art of Multi-processor Programming", though I did refactor the code style to have less nested ifs and elses, while keeping the code equivalent)

7
задан Shiroko 23 March 2011 в 13:22
поделиться