CPU缓存
因为CPU运算速度和内存的读取速度相差了很多个数量级,所以在CPU这里通常会有几级缓存,如下图:
对于现代处理起来说,一个CPU通常有两个逻辑线程,如上图的Core0和Core1。每个Core有自己的L1 Cache,其中又分为存储指令的L1i和存储数据的L1d。同一个物理CPU的逻辑核心共享同一个L2 Cache,所有的物理CPU共享L3 Cache,这三层Cache的速度对比如下:
- L1:紧靠CPU内核
- L2:比L1大一些,慢一些
- L3:单插槽内CPU核共享
实测数据:
伪共享问题
原理
因为CPU Cache加载的时候是加载整个Cache Line的,所以这里会出现伪共享的问题。如下图所示
现在主流的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数据
来举个例子:多核协同操作
1. 初始状态
假设有三个CPU A、B、C,对应三个缓存分别是cache a、b、 c。在主内存中定义了x的引用值为0。
2. 单核读取
CPU A 先发出一条指令去读取数据,从主内存通过bus读取到缓存中(remote read),该x现在是E状态
3. 双核读取
CPU B这时候也发出一条指令去读取数据,从主内存中读取的时候,CPU A探测到了地址冲突,之后CPU A和CPU B对这个x的状态都是S。
4. 修改数据
CPU A 需要修改数据,则将缓存行置为M,并通知了CPU B,CPU B将本地cache中的x设置为I。之后CPU A对x进行赋值。
5. 同步数据
之后CPU B需要读取x,CPU B通知CPU A,CPU A将修改后的数据同步到主内存,cache a 修改为E。
之后CPU B同步x,cache a和cache b中的x设置为S状态(共享)。
引入的问题
缓存中的一致性消息传递需要时间,意味着状态同步会产生延迟。当一个缓存切换状态时,其他缓存收到信息并切换状态回应信息的这段时间,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;
}