Detailed sample code explaining the principle of reentrant lock in Java

1. Overview

This article first introduces the Lock interface, the class hierarchy of ReentrantLock, and the simple principle of the lock function template class AbstractQueuedSynchronizer, and then explains the internal principles of ReentrantLock by analyzing the lock method and unlock method of ReentrantLock. , and finally make a summary. This article does not cover condition variables in ReentrantLock.

1.1. Lock interface

Lock interface is an abstraction of tools for controlling concurrency. It is more flexible than using the synchronized keyword and can support condition variables. It is a tool for controlling concurrency. Generally speaking, it controls the exclusivity of a certain shared resource. In other words, only one thread can acquire this lock and occupy resources at the same time. If other threads want to acquire the lock, they must wait for this thread to release the lock. ReentrantLock in Java implementation is such a lock. Another kind of lock, which can allow multiple threads to read resources, but can only allow one thread to write resources. ReadWriteLock is such a special lock, referred to as read-write lock. The following is an overall description of several methods of the Lock interface:

Method name	Description
lock	Acquire the lock. If the lock cannot be acquired, then the current thread becomes unschedulable until the lock is acquired
lockInterruptibly	Acquisition lock unless the current thread is interrupted. If the lock is obtained, return immediately. If it cannot be obtained, the current thread becomes unschedulable and sleeps until the following two things happen: 1. The current thread obtains the lock 2. Other threads interrupt the current thread
tryLock	If the lock can be acquired when called, then acquire the lock and return true. If the current lock If it cannot be obtained, then this method will immediately return false
tryLcok(long time, TimeUnit unit)	Try to obtain the lock within the specified time. If the lock can be obtained, then Acquire the lock and return true. If the current lock cannot be acquired, then the current thread becomes unschedulable until one of the following three things happens: 1. The current thread acquires the lock 2. The current thread is interrupted by other threads 3. The specified waiting time is up
unlock	Release the current thread Occupied lock
newCondition	Returns a condition variable associated with the current lock. Before using this condition variable, the current thread must occupy the lock. Calling Condition's await method will atomically release the lock before waiting, and atomically acquire the lock after waiting to be awakened

Next, we will introduce how the entire ReentrantLock works around the two methods of lock and unlock. Before introducing ReentrantLock, let's first take a look at the class hierarchy of ReentrantLock and its closely related AbstractQueuedSynchronizer

1.2, ReentrantLock class hierarchy

ReentrantLock It implements the Lock interface and has three internal classes, Sync, NonfairSync, and FairSync. Sync is an abstract type that inherits AbstractQueuedSynchronizer. This AbstractQueuedSynchronizer is a template class that implements many lock-related functions and provides hook methods for User implementation, such as tryAcquire, tryRelease, etc. Sync implements the tryRelease method of AbstractQueuedSynchronizer. The NonfairSync and FairSync classes inherit from Sync, implement the lock method, and then have different implementations of tryAcquire for fair preemption and unfair preemption respectively.

1.3. AbstractQueuedSynchronizer

First of all, AbstractQueuedSynchronizer inherits from AbstractOwnableSynchronizer. The implementation of AbstractOwnableSynchronizer is very simple. It represents an exclusive synchronizer, and the variable exclusiveOwnerThread is used internally to represent an exclusive thread.

Secondly, AbstractQueuedSynchronizer internally uses the CLH lock queue to turn concurrent execution into serial execution. The entire queue is a doubly linked list. Each node in the CLH lock queue will save references to the previous node and the next node, the thread corresponding to the current node, and a state. This status is used to indicate whether the thread should block. When the previous node of the node is released, the current node is awakened and becomes the head. Newly added nodes will be placed at the end of the queue.

2. Lock method of unfair lock

2.1. Lock method flow chart

2.2. Detailed description of lock method

1. When initializing ReentrantLock, if we do not pass the parameters whether they are fair, then the unfair lock will be used by default, which is NonfairSync.

2. When we call the lock method of ReentrantLock, we actually call the lock method of NonfairSync. This method first uses CAS operation to try to seize the lock. If successful, the current thread is set on this lock, indicating that the preemption is successful. If it fails, call the acquire template method and wait for preemption. The code is as follows:

static final class NonfairSync extends Sync {
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

        protected final boolean tryAcquire(int acquires) {
            return nonfairTryAcquire(acquires);
        }
}

3. Calling acquire(1) actually uses the acquire method of AbstractQueuedSynchronizer, which is a set of lock preemption templates. The overall principle is to try to acquire the lock first. If the acquisition is not successful, Just add a node of the current thread in the CLH queue, indicating that it is waiting for preemption. Then enter the preemption mode of the CLH queue. When entering, it will also perform an operation to acquire the lock. If it still cannot be obtained, LockSupport.park is called to suspend the current thread. So when will the current thread be awakened? When the thread holding the lock calls unlock, it will wake up the thread on the node next to the head node of the CLH queue and call the LockSupport.unpark method. The acquire code is relatively simple, as follows:

public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
}

3.1. The tryAcquire hook method is first used inside the acquire method to try to acquire the lock again. This method actually uses nonfairTryAcquire in the NonfairSync class. The specific implementation principle is to first Compare whether the current lock status is 0. If it is 0, try to atomically seize the lock (set the status to 1, and then set the current thread to an exclusive thread). If the current lock status is not 0, compare the current thread and Is the thread occupying the lock a thread? If so, it will increase the value of the state variable. It can be seen from this that the reason why the reentrant lock is reentrant is that the same thread can repeatedly use the lock it occupies. If neither of the above conditions pass, return false on failure. The code is as follows:

final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }

3.2. Once tryAcquire returns false, it will enter the acquireQueued process, which is the preemption mode based on the CLH queue:

3.2.1. First, at the end of the CLH lock queue Add a waiting node. This node saves the current thread. This is achieved by calling addWaiter. Here you need to consider the initialization situation. When the first waiting node enters, you need to initialize a head node and then add the current node to the tail. The follow-up is directly Just add nodes at the end.

The code is as follows:

private Node addWaiter(Node mode) {
		// 初始化一个节点，这个节点保存当前线程
        Node node = new Node(Thread.currentThread(), mode);
        // 当CLH队列不为空的视乎，直接在队列尾部插入一个节点
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
		// 当CLH队列为空的时候，调用enq方法初始化队列
        enq(node);
        return node;
}

private Node enq(final Node node) {
        for (;;) {
            Node t = tail;
            if (t == null) { // 初始化节点，头尾都指向一个空节点
                if (compareAndSetHead(new Node()))
                    tail = head;
            } else {// 考虑并发初始化
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
}

3.2.2. After adding the node to the CLH queue, enter the acquireQueued method.

First of all, the outer layer is an infinite for loop. If the current node is the next node of the head node and the lock is obtained through tryAcquire, it means that the head node has released the lock and the current thread It is awakened by the thread of the head node. At this time, you can set the current node as the head node, set the failed flag to false, and then return. As for the previous node, its next variable is set to null and will be cleared during the next GC.

如果本次循环没有获取到锁，就进入线程挂起阶段，也就是shouldParkAfterFailedAcquire这个方法。

代码如下：

final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
}

3.2.3、如果尝试获取锁失败，就会进入shouldParkAfterFailedAcquire方法，会判断当前线程是否挂起，如果前一个节点已经是SIGNAL状态，则当前线程需要挂起。如果前一个节点是取消状态，则需要将取消节点从队列移除。如果前一个节点状态是其他状态，则尝试设置成SIGNAL状态，并返回不需要挂起，从而进行第二次抢占。完成上面的事后进入挂起阶段。

代码如下：

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            //
            return true;
        if (ws > 0) {
            //
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            //
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

3.2.4、当进入挂起阶段，会进入parkAndCheckInterrupt方法，则会调用LockSupport.park(this)将当前线程挂起。代码：

private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
}

三、 非公平锁的unlock方法

3.1、unlock方法的活动图

3.2、unlock方法详细描述

1、调用unlock方法，其实是直接调用AbstractQueuedSynchronizer的release操作。

2、进入release方法，内部先尝试tryRelease操作,主要是去除锁的独占线程，然后将状态减一，这里减一主要是考虑到可重入锁可能自身会多次占用锁，只有当状态变成0，才表示完全释放了锁。

3、一旦tryRelease成功，则将CHL队列的头节点的状态设置为0，然后唤醒下一个非取消的节点线程。

4、一旦下一个节点的线程被唤醒，被唤醒的线程就会进入acquireQueued代码流程中，去获取锁。

具体代码如下：

unlock代码：

public void unlock() {
        sync.release(1);
}

release方法代码：

public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
}

Sync中通用的tryRelease方法代码：

protected final boolean tryRelease(int releases) {
     int c = getState() - releases;
    if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
          free = true;
          setExclusiveOwnerThread(null);
    }
    setState(c);
    return free;
 }

unparkSuccessor代码：

private void unparkSuccessor(Node node) {
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);
        Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null) 
            LockSupport.unpark(s.thread);
}

四、 公平锁和非公平锁的区别

公平锁和非公平锁，在CHL队列抢占模式上都是一致的，也就是在进入acquireQueued这个方法之后都一样，它们的区别在初次抢占上有区别，也就是tryAcquire上的区别，下面是两者内部调用关系的简图：

NonfairSync
lock —> compareAndSetState
                | —> setExclusiveOwnerThread
      —> accquire
		     | —> tryAcquire
                           |—>nonfairTryAcquire
                |—> acquireQueued

FairSync
lock —> acquire
               | —> tryAcquire
                           |—>!hasQueuePredecessors
                           |—>compareAndSetState
                           |—>setExclusiveOwnerThread
               |—> acquireQueued

真正的区别就是公平锁多了hasQueuePredecessors这个方法，这个方法用于判断CHL队列中是否有节点，对于公平锁，如果CHL队列有节点，则新进入竞争的线程一定要在CHL上排队，而非公平锁则是无视CHL队列中的节点，直接进行竞争抢占，这就有可能导致CHL队列上的节点永远获取不到锁，这就是非公平锁之所以不公平的原因。

五、 总结

线程使用ReentrantLock获取锁分为两个阶段，第一个阶段是初次竞争，第二个阶段是基于CHL队列的竞争。在初次竞争的时候是否考虑队列节点直接区分出了公平锁和非公平锁。在基于CHL队列的锁竞争中，依靠CAS操作保证原子操作，依靠LockSupport来做线程的挂起和唤醒，使用队列来保证并发执行变成了串行执行，从而消除了并发所带来的问题。总体来说，ReentrantLock是一个比较轻量级的锁，而且使用面向对象的思想去实现了锁的功能，比原来的synchronized关键字更加好理解。

The above is the detailed content of Detailed sample code explaining the principle of reentrant lock in Java. For more information, please follow other related articles on the PHP Chinese website!