Click here to Skip to main content
15,867,308 members
Articles / Desktop Programming / MFC
Article

A solution to the Readers/Writers Problem using semaphores

Rate me:
Please Sign up or sign in to vote.
3.61/5 (14 votes)
18 Oct 20024 min read 348.8K   3.2K   41   42
A solution to the Readers/Writers Problem using semaphores

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

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


Written By
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 Pin
Member 102727118-Nov-13 3:35
Member 102727118-Nov-13 3:35 
Questionhelp with me with c code Pin
Member 102727118-Nov-13 3:34
Member 102727118-Nov-13 3:34 
GeneralWriters given preference Pin
humor_me22-Dec-08 14:57
humor_me22-Dec-08 14:57 
GeneralStarvation Pin
M1cr0ch1p7-May-08 3:51
M1cr0ch1p7-May-08 3:51 
QuestionUsing mutex Pin
Tulio18-Sep-07 8:20
Tulio18-Sep-07 8:20 
Generalwhy wait on read semaphore in Lock_DataRead () Pin
SandipShahane14-Feb-07 8:55
SandipShahane14-Feb-07 8:55 
GeneralWhy not critical Section Pin
Dewdman425-Dec-05 16:45
Dewdman425-Dec-05 16:45 
Questionshared memory with mm.h in C??? Pin
mora2630-Oct-05 8:45
mora2630-Oct-05 8:45 
GeneralI need help using semaphore Pin
myvince3-Feb-05 16:16
sussmyvince3-Feb-05 16:16 
GeneralRe: I need help using semaphore Pin
Joris Koster4-Feb-05 5:01
Joris Koster4-Feb-05 5:01 
http://www.google.com/search?q=Dining+philosophers&lr=[^]
GeneralRe: I need help using semaphore Pin
Joris Koster4-Feb-05 5:18
Joris Koster4-Feb-05 5:18 
GeneralRe: I need help using semaphore Pin
Member 17070286-Feb-05 14:56
Member 17070286-Feb-05 14:56 
Generalsharing the object over multiple processes Pin
Philippe Bouteleux26-May-03 6:02
Philippe Bouteleux26-May-03 6:02 
GeneralOne less semaphore, but write starvation Pin
Pieter Viljoen30-Oct-02 9:08
Pieter Viljoen30-Oct-02 9:08 
GeneralNOPE, and read the article carefully [Re: One less semaphore, but write starvation] Pin
Joris Koster3-Nov-02 11:04
Joris Koster3-Nov-02 11:04 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] Pin
Pieter Viljoen3-Nov-02 15:40
Pieter Viljoen3-Nov-02 15:40 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] Pin
Pieter Viljoen5-Nov-02 11:51
Pieter Viljoen5-Nov-02 11:51 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] Pin
Anonymous20-Dec-03 16:22
Anonymous20-Dec-03 16:22 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] Pin
Anonymous25-Jan-05 8:15
Anonymous25-Jan-05 8:15 
GeneralRe: NOPE, and read the article carefully [Re: One less semaphore, but write starvation] Pin
Codebender13-Sep-04 16:38
Codebender13-Sep-04 16:38 
QuestionSame functionality from different machines? Pin
Simian Jones25-Oct-02 7:35
Simian Jones25-Oct-02 7:35 
AnswerRe: Same functionality from different machines? Pin
Daniel Turini25-Oct-02 7:43
Daniel Turini25-Oct-02 7:43 
GeneralRe: Same functionality from different machines? Pin
Joris Koster3-Nov-02 10:43
Joris Koster3-Nov-02 10:43 
GeneralDatafeed Pin
Roberto Tortini20-Oct-02 21:22
Roberto Tortini20-Oct-02 21:22 
GeneralRe: Datafeed Pin
Joris Koster3-Nov-02 10:40
Joris Koster3-Nov-02 10:40 

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

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