A brief introduction to thread safety implementation in Java and CLH queue principle (code example)

This article brings you a brief introduction (code example) about thread safety implementation in Java and CLH queue principle. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. help.

Blocking synchronization

In Java, we often use the synchronized keyword to achieve mutually exclusive synchronization to solve multi-thread concurrency Issues accessing shared data. After the synchronzied keyword is compiled, two bytecode instructions, monitorenter and monitorexit, will be added before and after the synchronization code block contained in synchronized. The synchronized keyword requires specifying an object for locking and unlocking. For example:

public class Main {

    private static final Object LOCK = new Object();
    
    public static void fun1() {
        synchronized (LOCK) {
            // do something
        }
    }
    
    public static void fun2() {
        synchronized (LOCK) {
            // do something
        }
    }
}

When the object is not explicitly specified, whether the synchonized modification is an instance method or a static method determines whether to use the object instance or the class instance of the class as the object. For example:

public class SynchronizedTest {
    public synchronized void doSomething() {
        //采用实例对象作为锁对象
    }
}

public class SynchronizedTest {
    public static synchronized void doSomething() {
        //采用SynchronizedTest.class 实例作为锁对象
    }
}

Due to the blocking mutual exclusion based on synchronized implementation, in addition to blocking the operating thread, it also needs to wake up or block the native thread at the operating system level, and needs to transition from the user state to the kernel state. The conversion of this state consumes The time may be longer than the execution time of user code, so we often say that synchronized is a "heavyweight lock" in the Java language.

Non-blocking synchronization

Optimistic locking and pessimistic locking

Synchronization using the synchronized keyword The main problem with this method is the performance consumption caused by thread blocking and waking up. Blocking synchronization is a pessimistic concurrency strategy. As long as there is a possibility of competition, it believes that locking must be performed.
However, the synchronization strategy has another optimistic strategy. The optimistic concurrency strategy advances the operation of data. If it is not found that other threads have also operated on the data, then the operation is considered successful. If other threads also operate data, generally retry continuously until success. This optimistic locking strategy does not require thread blocking and is a method of non-blocking synchronization.

CAS

The optimistic concurrency strategy mainly has two important stages, one is to operate the data, and the other is to detect conflicts, that is, to detect whether other threads have None also performed operations on this data. The data operations and conflict detection here need to be atomic, otherwise problems similar to i will easily occur.
CAS means compare and swap. At present, most CPUs natively support CAS atomic instructions. For example, in the instruction sets of IA64 and x86, there are instructions such as cmpxchg to complete the CAS function. Its atomicity requirement is Guaranteed at the hardware level.
The CAS instruction generally requires three parameters, namely the memory address of the value, the expected old value and the new value. When the CAS instruction is executed, if the value at the memory address matches the expected old value, the processor will update the value at the memory address with the new value, otherwise it will not update. This operation is guaranteed to be atomic within the CPU.
There are many CAS-related APIs in Java. The most common ones we have are various atomic classes under the java.util.concurrent package, such as AtomicInteger, AtomicReferenceetc.
These classes all support CAS operations, and they actually rely internally on the compareAndSwapInt() and compareAndSwapLong() methods in sun.misc.Unsafe.
CAS is not perfect. Although it can guarantee atomicity, it has a famous ABA problem. The value of a variable is A when it is read for the first time, and it is A when it is read again. So can we explain that this variable has not changed between the two reads? cannot. During this period, the variable may change from A to B, and then from B to A. When reading for the second time, you see A, but in fact the variable has changed. The general code logic will not care about this ABA problem, because according to the code logic it will not affect the security of concurrency, but if you care, you may consider using blocking synchronization instead of CAS. In fact, the JDK itself also provides a solution to this ABA problem, providing the AtomicStampedReference class to add versions to variables to solve the ABA problem.

Spin lock

Blocking synchronization represented by synchronized, because the blocked thread will resume the thread operation, it needs to involve the user state and kernel state at the operating system level Switching between them has a great impact on the performance of the system. The strategy of the spin lock is that when a thread acquires a lock, if it finds that the lock is already occupied by another thread, it does not immediately give up the execution time slice of the CPU, but enters a "meaningless" loop to see if the thread The lock has been given up.
But the spin lock is suitable for critical sectionsWhen the critical section is relatively small, if the lock is held for too long, the spin operation itself will waste the performance of the system.

The following is a simple spin lock implementation:

import java.util.concurrent.atomic.AtomicReference;
public class SpinLock {
   private AtomicReference owner = new AtomicReference();
   public void lock() {
       Thread currentThread = Thread.currentThread();
        // 如果锁未被占用，则设置当前线程为锁的拥有者
       while (!owner.compareAndSet(null, currentThread)) {}
   }

   public void unlock() {
       Thread currentThread = Thread.currentThread();
        // 只有锁的拥有者才能释放锁
       owner.compareAndSet(currentThread, null);
   }
}

上述的代码中， owner 变量保存获得了锁的线程。这里的自旋锁有一些缺点，第一个是没有保证公平性，等待获取锁的线程之间，无法按先后顺序分别获得锁；另一个，由于多个线程会去操作同一个变量 owner，在 CPU 的系统中，存在着各个 CPU 之间的缓存数据需要同步，保证一致性，这会带来性能问题。

公平的自旋

为了解决公平性问题，可以让每个锁拥有一个服务号，表示正在服务的线程，而每个线程尝试获取锁之前需要先获取一个排队号，然后不断轮询当前锁的服务号是否是自己的服务号，如果是，则表示获得了锁，否则就继续轮询。下面是一个简单的实现：

import java.util.concurrent.atomic.AtomicInteger;

public class TicketLock {
   private AtomicInteger serviceNum = new AtomicInteger(); // 服务号
   private AtomicInteger ticketNum = new AtomicInteger(); // 排队号

   public int lock() {
       // 首先原子性地获得一个排队号
       int myTicketNum = ticketNum.getAndIncrement();
       // 只要当前服务号不是自己的就不断轮询
       while (serviceNum.get() != myTicketNum) {
       }
       return myTicketNum;
    }

    public void unlock(int myTicket) {
        // 只有当前线程拥有者才能释放锁
        int next = myTicket + 1;
        serviceNum.compareAndSet(myTicket, next);
    }
}

虽然解决了公平性的问题，但依然存在前面说的多 CPU 缓存的同步问题，因为每个线程占用的 CPU 都在同时读写同一个变量 serviceNum，这会导致繁重的系统总线流量和内存操作次数，从而降低了系统整体的性能。

MCS 自旋锁

MCS 的名称来自其发明人的名字：John Mellor-Crummey和Michael Scott。
MCS 的实现是基于链表的，每个申请锁的线程都是链表上的一个节点，这些线程会一直轮询自己的本地变量，来知道它自己是否获得了锁。已经获得了锁的线程在释放锁的时候，负责通知其它线程，这样 CPU 之间缓存的同步操作就减少了很多，仅在线程通知另外一个线程的时候发生，降低了系统总线和内存的开销。实现如下所示：

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
public class MCSLock {
    public static class MCSNode {
        volatile MCSNode next;
        volatile boolean isWaiting = true; // 默认是在等待锁
    }
    volatile MCSNode queue;// 指向最后一个申请锁的MCSNode
    private static final AtomicReferenceFieldUpdater UPDATER = AtomicReferenceFieldUpdater
            .newUpdater(MCSLock.class, MCSNode.class, "queue");

    public void lock(MCSNode currentThread) {
        MCSNode predecessor = UPDATER.getAndSet(this, currentThread);// step 1
        if (predecessor != null) {
            predecessor.next = currentThread;// step 2
            while (currentThread.isWaiting) {// step 3
            }
        } else { // 只有一个线程在使用锁，没有前驱来通知它，所以得自己标记自己已获得锁
            currentThread.isWaiting = false;
        }
    }

    public void unlock(MCSNode currentThread) {
        if (currentThread.isWaiting) {// 锁拥有者进行释放锁才有意义
            return;
        }

        if (currentThread.next == null) {// 检查是否有人排在自己后面
            if (UPDATER.compareAndSet(this, currentThread, null)) {// step 4
                // compareAndSet返回true表示确实没有人排在自己后面
                return;
            } else {
                // 突然有人排在自己后面了，可能还不知道是谁，下面是等待后续者
                // 这里之所以要忙等是因为：step 1执行完后，step 2可能还没执行完
                while (currentThread.next == null) { // step 5
                }
            }
        }
        currentThread.next.isWaiting = false;
        currentThread.next = null;// for GC
    }
}

MCS 的能够保证较高的效率，降低不必要的性能消耗，并且它是公平的自旋锁。

CLH 自旋锁

CLH 锁与 MCS 锁的原理大致相同，都是各个线程轮询各自关注的变量，来避免多个线程对同一个变量的轮询，从而从 CPU 缓存一致性的角度上减少了系统的消耗。
CLH 锁的名字也与他们的发明人的名字相关：Craig，Landin and Hagersten。
CLH 锁与 MCS 锁最大的不同是，MCS 轮询的是当前队列节点的变量，而 CLH 轮询的是当前节点的前驱节点的变量，来判断前一个线程是否释放了锁。
实现如下所示：

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
public class CLHLock {
    public static class CLHNode {
        private volatile boolean isWaiting = true; // 默认是在等待锁
    }
    private volatile CLHNode tail ;
    private static final AtomicReferenceFieldUpdater UPDATER = AtomicReferenceFieldUpdater
            . newUpdater(CLHLock.class, CLHNode .class , "tail" );
    public void lock(CLHNode currentThread) {
        CLHNode preNode = UPDATER.getAndSet( this, currentThread);
        if(preNode != null) {//已有线程占用了锁，进入自旋
            while(preNode.isWaiting ) {
            }
        }
    }

    public void unlock(CLHNode currentThread) {
        // 如果队列里只有当前线程，则释放对当前线程的引用（for GC）。
        if (!UPDATER .compareAndSet(this, currentThread, null)) {
            // 还有后续线程
            currentThread.isWaiting = false ;// 改变状态，让后续线程结束自旋
        }
    }
}

从上面可以看到，MCS 和 CLH 相比，CLH 的代码比 MCS 要少得多；CLH是在前驱节点的属性上自旋，而MCS是在本地属性变量上自旋；CLH的队列是隐式的，通过轮询关注上一个节点的某个变量，隐式地形成了链式的关系，但CLHNode并不实际持有下一个节点，MCS的队列是物理存在的，而 CLH 的队列是逻辑上存在的；此外，CLH 锁释放时只需要改变自己的属性，MCS 锁释放则需要改变后继节点的属性。

CLH 队列是 J.U.C 中 AQS 框架实现的核心原理。

The above is the detailed content of A brief introduction to thread safety implementation in Java and CLH queue principle (code example). For more information, please follow other related articles on the PHP Chinese website!