Java多线程总结之线程安全队列Queue - JAVA

dSet(curTail, newNode) /* D */ ;return true;}} else {tail.compareAndSet(curTail, residue) /* B */;}}}}}
看看这代码完全就是ConcurrentLinkedQueue 源码啊。
插入一个元素涉及头指针和尾指针两个指针更新，这两个更新都是通过 CAS 进行的：从队列当前的最后节点（C）链接到新节点，并把尾指针移动到新的最后一个节点（D）。如果第一步失败，那么队列的状态不变，插入线程会继续重试，直到成功。一旦操作成功，插入被当成生效，其他线程就可以看到修改。还需要把尾指针移动到新节点的位置上，但是这项工作可以看成是 “清理工作”，因为任何处在这种情况下的线程都可以判断出是否需要这种清理，也知道如何进行清理。

队列总是处于两种状态之一：正常状态（或称静止状态，图 1 和图 3）或中间状态（图 2）。在插入操作之前和第二个 CAS（D）成功之后，队列处在静止状态；在第一个 CAS（C）成功之后，队列处在中间状态。在静止状态时，尾指针指向的链接节点的 next 字段总为 null，而在中间状态时，这个字段为非 null。任何线程通过比较 tail.next 是否为 null，就可以判断出队列的状态，这是让线程可以帮助其他线程 “完成” 操作的关键。

Java多线程总结之线程安全队列Queue - 火木棉 - 淡泊明智

上图显示的是：有两个元素，处在静止状态的队列

插入操作在插入新元素（A）之前，先检查队列是否处在中间状态。如果是在中间状态，那么肯定有其他线程已经处在元素插入的中途，在步骤（C）和（D）之间。不必等候其他线程完成，当前线程就可以 “帮助” 它完成操作，把尾指针向前移动（B）。如果有必要，它还会继续检查尾指针并向前移动指针，直到队列处于静止状态，这时它就可以开始自己的插入了。
第一个 CAS（C）可能因为两个线程竞争访问队列当前的最后一个元素而失败；在这种情况下，没有发生修改，失去 CAS 的线程会重新装入尾指针并再次尝试。如果第二个 CAS（D）失败，插入线程不需要重试 ―― 因为其他线程已经在步骤（B）中替它完成了这个操作！

Java多线程总结之线程安全队列Queue - 火木棉 - 淡泊明智

上图显示的是：处在插入中间状态的队列，在新元素插入之后，尾指针更新之前

Java多线程总结之线程安全队列Queue - 火木棉 - 淡泊明智

上图显示的是：在尾指针更新后，队列重新处在静止状态

Java多线程总结之线程安全队列Queue(四)