多懂一点并发

更新日期:2019-03-13
流利说技术团队

关于并发,自己之前的知识面一直是停留在语言提供的特性。比如在学习 Java 的时候,稍微深入一点到虚拟机是如何支持的。但是从虚拟机到计算机系统之间的这一层,一直没有了解过,或者通常就记住了结论(大概就是:嗯,虚拟机包装好了;编译器也做好了,用就是了)。所以本文仅为了帮助理解并发机制,来简单地自下而上介绍一下。

目录

一、问题和答案

二、缓存锁

三、缓存一致性

四、关于屏障

五、GO语言的 lock

六、JAVA的 volatile

为了更好理解后面的问题,学习 Java 的同学或者虚拟机语言的同学可能要大概了解一下虚拟机跟系统之间的映射关系,例如 Java:栈、堆跟计算机系统之间的映射关系:

一、问题和答案

并发的问题一般都会围绕着原子性、有序性、可见性,这三个特性来分析(不清楚三个特性可以自行了解一下,先不在这里介绍)。先从硬件层面上来了解关于并发的问题。以 SMP 架构为例,如图:

       

  先抛问题:

  • 基于多级缓存的架构,多核间缓存同步怎么办

  • 基于优化的目的,会进行重排序,举个例子:面试官要去面试候选人的时候。

  • 一般重排序分为三种(按照个人能够比较明确理解,标注了真、假):

  • 编译器优化重排序(真)

  • 指令集执行重排序(真)

  • 缓存同步重排序(假)


  • 不绕弯子,直接告诉解决方案:

  • 通过总线锁、缓存锁机制来解决缓存同步问题

  • 优化屏障、内存屏障。这个方案其实等于交给软件来决定优化时机


  • 到目前为止,关于并发自下而上的问题和解决方案,都大概交代了一遍。后面篇幅还是主要集中在分析问题和理解。

    二、缓存锁

    基于上面 SMP 架构图(此时先忽略 Store Buffer 和 Invalidate Queue)的硬件,被缓存在处理器中的共享数据,在 LOCK #操作期间被锁定,那么当被修改的共享内存的数据回写到内存时,处理器不在总线上声明 LOCK# 信号,而是修改内部的内存地址,并通过缓存一致性机制来保证操作的原子性。

    三、缓存一致性

    关于缓存一致性,比较经典的就是 MESI 协议,它是以缓存行(Cache line:缓存存储数据的单元)的四种状态来命名:

  • M: 被修改(Modified):该缓存行只被缓存在该 CPU 的缓存中,并且是被修改过的,即与主存中的数据不一致

  • E: 独享的(Exclusive):该缓存行只被缓存在该 CPU 的缓存中,它是未被修改过的,与主存中数据一致

  • S: 共享的(Shared):该状态意味着该缓存行可能被多个 CPU 缓存,并且各个缓存中的数据与主存数据一致

  • I: 无效的(Invalid):该缓存是无效的

  • 具体监听任务和状态切换就不在这边展开介绍,有兴趣的同学可以自行研究一下这个协议。按照这个协议,已经解决了 CPU 缓存层面的可见性问题,但是面临着性能问题。这个协议两个行为执行成本比较大:(这个两个状态的变更,操作路径比较长一点,并且伴随着核心等待) 

  • 将缓存行标记为 I

  • 当缓存行状态为 I,写入新的数据

  • 所以伟大的 CPU 工程师做了一些优化,加入了 Store Buffer 和 Invalidate Queue。然而,又很不幸,这么优化又带来了新的问题,结合上图,产生的问题有:

  • 当核心 C1 要执行数据写入的时候,首先会给其它核(例如:C2)发送 Invalid  消息,然后把数据写入到 Store Buffer 中,并且会异步在某个时刻真正的写入到 Cache Line 中。对于 C1 本身来说,要读取数据的时候,需要先扫描 Store Buffer 之后再读取 Cache Line。但是 C2  看不到 C1 的 store buffer,一首凉凉送给 C2。。。

  • C1从 store buffer 写入到 cache line 的时机也是不确定的。那么假如有这样一段代码:

    先抛开编译器指令重排序这个真的排序不说,还有可能上面提到的缓存同步重排序这个“假”重排序😂。如果C1 缓存了 a,并且状态为独享(E),而 b 可能是失效状态(I), 这种情况下给 b 写入数据,C1 首先会给其他核,例如 C2,发送 Invalid 消息,然后 C1 把数据写入 StoreBuffer 中,接着 C1 继续处理其他指令(假设 a=true 这个指令),这就会导致 b 会比 a 更迟的刷入缓存。那么就可能出现 C2 读取到了 a 的值为 true,而 b 的值不等于2的情况。

  • 此时,硬件已经无法知道怎么继续优化下去了(硬件无法知道前后的依赖关系,例如上面举的a、b例子),所以硬件通过提供指令让软件自己来控制。在本文里面讨论的,说白了,就是让虚拟机或者语言层面来自己控制了😂。

    四、关于屏障

    按照本文惯例,有了上面的问题,先给解决方案:

  • 优化屏障 (Optimization Barrier):避免编译器的重排序优化操作,主要作用是:保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行,让编译的优化不会影响到实际逻辑。

  • 内存屏障 (Memory Barrier)分为写屏障(Store Barrier)读屏障(Load Barrier)全屏障(Full Barrier),其作用有两个:

  • 防止指令之间的重排序

  • 保证数据的可见性

  • 当然说到这么多屏障,还是比较难理解。因为平常关于并发编程比较熟悉的,例如:golang 的 sync.Mutex,java 的 synchronized,volatile,以及到处都在说的 CAS。

    五、GO

    先从 golang 的 sync.Mutex 的源码实现入手发现,核心就是使用到了 CPU 指令 CAS,这个指令其实和 CPU 架构密切相关(最明显的就是不同的汇编文件)。以 asm_amd64.s 为例封装的 atomic·Cas64,可以查看到:

    使用 LOCK 指令,表示多核下需要总线锁或者使用MESI协议来保证原子指令的原子性,同时也是一个内存全屏障并且禁止了编译器优化重排序,另外在冲突的时候,进入任务等待队列。

    LOCK 指令大概一个执行过程:

  • 对总线和缓存上锁。

  • 强制所有 lock 信号之前的指令,都在此之前被执行,并同步相关缓存。

  • 执行 lock 后的指令(如 cmpxchgq)。

  • 释放对总线和缓存上的锁。

  • 强制所有 lock 信号之后的指令,都在此之后被执行,并同步相关缓存。

  • 基本上看到这里,可以大致明白 golang 是如何使用优化屏障和内存屏障的。

    六、JAVA


    而在 Java 语言中(后面讨论都是以 JDK1.5 及以上),JVM 对于 CPU 层面的内存屏障指令进行了包装,分为四类:LoadLoad,StoreStore,LoadStore,StoreLoad(不太熟悉的同学,可以自行了解一下这四个屏障的意思)。这里以关键字“ volatile ”为例:

  • volatile 读之前,会添加 LoadLoad 内存屏障。

  • volatile 读之后,会添加 LoadStore 内存屏障。

  • volatile 写之前,会添加 StoreStore 内存屏障。

  • volatile 写之后,会添加 StoreLoad 型内存屏障。

  • 再回到上文 a=false,b=1 的问题,修正一下代码,用 volatile 来修饰一下 a 变量,按照JMM的规则,大概如图:

    所以根据四个屏障的语义,可以明确理解 volatile 这个关键字的两个特性:可见性和有序性。

    另外我们也可以直接看到 JIT 编译出的目标机器指令(代码稍微被改了一下,乱写一通,让 JIT 觉得足够复杂),如图:

    同样会涉及到 LOCK 指令,也验证了上面对于 volatile 和四个屏障的理解了。

    到目前为止,基本上在并发方面,从硬件到软件编程做了一次大概的介绍。文章中其实涉及到很多比较容易引发争议的问题,欢迎大家讨论和指正。