The Single WriterMultiple Reader Guard (SWMRG)

[Previous] [Next]

Many applications have a basic synchronization problem commonly referred to as a single-writer/multiple-readers scenario. The problem involves an arbitrary number of threads that attempt to access a shared resource. Some of these threads (the writers) need to modify the contents of the data, and some of the threads (the readers) need only to read the data. Synchronization is necessary because of the following four rules:

1. When one thread is writing to the data, no other thread can write to the data.
2. When one thread is writing to the data, no other thread can read from the data.
3. When one thread is reading from the data, no other thread can write to the data.
4. When one thread is reading from the data, other threads can also read from the data.

Let's look at this problem in the context of a database application. Let's say we have five end users, all accessing the same database. Two employees are entering records into the database, and three employees are retrieving records from the database.

In this scenario, rule 1 is necessary because we certainly can't have both Employee 1 and Employee 2 updating the same record at the same time. If both employees attempt to modify the same record, Employee 1's changes and Employee 2's changes might be made at the same time, and the information in the record might become corrupted.

Rule 2 prohibits an employee from accessing a record in the database if another employee is updating that record. If this situation is not prevented, Employee 4 might read the contents of a record while Employee 1 is altering the same record. When Employee 4's computer displays the record, the record will contain some of the old information and some of the updated information—this is certainly unacceptable. Rule 3 is needed to solve the same problem. The difference in the wording of rules 2 and 3 prevents the situation regardless of who gains access to the database record first—an employee who is trying to write or an employee who is trying to read.

Rule 4 exists for performance reasons. It makes sense that if no employees are attempting to modify records in the database, the content of the database is not changing and therefore any and all employees who are simply retrieving records from the database should be allowed to do so. It is also assumed that there are more readers than there are writers.

OK, you have the gist of the problem. Now the question is, how do we solve it?

NOTE

---

The code that I present here is new. Previously, I published solutions to this problem that were criticized for two reasons. First, my previous implementations were too slow because they were designed to be useful in many scenarios. For example, they used more kernel objects so that threads in different processes could synchronize their access to the database. Of course, my implementation still worked even in a single-process scenario, but the heavy use of kernel objects added a great deal of overhead when all threads were running in a single process. I must concede that the single-process case is probably much more common.

The second criticism was that my implementation could potentially lock out writer threads altogether. From the rules stated previously, if a lot of reader threads accessed the database, writer threads could never get access to the resource.

I have addressed both of these issues with the implementation I present here. It avoids kernel objects as much as possible and uses a critical section for most of the synchronization.

To simplify things, I have encapsulated my solution in a C++ class, called CSWMRG (which I pronounce "swimerge"); it stands for single-writer/multiple-reader guard. The SWMRG.h and SWMRG.cpp files (in Figure 10-3) show my implementation.

Using a CSWMRG couldn't be easier. You simply create an object of the CSWMRG C++ class and then call the appropriate member functions as your application dictates. There are only three methods in the C++ class (not including the constructor and destructor):

 VOID CSWMRG::WaitToRead(); // Call this to gain shared read access. VOID CSWMRG::WaitToWrite(); // Call this to gain exclusive write access. VOID CSWMRG::Done(); // Call this when done accessing the resource. 

You call the first method, WaitToRead, just before you execute code that reads from the shared resource. You call the second method, WaitToWrite, just before you execute code that reads or writes to the shared resource. You call the last method, Done, when your code is no longer accessing the shared resource. Pretty simple, huh?

Basically, a CSWMRG object contains a number of member variables that reflect the state of how threads are accessing the shared resource. The table below describes each member's purpose and summarizes how the whole thing works. See the source code for the details.

Member	Description
m_cs	This guards all the other members so that manipulating them can be accomplished atomically.
m_nActive	This reflects the current state of the shared resource. If the value is 0, no thread is accessing the resource. If the value is greater than 0, the value indicates the number of threads that are currently reading from the resource. If the number is negative, a writer is writing to the resource. The only valid negative number is -1.
m_nWaitingReaders	This value indicates the number of reader threads that want to access the resource. This value is initialized to 0 and is incremented every time a thread calls WaitToRead while m_nActive is -1.
m_nWaitingWriters	This value indicates the number of writer threads that want to access the resource. This value is initialized to 0 and is incremented every time a thread calls WaitToWrite while m_nActive is greater than 0.
m_hsemWriters	When threads call WaitToWrite but are denied access because m_nActive is greater than 0, the writer threads all wait on this semaphore. While a writer thread is waiting, new reader threads are denied access to the resource. This prevents reader threads from monopolizing the resource. When the last reader thread that currently has access to the resource calls Done, this semaphore is released with a count of 1, waking one waiting writer thread.
m_hsemReaders	When threads call WaitToRead but are denied access because m_nActive is -1, the reader threads all wait on this semaphore. When the last waiting writer thread calls Done, this semaphore is released with a count of m_nWaitingReaders, waking all waiting reader threads.

The SWMRG Sample Application

The SWMRG application ("10 SWMRG.exe"), listed in Figure 10-3, tests the CSWMRG C++ class. The source code and resource files for the application are in the 10-SWMRG directory on this book's companion CD-ROM. I always run the application in the debugger so I can closely watch all the class member functions and variable changes.

When you run the application, the primary thread spawns several threads that all execute the same thread function. Then the primary thread waits for all these threads to terminate by calling WaitForMultipleObjects. When all the threads have terminated, their handles are closed and the process exits.

Each secondary thread displays a message that looks like this.

If you want this thread to simulate reading the resource, click the Yes button; if you want the thread to simulate writing to the resource, click No. These actions simply cause the thread to call the SWMRG object's WaitToRead or WaitToWrite function, respectively.

After calling one of these two functions, the thread displays another message box that looks like one of these.

The message box suspends the thread and simulates the time that it takes the thread to manipulate the resource that it now has access to.

Of course, if a thread is currently reading from the resource and you instruct a different thread to write to the resource, the writer thread's message box does not appear because the thread is waiting inside its call to WaitToWrite. Similarly, if you instruct a thread to read while a writer thread's message box is displayed, the thread that wants to read is suspended inside its call to WaitToRead—its message box won't appear until any and all writer threads have finished their simulated access of the resource.

When you click on the OK button to dismiss either of these message boxes, the thread that had access to the resource calls Done and the SWMRG object tends to any waiting threads.

Figure 10-3. The SWMRG application

SWMRG.cpp

 /****************************************************************************** Module: SWMRG.cpp Notices: Copyright (c) 2000 Jeffrey Richter ******************************************************************************/ #include "..\CmnHdr.h" /* See Appendix A. */ #include "SWMRG.h" /////////////////////////////////////////////////////////////////////////////// CSWMRG::CSWMRG() { // Initially no readers want access, no writers want access, and // no threads are accessing the resource m_nWaitingReaders = m_nWaitingWriters = m_nActive = 0; m_hsemReaders = CreateSemaphore(NULL, 0, MAXLONG, NULL); m_hsemWriters = CreateSemaphore(NULL, 0, MAXLONG, NULL); InitializeCriticalSection(&m_cs); } /////////////////////////////////////////////////////////////////////////////// CSWMRG::~CSWMRG() { #ifdef _DEBUG // A SWMRG shouldn't be destroyed if any threads are using the resource if (m_nActive != 0) DebugBreak(); #endif m_nWaitingReaders = m_nWaitingWriters = m_nActive = 0; DeleteCriticalSection(&m_cs); CloseHandle(m_hsemReaders); CloseHandle(m_hsemWriters); } /////////////////////////////////////////////////////////////////////////////// VOID CSWMRG::WaitToRead() { // Ensure exclusive access to the member variables EnterCriticalSection(&m_cs); // Are there writers waiting or is a writer writing? BOOL fResourceWritePending = (m_nWaitingWriters || (m_nActive < 0)); if (fResourceWritePending) { // This reader must wait, increment the count of waiting readers m_nWaitingReaders++; } else { // This reader can read, increment the count of active readers m_nActive++; } // Allow other threads to attempt reading/writing LeaveCriticalSection(&m_cs); if (fResourceWritePending) { // This thread must wait WaitForSingleObject(m_hsemReaders, INFINITE); } } /////////////////////////////////////////////////////////////////////////////// VOID CSWMRG::WaitToWrite() { // Ensure exclusive access to the member variables EnterCriticalSection(&m_cs); // Are there any threads accessing the resource? BOOL fResourceOwned = (m_nActive != 0); if (fResourceOwned) { // This writer must wait, increment the count of waiting writers m_nWaitingWriters++; } else { // This writer can write, decrement the count of active writers m_nActive = -1; } // Allow other threads to attempt reading/writing LeaveCriticalSection(&m_cs); if (fResourceOwned) { // This thread must wait WaitForSingleObject(m_hsemWriters, INFINITE); } } /////////////////////////////////////////////////////////////////////////////// VOID CSWMRG::Done() { // Ensure exclusive access to the member variables EnterCriticalSection(&m_cs); if (m_nActive > 0) { // Readers have control so a reader must be done m_nActive--; } else { // Writers have control so a writer must be done m_nActive++; } HANDLE hsem = NULL; // Assume no threads are waiting LONG lCount = 1; // Assume only 1 waiter wakes; always true for writers if (m_nActive == 0) { // No thread has access, who should wake up? // NOTE: It is possible that readers could never get access // if there are always writers wanting to write if (m_nWaitingWriters > 0) { // Writers are waiting and they take priority over readers m_nActive = -1;  // A writer will get access m_nWaitingWriters--;  // One less writer will be waiting hsem = m_hsemWriters;  // Writers wait on this semaphore // NOTE: The semaphore will release only 1 writer thread } else if (m_nWaitingReaders > 0) { // Readers are waiting and no writers are waiting m_nActive = m_nWaitingReaders; // All readers will get access m_nWaitingReaders = 0; // No readers will be waiting hsem = m_hsemReaders; // Readers wait on this semaphore lCount = m_nActive; // Semaphore releases all readers } else { // There are no threads waiting at all; no semaphore gets released } } // Allow other threads to attempt reading/writing LeaveCriticalSection(&m_cs); if (hsem != NULL) { // Some threads are to be released ReleaseSemaphore(hsem, lCount, NULL); } } //////////////////////////////// End of File ////////////////////////////////// 

 SWMRG.h /****************************************************************************** Module: SWMRG.h Notices: Copyright (c) 2000 Jeffrey Richter ******************************************************************************/ #pragma once /////////////////////////////////////////////////////////////////////////////// class CSWMRG { public: CSWMRG(); // Constructor ~CSWMRG(); // Destructor VOID WaitToRead(); // Call this to gain shared read access VOID WaitToWrite(); // Call this to gain exclusive write access VOID Done(); // Call this when done accessing the resource private: CRITICAL_SECTION m_cs; // Permits exclusive access to other members HANDLE m_hsemReaders; // Readers wait on this if a writer has access HANDLE m_hsemWriters; // Writers wait on this if a reader has access int m_nWaitingReaders; // Number of readers waiting for access int m_nWaitingWriters; // Number of writers waiting for access int m_nActive; // Number of threads currently with access // (0=no threads, >0=# of readers, -1=1 writer) }; //////////////////////////////// End of File ////////////////////////////////// 

 SWMRG.rc //Microsoft Developer Studio generated resource script. // #include "resource.h" #define APSTUDIO_READONLY_SYMBOLS ///////////////////////////////////////////////////////////////////////////// // // Generated from the TEXTINCLUDE 2 resource. // #include "afxres.h" ///////////////////////////////////////////////////////////////////////////// #undef APSTUDIO_READONLY_SYMBOLS ///////////////////////////////////////////////////////////////////////////// // English (U.S.) resources #if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENU) #ifdef _WIN32 LANGUAGE LANG_ENGLISH, SUBLANG_ENGLISH_US #pragma code_page(1252) #endif //_WIN32 ///////////////////////////////////////////////////////////////////////////// // // Icon // // Icon with lowest ID value placed first to ensure application icon // remains consistent on all systems. IDI_SWMRG ICON DISCARDABLE "SWMRG.ico" #ifdef APSTUDIO_INVOKED ///////////////////////////////////////////////////////////////////////////// // // TEXTINCLUDE // 1 TEXTINCLUDE DISCARDABLE BEGIN "resource.h\0" END 2 TEXTINCLUDE DISCARDABLE BEGIN "#include ""afxres.h""\r\n" "\0" END 3 TEXTINCLUDE DISCARDABLE BEGIN "\r\n" "\0" END #endif // APSTUDIO_INVOKED #endif // English (U.S.) resources ///////////////////////////////////////////////////////////////////////////// #ifndef APSTUDIO_INVOKED ///////////////////////////////////////////////////////////////////////////// // // Generated from the TEXTINCLUDE 3 resource. // ///////////////////////////////////////////////////////////////////////////// #endif // not APSTUDIO_INVOKED 

 SWMRGTest.cpp /****************************************************************************** Module: SWMRGTest.Cpp Notices: Copyright (c) 2000 Jeffrey Richter ******************************************************************************/ #include "..\CmnHdr.h" /* See Appendix A. */ #include <tchar.h> #include <process.h> // for _beginthreadex #include "SWMRG.h" /////////////////////////////////////////////////////////////////////////////// // Global Single-Writer/Multiple-Reader Guard synchronization object CSWMRG g_swmrg; /////////////////////////////////////////////////////////////////////////////// DWORD WINAPI Thread(PVOID pvParam) { TCHAR sz[50]; wsprintf(sz, TEXT("SWMRG Test: Thread %d"), PtrToShort(pvParam)); int n = MessageBox(NULL, TEXT("YES: Attempt to read\nNO: Attempt to write"), sz, MB_YESNO); // Attempt to read or write if (n == IDYES) g_swmrg.WaitToRead(); else g_swmrg.WaitToWrite(); MessageBox(NULL, (n == IDYES) ? TEXT("OK stops READING") : TEXT("OK stops WRITING"), sz, MB_OK); // Stop reading/writing g_swmrg.Done(); return(0); } /////////////////////////////////////////////////////////////////////////////// int WINAPI _tWinMain(HINSTANCE hinstExe, HINSTANCE, PTSTR pszCmdLine, int) { // Spawn a bunch of threads that will attempt to read/write HANDLE hThreads[MAXIMUM_WAIT_OBJECTS]; for (int nThreads = 0; nThreads < 8; nThreads++) { DWORD dwThreadId; hThreads[nThreads] = chBEGINTHREADEX(NULL, 0, Thread, (PVOID) (DWORD_PTR) nThreads, 0, &dwThreadId); } // Wait for all the threads to exit WaitForMultipleObjects(nThreads, hThreads, TRUE, INFINITE); while (nThreads—) CloseHandle(hThreads[nThreads]); return(0); } //////////////////////////////// End of File //////////////////////////////////