smp cache line并發(fā)訪問

blake326

smp比如8核，比如我現(xiàn)在有一個(gè)數(shù)組，a[8] = {0}; 地址是0xd000000;這樣a[0]  ~ a[7]都是在同一個(gè)cache line中的, 并且每個(gè)cpu對(duì)應(yīng)的cacheline都是share狀態(tài)的。那么考慮下面并發(fā)場(chǎng)景：
cpu0 寫 a[0] = 0;
cpu1 寫 a[1] = 1;
cpu2 寫 a[2] = 2;
...
cpu7 寫 a[7] = 7;
結(jié)果是：
cpu0， 把cache line寫成了0，。。。， 然后發(fā)出一個(gè)inv 廣播到其他cpu
cpu1， 把cache line寫成了。1.。。， 然后發(fā)出一個(gè)inv 廣播到其他cpu
。。。

問題是：
1. 假設(shè)同時(shí)發(fā)生的，最終cache line的值是多少？
2. 某個(gè)cpu 寫完自己的cache line，發(fā)出去一個(gè)inv 廣播，然后又收到一個(gè)inv 事件，那么這個(gè)事件如何處理呢？
3. 這種代碼是不是無法保證cache line等于 0,1,2,3,4,5,6,7

chishanmingshen

回復(fù) 1# blake326

通過內(nèi)存中轉(zhuǎn)。比如：給a[1]賦值后，cpu0和cpu1的cache line已經(jīng)都一樣了。
而且，我覺得你這個(gè)case，8次操作，僅在第一次操作會(huì)發(fā)一次inv，并不是8次。

blake326

回復(fù) 2# chishanmingshen


    cpu0  寫完 a[0] = 0, 會(huì)發(fā)一個(gè)inv事件到其他cpu，其他cpu會(huì)inv 相應(yīng)的cache line，這樣就會(huì)感知到cache變化，但是假設(shè)多個(gè)cpu同時(shí)寫的話，不能保證這個(gè)順序了。

參考：
http://www.72891.cn/thread-3593865-1-1.html

chishanmingshen

回復(fù) 3# blake326


   我覺得你這個(gè)問題跟亂序不大涉及。
   可能8次寫是亂序的，但是總有一個(gè)cpu先讓自己的cacheline 從S到M，這樣其他的只能讀內(nèi)存了。

   所以最終結(jié)果是ok的，雖然損耗時(shí)間。

arm-linux-gcc

今天面試剛好被問到了這個(gè)問題
最終各個(gè)core的inner cache都會(huì)是invalid
outter cache最終會(huì)是0 1 2 3 ... 7

這種用法性能低下，最好用per-cpu，以達(dá)到避免競(jìng)爭(zhēng)同一個(gè)line的目的

wth0722

回復(fù) 5# arm-linux-gcc

為什麼outter cache最終會(huì)是0 1 2 3 ... 7 ?

我個(gè)人認(rèn)知如下，如有錯(cuò)幫忙釘正

第一個(gè)搶到cache的人會(huì)去更新 & invalid

第二搶到cache的，會(huì)發(fā)現(xiàn)該cache line已經(jīng)invalid (也就是所謂的write miss)

所以他就寫到記憶體，並在去cache上找一個(gè)cache line存放 (他不一定上一個(gè)cache line位置)

第二個(gè)寫完時(shí)，他又去下invalid

第三個(gè)搶到cache的，就會(huì)跟第二個(gè)一樣

以後以此類推


   

arm-linux-gcc

以outter include inner這種情況來說：因?yàn)閍rm cortex-a15就是這種情況
core 0寫了inner line，會(huì)使得core 1的相應(yīng)inner line變?yōu)閕nvalid，同時(shí)core 0的這次寫會(huì)同步到outter上
core 1寫自己的inner line時(shí)會(huì)發(fā)現(xiàn)沒有命中，于是就會(huì)去outter找有沒有能夠命中的line，于是發(fā)現(xiàn)outter中有能夠命中的，于是會(huì)寫outter，同時(shí)也使得core 0的inner變?yōu)閕nvalid

cortex-a9則是可以配置成exclusive或inclusive的
exclusive時(shí)應(yīng)該就最終在outter和inner中都沒有能夠命中的

blake326

回復(fù) 7# arm-linux-gcc


core 0寫了inner line，會(huì)使得core 1的相應(yīng)inner line變?yōu)閕nvalid，同時(shí)core 0的這次寫會(huì)同步到outter上


這個(gè)順序是如何保證的呢？
core1 變成invalid是因?yàn)闀?huì)收到core0的inv request。但是在core1收到inv request之前的話，core1就開始寫cache怎么辦？

從這個(gè)帖子里http://www.72891.cn/thread-3593865-1-1.html 來說，core0寫完cache之后，應(yīng)該會(huì)發(fā)出inval request到其他core，并且會(huì)接受其他core 的inval 成功的reply。整個(gè)邏輯還是搞不清楚現(xiàn)在。



   

blake326

我現(xiàn)在懷疑這種并發(fā)訪問可能會(huì)發(fā)生只有cpu2成功寫入的結(jié)果，例如： 0 0 2 0 0 0 0 0


www.72891.cn/forum.php?mod=viewthread&tid=1972593
這個(gè)里面講的 Figure 2. Data Destruction by Dirty Cache Lines 問題，感覺有點(diǎn)類似。

blake326

參考cache一致性的一個(gè)文檔：
http://www.72891.cn/thread-4070325-1-1.html

基本的mesi協(xié)議中，cache存在四種狀態(tài)e，s，m，i
i invalid， 表示該數(shù)據(jù)沒有對(duì)應(yīng)cache line
e excluisve，表示該數(shù)據(jù)有效，并且只存在本cpu的cache line中。其他cpu沒有cache該數(shù)據(jù)。
m modify, 表示該數(shù)據(jù)有效，但是與存儲(chǔ)器中的不一致，并且只存在本cpu的cache line中。其他cpu沒有cache該數(shù)據(jù)。
s share, 表示該數(shù)據(jù)有效，并且多個(gè)cpu都有該數(shù)據(jù)的cache line并且他們的狀態(tài)都是share。

然后，當(dāng)CPU對(duì)一段存儲(chǔ)器進(jìn)行寫操作時(shí)，如果這些數(shù)據(jù)在本地Cache中命中時(shí)，其狀態(tài)可能為E、S、M或者O。
     狀態(tài)為E或者M(jìn)時(shí)，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M。
     狀態(tài)為S時(shí)，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時(shí)其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S或者O遷移到I(Probe Write Hit)。
     狀態(tài)為O時(shí)，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時(shí)其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S遷移到I(Probe Write Hit)。


這里，我們不管狀態(tài)o（owner), 其實(shí)我現(xiàn)在的問題就是：
     狀態(tài)為S時(shí)，數(shù)據(jù)將直接寫入到Cache中，并將狀態(tài)改為M，同時(shí)其他CPU保存該數(shù)據(jù)副本的Cache行狀態(tài)將從S或者O遷移到I(Probe Write Hit)。這個(gè)操作是不是原子的？

假設(shè)某個(gè)時(shí)間點(diǎn)，所有cpu該數(shù)據(jù)都是cache share的。那么這時(shí)：
cpu0, 寫了 0 0 0 0 0 0 0
cpu1, 寫了 0 1 0 0 0 0 0
cpu2，寫了 0 0 2 0 0 0 0


如果，該操作時(shí)原子的話，那么這種并發(fā)疑問就沒有了，結(jié)果勢(shì)必會(huì)使cache line變成, 0 1 2 3 4 5 6 7。而且怎樣保證原子性的呢？