- Start with the acquire method — get
- Why does AQS need a virtual head node
- How does the Reelase method release the lock
- conclusion
preface
AQS is the core of JUC, which encapsulates the acquisition and release of resources. In our previous AQS source code anatomy article on concurrent programming, we analyzed lock acquisition and release from ReentranLock. But I need to explain the core CLH locks of AQS again.
Here’s a quote from someone else’s explanation of CLH:
CLH CLH(Craig, Landin, and Hagersten Locks): A spin lock that ensures no hunger and provides first-come-first-served fairness.
CLH locks are also scalable, high-performance, and fair spinlocks based on linked lists. The requisition thread spins only on local variables. It constantly polls the state of the precursor and ends the spin if it finds that the precursor has released the lock.
The Design of Java AQS is an optimization or variant of CLH locking.
Let’s start with the code.
1. Start with the acquire method — get
The acquire method is a common way to acquire locks. The code is as follows:
public final void acquireQueued(int arg) {
// If tryAcquire returns true, the lock has been acquired.
// If false is returned, the latter method needs to be executed.
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeAs long as the subclass’s tryAcquire method returns false, it is necessary to enqueue itself to acquire the lock event.
private Node addWaiter(Node mode) {
// Create an exclusive node
Node node = new Node(Thread.currentThread(), mode);
// Try the fast path of enq; backup to full enq on failure
Node pred = tail;
// If the tail node is not null, set the pred node of the new node to the tail node.
// And set the new node to the tail node.
if(pred ! =null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
returnnode; }}// If the tail node is null, or the CAS fails to set tail.
// in the enq method
enq(node);
return node;
}
Copy the codeAdd yourself to the tail and update the tail node.
private Node enq(final Node node) {
for (;;) {
Node t = tail;
// If tail is null, a virtual node is created that points to both head and tail. This is called initialization.
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {// If not null
// As in the previous method, append the new node to the tail node and update the tail of the queue to the new node.
// If you fail, you can try again.
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
returnt; }}}}Copy the codeWhat is the logic of the ENQ method? When tail is null (the queue is not initialized), the queue needs to be initialized. If the CAS fails to set tail, this is also used. You need to loop tail in the ENQ method. Until you succeed.
Note: A virtual node is created here.
2. Why does AQS need a virtual head node
Why create a virtual node?
It all starts with the Node class waitStatus variable, or WS. Each node has a WS variable that is used for some indication of the node’s state. The initial state is 0. If it’s canceled, the node is 1, and it gets cleaned up by AQS.
There is another important state: SIGNAL — 1, which means that when the current node releases the lock, the next node needs to wake up.
All nodes need to set WS to SIGNAL on the front node before they hibernate. Otherwise they will never be awakened.
Why do you need such a WS? — Prevent repeated operations. Suppose, when a node has been released, another thread does not know that it has been released again. This is a mistake.
Therefore, a variable is required to guarantee the state of this node. To modify this node, CAS operations must be performed to ensure thread-safety.
So, back to our earlier question: why create a virtual node?
Each node must set the front-node’s WS state to SIGNAL, so there must be a front-node, and this front-node is, in effect, the node that currently holds the lock.
The problem is that there is a boundary problem: what about ** the first node? ** It has no front nodes.
So create a fake one.
That’s why you want to create a virtual node.
To sum up: each node needs to set the WS state of the front node (this state is to ensure data consistency), and the first node does not have the front node, so it needs to create a virtual node.
Go back to our acquireQueued method and verify:
// The returned node is the newly created node, and arg is the number of requests
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
// Find the last node
final Node p = node.predecessor();
// If the previous node was head, try to acquire the lock
// If successful, set the current node to head, noting that the head node is never woken up.
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
// Block when the lock fails to be acquired.
/ / shouldParkAfterFailedAcquire - > check the state of a node, if the SIGNAL is blocked, otherwise it into a SIGNAL.
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true; }}finally {
if(failed) cancelAcquire(node); }}Copy the codeThere are two logic to this approach:
- How do I suspend myself?
- What do you do when you wake up?
First answer the second question: what do you do when you wake up?
Try to pick up the lock. Once successful, set yourself to HEAD and disconnect from next.
The second question is: How do YOU suspend yourself?
Note: Before suspending yourself, you need to set the ws state of the front node to SIGNAL and tell it to wake me up when you release the lock.
Specific logic in shouldParkAfterFailedAcquire approach:
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
// If the ws on his last node is SIGNAL, he needs to block.
if (ws == Node.SIGNAL)
/ / blocking
return true;
// The predecessor is cancelled. Skip the predecessor and try again.
if (ws > 0) {
do {
// Assign the value of the predecessor to the current predecessor
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
// Assign next of the predecessor to the current node
pred.next = node;
} else {
/ / if not cancel the | | 0 | | CONDITION | | the PROPAGATE, then set the former ws into SIGNAL.
// Why must it be SIGNAL?
// A: I want my last node to notify me when it releases the lock.
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
/ / again
return false;
}
Copy the codeThe main logic of this method is to change the state of the front node to SIGNAL. If the front node is cancelled, it is skipped.
Then it must wake up when the front node releases the lock. Look at the logic of release.
3. How does the reelase method release locks
First, a wave of code:
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
// All nodes set the front node to SIGNAL before suspending themselves, hoping to wake up when the front node is released.
// If the front node is 0, the front node has been released. The release cannot be repeated, as you will see later that ws is changed to 0 after the release.
if(h ! =null&& h.waitStatus ! =0)
unparkSuccessor(h);
return true;
}
return false;
}
Copy the codeFrom this method we can see that head must not equal 0. Why is that? When a node attempts to suspend itself, the leading node is set to signal-1. Even if the first node to join the queue fails to acquire the lock, the virtual node’s ws is set to SIGNAL.
This judgment also prevents multiple threads from being released repeatedly.
Then you must set the WS state to 0 after releasing the lock. Prevent repeated operations.
The code is as follows:
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
// set ws to 0 for head. Said he had been released. Cannot repeat release.
compareAndSetWaitStatus(node, ws, 0);
Node s = node.next;
// If next is null, or next is cancelled. Start at tail and work your way up to the node.
if (s == null || s.waitStatus > 0) {
s = null;
// Start at the tail and look forward for uncancelled nodes until the node is null, or head.
// If next of head is null, start from tail until head is not null.
// If next of head is not null, but cancelled, this node will also be skipped.
for(Node t = tail; t ! =null&& t ! = node; t = t.prev)if (t.waitStatus <= 0)
s = t;
}
// Wake up the head.next node.
// Usually this node is next to head.
// If head.next is cancelled, the search will start at the end.
if(s ! =null)
LockSupport.unpark(s.thread);
}
Copy the codeIf ws is less than 0, we assume SIGNAL, change to 0. It confirms what we thought.
If his next is null, it means that next is canceled, so start at the tail and look up. Of course, in the search process, also skipped the failed node.
Finally, wake him up.
What does the logic look like after wake up remember?
A refresher: Take the lock, set yourself to head, and disconnect your predecessor head from you.
4. To summarize
CLH locks used by AQS require a virtual head node to prevent repeated lock releases. When the first node to enter the queue has no front nodes, a virtual one is created.
Here’s a picture to try to explain AQS:
-
When a node is added
-
Update the tail
- When the node is awakened, the previous head is cancelled
