搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 懂一点架构 > 聊聊高并发:CPU高速缓存行和伪共享

聊聊高并发:CPU高速缓存行和伪共享

懂一点架构 2017-10-29

CPU高速缓存行和伪共享


CPU 为了更快的执行代码,于是当从内存中读取数据时,并不是只读自己想要的部分。而是读取足够的字节来填入高速缓存行。根据不同的 CPU ,高速缓存行大小不同。如 X86 是 32BYTES ,而 ALPHA 是 64BYTES 。并且始终在第 32 个字节或第 64 个字节处对齐。这样,当 CPU 访问相邻的数据时,就不必每次都从内存中读取,提高了速度。 因为访问内存要比访问高速缓存用的时间多得多。


但是,多核发达的年代。情况就不能那么简单了。试想下面这样一个情况。

1、CPU1 读取了一个字节,以及它和它相邻的字节被读入 CPU1 的高速缓存。

2、CPU2 做了上面同样的工作。这样 CPU1 , CPU2 的高速缓存拥有同样的数据。

3、CPU1 修改了那个字节,被修改后,那个字节被放回 CPU1 的高速缓存行。但是该信息并没有被写入 RAM 。

4、CPU2 访问该字节,但由于 CPU1 并未将数据写入 RAM ,导致了数据不同步。


缓存系统中是以缓存行(cache line)为单位存储的。缓存行是2的整数幂个连续字节,一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。缓存行上的写竞争是运行在SMP系统中并行线程实现可伸缩性最重要的限制因素。有人将伪共享描述成无声的性能杀手,因为从代码中很难看清楚是否会出现伪共享。

说明:上图中,一个运行在处理器 core1上的线程想要更新变量 X 的值,同时另外一个运行在处理器 core2 上的线程想要更新变量 Y 的值。但是,这两个频繁改动的变量都处于同一条缓存行。两个线程就会轮番发送 RFO 消息,占得此缓存行的拥有权。当 core1 取得了拥有权开始更新 X,则 core2 对应的缓存行需要设为 I 状态(失效态)。当 core2 取得了拥有权开始更新 Y,则 core1 对应的缓存行需要设为 I 状态(失效态)。轮番夺取拥有权不但带来大量的 RFO 消息,而且如果某个线程需要读此行数据时,L1 和 L2 缓存上都是失效数据,只有 L3 缓存上是同步好的数据。从前一篇我们知道,读 L3 的数据非常影响性能。更坏的情况是跨槽读取,L3 都要 miss,只能从内存上加载。一个处理器的缓存回写到内存会导致其它处理器的缓存无效


下表表示了CPU到各缓存和内存之间的大概速度:

从CPU到 大约需要的CPU周期 大约需要的时间(单位ns)
寄存器 1 cycle
L1 Cache ~3-4 cycles ~0.5-1 ns
L2 Cache ~10-20 cycles ~3-7 ns
L3 Cache ~40-45 cycles ~15 ns
跨槽传输
~20 ns
内存 ~120-240 cycles ~60-120ns

就像数据库cache一样,获取数据时首先会在最快的cache中找数据,如果没有命中(Cache miss) 则往下一级找,直到三层Cache都找不到,那只要向内存要数据了. 一次次地未命中,代表取数据消耗的时间越长。


MESI 协议及 RFO 请求



每个核都有自己私有的 L1,、L2 缓存。那么多线程编程时, 另外一个核的线程想要访问当前核内 L1、L2 缓存行的数据, 该怎么办呢?


有人说可以通过第 2 个核直接访问第 1 个核的缓存行,这是当然是可行的,但这种方法不够快。跨核访问需要通过 Memory Controller(内存控制器,是计算机系统内部控制内存并且通过内存控制器使内存与 CPU 之间交换数据的重要组成部分),典型的情况是第 2 个核经常访问第 1 个核的这条数据,那么每次都有跨核的消耗.。更糟的情况是,有可能第 2 个核与第 1 个核不在一个插槽内,况且 Memory Controller 的总线带宽是有限的,扛不住这么多数据传输。所以,CPU 设计者们更偏向于另一种办法: 如果第 2 个核需要这份数据,由第 1 个核直接把数据内容发过去,数据只需要传一次。


那么什么时候会发生缓存行的传输呢?答案很简单:当一个核需要读取另外一个核的脏缓存行时发生。但是前者怎么判断后者的缓存行已经被弄脏(写)了呢?


下面将详细地解答以上问题. 首先我们需要谈到一个协议—— MESI 协议。现在主流的处理器都是用它来保证缓存的相干性和内存的相干性。M、E、S 和 I 代表使用 MESI 协议时缓存行所处的四个状态:

M(修改,Modified):本地处理器已经修改缓存行,即是脏行,它的内容与内存中的内容不一样,并且此 cache 只有本地一个拷贝(专有);

E(专有,Exclusive):缓存行内容和内存中的一样,而且其它处理器都没有这行数据;

S(共享,Shared):缓存行内容和内存中的一样, 有可能其它处理器也存在此缓存行的拷贝;

I(无效,Invalid):缓存行失效, 不能使用。


下面说明这四个状态是如何转换的:

初始:一开始时,缓存行没有加载任何数据,所以它处于 I 状态。

本地写(Local Write):如果本地处理器写数据至处于 I 状态的缓存行,则缓存行的状态变成 M。

本地读(Local Read):如果本地处理器读取处于 I 状态的缓存行,很明显此缓存没有数据给它。此时分两种情况:(1)其它处理器的缓存里也没有此行数据,则从内存加载数据到此缓存行后,再将它设成 E 状态,表示只有我一家有这条数据,其它处理器都没有;(2)其它处理器的缓存有此行数据,则将此缓存行的状态设为 S 状态。(备注:如果处于M状态的缓存行,再由本地处理器写入/读出,状态是不会改变的)

远程读(Remote Read):假设我们有两个处理器 c1 和 c2,如果 c2 需要读另外一个处理器 c1 的缓存行内容,c1 需要把它缓存行的内容通过内存控制器 (Memory Controller) 发送给 c2,c2 接到后将相应的缓存行状态设为 S。在设置之前,内存也得从总线上得到这份数据并保存。

远程写(Remote Write):其实确切地说不是远程写,而是 c2 得到 c1 的数据后,不是为了读,而是为了写。也算是本地写,只是 c1 也拥有这份数据的拷贝,这该怎么办呢?c2 将发出一个 RFO (Request For Owner) 请求,它需要拥有这行数据的权限,其它处理器的相应缓存行设为 I,除了它自已,谁不能动这行数据。这保证了数据的安全,同时处理 RFO 请求以及设置I的过程将给写操作带来很大的性能消耗。


状态转换由下图做个补充:

聊聊高并发:CPU高速缓存行和伪共享


再来看一下并发更新流程:

聊聊高并发:CPU高速缓存行和伪共享


问题:多CPU时的L3 cache对缓存行是否唯一,还是一个缓存行的多个拷贝?

本人解读:这应该是CPU3级缓存的缘由,就像同个槽内L1和L2多个缓存行拷贝一样,不同L3缓存也应该是多个拷贝。(此处仅代表个人理解)


伪共享的解决之道


为了高效地存取缓存,不是简单随意地将单条数据写入缓存的,缓存是由缓存行组成的,典型的一行是64字节。可以通过下面的shell命令,查看cherency_line_size就知道知道机器的缓存行是多大。

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size   

64

CPU存取缓存都是按行为最小单位操作的。将问题简化一些,一个Java long型占8字节,所以从一条缓存行上你可以获取到8个long型变量。所以如果你访问一个long型数组,当有一个long被加载到cache中,你将无消耗地加载了另外7个,所以你可以非常快地遍历数组。


public final static class VolatileLong {

       public volatile long value = 0L;

       public long p1, p2, p3, p4, p5, p6; 

}

VolatileLong通过填充一些无用的字段p1,p2,p3,p4,p5,p6,再考虑到对象头也占用8bit, 刚好把对象占用的内存扩展到刚好占64bytes(或者64bytes的整数倍)。这样就避免了一个缓存行中加载多个对象。


note:在java中空对象占八个字节(默认对象头的占用大小),对象的引用占四个字节。所以上面那条语句所占的空间是4byte+8byte=12byte.java中的内存是以8的倍数来分配的,所以分配的内存是16byte。


实际case1:

JDK1.8 ConcurrentHashMap的处理

java.util.concurrent.ConcurrentHashMap在这个如雷贯耳的Map中,有一个很基本的操作问题,在并发条件下进行++操作。因为++这个操作并不是原子的,而且在连续的Atomic中,很容易产生伪共享(false sharing)。所以在其内部有专门的数据结构来保存long型的数据:

@sun.misc.Contended 

static final class CounterCell { 

    volatile long value; 

    CounterCell(long x) { 

        value = x; 

    }

}

我们看到该类中,是通过@sun.misc.Contended达到防止false sharing的目的。


note:那么是不是在使用Volatile变量时都应该追加到64字节呢?不是的。在两种场景下不应该使用这样的方式。第一:缓存行非64字节宽的处理器。如P6系列和奔腾处理器,它们的L1和L2快速缓存行是32个字节宽。第二:共享变量不会被频繁的写。由于使用追加字节的方式须要处理器读取很多其它的字节到快速缓冲区。这本身就会带来一定的性能消耗,共享变量假设不被频繁写的话。锁的几率也很小,就不是必需通过追加字节的方式来避免相互锁定。


实际case2:

实现字节填充的框架有 Disruptor,在RingBuffer中实现填充。具体实现不在本文解决了,后续再展开介绍。 



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《聊聊高并发:CPU高速缓存行和伪共享》的版权归原作者「懂一点架构」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注懂一点架构微信公众号

懂一点架构微信公众号:gh_fba925235d45

懂一点架构

手机扫描上方二维码即可关注懂一点架构微信公众号

懂一点架构最新文章

精品公众号随机推荐