Implement a Wait-Free Counter

Topic Overview

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.

cCopy
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.

Your Task

Lock-free means that some thread always makes progress. Wait-free means that every thread finishes each operation within a bounded number of its own steps, however it is scheduled. A CAS-loop counter is only lock-free: an unlucky thread can lose every CAS for ever. fetch_add is wait-free, and so is a sharded counter (one slot per thread, summed on read). Run all three under the same adversarial schedule and measure the steps each operation needs.

Input

cCopy
Loading…

Model

The schedule is a list of turns. Each turn, the named thread performs one step of its current increment. A thread that has finished its K increments ignores its turns.

• fetch_add: one step, counter += 1. Done.
• CAS loop: step A loads the counter. Step B runs CAS(counter, loaded, loaded + 1): on success the increment is done, on failure it counts as a failed CAS and the next step is a new load.
• sharded: one step, slot[thread] += 1. Done. The final counter is the sum of all slots.

An operation's length is the number of that thread's own steps from its start to its completion. An operation still running at the end of the schedule counts as (still running).

Output

cCopy
Loading…

Print the three versions in the order fetch_add, CAS loop, sharded. The wait-free line uses the longest operation (at least 1). Errors: ops: 1..1000, schedule: unknown thread NAME, and run: no threads.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Replay the identical schedule for each algorithm, so the only difference is the algorithm.
2. Measure operation length in the thread's own steps. That is how wait-freedom is defined, and it is independent of what other threads do.

Hidden tests cover a schedule that starves one CAS thread completely, three threads, a victim that only finishes once the others are done, schedules longer than the work needed, and unknown thread names.