ReentrantReadWriteLock

0

In this article, we will go through the internals of ReentrantReadWriteLock.

Read Write Lock

It allows multiple threads to read a resource concurrently, but requires a thread to wait for an exclusive lock in order to write to the resource.

Rules are:

  • A reader can access the resource when there are no writers active in any other thread.
  • A writer can access the resource when no other reader or writer from a different thread is active.
  • Several readers can share the resource concurrently. If you have a read lock, you can safely acquire another read lock. The maximum count of shared locks is 1111 1111 1111 1111
  • If you have a read lock, you CANNOT acquire a write lock
  • If you have a write lock, you can acquire another write lock in the same thread. The maximum count of exclusive locks that a thread can own is 1111 1111 1111 1111
  • If you have a write lock, you CANNOT acquire a read lock in any other thread.
  • Prefers writers over readers. That is, if a writer is waiting on the lock, no new readers from other thread are allowed to access the resource. Existing readers can continue to use the resource until they release the lock. This prevents so-called “writer starvation”.
  • Allows downgrading from the write lock to a read lock, by acquiring the write lock, then the read lock and then releasing the write lock. However, upgrading from a read lock to the write lock is not possible.

Lock State

The lock state (c) is logically divided into two shorts: The lower one representing the exclusive (writer) lock hold count, and the upper the shared (reader) hold count.Assuming current state of lock is c= xxxx xxxx xxxx xxxx yyyy yyyy yyyy yyyy then
Number of reader locks are the upper bits, can be retrieved by doing an unsigned right shift
= c >>> 16
= xxxx xxxx xxxx xxxx

Number of writer locks are the lower bits, can be retrieved using a simple AND operation
= c & (1<< 16 -1)
= c & 0000 0000 0000 0000 1111 1111 1111 1111
= yyyy yyyy yyyy yyyy

Write Lock

Fails to acquire if read lock is already acquired

    public void testReentrantTryWriteAfterReadLock() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        readLock.lock();
        try {
            assertFalse(writeLock.tryLock(2, TimeUnit.SECONDS));
        } catch (InterruptedException e) {
            fail(e.toString());
        }
    }

Fails if write lock already acquired by a different thread

    public void testReentrantTryWriteAfterWriteLock() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        writeLock.lock();
        final CountDownLatch writeLockTried = new CountDownLatch(1);
        new Thread(new Runnable() {
            public void run() {
                try {
                    assertFalse(writeLock.tryLock(2, TimeUnit.SECONDS));
                    writeLockTried.countDown();
                } catch (InterruptedException e) {
                    fail(e.toString());
                }
            }
        }).start();
        try {
            writeLockTried.await();
        } catch (InterruptedException e) {
            fail(e.toString());
        }
    }

Fails if write lock count would saturate and reaches the maximum allowed locks.
Since write count is held in the lower bits of hold state, it can reach a maximum of 1111 1111 1111 1111=65535.

If the thread fails to acquire the lock it will be put in a queue. See ReentrantLock for more details about the queue data structure.

If the write lock count is 0, it is eligible to acquire the lock but the fairness policy will still apply and will decide whether the thread has to block. In case of fair policy, it will proceed ONLY if queue is empty or current thread is at head. If it is non-fair, the writer thread can barge in and acquire the lock ahead of the other threads waiting.

Once the lock is acquired, the lock count increments and the current thread becomes the owner of the lock.

Read Lock

Fails if the write lock is already obtained by some other thread. It may also fail if maximum shared lock count is reached. If the current thread already owns the write lock or read lock, then it will allow the thread to acquire the read lock else the reader may be put on hold if there is a writer thread waiting to acquire the lock. Note that a writer thread may have to wait if the lock is acquired by either a reader or writer from some other thread.
Fails to acquire if write lock is acquired by another thread.

    public void testReentrantTryReadAfterWrite() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        final CountDownLatch writeLockAcquired = new CountDownLatch(1);
        new Thread(new Runnable() {
            public void run() {
                writeLock.lock();
                writeLockAcquired.countDown();
            }
        }).start();
        try {
            writeLockAcquired.await();
        } catch (InterruptedException e) {
            fail(e.toString());
        }
        ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        try {
            assertFalse(readLock.tryLock(2, TimeUnit.SECONDS));
        } catch (InterruptedException e) {
            fail(e.toString());
        }
    }

Fails if number of shared holds reaches maximum allowed.

    public void testReentrantReadLockMaxLocks() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        final int MAX_COUNT = (1 << 16) - 1;
        int c = 0;
        for (int i = 0; i <= MAX_COUNT; i++) {
            try {
                readLock.lock();
                assertTrue(i < MAX_COUNT);
            } catch (Error e) {
                assertTrue(i == MAX_COUNT);
            }
        }
    }

The current thread acquires the write lock. A second thread tries to acquire write lock and is put on queue. The current thread then tries to acquire a read lock and it acquires it as it already holds a write lock.

    public void testReentrantReadLockReadLockInWait() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        final ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        writeLock.lock();
        Thread writeThread = new Thread(new Runnable() {
            public void run() {
                writeLock.lock();
            }
        });
        writeThread.start();
        while (!readWriteLock.hasQueuedThread(writeThread)) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }
        try {
            assertTrue(readLock.tryLock(1, TimeUnit.SECONDS));
        } catch (InterruptedException e) {
            fail(e.toString());
        }
    }

Acquires read lock. In another thread, a writer thread tries to acquire the lock and is put in a queue. Now the current thread tries to acquire a read lock and it acquires it as it already holds a read lock.

    public void testReentrantReadLockReadLockInWait1() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        final ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        readLock.lock();
        Thread writeThread = new Thread(new Runnable() {
            public void run() {
                writeLock.lock();
            }
        });
        writeThread.start();
        while (!readWriteLock.hasQueuedThread(writeThread)) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }
        try {
            assertTrue(readLock.tryLock(1, TimeUnit.SECONDS));
        } catch (InterruptedException e) {
            fail(e.toString());
        }
    }

Fails if a writer thread is in queue. Scenario might be that a reader thread first acquires the lock. Next a writer thread tries to acquire lock and is put in a queue. If the same owning thread tries to acquire a read lock, it will be able to get it. If some other reader thread tries to acquire the lock, it will be put on hold as a writer thread is already waiting.

    public void testReentrantReadLockWriteLockInWait() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        final ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        readLock.lock();
        Thread writeThread = new Thread(new Runnable() {
            public void run() {
                writeLock.lock();
            }
        });
        writeThread.start();
        while (readWriteLock.getQueueLength() == 0) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }
        assertEquals(1, readWriteLock.getQueueLength());
        assertTrue(readWriteLock.hasQueuedThread(writeThread));
        readLock.lock();
        assertEquals(2, readWriteLock.getReadLockCount());
        Thread readThread = new Thread(new Runnable() {
            public void run() {
                readLock.lock();
            }
        });
        readThread.start();
        while (!readWriteLock.hasQueuedThread(readThread)) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }
        assertEquals(2, readWriteLock.getQueueLength());
    }

Progressive release scenario:

  1. Reader thread acquires the lock
  2. Writer thread tries to acquire the lock and is put in a queue
  3. Reader thread tries to acquire the lock and is put in a queue
  4. One more reader thread tries to acquire the lock and is put on hold, total threads waiting would be three.
  5. The main reader thread unlocks and un-parks the writer thread
  6. Writer thread automatically acquires the lock
  7. Writer thread now unlocks
  8. Both the reader threads in queue acquire the lock in shared mode
    public void testReentrantReadLockProgressiveRelease() {
        ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
        final ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();
        final ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
        //Get read lock
        readLock.lock();
        final CountDownLatch readLockAcquired = new CountDownLatch(2);

        // try getting write lock, it will be put on queue
        Thread writeThread = new Thread(new Runnable() {
            public void run() {
                writeLock.lock();
                writeLock.unlock();
            }
        });
        writeThread.start();
        while (!readWriteLock.hasQueuedThread(writeThread)) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }

        // try getting read lock, it will be put on queue
       Thread readThread1 = new Thread(new Runnable() {
            public void run() {
                readLock.lock();
                readLockAcquired.countDown();
            }
        });
        readThread1.start();
        while (!readWriteLock.hasQueuedThread(readThread1)) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }

        // try getting read lock, it will be put on queue
       Thread readThread2 = new Thread(new Runnable() {
            public void run() {
                readLock.lock();
                readLockAcquired.countDown();
            }
        });
        readThread2.start();
        while (!readWriteLock.hasQueuedThread(readThread2)) {
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                fail(e.toString());
            }
        }

        // Total 3 threads are on queue - write, read and read
        assertEquals(3, readWriteLock.getQueueLength());

        // Unlock the main read lock, write will automatically acquire the lock..
        readLock.unlock();


        // Writer thread will unlock, both the read locks show acquire the lock
        try {
            readLockAcquired.await(1, TimeUnit.SECONDS);
        } catch (InterruptedException e) {
            fail(e.toString());
        }
        assertEquals(2, readWriteLock.getReadLockCount());

    }
Share.

Leave A Reply