H5W3
当前位置:H5W3 > 其他技术问题 > 正文

CAS底层实现原理

  初入染缸,不知深浅,记少年长成。

前言

本文摘要: “CAS底层实现”、“cmpxchg指令”、“ ‘Intel汇编’ 与 ‘AT&T汇编’ 的区别”。

若有偏颇之处,欢迎指正。同时,若文章侵犯了你的权益,请及时与我联系:bycqgEmail@163.com。

一、CAS的实现

在学习Java并发时,一路往底层追溯,最终追寻到了CAS(Compare and Swap,比较并交换),学习过程中收获挺多的,所以写下此文,希望能对读者有所帮助。

首先讲下CAS的概念,CAS是一种乐观锁,乐观锁会假定“多线程环境下,线程与线程之间不会发生冲突”,然后执行相关操作,执行完毕准备对变量执行写入操作时,再来判断线程之间是否真正发生了冲突。若没发生冲突那最好,可以成功写入;若发生冲突,当前线程直接重试以上过程。

相比乐观锁,还有悲观锁,本文不展开。

1、CAS上层封装的应用

“AtomicInteger类”是CAS的一种上层封装,这里通过“AtomicInteger类”来保证“i++”这种复合操作的原子性,由上层封装开始,慢慢深入到CAS的底层实现。

  1. 不使用“AtomicInteger类”实现“i++”。
    • 先给出测试类:
    //开启1000个线程,每个线程对i加上1000
    //预期结果:1000000(一百万)
    public class Test {
    public static int i=0;
    //每个线程对i加上1000
    public static void add(){
    for (int j = 0; j < 1000; j++) {
    i++;
    }
    }
    public static void main(String[] args) throws InterruptedException {
    //存放1000个线程的数组
    Thread[] threads=new Thread[1000];
    //新建1000个线程 · 并且启动,每个线程的任务都是执行一次add()方法
    for (int j = 0; j < 1000; j++) {
    //新建一个线程,然后设置执行逻辑
    threads[j]=new Thread(()->{
    add();
    });
    //启动当前线程
    threads[j].start();
    }
    //确保main()方法所在的线程等待那1000个线程执行完之后,再执行
    for (Thread thread : threads) {
    thread.join();
    }
    System.out.println(i);
    }
    }
     
    • 不使用“AtomicInteger”实现“i++”对应的结果:
    996693
     
    • 结果为996693,并不为预期的100000,没有保证“i++”这种复合操作的原子性,存在并发问题。
  2. 使用“AtomicInteger类”实现“i++”。
    • 先给出测试类:
    //开启1000个线程,每个线程对i加上1000
    //预期结果:1000000(一百万)
    public class Test {
    public static AtomicInteger i=new AtomicInteger();
    //每个线程对i加上1000
    public static void add(){
    for (int j = 0; j < 1000; j++) {
    i.incrementAndGet();
    }
    }
    public static void main(String[] args) throws InterruptedException {
    //存放1000个线程的数组
    Thread[] threads=new Thread[1000];
    //新建1000个线程 · 并且启动,每个线程的任务都是执行一次add()方法
    for (int j = 0; j < 1000; j++) {
    //新建一个线程,然后设置执行逻辑
    threads[j]=new Thread(()->{
    add();
    });
    //启动当前线程
    threads[j].start();
    }
    //确保main()方法所在的线程等待那1000个线程执行完之后,再执行
    for (Thread thread : threads) {
    thread.join();
    }
    System.out.println(i);
    }
    }
     
    • 使用“AtomicInteger”实现“i++”对应的结果:
    1000000
     
    • 结果为1000000,与预期的100000相等,使用“AtomicInteger类”实现了“i++”这种复合操作的原子,不存在并发问题。

2、CAS的通俗解释

之后涉及到“变量的加1操作”,这里简单描述一下。类似于“i++”这种加1操作,其实涉及到“取出i变量中的值”、“add指令对该值进行加1”、“把结果写回i变量”这3个原子操作,但这3个原子操作合在一起 · 形成的“i++”这种复合操作就不是原子性的。这在多线程环境下会产生并发问题,这里给出这个结论,更加深入的解释,本文不展开。

以下代码属于“伪代码”,旨在说明CAS原理,实际上无法做到真正意义上的CAS实现(代码之后会有解释 “为什么是伪代码” )。

CAS中涉及三个参数,分别是当前值_currval、预期值_expect、更新值_update,分别对应以下代码的i、backup、update。

以下代码的逻辑就是对i赋值给backup进行备份,然后将“加1”后的结果赋值给update,最后将这两个变量作为方法参数传入compareAndSwap(……)方法,通过该方法判断i是否被其他线程修改,没被修改的话,当前线程才能对i进行写入。

//CAS原理描述
public class Test {
private static int i;
//对i进行加1操作
public static void add() {
//先对i进行备份,即将i的值赋给backup(即预期值expect)
int backup = i;
//然后对i进行加1操作,加1后的值不立即赋给i,而是先赋给update(即更新值update)
int update = i + 1;
//检验i是否有被其他线程重新写入
compareAndSwap(backup, update);
}
//检验i是否有被其他线程重新写入
public static void compareAndSwap(int expect, int update) {
//如果i的值与之前备份的值一样,说明没被其他线程重新写入
if (i == expect) {
//那么当前线程就可以对i进行写入
i = update;
}
}
}
 

**为什么说 “以上代码是伪代码” 呢?
1、因为CAS实现的关键是 “比较、交换”这两个操作合在一起后 · 组成的复合操作要是原子性的。例如上面代码中的compareAndSwap(……)方法,该方法对应的就是这个复合操作,但关键点在于这个方法不是原子性的。该复合操作的原子性需要在底层通过硬件来实现,所以说以上代码是伪代码。

3、“AtomicInteger.java”源码分析

这里先大致讲一下CAS由上至下所涉及的:

1. AtomicInteger.java,上层封装,由程序员直接进行调用。
2. Unsafe.java,通过JNI(Java Native Interface,Java本地接口)对本地C代码“unsafe.cpp”进行调用。
3. unsafe.cpp,C++文件,内嵌汇编指令“cmpxchg指令”。
4. 汇编指令之“cmpxchg指令”,即compare and exchange,完成比较 · 并交换。
 

这里先分析一下AtomicInteger类的相关字段 · 以及静态代码块:

//源自JDK1.8_AtomicInteger源码
public class AtomicInteger extends Number implements java.io.Serializable {
//……省略部分
//unsafe实例对象
private static final Unsafe unsafe = Unsafe.getUnsafe();
//valueOffset字段 · 相对于对象首地址的地址偏移量
private static final long valueOffset;
//valueOffset赋值的具体实现
static {
try {
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
//value字段,存储目标值
private volatile int value;
//……省略部分
 

1、 value字段:该字段用来存储目标值,所有的一切都是围绕这个值展开的,目的是为了保证该值在多线程环境下的“读/写”安全。同时该字段用Volatile关键字修饰,保证最新写入的值的可见性。

2、valueOffset字段:地址偏移量。这个地址偏移量是value字段相对于首地址的偏移量。当想要取得value的值时,只需要通过“AtomicInteger实例对象在堆中的首地址”与“地址偏移量valueOffset”就可以获得。

3、unsafe字段:Unsafe实例对象。AtomicInteger类中对 “value字段存储的值” 的操作实际上是通过unsafe对象实现的;还有valueOffset字段也是通过unsafe对象得到的。

4、静态代码块:通过Unsafe_objectFieldOffset(……)方法对valueOffset字段进行赋值。

4、“Unsafe.java”源码分析

AtomicInteger实例对象 · 实际上是通过Unsafe实例对象来完成incrementAndGet()方法的调用:

//源自JDK1.8_AtomicInteger源码
public final int incrementAndGet() {
//调用Unsafe实例对象的getAndAddInt(……)方法
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
 

Unsafe对象_getAndAddInt0(……)方法的三个参数:

1、第一个参数“this”:指AtomicInteger对象,通过该实例对象可以获得该对象在堆中的首地址,然后配合valueOffset字段可以获得value字段。

2、第二个参数“valueOffset”:value字段相对于实例对象首地址的地址偏移量。

3、第三个参数“1”:这个1表示“在当前值的基础上加多少”,若为x,就是在当前值的基础上加x。

理解了三个参数所代表的含义后,再深入到Unsafe源码之中:

//源自JDK1.8_Unsafe源码
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;
}
 

通过AtomicInteger实例对象var1、地址偏移量var2对当前值进行备份 · 获得预期值var5,然后调用Unsafe实例对象的compareAndSwapInt(……)方法:

//源自JDK1.8_Unsafe源码
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
 

Unsafe_compareAndSwapInt(……)方法是一个本地方法,虚拟机通过JNI(Java Native Interface,Java本地接口)调用本地的C程序来实现CAS。

再来分析一下Unsafe_compareAndSwapInt(……)方法的四个参数:var1代表AtomicInteger实例对象;var2代表地址偏移量;var4代表预期值expect;var5代表更新值update。

5、“unsafe.cpp”源码分析

前面讲过Unsafe_compareAndSwapInt(……)方法是一个本地方法,现在进入本地C代码“unsafe.cpp”进行分析。

//源自OpenJDK_1.8_unsafe.cpp源码
static JNINativeMethod methods_18[] = {
//……省略部分
//各种数据类型 · 对应的缩写
DECLARE_GETSETOOP(Boolean, Z),
DECLARE_GETSETOOP(Byte, B),
DECLARE_GETSETOOP(Short, S),
DECLARE_GETSETOOP(Char, C),
DECLARE_GETSETOOP(Int, I),
DECLARE_GETSETOOP(Long, J),
DECLARE_GETSETOOP(Float, F),
DECLARE_GETSETOOP(Double, D),
//……省略部分
//Java与Cpp之间方法的对应
{CC"compareAndSwapInt",  CC"("OBJ"J""I""I"")Z",      FN_PTR(Unsafe_CompareAndSwapInt)}
//……省略部分
};
 

解释一下大括号{ }中各部分所代表的意思:

1、第一部分_CC”compareAndSwapInt”:对应Java中的方法名。

2、第二部分_CC”(“OBJ”J””I””I””)Z”:该方法涉及的参数及返回值,一个Object对象,一个Long型变量,两个Int型变量 · 以及Boolean型返回值。

3、第三部分_FN_PTR(Unsafe_CompareAndSwapInt):FN_PTR,Function Pointer,即函数指针;Unsafe_CompareAndSwapInt,即unsafe.cpp中的Unsafe_CompareAndSwapInt(……)函数。

接下来,分析一下Unsafe_CompareAndswapInt(……)函数,请看代码:

//源自OpenJDK_1.8_unsafe.cpp源码
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
UnsafeWrapper("Unsafe_CompareAndSwapInt");
//获得JVM层面对应的oop指针
oop p = JNIHandles::resolve(obj);
//获得当前值currval对应的内存地址
jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
//调用cmpxchg指针,并将该指针送回来的结果进行处理(? == e)
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
 

Unsafe_CompareAndSwapInt(……)方法做了什么?先获取最开始传入的AtomicInteger实例对象 · 在JVM层面对应的oop指针。然后,通过 “oop指针” 和 “地址偏移量valueOffset” 获得指针addr,即value字段对应的索引位置。最后,传入参数,调用cmpxchg指令。

6、“cmpxchg指令”分析

这里先讲个要点:Linux平台采用的汇编格式是“AT&T格式”,Windows平台采用的是“Intel格式”,涉及到本文的一个知识点就是 “两种格式的汇编指令的 ‘源操作数’ 和 ‘目的操作数’ 在指令中的位置是不一样的” 。

  1、“AT&T格式”:xx指令 源操作数, 目的操作数;
2、“Intel格式”:xx指令 目的操作数, 源操作数;

这里分析的cmpxchg指令是Linux平台下的,源自OpenJDK_1.8源码下的“atomic_linux_x86.inline.hpp”;而对该指令的具体说明来自Intel手册,但是因为分析的是Linux平台下的汇编指令,所以需要站在 “AT&T格式” 的角度上去查看该手册。

下面来看具体代码:

//源自OpenJDK_1.8_atomic_linux_x86.inline.hpp源码
//宏定义"LOCK_IF_MP(mp)"
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
//……省略部分
inline jint    Atomic::cmpxchg    (jint    exchange_value, volatile jint*    dest, jint    compare_value) {
//判断CPU是否为多核处理器,是的话,就返回,否则返回0
int mp = os::is_MP();
//执行汇编指令cmpxchg
__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;
}
//……省略部分
 

首先是宏定义:

#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
//以上长长一串有点难分析,化为以下形式:
cmp $0,#mp;
je 1f;
lock;
1:
 

cmp是比较传进来的mp是否与 “立即数0” 相等,相等就说明传进来的mp为0,即 “CPU不为多核处理器”,则je(jump equal)判断成立,直接跳到标号1处,即跳过lock前缀指令;若传进来的mp为1,则je判断不成立,就无法直接直接跳到标号1处,即需要执行lock前缀指令。

**这里想说明几点:

1、lock前缀指令执行时,要么锁住 “总线锁”,要么锁住 “缓存锁”,目的都是为了保证 “比较、交换” 这个复合操作的原子性,两个的区别在于 “效率高低”,lock前缀指令涉及很深,本文不展开。

2、“1f” 所代表的意思是:顺序跳转,跳转到标号1处。1代表标号1,f代表 “forward”,即向前的。与f对应的是d,代表 “backward”,即向后的。

至此,也就明白了CAS底层实现的原理,就是通过lock前缀指令,在硬件层面上解决并发问题。

下面,就继续分析cmpxchg指令:

//源自OpenJDK_1.8_atomic_linux_x86.inline.hpp源码
inline jint    Atomic::cmpxchg    (jint    exchange_value, volatile jint*    dest, jint    compare_value) {
//判断CPU是否为多核处理器,是的话,就返回,否则返回0
int mp = os::is_MP();
//执行汇编指令cmpxchg
__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;
}
 

在继续分析之前,还需要了解下内嵌汇编的基本格式:

asm ( Assembler Template
: Output Field
: Input Field
: Clobber/Modify Field
);
 

1、第一部分_Assembler Template:对应汇编指令,例如 “cmpxchgl %1,(%3)”,后面会通过Intel手册对 “cmpxchg” 指令进行分析。

2、第二部分_Output Field:对应输出。例如 “=a”,‘=’ 是个限定符,只能在Output域使用,表示操作数_exchange_value只能写入,而 ‘a’ 表示eax寄存器,所以 “=a” 表示最终要把exchange_value写入eax寄存器。

3、第三部分_Input Field:对应输入。例如 “a” (compare_value),指把compare_value的值放入eax寄存器。‘r’ 表示程序员不指定固定的寄存器,由编译器来指定。输入的参数可以通过 ‘%’ 来获取,例如 “%2” 就是获取eax寄存器中的compare_value的值。

4、第四部分_Clobber/Modify Field:对应额外参数。例如 “cc”,如果汇编指令会涉及到条件寄存器中的值,需要声明 “cc” 。“memory” 则是防止编译器对内嵌汇编指令进行优化。

cmpxchg指令分析:

//“AT&T格式”:xx指令 源操作数, 目的操作数;
cmpxchgl %1,(%3);
 

首先看看Intel手册对该指令的描述:

Compares the value in the AL, AX, or EAX register (depending on the size of the operand) with the first operand (destination operand). If the two values are equal, the second operand (source operand) is loaded into the destination operand. Otherwise, the destination operand is loaded into the AL, AX, or EAX register.

因为手册对应的是Intel格式的汇编,所以这里笔者将其翻译为“AT&T”格式的汇编的描述:

比较 “目的操作数的值” 和 “eax寄存器的值” ,如果两个值相等,则将 “源操作数的值” 送入 “目的操作数”。否则,将 “目的操作数的值” 送入eax寄存器。

“源操作数” 是更新值update,对应代码中的exchange_value变量;“目的操作数” 是当前值currval,对应代码中的dest指针;“exa寄存器中的值” 是预期值expect,对应代码中的compare_value。

这整个 “比较、交换” 过程如果分析起来反而容易乱,读者可以自己假设一下 “当前值为xxx”,“预期值为xxx”,“更新值为xxx” ,自行带入分析。

以上就是整个CAS底层实现的分析,希望对你有所帮助。

本文地址:H5W3 » CAS底层实现原理

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址