线程安全的队列实现的两种方式

  • 阻塞算法：入队和出队公用一把锁
  • 非阻塞算法：CAS

基于链接节点的无界线程安全队列。采用“wai-free”算法来实现。

  • 类的整体结构
  • 节点入队列的过程
  • 节点出队列过程

类的整体结构

image.png

  • 默认初始化，会tail=head
    1. public ConcurrentLinkedQueue() {
    2.    head = tail = new Node<E>(null);
    3. }

    入队列的过程

    image.png
    注意：tail节点不总是指向队列中的最后一个节点
    单线程：
  • 当前tail的next节点为空：入队列节点成为tail的next节点，tail不做变动
  • 当前tail的next节点不为空：则将入队列节点放在队列最后，并设置成tail节点。

多线程：

  • 先定位到尾节点

  • CAS将本节点设置为tail的next节点

    定位尾节点

    尾节点不一定是是tail节点，也有可能是tail的next节点。

    设置入队节点为尾节点

    p.casNext()将入队节点设置为队列尾节点的next节点。

  • p是null：p是当前队列的尾节点

  • p不是null：表示其他线程更新了尾节点，需要重新获取

    HOPS的设计意图

    为什么不让tail一直指向尾节点。
    因为这样可以减少CAS次数

  • 并不是每次节点入队后都将tail节点更新成尾节点，而是当tail节点和尾节点的距离大于等于常量HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距离越长，使用CAS更新tail节点的次数就会越少

  • 但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长

节点出队列过程

image.png

  • head中无值：直接改变head节点 head=head.next
  • head中有值：直接弹出head中拥有的元素
  • 上述过程均需要通过CAS进行操作