CAS算法（compare and swap）

CAS算法涉及到三個操作數

• 需要讀寫的內存值V
• 進行比較的值A
• 擬寫入的新值B

當且僅當 V 的值等于 A時，CAS通過原子方式用新值B來更新V的值，否則不會執行任何操作（比較和替換是一個原子操作）。一般情況下是一個自旋操作，即不斷的重試。

CAS算法（Compare And Swap）,是原子操作的一種, CAS算法是一種有名的無鎖算法。無鎖編程，即不使用鎖的情況下實現多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實現變量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。可用于在多線程編程中實現不被打斷的數據交換操作，從而避免多線程同時改寫某一數據時由于執行順序不確定性以及中斷的不可預知性產生的數據不一致問題。

該操作通過將內存中的值與指定數據進行比較，當數值一樣時將內存中的數據替換為新的值。

Go中的CAS操作是借用了CPU提供的原子性指令來實現。CAS操作修改共享變量時候不需要對共享變量加鎖，而是通過類似樂觀鎖的方式進行檢查，本質還是不斷的占用CPU 資源換取加鎖帶來的開銷（比如上下文切換開銷）。

package main
import (
	"fmt"
	"sync"
	"sync/atomic"
)
var (
	counter int32          //計數器
	wg      sync.WaitGroup //信號量
)
func main() {
	threadNum := 5
	wg.Add(threadNum)
	for i := 0; i < threadNum; i++ {
		go incCounter(i)
	}
	wg.Wait()
}
func incCounter(index int) {
	defer wg.Done()
	spinNum := 0
	for {
		// 原子操作
		old := counter
		ok := atomic.CompareAndSwapInt32(&counter, old, old+1)
		if ok {
			break
		} else {
			spinNum++
		}
	}
	fmt.Printf("thread,%d,spinnum,%d\n", index, spinNum)
}

當主函數main首先創建了5個信號量，然后開啟五個線程執行incCounter方法,incCounter內部執行, 使用cas操作遞增counter的值，atomic.CompareAndSwapInt32具有三個參數，第一個是變量的地址，第二個是變量當前值，第三個是要修改變量為多少，該函數如果發現傳遞的old值等于當前變量的值，則使用第三個變量替換變量的值并返回true，否則返回false。

這里之所以使用無限循環是因為在高并發下每個線程執行CAS并不是每次都成功，失敗了的線程需要重寫獲取變量當前的值，然后重新執行CAS操作。讀者可以把線程數改為10000或者更多就會發現輸出thread,5329,spinnum,1其中這個1就說明該線程嘗試了兩個CAS操作，第二次才成功。

因此呢, go中CAS操作可以有效的減少使用鎖所帶來的開銷，但是需要注意在高并發下這是使用cpu資源做交換的。

CAS是如何運行的

我們有兩個goroutineA和goroutineB，接下來我們簡稱 A 和 B， 共享資源稱為C

• A 和 B 均保存 C 當前的值
• A 嘗試使用CAS（56，53）更新C的值
• C目前為56，可以更新，然后更新成功
• B嘗試使用CAS（56，53）更新C的值
• C已經為53，更新失敗

Go中的CAS源碼

// CompareAndSwapUint32 executes the compare-and-swap operation for a uint32 value.
func CompareAndSwapUint32(addr *uint32, old, new uint32) (swapped bool)

實際代碼文件在

Go / src / runtime / internal / atomic / asm_amd.s文件中

TEXT runtime∕internal∕atomic·Cas64(SB), NOSPLIT, $0-25
 MOVQ ptr+0(FP), BX
 MOVQ old+8(FP), AX
 MOVQ new+16(FP), CX
 LOCK
 CMPXCHGQ CX, 0(BX)
 SETEQ ret+24(FP)
 RET

其中我們可以看作

lock(一個命令前綴，在這里用于CMPXCHGQ)可以鎖住總線保證多次內存操作的原子性。

然后執行CMPXCHGQ

cmpxchg %cx, %bx；如果AX與BX相等，則CX送BX且ZF置1；否則BX送CX，且ZF清0

• 拿AX(old) 與 BX(共享數據ptr) 做對比。
• 相等，則修改BX(共享數據ptr)，狀態碼ZX設置為 1 。
• 不相等，則將CX(new)置為目前BX(共享數據ptr)的值， 狀態碼ZX設置為 0

CAS的缺陷

CAS在共享資源競爭比較激烈的時候，每個goroutine會容易處于自旋狀態，影響效率，在競爭激烈的時候推薦使用鎖。

無法解決ABA問題

ABA問題是無鎖結構實現中常見的一種問題，可基本表述為：

進程P1讀取了一個數值A

P1被掛起(時間片耗盡、中斷等)，進程P2開始執行

P2修改數值A為數值B，然后又修改回A

P1被喚醒，比較后發現數值A沒有變化，程序繼續執行。