从JVM并发看CPU内存指令重排序(Memory Reordering)

 

我们都知道，现在的计算机， cpu 在计算的时候，并不总是从内存读取数据，它的数据读取顺序优先级是：寄存器－高速缓存－内 存。线程耗费的是 CPU ，线程计算的时候，原始的数据来自内存，在计算过程中，有些数据可能被频繁读取，这些数据被存储在寄存器和高速缓存中，当线程计算 完后，这些缓存的数据在适当的时候应该写回内存。当个多个线程同时读写某个内存数据时，就会产生多线程并发问题，涉及到三个特性：原子性，有序性，可见性。

本文转自：http://kenwublog.com/illustrate-memory-reordering-in-cpu

这两天，笔者拜读了 Dennis Byrne 写的一片博文  Memory Barriers and JVM Concurrency ( 中译文  内存屏障与 JVM 并发 ) 。

文中提到 :

对主存的一次访问一般花费硬件的数百次时钟周期。处理器通过缓存（ caching ）能够从数量级上降低内存延迟的成本这些缓存为了性能重新排列待定内存操作的顺序。也就是说，程序的读写操作不一定会按照它要求处理器的顺序执行。

这段话是作者对内存屏障重要性的定义。通过 cache 降低内存延迟，这句话很好理解。但后面那句 “ 为了性能重排序内存操作顺序 ” ，让没学好微机原理的我倍感疑惑。

CPU 为何要重排序内存访问指令？在哪种场景下会触发重排序？作者在文中并未提及。

为了解答疑问，我在网上查阅了一些资料，在这里跟大家分享一下。

1. 重排序的背景

我们知道现代 CPU 的主频越来越高，与 cache 的交互次数也越来越多。当 CPU 的计算速度远远超过访问 cache 时，会产生 cache wait ，过多的 cache  wait 就会造成性能瓶颈。
针对这种情况，多数架构（包括 X86 ）采用了一种将 cache 分片的解决方案，即将一块 cache 划分成互不关联地多个 slots ( 逻辑存储单元，又名 Memory Bank 或 Cache Bank) ， CPU 可以自行选择在多个 idle bank 中进行存取。这种 SMP 的设计，显著提高了 CPU 的并行处理能力，也回避了 cache 访问瓶颈。

Memory Bank 的划分
一般 Memory bank 是按 cache address 来划分的。比如 偶数 adress 0×12345000  分到 bank 0, 奇数 address 0×12345100  分到 bank1 。

重排序的种类
编译期重排。编译源代码时，编译器依据对上下文的分析，对指令进行重排序，以之更适合于 CPU 的并行执行。

运行期重排， CPU 在执行过程中，动态分析依赖部件的效能，对指令做重排序优化。

2. 实例讲解指令重排序原理

为了方便理解，我们先来看一张 CPU 内部结构图 :

 

从图中可以看到，这是一台配备双CPU 的计算机，cache 按地址被分成了两块 cache banks ，分别是 cache bank0 和 cache bank1 。

理想的内存访问指令顺序：
1 ，CPU0 往 cache address 0×12345000 写入一个数字 1 。因为address 0×12345000 是偶数，所以值被写入 bank0.
2 ，CPU1 读取 bank0 address 0×12345000 的值，即数字1 。
3 ，CPU0 往 cache 地址 0×12345100   写入一个数字 2 。因为address 0×12345100 是奇数，所以值被写入 bank1.
4 ，CPU1 读取 bank1 address  0×12345100 的值，即数字2 。

重排序后的内存访问指令顺序：
1 ，CPU0 准备往 bank0 address 0×12345000 写入数字 1 。
2 ，CPU0 检查 bank0 的可用性。发现 bank0 处于 busy 状态。
3 ， CPU0 为了防止 cache 等待，发挥最大效能，将内存访问指令重排序。即先执行后面的 bank1 address 0×12345100 数字2 的写入请求。
4 ，CPU0 检查 bank1 可用性，发现bank1 处于 idle 状态。
5 ，CPU0 将数字2 写入 bank 1 address 0×12345100 。
6 ，CPU1 来读取  0×12345000 ，未读到 数字1 ，出错。
7 ， CPU0 继续检查 bank0 的可用性，发现这次 bank0 可用了，然后将数字1 写入 0×12345000 。
8 ， CPU1 读取 0×12345100 ，读到数字2 ，正确。

从上述触发步骤中，可以看到第 3 步发生了指令重排序，并导致第 6 步读到错误的数据。

通过对指令重排，CPU 可以获得更快地响应速度， 但也给编写并发程序的程序员带来了诸多挑战。
内存屏障是用来防止CPU 出现指令重排序的利器之一。
通过这个实例，不知道你对指令重排理解了没有？

3. 不同架构下的指令重排优化

从图中，可以看到，X86 仅在 Stores after loads 和 Incoherent instruction cache pipeline 中会触发重排。

Stores after loads 的含义是在对同一个地址进行读写操作时，写入在读取后面，允许重排序。即满足弱一致性(Weak Consistency) ，这是最可被接受的类型，不会造成太大的影响。

Incoherent instruction cache pipeline 是跟JIT 相关的类型，作用是在执行 self-modifying code 时预防JIT 没有flush 指令缓存。我不知道该类型跟指令排序有什么关系，既然不在本文涉及范围内，就不做深入探讨了。

 

转载请注明原文链接：http://kenwublog.com/illustrate-memory-reordering-in-cpu

参考资料

http://kenwublog.com/docs/memory.barrier.ppt
http://kenwublog.com/docs/memory.model.instruction.reordering.and.store.atomicity.pdf
http://kenwublog.com/docs/memory.ordering.in.modern.microprocessor.pdf
http://en.wikipedia.org/wiki/Memory_ordering
http://en.wikipedia.org/wiki/Memory_Bank