A Scalable RW-Lock with 2-state Readers

Yesterday Andreia had another idea for a really cool modification of the scalable-rw-lock algorithm which not only gives a performance improvement (up to 15% in certain cases), but it also makes the algorithm easier to understand.

The idea is very simple, instead of having 4 states for the Readers, we have just two states: 0 or 1. If the Reader is not doing any locking in read-only mode, then the state will be 0, and if it is trying to acquire the lock or is already accessing the resource (in read-only mode) then the state is 1.

How are we able to achieve synchronization with only two states?
Well, the trick is that the Reader will first read the variable that has the write-lock, we'll call that writer_owner, and if it is not locked then it will set it's own state in readers_count to 1, followed by checking again the value of writer_owner to confirm it is still unlocked. If it is unlocked, then the thread got the lock in read-only mode and can return, otherwise it must give up and set the reader's state back to 0, and then yield() until no writer is holding the lock.

This is what the code looks like:

        while (true) {

            if (writer_owner.get() == SRWL_INVALID_TID) {

               readers_count.set(local_tid, 1);

               if (writer_owner.get() == SRWL_INVALID_TID) {

                   // Acquired lock in read-only mode

                   return;

               }

               else {

                   // A Writer has acquired the lock, must reset to 0 and wait

                   readers_count.set(local_tid, 0);

               }

            }

            Thread.yield();

        }

Pretty simple, huh?  :)

You can get the full code for the Reentrant implementation in Java here ScalableReentrantRWLock.java

Checkout the performance plots I got on my laptop with only 4 real threads, for the cases with 1 Writer in 5 Readers, 1 Writer in 10 Readers, 1 Writer in 100 Readers, and No Writers (more operations is better):

The work being done between the lock/unlock is reading/writing on an array of ints with 64 elements (4 cache lines) .

Under these high-contention scenarios, the ScalableReentrantRWLock is at least 2.5x faster than the current implementation in java.util.concurrent.locks.ReentrantReadWriteLock

If you want the C version of this lock you can get it here:
srwlock.h
srwlock.c
main.c