Java并发容器之非阻塞队列ConcurrentLinkedQueue

467 阅读4分钟

转载(原文链接):www.cnblogs.com/ygj0930/p/6…

参考资料:http://blog.csdn.net/chenchaofuck1/article/details/51660521

实现一个线程安全的队列有两种实现方式:一种是使用阻塞算法,阻塞队列就是通过使用加锁的阻塞算法实现的;另一种非阻塞的实现方式则可以使用循环CAS(比较并交换)的方式来实现。

ConcurrentLinkedQueue是一个基于链表实现的无界线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部,当我们获取一个元素时,它会返回队列头部的元素。默认情况下head节点存储的元素为空,tair节点等于head节点。

一:入队

入队主要做两件事情, 第一是将入队节点设置成当前队列的最后一个节点。

第二是更新tail节点,如果原来的tail节点的next节点不为空,则将tail更新为刚入队的节点(即队尾结点),如果原来的tail节点(插入前的tail)的next节点为空,则将入队节点设置成tail的next节点(而tial不移动,成为倒数第二个节点),所以tail节点不总是尾节点!

public boolean offer(E e) { if (e == null) throw new NullPointerException(); //入队前,创建一个入队节点 Node n = new Node(e); retry:

        //死循环,入队不成功反复入队。

        for (;;) {

            //创建一个指向tail节点的引用

            Node</e><e> t = tail;

            //p用来表示队列的尾节点,默认情况下等于tail节点。

            Node</e><e> p = t;

            //获得p节点的下一个节点。

               Node</e><e> next = succ(p);

     //next节点不为空,说明p不是尾节点,需要更新p后在将它指向next节点

                if (next != null) {

                   //循环了两次及其以上,并且当前节点还是不等于尾节点

                    if (hops > HOPS && t != tail)

                        continue retry;
                         p = next;

                }
                //如果p是尾节点,则设置p节点的next节点为入队节点。
                else if (p.casNext(null, n)) {

//如果tail节点有大于等于1个next节点,则将入队节点设置成tair节点,更新失败了也没关系,因为失败了表示有其他线程成功更新了tair节点。

             if (hops >= HOPS)

                   casTail(t, n); // 更新tail节点,允许失败

              return true;

                }

               // p有next节点,表示p的next节点是尾节点,则重新设置p节点

                else {
                    p = succ(p);
                }

            }

        }
    }



二:出队



不是每次出队时都更新head节点,当head节点里有元素时,直接弹出head节点里的元素,而不会更新head节点。只有当head节点里没有元素时,则弹出head的next结点并更新head结点为原来head的next结点的next结点。
public E poll() {
               Node</e><e> h = head;
           // p表示头节点,需要出队的节点
               Node</e><e> p = h;
 
               for (int hops = 0;; hops++) {
                    // 获取p节点的元素
                    E item = p.getItem();
                    // 如果p节点的元素不为空,使用CAS设置p节点引用的元素为null,如果成功则返回p节点的元素。
                    if (item != null && p.casItem(item, null)) {
                         if (hops >= HOPS) {
                              //将p节点下一个节点设置成head节点
                              Node</e><e> q = p.getNext();
                              updateHead(h, (q != null) ? q : p);
                         }
                         return item;
                    }
                    // 如果头节点的元素为空或头节点发生了变化,这说明头节点已经被另外一个线程修改了。那么获取p节点的下一个节点
                Node</e><e> next = succ(p);

                    // 如果p的下一个节点也为空,说明这个队列已经空了
                    if (next == null) {
                  // 更新头节点。
                         updateHead(h, p);
                      break;
            }

                    // 如果下一个元素不为空,则将头节点的下一个节点设置成头节点

                    p = next;
               }
               return null;
         }
三:非阻塞却线程安全的原因

观察入队和出队的源码可以发现,无论入队还是出队,都是在死循环中进行的,也就是说,当一个线程调用了入队
、出队操作时,会尝试获取链表的tail、head结点进行插入和删除操作,而插入和删除是通过CAS操作实现的,
而CAS具有原子性。故此,如果有其他任何一个线程成功执行了插入、删除都会改变tail/head结点,那么当前线程的插
入和删除操作就会失败,则通过循环再次定位tail、head结点位置进行插入、删除,直到成功为止。也就是说,
ConcurrentLinkedQueue的线程安全是通过其插入、删除时采取CAS操作来保证的。不会出现同一个tail结点的next指
针被多个同时插入的结点所抢夺的情况出现。

END