1. Concept and features

CAS(Compare And Swap/Set) The process of the CAS algorithm is as follows: It contains three parameters CAS(V,E, And N). V represents the variable to be updated (memory value), E represents the expected value (old), and N represents the new value. The value of V is set to N if and only if the value of V is equal to the value of E. If the value of V is different from the value of E, another thread has done the update, and if the previous thread does nothing. Finally, CAS returns the true value of the current V. The CAS operation operates with an optimistic attitude (optimistic locking), always assuming that it can successfully complete the operation. When multiple threads operate on a variable using CAS at the same time, only one will win and update successfully, while the rest will fail. Failing threads are not suspended, but are simply notified of their failure and allowed to try again, as well as aborting the operation. Based on this principle, CAS operations can detect interference from other threads to the current thread even if there is no lock, and handle it appropriately.

2, atomic package Java. Util. Concurrent. Atomic spin (lock)

JDK1.5 atomic package: Java. Util. Concurrent. The atomic inside this package provides a set of atomic classes. The basic feature is that in a multithreaded environment, when multiple threads execute the methods contained in the instance of these classes at the same time, it has exclusivity. That is, when one thread enters the method and executes its instructions, it will not be interrupted by other threads, and the other threads will act like a spin lock and wait until the method is complete. It is only logical that the JVM selects one thread from the wait queue to enter another. Compared with synchronized, CAS is a common implementation of non-blocking algorithms. Because CPU switch times are generally longer than CPU instruction set operations, J.U.C provides a significant performance boost. The following code:

private volatile int value; public final int get() { return value; } public final int getAndIncrement() { for (;;) Int current = get(); int next = current + 1; if (compareAndSet(current, next)) return current; } } public final boolean compareAndSet(int expect, int update) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); }}Copy the code

GetAndIncrement uses the CAS operation. Each time the data is read from the memory and then the CAS operation is performed with the result after +1. If the result is successful, the CAS operation is returned. CompareAndSet uses JNI to execute CPU instructions.

3. ABA problems

CAS can cause “ABA problems”. 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 class will lead to data changes at this time. Let’s say one thread fetches A from location V, and two thread two fetches A from location V, and two does something to change it to location B, and then two changes the data from location V to location A, Thread one performs the CAS operation and finds that A is still in memory. Then thread ONE succeeds. Even though the CAS operation on thread one was successful, it does not mean that the procedure is problem-free. Some optimistic locks are implemented to solve THE ABA problem by using version numbers. Each time an optimistic lock performs data modification, it carries a version number. Once the version number is consistent with the data version number, the modification operation can be performed and the +1 operation can be performed for the version number. Because the version number of each operation increases, there is no ABA problem because the version number only increases, not decreases.