golang中的atomic，以及CAS操作

CAS無鎖算法

要實現無鎖（lock-free）的非阻塞算法有多種實現方法，其中CAS（比較與交換，Compare and swap）是一種有名的無鎖算法。CAS是CPU指令，在大多數處理器架構，包括 IA32、Space中采用的都是CAS指令，CAS是樂觀鎖技術，當多個線程嘗試使用CAS同時更新同一個變量時，只有其中一個線程能更新變量的值，而其它線程都失敗，失敗的線程並不會被掛起，而是被告知這次競爭中失敗，並可以再次嘗試。

CAS在golang的實現

for {
    
    if atomic.CompareAndSwapInt64(&data, old, new) {
    
        return new
    }
}

CompareAndSwap會先進行比較，如果data的值等於old，那麼就會執行替換操作並返回true，如果不等於，則說明已經被其他線程操作了就返回false，所以它並不一定總能成功，尤其是在並發大的情况下，所以使用for循環來自旋。當同步沖突出現的機會很少時，這種假設能帶來較大的性能提昇。

通常使用的i++操作，其過程是先從內存讀取出i，然後加1，然後賦值給內存，很顯然這個過程並不是原子的，我們可以使用CAS來實現原子化自增操作。

func AddInt64(addr *int64, inc int64) int64 {
    
	for {
    
		old := *addr
		if atomic.CompareAndSwapInt64(addr, old, old+inc) {
    
			return old
		}
	}
}

所以，基於CAS，我們可以對一個內存地址上的值先比較再賦值，保證了原子性。

atomic一般是由匯編語言實現的，比如文件src/runtime/internal/atomic/atomic_386.s

CAS指令

知道了CAS是個什麼意思之後，接下來就要去探究CAS的實現原理，以及CAS的比較+賦值過程是如何做到原子性的。

CAS自身的原子性是由CPU指令來實現的，我沒有找到具體代碼，下面是網上的代碼。

// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line // so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0 \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:
  
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
    
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

程序會根據當前處理器的類型來决定是否為 cmpxchg指令 添加 lock前綴。如果程序是在多處理器上運行，就為 cmpxchg指令 加上 lock前綴（lock cmpxchg）。反之，如果程序是在單處理器上運行，就省略 lock前綴（單處理器自身會維護單處理器內的順序一致性，不需要lock前綴提供的內存屏障效果）。

intel的手册對lock前綴的說明如下

1. 確保對內存的 讀-改-寫 操作原子執行。在Pentium及Pentium之前的處理器中，帶有lock前綴的指令在執行期間會鎖住總線，使得其他處理器暫時無法通過總線訪問內存。很顯然，這會帶來昂貴的開銷。從Pentium 4，Intel Xeon及P6處理器開始，intel在原有總線鎖的基礎上做了一個很有意義的優化：如果要訪問的內存區域（area of memory）在lock前綴指令執行期間已經在處理器內部的緩存中被鎖定（即包含該內存區域的緩存行當前處於獨占或以修改狀態），並且該內存區域被完全包含在單個緩存行（cache line）中，那麼處理器將直接執行該指令。由於在指令執行期間該緩存行會一直被鎖定，其它處理器無法讀/寫該指令要訪問的內存區域，因此能保證指令執行的原子性。這個操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低lock前綴指令的執行開銷，但是當多處理器之間的競爭程度很高或者指令訪問的內存地址未對齊時，仍然會鎖住總線。
2. 禁止該指令與之前和之後的讀和寫指令重排序。
3. 把寫緩沖區中的所有數據刷新到內存中。

關於CPU的鎖有如下2種

1. 使用總線鎖保證原子性

第一個機制是通過總線鎖保證原子性。如果多個處理器同時對共享變量進行讀改寫（i++就是經典的讀改寫操作）操作，那麼共享變量就會被多個處理器同時進行操作，這樣讀改寫操作就不是原子的，操作完之後共享變量的值會和期望的不一致。原因是有可能多個處理器同時從各自的緩存中讀取變量i，分別進行加1操作，然後分別寫入系統內存當中。那麼想要保證讀改寫共享變量的操作是原子的，就必須保證CPU1讀改寫共享變量的時候，CPU2不能操作緩存了該共享變量內存地址的緩存。

處理器使用總線鎖就是來解决這個問題的。所謂總線鎖就是使用處理器提供的一個LOCK＃信號，當一個處理器在總線上輸出此信號時，其他處理器的請求將被阻塞住,那麼該處理器可以獨占使用共享內存。

2. 使用緩存鎖保證原子性

第二個機制是通過緩存鎖定保證原子性。在同一時刻我們只需保證對某個內存地址的操作是原子性即可，但總線鎖定把CPU和內存之間通信鎖住了，這使得鎖定期間，其他處理器不能操作其他內存地址的數據，所以總線鎖定的開銷比較大，最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進行優化。

頻繁使用的內存會緩存在處理器的L1，L2和L3高速緩存裏，那麼原子操作就可以直接在處理器內部緩存中進行，並不需要聲明總線鎖，在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來實現複雜的原子性。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內存區域在LOCK操作期間被鎖定，當它執行鎖操作回寫內存時，處理器不在總線上聲言LOCK＃信號，而是修改內部的內存地址，並允許它的緩存一致性機制來保證操作的原子性，因為緩存一致性機制會阻止同時修改被兩個以上處理器緩存的內存區域數據，當其他處理器回寫已被鎖定的緩存行的數據時會起緩存行無效。

但是有兩種情况下處理器不會使用緩存鎖定。第一種情况是：當操作的數據不能被緩存在處理器內部，或操作的數據跨多個緩存行（cache line），則處理器會調用總線鎖定。第二種情况是：有些處理器不支持緩存鎖定。對於Inter486和奔騰處理器,就算鎖定的內存區域在處理器的緩存行中也會調用總線鎖定。

以上兩個機制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實現。比如比特測試和修改指令BTS，BTR，BTC，交換指令XADD，CMPXCHG和其他一些操作數和邏輯指令，比如ADD（加），OR（或）等，被這些指令操作的內存區域就會加鎖，導致其他處理器不能同時訪問它。

鎖（lock）的代價

鎖是用來做並發最簡單的方式，當然其代價也是最高的。內核態的鎖的時候需要操作系統進行一次上下文切換，加鎖、釋放鎖會導致比較多的上下文切換和調度延時，等待鎖的線程會被掛起直至鎖釋放。在上下文切換的時候，cpu之前緩存的指令和數據都將失效，對性能有很大的損失。操作系統對多線程的鎖進行判斷就像兩姐妹在為一個玩具在爭吵，然後操作系統就是能决定他們誰能拿到玩具的父母，這是很慢的。用戶態的鎖雖然避免了這些問題，但是其實它們只是在沒有真實的競爭時才有效。

CAS缺點

1、 CAS雖然很高效的解决原子操作，但是CAS仍然存在三大問題。

ABA問題。因為CAS需要在操作值的時候檢查下值有沒有發生變化，如果沒有發生變化則更新，但是如果一個值原來是A，變成了B，又變成了A，那麼使用CAS進行檢查時會發現它的值沒有發生變化，但是實際上卻變化了。ABA問題的解决思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加一，那麼A－B－A 就會變成1A-2B－3A。

循環時間長開銷大。自旋CAS如果長時間不成功，會給CPU帶來非常大的執行開銷。如果JVM能支持處理器提供的pause指令那麼效率會有一定的提昇，pause指令有兩個作用，第一它可以延遲流水線執行指令（de-pipeline）,使CPU不會消耗過多的執行資源，延遲的時間取决於具體實現的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因內存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執行效率。

只能保證一個共享變量的原子操作。當對一個共享變量執行操作時，我們可以使用循環CAS的方式來保證原子操作，但是對多個共享變量操作時，循環CAS就無法保證操作的原子性，這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合並成一個共享變量來操作。比如有兩個共享變量i＝2,j=a，合並一下ij=2a，然後用CAS來操作ij。

2、比較花費CPU資源，即使沒有任何爭用也會做一些無用功。

3、會增加程序測試的複雜度，稍不注意就會出現問題。

應用

CAS操作的優勢是，可以在不形成臨界區和創建互斥量的情况下完成並發安全的值替換操作。
這可以大大的减少同步對程序性能的損耗。

當然，CAS操作也有劣勢。在被操作值被頻繁變更的情况下，CAS操作並不那麼容易成功。

1. 增或减
被用於進行增或减的原子操作（以下簡稱原子增/减操作）的函數名稱都以“Add”為前綴，並後跟針對的具體類型的名稱。
不過，由於atomic.AddUint32函數和atomic.AddUint64函數的第二個參數的類型分別是uint32和uint64，所以我們無法通過傳遞一個負的數值來减小被操作值。atomic.AddUint32(&uint32, ^uint32(-NN-1)) 其中NN代錶了一個負整數。

2. 比較並交換
func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)
第一個參數的值應該是指向被操作值的指針值。該值的類型即為*int32。後兩個參數的類型都是int32類型。它們的值應該分別代錶被操作值的舊值和新值。CompareAndSwapInt32函數在被調用之後會先判斷參數addr指向的被操作值與參數old的值是否相等。僅當此判斷得到肯定的結果之後，該函數才會用參數new代錶的新值替換掉原先的舊值。否則，後面的替換操作就會被忽略。

3. 載入
v := atomic.LoadInt32(&value)
接受一個*int32類型的指針值，並會返回該指針值指向的那個值。 有了“原子的”這個形容詞就意味著，在這裏讀取value的值的同時，當前計算機中的任何CPU都不會進行其它的針對此值的讀或寫操作。這樣的約束是受到底層硬件的支持的。

4. 存儲
在原子的存儲某個值的過程中，任何CPU都不會進行針對同一個值的讀或寫操作。如果我們把所有針對此值的寫操作都改為原子操作，那麼就不會出現針對此值的讀操作因被並發的進行而讀到修改了一半的值的情况了。原子的值存儲操作總會成功，因為它並不會關心被操作值的舊值是什麼。函數atomic.StoreInt32會接受兩個參數。第一個參數的類型是*int 32類型的，其含義同樣是指向被操作值的指針。而第二個參數則是int32類型的，它的值應該代錶欲存儲的新值。其它的同類函數也會有類似的參數聲明列錶。

5. 交換
與CAS操作不同，原子交換操作不會關心被操作值的舊值。它會直接設置新值。但它又比原子載入操作多做了一步。作為交換，它會返回被操作值的舊值。此類操作比CAS操作的約束更少，同時又比原子載入操作的功能更强。以atomic.SwapInt32函數為例。它接受兩個參數。第一個參數是代錶了被操作值的內存地址的*int32類型值，而第二個參數則被用來錶示新值。注意，該函數是有結果值的。該值即是被新值替換掉的舊值。atomic.SwapInt32函數被調用後，會把第二個參數值置於第一個參數值所錶示的內存地址上（即修改被操作值），並將之前在該地址上的那個值作為結果返回。

用原子操作來替換mutex鎖

其主要原因是，原子操作由底層硬件支持，而鎖則由操作系統提供的API實現。若實現相同的功能，前者通常會更有效率。