Go是一門以并發(fā)編程見(jiàn)長(zhǎng)的語(yǔ)言，它提供了一系列的同步原語(yǔ)方便開(kāi)發(fā)者使用，例如sync包下的Mutex、RWMutex、WaitGroup、Once、Cond，以及抽象層級(jí)更高的Channel。但是，它們的實(shí)現(xiàn)基石是原子操作。需要記住的是：軟件原子操作離不開(kāi)硬件指令的支持。本文擬通過(guò)探討原子操作——比較并交換(compare and swap, CAS)的實(shí)現(xiàn)，來(lái)理解Go是如何借助硬件指令來(lái)實(shí)現(xiàn)這一過(guò)程的。
什么是CAS
在看源碼實(shí)現(xiàn)之前，我們先理解一下CAS。
維基百科定義：CAS是原子操作的一種，可用于在多線程編程中實(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ù)替換為新的值。
CAS的實(shí)現(xiàn)思想可以用以下偽代碼表示
bool Cas(int *val, int old, int new)
Atomically:
if(*val == old){
*val = new;
return 1;
} else {
return 0;
}
在sync/atomic/doc.go中，定義了一系列原子操作函數(shù)原型。以CompareAndSwapInt32為例，有以下代碼
package main
import (
"fmt"
"sync/atomic"
)
func main() {
a := int32(10)
ok := atomic.CompareAndSwapInt32(&a, 10, 100)
fmt.Println(a, ok)
ok = atomic.CompareAndSwapInt32(&a, 10, 50)
fmt.Println(a, ok)
}
它的執(zhí)行結(jié)果如下
$ go run main.go
100 true
100 false
CAS能做什么
CAS從線程層面來(lái)說(shuō)，它是非阻塞的，其樂(lè)觀地認(rèn)為在數(shù)據(jù)更新期間沒(méi)有其他線程影響，因此也常常被稱為是一種輕量級(jí)的樂(lè)觀鎖。它關(guān)注的是并發(fā)安全，而并非并發(fā)同步。
在文章開(kāi)頭時(shí)，我們就已經(jīng)提到原子操作是實(shí)現(xiàn)上層同步原語(yǔ)的基石。以互斥鎖為例，為了方便理解，我們?cè)谶@里將它的狀態(tài)定義為0和1，0代表目前該鎖空閑，1代表已被加鎖。那么，這個(gè)時(shí)候，CAS就是管理狀態(tài)的最佳選擇，以下是sync.Mutex中Lock方法的部分實(shí)現(xiàn)代碼。
func (m *Mutex) Lock() {
// Fast path: grab unlocked mutex.
if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
if race.Enabled {
race.Acquire(unsafe.Pointer(m))
}
return
}
// Slow path (outlined so that the fast path can be inlined)
m.lockSlow()
}
在atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked)中，m.state代表鎖的狀態(tài)，通過(guò)CAS函數(shù)，判斷鎖此時(shí)的狀態(tài)是否空閑（m.state==0），是，則對(duì)其加鎖（這里mutexLocked的值為1）。
源碼解讀
同樣還是以CompareAndSwapInt32為例，它在sync/atomic/doc.go中定義的函數(shù)原型如下
func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)
對(duì)應(yīng)的匯編代碼位于sync/atomic/asm.s中
TEXT ·CompareAndSwapInt32(SB),NOSPLIT,$0
JMP runtime∕internal∕atomic·Cas(SB)
通過(guò)指令JMP，跳轉(zhuǎn)到它的實(shí)際實(shí)現(xiàn)runtime∕internal∕atomic·Cas(SB)。這里需要注意的是，由于架構(gòu)體系差異，其匯編實(shí)現(xiàn)也會(huì)存在差別。在本文，我們就以常見(jiàn)的amd64為例，因此進(jìn)入runtime/internal/atomic/asm_amd64.s，匯編代碼如下
TEXT runtime∕internal∕atomic·Cas(SB),NOSPLIT,$0-17
MOVQ ptr+0(FP), BX
MOVL old+8(FP), AX
MOVL new+12(FP), CX
LOCK
CMPXCHGL CX, 0(BX)
SETEQ ret+16(FP)
RET
Go的匯編是基于 Plan9 的，我想是因?yàn)?strong>Ken Thompson（他是Plan 9操作系統(tǒng)的核心成員）吧。如果你不熟悉Plan 9，看到這段匯編可能比較懵。小菜刀覺(jué)得沒(méi)必要花過(guò)多時(shí)間去學(xué)懂，因?yàn)樗軓?fù)雜且另類，同時(shí)涉及到很多硬件知識(shí)。不過(guò)如果只是要求看懂簡(jiǎn)單的匯編代碼，稍微研究下還是能夠做到的。
由于本文的重點(diǎn)并不是plan 9，所以這里就只解釋上述匯編代碼的含義。
atomic.Cas(SB)的函數(shù)原型為func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)，其入?yún)?code>addr為8個(gè)字節(jié)（64位系統(tǒng)），old和new分別為4個(gè)字節(jié)，返回參數(shù)swapped為1個(gè)字節(jié)，所以17=8+4+4+1。
FP（Frame pointer: arguments and locals），它是偽寄存器，用來(lái)表示函數(shù)參數(shù)與局部變量。其通過(guò)symbol+offset(FP)的方式進(jìn)行使用。在本函數(shù)中，我們可以把FP指向的內(nèi)容表示為如下所示。
ptr+0(FP)代表的意思就是ptr從FP偏移0byte處取內(nèi)容。AX，BX，CX在這里，知道它們是存放數(shù)據(jù)的寄存器即可。MOV X Y所做的操作是將X上的內(nèi)容復(fù)制到Y上去，MOV后綴L表示“長(zhǎng)字”（32位，4個(gè)字節(jié)），Q表示“四字”（64位，8個(gè)字節(jié)）。
MOVQ ptr+0(FP), BX // 第一個(gè)參數(shù)addr命名為ptr，放入BP(MOVQ，完成8個(gè)字節(jié)的復(fù)制)
MOVL old+8(FP), AX // 第二個(gè)參數(shù)old，放入AX（MOVL，完成4個(gè)字節(jié)的復(fù)制）
MOVL new+12(FP), CX // 第三個(gè)參數(shù)new，放入CX（MOVL，完成4個(gè)字節(jié)的復(fù)制）
重點(diǎn)來(lái)了，LOCK指令。這里參考 Intel 的64位和IA-32架構(gòu)開(kāi)發(fā)手冊(cè)
Causes the processor’s LOCK# signal to be asserted during execution of the accompanying instruction (turns the instruction into an atomic instruction). In a multiprocessor environment, the LOCK# signal ensures that the processor has exclusive use of any shared memory while the signal is asserted.
在多處理器環(huán)境中，指令前綴LOCK能夠確保，在執(zhí)行LOCK隨后的指令時(shí)，處理器擁有對(duì)任何共享內(nèi)存的獨(dú)占使用。
LOCK：是一個(gè)指令前綴，其后必須跟一條“讀-改-寫(xiě)”性質(zhì)的指令，它們可以是ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG。該指令是一種鎖定協(xié)議，用于封鎖總線，禁止其他 CPU 對(duì)內(nèi)存的操作來(lái)保證原子性。
在匯編代碼里給指令加上 LOCK 前綴，這是CPU 在硬件層面支持的原子操作。但這樣的鎖粒度太粗，其他無(wú)關(guān)的內(nèi)存操作也會(huì)被阻塞，大幅降低系統(tǒng)性能，核數(shù)越多愈發(fā)顯著。
為了提高性能，Intel 從 Pentium 486 開(kāi)始引入了粒度較細(xì)的緩存鎖：MESI協(xié)議（關(guān)于該協(xié)議，小菜刀在之前的文章《CPU緩存體系對(duì)Go程序的影響》有詳細(xì)介紹過(guò)）。此時(shí)，盡管有LOCK前綴，但如果對(duì)應(yīng)數(shù)據(jù)已經(jīng)在 cache line里，也就不用鎖定總線，僅鎖住緩存行即可。
LOCK
CMPXCHGL CX, 0(BX)
CMPXCHGL，L代表4個(gè)字節(jié)。該指令會(huì)把AX（累加器寄存器）中的內(nèi)容（old）和第二個(gè)操作數(shù)（0(BX)）中的內(nèi)容（ptr所指向的數(shù)據(jù)）比較。如果相等，則把第一個(gè)操作數(shù)（CX）中的內(nèi)容（new）賦值給第二個(gè)操作數(shù)。
SETEQ ret+16(FP)
RET
這里，SETEQ 與CMPXCHGL是配合使用的，如果CMPXCHGL中比較結(jié)果是相等的，則設(shè)置ret（即函數(shù)原型中的swapped）為1，不等則設(shè)置為0。RET代表函數(shù)返回。
總結(jié)
本文探討了atomic.CompareAndSwapInt32是如何通過(guò)硬件指令LOCK實(shí)現(xiàn)原子性操作的封裝。但要記住，在不同的架構(gòu)平臺(tái)，依賴的機(jī)器指令是不同的，本文僅研究的是amd64下的匯編實(shí)現(xiàn)。
在Go提供的原子操作庫(kù)atomic中，除了CAS還有許多有用的原子方法，它們共同筑起了Go同步原語(yǔ)體系的基石。
func SwapIntX(addr *intX, new intX) (old intX)
func CompareAndSwapIntX(addr *intX, old, new intX) (swapped bool)
func AddIntX(addr *intX, delta intX) (new intX)
func LoadIntX(addr *uintX) (val uintX)
func StoreIntX(addr *intX, val intX)
func XPointer(addr *unsafe.Pointer, val unsafe.Pointer)
那么它們是如何實(shí)現(xiàn)的？小菜刀將它們實(shí)現(xiàn)的關(guān)鍵指令總結(jié)如下。
-
Swap :
XCHGQ -
CAS :
LOCK+CMPXCHGQ -
Add :
LOCK+XADDQ -
Load :
MOVQ -
Store :
XCHGQ - Pointer : 以上指令結(jié)合GC 調(diào)度
這里大家可能會(huì)好奇，Swap和Store會(huì)對(duì)共享數(shù)據(jù)做修改，但是為啥它們沒(méi)有加LOCK，小菜刀對(duì)此也同樣疑惑。不過(guò)，好在 Intel 的64位和IA-32架構(gòu)開(kāi)發(fā)手冊(cè)中給出了答案
If a memory operand is referenced, the processor’s locking protocol is automatically implemented for the duration of the exchange operation, regardless of the presence or absence of the LOCK prefix or of the value of the IOPL
這段話表明，在實(shí)現(xiàn)Swap和Store方法時(shí)，其實(shí)不管是否存在LOCK前綴，在交換操作期間（XCHGQ）將自動(dòng)實(shí)現(xiàn)CPU的鎖定協(xié)議。
另外我們可以發(fā)現(xiàn)，在Load和Store/Swap的實(shí)現(xiàn)中，前者沒(méi)有使用鎖定協(xié)議，而后者需要。兩者結(jié)合，那這不就是一種讀共享，寫(xiě)?yīng)氄嫉乃枷雴幔?/p>
