The lock
As I mentioned earlier, one of the most difficult aspects of concurrent programming is the problem of concurrent access control for shared resources. If synchronization is not done well, it is easy to have inconsistencies, which can lead to errors in business logic. However, if the control of shared resources is too strict, it can easily cause a great impact on performance. In concurrent programming, on the one hand, learn from Daniu’s source code exquisite ideas and structural design; On the other hand, if you have a solid grasp of concurrency fundamentals, you can easily combine design patterns and architectural ideas to create high-quality, high-concurrency, high-performance systems. Concurrent programming is very dependent on design pattern and architecture design. Therefore, concurrent programming requires high accumulation of experience and knowledge.
As mentioned earlier, shared resources can easily cause inconsistencies in concurrent access, and the solution is known as pessimistic locking and optimistic locking. Pessimistic locks are as their name suggests: pessimistic locks assume that concurrent access will inevitably lead to state inconsistencies, so resources must be locked before concurrent operations, allowing concurrent threads to serialize access one by one. Optimistic locks, on the other hand, assume that concurrent access will not cause state inconsistencies in most cases, so it can be accessed safely. In case of a problem, optimistic locks will not add lock restrictions on shared resources. This is my personal understanding, maybe straightforward is not so precise, the definition of pessimistic lock, optimistic lock can search for more accurate official explanation.
Let’s look at how pessimistic locking and optimistic locking are implemented in Java. Pessimistic Lock is known to us in Java and can be implemented in two ways: synchronized and Lock, while optimistic Lock is mainly realized through CAS operation. Here’s a general comparison between synchronized and Lock: 1. Synchronized mainly relies on the underlying implementation of JVM, while Lock is implemented through coding, and its implementation methods are quite different. 2. In general programming usage is still relatively large, but in the real concurrent programming system, Lock mode is significantly better than synchronized: a. In older JDK versions, synchronized has been optimized, and the performance differences between synchronized and Lock are no longer noticeable b.synchronized Synchronized does not support interruption and timeout. That is to say, once synchronized is blocked, it will be blocked all the time if it cannot obtain all the resources. Even if synchronized is interrupted, it will be useless, which has a great impact on the performance of concurrent systems. Lock supports interrupts and timeouts, and attempts to acquire locks, extending synchronized well, so Lock is significantly superior to synchronized in terms of flexibility
In Java. Util. Concurrent. The locks in the package there are a lot of the Lock implementation class, commonly used have already, ReadWriteLock (implementation class ReentrantReadWriteLock), ReentrantLock is very common in the use of locks. In this section, we will take ReentrantLock as an example to analyze the implementation of Lock.
ReentrantLock
A ReentrantLock is a reentrant mutex in which threads can repeatedly acquire locks they already hold. Locks are basically designed to support reentrancy, otherwise deadlocks can easily occur. Such as: if the lock B does not support reentrancy, thread A under the condition of the lock is held B again acquiring A lock B, due to not support reentrancy thread A blocked, know lock B resources were released, but the lock B resources is held by A thread, so the thread A can never be awakened by access to the lock B, this leads to A deadlock.
Already internal implementation mainly through AbstractQueuedSynchronizer class implements, AbstractQueuedSynchronizer is an abstract class, in class already has two implementation class: NonfairSync and FairSync correspond to the implementation of unfair lock and fair lock respectively. The class structure relation is as follows:
+-------------------------------+
| AbstractQueuedSynchronizer |
+ -- -- -- -- -- -- -- -- -- -- -- -- -- -- ^ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - +
|
|
+------------------------------+
| Sync |
+ -- -- -- -- -- -- -- -- ^ -- -- -- -- -- -- -- -- -- -- ^ -- -- -- -- -- -- -- -- -- -- +
| |
| |
+-----------------------+ +-----------------------+
| NonfairSync | | FairSync |
+-----------------------+ +-----------------------+
Copy the codeThe ReentrantLock class contains a variable of type Sync. The main implementation is basically the implementation mechanism of Sync. The default construction is NonfairSync, which is not fair lock.
/ * *
ReentrantLock(false); ReentrantLock(false);
* /
public ReentrantLock() {
sync = new NonfairSync();
}
/ * *
* @param fair true: a fair lock False: an unfair lock
* /
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
Copy the codePrinciple of lock acquisition
When ReentrantLock is used, the general process is as follows: 1. Call lock() to apply for the lock resource. 2. After applying for the lock successfully, you can share the resource. 3. Unlock () is called to release the resource.
/ * *
* 1, obtain the lock, if the lock is not held by another thread immediately return, and set the lock's hold count=1
* 2, if the current thread already holds the lock, the lock count+1 and immediately return
* 3, if the lock is held by another thread, the current thread will sleep until the lock is acquired, and set hold count=1
* * Sync.lock () will invoke the sync implementation class NonfairSync.
* /
public void lock() {
sync.lock();
}
Copy the codeReentrantlock. lock() is a very simple source code, call sync.lock(), which reflects the core mechanism of ReentrantLock is implemented in sync, as mentioned above, sync in ReentrantLock has two subclasses respectively for fair lock and unfair lock. Here we will first look at the non-fair lock NonfairSync implementation:
/ * *
* state defined in AbstractQueuedSynchronizer class, said the current lock status:
*
* 0: The current lock lock is not held by any thread, the thread can use the CAS atomic operation to acquire the lock resource compareAndSetState(0, 1)
* Change state from 0 to 1, lock obtained successfully, state changed to 1, and set 'exclusiveOwnerThread' to current Thread
* exclusiveOwnerThread specifies the thread that holds the lock
*
* >0: indicates that the current lock is held by the thread, because the ReentrantLock is a ReentrantLock, the same thread can ReentrantLock multiple times, each time the state increment 1,
* When the lock resource release() is released, state is reduced by 1 until state=0, indicating that all locks are released and can be used by other threads
* If state is greater than 0, the CAS atomic operation compareAndSetState(0, 1) will fail, i.e. enter another branch
* /
final void lock() {
if (compareAndSetState(0, 1))
// The current thread successfully acquired the lock and assigned the current thread to the exclusiveOwnerThread variable
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1); // This branch indicates that an existing thread holds the current lock
}
Copy the codeSync’s exclusiveOwnerThread variable holds the current thread for subsequent reentrant use. Sync’s exclusiveOwnerThread variable holds the current thread for subsequent reentrant use. If the CAS operation fails, it indicates that there is a competition. The existing thread obtains the lock, but the current thread fails to obtain the lock, and needs to enter the acquire(1) branch. As you can see, the core of ReentrantLock is to determine whether it is occupied by the value of the state field.
/ * *
* 1, call tryAcquire attempts to acquire lock, note: tryAcquire AbstractQueuedSynchronizer class implement the direct throw an exception, are typically subclass NonfairSync, FairSync inheritance to rewrite the method
* 2. TryAcquire will try the following:
* a. If state=0 indicates that the current lock is not held by the thread again, return true on success and false on failure
* b. If the thread holding the lock is the current thread, add state by 1 to count the number of reentrant times and release all of them. Return true to indicate that the lock was acquired successfully
* c. If not, return fasle directly
* 3, tryAcquire returns true, tryAcquire returns true
* 4, If tryAcquire fails (i.e. TryAcquire returns false), encapsulate the current thread as a Node and place it in Sync Queue (call addWaiter) and wait for Signal
Repeatedly execute the repeatedly unblocking and unblocking command repeatedly.
* 4. SelfInterrupt if the lock is interrupted by the acquireQueued return value. If selfInterrupt, selfInterrupt
* /
public final void acquire(int arg) {
//acquireQueued blocks the thread node that has been added to the queue (the value returned by the addWaiter method), but before blocking, tryAccquire the lock again. If the retry succeeds, the queue will be returned without blocking
if (! tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
Copy the codeAbstractQueuedSynchronizer acquire () logic is roughly as follows:
1. First call tryAcquire(). The purpose of this method is: A. Re-spin to obtain the lower lock to see if it succeeded, and return true on success; B. Determine whether the thread holding the lock is the current thread. If so, add 1 to state and return true to indicate that the lock was acquired successfully. C. If neither of the preceding two goals is fulfilled, false is returned, indicating that the lock fails to be obtained. Note: tryAcquire () is directly in AbstractQueuedSynchronizer throws an exception, specific invocation is implemented in subclasses NonfairSync logic, the source code is as follows:
/ * *
If state=0, no thread currently holds the lock. If state=0, return true on success and false on failure
If the thread holding the lock is the current thread, the lock is acquired successfully and state acquires will be incremented
* 3. If false is returned, the lock fails to be obtained
* /
final boolean nonfairTryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
If (c = = 0) {/ / if equal to 0 indicates this moment has no thread holds the lock, so to get a lock, and immediately returns true on success, otherwise returns false immediately
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}else if (current == getExclusiveOwnerThread()) {
// If the thread holding the lock is the current thread, then state+1 and immediately return true to indicate that the lock was acquired successfully, which is a reentrant lock feature
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc); // Change the state value, where only the thread holding the lock will execute, there is no multi-thread contention, so use setState instead of CAS to change the partial lock function
return true;
}
return false;
}
Copy the codeAcquireQueued (addWaiter(node.exclusive), arg) acquireQueued(addWaiter(node.exclusive)) Its function is to append the thread that cannot obtain the lock to a bidirectional linked list, and then let the thread sleep, when the lock resource is available, it will wake up a thread from the bidirectional linked list head to compete for lock resources, its source code is as follows:
/ * *
* 1. Encapsulate the current thread that cannot acquire the lock as a Node and add it to Sync Queue. If read/write lock mode is used, the lock mode is shared
* 2. Sync Queue implements a bidirectional list, consisting of head and tail pointing to the head Node and tail Node, respectively. The head and tail Node are set to volatile, and changes to the head and tail nodes are seen by other threads
* 3. When a new Node is added to the bidirectional list, tail points to the new Node, next points to the new Node, and pre points to the previous tail Node
* 4. In short, the purpose of addWaiter is to append a Node wrapped by the current thread to the end of the queue via CAS and return the Node instance.
* 5. Main reasons to wrap threads as Node objects:
* a. When constructing a bidirectional linked list, we need to refer to the precursor node and the back-end node
* B. mode is used to distinguish between exclusive mode and shared mode
* waitStatus in c. ode is used to indicate the current thread status:
SIGNAL(-1) : a thread's successor is/has blocked and needs to be reawakened when it releases or cancels
CANCELLED(1) : the thread has been CANCELLED due to timeout or interruption and will not be allowed to compete for lock resources after its predecessor releases the lock
CONDITION(-2) : indicates that the thread is in a conditional queue and is blocked because of the call to condition.await
PROPAGATE(-3) : PROPAGATE the shared lock
0:0 indicates stateless, which is the default Node state. If a back-end Node is appended, set its front-end Node to SIGNAL
* /
private Node addWaiter(Node mode) {
Node node = new Node(Thread.currentThread(), mode);
Node pred = tail;
if (pred ! = null) {// default head = tail = null, tail! =null Indicates that there is a node in the queue and the CAS is directly sent to the last node
/ * *
* Append the current Node to the end of Queue:
* 1. Set the front driver of the current node to the tail node
* 2. Run the CAS command to point the tail pointer to the current node
* 3, and put the previous tail node next to the current node
* Append a node to the end of the bidirectional list using the three steps above
* /
node.prev = pred;
If (compareAndSetTail(pred, node)) {//4
pred.next = node;
return node;
}
}
enq(node); Enq initializes the Queue and appends the current node to the end
return node;
}
/ * *
* 1. CAS is called in an infinite loop, which will eventually succeed in appending the current thread to the end of the queue even in high concurrency scenarios
* 2. If tail is null for the first time, a default node is initialized and head=tail points to that node
* 3. The second loop appends the current node to the end of the node created in 1
* /
private Node enq(final Node node) {
for (;;) {
Node t = tail;
If (t == null) {//1. If (t == null) {//1
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
Copy the codeAcquireQueued () acquireQueued() after addWaiter(Node.exclusive) adds the current thread’s Node to the Queue, acquireQueued() is used to obtain the core lock logic. This method is designed to be an infinite for loop, which exits only if it is able to acquire a lock through tryAcquire(). If it does not acquire a lock, it does not loop through the loop indefinitely. Instead, it uses parkAndCheckInterrupt() to sleep the thread. A for loop is executed when the thread is awakened to see if it can acquire the lock. If the lock is obtained, the head pointer of the Queue points to the current thread and the previous head is discarded. When tryAcquire() compets for lock resources, there will be p == head judgment to determine whether the precursor node of the current thread is head node. Only the thread whose precursor is head node is qualified to call tryAcquire() to compete for lock resources. The design logic is mainly as follows: Apply for lock resources failed thread will join the Queue, in turn head to head and tail pointing to the tail, if the head is not null, then the nodes represent the thread for the possession of the lock, when this thread lock is released, it will wake up after its displacement node, and not all threads in the Queue, therefore, each time you release the lock only will wake a thread, In this way, if there are hundreds or thousands of threads, competing for lock resources will cause a great loss to system performance and effectively avoid performance storm C. This method will spin the thread to acquire the lock once more before putting it to sleep. If it fails again, it will immediately go to sleep. Let thread dormancy or comparing performance cost resources, involving a context switch, and waked up when a thread may be assigned to other CPU execution, due to caching of L1 and L2 is unique to the CPU, will reduce the cache hit ratio, the performance impact is bigger, so try not to sleep will not let the thread to sleep d. When a thread releases the lock, it will wake up the rear node of the thread in the head of the Queue. After waking up, the thread still has to compete for the lock. The object of contention is the thread that has just applied for the lock but has not entered the Queue waiting Queue. In terms of performance, if the thread applying for the lock can acquire the lock immediately, it avoids the subsequent operation of creating nodes, adding nodes to the Queue, etc., while the thread waking up from the Queue does not acquire the lock but just re-enters the sleep, which costs much less. Let them compete for lock resources together to avoid Queue waiting for threads in the Queue to be unable to acquire locks and starve to death
/ * *
* 1. This method is an infinite infinite loop, which will only be pushed if the first node is guaranteed to be the head node and tryAcquire() is successfully called once again
* 2, otherwise it will execute shouldParkAfterFailedAcquire waitStatus of precursor for () to the current node node set to SIGNAL, said after the lock is released when it is the precursor of node will wake the current thread, then the current thread can be at ease to sleep
* 3, call shouldParkAfterFailedAcquire (), because the default waitStatus of precursor node is not equal to the SIGNAL, so the precursor node will be set to SIGNAL, but pay attention to when return the result is false, If the lock is acquired successfully, the head node is pointed to the current node, and the head node has been discarded before. If the fetch fails, parkAndCheckInterrupt() is called to actually put the thread to sleep
ParkAndCheckInterrupt () calls locksupport.park () to sleep the current thread and block the client. Note the key point here: When the dormant thread is awakened, it needs to run the for loop again to compete for the lock resources through tryAcquire(). If the contention succeeds, the thread will exit the for loop, and if the contention fails, the thread will enter the hibernation state again
*
* Queue threads are woken up from head to tail. Only one thread in the Queue is woken up at a time. Why is there a race? This is because only one thread is awakened from the Queue, but if another thread is not in the Queue, it will compete with the thread awakened from the Queue for lock resources. This shows the characteristics of unfair locking: The thread that applies for the lock resource later may apply for the lock resource before the thread that applies for the lock resource first.
* Why?
* For performance reasons, if the thread that claims the lock immediately acquires the lock, avoiding subsequent Node creation, Node addition, etc., while the thread that wakes up from the Queue does not claim the lock but simply goes back to sleep. It's much cheaper, and it allows them to compete for lock resources so that the Queue doesn't starve to death
* /
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
//1. Obtain the precursor node of the current node
final Node p = node.predecessor();
//2. Check whether the precursor node is a head node.
// a. The predecessor node now occupies the lock
// b. The successor node is an empty node and has released the lock. Node now has the opportunity to acquire the lock. Call tryAcquire again to try to acquire the lock, the source code has been analyzed before
if (p == head && tryAcquire(arg)) {
setHead(node); //3. Set the new head after the lock is set.
p.next = null; // help GC
failed = false;
return interrupted; //4. Return whether the whole process of fetching is interrupted; If the whole process is interrupted, THEN I end up with a selfInterrupt, because the outside function might need to know if the whole process was interrupted
}
/ / shouldParkAfterFailedAcquire (p, node) whether you need to return the current thread hanging, if you need to call the parkAndCheckInterrupt () for the current thread to sleep
if (shouldParkAfterFailedAcquire(p, node) &&
ParkAndCheckInterrupt ()) / / 6. ParkAndCheckInterrupt suspending the current thread, thread to block the call stack, the return value to determine whether the thread is interrupted by awakening
interrupted = true;
}
} finally {
If (failed)//7
cancelAcquire(node); //8. Cancel Node (CANCELLED first)
}
}
private final boolean parkAndCheckInterrupt() {
// Use LockSupport's park method to suspend the current thread until it is woken up.
LockSupport.park(this);
return Thread.interrupted();
}
Copy the codeReentrantLock acquires lock resources unfairly. The process of fair and unfair lock is basically the same, the only difference is that the lock logic in tryAcquire() is different as follows:
TryAcquire () in FailSync gets lock logic:
protected final boolean tryAcquire(int acquires) {
final Thread current = Thread.currentThread();
int c = getState();
if (c == 0) {
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 codeWhen the lock resource is available (state=0) and there is no thread waiting for the lock resource in the Queue, the cas operation will set the state from 0 to 1, indicating that the lock resource is successfully applied. Otherwise, the lock resource will be added to the end of the Queue. Compare nonfairTryAcquire() with nonfairTryAcquire(). An unfair lock obtains lock resources through CAS as soon as it is determined that lock resources are available. A fair lock applies for lock resources only when the lock resources are available. Otherwise, the thread will be appended to the end of the Queue.
Reentrantlock. lock() : reentrantLock. lock() : reentrantLock. lock() : ReentrantLock also provides lockInterruptibly(), tryLock(), tryLock(long Timeout, TimeUnit Unit), and so on. Let me give you an overview.
Already. LockInterruptibly () : According to the previous source code analysis, if the thread does not obtain the Lock, it will sleep through locksupport.park (). When the Lock resource is released, other threads call lock.unpark () to wake up the dormant thread to compete for the Lock resource. Locksupport.park () can also be used to wake up a thread in interrupt mode, but interrupt lock is used to determine if it is interrupted to wake up, then directly throw an exception, while lock() can be used to directly compete for lock resources, which is the difference between them. Specific implementation to see the source code:
private void doAcquireInterruptibly(int arg)
throws InterruptedException {
final Node node = addWaiter(Node.EXCLUSIVE);
boolean failed = true;
try {
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return;
}
if (shouldParkAfterFailedAcquire(p, node) &&
ParkAndCheckInterrupt ())// Enter the blocking state, when the blocking is cleared, return true to indicate interrupt mode wake up
throw new InterruptedException(); // Interrupt wake up does not compete for lock resources, but instead throws an exception
}
} finally {
if (failed)
cancelAcquire(node);
}
Copy the codeAlready. TryLock () : If nonfairTryAcquire() is acquired, the lock will return true. If nonfairTryAcquire() is acquired, the lock will return true. If nonfairTryAcquire() is acquired, it will return false. Instead of adding to the Sync Queue and waiting on the blocking Queue.
Reentrantlock. tryLock(long timeout, TimeUnit Unit) : returns false if the lock cannot be obtained for a period of time
private boolean doAcquireNanos(int arg, long nanosTimeout)
throws InterruptedException {
if (nanosTimeout <= 0L)
return false;
final long deadline = System.nanoTime() + nanosTimeout; // The timeout period
// Join the Sync Queue. This is mainly for performance optimization. The following logic obtains the lock in the for wireless loop if the timeout is set to a long time
// It is a waste of CPU resources to continue the wireless loop, so it sleeps and waits for the precursor node to release the lock to wake up the thread
final Node node = addWaiter(Node.EXCLUSIVE);
boolean failed = true;
try {
for (;;) {
final Node p = node.predecessor();
if (p == head && tryAcquire(arg)) {
setHead(node);
p.next = null; // help GC
failed = false;
return true;
}
nanosTimeout = deadline - System.nanoTime();
If (nanosTimeout <= 0L)// If timeout, return false, indicating failure to acquire lock
return false;
if (shouldParkAfterFailedAcquire(p, node) &&
NanosTimeout > spinForTimeoutThreshold)// If the timeout is now greater than 1000 nanoseconds, the for loop will go into hibernation, otherwise the for loop will not stop, because the timeout is too short, there is no need to hibernate, hibernate is more expensive
LockSupport.parkNanos(this, nanosTimeout);
If (thread.interrupted ())// If (thread.interrupted ()) returns with an exception
throw new InterruptedException();
}
} finally {
if (failed)
cancelAcquire(node);
}
}
Copy the codeconclusion
According to the source code analysis of ReentrantLock, the core of the Lock mechanism is to operate the state attribute through CAS atom. State =0 means that the Lock resource is available. To obtain the Lock is to set the state from 0 to 1 through CAS atom operation. If state is greater than 0, the CAS operation fails. That is, the lock has been occupied and cannot be obtained. If the lock fails to be acquired, the processing logic varies depending on whether it is interruptible or timeout, but it is roughly as follows: 1. Encapsulate the thread that fails to acquire the Lock into Node. On the one hand, it is necessary to build a bidirectional queue, on the other hand, it is necessary to add additional status information to Node to control the Node. Will head to tail in the order from the Queue awakened threads (will skip CANCELLED tag node, because these nodes represent the thread is invalid), note that there will only be wake up a single thread, wake up the thread only said this thread lock competitive resources, but not in the need and the new application to the Queue of threads in the lock resources for competition, This is a feature of an unfair lock, which is designed primarily for performance. If the race is successful, exit the for loop and return, otherwise continue to sleep
Finally, through a rough flow chart, the overall implementation process has a clearer understanding.
Principle of lock release
Let’s examine the process of ReentrantLock releasing lock resources. Releasing locks does not distinguish between fair and unfair. The main job is to decrease the value of state. When state equals 0, the lock is released and other threads in the Queue are awakened to acquire the lock.
public void unlock() {
sync.release(1);
}
Copy the codeRelease () are implemented in AbstractQueuedSynchronizer,
/ * *
* Releases in exclusive mode. Implemented by unblocking one or
* more threads if {@link #tryRelease} returns true.
* This method can be used to implement method {@link Lock#unlock}.
*
* @param arg the release argument. This value is conveyed to
* {@link #tryRelease} but is otherwise uninterpreted and
* can represent anything you like.
* @return the value returned from {@link #tryRelease}
* /
public final boolean release(int arg) {
//tryRelease: try to release state, return true to indicate that lock resource release is complete,
if (tryRelease(arg)) {
Node h = head;
if (h ! = null && h.waitStatus ! = 0)
unparkSuccessor(h);
return true;
}
return false;
}
/ * *
* 1. Only the thread holding the lock will execute tryRelease(), so there are no multithreading issues involved, and cas is not required to ensure atomicity
Select * from thread 1 where state = 1 and state = 0
* Set the exclusiveOwnerThread to null, indicating that the current lock resource is free and not occupied by any thread
* 3, if state>0, the current release is not complete, return false
* /
protected final boolean tryRelease(int releases) {
int c = getState() - releases;
if (Thread.currentThread() ! = getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
If (c = = 0) {/ / only state = 0 means the lock is released to complete all the threads, the lock can be occupied by other threads, otherwise just released a number of reentrant, does not release the lock
free = true;
setExclusiveOwnerThread(null);
}
setState(c); // There is no concurrency problem, setState() is used instead of CAS operation to provide performance
return free;
}
Copy the codeIn-depth analysis
ReentrantLock acquires a lock and releases a lock. The more you look at the ReentrantLock, the more you’ll be amazed at the ingenuity and concurrency of Doug Lea and the IO model we’ll talk about later. There will still be great work by Doug Lea, if you don’t know about him, do a bit of research.
To understand the process does not necessarily mean that you are completely familiar with already, do you know what he is doing so, but you don’t know what considerations behind him to do so is, after all, concurrent programming is much higher than single-threaded programming complexity, it is hard to focus on all the threads run branch process, it is very easy to cause the root cause of the bug. We’ve already looked at the addWaiter() method above, but let’s take a closer look at it and hopefully get a better understanding of concurrent programming.
The addWaiter() method does what it does: encapsulate the unlocked thread as a Node and append it to the end of the Queue, which does not have a defined data structure but is a bidirectional linked list of dequeue and entrant operations simulated by head, tail, Next, and prev. Append the current node to the end of the bidirectional list
node.prev = pred;
If (compareAndSetTail(pred, node)) {//4
pred.next = node;
return node;
}
Copy the code1. Point the prev of the current node to the tail node. 2. Use the CAS atomic operation to point the tail pointer to the current node. 3. Point next of the previous tail node to the current node.
The schematic diagram is as follows:
If we reverse the three steps of the append node, first switch the tail node next to the current node, then switch the CAS atom tail pointer to the current node, then switch the cas atom tail pointer to the current node, then switch the cas atom tail pointer to the current node, then switch the cas atom tail pointer to the current node.
Tail next points to the current node, and then cas is executed to modify tail to the current node. Due to the concurrency problem of multiple threads, that is, multiple threads may apply for the lock resource at the same time. 1. After t1 thread changes next, t2 thread also changes next pointer, resulting in overwriting t1’s modified pointer. 2. If t1 thread succeeds in replacing tail with CAS, T2 thread fails to perform cas as well. T1 Because the CAS operation succeeded, the PREv pointing was modified
As you can see, the appended T1 nodes are problematic due to concurrency. Normally, Node1’s next should point to T1, but is overwritten by T2 nodes. Therefore, the 1 and 3 swap is problematic under concurrent conditions.
What if 1 and 2 were swapped, doing CAS first, then prev, and then next? First, use the CAS atomic operation to point tail to the current node, as shown in the following diagram:
The tail node is still an isolated node, prev and next are not pointed to yet, and there is no relation between the tail node and the other nodes. Then it is dangerous if other threads need to go through the bidirectional linked list, for example, the unparksucceeded () will be called when the lock is released.
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
// If the state is not met, start from the tail to find the node that meets the requirements and wake it up
Node s = node.next;
If (s = = null | | s. aitStatus > 0) {/ / s. aitStatus > 0 indicates the current thread has been CANCELLED, don't need to wake up
s = null;
// find the thread with waitStatus<=0 and assign it to s
for (Node t = tail; t ! = null && t ! = node; t = t.prev)
if (t.waitStatus <= 0)
s = t;
}
// Queue maintenance (first node replacement) is done by the consumer (fetch), that is, the moment the spin exit condition is met, the node will be set as the first node.
if (s ! = null)
LockSupport.unpark(s.thread);
}
Copy the codeThere is a possibility that there will be a process that looks up from tail to head. If this process is executed, there will obviously be a problem finding nodes from tail to head, so the process of 1 and 2 switching will also be problematic under concurrent conditions. The unparksucceeded () did not find the next effective node of head from head to tail but from tail to head in the opposite direction. Logic would surely have been faster to find the next effective node of head from head to tail, but why did it go the other way? If you only look at this code, you will never see the problem. For specific reasons, you can take part in the normal flow analysis below.
I will not give an example of the wrong order, but it is almost the same. Now let’s analyze why this order is not a problem in the source code under concurrent execution. Now assume that neither thread acquires a lock at the same time, and both threads need to append to the end of the Sync Queue as follows: Thread T1 sets prev to tail, thread T2 sets prev to tail, thread T1 sets prev to tail, thread T2 sets prev to tail, thread T1 sets prev to tail, thread T2 sets prev to tail, thread T1 sets prev to tail, thread T2 sets prev to tail. Multiple threads operate on Node1 at the same time, resulting in inconsistent state. If prev is set first, there is no multi-thread concurrency problem on the node of the thread itself when the object is operated, as shown in the diagram below:
The cas atomic operation on Node1 will be performed on both t1 and T2. If the cas atomic operation on Node1 is performed on t1, one thread will succeed. If the CAS atomic operation on Node1 is performed on T1, then the next operation on Node1 will be set to T1. As the CAS operation of T1 is successful, the CAS operation of T2 thread must fail. The schematic diagram is as follows:
The enq() method uses cas+ infinite loop to ensure that t2 nodes are appended to the end of Sync Queue. Each loop retrieves the latest tail, then points T2’s prev to the latest tail, then points tail to itself via cas, and finally points next from the previous tail node to T2. In this case, the latest tail is t1. Therefore, T2 nodes will be appended to T1 nodes, which can ensure that nodes can be added normally even under high concurrency, and there will be no inconsistent status as before, as shown in the diagram below:
/ * *
* 1. CAS is called in an infinite loop, which will eventually succeed in appending the current thread to the end of the queue even in high concurrency scenarios
* 2. If tail is null for the first time, a default node is initialized and head=tail points to that node
* 3. The second loop appends the current node to the end of the node created in 1
* /
private Node enq(final Node node) {
for (;;) {
Node t = tail;
If (t == null) {//1. If (t == null) {//1
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}
Copy the code
4. The search for the next effective node of the head (), not from head to tail but from tail to head, will be easier to explain if you can follow the logic of my analysis. Such as: T1 sets the prev to Node1 and then cas directs tail to T1. Then the Queue is structured as follows. If unparkprecursor () was executed, Node0 finds its successor to be Node1, and if Node1 is an invalid node, Node1 needs to continue to look for its rear drive node, but Node1’s next is not set and cannot be found, so it must look from tail to head.
Through an in-depth analysis of addWaiter, you’ll get a better sense of how difficult concurrent programming can be. It’s really important to be careful where you’re going, but Doug Lea’s clever design makes it easy.
At this point, a relatively complete process analysis of ReentrantLock is completed, and this section will be followed by some analysis of other Lock implementation classes and the underlying implementation mechanism of synchronized.