CAS

是什么

CAS--Compare And Swap,比较并交换,是一种无锁算法.算法大概的思路是先从内存中取出内存值V作为预期值A,要修改的新值为B,若预期值A与V相等,则把B的值更新到内存;否则,证明其他线程修改过V,再重试,直到修改成功为止.

比较的目的是判断有无其他线程改动过V,如果V不是原来的V,证明有其他线程修改过,那么就要把上述过程重新再来一次,否则会发生写覆盖

CAS的优势及原理

CAS其实采取的是乐观策略,类似于乐观锁,它最大的优势是无锁,不会阻塞,效率自然翻倍提高.

那是怎么做到不加锁也能保证数据的一致性呢?

我们先看看CAS最常见的应用场景,jdk的原子类AtomicInteger,我们来看看它的getAndIncrement方法

    /**
     * Atomically increments by one the current value.
     *
     * @return the previous value
     */
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

我们发现是调用了Unsafe类的getAndAddInt方法

  public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);//先从主存取出预期值
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//循环直到预期值和当前内存值相等为止,然后更新内存值,此操作称为自旋
        return var5;
  }

我们发现,比较并交换的核心方法是compareAndSwapInt

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

点进去却发现是native方法,这个方法是利用CPU原语实现的,在硬件级别保证了原子性,所以这个方法是CAS无锁的关键所在

CAS缺点

但,CAS并不是完美的

第一,CAS在进行自旋操作时(若V被频繁改动,则该线程会一直循环直到修改成功),消耗的CPU资源极大

ABA问题

第二,会出现ABA问题

假设线程1从主存取得的值为V,然后挂起,其他线程把V修改为V'再修改回V,这时线程1比较时,发现主存的值仍然为V,认为V值没有被改过,所以执行更新,但是V其实被修改了两次了,只不过第二次又修改回原来的V

那应该如何解决ABA问题,jdk中有一个原子类叫AtomicStampedReference就是用来解决这个问题的,AtomicStampedReference加入了stamp概念,每做一次修改stamp的值改变一次,且每次修改的stamp不相同

import java.util.concurrent.atomic.AtomicStampedReference;
/**
 * @author dugm
 * @description
 * @date 2019-08-10 12:37
 */
public class ABATester {
    public static void main(String[] args) {
        int v = 1;
        int initStamp = 0;
        AtomicStampedReference<Integer> i = new AtomicStampedReference<>(v, initStamp);

        //获取v值和初始版本号
        Integer expectedReference = i.getReference();
        int expectedStamp = i.getStamp();

        //开启线程T对V值修改两次
        new Thread(() -> {
            Integer expectedReference1 = i.getReference();
            int newReference1 = expectedReference1 + 1;
            int expectedStamp1 = i.getStamp();
            int newStamp1 = expectedStamp1 + 1;
            boolean result1 = i.compareAndSet(expectedReference1, newReference1, expectedStamp1, newStamp1);
            System.out.println(
                    "线程" + Thread.currentThread().getName() + "第一次修改" + result1 + ",结果为" + i.getReference() + ",版本号为"
                            + i.getStamp());

            Integer expectedReference2 = i.getReference();
            int expectedStamp2 = i.getStamp();
            int newStamp2 = expectedStamp2 + 1;
            boolean result2 = i.compareAndSet(expectedReference2, 1, expectedStamp2, newStamp2);
            System.out.println(
                    "线程" + Thread.currentThread().getName() + "第二次修改" + result2 + ",结果为" + i.getReference() + ",版本号为"
                            + i.getStamp());
        }, "T").start();

        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {}

        int newReference = expectedReference + 1;
        int newStamp = expectedStamp + 1;
        boolean result = i.compareAndSet(expectedReference, newReference, expectedStamp, newStamp);

        System.out.println(
                "线程" + Thread.currentThread().getName() + "修改" + result + ",结果为" + i.getReference() + ",版本号为" + i
                        .getStamp());
    }
}