Java high concurrency core programming – CAS and JUC atomic class

Note: This note is a note compiled after reading "Java High Concurrency Core Programming Volume 2"!

Principle of CAS
JUC atomic class-Atomic
basic atomic class
array atomic class
reference atomic class
field update atomic class
AtomicInteger thread safety principle
reference type atomic class
property update atomic class
ABA questions
Improve the performance of CAS operation in high concurrency scenarios
Exchange space for time: LongAdder
CAS advantages and disadvantages
Improve CAS performance

The JVM’s synchronized lightweight lock uses CAS (Compare And Swap, compare and exchange) for spin grabbing. CAS is an atomic operation at the CPU instruction level and is in user mode, so the JVM is lightweight Lock overhead is small. The atomic classes in the java.util.concurrent.atomic package (such as AtomicXXX) all use CAS to guarantee the atomicity of operations on digital members. Most classes of java.util.concurrent (including explicit locks and concurrent containers) are implemented based on AQS and AtomicXXX, in which AQS guarantees the atomicity of its internal bidirectional queue head and tail operations through CAS

CAS principle

The JUC (java.util.concurrent) concurrency package added by JDK 5 encapsulates the underlying CAS atomic operation of the operating system, and provides an API for CAS operations for upper-level Java programs. CAS is a lock-free algorithm. The key to this algorithm depends on two values-the expected value (the current value) and the new value. The underlying CPU uses atomic operations to determine whether the original value of the memory is equal to the expected value. If they are equal, the Assign a new value to the memory address, otherwise do nothing.

The steps for lock-free programming using CAS are roughly as follows:

  1. Get the expected value (oldValue) of the field.
  2. Calculate the new value ( newValue ) that needs to be replaced.
  3. Put the new value (newValue) on the memory address of the field through CAS. If CAS fails, repeat steps 1) to 2) until CAS succeeds. This repetition is commonly known as CAS spin.
do
{<!-- -->
    Obtain the expected value (expValue) of the field, that is, read the original value of the memory;
    Calculate the new value (newValue) that needs to be replaced;
} while (!CAS(memory address, expValue, newValue)) // Determine whether the expected value is equal to the original value of the current memory. If it is equal, it means that no one has modified it during this period, otherwise it has been modified, and the expected value is regained.

Suppose the memory value of the shared variable V is 100, thread A subtracts 1 from V, and thread B adds 1 to V. Use CAS to achieve: no matter whether A or B wants to modify it, first obtain the value of V as the expected value, and then perform the operation. When submitting the modification at the end, you need to use the initial expected value to compare with the original value V of the memory. If it is equal, it means was not modified. If it is not equal, it means that it has been modified, and repeat the previous operation to obtain the V value as the expected value. . .

When there are few threads for concurrent modification and fewer opportunities for conflicts, the number of spins will be small, and the performance of CAS will be high; when there are many threads for concurrent modification and more opportunities for conflicts, the number of spins will be more, CAS Performance will be greatly reduced. Therefore, the key to improving the efficiency of CAS lock-free programming is to reduce the chance of conflicts. Therefore, CAS is suitable for scenarios with a small number of concurrent threads.

CAS must use volatile to read the latest value of the shared variable to achieve the effect of comparison and exchange

CAS atomic operations can be implemented using the Unsafe class:

//Through CAS atomic operation, perform "comparison and exchange"
public final boolean unSafeCompareAndSet(int oldValue, int newValue)
{<!-- --> //valueOffset: The offset indicates the offset of the variable value relative to the current object address, and Unsafe obtains data based on the memory offset address. Atomic operation: use unsafe "compare and exchange" method to exchange the value attribute
return unsafe. compareAndSwapInt( this, valueOffset, oldValue , newValue );
}

JUC atomic class-Atomic

When multiple threads are executed concurrently, operations such as “++” or “–” are not atomic and are not thread-safe operations. Usually, you will use synchronized to turn these thread-unsafe operations into synchronous operations, but this will reduce the performance of concurrent programs. Therefore, JDK provides some atomic classes for these types of unsafe operations. Compared with the synchronized synchronization mechanism, JDK atomic classes are implemented based on CAS lightweight atomic operations, which makes the program run more efficiently.

The atomic classes in the JUC concurrent package are all stored in the java.util.concurrent.atomic class path, and the atomic classes in the JUC package can be divided into four categories: basic atomic classes, array atomic classes, atomic reference classes, and field update atomic classes. The basic atomic class and the array atomic class are mainly used, and the others are known a little bit.

Basic atomic class

The function of the basic atomic class is to atomically update the value of the Java basic type variable:

  • AtomicInteger: Integer atomic class.
  • AtomicLong: long integer atomic class.
  • AtomicBoolean: Boolean atomic class.

In a multi-threaded environment, if it involves concurrent operations of basic data types, it is not recommended to use synchronized heavyweight locks for thread synchronization. Instead, it is recommended to use basic atomic classes first to ensure the thread safety of concurrent operations. The commonly used methods of the basic atomic class AtomicInteger are mainly as follows:

public final int get() //Get the current value
public final int getAndSet(int newValue) //get the current value, and then set the new value
public final int getAndIncrement() //Get the current value and then increment
public final int getAndDecrement() //Get the current value, and then decrement
public final int getAndAdd(int delta) //Get the current value and add the expected value
boolean compareAndSet(int expect, int update); //Set the integer value by CAS

int tempvalue = 0;
AtomicInteger i = new AtomicInteger(0);
//Get the value, then set a new value i=3
tempvalue = i. getAndSet(3);
//Get the value, then increment i=4
tempvalue = i. getAndIncrement();
//Get the value, then add 5 i=9
tempvalue = i. getAndAdd(5);
//CAS exchange i=100
boolean flag = i. compareAndSet(9, 100);
Array atomic class

The function of the array atomic class is to atomically update the value of an element in the array:

  • AtomicIntegerArray: Integer array atomic class.
  • AtomicLongArray: Long integer array atomic class.
  • AtomicReferenceArray: reference type array atomic class

The methods provided by the above three classes are almost the same, so we take AtomicIntegerArray as an example here. Common methods of the AtomicIntegerArray class are as follows:

//Get the value of the element at index=i
public final int get(int i)
//Return the current value at index=i and set it to a new value: newValue
public final int getAndSet(int i, int newValue)
//Get the value of the element at index=i position, and let the element at this position auto-increment
public final int getAndIncrement(int i)
//Get the value of the element at index=i, and let the element at this position decrement
public final int getAndDecrement(int i)
//Get the value of the element at index=i, and add the expected value
public final int getAndAdd(int delta)
//If the input value is equal to the expected value, atomically set the element value at position i to the input value (update)
boolean compareAndSet(int expect, int update)
//finally set the element at position i to newValue
//The lazySet method may cause other threads to read the old value for a short period of time
public final void lazySet(int i, int newValue);

int tempvalue = 0;
// original array
int[] array = {<!-- --> 1, 2, 3, 4, 5, 6 };
// Wrap as an atomic array
AtomicIntegerArray i = new AtomicIntegerArray(array);
//Get the 0th element, then set it to 2, output tempvalue:1; i:[2, 2, 3, 4, 5, 6]
tempvalue = i. getAndSet(0, 2);
//Get the 0th element, then increment, output tempvalue:2; i:[3, 2, 3, 4, 5, 6]
tempvalue = i.getAndIncrement(0);
// Get the 0th element, then add a delta 5, output tempvalue: 3; i: [8, 2, 3, 4, 5, 6]
tempvalue = i.getAndAdd(0, 5);
Reference atomic class

Reference atomic classes mainly include the following three:

  • AtomicReference: reference type atomic class.
  • AtomicMarkableReference: An atomic reference type with an update mark bit.
  • AtomicStampedReference: An atomic reference type with an updated version number.
Field update atomic class

Field update atomic classes mainly include the following three:

  • AtomicIntegerFieldUpdater: An updater for atomically updating integer fields
  • AtomicLongFieldUpdater: An updater for atomically updating long integer fields.
  • AtomicReferenceFieldUpdater: Atomically updates fields in reference types.
AtomicInteger thread safety principle

The basic atomic class (taking AtomicInteger as an example) is mainly implemented through the combination of CAS spin + volatile, which not only ensures the thread safety of variable operations, but also avoids the high overhead of synchronized heavyweight locks, making Java programs more efficient. for promotion. CAS is used to ensure the atomicity of variable operations, and the volatile keyword is used to ensure the visibility of variables (that is, a thread modifies the value of a volatile variable, which is immediately visible to other threads.), and the two are often used in combination.

Source code implementation:

//Unsafe class instance, also use the CAS operation of Unsafe class
private static final Unsafe unsafe = Unsafe. getUnsafe();
//Internal value, use volatile to ensure thread visibility
private volatile int value;
// Compare expect (expected value) and value, if they are different, return false
//If expect is the same as value, assign the new value to value and return true, otherwise loop spin until success
return unsafe. compareAndSwapInt(this, valueOffset, expect, update);
Reference type atomic class

The basic atomic type can only guarantee the atomic operation of one variable. When multiple variables need to be operated, CAS cannot guarantee the atomic operation. At this time, AtomicReference (atomic reference type) can be used to ensure the atomicity of the object reference. To put it simply, if you need to guarantee the atomicity of operations on multiple variables at the same time, you can put multiple variables in one object for operation.

After wrapping the User object with the atomic reference type AtomicReference, only the atomic operation of the User reference can be guaranteed, and atomicity cannot be guaranteed when modifying the field value of the wrapped User object, which must be kept in mind.

Here we take AtomicReference as an example to introduce. First, define a User class with attributes including uid, nickName, and age.

public class User implements Serializable{<!-- -->
    String uid; //User ID
    String nickName; //nickname
    public volatile int age; //age
    public User(String uid, String nickName){<!-- -->
        this.uid = uid;
        this.nickName = nickName;
    }
    @Override
    public String toString(){<!-- -->
        return "User{" +
            "uid='" + getUid() + ''' +
            ", nickName='" + getNickName() + ''' +
            ", platform=" + getPlatform() +
            '}';
    }
}

Use AtomicReference to atomically modify the reference of User, the code is as follows:

//wrapped atomic object
AtomicReference<User> userRef = new AtomicReference<User>();
//User object to be wrapped
User user = new User("1", "Zhang San");
// set the value for the atomic object
userRef.set(user);
//User object to be replaced by CAS
User updateUser = new User("2", "Lisi");
//Use CAS to replace , success is true, user is Lisi
boolean success = userRef. compareAndSet(user, updateUser);
Attribute update atomic class

If you need to guarantee the atomicity of the update operation of a certain field (or attribute) of the object, you need to use the attribute update atomic class. Here we take AtomicIntegerFieldUpdater as an example. The process of using the attribute update atomic class to ensure the security update of attributes generally requires two steps:

  • In the first step, the updated object properties must use the public volatile modifier.
  • In the second step, because the object’s property modification type atomic class is an abstract class, you must use the static method newUpdater() to create an updater every time you use it, and you need to set the class and property you want to update.
//Use the static method newUpdater() to create an updater updater
AtomicIntegerFieldUpdater<User> updater=
AtomicIntegerFieldUpdater.newUpdater(User.class, "age");
User user = new User("1", "Zhang San");
//Use the getAndIncrement and getAndAdd of the attribute updater to increase the age value of the user
Print.tco(updater.getAndIncrement(user)); // 1
Print.tco(updater.getAndAdd(user, 100)); // 101
/ / Use the get of the attribute updater to get the age value of the user
Print.tco(updater.get(user)); // 101
ABA Question

For example, one thread A fetches V1 from memory location M, and another thread B also fetches V1. Now suppose that thread B changes the data V1 at the M position into V2 after performing some operations, and then changes V2 into V1 after some operations. Afterwards, thread A performs the CAS operation, but thread A finds that the data at position M is still V1, and finally thread A succeeds in the operation. Although the CAS operation of thread A is successful, it does not mean that there is no problem in this process. The data V1 operated by thread A may not be the previous V1, but the V1 replaced by thread B. This is the ABA problem.

Example: Suppose the memory value of the shared variable V is 100, thread A subtracts 1 from V and then adds 1, and thread B adds 1 to V and then subtracts 1. Use CAS to achieve: no matter whether A or B wants to modify it, first obtain the value of V as the expected value, and then perform the operation. When submitting the modification at the end, you need to use the initial expected value to compare with the original value V of the memory. If it is equal, it means was not modified. If not equal it means it has been modified. In this case, no matter which thread A or thread B reads and modifies first, the subsequent thread can always modify successfully without spinning! That is, as if this optimistic lock does not exist!

Solution:

Using the version number method of optimistic lock, optimistic lock will bring a version number every time it executes data modification operation. If the version number is consistent with the data version number, the modification operation can be performed and the version number will be incremented by 1, otherwise it will be executed fail. Because the version number of each operation will increase accordingly, there will be no ABA problem, because the version number will only increase and not decrease.

JDK provides a class similar to AtomicStampedReference to solve the ABA problem. AtomicStampReference adds a Stamp (stamp or mark) on the basis of CAS. Using this stamp can be used to detect whether the data has changed, and bring a kind of effectiveness test to the data. The compareAndSet() method of AtomicStampReference first checks whether the current object reference value is equal to the expected reference, and whether the current stamp flag is equal to the expected flag, and if all are equal, update the reference value and stamp flag value to the given value in an atomic way Update the value.

//The first parameter of the compareAndSet method is the original parameter in the original CAS, and the second parameter is the new parameter to be replaced.
//The three parameters are the old version number of the original CAS data, and the fourth parameter indicates the version number after replacement.
public boolean compareAndSet(V expectedReference, // expected reference value
                             V newReference, //Updated reference value
                             int expectedStamp, //old version number
                             int newStamp) //New version number, just + 1

Improve the performance of CAS operations in high concurrency scenarios

In a scene with intense contention, it will lead to a large number of CAS empty spins. For example, when a large number of threads modify an AtomicInteger concurrently, many threads may spin continuously, and some threads may even enter an infinitely repeating loop. A large number of CAS idle spins will waste a lot of CPU resources and greatly reduce the performance of the program. A large number of CAS operations may also cause a “bus storm”. How to improve the performance of CAS operations in high concurrency scenarios? LongAdder can be used instead of AtomicInteger.

Exchanging space for time: LongAdder

Java 8 provides a new class, LongAdder, to improve the performance of CAS operations in high-concurrency scenarios by exchanging space for time. The core idea of LongAdder is hotspot separation, which is similar to the design idea of ConcurrentHashMap: separate the value into an array, and when multi-threaded access, use the Hash algorithm to map the thread to an element of the array for operation; when obtaining the final value result, then sums the elements of the array. The internal members of LongAdder contain a base value and a cells array. When there is no competition at the beginning, only the value of base is operated; when the thread fails to execute CAS, the cells array is initialized and the corresponding element is allocated to the thread. Equivalent to segmented optimistic locking!

//The following is the traditional way
// define an atomic object
AtomicLong atomicLong = new AtomicLong(0);
atomicLong. incrementAndGet();
sout(atomicLong. get());
//The following is the LongAdder approach
//Define a LongAdder object
LongAdder longAdder = new LongAdder();
longAdder. add(1);
sout(longAdder. longValue());

AtomicLong uses the internal variable value to save the actual long value, and all operations are performed on the value variable. In other words, in a high-concurrency environment, the value variable is actually a hotspot, that is, N threads compete for a hotspot. The more retry threads, the higher the probability of CAS failure, thus entering the vicious CAS empty spin state. The basic idea of LongAdder is to disperse hotspots, disperse value values into an array, different threads will hit different slots (elements) of the array, and each thread only performs CAS operation on the value in its own slot. In this way, hot spots are dispersed, and the probability of conflict is much smaller. Using LongAdder, even if the number of threads is large, don’t worry. Each thread will be assigned to multiple elements to update. Increasing the number of elements can reduce the “heat” of value, and the vicious CAS empty spin in AtomicLong will be solved. If you want to obtain the complete value stored in LongAdder, you only need to accumulate the variable values in each slot and return the final accumulated value. The implementation idea of LongAdder is very similar to the basic principle of segment lock in ConcurrentHashMap. In essence, different threads operate on different units, which reduces thread competition and improves concurrency efficiency.

CAS advantages and disadvantages:

There are two main advantages of CAS:

  • It belongs to lock-free programming, and there is no heavyweight operation such as blocking and waking up threads.
  • There is no running switch between user mode and kernel mode in the process, and the process does not need to bear the overhead of frequent switching.

Disadvantages of CAS:

  • ABA problems. Solution: version number mechanism. JDK provides the AtomicStampedReference version number to solve the ABA problem. Stamp as version.
  • Only the atomic operation between one shared variable can be guaranteed. The way to avoid it is: combine multiple shared variables into one shared variable for operation. The evasion methods are combined into one object, and JDK provides the AtomicReference class to ensure the atomicity between referenced objects.
  • Invalid CAS will bring overhead problems. If spin CAS fails for a long time (unsuccessful, it will be executed in a loop until it succeeds), it will bring a very large execution overhead to the CPU.
Improve CAS performance
  • To disperse operation hotspots, use LongAdder to replace the basic atomic class AtomicLong. LongAdder disperses a single CAS hotspot (value value) into a cells array.
  • Use queue peak shaving to add threads with CAS contention to a queue to reduce the intensity of CAS contention. Spin is changed to queue queuing.