重溫一下 CAS 操作的偽碼
<code>bool compare_and_swap (int *accum, int *dest, int newval)
{
if ( *accum == *dest ) {
*dest = newval;
return true;
}
return false;
}/<code>
其對應的彙編指令是 cmpxchg, 這是一條原子操作指令, 也就是說CPU 會保證這條指令執行的原子性, 亦即,在特定的一個時間點,當多個cpu core 同時執行這條指令(參數相同),只會有一個core 成功的執行swap的操作.
那麼不由得激起了開發者的好奇心, CPU到底是如何保證這個原子性, 以及其底層實現會給軟件開發帶來什麼樣的好處,又有什麼樣的缺點. 本文就試圖從這個角度進行嘗試性的解讀.
486,Pentium, 時代
根據X86開發手冊第三冊 8.1.2 章節的說法, 在486以及pentium 處理器會顯式的向系統總線(也許是在3級緩存通信總線,細節沒有公開)發出Lock# 信號從而獲取對應Cache line的獨佔權.
具體的實現從來沒有公開過, 不過下面這張圖做了一個非官方的詮釋, 引自Jeremy.Jones 教案
從這張圖可以看出 當core試圖獲取cache line的訪問權(讀/寫), 該core需要向bus發出一個鎖信號,bus 仲裁器將會以round robin(無優先級輪流)算法選取某個core獲取訪問權. 每次也只允許一個core獲取這個cacheline, 也就是獨佔, 可以讀可以寫,
非常明顯的是這種方式非常低效, 首先讀寫的要求沒有區分開來, 讀的一致性要求要弱於寫.一次只有一個core可以訪問cacheline,而其它core則需要等待. 時延高.(尤其大大提高了讀操作的時延)
P6以後時代
根據開發者手冊 8.1.4的描述在p6以後的x86處理器中, 原子操作(例如cmpxchg)不再發出任何lock信號, 一切都由 Cache 一致性協議來完成.
首先說一下我們要討論的多核處理器的緩存結構
目前的結構每個core都會持有自己的私有的L1/L2 Cache, 但是 L3 cache是所有core共有的. 那麼就存在一個cache一致性的問題, 由公開資料可以知道, X86 採用的是改進型的MESI協議 MESIF, 主要是添加了一個 Forwarding的狀態, 簡化有多share節點狀態下 對read request的處理. 每個core都掛在一個或數個cache ring bus只上. 每個core都有一個cbox(bus agent)負責監聽其它core對cache的操作行為, 從而根據協議採取對應的行動.
Modified(M): 表示這個cacheline已經被修改,但是還未寫回主存(cache中數據與主存中數據不一致!所有其它core對這個cacheline的讀操作必須在該cacheline 寫回主存後, 寫回主存後,狀態變換到share
Exclusive(E): 表示這個cacheline 目前是獨有的且與主存一致,可以轉換到shared 或者M,重點是可以轉換到M,也就意味著可以對其修改!
Shared(S):表示這個cacheline 在其它core的cache中也存在, 目前也與主存一致, 隨時會被invalidate.
Invalid(I): 表示這個cacheline 目前不可用
這個圖的含義就是當一個core持有一個cacheline的狀態為Y時,其它core對應的cacheline應該處於狀態X, 比如地址 0x00010000 對應的cacheline在core0上為狀態M, 則其它所有的core對應於0x00010000的cacheline都必須為I , 0x00010000 對應的cacheline在core0上為狀態S, 則其它所有的core對應於0x00010000的cacheline 可以是S或者I ,
MESIF 就是對MESI做了一個優化. 大家設想一下, 如果現在一個cacheline 是S狀態, 在多個core中有同一copy, 那麼現在有一個新的core需要讀取該cacheline, 應該由那個core來應答. 如果每個持有該cacheline的core都來應答就會造成冗餘的數據傳輸, 所以對於在系統中有多個copy的S狀態的cacheline中,必須選取一個轉換為F, 只有F狀態的負責應答. 通常是最後持有該copy的轉換為F.
說了這些背景知識之後,再回到我們的CAS指令.
當兩個core同時執行針對同一地址的CAS指令時,其實他們是在試圖修改每個core自己持有的Cache line, 假設兩個core都持有相同地址對應cacheline,且各自cacheline 狀態為S, 這時如果要想成功修改,就首先需要把S轉為E或者M, 則需要向其它core invalidate 這個地址的cacheline,則兩個core都會向ring bus 發出 invalidate這個操作, 那麼在ringbus上就會根據特定的設計協議仲裁是core0,還是core1能贏得這個invalidate, 勝者完成操作, 失敗者需要接受結果, invalidate自己對應的cacheline,再讀取勝者修改後的值, 回到起點.
到這裡, 我們可以發現MESIF協議大大降低了讀操作的時延,沒有讓寫操作更慢,同時保持了一致性! 那麼對於我們的CAS操作來說, 其實鎖並沒有消失,只是轉嫁到了ring bus的總線仲裁協議中. 而且大量的多核同時針對一個地址的CAS操作會引起反覆的互相invalidate 同一cacheline, 造成pingpong效應, 同樣會降低性能. 只能說 基於CAS的操作仍然是不能濫用,不到萬不得已不用,通常情況下還是使用數據地址範圍分離模式更好.
最後, 更進一步 ring bus的協議又是什麼? x86這方面的公開信息非常罕見. 唯一可以推斷的是 這個協議會保證公平性, 在invalidate的競爭中不會總是一個core贏, 從而保證不會有starving core. 在power4/5 的設計中有一篇論文涉及到power具體細節, 大家可以參考
閱讀更多 餘生做酒長醉不憂 的文章
