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

ReentrantLock Fair lock source code The first 0 More related articles in this article

  1. ReentrantLock The unfair lock source code analysis

    Analyzed in this paper ReentrantLock The corresponding Java Version is JDK8. Before reading this article , Readers should know what is CAS. The spin . because ReentrantLock There are many common codes in fair lock and unfair lock , This article will only focus on these two ...

  2. ReentrantLock Fair lock source code analysis

    ReentrantLock Source code analysis    Take fair lock source code analysis as an example : 1: data structure : maintain Sync References to objects :   private final Sync sync; Sync Object inheritance AQS,  Syn ...

  3. ReentrantLock Fair lock source analysis

    Analyzed in this paper ReentrantLock The corresponding Java Version is JDK8. Before reading this article , Readers should know what is CAS. The spin . Outline of this article 1.ReentrantLock Fair lock Introduction 2.AQS 3.lock Method ...

  4. ReentrantLock And synchronized The source code parsing

    One . Concept and implementation principle    stay JDK 1.5 Previously, the coordination mechanism of shared objects was synchronized and volatile, stay JDK 1.5 A new mechanism has been added in ReentrantLock, The birth of this mechanism did ...

  5. Java About ReentrantLock Get lock and release lock source tracking

    Through to ReentrantLock Get lock and release lock source tracking mainly want to further in-depth study AQS. remarks :AQS Medium waitStatus Status code meaning :

  6. ReentrantLock lock Source code analysis

    According to the following code analysis ReentrantLock  The process of acquiring and releasing locks ReentrantLock lock = new ReentrantLock(); lock.lock();// Gets the lock lock.u ...

  7. ReentrantLock And AQS Source code analysis

    ReentrantLock And AQS Source code analysis 1. The basic structure    Reentrant lock ReetrantLock,JDK 1.5 New class , The functions and synchronized Keywords are equivalent , But more than synchronized ...

  8. ReentrantLock and condition Source analyses ( Two )

    Reprint please indicate the source ... And then the last one ReentrantLock and condition Source analyses ( One ), This article revolves around condition One .condition Introduction to Here for comparison , introduce Object Two sides of a class ...

  9. JUC Source code analysis - Collection of articles ( Ten )LinkedTransferQueue

    JUC Source code analysis - Collection of articles ( Ten )LinkedTransferQueue LinkedTransferQueue(LTQ) comparison BlockingQueue Further more , The producer blocks until the element added to the queue ...

  10. JUC Source code analysis - Collection of articles ( Nine )SynchronousQueue

    JUC Source code analysis - Collection of articles ( Nine )SynchronousQueue SynchronousQueue Is a synchronous blocking queue , Each insert operation of it will wait for the corresponding removal operation of other threads , vice versa .SynchronousQu ...

Random recommendation

  1. JVM And PC register (Program Counter Register)

    Basic characteristics : The line number indicator of bytecode executed by the current thread . Java The virtual machine supports multiple threads to execute at the same time , Each thread has its own pc register . Anytime , A thread will only execute the code of one method , Called the current method of the thread , For non nativ ...

  2. GitHUb Problems encountered in code submission and solutions

    git The following error occurred when adding code : fatal: Unable to create 'F:/wamp/www/ThinkPhpStudy/.git/index.lock': File exists. If ...

  3. spring Source code analysis spring-jms Module details

    0 summary spring Provides a jms Integration Framework , This framework is like spring Integrate jdbc api equally , To simplify the jms api Use . jms It can be simply divided into two functional areas , The production and consumption of news .JmsTempl ...

  4. Sharepoint Website create custom navigation full record

    turn :http://tech.it168.com/a2009/1207/820/000000820524_all.shtml [IT168 Technical documentation ] In a Sharepoint You can create subwebs in a website , page ...

  5. poj 1008

    #include<iostream>#include<string> using namespace std;string hname[19] = { "pop&qu ...

  6. ( turn ) One a day linux command (27):linux chmod command

    scene : In the process of project deployment, it is often necessary to authorize different directories ! 1 brief introduction chmod Commands are used to change linux Access to system files or directories . Use it to control access to files or directories . There are two uses for this command . One is a text set containing letters and operator expressions ...

  7. Compare three CSS The preprocessor :Sass、LESS and Stylus( Next )

    5、 ... and .Mixins ( Mix in ) Mixins It's kind of like a function or a macro , When you have a certain period CSS When you often need to use multiple elements , You can share for these CSS Define a Mixin, Then you just need to quote these when you need them CSS place ...

  8. openstack-ocata- Image services 3

    One . Overview of image service Image services (glance) Enables users to discover . registration , And retrieve the virtual machine image . It provides a REST API, Enables you to query virtual machine image metadata and retrieve an actual image . Virtual machine images can be stored in different locations through the image service ...

  9. ansible Of tags

    perform ansible-playbook You can use --tags "tag1,tag2..." perhaps --skip-tags "tag1,tag2..." Specified for execution t ...

  10. solve log4j and self4j Log error Could NOT find resource [logback.groovy] And Could NOT find resource [logback-test.xml] problem

    Background of the event : my log4j and self4j According to the online configuration , Configuration worked , But the error reports are as follows : It makes me very depressed , So I found a big circle ........ Solution : In conclusion, it is :log4j.properties and logba ...