心安

缓存一致性原理

字数统计: 3.1k阅读时长: 11 min
2019/02/23 Share

前言

在计算机中,计算机的指令都是由 cpu(Central Processing Unit,中央处理器)来执行的,而指令执行的过程中就会涉及到数据的读取与写入。程序运行过程中的临时数据都是存储在主存(物理内存)中的,随着cpu的速度变快,主存的速度就跟不上cpu的速度了,于是就有了“高速缓存”,从名字上面我们就可以知道,这个缓存速度是很快的。这样在程序的运行过程中,会将运算中需要的数据复制一份到缓存中,下次再使用的时候就可以直接从缓存中读取,从而提高程序的运行速度。后面cpu的速度越来越快,高速缓存的速度也跟不上cpu的速度的,于是就出现了二级缓存,在有些计算机中甚至更多级的缓存。

同样思想的就是在我们的应用程序中,对于需要频繁查询而很少更新的数据,由于每次直接查询数据库非常耗时,所以通常的处理就是在第一次查询数据库之后,将这些数据放入缓存中,再次查询的时候就可以在缓存中读取,而不需要再次访问数据库,这样不仅减少了数据库的压力,而且加速了数据的读取速度。

总之,CPU 缓存的出现就是为了读取数据更快,解决cpu和内存之间速度不匹配的问题。

一级缓存和多级缓存示意图

上图分别为一级缓存和多级缓存的示意图。其中bus代表消息总线( cpu 和计算机其他部件通信是通过消息总线来进行的),蓝色代表主存,绿色代表缓存,黄色代表 cpu 。

局部性原理

有一个疑问就是,缓存中包含的只有主存中的部分数据,那么缓存中不存在所需数据的情况就在所难免,那么就需要直接去主存中读取。这样一来,缓存的出现真的有意义吗?

局部性原理:

  • 时间局部性

    如果某个数据被访问,那么它很可能很快再次被访问。

比如说在递归调用、循环调用等情况。

  • 空间局部性

    如果某个数据被访问,那么它相邻的数据很可能很快被访问。

比如说循环遍历一个数组。

由局部性原理我们可以发现,访问某个数据,那么很快就可能会再次访问和访问这块数据相邻的数据,所以将访问的数据和它相邻的数据加入到缓存中,以便不久的将来继续使用,这就是缓存出现的意义。

缓存一致性问题的出现

如上面提到的一样,当计算机加入了缓存,cpu读取数据的时候首先会从缓存读取,如果缓存中不存在,则从主存读取,同时把该数据加入到缓存中,这样下次再次使用的时候就可以直接从缓存中读取。当修改了某些数据,先把修改后的数据写入到缓存中,然后再刷到主存中,以此来提高效率。

这样的过程在单线程的环境下是不会出现问题的,但是在多线程环境下就会出现问题,现在的计算机几乎都是多个核心的,多个线程运行在不同的核心中,每个核心都有自己的缓存。这时就会出现多个cpu同时修改了同一个数据的问题,这就是著名的缓存一致性问题。

早期cpu中,为了解决缓存一致性问题,计算机厂商们通过在消息总线上加锁来解决的,也就是说同时只有一个cpu能操作同一块数据。这样的后果就是,加锁期间其他cpu无法访问内存,导致效率低下,因此出现了第二种解决方案,就是通过缓存一致性协议来解决缓存一致性问题。

缓存一致性协议(MESI)

MESI是取自缓存行(Cache line,缓存中存储数据的单元)中数据的四种状态的英文首字母,缓存行中数据具有四种状态,它们分别是:

  • Modified(修改):数据有效,数据被修改了,和内存中数据不一致,数据只存在于本Cache中。
  • Exclusive(独享):数据有效,数据和内存中的数据一致,数据只存在于本Cache中。
  • Shared(共享):数据有效,数据和内存中的数据一致,数据存在多个Cache中。
  • Invalid(无效):数据无效,一旦数据被标记为无效,那效果就等同于它从来没被加载到缓存中。

这四种状态之间的转化晦涩难懂,所以笔者参考了CSDN博主陌小北zzZ的文章《缓存一致性协议》,觉得这个博主举得例子非常的生动,所以这里借用一下。

举个栗子

我们以github为例来讲解缓存一致性协议。我们的项目存储在github,那么项目就等于计算机中的“数据”,github等于“主存”。假设项目组有A、B、C、D四个人,也就是四个“cpu”,每个人都有一台计算机,也就是每个人都有自己的“缓存”。然后我们需要把项目从“主存”github上面拉取到本地计算机,也就是“缓存”中。

  1. 初始状态下,每个人的计算机中都没有项目,也就是缓存都为空。
  2. A同学把项目拉取到了本地,此时A的缓存中有了项目,且与远程仓库保持一致,也就是说只有A的缓存中的存在数据,并且与主存数据保持一致,此时A独享数据,就是Exclusive。
  3. B、C、D同学也把项目拉取到了本地,此时多个缓存中存在同一份数据,并且和主存数据一致,此时大家共享数据,就是Shared。
  4. A同学进行了代码修改,此时,A同学就告诉其他同学,代码被我改过了,你们的数据都是失效的数据,也就是Invalid。而A同学的数据就是Modified。
  5. A同学修改代码之后提交了代码,此时只有A同学的数据和主存数据一致,所以数据从Modified变为了独享Exclusive。
  6. 其他同学需要看A同学修改的代码,所以拉取了最新的代码,此时所有人数据和主存数据一致,都成了共享Shared。

也就是说,当数据被修改,那么其他cpu缓存中的数据都会失效(这里面其实有一个监听的机制,读写操作都会通知到其他 cpu )变成Invalid,被修改的那一份变为Modified。当其他 cpu 需要读取这份数据,由于这份数据是Modified状态,所以需要先将该数据写入到主存,写入之后就成了独享状态,这时其他cpu就可以读取这份数据,成为共享。

只有当缓存段处于 E 或 M 状态时,处理器才能去写它(往缓存中写入),也就是说只有这两种状态下,处理器是独占这个缓存段的。当处理器想写某个缓存段时,如果它没有独占权,它必须先发送一条“我要独占权”的请求给总线,这会通知其他处理器(使用的是一种类似广播的形式来进行通讯),把它们拥有的同一缓存段的拷贝失效(如果它们有的话)。只有在获得独占权后,处理器才能开始修改数据——并且此时,这个处理器知道,这个缓存段只有一份拷贝,在我自己的缓存里,所以不会有任何冲突。

反之,如果有其他处理器想读取这个缓存段,独占或已修改的缓存段必须先回到“共享”状态。如果是已修改的缓存段,那么还要先把内容回写到内存中。

状态迁移图

对于数据的读写也有四种操作,分别是local read(从缓存中读取)、local write(写入到缓存)、remote read(读取其他 cpu 的缓存)、remote write(写入到其他 cpu 的缓存中)。当内核需要访问的数据不在本Cache中,而其它Cache有这份数据的备份时,本Cache既可以从内存中导入数据,也可以从其它Cache中导入数据,不同的处理器会有不同的选择。MESI协议为了使自己更加通用,没有定义这些细节,只定义了状态之间的迁移。

下面是MESI协议状态迁移图:

MESI协议中数据的状态有4种,引起状态变化的操作也有四种,所以理解MESI协议就需要对这16种状态转换的情况理解清楚。

多核系统中,每个cpu都有自己的缓存,他们共享同一个主内存。缓存的目的就是减少读取共享主存的次数,数据除了在I状态下,都是可以满足读请求的。如上图:

  1. 我们先看local read,也就是绿色的线,在M、E、S状态下,三条绿色的线经过本地读取之后又指向了自身。也就是说共享、独享、修改状态下,cpu直接读取缓存中的数据,而不会导致数据状态的变化。当在I状态下时,等同于缓存中没有这块数据的缓存,那么cpu就会把主存的数据复制到缓存,使其变为独享或者共享。

  2. 然后是local write,红色的线。当数据在任意状态下时,cpu往缓存中写入数据的时候都会是数据变为M状态。

  3. 再看一下remote read,就是本缓存中没有,从其他cpu的缓存中读取,对应蓝色的线。S状态下,读取之后状态不变,M、E状态下,都会变为共享。

  4. 最后看remote write,将数据写入到其他cpu的缓存,黄色的线。除了I状态,其他状态下都可以执行remote write操作,并且写入后,数据全部失效。

下面的表格详细的表示了数据状态迁移的过程:














































































当前状态



事件



行为



M(Modified)



Local Read



从Cache中取数据,状态不变



Local Write



修改Cache中的数据,状态不变



Remote Read



这行数据被写到内存中,使其它核能使用到最新的数据,状态变成S



Remote Write



这行数据被写到内存中,使其它核能使用到最新的数据,由于其它核会修改这行数据,状态变成I



E(Exclusive)



Local Read



从Cache中取数据,状态不变



Local Write



修改Cache中的数据,状态变成M



Remote Read



数据和其它核共用,状态变成了S



Remote Write



数据被修改,本Cache line不能再使用,状态变成I



S(Shared)



Local Read



从Cache中取数据,状态不变



Local Write



修改Cache中的数据,状态变成M,其它核共享的Cache line状态变成I



Remote Read



状态不变



Remote Write



数据被修改,本Cache line不能再使用,状态变成I



I(Invalid)



Local Read



如果其它Cache没有这份数据,本Cache从内存中取数据,Cache line状态变成E;


如果其它Cache有这份数据,且状态为M,则将数据更新到内存,本Cache再从内存中取数据,2个Cache 的Cache line状态都变成S;


如果其它Cache有这份数据,且状态为S或者E,本Cache从内存中取数据,这些Cache 的Cache line状态都变成S



Local Write



从内存中取数据,在Cache中修改,状态变成M;


如果其它Cache有这份数据,且状态为M,则要先将数据更新到内存;


如果其它Cache有这份数据,则其它Cache的Cache line状态变成I



Remote Read



既然是Invalid,别的核的操作与它无关



Remote Write



既然是Invalid,别的核的操作与它无关


参考

缓存一致性协议

缓存一致性(Cache Coherency)入门

Cache coherency primer

原文作者:XinAnzzZ

原文链接:https://www.yuhangma.com/2019/concurrent/2019-02-23-cpu-cache/

发表日期:February 23rd 2019, 12:00:00 am

更新日期:February 2nd 2021, 4:44:20 pm

版权声明:(转载本站文章请注明作者和出处 心 安 – XinAnzzZ ,请勿用于任何商业用途)

CATALOG
  1. 1. 前言
  2. 2. 局部性原理
  3. 3. 缓存一致性问题的出现
  4. 4. 缓存一致性协议(MESI)
    1. 4.1. 举个栗子
    2. 4.2. 状态迁移图
  5. 5. 参考