Non blocking synchronization mechanism and CAS

Non blocking synchronization mechanism and CAS

We know that before Java 5, synchronization is achieved through the synchronized keyword. After Java 5, Java util. Many synchronization classes with more powerful performance have been added to the concurrent package. Many of these powerful classes implement non blocking synchronization mechanisms to help them improve performance.

What is nonblocking synchronization

Non blocking synchronization means that multiple threads will not block when competing for the same data, so they can coordinate in a more fine-grained dimension, which greatly reduces the overhead of thread scheduling and improves efficiency. There is no lock mechanism in non blocking algorithm, so there is no deadlock problem.

In the lock based algorithm, if one thread holds a lock, other threads will not be able to continue. Although using locks can ensure consistent access to resources, there is a very large overhead in the process of suspending and resuming thread execution. If there is a lot of competition on locks, the scheduling overhead may be higher than the actual work overhead.

Pessimistic lock and optimistic lock

We know that an exclusive lock is a pessimistic lock. A pessimistic lock means that in the worst case, if you do not lock the resource, other threads will modify the resource. Pessimistic lock can ensure the smooth execution of tasks, but its efficiency is not high.

Optimistic locking assumes that other threads will not change the resource to be processed, but we need to judge whether the resource has been changed by other threads when updating the resource. If it is changed, the update fails. We can try again. If it is not changed, the update succeeds.

The premise of using optimistic lock is that the system will not conflict with the update of resources most of the time.

The atomic comparison and update operations of optimistic locks are generally supported by the underlying hardware.

CAS

Most processors implement a CAS instruction (compare and swap). Generally speaking, a CAS receives three parameters: the present value V of the data, the value a for comparison, and the value B to be written. B is written only when V and a are equal. V is returned whether the writing is successful or not "I think the current value of V is a. if so, update the value of V to B. otherwise, do not modify the value of V and tell me what the current value of V is."

This is the meaning of CAS. The concurrent class in JDK uses CAS by using unsafe class. We can build a concurrent class ourselves, as shown below:

public class CasCounter {

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

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

    public CasCounter(int initialValue) {
        value = initialValue;
    }

    public CasCounter() {
    }

    public final int get() {
        return value;
    }

    public final void set(int newValue) {
        value = newValue;
    }

    public final boolean compareAndSet(int expect,int update) {
        return unsafe.compareAndSwapInt(this,valueOffset,expect,update);
    }

}

In the above example, we define an atomic operation compareandset, which internally calls the compareandswapint method of unsafe.

It seems that the use of CAS above is more complex than the direct use of locks, but in fact, it is necessary to traverse a very complex code path in the JVM when implementing locking in the JVM, which may lead to operating system level locking, thread hang up, context switching and other operations. In the best case, locking requires a CAS command to be executed once.

The main disadvantage of CAS is that the caller needs to deal with the competition problems (retry, fallback, give up) by himself, and these problems can be handled automatically in the lock.

In the previous article, we also talked about atomic variables. CAS is used at the bottom of atomic variables.

For examples of this article, please refer to https://github.com/ddean2009/learn-java-concurrency/tree/master/CAS

For more information, please visit flybean's blog