內存一致性模型

在計算機科學中, 當然只有 兩件難事 [1] : 緩存失效、命名和漏掉一個錯誤。但是在計算機科學的高草叢中還隱藏着另一個難題: 按順序看事物。無論是 排序 [2] 、 亂序 [3] 還是 發推文 [4] , 按順序看事物都是一個歷史悠久的挑戰。

一個常見的排序挑戰是內存一致性, 即定義並行線程如何觀察其共享內存狀態的問題。關於內存一致性有許多資源, 但大多數要麼是 幻燈片 [5] (比如 我的 [6] !) 要麼是 密集的專著 [7] 。我的目標是製作一個入門讀物, 並解釋爲什麼內存一致性是多核系統的一個問題。至於細節, 您當然應該參考這些其他優秀的資源。

使線程達成一致

一致性模型涉及多個線程 (或工作者、節點、副本等) 如何看待世界。考慮這個簡單的程序, 運行兩個線程, 其中 A 和 B 最初都是 0:

爲了理解這個程序可能輸出什麼, 我們應該思考它的事件可能發生的順序。直觀地說, 這個程序可以按以下兩種明顯的順序運行:

還有一些不太明顯的順序, 其中指令是相互交錯的:

不應該發生的事情

直觀上, 這個程序不應該打印 00。爲了在 (2) 中打印 0, 我們必須在 (3) 將 1 寫入 B 之前打印 B。我們可以用一條邊來圖示表示:

從操作 x 到操作 y 的一條邊表示, 爲了獲得我們感興趣的行爲, x 必須在 y 之前發生。同樣, 爲了在 (4) 中打印 0, 那次打印必須在 (1) 將 1 寫入 A 之前發生, 所以讓我們在圖中添加這一點:

最後, 當然, 每個線程的事件應該按順序發生——(1)在 (2) 之前,(3)在 (4) 之前——因爲這是我們對命令式程序的期望。所以讓我們也添加這些邊:

但現在我們遇到了一個問題。

如果我們從 (1) 開始, 並沿着邊緣前進——到 (2), 然後(3), 然後(4), 然後......(1) 再次! 記住, 這些邊緣表示哪些事件必須在其他事件之前發生。所以如果我們從 (1) 開始, 最終又回到 (1), 圖表明(1) 必須在自身之前發生! 除非物理學有了非常令人擔憂的進展, 否則這是不可能的。

由於這種執行需要扭曲時間, 我們可以得出結論, 這個程序無法打印 "00"。可以把它看作是一個矛盾證明: 假設這個程序可以打印 "00"。那麼我們剛纔展示的所有順序規則都必須成立。但這些規則導致了矛盾 (事件(1) 發生在自身之前)。所以這個假設是錯誤的。

順序一致性: 並行的直觀模型

架構師和編程語言設計者認爲, 我們剛剛探討的規則對程序員來說是直觀的。其思想是, 多個並行運行的線程正在操作一個單一的主內存, 因此一切都必須按順序進行。沒有 "兩個事件可以同時發生" 的概念, 因爲它們都在訪問一個單一的主內存。

請注意, 這條規則沒有說明事件發生的順序是什麼——只是它們按某種順序發生。這種直觀模型的另一部分是, 事件按程序順序發生: 單個線程中的事件按照編寫的順序發生。這正是程序員所期望的: 如果允許我的程序在檢查鑰匙是否已經轉動之前就發射導彈, 那麼各種各樣的糟糕情況就會發生。

這兩條規則——單一主內存和程序順序——共同定義了順序一致性。在 2013 年, 萊斯利 · 蘭伯特憑藉定義順序一致性等多項成就獲得了圖靈獎。

順序一致性是我們的第一個內存一致性模型的例子。內存一致性模型 (我們通常稱之爲 "內存模型") 定義了多線程在多處理器上的允許順序。例如, 對於上面的程序, 順序一致性禁止任何導致打印 "00" 的順序, 但允許一些打印 "01" 和 "11" 的順序。

內存一致性模型是硬件和軟件之間的一種契約。硬件承諾只以該模型允許的方式重新排序操作, 作爲回報, 軟件承認所有這些重新排序都是可能的, 並且需要加以考慮。

順序一致性的問題

思考順序一致性的一種好方法是將其視爲一個開關。在每個時間步驟中, 開關選擇一個線程運行, 並完全運行它的下一個事件。這種模型保留了順序一致性的規則: 事件正在訪問單一的主內存, 因此按順序發生; 並且通過始終運行所選線程的下一個事件, 每個線程的事件都按程序順序發生。

這種模型的問題在於它非常、非常慢。我們一次只能運行一條指令, 因此我們失去了擁有多個並行運行的線程的大部分好處。更糟糕的是, 我們必須等待每條指令完成, 然後才能開始下一條——在當前指令的影響對每個其他線程可見之前, 不能運行更多的指令。

一致性

有時, 等待是有道理的。考慮這種情況, 兩個線程都想寫入變量 A, 而另一個線程想讀取它:

如果我們放棄單一主內存的概念, 以允許 (1) 和(2)並行運行, 那麼事件 (3) 應該讀取哪個值就變得不清楚了。單一主內存保證總會有一個 "贏家": 每個變量的最後一次寫入。沒有這個保證, 在 (1) 和(2)都發生之後,(3)可能會看到 1 或 2, 這就令人困惑了。

我們稱這種保證爲一致性, 它表示對同一位置的所有寫入操作都以相同的順序被每個線程看到。它不規定實際的順序 (可以先發生(1) 或(2)), 但要求每個人都看到相同的 "贏家"。

放鬆的內存模型

除了一致性之外, 單一主內存通常是不必要的。再次考慮這個例子: 兩個線程並行運行 " 的中文翻譯如下:

有一個原因, 執行事件 (2)(從 B 讀取) 不需要等待事件 (1)(寫入 A) 完成。它們根本不會互相干擾, 因此應該允許並行運行。事件 (1) 特別緩慢, 因爲它是一次寫入操作。這意味着在單一內存視圖下, 我們不能運行 (2), 直到(1) 對每個其他線程都可見爲止。在現代 CPU 上, 由於緩存層次結構, 這是一個非常昂貴的操作:

兩個內核之間唯一共享的內存是在 L3 緩存處, 通常需要 90 多個週期才能訪問。

總存儲順序 (TSO)

與其等待寫入 (1) 變爲可見, 我們可以將其放入存儲緩衝區:

然後 (2) 可以在將 (1) 放入存儲緩衝區後立即開始, 而不是等待它到達 L3 緩存。由於存儲緩衝區位於內核上, 因此訪問它非常快。將來某個時候, 緩存層次結構將從存儲緩衝區中提取寫入, 並通過緩存傳播, 使其對其他線程可見。存儲緩衝區允許我們隱藏通常需要使寫入 (1) 對所有其他線程可見的寫入延遲。

存儲緩衝區很好, 因爲它保留了單線程行爲。例如, 考慮這個簡單的單線程程序:

爲了保留預期的單線程行爲, 讀取 (2) 需要看到 (1) 寫入的值。寫入 (1) 尚未進入內存 - 它位於內核 1 的存儲緩衝區中 - 因此如果讀取 (2) 只查看內存, 它將獲得舊值。但由於它運行在同一 CPU 上, 讀取可以直接檢查存儲緩衝區, 看到它包含對要讀取的位置的寫入, 並使用該值。因此, 即使使用存儲緩衝區, 此程序也能正確打印 "1"。

一種流行的允許使用存儲緩衝區的內存模型稱爲總存儲順序 (TSO)。TSO 大多保留與 SC 相同的保證, 除了允許使用存儲緩衝區。這些緩衝區隱藏了寫入延遲, 使執行 顯著加快 [8] 。

陷阱

存儲緩衝區聽起來像是一種很好的性能優化, 但有一個陷阱: TSO 允許 SC 不允許的行爲。換句話說, 在 TSO 硬件上運行的程序可能表現出程序員認爲令人驚訝的行爲。

讓我們再看一下上面的第一個示例, 但這次在帶有存儲緩衝區的機器上運行。首先, 我們執行 (1) 和(3), 它們都將數據放入存儲緩衝區, 而不是發送回主內存:

接下來, 我們在內核 1 上執行 (2), 它將讀取 B 的值。它首先檢查本地存儲緩衝區, 但那裏沒有 B 的值, 所以它從內存中讀取 B 並獲得值 0, 然後打印出來。最後, 我們在內核 2 上執行 (4), 它將讀取 A 的值。內核 2 的存儲緩衝區中沒有 A 的值, 所以它從內存中讀取並獲得值 0, 然後打印出來。在將來的某個不確定時間點, 緩存層次結構將清空兩個存儲緩衝區並將更改傳播到內存。

因此, 在 TSO 下, 此程序可以打印 "00"。正如我們上面所展示的, 這是 SC 明確禁止的行爲! 所以存儲緩衝區導致了程序員意料之外的行爲。

有任何架構願意採用一種違背程序員直覺的優化嗎? 是的! 事實證明, 幾乎每一種現代架構都包含一個存儲緩衝區, 因此其內存模型至少與 TSO 一樣弱。特別是, 古老的 x86 架構指定了一種內存模型, 非常接近 TSO。英特爾 (x86 的創始人) 和 AMD(x86-64 的創始人)都使用類似於上面的程序的示例 litmus 測試來指定他們的內存模型, 描述了小測試的可觀察結果。不幸的是, 用少量示例來指定一個複雜系統的行爲會留下歧義空間。劍橋大學的研究人員已經付出了大量努力來 形式化 x86-TSO[9] , 以明確 x86 TSO 實現的預期行爲 (特別是它與這種存儲緩衝區概念的不同之處)。

變得更弱

儘管 x86 放棄了順序一致性, 但就允許的瘋狂行爲而言, 它仍然是最規範的架構之一。大多數其他架構實現了更弱的內存模型, 這意味着它們允許更多反直覺的行爲。存在着這樣一個模型光譜—— SPARC[10] 架構允許程序員在運行時選擇三種不同的模型之一。

值得一提的是 ARM[11] 架構, 它可能驅動着你的智能手機。ARM 內存模型是出了名的未充分指定, 但本質上是一種弱排序形式, 提供了很少的保證。弱排序允許幾乎任何操作重新排序, 這使得各種硬件優化成爲可能, 但在最低層次編程時也是一場噩夢。

通過屏障逃脫

幸運的是, 所有現代架構都包含同步操作, 以在必要時控制其寬鬆的內存模型。最常見的這種操作是屏障 (或柵欄)。屏障指令強制在它之前的所有內存操作完成後, 才能開始在它之後的任何內存操作。也就是說, 屏障指令有效地在程序執行的特定點重新實施了順序一致性。

當然, 這正是我們通過引入存儲緩衝區和其他優化措施試圖避免的行爲。屏障是一個應該謹慎使用的逃生艙口: 它們可能需要數百個週期。在與模糊的內存模型定義相結合時, 正確使用它們也是極其微妙的。還有一些更易用的原語, 如 原子比較和交換 [12] , 但直接使用低級同步操作真的應該避免。一個真正的同步庫將爲你省去無數痛苦。

語言也需要內存模型

不僅硬件會重新排序內存操作——編譯器也經常這樣做。考慮這個程序:

X = 0
for i in range(100):
    X = 1
    print X

這個程序總是打印 100 個 1的字符串。當然, 循環內對 X的寫入是多餘的, 因爲沒有其他代碼改變 X的值。一個標準的 循環不變式代碼移動 [13] 編譯器通過將寫入移到循環外部來避免重複, 然後 死存儲消除 [14] 將刪除 X=0, 留下:

X = 1
for i in range(100):
    print X

這兩個程序在產生相同輸出時是完全等價的。2[15]

但是現在假設有另一個線程與我們的程序並行運行, 並對 X執行單個寫入:

在這兩個線程並行運行時, 第一個程序的行爲會發生變化: 現在, 它可以打印出像 11101111...這樣的字符串, 只要有一個零 (因爲它會在下一次迭代中重置 X=1)。第二個程序的行爲也會發生變化: 現在它可以打印出像 11100000...這樣的字符串, 一旦開始打印零就再也回不到一。

但是這兩種行爲變化並不適用於這兩個程序: 第一個程序永遠不會打印 11100000..., 第二個程序也永遠不會打印 11101111...。這意味着在並行存在的情況下, 編譯器優化不再產生等價程序! 這個例子所暗示的是, 在程序層面上也存在內存一致性的概念。編譯器優化在這裏實際上是一種重新排序: 它以可能對程序員可見或不可見的方式重新排列 (並刪除了一些) 內存訪問。因此, 爲了保持直觀的行爲, 編程語言需要自己的內存模型, 爲程序員提供關於他們的內存操作將如何重新排序的契約。這個想法在語言設計社區中變得越來越普遍。例如, 最新版本的 C++[16] 和 Java[17] 都有嚴格定義的內存模型來管理其操作。

計算機被破壞了!

所有這些重新排序看起來都瘋狂無稽, 人類根本無法全部理解。另一方面, 如果你反思自己的編程經驗, 內存一致性可能不是你經常遇到的問題 (除非你是一個低級內核黑客)。我如何調和這兩個極端?

訣竅在於, 我提到的每個例子都涉及到了 數據競爭。數據競爭是指對同一內存位置的兩次訪問, 其中至少有一次是寫操作, 並且沒有由同步操作引入的排序。如果沒有數據競爭, 那麼重新排序的行爲就無關緊要了, 因爲所有反直覺的重新排序都會被同步操作阻止。請注意, 這並不意味着無競爭程序是 確定性的: 不同線程可以在每次執行時贏得競爭。

事實上, 像 C++ 和 Java 這樣的語言提供了一種稱爲 無數據競爭程序的順序一致性 (或者流行的說法是 "SC for DRF") 的保證。這個保證說, 如果你的程序沒有數據競爭, 編譯器將插入所有必要的柵欄來保持順序一致性的外觀。但是, 如果你的程序 確實 有數據競爭, 那就無法保證了, 編譯器可以隨意處理。直覺上, 有數據競爭的程序很可能存在錯誤, 因此無需爲這種有錯誤的程序提供強有力的保證。如果一個程序有故意的數據競爭, 程序員可能知道自己在做什麼, 因此可以自己負責內存排序問題。

使用同步庫

現在你已經看到了所有這些混亂, 最重要的一課是你應該使用同步庫。它會爲你處理醜陋的重新排序問題。操作系統也經過了高度優化, 只在特定平臺上進行必要的同步。但現在你知道了這些庫和內核在處理微妙的同步問題時, 底層發生了什麼。

如果由於某些原因, 你想了解更多計算機架構強加給世界的各種可憎的內存模型, Morgan & Claypool 關於計算機架構的綜合講座有 一個很好的條目 [6] 關於內存一致性和一致性。

參考鏈接

  1. 兩件難事: http://martinfowler.com/bliki/TwoHardThings.html
  2. 排序: https://en.wikipedia.org/wiki/Bubblesort
  3. 亂序: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yatesshuffle
  4. 發推文: https://twitter.com/mathiasverraes/status/632260618599403520
  5. 幻燈片: http://15418.courses.cs.cmu.edu/spring2015/lecture/consistency
  6. 我的: http://courses.cs.washington.edu/courses/cse451/15au/notes/l17-mcm-slides.pdf
  7. 密集的專著: http://www.morganclaypool.com/doi/abs/10.2200/S00346ED1V01Y201104CAC016
  8. 顯著加快: https://courses.engr.illinois.edu/cs533/readinglist/2b.pdf
  9. 形式化 x86-TSO: https://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf
  10. SPARC: https://en.wikipedia.org/wiki/SPARC
  11. ARM: https://en.wikipedia.org/wiki/ARMarchitecture
  12. 原子比較和交換: https://en.wikipedia.org/wiki/Compare-and-swap
  13. 循環不變式代碼移動: https://en.wikipedia.org/wiki/Loop-invariantcodemotion
  14. 死存儲消除: https://en.wikipedia.org/wiki/Dead_store
  15. 2: #fn:compiler
  16. C++: https://cseweb.ucsd.edu/classes/fa13/cse160-a/Lectures/Lec07.pdf
  17. Java: http://www.cs.umd.edu/~pugh/java/memoryModel/
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/QLasWNEPxpzaCtegjjF4gQ

猜你喜歡