背景:

  1. 并发编程,多核、多线程的情况下,线程安全性问题都是一个无法回避的难题。虽然我们可以用到CAS,互斥锁,消息队列,甚至分布式锁来解决,但是对于锁的底层实现,这次课程,我们想更深入的来分析和探讨锁的底层原理,以便更好地理解和掌握并发编程。

大纲:

  • 1.并发编程与锁
  • 2.缓存和一致性协议MESI
  • 3.CPU/缓存与锁
  • 4.常见锁总结

    1 并发编程与锁

    1. 我们写的各种应用系统,像网络编程,基本上都是并发编程,不论是多进程还是多线程,亦或是协程、队列的方式,也都是并发编程的范畴。并发编程中,在多核操作系统中,多线程的时候,就会出现**线程安全性**问题,有的也说**并发安全性**问题。这种问题,都是因为对共享变量的并发读写引起的数据不一致问题。所以,在并发编程中,就会经常用到锁,当然也可能使用队列或者单线程的方式来处理共享数据。
    2. 我们先来还原一下具体的问题,然后再用不同的方法来处理它们。

    线程安全性问题1

    并发编程与锁的底层原理 - 图1
    代码中共享变量num是一个简单的计数器,main主线程启动了两个协程,分别循环一万次对num进行递增操作。正常情况下,预期的结果应该是1w+1w=2w,但是,在并发执行的情况下,最终的结果只有10891,离2w差的好多。
    典型应用场景:

  • 1 库存数量扣减

  • 2 投票数量递增
    并发安全性问题:
    num+ +是三个操作(读、改、写),不满足原子性
    并发读写全局变量,线程不安全

    线程安全性问题2

    并发编程与锁的底层原理 - 图2
    代码中共享变量list作为一个数据集合,由两个协程并发的循环append数据进去。同样是每个协程执行一万次,正常情况下,预期的list长度应该是2w,但是,在并发执行下,结果却可能连1w都不到。
    具体的原因,大家可以思考下,为什么并发执行的情况下,2个协程,竟然list长度还小于1w呢?
    典型应用场景:

  • 1 发放优惠券

  • 2 在线用户列表
    并发安全性问题:
    append(list, i) 内部是一个复杂的数组操作函数
    并发读写全局变量,线程不安全

    问题修复

    并发编程与锁的底层原理 - 图3
    通过WaitGroup将两个协程分开执行,第一个执行完成再执行第二个,避免并发执行,串行化两个任务。
    并发编程与锁的底层原理 - 图4
    通过互斥锁,在数字递增的前后加上锁的处理,数值递增操作时互斥。
    并发编程与锁的底层原理 - 图5
    针对int64的数字指针递增操作,可以利用atomic.AddInt64原子递增方法来处理。
    当然还会有更多的实现方法,但是内部的实现原理也都类似,原子操作,避免对共享数据的并发读写。

    并发编程的几个基础概念

  • 概念1:并发执行不一定是并行执行。

  • 概念2:单核CPU可以并发执行,不能并行执行。
  • 概念3:单进程、单线程,也可以并发执行。
    并行是同一时刻的多任务处理,并发是一个时间段内(1秒、1毫秒)的多任务处理。
    区别并发和并行,多核的并行处理涉及到多核同时读写一个缓存行,所以很容易出现数据的脏读和脏写;单核的并发处理中因为任务内部的中间变量,所以有可能存在脏写的情况。

    锁的作用

  • 避免并行运算中,共享数据读写的安全性问题。

  • 并行执行中,在锁的位置,同时只能有一个程序可以获得锁,其他程序不能获得锁。
  • 锁的出现,使得并行执行的程序在锁的位置串行化执行。
  • 多核、分布式运算、并发执行,才会需要锁。

    不用锁,也可以实现同样效果?

    1. 单线程串行化执行,队列式,CAS
    2. ——不要通过共享内存来通信,而应该通过通信来共享内存

    锁的底层实现类型

  • 1 锁内存总线,针对内存的读写操作,在总线上控制,限制程序的内存访问

  • 2 锁缓存行,同一个缓存行的内容读写操作,CPU内部的高速缓存保证一致性
    ,作用在一个对象或者变量上。现代CPU会优先在高速缓存查找,如果存在这个对象、变量的缓存行数据,会使用锁缓存行的方式。否则,才使用锁总线的方式。
    速度,加锁、解锁的速度,理论上就是高速缓存、内存总线的读写速度,它的效率是非常高的。而出现效率问题,是在产生冲突时的串行化等待时间,再加上线程的上下文切换,让多核的并发能力直线下降。

    2 缓存和一致性协议MESI

    1. 英文首字母缩写,也就是英文环境下的术语、俚语、成语,新人理解和学习有难度,但是,掌握好了既可以省事,又可以缩小文化差距。
    2. 另外就是对英文的异形化,也类似汉字的变形体,“表酱紫”,“蓝瘦香菇”,老外是很难懂得,反之一样。

    MESI“生老病死”缓存行的四种状态

  • M: modify 被修改,数据有效,cache和内存不一致

  • E: exclusive 独享,数据有效,cache与内存一致
  • S: shared 共享,数据有效,cache与内存一致,多核同时存在
  • I: invalid 数据无效
  • F: forward 向前(intel),特殊的共享状态,多个S状态,只有一个F状态,从F高速缓存接受副本
      当内核需要某份数据时,而其它核有这份数据的备份时,本cache既可以从内存中导入数据,也可以从其它cache中导入数据(Forward状态的cache)。

    四种状态的更新路线图

    并发编程与锁的底层原理 - 图6
    高效的状态: E, S
    低效的状态: I, M
      这四种状态,保证CPU内部的缓存数据是一致的,但是,并不能保证是强一致性。
      每个cache的控制器不仅知道自己的读写操作,而且也要监听其它cache的读写操作。

    缓存的意义

    并发编程与锁的底层原理 - 图7

  • 1 时间局部性:如果某个数据被访问,那么不久还会被访问

  • 2 空间局部性:如果某个数据被访问,那么相邻的数据也很快可能被访问
    局限性:空间、速度、成本
    更大的缓存容量,需要更大的成本。更快的速度,需要更大的成本。均衡缓存的空间、速度、成本,才能更有市场竞争力,也是现在我们看到的情况。当然,随着技术的升级,成本下降,空间、速度也就能继续稳步提高了。

    缓存行,64Byte的内容

    并发编程与锁的底层原理 - 图8
    缓存行的存储空间是64Byte(字节),也就是可以放64个英文字母,或者8个int64变量。
    注意伪共享的情况——56Byte共享数据不变化,但是8Byte的数据频繁更新,导致56Byte的共享数据也会频繁失效。
    解决方法:缓存行的数据对齐,更新频繁的变量独占一个缓存行,只读的变量共享一个缓存行。

    3 CPU/缓存与锁

    锁的底层实现原理,与CPU、高速缓存有着密切的关系,接下来一起看看CPU的内部结构。

    CPU与计算机结构

    并发编程与锁的底层原理 - 图9
    并发编程与锁的底层原理 - 图10
    内核独享寄存器、L1/L2,共享L3。在早先时候只有单核CPU,那时只有L1和L2,后来有了多核CPU,为了效率和性能,就增加了共享的L3缓存。
    多颗CPU通过QPI连接。再后来,同一个主板上面也可以支持多颗CPU,多颗CPU也需要有通信和控制,才有了QPI。
    内存读写都要通过内存总线。CPU与内存、磁盘、网络、外设等通信,都需要通过各种系统提供的系统总线。

    CPU流水线

    并发编程与锁的底层原理 - 图11
    并发编程与锁的底层原理 - 图12
    CPU流水线,里面还有异步的LoadBuffer,
    Store Buffer, Invalidate Queue。这些缓冲队列的出现,更多的异步处理数据,提高了CPU的数据读写性能。
    CPU为了保证性能,默认是宽松的数据一致性。

    编译器、CPU优化

    并发编程与锁的底层原理 - 图13
    并发编程与锁的底层原理 - 图14
    编译器优化:重排代码顺序,优先读操作(读有更好的性能,因为cache中有共享数据,而写操作,会让共享数据失效)
    CPU优化:指令执行乱序(多核心协同处理,自动优化和重排指令顺序)

    编译器、CPU屏蔽

  • 优化屏蔽:禁止编译器优化。按照代码逻辑顺序生成二进制代码,volatile关键词

  • 内存屏蔽:禁止CPU优化。防止指令之间的重排序,保证数据的可见性,store barrier, load barrier, full barrier
  • 写屏障:阻塞直到把Store Buffer中的数据刷到Cache中
  • 读屏障:阻塞直到Invalid Queue中的消息执行完毕
  • 全屏蔽:包括读写屏障,以保证各核的数据一致性
    Go语言中的Lock指令就是一个内存全屏蔽同时禁止了编译器优化。
    并发编程与锁的底层原理 - 图15
    x86的架构在CPU优化方面做的相对少一些,只是针对“写读”的顺序才可能调序。

    加锁,加了些什么?

  • 禁止编译器做优化(加了优化屏蔽)

  • 禁止CPU对指令重排(加了内存屏蔽)
  • 针对缓存行、内存总线上的控制
  • 冲突时的任务等待队列

    4 常见锁总结

    1. 最后,我们一起来看看常见的自旋锁、互斥锁、条件锁、读写锁的实现逻辑,以及在Go源码中,是如何来实现的CAS/atomic.AddInt64Mutext.Lock方法的。

    自旋锁

    并发编程与锁的底层原理 - 图16
    只要没有锁上,就不断重试。
    如果别的线程长期持有该锁,那么你这个线程就一直在 while while while 地检查是否能够加锁,浪费 CPU 做无用功。
    优点:不切换上下文;
    不足:烧CPU;
    适用场景:冲突不多,等待时间不长的情况下,或者少次数的尝试自旋。

    互斥锁

    并发编程与锁的底层原理 - 图17
    操作系统负责线程调度,为了实现「锁的状态发生改变时再唤醒」就需要把锁也交给操作系统管理。
    所以互斥器的加锁操作通常都需要涉及到上下文切换,操作花销也就会比自旋锁要大。
    优点:简单高效;
    不足:冲突等待时的上下文切换;
    适用场景:绝大部分情况下都可以直接使用互斥锁。

    条件锁

    并发编程与锁的底层原理 - 图18
    它解决的问题不是「互斥」,而是「等待」。
    消息队列的消费者程序,在队列为空的时候休息,数据不为空的时候(条件改变)启动消费任务。
    条件锁的业务针对性更强。

    读写锁

    并发编程与锁的底层原理 - 图19
    内部有两个锁,一个是读的锁,一个是写的锁。
    如果只有一个读者、一个写者,那么等价于直接使用互斥锁。
    不过由于读写锁需要额外记录读者数量,花销要大一点。
    也可以认为读写锁是针对某种特定情景(读多写少)的「优化」。
    但个人还是建议忘掉读写锁,直接用互斥器。
    试用场景:读多写少,而且读的过程时间较长,可以通过读写锁,减少读冲突时的等待。

    无锁操作CAS

    1. Compare And Swap 比较并交换,类似于将 num+ + 的三个指令合并成一个指令 CMPXCHG,保证了操作的原子性。

    为了保证顺序一致性和数据强一致性,还需要有一个LOCK指令。
    源码,参见 runtime/internal/atomic/asm_amd64.s
    并发编程与锁的底层原理 - 图20
    LOCK指令的作用就是禁止编译器优化,同时加上内存全屏障,可以保证LOCK指令之后的一个指令执行时的数据强一致性和可见性。

    数字的原子递增操作 atomic.AddInt64

    1. 在原始指针数字的基础上,原子性递增 delta 数值,并且返回递增后的结果值。
    2. 源码1,参见 sync/atomic/asm.s

    并发编程与锁的底层原理 - 图21
    XADDQ 数据交换,数值相加,写入目标数据
    ADDQ 数值相加,写入目标数据
    在XADDQ之前加上LOCK指令,保证这个指令执行时的数据强一致性和可见性。
    源码2,参见 runtime/internal/atomic/asm_amd64.s
    并发编程与锁的底层原理 - 图22

    互斥锁操作 sync.Mutex.Lock

    并发编程与锁的底层原理 - 图23
    并发编程与锁的底层原理 - 图24
    源码,参见 sync/mutex.go
    大概的源码处理逻辑如下:

  • 1 通过CAS操作来竞争锁的状态 &m.state;

  • 2 没有竞争到锁,先主动自旋尝试获取锁 runtime_canSpin 和 runtime_doSpin (原地烧CPU);
  • 3 自旋尝试失败,再次CAS尝试获取锁;
  • 4 runtime_SemacquireMutex 锁请求失败,进入休眠状态,等待信号唤醒后重新开始循环;
  • 5 m.state等待队列长度(复用的int32位数字,第一位是锁的状态,后31位是锁的等待队列长度计数器);