源码分析 GO - Mutex

date
Nov 11, 2023
slug
go-mutex
status
Published
tags
Go
并发
summary
深入浅出 Mutex 的实现。
type
Post
为什么需要 Mutex临界资源和临界区竞态条件Mutex 的使用Mutex 的演变初代 mutex —— 公平锁非公平锁Lock()Unlock()自旋版本Lock()解决饥饿Lock()总结Ref

为什么需要 Mutex

现实中的并发场景很多，如多个用户同时请求一个商品、多个请求写数据、秒杀活动等。此时都需要处理并发问题，不然就会产生预料之外的结果。
互斥锁就是一个常见的解决方法，在 Go 中最基础的互斥锁就是 Mutex。

临界资源和临界区

在介绍 Mutex 之前，我们先了解两个定义：
临界资源
临界资源指的是那些同一时刻只能被一个请求占有的资源，比如说打印机资源、数据库连接等都是临界资源。
临界区
临界区是指访问临界资源的一段代码。
临界区的特点是同一时刻只允许一个请求执行该代码，能够很好的保护临界资源。互斥锁正好能实现这个功能，因为锁同一时刻只能被一个协程持有，持有锁的协程才能进行下一步操作。
多个协程竞争临界资源时，需要竞争，而互斥锁同一时刻只能被一个协程持有，其它竞争不到锁的协程只能等待当前持有锁的协程释放锁后重新竞争，这样就能很好的保护临界资源了。
notion image

竞态条件

其实像上图这样的情形，有一个专门的词来描述：竞态条件（data race）。
静态条件是非常难 debug 的，尤其是我们没有意识到代码会产生并发问题的时候，因此 Go 设计了一个工具名为 Go race detector，它能够在运行时检测出可能存在的 data race 问题。只需要在运行 go 文件的时候加上-race 参数就能使用它来检查并发问题了。
例如我们写一个 counter.go，它使用 10 个协程将cnt 加到 10 万，但是它并没有对cnt 进行加锁保护。
在我本机上输入 $ go run counter.go 后得到的结果是 42685 ，小了快一半。原因很明显，因为 cnt += 1这个操作不是原子的，它会将 cnt 先取出来，然后执行 +1 操作，再设置回 cnt，这个过程中有可能产生冲突，导致没有正确累加。
下面我们尝试用 Go race detector 来检测一下
notion image
这个时候就能看到哪里出现错误啦，很方便很强大。但是我们线上环境尽量避免，因为它的原理是记录内存读写的操作，然后进行分析，所以会有比较大的性能损耗。

Mutex 的使用

像刚刚上面的例子，我们只需要使用 Mutex 就能正确的得到结果了
这个时候再运行，也不会提示 Warning 了，说明我们的 data race 问题消除了。
notion image
如果我们熟悉 go 的话，可以把 Mutex 封装到 strcut 里面，写出更优雅的代码
基本的使用介绍完了，下面我们看看 Mutex 的实现原理吧。

Mutex 的演变

Mutex 其实是经过很多版本演变的，直接看最新版本容易 get 不到有些地方为什么这么设计，我们可以按照时间顺序来学习 Mutex，体会每个版本的迭代目的和它们的特点，这样能够加深印象。
notion image
Mutex 一共经历过四个大的版本，如上图所示，一开始的初版 Mutex 实现了最基本的互斥锁；后续的版本考虑到上下文的切换开销，引入了非公平机制，让新来的 goroutine 有机会能抢到锁；由于非公平锁可能会导致饥饿，最后的版本也是解决了饥饿问题，避免 goroutine 长时间等待。
每个版本的 Mutex 只实现了一个 Locker 接口，里面只有两个函数，非常简单：
这也是 Go 的特点之一，将复杂的逻辑交给实现，而接口只提供最主要的功能，将来我们要设计自己的接口的时候，用这种思想组织接口和实现，会写出更高质量的代码。

初代 mutex —— 公平锁

假如让我们来实现一个最简单的锁，应该怎么做？
一个直观的想法是，通过flag 变量来表示锁是否被持有，1 则表示被持有，此时其它协程只能等待，0 表示锁处于可用状态，率先修改锁为 1 的协程就拥有执行权，而修改可以通过 CAS（compare-and-swap）来实现。
CAS 是一个原子操作，假设 p 是指向对应值内存的指针，old 是在修改未发生之前的值，new 是我们想要修改为的值，那么 CAS 的操作伪代码如下：
基于 flag 和 CAS 操作，我们就能实现一个最简单的锁，事实上 Russ Cox 在 2008 年提交的第一版 Mutex 正是这样的思想。
初学者可能有这样的疑问
这个版本的 Mutex 还是很简单的，没有特别的机制。
变量：
  • key：表示持有锁和等待锁的数量
    • 0 表示锁未被持有
    • 1 表示锁被持有，没有等待者
    • n 表示锁被持有，且有 n - 1 个等待者
  • sema：等待者队列使用的信号量
    • 释放锁的时候，会唤醒 sema 相关的等待者（如果有的话）
notion image
逻辑：
  • Lock，尝试加锁，使用 cas 对 key 操作，如果结果为 1，表示持有成功，否则阻塞等待 sema
  • Unlock，解锁，对 key 操作，如果为 0，则没有等待者可以直接返回，否则唤醒 sema 的等待者
注意：
  • Unlock 没有对调用者做检查，不是锁的持有者也可以释放锁。因此我们一般使用 defer 来进行优化调用
    notion image
    notion image
    这个版本的逻辑很清晰的，但是它存在一个问题，就是请求锁的协程会按照先后顺序排队等待获取互斥锁，也就是公平锁，公平锁的释放和获取必然会涉及到一次 CPU 上下文切换
    对此，非公平锁有一个很大的好处是，如果刚好当前占用 CPU 资源的协程尝试获取锁，那么就会把锁分配给它，这样就能避免一次上下文切换。

    非公平锁

    Lock()

    我们先思考一下，如何在现有的基础上实现非公平锁？
    首先，我们必须要给幸运儿设置一条 fast-path，让它一旦获取到锁就退出。
    其中 state 是当前锁的状态信息，lock 是尝试将 state 转换为加锁状态。
    然后我们需要在这个基础上，增加我们传统锁的获取和释放
    上面的版本，我们实现了 fast-path 和获取锁成功的逻辑，接下来我们实现阻塞和唤醒的逻辑，就完成了非公平锁。
    上面我们添加了阻塞和唤醒的逻辑，我们只要实际调整一下，就能得到最终版本：
    这里有一个位运算技巧： new &^= mutexWoken 这行代码是对 new 变量进行位操作的语法，使用了按位与非（bitwise AND NOT）的操作符 &^=，它被用来清除 变量中的 mutexWoken 标志位。
    相比于公平锁版本，使用 state 替换了 flag， 下面是state的定义：
    state是一个复合型的字段，包含了多个信息，和 java 线程池表示状态的实现很类似。
    • 第一位（低位）表示锁是否被持有
    • 第二位表示是否有唤醒的 goroutine
    • 剩余的位数表示等待此锁的 goroutine
    notion image
    最后我们可以根据代码总结出四种逻辑：
    notion image

    Unlock()

    我们讨论了非公平锁的 Lock() ，下面来看下Unlock()的实现。
    首先，我们还是需要一个 fast-path 来快速解锁
    其中我们要注意三种情况：
    1. 等待者数量为 0 ，意味着不需要唤醒其它协程。
    1. 锁状态已加锁，意味着并发情况下，其它协程已经持有锁，此时不再进行解锁。
    1. 锁已经处于唤醒状态，不需要再次唤醒其他协程。
    我们按照上面的逻辑更新 state，就能得到下面的实现代码：
     

    自旋版本

    自旋（spin）指的是协程会通过循环不断尝试获取锁，超过一定次数后再放弃，进行阻塞等待。也就是说，每个协程会持有 CPU 资源尝试若干次，如果尝试成功了，那么无需上下文切换即可获取到锁。

    Lock()

    首先我们来单独思考下，自旋的逻辑如何设计。
    第一个问题是，多个协程自旋的情况下，如何加锁？
    1. 每个协程尝试直接加锁，加锁成功则获取锁。❌
        2. 这是很直观的想法，但是存在一个很大的问题。多个协程同时识别到无锁状态然后尝试加锁可能引发竞争条件，可能会出现多个协程同时修改锁的状态，从而导致数据不一致性或者出现错误的加锁顺序。
    1. 通过唤醒机制，保证只有一个协程能获取锁。✅
        2. 虽然直接识别到无锁状态然后加锁可能更高效，但需要考虑到并发安全性和数据一致性的问题。因此我们使用间接的唤醒机制来加锁。
    明确了自旋是通过唤醒机制后来获取锁，我们再思考下自旋的过程：
    我们可以根据这个逻辑，画出流程图：
    notion image
    接着，我们可以在非公平锁的基础上实现伪代码：
    接下来我们对伪代码加以完善，就能得到最终的自旋版本：
    可以看到，除了新增的自旋机制外，其余的逻辑基本和非公平锁相同，并且我们的自旋是通过唤醒机制实现的，了解了这一点，我们就能理解上面的加锁代码了。

    解决饥饿

    在极端情况下，有一些协程始终无法获取到锁，这就是饥饿问题。
    为了解决这个问题，Mutex经过了几次修改：
    1. 2016 年 Go 1.9 中 Mutex 增加了饥饿模式，最长等待时间限制在 1 毫秒，并且修复了一个 bug：总是把协程放在等待队列的尾部，这样更容易导致饥饿问题。
    1. 2018 年，拆分 fast-path 和 slow-path 作为独立的方法。
    如下所示：
    1. 2019 年，调度器以更高优先级去执行持有锁的协程，这属于性能优化。
    下面我们来看看目前 Mutex 是如何解决饥饿问题的。

    Lock()

    在这个版本中，state 变得更加复杂：
    notion image
    新增了一个 mutexStarving饥饿标记。
    下面是代码实现：
    饥饿机制是在自旋锁的版本上实现的，只要掌握了自旋锁和饥饿机制，上面的代码就不难理解，总结：
    1. 设置了 1ms 的等待时间来判断是否有协程处于饥饿状态。
    1. 如果尝试获取锁成功
      1. 如果处于饥饿机制，那么必然需要唤醒一个协程
        1. 如果是当前协程饥饿，直接获取锁
        2. 否则，必然有其它饥饿协程获取到锁，关闭饥饿模式
      2. 否则，直接唤醒锁，多个协程进行竞争
    补充 race.Enabled 的含义：
    这行代码是用于 Go 语言中的竞争检测（Race Detection）功能。race.Enabled 是一个布尔类型的变量，用于表示当前程序是否启用了竞争检测。
    如果竞争检测被启用（即 race.Enabled 为真），那么 race.Acquire(unsafe.Pointer(m)) 函数会被调用。race.Acquire 函数用于通知竞争检测器当前协程正在获取一个锁。其中，unsafe.Pointer(m) 表示将互斥锁 m 的指针转换为 unsafe.Pointer 类型，以便在竞争检测器中进行处理。
    竞争检测是 Go 运行时提供的一项强大的工具，用于检测并报告在并发程序中可能导致数据竞争的情况。通过在程序执行过程中对共享变量的访问进行跟踪和分析，竞争检测器可以帮助开发者找到潜在的竞争条件，并提供相关的诊断信息。这有助于开发者在编写高并发程序时发现和修复潜在的并发 bug。

    总结

    Go 的 Mutex 经过以下版本的变更：
    公平锁 → 非公平锁 → 自旋锁 → 避免饥饿
    其中每个版本的特点如下：
    • 公平锁：实现了最基本的锁功能，按照请求锁的顺序进行获取，但可能导致上下文切换频繁。
    • 非公平锁：减少上下文切换，直接分配锁给当前请求的协程。
    • 自旋锁：进一步优化非公平锁，通过若干次自旋去请求锁。
    • 避免饥饿：通过等待时间和饥饿机制，来避免协程饥饿。

    Ref

    Go 并发编程实战课 (geekbang.org)
    什么是临界资源，临界区？ - 知乎 (zhihu.com)
    Introducing the Go Race Detector - The Go Programming Language

    © hhmy 2019 - 2024