深入理解Java内存模型(二)——重排序

本文属于作者原创,原文发表于InfoQ:http://www.infoq.com/cn/articles/java-memory-model-2

数据依赖性

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

名称 代码示例 说明
写后读 a = 1;b = a; 写一个变量之后,再读这个位置。
写后写 a = 1;a = 2; 写一个变量之后,再写这个变量。
读后写 a = b;b = 1; 读一个变量之后,再写这个变量。

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

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

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

as-if-serial语义

as-if-serial语义的意思指:不管怎么重排序(编译器和处理器为了提高并行度),(单线程)程序的执行结果不能被改变。编译器,runtime 和处理器都必须遵守as-if-serial语义。

为了遵守as-if-serial语义,编译器和处理器不会对存在数据依赖关系的操作做重排序,因为这种重排序会改变执行结果。但是,如果操作之间不存在数据依赖关系,这些操作可能被编译器和处理器重排序。为了具体说明,请看下面计算圆面积的代码示例:

double pi  = 3.14;    //A
double r   = 1.0;     //B
double area = pi * r * r; //C

上面三个操作的数据依赖关系如下图所示:

如上图所示,A和C之间存在数据依赖关系,同时B和C之间也存在数据依赖关系。因此在最终执行的指令序列中,C不能被重排序到A和B的前面(C排到A和B的前面,程序的结果将会被改变)。但A和B之间没有数据依赖关系,编译器和处理器可以重排序A和B之间的执行顺序。下图是该程序的两种执行顺序:

as-if-serial语义把单线程程序保护了起来,遵守as-if-serial语义的编译器,runtime 和处理器共同为编写单线程程序的程序员创建了一个幻觉:单线程程序是按程序的顺序来执行的。as-if-serial语义使单线程程序员无需担心重排序会干扰他们,也无需担心内存可见性问题。

程序顺序规则

根据happens- before的程序顺序规则,上面计算圆的面积的示例代码存在三个happens- before关系:

  1. A happens- before B;
  2. B happens- before C;
  3. A happens- before C;

这里的第3个happens- before关系,是根据happens- before的传递性推导出来的。

这里A happens- before B,但实际执行时B却可以排在A之前执行(看上面的重排序后的执行顺序)。在第一章提到过,如果A happens- before B,JMM并不要求A一定要在B之前执行。JMM仅仅要求前一个操作(执行的结果)对后一个操作可见,且前一个操作按顺序排在第二个操作之前。这里操作A的执行结果不需要对操作B可见;而且重排序操作A和操作B后的执行结果,与操作A和操作B按happens- before顺序执行的结果一致。在这种情况下,JMM会认为这种重排序并不非法(not illegal),JMM允许这种重排序。

在计算机中,软件技术和硬件技术有一个共同的目标:在不改变程序执行结果的前提下,尽可能的开发并行度。编译器和处理器遵从这一目标,从happens- before的定义我们可以看出,JMM同样遵从这一目标。

重排序对多线程的影响

现在让我们来看看,重排序是否会改变多线程程序的执行结果。请看下面的示例代码:

class ReorderExample {
int a = 0;
boolean flag = false;

public void writer() {
    a = 1;                   //1
    flag = true;             //2
}

Public void reader() {
    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重排序时,可能会产生什么效果?请看下面的程序执行时序图:

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

※注:本文统一用红色的虚箭线表示错误的读操作,用绿色的虚箭线表示正确的读操作。

下面再让我们看看,当操作3和操作4重排序时会产生什么效果(借助这个重排序,可以顺便说明控制依赖性)。下面是操作3和操作4重排序后,程序的执行时序图:

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

从图中我们可以看出,猜测执行实质上对操作3和4做了重排序。重排序在这里破坏了多线程程序的语义!

在单线程程序中,对存在控制依赖的操作重排序,不会改变执行结果(这也是as-if-serial语义允许对存在控制依赖的操作做重排序的原因);但在多线程程序中,对存在控制依赖的操作重排序,可能会改变程序的执行结果。

参考文献

  1. Computer Architecture: A Quantitative Approach, 4th Edition
  2. Concurrent Programming on Windows
  3. Concurrent Programming in Java™: Design Principles and Pattern
  4. JSR-133: Java Memory Model and Thread Specification
  5. JSR 133 (Java Memory Model) FAQ

关于作者

程晓明,Java软件工程师,国家认证的系统分析师、信息项目管理师。专注于并发编程。个人邮箱:asst2003@163.com


原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 深入理解Java内存模型(二)——重排序


程晓明

程晓明,Java软件工程师,专注于并发编程,就职于富士通南大。个人邮箱:asst2003@163.com。
FavoriteLoading添加本文到我的收藏
  • Trackback 关闭
  • 评论 (15)
    • johnson
    • 2013/01/28 2:04下午

    整理的非常好,多谢。

  1. 很好。例子很清楚。

  2. 编译器和处理器在重排序时,会遵守数据依赖性,编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序。

  3. 通俗易懂。

  4. 你好,我有个问题,这里。
    if (flag) { //3
    int i = a * a; //4

    这两个步骤的重排序问题,在我看来3和4是有依赖性的…因为有if的语境在,3和4如果可以重排序,那不是数据的结果被破坏了么? 求指导

  5. 骚瑞,没看到下边还有话。。。。。

    • vavio99
    • 2013/03/20 7:57下午

    “同样,操作3和操作4没有数据依赖关系” 和 “操作3和操作4存在控制依赖关系” 感觉有点矛盾,虽然作者的表达的意图我理解了…4之所以会比3提前执行,是因为CPU的”分支预判” (FROM CSAPP)

      • 匿名
      • 2013/03/21 10:34下午

      数据依赖关系和控制依赖关系,是两个不同的概念。
      在ReorderExample 中,3和4没有数据依赖关系;但3和4之间存在控制依赖关系。
      它们之间并不矛盾。

  6. 如果存在重排序的可能,例子中应该能看到i=0的结果,但我写的测试类执行100w次,也没有看到这个结果,请教高人解惑!
    以下是我的测试代码:

    public class ReorderExample {
    
    	int a = 0;
    	boolean flag = false;
    
    	public void writer() {
    	    a = 1;                //1
    	    flag = true;          //2
    	}
    	
    	public int reader() {
    	    while (true) {        
    	    	if (flag) {		//3
    	    		int i =  a * a;	  //4
    		        return i;
    	    	}
    	    }
    	}
    	
    	/**
    	 * @param args
    	 * @throws InterruptedException 
    	 */
    	public static void main(String[] args) throws InterruptedException {
    		final ConcurrentMap counter = new ConcurrentHashMap();
    		
    		for (int i = 0; i < Integer.parseInt(args[0]); i++) {
    			final ReorderExample re = new ReorderExample();
    			
    			Thread readThread = new Thread(new Runnable() {
    				@Override
    				public void run() {
    					int result = re.reader();
    					Integer count = counter.get(result);
    					if (count == null) {
    						count = 0;
    					}
    					counter.put(result, count.intValue() + 1);
    				}
    			});
    			readThread.start();
    			re.writer();
    			readThread.join();
    		}
    		
    		for (int result : counter.keySet()) {
    			System.out.println("" + result + ", count=" + counter.get(result));
    		}
    		
    	}
    
    }
    
    • seagod
    • 2013/12/28 1:12上午

    写得很好,表达的清晰易懂,学习了

  7. 问一个问题啊:编译器重排序的目的是什么,重排序后对执行效率貌似也没影响啊,求指导

    • 程晓明
    • 2014/06/06 11:53下午

    编译器采取的策略包括:
    执行更少的指令,优化寄存器的访问,将相关内存的访问尽可能的放在接近的位置上(为了获得空间局部性),尽可能少的访问内存等等。
    执行这些优化时,编译器可能会对操作做重排序。
    这些重排序的目的是:在不改变单线程内的执行结果的前提下,提高执行效率。

    • 大巴气
    • 2015/02/16 2:35下午

    好文章,写的非常好。

您必须 登陆 后才能发表评论

return top