GolangMutex实现互斥的具体方法

2023-05-17 11:05:11 方法 互斥 GolangMutex

Mutex是golang常见的并发原语,不仅在开发过程中经常使用到,如channel这种具有Golang特色的并发结构也依托于Mutex从而实现

type Mutex struct {
  // 互斥锁的状态,比如是否被锁定
  state int32
  // 表示信号量。堵塞的协程会等待该信号量,解锁的协程会释放该信号量
  sema int32
}
const (
  // 当前是否已经上锁
  mutexLocked = 1 << iota // 1
  // 当前是否有唤醒的goroutine
  mutexWoken // 2
  // 当前是否为饥饿状态
  mutexStarving // 4
  // state >> mutexWaiterShift 得到等待者数量
  mutexWaiterShift = iota // 3

  starvationThresholdNs = 1e6 // 判断是否要进入饥饿状态的阈值
)

Mutex有正常饥饿模式。

  • 正常模式:等待者会入队,但一个唤醒的等待者不能持有锁,以及与新到来的goroutine进行竞争。新来的goroutine有一个优势——他们已经运行在CPU上。
    超过1ms没有获取到锁,就会进入饥饿模式
  • 饥饿模式:锁的所有权直接移交给队列头goroutine,新来的goroutine不会尝试获取互斥锁,即使互斥锁看起来已经解锁,也不会尝试旋转。相反,他们自己排在等待队列的末尾。

若等待者是最后一个,或者等待小于1ms就会切换回正常模式

获取锁

未锁——直接获取

func (m *Mutex) Lock() {
    // 快路径。直接获取未锁的mutex
  // 初始状态为0,所以只要状态存在其他任何状态位都是无法直接获取的
    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()
}

在不饥饿且旋的不多的情况下,尝试自旋

        // 只要原状态已锁且不处于饥饿状态,并满足自旋条件
        if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
            // 在当前goroutine没有唤醒,且没有其他goroutine在尝试唤醒,且存在等待的情况下,cas标记存在goroutine正在尝试唤醒。若标记成功就设置当前goroutine已经唤醒了
            if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
                atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
                awoke = true
            }
      // 自旋
            runtime_doSpin()
      // 自旋次数加一
            iter++
      // 更新原状态
            old = m.state
            continue
        }

具体的自旋条件如下

  • 自旋次数小于4
  • 多核CPU
  • p数量大于1
  • 至少存在一个p的队列为空
const (
    locked uintptr = 1

    active_spin     = 4
    active_spin_cnt = 30
    passive_spin    = 1
)

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
}

自旋究竟在做什么呢?

自旋是由方法runtime_doSpin()执行的,实际调用了procyield()

# 定义了一个runtime.procyield的文本段,通过NOSPLIT不使用栈分裂,$0-0 表示该函数不需要任何输入参数和返回值
TEXT runtime·procyield(SB),NOSPLIT,$0-0
    # 从栈帧中读取cycles参赛值,并储存在寄存器R0中
    MOVWU    cycles+0(FP), R0
# 组成无限循环。在每次循环中,通过YIELD告诉CPU将当前线程置于休眠状态
# YIELD: x86上,实现为PAUSE指令,会暂停处理器执行,切换CPU到低功耗模式并等待更多数据到达。通常用于忙等待机制,避免无谓CPU占用
# ARM上,实现为WFE(Wait For Event),用于等待中断或者其他事件发生。在某些情况下可能会导致CPU陷入死循环,因此需要特殊处理逻辑解决
again:
    YIELD
    # 将R0值减1
    SUBW    $1, R0
    # CBNZ(Compare and Branch on Non-Zero)检查剩余的时钟周期数是否为0。不为0就跳转到标签again并再次调用YIELD,否则就退出函数
    CBNZ    R0, again
    RET

以上汇编代码分析过程感谢chatgpt的大力支持

从代码中可以看到自旋次数是30次

const active_spin_cnt = 30

func sync_runtime_doSpin() {
    procyield(active_spin_cnt)
}

计算期望状态

1.原状态不处于饥饿状态,新状态设置已锁状态位

原状态处于已锁状态或饥饿模式,新状态设置等待数量递增

当前goroutine是最新获取锁的goroutine,在正常模式下期望就是要获取锁,那么就应该设置新状态已锁状态位

如果锁已经被抢占了,或者处于饥饿模式,那么就应该去排队

2.若之前尝试获取时已经超过饥饿阈值时间,且原状态已锁,那么新状态设置饥饿状态位

3.若goroutine处于唤醒,则新状态清除正在唤醒状态位

期望是已经获取到锁了,那么自然要清除正在获取的状态位

        new := old
        // Don't try to acquire starving mutex, new arriving goroutines must queue.
    // 若原状态不处于饥饿状态,就给新状态设置已加锁
        if old&mutexStarving == 0 {
            new |= mutexLocked
        }
    // 只要原状态处于已锁或者饥饿模式,就将新状态等待数量递增
        if old&(mutexLocked|mutexStarving) != 0 {
            new += 1 << mutexWaiterShift
        }
    // 若已经等待超过饥饿阈值时间且原状态已锁,就设置新状态为饥饿
    // 这也意味着如果已经不处于已锁状态,就可以切换回正常模式了
        if starving && old&mutexLocked != 0 {
            new |= mutexStarving
        }
    // 如果已经唤醒了(也就是没有其他正在抢占的goroutine),则在新状态中清除正在唤醒状态位
        if awoke {
            // The goroutine has been woken from sleep,
            // so we need to reset the flag in either case.
            if new&mutexWoken == 0 {
                throw("sync: inconsistent mutex state")
            }
            new &^= mutexWoken
        }

尝试达成获取锁期望

cas尝试从原状态更新为新的期望状态

如果失败,则更新最新状态,继续尝试获取锁

说明这期间锁已经被抢占了

若原来既没有被锁住,也没有处于饥饿模式,那么就获取到锁,直接返回

排队。若之前已经在等待了就排到队列头

获取信号量。此处会堵塞等待

被唤醒,认定已经持有锁。并做以下饥饿相关处理

  • 计算等待时长,若超出饥饿阈值时间,就标记当前goroutine处于饥饿
  • 若锁处于饥饿模式,递减等待数量,并且在只有一个等待的时候,切换锁回正常模式
if atomic.CompareAndSwapInt32(&m.state, old, new) {
      // 如果原状态既没有处于已锁状态,也没有处于饥饿模式
      // 那么就表示已经获取到锁,直接退出
            if old&(mutexLocked|mutexStarving) == 0 {
                break // locked the mutex with CAS
            }
      // 若已经在等待了,就排到队列头
            queueLifo := waitStartTime != 0
            if waitStartTime == 0 {
                waitStartTime = runtime_nanotime()
            }
      // 尝试获取信号量。此处获取一个信号量以实现互斥
      // 此处会进行堵塞
            runtime_SemacquireMutex(&m.sema, queueLifo, 1)
      // 被信号量唤醒之后,发现若等待时间超过饥饿阈值,就切换到饥饿模式
            starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
            old = m.state
      // 处于饥饿模式下
            if old&mutexStarving != 0 {
                // If this goroutine was woken and mutex is in starvation mode,
                // ownership was handed off to us but mutex is in somewhat
                // inconsistent state: mutexLocked is not set and we are still
                // accounted as waiter. Fix that.
        // 若既没有已锁且正在尝试唤醒,或者等待队列为空,就代表产生了不一致的状态
                if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
                    throw("sync: inconsistent mutex state")
                }
        // 当前goroutine已经获取锁,等待队列减1;若等待者就一个,就切换正常模式。退出
                delta := int32(mutexLocked - 1<<mutexWaiterShift)
                if !starving || old>>mutexWaiterShift == 1 {
                    delta -= mutexStarving
                }
                atomic.AddInt32(&m.state, delta)
                break
            }
      // 不处于饥饿模式下,设置当前goroutine为唤醒状态,重置自璇次数,继续尝试获取锁
            awoke = true
            iter = 0
        } else {
      // 若锁被其他goroutine占用了,就更新原状态,继续尝试获取锁
            old = m.state
        }

考虑几种场景

  • 如果lock当前只有一个goroutine g1去获取锁,那么会直接快路径,cas更新已锁状态位,获取到锁
  • 如果锁已经被g1持有,
    • 此时g2会先自旋4次,
    • 然后计算期望状态为已锁、等待数量为1、唤醒状态位被清除
    • 在cas更新的时候尝试更新锁状态成功,接着因为原状态本身处于已锁,所以就不能获取到锁,只能排队,信号量堵塞
    • g1释放锁后,g2被唤醒,接着再次计算期望状态,并cas更新状态成功,直接获取到锁
  • 如果锁已经被g1持有,且g2在第一次尝试获取时超过了1ms(也就是饥饿阈值),那么
    • 计算期望状态为已锁、饥饿、清除唤醒状态位
    • cas更新状态成功,排在队列头,并被信号量堵塞
    • g1释放锁后,g2被唤醒就直接获取到锁,并减去排队数量以及清空饥饿位

释放锁

只有已锁——直接释放

如果没有排队的goroutine,没有处于饥饿状态,也没有真正尝试获取锁的goroutine,那么就可以直接cas更新状态为0

func (m *Mutex) Unlock() {
    // Fast path: drop lock bit.
    new := atomic.AddInt32(&m.state, -mutexLocked)
    if new != 0 {
        // Outlined slow path to allow inlining the fast path.
        // To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock.
        m.unlockSlow(new)
    }
}

慢释放

  • 如果原锁没有被锁住,就报错
  • 若原状态不处于饥饿状态,尝试唤醒等待者
    • 若现在锁已经被获取、正在获取、饥饿或者没有等待者,直接返回
    • 期望状态等待数量减1,并设置正在唤醒状态位
    • cas尝试更新期望状态,若成功,释放
    • 失败说明在这过程中又有goroutine在尝试获取,那么继续下一轮释放
  • 处于饥饿状态,直接释放信号量,移交锁所有权
func (m *Mutex) unlockSlow(new int32) {
  // 若原状态根本没有已锁状态位
    if (new+mutexLocked)&mutexLocked == 0 {
        throw("sync: unlock of unlocked mutex")
    }
  // 若原状态不处于饥饿状态
    if new&mutexStarving == 0 {
        old := new
        for {
      // 若没有等待,或者存在goroutine已经被唤醒,或者已经被锁住了,就不需要唤醒任何人,返回
            if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
                return
            }
            // Grab the right to wake someone.
      // 设置期望状态为正在获取状态位,并减去一个等待者
            new = (old - 1<<mutexWaiterShift) | mutexWoken
      // 尝试cas更新为期望新状态,若成功就释放信号量,失败就更新原状态,进行下一轮释放
      // 失败说明在这过程中又有goroutine在尝试获取,比如已经获取到了、变成饥饿了、自旋等
            if atomic.CompareAndSwapInt32(&m.state, old, new) {
                runtime_Semrelease(&m.sema, false, 1)
                return
            }
            old = m.state
        }
    } else {
    // 饥饿模式下就移交锁所有权给下一个等待者,并放弃时间片,以便该等待者可以快速开始
        runtime_Semrelease(&m.sema, true, 1)
    }
}

到此这篇关于Golang Mutex实现互斥的具体方法的文章就介绍到这了,更多相关Golang Mutex互斥内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!

相关文章