并发之CAS

1 问题引入

启动一千个线程,然后每个线程对余额进行-10操作,请问初始余额为1000,最后结果是多少?正确结果应该是0,但是在多线程环境下结果很难为0

interface Account {
     // 获取余额
     Integer getBalance();
     // 取款
     void withdraw(Integer amount);
     /**
     * 方法内会启动 1000 个线程，每个线程做 -10 元 的操作
     * 如果初始余额为 10000 那么正确的结果应当是 0
     */
     static void demo(Account account) {
     List<Thread> ts = new ArrayList<>();
     long start = System.nanoTime();
     for (int i = 0; i < 1000; i++) {
         ts.add(new Thread(() -> {
         account.withdraw(10);
         }));
     }
     ts.forEach(Thread::start);
     ts.forEach(t -> {
         try {
             t.join();
         } catch (InterruptedException e) {
             e.printStackTrace();
         }
     });
     
     long end = System.nanoTime();
     System.out.println(account.getBalance() 
     + " cost: " + (end-start)/1000_000 + " ms");
     }
}
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

class AccountUnsafe implements Account {
     private Integer balance;
    
     public AccountUnsafe(Integer balance) {
     this.balance = balance;
     }
    
     @Override
     public Integer getBalance() {
     return balance;
     }
    
     @Override
     public void withdraw(Integer amount) {
     balance -= amount;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

测试

public static void main(String[] args) {
 Account.demo(new AccountUnsafe(10000));
}
/*
运行结果:
130 cost: 287 ms 
*/
1
2
3
4
5
6
7

实际运行结果和预期值不符合.

分析原因withdraw方法执行不安全

public void withdraw(Integer amount) {
 balance -= amount;
}
1
2
3

对应字节码

ALOAD 0 // <- this
ALOAD 0
GETFIELD cn/cf/AccountUnsafe.balance : Ljava/lang/Integer; // <- this.balance
INVOKEVIRTUAL java/lang/Integer.intValue ()I // 拆箱
ALOAD 1 // <- amount
INVOKEVIRTUAL java/lang/Integer.intValue ()I // 拆箱
ISUB // 减法
INVOKESTATIC java/lang/Integer.valueOf (I)Ljava/lang/Integer; // 结果装箱
PUTFIELD cn/cf/AccountUnsafe.balance : Ljava/lang/Integer; // -> this.balance
1
2
3
4
5
6
7
8
9

多线程执行流程

ALOAD 0 // thread-0 <- this 
ALOAD 0 
GETFIELD cn/cf/AccountUnsafe.balance // thread-0 <- this.balance 
INVOKEVIRTUAL java/lang/Integer.intValue // thread-0 拆箱
ALOAD 1 // thread-0 <- amount 
INVOKEVIRTUAL java/lang/Integer.intValue // thread-0 拆箱
ISUB // thread-0 减法
INVOKESTATIC java/lang/Integer.valueOf // thread-0 结果装箱
PUTFIELD cn/cf/AccountUnsafe.balance // thread-0 -> this.balance 
 
 
ALOAD 0 // thread-1 <- this 
ALOAD 0 
GETFIELD cn/cf/AccountUnsafe.balance // thread-1 <- this.balance 
INVOKEVIRTUAL java/lang/Integer.intValue // thread-1 拆箱
ALOAD 1 // thread-1 <- amount 
INVOKEVIRTUAL java/lang/Integer.intValue // thread-1 拆箱
ISUB // thread-1 减法
INVOKESTATIC java/lang/Integer.valueOf // thread-1 结果装箱
PUTFIELD cn/cf/AccountUnsafe.balance // thread-1 -> this.balance 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2 解决方法

1 加锁

对Account 对象加锁.

class AccountUnsafe implements Account {
     private Integer balance;
     public AccountUnsafe(Integer balance) {
     this.balance = balance;
     }
    
     @Override
     public synchronized Integer getBalance() {
     return balance;
     }
    
     @Override
     public synchronized void withdraw(Integer amount) {
     balance -= amount;
     }
}
/*
运行结果:
0 cost: 300 ms 
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2 无锁之CAS

class AccountSafe implements Account {
     private AtomicInteger balance;
    
     public AccountSafe(Integer balance) {
     	this.balance = new AtomicInteger(balance);
     }
    
     @Override
     public Integer getBalance() {
         return balance.get();
     }
    
     @Override
     public void withdraw(Integer amount) {
         while (true) {
             int prev = balance.get();
             int next = prev - amount;
             if (balance.compareAndSet(prev, next)) {
             break;
             }
         }
         // 可以简化为下面的方法
         // balance.addAndGet(-1 * amount);
     }
}
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

测试

public static void main(String[] args) {
 Account.demo(new AccountSafe(10000));
}
/*
运行结果:
0 cost: 302 ms 
*/
1
2
3
4
5
6
7

AtomicInteger的解决方案, 内部没有使用锁来保护共享变量.

public void withdraw(Integer amount) {
     while(true) {
         // 需要不断尝试，直到成功为止
         while (true) {
         // 比如拿到了旧值 1000
         int prev = balance.get();
         // 在这个基础上 1000-10 = 990
         int next = prev - amount;
         /*
         compareAndSet 正是做这个检查，在 set 前，先比较 prev 与当前值
         - 不一致了，next 作废，返回 false 表示失败
         比如，别的线程已经做了减法，当前值已经被减成了 990
         那么本线程的这次 990 就作废了，进入 while 下次循环重试
         - 一致，以 next 设置为新值，返回 true 表示成功
         */
             if (balance.compareAndSet(prev, next)) {
                 break;
             }
         }
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

compareAndSet方法, 简称 CAS ，它必须是原子性操作.

CAS 的底层是 lock cmpxchg 指令（X86 架构），在单核 CPU 和多核 CPU 下都能够保证【比较-交 换】的原子性。

• 在多核状态下，某个核执行到带 lock 的指令时，CPU 会让总线锁住，当这个核把此指令执行完毕，再开启总线。这个过程中不会被线程的调度机制所打断，保证了多个线程对内存操作的准确性，是原子的。

另外,在CAS中还会用到volatile.

volatile修饰后,获取共享变量时，为了保证该变量的可见性.避免线程从自己的工作缓存中查找变量的值，必须到主存中获取它的值，线程操作 volatile 变量都是直接操作主存。即一个线程对 volatile 变量的修改，对另一个线程可见.

所以, CAS 必须借助 volatile 才能读取到共享变量的最新值来实现【比较并交换】的效果.

3 总结

1 无锁效率高

无锁情况下，即使重试失败，线程始终在高速运行，没有停歇，而 synchronized 会让线程在没有获得锁的时 候，发生上下文切换，进入阻塞. 但无锁情况下，因为线程要保持运行，需要额外 CPU 的支持, 但由于没有分到时间片，仍然会进入可运行状态，还是会导致上下文切换.

2 CAS特点

• CAS 是基于乐观锁的思想：最乐观的估计，不怕别的线程来修改共享变量，就算改了也没关系，再重试获取值
• synchronized 是基于悲观锁的思想：最悲观的估计，得防着其它线程来修改共享变量，我上了锁你们都别想改，我改完了解开锁，你们才有机会获取锁
• CAS 体现的是无锁并发、无阻塞并发
  • 因为没有使用 synchronized，所以线程不会陷入阻塞, 比较提升效率
  • 如果竞争激烈，频繁发生重试,反过来也会影响效率