1, Introduction to read-write lock

In reality, there is such a scenario: there are read and write operations on shared resources, and write operations are not as frequent as read operations. When there is no write operation, there is no problem for multiple threads to read a resource at the same time, so multiple threads should be allowed to read shared resources at the same time; However, if a thread wants to write these shared resources, it should not allow other threads to read and write to the resource.

For this scenario, JAVA's concurrent package provides a read-write lock ReentrantReadWriteLock, which represents two locks. One is a lock related to a read operation, which is called a shared lock; One is a write related lock, called an exclusive lock, which is described as follows:

• Preconditions for a thread to enter lock reading:

  • There are no write locks for other threads.

  • There is no write request or {there is a write request, but the calling thread and the thread holding the lock are the same.

• Prerequisites for a thread to enter a write lock:

  • There are no read locks for other threads.

  • There are no write locks for other threads.

The read-write lock has the following three important characteristics:

(1) Fair selectivity: supports unfair (default) and fair lock acquisition methods. Throughput is still unfair rather than fair.

(2) Reentry: both read lock and write lock support thread reentry.

(3) Lock demotion: follow the sequence of obtaining a write lock, obtaining a read lock, and then releasing a write lock. A write lock can be demoted to a read lock.

2, Source code interpretation

Let's first look at the overall structure of the ReentrantReadWriteLock class:

public class ReentrantReadWriteLock implements ReadWriteLock, java.io.Serializable {

    /** Read lock */
    private final ReentrantReadWriteLock.ReadLock readerLock;

    /** Write lock */
    private final ReentrantReadWriteLock.WriteLock writerLock;

    final Sync sync;
    
    /** Create a new ReentrantReadWriteLock using the default (unfair) sort property */
    public ReentrantReadWriteLock() {
        this(false);
    }

    /** Create a new ReentrantReadWriteLock using the given fairness policy */
    public ReentrantReadWriteLock(boolean fair) {
        sync = fair ? new FairSync() : new NonfairSync();
        readerLock = new ReadLock(this);
        writerLock = new WriteLock(this);
    }

    /** Returns the lock used for the write operation */
    public ReentrantReadWriteLock.WriteLock writeLock() { return writerLock; }
    
    /** Returns the lock used for the read operation */
    public ReentrantReadWriteLock.ReadLock  readLock()  { return readerLock; }


    abstract static class Sync extends AbstractQueuedSynchronizer {}

    static final class NonfairSync extends Sync {}

    static final class FairSync extends Sync {}

    public static class ReadLock implements Lock, java.io.Serializable {}

    public static class WriteLock implements Lock, java.io.Serializable {}
}

1. Class inheritance

public class ReentrantReadWriteLock
        implements ReadWriteLock, java.io.Serializable {}

Note: it can be seen that ReentrantReadWriteLock implements the ReadWriteLock interface, which defines the specifications for obtaining read locks and write locks, which need to be implemented by implementation classes; At the same time, it also implements the Serializable interface, which means that it can be serialized. You can see in the source code that ReentrantReadWriteLock implements its own serialization logic.

2. Inner class of class

ReentrantReadWriteLock has five inner classes, and the five inner classes are also interrelated. The relationship between internal classes is shown in the following figure.

img

Note: as shown in the above figure, Sync inherits from AQS, NonfairSync inherits from Sync class, FairSync inherits from Sync class (the Boolean value passed in by the constructor determines which Sync instance to construct); ReadLock implements the Lock interface and WriteLock also implements the Lock interface.

Sync class:

(1) Class inheritance

abstract static class Sync extends AbstractQueuedSynchronizer {}

Note: the Sync abstract class inherits from the AQS abstract class. The Sync class provides support for ReentrantReadWriteLock.

(2) Inner class of class

There are two internal classes in Sync class, HoldCounter and ThreadLocalHoldCounter. HoldCounter is mainly used with read lock. The source code of HoldCounter is as follows.

// Counter
static final class HoldCounter {
    // count
    int count = 0;
    // Gets the value of the TID property of the current thread
    final long tid = getThreadId(Thread.currentThread());
}

Note: HoldCounter mainly has two attributes, count and tid, where count represents the number of reentries of a read thread and tid represents the value of the TID field of the thread, which can be used to uniquely identify a thread. The source code of ThreadLocalHoldCounter is as follows

// Local thread counter
static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> {
    // Override the initialization method, and get the HoldCounter value without set ting
    public HoldCounter initialValue() {
        return new HoldCounter();
    }
}

Description: ThreadLocalHoldCounter overrides the initialValue method of ThreadLocal. ThreadLocal class can associate threads with objects. In the case of no set, the HolderCounter object generated in the initialValue method is obtained.

(3) Properties of class

abstract static class Sync extends AbstractQueuedSynchronizer {
    // Version serial number
    private static final long serialVersionUID = 6317671515068378041L;        
    // The upper 16 bits are read locks and the lower 16 bits are write locks
    static final int SHARED_SHIFT   = 16;
    // Lock reading unit: the number of locks read plus 1 is state+SHARED_UNIT
    static final int SHARED_UNIT    = (1 << SHARED_SHIFT);
    // Maximum number of read locks
    static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
    // Maximum number of write locks
    static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;
    // Local thread counter
    private transient ThreadLocalHoldCounter readHolds;
    // Cached counters
    private transient HoldCounter cachedHoldCounter;
    // First read thread
    private transient Thread firstReader = null;
    // Count of the first read thread
    private transient int firstReaderHoldCount;
}

Note: this attribute includes the maximum number of read lock and write lock threads. Local thread counters, etc.

(4) Class constructor

// Constructor
Sync() {
    // Local thread counter
    readHolds = new ThreadLocalHoldCounter();
    // Set AQS status
    setState(getState()); // ensures visibility of readHolds
}

Note: set the local thread counter and AQS state in the Sync constructor.

3. Design of read-write state

In the implementation of reentry lock, the synchronization state represents the number of times repeatedly obtained by the same thread, that is, it is maintained by an integer variable, but the previous representation only represents whether it is locked, without distinguishing whether it is a read lock or a write lock. The read-write lock needs to maintain the state of multiple read threads and one write thread in the synchronous state (an integer variable).

The implementation of read-write lock for synchronous state is through "bit cutting" on a shaping variable: the variable is cut into two parts, the high 16 bits represent read and the low 16 bits represent write.

http://static.open-open.com/lib/uploadImg/20151031/20151031223319_397.png

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

(1) Get write status:

S & 0x0000ffff: erase all the upper 16 bits

(2) Get read status:

S> > > 16: unsigned complement 0, shift right 16 bits

(3) Write status plus 1:

S+1

(4) Read status plus 1:

S + (1 < < 16) i.e. S + 0x00010000

In the judgment of the code layer, if s is not equal to 0, when the write state (S & 0x0000ffff) and the read state (s > > > 16) are greater than 0, it indicates that the read lock of the read-write lock has been obtained.

4. Acquisition and release of write lock

Look at the lock and unlock methods in the WriteLock class:

public void lock() {
    sync.acquire(1);
}

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

You can see the acquisition and release of the exclusive synchronization state of the call, so the real implementation is tryAcquire and tryRelease of Sync.

To obtain a write lock, see tryAcquire:

 1 protected final boolean tryAcquire(int acquires) {
 2     //Current thread
 3     Thread current = Thread.currentThread();
 4     //Get status
 5     int c = getState();
 6     //Number of write threads (i.e. the number of reentries to acquire exclusive locks)
 7     int w = exclusiveCount(c);
 8     
 9     //Current synchronization state= 0, indicating that another thread has obtained a read lock or write lock
10     if (c != 0) {
11         // If the current state is not 0 and the write lock status is 0, it indicates that the read lock is occupied and returns false;
12         // If the write lock status is not 0 and the write lock is not held by the current thread, false is returned
13         if (w == 0 || current != getExclusiveOwnerThread())
14             return false;
15         
16         //Judge whether the same thread obtains the write lock more than the maximum number of times (65535), and support reentrant
17         if (w + exclusiveCount(acquires) > MAX_COUNT)
18             throw new Error("Maximum lock count exceeded");
19         //Update status
20         //At this time, the current thread has a write lock and is now reentrant, so you only need to modify the number of locks.
21         setState(c + acquires);
22         return true;
23     }
24     
25     //Here it is explained that at this time, c=0, the read lock and write lock are not obtained
26     //writerShouldBlock indicates whether it is blocked
27     if (writerShouldBlock() || !compareAndSetState(c, c + acquires))
29         return false;
30     
31     //Set the lock to be owned by the current thread
32     setExclusiveOwnerThread(current);
33     return true;
34 }

The exclusiveCount method indicates the number of threads occupying the write lock. The source code is as follows:

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

Note: directly sum the States State and (2 ^ 16 - 1), which is equivalent to 2 ^ 16 on the state module. The number of write locks is represented by the lower sixteen bits of state, which is equivalent to erasing all the high bits.

As can be seen from the source code, the steps to obtain the write lock are as follows:

(1) First obtain c and w. c represents the current lock status; w represents the number of write threads. Then judge whether the synchronization status state is 0. If state!=0, it indicates that other threads have obtained read or write locks. Execute (2); Otherwise, execute (5).

(2) If the lock status is not zero (c! = 0) and the write lock status is 0 (w = 0), it means that the read lock is occupied by other threads at this time, so the current thread cannot obtain the write lock and naturally returns false. Or if the lock status is not zero and the write lock status is not 0, but the thread obtaining the write lock is not the current thread, the current thread cannot obtain the write lock.

(3) Judge whether the current thread has obtained the write lock more than the maximum number of times. If so, throw an exception, otherwise update the synchronization status (at this time, the current thread has obtained the write lock, and the update is thread safe), and return true.

(4) If the state is 0, neither the read lock nor the write lock is obtained. Judge whether blocking is required (fair and unfair methods are different). It will not be blocked under the unfair policy, and judge under the fair policy (judge whether there are threads waiting longer in the synchronization queue. If there are threads, they need to be blocked; otherwise, they do not need to be blocked). If blocking is not required, CAS updates the synchronization status. If CAS succeeds, it returns true. If CAS fails, it indicates that the lock has been robbed by other threads, and returns false. If blocking is required, it also returns false.

(5) After successfully obtaining the write lock, set the current thread as the thread occupying the write lock, and return true.

The method flow chart is as follows:

img

Release of write lock, tryRelease method:

 1 protected final boolean tryRelease(int releases) {
 2     //If the lock holder is not the current thread, an exception is thrown
 3     if (!isHeldExclusively())
 4         throw new IllegalMonitorStateException();
 5     //Number of new threads to write lock
 6     int nextc = getState() - releases;
 7     //If the exclusive mode reentry number is 0, the exclusive mode is released
 8     boolean free = exclusiveCount(nextc) == 0;
 9     if (free)
10         //If the number of new threads of the write lock is 0, the lock holder is set to null
11         setExclusiveOwnerThread(null);
12     //Sets the number of new threads to write lock
13     //Update exclusive reentry count whether exclusive mode is released or not
14     setState(nextc);
15     return free;
16 }

The release process of write lock is relatively simple: first, check whether the current thread is the holder of write lock, if not throw an exception. Then check whether the number of threads writing the lock after release is 0. If it is 0, it means that the write lock is idle. Release the lock resource and set the lock holding thread to null. Otherwise, releasing the lock is only a re-entry lock and cannot empty the write lock thread.

Note: this method is used to release write lock resources. First, it will judge whether the thread is exclusive. If it is not exclusive, an exception will be thrown. Otherwise, the number of write locks after releasing resources will be calculated. If it is 0, it indicates that the resources are successfully released and will not be occupied. Otherwise, it indicates that the resources are still occupied. The method flow chart is as follows.

img

5. Acquisition and release of read lock

Similar to write lock and read lock, the actual implementation of lock and unlock corresponds to the tryAcquireShared and tryrereleaseshared methods of Sync.

For the acquisition of read lock, see the tryAcquireShared method

 1 protected final int tryAcquireShared(int unused) {
 2     // Get current thread
 3     Thread current = Thread.currentThread();
 4     // Get status
 5     int c = getState();
 6     
 7     //If the number of write lock threads= 0, and the exclusive lock is not the current thread, a failure is returned because there is a lock degradation
 8     if (exclusiveCount(c) != 0 && getExclusiveOwnerThread() != current)
10         return -1;
11     // Number of read locks
12     int r = sharedCount(c);
13     /*
14      * readerShouldBlock():Whether to wait for lock reading (fair lock principle)
15      * r < MAX_COUNT: The number of threads held is less than the maximum (65535)
16      * compareAndSetState(c, c + SHARED_UNIT): Set read lock status
17      */
18      // Whether the read thread should be blocked, less than the maximum value, and the comparison setting is successful
19     if (!readerShouldBlock() && r < MAX_COUNT && compareAndSetState(c, c + SHARED_UNIT)) {
22         //r == 0 indicates the first read lock thread. The first read lock firstRead will not be added to readHolds
23         if (r == 0) { // The number of read locks is 0
24             // Set first read thread
25             firstReader = current;
26             // The number of resources occupied by the read thread is 1
27             firstReaderHoldCount = 1;
28         } else if (firstReader == current) { // The current thread is the first read thread, indicating that the first read lock thread re enters
29             // Number of resources occupied plus 1
30             firstReaderHoldCount++;
31         } else { // The number of read locks is not 0 and is not the current thread
32             // Get counter
33             HoldCounter rh = cachedHoldCounter;
34             // The counter is empty or the tid of the counter is not the tid of the currently running thread
35             if (rh == null || rh.tid != getThreadId(current)) 
36                 // The existence of the cachedHoldCounter corresponding to the current thread is to provide performance. For example, it is thread A for the first time,
                   // readHolds.get() once, and then assign it to cachedHoldCounter. On the second time, cachedHoldCounter
                   // What is saved is the current thread, so you don't have to read holds again Get() because readholds Get () is a time-consuming operation.)
37                 cachedHoldCounter = rh = readHolds.get();
38             else if (rh.count == 0) // The count is 0
39                 //Add to readHolds
40                 readHolds.set(rh);
41             //Count + 1
42             rh.count++;
43         }
44         return 1;
45     }
46     return fullTryAcquireShared(current);
47 }

The sharedCount method indicates the number of threads occupying the read lock. The source code is as follows:

static int sharedCount(int c)    { return c >>> SHARED_SHIFT; }

Note: by directly moving the state to the right by 16 bits, you can get the number of threads reading locks, because the high 16 bits of state represent read locks and the corresponding 16th bit represents the number of write locks.

The process of obtaining a lock from a read lock is slightly more complicated than that from a write lock. First, judge whether the write lock is 0 and the current thread does not occupy the exclusive lock and returns directly; Otherwise, judge whether the read thread needs to be blocked and whether the number of read locks is less than the maximum value, and compare the setting status successfully. If there is no read lock at present, set the first read thread firstReader and firstReaderHoldCount; If the current thread is the first reading thread, increase firstReaderHoldCount; Otherwise, the value of the HoldCounter object corresponding to the current thread will be set. The flow chart is as follows.

img

Note: after the update is successful, the current thread reentry number (23 lines to 43 lines of code) will be recorded in the firstReaderHoldCount or in the thread copy of readHolds(ThreadLocal type). This is to implement the getReadHoldCount() method added in jdk1.6. This method can obtain the current thread's number of reentry into the shared lock (the state records the total number of reentry times of multiple threads), Adding this method makes the code a lot more complicated, but its principle is still very simple: if there is only one thread at present, you don't need to use ThreadLocal. You can directly save the re-entry number into the member variable firstReaderHoldCount. When a second thread comes, you need to use the ThreadLocal variable readHolds. Each thread has its own copy, Used to save your own reentrant number.

fullTryAcquireShared method:

final int fullTryAcquireShared(Thread current) {

    HoldCounter rh = null;
    for (;;) { // Infinite loop
        // Get status
        int c = getState();
        if (exclusiveCount(c) != 0) { // The number of write threads is not 0
            if (getExclusiveOwnerThread() != current) // Not for current thread
                return -1;
        } else if (readerShouldBlock()) { // The number of write threads is 0 and the read thread is blocked
            // Make sure we're not acquiring read lock reentrantly
            if (firstReader == current) { // The current thread is the first read thread
                // assert firstReaderHoldCount > 0;
            } else { // The current thread is not the first read thread
                if (rh == null) { // Counter is not empty
                    // 
                    rh = cachedHoldCounter;
                    if (rh == null || rh.tid != getThreadId(current)) { // The counter is empty or the tid of the counter is not the tid of the currently running thread
                        rh = readHolds.get();
                        if (rh.count == 0)
                            readHolds.remove();
                    }
                }
                if (rh.count == 0)
                    return -1;
            }
        }
        if (sharedCount(c) == MAX_COUNT) // If the number of read locks is the maximum, an exception is thrown
            throw new Error("Maximum lock count exceeded");
        if (compareAndSetState(c, c + SHARED_UNIT)) { // Compare and set successfully
            if (sharedCount(c) == 0) { // The number of read threads is 0
                // Set first read thread
                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;
        }
    }
}

Note: in the tryAcquireShared function, if the following three conditions are not met (whether the read thread should be blocked, less than the maximum value, and the comparison setting is successful), it will be fullTryAcquireShared. In the tryAcquireShared function, it is used to ensure the success of relevant operations. Its logic is similar to tryAcquireShared logic and is no longer cumbersome.

Release of read lock, tryrereleaseshared method

 1 protected final boolean tryReleaseShared(int unused) {
 2     // Get current thread
 3     Thread current = Thread.currentThread();
 4     if (firstReader == current) { // The current thread is the first read thread
 6         if (firstReaderHoldCount == 1) // The number of resources occupied by the read thread is 1
 7             firstReader = null;
 8         else // Reduce occupied resources
 9             firstReaderHoldCount--;
10     } else { // The current thread is not the first read thread
11         // Get cached counters
12         HoldCounter rh = cachedHoldCounter;
           // The counter is empty or the tid of the counter is not the tid of the currently running thread
13         if (rh == null || rh.tid != getThreadId(current)) 
14             // Gets the counter corresponding to the current thread
15             rh = readHolds.get();
16         // Get count
17         int count = rh.count;
18         if (count <= 1) { // Count less than or equal to 1
19             // remove
20             readHolds.remove();
21             if (count <= 0) // If the count is less than or equal to 0, an exception is thrown
22                 throw unmatchedUnlockException();
23         }
24         // Decrease count
25         --rh.count;
26     }
27     for (;;) { // Infinite loop
28         // Get status
29         int c = getState();
30         // Get status
31         int nextc = c - SHARED_UNIT;
32         if (compareAndSetState(c, nextc)) // Compare and set
36             return nextc == 0;
37     }
38 }

Description: this method indicates that the lock reading thread releases the lock. First, judge whether the current thread is the first reading thread firstReader. If so, judge whether the number of resources occupied by the first reading thread firstReaderHoldCount is 1. If so, set the first reading thread firstReader to null. Otherwise, reduce the number of resources occupied by the first reading thread firstReaderHoldCount by 1; If the current thread is not the first reading thread, Then the cache counter will be obtained first (the counter corresponding to the last lock reading thread). If the counter is empty or tid is not equal to the tid value of the current thread, the counter of the current thread will be obtained. If the counter count is less than or equal to 1, the counter corresponding to the current thread will be removed. If the counter count is less than or equal to 0, an exception will be thrown, and then the count will be reduced. In any case, it is OK An infinite loop is entered, which ensures that the state state is successfully set. The flow chart is as follows.

img

In the process of acquiring and releasing a read lock, there will always be an object. At the same time, the object is + 1 when the acquisition thread obtains the read lock and - 1 when the read lock is released, the object is HoldCounter.

To understand HoldCounter, you must first understand the read lock. As mentioned earlier, the internal implementation mechanism of read lock is shared lock. In fact, for shared lock, we can think that it is not a lock concept, but more like a counter concept. A shared lock operation is equivalent to a counter operation. Obtain the shared lock counter + 1 and release the shared lock counter - 1. Only after the thread obtains the shared lock can it release and re-enter the shared lock. Therefore, the function of HoldCounter is the number of shared locks held by the current thread. This number must be bound with the thread, otherwise operating other thread locks will throw an exception.

Let's first look at the part of reading and obtaining locks:

if (r == 0) {//r == 0 indicates the first read lock thread. The first read lock firstRead will not be added to readHolds
    firstReader = current;
    firstReaderHoldCount = 1;
} else if (firstReader == current) {//First read lock thread reentry
    firstReaderHoldCount++;    
} else {    // Other threads hold read locks
    HoldCounter rh = cachedHoldCounter;//readHoldCounter cache
    //rh == null or rh tid !=  current. Getid(), need to get rh
    if (rh == null || rh.tid != current.getId())    
        cachedHoldCounter = rh = readHolds.get();
    else if (rh.count == 0)
        readHolds.set(rh);  //Add to readHolds
    rh.count++; //Count + 1
}

Why do we have a firstRead and firstReaderHoldCount here? Instead of using the else code directly? This is for the sake of efficiency. The firstReader will not be put into readHolds. If there is only one read lock, it will avoid finding readHolds. Maybe this code doesn't understand HoldCounter very well. Let's first look at the definitions of firstReader and firstReaderHoldCount:

private transient Thread firstReader = null;
private transient int firstReaderHoldCount;

These two variables are relatively simple. One represents a thread. Of course, the thread is a special thread, and the other is the reentry count of firstReader.

Definition of HoldCounter:

static final class HoldCounter {
    int count = 0;
    final long tid = Thread.currentThread().getId();
}

In HoldCounter, there are only two variables count and tid, where count represents the counter and tid is the id of the thread. However, if you want to bind an object to a thread, it is certainly not enough to only record TID, and HoldCounter can't bind objects at all, it just records thread TID.

Admittedly, in java, we know that if we want to bind a thread and an object together, only ThreadLocal can be implemented. Therefore, it is as follows:

// ThreadLocalHoldCounter inherits ThreadLocal and overrides the initialValue method.
static final class ThreadLocalHoldCounter extends ThreadLocal<HoldCounter> {
    public HoldCounter initialValue() {
        return new HoldCounter();
    }
}

Therefore, HoldCounter should be a counter on the bound thread, and threadlocalholdcounter is the ThreadLocal bound by the thread. From the above, we can see that ThreadLocal binds HoldCounter to the current thread, and HoldCounter also holds thread Id, so that we can know whether the last read thread (cachedHoldCounter) cached in ReadWriteLock is the current thread when releasing the lock.

The advantage of this is that it can reduce ThreadLocal The number of times to get (), because this is also a time-consuming operation. It should be noted that the reason why HoldCounter binds thread id instead of thread object is to prevent HoldCounter and ThreadLocal from being bound to each other and GC is difficult to release them (although GC can intelligently discover such references and recycle them, it needs a certain price), so this is just to help GC recycle objects quickly.

3, Summary

Through the above source code analysis, we can find a phenomenon:

• When a thread holds a read lock, the thread cannot obtain a write lock (because when obtaining a write lock, if it finds that the current read lock is occupied, it immediately fails to obtain it, regardless of whether the read lock is held by the current thread or not).

• When a thread holds a write lock, the thread can continue to acquire the read lock (if it is found that the write lock is occupied when acquiring the read lock, the acquisition will fail only if the write lock is not occupied by the current thread).

  Think about it carefully. This design is reasonable: when a thread acquires a read lock, other threads may also hold a read lock, so the thread that acquires a read lock cannot be "upgraded" to a write lock; For the thread that obtains the write lock, it must monopolize the read-write lock, so it can continue to obtain the read lock. When it obtains the write lock and the read lock at the same time, it can release the write lock first and continue to hold the read lock. In this way, a write lock will be "degraded" to a read lock.

To sum up: if a thread wants to hold a write lock and a read lock at the same time, it must first obtain a write lock and then a read lock; Write locks can be "downgraded" to read locks; Read locks cannot be "promoted" to write locks.