Concurrent CAS

1 问题引入

Start a thousand threads,Then each thread does it on the balance-10操作,What is the initial balance please1000,What is the final result?正确结果应该是0,But in a multi-threaded environment the results are very difficult0

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");
     }
}

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;
     }
}

测试

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

The actual running result does not match the expected value.

分析原因withdrawThe method is not safe to execute

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

对应字节码

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

多线程执行流程

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 

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 */

2 no lockCAS

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);
     }
}

测试

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

AtomicInteger的解决方案, No locks are used internally to protect shared variables.

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;
             }
         }
     }
}

compareAndSet方法, 简称 CAS ,It must be an atomic operation.

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

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

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

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

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

3 总结

1 无锁效率高

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

2 CAS特点

• CAS 是基于乐观锁的思想：最乐观的估计,不怕别的线程来修改共享变量,就算改了也没关系,Try again to get the value
• synchronized 是基于悲观锁的思想：最悲观的估计,得防着其它线程来修改共享变量,我上了锁你们都别想改,我改完了解开锁,You have the opportunity to acquire the lock
• CAS 体现的是无锁并发、无阻塞并发
  • 因为没有使用 synchronized,所以线程不会陷入阻塞, Compare efficiency
  • 如果竞争激烈,Retries occur frequently,This in turn affects efficiency