preface
While we may often use synchronization tools like ReentrantLock, Semaphore, and CountDwonLatch to keep threads safe in Java concurrent programming, we may not know exactly how. This article through parsing the mutual depend on their class AbstractQueuedSynchronizer to explore how to realize the control of the resources they are. For the sake of analysis, this article focuses on ReentrantLock as a starting point, and you can analyze the implementation logic of other implementation classes by yourself after reading this article.
case
First, let’s review a use case for ReentrantLock:
public class Bootstrap {
private static final Lock lock = new ReentrantLock();
private int count = 0;
public void count() { try { lock.lock(); count++; } finally { lock.unlock(); }}}Copy the codeThis demo is very simple, just counting count, and using ReentrantLock to ensure data security in a multi-threaded environment.
Source code analysis
Initialize the
The above code starts by creating a Lock object through the ReentrantLock constructor, so let’s see which objects are actually created.
public ReentrantLock() {
sync = new NonfairSync();
}
Copy the codeNew ReentrantLock(true); ReentrantLock(true); ReentrantLock(true); ReentrantLock(true);
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
Copy the codeNow that we know the two ways to create locks, let’s look at the differences between the two types of locks:
Fair lock implementation part of the source:
static final class FairSync extends Sync {
private static final long serialVersionUID = -3000897897090466540L;
final void lock() { acquire(1); }... }Copy the codeNon-fair lock implementation part of the source code:
static final class NonfairSync extends Sync {
private static final long serialVersionUID = 7316153563782823691L;
final void lock() {
if (compareAndSetState(0, 1))
setExclusiveOwnerThread(Thread.currentThread());
elseacquire(1); }... }Copy the codeYou can see that there is a judgment condition for an unfair lock. For now, I will tell you that the condition is to let the current thread try to acquire the lock, and if it succeeds, it will directly set it to exclusive lock mode. This also demonstrates the unfair principle of directly trying to acquire the lock, failed and then wait like any other thread.
Since the logic of NonfairSync includes FairSync, let’s proceed from NonfairSync and take a look at the NonfairSync inheritance diagram:
As you can see, the core class Sync inherits from AQS, and both NonfairSync and FairSync inherit from Sync. This set of inheritance mechanisms implements ReentrantLock locking and lock release logic. As can be seen from this, AQS does not have specific implementation logic, it only specifies the mechanism to manage thread waiting and lock acquisition (which is the focus of the next section). ReentrantLock (similar to other implementation classes such as Semaphore) implements the logic of when the lock should be acquired and released.
AQS source code analysis
Before explaining AQS, let me use a diagram to illustrate how it works.
When a Thread fails to acquire a lock, AQS encapsulates the Thread into a Node through its internal Node class, and adds the Node to the queue in the form of a bidirectional linked list while waiting for the lock. (CLH queue is a variant of CLH queue here.
Let’s explore the full workings of NonfairSync from the beginning:
compareAndSetState
When the lock.lock() method is called in the case, it enters the lock() method of NonfairSync. The first step is to obtain the lock by compareAndSetState(0, 1). Let’s look at the code:
In the AQS class:
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 codeThe Unsafe class iterates memory directly and implements CAS to update the state value, which is a volatile integer of the AQS, indicating that the lock is not in use if it is 0 and that the lock is in use if it is 1. So an unfair lock first calls this method to get the lock and see if it succeeds. If it succeeds, setExclusiveOwnerThread(thread.currentThread ()) is called; Method, let’s look at the code for this method again
setExclusiveOwnerThread
protected final void setExclusiveOwnerThread(Thread thread) {
exclusiveOwnerThread = thread;
}
Copy the codeThis method exists in the AbstractOwnableSynchronizer class, through the inheritance diagram above can see that it is the parent class of AQS. This method sets the ‘exclusiveOwnerThread’ to the specified thread, indicating that the thread is holding the lock. The first condition over here is done, which means that if you can get the lock directly, then the current thread is locked, and the process is done.
acquire
Acquire (1); acquire(1); acquire(1);
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeAs we can see, there are two main conditions involved, and we will explain them one by one:
tryAcquire
This method is not specifically implemented in AQS, which is also the method we need to customize to achieve AQS. The corresponding implementation of NonfairSync is as follows:
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
#1 int c = getState();
#2 if (c == 0) {
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true; }}#3 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 codeHere, I will explain the main steps after numbering them:
Get the current thread object, and then get the current lock state (#1) via getState(). If the status is 0, the lock has not been occupied yet, try to acquire the lock directly (this step is actually what the first condition does), with success set the current thread to exclusive lock mode (#2); If the current thread is already in exclusive lock mode, it does not need to acquire the lock again. If the current thread is already in exclusive lock mode, it does not need to acquire the lock again. Return false if none of the above conditions are met.
acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
The addWaiter(Node.exclusive) method is used to queue a thread to wait if the lock is not obtained directly.
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 codeThread is wrapped in the Node initialization method and the Node type is set to EXCLUSIVE. There are concepts of head nodes and tail nodes for the entire list, which refer to the head and tail of the list, respectively. If tail is not empty, point the node’s prev to that node and point the new tail node to the node. If it fails, enq(node) will be executed to re-join the team. The specific implementation of ENQ method is as follows:
private Node enq(final Node node) {
for (;;) {
Node t = tail;
#1 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 the tail node is empty, it will initialize an empty node and point both tail and head nodes to it (#1). If tail exists, set the node at the end of the list as above. Node enqueue relies on the old tail node. The new tail node is set by the front node of the new node.
acquireQueued
After enqueueing, we need to further explore how Node acquires locks in queues. Let’s take a look at the acquireQueued method in action:
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();
#1 if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
#2 if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if(failed) cancelAcquire(node); }}Copy the codeFirst of all, we need to know the two attributes: failed indicates whether the lock fails to be acquired, and interupted indicates whether the thread has been interrupted. In addition, this method is a spin operation and consists of two steps: check whether the current node’s precursor node is a head node. If so, try again to obtain the lock, set the new head node to the current node and return to interrupted. (#1) If the precursor node of the current node is not a head node or fails to acquire the lock, then it is necessary to determine whether to block the current thread. Here involves two shouldParkAfterFailedAcquire judgment conditions and parkAndCheckInterrupt (), in turn explain below:
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
#1 if (ws == Node.SIGNAL)
/*
* This node has already set status asking a release
* to signal it, so it can safely park.
*/
return true;
#2 if (ws > 0) {
/*
* Predecessor was cancelled. Skip over predecessors and
* indicate retry.
*/
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
#3 } else {/ * *waitStatus must be 0 or PROPAGATE. 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 codeIf waitStatus is SIGNAL, return true(#1); If waitStatus is greater than 0, it indicates that the precursor node is in cancelled state. Then, directly fetch the previous node to know that the precursor node’s waiteStatus is not greater than 0(#2). If waitStatus is 0 or 3, set the precursor node’s waitStatus to SIGNAL(#3) directly. This is used to determine whether the thread on the current node needs to block.
If true then parkAndCheckInterrupt is called to block. Let’s look at the implementation:
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
Copy the codeThe park method of the LockSupport class is used to block threads. This also relies on the Unsafe method, which directly handles the permit license of the specific thread to determine whether to block 1. Finally, the thread’s blocking flag is returned.
Finally we go back to the acquire method, the thread blocked, and we need to do selfInterrupt which is a response to the interrupt mechanism. Note that if the lockInterruptibly method is used, the blocking operation is different, The above sets interrupted to true, but the lockInterruptibly method throws new InterruptedException(); The operation is broken, and the lock is unlocked in finally.
conclusion
To conclude, the implementation of ReentrantLock is AQS dependent, and the ReentrantLock layer simply overwrites the logical code that acquires the lock. In addition, AQS stores Node nodes containing Thread information through a bidirectional queue, and represents the lock acquisition state through the state variable. The thread sets the lock state through CAS, and decides whether to acquire the lock or block the thread by waiting information of the node. I believe that through this article we also have an intuitive understanding of the realization principle of AQS
reference
- [1] JDK 8 source code
- [2] See the principle and application of AQS from the implementation of ReentrantLock
- [3] LockSupport principle analysis
Reprint please indicate the source!