Interview questions (CAS)

Preparation of common interview questions for large enterprises

It's right to talk CAS The understanding of the ？

questions : secondary
Title Description : Question line CAS—> Unsafe—> CAS Underlying principle —> Atomic reference update —> How to avoid ABA problem

Topic analysis

compareAndSet How to use it? ？（ Compare and exchange ）

/** * boolean compareAndSet(int expect,int update) * -  If the value of main memory = Look forward to expect, Change the main memory value to update * -  This method can detect threads a Operation variables for X Not modified by other threads  * -  Guaranteed thread safety  */
public static void main(String[] args)
{
    
	AtomicInteger atomicInteger = new AtomicInteger(5);
	System.out.println(atomicInteger.compareAndSet(5, 10)+ "\t" + atomicInteger);
	System.out.println(atomicInteger.compareAndSet(5, 20)+ "\t" + atomicInteger);
	//true 10
	//false 10
}

CAS A brief description of the underlying principle ？
1.Compare-And-Swap. It's a piece. CPU Concurrent primitives .（ The original language ： Operating system category , Relying on hardware , Without interruption .）
2. The function is to judge whether the value of a certain location in the memory is the expected value （Compare）, If yes, update （Swap）, This process is atomic .
3. Function description
a: The function is to judge whether the value of a certain location in the memory is the expected value （Compare）, If yes, update （Swap）, This process is atomic .
b:cas There are three operands , Memory value V, Old expectations A, Values to update B. Only if expected A= Memory value V when , Only the memory value V It is amended as follows B, Otherwise, do nothing
4. The spin ： Compare and exchange , Until it's more successful
5. The bottom depends on Unsafe Class guarantees atomicity .
6.getAndIncrement() The source code parsing （ It was used cas Ensure thread safety ）

/** *  Parameter description ： * this: atomicInteger object  * valueOffset： The memory address of the object  * unsafe：sun.misc.Unsafe class  * AtomicInteger Medium variable value Use volatile modification , Keep memory visible . *  Conclusion ： The underlying dependence CAS operation /Unsafe class  * */
public final int getAndIncrement() {
    
	return unsafe.getAndAddInt(this,valueOffset, 1);
}

/** 1. compareAndSwapInt： namely CAS 2. while:  If the modification fails , Will always try to modify , Until success . */
public final int getAndAddInt(Object var1, long var2, int var4) {
    
	int var5;
	do {
    
		var5 =this.getIntVolatile(var1, var2);
	}
	while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
	return var5;
}

sketch ：

1. Called Unsafe Class getAndAddInt
2. getAndAddInt Use cas Keep trying to modify the main memory in a loop

Yes Unsafe The understanding of the ?

1. All methods of this class are native modification , Directly call the underlying resources .sun.misc In bag
2. Can be like C Direct operation of memory as a pointer to .java Of CAS Operational dependency Unsafe Class method

CAS What are the disadvantages ？

• Long cycle time , Spending big （ If cas Failure , Always do while Try . If it doesn't work for a long time , May give CPU It's a big expense ）
• Only one atomic operation of shared variables can be guaranteed （ If there are multiple shared variables ,cas There is no guarantee of atomicity , Only locks , Lock the code segment ）
• There is ABA problem

sketch ABA Problems and solutions ？
ABA Problem description : Threads 1 do CAS Operation will A Change it to B Change it to A, And threads 2 Do it again CAS The modification was successful , This is not in line with the design idea .
How to solve ：AtomicStampReference Time stamp atom reference

ABA Problem description ：
Like threads 1 From memory location V Remove from A, The thread 2 Also take out A. And thread 2 Did it once cas Change the value to B, Then I did it again cas Changed the value back to A. The thread 1 do cas Found in memory or A, The thread 1 Successful operation . This time actually A The value has been changed by other threads , This is not in line with the design idea

What's wrong with this process ？
If you only care about the result ,ABA Don't you mind? B The existence of , No problem
If B The existence of will have an impact , Need to pass through AtomicStampReference, Add timestamp to solve .

What is the atomic update reference ？
AtomicStampReference, Use time stamps , solve cas What happened in ABA problem .

/** *  If you want the variable of atomic operation to be  User,Book, You need to use AtomicReference class  */
public static void main(String[] args) {
    
	User z3 = new User("z3",18);
	User l4 = new User("l4",19);
	AtomicReference<User> atomicReference = new AtomicReference<>(z3);
	System.out.println(atomicReference.compareAndSet(z3, l4) + "\t" + atomicReference.get().toString());
	System.out.println(atomicReference.compareAndSet(z3, l4) + "\t"+ atomicReference.get().toString());
	//true [email protected]
	//false [email protected]
}

AtomicReference There is ABA Problem code verification

AtomicReference atomicReference = new AtomicReference<Integer>(100);
/** * ABA Problem verification ： * 1--ABA * 2--A,C * @param args */
public static void main(String[] args) {
    
	ABADemo abaDemo = new ABADemo();

	new Thread(()->{
    
		abaDemo.atomicReference.compareAndSet(100,101);
		abaDemo.atomicReference.compareAndSet(101,100);
	},"1").start();
	new Thread(()->{
    
		//  sleep 1s Wait for the thread 1 After execution ABA
		try
		{
    TimeUnit.SECONDS.sleep(1);}
		catch (InterruptedException e) {
    
			e.printStackTrace();
		}
		System.out.println(abaDemo.atomicReference.compareAndSet(100,2020)+"\t"+abaDemo.atomicReference.get());
		//true 2020
	},"2").start();

AtomicStampReference solve ABA Problem code verification
Solutions ： Every time a variable is updated , Add one to the version number of the variable , In this way, as long as the variable is modified by a thread , The version number of this variable will be incremented , So it solved ABA change

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

public static void main(String[] args) {
    
	// ABAProblem();
	ABADemo abaDemo = new ABADemo();
	new Thread(()->{
    
		//  Wait for the thread 2 Read the value of the initial version number 
		try
		{
    TimeUnit.SECONDS.sleep(1);}
		catch (InterruptedException e) {
    
		e.printStackTrace();}
		
		System.out.println(" Threads 1 stay ABA Previous version number ："+abaDemo.atomicStampedReference.getStamp());
		abaDemo.atomicStampedReference.compareAndSet(100,101,abaDemo.atomicStampedReference.getStamp(),
		abaDemo.atomicStampedReference.getStamp()+1);
		abaDemo.atomicStampedReference.
		compareAndSet(101,100,abaDemo.atomicStampedReference.getStamp(),abaDemo.atomicStampedReference.getStamp()+1);
		System.out.println(" Threads 1 stay ABA Later version number ："+abaDemo.atomicStampedReference.getStamp());
	},"1").start();
	
	new Thread(()->{
    
		//  Save the version number before modification 
		int stamp = abaDemo.atomicStampedReference.getStamp();
		System.out.println(" Threads 2 Version number before modification ："+stamp);
		//  sleep 1s Wait for the thread 1 After execution ABA
		try
		{
    TimeUnit.SECONDS.sleep(2);}
		catch (InterruptedException e) {
    
		e.printStackTrace();}
		System.out.println(abaDemo.atomicStampedReference.compareAndSet(100,2020,stamp,abaDemo.atomicStampedReference.getStamp()+1)+"\t" +abaDemo.atomicStampedReference.getReference());
		// Threads 2 Version number before modification ：1
		// Threads 1 stay ABA Previous version number ：1
		// Threads 1 stay ABA Later version number ：3
		//false 100
	},"2").start();