Write in front:
The content of this article is summarized through personal arrangement and reference to relevant materials, and some mistakes will inevitably occur
If there is an error, please point it out in the comments! thank you
1 CAS
We usually familiar with lock concurrency is the typical representative of the synchronize, concurrent execution process through the keyword can control one and only one thread can access to a Shared resource, its principle by the current thread holds the lock the current object, thus have access, and other don’t hold the thread of object lock cannot have access, This ensures thread safety
But we’re going to look at another concurrency strategy that works the other way around: lockless concurrency, which ensures program concurrency without locking
1.1 no lock
When talking about the concept of no lock, optimists and pessimists are always associated. For optimists, they believe that things will always develop in a good direction, and they always think that the probability of bad situation is very low, so they can do things without hesitation. But for the pessimists, they always think that if the development is not controlled in time, it will be irreversible, even if the irreversible situation is almost impossible to happen
The mapping of these two factions to concurrent programming is analogous to locking and no-lock strategies, in that locking is a pessimistic strategy and no-lock is an optimistic strategy. Because locked concurrent programs assume that a conflict will occur every time they access a shared resource, they must implement a locking policy for every data operation. However, without lock, it is always assumed that there is no conflict of access to the shared resource, and the thread can keep executing without locking or waiting. Once a conflict occurs, the no-lock policy adopts a CAS technology to ensure the security of thread execution
1.2 Unlocked executor -CAS
1.2.1 the CAS
The full name of CAS is Compare And Swap, And the core idea of its algorithm is:
Execute function: CAS(V,E,N)
There are three parameters:
- V represents the variable to be updated
- E is the expected value
- N indicates the new value
If the value of V is equal to the value of E, set the value of V to N. If the value of V is different from the value of E, it indicates that the update has been made by another thread, and the current thread does not change
When the value of the expected value is the same as the variable value of the current thread, it indicates that no thread has operated on the value. The current thread can modify the value, and then the CAS operation can be performed. If the expected value is different from the variable value of the current thread, it indicates that the value has been modified by another thread. 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. The schematic diagram is as follows:
Because the CAS operation are optimists, it always think they can successfully complete the operation, when multiple threads at the same time use the CAS operation when a variable, only one will win out, and updated successfully, the others all will fail, but no thread failure will be hung, only to be told that failure, and allowed to try again, of course also allow threads to give up operation failure, This can also be seen in the picture
Based on this principle, even if the CAS operation does not have a lock, it is also aware of the impact of other threads on the operation of shared resources and performs corresponding processing measures. It can also be seen that since there is no lock in the lock-free operation, it is impossible for the CAS to be deadlocked, that is, CAS is inherently immune to deadlocks
1.2.2 CAS Support by CPU Instructions
Maybe we have such a question, assuming that there are multiple threads performing CAS operation and there are many CAS steps, is it possible that when V and E are judged to be the same, they switch to another thread and modify the value, resulting in inconsistent data?
The answer is no, because CAS is a system primitive, which belongs to the language of the operating system and is composed of several instructions to complete a process of a certain function. Moreover, the execution of the primitive must be continuous and cannot be interrupted during the execution
This means that CAS is an atomic instruction of the CPU and does not cause the so-called data inconsistency problem
1.3 Unsafe Class (Pointers)
Unsafe classes exist in the Sun. misc package, and their internal method operations can operate directly on memory like Pointers to C. The Unsafe class is not safe from its name alone. After all, the Unsafe class has pointer operations similar to C, and therefore should never be used in the first place
The Unsafe class itself is not recommended, but it’s important to know about it because CAS operations depend on the Unsafe class’s methods. Note that all its methods are native modifications, meaning that its methods call underlying operating system resources directly to perform tasks. The key features of the Unsafe class are as follows:
Memory management, the Unsafe class has methods to manipulate 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
// The memory page size of the operating system
public native int pageSize(a);
Copy the codeProvides a new approach to instance objects
// 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 codeClass and instance objects and variables are operated in the following main ways
// 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) operation with putIntVolatile and getIntVolatile, same reference type putObjectVolatile, too.
As with putIntVolatile, but the field being operated on must be volatile
public native void putOrderedInt(Object o,long offset,int x);
Copy the codeOperate on an array
// 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 codeThread suspend and resume operations
Suspending a thread is implemented through the park method. After calling park, the thread will remain blocked until timeout or interruption conditions occur. 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 uses 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 codeSo let’s introduce suspension of the operating system
Pending state
//TODO
1.3.1 Testing the Unsafe class
public class UnsafeDemo {
public static void main(String[] args) throws Exception {
// get the Field object corresponding to theUnsafe class theUnsafe attribute by reflection
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.toString());
// Create objects directly through allocateInstance
User user = (User) unsafe.allocateInstance(User.class);
Class userClass = user.getClass();
Field name = userClass.getDeclaredField("name");
Field age = userClass.getDeclaredField("age");
Field id = userClass.getDeclaredField("id");
// Get the offset of the instance variables name and age in the object memory and set the value
unsafe.putInt(user,unsafe.objectFieldOffset(age),18);
unsafe.putObject(user,unsafe.objectFieldOffset(name),"hello jiang");
// this returns user.class
Object staticBase = unsafe.staticFieldBase(id);
System.out.println("staticBase:" + staticBase);
// Get the offset of the static variable id staticOffset
long staticOffset = unsafe.staticFieldOffset(id);
// Get the value of a static variable
System.out.println("ID before setting :" + unsafe.getObject(staticBase,staticOffset));
/ / set the value
unsafe.putObject(staticBase,staticOffset,"jiang xiaopang");
// Get the value of a static variable
System.out.println("设置后的ID:" + unsafe.getObject(staticBase,staticOffset));
long data = 1000;
byte size = 1;
// 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("addData:"+ addrData); }}@ToString
class User {
private String name;
private int age;
private static String id="USER_ID";
public User(a){
System.out.println("User constructor called"); }}Copy the codeThe output
Sun. Misc. Unsafe @ 14 ae5a5 staticBase: class org. Jiang. TestUnsafe. User ID before setting: USER_ID setting after ID: jiang xiaopang addData: 1000Copy the codeAlthough the getUnsafe() method exists in the Unsafe class, it is only available for use by the advanced Bootstrap classloader. Calls to it by ordinary users will throw exceptions, So in the Demo, we’re using reflection to get the Unsafe instance object and to do that.
public static Unsafe getUnsafe(a) {
Class cc = sun.reflect.Reflection.getCallerClass(2);
if(cc.getClassLoader() ! =null)
throw new SecurityException("Unsafe");
return theUnsafe;
}
Copy the code1.3.2 Unsafe Indicates CAS operations
CAS are instructions that are directly supported by the CPU, namely the lock-free operations we examined earlier. Lock-free operations in Java are implemented based on the following three methods (the Atomic family of internal methods explained later)
// 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 codeThe Broadening class also introduces several new Java8 methods, which are implemented based on the CAS method described above:
// 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 codeThe above methods are still visible in Atomic series analysis
1.3.3 analysis based on Unsafe#getAndAddInt
Above we have introduced the source code of the Unsafe#getAndAddInt method
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;
}
Copy the codeWe create a local variable v, use getIntVolatile() to obtain the offset value of o, and then call compareAndSwapInt() to make constant comparisons
We know that the compareAndSwapInt() method checks whether the object o’s offset is still v. If it is v, it swaps v + delta and returns true, and vice versa
If false is returned, continue the loop, change variable V to the value of the latest object O, whose offset is offset, and then judge
So as long as other threads make changes, the loop continues to execute and get the value of the latest property until no other threads make changes
1.4 Atomic series
Unsafe, unlockable CAS, and its pointer class unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. unsafe. Unsafe Java is available from JDK1.5. Util. Concurrent. Atomic package, in the package provides many atomic operations based on CAS implementation class, mainly divided into four types
1.4.1 Atomic update base types
The atomic update basic types mainly include three classes:
- AtomicBoolean: Atom updates Boolean type
- AtomicInteger: Atom update integer
- AtomicLong: Atom updates long integers
The realization principle and use of these three classes are almost the same, here to AtomicInteger as an example for analysis, AtomicInteger mainly for int type data to perform atomic operations, it provides atomic increment, atomic subtraction and atomic assignment methods, the following first look at the source code
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// Get the pointer class Unsafe
private static final Unsafe unsafe = Unsafe.getUnsafe();
// The memory offset of the following 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);
}
// Add 1 to the current value to return the old value, underlying CAS operation
public final int getAndIncrement(a) {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
// If the current value is reduced by 1, 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);
}
// Add 1 to the current value, return the new value, underlying CAS operation
public final int incrementAndGet(a) {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
// If the current value is reduced by 1, 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 codeSo what did AtomicInteger do in the first place?
The instance object in the pointer class Unsafe is for pointer operations
2. We know that the value attribute in AtomicInteger is actually the initial value parameter passed in when the AtomicInteger object is created, that is, the encapsulated int value
3. Obtain the memory offset address of the value attribute in the AtomicInteger object through a static code block during initialization
Now, how are the main methods of doing operations implemented?
The getAndSet(), compareAndSet(), and getAndAdd() methods are actually cas-related operations called from the Unsafe class, indicating that AtomicInteger is lock-free
GetAndAddInt () = getAndAddInt() = getAndAddInt(
// The getAndAddInt method in the Unsafe class
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 codeThis is a do… While loop, the judgment condition of the loop is! CompareAndSwapInt (o, offset, v, v + delta). In the Unsafe class, we already know that using the variables o and offset, we can get the value of the property defined by the offset. V is the first value we get from the main memory. Then we want to change this value to v + delta
If the value of the main memory has changed, the CAS operation returns a Boolean value of false, and the variable v needs to retrieve the value of the property defined by the specified offset, and the loop continues
Only if the value of main memory does not change and CAS returns a Boolean value of true will the loop be broken out and the value of main memory be changed successfully
This ensures that the modified operation is based on lock-free atomic operation (without considering ABA)
12.4.2 AtomicInteger Method principle analysis
Broadening the Unsafe class, AtomicInteger and AtomicBoolean work in the same way, so we’ll look at AtomicInteger#getAndSet as an example
Let’s start by examining the AtomicInteger constructor. We know that when the constructor is called it initializes the class and executes some static variables and static code blocks (i.e. the CINit method)
The AtomicInteger class maintains a value variable of type int (volatile). The static code block reads:
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
Copy the codeGets the memory offset address of the value variable and assigns the value to valueOffset
Also, the class maintains a static variable unsafe:
private static final Unsafe unsafe = Unsafe.getUnsafe()
We know that objects cannot be created directly from the constructor in the Unsafe class, so here is an example of getting the Unsafe class
The constructor then assigns the parameter to the value variable
After initialization, let’s look at the getAndSet method
public final int getAndSet(int newValue) {
return unsafe.getAndSetInt(this, valueOffset, newValue);
}
Copy the codeAs you can see from the Unsafe class, this is actually a call to the getAndSetInt() method, as we’ve already looked at some of the broadening methods above, so the principles are pretty much the same
In fact, it also circulates through the characteristics of CAS and constantly takes out the latest value in main memory, and then compares it with the expected value to determine whether it can be updated
1.4.3 Atom update Reference
AtomicInteger, AtomicBoolean, AtomicBoolean, AtomicInteger, AtomicBoolean, AtomicBoolean, AtomicInteger, AtomicBoolean, AtomicBoolean, AtomicInteger, AtomicBoolean, AtomicBoolean, AtomicInteger, AtomicBoolean, AtomicBoolean, AtomicInteger, AtomicBoolean, AtomicBoolean, AtomicBoolean, AtomicInteger, AtomicBoolean, AtomicBoolean This is where the AtomicReference type, AtomicReference, needs to be used, and the basic principle is similar
Here is a simple example:
Define custom classes for operations:
@Data
@AllArgsConstructor
@NoArgsConstructor
class Person {
private String name;
private int age;
}
Copy the codeDefine test classes to test:
@Slf4j
public class Demo7 {
private static AtomicReference<Person> reference = new AtomicReference<>();
public static void main(String[] args) {
Person person = new Person("jiang".18);
reference.set(person);
Person newPerson = new Person("nidi".23);
person.setName("liu");
booleanflag = reference.compareAndSet(person, newPerson); log.info(String.valueOf(flag)); log.info(reference.get().toString()); }}Copy the codeHere generics on the AtomicReference class are reference types, and passing in different generics is essentially atomic operations on objects of different types
Reference. Set (person) is essentially an assignment to a value variable using a constructor similar to the AtomicInteger class
The test results
Since the data was not modified by any other thread, the expected value is the same as the value of the variable in main memory, so the modification succeeds
Test by modifying the expected value
@Slf4j
public class Demo7 {
private static AtomicReference<Person> reference = new AtomicReference<>();
public static void main(String[] args) {
Person person = new Person("jiang".18);
reference.set(person);
Person newPerson = new Person("nidi".23);
Person updatePerson = new Person("liu".18);
booleanflag = reference.compareAndSet(updatePerson, newPerson); log.info(String.valueOf(flag)); log.info(reference.get().toString()); }}Copy the codeThe test results
This is essentially simulating that there are other threads making changes to the variable, and you can see that the atomic changes fail
1.4.2.1 ABA problem
We know that CAS is really just a comparison and exchange, so here’s a question to think about:
If a thread in the access to the latest variable values before and after comparison and exchange, other threads on the variable operating twice, once changed to other values, another change back again, so at this time the CAS in comparison and exchange, it found that a variable’s value is the same as the expected value, does this mean no other threads to operate? , the above problems can be described as follows:
12.4.2.2 AtomicStampedReference
The AtomicStampedReference atom class is a time-stamped update of an object reference (essentially a version that has been modified by another thread)
After each change, the AtomicStampedReference not only sets the new value but also records the time stamp of the change
When an AtomicStampedReference object value is set, the object value and timestamp must meet the expected value to be read successfully. Therefore, you cannot predict whether the value has been modified during repeated reads and writes
Test the AtomicStampedReference class:
public class Demo07 {
static AtomicInteger atIn = new AtomicInteger(100);
// Initialization requires passing in an initial value and an initial time
static AtomicStampedReference<Integer> atomicStampedR =
new AtomicStampedReference<Integer>(200.0);
static Thread t1 = new Thread(new Runnable() {
@Override
public void run(a) {
// Update to 200
atIn.compareAndSet(100.200);
// Update to 100
atIn.compareAndSet(200.100); }});static Thread t2 = new Thread(new Runnable() {
@Override
public void run(a) {
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean flag=atIn.compareAndSet(100.500);
System.out.println("flag:"+flag+",newValue:"+atIn); }});static Thread t3 = new Thread(new Runnable() {
@Override
public void run(a) {
int time=atomicStampedR.getStamp();
// Update to 200
atomicStampedR.compareAndSet(100.200,time,time+1);
// Update to 100
int time2=atomicStampedR.getStamp();
atomicStampedR.compareAndSet(200.100,time2,time2+1); }});static Thread t4 = new Thread(new Runnable() {
@Override
public void run(a) {
int time = atomicStampedR.getStamp();
System.out.println("T4 time before sleep."+time);
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean flag=atomicStampedR.compareAndSet(100.500,time,time+1);
System.out.println("flag:"+flag+",newValue:"+atomicStampedR.getReference()); }});public static void main(String[] args) throws InterruptedException { t1.start(); t2.start(); t1.join(); t2.join(); t3.start(); t3.join(); t4.start(); t4.join(); }}Copy the codeThe basic logic of the test scheme is as follows:
AtomicInteger and AtomicStampedReference are created for comparison
We know that thread T1 must execute first and then put thread T2 in the ready state after completion of execution, so thread T1 will update variable 200, and then update variable 100, and then thread T2 will perform CAS operation
The basic logic is essentially the same for T3 and T4 threads, but the AtomicStampedReference class is added for atomic updates
The test results
You can see here that the AtomicStampedReference class avoids the ABA problem
The AtomicStampedReference class is described below:
The timestamp variable stamp here is a variable of int type, and stamp is not set automatically. Instead, the value of stamp variable is actively updated every time the CAS operation is performed. Of course, if the modification is successful, the version will be changed; otherwise, the version will not be changed
1.4.4 Atomic classes implement spin locking
Spin lock is an assumption that the current thread will acquire the lock in the near future. Therefore, the virtual machine will make the current thread to acquire the lock do several empty loops (this is why it is called spin). After several loops, if the lock is obtained, it will enter the critical region smoothly. If the lock is not available, threads are suspended at the operating system level, which can be a real productivity boost
However, as the number of threads increases and the competition becomes fierce, the CPU usage becomes longer, leading to a sharp decline in performance. Therefore, Java virtual machines generally have a certain number of spin locks, which may be abandoned after 50 to 100 cycles and directly suspend the thread to release CPU resources
AtomicReferenece implements a simple spinlock below:
public class SpinLock {
private AtomicReference<Thread> sign = new AtomicReference<>();
public void lock(a) {
Thread currentThread = Thread.currentThread();
while(! sign.compareAndSet(null, currentThread)) {
}
}
public void unlock(a) {
Thread currentThread = Thread.currentThread();
while(! sign.compareAndSet(currentThread,null) {}}}Copy the codeHere the CAS atomic operation is used as the underlying implementation, with the lock() method setting the value to be updated to the current thread and the expected value to NULL
The unlock() function is set to update the value to null, and the expected value is set to the current thread
We then use lock() and unlock() methods to control the opening and closing of a spin lock. Note that this is an unfair lock
In fact, the CAS operation inside the AtomicInteger(or AtomicLong) atomic class is also implemented through a while loop, which ends if the thread successfully updates the values of the values, but is also a type of spin lock
Test custom splock:
public class Demo007 {
private static SpinLock lock = new SpinLock();
public static void main(String[] args) {
new Thread(() -> {
try {
lock.lock();
try {
TimeUnit.SECONDS.sleep(5);
} catch(InterruptedException e) { e.printStackTrace(); }}finally{ lock.unlock(); }},"t1").start();
try {
TimeUnit.SECONDS.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(new Date());
lock.lock();
System.out.println(new Date());
System.out.println("Lock has been obtained"); }}Copy the codeHere we know that we don't use locks in our custom spin locks, so how do we do this?
We first create a spinlock object
For Thread T1, we call the lock.lock() method first. Since we maintain an AtomicReference
variable sign in our custom SpinLock class, and call the AtomicReference constructor when the class is initialized, Since no arguments are passed in the constructor, the value attribute in the AtomicReference class is null
Then, the CAS operation is used to determine whether the current value variable is null. If so, it is changed to the current thread. Obviously, thread T1 has been changed successfully (because the mian thread has been hibernated for 1s).
When the main thread attempts to call lock.lock(), it finds that the CAS value has been modified, so it spins itself
This is how the spin lock is implemented, and the mian thread stops spinning and executes downwards only when thread T1 re-sets the variable value from the current thread to NULL via the CAS operation using lock.unlock()
The test results
You can see from the timing that the main thread starts executing after the T1 thread completes
2 Shared model – immutable
2.1 Issues of date conversion
The SimpleDateFormat class is normally used for date formatting conversions. Is it safe in a concurrent environment?
Here’s a simple test:
public class Demo8 {
private static SimpleDateFormat format = new SimpleDateFormat("YYYY-MM-dd");
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
new Thread(() -> {
try {
Date date = format.parse("2021-03-04");
log.info("{}",date);
} catch(ParseException e) { e.printStackTrace(); } }).start(); }}}Copy the codeThe test results
Now that this is a problem, how can we improve it?
The DateTimeFormatter class can be used instead of the SimpleDateFormat class
The DateTimeFormatter class is immutable and thread-safe
Here’s the test:
@Slf4j
public class Demo8 {
private static DateTimeFormatter format = DateTimeFormatter.ofPattern("YYYY-MM-dd");
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
new Thread(() -> {
TemporalAccessor accessor = format.parse("2021-03-04");
log.info("{}",accessor); }).start(); }}}Copy the codeThe test results
13.2 Cause and solution of SimpleDateFormat Thread Insecurity
13.2 Cause and solution of SimpleDateFormat Thread Insecurity2.2.1 Reason why SimpleDateFormat thread is unsafe
2.2.2 Solution
2.3 Immutable object design
We are familiar with the String class, so let’s use the String class to design immutable elements
You can see that there are two attributes in the String class, one of which is a char array to hold the array of bytes used to create strings, and the other hash is a hashcode to cache String objects
For the final keyword:
- The final modifier property is used to ensure that the property is only readable, but cannot be modified
- A final class guarantees that methods in that class cannot be overridden, preventing subclasses from inadvertently breaking their immutability (
Classes that are actually final implicitly add the final keyword to their methods by default), and final modified classes cannot be inherited
Let’s look at the String constructor:
First, let’s understand what this comment means:
The contents of the byte array are copied because the value property in the String is not affected when the original array is modified
Let’s look at the constructor:
The value property is assigned to the byte array by copying the original byte array, which means that any changes to the parameters passed in will not affect the internal structure of the String
Now let’s look at the substring method:
The first step is to check that the truncated length matches the rule, and if it does, we call the String constructor, which we know is actually done by copying an array of bytes
So no matter how the byte array of the string before the interception changes, it doesn't affect the content of the string after the interception, right
In fact, this embodies the concept of immutable object design: protective copy
When a new String is created, a new byte array is generated, essentially copying the original byte array. The idea of creating duplicate objects to avoid sharing problems is protected copying
2.4 Share Mode
In the process of object-oriented design, it is sometimes necessary to create a large number of identical and similar object instances. It takes a lot of performance to create so many similar objects
2.4.1 Definition and Features
define
Sharing technology is used to effectively support the reuse of a large number of fine-grained objects. By sharing existing objects, the number of objects that need to be created can be greatly reduced, and the overhead of a large number of similar classes can be avoided, so as to improve the utilization rate of system resources
advantages
Only one copy of an object is saved, reducing the number of objects in the system and reducing the pressure on the memory caused by fine-grained objects in the system
disadvantages
In order to make objects shareable, some states that cannot be shared need to be externalized, increasing the complexity of the system
Reading the external state of the share mode makes the run time slightly longer
2.4.2 structure
There are two requirements in the definition of the share pattern: fineness and shared objects
Because of the need for fine granularity, there is inevitably a large number of objects with similar properties, so the information about objects needs to be divided into two parts: internal state and external state
- Internal state refers to the information shared by the object, stored within the metadata, and does not change with the environment
- An external state is a tag that an object can depend on, changes with the environment, and is not shareable
For example, the connection object in the connection pool, the user name, password, connection URL and other information stored in the connection object have been set up when the object is created and will not change with the environment. These are internal states
When each connection is to be recycled, we need to mark it as available. These are external states
Primary role in share mode
- Abstract privilege role: is the base class of all concrete privilege classes. To define the common interface that the privilege specification needs to implement, non-privilege external state is injected through methods in the form of parameters
- Concrete user role: Implements the interface specified in the abstract user role
- Non-share role: An external state that cannot be shared and is injected as a parameter into the methods associated with the specific share
- Privilege factory role: Is responsible for creating and managing privilege roles. When a customer object requests a privilege object, the privilege factory checks whether there is a qualified privilege object in the system. If there is a privilege object, the privilege factory provides it to the customer
Enjoy element mode structure diagram
UnsharedConcreteFlyweightA non-shared meta-role, which contains non-shared external status information infoFlyweightIs an abstract meta-role that contains meta-methodsoperation(UnsharedConcreteFlyweight state)The external state of non-privileged elements is passed in as parametersConcreteFlyweightIs a concrete user role that contains the keyword key and implements the abstract user interfaceFlyweightFactoryIs the privileges factory role, which is the key to manage specific privileges- The customer role obtains a specific privilege from the privilege factory and accesses methods related to the privilege
13.4.3 Mode Implementation
Abstract meta-roles
public interface Flyweight {
/** * Inject the external state of the non-privileged role */
void operation(UnshareConcreteFlyweight outState);
}
Copy the codeNon-privileged role
@Data
@AllArgsConstructor
@NoArgsConstructor
public class UnshareConcreteFlyweight {
private String info;
}
Copy the codeSpecific share meta role
@Slf4j
public class ConcreteFlyweight implements Flyweight{
private String key;
public ConcreteFlyweight(String key) {
this.key = key;
log.info("Concrete share {} was created",key);
}
@Override
public void operation(UnshareConcreteFlyweight outState) {
log.info("Specific element {} is called",key);
log.info("Non-privileged information is :{}",outState.getInfo()); }}Copy the codeEnjoy yuan factory role
@Slf4j
public class FlyweightFactory {
private HashMap<String,Flyweight> flyweights = new HashMap<>();
public Flyweight getFlyweight(String key) {
Flyweight flyweight = flyweights.get(key);
if(flyweight ! =null) {
log.info("Share {} already exists, obtained successfully",key);
} else {
flyweight = new ConcreteFlyweight(key);
flyweights.put(key,flyweight);
}
returnflyweight; }}Copy the codeClient testing
public class FlyweightPattern {
public static void main(String[] args) {
FlyweightFactory factory = new FlyweightFactory();
Flyweight f01 = factory.getFlyweight("a");
Flyweight f02 = factory.getFlyweight("a");
Flyweight f03 = factory.getFlyweight("a");
Flyweight f11 = factory.getFlyweight("b");
Flyweight f12 = factory.getFlyweight("b");
f01.operation(new UnsharedConcreteFlyweight("First call to A"));
f02.operation(new UnsharedConcreteFlyweight("Call a the second time"));
f03.operation(new UnsharedConcreteFlyweight("Third call to A"));
f11.operation(new UnsharedConcreteFlyweight("The first call to B"));
f12.operation(new UnsharedConcreteFlyweight("Call b the second time")); }}Copy the codeThe test results
The memory address is only created when it is first retrieved, and then retrieved if it exists
2.4.4 Integer Wraps the free element schema in the class
First we introduce Integer with a small test:
@Slf4j
public class IntegerTest {
public static void main(String[] args) {
Integer a = Integer.valueOf(127);
Integer b = 127;
Integer c = Integer.valueOf(128);
Integer d = 128;
log.info("{}", a == b);
log.info("{}",c == d); }}Copy the codeTest results:
You can see that the wrapper class created by 127 is an object no matter what, whereas the wrapper class created by 128 is a new object every time, right
Source code analysis
If I is between integerCache. low and integerCache. high, the object is retrieved from the cache array of the IntegerCache class
If not, create a new wrapper object
So what exactly is an IntegerCache?
/**
* Cache to support the object identity semantics of autoboxing for values between
* -128 and 127 (inclusive) as required by JLS.
*
* The cache is initialized on first usage. The size of the cache
* may be controlled by the {@code -XX:AutoBoxCacheMax=<size>} option.
* During VM initialization, java.lang.Integer.IntegerCache.high property
* may be set and saved in the private system properties in the
* sun.misc.VM class.
*/
private static class IntegerCache {
static final int low = -128;
static final int high;
static final Integer cache[];
static {
// high value may be configured by property
int h = 127;
String integerCacheHighPropValue =
sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
if(integerCacheHighPropValue ! =null) {
try {
int i = parseInt(integerCacheHighPropValue);
i = Math.max(i, 127);
// Maximum array size is Integer.MAX_VALUE
h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
} catch( NumberFormatException nfe) {
// If the property cannot be parsed into an int, ignore it.
}
}
high = h;
cache = new Integer[(high - low) + 1];
int j = low;
for(int k = 0; k < cache.length; k++)
cache[k] = new Integer(j++);
// range [-128, 127] must be interned (JLS7 5.1.7)
assert IntegerCache.high >= 127;
}
private IntegerCache(a) {}}Copy the codeIntegerCache is an inner class of the Integer class
Let’s understand the IntegerCache class comment:
IntegerCache default to the Integer – 128-127 to the cache, but can be modified by the JVM startup the largest cache values, start the instructions for the Java. Lang. Integer. IntegerCache. High
The static code block is then analyzed:
Here to create a variable h is 127, and then get in the JVM startup to Java. Lang. Integer. IntegerCache. The value of the high command
If the value exists, assign h to the maximum value between 127 and the value obtained by the instruction, and then assign H to the variable high (which has already achieved the maximum value of the custom cache).
The cache array is then created by traversing
From the above analysis, we know that when a static property in IntegerCache is called when the Integer#valueOf method is called, IntegerCache must be initialized and a static code block must be called
So why is it that when you create a wrapper object with a value of 127 it’s actually the same object
2.4.5 Customizing connection Pools
Let’s start by customizing a Connection class by implementing the Connection interface
@ToString
class MockConnection implements Connection {
@Override
public Statement createStatement(a) throws SQLException {
return null; }... }Copy the codeThen define a custom connection pool
@Slf4j
public class Pool {
// The connection pool size
private int poolSize;
// Join an array of objects
private Connection[] connections;
// Connection status array, 0 indicates unused, 1 indicates used
private AtomicIntegerArray states;
// constructor
public Pool(int poolSize) {
this.poolSize = poolSize;
connections = new Connection[poolSize];
states = new AtomicIntegerArray(poolSize);
for (int i = 0; i < poolSize; i++) {
connections[i] = newMockConnection(); }}// Get the connection
public Connection getConnection(a) {
while (true) {
for (int i = 0; i < poolSize; i++) {
if (states.get(i) == 0) {
states.compareAndSet(i,0.1);
log.info("get {}",connections[i]);
returnconnections[i]; }}// Block if there are no free connections
synchronized (this) {
try {
log.info("wait...");
this.wait();
} catch(InterruptedException e) { e.printStackTrace(); }}}}// Return the connection
public void free(Connection connection) {
for (int i = 0; i < poolSize; i++) {
if (connections[i] == connection) {
states.set(i,0);
log.info("free {}",connections[i]);
break; }}synchronized (this) {
this.notifyAll(); }}}Copy the codeDefining connection pools
Because the array thread is not safe, you need to use the AtomicIntegerArray to ensure that you can modify the values in the array simultaneously without concurrency problems
When the constructor is called to specify the size of the connection pool with the parameter passed in, and the array of connection objects and connection objects is created from the pool size, you can see that each object in the array of connection objects is a MockConnection object
Define fetch connection
The entire connection pool is first traversed, and if there is a thread object with a state of 0, the connection status information is first modified through CAS, and then the connection is acquired
If there are no free connections, the current thread is blocked until another thread releases the connection and wakes up
Define release connection
If so, set the connection status to 1. (Because this connection object is acquired by a thread, other threads cannot obtain this connection, so there is no security problem.)
When the connection is released, the thread currently blocked is woken up
The test class
public class Test {
public static void main(String[] args) {
Pool pool = new Pool(2);
for (int i = 0; i < 5; i++) {
new Thread(() -> {
Connection connection = pool.getConnection();
try {
Thread.sleep(new Random().nextInt(1000));
} catch(InterruptedException e) { e.printStackTrace(); } pool.free(connection); }).start(); }}}Copy the codeThe test results
You can see that only two threads can acquire connections, and they can only be reacquired when they are released
details
-
In fact, there is still a problem with the code. The connection state array needs to be modified with the volatile keyword to keep it visible (otherwise, if some thread has changed the state but there is no update in main memory, the concurrency error will still occur).
-
The reason for using the while loop when acquiring a connection is that when the thread that released the connection wakes up the blocking thread, it must ensure that the connection pool is checked again for existence (because it may have been acquired by another thread).
The above implementation does not consider:
-
Dynamic growth and contraction of connections
-
Keepalive connection (Availability check)
Cannot detect whether a connection is valid when it fails for some reason (such as heartbeat detection)
-
Wait timeout processing
We use this.wait() to block the thread, but do not deal with the blocking time, in order to prevent loop attempts when a connection is fetched but not yet fetched
-
Distributed hash
My personal official account is under preliminary construction now. If you like, you can follow my official account. Thank you!
