最近越来越感觉到坚持写 Blog 不是一件容易的事情,先前立下的每周至少更新一篇的目标也没有完成;leveldb 的系列也一直拖着没有继续,这个要自我反省一下。 这段时间工作之余在慢慢地看 perfbook ,个人感觉收获颇多。尽管书中很多内容涉及到了底层体系结构,操作系统和编译系统,在平时的工作中极少会使用到;但是书中所提出的各种设计思想和思考问题的方式,给我带来了很多启发,也为后续学习很多新东西打下了基础。举个例子,最近百度开源了其内部使用的 rpc 框架 brpc,今天扫描了一下其中 bvar 的实现,发现完全就是 perfbook 中 counting 所使用的 data ownership 设计思想,如果有相应的模式在脑海里,理解起来非常容易。 有关 perfbook 中更多细节,以后再慢慢道来。今天这篇文章所关注的主题 – Memory reordering 以及 Memory barrier 也由 perfbook 和 leveldb 中引出,与 lock-free algorithm 息息相关。尽管这个主题涉及到 Cache coherence 协议,CPU 体系结构,Sequential consistency 概念等问题,看起来非常底层,但是一旦深入理解,对于后续编程和学习必定大有帮助。 Memory reordering对于很多人来说,Memory reordering 是一个非常陌生的词。在我们日常的编程过程中,它可能没有发生过;或者它发生了,但是我们从未意识到它的存在。Memory reordering 翻译成中文就是内存乱序,我们可以将这种现象描述如下:
你可能会觉得这个表现非常反直觉,从而产生疑惑–如果读写内存操作不按照定义的顺序执行,程序的效果不会受到影响吗?事实上,这是一个非常重要的问题,其表明了 Memory reordering 并不能随意地无条件地产生。因此,在介绍 Memory reordering 的详细内容之前,我们需要指出其产生的前提:从单个线程的角度来看,任何一段程序在 Reordering 前与 Reordering 后,拥有相同的执行效果。这段话不是太好理解,我们会在后续内容中结合实例来解释其含义。 Compiler Reordering任何一个程序都需要经过编译才能运行到 CPU 上,而在编译和运行阶段都”可能”产生 Memory reordering。我们把编译阶段产生的乱序称为 Compiler Reordering(编译乱序),也即 Software memory reordering;把产生于运行阶段的乱序被称为 CPU memory reordering,也叫做 Hardware memory reordering。这一小节我们先来介绍编译乱序。 注意:很多不甚了解 Memory Reordering 的人可能会混淆这两个概念,或者认为它们等价。事实上,对于不同体系架构(eg. 单核,多核,Intel-arch 或 ARM),Compiler Reordering 与 CPU reordering 有本质的区别。 编译乱序很好理解,即在编译阶段,编译器为了优化程序的执行效率,自行地将内存操作指令重排,从而使得读写内存的指令与程序定义的操作顺序不一致。我们通过一个例子来证明 Compiler Reordering 的存在。对于如下简单的 c 程序:
在 CentOS 6 with gcc 4.4.7 环境下通过命令编译
通过以上注释可以看到,汇编代码严格按照程序中定义顺序执行 load 和 store 指令,即先保存变量 OK,接下来我们使用编译指令
可以看到,汇编指令先执行变量 Compiler Reordering 是编译器为了提高程序的执行效率而故意产生的。但是在很多时候,我们希望避免这种乱序的发生,即告诉编译器不应产生乱序。一般而言有两种方式来阻止编译器产生乱序,即显式的内存屏障(memory barrier)和隐式的内存屏障。 对于 GCC 及 clang 编译器而言,我们可以使用如下指令来显示地阻止编译器产生乱序:
需要指明的是,上述的 除了上述显示的 barrier() 以外,程序中的其他元素,例如同步原语(e.g. Mutex,RWLock,信号量,CPU 屏障等),非 inline 函数以及 C++11 提供的 non-relaxed 原子操作等均可以扮演 compiler barrier 的作用。关于 C++11 提供的内存模型和原子操作,后续有时间再专门介绍。 CPU memory reordering介绍完编译乱序,接下来我们再来看一下运行时产生的乱序,即 CPU memory reordering,也被称为 Hardware memory reordering。相比于编译乱序而言,CPU 乱序的产生背景以及对程序的影响都要更为复杂,其涉及到了 CPU 体系结构以及 cache coherence 协议。当然,要把所有的东西都说明白可能需要一篇很长的文章,这里我们尽量先用简单的例子来证明 CPU reordering 的存在,然后介绍一下几种不同的 CPU reordering 的类型以及相应的 barrier。关于 CPU reordering 的产生原因,后面再用一篇文章细细讲解。 对于如下的两个程序 P1 和 P2,假设 X 和 Y 的值初始均为 1, 且 P1 和 P2 分别由两个线程运行在一个双核 CPU 上,我们的问题是:两个线程并行执行得到的
大多数人可能都会认为 如果你是一个主动思考的人,看到这里一定会有一个疑问:这种 CPU 产生的乱序难道没有违背先前所制定的产生 memory reordering 的前提吗?为了清楚地说明这个问题,我们再重申一下任何体系架构产生 memory reordering 的前提要求:
我们分别看执行 P1 和 P2 的两个线程,如果我们从 P1 的线程角度角度来看,先执行指令 1 还是 指令 2 对 P1 本身来讲没有任何影响;同样的,如果单从 P2 的角度来看,先执行指令 1 还是 指令 2 对其本身也没有任何影响,因此这种乱序完全满足上述的前提。(这个例子也充分解释了什么叫做”从单线程的角度”)。 接下来我借用 Preshing 的代码来证明 CPU memory reordering 的存在。为了支持在 MacOS 下的运行,用 程序的主体通过两个线程分别执行如下程序,也就是完整地实现了上述关于 X 和 Y 的伪代码:
然后主程序进行如下同步,其执行多次地循环来输出
可以看到 main 函数通过 修改
即出现了 22308 次 CPU 乱序,如果设置 CPU memory barrierCPU 对内存的操作共分两种,分别是 load 和 store,因此在理论上存在四种 CPU 内存乱序:Load-Load,Load-Store,Store-Store,Store-Load 乱序(在 DEC Alpha 上会出现另一种 Dependent Loads 乱序,鉴于这种乱序在现代 CPU 体系结构不会出现,这里也不再过多强调)。我们用『理论上』三个字的原因是:在不同的硬件内存模型上,可能产生的内存乱序的种类并不相同。在 Strongly-ordered memory 环境例如 X86/X64 下,唯一允许产生的乱序是 Store-Load 乱序。(由 write buffer 的存在而产生)。 针对四种不同的 CPU 内存乱序,也应该存在对应的四种 barrier。然而针对 Intel CPU 而言,我们主要讨论三种内存 Barrier:
我们可以通过 CPU 提供的如下的指令来显示的达到 Barrier 的目的:
同时,任何带有
我们也可以将 Compiler Barrier 和 CPU Barrier 通过一条指令来实现:
最后需要说明的是,不同于编译屏障,CPU 内存屏障是在 CPU 上执行的指令,任何在程序中定义的 CPU 屏障最后都会编译成为汇编代码中的指令,例如,使用上面的 更多内容有关 memory reordering 的简介到这里就先结束了。涉及到内存模型,还有非常多额外的内容,例如
这其中的每一条都可以花一整篇文章来写,后续有时间,我们慢慢来完善这一块的内容。 |
|
来自: astrotycoon > 《待分类》