ReentrantLock is a very important synchronization component in concurrent programming, and locks or other synchronization components can be built through the AQS synchronizer. This article will use ReentrantLock source code to analyze the working principle of AQS.
A list,
AQS members (AbstractQueuedSynchronizer) use an int variable state synchronization state (the state of 0, said the current resource is not occupied, the state > 0, said that the current resources have been occupied). Combined with a built-in synchronization queue (FIFO) to complete the waiting queue of the resource acquisition thread, if the current thread does not get the lock, then the thread is encapsulated as a Node Node, join the synchronization queue, wait to wake up, try to get the lock by means of spin.
Node Node composition
- WaitStatus: indicates the waitStatus
- Node prev: indicates a precursor Node
- Node next: indicates the successor Node
- Thread Thread: obtains the synchronization status of the Thread
- Node nextWaiter: the successor Node in the wait queue
Node Node status: waitStatus
- INITIAL=0: indicates the INITIAL state
- SIGNAL=-1: The thread of the successor node is in the waiting state. If the current node releases the synchronization state, the successor node will be notified
- CONDITION=-2: The node is in the wait queue, and the node thread is waiting on CONDITION. When another thread calls signal on CONDITION, the node will be transferred from the wait queue to the synchronization queue and added to the synchronization state
- PROPAGATE=-3: indicates that the next shared synchronization state acquisition will be transmitted unconditionally
- CANNELED=1: A thread waiting in the synchronization queue has timed out or is interrupted. The wait needs to be canceled from the synchronization queue. The node enters the state unchanged
Second, source code analysis
2.1 lock
Start with the Lock method of ReentrantLock
public void lock(a) {
sync.lock();
}
Copy the codeYou can find the Lock method of the sync object that ReentrantLock actually calls, which is a static inner class inside ReentrantLock
abstract static class Sync extends AbstractQueuedSynchronizer {
// ...
}
Copy the codeThe sync class has two implementations: FairSync and NonfairSync, which correspond to fair and unfair locks, respectively. First from the point of view of the non-fair lock analysis of the source code, below using sync to replace the non-fair lock NonfairSync
final void lock(a) {
// Try to obtain the lock through CAS
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
Copy the codeThe sync class lock method first attempts to change the state bit 1 through CAS. If the change succeeds, the current thread has acquired the lock. Otherwise, call acquire method to attempt locking.
// AQS implements methods, subclasses cannot be overridden
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeInside the acquire method, try again to acquire the lock through tryAcquire
TryAcquire needs to subclass the implementation, find the implementation of NonfairSync
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
// There is no current lock
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true; }}else if (current == getExclusiveOwnerThread()) {
// The thread that acquired the lock is the current thread (reentrant)
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
Copy the codeIf the current thread already owns the lock, return status +acquires (lock acquires required, reentrant). If no lock was obtained, false is returned
Back to the acquire method, assuming that tryAcquire did not lock successfully, continue tracing addWaiter, as you can guess by the method name, which wraps the current thread into a Node
// Synchronize queue header pointer, null by default
private transient volatile Node head;
// Synchronize the queue tail pointer, null by default
private transient volatile Node tail;
// mode= node.exclusive
private Node addWaiter(Node mode) {
Node 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;
}
}
enq(node);
return node;
}
Copy the codeWrap the current thread into a Node object. If the current queue is empty, head and tail are both null by default. = null) condition not found, continue to trace enq method
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
returnt; }}}}Copy the codeIf (t == null), CAS sets the head Node to an empty Node (sentinel Node), and then sets tail and head to both sentinel nodes
The sentinel node represents the thread that currently has the lock and is executing the business logic
For the second loop, t is not null (t refers to the sentinel node), and the precursor pointer to Node (the object encapsulated by the current thread) points to T, which is the sentinel node created in the first loop
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;
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true; }}finally {
if(failed) cancelAcquire(node); }}Copy the codeFirst, obtain the precursor Node P of the current thread Node Node, and determine whether the precursor Node P is the head Node. According to the above analysis, p is the head node and then attempts to acquire the lock through tryAcquire method.
- If the lock is successful, the current Node is set as the head Node, and the next pointer of the previously created sentinel Node points to null, that is, the association between the sentinel Node and the current thread Node is disconnected, and the current thread has obtained the lock.
- If the lock fails, the call shouldParkAfterFailedAcquire method
// pred= head node (sentry node), node= successor node of head node
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
Copy the codeThe current wait state of the header is initial, so go to the else code block, set the header state to SIGNAL(-1), and continue the next loop. Assuming that the next cycle is still no locking success, again into shouldParkAfterFailedAcquire method, the current state head nodes has become a SIGNAL, return true, continue to call parkAndCheckInterrupt method
private final boolean parkAndCheckInterrupt(a) {
LockSupport.park(this);
return Thread.interrupted();
}
Copy the codeAs you can see, the current thread is blocked and enters the wait state.
Now that the thread locking failure has been completed, the source code is queued up in the synchronous queue. Let’s continue to see how the waiting thread is woken up.
2.2 release the lock
A queued thread must be awakened by another thread releasing the lock, so we continue to trace the unlock method of ReentrantLock
/ / already method
public void unlock(a) {
sync.release(1);
}
/ / already. The Sync method
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if(h ! =null&& h.waitStatus ! =0)
unparkSuccessor(h);
return true;
}
return false;
}
Copy the codeReentrantLock releases the lock through Sync’s release method, which calls the tryRelease method
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 codeDetermines whether the current thread is the exclusive thread of the lock and throws an exception if it is not. So when we use ReentrantLock, we must successfully lock it before we can execute unlock. If the result of state-Releases is 0, the lock is successfully released, the exclusive thread of the current lock is cleared, and the status is reset to 0. We have to be careful here, as many times as we lock, we release.
Go back to the sync. release method and, after successful release, if the head node H is not equal to nothing and the wait state of the head node H is not 0, call the unparksucceeded method (from the above analysis, the state of the heads is -1, indicating that the successors of the heads are in the wait state)
// node= head h
private void unparkSuccessor(Node node) {
// node=head
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
// s=Node A
Node s = node.next;
if (s == null || s.waitStatus > 0) {
// Thread A waits for timeout or is interrupted by another thread, waitStatus > 0, and thread B needs to wake up
s = null;
// tail=Node B
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 codeThe state of the head Node h is equal to SIGNAL(-1), the CAS sets the state of the head Node to 0, the Node S (pointing to the Node corresponding to thread A) is not null, and the Node S is in the initial state (0), and does not enter the if condition, and the thread A is awakened through locksupport. unpark
If thread A waits to timeout or is interrupted
If the state of Node S is greater than zero (i.e., thread A waits for timeout or is interrupted), the for loop is executed and tail points to the Node corresponding to thread B.
- For the first loop, t=tail, t refers to Node B, and the waiting state of Node B is determined. Node B is the initial state (0), t is assigned to S, and S refers to Node B
- For the second loop, t=Node A (t = t.rev), Node A is interrupted due to timeout, so waitStatus equals 1, if (t.waitStatus <= 0) is not established
- The third loop, t=head (t= t. rev), for loop condition is not true, end the loop
At this point, s points to Node B and continues to wake up thread B with locksupport. unpark.
2.3 Fair lock and Unfair Lock
The ReentrantLock constructor allows you to specify the type of lock, i.e., unfair lock and fair lock. The default is unfair lock.
What are unfair locks and fair locks?
- Unfair locking: The order in which a thread acquires a lock is independent of the order in which it is locked, which is better performance, but can lead to “starvation”, which means that the thread never acquires a lock
- Fair lock: The thread that tries to lock first gets the lock first, preventing thread hunger
The above has completed the source analysis of the unfair lock, next continue to trace the source code to see how to implement the fair lock.
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
Copy the codeInside the ReentrantLock class are three inner classes, Sync, NonfairSync, and FairSync. Sync is an abstract class. NonfairSync and FairSync both inherit from Sync and correspond to the implementation of unfair and fair locks, respectively.
Let’s look at NonfairSync, the difference between an unfair lock and a fair lock
final void lock(a) {
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
Copy the codeFairSync
final void lock(a) {
acquire(1);
}
Copy the codeIf the current lock is idle, the current thread can directly obtain the lock. A fair lock calls the acquire method directly. If the current lock is already occupied, the acquire method is called for both unfair and fair locks.
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeTryAcquire requires an AQS subclass implementation to continue tracking NonfairSync and FairSync’s implementation NonfairSync
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);
}
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
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 codeFairSync
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
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 codeAs you can see, an unfair lock tries to add the lock again, while for a fair lock, hasqueued24 is first called to check whether a waiting thread exists on the queue
public final boolean hasQueuedPredecessors(a) {
Node t = tail;
Node h = head;
Node s;
returnh ! = t && ((s = h.next) ==null|| s.thread ! = Thread.currentThread()); }Copy the codeIf there are already waiting threads in the synchronization queue, the lock is not attempted and false is returned to acquire method
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeWhen tryAcquire fails to acquire the lock, wrap the current thread as a Node object and add it to the end of the synchronization queue. Fair lock is, therefore, in the order into the synchronous queue for lock, rather than a fair lock is not according to the order of entrance, the next node of the sentinel node is awakened, may at the same time there are other thread preemption locks, together with the current thread synchronization in the queue queue thread to be awakened, still need to compete with other not enter the thread of the queue.