Fully understand CAS mechanism in Java

preface

When I saw the Java lock mechanism, I accidentally saw the word CAS. Then I looked for CAS in Baidu. I read many articles and didn't understand it very much. Today, I found some information on Google to really understand the CAS mechanism.

What is CAS

One of the most important support added in JDK 1.5 is atomic classes, such as atomicinteger and atomiclong. These classes can help minimize the complexity of some basic operations in multithreading (for example, increasing or reducing the value shared between multiple threads). The implementation of these classes depends on CAS (compare and swap) algorithm.

Optimistic lock and pessimistic lock

CPU is time-division multiplexed, that is, CPU time slices are allocated to different threads / processes for execution in turn. CPU switching is required between time slices, that is, process switching will occur. Switching involves emptying registers and caching data. Then reload the data required by the new thread. When a thread is suspended, it joins the blocking queue and wakes up through notify(), notifyall() under certain time or conditions. When a resource is unavailable, the CPU is released and the current waiting thread is switched to the blocking state. Wait until resources (for example, if a shared data) is available, wake up the thread and let it enter the runnable state to wait for CPU scheduling. This is the implementation of a typical pessimistic lock. An exclusive lock is a pessimistic lock, and synchronized is an exclusive lock. It assumes the worst case and executes only when ensuring that other threads will not cause interference, which will lead to all other locks The thread hangs, waiting for the thread holding the lock to release the lock.

However, there is a lot of overhead in the process of suspending and resuming execution. When a thread is waiting for a lock, it can't do anything, so pessimistic locking has great disadvantages. For example, if a thread needs a resource, but the occupation time of the resource is very short, when the thread preempts the resource for the first time, the resource may be occupied. If the thread is suspended at this time, it may immediately find that the resource is available, and then it will take a long time to re preempt the lock, and the time cost will be very high.

The idea of optimistic locking is to complete an operation without locking each time, assuming that there is no conflict. If the conflict fails, try again until it succeeds. A thread can not give up the CPU, but keep the while loop. If it fails, it will try again until it succeeds. Therefore, optimistic locking works better when data contention is not serious. For example, CAS is an application of optimistic locking.

CAS (compare and swap) algorithm

There are three core parameters in CAS:

1. The V value stored in the main memory is shared by all threads.

2. The V value a last read by the thread from memory is stored in the frame stack of the thread, and each thread is private.

3. You need to write to memory and rewrite the b value of V value. That is, the thread operates on the a value and puts it into the main memory v.

The above is more abstract. It's easier to understand from the following picture.

As shown in the figure above, the V value is saved in the main memory. To use the V value in the thread, first read the V value from the main memory to the working memory a of the thread, then calculate it and turn it into the b value, and finally write the b value back to the memory V value. This is how multiple threads share V values. The core of CAS is to compare whether the a value and the V value are the same before writing the b value to v. if they are different, it proves that the V value has been changed by other threads. Reassign the V value to a and recalculate B. if they are the same, assign the b value to v.

If the CAS mechanism is not used, look at the problems. If v = 1, now thread1 should add 1 to V, and thread2 should also add 1 to v. first, thread1 reads v = 1 into its own working memory A. at this time, a = 1. Suppose thread2 also reads v = 1 into its own working memory A. after adding 1 respectively, the value of B in both threads is 2. When writing back to V, it is found that the value of V is 2, However, the two threads add V respectively, but the result is only 1. There is a problem.

CAS core code

The above operation is an atomic operation. Now let's see if two threads want to add 1 to V at the same time, and whether the correct results can be obtained by using the CAS mechanism above.

① Thread 1 and thread2 need to add 1 to v. thread1 and thread2 read the value of V at the same time and perform the operation of adding 1 to v.

Initial value v = 1, a = 0, B = 0.

② Suppose thread1 and thread2 first read the V value and assign it to a, and add 1 to a to get b = 2.

V=1，T1_ A=1，T1_ B=2； T2_ A=1

Thread1 to T1_ When B is written into V, CAS operation must be performed first:

Because T1_ A = 1 = V, so execute v = T1_ B = 2, v = 2.

③ Thread2 also performs a plus operation on v. After adding

V=2 ，T2_ A=1,T2_ B=2，

When thread2 wants T2_ CAS operation shall be performed before b value is written into v,

At this time T2_ A=1，V=2,T2_ A!= 5. At this time, v = 2 is returned to T2_ A，T2_ A = v = 2, then test T2 again_ Add 1 to a to get T2_ B. At this time T2_ B=3，T2_ A = 2, compare T2_ A = = V, so T2_ The value of B is assigned to T2_ V，T2_ V=T2_ B=3。 The final result is 3. correct.

ABA problem in CAS

If the old value obtained at the beginning position V is a, it is still a when read again during the assignment operation, which does not mean that the variable has not been changed by other threads. It is possible that other threads changed the variable to B and then back to a. In most cases, the ABA problem will not affect the correctness of program concurrency. If the ABA problem is to be solved, the traditional mutually exclusive synchronization may be more efficient than atomic classes.

Solutions to ABA problems

1. Add a version number in front of the variable: add 1 to the version number every time the variable is updated, and A-B-A becomes 1a-2b-3a.

2. Atomicstampedreference class under atomic package: its compareandset method first checks whether the current reference is equal to the expected reference and whether the current flag is equal to the expected flag. If they are all equal, set the value of the flag of the reference to the given updated value in an atomic manner.

The above comprehensive understanding of CAS mechanism in Java is all that Xiaobian has shared with you. I hope it can give you a reference and support more programming tips.