ConcurrentLinkedQueue深度源码剖析

在Java的并发包中，存在着许多高效的并发工具类，它优于synchronized关键字，在JDK中提供了一个ConcurrentLinkedQueue工具类实现了高效的并发读写工具类，该工具类具有很高效的性能，因此，本片文章笔者将通过解读ConcurrentLinkedQueue源码的方式探究该数据结构的内部构造。

一、无锁（CAS算法）
在介绍这个工具类之前，先来讲讲无锁的概念以及其算法实现，因为在JDK的并发包中的工具类之所以有高效的性能，大多来源于采用了无锁的算法。因此必须掌握无锁的原理才能理解并发工具类的实现原理。

那么？什么是无锁呢？为什么无锁的性能更佳呢？我们都知道，在并发的环境下，要保证数据的一致性，多个线程共享同一个资源都必须实现同步，否则会产生严重的后果，我们首先想到采用synchronized来实现同步访问资源，没错，这种方式是传统的并发环境下的解决方案，可是，使用该关键字同步访问也就意味着阻塞访问，当在高并发的生产环境中，一个线程占用了共享资源，其他线程就将等待该线程释放资源，对于系统的性能影响非常严重。因此，提出了无锁的概念。无锁是一种非阻塞的方式，因此它在并发环境下不会发生死锁，也就是说它避免了之前阻塞方式下锁的资源竞争给系统带来的开销，也避免了线程之前频繁挂起，唤醒的调度开销，因此，它的性能比基于锁的方式更加优越。但是，性能提高了，它的内部员原理实现也比较复杂，当然，为了提高性能这是有必要的。

无锁算法CAS（全称CompareAndSwap），该算法包含三个过程CAS(V,E,N)，V表示当前值，E表示期望值，N表示更新值，该算法的实现是这样的：当V当前值等于期望值E的时候，就将V更新为N，如果不相等，表示有其他线程修改过改值，因此，不做任何操作，在该算法内部，实现了一个死循环，因此在当有其他线程修改过当前值时，当前线程就会发现，并不做任何操作，再次循环，一直尝试，知道修改成功。之前看到有人提到这样一个问题：如果在判断当前值和期望值是否相等与设置新值之间有其他线程修改了当前值该怎么办，这样不是产生了脏数据吗？其实在CAS操作在硬件层面上，已经实现了原子化的CAS指令，不会发生这种问题。这里就不深究了，读者可自行去查看源码探究。

在介绍完无锁的概念后，我们来进入正题，探究ConcurrentLinkedQueue的内部原理。

二、剖析ConcurrentLinkedQueue
ConcurrentLinkedQueue的性能确实非常的高，但是它的内部实现相当的复杂。它是一个链表的数据结构，实现了Queue接口。它内部实现了一个静态内部类定义了它的节点变量。

上图是这个内部类的成员变量，item用来表示当前元素，next执行下一个元素。这个很好理解。在这个内部类中使用了CAS操作，也就是说在并发环境下是线程安全的。

casItem(E cmp, E val)表示使用CAS操作设置当前值，casNext(Node cmp, Node val)设置下一个节点。
在ConcurrentLinkedQueue的内部，有两个重要的成员变量head,tail，head指向链表的表头，tail指向链表的表尾，在它的无参构造器中，head和tail指向了一个空节点，表示一个空链表。

它也给出了一个带参的构造器，允许传入一个集合。

这个构造器主要是将Collection结合中的元素建立一个链表如果该集合为空，则会抛出空指针异常。
在add方法中调用了一个offer方法，这个方法是ConcurrentLinkedQueue内部实现原理的一个重点，也是一个难点，比较复杂。

下面，我们来看看offer方法的具体实现：

public boolean offer(E e) {
checkNotNull(e);
final Node newNode = new Node(e);

for (Node t = tail, p = t;;) {
Node q = p.next;
if (q == null) {
// p是最后一个节点
if (p.casNext(null, newNode)) {
//每两次更新一下tail
if (p != t)
casTail(t, newNode); // Failure is OK.
return true;
}
// CAS操作竞争失败，再次尝试
}
else if (p == q)
//遇到哨兵节点，从head开始遍历，但是如果tail被修改，则使用tail
//因为它有可能被其他线程修改成功，因此，该操作在并发环境下才会返回true
p = (t != (t = tail)) ? t : head;
else
//取下一个节点或者最后一个节点
p = (p != t && t != (t = tail)) ? t : q;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
该方法首先会检查加入的元素是否为空，如果为空会抛出一个空指针异常，如果不为空，实例化一个节点，进入for循环，该循环是整个方法的核心，由CAS操作完成，是一个死循环，没有出口，一直尝试，直到成功返回。在刚开始，整个链表是空的，head和tail是空的，所以在for循环内部p,t指向头一个空节点，p.next当然为空，因此q也指向一个null值，进入if循环，因为当前值p为null满足期望值，因此进入if语句if (p.casNext(null, newNode))，但是p==t，所以跳过casTail(t, newNode)语句，表示tail没有更新，因此在casNext成功的时候，返回true表示加入元素成功，如果不成功则不返回一直进行尝试直到成功。当加入第二个元素的时候，p.next指向第一个增加的元素，q!=null表示q不是最后一个节点，但是我们要插入一个元素必须找到最后一个节点才能进行插入，因此程序进入 p = (p != t && t != (t = tail)) ? t : q;语句查找尾节点。这个语句在第一个节节点加入成功后进入第二值的时候p != t则会返回q，而q表示p.next，所以该语句这时相当于p=p.next指向下一个节点，也就是尾节点。这时再次循环进入if(q == null)语句，此时由于t在插入第一个节点是没有更新，而p已经更新为尾节点，因此if (p != t)成立，执行casTail方法更新tail为尾节点，返回true表示第二个节点插入成功。由此可以看出，tail每插入两个节点才更新一次。

在上面的源码中，有p==q的情况，这种情况是由于遇到了哨兵，什么是哨兵呢？所谓哨兵节点就是next执行了自己的节点，因为在for循环刚开始 Node q = p.next;如果该if语句成立，表示自己指向了自己，next无法指向了下一个节点，因此我们需要寻找下一个节点来找到尾节点，p = (t != (t = tail)) ? t : head;语句在极大多数情况下会返回head，也就是找不到下一个节点，只能从头开始遍历，在单线程下只能总是从头找起，但是在高并发环境下，t有可能会被其他线程修改，因此t!=t成立，返回tail，这里，有的读者可能不会太明白，t!=t怎么会成立呢？这里解释一下：因为!=操作符不是原子操作符，在该操作符之前我们拿到了t的值，也许在拿到该值之后要去进行比较的时候另外的线程修改了t的值，这样就造成了t!=t成立。所以它本着一种乐观的态度去尝试，也许会有其他线程将t修改成功，此时就可以找到尾节点，不必再从头找起，浪费时间，写到这里笔者深切的体会到该算法的高明之处，极其高明。

对于poll方法，删除一个节点，和上面的offer方法的算法一样，head也是执行两次之后才会更新。有兴趣的读者可以自己查看源码探究。

下面再简单看一下remove方法，删除指定元素节点：

remove方法，它会从头开始遍历，判断是否与指定删除的元素相等，如果不相等，指向下一个节点，succ方法返回下一个节点元素，然后进入下一个循环，如果执行removed = p.casItem(item, null)语句表示找到了要删除的元素，然后将该元素所在的节点值设置为null，如果设置成功则返回true，然后找到下一个节点next，在判断了当前节点与next不为空之后就将当前节点的next指向要删除节点的下一个节点，达到删除的目的，最后返回true表示删除成功。该方法比较简单，只要熟悉 链表的删除等操作不难理解该方法的实现。

该类中还有很多方法，这里不一一讲解了，关键只要理解了它的设置原理，读懂一个方法，其他的也就类似了，有兴趣的读者可以参考JDK源码查看。

最后，要说的是，通过上面可以看出大量的使用了CAS操作，因此要掌握这些并发工具类，理解CAS算法是关键，不过使用了该算法也加大了程序设计的难度，但是对于性能的高速提升，我们认为该设计是完全有必要的。

至此，就介绍完该并发工具类的内部原理，笔者的能力有限，如有不足之处可以指出共同探讨，谢谢！！！
————————————————
版权声明：本文为CSDN博主「不清不慎」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37142346/article/details/80057713

ConcurrentLinkedQueue深度源码剖析