背景:
1 | 并发编程,多核、多线程的情况下,线程安全性问题都是一个无法回避的难题。虽然我们可以用到CAS,互斥锁,消息队列,甚至分布式锁来解决,但是对于锁的底层实现,这次课程,我们想更深入的来分析和探讨锁的底层原理,以便更好地理解和掌握并发编程。 |
大纲:
- 1.并发编程与锁
- 2.缓存和一致性协议 MESI
- 3.CPU/缓存与锁
- 4.常见锁总结
1 并发编程与锁
1 | 我们写的各种应用系统,像网络编程,基本上都是并发编程,不论是多进程还是多线程,亦或是协程、队列的方式,也都是并发编程的范畴。并发编程中,在多核操作系统中,多线程的时候,就会出现**线程安全性**问题,有的也说**并发安全性**问题。这种问题,都是因为对共享变量的并发读写引起的数据不一致问题。所以,在并发编程中,就会经常用到锁,当然也可能使用队列或者单线程的方式来处理共享数据。 |
线程安全性问题 1
代码中共享变量 num 是一个简单的计数器,main 主线程启动了两个协程,分别循环一万次对 num 进行递增操作。正常情况下,预期的结果应该是 1w+1w=2w,但是,在并发执行的情况下,最终的结果只有 10891,离 2w 差的好多。
典型应用场景:
- 1 库存数量扣减
- 2 投票数量递增
并发安全性问题:
num+ +是三个操作(读、改、写),不满足原子性
并发读写全局变量,线程不安全
线程安全性问题 2
代码中共享变量 list 作为一个数据集合,由两个协程并发的循环 append 数据进去。同样是每个协程执行一万次,正常情况下,预期的 list 长度应该是 2w,但是,在并发执行下,结果却可能连 1w 都不到。
具体的原因,大家可以思考下,为什么并发执行的情况下,2 个协程,竟然 list 长度还小于 1w 呢?
典型应用场景:
- 1 发放优惠券
- 2 在线用户列表
并发安全性问题:
append(list, i) 内部是一个复杂的数组操作函数
并发读写全局变量,线程不安全
问题修复
通过 WaitGroup 将两个协程分开执行,第一个执行完成再执行第二个,避免并发执行,串行化两个任务。
通过互斥锁,在数字递增的前后加上锁的处理,数值递增操作时互斥。
针对 int64 的数字指针递增操作,可以利用 atomic.AddInt64 原子递增方法来处理。
当然还会有更多的实现方法,但是内部的实现原理也都类似,原子操作,避免对共享数据的并发读写。
并发编程的几个基础概念
- 概念 1:并发执行不一定是并行执行。
- 概念 2:单核 CPU 可以并发执行,不能并行执行。
- 概念 3:单进程、单线程,也可以并发执行。
并行是同一时刻的多任务处理,并发是一个时间段内(1 秒、1 毫秒)的多任务处理。
区别并发和并行,多核的并行处理涉及到多核同时读写一个缓存行,所以很容易出现数据的脏读和脏写;单核的并发处理中因为任务内部的中间变量,所以有可能存在脏写的情况。
锁的作用
- 避免并行运算中,共享数据读写的安全性问题。
- 并行执行中,在锁的位置,同时只能有一个程序可以获得锁,其他程序不能获得锁。
- 锁的出现,使得并行执行的程序在锁的位置串行化执行。
- 多核、分布式运算、并发执行,才会需要锁。
不用锁,也可以实现同样效果?
1 | 单线程串行化执行,队列式,CAS。 |
锁的底层实现类型
- 1 锁内存总线,针对内存的读写操作,在总线上控制,限制程序的内存访问
- 2 锁缓存行,同一个缓存行的内容读写操作,CPU 内部的高速缓存保证一致性
锁,作用在一个对象或者变量上。现代 CPU 会优先在高速缓存查找,如果存在这个对象、变量的缓存行数据,会使用锁缓存行的方式。否则,才使用锁总线的方式。
速度,加锁、解锁的速度,理论上就是高速缓存、内存总线的读写速度,它的效率是非常高的。而出现效率问题,是在产生冲突时的串行化等待时间,再加上线程的上下文切换,让多核的并发能力直线下降。
2 缓存和一致性协议 MESI
1 | 英文首字母缩写,也就是英文环境下的术语、俚语、成语,新人理解和学习有难度,但是,掌握好了既可以省事,又可以缩小文化差距。 |
MESI“生老病死”缓存行的四种状态
- M: modify 被修改,数据有效,cache 和内存不一致
- E: exclusive 独享,数据有效,cache 与内存一致
- S: shared 共享,数据有效,cache 与内存一致,多核同时存在
- I: invalid 数据无效
- F: forward 向前(intel),特殊的共享状态,多个 S 状态,只有一个 F 状态,从 F 高速缓存接受副本
当内核需要某份数据时,而其它核有这份数据的备份时,本 cache 既可以从内存中导入数据,也可以从其它 cache 中导入数据(Forward 状态的 cache)。
四种状态的更新路线图
高效的状态: E, S
低效的状态: I, M
这四种状态,保证 CPU 内部的缓存数据是一致的,但是,并不能保证是强一致性。
每个 cache 的控制器不仅知道自己的读写操作,而且也要监听其它 cache 的读写操作。
缓存的意义
- 1 时间局部性:如果某个数据被访问,那么不久还会被访问
- 2 空间局部性:如果某个数据被访问,那么相邻的数据也很快可能被访问
局限性:空间、速度、成本
更大的缓存容量,需要更大的成本。更快的速度,需要更大的成本。均衡缓存的空间、速度、成本,才能更有市场竞争力,也是现在我们看到的情况。当然,随着技术的升级,成本下降,空间、速度也就能继续稳步提高了。
缓存行,64Byte 的内容
缓存行的存储空间是 64Byte(字节),也就是可以放 64 个英文字母,或者 8 个 int64 变量。
注意伪共享的情况——56Byte 共享数据不变化,但是 8Byte 的数据频繁更新,导致 56Byte 的共享数据也会频繁失效。
解决方法:缓存行的数据对齐,更新频繁的变量独占一个缓存行,只读的变量共享一个缓存行。
3 CPU/缓存与锁
锁的底层实现原理,与 CPU、高速缓存有着密切的关系,接下来一起看看 CPU 的内部结构。
CPU 与计算机结构
内核独享寄存器、L1/L2,共享 L3。在早先时候只有单核 CPU,那时只有 L1 和 L2,后来有了多核 CPU,为了效率和性能,就增加了共享的 L3 缓存。
多颗 CPU 通过 QPI 连接。再后来,同一个主板上面也可以支持多颗 CPU,多颗 CPU 也需要有通信和控制,才有了 QPI。
内存读写都要通过内存总线。CPU 与内存、磁盘、网络、外设等通信,都需要通过各种系统提供的系统总线。
CPU 流水线
CPU 流水线,里面还有异步的 LoadBuffer,
Store Buffer, Invalidate Queue。这些缓冲队列的出现,更多的异步处理数据,提高了 CPU 的数据读写性能。
CPU 为了保证性能,默认是宽松的数据一致性。
编译器、CPU 优化
编译器优化:重排代码顺序,优先读操作(读有更好的性能,因为 cache 中有共享数据,而写操作,会让共享数据失效)
CPU 优化:指令执行乱序(多核心协同处理,自动优化和重排指令顺序)
编译器、CPU 屏蔽
- 优化屏蔽:禁止编译器优化。按照代码逻辑顺序生成二进制代码,volatile 关键词
- 内存屏蔽:禁止 CPU 优化。防止指令之间的重排序,保证数据的可见性,store barrier, load barrier, full barrier
- 写屏障:阻塞直到把 Store Buffer 中的数据刷到 Cache 中
- 读屏障:阻塞直到 Invalid Queue 中的消息执行完毕
- 全屏蔽:包括读写屏障,以保证各核的数据一致性
Go 语言中的 Lock 指令就是一个内存全屏蔽同时禁止了编译器优化。
x86 的架构在 CPU 优化方面做的相对少一些,只是针对“写读”的顺序才可能调序。
加锁,加了些什么?
- 禁止编译器做优化(加了优化屏蔽)
- 禁止 CPU 对指令重排(加了内存屏蔽)
- 针对缓存行、内存总线上的控制
- 冲突时的任务等待队列
4 常见锁总结
1 | 最后,我们一起来看看常见的自旋锁、互斥锁、条件锁、读写锁的实现逻辑,以及在Go源码中,是如何来实现的CAS/atomic.AddInt64和Mutext.Lock方法的。 |
自旋锁
只要没有锁上,就不断重试。
如果别的线程长期持有该锁,那么你这个线程就一直在 while while while 地检查是否能够加锁,浪费 CPU 做无用功。
优点:不切换上下文;
不足:烧 CPU;
适用场景:冲突不多,等待时间不长的情况下,或者少次数的尝试自旋。
互斥锁
操作系统负责线程调度,为了实现「锁的状态发生改变时再唤醒」就需要把锁也交给操作系统管理。
所以互斥器的加锁操作通常都需要涉及到上下文切换,操作花销也就会比自旋锁要大。
优点:简单高效;
不足:冲突等待时的上下文切换;
适用场景:绝大部分情况下都可以直接使用互斥锁。
条件锁
它解决的问题不是「互斥」,而是「等待」。
消息队列的消费者程序,在队列为空的时候休息,数据不为空的时候(条件改变)启动消费任务。
条件锁的业务针对性更强。
读写锁
内部有两个锁,一个是读的锁,一个是写的锁。
如果只有一个读者、一个写者,那么等价于直接使用互斥锁。
不过由于读写锁需要额外记录读者数量,花销要大一点。
也可以认为读写锁是针对某种特定情景(读多写少)的「优化」。
但个人还是建议忘掉读写锁,直接用互斥器。
试用场景:读多写少,而且读的过程时间较长,可以通过读写锁,减少读冲突时的等待。
无锁操作 CAS
1 | Compare And Swap 比较并交换,类似于将 num+ + 的三个指令合并成一个指令 CMPXCHG,保证了操作的原子性。 |
为了保证顺序一致性和数据强一致性,还需要有一个 LOCK 指令。
源码,参见 runtime/internal/atomic/asm_amd64.s
LOCK 指令的作用就是禁止编译器优化,同时加上内存全屏障,可以保证LOCK 指令之后的一个指令执行时的数据强一致性和可见性。
数字的原子递增操作 atomic.AddInt64
1 | 在原始指针数字的基础上,原子性递增 delta 数值,并且返回递增后的结果值。 |
XADDQ 数据交换,数值相加,写入目标数据
ADDQ 数值相加,写入目标数据
在 XADDQ 之前加上 LOCK 指令,保证这个指令执行时的数据强一致性和可见性。
源码 2,参见 runtime/internal/atomic/asm_amd64.s
互斥锁操作 sync.Mutex.Lock
源码,参见 sync/mutex.go
大概的源码处理逻辑如下:
- 1 通过 CAS 操作来竞争锁的状态 &m.state;
- 2 没有竞争到锁,先主动自旋尝试获取锁 runtime_canSpin 和 runtime_doSpin (原地烧 CPU);
- 3 自旋尝试失败,再次 CAS 尝试获取锁;
- 4 runtime_SemacquireMutex 锁请求失败,进入休眠状态,等待信号唤醒后重新开始循环;
- 5 m.state 等待队列长度(复用的 int32 位数字,第一位是锁的状态,后 31 位是锁的等待队列长度计数器);