ConcurrentLinkedQueue代码解释

Question

http://www.java2s.com/Open-Source/Java-Open-Source-Library/7-JDK/java/java/util/concurrent/ConcurrentLinkedQueue.java.htm

上面是ConcurrentLinkedQueue的源代码。 我不理解下面这个条件。 在offer方法中，如何出现条件(p == q)的情况。

  public boolean offer(E e) {
        checkNotNull(e);
        final Node<E> newNode = new Node<E>(e);

        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p is last node
                if (p.casNext(null, newNode)) {
                    // Successful CAS is the linearization point
                    // for e to become an element of this queue,
                    // and for newNode to become "live".
                    if (p != t) // hop two nodes at a time
                        casTail(t, newNode);  // Failure is OK.
                    return true;
                }
                // Lost CAS race to another thread; re-read next
            }
            else if (p == q)
                // We have fallen off list.  If tail is unchanged, it
                // will also be off-list, in which case we need to
                // jump to head, from which all live nodes are always
                // reachable.  Else the new tail is a better bet.
                p = (t != (t = tail)) ? t : head;
            else
                // Check for tail updates after two hops.
                p = (p != t && t != (t = tail)) ? t : q;
        }
    }

同时，作者在说"我们已经掉出了名单"时是什么意思？

- veritas

Answer 1

ConcurrentLinkedQueue允许在遍历内部列表时进行并发修改。这意味着你正在查看的节点可能已经被同时删除了。为了检测这种情况，已删除节点的下一个指针被更改为指向自身。请参阅updateHead（L302）获取详细信息。

- Holger

---

@Holger：你能解释一下concurrentlinkedqueue的remove方法是如何工作的吗？因为当我在多线程环境中尝试理解它时，似乎它并没有按照我的预期工作，我可能漏掉了什么。 - Aarish Ramesh

public boolean remove(Object o) { if (o == null) return false; Node<E> pred = null; for (Node<E> p = first(); p != null; p = succ(p)) { E item = p.item; if (item != null && o.equals(item) && p.casItem(item, null)) { Node<E> next = succ(p); if (pred != null && next != null) pred.casNext(p, next); return true; } pred = p; } return false; } - Aarish Ramesh

@Aarish：你说的“似乎不起作用”是什么意思？ - Holger

@Holger 我在纸上尝试了针对并发线程的删除操作，例如像A->B->C->D->E这样的列表，并且线程1删除C，线程2删除D。在这种情况下，如果两个线程切换执行并使用上述代码，则我不会看到B的下一个指向E。在这两种情况下，如果（pred！= null && next！= null），则不会被执行，因为C或D将为空。因此，我想知道在并发修改下如何设置节点的下一个。 - Aarish Ramesh

@Aarish：将项目设置为null并不会将下一个指针设置为null。在这段代码中，下一个指针从未被设置为null。你似乎混淆了项目和节点。 - Holger

Answer 2

这个条件问的问题是“当前节点和下一个节点是否相同？”

如果是，那么你已经跳出了列表（文档中有说明）。

基本步骤概述如下：

1. 为提供的数据创建一个新节点。
2. 遍历列表以找到最后一个节点。
3. 将新节点插入作为新尾部。

if语句的其他部分处理并发修改问题。

要更好地理解正在发生的事情，请阅读Node.casTail()和casNext()。

- lscoughlin

---

该条件询问“当前节点是否与下一个节点相同？”这难道不是主要问题吗？因为使用p.next获取的下一个节点等于p并不是非常明显。 - mawia

这是由于列表的并发修改可能导致的条件之一。 - lscoughlin

@mawia，你还有什么不清楚的地方吗？如果没有，你可以标记一个被接受的答案，或者澄清你认为缺少什么，这样我就可以改进答案了。 - lscoughlin