java - 并发链接队列使用CAS

Question

我在 IBM Developer 中找到了这段关于并发链接队列的代码段。

但我听不懂其中的一部分。哪个是

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

---

根据 curTail 和 residue 的定义，我认为 curTail 是 Tail 的副本，curTail 是一个等于 Tail.next 的指针。

我担心函数compareAndSet会判断调用者对象是否等于第一个参数，为什么必须在调用这个函数之前判断它们？我认为下面的代码可以很好地完成同样的事情。

        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 */;
                }
            }
        }

如有任何帮助，我们将不胜感激。谢谢。

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 */;
                }
            }
        }
    }
}

Answer 1

供引用:例如，算法的代码解释可以在this page from the IBM Developer website上找到.

上面链接的页面将为您提供每个操作的目的 A、B、C 和 D ，以及为什么它们需要允许在线程之间同时更新队列尾部的建设性干扰。

您的更改破坏了算法。当 C 不成功时，else 子句必须不执行。它所扮演的角色是当一个线程截获另一个线程未完成的尾部更新时重现操作D。

[*]:即在C之后但在D之前。

要了解失败的原因和时间，请考虑以下场景。

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 */;
   }
}

• 两个线程T1 和T2 同时从位置(i) 开始。它们的堆栈包含对 curTail 和 residue 的相同引用。 residue 应该是 null(即队列应该处于静止状态)。

• T1 成功完成第一个 CAS C。它还没有执行D。

• T2 使 CAS C 失败，进入 else，成功执行 CAS B，因为引用 tail 没有改变。

• T1 未能通过 CAS D，因为分配给 tail 的引用已设置为 null C。没有回退，方法退出。未插入来自 T2 的元素。

• 第二次尝试 T1，分配给 tail 的引用是 null 和 curTail.next抛出一个 NullPointerException。数据结构已损坏。

总而言之，A 和B 成对工作。它们的存在是为了确保干扰线程可以帮助队列收敛到正常状态，并从处于中间状态的队列中恢复。想象一个线程执行 C 但在有机会运行 D 之前被杀死。没有 A 和 B，队列将永远损坏。 A 和B 确保状态可以被重构，未完成的插入完成。