Java Concurrency Basics - CAS - Moment For Technology

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

CAS (Compare and Swap), which can be understood as “Compare and replace” in Chinese, is a technology often used to implement concurrent algorithms. It is a kind of lock-free atom algorithm, is a kind of optimistic lock implementation way, in the operation is optimistic attitude, it always thinks that the operation can be successfully completed.

CAS thinking

Let’s first intuitively understand the general idea of CAS:

CAS (V, E, N)Copy the code

It takes three arguments, V for the value of the variable to be updated, E for the expected value, and N for the new value. The value of V is set to N only if V is equal to E. If V and E are different, another thread has already done the update, and the current thread does nothing. Finally, CAS returns the true value of the current V.

Let’s start with a simple example:

public class CasTest0 {
    private static volatile int m = 0;
    public static void increase1(a) {
        m++;
    }

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 1000; i++) {
           new Thread(() -> {
                CasTest0.increase1();
            }).start();
        }
        TimeUnit.SECONDS.sleep(3); System.out.println(m); }}public class CasTest0 {
    private static volatile int m = 0;
    public static void increase1(a) {
        m++;
    }

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 1000; i++) {
           new Thread(() -> {
                CasTest0.increase1();
            }).start();
        }
        TimeUnit.SECONDS.sleep(3); System.out.println(m); }}Copy the code

Run this example, and the final printed value could be any positive integer less than 1000. As mentioned in the previous article, volatile guarantees visibility and order, but not atomicity. M++ is not an atomic operation and can be divided into three steps:

Get static variable m to stack, int constant 1 to stack
Stack top adds values of int type and pushes the result to the top of the stack
Assign to the static variable m

It can be seen from the above analysis that the autoincrement operation does not have atomicity, so in the multi-threaded environment, the result obtained by running must be less than or equal to 1000.

CAS implementation in JUC

Next, switch to the atomic class operation under JUC package and try:

public class CasTest1 {
    private static AtomicInteger atomicI = new AtomicInteger(0);  
    public static void increase2(a) {
        atomicI.incrementAndGet(); 
    }

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 1000; i++) {
            new Thread(() -> {
                CasTest1.increase2();
            }).start();
        }
        TimeUnit.SECONDS.sleep(3); System.out.println(atomicI.get()); }}public class CasTest1 {
    private static AtomicInteger atomicI = new AtomicInteger(0);  
    public static void increase2(a) {
        atomicI.incrementAndGet(); 
    }

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 1000; i++) {
            new Thread(() -> {
                CasTest1.increase2();
            }).start();
        }
        TimeUnit.SECONDS.sleep(3); System.out.println(atomicI.get()); }}Copy the code

The result will always return 1000, depending on where the atom Integer class AtomicInteger comes in. Decompile to see what is actually being done. Here, increment is done with only one instruction

Look at the implementation of the AtomicInteger class:

The Unsafe class is used in AtomicInteger, which is essentially a backclass provided by Java for manipulating memory addresses directly. Looking beyond broadening, an earlier article on the Unsafe class, Java double-edged sword, addressed broadening concerns over food, such as food, food, and food.

The variables in the code represent the following meanings:

valueOffset: Address offset of the variable value, which is assigned in the following static code block
value: Indicates the value to be modified, which is equivalent to I in the I ++ operation

IncrementAndGet eventually calls the method in the Unsafe class:

// Get the value of the variable whose memory address is obj+offset and add delta to it
public final int getAndAddInt(Object obj, long offset, int delta) {
    int v;
    do {
        // Get the value of a variable by object and offset
        // Because of the volatile modifier, all threads see v the same
        v= this.getIntVolatile(obj, offset);
    } while(!this.compareAndSwapInt(obj, offset, v, v + delta));
    return v;
}
Copy the code

Specific process:

In the while loopcompareAndSwapInt()The v method attempts to change the value of v, and passesobjandoffsetGets the value of a variable
If this value is different from v, another thread has changed itobj+offsetThe value at the address, at this timecompareAndSwapInt()Return false and continue the loop
If this value is the same as v, no other threads have modified itobj+offsetThe value at the addressobj+offsetChange the value at the address tov+delta.compareAndSwapInt()Return true to exit the loop

CompareAndSwapInt is a native method that calls a c++ method, followed by the CMPXCHG instruction in assembly, which is finally implemented through binary hardware support.

So, what are the application scenarios of CAS? A typical scenario is the inventory management of goods in e-commerce. First, read the inventory from the database. When updating the inventory after selling the goods, judge whether the inventory quantity is still the same as when you took it out. If so, update it.

ABA problem

Having said that, is CAS perfect? Unfortunately not, CAS still has the classic ABA problem:

According to our previous understanding, CAS needs to check whether the operation value has changed, and update it if it has not. But there is A situation where if A value is A, changes to B, and then changes to A, CAS checks that it has not changed, but it has changed. This is called the ABA problem.

public class CasTest2 {
    private static AtomicInteger atomicI = new AtomicInteger(100);

    public static void main(String[] args) throws Exception {
        Thread t1 = new Thread(() -> {
            System.out.println(Thread.currentThread().getName()+":"+atomicI.compareAndSet(100.110));
        },"thread1");
        t1.start();

        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run(a) {
                try {
                    TimeUnit.SECONDS.sleep(1);
                    System.out.println(Thread.currentThread().getName()+":"+atomicI.compareAndSet(110.100));
                } catch(InterruptedException e) { e.printStackTrace(); }}},"thread2");
        t2.start();

        Thread t3 = new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(3);
                System.out.println(Thread.currentThread().getName()+":"+atomicI.compareAndSet(100.90));
            } catch(InterruptedException e) { e.printStackTrace(); }},"thread3"); t3.start(); }}Copy the code

Running results:

All three threads run true, but thread3 checks for a value that has been changed mid-stream, not the original value.

The solution to the ABA problem is to add a version number, that is, add a version number to each variable and add 1 each time it changes.

Change: A -- > B -- > A to 1A -- > 2B -- > 3ACopy the code

The AtomicStampedReference class maintains not only the object value but also an int stamp value, which can be interpreted as a timestamp or version number. When the value corresponding to the AtomicStampedReference is modified, the stamp value must be updated in addition to the data. If the object value of AtomicStampedReference is set, the object value and stamp value must meet the expectations. The write is successful. Therefore, even if the object value is repeatedly read and written back to the original value, improper writing can be prevented as long as the value of stamp changes.

public class CasTest3 {
    private static AtomicStampedReference asr = new AtomicStampedReference(100.1);
    public static void main(String[] args) throws Exception {
        Thread t1 = new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(2);
            } catch (Exception e) {
                e.printStackTrace();
            }
            System.out.println("1:" + asr.compareAndSet(100.110, asr.getStamp(), asr.getStamp() + 1)); System.out.println("stamp:"+asr.getStamp()+" value:"+asr.getReference());
            System.out.println("2:" + asr.compareAndSet(110.100, asr.getStamp(), asr.getStamp() + 1)); System.out.println("stamp:"+asr.getStamp()+" value:"+asr.getReference());
        });

        Thread t2 = new Thread(() -> {
            int stamp = asr.getStamp();
            try {
                TimeUnit.SECONDS.sleep(4);
            } catch (Exception e) {
                e.printStackTrace();
            }
            System.out.println("3:" + asr.compareAndSet(100.110, stamp, stamp + 1)); System.out.println("stamp:"+asr.getStamp()+" value:"+asr.getReference()); }); t1.start(); t2.start(); }}Copy the code

Running results:

Thread2 expects a stamp value of 1 and a Reference value of 100. When Thread1 increments each time, the stamp value increases by 1. Therefore, after Thread1 modifies the Reference value twice, no modification is made even if the Reference value is the same as the expected value but the stamp value is different.

CAS shortcomings

Finally, the disadvantages of CAS are summarized. Although CAS effectively solves the problem of atomic operation, it still has some defects, mainly in three aspects:

Too long loop time: If the CAS is never successful, the spin operation will continue, causing a lot of CPU execution overhead. There are places in JUC that limit the number of CAS spins, for exampleBlockingQueuetheSynchronousQueue
Only one shared variable atom operation can be guaranteed: CAS can only be applied to one shared variable. If multiple shared variables are used, a lock must be used to ensure atomicity
ABA problem: CAS needs to check if the value of the operation has changed and update it if it has not, but the ABA problem mentioned earlier can have an effect, so it can be qualified by adding the version number

The last

If you think it is helpful, you can like it and forward it. Thank you very much

Public number agriculture ginseng, add a friend, do a thumbs-up friend ah

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Java Concurrency Basics – CAS

CAS thinking

CAS implementation in JUC

ABA problem

CAS shortcomings

The last

Java Concurrency Basics – CAS

CAS thinking

CAS implementation in JUC

ABA problem

CAS shortcomings

The last

Related Posts

Learn about InnoDB memory structure and its principle in detail

Virtual Machine family: Memory allocation in the JVM

Storm series (3) Java to write the first Storm program