ConcurrentLinkedQueue 介绍

在多线程编程环境下并发安全队列是不可或缺的一个重要工具类,为了实现并发安全可以有两种方式:一种是阻塞式的,例如:LinkedBlockingQueue;另一种即是我们将要探讨的非阻塞式,例如:ConcurrentLinkedQueue。相比较于阻塞式,非阻塞的最显著的优点就是性能,非阻塞式算法使用CAS来原子性的更新数据,避免了加锁的时间,同时也保证了数据的一致性。

简单介绍

ConcurrentLinkedQueue是一个基于链接节点的无界无锁线程安全队列,它采用先进先出的规则对节点进行排序,当我们添加一个元素的时候,它会添加到队列的尾部,当我们获取一个元素时,它会返回队列头部的元素。它采用了“wait-free”算法来实现,该算法在Michael & Scott算法上进行了一些修改。

ConcurrentLinkedQueue中的方法不多,其中最主要的两个方法是:offer(E)和poll(),分别实现队列的两个重要的操作:入队和出队。

方法

含义

offer(E)

插入一个元素到队列尾部

poll()

从队列头部取出一个元素

add(E)

同offer(E)

peek()

获取头部元素,但不删除

isEmpty()

判断队列是否为空

size()

获取队列长度(元素个数)

contains(Object)

判断队列是否包含指定元素

remove(Object)

删除队列中指定元素

toArray(T[])

将队列的元素复制到一个数组

iterator()

返回一个可遍历该队列的迭代器

为什么针对ConcurrentLinkedQueue的整个入队/出队/删除都是不需要锁的。

  1. 如果多个线程同时访问其中任一个方法(offer/poll/remove)都是无需加锁而且线程安全的
  2. 由于remove方法不修改ConcurrentLinkedQueue的结构,所以跟其他两个方法都不会有冲突
  3. 如果同时两个线程,一个入队,一个出队,在队列不为NULL的情况下是不会有任何问题的,因为一个操作tail,一个操作head,完全不相关。但是如果队列为NULL时还是会发生冲突的,因为tail==head。
  4. 如果出队线程发现tail的next不为NULL,那么就会感知到当前有一个线程在执行入队操作,所以出队线程就会帮助入队线程完成入队操作,而且每个操作都是通过CAS保证原子性更新,所以就算同时两个线程,一个入队,一个出队也不会发生冲突。

综上,ConcurrentLinkedQueue最终实现了无锁队列。

使用场景

ConcurrentLinkedQueue适合在对性能要求相对较高,同时对队列的读写存在多个线程同时进行的场景,即如果对队列加锁的成本较高则适合使用无锁的ConcurrentLinkedQueue来替代。下面我们来简单对比下ConcurrentLinkedQueue与我们常用的阻塞队列LinkedBlockingQueue的性能。

表1:入队性能对比

线程数

ConcurrentLinkedQueue耗时(ms)

LinkedBlockingQueue耗时(ms)

5

22

29

10

50

59

20

99

112

30

139

171

测试数据:N个线程,每个线程入队10000个元素。

评论

暂无评论