Project 2: Thread-Safe Producer-Consumer Queue

Build a queue that safely connects producers and consumers without busy-waiting.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Main Programming Language C++17
Coolness Level Genuinely Clever
Business Potential Resume Gold
Prerequisites C++ basics, RAII, basic threading
Key Topics mutexes, condition variables, shutdown protocol, atomics

1. Learning Objectives

  1. Build a multi-producer/multi-consumer queue with safe shutdown.
  2. Use condition variables correctly (no spurious wakeup bugs).
  3. Understand happens-before and data races.
  4. Validate concurrency with TSan and stress tests.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Mutexes and Locking Discipline

Description

Mutexes provide mutual exclusion. A disciplined locking policy is the difference between correctness and deadlocks.

Definitions & Key Terms

  • Mutex: exclusive lock.
  • Critical section: region protected by a mutex.

Mental Model Diagram (ASCII)

Thread A: lock -> modify -> unlock
Thread B: lock -> modify -> unlock

How It Works

  1. Acquire lock before touching shared data.
  2. Release lock as soon as possible.
  3. Never hold locks across slow operations.

Minimal Concrete Example

std::lock_guard<std::mutex> lock(m);
q.push(item);

Common Misconceptions

  • “Locks are always slow” -> contention is the real problem.

Check-Your-Understanding Questions

  • What happens if a lock is not released?

Where You’ll Apply It

  • Queue push/pop critical sections

2.2 Condition Variables

Description

Condition variables allow threads to sleep until a predicate is true. They can wake spuriously, so you must re-check.

Definitions & Key Terms

  • Predicate: condition to be true when waking.
  • Spurious wakeup: wake without notify.

Mental Model Diagram (ASCII)

wait(cv, pred)
   | releases lock
   | sleeps
   | re-locks on wake

How It Works

  1. Consumer locks mutex.
  2. cv.wait(lock, pred) releases lock and sleeps.
  3. On notify, thread wakes, re-locks, and checks predicate.

Minimal Concrete Example

cv.wait(lock, [&]{ return !q.empty() || shutdown; });

Common Misconceptions

  • “notify always wakes exactly one” -> spurious wakeups can happen.

Check-Your-Understanding Questions

  • Why is the predicate required?

Where You’ll Apply It

  • Queue pop

2.3 Memory Ordering and Shutdown Flags

Description

Thread shutdown protocols often use atomics to avoid races between producers and consumers.

Definitions & Key Terms

  • Atomic flag: lock-free state indicator.
  • Happens-before: ordering of writes and reads.

Mental Model Diagram (ASCII)

producer sets shutdown -> consumers observe flag

Minimal Concrete Example

std::atomic<bool> shutdown{false};

Common Misconceptions

  • “Atomic means everything is safe” -> only that variable is atomic.

Where You’ll Apply It

  • Queue shutdown behavior

3. Project Specification

3.1 What You Will Build

A templated queue with blocking pop(), non-blocking try_pop(), and a clean shutdown() that wakes all consumers.

3.2 Functional Requirements

  1. Thread-safe push and pop.
  2. Blocking pop with condition variable.
  3. shutdown() releases all waiting consumers.

3.3 Non-Functional Requirements

  • No busy waiting.
  • Safe under multiple producers/consumers.
  • Clean shutdown under load.

3.4 Example Usage / Output

ThreadSafeQueue<int> q;
q.push(42);
auto v = q.pop();

3.5 Data Formats / Schemas / Protocols

  • Internal: std::queue<T>, std::mutex, std::condition_variable, bool shutdown.

3.6 Edge Cases

  • shutdown() while queue still has items
  • consumer waits with no producers

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

cmake -S . -B build
cmake --build build
./build/queue_demo --items=5 --seed=7

3.7.2 Golden Path Demo

[PRODUCER] push 0
[CONSUMER] pop 0
[PRODUCER] push 1
[CONSUMER] pop 1
[QUEUE] shutdown
[CONSUMER] exit

3.7.3 Failure Demo

[FAIL] consumer did not exit on shutdown

4. Solution Architecture

4.1 High-Level Design

[Producers] -> [Queue + Mutex] -> [Condition Variable] -> [Consumers]

4.2 Key Components

| Component | Responsibility | Key Decisions | |—|—|—| | Mutex | protect queue | lock granularity | | Condition variable | block consumers | predicate design | | Shutdown flag | signal exit | atomic or guarded |

4.3 Data Structures

struct ThreadSafeQueue {
    std::queue<T> q;
    std::mutex m;
    std::condition_variable cv;
    bool shutdown;
};

4.4 Algorithm Overview

  • push: lock, push, unlock, notify.
  • pop: lock, wait predicate, pop, return.

5. Implementation Guide

5.1 Development Environment Setup

cmake -S . -B build
cmake --build build

5.2 Project Structure

queue-safe/
├── src/queue.hpp
├── src/queue.cpp
├── tests/queue_tests.cpp
└── CMakeLists.txt

5.3 The Core Question You’re Answering

“How do I share data between threads without races or wasting CPU?”

5.4 Concepts You Must Understand First

  • Mutex locking discipline
  • Condition variable usage
  • Data races and happens-before

5.5 Questions to Guide Your Design

  • When do you hold the lock?
  • What is the correct predicate for waiting?
  • How do you wake all consumers on shutdown?

5.6 Thinking Exercise

Draw a timeline for two consumers waiting and a producer waking them. What happens on shutdown?

5.7 The Interview Questions They’ll Ask

  1. Why must cv.wait use a predicate?
  2. What is a data race?
  3. What is the difference between notify_one and notify_all?

5.8 Hints in Layers

Hint 1: cv.wait(lock, pred) is the safe pattern. Hint 2: set shutdown flag before notifying. Hint 3: return std::optional<T> from pop.

5.9 Books That Will Help

| Topic | Book | Chapter | |—|—|—| | Condition variables | C++ Concurrency in Action | Ch. 4 | | Thread lifecycle | C++ Concurrency in Action | Ch. 2 | | Concurrency basics | The C++ Programming Language | Concurrency chapter |

5.10 Implementation Phases

Phase 1: Single Producer/Consumer (2-3 days)

  • Basic queue with mutex.
  • Checkpoint: passes basic tests.

Phase 2: Blocking Pop (2-3 days)

  • Add condition variable.
  • Checkpoint: no busy wait.

Phase 3: Shutdown (2-3 days)

  • Implement shutdown flag + notify_all.
  • Checkpoint: clean exit.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |—|—|—|—| | Shutdown flag | atomic / mutex-guarded | mutex-guarded | simplicity | | Pop result | throw / optional | optional | explicit shutdown handling |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |—|—|—| | Unit | single-thread behavior | push/pop | | Concurrency | multi-thread stress | 4 producers, 4 consumers | | Shutdown | exit logic | shutdown with empty queue |

6.2 Critical Test Cases

  1. Consumers block on empty queue.
  2. Shutdown wakes all consumers.
  3. No data races under TSan.

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |—|—|—| | Missing predicate | spurious wakeup bug | use cv.wait(lock, pred) | | Notify without lock | lost wakeups | hold lock when updating state | | Shutdown race | consumers hang | set flag then notify_all |

7.2 Debugging Strategies

  • Use TSan to catch races.
  • Add log lines around wait/notify.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add try_pop.

8.2 Intermediate Extensions

  • Add bounded queue with backpressure.

8.3 Advanced Extensions

  • Add lock-free variant (Michael-Scott queue).

9. Real-World Connections

9.1 Industry Applications

  • Worker thread pools
  • Task schedulers

9.2 Interview Relevance

  • Condition variable and race condition questions

10. Resources

10.1 Essential Reading

  • C++ Concurrency in Action (condvar, threads)
  • The C++ Programming Language (concurrency chapter)

11. Self-Assessment Checklist

  • I can explain why spurious wakeups occur.
  • I can design a clean shutdown protocol.
  • My queue passes TSan.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Blocking pop with predicate
  • Clean shutdown

Full Completion:

  • Stress tests pass
  • No TSan warnings

Excellence:

  • Bounded queue with backpressure