Principles and applications of Reentrantlock and AQS

features

Reentantlock is a lock implementation class, which has the following features: reentrantLock implementation depends on AQS, so we will focus on AQS

Mechanism of the cas

Cas, also known as optimistic locking, is an asynchronous strategy. The CAS mechanism uses three basic operands:

• Memory address V
• The old expected value A
• The new value B to be modified

To update a variable, the value of memory address v is changed to B only if the actual value in memory address V is the same as the expected value a. And this process of comparison is constantly traversing, which is the spin

The disadvantage of the cas

• Large CPU overhead

• The atomicity of a code block is not guaranteed; the CAS mechanism guarantees only a mutational atomicity operation, not the entire code block. Synchronization, for example, is used to ensure that all three variables are updated atomically together

• ABA Problems ABA problems can be explained by an example

  1) Thread 1 (ATM) : get the current value of 100, expect to update to 50, thread 2 (ATM) : Get current value 100, expect update to 50, thread 1 executes successfully, thread 2 blocks for some reason, then someone sends Xiaoming 50 thread 3 (default) : Thread 3 returns from the Block with a balance of 100. Thread 2 returns from the Block with a balance of 100. Thread 2 returns from the Block with a balance of 100. At this point, you can see that the actual balance should be 100 (100-50+50), but it is actually 50 (100-50+50-50), which is the ABA problem resulting in a successful submission. Solution: Add the version number before the variable. Each time the variable is updated, the version number of the variable is +1, i.e. A->B->A becomes 1A->2B->3A.

Reentrantlock’s connection to AQS

static final class NonfairSync extends Sync { ... final void lock() { if (compareAndSetState(0, 1)) setExclusiveOwnerThread(Thread.currentThread()); else acquire(1); }... }Copy the code

This is a non-fair lock source, in the lock process processing strategy, you can see that if the CAS set variable state (synchronization state) success, that is, to obtain the lock success, the current thread is set as an exclusive lock. If the variable fails to be set through CAS, that is, the lock fails to be acquired, then the AQS processing process is entered, that is, acquire () method

Understand AQS through ReentrantLock

The thread joins the wait queue

After acquire, obtain the lock through tryAcquire. In this case, if the fetch lock fails, addWaiter is called to join the wait queue. So how do you get in the queue?

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; } private final boolean compareAndSetTail(Node expect, Node update) { return unsafe.compareAndSwapObject(this, tailOffset, expect, update); }Copy the code

Although this is a bidirectional list, it is still a tail plug. In this list, head is a fixed null value, and after insertion, the tail pointer moves backwards

The time when a thread in the queue will exit the queue

Final Boolean acquireQueued(final Node Node, int arg) {final Boolean failed = true; Boolean interrupted = false; // Start the spin, either acquire the lock, or interrupt for (;;) Final Node p = node.predecessor(); If (p == head && tryAcquire(arg)) {setHead(node); setHead(node); p.next = null; // help GC failed = false; return interrupted; } // p is the head node and does not currently acquire the lock (it may be unfair that the lock is preempted) or p is not the head node. In this case, it is necessary to determine whether the current node will be blocked (blocked condition: waitStatus of the precursor node is -1) to prevent infinite loop waste of resources. Concrete under the two methods to analysis the if (shouldParkAfterFailedAcquire (p, node) && parkAndCheckInterrupt ()) interrupted = true; } } finally { if (failed) cancelAcquire(node); }}Copy the code

As you can see from the above, the condition for breaking out of the loop is that it must be after the head node and the current node is not blocked

Interrupt to cancel

In the string above, the last thing to finally execute is

finally {
		if (failed)
			cancelAcquire(node);
	}
Copy the code

Let’s take a closer look at the cancelAcquire () code

Private void cancelAcquire(Node Node) {if (Node == null) return; Thread = null; thread = null; thread = null; Node pred = node.prev; While (pred.waitStatus > 0) node.prev = pred = pred.prev; Node predNext = pred.next; CANCELLED node.waitStatus = node.cancelled; // If the current node is the last node, set the first non-canceled node from back to last node as the last node. If (node == tail && compareAndSetTail(node, pred)) {compareAndSetNext(pred, predNext, null); } else { int ws; // If the current node is not a successor of the head, 1: check whether the current node's precursor is SIGNAL, 2: if not, set the precursor to SINGAL to check whether the current node's precursor is SIGNAL. // If all the above conditions are met, the successor pointer of the current node points to the successor node of the current node. = head && ((ws = pred.waitStatus) == Node.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) && pred.thread ! = null) { Node next = node.next; if (next ! = null && next.waitStatus <= 0) compareAndSetNext(pred, predNext, next); } else {// If the current node is the successor of head, or the above conditions are not met, wake up the unparksucceeded (node) of the current node; } node.next = node; // help GC } }Copy the code

The process of this code is as follows: obtain the predecessor Node of the current Node. If the predecessor Node is CANCELLED, go straight ahead and find the first waitStatus <= 0 Node. Associate the found Pred Node with the current Node and set the current Node to CANCELLED. Then, according to the position of the current node, consider the following three situations:

• (1) The current node is the tail node.

• (2) The current node is the successor node of Head.

• (3) The current node is neither a successor of Head nor a tail node.

The rule for removing nodes is to move only the next pointer, not the prev pointer. Why is that?

The reason: Enforce cancelAcquire, front nodes of the current node may have already went out from the queue (has been carried out in the Try block shouldParkAfterFailedAcquire method), if the modified Prev pointer, It may cause the Prev to point to another Node that has been removed from the queue, so the changed Prev pointer is not safe. ShouldParkAfterFailedAcquire method, execute the following code, is actually in the treatment of the Prev pointer. ShouldParkAfterFailedAcquire is acquiring a lock failed to perform, after entering the method, has been Shared resources available, before the current node node will not change, so this time change Prev pointer is safe.

So we can continue to look at these three situations:

①Delete the last node while the tail pointer moves forwardInterrupt by pointing the node at itselfDelete the node and point to your own seeding

Release the lock

public void unlock() {
	sync.release(1);
}
Copy the code

The lock release is done through the framework

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 code