ToB企服应用市场:ToB评测及商务社交产业平台

标题: 美团一面：什么是CAS？有什么优缺点？我说我只用过AtomicInteger。。。。 [打印本页]
作者: 王國慶    时间: 2024-6-3 15:43
标题: 美团一面：什么是CAS？有什么优缺点？我说我只用过AtomicInteger。。。。
引言

传统的并发控制手段，如使用synchronized关键字或者ReentrantLock等互斥锁机制，虽然可以或许有效防止资源的竞争辩论，但也可能带来额外的性能开销，如上下文切换、锁竞争导致的线程阻塞等。而此时就出现了一种乐观锁的策略，以其非阻塞、轻量级的特点，在某些场合下能更好地提升并发性能，其中最为关键的技术便是Compare And Swap（简称CAS）。
关于synchronize的实现原理，请看移步这篇文章：美团一面：说说synchronized的实现原理？问麻了。。。。
关于synchronize的锁升级，请移步这篇文章：京东二面：Sychronized的锁升级过程是怎样的？
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方法。
  1. public class AtomicInteger extends Number implements java.io.Serializable {
  2.     private static final long serialVersionUID = 6214790243416807050L;
  4.     //由这里可以看出来，依赖jdk.internal.misc.Unsafe实现的
  5.     private static final jdk.internal.misc.Unsafe U = jdk.internal.misc.Unsafe.getUnsafe();
  6.     private static final long VALUE = U.objectFieldOffset(AtomicInteger.class, "value");
  8.     private volatile int value;
  10.         public final boolean compareAndSet(int expectedValue, int newValue) {
  11.             // 调用 jdk.internal.misc.Unsafe的compareAndSetInt方法
  12.             return U.compareAndSetInt(this, VALUE, expectedValue, newValue);  
  13.         }
  14. }
复制代码
Unsafe中的compareAndSetInt使用了@HotSpotIntrinsicCandidate注解修饰，@HotSpotIntrinsicCandidate注解是Java HotSpot虚拟机（JVM）的一个特性注解，它表明标注的方法有可能会被HotSpot JVM识别为“内联候选”，当JVM发现有方法被标记为内联候选时，会尝试使用底层硬件提供的原子指令（比如cmpxchg指令）直接替换掉原本的Java方法调用，从而在运行时获得更好的性能。
  1. public final class Unsafe {
  2.         @HotSpotIntrinsicCandidate  
  3.         public final native boolean compareAndSetInt(Object o, long offset,  
  4.                                                      int expected,  
  5.                                                      int x);
  6. }                                            
复制代码
compareAndSetInt这个方法我们可以从openjdk的hotspot源码（位置：hotspot/src/share/vm/prims/unsafe.cpp）中可以找到：
  1. {CC "compareAndSetObject",CC "(" OBJ "J" OBJ "" OBJ ")Z", FN_PTR(Unsafe_CompareAndSetObject)},
  3. {CC "compareAndSetInt", CC "(" OBJ "J""I""I"")Z", FN_PTR(Unsafe_CompareAndSetInt)},
  5. {CC "compareAndSetLong", CC "(" OBJ "J""J""J"")Z", FN_PTR(Unsafe_CompareAndSetLong)},
  7. {CC "compareAndExchangeObject", CC "(" OBJ "J" OBJ "" OBJ ")" OBJ, FN_PTR(Unsafe_CompareAndExchangeObject)},
  9. {CC "compareAndExchangeInt", CC "(" OBJ "J""I""I"")I", FN_PTR(Unsafe_CompareAndExchangeInt)},
  11. {CC "compareAndExchangeLong", CC "(" OBJ "J""J""J"")J", FN_PTR(Unsafe_CompareAndExchangeLong)},
复制代码
关于openjdk的源码，本文源码版本为1.9，如须要该版本源码或者其他版本下载方法，请关注本公众号【码农Academy】后，后台回复【openjdk】获取
而hostspot中的Unsafe_CompareAndSetInt函数会统一调用Atomic的cmpxchg函数：
  1. UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
  3. oop p = JNIHandles::resolve(obj);
  5. jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);
  6. // 统一调用Atomic的cmpxchg函数
  7. return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
  9. } UNSAFE_END
复制代码
而Atomic的cmpxchg函数源码(位置：hotspot/src/share/vm/runtime/atomic.hpp)如下：
  1. /**
  2. *这是按字节大小进行的`cmpxchg`操作的默认实现。它使用按整数大小进行的`cmpxchg`来模拟按字节大小进行的`cmpxchg`。不同的平台可以通过定义自己的内联定义以及定义`VM_HAS_SPECIALIZED_CMPXCHG_BYTE`来覆盖这个默认实现。这将导致使用特定于平台的实现而不是默认实现。
  3. *  exchange_value：要交换的新值。
  4. *  dest：指向目标字节的指针。
  5. *  compare_value：要比较的值。
  6. *  order：内存顺序。
  7. */
  8. inline jbyte Atomic::cmpxchg(jbyte exchange_value, volatile jbyte* dest,
  9.                              jbyte compare_value, cmpxchg_memory_order order) {
  10.   STATIC_ASSERT(sizeof(jbyte) == 1);
  11.   volatile jint* dest_int =
  12.       static_cast<volatile jint*>(align_ptr_down(dest, sizeof(jint)));
  13.   size_t offset = pointer_delta(dest, dest_int, 1);
  14.   // 获取当前整数大小的值，并将其转换为字节数组。
  15.   jint cur = *dest_int;
  16.   jbyte* cur_as_bytes = reinterpret_cast<jbyte*>(&cur);
  18.   // 设置当前整数中对应字节的值为compare_value。这确保了如果初始的整数值不是我们要找的值，那么第一次的cmpxchg操作会失败。
  19.   cur_as_bytes[offset] = compare_value;
  21.   // 在循环中，不断尝试更新目标字节的值。
  22.   do {
  23.     // new_val
  24.     jint new_value = cur;
  25.     // 复制当前整数值，并设置其中对应字节的值为exchange_value。
  26.     reinterpret_cast<jbyte*>(&new_value)[offset] = exchange_value;
  27.         // 尝试使用新的整数值替换目标整数。
  28.     jint res = cmpxchg(new_value, dest_int, cur, order);
  29.     if (res == cur) break; // 如果返回值与原始整数值相同，说明操作成功。
  31.     // 更新当前整数值为cmpxchg操作的结果。
  32.     cur = res;
  33.     // 如果目标字节的值仍然是我们之前设置的值，那么继续循环并再次尝试。
  34.   } while (cur_as_bytes[offset] == compare_value);
  35.   // 返回更新后的字节值
  36.   return cur_as_bytes[offset];
  37. }
复制代码
而由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包括：
这些方法都是基于CAS原理，可以或许在多线程环境下保证对变量的原子性修改，从而在不引入锁的情况下实现高效的并发控制。
CAS的优缺点与实用场景

CAS摒弃了传统的锁机制，制止了因获取和释放锁产生的上下文切换和线程阻塞，从而明显提升了系统的并发性能。并且由于CAS操作是基于硬件层面的原子性保证，所以它不会出现死锁问题，这对于复杂并发场景下的程序计划特别紧张。另外，CAS策略下线程在无法乐成更新变量时不须要挂起和唤醒，只需通过简单的循环重试即可。
但是，在高并发条件下，频仍的CAS操作可能导致大量的自旋重试，消耗大量的CPU资源。尤其是在竞争猛烈的场景中，线程可能耗费大量的时间在不断地尝试更新变量，而不是做有用的工作。这个由刚才cmpxchg函数可以看出。对于这个问题，我们可以参考synchronize中轻量级锁颠末自旋，凌驾肯定阈值后升级为重量级锁的原理，我们也可以给自旋设置一个次数，如果凌驾这个次数，就把线程挂起或者执行失败。(自顺应自旋)
另外，Java中的原子类也提供了办理办法，比如LongAdder以及DoubleAdder等，LongAdder过分散竞争点来淘汰自旋锁的辩论。它并没有像AtomicLong那样维护一个单一的共享变量，而是维护了一个Base值和一组Cell（桶）结构。每个Cell本质上也是一个可以举行原子操作的计数器，多个线程可以分别在一个独立的Cell上举行累加，只有在须要时才将各个Cell的值汇总到Base中。这样一来，大部分时间线程间的修改不再是集中在同一个变量上，从而低落了竞争强度，提高了并发性能。

而对于这个问题，着实也很好办理，我们给这个数据加上一个时间戳或者版本号（乐观锁概念）。即每次不仅比较值，还会比较版本。比如上述示例，初始时str的值的版本是1，然后线程2操作后值酿成B，而对应版本酿成了2，然后线程3操作后值酿成了A，版本酿成了3，而对于线程2来说，虽然值还是A，但是版本号变了，所以线程2依然会执行替换的操作。
Java的原子类就提供了类似的实现，如AtomicStampedReference和AtomicMarkableReference引入了附加的标记位或版本号，以便区分不同的修改序列。


总结

Java中的CAS原理及其在并发编程中的应用是一项非常紧张的技术。CAS使用CPU硬件提供的原子指令，实现了在无锁环境下的高效并发控制，制止了传统锁机制带来的上下文切换和线程阻塞开销。Java通过JNI接口调用底层的CAS指令，封装在jdk.internal.misc类和java.util.concurrent.atomic包下的原子类中，为我们提供了简洁易用的API来实现无锁编程。
CAS在带来并发性能提升的同时，也可能引发循环开销过大、ABA问题等问题。针对这些问题，Java提供了如LongAdder、AtomicStampedReference和AtomicMarkableReference等工具类来办理ABA问题，同时也通过自顺应自旋、适时放弃自旋转而进入阻塞等候等方式低落循环开销。
明白和熟练掌握CAS原理及其在Java中的应用，有助于我们在开发高性能并发程序时作出更明智的选择，既能提高系统并发性能，又能保证数据的正确性和同等性。
本文已收录于我的个人博客：码农Academy的博客，专注分享Java技术干货，包括Java基础、Spring Boot、Spring Cloud、Mysql、Redis、Elasticsearch、中心件、架构计划、口试题、程序员攻略等

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4