( 九）并发包非阻塞队列ConcurrentLinkedQueue

淩亂°似流年 2022-04-25 06:56 216阅读 0赞

***jdk1.7.0\_79 ***

队列是一种非常常用的数据结构，一进一出，先进先出。

在Java并发包中提供了两种类型的队列，非阻塞队列与阻塞队列，当然它们都是线程安全的，无需担心在多线程并发环境所带来的不可预知的问题。为什么会有非阻塞和阻塞之分呢？这里的非阻塞与阻塞在于有界与否，也就是在初始化时有没有给它一个默认的容量大小，对于阻塞有界队列来讲，如果队列满了的话，则任何线程都会阻塞不能进行入队操作，反之队列为空的话，则任何线程都不能进行出队操作。而对于非阻塞无界队列来讲则不会出现队列满或者队列空的情况。它们俩都保证线程的安全性，即不能有一个以上的线程同时对队列进行入队或者出队操作。

非阻塞队列：ConcurrentLinkedQueue

阻塞队列：ArrayBlockingQueue、LinkedBlockingQueue、……

本文介绍非阻塞队列——ConcurentLinkedQueue。

首先查看ConcurrentLinkedQueue默认构造函数，观察它在初始化时做了什么操作。

//ConcurrentLinkedQueue 
    public ConcurrentLinkedQueue() { 
    　　head = tail = new Node<E>(null); 
    }

可以看到ConcurrentLinkedQueue在其内部有一个头节点和尾节点，在初始化的时候指向一个节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc3MDk4Mg_size_16_color_FFFFFF_t_70][]

对于入队（插入）操作一共提供了这么2个方法（实际上是一个）：

<table> 
 <tbody> 
  <tr> 
   <td> <p>&nbsp;</p> </td> 
   <td> <p>&nbsp;</p> </td> 
   <td> <p>&nbsp;</p> </td> 
  </tr> 
  <tr> 
   <td> <p>入队（插入）&nbsp;</p> </td> 
   <td> <p>add(e)（其内部调用offer方法，）&nbsp;</p> </td> 
   <td> <p>offer(e)（插入到队列尾部，当队列无界将永远返回true）&nbsp;</p> </td> 
  </tr> 
 </tbody> 
</table>

1 //ConcurrentLinkedQueue#offer
     2 public boolean offer(E e) {
     3     checkNotNull(e);    //入队元素是否为空，不允许Null值入队
     4     final Node<E> newNode = new Node<E>(e);    //将入队元素构造为Node节点
     5     /*tail指向的是队列尾节点，但有时tail.next才是真正指向的尾节点*/
     6     for (Node<E> t = tail, p = t;;) {
     7         Node<E> q = p.next;
     8         if (q == null) {    //此时p指向的就是队列真正的尾节点
     9             if(p.casNext(null, newNode)) {    //cas算法,p.next = newNode
    10                 if (p != tail)     //将tail指向队列尾节点
    11                     casTail(t, newNode);
    12                 return true;
    13 　　　　　　　}
    14 　　　　}
    15 　　　　else if (p == q) 
    16     　　　　p = (t != (t = tail)) ? t : head;
    17 　　　　else
    18     　　　　p = (p != t && t != (t = tail)) t : q;
    19 　　}
    20 }

offer入队过程如下图所示：  
　　① 队列中没有元素，第一次入队操作：  
　　　　进入循环体：  
　　　　t = tail;  
　　　　p = tail;  
　　　　q = p.next = null;

![630246-20170609233459043-2117159646.png][]

判断尾节点的引用p是否指向的是尾节点（if(q == null)）->是：  
　　　　　　CAS算法将入队节点设置成尾节点的next节点（p.casNext(null, newNode)）  
　　　　判断tail尾节点指针的引用p是否大于等于1个next节点（if (p != t)）->否  
　　　　返回true

![630246-20170609233623200-1550315734.png][]

② 队列中有元素，进行入队操作：

1) 第一次循环：  
　　　　t = tail;  
　　　　p = tail;  
　　　　q = p.next = Node1;

![630246-20170609233749012-778615241.png][]

判断tail尾节点指针的引用p是否指向的是尾节点（if(q == null)）->否  
　　　　判断tail尾节点指针的引用p是否指向的是尾节点（else if (p == q)）->否  
　　　　将tail尾节点指针的引用p向后移动（p = (p != t && t != (t = tail)) ? t : q;）->p = Node1

![630246-20170609233835418-1492815147.png][]

2) 第二次循环：  
　　　　t = tail;  
　　　　p = Node1;  
　　　　q = p.next = null;

![630246-20170609233953043-450266686.png][]

判断tail尾节点指针的引用p是否指向真正的尾节点（if(q == null)）->是：  
　　　　　　CAS算法将入队节点设置成尾节点的next节点（p.casNext(null, newNode)）  
　　　　判断tail尾节点指针的引用p是否大于等于1个next节点(if (p != t))->是：  
　　　　　　更新tail节点（casTail(t, nextNode)）  
　　　　返回true

![630246-20170609234108325-26592513.png][]

入队的操作都是由CAS算法完成，显然是为了保证其安全性。整个入队过程首先要定位出尾节点，其次使用CAS算法将入队节点设置成尾节点的next节点。整个入队过程首先要定位队列的尾节点，如果将tail节点一直指向尾节点岂不是更好吗？每次即tail->next = newNode;tail = newNode;这样在单线程环境来确实没问题，但是，在多线程并发环境下就不得不要考虑线程安全，每次更新tail节点意味着每次都要使用CAS更新tail节点，这样入队效率必然降低，所以ConcurrentLinkedQueue的tail节点并不总是指向队列尾节点的原因就是减少更新tail节点的次数，提高入队效率。  
　　对于出队（删除）操作一共提供了这么1个方法：

![630246-20170609234214809-1356415343.png][]

1 //ConcurrentLinkecQueue#poll
     2 public E poll() {
     3     restartFromHead:
     4     for (;;) {
     5         for (Node<E> h = head, p = h, q;;) {
     6             E item = p.item;
     7             if (item != null && p.casItem(item, null)) {
     8                 if (p != h)
     9                     updateHead(h, ((q = p.next) != null) ? q : p);
    10                 return item;
    11 　　　　　　　}　　
    12 　　　　　　  else if ((q = p.next) == null) {
    13　　　　          updateHead(h, p);
    14     　　　　　　　return null;
    15 　　　　　　　}
    16 　　　　　　  else if (p == q)
    17     　　　　　  continue restartFromHead;
    18 　　　　　　  else
    19     　　　　    p = q;
    20 　　　　}
    21 　　}
    22 }

以上面队列中有两个元素为例：(注意，初始时，head指向的是空节点)

![630246-20170609234347747-232149716.png][]

出队（删除）：  
　　1） 第一次循环：  
　　　　h = head;  
　　　　p = head;  
　　　　q = null;  
　　　　item = p.item = null;

![630246-20170609234432090-210163747.png][]

判断head节点指针的引用是否不是空节点（if (item != null)）->否，即是空节点  
　　　　判断（暂略）   
　　　　判断（暂略）  
　　　　将head节点指针的引用p向后移动（p = q）

2） 第二次循环：  
　　　　h = head;  
　　　　p = q = Node1;  
　　　　q = Node1;  
　　　　item = p.item = Node1.item;

![630246-20170609234607403-609774020.png][]

判断head节点指针的引用p是否不是空节点（if (item != null)）->是，即不是空节点：  
　　　　　　判断head节点指针与p是否指向同一节点（if (p != h)）->否：  
　　　　　　　　更新头节点（updateHead(h, ((q = p.next) != null) ? q : p)）  
　　　　　　　　返回item

![630246-20170609234640918-713564414.png][]

实际上继续出队会发现，出队和入队类似，不会每次出队都会更新head节点，原理也和tail一样。  
　　对于ConcurrentLinkedQueue\#size方法将会遍历整个队列，可想它的效率并不高，如果一定需要调用它的size方法，特别是for循环时，我建议一下写法：

for (int i = 0, int size = concurrentLinkedQueue.size(); i < size;i++)

因为这能保证不用每次循环都调用一次size方法遍历一遍队列。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc3MDk4Mg_size_16_color_FFFFFF_t_70]: /images/20220126/5e5357e387254105bfdfd661d843441b.png
[630246-20170609233459043-2117159646.png]: /images/20220126/00bf8878b7fc45b8b351135cc7a9c76d.png
[630246-20170609233623200-1550315734.png]: /images/20220126/77d890f3af1d482fb7d80decb0532887.png
[630246-20170609233749012-778615241.png]: /images/20220126/09fe8c9aa892401ca2284216da884c22.png
[630246-20170609233835418-1492815147.png]: /images/20220126/af223f405f1d403aa6f128503c4fa88d.png
[630246-20170609233953043-450266686.png]: /images/20220126/b169f79e5f514ee5879bde38c1c0c414.png
[630246-20170609234108325-26592513.png]: /images/20220126/9162a55a7c77454ca2636463b93e98a9.png
[630246-20170609234214809-1356415343.png]: /images/20220126/455521bc9fc04ce4bfb9e466ab739dc3.png
[630246-20170609234347747-232149716.png]: /images/20220126/cb07958427e84607a2fae52ef806edcb.png
[630246-20170609234432090-210163747.png]: /images/20220126/e3031fc493f64af08cbce03e2ba7c265.png
[630246-20170609234607403-609774020.png]: /images/20220126/282a08b8d6b640d084ec64b44aa3143b.png
[630246-20170609234640918-713564414.png]: /images/20220126/553faa39f66f4bb7bb0f16969774fa42.png