Read/Write Locks and Upgrading Lock State from Read to Write

November 28, 2012 · by · in Programming

In an earlier article I described how to write a read/write lock. This type of lock can lock a shared resource to allow multiple reader thread or a single writer thread and no readers. But sometimes you want to be able to upgrade a thread’s lock on a shared resource from allowing just reading to allowing writing.

Implementing Upgradable Read/Write Locks

One way to do this is to first have the thread unlock for reading and then lock for writing:

KxRWMutex rwLock;

void threadDoStuff()
{
   rwLock.readLock();
   doReadOnlyStuff();
   rwLock.readUnlock();

   rwLock.writeLock();
   doWritingStuff();
   rwLock.writeUnlock();
}

The problem with this is that between the reading phase and the writing phase of this thread the read/write lock is unlocked, and another thread could take control. Sometimes this is ok, but there are times when you want to ensure that no other thread tries to lock for writing before the current reader thread gets a chance to write. You want to do something like this:

KxRWMutex rwLock;

void threadDoStuff()
{
   rwLock.readLock();
   doReadOnlyStuff();

   rwLock.writeLock( true );
   doWritingStuff();
   rwLock.writeUnlock( true );
}

The read lock is never released. Rather it is upgraded to write state.

We add an argument to writeLock(). If true then we are upgrading the lock from read to write. If false we are locking for writing in the usual way – that is the write lock will fail if any thread is already locked for reading. This is not strictly necessary – it would be possible with extra code to detect if the current thread holds on of the read locks and upgrade the lock in that case. But it is easier and better performing to not have the read/write lock track which threads are holding read locks. In our implementation the read/write lock just holds a count of the number of read locks.

When you unlock for writing at the end you have a choice, do you release just the write lock, or both the lock for reading and writing. So we add an additional argument to writeUnlock(), if true we release both the read and write locks, if false we release just the write lock, and leave the read lock ( if there was one ).

To implement this we build on our previous read/write lock code, which in turn builds on our mutex class. First we change the prototype for the write lock functions to add the extra arguments:

class KxRWMutex
{
public:
   void writeLock   ( bool upgrade = false );
   bool writeTryLock( bool upgrade = false );
   void writeUnlock ( bool releaseReadLock = false );

protected:
   bool    mReadsBlocked;
   u32     mMaxReaders;
   u32     mReaders;
   KxMutex mReadMutex;
   KxMutex mWriteMutex;
}

And now we change the write lock methods:

bool KxRWMutex::writeTryLock( bool upgrade )
{
   if ( !mWriteMutex.tryLock())
      return false;
   waitReaders( upgrade ? 1 : 0 );
   return true;
}

void KxRWMutex::writeLock( bool upgrade )
{
   mWriteMutex.lock(); 
   waitReaders( upgrade ? 1 : 0 );
}

void KxRWMutex::writeUnlock( bool releaseReadLock )
{
   mReadMutex.lock();
   if ( releaseReadLock )
   {
      assert( mReaders <= 1 );
      if ( mReaders == 1 )
         mReaders--; 
   }
   mReadsBlocked = false;
   mReadMutex.unlock();
   mWriteMutex.unlock(); 
}

Normally the writeLock() methods wait until there are no readers, but when we are upgrading the read write lock we just wait until there is a single reader thread – which should be the current thread. This will wreak havoc if you call writeLock( true ) when the current thread does not hold a read lock. In that case we would be allowing a single other random thread in read state when we enter write state. But if our thread is in read state this should work as expected.

Then in the writeUnlock() method we add an additional condition. If releaseReadLock is true, then we expect to find a single read lock still active, and we release it. If not, then the existing read lock remains when we return.

Upgradable Write Locks and Deadlock

Using read/write locks with upgrading is tricky. You only want to upgrade a read/write lock in cases where you are sure only one active reader will eventually want to write lock.

Consider the following situation:

  • Thread 1 acquires a read lock
  • Thread 2 acquires a read lock
  • Thread 1 tries to acquire a write lock, and is blocked on thread 2’s read lock
  • Thread 2 tries to acquire a write lock, and is blocked on thread 1’s read lock.

Result: Deadlock.

In the usual case when you could potentially have multiple threads trying to upgrade a read lock to write, you need to use writeTryLock(). Most locking functions will block waiting on a lock if another thread is holding it. A “try lock” is “non-blocking” – that is it will return false if the lock is busy.

Unless you know for sure that only one thread will ever want to upgrade a write lock at any time, then when upgrading locks from read to write always use a “try lock”.

An Example of Using Upgradable Write Locks

Suppose you want to make a shared hash table. Multiple threads will be retrieving hashed values from the table, which they can do simultaneously so long as the table doesn’t change. Less frequently a thread will find that the value it needs is not in the table and it will want to add it.

Consider the following class:

class SharedHashTable
{
public:
   HashValue& findOrAdd( HashKey& key );

protected:
   KxRWMutex                     mRwLock;
   HashTable<HashKey, HashValue> mHashTable;
}

It contains a templatized has table that given a key of type HashKey returns a value of HashValue. And we have a method findOrAdd() that give a key will return its value, or if the key is not found will add that key, and create a new associated HashValue.

HashValue& SharedHashTable::findOrAdd( HashKey& key )   
{
tryAgain:
   // Lock the table for reading. From this point forward we know that no
   // other thread will change the hash table while we are reading it.
   mRwLock.readLock();
   if ( mHashTable.isDefined( key ) )
   {
      HashValue& val = mHashTable.getValue( key );
      mRwLock.readUnlock();
      return val; 
   }

   // if we are still here it is because the key we wanted was not in the table. 
   // and we intend to add a new key value pair. We are still holding the read lock.
   // So we try locking for writing without unlocking for reading sending the upgrade
   // flag to writeTryLock.
   if ( mRwLock.writeTryLock( true ) )
   {
      // in the usual case this will succeed. And we can be sure the hash table has not
      // been modified. So we make our change - adding the new key.
      HashValue& val = mHashTable.addKeyAndValue( key, createNewValue( key ));
      mRWLock.writeUnlock( true );
      return val;
   }
 
   // We will only get here in rare cases where multiple threads tried to get a value
   // and simultaneously found that they needed to modify the hash table. One thread
   // would have succeeded in entering "writeTryLock", and is waiting on the other
   // threads to release their read locks. 

   // So we release our read lock, and yield to the other thread, and then try our
   // operation again.
   mRWLock.readUnlock();

   // yield is an operating system method that will tell the task scheduler to allow 
   // some other thread to run. It will be different on different operating systems.
   // This is not strictly necessary, but in some systems may improve performance of 
   // a deadlock prevention loop like this.
   yield();

   goto tryAgain;
}

Resources:

Implementing Portable Threads and Mutexes Our tutorial on the basics of threaded programming.
Implementing Read/Write Locks Portably Our tutorial on writing your own basic read/write locks.
upgrading read lock to write lock An example of read/write lock deadlocking on StackOverflow.