乐趣区

关于golang:Go同步原语的基石

jiezi

Go 是一门以并发编程见长的语言，它提供了一系列的同步原语不便开发者应用，例如 sync 包下的 Mutex、RWMutex、WaitGroup、Once、Cond，以及形象层级更高的Channel。然而，它们的实现基石是原子操作。须要记住的是： 软件原子操作离不开硬件指令的反对 。本文拟通过探讨原子操作—— 比拟并替换 (compare and swap, CAS) 的实现，来了解 Go 是如何借助硬件指令来实现这一过程的。

什么是 CAS

在看源码实现之前，咱们先了解一下 CAS。

维基百科定义：CAS 是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而 防止多线程同时改写某一数据时因为执行程序不确定性以及中断的不可预知性产生的数据不统一问题。该操作通过将内存中的值与指定数据进行比拟，当数值一样时将内存中的数据替换为新的值。

CAS 的实现思维能够用以下伪代码示意

bool Cas(int *val, int old, int new)
 Atomically:
    if(*val == old){
        *val = new;
        return 1;
    } else {return 0;}

在 sync/atomic/doc.go 中，定义了一系列原子操作函数原型。以 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)
}

它的执行后果如下

 $ go run main.go
100 true
100 false

CAS 能做什么

CAS 从线程层面来说，它是非阻塞的，其乐观地认为在数据更新期间没有其余线程影响，因而也经常被称为是一种轻量级的乐观锁。它关注的是并发平安，而并非并发同步。

在文章结尾时，咱们就曾经提到原子操作是实现下层同步原语的基石。以互斥锁为例，为了不便了解，咱们在这里将它的状态定义为 0 和 1，0 代表目前该锁闲暇，1 代表已被加锁。那么，这个时候，CAS 就是治理状态的最佳抉择，以下是 sync.Mutex 中Lock办法的局部实现代码。

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代表锁的状态，通过 CAS 函数，判断锁此时的状态是否闲暇（m.state==0），是，则对其加锁（这里 mutexLocked 的值为 1）。

源码解读

同样还是以 CompareAndSwapInt32 为例，它在 sync/atomic/doc.go 中定义的函数原型如下

func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)

对应的汇编代码位于 sync/atomic/asm.s 中

TEXT ·CompareAndSwapInt32(SB),NOSPLIT,$0
    JMP    runtime∕internal∕atomic·Cas(SB)

通过指令 JMP，跳转到它的理论实现runtime∕internal∕atomic·Cas(SB)。这里须要留神的是，因为架构体系差别，其汇编实现也会存在差异。在本文，咱们就以常见的amd64 为例，因而进入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 的，我想是因为 Ken Thompson（他是Plan 9 操作系统的核心成员）吧。如果你不相熟Plan 9，看到这段汇编可能比拟懵。小菜刀感觉没必要花过多工夫去学懂，因为它很简单且另类，同时波及到很多硬件常识。不过如果只是要求看懂简略的汇编代码，略微钻研下还是可能做到的。

因为本文的重点并不是 plan 9，所以这里就只解释上述汇编代码的含意。

atomic.Cas(SB)的函数原型为 func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)，其入参addr 为 8 个字节（64 位零碎），old和 new 别离为 4 个字节，返回参数 swapped 为 1 个字节，所以 17=8+4+4+1。

FP（Frame pointer: arguments and locals），它是伪寄存器，用来示意函数参数与局部变量。其通过 symbol+offset(FP) 的形式进行应用。在本函数中，咱们能够把 FP 指向的内容示意为如下所示。

ptr+0(FP)代表的意思就是 ptr 从 FP 偏移 0byte 处取内容。AX，BX，CX在这里，晓得它们是存放数据的寄存器即可。MOV X Y所做的操作是将 X 上的内容复制到 Y 下来，MOV后缀 L 示意“长字”（32 位，4 个字节），Q示意“四字”（64 位，8 个字节）。

 MOVQ     ptr+0(FP), BX  // 第一个参数 addr 命名为 ptr，放入 BP(MOVQ，实现 8 个字节的复制)
 MOVL     old+8(FP), AX  // 第二个参数 old，放入 AX（MOVL，实现 4 个字节的复制）MOVL     new+12(FP), CX // 第三个参数 new，放入 CX（MOVL，实现 4 个字节的复制）

重点来了，LOCK指令。这里参考 Intel 的 64 位和 IA-32 架构开发手册

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.

在多处理器环境中，指令前缀 LOCK 可能确保，在执行 LOCK 随后的指令时，处理器领有对任何共享内存的独占应用。

LOCK：是一个指令前缀，其后必须跟一条“读 - 改 - 写 ”性质的指令，它们能够是ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, CMPXCHG16B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, XCHG。该指令是一种锁定协定，用于封闭 总线，禁止其余 CPU 对内存的操作来保障原子性。

在汇编代码里给指令加上 LOCK 前缀，这是 CPU 在 硬件层面反对的原子操作 。但这样的锁 粒度太粗 ，其余无关的内存操作也会被阻塞，大幅 升高零碎性能，核数越多愈发显著。

为了进步性能，Intel 从 Pentium 486 开始引入了粒度较细的 缓存锁：MESI 协定（对于该协定，小菜刀在之前的文章《CPU 缓存体系对 Go 程序的影响》有具体介绍过）。此时，只管有 LOCK 前缀，但如果对应数据曾经在 cache line 里，也就不必锁定总线，仅锁住缓存行即可。

    LOCK
    CMPXCHGL    CX, 0(BX)

CMPXCHGL，L代表 4 个字节。该指令会把 AX（累加器寄存器）中的内容（old）和第二个操作数（0(BX)）中的内容（ptr 所指向的数据）比拟。如果相等，则把第一个操作数（CX）中的内容（new）赋值给第二个操作数。

 SETEQ    ret+16(FP)
 RET

这里，SETEQ 与 CMPXCHGL 是配合应用的，如果 CMPXCHGL 中比拟后果是相等的，则设置 ret（即函数原型中的swapped）为 1，不等则设置为 0。RET 代表函数返回。

总结

本文探讨了 atomic.CompareAndSwapInt32 是如何通过硬件指令 LOCK 实现原子性操作的封装。但要记住，在不同的架构平台，依赖的机器指令是不同的，本文仅钻研的是 amd64 下的汇编实现。

在 Go 提供的原子操作库 atomic 中，除了 CAS 还有许多有用的原子办法，它们独特筑起了 Go 同步原语体系的基石。

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)

那么它们是如何实现的？小菜刀将它们实现的要害指令总结如下。

  • Swap : XCHGQ
  • CAS : LOCK+ CMPXCHGQ
  • Add : LOCK + XADDQ
  • Load : MOVQ
  • Store : XCHGQ
  • Pointer : 以上指令联合 GC 调度

这里大家可能会好奇，Swap和 Store 会对共享数据做批改，然而为啥它们没有加LOCK，小菜刀对此也同样纳闷。不过，好在 Intel 的 64 位和 IA-32 架构开发手册中给出了答案

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

这段话表明，在实现 Swap 和Store办法时，其实不论是否存在 LOCK 前缀，在替换操作期间（XCHGQ）将主动实现 CPU 的锁定协定。

另外咱们能够发现，在 Load 和Store/Swap的实现中，前者没有应用锁定协定，而后者须要。两者联合，那这不就是一种读共享，写独占的思维吗？

退出移动版