CAS的实现原理

Love The Way You Lie 2022-02-27 16:42 298阅读 0赞

原子操作意为“不可被中断的一个或一系列操作”。

### 处理器实现原子操作 ###

**1、通过总线锁保证原子性**  
所谓总线锁就是使用处理器提供的一个`LOCK#`信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存。

**2、通过缓存锁定来保证原子性**  
所谓“缓存锁定”是指内存区域如果被缓存在处理器的缓存行中，并且在Lock操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不在总线上声言`LOCK#`信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据。

**但是两种情况下处理器不会使用缓存锁定**

*  当操作数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。
 *  处理器不支持，例如Intel 486和Pentium处理器

### Java中实现原子操作 ###

在Java中通过锁和循环CAS的方式来实现原子操作

#### CAS简介 ####

CAS的全称Compare And Swap，直译就是比较和交换，一种无锁原子算法。过程是这样：它包含3个参数CAS(V, E, N)，V表示要更新变量的值，E表示预期值，N表示新值。仅当V=E时，才会将V的值设为N，如果V值和E值不同，则当前线程什么都不做。简单来说，CAS 需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的。如果变量不是你想象的那样，则说明它已经被别人修改过了，你就需要重新读取（自旋），再次尝试修改就好了。

与锁相比，使用CAS会使程序看起来更加复杂一些，但由于其非阻塞的，它对死锁问题天生免疫，并且，线程间的相互影响也非常小。更为重要的是，使用无锁的方式完全没有锁竞争带来的系统开销，也没有线程间频繁调度带来的开销，因此，它要比基于锁的方式拥有更优越的性能

#### CAS底层原理 ####

CAS归功于硬件指令集的发展，硬件保证一个从语义上看起来需要多次操作的行为只通过一条处理器指令就能完成。这类指令常用的有：

*  测试并设置（Test and Set）
 *  获取并增加（Fetch and Increment）
 *  交换（Swap）
 *  比较并交换（Compare and Swap）
 *  加载链接/条件存储（Load Linked/Store Conditional）

`java.util.concurrent.atomic`包里的atomic类都是通过CAS来实现的，下面以AtomicInteger为例，来看下CAS的具体实现。  
![AtomicInteger][]  
比如说AtomicInteger中的`incrementAndGet()`方法，内部调用`compareAndSwapInt()`方法，而`compareAndSwapInt()`是本地native方法。  
![getAndAddInt][]  
更底层是利用处理器提供的CMPXCHG指令实现的，所以说CAS需要底层硬件的支持。

**代码示例：**

public class Counter {
        private static AtomicInteger atomicI = new AtomicInteger(0);
        private static int i = 0;
    
        public static void main(String[] args) {
            Thread[] threads = new Thread[100];
            for (int i = 0; i < 100; i++) {
                threads[i] = new Thread(() -> {
                    Counter.count();
                    Counter.safeCount();
                });
                threads[i].start();
            }
            System.out.println(Counter.i);
            System.out.println(Counter.atomicI.get());
        }
    
        private static void safeCount() {
            while (true) {
                int i = atomicI.get();
                boolean suc = atomicI.compareAndSet(i, ++i);
                if (suc) {
                    break;
                }
    
            }
        }
    
        // unsafe
        private static void count() {
            i++;
        }
    }

### CAS实现原子操作的三大问题 ###

**循环时间长开销大**  
自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销

**只能保证一个共享变量的原子操作**  
循环CAS只能保证一个共享变量的原子操作，当对多个共享变量操作时，就需要使用锁了，或者把多个共享变量合并成一个共享变量来操作。例如：AtomicReference类保证引用对象之间的原子性，可以把多个变量放在一个对象里来进行CAS操作。

**ABA问题**  
如果一个值原来是A，变成了B，又变成了A。那么根据CAS的算法过程，在对预期值进行检查时会发现没有改变，但实际上却变化了，这就是ABA问题。ABA问题的解决思是在变量前追加版本号，比如：A1-B2-A3。从JDK1.5开始，`java.util.concurrent.atomic`包中提供了AtomicStampedReference来解决ABA的问题，这个类的`compareAndSet()`方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

**下面我们来看个实例：**

public class ABADemo {
        private static AtomicStampedReference asr = new AtomicStampedReference(100, 1);
        public static void main(String[] args) throws InterruptedException {
    
            // 模拟ABA问题
            Thread th1 = new Thread(() -> {
                try {
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(asr.compareAndSet(100, 110, asr.getStamp(), asr.getStamp() + 1));
                System.out.println(asr.compareAndSet(110, 100, asr.getStamp(), asr.getStamp() + 1));
            });
            th1.start();
    
            // 先取出stamp，然后等ABA操作后去更新A的值
            Thread th2 = new Thread(() -> {
                int stamp = asr.getStamp();
                try {
                    TimeUnit.SECONDS.sleep(3);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(asr.compareAndSet(100, 120, stamp, stamp + 1));
            });
            th2.start();
        }
    }

**操作结果如下：**  
![操作结构][20190329164831618.png]  
可以发现ABA操作后，如果再使用原先的stamp去做更新，会导致更新失败。

**参考资料**  
Java并发编程的艺术 方腾飞 魏鹏 程晓明 著  
Java并发编程实战 童云兰 译

--------------------

\------------本文结束感谢您的阅读------------

[AtomicInteger]: /images/20220227/013c38c8d0604056b31d43ae5ea6a241.png
[getAndAddInt]: /images/20220227/e6e86170e8b6474cb62949b6d77145d8.png
[20190329164831618.png]: /images/20220227/8b5824230aca4533815231a06101d4c1.png