<–Part 1

Last time, we saw how to protect a shared resource with a critical section. Today we’ll look at why a critical section, though technically correct, can cause problems. Let’s write some critical-section-protected code and see what might happen:

SharedResource gSharedResource;
CRITICAL_SECTION g_csResourceLock; // Assume that this has been initialized properly

Glob GlobulateSharedResource()
{
    Glob returnValue;

    EnterCriticalSection(&g_csResourceLock);
    for(int i=0; i<gSharedResource.dagronCount; i++)
    {
        Globulate(returnValue, gSharedResource.dagrons[i]);
    }
    LeaveCriticalSection(&g_csResourceLock);

    return returnValue;
}

Dagron* AddDagron()
{
    Dagron* pNewDagron = new Dagron;

    EnterCriticalSection(&g_csResourceLock);
    gSharedResource.dagronCount++;
    gSharedResource.dagrons = (Dagron**)realloc(gSharedResource.dagrons, gSharedResource.dagronCount * sizeof(Dagron*));
    gSharedResource.dagrons[gSharedResource.dagronCount-1] = pNewDagron;
    LeaveCriticalSection(&g_csResourceLock);

    return pNewDagron;
}

Now, this is fine code. It has no threading issues…or does it? What if our thread function looked like this:

unsigned int __stdcall HappyThread(void* pData)
{
    Glob glob = GlobulateSharedResource();
    Flazmify(glob);
    if(ShouldAddDagron())
      AddDagron();
}

Now we spin up two of those threads. What’s going to happen? Let’s see:

  • Thread A enters GlobulateSharedResource() and acquires the lock
  • Thread B enters GlobulateSharedResource() and attempts to acquire the lock, but the lock is taken, so it blocks
  • Thread A globulates all of the Dagrons, then leaves the critical section and returns its glob
  • Thread B now globulates all of the dagrons, but is interrupted before it can finish the operation
  • Thread A flazmifies the glob, and sees that it should add a Dagron. It enters AddDagron(), but is blocked when trying to acquire the lock
  • Thread B finishes globulating the Dagrons
  • Thread A adds its Dagron, then goes on to Globulate again

Sure, it’s all quote-unquote “correct,” but do you see how in the first couple of steps, only one of the two threads can be globulating the shared resource at the same time, even though there’s no reason to prevent that? You can imagine how much worse it would be if we spun up three, or four, or a dozen of these threads. But we can’t eliminate the lock, because then one thread could be adding a Dagron at the same time as another is reading the list, which would cause all sorts of badness to occur.

This brings us to the next tip:

Tip #4: A contentious lock is the same as single-threaded code.

In the above code, the g_csResourceLock critical section is so contentious that, even though we’ve got multiple threads going at once, only one of them can really be doing work at a time. Ironically, the problem actually gets worse the more threads there are.

So, what do we do? Enter the multiple-reader-single-writer lock. In general, you can have any number of threads reading a particular piece of data, so long as only one thread is actually writing to it. The multi-reader-single-writer lock encapsulates that concept by allowing a thread to enter the lock in different ways: as either a reader or a writer (sometimes called shared mode and exclusive mode respectively). A reader will block out a writer, a writer will block out readers and other writers, but a reader will not block out another reader. Unfortunately, the waters get a bit murkier here when trying to find an implementation of such a construct to use:

  • In Windows, there is the Slim Reader/Writer Lock. Unfortunately, these locks are only available if you’re targeting Windows Vista or higher. If you want to target Windows XP, then you’ve got to search elsewhere.
  • Boost has an implementation. However, if you’re not already using boost, it can be a big dependency to take just for threading primitives, especially since the threading library is one that requires a compile (which can be complicated and time-consuming for Boost).
  • Roll your own using other primitives. This is the route that we’ve gone in the GSD Engine, using Glenn Slayden‘s implementation as a baseline. It’s clean, decently efficient, correct, and works on Windows XP and up. You could very easily convert this to work on another platform as well. We have actually made some minor modifications to that code, which we will post next time (this post is already long enough as is).

Let’s take a look at how we’ll change our code to take advantage of a multi-reader-single-writer lock:

SharedResource gSharedResource;
MultiReaderSingleWriterLock g_csResourceLock; // Assume that this has been initialized properly

Glob GlobulateSharedResource()
{
    Glob returnValue;

    g_csResourceLock.EnterReader();
    for(int i=0; i<gSharedResource.dagronCount; i++)
    {
        Globulate(returnValue, gSharedResource.dagrons[i]);
    }
    g_csResourceLock.LeaveReader();

    return returnValue;
}

Dagron* AddDagron()
{
    Dagron* pNewDagron = new Dagron;

    g_csResourceLock.EnterWriter();
    gSharedResource.dagronCount++;
    gSharedResource.dagrons = (Dagron**)realloc(gSharedResource.dagrons, gSharedResource.dagronCount * sizeof(Dagron*));
    gSharedResource.dagrons[gSharedResource.dagronCount-1] = pNewDagron;
    g_csResourceLock.LeaveWriter();

    return pNewDagron;
}

The thread function remains the same. Let’s take a look at what happens now:

  • Thread A enters GlobulateSharedResource() and enters as a reader
  • Thread B enters GlobulateSharedResource() and enters as a reader
  • Thread A begins globulating the Dagrons, but is interrupted before it can finish
  • Thread B globulates all of its Dagrons
  • Thread B flazmifies the resulting glob
  • Thread B starts to add a new Dagron. However, EnterWriter() blocks because there is a reader
  • Thread A finishes globulating the Dagrons and leaves as a reader
  • Thread A begins flazmifying the glob
  • Thread B is now able to enter as a writer and begin adding a Dagron, but is interrupted before it can finish
  • Thread A finishes flazmifying its glob
  • Thread A skips adding a Dagron, and goes back into globulating the Dagrons
  • Thread A blocks on EnterReader(), because there exists a writer
  • Thread B finishes adding the Dagron, and leaves as a writer
  • Thread B begins globulating the Dagrons
  • etc.

Now threads A and B can globulate the dagrons at the same time, and it’s only when a thread wants to add a new Dagron that there is ever any contention for the lock. Assuming that adding a Dagron is more rare than globulating the list of Dagrons, then we’ve just made a radical improvement in the performance of our code.

Next time: the dreaded lockless constructs.

Go to Part 2.5.