ConcurrentLinkedQueue

我们要实现一个线程安全的队列有两种实现方式，阻塞算法、非阻塞算法。使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）

或两个锁（入队和出队用不同的锁）等方式来实现，而非阻塞的实现方式则可以使用循环CAS的方式来实现，本节我们就来研究下

ConcurrentLinkedQueue是如何保证线程安全的同时又能高效的操作的。

一.ConcurrentLinkedQueue

当前常用的多线程同步机制可以分为下面三种类型：

所以要在多线程中安全使用volatile，必须同时满足

1、对变量的写入操作不依赖其当前值（不满足：number++、count=count*5等，满足：boolean变量、记录温度变化的变量等）；

2、该变量没有包含在具有其他变量的不变式中（不满足：不变式low < up）

ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，

它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。基于CAS的“wait－free”（无等待）来实现，CAS并不是一个

算法，它是一个CPU直接支持的硬件指令，这也就在一定程度上决定了它的平台相关性。

ConcurrentLinkedQueue 的非阻塞算法实现主要可概括为下面几点：

这个特性把入队 /出队时，原本需要一起原子化执行的两个步骤分离开来，从而缩小了入队 /出队时需要原子化更新值的范围到唯一变量。这是非阻塞算法得以实现的关键。

Iterators are weakly consistent, returning elements reflecting the state of the queue at some point at or since the creation of the iterator.

They do not throw ConcurrentModificationException, and may proceed concurrently with other operations. Elements contained in the

queue since the creation of the iterator will be returned exactly once.

Beware that, unlike in most collections, the size method is NOT a constant-time operation. Because of the asynchronous nature of these

queues, determining the current number of elements requires a traversal of the elements, and so may report inaccurate results if this collection

is modified during traversal. Additionally, the bulk operations addAll, removeAll, retainAll, containsAll, equals, and toArray are not

guaranteed to be performed atomically. For example, an iterator operating concurrently with an addAll operation might view only some of

the added elements.