Back to course

Mutexes, Condition Variables and the Lost Wakeup

Producer-consumer with condition variables is a reported question at several firms, and a bounded blocking queue at several more. They are the same exercise, and it has three classic errors that an interviewer can spot in five seconds.

The shape

template <class T>
class BoundedQueue {
public:
    explicit BoundedQueue(std::size_t cap) : cap_(cap) {}

    void push(T item) {
        std::unique_lock lock(m_);
        not_full_.wait(lock, [this] { return q_.size() < cap_; });
        q_.push_back(std::move(item));
        lock.unlock();
        not_empty_.notify_one();
    }

    T pop() {
        std::unique_lock lock(m_);
        not_empty_.wait(lock, [this] { return !q_.empty(); });
        T item = std::move(q_.front());
        q_.pop_front();
        lock.unlock();
        not_full_.notify_one();
        return item;
    }
private:
    std::mutex m_;
    std::condition_variable not_full_, not_empty_;
    std::deque<T> q_;
    std::size_t cap_;
};

Two condition variables, not one. With a single variable, a notify_one intended for a waiting consumer can wake a waiting producer instead, which re-checks its predicate, finds it false and goes back to sleep, and the consumer is never woken. That is a lost wakeup, and it deadlocks a queue that is neither full nor empty.

The rest of this lesson is for subscribers

Unlock every lesson in Systems Programming for Trading, and every other premium course.

Subscribe to continue

Test your knowledge

Questions are only available to subscribers.
Continue
NextAtomics and the Memory Model

Keep reading Systems Programming for Trading

19 lessons in this course, and every other premium course, on one subscription.

Subscribe now
  • Every lesson in every course, with the worked examples and interactive simulators
  • Graded questions on every lesson, with explanations for the wrong answers as well as the right one
  • The trainers, timed assessments and brainteaser library that go with them