Project 8: Build a Lock-Free Data Structure (Atomics)

A lock-free stack using compare-and-swap operations, demonstrating safe shared mutability without locks.

Quick Reference

Attribute Value
Primary Language Rust
Alternative Languages C++ (for comparison)
Difficulty Level 5: Master
Time Estimate 3-4 weeks
Knowledge Area Concurrency / Lock-Free Programming
Tooling Rust std::sync::atomic
Prerequisites Projects 1-7, concurrency knowledge

What You Will Build

A lock-free stack using compare-and-swap operations, demonstrating safe shared mutability without locks.

Why It Matters

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

Core Challenges

  • Using atomic operations → maps to AtomicPtr, compare_exchange
  • Handling ABA problem → maps to why raw pointers need careful design
  • Choosing memory ordering → maps to Acquire, Release, SeqCst semantics
  • Preventing memory leaks → maps to correct deallocation in concurrent contexts

Key Concepts

  • Atomics: “Rust Atomics and Locks” by Mara Bos (definitive guide)
  • Lock-Free Data Structures: “The Art of Multiprocessor Programming” by Herlihy & Shavit
  • Memory Ordering: C++ memory model documentation (applies to Rust)
  • ABA Problem: “Concurrency” chapter in any systems textbook

Real-World Outcome

Deliver a working demo with observable output that proves the feature is correct.

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: RUST_BORROW_CHECKER_LIFETIME_PHILOSOPHY.md
  • “Rust Atomics and Locks” by Mara Bos