JUC ConcurrentLinkedQueue

java.util.concurrent.ConcurrentLinkedQueue 是一个基于链接结点的、无界、线程安全的、FIFO队列。它的是实现采用了无等待(wait-free)、无锁(lock-free)算法,该算法基于 Maged M. Michael 和 Michael L. Scott 合著的 Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 中描述的算法。

一、设计思路

  1. 使用 CAS 原子指令来处理对数据的并发访问,把同步最小化到单个硬件指令上;这是无锁算法的基础。
  2. 分别用 head、tail 两个原子指针来指向队头和队尾,可以同时进行入队和出队操作,但允许 head、tail 并不总是指向有效的头和尾;把入队、出队需要同步更新的范围最小化到单个原子变量上,这是无锁算法实现的关键。
  3. 在入队、出队操作上并不总是更新 head、tail,而是在多次操作后才进行更新,节省了CAS指令。具有批量更新的效果。
  4. 由于 head、tail 并不总是指向头和尾,这就是说,队列会出现不一致的情况,所以在 head、tail 上定义了一些不变式来维护算法的正确性。

二、不变式

不变式是在执行方法之前和之后,队列必须要保持的。可变式是在执行过程中,队列允许出现的不一致情况。

head 的约束

通过这个结点能够在 O(1) 时间到达第一个存活(非已删除)结点,如果有的话。

不变式
  • 所有存活结点可以 从 head 开始通过 succ() 访问。
  • head != null
  • (tmp = head).next != tmp || tmp != head,这个不变式是说 head 在方法开始之前、之后,head 指向的结点应该是在队列上的。
可变式
  • head.item 可能是、也可能不是 空的。
  • 允许 tail 落后于 head,那是因为 tail 不能从 head 到达。

tail 的约束

从它可以在 O(1) 时间访问到队列的最后一个结点(唯一的满足 node.next == null 的结点)。这个也就是说 tail 指向的并不总是最后一个存活结点。

不变式
  • 最后的结点总是可以从 tail 开始通过 succ() 访问。
  • tail != null
可变式
  • tail.item 可能是、也可能不是空。
  • 允许 tail 落后于 head,那是因为 tail 不能从 head 到达。
  • tail.next 可能是、也可能不是 自指向到 tail。
    继续阅读