基于共享内存的并发编程

在基于共享内存的并发编程中，线程间通过读写共享的变量进行隐式的通信。在多线程并发读写共享变量的场景下，如果没有进行正确的同步，将会导致一些非预期的结果。

在编写正确的并发代码中，我们主要需要关注以下3个点

• 原子性：什么操作在什么条件下是原子的

• 可见性：一个线程对一个共享变量的写操作，写入的值在什么条件下，其它线程能够读到

• 有序性：在同一个线程内，代码的执行顺序看起来与编写的代码顺序一致。在正确同步下，一个线程(通过共享变量)观察另一个线程代码的执行顺序，看起来与编写的代码顺序一致

我们先看下面的case

    private static int a = 0;   
    private static int b = 0;

    // 线程A执行
    public static void threadRunA(){
        a = 1;
        b = 1;
    }
    // 线程B执行
    public static void threadRunB(){
        while (b != 1){}
        assert(a == 1);
    }

线程AB并发执行，线程B中的断言是否一定成功？

由于上述方法threadRunA，threadRunB运行在不同的线程中，且对于共享变量a,b的读写没有进行同步，因此在线程B通过共享变量a,b中观察线程A的赋值逻辑的顺序不一定是a先赋值，b再赋值。所以断言不一定成功

对于操作的原子性，大家其实都比较了解，比如 i++这样的代码就不是原子的。

但是基于我们平常的认知：

• 一个变量如果被写入，那么在此之后对该变量的访问，应该都能读取到最新写入的值。
• 一段代码的编写顺序与最终执行的顺序应该相同。

如上认知被称为顺序一致性。 实际上，顺序一致性在单线程下总是是成立的（如果不成立的话连程序运行正确都无法保证），但在多线程的情况下，只有在正确同步的情况下才能成立

why？如果我们进行并发编程的时候没有正确的同步，是什么影响到程序的顺序一致性？

主要原因在于编译器与处理器对于程序执行的优化，影响顺序一致性的优化：

• CPU高速缓存
• CPU指令重排序
• 编译器重排序

CPU高速缓存

随着现代处理器速度与主存访问速度的差距逐渐加大，硬件设计者不得不在CPU的核与主存之间添加新的高速存储器作为缓存，来提高CPU的处理速度。

加入高速缓存后，那么就在多核CPU上，如何保证不同核的高速缓存的缓存一致性？如果一个内存地址的值在高速缓存中与主存，或者其他高速缓存中不同，那么势必引起可见性问题

先来看一下高速缓存的读写策略

CPU高速缓存读策略

先读高速缓存，读不命中再从主存中加载

CPU高速缓存写策略

直写：直接写入主存，每次都会引起总线IO

写回：先写入高一级缓存中，待条件满足（缓存行被替换时），再将缓存数据写入下

级缓存（或主存）。尽量降低总线IO

目前现代CPU主要使用写回

由此看来，高速缓存的读写策略会造成的可见性问题

CPU指令重排序

顺序执行指令将无法充分利用CPU，在不影响（单线程）执行结果的前提下，通过引入流水线指令并行来提高性能。在这种情况下指令的执行可能会被重排序

多线程下指令执行重排序导致有序性问题

解决多线程下上述优化带来的问题，系统的设计者提供的一种特殊的指令，内存屏障

内存屏障指令主要提供两个功能

• 确保CPU间的缓存一致性
• 确保指令顺序执行

处理器上内存屏障的分类

Store屏障 : 保证所有在store屏障指令之前的store指令，都在该store屏障指令执行之前被执行，并且store指令写入所有CPU可见的公共区域

Load屏障 : 保证所有在load屏障指令之后的load指令，都在该load屏障指令执行之后被执行，并且load指令从所有CPU可见的公共区域读取

Full屏障 : 同时具有Store屏障与Load屏障的功能

通过在适当位置插入内存屏障指令，阻止指令重排，引发高速缓存行失效或写回，保证多线程下的可见性与有序性

编译器重排序优化

（单线程内）不存在数据依赖的代码，编译器可能会在编译时进行重排序优化，编译器重排序造成有序性问题

语言层面的内存模型在一定条件下禁止某些编译器重排序，以解决多线程下编译器重排序带来的有序性问题

内存模型

之前提到的三种优化，要保证程序的正确运行，就必须在一定的规则下进行。设计人员使用内存模型用以描述这些规则

回到最初提到的原子性，可见性与有序性，即内存模型描述了

• 原子性：什么操作在什么条件下是原子的
• 可见性：一个线程对一个共享变量的写操作，写入的值在什么条件下，其它线程能够读到
• 有序性：在同一个线程内，代码的执行顺序看起来与编写的代码顺序一致。什么情况下，一个线程(通过共享变量)观察另一个线程代码的执行顺序，与编写的代码顺序一致

顺序一致性内存模型

设计人员提出的理想模型，最佳的易编程性，最低的性能

• 所有操作都是原子的
• 所有操作都是立即对其他CPU可见的
• 一个线程内的操作都是按编码顺序执行的

java内存模型

基于易编程性与性能优化的考虑，放松顺序一致性模型的限制，使得一些优化操作可以进行

• 定义某些操作是原子的（例：long读原子，long写不一定原子）
• 在正确同步下，读写操作是立即可见的（例：volatile变量的读写是可见的，满足happens-before关系的操作是可见的）
• 在正确同步下，一个线程(通过共享变量)观察另一个线程代码的执行顺序，与编写的代码顺序一致

基本类型的读写原子性

• 除long类型的写，其余基本类型的读写均具有原子性
• long 类型的写可分为2个32位的写
• volatile变量读写都是原子的

可见性的保证，读写操作之间的 happens-before 关系

定义：如果操作1 happens-before 操作2，则操作1对操作2可见；操作1与操作2可以分布于不同线程

规则：

• 程序顺序规则：同一线程内，任何操作 hb 该操作的后续操作
• 监视器锁规则：对于同一个锁，释放该锁的操作 hb 获取该锁的操作
• volatile变量规则：对一个volatile变量的写，hb 对该变量的读
• 传递规则：A hb B, B hb C , 则 A hb C

例：

    private static int a = 0;   
    private static volatile int b = 0;

    // 线程A执行
    public static void threadRunA(){
        a = 1;
        b = 1;
    }
    // 线程B执行
    public static void threadRunB(){
        if (b == 1)
            assert(a == 1);
    }

根据 happens-before 关系规则,推断 assert(a == 1) 是否一定成功

如下图所示

• 根据程序顺序规则，A线程中赋值操作 a = 1 happens-before 赋值操作b = 1
• 根据volatile变量规则，A线程中赋值操作b = 1 happens-before B线程中条件判断 if(b == 1) 中对b的读取
• 根据程序顺序规则， B线程中，条件判断 if(b == 1) happens-before 断言Assert(a == 1)
• 根据传递规则，A线程中赋值操作 a = 1 happens-before B线程中断言 Assert(a == 1)

综上：A线程中赋值操作 a = 1 对 B线程中断言 Assert(a == 1) 一定可见，因此断言一定成功

不同处理器平台内存屏障指令在java内存模型中的抽象分类

LoadLoad 屏障： Load1,Loadload,Load2 ；在Load1与Load2操作之间插入 确保Load1及之前Load所要读入的数据能够在被Load2及后续的load指令访问前读入。

StoreStore 屏障： Store1，StoreStore，Store2；在Store1与Store2操作之间插入， 确保Store1及之前Stroe的数据在Store2及后续Store指令操作相关数据之前对其它处理器可见

LoadStore 屏障： Load1; LoadStore; Store2；在Load1与Store2之间插入， 确保Load1及之前Load的数据在Store2及后续Store指令可见之前读取。

StoreLoad 屏障： Store1; StoreLoad; Load2；在Store1与Load2之间插入， 确保Store1及之前Store的数据在被Load2及后续的Load指令读取之前对其他处理器可见。

不同平台下 jvm 通过使用具体指令实现上述屏障，比如通过处理器的全屏障实现StoreLoad屏障

对象的发布与安全初始化

先说明两个概念：对象发布与对象逸出

• 对象发布：使一个对象能够被当前作用域外访问到，称为发布对象
• 对象逸出：不正确的发布对象，称为对象逸出

再来看一下经典的未能正确同步导致的可见性与有序性问题，双重检查锁构造单例

public class SingleTon {

    private static SingleTon instance;
    private int a;
    private int b;

    private SingleTon(){
        a = 10;
        b = 10;
    }

    public static SingleTon getInstance(){
        if (instance == null){
           synchronized (SingleTon.class){
               if (instance == null){
                   instance = new SingleTon();
               }
           }
        }
        return instance;
    }
}

让我们先把对象构造过程分解：

    instance = new SingleTon(); 

变为

//构造函数
SingleTon tmp = 堆上分配空间
//执行构造函数
tmp.a = 10； //store1
tmp.b = 10;   //store2
instance = tmp; // store3, 对象引用赋值给静态引用变量，对象被发布，之后其他线程可以访问到单例变量

将分解后的代码代入原getInstance方法

public static SingleTon getInstance(){
        if (instance == null){                        // load 1
           synchronized (SingleTon.class){
               if (instance == null){                 // load 2
                    SingleTon tmp = 分配空间
                    tmp.a = 10；                      // store1
                    tmp.b = 10;                       // store2
                    instance = tmp;                   // store3
               }
           }
        }
        return instance;                             // load4       
}

让我们考虑以下两种情况：

• 当store3写入的数据缓存行写回主存，stroe1或store2写入的数据还未写回
• stroe1或stroe2 与 store3 发生重排序

出现以上两种情况，将会使其他线程拿到未初始化完成的单例对象

从有序性和可见性角度分析

称执行 instance = new SingleTon() 的线程为初始化线程

对于其他线程来说，return时，初始化线程的store1 与 store2 不一定可见，并且其他线程观察到初始化线程的store1，store2 与 store3 的有序性不能得到保证

如何解决，google告诉我们，只要在把instance用volatile修饰便可解决，why？

祭出java内存模型的happens-before规则

在用volatile修饰instance后,stroe3 变为 voaltile写，load4 变为volatile读

根据程序顺序规则：同一线程内，任何操作 hb 该操作的后续操作

我们推出 stroe1 与 stroe2 hb store3 （初始化线程单一线程内）

根据volatile变量规则：对一个volatile变量的写，hb 对该变量的读

我们推出 store3 hb load4

根据传递规则，stroe1 与 stroe2 hb store3，store3 hb load4 => store1,store2 hb load4

可以得到，当其他线程通过load4拿到单例时，store1与store2已经对其可见，不会再取得一个未初始化完成的对象

java内存模型提供给程序员的关键字

关键字特性及原理-synchronize

作用：

• 构造临界区，保证原子性
• 阻止临界区内与临界区外的操作重排序
• 保证临界区内写操作对退出临界区后（其他线程）再次进入相同临界区的读操作可见，构建happens-before关系

synchronize如何保证可见性与有序性：

• 禁止临界区内与临界区外的操作编译器重排序
• 通过（显式或隐式）插入内存屏障限制处理器重排序，并使CPU缓存写回

屏障插入规则：

可见在退出临界区时，会插入StroeLoad类型的内存屏障，对应于具体的处理器内存屏障为全屏障

关键字特性及原理-volatile

volatile变量特性：

• 可见性，volatile 写读构建 happens-before 关系
• 读写原子性

volatile如何保证可见性与有序性：

编译器重排序的限制

java内存模型限制编译器对volatile变量读写的重排

• volatile读不能重排到任何读写操作之后
• volatile写不能重排到任何读写操作之前

处理器重排序的限制及CPU缓存写回（通过内存屏障实现）

重点关注voaltile写与voaltile读之间的StoreLoad（全屏障）

不可变类

在介绍关键字final前，先说一下不可变类的相关概念

不可变类:类对象初始化后，运行中不能（不会）被改变

对于不可变类的对象，多线程访问时无需进行同步。典型的例子就是String类，String类是线程安全的，原因就是String类对象是不可变的

构造不可变对象

（真）不可变类 vs 事实不可变类

事实不可变对象，顾名思义就是其在初始化后，不会再有代码取改变它。构造事实不可变对象只需保证初始化后没有代码去修改他，但是其在编译器层面没有限制，因此存在误用导致多线程问题

（真）不可变对象，即在编译器层面就杜绝了初始化后对其的修改。我们都知道，通过final关键字修饰变量，就能使该变量在初始化后不能再被修改。因此构造（真）不可变对象，我们需要：

• 将类成员变量全部用final修饰
• 若类成员变量为引用，需要其引用的类为不可变类

构造不可变类完成，是不是我们就能多线程下高枕无忧的去并发访问该类的对象了呢。其实还有一个问题，我们要注意到不可变类是在初始化完成后才不可变的，而初始化时是在改变的，之前讨论对象的发布与逸出时已经说过对象在初始化时多线程可见性与有序性的问题。

因此只有在正确构造不可变类，并安全的发布类对象，我们才能在多线程中无需同步的访问

关键字特性及原理-final

作用：（修饰变量）初始化赋值后无法修改

对于final变量，java内存模型要求做如下处理

• 构造函数中final基本类型变量的写，与构造函数return后被构造对象的引用赋值给一个引用变量，这两个操作不能重排序（编译器与处理器重排）
• 构造函数中对final引用的对象的成员域的写，与构造函数return后被构造对象的引用赋值给一个引用变量，这两个操作不能重排序（编译器与处理器重排）

通过在final变量写与引用变量赋值之前插入写屏障保证CPU缓存写回与处理器重排序禁止

回到之前的双重检查锁：现在成员变量a,b 由final修饰

public static SingleTon getInstance(){
        if (instance == null){                            // load 1
           synchronized (SingleTon.class){
               if (instance == null){                     // load 2
                    SingleTon tmp = 分配空间
                    tmp.a = 10；                          // store1
                    tmp.b = 10;                           // store2
                    //stroe屏障
                    instance = tmp;                       // store3
               }
           }
        }
        return instance;                                  // load4       
}

stroe1与store2无法重排到store3之后，并且在stroe3执行前store1与stroe2写入的数据已写回

注意：不要在构造函数中逸出this引用

this引用的逸出：在构造函数中将this引用赋值给一个引用，使得其他线程可以访问到该对象

如果this引用在构造函数中逸出（因为重排序，即使逸出在构造函数最后也不行！），那么在构造函数完成前，其他线程将能访问到这个未完全初始化的对象

在this引用没有逸出的情况下，所有线程都能看到构造函数给对象的各个final字段设置的正确值，而不管采用何种方式来发布对象。

因此可以通过final构造不可变对象，并安全的发布，而不需要其他的同步手段

因此在我们的双重检查锁的例子中，如果将a,b变量改为final，也可以解决问题

无锁的基础-CAS

CAS 指的是现代 CPU 广泛支持的一种对内存中的共享数据进行操作的一种特殊指令。这个指令会对内存中的共享数据做原子的读写操作

CAS 为compare and swap的缩写，中文翻译成比较并交换。

指令的主要操作过程 : 给出要更新变量A，预期值B，新值C，若A等于B，则将C赋值给A, 并返回成功，否则返回失败。整个操作是原子的

通过CAS实现原子自增的一个例子 ：

    class AtomicInt{
        int i;
        public void increment(){
            for(;;){
                int current = i;
                int expected = current + 1;
                if (CAS(i, current, expected)){
                    return;
                }
            }
        } 
    }

CAS 在 x86下的指令实现为 lock cmpxchg ……

比较并交换指令为cmpxchg，这里主要关注其前缀 lock

通过查阅手册，了解lock前缀指令的作用

• 锁总线或缓存行，直到lock后的指令执行完成，保证原子
• lock后的写操作会写回已修改的数据（volatile写语义），同时让其它CPU相关缓存失效，从而重新从主存中加载最新的数据（volatile读语义）
• 类似内存屏障，阻止指令两端的指令重排序

基于以上特性，事实上lock前缀可以实现内存屏障的功能。比如jvm在x86下,volatile写操作后插入的StoreLoad屏障实际上并不是使用 mfence（全屏障） 指令，而是使用lock指令

CAS同时具有volatile读与写的内存语义。可以构造happens-before关系

CAS规则：CAS更新一个变量，happnes-before 之后对该变量的读

CAS在java的并发包被广泛应用，现在简单分析一下AQS（AbstractQueuedSynchronizer），推导一下通过AQS的lock（加锁）与release（释放锁），如何实现与临界区进入退出的内存语义

源码分析不在此多说，有兴趣可以自己去看。我这里描述一下其lock与releas的主要操作

AQS 拥有一个volatile成员变量用于保存当前锁状态（是否被持有），称为state

lock时，CAS写入state为持有，若成功则线程持有锁，并进入临界区。若不成功则被阻塞

release时，写入state为未持有

根据java内存模型happens-before规则中的监视器锁规则：对于同一个锁，释放该锁的操作 hb 获取该锁的操作

AQS release释放时进行volatile写state，lock时volatile读这个state

根据volatile规则，release hb lock，可见使用并发包中的AQS实现（ReentrantLock）也能具有监视器锁规则所带来的happens-before关系 (实际上synchronize底层实现也使用了CAS）

to be continue