Producer-consumer queue- std::queue or user-written linked-list?

3
votes

I came across the following post detailing a producer consumer lock-free queue:

C++ Lock free producer/consumer queue

which uses a custom-written linked list. What is the purpose of writing a linked-list, when one could just use std::queue and write some accessor wrappers around the data structure?

1
c++multithreadingc++11queueproducer-consumer
You cannot create a lock-free data structure from a non-lock-free data structure. You can make it concurrent easily, but not without locks. - Casey
Lock-free programming is very subtle, and there is no "quick and obvious way" to do it. I recommend spending a week or six researching the topic if you're genuinely interested, though; it'd be time well spent. - Kerrek SB
@Casey could you please elaborate on why not? I presume you are directly answering why one must write their own data structure rather than use std::queue? - mezamorphic
It isn't safe for multiple threads to concurrently modify a std::queue. The "accessor wrappers" you suggest would necessarily need to ensure that only one thread at a time could call the member functions of the contained std::queue. You would effectively be implementing a mechanism that requires other threads to wait on the thread currently accessing the shared data structure to complete, i.e., a lock. - Casey

1 Answers

0
votes

It isn't possible to design a std::list where push_back and pop_front don't both modify the size member. If you have two threads calling these at the same time, they'll probably corrupt the list. You could write a wrapper accessor to make it safe, by using locks. That defeats the goal of a lock-free structure. Both push_back and pop_front of a std::deque will need to modify an internal "vector" of node pointers, and if they're called at the same time by two different threads, again, they corrupt the deque.

One can easily write a list-like or circular-buffer lock-free producer/consumer queue, but no standard C++ container can qualify.