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. This lesson builds the queue, then breaks it each of the three ways, slowly enough to see where each break hides.

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_;
};

Everything a condition variable does is in those two functions. A waiter takes the mutex, checks a predicate about shared state, and if the predicate is false, atomically releases the mutex and goes to sleep. A notifier changes the shared state under the mutex and signals. The waiter wakes up holding the mutex again and re-checks. Two of the three errors are failures to respect one of those steps. The third is a failure to aim the signal.