Analysis of ReentrantLock based on AQS
I am a slow walker, but I never walk backwards. – Abraham Lincoln
“This is the second day of my participation in the First Challenge 2022.
Code case
public class ReentrantLockDemo {
static int counter = 0;
static ReentrantLock lock = new ReentrantLock();
public static void main(String[] args) {
new Thread(() -> {
for(int i = 0; i < 10; i++) {
lock.lock();
System.out.println("Thread name"+Thread.currentThread().getName()+"Lock...");
counter++;
System.out.println(counter);
lock.unlock();
System.out.println("Thread name"+Thread.currentThread().getName()+"Release lock........");
}
}).start();
new Thread(() -> {
for(int i = 0; i < 10; i++) {
lock.lock();
System.out.println("Thread name"+Thread.currentThread().getName()+"Lock");
counter++;
System.out.println(counter);
System.out.println("Thread name"+Thread.currentThread().getName()+"Release lock"); lock.unlock(); } }).start(); }}Copy the codeCode run result
Code interpretation
Two threads are opened, and only one thread at a time makes +1 to counter by locking to ensure data security
Source code analysis
Analysis constructor
The key code
We start by creating an object for ReentrantLock
ReentrantLock lock = new ReentrantLock();
Copy the codeWhat’s going on inside the constructor
public ReentrantLock(a) {
sync = new NonfairSync();
}
Copy the codeIn the constructor, there is a new instance of NonfailSync. What does this instance do? Click on the underlying code to see what this NonfailSync is
// Sync object for non-fair locks
static final class NonfairSync extends Sync {
final void lock(a) {
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1);
}
protected final boolean tryAcquire(int acquires) {
returnnonfairTryAcquire(acquires); }}Copy the codeNonfailSync inherits Sync and has been shown to be an unfair lock. Take a look at the lock() method and see what Sync does.
public class ReentrantLock implements Lock.java.io.Serializable {
private final Sync sync;
abstract static class Sync extends AbstractQueuedSynchronizer {
// ...}}Copy the codeSync is a property of ReentrantLock, and this property class implements the AQS class of ReentrantLock. In this case, an unfair lock is created by default when ReentrantLock is instantiated.
Analyze the locking code
lock.lock();
Copy the codeClick in and see
public void lock(a) {
sync.lock();
}
public ReentrantLock(a) {
sync = new NonfairSync();
}
static final class NonfairSync extends Sync {
final void lock(a) {
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1); }... Omit}Copy the codeRemember that sync is the one initialized in the constructor, which calls the lock method inside the unfair lock. Let’s examine the unfair lock lock
Unfair lock locks
static final class NonfairSync extends Sync {
final void lock(a) {
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
else
acquire(1); }... Omit}Copy the codeAnalyze the if module first
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
Copy the codeThere’s a CAS method in there and let’s go inside
protected final boolean compareAndSetState(int expect, int update) {
return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}
Copy the codeUnsafe is the underlying variable address, whose address is the address of the state variable, and the expected value is 0. If it’s 0, change it to 1. So what is this state thing? Up to find
public abstract class AbstractQueuedSynchronizer{
private static final Unsafe unsafe = Unsafe.getUnsafe();
private volatile int state;
private static final long stateOffset;
static {
try {
stateOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("state")); . Omit}catch (Exception ex) { throw newError(ex); }}}Copy the codeThe state variable volatile is the property of AQS to see if the lock was preempted. If it is not 0 then the lock was preempted. If it is 0 then the lock is likely to succeed. Therefore, the following CAS operation will go inside if if it succeeds
if (compareAndSetState(0.1))
setExclusiveOwnerThread(Thread.currentThread());
Copy the codeIf CAS is set successfully, set the current sovereign thread as its own, and go to this method
public abstract class AbstractOwnableSynchronizer{
private transient Thread exclusiveOwnerThread;
protected final void setExclusiveOwnerThread(Thread thread) { exclusiveOwnerThread = thread; }}Copy the codeThis class is AbstractOwnableSynchronizer AbstractQueuedSynchronizer this class inherits the parent class, through the exclusive thread, this method sets the current lock CAS failed to do then? Go the following way
acquire(1);
Copy the codeClick in and see
public final void acquire(int arg) {
if(! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); }Copy the codeTryAcquire (ARG) = tryAcquire(ARG);
static final class NonfairSync extends Sync {... omitprotected final boolean tryAcquire(int acquires) {
returnnonfairTryAcquire(acquires); }}Copy the codeThis method calls the tryAcquire method inside the unfair lock and acquires is passed in as 1. Enter the method nonfairTryAcquire, which is also implemented in AQS.
final boolean nonfairTryAcquire(int acquires) {
// Get the current thread
final Thread current = Thread.currentThread();
// Get the state variable
int c = getState();
// If state is 0, enter if
if (c == 0) {
// Use CAS again to set state to 1, if successful set the current exclusive thread to the current thread, return true
if (compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true; }}// If state is not 0, then check whether the currently added exclusive thread is the current thread to be locked, if so, then return state by 1
// true, proving that ReentrantLock is a ReentrantLock
else if (current == getExclusiveOwnerThread()) {
int nextc = c + acquires;
if (nextc < 0) // overflow
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
// Lock failure returns false
return false;
}
// Set the new state value
protected final void setState(int newState) {
state = newState;
}
Copy the codeAcquireQueued (addWaiter(Node.exclusive), arG) ¶ tryAcquire(arg) returns false
private Node addWaiter(Node mode) { // Node.EXCLUSIVE is NULL
// Create a NODE object
Node node = new Node(Thread.currentThread(), mode);
Node pred = tail;
if(pred ! =null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
}
Copy the codeStep by step, this addWaiter has a Node class in it and what does this Node class do? This Node is also a Node in AQS.
static final class Node {
// Share mode node
static final Node SHARED = new Node();
// Exclusive mode node
static final Node EXCLUSIVE = null;
// The thread has been canceled
static final int CANCELLED = 1;
/** waitStatus value to indicate successor's thread needs unparking */
// Subsequent threads need to be woken up
static final int SIGNAL = -1;
// indicates that the thread is waiting for a condition
static final int CONDITION = -2;
// The next fetch share should propagate unconditionally
static final int PROPAGATE = -3;
CANCELLED, SIGNAL, CONDITION, PROPAGATE
volatile int waitStatus;
// The precursor of the current node
volatile Node prev;
// The successor of the current node
volatile Node next;
// The thread currently put into Node
volatile Thread thread;
// Link the node to the next waiting condition
Node nextWaiter;
// The comment indicates Used by addWaiter
Node(Thread thread, Node mode) { // Used by addWaiter
this.nextWaiter = mode;
this.thread = thread;
}
// The Used by Condition comment already indicates that
Node(Thread thread, int waitStatus) { // Used by Condition
this.waitStatus = waitStatus;
this.thread = thread; }}Copy the codeHere we create a Node Node
Node node = new Node(Thread.currentThread(), mode); // mode = NULL
static final class Node {
Node(Thread thread, Node mode) { // Used by addWaiter
this.nextWaiter = mode;
this.thread = thread; }}Copy the codeFurther analysis defines a pred variable equal to tail, which is still null
Node pred = tail;
if(pred ! =null) {
node.prev = pred;
if (compareAndSetTail(pred, node)) {
pred.next = node;
return node;
}
}
enq(node);
return node;
Copy the codeThe enq(node) method is used because pred is null
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;
returnt; }}}}Copy the code(t==null); (t==null); (t==null); (t==null) The tail and head Pointers point to an empty node
// The head node of the queue
private transient volatile Node head;
private static final long headOffset;
static {
try {
headOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("head"));
} catch (Exception ex) { throw new Error(ex); }
}
compareAndSetHead(new Node()) // The tail pointer and the head pointer point to the empty Node
private final boolean compareAndSetHead(Node update) {
return unsafe.compareAndSwapObject(this, headOffset, null, update);
}
Copy the code
Since the loop does not break and exit, the next loop is executed, where t also points to tail, the empty node
But now the T pointer is not null so we go to else, and the node here is the node that we passed in, and its precursor points to the node that the T pointer points to
node.prev = t;
Copy the code
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
Copy the codeGo to compareAndSetTail(t, node)
private transient volatile Node tail;
private static final long tailOffset;
static {
try {
tailOffset = unsafe.objectFieldOffset
(AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
} catch (Exception ex) { throw newError(ex); }}private final boolean compareAndSetTail(Node expect, Node update) {
return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
}
Copy the codeThe tail pointer points to the newly enqueued node and, if set successfully, the successor node of the node to which the T pointer points points points to node
addWaiter(Node.EXCLUSIVEAcquireQueued (addWaiter(Node)EXCLUSIVE), arg) look into the 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); }}Copy the codeIn this aspect, there is another for loop, which defines a p pointer to the precursor node of the node that has just been enqueued
At this time, p pointer points to the empty head node, so P ==head is valid, so try to acquire lock tryAcquire(ARg) again, because it is possible that the thread that owned the lock before this time has released the lock and entered the method analyzed before again
protected final boolean tryAcquire(int acquires) {
return nonfairTryAcquire(acquires);
}
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 codeIf successful, lock away the following method
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
Copy the codeprivate void setHead(Node node) {
head = node;
node.thread = null;
node.prev = null;
}
Copy the codeAt this point, the head pointer points to the node, the node thread becomes null, and the node precursor points to null
p.next = null; // help GC
failed = false;
Copy the code
If the lock fails again, the graph, the queue, remains the same
if (shouldParkAfterFailedAcquire(p, node) &&
parkAndCheckInterrupt())
interrupted = true;
Copy the codeEnter the method see shouldParkAfterFailedAcquire (p, node)
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { // The p node is passed in
int ws = pred.waitStatus; // the waitStatus of p is null
if (ws == Node.SIGNAL)
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
// So go inside
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
Copy the codeNow the waitStatus of the p node is null, so it goes in here
private static final long waitStatusOffset;
static {
try {
waitStatusOffset = unsafe.objectFieldOffset
(Node.class.getDeclaredField("waitStatus"));
} catch (Exception ex) { throw new Error(ex); }
}
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
private static final boolean compareAndSetWaitStatus(Node node,int expect,int update) {
return unsafe.compareAndSwapInt(node, waitStatusOffset,expect, update);
}
Copy the codeSet waitStatus on the empty head node to SIGNAL. The current thread can only be suspended if the precursor node is SIGNAL
After entering the next loop, the lock is not acquired successfully, thenshouldParkAfterFailedAcquire(p, node)
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL) // After the last loop, the waitStatus of p has been set to Node.SIGNAL, so return true
return true;
if (ws > 0) {
do {
node.prev = pred = pred.prev;
} while (pred.waitStatus > 0);
pred.next = node;
} else {
compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
}
return false;
}
Copy the codeThen it goes into another method, parkAndCheckInterrupt()
private final boolean parkAndCheckInterrupt(a) {
LockSupport.park(this);
return Thread.interrupted();
}
Copy the codeThrough LockSupport. Park (this); Suspends the current thread
Analyze the lock release code
public void unlock(a) {
sync.release(1);
}
Copy the codeEnter the method below
public final boolean release(int arg) {
if (tryRelease(arg)) {
Node h = head;
if(h ! =null&& h.waitStatus ! =0)
unparkSuccessor(h);
return true;
}
return false;
}
Copy the codeEnter the tryRelease(ARG) method, and release the lock is partially fair and unfairly locked
protected final boolean tryRelease(int releases) {
int c = getState() - releases; // Count how many locks are left
if(Thread.currentThread() ! = getExclusiveOwnerThread())throw new IllegalMonitorStateException();
boolean free = false;
if (c == 0) { // Set the current exclusive thread to null if state is currently computed
free = true;
setExclusiveOwnerThread(null);
}
setState(c); // Set the state keyword
return free;
}
Copy the codeprotected final void setState(int newState) {
state = newState;
}
Copy the codeIf the lock is released successfully, define an H pointer to the head node of the queue
The head node is not empty and the waitStatus of the head node is -1 and not 0 so the unparksucceeded (h) was gone; methods
private void unparkSuccessor(Node node) {
int ws = node.waitStatus; // -1
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0); // Set the wait state of the head node to 0
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) // It wakes up the thread that was suspended using locksupport.park (this)
LockSupport.unpark(s.thread);
}
Copy the code
So where do you think the thread is suspended?
If it is woken up it will continue to acquire the lock, so the current diagram looks like this
After that, a p pointer is defined to point to the precursor node of the current node. Our current precursor node is the head node. If the lock is obtained successfully, then use the setHead(node) method
private void setHead(Node node) {
head = node;
node.thread = null;
node.prev = null;
}
Copy the code
At this point, there are no other nodes in the queue waiting for the lock except for an empty head node, and the lock release analysis is complete
