Project 4: Implement a Thread-Safe Queue (Arc + Mutex)

Build a bounded multi-producer multi-consumer queue with blocking semantics using Arc, Mutex, and Condvar.

Quick Reference

Attribute	Value
Difficulty	Advanced
Time Estimate	1 week
Main Programming Language	Rust (Alternatives: C++ for comparison)
Alternative Programming Languages	C++ (std::mutex/condition_variable), Go (channels)
Coolness Level	High
Business Potential	High
Prerequisites	Basic concurrency, ownership, RAII
Key Topics	Arc, Mutex, Condvar, Send/Sync, bounded buffer

1. Learning Objectives

By completing this project, you will:

Implement a bounded, blocking queue safe for multiple producers and consumers.
Understand how Arc and Mutex interact with ownership and borrowing.
Use Condvar correctly to avoid lost wakeups and deadlocks.
Provide deterministic stress tests and throughput benchmarks.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Shared Ownership with Arc and Send/Sync

Fundamentals

Arc<T> is an atomically reference-counted pointer for shared ownership across threads. Unlike Rc, it uses atomic increments and decrements so it can be safely shared. Send and Sync are auto traits that determine whether a type can be transferred or shared between threads. A queue that is used by multiple threads must be Send + Sync, and Arc<Mutex<T>> is the standard pattern that achieves this safely.

Deep Dive into the concept

The core challenge in multithreaded Rust is expressing shared ownership safely. Arc<T> provides this by storing an atomic refcount. Cloning an Arc increments the count, dropping decrements it. When the count reaches zero, the allocation is freed. This mirrors Rc but with atomic operations, which are more expensive but thread-safe.

Send and Sync are not just markers; they are the compiler’s proof that it is safe to move or share data across threads. Send means ownership can be transferred to another thread. Sync means references can be shared. For a type to be Sync, it must be safe for multiple threads to access it simultaneously. Mutex<T> provides that guarantee by enforcing mutual exclusion at runtime. Arc<Mutex<T>> is therefore both Send and Sync as long as T is Send.

In practice, you will design your queue as a struct containing Mutex<Inner> plus a Condvar. The queue itself is then wrapped in an Arc and cloned into producer and consumer threads. Each thread locks the mutex to access the inner state. The Arc ensures the queue lives as long as any thread needs it. This is a direct application of ownership: the allocation is owned collectively by the threads, and the Arc refcount ensures it is freed when no longer used.

The subtlety is that Arc does not guarantee safety of the data itself; it only guarantees shared ownership. You must still enforce synchronization. This is why Arc<T> alone is not enough for a queue; you need Arc<Mutex<T>>. The mutex enforces the aliasing rule: one mutable access at a time. In return, you get compile-time safety: the borrow checker won’t allow you to access T without holding the lock.

Understanding Send and Sync is crucial because they are how Rust encodes concurrency safety into types. For example, Rc<T> is not Send, so you cannot move it into a thread. RefCell<T> is not Sync, so you cannot share it between threads. This is a static guarantee that prevents data races. In this project, you will see these trait bounds appear in function signatures and compiler errors, and you will learn how to reason about them.

How this fit on projects

This concept is applied in §4.2 (key components) and §5.10 (architecture). It also connects directly to Project 8 (lock-free stack) where you replace locks with atomics.

Definitions & key terms

Arc: Atomic reference-counted pointer.
Send: Safe to move ownership across threads.
Sync: Safe to share references across threads.
Mutex: Mutual exclusion lock.

Mental model diagram (ASCII)

Arc<Queue>
  | clone to threads
  v
+---------+   +---------+
| Thread1 |   | Thread2 |
+---------+   +---------+
     \           /
      \         /
      Mutex<Inner>

How it works (step-by-step)

Create Arc<Queue>.
Clone it into each thread.
Each thread locks the mutex to access shared state.
Arc drops when the last thread exits.

Minimal concrete example

let q = Arc::new(Queue::new());
let q2 = q.clone();
thread::spawn(move || q2.push(1));

Common misconceptions

“Arc makes data thread-safe.” Only ownership is safe; you still need locks.
“Send/Sync are runtime properties.” They are compile-time proofs.

Check-your-understanding questions

Why is Arc required instead of Rc?
What does Sync guarantee for a queue type?
Why must T: Send for Mutex<T> to be Sync?

Check-your-understanding answers

Rc is not thread-safe because refcounting is not atomic.
That shared references can be safely used by multiple threads.
Because the mutex can hand out &mut T to other threads.

Real-world applications

Thread pools and work queues.
Producer-consumer pipelines.

Where you’ll apply it

This project: §3.1, §4.2, §5.10 Phase 1.
Also used in: Project 9: Connection Pool.

References

TRPL Ch. 16 (threads, mutexes).
Rust Atomics and Locks (mutex design).

Key insights

Shared ownership is necessary but not sufficient; synchronization is the real safety boundary.

Summary

Arc + Mutex is the canonical Rust pattern for shared, mutable state across threads.

Homework/Exercises to practice the concept

Share a counter across two threads with Arc<Mutex<usize>>.
Remove the mutex and observe compiler errors.

Solutions to the homework/exercises

Lock, increment, unlock inside each thread.
Rust will reject shared mutable access without synchronization.

2.2 Condition Variables and the Bounded Buffer Problem

Fundamentals

A bounded buffer has a fixed capacity. Producers must block when the buffer is full, and consumers must block when it is empty. Condition variables (Condvar) provide a way to put threads to sleep and wake them when a condition changes. The correct pattern is: lock the mutex, check the condition in a loop, and wait on the condvar if the condition is not satisfied. This avoids lost wakeups.

Deep Dive into the concept

The bounded buffer is a classic concurrency problem. The core challenge is coordinating producers and consumers without busy-waiting. A condition variable works with a mutex: the thread checks a condition, and if it is not satisfied, it calls wait, which atomically unlocks the mutex and suspends the thread. When another thread changes the condition (e.g., pushes or pops), it signals the condvar, waking up one or more waiting threads. The waiting thread then re-locks the mutex and re-checks the condition.

The re-check in a loop is critical. Spurious wakeups can happen: a thread may wake up without the condition being true. Therefore, the rule is always while !condition { condvar.wait(...) }. This is a standard pitfall in concurrency. Another pitfall is lost wakeups, which occur if you check the condition, then wait, but a signal arrives between those two actions. The correct pattern avoids this by holding the mutex while checking and waiting.

In a bounded queue, you typically have two condition variables: not_empty and not_full. When a producer pushes an item, it signals not_empty. When a consumer pops an item, it signals not_full. This keeps producers and consumers moving efficiently. You also need to track the current length to decide when to block. The inner state might be { queue: VecDeque<T>, capacity: usize }.

The borrow checker helps here: you can’t access the inner queue without holding the mutex lock because the lock guard is the only way to get &mut Inner. This creates a natural discipline. The safety contract of Condvar is also explicit: you must use the same mutex for the condition and call wait in a loop.

A subtlety is fairness. Condition variables do not guarantee fairness; some threads may starve if you always notify one thread. You can choose notify_one or notify_all. notify_one is efficient but may cause starvation in some patterns; notify_all is safer but less efficient. For this project, use notify_one and document the trade-offs.

How this fit on projects

This concept is central to §3.2 requirements and §5.10 Phase 2. It also appears in Project 9 (connection pool blocking).

Definitions & key terms

Condvar: Condition variable.
Lost wakeup: Signal missed by a waiting thread.
Spurious wakeup: Waking without condition being true.
Bounded buffer: Queue with fixed capacity.

Mental model diagram (ASCII)

Producers -> [Queue] -> Consumers
      ^         |         ^
      |      not_full   not_empty

How it works (step-by-step)

Producer locks mutex.
If full, wait on not_full.
Push item, unlock, notify not_empty.
Consumer locks mutex.
If empty, wait on not_empty.
Pop item, unlock, notify not_full.

Minimal concrete example

while q.is_empty() {
    guard = not_empty.wait(guard).unwrap();
}

Common misconceptions

“You only need to check once.” You must check in a loop.
“notify_one is always fair.” It is not guaranteed.

Check-your-understanding questions

Why must you hold the mutex when calling wait?
What causes spurious wakeups?
When should you use notify_all?

Check-your-understanding answers

To avoid lost wakeups and to ensure atomic wait/unlock.
OS scheduling and condition variable semantics.
When many threads may need to re-check a condition.

Real-world applications

Task queues in thread pools.
Network server request queues.

Where you’ll apply it

This project: §5.10 Phase 2, §6.2 tests.
Also used in: Project 9: Connection Pool.

References

“The Little Book of Semaphores”.
TRPL Ch. 16.

Key insights

Condition variables are safe only when paired with a mutex and a loop.

Summary

The bounded buffer problem is solved by correct use of Condvar and careful state checks.

Homework/Exercises to practice the concept

Implement a bounded buffer in pseudocode.
Remove the while and observe incorrect behavior.

Solutions to the homework/exercises

Use while full and while empty patterns.
Lost wakeups or spurious wakeups cause errors.

2.3 Deadlocks, Ordering, and Debugging

Fundamentals

Deadlocks occur when two or more threads wait on each other forever. In a queue, deadlocks can happen if you lock multiple mutexes in different orders, or if you call blocking functions while holding locks incorrectly. Debugging requires understanding lock ordering and using tools like logs or debuggers to see where threads are blocked.

Deep Dive into the concept

Deadlocks are often caused by circular wait: Thread A holds lock 1 and waits for lock 2, while Thread B holds lock 2 and waits for lock 1. In this project, you likely only use one mutex, so deadlocks are less likely, but you can still deadlock if you call wait or notify incorrectly or if you hold the lock while performing long-running work. The key is to keep lock scope minimal and avoid blocking I/O while holding the lock.

Another issue is priority inversion: a low-priority thread holds a lock while a high-priority thread waits. This can reduce throughput. In Rust’s standard library, there is no priority inheritance, so you should structure the code to keep the critical section as short as possible.

Debugging concurrency bugs is difficult because they are nondeterministic. You can use deterministic tests with loom to explore interleavings. You can also add logging of thread IDs and timestamps around lock acquisition and condition waits to detect stalls. A useful technique is to add timeouts to waits in debug builds, so you can fail fast if something is stuck.

Finally, remember that data races are prevented by Rust’s type system, but logical deadlocks are still possible. The compiler cannot prove that you won’t deadlock. This is why you must design and test for it explicitly.

How this fit on projects

This concept appears in §7 (pitfalls) and §6 (testing). It also connects to Project 8 where lock-free structures avoid deadlocks altogether.

Definitions & key terms

Deadlock: Threads waiting on each other indefinitely.
Starvation: Thread never gets scheduled or notified.
Critical section: Code executed while holding a lock.

Mental model diagram (ASCII)

Thread A: lock L1 -> wait for L2
Thread B: lock L2 -> wait for L1
=> deadlock

How it works (step-by-step)

Identify all locks and their acquisition order.
Ensure a global order for locks.
Keep critical sections short.
Use timeouts and logging in debug builds.

Minimal concrete example

// Avoid holding lock while sleeping
let item = { let mut g = q.lock().unwrap(); g.pop() };
thread::sleep(Duration::from_millis(10));

Common misconceptions

“Rust prevents deadlocks.” It prevents data races, not deadlocks.
“One mutex means no deadlocks.” You can still deadlock with condvars.

Check-your-understanding questions

Why can a thread deadlock while waiting on a condvar?
How does loom help debug concurrency?
What is lock ordering and why does it matter?

Check-your-understanding answers

If the condition is never signaled or a lock is held incorrectly.
It explores possible interleavings deterministically.
It prevents circular wait when multiple locks exist.

Real-world applications

Thread pool work queues.
Producer-consumer pipelines.

Where you’ll apply it

This project: §7.1 pitfalls, §6.2 tests.
Also used in: Project 8: Lock-Free Stack.

References

“Rust Atomics and Locks”.
“The Little Book of Semaphores”.

Key insights

Rust guarantees data-race freedom, but deadlock freedom is still your responsibility.

Summary

Avoid deadlocks by ordering locks, minimizing critical sections, and testing interleavings.

Homework/Exercises to practice the concept

Write a deadlock example with two mutexes.
Fix it by enforcing lock ordering.

Solutions to the homework/exercises

Lock A then B in one thread, B then A in another.
Always lock A before B in both threads.

3. Project Specification

3.1 What You Will Build

A crate bounded_queue that implements a bounded blocking queue with multiple producers/consumers, including a CLI demo and throughput benchmark.

3.2 Functional Requirements

push blocks when the queue is full.
pop blocks when the queue is empty.
Multiple threads can safely call push and pop.
CLI demo produces deterministic metrics.

3.3 Non-Functional Requirements

Performance: Throughput within expected range.
Reliability: No deadlocks in stress tests.

3.4 Example Usage / Output

$ cargo run --example queue_demo
producers=10 consumers=5 capacity=1024
pushed: 1_000_000
popped: 1_000_000
lost: 0
throughput: 4.7M ops/sec
exit code: 0

3.5 Data Formats / Schemas / Protocols

Inner { queue: VecDeque<T>, capacity: usize }.

3.6 Edge Cases

Capacity=0.
High contention with many producers.
Spurious wakeups.

3.7 Real World Outcome

Deterministic queue demo and failure case.

3.7.1 How to Run (Copy/Paste)

cargo run --example queue_demo

3.7.2 Golden Path Demo (Deterministic)

Use fixed thread counts and iterations.
Expect pushed == popped.

3.7.3 CLI Transcript (Success)

$ cargo run --example queue_demo -- --producers 2 --consumers 2 --count 10000
pushed: 10000
popped: 10000
lost: 0
exit code: 0

3.7.4 Failure Demo (Invalid Arg)

$ cargo run --example queue_demo -- --capacity 0
error: capacity must be > 0
exit code: 2

4. Solution Architecture

4.1 High-Level Design

Arc<Queue>
  |
Mutex<Inner> + Condvar (not_empty, not_full)

4.2 Key Components

Component	Responsibility	Key Decisions
`Queue<T>`	Public API	Blocking push/pop
`Inner`	Buffer state	VecDeque + capacity
`Condvar`s	Blocking semantics	notify_one

4.4 Data Structures (No Full Code)

struct Queue<T> {
    inner: Mutex<Inner<T>>,
    not_empty: Condvar,
    not_full: Condvar,
}

4.4 Algorithm Overview

Key Algorithm: Blocking Push

Lock mutex.
While full, wait on not_full.
Push item.
Notify not_empty.

Complexity Analysis:

Time: O(1) amortized
Space: O(capacity)

5. Implementation Guide

5.1 Development Environment Setup

cargo new bounded_queue
cd bounded_queue

5.2 Project Structure

bounded_queue/
├── src/
│   ├── lib.rs
│   └── queue.rs
├── examples/
│   └── queue_demo.rs
└── benches/
    └── queue_bench.rs

5.3 The Core Question You’re Answering

“How can multiple threads safely share a mutable queue without losing data or deadlocking?”

5.4 Concepts You Must Understand First

Arc + Mutex + Condvar.
Bounded buffer problem.
Send/Sync auto traits.

5.5 Questions to Guide Your Design

How will you represent the queue state and capacity?
How will you avoid lost wakeups?
How will you test for deadlocks?

5.6 Thinking Exercise

Sketch the state transitions between empty, partially full, and full.

5.7 The Interview Questions They’ll Ask

“Why use Condvar instead of busy-waiting?”
“What is a lost wakeup?”
“How does Rust prevent data races here?”

5.8 Hints in Layers

Hint 1: Start with a single-threaded queue. Hint 2: Wrap it in Mutex and add Condvar. Hint 3: Add Arc for sharing.

5.9 Books That Will Help

5.10 Implementation Phases

Phase 1: Core Queue (2 days)

Implement VecDeque based queue.

Phase 2: Blocking Semantics (2-3 days)

Add Condvar wait/notify.

Phase 3: Stress Tests (2 days)

Multi-threaded tests with deterministic counts.

5.11 Key Implementation Decisions

6. Testing Strategy

6.1 Test Categories

6.2 Critical Test Cases

No items lost under heavy load.
Producers block when full.
Consumers block when empty.

6.3 Test Data

producers=4
consumers=4
count=10000

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

7.2 Debugging Strategies

Add log lines around wait and notify.
Use loom for deterministic interleavings.

7.3 Performance Traps

Too many wakeups with notify_all.

8. Extensions & Challenges

8.1 Beginner Extensions

Add try_push / try_pop (non-blocking).

8.2 Intermediate Extensions

Add timeouts to push/pop.

8.3 Advanced Extensions

Implement lock-free queue for comparison.

9. Real-World Connections

9.1 Industry Applications

Job queues in servers.
Logging pipelines.

crossbeam-channel.

9.3 Interview Relevance

Explain condvar usage and bounded buffer.

10. Resources

10.1 Essential Reading

TRPL Ch. 16.
Rust Atomics and Locks.

10.2 Video Resources

RustConf talk on concurrency.

10.3 Tools & Documentation

loom for testing.

11. Self-Assessment Checklist

11.1 Understanding

I can explain why Arc<Mutex<T>> is thread-safe.
I can describe lost wakeups.

11.2 Implementation

Queue passes stress tests.
Blocking semantics are correct.

11.3 Growth

I can compare blocking queue vs lock-free queue.

12. Submission / Completion Criteria

Minimum Viable Completion:

Bounded queue with push/pop and blocking.
CLI demo with deterministic output and failure case.

Full Completion:

Stress tests and benchmarks.

Excellence (Going Above & Beyond):

Lock-free queue implementation for comparison.