ReentrantReadWriteLock: ReentrantReadWriteLock

preface

This article will introduce AQS shared locks and ReentrantReadWriteLock, which implements read and write lock separation based on shared locks. This article will introduce AQS shared locks and ReentrantReadWriteLock. (I will not repeat the previous methods if I encounter them.)

First, why do we use read-write lock separation?

We know that ReentrantLock uses an exclusive lock and blocks regardless of whether the thread is in the read or write state, which undoubtedly reduces concurrency.

However, we know that when multiple threads read data simultaneously, there is no thread-safety problem because they do not interfere with each other. So why not design a scheme where all reader threads can share and read data at the same time, just by blocking the writing thread? This improves concurrency without causing data inconsistencies.

Similarly, if a thread is writing data, it blocks the other reader threads (as well as the other writer threads) until the data is written, ensuring that the data read is up to date.

Therefore, we can use read and write locks to control data read and write respectively. Realize read sharing, read and write mutually exclusive, write mutually exclusive. This is where the ReentrantReadWriteLock read-write separation lock comes from. It works well in scenarios where you read more than you write.

ReentrantReadWriteLock

Like ReentrantLock, it is a ReentrantLock and provides read/write separation based on the AQS shared lock. Its internal structure is much the same, supporting fair and unfair locks. Let’s look at its constructor,

Public ReentrantReadWriteLock() {this(false); } public ReentrantReadWriteLock(boolean fair) { sync = fair ? new FairSync() : new NonfairSync(); readerLock = new ReadLock(this); writerLock = new WriteLock(this); }Copy the code

It defines two inner classes to represent read locks and write locks, and uses the inner class Sync to lock and release locks.

public static class ReadLock implements Lock, java.io.Serializable { private static final long serialVersionUID = -5992448646407690164L; private final Sync sync; protected ReadLock(ReentrantReadWriteLock lock) { sync = lock.sync; }... } public static class WriteLock implements Lock, java.io.Serializable { private static final long serialVersionUID = -4992448646407690164L; private final Sync sync; protected WriteLock(ReentrantReadWriteLock lock) { sync = lock.sync; }... } abstract static class Sync extends AbstractQueuedSynchronizer { }Copy the code

Let’s look at fair and unfair locks. There are two important methods to determine whether read and write locks should be blocked, which will be used later in the lock process.

static final class FairSync extends Sync { private static final long serialVersionUID = -2274990926593161451L; // Both reading and writing of a fair lock need to determine whether there is already a thread waiting in front of it. // If so, the current thread needs to block, which is also fair. final boolean writerShouldBlock() { return hasQueuedPredecessors(); } final boolean readerShouldBlock() { return hasQueuedPredecessors(); } } static final class NonfairSync extends Sync { private static final long serialVersionUID = -8159625535654395037L; Final Boolean writerShouldBlock() {return false; // Writers can always barge} final Boolean readerShouldBlock() {// In order to prevent writers from being hungry, Need to determine synchronous queue first in line (head. Next) is an exclusive lock (write threads) / / if it is, the reader thread will need to block, this is method of AQS return apparentlyFirstQueuedIsExclusive (); } } final boolean apparentlyFirstQueuedIsExclusive() { Node h, s; return (h = head) ! = null && (s = h.next) ! = null && ! s.isShared() && s.thread ! = null; }Copy the code

Think about:

We know that ReentrantLock’s synchronization status and reentrant count are directly expressed as state values. So, now THAT I need to read and write two locks, how can I use an int to represent the state of both locks? Also, locks are reentrant. How do I count the number of reentrants?

Don’t worry. One at a time.

How to use one state value to indicate that read and write two locks?

State is a 32-bit int value, which is divided into two parts. The high 16 bits represent the read state, and the value represents the number of threads that read the lock (as shown in figure 3). The low 16 bits represent the write state, and the value represents the number of reentrant times (since the lock is exclusive) for the write lock. In this way, the number of read and write locks can be counted separately. Its associated properties and methods are defined in the Sync class.

static final int SHARED_SHIFT = 16; Static final int SHARED_UNIT = (1 << SHARED_SHIFT); static final int SHARED_UNIT = (1 << SHARED_SHIFT); Static final int MAX_COUNT = (1 << SHARED_SHIFT) - 1; static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1; // The number of threads holding the read lock, such as c represents the state value //state 32 bits, unsigned right 16 bits, Static int sharedCount(int c) {return c >>> SHARED_SHIFT; Static int exclusiveCount(int c) {return c & EXCLUSIVE_MASK; }Copy the code

It is easy to calculate the number of read locks by moving 16 bits to the right without sign. Let’s look at how write lock reentrant counts. ‘EXCLUSIVE_MASK’ : (1 << 16) -1

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 // Any 32-bit binary number c and the above values are the lower 16 bits of its own value.Copy the code

How is the lock reentrant count calculated?

Write locks are relatively simple, and the reentrant number of write locks can be directly represented by the lower 16 bits calculated.

Reading locks is more complicated because the 16 bits high only represent the number of threads holding the shared lock. So, within Sync, we maintain a class that represents the number of reentries per thread,

static final class HoldCounter {
    int count = 0;
    // Use id, not reference, to avoid garbage retention
    final long tid = getThreadId(Thread.currentThread());
}Copy the code

Here we define a counter to represent the number of reentries and tid to represent the current thread ID. However, we need to bind the HoldCounter to the thread so that we can distinguish the number of locks held by each thread (the number of reentrant times), which requires a ThreadLocal.

Static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> {static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> { Public HoldCounter initialValue() {return new HoldCounter(); }}Copy the code

In addition, Sync defines some other read lock related properties,

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * HoldCounter private TRANSIENT ThreadLocalHoldCounter readHolds; // If the last thread to acquire the read lock has repeatedly acquired the read lock, it can be used directly without updating. Private TRANSIENT HoldCounter cachedHoldCounter; Private TRANSIENT Thread firstReader = null; Private TRANSIENT int firstReaderHoldCount; private TRANSIENT int firstReaderHoldCount; // These two parameters, for efficiency purposes, avoid looking for readHolds when only one thread has the read lockCopy the code

With the basics out of the way, it’s time to acquire and release locks. Write lock first, because of the last article on the basis of the exclusive lock, it is easier to understand.

Write lock acquisition

The write lock is acquired from the lock method,

//ReentrantReadWriteLock.WriteLock.lock public void lock() { sync.acquire(1); } //AbstractQueuedSynchronizer.acquire public final void acquire(int arg) { if (! tryAcquire(arg) && acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) selfInterrupt(); } // Fair and unfair locks call the same method, Defined in Sync class. / / ReentrantReadWriteLock Sync. TryAcquire protected final Boolean tryAcquire (int) acquires {Thread current =  Thread.currentThread(); State int c = getState(); Int w = exclusiveCount(c); If (c! // If the write lock status is not 0, and the current thread does not acquire the write lock, then the reentrant is not allowed. Returns false if (w = = 0 | | current! = getExclusiveOwnerThread()) return false; If (w + exclusiveCount(acquires) > MAX_COUNT) throw new Error("Maximum lock count exceeded"); Acquires (c + acquires); // Count the reentrant count and return true setState(c + acquires); return true; } / / to this suggests that c is 0, read and write locks lock / / if not occupied write lock failed to get write locks should be blocked or CAS, if return false (writerShouldBlock () | |! compareAndSetState(c, c + acquires)) return false; SetExclusiveOwnerThread (current); return true; }Copy the code

Write lock release

Similarly, write locks are released from 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; } protected final Boolean tryRelease(int releases) {// If the owner of the exclusive lock is not the current thread, throw an exception if (! isHeldExclusively()) throw new IllegalMonitorStateException(); // State minus 1 int nexTC = getState() -releases; boolean free = exclusiveCount(nextc) == 0; if (free) setExclusiveOwnerThread(null); setState(nextc); return free; }Copy the code

As you can see, the basic idea of acquiring and releasing write locks is similar to that of ReentrantLock. Below, focus on read lock acquisition and release, relatively complex.

Read lock acquisition

tryAcquireShared

Starting with the readlock. lock method,

Public void lock() {// Call the AQS method sync.acquireshared (1); } public final void acquireShared(int arg) {// If tryAcquireShared returns < 0, If (tryAcquireShared(arg) < 0) // Join the queue in shared mode and spin the lock doAcquireShared(arg); } protected final int tryAcquireShared(int unused) { Thread current = Thread.currentThread(); int c = getState(); // If a thread has acquired the write lock and is not the current thread, -1 is returned. // This is because if the program first acquired the write lock, it can re-enter to acquire the read lock again, which is lock degradation. // Otherwise do not reenter. if (exclusiveCount(c) ! = 0 && getExclusiveOwnerThread() ! = current) return -1; Int r = sharedCount(c); If all the following conditions are met (the read thread should not be blocked, the number of read locks is less than the maximum number, and the CAS is successful), the read lock is obtained successfully. 1 is returned. Then set the values of the related properties. if (! ReaderShouldBlock () &&r < MAX_COUNT &&compareAndSetState (c, c + SHARED_UNIT)) { If (r == 0) {if (r == 0) {firstReader = current; // The first reader thread count is set to 1 firstReaderHoldCount = 1; } else if (firstReader == current) {// if the current thread is the first thread to acquire the read lock, reentrant, count + 1 firstReaderHoldCount++; HoldCounter rh = cachedHoldCounter;} else {// The last thread that successfully acquired the lock is not firstReader. Rh has not been set by any thread, and only firstReader has acquired the read lock. Rh is set and is not the current thread, so the current thread is the third thread to acquire the read lock (at least). if (rh == null || rh.tid ! = getThreadId(current)) // In either case, create and initialize the current thread's counter and assign it to cachedHoldCounter because the current thread is the last one to acquire the read lock at this point, CachedHoldCounter = rh = readHolds. Get (); // If (rh.count == 0) else if (rh.count == 0) // Put readHolds (holds). Set (rh); // add 1 rh.count++; } return 1; } return fullTryAcquireShared(current);} return fullTryAcquireShared(current); }Copy the code

FullTryAcquireShared The fullTryAcquireShared method is very similar to the tryAcquireShared method, except that the spin process is complete until a certain value (-1 or 1) is returned.

final int fullTryAcquireShared(Thread current) { HoldCounter rh = null; // Spin until a definite value (1 or -1) is returned for (;;). { int c = getState(); If (exclusiveCount(c)! If (getExclusiveOwnerThread()! = 0) {if (getExclusiveOwnerThread()! = current) return -1; // The thread has acquired the write lock, so it needs to downgrade the write lock to the read lock. Because if you don't do that, the thread will block up here, which will cause a deadlock. //===========//} else if (readerShouldBlock()) {// Write lock is free and read lock should block, so head. Next is waiting for write lock However, this should not be blocked immediately, as there may be read lock reentrant, which needs to be confirmed. If (firstReader == current) {// The current thread is the first read lock, Else {if (rh == null) {// The first loop must be null rh = cachedHoldCounter; / / to cache the last time to get to read lock counter the if (rh = = null | | rh. Dar! = getThreadId(current)) { rh = readHolds.get(); If (rh.count == 0) // If (rh.count == 0) readHolds. Remove (); }} if the current thread is not a firstReader and has not acquired a read lock, it does not meet the reentrant condition. if (rh.count == 0) return -1; If (sharedCount(c) == MAX_COUNT) throw new Error("Maximum lock count exceeded"); //CAS gets the read lock, just like tryAcquireShared, If (compareAndSetState(c, c + SHARED_UNIT)) {if (sharedCount(c) == 0) {firstReader = current; firstReaderHoldCount = 1; } else if (firstReader == current) { firstReaderHoldCount++; } else { if (rh == null) rh = cachedHoldCounter; if (rh == null || rh.tid ! = getThreadId(current)) rh = readHolds.get(); else if (rh.count == 0) readHolds.set(rh); rh.count++; cachedHoldCounter = rh; // cache for release } return 1; }}}Copy the code

doAcquireShared

If tryAcquireShared still fails, the doAcquireShared method is executed.

Private void doAcquireShared(int arg) {// Join the queue in SHARED mode final Node Node = addWaiter(node.shared); boolean failed = true; try { boolean interrupted = false; for (;;) { final Node p = node.predecessor(); Int r = tryAcquireShared(arg); if (p == head) {// If (p == head) {int r = tryAcquireShared(arg); Propagate(node, r); // propagate (node, r); p.next = null; // help GC if (interrupted) selfInterrupt(); failed = false; return; Failed to get read lock}} / /, determine whether to suspend the current thread if (shouldParkAfterFailedAcquire (p, node) && parkAndCheckInterrupt ()) interrupted = true; } } finally { if (failed) cancelAcquire(node); }}Copy the code

setHeadAndPropagate

Private void propagate (Node propagate, int propagate) {// propagate (Node propagate); // Set the current node to the new head setHead(node); //propagate is the return value of the tryAcquireShared method. If the propagate is greater than 0, or the old header is null, or the ws of the header is less than 0, or the new header is null, or the WS of the new header is less than 0, For subsequent nodes if (the propagate > 0 | | h = = null | | h.w. aitStatus < 0 | | (h = head) = = null | | h.w. aitStatus < 0) {Node s = node.next; / / no subsequent nodes are Shared or subsequent node, is executed awaken the if (s = = null | | s.i sShared ()) / / release resources, and wake up the subsequent nodes, later on doReleaseShared (); }}Copy the code

Read lock release

tryReleaseShared

Start with the readlock. unlock method,

public void unlock() { sync.releaseShared(1); } public final boolean releaseShared(int arg) { if (tryReleaseShared(arg)) { doReleaseShared(); return true; } return false; } protected final boolean tryReleaseShared(int unused) { Thread current = Thread.currentThread(); If (firstReader == current) {// If (firstReader == current) { If (firstReaderHoldCount == 1) firstReader = null; FirstReaderHoldCount --; firstReaderHoldCount--; } else { HoldCounter rh = cachedHoldCounter; if (rh == null || rh.tid ! = getThreadId(current)) rh = readHolds.get(); int count = rh.count; If (count <= 1) {// If (count <= 1) {readHolds. Remove (); Throw unmatchedUnlockException() if (count <= 0) // Throw unmatchedUnlockException() if (count <= 0) } // count minus 1 --rh.count; } for (;;) { int c = getState(); Int nexTC = c - SHARED_UNIT; int nexTC = c - SHARED_UNIT; If (compareAndSetState(c, nexTC)) if (compareAndSetState(C, nexTC)) if (compareAndSetState(C, nexTC))) Return nexTC == 0; return nexTC == 0; }}Copy the code

doReleaseShared

If the tryReleaseShared method returns true, the read lock is released successfully and the subsequent nodes need to be woken up.

private void doReleaseShared() { for (;;) {// Node h = head; // There are at least two nodes in the queue. = null && h ! = tail) { int ws = h.waitStatus; If (ws = = Node. SIGNAL) {/ / if the head Node of the ws to 1, the CAS set it to 0, because wake up after subsequent nodes, / / don't need to do it. Failed continue spin attempt if (! compareAndSetWaitStatus(h, Node.SIGNAL, 0)) continue; // If CAS succeeds, wake up the unparksucceeded (h); } // If ws is 0, set it to -3, which indicates that the shared state can PROPAGATE backwards, if it fails, continue the spin attempt // Later I have been thinking about why PROPAGATE such a state, but I have no idea about it. / / https://www.cnblogs.com/micrari/p/6937995.html / / can only say that Doug Lea, a great god are too rigorous logic, etc. I want to see later, add it. Else if (ws == 0 &&! compareAndSetWaitStatus(h, 0, Node.PROPAGATE)) continue; // loop on failed CAS} // loop on failed CAS} If (h == head) // loop if head changed break; }}Copy the code

conclusion

The exclusive lock is relatively simple. Lock reading involves many critical points and transient states. It’s not as simple as it looks on the surface. After all, the thoughts of Doug Lea are hard to fathom.

This article is just some of my personal understanding, if the explanation is not in place, welcome to clap brick.

In fact, there are many details, this article is not developed. For example, why does setHeadAndPropagate method judge ws state of two old and new nodes, what is the meaning? What does the doReleaseShared method finally need to design h == head? Why PROPAGATE state is needed, what if there is no PROPAGATE state.

Looks like the road is long… Later to fill the hole, this can only be called a brief analysis. ￣□￣ | |

If this article is useful to you, please like it, comment on it, and retweet it.

Learning is boring and interesting. I am “Misty rain sky”, welcome to pay attention to, can be the first time to receive the article push.