This article is from wechat public number [fat rolling pig learning programming], please indicate the source
In the comic concurrent programming system blog post, we talked about N on the knowledge of lock, indeed, lock is the master key to solve the concurrency problem, but the concurrency problem can only be solved by lock? Today we are going to introduce a big BOSS: CAS lock-free algorithm, which is the core of concurrent programming.
So wen
First, let’s review the causes of the atomicity problem, and see how concurrent programming in JAVA solves the atomicity problem.
Both threads load count=0 into their working memory at the same time. Thread B performs count++ first. The main memory has changed to 1, but thread A still thinks count=0, which is the root cause of the problem.
So the solution is: instead of making thread A think count=0, thread A should compare with main memory. If the value in memory is 0, no other thread has updated count, so swap and write the new value back to main memory. If the value in memory is not 0, as in this case, the count in memory has already been updated to 1 by thread B, compare 0! =1, so compare fails and the new value is not written back to main memory.
This article is from wechat public number [fat rolling pig learning programming]. A set of appearance level and talent in a female program yuan, in the form of comics so easy and interesting programming! Please indicate the source of reprint
Concept of CAS
CAS (compareAndSwap), Chinese called comparison swap, a locking atom algorithm.
The CAS algorithm contains three parameters, CAS (V, E, N), where V represents the value of the variable to be updated in memory, E represents the old expected value, and N represents the new value. V is set to N only if the value of V is equal to the value of E. If the values V and E are different, then another thread has already made two updates, and the current thread does not update, but spins.
Simulated CAS implementation
Now that we understand the idea of CAS, we can write a simple CAS model:
// count must be volatile to ensure visibility between threads private volatile static int count; public voidaddOne() {
int newValue;
do {
newValue = count++;
} while(! compareAndSwapInt(expectCount, newValue)); Public final Boolean compareAndSwapInt(int expectCount, int newValue) {// expectCount = expectCount; // Compare whether the current count value == expected valueifExpectCount (curValue == expectCount) {// If so, update the value of count = newValue;return true; } // Otherwise returnfalseThen the cyclereturn false;
}
Copy the codeThis simple simulation code, in fact, basically reflects the idea of CAS, but in fact, CAS principle can be a lot more complex oh, let’s see how JAVA is how to implement CAS!
Atomic classes
To understand the implementation of CAS in JAVA, we have to refer to the well-known atomic class, which is very simple to use, and the profound principle is the CAS lock-free algorithm.
The atomic classes provided in Java bundle are very rich and can be divided into five categories: atomized base data types, atomized object reference types, atomized arrays, atomized object property updaters, and atomized accumulators.
The use of atomic class is very simple, I believe that as long as look at the API to know how to use, so no more explanation, if necessary can refer to my Github code. Here we use AtomicInteger as an example to test if the atomic class is true to its name and guarantees atomicity:
private static AtomicInteger count = new AtomicInteger(0); private static int count1 = 0; // Start 10 threads to test the output of AtomicInteger and ordinary int. Private static voidadd10K() {
int idx = 0;
while(idx++ < 10000) {// implement i++ functionality with incrementAndGet count.incrementandget (); } countDownLatch.countDown(); } private static voidadd10K1() {
int idx = 0;
while (idx++ < 10000) {
count1++;
}
countDownLatch.countDown();
}
Copy the codeAs you can see from your tests, AtomicInteger guarantees an output of 100000, whereas normal int does not.
This article is from wechat public number [fat rolling pig learning programming]. A set of appearance level and talent in a female program yuan, in the form of comics so easy and interesting programming! Please indicate the source of reprint
CAS source code Analysis
How does JAVA implement CAS? Follow the incrementAndGet() method in AtomicInteger and you’ll have the answer. Let’s start with a few things in AtomicInteger.java:
private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; // Address offset of data in memory, ValueOffset = unsafe.objectFieldOffset Static {try {// Calculates the offset of value in the class object (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; // The value volatile ensures visibility public final intincrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
Copy the codeUnsafe is a core CAS class. Java methods cannot access the underlying system directly, requiring native methods. Unsafe is a backdoor that allows you to directly manipulate data in specific memory. The variable valueOffset, which represents the offset address of the variable value in memory, is also used to obtain data. The value variable must be volatile, ensuring memory visibility across multiple threads.
Of course, we’ll have to look at the getAndAddInt method for implementation:
// CAS update internally using spin (whilePublic final int getAndAddInt(Object var1, long var2, int var4) {//var1 is the current Object, Count. GetAndIncrement (), var1 = count; // The second parameter is the AtomicInteger value; // The third parameter is the value to increment int var5;do{//var5 = this.getIntVolatile(var1, var2); }while(! this.compareAndSwapInt(var1, var2, var5, var5 + var4)); // Loop to determine whether the value of the memory location matches the expected original valuereturn var5;
}
Copy the codeThe memory address offset of the instance variable. The expected old value. The value to be updated
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Copy the codeIf you want to get to the bottom of it, you’ll find it’s not moving. Because the native method represents the underlying method, of course, if you must look beyond broadening, you can also look for the corresponding safe. CPP file to parse the C code in depth:
Personally, I don’t think it’s necessary to delve into it. After all, the industry has expertise. All you need to know is that the core code is actually a CMPXCHG instruction. CMPXCHG: Compare and swap instruction. The idea is the same as we said above: compare the value in the EAX register (compare_value) with the value in the [EDX] two-word memory unit, and if they are the same, store the value in the ECX register (exchange_value) in the [EDX] memory unit.
Bottom line: Just keep in mind that CAS is implemented on hardware to increase efficiency at the hardware level. The implementation method is based on hardware platform assembly instructions, in the Intel CPU, the use of CMPXCHG instructions. V is set to the new value N (swap) only when V is equal to E (compare).
Is CAS really that good?
Both CAS and locks solve atomicity problems, are inherently immune to deadlocks because they are non-blocking compared to locks, and there is very little interaction between threads. More importantly, there is no overhead associated with lock contention, and no overhead associated with frequent scheduling between threads, so it has better performance than the lock-based approach.
But is CAS really that good? It’s time to nitpick again!
To disappoint us, CAS is not that good, mainly in three aspects:
- 1. Cycle time is too long
- 2. Only one shared variable atomic operation is guaranteed
- 3. ABA problems.
Loop time is too long And if CAS is unsuccessful for a long time, we know that it will continue to loop and spin. This is bound to be very expensive for the CPU. There are places in JUC that limit the number of CAS spins, such as the SynchronousQueue of BlockingQueue.
If you have multiple shared variables, you can only use locks. Of course, if you have a way to consolidate multiple variables into a single variable, CAS is also good. For example, the high and low bits of state in the read/write lock.
This is an important interview question! Listen carefully!
CAS needs to check whether the operation value has changed. If not, CAS updates the operation value. But there is A situation where if A value is A, changes to B, and then changes to A, CAS checks that it has not changed, but it has changed. This is called the ABA problem. There are cases where ABA is not A concern, such as atomic increments, but not all cases, such as when an atomized update object is likely to be concerned about ABA because the two A’s are equal, but the properties of the second A may have changed.
The solution to the ABA problem is to add A version number, that is, add A version number to each variable and add 1 to each change, so that A — > B — > A becomes 1A — > 2B — > 3A.
The ATOM class AtomicStampedReference solves the ABA problem by internally maintaining not only the object value but also a Stamp (think of it as a version number, which uses an integer to represent the state value). If the value of AtomicStampedReference is modified, you must update the version number as well as the data. When AtomicStampedReference sets the object value, the object value and version number must meet the expected value. Thus, even if the object value is repeatedly read and written back to the original value, as long as the version number changes, improper writes are prevented.
// The parameters are: Expected Write New value Expected Version New Version public Boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp); Public V getReference(); Public int getStamp(); // Set the current object reference and version number public voidset(V newReference, int newStamp);
Copy the codeIt’s no use talking about theories, but try it out for yourself to see if it can solve the ABA problem:
private static AtomicStampedReference<Integer> count = new AtomicStampedReference<>(10, 0); public static void main(String[] args) { Thread main = new Thread(() -> { int stamp = count.getStamp(); // Get the current version log.info("Thread {} current version {}",Thread.currentThread(),stamp); try { Thread.sleep(1000); // Wait 1 second for the interfering thread to execute} catch (InterruptedException e) {e.printStackTrace(); } boolean isCASSuccess = count.compareAndSet(10, 12, stamp, stamp + 1); // At this point, the expectedReference is not changed, but stamp has been modified, so the CAS fails log.info("CAS successful ={}",isCASSuccess);
}, "Main thread of action"); Thread other = new Thread(() -> { int stamp = count.getStamp(); // Get the current version log.info("Thread {} current version {}",Thread.currentThread(),stamp);
count.compareAndSet(10, 12, stamp, stamp + 1);
log.info("Thread {} added after version {}",Thread.currentThread(),count.getStamp());
// 模拟ABA问题 先更新成12 又更新回10
int stamp1 = count.getStamp(); //获取当前版本
count.compareAndSet(12, 10, stamp1, stamp1 + 1);
log.info("Thread {} reduced version {}",Thread.currentThread(),count.getStamp());
}, "Interfering with threads");
main.start();
other.start();
}
Copy the codeThe following output is displayed:
INFO - Thread INFO - Thread INFO - Thread INFO - Thread INFO - Thread INFO - Thread INFO INFO - Thread Thread[interfering Thread,5,main] reduced after version 2 [main operating Thread] INFO - CAS succeeded =false
Copy the codeconclusion
JAVA has a lot more to do with concurrency than just locking. CAS lock-free algorithm is also necessary to solve atomicity problems. Atomic classes, on the other hand, are an example of lockless utility classes. Atomic classes include five types (atomized basic data types, atomized object reference types, atomized arrays, atomized object property updaters, and atomized accumulators).
CAS is a kind of optimistic lock. The optimistic lock takes a more optimistic attitude towards things, believing that it can be successfully operated. A pessimistic lock keeps a thread blocked. Therefore, CAS has many advantages, such as high performance and deadlock avoidance. But it’s not that good, you should take into account ABA issues, long circulation times. Therefore need comprehensive choice, suit oneself just is the best.
Appendix: Concurrent programming full series of code github
This article is from wechat public number [fat rolling pig learning programming]. A set of appearance level and talent in a female program yuan, in the form of comics so easy and interesting programming! Welcome to communicate with me!
This article is reprinted from the public number [fat rolling pig learning programming] programming with comics so easy and interesting! Welcome to pay attention!