24 冒险和预测（三）：CPU里的“线程池”
过去两讲，我为你讲解了通过增加资源、停顿等待以及主动转发数据的方式，来解决结构冒险和数据冒险问题。对于结构冒险，由于限制来自于同一时钟周期不同的指令，要访问相同的硬件资源，解决方案是增加资源。对于数据冒险，由于限制来自于数据之间的各种依赖，我们可以提前把数据转发到下一个指令。
但是即便综合运用这三种技术，我们仍然会遇到不得不停下整个流水线，等待前面的指令完成的情况，也就是采用流水线停顿的解决方案。比如说，上一讲里最后给你的例子，即使我们进行了操作数前推，因为第二条加法指令依赖于第一条指令从内存中获取的数据，我们还是要插入一次NOP的操作。
那这个时候你就会想了，那我们能不能让后面没有数据依赖的指令，在前面指令停顿的时候先执行呢？
答案当然是可以的。毕竟，流水线停顿的时候，对应的电路闲着也是闲着。那我们完全可以先完成后面指令的执行阶段。
填上空闲的NOP：上菜的顺序不必是点菜的顺序
之前我为你讲解的，无论是流水线停顿，还是操作数前推，归根到底，只要前面指令的特定阶段还没有执行完成，后面的指令就会被“阻塞”住。
但是这个“阻塞”很多时候是没有必要的。因为尽管你的代码生成的指令是顺序的，但是如果后面的指令不需要依赖前面指令的执行结果，完全可以不必等待前面的指令运算完成。
比如说，下面这三行代码。
计算里面的 x ，却要等待 a 和 d 都计算完成，实在没啥必要。所以我们完全可以在 d 的计算等待 a 的计算的过程中，先把 x 的结果给算出来。
在流水线里，后面的指令不依赖前面的指令，那就不用等待前面的指令执行，它完全可以先执行。
可以看到，因为第三条指令并不依赖于前两条指令的计算结果，所以在第二条指令等待第一条指令的访存和写回阶段的时候，第三条指令就已经执行完成了。
这就好比你开了一家餐馆，顾客会排队来点菜。餐馆的厨房里会有洗菜、切菜、炒菜、上菜这样的各个步骤。后厨也是按照点菜的顺序开始做菜的。但是不同的菜需要花费的时间和工序可能都有差别。有些菜做起来特别麻烦，特别慢。比如做一道佛跳墙有好几道工序。我们没有必要非要等先点的佛跳墙上菜了，再开始做后面的炒鸡蛋。只要有厨子空出来了，就可以先动手做前面的简单菜，先给客户端上去。
这样的解决方案，在计算机组成里面，被称为乱序执行（Out-of-Order Execution，OoOE）。乱序执行，最早来自于著名的IBM 360。相信你一定听说过《人月神话》这本软件工程届的经典著作，它讲的就是IBM 360开发过程中的“人生体会”。而IBM 360困难的开发过程，也少不了第一次引入乱序执行这个新的CPU技术。
CPU里的“线程池”：理解乱序执行
那么，我们的CPU怎样才能实现乱序执行呢？是不是像玩俄罗斯方块一样，把后面的指令，找一个前面的坑填进去就行了？事情并没有这么简单。其实，从今天软件开发的维度来思考，乱序执行好像是在指令的执行阶段，引入了一个“线程池”。我们下面就来看一看，在CPU里，乱序执行的过程究竟是怎样的。
使用乱序执行技术后，CPU里的流水线就和我之前给你看的5级流水线不太一样了。我们一起来看一看下面这张图。
1.在取指令和指令译码的时候，乱序执行的CPU和其他使用流水线架构的CPU是一样的。它会一级一级顺序地进行取指令和指令译码的工作。
2.在指令译码完成之后，就不一样了。CPU不会直接进行指令执行，而是进行一次指令分发，把指令发到一个叫作保留站（Reservation Stations）的地方。顾名思义，这个保留站，就像一个火车站一样。发送到车站的指令，就像是一列列的火车。
3.这些指令不会立刻执行，而要等待它们所依赖的数据，传递给它们之后才会执行。这就好像一列列的火车都要等到乘客来齐了才能出发。
4.一旦指令依赖的数据来齐了，指令就可以交到后面的功能单元（Function Unit，FU），其实就是ALU，去执行了。我们有很多功能单元可以并行运行，但是不同的功能单元能够支持执行的指令并不相同。就和我们的铁轨一样，有些从上海北上，可以到北京和哈尔滨；有些是南下的，可以到广州和深圳。
5.指令执行的阶段完成之后，我们并不能立刻把结果写回到寄存器里面去，而是把结果再存放到一个叫作重排序缓冲区（Re-Order Buffer，ROB）的地方。
6.在重排序缓冲区里，我们的CPU会按照取指令的顺序，对指令的计算结果重新排序。只有排在前面的指令都已经完成了，才会提交指令，完成整个指令的运算结果。
7.实际的指令的计算结果数据，并不是直接写到内存或者高速缓存里，而是先写入存储缓冲区（Store Buffer面，最终才会写入到高速缓存和内存里。
可以看到，在乱序执行的情况下，只有CPU内部指令的执行层面，可能是“乱序”的。只要我们能在指令的译码阶段正确地分析出指令之间的数据依赖关系，这个“乱序”就只会在互相没有影响的指令之间发生。
即便指令的执行过程中是乱序的，我们在最终指令的计算结果写入到寄存器和内存之前，依然会进行一次排序，以确保所有指令在外部看来仍然是有序完成的。
有了乱序执行，我们重新去执行上面的3行代码。
里面的 d 依赖于 a 的计算结果，不会在 a 的计算完成之前执行。但是我们的CPU并不会闲着，因为 x = y * z 的指令同样会被分发到保留站里。因为 x 所依赖的 y 和 z 的数据是准备好的， 这里的乘法运算不会等待计算 d，而会先去计算 x 的值。
如果我们只有一个FU能够计算乘法，那么这个FU并不会因为 d 要等待 a 的计算结果，而被闲置，而是会先被拿去计算 x。
在 x 计算完成之后，d 也等来了 a 的计算结果。这个时候，我们的FU就会去计算出 d 的结果。然后在重排序缓冲区里，把对应的计算结果的提交顺序，仍然设置成 a -> d -> x，而计算完成的顺序是 x -> a -> d。
在这整个过程中，整个计算乘法的FU都没有闲置，这也意味着我们的CPU的吞吐率最大化了。
整个乱序执行技术，就好像在指令的执行阶段提供一个“线程池”。指令不再是顺序执行的，而是根据池里所拥有的资源，以及各个任务是否可以进行执行，进行动态调度。在执行完成之后，又重新把结果在一个队列里面，按照指令的分发顺序重新排序。即使内部是“乱序”的，但是在外部看起来，仍然是井井有条地顺序执行。
乱序执行，极大地提高了CPU的运行效率。核心原因是，现代CPU的运行速度比访问主内存的速度要快很多。如果完全采用顺序执行的方式，很多时间都会浪费在前面指令等待获取内存数据的时间里。CPU不得不加入NOP操作进行空转。而现代CPU的流水线级数也已经相对比较深了，到达了14级。这也意味着，同一个时钟周期内并行执行的指令数是很多的。
而乱序执行，以及我们后面要讲的高速缓存，弥补了CPU和内存之间的性能差异。同样，也充分利用了较深的流水行带来的并发性，使得我们可以充分利用CPU的性能。
总结延伸
好了，总结一下。这一讲里，我为你介绍了乱序执行，这个解决流水线阻塞的技术方案。因为数据的依赖关系和指令先后执行的顺序问题，很多时候，流水线不得不“阻塞”在特定的指令上。即使后续别的指令，并不依赖正在执行的指令和阻塞的指令，也不能继续执行。
而乱序执行，则是在指令执行的阶段通过一个类似线程池的保留站，让系统自己去动态调度先执行哪些指令。这个动态调度巧妙地解决了流水线阻塞的问题。指令执行的先后顺序，不再和它们在程序中的顺序有关。我们只要保证不破坏数据依赖就好了。CPU只要等到在指令结果的最终提交的阶段，再通过重排序的方式，确保指令“实际上”是顺序执行的。
推荐阅读
想要更深入地了解CPU的乱序执行的知识，我们就不能局限于组成原理，而要深入到体系结构中去了。你可以读一下《计算机体系结构：量化研究方法》的3.4和3.5章节。
想要了解乱序执行为什么可行，你可以看看Wikipedia上，乱序执行所依赖的Tomasulo算法。这个算法，也是在IBM 360时代引入的。
课后思考
在现代Intel的CPU的乱序执行的过程中，只有指令的执行阶段是乱序的，后面的内存访问和数据写回阶段都仍然是顺序的。这种保障内存数据访问顺序的模型，叫作强内存模型（Strong Memory Model）。你能想一想，我们为什么要保障内存访问的顺序呢？在前后执行的指令没有相关数据依赖的情况下，为什么我们仍然要求这个顺序呢？
欢迎留言和我分享你的疑惑和见解。你也可以把今天的内容，分享给你的朋友，和他一起学习和进步。
- 88591 👍（55） 💬（2）
应该是数据一致性问题，多核访问相同的内存。但是有自己的缓存，寄存器。
2019-12-09 - 许先森 👍（0） 💬（1）
我的思考是上面的例子只是简单的计算，会不会是后面有一些逻辑运算对a和x的结果读取有顺序要求，如果不保证先正确读取a再正确读取到x的话会对逻辑运算有影响。
2020-01-14 - 许先森 👍（0） 💬（1）
“3. 这些指令不会立刻执行，而要等待它们所依赖的数据，传递给它们之后才会执行。这就好像一列列的火车都要等到乘客来齐了才能出发。” 这里有个问题啊，所有指令都是在保留站中等待自己依赖的数据，那如果依赖的是上一条指令的结果呢？
2020-01-14 - 程序员花卷 👍（0） 💬（2）
我觉得如果不保证它们的执行顺序的话，那最终得到的结果也可能不是我们期望的结果
2019-12-18 - Mango 👍（0） 💬（1）
思考题，感觉是内存屏障，防止多核CPU操作共享内存时出现数据冒险问题。
2019-08-28 - 焰火 👍（26） 💬（3）
数据从cpu --> 寄存器 --> 内存， 数据从CPU到内存中间有个寄存器，寄存器和内存数据交换应该也是整页交换，如果不顺序写回寄存器的话，很有可能在寄存器页边界的时候，到内存发生时间差，导致后面寄存器再重新取内存的时候发生数据错误，之前数据不依赖，不保证后面数据不依赖。所以还是顺序写回比较安全。
2019-07-19 - xindoo 👍（10） 💬（2）
我觉得强内存模型是为了保证不同指令对同一内存地址的读写正确性，不同指令的执行不仅仅有寄存器数据依赖，还会有内存数据依赖。
2019-06-19 - zhengfan 👍（4） 💬（0）
徐老师您好。我有两个问题如下： 1. 乱序执行是否在debug模式下不启用？还是说reorder输出后，已经满足了单步执行下的顺序？ 2. 乱序执行这样的优化是否对编码过程透明？换言之，编码过程中有意识的遵从乱序原则，是否会对运行效率有影响？个人感觉是会有影响的，至少在reserve和reorder两个阶段降低了排序难度。您认为呢？
2020-04-22 - 有米 👍（4） 💬（1）
老师您好！乱序执行就是我们平时说的指令重排么？
2020-03-10 - sun 👍（2） 💬（0）
比如 两个线程分别在两个核中执行fun1（）{int i1=1; int i2=i1+1; boolean b = true;）和fun2（）{if(b) {System.out.println()i2}},假设 协会阶段不是顺序的，b=true被先写回缓存中，此时因为内存屏障，同步到主存中b位true，i2为0，另一个线程输出0，也就是说如果不保证最后的写回阶段有序，内存屏障也会失效？？ 请问老师是这样吗？
2020-04-01 - cc 👍（2） 💬（4）
老师，有一点没想明白。五级流水线，取指令-译指令-执行-访存-写回。这里的访存是干什么的？能否具体举例讲一讲？我理解访存是把数据读入寄存器。那这样的话，访存应该先于执行才对。感谢答疑
2019-06-20 - geraltlaush 👍（2） 💬（2）
搜了下资料，假如有两个阶段，之间没有数据依赖，第一个阶段判断变量a是否为true，再执行，否则退出。第二个阶段直接把a置为false，如果乱序执行，第二个阶段先执行影响业务逻辑，第一个阶段本来可以执行的，现在直接退出了
2019-06-19 - 一頭蠻牛 👍（1） 💬（0）
老师 请问保留站靠什么“保留”数据 它又是什么 cpu缓存，内存，还是寄存器
2022-06-28 - Mamba 👍（0） 💬（0）
最重要的原因是确保程序的可预测性和正确性。保障内存访问顺序能够确保程序员编写的代码在内存访问方面的行为符合预期，这是多线程编程和同步机制正确工作的基础，也是维护系统稳定性和可靠性的关键。
2024-08-24 - Geek_88604f 👍（0） 💬（0）
这里确实是为了保障数据一致性而强制做一次数据同步。但并不是每次都是必须的，这里面可能还有优化空间，就是按需同步，当后面的数据依赖前面的数据时才做同步
2023-11-07