CAS解决原子性问题的另一种方案

CAS是什么

CAS（compare and swap）比较并交换。给定一个预期值和一个新值，首先比较内存中的值与预期值是否相等（比较），如果相等则将内存中的值改为新值（交换）。否则，说明在此期间有其他线程修改了值，则修改失败。通常CAS伴随自旋，即失败后重新从主内存中读取最新的值最为预期值，再次尝试修改。CAS的伪代码如下：

for(;;){
   expect = readFromMemory();      // 从内存中读取最新的值作为预期值
   newValue = expect + 1;
   if(expect == newFromMemory()){ //如果相等说明再次期间没有其他线程修改过值
      write(newValue);            //将最新值写回内存中
   }
}
1
2
3
4
5
6
7

CAS解决原子性问题

首先我们来看一个熟悉的例子，下面的代码会创建多个线程同时修改共享变量count，很明显，这将会有原子性问题，count最终的结果将会不确定。

public class AtomicTest {
    static int count = 0;
     public static void main(String[] args) throws InterruptedException {
        CountDownLatch countDownLatch = new CountDownLatch(100);

        for (int i = 0; i < 100; i++) {
            new Thread(() -> {
                for (int j = 0; j < 100; j++) {
                    count++;
                }
                countDownLatch.countDown();
            }).start();
        }

        countDownLatch.await();
        System.out.println(count);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

下面利用CAS的思想，自己实现一个支持原子自增的原子类：

public class UnsafeFactory {
    /**
     * 获取 Unsafe 对象
     * @return
     */
    public static Unsafe getUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }
}

public class MyAtomicInteger {
    private Unsafe unsafe;

    private volatile int value;

    public long offset;

    public MyAtomicInteger() {
        unsafe = UnsafeFactory.getUnsafe();
        try {
            // 偏移量
            offset = unsafe.objectFieldOffset(MyAtomicInteger.class.getDeclaredField("value"));
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
        }
    }
    
    public void increment() {
        int expect;
        do {
            // 根据偏移量从内存中获取最新的值
            expect = unsafe.getIntVolatile(this, offset);
        } while (!unsafe.compareAndSwapInt(this, offset, expect, expect + 1));
    }

    public int get() {
        return value;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

1. 首先我们定义了一个UnsafeFactory，这个类是用来获取Unsafe对象的。因为Unsafe的构造方法做了限制，只能由启动类加载器才能够创建，因此我们只能通过反射强行拿到Unafe对象
2. 在MyAtomicInteger类中有三个成员变量
   a. unsafe
   b. value：相当于count
   c. offset：value的偏移量，Unsafe提供了一个方法，通过偏移量可以直接从内存中获取对应字段的值
3. increment：实现了比较并交换的逻辑，compareAndSwapInt包含了比较和交换俩个逻辑，由硬件层面保证原子性。如果内存中的指与预期值相等，就会返回true，跳出循环。否则不断自旋尝试

JDK自带的原子类

其实我们上面写的MyAtomicInteger类，JDK已经帮我们实现了，我们只需要拿过来用就行了。此外JDK还提供了许多其他的原子类

基本类型： AtomicInteger、AtomicLong、AtomicBoolean；
引用类型： AtomicReference、AtomicStampedRerence、AtomicMarkableReference；
数组类型： AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray

这些原子类的使用方式的都很简单，且实现原理与我们上面的MyAtomicInteger大差不差，在此就不再赘述了。

实现一把CAS锁

使用CAS实现锁，可以避免线程进入阻塞，带来额外的系统调用开销，在某种程度上，性能会比synchronied、Lock这类可能会阻塞线程的锁性能更高。当然，如果临界区（指同一时刻只能有一个线程执行）的代码如果业务逻辑比较复杂，执行时间较长，并发较高，那么可能不适用使用CAS锁，因为这会造成大量的线程自旋等待，给CPU造成巨大的负担。

CAS锁实现也很简单，我们可以利用CAS去修改某个变量，修改成功的线程就等于获取到锁了，而其他线程则自旋等待，直到获取锁的线程释放了锁。

public class CasLock {

    private AtomicReference<Thread> atomicReference = new AtomicReference<>();

    public void lock() {
        Thread currentThread = Thread.currentThread();
        for (;;) {
            if (atomicReference.compareAndSet(null, currentThread)) {
                break;
            }
        }
    }

    public void unlock() {
        Thread currentThread = Thread.currentThread();
        atomicReference.compareAndSet(currentThread, null);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

ABA问题

所谓的ABA问题指的是某个线程将值改成B，然后又改为A。举个形象的例子，你往银行卡里存了100万后，有人把你银行卡里的钱全都转走了，然后又转回来了，此时你再去查余额，发现还是100万，但你能说在次期间你银行卡的钱没被别人动过吗？很明显是不能的，当然如果你只是关心银行卡中的余额是否正确，那么你就不需要关心ABA问题，但如果你关心是否有其他人动作你的卡，那么你就需要关心ABA问题了。

如何解决ABA问题

解决ABA问题的方式也很简单，就是加入一个版本号，每次更新后版本号+1，这样我们就可以通过对比版本号知道期间有没有被修改过了。JDK也提供了一个带版本号的原子类AtomicStampedReference

/**
* expectedReference: 预期值
* newReference: 新值
* expectedStamp: 预期版本号
* newStamp: 最新版本号
*/
public boolean compareAndSet(V expectedReference,V newReference,int expectedStamp,int newStamp) 

1
2
3
4
5
6
7
8

如在下面的代码中，我会启动俩个线程，线程1读取内存中的值和版本号后，会阻塞一秒。在这一秒期间，线程2会将值从1修改为2，再改回1。一秒后线程1被唤醒，通过比较版本号会发现期间数据被动过，从而修改失败

public class AtomicStampedReferenceTest {
    public static void main(String[] args) {
        // 定义AtomicStampedReference    Pair.reference值为1, Pair.stamp为1
        AtomicStampedReference atomicStampedReference = new AtomicStampedReference<>(1, 1);

        new Thread(() -> {
            int[] stampHolder = new int[1];
            int value = (int) atomicStampedReference.get(stampHolder);
            int stamp = stampHolder[0];
            System.out.println("Thread1 read value: " + value + ", stamp: " + stamp);
            // 阻塞1s
            LockSupport.parkNanos(1000000000L);
            // Thread1通过CAS修改value值为3
            if (atomicStampedReference.compareAndSet(value, 3, stamp, stamp + 1)) {
                System.out.println("Thread1 update from " + value + " to 3");
            } else {
                System.out.println("Thread1 update fail!");
            }
        }, "Thread1").start();

        new Thread(() -> {
            int[] stampHolder = new int[1];
            int value = (int) atomicStampedReference.get(stampHolder);
            int stamp = stampHolder[0];
            System.out.println("Thread2 read value: " + value + ", stamp: " + stamp);
            // Thread2通过CAS修改value值为2
            if (atomicStampedReference.compareAndSet(value, 2, stamp, stamp + 1)) {
                System.out.println("Thread2 update from " + value + " to 2");

                // do something

                value = (int) atomicStampedReference.get(stampHolder);
                stamp = stampHolder[0];
                System.out.println("Thread2 read value: " + value + ", stamp: " + stamp);
                // Thread2通过CAS修改value值为1
                if (atomicStampedReference.compareAndSet(value, 1, stamp, stamp + 1)) {
                    System.out.println("Thread2 update from " + value + " to 1");
                }
            }
        }, "Thread2").start();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

最后总结一下CAS的缺点：
• CAS自旋长时间不成功，会给CPU带来较大的压力
• 只能保证一个变量的原子操作