Older versions of Synchronized are known to be heavyweight locks, and heavyweight locks occur because thread blocking and awakening require the operating system to switch from kernel to user mode. ReentrantLock’s lock() method also causes threads to hibernate and block, so why is ReentrantLock more efficient?
This question has prompted me to analyze the source code of ReentrantLock. The main part is to analyze how AQS can achieve the ReentrantLock scheme, and discuss why it is faster (compared to the heavyweight lock).
Before the analysis of the source code, I probably understand the main use of Lock or CAS way to achieve the method, its internal first use CAS to do the prediction, if the prediction found the Lock success is directly not locked, RLock can also have a lot of functions such as tryLock and fair Lock non-fair Lock and so on
Well, their previous shallow understanding, there may be errors, now into the world of source analysis
Class family (understand, no useful first look at the field and class inheritance)
Above is the class diagram of fields, attributes, and inner classes. The inner structure of this class is relatively simple
Since there’s a lot of detail here, I’m sharing this image separately
Take a look at the Node class first
It can be found that this is a data storage class, wherein waitStatus stores the state of the node, prev and Next stores the front and back bidirectional linked list, and nextWaiter stores the node with the next waiting state. The main purpose of this class is to store the state of each node
Then take a look at ConditionObject
This is a one-way linked list, which mainly contains the nodes in the wait state
A simple look at it is also a one-way linked list and state
[1] State is used as a ticket to Lock success in the Lock — acquire — tryAcquire function, and state has only two values, 1 or 0
[1] The location of the mark, search this blog and you will find three, indicating that several nodes have the same knowledge
Let’s start with the construction method
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
Copy the codeHere the constructor is the most complete, fair == true is a fair lock, fair == false is an unfair lock
The difference between a fair lock and an unfair lock is to check if an old Node already exists in the queue
How do we start with ReentrantLock
public void lock(a) {
sync.acquire(1);
}
// arg = 1
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeAnalyze the tryAcquire function
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
// Get the 'state' state
int c = getState();
// If it is empty, it is the first time to lock
if (c == 0) {
// Check if there are any old threads waiting longer in the queue;
Acquires == 1; // Modify the 'state' state for the first time and change the value to 'acquires == 1'.
// Set the exclusively owned thread
// The following 'if' statement can be expressed:
// If the previous queue is empty and the old Node cannot be found, this is the method of fair lock judge scheme
// change the value of 'state' from 0 to 1
if(! hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
// The 'if' statement can come in and you can set the exclusive thread to own the lock object
setExclusiveOwnerThread(current);
return true; }}// If the lock object is not acquired for the first time, we need to determine whether the current thread and the exclusive thread are the same thread, if so, it means that the lock reentrant
else if (current == getExclusiveOwnerThread()) {
// Lock reentrant to get the current rush count
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
// Add one more layer of reentrant locks
setState(nextc);
return true;
}
return false;
}
Copy the codeThe tryAcquire method above means that if it is the first lock, set the lock object to own the thread and increase the number of reentrants to 1. If it is not the first lock, determine whether it is the original exclusive thread, if it is the lock reentrant number +1
Now analyze the fair lock function hasqueuedToraise
Note the waitStatus status before analyzing the method
/** The waitStatus value indicates that the thread has been cancelled */
static final int CANCELLED = 1;
/** The value of waitStatus, which indicates that the inheritor's thread needs unparking. * /
static final int SIGNAL = -1;
/** The waitStatus value indicates that the thread is waiting for a condition
static final int CONDITION = -2;
/** The waitStatus value, which means the next acquireShared should be propagated unconditionally. * /
static final int PROPAGATE = -3;
Copy the codepublic final boolean hasQueuedPredecessors(a) {
Node h, s;
if((h = head) ! =null) {
// Get the next node of the head node == null or 'waitStatus' is cancelled
if ((s = h.next) == null || s.waitStatus > 0) {
s = null; // traverse in case of concurrent cancellation
// Find the state that is just created, 'CONDITION' and 'PROPAGATE', give s variable
for(Node p = tail; p ! = h && p ! =null; p = p.prev) {
if (p.waitStatus <= 0) s = p; }}// If the Node thread found is the same as the current thread, the previous Node exists, indicating that there is an executable Node in front of the queue
if(s ! =null&& s.thread ! = Thread.currentThread())return true;
}
return false;
}
Copy the codeIf the thread that is not the Owner cannot re-enter the lock, only the thread that is not the Owner cannot re-enter the lock
private Node addWaiter(Node mode) {
// Get a new Node
Node node = new Node(mode);
for (;;) {
Node oldTail = tail;
if(oldTail ! =null) {
// Add 'tail' to 'prev' of 'node'
node.setPrevRelaxed(oldTail);
// Modify the address of 'tail'
/** * 'if (oldTail == memory size tail) {memory size tail = node}' */
if (compareAndSetTail(oldTail, node)) {
// This is equivalent to 'tail.next = node'
oldTail.next = node;
returnnode; }}else {
// use cas to create a header nodeinitializeSyncQueue(); }}}Copy the code- The code above is
node.prev = tail;thentail = node;afteroldTail.next = node; / / hereoldTailIs beforetailaddress
To put it bluntly, this is like adding a new node to a bidirectional list
Remember, this is actually the linked list in AQS, which records wait node to AQS
// 'node' added to the last node in 'wait' list, 'arg' reentrant count, where 'arg' == 1 '
final boolean acquireQueued(final Node node, int arg) {
boolean interrupted = false;
try {
for (;;) {
// Get the previous node
final Node p = node.predecessor();
// Try again to get the exclusive state, but in my flow it will be 'false' that does not satisfy the condition, but the address of 'head' is given to the 'p' object
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
return interrupted;
}
// If there is a relationship between 'p' and 'node' that causes the return value to be 'true', the thread is blocked. We know that the thread is blocked because the lock is being used by someone else, and the current thread tried to lock it but failed. The 'p' object continuously fetches the nodes in front of node through 'node' and then puts them into the following function to perform some kind of algorithm, resulting in different results. Here 'node' and 'node.prve' are not seen to have been modified. We expect it to be modified in the following function
// Now let's formally analyze this function in the following code block
if (shouldParkAfterFailedAcquire(p, node))
// 'park' blocks and throws the status of whether or not it is interrupted to the 'interrupted' variableinterrupted |= parkAndCheckInterrupt(); }}catch (Throwable t) {
cancelAcquire(node);
if (interrupted)
selfInterrupt();
throwt; }}Copy the codeThe analysis of the function shouldParkAfterFailedAcquire
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
/* * If 'node. SINGAL' returns' true ', * * if 'node. SINGAL' returns' true ', * * if 'SINGAL' returns' true ', * * if 'SINGAL' returns' true ', * * if 'SINGAL' returns' true ', * * if 'SINGAL' returns' true ', * * if 'SINGAL' returns' true ', * Then generally have to wait for 'unparking' */
return true;
if (ws > 0) {
If the pred is greater than zero, we find that the pred has been canceled, so we need to skip and find the next Node until we can't find the canceled Node */
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
// After finding a node that is not canceled, set the node's 'next' field to the reference address of 'node'
pred.next = node;
} else {
/* * 'waitStatus' must be 0 or PROPAGATE. Indicates that we need a signal, but not yet a park. The caller needs to retry to ensure that cannot 'acquire' only 'parking' */
pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
}
return false;
}
Copy the codeThe main purpose of this function is to find the Node in signal state. If the Node is not signal state, it will find the Node that has not been cancelled. If the state is in the initial or PROPAGATE state, cas should be used to change it into Signal state and wait for the next time to enter this function again
The old version of theSynchronizedWhy slow?
ReentrantLock does not lock directly, but uses the CAS operation first and then the heavyweight lock, and supports the priority queue scheme, whereas older Synchronized is the heavyweight lock directly and therefore slower
The new version of theSynchronizedWhat did you do?
The new version of Synchronized has improved a number of features, including:
The new version does not allow direct use of the upper weight lock, it has two barriers, the first is a bias lock, the second is a lightweight lock
Before we introduce these two thresholds, we need to first understand the object header structure
Object head
As shown above, the object header is made up of three parts, the most important of which is the Mark Word
Mark Word
Biased locking
The first is a biased lock (also known as a spin lock, but the lighter locks are also part of the spin lock category)
The premise of biased lock is that if there is only one thread, or two or more threads are executed alternately, then biased lock will be used. The advantage of biased lock is that only one CAS operation is performed. If the lock object is about to enter the biased lock, there will be the following steps:
- Example Change the flag bit to 01
- Change the bias mode to 1
- Use CAS to record the id of the thread that performs the upward bias lock on the mark word thread ID
After these three steps, the bias lock is complete
This prevents any synchronization operations (such as locking, unlocking, and modifying Mark Words) from occurring when there is only one thread.
But now what if suddenly another thread appears??
This happens in two ways
Thread ARun sync code block after exit anotherThread BAlso entered, this time the bias lock will beHeavy biasHowever, there is a problem with this bias. If the bias is too much (like 20 or 40 times), the bias lock will be upgraded to a lightweight lockThread ARunning synchronized code block, not exiting yet,Thread BWhen it runs, another thread (thread A) is found in the synchronized code blockThread AWill be suspended, upgrading bias locks to lightweight locks
The lock upgrade process is shown below:
In the beginning
(1) marks a = 01 | can bias a = 1 | thread ID position is empty
② After the initial lock, the cas mode is used to set the thread ID to the mark Word thread ID. At this point, the lock is complete
(3) Duplicate bias. If one thread finishes executing the synchronized code block and another thread enters the synchronized code block, the bias lock will be released and the thread Id position will be empty
(4) If hashCode already exists, bias lock cannot be used, so only lightweight lock can be used at this time. The locking method of lightweight lock is also very simple, mainly we still need to create the memory of pointer address above the Mark word, and then change the mark bit to 00. The location of the store pointer is left empty for the thread to store a spatial address called the Lock Record created in the current thread’s stack frame
⑤ If the lightweight competition situation, this time will spin 10 times, if after 10 times will expand, change the lock flag bit to 10 state, and then the original record lock record space address change to the heavyweight lock pointer address
Lightweight lock
A lightweight lock can also be called a spin lock. The spin is a while idle, which prevents the thread from entering the heavyweight lock directly. The while idle is usually 10 times
Now let’s talk about the detailed process of upgrading to lightweight locks in the case of biased locks or non-biased locks
In the case of the lock flag bit 01, the thread creates the lock record space, and now the lightweight lock time is officially entered
① Copy the content of the Mark word to the lock record space lock record, and then empty the mark word space, make a pointer to just the lock record space address
② Change the mark word pointer to PTR. Now this pointer points to the address of the lock record, which means that the lock object has the address of the lock record. Then change the lock flag bit to 00
All right, lightweight locking is successful
The process is simple
Now the lock object has such a pointer to the Lock Record, now the unlock method is to directly copy the contents of the Lock Record into the Mark Word (using CAS), if the replacement is successful, it means that the unlock is successful
The process by which a lightweight lock expands to a heavyweight lock
If in the process of lightweight lock lock exists another thread B at this lock preemption, the situation is to find the lock object is locked thread B stage, at this time choose spin thread B, the number of spin generally for 10 times, if after 10 spin or not able to get the lock, now on inflation for the heavyweight lock
① The mark Word space becomes a heavyweight pointer, now set the heavyweight pointer to the Monitor pointer of the heavyweight lock, and change the lock state in Mark Word to 10