The introduction
We’ve talked about CAS a lot in our last article about the synchronized keyword in Java concurrency, but what exactly is CAS? In fact, in order to solve the thread safety problem caused by the parallel execution of multiple threads, we often use the locking mechanism to change the parallel execution of multiple threads into the serial execution of single threads. In fact, there is another way to avoid such problems. This scheme is quite different from the principle of synchronized keyword exclusion we analyzed before, and it actually uses a non-locking form of spin to solve the problem of thread safety. We is not hard to find in the previous analysis, when a thread to execute is decorated synchronized code/method, in order to avoid the operation of the Shared resource conflict, every time you need to perform locking strategy, and no lock is always assuming that access to Shared resources without conflict, thread can perform, no lock, without waiting for, but all things are difficult to work out, Is it true that a no-lock policy does not handle conflicts once they are found? No, the lockless policy uses a technology called CAS to ensure the security of thread execution, and this CAS technology is the key to the implementation of the lockless policy.
I. Landing executor without lock – CAS mechanism
The lockless strategy we’ve been talking about sounds great, but how does it work when it’s actually needed? The CAS mechanism is the implementation of our lock-free strategy. The full name of CAS is Compare And Swap. The CAS implementation in Java ultimately depends on the atomic instruction implementation of CPU (we will analyze later), And the core ideas of CAS mechanism are as follows:
CAS(V,E,N)
- V: shared variable to operate on
- E: Expected value
- N: the new value
If the value of V is equal to the value of E, then N is assigned to V. On the other hand, if V is not equal to E, it means that some other thread changed V before the current thread wrote back, and the current thread does nothing. Simple is when a thread to V need to make changes, in the first operation to save the current moment before share the value of a variable, when a thread operation after the completion of the need to write back to the new value again to get the latest first before the start of a variable’s value and operation of the preservation of the expected value, if there is no other threads to turn that same, then the current thread execution write operation. However, if the expected value does not match the value saved before the operation of the current thread, it means that the value has been modified by other threads. In this case, the update operation is not performed, but the variable can be read again and try to modify the variable again, or the operation can be abandoned, as shown in the following diagram:
Because the CAS operation are optimists, with each thread operation think they can succeed, when multiple threads at the same time use the CAS operation when a variable, only one will be successful execution and updated, the others all will fail, but fail threads will not be suspended, only to be told that failure, and allowed to try again, of course also allow threads to give up operation failure. Based on this principle, the CAS mechanism can know that other threads have performed operations on the shared resource even if there is no lock. At the same time, CAS has no lock in lock-free operation, so it is impossible for deadlocks to occur, so a conclusion can also be drawn:“CAS innate immunity deadlock”Because CAS itself is not locked.
1.1. CAS mechanism supported by the operating system
When multiple threads perform CAS operations at the same time, there will be security problems, causing inconsistencies. As we know from our above explanation that CAS operation is not performed in one step, but is also performed in multiple steps. Is it possible that the thread was switched and the value was changed when V and E were about to be assigned after judging that they were the same? The answer is very definite: NO, Why? Just I mentioned before the CAS mechanism in the Java ultimately is dependent on the CPU atomic instruction implementation, the CAS is a kind of operating system primitives category instructions, is made up of several instructions, to complete a process, a feature and primitive execution must be continuous, in the process of execution is not permitted to cut off, This means that CAS is an atomic instruction to the CPU and does not cause the so-called data inconsistency problem.
Unsafe is the Unsafe pointer class in Java
Unsafe class is located in the sun. The misc package, the Chinese translation is not the meaning of security, when we saw this class for the first time, we may be surprised, why there will be a class name in the JDK is named “Unsafe”, but you go to study in detail is not hard to find the wonders of this class, function is very powerful, But there is some insecurity. The Unsafe class, found in the Sun. misc package, has internal method operations that manipulate memory as directly as Pointers to C. The Unsafe class also indicates that it can manipulate memory as directly as Pointers to C:
- This class is not managed by the JVM, which means it cannot be GC, requiring us to manually free memory, which can leak when you do something with it
- The Unsafe class requires many methods to provide the original address (memory address) and the address of the object to be replaced. The offset must be calculated by the Unsafe class itself. A JVM crack-level error can cause an entire Java application to crash
However, directly manipulating memory via the Unsafe class also means that it is faster than normal Java programs, which is a great way to improve efficiency in the context of high concurrency. Therefore, despite the increased efficiency, Unsafe Pointers are also important in these aspects. The Unsafe class should not be used without special requirements when writing programs, and it is not officially recommended by Java (Unsafe does not provide a constructor), and Oracle originally planned to remove the Unsafe class from Java9. However, due to its extensive use in Java, Oracle did not remove the Unsafe class in Java. Instead, it only optimized and maintained the Unsafe class. Moreover, frameworks such as Netty also frequently use the Unsafe class in the underlying environment. Otherwise, there will be fewer excellent open source frameworks. Even though Unsafe, all methods in the Unsafe class are native, meaning that methods in the Unsafe class call the underlying operating system resources directly to perform their tasks.
- Class dependency: Provides a Class and its static field manipulation methods
- Info Related: Returns some low-level memory information
- Arrays: Provides Arrays manipulation methods
- Object dependency: Provides an Object and its domain manipulation methods
- Memory dependency: Provides direct Memory access (direct manipulation of local Memory bypassing the JVM heap)
- Synchronization related: provides low-level Synchronization primitives and thread suspend/drop manipulation methods
2.1. Memory management: The Unsafe class provides methods for manipulating memory directly
// Allocate memory Specifies the size of memory
public native long allocateMemory(long bytes);
// Reallocate memory of the specified size based on the given memory address setting
public native long reallocateMemory(long address, long bytes);
// Used to free memory applied by allocateMemory and reallocateMemory
public native void freeMemory(long address);
// Sets all bytes in the memory block at the given offset of the specified object to fixed values
public native void setMemory(Object o, long offset, long bytes, byte value);
// Set the value of the given memory address
public native void putAddress(long address, long x);
// Get the value of the specified memory address
public native long getAddress(long address);
// Set the long value of the given memory address
public native void putLong(long address, long x);
// Get the long value of the specified memory address
public native long getLong(long address);
// Sets or gets a byte value for the specified memory
public native byte getByte(long address);
public native void putByte(long address, byte x);
/ / other basic data types (long, char, and float, double, short, etc.) at the same operation with putByte and getByte. Omit code// The memory page size of the operating system
public native int pageSize(a);
Copy the code2.2. Object Instance Creation: The Unsafe class provides a new way to create object instances
Previously, the broadening class has two ways to create an object instance: new and reflection. However, both methods call the constructor to initialize the object. The broadening class offers the following new ways to create an object instance:
// Pass in the class of an object and create the instance object, but the constructor is not called
public native Object allocateInstance(Class cls) throws InstantiationException;
Copy the code2.3. Classes, Instance Objects, and variable Operations: The Unsafe class provides classes, instance objects, and variable manipulation methods
// Get the offset of field F in the instance object
public native long objectFieldOffset(Field f);
// Static property offset, used to read and write static properties in the corresponding Class object
public native long staticFieldOffset(Field f);
// Return f.declaringClass ()
public native Object staticFieldBase(Field f);
// Get the int value at the offset of the given object. The offset is simply a pointer to the memory address of the variable.
// The offset can be used to obtain the variable of the object for various operations
public native int getInt(Object o, long offset);
// Sets the int value of the offset on the given object
public native void putInt(Object o, long offset, int x);
// Get the value of the reference type at the offset of the given object
public native Object getObject(Object o, long offset);
// Sets the value of the reference type at the offset of the given object
public native void putObject(Object o, long offset, Object x);
/ / other basic data types (long, char, byte, float, double) at the same operation with getInthe and putInt
// Set the int value of the given object, using volatile semantics, that is, immediately updated to memory to be visible to other threads
public native void putIntVolatile(Object o, long offset, int x);
// Use volatile semantics to always obtain the latest int value.
public native int getIntVolatile(Object o, long offset);
/ / other basic data types (long, char, byte, float, double) in the operation and putIntVolatile
// Same as getIntVolatile, same as putObjectVolatile.. Omit codeAs with putIntVolatile, but the field being operated on must be volatile
public native void putOrderedInt(Object o,long offset,int x);
Copy the codeTo familiarize yourself with the broadening class, here’s a quick Demo: The Unsafe class does not provide a constructor. Although the Unsafe class does provide the getUnsafe() method, this method is only available to the Bootstrap class loader. Calls to the Unsafe class will throw exceptions. Therefore, in the following Demo, we use reflection techniques to retrieve and manipulate the Unsafe instance object.
public static Unsafe getUnsafe(a) {
Class cc = sun.reflect.Reflection.getCallerClass(2);
if(cc.getClassLoader() ! =null)
throw new SecurityException("Unsafe");
return theUnsafe;
}
Copy the codepublic class UnSafeDemo {
public static void main(String[] args) throws NoSuchFieldException, IllegalAccessException, InstantiationException {
// The Field object corresponding to theUnsafe is reflected
Field field = Unsafe.class.getDeclaredField("theUnsafe");
// Make the Field accessible
field.setAccessible(true);
// Get the object from the Field. Null is passed because the Field is static
Unsafe unsafe = (Unsafe) field.get(null);
System.out.println(unsafe);
// Create objects directly through allocateInstance
Demo demo = (Demo) unsafe.allocateInstance(Demo.class);
Class demoClass = demo.getClass();
Field str = demoClass.getDeclaredField("str");
Field i = demoClass.getDeclaredField("i");
Field staticStr = demoClass.getDeclaredField("staticStr");
// Get the offset of the instance variables STR and I in the object's memory and set the value
unsafe.putInt(demo,unsafe.objectFieldOffset(i),1);
unsafe.putObject(demo,unsafe.objectFieldOffset(str),"Hello Word!");
/ / return the User. The class
Object staticField = unsafe.staticFieldBase(staticStr);
System.out.println("staticField:" + staticStr);
// Get the offset staticOffset of the static variable staticStr
long staticOffset = unsafe.staticFieldOffset(userClass.getDeclaredField("staticStr"));
// Get the value of a static variable
System.out.println("Static value before setting :"+unsafe.getObject(staticField,staticOffset));
/ / set the value
unsafe.putObject(staticField,staticOffset,"Hello Java!");
// Get the static variable value again
System.out.println("Static value set :"+unsafe.getObject(staticField,staticOffset));
// Call toString
System.out.println("Output result:+demo.toString());
long data = 1000;
byte size = 1; // Unit byte
// call allocateMemory to allocateMemory and get memoryAddress memoryAddress
long memoryAddress = unsafe.allocateMemory(size);
// Write data directly to memory
unsafe.putAddress(memoryAddress, data);
// Get data for the specified memory address
long addrData = unsafe.getAddress(memoryAddress);
System.out.println("addrData:"+addrData);
/** * sun.misc.Unsafe@0f18aef2 staticField:class com.demo. Static values before demo setting :Demo_Static Values after demo setting :Hello Java! Output the USER: Demo {STR = 'Hello Word! ', i='1', staticStr='Hello Java! '} addrData:1000 */}}class Demo{
public Demo(a){
System.out.println("I am the constructor of the Demo class. I am called to create an object instance....");
}
private String str;
private int i;
private static String staticStr = "Demo_Static";
@Override
public String toString(a) {
return "Demo{" +
"str = '" + str + '\' ' +
", i = '" + i +'\' ' +
", staticStr = " + staticStr +'\' ' +
'} '; }}Copy the code2.4. Array operations: The Unsafe class provides a direct way to retrieve the memory location of array elements
// Get the offset address of the first element of the array
public native int arrayBaseOffset(Class arrayClass);
// The memory space occupied by an element in an array. ArrayBaseOffset is used with arrayIndexScale to locate each element in the array
public native int arrayIndexScale(Class arrayClass);
Copy the code2.4. Cas-related Operations: The Unsafe class supports CAS operations in Java
// The first parameter o is the given object, offset is the memory offset of the object, by which the field is quickly located and the value of the field is set or obtained.
// Expected indicates the expected value, and x indicates the value to be set. The following three methods all operate via CAS atomic instructions.
public final native boolean compareAndSwapObject(Object o, long offset,Object expected, Object x);
public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);
public final native boolean compareAndSwapLong(Object o, long offset,long expected,long x);
Copy the code2.5 methods based on the original CAS method are added after JDK8
// add a delta to the object o.
// This is a CAS operation that exits the loop until it is successfully set and returns the old value
public final int getAndAddInt(Object o, long offset, int delta) {
int v;
do {
// Get the latest value in memory
v = getIntVolatile(o, offset);
// The operation is performed through CAS
} while(! compareAndSwapInt(o, offset, v, v + delta));return v;
}
// add the same function as above, except that this operation operates on long data
public final long getAndAddLong(Object o, long offset, long delta) {
long v;
do {
v = getLongVolatile(o, offset);
} while(! compareAndSwapLong(o, offset, v, v + delta));return v;
}
// set the memory offset to newValue.
// This is a CAS operation that exits the loop until it is successfully set and returns the old value
public final int getAndSetInt(Object o, long offset, int newValue) {
int v;
do {
v = getIntVolatile(o, offset);
} while(! compareAndSwapInt(o, offset, v, newValue));return v;
}
// add a new type of long
public final long getAndSetLong(Object o, long offset, long newValue) {
long v;
do {
v = getLongVolatile(o, offset);
} while(! compareAndSwapLong(o, offset, v, newValue));return v;
}
//1.8 add, same as above, operate on reference type data
public final Object getAndSetObject(Object o, long offset, Object newValue) {
Object v;
do {
v = getObjectVolatile(o, offset);
} while(! compareAndSwapObject(o, offset, v, newValue));return v;
}
Copy the codeIf you have seen the source code of the JDK8 Atomic package, you should also see them.
2.6. Threading Operations: The Unsafe class supports thread suspension and recovery operations
Suspending a thread is done with the park method, which blocks the thread until a timeout or interrupt occurs. Unpark can terminate a suspended thread and restore it to normal. The suspension of Java threads is encapsulated in the LockSupport class, which has various versions of the pack methods, and the underlying implementation is ultimately implemented using the unsafe.park () and unsafe.unpark () methods.
// The thread calls this method and blocks until it times out or an interrupt condition occurs.
public native void park(boolean isAbsolute, long time);
Java.util.concurrent the suspension operations in the java.util.concurrent package are implemented in the LockSupport class, which uses these two methods at the bottom.
public native void unpark(Object thread);
Copy the code2.7 memory barriers: mentioned in the previous articleJMM, instruction reorderingSuch operations as memory barrier definition support
// All reads before this method must be executed before the load barrier
public native void loadFence(a);
// All writes before this method must be executed before the Store barrier
public native void storeFence(a);
// All read and write operations before this method must be performed before the full barrier, which is equivalent to the above two functions combined
public native void fullFence(a);
Copy the code2.8 Other operations: Please refer to more operationsJDK8 official API documentation
// Get hold lock. It is not recommended
@Deprecated
public native void monitorEnter(Object var1);
// Release the lock. It is not recommended
@Deprecated
public native void monitorExit(Object var1);
// Try to obtain the lock. It is not recommended
@Deprecated
public native boolean tryMonitorEnter(Object var1);
// Get the number of pages in native memory, which is always a power of 2
public native int pageSize(a);
// Tell the virtual machine that a class is defined without security checks. By default, the classloader and the protected domain are called by the caller class
public native Class defineClass(String name, byte[] b, int off, int len, ClassLoader loader, ProtectionDomain protectionDomain);
// Load an anonymous class
public native Class defineAnonymousClass(Class hostClass, byte[] data, Object[] cpPatches);
// Determine if a class needs to be loaded
public native boolean shouldBeInitialized(Class
c);
// Make sure the class is loaded
public native void ensureClassInitialized(Class
c);
Copy the codeAtomic operation package of J.U.C
Unlockable CAS, unlockable magic, and Unsafe are the basic requirements for atomic packages. Therefore, CAS applications in Java are discussed step by step. JDK5 after launch in the process of contract awarding JUC and provides Java. Util. Concurrent. Package, atomic atoms under the package provides a number of atomic operations based on CAS implementation classes, such as later don’t want to code lock but still want to avoid thread safety problem, so you can use this package provides classes, The operation classes provided by atomic packages can be divided into the following four types:
- Base type atomic operation class
- Reference type atomic operation class
- Array type atomic operation class
- Property updates atomic action class
3.1 Basic type Atomic operation class
Atomic package provides AtomicInteger, AtomicBoolean and AtomicLong for basic types of Atomic operation classes. Their low-level implementation and use methods are consistent, so we only analyze one AtomicInteger as an example. AtomicInteger performs atomic operations on data of type INT. AtomicInteger provides API for atomic increment, atomic decrement, and atomic assignment.
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// Get the instance of the pointer class Unsafe
private static final Unsafe unsafe = Unsafe.getUnsafe();
// The memory offset of the variable value within the AtomicInteger instance object
private static final long valueOffset;
static {
try {
// Retrieve the offset of the value variable in the object memory using the unsafe class objectFieldOffset() method
// With valueOffset, the unsafe class's internal method can retrieve the value variable to evaluate or assign to
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw newError(ex); }}// The current AtomicInteger encapsulates the int variable value
private volatile int value;
public AtomicInteger(int initialValue) {
value = initialValue;
}
public AtomicInteger(a) {}// Get the current latest value,
public final int get(a) {
return value;
}
// Set the current value, volatile, and final to further ensure thread-safety
public final void set(int newValue) {
value = newValue;
}
// Will eventually be set to newValue, which may cause other threads to retrieve the old value for a short time later, similar to lazy loading
public final void lazySet(int newValue) {
unsafe.putOrderedInt(this, valueOffset, newValue);
}
Unsafe.com pareAndSwapInt(); // Set the new value and get the old value
public final int getAndSet(int newValue) {
return unsafe.getAndSetInt(this, valueOffset, newValue);
}
// If the current value is expect, set to update(the current value refers to the value variable)
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
// The current value increases by 1, and the old value is returned
public final int getAndIncrement(a) {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
// The current value is subtracted by 1, and the old value is returned
public final int getAndDecrement(a) {
return unsafe.getAndAddInt(this, valueOffset, -1);
}
// Add delta to current value, return old value, bottom CAS operation
public final int getAndAdd(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta);
}
// The current value increases by 1 and returns the new value, the underlying CAS operation
public final int incrementAndGet(a) {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
// The current value is subtracted by 1 and the new value is returned
public final int decrementAndGet(a) {
return unsafe.getAndAddInt(this, valueOffset, -1) - 1;
}
// Add delta to current value, return new value, bottom CAS operation
public final int addAndGet(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
}
// omit some unusual methods....
}
Copy the codeThe AtomicInteger atomic class doesn’t use any mutex mechanisms for synchronization. Instead, it uses the CAS operations provided by the Unsafe class to ensure thread-safety. The AtomicInteger atomic class increments with incrementAndGet:
public final int incrementAndGet(a) {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
Copy the codeThe unsafe.getAndAddInt() method is called, and the unsafe.getAndAddInt() method is a new cas method after the unsafe.cas operation.
public final int getAndAddInt(Object o, long offset, int delta) {
int v;
do {
v = getIntVolatile(o, offset);
} while(! compareAndSwapInt(o, offset, v, v + delta));return v;
}
Copy the codeThe Unsafe class calls getAndAddInt, a CAS operation, to update the value through a do while loop until it succeeds. The Unsafe class calls the compareAndSwapInt method. Note: Java8’s prior source implementation of the for loop, which was implemented directly in the AtomicInteger class, was replaced by while and moved to the Unsafe class. Let’s use a simple demo to learn how to use atomic operation classes of basic types:
public class AtomicIntegerDemo {
// Create the shared variable atomicI
static AtomicInteger atomicI = new AtomicInteger();
public static class AddThread implements Runnable{
public void run(a){
for(int i = 0; i < 10000; i++) atomicI.incrementAndGet(); }}public static void main(String[] args) throws InterruptedException {
Thread[] threads = new Thread[10];
// Enable 5 threads to perform atomicI increment at the same time
for(int i = 1; i <= 5; i++){
threads[i]=new Thread(new AddThread());
}
// Start the thread
for(int i = 1; i <= 5; i++){threads[i].start(); }for(int i = 1; i <= 5; i++){threads[i].join();}
System.out.println(atomicI);
}
}
// Output :50000
Copy the codeIn the demo above, we used AtomicInteger instead of int, so that we can keep the thread safe without locking. AtomicBoolean and AtomicLong will no longer be analyzed. The usage and principle are the same.
3.2. Reference type Atomic operation class
AtomicReference AtomicReference AtomicReference AtomicReference AtomicReference AtomicReference AtomicReference AtomicReference AtomicReference
public class AtomicReferenceDemo {
public static AtomicReference<Student> atomicStudentRef = new AtomicReference<Student>();
public static void main(String[] args) {
Student s1 = new Student(1."Bamboo");
atomicStudentRef.set(s1);
Student s2 = new Student(2."Panda");
atomicStudentRef.compareAndSet(s1, s2);
System.out.println(atomicStudentRef.get().toString());
Student{id=2, name=" panda "}
}
static class Student {
private int id;
public String name;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
public String getName(a) {
return name;
}
@Override
public String toString(a) {
return "Student{" +"id=" + id +", name=" + name +"}"; }}}Copy the codeThe unaddressed atomic counter (AtomicInteger) is a CAS operation in its Unsafe class. The unaddressed atomic counter (AtomicInteger) is a CAS operation in its Unsafe class.
public class AtomicReference<V> implements java.io.Serializable {
// Get the unsafe object instance
private static final Unsafe unsafe = Unsafe.getUnsafe();
// Define the value offset
private static final long valueOffset;
static {
try {
/* Static code blocks assign values to offsets during class loading. The address API provided by the broadening class gets the address of the current class definition value */
valueOffset = unsafe.objectFieldOffset
(AtomicReference.class.getDeclaredField("value"));
} catch (Exception ex) { throw newError(ex); }}// The Unsafe class uses the valueOffset memory offset to obtain the value
private volatile V value;
/* Atomic substitution method, which indirectly calls the Unsafe class compareAndSwapObject(), a native method that implements CAS operations */
public final boolean compareAndSet(V expect, V update) {
return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
}
// Set and get the old value
public final V getAndSet(V newValue) {
return (V)unsafe.getAndSetObject(this, valueOffset, newValue);
}
// omit the code......
}
// Unsafe. the getAndSetObject method in the Unsafe class is still the CAS operation
public final Object getAndSetObject(Object o, long offset, Object newValue) {
Object v;
do {
v = getObjectVolatile(o, offset);
} while(! compareAndSwapObject(o, offset, v, newValue));return v;
}
Copy the codeAtomicReference is implemented in much the same way as the AtomicInteger implementation, which is ultimately implemented through CAS operations in the Unsafe class. Other methods for implementing AtomicReference are also implemented in much the same way. Just note that Java8 adds several new apis to AtomicReference:
- getAndUpdate(UnaryOperator)
- updateAndGet(UnaryOperator)
- getAndAccumulate(V,AnaryOperator)
- accumulateAndGet(V,AnaryOperator)
The above methods exist in almost all atomic classes, and these methods can perform the CAS operation based on the Lambda expression on the passed expected value or the value to be updated. To simplify, the CAS update can be performed after the expected value or the value to be updated is additional modified.
Array type atomic operation class
When we first got to know the array we learned from Java, there would be thread-safety problems when we operated on its elements. However, the meaning of our array atomic operation class is actually very simple, which means to update the elements in the array in the form of atoms to avoid thread-safety problems. The atomic operation class of array type in JUC package can be divided into the following three classes:
- AtomicIntegerArray: Atom updates elements in an integer array
- AtomicLongArray: Atom updates elements in an array of long integers
- AtomicReferenceArray: The atom updates the element in the array of reference types
AtomicIntegerArray AtomicIntegerArray AtomicIntegerArray AtomicIntegerArray
public class AtomicIntegerArrayDemo {
static AtomicIntegerArray atomicArr = new AtomicIntegerArray(5);
public static class incrementTask implements Runnable{
public void run(a){
// Increments the array element with index
for(int i = 0; i < 10000; i++) atomicArr.getAndIncrement(i % atomicArr.length()); }}public static void main(String[] args) throws InterruptedException {
Thread[] threads = new Thread[5];
for(int i = 0; i < 5; i++) threads[i] =new Thread(new incrementTask());
for(int i = 0; i < 5; i++) threads[i].start();for(int i = 0; i < 5; i++) threads[i].join(); System.out.println(atomicArr);/* Result: [10000, 10000, 10000, 10000, 10000] */}}Copy the codeIn the previous Demo, we started five threads to increment the elements in the array, and the results were as we expected. So we next step to analyze AtomicIntegerArray internal implementation logic, the source code is as follows:
public class AtomicIntegerArray implements java.io.Serializable {
// Get the Unsafe instance object
private static final Unsafe unsafe = Unsafe.getUnsafe();
// Unsafe. arrayBaseOffset() returns the address of the first element of an array
private static final int base = unsafe.arrayBaseOffset(int[].class);
private static final int shift;
// Internal array
private final int[] array;
static {
// Get the memory space occupied by an element in the array
int scale = unsafe.arrayIndexScale(int[].class);
// Check whether it is the power of 2, usually the power of 2 otherwise throw exception
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
//
shift = 31 - Integer.numberOfLeadingZeros(scale);
}
private long checkedByteOffset(int i) {
if (i < 0 || i >= array.length)
throw new IndexOutOfBoundsException("index " + i);
return byteOffset(i);
}
// Compute the memory address of each element in the array
private static long byteOffset(int i) {
return ((long) i << shift) + base;
}
// omit the code......
}
Copy the codeIn our previous broadening analysis, we learned that arrayBaseOffset retrieves the memory starting position of the first element in an array, and we have another API: ArrayIndexScale can be used to determine the size of the specified subscript element in the array. AtomicIntegerArray is currently an int. When we learn the basics of Java, we learned that the size of int in memory is 4Byte (byte), so the value of scale is 4. So now what if we calculate the starting memory address of each element in the array based on these two pieces of information? After a little deduction, we can come to the following conclusion:
The initial memory location of each element in the array = the initial memory location of the first element in the array + the subscript of the array elements * The size of the memory used by each element in the array
The byteOffset(I) method in the above source code is the embodiment of the formula described above. One might see some confusion here, as the implementation of this method seems to differ from the conclusion I just described. Let’s take a look at where the shift value comes from:
shift = 31 – Integer.numberOfLeadingZeros(scale);
Integer. NumberOfLeadingZeros (scale) : Calculate the number of leading zeros of scale (the number of consecutive zeros after converting to binary is called the derivative of leading zeros), scale=4, when converting to binary is 00000000 00000000 00000000 00000100, so the derivative of leading zeros is 29, so the shift value is 2.
So our initial question: how do we calculate the starting memory location of each element in the array? We use our just-obtained shift value to insert byteOffset(I) to calculate the starting memory position of each element in the array (if the array subscript is within bounds) :
ByteOffset :(I << shift) + base (I = index, base = first element)
First element: memoryAddress = 0 << 2 + base MemoryAddress = 1 << 2 + base = memoryAddress + 1 * 4 MemoryAddress = 2 << 2 + base; memoryAddress = base + 2 * 4 MemoryAddress = 3 << 2 + Base memoryAddress = Base + 3 * 4 and so on…….
As this is AtomicIntegerArray byteOffset method principle. So the byteOffset(int) method can calculate the memory address of each element based on the array subscript. The other AtomicIntegerArray methods implicitly call the CAS atomic operation method of the Unsafe class. Here’s a quick look at some of the most popular methods:
// Perform the increment operation, return the old value, the input parameter I is index is the array element index
public final int getAndIncrement(int i) {
return getAndAdd(i, 1);
}
// Specifies that the subscript element increments and returns a new value
public final int incrementAndGet(int i) {
return getAndAdd(i, 1) + 1;
}
// Specify subscript elements to decrement and return new values
public final int decrementAndGet(int i) {
return getAndAdd(i, -1) - 1;
}
// Call unsafe.getAndAddInt() indirectly
public final int getAndAdd(int i, int delta) {
return unsafe.getAndAddInt(array, checkedByteOffset(i), delta);
}
// The Unsafe class getAndAddInt method, which performs the CAS operation
public final int getAndAddInt(Object o, long offset, int delta) {
int v;
do {
v = getIntVolatile(o, offset);
} while(! compareAndSwapInt(o, offset, v, v + delta));return v;
}
Copy the codeThe principles of AtomicReferenceArray and AtomicLongArray are not described.
3.4. Attribute update atomic operation class
If we just need a field of a class (class attribute) into atomic operation is also to make a normal variable into atomic operation, also can use the attribute update atomic operations, such as project needs changes in some time, as a direct result of a class does not need to involve multithreading operating a property before you need to perform multithreaded operations, because the attribute is used by many when encoding, The code is highly intrusive and complex to change, and there is no need to consider thread safety when using this attribute in previous code. As long as new scenarios need to be guaranteed, atomic updater can handle such scenarios. The J.U.C. Attomic Concurrent atomic package provides the following three classes:
- AtomicIntegerFieldUpdater: update the integer property of atomic operations
- AtomicLongFieldUpdater: Atomic action class that updates long integer properties
- AtomicReferenceFieldUpdater: update the properties of atoms in the reference type action class
It is worth noting, however, that the conditions for using atoms to update classes are more stringent, as follows:
- Fields of operations cannot be modified static
- Fields of an operation cannot be modified by final because constants cannot be modified
- The fields of the operations must be volatile to ensure visibility, meaning that the data read is visible to the thread
- Property must be visible to the region where the current Updater is located. The private, protected modifier cannot be used unless atomic Updater operations are performed inside the current class. The modifier must be protected and above when a subclass operates on its parent class, or default and above if it is in the same package, which means that visibility between the class being operated on and the class being operated on should always be guaranteed.
Here’s a simple little Demo to feel it:
public class AtomicIntegerFieldUpdaterDemo{
// Define the atomic operation class that updates the attributes of an integer. The target attribute is: Course. CourseScore
static AtomicIntegerFieldUpdater<Course> courseAIFU =
AtomicIntegerFieldUpdater.newUpdater(Course.class, "courseScore");
// Define the atomic action class that updates the attribute in the reference type, with the target attribute: student.studentName
static AtomicReferenceFieldUpdater<Student,String> studentARFU =
AtomicReferenceFieldUpdater.newUpdater(Student.class,String.class,"studentName");
// Define the accuracy of atomic counter effect data
public static AtomicInteger courseScoreCount = new AtomicInteger(0);
public static void main(String[] args) throws Exception{
final Course course = new Course();
Thread[] threads = new Thread[1000];
for(int i = 0; i <1000; i++){ threads[i] =new Thread(()->{
if(Math.random()>0.6){ courseAIFU.incrementAndGet(course); courseScoreCount.incrementAndGet(); }}); threads[i].start(); }for(int i = 0; i <1000; i++) threads[i].join(); System.out.println("Course. CourseScore:" + course.courseScore);
System.out.println("Data effect result:" + courseScoreCount.get());
// Update the atomic operation class demo for attributes in reference types
Student student = new Student(1."Bamboo");
studentARFU.compareAndSet(student,student.studentName,"Panda");
System.out.println(student.toString());
}
public static class Course{
int courseId;
String courseName;
volatile int courseScore;
}
public static class Student{
int studentId;
volatile String studentName;
public Student(int studentId,String studentName){
this.studentId = studentId;
this.studentName = studentName;
}
@Override
public String toString(a) {
return "Student[studentId="+studentId+"studentName="+studentName+"]"; }}}Student[studentId=1studentName= panda] **/
Copy the codeFrom the code above, there are two internal static classes: Course as well as Student, we use AtomicIntegerFieldUpdater role in the Course. The courseScore attributes, Using AtomicReferenceFieldUpdater role in Student. StudentName. Article one thousand in the code above, we open the thread by using the Boolean operation, use AtomicInteger define counter courseScoreCount efficacy data, its purpose lies in efficacy AtomicIntegerFieldUpdater can ensure thread safety problem. If a random number greater than 0.6 is read on the open thread, the score will be recorded in Course. CourseScore, and then courseScoreCount increment will be performed for subsequent data verification. CourseScoreCount results are in agreement with the final result output Course. CourseScore results, also represents AtomicIntegerFieldUpdater correctly update Course. CourseScore value can ensure thread safety problem. For AtomicReferenceFieldUpdater we in the code above simple way of writing the demo demonstrates its use, when we were in the use of AtomicReferenceFieldUpdater worthy of note is the need to two generic parameters, One is the class object of the modified class and the other is the class object of the modified Field. As for the other AtomicLongFieldUpdater is not shown, use way and the AtomicIntegerFieldUpdater roughly the same. At this point, we study the implementation principle of AtomicIntegerFieldUpdater again, on the first code:
public abstract class AtomicIntegerFieldUpdater<T> {
public static <U> AtomicIntegerFieldUpdater<U> newUpdater(Class tclass, String fieldName){
return newAtomicIntegerFieldUpdaterImpl<U> (tclass, fieldName, Reflection.getCallerClass()); }}Copy the codeFrom the source is not hard to find, in fact AtomicIntegerFieldUpdater is defined as an abstract class, final implementation class for AtomicIntegerFieldUpdaterImpl, further follow-up AtomicIntegerFieldUpdaterImpl:
private static class AtomicIntegerFieldUpdaterImpl<T>
extends AtomicIntegerFieldUpdater<T> {
// Get the unsafe instance
private static final Unsafe unsafe = Unsafe.getUnsafe();
// Define the memory offset
private final long offset;
private final Class<T> tclass;
private finalClass<? > cclass;// constructor
AtomicIntegerFieldUpdaterImpl(final Class<T> tclass,
final String fieldName,
finalClass<? > caller) {final Field field;// The field to be modified
final int modifiers;// Field modifiers
try {
field = AccessController.doPrivileged(
new PrivilegedExceptionAction<Field>() {
public Field run(a) throws NoSuchFieldException {
// Get the field object by reflection
returntclass.getDeclaredField(fieldName); }});// Get the field modifier
modifiers = field.getModifiers();
// Check the access permission of the field, do not throw exceptions in the access scope
sun.reflect.misc.ReflectUtil.ensureMemberAccess(
caller, tclass, null, modifiers);
// Get the class loader for the corresponding class object
ClassLoader cl = tclass.getClassLoader();
ClassLoader ccl = caller.getClassLoader();
if((ccl ! =null) && (ccl ! = cl) && ((cl ==null) || !isAncestor(cl, ccl))) {
sun.reflect.misc.ReflectUtil.checkPackageAccess(tclass);
}
} catch (PrivilegedActionException pae) {
throw new RuntimeException(pae.getException());
} catch (Exception ex) {
throw newRuntimeException(ex); } Class<? > fieldt = field.getType();// Check whether it is an int
if(fieldt ! =int.class)
throw new IllegalArgumentException("Must be integer type");
// Determine whether it is volatile
if(! Modifier.isVolatile(modifiers))throw new IllegalArgumentException("Must be volatile type");
this.cclass = (Modifier.isProtected(modifiers) && caller ! = tclass) ? caller :null;
this.tclass = tclass;
// Get the memory offset of the field. You can get or modify the value of the field by using the memory offsetoffset = unsafe.objectFieldOffset(field); }}Copy the codeIt is not hard to see from AtomicIntegerFieldUpdaterImpl source fields actually updater is through reflection mechanism + Unsafe class implements, see the increase in AtomicIntegerFieldUpdaterImpl method incrementAndGet implementation:
public int incrementAndGet(T obj) {
int prev, next;
do {
prev = get(obj);
next = prev + 1;
// Call the compareAndSet method below to complete the CAS operation
} while(! compareAndSet(obj, prev, next));return next;
}
// The Unsafe class also calls the compareAndSwapInt() method
public boolean compareAndSet(T obj, int expect, int update) {
if (obj == null|| obj.getClass() ! = tclass || cclass ! =null) fullCheck(obj);
return unsafe.compareAndSwapInt(obj, offset, expect, update);
}
Copy the codeThe Unsafe class is also used to implement Atomic Atomic packages in J.U.C., and many of the concurrent knowledge discussed later, such as AQS, involves CAS.
4. The problem of CAS no lock
4.1 ABA problems of CAS
When the first thread CAS (V, E, N) operation, in access to the current variable V, to change before the new value N, the other two threads have been modified for twice the value of the variable V makes the value back to the first thread to see the original value, so, we will not be able to correctly judge whether the variable has been modified, and a simple example: Threads T1,T2,T3 share atomicI=0. When the first thread T1 tries to change atomicI to 1, the T1 thread sees the value of 1 and reads atomicI=1 back to the working memory. However, during the operation of T1 thread, the T2 thread updates the value to 1. Then T3 thread changes atomicI to 0. At this time, T1 cannot know that this value has been changed by other threads when it comes back for update. When V==E judgment is made and atomicI is still the original value, atomicI will be changed. But the scene is different now than when the T1 thread first saw the value. The diagram below:
As above problems existing in the mechanism of this example is the CAS, the probability that normally occur is very small, and even the general business don’t cause any problems, such as the example above, even if the ABA problem will not impact, because will not affect the eventual consistency of data, expected value of the T1 thread itself to 1, even if the ABA problem, The value of the T1 thread is still 1. However, there are some cases where you need to avoid this kind of problem, such as a one-way linked list implementation stack stack as follows:
As shown in the figure above, at this time, the top element on the stack is A, at this time, thread T1 already knows that A. ext is element B, and hopes to replace the top element on the stack with B through CAS mechanism, as follows:
stackHead.compareAndSet(A,B);
When thread T1 executes this line of code, thread T2 intervenes. Thread T2 pushes A and B off the stack, and then pushes elements Y, X, and A onto the stack. At this point, elements Y, X, and A are in the stack, and element B is isolated, as shown in the diagram below:
At this moment, thread T1 performs CAS write back operation, and the detection finds that the top of stack is still A, so CAS succeeds and the top of stack is changed to B, but actually B.ext is null, so the situation is changed to:
There are only B elements in the stack, and Y and X elements no longer exist in the stack, but it is true that the T2 thread did Y and X on the stack, but dropped X and Y for no reason.
All in all, ABA problems need to be solved as long as there are actions that need to be made based on dynamic changes in the scene, but if your application only makes decisions based on the data surface, then ABA problems can be ignored.
4.2 CAS ABA solution
So when we have this kind of problem and we need to pay attention to how to solve it? When implementing optimistic locks in other forms, we usually mark them with the version version number to avoid concurrency problems. In Java, there are two main solutions to the ABA problem of CAS:
- AtomicStampedReference: Timestamp control, fully resolved
- AtomicMarkableReference: Maintains Boolean control, not completely eliminated
2, AtomicStampedReference
An AtomicStampedReference is an object reference with a time stamp. It stores data and a time stamp in a key-value Pair. During each update, the data is compared with the time stamp. The Unsafe compareAndSwapObject method is called only if both match the expected values. Of course, the AtomicStampedReference not only sets the new value but also records the time stamp of the change. This solves the ABA problem caused by the previous CAS mechanism. Here’s a simple example:
public class ABAIssue {
// Define atomic counter with initial value = 100
private static AtomicInteger atomicI = new AtomicInteger(100);
// Define AtomicStampedReference: An initial value and an initial time are passed during initialization
private static AtomicStampedReference<Integer> asRef = new AtomicStampedReference<Integer>(100.0);
/** * No AtomicStampedReference Thread group: TA TB */
private static Thread TA = new Thread(() -> {
System.err.println("No AtomicStampedReference Thread group: [TA TB] >>>>");
// Update the value to 101
boolean flag = atomicI.compareAndSet(100.101);
System.out.println("Thread TA: 100 -> 101.... flag:" + flag + ", atomicINewValue:" + atomicI.get());
// Update the value to 100
flag = atomicI.compareAndSet(101.100);
System.out.println("Thread TA: 101 -> 100.... flag:" + flag + ", atomicINewValue:" + atomicI.get());
});
private static Thread TB = new Thread(() -> {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean flag = atomicI.compareAndSet(100.888);
System.out.println("Thread TB: 100 -> 888.... flag:" + flag + ", atomicINewValue:" + atomicI.get() + "\n\n");
});
/** * AtomicStampedReference Thread group: T1 T2 */
private static Thread T1 = new Thread(() -> {
System.err.println("Use AtomicStampedReference Thread Group: [T1 T2] >>>>");
// Update the value to 101
boolean flag = asRef.compareAndSet(100.101, asRef.getStamp(), asRef.getStamp() + 1);
System.out.println("Thread T1:100 -> 101.... flag:" + flag + "... asRefNewValue:" + asRef.getReference() + "... Current Time:" + asRef.getStamp());
// Update the value to 100
flag = asRef.compareAndSet(101.100, asRef.getStamp(), asRef.getStamp() + 1);
System.out.println("Thread T1:101 -> 100.... flag:" + flag + "... asRefNewValue:" + asRef.getReference() + "... Current Time:" + asRef.getStamp());
});
private static Thread T2 = new Thread(() -> {
int time = asRef.getStamp();
System.out.println(Time value before thread sleep: + time);
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean flag = asRef.compareAndSet(100.888, time, time + 1);
System.out.println("Thread T2:100 -> 888.... flag:" + flag + "... asRefNewValue:" + asRef.getReference() + "... Current Time:" + asRef.getStamp());
});
public static void main(String[] args) throws InterruptedException { TA.start(); TB.start(); TA.join(); TB.join(); T1.start(); T2.start(); }}/** * AtomicStampedReference Thread group: [TA TB] >>>> * Thread TA: 100 -> 101.... Flag: true, atomicINewValue: thread TA: 101 * 101 - > 100... Flag: true, atomicINewValue: 100 * thread TB: 100 - > 888... Flag: true, atomicINewValue: 888 * * * using AtomicStampedReference thread group: [T1 T2] > > > > * thread before sleep Time values: 0 * thread T1:100 - > 101... flag:true.... asRefNewValue:101.... Current Time: 1 * Thread T1:101 -> 100.... flag:true.... asRefNewValue:100.... Current Time: 2 * threads T2:100 -> 888.... flag:false.... asRefNewValue:100.... Current Time: 2 */
Copy the codeBy observing the test results of AtomicInteger and AtomicStampedReference in the Demo above, we can see that AtomicStampedReference can indeed solve the ABA problem we described earlier. So how exactly does AtomicStampedReference have ABA problems? Let’s look at its internal implementation:
public class AtomicStampedReference<V> {
// Data and timestamps are stored by Pair internal classes
private static class Pair<T> {
final T reference;
final int stamp;
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
static <T> Pair<T> of(T reference, int stamp) {
return newPair<T>(reference, stamp); }}// An inner class that stores values and times
private volatile Pair<V> pair;
// Initializers: pass in initializers and time initializers
public AtomicStampedReference(V initialRef, int initialStamp) { pair = Pair.of(initialRef, initialStamp); }}Copy the codeCompareAndSet method source code implementation:
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}
// The final implementation calls the compareAndSwapObject() method of the Unfase class
private boolean casPair(Pair<V> cmp, Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}
Copy the codeIn compareAndSet method source code implementation we are not difficult to find, it is both the current data and the current time comparison, only if both are equal will execute casPair() method, and casPair() method is also an atomic method, Again, the Unsafe class calls the compareAndSwapObject() method.
4.2.2, AtomicMarkableReference
AtomicMarkableReference is different from the AtomicStampedReference we discussed before. AtomicStampedReference can only reduce the occurrence of ABA problems to a certain extent, but cannot completely eliminate ABA problems. An AtomicStampedReference maintains a Boolean id, which means that the time stamp inside your AtomicStampedReference does not increase in value. The inside of AtomicStampedReference is a Boolean, meaning that only true and false states are switched back and forth, so there is still an ABA problem. Let’s start with a demo:
public class ABAIssue {
static AtomicMarkableReference<Integer> amRef = new AtomicMarkableReference<Integer>(100.false);
private static Thread t1 = new Thread(() -> {
boolean mark = amRef.isMarked();
System.out.println("Thread T1: flag before modification Mrak:" + mark + "...");
// Update the value to 200
System.out.println("Thread T1:100 --> 200.... Result:" + amRef.compareAndSet(amRef.getReference(), 200, mark, ! mark)); });private static Thread t2 = new Thread(() -> {
boolean mark = amRef.isMarked();
System.out.println("Thread T2: flag before modification Mrak:" + mark + "...");
// Update the value back to 100
System.out.println("Thread T2:200 --> 100.... Result:" + amRef.compareAndSet(amRef.getReference(), 100, mark, ! mark)); });private static Thread t3 = new Thread(() -> {
boolean mark = amRef.isMarked();
System.out.println("Thread T3: flag before sleep Mrak:" + mark + "...");
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean flag = amRef.compareAndSet(100.500, mark, ! mark); System.out.println("Thread T3:100 --> 500.... flag:" + flag + ",newValue:" + amRef.getReference());
});
public static void main(String[] args) throws InterruptedException {
t1.start();
t1.join();
t2.start();
t2.join();
t3.start();
* Thread T1: flag before modification Mrak:false.... * Thread T1:100 --> 200.... Value returned after modification Result:true * Thread T2: flag before modification Mrak:true.... * Thread T2:200 --> 100.... Result:true * Thread T3: flag before hibernation Mrak:false.... * Thread T3:100 --> 500.... flag:true,newValue:500 */
/* The result of the t3 thread is still successfully updated to 500, indicating that the changes made by t1 and T2 threads are still invisible to T3 thread */}}Copy the codeFrom the above demo, we can find that the use of AtomicMarkableReference has not really prevented the occurrence of ABA problems. Then we will not explain the principle of AtomicMarkableReference (roughly the same as AtomicStampedReference).
We know from the previous discussion on ABA that AtomicMarkableReference can reduce the incidence of ABA problems to a certain extent, but cannot completely eliminate them. If we want to avoid ABA problems completely, we need to use AtomicStampedReference.
5. CAS unlocked spin
At the beginning of this article we have talked about the initial concept of lock free, in fact, the concept of lock free is also mentioned in our last article: analysis of the principle of Synchronized keyword escalation expansion process. Without lock also in some places is called a spin lock, spin is a kind of competition if there is a thread, but the logic thread here very fast and some didn’t get to the resource (number) threads can also access to resources and perform in the soon future, OS let no access to the resources of threads to execute a few empty cycle operating waiting for resources. Spinning is also efficient because the spin lock only logically blocks the thread and stops execution in user mode. It does not actually suspend the corresponding kernel thread in kernel mode, thus reducing the amount of resources used by the kernel to suspend/drop the thread. However, the problem is that when there are more and more threads and the competition is intense, the CPU usage becomes longer and performance deteriorates dramatically. Therefore, Java virtual machines generally have a certain number of spin locks, which may be abandoned after 50 or 100 cycles, and the OS directly suspends the kernel thread to free up CPU resources.
6. Reference materials and books
- Deep Understanding of the JVM VIRTUAL Machine
- The Beauty of Concurrent Programming in Java
- Java High Concurrency Programming
- Core Technology of Website Architecture with 100 million Traffic
- Java Concurrent Programming