Introduction to the

CAS stands for compare and Swap, and is the basis of the Java synchronization classes, which in java.util.Concurrent use CAS to implement their atomicity.

The principle of CAS is very simple, to ensure that in a multi-threaded environment we update the object as expected, or that when one thread updates an object, no other thread changes the object. Before the thread updates an object (or value), it saves the value before the update, and then passes in the saved value during the actual update. If the value is consistent, the update will be performed. Otherwise, the update fails.

Note that CAS is implemented in Java in a native way, taking advantage of the atomic operations provided by the system itself.

So what are the problems in using CAS? Generally speaking, if CAS design is not perfect, ABA problems may occur, and ABA problems can be divided into two categories, let’s first look at the first category.

More highlights:

  • Blockchain from getting started to Giving up series tutorials – with ongoing updates covering cryptography, Hyperledger, Ethereum,Libra, Bitcoin and more
  • Spring Boot 2.X Series tutorials: Learn Spring Boot from Scratch in seven days – continuous updates
  • Spring 5.X Series tutorials: Everything you can think of in Spring5 – constantly updated
  • Java Programmer from Handyman to Expert to God (2020 edition) – Ongoing updates with detailed articles and tutorials

For more, visit www.flydean.com

The first kind of question

Consider the following case of ABA:

  1. In a multithreaded environment, thread A reads object A from the shared address X.
  2. Before thread A is ready to update address X, thread B changes the value in address X to B.
  3. Thread B then changes the value of address X back to A.
  4. The latest thread A executes CAS on address X and finds that object A is still stored in X. The object matches and the CAS succeeds.

In the example above, the CAS succeeded, but in fact the CAS is not an atomic operation, and there may be hidden bugs if we try to rely on CAS to implement atomic operations.

The key to the first type of problem is in steps 2 and 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, 2,3 is not possible because in Java, two objects are equal as long as they have the same address.

Step 2,3 is possible in a programming language like C++ that doesn’t have an automatic GC environment. Since we can control the life cycle of objects, if we delete an object from a list and then re-allocate an object and add it back to the list, then according to MRU memory allocation algorithm, The new object will most likely have the same memory address as the deleted object. This can lead to ABA problems.

Problem of the second kind

If we were in a programming language with automatic GC, would there still be a CAS problem?

Consider the case where we have A list with data A->B->C, and we want to perform A CAS operation to replace A with D to generate A list D->B->C. Consider the following steps:

  1. Thread A reads the head node A of the linked list.
  2. Thread B removes node B from the list and the list becomes A->C
  3. Thread A performs the CAS operation to replace A with D.

Our final list is D->C, not D->B->C.

What’s the problem? The CAS compares node A to the latest header node, and it does not care whether node A’s content changes between steps 1 and 3.

Let’s take an example:

public void useABAReference(a){
        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("{}",atomicReference.compareAndSet(a,c));
    }
Copy the code

In the example above, we use the CAS method of the AtomicReference to determine if the object has changed. After CAS B and A, we modified the name of A. Let’s look at the final output:

[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
Copy the code

The result of all three CAS is true. This indicates that CAS does not care about the changes in the contents of the unified object.

The second type of problem may result in some collection class operations that are not atomic, because you cannot guarantee that other nodes will send changes during the CAS process.

The solution of the first type of problem

The first type of problem doesn’t exist in languages with automatic GC, so let’s focus on how to solve it in languages like C++.

According to the authorities, there are roughly four solutions to the first type of problem:

  1. Use intermediate nodes – Use intermediate nodes that do not represent any data to indicate that some nodes are marked for deletion.
  2. Use automatic GC.
  3. Using Hazard Pointers – Hazard Pointers saves the addresses of nodes that are being accessed by the current thread. Nodes in these Hazard Pointers cannot be modified or deleted.
  4. Use read-copy update (RCU) – a copy of the new structure is made before each update.

The solution of the second type of problem

The second type of problem is actually the CAS problem of the global collection object. A simple solution is to add a version number every time you make a CAS update. If the version number is not the expected version, another thread has updated some nodes in the collection, and the CAS failed this time.

Here’s an example of an AtomicStampedReference:

public void useABAStampReference(a){
        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,0.1));
        log.info("{}",atomicStampedReference.compareAndSet(b,a,1.2));
        log.info("{}",atomicStampedReference.compareAndSet(a,c,0.1));
    }
Copy the code

The compareAndSet method of AtomicStampedReference has two extra parameters, expectedStamp and newStamp, which are both ints and need to be passed in manually.

conclusion

ABA problems are actually composed of two types of problems that need to be treated and solved separately.

Examples for this article github.com/ddean2009/ learning-Java-base-9-to-20

Author: Flydean program stuff

Link to this article: www.flydean.com/aba-cas-sta…

Source: Flydean’s blog

Welcome to pay attention to my public number: procedures those things, more wonderful waiting for you!