CRWCriticalSection : Another solution to the readers/writers problem with time-out

• Download source files - 2 Kb
• Download demo project - 22 Kb

Introduction

I got into multithreading reluctantly. I was happy for my applications to be sluggish. If I really had to, I would implement something with a timer. In utter laziness, I have even sometimes used the C++ equivalent of the VB DoEvents (a PeekMessage loop). Please do not tell anyone: if this comes out, I know it is you. Anyway, the users got insistent and I started adding threads to my applications.

It was a nightmare and it took me ages before I was able to stabilize them. The first problem is the fact that different threads access objects at the same time... or worse one deletes the object while the other accesses it. You do get some nasty exception faults. Not right away, of course! Only when your application is in production. To overcome this, you usually add Critical Sections all over your code to make sure that only one thread can access the object at one time.

Then comes the second problem: the dreaded "Mr Freeze". Two threads lock each other out and that's the end of your application as a living organism... and you do not even get a GPF that would have allowed to understand the problem. Needless to say that - again- this behaviour only happens at your clients, never in your nice and cozy debugging environment.

Even once you have managed to sort out your lock problems, by calling the critical sections in the same order among all threads, you get the performance issue. Every thread is waiting for the other one to finish something and the whole thing is painfully slow and your users start complaining - again!

A few months back, I was at that stage. My application was stable but slow and I did not have the beginning of an idea about how to improve it. My usual answer to moaning users was to advise them to buy a server with 82 processors. They did not usually take my idea seriously. Well, they have stopped doing that a long time ago! Close to depression, I was wandering idly through the articles of codeproject when I found this: A solution to the Readers/Writers Problem using semaphores , an article by Joris Koster. The title was so good I knew right away that it was matching my needs. Some of my threads were reading some pretty complicated structure. Other threads were actually modifying the structure. I could only allow one writer at a time. But as many readers as I wanted. I read the article, the title was good but the article was excellent. A definite 5+.

Only one problem: the priority was always given to readers and writers could remain waiting for ever (what the author called writer starvation). Not good for me. The other problem was the fact that Joris' code did not have a time-out. After my previous problems with deadlocks, I thought it would be useful to have some time-out mechanism. The problem could be traced and the program would start again gracefully.

Background

For my small class , I have used three types of synchronization objects. I thought it would be useful to remind what they were for. Specialists, please skip this section (and why are you reading this article anyway - haven't you read my disclaimer?).

The critical section :

This makes sure that only one thread can enter parts of the code at the same time. This way you can ensure that an object will not be changed by other threads during a given "critical section" of your code. This usually looks like this:

// Enter part of my code where I want my object to be "stable"

::EnterCriticalSection(&m_csMyObject);

// Modify my object

...

// Let other threads play around with my object

LeaveCriticalSection(&m_csMyObject);

The event :

This allows implementation of something like this:

while( !isOtherThreadReady)
;

except that the wait does not take any processor time. In other words, you can let a thread sleep and wake it up with an event. The code actually looks like this:

// Wait for ten seconds and give-up if I do not get the event

if ( WaitForSingleObject(m_hEvent,10000) != WAIT_OBJECT_0 )
return false;

The mutex:

The mutex is exactly like an event except if more than one thread are waiting for it, only one will get the event and the others will still be waiting.

Implementation

The reader's implementation.

We are waiting here for the eventual writing to be finished. We use a mutex because another writer could be waiting as well and we do not want both threads to be allowed to go on together.

bool CRWCriticalSection::LockReader(DWORD dwTimeOut)
{
// We make sure that nobody is writing

if ( WaitForSingleObject(m_hWritingMutex,dwTimeOut) != WAIT_OBJECT_0 )
return false;
...

Here we have a critical section so we can maintain safely the number of readers. If we have at least one, we reset an event to forbid the writers to start modifying.

// We need a critical section to update the number of readers

::EnterCriticalSection(&m_csReading);
{
m_nReaders++;
if ( m_nReaders == 1 )
{
// We must indicate that there are some readers

ResetEvent(m_hNobodyIsReading);
}
}
::LeaveCriticalSection(&m_csReading);
...

Finally, I release the mutex to let another thread in.

ReleaseMutex(m_hWritingMutex);
return true;
}

The UnlockReader() is straight forward. I simply maintain the state of the number of readers and of the "Nobody Is reading" flag/event.

void CRWCriticalSection::UnlockReader()
{
// We need a critical section to update the number of readers

::EnterCriticalSection(&m_csReading);
{
m_nReaders--;
ASSERT(m_nReaders >= 0);
if ( m_nReaders == 0 )
{
// We indicate that there are no more readers

SetEvent(m_hNobodyIsReading);
}
}
::LeaveCriticalSection(&m_csReading);
}

The writer's implementation

We are waiting for the mutex to indicate if a writer thread is working or if a reader is in the process of getting the right to go-on.

bool CRWCriticalSection::LockWriter(DWORD dwTimeOut)
{
// Only one writer at a time

if ( WaitForSingleObject(m_hWritingMutex,dwTimeOut) != WAIT_OBJECT_0 )
return false;
... 

Now that we have the m_hWritingMutex for ourselves, we know that no other reading or writing thread will go on. We simply wait for all the other reading threads to leave. If a time-out occurs at this stage, we must remember to release the mutex...

// Wait for all readers to leave

if ( WaitForSingleObject(m_hNobodyIsReading,dwTimeOut) != WAIT_OBJECT_0 )
{
// We have waited too long, so we have to set the "Writing" mutex

ReleaseMutex(m_hWritingMutex);
return false;
}

return true;
}

The UnlockWriter() could not be simpler. I free the mutex to let another reader or writer in.

void CRWCriticalSection::UnlockWriter()
{
// Let other readers and writers in

ReleaseMutex(m_hWritingMutex);
}

Using the code

I have put a sample together so if you download the project you have something to look at rather than some dry C++ code. Not very useful but it will allow you to see how the system behaves under stress. I did use it to debug my class.

One very important thing: when you lock an event, make sure that you unlock it. This seems obvious but if you have an exception raised during the execution of the pseudo-critical section, you will get a deadlock. Hence I always use the section like this:

if ( m_csCriticalSection.LockReader(30000) )
{
  try
  {
  // My buggy code

  ...
  }
  catch(...)
  {
  ASSERT(false);
  }
  m_csCriticalSection.UnlockReader();
}

History

Version 1.0

27/10/2003

First release

Conclusion, remarks, thanks and apologies

Think long and hard before using multi-threading. If you can, use a timer. If there is absolutely no other way, then analyze well your problem before starting to implement the solution. Identify your critical objects and try to understand which thread reads and which threads modifies. For this, using the C++ keyword const is a good idea!

The whole class could definitely be improved. A mutex does not take in account how long a thread has been waiting for... so maybe an algorithm that would take this account and even a priority would be fantastic... That's beyond my needs. But in a similar fashion I was inspired by Joris Koster, somebody will be by this article and hopefully post his implementation here! I also use 3 different synchronization objects which is maybe overkill. Let me know if you find a simpler way of doing it.

I have said, but I will repeat it, thank you Joris for your great article. Without you, I would probably be jobless!

Finally, apologies if my English is not as flowing as I would want it to be... French is my native language. Corrections on the code and the lingo are welcome.