Java内存模型一个经典例子-指令重排序与CPU指令多发射导致执行结果异常

时间:2023-12-14 23:17:26

先上代码:

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier; public class ThreadTest {
int a = 0;
int b = 0;
int x = -1;
int y = -1; public void path1() {
a = 1;
x = b;
} public void path2() {
b = 2;
y = a;
} public boolean test() throws InterruptedException {
a = b = 0;
x = y = -1;
CyclicBarrier cy = new CyclicBarrier(2);
Thread t1 = new Thread(() -> {
try {
cy.await();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (BrokenBarrierException e) {
e.printStackTrace();
}
path1();
});
Thread t2 = new Thread(() -> {
try {
cy.await();
} catch (InterruptedException e) {
e.printStackTrace();
} catch (BrokenBarrierException e) {
e.printStackTrace();
}
path2();
}); t1.start();
t2.start(); t1.join();
t2.join(); // System.out.println("x="+x+", y="+y);
if (x == 0 && y == 0) {
return false;
} else {
return true;
}
} public static void main(String[] args) throws InterruptedException {
for(int i=0; i<=10; i++){
ThreadTest tt = new ThreadTest();
boolean b = tt.test();
if(!b){
System.out.println(i);
}
}
}
}

  

如果不执行,先分析,95%以上的人认为是没有打印结果的;

那就执行一遍代码,相信99.99%的人看到的结果和你分析的结果是一致的。

但当你将循环次数增大到10万,100万,1000万,就可能出现打印结果(当然,CPU较差的出现的几率要小很多)。

那问题出在哪?

我们分析一般会出现的(x,y)组合有:

(0,1)//先执行path1(),再执行path2(),并且里面赋值是按照代码顺序执行

(2,0)//先执行path2(),在执行path1(),并且里面赋值是按照代码顺序执行

(2,1)//四条语句执行先后顺序为:a=1;b=2;x=b;y=a;

其实还有一种组合:

(0,0)//四条语句执行先后顺序为:x=b与y=a由于CPU多发射机制,会先同时执行;然后再执行a=1;b=2。

这种组合开始我也是认为没有可能的。但是我们的技术总监给我们解释出这种组合的真正原因:

目前的高级处理器,为了提高内部逻辑元件的利用率以提高运行速度,通常会采用多指令发射、乱序执行等各种措施。现在普遍使用的一些超标量处理器通常能够在一个指令周期内并发执行多条指令

深入了解原理:

处理器从L1-Cache预取了一批指令后,就会分析找出那些互相没有关联可以并发执行的指令,然后送到几个独立的执行单元进行并发执行。比如下面这样的代码(假定编译器不做优化): 
z = x + y;
p = m + n;
CPU就有可能将这两行无关代码分别送到两个算术单元去同时执行。像Freescale的MPC8541这种嵌入式处理器一个指令周期能够加载4条指令、发射2条指令到流水线、用5个独立的执行单元来并发执行。

通常来说访存指令(由LSU单元执行)所需要的指令周期可能很多(可能要几十甚至上百个周期),而一般的算术指令通常在一个指令周期就搞定。

所以有 可能代码中的访存指令耗费了多个周期完成执行后,其他几个执行单元可能已经把后面有多条逻辑上无关的算术指令都执行完了,这就产生了乱序。

另外访存指令之间也存在乱序的问题。高级的CPU可以根据自己Cache的组织特性,将访存指令重新排序执行。访问一些连续地址的可能会先执行,因为这时候Cache命中率高。

有的还允许访存的Non-blocking,即如果前面一条访存指令因为Cache不命中,造成长延时的存储访问时,后面的访存指令可以先执行以便从Cache取数。

对写指令的访存乱序有可能造成的错误后果,所以处理器通常有专门的机制(通常是做了个缓冲)保证在出现异常或者错误的时候,可以丢弃异常点后面的写指令的结果不做写入。

处理器的分支预测功能也能引起并发执行。处理器的分支预测单元有可能直接把两条分支的指令都预取来一块并发执行掉。

等到分支判断的结果出来以后,再丢弃错误分支的计算结果。这样在很多情况下可以实现0周期跳转。

比如这样的代码(假定编译器不做优化): 
z = x + y; 
if (z > 0) then
    p = m + n;
else
    p = m - n;

看上去如果z不计算出来是无法继续的。但是实际上CPU有可能先把三个加法都同时进行计算,然后根据z=x+y的结果直接挑选正确的p值。

因此,即使是从汇编上看顺序正确的指令,其执行的顺序也是不可预知的。处理器能够保证并发和乱序执行不会得到错误结果,但是如果是对一些硬件寄存器的操作不能允许乱序的话,程序员就必须把这个情况告诉CPU。

告诉的方法就是通过CPU提供的一组同步指令实现,通常在CPU的文档里面有对同步指令的使用说明。

系统函数库里面的内存屏障(rmb/wmb/mb)实际上也是通过这些同步指令实现的。

因此在C编码的时候,只要设置好内存屏障,就能告诉CPU哪些代码是不能乱序的。

编译器的乱序优化受到处理器预取单元的能力限制,处理器每次只能分析一小块指令的并发性,如果指令相隔比较远就无能为力了。

但是从编译器的角度来看,编译器能够对很大一个范围的代码进行分析,能够从更大的范围内分辨出可以并发的指令,并将其尽量靠近排列让处理器更容易预取和并发执行,充分利用处理器的乱序并发功能。

所以现代的高性能编译器在目标码优化上都具备对指令进行乱序优化的能力。并且可以对访存的指令进行进一步的乱序,减少逻辑上不必要的访存,以及尽量提高Cache命中率和CPU的LSU(load/storeunit)的工作效率。

所以在打开编译器优化以后,看到生成的汇编码并不严格按照代码的逻辑顺序是正常的。

和处理器一样,如果想要告诉编译器不要去对某些指令乱序优化,也要通过一些方式来告诉编译器。通常可以通过volatile关键字来抑制(注意,不是禁止)编译器对相关变量的访问优化。

举个例子:

int *p, *q; 
......; 
*p = 1; 
*p = 2; 
*q = *p;

这样,编译器通常会优化掉前面一个对*p的写入(逻辑上冗余),仅对*p写入2。而对*q赋值的时候,编译器认为此时*q的结果就应该是上次*p的值,会优化掉从*p取数的过程,直接把在寄存器中保存的*p的值给*q(PowrPC汇编):

(假设r3=p,r4=q) 
li   r5, 2      // r5赋值2 
stw  r5, 0(r3)  // 把r5写到*p 
stw  r5, 0(r4)  // 把r5写到*q

但是如果为p指针加上了volatile关键字,情况就不同了:

volatile int *p; 
int *q; 
......; 
*p = 1; 
*p = 2; 
*q = *p;

在这种情况下,编译器看见*p是volatile的时候,就会:

不对*p操作生成乱序指令(通常如此,具体请看后面的解释) 每次从*p取数据的时候,一定会进行一次访存操作,哪怕前面不久才取过*p的值放在寄存器里。

不合并对*p的写操作(也只是通常如此,解释见后)
所以这回的结果如下(PowrPC汇编): 
(假设r3=p,r4=q) 
li   r5, 1      // r5赋值1 
stw  r5, 0(r3)  // 把r5写到*p 
li   r5, 2      // r5赋值2 
stw  r5, 0(r3)  // 把r5写到*p 
lwz  r5, 0(r3)  // 从*p取值到r5 
stw  r5, 0(r4)  // 把r5写到*q

这样编译器会在汇编码级别保证指令有序和不优化掉访存操作。通常简单地使用volatile关键字就可以解决编译器的乱序问题,但是这些指令到了处理器执行的时候,仍然可能被乱序。对于处理器乱序执行的避免就需要用到一组内存屏障函数(barrier)了。

重要

绝大多数的编译器,通常不会优化掉对volatile对象的访问,并且通常保持同一个volatile对象的一系列读写操作是有序的(但是不能保证不同的volatile对象之间有序)。

但是,这不是绝对的。因为ANSIC99标准关于对volatile对象访问时编译器是否要绝对保证禁止乱序(reorder)和禁止访问合并(combineaccess)并没有做任何规定!

仅仅是鼓励编译器最好不要去优化对volatile对象的访问,而唯一的强制要求仅仅是要求编译器保证对volatile对象的访问优化不会跨越“sequence point”即可(所谓sequencepoint是指一些诸如外部函数调用、条件或循环跳转等关键点,具体定义请查阅C99标准内的详细说明)。

这就是说,如果一个编译器在两个sequence point之间像对待普通变量一样去优化volatile变量,也是完全符合C99标准的!比如:

volatile int a;
if (...) { ... }  // sequence point
a = 1;
a = 2;
a = 3;
printk("...");    // sequence point

在两个sequence point之间,要是有编译器对a的赋值操作合并(即仅写入3)或者乱序(如写1和写2对调),都是完全符合C99标准的。

所以,我们在使用的时候,不能指望用了volatile以后绝对能生成有序的完整的汇编码,即不要指望volatile来保证访存有序。

实质上volatile最大的作用主要还是在保证每次使用从内存中取值,而并不能保证编译器不做其他任何优化(毕竟volatile从字面上看意思是“易变”而不是“有序”。编译器只保证对volatile对象即时更新但不保证访问有序也不是说不过去的)。

从另一个角度看,即使是编译器生成的汇编码有序,处理器也不一定能保证有序。就算编译器生成了有序的汇编码,到了处理器那里也拿不准是不是会按照代码顺序执行。

所以就算编译器保证有序了,程序员也还是要往代码里面加内存屏障才能保证绝对访存有序,这倒不如编译器干脆不管算了,因为内存屏障本身就是一个sequence point,加入后已经能够保证编译器也有序。

因此,对于切实是需要保障访存顺序的代码,就算当前使用的编译器能够编译出有序的目标码来,我们也还是必须通过设置内存屏障的方式来保证有序,否则都是不严谨,有隐患的。

Barrier屏障函数

Barrier函数可以在代码中设置屏障,这个屏障可以阻挡编译器的优化,也可以阻挡处理器的优化。

对于编译器来说,设置任何一个屏障都可以保证:

编译器的乱序优化不会跨越屏障,即屏障前后的代码不会乱序;

在屏障后所有对变量或者地址的操作,都会重新从内存中取值(相当于刷新寄存器中的变量副本)。

而对于处理器来说,根据不同的屏障有不同的表现(以下仅仅列举3种最简单的屏障):

读屏障rmb() 
处理器对读屏障前后的取数指令(LOAD)能保证有序,但是不一定能保证其他算术指令或者是写指令的有序。对于读指令的执行完成时间也不能保证,即它不能保证在屏障之前的读指令一定都执行完成,只能保证屏障之前的读指令一定能在屏障之后的读指令之前完成。

写屏障wmb() 
处理器对屏障前后的写指令(STORE)能保证有序,但是不一定能保证其他算术指令或者是读指令的有序。对于写指令的执行完成时间也不能保证,即它不能保证在屏障之前的写指令一定都执行完成,只能保证屏障之前的写指令一定能在屏障之后的写指令之前完成。

通用内存屏障mb() 
处理器保障只有屏障之前的访存操作(包括读写)都完成以后才会执行屏障之后的访存操作。即可以保障读写之间的有序(但是同样无法保证指令完成的时间)。这种屏障对处理器的执行单元效率产生的负面影响要比单纯用读屏障或者写屏障来的大。比如对于PowerPC来说这种通用屏障通常是使用sync指令

实现的,在这种情况下处理器会丢弃所有预取的指令并清空流水线。所以频繁使用内存屏障会降低处理器执行单元的效率。

对于驱动开发者来说,一些对设备寄存器的操作,通常是必须保证有序的。在绝大部分情况下,一般都是写操作。对于有序的写操作,必须设置写屏障(wmb): 
例:在驱动中使用写屏障 
/* Mask out everything */ 
im_intctl->ic_simrh = 0x00000000; 
im_intctl->ic_simrl = 0x00000000;wmb();  /* Ack everything */ 
im_intctl->ic_sipnrh = 0xffffffff;
im_intctl->ic_sipnrl = 0xffffffff;

这是一个对中断控制器操作的例子。在设置两个mask寄存器的值的时候,这两个写操作没有顺序要求,因此可以不加屏障。但是对ack寄存器的设置必须在mask寄存器完成设置以后,所以在中间要加入写屏障wmb()以保证对两组寄存器的写有序。 
同样的,对于一系列的只读操作,也可以简单使用rmb()来保证有序。 
注意 
任何一个rmb()或者wmb()都是可以被替换成mb()的。但是因为上面提到过的mb()的效率问题,所以应该只有在同时需要读屏障和写屏障的时候,才建议使用mb()。否则应该根据实际情况来选择合适的屏障。当然,在设备初始化的时候,即使是使用mb()也不会对性能带来什么影响,因为设备一般只会初始化一次。但是在发生很频繁的设备操作(比如网口的收发帧中断等)时,应该考虑到mb()对性能的影响。 
如果驱动不仅仅需要在单纯的读指令或者写指令之间有序,还需要保证读写指令之间有序的时候,就需要设置mb()屏障了。下面将演示一个这样的例子: 
例:使用mb()屏障保证读写有序 
我们假设有一个设备,在读取设备信息时需要依次对REG1~3这三个寄存器进行写入操作(写入设备读取命令),然后才能依次读取REG4和REG5取得设备返回的信息。
 

REG1 = a; 
wmb();  // 保证REG1和REG2的写有序
REG2 = b; 
wmb();  // 保证REG2和REG3的写有序
REG3 = c;
mb();   // 保证在对设备读之前,前面的配置操作都完成(读写之间有序)
*d = REG4; 
rmb();  // 保证REG4和REG5的读有序
*e = REG5;
mb();   // 保证与未来对设备的操作有序 
return;

1, 对于REG1~3的写入,可以通过设置写屏障来保证有序;

2. 在进行REG4和5的读取之前,因为得保证前面的寄存器写操作都执行完才能读,所以需要设置一个内存屏障mb()来保证前面对寄存器的写都完成,以保障读写指令之间的有序;

3. 后面两个读操作之间就可以通过设置读屏障来保证有序了;

4. 最后通常在从设备操作函数返回之前,我们一般需要保证对设备的操作都执行完毕了。这样下次对设备进行操作的时候我们可以保证设备已经完成了上次操作,避免反复调用设备操作函数带来的函数间的乱序问题。所以在最后设置一个内存屏障mb(),保障和未来对设备的其他访问有序。

原理部分转自:https://blog.csdn.net/silentpebble/article/details/19190737