英文原文：Atomic operations and contention

　　本文是RAD Game Tools程序員Fabian “ryg” Giesen在其博客上發表的《Atomic operations and contention》一文的翻譯，經作者許可分享至InfoQ中文站。

　　上次（緩存一致性（Cache Coherency）入門），我們講了緩存一致性原理的基礎知識。今天，我們來談談基于一致的緩存構建一個有用的系統，需要哪些原語（primitive），以及它們是如何工作的。

　　原子性和原子操作

　　計算機操作最重要的構成單位是原子操作。這里的原子跟物理上說的原子沒有任何關系，而是起源于單詞atom，也就是希臘語“ἄτομος”（意為不可見的）。原子操作是一種不可再細分的操作，或者在系統中其他處理器看來是不可再分了。為了說明為什么原子操作很重要，考慮兩個處理器以幾乎相同的方式增加一個計數器，翻譯成C語言就是counter++，此時會發生什么：

　　在編譯好的代碼中，這樣一個操作分為：讀操作、寄存器自加，最后是一個寫操作（這里用類似C語言的偽代碼表示）。這三個步驟是獨立且按順序執行的（注意，對于x86來說，在更微觀的架構層次上這句話是正確的，但是在指令集架構的層次上，這三步看起來可以用一條“讀-修改-寫（read-modify-write）”指令完成：add [memory], value）。并且因為這些操作被分成多個指令周期來執行，所以在處理器一讀完counter（并且正開始把它加一）之后，把結果寫回去之前的空隙，處理器二也有可能去讀它。結果導致雖然兩個處理器都去增加這個計數器，但最終計數器的值只被加了1，其中一個加法運算“丟失”了。

　　原子操作恰恰就是用來防止這個問題的。如果我們使用一個原子的自加操作（說得更通用一點，原子加法）而不是常規的自加操作，執行指令的處理器會確保上面的三個步驟（讀、加、寫）像一條指令那樣完成，成為一個原子操作。在自加操作進行的時候，其他處理器無法插手。

　　原子操作是如何實現的

　　現在問題來了，原子操作是如何實現的呢？從理論上來說，最簡單的方法就是加鎖：在任何時間點上，只有一個處理器被允許執行一個原子操作。這個處理器在做原子操作之前，必須先獲得鎖，并且在操作完成后釋放它。這就是x86的LOCK前綴的作用（大致如此；這里我略去了細節）。這里，獲得鎖的操作意味著向總線發送一條消息，說“好吧，我要占用總線一會兒，大家都退后”（根據我們的目的，這就意味著“請不要再做內存操作了”）。然后發出請求的處理器要先等其他處理器完成它們正在進行的內存操作，之后才會得到確認。只有等到其他所有處理器都確認了以后，請求鎖的處理器才能開始處理內存操作。最后，一旦鎖被釋放，它還需要發送一條信息給總線上的其他處理器“我的工作完成，你們可以繼續向總線發送請求了”。

　　這種做法沒有問題，但是慢得無法想象。x86處理器依然保留了這種方式（或者類似做法），但只有當絕對緊急的情況下才會使用，也就是其他所有方法都失敗時的最后一招。x86指令集架構需要這么一個辦法來兜底，因為他們為了向后兼容，允許一些非常不可靠的操作，比如跨多個緩存段（cache line）的非對齊的原子操作。其他體系架構不允許對非對齊的數據進行原子操作，也不允許對“太大”的數據進行原子操作。這些限制確保了單個原子操作只會發生在單個緩存段中。并且一旦有了這個前提，我們討論起來就方便了：上次討論緩存一致性協議的時候我們看到，處理器之間對于同步內存的交互是以緩存段為單位的，所以原則上我們可以對單個緩存段做復雜的修改，然后通過刷新緩存段內容來把修改公之于眾。而且，MESI協議狀態機有兩個狀態（M和E，代表“已修改”和“獨占”）可以保證一個緩存段被處理器獨占——當一個緩存段被獨占時，其他處理器無法“窺探”。我們可以用這種機制來替代加鎖協議。

　　所以結論是這樣的：在一個使用MESI（或其衍生協議）的系統中，我們為了確保針對單個緩存段的操作具有原子性，只需要做到：一、保證在正確的地方擺放內存屏障（memory barrier），使內存操作和周邊的代碼保持正確的執行順序（見上一篇的文章），二、在讀任何東西前先獲得緩存段的所有權，三、只有當我們在整個原子操作期間一直握有獨占權，才可以把操作的結果回寫。這可以確保沒有其他處理器能看到只完成了一半的數據。要完成第三點有好幾種方法，比如我們可以開發出這樣的硬件，讓它可以在單個總線時鐘周期內完成某些原子操作；如果我們從一個時鐘周期開始的時候擁有某個緩存段的獨占權，那么直到這個周期結束，我們都可以修改數據。因為一個緩存段不可能在一個時鐘周期內“易手”，這樣的操作是很快的。根據總線協議，我們也可以玩點花樣，一致性請求可以立即響應，但如果我們正在做原子操作，真正的數據可以稍晚發送。最后，我們也可以選擇根本不作弊，而是直接實現二和三：把所有正在進行原子操作的緩存段“監控”起來，在原子操作完成前，如果有其他處理器請求這個緩存段，那我們的原子操作要從頭再來。因為這個原因，大多數RISC處理器都有load-link/store-conditional（LL/SC）指令。

　　順便說一下，從總線側（以及其他處理器通過總線）看來，正確對齊的原子操作和普通的內存更新沒有什么區別。所有的工作都在處理器內部完成，其他處理器既不知道也不關心某次內存更新到底是通過原子性的比較并交換（compare-and-swap）操作加上內存屏障來完成的，還是通過一次隨意寫指令完成的。

　　這一切聽起來簡單而美好，至少理論上是，但魔鬼往往藏于細節中。壞消息是，如果你是一個CPU架構師，這個過程的每個細節對你來說都關系重大；你對內存操作的內部實現需要避免“饑餓”（每個想獲取緩存段獨占權的處理器，最終都能獲得它，無論其他處理器在做什么），并且確保基本的原子操作的實現不能導致死鎖或活鎖。這聽起來是顯而易見的，但是對低層次的原語（比如原子操作、LL/SC指令）來說，這種保證不是與生俱來的。這東西實現起來挺困難的，并且CPU不但要保證有正確的實現，還要保證這種實現在“典型場景”下足夠快。當然，好消息是如果你工作的公司不是設計CPU的，以上這些都不關你的事。肯定已經有人通盤考慮過這些問題，并且他們背后有一支強大的驗證工程師隊伍拼命地在找這些實現的紕漏。

　　內存操作的開銷

　　回到軟件上，假設我們工作在一種典型的CPU體系結構上，并且在多核系統中運行代碼。在這種環境下，一次內存操作的開銷到底是什么？這將分為幾個部分：

　　執行。執行一次內存操作是有開銷的。現在假設我們只有一個處理器核在工作，并且正在運行單線程的代碼。即便如此，內存訪問還是很復雜。跟程序打交道的是虛擬地址，但是緩存和內存總線看到的卻是物理地址。所以任何內存操作首先做的就是把虛擬地址轉換成物理地址，這些結果本身會保存在頁表緩存中（Translation Lookaside Buffer，簡稱TLB）。如果你運氣不好，你所要訪問的虛擬地址當前可能并沒有映射到物理地址，并且它的內容需要從虛擬內存中載入。當這個情況發生時，操作系統會調度別的線程到當前的處理器上運行一段時間，因為從處理器看來，IO操作需要花很長時間。但是我們先假設這種情況不會發生。

　　所以，一切都很順利的話，內存操作到底能跑多快？看起來非常快。通常每個時鐘周期至少可以完成一次操作（讀/寫），很有可能更多。在3GHz單核處理器上，能高效利用緩存的代碼每秒鐘可以完成十億次數量級的內存操作。

　　內存屏障和原子性的“讀-修改-寫”操作。下一步，假設我們的代碼是多線程的，但我們還是在單核上運行它。這里我們就可以看到內存屏障和原子操作了，但是沒有來自其他處理器的干擾。我們簡單假設所有需要的緩存段已經被我們的處理器獨占了。在這種情況下，使用一次原子的整數加法來更新內存中的一個引用計數器，代價到底有多大？

　　好吧，這其實取決于處理器架構的實現。一般來說，對于帶有激進的內存重排序（memory reordering）策略的微架構處理器來說，使用內存屏障和原子操作的開銷更大，而只支持輕度重排序或者順序執行（in-order）內存操作的處理器則好一點。比如，在 Intel Atom處理器（順序執行）上使用LOCK INC [mem]來增加引用計數器值的開銷，本質上和使用常規INC [mem]指令是一樣的。而更復雜的內存操作，如“交換（exchange）”和“交換-加(exchange-add)”花費的時間是基礎的“讀-修改-寫”操作的兩到三倍。相反，在Intel和AMD支持亂序執行（out-of-order）的桌面處理器產品線中，一次原子自加操作的開銷是非原子版本的十到二十五倍，這些開銷是保證正確的執行順序所帶來的。再一次重申：這僅是在單核上運行的代碼，還沒有涉及處理器間通訊的開銷。為了使代碼在多核系統上安全地運行，還會在單個處理器內引入額外的開銷。

　　總線流量（bus traffic）和緩存一致性（cache coherency）。部分內存訪問操作實際上會無法命中緩存，從而只能從內存中加載。一旦有些緩存段因為長時間無人訪問而被丟棄，我們就要開始把它的內容回寫（write-back）到內存中。所有這些事件都會導致總線上（以及內存中）發生通訊流量。而總線和內存的帶寬是有限的，當容量飽和時，系統就變慢了。

　　而且，一旦我們在多核系統中運行多線程程序，總線上就會產生額外的通訊流量來保證緩存一致性，因為各個處理器都會不斷地同步它們所看到的內存內容。如果每個線程都在自己獨立的內存空間里工作，那么這種流量不會很大。如果每塊內存只會被一個處理器使用，那么根本無需同步，而且我們可以很容易獲取這些內存對應的緩存段的獨占權，不會引起其他處理器上的緩存段失效。

　　相反，如果兩個或多個處理器頻繁地訪問相同的緩存段，那么這些緩存段的內容必須保持同步。如果想更新其中一個緩存段的內容，必須先獲得獨占權，這意味著其他所有處理器必須先丟棄它們緩存中的同一緩存段的拷貝。這帶來的結果是，下一次有另外一個處理器要訪問這個緩存段，它的內容必須先通過總線來加載。所以結果就是緩存失效率（對于其他處理器來說）和總線上額外的通訊流量都增加了。這種多個處理器訪問一個頻繁被更新的緩存段的現象，叫做“緩存（段）競爭”。如果你想在多個處理器共用內存的環境中拖慢一個并行的程序，這也許是最簡單的方法。

　　緩存段競爭

　　要產生緩存段競爭，我們需要多個處理器頻繁訪問同一緩存段，并且其中部分的訪問是寫操作。私有數據（只會被一個線程訪問的緩存段）從來不是問題。不變的（immutable）數據（只被寫一次，其后到生命期結束都不會被修改）也不是問題。麻煩的是那些既被線程共享，又可變的數據：處理這些數據需要大量的通訊工作來使各個處理器看到的內存內容保持一致（根據內存模型的限制）。這種通訊代價很大——并且隨著處理器數量的增多，開銷會越來越大。

　　那么我們談論的開銷到底有多大？幾個星期前我寫了一個測試程序（針對x86/Windows）。這個測試程序用起來肯定是不方便的，也不好理解，它假設運行在四核處理器多線程環境，或者至少擁有八個邏輯處理器的類似環境下。它的要點是：上面已經解釋過，把一個“讀-修改-寫”模式的加法操作替換為原子加法操作，將產生十到二十五倍的開銷（精確數值取決于具體的微架構）。如果你需要一個經驗值，算十倍就可以了（對于費米估算來說已經足夠了）。

　　一旦有第二個處理器在讀同一個緩存段，開銷就會暴增。如果第二個處理器在快速循環中不停地讀取這個緩存段，那么原子加法的開銷會更大——大得多：典型的，增加四到六倍（這可是在我們使用原子加法而產生十倍開銷的基礎上再次翻倍！）。同時讀取這個緩存段的處理器越多，開銷就越大，而如果同時還有處理器在寫這個緩存段，那么效果更甚。但是請不要把這個數據當作金科玉律，這只是人寫的基準測試程序而已，它并不做任何實質性工作。為保證緩存一致性而產生的真正開銷跟具體的上下文有很大關系。在這里我想做的只是讓你對保證緩存一致性而產生的開銷有一個粗略的直觀感受（即：它是無法忽略不計的）。

　　其中有一些通訊流量是不必要的。比如，由于緩存一致性的最小顆粒度是段，很多不必要的同步開銷是可以簡化的，因為不同類型的數據——不可變的、私有的和共享的——在同一緩存段中交錯分布（或者類似地，因為一個緩存段中只保存了多個線程各自的私有數據）。這種現象叫做“假共享”。幸運的是，這種問題可以簡單通過性能評估程序來定位，通過重新組織內存數據（可能通過填充的方式，確保不同類型的數據不放在同一緩存段）的方法，可以相對直接地修復它，或者直接移除一些搗亂的數據。我的舊文“處理器不喜歡共享”中給出了一個例子。

　　經此過濾下來的就是真正的競爭了——競爭訪問共享數據。這包括了真正共享的可變數據結構，以及某些元數據（metadata），比如鎖和其他同步對象。準確地說，這種競爭運行得有多流暢，取決于數據在內存中的具體布局，以及使用什么操作來訪問它。

　　一般來說，要寫出在多核處理器上具有良好可伸縮性（scalable）的代碼，方法就是盡可能避免競爭，如果不能避免，則使所有競爭都盡可能快速通過。完善地考慮競爭問題，理解緩存一致性的工作原理（至少要大致上），理解處理器為了保證緩存一致性而需要交換什么信息，理解這種通訊何時會發生，這是非常重要的。我們講完了這些基礎知識，現在可以看看更上層的軟件了。這篇文章已經夠長了，在下篇文章中，我打算講講鎖和無鎖數據結構（lock-free data structures），并討論其中一些取舍問題。下次見，寫代碼要小心哦。