Project 15: Lock-Free SPSC Queue

A single-producer single-consumer lock-free queue in shared memory using only atomic operations.

Quick Reference

Attribute Value
Primary Language C
Alternative Languages Rust, C++
Difficulty Level 5 (Master)
Time Estimate See main guide
Knowledge Area Lock-Free Programming, Memory Models
Tooling See main guide
Prerequisites See main guide

What You Will Build

A single-producer single-consumer lock-free queue in shared memory using only atomic operations.

Why It Matters

This project builds core skills that appear repeatedly in real-world systems and tooling.

Core Challenges

  • Memory barriers → __atomic_thread_fence, seq_cst vs relaxed
  • False sharing → Cache line padding
  • ABA problem → Sequence numbers

Key Concepts

  • Map the project to core concepts before you code.

Real-World Outcome

$ ./lockfree_bench --iterations=100M

Lock-Free SPSC Queue Benchmark
Operations: 100 million

Lock-free queue: 45M ops/sec
Mutex-based queue: 8M ops/sec
Semaphore-based: 6M ops/sec

Speedup: 5.6x over mutex
Latency (p99): 22ns vs 180ns

Implementation Guide

  1. Reproduce the simplest happy-path scenario.
  2. Build the smallest working version of the core feature.
  3. Add input validation and error handling.
  4. Add instrumentation/logging to confirm behavior.
  5. Refactor into clean modules with tests.

Milestones

  • Milestone 1: Minimal working program that runs end-to-end.
  • Milestone 2: Correct outputs for typical inputs.
  • Milestone 3: Robust handling of edge cases.
  • Milestone 4: Clean structure and documented usage.

Validation Checklist

  • Output matches the real-world outcome example
  • Handles invalid inputs safely
  • Provides clear errors and exit codes
  • Repeatable results across runs

References

  • Main guide: UNIX_IPC_STEVENS_VOL2_MASTERY.md
  • Primary references are listed in the main guide