Interviewer: ReentrantLock and Queue Synchronizer (AQS) from a source perspective

An implementation of an exclusive lock in the JDK can use ReentrantLock in addition to the keyword synchronized. Although ReentrantLock is not significantly different from synchronized in terms of performance, ReentrantLock is more feature-rich, more flexible to use, and more suitable for complex concurrent scenarios than synchronized.

ReentrantLock is often compared to synchronized, so let’s look at it first and then analyze it point by point.

1. Synchronized is an exclusive lock. The process of locking and unlocking is automatic and easy to operate, but not flexible enough. ReentrantLock is also an exclusive lock. The process of locking and unlocking a ReentrantLock is manual, difficult to operate, but flexible.
2. Synchronized can be re-entrant, because lock and unlock automatically, do not worry about whether the lock is finally released; ReentrantLock can also be reentrant, but the lock must be added and unlocked manually and the number of times must be the same; otherwise, the lock cannot be acquired by other threads.
3. Synchronized unresponsive interrupts, in which a thread waits until it can acquire a lock; ReentrantLock can be interrupted accordingly.

ReentrantLock doesn’t seem much better than synchronized, so let’s look at what synchronized doesn’t. One of the most important is that ReentrantLock also implements fair locking. What is a fair lock? The thread that waits the longest on the lock gets the lock. It is commonly understood that the longest queue is the first to perform the lock acquisition.

Before explaining already, must first understand a call AQS (queue synchronizer), this thing is and contract awarding, AQS AbstractQueuedSynchronizer namely, it is a core of Java and contract, Both ReentrantLock and ReentrantReadWriteLock are implemented based on AQS. Want to figure out is how to implement the already, you must first learn AbstractQueuedSynchronizer. This article combines JDK1.8 source code first analyzes the queue synchronizer, and then explains how to use the queue synchronizer in ReentrantLock to achieve an exclusive lock.

Queue synchronizer (AQS)

Queue synchronizer AbstractQueuedSynchronizer, is used to construct locks or other synchronous component based framework, it USES a volatile modified int member variable synchronous state, through the built-in FIFO queue to complete resources for thread line work.

The main use of synchronizer is inheritance. Subclasses manage synchronization state by inheriting the synchronizer and implementing its abstract methods. During the implementation of abstract methods, synchronization state must be changed. The three methods provided by the synchronizer, getState(), setState(int newState), and compareAndSetState(int expect, int Update), are needed to operate, because they guarantee that state changes are safe. Recommended is defined as a custom subclass synchronous components of a static inner class, synchronizer itself does not implement any synchronization interfaces, it simply defines a number of state synchronization acquisition and release methods for use by the custom synchronous components, synchronizer which can support the exclusive access to synchronous state, also can to support Shared access to sync, This makes it easy to implement different types of synchronization components (ReentrantLock, ReentrantReadWriteLock, CountDownLatch, and so on).

AQS are the key to implementing locks (or any synchronization component) : synchrones are aggregated within locks, and the semantics of the locks are implemented using synchronizers. The relationship between the two is as follows: the lock is user-oriented, and it defines the interface for the user to interact with the lock (such as allowing two threads to access it in parallel), hiding the implementation details; Synchronizer is a lock-oriented implementor, which simplifies the implementation of locks and shields the low-level operations such as synchronization management state, queuing, waiting and wake up of threads.

Queue synchronizer interface and template methods

The synchronizer is implemented based on the template design pattern, in which the consumer inherits the synchronizer and overwrites the specified methods, then combines the synchronizer into a custom synchronization component implementation and calls the template methods provided by the synchronizer, which invoke the user-overwritten methods.

Overriding synchronizer specified methods requires the following three methods provided by the synchronizer to access or modify synchronization state:

• GetState (): Gets the current synchronization status
• SetState (int new State): Sets the current synchronization status
• CompareAndState (int expect, int update): Uses CAS to set the current state. This method ensures atomicity of state Settings.

Methods that synchronizer can override:

Implementing custom components synchronously, will call AbstractQueuedSynchronizer itself has written template method, the template method and description:

A method that the synchronizer can override

Note: Template methods are basically divided into three types: exclusive synchronization state acquisition and release, shared synchronization state acquisition and release, and query the status of waiting threads in the synchronization queue.

AbstractQueuedSynchronizer requires a subclass to override a method is as follows, demand it subclasses override these methods, in order to make the user can add their own judgment logic.

Template methods provided by the synchronizer

AQS provides many methods to implement locks

• getState(): gets the flag state value of the lock
• setState(): Sets the state value of the lock flag
• tryAcquire(int): Obtains the lock in exclusive mode. Attempts to obtain the resource return true on success and false on failure
• tryRelease(int): Releases locks in exclusive mode. Attempts to free resources return true on success and false on failure

Queue synchronizer data structure

Synchronizer depends on the internal synchronous queue (two-way a FIFO queue) to complete synchronization state management, the current thread for synchronous state failure, synchronizer will the information such as the current thread and wait states constitute a Node (the Node) and add it to the synchronous queue, blocking the current thread at the same time, when sync release, will be the first Node of threads in the awakening, Make it try again to get the synchronization status.

In AbstractQueuedSynchronizer class, Node class is a static inner class, its source code is as follows:

static final class Node { /** Marker to indicate a node is waiting in shared mode */ static final Node SHARED = new Node(); /** Marker to indicate a node is waiting in exclusive mode */ static final Node EXCLUSIVE = null; /** waitStatus value to indicate thread has cancelled */ static final int CANCELLED = 1; /** waitStatus value to indicate successor's thread needs unparking */ static final int SIGNAL = -1; /** waitStatus value to indicate thread is waiting on condition */ static final int CONDITION = -2; /** * waitStatus value to indicate the next acquireShared should * unconditionally propagate */ static final int PROPAGATE = -3; Volatile int waitStatus; // The pointer to the previous Node is volatile Node prev; // Pointer to the next Node volatile Node next; // The current node represents the Thread volatile Thread Thread; If the current Node is SHARED, this field will be a SHARED constant, i.e. the Node type (exclusive and SHARED) and the successor Node in the wait queue share the same field Node nextWaiter. /** * Returns true if node is waiting in shared mode. */ final boolean isShared() { return nextWaiter == SHARED; } final Node predecessor() throws NullPointerException { Node p = prev; if (p == null) throw new NullPointerException(); else return p; } Node() { // Used to establish initial head or SHARED marker } Node(Thread thread, Node mode) { // Used by addWaiter this.nextWaiter = mode; this.thread = thread; } Node(Thread thread, int waitStatus) { // Used by Condition this.waitStatus = waitStatus; this.thread = thread; }}Copy the code

In AbstractQueuedSynchronizer class, meanwhile, and separately defines the queue head nodes, tail, synchronous state variables.

Private TRANSIENT volatile Node head; Private TRANSIENT volatile Node tail; // Private volatile int state; protected final int getState() { return state; } protected final void setState(int newState) { state = newState; } protected final boolean compareAndSetState(int expect, int update) { // See below for intrinsics setup to support this return unsafe.compareAndSwapInt(this, stateOffset, expect, update); }Copy the code

The structure of the synchronization queue is shown below:

The structure of the synchronization queue

In order to have a better understanding of the lock and unlock process source code, the characteristics of the synchronization queue for a simple description:

1. A synchronous queue is a first-in, first-out (FIFO) queue. The thread that fails to acquire the lock will construct a node and join the end of the queue. The process of joining the queue must be thread safe. Because there are multiple threads that do not get the synchronization state at the same time and want to join the end of the synchronization queue;
2. The start node of the queue is the thread node that successfully obtains the synchronization state.
3. After releasing the lock, the thread of the precursor node attempts to wake up the blocked thread of the successor node

The process by which a synchronizer adds a node to a synchronization queue:

The process by which a synchronizer adds a node to a synchronization queue

The synchronization queue follows FIFO. The first node is the node that successfully obtains the synchronization state. When the thread of the first node releases the synchronization state, it will wake up the successor node, and the successor node will set itself as the new first node when successfully obtains the synchronization state.

Synchronous queues follow FIFO

Note: The first node is set by the thread that has obtained the synchronization state. Since only one thread can obtain the synchronization state, the method of setting the head node does not require CAS. It only requires the head pointer to point to the successor node of the original first node and disconnects the next reference of the original first node.

Exclusive method of obtaining synchronization state provided by the queue synchronizer

Through AbstractQueuedSynchronizer class provides acquire (int arg) method can obtain synchronous state, this method is not sensitive to interrupt, that is because the thread into the synchronous queue, after acquiring the synchronization status failed subsequent to interrupt the operation of the thread, the thread will not remove from the synchronous queue. Acquire methods:

Public final void acquire (int arg) {/ / tryAcquie () method should give specific subclass to be realized, AbstractQueuedSynchronizer class does not implement the if (! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code

The above code has completed the synchronization state acquisition, node construction, join the synchronization queue and synchronization queue spin waiting related work.

First call the custom synchronizer (AbstractQueuedSynchronizer subclass) implementation of tryAcquire (int arg) method, this method guarantees thread-safe access to the synchronous state, if the sync status for failure, the tectonic synchronous Node (EXCLUSIVE Node. The EXCLUSIVE, AcquireQueued (Node Node,int arg) is invoked to obtain the synchronization status in an “infinite loop” mode after the addWaiter(Node Node) method is added to the end of the queue. If not, the thread in the node is blocked, and the blocked thread is woken up mainly by the disqueuing of the precursor node or the blocking thread is interrupted.

The addWaiter and enQ methods are used to construct the node and join the synchronous queue:

Private Node addWaiter(Node mode) {void Node = new Node(thread.currentThread (), mode); // Try the fast path of enq; backup to full enq on failure Node pred = tail; if (pred ! = null) { node.prev = pred; if (compareAndSetTail(pred, node)) { pred.next = node; return node; }} /// join the queue logic enq(node); return node; } /** * The logic of adding nodes to the end of the queue when it is not empty is also present in the ENq (node) method. The reason for this "duplicate code" is that some special cases are processed in advance and some code readability is sacrificed in exchange for improved performance. */ private Node enq(final Node node) { for (;;) {//t indicates the last Node in the current queue, null Node t = tail; If (t == null) {if (t == null) { If (compareAndSetHead(new Node())) tail = head; if (compareAndSetHead(new Node())) tail = head; } else {// The queue is not empty node.prev = t; If (compareAndSetTail(t, node)) {//CAS sets the tail pointer to the current node. // Next pointer to current node return t; } } } } 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; // Normal dead-loop only exit return interrupted; } / / judge whether to block the current thread if (shouldParkAfterFailedAcquire (p, node) && parkAndCheckInterrupt ()) interrupted = true; } } finally { if (failed) cancelAcquire(node); }}Copy the code

After looking at the enQ (Final Node Node) method, it turns out that the head Node of the AQS queue is actually a sentinel Node.

In enQ (Final Node Node), the synchronizer ensures that nodes are added through an infinite loop, in which the current thread can only return from CAS after the current Node is set to tail, otherwise the current thread keeps trying to set. The ENQ (Final Node Node) method serializes requests for concurrent Node addition through CAS. Cyclic and CAS operations are the standard way to implement optimistic locking. CAS were created to implement atomic operations, which are performed without interference from other threads. The CAS implemented in Java calls the unsafe class’s methods, and the underlying CAS calls C++ methods, which operate directly on memory and lock it at the CPU level.

To see shouldParkAfterFailedAcquire (Node Mr Pred, Node Node), we can probably guess from the method name is this judgment whether to block the current thread, the source code is as follows:

private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { int ws = pred.waitStatus; If (ws == node. SIGNAL) // This Node has already set status asking a release * to SIGNAL it, so it can safely park. */ return true; CANCELLED (ws > 0) { /* * Predecessor was cancelled. Skip over predecessors and * indicate retry. */ do { node.prev = pred = pred.prev; } while (pred.waitStatus > 0); pred.next = node; Indicate that we * need a signal. Indicate that we * need a signal. but don't park yet. Caller will need to * retry to make sure it cannot acquire before parking. */ compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; }Copy the code

We can see that the state of the precursor node pred is handled differently:

1. If pred is SIGNAL, true is returned, indicating that the current thread is to be blocked.
2. If the status of pred is CANCELLED, the node should be traced back to the head of the queue until it finds a node whose status is not CANCELLED, and the current node node should be suspended behind this node.
3. The pred status is initialized. In this case, the CAS operation is performed to change the preD status to SIGNAL

SIGNAL means that if the thread releases the lock, it will wake up any subsequent blocking thread. After all, the current thread can safely block only if it is guaranteed to wake up.

Note that immediate blocking is performed only after the precursor node is already in SIGNAL state, which corresponds to the first case above. The other two cases are reexecuted because false is returned

The source of the acquireQueued() method shows that a node enters a spin state after being queued. Each node (or thread) is introspectively observed and can exit the spin process when the condition is met and the synchronization state is obtained. Otherwise, it remains in the spin process.

This process is illustrated below.

The spin state

In the acquireQueued(Final Node Node, int arg) method, a thread attempts to obtain the synchronization state in an “infinite loop” and can only attempt to obtain the synchronization state if the drive Node is the head Node, for the following reasons:

1. The head node is the node that has successfully obtained the synchronization state, and the thread of the head node will wake up the subsequent node after obtaining the synchronization state. The thread of the subsequent node needs to check whether its precursor node is the head node after being awakened.
2. Maintain the FIFO principle for synchronization queues

It can be seen that nodes and nodes basically do not communicate with each other in the process of cyclic checking, but simply judge whether their precursor is the head node, which makes the release of nodes conform to FIFO, and facilitates the processing of premature notification.

Acquire (int ARg) :

Exclusive synchronization state obtaining process

When the synchronization status is acquired successfully, the current thread returns from acquire(int arg), which means that the current thread has acquired the lock.

An exclusive synchronization state release method provided by the queue synchronizer

To release the synchronization state, the synchronization state can be released by calling the release(int arg) method of the synchronizer, which wakes up subsequent nodes after releasing the synchronization state (thus causing them to try again to get the synchronization state). Unlock the source code is relatively simple, the code is as follows:

Public final Boolean release(int arg) {//tryRelease(); AbstractQueuedSynchronizer class does not implement the if (tryRelease (arg)) {Node h = head; // The current queue is not empty and the header state is not initialized (0) if (h! = null && h.waitStatus ! = 0) unparkSuccessor(h); // Wake up a blocked thread in the sync queue return true; } return false; }Copy the code

If the current thread has fully released the lock, that is, the lock can be used by other threads, then subsequent waiting threads should also wake up. However, two conditions need to be judged before this:

• h ! = nullTo prevent the queue from being empty, that is, there are no threads in the waiting queue, so there is no need to wake up;
• h.waitStatus ! = 0A thread must set the state of its precursor node to SIGNAL before it blocks itself; otherwise, it will not block itself.

The unparkSuccerssor(Node Node) method uses LcokSupport to wake up threads in the waiting (blocking) state.

private void unparkSuccessor(Node node) { int ws = node.waitStatus; if (ws < 0) compareAndSetWaitStatus(node, ws, 0); Node s = node.next; if (s == null || s.waitStatus > 0) { s = null; For (Node t = tail; t ! = null && t ! = node; t = t.prev) if (t.waitStatus <= 0) s = t; } if (s ! = null) LockSupport.unpark(s.thread); }Copy the code

Normally, it’s just a matter of waking up the thread of the successor node, but the successor node may have canceled the wait, so go back to the end of the queue, find the normal node closest to the head node, and wake up its thread.

Release (int arg); release(int arg);

Exclusive synchronization state release process

Exclusive synchronization state acquisition and release:

• When the synchronization status is obtained, the synchronizer maintains a synchronization queue, and the thread that fails to obtain the synchronization queue is added to the synchronization queue, and spins in the synchronization queue (determine its own leading node as the head node).
• The condition for moving out of the queue (stopping spin) is that the leading node is the head node and synchronization status has been successfully obtained. The synchronizer is called when synchronizing state is releasedtryRelease(int arg)Method to release the synchronization state and wake up the successor nodes of the head node.

Shared synchronization state acquisition and release

The difference between shared and exclusive fetches is whether more than one thread can obtain the synchronization state at the same time.

Take reading and writing files as an example:

1. If a program is reading the file, all writes are blocked at that time, but reads can be performed simultaneously.
2. If a program is writing to a file, all other write and read operations are blocked at that moment.
3. Write operations require exclusive access to resources, while read operations can be shared access.

The acquireShared() template method of the synchronizer is called to share the state of the synchronization.

public final void acquireShared(int arg) { if (tryAcquireShared(arg) < 0) doAcquireShared(arg); } private void doAcquireShared(int arg) {// The current Node joins the queue final Node Node = addWaiter(node.shared); boolean failed = true; try { boolean interrupted = false; for (;;) Final Node p = node.predecessor(); If (p == head) {int r = tryAcquireShared(arg); if (r >= 0) { setHeadAndPropagate(node, r); p.next = null; // help GC if (interrupted) selfInterrupt(); failed = false; return; }} / / the current thread with LockSupport park method blocked the if (shouldParkAfterFailedAcquire (p, node) && parkAndCheckInterrupt()) interrupted = true; } } finally { if (failed) cancelAcquire(node); }}Copy the code

• The current thread calls firsttryAcquireShared()This method, overridden by subclasses, gets synchronized state shared. If the value is greater than or equal to 0, the command is successfully obtained and returned.
• If the return value is less than 0, the fetch failed. Call the doAcquireShared() method to put the thread into a spin state.
• During spin, if the precursor node of the current node is a head node, and calltryAcquireShared()Method returns a value greater than or equal to 0, then exits the spin. Otherwise, go ahead and spin.

public final boolean releaseShared(int arg) {
    if (tryReleaseShared(arg)) {
        doReleaseShared();
        return true;
    }
    return false;
}
Copy the code

First try to release the resource tryReleaseShared(arG). If the release succeeds, it means that the resource is free. Then use doReleaseShared() to wake up subsequent nodes.

Application of ReentrantLock to queue synchronizers

The syncronized keyword implicitly supports re-entry, such as syncronized referring to a recursive method in which the thread of execution acquires the lock multiple times in a row.

ReentrantLock does not support implicit reentry like the synchronized keyword, but when the lock() method is called, a thread that has acquired the lock can call the lock() method again without being blocked. To implement reentrant features, two problems need to be solved:

• The thread acquires the lock again. The lock needs to identify whether the thread that acquires the lock is the thread that currently occupies the lock. If so, it acquires the lock again successfully
• When the lock is finally released, the thread acquires the lock n times, and after the NTH release, the other thread acquires the lock. The final release of the lock requires the lock to increment for acquisition and decrement for release, and when the count equals 0, the lock has been successfully released.

ReentrantLock enables ReentrantLock acquisition and release by combining custom queue synchronizers.

ReentrantLock implements the Lock interface. Sync and ReentrantLock are combinatorial relations. FairSync and NonfairySync are subclasses of Sync.

FairSync, NonfairySync, Sync

A fair lock is FairSync, and an unfair lock is NonfairSync. Whether FairSync or NonfariSync, inherited from indirect AbstractQueuedSynchronizer this abstract class, as shown in the figure below

NonfariSync class diagram

ReentrantLock Acquires and releases locks in unfair mode

The code for ReentrantLock in unfair mode is as follows:

Public void Lock () {// In non-fair mode,sync refers to the object type NonfairSync sync.lock(); } // Implement the tryLock method of the Lock interface, try to obtain the Lock without blocking, call this method immediately return, Public Boolean tryLock() {return sync.nonfairtryacquire (1); }Copy the code

Static inner class NonfairSync source code:

static final class NonfairSync extends Sync { private static final long serialVersionUID = 7316153563782823691L; /** * Performs lock. Try immediate barge, Backing up to normal * acquire on failure. */ final void lock() {backing up to normal * acquire on failure. If (compareAndSetState(0, 1)) setExclusiveOwnerThread(thread.currentThread ()); The else / / here is calling the superclass AbstractQueuedSynchronizer acquire () method, // Acquire() will call the tryAcquiretryAcquire() method implemented by the subclass. } protected final boolean tryAcquire(int acquires) { return nonfairTryAcquire(acquires); }}Copy the code

NonfairTryAcquire () ¶

// This method is written in Sync class, Final Boolean nonfairTryAcquire(int acquires) {final Thread current = thread.currentThread (); int c = getState(); If (compareAndSetState(0, acquires)) {setExclusiveOwnerThread(current); return true; } } else if (current == getExclusiveOwnerThread()) { int nextc = c + acquires; if (nextc < 0) // overflow throw new Error("Maximum lock count exceeded"); setState(nextc); return true; } return false; }Copy the code

The nonfairTryAcquire() method adds the logic to acquire the synchronization state again: the acquisition succeeds by determining whether the current thread is the one that has acquired the lock. If so, the value of the synchronization state is increased and true is returned, indicating that the synchronization state was acquired successfully.

Unlock method of ReentrantLock:

Public void unlock () {/ / here is calling the superclass AbstractQueuedSynchronizer release () method, Sync.release (1); Sync (tryRelease()); Sync (tryRelease()); }Copy the code

The tryAcquire() method is implemented by the NonfairSync and FairSync classes respectively since the difference between a fair lock and an unfair lock is mainly in the acquisition of the lock. The lock release process is the same regardless of the fair lock or the unfair lock. So the tryRelease() method is implemented by the Sync class. The source code is as follows:

protected final boolean tryRelease(int releases) { int c = getState() - releases; if (Thread.currentThread() ! = getExclusiveOwnerThread()) throw new IllegalMonitorStateException(); boolean free = false; if (c == 0) { free = true; setExclusiveOwnerThread(null); } setState(c); return free; }Copy the code

If the lock is acquired N times, then the previous (n-1) tryRelease(int Releases) method must return false, and only return true if the synchronization state is fully released.

ReentrantLock Fair mode to acquire and release locks

In fair lock mode, there are strict restrictions on lock acquisition. In the case that the synchronization queue has threads waiting, all threads must join the synchronization queue before acquiring the lock, and the threads in the queue obtain the lock in the order in which they join the queue.

static final class FairSync extends Sync { private static final long serialVersionUID = -3000897897090466540L; Final void the lock () {/ / here is calling the superclass AbstractQueuedSynchronizer acquire () method / / parent acquire () method will be called tryAcquire () method, This method is implemented by subclasses, which eventually call the tryAcquire() method acquire(1) of the FairSync implementation; } /** * Fair version of tryAcquire. Don't grant access unless * recursive call or no waiters or is first. */ protected final boolean tryAcquire(int acquires) { final Thread current = Thread.currentThread(); int c = getState(); If (c == 0) {// Add hasqueuedToraise () method before the real CAS obtains the lock if (! hasQueuedPredecessors() && compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } } else if (current == getExclusiveOwnerThread()) { int nextc = c + acquires; If (nexTC < 0) throw new Error("Maximum lock count exceeded"); setState(nextc); return true; } return false; }}Copy the code

HasQueuedPredecessors () method in the AbstractQueuedSynchronizer class (a typical application of the template method pattern, all public methods all written by AbstractQueuedSynchronizer, Only personalization logic is subclass to implement), source code as follows:

public final boolean hasQueuedPredecessors() { // The correctness of this depends on head being initialized // before tail and on head.next being accurate if the current // thread is first in queue. Node t = tail; // Read fields in reverse initialization order Node h = head; Node s; return h ! = t && ((s = h.next) == null || s.thread ! = Thread.currentThread()); }Copy the code

Which thread in the queue has the highest priority? Since the head node is the thread currently acquiring the lock, the second node in the queue represents the thread with the highest priority. All you have to do is check whether the second node in the queue exists and whether it represents the current thread. Here are two cases to discuss:

• The second node is fully inserted, but it is not known whether this node is the same node as the current thread. Thread.currentthread (); if true, the second node represents another Thread.

• The second node is not fully inserted, and we know that there are three steps to join the node:

• 1. The pre pointer of the node to be inserted points to the original tail node;
  2. CAS update tail pointer;
  3. The next pointer to the original tail points to the newly inserted node. so(s = h.next) == nullThis is the case where 2 has just been executed but 3 has not yet been executed. In this case the second node must belong to another thread.

When a thread with a higher priority is waiting in the queue, the current thread will not perform CAS operation to obtain the lock, which ensures that the sequence of obtaining the lock is the same as that of joining the synchronization queue. This ensures fairness, but also increases the cost of obtaining the lock.

How does synchronous queue based on FIFO realize unfair lock preemption

By the nature of FIFO queues, the thread that joins the synchronous queue first is closer to the head of the queue than the thread that joins the queue later, so it will wake up earlier than the latter, and it can get the lock earlier. In this sense, it is clearly a fair pattern for threads waiting in a synchronous queue to acquire locks in the same order as they joined the synchronous queue. However, it is not only when a thread joins the queue that it has the opportunity to acquire the lock, even if there are already threads waiting in the synchronized queue. This is where unfair locking is unfair. Looking back at the process of locking an unfair lock, the thread has two opportunities to preempt the lock before entering the synchronous queue to wait:

• The first non-reentrant lock acquisition succeeds only if the current lock is not owned by any thread (including itself).
• The second is the way to acquire the lock in all cases before entering the synchronization queue

Only after these two failed to acquire the lock will the thread construct the node and join the synchronous queue to wait. When a thread releases a lock, it first releases the lock (changing the state value) and then wakes up subsequent threads. Imagine A situation where thread A has released the lock, but has not yet woken up its successor thread C, and another thread B tries to acquire the lock, which is not held by any thread, so it will acquire the lock without being queued. Thread C then wakes up to try to acquire the lock, which has already been preempted by thread B, so it fails to acquire the lock and continues to wait in the queue.

An unfair lock is really unfair in terms of the order in which a thread succeeds in acquiring the lock from its first attempt. This is because a thread that has been queuing for a long time does not have priority over a thread that has not yet queued, and it is even at a competitive disadvantage: a thread waiting in the queue must wait for its precursor thread to wake up, and must check whether its precursor is a header before acquiring the lock. In the case of hotly contested locks, threads waiting in the queue may be slow to compete for locks. This is not fair in the case of high concurrency in the hunger problem.

Why do unfair locks perform better

Unfair lock to lock competition is preemptive (except for threads already in the wait queue), and threads can make two attempts before entering the wait queue, greatly increasing their chances of acquiring the lock. This benefit can be seen in two ways:

• The thread can obtain the lock without joining the waiting queue, which not only avoids the tedious operation of constructing nodes and joining the queue, but also saves the overhead of thread blocking and waking up. Thread blocking and waking up involve the switch of thread context and the system call of the operating system, which is very time-consuming. In the case of high concurrency, the concurrency benefit of preemption is even more pronounced if the lock is held by a thread for such a short time that the queue blocking process exceeds the time cost of holding and releasing the lock.
• Reduce CAS contention. If threads must join the blocking queue to acquire the lock, the CAS competition will become extremely fierce when joining the queue. Although THE CAS operation will not cause the failed thread to hang, the waste of CPU caused by the continuous failed spin should not be ignored.

Application of AQS in other synchronization tools

In the custom synchronizer implementation of ReentrantLock, synchronization status represents the number of times the lock has been repeatedly acquired by a thread. In addition to ReentrantLock, AQS is also widely used in other synchronization tools.

ReentrantReadWriteLock: The ReentrantReadWriteLock class uses the lower 16 bits in the AQS synchronization status to store the number of write locks held, and the higher 16 bits to store the number of read locks held. Because WriteLock is also an exclusive lock, it is built the same way as ReentrantLock. ReadLock supports multiple reader threads at the same time by using the acquireShared method.

AQS synchronization status

Semaphore: The Semaphore class (Semaphore) uses the AQS synchronization state to hold the current count of the Semaphore. The acquireShared method defined in it reduces the count or blocks the thread if the count is non-positive; The tryRelease method increments the count and unblocks the thread if the count is positive.

CountDownLatch: The CountDownLatch class uses the AQS synchronization status to represent the count. When the count is 0, all acquire operations (corresponding to the await method in CountDownLatch) can pass.

FutureTask: The FutureTask class uses the AQS synchronization status to indicate the running status (initialized, running, canceled, and completed) of an asynchronous computing task. AQS release is called when setting (FutureTask’s set method) or canceling (FutureTask’s cancel method) a FutureTask. Unblocking of the thread waiting for the result of the calculation is done through the ACQUIRE operation of AQS.

SynchronousQueues: The SynchronousQueues class uses internal wait nodes that can be used to coordinate producers and consumers. At the same time, it uses the AQS synchronization state to control when a consumer consumes the current item, allowing a producer to continue producing and vice versa.

Search the public account of “Programmer Black brother” on wechat, and brush it every day to easily improve skills and win various offers: