“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The introduction

When I saw the compareAndSetState method call while writing ReentrantLock, I wanted to write an article about CAS operations and the ABA problems CAS might cause. Technology leaders can be directly closed, this article is really pediatric, suitable for the foundation of the weak students to watch. If you feel 👨🎓 at 👌, you can leave a comment in the comments section, or light up ❤️ to support it.

CAS

First, write the source code for the compareAndSetState method below.

/** * If the current status value is equal to the expected value, the synchronization status is automatically set to the given update value. * This operation has the memory semantics of volatile reads and writes. *@paramExpect *@paramUpdate the new values@returnFalse indicates that the actual value does not equal the expected value, and true indicates success */
protected final boolean compareAndSetState(int expect, int update) {
	// See below for intrinsics setup to support this
	return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
Copy the code

What is CAS?

PareAndSwapInt unsafe.compareAndSwapInt is called, compareAndSwap is the full name of CAS, compareAndSwap. The function of this statement is to determine whether the value in memory is the same as the expected value, if so, change to the new value. This whole process is atomic and therefore a concurrent safe operation.

The CAS theory

CAS operates using the concept of optimistic locking. Leave the lock unlocked each time, assuming no conflicts to complete an operation, and retry until it succeeds if it fails because of conflicts. The trial and error here is really the spin. The broadening class has the following source code:

/**
 * Atomically update Java variable to <tt>x</tt> if it is currently
 * holding <tt>expected</tt>.
 * @return <tt>true</tt> if successful
 */
public final native boolean compareAndSwapInt(Object o, long offset,
                                              int expected,
                                              int x);
Copy the code

The broadening class uses these two values to retrieve the actual value of the object in its main memory. If not, the parsing parsing class compares the expected value to ♻️ until the expected value equals the expected value and writes the expected value x back to the main memory.

ABA problem

An important prerequisite for CAS algorithm implementation is to take out the data in memory at a certain time and compare and replace the data at the next time, so the time difference will lead to data changes. An 🌰 : Remove objects from memory such as A thread 1 o has A value of A, then thread 2 also remove objects from the memory o has A value of A, and thread 2 for some operation becomes the value to B, then another thread 2 o values into A, thread 1 at this time for the CAS operation was found in the memory is still A, then thread 1 performs operations will become C value, The operation succeeds. Even though the CAS operation on thread 1 was successful, it does not mean that the process was problem-free. If the head of the list changes twice and then returns to its original value, it does not mean that the list has not changed. So how to solve this problem? This requires the AtomicStampedReference class to solve the ABA problem.

AtomicStampedReference solves ABA problems

This class maintains a version number Stamp, which is similar to optimistic lock. When the CAS operation is performed, not only the current value is compared, but also the version number. Update operations are performed only if both are equal.

AtomicStampedReference.compareAndSet(expectedReference,newReference,oldStamp,newStamp);
Copy the code

🌰 above, for one, when values out of A thread 1, plus A version number, the hypothesis is 1, then thread 2 values out A, also added A version number, hypothesis 1, thread 2 will value becomes B, the version number into 2, again, when the value into A version number into 3, thread 1 continue at this time, compare the version number of the value of 3 in the main memory If the version number obtained by thread 1 is different from that obtained by thread 1, the operation fails and the value is read from main memory again. The value is obtained by thread 1 and the version number is 3. The operation then changes the value to C.

conclusion

  • CAS uses a spin lock, which is always circulating and has a high overhead. It is suitable for some scenarios with low concurrency and few thread contention. However, once the thread conflict is serious, the loop time is too long, which brings a lot of overhead to the CPU.
  • Atomic operations can only be guaranteed for one variable, and multiple variables are still locked. Raises theABA problem(using theAtomicStampedReferenceSolvable).