Implement Lock-Free Stack Using Compare-And-Swap

Compare-And-Swap Stacks

A lock-free stack pushes and pops via compare_exchange_weak on the head pointer. Michael and Scott's queue extends the idea to two ends. Windows' InterlockedPushEntrySList, Java's ConcurrentLinkedQueue, and Rust crossbeam all trace back to these CAS loops.

Push and Pop Loops

Read head, link new node to head, CAS head from observed value to new node. On failure, retry with updated head.

c
Loading…

ABA problem appears if nodes are freed and reallocated; defer reclamation
compare_exchange_weak may spuriously fail; loops must retry
Helps when contention is moderate; mutexes win under extreme write contention
Always align head pointer for the platform word size

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a lock-free stack with CAS push and pop. This exercise requires correct retry loops and a concurrent test with multiple threads.

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)

Compare-And-Swap Stacks

Push and Pop Loops

Read head, link new node to head, CAS head from observed value to new node. On failure, retry with updated head.

c
Loading…

ABA problem appears if nodes are freed and reallocated; defer reclamation
compare_exchange_weak may spuriously fail; loops must retry
Helps when contention is moderate; mutexes win under extreme write contention
Always align head pointer for the platform word size

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement a lock-free stack with CAS push and pop. This exercise requires correct retry loops and a concurrent test with multiple threads.

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)

Topic Overview

Compare-And-Swap Stacks

Push and Pop Loops

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Implement Lock-Free Stack Using Compare-And-Swap

Topic Overview

Compare-And-Swap Stacks

Push and Pop Loops

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source