一文讀懂Memory consistency model (內(nèi)存模型)

Memory consistency model又稱Memory model (內(nèi)存模型)，定義了使用Shared memory(共享內(nèi)存)執(zhí)行多線程(Multithread)程序所允許的行為規(guī)范。Memory model定義了軟硬件接口規(guī)范，以便程序員預(yù)料硬件的行為、硬件實(shí)現(xiàn)者知道可以使用什么樣的優(yōu)化，消除軟硬件在配合上的歧義。

1、共享內(nèi)存的問題

為什么需要定義內(nèi)存模型規(guī)范，我們先舉個(gè)例子：系統(tǒng)中有兩個(gè)cores在執(zhí)行各自的代碼，假設(shè)所有變量的初始值都是0，那么最終Core C2中寄存器r2的值應(yīng)該為多少呢？

表1 寄存器r2的最終值為多少？

大多數(shù)程序員會(huì)期望Core C2的寄存器r2應(yīng)該得到NEW值。然而，如今一些計(jì)算機(jī)系統(tǒng)中，最終寄存器r2的值可能是0。因?yàn)镾1 store和S2 store訪問不同的地址，硬件可能會(huì)對(duì)Core C1的S1 store和S2 store重排序，從而使得S2先于S1寫到memory中。接下來，Core C2讀取到Core C1的S2 store更新的flag值NEW，以為Core C1已經(jīng)準(zhǔn)備好了data值，就發(fā)起L2 load讀取data返回給寄存器r2，而此時(shí)data值為0，也就導(dǎo)致最終寄存器r2為0。如下表2所示，程序的執(zhí)行總順序是S2->L1->L2->S1。

表2 程序的一種可能執(zhí)行結(jié)果

對(duì)于相同地址的memory訪問，硬件需要保證它們按照程序順序(program order)執(zhí)行，但硬件會(huì)對(duì)不同地址的memory訪問進(jìn)行重排序(Reorder)，根據(jù)重排序的memory操作是load還是store，分為四種情況：

Store-store reorder：如果Core有一個(gè)非FIFO類型的write buffer，它允許store以不同于它們進(jìn)入的順序離開，那么兩個(gè)store可能會(huì)被重新排序。比如第一個(gè)store在cache中miss，而第二個(gè)store hit cache，又或者第二個(gè)store與更老(older)的store合并(merge)到同一個(gè)write buffer的條目中。Store-store重排序?qū)尉€程執(zhí)行沒有影響。對(duì)多線程就會(huì)出現(xiàn)表1的現(xiàn)象。

Load-load reorder：Core的動(dòng)態(tài)調(diào)度可以不按program order執(zhí)行指令。如果表1中，Core C2可以亂序執(zhí)行L1 load和L2 load。對(duì)于單線程執(zhí)行，這種不同地址的重排序是安全的。但多線程中，Core C2的load重排序與Core C1的重排序store情況相同，如果memory按照L2->S1->S2->L1的順序執(zhí)行，那么寄存器r2將被賦值為0。

Load-store reorder：亂序執(zhí)行的Core可以重排序來自同一線程不同地址的load和store指令。用年輕的(younger)的store重排序到較老(older)的load之前(load-store reorder)可能會(huì)導(dǎo)致不正確的行為。如果younger store是互斥鎖(mutex)的解鎖操作，那么被reorder的older load可能load到解鎖之后的其它值。

Store-load reorder：如果將younger的load重排序到older的store之前，就如表3所示，可能會(huì)出現(xiàn)反直覺的結(jié)果r1和r2都是0。這種情況通常是系統(tǒng)中實(shí)現(xiàn)了FIFO類型的write buffer引起的。就比如Intel和AMD的x86系統(tǒng)。

表3 r1和r2可以同時(shí)為0嗎

與單線程執(zhí)行不同，多線程執(zhí)行通常允許多個(gè)正確的行為，這種執(zhí)行結(jié)果的不確定可能會(huì)讓大家感覺困惑，但所有當(dāng)今的多Core在默認(rèn)情況下都是非確定性的，所有體系結(jié)構(gòu)(architecture)都允許并發(fā)線程的多重交錯(cuò)執(zhí)行。不過我們平時(shí)使用的軟件會(huì)有適當(dāng)?shù)耐讲僮鱽韺⑦@些不確定性轉(zhuǎn)成確定性的結(jié)果。因此，必須精確地定義memory model，減少這些不確定帶來的影響。

2、Memory consistency model標(biāo)準(zhǔn)

2.1 4P原則

一個(gè)好的Memory consistency model應(yīng)該具備以下4P原則：

Programmability：好的模型應(yīng)該使編寫多線程程序變得相對(duì)容易，而且對(duì)于大多數(shù)用戶來說是直觀的。

Performance：好的模型應(yīng)該在合理的功耗、成本等條件下促進(jìn)更高性能的實(shí)現(xiàn)，也應(yīng)該給予實(shí)現(xiàn)者廣泛的選擇余地。

Portability： 好的模型應(yīng)該被廣泛采用，或者至少提供向后兼容或模型之間的轉(zhuǎn)換能力。

Precision：好的模型應(yīng)該是能用數(shù)學(xué)公式精確定義的。自然語言描述太過模棱兩可，通常會(huì)讓受用者無法達(dá)到允許的極限。

2.2 Memory consistency model和cache coherency的聯(lián)系和區(qū)別

之前的另一篇文章解釋了cache coherency原理，需要的請(qǐng)翻看《一文讀懂Cache一致性原理》。Cache coherency和memory consistency很容易混淆，看似cache coherency定義了共享內(nèi)存(Shared memory)的行為。但事實(shí)并非如此，從圖1可以看到，coherency協(xié)議只是為core pipeline提供了一個(gè)內(nèi)存系統(tǒng)(Memory system)的抽象，它本身不能決定共享內(nèi)存的行為，反之，core pipeline也不能。

圖1 consistency model

如果core pipline以與program order相反的順序?qū)emory操作重排序并送給coherency協(xié)議，即使coherency協(xié)議正確地完成了它的工作，共享內(nèi)存也會(huì)發(fā)生問題?？偨Y(jié)來說:

Cache coherency不等于Memory consistency。Memory consistency是由core pipeline和cache coherency共同實(shí)現(xiàn)的，共同定義了共享內(nèi)存的行為。

Memory consistency的實(shí)現(xiàn)可以把cache coherency當(dāng)作是一個(gè)黑盒子。

3、概念解釋

為了方便大家的理解，本小節(jié)講述了memory consistency中常見的幾個(gè)概念。

Program order(程序順序)：是指程序內(nèi)語句的順序執(zhí)行，這意味著語句將按照它們?cè)诖a中編寫的順序依次執(zhí)行，除非遇到循環(huán)、條件或函數(shù)調(diào)用等控制流結(jié)構(gòu)改變了執(zhí)行流。

Memory order(內(nèi)存順序)：是指系統(tǒng)中處理器(單個(gè)core或多個(gè)cores)的各個(gè)操作對(duì)內(nèi)存進(jìn)行訪問的總順序(total order)。

Single processor (core) sequential：是指任意指令的執(zhí)行結(jié)果與按照程序指定的順序執(zhí)行的操作相同。

Multiprocessor sequentially consistent：是指任意執(zhí)行的結(jié)果都是相同的，所有處理器的操作都按照某種內(nèi)存順序執(zhí)行，并且每個(gè)處理器的操作按照其程序指定的順序出現(xiàn)在內(nèi)存順序中。

Load：從memory中讀取數(shù)據(jù)到寄存器。

Store：將寄存器數(shù)據(jù)寫到memory中。

RMW：為了編寫多線程代碼，程序員需要能夠同步不同線程，而這種同步通常需要執(zhí)行成對(duì)的原子操作。這個(gè)功能是由原子執(zhí)行的“read-modify-write” (RMW)指令提供的，例如：“test-and-set”， “fetch-and-increment”和 “compare-and-swap”。這些原子指令對(duì)于正確的同步至關(guān)重要，并用于實(shí)現(xiàn)spin-locks(自旋鎖)和其它同步場(chǎng)景。比如spin-lock，程序員可以使用RMW來原子地讀取鎖的值是否為未鎖定(等于0)，并寫入鎖定的值(等于1)。

FENCE：執(zhí)行FENCE可以確保program order在FENCE之前的memory操作先于比在FENCE之后的memory操作到達(dá)memory order上的。因此，F(xiàn)ENCE也叫memory barriers。FENCE在SC模型中是不需要的，在TSO和relaxed模型中才需要的。不過TSO模型的程序員很少使用FENCE，因?yàn)門SO在大多數(shù)場(chǎng)景下不需要FENCE。但是FENCE對(duì)relaxed模型有重要作用。

Processor consistency：簡稱PC，表示一個(gè)Core的store操作按順序達(dá)到其它Core，但不一定同時(shí)達(dá)到其它Core。TSO模型是PC的特殊情況，其中每個(gè)Core都可以立即看到自己的Store操作，但是當(dāng)任何其它Core看到Store操作時(shí)，所有其它Core都可以看到它，這個(gè)屬性稱為write atomicity。

圖2 memory system

關(guān)于load和store在program order和memory order上出現(xiàn)的位置可以用下圖3方式來展示。中間垂直向下的箭頭表示memory order (<m)，而每個(gè)Core的向下箭頭表示其program order (<p)。op1<m op2意味著在memory order上，op1在op2之前。類似的op1<p op2意味著在Core的program order中，op1在op2之前。在Sequential Consistency (SC，下文會(huì)詳細(xì)介紹)中，memory order保留每個(gè)Core的program order?！氨Ａ簟笔侵竜p1<p op2意味著op1<m op2。注釋中的值(/* … */)為load或store的值。

圖3 執(zhí)行流表示

4、Memory consistency model分類 -

Memory consistency model主要可以分為Strong model和Relaxed model兩大類，如下圖4所示為常見的memory model。

圖4 常見memory model

一般來說，memory models之間是relaxed(weaker)還是stronger可以這樣判斷：如果所有model A里允許的行為也是model B里允許的行為，則model B比model A更relaxed(weaker)，反之則不然。如果model B比model A更relaxed，那么所有的model A實(shí)現(xiàn)也是model B實(shí)現(xiàn)。當(dāng)然也有可能兩個(gè)memory models無法比較，因?yàn)樗鼈兏髯远加袑?duì)方不允許的行為。

在Strong model里，常見的有SC (Sequential Consistency)和TSO (Total Store Order)兩種，這兩種models的global memory order通常都保留每個(gè)線程的program order。我們平時(shí)常見的Intel和AMD的CPU就是采用TSO模型的。Relaxed model也包括很多種類的models，終端設(shè)備中大量使用的Arm CPU就是采用Relaxed model。Relaxed model只保留程序員需要的順序，這種方法的主要好處是允許更多的硬件和軟件(編譯器和運(yùn)行系統(tǒng))優(yōu)化，減少排序約束可以促進(jìn)性能的提高。主要缺點(diǎn)是，當(dāng)需要在某些訪存操作間排序時(shí)，relaxed model必須為程序員或低層次軟件提供排序的通信機(jī)制，而供應(yīng)商未能就relaxed model達(dá)成一致，損害了代碼的可移植性。

5、SCmodel -

Sequential consistency (SC)模型是最直觀的memory model，它是程序員對(duì)共享內(nèi)存的預(yù)期行為，并為理解其它memory model提供了基礎(chǔ)。在SC模型中，memory order保留了每個(gè)core的program order。也就是SC模型為同一個(gè)線程的兩個(gè)指令間的所有四種load和store組合(Load -> Load, Load -> Store, Store -> Store, and Store -> Load)保留了順序。

5.1 SC模型舉例

圖5以表1中的代碼為示例。

表1 寄存器r2的最終值為多少？

圖5 表1程序的SC執(zhí)行

在圖5中，兩個(gè)Core的執(zhí)行以Core C2寄存器r2的值為NEW結(jié)束。唯一的不確定性是Core C2 L1在load值SET之前讀取flag為0的次數(shù)是多少，不過這一點(diǎn)不重要。

再以表3為例。

表3 r1和r2可以同時(shí)為0嗎

在SC模型中，(r1, r2)的可能值有三種：(0, NEW)，(NEW, 0)或(NEW, NEW)。

(r1, r2)為(0, NEW)的執(zhí)行流：{S1, L1, S2, L2}；

(r1, r2)為(NEW, 0)的執(zhí)行流：{S2, L2, S1, L1}；

(r1, r2)為(NEW, NEW)的執(zhí)行流：{S1, S2, L1, L2}，{S1, S2, L2, L1}，{S2, S1, L1, L2}，{S2, S1, L2, L1}；

(r1, r2)為(0,0)的執(zhí)行流：無；

圖6畫出了(r1, r2)為(NEW, NEW)的執(zhí)行流的其中一種{S1, S2, L1, L2}。

圖6 SC執(zhí)行流

圖7畫出了一個(gè)非SC的執(zhí)行流來做對(duì)比，在這種執(zhí)行流中，(r1, r2)的值將為(0,0)。但對(duì)于這種結(jié)果，沒有辦法創(chuàng)建一個(gè)保留program order的memory order，因此不被SC模型所允許。

圖7 非SC執(zhí)行流

5.2 SC模型公式

L(a)和S(a)分別表示地址為a的load和store指令。<p和<m分別定義了program order和memory order。SC模型需要滿足以下條件：

不論load或store指令是訪問相同還是不同的地址(即a＝b或a≠b)，所有Cores按照program order將它們插入到memory order<m中。有四種情況：

如果L(a) <p L(b)，那么L(a)<m L(b)? ???/* Load -> Load */

如果L(a) <p S(b)，那么L(a)<m S(b)? ?/* Load -> Store */

如果S(a) <p S(b)，那么S(a)<m S(b)? ?/* Store -> Store */

如果S(a) <p L(b)，那么S(a)<m L(b)

/* Store -> Load */

每次load得到的數(shù)據(jù)值都是從它之前(memory order)的最后一個(gè)相同地址的store獲取到的。也就是L(a)的值等于MAX<m {S(a) | S(a)<m L(a)}的值，其中MAX<m表示memory order上的最新值。

表4總結(jié)了SC模型的排序要求，這個(gè)表指定consistency model強(qiáng)制遵循哪些program order。如果一個(gè)給定的線程在program order的store之前有一個(gè)load(load是表中的”O(jiān)peration1”，store是表中的”O(jiān)peration2”)，那么在交集的表項(xiàng)如果是一個(gè)”X”，表示對(duì)應(yīng)的操作必須按program order執(zhí)行。對(duì)于SC，所有的memory操作都必須按照program order執(zhí)行的。對(duì)于RMW指令的執(zhí)行必須是原子的，RMW的read(load)和write(store)操作必須連續(xù)出現(xiàn)在SC模型的memory order上。

表4 SC保序規(guī)則 (X表示必須遵循)

5.3 SC模型實(shí)現(xiàn)

如圖8所示，SC模型可以用一組Core Ci、一個(gè)多選一選擇器和一個(gè)Memory實(shí)現(xiàn)。假設(shè)每個(gè)Core按program order一次向選擇器提供一個(gè)memory操作，選擇器每次選擇一個(gè)Core的操作，允許完成一次memory訪問操作，再去選擇下一個(gè)操作，并且只要Core存在請(qǐng)求就重復(fù)此過程。如果有多個(gè)Core同時(shí)請(qǐng)求，選擇器可以通過任何方法(例如：隨機(jī))挑選Core。這就完成了一個(gè)簡單的SC模型。

圖8 簡單的SC模型實(shí)現(xiàn)

6、TSOmodel

Total Store Order(TSO)是一個(gè)廣泛使用的memory consistency model。TSO最初是由SPARC引入的，x86也是使用TSO模型。為了方便移植最初為x86或SPARC架構(gòu)編寫的代碼，RISC-V也支持TSO擴(kuò)展RVTSO。

6.1 為何引入TSO模型

處理器Core經(jīng)常使用write(store) buffer來保存commited(retired)的stores指令，直到memory系統(tǒng)可以處理這些stores。當(dāng)store commit時(shí)，它就進(jìn)入write buffer，Core可以繼續(xù)處理后續(xù)的指令，直到要寫的cache line在cache中有讀寫權(quán)限，store從write buffer中退出來。因此，write buffer隱藏了處理器store miss cache下的latency(延遲)。

在單core處理器中，如果對(duì)地址A的store還在write buffer中，后續(xù)對(duì)地址A的load可以通過bypass方式來獲取最近store的數(shù)據(jù)，其中最近的順序是由program order決定的，從而使write buffer在體系結(jié)構(gòu)(architecture)上不可見。但在多core處理器中，如果每個(gè)core都有自己的bypass write buffer，那么write buffer在體系結(jié)構(gòu)上是必須可見的。以表5的代碼為例，Core C1的S1和Core C2的S2假設(shè)都把store data暫放在write buffer中，最終會(huì)使得r1,r2都為0，但這種情況在SC模型中是不可能的。

表5 r1和r2會(huì)同時(shí)為0嗎

如果去掉write buffer，會(huì)使性能下降，因此SPARC和后來的x86選擇放棄SC模型，轉(zhuǎn)而支持TSO模型。TSO模型允許在每個(gè)Core上使用FIFO類型的write buffer，它允許r1,r2都為0的結(jié)果。下圖9為r1,r2都為0的TSO執(zhí)行流。

圖9 TSO模型執(zhí)行

6.2 TSO模型舉例

在TSO模型中，Store->Load的memory order不需要保留program order，因此允許每個(gè)Core使用write buffer。由于TSO模型需要保留Store->Store的order，因此write buffer必須是FIFO類型的，而且不能合并多個(gè)store的數(shù)據(jù)。

TSO允許一些非直觀的執(zhí)行結(jié)果，表6是在表5的基礎(chǔ)上修改的.其中Core C1和Core C2分別生成x和y的本地副本。許多程序員可能會(huì)假設(shè)，如果r2和r4都等于0，那么r1和r3也應(yīng)該是0，因?yàn)閟tore S1和S2必須在load L2和L4之后插入memory order中。

表6 r1和r3是否會(huì)被設(shè)置為0

但是，圖10演示了一個(gè)執(zhí)行流，其中r1和r3通過bypass獲得了每個(gè)Core的write buffer中的NEW值。實(shí)際上，為了保持單線程順序正確，每個(gè)Core都必須按照program order看到自己store的數(shù)據(jù)，即使其它Core還沒有觀察到該store的數(shù)據(jù)。因此，在所有的TSO模型執(zhí)行中，本地副本r1和r3總是被設(shè)置為NEW值。

圖10 程序的TSO執(zhí)行 (帶有bypass)

6.3 TSO模型公式

TSO模型執(zhí)行需要滿足以下條件：

不論load或store指令是訪問相同還是不同的地址(即a＝b或a≠b)，所有Cores按照program order將它們插入到memory order<m中。有四種情況：

如果L(a) <p L(b)，那么L(a)<m L(b)? ???/* Load -> Load */

如果L(a) <p S(b)，那么L(a)<m S(b)? ? /* Load -> Store */

如果S(a) <p S(b)，那么S(a)<m S(b) /* Store -> Store */

如果S(a) <p L(b)，那么S(a)<m L(b) /* Store -> Load */

/* 修改點(diǎn)1：使能FIFO write buffer */

每次load得到的數(shù)據(jù)值都是從它之前(memory order)的最后一個(gè)相同地址的store獲取到的。也就是L(a)的值等于MAX<m {S(a) | S(a) <m L(a) or <p L(a)}的值/*(修改點(diǎn)2：需要bypass)*/，其中MAX<m表示最新值。這一點(diǎn)表示load的值是同一地址的最后一個(gè)store的值，該store在memory order中處于它前面，或者在program order中處于它前面(通過write buffer來bypass)。

因?yàn)?)中Store->Load的memory order不被保證，所以TSO增加了FENCE指令，在程序員希望對(duì)Store->load進(jìn)行排序的情況下，可以store和后續(xù)的load之間放置一個(gè)FENCE指令來顯示指定排序關(guān)系。FNECE指令可以對(duì)任何操作進(jìn)行保序。它的定義如下： /*(修改點(diǎn)3)*/

如果L(a) <p FENCE，那么L(a)<m?FENCE ? ?/* Load -> FENCE */

如果S(a) <p FENCE，那么S(a)<m FENCE ??/* Store -> FENCE */

如果FENCE <p FENCE，那么FENCE <m FENCE ??/* FENCE -> FENCE */

如果FENCE <p L(a)，那么FENCE<m L(a)? ? /* FENCE -> Load */

如果FENCE <p S(a)，那么FENCE<m S(a)? ? ?/* FENCE -> Store */

除了Store->Load之外，TSO模型要求其它操作要自然保序。因此TSO模型的FENCE可以只定義以下屬性：

如果S(a) <p FENCE，那么S(a)<m FENCE ????/* Store -> FENCE */

如果FENCE <p L(a)，那么FENCE<m L(a)? ? ?/* FENCE -> Load */

這里選擇讓TSO FENCE冗余地排序所有操作，這樣也不會(huì)造成問題，并且可以使FENCE像下文Relaxed模型中定義的FENCE。

表7總結(jié)了TSO模型的排序規(guī)則，”X”表示強(qiáng)制排序，”B”表示如果操作指向同一個(gè)地址，則需要bypass數(shù)據(jù)。表中也包含了FENCE指令，SC模型不需要FENCE，因此在SC模型的排序規(guī)則表4中沒有FENCE欄，SC模型的行為就好像在每個(gè)操作之前和之后都自帶有FENCE效果。

表7 TSO模型的保序規(guī)則

為了理解TSO模型中atomic RMW的約束，可以把RMW理解成一筆store緊跟在一筆load之后，它們是不可拆分的。由于TSO模型的排序規(guī)則，RMW的load部分不能超過先前的load。乍一看，RMW的load部分可以bypass write buffer中更早的store指令，但這是不合法的。如果RMW的load部分bypass一個(gè)較早的store指令，因?yàn)镽MW是一個(gè)原子對(duì)，那么RMW的store部分相當(dāng)于也bypass了較早的store指令。但TSO中不允許store之間相互bypass，所以RMW的load部分也不能bypass之前的store指令。

6.4 TSO模型實(shí)現(xiàn)

TSO模型的實(shí)現(xiàn)類似于SC模型，只是為每個(gè)Core增加了一個(gè)FIFO類型的write buffer。關(guān)于這個(gè)實(shí)現(xiàn)，有幾點(diǎn)要求：

Loads和stores按照每個(gè)Core的program order離開該Core。

Load要么bypass write buffer中的值，要么像以前一樣等待選擇器切換，從memory里去獲得值。

Store進(jìn)入FIFO write buffer的尾部，如果buffer已滿，那么就暫停Core的執(zhí)行。

當(dāng)選擇器選擇Core Ci時(shí)，它執(zhí)行下一次load或在write buffer頭部的store操作。

圖11 簡單的TSO模型實(shí)現(xiàn)

7、Relaxedmodel

Relaxed(weker) consistency model是相對(duì)SC和TSO模型來說的，任何比SC和TSO模型更寬松的模型都是Relaxed model。在前文中提過，SC模型為同一線程中l(wèi)oad和store的所有四種組合(Load->Load, Load->Store, Store->Store, ?Store->Load)提供memory order保序。TSO組合為同一線程中l(wèi)oad和store的三種組合(Load->Load, Load->Store, Store->Store)提供保序，不對(duì) Store->Load做memory order保序，TSO模型中如果需要對(duì) Store->Load做保序那么需要FENCE指令。

本節(jié)講述的Relaxed model進(jìn)一步弱化了保序條件，只尋求保留程序員需要的保序，從而允許軟硬件更多的優(yōu)化，促進(jìn)性能提高。缺點(diǎn)是需要程序員推斷哪些操作必須強(qiáng)制排序。

7.1 為何引入Relaxed模型

Relaxed模型優(yōu)化了一些程序員不關(guān)心的指令排序，讓這些指令可以亂序執(zhí)行。以表8為例，大多數(shù)程序員期待r2總是會(huì)得到NEW值，因?yàn)閳?zhí)行流是：S1 -> S3 -> L1 load SET -> L2。類似的，大多數(shù)程序員期待r3也總會(huì)得到NEW值，因?yàn)閳?zhí)行流是：S2 -> S3 -> L1 load SET -> L3。

除了上述兩個(gè)預(yù)期的執(zhí)行流順序外，SC和TSO模型還需要S1 -> S2和L2 -> L3的保序。不過這兩個(gè)額外的順序不影響程序正常運(yùn)行，因此保留這些額外的順序可能會(huì)限制實(shí)現(xiàn)優(yōu)化以幫助提高性能。

表8 什么樣的保序會(huì)使r2和r3都是NEW

表9描述了使用同一lock(鎖)在兩個(gè)程序片段之間切換的一般情況。假設(shè)硬件支持lock acquire(例如，使用test-and-set對(duì)lock執(zhí)行讀-修改-寫操作，并循環(huán)直到成功)和lock release(例如，store lock值為0)操作。Core C1通過acquire獲得lock，讓Section1中的Loads(L1i)和Stores(S1i)以任意順序執(zhí)行，然后release釋放lock。類似的，Core C2在獲得鎖之后，讓讓Section2中的Loads(L2i)和Stores(S2i)以任意順序執(zhí)行。從Section1切換到Section2的正確操作取決于這些操作的順序：

All L1i, All S1j -> R1 -> A2 -> All L2i, All S2j? ??// (逗號(hào)“,”表示操作之間未指定順序)

Core C1和C2程序的正常運(yùn)行不依賴于每個(gè)Section內(nèi)的loads和stores的任何排序，除非這些操作指向相同的地址(在這種情況下，需要操作排序以保持單線程的sequentiality)，所以：

所有的L1i和S1j可以以任何順序相對(duì)執(zhí)行，并且所有的L2i和S2j可以以任何順序相對(duì)執(zhí)行。

如果正確的操作不依賴于許多l(xiāng)oads和stores之間的順序，那么通過放松它們之間的順序可能會(huì)獲得更高的性能，因?yàn)閘oad和store通常比lock的acquire和release要頻繁的多，所以這就是relaxed(weak)模型存在的意義。

表9 如何從section1切換到section2

7.2 Relaxed模型舉例

因?yàn)镽elaxed模型很多，為了方便說明，以XC(eXample relaxed Consistency model)模型來代表relaxed模型的基本思想和一些實(shí)現(xiàn)潛力。與SC和TSO一樣，XC模型也假設(shè)存在global memory order。對(duì)不同地址的memory操作，XC模型允許它們亂序執(zhí)行。但是對(duì)于相同地址的memory操作，XC和TSO的規(guī)則一致。

XC模型也提供了一個(gè)FENCE指令，以便程序員可以指示合適需要保序，這個(gè)FENCE指令的功能和TSO中的FENCE類似，除了有些體系結(jié)構(gòu)中FENCE指令會(huì)指定不同的保序?qū)傩?。FENCE指令不指定地址，同一個(gè)Core中兩個(gè)FENCE指令也會(huì)保序。另外，F(xiàn)ENCE指令不會(huì)影響其它Core的memory操作順序。

表10位程序員應(yīng)該如何在表8程序的基礎(chǔ)上插入FENCE，以便程序可以在XC模型下正常運(yùn)行。這些FENCE保證以下順序：

S1, S2 -> F1 -> S3 -> L1 loads SET -> F2 -> L2, L3

F1 FENCE將S1,S2和S3隔開，確保S1和S2先于S3執(zhí)行。F2 FENCE是為了防止在亂序指令中，L2,L3可能先于L1執(zhí)行，這樣的話，最終r2和r3的值可能為0，不符合程序的意圖。

表10 為XC模型添加FENCE到表8的程序

圖10為表10中XC模型的執(zhí)行，其中Core C1的Store S1和S2亂序執(zhí)行，Core C2的load L1和L2也亂序執(zhí)行。但是，這兩種亂序執(zhí)行都不會(huì)影響程序的最終結(jié)果。因此，對(duì)程序員而言，這個(gè)XC模型執(zhí)行等同于圖11種描述的SC執(zhí)行，其中兩對(duì)操作沒有亂序執(zhí)行。

圖12 表10的XC模型執(zhí)行流

圖13 表10的SC模型執(zhí)行流

這個(gè)例子表明，有了足夠的FENCE，XC模型對(duì)程序員來說就像SC模型一樣。

7.3 Relaxed模型公式

這里使用與SC和TSO一樣的公式表示符號(hào)來描述Relaxed(XC)模型公式。XC模型執(zhí)行需要滿足以下條件：

所有Cores按照以下順序分別將它們的loads, stores和FENCE插入到memory order<m中：

如果L(a) <p FENCE，那么L(a)<m FENCE???????? /* Load -> FENCE */

如果S(a) <p FENCE，那么S(a)<m FENCE???? /* Store -> FENCE */

如果FENCE<p FENCE，那么FENCE<m FENCE ??????/* FENCE -> FENCE */

如果FENCE <p L(a)，那么FENCE<m L(a)????? /* FENCE -> Load */

如果FENCE <p S(a)，那么FENCE<m S(a)???? /* FENCE -> Store */

所有Cores按照以下順序分別將它們同地址的的loads和stores插入到memory order<m中：

如果L(a) <p L’(a)，那么L(a)<m L’(a)????? /* Load -> Load to same address */

如果L(a) <p S(a)，那么L(a)<m S(a)?????? /* Load -> Store to same address */

如果S(a) <p S’(a)，那么S(a)<m S’ (a)?? /* Store -> Store to same address */

每次load都從它之前的最后一個(gè)相同地址的store中獲取到它的值：

Value of L(a) = Value of MAX<m {S(a) | S(a) <m L(a) or <p L(a)}? /* 和TSO類似*/

在表11中總結(jié)了這些保序規(guī)則，這個(gè)表與SC和TSO模型的保序表不大一樣，”X”表示強(qiáng)制保序；”B”表示如果操作的地址相同的話，需要bypass數(shù)據(jù)；”A”表示只有當(dāng)操作的地址相同時(shí)，才強(qiáng)制保序。

該表顯示只有對(duì)相同地址的操作或使用了FENCE的情況下，XC模型才會(huì)強(qiáng)制保序。對(duì)于同地址的store->load與TSO模型規(guī)則一樣，store可以在load之后進(jìn)入global memory order，但load必須可以得到新store的值。

表11 XC模型保序規(guī)則

TSO模型中允許使用FIFO類型的write buffer，隱藏了部分或全部committed store的latency來提高性能。為了進(jìn)一步提高性能，XC模型使用非FIFO類型的write buffer，允許多store數(shù)據(jù)的合并(merge)，即program order上不連續(xù)的兩個(gè)store可以寫入到write buffer的同一個(gè)條目(entry)中。

在TSO模型中，RMW指令執(zhí)行之前，需要Core排空FIFO類型的write buffer，獲得讀寫權(quán)限，然后原子地執(zhí)行RMW的load部分和store部分。在XC模型中，允許RMW的load部分和store部分與其它Stores亂序執(zhí)行，因此Core執(zhí)行RMW指令不需要排空write buffer。因此，只需要獲得對(duì)訪問地址的讀寫權(quán)限，然后執(zhí)行原子地執(zhí)行RMW的load部分和store部分就可以了。

XC和TSO模型之間的一個(gè)重要區(qū)別是如何使用atomic RMW來實(shí)現(xiàn)同步。表12展示了一個(gè)代碼片段，并帶有TSO和XC模型的lock acquire與lock release。對(duì)于TSO模型，atomic RMW用于acquire lock，store用于release lock就足夠了。但對(duì)于XC模型，情況更加復(fù)雜，atomic RMW無法限制其它操作的亂序執(zhí)行，lock acquire后面必須跟一個(gè)FENCE。類似的，lock release也不受限制，也必須在lock release之前先執(zhí)行FENCE。

表12 TSO和XC的同步對(duì)比

7.4 Relaxed模型實(shí)現(xiàn)

與實(shí)現(xiàn)SC和TSO模型的方法類似，圖14為XC模型的實(shí)現(xiàn)。TSO模型實(shí)現(xiàn)中每個(gè)Core都通過FIFO write buffer與Shared memory分開。對(duì)于XC模型實(shí)現(xiàn)，每個(gè)Core將通過一個(gè)更通用的reorder unit(重排序單元)從Shared memory上分離出來，該單元可以對(duì)loads和stores進(jìn)行重排序。關(guān)于這個(gè)實(shí)現(xiàn)，有幾點(diǎn)要求：

每個(gè)Core Ci上的loads, stores和FENCE按照program order離開pipeline并進(jìn)入Ci的reorder unit的尾部。

Core Ci的reorder unit會(huì)對(duì)操作進(jìn)行排序，并按program order或下面指定的規(guī)則，將這些操作從它的尾部傳遞到頭部。當(dāng)FENCE指令到達(dá)reorder unit的頭部時(shí)，它的使命就完成了。

當(dāng)選擇器選擇Core Ci時(shí)，在Ci reorder unit頭部的load或store會(huì)被執(zhí)行。

圖14 簡單的XC模型實(shí)現(xiàn)

對(duì)于(1) FENCE，(2) 同地址的操作，(3) bypass，reorder unit遵循以下規(guī)則：

FENCE可以用幾種不同的方式實(shí)現(xiàn)，但它們必須強(qiáng)制執(zhí)行保序，不管任何地址，reorder unit不能對(duì)它亂序處理：

Load -> FENCE, Store -> FENCE, FENCE -> FENCE, FENCE -> Load, FENCE -> Store

對(duì)同地址操作的，reorder unit也不能亂序處理：

Load -> Load, Load -> Store, Store -> Store ??????(同地址)

Reorder unit必須確保后續(xù)的load可以得到同一個(gè)Core里前面store的數(shù)據(jù)。

7.5 Relaxed 模型的一些重要擴(kuò)展

7.5.1 Release consistency

Release consistency(RC)的提出是基于一個(gè)觀察：將所有同步操作用FENCE圍在一起是多余的。隨著對(duì)同步操作的深入理解，同步操作acquire只需要一個(gè)后面放一個(gè)FENCE，同步操作release只需要前面放一個(gè)FNECE。因此RC提供了ACQUIRE和RELEASE操作，它們和FENCE類似，但是只在一個(gè)方向上對(duì)memory進(jìn)行保序，而不是像FENCE那樣在兩個(gè)方向上都進(jìn)行保序。更一般地說，RC只需要：

ACQUIRE -> Load, Store ??(Load, Store -> ACQUIRE方向不保序)

Load, Store -> RELEASE ???(RELEASE -> Load, Store 方向不保序)

ACQUIRE -> ACQUIRE

ACQUIRE -> RELEASE

RELEASE -> ACQUIRE

RELEASE -> RELEASE

在RISC-V中，與RC類似，load和store指令可以攜帶其它語義：load指令可以攜帶ACQUIRE語義，store指令可以攜帶RELEASE語義，以及RMW指令可以攜帶ACQUIRE、RELEASE或兩者都具有。有兩種ACQUIRE語義：ACQUIRE-RCpc和ACQUIRE-RCsc。同樣，也有兩種RELEASE語義：RELEASE-RCpc和RELEASE-RCsc。Load(store)可以攜帶任何一種ACQUIRE(RELEASE)語義，而RMW只能攜帶RCsc語義。這些語義有如下保序：

ACQUIRE -> Load,Store ??(ACQUIRE代表ACQUIRE-RCSC和ACQUIRE-RCPC)

Load,Store -> RELEASE (RELEASE 代表RELEASE-RCSC和RELEASE-RCPC)

RELEASE-RCSC -> ACQUIRE-RCSC

7.5.2 Causality和Write atomicity

Causality(因果性)：要求“如果我看到它并告訴你，那么你也會(huì)看到它”。以表13為例，其中Core C1執(zhí)行store S1更新data1。當(dāng)Core C2看到S1的結(jié)果(r1==NEW)，執(zhí)行FENCE F1，然后執(zhí)行store S2更新data2。同樣，當(dāng)Core C3看到S2的結(jié)果(r2==NEW)，執(zhí)行FENCE F2，然后執(zhí)行l(wèi)oad L3觀察store S1的值，如果Core C3保證能得到S1的值(r3==NEW)，那么causality關(guān)系成立。否則，如果r3為0，則違反了causality關(guān)系。

表13 Causality: 如果我看到store并告訴你，你也必須看到

Write atomicity：它也稱作store atomicity或multi-copy atomicity，要求一個(gè)core的store在邏輯上被所有其它c(diǎn)ores同時(shí)看到。按照這個(gè)定義，XC模型是write atomicity，因?yàn)樗膍emory order(<m)指定了store在memory中生效的邏輯原子點(diǎn)。在此之前，沒有其它c(diǎn)ore可以看到新store的值。在此之后，所有其它c(diǎn)ore必須看到新值或來自稍后store的值，但不能看到被store覆蓋的之前值。Write atomicity允許一個(gè)core在其它c(diǎn)ore之前看到它自己store的值，這一點(diǎn)XC模型也要求。

8、Memory consistency model比較

圖15畫出了各個(gè)模型關(guān)系的Venn圖。Relaxed模型分兩個(gè)圓圈，第一個(gè)圓圈Power為Power內(nèi)存模型，第二個(gè)圓圈MC2可以是Alpha, ARM, RMO或XC內(nèi)存模型。

Power模型比TSO模型寬松(relaxed)，TSO模型比SC模型寬松。

Alpha，ARM，RMO和XC模型(MC2)比TSO模型寬松，TSO模型比SC模型寬松。

對(duì)于MC2來說，目前與Power模型是無法互相比較的。

圖15 memory模型對(duì)比Venn圖

再結(jié)合4P原則比較下三種memory模型，可列出表14大致的比較結(jié)果。當(dāng)然，這個(gè)表只是相對(duì)的比較，就比如Performance來說，Relaxed模型可以提供比TSO模型更好地性能，但對(duì)于許多Core微架構(gòu)體系來說，這種差異更小。

表14 memory模型的4P比較

9、DRFfor SC

9.1 DRF for SC定義

DRF是Data Race Free的縮寫，表示無數(shù)據(jù)競(jìng)爭(zhēng)。當(dāng)兩個(gè)線程訪問相同的memory地址，至少有一個(gè)訪問是寫操作，并且沒有提供同步操作，那么就會(huì)發(fā)生Data Race(DR, 數(shù)據(jù)競(jìng)爭(zhēng))。通常來說(但不總是)，DR是編程錯(cuò)誤的結(jié)果，因此程序員需要編寫DRF的代碼。

DRF for SC編程需要軟件程序員通過編寫正確的同步程序和標(biāo)記同步指令來確保程序在SC下是DRF。并要求硬件實(shí)現(xiàn)者將同步程序和標(biāo)記同步指令映射到Relaxed模型所支持的FENCE和RMW操作，從而確保在Relaxed模型上執(zhí)行的DRF程序總得效果是SC執(zhí)行的。XC和大多數(shù)商業(yè)relaxed模型都有必須的FENCE和RMW指令來幫助達(dá)到DRF for SC，并且這種方法也是Java和C++高級(jí)語言(HLL) memory模型的基礎(chǔ)。

表15和表16描述了在relaxed模型中DRF for SC的效果。兩個(gè)表的共同點(diǎn)都是Core C1往兩個(gè)不同的地址執(zhí)行store操作(S1和S2)，Core C2以相反的順序load這兩個(gè)位置的數(shù)據(jù)(L1和L2)。兩個(gè)表的不同點(diǎn)在于，表15種的Core C2沒有使用同步，表16的Core C2使用了lock同步機(jī)制。

由于表15的Core C2沒有使用同步，所以L1和L2可以與Core C1的S1和S2并發(fā)亂序執(zhí)行，因此最終(r1, r2)會(huì)有四種結(jié)果：(0, 0), (0, NEW), (NEW, 0), (NEW, NEW)。

表15 具有data race的XC執(zhí)行 (有四種結(jié)果)

表16為Core C1和Core C2爭(zhēng)搶相同的lock(同步機(jī)制)去執(zhí)行各自操作。在這種情況下，先搶到lock的Core先執(zhí)行，因此(r1, r2)會(huì)有兩種結(jié)果：(0, 0), (NEW, NEW)。這種執(zhí)行結(jié)果和SC下允許的結(jié)果一樣。

表16 無data race的XC執(zhí)行 (只有兩種結(jié)果，像SC)

根據(jù)上述的例子，可以簡單總結(jié)DRF for SC的定義：

首先XC模型會(huì)有一些memory操作是用于同步操作的，而其它memory操作是數(shù)據(jù)操作的。DRF是針對(duì)多線程(或多Cores)對(duì)同地址的數(shù)據(jù)操作而言，如果兩筆數(shù)據(jù)操作發(fā)生race(競(jìng)爭(zhēng))且沒有使用同步操作進(jìn)行同步來避免，那么這個(gè)程序就不是DRF的。換句話說，一對(duì)相互沖突的數(shù)據(jù)操作(Di, Dj)當(dāng)且僅當(dāng)存在一對(duì)解決沖突的同步操作(Si, Sj)，使得Di < m Si < mSj < m Dj時(shí)，Di < m Dj不存在數(shù)據(jù)競(jìng)爭(zhēng)，也就是DRF for SC。

如果沒有數(shù)據(jù)操作競(jìng)爭(zhēng)，那么SC執(zhí)行是DRF的。如果一個(gè)程序的所有SC執(zhí)行都是DRF，那么這個(gè)程序就是DRF的。另外一個(gè)memory模型支持“SC for DRF programs”，那么所有DRF程序在這個(gè)memory模型上的執(zhí)行都是SC執(zhí)行的。這種支持通常需要memory模型提供一些特殊的同步操作。

支持“SC for DRF programs”允許程序員使用SC模型而不是更復(fù)雜的XC模型來推理他們寫的程序，同時(shí)受益于XC模型的性能改進(jìn)。總之，使用relaxed模型的程序員可以使用兩種方式來推理他們的程序：

可以直接使用relaxed模型最本質(zhì)的推理來判斷模型會(huì)做什么和不會(huì)做什么；

可以插入足夠的同步操作，以確保沒有沒有數(shù)據(jù)競(jìng)爭(zhēng)(DRF)，但同步操作競(jìng)爭(zhēng)仍然是允許的，并使用相對(duì)簡單的SC模型來推理他們的程序。

當(dāng)然，推薦是使用后一種SC for DRF的方法，第一種方法通常是留給編寫同步庫或設(shè)備驅(qū)動(dòng)程序等代碼的專家使用的。

9.2 高級(jí)語言模型

前面討論了硬件和底層軟件之間接口的memory consistency models，討論了軟件期望什么，硬件實(shí)現(xiàn)者可以做什么。本節(jié)主要將高級(jí)語言(HLLs)的memory模型，確定：(a) HLL軟件應(yīng)該期望什么，(2) 編譯器、運(yùn)行系統(tǒng)和硬件實(shí)現(xiàn)者可能會(huì)做什么。圖16展示了高級(jí)和底層語言的memory模型。

圖16 (a) 高級(jí)語言，(b) 硬件memory模型

Java和C++兩個(gè)高級(jí)語言的模型基礎(chǔ)都是“SC for DRF”，允許synchronization同步競(jìng)爭(zhēng)，但不允許數(shù)據(jù)競(jìng)爭(zhēng)。程序員必須在變量可能競(jìng)爭(zhēng)時(shí)將其標(biāo)記為synchronization(使用注入atomic之類的關(guān)鍵字)，或者使用Java的類似監(jiān)控器的synchronized方法隱式創(chuàng)建同步鎖。在所有情況下，只要沒有數(shù)據(jù)競(jìng)爭(zhēng)的程序都會(huì)遵守SC執(zhí)行，因此，實(shí)現(xiàn)可以自由地亂序執(zhí)行。

實(shí)現(xiàn)可以在同步訪問之間亂序執(zhí)行或減少內(nèi)存訪問。圖17給出了一個(gè)例子。圖17(a)為HLL代碼，圖17(b)為Core C1上的執(zhí)行代碼且沒有分配寄存器(register allocation)，圖17(c)為Core C1上的執(zhí)行代碼且有分配寄存器給變量A，從而使load L2與load L1兩個(gè)操作可以重排序并合并。因?yàn)槭褂谩癝C for DRF”規(guī)則判斷，沒有其它線程與變量A的load有數(shù)據(jù)沖突，所以這種合并是可行的。

圖17 寄存器分配影響memory order

除了寄存器分配，許多編譯器和運(yùn)行系統(tǒng)都可以對(duì)內(nèi)存訪問進(jìn)行重排序，例如常量傳播、公共表達(dá)式消除、循環(huán)裂變/融合、循環(huán)不變代碼移動(dòng)。軟件流水線和指令調(diào)度等等?！癝C for DRF”允許這些優(yōu)化，編譯器和運(yùn)行系統(tǒng)可以生成與單線程性能相當(dāng)?shù)拇a。因此，Java和SC提供了多種同步操作，編譯器和運(yùn)行系統(tǒng)只需要將HLL的同步操作轉(zhuǎn)換為特定硬件的底層同步操作或FENCE，以提供必要的保序，其余情況下，可以重排序所有操作，來使性能最大化。

10、總結(jié)

為了解決多線程或多Core使用共享內(nèi)存出現(xiàn)不確定的結(jié)果，業(yè)界定義了多種memory consistency model，消除軟硬件在配合上的歧義。本文講述了常見的SC、TSO和Relaxed模型，分析了創(chuàng)建該模型的原因、模型的使用例子、模型的公式和模型的實(shí)現(xiàn)，并總結(jié)了三種模型的優(yōu)缺點(diǎn)。一個(gè)好的模型，應(yīng)該在Programmability, Performance, Portability和Precision (4P原則)上都有較好的表現(xiàn)。最后介紹了“DRF? for SC”的概念，它的出現(xiàn)主要是Relaxed模型分析起來過于復(fù)雜，需要一些同步機(jī)制來簡化模型分析，并把更多的不確定結(jié)果轉(zhuǎn)成確定結(jié)果，這一點(diǎn)在高級(jí)語言C++和Java都有應(yīng)用。

本文沒有對(duì)Relaxed模型里的其它模型做更深入描述，比如RISC-V的RVWMO和Arm的Other-multi-copy atomic，盡管它們兩者很像。另外沒有介紹relaxed模型中可能存在的address、data和control dependencies，這三者在有些模型里可以引起memory order，它們是語法上的依賴關(guān)系，而不是語義依賴關(guān)系，與寄存器的選取有關(guān)。

希望本文能幫助大家了解更多的memory consistency model知識(shí)。今天就寫到這里了，后面的計(jì)劃是分享下“軟硬件虛擬化”的文章，但可能需要更長的時(shí)間。近期打算先把之前規(guī)劃的分享視頻做下，敬請(qǐng)期待。

微信號(hào)｜c(diǎn)hip_yes

微信公眾號(hào)｜專芯致志er

專注分享Arm architecture，AMBA，芯片驗(yàn)證，腳本，EDA工具，Linux等知識(shí)。