Process P1 has statement S1. Process P2 has statement S2. Process P3 has stateme

Question

Process P1 has statement S1. Process P2 has statement S2. Process P3 has statement S3. Statements S2 or S3 can execute in any order but they should not execute before S1.

Explanation / Answer

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 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: Collapse | Copy Code 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 ", (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: Collapse | Copy Code 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: Collapse | Copy Code 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. Collapse | Copy Code 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: Collapse | Copy Code 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; } };

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.