preface
If you want to talk about atomic classes, you can start with the basic concepts
1. What kind of problems do atomic classes solve?
A: In order to solve the concurrent scenario without locking to ensure the data consistency of a single variable
2. When do concurrency problems exist?
A: Multithreading concurrency is a problem when multiple threads read and write to the same shared data
There are many ways to address concurrency security issues, the famous being the JDK and issuing concurrent packages, which exist for concurrency
Read the article and learn the following:
1. The output background of lock-free programming 2. How to realize lock-free programming of CAS 3. How to solve the “ABA” problem
Article first from the public number [source interest circle], concerned about the public number for the first time to obtain back-end core knowledge, has issued [44] original technology blog
Nonatomic calculation
As you probably know, this is similar to the i++ operation in the code, although it is one line, but the execution is divided into three steps
- Gets variable I from main memory
- The variable I is plus 1
- The value of variable I is written back to main memory
Let’s write a little program just to get a better sense of it, no matter how we run the program below, 99% of the time it’s not going to get to 10,000,000, right
static int NUM = 0;
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10000; i++) {
new Thread(() -> {
for (int j = 0; j < 10000; j++) {
NUM++;
}
}).start();
}
Thread.sleep(2000);
System.out.println(NUM);
/ * * * * / 99149419
}
Copy the codeYou can use the JDK’s built-in synchronized code block to execute NUM++ as a mutex
static int NUM = 0;
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10000; i++) {
new Thread(() -> {
for (int j = 0; j < 10000; j++) {
synchronized (Object.class) {
NUM++;
}
}
}).start();
}
Thread.sleep(2000);
System.out.println(NUM);
/ * * * * / 100000000
}
Copy the codeAtomicInteger: Lock, lock, lock, lock, lock, lock
If you have looked at the JDK source code for the library in the JUC package, you will be familiar with the library starting with Atomic
It’s an Atomic thing
If you don’t use locks to solve the non-atomic increment problem above, you can write it this way
static AtomicInteger NUM = new AtomicInteger();
public static void main(String[] args) throws InterruptedException {
for (int i = 0; i < 10000; i++) {
new Thread(() -> {
for (int j = 0; j < 10000; j++) {
// 🚩 key point, increment and get new value
NUM.incrementAndGet();
}
}).start();
}
Thread.sleep(2000);
System.out.println(NUM);
/ * * * * / 100000000
}
Copy the codeAtomicInteger profile
When looking at a relatively new piece of knowledge such as a technical point or framework, two questions are often asked
What is it
AtomicInteger is an Integer type atomic class for operations provided under the JDK and distributed packages. Atomic operations are implemented by calling the CAS related methods of the underlying Unsafe
A lock-free atomic operation based on the idea of optimistic locking ensures the thread safety of a single variable in the case of multiple threads
The concept of CAS will be explained in more detail below
What are the advantages
AtmoicInteger uses the hardware-level instruction CAS to update the value of the counter, which is directly supported by the machine to avoid locking
Synchronized, for example, upgrades to heavyweight locks in cases of high concurrency
There is a transition from user state to kernel state when a thread is awakened or blocked, and the transition state takes a lot of time
I have written a program for testing. Although synchronized has greatly improved its performance after upgrading, CAS lock-free algorithm has higher performance in general concurrent scenarios
Of course, it is impossible to be perfect. Disadvantages of CAS lock-free algorithm will be explained below
Structure analysis
AtomicInteger has two constructors, a no-parameter construct and a parameter construct
- A value constructed without arguments is the default value of int 0
- Parameter constructs assign value
public AtomicInteger(a) {}public AtomicInteger(int initialValue) {
value = initialValue;
}
Copy the codeAtomicInteger has three important variables, which are:
Unsafe: It’s a “BUG” for Java, and its most important function in AtomicInteger is to directly manipulate memory for value substitution
Value: Uses the int type to store the AtomicInteger calculated value, which is modified by volatile to provide memory visibility and prevent instruction reordering
ValueOffset: memory offset of value
// Get the Unsafe instance
private static final Unsafe unsafe = Unsafe.getUnsafe();
private static final long valueOffset;
// Static code block, run at class load time
static {
try {
// Get the memory offset of value
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) {
throw newError(ex); }}private volatile int value;
Copy the codeHere’s a list of some common apis, all with the same core implementation ideas. I’ll focus on one of them
// Get the current value
public final int get(a);
// Take the current value and set the new value
public final int getAndSet(int newValue);
// Get the current value and add the expected value
public final int getAndAdd(int delta);
// Get the current value and increment it by 1
public final int getAndIncrement(a);
// Get the current value and decrement by 1
public final int getAndDecrement(a);
Copy the codeIncrement #getAndIncrement()
How does this work in the source code
public final int getAndIncrement(a) {
return unsafe.getAndAddInt(this, valueOffset, 1);
}
/**
* unsafe.getAndAddInt
*
* @paramVar1 AtomicInteger object *@paramVar2 value Memory offset *@paramThe increment of var4, such as + 1 * over the original value@return* /
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
// Value Indicates the latest value in memory
var5 = this.getIntVolatile(var1, var2);
} while (!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
Copy the codeThis is where CAS represents the lock-free algorithm. Here’s how to execute this code
1. Obtain the latest value of the corresponding value based on the AtomicInteger object and the memory offset of the value
2, compareAndSwapInt(…) Changing the value in memory (var5) to the desired value (var5+ VAR4) without multithreaded contention returns True to terminate the loop, and Flase continues the loop
The essence is compareAndSwapInt(…)
/** * compares the memory offset of var1 with that of var4, and updates the value to var5 **@paramVar1 AtomicInteger object *@paramVar2 value Memory offset *@paramVar4 value Original value *@paramVar5 expects the value to be set to *@return* /
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
Copy the codeBecause it is native keyword modification, we can not view its source code, explain the method idea
1. Obtain the value of VAR2 (memory offset) from VAR1 (AtomicInteger)
2. Compare value(in-memory value) to VAR4 (in-thread value)
3. If equal, set var5(expected value) to the new value in memory and return True
4. Unequal returns False to continue trying to execute the loop
Graphic Analysis CAS
Here is a set of images to further understand CAS
Unsafe#getAndAddInt() takes this method as an example
1. This image corresponds to the position of valueOffset corresponding to the AtomicInteger object
Var5 = this.getIntVolatile(var1, var2)
Var5 = this.getIntVolatile(var1, var2)
Var5 is now 0 in the working memory of thread 1 and thread 2
4, thread 1 wants to change the value in memory to 1, by comparing var4 with the value in memory, the memory value is successfully set to 1
Thread 2 is trying to change the value of the memory. If the value is not equal, return False
Deficiency in
CAS, while capable of lock-free programming, generally improves performance, is not without limitations or drawbacks
1, CPU spin overhead is high
In high concurrency cases, spin CAS can incur significant execution overhead on the CPU if they are unsuccessful for long periods of time
If it is to achieve high concurrency under the count, you can use LongAdder, design of high concurrency is really strong!
The famous “ABA” problem
The CAS needs to check whether the value has changed during the operation. If the value has not changed, the CAS updates the value
But if A value is A, becomes B, and becomes A again, then checking with CAS will find that its value has not changed, when in fact it has
If you are interested, check out AtomicStampedReference in the JUCA atom package
Background of ABA problems
One problem with AtomicInteger, and with most of its Atomic related classes, is the ABA problem
In short, thread one gets an AtomicInteger value of 0 before it is ready to modify it
Thread two performs two operations on the Value of AtomicInteger, once changing the value to 1 and then changing it back to 0
As soon as the thread performs CAS operation, it finds that the value in memory is still 0. OK, the update is successful
1. Why can thread 2 operate after thread 1 gets the latest value?
Let’s illustrate this with Atom Integer#getAndIncrement
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
/ / mark 1
var5 = this.getIntVolatile(var1, var2);
} while (!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
Copy the codeBecause our CPU execution is preemptive, the time slice allocation is not fixed
It is possible that the allocation of time slices is performed by thread 2 as soon as the thread reads marker 1, and thread 1 waits for the allocation of time slices
After thread 2 completes the two-step operation, the time slice is allocated to thread 1 and the execution will continue
2. What kind of problems can ABA cause?
You probably already know how ABA behavior works. Here’s a quick example from the Internet.
1. Xiao Ming’s bank card account has a balance of 10,000 yuan and goes to the ATM to withdraw 5,000 yuan. Normally, he should initiate a request, but he initiated two requests because of network or machine failure
Everyone big brother big sister don’t barter ha, don’t say what back-end interface idempotence, withdrawal machine against repeated submission and so on, the example is to illustrate the problem, thank 😄
2, thread 1 “initiated by ATM” : get the current bank card balance value of 10,000 yuan, expected value of 5,000 yuan
3. Thread 2 “initiated by ATM” : obtain the current bank card balance value of 10,000 yuan, expected value of 5,000 yuan
Thread 1 succeeded, the bank card balance remaining 5000, thread 2 did not allocate time slice, after obtaining the balance was blocked
5. At this time, thread 3 “Alipay into bank card” : the current bank card balance is 5,000 yuan, the expected value is 10,000 yuan, the modification is successful
6. Thread 2 gets the time slice, finds the balance in the card is 10,000, and successfully reduces the balance in the card to 5,000
7. The balance in the card should have been 10,000-5,000 + 5,000-5,000 = 10,000, but eventually 10,000-5,000 + 5,000-5,000 = 5,000 due to ABA problems
Of course, formal business may not have such problems, but ordinary business use of atomic classes, there are still potential dangers
So let’s start with a little program code, how does the ABA problem recur
public static void main(String[] args) throws InterruptedException {
AtomicInteger atomicInteger = new AtomicInteger(100);
new Thread(() -> {
atomicInteger.compareAndSet(100.101);
atomicInteger.compareAndSet(101.100);
}).start();
Thread.sleep(1000);
new Thread(() -> {
boolean result = atomicInteger.compareAndSet(100.101);
System.out.println(String.format(">>> Modify atomicInteger :: %s", result));
}).start();
/** * >>> Modify atomicInteger :: true */
}
Copy the codeCreate an AtomicInteger with an initial value of 100, and select 100-> 101 from thread 1
2. Hibernate for 1000ms to prevent time slice allocation thread 2 from executing ahead of schedule
3, thread 2 from 100->101, modify successfully
AtomicStampedReference
Let’s start with the idea of ABA solution, namely the principle of atom Stampedreference
Internal maintenance of a Pair object, store value and a version number, each update in addition to the value value will update the version number
private static class Pair<T> {
// Store the value equivalent to the value 100 above
final T reference;
// Similar to the concept of version numbers
final int stamp;
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
// Create a new Pair object, each time the value changes
static <T> AtomicStampedReference.Pair<T> of(T reference, int stamp) {
return newAtomicStampedReference.Pair<T>(reference, stamp); }}Copy the codeLet’s start with a little program to see how your AtomicStampedReference works
@SneakyThrows
public static void main(String[] args) {
AtomicStampedReference stampedReference = new AtomicStampedReference(100.0);
new Thread(() -> {
Thread.sleep(50);
stampedReference.compareAndSet(100.101,
stampedReference.getStamp(),
stampedReference.getStamp() + 1);
stampedReference.compareAndSet(101.100,
stampedReference.getStamp(),
stampedReference.getStamp() + 1);
}).start();
new Thread(() -> {
int stamp = stampedReference.getStamp();
Thread.sleep(500);
boolean result = stampedReference.compareAndSet(100.101, stamp, stamp + 1);
System.out.println(String.format(">>> Modify stampedReference :: %s", result));
}).start();
/** * >>> Modify atomicInteger :: false */
}
Copy the code1. Create AtomicStampedReference and set the initial value to 100 and version number to 0
2, thread 1 sleep 50ms, then perform operation on value 100->101, 101->100, version +1
Why sleep 50ms? To simulate concurrent preemption, let thread two get the version number first
3, thread two sleep 500ms, wait for thread one to complete the execution, start to 100->101, version number +1
Not surprisingly, thread 2 will fail to modify, although the values correspond, but the expected version number is not the same as in Pair
compareAndSet
Check out its compareAndSet(…) How is it done
/** * compares and sets **@paramExpectedReference Expected value *@paramNewReference Expected value *@paramExpectedStamp The expected version number *@paramNewStamp Expected version number *@returnSuccessful */
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
// Get the current pair reference
AtomicStampedReference.Pair<V> current = pair;
// Expected value comparison pair value
return expectedReference == current.reference &&
// Expected version number compared to pair stamp
expectedStamp == current.stamp &&
// Pair value
((newReference == current.reference &&
// Expected version number compared to pair stamp
newStamp == current.stamp) ||
// casPair
casPair(current, Pair.of(newReference, newStamp)));
}
Copy the codeIf the compareAndSet (…). If True, all three conditions in the conditional expression above must be met
1. The expected value is the pair value
2. The expected version number is equal to pair stamp
3. The expected value is the pair value and the expected version is the pair stamp
This is the scenario where the value and version number have not changed
4. If the first condition and the second condition are met, but the third condition is not met, prove that the value and version number have changed, create a Pair for CAS comparison and replacement
The above conditions must satisfy 1, 2, 3 or 1, 2, 4
Switch the current Pair AtomicReference to the new Pair, the same idea as AtomicReference, the object reference atomic conversion
private boolean casPair(AtomicStampedReference.Pair<V> cmp, AtomicStampedReference.Pair<V> val) {
return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}
Copy the codePits that use Integer value
As you probably know, if you write the following code, you will not create objects in the heap
Integer i1 = 100;
Integer i2 = 101;
Copy the codeBecause the JVM stores two objects in the constant pool, values above -128 to 127 create objects in the heap
The reference of our Pair object is a stereotype, and the value passed as an int will be converted to an Integer
Error: compareAndSet(…); error: compareAndSet(…); Will understand the
AtomicMarkableReference
As you can see from the above version number, the two operations must be inconsistent, increment or, subtraction or other operations, relatively tedious
Doug Lea also provides a handy library called AtomicMarkableReference
The API interface and implementation ideas are basically the same as above, except that the version number int type is replaced by a Boolean type, other no difference
However, AtomicMarkableReference is not a complete solution to ABA problems, only a small probability of prevention
“Said
Due to the limited level of the author, you are welcome to feedback and correct the article is not correct, thanks to 🙏
The likes of my friends are the biggest support for me. If I gain something from reading this article, I hope I can like it, comment on it and pay attention to it.
Recommended reading:
- ParallelStream Is a new feature in JDK 8
- How does Redisson implement distributed locking principle
- [Highly recommended] Talk about ReentrantLock and AQS
- How to quickly consume tasks in the JDK thread pool without exceeding the maximum number of threads
- How does the JDK thread pool ensure that core threads are not destroyed
Author Mahua, coordinate Java backend research and development, aspiring to become an architect of a Virgo programmer, focus on high concurrency, framework source code, distributed and other knowledge sharing