Technical Director and Chief Architect of Novaleaf Software (and Novaleaf Game Studios!) Novaleaf is Thailand's leader in real-time simulations, and is located in Bangkok. Jason is about as 'expert' at C# as one can get, and has a passion for high-performance simulations (scientific or otherwise) While Jason has a Linked-In, Twitter, and Facebook account, he never checks them. Apologies, email me!
Posts by Jason-Swearingen
  1. Kickstarter campign isn't looking so hot? ( Counting comments... )
  2. Want to get Kickstarted? Here’s what you need to know... ( Counting comments... )
  3. [Video] Why Salt is good for you: Handling password security in web applications ( Counting comments... )
  4. Getting started with Google App Engine (for .NET developers) ( Counting comments... )
  5. How to Architect a Worker Thread subsystem, step-by-step (C#) ( Counting comments... )
  6. MapFold: Simplifying Inter-Thread Communication. ( Counting comments... )
  7. Lock-Free Queue ( Counting comments... )
  8. Spatial Partitioning. Part 1: Survey of spatial partitioning solutions ( Counting comments... )
  9. Nobody Gives a Shit: Introspections of a start-up indie studio’s dealings with publishers. ( Counting comments... )
Advocacy / Technology/ Code /

Introduction
I have just completed rewriting of our "worker thread" execution subsystem, fixing some obscure race conditions, and wanted to share the solution in a "step by step" approach.

Primary Aim: (education)
to provide practical knowledge to those recently entered into the "system parallelization" field. I will describe the multithread relevent design process that went into the design and development of Novaleaf's new WorkerThread subsystem.

First step, what's the goal? (use case scenario)
it's very important for any development (not just multithreading) to fully understand your "functional objectives" before starting to architect, and then to architect your system (high-level design) before you code.

Here is my scenario:
Synchronization between a "main engine thread" and a reusable "worker thread" subsystem. main and worker threads should execute loops at a 1:1 frequency, with the start/end of the worker thread's loop tied to a specific part of the engine's loop code.

illustration of the scenario:
Worker Thread Workflow Diagram

High level design:

  1. "engine wait for worker": need main thread sync-point to wait for worker to finish
  2. "worker wait for engine": need worker to wait until main thread resumes worker (starts next loop)
  3. "others wait for worker" also need other systems to be able to wait for worker to finish. an example is if there is a shared resource that multiple threads access.
  4. Worker owns it's own thread:  The worker runs in an infinite loop, pausing when waiting for the engine (Design point #2).
  5. Keep it stupid simple!  There are many ways I could sexify (complicate) this setup, but there are three reasons why i do not:
    1. Educational purposes
    2. Complex thread synchronization has bugs (race conditions)
    3. "I use this in real life" (it works)

Implementation Phase 1: (identify existing solutions)

Design point #2,
"worker wait for engine" shows that to fulfill this functionality, only 1 thread (worker) needs to wait for the main engine thread. In this case, the .NET BCL class AutoResetEvent works nicely because it will allow a single waiter (the worker) through when the main thread says it's ready (signals).


//**worker loop, (full workflow)**
while(true){
//wait for engine to allow this worker to start it's next loop
waitForEngine_AutoResetEvent.WaitOne();

//do fancy asynchronous work here!

//worker informs engine that it is finished
waitForWorker_ManualResetEvent.Set();
}

Above is the worker thread's loop. it waits for the engine to signal it to proceed, does work, then informs the engine that it's finished.

Now for what the engine's code (partially) looks like:

//**engine thread**
//allow 1 waiting thread through,
//or if none are waiting, exactly 1 future caller through
//then automatically (instantly) resets to blocking.
waitForEngine_AutoResetEvent.Set();

We can not use ManualResetEvent because we need to call .Set() and .Reset() independently:

//**engine thread with race condition (bad)**
//allow waiting code through
waitForEngine_ManualResetEvent.Set();
//set to blocking
waitForEngine_ManualResetEvent.Reset();

This doesn't work because of the situation when worker has called waitForWorker_ManualResetEvent.Set(); but has not yet looped back and made the .WaitOne() call. the worker's execution may be suspended between those two lines, and thus the engine may itself .Set() and .Reset() before the worker even gets to the next line. It sounds unlikely, and it is, but it is not safe (it may fail 1 out of 1 million times).

Design point #1,
"engine wait for worker": we could get by with the design point #2 solution "AutoResetEvent" stated above, however we need to consider Design point #3.

Design point #3,
"others wait for worker": because of this, the AutoResetEvent solution doesn't work.

//fails because only the first waiter will be allowed through
//multiple systems may wait on the worker thread completing.
waitForWorker_AutoResetEvent.WaitOne();

however we also can not use the ManualResetEvent, because of the problem already outlined above in Design point#2.
If you look at the other classes in the .NET BCL System.Threading namespace, none of those seem to be a good fit for this problem. So looks like we need to write our own synchronization primitive!

Implementation Phase 2: (rethinking the problem)

To recap, we need a synchronization primitive similar to AutoResetEvent, however needs to only reset (block future calles) after the main engine thread finishes waiting. All threads, including the engine, should unblock once the worker thread's loop completes.

After thinking through the problem, it turns out we actually DO NOT need anything more complex than ManualResetEvent for the engine-wait-on-worker. here's why:

  1. if our worker calls waitForWorker_ManualResetEvent.Set() then all waiting threads will clear, and all future waits will clear
  2. if the engine calls waitForWorker_ManualResetEvent.Reset() after waiting for the worker to finish but before launching the worker's next loop, then the engine's target workflow is preserved.
  3. Here's the kicker: if other threads wait on the worker, they will suffer race conditions (example: worker's next loop starts before the other thread's call to .WaitOne() even finishes). Thus this workflow is unsupported. Other threads must synchronize with main, not with workers.

Implementation Phase 3: (Final take away)
Please pay special attention to my "Here's the kicker" list-item above. This shows that while my initial thoughts were to allow any "other thread" to synchronize with the worker thread, this requirement would have resulted in the construction of a custom (and complex) synchronization primitive. Also, on closer inspection this seems to be a significantly troubling anti-pattern which should consciously be avoided.


//**main thread, (full workflow)**
void Engine_UpdateTheWorker(float time)
{
//wait for worker's previous loop to finish
waitForWorker_manualResetEvent.WaitOne();
//reset our worker's waitEvent back to blocking
waitForWorker_manualResetEvent.Reset();

//do data synchronization
workerLoopTime=time;

//signal our worker to start it's next loop
waitForEngine_autoResetEvent.Set();
}

Above is the full implementation of the engine's synchronization code. This and the worker's loop code further above is copy-paste-programmer friendly for those looking to quickly utilize the architecture I have provided.

Conclusion: really really try not to re-invent the wheel.
There certainly will be times where the base synchronization primitives will not be enough to get the job done, but with the .NET 4.0 BCL System.Threading additions, those will (should) be few and far between. I hope that this step-by-step on the process I went through for re-designing Novaleaf's WorkerThread subsystem helps illustrate this point.