一,深入理解cas底层的执行原理

1,什么是cas

在讲底层原理之前,一定需要先了解JMM的内存模型以及多线程的通信机制,可以查看我写的前几篇文章。

Compare And Swap:顾名思义,就是比较与交换的意思。cas是一个指令,底层是一个无锁的算法,可以在并发场景中保证数据的原子性。

cas主要是针对某一个变量,对该值在不同线程位置的比较与交换,通过自旋的方式,实现主内存值,工作内存的旧值和工作内存的新值直接的操作,通过比较主内存的变量值和工作内存的初始值是否相等,来判断是否可以将工作内存的新值对主内存的值进行替换的操作。cas的比较与交换是一个原子操作,要么同时成功,要么同时失败。

但是cas并不是在java层面直接去实现,而是要借助于硬件底层去实现,如下面一些常见的比较与交换的方法中,都是通过调用native方法区实现的。

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

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

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

而上面的四个参数,分别对应的是:对象,偏移量,工作内存初始值,工作内存新值

2,cas的自旋原理

接下来先举一个例子,假设此时主内存中有一个值x等于10,然后有三个工作线程thread1,thread2,thread3,用K表示主内存中的x,用M表示工作线程中的x,用N表示工作线程修改后的值,假设此时三个工作线程同时去对这个工作线程的x的值做一个类加操作,在用cas的情况下,来讲一下底层的实现逻辑

假设此时线程thread1获取到了这个x值,此时线程thread1的M值为10,N值为11,随后进行比较操作,如果此时主内存的值还是10,那么CAS就会认为此时还没有线程改过这个值,此时M的值等于K,比较成功后再进行交换,此时工作内存的K对应的x值就是11

但是可能也会出现另外一种情况,此时线程thread1中M的值还是10,N为11,但是此时线程2先对主内存的值进行修改,就是此时K的值变成了11,在比较的时候,发现旧值M和主内存的K值不一样,那么就比较失败,那么就不能进行交换

如果此时直接将这次失败直接丢弃,那么很显然不能保证cas的原子性,cas内部是这样做的,他会携带最新的值继续自旋,此时线程1的M值变成了11,N值变成了12,M值再和K值相比,如果比较一致,则将最新的12交换,如果比较失败,则继续携带最新值轮询,一直重复下去,这样就能保证原子性了

 

再了解完整个代码流程之后,再来看一段AtomicInteger类的incrementAndGet()的自增操作

//var1:对象        var2:偏移量,找到对应的变量值
//var4:值1         var5:内存中的值,旧值
public final int getAndAddInt(Object var1, long var2, int var4) {
   
     
    int var5;
    do {
   
     
        //获取旧值,内存中的值
        var5 = this.getIntVolatile(var1, var2);
        //比较与交换,如果var5和var1的值相对,则将最新值var5+var4写回
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
	//将旧值返回,返回后进行+1操作
    return var5;
}

3,cas的底层实现原理

cas是一个指令,具体如何实现的,这就得看jvm层面的逻辑了。由于这个涉及到多线程之间的通信问题,因此需要考虑线程间的可见性和有序性,在hotspot虚拟机中,由于cas本身就是一个原子指令,所以在jvm底层,就直接在方法中加了一个 #lock 的前缀指令,这样就实现了一个类似于内存屏障的功能,这样就保证了线程之间的有序性和可见性。

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

这里的第二个参数是一个偏移量,通过第一个参数的对象头加上压缩指针来确认x的位置。

在Hotspot虚拟机的底层源码中,主要的核心cas算法是通过Atomic::cmpxchg 方法来实现的。在这个方法中,第一个参数是要交换的值,第二个参数是偏移量,第三个参数是比较的值

#atomic_linux_x86.inline.hpp
inline jint Atomic::cmpxchg(jint exchange_value, volatile jint* dest, jint compare_value) {
   
     
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
            : "=a" (exchange_value)
            : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
            : "cc", "memory");
  return exchange_value;

首先会判断当前的执行环境是否为多处理器环境,目前一个cpu中基本是有两个处理器的

int mp = os::is_MP();

如果上面判断是一个多核处理器架构,那么就会在方法前面加一个 Lock 前缀指令,这样就保证了后面的比较与交换之间的原子性

(LOCK_IF_MP(%4)

随后通过cmpxchg方法进行比较与交换的操作,这里的%1和%3代表的是第1个和第三个参数。并且在调用这个方法的时候,在操作系统底层会进行一个总线加锁的机制,就是一把独占锁,整体操作变成一个串行操作。

cmpxchgl %1,(%3)

如果是=a,那么代表比较与交换成功,则直接将exchange_value值返回

"=a" (exchange_value)

如果是r,那么就代表比较与交换失败,那么返回的值就是内存里面的值

"r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)

上面的源码是linux_x86系统的源码,不同的操作系统之间,其底层实现也不同

4,cas的缺陷以及不足

4.1,长时间自旋耗费cpu资源

cas是通过无锁算法来保证数据的同步的,synchronized,lock等是通过加锁的方式来保证数据的同步的,并且要涉及到用户态和内核态之间的来回切换,但是cas是不需要来回切换的,而是不断的自旋加配合底层硬件来解决

但是cas也会出现一个问题,在并发量比较大的时候,就会需要不断的进行自旋的操作,此时就会占用大量的cpu,从而影响整个系统的性能和效率。因此需要通过不同的场景来判断是否使用CAS

4.2,只能有一个共享变量的操作

虽然上面谈到了比较和交换的操作,但是整个流程都是围绕一个对象来进行的,如果存在多个对象就得多写几个cas的程序,这也是cas的一个缺陷。

4.4,ABA问题

依旧是下图,假设thread1获取到值,此时thread2也拿到了值,将值改成11,比较交换之后,此时主内存的值为11,但是thread3拿到值后,又通过比较交换将值改成了10,此时正好轮到thread1来进行比较交换,发现主内存的值和thread1的原始值是一样的,就认为此时还没有线程改了这个值,于是进行比较交换操作

 

其实是已经被别的线程将值修改了,但是当前线程认为该值还没有被修改过。

如男女朋友分手了,但是女方又恋爱了,又分手,然后男方再次找到女方,发现女方还是单身,男方就认为这段时间女方没有恋爱,但是女方期间谈了多少次男方并不知情,并且可能给男方带回一个小朋友…,所以说,这种问题是很严重的

那么如何解决这种ABA问题,直接看Atomic里面是怎么解决的吧,在Atomic包下面有一个AtomicStampedReference 类,在该类中有一个静态内部类 Pair,里面除了一个对象的引用之外,另外增加了一个stamp的一个版本,这个有点类似于乐观锁,每被操作一次,版本号就加1,通过这种加版本号来保证这个变量是否被更改过。

private static class Pair<T> {
   
     
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
   
     
        this.reference = reference;
        this.stamp = stamp;
    }
    static <T> Pair<T> of(T reference, int stamp) {
   
     
        return new Pair<T>(reference, stamp);
    }
}

其创建对象的方式如下,第一个参数表示初始值,第二个参数表示版本。

AtomicStampedReference atomicStampedReference = new AtomicStampedReference(1,1);
// 构造方法如下
public AtomicStampedReference(V initialRef, int initialStamp) {
   
     
    pair = Pair.of(initialRef, initialStamp);
}

当然了,除了加版本号之外,还有一个加标记的方式解决,其原理很简单,就是只要被加载过,那么就给他一个mark标记,在atomic原子包下面就有这么一个类 AtomicMarkableReference

public class AtomicMarkableReference<V> {
    private static class Pair<T> {
        final T reference;
        final boolean mark;
        private Pair(T reference, boolean mark) {
            this.reference = reference;
            this.mark = mark;
        }
        static <T> Pair<T> of(T reference, boolean mark) {
            return new Pair<T>(reference, mark);
        }
    }
}

在里面的静态内部类中,除了引用之外,还存在一个布尔类型的mark标志位,只有被加载过,那么就对这个标志位设置一个true。

5,通过Atomic举例cas

首先定义一个AtomicInteger的原子类,随后进行一个值更新的操作

//这里初始化为0,这个0是当前线程的初始值
AtomicInteger atomicInteger = new AtomicInteger(0);
// 0是主内存中的最新值,10是要更新的值
atomicInteger.compareAndSet(0,10);

随后再次分析这个compareAndSet方法,可以发现里面调用了这个compareAndSwapInt方法

public final boolean compareAndSet(int expect, int update) {
   
     
    //比较与交换
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

如果主内存的最新值和当前线程的初始值一致,则进行更新的操作,否则携带最新值继续进行自旋的操作。

6,总结

cas比较和交换,通过jmm的java内存模型,借助于自旋的方式不断的去进行比较与交换,在每个对象的比较与交换中,主要是通过调用jvm的native本地方法去实现,从而去调用操作系统,在操作系统底层,cas借助了锁总线的串行方法来保证整个命令的原子操作,从而可以保证最终结果的一致性。

相对于其他的重锁,cas底层采用的是无锁算法,通过#lock前缀指令达到内存屏障的效果,从而保证数据的可见性,一致性和有序性,其内部需要花费的时间,也远远小于其他的重锁,如synchronized等。