JDK并发集合1:CPU缓存(基础篇)

CPU缓存

因为CPU运算速度和内存的读取速度相差了很多个数量级,所以在CPU这里通常会有几级缓存,如下图:

--1

对于现代处理起来说,一个CPU通常有两个逻辑线程,如上图的Core0和Core1。每个Core有自己的L1 Cache,其中又分为存储指令的L1i和存储数据的L1d。同一个物理CPU的逻辑核心共享同一个L2 Cache,所有的物理CPU共享L3 Cache,这三层Cache的速度对比如下:

  • L1:紧靠CPU内核
  • L2:比L1大一些,慢一些
  • L3:单插槽内CPU核共享

实测数据:
--3

伪共享问题

原理

因为CPU Cache加载的时候是加载整个Cache Line的,所以这里会出现伪共享的问题。如下图所示
--2
现在主流的CacheLine是64Bytes,我们看到图中两个CPU运行着两个线程,这两个线程读取了两个不同的数据,这两个数据在物理内存上连续,并且位于同一个CacheLine中。当某个线程修改了数据之后,会使得另一个线程的CacheLine失效,另一个线程在读写的时候就会发生cache miss,需要重新去内存中读取数据,这样就大大降低了性能。

例子

这里举一个例子:

public class FalseShareTest implements Runnable {
    public static int NUM_THREADS = 4;
    public final static long ITERATIONS = 500L * 100L * 100L;
    private final int arrayIndex;
    private static VolatileLong[] longs;
    public static long SUM_TIME = 0l;
    public FalseShareTest(final int arrayIndex) {
        this.arrayIndex = arrayIndex;
    }
    public static void main(final String[] args) throws Exception {
        Thread.sleep(1000);
        for(int j=0; j<10; j++){
            System.out.println(j);
            if (args.length == 1) {
                NUM_THREADS = Integer.parseInt(args[0]);
            }
            longs = new VolatileLong[NUM_THREADS];
            for (int i = 0; i < longs.length; i++) {
                longs[i] = new VolatileLong();
            }
            final long start = System.currentTimeMillis();
            runTest();
            final long end = System.currentTimeMillis();
            SUM_TIME += end - start;
        }
        System.out.println("平均耗时:"+SUM_TIME/10 + "ms");
    }
    private static void runTest() throws InterruptedException {
        Thread[] threads = new Thread[NUM_THREADS];
        for (int i = 0; i < threads.length; i++) {
            threads[i] = new Thread(new FalseShareTest(i));
        }
        for (Thread t : threads) {
            t.start();
        }
        for (Thread t : threads) {
            t.join();
        }
    }
    public void run() {
        long i = ITERATIONS + 1;
        while (0 != --i) {
            longs[arrayIndex].value = i;
        }
    }
    public final static class VolatileLong {
        public volatile long value = 0L;
        public long p1, p2, p3, p4, p5, p6;     //屏蔽此行
    }
}

在上面的例子中,分别屏蔽和打开“屏蔽此行”,在我的笔记上的测试结果:足足差了三倍

例子 耗时
打开 105ms
屏蔽 344ms

缓存一致性协议

因为CPU之间存在缓存一致性问题,多个CPU在访问缓存的时候需要遵守一些协议,在读写操作时根据协议来操作,它们规定了何时应该访问缓存,何时应该让缓存失效,何时应该访问内存等,保证了每个缓存中使用的共享变量的副本是一致的。

MESI

MESI协议是当前最主流的缓存一致性协议。在MESI中,每个缓存行有四个状态,以及每种状态的监听任务:

状态 描述 监听任务
M(Modified) 本地CPU已修改缓存行 监听所有读该行的操作,操作需要在将该行写回主存并将状态变成S状态之前被延迟执行。
E(Exclusive) 缓存行内容和内存中一致,且其他CPU没有这行缓存 监听所有读该行的操作,一旦有这种操作,则变成S状态
S(Shared) 缓存行内容和内存中一致,有可能其他CPU也缓存了这行 监听所有使该缓存行无效或者独享该缓存行的请求,并将该缓存行变成I
I(Invalid) 缓存行失效,不能使用

只有M和E状态,CPU才是独占这个缓存行的。如果一个CPU想要修改某个缓存行,但是它没有独占,则需要发送一个“我要独占”的请求给总线,这会通知其他CPU把它们拥有的该缓存行置为失效状态。只有在获得独占权之后,CPU才能修改数据。反之,如果是其他CPU想要读取某个缓存行(CPU一直在嗅探总线),则当前CPU需要修改状态为“共享”,如果是已经修改了的则需要写回到内存。

状态转换

MESI的状态转换如下图所示:
几种动作分别是:

  • 本地读取(Local read):本地cache读取本地cache数据
  • 本地写入(Local write):本地cache写入本地cache数据
  • 远端读取(Remote read):其他cache读取本地cache数据
  • 远端写入(Remote write):其他cache写入本地cache数据

--2020-10-11---12.29.50

来举个例子:多核协同操作

1. 初始状态

假设有三个CPU A、B、C,对应三个缓存分别是cache a、b、 c。在主内存中定义了x的引用值为0。
1195582-20180503162549299-994420333

2. 单核读取

CPU A 先发出一条指令去读取数据,从主内存通过bus读取到缓存中(remote read),该x现在是E状态
1195582-20180503162602668-681441242

3. 双核读取

CPU B这时候也发出一条指令去读取数据,从主内存中读取的时候,CPU A探测到了地址冲突,之后CPU A和CPU B对这个x的状态都是S。
1195582-20180503162619534-683579600

4. 修改数据

CPU A 需要修改数据,则将缓存行置为M,并通知了CPU B,CPU B将本地cache中的x设置为I。之后CPU A对x进行赋值。

1195582-20180503162633779-1465275811

5. 同步数据

之后CPU B需要读取x,CPU B通知CPU A,CPU A将修改后的数据同步到主内存,cache a 修改为E。
之后CPU B同步x,cache a和cache b中的x设置为S状态(共享)。
1195582-20180503162644640-382839091

引入的问题

缓存中的一致性消息传递需要时间,意味着状态同步会产生延迟。当一个缓存切换状态时,其他缓存收到信息并切换状态回应信息的这段时间,CPU都需要阻塞等待,而这时间远远比CPU执行一个指令的时间长,这会造成性能和稳定性的问题。比如CPU需要修改缓存里面的一个值,则它需要将状态通知到其他拥有该缓存数据的CPU缓存中,并且等待确认。等待确认的过程会阻塞处理器。

Store Buffer

为了避免浪费CPU运算能力,引入了Store Buffer,它具体做了以下两件事情:

  • 写入缓存后去处理其他事情
  • 所有失效确认都收到时才提交

这么做有同时也带来两个风险:

  • CPU会从Store Buffer中读取未提交的值,即如果加载的时候缓存值一直存在,则立即返回;
  • 无法确定什么时候保存。

这会导致问题一个问题:其他CPU读取的值跟程序中写入顺序不一样。我们来看下面一段代码:

int value;
boolean isFinish;

void exeToCPUA(){
    value = 10;
    isFinish = true;
}

void exeToCPUB(){
    if(isFinish){
        //value不一定等于10
        assert value == 10;
    }
}

假设CPU A中isFinish为E,value为I(没有保存在缓存中),value比isFinish更迟的抛弃存储缓存,则CPU B读到isFinish为true的时候,value不一定被修改为10。即isFinsh的赋值在value赋值之前。

即其他CPU可能会读到跟程序写入顺序不一样的结果。

失效队列

Store buffer不是无穷大,所以CPU有时候需要等待失效确认的返回。执行失效不是一个简单的动作,这两个加起来会使得性能大幅度降低。为了优化这一部分性能,引入了失效队列:

  • 所有收到的I请求都立即发送Invalidate回执
  • I不真正执行,而是放到失效队列
  • 为了不频繁阻塞CPU,CPU不会马上读取主存并设置缓存为I,它会等到合适的时候再一块处理失效队列。

内存屏障指令

追求性能会造成重排序,追求可见性会降低性能,CPU因此提供了两个接口供用户用户自己刷新——屏障指令(Memory Barrier):

  • 写屏障:应用所有已经在Store Buffer中的保存指令
  • 读屏障:应用所有已经在失效队列中的失效操作的指令

有了这两个屏障后,上面不一致的代码就可以改下为下面这样:

void executedOnCpu0() {
    value = 10;
    //在更新数据之前必须将所有存储缓存(store buffer)中的指令执行完毕。
    storeMemoryBarrier();
    isFinish = true;
}
void executedOnCpu1() {
    while(!isFinish);
    //在读取之前将所有失效队列中关于该数据的指令执行完毕。
    loadMemoryBarrier();
    assert value == 10;
}

refer

状态转换具体参考 https://www.cnblogs.com/yanlong300/p/8986041.html

comments powered by Disqus