brief introduction

The full name of CAS is compare and swap, which is the basis of Java synchronization class, Java util. Synchronization classes in concurrent basically use CAS to achieve their atomicity.

The principle of CAS is actually very simple. In order to ensure that our update is expected in a multi-threaded environment, or when a thread updates an object, no other thread modifies the object. Before the thread updates an object (or value), save the value before the update, and then pass in the previously saved value during the actual update for comparison. If it is consistent, update it, otherwise it fails.

Note that CAS is implemented in Java using the native method, using the atomic operations provided by the system itself.

So what problems will CAS have in use? Generally speaking, if CAS is not designed perfectly, ABA problems may occur, and ABA problems can be divided into two categories. Let's look at one category first.

More highlights:

The first kind of problem

We consider the following ABA case:

In the above example, CAS is successful, but in fact, CAS is not an atomic operation. If we want to rely on CAS to realize atomic operation, there may be hidden bugs.

The key to the first type of problem is step 2 and step 3. In these two steps, we can see that thread B directly replaces the contents of memory address X.

In a programming language with an automatic GC environment, such as Java, the case of 2 and 3 is impossible, because in Java, as long as the addresses of two objects are consistent, it means that the two objects are equal.

The possible situations of steps 2 and 3 are in a programming language like C + + that does not have an automatic GC environment. Because we can control the life cycle of objects by ourselves, if we delete an object from a list, then reassign an object and add it back to the list, according to the MRU memory allocation algorithm, the memory address of this new object is likely to be the same as that of the previously deleted object. This will lead to ABA problems.

The second kind of problem

If we are in a programming language with automatic GC, is there still a CAS problem?

Consider the following situation. The data in a linked list is a - > b - > C. We want to perform a CAS operation, replace a with D, and generate a linked list D - > b - > C. Consider the following steps:

Finally, our linked list is D - > C, not D - > b - > C.

What's the problem? Whether the node a compared by CAS and the latest header node are the same node does not care whether the content of node a changes between steps 1 and 3.

Let's take an example:

public void useABAReference(){
        CustUser a= new CustUser();
        CustUser b= new CustUser();
        CustUser c= new CustUser();
        AtomicReference<CustUser> atomicReference= new AtomicReference<>(a);
        log.info("{}",atomicReference.compareAndSet(a,b));
        log.info("{}",atomicReference.compareAndSet(b,a));
        a.setName("change for new name");
        log.info("{}",c));
    }

In the above example, we used the CAS method of atomicreference to determine whether the object has changed. After CAS B and a, we modified the name of A. let's see the final output:

[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true

The results of the three CAS are true. It indicates whether CAS does compare the two objects as a unified object, and does not care about the changes of their contents.

The second kind of problem may cause that the operations of some collection classes are not atomic, because you can't guarantee whether other nodes send changes in the process of CAS.

Solution of the first kind of problems

The first kind of problem does not exist in programming languages with automatic GC. We mainly look at how to solve this problem in languages such as C + +.

According to the official statement, there are about four solutions to the first type of problem:

Solution of the second kind of problems

The second kind of problem is actually the CAS problem of the whole set object. A simple solution is to add a version number every time CAS is updated. If the version number is not the expected version, it indicates that other threads have updated some nodes in the collection. This time, CAS fails.

Let's take an example of atomicstampedreference:

public void useABAStampReference(){
        Object a= new Object();
        Object b= new Object();
        Object c= new Object();
        AtomicStampedReference<Object> atomicStampedReference= new AtomicStampedReference(a,0);
        log.info("{}",atomicStampedReference.compareAndSet(a,b,1));
        log.info("{}",atomicStampedReference.compareAndSet(b,a,1,2));
        log.info("{}",c,1));
    }

The compareandset method of atomicstampedreference has two additional parameters, expectedstamp and newstamp. Both parameters are int type and need to be passed in manually.