【并发编程】JAVA CAS（Conmpare And Swap）原理

悠悠 2023-10-06 12:12 47阅读 0赞

1. CAS简介

在计算机科学中，比较和交换（Conmpare And Swap）是用于实现多线程同步的原子指令。它将内存位置的内容与给定值进行比较，只有在相同的情况下，将该内存位置的内容修改为新的给定值。这是作为单个原子操作完成的。  
  原子性保证新值基于最新信息计算；如果该值在同一时间被另一个线程更新，则写入将失败。操作结果必须说明是否进行替换；这可以通过一个简单的布尔响应（这个变体通常称为比较和设置），或通过返回从内存位置读取的值来完成。  
  查看JUC（java.util.concurrent）下的atomic包：  
![format_png][]

2. CAS在Java中的应用

以AtomicInteger为例：

package java.util.concurrent.atomic;
    import java.util.function.IntUnaryOperator;
    import java.util.function.IntBinaryOperator;
    import sun.misc.Unsafe;
    
    /**
     * An {@code int} value that may be updated atomically.  See the
     * {@link java.util.concurrent.atomic} package specification for
     * description of the properties of atomic variables. An
     * {@code AtomicInteger} is used in applications such as atomically
     * incremented counters, and cannot be used as a replacement for an
     * {@link java.lang.Integer}. However, this class does extend
     * {@code Number} to allow uniform access by tools and utilities that
     * deal with numerically-based classes.
     *
     * @since 1.5
     * @author Doug Lea
    */
    public class AtomicInteger extends Number implements java.io.Serializable {
        private static final long serialVersionUID = 6214790243416807050L;
    
        // setup to use Unsafe.compareAndSwapInt for updates
        private static final Unsafe unsafe = Unsafe.getUnsafe();
        private static final long valueOffset;
    
        static {
            try {
                valueOffset = unsafe.objectFieldOffset
                    (AtomicInteger.class.getDeclaredField("value"));
            } catch (Exception ex) { throw new Error(ex); }
        }
    
        private volatile int value;
    
        /**
         * Creates a new AtomicInteger with the given initial value.
         *
         * @param initialValue the initial value
         */
        public AtomicInteger(int initialValue) {
            value = initialValue;
        }
    
        /**
         * Creates a new AtomicInteger with initial value {@code 0}.
         */
        public AtomicInteger() {
        }
    
        /**
         * Gets the current value.
         *
         * @return the current value
         */
        public final int get() {
            return value;
        }
    
        /**
         * Sets to the given value.
         *
         * @param newValue the new value
         */
        public final void set(int newValue) {
            value = newValue;
        }
    
        /**
         * Eventually sets to the given value.
         *
         * @param newValue the new value
         * @since 1.6
         */
        public final void lazySet(int newValue) {
            unsafe.putOrderedInt(this, valueOffset, newValue);
        }
    
        /**
         * Atomically sets to the given value and returns the old value.
         *
         * @param newValue the new value
         * @return the previous value
         */
        public final int getAndSet(int newValue) {
            return unsafe.getAndSetInt(this, valueOffset, newValue);
        }
    
        /**
         * Atomically sets the value to the given updated value
         * if the current value {@code ==} the expected value.
         *
         * @param expect the expected value
         * @param update the new value
         * @return {@code true} if successful. False return indicates that
         * the actual value was not equal to the expected value.
         */
        public final boolean compareAndSet(int expect, int update) {
            return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
        }
    
        /**
         * Atomically sets the value to the given updated value
         * if the current value {@code ==} the expected value.
         *
         * <p><a href="package-summary.html#weakCompareAndSet">May fail
         * spuriously and does not provide ordering guarantees</a>, so is
         * only rarely an appropriate alternative to {@code compareAndSet}.
         *
         * @param expect the expected value
         * @param update the new value
         * @return {@code true} if successful
         */
        public final boolean weakCompareAndSet(int expect, int update) {
            return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
        }
    
        /**
         * Atomically increments by one the current value.
         *
         * @return the previous value
         */
        public final int getAndIncrement() {
            return unsafe.getAndAddInt(this, valueOffset, 1);
        }
    
        /**
         * Atomically decrements by one the current value.
         *
         * @return the previous value
         */
        public final int getAndDecrement() {
            return unsafe.getAndAddInt(this, valueOffset, -1);
        }
    
        /**
         * Atomically adds the given value to the current value.
         *
         * @param delta the value to add
         * @return the previous value
         */
        public final int getAndAdd(int delta) {
            return unsafe.getAndAddInt(this, valueOffset, delta);
        }
    
        /**
         * Atomically increments by one the current value.
         *
         * @return the updated value
         */
        public final int incrementAndGet() {
            return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
        }
    
        /**
         * Atomically decrements by one the current value.
         *
         * @return the updated value
         */
        public final int decrementAndGet() {
            return unsafe.getAndAddInt(this, valueOffset, -1) - 1;
        }
    
        /**
         * Atomically adds the given value to the current value.
         *
         * @param delta the value to add
         * @return the updated value
         */
        public final int addAndGet(int delta) {
            return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
        }
    
        /**
         * Atomically updates the current value with the results of
         * applying the given function, returning the previous value. The
         * function should be side-effect-free, since it may be re-applied
         * when attempted updates fail due to contention among threads.
         *
         * @param updateFunction a side-effect-free function
         * @return the previous value
         * @since 1.8
         */
        public final int getAndUpdate(IntUnaryOperator updateFunction) {
            int prev, next;
            do {
                prev = get();
                next = updateFunction.applyAsInt(prev);
            } while (!compareAndSet(prev, next));
            return prev;
        }
    
        /**
         * Atomically updates the current value with the results of
         * applying the given function, returning the updated value. The
         * function should be side-effect-free, since it may be re-applied
         * when attempted updates fail due to contention among threads.
         *
         * @param updateFunction a side-effect-free function
         * @return the updated value
         * @since 1.8
         */
        public final int updateAndGet(IntUnaryOperator updateFunction) {
            int prev, next;
            do {
                prev = get();
                next = updateFunction.applyAsInt(prev);
            } while (!compareAndSet(prev, next));
            return next;
        }
    
        /**
         * Atomically updates the current value with the results of
         * applying the given function to the current and given values,
         * returning the previous value. The function should be
         * side-effect-free, since it may be re-applied when attempted
         * updates fail due to contention among threads.  The function
         * is applied with the current value as its first argument,
         * and the given update as the second argument.
         *
         * @param x the update value
         * @param accumulatorFunction a side-effect-free function of two arguments
         * @return the previous value
         * @since 1.8
         */
        public final int getAndAccumulate(int x,
                                          IntBinaryOperator accumulatorFunction) {
            int prev, next;
            do {
                prev = get();
                next = accumulatorFunction.applyAsInt(prev, x);
            } while (!compareAndSet(prev, next));
            return prev;
        }
    
        /**
         * Atomically updates the current value with the results of
         * applying the given function to the current and given values,
         * returning the updated value. The function should be
         * side-effect-free, since it may be re-applied when attempted
         * updates fail due to contention among threads.  The function
         * is applied with the current value as its first argument,
         * and the given update as the second argument.
         *
         * @param x the update value
         * @param accumulatorFunction a side-effect-free function of two arguments
         * @return the updated value
         * @since 1.8
         */
        public final int accumulateAndGet(int x,
                                          IntBinaryOperator accumulatorFunction) {
            int prev, next;
            do {
                prev = get();
                next = accumulatorFunction.applyAsInt(prev, x);
            } while (!compareAndSet(prev, next));
            return next;
        }
    
        //......
    
    }

可以看出自JDK1.5就开始引入CAS来解决多线程中的并发问题。  
  查看方法源码，可以看出所有的CAS操作都是通过sun.misc包下`Unsafe`类实现的。而sun.misc包存在于JDK的rt.jar包，是由JVM本地实现。  
  `Unsafe`是CAS的核心类。由于Java无法直接访问底层系统，则需要通过本地（native）来访问。`Unsafe`可以直接操作特定内存的数，其内部方法可以像C语言的指针一样直接操作内存。  
  注意：`Unsafe`类的所有方法都是native修饰的，即`Unsafe`类的所有方法都可以直接调用底层操作系统资源。

3. CAS在JUC中的应用

以重入锁`ReentrantLock`为例。通过查看部分源码：

public class ReentrantLock implements Lock, java.io.Serializable {
        private static final long serialVersionUID = 7373984872572414699L;
        /** Synchronizer providing all implementation mechanics */
        private final Sync sync;
    
        /**
         * Base of synchronization control for this lock. Subclassed
         * into fair and nonfair versions below. Uses AQS state to
         * represent the number of holds on the lock.
         */
        abstract static class Sync extends AbstractQueuedSynchronizer {
            private static final long serialVersionUID = -5179523762034025860L;
    
            /**
             * Performs {@link Lock#lock}. The main reason for subclassing
             * is to allow fast path for nonfair version.
             */
            abstract void lock();
    
            /**
             * Performs non-fair tryLock.  tryAcquire is implemented in
             * subclasses, but both need nonfair try for trylock method.
             */
            final boolean nonfairTryAcquire(int acquires) {
                final Thread current = Thread.currentThread();
                int c = getState();
                if (c == 0) {
                    if (compareAndSetState(0, acquires)) {
                        setExclusiveOwnerThread(current);
                        return true;
                    }
                }
                else if (current == getExclusiveOwnerThread()) {
                    int nextc = c + acquires;
                    if (nextc < 0) // overflow
                        throw new Error("Maximum lock count exceeded");
                    setState(nextc);
                    return true;
                }
                return false;
            }
            //......
        }
        //......
    }

可以看出，内部抽象类`Sync`继承自`AbstractQueuedSynchronizer`类。`AbstractQueuedSynchronizer`作为Java多种锁的父类，有很多地方通过CAS操作来提高并发效率。查看`AbstractQueuedSynchronizer`部分源码：

/**
     * Inserts node into queue, initializing if necessary. See picture above.
     * @param node the node to insert
     * @return node's predecessor
     */
    private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // Must initialize
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }

可以看出在上述的同步队列的入队操作时，在多线程环境下，对其头尾节点的操作都有可能失败，失败后通过自旋操作再次尝试，直到成功，这也是一种乐观锁的实现。

4. CAS缺点

*  循环时间长，CPU开销大
 *  只能保证一个共享变量的原子操作
 *  引出ABA问题

5. ABA问题

比如说一个线程1从内存位置V中取出A，另一个线程2也从内存中取出A，线程2将A变成了B，然后将V位置的数据变成A，这时候线程1进行CAS操作发现内存中仍然是A，那么线程1操作成功。尽管线程1的CAS操作成功，但是不代表这个过程就是没有问题的。  
  如果链表的头在变化了两次后恢复了原值，但是不代表链表就没有变化。  
  所以JAVA中提供了`AtomicStampedReference`或`AtomicMarkableReference`来处理ABA问题，主要是在对象中额外再增加一个标记来标识对象是否有过变更。

[format_png]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcyMDIwLmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDIwMDcvMTExOTA5Ny0yMDIwMDcwMTE0MzIyNjYzMS00NjIxMjQ4MTgucG5n?x-oss-process=image/format,png