The concept of lock-free has been mentioned in the introduction of [High Concurrency Java 1]. Since there are a large number of lock-free applications in the jdk source code, lock-free is introduced here.
1 Detailed explanation of the principle of lockless class
1.1 CAS
The process of the CAS algorithm is as follows: it contains 3 parameters CAS(V,E,N). V represents the variable to be updated, E represents the expected value, and N represents the new value. Only if V
When the value is equal to the E value, the value of V will be set to N. If the V value is different from the E value, it means that other threads have already done updates, and the current thread does nothing. Finally, CAS returns the true value of the current V. CAS operations are carried out with an optimistic attitude, and it always believes that it can successfully complete the operations. When multiple threads operate a variable using CAS at the same time, only one will win and update successfully, and the rest will fail. The failed thread will not be suspended, it is only told that the failure is allowed, and it is allowed to try again, and of course the failed thread will also allow the operation to be abandoned. Based on this principle, CAS
The operation is locked immediately, and other threads can also detect interference to the current thread and handle it appropriately.
We will find that there are too many steps in CAS. Is it possible that after judging that V and E are the same, when we are about to assign values, we switched the thread and changed the value. What caused data inconsistency?
In fact, this worry is redundant. The entire operation process of CAS is an atomic operation, which is completed by a CPU instruction.
1.2 CPU instructions
The CPU instruction of CAS is cmmpxchg
The instruction code is as follows:
/* accumulator = AL, AX, or EAX, depending on whether a byte, word, or doubleword comparison is being performed */ if(accumulator == Destination) { ZF = 1; Destination = Source; } else { ZF = 0; accumulator = Destination; } If the target value is equal to the value in the register, a jump flag is set and the original data is set to the target. If you don't wait, you won't set the jump flag.
Java provides many lock-free classes, so let’s introduce lock-free classes below.
2 Useless
We already know that lock-free is much more efficient than blocking. Let's take a look at how Java implements these lock-free classes.
2.1. AtomicInteger
AtomicInteger, like Integer, both inherit the Number class
public class AtomicInteger extends Number implements java.io.Serializable
There are many CAS operations in AtomicInteger, typical of which are:
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
Here we will explain the unsafe.compareAndSwapInt method. It means that if the value of the variable whose offset on this class is valueOffset is the same as the expected value, then set the value of this variable to update.
In fact, the variable with the offset valueOffset is value
static { try { valueOffset = unsafe.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); }}We have said before that CAS may fail, but the cost of failure is very small, so the general implementation is in an infinite loop until it succeeds.
public final int getAndIncrement() { for (;;) { int current = get(); int next = current + 1; if (compareAndSet(current, next)) return current; } }2.2 Unsafe
From the class name, we can see that Unsafe operations are non-safe operations, such as:
Set the value according to the offset (I have seen this function in the AtomicInteger just introduced)
park() (stop this thread, it will be mentioned in the future blog)
The underlying CAS operation non-public API may differ greatly in different versions of JDK.
2.3. AtomicReference
AtomicInteger has been mentioned earlier, and of course AtomicBoolean, AtomicLong, etc. are all similar.
What we want to introduce here is AtomicReference.
AtomicReference is a template class
public class AtomicReference<V> implements java.io.Serializable
It can be used to encapsulate any type of data.
For example, String
package test;import java.util.concurrent.atomic.AtomicReference;public class Test{ public final static AtomicReference<String> atomicString = new AtomicReference<String>("hosee"); public static void main(String[] args) { for (int i = 0; i < 10; i++) { final int num = i; new Thread() { public void run() { try { Thread.sleep(Math.abs((int)Math.random()*100)); } catch (Exception e) { e.printStackTrace(); } if (atomicString.compareAndSet("hosee", "ztk")) { System.out.println(Thread.currentThread().getId() + "Change value"); }else { System.out.println(Thread.currentThread().getId() + "Failed"); } }; }.start(); } }}result:
10Failed
13Failed
9Change value
11Failed
12Failed
15Failed
17Failed
14Failed
16Failed
18Failed
You can see that only one thread can modify the value, and the subsequent threads cannot modify it any more.
2.4.AtomicStampedReference
We will find that there is still a problem with CAS operation.
For example, the previous AtomicInteger incrementAndGet method
public final int incrementAndGet() { for (;;) { int current = get(); int next = current + 1; if (compareAndSet(current, next)) return next; } } Suppose the current value=1 When a thread int current = get() executes, switch to another thread, this thread turns 1 into 2, and then another thread turns 2 into 1 again. At this time, switch to the initial thread. Since the value is still equal to 1, CAS operations can still be performed. Of course, there is no problem with addition. If there are some cases, such a process will not be allowed when it is sensitive to the state of the data.
At this time, the AtomicStampedReference class is required.
It implements a Pair class internally to encapsulate values and timestamps.
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 new Pair<T>(reference, stamp); } }The main idea of this class is to add timestamps to identify each change.
//Compare settings parameters are: the expected value writes the new value expect timestamp New timestamp
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))); } When the expected value is equal to the current value and the expected timestamp is equal to the current timestamp, the new value is written and the new timestamp is updated.
Here is a scenario that uses AtomicStampedReference. It may not be suitable, but I can't imagine a good scenario.
The scene background is that a company recharges users with low balance for free, but each user can only recharge once.
package test;import java.util.concurrent.atomic.AtomicStampedReference;public class Test{ static AtomicStampedReference<Integer> money = new AtomicStampedReference<Integer>( 19, 0); public static void main(String[] args) { for (int i = 0; i < 3; i++) { final int timestamp = money.getStamp(); new Thread() { public void run() { while (true) { while (true) { Integer m = money.getReference(); if (m < 20) { if (money.compareAndSet(m, m + 20, timestamp, timestamp + 1)) { System.out.println("Recharge successfully, balance:" + money.getReference()); break; } } else { break; } } } } } }; }.start(); } new Thread() { public void run() { for (int i = 0; i < 100; i++) { while (true) { int timestamp = money.getStamp(); Integer m = money.getReference(); if (m > 10) { if (money.compareAndSet(m, m - 10, timestamp, timestamp + 1)) { System.out.println("Consumed 10 yuan, balance:" + money.getReference()); break; } }else { break; } } try { Thread.sleep(100); } catch (Exception e) { // TODO: handle exception } } } }; }.start(); }}Explain the code, there are 3 threads recharge the user. When the user's balance is less than 20, recharge the user 20 yuan. There are 100 threads consuming, each spending 10 yuan. The user initially has 9 yuan. When using AtomicStampedReference to implement it, the user will only be recharged once, because each operation causes the timestamp +1. Running results:
Recharge successfully, balance: 39
Consumption of 10 yuan, balance: 29
Consumption of 10 yuan, balance: 19
Consumption of 10 yuan, balance: 9
If you use AtomicReference<Integer> or Atomic Integer to implement it, it will cause multiple recharges.
Recharge successfully, balance: 39
Consumption of 10 yuan, balance: 29
Consumption of 10 yuan, balance: 19
Recharge successfully, balance: 39
Consumption of 10 yuan, balance: 29
Consumption of 10 yuan, balance: 19
Recharge successfully, balance: 39
Consumption of 10 yuan, balance: 29
2.5. AtomicIntegerArray
Compared with AtomicInteger, the implementation of arrays is just an extra subscript.
public final boolean compareAndSet(int i, int expect, int update) {
return compareAndSetRaw(checkedByteOffset(i), expect, update);
}
Its interior just encapsulates a normal array
private final int[] array;
What's interesting here is that the leading zeros of binary numbers are used to calculate the offset in the array.
shift = 31 - Integer.numberOfLeadingZeros(scale);
The leading zero means that for example, 8 bits represent 12,00001100, then the leading zero is the number of 0 in front of 1, which is 4.
How to calculate the offset is not introduced here.
2.6. AtomicIntegerFieldUpdater
The main function of the AtomicIntegerFieldUpdater class is to allow ordinary variables to enjoy atomic operations as well.
For example, there was originally a variable that was int type, and this variable was applied in many places. However, in a certain scenario, if you want to turn the int type into AtomicInteger, if you change the type directly, you have to change the application in other places. AtomicIntegerFieldUpdater is designed to solve such problems.
package test;import java.util.concurrent.atomic.AtomicInteger;import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;public class Test{ public static class V{ int id; volatile int score; public int getScore() { return score; } public void setScore(int score) { this.score = score; } } public final static AtomicIntegerFieldUpdater<V> vv = AtomicIntegerFieldUpdater.newUpdater(V.class, "score"); public static AtomicInteger allscore = new AtomicInteger(0); public static void main(String[] args) throws InterruptedException { final V stu = new V(); Thread[] t = new Thread[10000]; for (int i = 0; i < 10000; i++) { t[i] = new Thread() { @Override public void run() { if(Math.random()>0.4) { vv.incrementAndGet(stu); allscore.incrementAndGet(); } } }; t[i].start(); } for (int i = 0; i < 10000; i++) { t[i].join(); } System.out.println("score="+stu.getScore()); System.out.println("allscore="+allscore); }} The above code turns score using AtomicIntegerFieldUpdater into AtomicInteger. Ensure thread safety.
Allscore is used here to verify. If the score and allscore values are the same, it means that it is thread-safe.
Note: