AQS profile

AbstractQueuedSynchronizer (AQS) is the core of the whole JUC package. Synchronization tools in JUC such as ReentrantLock, ReentrantReadWriteLock, CountDownLatch, Semaphore, and LimitLatch are all implemented based on AQS.

AQS isolates common concerns for building synchronizers, which include the following:

  • Can resources be accessed simultaneously? Or can only be accessed by one thread at a time? (Share/Exclusive function)
  • How are threads accessing resources managed concurrently? (Waiting queue)
  • How do I exit the wait queue if a thread cannot wait for a resource? (Timeout/interrupt)

These concerns are centered around a resource called synchronization state. AQS encapsulates these common concerns into template methods that subclasses can use directly.

AQS leaves users with just two questions:

  • What is a resource
  • Under what circumstances are resources accessible

This makes defining a synchronizer much easier. Users can build an excellent synchronizer by solving the above two problems.

Here are a few common synchronizer definitions of resources:

synchronizer Definition of resources
ReentrantLock Resources represent exclusive locks. State 0 indicates that the lock is available. 1 indicates that it is occupied. N indicates the number of reentries
ReentrantReadWriteLock Resources represent shared read locks and exclusive write locks. State is logically divided into two 16-bit unsigned shorts that record how many threads the read lock is used and how many times the write lock is reentered.
CountDownLatch Resources represent reciprocal counters. A State of 0 means that the counter returns to zero and all threads have access to the resource. A value of N indicates that the counter is not zero and all threads need to block.
Semaphore Resources represent semaphores or tokens. State≤0 means no tokens are available and all threads need to block; If the token is greater than 0, the token is available. State decreases by 1 each time a thread acquires a token, and increases by 1 if the thread does not release a token.

AQS principle

In the previous section, IT was introduced that AQS abstracts three concerns. The following is a detailed look at how AQS solves these three problems.

Manage synchronization status

The synchronization state is essentially a resource. AQS uses a single int (32 bits) to hold the synchronization state and exposes getState, setState, and compareAndSetState operations to read and update the state.

Thread blocking and waking up

Prior to JDK1.5, there was no safe and convenient way to block and wake up the current thread except for the built-in monitor mechanism.

JDK1.5, Java. Util. Concurrent. The locks package provides LockSupport class as a tool for thread blocking and wake up.

Waiting queue

Wait queue is the core of AQS framework. The key of the whole framework is how to manage blocked threads in concurrent state.

Wait queues are strict FIFO queues, a variant of Craig, Landin and Hagersten locks (CLH locks), implemented by bidirectional cyclic linked lists, so also called CLH queues.

1. Node definition

Nodes in CLH queues are threads wrapped around them, and there are two types of nodes: EXCLUSIVE and SHARED.

Each type of node has some states, among which CANCELLED(1), SIGNAL(-1) and CONDITION(-2) are used for exclusive nodes, while CANCELLED(1), SIGNAL(-1) and PROPAGATE(-3) are used for shared nodes.

Node status value describe
CANCELLED 1 Cancel it. Indicates that the back-end node is interrupted or timed out and needs to be removed from the queue
SIGNAL – 1 Signals. (Before the current node is enqueued, make sure that its PREV node type is changed to SIGNAL so that the current node will wake up when the preV node is cancelled or released.)
CONDITION 2 – Special Condition. Indicates that the current node is in the Condition queue and is blocked waiting for a Condition
PROPAGATE – 3 Transmission. It is suitable for shared mode (for example, continuous read operation nodes can enter the critical region in turn, PROPAGATE is helpful for realizing such iterative operation.)
INITIAL 0 The default. The new node will be in this state

AQS uses CLH queue to achieve thread structure management, and CLH structure just uses a certain attribute of the previous node to represent the state of the current node. The reason for this is that it is easier to realize cancellation and timeout functions under the structure of bidirectional linked list.

Next pointer: Used to maintain queue order. When critical section resources are released, the head node uses the next pointer to find the first queue node.

Prev pointer: Used when a node (thread) is canceled, so that the precursor of the current node points directly to the back-end of the current node to complete the queue action.

2. Queue definition

For CLH queues, when a thread requests a resource, if it does not, the thread is wrapped as a node and mounted at the end of the queue.

Let’s look at the process of the node entering the queue with some code.

In the first loop of the code above, when the element is inserted at the end of the AQS queue, the state of the AQS queue is shown in the figure below (default). Both the head and tail of the queue point to NULL; When node T points to the tail node after executing code (1), the queue status is shown in figure (I).

In this case, t is null, so code (2) is executed and CAS algorithm is used to set a sentinel node as the head node. If CAS is set successfully, the tail node also points to the sentinel node. At this time, the queue status is shown in figure (II).

So far only one sentinel node has been inserted, and node node still needs to be inserted, so after the second loop, code (1) is executed, and the queue state is shown in figure (III). Then code (3) is executed to set the front node of node as the tail node. At this time, the queue state is as shown in figure (IV).

Then, CAS algorithm is used to set node node as tail node. After CAS is successful, queue status is shown in figure (V).

After CAS is successful, the rear drive node of the original tail node is set as Node. At this time, the insertion of the bidirectional linked list is completed, and the queue status is shown in the figure (VI).

AQS method introduction

Users need to rewrite their own methods

As mentioned above, AQS has solved most of the problems in the synchronizer definition process for users, leaving only the following two problems to the users to solve:

  • What is a resource
  • Under what circumstances are resources accessible

Specifically, AQS allows users to solve the above problems by exposing the following apis.

Hook method describe
tryAcquire Exclusive mode. Attempts to obtain the resource return true on success and false on failure.
tryRelease Exclusive mode. Attempts to free resources return true on success and false on failure.
tryAcquireShared Sharing mode. Attempt to obtain resources. Negative numbers indicate failure; 0 indicates success, but no available resources are available. A positive number indicates success and free resources.
tryReleaseShared Sharing mode. Attempts to free the resource, returning true if subsequent wait nodes are allowed to wake up after release, false otherwise.
isHeldExclusively Whether the thread is monopolizing resources. You only need to implement it if you use condition.

If you need to implement a synchronizer of your own, you can generally just inherit AQS and rewrite the methods in AQS. As for the maintenance of thread-specific wait queues (e.g., resource failure to queue/wake up queue, etc.), AQS are already implemented at the top level. How else can I say Doug Lea is sweet.

Note that if you call these methods without overriding them in a subclass, they will throw an exception. Therefore, you must override these methods before you call them. You don’t have to rewrite it if you don’t use it.

AQS provides a series of template methods

Looking at the AQS source code, we can find that this class provides a number of methods that look “dazzling”. But the two main types of methods are methods of obtaining resources and methods of releasing resources. So let’s just focus on the main contradiction:

  • Public final void acquire(int arg) // Obtain resources in exclusive mode
  • Public final Boolean release(int arg) // Release resources in exclusive mode
  • Public final void acquireShared(int arg) // Obtain resources in shared mode
  • Public Final Boolean releaseShared(int arg) // Release resources in shared mode

Acquire (int) method

This method obtains resources exclusively. If the resource is obtained, the thread continues to execute. Otherwise, the thread enters a waiting queue until the resource is obtained. This method is the top-level entry for threads in exclusive mode to obtain shared resources.

Let’s analyze the specific execution flow of the Acquire method:

Step1: First of all, this method calls the user-implemented tryAcquire method to try to acquire resources. If this method returns true, that is to say, it has successfully acquired resources, then the whole acquire method is finished and the thread continues to execute.

Step2: If the tryAcquir method returns false, the attempt to obtain the resource has failed. The Acquire method first calls the addWaiter method to wrap the current thread into a Node class and join the end of a FIFO two-way queue.

Step3: look again at the acquireQueued key method. The first thing to notice is the unconditional for loop in this method, which says that the acquireQueued method is always spinning to try to get the resource. After entering the for loop, we first determine whether the preceding node of the current node is the head node. If so, we try to fetch the resource again.

If still have no access to resources is successful, judge whether the current node needs to enter a state of waiting, after shouldParkAfterFailedAcquire the judging methods, if need to let the thread into waiting state, Call LockSupport’s park method to put the thread into waiting. After entering a waiting state, the thread is waiting to be interupt or unpark (which happens in the release operation, see the code below). The thread is woken up and continues to execute the for loop in an attempt to retrieve the resource

This is the simple analysis of acquire method.

This method may not be clear on its own, but it makes a lot more sense when you look at the code with synchronization tools such as ReentrantLock, ReentrantReadWriteLock, CountDownLatch, Semaphore, and LimitLatch.

Release (int) method

The release(int) method is the top-level entry for threads in exclusive mode to release shared resources. It frees a specified amount of resources, and if it frees completely (i.e., state=0), it wakes up other threads in the waiting queue to acquire resources.

Like tryAcquire() in acquire(), the tryRelease() method requires a custom synchronizer in exclusive mode to implement. Normally, tryRelease() will succeed because it is in exclusive mode, and the thread must have already taken the exclusive resource, subtracting the corresponding amount of resources (state-=arg) without worrying about thread safety.

But notice the return value. As mentioned above, release() is the return value of tryRelease() to determine if the thread has finished releasing the resource! So when implemented, the custom synchronizer returns true if the resource has been completely freed (state=0), and false otherwise.

The unparksucceeded (Node) method is used to wake up the next thread in the wait queue. Note here that the next thread is not necessarily the next node of the current node, but the next thread that can be woken up by calling the unpark() method if the node exists.

In summary, release() is the top-level entry for threads in exclusive mode to release shared resources. It frees a specified amount of resources, and if it frees completely (i.e., state=0), it wakes up other threads in the waiting queue to acquire resources. (It is important to note that the awakened thread in the queue does not necessarily acquire the resource immediately, because the resource may be immediately stolen by another thread (other than the thread waiting in the queue).)

AcquireShared (int) method

The acquireShared(int) method is the top-level entry for threads in shared mode to get shared resources. It will obtain a specified amount of resources, the success of the return, the failure to get into the waiting queue, until the resource, the whole process ignores interruption.

As you can see, the key implementation of this approach is actually managing threads after resource acquisition failures. That’s the logic of doAcquireShared.

As you can see, the logic of doAcquireShared is similar to that of acquireQueued. The current thread is added to the end of the queue to rest until other threads release resources to wake it up, and it successfully gets the corresponding amount of resources before returning.

AcquireShared:

Step1: tryAcquireShared() tries to get the resource and returns if it succeeds.

Step2: pass doAcquireShared() and enter wait queue park() until unpark()/interrupt() and resources are obtained successfully. The entire wait process is also interrupt-oblivious.

ReleaseShared (int) method

The releaseShared(int) method is the top-level entry for threads to releaseShared resources in shared mode. It frees a specified amount of resources, and if it successfully frees and allows the waiting thread to wake up, it wakes up other threads in the waiting queue to acquire resources.

After releasing the resource, wake up the successor. Similar to release() in exclusive mode, but with a slight note: Exclusive tryRelease() does not return true to wake up other threads until it has completely freed resources (state=0), mainly due to reentrant considerations. ReleaseShared () in shared mode has no such requirement. In shared mode, a certain number of threads are controlled to execute concurrently, so that the thread with the resource can wake up the waiting node when it releases some resources.