現(xiàn)代的CPU比內(nèi)存系統(tǒng)快很多，2006年的cpu可以在一納秒之內(nèi)執(zhí)行10條指令，但是需要多個(gè)十納秒去從內(nèi)存讀取一個(gè)數(shù)據(jù)，這里面產(chǎn)生了至少兩個(gè)數(shù)量級(jí)的速度差距。在這樣的問(wèn)題下，cpu cache應(yīng)運(yùn)而生。

[[323140]]

cache處于cpu與內(nèi)存之間，讀寫速度比內(nèi)存快很多，但也比較昂貴。

cache是以cache line為基本單位來(lái)進(jìn)行讀寫的，cache line的大小是2的冪次，從16字節(jié)到256字節(jié)不等。

上圖就是一個(gè)cpu cache的架構(gòu)示意圖，總共有32個(gè)cache line，每個(gè)cache line是256字節(jié)。cacheline的起始地址低8位都是0，使用內(nèi)存地址的9-12位數(shù)據(jù)來(lái)進(jìn)行hash。

當(dāng)cpu在cache里尋找數(shù)據(jù)時(shí)，如果數(shù)據(jù)不存在，則會(huì)產(chǎn)生一個(gè)cache miss，這時(shí)候cpu需要等待數(shù)據(jù)從內(nèi)存讀回，這需要耗費(fèi)很長(zhǎng)時(shí)間，但是因?yàn)樽x取之后會(huì)存儲(chǔ)到cache中，所以以后的讀取就會(huì)變得非常快。為了減少cache miss造成的性能損失，現(xiàn)代的cpu單核可以超線程，一個(gè)線程等待的時(shí)候，另一個(gè)線程就能執(zhí)行指令了。

為什么會(huì)有cache miss，一種是數(shù)據(jù)預(yù)熱，機(jī)器剛啟動(dòng)的時(shí)候，cache是沒(méi)有數(shù)據(jù)的，還有一種情況是cache不足，需要淘汰舊的數(shù)據(jù)。

我們用的最多的緩存一致性協(xié)議是MESI，四個(gè)字母分別表示modified, exclusive, shared, invalid，這是cache line的四種狀態(tài)，

modified：數(shù)據(jù)是被該cpu獨(dú)占的，其他cpu沒(méi)有存儲(chǔ)該數(shù)據(jù)。

exclusive：這個(gè)狀態(tài)跟modified很類似，只是該狀態(tài)下，cache的數(shù)據(jù)已經(jīng)同步到主存了，所以即使丟棄也無(wú)所謂。

shared：數(shù)據(jù)存在于多個(gè)cpu cache里，每個(gè)cpu對(duì)該數(shù)據(jù)只能讀，而不能簡(jiǎn)單地寫

invalid：該cache line是空的

Read：read消息會(huì)帶上cache line的物理內(nèi)存地址向其他cpu獲取數(shù)據(jù)

Read Response：如果其他cpu有這個(gè)cache line，并且處于modified，那么該cpu必須返回該消息，因?yàn)槠渌鹀pu的cache line和主存都沒(méi)有最新的數(shù)據(jù)

Invalidate：invalidate消息會(huì)帶上cache line的物理內(nèi)存地址，來(lái)讓其他cache把相應(yīng)的數(shù)據(jù)從cache line里去除掉

Invalidate Acknowledge：如果一個(gè)cpu收到Invalidate消息，那么它必須在刪除數(shù)據(jù)之后返回該消息

Read Invalidate：該消息是Read和Invalidate的組合，所以它需要一個(gè)Read Response和多個(gè)Invalidate Acknowledge

Writeback：modified狀態(tài)的cache line寫到主存，可以用來(lái)騰出空間給其他數(shù)據(jù)

我們現(xiàn)在來(lái)看一下MESI各種狀態(tài)之間的遷移：

a) cpu把cacheline 回寫到內(nèi)存，此時(shí)該cpu對(duì)這個(gè)cacheline還是有獨(dú)占權(quán)

b) cacheline 被cpu修改，該操作不需要cpu之間通信

c) cpu收到read invalidate之后，本地cacheline失效

d) cacheline 被本地cpu修改，需要和其他cpu通信，發(fā)出read invalidate 獲取最新的數(shù)據(jù)

e) cacheline 被本地cpu修改，需要向其他cpu發(fā)出invalidate請(qǐng)求

f) 其他cpu發(fā)來(lái)read請(qǐng)求

g) 其他cpu發(fā)來(lái)read請(qǐng)求

h) cpu意識(shí)到它馬上要寫數(shù)據(jù)到cacheline，所以提前發(fā)出invalidate消息給其他cpu

i) 其他cpu發(fā)來(lái)read invalidate

j) cpu在寫數(shù)據(jù)之前發(fā)出read invalidate消息給其他cpu，之后就處于e狀態(tài)，該狀態(tài)很快就可能變成m狀態(tài)

k) cpu發(fā)出read請(qǐng)求

l) 收到invalidate請(qǐng)求

雖然MESI協(xié)議能保證讀寫內(nèi)存的高性能，但還是有點(diǎn)問(wèn)題：

當(dāng)cpu0要寫數(shù)據(jù)到本地cache的時(shí)候，如果不是M或者E狀態(tài)，需要發(fā)送一個(gè)invalidate消息給cpu1，只有收到cpu1的acknowledgement才能寫數(shù)據(jù)到cache中，在這個(gè)過(guò)程中cpu0需要等待，這大大影響了性能。一種解決辦法是在cpu和cache之間引入store buffer，當(dāng)發(fā)出invalidate之后直接把數(shù)據(jù)寫入store buffer。當(dāng)收到acknowledgement之后可以把store buffer中的數(shù)據(jù)寫入cache。現(xiàn)在的架構(gòu)圖是這樣的：

現(xiàn)在這樣的架構(gòu)引入了復(fù)雜性，看下面的例子：

cpu0cache里面有個(gè)b，初值為0，cpu1cache有個(gè)a，初值為0，現(xiàn)在cpu0運(yùn)行代碼

a=1; 
b=a+1; 
assert(b==2) 

cpu0執(zhí)行a=1的時(shí)候發(fā)現(xiàn)本地cache沒(méi)有a，所以發(fā)送read invalidate給cpu1，然后把a(bǔ)=1寫入store buffer

cpu1收到read invalidate之后把a(bǔ)傳給cpu0并且本地cacheline置為無(wú)效

cpu0開(kāi)始執(zhí)行b=a+1

cpu0收到cpu1的read response，發(fā)現(xiàn)a=0

cpu0執(zhí)行a+1，得到1賦給b

cpu0執(zhí)行最后一句，失敗

這里關(guān)鍵的問(wèn)題是cpu會(huì)把自己的操作看做是全局的內(nèi)存操作，但其實(shí)操作storebuffer沒(méi)有操作到主存，所以我們需要在查cache的時(shí)候還得查一下store buffer,這種技術(shù)叫做store forwarding.

現(xiàn)在的架構(gòu)是這樣的：

上面是store buffer在一個(gè)cpu中碰到的問(wèn)題，在多個(gè)cpu并發(fā)的過(guò)程中也可能存在問(wèn)題，看下例：

void foo(void) 
{ 
a = 1; 
b = 1; 
} 
void bar(void) 
{ 
while (b == 0) continue; 
assert(a == 1); 
} 

同樣的，cpu0cache里面有個(gè)b，初值為0，cpu1cache有個(gè)a，初值為0，現(xiàn)在cpu0運(yùn)行foo, cpu1運(yùn)行bar

cpu0 發(fā)現(xiàn)a不在本地cache，發(fā)送read invalidate去cpu1，并在store buffer中把a(bǔ)置為1

cpu1 執(zhí)行while (b == 0)發(fā)現(xiàn)b不在本地內(nèi)存，發(fā)送read消息去cpu0

cpu0 在本地cache置b為1

cpu0收到read消息，把cache中的b傳送給cpu1，并把本地狀態(tài)置為s

cpu1發(fā)現(xiàn)b為1，退出循環(huán)，因?yàn)檫@時(shí)候cpu1本地cache中a還是1，所以失敗

cpu1收到read invalidate,把a(bǔ)傳輸給cpu0，并置本地cache為invalidate但是太晚了

cpu0收到cpu1關(guān)于a的read response，把本地的store buffer移到cache中

第一個(gè)問(wèn)題硬件工程署可以解決，但是第二個(gè)很難處理，因?yàn)橛布o(wú)法知道變量之間的依賴關(guān)系，硬件工程師設(shè)計(jì)了memory barrier(內(nèi)存屏障)，軟件可以使用這個(gè)工具來(lái)提示cpu變量之間的關(guān)系。新的代碼如下：

void foo(void) 
{ 
a = 1; 
smp_mb(); 
b = 1; 
} 
void bar(void) 
{ 
while (b == 0) continue; 
assert(a == 1); 
} 

內(nèi)存屏障smp_mb()提示cpu在進(jìn)行smp_mb之后的存儲(chǔ)的時(shí)候，會(huì)先把store buffer里的數(shù)據(jù)刷新到cache中。有兩種方式，1：cpu會(huì)等到store buffer清空之后再處理其他指令，或者2：之后的所有寫操作都不寫到cache，而是寫到store buffer中，直到smp_mb之前的store buffer中的數(shù)據(jù)刷新到cache中。

上例中的執(zhí)行效果如下：

cpu0執(zhí)行 a=1,發(fā)現(xiàn)a不在本地cache中，進(jìn)而把a(bǔ)=1寫入store buffer，并發(fā)出read invalidate消息給cpu1

cpu1執(zhí)行while (b == 0)，發(fā)現(xiàn)b不在本地cache中，進(jìn)而發(fā)出read消息給cpu0

cpu0執(zhí)行smp_mb，把store buffer中的a標(biāo)記一下

cpu0執(zhí)行b=1 發(fā)現(xiàn)狀態(tài)為獨(dú)占，所以可以直接寫，但是因?yàn)閟tore buffer中有標(biāo)記過(guò)的值，所以把b=1寫入store buffer，但是不標(biāo)記

cpu0收到read消息，把cache中b的數(shù)據(jù)0發(fā)給cpu1，并把cacheline置為s

cpu1收到b=0，陷入循環(huán)中

cpu0收到read invalidate消息，進(jìn)而把a(bǔ)=1從store buffer寫入cache，這時(shí)候可以把store buffer中的b=1寫入cache，但是發(fā)現(xiàn)這時(shí)候cache中的b屬于s狀態(tài)，所以發(fā)出invalidate消息給cpu1

cpu1收到invalidate消息之后把b設(shè)為1

cpu0收到invalidate ack之后把b的值1寫入cache

cpu1要讀取b的值，發(fā)出read消息給cpu0,

cpu0把b=1發(fā)給cpu1

cpu1收到b的值1，退出循環(huán)

cpu1發(fā)現(xiàn)a無(wú)效，發(fā)出read消息給cpu0

cpu0把a(bǔ)的值1發(fā)送給cpu1，并且把a(bǔ)置為s

cpu1得到a=1，成功

但是內(nèi)存屏障的處理方法有個(gè)問(wèn)題，那就是store buffer空間是有限的，如果store buffer中的空間被smp_mb之后的存儲(chǔ)塞滿，cpu還是得等待invalidate消息返回才能繼續(xù)處理。解決這種問(wèn)題的思路是讓invalidate ack能更早得返回，一種辦法是提供一種放置invalidate message的隊(duì)列，稱為invalidate queue. cpu可以在收到invalidate之后馬上返回invalidate ack，而不是在把本地cache invalidate之后，并把invalidate message放置到invalide queue，以待之后處理。

但是這種方法會(huì)使得我們之前的內(nèi)存屏障的例子也失效，主要是因?yàn)樵赾pu1收到cpu0關(guān)于a的invalidate消息之后直接ack，而沒(méi)有真正invalidate cache，導(dǎo)致退出循環(huán)之后發(fā)現(xiàn)a是有效的，執(zhí)行assert(a==1)失敗

void foo(void) 
{ 
a = 1; 
smp_mb(); 
b = 1; 
} 
void bar(void) 
{ 
while (b == 0) continue; 
smp_mb(); 
                         
assert(a == 1); 
} 

在assert之前插入內(nèi)存屏障，作用是把invalidate queue標(biāo)記下，在讀取下面的數(shù)據(jù)的時(shí)候，譬如a的時(shí)候會(huì)先把invalidate queue中的消息都處理掉，這里的話會(huì)使得a失效而去cpu0獲取最新的數(shù)據(jù)。

進(jìn)而我們知道smp_mb有兩個(gè)作用，1，標(biāo)記store buffer，在處理之后的寫請(qǐng)求之前需要把store buffer中的數(shù)據(jù)apply到cache，2，標(biāo)記invalidate queue，在加載之后的數(shù)據(jù)之前把invalidate queue中的消息都處理掉

進(jìn)而我們?cè)儆^察上面的例子，我們發(fā)現(xiàn)，在foo中我們不需要處理invalidate queue，而在bar中，我們不需要處理store buffer，我們可以使用一種更弱的內(nèi)存屏障來(lái)修改上例讓我們程序的性能更高，smp_wmb寫屏障，只會(huì)標(biāo)記store buffer，smp_rmb讀屏障，只會(huì)標(biāo)記invalidate queue，代碼如下：

void foo(void) 
{ 
a = 1; 
smp_wmb(); 
b = 1; 
} 
void bar(void) 
{ 
while (b == 0) continue; 
smp_rmb(); 
assert(a == 1); 

本文基本是對(duì)http://www.puppetmastertrading.com/images/hwViewForSwHackers.pdf的理解與翻譯。

MESI緩存一致性協(xié)議，能保證緩存和內(nèi)存數(shù)據(jù)一致

volatile表示不使用寄存器的值，每次都從內(nèi)存讀(不包括緩存)

dma越過(guò)cpu修改內(nèi)存，會(huì)影響MESI

補(bǔ)充MESI：

緩存一致性協(xié)議給緩存行(通常為64字節(jié))定義了個(gè)狀態(tài)：獨(dú)占(exclusive)、共享(share)、修改(modified)、失效(invalid)，用來(lái)描述該緩存行是否被多處理器共享、是否修改。所以緩存一致性協(xié)議也稱MESI協(xié)議。

• 獨(dú)占(exclusive)：僅當(dāng)前處理器擁有該緩存行，并且沒(méi)有修改過(guò)，是最新的值。
• 共享(share)：有多個(gè)處理器擁有該緩存行，每個(gè)處理器都沒(méi)有修改過(guò)緩存，是最新的值。
• 修改(modified)：僅當(dāng)前處理器擁有該緩存行，并且緩存行被修改過(guò)了，一定時(shí)間內(nèi)會(huì)寫回主存，會(huì)寫成功狀態(tài)會(huì)變?yōu)镾。
• 失效(invalid)：緩存行被其他處理器修改過(guò)，該值不是最新的值，需要讀取主存上最新的值。
• 協(xié)議協(xié)作如下：
• 一個(gè)處于M狀態(tài)的緩存行，必須時(shí)刻監(jiān)聽(tīng)所有試圖讀取該緩存行對(duì)應(yīng)的主存地址的操作，如果監(jiān)聽(tīng)到，則必須在此操作執(zhí)行前把其緩存行中的數(shù)據(jù)寫回CPU。
• 一個(gè)處于S狀態(tài)的緩存行，必須時(shí)刻監(jiān)聽(tīng)使該緩存行無(wú)效或者獨(dú)享該緩存行的請(qǐng)求，如果監(jiān)聽(tīng)到，則必須把其緩存行狀態(tài)設(shè)置為I。
• 一個(gè)處于E狀態(tài)的緩存行，必須時(shí)刻監(jiān)聽(tīng)其他試圖讀取該緩存行對(duì)應(yīng)的主存地址的操作，如果監(jiān)聽(tīng)到，則必須把其緩存行狀態(tài)設(shè)置為S。
• 當(dāng)CPU需要讀取數(shù)據(jù)時(shí)，如果其緩存行的狀態(tài)是I的，則需要從內(nèi)存中讀取，并把自己狀態(tài)變成S，如果不是I，則可以直接讀取緩存中的值，但在此之前，必須要等待其他CPU的監(jiān)聽(tīng)結(jié)果，如其他CPU也有該數(shù)據(jù)的緩存且狀態(tài)是M，則需要等待其把緩存更新到內(nèi)存之后，再讀取。
• 當(dāng)CPU需要寫數(shù)據(jù)時(shí)，只有在其緩存行是M或者E的時(shí)候才能執(zhí)行，否則需要發(fā)出特殊的RFO指令(Read Or Ownership，這是一種總線事務(wù))，通知其他CPU置緩存無(wú)效(I)，這種情況下會(huì)性能開(kāi)銷是相對(duì)較大的。在寫入完成后，修改其緩存狀態(tài)為M。

另外MESI協(xié)議為了提高性能，引入了Store Buffe和Invalidate Queues，還是有可能會(huì)引起緩存不一致，還會(huì)再引入內(nèi)存屏障來(lái)確保一致性

存儲(chǔ)緩存(Store Buffe)

也就是常說(shuō)的寫緩存，當(dāng)處理器修改緩存時(shí)，把新值放到存儲(chǔ)緩存中，處理器就可以去干別的事了，把剩下的事交給存儲(chǔ)緩存。

失效隊(duì)列(Invalidate Queues)

處理失效的緩存也不是簡(jiǎn)單的，需要讀取主存。并且存儲(chǔ)緩存也不是無(wú)限大的，那么當(dāng)存儲(chǔ)緩存滿的時(shí)候，處理器還是要等待失效響應(yīng)的。為了解決上面兩個(gè)問(wèn)題，引進(jìn)了失效隊(duì)列(invalidate queue)。處理失效的工作如下：

• 收到失效消息時(shí)，放到失效隊(duì)列中去。
• 為了不讓處理器久等失效響應(yīng)，收到失效消息需要馬上回復(fù)失效響應(yīng)。
• 為了不頻繁阻塞處理器，不會(huì)馬上讀主存以及設(shè)置緩存為invlid，合適的時(shí)候再一塊處理失效隊(duì)列。

MESI和CAS關(guān)系

在x86架構(gòu)上，CAS被翻譯為”lock cmpxchg...“，當(dāng)兩個(gè)core同時(shí)執(zhí)行針對(duì)同一地址的CAS指令時(shí),其實(shí)他們是在試圖修改每個(gè)core自己持有的Cache line,

假設(shè)兩個(gè)core都持有相同地址對(duì)應(yīng)cacheline,且各自cacheline 狀態(tài)為S, 這時(shí)如果要想成功修改,就首先需要把S轉(zhuǎn)為E或者M(jìn), 則需要向其它c(diǎn)ore invalidate 這個(gè)地址的cacheline,則兩個(gè)core都會(huì)向ring bus發(fā)出 invalidate這個(gè)操作, 那么在ringbus上就會(huì)根據(jù)特定的設(shè)計(jì)協(xié)議仲裁是core0,還是core1能贏得這個(gè)invalidate, 勝者完成操作, 失敗者需要接受結(jié)果, invalidate自己對(duì)應(yīng)的cacheline,再讀取勝者修改后的值, 回到起點(diǎn).。

對(duì)于我們的CAS操作來(lái)說(shuō), 其實(shí)鎖并沒(méi)有消失,只是轉(zhuǎn)嫁到了ring bus的總線仲裁協(xié)議中. 而且大量的多核同時(shí)針對(duì)一個(gè)地址的CAS操作會(huì)引起反復(fù)的互相invalidate 同一cacheline, 造成pingpong效應(yīng), 同樣會(huì)降低性能(參考[9])。當(dāng)然如果真的有性能問(wèn)題，我覺(jué)得這可能會(huì)在ns級(jí)別體現(xiàn)了,一般的應(yīng)用程序中使用CAS應(yīng)該不會(huì)引起性能問(wèn)題。