76 What Are the Internal Principles of Aqs

76 What Are the Internal Principles of AQS #

In this lesson, we will mainly introduce the internal principle of AQS.

Analysis of the internal principle of AQS #

To analyze the internal principle of AQS, we need to focus on the key points. Because the internal of AQS is relatively complex, the code is long and not easy to understand. If we dive into reading the source code from the beginning, it is difficult to fully grasp it. So in this lesson, we extract the three most core parts of AQS as the key points to open the door of AQS.

What are these three parts? The three most core parts of AQS are state, queue, and important methods, such as acquire/release, implemented by collaborative utility classes. We will explain them in detail starting from these three parts.

State #

The first thing to explain is the state. If our AQS wants to manage or serve as a basic framework for collaborative utility classes, it must manage some states, which are represented by the state variable inside AQS. Its definition is as follows:

/**
 * The synchronization state.
 */
private volatile int state;

The meaning of the state is not fixed, it will vary depending on the specific implementation class. Here are a few examples.

For example, in the semaphore, the state represents the number of remaining permits. If we initially set the state to 10, it means there are a total of 10 permits. Then, when a thread takes away a permit, the state will become 9. So the state of the semaphore acts as an internal counter.

Another example is in the CountDownLatch utility class, where the state represents the number of “counts” needed. Suppose we initially set it to 5. When we call the CountDown method each time, the state will be reduced by 1. When it is reduced to 0, it means the latch has been opened.

Next, let’s take a look at what the state means in ReentrantLock. In ReentrantLock, it represents the lock occupation status. Initially, it is 0, indicating that no thread owns the lock. If the state becomes 1, it means the lock has been acquired by a thread.

Why does it become 2, 3, 4, and so on? Why does it increase? Because ReentrantLock is reentrant, the same thread can own the lock multiple times, which is called reentrancy. If the lock is acquired multiple times by the same thread, the state will gradually increase, indicating the number of times it has been reentrant. The release operation also reduces the state incrementally. For example, if the initial state is 4, after releasing once, it becomes 3, and after releasing again, it becomes 2. This decrement operation, even when it reaches 2 or 1, does not mean that the lock is not owned by any thread. Only when it is reduced to 0, which restores the initial state, it means that no thread owns the lock at this time. So when the state equals 0, it means the lock is not owned by any thread, indicating that the lock is currently in the release state, and other threads can try to acquire it.

This is how the state is represented with different meanings in different classes. We have given three examples. If there are new utilities in the future that utilize AQS, they will definitely need to use the state to represent their business logic and states.

Next, let’s take a look at the issue of modifying the state. Because the state is shared by multiple threads and modified concurrently, all methods that modify the state must ensure that it is thread-safe. However, the state itself is only volatile, and volatile alone is not enough to guarantee thread-safety. So let’s take a look at the specific design used by AQS to ensure concurrency safety when modifying the state.

We will take two methods related to the state as examples: compareAndSetState and setState. Their implementation has been completed by AQS, which means we can directly call these two methods to achieve thread-safe modification of the state. Now let’s take a look at the source code of these two methods.

First, let’s take a look at the compareAndSetState method, which is a very familiar CAS operation. The code of this method is as follows:

protected final boolean compareAndSetState(int expect, int update) {
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

There is only one line of code inside the method, which is return unsafe.compareAndSwapInt(this, stateOffset, expect, update). This method is very familiar to us. It utilizes the CAS operation in Unsafe, and the atomicity of this operation is guaranteed by the atomicity of CPU instructions, which is consistent with the principle of using atomic classes we introduced earlier to guarantee thread safety.

Next, let’s take a look at the source code of the setState method, which is as follows:

protected final void setState(int newState) {
    state = newState;
}

We can see that when modifying the value of the state, it is done directly by assigning state = newState. You may be confused because there is no concurrent safety handling here, no locking or CAS. How is thread safety ensured?

This is where the use of volatile comes in. As we learned earlier when studying the volatile keyword, it is applicable in two scenarios, one of which is when directly assigning a value to a primitive type variable. If volatile is added, it can ensure thread safety. Note that this is a very typical use case of volatile.

/**
 * The synchronization state.
 */
private volatile int state;

From this code, we can see that state is of type int, which is a primitive type. The setState method directly assigns a value to state without involving the reading of its previous value or modifying it based on the original value. Therefore, we only need to use volatile to ensure thread safety in this situation. That is the reason why the setState method is thread-safe.

Now let’s summarize state. In AQS, there is a property called state which is annotated with volatile and can be concurrently modified. It represents a certain state of the utility class and has different meanings in different classes.

FIFO Queue #

Now let’s take a look at the second core part of AQS, the FIFO queue. This queue’s primary purpose is to store waiting threads. Assume that many threads are trying to acquire the same lock at the same time. Most of them will fail to acquire the lock. How should we handle these threads that fail to acquire the lock? We need a queue to store and manage them. Therefore, a major function of AQS is to act as a “queue manager” for threads.

When multiple threads compete for the same lock, a queuing mechanism is needed to put those threads that fail to acquire the lock in order. When the preceding thread releases the lock, the manager selects a suitable thread to try to acquire the just released lock. Therefore, AQS is always maintaining this queue and putting the waiting threads into it.

The internal structure of this queue is a doubly linked list. Although its data structure seems simple, maintaining it as a thread-safe doubly linked queue is very complex because it involves many concurrency issues. Let’s take a look at a diagram of this queue provided by Doug Lea, the author of AQS:

Diagram 1.png

(This diagram is referenced from the figure in the English documentation)

In the queue, head and tail represent the head and tail nodes respectively. They are initialized to point to an empty node. The head node can be understood as the “thread currently holding the lock”, and the threads after the head node are blocked. They are waiting to be awakened, and awakening is also handled by AQS.

Acquire/Release Methods #

Now let’s take a look at the third core part of AQS, the acquire/release methods. In addition to the state and the queue mentioned earlier, there is another important part in AQS, which is the acquire and release methods. These methods are the concrete embodiment of the logic of the collaborative utility class and need to be implemented by each collaborative utility class individually, so their implementations and meanings vary in different tool classes.

Acquire Methods #

Let’s first take a look at the acquire methods. The acquisition operation usually depends on the value of the state variable. Depending on the value of the state, the collaborative utility class will have different logic, and it often blocks during acquisition. Let’s see a few specific examples.

For example, the lock method in ReentrantLock is one of the “acquire methods”. When it is executed, if it finds that the state is not equal to 0 and the current thread is not the thread holding the lock, it means that the lock is already held by another thread. At this time, it cannot acquire the lock and the thread enters a blocked state.

Another example is the acquire method in Semaphore, which is another “acquire method”. Its purpose is to acquire a permit, and whether it can acquire the permit depends on the value of the state. If the state value is positive, it means there are still remaining permits, and if the quantity is sufficient, it can be successfully acquired. However, if the state is 0, it means there are no more available permits, and the thread cannot acquire the permit and enters a blocked state. So this is also related to the value of the state.

Another example is the await method (including overloaded methods) in CountDownLatch, which is the acquire method for CountDownLatch. Its purpose is to “wait until countdown ends”. When await is executed, it checks the value of the state. If the state is not equal to 0, the thread enters a blocked state until other threads execute the countdown method and reduce the state to 0, which means the latch is now open, so the previously blocked thread is awakened.

In summary, “acquire methods” represent different meanings in different classes, but they are often related to the value of the state and often cause the thread to enter a blocked state, which also proves the important position of the state in the AQS class.

Release Methods #

Release methods are the opposite of acquire methods and are usually used in conjunction with the acquire methods. The acquire methods we just talked about may cause the thread to block. For example, if the lock cannot be acquired, the thread will enter a blocked state, but the release methods usually do not block threads.

For example, in Semaphore, release is the release method (including overloaded methods). The release() method is used to release a permit, which increases the state by 1. In CountDownLatch, release is the countDown method, which counts down a number and decreases the state by 1. So we can also see that in different implementing classes, their operations on the state are completely different and need to be specifically implemented by each collaborative class according to its own logic.

Conclusion #

In this lesson, we introduced the three most important parts of AQS. The first is the state, which is a numerical value that represents different meanings in different classes and often represents a state. The second is a queue, which is used to store threads. The third part is the “acquire/release” related methods, which need to be implemented by AQS’s utility classes based on their own logic.