Introducing lunchbox::LFQueue< T >

The second installment on Lunchbox introduces the lock-free queue.

Lunchbox uses two naming schemes when implementing containers which have a STL pendant, ‘LF’ and ‘MT’. In both cases the containers are thread-safe, in contrast to their STL counterparts. These classes carefully document what types of multi-threaded access are allowed, and which methods might only be accessed from a certain thread or in a certain state, if any.

‘MT’ stands for multi-threaded and typically uses synchronization primitives and blocking access. More on ‘MT’ classes in a later post.

‘LF’ stands for lock-free and uses atomic variables and non-blocking access. Lunchbox provides an Atomic class, which is derived from a library which recently got accepted as boost::lock_free. Atomic variables are a standard concept, google it if you’re not familiar with it.

Implementing lock-free containers is a very tricky business. Smart minds spend a lot of time on it, and still get it wrong quite often. For that reason, the functionality of the LFQueue is limited. To begin with, it has a fixed-size storage allocated at construction time. For that reason, a push might fail if the queue is full. Furthermore, only a single thread may write and (another) single thread might read at the same time, that is, at most two threads can access the LFQueue at the same time.

All these restrictions seem severe, but they allow for a fast and simple implementation. A quick test on my laptop yields:

[roku Release master]% ./Lunchbox/tests/mtQueue
193.339 reads/ms
193.34 writes/ms
[roku Release master]% ./Lunchbox/tests/lfQueue
12288.8 reads/ms, 6629.31 empty/ms
6145.42 writes/ms, 2031.51 full/ms


Collage uses the LFQueue in its multicast implementation. The RSPConnection uses a protocol thread handling the sending of data, acknowledgment, negative acknowledgement and retransmissions. Each connection has a fixed set of data buffers, which are constantly shuffled around between the application and protocol thread. At high wire speed (10GigE), more than 100.000 buffers need to be shifted each second. From the protocol thread to the application thread this is blocking, using an MTQueue, and in the other direction it’s non-blocking using a LFQueue. Since the queue size (number of buffers) is fixed, and only two threads are involved, the LFQueue is well suited here. For the curious, here is more background on the RSP implementation.

Introducing Lunchbox: Monitor< T >

We’ve recently refactored the Equalizer and Collage base library co::base into a separate library and project called Lunchbox. This post has some background on this change.

Why Lunchbox? It’s a basic ‘toolbox’ library for multi-threaded programming. This combined with the famous ‘the free lunch is over’ quote lead to the name Lunchbox.

I’ve decided to do a weekly series of posts where I present one feature/class of Lunchbox which is beyond the basic, well-documented threading primitives provided by STL and boost. Today it’s the turn of the template class Monitor.

The monitor is a higher-level primitive based on a condition variable. Lunchbox also has a Condition class which encapsulates a condition variable and associated lock. If you’re not familiar with condition variables, google it. Smarter people than me have written good articles about them, and the Lunchbox API is pretty straight-forward.

The monitor allows to observe the state of a variable in a blocking fashion. You can think of it as a blocking variable: A monitor has a value which can be incremented, decremented and set. Any thread can wait on the monitor to reach a certain value (waitEQ), to leave a certain value (waitNE), or to reach (waitGE) or undercut (waitNE) a given value. Using a monitor makes the code easier to understand and robust, as compared to using a traditional semaphore or barrier.

In Equalizer I typically use them to monitor a state for synchronization. For example, the pipe initialization needs to wait for the node to be initialized. Since these tasks are queued and executed in parallel, the pipe thread monitors the node state to pass initialization. The eq::Node has a Monitor< State > which represents its current state (stopped, running, failed, …):

enum State
{
STATE_STOPPED,
STATE_INITIALIZING,
STATE_INIT_FAILED,
STATE_RUNNING,
STATE_FAILED
};
lunchbox::Monitor< State > _state;

This monitor allows to wait on the state to reach a certain value, which is used in Node::waitInitialized to wait for the node thread to finish initialization from the pipe thread:

void Node::waitInitialized() const
{
_state.waitGE( STATE_INIT_FAILED );
}

The node state is advanced after initialization by the node main thread:

_state = initResult ? STATE_RUNNING : STATE_INIT_FAILED;

Similarly, the per-node frame synchronization during rendering is using monitors of frame numbers to synchronize the node main thread and pipe render threads.

Since the monitor is a template class, you can use it with your own data types. Monitors have become an invaluable primitive in Collage and Equalizer for thread synchronization.