英文原文：Atomic operations and contention
本文是RAD Game Tools程序員Fabian “ryg” Giesen在其博客上發(fā)表的《Atomic operations and contention》一文的翻譯，經(jīng)作者許可分享至InfoQ中文站。
上次（緩存一致性（Cache Coherency）入門），我們講了緩存一致性原理的基礎(chǔ)知識(shí)。今天，我們來談?wù)劵谝恢碌木彺鏄?gòu)建一個(gè)有用的系統(tǒng)，需要哪些原語（primitive），以及它們是如何工作的。
原子性和原子操作
計(jì)算機(jī)操作最重要的構(gòu)成單位是原子操作。這里的原子跟物理上說的原子沒有任何關(guān)系，而是起源于單詞atom，也就是希臘語“?τομο?”（意為不可見的）。原子操作是一種不可再細(xì)分的操作，或者在系統(tǒng)中其他處理器看來是不可再分了。為了說明為什么原子操作很重要，考慮兩個(gè)處理器以幾乎相同的方式增加一個(gè)計(jì)數(shù)器，翻譯成C語言就是counter++，此時(shí)會(huì)發(fā)生什么：
| 指令周期 | 處理器一 | 處理器二 |
| 0 | reg = load(&counter); | |
| 1 | reg = reg + 1; | reg = load(&counter); |
| 2 | store(&counter, reg); | reg = reg + 1; |
| 3 | store(&counter, reg); |
在編譯好的代碼中，這樣一個(gè)操作分為：讀操作、寄存器自加，最后是一個(gè)寫操作（這里用類似C語言的偽代碼表示）。這三個(gè)步驟是獨(dú)立且按順序執(zhí)行的（注意，對(duì)于x86來說，在更微觀的架構(gòu)層次上這句話是正確的，但是在指令集架構(gòu)的層次上，這三步看起來可以用一條“讀-修改-寫（read-modify-write）”指令完成：add [memory], value）。并且因?yàn)檫@些操作被分成多個(gè)指令周期來執(zhí)行，所以在處理器一讀完counter（并且正開始把它加一）之后，把結(jié)果寫回去之前的空隙，處理器二也有可能去讀它。結(jié)果導(dǎo)致雖然兩個(gè)處理器都去增加這個(gè)計(jì)數(shù)器，但最終計(jì)數(shù)器的值只被加了1，其中一個(gè)加法運(yùn)算“丟失”了。
原子操作恰恰就是用來防止這個(gè)問題的。如果我們使用一個(gè)原子的自加操作（說得更通用一點(diǎn)，原子加法）而不是常規(guī)的自加操作，執(zhí)行指令的處理器會(huì)確保上面的三個(gè)步驟（讀、加、寫）像一條指令那樣完成，成為一個(gè)原子操作。在自加操作進(jìn)行的時(shí)候，其他處理器無法插手。
原子操作是如何實(shí)現(xiàn)的
現(xiàn)在問題來了，原子操作是如何實(shí)現(xiàn)的呢？從理論上來說，最簡單的方法就是加鎖：在任何時(shí)間點(diǎn)上，只有一個(gè)處理器被允許執(zhí)行一個(gè)原子操作。這個(gè)處理器在做原子操作之前，必須先獲得鎖，并且在操作完成后釋放它。這就是x86的LOCK前綴的作用（大致如此；這里我略去了細(xì)節(jié)）。這里，獲得鎖的操作意味著向總線發(fā)送一條消息，說“好吧，我要占用總線一會(huì)兒，大家都退后”（根據(jù)我們的目的，這就意味著“請(qǐng)不要再做內(nèi)存操作了”）。然后發(fā)出請(qǐng)求的處理器要先等其他處理器完成它們正在進(jìn)行的內(nèi)存操作，之后才會(huì)得到確認(rèn)。只有等到其他所有處理器都確認(rèn)了以后，請(qǐng)求鎖的處理器才能開始處理內(nèi)存操作。最后，一旦鎖被釋放，它還需要發(fā)送一條信息給總線上的其他處理器“我的工作完成，你們可以繼續(xù)向總線發(fā)送請(qǐng)求了”。
這種做法沒有問題，但是慢得無法想象。x86處理器依然保留了這種方式（或者類似做法），但只有當(dāng)絕對(duì)緊急的情況下才會(huì)使用，也就是其他所有方法都失敗時(shí)的最后一招。x86指令集架構(gòu)需要這么一個(gè)辦法來兜底，因?yàn)樗麄優(yōu)榱讼蚝蠹嫒?，允許一些非常不可靠的操作，比如跨多個(gè)緩存段（cache line）的非對(duì)齊的原子操作。其他體系架構(gòu)不允許對(duì)非對(duì)齊的數(shù)據(jù)進(jìn)行原子操作，也不允許對(duì)“太大”的數(shù)據(jù)進(jìn)行原子操作。這些限制確保了單個(gè)原子操作只會(huì)發(fā)生在單個(gè)緩存段中。并且一旦有了這個(gè)前提，我們討論起來就方便了：上次討論緩存一致性協(xié)議的時(shí)候我們看到，處理器之間對(duì)于同步內(nèi)存的交互是以緩存段為單位的，所以原則上我們可以對(duì)單個(gè)緩存段做復(fù)雜的修改，然后通過刷新緩存段內(nèi)容來把修改公之于眾。而且，MESI協(xié)議狀態(tài)機(jī)有兩個(gè)狀態(tài)（M和E，代表“已修改”和“獨(dú)占”）可以保證一個(gè)緩存段被處理器獨(dú)占——當(dāng)一個(gè)緩存段被獨(dú)占時(shí)，其他處理器無法“窺探”。我們可以用這種機(jī)制來替代加鎖協(xié)議。
所以結(jié)論是這樣的：在一個(gè)使用MESI（或其衍生協(xié)議）的系統(tǒng)中，我們?yōu)榱舜_保針對(duì)單個(gè)緩存段的操作具有原子性，只需要做到：一、保證在正確的地方擺放內(nèi)存屏障（memory barrier），使內(nèi)存操作和周邊的代碼保持正確的執(zhí)行順序（見上一篇的文章），二、在讀任何東西前先獲得緩存段的所有權(quán)，三、只有當(dāng)我們?cè)谡麄€(gè)原子操作期間一直握有獨(dú)占權(quán)，才可以把操作的結(jié)果回寫。這可以確保沒有其他處理器能看到只完成了一半的數(shù)據(jù)。要完成第三點(diǎn)有好幾種方法，比如我們可以開發(fā)出這樣的硬件，讓它可以在單個(gè)總線時(shí)鐘周期內(nèi)完成某些原子操作；如果我們從一個(gè)時(shí)鐘周期開始的時(shí)候擁有某個(gè)緩存段的獨(dú)占權(quán)，那么直到這個(gè)周期結(jié)束，我們都可以修改數(shù)據(jù)。因?yàn)橐粋€(gè)緩存段不可能在一個(gè)時(shí)鐘周期內(nèi)“易手”，這樣的操作是很快的。根據(jù)總線協(xié)議，我們也可以玩點(diǎn)花樣，一致性請(qǐng)求可以立即響應(yīng)，但如果我們正在做原子操作，真正的數(shù)據(jù)可以稍晚發(fā)送。最后，我們也可以選擇根本不作弊，而是直接實(shí)現(xiàn)二和三：把所有正在進(jìn)行原子操作的緩存段“監(jiān)控”起來，在原子操作完成前，如果有其他處理器請(qǐng)求這個(gè)緩存段，那我們的原子操作要從頭再來。因?yàn)檫@個(gè)原因，大多數(shù)RISC處理器都有load-link/store-conditional（LL/SC）指令。
順便說一下，從總線側(cè)（以及其他處理器通過總線）看來，正確對(duì)齊的原子操作和普通的內(nèi)存更新沒有什么區(qū)別。所有的工作都在處理器內(nèi)部完成，其他處理器既不知道也不關(guān)心某次內(nèi)存更新到底是通過原子性的比較并交換（compare-and-swap）操作加上內(nèi)存屏障來完成的，還是通過一次隨意寫指令完成的。
這一切聽起來簡單而美好，至少理論上是，但魔鬼往往藏于細(xì)節(jié)中。壞消息是，如果你是一個(gè)CPU架構(gòu)師，這個(gè)過程的每個(gè)細(xì)節(jié)對(duì)你來說都關(guān)系重大；你對(duì)內(nèi)存操作的內(nèi)部實(shí)現(xiàn)需要避免“饑餓”（每個(gè)想獲取緩存段獨(dú)占權(quán)的處理器，最終都能獲得它，無論其他處理器在做什么），并且確?；镜脑硬僮鞯膶?shí)現(xiàn)不能導(dǎo)致死鎖或活鎖。這聽起來是顯而易見的，但是對(duì)低層次的原語（比如原子操作、LL/SC指令）來說，這種保證不是與生俱來的。這東西實(shí)現(xiàn)起來挺困難的，并且CPU不但要保證有正確的實(shí)現(xiàn)，還要保證這種實(shí)現(xiàn)在“典型場景”下足夠快。當(dāng)然，好消息是如果你工作的公司不是設(shè)計(jì)CPU的，以上這些都不關(guān)你的事?？隙ㄒ呀?jīng)有人通盤考慮過這些問題，并且他們背后有一支強(qiáng)大的驗(yàn)證工程師隊(duì)伍拼命地在找這些實(shí)現(xiàn)的紕漏。
內(nèi)存操作的開銷
回到軟件上，假設(shè)我們工作在一種典型的CPU體系結(jié)構(gòu)上，并且在多核系統(tǒng)中運(yùn)行代碼。在這種環(huán)境下，一次內(nèi)存操作的開銷到底是什么？這將分為幾個(gè)部分：
執(zhí)行。執(zhí)行一次內(nèi)存操作是有開銷的?，F(xiàn)在假設(shè)我們只有一個(gè)處理器核在工作，并且正在運(yùn)行單線程的代碼。即便如此，內(nèi)存訪問還是很復(fù)雜。跟程序打交道的是虛擬地址，但是緩存和內(nèi)存總線看到的卻是物理地址。所以任何內(nèi)存操作首先做的就是把虛擬地址轉(zhuǎn)換成物理地址，這些結(jié)果本身會(huì)保存在頁表緩存中（Translation Lookaside Buffer，簡稱TLB）。如果你運(yùn)氣不好，你所要訪問的虛擬地址當(dāng)前可能并沒有映射到物理地址，并且它的內(nèi)容需要從虛擬內(nèi)存中載入。當(dāng)這個(gè)情況發(fā)生時(shí)，操作系統(tǒng)會(huì)調(diào)度別的線程到當(dāng)前的處理器上運(yùn)行一段時(shí)間，因?yàn)閺奶幚砥骺磥?，IO操作需要花很長時(shí)間。但是我們先假設(shè)這種情況不會(huì)發(fā)生。
所以，一切都很順利的話，內(nèi)存操作到底能跑多快？看起來非?？臁ＭǔＣ總€(gè)時(shí)鐘周期至少可以完成一次操作（讀/寫），很有可能更多。在3GHz單核處理器上，能高效利用緩存的代碼每秒鐘可以完成十億次數(shù)量級(jí)的內(nèi)存操作。
內(nèi)存屏障和原子性的“讀-修改-寫”操作。下一步，假設(shè)我們的代碼是多線程的，但我們還是在單核上運(yùn)行它。這里我們就可以看到內(nèi)存屏障和原子操作了，但是沒有來自其他處理器的干擾。我們簡單假設(shè)所有需要的緩存段已經(jīng)被我們的處理器獨(dú)占了。在這種情況下，使用一次原子的整數(shù)加法來更新內(nèi)存中的一個(gè)引用計(jì)數(shù)器，代價(jià)到底有多大？
好吧，這其實(shí)取決于處理器架構(gòu)的實(shí)現(xiàn)。一般來說，對(duì)于帶有激進(jìn)的內(nèi)存重排序（memory reordering）策略的微架構(gòu)處理器來說，使用內(nèi)存屏障和原子操作的開銷更大，而只支持輕度重排序或者順序執(zhí)行（in-order）內(nèi)存操作的處理器則好一點(diǎn)。比如，在 Intel Atom處理器（順序執(zhí)行）上使用LOCK INC [mem]來增加引用計(jì)數(shù)器值的開銷，本質(zhì)上和使用常規(guī)INC [mem]指令是一樣的。而更復(fù)雜的內(nèi)存操作，如“交換（exchange）”和“交換-加(exchange-add)”花費(fèi)的時(shí)間是基礎(chǔ)的“讀-修改-寫”操作的兩到三倍。相反，在Intel和AMD支持亂序執(zhí)行（out-of-order）的桌面處理器產(chǎn)品線中，一次原子自加操作的開銷是非原子版本的十到二十五倍，這些開銷是保證正確的執(zhí)行順序所帶來的。再一次重申：這僅是在單核上運(yùn)行的代碼，還沒有涉及處理器間通訊的開銷。為了使代碼在多核系統(tǒng)上安全地運(yùn)行，還會(huì)在單個(gè)處理器內(nèi)引入額外的開銷。
總線流量（bus traffic）和緩存一致性（cache coherency）。部分內(nèi)存訪問操作實(shí)際上會(huì)無法命中緩存，從而只能從內(nèi)存中加載。一旦有些緩存段因?yàn)殚L時(shí)間無人訪問而被丟棄，我們就要開始把它的內(nèi)容回寫（write-back）到內(nèi)存中。所有這些事件都會(huì)導(dǎo)致總線上（以及內(nèi)存中）發(fā)生通訊流量。而總線和內(nèi)存的帶寬是有限的，當(dāng)容量飽和時(shí)，系統(tǒng)就變慢了。
而且，一旦我們?cè)诙嗪讼到y(tǒng)中運(yùn)行多線程程序，總線上就會(huì)產(chǎn)生額外的通訊流量來保證緩存一致性，因?yàn)楦鱾€(gè)處理器都會(huì)不斷地同步它們所看到的內(nèi)存內(nèi)容。如果每個(gè)線程都在自己獨(dú)立的內(nèi)存空間里工作，那么這種流量不會(huì)很大。如果每塊內(nèi)存只會(huì)被一個(gè)處理器使用，那么根本無需同步，而且我們可以很容易獲取這些內(nèi)存對(duì)應(yīng)的緩存段的獨(dú)占權(quán)，不會(huì)引起其他處理器上的緩存段失效。
相反，如果兩個(gè)或多個(gè)處理器頻繁地訪問相同的緩存段，那么這些緩存段的內(nèi)容必須保持同步。如果想更新其中一個(gè)緩存段的內(nèi)容，必須先獲得獨(dú)占權(quán)，這意味著其他所有處理器必須先丟棄它們緩存中的同一緩存段的拷貝。這帶來的結(jié)果是，下一次有另外一個(gè)處理器要訪問這個(gè)緩存段，它的內(nèi)容必須先通過總線來加載。所以結(jié)果就是緩存失效率（對(duì)于其他處理器來說）和總線上額外的通訊流量都增加了。這種多個(gè)處理器訪問一個(gè)頻繁被更新的緩存段的現(xiàn)象，叫做“緩存（段）競爭”。如果你想在多個(gè)處理器共用內(nèi)存的環(huán)境中拖慢一個(gè)并行的程序，這也許是最簡單的方法。
緩存段競爭
要產(chǎn)生緩存段競爭，我們需要多個(gè)處理器頻繁訪問同一緩存段，并且其中部分的訪問是寫操作。私有數(shù)據(jù)（只會(huì)被一個(gè)線程訪問的緩存段）從來不是問題。不變的（immutable）數(shù)據(jù)（只被寫一次，其后到生命期結(jié)束都不會(huì)被修改）也不是問題。麻煩的是那些既被線程共享，又可變的數(shù)據(jù)：處理這些數(shù)據(jù)需要大量的通訊工作來使各個(gè)處理器看到的內(nèi)存內(nèi)容保持一致（根據(jù)內(nèi)存模型的限制）。這種通訊代價(jià)很大——并且隨著處理器數(shù)量的增多，開銷會(huì)越來越大。
那么我們談?wù)摰拈_銷到底有多大？幾個(gè)星期前我寫了一個(gè)測試程序（針對(duì)x86/Windows）。這個(gè)測試程序用起來肯定是不方便的，也不好理解，它假設(shè)運(yùn)行在四核處理器多線程環(huán)境，或者至少擁有八個(gè)邏輯處理器的類似環(huán)境下。它的要點(diǎn)是：上面已經(jīng)解釋過，把一個(gè)“讀-修改-寫”模式的加法操作替換為原子加法操作，將產(chǎn)生十到二十五倍的開銷（精確數(shù)值取決于具體的微架構(gòu)）。如果你需要一個(gè)經(jīng)驗(yàn)值，算十倍就可以了（對(duì)于費(fèi)米估算來說已經(jīng)足夠了）。
一旦有第二個(gè)處理器在讀同一個(gè)緩存段，開銷就會(huì)暴增。如果第二個(gè)處理器在快速循環(huán)中不停地讀取這個(gè)緩存段，那么原子加法的開銷會(huì)更大——大得多：典型的，增加四到六倍（這可是在我們使用原子加法而產(chǎn)生十倍開銷的基礎(chǔ)上再次翻倍?。?。同時(shí)讀取這個(gè)緩存段的處理器越多，開銷就越大，而如果同時(shí)還有處理器在寫這個(gè)緩存段，那么效果更甚。但是請(qǐng)不要把這個(gè)數(shù)據(jù)當(dāng)作金科玉律，這只是人寫的基準(zhǔn)測試程序而已，它并不做任何實(shí)質(zhì)性工作。為保證緩存一致性而產(chǎn)生的真正開銷跟具體的上下文有很大關(guān)系。在這里我想做的只是讓你對(duì)保證緩存一致性而產(chǎn)生的開銷有一個(gè)粗略的直觀感受（即：它是無法忽略不計(jì)的）。
其中有一些通訊流量是不必要的。比如，由于緩存一致性的最小顆粒度是段，很多不必要的同步開銷是可以簡化的，因?yàn)椴煌愋偷臄?shù)據(jù)——不可變的、私有的和共享的——在同一緩存段中交錯(cuò)分布（或者類似地，因?yàn)橐粋€(gè)緩存段中只保存了多個(gè)線程各自的私有數(shù)據(jù)）。這種現(xiàn)象叫做“假共享”。幸運(yùn)的是，這種問題可以簡單通過性能評(píng)估程序來定位，通過重新組織內(nèi)存數(shù)據(jù)（可能通過填充的方式，確保不同類型的數(shù)據(jù)不放在同一緩存段）的方法，可以相對(duì)直接地修復(fù)它，或者直接移除一些搗亂的數(shù)據(jù)。我的舊文“處理器不喜歡共享”中給出了一個(gè)例子。
經(jīng)此過濾下來的就是真正的競爭了——競爭訪問共享數(shù)據(jù)。這包括了真正共享的可變數(shù)據(jù)結(jié)構(gòu)，以及某些元數(shù)據(jù)（metadata），比如鎖和其他同步對(duì)象。準(zhǔn)確地說，這種競爭運(yùn)行得有多流暢，取決于數(shù)據(jù)在內(nèi)存中的具體布局，以及使用什么操作來訪問它。
一般來說，要寫出在多核處理器上具有良好可伸縮性（scalable）的代碼，方法就是盡可能避免競爭，如果不能避免，則使所有競爭都盡可能快速通過。完善地考慮競爭問題，理解緩存一致性的工作原理（至少要大致上），理解處理器為了保證緩存一致性而需要交換什么信息，理解這種通訊何時(shí)會(huì)發(fā)生，這是非常重要的。我們講完了這些基礎(chǔ)知識(shí)，現(xiàn)在可以看看更上層的軟件了。這篇文章已經(jīng)夠長了，在下篇文章中，我打算講講鎖和無鎖數(shù)據(jù)結(jié)構(gòu)（lock-free data structures），并討論其中一些取舍問題。下次見，寫代碼要小心哦。
聯(lián)系客服
