八股文-Golang Sync

Golang
,

1.原子操作(sync.atomic包)

sync.atomic包提供低级别的内存原子操作。除非特殊情况，建议还是通过channel或者sync包实现同步。

交换(swap)操作由SwapT函数实现，等同于：

1
2
3
old = *addr
*addr = new
return old

CAS(compare-and-swap)操作由CompareAndSwapT系列函数实现, 等同于：

1
2
3
4
5
if *addr == old {
    *addr = new
    return true
}
return false

add操作由AddT系列函数实现, 等同于：

1
2
*addr += delta
return *addr

load和store操作对应LoadT和StoreT系列函数，等同于return *addr和*addr = val。

在golang内存模型中，如果原子操作A的影响会被原子操作B观察到，那么Asynchronizes beforeB。并且，一个程序中的所有原子操作表现的像是按一定程度的顺序一致性。这个定义和C++的顺序一致原子操作，以及Java里面的volatile一致。

实现上也和Java的老版Atomic*类一致，CAS操作在x86上对应的是cmpxchg指令。

2.同步原语(sync包)

sync包为golang提供了基本的同步原语(synchronization primitive)，不过包里面除了Once和WaitGroup，大部份都是为了低级别库使用。高级同步，golang文档建议是采用channel和通信。

sync包中的基本原语，包括Mutex、RWMutex、WaitGroup、Pool、Map、Once和Cond。

Mutex

Mutex不是公平锁，存在正常模式和饥饿模式两种模式。如果一个 Goroutine 获得了互斥锁并且它在队列的末尾或者它等待的时间少于 1ms，那么当前的互斥锁就会切换回正常模式。正常模式下的互斥锁能够提供更好地性能，饥饿模式的能避免goroutine由于陷入等待无法获取锁而造成的高尾延时。
背景，在初始版本中通过cas和信号量实现，后续版本中出于性能优化，使得新goroutine获取锁的几率大增，导致旧goroutine无法竞争过新的，从而发生饥饿情况。原因是正常模式下，waiter（goroutine）虽然是按FIFO的顺序入队，但是刚唤醒的goroutine不会直接获取到锁，而是去竞争。在这种情况下，与之竞争的新goroutine，会因为已经被CPU执行，更容易获取到锁。
在饥饿模式下，mutex的所有权会直接从解锁的goroutine转交给队首的waiter。新到的goroutine不立刻竞争锁，也不自旋，而是排到队尾。

1
2
3
4
type Mutex struct {
    state int32
    sema  uint32
}

state最低三位分别表示mutexLocked(1)、mutexWoken(2)和mutexStarving(4)，剩下的位置表示当前有多少个goroutine在等待互斥锁的释放。

加锁过程：优先CAS，然后通过自旋+信号量获取锁。
解锁过程：饥饿模式直接将所有权交与下一个waiter，普通模式直接返回，或者通过信号量唤醒其他waiter。

RWMutex

1
2
3
4
5
6
7
type RWMutex struct {
    w           Mutex        // held if there are pending writers
    writerSem   uint32       // semaphore for writers to wait for completing readers
    readerSem   uint32       // semaphore for readers to wait for completing writers
    readerCount atomic.Int32 // number of pending readers
    readerWait  atomic.Int32 // number of departing readers
}

RWMutex.w负责写锁的互相阻塞。
RWMutex.readerCount标识goroutine的读锁数量。每次goroutine获得读锁，readerCount+1。如果写锁被获取，那么readerCount在-rwmutexMaxReaders与0之间。如果写锁未被获取，那么readerCount>=0，获取读锁，不阻塞。
在RWMutex.readerCount为负，也就是存在写锁的情况下，写锁Unlock时会释放读锁的信号量RWMutex.readerSem，读锁RUnlock的时候会释放写锁的信号量RWMutex.writerSem。（读锁不互相阻塞， 因此不需要信号量。写锁互相阻塞会通过RWMutex.w实现）

WaitGroup

WaitGroup除noCopy字段，有意义的属性有三个：waiter、counter和sema。（本来是[3]unit32来存储，1.18版本进行拆分为uint64和uint32）

1
2
3
4
5
6
type WaitGroup struct {
    noCopy noCopy // 编译器负责WaitGroup不被复制

    state atomic.Uint64 // high 32 bits are counter, low 32 bits are waiter count.
    sema  uint32
}

和Java的CountDownLatch功能类似，区别在于CountDownLatch初始化之后不能+1。常见使用模式：

1
2
3
4
5
6
7
8
9
10
11
requests := []*Request{...}
wg := &sync.WaitGroup{}
wg.Add(len(requests))

for _, request := range requests {
    go func(r *Request) {
        defer wg.Done()
        // res, err := service.call(r)
    }(request)
}
wg.Wait()

Once

Once确保golang程序运行期间的某段代码只会执行一次。

数据结构如下，通过Mutex和完成标识来实现。

type Once struct {
done uint32
m Mutex
}

Cond

go提供的条件变量，用途和Java中的synchronized类似。Wait用于等待，Broadcast和Signal分别解锁全部和单个。

不推荐使用，建议是用channel替换。

Pool

golang提供的对象池，可以通过服用对象，减轻gc的压力。

每个P（GMP模型中的P）都绑定一个本地对象池poolLocal。除本地对象池外，每个P还有一个本地对象private用于快速读写。
本地对象为空的时候，从P对应本地对象池中获取，失败后则从其他P的对象池偷。返还时若本地对象存在，则将返还对象放到对象池中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type Pool struct {
    noCopy noCopy

    local     unsafe.Pointer // 本地对象池指针，实际类型是[P]poolLocal，每个P的指针指向对应地址，方便后续窃取
    localSize uintptr        // local的大小

    victim     unsafe.Pointer // 上次循环的local。gc开始时的stop world会将Pool的local迁移至victim
    victimSize uintptr        // victim的大小

    New func() any
}

// Local per-P Pool appendix.
type poolLocalInternal struct {
    private any       // Can be used only by the respective P.
    shared  poolChain // Local P can pushHead/popHead; any P can popTail.
}

type poolLocal struct {
    poolLocalInternal

    // Prevents false sharing on widespread platforms with
    // 128 mod (cache line size) = 0 .
    pad [128 - unsafe.Sizeof(poolLocalInternal{})%128]byte
}

Map

Map是线程安全版本的map[interface{}]interface{}，通过读写分离实现，适用于读多写少(或者goroutine间读写不冲突)的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type Map struct {
    mu Mutex

    read atomic.Pointer[readOnly]
    dirty map[any]*entry

    misses int
}

type readOnly struct {
    m       map[any]*entry
    amended bool // true if the dirty map contains some key not in m.
}

var expunged = new(any)

type entry struct {
    p atomic.Pointer[any]
}

互斥量mu保护read和dirty。
dirty是一个非线程安全的原始map，包含新写入的 key，和read中的所有未被删除的key。通过CAS，可以快速地将dirty提升为read对外提供服务。如果dirty为nil，那么下一次写入时，会新建一个新的dirty，遍历read中未删除（非nil）的entry，迁移至dirty，同时将read的entry指针设置为expunged。

每当从read中读取失败，都会将misses的计数值加 1。当加到一定阈值以后，将dirty提升为read，目前阈值为len(dirty)。

entry对read和dirty都是可见的。指针p的状态有三种：

  • 当p == nil时，说明这个键值对已被删除；此时dirty == nil或者dirty[key]指向当前entry。
  • 当p == expunged时，说明这条键值对已被删除；此时dirty != nil，且dirty[key] == nil。
  • 其他情况，p指向实际 interface{} 的地址。此时read.m[key]和dirty[key]实际上指向的是同一个值。