★★★ 建议星标我们 ★★★

Java 进阶架构师 ★ “ 星标 ”！这样才不会错过每日进阶架构文章呀。

2020年Java面试题库连载中

【000期】Java最全面试题库思维导图

【001期】JavaSE面试题（一）：面向对象

【002期】JavaSE面试题（二）：基本数据类型与访问修饰符

【003期】JavaSE面试题（三）：JavaSE语法（1）

【004期】JavaSE面试题（四）：JavaSE语法（3）

【005期】JavaSE面试题（五）：String类

【006期】JavaSE面试题（六）：泛型

【007期】JavaSE面试题（七）：异常

【008期】JavaSE面试题（八）：集合之List

【009期】JavaSE面试题（九）：集合之Set

【010期】JavaSE面试题（十）：集合之Map

【011期】JavaSE面试题（十一）：多线程（1）

【012期】JavaSE面试题（十二）：多线程（2）

【013期】JavaSE面试题（十三）：多线程（3）

【014期】JavaSE面试题（十四）：基本 IO流

【015期】JavaSE面试题（十五）：网络IO流

【016期】JavaSE面试题（十六）：反射

【017期】JavaSE面试题（十七）： JVM 之内存模型

【018期】JavaSE面试题（十八）：JVM之垃圾回收

1. 类结构

队列由单向链表实现，ConcurrentLinkedQueue 持有头尾指针（head/ tail 属性）来管理队列。

队列进行出队入队时对节点的操作都是通过 CAS 实现，保证线程安全。

 public class ConcurrentLinkedQueue<E> { 
private transient volatile Node<E> head; 
private transient volatile Node<E> tail; 
 
/** 
* 节点类 
* CAS保证节点操作安全 
*/ 
private static class Node<E> { 
volatile E item; 
volatile Node<E> next; 
 
Node(E item) { 
// 获得item 和 next 的偏移量 
UNSAFE.putObject(this, itemOffset, item); 
} 
 
/** 
* 更改Node中的数据域item 
*/ 
boolean casItem(E cmp, E val) { 
return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val); 
} 
 
/** 
* 更改Node中的指针域next 
*/ 
void lazySetNext(Node<E> val) { 
UNSAFE.putOrderedObject(this, nextOffset, val); 
} 
 
/** 
* 更改Node中的指针域next 
*/ 
boolean casNext(Node<E> cmp, Node<E> val) { 
return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val); 
} 
} 
 
/**入队*/ 
public boolean offer(E e) 
/**出队*/ 
public E poll 
}

2. 入队 offer

将入队节点设置成当前队列尾节点的下一个节点。
更新 tail 节点，tail 节点不总是尾节点。如果 tail 节点的 next 节点不为空，则将入队节点设置成 tail 节点；如果 tail 节点的 next 节点为空，则只入队不更新尾节点。

看下源码：

 public boolean offer(E e) { 
checkNot(e); 
final Node<E> newNode = new Node<E>(e); 
for (Node<E> t = tail, p = t;;) {// 注意这里是个循环 
Node<E> q = p.next; 
if (q == ) {//(1) 
/* 
* q == 表示p是最后一个节点，设置t.next=newNode 
* 如果失败，说明表示其他 线程 已经修改了p的指向，循环尝试直到成功 
*/ 
if (p.casNext(, newNode)) {// 2) 
// node 加入节点后会导致tail距离最后一个节点相差大于一个，需要更新tail 
if (p != t)//(3) 
casTail(t, newNode);//(4) casTail：设置tail 尾节点 
return true; 
} 
} 
else if (p == q)//(5) 
/* 
* 多线程环境下，offer(e)和poll同时执行， 
* 此时p节点被poll，设置了p.next=p，所以此时q=p.next=p 
* 这里要重新设置p结点 
*/ 
p = (t != (t = tail)) ? t : head;//(6) 
else 
// tail并没有指向尾节点，重新设置p 
p = (p != t && t != (t = tail)) ? t : q;//(7) 
} 
}

单看代码很难理解 offer过程，不用担心，我们一起从头复现一下 offer过程：

初始时，head、tail 都指向同一个 item 为的节点

offer(A)：执行步骤(1) (2)，将 A 加入队列，但不更新 tail。

offer(B)：第一次循环执行(7)，设置 p=A 结点。第二次循环执行(1)(2)(3)，插入 B 并将 taill 更新为 B。

offer(C)：执行步骤(1) (2)，将 C 加入队列，但不更新 tail。

循环….

3. 出队 poll

从队列里返回一个节点元素，并清空该节点对元素的引用
更新 head，并不是每次出队时都更新 head 节点。当 head 节点里有元素时，直接弹出 head 节点里的元素，而不会更新 head 节点；只有当 head 节点里没有元素时，出队操作才会更新 head 节点。

 public E poll { 
restartFromHead:// 如果出现p被删除的情况需要从head重新开始 
for (;;) { 
for (Node<E> h = head, p = h, q;;) { 
E item = p.item; 
// item不为，将item返回并设置为 
if (item != && p.casItem(item, )) {//(1) 
if (p != h)//(2) 
/* 
* p != head 则更新head 
* p.next != ，则将head更新为p.next ,否则更新为p 
*/ 
updateHead(h, ((q = p.next) != ) ? q : p);//(3) 
return item; 
} 
// p.next == 队列为空 
else if ((q = p.next) == )//(4) 
updateHead(h, p); 
return ; 
} 
// 另一个线程已经把p从队列中删除并设置p.next = p，p已经被移除不能继续，需要重新开始 
else if (p == q)//(5) 
continue restartFromHead; 
else 
p = q;//(6) 
} 
} 
} 
 
/** 
* 更新head 
*/ 
final void updateHead(Node<E> h, Node<E> p) { 
if (h != p && casHead(h, p)) 
h.lazySetNext(h); 
}

同样复现一下 poll过程，接着上文 offer之后的数据：

第一次 poll：第一次循环，执行(6)设置 p=A；第二次循环执行(1)(2)(3)，将 A 返回，设置 A.item=,更新 head=原 A 节点。

第二次 poll：第一循环，执行(6)设置 p=B；第二次循环执行(1)(2)(3)，将 A 返回，设置 B.item=,更新 head=原 B 节点。

第三次 poll：第一循环，执行(6)设置 p=C；第二次循环执行(1)(2)(3)，将 A 返回，设置 B.item=,更新 head=原 C 节点。

4. 总结

4.1 如何保证并发安全性

需要保证线程安全的三种情况：

多个线程同时 offer：

多个线程同时执行到 casNext设置最后的节点，casNext通过 CAS 实现，第一个线程执行成功设置了最后一个节点后，其他线程的在 CAS 时发现期望的最后节点和实际上的最后节点不一致，CAS 就会失败，然后继续循环尝试直到成功。

多个线程同时 poll：

同样是通过 CAS 保证线程安全，多个线程同时执行到 casItem设置当前节点 item=，第一个线程执行成功设置了当前节点 item= 后，其他线程的在 CAS 时发现期望的 item 与实际的 item 不一致，CAS 就会失败，然后继续循环尝试 poll 下一个节点直到成功。

队列中只有一个元素时，线程 Aoffer一个线程 Bpoll：

线程 A 要设置 p.next=newNode，但是此时 poll将 p 删除了。当 poll将 p 删除时设置了 p.next=p，offer方法中会检查这种情况，发现有 p.next=p 就重新设置一个合适的 p 节点，以便将 newNode 入队。

4.2 head/tail 为何延迟更新

tail 更新时机：tail 节点不总是尾节点。如果 tail 节点的 next 节点不为空，则将入队节点设置成 tail 节点；如果 tail 节点的 next 节点为空，则只入队不更新尾节点。head 更新时机：并不是每次出队时都更新 head 节点。当 head 节点里有元素时，直接弹出 head 节点里的元素，而不会更新 head 节点；只有当 head 节点里没有元素时，出队操作才会更新 head 节点。

head 和 tail 的更新总是间隔了一个。如果让 tail 永远作为队列的队尾节点，代码不是逻辑简单容易实现吗？

如果让 tail 永远作为队列的队尾节点，实现的代码量会更少，而且逻辑更易懂。但是，这样做有一个缺点，如果大量的入队操作，每次都要执行 CAS 进行 tail 的更新，汇总起来对性能也会是大大的损耗。如果能减少 CAS 更新的操作，无疑可以大大提升入队的操作效率，所以 doug lea 大师每间隔 1 次（tail 和队尾节点的距离为 1）进行才利用 CAS 更新 tail。对 head 的更新也是同样的道理。

并发系列文章汇总

【原创】01|开篇获奖感言

【原创】02|并发编程三大核心问题

【原创】03|重排序-可见性和有序性问题根源

【原创】04|Java 内存模型详解

【原创】05|深入理解 volatile

【原创】06|你不知道的 final

【原创】07|synchronized 原理

【原创】08|synchronized 锁优化

【原创】09|基础干货

【原创】10|线程状态

【原创】11|线程调度

【原创】12|揭秘 CAS

【原创】13|LockSupport

【原创】14|AQS 源码分析

【原创】15|重入锁 ReentrantLock

【原创】16|公平锁与非公平锁

【原创】17|读写锁八讲（上）

【原创】18|读写锁八讲（下）

【原创】19|JDK8 新增锁 StampedLock

【原创】20|StampedLock 源码解析

【原创】21|Condition-Lock 的等待通知

【原创】22|倒计时器 CountDownLatch

【原创】23|循环屏障 CyclicBarrier

【原创】24|信号量 Semaphore

【原创】25|交换器 Exchangere

【原创】26|ConcurrentHashMap（上）

【原创】27|ConcurrentHashMap（下）

【原创】28|Copy-On-Write 容器

 
   之前，给大家发过  三份Java  面试宝典，这次新增了一份，目前总共是  四份  面试宝典，相信在跳槽前一个月按照面试宝典准备准备，基本没大问题。  
    《java面试宝典5.0》  (初中级)  
 
   《350道Java面试题：整理自100+公司》  （中高级）  
 
   《资深java面试宝典-视频版》  （资深）  
 
   《Java[BAT]面试必备》  （资深）  
 
 
  分别适用于  初中级，中高级  ，  资深  级工程师  的面试复习。  
  内容包含  java基础、javaweb、mysql性能优化、JVM、锁、百万并发、消息队列，高性能缓存、反射、Spring全家桶原理、微服务、Zookeeper、数据结构、限流熔断降级等等。  
          
   看到这里，证明有所收获

智云一二三科技

「原创」Java并发编程系列29 | ConcurrentLinkedQueue

1. 类结构

2. 入队 offer

3. 出队 poll

4. 总结

4.1 如何保证并发安全性

4.2 head/tail 为何延迟更新

并发系列文章汇总

关于作者: 智云科技

发表回复

1. 类结构

2. 入队 offer

3. 出队 poll

4. 总结

4.1 如何保证并发安全性

4.2 head/tail 为何延迟更新

并发系列文章汇总

给这篇文章的作者打赏

关于作者: 智云科技

相关文章

Map和List的几种遍历方式

全网大佬都在用的Java+Python这两套视频学习教程，学习很重要

JavaWeb快速进阶全套教程(程序员必备2020版)：视频+笔记+源码

热门文章

1分享新浪图床上传接口源码

2PHP简单实现路由Route功能

3Tideways、xhprof 和 xhgui 打造 PHP 非侵入式监控平台

4centos系统如何查看是否安装了mysql

5curl 工具简述

发表回复