Make writing a habit together! This is my first day to participate in the “Gold Digging Day New Plan · April More text challenge”, click to see the details of the activity.
Java ReentrantLock source code implementation, including lock, unlock source code, and fairness, reentrant implementation!
1 Overview of ReentrantLock
public class ReentrantLock extends Object implements Lock, Serializable
ReentrantLock comes from JDK1.5 and is in the LOCKS subpackage of the JUC package, exclusive (mutex) reentrant locks. He has all the features of Synchronized, and much more powerful ones.
Realize the Lock interface, with a universal operation Lock method. As a result of the JUC package, internal is the use of AQS queue synchronizer to assist the implementation, rewriting the AQS exclusive lock acquisition method, and achieve reentrancy.
ReentrantLock also has fair and unfair lock acquisition modes, which are not provided by AQS but implemented by ReentrantLock based on AQS itself.
In addition to the generic methods of the Lock interface. This class also defines isLocked and getLockQueueLength methods, as well as related protected access methods that may be useful for detection and monitoring.
To learn more about the source implementation of ReentrantLock, you should first learn and understand AQS. The following source code involving AQS are not said, in the previous article has a detailed introduction!
1.1 API methods for ReentrantLock
In addition to the generic methods of the Lock interface, it also has the following unique methods:
| Method names | describe |
| int getHoldCount() | Query the number of times the current thread held this lock (reentrant times) before this method was called (lock method invocations – UNLOCK method invocations). |
| int getWaitQueueLength(Condition condition) | Returns an estimate of the number of threads waiting in the given conditional queue associated with this lock. |
| boolean hasQueuedThread(Thread thread) | Queries whether a given thread is waiting to acquire this lock. |
| boolean hasQueuedThreads() | Queries whether any thread is waiting to acquire the lock. |
| boolean hasWaiters(Condition condition) | Queries whether any thread waits for a given condition associated with this lock |
| boolean isFair() | Query whether the lock is a fair lock. |
| boolean isHeldByCurrentThread() | Query whether the lock is held by the current thread. |
| boolean isLocked() | Query whether this lock is held by any thread. |
| protected Thread getOwner() | Returns the thread that currently owns the lock, or null if it does not |
| protected Collection getQueuedThreads() | Returns a collection of threads that might be waiting to acquire this lock |
| int getQueueLength() | Returns an estimate of the number of threads waiting to acquire this lock. |
| protected Collection getWaitingThreads(Condition condition) | Returns a collection of threads that might be waiting under a given condition associated with this lock. |
1.2 reentrant
ReentrantLock is a reentrant mutex. As the name implies, “mutex” means that the lock can only be owned by the same thread at a certain point in time. Reentrant means that the lock can be acquired more than once by a thread. Of course synchronized is also a reentrant mutex.
The synchronized keyword implicitly supports re-entry, such as a synchronized modified recursive method in which the thread of execution acquires the lock several times in a row after it has been acquired.
ReentrantLock does not support implicit reentry like the synchronized keyword, but when the lock() method is called, a thread that has acquired the lock can call the lock() method again to acquire the lock without blocking. The main implementation is to implement the tryAcquire(int Acquires) method in a scenario where the thread holding the lock acquires again.
In ReentrantLock, the state synchronization status value of AQS indicates how many times a thread can reentrant the lock. By default, a value of state of 0 indicates that the current lock is not held by any thread. When a thread acquires the lock for the first time, it attempts to use CAS to set state to L. If CAS succeeds, the current thread acquires the lock, and records that the holder of the lock is the current thread. After the thread acquires the lock a second time without releasing it, the status value is set to 2, which is the reentrant count. When the thread releases the lock, it tries to use CAS to decrease the state value by 1, and if the state value is 0 by l, the current thread releases the lock.
1.3 Fair and Unfair
According to the preemption mechanism, locks can be divided into fair locks and unfair locks.
If in absolute time, the lock acquisition request must be satisfied first, that is, the thread with the longest waiting time has the highest priority to acquire the lock, it can also be said that lock acquisition is sequential. So this lock is fair, and vice versa, it’s not fair.
Fair lock is strictly FIFO lock competition, but unfair lock is disorderly lock competition, just released the lock thread to a large extent can be relatively fast to get the lock, the queue thread can only wait, so unfair lock may have the problem of “hunger”. However, repeated lock acquisition can reduce switching between threads, while fair lock is strict thread switch, which has a relatively large impact on the operating system, so the throughput of unfair lock is greater than fair lock, which is why the JDK uses unfair lock as the default implementation.
A ReentrantLock can be either fair or unfair. When the constructor of this class ReentrantLock(Boolean fair) takes true as an argument, a ReentrantLock is a fair lock. The threads queue up to acquire a fair lock, i.e. the lock will be owned by the thread that has waited the longest.
Programs that use fair locks are less efficient in multithreaded environments than the default (which uses unfair locks). Even a fair lock does not guarantee fairness in thread scheduling, and a subsequent call to tryLock can obtain the lock without queuing.
2 Principles of ReentrantLock
2.1 Basic Structure
Let’s take a look at ReentrantLock’s class diagram structure to help us do a complete analysis:
As you can see from the figure, ReentrantLock has three inner classes, Sync, NonfairSync, and FairSync. Sync directly inherited AbstractQueuedSynchronizer, should be provided the general method of implementation.
NonfairSync and FairSync inherit Sync directly. Can guess from the name, fair lock internal call is FairSync class, is a fair lock internal call NonfairSync class, they have their own special ways, they are indirectly inherited AbstractQueuedSynchronizer abstract classes.
So ReentrantLock relies on AQS internally, but implements two inner classes because of the need to support fair and unfair modes. After we specify the mode to use, we can choose to initialize different AQS implementations to support it.
2.2 the constructor
2.2.1 already ()
public ReentrantLock()
Create an instance of ReentrantLock. This is equivalent to using ReentrantLock(false). That is, the default no-parameter constructor is an unfair mode.
/** A reference to the synchronizer object in ReentrantLock */
private final Sync sync;
/** * Create an unfair instance of ReentrantLock, which is the default mode */
public ReentrantLock(a) {
// Internally initializes a NonfairSync object
sync = new NonfairSync();
}
Copy the code2.2.2 already (Boolean fair)
public ReentrantLock(boolean fair)
Create a ReentrantLock with a given fairness policy. False indicates unfair and true indicates fair.
/** * Create a ReentrantLock with a given fairness policy **@paramFair false means unfair and true means fair. * /
public ReentrantLock(boolean fair) {
// It is very simple to initialize different AQS objects according to the parameter selection
sync = fair ? new FairSync() : new NonfairSync();
}
Copy the code2.3 Principle of locking in unfair mode
2.3.1 Lock The lock cannot be obtained interruptively
In JUC, whenever a Lock is implemented, the Lock method will generally call the external Lock () method.
/** * exclusive reentrant lock */
public void lock(a) {
// Internally call the lock method implemented by the AQS synchronizer
sync.lock();
}
Copy the codeIn already realized, the lock is called the internal AQS synchronizer of the lock () method, if we learn the AQS, then we know that there is no lock in AbstractQueuedSynchronizer method, it provides some template method and rewritable method. Therefore, the lock method should be Sync, which directly inherits AQS and is added by the implementation itself.
abstract static class Sync extends AbstractQueuedSynchronizer {
/** * provides the lock method * this method is an abstract method, the concrete implementation is done by the subclass ** mainly used to unify the method name */
abstract void lock(a);
/ /.....................
}
Copy the codeSo we’ll have to look in the subclass for the implementation, but in this case, because of the unfair pattern, we should look in the NonfairSync inner class.
/** * The implementation of the lock method in NonfairSync is used to unfairly acquire an exclusive shared lock */
final void lock(a) {
* CAS attempts to update state from 0 to 1 * */, assuming that the current lock has not been re-entered
if (compareAndSetState(0.1))
// If CAS succeeds, the lock was acquired, and the thread that acquired the lock is recorded
setExclusiveOwnerThread(Thread.currentThread());
else
/*2 If CAS fails, the current lock was re-entered or acquired by another thread, then execute AQS acquire template method to try to acquire */
acquire(1);
}
/** * the method in AQS records the thread from which the lock was acquired@paramThread Current thread */
protected final void setExclusiveOwnerThread(Thread thread) {
// Record the thread
exclusiveOwnerThread = thread;
}
Copy the codeNonfairSync’s lock is the real entry point to the locking process, which is roughly divided into two steps:
- The thread attempts to acquire the lock first, when CAS updates the value of state from 0 to 1, assuming that no lock is available at this point. If the CAS succeeds, the lock has not been acquired by any thread. If the CAS succeeds, the current thread is marked as the thread holding the lock.
- If it fails to acquire the lock, it indicates that the lock has been acquired by a thread before, or another thread succeeded in CAS. Then, run the acquire method to continue trying to acquire the lock.
2.3.1.1 Acquire An exclusive lock
Acquire method we are familiar with, is the template method provided by AQS, used for exclusive lock acquisition, this method is explained in detail in the AQS chapter.
In the Acquire method, attempts to acquire the lock continue until they succeed. The main one is our own rewrite of the tryAcquire method, which is the key to reentrant and reentrant, fair and unfair.
/** * an exclusive attempt to acquire the lock. If the lock fails, it will enter the synchronization queue and wait */
public final void acquire(int arg) {
// The interior is made up of four method calls
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the code2.3.1.1.1 tryAcquire attempted to obtain a lock
TryAcquire is a method defined in AQS, whose implementation in AQS is to throw an exception that needs to be overridden by subclasses themselves.
protected boolean tryAcquire(int arg) {
throw new UnsupportedOperationException();
}
Copy the codeReentrantLock has different implementations of this in fair and unfair modes, which are as follows:
/** * The tryAcquire implementation in NonfairSync attempts to acquire an exclusive lock@paramAcquires argument, 1 * passed in ReentrantLock@returnTrue Obtain success false Obtain failure */
protected final boolean tryAcquire(int acquires) {
// Call the nonfairTryAcquire method, which is in Sync
return nonfairTryAcquire(acquires);
}
Copy the code2.3.1.1.1.1 nonfairTryAcquire can reenter an unfair acquisition exclusive lock
NonfairTryAcquire is a method for trying to acquire locks in unfair mode.
Since tryAcquire is basically the only method that can be overwritten when acquiring a lock, and this tryAcquire calls nonfairTryAcquire, nonfairTryAcquire should contain the logic to implement re-entrant locks and unfair modes, as follows:
- If state=0, it means that the current lock is not held by any thread. Then try CAS to obtain the lock. If CAS succeeds, set the current thread and return true.
- If so, execute the reentrant logic, add state to 1 and write back to indicate the number of reentrant times +1, return true, and the method ends.
- If the CAS fails (another thread has already acquired the lock), or if the current lock is already held by another thread, return false.
/** * Sync methods * reentrant lock unfair access exclusiveness **@paramAcquires argument, 1 * passed in ReentrantLock@returnTrue Obtain success false Obtain failure */
final boolean nonfairTryAcquire(int acquires) {
// Get the current thread
final Thread current = Thread.currentThread();
// Get the current synchronization state value
int c = getState();
/* If 0, no thread has acquired the lock */
if (c == 0) {
// Try to get the lock
if (compareAndSetState(0, acquires)) {
// Set thread variables on success
setExclusiveOwnerThread(current);
// Return true, the method ends
return true; }}/* If the value is not 0, the thread has acquired the lock. If the value is not 0, the thread has acquired the lock
else if (current == getExclusiveOwnerThread()) {
// The new state should be the state+1 obtained previously
int nextc = c + acquires;
* The new state is less than 0, and only happens when c is integer.max_value. * Due to the binary computing principle, If you add 1 to an int, it will be less than 0 * */
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
Reentrant count +1 (reentrant count +1
// CAS is not required, because in the else if condition, the current thread is the thread that has acquired the lock.
setState(nextc);
// Return true, the method ends
return true;
}
/* If the thread that reentered the lock failed to acquire the lock, or if the thread that re-entered the lock is not the current thread, return false * and it will be added to the synchronization queue, performing the following logic * */
return false;
}
Copy the codeThis implementation uses state to count the number of times a lock is reentranted by a thread. For each ReentrantLock, state is incremented by 1. The maximum number of reentrant times is integer. MAX_VALUE, which if added to by 1 becomes negative, and an exception is thrown!
In addition, there is a CAS attempt to acquire the lock when entering the lock method, but the nonfairTryAcquire method covers all possible cases. Why would there be code that looks redundant in the lock method? Although the lock is a reentrant lock, there is basically no business logic that requires reentrant in the practical application. Generally, it is a one-time acquisition and one-time release. An intuitive idea is that it can improve code performance without requiring more judgment. In addition, in the tryLock method, the nonfairTryAcquire method is called directly, so nonfairTryAcquire must also contain all cases.
NonfairTryAcquire (ARG) Returns true, indicating that the current thread successfully acquired the lock (first or reentrant). NonfairTryAcquire (ARG) if true is returned.
2.3.1.1.1.2 How can nonfairTryAcquire be unfair
Unfair means that the thread that tries to acquire the lock first does not necessarily acquire the lock before the thread that tries to acquire the lock later.
If thread A calls the lock method to nonfairTryAcquire and finds that the current state is not 0 and that the current thread is not A thread owner, return false and the current thread is put into the AQS synchronization queue.
At this time, thread C releases the lock, and state becomes 0. At this time, thread B also calls the lock method to execute nonfairTryAcquire, and finds that the current state value is 0. Therefore, it obtains the lock through CAS setting, or even obtains the lock first in the outside lock method.
It is clear that thread A first requests to acquire the lock, but thread B later requests to acquire the lock, which is unfair. Here thread B does not check whether there are threads in the current AQS queue that request the lock earlier than itself before acquiring the lock, but uses the snatch strategy, from which we can also imagine the implementation of fair mode!
2.3.2 LockLNterruptibly Can interrupt lock acquisition
This method is similar to the Lock method, but it responds to interrupts in that if the current thread is suspended because it did not acquire the lock, the current thread will wake up and throw InterruptedException if another thread calls the current thread’s interrupt method.
Here interrupt and uninterruptible mode, is AQS has been implemented for us, we just need to call the corresponding template method on the line, do not need to implement their own. The AQS acquireInterruptibly template method is described in detail in the AQS section.
/** * Methods in ReentrantLock can interrupt lock acquisition **@throws InterruptedException
*/
public void lockInterruptibly(a) throws InterruptedException {
// Internally call the AQS template method acquireInterruptibly
sync.acquireInterruptibly(1);
}
/** * Methods in AQS can interrupt to obtain locks **@paramArg parameter, passed 1 * in ReentrantLock@throws InterruptedException
*/
public final void acquireInterruptibly(int arg)
throws InterruptedException {
// If the current thread is interrupted, throw an exception
if (Thread.interrupted())
throw new InterruptedException();
// Try to get the lock
if(! tryAcquire(arg))// If not, call AQS interruptible method
doAcquireInterruptibly(arg);
}
Copy the code2.3.3 Trylock Attempted to obtain the lock
Attempts to acquire the lock, returning true if the current thread acquires the lock (first or reentrant), false otherwise. This method does not cause the current thread to block!
The nonfairTryAcquire method is called internally, and there is only one implementation for both fair and unfair modes, so actually trylock is always an unfair call.
/** * Method of ReentrantLock * unfair attempt to obtain an exclusive lock **@returnTrue Successful false failed */
public boolean tryLock(a) {
// Call Sync's nonfairTryAcquire method internally. If you can't get it, it will not block and will return false
// The mode is not fair and cannot be changed
return sync.nonfairTryAcquire(1);
}
Copy the code2.4 Fair mode locking principle
Fairness depends on the order in which locks are acquired. If a lock is fair, the order in which locks are acquired should conform to the absolute chronological order of the request, known as FIFO.
In nonfairTryAcquire(int acquires), if CAS is set successfully, then the current thread has acquired the lock.
The first difference: starting from the fair lock entry, there is one less attempt for CAS to acquire the lock compared to an unfair lock.
final void lock(a) {
acquire(1);
}
Copy the codeThen look at fairlock FairSync’s implementation of the tryAcquire method for obtaining the lock:
/** * The method in FairSync gets the lock fairly **@paramAcquires argument, passed 1 * in ReentrantLock@returnTrue Successful false failed */
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
/* The other parts are the same as the implementation of the unfair lock, except that the HasqueuedBoommethod is called and the hasqueuedBoommethod is a guarantee of fairness */
if(! hasQueuedPredecessors() && 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;
}
Copy the codeThe only difference between this method and nonfairTryAcquire(int acquires) is that the hasqueued24 () method determines whether any thread has waited longer than the current thread to acquire the lock. That’s the second difference.
2.4.1 Hasqueued24 Determines the waiting time
/** * Method in AQS * queries whether any thread has waited longer than the current thread to acquire the lock. * *@returnReturn true if there is a precursor and false */ otherwise
public final boolean hasQueuedPredecessors(a) {
// Synchronize the last node of the queue
Node t = tail;
// Synchronize the queue head node
Node h = head;
Node s;
// If the head node is equal to the tail node, false is returned, indicating that no thread is waiting
Otherwise, if the successor s of the header is not null and the thread of s is equal to the current thread, return false, indicating that the current thread is the one that has waited the longest
returnh ! = t && ((s = h.next) ==null|| s.thread ! = Thread.currentThread()); }Copy the codeSince the head node in the synchronous queue is the thread that currently acquired the lock and the new node is added to the tail, the thread represented by the second node in the queue is the one with the highest request priority, i.e., the one with the longest wait time.
If the head node is equal to the tail node, there are no threads waiting in the synchronization queue. Otherwise, if the successor s of the header is not null and the thread of S is equal to the current thread, the current thread is the one that has waited the longest. In both cases, false is returned, indicating that no thread has requested the lock before the current thread, so the current thread can acquire the lock.
If this method returns true, it means that a thread requested the lock earlier than the current thread. In this case, the current thread will not perform CAS operation to acquire the lock, but return false, which ensures that the sequence of acquiring the lock is the same as that of joining the synchronization queue, which ensures fairness, but also significantly increases the cost of acquiring the lock. For performance, the implementation of ReentrantLock is unfair by default.
2.5 Unlocking Principles
2.5.1 UNLOCK Releases a lock
In JUC, unlock () is invoked externally whenever a Lock implements a Lock.
/** * Attempts to release the lock **@throwsIllegalMonitorStateException if the current thread is not holding the lock, throw an exception * /
public void unlock(a) {
// Internally call AQS 'release template method
sync.release(1);
}
Copy the code2.5.1.1 Release Exclusive lock release
We are familiar with the release method, which is the template method provided by AQS for exclusive lock release. This method is explained in great detail in the AQS chapter.
The main thing here is the tryRelease method we rewrote ourselves, where the key is the reentrant lock release logic.
/** * exclusive release lock **@paramArg parameter *@returnReturn true on success, false */ otherwise
public final boolean release(int arg) {
/*tryRelease releases the lock. This method will return true on success or false otherwise
if (tryRelease(arg)) {
// Get the header
Node h = head;
// If the header is not null and the state is not zero
if(h ! =null&& h.waitStatus ! =0)
/* Then wake up a successor of the header in a wait-locked state * this method was described in acquire * */
unparkSuccessor(h);
return true;
}
return false;
}
Copy the code2.5.1.1.1 tryRelease Attempted to release the lock
TryRelease is a method defined in AQS that throws an exception and needs to be overridden by subclasses themselves.
protected boolean tryRelease(int arg) {
throw new UnsupportedOperationException();
}
Copy the codeReentrantLock has the same implementation in both fair and unfair modes, i.e. the lock release logic is the same, in Sync:
/** * Sync's tryRelease implementation attempts to release the lock@paramThe releases parameter, which is passed 1 * in the ReentrantLock@returnTrue Successful false failed */
protected final boolean tryRelease(int releases) {
// Get the state value c after release, minus 1 in ReentrantLock
int c = getState() - releases;
/ / if the current thread is not acquiring a lock the thread, then throw IllegalMonitorStateException anomalies
if(Thread.currentThread() ! = getExclusiveOwnerThread())throw new IllegalMonitorStateException();
// Free Indicates the flag bit used to record whether the release is successful. The default value is false
boolean free = false;
// If c is 0, the lock is completely released, and the thread is cleared. Free is true
// If the lock is re-entered, unlock is required several times because state is subtracted 1 each time and the lock is not fully released
if (c == 0) {
free = true;
setExclusiveOwnerThread(null);
}
// Set the new state
setState(c);
/ / return free
return free;
}
Copy the codeIn ReentrantLock, the implementation of tryRelease is actually to reduce the number of times the thread holds the lock state by 1, that is, the state value by 1. If the state value is 0 after the reduction, it means that the thread will release the lock completely, set the thread acquiring the lock to NULL, update the state value, and return true.
If false is returned, the lock is not fully released. Since the thread executing the method necessarily holds the lock, this method does not require any CAS operation to update the state.
3 already concluded
ReentrantLock is an exclusive ReentrantLock based on AQS. It also has fair mode and unfair mode. You can choose to implement non-unfair lock and fair lock.
If a new thread attempts to acquire the lock, the new thread may succeed in the race with the subsequent thread. There are two possibilities that support this:
- In the Lock method of NonfairSync implementation, CAS obtains the lock (only if the current lock is not held by any thread).
- In the nonfairTryAcquire method, CAS acquirement the lock (only if the current lock is not held by any thread).
If the new thread acquires the lock, then the thread that acquires the lock does not need to join the queue. However, the awakened successor node in the queue can only wait for the lock to be released after the lock is released.
As long as the node (thread) is queued in the synchronization queue, it can only obtain the lock according to the queue order, while the thread that is not queued may directly jump the queue to obtain the lock. If the thread fails to acquire the lock in either of the above two places, the thread is constructed and queued to wait, with no possibility of acquiring the lock first.
As you can see, in the unfair mode, threads waiting for a long time in the synchronous queue have no priority over threads not yet in the queue, and even compete at a disadvantage: threads in the queue have to wait to wake up and check whether the precursor node is a head node. In the case of fierce lock competition, the threads waiting in the queue may be late to compete for the lock, which is not fair in the case of high concurrency starvation problem.
But not fair model will have good performance, direct access to lock the thread joining a waiting queue can obtain locks, revoke the synchronization of queue structure nodes and join operations, because join the queue when the tail is also need the CAS competition, may lead to waste of CPU, and it also may be because of subsequent threads waiting, wake up, causing the thread context switching, Very time consuming.
Even a fair lock does not guarantee fairness in thread scheduling. In fair mode, a subsequent thread can call the tryLock method and obtain the lock without queuing. Because inside the tryLock method is a direct call to the nonfairTryAcquire method, which we said is not fair!
To learn more about the source implementation of ReentrantLock, you should first learn and understand AQS. The source of this article involves AQS in the above article has a detailed introduction!
If you don’t understand or need to communicate, you can leave a message. In addition, I hope to like, collect, pay attention to, I will continue to update a variety of Java learning blog!