Golang Mutex

Mutex实现原理

Mutex的设计参照了 plan9, linux也有相关实现: futex

先看mutex.go的注释:

    // Mutex fairness.
    //
    // Mutex can be in 2 modes of operations: normal and starvation.
    // In normal mode waiters are queued in FIFO order, but a woken up waiter
    // does not own the mutex and competes with new arriving goroutines over
    // the ownership. New arriving goroutines have an advantage -- they are
    // already running on CPU and there can be lots of them, so a woken up
    // waiter has good chances of losing. In such case it is queued at front
    // of the wait queue. If a waiter fails to acquire the mutex for more than 1ms,
    // it switches mutex to the starvation mode.
    //
    // In starvation mode ownership of the mutex is directly handed off from
    // the unlocking goroutine to the waiter at the front of the queue.
    // New arriving goroutines don't try to acquire the mutex even if it appears
    // to be unlocked, and don't try to spin. Instead they queue themselves at
    // the tail of the wait queue.
    //
    // If a waiter receives ownership of the mutex and sees that either
    // (1) it is the last waiter in the queue, or (2) it waited for less than 1 ms,
    // it switches mutex back to normal operation mode.
    //
    // Normal mode has considerably better performance as a goroutine can acquire
    // a mutex several times in a row even if there are blocked waiters.
    // Starvation mode is important to prevent pathological cases of tail latency.

其实, 就是在处理锁的公平性的问题. 普通模式下, 其实就是不公平的, 因为后来的goroutine可能会持有锁, 饥饿模式下, 就是公平的, 因为后来的活跃的goroutine一定是在先放到队列的尾部, 并不会进行自旋或者拿锁.

看下Mutex的结构:

type Mutex struct {
    state int32
    sema  uint32
}

其中, state表示当前的状态, 比如 mutexLocked、mutexWoken、mutexStarving、mutexWaiterShiftstarvationThresholdNs, 通过atomic.CompareAndSwapInt32 实现状态的变更, 判断是否抢锁成功. sema 是抢锁过程中操作的对象, 通过对sema的cas操作表示是否抢占成功. 常用的几个函数的实现:

Lock: 原子更新状态lock, 失败直接返回. 第一次不进行排队, 尝试抢锁(参看下面sema实现原理). 针对唤醒、饥饿模式、自旋做了实现. (自旋的goroutine是直接排到队列前面的)
Unlock: 去除锁状态, 释放锁(参看下面sema实现原理). 注意在starving模式下, 释放锁会唤醒下一个goroutine, 非starving模式下, 不进行唤醒.(唤醒下一个的操作在 semacquire1 中实现, 通过sudog的ticket实现. Starving -> handoff:true -> ticket==1 -> semacquire1 不进行循环了. NoStarving -> handoff:false -> ticket==0 -> semacquire1 进行循环: 从队列中拿下一个, 尝试抢锁)

Mutex是基于sema实现的, 先关注下 Mutex.

sema 实现原理:

主要的数据结构

type semaRoot struct {
    lock  mutex
    treap *sudog // root of balanced tree of unique waiters.
    nwait uint32 // Number of waiters. Read w/o the lock.
}

var semtable [semTabSize]struct {
    root semaRoot
    pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

通过注释, 在semaRoot的实现中, semaRoot用平衡树的方式组织sudog, sudog在这里表示阻塞在同一个地址上的goroutine, 寻找不同地址的sudog就是log(n)的.系统中使用semtable维护了251个semaRoot。 ??? 怎么维护的 ??? 为啥是这个数字? , nwait维护了等待的goroutine数量.

实现的相关函数:

cansemacquire: 通过对uint32 元素进行cas实现抢锁的功能. 在Mutex的使用场景中, sema初始化是0, 第一次抢Mutex, goroutine是直接成功, 在释放Mutex的时候, sema会递增加一. 保证了并发抢锁情况下 cansemacquire 是可以运行的.
semaRoot#queue: 将元素放入semaRoot的平衡树中.
semaRoot#dequeue: 获取semaRoot指定地址的第一个元素, 涉及到转换到叶子节点
semacquire1: 参照内部注释就可以了:

    // Harder case:
    //  increment waiter count
    //  try cansemacquire one more time, return if succeeded
    //  enqueue itself as a waiter
    //  sleep
    //  (waiter descriptor is dequeued by signaler)

放入等待列表的操作, 就是将sudog放到semaRoot的平衡树+挂起当前goroutine 3. semrelease1: 参考注释:

// Harder case: search for a waiter and wake it.

补充sudog为了支持Mutex的做的实现:

sudog 添加了 waittail 和 waitlink、parent, waittail 指向sema链表里的最后一个元素, 方便实现添加到最后的语义; waitlink指向sema链表中下一个, 方便实现dequeue语义. parent 指向sema二叉树的父节点.
关于runtime_canSpin, 其实链接到 sync_runtime_canSpin, 判断条件参看注释

func sync_runtime_canSpin(i int) bool {
    // sync.Mutex is cooperative, so we are conservative with spinning.
    // Spin only few times and only if running on a multicore machine and
    // GOMAXPROCS>1 and there is at least one other running P and local runq is empty.
    // As opposed to runtime mutex we don't do passive spinning here,
    // because there can be work on global runq or on other Ps.

关于runtime_doSpin, 其实是链接到sync_runtime_doSpin.

问题:

定位semroot 的算法, 不是很理解

func semroot(addr *uint32) *semaRoot {
    return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root
}

Mutex 的sema每次goroutine阻塞、唤醒都要加减1, sema.go中有使用了nwait 表示等待着数量, 是否可以统一呢?

汇编指令

1.cas 汇编指令cas等参考asm_amd64.s, 这里以atomic·Casuintptr为例, 对应的asm代码:

// bool Cas(int32 *val, int32 old, int32 new)
// Atomically:
//  if(*val == old){
//      *val = new;
//      return 1;
//  } else
//      return 0;
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

TEXT runtime∕internal∕atomic·Casuintptr(SB), NOSPLIT, $0-13
    JMP runtime∕internal∕atomic·Cas(SB)

// bool runtime∕internal∕atomic·Cas64(uint64 *val, uint64 old, uint64 new)
// Atomically:
//  if(*val == *old){
//      *val = new;
//      return 1;
//  } else {
//      return 0;
//  }
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 两条汇编指令, 所以, 加锁其实是线程级别的. 这里的细说两个指令. LOCK: 保持缓存行处于 M/E 状态(参看补充知识点). CMPXCHGQ/CMPXCHGL: CMPXCHGL 是32bit操作, CMPXCHG的64bit操作. 但单处理器中, 是不需要切换到Level 0层的. 多核处理器中, 一定是搭配LOCK前缀实现cas操作原子的语义

补充知识点:

MESI缓存协议:

缓存行64byte, 每个缓存行有四种状态:

M[Modified]: 缓存行独占, 尚未写会内存,
E[Exclusive]: 缓存行独占, 与内存一致
S[Shared]: 缓存行多核共享, 与内存一致
I[Invalid]: 使缓存无效

通信多核之间通过L3总线进行通信.
读取流程当一个cpu核的线程准备读取某个缓存行的内容时, 如果状态处于MES,就直接读取; 如果处于I, 就需要和其他cpu核进行通信, 广播读消息,在收到读响应后, 更新缓存行, 并将状态更新成S.
写入流程当一个cpu核的线程准备写入某个缓存行的内容时, 如果状态处于M, 直接写; 如果状态处于E, 直接写入, 更新成M; 如果状态处于S/I, 向其他cpu核广播使无效消息, 转换状态E, 直接写入, 进入M.

汇编指令lock的优化

具体参考: “Locked Atomic Operations” in Chapter 8 in Intel Developer mannual

总线锁. 系统总线锁.
缓存锁: 缓存一致性协议实现缓存的数据结构的原子操作. 对于P6和更新的处理器系列, 如果LOCK操作的内存位置被缓存在处理器中, 并且完全在一个缓存行上, 那么, 在总线上并不会生成LOCK指令, 相反, 内存位置的修改的修改内部执行的, 并使用缓存一致性机制保证操作是原子执行的

参考: