快捷導(dǎo)航

Golang?Compare?And?Swap算法詳細(xì)介紹

更新時間：2022年10月11日 09:46:28 作者：~龐貝

CAS算法是一種有名的無鎖算法。無鎖編程，即不使用鎖的情況下實(shí)現(xiàn)多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實(shí)現(xiàn)變量的同步，所以也叫非阻塞同步Non-blocking?Synchronization

CAS算法（compare and swap）

CAS算法涉及到三個操作數(shù)

需要讀寫的內(nèi)存值V
進(jìn)行比較的值A(chǔ)
擬寫入的新值B

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

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

該操作通過將內(nèi)存中的值與指定數(shù)據(jù)進(jìn)行比較，當(dāng)數(shù)值一樣時將內(nèi)存中的數(shù)據(jù)替換為新的值。

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

package main
import (
	"fmt"
	"sync"
	"sync/atomic"
)
var (
	counter int32          //計(jì)數(shù)器
	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)
}

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

這里之所以使用無限循環(huán)是因?yàn)樵诟卟l(fā)下每個線程執(zhí)行CAS并不是每次都成功，失敗了的線程需要重寫獲取變量當(dāng)前的值，然后重新執(zhí)行CAS操作。讀者可以把線程數(shù)改為10000或者更多就會發(fā)現(xiàn)輸出thread,5329,spinnum,1其中這個1就說明該線程嘗試了兩個CAS操作，第二次才成功。

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

CAS是如何運(yùn)行的

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

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

Go中的CAS源碼

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

實(shí)際代碼文件在

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)可以鎖住總線保證多次內(nèi)存操作的原子性。

然后執(zhí)行CMPXCHGQ