編譯器的亂序策略

很多現(xiàn)代高級(jí)語(yǔ)言多提供了多線程并發(fā)技術(shù)，今天服務(wù)器CPU基本上都是多核架構(gòu)，在Java中，JVM能夠根據(jù)處理器特性（CPU多級(jí)緩存系統(tǒng)、多核處理器等）適當(dāng)對(duì)機(jī)器指令進(jìn)行重排序，最大限度發(fā)揮機(jī)器性能。Java中的指令重排有兩次，第一次發(fā)生在將字節(jié)碼編譯成機(jī)器碼的階段，第二次發(fā)生在CPU執(zhí)行的時(shí)候，也會(huì)適當(dāng)對(duì)指令進(jìn)行重排。

寫這篇文章的目的，是想明確下cpu指令亂序這件事。只要是熟悉計(jì)算機(jī)底層系統(tǒng)的同學(xué)就會(huì)知道，程序里面的每行代碼的執(zhí)行順序，有可能會(huì)被編譯器和cpu根據(jù)某種策略，給打亂掉，目的是為了性能的提升，讓指令的執(zhí)行能夠盡可能的并行起來(lái)。

知道指令的亂序策略很重要，原因是這樣我們就能夠通過(guò)barrier（內(nèi)存屏障）等指令，在正確的位置告訴cpu或者是編譯器，這里我可以接受亂序，那里我不能接受亂序等等。從而，能夠在保證代碼正確性的前提下，最大限度地發(fā)揮機(jī)器的性能。

10多年前的程序員對(duì)處理器亂序執(zhí)行和內(nèi)存屏障應(yīng)該是很熟悉的,但隨著計(jì)算機(jī)技術(shù)突飛猛進(jìn)的發(fā)展,我們離底層原理越來(lái)越遠(yuǎn),這并不是一件壞事,但在有些情況下了解一些底層原理有助于我們更好的工作,比如現(xiàn)代高級(jí)語(yǔ)言多提供了多線程并發(fā)技術(shù),如果不深入下來(lái),那么有些由多線程造成問(wèn)題就很難排查和理解。

前言

這里我不打算討論編譯器的亂序策略，這里討論的指令亂序，含義稍廣些，包括在多核上分別執(zhí)行的指令間，在時(shí)間維度上的亂序。

如果在多核cpu層面考慮亂序執(zhí)行的話，我們要來(lái)梳理清楚以下幾個(gè)概念：單核和多核，亂序執(zhí)行和順序提交，store buffer和invalid queue。最后會(huì)對(duì)x86和arm/power架構(gòu)的異同，做一個(gè)總結(jié)。

單核 vs 多核

從多核的視角上來(lái)說(shuō)，是存在著亂序的可能的。比如，假設(shè)存在變量x = 0，cpu0上執(zhí)行寫入W0(x, 1)，對(duì)x寫入1。接著在cpu1上，執(zhí)行讀取R1(x, 0)，得到x = 0，這在x86和arm/power的cpu上都是可能出現(xiàn)的。原因是x86上cpu核和cache以及內(nèi)存之間，存在著store buffer，當(dāng)W0(x, 1)執(zhí)行成功后，修改只存在于store buffer中，并未寫到cache以及內(nèi)存上，因此cpu1讀取不到最新的x值。對(duì)于arm/power來(lái)說(shuō)，同樣也有store buffer，而且還可能會(huì)有invalid queue，導(dǎo)致cpu1讀不到最新的x值。

對(duì)于沒(méi)有invalid queue的x86系列cpu來(lái)說(shuō)，當(dāng)修改從store buffer刷入cache時(shí)，就能夠保證在其他核上能夠讀到最新的修改。但是，對(duì)于存在invalid queue的cpu來(lái)說(shuō)，則不一定。

為了能夠保證多核之間的修改的可見(jiàn)性，我們?cè)趯懗绦虻臅r(shí)候需要加上內(nèi)存屏障，例如x86上的mfence指令。

亂序執(zhí)行 vs 順序提交

我們知道，在cpu中為了能夠讓指令的執(zhí)行盡可能地并行起來(lái)，從而發(fā)明了流水線技術(shù)。但是如果兩條指令的前后存在依賴關(guān)系，比如數(shù)據(jù)依賴，控制依賴等，此時(shí)后一條語(yǔ)句就必需等到前一條指令完成后，才能開(kāi)始。

cpu為了提高流水線的運(yùn)行效率，會(huì)做出比如：

1)對(duì)無(wú)依賴的前后指令做適當(dāng)?shù)膩y序和調(diào)度；

2)對(duì)控制依賴的指令做分支預(yù)測(cè)；

3)對(duì)讀取內(nèi)存等的耗時(shí)操作，做提前預(yù)讀；

等等。以上總總，都會(huì)導(dǎo)致指令亂序的可能。

但是對(duì)于x86的cpu來(lái)說(shuō)，在單核視角上，其實(shí)它做出了Sequential consistency[1]的一致性保障。Sequential consistency的在wiki上的定義如下：

"... the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program."

也就是說(shuō)，要滿足Sequential consistency，必需保障每個(gè)處理器的指令執(zhí)行順序必需和程序給出的順序一致。奇怪吧？這不就和我剛才說(shuō)的指令亂序優(yōu)化矛盾了嘛？其實(shí)并不矛盾，指令在cpu核內(nèi)部確實(shí)是亂序執(zhí)行和調(diào)度的，但是它們對(duì)外表現(xiàn)卻是順序提交的。

如果把ISA寄存器（如EAX，EBX等）和store buffer，作為cpu對(duì)外的接口的話，cpu只需要把內(nèi)部真實(shí)的物理寄存器按照指令的執(zhí)行順序，順序映射到ISA寄存器上，也就是cpu只要將結(jié)果順序地提交到ISA寄存器，就可以保證Sequential consistency。

當(dāng)然，以上是對(duì)x86架構(gòu)的cpu來(lái)說(shuō)的，ARM/Power架構(gòu)的cpu在單核上的一致性保證要弱一些，無(wú)需保證Sequential consistency，因此也不需要順序提交，只需保證控制依賴，數(shù)據(jù)依賴，地址依賴等指令的順序即可。要想在這些弱一致性模型cpu下保證無(wú)關(guān)指令間的提交順序，需要使用barrier指令。

Store Buffer & Invalid Queue

store buffer存在于cpu核與cache之間，對(duì)于x86架構(gòu)來(lái)說(shuō)，store buffer是FIFO，因此不會(huì)存在亂序，寫入順序就是刷入cache的順序。但是對(duì)于ARM/Power架構(gòu)來(lái)說(shuō)，store buffer并未保證FIFO，因此先寫入store buffer的數(shù)據(jù)，是有可能比后寫入store buffer的數(shù)據(jù)晚刷入cache的。從這點(diǎn)上來(lái)說(shuō)，store buffer的存在會(huì)讓ARM/Power架構(gòu)出現(xiàn)亂序的可能。store barrier存在的意義就是將store buffer中的數(shù)據(jù)，刷入cache。

在某些cpu中，存在invalid queue。invalid queue用于緩存cache line的失效消息，也就是說(shuō)，當(dāng)cpu0寫入W0(x, 1)，并從store buffer將修改刷入cache，此時(shí)cpu1讀取R1(x, 0)仍是允許的。因?yàn)槭筩ache line失效的消息被緩沖在了invalid queue中，還未被應(yīng)用到cache line上。這也是一種會(huì)使得指令亂序的可能。load barrier存在的意義就是將invalid queue緩沖刷新。

X86 vs ARM/Power

對(duì)于x86架構(gòu)的cpu來(lái)說(shuō)，在單核上來(lái)看，其保證了Sequential consistency，因此對(duì)于開(kāi)發(fā)者，我們可以完全不用擔(dān)心單核上的亂序優(yōu)化會(huì)給我們的程序帶來(lái)正確性問(wèn)題。在多核上來(lái)看，其保證了x86-tso模型，使用mfence就可以將store buffer中的數(shù)據(jù)，寫入到cache中。而且，由于x86架構(gòu)下，store buffer是FIFO的和不存在invalid queue，mfence能夠保證多核間的數(shù)據(jù)可見(jiàn)性，以及順序性。[2]

對(duì)于arm和power架構(gòu)的cpu來(lái)說(shuō)，編程就變得危險(xiǎn)多了。除了存在數(shù)據(jù)依賴，控制依賴以及地址依賴等的前后指令不能被亂序之外，其余指令間都有可能存在亂序。而且，它們的store buffer并不是FIFO的，而且還可能存在invalid queue，這些也同樣讓并發(fā)編程變得困難重重。因此需要引入不同類型的barrier來(lái)完成不同的需求。[3]

總結(jié)

從上面的介紹可以知道，開(kāi)發(fā)者想要做好并發(fā)編程是多么困難的事情，但是我們至少跨出了第一步，也就是定義困難本身。