java.util.concurrent.ConcurrentLinkedQueue 是一个基于链接结点的、无界、线程安全的、FIFO队列。它的是实现采用了无等待（wait-free）、无锁（lock-free）算法，该算法基于 Maged M. Michael 和 Michael L. Scott 合著的 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 中描述的算法。

一、设计思路

1. 使用 CAS 原子指令来处理对数据的并发访问，把同步最小化到单个硬件指令上；这是无锁算法的基础。
2. 分别用 head、tail 两个原子指针来指向队头和队尾，可以同时进行入队和出队操作，但允许 head、tail 并不总是指向有效的头和尾；把入队、出队需要同步更新的范围最小化到单个原子变量上，这是无锁算法实现的关键。
3. 在入队、出队操作上并不总是更新 head、tail，而是在多次操作后才进行更新，节省了CAS指令。具有批量更新的效果。
4. 由于 head、tail 并不总是指向头和尾，这就是说，队列会出现不一致的情况，所以在 head、tail 上定义了一些不变式来维护算法的正确性。

二、不变式

不变式是在执行方法之前和之后，队列必须要保持的。可变式是在执行过程中，队列允许出现的不一致情况。

head 的约束

通过这个结点能够在 O(1) 时间到达第一个存活（非已删除）结点，如果有的话。

不变式

• 所有存活结点可以 从 head 开始通过 succ() 访问。
• head != null。
• (tmp = head).next != tmp || tmp != head，这个不变式是说 head 在方法开始之前、之后，head 指向的结点应该是在队列上的。

可变式

• head.item 可能是、也可能不是 空的。
• 允许 tail 落后于 head，那是因为 tail 不能从 head 到达。

tail 的约束

从它可以在 O(1) 时间访问到队列的最后一个结点（唯一的满足 node.next == null 的结点）。这个也就是说 tail 指向的并不总是最后一个存活结点。

不变式

• 最后的结点总是可以从 tail 开始通过 succ() 访问。
• tail != null。

可变式

• tail.item 可能是、也可能不是空。
• 允许 tail 落后于 head，那是因为 tail 不能从 head 到达。
• tail.next 可能是、也可能不是 自指向到 tail。
  继续阅读 →