暂无图片
暂无图片
暂无图片
暂无图片
暂无图片

RingBuffer往事 ---- 生产媛消费媛问题新解(二)

IT知识刺客 2025-01-09
13

第七届中国PostgreSQL数据库生态大会拾遗中,我给出了我对国产数据库的8字总结:理念领先,代码不行。

分布式、云原生等理念的确领先世界,但基础代码不行。我在《拾遗》这篇文章中给出了具体的例子,以”可观测“性为例,详细分析了”行“的代码应该有的样子。

但是吧,真相这东西,不单是奢侈的,更是残酷的。还是有些朋友接受不了。

基础软件,毕竟带了“基础”二字,不同于纯应用软件。比如QQ、微信,能写一个QQ、微信的人,举不胜数。但能运营至如今腾讯帝国规模的,又有几人。

技术,对于纯应用层软件,重要性几乎趋近于0。

但基础软件不同,其短期的发展,虽仍受市场案例、政策方向、政商关系、营销投入、国际局势等众多因素影响,但如果把眼光拉长,以5年甚至十年为跨度去看,基础类软件的胜出,技术绝对是重要的决定因素之一。

我们旁边就有一位活生生的例子。

曾有一位主导了世界著名火箭与核弹项目的80后年青人,其火箭试射时,身在白宫的川皇都为之震动。其执行能力、行动力更不输马斯克,在火箭轰鸣中,他迈着坚毅的步伐向我们走来:

在金主席钞能力感召下,有为数不少的IT精英,投身基础软件的开发之中,并成功开发出了《红星操作系统》,纯血的:

别笑,如果金主席安排你和下面几位革命同志喜结连理,是不是很难选择:

没关系,如果操作系统你开发的好,金主席全都给你,也是可能的。金主席的能力,可不只钞能力哦。

那么,把时间线拉长,除了技术,什么能力都不缺的《红星操作系统》,你认为什么时候能超越Windows、Linux、Android,甚至纯血鸿蒙?

5年、10年还是15年?

10年后、15年后,《红星操作系统》是否还存在,都不一定。一朝天子一朝臣这种事,咱们作为文明古国,可是太熟悉了。

一款基础软件若是没了技术这个重要因素,就算它一时之间,因为某些因素,被推到浪花之巅,终归是镜花水月,其开发者也免不了最终成为一时笑谈。

(当然,就算技术真的顶尖,《红星操作系统》也有可能抗不过王朝政权的迭代,但如果技术普通,《红星操作系统》是一定抗不过政权迭代)

当然,我们这个邻居是特例。我们肯定不太一样。

不扯那么多了,我们继续以RingBuffer为例,探讨内存屏障的应用,与“锁”的本质。

上一篇中,我们讲述了单个生产媛-消费媛的情况。结论是要看CPU的微架构,x64中不需要锁,也不需要内存屏障。ARM、RISC-V没有详述,这两种CPU是需要内存屏障的,但不需要锁。

在今天的第二篇内容前,按惯例,还是要把生产媛、消费媛请来,集体亮个像:

在开始两个生产媛的双飞与3P前,关于单个生产媛-消费媛的情况,还留了个小尾巴,上一篇重点分析了生产媛这边,消费媛还没看。下面我们把镜头给到消费媛C1这边,看图6:

图6

和图4、5一样,生产媛这边用灰色表示,主要是希望大家把注意集中到消费媛C1这边。但不要盯着她的事业线啊,看她的下面,我的意思是,看下面的那段示例程序。

步1,读“已取数据指针”到寄存器或局部变量reg1中,它对应Load,并且因为“已取数据指针”会被消费媛C1修改,这一步load我标记为“读我的”。

步2,读“可用空间指针”,也是一个Load,在消费媛C1所在CPU视角,这是“读你的”,因为消费媛C1并不会Store“可用空间指针”。

步3,是一个轮询。判断是否有数据写入RingBuffer。这里退出轮询的条件,我写的比较粗糙,可能会有考试不周的地方,但这并不影响结论。因为这里参于对比的是Reg1、Reg2,都是局部变量,它们的值在步1    

步2已经确定。

局部变量不存在共享问题,所以步3没有什么“你的”、“我的”。

另外,如果对实时性要求没那么高,又不想轮询一直占CPU,可以把轮询换成操作系统提供的“消息”等机制。关于这点,这里不展开了。

步4,判断有新的数据到达,开始读数据。

读数据也可以使用memcpy,注意,是从公共内存中读出,写入不共享的私有内存。站在公共内存角度,步4是读,Load。并且“读”的数据是生产媛P1写入的,所以步4是“读你的”。

步5:计算新的“已取数据指针”值。私有变量或寄存器的运算,不涉及共享问题。至于Data_len如何得到,可以放在数据头,也可以使用其他形式,总之这不是重点,不展开。

步6:将步5计算出的新的“已取数据指针”值,Store到“已取数据指针”中。“已取数据指针”是共享内存变量,它被消费媛C1修改,站在消费媛C1角度,它是“我的”。

结论相信大伙能看出来,“读我的 读你的 读你的 写我的”,这是个“load load load store”序列,CPU不会将它们乱序,不需要内存屏障。(主要指x64微架构下的TSO内存模型,ARM/RSIC-V需要内存屏障,具体需要参阅CPU手册)

最终结论,不存在“生产媛还没写完数据,消费媛就开始读数据”,也不存在,“消费媛还没读完数据,生产媛就开始覆盖数据”,等等情况。

当一龙一凤时,只有一个生产媛-消费媛时,不单不需锁,连内存屏障也不需要(x64微架构,TSO内存模式情况下,其他微架构请查阅手册,后文不再备注)。

下面继续讨论更复杂的情况,生产者、消费者是多个时的情况。

终于要说到双飞和3P了,激动不。    

主要说说双飞吧,3P其实我不怎么感冒:

两个产生媛对食品进行粗加工,消费媛接收到粗加工后的Data,进一步精细化处理。

站在CPU角度,双飞之后,一定是需要锁的。3P,或多个消费媛,其实和双飞一样,都需要锁。

所谓的“无锁”,是在程序角度上,以不阻塞的方式工作。有“锁”怎么能不阻塞呢?

当然可以了,你看到前面有个红灯,你不想被阻塞,可以右转弯,绕过去吗。

怎么个绕法,怎么从CPU角度有“锁”,从程序角度又“无锁”?

看图7:    

7

图中生产媛有N个,我们重点聊两个P1、P2。更多生产媛时要考虑的问题其实是一样的。

如图7所示,现在指针又多了一个:写入数据指针,假设生产媛P2,向RingBuffer中写入了Data 1,过程如下:

1:假设Data 1长度为Len,修改可用空间指针,向下移动Len字节。这一步就是在RingBuffer中分配空间。步1和步2对应图7右上第二幅小图。

2:得到空间后,P2RingBuffer中写入Data 1。对应图7右上第二幅小图。

3:写入完毕,修改写入数据指针,指向Data 1末尾。对应图7左下第三小图。

这里的写入数据指针,明显就是单生产者时的可用空间指针。作用是让消费媛C1知道,已经有新的Data写入了。

比单生产媛时,多了步1,分配空间的步骤。先分配、再写入。因为有多个生产媛吗,大家向一个地方写,不就相互覆盖了吗,所以需要先分配空间。    

好,现在考虑步1到步3,那一步需要锁?

当然就是1”分配空间这步了。

8

如图8所示,P1Pn,多个生产者进/线程进可以同时读取、并修改可用空间指针的。

我这里说的锁,是CPU层面的,比如x64微架构中的LOCK前缀。在用户层程序层面,其实没有,只是需要重试

具体流程是这样的:

1P1Pn,同时读取可用空间指针,假设是Address_A

2P1Pn,各自加上自己要写数据的长度,得到Addrees_1P1的新地址)、Address_2P2的新地址)……    

3P1Pn,同时执行带有LOCK前缀的比较并交换指令:LOCK cmpxchg Address_。。。, (mem) ”

对于P1来说:

比较可用空间指针,是否仍为Address_A,如果是,修改可用空间指针为自己的新地址:Address_1

P2也一样:

比较可用空间指针,是否仍为Address_A,如果是,修改可用空间指针为自己的新地址:Address_2

直到Pn,都一样。

这里CPU当然会有一个仲裁机制,假设经过仲裁,P2LOCK cmpxchg”成功执行,可用空间指针将被改为Address_2P1Pn其他生产者进/线程的LOCK cmpxchg”将返回失败(通过判断 RAX寄存器的值,可以知道是成功还是失败)。

失败了也没关系:    

9

如图9所示,P2成功修改了可用空间指针,得到了空间。它向RingBuffer中写Data 1

P1Pn继续抢着修改可用空间指针

CPU层面,LOCK当然是有的,但在用户层程序层面,没有进/线程被阻塞,没有得到空间,只不过需要重试一次而已,这就是“无锁”。

无锁指的是程序不会被阻塞,并不是真的不需要锁。

“阻塞”这东西,对于CPU来说,属于高端操作,普通指令都不阻塞,只不过会“失败”。

比如“LOCK cmpxchg”,它有锁,但它不会被“阻塞”、转入Sleeping,它会成功、失败。

它失败后,程序端可以根据情况,重试,或转入Sleeping。

如果重试,就是“无锁”编程。

如果转入Sleeping,就是“有锁”编程。

好了,具体关于无锁的,还可以参考这两篇:

一文彻底搞懂Lockfree/Lockless

还有知乎上的文章:

《无锁的线程池和内存池还有无锁的队列的设计思路是什么呢?》

https://www.zhihu.com/question/374142552/answer/3401692614

《C++无锁(lock free)数据结构与有锁数据结构相比,速度,性能等有何区别?多线程中如何选择?》

https://www.zhihu.com/question/558986994/answer/3498768792

另外还有一篇锁原理的:

《C++的锁是如何实现的?》

https://www.zhihu.com/question/5646769945/answer/58376766011


文章转载自IT知识刺客,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论