CAS指令与MESI缓存一致性协议

锁机制存在的问题

在JDK 5之前Java语言是靠synchronized关键字保证同步的，这会导致有锁

锁机制存在以下问题：

（1）在多线程竞争下，加锁、释放锁会导致比较多的上下文切换和调度延时，引起性能问题。

（2）一个线程持有锁会导致其它所有需要此锁的线程挂起。

（3）如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置，引起性能风险。

volatile是不错的机制，它是通过汇编语言中的LOCK指令实现的，但是volatile不能保证原子性。因此对于同步最终还是要回到锁机制上来。

独占锁是一种悲观锁，synchronized就是一种独占锁，会导致其它所有需要锁的线程挂起，等待持有锁的线程释放锁。

而另一个更加有效的锁就是乐观锁。所谓乐观锁就是，每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。乐观锁的缺点是不能解决脏读的问题。乐观锁用到的机制就是CAS，Compare and Swap。

 

什么是CAS

CAS的全称为Compare And Swap，直译就是比较交换。是一条CPU的原子指令，其作用是让CPU先进行比较两个值是否相等，然后原子地更新某个位置的值，其实现方式是基于硬件平台的汇编指令，在intel的CPU中，使用的是CMPXCHG指令，就是说CAS是靠硬件实现的，从而在硬件层面提升效率。

它是一个无锁的原子算法。无锁也就没有加锁和解锁的过程，不存在阻塞，也就提高了效率，提高了CPU的吞吐量（单位时间内执行完成的操作条数就多了）

CAS 操作包含三个操作数 —— 内存位置(V)、预期原值(A)和新值(B)。如果内存位置的值V与预期原值A相匹配，那么处理器会自动将内存位置值更新为新值B 。否则，处理器不做任何操作。最后，CAS 返回当前V的真实值（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值）。CAS 操作时抱着乐观的态度进行的，它总是认为自己可以成功完成操作。

当多个线程同时使用CAS 操作一个变量时，只有一个会胜出，并成功更新，其余均会失败。失败的线程不会挂起，仅是被告知失败，并且允许再次尝试，当然也允许实现的线程放弃操作。基于这样的原理，CAS 操作即使没有锁，也可以发现其他线程对当前线程的干扰。

与锁相比，使用CAS会使程序看起来更加复杂一些，但由于其非阻塞的，它对死锁问题天生免疫，并且，线程间的相互影响也非常小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，它要比基于锁的方式拥有更优越的性能。

简单的说，CAS 需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的。如果变量不是你想象的那样，那说明它已经被别人修改过了。你就需要重新读取，再次尝试修改就好了。

 

synchronized 和 CAS 的区别

  • synchronized 采用的是 CPU 悲观锁机制，即线程获得的是独占锁。独占锁就意味着其他线程只能依靠阻塞来等待线程释放锁。而在 CPU 转换线程阻塞时会引起线程上下文切换，当有很多线程竞争锁的时候，会引起 CPU 频繁的上下文切换导致效率很低。尽管 Java1.6 为 synchronized 做了优化，增加了从偏向锁到轻量级锁再到重量级锁的过度，但是在最终转变为重量级锁之后，性能仍然较低;
  • CAS并不是线程挂起，当CAS操作失败后会进行一定的尝试，而非进行耗时的挂起唤醒的操作，因此也叫做非阻塞同步。这是两者主要的区别;
  • 使用CAS时非阻塞同步，也就是说不会将线程挂起，会自旋(无非就是一个死循环)进行下一次尝试，如果这里自旋时间过长对性能是很大的消耗。如果JVM能支持处理器提供的pause指令，那么在效率上会有一定的提升。

 

CAS底层实现，以AtomicInteger类为例

源码来自我的JDK18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/** 
 * Atomically adds the given value to the current value. 
 * 
 * @param delta the value to add 
 * @return the previous value 
 */ 
private static final long VALUE
        = U.objectFieldOffset(AtomicInteger.class, "value");
private volatile int value;

//给值加delta，返回原先的值
public final int getAndAdd(int delta) {return U.getAndAddInt(this, VALUE, delta);}

public final int get() { 
    return value; 
}

Unsafe.class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@IntrinsicCandidate
public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

//就是调用了native方法
@IntrinsicCandidate
public final boolean weakCompareAndSetInt(Object o, long offset,
                                          int expected,
                                          int x) {
    return compareAndSetInt(o, offset, expected, x);
}

@IntrinsicCandidate
public final native boolean compareAndSetInt(Object o, long offset,
                                             int expected,
                                             int x);

compareAndSwapInt为native方法，对应底层hotspot虚拟机unsage.cpp

1
2
3
4
5
6
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) 
  UnsafeWrapper("Unsafe_CompareAndSwapInt"); 
  oop p = JNIHandles::resolve(obj); 
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset); 
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e; 
UNSAFE_END

这里可以看到最终使用了Atomic::cmpxchg来保证原子性。

Intel文档 http://faydoc.tripod.com/cpu/cmpxchg.htm

 

CAS 的缺点及解决方式

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

ABA问题

因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A， 那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。

ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A-B-A 就会变成1A-2B-3A。

从Java1.5开始JDK的atomic包里提供了一个类 AtomicStampedReference 来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

循环时间长开销大

在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，即自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销;

如果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用，第一它可以延迟流水线执行指令(de-pipeline),使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突(memory order violation)而引起CPU流水线被清空(CPU pipeline flush)，从而提高CPU的执行效率;

代码层面，破坏掉for死循环，当自旋超过一定时间或者一定次数时，return退出;

使用类似ConcurrentHashMap的方法。当多个线程竞争时，将粒度变小，将一个变量拆分为多个变量，达到多个线程访问多个资源的效果，最后再调用sum把它合起来，能降低CPU消耗，但是治标不治本;

只能保证一个共享变量的原子操作

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性;

这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。

从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作;

 

MESI 缓存一致性协议

有点没看懂

关于CAS指令最著名的传闻是CAS需要锁总线，因此CAS指令不但慢而且会严重影响系统并发度，即使没有冲突是也一样。不过在较新的CPU中（对于Intel CPU来说是486之后），事实并非如此。目前的CPU一般都采用了很好的缓存一致性协议，在很多情况下能够防止锁总线的发生，这其中最著名的就是Intel CPU中使用的MESI缓存一致性协议。

先来说说缓存一致性问题。为了提高数据访问效率，每个CPU上都有一个容量很小（现在一般是1M这个数量级），速度很快的缓存，用于缓存最常访问的那些数据。由于操作内存的速度实在太慢，数据被修改时也只更新缓存，并不直接写出到内存中去，这一来就造成了缓存中的数据与内存不一致。如果系统中只有一个CPU，所有线程看到的都是缓存中的最新数据，当然没问题。但如果系统中有多个CPU，同一份内存可能会被缓存到多个CPU中，如果在不同CPU中运行的不同线程看到同一份内存的缓存值不一样就麻烦了，因此有必要维护这多种缓存的一致性。当然要做到这一点只要一有修改操作，就通知所有CPU更新缓存，或者放弃缓存下次访问的时候再重新从内存中读取。但这 Stupid 的实现显然不会有好的性能，为解决这一问题，产生了很多维护缓存一致性的协议，MESI就是其中一种。

MESI协议的名称由来是指这一协议为缓存的每个数据单位（称为cache line，在Intel CPU上一般是64字节）维护两个状态位，使得每个数据单位可能处于M、E、S或I这四种状态之一。各种状态含义如下：

  • M: 被修改的。处于这一状态的数据只在本CPU中有缓存，且其数据已被修改，没有更新到内存中
  • E: 独占的。处于这一状态的数据只在本CPU中有缓存，且其数据没有被修改，与内存一致
  • S: 共享的。处于这一状态的数据在多个CPU中有缓存
  • I: 无效的。本CPU中的这份缓存已经无效了。

当CPU要读取数据时，只要缓存的状态不是I都可以从缓存中读，否则就要从主存中读。这一读操作可能会被某个处于M或E状态的CPU截获，该CPU将修改的数据写出到内存，并将自己设为S状态后这一读操作才继续进行。只有缓存状态是E或M时，CPU才可以修改其中的数据，修改后缓存即处于M状态。如果CPU要修改数据时发现其缓存不处于E或M状态，则需要发出特殊的RFO指令（Read For Ownership），将其它CPU的缓存设为I状态。

因此，如果一个变量在某段时间内只被一个线程频繁修改，则对应的缓存早就处于M状态，这时CAS操作就不会涉及到总线操作。所以频繁的加锁并不一定会影响系统并发度，关键是看锁冲突的情况严重不严重，如果经常出现冲突，即缓存一会被这个CPU独占，一会被那个CPU独占，这时才会不断产生RFO，影响到并发性能。

参考

https://www.51cto.com/article/682780.html

https://cloud.tencent.com/developer/article/1188211