C/C++ Tips

C/C++ Tip #8: Performing Multiple Read/Write Locks

Tomer Abramson

The readers/writer lock is a well-known pattern in multithreaded programming. It allows multiple readers or a single writer to access a critical section at the same time.

Using the readers/writer lock pattern can create a problem: what do you do about multiple locks? For example:

RWLock lockA, lockB;
Thread 1                  Thread 2
lockA.AcquireWriteLock()  lockB.AcquireWriteLock()
lockB.AcquireReadLock()   lockA. AcquireReadLock()

The preceding code can lead to a deadlock. Assume the order of locks is:

  1. Thread 1 acquires a write lock on lockA.
  2. Thread 2 acquires a write lock on lockB.

Now, Thread 1 will wait for Thread 2 to release the write lock on lockB in order to acquire a read lock on lockB. Thread 2 will wait for Thread 1 to release the write lock on lockA in order to acquire a read lock on lockA. Consequently, the threads will deadlock.

A typical implementation of the readers/writer pattern is:

#include <windows.h>
class RWLock  
{
public:
  RWLock() : m_nReaders(0) { /* create events */ }
  virtual ~RWLock() { /* close handles */ }

  void AcquireWriteLock() const
  { WaitForSingleObject(m_hDataEvent, INFINITE); }
  void ReleaseWriteLock() const
  { SetEvent(m_hDataEvent); }

  void AcquireReadLock()
  {
    WaitForSingleObject(m_hReadersEvent, INFINITE);
    if (m_nReaders++ == 0)
      WaitForSingleObject(m_hDataEvent, INFINITE);
  SetEvent(m_hReadersEvent);
  }
  void ReleaseReadLock()
  {
    WaitForSingleObject(m_hReadersEvent, INFINITE);
    if (--m_nReaders == 0)
      SetEvent(m_hDataEvent);
    SetEvent(m_hReadersEvent);
  }

private:
  int      m_nReaders;
  HANDLE   m_hReadersEvent;
  HANDLE   m_hDataEvent;

};

I want to add another method, MultipleRWLock, that allows multiple locks as atomic action. In other words, multiple locks are performed logically as one inseparable operation. This approach is analogous to the behavior of the Win32 WaitForMultipleObjects. Applying this approach to the previous example yields two scenarios for locking. In each scenario, only one thread waits:

  1. Thread 1 acquires a write lock on lockA and a read lock on lockB (with both locks treated as one operation), and Thread 2 waits.
  2. Thread 2 acquires a write lock on lockB and a read lock on lockA (with both locks treated as one operation), and Thread 1 waits.

This scheme eliminates the deadlock scenario, in which each thread waits for the other.

Trying to implement MultipleRWLock by using WaitForMultipleObjects with any combination of the RWLock handles is doomed to fail. In order to perform a read lock, you need to lock m_nReaders, compare m_nReaders to zero and increment it, and, if m_nReaders equals zero, lock the data. Based on that, you would expect the MultipleRWLock implementation to perform the following tasks:

  1. Lock all m_nReaders for all read requests.
  2. Compare all m_nReaders to zero and increment.
  3. Lock data for all read requests with m_nReaders == 0 and for all write requests.
  4. Release all m_nReaders that were locked in Step 1.

Listing 1 contains the code for this implementation of MultipleRWLock.

The problem with this implementation is that the MultipleRWLock interferes with the operation of the AcquireReadLock. Assume you have two resources (R1 and R2) and three threads (T1, T2, T3). Now you have a sequence of locks:

T2 will lock m_nReaders of R1 and R2, increment R1 and R2, and wait for T1 to release the write lock on R1 in order to lock the data.

Now T3 will not be able to acquire a read lock on R2 because T3 will wait for T2 to release the lock on m_nReaders. So, although no one locks R2, T3 still has to wait for it. T3 actually waits for T1 to release the write lock on R1!

The solution is simple: you must add another handle in order to synchronize the locks from MultipleRWLock. These are the changes to perform:

  1. Add to RWLock another member:
    2. HANDLE m_hAnotherDataEvent;
  2. Change AcquireWriteLock:
    3. HANDLE handles[2] =
{ m_hDataEvent, m_hAnotherDataEvent };
WaitForMultipleObjects(2, handles, TRUE, INFINITE);
  3. Change ReleaseWriteLock:
    4. SetEvent(m_hDataEvent);
SetEvent(m_hAnotherDataEvent);
  4. Add a struct that encapsulates the lock request:
    5. struct LockRequest
{
  enum LockType_En   
  { READ_LOCK, WRITE_LOCK };
  LockRequest(RWLock* pRWLock, LockType_En lockType) :
    m_pRWLock(pRWLock), m_lockType(lockType) {};

  RWLock* m_pRWLock;
  LockType_En m_lockType;
};

Now you are ready to implement MultipleRWLock:

static void RWLock::MultipleRWLock
  (LockRequest* pRequest, int nCount)
{
  HANDLE
    dataHandles[MAXIMUM_WAIT_OBJECTS];
  RWLock*
    readers[MAXIMUM_WAIT_OBJECTS];
      int nDataHandles = 0, nReaders= 0;
  
    
  for (int i = 0; i < nCount; i++)
  {
    // Build data handles array
    dataHandles[nDataHandles++] =
      pRequest[i].m_pRWLock
        ->m_hAnotherDataEvent;
    if (pRequest[i].m_lockType ==
      LockRequest::WRITE_LOCK)
      dataHandles[nDataHandles++] =
        pRequest[i].m_pRWLock
          ->m_hDataEvent;
    else
      // Build readers array
      readers[nReaders++] =
        pRequest[i].m_pRWLock;
  }

  // Perform the locks
  WaitForMultipleObjects(nDataHandles,
    dataHandles, TRUE, INFINITE);
  
  // For each read request update 
  // readers counter
  for (i = 0; i < nReaders; i++)
  {
    readers[i]->AcquireReadLock();
    SetEvent(readers[i]
      ->m_hAnotherDataEvent);
  }  
}

By adding the m_hAnotherDataEvent, I accomplished the ability to request a read lock from MultipleRWLock without interfering with a read lock from AcquireReadLock and still block any write lock attempt.

Finally, here is how to use it:

RWLock lockA, lockB;
LockRequest lockRequests[2] =
  { LockRequest(&lockA, LockRequest::WRITE_LOCK),
    LockRequest(&lockB, LockRequest::READ_LOCK) };

RWLock::MultipleRWLock(lockRequests, 2);

Note: in my code, I didn’t perform any error checking, and all my waitForObjects are waiting an infinite time. This was done only to simplify the code.