1. 重排序的含义
1.1 什么是重排序
一般说起重排序，应当有个概念，那就是被排序的对象是什么？答案是指令。而重排序本质上是一种技术，是编译期或者运行时环境为了提高程序执行的性能而对指令进行重新排序的手段。
根据排序指令的主体来看来看，重排序分为两类：编译器优化重排序与处理器重排序。其中处理器重排序可进一步细分为指令集并行级重排序和内存系统重排序。
编译器优化重排序：不改变单线程程序语义前提下，重新安排指令执行顺序。
指令集并行级重排序：指令并行技术可以将多条指令重叠执行，如果不存在数据依赖性，处理器会改变语句对应的机器指令执行顺序。
内存系统重排序：本质上说是由于内存读写的实际执行顺序与处理器预测的指令执行顺序不同，从而引入了异步模式，可以理解为乱序执行。
源代码经过编译器优化重排序，指令集并行级重排序和内存系统重排序后得到最终执行的指令序列。
在单线程的情况，我们可以假定各个指令的执行是唯一而且有序的，指令的顺序对应着源代码书写的顺序，与编译器和处理器无关，这种模型被称作顺序一致性模型。但是在多线程的情况下，我们不能假定指令是按何种顺序执行的，因为无法预测不同线程间指令的运行顺序。从而可能会导致数据不一致的问题，产生错误的执行结果。
1.2 数据依赖性
如果两个操作访问同一个变量，且这两个操作中有一个为写操作，此时这两个操作之间就存在数据依赖性。数据依赖分为下列3种类型：
上面3种情况，只要重排序两个操作的执行顺序，程序的执行结果就会被改变。
前面提到过，编译器和处理器可能会对操作做重排序。编译器和处理器在重排序时，会遵守数据依赖性，编译器和处理器不会改变存在数据依赖关系的两个操作的执行顺序。
这里所说的数据依赖性仅针对单个处理器中执行的指令序列和单个线程中执行的操作，不同处理器之间和不同线程之间的数据依赖性不被编译器和处理器考虑。
2.为什么会有重排序
2.1为什么会有编译器优化重排序
编译器优化重排序：通过调整指令的执行顺序，减少寄存器内容的访问、存储操作次数，做到尽可能的复用寄存器中的内容。
情形一：
假设源码中有三条指令，按照代码书写顺序分别为
将某个值赋给变量A并存放在寄存器中；
与变量A无关的指令但是要占用变量A所在的寄存器；
使用A的值并与第二条指令无关。
没有经过指令重排序的情况：A在第一条指令执行过后被放入寄存器，在第二条指令执行时A不再存在，第三条指令执行时A重新被读入寄存器，而这个过程中，A的值没有发生变化。
经过指令重排序的情况（重排序第一条和第二条指令的位置或者重排序第二条和第三条指令的位置）：指令结束时A存在于寄存器中，接下来可以直接从寄存器中读取A的值，降低了重复读取的开销。
情形二：
线程P执行代码：
x = a; //操作1
b = 2; //操作2
线程Q执行代码：
y = b; //操作3
a = 1; //操作4
假设a,b的初始值均为0，试问在没有编译器优化重排序的情况下，是否会出现x = 1, y = 2的结果？按照顺序一致性模型的概念，这种结果是不会出现的。但是在实际的运行过程中，这种结果是可能出现的，因为发生了编译器优化重排序。
优化重排后指令执行顺序可能为：
线程P执行代码：
b = 2; //操作2
x = a; //操作1
线程Q执行代码：
a = 1; //操作4
y = b; //操作3
依次执行操作2，4，1，3后即会出现x = 1, y = 2的结果。这也从侧面验证了在多线程的情况下不能假定指令是按何种顺序执行的。
2.2为什么会有指令集并行级重排序
一下计算机指令的流水线机制。通常执行一条处理器指令需要耗费若干个CPU时钟周期，在这若干个CPU时钟周期中会使用到若干个计算机硬件，若干个CPU时钟周期结束后，计算机硬件资源被释放，下一条指令才可以使用被上一条指令执行完释放的计算机硬件资源。
为了能够在这若干个CPU时钟周期能够执行多条处理器指令，CPU就需要采用流水线架构进一步优化CPU的性能，使得指令集能够并行执行。
而流水线机制就是将一条处理器指令依照使用到的硬件资源细分，细分后的每个步骤使用不同的硬件资源，当前步骤使用完硬件资源立即释放进入下一步骤使用其他的硬件资源，下一条指令得到硬件资源后重叠执行。
具体的，从指令的执行角度来说一条指令可以分为多个步骤完成(在这里由于指令执行的不同可能会使用到不同的硬件资源)，如下 ：
取指 IF——会使用到PC寄存器和存储器
译码和取寄存器操作数 ID——会使用到指令寄存器组
执行或者有效地址计算 EX——ALU(算术逻辑单元)
存储器访问 MEM——会使用到存储器
写回 WB——会使用到寄存器组
在流水线架构下，CPU指令的执行过程如下：
从上图中可以得到以下信息：当指令1还未执行完成时，第2条指令便利用空闲的硬件开始执行。这样做是有好处的，假设每个步骤花费1个时钟周期，那么如果第2条指令需要等待第1条指令执行完成后再执行的话，则需要等待5个时钟周期，但如果使用流水线技术的话，指令2只需等待1个时钟周期就可以开始执行了，做到了在若干个时钟周期内指令的并行执行，这样就能大大提升CPU的执行性能。
虽然流水线技术可以大大提升CPU的性能，但不幸的是一旦出现流水中断，所有硬件设备将会进入一轮停顿期，当再次弥补中断点可能需要几个周期，这样性能损失也会很大，就好比工厂组装手机的流水线，一旦某个零件组装中断，那么该零件往后的工人都有可能进入一轮或者几轮等待组装零件的过程。因此我们需要尽量阻止指令中断的情况，指令重排序就是其中一种优化中断的手段。
假设程序正在执行以下代码：
a = b + c ;
d = e - f ;
在流水线架构下，CPU指令的执行过程如下：
其中LW指令表示 load；SW 指令表示 store；ADD 指令表示加法；SUB 指令表示减法。
LW R1, b表示把变量b的值加载到寄存器R1中；
LW R2, c 表示把变量c的值加载到寄存器R2中；
ADD R3, R1, R2表示把寄存器R1 、R2的值相加，并存入R3寄存器中；
SW a, R3表示将 R3寄存器的值保持到变量a中；
LW R4, e 表示把变量e的值加载到寄存器R4中；
LW R5, f 表示把变量f的值加载到寄存器R5中；
SUB R6, R4, R5表示把寄存器R4 、R5的值相减，并存入R6寄存器中；
SW d, R6 表示将R6寄存器的值保持到变量d中。
CPU指令的执行过程中，在某些步骤上存在X的标志，X代表中断的含义，也就是只要有X的地方就会导致指令流水线技术停顿，同时也会影响后续指令的执行，可能需要经过1个或几个指令周期才可能恢复正常，那为什么停顿呢？这是因为部分数据还没准备好，如执行ADD指令时，需要使用到前面指令的数据R1，R2，而此时R2的MEM操作没有完成，即未拷贝到存储器中，这样加法计算就无法进行，必须等到MEM操作完成后才能执行，也就因此而停顿了，其他指令也是类似的情况。前面阐述过，停顿会造成CPU性能下降，因此我们应该想办法消除这些停顿，这时就需要使用到指令重排了。过程如下：
如上图，既然ADD指令需要等待，那我们就利用等待的时间做些别的事情，如把LW R4, e 和 LW R5, f 移动到前面执行，毕竟LW R4, e 和 LW R5, f执行并没有数据依赖关系，对他们有数据依赖关系的SUB R6, R4, R5指令在R4, R5加载完成后才执行的，没有影响。这个时候所有的停顿都完美消除了，指令流水线也无需中断了，这样CPU的性能也能带来很好的提升，这就是处理器指令重排序的作用。
2.3为什么会有内存系统重排序(内存乱序)
内存系统重排序实质上是对内存访问指令的重新排序。
对主存的一次访问一般花费硬件的数百次时钟周期。处理器通过缓存(cache)能够从数量级上降低内存延迟(等待对系统内存中存储数据的访问完成时引起的延期)的成本。CPU的主频越来越高，与缓存的交互次数也越来越多。当CPU的计算速度远远超过访问缓存的速度时，会产生cache wait(缓存等待)，过多的cache wait就会造成性能瓶颈。
为了提升性能，处理器的缓存可以重新排列待定内存操作的顺序。也就是说，程序的读写操作不一定会按照它要求处理器的顺序执行。
针对这种情况，多数架构（包括x86架构）采用了一种将cache分片的解决方案，即将一块cache划分成互不关联的多个 slots (逻辑存储单元，又名 Memory Bank 或 Cache Bank)，CPU可以自行选择在多个空闲的bank(idle bank)中进行存取。这种SMP的设计，显著提高了CPU的并行处理能力，也回避了cache访问所造成的性能瓶颈。如下CPU内部结构图：
PS：SMP的全称是"对称多处理"（Symmetrical Multi-Processing）技术，是指在一个计算机上汇集了一组处理器(多CPU),各CPU之间共享内存子系统以及总线结构。
对于Memory Bank的划分，一般来说 Memory Bank 是按cache address(缓存地址)来划分的。比如 偶数地址0×12345000分到 bank 0, 奇数地址0×12345100分到bank 1。这里奇数偶数地址是通过缓存地址映射的cache line决定的，地址0×12345000映射到cache line中是0x0，所以是偶数地址；地址0×12345100映射到cache line中是0x1，所以是奇数地址。
理想的内存访问指令顺序：
1. CPU0 往缓存地址0×12345000 写入一个数字 1，因为地址0×12345000是偶数地址，所以值被写入 bank0；
2. CPU1 读取 bank0 地址0×12345000 的值，即数字1；
3. CPU0 往缓存地址 0×12345100 写入一个数字 2，因为地址 0×12345100是奇数地址，所以值被写入 bank1；
4. CPU1 读取 bank1 地址0×12345100 的值，即数字2。
但是，我们在上面提到缓存等待，当某一个bank忙碌时，CPU可以自行选择在多个空闲的bank(idle bank)中进行存取。此时涉及到内存访问指令的重排序。当前指令A所访问的bank忙碌，而下一条指令B所访问的bank空闲时，缓存就会重新排序指令A和B，首先执行指令B，再执行指令A。
重排序后的内存访问指令顺序：
1. CPU0 准备缓存地址0×12345000 写入一个数字 1，因为地址0×12345000是偶数地址，所以值将被写入 bank0；
2. CPU0 检查 bank0 的可用性，发现 bank0 处于忙碌(busy)状态；
3. CPU0 为了防止 cache wait，发挥最大效能，将内存访问指令重排序;即先执行后面的 bank1 缓存地址0×12345100 数字2的写入请求；
4. CPU0 检查 bank1 可用性，发现bank1处空闲(idle)状态。
5. CPU0 将数字2写入 bank 1 地址0×12345100。
6. CPU1来读取地址0×12345000的值，未读到 数字1，出错。
7. CPU0 继续检查 bank0 的可用性，发现这次bank0 可用了，然后将数字1写入 0×12345000。
8. CPU1 读取地址 0×12345100，读到数字2，正确。
此时通过对内存访问指令的重排，CPU可以获得更快的响应速度；但是涉及到在多线程下指令的重排序，带来了不可预知的问题，如在第三步发生的指令重排序导致了第六步访问缓存的出错。这里再次从侧面验证了在多线程的情况下不能假定指令是按何种顺序执行的。
参考：
《Java并发编程的艺术》
https://blog.csdn.net/javazejian/article/details/72772461
https://ifeve.com/jvm-memory-reordering/