美团一面:什么是CAS?有什么优缺点?我说我知道AtomicInteger

2024年 4月 22日 68.1k 0

引言

传统的并发控制手段,如使用synchronized关键字或者ReentrantLock等互斥锁机制,虽然能够有效防止资源的竞争冲突,但也可能带来额外的性能开销,如上下文切换、锁竞争导致的线程阻塞等。而此时就出现了一种乐观锁的策略,以其非阻塞、轻量级的特点,在某些场合下能更好地提升并发性能,其中最为关键的技术便是Compare And Swap(简称CAS)。

CAS是一种无锁算法,它在硬件级别提供了原子性的条件更新操作,允许线程在不加锁的情况下实现对共享变量的修改。在Java中,CAS机制被广泛应用于java.util.concurrent.atomic包下的原子类以及高级并发工具类如AbstractQueuedSynchronizer(AQS)的实现中。

CAS的基本概念与原理

CAS是一种原子指令,常用于多线程环境中的无锁算法。CAS操作包含三个基本操作数:内存位置、期望值和新值。在执行CAS操作时,计算机会检查内存位置当前是否存放着期望值,如果是,则将内存位置的值更新为新值;若不是,则不做任何修改,保持原有值不变,并返回当前内存位置的实际值。

在Java中,CAS机制被封装在jdk.internal.misc.Unsafe类中,尽管这个类并不建议在普通应用程序中直接使用,但它是构建更高层次并发工具的基础,例如java.util.concurrent.atomic包下的原子类如AtomicInteger、AtomicLong等。这些原子类通过JNI调用底层硬件提供的CAS指令,从而在Java层面上实现了无锁并发操作。

这里指的注意的是,在JDK1.9之前CAS机制被封装在sun.misc.Unsafe类中,在JDK1.9之后就使用了 jdk.internal.misc.Unsafe。这点由java.util.concurrent.atomic包下的原子类可以看出来。而sun.misc.Unsafe被许多第三方库所使用。

CAS实现原理

在Java中,虽然Java语言本身并未直接提供CAS这样的原子指令,但是Java可以通过JNI调用本地方法来利用硬件级别的原子指令实现CAS操作。在Java的标准库中,特别是jdk.internal.misc.Unsafe类提供了一系列compareAndSwapXXX方法,这些方法底层确实是通过C++编写的内联汇编来调用对应CPU架构的cmpxchg指令,从而实现原子性的比较和交换操作。

cmpxchg指令是多数现代CPU支持的原子指令,它能在多线程环境下确保一次比较和交换操作的原子性,有效解决了多线程环境下数据竞争的问题,避免了数据不一致的情况。例如,在更新一个共享变量时,如果期望值与当前值相匹配,则原子性地更新为新值,否则不进行更新操作,这样就能在无锁的情况下实现对共享资源的安全访问。 我们以java.util.concurrent.atomic包下的AtomicInteger为例,分析其compareAndSet方法。

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

    //由这里可以看出来,依赖jdk.internal.misc.Unsafe实现的
    private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
    private static final long VALUE = U.objectFieldOffset(AtomicInteger.class, "value");

    private volatile int value;

    public final boolean compareAndSet(int expectedValue, int newValue) { 
        // 调用 jdk.internal.misc.Unsafe的compareAndSetInt方法
        return U.compareAndSetInt(this, VALUE, expectedValue, newValue);  
    }
}

Unsafe中的compareAndSetInt使用了@HotSpotIntrinsicCandidate注解修饰,@HotSpotIntrinsicCandidate注解是Java HotSpot虚拟机(JVM)的一个特性注解,它表明标注的方法有可能会被HotSpot JVM识别为“内联候选”,当JVM发现有方法被标记为内联候选时,会尝试利用底层硬件提供的原子指令(比如cmpxchg指令)直接替换掉原本的Java方法调用,从而在运行时获得更好的性能。

public final class Unsafe {
    @HotSpotIntrinsicCandidate  
    public final native boolean compareAndSetInt(Object o, long offset,  
                                                 int expected,  
                                                 int x);
}

compareAndSetInt这个方法我们可以从openjdk的hotspot源码(位置:hotspot/src/share/vm/prims/unsafe.cpp)中可以找到:

{CC "compareAndSetObject",CC "(" OBJ "J" OBJ "" OBJ ")Z", FN_PTR(Unsafe_CompareAndSetObject)},

{CC "compareAndSetInt", CC "(" OBJ "J""I""I"")Z", FN_PTR(Unsafe_CompareAndSetInt)},

{CC "compareAndSetLong", CC "(" OBJ "J""J""J"")Z", FN_PTR(Unsafe_CompareAndSetLong)},

{CC "compareAndExchangeObject", CC "(" OBJ "J" OBJ "" OBJ ")" OBJ, FN_PTR(Unsafe_CompareAndExchangeObject)},

{CC "compareAndExchangeInt", CC "(" OBJ "J""I""I"")I", FN_PTR(Unsafe_CompareAndExchangeInt)},

{CC "compareAndExchangeLong", CC "(" OBJ "J""J""J"")J", FN_PTR(Unsafe_CompareAndExchangeLong)},

关于openjdk的源码,本文源码版本为1.9,如需要该版本源码或者其他版本下载方法,请关注本公众号【码农Academy】后,后台回复【openjdk】获取

而hostspot中的Unsafe_CompareAndSetInt函数会统一调用Atomic的cmpxchg函数:

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {

oop p = JNIHandles::resolve(obj);

jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);
// 统一调用Atomic的cmpxchg函数
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;

} UNSAFE_END

而Atomic的cmpxchg函数源码(位置:hotspot/src/share/vm/runtime/atomic.hpp)如下:

/**
*这是按字节大小进行的`cmpxchg`操作的默认实现。它使用按整数大小进行的`cmpxchg`来模拟按字节大小进行的`cmpxchg`。不同的平台可以通过定义自己的内联定义以及定义`VM_HAS_SPECIALIZED_CMPXCHG_BYTE`来覆盖这个默认实现。这将导致使用特定于平台的实现而不是默认实现。
*  exchange_value:要交换的新值。
*  dest:指向目标字节的指针。
*  compare_value:要比较的值。
*  order:内存顺序。
*/
inline jbyte Atomic::cmpxchg(jbyte exchange_value, volatile jbyte* dest,
                             jbyte compare_value, cmpxchg_memory_order order) {
  STATIC_ASSERT(sizeof(jbyte) == 1);
  volatile jint* dest_int =
      static_cast(align_ptr_down(dest, sizeof(jint)));
  size_t offset = pointer_delta(dest, dest_int, 1);
  // 获取当前整数大小的值,并将其转换为字节数组。
  jint cur = *dest_int;
  jbyte* cur_as_bytes = reinterpret_cast(&cur);

  // 设置当前整数中对应字节的值为compare_value。这确保了如果初始的整数值不是我们要找的值,那么第一次的cmpxchg操作会失败。
  cur_as_bytes[offset] = compare_value;

  // 在循环中,不断尝试更新目标字节的值。
  do {
    // new_val
    jint new_value = cur;
    // 复制当前整数值,并设置其中对应字节的值为exchange_value。
    reinterpret_cast(&new_value)[offset] = exchange_value;
    // 尝试使用新的整数值替换目标整数。
    jint res = cmpxchg(new_value, dest_int, cur, order);
    if (res == cur) break; // 如果返回值与原始整数值相同,说明操作成功。

    // 更新当前整数值为cmpxchg操作的结果。
    cur = res;
    // 如果目标字节的值仍然是我们之前设置的值,那么继续循环并再次尝试。
  } while (cur_as_bytes[offset] == compare_value);
  // 返回更新后的字节值
  return cur_as_bytes[offset];
}

而由cmpxchg函数中的do...while我们也可以看出,当多个线程同时尝试更新同一内存位置,且它们的期望值相同但只有一个线程能够成功更新时,其他线程的CAS操作会失败。对于失败的线程,常见的做法是采用自旋锁的形式,即循环重试直到成功为止。这种方式在低竞争或短时间窗口内的并发更新时,相比于传统的锁机制,它避免了线程的阻塞和唤醒带来的开销,所以它的性能会更优。

Java中的CAS实现与API

在Java中,CAS操作的实现主要依赖于两个关键组件:sun.misc.Unsafe类、jdk.internal.misc.Unsafe类以及java.util.concurrent.atomic包下的原子类。尽管Unsafe类提供了对底层硬件原子操作的直接访问,但由于其API是非公开且不稳定的,所以在常规开发中并不推荐直接使用。Java标准库提供了丰富的原子类,它们是基于Unsafe封装的安全、便捷的CAS操作实现。

java.util.concurrent.atomic包

Java标准库中的atomic包为开发者提供了许多原子类,如AtomicInteger、AtomicLong、AtomicReference等,它们均内置了CAS操作逻辑,使得我们可以在更高的抽象层级上进行无锁并发编程。

图片图片

原子类中常见的CAS操作API包括:

• compareAndSet(expectedValue, newValue):尝试将当前值与期望值进行比较,如果一致则将值更新为新值,返回是否更新成功的布尔值。

• getAndAdd(delta):原子性地将当前值加上指定的delta值,并返回更新前的原始值。

• getAndSet(newValue):原子性地将当前值设置为新值,并返回更新前的原始值。

这些方法都是基于CAS原理,能够在多线程环境下保证对变量的原子性修改,从而在不引入锁的情况下实现高效的并发控制。

CAS的优缺点与适用场景

CAS摒弃了传统的锁机制,避免了因获取和释放锁产生的上下文切换和线程阻塞,从而显著提升了系统的并发性能。并且由于CAS操作是基于硬件层面的原子性保证,所以它不会出现死锁问题,这对于复杂并发场景下的程序设计特别重要。另外,CAS策略下线程在无法成功更新变量时不需要挂起和唤醒,只需通过简单的循环重试即可。

但是,在高并发条件下,频繁的CAS操作可能导致大量的自旋重试,消耗大量的CPU资源。尤其是在竞争激烈的场景中,线程可能花费大量的时间在不断地尝试更新变量,而不是做有用的工作。这个由刚才cmpxchg函数可以看出。对于这个问题,我们可以参考synchronize中轻量级锁经过自旋,超过一定阈值后升级为重量级锁的原理,我们也可以给自旋设置一个次数,如果超过这个次数,就把线程挂起或者执行失败。(自适应自旋)

另外,Java中的原子类也提供了解决办法,比如LongAdder以及DoubleAdder等,LongAdder过分散竞争点来减少自旋锁的冲突。它并没有像AtomicLong那样维护一个单一的共享变量,而是维护了一个Base值和一组Cell(桶)结构。每个Cell本质上也是一个可以进行原子操作的计数器,多个线程可以分别在一个独立的Cell上进行累加,只有在必要时才将各个Cell的值汇总到Base中。这样一来,大部分时候线程间的修改不再是集中在同一个变量上,从而降低了竞争强度,提高了并发性能。

图片图片

1. ABA问题: 单纯的CAS无法识别一个值被多次修改后又恢复原值的情况,可能导致错误的判断。比如现在有三个线程:image.png即线程1将str从A改成了B,然后线程3将str又从B改成了A,而此时对于线程2来说,他就觉得这个值还是A,所以就不会在更改了。

图片图片

而对于这个问题,其实也很好解决,我们给这个数据加上一个时间戳或者版本号(乐观锁概念)。即每次不仅比较值,还会比较版本。比如上述示例,初始时str的值的版本是1,然后线程2操作后值变成B,而对应版本变成了2,然后线程3操作后值变成了A,版本变成了3,而对于线程2来说,虽然值还是A,但是版本号变了,所以线程2依然会执行替换的操作。

Java的原子类就提供了类似的实现,如AtomicStampedReference和AtomicMarkableReference引入了附加的标记位或版本号,以便区分不同的修改序列。

美团一面:什么是CAS?有什么优缺点?我说我知道AtomicInteger-1图片

图片图片

总结

Java中的CAS原理及其在并发编程中的应用是一项非常重要的技术。CAS利用CPU硬件提供的原子指令,实现了在无锁环境下的高效并发控制,避免了传统锁机制带来的上下文切换和线程阻塞开销。Java通过JNI接口调用底层的CAS指令,封装在jdk.internal.misc类和java.util.concurrent.atomic包下的原子类中,为我们提供了简洁易用的API来实现无锁编程。

CAS在带来并发性能提升的同时,也可能引发循环开销过大、ABA问题等问题。针对这些问题,Java提供了如LongAdder、AtomicStampedReference和AtomicMarkableReference等工具类来解决ABA问题,同时也通过自适应自旋、适时放弃自旋转而进入阻塞等待等方式降低循环开销。

理解和熟练掌握CAS原理及其在Java中的应用,有助于我们在开发高性能并发程序时作出更明智的选择,既能提高系统并发性能,又能保证数据的正确性和一致性。

相关文章

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

发布评论