Last article AQS Series I: Source Code Analysis Unfair ReentrantLock We analyze the unfair implementation of ReentrantLock. In this article, we will continue to analyze the fair lock implementation of ReentrantLock (and the implementation of Condition).
Before that, we have to figure out where the "unfairness" is.
Why is it "unfair"
Well, I don't know.
So I compared the unfair and fair implementation of ReentrantLock, i.e. NonfairSync vs FairSync, and found that the difference was mainly in locking, or rather acquiring the lock link.
## Unfair access lock final boolean nonfairTryAcquire(int acquires) { ... if (c == 0) { if (compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } } ... } ## Fair access lock protected final boolean tryAcquire(int acquires) { ... if (!hasQueuedPredecessors() //### This is where the difference lies. && compareAndSetState(0, acquires)) { setExclusiveOwnerThread(current); return true; } ... }
Obviously, fair locks are more executed! hasQueuedPredecessors(), look at the logic of this method.
public final boolean hasQueuedPredecessors() { Node h, s; if ((h = head) != null) { ## h-head node if ((s = h.next) == null ... ) { ## s-2 node ... } if (s != null && s.thread != Thread.currentThread()) ##Check that node 2 binds threads and whether they are current threads return true; } return false; }
The hasQueuedPredecessors method returns true only if the node 2 is not empty and the bound thread is not the current thread.
Returning to ture means! HasQueued Predecessors () = false, not qualified to acquire locks (that is, no chance to perform compareAndSetState - try to modify state)
Conversely, only when there is no queue (the wireless process is executing), or no node 2 (cancel or temporary state), or when the bound thread of node 2 is the current thread, will the lock be attempted.
In the final analysis, the thread bound by Node 2 is the first waiting thread (the first thread that failed to acquire the lock), and the first waiting thread becomes the first thread eligible to attempt to acquire the lock under the operation of hasQueued Predecessors (). And that's fair!
So where is the "unfairness" without the unfair lock of hasQueuedPredecessors method?
Let's recall that during the add/unlock process, the location where the nonfairTryAcquire method is called is the answer.
public final void acquire(int arg) { if (!tryAcquire(arg) ### Location 1, try to get && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); } final boolean acquireQueued(final Node node, int arg) { boolean interrupted = false; ... for (;;) { final Node p = node.predecessor(); if (p == head && tryAcquire(arg)) { ### Location 2, try to get setHead(node); p.next = null; // help GC return interrupted; } if (shouldParkAfterFailedAcquire(p, node)) interrupted |= parkAndCheckInterrupt(); } ... }
In the above code, tryAcquire (unfair implementation calls nonfair TryAcquire) triggers at locations 1 and 2. Imagine the following scenario:
- Thread T-3 is executed and unlock is invoked; as thread T-2 is awakened, code at position 2 may be executed.
- At the same time, with the intervention of new thread T-1, the code at location 1 may also be executed.
Therefore, it is uncertain who can grab the lock in concurrency between threads T-2 and T-1.
- If thread T-2 executes first, T-1 fails at position 1 and subsequently blockages at the end of the queue.
- If thread T-1 executes first, T-2 fails at position 2 and faces another round of blocking, this situation is not so "fair" - the new thread T-1 preempts!
The principle is over, so how to build a fair ReentrantLock? The constructor can pass parameters:
public ReentrantLock(boolean fair) { sync = fair ? new FairSync() : new NonfairSync(); ## Input fair into true, construct fair lock }
Condition analysis
Use
ReentrantLock's unlocking process has been analyzed in detail, and if you use this tool frequently, you're certainly unfamiliar with the condition that spawned another big cafe.
If you don't say a word, first throw out demo: demo, demo, demo, demo, demo, demo, demo, demo, demo, demo, demo, demo, demo, demo, demo, demo.
static Lock lock = new ReentrantLock(); Condition condition = lock.newCondition();; public void doSomething(){ lock.lock(); System.out.println(String.format("%s Thread, get the lock",Thread.currentThread().getName())); try { System.out.println(String.format("%s Threads, await",Thread.currentThread().getName())); TimeUnit.SECONDS.sleep(2L); //Simulate time-consuming business logic execution condition.await(); //await System.out.println(String.format("%s Threads, await To be awakened",Thread.currentThread().getName())); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println(String.format("%s Thread, Business Execution Completed",Thread.currentThread().getName())); lock.unlock(); } public static void main(String[] args) throws InterruptedException { ReentrantLockTest test = new ReentrantLockTest(); int total = 1; while (total>0){ Thread t = new Thread(()->{ test.doSomething(); },"T-"+total); t.start(); TimeUnit.MILLISECONDS.sleep(200L); //Let sub-thread T-1 take the lead in acquiring locks lock.lock(); System.out.println(String.format("%s Thread, get the lock",Thread.currentThread().getName())); test.condition.signal(); System.out.println(String.format("%s Threads, signal",Thread.currentThread().getName())); lock.unlock(); total--; } }
Combining with the principle of unlocking, the demo execution process is analyzed.
- Artificial control lets the sub-thread T-1 acquire the lock first, and the main thread will try to acquire the lock after 200 ms. Of course, the main thread cannot acquire the lock because of the frantic execution of business logic that takes up to 2 seconds. (At sleep, the main thread should build a synchronization queue, and the main thread, as the bound thread of node 2, is ruthlessly blocked, as shown below)
- After 2s, thread T-1 worked out the hard business logic, but it was ambushed by condition.await().
- At this point, the thread main finds itself miraculously unblocked and magically acquires the lock. So the condition.signal() wakes up the thread T-1 after unlock.
- Thread T-1 wakes up at await and executes the remaining logic
The results of demo implementation can preliminarily prove the above analysis:
T-1 thread, get the lock T-1 thread, await main thread, get the lock main thread, signal T-1 thread, await is awakened T-1 Thread, Business Execution Completed
principle
constructor
Starting from the constructor:
public Condition newCondition() { return sync.newCondition(); } ## Sync class creates ConditionObject final ConditionObject newCondition() { return new ConditionObject(); }
ConditionObject is another internal class in AQS. Look at its properties:
## ConditionObject class private transient Node firstWaiter; private transient Node lastWaiter;
Feeling like AQS settings?
## Class AQS private transient volatile Node head; private transient volatile Node tail;
Let's make a bold guess. It's very likely that the synchronization queue will be built again in condition.
await()
Next comes the process of validating our guesses:
public final void await() throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); Node node = addConditionWaiter(); ## Create a waiting queue, node is the tail node. See [addConditionWaiter details] int savedState = fullyRelease(node); ## Reset state, returning the state value before reset. See [fully Release details] int interruptMode = 0; while (!isOnSyncQueue(node)) { ## Is it in the AQS synchronization queue? LockSupport.park(this); ## Nodes that are not in AQS synchronization queue block the current thread if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break; } if (acquireQueued(node, savedState) && interruptMode != THROW_IE) interruptMode = REINTERRUPT; if (node.nextWaiter != null) // clean up if cancelled unlinkCancelledWaiters(); if (interruptMode != 0) reportInterruptAfterWait(interruptMode); }
- Details of addConditionWaiter
private Node addConditionWaiter() { if (!isHeldExclusively()) ## Whether the current thread is the owner thread, if not, throw an exception -- this determines that await must be used after the lock() method throw new IllegalMonitorStateException(); Node t = lastWaiter; // If lastWaiter is cancelled, clean out. if (t != null && t.waitStatus != Node.CONDITION) { unlinkCancelledWaiters(); t = lastWaiter; } Node node = new Node(Node.CONDITION); ## Create a new node, assign waitStatus=CONDITION=-2 atomically, and bind the current thread to the node ## The node is placed at the end of the queue as the tail node if (t == null) firstWaiter = node; else t.nextWaiter = node; lastWaiter = node; return node; }
- Fully Release Details
final int fullyRelease(Node node) { try { int savedState = getState(); ## Get the current state if (release(savedState)) return savedState; throw new IllegalMonitorStateException(); } catch (Throwable t) { node.waitStatus = Node.CANCELLED; throw t; } } public final boolean release(int arg) { if (tryRelease(arg)) { ## Trying to Clean 0 state Node h = head; ## Here the head is not empty, unpark thread main, return true 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()) ## Current thread validation, if the current thread!= owner, throw an exception throw new IllegalMonitorStateException(); boolean free = false; if (c == 0) { ## If the state clears 0, the colleague clears the owner thread, return true free = true; setExclusiveOwnerThread(null); } setState(c); return free; }
With previous experience in analyzing ReentrantLock, condition code that is very similar to it should not be difficult to capture.
Here we draw the changes of nodes and key attributes before and after fullyRelease(node) execution in await method:
On the right side of the graph (when the await method executes to LockSupport.park(this), thread T-1 is blocked and thread main is unblocked.
It's easy to see from the figure above that our previous guess is correct: the await method builds a synchronous queue, but this time the head and tail pointers are in the ConditionObject class.
signal()
Let's look at what the signal method does:
public final void signal() { if (!isHeldExclusively()) ## As in the await() method, verify the owner thread first throw new IllegalMonitorStateException(); Node first = firstWaiter; if (first != null) doSignal(first); } private void doSignal(Node first) { do { if ( (firstWaiter = first.nextWaiter) == null) lastWaiter = null; first.nextWaiter = null; } while (!transferForSignal(first) ## condition header node delivery && (first = firstWaiter) != null); } final boolean transferForSignal(Node node) { if (!node.compareAndSetWaitStatus(Node.CONDITION, 0)) return false; Node p = enq(node); ## Move the ConditionObject header node to the end of the AQS queue. See [enq details] int ws = p.waitStatus; if (ws > 0 || !p.compareAndSetWaitStatus(ws, Node.SIGNAL)) ## Canceling or modifying waitStatus fails before unpark is done, where unpark does not trigger LockSupport.unpark(node.thread); return true; }
- enq details
private Node enq(Node node) { for (;;) { Node oldTail = tail; if (oldTail != null) { node.setPrevRelaxed(oldTail); ## Join the node and become the new tail node of the AQS queue if (compareAndSetTail(oldTail, node)) { oldTail.next = node; return oldTail; } } else { initializeSyncQueue(); ## Initialize AQS queue } } }
The most magic of signal s is the enq(node) method, which completes the node transfer, the condition queue head node - > AQS queue tail node.
Observe the changes in the structure and attributes of the objects generated by the signal ing method as follows:
Observation shows that after signal execution, node transfer has been completed, thread T-1 is still blocked, while ConditionObject has completed its historical mission.
When does thread T-1 unblock? In fact, this part of the last article has been analyzed, is our old friend unlock().
The difference is that after the thread T-1 is waked up, the following logic of await is executed:
public final void await() throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); Node node = addConditionWaiter(); int savedState = fullyRelease(node); int interruptMode = 0; while (!isOnSyncQueue(node)) { ## 2. Next time the node is in the AQS queue, return true and jump out of the loop LockSupport.park(this); ## Thread T-1 awakens here if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) break; } if (acquireQueued(node, savedState) ## 3. Retrieve the lock again && interruptMode != THROW_IE) interruptMode = REINTERRUPT; if (node.nextWaiter != null) // clean up if cancelled unlinkCancelledWaiters(); if (interruptMode != 0) reportInterruptAfterWait(interruptMode); }
Epilogue
So far, we have learned about the source implementation of ReentrantLock's main logic (fair, unfair, condition). The next article in this series will go to the next copy, Count Down Latch. Please look forward to it!