preface

The ReentrantLock mentioned earlier is an exclusive lock that allows only one thread to access at a time, whereas a read-write lock allows multiple reader threads to access at a time, but all reader threads and other writer threads are blocked when the writer thread accesses it. Read-write locks maintain a pair of locks, a read lock and a write lock. By separating the read lock and the write lock, concurrency is greatly improved compared to the general exclusive lock.

features

Fair selection

Enforce unfair (default) and fair lock acquisition, throughput unfair takes precedence over fair.

reenter

Support for re-entry: After a reader thread has acquired a read lock, it can acquire the read lock again. After acquiring the write lock, the writer thread can acquire the write lock again and also acquire the read lock.

Lock down

A write lock can be degraded to a read lock by following the sequence of acquiring a write lock, acquiring a read lock, and releasing a write lock.

ReentrantReadWriteLock class diagram

ReadWriteLock interface

As you can see, ReentrantReadWriteLock implements the ReadWriteLock interface.

public interface ReadWriteLock {
    Lock readLock();
    Lock writeLock();
}
Copy the code

This interface defines only two methods that return read and write locks.

Relationship between Sync and Lock

As you can see, the Sync synchronization class implements the AQS abstract class. ReentrantReadWriteLock is also implemented based on AQS.

Like ReentrantLock, Sync has two subclasses, FairSync (fair lock) and NonfairSync (non-fair lock).

ReadLock and WriteLock implement the Lock interface while maintaining a reference to Sync.

An inner class of Sync

HoldCounter is used primarily with read locks.

        static final class HoldCounter {
            int count = 0;
            final long tid = getThreadId(Thread.currentThread());
        }
Copy the code

HoldCounter has two main attributes, count and tid, where count represents the number of times a reader thread reenters and tid represents the value of the tid field of the thread, which can be used to uniquely identify a thread.

ThreadLocalHoldCounter overrides the initialValue method of ThreadLocal, the ThreadLocal class that associates threads with objects. In the absence of a set, all you get is the HolderCounter object generated in the initialValue method.

static final class ThreadLocalHoldCounter
    extends ThreadLocal<HoldCounter> {
    public HoldCounter initialValue() {
        returnnew HoldCounter(); }}Copy the code

Sync

Let’s start with the basics and most important Sync.

attribute

Private static Final Long serialVersionUID = 6317671515068378041L; Static final int SHARED_SHIFT = 16; 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; // Private TRANSIENT ThreadLocalHoldCounterreadHolds; Private TRANSIENT HoldCounter cachedHoldCounter; Private TRANSIENT Thread firstReader = null; Private TRANSIENT int firstReaderHoldCount; private TRANSIENT int firstReaderHoldCount;Copy the code

It mainly defines the design of read and write states.

The constructor

Sync() {
    readHolds = new ThreadLocalHoldCounter();
    setState(getState()); // ensures visibility of readHolds
}
Copy the code

Design of read and write states

The synchronization status in the reentrant lock implementation is the number of times it is repeatedly acquired by the same thread, i.e. maintained by an integer variable, but the previous representation only indicates whether the lock is locked, not whether it is read or write. Read/write locks need to maintain the state of multiple readers and one writer on a synchronous state (an integer variable).

Read/write locks are implemented in a synchronous state by “bitwise cutting” on an integer variable: the variable is cut in two, with 16 bits higher indicating read and 16 bits lower indicating write.

Assuming that the current synchronization status is S, the operations of get and set are as follows:

  • Get write status: S&0x0000FFFF: Erase all the high 16 bits

  • Get read status: S>>>16: unsigned complement 0, move 16 bits right

  • Write state +1: S+1

  • Read status plus 1: S+ (1<<16) that is, S+ 0x00010000

In the code level judgment, if S is not equal to 0, when the write state (S&0x0000FFFF) and the read state (S>>>16) is greater than 0, it indicates that the read lock of the read/write lock has been acquired.

TryAcquire write lock acquisition

Protected final Boolean tryAcquire(int acquires) {tryAcquire current = thread.currentThread (); Int c = getState(); Int w = exclusiveCount(c); // If the resource has already been acquired (read lock acquired or write lock acquired)if(c ! = 0) {// If the reentrant count of the write lock is 0 or the current thread is not an exclusive thread and returns an attempt to acquire the resource. // If the resource count of the write lock is not 0, it indicates that the read lock did not acquire the resourceif(w == 0 || current ! = getExclusiveOwnerThread())return false; // If the number of reentrants plus the resources to be retrieved is greater than the maximum number of reentrants, an exception is thrownif (w + exclusiveCount(acquires) > MAX_COUNT)
                    throw new Error("Maximum lock count exceeded"); // If the number of resources obtained is greater than 0 and is from the current thread, set the number of resourcessetState(c + acquires);
                return true; } // if c == 0, write lock and read lock are not acquired. // writerShouldBlock determines whether a block is needed (fair and unfair locks are implemented differently) // If not, CAS attempts to acquire the resourceif(writerShouldBlock() || ! CompareAndSetState (c, c + acquires)) // If the resource fails to be obtainedfalseIt indicates that the system fails to obtain resources and enters the AQS queue to wait for obtaining locksreturn false; Set the current thread to an exclusive threadsetExclusiveOwnerThread(current);
            return true;
        }
Copy the code
  • First get the number of resources that have been occupied c (read and write locks)
  • Then get the number of resources occupied by the write lock w (reentrant)
  • If the number of occupied resources c is not 0, the system checks whether the current thread has obtained the resources
    • Return false if the resource w occupied by the write lock is 0 (if another read lock is occupying the resource).
    • If w is not zero, but the exclusive thread is not the current thread, false is also returned.
    • If w is not 0 and the current thread is an exclusive thread, but the number of resources to be acquired plus the number of resources that have been acquired is greater than the maximum number of resources to be acquired, false is returned.
    • If the number of resources occupied by the write lock is not 0 and the current thread is an exclusive thread, and the number of resources obtained is smaller than the maximum number of resources, reset the number of resources obtained, and return true.
  • If the number of occupied resources c is 0, no lock (read lock, write lock) has acquired the resource.
    • This method returns false to determine whether blocking is required (fair or unfair), and false to determine whether another thread acquired the lock resource before the current thread.
    • If the CAS mode is used to change the number of resources obtained, false is returned if obtaining the resources fails.
  • If c is 0 and CAS succeeded in changing the number of resources, the current thread is set to the exclusive thread and returns true.

The flow chart is as follows:

ExclusiveCount Exclusive reentrant number of write locks

static int exclusiveCount(int c) { return c & EXCLUSIVE_MASK; }
Copy the code

The lower 16 bits represent write locks.

TryRelease Release of the write lock

Protected Final Boolean tryRelease(int Releases) {// If the current thread is not an exclusive thread, throw an exceptionif(! isHeldExclusively()) throw new IllegalMonitorStateException(); Int nexTC = getState() -releases; boolean free = exclusiveCount(nextc) == 0; // If the total resources released are equal to 0if(free) // Sets the exclusive thread to NULLsetExclusiveOwnerThread(null); // Set the total resources after releasesetState(nextc); // Returns whether to release the lockreturn free;
        }
Copy the code

TryRelease is simple, so I won’t go over it.

TryAcquireShared Obtain the read lock

Protected final int tryAcquireShared(int unused) {Thread current = thread.currentThread (); Int c = getState(); // If an exclusive (write lock) access to resources is not 0if(exclusiveCount(c) ! GetExclusiveOwnerThread ()! GetExclusiveOwnerThread ()! = current) // Return -1return- 1; Int r = sharedCount(c); // Determine whether the read needs to be blocked (fair and unfair locks) // If it does not need blockingif(! ReaderShouldBlock () && r < MAX_COUNT && and // CAS set resource count successfully compareAndSetState(c, C + SHARED_UNIT)) {// if r==0, the current thread is the first thread to acquire the read lockif(r == 0) {// Then the first thread to acquire the lock is set to the current thread firstReader = current; FirstReaderHoldCount = 1; firstReaderHoldCount = 1; }else if(firstReader == current) {// if the current thread is the first thread to acquire the read lock, the number of resources occupied by the firstReader thread ++ firstReaderHoldCount++; }else{// The number of read locks is not 0 and the first thread to acquire the read lock is not the current thread // Obtain the counter HoldCounter rh = cachedHoldCounter; // If the counter is null or the tid of the counter is not the TID of the currently running threadif(rh == null || rh.tid ! = getThreadId(current)) // Get the current thread counter cachedHoldCounter = rh =readHolds.get(); // If the count is 0else if(rh.count == 0) // Set the counter to ThreadLocalreadHolds.set(rh); // count+ 1 rh.count++; } // return 1return 1;
            }
            return fullTryAcquireShared(current);
        }
Copy the code
  • Get current thread
  • Obtain the number of occupied resources
  • Check whether the write lock is owned by another thread. If so, return -1
    • Check whether the number of resources occupied by write locks is 0
    • If the number of resources occupied by the write lock is not 0, the system checks whether the current thread has the exclusive write lock
  • Obtain the number of resources occupied by the read lock
  • Determine whether resources can be obtained and obtain resources
    • Determine whether blocking is required (fair and unfair locks)
    • Check whether the number of write lock resources is less than the maximum number of write lock resources.
    • CAS attempts to obtain resources
  • The number of threads reentrant is recorded if the resource is successfully fetched
    • If r==0, the current thread is the first thread to acquire the read lock
      • Set the first thread that acquires the read lock (firstReader) to the current thread
      • Set firstReaderHoldCount to 1
    • If r is not 0, it determines whether the current thread is the first thread to acquire the read lock
      • If it is the first thread to acquire the read lock, the number of resources held by the first reader thread (firstReaderHoldCount) is increased by 1
    • If r is not 0 and the current thread is not the first thread to acquire the lock
      • Get cache counter
      • Determines if the cache counter is a counter for the current thread, and if not, gets the current thread’s counter
      • If the cache counter is the current thread’s counter, determine if count is 0, and if it is 0, set it to readHolds
      • The final count will be +1
  • If you need to block or fail to get the resource number, the fullTryAcquireShared loop is called to get the resource.

After a successful update, the current thread reentrancecount is recorded in firstReaderHoldCount or readHolds(of type ThreadLocal) in the local thread copy. This is to implement the getReadHoldCount() method added in JDK1.6. This method gets the number of times the current thread re-entered the shared lock (state is the total number of threads re-entered). Adding this method makes the code a bit more complicated, but the principle is simple: If there is only one thread, you do not need to use the ThreadLocal to store the reentrant value directly into the firstReaderHoldCount member. When a second thread approaches, you need to use the ThreadLocal readHolds variable. Each thread has its own replica. Used to store its own reentrant number.

The fullTryAcquireShared loop obtains the read lock

In the tryAcquireShared function, if the following three conditions are not met (should the reader thread be blocked, less than the maximum value, and the comparison set successful) then the fullTryAcquireShared function is used to ensure that the operation succeeds.

Final Int fullTryAcquireShared(Thread Current) {// Counter HoldCounter RH = null;for(;;) Int c = getState(); // If the number of resources occupied by the write lock is not 0if(exclusiveCount(c) ! = 0) {// If the current thread does not acquire the write lockif(getExclusiveOwnerThread() ! = current)return- 1; // If you need to block}else if(readerShouldBlock()) {// If the first thread to acquire the read lock is the current threadif (firstReader == current) {
                    
                } else{// If the counter is nullif(rh == null) {// Get the cache counter rh = cachedHoldCounter; // If the counter is null or not the current thread counterif(rh == null || rh.tid ! = getThreadId(current)) {// Get current thread counter rh =readHolds.get(); // If the current thread read lock count is 0if(rh.count == 0) // Delete the current thread counterreadHolds.remove(); }} // Returns -1 if the current thread count is 0if (rh.count == 0)
                    return- 1; }} // If the number of resources occupied by the read lock is equal to the maximum number of resourcesif(sharedCount(c) == MAX_COUNT)"Maximum lock count exceeded"); // Cas is used to obtain read lock resourcesif(compareAndSetState(c, c + SHARED_UNIT)) {// If the thread is the first to acquire the read lockif (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; 
            }
            return1; }}}Copy the code

Add threadLocal cleanup to the tryAcquireShared method, which essentially circulates the read lock.

  • Check whether the number of resources (r) occupied by write locks is 0
    • If r is not 0, check whether the write lock is occupied by the current thread. If r is not the current thread, return -1
    • If r is 0, no thread is currently holding the write lock, then determine whether blocking is required (fair and unfair)
      • If blocking is required, the current thread is determined to be the first thread to acquire the read lock
      • If the current thread is not the first thread to acquire the read lock, then determine whether the current thread has acquired the read lock.
      • If the current thread is not holding the read lock (no re-entry), you need to clear threadLocal and return -1
    • If r is not 0 and is the write lock occupied by the current thread, or if r is 0, no blocking is required
      • If the number of read locks is equal to the maximum, an exception is thrown directly
      • Obtain read lock resources in Cas mode
      • If the resource is obtained successfully, the number of resources occupied by the thread is recorded using such methods as threadLocal

TryReleaseShared Read lock release

Protected final Boolean tryReleaseShared(int unused) {tryReleaseShared = thread.currentThread (); // If the first thread to acquire the read lock is the current threadif(firstReader == current) {// If the first thread to acquire the read lock reentrant is 1if(firstReaderHoldCount == 1) // Set the first thread to acquire the read lock to null.elseFirstReaderHoldCount = firstReaderHoldCount; }else{// Get the cache counter HoldCounter rh = cachedHoldCounter; // If the cache counter points to something other than the current threadif(rh == null || rh.tid ! GetThreadId (current)) // Get the cache counter rh = from threadLocalreadHolds.get(); Int count = rh.count; // If the reentrant is less than or equal to 1if(count <= 1) {// Clear threadLocalreadHolds.remove(); If less than or equal to 0, an exception is thrownif(count <= 0) throw unmatchedUnlockException(); } // Reentrant count -1 --rh.count; }for(;;) { int c = getState(); int nextc = c - SHARED_UNIT; // Release resources in CAS modeif (compareAndSetState(c, nextc))
                    returnnextc == 0; }}Copy the code

There are only two steps to release a read lock:

  • 1, the current thread counter count is -1, if the number of records is 0, the threadLocal is cleared
  • ReentrantLock is different from ReentrantLock. Multiple threads may share the read lock. Therefore, for loop and CAS are used to release the read lock.

GetReadHoldCount Gets the reentrant count of the current thread’s read lock

        final int getReadHoldCount() {
            if (getReadLockCount() == 0)
                return 0;

            Thread current = Thread.currentThread();
            if (firstReader == current)
                return firstReaderHoldCount;

            HoldCounter rh = cachedHoldCounter;
            if(rh ! = null && rh.tid == getThreadId(current))return rh.count;

            int count = readHolds.get().count;
            if (count == 0) readHolds.remove();
            return count;
        }
Copy the code

Relatively simple, not a comment code.

  • Check whether the usage of the status resource read lock in the CAS server is 0. If the usage is 0, return 0.
  • If the value is not 0, the current thread is the first thread to acquire the read lock
  • If not, the cached counter thread ID is the current thread
  • Still not? You’ll have to look in threadLocal

Why not put it all in threadLocal?

  • A threadLocal is actually a map, and if only one thread acquires the read lock, there is no need to put it into a ThreadLocal to reduce efficiency.

Why does a HoldCounter record the thread ID instead of pointing directly to the current thread?

  • To avoid binding HoldCounter and ThreadLocal to each other and making it difficult for the GC to release them (although the GC can be smart enough to find such references and reclaim them, there is a price to pay), this is just to help the GC reclaim the object quickly.

ReentrantReadWriteLock

The constructor

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

As you can see, the ReentrantReadWriteLock construct constructs fair and unfair locks in different cases.

FairSync

    static final class FairSync extends Sync {
        private static final long serialVersionUID = -2274990926593161451L;
        final boolean writerShouldBlock() {
            return hasQueuedPredecessors();
        }
        final boolean readerShouldBlock() {
            returnhasQueuedPredecessors(); }}Copy the code

The writerShouldBlock, readerShouldBlock methods call the HasqueuedTorawithaQS to determine whether a wired program obtains the lock before the current thread.

NonfairSync

    static final class NonfairSync extends Sync {
        private static final long serialVersionUID = -8159625535654395037L;
        final boolean writerShouldBlock() {
            return false; // writers can always barge
        }
        final boolean readerShouldBlock() {
            returnapparentlyFirstQueuedIsExclusive(); }}Copy the code

As you can see, the writerShouldBlock method returns false directly. In tryAcquire, Cas attempts to acquire the resource directly. ReaderShouldBlock calls the AQS apparentlyFirstQueuedIsExclusive method.

apparentlyFirstQueuedIsExclusive

    final boolean apparentlyFirstQueuedIsExclusive() {
        Node h, s;
        return(h = head) ! = null && (s = h.next) ! = null && ! s.isShared() && s.thread ! = null; }Copy the code

Returning true requires the following conditions:

  • If the head node is not null
  • The next node of the head node is not null
  • The next node of the head node is not shared
  • The thread next to the head node is not null

This method determines whether the queue’s head.next is waiting for an exclusive lock (write lock).

The official explanation is that a read lock should not keep a write lock waiting, causing the write lock thread to starve.

ReadLock constructor

    protected ReadLock(ReentrantReadWriteLock lock) {
        sync = lock.sync;
    }
Copy the code

WriteLock constructor

    protected WriteLock(ReentrantReadWriteLock lock) {
        sync = lock.sync;
    }
Copy the code

It’s easy. There’s nothing to talk about.

conclusion

If a thread holds a read lock, the thread cannot acquire a write lock (because when acquiring a write lock, if the current read lock is found to be occupied, the acquisition fails immediately, regardless of whether the read lock is held by the current thread).

If a thread holds a write lock, the thread can continue to acquire the read lock (if the write lock is occupied, it will fail to acquire the read lock only if the write lock is not occupied by the current thread).

reference

  • The art of Concurrent programming in Java
  • ReentrantReadWriteLock Description of a read/write lock