Click here to Skip to main content
Click here to Skip to main content

A solution to the Readers/Writers Problem using semaphores

By , 18 Oct 2002
Rate this:
Please Sign up or sign in to vote.

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 Wink | ;) .

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Joris Koster
Web Developer
Netherlands Netherlands
Joris lives in the geographical center of The Netherlands, Utrecht, where he started his academic education Computational Science in 1995.
In (aug) 2002 he (finally Wink | ;) ) obtained his master's degree by finishing his Master's thesis resulting from research into parallel matrix-vector multiplication on supercomputers.
 
In 1997 he started working (parttime) at Accent Pointe, the IT department of Accent Groupe, a market maker company at the Amsterdam Euronext Exchange.
 
From aug 2002 he continued working at Accent Pointe, but on a full-time basis, where his major occupation became the development of a new portfolio management model (like Black & Scholes, Binominal trees, etc.) and a fast (parallel) implementation.
 
Besides this major occupation, several minor engineering projects ensure his programming skills are kept up to date Wink | ;)

Comments and Discussions

 
Questionhelp me with c code PinmemberMember 102727118-Nov-13 3:35 
Questionhelp with me with c code PinmemberMember 102727118-Nov-13 3:34 
GeneralWriters given preference Pinmemberhumor_me22-Dec-08 14:57 
GeneralStarvation PinmemberMember 17363567-May-08 3:51 
QuestionUsing mutex PinmemberTulio18-Sep-07 8:20 
Generalwhy wait on read semaphore in Lock_DataRead () PinmemberSandipShahane14-Feb-07 8:55 
GeneralWhy not critical Section PinmemberDewdman425-Dec-05 16:45 
Questionshared memory with mm.h in C??? Pinmembermora2630-Oct-05 8:45 
GeneralI need help using semaphore Pinsussmyvince3-Feb-05 16:16 
GeneralRe: I need help using semaphore PinmemberJoris Koster4-Feb-05 5:01 
http://www.google.com/search?q=Dining+philosophers&lr=[^]
GeneralRe: I need help using semaphore PinmemberJoris Koster4-Feb-05 5:18 
GeneralRe: I need help using semaphore Pinmembermyvince6-Feb-05 14:56 
Generalsharing the object over multiple processes Pinmemberboutblock26-May-03 6:02 
GeneralOne less semaphore, but write starvation PinmemberPieter Viljoen30-Oct-02 9:08 
GeneralNOPE, and read the article carefully [Re: One less semaphore, but write starvation] PinmemberJoris Koster3-Nov-02 11:04 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] PinmemberPieter Viljoen3-Nov-02 15:40 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] PinmemberPieter Viljoen5-Nov-02 11:51 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] PinsussAnonymous20-Dec-03 16:22 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] PinsussAnonymous25-Jan-05 8:15 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] PinmemberCodebender13-Sep-04 16:38 
QuestionSame functionality from different machines? PinmemberSimian Jones25-Oct-02 7:35 
AnswerRe: Same functionality from different machines? PinmemberDaniel Turini25-Oct-02 7:43 
GeneralRe: Same functionality from different machines? PinmemberJoris Koster3-Nov-02 10:43 
GeneralDatafeed Pinmembertortini20-Oct-02 21:22 
GeneralRe: Datafeed PinmemberJoris Koster3-Nov-02 10:40 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140415.2 | Last Updated 19 Oct 2002
Article Copyright 2002 by Joris Koster
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid