2

So, suppose I have a struct A { int val1; int val2}; And a std::queue<A> fifo

Two threads, Reader thread: reads all contents from A, and clears it. Writer thread: writes one A at a time to queue.

Is std::queue enough for maintaining a lockless thread safe fifo container with one reader and one writer? If not, can any other stl container work? dequeue is the default underlying in std::queue.

themagicalyang
  • 2,493
  • 14
  • 21
  • If you're asking this question you're not yet experienced enough with the c++11 memory model to begin to attempt such a thing. Use a mutex and condition variable and revisit when your users are complaining that your server is too slow. – Richard Hodges Dec 16 '15 at 09:52

1 Answers1

3

No, you absolutely cannot use any STL container directly for this. What you can use is any of the many, many lockfree queue implementations that already exist for C++. You should search for "SPSC" meaning Single Producer, Single Consumer. For example, from Boost: http://www.boost.org/doc/libs/1_59_0/doc/html/boost/lockfree/spsc_queue.html

One wait-free, fixed-size implementation is right here: SPSC lock free queue without atomics (but do note the answer and comments there, which explain some ways that the implementation in the question is not completely safe, and offer some solutions).

Community
  • 1
  • 1
John Zwinck
  • 239,568
  • 38
  • 324
  • 436
  • You should remove this link. A lock-free queue without atomics is absolutely not thread-safe and never will be. The atomics are required to ensure correct release/acquire behaviour in the memory model. – Richard Hodges Dec 16 '15 at 09:50
  • @RichardHodges: The question I linked asks about the safety of that implementation, and the answer and comments on the question explain how to make it safe and under what conditions it is already safe. I've added a caveat to my answer. – John Zwinck Dec 16 '15 at 09:59
  • Understood. Another problem with that implementation is that it relies on UB (the integer wrapping). It's therefore not logically correct. – Richard Hodges Dec 16 '15 at 10:21
  • @RichardHodges: Integer overflow is only UB in C and C++ if the integers are signed. In this case they are unsigned, so there is no UB that I can see. For reference: http://stackoverflow.com/questions/18195715/why-is-unsigned-integer-overflow-defined-behavior-but-signed-integer-overflow-is – John Zwinck Dec 16 '15 at 10:26