處理器架構(gòu)下并發(fā)編程里必須掌握的基礎(chǔ)概念

現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)上，CPU執(zhí)行指令的速度遠(yuǎn)遠(yuǎn)大于CPU訪問(wèn)內(nèi)存的速度，于是引入Cache機(jī)制來(lái)加速內(nèi)存訪問(wèn)速度。除了Cache以外，分支預(yù)測(cè)和指令預(yù)取也在很大程度上提升了CPU的執(zhí)行速度。隨著SMP的出現(xiàn)，多線程編程模型被廣泛應(yīng)用，在多線程模型下對(duì)共享變量的訪問(wèn)變成了一個(gè)復(fù)雜的問(wèn)題。于是我們有必要了解一下內(nèi)存模型，這是多處理器架構(gòu)下并發(fā)編程里必須掌握的一個(gè)基礎(chǔ)概念。

1. 什么是內(nèi)存模型？

到底什么是內(nèi)存模型呢？看到有兩種不同的觀點(diǎn)：

A：內(nèi)存模型是從來(lái)描述編程語(yǔ)言在支持多線程編程中對(duì)共享內(nèi)存訪問(wèn)的順序。

B：內(nèi)存模型的本質(zhì)是指在單線程情況下CPU指令在多大程度上發(fā)生指令重排（reorder）［1］。

實(shí)際上A，B兩種說(shuō)法都是正確的，只不過(guò)是在嘗試從不同的角度去說(shuō)明memory model的概念。個(gè)人認(rèn)為，內(nèi)存模型表達(dá)為“內(nèi)存順序模型”可能更加貼切一點(diǎn)。

一個(gè)良好的memory model定義包含3個(gè)方面：

Atomic Operations

Partial order of operations

Visable effects of operations

這里要強(qiáng)調(diào)的是：我們這里所說(shuō)的內(nèi)存模型和CPU的體系結(jié)構(gòu)、編譯器實(shí)現(xiàn)和編程語(yǔ)言規(guī)范3個(gè)層面都有關(guān)系。

首先，不同的CPU體系結(jié)構(gòu)內(nèi)存順序模型是不一樣的，但大致分為兩種：

ArchitectureMemory Model

x86_64Total Store Order

SparcTotal Store Order

ARMv8Weakly Ordered

PowerPCWeakly Ordered

MIPSWeakly Ordered

x86_64和Sparc是強(qiáng)順序模型（Total Store Order），這是一種接近程序順序的順序模型。所謂Total，就是說(shuō)，內(nèi)存（在寫(xiě)操作上）是有一個(gè)全局的順序的（所有人看到的一樣的順序）， 就好像在內(nèi)存上的每個(gè)Store動(dòng)作必須有一個(gè)排隊(duì)，一個(gè)弄完才輪到另一個(gè)，這個(gè)順序和你的程序順序直接相關(guān)。所有的行為組合只會(huì)是所有CPU內(nèi)存程序順序的交織，不會(huì)發(fā)生和程序順序不一致的地方［4］。TSO模型有利于多線程程序的編寫(xiě)，對(duì)程序員更加友好，但對(duì)芯片實(shí)現(xiàn)者不友好。CPU為了TSO的承諾，會(huì)犧牲一些并發(fā)上的執(zhí)行效率。

弱內(nèi)存模型（簡(jiǎn)稱WMO，Weak Memory Ordering），是把是否要求強(qiáng)制順序這個(gè)要求直接交給程序員的方法。換句話說(shuō)，CPU不去保證這個(gè)順序模型（除非他們?cè)谝粋€(gè)CPU上就有依賴）， 程序員要主動(dòng)插入內(nèi)存屏障指令來(lái)強(qiáng)化這個(gè)“可見(jiàn)性”［4］。ARMv8，PowerPC和MIPS等體系結(jié)構(gòu)都是弱內(nèi)存模型。每種弱內(nèi)存模型的體系架構(gòu)都有自己的內(nèi)存屏障指令，語(yǔ)義也不完全相同。弱內(nèi)存模型下，硬件實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，處理器執(zhí)行的效率也高， 只要沒(méi)有遇到顯式的屏障指令，CPU可以對(duì)局部指令進(jìn)行reorder以提高執(zhí)行效率。

對(duì)于多線程程序開(kāi)發(fā)來(lái)說(shuō)，對(duì)并發(fā)的數(shù)據(jù)訪問(wèn)我們一般到做同步操作， 可以使用mutex，semaphore，conditional等重量級(jí)方案對(duì)共享數(shù)據(jù)進(jìn)行保護(hù)。但為了實(shí)現(xiàn)更高的并發(fā)，需要使用內(nèi)存共享變量做通信（Message Passing）， 這就對(duì)程序員的要求很高了，程序員必須時(shí)時(shí)刻刻必須很清楚自己在做什么， 否則寫(xiě)出來(lái)的程序的執(zhí)行行為會(huì)讓人很是迷惑！值得一提的是，并發(fā)雖好，如果能夠簡(jiǎn)單粗暴實(shí)現(xiàn)，就不要搞太多投機(jī)取巧！要實(shí)現(xiàn)lock-free無(wú)鎖編程真的有點(diǎn)難。

其次，不同的編程語(yǔ)言對(duì)內(nèi)存模型都有自己的規(guī)范，例如：C/C++和Java等不同的編程語(yǔ)言都有定義內(nèi)存模型相關(guān)規(guī)范。

2011年發(fā)布的C11/C++11 ISO Standard為我們帶來(lái)了memory order的支持， 引用C++11里的一段描述：

The memory model means that C++ code now has a standardized

library to call regardless of who made the compiler and on

what platform it‘s running. There’s a standard way to control

how different threads talk to the processor‘s memory.［7］

memory order的問(wèn)題就是因?yàn)橹噶钪嘏乓鸬模?指令重排導(dǎo)致 原來(lái)的內(nèi)存可見(jiàn)順序發(fā)生了變化， 在單線程執(zhí)行起來(lái)的時(shí)候是沒(méi)有問(wèn)題的， 但是放到 多核/多線程執(zhí)行的時(shí)候就出現(xiàn)問(wèn)題了， 為了效率引入的額外復(fù)雜邏輯的的弊端就出現(xiàn)了［8］。

C++11引入memory order的意義在于我們現(xiàn)在有了一個(gè)與運(yùn)行平臺(tái)無(wú)關(guān)和編譯器無(wú)關(guān)的標(biāo)準(zhǔn)庫(kù)， 讓我們可以在high level languange層面實(shí)現(xiàn)對(duì)多處理器對(duì)共享內(nèi)存的交互式控制。我們的多線程終于可以跨平臺(tái)啦！我們可以借助內(nèi)存模型寫(xiě)出更好更安全的并發(fā)代碼。真棒，簡(jiǎn)直不要太優(yōu)秀~

C11/C++11使用memory order來(lái)描述memory model， 而用來(lái)聯(lián)系memory order的是atomic變量， atomic操作可以用load（）和release（）語(yǔ)義來(lái)描述。一個(gè)簡(jiǎn)單的atomic變量賦值可描述為：

atomic_var1.store （atomic_var2.load（））; // atomic variables

vs

var1 = var2; // regular variables

為了更好地描述內(nèi)存模型，有4種關(guān)系術(shù)語(yǔ)需要了解一下。

sequenced-before

同一個(gè)線程之內(nèi)，語(yǔ)句A的執(zhí)行順序在語(yǔ)句B前面，那么就成為A sequenced-before B。它不僅僅表示兩個(gè)操作之間的先后順序，還表示了操作結(jié)果之間的可見(jiàn)性關(guān)系。兩個(gè)操作A和操作B，如果有A sequenced-before B，除了表示操作A的順序在B之前，還表示了操作A的結(jié)果操作B可見(jiàn)。例如：語(yǔ)句A是sequenced-before語(yǔ)句B的。

r2 = x.load（std：：memory_order_relaxed）; // A

y.store（42， std：：memory_order_relaxed）; // B

happens-before

happens-before關(guān)系表示的不同線程之間的操作先后順序。如果A happens-before B，則A的內(nèi)存狀態(tài)將在B操作執(zhí)行之前就可見(jiàn)。happends-before關(guān)系滿足傳遞性、非自反性和非對(duì)稱性。happens before包含了inter-thread happens before和synchronizes-with兩種關(guān)系。

synchronizes-with

synchronizes-with關(guān)系強(qiáng)調(diào)的是變量被修改之后的傳播關(guān)系（propagate）， 即如果一個(gè)線程修改某變量的之后的結(jié)果能被其它線程可見(jiàn)，那么就是滿足synchronizes-with關(guān)系的［9］。另外synchronizes-with可以被認(rèn)為是跨線程間的happends-before關(guān)系。顯然，滿足synchronizes-with關(guān)系的操作一定滿足happens-before關(guān)系了。

Carries dependency

同一個(gè)線程內(nèi)，表達(dá)式A sequenced-before 表達(dá)式B，并且表達(dá)式B的值是受表達(dá)式A的影響的一種關(guān)系， 稱之為“Carries dependency”。這個(gè)很好理解，例如：

int *a = &var1;

int *b = &var2;

c = *a + *b;

了解了上面一些基本概念，下面我們來(lái)一起學(xué)習(xí)一下內(nèi)存模型吧。

2. C11/C++11內(nèi)存模型

C/C++11標(biāo)準(zhǔn)中提供了6種memory order，來(lái)描述內(nèi)存模型［6］：

enum memory_order {

memory_order_relaxed，

memory_order_consume，

memory_order_acquire，

memory_order_release，

memory_order_acq_rel，

memory_order_seq_cst

};

每種memory order的規(guī)則可以簡(jiǎn)要描述為：

枚舉值定義規(guī)則

memory_order_relaxed不對(duì)執(zhí)行順序做任何保證

memory_order_consume本線程中，所有后續(xù)的有關(guān)本原子類型的操作，必須在本條原子操作完成之后執(zhí)行

memory_order_acquire本線程中，所有后續(xù)的讀操作必須在本條原子操作完成后執(zhí)行

memory_order_release本線程中，所有之前的寫(xiě)操作完成后才能執(zhí)行本條原子操作

memory_order_acq_rel同時(shí)包含memory_order_acquire和memory_order_release標(biāo)記

memory_order_seq_cst全部存取都按順序執(zhí)行

下面我們來(lái)舉例一一說(shuō)明，扒開(kāi)內(nèi)存模型的神秘面紗。

2.1 memory order releaxed

relaxed表示一種最為寬松的內(nèi)存操作約定，Relaxed ordering 僅僅保證load（）和store（）是原子操作， 除此之外，不提供任何跨線程的同步［5］。

std：：atomic《int》 x = 0; // global variable

std：：atomic《int》 y = 0; // global variable

Thread-1： Thread-2：

r1 = y.load（memory_order_relaxed）; // A r2 = x.load（memory_order_relaxed）; // C

x.store（r1， memory_order_relaxed）; // B y.store（42， memory_order_relaxed）; // D

上面的多線程模型執(zhí)行的時(shí)候，可能出現(xiàn)r2 == r1 == 42。要理解這一點(diǎn)并不難，因?yàn)镃PU在執(zhí)行的時(shí)候允許局部指令重排reorder，D可能在C前執(zhí)行。如果程序的執(zhí)行順序是 D -》 A -》 B -》 C，那么就會(huì)出現(xiàn)r1 == r2 == 42。

如果某個(gè)操作只要求是原子操作，除此之外，不需要其它同步的保障，那么就可以使用 relaxed ordering。程序計(jì)數(shù)器是一種典型的應(yīng)用場(chǎng)景：

#include 《cassert》

#include 《vector》

#include 《iostream》

#include 《thread》

#include 《atomic》

std：：atomic《int》 cnt = {0};

void f（）

{

for （int n = 0; n 《 1000; ++n） {

cnt.fetch_add（1， std：：memory_order_relaxed）;

}

}

int main（）

{

std：：vector《std：：thread》 v;

for （int n = 0; n 《 10; ++n） {

v.emplace_back（f）;

}

for （auto& t ： v） {

t.join（）;

}

assert（cnt == 10000）; // never failed

return 0;

}

cnt是共享的全局變量，多個(gè)線程并發(fā)地對(duì)cnt執(zhí)行RMW（Read Modify Write）原子操作。這里只保證cnt的原子性，其他有依賴cnt的地方不保證任何的同步。

2.2 memory order consume

consume要搭配release一起使用。很多時(shí)候，線程間只想針對(duì)有依賴關(guān)系的操作進(jìn)行同步， 除此之外線程中其他操作順序如何不關(guān)心，這時(shí)候就適合用consume來(lái)完成這個(gè)操作。例如：

b = *a;

c = *b

第二行的變量c依賴于第一行的執(zhí)行結(jié)果，因此這兩行代碼是“Carries dependency”關(guān)系。顯然，由于consume是針對(duì)有明確依賴關(guān)系的語(yǔ)句來(lái)限定其執(zhí)行順序的一種內(nèi)存順序， 而releaxed不提供任何順序保證， 所以consume order要比releaxed order要更加地Strong。

#include 《thread》

#include 《atomic》

#include 《cassert》

#include 《string》

std：：atomic《std：：string*》 ptr;

int data;

void producer（）

{

std：：string* p = new std：：string（“Hello”）;

data = 42;

ptr.store（p， std：：memory_order_release）;

}

void consumer（）

{

std：：string* p2;

while （?。╬2 = ptr.load（std：：memory_order_consume）））

;

assert（*p2 == “Hello”）; // never fires： *p2 carries dependency from ptr

assert（data == 42）; // may or may not fire： data does not carry dependency from ptr

}

int main（）

{

std：：thread t1（producer）;

std：：thread t2（consumer）;

t1.join（）;

t2.join（）;

}

assert（*p2 == “Hello”）永遠(yuǎn)不會(huì)失敗，但assert（data == 42）可能會(huì)。原因是：

p2和ptr直接有依賴關(guān)系，但data和ptr沒(méi)有直接依賴關(guān)系，

盡管線程1中data賦值在ptr.store（）之前，線程2看到的data的值還是不確定的。

2.3 memory order acquire

acquire和release也必須放到一起使用。 release和acquire構(gòu)成了synchronize-with關(guān)系，也就是同步關(guān)系。在這個(gè)關(guān)系下：線程A中所有發(fā)生在release x之前的值的寫(xiě)操作， 對(duì)線程B的acquire x之后的任何操作都可見(jiàn)。

#include 《thread》

#include 《atomic》

#include 《cassert》

#include 《string》

#include 《iostream》

std：：atomic《bool》 ready{ false };

int data = 0;

std：：atomic《int》 var = {0};

void sender（）

{

data = 42; // A

var.store（100， std：：memory_order_relaxed）; // B

ready.store（true， std：：memory_order_release）; // C

}

void receiver（）

{

while （！ready.load（std：：memory_order_acquire）） // D

;

assert（data == 42）; // never failed // E

assert（var == 100）; // never failed // F

}

int main（）

{

std：：thread t1（sender）;

std：：thread t2（receiver）;

t1.join（）;

t2.join（）;

}

上面的例子中：

sender線程中data = 42是sequence before原子變量ready的

sender和receiver在C和D處發(fā)生了同步

線程sender中C之前的所有讀寫(xiě)對(duì)線程receiver都是可見(jiàn)的 顯然， release和acquire組合在一起比release和consume組合更加Strong！

2.4 memory order release

release order一般不單獨(dú)使用，它和acquire和consume組成2種獨(dú)立的內(nèi)存順序搭配。

這里就不用展開(kāi)啰里啰嗦了。

2.5 memory order acq_rel

acq_rel是acquire和release的疊加。中文不知道該咋描述好：

A read-modify-write operation with this memory order is both an acquire operation and a release operation. No memory reads or writes in the current thread can be reordered before or after this store. All writes in other threads that release the same atomic variable are visible before the modification and the modification is visible in other threads that acquire the same atomic variable.

大致意思是：memory_order_acq_rel適用于read-modify-write operation， 對(duì)于采用此內(nèi)存序的read-modify-write operation，我們可以稱為acq_rel operation， 既屬于acquire operation 也是release operation. 設(shè)有一個(gè)原子變量M上的acq_rel operation：自然的，該acq_rel operation之前的內(nèi)存讀寫(xiě)都不能重排到該acq_rel operation之后， 該acq_rel operation之后的內(nèi)存讀寫(xiě)都不能重排到該acq_rel operation之前。 其他線程中所有對(duì)M的release operation及其之前的寫(xiě)入都對(duì)當(dāng)前線程從該acq_rel operation開(kāi)始的操作可見(jiàn)， 并且截止到該acq_rel operation的所有內(nèi)存寫(xiě)入都對(duì)另外線程對(duì)M的acquire operation以及之后的內(nèi)存操作可見(jiàn)［13］。

這里是一個(gè)例子，關(guān)于為什么要有acq_rel可以參考一下：

#include 《thread》

#include 《atomic》

#include 《cassert》

#include 《vector》

std：：vector《int》 data;

std：：atomic《int》 flag = {0};

void thread_1（）

{

data.push_back（42）;

flag.store（1， std：：memory_order_release）;

}

void thread_2（）

{

int expected=1;

while （！flag.compare_exchange_strong（expected， 2， std：：memory_order_acq_rel）） {

expected = 1;

}

}

void thread_3（）

{

while （flag.load（std：：memory_order_acquire） 《 2）

;

assert（data.at（0） == 42）; // will never fire

}

int main（）

{

std：：thread a（thread_1）;

std：：thread b（thread_2）;

std：：thread c（thread_3）;

a.join（）; b.join（）; c.join（）;

}

2.6 memory order seq_cst

seq_cst表示順序一致性內(nèi)存模型，在這個(gè)模型約束下不僅同一個(gè)線程內(nèi)的執(zhí)行結(jié)果是和程序順序一致的， 每個(gè)線程間互相看到的執(zhí)行結(jié)果和程序順序也保持順序一致。顯然，seq_cst的約束是最強(qiáng)的，這意味著要犧牲性能為代價(jià)。

atomic int x （0）; atomic int y （0）;

x. store （1， seq cst ）; || y. store （1， seq cst ）;

int r1 = y.load（ seq cst ）; || int r2 = x.load（ seq cst ）;

assert （r1 == 1 || r2 == 1）;

下面是一個(gè)seq_cst的實(shí)例：

#include 《thread》

#include 《atomic》

#include 《cassert》

std：：atomic《bool》 x = {false};

std：：atomic《bool》 y = {false};

std：：atomic《int》 z = {0};

void write_x（）

{

x.store（true， std：：memory_order_seq_cst）;

}

void write_y（）

{

y.store（true， std：：memory_order_seq_cst）;

}

void read_x_then_y（）

{

while （！x.load（std：：memory_order_seq_cst））

;

if （y.load（std：：memory_order_seq_cst）） {

++z;

}

}

void read_y_then_x（）

{

while （！y.load（std：：memory_order_seq_cst））

;

if （x.load（std：：memory_order_seq_cst）） {

++z;

}

}

int main（）

{

std：：thread a（write_x）;

std：：thread b（write_y）;

std：：thread c（read_x_then_y）;

std：：thread d（read_y_then_x）;

a.join（）; b.join（）; c.join（）; d.join（）;

assert（z.load（） ！= 0）; // will never happen

}

2.7 Relationship with volatile

人的一生總是充滿了疑惑。

可能你會(huì)思考？volatile關(guān)鍵字能夠防止指令被編譯器優(yōu)化，那它能提供線程間（inter-thread）同步語(yǔ)義嗎？答案是：不能?。?！

盡管volatile能夠防止單個(gè)線程內(nèi)對(duì)volatile變量進(jìn)行reorder，但多個(gè)線程同時(shí)訪問(wèn)同一個(gè)volatile變量，線程間是完全不提供同步保證。

而且，volatile不提供原子性！

并發(fā)的讀寫(xiě)volatile變量是會(huì)產(chǎn)生數(shù)據(jù)競(jìng)爭(zhēng)的，同時(shí)non volatile操作可以在volatile操作附近自由地reorder。

看一個(gè)例子，執(zhí)行下面的并發(fā)程序，不出意外的話，你不會(huì)得到一個(gè)為0的結(jié)果。

#include 《thread》

#include 《iostream》

volatile int count = 0;

void increase（） {

for （int i = 0; i 《 1000000; i++） {

count++;

}

}

void decrease（） {

for （int i = 0; i 《 1000000; i++） {

count--;

}

}

int main（） {

std：：thread t1（increase）;

std：：thread t2（decrease）;

t1.join（）;

t2.join（）;

std：：cout 《《 count 《《 std：：endl;

}

3. Reference

The C/C++ Memory Model： Overview and Formalization

知乎專欄：如何理解C++的6種memory order

理解 C++ 的 Memory Order

理解弱內(nèi)存順序模型

當(dāng)我們?cè)谡務(wù)?memory order 的時(shí)候，我們?cè)谡務(wù)撌裁?/p>

https://en.cppreference.com/w/cpp/atomic/memory_order

Youtube： Atomic’s memory orders， what for？ - Frank Birbacher ［ACCU 2017］

C++11中的內(nèi)存模型下篇 - C++11支持的幾種內(nèi)存模型

memory ordering， Gavin’s blog

c++11 內(nèi)存模型解讀

memory barriers in c， MariaDB FOUNDATION， pdf

C++ memory order循序漸進(jìn)

Memory Models for C/C++ Programers

Memory Consistency Models： A Tutorial
責(zé)任編輯:pj