preface

AbstractQueuedSynchronizer (AQS) is a barrier in Java Concurrent Programming. Lock, Semaphore and ReentrantLock under JUC concurrent package are all implemented based on AQS. AQS is an abstract synchronization framework, which provides atomicity to manage synchronization status, and realizes the functions of blocking and waking up waiting threads based on blocking queue model

Starting with the ReentrantLock locking and unlocking application API, this paper gradually explains the corresponding source code of AQS and relevant implicit processes

List the outline of this article and relevant knowledge points for better understanding

What is ReentrantLock

ReentrantLock is translated as a reentrant lock, which means that a thread can repeatedly lock the shared resources in the critical area

The most common way to ensure thread safety is to use the Lock mechanism (Lock, synchronized) to mutually exclusive synchronize the shared data. In this way, at the same time, only one thread can execute a method or a code block, so the operation must be atomic and thread safe

There is a question here, because the keyword synchronized in JDK can also support atomicity and thread safety at the same time

Why do I need ReentrantLock when I have the synchronized keyword?

In order to better master the ReentrantLock source code, here are the differences between the two locks

Through the comparison of the above six dimensions, it can be seen that ReentrantLock is more flexible and supports more functions than synchronized

What is AQS

AQS (AbstractQueuedSynchronizer) is an abstract framework for building locks and synchronizers. We can easily implement our customized multi-threaded synchronizers and locks by inheriting AQS

As shown in the figure, under the java.util.concurrent package, related locks and synchronizers (commonly used are ReentrantLock, ReadWriteLock, CountDownLatch...) are implemented based on AQS

AQS is a typical template method design pattern. The parent class (AQS) defines the skeleton and internal operation details, and the specific rules are implemented by the child classes

AQS core principles

If the requested shared resource is not occupied, set the thread requesting the resource as the exclusive thread and set the shared resource to the locked state

AQS uses a member variable State of int type modified by Volatile to represent the synchronization State. If the synchronization State is modified successfully, the lock is obtained

Volatile ensures the visibility of variables among multiple threads. When modifying the State value, CAS mechanism is used to ensure the atomicity of modification

If shared resources are occupied, a certain blocking waiting wake-up mechanism is required to ensure lock allocation. AQS will add the thread that failed to compete for shared resources to a variant CLH queue

Important methods and attributes for supporting AQS characteristics are as follows:

public abstract class AbstractQueuedSynchronizer 
  extends AbstractOwnableSynchronizer implements java.io.Serializable {
  	// CLH variant queue header and tail nodes
    private transient volatile Node head;
  	private transient volatile Node tail;
  	// AQS synchronization status
   	private volatile int state;
  	// Update state in CAS mode
  	protected final boolean compareAndSetState(int expect, int update) {
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }
}

CLH queue

Since the CLH variant queue is used in AQS, let's first understand what the CLH queue is

CLH: Craig, Landin and Hagersten queue, which is a queue implemented by one-way linked list. The application thread spins only on the local variable. It constantly polls the state of the precursor. If it finds that the precursor node has released the lock, it ends the spin

Through the description of CLH queue, the following conclusions can be drawn

1. CLH queue is a one-way linked list that maintains FIFO first in first out queue characteristics
2. The queue is built through the tail node (atomic reference), which always points to the last node
3. Nodes that do not acquire locks spin instead of switching thread states
4. The performance is poor when concurrency is high, because the node that has not obtained the lock keeps rotating the status of the precursor node to check whether it has obtained the lock

The queue in AQS is a virtual bi-directional queue of CLH variant. Lock allocation is realized by encapsulating each thread requesting shared resources into a node

Compared with CLH queue, CLH variant waiting queue in AQS has the following characteristics

1. The queue in AQS is a two-way linked list, which is also a FIFO first in first out feature
2. The queue structure is composed of Head and Tail nodes, and the visibility is guaranteed through volatile modification
3. The Head node refers to the node that has obtained the lock. It is a virtual node. The node itself does not hold a specific thread
4. If the synchronization status cannot be obtained, the node will be spin locked. After a certain number of spin failures, the thread will be blocked. Compared with the CLH queue, the performance is better

Know AOS

Abstract class AQS also inherits from abstract class AOS (AbstractOwnableSynchronizer)

There is only one Thread type variable in AOS, which provides a method to obtain and set the current exclusive lock Thread

The main function is to record the thread instances that currently occupy exclusive locks (mutexes)

public abstract class AbstractOwnableSynchronizer implements java.io.Serializable {
    // Exclusive thread (not participating in serialization)
    private transient Thread exclusiveOwnerThread;
    // Sets the currently exclusive thread
    protected final void setExclusiveOwnerThread(Thread thread) {
        exclusiveOwnerThread = thread;
    }
    // Returns the currently exclusive thread
    protected final Thread getExclusiveOwnerThread() {
        return exclusiveOwnerThread;
    }
}

Why master AQS

How to reflect the level of programmers is to master the technology that most people don't master, which is why AQS appears frequently during the interview, because it's not simple

When I first came into contact with ReentrantLock and AQS, I was confused when I saw the source code, and Debug lost himself. I believe this is also the reaction of most people

It is because of experience that we can sort out all the knowledge points from Xiaobai's psychology

The author writes very carefully. The little friends who have read this article can't guarantee to fully understand the principles of AQS and ReentrantLock, but they will gain something

Exclusive locking source code analysis

What is an exclusive lock

An exclusive lock is also called an exclusive lock, which means that the lock can only be held by one thread at a time. If other threads want to obtain the lock, they can only wait until the thread holding the lock is released

The thread that obtains the exclusive lock can read and modify the data. The opposite is the shared lock

A shared lock means that the lock can be held by multiple threads. If thread T adds a shared lock to data a, other threads can only add a shared lock to a, not an exclusive lock

The thread that obtains the shared lock can only read data and cannot modify data

Exclusive lock

ReentrantLock is an implementation of exclusive lock. Next, let's see how to use ReentrantLock to complete exclusive locking business logic in the code

public static void main(String[] args) {
    // Create unfair lock
    ReentrantLock lock = new ReentrantLock();
    // Acquire lock operation
    lock.lock();
    try {
        // Execute code logic
    } catch (Exception ex) {
        // ...
    } finally {
        // Unlock operation
        lock.unlock();
    }
}

The new ReentrantLock() constructor creates a non fair lock NonfairSync by default

public ReentrantLock() {
    sync = new NonfairSync();
}

At the same time, you can also pass specific parameters in the create lock constructor to create fair lock FairSync

ReentrantLock lock = new ReentrantLock(true);
--- ReentrantLock
// true represents fair lock and false represents non fair lock
public ReentrantLock(boolean fair) {
    sync = fair ? new FairSync() : new NonfairSync();
}

FairSync and NonfairSync represent fair locks and unfair locks. Both are static internal classes of ReentrantLock, but implement different lock semantics

Fair lock FairSync

1. Fair lock means that multiple threads acquire locks according to the order in which they apply for locks. Threads directly queue in the queue, and the first thread in the queue can obtain the lock
2. The advantage of fair locks is that threads waiting for locks do not starve. The disadvantage is that the overall throughput efficiency is lower than that of unfair locks. All threads in the waiting queue except the first thread will block, and the cost of CPU waking up blocked threads is greater than that of unfair locks

Non fair lock NonfairSync

1. An unfair lock is a direct attempt to obtain a lock when multiple threads lock. If they cannot obtain the lock, they will wait at the end of the waiting queue. However, if the lock is just available at this time, the thread can obtain the lock directly without blocking
2. The advantage of unfair locking is that it can reduce the overhead of arousing threads, and the overall throughput efficiency is high, because threads have the possibility to obtain locks directly without blocking, and the CPU does not have to wake up all threads. The disadvantage is that threads in the waiting queue may starve to death or wait a long time to get a lock

Both of them inherit from the ReentrantLock static abstract internal class Sync, and the Sync class inherits from AQS. Here's a question

These locks do not directly inherit AQS, but define a Sync class to inherit AQS. Why?

Because the lock is for users and the synchronizer is for thread control, aggregating the synchronizer in the implementation of the lock rather than directly inheriting AQS can well isolate the concerns of the two

Through the explanation of different lock types and the analysis of the internal structure of ReentrantLock, the understanding is deepened according to the inheritance diagram of parent-child relationship

Here, take unfair lock as an example to view the specific process of locking. The details will be described in detail below

Let's take a look at what the unfair lock locking method does inside lock

ReentrantLock lock = new ReentrantLock();
lock.lock();
--- ReentrantLock
public void lock() {
    sync.lock();
}
--- Sync
abstract void lock();

Sync#lock is an abstract method, which will eventually call the lock method of its subclass unfair lock

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

The unfair locking method has two logics

1. Whether the lock is obtained is determined by comparing and replacing the success of the State (synchronization State). Setting the State to 1 indicates that the lock is successfully obtained, and setting the current thread as an exclusive thread
2. If it fails to modify the State value, enter the process of trying to obtain the lock. The acquire method is the method provided by AQS

compareAndSetState sets the State value to 1 by CAS comparison and replacement, indicating that the synchronization State is occupied

protected final boolean compareAndSetState(int expect, int update) {
    // See below for intrinsics setup to support this
    return unsafe.compareAndSwapInt(this, StateOffset, expect, update);
}

setExclusiveOwnerThread sets the current thread as the exclusive lock owning thread

protected final void setExclusiveOwnerThread(Thread thread) {
    exclusiveOwnerThread = thread;
}

Acquire serves as a link between the preceding and the following for the whole AQS. Try to acquire the lock through the tryAcquire template method. If the lock acquisition fails, wrap the current thread into the waiting queue for the Node node

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

tryAcquire is an abstract template method in AQS, but there will be a default implementation inside. Although the default method throws an exception inside, why not directly define it as an abstract method?

Because AQS not only abstracts exclusive locks, but also includes shared locks; If different locks define different types of methods, tryAcquire is not required for shared locks. If it is defined as an abstract method, all subclasses that inherit AQS need to implement this method

protected boolean tryAcquire(int arg) {
    throw new UnsupportedOperationException();
}

There is a tryAcquire override method in the NonfairSync class. Continue to see how to obtain locks unfairly

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

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
  	// State equal to 0 means there is no lock at this time
    if (c == 0) {
      	// The CAS is used again to try to obtain the lock, which is shown as an unfair lock
        if (compareAndSetState(0, acquires)) {
          	// Set thread to exclusive lock thread
            setExclusiveOwnerThread(current);
            return true;
        }
    // If the current thread is equal to the thread that has acquired the lock, it is represented as a reentrant lock feature
    } else if (current == getExclusiveOwnerThread()) {
        int nextc = c + acquires;
        if (nextc < 0) // overflow
            throw new Error("Maximum lock count exceeded");
      	// Set State
        setState(nextc);
        return true;
    }
  	// If state is not equal to 0 and the exclusive thread is not the current thread, false is returned
    return false;
}

Since the tryAcquire is negated, if the state setting fails and the exclusive lock thread does not return false by itself, the next process will be entered by negating

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

Node queuing process

The attempt to obtain the lock fails. Next, the thread will be assembled into a Node for the queue process

Node is the most basic data structure in AQS and also a node in CLH variant queue. Node has two modes: SHARED and EXCLUSIVE. This article mainly introduces the EXCLUSIVE mode, and irrelevant attributes and methods will not be introduced

Some key methods and status information about Node EXCLUSIVE mode are listed below

Key methods and attributes	Corresponding meaning
waitStatus	What state is the current node in the queue
thread	Represents the thread corresponding to the node
prev	Precursor pointer, pointing to the previous node of this node
next	Subsequent pointer to the next node of this node
predecessor	Return the precursor node, and throw an NPE exception if there is no one

The waitStatus attribute related to the exclusive lock in Node has the following statuses:

Attribute value	Value meaning
0	Default value of Node after initialization
CANCELLED	With a value of 1, the node was cancelled due to an interrupt or timeout
SIGNAL	A value of - 1 indicates that the successor node of the node is about to be blocked
CONDITION	A value of - 2 indicates that the node is in the waiting queue and the node thread is waiting to wake up

After introducing the basic knowledge of Node, let's take a look at how the request lock thread is wrapped as a Node and how to initialize the queue

private Node addWaiter(Node mode) {
    Node node = new Node(Thread.currentThread(), mode);
    // Gets the tail node of the waiting queue
    Node pred = tail;
  	// If the tail node is not empty, set the node as the tail node and point the original tail node next to the new tail node
    if (pred != null) {
        node.prev = pred;
        if (compareAndSetTail(pred, node)) {
            pred.next = node;
            return node;
        }
    }
  	// The tail is empty, enq execute
    enq(node);
    return node;
}

pred is the tail node of the queue. The corresponding process will be executed according to whether the tail node is empty

1. If the tail node is not empty, it proves that the queue has been initialized, then the corresponding node (current thread) needs to be set as a new tail node, that is, queue operation; Point the precursor pointer of node node to pred (tail node), and set node as the tail node of AQS waiting queue through CAS. After successful replacement, point the subsequent pointer of the original tail node to the new tail node
2. If the tail node is empty, it proves that the queue has not been initialized. Execute enq method to initialize the queue

The enq method performs the operation of initializing the queue, and the virtualized head node in the waiting queue is also generated here

private Node enq(final Node node) {
    for (; ; ) {
        Node t = tail;
        if (t == null) {
          	// Virtualize an empty Node and point the head to the empty Node
            if (compareAndSetHead(new Node()))
              	// Equal tail node to head node
                tail = head;
        } else {
          	// The previous node points to the tail node
            node.prev = t;
          	// Set node as tail node
            if (compareAndSetTail(t, node)) {
              	// Set the next point of the original tail node to node
                t.next = node;
                return t;
            }
        }
    }
}

The premise of enq method is that the tail node of the queue is empty. Why judge whether the tail node is empty?

Because enq method is an endless loop, the value of t in the loop process is not fixed. If the queue is empty when the enq method is executed, the for loop executes different processing logic twice

1. When the tail Node is empty, a new Node head Node is virtualized. At this time, there is only one element in the queue. In order to ensure the integrity of AQS queue structure, the tail Node will be pointed to the head Node, and the first cycle ends
2. The second pass does not meet the condition that the tail node is empty, execute the else statement block, point to the tail node through the node precursor pointer, and set the node as a new tail node through CAS. After success, set the subsequent pointer of the original tail node to point to the node. So far, the team is successful. The returned t is meaningless, just to terminate the loop

Draw two diagrams to understand the overall AQS queue initialization process of enq method. Suppose that T1 and T2 strive for the lock, T1 successfully obtains the lock, and T2 performs the queue entry operation

1. T2 performs the queue entry operation, the first cycle, and the tail node is empty. Start initializing the head node and point the tail node to the head node. The final queue form is as follows

1. For the second cycle, you need to set node as the new tail node. The logic is as follows: if the tail node is not empty, set the node precursor pointer to the tail node, set the node as the tail node, and the original tail node next pointer to the node

The addWaiter method is to queue nodes and maintain a two-way queue model

After the queue is successfully executed, the contention lock will be tried again in acquirequeueueueueueueueued. After the contention fails, the thread will be blocked

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

The acquirequeueueueued method will attempt to spin to obtain the lock. If the acquisition fails, the blocking process will be implemented on the current thread. This is also to avoid meaningless spin. Compared with the performance optimization of CLH queue

final boolean acquireQueued(final Node node, int arg) {
    boolean failed = true;
    try {
        boolean interrupted = false;
        for (; ; ) {
          	// Get the previous node on node
            final Node p = node.predecessor();
          	// If node is the head node & the attempt to acquire the lock is successful
            if (p == head && tryAcquire(arg)) {
              	// At this point, the current node thread acquires the lock
              	// Set node as the new head node
                setHead(node);
              	// help GC
                p.next = null;
                failed = false;
                return interrupted;
            }
            if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                interrupted = true;
        }
    } finally {
        if (failed)
            cancelAcquire(node);
    }
}

Obtain the precursor node of the node through node.predecessor(). If the precursor node is empty, a null pointer exception will be thrown

final Node predecessor() throws NullPointerException {
    Node p = prev;
    if (p == null)
        throw new NullPointerException();
    else
        return p;
}

After obtaining the precursor node, make two-step logical judgment

1. Judge whether the precursor node p is the head node. If it is true, try to obtain the lock. The lock is successfully obtained, set the current node as the new head node, and set the trailing pointer of the original head node to null
2. If the precursor node is not the head node or the attempt to lock fails, perform thread sleep blocking operation

After the node obtains the lock, setHead sets the node as the queue header to achieve the out of queue effect. For the sake of GC, unused data is cleared

private void setHead(Node node) {
    head = node;
    node.thread = null;
    node.prev = null;
}

shouldParkAfterFailedAcquire requires special attention, and the process is relatively difficult to understand

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;
}

ws represents the waiting state of the precursor node of the current lock application node. The code contains three logics, namely:

1. ws == Node.SIGNAL, indicating that the node applying for lock needs to be blocked
2. Ws > 0 indicates that the waiting queue contains cancelled nodes, and the queue needs to be adjusted
3. If WS = = Node.SIGNAL | WS > 0 is false, use CAS to set the waiting state of the precursor node to Node.SIGNAL

Set the waiting status of the front node of the current node to Node.SIGNAL, which indicates that the current node failed to obtain the lock and needs to be blocked

Let's understand the process through several diagrams. Suppose that T1 and T2 threads compete for locks at this time

T1 thread obtains the lock, T2 enters the AQS waiting queue, and sets the waiting state of the precursor node of T2 node to SIGNAL through CAS

After switching the waiting state of the precursor node, it returns false and continues to cycle to try to obtain the synchronization state

This step ensures that the thread can retry many times and try to avoid thread state switching

If the T1 thread does not release the lock, the T2 thread executes the shouldParkAfterFailedAcquire method for the second time. Because the precursor node has been set to SIGNAL, it will directly return true to execute the thread blocking operation

private final boolean parkAndCheckInterrupt() {
  	// Block the current thread
    LockSupport.park(this);
  	// Method returns the interrupt status of the current thread and sets the interrupt ID of the current thread to false
    return Thread.interrupted();
}

The LockSupport.park method blocks the thread in the current WAITING queue, and the thread performs a state transition from RUNNABLE to WAITING

If the thread is awakened, check the interrupt status by executing Thread.interrupted. The interrupt status here will be passed to the acquire method

public final void acquire(int arg) {
    if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
      	// If the thread is interrupted, the interrupt state will be set again
      	// Because if the thread is interrupted, calling Thread.interrupted will return true, but the thread interrupt status will be cleared
        selfInterrupt();
}

Even if the thread wakes up from the park method and finds itself interrupted, it will not affect the subsequent lock acquisition operation. If it is necessary to set the thread interrupt to affect the process, you can use lockinterruptable to obtain the lock and throw a check exception InterruptedException

cancelAcquire

The method of canceling queuing is a difficult knowledge point in AQS and is not easy to understand

When the thread fails to acquire the lock due to spin or exception, this method will be called to cancel the operation of acquiring the lock

private void cancelAcquire(Node node) {
    // Non existing nodes are returned directly
    if (node == null)
        return;
node<span class="token punctuation">.</span>thread <span class="token operator">&#61;</span> null<span class="token punctuation">;</span>

<span class="token comment">/**
 * waitStatus &gt; 0 Indicates that the node is in cancel status
 * while The loop points the precursor pointer of the node node to a node that is not in the cancelled state
 * pred Equal to the predecessor node of the current node ( Non cancellation status )
 */</span>
Node pred <span class="token operator">&#61;</span> node<span class="token punctuation">.</span>prev<span class="token punctuation">;</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span>pred<span class="token punctuation">.</span>waitStatus <span class="token operator">&gt;</span> <span class="token number">0</span><span class="token punctuation">)</span>
    node<span class="token punctuation">.</span>prev <span class="token operator">&#61;</span> pred <span class="token operator">&#61;</span> pred<span class="token punctuation">.</span>prev<span class="token punctuation">;</span>

<span class="token comment">// Gets the successor node of the filtered predecessor node</span>
Node predNext <span class="token operator">&#61;</span> pred<span class="token punctuation">.</span>next<span class="token punctuation">;</span>

<span class="token comment">// Set node wait status to cancel status</span>
node<span class="token punctuation">.</span>waitStatus <span class="token operator">&#61;</span> Node<span class="token punctuation">.</span>CANCELLED<span class="token punctuation">;</span>

<span class="token comment">// 🚩 Step 1 ， If node is the tail node ， Use CAS to set pred as the new tail node</span>

<span class="token keyword">if</span> <span class="token punctuation">(</span>node <span class="token operator">&#61;&#61;</span> tail <span class="token operator">&amp;&amp;</span> <span class="token function">compareAndSetTail</span><span class="token punctuation">(</span>node<span class="token punctuation">,</span> pred<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span>
  	<span class="token comment">// Set pred( New tail) The rear drive pointer of is null</span>
    <span class="token function">compareAndSetNext</span><span class="token punctuation">(</span>pred<span class="token punctuation">,</span> predNext<span class="token punctuation">,</span> null<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{<!-- --></span>
    <span class="token keyword">int</span> ws<span class="token punctuation">;</span>
  	<span class="token comment">// 🚩 Step 2 ， The precursor node pred&#xff08 of node; Non cancellation status &#xff09&# 61;  Head node</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>pred <span class="token operator">!&#61;</span> head 
        	<span class="token comment">/**
        	 * 1. pred Wait status equals SIGNAL
        	 * 2. ws &lt;&#61; 0 And set the pred waiting state to SIGNAL
        	 */</span>
        	<span class="token operator">&amp;&amp;</span> <span class="token punctuation">(</span><span class="token punctuation">(</span>ws <span class="token operator">&#61;</span> pred<span class="token punctuation">.</span>waitStatus<span class="token punctuation">)</span> <span class="token operator">&#61;&#61;</span> Node<span class="token punctuation">.</span>SIGNAL <span class="token operator">||</span> <span class="token punctuation">(</span>ws <span class="token operator">&lt;&#61;</span> <span class="token number">0</span> <span class="token operator">&amp;&amp;</span> <span class="token function">compareAndSetWaitStatus</span><span class="token punctuation">(</span>pred<span class="token punctuation">,</span> ws<span class="token punctuation">,</span> Node<span class="token punctuation">.</span>SIGNAL<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span> 
        	<span class="token comment">// Thread in pred is not empty</span>
        	<span class="token operator">&amp;&amp;</span> pred<span class="token punctuation">.</span>thread <span class="token operator">!&#61;</span> null<span class="token punctuation">)</span> <span class="token punctuation">{<!-- --></span>
        Node next <span class="token operator">&#61;</span> node<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
      	<span class="token comment">/**
      	 * 1. The successor node of the current node is not empty
      	 * 2. Successor node waiting state & lt&# 61; 0( Indicates non cancellation status )
      	 */</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>next <span class="token operator">!&#61;</span> null <span class="token operator">&amp;&amp;</span> next<span class="token punctuation">.</span>waitStatus <span class="token operator">&lt;&#61;</span> <span class="token number">0</span><span class="token punctuation">)</span>
          	<span class="token comment">// Set the successor node of pred as the successor node of the current node</span>
            <span class="token function">compareAndSetNext</span><span class="token punctuation">(</span>pred<span class="token punctuation">,</span> predNext<span class="token punctuation">,</span> next<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{<!-- --></span>
      	<span class="token comment">// 🚩 Step 3 ， If the current node is the head node or the above conditions are not met, execute the subsequent node process of waking up the current node</span>
        <span class="token function">unparkSuccessor</span><span class="token punctuation">(</span>node<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    node<span class="token punctuation">.</span>next <span class="token operator">&#61;</span> node<span class="token punctuation">;</span> <span class="token comment">// help GC</span>
<span class="token punctuation">}</span>

}

The logic is a little more complex. The more important are the following three logics

1. Step 1: if the current node is the tail node, set the pred node as the new tail node. After successful setting, set the pred successor node to null (the tail node will not have a successor node)

2. In step 2, the following four conditions need to be met before the successor pointer of the predecessor node (non cancelled state) points to the successor pointer of the current node

   1) The current node is not equal to the tail node

   2) The current node precursor node is not equal to the head node

   3) The waiting state of the precursor node is not cancelled

   4) The owning thread of the precursor node is not empty

3. If step 2 is not satisfied, the related logic of step 3 will be executed to wake up the successor node

Step 1:

Assuming that the current cancellation node is the tail node and the front node has no cancellation node, the existing waiting queue is shown in the figure below, and the following logic is executed

if (node == tail && compareAndSetTail(node, pred)) {
    compareAndSetNext(pred, predNext, null);
}

Set pred as the new tail node and set pred successor node to null, because the tail node will not have successor nodes

The node where the T4 thread is located will be garbage collected by GC because it has no reference point

Step 2:

If the precursor node of the current node to be cancelled is a node in cancelled status, as shown in the figure

Set the successor node of pred (non cancellation status) as the successor node of node, and set the next node as itself

How to perform GC because the nodes of threads T2 and T3 are directly or indirectly pointed to by T4?

The node in the AQS waiting queue whose status is cancelled will be garbage collected by GC in the shouldParkAfterFailedAcquire method

if (ws > 0) {
    do {
        node.prev = pred = pred.prev;
    } while (pred.waitStatus > 0);
    pred.next = node;
}

When the node where the T4 thread is located fails to acquire the lock and attempts to stop, the above code will be executed. The waiting queue after execution is shown in the following figure

The node in the waiting queue can be garbage collected by GC. So far, the locking process is over. Let's continue to see how to unlock it

Exclusive unlock source code analysis

The unlocking process is much simpler than locking, and the corresponding API-lock.unlock() is called

--- ReentrantLock
public void unlock() {
    sync.release(1);
}
--- AQS
public final boolean release(int arg) {
  	// Attempt to release the lock
    if (tryRelease(arg)) {
        Node h = head;
        if (h != null && h.waitStatus != 0)
            unparkSuccessor(h);
        return true;
    }
    return false;
}

Release lock synchronization status

tryRelease is an abstract method defined in AQS, and its implementation is rewritten by the Sync class

protected final boolean tryRelease(int releases) {
    int c = getState() - releases;
  	// If the current thread is not equal to the thread that owns the lock, an exception is thrown
    if (Thread.currentThread() != getExclusiveOwnerThread())
        throw new IllegalMonitorStateException();
    boolean free = false;
    if (c == 0) {
        free = true;
      	// Set lock owning thread to null
        setExclusiveOwnerThread(null);
    }
  	// Set the State to 0 and unlock successfully
    setState(c);
    return free;
}

Wake up the successor node

At this time, the State value has been released, which is an interesting process for judging the header node

Node h = head;
if (h != null && h.waitStatus != 0)
		unparkSuccessor(h);

When the head node is empty, when the thread is still competing for the lock and the queue is not initialized, the head node must be empty

When the waiting state of the head node is equal to 0, it proves that the successor node is still spinning and does not need to wake up the successor node

If the above two conditions are met at the same time, wake up the successor node of the waiting queue head node

private void unparkSuccessor(Node node) {
  	// Get node wait status
    int ws = node.waitStatus;
    if (ws < 0)
        compareAndSetWaitStatus(node, ws, 0);
  	// Get the successor node of node
    Node s = node.next;
  	// If the next node is empty or cancelled, traverse the queue to query the non cancelled node
    if (s == null || s.waitStatus > 0) {
        s = null;
      	// Search from the end of the queue and wait for nodes with status < = 0
        for (Node t = tail; t != null && t != node; t = t.prev)
            if (t.waitStatus <= 0)
                s = t;
    }
  	// Satisfy s= null && s.waitStatus <= 0
  	// Execute unpark
    if (s != null)
        LockSupport.unpark(s.thread);
}

Why does it need to start from the tail to find nodes in the queue that have not been cancelled?

There are two reasons for this problem, namely, Node queuing and cleaning up nodes in cancelled status

1. First, when addWaiter joins the queue, compareAndSetTail(pred, node) and pred.next = node are not atomic operations. If unparksuccess is performed before pred.next = node, there is no way to traverse backward through the next pointer, so we will look for non cancelled nodes from the back to the front

2. The cancelAcquire method also has a factor that makes it impossible to traverse all nodes using the head, because the next pointer is disconnected first, and the prev pointer is not disconnected

Wake up after blocking process

When the thread fails to acquire the lock, it enters the blocking mode after being park. After the precursor node releases the lock, it will wake up unpark, and the blocked thread returns to the RUNNABLE state

private final boolean parkAndCheckInterrupt() {
  	// Wake up from this location
    LockSupport.park(this);
    return Thread.interrupted();
}

The awakened thread checks whether it is interrupted and returns its interrupt status to acquirequeueueueued

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);
    }
}

Assuming that it is interrupted, set interrupted = true, continue to try to obtain the lock through a loop, and return to the interrupted interrupt state after successfully obtaining the lock

The interrupt status itself does not affect the lock adding process. After being awakened, it will continue to obtain the lock until the lock is successfully returned. The interrupt status is returned to supplement the interrupt record later

If an interrupt is found after the thread is awakened, the interrupt status will be returned after successfully obtaining the lock to supplement the interrupt status

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

Self interrupt is a supplement to the thread interrupt status. After the supplement status is successful, the process ends

static void selfInterrupt() {
    Thread.currentThread().interrupt();
}

Tips for reading source code

1. Master the functions provided by the source code to be read from a global perspective

This is also the way I have always respected to learn the source code. The key point of learning the source code is to grasp the main line process. Before understanding the main line, don't study the implementation details of the source code at the beginning, otherwise it's easy to get lost in the trivial code

Take AQS in this article as an example. When you know that it is an abstract queue synchronizer, you can use it to construct locks and synchronizers more simply

Then understand the implementation of tryAcquire, tryRelease and other methods. Can you better understand the code related to AQS and its subclasses

2. Paste the incomprehensible source code, sort out the format and make notes

The behavior format in the general source code is different from our daily code typing, and the variable naming in the JDK source code is really terrible

Therefore, you should paste the hard to understand source code, mark the corresponding comments and adjust it to an easy to understand format, so that it will be much easier to read the source code

Postscript

There are still a lot of AQS related knowledge in my daily work. I know what it is and why. Taking ReentrantLock as the starting point, this paper describes the concepts of fair lock and unfair lock, as well as the concepts that are not easy to be found in AQS, such as CLH and AOS

The processes of ReentrantLock and AQS locking, unlocking and queuing are described in detail, and the implementation details of the process source code are described in the way of pictures and texts. Here, I hope all the partners watching can gain AQS related knowledge

Due to the limited level of the author, you are welcome to feed back and correct the mistakes and incorrect places in the article. Thank you 🙏

My partner's love is my greatest support. If I get something from reading the article, I hope I can praise, comment and pay attention to the third company!

reference material

• https://tech.meituan.com/2019/12/05/aqs-theory-and-apply.html
• https://tech.meituan.com/2018/11/15/java-lock.html
• https://mp.weixin.qq.com/s/y_e3ciU-hiqlb5vseuOFyw
• https://zhuanlan.zhihu.com/p/197840259?utm_source=wechat_session
• https://blog.csdn.net/java_lyvee/article/details/98966684
• https://zhuanlan.zhihu.com/p/197840259?utm_source=wechat_session