CAS (Compare and Swap)

CAS (Compare and Swap Compare and Replace) is a CPU concurrency primitive. It is an implementation of optimistic lock and a lightweight lock.

How does CAS implement thread safety

When a thread reads data, it does not lock it. When preparing to write back data, it queries the original value first and compares whether the original value has been modified. If the original value has not been modified by other threads, it writes back. The process isThe atomic. Let’s use the graph to make it a little bit more intuitive.

public class CASDemo{
	public static void main(string[] args){
		AtomicInteger atomicInteger = new AtomicInteger(initialValue: 5);
		// main do thing......
		
		System.out.println(atomicInteger.compareAndSet(expect: 5, update: 2020) + "\t current data: " + atomicInteger.get());

		System.out.println(atomicInteger.compareAndSet(expect: 5, update: 1024) + "\t current data: "+ atomicInteger.get()); }}Copy the code

There are still problems along the way:

1. Long cycle time and high cost.

If the CAS fails, the system keeps trying. If the CAS fails for a long time, the CPU may be expensive.

2 guarantees atomic operations of only one shared variable.

CAS can operate on a single shared variable to ensure the operation of atoms, but not on multiple variables. After JDK 5, AtomicReference can be used to ensure atomicity between objects, so that multiple objects can be operated in CAS.

AtomicInteger, for example, implements its incrementing function incrementAndGet () in this way, with a lot of iterating until the condition is met.

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:var5 + var4));
	
	return var5;
}
Copy the code

The loop determines whether a given offset is equal to an offset in memory until it succeeds.

3 ABA problem

Order of execution:

thread1Read data from thread A2Read data from thread A2The CAS comparison shows that the value of A is correct, so we can change data A to data B thread3Thread B reads the data3After CAS comparison, it is found that data B is correct, so we can change data B to data A thread1Through CAS comparison, it found that the data was still A unchanged, so it wrote the value it wanted to changeCopy the code

None of the threads did anything wrong in the process, but the value was changed and thread 1 had no way of finding out. In fact, this situation has no effect on the result itself, but we need to guard against it.

How to prevent ABA problems?
  1. Add flag bit. For example, to add an increment field, each operation increments by one.
  2. The time stamp. Compares the value of the timestamp

Unadded version number:

// A previously unadded version number
update table set value = newValue where value = #{oldValue}
//oldValue is the value queried before execution
Copy the code

Added version number:

// Add the version numberUpdate table set value = newValue, vision = vision +1 where value = #{oldValue} and vision = #{vision} 
// Check whether the original value and the version number match, there are other threads in the middle, the value may be equal, but the version number is 100% different
Copy the code