Katkat
Back

Implement Concurrent Utilities in C++

BelvederetradingSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests your ability to implement a thread-safe, generic blocking queue in C++ using synchronization primitives like mutexes and condition variables.

Problem Statement

Implement a thread-safe BlockingQueue class template in C++. The queue should provide a way for multiple producer and consumer threads to safely add and remove elements. If the queue is empty, a pop operation should block the calling thread until an element becomes available. You must also implement a mechanism to shut down the queue, ensuring that threads waiting on an empty queue are woken up and informed that no more items will be added.

Requirements

  • Provide void push(T value): Adds an item to the queue.
  • Provide bool pop(T& out_value): Removes an item. Returns true if an item was retrieved, and false if the queue is shut down and empty.
  • Provide void shutdown(): Signals that no further elements will be added and wakes up all waiting threads.
  • Ensure the implementation is exception-safe and prevents data races.

Example

BlockingQueue q;
// Thread 1:
q.push(42);

// Thread 2:
int val;
if (q.pop(val)) { // Blocks until 42 is pushed
    // val == 42
}

// Thread 3:
q.shutdown(); // Any blocked pop() calls will return false

Constraints

  • Use std::mutex, std::condition_variable, and std::queue.
  • Assume T is movable or copyable.
  • Consider the behavior when multiple consumers are waiting and shutdown() is called.

Hints

Hint 1

Use a `std::mutex` to protect the internal `std::queue` and a `std::condition_variable` to manage thread waiting states.

Hint 2

For the `pop()` method, use the `wait()` overload of `std::condition_variable` with a predicate that checks both the queue size and a boolean flag for the shutdown state.

Hint 3

Ensure `shutdown()` sets a flag and calls `notify_all()` so that all sleeping threads can re-evaluate the predicate and exit gracefully.

Follow-up questions

  • How would you modify this class to support a bounded size (capacity) to prevent memory overflow if producers are faster than consumers?
  • What are the performance implications of using a single mutex for both push and pop operations, and could you improve this with a lock-free approach?
  • How would you handle potential exceptions thrown by the copy constructor or assignment operator of type T within the push method?