Thoughts without locks

as everyone knows ,Java The most common way to control concurrency in Windows vista is through locking , A lock guarantees that only one thread can access the resources of the critical section at a time , To achieve thread safety . However , Although the lock works , But it is a pessimistic strategy . It assumes that every access to a critical section’s resources will result in a conflict , When a thread accesses a resource , Other threads must wait , So the lock is blocking the thread from executing .

Of course , Every coin has two sides , Where there is pessimism, there is optimism . Unlocked is an optimistic strategy , It assumes that the thread’s access to the resource is conflict-free , At the same time, all threads execute without waiting , Can be executed continuously . If there is a conflict , Let’s just use something called CAS ( More exchange ) To identify thread conflicts , If a conflict is detected , Retry the current operation until there is no conflict .

CAS summary

CAS The full name is Compare-and-Swap, So compare and swap , Is a common algorithm in concurrent programming . It contains three parameters ：V,A,B.

among ,V Represents the memory location to read and write to ,A Represents the old expected value ,B Represents the new value

CAS Instruction execution , If and only if V Is equal to the expected value A when , Will be V The value of the set B, If V and A Different , Note that another thread may have made the update , So the current thread does nothing , Last ,CAS The return is V True value of .

And in the case of multithreading , When multiple threads are used simultaneously CAS When you manipulate a variable , Only one will succeed and update the value , The rest of the threads will fail , But failed threads are not suspended , Instead, it keeps repeating and retrying . It’s based on this principle ,CAS Lock is not used immediately , You can also find other threads interfering with the current thread , In order to carry out timely processing .

CAS The application of the class

Java Provides a range of applications CAS Operation of class , These classes are located in java.util.concurrent.atomic It’s a bag , One of the most common is AtomicInteger, This class can be considered an implementation CAS Operation of the Integer, therefore , Let’s take a look at the whole picture by studying the cases of this class CAS The magic effect of .

Study AtomicInteger Before , Let’s start with an example of the code ：

public class AtomicDemo {
public static int NUMBER = 0;
public static void increase() {
NUMBER++;
}
public static void main(String[] args) throws InterruptedException {
AtomicDemo test = new AtomicDemo();
for (int i = 0; i < 10; i++) {
new Thread(() -> {
for (int j = 0; j < 1000; j++)
test.increase();
}).start();
}
Thread.sleep(200);
System.out.println(test.NUMBER);
}
}

stay main The function is turned on 10 Threads , It will be called in turn after execution increase(), Of course we know , The output after running is definitely not what we expected , Because we’re not doing thread-safe processing , therefore 10 The resources of the critical section are manipulated by thread traffic NUMBER Will go wrong .

The solution is not difficult , Use the locks we learned before , for example synchronized Decorated code block , The program will output normally 10000. Of course , Locking is not the way we want it to be , Because the lock blocks the thread , Affects program performance , Now ,AtomicInteger I can use it .

Modify the above program , It goes down like this ：

public static AtomicInteger NUMBER = new AtomicInteger(0);
public static void increase() {
NUMBER.getAndIncrement();
}
public static void main(String[] args) throws InterruptedException {
AtomicDemo test = new AtomicDemo();
for (int i = 0; i < 10; i++) {
new Thread(() -> {
for (int j = 0; j < 1000; j++)
test.increase();
}).start();
}
Thread.sleep(200);
System.out.println(test.NUMBER);
}

function main Method , The output of the program is the value we want , That is to say 10000.

In the above code ,increase Called in the method NUMBER.getAndIncrement() , This is a AtomicInteger Self – increment method , It will add to the current value 1, And return the old value , Click into the source method , It calls theta unsafe.getAndAddInt() Method ：

public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

getAndAddInt Is added to the current value 1, And return the old value .

unsafe yes Unsafe A variable in a class , adopt Unsafe.getUnsafe() To get

private static final Unsafe unsafe = Unsafe.getUnsafe();

Unsafe Class is a special class , It’s a JDK Exclusive classes for internal use , You can’t view the source code directly with a regular editor , You can only see decompiled class file .

Here’s an extension , Namely Java The operating system itself cannot be accessed , Need to use native Method , and Unsafe Methods in a class contain a large number of methods native Method , Improved Java Ability to manipulate the atoms at the bottom of the system . For example, we use it in our code getAndAddInt() The bottom level is to call one native Method , use idea Click on the way , Get the following decompiled code ：

public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

compareAndSwapInt Is used to compare and exchange integer values , If the value of the specified field is equal to the expected value , That is to say CAS Medium ‘A’ ( Expected value ), So it’s going to set it to the new value (CAS Medium ‘B’), It’s not hard to imagine , The internal implementation of this method must be done by atomic operation . besides ,Unsafe The class also provides methods for other atomic operations , For example, in the above source code getIntVolatile Is the use of volatile Semantically gets the value of the given object , These methods effectively improve the performance of the application layer through the underlying atomic operations .

CAS The shortcomings of

although CAS Is much more powerful than locking , But it also has some disadvantages , for example ：

1、 Loops are time consuming

stay getAndAddInt The methods of , We can see , Simply setting a value calls the loop , If CAS Failure , It’s going to keep trying . If CAS It didn’t work for a long time , Then the loop will keep going , There is no doubt that this will cause a lot of overhead to the system .

2、ABA problem

As I said before ,CAS The conditions for the success of the variable operation are V The value of and A It’s consistent , There is a small flaw in this logic , Is that if V Is at the beginning A, The change was made during the preparation of the change to the new value B, It was later changed back to A, The value of the object remains the same after the thread has changed it twice , that CAS This variable has never been modified . This is it. CAS Medium “ABA” problem .

Of course ,”ABA” There are solutions to problems ,Java An object reference with a timestamp is provided in the packet AtomicStampedReference, It maintains more than just an object value internally , A timestamp is also maintained , When AtomicStampedReference When the corresponding value is modified , In addition to updating the data itself , You also need to update the timestamp , Only the object value and timestamp satisfy the expected value , To modify it successfully . This is a AtomicStampedReference Several methods for timestamp information ：

// Is set The parameters are ： Expectations Write the new value Expected timestamp A new time stamp
public boolean compareAndSet(V expectedReference, V newReference,
int expectedStamp, int newStamp)
// Get the current timestamp
public int getStamp()
// Sets the current object reference and timestamp
public void set(V newReference, int newStamp)