package cn.daheww.demo.juc.reentrylock;
import sun.misc.Unsafe;
import java.lang.reflect.Field;
import java.util.concurrent.locks.LockSupport;
/**
* @author daheww
* @date 2022/7/7
*/
public class MiniReentryLock implements Lock {
/**
* What's the lock --> resources --> state
* 0 --> Unlocked
* >0 -> Lock
*/
private volatile int state;
/**
* Exclusive mode
* Only one thread can hold a lock at a time , Other threads will be blocked when they do not acquire the lock
*
* Thread that currently owns the lock （ Thread occupying lock ）
*/
private Thread exclusiveOwnerThread;
/**
* Two nodes are needed to maintain the blocking queue
* Head Point to the head node of the queue
* Tail Point to the end of the queue
*
* A special ：Head The thread corresponding to the node is the thread currently occupying the lock
*/
private Node head;
private Node tail;
/**
* Get the lock
* Suppose the current lock is occupied , Will block the caller thread , Until it grabs the lock
*
* Simulate fair lock
* --> first come , first served
*
* lock The process of
* scene 1. After the thread came in, it found , At present state == 0 --> Go ahead and grab the lock
* scene 2. After the thread came in, it found , At present state > 0 --> Queue the current thread
*/
@Override
public void lock() {
// The first time a lock is obtained , take state Set to 1
// The first n Second reentry , take state Set to n
acquire(1);
}
@Override
public void unlock() {
release(1);
}
private void release(int arg) {
// Conditions established ： This indicates that the thread has completely released the lock
if (tryRelease(arg)) {
// Blocking the queue , And the thread of sleeping , You should wake up a thread
// First of all, we need to know whether there is any waiting node --> head.next == null
Node head = this.head;
if (head.nx != null) {
// Fair lock , Wake up the head.nx node
unparkSuccessor(head);
}
}
}
private void unparkSuccessor(Node node) {
Node s = node.nx;
if (s != null && s.thread != null) {
LockSupport.unpark(s.thread);
}
}
/**
* If the lock is released successfully, it returns true
*/
private boolean tryRelease(int arg) {
int c = getState() - arg;
if (getExclusiveOwnerThread() != Thread.currentThread()) {
throw new RuntimeException("must get lock first");
}
// So if I go here , There is no concurrency , Only one thread will come here
// Conditions established , It indicates that the current thread holds lock The lock has been completely released
if (c == 0) {
this.exclusiveOwnerThread = null;
this.state = c;
return true;
} else {
this.state = c;
return false;
}
}
/**
* Compete for resources
* 1. Attempt to acquire lock . Success will occupy the lock , And return to
* 2. Failed to seize the lock , Block the current thread
* @param arg
*/
private void acquire(int arg) {
if (!tryAcquire(arg)) {
// Lock snatch failed
// step1. Encapsulate the current thread as node, Join the blocking queue
Node node = addWaiter();
// step2. Current thread park, Put the thread in a suspended state
acquireQueued(node, arg);
}
// Successful lock snatching
// 1. Got the lock
// 2. Re entered the lock
}
/**
* The attempt to grab the lock failed , What needs to be done ：
* 1. The current thread needs to be encapsulated as node, Join the blocking queue
* 2. The current thread needs to be park, Put the thread in a suspended state
*
* Wake up process ：
* 1. Check current node Is it head.next node
* head.next It is a thread with preemptive permission , Other node There is no preemptive permission
* 2. preemption ：
* success ：
* 1. Will the current node Set to node, Will the old head Out of the team , Go back to the business level
* 2. continue park Waiting to be awakened
*
* ----------------------------------------------
* 1. Logic added to the blocking queue addWaiter()
* 2. The logic of competing for resources acquireQueued()
*/
private void acquireQueued(Node node, int arg) {
// The current thread has been put into queue It's in
// Only current node The spin will not jump out until the lock is successfully obtained
for (; ; ) {
// Under what circumstances , At present node After being awakened, you can try to get the lock ？
// There is only one case , At present node yes head Successor node , That's the right
// It's not just first come, first served
Node pvNode = node.pv;
// Conditions 1：pvNode == head
// true --> Show the current node Have preemptive permission
// queue The first node in represents the thread currently executing the lock --> head Thread to point to
// head The following thread represents the thread that is queuing --> So only head.nx The node has the right to rob the lock
// Conditions 2：tryAcquire(arg)
// true --> The current thread has acquired the lock
//
if (pvNode == head && tryAcquire(arg)) {
// Entering this indicates that the current thread has successfully competed for the lock
// What to do ：
// 1. Set up current head For the current thread node
// 2. Assist the original object to leave the team
setHead(node);
pvNode.nx = null;
// Because I got the lock , So I return 了
return;
}
// Not at present head.nx node , Or the attempt to acquire the lock fails , At this time, you need to put the current thread park fall
System.out.println(" Threads ：" + Thread.currentThread().getName() + " Hang up ");
LockSupport.park();
// Until a thread does the current thread unPark operation , This thread will continue to execute
/*
So to summarize ,lock The logic of ：
1. Without a lock , If a thread calls lock Method , It will change lock Medium state value . here state The value will not be 0 了 .
Then other threads call lock When the method is used , You'll see this state Not for 0.
2. Then the thread will be encapsulated into a node node
3. Then I will try to compete for the lock , Do the final rescue work , If it can't be saved , Just park 了
--> The thread is right here lock Of lock() The method is blocked . The lock effect is achieved
--> All calls to this lock object lock Only one thread can continue to execute the method of , Then other threads will be blocked , Until this thread has done unlock operation
*/
System.out.println(" Threads ：" + Thread.currentThread().getName() + " Wake up the ");
// When to wake up by park The thread of ？--> unlock()
}
}
/**
* Queue the current thread
* Returns the... Corresponding to the current thread node node
*
* addWaiter After execution , Ensure that the current thread has been queued successfully
*/
private Node addWaiter() {
Node newNode = new Node(Thread.currentThread());
// How to join the team ？
// Case1. At present node Not the first one to join the team node, The queue already has waiting node 了
// 1. find newNode Of pv node
// 2. to update newNode.pvNode = pv node
// 3.CAS to update tail by newNode
// 4. to update pv node
Node pvNode = tail;
if (pvNode != null) {
newNode.pv = pvNode;
// Conditions established , Indicates that the current thread has been successfully queued
if (compareAndSetTail(pvNode, newNode)) {
pvNode.nx = newNode;
return newNode;
}
}
// Several cases of implementation here
// 1.tail == null The queue is empty
// 2.cas Set up current newNode by tail It failed --> Cycle into the team --> The spin
enq(newNode);
return newNode;
}
/**
* Spin into the team , Return only after success
* 1.tail == null The queue is empty
* 2.cas Set up current newNode by tail It failed
*/
private void enq(Node node) {
for (; ; ) {
// Case one ： The queue is empty
// --> The current thread is the first thread to preempt the lock ...
// The thread currently holding the lock , Nothing has been set node, So as the first driver node of this thread
// Need to wipe his ass
// Add a to the thread that currently holds the lock node As head node
// head The node represents the thread currently occupying the lock at any time
if (tail == null) {
// Conditions established ： It indicates that the current thread supplements the thread that currently holds the lock head Operation succeeded
if (compareAndSetHead(new Node())) {
tail = head;
// Be careful , There was no direct return , But will continue to spin
}
} else {
// There are already node 了 , It shows that this is an addition node The process of
// How to join the team ？
// 1. find newNode Of pv node --> Abreast of the times tail node
// 2. to update newNode.pvNode = pv node
// 3.CAS to update tail by newNode
// 4. to update pv node
Node pvNode = tail;
node.pv = pvNode;
// Conditions established , Indicates that the current thread has been successfully queued
if (compareAndSetTail(pvNode, node)) {
pvNode.nx = node;
return;
}
}
}
}
/**
* Attempt to acquire lock , It doesn't block threads
* true --> Seize success
* false --> Preemption failed
*/
private boolean tryAcquire(int arg) {
if (state == 0) {
// At present state by 0
// You can't grab the lock directly --> Fair lock --> first come , first served
// Conditions for a ：!hasQueuedPredecessors() ---> After taking the reverse, it is true, Indicates that there is no waiting thread in front of the current thread
// Condition 2 ：compareAndSetState(0, arg) -> Use cas Why ：lock Methods may be called by multiple threads
// true --> The current thread successfully grabs the lock
// (1) volatile --> state By volatile Modify the , So other threads can know at the first time that this value is not 0 了 --> The cache can be consistent
// (2) cas -------> state from 0 Turn into arg The operation of cas Realization , Used to ensure that only one thread can change state Value （0->arg） --> Only one thread can perform the next operation --> lock
// 1. If cas Variables of do not volatile Modification is meaningless ：
// because A The thread has changed state Value , however B Threads don't know
// （ visibility ,volatile Will make B The copy in the thread will expire immediately , Then get the latest state Value , here B In the thread workspace state The value is not 0 了 ）
// 2. If volatile Variables of do not cas To change its value , It doesn't make sense ：
//· step1.A Threads ,B Threads are all got state Copy information for , here state The value is 0
// step2.A The thread has changed state Value .B The thread is still writing , because state The value of , therefore B In the thread workspace state Value change , then B Keep writing .
// So all judgments state The value is 0 All threads can write successfully , And can perform subsequent operations after successful writing
// So want to use cas+volatile To ensure that only one thread can write this value successfully
// Ps. You can see , If the values that these threads want to write are the same , Write a few more times , But the result is consistent with writing only once
// cas+volatile The main thing is to control that the operation after a successful write will only be performed once , It's like a lock
if (!hasQueuedPredecessors() && compareAndSetState(0, arg)) {
// Successful lock snatching
// 1. take exclusiveOwnerThread Set as current thread
this.exclusiveOwnerThread = Thread.currentThread();
return true;
// Will not join any node, Return to true
// Next, the first thread that fails to compete will help create a node, Then perform subsequent operations
}
// There is a thread waiting in front of the current thread || Multiple threads are trying to acquire this lock together with the current thread , Then the current thread fails --> return false;
} else if (Thread.currentThread() == this.exclusiveOwnerThread) {
// Timing of execution ：
// 1. The current lock is occupied
// 2. The current thread is the lock thread
// There is no concurrency . Only the currently locked thread has permission to modify state
// Even if the same thread enters here many times , Set up state Value , Then they all use the same workspace
// There are no different workspaces , This value is different （ Because there is no cache ）
// Lock reentry process
int c = getState();
c += arg;
// TODO Cross border judgment
this.state = c;
return true;
}
// When will it return false？
// 1.cas Locking failed
// 2.state Greater than 0, And the current thread is not a lock thread
return false;
}
/**
* Whether there is a waiting thread in front of the current thread
* true --> There is a waiting thread in front of the current thread
* false -> There are no other waiting threads in front of the current thread
*
* Call chain
* lock --> acquire -> tryAcquire -> hasQueuedPredecessors(state The value is 0 when , At present lock It is in an ownerless state )
*
* When to return false？
* 1. The current queue is empty
* 2. The current thread is head.next node --> head.next Have the right to fight for at any time lock
*/
private boolean hasQueuedPredecessors() {
Node h = head;
Node t = tail;
Node s;
// Conditions for a ：h != t
// true --> The current queue already has node 了
// false -> h == t
// case1. h == t == null --> Not initialized yet queue
// case2. h == t == head
// The first thread that fails to acquire a lock will create a new one for the thread that currently holds the lock head node
// Condition 2 ：
// precondition ： Condition one holds
// Exclude several situations ：
// Conditions 2.1： In extreme cases --> The first thread that failed to acquire the lock , It will be added to the lock thread head node , Then join the team in spin
// step1.cas Set up tail succeed
// step2.head.next = node
// In the middle of these two steps , There are threads to check whether there are waiting threads in front
// This situation should return true： There has been a head.next The node , When other threads come here, they need to return true
// Conditions 2.2：
// precondition ：h.next No null
// true --> If the condition is true, it means that the current thread is the thread holding the lock
// false -> This indicates that the current thread is h.next The thread corresponding to the node , Need to return false. Then the thread will compete for the lock
return h != t && ((s = h.nx) == null || s.thread != Thread.currentThread());
}
private static final Unsafe UNSAFE;
private static final long STATE_OFFSET;
private static final long HEAD_OFFSET;
private static final long TAIL_OFFSET;
static {
try {
Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
UNSAFE = (Unsafe) f.get(null);
STATE_OFFSET = UNSAFE.objectFieldOffset(MiniReentryLock.class.getDeclaredField("state"));
HEAD_OFFSET = UNSAFE.objectFieldOffset(MiniReentryLock.class.getDeclaredField("head"));
TAIL_OFFSET = UNSAFE.objectFieldOffset(MiniReentryLock.class.getDeclaredField("tail"));
} catch (Exception e) {
throw new Error(e);
}
}
private boolean compareAndSetHead(Node update) {
return UNSAFE.compareAndSwapObject(this, HEAD_OFFSET, null, update);
}
private boolean compareAndSetTail(Node expect, Node update) {
return UNSAFE.compareAndSwapObject(this, TAIL_OFFSET, expect, update);
}
private boolean compareAndSetState(int expect, int update) {
return UNSAFE.compareAndSwapInt(this, STATE_OFFSET, expect, update);
}
/**
* Blocked threads are encapsulated as node node , And then put in FIFO queue
*/
static final class Node {
/**
* Encapsulated thread itself
*/
Thread thread;
/**
* Front node reference
*/
Node pv;
/**
* Post node reference
*/
Node nx;
public Node(Thread thread) {
this.thread = thread;
}
public Node() {
}
}
public int getState() {
return state;
}
private void setHead(Node node) {
this.head = node;
// The current thread is already the thread that has obtained the lock
node.thread = null;
node.pv = null;
}
public void setState(int state) {
this.state = state;
}
public Thread getExclusiveOwnerThread() {
return exclusiveOwnerThread;
}
public void setExclusiveOwnerThread(Thread exclusiveOwnerThread) {
this.exclusiveOwnerThread = exclusiveOwnerThread;
}
public Node getHead() {
return head;
}
public Node getTail() {
return tail;
}
public void setTail(Node tail) {
this.tail = tail;
}
}
Write a simulated ReentrantLock More articles about
- give up antd table, be based on React Write a virtual scrolling table
origin The title is a bit exaggerated , It's not giving up completely antd-table, After all, react In our ecosystem , For the Chinese , It's easy to use PC End component library , It's just antd 了 . Even after 2018 The Christmas egg incident in ,antd The number of users is not reduced , back ...
- You can only use it out 了 , Write a standard Promise
Promise What is it? So-called Promise, It's simply a container , It holds an event that will end in the future ( This is usually an asynchronous operation ) Result . grammatically ,Promise It's an object , From it you can get messages for asynchronous operations .Prom ...
- utilize SpringBoot+Logback Write a simple link trace
Catalog One . Realization principle Two . Code combat 3、 ... and . test Recently, when checking online problems , Finding too many requests leads to complex logs , There's no way to associate user logs in one or more requests , So use it SpringBoot+Logback I wrote a Jane ...
- Write a thread pool , Take you to study ThreadPoolExecutor Thread pool implementation principle
Abstract : Start with handwriting thread pool , Step by step, analyze the code in the Java How is it implemented in the thread pool of . This article is shared from Huawei cloud community < Handwriting thread pool , Contrast learning ThreadPoolExecutor Thread pool implementation principle !>, author : Little brother Fu ...
- 『 try 』 Write an independent Json Algorithm JsonHelper
background : > Always use Newtonsoft.Json.dll It's quite stable . > But this framework is also very disturbing : > 1. Impact compilation failure :https://www.cnblogs.com/zih ...
- Teach you how to use Java Write a list based queue
In the last blog [ Teach you how to use Java Write an array based queue ] Queues have been described in , as well as Java Implementation of queue in language , I don't know much about queues. I can write my last article . that , Now let's go straight to the subject . This blog is mainly about how to make ...
- 【spring】-- Handwriting is the simplest IOC frame
1. What is? springIOC IOC It's about putting each bean( Entity class ) And bean( Entity ) The relationship between them is managed by a third party container . If we write the simplest IOC, What's the final result ? xml To configure : <b ...
- Get it done redis interview --Redis The expiration strategy of ？ Writing a LRU？
1 Interview questions Redis What are the expiration policies of ? What are the memory elimination mechanisms ? Write it by hand LRU Code implementation ? 2 Test point analysis 1) I'll go redis What's wrong with the data in ? Our production environment is redis How often do you lose some data ? Written in. ...
- Write a simple one by hand ElasticSearch SQL converter ( One )
One . Preface There was a need , Is to make ElasticSearch Support use SQL Simple query , Newer versions of ES This feature is already supported ( But it seems to be experimental ?) , and git There are also elasticsearch-sql plug-in unit , ...
- Look at the annual salary 50W How to write a SpringMVC frame
Preface do Java Web Developed by you , I must have heard of SpringMVC The name of , As the most widely used Java frame , So far, it still maintains a strong vitality and a wide user base . How does this work eclipse Build it step by step S ...
Random recommendation
- DevExpress GridControl Summary of usage （ turn ）
One . How to solve the problem of selecting the whole line of click record View->OptionsBehavior->EditorShowMode Set to :Click Two . How to add a new record (1).gridView.AddN ...
- jenkins Continuous integration tools
jenkins It's open source. Continuous integration . Continuous build Visualization web Tools , Continuous construction, to put it bluntly , It's the automatic compilation of various projects . pack . Distribution deployment . There are many advantages : 1. Support for multiple languages 2. Follow svn.git Seamless integration 3. Direct contact with well-known sources ...
- Internship notes -3：ef Entity operation errors
Learning notes 1.json serialize ef Entity is an error :“ The serialization type is “System.Data.Entity.DynamicProxies.XXXX.... Circular reference detected while object .” In the company ef To generate entities . however ...
- Omi v1.0 Shock release - Suffocating Web Componentized framework
Link to the original text --https://github.com/AlloyTeam/omi Write it at the front Omi The framework iterates through dozens of versions , It's getting easier to use and more powerful . After working overtime all night on weekends ,Omi v1.0 The version finally came out ...
- 201521123103 《Java Learning notes 》 Fourth week learning summary
One . This week's learning summary 1.1 Try to use mind map to summarize knowledge about inheritance . 1.2 Summarize other lessons in the usual way . (1) polymorphism : The same shape , Different behavior ( Different definitions ): (2) Polymorphic binding : The runtime can automatically select which ...
- 6. Deep cloning _ES7**_arr.includes(' The Monkey King ')
1. How to achieve deep cloning utilize JSON Method ( There is no way to clone function data ) `JSON.parse(JSON.stringify(xxx))` Custom method Methods for checking all data types `Object.proto ...
- hive function -- Encoding and decoding
With UTF-8 For example : Test string :️ Afternoon coffee ️ One . code hive"); Output : %E2%98%95%EF%B8%8F%E5%8D%88%E5%90%8E%E5%92%96%E5%95%A ...
- windows Solve access github Slow question
·1. change host file File address : C:\Windows\System32\Drivers\etc If you can't modify it directly , It can be copied back to the desktop after modification 2. stay host files were added #github 19 ...
- use react Write a table that you can edit
This is a prototype , But it works . The difficulty is how to click the Edit button at the end of each line , Let the current row of the grid become input. import {Component} from 'react' const Action = props ...
- python singleton design pattern super() Multiple inheritance
python singleton design pattern decorate baseclass metaclass import module super() One .A decorator de ...
