CPU储存器+MESI+CPU伪共享+CPU乱序问题及代码论证

1、存储器的层次结构

2、cache line 缓存行

由于共享变量在CPU缓存中的存储是以缓存行为基本单位，一个缓存行可以存储多个变量（存满当前缓存行的字节数）；而CPU对缓存的修改又是以缓存行为最小单位的，那么就会出现上诉的伪共享问题。

Cache Line可以简单的理解为CPU Cache中的最小缓存单位，今天的CPU不再是按字节访问内存，而是以64字节为单位的块(chunk)拿取，称为一个缓存行(cache line)。当你读一个特定的内存地址，整个缓存行将从主存换入缓存，并且访问同一个缓存行内的其它值的开销是很小的。

3、为什么会出现伪共享的问题呢？

如下图：在T1,T2等多线程的情况下，假如想，X，Y两个共享变量在同一个缓存行中，CPU1修改变量X，会导致CPU2中的X和Y变量同事失效。此时对于在CPU1上运行的线程，仅仅只是修改了变量X，却导致同一个缓存行中的所有变量都无效，需要重新刷新缓存（并不一定代表每次都要从内存中重新载入，也有可能是从其他Cache中导入数据，具体的实现要看各个芯片厂商的实现了）。假设此时在CPU2上运行的线程，正好想要修改变量Y，那么就会出现相互竞争，相互失效的情况，这就是伪共享。

 4、怎么解决伪共享？

• 使用缓存行的对齐能够提高效率
• 现在cpu的数据一致性实现是通过缓存所（MESI）+总线锁（数据量非常大无法被缓存的数据或者跨越多个缓存行的数据就得使用缓存锁）结合设计的。

代码验证：

T01_CacheLinePadding 演示在同一缓存行里需要的时间。响应时间：280左右

public class T01_CacheLinePadding {
    private static class T {
        public volatile long x = 0L;
    }

    public static T[] arr = new T[2];

    static {
        arr[0] = new T();
        arr[1] = new T();
    }

    public static void main(String[] args) throws Exception {
        Thread t1 = new Thread(()->{
            for (long i = 0; i < 1000_0000L; i++) {
                arr[0].x = i;
            }
        });

        Thread t2 = new Thread(()->{
            for (long i = 0; i < 1000_0000L; i++) {
                arr[1].x = i;
            }
        });

        final long start = System.nanoTime();
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println((System.nanoTime() - start)/100_0000);
    }
}

我们把两个对象分开在不同的缓存行。默认初始化为56个字节大小的数据。响应时间：120左右

public class T02_CacheLinePadding {
    private static class Padding {
        public volatile long p1, p2, p3, p4, p5, p6, p7;
    }

    private static class T extends Padding {
        public volatile long x = 0L;
    }

    public static T[] arr = new T[2];

    static {
        arr[0] = new T();
        arr[1] = new T();
    }

    public static void main(String[] args) throws Exception {
        Thread t1 = new Thread(()->{
            for (long i = 0; i < 1000_0000L; i++) {
                arr[0].x = i;
            }
        });

        Thread t2 = new Thread(()->{
            for (long i = 0; i < 1000_0000L; i++) {
                arr[1].x = i;
            }
        });

        final long start = System.nanoTime();
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println((System.nanoTime() - start)/100_0000);
    }
}

测试结果很明显T02_CacheLinePadding 的运行时间比T01_CacheLinePadding少很多，虽然多占了内存但是它的效率提升了。

5、硬件层数据一致性 MESI(缓存锁)

MESI（Modified Exclusive Shared Or Invalid）(也称为伊利诺斯协议，是因为该协议由伊利诺斯州立大学提出）是一种广泛使用的支持写回策略的缓存一致性协议。

1、MESI协议中的状态

CPU中每个缓存行（caceh line)使用4种状态进行标记（使用额外的两位(bit)表示):

Modified: 被修改

该缓存行只被缓存在该CPU的缓存中，并且是被修改过的（dirty),即与主存中的数据不一致，该缓存行中的内存需要在未来的某个时间点（允许其它CPU读取请主存中相应内存之前）写回（write back）主存。

当被写回主存之后，该缓存行的状态会变成独享（exclusive)状态。

Exclusive: 独享的

该缓存行只被缓存在该CPU的缓存中，它是未被修改过的（clean)，与主存中数据一致。该状态可以在任何时刻当有其它CPU读取该内存时变成共享状态（shared)。

同样地，当CPU修改该缓存行中内容时，该状态可以变成Modified状态。

Shared: 共享的

该状态意味着该缓存行可能被多个CPU缓存，并且各个缓存中的数据与主存数据一致（clean)，当有一个CPU修改该缓存行中，其它CPU中该缓存行可以被作废（变成无效状态（Invalid））。

Invalid: 无效的

该缓存是无效的（可能有其它CPU修改了该缓存行）。再去内存里面读一遍

6、CPU乱序问题

如果一个cpu在执行的时候需要访问的内存都不在cache中，cpu必须要通过内存总线到主存中取，那么在数据返回到cpu这段时间内（这段时间大致为cpu执行成百上千条指令的时间，至少两个数据量级）干什么呢？

答案是：cpu会继续执行其他的符合条件的指令。比如cpu有一个指令序列 指令1  指令2  指令3 …， 在指令1时需要访问主存，在数据返回前cpu会继续后续的和指令1在逻辑关系上没有依赖的”独立指令”，cpu一般是依赖指令间的内存引用关系来判断的指令间的”独立关系”，具体细节可参见各cpu的文档。这也是导致cpu乱序执行指令的根源之一。

CPU为了提高指令执行效率，会在一条指令执行过程中（比如去内存读数据（慢100倍）），去同时执行另一条指令，前提是，两条指令没有依赖关系

对于写数据则会显得更加复杂一点：

当cpu执行存储指令时，它会首先试图将数据写到离cpu最近的L1_cache, 如果此时cpu出现L1未命中，则会访问下一级缓存。速度上L1_cache基本能和cpu持平，其他的均明显低于cpu，L2_cache的速度大约比cpu慢20-30倍，而且还存在L2_cache不命中的情况，又需要更多的周期去主存读取。其实在L1_cache未命中以后，cpu就会使用一个另外的缓冲区，叫做合并写存储缓冲区（WCBuffer，速度比L1_cache更快，所以应该看起来是很贵的，一般只有4个位置）。这一技术称为合并写入技术。在请求L2_cache缓存行的所有权尚未完成时，cpu会把待写入的数据写入到合并写存储缓冲区，该缓冲区大小和一个cache line大小，一般都是64字节。这个缓冲区允许cpu在写入或者读取该缓冲区数据的同时继续执行其他指令，这就缓解了cpu写数据时cache miss时的性能影响。

当后续的写操作需要修改相同的缓存行时，这些缓冲区变得非常有趣。在将后续的写操作提交到L2缓存之前，可以进行缓冲区写合并。 这些64字节的缓冲区维护了一个64位的字段，每更新一个字节就会设置对应的位，来表示将缓冲区交换到外部缓存时哪些数据是有效的。当然，如果程序读取已被写入到该缓冲区的某些数据，那么在读取缓存数据之前会先去读取本缓冲区的。

经过上述步骤后，缓冲区的数据还是会在某个延时的时刻更新到外部的缓存（L2_cache）.如果我们能在缓冲区传输到缓存之前将其尽可能填满，这样的效果就会提高各级传输总线的效率，以提高程序性能。

合并写代码验证：

/**
 * WCBuffer只有4个位置
 */
public final class WriteCombining {

    private static final int ITERATIONS = Integer.MAX_VALUE;
    private static final int ITEMS = 1 << 24;
    private static final int MASK = ITEMS - 1;

    private static final byte[] arrayA = new byte[ITEMS];
    private static final byte[] arrayB = new byte[ITEMS];
    private static final byte[] arrayC = new byte[ITEMS];
    private static final byte[] arrayD = new byte[ITEMS];
    private static final byte[] arrayE = new byte[ITEMS];
    private static final byte[] arrayF = new byte[ITEMS];

    public static void main(final String[] args) {

        for (int i = 1; i <= 3; i++) {
            System.out.println(i + " SingleLoop duration (ns) = " + runCaseOne());
            System.out.println(i + " SplitLoop  duration (ns) = " + runCaseTwo());
        }
    }

    public static long runCaseOne() {
        long start = System.nanoTime();
        int i = ITERATIONS;

        while (--i != 0) {
            int slot = i & MASK;
            byte b = (byte) i;
            arrayA[slot] = b;
            arrayB[slot] = b;
            arrayC[slot] = b;
            arrayD[slot] = b;
            arrayE[slot] = b;
            arrayF[slot] = b;
        }
        return System.nanoTime() - start;
    }

    public static long runCaseTwo() {
        long start = System.nanoTime();
        int i = ITERATIONS;
        while (--i != 0) {
            int slot = i & MASK;
            // 这里的b占了一个位置
            byte b = (byte) i;
            arrayA[slot] = b;
            arrayB[slot] = b;
            arrayC[slot] = b;
        }
        i = ITERATIONS;
        while (--i != 0) {
            int slot = i & MASK;
            // 这里的b占了一个位置
            byte b = (byte) i;
            arrayD[slot] = b;
            arrayE[slot] = b;
            arrayF[slot] = b;
        }
        return System.nanoTime() - start;
    }
}

结果显示：分开的情况效率更快。（因为充分了利用了合并写的技术）

6个的为什么会慢呢？

因为WCBuffer是4个位置，6=4+2,4个可以通过WCBuffer读取一次，但是还有2个必须要等后面来2个补充才能读取一次，这里也会浪费效率。

 

乱序执行的证明：

要执行蛮久才可能出现结果：

public class T04_Disorder {
    private static int x = 0, y = 0;
    private static int a = 0, b =0;

    public static void main(String[] args) throws InterruptedException {
        int i = 0;
        for(;;) {
            i++;
            x = 0; y = 0;
            a = 0; b = 0;
            Thread one = new Thread(new Runnable() {
                public void run() {
                    //由于线程one先启动，下面这句话让它等一等线程two. 读着可根据自己电脑的实际性能适当调整等待时间.
                    //shortWait(100000);
                    a = 1;
                    x = b;
                }
            });

            Thread other = new Thread(new Runnable() {
                public void run() {
                    b = 1;
                    y = a;
                }
            });
            one.start();other.start();
            one.join();other.join();
            String result = "第" + i + "次 (" + x + "," + y + "）";
            if(x == 0 && y == 0) {
                System.err.println(result);
                break;
            } else {
                //System.out.println(result);
            }
        }
    }


    public static void shortWait(long interval){
        long start = System.nanoTime();
        long end;
        do{
            end = System.nanoTime();
        }while(start + interval >= end);
    }
}

如何保证特定情况下不乱序？

1、硬件内存屏障（X86上）

• sfence: store| 在sfence指令前的写操作当必须在sfence指令后的写操作前完成。
• lfence：load | 在lfence指令前的读操作当必须在lfence指令后的读操作前完成。
• mfence：modify/mix | 在mfence指令前的读写操作当必须在mfence指令后的读写操作前完成。
• 原子指令，如x86上的”lock …” 指令是一个Full Barrier，执行时会锁住内存子系统来确保执行顺序，甚至跨多个CPU。Software Locks通常使用了内存屏障或原子指令来实现变、量可见性和保持程序顺序

2、JVM级别如何规范（JSR133）

（这是虚的东西，硬件内存屏障才是实在的，JVM只是定了规范，实现看虚拟机或者CPU具体的实现）

1. LoadLoad屏障：

• 对于这样的语句Load1; LoadLoad; Load2，
• 在Load2及后续读取操作要读取的数据被访问前，保证Load1要读取的数据被读取完毕。

1. StoreStore屏障：

• 对于这样的语句Store1; StoreStore; Store2，
• 在Store2及后续写入操作执行前，保证Store1的写入操作对其它处理器可见。

1. LoadStore屏障：

• 对于这样的语句Load1; LoadStore; Store2，
• 在Store2及后续写入操作被刷出前，保证Load1要读取的数据被读取完毕。

1. StoreLoad屏障：

• 对于这样的语句Store1; StoreLoad; Load2，
• 在Load2及后续所有读取操作执行前，保证Store1的写入对所有处理器可见。

volatile的实现细节

很多文章讲解volatile都比较凌乱，我这里从字节码、JVM、硬件层面上去分析一下。

1、字节码层面

（去看编译过后的字节码文件）只是加了个 ACC_VOLATILE

public class TestVolatile {
    int i;
    volatile int j;
}

字节码：

2、JVM层面

volatile内存区的读写 都加屏障

指令见上面 “JVM级别如何规范”

StoreStoreBarrier
volatile 写操作
StoreLoadBarrier

LoadLoadBarrier
volatile 读操作
LoadStoreBarrier

3、OS和硬件层面

这个要工具

想详细了解可以看一下这篇文章：https://blog.csdn.net/qq_26222859/article/details/52235930

使用hsdis观察汇编码
lock指令 执行指令的时候保证对内存区域的枷锁
hsdis - HotSpot Dis Assembler
在windows上 就是使用 lock 指令实现 | MESI实现

synchrnized实现细节

1、字节码层面

方法：ACC_SYSCHRONIZED

同步语句块：monitorenter/monitorexit。

public class TestSync {
    synchronized void m() {

    }

    void n() {
        synchronized (this) {

        }
    }

    public static void main(String[] args) {

    }
}

monitorenter：进入

第一个monitorexit：退出

第二个monitorexit：发现异常会自动退出

2、JVM层面

C/C++调用了操作系统提供的同步机制。

3、OS和硬件层面

X86：lock一个指令  各种各样的指令cmpxchg / xxx（lock是锁定，后面的是修改的意思）

详情：https://blog.csdn.net/21aspnet/article/details/88571740