[游戏开发]并发编程之可见性、有序性

一、可见性

1.1 不可见问题

这个案例比较简单，就是t1线程中用到了stop这个属性，接在在main线程中修改了 stop 这个属性的值来使得t1线程结束，但是t1线程并没有按照期望的结果执行。

public class VolatileExample {

    public static boolean stop=false;
    public static void main(String[] args) throws InterruptedException {
        Thread t1=new Thread(()->{
            int i=0;
            while(!stop){
                i++;
            }
        });
        t1.start();
        System.out.println("begin start thread");
        Thread.sleep(1000);
        stop=true;
    }
}

运行结果

1.2 volatile解决不可见问题

stop变量加上volatile修饰

public class VolatileExample {

    public volatile static boolean stop=false;
    public static void main(String[] args) throws InterruptedException {
        Thread t1=new Thread(()->{
            int i=0;
            while(!stop){
                i++;
            }
        });
        t1.start();
        System.out.println("begin start thread");
        Thread.sleep(1000);
        stop=true;
    }
}

运行结果

1.3 不可见原因

1.3.1 cup缓存由来

在整个计算机的发展历程中，除了CPU、内存以及I/O设备不断迭代升级来提升计算机处理性能之外，还有一个非常核心的矛盾点，就是这三者在处理速度的差异。CPU的计算速度是非常快的，其次是内存、最后是IO设备（比如磁盘），也就是CPU的计算速度远远高于内存以及磁盘设备的I/O速度。如下图所示，计算机是利用CPU进行数据运算的，但是CPU只能对内存中的数据进行运算，对于磁盘中的数据，必须要先读取到内存，CPU才能进行运算，也就是CPU和内存之间无法避免的出现了IO操作。而cpu的运算速度远远高于内存的IO速度，比如在一台2.4GHz的cpu上，每秒能处理2.4x10 9 次，每次处理的数据量，如果是64位操作系统，那么意味着每次能处理64位数据量。

虽然CPU从单核升级到多核甚至到超线程技术在最大化的提高CPU的处理性能，但是仅仅提升CPU性能是不够的，如果内存和磁盘的处理性能没有跟上，就意味着整体的计算效率取决于最慢的设备，为了平衡这三者之间的速度差异，最大化的利用CPU。所以在硬件层面、操作系统层面、编译器层面做出了很多的优化

1. CPU增加了高速缓存
2. 操作系统增加了进程、线程。通过CPU的时间片切换最大化的提升CPU的使用率
3. 编译器的指令优化，更合理的去利用好CPU的高速缓存
   每一种优化，都会带来相应的问题，而这些问题是导致线程安全性问题的根源，那接下来我们逐步去了解这些优化的本质和带来的问题。

1.3.2 cup缓存布局

CPU在做计算时，和内存的IO操作是无法避免的，而这个IO过程相对于CPU的计算速度来说是非常耗时，基于这样一个问题，所以在CPU层面设计了高速缓存，这个缓存行可以缓存存储在内存中的数据，CPU每次会先从缓存行中读取需要运算的数据，如果缓存行中不存在该数据，才会从内存中加载，通过这样一个机制可以减少CPU和内存的交互开销从而提升CPU的利用率。对于主流的x86平台，cpu的缓存行（cache）分为L1、L2、L3总共3级。

1.3.3 缓存一致性问题

CPU高速缓存的出现，虽然提升了CPU的利用率，但是同时也带来了另外一个问题–缓存一致性问题，这个一致性问题体现在多线程环境中，当多个线程并行执行加载同一块内存数据时，由于每个CPU都有自己独立的L1、L2缓存，所以每个CPU的这部分缓存空间都会缓存到相同的数据，并且每个CPU执行相关指令时，彼此之间不可见，就会导致缓存的一致性问题，据图流程如下图所示：

1.3.4 缓存一致性协议

为了达到数据访问的一致，需要各个处理器在访问缓存时遵循一些协议，在读写时根据协议来操作，常见的协议有MSI，MESI，MOSI等。最常见的就是MESI协议。接下来给大家简单讲解一下MESI。
MESI表示缓存行的四种状态，分别是

1. M(Modify[?m?d?fa?]) 表示共享数据只缓存在当前CPU缓存中，并且是被修改状态，也就是缓存的数据和主内存中的数据不一致
2. E(Exclusive[?k?sklu?s?v]) 表示缓存的独占状态，数据只缓存在当前CPU缓存中，并且没有被修改
3. S(Shared[?erd]) 表示数据可能被多个CPU缓存，并且各个缓存中的数据和主内存数据一致
4. I(Invalid[??nv?l?d]) 表示缓存已经失效
   在CPU的缓存行中，每一个Cache一定会处于以下三种状态之一
   Shared
   Exclusive
   Invalid
   
   
   
   注意:MESI协议只对汇编指令中执行加锁操作的变量有效，表现到java中为使用voliate关键字定义变量或使用加锁操作

二、有序性

2.1 指令重排序问题

public class SeqExample {
    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 t1=new Thread(()->{
                a=1;
                x=b;

                //
                x=b;
                a=1;
            });
            Thread t2=new Thread(()->{
                b=1;
                y=a;
                //
                y=a;
                b=1;
            });
            /**
             * 可能的结果：
             *  1和1
             *  0和1
             *  1和0
             *  ----
             *  0和0
             */
            t1.start();
            t2.start();
            t1.join();
            t2.join();
            String result="第"+i+"次("+x+","+y+")";
            if(x==0&&y==0){
                System.out.println(result);
                break;
            }else{

            }
        }
    }
}

运行结果

2.2 volatile解决指令重排序问题

public class SeqExample {
    private volatile static int x=0,y=0;
    private volatile 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 t1=new Thread(()->{
                a=1;
                x=b;

                //
                x=b;
                a=1;
            });
            Thread t2=new Thread(()->{
                b=1;
                y=a;
                //
                y=a;
                b=1;
            });
            /**
             * 可能的结果：
             *  1和1
             *  0和1
             *  1和0
             *  ----
             *  0和0
             */
            t1.start();
            t2.start();
            t1.join();
            t2.join();
            String result="第"+i+"次("+x+","+y+")";
            if(x==0&&y==0){
                System.out.println(result);
                break;
            }else{

            }
        }
    }
}

运行结果(程序不会停)

2.3 内存屏障

CPU在性能优化道路上导致的顺序一致性问题，在CPU层面无法被解决，原因是CPU只是一个运算工具，它只接收指令并且执行指令，并不清楚当前执行的整个逻辑中是否存在不能优化的问题，也就是说硬件层面也无法优化这种顺序一致性带来的可见性问题。
因此，在CPU层面提供了写屏障、读屏障、全屏障这样的指令，在x86架构中，这三种指令分别是SFENCE、LFENCE、MFENCE指令，

• sfence：也就是save fence，写屏障指令。在sfence指令前的写操作必须在sfence指令后的写操作前完成。
• lfence：也就是load fence，读屏障指令。在lfence指令前的读操作必须在lfence指令后的读操作前完成。
• mfence：也就是modify/mix，混合屏障指令，在mfence前得读写操作必须在mfence指令后的读写操作前完成。
  在Linux系统中，将这三种指令分别封装成了, smp_wmb-写屏障 、 smp_rmb-读屏障 、 smp_mb-读写屏障三个方法

被volatile修饰的变量在编译成字节码文件时会生成多个lock指令，该指令在执行过程中会生成相应的内存屏障，以此来解决可见性跟重排序的问题。
内存屏障的作用：
1.在有内存屏障的地方，会禁止指令重排序，即屏障下面的代码不能跟屏障上面的代码交换执行顺序。
2.在有内存屏障的地方，线程修改完共享变量以后会马上把该变量从本地内存写回到主内存，并且让其他线程本地内存中的该变量副本失效（使用MESI协议）

三、JMM

下图所示，在不同的CPU架构中，为了避免因为指令重排序、或者缓存一致性问题，都提供了不同的内存屏障指令。同时，在不同的操作系统中，也都会实现封装一个内存屏障的实现。
那么，我们写的Java线程，如何能够在不同的硬件、不同操作系统下，仍然能够保证线程安全性呢？这就要引出JMM（Java 内存模型），它就是为了屏蔽操作系统和硬件的差异，让一套代码在不同平台下都能达到线程安全的访问目的。

3.1 JMM介绍

首先，我们都知道Java程序是运行在Java虚拟机上的，同时我们也知道，JVM是一个跨语言跨平台的实现，也就是Write Once、Run Anywhere。那么JVM如何实现在不同平台上都能达到线程安全的目的呢？所以这个时候JMM出来了，Java内存模型（Java Memory Model ,JMM）就是一种符合内存模型规范的，屏蔽了各种硬件和操作系统的访问差异的，保证了Java程序在各种平台下对内存的访问都能保证效果一致的机制及规范。Java内存模型规定了所有的变量都存储在主内存中，每条线程还有自己的工作内存，线程的工作内存中保存了这个线程中用到的变量的主内存副本拷贝，线程对变量的所有操作都必须在工作内存中进行，而不能直接读写主内存。不同的线程之间也无法直接访问对方工作内存中的变量，线程间变量的传递均需要自己的工作内存和主存之间进行数据同步进行，流程图如下：

再总结一下： JMM定义了共享内存中多线程程序读写操作的行为规范：在虚拟机中把共享变量存储到内存以及从内存中取出共享变量的底层实现细节。目的是解决由于多线程通过共享内存进行通信时，存在的本地内存数据不一致、编译器会对代码指令重排序、处理器会对代码乱序执行等带来的问题。本地内存是JMM的一个抽象概念，并不真实存在。它涵盖了缓存，写缓冲区，寄存器以及其他的硬件和编译器优化。实际上，不难发现JMM的整个模型实际上CPU高速缓存和内存交互的模型是一致的，因为不管软件怎么设计，最终还是由硬件来执行。而这个抽象模型的意义就在于，它可以针对不同平台来保证并发场景下的可见性问题。

3.2 JMM在JVM中实现的相关源码

java内存屏障

inline void OrderAccess::loadload()  { acquire(); }
inline void OrderAccess::storestore() { release(); }
inline void OrderAccess::loadstore() { acquire(); }
inline void OrderAccess::storeload() { fence(); }

orderAccess_linux_x86.inline

inline void OrderAccess::fence() {
 if (os::is_MP()) {
  // always use locked addl since mfence is sometimes expensive
#ifdef AMD64
  __asm__ volatile ("lock; addl $0,0(%%rsp)" : : : "cc", "memory");
#else
  __asm__ volatile ("lock; addl $0,0(%%esp)" : : : "cc", "memory");
#endif
}
}

orderAccess_linux_sparc.inline

inline void OrderAccess::fence() {
 __asm__ volatile ("membar #StoreLoad" : : :);
}

OrderAccess::storeload();
ACC_VOLATILE
bool is_volatile () const { return (_flags & JVM_ACC_VOLATILE ) != 0; }

四、Happens-Before模型

前面说了这么多，都是为了讲解清楚，到底是什么原因导致了在多线程环境下的可见性和有序性问题。并且也了解了volatile解决可见性问题的本质。那么有没有哪些情况是，不需要通过增加volatile关键字，也能保证在多线程环境下的可见性和有序性的呢？从JDK1.5开始，引入了一个happens-before的概念来阐述多个线程操作共享变量的可见性问题。所以我们可以认为在JMM中，如果一个操作执行的结果需要对另一个操作可见，那么这两个操作必须要存在happens-before关系。这两个操作可以是同一个线程，也可以是不同的线程。happens-before，字面意思，先行发生，以Java层面来理解的话就是，上一行代码的结果会被下一行代码所使用到，这就是先行发生。

4.1 程序顺序规则

一个线程中的每个操作，happens-before这个线程中的任意后续操作，可以简单认为是as-if-serial。as-if-serial的意思是，不管怎么重排序，单线程的程序的执行结果不能改变。处理器不能对存在依赖关系的操作进行重排序，因为重排序会改变程序的执行结果。对于没有依赖关系的指令，即便是重排序，也不会改变在单线程环境下的执行结果。具体来看下面这段代码，A和B允许重排序，但是C是不允许重排，因为存在依赖关系。根据as-if-serial语义，在单线程环境下， 不管怎么重排序，最终执行的结果都不会发生变化。

int a=2; //A
int b=2; //B
int c=a*b; //C

4.2 传递性规则

仍然看下面这段代码，根据程序顺序规则可以知道，这三者之间存在一个happens-before关系。

int a=2; //A
int b=2; //B
int c=a*b; //C

• A happens-before B。
• B happens-before C。
• A happens-before C。
  这三个happens-before关系，就是根据happens-before的传递性推导出来的。不是说A和B之间允许重排序吗？那是不是A happens-before B不一定存在，也可能是B可以重排序在A之前执行呢？没错，确实是这样，JMM不要求A一定要在B之前执行，但是他要求的是前一个操作的执行结果对后一个操作可见。这里操作A的执行结果不需要对操作B可见，并且重排序操作A和操作B后的执行结果与A happens-before B顺序执行的结果一致，这种情况下，是允许重排序的。

4.3 volatile变量规则

对于volatile修饰的变量的写操作，一定happens-before后续对于volatile变量的读操作，这个是因为volatile底层通过内存屏障机制防止了指令重排，这个规则前面已经分析得很透彻了，所以没什么问题，我们再来观察如下代码，基于前面两种规则再结合volatile规则来分析下面这个代码的执行顺序，假设两个线程A和B，分别访问writer方法和reader方法，那么它将会出现以下可见性规则。

public class VolatileExample {
  int a=0;
  volatile boolean flag=false;
  public void writer(){
    a=1;       //1
    flag=true;    //2
 }
  public void reader(){
    if(flag){   //3
      int i=a;   //4
   }
 }
}

• 1 happens before 2、 3 happens before 4， 这个是程序顺序规则
• 2 happens before 3、 是由volatile规则产生的，对一个volatile变量的读，总能看到任意线程对这个volatile变量的写入。
• 1 happens before 4， 基于传递性规则以及volatile的内存屏障策略共同保证。
  那么最终结论是，如果在线程B执行reader方法时，如果flag为true，那么意味着 i=1成立。
  
  这里有人可能会有疑问说，你前面讲的程序顺序规则中，在单线程中，如果两个指令之间不存在依赖关系，是允许重排序的，也就是1 和 2的顺序可以重排，那么是不是意味着最终4输出的结果是0呢？这里也是因为volatile修饰的重排序规则的存在，导致1和2是不允许重排序的，在volatile重排序规则表中，如果第一操作是普通变量的读/写，第二个操作是volatile的写，那么这两个操作之间不允许重排序。
  

4.4 监视器锁规则

一个线程对于一个锁的释放锁操作，一定happens-before与后续线程对这个锁的加锁操作。

public class Synchronizedrule {

    private Object ob = new Object();

    int x = 10;

    private void testRule(){
        synchronized (ob){ // 此处自动加锁
            // x 是共享变量, 初始值 =10
            System.out.println(x);
            if (this.x < 12) {
                this.x = 12;
            }
        } // 此处自动解锁
    }

    public static void main(String[] args) throws InterruptedException {
        Synchronizedrule synchronizedrule = new Synchronizedrule();
        Thread thread1 = new Thread(() -> {
            synchronizedrule.testRule();
        });
        Thread thread2 = new Thread(() -> {
            synchronizedrule.testRule();
        });
        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();
    }
}

假设x的初始值是10，线程A执行完代码块后，x的值会变成12，执行完成之后会释放锁。 线程B进入代码块时，能够看到线程A对x的写操作，也就是B线程能够看到x=12。

4.5 start规则

如果线程A执行操作ThreadB.start(),那么线程A的ThreadB.start()之前的操作happens-before线程B中的任意操作。

public class StartDemo {

    static int x=0;

    public static void main(String[] args){
        Thread t1 = new Thread(()->{
            // 主线程调用 t1.start() 之前
            // 所有对共享变量的修改，此处皆可见
            // 此例中，x==10
            System.out.println(x);
        });
        // 此处对共享变量 x修改
        x = 10;
        // 主线程启动子线程
        t1.start();
    }
    
}

4.6 join规则

join规则，如果线程A执行操作ThreadB.join()并成功返回，那么线程B中的任意操作happens-before于线程A从ThreadB.join()操作成功的返回。

public class JoinRule {

    static int x = 10;

    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(() -> {
            // 此处对共享变量 x 修改
            x = 100;
        });
    // 例如此处对共享变量修改，
    // 则这个修改结果对线程 t1 可见
    // 主线程启动子线程
        t1.start();
        t1.join();
    // 子线程所有对共享变量的修改
    // 在主线程调用 t1.join() 之后皆可见
    // 此例中，x==100
        System.out.println(x);
    }
    
}

五、DCL重排序

5.1 DCL错误写法

public class Singleton {
    private static Singleton singleton;

    private Singleton() {
    }

    public static Singleton getInstance() {
        if (singleton == null) {
            synchronized (Singleton.class) {
                if (singleton == null) singleton = new Singleton();
            }

        }
        return singleton;
    }

}

这个代码看起来perfect：
1、如果检查第一一个singleton不为null，则不需要执行加锁动作，极大的提高了性能
2、如果第一个singleton为null，即使有多个线程同时判断，但是由于synchronized的存在，只有一个线程能创建对象
3、当第一个获取锁的线程创建完成singleton对象后，其他的在第二次判断singleton一定不会为null，则直接返回已经创建好的singleton对象
DCL看起来非常完美，但其实这个是不正确的。逻辑没问题，分析也没问题？但为何是不正确的？不妨我们先回顾一下创建对象的过程
1、为对象分配内存空间
2、初始化对象
3、将内存空间的地址赋值给对应的引用
但由于jvm编译器的优化产生的重排序缘故，步骤2、3可能会发生重排序：
1、为对象分配内存空间
2、将内存空间的地址赋值给对应的引用
3、初始化对象
如果2、3发生了重排序就会出现第二个线程访问的时候最外层的判断singleton != null的情况，但是它其实仅仅只是一个地址而已，此时对象还没有被初始化，所以return的singleton对象是一个没有被初始化的对象，那么我们就可以解决？

5.2 DCL正确写法

解决方法
利用volatile的特性即可阻止重排序和可见性

public class Singleton {
    private volatile static Singleton singleton;

    private Singleton() {
    }

    public static Singleton getInstance() {
        if (singleton == null) {
            synchronized (Singleton.class) {
                if (singleton == null) singleton = new Singleton();
            }

        }
        return singleton;
    }

}

阅读世界，共赴山海

423全民读书节，邀你共读