并发编程(三) - 重排序,happens-before原则,顺序一致性_重排序遵循的原则

重排序是指编译器和处理器为了优化程序性能而对指令序列进行重新排序的一种手段。

上一篇文章中已经介绍了从Java源代码到最终实际执行的指令序列，会分别经历下面3种重排序：

1属于编译器重排序，2和3属于处理器重排序。

     这些重排序可能会导致多线程程序出现内存可见性问题。在单线程程序中，对存在控制依赖的操作重排序，不会改变执行结果（这也是as-if-serial语义允许对存在控制依赖的操作做重排序的原因）；但在多线程程序中，对存在控制依赖的操作重排序，可能会改变程序的执行结果。

1. 数据依赖性（针对单个处理器而已）

如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性。数据依赖分为下列3种类型，

上面三种情况，只要重排序两个操作的执行顺序，程序的执行结果将会被改变。

前面提到过，编译器和处理器可能会对操作做重排序。编译器和处理器在重排序时，会遵守数据依赖性，编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序。

注意，这里所说的数据依赖性仅针对单个处理器中执行的指令序列和单个线程中执行的操作，不同处理器之间和不同线程之间的数据依赖性不被编译器和处理器考虑。

2. AS-IF-SERIAL 语义

       as-if-serial语义的意思是，所有的动作(Action)都可以为了优化而被重排序，但是必须保证它们重排序后的结果和程序代码本身的应有结果是一致的。Java编译器、运行时和处理器都会保证单线程下的as-if-serial语义。 比如，为了保证这一语义，重排序不会发生在有数据依赖的操作之中。编译器，runtime 和处理器都必须遵守 as-if-serial 语义。为了遵守 as-if-serial 编译器和处理器不会对存在数据依赖关系的操作做重排序，因为这种重排序会改变执行结果。但是如果操作之间没有数据依赖关系，这些操作就可能被编译器和处理器重排序。如下面的代码:   

int a = 1;
int b = 2;
int c = a + b;

将上面的代码编译成Java字节码或生成机器指令，可视为展开成了以下几步动作（实际可能会省略或添加某些步骤）。

1. 对a赋值1
2. 对b赋值2
3. 取a的值
4. 取b的值
5. 将取到的两个值相加后存入c

在上面5个动作中，动作1可能会和动作2、4重排序，动作2可能会和动作1、3重排序，动作3可能会和动作2、4重排序，动作4可能会和1、3重排序。但动作1和动作3、5不能重排序。动作2和动作4、5不能重排序。因为它们之间存在数据依赖关系，一旦重排，as-if-serial语义便无法保证。

      as-if-serial语义把单线程程序保护了起来，as-if-serial语义使单线程程序员无需担心重排序会干扰他们，也无需担心内存可见性问题。

===========================================================

回顾一下前面一章节介绍的JMM的内存模型. 

      在这种模型下会存在一个现象，即缓存(工作内存)中的数据与主内存的数据并不是实时同步的，各CPU（或CPU核心）间缓存的数据也不是实时同步的。这导致在同一个时间点，各CPU所看到同一内存地址的数据的值可能是不一致的。从程序的视角来看，就是在同一个时间点，各个线程所看到的共享变量的值可能是不一致的。

       有的观点会将这种现象也视为重排序的一种，命名为“内存系统重排序”。因为这种内存可见性问题造成的结果就好像是内存访问指令发生了重排序一样。

    小结:  所以重排序实际上有两种情况:   指令重排序和内存系统重排序. 

   在计算机中，软件技术和硬件技术有一个共同的目标：在不改变程序执行结果的前提下，尽可能的开发并行度。这就是重排序的由来。

3. happens-before原则

   在上一篇文章中我们介绍过happens-before原则，我们知道Java的目标是成为一门平台无关性的语言，即Write once, run anywhere. 但是不同硬件环境下指令重排序的规则不尽相同。例如，x86下运行正常的Java程序在IA64下就可能得到非预期的运行结果。下面是常见处理器允许的重排序操作类型的列表：

为此，JSR-1337制定了Java内存模型(Java Memory Model, JMM)，旨在提供一个统一的可参考的规范，屏蔽平台差异性。从Java 5开始，Java内存模型成为Java语言规范的一部分。

根据Java内存模型中的规定，可以总结出以下几条happens-before规则8。Happens-before的前后两个操作不会被重排序且后者对前者的内存可见。

• 程序次序法则：线程中的每个动作A都happens-before于该线程中的每一个动作B，其中，在程序中，所有的动作B都能出现在A之后。
• 监视器锁法则：对一个监视器锁的解锁 happens-before于每一个后续对同一监视器锁的加锁。
• volatile变量法则：对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。
• 线程启动法则：在一个线程里，对Thread.start的调用会happens-before于每个启动线程的动作。
• 线程终结法则：线程中的任何动作都happens-before于其他线程检测到这个线程已经终结、或者从Thread.join调用中成功返回，或Thread.isAlive返回false。
• 中断法则：一个线程调用另一个线程的interrupt happens-before于被中断的线程发现中断。
• 终结法则：一个对象的构造函数的结束happens-before于这个对象finalizer的开始。
• 传递性：如果A happens-before于B，且B happens-before于C，则A happens-before于C

Happens-before关系只是对Java内存模型的一种近似性的描述，它并不够严谨，但便于日常程序开发参考使用，关于更严谨的Java内存模型的定义和描述，请阅读JSR-133原文或Java语言规范章节17.4。

4. 重排序对多线程的影响 

class Demo {
  int a = 0;
  boolean flag = false;
 
  public void write() {
    a = 1;          // 操作1
    flag = true;    //操作2
  }
 
  public void read() {
    if(flag) {          //操作3
      int i = a * a;    //操作4
    }
  }
}

      flag变量是个标记，用来标识变量a是否已被写入。这里假设有两个线程A和B，A首先执行writer()方法，随后B线程接着执行reader()方法。线程B在执行操作4时，能否看到线程A在操作1对共享变量a的写入呢？

答案是：不一定能看到。

  由于操作1和操作2没有数据依赖关系，编译器和处理器可以对这两个操作重排序；同样，操作3和操作4没有数据依赖关系，编译器和处理器也可以对这两个操作重排序。

操作1和2重排序示意图

在线程A中对操作1和操作2做了重排序。程序执行时，线程A首先写标记变量flag,随后线程B读这个变量。由于条件上判断为真，线程B将读取变量a.此时，变量a还没有被线程A写入，这样在多线程程序的语义被重排序破坏了!. 

操作3和4重排序示意图如下， 在这两个操作中存在控制依赖关系( 即先判断，如判断为真，才会执行 int i=a*a ), 当代码中存在控制依赖性时，会影响指令序列执行的并行度。为此，编译器和处理器会采用猜测（Speculation）执行来克服控制相关性对并行度的影响。以处理器的猜测执行为例，执行线程B的处理器可以提前读取并计算a*a，然后把计算结果临时保存到一个名为重排序缓冲（ReorderBuffer，ROB）的硬件缓存中。当操作3的条件判断为真时，就把该计算结果写入变量i中。

从上图可以看出，猜测执行实质上对操作3和操作4做了重排序。它破坏了多线程程序的语义。 在单线程程序中，对存在控制依赖的操作重排序，不会改变执行结果（这也是as-if-serial语义允许对存在控制依赖的操作做重排序的原因),但在多线程程序中，对存在控制依赖的操作重排序，可能会改变程序的结果. 

5. 顺序一致性

  顺序一致性内存模型是一个理论参考模型，在设计的时候，处理器的内存模型和编程语言的内存模型都会以顺序一致性内存模型作为参照。

5.1 数据竞争与顺序一致性

   java内存模型规范对数据竞争的定义如下:

•     在一个线程中写一个变量，
•     在另一个线程读同一个变量，
•     而且写和读没有通过同步来排序。

当代码中包含数据竞争时，程序的执行往往产生违反直觉的结果。如果一个多线程程序能正确同步，这个程序将是一个没有数据竞争的程序。

  JMM对正确同步的多线程程序的内存一致性做了如下保证:
       如果程序是正确同步的，程序的执行将具有顺序一致性（Sequentially Consistent）——即程序的执行结果与该程序在顺序一致性内存模型中的执行结果相同。这里的同步是指广义上的同步，包括对常用同步原语（synchronized、volatile和final）的正确使用。

5.2 顺序一致性内存模型

这个模型是一个被计算机科学家理想化了的理论参考模型，它为程序员提供了极强的内存可见性保证。顺序一致性内存模型有两大特性。

•   一个线程中的所有操作必须按照程序的顺序来执行。
• （不管程序是否同步）所有线程都只能看到一个单一的操作执行顺序。在顺序一致性内存模型中，每个操作都必须原子执行且立刻对所有线程可见。

顺序一致性内存模型为程序员提供的视图如下图:

    在概念上，顺序一致性模型有一个单一的全局内存，这个内存通过一个左右摆动的开关可以连接到任意一个线程，同时每一个线程必须按照程序的顺序来执行内存读/写操作。从上面的示意图可以看出，在任意时间点最多只能有一个线程可以连接到内存。当多个线程并发执行时，图中的开关装置能把所有线程的所有内存读/写操作串行化（即在顺序一致性模型中，所有操作之间具有全序关系）。

    为了更好进行理解，下面通过两个示意图来对顺序一致性模型的特性做进一步的说明。
   假设有两个线程A和B并发执行。其中A线程有3个操作，它们在程序中的顺序是：A1→A2→A3。      B线程也有3个操作，它们在程序中的顺序是：B1→B2→B3。
    假设这两个线程使用监视器锁来正确同步：A线程的3个操作执行后释放监视器锁，随后B线程获取同一个监视器锁。那么程序在顺序一致性模型中的执行效果将如图所示。

现在我们再假设这两个线程没有做同步，下面是这个未同步程序在顺序一致性模型中的执行示意图，如图所示。

    未同步程序在顺序一致性模型中虽然整体执行顺序是无序的，但所有线程都只能看到一个一致的整体执行顺序。以上图为例，线程A和B看到的执行顺序都是：B1→A1→A2→B2→A3→B3。之所以能得到这个保证是因为顺序一致性内存模型中的每个操作必须立即对任意线程可见。

       但是，在JMM中就没有这个保证。未同步程序在JMM中不但整体的执行顺序是无序的，而且所有线程看到的操作执行顺序也可能不一致。(为什么呢？这与JMM内存模型有关系，线程操作的是本地内存中的数据，再将更新刷新到主内存中). 比如，在当前线程把写过的数据缓存在本地内存中，在没有刷新到主内存之前，这个写操作仅对当前线程可见；从其他线程的角度来观察，会认为这个写操作根本没有被当前线程执行。只有当前线程把本地内存中写过的数据刷新到主内存之后，这个写操作才能对其他线程可见。在这种情况下，当前线程和其他线程看到的操作执行顺序将不一致。

5.3 同步程序的顺序一致性效果

下面，对前面的示例程序Demo用锁来同步，看看正确同步的程序如何具有顺序一致性。

请看下面的示例代码。

class SynchronizedExample {
    int a = 0;
    boolean f?lag = false;
 
    public synchronized void writer() { // 获取锁
        a = 1;
        f?lag = true;
    } // 释放锁
 
    public synchronized void reader() { // 获取锁
        if (f?lag) {
            int i = a;
            ……
        } // 释放锁
    }
}

在上面示例代码中，假设A线程执行writer()方法后，B线程执行reader()方法。这是一个正确同步的多线程程序。根据JMM规范，该程序的执行结果将与该程序在顺序一致性模型中的执行结果相同。下面是该程序在两个内存模型中的执行时序对比图，如图所示。

       顺序一致性模型中，所有操作完全按程序的顺序串行执行。而在JMM中，临界区内的代码可以重排序（但JMM不允许临界区内的代码“逸出”到临界区之外，那样会破坏监视器的语义）。JMM会在退出临界区和进入临界区这两个关键时间点做一些特别处理，使得线程在这两个时间点具有与顺序一致性模型相同的内存视图。虽然线程A在临界区内做了重排序，但由于监视器互斥执行的特性，这里的线程B根本无法“观察”到线程A在临界区内的重排序。这种重排序既提高了执行效率，又没有改变程序的执行结果。

      从这里我们可以看到，JMM在具体实现上的基本方针为：在不改变（正确同步的）程序执行结果的前提下，尽可能地为编译器和处理器的优化打开方便之门。

5.4 未同步程序的执行特性

      对于未同步或未正确同步的多线程程序，JMM只提供最小安全性：线程执行时读取到的值，要么是之前某个线程写入的值，要么是默认值（0，Null，False），JMM保证线程读操作读取到的值不会无中生有（Out Of Thin Air）的冒出来。为了实现最小安全性，JVM在堆上分配对象时，首先会对内存空间进行清零，然后才会在上面分配对象（JVM内部会同步这两个操作）。因此，在已清零的内存空间（Pre-zeroed Memory）分配对象时，域的默认初始化已经完成了。
      JMM不保证未同步程序的执行结果与该程序在顺序一致性模型中的执行结果一致。因为如果想要保证执行结果一致，JMM需要禁止大量的处理器和编译器的优化，这对程序的执行性能会产生很大的影响。而且未同步程序在顺序一致性模型中执行时，整体是无序的，其执行结果往往无法预知。而且，保证未同步程序在这两个模型中的执行结果一致没什么意义。
    未同步程序在JMM中的执行时，整体上是无序的，其执行结果无法预知。未同步程序在两个模型中的执行特性有如下几个差异。

• 顺序一致性模型保证单线程内的操作会按程序的顺序执行，而JMM不保证单线程内的操作会按程序的顺序执行（比如上面正确同步的多线程程序在临界区内的重排序）。
• 顺序一致性模型保证所有线程只能看到一致的操作执行顺序，而JMM不保证所有线程能看到一致的操作执行顺序。
• JMM不保证对64位的long型和double型变量的写操作具有原子性，而顺序一致性模型保证对所有的内存读/写操作都具有原子性。

     第3个差异与处理器总线的工作机制密切相关。在计算机中，数据通过总线在处理器和内存之间传递。每次处理器和内存之间的数据传递都是通过一系列步骤来完成的，这一系列步骤称之为总线事务（Bus Transaction）。总线事务包括读事务（Read Transaction）和写事务（Write Transaction）。读事务从内存传送数据到处理器，写事务从处理器传送数据到内存，每个事务会读/写内存中一个或多个物理上连续的字。这里的关键是，总线会同步试图并发使用总线的事务。在一个处理器执行总线事务期间，总线会禁止其他的处理器和I/O设备执行内存的读/写。下面，让我们通过一个示意图来说明总线的工作机制，如图所示。

      由图可知，假设处理器A，B和C同时向总线发起总线事务，这时总线仲裁（Bus Arbitration）会对竞争做出裁决，这里假设总线在仲裁后判定处理器A在竞争中获胜（总线仲裁会确保所有处理器都能公平的访问内存）。此时处理器A继续它的总线事务，而其他两个处理器则要等待处理器A的总线事务完成后才能再次执行内存访问。假设在处理器A执行总线事务期间（不管这个总线事务是读事务还是写事务），处理器D向总线发起了总线事务，此时处理器D的请求会被总线禁止。
     总线的这些工作机制可以把所有处理器对内存的访问以串行化的方式来执行。在任意时间点，最多只能有一个处理器可以访问内存。这个特性确保了单个总线事务之中的内存读/写操作具有原子性。

     在一些32位的处理器上，如果要求对64位数据的写操作具有原子性，会有比较大的开销。为了照顾这种处理器，Java语言规范鼓励但不强求JVM对64位的long型变量和double型变量的写操作具有原子性。当JVM在这种处理器上运行时，可能会把一个64位long/double型变量的写操作拆分为两个32位的写操作来执行。这两个32位的写操作可能会被分配到不同的总线事务中执行，此时对这个64位变量的写操作将不具有原子性。

     当单个内存操作不具有原子性时，可能会产生意想不到后果。请看示意图:

      如上图所示，假设处理器A写一个long型变量，同时处理器B要读这个long型变量。处理器A中64位的写操作被拆分为两个32位的写操作，且这两个32位的写操作被分配到不同的写事务中执行。同时，处理器B中64位的读操作被分配到单个的读事务中执行。当处理器A和B按上图的时序来执行时，处理器B将看到仅仅被处理器A“写了一半”的无效值。
 
        注意，在JSR -133之前的旧内存模型中，一个64位long/double型变量的读/写操作可以被拆分为两个32位的读/写操作来执行。从JSR -133内存模型开始（即从JDK5开始），仅仅只允许把一个64位long/double型变量的写操作拆分为两个32位的写操作来执行，任意的读操作在JSR -133中都必须具有原子性（即任意读操作必须要在单个读事务中执行）。

  下面用一个程序来测试一下上面的场景: 注意测试环境:  32位虚拟机中. 

public class MultiThreadVolatileLong {
    public static long t=0;
    public static class ChangeT implements Runnable{
        private long to;
        public ChangeT(long to){
            this.to=to;
        }
        @Override
        public void run() {
            while(true){
                MultiThreadVolatileLong.t=to;
                Thread.yield();
            }
        }
    }
    public static class ReadT implements Runnable{
        @Override
        public void run() {
            while(true){
                long tmp=MultiThreadVolatileLong.t;
                if(tmp!=111L && tmp!=-999L && tmp!=333L && tmp!=-444L)
                    System.out.println(tmp);
                Thread.yield();
            }
        }
    }
 
    public static void main(String[] args) {
//		System.out.println(Long.toBinaryString(111L));
//		System.out.println(Long.toBinaryString(-999L));
//		System.out.println(Long.toBinaryString(333L));
//		System.out.println(Long.toBinaryString(-444L));
//		System.out.println(Long.toBinaryString(4294966297L));
//		System.out.println(Long.toBinaryString(-4294967185L));
 
        new Thread(new ChangeT(111L)).start();
        new Thread(new ChangeT(-999L)).start();
        new Thread(new ChangeT(333L)).start();
        new Thread(new ChangeT(-444L)).start();
        new Thread(new ReadT()).start();
    }
}

以上代码使用4个线程对变量t进行赋值，4个线程分别给t赋值为111,-999,333,和-444.在正常情况下，在任意时刻t的取值一定是其中一个。在程序if(tmp!=111L && tmp!=-999L && tmp!=333L && tmp!=-444L)处，读取线程读取变量t的值，并，判断是否为这4个值的一个，如果不是，则输出这个值。在32位的虚拟机上输出结果为: 

4294966297L
-4294967185L

为什么呢?这是因为多线程对long型数据的读写并非原子操作，有可能出现一个线程写了 long型数据的32位，而另一个线程写了long型数据的另外32位。 

解决方案:

将  public static long t=0;  更改为:   public static volatile long t=0;