Analysis of the principle of ReentrantLock
Speaking of ReentrantLock, we all know that it is a reentrant mutex based on AQS (AbstractQueuedSynchronizer).
If we want to analyze ReentrantLock, we have to start with AbstractQueuedSynchronizer.
Analysis of AbstractQueuedSynchronizer
AbstractQueuedSynchronizer has an internal class Node, and the underlying layer maintains a doubly linked list to form a queue. That is our AQS queue. When we fail to acquire the lock, the thread will be put into this queue and wake up when waiting for other threads to release the lock.
The entire locking process of ReentrantLock revolves around the state attribute. When the state field is greater than 0, it means that the current resource is locked, and the value of the state represents the number of reentries of the thread currently holding the lock. When the state is 0, the threads in the queue can compete for it through a series of CAS operations this lock.
public abstract class AbstractQueuedSynchronizer extends AbstractOwnableSynchronizer implements java.io.Serializable {<!-- --> static final class Node {<!-- --> // wait state volatile int waitStatus; // previous node volatile Node prev; // next node volatile Node next; //current node thread volatile Thread thread; //head pointer private transient volatile Node head; // tail pointer private transient volatile Node tail; //reentry times private volatile int state; } }
Sync
Sync is the abstract internal class of ReentrantLock, which inherits AQS. The main function of ReentrantLock depends on this internal class Sync. He defines a generic template for acquiring and releasing locks. And defines the unfair acquisition lock method.
abstract static class Sync extends AbstractQueuedSynchronizer {<!-- --> private static final long serialVersionUID = -5179523762034025860L; //Unfair lock acquisition method 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; } }
Sync has two sons, NoFairSync (unfair lock) and FairSync (fair lock). The main function of ReentrantLock is realized through these two implementation classes.
NoFairSync (unfair lock)
Acquiring lock process
-
Try to use CAS to lock
final void lock() {<!-- --> //Try to use CAS to lock if (compareAndSetState(0, 1)) //The lock is successful, and the current resource lock thread is set as the current thread setExclusiveOwnerThread(Thread. currentThread()); else //Failed to lock, follow the lock process defined by the parent class Sync acquire(1); }
-
If the CAS lock fails, follow the lock process defined by Sync
public final void acquire(int arg) {<!-- --> // try to lock if (!tryAcquire(arg) & amp; & amp; //Failed to lock, put the current thread at the end of the AQS queue //And judge whether the current thread is ranked first in the AQS queue, if so, try to acquire the lock again, if not, find the previous available thread, and suspend the current thread acquireQueued(addWaiter(Node. EXCLUSIVE), arg)) selfInterrupt(); }
-
tryAcquire is unfairly locked, using the nonfairTryAcquire() method defined by the parent class Sync
protected final boolean tryAcquire(int acquires) {<!-- --> //nonfairTryAcquire() defined by the parent class Sync return nonfairTryAcquire(acquires); } protected final boolean nonfairTryAcquire(int acquires) {<!-- --> // get the current thread final Thread current = Thread. currentThread(); // get state value int c = getState(); //If the state is 0, it means it can be locked if (c == 0) {<!-- --> //Use CAS to set state from 0 to 1 if (compareAndSetState(0, acquires)) {<!-- --> //If the CAS lock is successful, set the thread holding the lock resource as the current thread setExclusiveOwnerThread(current); //return lock successfully return true; } } //If the lock fails, determine whether the thread holding the lock resource is the current thread //If yes, start the lock reentry operation //If not, give up reentrancy else if (current == getExclusiveOwnerThread()) {<!-- --> //state + 1 int nextc = c + acquires; // Exceeded the reentry limit, throwing an exception if (nextc < 0) throw new Error("Maximum lock count exceeded"); //set state = state + 1 setState(nextc); //return lock successfully return true; } //Otherwise, return lock failure return false; }
-
addWaiter(Node.EXCLUSIVE) If the lock acquisition fails, add the current thread to the end of the AQS queue
//If the lock fails, add the current thread to the end of the AQS queue private Node addWaiter(Node mode) {<!-- --> Node node = new Node(Thread. currentThread(), mode); //Get AQS tail node Node pred = tail; if (pred != null) {<!-- --> // Point the previous node of the current thread to the original tail node.prev = pred; //Use the CAS method to point the pointer of the original tail node to the new thread just now if (compareAndSetTail(pred, node)) {<!-- --> pred.next = node; return node; } } //If using CAS to set the current thread to the end of AQS fails, execute this method enq(node); return node; } //Use an infinite loop until the current thread is successfully set to the end of the queue before jumping out of the loop private Node enq(final Node node) {<!-- --> for (;;) {<!-- --> // Get the tail pointer Node t = tail; //If the tail pointer is null, it proves that AQS is an empty queue and needs to be initialized if (t == null) {<!-- --> //Create a node and set it as the head pointer if (compareAndSetHead(new Node())) // tail pointer points to head pointer tail = head; } else {<!-- -->//If the tail pointer is not null, set the current thread to the end of the queue node.prev = t; if (compareAndSetTail(t, node)) {<!-- --> t.next = node; return t; } } } }
-
acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) Determine whether the current thread is in front of AQS, if so, try to acquire the lock again, if not, find the waiting thread in front of AQS, and suspend itself
//Judge whether the current thread is the first in the AQS queue //If so, re-acquire the lock //If not, suspend the current thread final boolean acquireQueued(final Node node, int arg) {<!-- --> //Acquiring lock failed flag boolean failed = true; try {<!-- --> //interrupt flag boolean interrupted = false; //Infinite loop: If the thread is the node in front of AQS, you can try to acquire the lock, if not, go from back to front until you find an active thread node, and then hang yourself for (;;) {<!-- --> // Get the previous node of the current thread final Node p = node. predecessor(); //If the previous node of the current thread is head, it proves that the current thread is at the head of AQS, and try to acquire the lock again if (p == head & amp; & amp; tryAcquire(arg)) {<!-- --> //Obtain the lock successfully, the next step... //Set the current thread as the head node setHead(node); //Release the object for garbage collection p.next = null; // help GC //Get the lock successfully failed = false; return interrupted; } //Failed to acquire the lock, determine whether it should be suspended if (shouldParkAfterFailedAcquire(p, node) & amp; & amp; // suspend the thread parkAndCheckInterrupt()) interrupted = true; } } finally {<!-- --> if (failed) cancelAcquire(node); } } / / Determine whether the current thread should be suspended private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {<!-- --> //Get the status of the previous node of the current thread int ws = pred.waitStatus; //If the previous thread is also in the waiting state, return true and the current thread can be suspended if (ws == Node. SIGNAL) return true; //If the previous thread is in the cancel state, then it has been traversing forward for a long time until the thread with the state less than 0 is obtained if (ws > 0) {<!-- --> do {<!-- --> node.prev = pred = pred.prev; } while (pred.waitStatus > 0); pred.next = node; } else {<!-- --> //Set the status of the found thread to wait (-1) compareAndSetWaitStatus(pred, ws, Node. SIGNAL); } return false; } \t //Call the park() method to suspend the thread private final boolean parkAndCheckInterrupt() {<!-- --> LockSupport. park(this); return Thread. interrupted(); }
FairSync (fair lock)
The difference between fair lock and unfair lock:
-
The unfair lock will use CAS to try to acquire the lock as soon as it enters the lock method, and the acquire() method will be called only when the lock fails to be acquired, while the fair lock directly calls the acquire() method
//Unfair lock final void lock() {<!-- --> //Use CAS once by default if (compareAndSetState(0, 1)) setExclusiveOwnerThread(Thread. currentThread()); else acquire(1); } // fair lock final void lock() {<!-- --> / / Directly call the common method of acquiring the lock acquire(1); }
-
Unfair lock does not judge whether there is queuing phenomenon in the AQS queue in the acquire() method of acquiring the lock. Regardless of whether the current thread exists in the AQS queue, it can compete for the lock. The fair lock will first call the hasQueuedPredecessors() method to check whether there is queuing in the queue. If there is queuing, the current thread will be stored at the end of the AQS queue, and then try to acquire the lock
//Unfair lock final boolean nonfairTryAcquire(int acquires) {<!-- --> final Thread current = Thread. currentThread(); int c = getState(); if (c == 0) {<!-- --> //The acquisition lock method does not judge whether there is a queuing phenomenon in the AQS queue, no matter whether the current thread exists in the AQS queue, it can compete for the lock 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; } // fair lock protected final boolean tryAcquire(int acquires) {<!-- --> final Thread current = Thread. currentThread(); int c = getState(); if (c == 0) {<!-- --> //First call the hasQueuedPredecessors() method to check whether there is a queue in the queue if (!hasQueuedPredecessors() & amp; & amp; 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; } }
Unlock process unlock()
Both fair lock and unfair lock unlocking use the same code, and both use the release() method of AQS to unlock.
public void unlock() {<!-- --> sync. release(1); }
release() process
public final boolean release(int arg) {<!-- --> //try to unlock if (tryRelease(arg)) {<!-- --> Node h = head; //Unlocking is successful, if the state of the head node !=0, it means that AQS still has queuing threads, and the subsequent threads need to be woken up if (h != null & amp; & amp; h.waitStatus != 0) //Find the thread closest to the head node from back to front to wake up and prepare to grab the lock unparkSuccessor(h); return true; } return false; }
-
Release the lock tryRelease()
//Try to release the lock protected final boolean tryRelease(int releases) {<!-- --> //state-1 int c = getState() - releases; //If the current thread != holds the lock thread, an exception is thrown if (Thread. currentThread() != getExclusiveOwnerThread()) throw new IllegalMonitorStateException(); //Release resources successful mark falg boolean free = false; //c == 0 means state == 0 means releasing resources successfully if (c == 0) {<!-- --> free = true; //The thread holding the lock is set to null setExclusiveOwnerThread(null); } //state = state - 1 wait for next reentry -1 setState(c); return free; }
-
The lock is successfully released and wakes up other waiting threads in AQS
private void unparkSuccessor(Node node) {<!-- --> // Get the state of the head node int ws = node.waitStatus; //If the head node state > 0 then set the state of the head node to 0 if (ws < 0) compareAndSetWaitStatus(node, ws, 0); //Get the next node of the head node Node s = node. next; //Find the thread closest to the head node to wake up //If the state of the next node > 0, it means that the next thread has given up acquiring the lock if (s == null || s.waitStatus > 0) {<!-- --> s = null; //Search from the back to the front of the AQS to find the thread closest to the head node for (Node t = tail; t != null & amp; & amp; t != node; t = t.prev) if (t. waitStatus <= 0) s = t; } // perform wakeup operation if (s != null) LockSupport. unpark(s. thread); }