LC

Implement Lock-Free Stack Using Compare-And-Swap

hard2/8

Understand C11 Memory Ordering: relaxed, acquire, release, seq_cst Fix ABA Problem Using Stamped Reference or Hazard Pointers

Language

Compiler

2.0s Limit 256MB

Implementation

Implement lock-free stack using atomic compare-and-swap.

Requirements:

Define Node structure with data and next pointer
Define Stack structure with atomic head pointer
Implement stack_push() using CAS loop
Implement stack_pop() using CAS loop
Handle empty stack condition
Use proper memory ordering (acquire/release)
Test with multiple threads (4 threads)
Compare with mutex-based implementation
Demonstrate lock-free property (no blocking)
Measure performance improvement (2-5x speedup)

Why This Matters

The CAS-loop stack you're building here is the same core primitive behind java.util.concurrent's ConcurrentLinkedDeque and the free-list allocators inside jemalloc, chosen specifically because it lets threads make progress without ever blocking on a futex. Herlihy and Shavit's 'The Art of Multiprocessor Programming' uses this exact stack as its opening example precisely because it's simple enough to implement but exposes every classic lock-free pitfall, including the ABA problem covered next in this track.

Hints

0 / 3 revealed

Validation Suite

main.c

Workspace 1.0