Writing in the front

In the past, a detailed introduction to synchronized was made, including a detailed summary of the upgrade and optimization of lock. Synchronized and lock can ensure the atomicity of data under multi-threaded concurrency. Then how to achieve lock? This starts with AQS, without further ado

AQS

While the core of Concurrent programming in Java is the java.util.concurrent package, most synchronizer implementations in JUC are built around common basic behaviors such as wait queues, conditional queues, exclusive fetch, shared fetch, etc. And the behavior of the abstract is based on AbstractQueuedSynchronizer referred to as “AQS, AQS defines a set of synchronizer framework for multithreaded access to a Shared resource, is a reliance on state (state) of synchronizer. ReentrantLock is an application implementation based on the AQS framework. It is a synchronization method for concurrent access of threads in JDK. Its function is similar to that of synchronized, which is a mutex lock to ensure thread safety. And it has more features than synchronized, such as it supports manual locking and unlocking, support the fairness of locking. Use ReentrantLock:

ReentrantLock lock = new ReentrantLock(false); // False is an unfair lock, true is a fair lock lock.lock() // code logic lock.unlock() // unlockCopy the code

Source code analysis (source code based on fair locks)

The structural inheritance relationship of ReentrantLock.



You can see that the argument false is an unfair lock and true is a fair lock.



Fairly or unfairly, it inherits Sync.

Sync is integrated with AbstractQueuedSynchronizer, that is, to say the AQS.

Found AbstractQueuedSynchronizer there is a parent class AbstractOwnableSynchronizer.

Only in the AbstractOwnableSynchronizer a Thread object,This is the thread currently holding the lock.

That’s the inheritance of ReentrantLock.

AbstractQueuedSynchronizer class



In AbstractQueuedSynchronizer class, foundNode, head, tail, and stateFour properties.

  • Node: a queue based on a two-way linked list data structure. It is a FIFO first-in, first-out thread waiting queue. Fair locking is implemented based on this queue.
  • Head: indicates the head node.
  • Tail: indicates the tail node.
  • State: indicates the synchronization status. Reentrant is implemented based on this state, with each reentrant incrementing state by one and vice versa until it is zero.

Let’s look at the structure of Node.

Node is a bidirectional linked list queue, and therefore contains references to prev and NEXT, respectively, to the previous and next nodes of the current Node, and threads of the current Node. CANCELLED = 1, SIGNAL = -1, CONDITION = -2, PROPAGATE = -3 and initial state 0 (SIGNAL: wakeup, CANCELLED: Error, cancel, CONDITION, PROPAGATE). EXCLUSIVE and SHARED modes of a node are EXCLUSIVE and SHARED, respectively.

The lock method



The lock method, as you can see, is an abstract method of Sync, implemented in both fair and unfair locks.

The acquire method is called in lock.



The tryAcquire method returns true: the lock succeeded and false: the lock failed. If the lock fails, it is added to the wait queue (addWaiter(Node.exclusive)).



It is implemented in fair lock and unfair lock.

First of all,Gets the current thread and gets the state synchronization state(in AbstractQueuedSynchronizer class),If 0, indicating that no thread currently holds the lock. And then, throughhasQueuedPredecessors()Check whether other threads are queuing. If no thread is queuing, proceedCAS (i.e. compareAndSetState(0, acquires) method) operation, try to put the currentState Synchronization status changed to 1, the modification is successfulExclusiveOwnerThread Exclusive thread is the current thread“, the lock is successfully added. The diagram below.



If you get the state synchronization state,Is not zero, to determine whether the current thread is an exclusive thread, i.eWhether the current thread holds the lockIf so, yesState plus 1“, the lock is successfully added. The current status is shown in the following figure.



If the lock fails, addWaiter(Node.exclusive) is called to add to the wait queue.

First of all, can useCurrent thread and exclusive modeTo build an exclusive Node node. Tail is then assigned to pred. Since it is the first time to enter the queue, both tail and head are null, indicating that the current wait queue is empty. Therefore, if judgment is not performed, the queue will enterEnq (node) method. If the wait queue is not empty, the node is directly joined at the end of the if judgment.



This method shows that there may be multiple threads enqueuing at the same time, so the spin is inserted into the queue through the CAS operation until it succeeds. If the queue is empty, then Must initialize, creating an empty node with no thread references and head and tail pointing to the empty node. As shown in the figure below.



After the initialization of the wait queue is complete, the queue entry operation begins. There is also competition for team entry and CAS is also used. As shown in the figure below.



After entering the wait queue, the thread needs to be blocked, and the blocking logic is implemented in acquireQueued(addWaiter(Node.exclusive), ARG).



In this method, you see that the head head node is pulled out before blockingRun the tryAcquire(ARG) method again to grab the lockBecause thread blocking requires switching from user mode to kernel mode as much as possibleReduce the overhead of blocking.

1. If the lock is obtained, setHead(node) resets the head node and empties the next node of the head node.



2. If no lock is obtained, block logic is entered. Enter the shouldParkAfterFailedAcquire (p, node) method.

You can see that they’re going to pick it upWaitStatus of the precursor nodeTo judge if it isSIGNAL indicates that you can wake upIf the value is greater than 0, the current node is abnormal. Otherwise, use the CAS operation to try to change the initial state from 0 to SIGNAL. That is, the waitStatus of the precursor node is used to determine whether the current node can be awakened.



The first round to enter shouldParkAfterFailedAcquire (p, node), modify the state of the head, change into a SIGNAL, can be awakened. Second loop into shouldParkAfterFailedAcquire (p, node), to determine the ws = SIGNAL states can be awakened, return true. Before entering the parkAndCheckInterrupt() method.



Call locksupport.park () to block the thread.

Above is the whole source process of Lock.

A blocked thread is woken up in unlock.

Unlock method





Enter the tryRelease(ARG) method.



So you get state and you call unlock once and you subtract one. Until the state is 0, setExclusiveOwnerThread(NULL) sets the sovereign thread to NULL, updating the state. If the lock is released successfully, the waitStatus of the head node is determined not to be 0, and then the threads that were blocked at the next node are awakened.



First, it will judge if the ws state is less than 0, and use CAS to modify the WS state back to 0. Because, when the thread enters parkAndCheckInterrupt() while it is locked above, it blocks here and does not execute further. At the end of the unlock there is an unpark() operation that wakes up the thread to continue with the parkAndCheckInterrupt() method. In fair lock will be the first node queue to get the lock, but if is a fair lock, is not necessarily the first node queue to lock, and are likely to be other threads to lock, the first node queue at this time is still to be blocking operation, therefore, the ws state back to zero, in the first cycle to 1.

summary: in shouldParkAfterFailedAcquire (p, node) will head node waiteState instead of 1, because, thread holding the lock need to decide when releasing the lock head node waiteState! =0, if true, it will change waiteState to 0. To wake up T1, the first queued thread, T1 is woken up and ready to continue the loop and acquireQueued (in the method). Lock grab may fail (in an unfair lock scenario), at which point another thread T3 may hold the lock. T1 may be blocked again, and the node state of head goes through another two loops to change waiteState to -1.

The last

The above source code process is fair lock logic. The source logic of non – fair lock is similar to that of fair lock, and the difference lies only in the judgment of hasqueued24 () method, which is not repeated here.