Comprehensive analysis of CAS operation in Java programming

CAS refers to a special instruction widely supported by modern CPU to operate the shared data in memory. This instruction will perform atomic read and write operations on the shared data in memory.

Briefly introduce the operation process of this instruction: first, the CPU will compare the data to be changed in memory with the expected value. Then, when the two values are equal, the CPU will replace the value in memory with the new value. Otherwise, do not operate. Finally, the CPU returns the old value. This series of operations is atomic. Although they seem complex, they are the fundamental reason why Java 5 concurrency mechanism is better than the original locking mechanism. In short, CAS means "what do I think the original value should be? If yes, update the original value to a new value, otherwise do not modify it, and tell me what the original value is". (this description is quoted from the Java Concurrent Programming practice.)

In short, CAS has three operands, the memory value V, the old expected value a, and the new value B to be modified. If and only if the expected value a is the same as the memory value V, modify the memory value V to B, otherwise return v. This is an optimistic lock idea. It believes that no other thread will modify it before it is modified; Synchronized is a pessimistic lock. It believes that other threads will modify it before it is modified. The efficiency of pessimistic lock is very low.

Here is a simple example:

Imagine what if the value of a is changed before doing a + +? Is a + + still implemented? The reason for this problem is that in a multithreaded environment, the value of a is in an uncertain state. Lock can solve such problems, but CAS can also solve them without lock.

In this way, if the value of a is changed, a + + will not be executed.

According to the above writing, a= After expect, a + + will not be executed. If we still want to execute a + + operation, it doesn't matter. We can use the while loop

Using the above writing method, a + + operation is realized without lock, which is actually a non blocking algorithm.

application

java. util. concurrent. Almost most classes in the atomic package adopt CAS operations. Take atomicinteger as an example to see the implementation of its main methods:

The getandset method is explained in the JDK document that it is set atomically to the given value and returns the old value. Where the atomic mode is reflected is reflected in the compareandset. See how the compareandset is implemented:

As expected, it is completed by the CAS operation of the unsafe class.

Let's take a look at how the a + + operation is implemented:

Almost as like as two peas, the CAS operation is used to achieve self increment.

++The a operation is similar to the a + + operation, but the results are different

In addition, Java util. concurrent. The concurrentlinkedqueue class is all non blocking algorithms. It does not use any locks. It is all implemented based on CAS operations. CAS operation can be said to be the basis of Java concurrency framework. The design of the whole framework is based on CAS operation.

Disadvantages:

1. ABA problem

Wikipedia gives a living example --

You are as like as two peas in a suitcase full of money at the airport. At this point, a hot and beautiful woman comes to her. Then she is very provocative to you. When you don't pay attention, you put a bag in the same suitcase and your money filled box, then leave, you see your suitcase is still there, so you carry your suitcase to catch the plane.

This is the ABA problem.

CAS operation can easily lead to ABA problems, that is, during a + + operation, a may have been modified by multiple threads, but returned to the original value. At this time, CAS will think that the value of a has not changed. A after walking around outside, you can guarantee that it hasn't done anything bad, can't!! Maybe it's easy to reduce the value of B, add the value of C, etc. What's more, if a is an object, the object may be newly created, and a is a reference, so there are still many problems. There are many methods to solve the ABA problem. You can consider adding a modification count, Only when the modification count remains unchanged and the a value remains unchanged can a + + be performed. You can also consider introducing a version number. When the version number is the same, a + + operation can be performed. This is somewhat similar to transaction atomicity processing!

2. Compared with CPU resources, it will do some useless work even if there is no contention.

3. It will increase the complexity of program testing, and problems will occur if you don't pay attention to it.

summary

CAS can be used to realize atomic operation without lock, but the application situation should be clear. CAS operation can be considered for very simple operation without introducing lock. CAS can also be considered when you want to complete a certain operation without blocking. It is not recommended to introduce CAS into complex operations, which will make the program less readable and difficult to test, and ABA problems will occur.

The above is all about Java programming CAS operation in this paper. I hope it can be helpful to you.