586之前的CPU, 會通過LOCK鎖總線的形式來實作原子操作. 686開始則提供了存盤一致性(Cache coherence), 這是多處理的基礎, 也是原子操作的基礎.
1. 存盤的粒度
存盤的組織形式(粒度)是以CacheLine為單位的, 通常為64位元組甚至更高(早期也有32位元組的). 然后幾組CacheLine組成一個小的LRU(或者其他替換規則).
2. 協議
存盤一致性(CC)一般是通過MESI協議, 以及后續的變種協議, 例如Intel的MESIF協議和AMD的MOESI協議, 來實作的.
以MESI協議為例:
Modified: 獨占CacheLine, 已經修改了, 但是還未同步到主存
Exclusive: 獨占, 并且和主存一致
Shared : 共享的, 其他core也擁有該CacheLine, 并且與主存中一致
Invalid: 表示該CacheLine不可用
3. 通訊
有了協議, 那么就需要通訊來實作協議(存盤的狀態). 通訊有兩種, 一種是廣播/偵聽, 一種是目錄式.
廣播/偵聽顧名思義就是存盤狀態的變更, 會被廣播到其他core上面去, 進而去維護CacheLine的狀態. 很明顯這種方式會浪費大量的流量, 而且難以擴展, CPU核數多了, 總線就是明顯的瓶頸.
目錄式, 就是把改變通知給具體的core, 從而避免廣播. 但是考慮一種極端情況, 如果很多個core都在訪問同一個CacheLine, 那還是不能避免(事實上的)廣播. 所以, 多執行緒編程時, 共享同一個CacheLine不是一個好的選擇.
有了上面的東西, 現在我們來考慮原子操作的實作:
1. 原子的Load/Store
由于CPU對快取的管理是以CacheLine為單位的, 所以在一個CacheLine內load/store實際上都是原子的. Load和Store一個8位元組物件, 不可能高4位和低4位是分開操作的(從而搞成倆值).
但是光有這個實際上還不夠, CPU對CacheLine的修改不是立即寫到主存里面去, 所以其他Core看到的值就有可能是老的值, 所以這時候還需要fence來讀到最新的值; 至于寫, 那一定需要寫權限, 即M或者E狀態, 而這兩個權限里面都有最新的值(只是你剛才讀到的不一定是最新的, 所以有可能用老值覆寫了新值).
2. FetchAndAdd
這是比load和store稍微復雜的操作, 實際上是一個復合操作. 但是有了M和E狀態, 就很好理解了:
lock(CacheLine) v := load(obj) v += add store(obj, v) release(CacheLine)
x86里面是xadd指令.
3. CompareAndSwap
那么CAS, 也就可以猜出來:
lock(CacheLine)
v := load(obj)
if v != expected {
store(obj, new_value)
}
release(CacheLine)
x86里面是xchg
這里說的lock和release均表示對該CacheLine獨占和解出獨占的意思.
關于原子操作的原理, 鮮有資料表表示其具體怎么做的, 很有可能是過于偏向于硬體. 但是對MESI等協議的思考, 實際上還是能猜到CPU內部的實作(至少七八不離十). 好在找到兩個資料, 一個是<<并行多核體系結構基礎>>和<<從鯤鵬920了解現代服務器實作和參考>>. 其中鯤鵬920記憶體模型章節這么寫到:
原子指令在軟體上看來邏輯并不復雜，但在微架構上看，成本是很高的，如果我們把CPU 和記憶體都看做是總線上的一個個獨立的物體，有一個CPU要做CAS指令，這個CPU需要先從 記憶體中讀一個值，同時要在記憶體控制器上設定一個標志，保證其他CPU寫不進去，等它比 較完了，然后再決定寫一個值回去，才會讓其他CPU寫入，
不同微架構實作有不同方法對行為進行優化，在鯤鵬920上，原子指令的請求需要在 L3Cache上進行排隊，保證在原子操作的多個動作之間能維持原子指令要求的語意，這個 排隊本身也有成本，所以沒有原子需要就不要輕易用原子變數，這其實是有成本的，
并行多核體系結構這么寫到:
幸運的是, 快取一致性協議提供了原子性被保障的基礎. 舉例來說, 當遇到一個原子指令時, 這個協議知道需要保證原子性. 他首先獲得對存盤單元M的"獨家所有權" (通過將其他包含M的快取塊中的拷貝都置為無效). 當獲得獨家所有權之后, 這個協議會確保只有一個處理器能夠訪問這個塊, 而如果其他處理器在此時想要訪問的話就會經歷快取缺失, 接下來原子指令就可以執行. 在原子指令持續期間, 其他處理器不允許"偷走"這個塊. 距離來說, 如通另一個處理器要求讀或者寫這個塊, 這個塊就被"偷"了(如塊被清理, 塊的狀態被降級為無效). 在原子指令完成之前暴露塊會破壞指令的原子性, ......
參考:
1) 并行多核體系結構基礎
2) 從鯤鵬920了解現代服務器實作和應用
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/230133.html
標籤：C++
上一篇：二叉樹的最近公共祖先