ReentrantReadWriteLock read / write lock analysis

Introduction to read / write lock

In reality, there is such a scenario: there are read and write operations on shared resources, and the write operations are less frequent than the read operations (more reads and less writes). 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 (reading can be concurrent); However, if a thread wants to write these shared resources, it should not allow other threads to read and write the resources (read / write, write / read, write / write are mutually exclusive). In the case of more reads than writes, read-write locks can provide better concurrency and throughput than exclusive locks.

For this scenario, JAVA's concurrent packages provide a ReentrantReadWriteLock, which internally maintains a pair of related locks. One is used for read-only operations, which is called a read lock; A write lock is used for write operations. It is described as follows: the precondition for a thread to enter a read lock:

  • No write locks for other threads
  • There is no write request or write request, but the calling thread and the thread holding the lock are the same.

Prerequisites for a thread to enter a write lock:

  • No read lock for other threads
  • No write locks for other threads

Read / write locks have the following three important characteristics:

  • Fair selectivity: supports unfair (default) and fair lock acquisition methods. Throughput is still unfair rather than fair.
  • Reentrant: both read and write locks support thread reentry. Take the read-write thread as an example: after the read thread acquires the read lock, it can acquire the read lock again. After acquiring the write lock, the write thread can acquire the write lock again, and can also acquire the read lock.
  • Lock demotion: follow the sequence of acquiring a write lock, acquiring a read lock, and finally releasing a write lock. A write lock can be demoted to a read lock.

After reading the above description, you may feel a little dizzy. I will give an example of previous development orders to help you understand. Our order has a concept of primary order and sub order: the primary order code is orderCode, and the sub order code is subOrderCode. The corresponding relationship is 1:N. When I refund, I need to support sub order and main order refund. The dimension of the sub order refund is the subOrderCode main order refund, and the dimension of the orderCode may be concurrent. We can add a read-write lock to the orderCode

  • In the case of primary order refund, whether the sub order refund is mutually exclusive
  • In case of sub order refund, it can be parallel. However, the sub order is a subOrderCode dimension, and a subOrderCode mutex needs to be added.

Read / write lock usage

How to store read-write locks at the same time can be stored through the value of state. The high 16 bits represent read locks and the low 16 bits represent write locks. For example: 0000 0000 0000 0000 (1<<16) 0000 0000 0000 high 16 bits are not 0: there is a read lock C > > > 16 low 16 bits are not 0: there is a write lock 5

ReadWriteLock interface

We can see that the ReentranReadWriteLock has two locks, a read lock and a write lock.

Use examples

Cache operation:

public class ReentrantReadWriteLockCacheTest {

    static Map<String, Object> map = new HashMap<String, Object>();
    static ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
    static Lock r = rwl.readLock();
    static Lock w = rwl.writeLock();

    // Get the value corresponding to a key
    public static final Object get(String key) {
        r.lock();
        try {
            return map.get(key);
        } finally {
            r.unlock();
        }
    }

    // Set the value corresponding to the key and return the old value
    public static final Object put(String key, Object value) {
        w.lock();
        try {
            return map.put(key, value);
        } finally {
            w.unlock();
        }
    }

    // Clear all contents
    public static final void clear() {
        w.lock();
        try {
            map.clear();
        } finally {
            w.unlock();
        }
    }

}

In the above example, the Cache combines a non thread safe HashMap as the implementation of the Cache, and uses the read lock and write lock of the read-write lock to ensure that the Cache is thread safe. In the read operation get(String key) method, it is necessary to obtain a read lock, so that concurrent access to the method will not be blocked. The write operation put(String key,Object value) method and clear() method must acquire the write lock in advance when updating the HashMap. After acquiring the write lock, other threads' acquisition of the read lock and the write lock is blocked. Only after the write lock is released can other read-write operations continue. The Cache uses read-write locks to improve the concurrency of read operations, ensure the visibility of each write operation to all read-write operations, and simplify the programming method.

Lock degradation

Lock demotion means that a write lock is demoted to a read lock. If the current thread owns a write lock, then releases it, and finally obtains a read lock, this segmented completion process cannot be called lock degradation. Lock demotion refers to the process of holding the (currently owned) write lock, acquiring the read lock, and then releasing the (previously owned) write lock. Lock demotion can help us get the modified results of the current thread without being damaged by other threads, so as to prevent the loss of updates.

Example of lock degradation

Because the data does not change frequently, multiple threads can process the data concurrently. After the data changes, if the current thread senses the data changes, it will prepare the data. At the same time, other processing threads are blocked until the current thread completes the data preparation.

private final ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
private final Lock readLock = rwl.readLock();
private final Lock writeLock = rwl.writeLock();
private volatile boolean update = false;

public void processData() {
    readLock.lock();
    if (!update) {
        // The read lock must be released first
        readLock.unlock();
        // Lock degradation starts from write lock acquisition
        writeLock.lock();
        try {
            if (!update) {
                // TODO data preparation process (omitted)
                update = true;
            }
            readLock.lock();
        } finally {
            writeLock.unlock();
        }

        // Lock demotion is completed, and write lock is demoted to read lock
    }
    try {
        //TODO process of using data (omitted)
    } finally {
        readLock.unlock();
    }
}

Precautions:

  • Read lock does not support conditional variables
  • No upgrade or support during reentry: obtaining a write lock while holding a read lock will cause a permanent wait
  • Downgrade is supported during re-entry: you can obtain a read lock when you hold a write lock

ReentranReadWriteLock structure

Method structure design

Read / write state design

Source code analysis

Write lock locking

The method tryAcquire is the core logic for writing locks

protected final boolean tryAcquire(int acquires) {
    /*
     * Walkthrough:
     * 1\. If read count nonzero or write count nonzero
     *    and owner is a different thread, fail.
     * 2\. If count would saturate, fail. (This can only
     *    happen if count is already nonzero.)
     * 3\. Otherwise, this thread is eligible for lock if
     *    it is either a reentrant acquire or
     *    queue policy allows it. If so, update state
     *    and set owner.
     */
    Thread current = Thread.currentThread();
    int c = getState();
    // Get write lock status
    int w = exclusiveCount(c);
    if (c != 0) {
        // (Note: if c != 0 and w == 0 then shared count != 0)
        if (w == 0 || current != getExclusiveOwnerThread())
            return false;
        if (w + exclusiveCount(acquires) > MAX_COUNT)
            throw new Error("Maximum lock count exceeded");
        // Reentrant acquire
        // Reentry
        setState(c + acquires);
        return true;
    }
    // Acquire write lock
    if (writerShouldBlock() ||
        !compareAndSetState(c, c + acquires))
        return false;
    // Set write lock owner
    setExclusiveOwnerThread(current);
    return true;
}

Release of write lock

protected final boolean tryRelease(int releases) {
    if (!isHeldExclusively())
        throw new IllegalMonitorStateException();
    int nextc = getState() - releases;
    boolean free = exclusiveCount(nextc) == 0;
    if (free)
        setExclusiveOwnerThread(null);
    setState(nextc);
    return free;
}

Acquisition of read lock

protected final int tryAcquireShared(int unused) {
    /*
     * Walkthrough:
     * 1\. If write lock held by another thread, fail.
     * 2\. Otherwise, this thread is eligible for
     *    lock wrt state, so ask if it should block
     *    because of queue policy. If not, try
     *    to grant by CASing state and updating count.
     *    Note that step does not check for reentrant
     *    acquires, which is postponed to full version
     *    to avoid having to check hold count in
     *    the more typical non-reentrant case.
     * 3\. If step 2 fails either because thread
     *    apparently not eligible or CAS fails or count
     *    saturated, chain to version with full retry loop.
     */
    Thread current = Thread.currentThread();
    int c = getState();
    if (exclusiveCount(c) != 0 &&
        getExclusiveOwnerThread() != current)
        return -1;
    int r = sharedCount(c);
    if (!readerShouldBlock() &&
        r < MAX_COUNT &&
        compareAndSetState(c, c + SHARED_UNIT)) {
        // Acquire read lock for the first time
        if (r == 0) {
            firstReader = current;
            // First thread reentry
            firstReaderHoldCount = 1;
        } else if (firstReader == current) {
            // Reentry
            firstReaderHoldCount++;
        } else {
            // For subsequent threads, obtain the number of reentries through ThreadLocal
            HoldCounter rh = cachedHoldCounter;
            if (rh == null || rh.tid != getThreadId(current))
                cachedHoldCounter = rh = readHolds.get();
            else if (rh.count == 0)
                readHolds.set(rh);
            rh.count++;
        }
        return 1;
    }
    return fullTryAcquireShared(current);
}

The fullTryAcquireShared method is as follows:

final int fullTryAcquireShared(Thread current) {
    /*
     * This code is in part redundant with that in
     * tryAcquireShared but is simpler overall by not
     * complicating tryAcquireShared with interactions between
     * retries and lazily reading hold counts.
     */
    HoldCounter rh = null;
    for (;;) {
        int c = getState();
        if (exclusiveCount(c) != 0) {
            if (getExclusiveOwnerThread() != current)
                return -1;
            // else we hold the exclusive lock; blocking here
            // would cause deadlock.
        } 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)
            throw new Error("Maximum lock count exceeded");
        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;
        }
    }
}

Release of read lock

protected final boolean tryReleaseShared(int unused) {
    Thread current = Thread.currentThread();
    if (firstReader == current) {
        // assert firstReaderHoldCount > 0;
        if (firstReaderHoldCount == 1)
            firstReader = null;
        else
            firstReaderHoldCount--;
    } else {
        HoldCounter rh = cachedHoldCounter;
        if (rh == null || rh.tid != getThreadId(current))
            rh = readHolds.get();
        int count = rh.count;
        if (count <= 1) {
            readHolds.remove();
            if (count <= 0)
                throw unmatchedUnlockException();
        }
        --rh.count;
    }
    for (;;) {
        int c = getState();
        int nextc = c - SHARED_UNIT;
        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;
    }
}

Tags: Java Programmer lock

Posted by neojordan on Sun, 29 May 2022 23:41:09 +0530