What is the CAS
While studying the JUC package, you know that at the bottom of the Atomic action class is CAS, so here’s a little note about CAS.
1. Performance problems of Synchronized
If you write this keyword, you know, this is a security problem for multithreading.
The Synchronized keyword can make the thread that does not obtain the lock resource enter the BLOCKED state, and then recover to the RUNNABLE state after the lock resource is captured. This process involves the conversion of the user mode and kernel mode of the operating system, and the cost is relatively high.
Although Java1.6 has been optimized for Synchronized, increasing the transition from bias to lightweight to heavyweight locks, performance is still low after the final shift to heavyweight locks.
2. Tell me about the CAS
CAS is short for Compare And Swap, which translates as Compare And replace.
The CAS mechanism uses three basic operands: the memory address V, the old expected value A, and the new value B to be modified.
When updating A variable, the value of memory address V is changed to B only if the expected value of the variable A is the same as the actual value of memory address V.
This may sound abstract, but let’s look at an example:
Example 3.
1. In memory address V, the variable with the value of 10 is stored.
2. Thread 1 wants to increase the value of the variable by 1. For thread 1, the old expected value A=10, and the new value B=11 to be modified.
3. Before thread 1 commits the update, another thread 2 takes the lead and updates the variable value in memory address V to 11.
4. Thread 1 starts to submit the update, first compares the actual value of A and address V, and finds that A is not equal to the actual value of V, so the submission fails.
5. Thread 1 retrieves the current value of memory address V and recalculates the new value to be modified. Now for thread 1, A=11, B=12. This process of trying again is called spin.
6. This time, fortunately, no other thread changed the value of address V. Thread 1 compares and finds that the actual values of A and address V are equal.
7. Thread 1 swaps address V with address B (12).
Ideologically, Synchronized is a pessimistic lock, pessimistic that the concurrency in the program is serious, so it is strictly guarded. CAS is an optimistic lock, which is optimistic that the concurrency in the program is not so serious, so it keeps the thread trying to update.
4.CAS underlying source code
Assembly language LOCK CMPXCHG instruction, hardware lock is a northbridge signal.
The lock is cpu-level. When a memory value is modified by a CPU, the lock does not allow other cpus to interrupt it.
5. Problems existing in CAS
1. The CPU overhead is high
In the case of high concurrency, if many threads repeatedly try to update a variable, but fail to update, the cycle will put a lot of stress on the CPU.
2. Atomicity of code blocks cannot be guaranteed
The CAS mechanism guarantees atomicity only for a variable, not for an entire code block. For example, Synchronized is used to ensure that all three variables are updated atomically.
3. The problem of ABA
This is the biggest problem with CAS.
What are ABA problems
ABA is not an acronym, but rather a figurative description. ABA problems occur in multithreaded or multiprocess computing environments.
First, DESCRIBE ABA. Suppose two threads T1 and T2 access the same variable V. When T1 accesses variable V, it reads the value of V as A. At this point, thread T1 is preempted, and thread T2 starts executing. T2 first changes the value of variable V from A to B, and then from B back to A. T1 now preempts the initiative and continues, but it sees that V is still A, and it thinks it hasn’t changed, so it continues. In this process, variable V changes from A to B, and then from B to A is figuratively called the ABA problem.
The above description does not seem to cause problems. There should be no problem in determining whether V is A in T1. The result should be the same whether it is A at the beginning or A after ABA.
It is not easy to see the problem mainly because “the value is the same” is equivalent to “no change” (even if it is changed back, it is still a change). After all, in most program code, we just need to know if the value is the same, and we don’t care if it has changed over time; So, ABA is the problem when I need to know “did anything change” during the previous process. People who watch too many police dramas should be able to quickly figure out what’s going on. When applied to the ABA problem, first of all, A and B here do not represent the physical package being dropped, but the change of state in the process of switching. Suppose a 10000W box (regardless of its size) is placed in a room, and 10 minutes later go in and take it out to redeem the person. However, a thief got in within the last 10 minutes (regardless of how he got in) and switched mine with an empty box of the same size. When I looked again, I found the box was still there, so I thought there was no problem and went on with the box on the table (regardless of whether the weight was correct or not). Now it’s just a matter of knowing that there’s a problem. Is it okay to redeem people with empty boxes?
The variable V here is the state of whether there are boxes on the table. A) there are boxes on the table. B is the state when the box leaves the table in the process of switching and there is no box on the table; The last “A” is also the case on the table. But we don’t know what’s in the box.