Java concurrency — non-blocking synchronization

CAS problem introduction

In the concurrency problem, the first thought is undoubtedly mutex synchronization, but thread blocking and wake up bring great performance problems, the core of the synchronization lock is nothing more than to prevent concurrent modification of shared variables caused by the problem, but not always such a competitive relationship.

What is the CAS

CAS, Compare and Swap (CAS). If the expected value is the same as the main memory value, the value to be updated is swapped. Also known as optimistic lock.

If thread A copies variable A as 1 from main memory and changes it to 10 in its own thread, then thread A has successfully updated the value of A in main memory if the value of main memory A does not change (expected value) and remains 1. But if the value of main memory A has been changed from 1 by another thread, then thread A keeps retrying until it succeeds (spin).

The CAS from which

CAS, which belongs to the J.U.C package, calls the method in the Unsafe class, a hardware-supported atomic operation that cannot be interrupted or stopped without mutex synchronization.

Take the getAndAddInt method under AtomicInteger, for example. U stands for Unsafe class.

/ * * *@paramExpectedValue Expect value *@paramNewValue the new value@returnPrice comparison update is successful. */
public final int incrementAndGet(a) {
    return U.getAndAddInt(this, VALUE, 1) + 1;
}
Copy the code

Then, getIntVolatile(o, offset) is used to obtain the previous value v. WeakCompareAndSetInt () is used to make the CAS comparison. If the value in the field’s memory address is equal to v, Update the variable with memory address o+offset to v + delta. The getAndAddInt() method runs in a loop, and the conflict is repeated retries.

/ * * *@paramO Update objects/arrays of fields/elements *@paramOffset Field/element offset *@paramDelta The value to be added, step *@returnPrevious value *@since1.8 * /
@HotSpotIntrinsicCandidate
public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while(! weakCompareAndSetInt(o, offset, v, v + delta));return v;
}
Copy the code

Run code examples

Threads T1 and T2 simultaneously change the value of A variable in main memory, artificially making B faster than A

public class TestCAS {
    // Primary memory atomicInteger has an initial value of 1
    public static AtomicInteger atomicInteger = new AtomicInteger(1);

    public static void main(String[] args) {
        // Thread A plans to change the value to 10, sleep for 2s, and compare the swap
        new Thread(() -> {
            try { TimeUnit.SECONDS.sleep(2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("Current thread:"+Thread.currentThread().getName()+"Compare the exchange results:"
                    +atomicInteger.compareAndSet(1.10) +"The current value is:"+atomicInteger.get());
        },"t1").start();

        // thread B plans to change the value to 10 without sleeping
        new Thread(() -> {
            System.out.println("Current thread:"+Thread.currentThread().getName()+"Compare the exchange results:"
                    +atomicInteger.compareAndSet(1.20) +"The current value is:"+atomicInteger.get());
        },"t2").start(); }}Copy the code

The console

Current thread: T2trueThe current value is:20Current thread: T1falseThe current value is:20
Copy the code

This eliminates the need for synchronization locks and solves the problem of concurrent modification of variables.

If your best friend borrows $10 from you, and the next day he gives you $10 back. If your friend just wants to buy a bag of snacks, you probably won’t care.

Introduction of ABA problems

In the last code, there was a problem. Such as: T1 and T2 both copy atomicInteger=1. If thread B has a higher priority or is lucky,t2 first changes atomicInteger to 20 and writes to main memory. T2 then copies atomicInteger=20 and changes the copy to 1 again. And successfully write back to main memory. The third time, T1 gets the main memory atomicInteger. But this value has been modified twice by T2, will it be a problem?

ABA problem

If A variable is first read with A value of A, its value is changed to B, and then changed back to A, the CAS operation will assume that it has never been changed.

ABA solution

  1. Mutually exclusive synchronization lock synchronized

  2. If the project only cares about correct values, then ABA problems do not affect the correctness of the program’s concurrency.

  3. The J.U.C package addresses this problem by providing a time-stamped atom reference class AtomicStampedReference, which guarantees the correctness of the CAS by controlling the version of the variable.

AtomicStampedReference code example

public class SolveCAS {
    // The main memory share variable, with an initial value of 1 and version number of 1
    private static AtomicStampedReference<Integer> atomicStampedReference = new
            AtomicStampedReference<>(1.1);


    public static void main(String[] args) {
        // t1, expect to change 1 to 10
        new Thread(() -> {
            // Get the timestamp for the first time
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName()+"1st time stamp:"+stamp+"Value:"+atomicStampedReference.getReference());
            // Sleep for 5s to ensure that T2 completes ABA operation
            try { TimeUnit.SECONDS.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); }
            // t2 changes the timestamp to 3,cas fails
            boolean b = atomicStampedReference.compareAndSet(1.10, stamp, stamp + 1);
            System.out.println(Thread.currentThread().getName()+"CAS successful or not:"+b);
            System.out.println(Thread.currentThread().getName()+"Current latest timestamp:"+atomicStampedReference.getStamp()+"Latest value is:"+atomicStampedReference.getReference());
        },"t1").start();

        // T2 perform ABA operation
        new Thread(() -> {
            // Get the timestamp for the first time
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName()+"1st time stamp:"+stamp+"Value:"+atomicStampedReference.getReference());
            // Hibernate and make sure t1 gets the same copy before changing, starting with 1
            try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); }
            // change the copy to 20, then write, then change the copy to 1, each time promote the timestamp, t1 does not intervene
            atomicStampedReference.compareAndSet(1.20, stamp, stamp + 1);
            System.out.println(Thread.currentThread().getName()+"Second timestamp:"+atomicStampedReference.getStamp()+"Value:"+atomicStampedReference.getReference());
            atomicStampedReference.compareAndSet(20.1, atomicStampedReference.getStamp(), atomicStampedReference.getStamp() + 1);
            System.out.println(Thread.currentThread().getName()+"3rd time stamp:"+atomicStampedReference.getStamp()+"Value:"+atomicStampedReference.getReference());

        },"t2").start(); }}Copy the code

The console

T1 first1Time stamp:1Value is:1T2 first1Time stamp:1Value is:1T2 first2Time stamp:2Value is:20T2 first3Time stamp:3Value is:1T1 Check whether the CAS is successful.falseT1 Current latest timestamp:3The latest value is:1
Copy the code