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.

When you say "multiple-writer," do you mean that you want the queue to support push() and pop() coming from multiple threads? — Matt Ball, Jul 31 '09 at 13:49
Do you mean a queue where two or more writer threads are adding to the queue concurrently, or a queue which has multiple possible writer threads, but only one of which writes to the queue at once? — , Jul 31 '09 at 13:51
- Multiple writer means multiple push()-ing threads. - Lock-free is not required by any means, but would be nice. - Concurrent writes are entirely possible, though not extraordinarily likely. (I.e there is no implicit guarantee that there will not be concurrent writes, but if one or more block until one is finished, that's not a huge issue.) — Edward, Jul 31 '09 at 14:08
BTW, one reason people may not have posted implementations is that this kind of code is tiresome though not too difficult to write in C. It's a lot simpler in C++. If you are not totally wedded to C, I suggest changing. — , Jul 31 '09 at 14:29
@Neil: At this point in the project I am totally wedded to C. I'd like to see what a lockless queue would look like, since, as onebyone mentioned, it's possible that my code might be code that would need it. I don't think it is, but I haven't tested its performance yet, either. — Edward, Jul 31 '09 at 14:45

Steve Jessop · Accepted Answer · 2009-07-31T21:04:54.633

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.

One problem I can see with that: When I decide to shut down the application, I'm going to need to stop the reader thread that is waiting on the condition variable. How would I go about doing that? — Edward, Jul 31 '09 at 14:39
Memory can be read simultaneously by any number of threads of execution. Thus, the read operation does not require mutexes. — Misguided, Jan 28 '12 at 04:41
@Julian: although in this context we've called the operation "read", it removes an item from the queue. It absolutely needs the lock to do that, and of course it also needs the lock in order to wait on the condition variable. — Steve Jessop, Jan 29 '12 at 16:16

score 5 · Answer 2 · answered May 23 '12 at 18:44

5

http://www.liblfds.org

Lock-free data structure library written in C.

Has the M&S queue.

answered May 23 '12 at 18:44

Nice answer, the library looks interesting though rather anonymous, there's not much about it around on net. Still it's a manageable amount of source code, so ought to be amenable to code review :) – Rob11311 Jul 04 '14 at 16:07

score 5 · Answer 3 · edited Dec 05 '19 at 14:43

5

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 handling 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.

There are a number of single reader/writer lockless queues around, however 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.

edited Dec 05 '19 at 14:43

Anmol Gautam

949
1
12
27

answered Jul 31 '09 at 14:18

Fire Lancer

29,364
31
116
182

That is a possibility, though I'd like it if, in the case where multiple items are in the queue, the reader could pop() the front while a writer push()-es on the back. There shouldn't be a need for mutual exclusion in that case. – Edward Jul 31 '09 at 14:23
Which is to say that, while I'm not against using a mutex in the design, I'd rather not wrap the whole damn thing in one. – Edward Jul 31 '09 at 14:24
2

This won't work. When there is a reader waiting for and item from the queue, it holds the lock and thus prevents any writers from adding items to the queue (assuming that queueFront()/queuePop() are blocking). If queueFront()/queuePop() are not blocking, then there is no way for the reader to wait for an item without polling. – mhagger Apr 23 '12 at 07:56

score 1 · Answer 4 · edited May 23 '17 at 12:07

1

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.

edited May 23 '17 at 12:07

Community

1
1

answered Jul 31 '09 at 13:53

Bahbar

17,760
43
62

Unfortunately, that's not really a possibility, since many threads are spawning, completing their tasks, and then writing the results to a queue, processed by a single database worker thread. Thus, each queue would only get written to once, defeating the whole purpose. – Edward Jul 31 '09 at 14:11
ok. So significant work per thread, with a single write to the queue at the end ? So the queue is not really a performance concern then. How about simply protecting the push method with a mutex ? – Bahbar Jul 31 '09 at 14:21

Multiple-writer thread-safe queue in C

4 Answers4

Linked