简单理解计算机内存乱序
作者 | 后端技术小牛说 责编 | 张文头图 | CSDN下载自视觉中国本文探讨了自己对内存一致性模型的理解,由于不可避免的需要和操作系统底层打交道,本文主要例子和代码是 C++ ...
作者 | 后端技术小牛说 责编 | 张文
头图 | CSDN 下载自视觉中国
本文探讨了自己对内存一致性模型的理解,由于不可避免的需要和操作系统底层打交道,本文主要例子和代码是 C++ 和汇编语言,但这些例子都不难,针对代码也有配套性的讲解,使用别的语言的读者们也可以基本读懂。
内存乱序
作为一个程序员,最让人安心的事可能就是我们认为机器会忠实的一句句执行自己的代码来实现特定的功能。这种“掌控感”使我们非常踏实,一切 bug 皆有源,无法解释的状况理论上是不存在的。
但当我们接触到复杂的多线程编程时,尤其是尝试使用无锁的方案来保护共享数据时,很多 bug 就浮现出来了。我们一句句的去在自己的代码里去排查,会发现假如程序真的按照我们写的顺序一句句执行,是不会产生那些错误的。这让我们不由得怀疑起来,程序真的是按照我们写的顺序执行的吗?
很遗憾,在某些情况下,程序指令的执行顺序会发生改变,这就产生了我们所说的内存乱序问题。
内存顺序描述了计算机 CPU 获取内存的顺序,内存乱序即程序并未按照写定的内存获取顺序获取内存数据。而且对于不同类型的 CPU 和开发工具链的组合,内存乱序出现的时机和位置还不一致。在一个平台上测试完成的多线程代码,可能换个编译环境或者是硬件平台,就会产生 bug。
既然内存乱序那么常见,为什么在自己快乐的写单线程代码时,丝毫没有察觉到它的存在呢?
这是因为,不管由于何种原因产生内存乱序,都要遵循一个基本的原则,这个原则就是单线程程序的行为是稳定的。
这意味着不管怎么内存乱序,都不会对单线程的执行结果产生影响。
刚开始学习多线程编程时,通常使用锁来保护线程间的共享数据时,也一直都没有发现问题,这又是为什么呢?
由于锁之类的同步操作在调用点时主动强化了对内存访问顺序的要求,禁止了可能对程序执行结果有影响的乱序形式,内存乱序对程序结果的影响同样被掩盖了。
同时互斥量、信号量和事件都在设计的时候就阻止了它们调用点中的内存乱序。
在语言层面提供的这些多线程并发技术,掩盖住了内存乱序带来的问题。
但当我们追求更高的性能时,想避免加锁和解锁时可能陷入系统调用这个耗时操作,而采用无锁编程模式。
用多个线程之间的共享变量的值来指示各个线程的执行状态,来解决多线程访问冲突,内存乱序的问题便浮现出来。
![](https://i-blog.csdnimg.cn/blog_migrate/759d2741998eac7c7dde29dbda9b0c09.png)
内存乱序
摆脱了高级语言带来的枷锁,也代表着割舍了它的便利性。我们需要直面更加底层的知识,只有充分认识内存乱序的内部机制,我们才能更好的解决它带来的问题。
其实,解决内存乱序带来的问题也没有多么巧妙的地方,识别出必须按序执行的代码段,增加指令在各个层次上避免乱序就可以实现。
为什么会产生内存乱序呢?
程序在机器上执行的时候,主要的三个操作就是读取数据、执行计算、存储数据。
配合着各种总线协议、十几级的流水线和各种计算单元来实现这三类操作。
我们程序员对硬件的执行知道的并不多,写的代码就是自己逻辑的再现,它们对于硬件来说,肯定是不能最大化资源的利用率的。
为了提高程序的执行效率,编译器和 CPU 都会对指令的执行顺序进行“微操”,识别出代码中不存在相互依赖的指令,调整其执行顺序,来最大化总线带宽利用率。
编译器是通过生成对应机器指令时,将指令重排序。而 CPU 则通过乱序执行技术,将不存在相互依赖的指令,同时将其发射到多个逻辑单元执行。
两者是相互搭配来最优化程序的执行效率的。编译器能在相对更大的范围内进行代码分析,但不能知道程序运行时的具体情况,CPU 能够根据当前的执行情况动态的调整指令执行顺序,但它的“可视范围”有限,不能大范围内调整。
除了这两个原因,在现在的多核机器上,由于有缓存层的存在,数据的变化不能及时反映在主存,这也会带来乱序现象。
虽然有缓存一致性协议来保证多核间缓存数据的一致性,但由于有一些其它的优化措施的存在,还是会在某些特定的情况下产生乱序,在下面会进行举例说明。
小牛先带大家看看这些地方是怎么产生内存乱序的。
编译期间乱序
我们来看下面一段简单的代码,使用简单的加法和赋值操作,复现指令顺序调整的现象。
int x = 0;int y = 0;void testCompilerReOrder() { x = y + 1; y = 0;}
我们使用编译器是 MSVC,在 Debug 版本,testCompilerReOrder 函数对应的汇编代码为:
;----------------------------------------------------------------------------------
; 计算 x = y + 1;
;----------------------------------------------------------------------------------
mov eax,dword ptr [y (0E4A13Ch)] ; 把内存中存y的值存在eax寄存器
add eax,1 ; 让eax寄存器的值加1
mov dword ptr [x (0E4A138h)],eax ; 把eax寄存器值放到x变量对应的内存位置中
;----------------------------------------------------------------------------------
; 计算 y = 0;
;----------------------------------------------------------------------------------
mov dword ptr [y (0E4A13Ch)],0 ; 把y赋值为0
多说一句,在计算机底层变量操作的话,不能针对内存中存的数据直接修改,需要先将内存中的值拷贝到寄存器,寄存修改完再写回回内存,这样才能完成变量值的更新工作。
上述的汇编代码可以看出,在 debug 模式下,汇编代码并没有改变我们的代码的执行顺序。
在 release 版本(需要在项目属性里设置禁止内联优化)下,汇编代码:
;----------------------------------------------------------------------------------
; 计算 x = y + 1;
;----------------------------------------------------------------------------------
mov eax,dword ptr [y (0E93380h)] ; 把内存中存y的值存在eax寄存器
inc eax ; 让eax寄存器的值加1
;----------------------------------------------------------------------------------
; 计算 y = 0;
; 发生指令顺序调整
;----------------------------------------------------------------------------------
mov dword ptr [y (0E93380h)],0 ; 把y赋值为0
mov dword ptr [x (0E9337Ch)],eax ; 把eax寄存器值放到x变量对应的内存位置中
这次的汇编代码,就可以看出指令的顺序被调整了,先存储 y 的值,再存储 x 的值。这样的调整,在单线程执行时,不会有任何问题,但是在编写不使用锁的多线程代码时,就会产生一系列的问题了.
int value;int isPublished = 0;//线程1运行sendValuevoid sendValue(int x){ value = x; isPublished = 1;}//线程2运行receiveValueint receiveValue(){ if (isPublished){ return value; } return -1; }
观察上面的代码,线程 1 执行sendValue函数,线程 2 执行 receiveValue 函数,在线程 1 看来,value 变量和 isPublished 变量没有任何的数据依赖关系,编译器完全有可能先存储变量 isPublished 的值,再存储变量 value 的值。
这样线程 2 看到变量 isPublished 被修改后,就返回了 value 的值,而这时候 value 的值可能还没有被线程 1 修改,就导致 receiveValue 函数的返回值是一个不确定的状态,违背了代码本来的意图。
![](https://i-blog.csdnimg.cn/blog_migrate/ff7da9ddca69a0e1728898491cd1a79a.png)
编译期间乱序
怎样来消除编译器的内存乱序问题呢?
我们可以使用一些指令,来避免编译器对指令进行重排。在 Microsoft Visual C++ 中,我们使用_ReadWriteBarrier 函数来实现这样的功能,在 release 版本的代码上加上该指令,可以看到指令重排消失了:
;----------------------------------------------------------------------------------
; 计算 x = y + 1;
;----------------------------------------------------------------------------------
mov eax,dword ptr [y (0763380h)] ; 把内存中存y的值存在eax寄存器
inc eax ; 让eax寄存器的值加1
mov dword ptr [x (076337Ch)],eax ; 把eax寄存器值放到x变量对应的内存位置中
;----------------------------------------------------------------------------------
; _ReadWriteBarrier();
; 计算 y = 0;
;----------------------------------------------------------------------------------
mov dword ptr [y (0763380h)],0 ; 把y赋值为0
对于编译器优化,只保证了单线程下程序执行的正确性,但当代码放到多线程的情况下,可能就会由于编译器的优化而产生错误。
CPU 执行期间乱序
了解了编译时的乱序问题,下面我们再来了解一下另外一个可以调整指令执行顺序的窗口——CPU 执行期间。
现代 CPU 可以根据当前的执行情况,灵活地调整不具有相关性的读写指令的执行顺序,这个很好理解,下图显示的是一个线程的执行代码:
![](https://i-blog.csdnimg.cn/blog_migrate/25cab8fa37fe89b37d58f75e9f1dd3f6.png)
CPU 执行期间乱序
(注:r1和r2表示处理器中的寄存器)
程序首先对变量 X1、X2、Y1、Y2 初始化,然后线程 1 按照某种顺序执行①②③④这四条指令。
由于四条语句操作的变量相互之间没有关联性,按理来说 CPU 可以根据自身的硬件结构和当前的执行情况,自由的组合其执行顺序,这对线程 1 作为单线程的执行结果不会产生什么不利影响,因此有着 24 种不同的组合方式。
但在真实的 CPU 中,其组合并不是乱序的,而是遵从一定的约束的。
这种在一个具有多个处理核心的计算机上,采用读写共享内存作为数据共享方式,规定其它处理器何时能看到本处理器对于一个变量的写操作的模型,称为内存一致性模型。
在 linux 系统下,对于单核心的系统,不会涉及到内存一致性的问题。即使多线程的且线程间需要数据共享的程序跑在单核的系统上一般也不会有什么问题。因为对单核处理器有两个前置条件:
单核不具有多核处理中存在的缓存一致性问题。
在单核 cpu 上乱序执行指令的线程在被调度出去发生上下文切换时,会把乱序的指令流水撤销或者提交。
对于一个采用消息传递作为数据共享方式的系统中,是没有内存一致性模型这个问题的;
为什么强调写操作,这是因为对于其它核心来说,你何时读取并不会对自己产生什么影响。是我不 care 的事。
规定着其它处理器何时能看到本处理器对于一个变量的写操作,这就说明着,在不同的内存一致性模型下,其它处理器可能看到的本处理器的程序指令的执行顺序和代码的编写顺序可能是不一样的,而且,作为观察者的处理器之间,看到的本处理器的指令执行顺序可能也是不一样的。
陈述一下几个基本概念(①->②代表①先于②执行,其它类似):
不满足①->②的执行顺序时,叫作写读乱序;
不满足②->③的执行顺序时,叫作读写乱序;
不满足①->③的执行顺序时,叫作写写乱序;
不满足②->④的执行顺序时,叫作读读乱序。
下面介绍几种内存一致性模型:
内存一致性模型
我们使用的计算机主要是基于 Intel x86/x64 的,这是个强内存模型的架构,不容易发现内存乱序的问题,本节的主要任务就是把 Intel x86/x64 下的 CPU 执行导致的内存乱序抓出来。
根据文档 Intel® 64 and IA-32 Architectures Software Developer’s Manual 中的例子,
Intel® 64 and IA-32 Architectures Software Developer’s Manual
两个线程的四个语句,r1 和 r2 的值总共有 4 种组合方式,下表反映的是不同内存一致性模型下的最终 r1 和 r2 的值:
可能的结果
两个线程运行在两个处理器上,每个处理器将 1 写入其中一个整型变量中,然后将另一个整型变量读取到寄存器中。现在不管哪个处理器先将 1 写入内存,都想当然地认为另一个处理器会读到这个值,这就意味着最后结果中要么 r1=1,要么 r2=1,要么这两个结果同时满足。但根据 Intel 手册,却不是这么回事。手册上说在这个例子里,最终 r1 和 r2 的值都有可能等于 0。
Intel x86/x64 处理器,和大部分处理器家族一样,在保证不改变一个单线程程序执行结果的基础上,会根据一定的规则将机器指令对内存的操作顺序重新排序。具体来说,对于不同内存变量的写读操作,处理器保留乱序的权利。
有想复现这个现象的同学可以利用下面代码,只想看文章的跳过这段哈:
int X, Y;int r1, r2;atomic<int> cnt1 = 0;atomic<int> cnt2 = 0;atomic<int> flag = 1;void thread1Entry() { while (1) { while (cnt1.load() == 0) {} cnt1--; while (rand() % 8 != 0) {} // 随机延时 X = 1; _ReadWriteBarrier(); //阻止编译器乱序 r1 = Y; if (cnt2.load() == 0) { flag.store(1); } }}void thread2Entry() { while (1) { while (cnt2.load() == 0) {} cnt2--; while (rand() % 8 != 0) {} Y = 1; _ReadWriteBarrier(); //阻止编译器乱序 r2 = X; if (cnt1.load() == 0) { flag.store(1); } }}int main() { thread thread1 = thread(thread1Entry); thread thread2 = thread(thread2Entry); int detected = 0; for (int iterations = 1; iterations < 10000; iterations++){ // 重置X和Y X = 0; Y = 0; //通知开启线程 cnt1.store(1); cnt2.store(1); //等待线程执行完一轮次的处理 while (flag.load() == 0) {} flag.store(0); //检查是否存在内存乱序 if (r1 == 0 && r2 == 0){ detected++; cout << "发现 " << detected << " 次乱序在 " << iterations << " 次迭代后"<< endl; } } getchar(); return 0; }
程序的执行结果:
结果
从程序的执行结果中,我们能够侦测到很多次程序执行时的指令重排现象。为什么 CPU 要在这里对指令进行重排呢?是因为 CPU 执行过程中真的先读后写了吗?在下个小节里小牛将进行解释。
缓存带来的乱序
上一节我们观察到了 Intel x86/x64 下的写读乱序的情况,本小节我们来分析一下这种内存乱序的产生原因。
首先我们来看一下常见计算机的存储模型:
存储模型
可以看到在内存和 CPU 之间有 cache 缓存层。加入缓存层的原因,就是为了弥补 CPU 处理速度与内存的访问速度之间的巨大鸿沟。我们写的程序都具有两个特性:
时间局部性(当前访问的内存位置一会有很大机率再次被访问)
空间局部性(当前访问的内存位置的前后内存单元一会有很大机率被访问)
由于这两个特性的存在,我们可以使用访问速度更快的 SRAM 做 cache,作为内存的缓存,来加快程序的执行速度。
这里插一个题外话,现在的计算机的系统优化的大部分都花在了优化数据的读写速度了,为什么呢?这是由于其它组件很难跟得上 CPU 的处理速度,下面图中的数据会给我们提供一个更加感性的认识:
假设计算机的每个时钟周期为 1 秒的话,计算机中其他部分的处理时间可以估计为:
cache 看起来的执行顺序已经够快了,但由于每个 cpu core 有自己的私有的 cache (有一级 cache 是共享的),而 cache 只是内存的副本。那么这就带来一个问题:如何保证每个 cpu core 中的 cache 是一致的?
这就要用到广泛使用的 缓存一致性协议即 MESI 协议了。这个协议在之前的文章中讲过。
当某个 cpu core 写一个内存变量时,往往是先修改 cache,那么这就会导致不同核心间的缓存数据不一致。为了保证缓存数据的一致性,需要先把其他 core 的对应的 cacheline 都 invalid 掉,给其他 core们发送 invalid 消息,然后等待它们的 response。
这个过程是耗时的,需要执行写变量的 core 等待,阻塞了它后面的操作。为了解决这个问题,cpu core 往往有自己专属的 store buffer。
在 L1 Cache 命中的情况下,访问数据一般需要 2 个指令周期。而且当 CPU 遭遇写数据 cache 未命中时,内存访问延迟增加很多。
硬件工程师为了追求极致的性能,在 CPU 和 L1 Cache 之间又加入一级缓存,我们称之为 store buffer。store buffer 和 L1 Cache 还有点区别,store buffer 只缓存CPU的写操作。store buffer 访问一般只需要 1 个指令周期,这在一定程度上降低了内存写延迟。不管 cache 是否命中,CPU 都是将数据写入 store buffer。store buffer 负责后续以 FIFO 次序写入 L1 Cache。store buffer 大小一般只有几十个字节。大小相对于本来就小的 L1 Cache 还要小不少。
store buffer
等待其他 core 给它 response 的时候,就可以先写store buffer,然后继续后面的读操作,对外表现就是写读乱序。因为写操作是写到 store buffer 中的,而 store buffer 是私有的,对其他 core 是不可访问的,core1 无法访问 core2 的 store buffer。因此其他 core 读不到这样的修改。
我们可以看到,未写入 cache 的 store buffer 里的数据造成了写读乱序,一旦写入 cache,MESI 协议自动保证缓存数据的一致性。总结来说内存一致性模型和和缓存一致性的区别在于,内存一致性模型规定着其它处理器何时能够看到本处理器的修改,缓存一致性协议规定着其它处理器如何看到本处理器的修改。
这种写读乱序是我们唯一能从 Intel x86/x64 架构的机器上观察到的 CPU 执行的内存乱序。这里说的是写读乱序,而且是对不同变量的写读操作的乱序。在 Intel x86/x64 处理器中,读读、写写、读写、以及写读同一个内存变量,CPU 是不会乱序的。导致这种乱序的深层次原因是由于缓存中 store buffer 的存在,并不是 CPU 某个核心真的先写后读了,而是在其它核心看起来,这个核心的表现是先读后写了,产生了写读乱序。
参考:
http://chonghw.github.io/blog/2016/08/11/memoryreorder/
http://preshing.com/20120515/memory-reordering-caught-in-the-act/
https://www.codedump.info/post/20191214-cxx11-memory-model-1/
https://preshing.com/20120625/memory-ordering-at-compile-time/
https://zhuanlan.zhihu.com/p/141655129
http://highscalability.com/numbers-everyone-should-know
程序员如何避免陷入“内卷”、选择什么技术最有前景,中国开发者现状与技术趋势究竟是什么样?快来参与「2020 中国开发者大调查」,更有丰富奖品送不停!
更多精彩推荐 ☞支持 RISC-V 芯片的 Android 系统来了! ☞Rust 升级成微软第一梯队语言;“熊孩子”乱敲键盘攻破 Linux 桌面;500 个值得学习的 AI 开源项目| 开发者周刊 ☞英特尔火线换帅,苹果搅动乾坤,国芯路在何方? 点分享点收藏点点赞点在看
更多推荐
所有评论(0)