并发编程之ConcurrentLinkedDeque

ConcurrentLinkedDeque 是双向链表结构的无界并发队列。从JDK 7开始加入到J.U.C的行列中。使用CAS实现并发安全，与 ConcurrentLinkedQueue 的区别是该阻塞队列同时支持FIFO和FILO两种操作方式，即可以从队列的头和尾同时操作(插入/删除)。适合“多生产，多消费”的场景。内存一致性遵循对 ConcurrentLinkedDeque 的插入操作先行发生于(happen-before)访问或移除操作。相较于 ConcurrentLinkedQueue，ConcurrentLinkedDeque 由于是双端队列，所以在操作和概念上会更加复杂，来一起看下。

概述

ConcurrentLinkedDeque（后面称CLD） 的实现方式继承了 ConcurrentLinkedQueue 和 LinkedTransferQueue的思想，在非阻塞算法的实现方面与 ConcurrentLinkedQueue 基本一致。关于 ConcurrentLinkedQueue，请参考笔者的上一篇文章：JUC源码分析-集合篇（三）：ConcurrentLinkedQueue。

数据结构

ConcurrentLinkedDeque 继承关系

重要属性：

和ConcurrentLinkedQueue一样，CLD 内部也只维护了和属性，对 head/tail 节点也使用了“不变性”和“可变性”约束，不过跟 ConcurrentLinkedQueue 有些许差异，我们来看一下：

head/tail 的不变性：

第一个节点总是能以O(1)的时间复杂度从 head 通过 prev 链接到达；

最后一个节点总是能以O(1)的时间复杂度从 tail 通过 next 链接到达；

所有live节点（item不为null的节点），都能从第一个节点通过调用 succ() 方法遍历可达；

所有live节点（item不为null的节点），都能从最后一个节点通过调用 pred() 方法遍历可达；

head/tail 不能为 null；

head节点的 next 域不能引用到自身；

head/tail 不会是GC-unlinked节点（但它可能是unlink节点）。

head/tail的可变性：

head/tail 节点的 item 域可能为 null，也可能不为 null；

head/tail 节点可能从first/last/tail/head 节点访问时不可达；

tail节点的 next 域可以引用到自身。

注：CLD中也对 head/tail 的更新也使用了“松弛阀值”的概念（在 ConcurrentLinkedQueue 一篇中已经分析），除此之外，CLD设定了一个“跳跃阀值”-HOPS（指在查找活动节点时跳过的已删除节点数），在执行出队操作时，跳跃节点数大于2或者操作的节点不是 first/last 节点时才会更新链表（后面源码中详细分析）。

除此之外，再来看看CLD中另外两个属性：

PREV_TERMINATOR：prev的终止节点，next指向自身，即。在 first 节点出列后，会把first.next指向自身()，然后把prev设为。

NEXT_TERMINATOR：next的终止节点，prev指向自身，即。在 last 节点出列后，会把last.prev指向自身()，然后把next设为

。

源码解析

在开始源码分析之前，我们先来看一下CLD中对Node的定义：

live node：节点的 item!=null 被称为live节点。当节点的 item 被 CAS 改为 null，逻辑上来讲这个节点已经从链表中移除；一个新的元素通过 CAS 添加到一个包含空 prev 或空 next 的 first 或 last 节点，这个元素的节点在这时是 live节点。

first node & last node：首节点(first node)总会有一个空的 prev 引用，终止任何从 live 节点开始的 prev 引用链；同样的最后一个节点(last node)是 next 的终止节点。first/last 节点的 item 可以为 null。并且 first 和 last 节点总是相互可达的。

active node：live节点、first/last 节点也被称为活跃节点(active node)，活跃节点一定是被链接的，如果p节点为active节点，则：

self-node：自链接节点，prev 或 next 指向自身的节点，自链接节点用在解除链接操作中，并且它们都不是active node。

head/tail节点：head/tail 也可能不是 first/last 节点。从 head 节点通过 prev 引用总是可以找到 first 节点，从 tail 节点通过 next 引用总是可以找到 last 节点。允许 head 和 tail 引用已删除的节点，这些节点没有链接，因此可能无法从 live 节点访问到。

节点删除时经历三个阶段：逻辑删除(logical deletion)，未链接( unlinking)，和gc未链接( gc-unlinking)：

logical deletion：通过 CAS 修改节点 item 为 null 来完成，表示当前节点可以被解除链接(unlinking)。

unlinking：这种状态下的节点与其他 active 节点有链接，但是其他 active 节点与之都没有链接，也就是说从这个状态下的节点可以达到 active 节点，但是从 active 节点不可达到这种状态的节点。在任何时候，从 first 通过 next 找到的 live 节点和从 last 通过 prev 找到的节点总是相等的。但是，在节点被逻辑删除时上述结论不成立，这些被逻辑删除的节点也可能只从一端是可达的。

gc-unlinking：GC未链接使已删除节点不可达到 active 节点，使GC更容易回收被删除的节点。通过让节点自链接或链接到终止节点（PREV_TERMINATOR 或 NEXT_TERMINATOR）来实现。 gc-unlinking 节点从 head/tail 访问不可达。这一步是为了使数据结构保持GC健壮性(gc-robust)，防止保守式GC（conservative GC，目前已经很少使用）对这些边界空间的使用。对保守式GC来说，使数据结构保持GC健壮性会消除内存无限滞留的问题，同时也提高了分代收机器的性能。

如果同学们对上述理论还是一头雾水，那么从源码解析中我们就可以直观的看到它们的作用。

OK！准备工作已经做完，下面我们正式开始源码解析。

添加（入列）

CLD的添加方法包括：，所有这些操作都是通过或来实现的。

linkFirst(E) / linkLast(E)

说明：是插入新节点到队列头的主函数，执行流程如下：

首先从 head 节点开始向前循环找到 first 节点()；然后通过设置新节点的 next 节点为 first；然后 CAS 修改 first 的 prev 为新节点。注意这里 CAS 指令成功后会判断 first 节点是否已经跳了两个节点，只有在跳了两个节点才会 CAS 更新 head，这也是为了节省 CAS 指令执行开销。是插入新节点到队列尾，执行流程与一致，不多赘述，具体见源码。

注：通过 Unsafe 类的实现，有关这个方法，请参考笔者的另一篇文章：JUC源码分析—CAS和Unsafe。

获取(出列)

CLD的获取方法分两种：

获取节点：，都是通过实现。

获取并移除节点： ，都是通过实现。

包括了的实现，都是找到并返回 first/last 节点，不同的是，比多了 unlink 这一步。所以这里我们只对和两个方法进行解析。

首先来看一下pollFirst() ：

pollFirst()

说明：用于找到链表中首个 item 不为 null 的节点（注意并不是first节点，因为first节点的item可以为null），并返回节点的item。涉及的内部方法较多，不过都很简单，我们通过穿插代码方式分析：

首先通过方法找到 first 节点，first 节点必须为 active 节点()。源码如下：

如果（这里是允许的，具体见上面我们对 first/last 节点的介绍），则继续调用方法寻找后继节点。源码如下：

CAS 修改节点的 item 为 null（即 “逻辑删除-logical deletion”），然后调用方法解除节点链接，最后返回 item。是移除节点的主方法，逻辑较为复杂，后面我们单独分析。

unlink(Node x)

说明：方法用于解除已弹出节点的链接，分三种情况：

首先说一下通常的情况（源码中标注 处），这种情况下，入列和出列非同端操作，即操作节点 x 非 first 和 last 节点， 就执行如下流程：

首先找到给定节点 x 的活跃（active）前继和后继节点。然后修整它们之间的链接，让它们指向对方（通过和方法），留下一个从活跃(active)节点不可达的 x 节点（即“unlinking”）。

如果成功执行，或者 x 节点没有 live 的前继/后继节点，再尝试 gc 解除链接(gc-unlink)，在设置 x 节点的 prev/next 指向它们自己或 TERMINATOR 之前（即“gc-unlink”），需要检查 x 的前继和后继节点的状态未被改变，并保证 x 节点从 head/tail 不可达（通过和方法）。

如果操作节点为 first 节点（入列和出列都发生在 first 端），则调用解除已删除节点的链接，并链接 first 节点到下一个 active 节点（注意，在执行完此方法之后 first 节点是没有改变的）。源码如下：

如果操作节点为 last 节点（入列和出列都发生在 last 端），则调用解除已删除节点的链接，并链接 last 节点到上一个 active 节点。与方法执行流程一致，只是操作的是 last 端，在此不多赘述。

小结

本章与 ConcurrentLinkedQueue 一篇中的非阻塞算法基本一致，只是为双端操作定义了几个可供操作的节点类型。

本章重点：理解 ConcurrentLinkedDeque 的非阻塞算法及节点删除的三个状态