Lock-Free Queue Policy

[JoelFilho]

Implement a single-producer, single-consumer lock-free queue container and its corresponding policy.

As unbounded queues have reduced real-time applications, the lock-free queue may be bounded.

Interface

(names are placeholders)

// Container
// Same member functions as blocking_queue and others
template<typename T, std::size_t N>
class lock_free_bounded_queue;

// A helper, to convert the template into a type-only one
// It needs to match the signature template<typename...> class Queue on the pipeline
template<std::size_t N>
struct declaration_helper {
template<typename T>
using type = lock_free_bounded_queue<T, N>;
};

// Policy
template<std::size_t N>
inline constexpr tdp::detail::policy_type< declaration_helper<N>::type > queue_lockfree = {};

Possible issues

• Bounded queues may require special treatment for a blocked push situation, i.e. full queue.
  • Might require a new interface for all containers, symmetric to pop_unless.

Possible implementations

As lock-free programming is error-prone, an ideal solution would be importing the data structure from a BSL-compatible library.

• Boost.LockFree (BSL)
• libcds (BSL)

The atomic_queue benchmarks point a few other options (not all BSL-compatible) and compares their performance. Could be useful.

[JoelFilho]

Update: boost::lockfree::queue requires trivially assignable types, so it can't be used with std::tuple (the pipeline input), and boost::lockfree::spsc_queue can't be unbounded, so it's not compatible with the current implementation.

Ideally, an unbounded version would be used. In case it's not possible, I'll go back to SPSC queue, and possibly implement a busy wait for full queue, as an "optimistic" version. It would need a similar waiting implementation to pop_unless to avoid locking on exit.

So, for now, the Boost.LockFree option won't be used.

[bftjoe]

Do you think that unbounded queues are a good idea at all to support, as this can result in unbounded memory consumption?