One, foreword

Java thread synchronization has two ways: synchronized keyword and Lock Lock mechanism. Among them, AQS queue is the underlying support of Lock Lock to achieve fair Lock.

AQS source code for lock.lock() implementation

2.1 AQS + Internal Node

2.1.1 Schematic diagram of AQS structure

First we will look at the structure of the AQS class diagram



As can be seen from the class structure diagram of AQS,

  1. AbstractQueuedSynchronizer is the parent of the AbstractOwnableSynchronizer;
  2. AbstractQueuedSynchronizer subclass is Sync, then through inheritance Sync got FairSync fair Lock and UnfaiSync not fair Lock, so the AQS is fairness Lock Lock Lock mechanism underlying support.

2.1.2 Internal Node Classes

From the structure diagram above, we can see that this class maintains a Node inner class, so we look at the Node source code below, mainly used to implement the queue we mentioned above.

Static final class Node {static final Node SHARED = new Node(); Static final Node EXCLUSIVE = null; Canceled static final int CANCELLED = 1; // Canceled static final int CANCELLED = 1; Static final int Signal = -1; static final int signal = -1; Static final int condition = -1; static final int condition = -1; static final int condition = -1; Propagate static final int propagate = -3; // propagate static final int propagate = -3; /* * SIGNAL: The successor of this node is (or will be) blocked (via park), so the current node must release its successor when it releases or cancels. To avoid contention, acquire methods must first indicate that they need a signal, then retry atomic acquisition, and block when that fails. * * CANCELLED: This object was CANCELLED due to timeout or interruption. The node doesn't leave this state. In particular, threads that cancel nodes do not block again. * * CONDITION: This object is currently in the CONDITION queue. It will not be used as a synchronization queue node until transmission, at which point the state will be set to 0. PROPAGATE: The shared release should PROPAGATE to other nodes. Set this in doReleaseShared (for the head node only) to ensure propagation continues even if other operations have intervened. * * 0: none of the above */ volatile int waitStatus; // The last Node is volatile Node prev; // Volatile Node next; // Volatile Thread Thread; // Next waiting Node Node nextWaiter; Final Boolean isShared() {return nextWaiter == SHARED; Final Node Predecessor () throws NullPointerException {Node p = prev; if (p == null) throw new NullPointerException(); else return p; } // Call Node(Thread Thread, Node mode) {this.nextwaiter = mode; this.thread = thread; } //Condition calls Node(Thread Thread, int waitStatus) {this.waitStatus = waitStatus; this.thread = thread; }}Copy the code

About waitStatus:

  1. SIGNAL=-1: The successor of this node is (or will be) blocked (via park), so the current node must release its successor when it releases or cancellations. To avoid contention, acquire methods must first indicate that they need a signal, then retry atomic acquisition, and block when that fails.
  2. CANCELLED=1: This object was CANCELLED due to timeout or interruption. The node doesn’t leave this state. In particular, threads that cancel nodes do not block again.
  3. CONDITION=-2: This object is currently in the conditional queue. It will not be used as a synchronization queue node until transmission, at which point the state will be set to 0.
  4. PROPAGATE=-3: The released share should PROPAGATE to other nodes. Set this in doReleaseShared (for the head node only) to ensure propagation continues even if other operations have intervened.
  5. WaitStatus =0: none of the above

According to the above code, we know that AQS queue is a queue of double linked list implementation, and each node contains prev pointer and next pointer, as shown in the following figure:

AQS internal class Node answer: AQS is essentially a non-cyclic bidirectional linked list (also called queue), so it is composed of nodes, namely Node, following lock(), unlock() await(), signal()/signalAll().

Question: What information should be stored in the Node inner class of the AQS class? Answer: Thread stores the value of the Node. Because the nodes of the AQS queue store threads, the value type is thread. Finally, nextWaiter is also a Node type, indicating the next waiting Node. WaitStatus wait state, said the current node SHARED | EXCLUSIVE representation is an EXCLUSIVE or SHARED.

volatile int waitStatus; // The current Node wait state volatile Node prev; // Volatile Node next; // Next node volatile Thread Thread; // Node nextWaiter; Static final Node SHARED = new Node(); static final Node EXCLUSIVE = null;Copy the code

Remember the six attributes of a Node (share/exclusive counts as one) and read the source code more easily

  1. The attributes used in the synchronization queue (in this article: lock, unlock) include: Next prev thread waitStatus, so synchronous queue is bidirectional circular linked list, involving the class variables AbstractQueuedSynchronizer class of the head and tail, respectively to synchronization in the queue head node and end node.
  2. The attributes used in the wait queue (next post: block, wake up) include: The nextWaiter thread waitStatus is a one-way non-circular linked list. The variables firstWaiter and lastWaiter in ConditionObject refer to the head node and the last node in the queue, respectively.
  3. The AQS queue is a working queue, a synchronous queue, and a non-circular bidirectional queue. When the head tail is used, the AQS queue is said to be established. A single thread does not use the head tail, so the AQS queue is not established.
  4. Wait queue, non-cyclic unidirectional queue: When firstWaiter lastWaiter is used, the wait queue is set up.
  5. Lock () and unlock() are operation synchronization queues: Lock () encapsulates the thread in the node (thread nextWaiter waitStatus is used by the node) and places it in the synchronization queue (AQS queue). Unlock () removes the thread from the synchronization queue to indicate that the thread is finished.
  6. Await () and signal() are await queues: await() encapsulates the thread inside the node (where the property used by the node is Thread prev Next waitStatus), puts it inside the wait queue, and signal() takes the element out of the wait queue.

2.2 Fair locking Requires work queues: The Lock () method in FairSync (emphasis)

2.2.1 The lock method has only one thread

2.2.1.1 Overall route diagram (locking for the first time + locking for the second ~n times)

The lock method has only one thread (ps: there is no AQS queue yet, head==tail), as shown in the following figure:

The correct way to look at this picture for an explanation of the above is:

  1. The methods involved in the chart above include acquire(), tryAcquire(), hasqueuedEstablishes ();
  2. For acquire(), we call tryAcquire() directly, passing in 1.
  3. For the tryAcquire() method, there is only one thread, A, which must be locked by CAS when it first enters the tryAcquire() method and set itself as the exclusive thread (if code). Modify state directly with setState(), incrementing by one at a time because the argument acquires is 1.
  4. For the HasqueuedToraise () method, which determines whether the AQS work queue is established, h==t, so it is not established, returns false.
  5. Overall process: For the same thread A, for the only diamond judgment box in the figure, CAS should lock when entering for the first time (if judge the latter half) and set itself as the exclusive thread (if code segment); The second to NTH entry is reentrant lock, direct entry, no CAS operation and set the exclusive lock, directly through setState() to change the state value, each increment can be one, this is the overall process, thread A’s overall process, divided into two ball cases.

Fair locking process (when there is only one thread) :

  1. Call tryAcquire directly and check if state is equal to 0
  2. The first time hasqueuedToraise () must pass (return false and reverse true), change the state value to 1 through the CAS operation, and then true, return true to indicate that the lock was successful, and the lock was completed.
  3. For thread A to lock for the 2nd ~n times, the value is not 0, indicating that it is not the first time to lock, and the lock is A re-entrant lock. At this time, add 1 to the original state value through CAS operation, and return true again, indicating that the lock is successful, and the lock is completed.

Tip1: Note that the queue for AQS is not created at this time. Tip2: setExclusiveOwnerThread (current); Tip4: FairSync lock() ¶ tip4: FairSync lock() ¶ Source code generally beautiful naming, naming can help clarify ideas, such as lock() is to lock, acquire() is to try to acquire() lock, acquireQueued() is to get queue

2.2.1.2 Important method: tryAcquire() source code parsing

Use lock.lock() for only one thread A; The most important method to acquire A lock is tryAcquire, which is the method to separate thread A, the first time to lock and non-first time to lock, source code out to tell:

Protected final Boolean tryAcquire(int acquires) {tryAcquire(int acquires) {tryAcquire(int acquires) {tryAcquire(int acquires); ** Final Thread current = thread.currentThread (); int c = getState(); If (c == 0) {// If (c == 0) { 1, Hasqueuedtoraise () &&/ ** ** compareAndSetState(0, acquires)) {// **1, Once hasqueuedToraise () returns false and withtrue, this cas must pass ** setExclusiveOwnerThread(current); ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** } else if (current == getExclusiveOwnerThread()) {int nexTC = c + acquires; if (nextc < 0) throw new Error("Maximum lock count exceeded"); setState(nextc); return true; **} return false; **} return false; **} return false; **} return false; / / * * 1, if not for the first time, also is not reentrant lock, cannot access ways to lock, lock to yourself and it returns false, lock failure * *}Copy the code

2.2.1.3 Important method: HasqueuedProsper () source code analysis

public final boolean hasQueuedPredecessors() { Node t = tail; // Read fields in reverse initialization order Node h = head; Node s; return h ! = t && ((s = h.next) == null || s.thread ! = Thread.currentThread()); }Copy the code

Question: HasqueuedToraise () source parse? Answer:

  1. If h == t is true and both h and t are null or the same concrete node with no successors, the method returns false, indicating that the lock is to be obtained by tryLock(). In this case, the first node, tail == head == null. Key: if the class variable head==tail, which means there are no nodes or only one node, so there must be no precursor nodes, the method returns false. =tail At least two nodes

  2. If h! =t is true (at least two nodes), and head.next == null, the method returns true. Under what circumstances h! =t and h.ext ==null?? Other threads may appear when they are enqueued for the first time. Tail =null,head=newNode,head. Next =null Key: head=newNode; tail=null; tail=null; And t.n ext = node; Head. Next =null.

  3. If h! =t (head and tail are not the same, at least two nodes), head. Next! = null, (true && (false | |)) is to judge the head. The next is the current thread, if the current thread (true && (false | | false)), the method returns false, the key: by acquiring a lock to lock; If not for the current thread (true && (false | | true)) returns true, the key: said the running thread is not the current the current, needs to wait for. (The head node is the node that acquired the lock, but at any moment the head node may occupy the lock, or it may release the lock(unlock()). The thread corresponding to the unblocked head.next node may need to attempt to acquire the lock at any moment.)

Actually, hasqueuedToraise returns true and waits only a certain amount of time to do it. If this method returns true, it means that a thread requested the lock earlier than the current thread and therefore needs to wait for the precursor thread to acquire and release the lock before continuing to acquire it.)

Question: What is the HasqueuedToraise () method used for? Answer:

  1. 24. Significance of hasqueuedToraise () method: If this method returns true, it means that a thread has requested to acquire the lock earlier than the current thread. Therefore, it needs to wait for the thread to acquire and release the lock before continuing to acquire the lock. Because it is a fair lock, it should follow the queue.
  2. The call to the hasqueued24 () method and the significance of the return: The HasqueuedToraise () method is only called and executed inside the tryAcquire() method. Hasqueuedtoraise () returns false to indicate that it is trying to establish a lock by acquiring it, and that no precursor node has requested the lock, If the value is true, the lock does not need to be acquired.

Question: How do I access the HasqueuedToraise () method? 24, Lock () -> acquire() -> tryAcquire() -> HasqueuedToraise ()

2.2.2 There are two threads in lock method

2.2.2.1 Overall route diagram (Thread A locked + Thread B locked)

If there are two threads in the AQS queue, as shown in the figure below:

Two points to note in the figure above:

  1. On the left, thread A obtains the lock first, and then thread B tries to obtain the lock, but thread B must wait until thread A releases the lock, before obtaining the lock successfully, can only block, i.e. in the source code for loop;
  2. Comparing the two figures carefully, the last change is that the value of waitStatus on the previous node of thread B is changed from 0 to -1.

An explanation of the above picture:

Thread A is unlocked, thread B is unlocked, thread A is unlocked, thread A is unlocked, thread B is unlocked, thread A is unlocked, thread B is unlocked, thread A is unlocked, thread B is unlocked. Thread A has been unlocked, and thread B has successfully locked the CAS. Procedure

2.2.2.2 The first case: When thread B enters, thread A is not unlocked in an infinite loop

First, establish AQS queue

Let’s assume that thread A has acquired the lock directly, but thread A has not unlocked the lock, thread B will acquire the lock, then execute the tryAcquire() method, thread A is not unlocked. So the tryAcquire() method will simply return false (state! The addWaiter(node.exclusive) method is then called (addWaiter() is new: The AQS queue will be initialized in the enq(node) method, and the current node will be inserted into the AQS queue using tail insertion method. The AQS queue is shown in the figure below:

For the current AQS queue explanation:

  1. Now the AQS queue is created
  2. Where thread=null means no threads are stored and waitStatus=0 means nothing
  3. If waitStatus=0, waitStatus=0, waitStatus=0, waitStatus=0, waitStatus=0

Second, call the enq() method in the addWaiter() method to create a new AQS queue

The method to complete the AQS queue is the enq() method called in addWaiter(), and look at the addWaiter() and enq() methods

Private Node addWaiter(Node mode) {// ** ** private Node addWaiter(Node mode) {// ** * ** Node Node = new Node(thread.currentThread (), mode); NextWaiter Node pred = tail; nextWaiter Node pred = tail; // Tail ==null if (pred! = null) { node.prev = pred; If (compareAndSetTail(pred, node)) {if (compareAndSetTail(pred, node)) {pred. Next = node; // Next is set to this node // ** Set the prev of the new Node to the last Node, reset the pointer to the tail variable, and set the next of the last Node to the new Node. ** return Node; }} enq(node); // Return value has no receiver, but the queue has a new return node; } private Node enq(final Node Node) {for (; ;) {// **1, ** t = tail; If (t == null) {// Must initialize ** ** if (compareAndSetHead(new Node()))) // **for+if (cas) = head; **} else {node.prev = t; // create a new node and set it to the head node. // **1, head tail, Node t = tail; If (compareAndSetTail(t, node)) {// If (compareAndSetTail(t, node)) {// If (compareAndSetTail(t, node)) Change tail from t to node, so node is the last node. // The end node points to the parameter node, and the head node points to t. Set the prev of the parameter node to t and the next of the tail node to node. Set the prev of the parameter node to t and the next of the tail node to node. Very simple), finally queue two elements t and node** return t; // return the header t}}}}Copy the code

Tip: CompareAndSetTail (t, node) // Change tail from t to node. CompareAndSetHead (t, node) // Set head from t to node. CompareAndSetState (0, acquires) // Set the state class variable from 0 to 1, cas guarantees security

Third, acquireQueued () method takes addWaiter () returns a value, called shouldParkAfterFailedAcquire () method, the modified AQS queue node waitStatus value from 0 to 1

The addWaiter() method returns the current Node and then calls the acquireQueued(addWaiter(Node.exclusive), arg) method (tip: Returns the tailest node just created in the addWaiter() method as an argument to the acquireQueued method, arg being 1, passed in). There is an infinite loop in this method, since thread A did not release the lock (tryAcquire()) will return false (state! = 0, nor is it a reentrant lock)), performs shouldParkAfterFailedAcquire (p, node) (p said thread B nodes on a node, p = node. Predecessor (); It’s the one on the tail node, node is the node of thread B, Else compareAndSetWaitStatus(pred, ws, waitStatus) ¶ The first time you enter this method will change the waitStatus of the last node on thread B to -1 The Node SIGNAL);) , and return false. The AQS queue looks like this:



The last change is that the value of waitStatus on the last node of thread B is changed from 0 to -1.

  1. First shouldParkAfterFailedAcquire () method will thread B node in a node waitStatus value to 1, then return false. At this time, the AQS work queue: Thread ==null on the head node indicates that no thread is stored, and waitStatus=-1 indicates that threads on the following nodes need to be released. The tail node thread= thread B indicates that thread B is stored, and waitStatus=0 indicates that nothing is stored.

  2. For the second time in shouldParkAfterFailedAcquire () method, will return true (if (ws = = Node. SIGNAL) return true) ParkAndCheckInterrupt () (locksupport.park (this);) Thread B is going to be park here. (1) Until thread A is unlocked, the second case can be regarded as the execution after the first case.

2.2.2.3 The second case: Thread A has been unlocked in an infinite loop

All of the above is if thread A is not unlocked, if thread A is unlocked in an infinite loop. If so, execute tryAcquire() directly, set the current thread B to the exclusive thread, and set state to 1 via CAS. If successful, return true. The lock is successfully added. At this point the code in the if judgment is executed. When setHead(node) is executed, the AQS queue is shown below:

if (p == head && tryAcquire(arg)) { setHead(node); // node is the addWaiter tail node, p.next = null; // help GC set next to null failed = false; CancelAcquire: false cancelAcquire: return interrupted; // false } private void setHead(Node node) { head = node; // Head points to the addWaiter tail node node.thread = null; Thread =null node.prev =null; // Prev ==null; // Prev ==nullCopy the code

At this point, the original thread B will exit the queue (because B is about to execute) and will always maintain an AQS queue with thread null in the header.

2.2.3 There are three threads in the lock method

There are three thread cases in the Lock method, as shown below:

The case for three threads is similar to that for two threads, i.e. the thread on the next node of the head node is always the thread on the next node of the head node, because the lock is fair.

The NonfairSync class lock() method does not require a queue for an unfair lock.

Unfair locking process:

  1. Unfair locks will come and try to lock directly;
  2. If the lock succeeds, the code in the thread is executed directly.
  3. If the lock is not successful, go directly to the logic of fair lock.

2.4 Other lock methods: ReentrantLock class tryLock() method

The tryLock() method is similar to the lock() method. The tryLock() method returns false if an attempt is unsuccessful.

public boolean tryLock() {
    return sync.nonfairTryAcquire(1);
}

final boolean nonfairTryAcquire(int acquires) {
    final Thread current = Thread.currentThread();
    int c = getState();
    if (c == 0) {
        if (compareAndSetState(0, acquires)) {
            setExclusiveOwnerThread(current);
            return true;
        }
    }
    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;
}
Copy the code

ReentrantLock (tryLock(long timeout, TimeUnit unit));

  1. TryLock (long timeout, TimeUnit Unit); if the tryLock is not obtained within this time, return false, indicating that the lock failed. TryAcquire (arg) (int arg, long nanosTimeout) (int arg, long nanosTimeout) The tryLock(long timeout, TimeUnit Unit) method returns true.

  2. If tryAcquire(ARg) returns false, doAcquireNanos(ARG, nanosTimeout) will be executed to insert the current node into the AQS queue. If the AQS queue is not initialized, it will be initialized directly. Puts the current node into the end node. At this time, it will judge whether the last node of the current node is the head node or not, and try locking again. If it succeeds, it will return true; if it fails, the thread of the current node will park the specified time directly, and wake up when the time is up. Attempts to acquire the lock again return true on success and false on failure. This method can respond directly to an interrupt.

Details:

public boolean tryLock(long timeout, TimeUnit unit) throws InterruptedException { return sync.tryAcquireNanos(1, unit.toNanos(timeout)); } public final boolean tryAcquireNanos(int arg, long nanosTimeout) throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); / / here will respond immediately interrupt return tryAcquire (arg) | | doAcquireNanos (arg, nanosTimeout); } private boolean doAcquireNanos(int arg, long nanosTimeout) throws InterruptedException { if (nanosTimeout <= 0L) return false; final long deadline = System.nanoTime() + nanosTimeout; 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) return false; if (shouldParkAfterFailedAcquire(p, node) && nanosTimeout > spinForTimeoutThreshold) LockSupport.parkNanos(this, nanosTimeout); // Park specifies the time if (thread.interrupted ()) throw new InterruptedException(); }} finally {if (failed) cancelAcquire(node); }}Copy the code

2.6 Other lock methods: The ReentrantLock class’s lockInterruptibly() method

The difference between lockInterruptibly and Lock:

  1. The lockInterruptibly will immediately respond to the interrupt: And the threads in the park will also wake up interruptibly, since it returns true, raising an exception and responding to the interrupt.
  2. Lock will not respond to interrupt until the thread is finished executing: the reason is that the thread in Park does not throw an exception after being woken up by the interrupt, but only sets the interrupt flag to true. It will respond to the interrupt of the object after obtaining the lock and completing execution.

LockInterruptibly will immediately respond to interrupts

public void lockInterruptibly() throws InterruptedException { sync.acquireInterruptibly(1); } public final void acquireInterruptibly(int arg) throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); if (! tryAcquire(arg)) doAcquireInterruptibly(arg); } 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()) throw new InterruptedException(); }} finally {if (failed) cancelAcquire(node); }}Copy the code

A lock will not respond to an interrupt until the thread is finished executing.

final void lock() { acquire(1); } public final void acquire(int arg) { if (! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); } final boolean acquireQueued(final Node node, int arg) { boolean failed = true; try { boolean interrupted = false; for (;;) { final Node p = node.predecessor(); if (p == head && tryAcquire(arg)) { setHead(node); p.next = null; // help GC failed = false; return interrupted; } if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) interrupted = true; Interrupt =true}} finally {if (failed) cancelAcquire(node); }}Copy the code

AQS source code for lock.unlock() implementation

Now that we’re done, let’s look at the process of unlocking, which is the unlock() method of the ReentrantLock class.

3.1 Overall Process for Unlocking a device

3.2 Functions involved in unlocking: UNLOCK ()-> Release() ->tryRelease() + Unlock in three cases

Unlock ()->release()->tryRelease()

public void unlock() { sync.release(1); } public final boolean release(int arg) { if (tryRelease(arg)) { Node h = head; if (h ! = null && h.waitStatus ! = 0) unparkSuccessor(h); return true; } 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) { free = true; setExclusiveOwnerThread(null); } setState(c); return free; }Copy the code

There are three cases of thread unlocking:

  1. The current thread is not in the AQS queue, call tryRelease(). If the current thread is not a reentrant lock (that is, if(c==0) is true), the current thread exclusive flag is removed directly, and the state value is changed to 0 by CAS. If the current thread has reentrant locks (i.e., if(c! =0) is false), unlock once, state is reduced by 1, return true if state is equal to 0. The account is unlocked successfully.

  2. There is only one header in the AQS queue, so tryRelease() returns the same result as above. This returns true, which goes into the current if, and determines whether the header is null and the value of waitStatus in the header is zero. In this case, head is not null, but waitState is equal to 0. If is not true, unpark will not be executed. Returns true. The account is unlocked successfully.

  3. There is more than one header in the AQS queue and there are other nodes, so tryRelease() returns the same result as above. This returns true, which goes into the current if, and determines whether the header is null and the value of waitStatus in the header is zero. Head is not equal to null, but waitState is equal to -1. If this is true, unpark will be executed. The unpark method will unpark the next node of the head node. Then, if the current node is in the cancelled state, the unpark method will start from the last node and find the next node of the current node that is not in the cancelled state. This will also return true. The account is unlocked successfully.

Important functions: unparksucceeded () (to be called in release())

Private void unparksucceeded (Node Node) {// The head of the queue is succeeded by int ws = node.waitstatus; If (ws < 0) compareAndSetWaitStatus(node, ws, 0); // Set ws to 0. Node s = node.next; / / to find a job queue if the back of the head of a node (s = = null | | s. aitStatus > 0) {/ / head behind this node is empty, or waitStatus greater than 0 s = null; // If waitStatus is greater than 0, set the Node after head to null for (Node t = tail; t ! = null && t ! = node; If (t.waitStatus <= 0) // If (t.waitStatus <= 0, record this t to s, S = t; s = t; } if (s ! = null) // unpark after head is not empty, locksupport-unpark (s.tuhread); }Copy the code

Q: How does the second if judge the three cases if? = null && h.waitStatus ! = 0)? Answer:

  1. If there is no AQS queue, head must be null, return true;
  2. In the second case, there are AQS queues but only one node in the synchronous queue, head is not null, but the only node is both the head node and the tail node, all h.waitStatus == 0, if the condition is not met, return true;
  3. The third case, if there is an AQS queue but there is more than one node in the synchronous queue, head is not null and the head node and the tail node are different nodes, so H. waitstatus ==-1, satisfying the second if judgment, is the unparkprecursor (H); Then return true;

Summary: Although the return is true and the unlock is successful, the internal logic is different.

Two important questions:

  1. Question: Why do I need to synchronize queue AQS? A: A synchronous queue is an internal data structure for a lock fair lock. An unfair lock does not require a synchronous queue.
  2. Question: Why is a synchronous queue acyclic, or not a acyclic singly linked list? Answer: In a fair lock, lock.lock() is inserted using a tail insert method. However, when you call lock.unlock(), the head node is the node that has successfully acquired the synchronization state, and the thread on the head node releases the synchronization state, it will wake up other subsequent nodes, s. Threads on subsequent nodes wake up and need to check whether their precursor node is the head node, and if so, try to obtain synchronization status. Therefore, in order to enable the successor node to obtain its precursor node, the synchronous queue is set as a bidirectional linked list, while the wait queue does not have such a requirement, it is a single linked list.

ReentrantLock: Lock () and unlock()

Interview question: How does lock implement fair lock and unlock (because synchronized cannot implement fair lock

4.1 Understand the basic element Node Node of AQS first

AQS internal class Node answer: AQS is essentially a non-cyclic bidirectional linked list (also called queue), so it is composed of nodes, namely Node, following lock(), unlock() await(), signal()/signalAll().

Question: What information should be stored in the Node inner class of the AQS class? Answer: Thread stores the value of the Node. Because the nodes of the AQS queue store threads, the value type is thread. Finally, nextWaiter is also a Node type, indicating the next waiting Node. WaitStatus wait state, said the current node SHARED | EXCLUSIVE representation is an EXCLUSIVE or SHARED.

volatile int waitStatus; // The current Node wait state volatile Node prev; // Volatile Node next; // Next node volatile Thread Thread; // Node nextWaiter; Static final Node SHARED = new Node(); static final Node EXCLUSIVE = null;Copy the code

Remember the six attributes of a Node (share/exclusive counts as one) and read the source code more easily

  1. The attributes used in the synchronization queue (in this article: lock, unlock) include: Next prev thread waitStatus, so synchronous queue is bidirectional circular linked list, involving the class variables AbstractQueuedSynchronizer class of the head and tail, respectively to synchronization in the queue head node and end node.
  2. The attributes used in the wait queue (next post: block, wake up) include: The nextWaiter thread waitStatus is a one-way non-circular linked list. The variables firstWaiter and lastWaiter in ConditionObject refer to the head node and the last node in the queue, respectively.
  3. The AQS queue is a working queue, a synchronous queue, and a non-circular bidirectional queue. When the head tail is used, the AQS queue is said to be established. A single thread does not use the head tail, so the AQS queue is not established.
  4. Wait queue, non-cyclic unidirectional queue: When firstWaiter lastWaiter is used, the wait queue is set up.
  5. Lock () and unlock() are operation synchronization queues: Lock () encapsulates the thread in the node (thread nextWaiter waitStatus is used by the node) and places it in the synchronization queue (AQS queue). Unlock () removes the thread from the synchronization queue to indicate that the thread is finished.
  6. Await () and signal() are await queues: await() encapsulates the thread inside the node (where the property used by the node is Thread prev Next waitStatus), puts it inside the wait queue, and signal() takes the element out of the wait queue.

Question: why is responsible for synchronizing queue head and tail in AbstractQueuedSynchronizer class, but is responsible for the waiting queue firstWaiter and lastWaiter in ConditionObject class?

Answer:

  1. Lock (), lock.unlock(), and ReentrantLock (AQS). So is responsible for synchronizing queue head and tail in AbstractQueuedSynchronizer class;
  2. Thread blocking and awakening are achieved via the ReentrantLock class object lock.newCondition(), condition reference refers to this object, and condition.await() condition.signal(), So the “firstWaiter” and “lastWaiter” queues are in ConditionObject.

4.2 Fair Lock Lock

4.2.1 Single-thread locking process

4.2.1.1 Overall Route Diagram (Locking for the first time + Locking for the second to n times)

Fair locking process (when there is only one thread) :

  1. Call tryAcquire directly and check if state is equal to 0
  2. The first time hasqueuedToraise () must pass (return false and reverse true), change the state value to 1 through the CAS operation, and then true, return true to indicate that the lock was successful, and the lock was completed.
  3. For thread A to lock for the 2nd ~n times, the value is not 0, indicating that it is not the first time to lock, and the lock is A re-entrant lock. At this time, add 1 to the original state value through CAS operation, and return true again, indicating that the lock is successful, and the lock is completed.

Tip1: Note that the queue for AQS is not created at this time. Tip2: setExclusiveOwnerThread (current); // Set the current node to exclusive tip3: see FairSync lock() for tip4: Source code generally beautiful naming, naming can help clarify ideas, such as lock() is to lock, acquire() is to try to acquire() lock, acquireQueued() is to get queue

4.2.1.2 Important method: tryAcquire() source code parsing

Use lock.lock() for only one thread A; The most important method to acquire A lock is tryAcquire, which is the method to separate thread A, the first time to lock and non-first time to lock, source code out to tell:

Protected final Boolean tryAcquire(int acquires) {tryAcquire(int acquires) {tryAcquire(int acquires) {tryAcquire(int acquires); ** Final Thread current = thread.currentThread (); int c = getState(); If (c == 0) {// If (c == 0) { 1, Hasqueuedtoraise () &&/ ** ** compareAndSetState(0, acquires)) {// **1, Once hasqueuedToraise () returns false and withtrue, this cas must pass ** setExclusiveOwnerThread(current); ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** } else if (current == getExclusiveOwnerThread()) {int nexTC = c + acquires; if (nextc < 0) throw new Error("Maximum lock count exceeded"); setState(nextc); return true; **} return false; **} return false; **} return false; **} return false; / / * * 1, if not for the first time, also is not reentrant lock, cannot access ways to lock, lock to yourself and it returns false, lock failure * *}Copy the code

4.2.1.3 Important method: HasqueuedProsper () source code parsing

Question: HasqueuedToraise () source parse? Answer:

  1. If h == t is true and both h and t are null or the same concrete node with no successors, the method returns false, indicating that the lock is to be obtained by tryLock(). In this case, the first node, tail == head == null. Key: if the class variable head==tail, which means there are no nodes or only one node, so there must be no precursor nodes, the method returns false. =tail At least two nodes

  2. If h! =t is true (at least two nodes), and head.next == null, the method returns true. Under what circumstances h! =t and h.ext ==null?? Other threads may appear when they are enqueued for the first time. Tail =null,head=newNode,head. Next =null Key: head=newNode; tail=null; tail=null; And t.n ext = node; Head. Next =null.

  3. If h! =t (head and tail are not the same, at least two nodes), head. Next! = null, (true && (false | |)) is to judge the head. The next is the current thread, if the current thread (true && (false | | false)), the method returns false, the key: by acquiring a lock to lock; If not for the current thread (true && (false | | true)) returns true, the key: said the running thread is not the current the current, needs to wait for. (The head node is the node that acquired the lock, but at any moment the head node may occupy the lock, or it may release the lock(unlock()). The thread corresponding to the unblocked head.next node may need to attempt to acquire the lock at any moment.)

Actually, hasqueuedToraise returns true and waits only a certain amount of time to do it. If this method returns true, it means that a thread requested the lock earlier than the current thread and therefore needs to wait for the precursor thread to acquire and release the lock before continuing to acquire it.)

Question: What is the HasqueuedToraise () method used for? Answer:

  1. 24. Significance of hasqueuedToraise () method: If this method returns true, it means that a thread has requested to acquire the lock earlier than the current thread. Therefore, it needs to wait for the thread to acquire and release the lock before continuing to acquire the lock. Because it is a fair lock, it should follow the queue.
  2. The call to the hasqueued24 () method and the significance of the return: The HasqueuedToraise () method is only called and executed inside the tryAcquire() method. Hasqueuedtoraise () returns false to indicate that it is trying to establish a lock by acquiring it, and that no precursor node has requested the lock, If the value is true, the lock does not need to be acquired.

Question: How do I access the HasqueuedToraise () method? 24, Lock () -> acquire() -> tryAcquire() -> HasqueuedToraise ()

4.2.2 Locking Two Threads (Thread A and Thread B)

4.2.2.1 The first case: When thread B enters, thread A is not unlocked in an infinite loop

First, establish AQS queue

Let’s assume that thread A has acquired the lock directly, but thread A has not unlocked the lock, thread B will acquire the lock, then execute the tryAcquire() method, thread A is not unlocked. So the tryAcquire() method will simply return false (state! The addWaiter(node.exclusive) method is then called (addWaiter() is new: The AQS queue will be initialized in the enq(node) method, and the current node will be inserted into the AQS queue using tail insertion method. The AQS queue is shown in the figure below:

For the current AQS queue explanation:

  1. Now the AQS queue is created
  2. Where thread=null means no threads are stored and waitStatus=0 means nothing
  3. If waitStatus=0, waitStatus=0, waitStatus=0, waitStatus=0, waitStatus=0

Second, call the enq() method in the addWaiter() method to create a new AQS queue

The method to complete the AQS queue is the enq() method called in addWaiter(), and look at the addWaiter() and enq() methods

Private Node addWaiter(Node mode) {// ** ** private Node addWaiter(Node mode) {// ** * ** Node Node = new Node(thread.currentThread (), mode); NextWaiter Node pred = tail; nextWaiter Node pred = tail; // Tail ==null if (pred! = null) { node.prev = pred; If (compareAndSetTail(pred, node)) {if (compareAndSetTail(pred, node)) {pred. Next = node; // Next is set to this node // ** Set the prev of the new Node to the last Node, reset the pointer to the tail variable, and set the next of the last Node to the new Node. ** return Node; }} enq(node); // Return value has no receiver, but the queue has a new return node; } private Node enq(final Node Node) {for (; ;) {// **1, ** t = tail; If (t == null) {// Must initialize ** ** if (compareAndSetHead(new Node()))) // **for+if (cas) = head; **} else {node.prev = t; // create a new node and set it to the head node. // **1, head tail, Node t = tail; If (compareAndSetTail(t, node)) {// If (compareAndSetTail(t, node)) {// If (compareAndSetTail(t, node)) Change tail from t to node, so node is the last node. // The end node points to the parameter node, and the head node points to t. Set the prev of the parameter node to t and the next of the tail node to node. Set the prev of the parameter node to t and the next of the tail node to node. Very simple), finally queue two elements t and node** return t; // return the header t}}}}Copy the code

Tip: CompareAndSetTail (t, node) // Change tail from t to node. CompareAndSetHead (t, node) // Set head from t to node. CompareAndSetState (0, acquires) // Set the state class variable from 0 to 1, cas guarantees security

Third, acquireQueued () method takes addWaiter () returns a value, called shouldParkAfterFailedAcquire () method, the modified AQS queue node waitStatus value from 0 to 1

The addWaiter() method returns the current Node and then calls the acquireQueued(addWaiter(Node.exclusive), arg) method (tip: Returns the tailest node just created in the addWaiter() method as an argument to the acquireQueued method, arg being 1, passed in). There is an infinite loop in this method, since thread A did not release the lock (tryAcquire()) will return false (state! = 0, nor is it a reentrant lock)), performs shouldParkAfterFailedAcquire (p, node) (p said thread B nodes on a node, p = node. Predecessor (); It’s the one on the tail node, node is the node of thread B, Else compareAndSetWaitStatus(pred, ws, waitStatus) ¶ The first time you enter this method will change the waitStatus of the last node on thread B to -1 The Node SIGNAL);) , and return false. The AQS queue looks like this:



The last change is that the value of waitStatus on the last node of thread B is changed from 0 to -1.

  1. First shouldParkAfterFailedAcquire () method will thread B node in a node waitStatus value to 1, then return false. At this time, the AQS work queue: Thread ==null on the head node indicates that no thread is stored, and waitStatus=-1 indicates that threads on the following nodes need to be released. The tail node thread= thread B indicates that thread B is stored, and waitStatus=0 indicates that nothing is stored.

  2. For the second time in shouldParkAfterFailedAcquire () method, will return true (if (ws = = Node. SIGNAL) return true) ParkAndCheckInterrupt () (locksupport.park (this);) Thread B is going to be park here. (1) Until thread A is unlocked, the second case can be regarded as the execution after the first case.

4.2.2.2 The second case: When thread B enters, thread A has been unlocked in an infinite loop

All of the above is if thread A is not unlocked, if thread A is unlocked in an infinite loop. If so, execute tryAcquire() directly, set the current thread B to the exclusive thread, and set state to 1 via CAS. If successful, return true. The lock is successfully added. At this point the code in the if judgment is executed. When setHead(node) is executed, the AQS queue is shown below:

if (p == head && tryAcquire(arg)) { setHead(node); // node is the addWaiter tail node, p.next = null; // help GC set next to null failed = false; CancelAcquire: false cancelAcquire: return interrupted; // false } private void setHead(Node node) { head = node; // Head points to the addWaiter tail node node.thread = null; Thread =null node.prev =null; // Prev ==null; // Prev ==nullCopy the code

At this point, the original thread B will exit the queue (because B is about to execute) and will always maintain an AQS queue with thread null in the header.

4.3 Lock.unlock () Unlocking process

There are three cases of thread unlocking:

  1. The current thread is not in the AQS queue, call tryRelease(). If the current thread is not a reentrant lock (that is, if(c==0) is true), the current thread exclusive flag is removed directly, and the state value is changed to 0 by CAS. If the current thread has reentrant locks (i.e., if(c! =0) is false), unlock once, state is reduced by 1, return true if state is equal to 0. The account is unlocked successfully.

  2. There is only one header in the AQS queue, so tryRelease() returns the same result as above. This returns true, which goes into the current if, and determines whether the header is null and the value of waitStatus in the header is zero. In this case, head is not null, but waitState is equal to 0. If is not true, unpark will not be executed. Returns true. The account is unlocked successfully.

  3. There is more than one header in the AQS queue and there are other nodes, so tryRelease() returns the same result as above. This returns true, which goes into the current if, and determines whether the header is null and the value of waitStatus in the header is zero. Head is not equal to null, but waitState is equal to -1. If this is true, unpark will be executed. The unpark method will unpark the next node of the head node. Then, if the current node is in the cancelled state, the unpark method will start from the last node and find the next node of the current node that is not in the cancelled state. This will also return true. The account is unlocked successfully.

Q: How does the second if judge the three cases if? = null && h.waitStatus ! = 0)? Answer:

  1. If there is no AQS queue, head must be null, return true;
  2. In the second case, there are AQS queues but only one node in the synchronous queue, head is not null, but the only node is both the head node and the tail node, all h.waitStatus == 0, if the condition is not met, return true;
  3. The third case, if there is an AQS queue but there is more than one node in the synchronous queue, head is not null and the head node and the tail node are different nodes, so H. waitstatus ==-1, satisfying the second if judgment, is the unparkprecursor (H); Then return true;

Summary: Although the return is true and the unlock is successful, the internal logic is different.

Two important questions:

  1. Question: Why do I need to synchronize queue AQS? A: A synchronous queue is an internal data structure for a lock fair lock. An unfair lock does not require a synchronous queue.
  2. Question: Why is a synchronous queue acyclic, or not a acyclic singly linked list? Answer: In a fair lock, lock.lock() is inserted using a tail insert method. However, when you call lock.unlock(), the head node is the node that has successfully acquired the synchronization state, and the thread on the head node releases the synchronization state, it will wake up other subsequent nodes, s. Threads on subsequent nodes wake up and need to check whether their precursor node is the head node, and if so, try to obtain synchronization status. Therefore, in order to enable the successor node to obtain its precursor node, the synchronous queue is set as a bidirectional linked list, while the wait queue does not have such a requirement, it is a single linked list.

Five, the summary

ReentrantLock lock(), unlock();

Play code every day, progress every day!!