- 锁 -
前面我们讲过好多面试题了，其实锁也很适合用来做套题，比如可以这么切入：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
}
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
}
}
}
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)
}
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()
}
}
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 包里还有很多解决并发问题的实用工具
下次考虑结合一些具体案例来讲讲，可能更有意思一点儿~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
---
参考资料：
1. 原子操作是如何实现的？
2. Compare-and-swap
3. 自旋锁
4. 聊聊CPU的LOCK指令
5. golang中的锁源码实现：Mutex
