A solution to the Readers/Writers Problem using semaphores

• Download source file - 1.1 Kb

Introduction

The readers/writers problem is one of the classic synchronization problems. Like the dining philosophers, it is often used to compare and contrast synchronization mechanisms. It is also an eminently practical problem.

Readers/Writers Problem - Classic definition

Two kinds of processes -- readers and writers -- share a database. Readers execute transactions that examine database records; writer transactions both examine and update the database. The database is assumed initially to be in a consistent state (i.e., one in which relations between data are meaningful). Each transaction, if executed in isolation, transforms the database from one consistent state to another. To preclude interference between transactions, a writer process must have exclusive access to the database. Assuming no writer is accessing the database, any number of readers may concurrently execute transactions.

Some time ago at work, we had to implement a server that relays and translates his incoming datafeed to multiple (typically > 32) clients. As this datafeed represents the continuously (but on a non-regular time base) changing (stock/option) market prices, fast relaying is crucial. We developed a solution that consists of one receiving thread, multiple translator threads, and even more sending threads (since we do not want to block the server if a client fails to receive).

Obviously, all the threads need access to the received and / or translated packet. To achieve this without corrupting data, synchronization is necessary. Searching the MSDN, resulted in finding several synchronization objects (CCriticalSection, CMutex, etc.) of which none seem to fulfill our demands: Multiple read-access when not writing. We thus decided to write the desired synchronization object ourselves: CMutexRW.

Formal readers and writers solution using semaphores

Since our problem has extensively been studied (since 1960?) we first turned to some old college-books on parallel formal semantics to refresh our knowledge about the problem. Soon we found the pages describing the readers and writers problem and (several) solution outlines. We chose to implement our solution (with readers preference) using semaphores.

First some quick (probably skipable) refresh course to (formal) semaphores: Semaphores where first introduced by Dijkstra in 1968, who thought it to be an useful tool for implementing mutual exclusion and for signalling the occurrence of events such as interrupts. A semaphore is an instance of an abstract data type: it has a representation that is manipulated only by two special operations, P and V. Because Dijkstra is Dutch, the P and V stand for Dutch words. In particular, P is the first letter of the Dutch word passeren, which means `to pass'; V is the first letter of vrijgeven, which means `to release'. The V operation signals the occurrence of an event; the P operation is used to delay a process until an event has occurred. In particular, the two operations must be implemented so that they preserve the following property for every semaphore in a program.

Semaphore Invariant: For semaphore s, let nP be the number of completed P operations and let nv be the number of completed V operations. If init is the initial value of s, then in all visible program states, nP <= nV + init.

Consequently, execution of a P operation potentially delays until an adequate number of V operations have been executed.

By using this definition of semaphores the readers and writers problem can be solved in the following way:

integer    nReaders   := 0
semaphore  semReaders := 1
semaphore  semWriters := 1
Reader[i: 1 .. m] :: do true ->
                        P( semReaders )
                            nReaders := nReaders + 1
                            if nReaders = 1 -> P( semWriters ) fi
                        V( semReaders )

                            read the database

                        P( semReaders )
                            nReaders := nReaders - 1
                            if nReaders = 0 -> V( semWriters ) fi
                        V( semReaders )
                     od
Writer[j: 1 .. n] :: do true ->
                        P( semWriters )
                             write the database
                        V( semWriters )
                     od

Clearly this solution gives readers preference over writers; once one reader is accessing the database, all readers are allowed to read the database without performing the P or V operations on semWriters.

The solution in C++

Without further delay, here's my implementation of CMutexRW. I hope the code is self-explanatory:

class CMutexRW
{
protected:
    HANDLE        m_semReaders;
    HANDLE        m_semWriters;
    int        m_nReaders;
public:
    CMutexRW() :
        m_semReaders(NULL),
        m_semWriters(NULL),
        m_nReaders(0)
    {
        // initialize the Readers & Writers variables
        m_semReaders    = ::CreateSemaphore(NULL, 1, 1, NULL);
        m_semWriters    = ::CreateSemaphore(NULL, 1, 1, NULL);
        m_nReaders    = 0;

        if (m_semReaders == NULL || m_semWriters == NULL)
        {
            LPVOID lpMsgBuf;
            FormatMessage( 
                FORMAT_MESSAGE_ALLOCATE_BUFFER | 
                FORMAT_MESSAGE_FROM_SYSTEM | 
                FORMAT_MESSAGE_IGNORE_INSERTS,
                NULL,
                GetLastError(),
                MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
                (LPTSTR) &lpMsgBuf,
                0,
                NULL 
                );
            TRACE( "***** ERROR: CreateSemaphore: %s\n", (LPCTSTR)lpMsgBuf );
            LocalFree( lpMsgBuf );            
        }
    };

    virtual ~CMutexRW()
    {
        if (m_semWriters)
            VERIFY( ::CloseHandle(m_semWriters) );    

        m_semWriters = NULL;
        if (m_semReaders)
            VERIFY( ::CloseHandle(m_semReaders) );    
        m_semReaders = NULL;
    }

    inline void Lock_DataRead(){
        DWORD dwEvent = WAIT_TIMEOUT;

        // P( semReaders )
        dwEvent = ::WaitForSingleObject( m_semReaders, INFINITE );
        ASSERT(dwEvent == WAIT_OBJECT_0);

        m_nReaders++;

        if (m_nReaders == 1)
        {
            // P( semWriters )
            dwEvent = ::WaitForSingleObject( m_semWriters, INFINITE );
            ASSERT(dwEvent == WAIT_OBJECT_0);
        }
        // V( semReaders )
        VERIFY( ::ReleaseSemaphore( m_semReaders, 1, NULL ) );
    };

    inline void Unlock_DataRead(){
        DWORD dwEvent = WAIT_TIMEOUT;
        // P( semReaders )
        dwEvent = ::WaitForSingleObject( m_semReaders, INFINITE );
        ASSERT(dwEvent == WAIT_OBJECT_0);

        m_nReaders--;

        if (m_nReaders == 0)
        {
            // V( semWriters )
            VERIFY( ::ReleaseSemaphore(m_semWriters, 1, NULL) );
        }
        // V( semReaders )
        VERIFY( ::ReleaseSemaphore( m_semReaders, 1, NULL ) );
    };

    inline void Lock_DataWrite(){
        DWORD dwEvent = WAIT_TIMEOUT;

        // P( semWriters )
        dwEvent = ::WaitForSingleObject( m_semWriters, INFINITE );
        ASSERT(dwEvent == WAIT_OBJECT_0);
    }

    inline void Unlock_DataWrite(){
        // V( semWriters )
        VERIFY( ::ReleaseSemaphore(m_semWriters, 1, NULL) );
    };

};

Of course we would also like to have some objects behaving like MFC's CSingleLock, i.e. automatically unlocking the locked CMutexRW upon leaving scope. Here's my implementation of CReadLock:

class CReadLock
{
protected:
    CMutexRW* m_pMutexRW;
    bool      m_bIsLocked;
public:
    CReadLock(CMutexRW* pMutexRW, const bool bInitialLock = false) :
        m_pMutexRW(pMutexRW), m_bIsLocked(false)
    {
        ASSERT(m_pMutexRW);
        if (bInitialLock){
            m_pMutexRW->Lock_DataRead();
            m_bIsLocked = true;
        }
    };

    inline const bool& IsLocked() const{
        return m_bIsLocked;
    };

    inline void Lock(){
        ASSERT(m_bIsLocked == false);
        m_pMutexRW->Lock_DataRead();
        m_bIsLocked = true;
    };

    inline void Unlock(){
        ASSERT(m_bIsLocked);
        m_pMutexRW->Unlock_DataRead();
        m_bIsLocked = false;
    };
    virtual ~CReadLock(){
        if (m_bIsLocked){
            m_pMutexRW->Unlock_DataRead();
        }
    };
};

followed by the implementation of CWriteLock:

class CWriteLock
{
protected:
    CMutexRW*   m_pMutexRW;
    bool        m_bIsLocked;
public:
    CWriteLock(CMutexRW* pMutexRW, const bool bInitialLock = false) :
        m_pMutexRW(pMutexRW), m_bIsLocked(false)
    {
        ASSERT(m_pMutexRW);
        if (bInitialLock){
            m_pMutexRW->Lock_DataWrite();
            m_bIsLocked = true;
        }
    };

    inline const bool& IsLocked() const{
        return m_bIsLocked;
    };

    inline void Lock(){
        ASSERT(m_bIsLocked == false);
        m_pMutexRW->Lock_DataWrite();
        m_bIsLocked = true;
    };

    inline void Unlock(){
        ASSERT(m_bIsLocked);
        m_pMutexRW->Unlock_DataWrite();
        m_bIsLocked = false;
    };
    virtual ~CWriteLock(){
        if (m_bIsLocked){
            m_pMutexRW->Unlock_DataWrite();
        }
    };
};

Usage example

Using these objects is quite straightforward; when wanting to read the data guarded by a CMutexRW object, construct a CReadLock object in the local scope, obtain the lock and do the actual read. Next, release the lock, or leave the local-scope. In the same way we can write the data in a thread-safe way.

class MyExampleObject{
protected:
      CMutexRW  m_mutexRW;
      int       m_Data;
public:
      void Set(const int& srcData){
           CWriteLock writeLock(&m_mutexRW, true);
           m_Data = srcData;
      }
      void Get(int& destData){
           CReadLock readLock(&m_mutexRW, true);
           destData = m_Data;
      }
};

There is (as observable) a small annoying problem; the Get routine is not const, i.e. the MyExampleObject does not behave as proper (data) objects should. This can be easily fixed by implementing the code as follows:

class MyExampleObject{
protected:
      mutable CMutexRW  m_mutexRW;
      int               m_Data;
public:
      void Set(const int& srcData){
           CWriteLock writeLock(&m_mutexRW, true);
           m_Data = srcData;
      }
      void Get(int& destData) const{
           CReadLock readLock(&m_mutexRW, true);
           destData = m_Data;
      }
};

Standard disclaimer

Although we use the discussed objects (slightly modified for better performance) extensively in our software, I cannot guarantee a 100% bug-proof, thread-safe and so on behaviour. So use it, use it well, but never forget, I'm just another programmer ;).