9.并发包非阻塞队列ConcurrentLinkedQueue

jdk1.7.0_79

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

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

　　非阻塞队列：ConcurrentLinkedQueue

　　阻塞队列：ArrayBlockingQueue、LinkedBlockingQueue、……

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

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

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

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

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

 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;

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

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

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

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

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

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

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

 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指向的是空节点)

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

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

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

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

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

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

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