The introduction

AQS, full name “AbstratcQueuedSynchronizer”, it is the foundation of Java explicitly lock implementation framework, is essentially a queue structure, first in first out of the way the maintenance thread blocking and wake up. The JDK source, AbstratcQueuedSynchronizer class definition comment is written like this:

Provides a framework for implementing blocking locks and related synchronizers (semaphores, events, etc) that rely on first-in-first-out (FIFO) wait queues. This class is designed to be a useful basis for most kinds of synchronizers that rely on a single atomic {@code int} value to represent state.

Here is a brief translation of the topic:

  1. A blocking lock frame
  2. Rely on fifO waiting queues

In this section, take a look at the source code for ReentrantLock, a reentrant mutex based on the AQS implementation. If we know the source code of this class well, we can follow the example in the AQS comment to customize the synchronization lock.

The overall structure

ReentrantLockThe class totals more than 700 lines. What’s particularly nice is that the code is elegant and every method is concise. Tracking the source code, the author drew the class structure is like this:First of all, let’s seeReentrantLockClass that contains a synchronizer member variablesyncThree methodslock 、 unlock 和 newCondition. It’s important to note that,lockMethods provide several ways to acquire locks:

  1. tryLock().tryLock(long ,TimeUnit), can be polling, can periodically obtain the lock;
  2. lock(), poll unconditionally to obtain the lock;
  3. lockInterruptibly(), an interruptible lock acquisition method. Threads can be interrupted while the lock is waiting.

Second, focus on the sync member variable, which is an instance of the AQS abstract class. There are two implementation subclasses in ReentrantLock, FairSync and NonfairSync. The difference is whether the lock method requests the lock and allows queue-jumping.

The difference between fair and unfair locks

Do not allow queue-jumping, acquire method directly, source:

final void lock() {
     acquire(1);
} 
Copy the code

When an unfair lock requests to obtain the lock, the CAS operation is performed to obtain the lock first. When the attempt fails, the lock is queued.

 final void lock() {
        if (compareAndSetState(0, 1))
          setExclusiveOwnerThread(Thread.currentThread());
        else
          acquire(1);
}
Copy the code

In highly competitive application scenarios, unfair locks perform better than fair locks because it may take less time for an active thread to directly attempt to acquire the lock than it does to restore a blocked thread and assign the lock to it. Threads take extra time to wake up, and there is a significant delay between waking up and actually running the thread. This is also mentioned in front of the benefits of jumping the queue, here no longer repeat!

Non-fair lock NonfairSync

Not fairly lockedlockMethod, the process is very simple, the first queue-jumping request lock, failure and then go normalacquireAccess to locks:At the back of theacquireThe operation is the execution flow of the fair lock.

Acquire, lock acquisition process

Acquire (1); acquire(1); acquire(1);

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

Simple: Try to acquire the lock first, and if that fails, add the current node from the back of the queueAQSQueue waiting. If the interrupt flag is true while the thread is waiting for the process, the current thread is interrupted.

tryAcquire(1)

tryAcquire(1) 是 acquire(1)Method, which returns a Boolean value indicating whether the lock was successfully acquired. Trace the source code and draw its flow chart:Brief description of flow chart:

  1. Check whether the lock is occupied. If not, run the commandCASAnd returnCASThe results; If the lock is occupied, continue;
  2. Check whether the current thread holder is the holder of the lock. If so, it indicates that the thread is reentrant. Add the lock reentrant count by one and returntrue;
  3. Otherwise, the fetch operation fails and returnsfalse 。

AddWaiter entry process

When the lock acquisition fails, the current thread needs to be enqueued to the conditional queue, which is what the addWaiter method does. AddWaiter encapsulates the current thread as an instance of a queue Node Node and repeats the attempt to insert the Node into the AQS queue in a for loop until the operation returns to the Node successfully.

AQS maintains a linked list with head and tail attributes that are initially null. To add the first Node, create a virtual head Node(that is, a new Node() Node with no information) and point tail to the head. New nodes are inserted from the end of the queue as CAS atoms, which are inserted in the for loop to ensure that threads are added to the queue.

The full flow chart looks like this:The core is to create a wait node for the current thread and successfully join the wait queue.

AcquireQueued Queued thread acquires the lock process

acquireQueued 是 acquireThe third step encapsulates the process of queuing threads acquiring locks. The flow chart is as follows: The thread that failed to acquire the lock,addWaiterAfter the method is enqueued, execution continuesacquireQueuedMethod, retry until the thread is blocked or the lock is successfully acquired. The return value is the thread interrupt identifier, which is returned if the thread was interrupted while waiting for the locktrue 给 acquireBy theacquireMethod to process interrupt requests.

Why this judgment? In order to ensure that the thread is blocked by waiting for the lock, the external interrupt signal will not be drowned. That is, if another thread sends it an interrupt signal after the thread is blocked by PARK, it cannot respond to the interrupt request.

It is therefore necessary to parkAndCheckInterrupt, which checks for interrupt flags and notifies the thread when it is invoked, and the thread itself responds to the interrupt interrupt signal, corresponding to what acquire’s selefIntrupt() does.

shouldParkAfterFailedAcquire

A thread attempts to acquire the lock, if failed, will call shouldParkAfterFailedAcquire method, according to the state of precursor node determine whether need to hang the thread, it returns a Boolean value that identifies whether the current node needs to be hung.

The specific process is as follows:At this point, the lock acquisition operation process analysis is finished.ReentrantLock 的 lockMethod is executed as a result of either the thread being suspended or polling to acquire the lock until the state is successfully set to 1 (occupied) and then removed from the queue.

A waiting thread is blocked only if its precursor has a SIGNAL waiting state, otherwise it is in a loop of retry.

I think it’s nice to block threads or spin retries based on the precursor state, rather than suspend them directly. Because the precursor is still blocked, waiting to wake up, that means they have no hope of getting the lock, there is no need to try. This avoids the resource consumption of thread scheduling, which, after all, comes at a cost when threads are suspended and woken up.

Unlock operation analysis

Unlock operation to release the lock, only a holder of the lock can call, otherwise you will be thrown IllegalMonitorStateException anomalies. The code is also relatively simple:

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

Call the release method of sync directly:

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

Attempt to release the lock and wake up its successor if it succeeds and the wait queue is not empty. The condition for waking up a successor node is that the successor node is non-empty and non-cancelled:

  • If so, it is calledLockSupport 的 unparkWake up;
  • Otherwise, the loop continues until an evocable successor node is found.

The revelation of

ReentrantLock is the work of a Java master. Look at the source code, understand one or two coding skills, later can be applied to their own development work.

Finally, to summarize the coding art of this class:

  1. abstract-dependentsyncIt is an abstraction oriented programming approach
  2. Clever use of data structures like queues
  3. In the process of waiting for the lock, if the precursor node of a node is blocked, the current node will no longer struggle unnecessarily
  4. Reasonable separation method, simple and elegant

I still see the ReentrantLock source code in 2015, all the flow chart and class diagram of this article, are then tracking the source drawn, in order to write a column, and a rearrangement of the old article. It’s instructive to look again at some of the things you figured out at the time.

This is also the meaning of recording ah, although across time and space, some feelings are connected!