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

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

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

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

一:入队

 

 

  • 入队主要做两件事情,

  第一是将入队节点设置成当前队列的最后一个节点。

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

    二:出队

    不是每次出队时都更新head节点,当head节点里有元素时,直接弹出head节点里的元素,而不会更新head节点。只有当head节点里没有元素时,则弹出head的next结点并更新head结点为原来head的next结点的next结点。

    三:非阻塞却线程安全的原因

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

from:https://www.cnblogs.com/ygj0930/p/6544543.html