面试中如何答好:CAS

2023年 10月 9日 27.1k 0

如何回答什么是CAS?

CAS是Compare And Swap的简称,单从字面理解是比较并替换,实际指的是Unsafe类中的三个方法compareAndSwapObject,compareAndSwapInt,compareAndSwapLong,三个方法分别是以比较并替换的方式对Object类型的数据,对int类型的数据,对long类型的数据保证其操作的原子性。

在CAS比较并替换的逻辑中有三个重要的概念:预估值,内存值,更新值,而比较替换的逻辑为:如果预估值等于内存值,则将内存值更新为更新值,否则就不更新。

比较和替换这两个动作,无论是在java层面实现还是在jvm层面实现在不加锁的情况下都是无法完全保证原子性的,因此不得不依赖硬件对于并发的支持,即操作系统底层提供了cmpxchg指令,这一个指令就可以完成比较和替换两个动作。那么即便是将两个动作浓缩到一个汇编指令里面,就能保证原子性吗?

答案是肯定的,这是因为计算机硬件自身支持一个汇编指令执行过程是不允许被中断的,这两个动作已经浓缩到了cmpxchg这一个汇编指令里面了,不能中断意味着这两个动作必须在同个cpu时间片段内完成,一气呵成,所以cmpxchg指令本身就具备了原子性。

但是不同的平台实现cas有不同的方式。这个汇编指令的名字可能也会不同,这个需要注意。

分析:

分析CAS前必须先明白原子性是什么。

什么是原子性

原子性:指事务的不可分割性,一个事务的所有操作要么不间断地全部被执行,要么一个也没有执行。

前置了解

我们都知道所有的程序都是运行在cpu上的,cpu执行的是机器码,如00,01,0A。因为这些指令操作起来太麻烦且不好记忆,所以后来有人发明了更加方便操作和好懂的汇编语言,汇编是一种低级语言,这里可以理解为机器码对外所呈现的样子,也可以干脆理解为cpu执行的就是汇编语言。基本每种平台都实现了自己的汇编语言,所以不同平台的汇编语言是不能通用的。

汇编和机器码的对应关系如下:

ADD reg8/mem8,reg8 对应 00

ADD reg16/mem16,reg16 对应 01

OR reg8,reg8/mem8 对应 0A

OR reg16,reg16/mem16 对应 0B

jvm是一个虚拟机,它有一套自己的字节码指令,它有一套内存管理机制和垃圾回收机制,它有自己的运行机制,它有类似与寄存器的操作数栈,它自身就是一台计算机,它专门运行java语言,java语言依靠jvm运行,需要先编译成字节码指令,就像C++语言运行要先编译成汇编语言一样。

jvm是C实现的,归根结底要运行在cpu上,所以我们可以知道java语言的运行过程为:java编译成c++,再编译成汇编,再编译成机器码。

通过一个例子来看下java代码到机器码的翻译过程:

java代码:i++

java代码编译成字节码反编译的代码:getstatic i 获取i的值 iconst_1    准备常量1 iadd        加1 putstatic   将修改后的值写回变量i

iadd会被jvm翻译成类似于下面的汇编代码:mov    (%rsp),%edx add    $0x8,%rsp add    %edx,%eax

而汇编指令add对应的二进制机器码为00,01等。

现在来理解下原子性概念中的不可分割和不间断执行

不可分割性就是原子性。而事物的不可分割则是事务不受外界影响。

不管是java还是c++代码,最终运行的时候都要被编译成机器码,而机器码是cpu运行的基本单元,所以只有一个机器码指令才是天然的不可分割,而为了方便开发和理解,每个平台都有一套对应机器码的汇编语言,以linux为例,操作系统会保证每个汇编指令的执行都是不允许被中断的,也就是一个汇编指令也是不可分割的。

多个指令就一定是分割的吗?

不一定,只要多个指令能够不间断执行就可以认为是没有被分割的。

那如何才算不间断执行呢?

不间断就是几个指令能够顺序执行,且执行过程中或者线程不可中断,或者线程中断后不受其他线程影响。

那什么是中断呢?

中断就是线程被挂起。

那什么时候线程才会被挂起呢?

java程序员都知道,线程执行过程中遇到锁的时候,如果没有获取到锁就会阻塞挂起。当调用wait方法,join方法,park方法的时候都会进入阻塞挂起的状态,但是这些状态都是程序员人为的,是可以避免的。

但是有一种挂起是不可避免的,我们知道cpu是串行的运行模式,一个时间点上只能运行一个线程。为了让所有的线程看起来都是在同时运行,操作系统的机制是将cpu的执行时间分成很多个细小的时间片段,由操作系统为每个线程分配时间片段,当轮到某个时间片段执行时,绑定此时间片段的线程才会被执行,当这个时间片段用完,当前的线程如果还没有执行完的话就会被挂起,等待再次被调度执行。这个过程中线程就被中断了。

中断后不受其他线程影响怎么理解?

例如synchronized代码块,虽然线程在执行代码块逻辑的时候会被cpu时间片段调度中断,但是synchronized关键字通过加锁的方式只允许一个线程进入代码块逻辑,这就保证了当前线程在运行代码块中逻辑的时候虽然会中断,但是不受其他线程的影响。

不能看出上面的说不可中断和中断不受其他线程影响对应的正是cas的方式和加锁的方式实现原子性。

本篇我们只看CAS方式

CAS实现原理

计算机做了什么?

我们知道了cas最终是靠计算机底层原语cmpxchg支持,下面就是linux_x86底层的汇编实现。

linux_x86底层实现

hotspotsrcos_cpulinux_x86vmatomic_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;
}

在这个方法中最关键的是一行代码是:LOCK_IF_MP(%4) "cmpxchgl %1,(%3),cmpxchgl关键字就是汇编指令原语,这个原语在不同的计算机的实现不一样,在linux_x86就叫做cmpxchgl。

而cmpxchg方法可以理解为linux_x86平台对外提供cas支持的API。

这段代码中我们看到LOCK_IF_MP关键字,看到lock一般我们会想到加锁,这里确实是加锁的意思,或许你会说cas操作为什么还要加锁,如果这样,那直接用加锁的方式实现原子性不就可以了,这段代码的逻辑其实是先判断是否为多核处理器,如果是多核就会加锁,如果单核就不加锁。而这个加锁的实现根据系统平台的不同会有不同的实现方式,大致分为锁总线和锁缓存。

我们说了,一条机器指令(或者说汇编指令)一定能在一个cpu时间片段内完成,如果两个线程占据两个时间片,这个两个时间片段都是要执行同一个指令,当一个时间片段执行完,才能执行下一个时间片段,这样看起来单个指令的执行是串行的,不会有问题,但是现在的处理器一般都会存在多核,甚至多cpu,每个核都会有自己的缓存,所以,多核情况下仅仅靠cas是无法保证原子性的,操作系统内部通过锁来规避。

这属于操作系统为实现更高效而不得不付出的复杂性。这里牵扯到缓存一致性协议,介绍操作系统的时候再细说。

JVM做了什么?

既然计算机提供了cas支持,那么应用程序怎么应用呢,java虚拟机为java实现提供了支持。

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; //执行Atomic类中的cmpxchg
UNSAFE_END

以上源码中真正实现cas的代码为:

Atomic::cmpxchg(x, addr, e)

不难看出,x为新值,addr为地址,e为期望值

jvm底层调用了汇编代码中的方法cmpxchg,这个方法就是上面汇编代码中方法。

上面这个方法是jvm底层实现,也是jvm对于cas的支持,jvm对外也提供了API,只不过是以本地方法的形式提供给java使用,它的体现就是 Unsafe类下面提供的三个本地方法compareAndSwapObject,compareAndSwapInt,compareAndSwapLong。

图片图片

这个几个方法的具体实现都在jvm内部。上面的jvm代码对应的就是compareAndSwapInt本地方法的具体实现,其他方法也都大同小异。

Unsafe类是java层面提供的用于内存管理的类,除内存操作方法外,同时还提供线程调度操作,,内存屏障相关操作等,但是它不是应用类加载器加载的,因此程序员是不能直接使用的。

我们来解释下这几个参数:

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

var1:要修改的对象起始地址 如:0x00000111

var2:需要修改的具体内存地址 如100 。0x0000011+100 = 0x0000111就是要修改的值的地址

注意没有var3

var4:期望内存中的值,拿这个值和0x0000111内存中的中值比较,如果为true,则修改,返回ture,否则返回false,等待下次修改。

var5:如果上一步比较为ture,则把var5更新到0x0000111其实的内存中。

原子操作,直接操作内存。

JAVA做了什么?

java提供了java.util.concurrent.atomic包,包下面提供了各种原子类,如下图。

图片图片

这些原子类底层基本都是依赖Unsafe类的三个方法实现。

接下来以AtomicInteger来介绍

先来看例子:

static int i=0;
public static void main(String[] args) throws IOException, InterruptedException {

Thread T1=new Thread(new Runnable(){
@Override
public void run(){
for(int n=0;n

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论