我們知道了cpu緩存及緩存行的概念, 同時用一個例子說明了編寫單線程java代碼時應該注意的問題. 下面我們讨論更為複雜,
而且更符合現實情況的多核程式設計時将會碰到的問題. 這些問題更容易犯, 連j.u.c包作者doug lea大師的jdk代碼裡也存在這些問題.
mesi協定及rfo請求
有人說可以通過第2個核直接通路第1個核的緩存行. 這是可行的, 但這種方法不夠快. 跨核通路需要通過memory
controller(見上一篇的示意圖), 典型的情況是第2個核經常通路第1個核的這條資料, 那麼每次都有跨核的消耗. 更糟的情況是,
有可能第2個核與第1個核不在一個插槽内.況且memory controller的總線帶寬是有限的, 扛不住這麼多資料傳輸. 是以,
cpu設計者們更偏向于另一種辦法: 如果第2個核需要這份資料, 由第1個核直接把資料内容發過去, 資料隻需要傳一次。
那麼什麼時候會發生緩存行的傳輸呢? 答案很簡單: 當一個核需要讀取另外一個核的髒緩存行時發生. 但是前者怎麼判斷後者的緩存行已經被弄髒(寫)了呢?
m(修改, modified): 本地處理器已經修改緩存行, 即是髒行, 它的内容與記憶體中的内容不一樣. 并且此cache隻有本地一個拷貝(專有).
e(專有, exclusive): 緩存行内容和記憶體中的一樣, 而且其它處理器都沒有這行資料
s(共享, shared): 緩存行内容和記憶體中的一樣, 有可能其它處理器也存在此緩存行的拷貝
i(無效, invalid): 緩存行失效, 不能使用
初始 一開始時, 緩存行沒有加載任何資料, 是以它處于i狀态.
本地寫(local write)如果本地處理器寫資料至處于i狀态的緩存行, 則緩存行的狀态變成m.
本地讀(local read) 如果本地處理器讀取處于i狀态的緩存行, 很明顯此緩存沒有資料給它.
此時分兩種情況: (1)其它處理器的緩存裡也沒有此行資料, 則從記憶體加載資料到此緩存行後, 再将它設成e狀态, 表示隻有我一家有這條資料,
其它處理器都沒有 (2)其它處理器的緩存有此行資料, 則将此緩存行的狀态設為s狀态.
p.s.如果處于m狀态的緩存行, 再由本地處理器寫入/讀出, 狀态是不會改變的.
遠端讀(remote read) 假設我們有兩個處理器c1和c2.
如果c2需要讀另外一個處理器c1的緩存行内容, c1需要把它緩存行的内容通過記憶體控制器(memory controller)發送給c2,
c2接到後将相應的緩存行狀态設為s. 在設定之前, 記憶體也得從總線上得到這份資料并儲存.
遠端寫(remote write) 其實确切地說不是遠端寫, 而是c2得到c1的資料後, 不是為了讀,
而是為了寫. 也算是本地寫, 隻是c1也擁有這份資料的拷貝, 這該怎麼辦呢? c2将發出一個rfo(request for owner)請求,
它需要擁有這行資料的權限, 其它處理器的相應緩存行設為i, 除了它自已, 誰不能動這行資料. 這保證了資料的安全,
同時處理rfo請求以及設定i的過程将給寫操作帶來很大的性能消耗.
僞共享
我們從上節知道, 寫操作的代價很高, 特别當需要發送rfo消息時. 我們編寫程式時, 什麼時候會發生rfo請求呢? 有以下兩種:
1. 線程的工作從一個處理器移到另一個處理器, 它操作的所有緩存行都需要移到新的處理器上. 此後如果再寫緩存行, 則此緩存行在不同核上有多個拷貝, 需要發送rfo請求了.
2. 兩個不同的處理器确實都需要操作相同的緩存行
一個運作在處理器core 1上的線程想要更新變量x的值, 同時另外一個運作在處理器core 2上的線程想要更新變量y的值. 但是,
這兩個頻繁改動的變量都處于同一條緩存行. 兩個線程就會輪番發送rfo消息, 占得此緩存行的擁有權. 當core 1取得了擁有權開始更新x,
則core 2對應的緩存行需要設為i狀态. 當core 2取得了擁有權開始更新y, 則core 1對應的緩存行需要設為i狀态(失效态).
表面上x和y都是被獨立線程操作的, 而且兩操作之間也沒有任何關系.隻不過它們共享了一個緩存行, 但所有競争沖突都是來源于共享.
實驗及分析
引用martin的例子, 稍做修改,代碼如下:
代碼的邏輯是預設4個線程修改一數組不同元素的内容. 元素的類型是volatilelong,
隻有一個長整型成員value和6個沒用到的長整型成員. value設為volatile是為了讓value的修改所有線程都可見.
在一台westmere(xeon e5620 8core*2)機器上跑一下看
把以上代碼49行注釋掉, 看看結果:
兩個邏輯一模一樣的程式, 前者隻需要9秒, 後者跑了将近一分鐘, 這太不可思議了! 我們用僞共享(false
sharing)的理論來分析一下. 後面的那個程式longs數組的4個元素,由于volatilelong隻有1個長整型成員,
是以整個數組都将被加載至同一緩存行, 但有4個線程同時操作這條緩存行, 于是僞共享就悄悄地發生了. 讀者可以測試一下2,4,8,
16個線程分别操作時分别是什麼效果, 什麼樣的趨勢.
比較一下兩個版本的結果, 慢的版本:
快的版本:
慢的版本由于false sharing引發的l2緩存in事件達34085次, 而快版本的為0次.
總結
僞共享在多核程式設計中很容易發生, 而且比較隐蔽. 例如, 在jdk的linkedblockingqueue中,
存在指向隊列頭的引用head和指向隊列尾的引用last. 而這種隊列經常在異步程式設計中使有,這兩個引用的值經常的被不同的線程修改,
但它們卻很可能在同一個緩存行, 于是就産生了僞共享. 線程越多, 核越多,對性能産生的負面效果就越大.
某些java編譯器會将沒有使用到的補齊資料, 即示例代碼中的6個長整型在編譯時優化掉, 可以在程式中加入一些代碼防止被編譯優化。
另外, 由于java的gc問題. 資料在記憶體和對應的cpu緩存行的位置有可能發生變化, 是以在使用pad的時候應該注意gc的影響.
2012年4月19日更新:
發現netty和grizzly的代碼中的linkedtransferqueue中都使用了
paddedatomicreference<qnode>來代替原來的node, 使用了補齊的辦法解決了隊列僞共享的問題.
不知道是不是jsr-166的人開發的, 看來他們早就意識到這個問題了. 但是從doug lea jsr-166的cvs看不到這個變化,
不知道究竟是誰改的? 他們的repository到底是在哪?
2012年5月19日更新:
為了差別cache coherence和cache consistency兩個概念, 不讓讀者混淆, 這裡把cache coherence改翻譯成緩存相幹性.