JDK并发集合1：CPU缓存（基础篇）

一张狗 java

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