preface

ReentrantLock ReentrantReadWriteLock ReentrantReadWriteLock ReentrantLock ReentrantLock ReentrantLock ReentrantReadWriteLock ReentrantReadWriteLock ReentrantLock ReentrantLock ReentrantLock ReentrantLock In ReentrantReadWriteLock, a pair of locks, one read and one write, are maintained, and read-write locks allow access by multiple reader threads at the same time. But when the writer thread accesses, all reader threads and other writer threads are blocked. Before reading this article, I hope you have read the following articles:

  • Lock interface for Java concurrent programming locking mechanism
  • Concurrent Java programming of locking mechanism of AQS (AbstractQueuedSynchronizer)
  • LockSupport tool for Java concurrent programming locking mechanism
  • Condition interface for Java concurrent programming locking mechanism
  • Reentrant locking for Concurrent programming in Java

The basic structure

Before we learn more about ReentrantReadWriteLock, let’s take a look at its overall structure, as shown below:

ReentrantReadWriteLock implements the ReadWriteLock interface. The following static internal classes are declared in ReentrantReadWriteLock:

  • WriteLockwithReadLock(a pair of read/write locks maintained) : From the name of the class, we can see that these two classes are used to control the lock of the read/write thread
  • SyncAnd its subclassesNofairSyncwithFairSync: If you read itReentrant locking for Concurrent programming in JavaIn the introduction of fair lock and unfair lock, then we can also guessReentrantReadWriteLockIs for fair and unfair locking.
  • ThreadLoclHoldCounterandHoldCounter: Involves lock re-entry, which will be described in detail below.

The basic use

When using certain types of collections, you can use ReentrantReadWriteLock to improve concurrency. Typically, this is worth trying when the Collection is expected to be large, the reader thread accesses it more times than the writer thread, and the overhead is higher than the synchronization overhead. For example, here is a dictionary class that uses TreeMap (we assume it is expected to be large and accessible simultaneously).

class RWDictionary { private final Map<String, Data> m = new TreeMap<String, Data>(); private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(); private final Lock r = rwl.readLock(); Private final Lock w = rwl.writelock (); Public Data get(String key) {r.lock(); try {returnm.get(key); } finally { r.unlock(); }} public String[]allKeys() {
        r.lock();
        try { returnm.keySet().toArray(); } finally { r.unlock(); Public Data put(String key, Data value) {w.lock(); try {returnm.put(key, value); } finally { w.unlock(); }} // Empty data public voidclear() { w.lock(); try { m.clear(); } finally { w.unlock(); }}}Copy the code

In the above example, we lock the read operations in TreeMap separately. When we call get(String key) to obtain the TreeMap key, we need to obtain the read lock first. Other threads will block for the write lock, but not for the read lock. Similarly, when we call put(String key, Data value) to update the Data, we need to get the write lock. Other threads will block both write and read locks. Only after the thread that acquired the write lock releases the lock. Only other read and write operations can be performed.

If a write lock is acquired, other read and write operations will be blocked. In order to ensure the visibility of the data. If other read/write operations are not blocked and the read operation takes precedence over the write operation, data obtained by the read operation before data update will be inconsistent with data updated by the write operation.

Note that ReentrantReadWriteLock supports a maximum of 65535 recursive write locks and 65535 read locks. Attempting to exceed these limits will cause the lock method to throw an Error. The specific reasons are described below.

Realize the principle of

So far, we have learned the basic structure and usage of ReentrantReadWriteLock. I’m sure you’re curious about the internals, and I’ll take you through the internals. I will analyze one of the principles of the whole here, and further details of the interior will be described below. Because I think you have to understand the whole thing before you understand the details. So the whole ReentrantReadWriteLock learning process is a little bit easier.

The overall principle

In the previous article, we introduced the basic use of ReentrantReadWriteLock. We found that control of the entire read-write lock is handed over to WriteLock and ReadLock. When we call the lock() method that reads and writes the lock to obtain the lock, we execute the following code:

 public void lock() { sync.acquireShared(1); }Copy the code

So sync. AcquireShared (1), and what is sync? We can also see from its constructor:

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

The statements about FairSync and NonfairSync are as follows:

/ / synchronization queue abstract static class Sync extends AbstractQueuedSynchronizer {omit part of the code... } static final class NonfairSync extends Sync{ } static final class extends Sync extends Sync { }Copy the code

Here we see the familiar AQS, namely the two locks WriteLock and ReadLock, are actually controlled by the synchronous queue in the AQS. Then combining our previous KNOWLEDGE of AQS, we can get the following figure:

(if you don’t know my way around AQS, so you can read this article — — — — > Java concurrent programming of locking mechanism of AQS (AbstractQueuedSynchronizer)

Why is the same synchronization queue maintained

Read and write state design

Now that we know that WriteLock and ReadLock maintain the same synchronization queue, I’m sure you’ll be wondering if there is only one state variable of type INT in the synchronization queue to indicate the current synchronization state. So how does it internally separate the two read and write states and achieve thread control?

The synchronization status of a synchronization queue in ReentrantReadWriteLock is divided into two parts. The high 16 bits indicate the read status and the low 16 bits indicate the write status, as shown in the following figure:

In the figure above, we can see that the maximum number of read and write states can be represented is 65535(excluding negative numbers), which means that the lock is allowed to re-enter 65535 times.

Let’s look at the 16 bits above, where the current thread has acquired the write lock and reentered it seven times. Similarly, if we look down only 16 bits, then the current thread has acquired the read lock and reentered it seven times. Note that in practice, read and write states cannot be assigned by different threads at the same time. Because according to The design of ReentrantReadWriteLock, read and write threads are mutually exclusive. This is just to help you understand the division of synchronization states.

Now that we know the synchronization state partition, we have a new problem. How to quickly distinguish and obtain read and write status? It’s actually pretty simple.

  • Read state: To obtain the read state, simply synchronize the current variableUnsigned 16 bits to the right
  • Write state: We just need to do this with the current synchronization state (denoted here by S)S&0x0000FFFF), that is,S&(1<<16-1).

That is, as shown below (it may not be very clear, so it is recommended to watch it on the PC) :

Detail analysis

After understanding ReentrantReadWriteLock and its read and write state partitioning, it’s easy to understand how ReentrantReadWriteLock works. In the following articles, I’ll discuss read and write lock acquisition separately.

Read lock acquisition

When the lock() method of ReadLock in ReentrantReadWriteLock is called, the tryAcquireShared(int unused) method in Sync is used to determine whether a write lock can be obtained. Now let’s look at a concrete implementation of this method. The specific code is as follows:

protected final int tryAcquireShared(int unused) { Thread current = Thread.currentThread(); int c = getState(); // (1) Check whether there is a write lockif(exclusiveCount(c) ! = 0 && getExclusiveOwnerThread() ! = current)return- 1; int r = sharedCount(c); (2) Obtain the status of the current read lock, determine whether is less than the maximum value, and determine whether the current thread needs to block according to the mode of fair lock or unfair lock.if(! ReaderShouldBlock () &&r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) {// (3) If the write state is less than the maximum, set the number of times the current thread enters againif(r == 0) {// If the current read state is 0, the current reader thread is set to, and the current thread is the first reader thread. firstReader = current; firstReaderHoldCount = 1; }else if(firstReader == current) {// count the number of times the firstReader thread reentered firstReaderHoldCount++; }elseHoldCounter rh = cachedHoldCounter;if(rh == null || rh.tid ! = getThreadId(current)) cachedHoldCounter = rh =readHolds.get();
                    else if (rh.count == 0)
                        readHolds.set(rh);
                    rh.count++;
                }
                return1; } //(4) If the read status fails to be obtained, try to obtain the read lock again.return fullTryAcquireShared(current);
        }
Copy the code
  • (1) According to the current synchronization status, determine whether there is a write lock, and the current thread owning the write lock is not the current thread, then directly return- 1, note that if the method returns a negative value, the value ofThe request thread is added to the AQS synchronization queueIn the. (If you are not familiar with this method, check it outConcurrent Java programming of locking mechanism of AQS (AbstractQueuedSynchronizer)
  • (2) Obtain the status of the current read lock, judge whether it is less than the maximum value, and judge whether the current thread needs to block according to the mode of fair lock or unfair lock
  • (3) If condition (2) is met, set separatelyThe number of times the first reader thread re-enteredandSubsequent threadsNumber of reentries
  • (4) If condition (2) is not met, try again to acquire the read lock.

The methods involved in acquiring a read lock are complex, so the methods involved in each step are described below.

How to determine whether there is a write lock in Step (1)?

In step 1 of the read lock acquisition, the code calls the exclusiveCount(int c) method to determine whether a write lock exists. This method belongs to Sync, and the code is as follows:

abstract static class Sync extends AbstractQueuedSynchronizer { static final int SHARED_SHIFT = 16; 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; static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) -1; Static int sharedCount(int c) {returnc >>> SHARED_SHIFT; Static int exclusiveCount(int c) {returnc & EXCLUSIVE_MASK; }}Copy the code

As you can see from the code, simply execute c & EXCLUSIVE_MASK, or S&0x0000FFFF, with the distinction between read and write states we discussed above, I believe the exclusiveCount(int c) and sharedCount(int c) methods are easy to understand.

In step (2), how to determine whether the lock is fair or unfair.

In step (2), we see that the readerShouldBlock() method is called, which is an abstract method in the Sync class. In ReentrantReadWriteLock, fair and unfair locks are implemented, as shown in the following figure:

Static final class extends Sync {private static final Long serialVersionUID = -2274990926593161451L; final booleanwriterShouldBlock() {returnhasQueuedPredecessors(); } final booleanreaderShouldBlock() {returnhasQueuedPredecessors(); }} static final class NonfairSync extends Sync {final BooleanwriterShouldBlock() { return false; } final booleanreaderShouldBlock() {return apparentlyFirstQueuedIsExclusive();}
    }
Copy the code

The analysis of fair and unfair locks will not be done here. This point has been analyzed in the article reentrent locking for Concurrent Programming in Java. Interested partners can refer to this article.

Why do you want to record the first thread to acquire a write lock in step (3)? How is thread re-entry implemented?

The ReentrantReadWriteLock class defines the Thread firstReader and int firstReaderHoldCount variables, respectively, to record the first Thread to acquire the write lock and the number of times it re-entered. The official explanation is that it is easy to track and record threads and that such records are very cheap. In other words, the reason for defining a separate variable to record the first thread to acquire the write lock is to distinguish threads among many reader threads, and also for later debugging and tracing.

Now that we’ve solved the first problem, let’s solve the second one. I’m not going to analyze how the first thread counts re-entries. Let’s look directly at the reentry times Settings for other reader threads. Because of space constraints, I’ll go straight to the principle here. The number of re-entries for other threads is determined by ThreadLocal. Get the number of times by keeping the HodlerCount class (used to record the number of times the current thread acquired the lock) in memory space in each thread. The specific code is as follows:

static final class HoldCounter { int count; Final Long tid = getThreadId(thread.currentThread ()); } static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> { public HoldCounterinitialValue() {
                return new HoldCounter();
            }
        }
     
   private transient ThreadLocalHoldCounter readHolds;
Copy the code

If you’re not familiar with ThreadLocal, check out this article on Android’s ThreadLocal Handler mechanism.

Continue trying to acquire the read lock in step (4)?

When the first attempt to acquire a read lock fails, the fullTryAcquireShared(Thread Current) method is called to continue trying to acquire the lock. The function returns three conditions:

  • A write lock already exists. Directly join the AQS synchronization queue.
  • If the number of lock write times exceeds the maximum value, an exception is thrown directly
  • Obtaining the read lock succeeded. Procedure Direct return

The specific code is as follows:

    final int fullTryAcquireShared(Thread current) {
            HoldCounter rh = null;
            for(;;) {// Pay attention to thisforLoop int c = getState();if(exclusiveCount(c) ! = 0) {// (1) there is a write lock directly returnif(getExclusiveOwnerThread() ! = current)return- 1; }else if (readerShouldBlock()) {
                    // Make sure we're not acquiring read lock reentrantly if (firstReader == current) { // assert firstReaderHoldCount > 0; } else { if (rh == null) { rh = cachedHoldCounter; if (rh == null || rh.tid ! = getThreadId(current)) { rh = readHolds.get(); if (rh.count == 0) readHolds.remove(); } } if (rh.count == 0) return -1; If (sharedCount(c) == MAX_COUNT)//(2) The number of lock iterations exceeds the maximum value. Throw new Error("Maximum lock count exceeded"); If (compareAndSetState(c, c + SHARED_UNIT)) {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

This method is similar to the tryAcquireShared(int unused) method mentioned earlier. So I won’t go through the logic again here. Note that this method will spin the lock.

Write lock acquisition

Knowing the acquisition of read locks, it is very easy to understand the acquisition of write locks. The write lock is eventually acquired using the tryAcquire(int Acquires) method in Sync. The specific code is as follows:

protected final boolean tryAcquire(int acquires) { Thread current = Thread.currentThread(); Int c = getState(); int c = getState(); int w = exclusiveCount(c); // (2) if c! =0 indicates that there is a thread operationif(c ! If (2.1) there is no write lock thread, then there is no read threadif(w == 0 || current ! = getExclusiveOwnerThread())return false; If w>0, it indicates that the current thread is a writer thread. Then count the number of current reentries. If it is saturated, an exception will be thrownif (w + exclusiveCount(acquires) > MAX_COUNT)
                    throw new Error("Maximum lock count exceeded"); // (2.3) The write status is directly recordedsetState(c + acquires);
                return true; } // (3) There is no thread to acquire read/write lock, according to the current lock mode and set write status is successful, determine whether to block threadif(writerShouldBlock() || ! compareAndSetState(c, c + acquires))return false; //(4) The first entry is successfulsetExclusiveOwnerThread(current);
            return true;
        }
Copy the code

To help you understand, I’ve broken it down into the following steps:

  • (1) Obtain the synchronization statusc(Write state + read state), and gets the write state separatelyw.
  • (2) Ifc! = 0It indicates that there is a thread operation.
  • (2.1) If there is no write lock thread, it indicates that there is a read thread.
  • (2.2) Ifw>0Then, indicates that the current thread is the writer thread, and the number of current reentry times is calculated. If it is saturated,Throws an exception.
  • (2.3) Record the current write status.
  • (3) If conditions (2) are not met, no thread can acquire read/write lock, and the thread needs to be blocked according to the mode of the current lock and whether the write state is set successfully
  • (4) If the conditions (2) and (3) are not met, it is the first time to enter, and success will be obtained.

Believe in combining the above steps. It’s easy to understand the code again.

Lock down

Read-write lock guarantees to write operation on the visibility of the read operation and improve concurrency, the read-write lock can also simplify the programming of reading and writing interact way, think of a situation, in the program we need to define a Shared for caching data structures, and read the services it provides most of the time (for example, query and search), and write operations have very little time, But we want updates after the write operation to be visible to subsequent reads. So how do you do that? See the following example:

public class CachedData {
    Object data;
    volatile boolean cacheValid;
    final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
    
    void processCachedData() {
        rwl.readLock().lock();
        if(! CacheValid) {// if the cache expires, release the readLock and acquire the write lock rwl.readlock ().unlock(); rwl.writeLock().lock(); (1) try {// Recheck whether the cache is out of date, because it is possible that other writer threads may change the cache state before the current thread operatesif(! cacheValid) { data = ... // Rewrites data to cacheValid =true; } // get the readLock rwl.readlock ().lock(); (2)} finally {// release writeLock rwl.writelock ().unlock(); (3)}} try {use(data); } finally {rwl.readlock ().unlock(); // Finally release read lock}}}Copy the code

In the example above, if the data cache expires and the cacheValid variable (volatile modified Boolean) is set to false, all threads calling processCachedData () will be aware of the change, but only one thread will acquire the write lock. Other threads block on lock() methods that read and write locks. After the current thread acquires the write lock, it acquires the read lock, and then releases the write lock (steps (1), (2), and (3) of the code above). The subsequent process of releasing the write lock is called lock degradation (lock degradation is supported in the internal implementation of the read/write lock).

The next question I would like to ask you is, why does a thread acquire a write lock after modifying data, instead of releasing the write lock directly? In fact, the reason is very simple, if the current thread directly release the write lock, then at this time if another thread has acquired the write lock, and modify the data. The thread that currently releases the write lock is not aware of the data change. The purpose of obtaining the read lock first is to ensure that no other thread will modify the data.

conclusion

  • ReentrantReadWriteLock supports a maximum of65535A recursive write lock sum65535A read lock.
  • ReentrantReadWriteLock is the sameintThe variableHigh 16saidRead the state.The low 16 bitssaidWrite status.
  • ReentrantReadWriteLock supports fair and unfair lock modes.
  • ReentrantReadWriteLock Supports lock degradation.