viksoe.dk

Read Write Lock


This article was submitted .


These classes are not my own. They are an extract of discussions on an old Microsoft ATL mailing list on how to implement a read/write lock most efficiently in Windows.

The first implementation is using standard Windows semaphore primitives. This might be slightly slower at switching, since it's using a Windows Semaphore object instead of atomic operations. But this one doesn't end up doing a Sleep() idle loop.

class CReadWriteSemaphore
{
private:
   CRITICAL_SECTION m_cs;
   HANDLE m_sem;
   LONG m_lMaximumReaders;

   CReadWriteSemaphore(const CReadWriteSemaphore&);

public:
   CReadWriteSemaphore(long lMaxReaders = 10) : 
      m_lMaximumReaders(lMaxReaders)
   {
      ::InitializeCriticalSection(&m_cs);
      m_sem = ::CreateSemaphore(NULL, m_lMaximumReaders, m_lMaximumReaders, NULL);
      _ASSERTE(m_sem!=NULL);
   }

   ~CReadWriteSemaphore()
   {
      ::CloseHandle(m_sem);
      ::DeleteCriticalSection(&m_cs);
   }

   void LockRead()
   {
      ::WaitForSingleObject(m_sem, INFINITE);
   }

   void UnlockRead()
   {
      ::ReleaseSemaphore(m_sem, 1, NULL);
   }

   void LockWrite()
   {
      ::EnterCriticalSection(&m_cs); 
      for( LONG i = 0; i < m_lMaximumReaders; i++ ) {
         ::WaitForSingleObject(m_sem, INFINITE);
      }
      ::LeaveCriticalSection(&m_cs); 
   }

   void UnlockWrite()
   {
      ::ReleaseSemaphore(m_sem, m_lMaximumReaders, NULL);
   }  
};

And here follows an implementation that uses only the InterlockedXXX functions.

class CReadWriteSemaphore
{
private:
   volatile LONG m_nReaders;
   volatile LONG m_nWriters;

   CReadWriteSemaphore(const CReadWriteSemaphore&);

public:
   CReadWriteSemaphore() : m_nReaders(0), m_nWriters(0)
   {
   }

   void LockRead()
   {
      for( ; ; ) {
         ::InterlockedIncrement(&m_nReaders);
         if( m_nWriters == 0 ) break;
         ::InterlockedDecrement(&m_nReaders);
         ::Sleep(0);
      }
   }

   void UnlockRead()
   {
      ::InterlockedDecrement(&m_nReaders);
   }

   void LockWrite()
   {
      for( ; ; ) {
         if( ::InterlockedExchange(&m_nWriters, 1) == 1 )
            ::Sleep(0);
         else {
            while( m_nReaders != 0 ) ::Sleep(0);
            break;
         }
      }
   }

   void UnlockWrite()
   {
      ::InterlockedDecrement(&m_nWriters);
   }
};

Let's introduce a maximum readers limit in the InterlockedXXX version.

class CReadWriteSemaphore
{
private:
   volatile LONG m_nCounter;

   CReadWriteSemaphore(const CReadWriteSemaphore&);

public:
   CReadWriteSemaphore() : m_nCounter(0)
   {
   }

   void LockRead()
   {
      for( ; ; ) {
         LONG n = ::InterlockedIncrement(&m_nCounter); 
         if( n <= MAX_READERS ) break;
         ::InterlockedDecrement(&m_nCounter);
         ::Sleep(0);
      }
   }

   void UnlockRead()
   {
      ::InterlockedDecrement(&m_nCounter);
   }

   void LockWrite()
   {
      for( ; ; ) {
         LONG n = ::InterlockedCompareExchange(&m_nCounter, (MAX_READERS+1), 0); 
         if( n == 0 ) break;
         ::Sleep(0);
      }
   }

   void UnlockWrite()
   {
      ::InterlockedExchangeAdd(&m_nCounter, -(MAX_READERS+1));
   }
};

We can write a more basic class for that matter. This one is by far the most readable version.
And still no writer starving here.

class CReadWriteSemaphore
{
private:
   CRITICAL_SECTION m_cs;
   volatile LONG m_nReaders;

   CReadWriteSemaphore(const CReadWriteSemaphore&);

public:
   CReadWriteSemaphore() : m_nReaders(0)
   {
      ::InitializeCriticalSection(&m_cs);
   }

   ~CReadWriteSemaphore()
   {
      ::DeleteCriticalSection(&m_cs);
   }

   void LockRead()
   {
      ::EnterCriticalSection(&m_cs); 
      ::InterlockedIncrement(&m_nReaders);
      ::LeaveCriticalSection(&m_cs); 
   }

   void UnlockRead()
   {
      ::InterlockedDecrement(&m_nReaders);
   }

   void LockWrite()
   {
      ::EnterCriticalSection(&m_cs); 
      while( m_nReaders > 0 ) ::Sleep(0); 
   }

   void UnlockWrite()
   {
      ::LeaveCriticalSection(&m_cs); 
   }  
};

For completeness, here is a wrapper for the native Windows Vista Slim ReadWrite Lock. Just like the ones above, it's a simple semaphore which doesn't support recursive locks nor upgrading of lock level.

class CReadWriteSemaphore
{
private:
   SRWLOCK m_srw;

   CReadWriteSemaphore(const CReadWriteSemaphore&);

public:
   CReadWriteSemaphore()
   {
      ::InitializeSRWLock(&m_srw);
   }

   void LockRead()
   {
      ::AcquireSRWLockShared(&m_srw);
   }

   void UnlockRead()
   {
      ::ReleaseSRWLockShared(&m_srw);
   }

   void LockWrite()
   {
      ::AcquireSRWLockExclusive(&m_srw);
   }

   void UnlockWrite()
   {
      ::ReleaseSRWLockExclusive(&m_srw);
   }  
};
The Slim ReadWrite Lock is not actually a slim implementation like the ones above. In the footnotes on his blog, Microsoft wizard Raymond Chen shares some details on how complicated the implementation of SRWLOCK really is.


To the top