一文讲透天下锁
一、原子操作
CAS等原子操作包含了LOCK指令，下面先普及一些常识
指令获取后，还需要它的数据运算对象，然后才能执行。如果待操作数据不在缓存行，此时cpu为了提高性能，会让其他指令先执行，尽可能的使用其他『可以执行』的指令填补时间空隙，简单概括就是『谁行谁上，没准备好的靠边』，这就是指令乱序问题
因为指令乱序的存在，有时会导致程序逻辑问题。当需要确保某行代码执行时，前面的指令全部执行完，可以插入内存屏障，来确保执行顺序
内存屏障：也称内存栅栏，保证了在内存屏障前边的指令一定会先于内存屏障后边的指令被执行
LOCK指令前缀功能如下：
- 被修饰的汇编指令成为“原子的”
- 与被修饰的汇编指令一起提供内存屏障效果
LOCK指令实现：
- 如果访问的数据已经在cpu的缓存行中，通过MESI缓存一致性协议处理多核间缓存的一致性。
- 如果访问的数据不在cpu缓存行中，会把数据总线锁住，这样其他的cpu就不能访问内存了，从而确保原子性
原子操作，该操作在执行结束前不会被打断，是由硬件厂商提供的汇编指令实现。除了常见的CAS外，还有一些原子加载int、long类型数据，以及对int、long原子加一减一等操作
存在问题： 使用原子指令时注意是否存在伪共享
二、spinlock
自旋锁是线程反复检查锁变量是否可用，属于忙等待，直到其他线程释放了此锁。自旋锁避免了线程切换的开销，对于一些很小的临界区效率很高，但自旋成本高于两次切换时，不如放弃cpu时间片，以免在高并发下导致性能更差。实际项目中不会单纯使用自旋锁，一般是自旋一定次数，然后把自己挂在阻塞队列上，让出cpu，等待唤醒。
三、seqlock
顺序锁是写者优先的锁，使用sequence变量初始化为0，当写线程进入临界区，加锁（多个写线程之间互斥）然后sequence++，更新完数据后sequence++并解锁，退出临界区。如果读线程在写线程更新数据期间获取sequence值为奇数，需要等待，读取后需要判断开始读取的sequence和现在的值是否相同，不同则表示读取过程中数据被修改，需要重新读取。
seqlock 伪代码示意图，如下：
三、Read-copy-update（RCU）
RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后把指向原来数据的指针重新指向新的被修改的数据。
rcu的思想很简单，像go有垃圾回收的机制，使用起来很方便。如果是C语言，确认旧内存回收时机太复杂，直接劝退，还不如futex来的痛快。
使用场景一般是读多写少，比如监听发布中心信息时，就可以新生成一个map，然后使用CAS替换指针指向即可
四、Linux futex
futex实现了理想的同步机制，没有锁冲突时在用户态使用原子指令解决问题，而需要挂起等待时再利用内核提供的系统调用进行睡眠和唤醒。
futex 的操作几乎全部在用户空间完成；只有真正锁冲突的时候，才需要进入操作系统内核空间执行。这种机制使得 futex 有非常高的执行效率：由于大多数情况下并没有竞争，所以绝大多数都只是在用户空间执行，而不需要使用（相对高代价的）系统调用。
在内核中通过一个哈希表来维护所有挂起阻塞在futex变量上的task，不同的futex变量会根据其地址标识计算出一个hash key定位到一个哈希桶链上，阻塞在同一个futex变量的所有task会挂到同一个哈希桶链上，如下如：
futex 是下面各种锁的基础，当然futex也依赖原子指令，runtime.mutex是基于spinlock和futex优化的锁，下图说明go常用锁的依赖关系：
五、runtime.mutex
// 1.15::/src/runtime/runtime2.go
type mutex struct {
key uintptr // key本身记录锁的状态，&key是调用futex使用，同一个地址是同一把锁
}
runtime.mutex是runtime内部线程间同步用的。首先自旋一定次数，超过自旋上限调用futex挂起，操作系统会调度下一个可运行的线程，待条件满足时会被唤醒，基本上是对futex做一层封装。
六、runtime.semaphore
// 1.15::/src/runtime/sema.go
const semTabSize = 251
var semtable [semTabSize]struct {
root semaRoot
pad [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte // 填充，避免伪共享
}
type semaRoot struct {
lock mutex // runtime.mutex
treap *sudog // Tree + Heap，二叉树保证有序，堆用来打乱数据避免退化为链表
nwait uint32 // Number of waiters. Read w/o the lock.
}
- 先通过
CAS快速判断是否获取信号量，成功直接返回； - 若
CAS失败，则尝试获取某个semaRoot下的runtime.mutex，因为可能会有多个线程并发操作同一个treap，因此需要加锁保证互斥 - 获得
mutex则再次尝试CAS，成功则解锁返回；否则把当前协程加入treap，调用goparkunlock挂起协程等待唤醒，GMP模型会调度下一个协程运行
semaphore一般不会导致线程的切换，只是把协程挂起，基本在用户态执行完成，性能更好，下图是管理协程挂起的数据结构，采用有251个平衡树，有效降低多线程锁的冲突。
七、sync.Mutex
// 1.15::/src/sync/mutex.go
type Mutex struct {
state int32
sema uint32
}
state: |32|31|..|4|3|2|1|
\________/ | | |
| | | |
| | | 当前mutex是否加锁
| | |
| | 当前mutex是否被唤醒
| |
| 饥饿标志
|
等待队列的goroutine协程数
state 存储的是互斥锁的状态，加锁和加锁都是通过原子指令。若加锁失败使用sema用作信号量，为Mutex提供等待队列。
Mutex分为正常模式和饥饿模式，正常模式有更好的性能，而饥饿模式防止有些协程一直抢不到锁。
正常模式下，协程会先自旋几次，尝试通过原子指令获取锁，如几次之后仍不能获得锁，则通过信号量排队等待。当锁释放时，唤醒队列中的一个协程和后来的多个协程竞争锁，因为后来者正在自旋且数量可能更多，获取锁的概率高。这时候被唤醒的协程会插入到等待队列的头尾「默认是尾部，FIFO」，当协程等待获取锁时间超过1ms，它会把这个Mutex切换到饥饿模式
饥饿模式下，一切新来的协程直接进入信号量的队列排队，当锁资源释放时会给队头的协程。当一个等待着获得锁之后，会在两种情况下将Mutex切换到正常模式：
1. 它是等待队列的最后一个协程
2. 它的等待时间小于1ms
sync.Mutex是暴露给协程使用的，底层是基于runtime.semaphore信号量实现排队。
八、锁的常见优化
- 按功能分为读写锁，实现锁分离
- 使用原子操作
- 减小锁粒度，比如分段锁
- 减小锁的持有时间
实际项目中，会根据自身的需求，选择哪一种锁，甚至是利用CAS实现无锁编程，但无论如何选择，应该了解底层实现，以及付出的代价和收益。
最后看个段子吧
参考文献：
【Linux的futex】 www.bilibili.com/video/BV1d5…，理解了futex再看其他锁就很容易
github.com/cch123/gola…，go信号量代码分析