首先声明，本文是伪源码阐明。主要是基于状态机本身实现一个简化的并刊行列，有助于读者把握并发措施设计的焦点——状态机；最后对源码实现略有提及。

ConcurrentLinkedQueue不支持阻塞，没有BlockingQueue那么易用；但在中等局限的并发场景下，其机能却比BlockingQueue高不少，并且相当不变。同时，ConcurrentLinkedQueue是进修CAS的经典案例。按照github的code results排名，ConcurrentLinkedQueue（164k）也十分风行，比我想象中的利用量大多了。很是值得一讲。

对付状态机和并发措施设计的根基领略，可以参考源码|并发一枝花之BlockingQueue，发起第一次打仗状态机的同学速读参考文章之后，再来阅读此文章。

JDK版本：oracle java 1.8.0_102

筹备常识：CAS

读者可以跳过这部门，后头讲到offer()要领的实现时再回首。

灰心锁与乐观锁

灰心锁：假定并发情况是灰心的，假如产生并发斗嘴，就会粉碎一致性，所以要通过独有锁彻底克制斗嘴产生。有一个经典比喻，“假如你不锁门，那么作怪鬼就回冲入并搞得一团糟”，所以“你只能一次打开门放进一小我私家，才气时刻盯紧他”。
乐观锁：假定并发情况是乐观的，即，固然会有并发斗嘴，但斗嘴可发明且不会造成损害，所以，可以不加任何掩护，等发明并发斗嘴后再抉择放弃操纵照旧重试。可类比的比喻为，“假如你不锁门，那么固然作怪鬼会冲入，但他们一旦规划粉碎你就能知道”，所以“你大可以放进所有人，等发明他们想粉碎的时候再做抉择”。

凡是认为乐观锁的机能比灰心所更高，出格是在某些巨大的场景。这主要由于灰心锁在加锁的同时，也会把某些不会造成粉碎的操纵掩护起来；而乐观锁的竞争则只产生在最小的并发斗嘴处，假如用灰心锁来领略，就是“锁的粒度最小”。但乐观锁的设计往往较量巨大，因此，巨大场景下照旧多用灰心锁。

首先担保正确性，有须要的话，再去追求机能。

CAS

乐观锁的实现往往需要硬件的支持，大都处理惩罚器都都实现了一个CAS指令，实现“Compare And Swap”的语义（这里的swap是“换入”，也就是set），组成了根基的乐观锁。

CAS包括3个操纵数：

当且仅当位置V的值便是A时，CAS才会通过原子方法用新值B来更新位置V的值；不然不会执行任何操纵。无论位置V的值是否便是A，都将返回V原有的值。

一个有意思的事实是，“利用CAS节制并发”与“利用乐观锁”并不等价。CAS只是一种手段，既可以实现乐观锁，也可以实现灰心锁。乐观、灰心只是一种并发节制的计策。下文将别离用CAS实现灰心锁和乐观锁？
我们先不讲JDK提供的实现，用状态机模子来阐明一下，看我们能不能本身实现一版。

行列的状态机模子

状态机模子与是否需要并发无关，一个类不管是否是线程安详的，其状态机模子从类被实现（此时，所有类行为都是确定的）开始就是确定的。接口是类行为的一个子集，我们从接口出发，逐渐构建出简化版ConcurrentLinkedQueue的状态机模子。

行列接口

ConcurrentLinkedQueue实现了Queue接口：

public interface BlockingQueue<E> extends Queue<E> {
  boolean add(E e);
  boolean offer(E e);
  E remove();
  E poll();
  E element();

  E peek();
}

需要存眷的是一对要领：

同时，抱负的线程安详行列中，入队和出队之间不该该存在竞争，这样入队的状态机模子和出队的状态机模子可以完全解耦，昆山软件开发，互不影响。

对我们的状态机作出两个假设：

从而，可以先阐明入队，再参照阐明出队；然后可实验去掉假设2，看如何完善我们的实现来担保假设2创立；最后看看真·神Doug Lea如何实现，进修一波。

状态机界说

此刻基于假设1和假设2，实验界说入队模子的状态机。

我们结构一个简化的场景：存在2个出产者P1、P2，同时触发入队操纵。

状态集

假如是单线程情况，入队操纵将是这样的：

3
4
5
6
7
8
9
10
11
12
13
14
// 筹备
newNode.next = null;
curTail = tail;
// 入队前
assert tail == curTail && tail.next == null; // 状态S1
// 开始入队
tail.next = newNode; // 事件E1
// 入队中
assert tail == curTail && tail.next == newNode; // 状态S2
tail = tail.next; // 事件E2
// 竣事入队
// 入队后
assert tail == newNode && tail.next == null; // 状态S3，归并到状态S1