執行緒同步 5：原子變數

上期我們看到當不同的執行緒彼此共同存取同一個變數的時候會發生什麼樣的異常結果， 但是在現實中的程式裡又沒辦法完全避免掉共同資料的存取，那麼我們能夠怎麼辦呢？ 本篇就來介紹第一個幫助我們解決執行緒資料競爭問題的方案：原子變數。

如何解決資料衝突問題？

回顧前篇，我們知道不同的執行緒共同操作同一段記憶體資料會導致錯亂的問題，其原因有三： 一個動作實際需動用多個指令來完成、由編譯器和 CPU 本身的亂序執行而導致的執行順序問題、 以及 CPU 核心之間快取不同步，三者同樣都會導致最終不預期的異常現象。

為了解決問題，首先我們需要 CPU 本身提供能「原子操作」(Atomic Operation)的指令。 是的，必須要 CPU 本身有提供這樣的能力。 如果 CPU 沒有這類指令的話，那這個 CPU 就沒法用來做平行運算了， 因為所有後面作業系統提供的那些更高級的功能都需要使用這些核心操作來實現。 通常來說每個這種原子式的操作都只對應一個指令來進行，不像前篇演示過的一個加運算由好幾個指令組合那樣。 原子操作指令只需要一個指令，畢竟只有一個指令的話，就不存在被其它指令從中間插隊的情形了！

再來，指令順序的部份也需要被解決， 我們需要對那些關鍵性的資料操作行為設下一些關於指令順序調換的限制。 我們需要要求編譯器不能那麼肆無忌憚的隨意調換程式敘述與編譯指令的位置， 比方說在我們對那個關鍵的，也就是許多執行緒都會共同操作的變數(或記憶體區域)操作時， 可能需要要求編譯器再怎麼最佳化調整順序，也不能把在此關鍵位置之前的讀寫操作調到後面去， 或者將此關鍵位置後面的讀寫操作調換到前面。 並且這項限制並不只是針對編譯器而已，考量到 CPU 本身可能有「亂序執行」的最佳化行為， 因此同樣也需要 CPU 在執行原子類型指令的時候排斥、暫停其它指令的動作。 而同樣的，這不能是另一個 CPU 指令，否則和前面的原子操作指令一前一後之間就存在了被插隊的風險， 因此通常這個效果會被併入前面介紹的原子化指令中一步到位一起進行。

最後就是關於 CPU 核心的快取暫存的問題。 如前篇解釋，CPU 的快取是為了減少與主記憶體的往來以加速資料存取及操作的目的地而存在。 然而當一個 CPU 核心對資料進行修改時，這被更改後的資料可能會被留存在快取內而非立即寫回主記憶體， 這就表示其它的 CPU 核心從主記憶體看到的並不是最新的資料； 且如果它又對同樣的資料進行操作的話，那麼兩個版本的最新資料就這麼產生了！ 因此我們需要在進行原子指令的時候將修改後的資料立刻刷回主記憶體， 並且同步去通知其它 CPU 核心，讓它們把我們正在操作的記憶體區段的快取(如果它們有的話)設為失效， 這樣當其它 CPU 核心下回需要使用到那段記憶體資料的時候，就會被強迫重新從主記憶體讀出最新的數據。 當然同樣的，相關的這些快取操作行為一般也都已經併入於 CPU 的原子化操作指令內了， 這樣就能用無法被別人給插隊的僅僅一個 CPU 指令來一起完成上述的這些全部的動作。

原子操作的代價

既然原子式的指令這麼好用，可以直接解決多緒競爭的問題， 那麼為什麼當今我們還要留著大量的普通指令，而不要全部使用原子化指令就好了呢？ 這是因為原子化的操作在解決競爭的同時，也是付帶著相應的代價的！

首先是對單一指令這件事。 之所以平常的常規操作通常都需要搭配多個指令一起合作，那是因為許多複雜的工作其基底大多是一樣的， 意思就是對 CPU 來說，提供幾個基本的磚塊就能讓我們使用疊積木的方式堆出我們想要的複雜功能。 然而原子指令可好了，強迫 CPU 必須要一個指令做完一整個工作，於是 CPU 的設計複雜度和成本就無法節省了！ 這裡說的成本泛指一切的成本，包括售價、體積、功耗、與發熱量等。 這就是為什麼 CPU 能提供的那些原子化的指令，通常都只能夠用來執行一些最簡單的功能的根本原因了， 比如只能夠進行部份整數的加、減、值交換、及部份簡單的位元運算等。

此外，原子化的指令還需要對指令的排序做出限制， 這會相當程度的影響程式的最終效能，無論是對於 CPU 還是對於編譯器來說都是。 因為任何的順序調換行為其目的都是為了最佳化執行效率的目的， 而當限制了能夠調整的空間，自然優化的效果就得受限了。 然後每次的原子化指令操作還都得讓好多 CPU 核心丟棄它們相應的快取資料， 使得如果原子指令操作的夠頻繁的話，CPU 就得不斷向速度慢了它自己一個等級的主記憶體頻繁讀寫資料， 而這是導致原子化操作緩慢的主要因素！ (當然緩慢或快速都是比較出來的，如果是和以後要介紹的那些高級鎖比較起來的話，那麼原子操作還是非常快速的！)

範例

這裡讓我們繼續沿用前篇的範例，但是把那共同寫入的變數更改為使用原子變數(Atomic Variable)：

struct WorkData
{
    atomic_int value;
    int step_value;
    int proc_times;
};

在執行累加變數的執行緒函式內也需要修改，需要使用 C11 規範的原子變數操作函式來操作它：

int n = data->proc_times;
int x = data->step_value;

for(int i = 0; i < n; ++i)
    atomic_fetch_add(&data->value, x);

而在主程式內也同樣需要改用規範的函式來操作與初始化原子變數：

atomic_init(&data.value, 0);

//......

printf("Finished, value=%d/%d, spend=%u\n",
    atomic_load(&data.value), /*......*/);

原子變數與一般的普通變數不一樣， 若直接把它當成普通變數那樣來做存取與運算，則並不能夠保證在所有的執行平臺上都能得到它應該產生的效果， 因此正規的用法還是需要使用標準規範的操作函式來執行相關的操作。 C11 的原子變數支援的操作有加法(add)、減法(sub)、值交換(exchange)、 位元與(and)、位元或(or)、位元異或(xor)、 及讀值(load)與存值(store)等操作。 就如同前面所說，原子變數能夠進行的操作運算真就不多！

完整的範例可以從這裡下載。 在我的電腦上執行後的結果如下：

Finished, value=800000000/800000000, spend=5592

改用原子變數與操作之後，程式的計算結果終於正確了！ 然而，副作用也同樣明顯，程式的效能變差了！

相比於前篇範例程式的執行只消耗 1 秒多的時間， 本篇改用原子操作之後的執行時間直接就拉到了 5 秒多，大約是原先的 5 倍。 至於原子操作為什麼會慢的原因在前面都解釋過了，主要就是為了解決那三道導致資料競爭的問題。 CPU 原子操作本身就具有排他性，加上限制了 CPU 與編譯器的最佳化調配空間， 然後快取又幫不上忙而需要去讀寫主記憶體，最終導致的結果就是肉眼可見的效能退化。 只不過快與慢都是比較出來的，相比於後續介紹的各種執行緒同步機制來說，原子變數那可已經是最快速高效的存在了！ 了解這些事情後，落實在我們日常設計程式的工作中那就是要： 儘量避免設計出需要在不同執行緒之間大量讀寫共用資料的情況，並將執行緒之間共同交集的範圍縮到愈小愈好。 這樣我們才只需要針對最少量的關鍵資料進行特別對待處理，從而能夠最大程度的降低對程式效能的劣化影響。

Memory Order

在閱讀 Atomic Operation 相關說明文件的時候，通常會看到幾種 Memory Order 可以選用， 那麼這些是什麼意義呢？我們又該如何選用呢？

前面提到了，原子操作其實相當影響效能(相較於非原子式的普通操作來說)， 而效能劣化的其中重要原因來自於對最佳化能力的限制(無論是對編譯器還是 CPU)， 那麼如果我們能夠視程式實際的情況去適度的放寬對最佳化的限制，是不是就能夠一定程度的提升原子操作的效能了呢？ 這就是不同的 Memory Order 所表達的意義了。 當然如果選錯了 Memory Order，那可能就會導致如同前篇說明的那不讓人樂意的資料競爭結果出現。 因此自認沒有把 Memory Order 完得很通透的作者我平常都只用條件最嚴格的預設值。

一般來說能夠選用的 Memory Order 有下列幾種：

  1. Acquire

    在這個執行緒裡，原本在這個原子操作後面的其它讀寫行為不能被重排序到這個原子操作前面； 言下之意就是原來在前面的讀寫可以被重排序到後面去執行。 並且其它執行緒如果對這同一個原子變數進行了 Release Order 的操作， 那麼在那個執行緒做原子操作之前的所有資料寫入(並不限定於原子變數)立刻就可以被這個執行緒看見； 因此 Acquire Order 通常被用來在讀取操作時使用。

  2. Release

    在這個執行緒裡，原本在這個原子操作前面的其它讀寫行為不能被重排序到這個原子操作的後面： 言下之意就是原來在後面的讀寫可以被重排序到前面去執行。 並且如果其它執行緒對同一個原子變數進行了 Acquire Order 的操作， 那麼在這個執行緒的這個原子操作之前的所有寫入更新(並不限定於原子變數)立刻就能被其它執行緒看見； 因此 Release Order 通常被用來在寫入操作時使用。

  3. Consume

    這個這定和 Acquire Order 基本是一樣的，用途也一樣， 只是對於限制排序的讀寫操作僅作用於與當下這個原子變數的值存有關聯關係的其它變數 (因此通常這只對編譯器的最佳化行為有所影響)。

  4. Relaxed

    顧名思義，就是一種相當「放鬆」的操作。 它只保證原子操作本身是原子的，但對於其它變數的讀寫操作排序什麼的就不做任何限制了！ 如果你的程式設計裡剛好只需要針對原子變數有所要求，而對其它變數的更新狀態無所謂的話， 那麼就可以選用這個設定來嘗試獲得更好的效能。

  5. ACQ_REL

    就是 Acquire Order 加上 Release Order 的操作， 既不允許在它之後的讀寫行為被排到它前面來，也不允許在它前面的排到它後面去。 這通常被用在「讀取後更新再寫入」類型的原子操作，其實也就是大部份原子變數的計算操作行為上。

  6. SEQ_CST

    這是在 ACQ_REL 本身的基礎之上再加上更多限制條件的選項，也是在不指定 Memory Order 時的預設選項。 我們說 CPU 的快取是因為讀寫主記憶體的緩慢而存在，但是過於頻繁的刷寫快取也被嫌慢， 於是又整出了「準備等會要更新快取」的 store buffer 和 invalidate queue 出來！ 所以 SEQ_CST 就是在 ACQ_REL 的基礎之上， 還要求 CPU 立刻馬上處理 store buffer 和 invalidate queue 不要拖。 因此 SEQ_CST 就是所有 Memory Order 裡面對效能影響最大的一個，不過也是最為保險的一個， 也是包含 C11 在那的大多數原子操作預設的選項，也是我通常不假思索就直接使用的選項。

Lock Free?

前面說明過，原子變數的實現需要 CPU 本身提供相應的原子操作指令， 因此造成原子變數能夠進行的操作種類並不多的結果。 然而另一方面，即便像是 C11 標準所制定的原子操作已經夠少了， 但是有沒有可能存在某些 CPU 它們能夠提供的原子操作甚至還更少呢？ 甚至於，C++ 的 std::atomic 模板更加變態，還能讓你把所有任何物件通通變成原子的， 你想想這怎麼可能呢？這些又是怎麼辦到的呢？

事實上就是許多 CPU 並不能夠提供 C11 想要的所有原子操作功能， 因此可能會有部份的操作必須要讓編譯器去想辦法實現， 而最終的辦法就是使用作業系統提供的高級鎖來實作這些功能。 也就是說隨著我們的編譯與執行環境不同， 可能有部份原子操作函式其實它底下並不是 CPU 的原生功能，而是藉由作業系統提供的功能來實現的。 不論是 CPU 原生功能還是編譯器封裝作業系統功能的實現方式， 最終都能讓我們的程式解決資料競爭的問題，跑出正確的結果，只不過效能可能會差很多！ 於是才有了判斷某個字面上的原子變數是不是 lock free 的相關函式。 所謂 lock free 就是指對於這個型態變數的操作是 CPU 原生的，不需要動用到鎖(lock)； 而那些不是 lock free 的，就是底層使用鎖(lock)等作業系統功能來實現的功能， 是帶有較大性能開銷的假原子變數。

說到了 lock free，那就不得不提一個非常特別的原子變數，那就是原子旗標 Atomic Flag。 這東西與其它型態的原子變數不一樣，它保證不管在哪一個平臺都是 lock free 的，都是使用 CPU 原生指令實現。 之所以能做這樣的保證，那是因為即便是最陽春的 CPU， 只要它能支援平行運算，那必定至少得實現最最最基本的這個指令，否則沒得玩了， 因為所有後續更高級的作業系統相關的鎖的實現，都建基於這個最簡單的操作之上。 作為所有 CPU 都俱備實現的原子操作的交集，這個 atomic flag 也是極其簡單， 基本上它只提供兩個操作： 第一個操作是設立旗標(設為非零)，並且傳回於本次執行前的舊旗標狀態； 另一個操作則是無條件清除旗標。 就只有這麼簡單的兩個操作，沒有別的了！

原子旗標的功能雖然簡陋，但是它保證肯定是 lock free 的。 在極其陽春的環境下，光只要有這個功能，就能夠以它為基礎實現許多其它的高級功能。 記得多年前我就曾在一個嵌入式設備的開發中使用過它。 當時 C++11 才剛發佈，也就是說我們使用的編譯平臺根本還不可能用上這些新功能， 甚至於我們當時還在使用祖傳的舊版本 GCC，連編譯器的 builtin atomic 都還沒有支援， 然後就這麼剛好的我需要在這樣的情況下解決一些執行緒競爭的問題。 於是我在那個時候就去翻找了 ARM CPU 的指令集(那個時候的 ARM 指令集還相當簡單，不像現在的複雜)， 找到了一個 atomic value exchange 的指令， 然後用組合語言寫了上面所描述的兩個 atomic flag 的操作函式， 再用這兩個函式手搓了一份簡單但能用的執行緒鎖(mutex)，如此解決了當時的問題。 當然以當前現在的開發環境來說應該是不太有需要再去做一次這種事情， 但是當時的經歷還是能讓我覺得挺有意思的！

結語

本篇介紹了能夠解決執行緒資料競爭問題的第一個解決方案：原子變數。 原子變數是所有執行緒同步機制當中最簡單高效的一種方案， 然而它也同樣帶來一些副作用，在解決競爭問題的同時給效能帶來劣化的影響， 因此在使用原子變數的時候也並不能夠過於肆無忌憚。

上一篇：「執行緒同步 4：為什麼出錯？」
下一篇：「執行緒同步 6：互斥子」