The introduction
There used to be a classic interview question, “Can you tell me what common Java classes are?” Most people can name CountDownLatch, CyclicBarrier, and Sempahore. The three weapons by AbstractQueuedSynchronizer abstract class (abbreviated below AQS), so learning the three tool it is necessary for us to learn before AQS.
AQS is a simple framework that provides atomically managing synchronization state, blocking and waking up thread capabilities, and a queue model
AQS structure
Speaking of synchronization how do we guarantee synchronization? Well, Synchronized is probably the first thing you think of as Synchronized. Synchronized is basically used by the JVM, so we can simply add the keyword Synchronized. It’s super easy to use. However, there is no case where Synchronized cannot be achieved by setting a lock timeout time. In this case, we can use ReentrantLock to achieve ReentrantLock. ReentrantLock is implemented by AQS.
CAS && Fair and unfair locks
AQS uses a large number of CAS before learning AQS, it is necessary to simply understand CAS, fair locks and unfair locks.
CAS
- CASCompare and swap is a mechanism for implementing synchronization in multi-threaded environments.
CASThe operation contains three operands — the memory location, the expected value, and the new value.CASThe implementation logic is to compare the value at the memory location with the expected value, if the value is equal, then the value at the memory location is replaced with the new value. If it’s not equal, it doesn’t do anything, and this operation is atomic, in JavaAtomicIntegerAnd other classes are implemented through CAS.
Fair locks and unfair locks
- Fair lock: multiple threads acquire locks in the same order as they apply for locks. The thread directly enters the queue to queue, and the first thread in the queue gets the lock.
Advantages: The thread waiting for the lock will not starve, each thread can acquire the lock. Disadvantages: The overall throughput efficiency is lower than that of an unfair lock, all threads in the waiting queue except the first thread will block, and the CPU cost of waking up a blocked thread is higher than that of an unfair lock.
- Unfair lock: When multiple threads try to obtain the lock, they will directly try to obtain it. If they fail to obtain the lock, they will enter the waiting queue. If they can obtain the lock, they will directly obtain the lock.
Advantages: can reduce the CPU wake up thread overhead, the overall throughput efficiency will be higher, CPU does not have to wake up all threads, will reduce the number of wake up threads. Cons: Threads in a waiting queue may starve to death or wait too long to acquire a lock. It’s a bit of a mouthful, so let’s do an actual example. For example, when we go to the canteen to have dinner, we all queue up for dinner in the order of first come first served, which is fair lock. If wait until you’re ready to take plate rice from time to time Jumping out of the five big three thick fat man cut in line in front of you, you see a dozen don’t win him whimper to jump the queue, such as the fat man finished meal comes a little also to your team, you can’t bear, a loud roar directly let him roll, this little fart dian fart to only the line to line up the lock is fair. Let’s start by looking at the properties of AQS
/ / head node
private transient volatile Node head;
// Block the tail node. Each new node comes in and is inserted at the end, forming a linked list
private transient volatile Node tail;
// This is the most important, representing the current lock status. 0 indicates that the lock is not occupied, and greater than 0 indicates that some thread holds the current lock
// This value can be greater than 1 because the lock can be reentrant, adding 1 each time
private volatile int state;
// represents the thread currently holding the exclusive lock. The most important use example is because locks can be reentrant
// reentrantLock.lock() can be nested multiple times, so use this each time to determine if the current thread already has the lock
// if (currentThread == getExclusiveOwnerThread()) {state++}
private transient Thread exclusiveOwnerThread; / / since the AbstractOwnableSynchronizer inheritance
Copy the codeLet’s write a demo to analyze the process of locking and releasing locks
final void lock(a) {
// Try setting the state to 1, if no one can get the lock
if (compareAndSetState(0.1))
// If the race succeeds, modify the thread that acquired the lock state
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
Copy the codeThe CAS attempt failed, indicating that someone else already holds the lock, so enter the acquire method
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeTryAcquire method, you can probably guess what it means by the name, just try it. TryAcquire actually calls the nonfairTryAcquire method of Sync, the parent class
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
// Get the current lock status
int c = getState();
// This is the same if logic as before
if (c == 0) {
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true; }}// If the lock is reentrant, +1 is required
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
// If the number of lock reentrant times is greater than the maximum value of int, an exception will be thrown directly. Normally this should not be the case, but the JDK is careful
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
If false is returned, the lock has failed and the acquireQueued method should be used
return false;
}
Copy the codetryAcquireMethod if it fails to acquire the lock, it must queue up to acquire the lock. Where do queued threads need to wait to acquire locks? The thread pool encapsulates tasks as a work, and when the thread fails to process the task, it puts it on a queue. AQS similarly encapsulates the threads queuing to acquire locks into a NODE. The NODE is then placed in a queue. The queue is shown below, but it is important to note that heads do not store nodes.
Let’s look at the source code and see how lock acquisition failures are enqueued. To execute the acquireQueued method, execute the addWaiter method before executing the acquireQueued method
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;
// Cas joins the end of the queue
if (compareAndSetTail(pred, node)) {
pred.next = node;
returnnode; }}/ / end node is not null | | cas join end node failure
enq(node);
return node;
}
Copy the codeenq
Now look at the ENQ method
// Make sure the current node joins the back of the queue through spin and CAS
private Node enq(final Node node) {
for (;;) {
Node t = tail;
// If the end node is empty, the queue is still empty and has not been initialized yet, so if you initialize the head node, you can see that the node of the head node is not thread bound
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 codeThe thread acquiring the lock has been added to the column by encapsulating it as a NODE using the addWaiter method. An execution flow diagram of the above method is as follows:
acquireQueued
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
// Attempt to obtain the lock by spinning the precursor node ==head, which was analyzed earlier.
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
// Entering this if indicates that the node precursor is not equal to head or that the attempt to acquire the lock failed
// Determine whether the current thread needs to be suspended
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true; }}finally {
CancelAcquire (Throwable e){cancelAcquire(node); } Simple and clear
if(failed) cancelAcquire(node); }}Copy the codesetHead
This method sets the current node as the head node whenever a node acquires the lock. This method can simply be used to “remove” the current node from the queue when the current node acquires the lock.
shouldParkAfterFailedAcquire
In the source code, we can see that there are four states in total
- CANCELLED: if the value is 1, the thread waiting in the synchronization queue shall wait for timeout or be interrupted, and the Node of the Node shall be CANCELLED from the synchronization queue. Its waitStatus shall be CANCELLED, that is, the Node will not change after entering the status.
- SIGNAL: a value of -1, identified as the wake-up state of the successor, which is notified to execute when its predecessor’s thread releases the synchronization lock or is cancelled. As soon as the predecessor releases the lock, the thread of the successor identified as SIGNAL is notified to execute it.
- CONDITION: The value -2 is associated with Condition. The node is in the wait queue, and the thread of the node is waiting on Condition. When other threads call Condition’s signal() method, the node in Condition state will be transferred from the wait queue to the synchronization queue, waiting for the synchronization lock.
- PROPAGATE: the value is -3, which is related to the sharing mode, in which the state indicates that the thread of the node is in a runnable state.
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
Return true if the state is -1 to suspend the current thread
if (ws == Node.SIGNAL)
return true;
// If greater than 0, the state is CANCELLED
if (ws > 0) {
do {
// Delete the cancelled node (make the cancelled node an unreferenced node to be collected by the next GC)
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
// Enter here only 0, -2, -3. The NODE NODE is initialized with a default waitStatus value of 0, so this is the only place to change waitStatus
// Set the state of the precursor node to -1 via cas, and return false
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
Copy the codeparkAndCheckInterrupt
Suspends the current thread and blocks
private final boolean parkAndCheckInterrupt(a) {
LockSupport.park(this); // Suspends the current thread and blocks
return Thread.interrupted();
}
Copy the code
unlock
Succeeded in the forerunner of the locks, the locks must be released when they have run out. It would be good to concentrate on the unparksucceeded method in forerunning the locks
private void unparkSuccessor(Node node) {
// The state of the header
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
Node s = node.next;
// s==null after the succeeded in obtaining the lock of the head, the unlocking thread read the head. Next =null, so s==null
// The following operations were performed when the head's succeeded node was cancelled: forgo.waitstatus =1; successor.next = successor;
if (s == null || s.waitStatus > 0) {
s = null;
// Start with the last node and move forward to find the first non-cancelled node
for(Node t = tail; t ! =null&& t ! = node; t = t.prev)if (t.waitStatus <= 0)
s = t;
}
if(s ! =null)
// Wake up the thread, which acquires the lock from the acquireQueued
LockSupport.unpark(s.thread);
}
Copy the codeRelease lock code is relatively simple, basically written in the code comments, the process is as follows:
- node.prev = pred; CompareAndSetTail (pred, node) these two places can be considered as Tail enqueue atomic operations, but pred. Next = node; Not yet. If the unparksucceeded method had been carried out at this time there would have been no way of looking forward, so one had to go from the back to the front.
- When the CANCELLED Node is generated, the Next pointer is disconnected first, while the Prev pointer is not. Therefore, the whole Node must be traversed from back to front
conclusion
- ReentrantLock to obtain and release the lock basic on the end, which also involves more details, interested students can try to debug the source line by line.
- Only with a proper understanding of AQS can we learn CountDownLatch, CyclicBarrier and Sempahore better, because these three tools are realized based on AQS.
The end of the
- As a result of their talent and learning, it is inevitable that there will be mistakes, if you found the wrong place, but also hope that the message to me pointed out, I will correct it.
- If you think the article is good, your forwarding, sharing, appreciation, like, message is the biggest encouragement to me.
- Thank you for reading. Welcome and thank you for your attention.
Standing on the shoulders of giants pick apples: tech.meituan.com/2019/12/05/… Javadoop.com/post/Abstra… www.cnblogs.com/yanlong300/…