背景
在阅读 java 中 volatile 的关键词语义时, 发现很多书中都使用了重排序这个词来描述, 同时又讲到了线程工作内存和主存等等相关知识. 但是只用那些书的抽象定义进行理解时总是感觉什么地方说不通, 最后发现, 是那些书中使用的抽象屏蔽了一些对读者的知识点, 反而导致了理解上的困难. 因此有了这篇文章. 没有任何虚构的理解抽象, 从硬件的角度来理解什么是内存屏障, 以及内存屏障如何让 volatile 工作. 最后说明了在多线程中, 如何使用 volatile 来提升性能.
存储结构
在计算机之中, 存在着多级的存储结构. 这是为了适应不同硬件速度带来的差异. 底层是主存(也就是内存), 容量最大, 速度最慢; 中间是 cpu 的缓存(现代 cpu 都有多级缓存结构, 级别越高速度越慢, 但是可以将多级缓存看成是一个整体), 容量较小, 但是速度很快; 最上层是 cpu 自身的 store buffer 和 Invalidate Queues, 速度最快, 容量非常少. 其中主存和 cpu 缓存的数据视图对于每一个 cpu 都是相同的, 也就是说在这个级别上, 每个 cpu 都看到了相同的数据, 而 store buffer 和 Invalidate Queues 是每一个 cpu 私有的. 这就导致了一系列的编程问题, 下文会详细展开.
CPU 缓存
Cpu 为了平衡自身处理速度过快和主存读写速度过慢这个问题, 使用了缓存来存储处理中的热点数据. cpu 需要处理数据的时候(包含读取和写出), 都是直接向缓存发出读写指令. 如果数据不在缓存中, 则会从主存中读取数据到缓存中, 再做对应的处理. 需要注意的是, cpu 读取数据到缓存中, 是固定长度的读取. 也就是说 cpu 缓存是一行一行的载入数据进来. 因为也称之为 cpu 缓存行, 即 cacheline. 而缓存中的数据, 也会在合适的时候回写到主存当中(这个时机可以抽象的认为是由 cpu 自行决定的).
现在的 cpu 都是多核 cpu, 为了在处理数据的时候保持缓存有效性, 因此一个 cpu 需要数据而且该数据不在自身的 cache 中的时候, 会同时向其他的 cpu 缓存和主存求取. 如果其他的 cpu 缓存中有数据, 则使用该数据, 这样就保证了不会使用到主存中的错误的尚未更新的旧数据.
而各个 cpu 的内部缓存依靠 MESI 缓存一致性协议来进行协调. 以此保证各个 Cpu 看到的内容是一致的.
Store buffer
如果一个 Cpu 要写出一个数据, 但是此时这个数据不在自己的 cacheline 中, 因为 cpu 要向其他的 cpu 缓存发出 read invalidate 消息. 等待其他的 cpu 返回 read response 和 invalidate ack 消息后, 将数据写入这个 cacheline. 这里就存在着时间的浪费, 因为不管其他的 cpu 返回的是什么数据, 本 cpu 都是要将它覆盖的. 而在等待的这段时间, cpu 无事可干, 只能空转. 为了让 cpu 不至于空闲, 因为设计了 store buffer 组件. store buffer 是每个 cpu 独享的写入缓存空间, 用于存储对 cacheline 的写入, 而且速度比 cacheline 高一个数量级, 但是容量非常少.
但是 store buffer 会产生在单核上的读写不一致问题. 下面是模拟
- a = 1;
- b = a+1;
- assert b==2;
假设 a 不在本 cpu 的 cacheline 中. 在其他 cpu 的 cacheline 中, 值为 0. 会有如下的步骤
序号操作内容 1 发现 a 的地址不在本 cpu 的 cacheline 中, 向其他的 cpu 发送 read invalidate 消息 2 将数据写入 store buffer 中 3 收到其他 cpu 响应的 read response 和 invalidate ack 消息 4 执行 b=a+1, 因为 a 这个时候已经在 cacheline 中, 读取到值为 0, 加 1 后为 1, 写入到 b 中 5 执行 assert b==2 失败, 因为 b 是 16store buffer 中的值刷新到 a 的 cacheline 中, 修改 a 的值为 1, 但是已经太晚了
为了避免这个问题, 所以对于 store buffer 的设计中增加一个策略叫做 store forwarding. 就是说 cpu 在读取数据的时候会先查看 store buffer, 如果 store buffer 中有数据, 直接用 store buffer 中的. 这样, 也就避免了使用错误数据的问题了.
store forwarding 可以解决在单线程中的数据不一致问题, 但是 store buffer 所带来的复杂性远不止如此. 在多线程环境下, 会有其他的问题. 下面是模拟代码
- public void set(){
- a=1;
- b=1;
- }
- public void print(){
- while(b==0)
- ;
- assert a==1;
- }
假设 a 和 b 的值都是 0, 其中 b 在 cpu0 中, a 在 cpu1 中. cpu0 执行 set 方法, cpu1 执行 print 方法.
序号 cpu0 的步骤(执行 set)cpu1 的步骤(执行 print)1 想写入 a=1, 但是由于 a 不在自身的 cacheline 中, 向 cpu1 发送 read invalidate 消息执行 while(b==0), 由于 b 不在自身的 cacheline 中, 向 cpu0 发送 read 消息 2 向 store buffer 中写入 a=1 等待 cpu0 响应的 read response 消息 3b 在自身的 cacheline 中, 并且此时状态为 M 或者 E, 写入 b=1 等待 cpu0 响应的 read response 消息 4 收到 cpu1 的 read 请求, 将 b=1 的值用 read response 消息传递, 同时将 b 所在的 cacheline 修改状态为 s 等待 cpu0 响应的 read response 消息 5 等待 cpu1 的 read response 和 invalidate ack 消息收到 cpu0 的 read response 消息, 将 b 置为 1, 因此程序跳出循环 6 等待 cpu1 的 read response 和 invalidate ack 消息因为 a 在自身的 cacheline 中, 所以读取后进行比对. assert a==1 失败. 因为此时 a 在自身 cacheline 中的值还是 0, 而且该 cacheline 尚未失效 7 等待 cpu1 的 read response 和 invalidate ack 消息收到 cpu0 发送的 read invalidate 消息, 将 a 所在的 cacheline 设置为无效, 但是 为时已晚, 错误的判断结果已经产生了 8 收到 cpu1 响应的 read response 和 invalidate ack 消息, 将 store buffer 中的值写入 cacheline 中无
通过上面的例子可以看到, 在多核系统中, store buffer 的存在让程序的结果与我们的预期不相符合. 上面的程序中, 由于 store buffer 的存在, 所以在 cacheline 中的操作顺序实际上先 b=1 然后 a=1. 就好像操作被重排序一样(重排序这个词在很多文章中都有, 但是定义不详, 不好理解. 实际上直接理解 store buffer 会简单很多). 为了解决这样的问题, cpu 提供了一些操作指令, 来帮助我们避免这样的问题. 这样的指令就是内存屏障(英文 fence, 也翻译叫做栅栏). 来看下面的代码
- public void set(){
- a=1;
- smp_mb();
- b=1;
- }
- public void print(){
- while(b==0)
- ;
- assert a==1;
- }
smb_mb()就是内存屏障指令, 英文 memory barries. 它的作用, 是在后续的 store 动作之前, 将 sotre buffer 中的内容刷新到 cacheline. 这个操作的效果是让本地的 cacheline 的操作顺序和代码的顺序一致, 也就是让其他 cpu 观察到的该 cpu 的 cacheline 操作顺序被分为 smp_mb()之前和之后. 要达到这个目的有两种方式
遇到 smp_mb()指令时, 暂停 cpu 执行, 将当前的 store_buffer 全部刷新到 cacheline 中, 完成后 cpu 继续执行
遇到 smp_mb()指令时, cpu 继续执行, 但是所有后续的 store 操作都进入到了 store buffer 中, 直到 store buffer 之前的内容都被刷新到 cacheline, 即使此时需要 store 的内容的 cacheline 是 M 或者 E 状态, 也只能先写入 store buffer 中. 这样的策略, 既可以提升 cpu 效率, 也保证了正确性. 当之前 store buffer 的内容被刷新到 cacheline 完成后, 后面新增加的内容也会有合适的时机刷新到 cacheline. 把 store buffer 想象成一个 FIFO 的队列就可以了.
下面来看, 当有了 smp_mb()之后, 程序的执行情况. 所有的初始假设与上面相同.
序号 cpu0 的步骤(执行 set)cpu1 的步骤(执行 print)1 想写入 a=1, 但是由于 a 不在自身的 cacheline 中, 向 cpu1 发送 read invalidate 消息执行 while(b==0), 由于 b 不在自身的 cacheline 中, 向 cpu0 发送 read 消息 2 向 store buffer 中写入 a=1 等待 cpu0 响应的 read response 消息 3 遇到 smp_mb(), 等待直到可以将 store buffer 中的内容刷新到 cacheline 等待 cpu0 响应的 read response 消息 4 等待直到可以将 store buffer 中的内容刷新到 cacheline 收到 cpu0 发来的 read invalidate 消息, 发送 a=0 的值, 同时将自身 a 所在的 cacheline 修改为 invalidate 状态 5 收到 cpu1 响应的 read response 和 invalidate ack 消息, 将 a=0 的值设置到 cacheline, 随后 store buffer 中 a=1 的值刷新到 cacheline, 设置 cacheline 状态为 M 等待 cpu0 响应的 read response 消息 6 由于 b 就在自身的 cacheline 中, 并且状态为 M 或者 E, 设置值为 b=1 等待 cpu0 响应的 read response 消息 7 收到 cpu1 的 read 请求, 将 b=1 的值传递回去, 同时设置该 cacheline 状态为 s 等待 cpu0 响应的 read response 消息 8 无收到 cpu0 的 read response 信息, 将 b 设置为 1, 程序跳出循环 9 无由于 a 所在的 cacheline 被设置为 invalidate, 因此向 cpu0 发送 read 请求 10 收到 cpu1 的 read 请求, 以 a=1 响应, 并且将自身的 cacheline 状态修改为 s 等待 cpu0 的 read response 响应 11 无收到 read response 请求, 将 a 设置为 1, 执行程序判断, 结果为真
可以看到, 在有了内存屏障之后, 程序的真实结果就和我们的预期结果相同了.
invalidate queue
使用了 store buffer 后, cpu 的 store 性能会提升很多. 然后 store buffer 的容量是很小的 (越快的东西, 成本就越高, 一定就越小),cpu 以中等的频率填充 store buffer. 如果不幸发生比较多的 cache miss, 那么很快 store buffer 就被填满了, cpu 只能等待. 又或者程序中调用了 smp_mb() 指令, 这样后续的操作都只能进入 store buffer, 而不管相关 cacheline 是否处于 M 或者 E 状态.
store buffer 很容易满的原因是因为收到其他 cpu 的 invalidate ack 的速度太慢. 而 cpu 发送 invalidate ack 的速度太慢是因为 cpu 要等到将对应的 cacheline 设置为 invalidate 后才能发送 invalidate ack. 有的时候太多 invalidate 请求, cpu 的处理速度就跟不上. 为了加速这个流程, 硬件设计者设计了 invaldate queue 来加速这个过程. 收到的 invalidate 请求先放入 invalidate queue, 然后之后立刻响应 invalidate ack 消息. 而 cpu 可以在随后慢慢的处理这些 invalidate 消息. 当然, 这里必须不能太慢. 也就是说, cpu 实际上给出了一个承诺, 如果一个 invalidatge 请求在 invalidate queue 中, 那么对于这个请求相关的 cacheline, 在该请求被处理完成前, cpu 不会再发送任何与该 cacheline 相关的 MESI 消息. 在有了 store buffer 和 invalidate queue 后, cpu 的处理速度又可以更高. 下面是结构图.
但是在引入了 invalidate queue 又会导致另外一个问题. 下面先来看代码
- public void set(){
- a=1;
- smp_mb();
- b=1;
- }
- public void print(){
- while(b==0)
- ;
- assert a==1;
- }
代码与上面的例子相同, 但是初始条件不同了. 这次 a 同时存在于 cpu0 和 cpu1 之中, 状态为 s.b 是 cpu0 独享, 状态为 E 或者 M.
序号 cpu0 的步骤(执行 set)cpu1 的步骤(执行 print)1 想写入 a=1, 但是由于 a 的状态是 s, 向 cpu1 发送 invalidate 消息执行 while(b==0), 由于 b 不在自身的 cacheline 中, 向 cpu0 发送 read 消息 2 向 store buffer 中写入 a=1 收到 cpu0 的 invalidate 消息, 放入 invalidate queue, 响应 invalidate ack 消息. 3 遇到 smp_mb(), 等待直到可以将 store buffer 中的内容刷新到 cacheline. 立刻收到 cpu0 的 invalidate ack, 将 store buffer 中的 a=1 写入到 cacheline, 并且修改状态为 M 等待 cpu0 响应的 read response 消息 4 由于 b 就在自己的 cacheline 中, 写入 b=1, 修改状态为 M 等待 cpu0 响应的 read response 消息 5 收到 cpu1 响应的 read 请求, 将 b=1 作为响应回传, 同时将 cacheline 的状态修改为 s. 等待 cpu0 响应的 read response 消息 6 无收到 read response, 将 b=1 写入 cacheline, 程序跳出循环 7 无由于 a 所在的 cacheline 还未失效, load 值, 进行比对, assert 失败 8 无 cpu 处理 invalidate queue 的消息, 将 a 所在的 cacheline 设置为 invalidate, 但是已经太晚了
上面的例子, 看起来就好像第一个一样, 仍然是 b=1 先生效, a=1 后生效. 导致了 cpu1 执行的错误. 就好像内存操作 "重排序" 一样(个人不太喜欢内存操作重排序这个术语, 因为实际上并不是重新排序的问题, 而是是否可见的问题. 但是用重排序这样的词语, 反而不好理解. 但是很多书都是用是了这个词语, 大家可以有自己的理解. 但是还是推荐不要理会这些作者的抽象概念, 直接了解核心). 其实这个问题的触发, 就是因为 invalidate queue 没有在需要被处理的时候处理完成, 造成了原本早该失效的 cacheline 仍然被 cpu 认为是有效, 出现了错误的结果. 那么只要让内存屏障增加一个让 invalidate queue 全部处理完成的功能即可.
硬件的设计者也是这么考虑的, 请看下面的代码
- public void set(){
- a=1;
- smp_mb();
- b=1;
- }
- public void print(){
- while(b==0)
- ;
- smp_mb();
- assert a==1;
- }
a 同时存在于 cpu0 和 cpu1 之中, 状态为 s.b 是 cpu0 独享, 状态为 E 或者 M.
序号 cpu0 的步骤(执行 set)cpu1 的步骤(执行 print)1 想写入 a=1, 但是由于 a 的状态是 s, 向 cpu1 发送 invalidate 消息执行 while(b==0), 由于 b 不在自身的 cacheline 中, 向 cpu0 发送 read 消息 2 向 store buffer 中写入 a=1 收到 cpu0 的 invalidate 消息, 放入 invalidate queue, 响应 invalidate ack 消息. 3 遇到 smp_mb(), 等待直到可以将 store buffer 中的内容刷新到 cacheline. 立刻收到 cpu0 的 invalidate ack, 将 store buffer 中的 a=1 写入到 cacheline, 并且修改状态为 M 等待 cpu0 响应的 read response 消息 4 由于 b 就在自己的 cacheline 中, 写入 b=1, 修改状态为 M 等待 cpu0 响应的 read response 消息 5 收到 cpu1 响应的 read 请求, 将 b=1 作为响应回传, 同时将 cacheline 的状态修改为 s. 等待 cpu0 响应的 read response 消息 6 无收到 read response, 将 b=1 写入 cacheline, 程序跳出循环 7 无遇见 smp_mb(), 让 cpu 将 invalidate queue 中的消息全部处理完后, 才能继续向下执行. 此时将 a 所在的 cacheline 设置为 invalidate8 无由于 a 所在的 cacheline 已经无效, 向 cpu0 发送 read 消息 9 收到 read 请求, 以 a=1 发送响应收到 cpu0 发送的响应, 以 a=1 写入 cacheline, 执行 assert a==1. 判断成功
可以看到, 由于内存屏障的加入, 程序正确了.
内存屏障
通过上面的解释和例子, 可以看出, 内存屏障是是因为有了 store buffer 和 invalidate queue 之后, 被用来解决可见性问题(也就是在 cacheline 上的操作重排序问题). 内存屏障具备两方面的作用
强制 cpu 将 store buffer 中的内容写入到 cacheline 中
强制 cpu 将 invalidate queue 中的请求处理完毕
但是有些时候, 我们只需要其中一个功能即可, 所以硬件设计者们就将功能细化, 分别是
读屏障: 强制 cpu 将 invalidate queue 中的请求处理完毕. 也被称之为 smp_rmb
写屏障: 强制 cpu 将 store buffer 中的内容写入到 cacheline 中或者将该指令之后的写操作写入 store buffer 直到之前的内容被写入 cacheline. 也被称之为 smp_wmb
读写屏障: 强制刷新 store buffer 中的内容到 cacheline, 强制 cpu 处理完 invalidate queue 中的内容. 也被称之为 smp_mb
JMM 内存模型
在上面描述中可以看到硬件为我们提供了很多的额外指令来保证程序的正确性. 但是也带来了复杂性. JMM 为了方便我们理解和使用, 提供了一些抽象概念的内存屏障. 注意, 下文开始讨论的内存屏障都是指的是 JMM 的抽象内存屏障, 它并不代表实际的 cpu 操作指令, 而是代表一种效果.
LoadLoad Barriers
该屏障保证了在屏障前的读取操作效果先于屏障后的读取操作效果发生. 在各个不同平台上会插入的编译指令不相同, 可能的一种做法是插入也被称之为 smp_rmb 指令, 强制处理完成当前的 invalidate queue 中的内容
StoreStore Barriers
该屏障保证了在屏障前的写操作效果先于屏障后的写操作效果发生. 可能的做法是使用 smp_wmb 指令, 而且是使用该指令中, 将后续写入数据先写入到 store buffer 的那种处理方式. 因为这种方式消耗比较小
LoadStore Barriers
该屏障保证了屏障前的读操作效果先于屏障后的写操作效果发生.
StoreLoad Barriers
该屏障保证了屏障前的写操作效果先于屏障后的读操作效果发生. 该屏障兼具上面三者的功能, 是开销最大的一种屏障. 可能的做法就是插入一个 smp_mb 指令来完成.
内存屏障在 volatile 关键中的使用
内存屏障在很多地方使用, 这里主要说下对于 volatile 关键字, 内存屏障的使用方式.
在每个 volatile 写操作的前面插入一个 StoreStore 屏障.
在每个 volatile 写操作的后面插入一个 StoreLoad 屏障.
在每个 volatile 读操作的后面插入一个 LoadLoad 屏障.
在每个 volatile 读操作的后面插入一个 LoadStore 屏障.
上面的内存屏障方式主要是规定了在处理器级别的一些重排序要求. 而 JMM 本身, 对于 volatile 变量在编译器级别的重排序也制定了相关的规则. 可以用下面的图来表示
volatile 变量除了在编译器重排序方面的语义以外, 还存在一条约束保证. 如果 cpu 硬件上存在类似 invalidate queue 的东西, 可以在进行变量读取操作之前, 会先处理完毕 queue 上的内容. 这样就能保证 volatile 变量始终是读取最新的最后写入的值.
Happen-before
JMM 为了简化对编程复杂的理解, 使用了 HB 来表达不同操作之间的可见性. HB 关系在不同的书籍中有不同的表达. 这里推荐一种比较好理解的.
A Happen before B, 说明 A 操作的效果先于 B 操作的效果发生. 这种偏序关系在单线程中是没有什么作用的, 因为单线程中, 执行效果要求和代码顺序一致. 但是在多线程中, 其可见性作用就非常明显了. 举个例子, 在线程 1 中进行进行 a,b 操作, 操作存在 hb 关系. 那么当线程 2 观察到 b 操作的效果时, 必然也能观察到 a 操作的效果, 因为 a 操作 Happen before b 操作.
在 java 中, 存在 HB 关系的操作一共有 8 种, 如下.
程序次序法则, 如果 A 一定在 B 之前发生, 则 happen before
监视器法则, 对一个监视器的解锁一定发生在后续对同一监视器加锁之前
Volatie 变量法则: 写 volatile 变量一定发生在后续对它的读之前
线程启动法则: Thread.start 一定发生在线程中的动作前
线程终结法则: 线程中的任何动作一定发生在线程终结之前 (其他线程检测到这个线程已经终止, 从 Thread.join 调用成功返回, Thread.isAlive() 返回 false)
中断法则: 一个线程调用另一个线程的 interrupt 一定发生在另一线程发现中断之前.
终结法则: 一个对象的构造函数结束一定发生在对象的 finalizer 之前
传递性: A 发生在 B 之前, B 发生在 C 之前, A 一定发生在 C 之前.
使用 HB 关系, 在多线程开发时就可以尽量少的避免使用锁, 而是直接利用 hb 关系和 volatile 关键字来达到信息传递并且可见的目的.
比如很常见的一个线程处理一些数据并且修改标识位后, 另外的线程检测到标识位发生改变, 就接手后续的流程. 此时如何保证前一个线程对数据做出的更改后一个线程全部可见呢. 先来看下面的代码例子
- class VolatileExample {
- int a = 0;
- volatile boolean flag = false;
- public void writer() {
- a = 1; //1
- flag = true; //2
- }
- public void reader() {
- while(flag==false); //3
- int i=a; //4
- }
- }
有两个不同的线程分别执行 writer 和 reader 方法, 根据 Hb 规则, 有如下的顺序执行图.
这样的顺序, i 读取到的 a 的值就是最新的, 也即是 1.
来源: http://www.bubuko.com/infodetail-2770069.html