ReentrantLock 0
About ReentrantLock In fact, I have written this article , But the feeling of writing at that time was not very good , It was deleted , Then why write it again
I have nothing to do recently. I want to write a lock by myself , Then after coming out for a few days, it's either lost the thread or unlocked , And five or six paragraphs are just one cas Poor performance , I feel that it is thousands of miles away from what the master wrote
therefore ! I just want to study it again and see what the master wrote , This blog is also a note , This article is about ReentrantLock The fair lock of , Prepare to write twoorthree articles about ReentrantLock Just write in these two days !
This blog is completely personal , If there is something wrong, you are welcome to comment or send me a private message , I am very happy to accept your comments or suggestions
CAS
The first thing to know is ,ReentrantLock Is basically in java Implemented at the code level , And the most important thing is CAS compare and swap Compare and exchange
This operation can be seen as atomic , stay java You can use reflection to get Unsafe Class cas operation
public test() {
try {
Field unsafeField = Unsafe.class.getDeclaredField("theUnsafe");
if (!unsafeField.isAccessible()) {
unsafeField.setAccessible(true);
}
unsafe = (Unsafe) unsafeField.get(null);
} catch (NoSuchFieldException | IllegalAccessException e) {
e.printStackTrace();
}
}
Park
stay juc It's a bag LockSupport There are two methods in the class park and unpark These two are like wait and notify/notifyAll, But it's different , It can be temporarily understood as pausing threads and starting threads
See this blog for a detailed introduction : https://www.jianshu.com/p/da76b6ab56be
On how to use ReentrantLock Don't repeat it, just start looking at the code , I originally wanted to put the class diagram here , But my idea There seems to be a problem , You can open it yourself idea see ,ctrl+alt+u Open the class diagram
public static void main(String[] args) {
ReentrantLock lock = new ReentrantLock(true);
lock.lock();
lock.unlock();
}
Construction method
public ReentrantLock(boolean fair) {
sync = fair ? new FairSync() : new NonfairSync();
}
lock Method
public void lock() {
sync.lock();
}
Click inside to actually call FairSync Class lock() Method
final void lock() {
acquire(1);
}
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
tryAcuqire 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;
}
First, get the current thread , Then there's a getState, This method returns the current state of the lock
protected final int getState() {
return state;
}
hasQueuedPredecessors
First look Node, This Node Is an entity class that forms a bidirectional linked list , Several important attributes
volatile int waitStatus;
volatile Node prev;
volatile Node next;
volatile Thread thread;
Node nextWaiter;
waitStatus Store the status of the current node
prev Store the last node
next Store the next node
thread Storing threads
nextWaiter The translator is the next waiter , I understand it as serving the next node , Let's talk about it later
public final boolean hasQueuedPredecessors() {
Node t = tail;
Node h = head;
Node s;
return h != t &&
((s = h.next) == null || s.thread != Thread.currentThread());
}
There are two properties ,tail Caudal node ,head Head node , The next judgment is
The head node is not equal to the tail node also ( The next node of the head node is not equal to null perhaps The thread of the node after the head node is not equal to the current thread )
if (c == 0) {
if (!hasQueuedPredecessors() && compareAndSetState(0, acquires)) {
setExclusiveOwnerThread(current);
return true;
}
}
stay hasQueuedPredecessors() Then there is a cas, Modify the state of this lock
If it works , Call setExclusiveOwnerThread()
protected final void setExclusiveOwnerThread(Thread thread) {
exclusiveOwnerThread = thread;
}
Save the current thread to exclusiveOwnerThread Properties of the
So in the absence of conflict lock The method is over , Now let's assume that there is only one thread , Go through the locking process from the beginning
Try running
Let's follow the logic , From the very beginning lock() Method start , The front one is not written , Direct to acquire
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
Get into acquire
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 of this getState() Method gets properties state There is no other assignment operation for this attribute , Initialization is 0, Get into if(c==0)
After entering hasQueuedPredecessors()
public final boolean hasQueuedPredecessors() {
Node t = tail;
Node h = head;
Node s;
return h != t &&
((s = h.next) == null || s.thread != Thread.currentThread());
}
The first judgment is false 了 , because tail and head Have not been initialized , All are null, So it's equal to , Go straight back to false, And in the hasQueuedPredecessors() There is another method in front of ! Take instead true, Go straight into if Code block
Set the exclusiveOwnerThread After attribute return true, Out of the lock() Method , The locking method ends
exclusiveOwnerThread Property stores the current thread in possession of the lock
This is in the case of no thread acquisition lock conflict , If two threads come at the same time , Let's see 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;
}
Let's now assume that threads A Get lock , To execute the business code , Threads B Get into
getState() The obtained value is no longer 0 了 , Because the thread A After execution compareAndSetState(0, acquires) The change is getState() Method acquired state attribute
So enter else if (current == getExclusiveOwnerThread()) Hey, isn't this the way to get the thread that currently owns the lock , Yes
Then why is there such a judgment ,ReentrantLock Characteristics of Reentrant lock , What is a reentry lock ?: The same thread can acquire the same lock multiple times Take the following example
public class Test{
private static final ReentrantLock LOCK=new ReentrantLock(true);
public void a(){
LOCK.lock();
b();
LOCK.unlock();
}
public void b(){
LOCK.lock();
//xxxxxx
LOCK.unlock();
}
}
If there is no reentry lock feature , So is this method deadlocked ?, Suppose when we call a thread a When the method is used ..
a : Brother, I need a lock to execute your code
b : Then unlock it first
a : I have to call you before I can unlock
b : How can you call me if you don't unlock it
........
OK, back to the code , Is the state of holding the lock +1, Return to true, Because we are now B Threads , So this if Don't set up , return false
go back to acquire Method
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
because tryAcquire by false, Reverse and continue acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
addWaiter
First, let's look at the inside addWaiter Method Well , A parameter is passed Node.EXCLUSIVE
static final Node EXCLUSIVE = null;
This parameter is Node A property in a class
private Node addWaiter(Node mode) {
// Create a Node
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;
}
Node The parametric structure of is as follows
Node(Thread thread, Node mode) { // Used by addWaiter
this.nextWaiter = mode;
this.thread = thread;
}
The first is to create a Node node , Then judge if tail The node is not null, because A Thread completed tryAcquire Straight back ,tail and head All are null, therefore if Don't set up , Get into enq Method
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;
}
}
}
}
The first is to get tail, Then it's still for null, Because our assumption is two threads ,A The thread has gone to perform business , So go in first if
adopt cas To set the header node to a new Node() Be careful ! This is new new Of Node, After setting, set the head to the tail , Then the node relationship at this time is as follows
em?? We're here B Nodes are not added to the linked list , Don't worry. , Look at the one above for(;;)
At the next cycle tail It's equal to null Do you ? The answer is No
Then the head node is assigned to t, take B The previous setting of the node is t,cas Set up tail, After success t Node next Set to B node , return t ( The returned value is not actually received )
Very simple logic, too hard to say , Look at the picture , After the second time for The post node relationship is as follows
This enq The method is 100% sure that this node has been added , Because you can't get out of this method without adding it , Then the return addWaiter Method , After this enq Just one more sentence ,return node;
acquireQueued
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);
}
}
As soon as it comes in, it defines a failed It is used to remove the wrong node in the linked list if an error occurs , Let's not watch
The next one interrupted Whether the storage has been interrupted , Continue to find that it is still a for(;;), The first step is to carry out node.predecessor()
final Node predecessor() throws NullPointerException {
Node p = prev;
if (p == null)
throw new NullPointerException();
else
return p;
}
That is to get the next B The last of the nodes , That is, the thread is null The empty node of ( Be careful : No null, But an empty Node)
Judge whether the last node is head, If it is , Attempt to acquire lock , This tryAcquire() The method is the method at the beginning , So what does this step mean
ReentrantLock How to do it , If you have to create a linked list , be head Point to the Node The node is always an empty node
This sentence may not be too rigorous , But most of the time the linked list exists ,head It does point to an empty node
Continue to look at the code , Suppose now A The thread still hasn't finished the business code , No implementation unlock(), So let's move on to the next if,
if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt())
interrupted = true;
shouldParkAfterFailedAcquire
private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
int ws = pred.waitStatus;
if (ws == Node.SIGNAL)
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;
}
Not much code , But it's not easy to understand Start or get B The state of the last node on the node , That is, the empty node , Because we followed the code all the way , I don't see any empty nodes state Property has been modified , So it's still 0
Then the first judgment
static final int SIGNAL = -1; //Node Properties in a class
Whether the status of the empty node is -1, Obviously not ,if(ws>0) Will not enter , Go straight into else,cas Modify the status of empty nodes , Change it to -1, Then return
if (shouldParkAfterFailedAcquire(p, node) &&parkAndCheckInterrupt())
interrupted = true;
the reason being that && Blocking the latter method , So don't enter , Then this cycle ends , The outermost layer is a for(;;) So the next cycle starts
Let's assume that tryAcquire() The lock was not acquired , It's back in shouldParkAfterFailedAcquire
So the first one this time if We'll go in , Because the last cycle has already B The state of an empty node in front of the node is changed to -1 了 ,return true
go back to if Then enter parkAndCheckInterrupt Method
private final boolean parkAndCheckInterrupt() {
LockSupport.park(this);
return Thread.interrupted();
}
park, that B The thread stops here , Turn your eyes back to A Threads , It finally executes the business code , perform unlock
unlock
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;
}
Look at the first if Medium tryRelease
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;
}
The first thing is to lock the state -1, Because it re enters once +1, This is why lock How many times do I need to call unlock How many times , Because it is necessary to ensure that the state of the lock is 0
Then judge whether the locking thread and the unlocking thread are the same , It's not throwing an exception
boolean free = false; This is to identify whether the lock is no longer held , because A Thread called once lock, therefore if(c==0) establish
take free Change it to true Then set the thread that currently holds the lock to null, Set the status of the lock , return true, go back to release Method
Because back true, So to enter if, Judge head Node is not empty , And the state of the head node is not 0
Is the header node empty ? - No because B The node adds an empty node when initializing the linked list ( Again, it's not null! It's empty. Node node )
Then the state of the head node is 0 Do you ? - No We are executing for the second time shouldParkAfterFailedAcquire() Method has set the state of the header node to -1 了
So enter unparkSuccessor()
private void unparkSuccessor(Node node) {
int ws = node.waitStatus;
if (ws < 0)
compareAndSetWaitStatus(node, ws, 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)
LockSupport.unpark(s.thread);
}
obtain ,cas Assign the state of the head node to 0, Get the next node of the header node , That's our B node , that if (s == null || s.waitStatus > 0) by false, Go to the bottom if(s!=null)
Just a word unpark(s.thread)
Here we are ,AB All threads are finished
It's a bit long , Write again in these two days , Bye-bye
