Go: 关于锁的1234

在上一篇《 踩坑记:Go服务灵异panic 》里我们提到了 mutex 和 atomic ,感觉意犹未尽,这篇再展开一点。

– 锁 –

前面我们讲过好多面试题了,其实锁也很适合用来做套题,比如可以这么切入:sync.Mutex 是悲观锁还是乐观锁?

有些候选人不了解它们的区别,回答靠猜,缺乏逻辑以至于我都记不住。虽然这只是一个概念性的知识,但是却很能反映候选人的工作经验,比如 读多写少的并发场景,乐观锁可以减少加锁冲突带来的开销

当然大多数人还是知道的,于是可以继续问:你有了解过锁是怎么实现的吗?

很多人都能想到:维护一个初值为 false 的变量,当一个线程加锁成功的时候,将它置为 true ,就可以保证其他线程无法再获取。

逻辑是没错,但真正的问题是:两个线程同时检查,发现它的值都是 false ,如何保证只有一个线程会把它置为 true 呢?

这样的提问让不少候选人意识到,自己其实并没有真正理解锁。

– 原子操作 –

学过 操作系统原理 的同学应该都知道,靠的是 原子操作 (atomic operations)。

那么具体是什么原子操作呢?

在早期只有 单核 的系统上只需要关闭中断就可以保证原子地执行一段代码 —— 但这通常效率较低,且还存在些问题,例如因为 bug 或恶意代码导致未能正常开启中断,系统就会锁死;而对于多核系统,通常也无法做到在多个核心上同时关闭中断。

因此 CPU 引入了 硬件支持的原子操作 ,例如 x86 体系下的 LOCK 信号 (在汇编里给指令加上 LOCK 前缀),通过 锁定总线 ,禁止其他 CPU 对内存的操作来保证原子性。但这样的锁 粒度太粗 ,其他无关的内存操作也会被阻塞,大幅 降低系统性能 ,而随着核数逐渐增加该问题会愈发显著 —— 要知道现在连家用 CPU 都有16核了。

因此 Intel 在 Pentium 486 开始引入了 用于保证缓存一致性的 MESI 协议 ,通过锁定对应的 cache line,使得其他 core 无法修改指定内存,从而实现了原子操作( 缓存锁 )。这里不展开了,对细节感兴趣的话,详见参考资料《原子操作是如何实现的》[1]。

– CAS –

针对前面问的“什么原子操作”,大多数候选人的回答是 CAS (compare-and-swap),也有人会提到 test-and-set 等其他操作,原理都一样,就是用前述机制实现的。

下面这段 Go 代码展示了 CAS 的逻辑:

func CompareAndSwap(p *int, oldValue int, newValue int) bool {
  if *p != oldValue {
    return false
  }
  *p = newValue
  return true
}

请注意: 这不是 CAS 的实现 ,如前所述,真正的 CAS 是硬件级别的指令支持的,最早出现在 1970 年 IBM 的 System 370 上,在 x86 上则是 80486 开始新增的 CMPXCHG 这个指令。

注:在多核系统上 CMPXCHG 也需要使用 LOCK 前缀,但是如果对应内存已经在 cache 里,就不用发出 LOCK 信号锁定总线,而是使用缓存锁。

由于不用锁定总线,这样的 原子操作指令不会限制其余 CPU core 操作非锁定内存 ,因此对系统整体的吞吐量影响不大。这一点对于当今核数越来越多的系统来说尤为重要。

由于原子操作指令仍然需要在 CPU 之间传递消息用于对 cache line 的锁定,其 性能仍有一定损耗 ,具体来说大概就相当于一个未命中 cache 的 Load Memory 指令[2]。

基于 CAS 我们可以用实现很多实用的原子操作,例如原子加法:

func atomicAdd(p *int32, incr int32) int32 {
  for {
    oldValue := *p
    newValue := oldValue + incr
    if atomic.CompareAndSwapInt32(p, oldValue, newValue) {
      return newValue
    }
  }
}

看,这就是一个典型的使用 乐观锁 的实现了:先做加法,如果更新失败,就换个姿势再来一次。

注:Go 语言 atomic.AddInt32 的实现是直接使用汇编 LOCK XADDL 完成的,不是基于 CAS 和循环。

– 自旋锁 –

回到锁的问题上,基于 CAS 我们可以很容易实现一个锁:

type spinLock int32
func (p *spinLock) Lock() {
  for !atomic.CompareAndSwapInt32((*int32)(p), 0, 1) {
  }
}
func (p *spinLock) Unlock() {
  atomic.StoreInt32((*int32)(p), 0)
}

这就是经典的 自旋锁 [3] —— 通过反复检测锁变量是否可用来完成加锁。在加锁过程中 CPU 是在忙等待,因此 仅适用于阻塞较短时间的场合 ;其优势在于 避免了线程切换的开销

注:spinlock 是 Linux 内核中主要的两种锁之一(另一种是Mutex),感兴趣的同学可以去看看内核源码里的实现,具体位于 include/asm/spinlock.h (吐槽:内核源码真是难读)。

在 Go 版的实现里还要注意:如果 GOMAXPROCS 被设置成 1 (Go Runtime只会给用户代码分配一个系统线程),会导致上述代码陷入死循环,因此更完善的实现是:

func (p *spinLock) Lock() {
  for !atomic.CompareAndSwapInt32((*int32)(p), 0, 1) {
    runtime.Gosched()
  }
}

通过将当前系统线程的使用权暂时归还给 Go Runtime(相当于其他语言的 yield),可以避免前述情况,但这也在一定程度上破坏了自旋锁的语义、使其变得更重了。

值得一提的是,研究人员发现,如果锁冲突比较频繁,在 CAS 失败时使用 指数退避算法 (Exponential Backoff)往往能得到更好的整体性能[2]。

– Mutex –

实际上 Go 语言没有提供自带的自旋锁实现,我们在代码中用得更多的是 Mutex 。

对比于 Spinlock 的忙等待,如果 Mutex 未获得锁,会释放对 CPU 的占用

上一篇 我们在说 Mutex 性能不够好的时候有提到“lock does not scale with the number of the processors”,这里的 lock 指的是用 CPU LOCK信号实现的锁;而通过阅读 Mutex 的源码,我发现实际上 Mutex 底层也是使用原子操作来实现的,所以前述说法不太准确。

Mutex 针对实际应用场景做了许多优化,是一个 从轻量级锁逐渐升级到重量级锁 的过程,从而平衡了各种场景下的需求和性能。

具体来说有这么几项:

  • fastpath:在简单场景下直接使用 CAS 加锁和解锁,缩短执行路径
  • spin:当自旋有意义时(多核、GOMAXPROCS > 1 、尝试不超过4次),优先使用自旋
  • 饥饿公平 :当等待超过 1ms 时,进入饥饿模式,新竞争者需要排队

注:对具体实现感兴趣的同学,可以结合参考资料《golang中的锁源码实现:Mutex》[5] 阅读源码。

这里提到的“ 公平 ”,指的是先到先得,这意味着每一个竞争者都需要进入等待队列,而这意味着 CPU控制权的切换和对应的开销 ;而 非公平 锁,指的是在进入等待队列之前先尝试加锁,如果加锁成功,可以 减少排队从而提高性能 ,但代价是队列中的竞争者可能会处于“ 饥饿 ”状态。

– sync  –

除了 Mutex,Go 在 sync 包里还实现了很多用于解决并发问题的工具,这里简单介绍下:

· RWMutex

读写锁,通过将资源的访问者分成读者和写者,允许多个读者同时访问资源,从而提高共享资源的并发度。 适用于读远多于写的场景

· WaitGroup

用于对 goroutine 的并发控制,在主 goroutine 里使用 Add(n) 指定并发数量,并使用 Wait() 等待所有任务都调用 Done() (配合 defer 使用效果更佳)。

· Pool

对象池,用于缓存后续会用到的对象,从而缓解 gc 压力。例如 fmt 包用它来缓存输出缓冲区。

· Once

“单例”:once.Do(f) 保证 f 只会被执行一次。f 被执行后,通过原子操作保证了性能。

· Cond

条件同步:当条件不满足时(通常是等待一个任务执行完成),goroutine调用 Wait() 等待通知;另一个 goroutine 完成任务后,调用 Signal() 或 Broadcast() 通知在等待的 goroutine。

· Map

支持并发的 map:通过 Load、Store、LoadOrStore、Delete、Range 等方法提供线程安全的 map 数据结构。

· atomic

提供 Add、CAS、Load、Store、Swap 等对基础数据类型的原子操作,以及 atomic.Value 来支持其他类型的 Load、Store 原子操作。

– 收尾 –

哎呀,这篇写得干巴巴的,连一个表情包都没有(忍住)。

最后照例小结一下:

  • 锁是基于原子操作实现的,而原子操作是需要硬件支持的
  • 基于 MESI 协议的缓存锁可以提高锁的性能
  • 比较常用的原子操作是 CAS
  • Go 没有官方自旋锁,我们通常用 sync.Mutex
  • sync 包里还有很多解决并发问题的实用工具

下次考虑结合一些具体案例来讲讲,可能更有意思一点儿,为了避免错过,记得关注↓↓↓