1, Concept of reentry lock
The concept of reentry means that the lock can be entered repeatedly within the same thread.
lock.lock();
lock.lock();
// do something
lock.unlock();
lock.unlock();
A thread can acquire a lock multiple times, but it also needs to release the lock the same number of times. Otherwise, the thread will continue to own the lock, and other threads will not be able to enter the critical area.
2, Several important methods of reentry lock
Lock: obtain the lock. If the lock is occupied by other threads, sleep and wait.
Lock interruptible: obtain the lock, which can be interrupted by other threads
tryLock: try to acquire a lock without waiting
tryLock (time, timeUnit): attempts to acquire a lock within a certain period of time
unlock: release lock
2.1 interrupt response
For synchronized, a thread either acquires the lock and starts execution, or continues to wait. However, for reentry locks, a more flexible mechanism is provided, that is, during the process of waiting for the lock, the request for the lock can be cancelled, which can effectively avoid the possibility of deadlock.
2.2 waiting time for lock application
Interrupt response is a mechanism to interrupt the request for lock through external notification, so as to avoid deadlock. In addition, there is another mechanism, that is, waiting time limit.
tryLock(long timeout, TimeUnit unit)
2.3 fair lock and unfair lock
Reentry locks are non fair locks by default
public ReentrantLock() {sync = new NonfairSync();
}
Fair locks can be implemented through constructor parameters
public ReentrantLock(boolean fair) {sync = fair ? new FairSync() : new NonfairSync();
}
If it is a non fair lock, in the concurrent scenario, the system will randomly select a thread from the waiting queue. If it is a fair lock, the system will maintain an ordered queue and execute it orderly according to the order of entering the queue. Therefore, although the fair lock avoids hunger, it will require higher cost to maintain this ordered queue.
2.4 composition and structure of AQS
The locking and unlocking process of reentry lock is mainly completed by AQS. AQS maintains a two-way linked list. Each Node stores a thread and thread status, and the Head Node represents the thread holding the lock.
AQS bidirectional linked list
Node status:
CANCELLED: the current node timed out or the interrupt was CANCELLED
SIGNAL: subsequent nodes of the current node are in a waiting state
Condition: the current node waits for condition
PROPAGATE: state propagation backward
static final class Node {/** waitStatus Status: the current node is canceled scheduling*/
static final int CANCELLED = 1;
/** waitStatus Status: subsequent nodes wait to be awakened*/
static final int SIGNAL = -1;
/** waitStatus Status: the current node is waiting condition Up,
* When other threads call Condition of signal()After the method,
* CONDITION The node in state will be transferred from the waiting queue to the synchronization queue,
* Waiting for synchronization lock*/
static final int CONDITION = -2;
/** waitStatus Status: in sharing mode, subsequent nodes and subsequent nodes will be awakened*/
static final int PROPAGATE = -3;/** Node status*/
volatile int waitStatus;
}
When the thread fails to acquire the lock, it will join the synchronization queue (join the tail) through addWaiter to determine whether it is the head node of the linked list. If it is the head node, it will continue to try to obtain resources. After successful acquisition, it will exit the synchronization queue.
3, Implementation principle of reentry lock
First, look at the class diagram of reentry lock
Reentrant lock class diagram relationship
ReentrantLock defines the internal class sync. Sync inherits from AbstractQueuedSynchronizer (AQS) and is a synchronous waiting queue. In essence, it is a two-way linked list with head and tail pointers.
There is a very important variable in AQS. Different components have different meanings. In the reentry lock component, it represents the number of times reentrant by threads. A value of 0 indicates that no thread holds a lock.
private volatile int state;
3.1 locking process of fair lock
sync. The acquire method of AQS is called during lock. This is a template design pattern, that is, the overall processing flow is defined in AQS, but the specific implementation details will be implemented in subclass methods according to different lock types.
public final void acquire(int arg) {// Attempt to acquire lock
if (!tryAcquire(arg) &&
// The thread that failed to acquire the lock is safely added to the waiting queue
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
// A break
selfInterrupt();
}
Let's take a look at the implementation details of each step
tryAcquire of fair lock
tryAcquire is a hook method. Implementation details are placed in specific subclasses.
Fair lock attempts to acquire the lock process
protected final boolean tryAcquire(int acquires) {final Thread current = Thread.currentThread();
//Gets the status of the current lock
int c = getState();
// No thread occupation
if (c == 0) {// If the current thread is the first in the queue and CAS preempts the lock successfully
if (!hasQueuedPredecessors() &&
compareAndSetState(0, acquires)) {// Set the thread occupying the lock as the current thread
setExclusiveOwnerThread(current);
return true;
}
}
// Determine whether the thread occupying the lock is the current thread
else if (current == getExclusiveOwnerThread()) {int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");// The number of reentries plus 1. Acquire is passed in by acquire(1)
setState(nextc);
return true;
}
return false;
}
acquireQueued(addWaiter())
The thread will try to obtain the lock in the synchronization queue. If it fails, it will be blocked. After being awakened, it will keep repeating this process until the thread really holds the lock and places its own node at the head of the queue. Students interested in the algorithm can study it in depth by themselves.
addWaiter queue process (when the queue is not empty)
1. Create a new Node according to the current thread
2. If the queue tail element is not empty, it is inserted into the queue tail through CAS operation
3. If the queue is empty, new a node and set it as the header head
Team joining process
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;
}
//Team logic
private Node enq(final Node node) { for (;;) {Node t = tail;
if (t == null) { // Must initializeif (compareAndSetHead(new Node()))
tail = head;
} else {node.prev = t;
if (compareAndSetTail(t, node)) {t.next = node;
return t;
}
}
}
}
What did you do after the elements joined the team?
1. Whether the user is qualified to acquire the lock is detected by spin. If the lock is acquired, the current node is set as the head node
2. If it is not the head - > next node or the lock acquisition fails, the current thread will be blocked
final boolean acquireQueued(final Node node, int arg) {boolean failed = true;
try {boolean interrupted = false;
for (;;) {// Gets the prev node of the current node
final Node p = node.predecessor();
// If it is the head node, try to acquire the lock
if (p == head && tryAcquire(arg)) {// If the lock is obtained successfully, set the current node as the head node
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
// If the lock is not obtained, first determine whether the current thread needs to be blocked
if (shouldParkAfterFailedAcquire(p, node) &&
// Via locksupport The park (this) primitive blocks the current thread
parkAndCheckInterrupt())
interrupted = true;
}
} finally {if (failed)
cancelAcquire(node);
}
}
The most difficult thing to understand here is this sentence. Why do you try to obtain a lock when the front node of the current node is the head node? Because the head node represents the thread currently holding the lock. When the thread releases the lock after execution, it will wake up the blocked thread in the queue, and the awakened thread will try to obtain the lock.
if (p == head && tryAcquire(arg)) {...
}
3.2 unlocking process of fair lock
public void unlock() {sync.release(1);
}
public final boolean release(int arg) {// Release lock
if (tryRelease(arg)) {Node h = head;
// Queue is not empty
if (h != null && h.waitStatus != 0)
// Wake up blocked threads in queue
unparkSuccessor(h);
return true;
}
return false;
}
The specific logic of releasing the lock is as follows
protected final boolean tryRelease(int releases) {// Times - 1
int c = getState() - releases;
// Determine whether it is the current thread
if (Thread.currentThread() != getExclusiveOwnerThread())
throw new IllegalMonitorStateException();
boolean free = false;
// No thread occupied after release
if (c == 0) {free = true;
// Set the lock process to null
setExclusiveOwnerThread(null);
}
// Update status
setState(c);
return free;
}
Wake up subsequent nodes after release
private void unparkSuccessor(Node node) {//Node is the node where the current thread is located
int ws = node.waitStatus;
// The status is set to 0
if (ws < 0)
compareAndSetWaitStatus(node, ws, 0);
// Find the next node that needs to be awakened
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)
//Wake up thread
LockSupport.unpark(s.thread);
}
3.3 the implementation principles of unfair lock and fair lock are basically similar
When trying to acquire a lock, a non fair lock does not judge whether it is the first element in the queue, but directly compares CAS. The process of releasing the lock is the same.
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;
}