Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Hybrid Structures
The lockless ring buffer works very well when the producer and consumer are both running more or less constantly. If the consumer is running faster than the producer, then it will spend a lot of time in the loop. This situation isn't ideal, because it wastes CPU cycles that could be used for something else.
The solution is to use a hybrid strategy, where you use a lock when the structures is not busy, but switch to lockless mode when it is busy. The best synchronization primitive for implementing this strategy is the condition variable. These have been part of the POSIX threading API from the start, and were added to the Win32 API with Vista.
A condition variable is associated with a mutex lock. You must acquire the lock before you do anything with the condition variable. It supports two operations: sleep and signal. When you sleep on a condition variable, you atomically release the mutex. When you signal a condition lock, any threads that were sleeping on it awaken and attempt to acquire the mutex. They block while doing so, and one of them resumes when you release the mutex.
In the ring buffer example, the consumer might decide to wait on a condition variable if the queue is empty after testing it a few times. Then you have a problem: When do you signal the condition variable? You could do it after every insertion into the ring buffer, but that idea adds a lot of overhead if both threads are busy—exactly the case where you want a minimum of overhead.
Fortunately, you can optimize this technique. The consumer will wait for the condition variable only if the queue is empty. If only one message is in the queue after an insert operation, the producer signals the condition variable. This design can generate some spurious wake events, but that's better than having the consumer miss some messages.
What happens if the producer inserts a value between when the consumer consumes the last one and sleeping? Isn't it possible for the consumer to sleep just after the producer has signaled the condition variable? This is why condition variables are associated with a mutex. The procedure for sleeping is something like this:
- Lock the mutex.
- Test whether the queue is still empty.
- If so, atomically release the mutex, and sleep on the condition variable.
- Release the mutex.
On the producer side, the procedure for signaling the condition variable is similar:
- Lock the mutex.
- Signal the condition variable.
- Release the mutex.
Because the producer has to acquire the mutex first, the condition variable cannot be signaled between steps 1 and 3 on the consumer side. If the condition variable is signaled just before the consumer's step 1, the test in step 2 will avoid sleeping. If it's signaled after step 3, it will awaken the consumer.
The exact case when you ought to switch between locked and lockless mode depends on your particular code, but this kind of hybrid approach has the potential to give very good performance.