Overview of Abstract Synchronization Queue AQS

AQS is the underlying support for locks

AQS Class Diagram

From this figure, it can be seen that AQS is a FIFO bidirectional queue, which records the first and last elements of the queue through nodes head and tail. The type of queue element is Node. The thread variable in Node is used to store threads entering the AQS queue; The SHARED inside the Node node is used to mark that the thread was blocked and suspended when obtaining shared resources, and then placed in the AQS queue. EXCLUSIVE is used to mark that the thread was suspended when obtaining exclusive resources and then placed in the AQS queue; WaitStatus records the current thread waiting status, which can be CANCELLED (thread cancelled), SIGNAL (thread needs to be awakened), CONDITION (thread waiting in conditional queue), PROPAGATE (other nodes need to be notified when releasing shared resources); Prev records the predecessor node of the current node, and next records the successor node of the current node.

A single state information state is maintained in AQS, and its value can be modified through the getState, setState, and compareAndSetState functions. For the implementation of ReentrantLock, state can be used to represent the number of times the current thread can re-enter the lock; For the read-write lock ReentrantReadWriteLock, the high 16 bits of state represent the read state, which is the number of times the read lock was acquired, and the low 16 bits represent the number of times the thread that acquired the write lock can re-enter; For semaphores, state is used to represent the current number of available signals; For CountDownlatch, state is used to represent the current value of the counter.

AQS has an Inner class ConditionObject, which is used to implement thread synchronization in combination with locks. ConditionObject can directly access variables within AQS objects, such as state state values and AQS queues. ConditionObject is a condition variable. Each condition variable corresponds to a condition queue (singly linked list queue), which is used to store the blocked threads after calling the await method of the condition variable. As shown in the class diagram, the header and footer elements of this condition queue are firstWaiter and lastWaiter respectively.

For AQS, the key to thread synchronization is to operate on the state value state. According to whether a state belongs to a thread, the methods of operating a state are divided into exclusive mode and shared mode. The method for obtaining and releasing resources in exclusive mode is: void acquire (int arg) void acquire Interruptible (int arg) boolean release (int arg).

The method for obtaining and releasing resources in shared mode is: void acquireShared (int arg) void acquireSharedInterruptibly (int arg) boolean releaseShared (int arg).

The resource obtained using exclusive method is bound to a specific thread, which means that if a thread obtains a resource, it will be marked as having obtained it. When other threads try to operate the state to obtain the resource, they will find that the current resource is not owned by themselves, and will be blocked after the acquisition fails. For example, in the implementation of exclusive lock ReentrantLock, when a thread acquires the lock of ReentrantLock, it will first use the CAS operation inside AQS to change the state value from 0 to 1, and then set the current lock holder as the current thread. When the thread acquires the lock again and finds that it is the lock holder, it will change the state value from 1 to 2, which is to set the number of reentrances, When another thread obtains a lock and discovers that it is not the holder of the lock, it will be placed in the AQS blocking queue and suspended.

The resources corresponding to the sharing method are not related to the specific thread. When multiple threads request resources, they compete through CAS to obtain them. When one thread obtains the resources and another thread obtains them again, if the current resource can still meet its needs, then the frontline process only needs to use CAS to obtain them. For example, Semaphore semaphores, when a thread obtains a semaphore through the acquire () method, it first checks whether the current number of semaphores meets the needs. If it does not, it puts the current thread in the blocking queue. If it does, it obtains the semaphore through spin CAS.

The process of obtaining and releasing resources in exclusive mode is as follows:

1. When a thread calls the acquire (int arg) method to obtain exclusive resources, it will first use the tryAcquire method to attempt to obtain the resources, specifically by setting the value of the state variable. If successful, it will be returned directly. If unsuccessful, the current thread will be encapsulated as a Node node of type Node.EXCLUSIVE and inserted into the end of the AQS blocking queue, and the LockSupport. park (this) method will be called to suspend itself.
2. When a thread calls the release (int arg) method, it will try to use the tryRelease operation to release resources. This is to set the value of the state variable, and then call the LockSupport. unpark (thread) method to activate a blocked thread in the AQS queue. The activated thread uses tryAcquire to try and see if the current state variable state value meets its needs. If it does, the thread is activated and continues to run downwards. Otherwise, it will still be placed in the AQS queue and suspended.

It should be noted that the AQS class does not provide available tryAcquire and tryRelease methods, just as AQS is the basic framework for lock blocking and synchronizers, tryAcquire and tryRelease need to be implemented by specific subclasses. When subclasses implement tryAcquire and tryRelease, they need to use the CAS algorithm to try to modify the state value based on the specific scenario. If successful, they will return true, otherwise they will return false. Subclasses also need to define what the increase or decrease in state values represent when calling the acquire and release methods.

For example, the exclusive lock ReentrantLock inherited from AQS implementation defines that when status is 0, the lock is idle, and when status is 1, the lock is already occupied. When rewriting tryAcquire, the CAS algorithm needs to be used internally to check if the current state is 0. If it is 0, CAS is set to 1, and the current lock holder is set to the current thread. Then, true is returned, and false is returned if CAS fails.

For example, when implementing tryRelease for exclusive locks inherited from AQS implementation, the CAS algorithm needs to be used internally to modify the current state value from 1 to 0, set the current lock holder to null, and then return true. If CAS fails, it returns false.

The process of obtaining and releasing resources in a shared mode is as follows:

When a thread calls acquireShared (int arg) to obtain a shared resource, it first attempts to obtain the resource using tryAcquireShared by setting the value of the state variable. If successful, it returns directly. If unsuccessful, it encapsulates the current thread as a Node node of type Node. SHARED and inserts it into the end of the AQS blocking queue, using the LockSupport. park (this) method to suspend itself. 2. When a thread calls releaseShared (int arg), it will attempt to use the tryReleaseShared operation to release resources. Here, the value of the state variable is set, and then LockSupport. unpark (thread) is used to activate a blocked thread in the AQS queue. The activated thread uses tryReleaseShared to check whether the current state variable state value meets its needs. If it does, the thread is activated and continues to run downwards. Otherwise, it will still be placed in the AQS queue and suspended.

It should also be noted that the AQS class does not provide available tryAcquireShared and tryReleaseShared methods, just as AQS is the fundamental framework for lock blocking and synchronizers, tryAcquireShared and tryReleaseShared need to be implemented by specific subclasses. When subclasses implement tryAcquireShared and tryReleaseShared, they need to use the CAS algorithm to try to modify the state value based on the specific scenario. If successful, they return true, otherwise they return false.

For example, when rewriting tryAcquireShared, the read and write lock inherited from the AQS implementation, ReentrantReadWriteLock, first checks whether the write lock is held by another thread. If so, returns false directly. Otherwise, CAS is used to increment the upper 16 bits of the state (in ReentrantReadWriteLock, the upper 16 bits of the state are the number of times the read lock is obtained).

For example, when a read write lock inherited from the AQS implementation, ReentrantReadWriteLock, is rewritten by tryReleaseShared, the CAS algorithm needs to be used internally to subtract the high 16 bits of the current state value by 1, and then return true. If the CAS fails, it returns false.

In addition to rewriting the methods described above, locks implemented based on AQS also need to rewrite the isHeldExclusively method to determine whether the lock is exclusive or shared by the current thread.

Additionally, you may be curious that void acquire (int arg) and void acquire Interruptible (int arg) in exclusive mode have a function with the Interruptible keyword compared to void acquire Shared (int arg) and void acquire SharedInterruptible (int arg) in shared mode. So what is the difference between having this keyword and not having it? Let's talk about it.

In fact, a method without the Interruptible keyword means not responding to interrupts. This means that when a thread calls a method without the Interruptible keyword to obtain resources or fails to obtain resources and is suspended, another thread interrupts the thread. Therefore, the thread will not throw an exception because it is interrupted. Instead, it will continue to obtain resources or be suspended, meaning it will not respond to interrupts and ignore interrupts.

And methods with the Interruptible keyword need to respond to interrupts, that is, when a thread calls a method with the Interruptible keyword to obtain resources or fails to obtain resources, and other threads interrupt the thread, the thread will throw an InterruptedException exception and return.

Finally, let's take a look at how to maintain the queues provided by AQS, mainly focusing on queue entry operations.

• Queuing operation: When a thread fails to acquire a lock, it will be converted to a Node node, and then the enq (final Node node) method will be used to insert the node into the blocking queue of AQS.