Fairness means that all threads apply for access to critical resources with the same success rate. It does not give priority to some threads. Through the analysis of several articles, we know that the LOCK of JDK AQS is optimized based on CLH lock, which uses FIFO queue, that is to say, the wait queue is a first-in, first-out queue. Is it fair to say that each thread acquires the lock? Fairness is strictly divided into three points: the team entry stage, the wake up stage, and the break-in strategy.

Links:

• What is the JDK built-in concurrency framework AQS
• How can the atomicity of AQS be guaranteed
• Optimization of CLH lock by AQS

The stage of entrance

Wake up the stage

When a thread node successfully joins the wait queue and becomes a node in the wait queue, and this is a first-in, first-out queue, we can conclude that all nodes in the queue are fair. Because all nodes in the wait queue wait sequentially for themselves to be awakened by the precursor node and acquire the lock, nodes in the wait queue are fair.

Broke into the strategy

Intrusion policy is a policy designed by AQS framework to improve performance. Specifically, when a new thread reaches the boundary of a shared resource, regardless of whether there are other waiting nodes in the waiting queue, the new thread will try to obtain the lock first, which looks like an intrusion behavior. The intrusion strategy destroys fairness, and the fairness externally reflected by AQS framework is mainly reflected by this.

The lock acquisition operation provided by AQS uses break-in algorithm, that is, if there is a new thread coming, the current thread will be added to the waiting queue only when the acquisition attempt fails. In the figure below, node threads in the waiting queue attempt to acquire access to a shared resource in sequence, one after another. At some point, when the thread of the head node is about to try to acquire resources, another thread enters the queue. The new thread does not directly join the end of the waiting queue, but competes with the thread of the head node to obtain resources. The interloper thread executes directly if it succeeds in obtaining the shared resource, and the header thread continues to wait for the next attempt. In this case, if the thread enters the queue successfully, the subsequent thread executes before the earlier thread, indicating that the AQS lock acquisition algorithm is not strict and fair.

In logic

The following figure shows the pseudo-code for the lock acquisition algorithm that contains the break-in strategy. We focus on the logic of the red box. It tries directly to acquire the lock first, and creates the node and joins the end of the wait queue if the acquisition fails.

Why is a break-in strategy needed

Why use break-in tactics? Break-in strategies often improve overall throughput. Because the granularity of the common synchronizer is relatively small, it can also be said that the scope of shared resources is small, and the time cycle consumed by the thread from the blocked state to the wake up may be several times or even dozens of times of the time cycle through shared resources.

As a result, there will be a large time period in the wake up process of threads, resulting in under-utilization of resources, and it will be inefficient if every thread is queued before waking up. This intrusion strategy was introduced to avoid unnecessary thread hangs and wakes, and to improve throughput. It can make full use of the blocking wake up window and avoid unnecessary suspend and wake up operations, thus greatly increasing throughput.

The implementation of the break-in mechanism provides a competitive adjustment mechanism for developers to define the number of break-in attempts to obtain in a custom synchronizer. Assuming that the number of times is N, the thread will be added to the waiting queue after repeated acquisition until the number of times is unsuccessful. With the increase of times n, the probability of successful entry will increase. At the same time, this intrusion strategy can lead to starvation of the threads in the wait queue, as the lock may always be acquired by the trespassing thread. However, since the time of holding the synchronizer is generally very short, hunger can be avoided, whereas if holding the lock for a long time, it will greatly increase the risk of waiting for the queue to wait indefinitely.

conclusion

In practice, we need to make policies according to the requirements. In a scenario with high fairness requirements, we can remove the intrusion strategy to achieve fairness. In the custom synchronizer, it can be realized by AQS reservation method tryAcquire method. It only needs to determine whether the current thread is the thread corresponding to the head node in the wait queue. If not, return false. The attempt failed. However, this fairness is relative to the Java semantic level of fairness, in reality, the implementation of JVM may also directly affect the order of thread execution.