Multiple-writer thread-safe queue in C

Question

I am working on a multi-threaded C application using pthreads. I have one thread which writes to a a database (the database library is only safe to be used in a single thread), and several threads which are gathering data, processing it, and then need to send the results to the database thread for storage. I've seen in mentioned that it is "possible" to make a multiple-writer safe queue in C, but every place I see this mentioned simply says that it's "too complicated for this example" and merely demonstrates a single-writer safe queue.

I need the following things:

• Efficient insertion and removal. I would assume that like any other queue O(1) enqueueing and dequeueing is possible.
• Dynamically allocated memory, i.e. a linked structure. I need to not have an arbitrary limit on the size of the queue, so an array really isn't what I'm looking for.

EDIT: Reading threads should not spin on an empty queue, since there is likely to be minutes worth of time with no writes, with short bursts of large numbers of writes.

Answer 1

If you dont need a lock free queue, then you could just wrap up an existing queue with a lock.

Mutex myQueueLock;
Queue myQueue; 
void mtQueuePush(int value)
{
    lock(myQueueLock);
    queuePush(myQueue, value);
    unlock(myQueueLock);
}
int mtQueueNext()
{
    lock(myQueueLock);
    int value = queueFront(myQueue);
    queuePop(myQueue);
    unlock(myQueueLock);
    return value;
}

The only thing after that is to add some sort of handeling for mtQueueNext when the queue is empty.

EDIT: If you have a single reader, single writer lockless queue, you only need to have a lock around mtQueuePush, to prevent multiple simultaneous writers.

Theres a nubmer of single reader/writer lockless queues around, howver most of them are implemented as c++ template classes. However do a google search and if need be work out how to rewrite them in plain C.

Answer 2

http://www.liblfds.org

Lock-free data structure library written in C.

Has the M&S queue.

Answer 3

Sure, there are lockless queues. Based on what you've said in comments, though, performance here is not at all critical, since you're creating a thread per write anyway.

So, this is a standard use case for a condition variable. Make yourself a struct containing a mutex, a condition variable, a linked list (or circular buffer if you like), and a cancel flag:

write:
    lock the mutex
    (optionally - check the cancel flag to prevent leaks of stuff on the list)
    add the event to the list
    signal the condition variable
    unlock the mutex

read:
   lock the mutex
   while (list is empty AND cancel is false):
       wait on the condition variable with the mutex
   if cancel is false:  // or "if list non-empty", depending on cancel semantics
       remove an event from the list
   unlock the mutex
   return event if we have one, else NULL meaning "cancelled"

cancel:
   lock the mutex
   set the cancel flag
   (optionally - dispose of anything on the list, since the reader will quit)
   signal the condition variable
   unlock the mutex

If you're using a list with external nodes, then you might want to allocate the memory outside the mutex lock, just to reduce the time its held for. But if you design the events with an intrusive list node that's probably easiest.

Edit: you can also support multiple readers (with no portable guarantees for which one gets a given event) if in cancel you change the "signal" to "broadcast". Although you don't need it, it doesn't really cost anything either.

Answer 4

I'd go for multiple single-writer queues (one per writer thread). Then you can check this for how to get the single reader to read the various queues.