Go 语言中 sync.Mutex 的实现

锁的获取和释放模式

先理解两种不同的锁的获取和释放模式"Barging" 和 "Handoff"，它们影响着等待锁的 goroutines 的行为。

Barging（插队）

在 Barging 模式下，当一个锁被释放时，任何尝试获取该锁的 goroutine 都有机会立即抢占（"插队"）并尝试获取锁，而不管是否有其他 goroutines 正在等待。这意味着新到达的 goroutine 可能会在等待的 goroutine 之前获取锁，即使那些 goroutine 已经在等待队列中等待了一段时间。

优点：是它可以减少唤醒等待线程的延迟，因为不需要显式地从等待队列中选择一个线程并唤醒它。这可以提高性能，特别是在锁的竞争不是很激烈的情况下。

缺点：是可能导致 "饥饿"，即某些 goroutine 可能会被不断地插队，从而无法及时获取锁。

如上图，Barging 模式既会唤醒等待者 G2，G3 作为新到达的 gorouting 也有机会直接获得锁

Handoff（交接）

在 Handoff 模式下，当一个锁被释放时，持有锁的 goroutine 显式地将锁交给等待队列中的下一个 goroutine。这意味着锁的所有权从释放锁的 goroutine 直接传递给等待队列中的一个特定 goroutine，而不允许其他 goroutine 插队。

优点：是它可以防止饥饿，因为等待时间最长的 goroutine 将被优先考虑。这种模式确保了公平性，因为每个 goroutine 都会按照它们到达等待队列的顺序获得服务。

缺点：可能会引入额外的延迟，因为需要显式地管理等待队列，并在每次释放锁时唤醒特定的 goroutine。

如上图，Handoff 模式唤醒等待队列中的 G2，之后直接把锁交接给 G2，即使唤醒过程中 G3、G4 正在请求锁

Go 语言中的实现

在 Go 语言的 sync.Mutex 实现中，为了平衡性能和公平性，采用了一种混合的策略。在某些情况下，它允许 Barging，以减少唤醒等待 goroutine 的开销；在其他情况下，它使用 Handoff，以确保长时间等待的 goroutine 最终能够获取锁，从而防止饥饿。

Go 1.9 引入了一些改进，使得 sync.Mutex 更加倾向于公平性，通过引入一个饥饿状态，当一个 goroutine 等待超过一定的时间阈值（1ms）时，它会进入饥饿状态。在饥饿状态下，锁的所有权会直接从解锁的 goroutine 交给等待队列中的下一个 goroutine，这类似于 Handoff 模式。当没有 goroutine 处于饥饿状态时，锁的获取更加自由，可能会出现 Barging。

这种混合策略旨在在高并发场景下提供良好的性能，同时在锁竞争激烈时保持足够的公平性，以避免饥饿问题。

自旋

自旋（spinning）是一种优化技术，用于在某些情况下避免 goroutine 在等待锁时立即进入休眠状态。自旋可以让 goroutine 在短时间内忙等（busy-wait），以期在这段时间内锁被释放，从而避免了系统调用的开销和上下文切换的成本。

自旋在 Go 的 sync.Mutex 中是这样使用的：

自旋尝试：当一个 goroutine 尝试获取一个已经被其他 goroutine 持有的锁时，它会执行一个有限次数的自旋尝试。在这个过程中，goroutine 会在用户空间中忙等，检查锁是否已经被释放。

退让：如果在自旋尝试期间锁没有被释放，goroutine 可能会调用 runtime.Gosched() 或类似的函数来让出 CPU 时间片，给其他 goroutine 执行的机会。这样做可以减少 CPU 的无效消耗，尤其是在单核心或者核心数较少的情况下。

阻塞：如果自旋后锁仍然不可用，goroutine 最终会停止自旋，并通过更重的同步机制（如 futex 或其他内核同步原语）进入休眠状态，等待被唤醒。

自旋与 Barging 和 Handoff 模式的关系

与 Barging 的关系：自旋与 Barging 模式结合得很好，因为在 Barging 模式下，锁一旦被释放，任何 goroutine 都有机会获取它。因此，自旋的 goroutine 可能会在锁释放时立即获取到锁，而不需要被唤醒。

与 Handoff 的关系：在 Handoff 模式下，锁的所有权直接从释放锁的 goroutine 传递给等待队列中的下一个 goroutine。在这种情况下，自旋可能不那么有效，因为锁的获取是预定的，不会立即发生。但是，如果等待队列中没有饥饿的 goroutine，那么自旋的 goroutine 仍然有机会在锁释放时立即获取它。

Go 语言的运行时会根据当前的情况（如锁的竞争程度和处理器的数量）来决定是否使用自旋，以及自旋的次数。这是一个经过调优的决策，目的是在减少延迟和避免浪费 CPU 资源之间找到平衡点。

sync_runtime_canSpin 判断是否可以进入自旋

// Active spinning for sync.Mutex.
//go:linkname sync_runtime_canSpin sync.runtime_canSpin
//go:nosplit
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.
    if i >= active_spin || ncpu <= 1 || gomaxprocs <= int32(sched.npidle+sched.nmspinning)+1 {
        return false
    }
    if p := getg().m.p.ptr(); !runqempty(p) {
        return false
    }
    return true
}

如果可以自选，就通过 sync_runtime_doSpin 进入自旋，对应执行 30 次 PAUSE 指令

PAUSE 指令会告诉 CPU 我当前处于处于自旋状态，这时候 CPU 会针对性的做一些优化，并且在执行这个指令的时候 CPU 会降低自己的功耗，减少能源消耗

//go:linkname sync_runtime_doSpin sync.runtime_doSpin
//go:nosplit
func sync_runtime_doSpin() {
    procyield(active_spin_cnt)
}

TEXT runtime·procyield(SB),NOSPLIT,$0-0
    MOVL    cycles+0(FP), AX
again:
    PAUSE
    SUBL    $1, AX
    JNZ    again
    RET

Mutex 源码结构

// A Mutex is a mutual exclusion lock.
// The zero value for a Mutex is an unlocked mutex.
//
// A Mutex must not be copied after first use.
type Mutex struct {
    state int32
    sema  uint32
}

mutexLocked = 1 << iota // mutex is locked
mutexWoken
mutexStarving
mutexWaiterShift = iota

state：4 字节的 Int32 类型，最低的 3 个 bit 表示锁的状态，分别是 mutexLocked mutexWoken mutexStarving ，剩下的 bit 用于统计当前在等待锁的 goroutine 数量

sema：控制 gorouting 在获取锁过程当中的休眠和唤醒，在 Linux 系统中，信号量可以通过多种方式实现，其中之一是使用 "futex"（快速用户空间互斥锁）。futex 是一种系统调用，它提供了一种在用户空间线程之间进行高效等待和唤醒的机制

Lock 方法

Fast Path：首先尝试一个快速路径，如果锁是空闲的（state 为 0），就通过原子操作 CompareAndSwapInt32 尝试将其设置为 mutexLocked 状态。如果成功，就直接返回，表示获取锁成功。

Slow Path：如果快速路径失败，表示锁已经被其他 goroutine 持有，那么就进入慢路径。在慢路径中，会有一个循环，goroutine 会在这里等待，直到它能够获取锁。

Starvation Detection: 代码中有对饥饿状态的检测，如果一个 goroutine 长时间等待锁，它可能会进入饥饿模式，这时它会被优先唤醒。

Waiters Counting: 如果锁已经被持有，goroutine 会增加等待者的计数，并可能进入休眠状态，等待锁被释放。

Waking Up: 当锁被释放时，等待的 goroutine 会被唤醒。如果有多个等待者，唤醒操作会尝试保持公平性，避免某些 goroutine 饥饿。

Unlock 方法

Fast Path: 通过原子操作减少 state 的值来释放锁。如果减少后的值表明锁已经是未锁定状态，那么会抛出 panic，因为这意味着试图释放一个未锁定的互斥锁。

No Waiters: 如果没有等待者，或者已经有一个 goroutine 被唤醒或处于饥饿状态，那么就没有必要进行唤醒操作。

Wake Someone Up: 如果有等待者，那么会释放一个信号量 sema 来唤醒一个等待的 goroutine。

参考：

1. https://lailin.xyz/post/go-training-week3-sync.html#RWMutex

2. https://pkg.go.dev/sync

标签：唤醒,goroutine,sync,Mutex,自旋,Go,等待
From： https://www.cnblogs.com/orchidzjl/p/18136167