快捷導(dǎo)航

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

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

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

CAS算法（compare and swap）

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

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

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

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

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

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

package main
import (
	"fmt"
	"sync"
	"sync/atomic"
)
var (
	counter int32          //計(jì)數(shù)器
	wg      sync.WaitGroup //信號(hào)量
)
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個(gè)信號(hào)量，然后開(kāi)啟五個(gè)線程執(zhí)行incCounter方法,incCounter內(nèi)部執(zhí)行, 使用cas操作遞增counter的值，atomic.CompareAndSwapInt32具有三個(gè)參數(shù)，第一個(gè)是變量的地址，第二個(gè)是變量當(dāng)前值，第三個(gè)是要修改變量為多少，該函數(shù)如果發(fā)現(xiàn)傳遞的old值等于當(dāng)前變量的值，則使用第三個(gè)變量替換變量的值并返回true，否則返回false。

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

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

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

我們有兩個(gè)goroutineA和goroutineB，接下來(lái)我們簡(jiǎn)稱 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(一個(gè)命令前綴，在這里用于CMPXCHGQ)可以鎖住總線保證多次內(nèi)存操作的原子性。

然后執(zhí)行CMPXCHGQ