并发 - JMM

前言

本篇文章将对 Java 的内存模型(JMM)进行介绍,本质上它是一种编程语言规范,用于尝试统一一个能够在各种处理器架构中为并发提供一致语义的内存模型(不同处理器架构一般具有不同强度的模型)。驱动 Java 内存模型产生的原因有很多,如编译器优化、处理器乱序执行和缓存等,这些因素导致并发程序中有些行为是非法的。因此,在介绍 Java 内存模型之前,我们先对并发编程相关概念进行说明,然后再引出 Java 内存模型。

硬件内存架构

了解现代计算机硬件架构对理解 Java 内存模型非常重要,常见的硬件内存架构图如下:

下面我们重点对硬件内存架构的组成,缓存一致性问题进行介绍。

硬件内存组成

现代计算机内存架构包括:多CPU、CPU寄存器、CPU缓存以及共享的内存。

多CPU

现代计算机通常有 2 个或更多 CPU ,其中一些 CPU 可能具有多个核。当只有一个 CPU 时,要运行多个程序(进程)的话,就意味着要经常进行进程上下文切换。尽管单 CPU 是多核,也只是多个处理器核心,其他设备都是共用的,所以多个进程就必然要经常进行进程上下文切换,这个代价是很高的。

CPU多核

一个多核的 CPU 也就是一个 CPU 上有多个处理器核心。

CPU寄存器

每个 CPU 都包含一组寄存器,它们是 CPU 内存的基础。CPU 在寄存器上执行操作的速度远大于在主存上执行的速度。这是因为 CPU 访问寄存器的速度远大于主存。

CPU缓存

每个 CPU 还可能有一个 CPU 缓存存储器层。事实上,大多数现代 CPU 都有一定大小的缓存层,位于 CPU 与主内存间的一种容量较小但速度很高的存储器,但通常不如访问其内部寄存器的速度快。由于 CPU 的速度远高于主内存,CPU 直接从主内存中存取数据要等待一定时间周期。CPU 缓存中保存着 CPU 刚用过或循环使用的一部分数据,当 CPU 再次使用该部分数据时可从缓存中直接获取, 减少了 CPU 的等待时间,提高了系统的效率。

一些 CPU 可能有多个缓存层,具体如下:

  • 一级缓存(L1 Cache): 容量最小,速度最快,每个核独有。针对指令和数据分为数据缓存和指令缓存
  • 二级缓存(L2 Cache): 容量比 L1 大,速度比 L1 慢,每个核独有
  • 三级缓存(L3 Cache): 容量最大,速度最慢,多个核共享

由于Cache的容量很小,一般都是充分的利用局部性原理,按行/块来和主存进行批量数据交换,以提升数据的访问效率。

内存

计算机还包含一个主存储区 (RAM),所有 CPU 都可以访问它。主内存区域通常比 CPU 的高速缓存大得多。

读取数据

  • 取寄存器中的值: 只需要一步,直接读取即可。
  • 取L1中的值: 先锁住缓存行,然后取出数据,最后解锁。如果没有锁住说明慢了。
  • 取L2中的值: 先到 L1 中取,L1 中不存在再到 L2 中取。L2 开始加锁,将 L2 中的数据复制到 L1 ,再执行从 L1 中读取数据的步骤,解锁 L2。
  • 取L3中的值: 同样地,先将数据由 L3 复制到 L2,然后从 L2 复制到 L1 ,从 L1 读取数据。

CPU 在读取数据时,先在 L1 中寻找,再从 L2 中寻找,再从 L3 中寻找,然后是内存,最后是外存储器。

CPU优化手段

为了提高程序运行的性能,现代 CPU 在很多方面对程序进行了优化。

缓存

CPU 高速缓存,尽可能地避免处理器访问主内存的时间开销,处理器大多会利用缓存提高性能。

运行时指令重排

为了提高 CPU 处理性能,CPU 可能会乱序执行。如,当 CPU 写缓存时发现缓存曲块正被其它 CPU 占用,为了提高 CPU 处理性能,可能将后面的读缓存命令优先执行。

注意,CPU 指令重排并非随意重排,需要遵守 as-if-serial语义 ,该语义表示:不管怎么重排序(编译器和处理器为了提高并行度),(单线程)程序的执行结果不能被改变。编译器,运行时和处理器都必须遵守 as-if-serial 语义。也就是说,编译器和处理器不会对存在数据依赖关系的操作做重排序

问题

基于高速缓存很好地解决了处理器与内存的速度矛盾,但是也引入了新的问题-缓存一致性(CacheCoherence)。缓存中的数据与主内存的数据并不是实时同步的,各 CPU(或 CPU 核)间缓存的数据也不是实时同步。也就是说,在同一个时间点,各 CPU 所看到同一内存地址的数据的值可能不一致。如,当多个处理器执行的任务都涉及到同一块主内存区域时,将可能导致各自的缓存数据不一致的情况,这样不一致的情况如果同步回主内存时以哪个处理为准呢?

运行在左侧 CPU 上的一个线程将共享对象复制到其 CPU 缓存中,并将其count变量更改为 2。此更改对运行在右侧 CPU 上的其他线程不可见,因为更新的count尚未刷新回主内存.

总线锁

所有内存的传输都发生在一条共享的总线上,所有的处理器都会使用该总线。虽然 CPU 缓存各自是独立的,但是主存是共享的,所有的内存访问都要经过总线加锁机制来决定是否可以进行内存的读写,也就是说在同一个指令周期中,只可能有一个 CPU 可以读写内存。

所谓总线锁就是使用处理器提供的一个 LOCK#信号 ,当一个处理器在总线上输出此信号时,其他处理器的请求将被阻塞住,只有该处理器可以独占共享内存。

缓存一致性协议

总线锁虽然可以保证缓存数据的一致性,但是它比较粗暴,当某个 CPU 对总线进行加锁后,所有后续其它 CPU 对主存的操作都是阻塞的,这样机制就必定会降低性能。因此,缓存一致性协议出现了,它是硬件程序的产物,用来保证缓存之间可见。

缓存一致性协议有多种,如 MSIMESI 等,多数 CPU 厂商对缓存一致性协议进行了实现。下面我们以 MESI 协议为例,对其进行介绍。

MESI协议规定每个缓存行有个状态位,同时定义了下面四个状态:

专有态(Exclusive)

锁住的缓存行内容只存在当前 CPU 缓存中且同于主存,不出现于其它缓存中,所以当 CPU 发现自己缓存中的共享数据是专有态(Exclusive)时,说明该数据是最新的,可以直接读取。

当缓存行处于专有态(Exclusive)时,在任何时刻当有其它 CPU 缓存了该数据时,那么缓存行会由专有态(Exclusive)变成共享态(Shared)

共享态(Shared)

锁住的缓存行同于主存,且该缓存行可能被多个 CPU 缓存,各个缓存与主内存数据一致,所以当 CPU 发现自己缓存中的共享数据是共享态(Shared)时,说明该数据是最新值,可以直接读取。

当缓存行处于共享态(Shared)时,当任一个 CPU 修改缓存行时,其它 CPU 中该缓存行变成无效态(Invalid)

修改态(Modified)

锁住的缓存行已被修改(脏行),内容已不同于主存。该状态是一个中间状态,缓存行的数据需要在未来某个时间点写回主内存,当被写回主内存之后,该缓存行就会变成专有状态。

当 CPU 对缓存行进行修改时,变为修改态(Modified),并且同时会向其他缓存了该数据的 CPU 缓存发送一条 Invalid 指令,告诉其他缓存自己对数据进行了修改,让它们把数据对应的缓存行置为无效态(Invalid); 当收到其它 CPU 缓存 Invalid 指令的成功响应时,当前 CPU 缓存会就会把数据同步到主存里面去,然后自己的缓存行由修改态(Modified)变为专有态(Exclusive),当有其他 CPU 缓存从主存中读取到了最新的数据时,数据状态会变为共享态(Shared)

无效态(Invalid)

当缓存行处于无效态(Invalid)时,说明对应的数据已经被其它 CPU 修改过了,当前锁住的缓存行无效,必须从主存中重新读取。

无效态(Invalid)是由于收到其它 CPU 发来的 Invalid 指令,收到该指令的 CPU 缓存会把对应的缓存行状态标记为无效态(Invalid),所以当数据处于无效态(Invalid)时表示数据已经被别人修改了,当前数据是无效的。

多处理器时,单个 CPU 对缓存中数据进行改动需要通知给其他 CPU 。也就意味着在缓存一致性协议下,CPU 处理要控制自己的读写操作,还要监听(嗅探)其它 CPU 发出的通知,从而保证最终一致

这里需要说明下,MESI协议可以在 CPU 修改数据时向其他 CPU 发送消息,但不会出现两个CPU同时修改数据,进而向其他CPU进行消息通知。这样的并发修改通过缓存锁定机制解决的,它会锁定这块内存区域的缓存并回写到内存,并使用缓存一致性机制来确保修改的原子性。只有在数据修改的时候才会需要加缓存锁,修改数据的时候先锁定缓存行,不让其他CPU同时修改,其他CPU读取数据是允许的。缓存是否失效是由缓存一致性协议来处理的,它解决一个 CPU 修改其它 CPU 看不到的问题。缓存锁解决几个 CPU 并发修改的问题。

以下两种情况下处理器会使用总线锁:

  • 当操作的数据不能被缓存在处理器内部,或操作的数据跨多个缓存行时
  • 处理器不支持缓存锁定

Store Buffer

前文在描述 MESI 协议时,如果对缓存行进行修改需要经历以下过程:

  1. 某个CPU修改自己缓存的值
  2. 修改缓存后通知其它CPU,等待其它CPU响应
  3. 收到所有CPU的响应
  4. 将缓存中的数据同步到主存

可以看到,以上整个过程都是同步的,CPU 发送完通知后必须同步等待所有其它 CPU 的响应,而这个过程中当前 CPU 又无法释放出来,所以为了避免这种 CPU 运算资源的浪费,就需要一种方式来进行优化了,此时 Store Buffer 就出来了。

当 CPU 对某个共享变量修改时,向其他 CPU 发出 Invalid 指令后不同步等待其他 CPU 指令的响应了,而是直接把最新值写入 Store Bufferes 缓冲区里,然后直接可以去干别的事情了,直到所有的 CPU 都对 Invalid 指令响应后,再把共享变量的值从 Store Buffere 里拿出来,然后写入到自己的缓存里同时同步到主存中。

Store Forward

Store Forward 称为存储转发。具体是:当 CPU 读取数据时需要先检查它的 Store Buffer 缓冲区中有没有,如果有则直接读取该缓冲区中的值,没有才会读取自己缓存中的值。解决了 Store Buffer 优化过程中由于只读取缓存导致的缓存脏数据问题。

至此,Store Buffer 优化提升了 CPU 效率。但由于修改共享变量先是放到了 Store Buffer 中,只有等到其它 CPU 返回 Invalid OK 后才会同步到缓冲和主存。可以看出执行写操作不是立即生效的,对于有相互依赖的共享数据相关指令,可能会出现CPU乱序执行的现象。解决手段是利用内存屏障禁用CPU缓存优化,也就是更新数据时必须立即更新到主存(也就是把store buffer里的指令全部执行完)。

Invalid Queue

因为 Store Buffer 空间很小,如果有大量的变量修改,它会存储不下,那么这个时候又回到同步通知的状态。此外,有时候其它 CPU 很繁忙并不能马上进行响应,因此为了避免同步等待响应的时间太长,就为每个 CPU 加一个失效队列,当 Store Buffer 存不下的时候,就把失效通知发送到其它 CPU 的失效队列里,只要队列成功接收到了发送的消息就进行响应(发送 Invalid 指令的 CPU 就可以将修改同步到主存了),等到其他CPU闲下来了就从各自的失效队列里读取消息然后失效掉CPU的缓存数据。

MESI 优化到了 Invalid Queue 阶段,一般来说性能已经很高了,但是在极端的情况下会出现缓存可见性问题。具体来说就是,接收到 Invalid 指令的 CPU 没有来得及处理它的实效队列中的消息,没有及时失效掉对应的缓存行,导致继续使用了本应该失效的缓存数据。这种因为CPU缓存优化而导致后面的指令查看不到前面指令的执行结果,就好像指令之间的执行顺序错乱了一样,这类现象也就是我们俗称的CPU乱序执行。解决方法很简单,直接禁用 CPU 缓存优化即可,也就是修改共享数据的指令都同步完成就能保证数据的可见性了,但是这样又会降低整体的性能,这样有点得不偿失,因为毕竟大部分情况下数据都不存在这种共享的问题。不过我们必须要为这种场景提供一种手段来禁用CPU缓存优化,而这种手段同样也是内存屏障机制,读取数据时必须读取最新的数据(也就是必须先把失效队列的数据先读取应用完)。

内存屏障

前文我们说的内存屏障可以同时作用于 Store Buffer 和 Invalidate Queue 。而实际上,对于写操作只需关心 Store Buffer ,读操作只需关心 Invalidate Queue 。因此,大多数 CPU 架构将内存屏障分为了读屏障和写屏障。内存屏障本质上是 CPU 提供的一组指令,不同的操作系统有不同的实现。

读屏障: 任何读屏障前的读操作都会先于读屏障后的读操作完成,即读屏障指令执行后就能保证后面的读取数据指令一定能读取到最新的数据。
写屏障: 任何写屏障前的写操作都会先于写屏障后的写操作完成,即遇到写屏障指令就必须把该指令之前的所有写入指令执行完毕才可以往下执行,这样就可以让CPU修改的数据及时暴露给其它CPU。
全屏障: 同时包含读屏障和写屏障的作用

实际的 CPU 架构中,可能提供多种内存屏障,常见的如下:

  • LoadLoad: 相当于前面说的读屏障
  • LoadStore: 任何该屏障前的读操作都会先于该屏障后的写操作完成
  • StoreLoad: 任何该屏障前的写操作都会先于该屏障后的读操作完成
  • StoreStore: 相当于前面说的写屏障

实现原理都是类似的,如作用于Store Buffer和Invalidate Queue 。

指令重排问题

CPU 指令重排虽然遵守了 as-if-serial 语义,但仅在单 CPU 执行的情况下能保证结果正确。在多核多线程中,指令逻辑无法分辨因果关联,为了更好地利用流水线可能出现乱序执行,导致程序运行结果错误。

前文中谈的是内存屏障的可见性功能,它能够让屏障前的操作(读/写)及时执行、刷新,被其它 CPU 看到。而内存屏障还有个功能就是限制指令重排(读/写指令),否则即使内存屏障可以保证可见性,但由于不能保证指令重排,保证可见性意义也不大。

也就是说,内存屏障提供了一套解决CPU缓存优化而导致的顺序性和可见性问题的方案,但是由于不同的硬件系统提供的内存屏障指令可能都不一样,因此像 JAVA 这种高级编程语言就把不同的内存屏障指令统一进行了封装,让开发者不需要关心到系统的底层,而封装这套解决方案的模型就是Java内存模型(Java Memory Model)。

注意,除了运行期间 CPU 的指令重排,编译器在编译期间,可能也对指令进行重排,以使其对CPU更友好。

并发

了解了硬件内存架构后,从本小节开始,我们简单聊聊并发。

并发编程关键问题

在并发编程中需要处理两个关键问题:线程之间如何通信及线程之间如何同步。

通信是指线程之间以何种机制来交换信息。在命令式编程中,线程之间的通信机制有两种,共享内存和消息传递。共享内存通信机制中,线程之间共享程序的公共状态,通过写-读内存中的公共状态进行隐式通信。消息传递通信机制中,线程之间没有公共状态,线程之间必须通过发送消息来显式通信

同步是指程序中用于控制不同线程间操作发生的相对顺序的机制。在共享内存并发模型中,同步是显式进行的,也就是说程序员必须显式指定某个方法或某段代码需要在线程之间互斥执行。在消息传递的并发模型中,由于消息的发送必须在消息的接收之前,因此同步是隐式进行的。

Java 的并发采用的是共享内存模型,Java 线程之间的通信总是隐式进行,整个通信过程对程序员完全透明。

并发特性

随着 CPU、内存、I/O设备都在不断迭代,不断朝着更快的方向努力的同时,有一个核心矛盾一直存在,那就是这三者的速度差异。为了合理利用 CPU 的高性能,平衡这三者的速度差异,计算机体系结构、操作系统和编译程序都做出了贡献,具体体现为:

  • CPU 增加了缓存,以均衡与内存的速度差异。
  • 操作系统增加了进程、线程,以分时复用 CPU,进而均衡 CPU 与 I/O设备的速度差异。
  • 编译程序优化指令执行次序

总结起来就是:硬件增加缓存、软件增加线程、编译程序优化指令顺序。

以上优化带来好处的同时,也给并发程序埋下了祸根。带来的问题可以总结为:

  • 缓存导致可见性问题
  • 线程切换导致原子性问题
  • 指令优化导致有序性问题

下面我们对以上问题详细说明。

可见性

一个线程对共享变量的修改,另外一个线程能够立刻看到,我们称为可见性

在单核时代,所有的线程都是在一颗 CPU 上执行,CPU 缓存与内存的数据一致性容易解决。因为所有线程都是操作同一个 CPU 的缓存,一个线程对缓存的写,对另外一个线程来说一定是可见的。例如,线程 A 和线程 B 都是操作同一个 CPU 里面的缓存,所以线程 A 更新了变量 V 的值,那么线程 B 之后再访问变量 V,得到的一定是 V 的最新值(线程 A 写过的值)。

多核时代,每颗 CPU 都有自己的缓存,这时 CPU 缓存与内存的数据一致性就没那么容易解决了,当多个线程在不同的 CPU 上执行时,这些线程操作的是不同的 CPU 缓存,它们是无法直接通信的。

原子性

一个或者多个操作在 CPU 执行的过程中不被中断的特性称为原子性

Java 并发程序都是基于多线程的,自然会涉及到线程切换,切换的时机大多数是在时间片结束的时候。操作系统做任务切换,可以发生在任何一条CPU 指令执行完,注意是 CPU 指令而非高级语言中的一条语句,因为高级语言中的一条语句可能包含多条 CPU 指令。也就是说,CPU 能保证的原子操作是 CPU 指令级别的,而不是高级语言级别。因此,很多时候需要我们自己在高级语言层面保证操作的原子性

有序性

有序性指的是程序按照代码的先后顺序执行。但编译器、处理器为了优化性能有时会改变程序执行的次序,而这也是导致问题的原因。

缓存、线程、编译优化的目的都是提高程序性能的,但是技术在解决一个问题的同时,可能会带来另外一个问题,所以在采用一项技术的同时,一定要清楚它带来的问题是什么,以及如何规避。

JMM

Java 的内存模型(JMM)本质上是一种编程语言规范,屏蔽了不同处理器内存模型的差异,它在不同的处理器平台之上为 Java 程序员呈现了一个一致的内存模型。不同点在于,JMM 是一个语言级的内存模型,处理器内存模型是硬件级的内存模型。JMM 通过定义多项规则对编译器和处理器进行限制,主要围绕原子性、有序性、可见性展开,具体来说包括 volatitle、synchronized 和 fianl 这三个关键字,以及系列 happens-before 原则

注意:JVM 内存模型和 Java 内存模型是完全不同的两个东西。JVM内存模型是一种内存逻辑划分,便于JVM 管理内存;JMM内存模型是对计算机硬件(处理器模型)的统一抽象,用来屏蔽差异。

细化规范

JMM 描述了程序的可能行为,程序执行产生的结果都可以由内存模型预测,它决定了在程序的每个点上可以读取什么值(读写是相互的,也就是写了后,读必须要读取到,这就要求写必须刷新到主内存)。既然 JMM 是一种规范,就需要给 JVM 开发者和厂商实现,需要细化规范。

共享变量

可以在线程之间共享的内存称为共享内存或堆内存。所有实例字段,静态字段和数组元素都存储在堆内存中。Java 内存模型的抽象示意图如下:

JMM 定义了线程和主内存之间的抽象关系:线程之间的共享变量存储在主内存中,每个线程都有一个私有的本地内存,本地内存中存储了该线程以读/写共享变量的副本,线程对变量的所有操作都必须在本地内存中进行,而不能直接操作主内存中的变量。注意,本地内存是 JMM 的一个抽象概念,并不真实存在。

如果线程 A 与线程 B 之间要通信的话,必须经历以下2个步骤:

  • 线程 A 把本地内存中更新过的共享变量刷新到主内存中去。
  • 线程 B 到主内存中去读取线程 A 之前已更新过的共享变量

关于主内存与本地内存之间的具体交互,即一个变量如何从主内存拷贝到本地内存、如何从本地内存同步到主内存之间的实现细节,Java内存模型定义了以下八种操作来完成。

  1. lock:作用于主内存,把变量标识为线程独占状态
  2. unlock:作用于主内存,解除独占状态
  3. read:作用主内存,把一个变量的值从主内存传输到线程的本地内存
  4. load:作用于本地内存,把 read 操作传过来的变量值放入本地内存的变量副本中
  5. use:作用本地内存,把本地内存当中的一个变量值传给执行引擎
  6. assign:作用本地内存,把一个从执行引擎接收到的值赋值给本地内存的变量
  7. store:作用于本地内存的变量,把本地内存的一个变量的值传送到主内存中
  8. write:作用于主内存的变量,把 store 操作传来的变量的值放入主内存的变量中

如果要把一个变量从主内存中复制到本地内存中,就需要按顺序地执行read和load操作, 如果把变量从本地内存中同步到主内存中,就需要按顺序地执行store和write操作。但Java内存模型只要求上述操作必须按顺序执行,而没有保证必须是连续执行。

如前所述,Java 内存模型和硬件内存架构是不同的。不管是本地内存的数据还是主内存的数据,对于计算机硬件来说都会存储在计算机主内存中,当然也有可能存储到CPU缓存或者寄存器中,因此总体上来说,Java内存模型和计算机硬件内存架构是一 个相互交叉的关系,是一种抽象概念划分与真实物理硬件的交叉。具体如下图所示:

当对象和变量可以存储在计算机中各种不同的内存区域时,可能会出现某些问题,两个主要问题是:

  • 线程更新(写入)共享变量的可见性
  • 读取、检查和写入共享变量时的竞争条件