ReentrantLock Fair Locking Process
Test code
public static void main(String[] args) { ReentrantLock lock = new ReentrantLock(true); new Thread(() -> { System.out.println("11111 try get lock"); lock.lock(); System.out.println("11111"); try { TimeUnit.SECONDS.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); } lock.unlock(); }).start(); try { TimeUnit.MILLISECONDS.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } new Thread(() -> { System.out.println("22222 try get lock"); lock.lock(); System.out.println("22222"); try { TimeUnit.SECONDS.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); } lock.unlock(); }).start(); try { TimeUnit.MILLISECONDS.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } new Thread(() -> { System.out.println("33333 try get lock"); lock.lock(); System.out.println("33333"); try { TimeUnit.SECONDS.sleep(5); } catch (InterruptedException e) { e.printStackTrace(); } lock.unlock(); }).start(); try { TimeUnit.MILLISECONDS.sleep(100); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("main"); }
Here, three threads are opened, and three threads are executed in turn.
First Thread Locking
public final void acquire(int arg) { if (!tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }
Let's first look at the tryAcquire method in the code above.
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; }
Because it's the first thread that gets the lock, getState() gets the default value of state 0. Next, go to the first if block and look at the hasQueuedPredecessors method.
public final boolean hasQueuedPredecessors() { // The correctness of this depends on head being initialized // before tail and on head.next being accurate if the current // thread is first in queue. 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()); }
Similarly, because it is the first thread, tail and head are also the default initial values null, that is, h!= t in the return statement block will return false, and then back to the tryAcquire method. At this time, hasQueued Predecessors () is true, so immediately execute compareAndSetState(0, acquires), which means that the code will state. The value changes from 0 to 1, which means that the lock is successful, and then the current thread is placed as the exclusive owner. Then the lock is completed.
So what does the code in else if below mean? Yes, as you think, it's reentry logic.
So far, the lock logic of the first thread has been completed. Has it been found that there is no relationship with AQS at present?
Second Thread Locking
Undoubtedly, we still start with the tryAcquire method.
Without considering reentry, the getState() method is then executed with a value of 1. So the first if block will not go in. Similarly, the current exclusive thread is not what we call the second thread, so else if block will not go in, then return false directly. At this point! tryAcquire(arg) is true, then execute the acquireQueued (addWaiter (Node. EXCLUSIVE), Arg method.
Let's first look at the addWaiter(Node.EXCLUSIVE) method.
/** Marker to indicate a node is waiting in exclusive mode */ static final Node EXCLUSIVE = null; private Node addWaiter(Node mode) { Node node = new Node(Thread.currentThread(), mode); // Try the fast path of enq; backup to full enq on failure Node pred = tail; if (pred != null) { node.prev = pred; if (compareAndSetTail(pred, node)) { pred.next = node; return node; } } enq(node); return node; }
You can see that this method starts with a new Node, which initializes the Node to contain what we call a second thread. Note that AQS (AbstractQueued Synchronizer) is starting to be involved here, which is actually a linked list queue.
Back to the point, the code then gets the tail node of the queue, because the first thread does not involve the queue, so there is no idea that the tail node is null, so enq(node) method is executed.
The old rule, look at the code.
private Node enq(final Node node) { for (;;) { Node t = tail; if (t == null) { // Must initialize if (compareAndSetHead(new Node())) tail = head; } else { node.prev = t; if (compareAndSetTail(t, node)) { t.next = node; return t; } } } }
As soon as you come in, you see a dead cycle. The same access to the tail node, not to say, iron is null. Then if the code block is executed, a new empty node is assigned to the header node, and then the header node is assigned to the tail node (then the header and tail point to the same memory address). Then the first loop ends, because there is no return value, so the second loop is executed, when the tail node is no longer null (even if it is an empty node), then enter the else code block.
First, set the last node of the incoming node (the new node with the second thread in the previous method) as the empty node set in the first loop.
Then the incoming node is given to the tail node.
Finally, the next node of the empty node is set to the incoming node.
In this way, a two-way linked list with two nodes is formed.
It's a little hard to understand. Draw a picture of kindergarten level.
First, an abstract empty node is defined.
Then define the node that comes out of the addWaiter method new and give the name t2 node.
Then an empty node from enq method new is defined.
Finally, look at the relationships between nodes.
When tail = head is executed;
When executing Node t = tail;
When node.prev = t is executed;
When compareAndSetTail(t, node) is executed
When t.next = node is executed;
Finally, the AQS queue is formed.
The picture is finished, only for personal understanding.
Finally, look at the acquireQueued method.
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; } } finally { if (failed) cancelAcquire(node); } }
Once in, it's a dead cycle. The first loop if (p == head & tryAcquire (arg)) code, because we set the scenario, so the lock must fail, so look directly at the shouldParkAfterFailedAcquire method.
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { int ws = pred.waitStatus; if (ws == Node.SIGNAL) /* * This node has already set status asking a release * to signal it, so it can safely park. */ return true; if (ws > 0) { /* * Predecessor was cancelled. Skip over predecessors and * indicate retry. */ do { node.prev = pred = pred.prev; } while (pred.waitStatus > 0); pred.next = node; } else { /* * waitStatus must be 0 or PROPAGATE. Indicate that we * need a signal, but don't park yet. Caller will need to * retry to make sure it cannot acquire before parking. */ compareAndSetWaitStatus(pred, ws, Node.SIGNAL); } return false; }
At this point, waitStatus is 0 because it has not entered the thread waiting for the lock, so the code in the execution of else sets waitStatus to - 1. It is worth noting that the waitStatus of the previous node is operated here. Next, the second loop also fails to lock (because of the scenario we set), and then enters the shouldParkAfterFailedAcquire method again, when waitStatus has been set to - 1, so it returns true. Then the parkAndCheckInterrupt method is executed.
private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }
At this point, the native method park() is called directly to make the second thread enter the wait. Let's start with the third thread and see how the second thread successfully locks.
Third Thread Locking
Again, the scenario we set led to the failure of the third lock, so look directly at the addWaiter method.
private Node addWaiter(Node mode) { Node node = new Node(Thread.currentThread(), mode); // Try the fast path of enq; backup to full enq on failure Node pred = tail; if (pred != null) { node.prev = pred; if (compareAndSetTail(pred, node)) { pred.next = node; return node; } } enq(node); return node; }
At this point pred is definitely not null, so the last node of the third thread node is set as the second thread node, and then the third thread node is set as the tail node. Then look at the acquireQueued method.
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; } } finally { if (failed) cancelAcquire(node); } }
At this point, the p node is definitely not the head node (actually the second thread node), all of which execute the second if code block, and the logic behind it is the same as that of the second thread.
ReentrantLock Fair Lock Unlocking Process
The first thread unlocks
public final boolean release(int arg) { if (tryRelease(arg)) { Node h = head; if (h != null && h.waitStatus != 0) unparkSuccessor(h); return true; } return false; }
Look directly at the tryRelease method
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; }
Or, without considering reentry, getState equals 1, so c equals 0, null the exclusive thread, and finally zero the state.
Next, because the first thread has no half-price relationship with the AQS queue, it executes the unparkSuccessor method directly and returns true to complete the unlocking.
Then look at the unparkSuccessor method.
private void unparkSuccessor(Node node) { /* * If status is negative (i.e., possibly needing signal) try * to clear in anticipation of signalling. It is OK if this * fails or if status is changed by waiting thread. */ int ws = node.waitStatus; if (ws < 0) compareAndSetWaitStatus(node, ws, 0); /* * Thread to unpark is held in successor, which is normally * just the next node. But if cancelled or apparently null, * traverse backwards from tail to find the actual * non-cancelled successor. */ Node s = node.next; if (s == null || s.waitStatus > 0) { s = null; for (Node t = tail; t != null && t != node; t = t.prev) if (t.waitStatus <= 0) s = t; } if (s != null) LockSupport.unpark(s.thread); }
As mentioned above, when a thread enters an AQS queue, it sets waitStatus to - 1, so it enters the first if block, sets waitStatus to 0, and then gets the second node in the queue (that is, the second thread node) and wakes it up.
Then what happens when the second thread node is awakened?
Let's first look at the second thread entering the waiting code.
private final boolean parkAndCheckInterrupt() { LockSupport.park(this); return Thread.interrupted(); }
When the second thread is awakened, the return statement will be executed, which returns false because we do not interrupt the thread outside. Then proceed to loop if (p = head & tryAcquire (arg)) statement, satisfying P = head, and then look at the tryAcquire method.
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; }
At this point, because the first thread unlocks and sets state to 0, it enters the hasQueuedPredecessors() method.
public final boolean hasQueuedPredecessors() { // The correctness of this depends on head being initialized // before tail and on head.next being accurate if the current // thread is first in queue. 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()); }
Because there are three nodes in the queue (the first empty node, the second thread node and the third thread node), h!= t satisfies the condition, (s = h.next) == null also satisfies the condition, so it returns true, and then, in turn, executes the compareAndSetState(0, acquires) method, and sets the state to 1, meaning the first one. Two threads were successfully locked, and the exclusive threads were set as the second thread, and finally true was returned.
Continue to look up and execute the method in if (p = head & tryAcquire (arg)).
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; } } finally { if (failed) cancelAcquire(node); } }
Set the second thread node as the header node and the header node as the empty node.
private void setHead(Node node) { head = node; node.thread = null; node.prev = null; }
The second thread is locked.
The third thread locks the second thread the same. That's all.
ReentrantLock Unfair Locking Process
final void lock() { if (compareAndSetState(0, 1)) setExclusiveOwnerThread(Thread.currentThread()); else acquire(1); }
As you can see, an unfair lock is an attempt to change the state. Failed to follow the same path as fair lock. All, after the failure of unfair locking, we still queued honestly.