【面试题】CAS

1. CAS Demo

atomicInteger.compareAndSet(期望值, 修改值)

public class CASDemo {
    public static void main(String[] args) {
        //主内存值为5
        AtomicInteger atomicInteger = new AtomicInteger(5);

        //atomicInteger.compareAndSet(期望值, 修改值)

        //线程AAA把主内存的值5拷贝到工作内存，操作的时候，期望值是5，修改值为2022，赋值成功
        new Thread(() -> {
            boolean updateResult1 = atomicInteger.compareAndSet(5, 2022);
            System.out.println("修改结果:" + updateResult1 + "当前值:" + atomicInteger.get());
        },"AAA").start();

        //线程BBB把主内存的值5拷贝到工作内存，操作的时候期望值是5，由于线程AAA先执行，已经将主内存的值改为2022，这时候期望值5和主内存的值2022冲突，赋值失败
        new Thread(() -> {
            //保证线程AAA先执行
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean updateResult2 = atomicInteger.compareAndSet(5, 2019);
            System.out.println("修改结果:" + updateResult2 + "当前值:" + atomicInteger.get());
        },"BBB").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

2. CAS底层原理

在测试volatile原子性的的时候，我们用到了 AtomicInteger.getAndIncrement();，我们点击这个方法进去看看底层实现。

AtomicInteger atomicInteger = new AtomicInteger(3);
atomicInteger.getAndIncrement();
1
2

假设线程A和线程B同时调用getAndIncrement()方法，
AtomicInteger里面的原始值是3，这时候主内存atomicInteger的值为3，线程A和线程B在各自的工作内存持有atomicInteger的副本值为3；
此时线程A通过调用getIntVolatile(var1,var2)拿到var5=3（这时候主内存的值），这时候线程A被挂起；
此时线程B通过调用getIntVolatile(var1,var2)拿到var5=3（这时候主内存的值），继续判断this.compareAndSwapInt(var1,var2,var5,var5+var4)，这时候主内存中的值刚好和预期的值3一致，这时候将var5(3)+1 return，这时候返回4，线程B执行完成。
线程A恢复，继续执行判断this.compareAndSwapInt(var1,var2,var5,var5+var4)发现和预期值为3不一致，则重新读取主线程中的值为4（由于变量用volatile修饰，所以线程A可以读到线程中最新的值）为新的预期值，var5=4被写入成功。

总的来说，就是通过Usafe类+CAS自旋来完成。

2.1 CAS（compareAndSwap）

比较工作内存中的值和主内存中值是否一致，如果一致，则执行操作，如果不一致，则继续比较，直到工作内存和主内存中的数据一致为止。

3. 缺点

循环时间长，开销大。
ABA问题。

3.1 ABA问题

CAS算法实现一个重要前提是需取出内存中某个时刻的并在当下比较替换，那么中间这个时间差就会导致数据发生变化。
比如线程1从主内存中位置V中拿出A，这时候线程2也从主内存中位置V中拿出A，并将A改为B，又改成A，这时候线程1进行CAS操作发现内存中的值为A，线程1操作成功。

3.2 ABA问题解决

使用AtomicStampedReference，引入版本号。

public class CASDemo3 {
    public static void main(String[] args) {

        AtomicStampedReference<Integer> integerAtomicStampedReference = new AtomicStampedReference<Integer>(100, 1);


        new Thread(() -> {
            int stampInit = integerAtomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName()+",stamp:" +stampInit);
            //保证线程B可以拿到最初始的版本号
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            //完成一次ABA
            //100  ->  101  stamp:2
            boolean update1 = integerAtomicStampedReference.compareAndSet(100, 101, stampInit, stampInit + 1);
            System.out.println(Thread.currentThread().getName()+",100->101:"+update1+",stamp:" + integerAtomicStampedReference.getStamp());
            //101  ->  100  stamp:3
            boolean update2 = integerAtomicStampedReference.compareAndSet(101, 100, integerAtomicStampedReference.getStamp(), integerAtomicStampedReference.getStamp() + 1);
            System.out.println(Thread.currentThread().getName()+",101->100:"+update2+",stamp:"  + integerAtomicStampedReference.getStamp());
        }, "A").start();

        new Thread(() -> {
            int stampInit = integerAtomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName()+",stamp:" +stampInit);
            //保证线程A ABA可以执行完成
            try {
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean update1 = integerAtomicStampedReference.compareAndSet(100, 101, stampInit, stampInit + 1);
             System.out.println(Thread.currentThread().getName()+",100->101:"+update1+",value:"+integerAtomicStampedReference.getReference()+",stamp:" + integerAtomicStampedReference.getStamp());


        }, "B").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

4.原子引用

class User {
    private String username;
    private int age;

    public User(String username, int age) {
        this.username = username;
        this.age = age;
    }

    public String getUsername() {
        return username;
    }

    public void setUsername(String username) {
        this.username = username;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "User{" +
                "username='" + username + '\'' +
                ", age=" + age +
                '}';
    }
}

public class CASDemo2 {
    public static void main(String[] args) {
        User zhang3 = new User("zhang3", 22);
        User li4 = new User("li4", 25);

        AtomicReference<User> userAtomicReference = new AtomicReference<>();
        userAtomicReference.set(zhang3);

        boolean update1 = userAtomicReference.compareAndSet(zhang3, li4);
        System.out.println("update1:" + update1 + ",userAtomicReference.get:" + userAtomicReference.get());

        boolean update2 = userAtomicReference.compareAndSet(zhang3, li4);
        System.out.println("update2:" + update2 + ",userAtomicReference.get:" + userAtomicReference.get());

    }
}
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
47
48
49
50