CAS(Compare and swap)比较并交换算法解析

CAS说明

CAS全称是Compare and swap。字面翻译的意思就是比较并交换。

CAS可以用来实现乐观锁，CAS中没有线程的上下文切换，减少了不必要的开销

说明：本文解析的JDK源码为open JDK 11版本。

CAS原理

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。（在 CAS 的一些特殊情况下将仅返回 CAS 是否成功，而不提取当前值。）CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则，不要更改该位置，只告诉我这个位置的值即可。”

通常将 CAS 用于同步的方式是从地址 V 读取值 A，执行多步计算来获得新值 B，然后使用 CAS 将 V 的值从 A 改为 B。如果 V 处的值尚未同时更改，则 CAS 操作成功。

JAVA实现

我们从源码中看下Java实现的 方式。

Java的cas实现代码如下：

public final class Unsafe {
 
    ...
 
    @ForceInline
    public final boolean compareAndSwapObject(Object o, long offset,
                                              Object expected,
                                              Object x) {
        return theInternalUnsafe.compareAndSetObject(o, offset, expected, x);
    }
 
    /**
     * Atomically updates Java variable to {@code x} if it is currently
     * holding {@code expected}.
     *
     * 
This operation has memory semantics of a {@code volatile} read
     * and write.  Corresponds to C11 atomic_compare_exchange_strong.
     *
     * @return {@code true} if successful
     */
    @ForceInline
    public final boolean compareAndSwapInt(Object o, long offset,
                                           int expected,
                                           int x) {
        return theInternalUnsafe.compareAndSetInt(o, offset, expected, x);
    }
 
    /**
     * Atomically updates Java variable to {@code x} if it is currently
     * holding {@code expected}.
     *
     * 
This operation has memory semantics of a {@code volatile} read
     * and write.  Corresponds to C11 atomic_compare_exchange_strong.
     *
     * @return {@code true} if successful
     */
    @ForceInline
    public final boolean compareAndSwapLong(Object o, long offset,
                                            long expected,
                                            long x) {
        return theInternalUnsafe.compareAndSetLong(o, offset, expected, x);
    }
 
    ...
}

我们可以看到，在JAVA源码中，将compareAndSwap使用了compareAndSwapObject、compareAndSwapInt、compareAndSwapLong等几个方法进行了对应的包装操作。这里对所有的方法使用了@ForceInline注解，说明这里没有使用标准的实现，而是强制使用了HotSpot VM 的优化实现方法。

@ForceInline注解源码

可跳过该小节....

/**
 * A method or constructor may be annotated as "force inline" if the standard
 * inlining metrics are to be ignored when the HotSpot VM inlines the method
 * or constructor.
 * 
 * This annotation must be used sparingly.  It is useful when the only
 * reasonable alternative is to bind the name of a specific method or
 * constructor into the HotSpot VM for special handling by the inlining policy.
 * This annotation must not be relied on as an alternative to avoid tuning the
 * VM's inlining policy.  In a few cases, it may act as a temporary workaround
 * until the profiling and inlining performed by the HotSpot VM is sufficiently
 * improved.
 *
 * @implNote
 * This annotation only takes effect for methods or constructors of classes
 * loaded by the boot loader.  Annotations on methods or constructors of classes
 * loaded outside of the boot loader are ignored.
 */
@Target({ElementType.METHOD, ElementType.CONSTRUCTOR})
@Retention(RetentionPolicy.RUNTIME)
public @interface ForceInline {
}

上面@ForceInline的注释的大意是如下：

        假设不需要使用标准指令排列处理时，HotSpot VM的方法或构造器可以使用此注解，让其强制排列。

        这个注解使用的话要谨慎，它唯一合理的用法是用来将其绑定到HotSpot VM的指定的方法或构造器中，用来提供一种排列策略。不能依赖该注解去避免VM的正常指令排列策略，在HotSpot VM中的少数情况下，它只能作为临时的应对方法，直到指令排列情况改善。

这个注解仅对通过boot loader加载的类中的方法和构造器有影响，其他的均会被忽略。

简单来讲，这个注解是用来做自定义指令排列的，它可以在一定程度上避免重排，但是不能作为调整指令排列的核心，只能作为一种替代方案。

compareAndSetXXX相关实现

public final class Unsafe {
 
    ...
 
    /**
     * Atomically updates Java variable to {@code x} if it is currently
     * holding {@code expected}.
     *
     * 
This operation has memory semantics of a {@code volatile} read
     * and write.  Corresponds to C11 atomic_compare_exchange_strong.
     *
     * @return {@code true} if successful
     */
    @HotSpotIntrinsicCandidate
    public final native boolean compareAndSetObject(Object o, long offset,
                                                    Object expected,
                                                    Object x);
    ...
 
    @HotSpotIntrinsicCandidate
    public final native boolean compareAndSetInt(Object o, long offset,
                                                 int expected,
                                                 Object x);
    ...
 
    @HotSpotIntrinsicCandidate
    public final native boolean compareAndSetLong(Object o, long offset,
                                                  long expected,
                                                  long x);
    ...
}

上面的这些方法简单的来讲就是如果当前Java的变量是expected值，就自动更新值为x。对应的是C语言11的atomic_compare_exchange_strong标准函数。根据@@HotSpotIntrinsicCandidate注解，我们知道这个实现是HotSpot VM实现的。

@HotSpotIntrinsicCandidate注解

扩展知识，可以略过。

我们知道JDK是统一的代码，不同的JVM的效率会有不同。不同的公司、组织会根据自己的情况，推出不同的JVM。所以这块的优化都会落到VM的肩膀上。每个虚拟机都会使用C或C++对其进行优化或者实现。

HotSpotIntrinsicCandidate是JDK9引入的。@HotSpotIntrinsicCandidate注解可以理解为HotSpot的VM的单独实现（解决）方案，理论上这个实现方式会比JDK的统一的实现方式要高效（这个很自然，你做的效能都比不上官方通用的，那这个解决方案有毛用？）。

HotSpotIntrinsicCandidate源码

/**
 * The {@code @HotSpotIntrinsicCandidate} annotation is specific to the
 * HotSpot Virtual Machine. It indicates that an annotated method
 * may be (but is not guaranteed to be) intrinsified by the HotSpot VM. A method
 * is intrinsified if the HotSpot VM replaces the annotated method with hand-written
 * assembly and/or hand-written compiler IR -- a compiler intrinsic -- to improve
 * performance. The {@code @HotSpotIntrinsicCandidate} annotation is internal to the
 * Java libraries and is therefore not supposed to have any relevance for application
 * code.
 *
 * Maintainers of the Java libraries must consider the following when
 * modifying methods annotated with {@code @HotSpotIntrinsicCandidate}.
 *
 * 
 * 
When modifying a method annotated with {@code @HotSpotIntrinsicCandidate},