Full Text Search: The Key to Better Natural Language Queries for NoSQL in Node.js
A common coding pattern in multi-threaded development is having a number of worker threads wait to perform a task and having a manager or producer thread queue work items for them. To implement this pattern without resorting to the inefficient process of periodically polling the work queue, you need an event-raising mechanism, a role traditionally filled by the Windows SDK functions of CreateEvent and SetEvent. Once a worker thread has been notified of work item availability via an event, the mechanism will acquire a lock, dequeue a work item, and then release the lock.
The trouble with this scenario is that the code to implement the worker thread needs to have two wait statements: one to wait for the event to be raised, and another to wait for the lock to be acquired. Although coding the two wait statements is not overly onerous, having two statements doubles the chance of coding errors and means twice the amount of code to handle run-time error conditions. As threading scenarios become more complex, the need to have separate event-listening and lock-acquisition statements can lead to bugs and code clutter.
To address the separate event-listening and lock-acquisition statements problem, Vista introduces a new threading primitive called a condition, which is represented by the data type CONDITION_VARIABLE. Conditions are similar in nature to events, but rather than requiring a call to WaitForSingleObject or WaitForMultipleObjects to wait for an event, a new function called SleepConditionVariableCS has been added. This call allows a thread to wait for the CONDITION_VARIABLE to be woken and for a lock to be managed as part of the same call. The code sample below shows the simplest possible use of condition variables:
CRITICAL_SECTION cs; CONDITION_VARIABLE cv; InitializeCriticalSection(&cs); EnterCriticalSection(&cs); while(!/*check shared state to see if we can do work*/) SleepConditionVariableCS(&cv, &cs, INFINITE); //cv has been woken. cs is owned by this thread //do work here LeaveCriticalSection(&cs);
The code sample declares a CRITICAL_SECTION and a CONDITION_VARIABLE, initializes and enters the critical section, and then checks to see whether work has been queued by another thread. If there is no work to do, it calls the SleepConditionVariableCS function, which will release the critical section and wait for the condition variable to be woken. Once the condition variable has been set, the critical section is re-acquired before SleepConditionVariableCS returns. The thread is then able to do any work that requires modification of shared states, after which the thread leaves the critical section. The key point is that waiting for state to change and dealing with lock acquisition is handled by a single API call.
The code for dealing with condition variables on the threads that raise the event can call either WakeConditionVariable (if a single worker thread needs to be woken) or WakeAllConditionVariable (if all the threads waiting on a single condition variable need to be woken). WakeConditionVariable is typically used when a single item has been added to a work queue, while WakeAllConditionVariable is used if multiple worker threads need to be woken to handle a workload, or a exit flag has been set to indicate all worker threads should exit gracefully.
Introducing Slim Reader/Writer Locks
In the same way that Vista introduces the condition variable to augment the functionality of events, it also introduces slim reader/writer (SRW) locks to build on critical sections. A critical section is designed to allow only a single thread access at a time; this works well in a number of scenarios but falls short in an implementation with a number of reader threads and a more limited number of writer threads. Using critical sections in this scenario is sub-optimal, as the entry of one reader thread into a critical section prevents other reader threads from entering, which is not required. The real requirement is having either one writer active or, if no writer is active, having multiple simultaneous reader threads. The code below shows the new reader/writer data type and functions in use:
SRWLOCK readerWriterLock; InitializeSRWLock(&readerWriterLock); AcquireSRWLockExclusive(&readerWriterLock); //only one thread in here at a time ReleaseSRWLockExclusive(&readerWriterLock); AcquireSRWLockShared(&readerWriterLock); //many threads can come in here ReleaseSRWLockShared(&readerWriterLock);
Although the addition of a reader/writer lock as part of the in-built threading APIs is a little anti-climatic when third-party libraries such as Boost have supported this and many other advanced threading APIs for quite a while, the in-built functions make life easier for developers who stick primarily to the Windows SDK. Thankfully, SRW locks work well with the new condition variables, and a new API called SleepConditionVariableSRW enables you to combine waits and acquisition of a SRW lock. A parameter to SleepConditionVariableSRW indicates whether the lock should be acquired shared or exclusively when the function returns.
Prepare Yourself for Multi-Threaded Programming
The new threading and synchronization APIs introduced in Vista likely foreshadow an even larger increase in the API set that will make multi-threaded programming easier and less error-prone. With the rapid increase in multi-core processors and multi-processor machines, splitting processing tasks into multiple threads is now more important than ever before.
About the Author
Nick Wienholt is an independent Windows and .NET consultant based in Sydney, Australia. He is the author of Maximizing .NET Performance from Apress, and specializes in system-level software architecture and development with a particular focus on performance, security, interoperability, and debugging. Nick can be reached at NickW@dotnetperformance.com.