ReentrantReadWriteLock principle

Two days ago, I went to play blue Bridge Cup (woo woo, it’s really a water cup, can’t stand it, can I get a participation award), I didn’t update JUC.

Read/write lock source

Continuing today, we’re going to look at another type of lock, a read-write lock, which, as the name implies, has two locks at the same time: a read lock and a write lock. So what’s the use? It can improve the overall performance of the system when there are more reads and less writes. Before there is no read/write lock, we can only rely on wait/notify mechanism to carry out thread cooperation. After the write operation is complete, notifyAll all read threads are blocked before the write operation is complete, and the write lock uses synchronized to ensure exclusive use. After the read and write lock out, let the program code has a more concise way, as well as some new functions, such as lock degradation…

Read/write Lock

Multiple threads can acquire a read lock at the same time, and if one thread acquires a write lock, other read and write requests block. If a read lock is acquired before the write lock is acquired, the write lock blocks until the read lock is released.

Features are as follows:

Lock down

Fairness and reentrancy, of course, we already know that. But what is a lock downgrade? We’ve seen before that once I acquire a write lock, all read/write lock requests from other threads will be blocked, but if I acquire a write lock, I can degrade to a read lock without blocking. Take a look at the sample code to learn more about this sentence

public static void main(String[] args) {

    ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();// Built-in read lock
    ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();// Built-in write lock

    Thread t1 = new Thread("t1") {
        @Override
        public void run(a) {
            writeLock.lock();// Get the write lock
            System.out.println("T1, I got the write lock.");

            readLock.lock();/ / lock down
            System.out.println("T1, I got a read lock, the lock is degraded.");

            try {
                sleep(1000);
                System.out.println("T1, I'm going to lock it.");
                writeLock.unlock();

                sleep(1000);
                System.out.println("T1, I'm going to lock the read.");
                readLock.unlock();
            } catch(InterruptedException e) { e.printStackTrace(); }}}; Thread t2 =new Thread("t2") {
        @Override
        public void run(a) {
            try {
                // Ensure that t1 is executed first
                Thread.sleep(10);
                System.out.println("T2 I woke up and wanted to write the lock.");
                writeLock.lock();
                System.out.println("T2, I got the write lock.");
            } catch(InterruptedException e) { e.printStackTrace(); }}}; t1.start(); t2.start(); }Copy the code

The result is as follows

T1, I've got the write lock t1, I've got the read lock, the lock is degraded T2, I wake up, I want to get the write lock T1, I'm going to put the write lock t1, I'm going to put the read lock T2, I've got the write lockCopy the code

See from the code, two threads, and guaranteed to a thread (t1) here first to get to the write lock, then can’t get another thread t2 read-write lock, he entered the block, and then I write lock t1 in acquiring, on the basis of get a read lock again, we found that can be directly obtained, no jam, by this time he wrote by locked down to read, T2 can then acquire the write lock by releasing the write lock (the write lock must be secured by no other thread). Use the order as shown above, write lock -> read lock -> release write lock -> release read lock.

The specific implementation

Read the above examples, read and write lock is used. So as we can see, read/write locks are flexible and easy to program. So how did he do it? Let’s take a look at the secrets of read-write locks.

Reading and writing the design

First of all, it is also implemented based on AQS. However, we found that there is only one state variable in AQS, which can maintain one lock. Then, how can you realize that there are two locks for reading and writing locks based on my AQS? The answer is bitwise sharded. One state variable is int, 32 bits. Then I use the high 16 bit read lock and the low 16 bit write lock.

abstract static class Sync extends AbstractQueuedSynchronizer {

    static final int SHARED_SHIFT   = 16;// The left shift of the shared lock is 16, that is, the high 16 bits are used as the read lock
    static final int SHARED_UNIT    = (1 << SHARED_SHIFT);/ / Shared lock
    static final int MAX_COUNT      = (1 << SHARED_SHIFT) - 1;
    static final int EXCLUSIVE_MASK = (1 << SHARED_SHIFT) - 1;// Exclusive lock flag, equivalent to 0x0000FFFF
}
Copy the code

When we use read lock, if the current synchronization state bit w, then in the high 16 bits +1 (read lock), w+(1<<16);

We use write lock, get read lock status, w>>>16, can get lower 16 bits.

How is AQS managed

We see read-write locks, which have two locks, so both shared and exclusive locks are queued by AQS. To join in, rewrite tryAcquire and tryAcquireShared to get resources and release the corresponding resources.

Write lock acquisition and release

tryAcquire

protected final boolean tryAcquire(int acquires) {
    Thread current = Thread.currentThread();
    int c = getState();
    int w = exclusiveCount(c);// Return the number of write locks in state
    
    if(c ! =0) {// Get read lock or write lock
        // No thread has acquired the write lock (to ensure that all read locks are released) or another thread has acquired the write lock
        if (w == 0|| current ! = getExclusiveOwnerThread())return false;
        if (w + exclusiveCount(acquires) > MAX_COUNT)
            throw new Error("Maximum lock count exceeded");
        // Reentrant acquire
        // There is only one write lock, so no cas is required
        setState(c + acquires);
        return true;
    }
    
    // Do not get read/write lock
    if(writerShouldBlock() || ! compareAndSetState(c, c + acquires))return false;
    setExclusiveOwnerThread(current);
    return true;
}
Copy the code

Write lock section: in the case of a write lock or read lock, any thread that acquires a read/write lock returns false to enter AQS block. The reason is to ensure visibility. An attempt is made to acquire a read lock if the read/write lock is not acquired.

tryRelease

protected final boolean tryRelease(int releases) {
    if(! isHeldExclusively())// The current thread did not acquire the write lock, raising an exception
        throw new IllegalMonitorStateException();
    int nextc = getState() - releases;// Subtract the reentrant number
    boolean free = exclusiveCount(nextc) == 0;
    if (free)
        setExclusiveOwnerThread(null);
    setState(nextc);
    return free;
}
Copy the code

It’s a little bit easier to just release the reentrant.

Read lock acquisition and release

tryAcquireShared

TryAcquire is complicated here by methods such as getReadHoldCount (stored using ThreadLocal to get the number of times the current thread has acquired a read lock). But the main logic is as follows (abridged)

final int fullTryAcquireShared(Thread current) {
   
    for (;;) {
        int c = getState();
        if(exclusiveCount(c) ! =0) {
            if(getExclusiveOwnerThread() ! = current)// The write lock was acquired and is not the current thread
                return -1; . }...if (compareAndSetState(c, c + SHARED_UNIT)) {//c+SHARED_UNIT = c+(1<<16
            return 1; }}}Copy the code

tryReleaseShared

Again, there’s been a corresponding deletion here

.for (;;) {
    int c = getState();
    int nextc = c - SHARED_UNIT;// c-(1<<16)
    if (compareAndSetState(c, nextc))
        // Releasing the read lock has no effect on readers,
        // but it may allow waiting writers to proceed if
        // both read and write locks are now free.
        return nextc == 0;
}
Copy the code

Since multiple read locks can be released at the same time, cas+ spin is used to release the read lock to ensure atomicity.

conclusion

Multiple threads can acquire a read lock at the same time, and if one thread acquires a write lock, all other read and write requests must be blocked. If a read lock is acquired before the write lock is acquired, the write lock blocks until the read lock is released. .

All the code implements this statement.