ReentrantLock Analysis
1. ReentrantLock is a reentrant mutex lock. Its performance is similar to that of synchronized after JDK1.6. The latter locks hermits, and introduces the concept of lock upgrade in JDK1.6, which is upgraded from a biased lock to a lightweight lock. Finally, it is upgraded to a heavyweight lock and cannot be downgraded
2. Synchronized is implemented at the JVM level. C++ codes, such as weight locks, are based on ObjectMoniter and support unfairness. ReentrantLock is implemented based on AQS. These implementation logics are all in sync. ReentrantLock itself implements the Lock interface, supports fair and unfair modes, and is set by the parameter fair in the construction method
3. ReentrantLock does not implement additional ConditionObject, and directly uses AQS
Article directory
- ReentrantLock Analysis
- foreword
- 1. Analyze the locking process
-
- 1. Analyze the lock method
- 2. Analyze the acquire method
- 3. Analyze the tryAcquire method
- 4. Analyze the tryLock method
- 2. Analyze the lock release process
-
- 1. Analyze the unlock method
- Summarize
Foreword
1. state is a built-in volatile variable in CAS. When it is 0, no thread acquires the lock resource
2. The default is unfair lock, and the external thread and the awakened thread in the AQS synchronization queue all seize the lock. Fair locks are queued to acquire lock resources from the queue
3. The built-in synchronization queue of AQS is a doubly linked list. ConditionObject is a one-way linked list
4. A lot of core logic ReentrantLock is not rewritten, and AQS is used directly
The following is the text of this article, the following case is for reference only
1. Analyze the locking process
1, analyze the lock method
public void lock() {<!-- -->
// There are fair implementations (FairSync) and non-fair implementations (NonFairSync)
sync. lock();
}
// unfair implementation
final void lock() {<!-- -->
// Using CAS, modify the state from 0 to 1
if (compareAndSetState(0, 1))
// After obtaining the lock resource, assign the current thread to the exclusiveOwnerThread variable (indicating who has obtained the lock resource)
setExclusiveOwnerThread(Thread. currentThread());
else
// Failed to acquire the lock, execute acquire to acquire the lock
acquire(1);
}
// fair implementation
final void lock() {<!-- -->
// Acquire the lock, if the acquisition fails, enter the tail of the AQS synchronization queue
acquire(1);
}
The process of acquiring the lock is the process of CAS state, and a variable is set to save which thread currently holds the lock resource.
After the unfair lock fails to acquire the lock, the acquire method will be called to continue to acquire the lock, and the fair lock will directly call the acquire method to acquire the lock
2, analyze the acquire method
Both fair locks and unfair locks call this method
public final void acquire(int arg) {<!-- -->
// try to acquire the lock resource
if (!tryAcquire(arg) & amp; & amp;
// Still haven't got the lock resource
// addWaiter: wrap the current into a Node, and append the tail of the AQS synchronization queue (EXCLUSIVE means exclusive mode)
// acquireQueued: If the current node is the head, try to acquire the lock again, if you still can't get it, the thread will be suspended (WAITING)
acquireQueued(addWaiter(Node. EXCLUSIVE), arg))
// Thread.currentThread().interrupt() sets the interrupt flag (just set, not necessarily terminated)
selfInterrupt();
}
// Add threads that have not acquired the lock to the end of the queue
private Node addWaiter(Node mode) {<!-- -->
// Encapsulate the current thread into a Node
Node node = new Node(Thread. currentThread(), mode);
// The tail node tail is the pred of the current node
Node pred = tail;
// If the tail node is not null, it means that the queue already has a queued Node
if (pred != null) {<!-- -->
node.prev = pred;
// Set the current node as the tail node (append at the end)
if (compareAndSetTail(pred, node)) {<!-- -->
pred.next = node;
return node;
}
}
// The tail node is empty or compareAndSetTail CAS fails, execute in an endless loop here
// If tail is null, execute compareAndSetHead in an endless loop
// Conversely, execute compareAndSetTail in an infinite loop
enq(node);
return node;
}
// After tryAcquire fails to acquire the lock, put the thread at the end of the queue, and then execute this method
final boolean acquireQueued(final Node node, int arg) {<!-- -->
// Whether the lock acquisition failed
boolean failed = true;
try {<!-- -->
boolean interrupted = false;
// infinite loop
for (;;) {<!-- -->
// Get the previous node of the current node, if not, throw an exception
final Node p = node. predecessor();
// If the previous node is head, try to acquire the lock again
// The thread inside the head is empty, which is a pseudo node, so the current node here is the first thread waiting to acquire the lock resource
if (p == head & amp; & amp; tryAcquire(arg)) {<!-- -->
// Acquire the lock resource successfully, point the current node to the head, and notify the empty internal thread and pre
// Equivalent to taking the original head out of the queue and waiting to be recycled
setHead(node);
p.next = null; // help GC
// Acquiring the lock did not fail
failed = false;
// exit
return interrupted;
}
// The current node is not the second node || Failed to acquire the lock again
// Determine whether the current thread can be suspended (LockSupport.park(this), enter WAITING)
if (shouldParkAfterFailedAcquire(p, node) & amp; & amp;
// Execute LockSupport.park(this), suspend the thread
parkAndCheckInterrupt())
interrupted = true;
}
} finally {<!-- -->
if (failed)
// Cancel the processing of the node
cancelAcquire(node);
}
}
// Determine whether the node node can be suspended
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {<!-- -->
int ws = pred.waitStatus;
// If the status of the previous node is -1, the node is still in the queue
if (ws == Node. SIGNAL)
return true;
// If the last node status is 1 (equivalent to the node being canceled, such a node is invalid and will be removed from the queue)
if (ws > 0) {<!-- -->
do {<!-- -->
// The previous of the current node = the previous of the previous node, which is equivalent to the pointer bypassing the middle node
node.prev = pred = pred.prev;
// Loop until a valid pre node is found (status is not 1)
} while (pred.waitStatus > 0);
pred.next = node;
} else {<!-- -->
// The node status is not -1 or 1, set the pred node status to -1
compareAndSetWaitStatus(pred, ws, Node. SIGNAL);
}
// cannot suspend
return false;
}
3, analyze the tryAcquire method
Fair implementation and unfair implementation methods are different, but the general logic is similar. Fairness is just an additional check for fair acquisition of locks.
// unfair implementation
final boolean nonfairTryAcquire(int acquires) {<!-- -->
// Get the current thread
final Thread current = Thread. currentThread();
// Get the current lock state
int c = getState();
// The lock status is 0, indicating that it is not occupied and may have been released by other threads
if (c == 0) {<!-- -->
// CAS status, acquire lock
if (compareAndSetState(0, acquires)) {<!-- -->
// Acquiring the lock is complete, set ExclusiveOwnerThread
setExclusiveOwnerThread(current);
return true;
}
}
// The lock is occupied, determine whether it is occupied by the current thread (ReentrantLock is a reentrant lock)
else if (current == getExclusiveOwnerThread()) {<!-- -->
// Increase the number of lock reentries
int nextc = c + acquires;
// The number of reentries cannot exceed the boundary of int
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
// set lock state
setState(nextc);
return true;
}
return false;
}
// fair implementation
protected final boolean tryAcquire(int acquires) {<!-- -->
// Get the current thread
final Thread current = Thread. currentThread();
// Get the current lock state
int c = getState();
// The lock status is 0, indicating that it is not occupied and may have been released by other threads
if (c == 0) {<!-- -->
// Judging whether there is a thread in front of the current thread inside, if not, the lock will be acquired
if (!hasQueuedPredecessors() & amp; & amp;
// acquire the lock
compareAndSetState(0, acquires)) {<!-- -->
// acquire the lock successfully
setExclusiveOwnerThread(current);
return true;
}
} else if (current == getExclusiveOwnerThread()) {<!-- -->
// Increase the number of lock reentries
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
// Fair lock: judge whether the current thread can acquire the lock, return false to indicate that there is no thread queued in front
public final boolean hasQueuedPredecessors() {<!-- -->
// tail node
Node t = tail;
// head node
Node h = head;
// the next node of the head node
Node s;
// head ! = tail
return h != t & amp; & amp;
// The next node of the head is not null || The next node of the head is not the current thread (indicating that there is a queue in front)
((s = h.next) == null || s.thread != Thread.currentThread());
}
4, analyze the tryLock method
Basically consistent with the above logic
public boolean tryLock() {<!-- -->
// Does not distinguish between fair mode and unfair mode, it will follow unfair logic
return sync. nonfairTryAcquire(1);
}
// acquire lock in unfair mode
final boolean nonfairTryAcquire(int acquires) {<!-- -->
final Thread current = Thread. currentThread();
int c = getState();
// The lock is not occupied, CAS acquires the lock
if (c == 0) {<!-- -->
if (compareAndSetState(0, acquires)) {<!-- -->
setExclusiveOwnerThread(current);
return true;
}
}
// lock reentry
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;
}
// wait for the time to acquire the lock
public boolean tryLock(long timeout, TimeUnit unit)
throws InterruptedException {<!-- -->
// Convert waiting time to nanoseconds
return sync.tryAcquireNanos(1, unit.toNanos(timeout));
}
public final boolean tryAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {<!-- -->
// Throw an exception when the thread is interrupted
if (Thread. interrupted())
throw new InterruptedException();
// try to acquire the lock
return tryAcquire(arg) ||
// When not obtained, execute "tryLock" with waiting time
doAcquireNanos(arg, nanosTimeout);
}
// acquire lock with wait time
private boolean doAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {<!-- -->
// No waiting time, failed to acquire lock
if (nanosTimeout <= 0L)
return false;
// Calculate the end time of the lock
final long deadline = System.nanoTime() + nanosTimeout;
// Encapsulate the current thread into a Node, append it to the end of the queue, and return the current Node
final Node node = addWaiter(Node. EXCLUSIVE);
// Whether to acquire the lock failed
boolean failed = true;
try {<!-- -->
// infinite loop
for (;;) {<!-- -->
// Get the previous node of the current node
final Node p = node. predecessor();
// If the previous node is the head, after the lock is obtained by itself, if the acquisition is successful, the current node is set as the head, and the old head waits for recycling
if (p == head & amp; & amp; tryAcquire(arg)) {<!-- -->
setHead(node);
p.next = null; // help GC
failed = false;
return true;
}
// Calculate the remaining time to acquire the lock
nanosTimeout = deadline - System.nanoTime();
// no time
if (nanosTimeout <= 0L)
return false;
// Determine whether the thread can be suspended (WAITING)
if (shouldParkAfterFailedAcquire(p, node) & amp; & amp;
// You can hang up, judge whether the remaining time is greater than 1000 nanoseconds, and leave a certain execution time for LockSupport.parkNanos
nanosTimeout > spinForTimeoutThreshold)
LockSupport. parkNanos(this, nanosTimeout);
// When the thread is WAITING, it can be woken up by setting the interrupt flag bit, which directly throws an exception
if (Thread. interrupted())
throw new InterruptedException();
}
} finally {<!-- -->
if (failed)
// Cancel the processing of node
cancelAcquire(node);
}
}
lockInterruptibly acquiring a lock is similar to the above, and is not analyzed. The difference is that when acquiring a lock, if it cannot be acquired, it will always be acquired unless the interrupt flag is set.
2. Analyze the lock release process
1. Analyze the unlock method
The code is as follows (example):
// release the lock, no distinction between fair mode and unfair mode
public void unlock() {<!-- -->
sync. release(1);
}
public final boolean release(int arg) {<!-- -->
// Try to release the lock. If the number of reentries is not 0 after decrementing, it means that the lock resource is still held. At this time, it is false
if (tryRelease(arg)) {<!-- -->
// get head
Node h = head;
if (h != null & amp; & amp; h.waitStatus != 0)
// wake up the following thread
unparkSuccessor(h);
return true;
}
return false;
}
// try to release the lock
protected final boolean tryRelease(int releases) {<!-- -->
// The number of reentries to acquire the lock
int c = getState() - releases;
// Is there no lock resource currently held, an exception is thrown
if (Thread. currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
// Whether the lock is fully released
boolean free = false;
// The number of reentries is equal to 0, indicating that all are released
if (c == 0) {<!-- -->
free = true;
setExclusiveOwnerThread(null);
}
setState(c);
return free;
}
private void unparkSuccessor(Node node) {<!-- -->
// Get the status of the node node
int ws = node.waitStatus;
if (ws < 0)
// If the node turns to state -1, set it to 0 (initialized state)
compareAndSetWaitStatus(node, ws, 0);
Node s = node. next;
// if there is no next node || or node status is 1 (meaning set to cancel)
if (s == null || s.waitStatus > 0) {<!-- -->
s = null;
// traverse from the tail to find normal nodes
//Because when adding a new node, the pointer will point to the end of the linked list first, and the relationship has not been established completely, so the newly created node cannot be found in the correct order
for (Node t = tail; t != null & amp; & amp; t != node; t = t.prev)
if (t. waitStatus <= 0)
s = t;
}
if (s != null)
// wake up the thread
LockSupport. unpark(s. thread);
}
Summary
To be summarized.