并发编程中的可见性与原子性

Scroll Down

1. 可见性

1.1 什么叫做可见性

可见性是指当多个线程访问同一个变量时,一个线程修改了这个变量的值,其他线程能够立即看得到修改的值。

1.2. 为什么会有可见性问题

可见性问题的根本原因是因为现代CPU在设计上解决CPU运算速度与内存读写速度不匹配问题而导致的。

这种访问速度的显著差异,导致CPU可能会花费很长时间等待数据到来或把数据写入内存。

基于此,现在CPU大多数情况下读写都不会直接访问内存(CPU都没有连接到内存的管脚),取而代之的是CPU缓存,CPU缓存是位于CPU与内存之间的临时存储器,它的容量比内存小得多但是交换速度却比内存快得多。而缓存中的数据是内存中的一小部分数据,但这一小部分是短时间内CPU即将访问的,当CPU调用大量数据时,就可先从缓存中读取,从而加快读取速度。

然而问题在于,多核CPU的前提下,多个CPU可能共享一个变量,如果其中一个CPU对这个变量进行了修改,另一个共享对CPU没有能够及时感知到这个变量的修改,还是用老数据进行运算,这就带来了问题。

举个例子,如图中所示,CPU-0和CPU-1共享变量A,这时候如果CPU-0修改了变量A,那么有以下流程:

  1. CPU-0修改本地副本为新值
  2. CPU-0将新值刷新到主内存中
  3. CPU-1感知到主内存值发生变化,修改本地副本的值

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled.png

问题在于,在还没执行到第3步的时候,如果CPU-1刚好用到这个变量,CPU-1选择自己本地的副本去处理,这也就没有获得CPU-0修改的新值,这就带来了不一致的问题。

值得一提的一点,可见性问题不仅存在于多核CPU中,单核CPU也有类似的“备份”带来这个问题,这点后续再研究。

1.3. 如何解决可见性问题

从上文我们知道,在不同 CPU 中运行的不同线程看到同一份内存的缓存值不一样就会存在可见性问题,我们一般有下面的方案,注意这里是有顺序的(诞生的思路)

1.3.1. 总线锁

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

1.3.2. 缓存锁

在同一时刻,我们只需保证对某个内存地址的操作是原子性即可,但总线锁定把CPU和内存之间的通信锁住了,这使得锁定期间,其他处理器不能操作其他内存地址的数据,所以总线锁定的开销比较大,目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。

需要注意的是:

但是有两种情况下处理器不会使用缓存锁定:

  1. 当操作的数据不能被缓存在处理器内部,或操作的数据跨多个缓存行(cacheline)时,则处理器会调用总线锁定。
  2. 有些处理器不支持缓存锁定。

缓存锁一般基于需要用到缓存一致性协议,最常见的有MESI协议,四个字母分别代表一种缓存行状态:

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled%203.png

基于缓存一致性协议,每个处理器通过嗅探在总线上传播的数据来检查自己缓存的值是不是过期了,当处理器发现自己缓存行对应的内存地址被修改,就会将当前处理器的缓存行设置成无效状态,当处理器对这个数据进行修改操作的时候,会重新从系统内存中把数据读到处理器缓存里。

1.3.3. 缓存一致性协议带来的问题

CPU 缓存行的状态是通过消息传递来进行的,如果 CPU0 要对一个在缓存中共享的变量进行写入,首先发送一个失效的消息给到其他缓存了该数据的 CPU。并且要等到他们的确认回执。CPU0 在这段时间内都会处于阻塞状态

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled%204.png

1.3.4. 引入Store Bufferes和Invalidate Queue

为了避免阻塞带来的资源浪费。在 cpu 中引入 了 Store Bufferes(存储缓存)Invalidate Queue(无效队列)
CPU0 写入共享数据时,直接把数据写入到 store bufferes 中,同时发送 invalidate 消息,然后继续去处理其他指令。
当收到其他所有 CPU 发送了 invalidate ACK消息时,再将 Store Bufferes 中的数据数据存储至 Cache 中。最后再从本地Cache同步到主内存。

但是 cpu 中引入 Store Bufferes 优化存在两个问题:

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled%205.png

  1. 图中第⑥、⑦步骤中,由于Invalidate消息进入队列后就给CPU-0返回了响应,不能保证第⑦步骤一定完成。
  2. 引入了 Store Bufferes 后,处理器会先尝试从 Store Bufferes 中读取值,如果 Store Bufferes 中有数据,则直接从Store Bufferes 中读取,否则就再从本地Cache中读取,从Store Bufferes读取数据存在脏读。

总结来说,Store Bufferes优化其实就是期望不阻塞CPU,让本该在阻塞之后唤醒继续执行的代码能够不需要堵塞,立刻执行,也就是改变了指令的执行顺序。

1.3.5. 内存屏障

为了指令重排序存在的问题,处理器提供了内存屏障指令,来让开发者自己决定,通过在需要的地方插入内存屏障阻止指令重排序。

在JVM中,内存屏障分为4类:

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled%201.png

StoreLoadBarriers是一个“全能型”的屏障,它同时具有其他3个屏障的效果。现代的多处理器大多支持该屏障(其他类型的屏障不一定被所有处理器支持)。执行该屏障开销会很昂贵,因为当前处理器通常要把写缓冲区中的数据全部刷新到内存中(BufferFullyFlush)。

2. 原子性

2.1. 什么叫做原子性

原子(atomic)本意是“不能被进一步分割的最小粒子”。

而原子操作(atomicoperation)意为一个操作或者多个操作 要么全部执行并且执行的过程不会被任何因素打断,要么就都不执行。

2.2. 多核处理器中的原子性问题

最典型的就是Java语言中的i++操作:

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled%202.png

举个例子,如果i=1,我们进行两次i++操作,我们期望的结果是3,但是有可能结果是2,结果对比原因可能是多个处理器同时从各自的缓存中读取变量i,分别进行加1操作,然后分别写入系统内存中。那么,想要保证读改写共享变量的操作是原子的,就必须保证CPU1读改写共享变量的时候,CPU2不能操作缓存了该共享变量内存地址的缓存。

2.3. 处理器如何解决原子性问题

  • 总线锁
  • 缓存锁

关于这两个方法,在上文的可见性中已经描述过,不复赘述。

2.4. Java中的原子操作

  • 除long和double之外的基本类型的赋值操作
  • 所有引用reference的赋值操作
  • java.concurrent.Atomic.*包中所有类的一切操作
  • 锁的语义可以保证临界区代码的原子性

其中long类型和double类型由于是8byte,也就是64bit,在32位系统中会被拆分为两个32位去存储操作,不能保证原子性。

2.5. CAS操作

java.concurrent.Atomic.*下很多包是通过循环CAS(compare and swap)实现原子操作的:

CAS是英文单词CompareAndSwap的缩写,中文意思是:比较并替换。CAS需要有3个操作数:内存地址V,旧的预期值A,即将要更新的目标值B。

CAS指令执行时,当且仅当内存地址V的值与预期值A相等时,将内存地址V的值修改为B,否则就什么都不做。整个比较并替换的操作是一个原子操作。

举个例子:

AtomicInteger这个类下面有个自增方法getAndIncrement(),我们逐层往下看:

public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
}
public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
}
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

compareAndSwapInt是一个本地方法,简单描述如下:

拿到内存位置的最新值v,使用CAS尝试修将内存位置的值修改为目标值v+delta,如果修改失败,则获取该内存位置的新值v,然后继续尝试,直至修改成功。

2.6. CAS存在的问题

CAS虽然很高效地解决了原子操作,但是CAS仍然存在三大问题。ABA问题,循环时间长开销大,以及只能保证一个共享变量的原子操作。

  • ABA问题。因为CAS需要在操作值的时候,检查值有没有发生变化,如果没有发生变化则更新,但是如果一个值原来是A,变成了B,又变成了A,那么使用CAS进行检查时会发现它的值没有发生变化,但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号,每次变量更新的时候把版本号加1,那么A→B→A就会变成1A→2B→3A。从Java1.5开始,JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用,并且检查当前标志是否等于预期标志,如果全部相等,则以原子方式将该引用和该标志的值设置为给定的更新值。

Untitled%20525f69f1c496471fa8f32db629bb7c72/Untitled%206.png

  • 循环时间长开销大。自旋CAS如果长时间不成功,会给CPU带来非常大的执行开销。
  • 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时,我们可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性,这个时候就可以用锁。还有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操作。比如,有两个共享变量i=2,j=a,合并一下ij=2a,然后用CAS来操作ij。从Java1.5开始,JDK提供了AtomicReference类来保证引用对象之间的原子性,就可以把多个变量放在一个对象里来进行CAS操作。

3. 参考