CAS NO lock

Ask questions

There are the following requirements , Guarantee account.withdraw Thread safety of withdrawal method

import java.util.ArrayList;
import java.util.List;
interface Account {
    
 //  Get the balance 
 Integer getBalance();
 //  Withdraw money 
 void withdraw(Integer amount);
 /** *  Method will start  1000  Threads , Each thread does  -10  element   The operation of  *  If the initial balance is  10000  Then the correct result should be  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");
 }
}

The original implementation is not thread safe

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;
 }
}
``
 Execute test code 

```java
public static void main(String[] args) {
    
 Account.demo(new AccountUnsafe(10000));
}

The result of a certain execution

330 cost: 306 ms

Solutions - lock
The first thought is to Account Object locking

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

The result is

0 cost: 399 ms

Solutions - unlocked

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;
 }
 }
 //  It can be simplified to the following method 
 // balance.addAndGet(-1 * amount);
 }
}

Execute test code

public static void main(String[] args) {
    
 Account.demo(new AccountSafe(10000));
}

The result of a certain execution

0 cost: 302 ms

CAS And volatile

What I saw in front AtomicInteger Solutions for , There is no internal lock to protect thread safety of shared variables . So how does it come true ？

public void withdraw(Integer amount) {
    
 while(true) {
    
 //  Need to keep trying , Until we succeed 
 while (true) {
    
 //  Like getting the old value  1000
 int prev = balance.get();
 //  On this basis  1000-10 = 990
 int next = prev - amount;
 /* compareAndSet  That's what I did , stay  set  front , Compare first  prev  With the current value  -  It's not the same ,next  To void , return  false  It means failure   such as , Other threads have subtracted , The current value has been reduced to  990  So this time of this thread  990  It's invalid , Get into  while  Try again next time  -  Agreement , With  next  Set to new value , return  true  It means success  */
 if (balance.compareAndSet(prev, next)) {
    
 break;
 }
 }
 }
}

The key is compareAndSet, Its short name is CAS （ Also have Compare And Swap That's what I'm saying ）, It has to be atomic operation .

Be careful
Actually CAS The bottom is lock cmpxchg Instructions （X86 framework ）, In a single core CPU And multicore CPU It can be guaranteed in all cases 【 Compare - In exchange for 】 The atomicity of

In a multicore state , A certain core performs to bring lock When instructed by ,CPU It locks the bus , When the core has finished executing this instruction , Turn on the bus again . This process will not be interrupted by the thread scheduling mechanism , Ensure the accuracy of memory operation by multiple threads , It's atomic. .

Slow motion analysis

@Slf4j
public class SlowMotion {
    
 public static void main(String[] args) {
    
 AtomicInteger balance = new AtomicInteger(10000);
 int mainPrev = balance.get();
 log.debug("try get {}", mainPrev);
 new Thread(() -> {
    
 sleep(1000);
 int prev = balance.get();
 balance.compareAndSet(prev, 9000);
 log.debug(balance.toString());
 }, "t1").start();
 sleep(2000);
 log.debug("try set 8000...");
 boolean isSuccess = balance.compareAndSet(mainPrev, 8000);
 log.debug("is success ? {}", isSuccess);
 if(!isSuccess){
    
 mainPrev = balance.get();
 log.debug("try set 8000...");
 isSuccess = balance.compareAndSet(mainPrev, 8000);
 log.debug("is success ? {}", isSuccess);
 }
 }
 private static void sleep(int millis) {
    
 try {
    
 Thread.sleep(millis);
 } catch (InterruptedException e) {
    
 e.printStackTrace();
 }
 }
}

Output results

 [main] try get 10000 
 [t1] 9000 
 [main] try set 8000... 
 [main] is success ? false 
 [main] try set 8000... 
 [main] is success ? true

volatile

When getting shared variables , To ensure the visibility of the variable , Need to use volatile modification . It can be used to modify member variables and static member variables , It can avoid the thread looking up the value of the variable from its own working cache , You have to get its value in main memory , Thread operation volatile Variables operate directly on main memory . A thread pair volatile Modification of variables , Visible to another thread .

Be careful
volatile Only the visibility of shared variables is guaranteed , Let other threads see the latest value , But it can't solve the problem of instruction interleaving （ Atomicity is not guaranteed ）
CAS Must use volatile To read the latest value of the shared variable 【 Compare and exchange 】 The effect of

Why is lockless efficient

• Without a lock , Even if the retry fails , Threads are always running at high speed , There is no pause , and synchronized It will make the thread when it doesn't get the lock , A context switch has occurred , Get in the jam . Make a comparison
• Threads are like racing cars on a high speed track , At high speed , Speed super fast , Once a context switch occurs , It's like a car has to slow down 、 Stalling , When you wake up, you have to start the fire again 、 start-up 、 Speed up … Return to high-speed operation , It costs a lot
• But without lock , Because the thread needs to stay running , Additional requirements CPU Support for ,CPU It's like a high-speed track here , No extra runway , It's impossible for threads to run at high speed , Although it won't get into the jam , But because there is no time slice , It will still be operational , Or will it cause context switching .

CAS Characteristics
combination CAS and volatile Can achieve lock free concurrency , For less threads 、 Multicore CPU In the scene of .

• CAS It's based on the idea of optimistic lock ： The most optimistic estimate , Not afraid of other threads to modify shared variables , Even if it changes, it doesn't matter , I'll try again if I lose something .
• synchronized It's based on the idea of pessimistic lock ： The most pessimistic estimate , Prevent other threads from modifying shared variables , I'm locked. You don't want to change , I've changed it , You have a chance to .
• CAS This is lock free concurrency 、 Non blocking concurrency , Please understand the meaning of these two sentences carefully
  • Because I didn't use synchronized, So threads don't get stuck , It's one of the factors in efficiency
  • But if the competition is fierce , It is conceivable that retrying must occur frequently , On the contrary, efficiency will be affected