Implement a Wait-Free Counter

Bounded Steps Per Operation

Wait-free guarantees every thread completes its operation in a bounded number of steps regardless of others. Lock-free only promises system-wide progress. Wait-free stacks and counters exist but often cost more atomic operations or memory than practical lock-free versions.

Examples and Tradeoffs

Wait-free snapshot and some counter implementations use helping: slow threads assist others to finish partial operations. Most production queues stop at lock-free.

c
Loading…

Real-time literature cares about wait-free for priority inversion bounds
Helping schemes complicate proofs and implementation
Often measure tail latency (p99) to see if wait-free helps
Start with correct lock-free before chasing wait-free

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 study a wait-free counter or stack algorithm and implement a simplified version. This exercise requires explaining the progress guarantee difference with a concurrent test.

Implement a wait-free counter and compare it to lock-free and mutex-based approaches.

Requirements:

Implement wait-free counter using atomic fetch_add
Implement lock-free counter using CAS retry loop
Implement mutex-based counter for comparison
Run all three with multiple threads and measure latency
Show that wait-free has bounded latency per operation
Calculate percentiles (p50, p99, p999) for each approach
Print results comparing throughput and tail latency
Explain why fetch_add is wait-free on x86

Test:

Show wait-free counter increments
Show lock-free counter increments
Show comparison results
Show latency percentiles

Bounded Steps Per Operation

Examples and Tradeoffs

Wait-free snapshot and some counter implementations use helping: slow threads assist others to finish partial operations. Most production queues stop at lock-free.

c
Loading…

Real-time literature cares about wait-free for priority inversion bounds
Helping schemes complicate proofs and implementation
Often measure tail latency (p99) to see if wait-free helps
Start with correct lock-free before chasing wait-free

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 study a wait-free counter or stack algorithm and implement a simplified version. This exercise requires explaining the progress guarantee difference with a concurrent test.

Implement a wait-free counter and compare it to lock-free and mutex-based approaches.

Requirements:

Implement wait-free counter using atomic fetch_add
Implement lock-free counter using CAS retry loop
Implement mutex-based counter for comparison
Run all three with multiple threads and measure latency
Show that wait-free has bounded latency per operation
Calculate percentiles (p50, p99, p999) for each approach
Print results comparing throughput and tail latency
Explain why fetch_add is wait-free on x86

Test:

Show wait-free counter increments
Show lock-free counter increments
Show comparison results
Show latency percentiles

Topic Overview

Bounded Steps Per Operation

Examples and Tradeoffs

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source

Implement a Wait-Free Counter

Topic Overview

Bounded Steps Per Operation

Examples and Tradeoffs

Working Through the Exercise

Why for this exercise

Implementation Task

Progressive Hints

Resources

Open Source