實作原理_atomic實作原理

atomic是原子的意思，意味"不可分割"的整體。在Linux kernel中有一類atomic操作API。這些操作對使用者而言是原子執行的，在一個CPU上執行過程中，不會被其他CPU打斷。最常見的操作是原子讀改寫，簡稱RMW。例如，atomic_inc()接口。atomic硬體實作和Cache到底有什麼關系呢？其實有一點關系，下面會一步步揭曉答案。

問題背景

我們先來看看不使用原子操作的時候，我們會遇到什麼問題。我們知道increase一個變量，CPU微觀指令級别分成3步操作。1) 先read變量的值到CPU記憶體寄存器；2) 對寄存器的值遞增；3) 将寄存器的值寫回變量。例如不使用原子指令的情況下在多個CPU上執行以下increase函數。

int counter = 0;

void increase(void)
{
        counter++;
}
           

例如2個CPU得系統，初始值counter為0。在兩個CPU上同時執行以上increase函數。可能出現如下操作序列：

+    +----------------------+----------------------+
   |    |    CPU0 operation    |    CPU1 operation    |
   |    +----------------------+----------------------+
   |    | read counter (== 0)  |                      |
   |    +----------------------+----------------------+
   |    |       increase       | read counter (== 0)  |
   |    +----------------------+----------------------+
   |    | write counter (== 1) |       increase       |
   |    +----------------------+----------------------+
   |    |                      | write counter (== 1) |
   |    +----------------------+----------------------+
   V
timeline
           

我們可以清晰地看到，當CPU0讀取counter的值位0後，在執行increase操作的同時，CPU1也讀取counter變量，同樣counter的值依然是0。随後CPU0和CPU1先後将1的值寫入記憶體。實際上，我們想執行兩次increase操作，我應該得到counter值為2。但是實際上得到的是1。這不是我們想要的結果。為了解決這個問題，硬體引入原子自增指令。保證CPU0遞增原子變量counter之間，不被其他CPU執行自增指令導緻不想要的結果。硬體是如何實作原子操作期間不被打斷呢？

Bus Lock

當CPU發出一個原子操作時，可以先鎖住Bus（總線）。這樣就可以防止其他CPU的記憶體操作。等原子操作結束，釋放Bus。這樣後續的記憶體操作就可以進行。這個方法可以實作原子操作，但是鎖住Bus會導緻後續無關記憶體操作都不能繼續。實際上，我們隻關心我們操作的位址資料。隻要我們操作的位址鎖住即可，而其他無關的位址資料通路依然可以繼續。是以我們引入另一種解決方法。

Cacheline Lock

為了實作多核Cache一緻性，現在的硬體基本采用MESI協定（或者MESI變種）維護一緻性。是以我們可以借助多核Cache一緻性協定MESI實作原子操作。我們知道Cache line的狀态處于Exclusive或者Modified時，可以說明該變量隻有目前CPU私有Cache緩存了該資料。是以我們可以直接修改Cache line即可更新資料。并且MESI協定可以幫我們保證互斥。當然這不能不能保證RMW操作期間不被打斷，是以我們還需要做些手腳實作原子操作。

我們依然假設隻有2個CPU的系統。當CPU0試圖執行原子遞增操作時。a) CPU0發出"Read Invalidate"消息，其他CPU将原子變量所在的緩存無效，并從Cache傳回資料。CPU0将Cache line置成Exclusive狀态。然後将該

cache line标記locked

。b) 然後CPU0讀取原子變量，修改，最後寫入cache line。c) 将cache line置位unlocked。

在步驟a)和c)之間，如果其他CPU（例如CPU1）嘗試執行一個原子遞增操作，CPU1會發送一個"Read Invalidate"消息，CPU0收到消息後，檢查對應的cache line的狀态是locked，暫時不回複消息（CPU1會一直等待CPU0回複Invalidate Acknowledge消息）。直到cache line變成unlocked。這樣就可以實作原子操作。我們稱這種方式為鎖cache line。這種實作方式必須要求操作的變量位于一個cache line。

LL/SC

LL/SC(Load-Link/Store-Conditional)是另一種硬體實作方法。例如aarch64架構就采用這種方法。這種方法就不是我們關注的重點了。略過。

總結

借助多核Cache一緻性協定可以很友善實作原子操作。當然遠不止上面舉例說的atomic_inc還有很多其他類似的原子操作，例如原子比較交換等。