写点什么

聊聊并发(六)——ConcurrentLinkedQueue 的实现原理分析

  • 2013-01-09
  • 本文字数:4051 字

    阅读完需:约 13 分钟

1. 引言

在并发编程中我们有时候需要使用线程安全的队列。如果我们要实现一个线程安全的队列有两种实现方式:一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现,而非阻塞的实现方式则可以使用循环 CAS 的方式来实现,本文让我们一起来研究下 Doug Lea 是如何使用非阻塞的方式来实现线程安全队列 ConcurrentLinkedQueue 的,相信从大师身上我们能学到不少并发编程的技巧。

2. ConcurrentLinkedQueue 的介绍

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

3. ConcurrentLinkedQueue 的结构

我们通过 ConcurrentLinkedQueue 的类图来分析一下它的结构。

(图 1)

ConcurrentLinkedQueue 由 head 节点和 tair 节点组成,每个节点(Node)由节点元素(item)和指向下一个节点的引用 (next) 组成,节点与节点之间就是通过这个 next 关联起来,从而组成一张链表结构的队列。默认情况下 head 节点存储的元素为空,tair 节点等于 head 节点。

复制代码
private transient volatile Node<E> tail = head;

4. 入队列

入队列就是将入队节点添加到队列的尾部。为了方便理解入队时队列的变化,以及 head 节点和 tair 节点的变化,每添加一个节点我就做了一个队列的快照图。

(图二)

  • 第一步添加元素 1。队列更新 head 节点的 next 节点为元素 1 节点。又因为 tail 节点默认情况下等于 head 节点,所以它们的 next 节点都指向元素 1 节点。
  • 第二步添加元素 2。队列首先设置元素 1 节点的 next 节点为元素 2 节点,然后更新 tail 节点指向元素 2 节点。
  • 第三步添加元素 3,设置 tail 节点的 next 节点为元素 3 节点。
  • 第四步添加元素 4,设置元素 3 的 next 节点为元素 4 节点,然后将 tail 节点指向元素 4 节点。

通过 debug 入队过程并观察 head 节点和 tail 节点的变化,发现入队主要做两件事情,第一是将入队节点设置成当前队列尾节点的下一个节点。第二是更新 tail 节点,如果 tail 节点的 next 节点不为空,则将入队节点设置成 tail 节点,如果 tail 节点的 next 节点为空,则将入队节点设置成 tail 的 next 节点,所以 tail 节点不总是尾节点,理解这一点对于我们研究源码会非常有帮助。

上面的分析让我们从单线程入队的角度来理解入队过程,但是多个线程同时进行入队情况就变得更加复杂,因为可能会出现其他线程插队的情况。如果有一个线程正在入队,那么它必须先获取尾节点,然后设置尾节点的下一个节点为入队节点,但这时可能有另外一个线程插队了,那么队列的尾节点就会发生变化,这时当前线程要暂停入队操作,然后重新获取尾节点。让我们再通过源码来详细分析下它是如何使用 CAS 算法来入队的。

复制代码
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
// 入队前,创建一个入队节点
Node<E> n = new Node<E>(e);
retry:
// 死循环,入队不成功反复入队。
for (;;) {
// 创建一个指向 tail 节点的引用
Node<E> t = tail;
//p 用来表示队列的尾节点,默认情况下等于 tail 节点。
Node<E> p = t;
for (int hops = 0; ; hops++) {
// 获得 p 节点的下一个节点。
Node<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 节点有大于等于 1next 节点,则将入队节点设置成 tair 节点,更新失败了也
没关系,因为失败了表示有其他线程成功更新了 tair 节点。
if (hops >= HOPS)
casTail(t, n); // 更新 tail 节点,允许失败
return true;
}
// p 有 next 节点, 表示 p 的 next 节点是尾节点,则重新设置 p 节点
else {
p = succ(p);
}
}
}
}

从源代码角度来看整个入队过程主要做二件事情。第一是定位出尾节点,第二是使用 CAS 算法能将入队节点设置成尾节点的 next 节点,如不成功则重试。

第一步定位尾节点。tail 节点并不总是尾节点,所以每次入队都必须先通过 tail 节点来找到尾节点,尾节点可能就是 tail 节点,也可能是 tail 节点的 next 节点。代码中循环体中的第一个 if 就是判断 tail 是否有 next 节点,有则表示 next 节点可能是尾节点。获取 tail 节点的 next 节点需要注意的是 p 节点等于 p 的 next 节点的情况,只有一种可能就是 p 节点和 p 的 next 节点都等于空,表示这个队列刚初始化,正准备添加第一次节点,所以需要返回 head 节点。获取 p 节点的 next 节点代码如下

复制代码
final Node<E> succ(Node<E> p) {
Node<E> next = p.getNext();
return (p == next) ? head : next;
}

第二步设置入队节点为尾节点。p.casNext(null, n) 方法用于将入队节点设置为当前队列尾节点的 next 节点,p 如果是 null 表示 p 是当前队列的尾节点,如果不为 null 表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。

hops 的设计意图。上面分析过对于先进先出的队列入队所要做的事情就是将入队节点设置成尾节点,doug lea 写的代码和逻辑还是稍微有点复杂。那么我用以下方式来实现行不行?

复制代码
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
Node<E> n = new Node<E>(e);
for (;;) {
Node<E> t = tail;
if (t.casNext(null, n) && casTail(t, n)) {
return true;
}
}
}

让 tail 节点永远作为队列的尾节点,这样实现代码量非常少,而且逻辑非常清楚和易懂。但是这么做有个缺点就是每次都需要使用循环 CAS 更新 tail 节点。如果能减少 CAS 更新 tail 节点的次数,就能提高入队的效率,所以 doug lea 使用 hops 变量来控制并减少 tail 节点的更新频率,并不是每次节点入队后都将 tail 节点更新成尾节点,而是当 tail 节点和尾节点的距离大于等于常量 HOPS 的值(默认等于 1)时才更新 tail 节点,tail 和尾节点的距离越长使用 CAS 更新 tail 节点的次数就会越少,但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长,因为循环体需要多循环一次来定位出尾节点,但是这样仍然能提高入队的效率,因为从本质上来看它通过增加对 volatile 变量的读操作来减少了对 volatile 变量的写操作,而对 volatile 变量的写操作开销要远远大于读操作,所以入队效率会有所提升。

复制代码
private static final int HOPS = 1;

还有一点需要注意的是入队方法永远返回 true,所以不要通过返回值判断入队是否成功。

5. 出队列

出队列的就是从队列里返回一个节点元素,并清空该节点对元素的引用。让我们通过每个节点出队的快照来观察下 head 节点的变化。

从上图可知,并不是每次出队时都更新 head 节点,当 head 节点里有元素时,直接弹出 head 节点里的元素,而不会更新 head 节点。只有当 head 节点里没有元素时,出队操作才会更新 head 节点。这种做法也是通过 hops 变量来减少使用 CAS 更新 head 节点的消耗,从而提高出队效率。让我们再通过源码来深入分析下出队过程。

复制代码
public E poll() {
Node<E> h = head;
// p 表示头节点,需要出队的节点
Node<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> q = p.getNext();
updateHead(h, (q != null) ? q : p);
}
return item;
}
// 如果头节点的元素为空或头节点发生了变化,这说明头节点已经被另外一个线程修改了。那么获取 p 节点的下一个节点
Node<> next = succ(p);
// 如果 p 的下一个节点也为空,说明这个队列已经空了
if (next == null) {
// 更新头节点。
updateHead(h, p);
break;
}
// 如果下一个元素不为空,则将头节点的下一个节点设置成头节点
p = next;
}
return null;
}

首先获取头节点的元素,然后判断头节点元素是否为空,如果为空,表示另外一个线程已经进行了一次出队操作将该节点的元素取走,如果不为空,则使用 CAS 的方式将头节点的引用设置成 null,如果 CAS 成功,则直接返回头节点的元素,如果不成功,表示另外一个线程已经进行了一次出队操作更新了 head 节点,导致元素发生了变化,需要重新获取头节点。

6. 参考资料

作者介绍

方腾飞,花名清英,淘宝资深开发工程师,关注并发编程,目前在广告技术部从事无线广告联盟的开发和设计工作。个人博客: http://ifeve.com 微博: http://weibo.com/kirals 欢迎通过我的微博进行技术交流。


感谢张龙对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作,请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博( @InfoQ )或者腾讯微博( @InfoQ )关注我们,并与我们的编辑和其他读者朋友交流。

2013-01-09 05:0932561

评论 3 条评论

发布
用户头像
第二步设置入队节点为尾节点。p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点,p如果是null表示p是当前队列的尾节点,如果不为null表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。/r/n
改成如下:是p的next不是p /r/n
第二步设置入队节点为尾节点。p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点,p的next如果是null表示p是当前队列的尾节点,如果不为null表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。 /r/n
另外图片有问题,老铁修改下啊。/r/n
不支持换行啊。
展开
2018-11-14 17:17
回复
用户头像
第二步设置入队节点为尾节点。p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点,p如果是null表示p是当前队列的尾节点,如果不为null表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。
改成如下:是p的next不是p
第二步设置入队节点为尾节点。p.casNext(null, n)方法用于将入队节点设置为当前队列尾节点的next节点,p的next如果是null表示p是当前队列的尾节点,如果不为null表示有其他线程更新了尾节点,则需要重新获取当前队列的尾节点。
另外图片有问题,老铁修改下啊。
2018-11-14 17:15
回复
用户头像
图有问题吧
2018-11-08 19:50
回复
没有更多了
发现更多内容

【YashanDB知识库】绑定参数,同一个sql多个执行计划的问题

YashanDB

yashandb 崖山数据库 崖山DB

仓颉编程语言技术指南:嵌套函数、Lambda 表达式、闭包

华为云开发者联盟

鸿蒙 编程语言 华为云开发者联盟 企业号2024年7月PK榜 仓颉

提升工作效率:顶级项目安排软件推荐

爱吃小舅的鱼

项目管理 项目进度管理软件 项目进度安排

聚焦于 Melos 数据生命网络,用户如何参与到生态的建设中?

大瞿科技

在 K8s 上用 KubeBlocks 提供的 PG 和 Redis operator 部署高可用 Harbor 集群

小猿姐

postgresql Kubernetes operator Redis 消费队列

一步即扫,直达应用所有服务

HarmonyOS SDK

HarmonyOS

ChatGPT4o 如何速写论文

蓉蓉

gpt4o

低代码技术在售后管理中的应用与优化

天津汇柏科技有限公司

低代码开发

深入解析仓颉编程语言:函数式编程的核心特性

代码忍者

仓颉

淘宝商品详情API:商品规格参数的详细解析

技术冰糖葫芦

API Explorer API 编排 api 货币化 API 文档

24年黑龙江正规等保测评机构名单汇总

行云管家

等保 堡垒机 等保测评 黑龙江

京东商品列表数据接口:电商数据分析的利器

tbapi

京东API 京东商品列表数据接口 京东商品数据采集

一文了解MySQL索引机制

京东零售技术

后端 MySQL 高可用 企业号2024年7月PK榜

Lights Out for Mac(扩展节能器)v2024.2激活版

理理

职场<火焰杯>测试开发大赛决赛成绩及获奖名单公布!

测吧(北京)科技有限公司

测试

AI客服上线 干货 干货 全是干货!

开源物联卡管理平台-设备管理

物联网 IoT eSIM安全 java 技术提升

运维安全审计以及运维安全审计软件定义看这里!

行云管家

安全运维 运维安全 运维安全审计

从积木式到装配式云原生安全

京东科技开发者

官宣!2024观测云发布会

观测云

监控

职场<火焰杯>测试开发大赛决赛成绩及获奖名单公布!

测试人

软件测试

LLM推理加速:decode阶段的Attention在GPU上的优化

阿里技术

阿里巴巴 推理 大模型 LLM RTP-LLM

灵活数据流处理:NeuronEX 支持 JavaScript 自定义函数

EMQ映云科技

Java 车联网 物联网 数据采集 NeuronEX

【YashanDB知识库】服务端是GBK编码,导致从22.2.12.100升级到22.2.13.100失败问题

YashanDB

yashandb 崖山数据库 崖山DB

以用户为中心:观测云的设计理念

可观测技术

监控

观测云:零售行业数据分析的利器

可观测技术

【论文速读】| Arondight:使用自动生成的多模态越狱提示对大型视觉语言模型进行红队测试

云起无垠

从C端到B端:我的前端技术进阶之路

京东零售技术

前端 企业号2024年7月PK榜

从K8s的“临时容器”看K8s设计的厉害之处

华为云开发者联盟

Docker 容器 云原生 华为云开发者联盟 企业号2024年7月PK榜

【程序大侠传】全局变量与并发之战

Disaster

观测云:企业级监控的全方位解决方案

可观测技术

监控

夏日清凉计划开启,来华为天气领取出行礼包、影音会员等惊喜福利

最新动态

聊聊并发(六)——ConcurrentLinkedQueue的实现原理分析_Java_方腾飞_InfoQ精选文章