Fastest implementation of one thread providing data, many threads consuming data

Question

I have a lot of data that I want to disseminate to many different threads. This data is coming from a single thread. The consuming threads can safely access the container simultaneously.

The data needs to be merged into the container ever delta seconds (50ms < delta < 1), during which time the consuming threads need to be locked out, but not blocked. Similarly, when the data producer wants to merge in the data, it should wait until any reading threads are finished (which should be fast), but no one else should start reading as the update needs to occur as soon as possible.

I'm working on linux (platform specific solution is perfectly fine/expected) and I care about every millisecond. What sort of locking mechanisms should I use or is there an even better model for this problem?

Answer 1

It looks like you need to use the pthread read/write locks. They allow you to restrict access to one writer OR multiple readers. Look at pthread_rwlock_init to initialize the lock, pthread_rwlock_rdlock to acquire the lock for reading data, and pthread_rwlock_wrlock to acquire the lock for writing data.

Answer 2

Sounds like a good use for pthread read-write locks along with some thread-safe queues. The producer thread inserts items into the queue. The worker pool will pull items off of the queue and process the data. I'm not sure how the output will work but you might want to use a thread-safe queue here as well... maybe a priority queue to automatically merge the data if it makes sense.

The locked queue construct is nothing more than a mutex for exclusive locking, a std::queue for data storage, and a condition variable to wake up threads that are waiting on the queue. The enqueue method grabs the lock, inserts into the queue, releases the lock, and signals the condition. The dequeue method grabs the mutex, waits on the condition using the mutex as a guard, and dequeues any data that is there when it is woken up. This is a pretty standard producer-consumer style queue.

Before you roll your own solution, you might want to check out Boost.MPI and Boost.Thread. They both provide nicer C++ interfaces over the underlying OS implementation. I've used Boost.Thread a lot but it doesn't provide a nice message passing interface, but it does improve over pthread.

If you are really into multi-processing, you might want to give Boost.MPI or maybe Apache Qpid serious consideration. I plan on looking into Qpid and AMPQ for future projects since they both provide nice message-based interfaces.

Answer 3

If there is only one data producer thread and memory is not a consideration, you may want to consider using a merge and swap algorithm.

In it, the writer thread creates a copy of the data structure while readers continue to use the original, merges in new changes, then performs an exchange of the two structures within a mutex or critical section (or reader/writer lock). If your Unix platform supports interlocked exchange as an atomic operation, you can perform a lock-free exchange maximizing read throughput through they implementation.