I. overview

1. CAS, Compare And Swap, that is, compare and exchange. When Doug Lea is implementing synchronous components, CAS technology is used extensively and Java multi-threaded concurrent operation is implemented artificially.
2. The whole AQS synchronization component, Atomic atom class operation, etc. are implemented by base CAS. Even Concurrent HashMap is adjusted to CAS + synchronized in JDK 1.8. It can be said that CAS is the cornerstone of the whole J.U.C.

CAS Analysis

1. In CAS, there are three parameters: memory value V, old expected value A and updated value B. If and only if the value of memory value V equals the old expected value A, the value of memory value V will be changed to B, otherwise nothing will be done. Its pseudocode is as follows:

if (this.value == A) {
	this.value = B
	return true;
} else {
	return false;
}

2. Atomic classes under J.U.C. are all implemented by CAS. Next, take Atomic Integer as an example to illustrate the implementation of CAS. As follows:

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

static {
    try {
        valueOffset = unsafe.objectFieldOffset
            (AtomicInteger.class.getDeclaredField("value"));
    } catch (Exception ex) { throw new Error(ex); }
}

private volatile int value;

Unsafe is the core class of CAS. Java can not access the underlying operating system directly, but through the local native method. Nevertheless, the JVM opens a back door: Unsafe, which provides hardware-level atomic operations.

valueOffset is the offset address of variable value in memory. Unsafe is to get the original value of data by offset address. The current value of value, modified with volatile, ensures that the same is seen in a multithreaded environment.

III. Atomic Integer

1. Let's use Atomic Integer's # addAndGet() method to illustrate, first look at the source code:

// AtomicInteger.java
public final int addAndGet(int delta) {
    return unsafe.getAndAddInt(this, valueOffset, delta) + delta;
}

// Unsafe.java
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;
}

2. Call unsafe's # getAndAddInt(Object var1, long var2, int var4) method internally. In the # getAndAddInt(Object var1, long var2, int var4) method, mainly look at the # compareAndSwapInt(Object var1, long var2, int var4, int var5) method. The code is as follows:

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

This method is a local method and has four parameters, which represent the object, the address of the object, the expected value and the modified value.

IV. CPU Atomic Operation

1.CAS guarantees that a read-rewrite operation is an atomic operation, which is easy to implement on a single processor, but a little complicated to implement on a multi-processor. CPU provides two ways to implement multiprocessor atomic operations: bus locking or cache locking.

• Bus Locking: Bus Locking is the use of a LOCK # signal provided by the processor. When a processor outputs this signal on the bus, requests from other processors will be blocked, so the processor can use shared memory exclusively. But this kind of processing method seems a bit arbitrary, unkind, he locked the communication between CPU and memory, during the lock period, other processors can not use other memory address data, its overhead is a little big. So there's a cache lock.
• Cache Locking: In fact, for the above situation, we just need to ensure that at the same time, the operation of a memory address is atomic. Cache locking means that if the data cached in the memory area is written back to memory during the lock operation, the processor will no longer output LOCK# signal, but modify the internal memory address and use the cache consistency protocol to ensure atomicity. Cache consistency mechanism can ensure that the data in the same memory area can only be modified by one processor. That is to say, when CPU1 modifies the i in the cached rows, CPU2 can not cache the i cached rows at the same time.

V. CAS Defects

1.CAS solves atomic operation efficiently, but there are still some defects, mainly in three aspects:

• Too long cycle time
• Only one shared variable atomic operation can be guaranteed
• ABA problem

6. Too Long Cycle Time

• What if CAS has been unsuccessful? This situation is absolutely possible, if spin CAS is unsuccessful for a long time, it will bring great CPU overhead. In J.U.C., there are places that limit the number of CAS spins, such as Synchronous Queue of BlockingQueue.

7. Only one shared variable atomic operation can be guaranteed.

• If you look at the implementation of CAS, you know that it can only be used for one shared variable. If you have multiple shared variables, you can only use locks. Of course, if you have a way to integrate multiple variables into one variable, using CAS is also good. For example, the position of state in read-write locks.

VIII. ABA Problem

• CAS needs to check whether the operation value has changed, and update if it has not. But there is a situation: if a value is a, B, and then a, it will not change when CAS is checked, but it has changed in essence, which is the so-called ABA problem. The solution to ABA problem is to add a version number, that is, to add a version number to each variable, and add 1 to each change, that is, A - > B - > A, to become 1A - > 2B - > 3A.

Nine, influence

An example is given to illustrate the impact of ABA problems.

There is a list of links as follows:

Suppose we want to replace A with B, that is, compare AndSet (this, A, B). Before thread 1 performs A instead of B, thread 2 first performs the following actions, A and B go out of the stack, then C and A go into the stack, and finally the list is as follows:

When thread 1 finds out that thread 1 is still A, then # compareAndSet(this, A, B) succeeds, but there will be a problem when it is B.next = null, so # compareAndSet(this, A, B) will cause C to be lost, only one B element will be changed to stack, and C will be lost without any reason.

Solution Atomic Stamped Reference

1.CAS ABA hidden trouble problem, the solution is version number, Java provides Atomic Stamped Reference to solve. Atomic Stamped Reference stamp s the version of an object by wrapping tuples of [E,Integer] to avoid ABA problems. For the above case, thread 1 should fail.

2. Atomic StampedReference's # compareAndSet(...) method, code as follows:

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)));
}

There are four method parameters, respectively: expected reference, updated reference, expected flag, updated flag. The source code part is well understood:

• Expected reference == current reference
• Expected identifier == current identifier
• If the updated reference and flag are equal to the current reference and flag, return true directly
• A new Pair object is generated by Pair#of(T reference, int stamp) method and replaced with the current Pair CAS.

Pair is an internal class of Atomic StampedReference. It is mainly used to record reference and version stamp information (identification). It is defined as follows:

// AtomicStampedReference.java

private static class Pair<T> {
    final T reference; // object reference
    final int stamp; // Version 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);
    }
}

private volatile Pair<V> pair;

• Pair records the object's reference and version stamp, which is int type and keeps increasing. Pair is also an immutable object whose properties are all defined as final. Provide a # of(T reference, int stamp) method, which returns a new Air object.
• The pair attribute, defined as volatile, ensures visibility in a multithreaded environment. In Atomic Stamped Reference, most methods generate a new Pair object by calling Pair's (T reference, int stamp) method and assign it to the variable pair. For example, set(V newReference, int newStamp) method, the code is as follows:

// AtomicStampedReference.java
public void set(V newReference, int newStamp) {
    Pair<V> current = pair;
    if (newReference != current.reference || newStamp != current.stamp)
        this.pair = Pair.of(newReference, newStamp);
}

11. Practical cases

Next, we'll show an example of the difference between Atomic Stamped Reference and Atomic Integer. We define two threads, thread 1 is responsible for 100 - > 110 - > 100, thread 2 is responsible for executing 100 - > 120, see the difference between the two.

public class Test {
    private static AtomicInteger atomicInteger = new AtomicInteger(100);
    private static AtomicStampedReference atomicStampedReference = new AtomicStampedReference(100,1);

    public static void main(String[] args) throws InterruptedException {

        // AtomicInteger
        Thread at1 = new Thread(new Runnable() {
            @Override
            public void run() {
                atomicInteger.compareAndSet(100,110);
                atomicInteger.compareAndSet(110,100);
            }
        });

        Thread at2 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    TimeUnit.SECONDS.sleep(2);      // at1, Execution Completed
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("AtomicInteger:" + atomicInteger.compareAndSet(100,120));
            }
        });

        at1.start();
        at2.start();

        at1.join();
        at2.join();

        // AtomicStampedReference

        Thread tsf1 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    //Let tsf2 get stamp first, resulting in inconsistent anticipated timestamps
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                // Expected Reference: 100, Updated Reference: 110, Expected Identity getStamp() Updated Identity getStamp() +1
                atomicStampedReference.compareAndSet(100,110,atomicStampedReference.getStamp(),atomicStampedReference.getStamp() + 1);
                atomicStampedReference.compareAndSet(110,100,atomicStampedReference.getStamp(),atomicStampedReference.getStamp() + 1);
            }
        });

        Thread tsf2 = new Thread(new Runnable() {
            @Override
            public void run() {
                int stamp = atomicStampedReference.getStamp();

                try {
                    TimeUnit.SECONDS.sleep(2);      //Thread tsf1 Executed
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("AtomicStampedReference:" +atomicStampedReference.compareAndSet(100,120,stamp,stamp + 1));
            }
        });

        tsf1.start();
        tsf2.start();
    }

}

Operation results:

 

 

The running results fully demonstrate the ABA problem caused by Atomic Integer and solve the ABA problem with Atomic Stamped Reference.

Last

If you see it here and think it's a good article, give it a compliment! _____________ Welcome to comment and discuss! If you think it's worth improving, please leave me a message. We will make serious inquiries, correct shortcomings, and regularly share technical dry goods free of charge. Like the little partner can pay attention to oh. Thank you!