欢迎大家来到IT世界,在知识的湖畔探索吧!
MESI协议
MESI协议是一个被广泛使用的CPU缓存一致性协议。我们都知道在CPU中存在着多级缓存,缓存级别越低,容量就越小,速度也越快。有了缓存,CPU就不需要每次都向主存读写数据,这提高了CPU的运行速度。然而,在多核CPU中,低级别的缓存是单个CPU独占的:
如上图所示,每个CPU核心分别拥有独立的一、二级缓存,共享了三级缓存。这就带来了缓存一致性的问题:当同一份数据同时存在于多个CPU的独立缓存中时,如何保证缓存数据的一致性?
MESI协议提供了一种方式,成功的解决了缓存一致性问题。对于缓存中的每一行,都设置一个状态位,一共有四种状态:
- M(modified):表示缓存行仅存在于当前的缓存中,并且已经被更改。在该缓存行写回到主存之前,任何其他CPU都不能读取该缓存行的内容。
- E(exclusive):表示缓存行仅存在于当前的缓存中,并且未被修改。如果有其他CPU读取该行,则转移到Shared状态;如果修改该行,则转移到Modified状态。
- S(shared):表示有多个CPU共享该缓存行,且内容未被修改。
- I(invalid):表示缓存行已失效(未被使用)。
从上述状态定义可以看出,MESI协议实际上定义了一个状态机,其中状态转移规则保证了CPU在多级缓存环境下的缓存一致性。MESI定义的状态转移规则如下所述:
除Invalid状态以外,所有状态的缓存行都可以进行读操作
从状态定义就可以看出,只有Invalid状态的缓存行内容是无效的,必须从主存读取。
只有在状态为M或E时才能进行写操作,如果当前状态为S,则其它CPU中的同一行必须转移到状态I,这是通过发送RFO(request for ownership)广播实现的
M或E状态下,缓存行都只存在于单个CPU中,S状态下多个CPU共享一行,因此必须将其他CPU的状态置为I,才能进行写操作。
除M以外的任意状态都可转移到I,M状态必须先写回到主存再丢弃
只要内容未被修改,CPU可以再任意时刻丢弃一个缓存行,否则则必须先把修改的内容写回到主存
处于M状态的缓存必须拦截其他CPU对同一行的读操作,并返回自身缓存中的数据
这可以保证所有CPU读到的都是最新的内容,这种拦截操作称为snoop,数据不需要写回到主存,直接由M状态的缓存返回,状态由M转移到S
处于S状态的缓存必须监听RFO广播,并转移到I状态
当一个CPU修改S状态的缓存时,其余的缓存必须先转移到I状态,防止并发的写操作
处于E状态的缓存必须拦截其他CPU的读操作,并转移到S状态
当有其他CPU读E状态的缓存时,状态必须由独占转移到共享
上述过程可以用下面这幅图来描述:
那么问题来了
MESI很好的解决了缓存一致性的问题,但是也不可避免的带来了额外的开销。考虑一个简单的赋值操作a=1,假设变量所在的缓存行不在当前CPU中,则CPU需要发送”read invalidate”消息,获取缓存行,并且告知其他CPU丢弃该缓存行,然后该CPU必须等待,直到收到来自其他CPU的确认响应为止:
而实际上,无论a之前的值为何,在该条指令执行后都会被覆盖,因此这段等待的开销是完全没有必要的。为此,CPU的设计者加入了store buffer,用于缓存store指令对缓存行的修改:
如图所示,对缓存行的修改操作不会立刻执行到缓存行上,而是先进入store buffer,这样CPU的写操作就不需要等待到从其他CPU得到缓存行才能执行。CPU可以立即执行写操作,等到得到缓存行时,才将变更从store buffer写入缓存行。然而,这又立刻带来了另外一个问题,由于store buffer的存在,在CPU中同一个变量可能存在两份拷贝(当缓存行到达CPU时,缓存和store buffer中存在同一个变量的两份拷贝),这无疑破坏了缓存的一致性,若CPU在store buffer写入缓存之前load数据,就会拿到旧的数据。为了解决这个问题,CPU设计者又加入了store forwarding机制,简单的讲就是CPU会优先从store buffer中取变量,保证同一时刻一个变量在单个CPU中的一致性:
然而,这样做并不能解决另外一个问题,那就是隐式的数据依赖,考虑下面两个
代码清单1: foo(){ a = 1; b = 1; } bar(){ while(b == 0) continue; assert(a == 1); } 复制代码
欢迎大家来到IT世界,在知识的湖畔探索吧!
假设CPU0执行foo,CPU1执行bar,并且a处于CPU1的缓存中。由于store buffer的存在,对a的写操作会立刻执行,而不会等待其他CPU的invalidate响应。CPU0接着执行b=1,CPU1获取到最新的b以后,执行assert语句,此时,CPU1有可能尚未收到来自CPU0的invalidate消息,因而a有可能仍在CPU1的缓存中,并且值未被改变,从而导致assert失败。
内存屏障
引入store buffer带来了性能的提升,却导致MESI协议无法保障缓存的一致性。从上一节中的例子可以看出,一致性问题的出现来源于数据之间的隐式依赖,也就是说必须保证某个操作在另外一个操作之前完成。比如a=1这个操作必须写入到cache line(只有在cpu收到invalidate响应时,才会把数据从store buffer写入cache line),才能执行b=1。但是CPU是无法探测到这种隐式相关性的,必须由程序员自己来进行控制。因此CPU提供了内存屏障指令,该指令使得屏障之前的写操作都在屏障之后的写操作之前完成:
欢迎大家来到IT世界,在知识的湖畔探索吧!代码清单2: foo(){ a = 1; smp_mb(); // 加入内存屏障 b = 1; } bar(){ while(b == 0) continue; assert(a == 1); } 复制代码
smp_mb的实际功能是对store buffer中的变量标记,这样当CPU0执行b=1时,发现store buffer中存在标记过的变量,就不能立刻将b=1写入缓存行,而是将其写入store buffer(但不进行标记)。等到CPU0收到invalidate响应,将store buffer中的标记变量写入缓存行,b=1才会写入到缓存行。在此期间,由于标记变量的存在,所有对b的读操作都只能读到b的原始值,也就是0,导致CPU1无法执行到assert语句。
除了写操作等待,invalidate操作的开销也很大,因为它的存在,CPU不得不频繁丢弃缓存行,导致缓存命中率低下。为了进一步提升性能,CPU中又加入了invalidate队列(invalidate queue),CPU收到invalidate消息以后会立刻发送响应,但并不立刻处理,而是将该消息放入队列,等到适当的时候再处理。与store buffer类似,这么做的副作用也是破坏了MESI协议,延迟响应的代价就是缓存中可能存在过期的数据。这个问题同样可以用内存屏障来解决:
代码清单3: foo(){ a = 1; smp_mb(); // 加入内存屏障 b = 1; } bar(){ while(b == 0) continue; smp_mb(); // 加入内存屏障 assert(a == 1); } 复制代码
bar()函数的内存屏障保证了屏障之前的invalidate消息都会执行,然后才执行后面的指令。这样CPU1执行assert时,发现a的缓存行已经失效,只能尝试读取,此时CPU0会返回最新的数据a=1,assert执行成功。为了进一步提升效率,CPU还支持对store buffer和invalidate队列单独进行操作,这就是写屏障和读屏障。写屏障保证屏障之前的写操作对其他CPU都是可见的;读屏障保证屏障之后的读操作读到的都是最新的数据。
Java中的内存屏障
Java中的 volatile 关键字可以用来修饰变量,它可以保证:
可见性 一个线程对volatile变量的写操作可以立刻被其他线程看到
原子性 对volatile变量的单个读/写操作具有原子性
在某些jvm中,对 long 和 double 的读写操作是不具有原子性的,而是会拆成两部分:对高32位和低32位分别赋值。因此,假设线程a在读 long 变量l时,线程b也在写入,那么线程a可能读到的数据可能一半是新的,一半是旧的。如果将 long 和 double 变量声明为volatile,则可能保证变量的读写具有原子性。但是要注意,这个原子性只是对读写的单个操作而言的,对于复合操作则不能保证:
欢迎大家来到IT世界,在知识的湖畔探索吧!代码清单4: volatile int a = 0; incrementAndGet(){ a++; return a; } 复制代码
如果指望代码清单4中的a变量能够正确的增长,恐怕要失望了。因为a++这个操作实际上是由读取-修改-写入三个操作组成的,在并发环境中,这样的操作不具有原子性,数据更新很有可能会丢失。
可见性 又是怎么一回事呢?这就涉及到了内存屏障,为了使得对volatile变量的修改对其他线程总是可见的,jvm会执行如下操作:
在volatile变量的写操作之后插入写屏障
插入写屏障之后,屏障之前的写操作对于其他CPU都是可见的,需要注意的是此处的可见性并不只针对标记为volatile的变量,而在所有在屏障之前执行了写操作的共享变量(写屏障是对store buffer中存在的所有变量进行标记)。
在对volatile变量的读操作之前插入读屏障
插入读屏障之后,本地缓存中所有被更改过的共享变量会立刻失效(通过执行invalidate队列中的消息实现)。这样,在屏障之后读取共享变量时,由于缓存失效,只能向主存或其他CPU发送读取请求,从而保证了读到的一定是最新的值。
代码清单5是一个简单的实例
代码清单5: class MBExample{ int a = 0; volatile boolean flag = false; void foo(){ a = 2; flag = true; } void bar(){ if(flag) a ++; else a --; } } 复制代码
假设线程t1和t2共享MBExample的一个实例,t1执行foo, t2执行bar。假设foo先于bar执行,此时我们一定期望a最终的值为3。但是,如果flag变量未被标记为 volatile ,根据之前的讨论,由于store buffer和invalidate queue的存在,t2未必能获得最新的a和flag的值(例如假设一开始a以S状态存在于t1,t2的cache line中,而flag以E状态存在与t1的cache line,最终的结果有可能为a=1)。如果flag被标记为volatile,代码清单5实际上变成了如代码清单6的情形:
代码清单6: ... void foo(){ a = 2; // ---------------------------1 flag = false; // --------------------2 smp_wmb(); // 写屏障 } void bar(){ smp_rmb(); // 读屏障 if(flag) // -------------------------3 a ++; // -----------------------4 else a --; } ... 复制代码
事实上,volatile的作用不止于此,对于JIT编译器而言,volatile还是”指令屏障”,如果编译器出于性能优化的考虑对指令进行重排序,有可能破坏程序的原本意图,volatile对这一行为进行了限制。Java内存模型针对volatile的指令重排序做了如下规定:
- 当第二个操作是volatile写时,不管第一个操作是什么,都不能重排序。这个规则确保volatile写之前的操作不会被编译器重排序到volatile写之后。
- 当第一个操作是volatile读时,不管第二个操作是什么,都不能重排序。这个规则确保volatile读之后的操作不会被编译器重排序到volatile读之前。
- 当第一个操作是volatile写,第二个操作是volatile读时,不能重排序。
因此,当foo在bar之前执行时,实际上产生了一种偏序关系,如代码清单6所示1 >> 2 >> 3 >> 4,最终使得4中读取到的a的值一定为2。这种指令重排的约束仅对JIT生效,因为java字节码解释器的解释执行是line by line的,指令的先后顺序天然的得到保留。
参考资料
Memory Barriers: a Hardware View for Software Hackers
MESI protocol
深入理解Java内存模型(四)——volatile
Memory Barriers/Fences
Non-atomic Treatment of double and long
我自己收集了一些Java资料,里面就包涵了一些BAT面试资料,以及一些 Java 高并发、分布式、微服务、高性能、源码分析、JVM等技术资料
资料获取方式:关注我并私信“666”即可免费获取
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/34007.html