Analysis of cas operations in Java

This article analyzes the concepts, principles and usage of cas operations in Java programming through examples. It has certain reference value and friends in need can learn about it.

CAS refers to a special instruction widely supported by modern CPUs that operates on shared data in memory. This instruction performs atomic read and write operations on shared data in memory.

Briefly introduce the operation process of this instruction: First, the CPU will compare the data to be changed in the memory with the expected value. Then, when the two values ​​are equal, the CPU replaces the value in memory with the new value. Otherwise, no operation will be performed. Finally, the CPU returns the old value. This series of operations is atomic. Although they seem complicated, they are the fundamental reason why Java 5 concurrency mechanism is superior to the original lock mechanism. Simply put, the meaning of CAS is "What do I think the original value should be, if so, update the original value to the new value, otherwise do not modify it and tell me what the original value is." (This description is quoted from "Java Concurrent Programming Practice")

Simply put, CAS has 3 operands, the memory value V, the old expected value A, and the new value to be modified B . If and only if the expected value A and the memory value V are the same, 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. Pessimistic lock efficiency Very low.

Let’s look at a simple example:

if(a==b) { 
  a++; 
}

Just imagine what if the value of a is changed before doing a++? Is a++ still executed? The reason for this problem is that in a multi-threaded environment, the value of a is in an uncertain state. Locks can solve such problems, but CAS can also solve them without locks.

int expect = a; 
if(a.compareAndSet(expect,a+1)) { 
  doSomeThing1(); 
} else { 
  doSomeThing2(); 
}

This way a++ will not be executed if the value of a is changed.

According to the above writing method, after a!=expect, a++ will not be executed. What if we still want to perform a++ operation? It doesn’t matter. We can use while loop

while(true) { 
  int expect = a; 
  if (a.compareAndSet(expect, a + 1)) { 
    doSomeThing1(); 
    return; 
  } else { 
    doSomeThing2(); 
  } 
}

Using the above writing method, a++ operation is implemented without locks. This is actually a non-blocking algorithm.

Application

Almost most classes in the java.util.concurrent.atomic package use CAS operations, taking AtomicInteger as an example, see Look at the implementation of several of its main methods:

public final int getAndSet(int newValue) { 
  for (;;) { 
    int current = get(); 
    if (compareAndSet(current, newValue)) 
      return current; 
  } 
}

The explanation in the getAndSet method JDK documentation is: atomically set to a given value and return the old value . Where the atomic method is reflected, it is reflected in compareAndSet. Let's see how compareAndSet is implemented:

public final boolean compareAndSet(int expect, int update) { 
  return unsafe.compareAndSwapInt(this, valueOffset, expect, update); 
}

As expected, it is the CAS operation of the Unsafe class. Completed.

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

public final int getAndIncrement() { 
  for (;;) { 
    int current = get(); 
    int next = current + 1; 
    if (compareAndSet(current, next)) 
      return current; 
  } 
}

is almost exactly the same as the original example, and also uses CAS operations to implement automatic Increase operations.

++a operation is similar to a++ operation, except that the return results are different

public final int incrementAndGet() { 
  for (;;) { 
    int current = get(); 
    int next = current + 1; 
    if (compareAndSet(current, next)) 
      return next; 
  } 
}

In addition, the java.util.concurrent.ConcurrentLinkedQueue class They are all non-blocking algorithms and do not use any locks. They are all implemented based on CAS operations. CAS operation can be said to be the foundation of the JAVA concurrency framework, and the design of the entire framework is based on CAS operations.

Disadvantages:

1. ABA problem

Wikipedia gives a living example——

You are holding a suitcase full of money at the airport. At this time, a hot and sexy beauty comes over. Then she teases you very ambiguously, and when you are not paying attention, she uses the same one. I swapped my suitcase with your suitcase full of money, and then left. You saw that your suitcase was still there, so you took the suitcase and went to catch the plane.

This is the problem with ABA.

CAS operations can easily lead to ABA problems, that is, between doing a++, a may have been modified by multiple threads, but it has just returned to the original value. At this time, CAS will think that the value of a has not changed. a After walking around outside for a while, you can guarantee that it didn’t do anything bad, no! ! Maybe for fun, it decreases the value of b, increases the value of c, etc. What's more, if a is an object, this object may be newly created, and a is a reference. What's the situation? How, so there are still many problems here. There are many ways to solve the ABA problem. You can consider adding a modification count. Only do a++ when the modification count remains unchanged and the value of a remains unchanged. You can also consider introducing a version. No., a++ operations are only performed when the version numbers are the same. This is somewhat similar to transaction atomicity processing!

2. It consumes more CPU resources and will do some useless work even if there is no contention.

3. It will increase the complexity of program testing, and problems may occur if you are not careful.

Summarize

CAS can be used to implement atomic operations without locks, but the application scenarios must be clearly defined. For very simple operations without introducing locks, you can consider using CAS operations. When you want to complete an operation non-blockingly, you can also consider it. CAS. It is not recommended to introduce CAS in complex operations, as it will make the program less readable and difficult to test, and ABA problems will occur.

The above is the detailed content of Analysis of cas operations in Java. For more information, please follow other related articles on the PHP Chinese website!