Loading page…
Master the fundamental concepts of lock-free & wait-free programming through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksLock-free structures shine under moderate contention and small critical sections. Mutexes plus a simple queue often win when critical sections are large, when you need condition variables, or when every core hammers the same CAS cache line.
Measure throughput and tail latency, not ideology. Consider memory reclamation cost, programmer complexity, and priority inversion requirements.
cLoading…
perf stat -e cache-misses on CAS loops shows line bouncingKeep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will benchmark lock-free queue vs mutex-backed queue under increasing thread counts. This exercise requires plotting where each approach wins and explaining the crossover.
How do a CAS loop and a mutex compare when many threads hammer one counter? And what goes wrong with no synchronisation at all? Real benchmarks are noisy, so use a deterministic step model. Threads take turns executing one step each, and you count total time, wasted steps (failed CASes, lock spins) and the final counter value.
cLoading…
Every tick, each thread that still has work takes exactly one step, in thread order (0, 1, 2, …), and all threads see each other's effects immediately. Before each increment, a thread spends W ticks on private work. Then:
| Version | Steps per increment |
|---|---|
| plain | load the counter; store load + 1 |
| CAS | load the counter; CAS(counter, loaded, loaded + 1). A failure is a wasted step, and the increment restarts at the load |
| mutex | lock: take it if it is free, otherwise spin (each spin is a wasted step); load; store load + 1; unlock |
The run ends when every thread has done K increments. Time = the number of ticks.
cLoading…
Throughput = N * K * 100 / ticks, rounded half up to 1 decimal with integer arithmetic. (LOST UPDATES) is shown when the counter is not N * K. Errors: ops: 1..100000, work: 0..1000, and threads N: 1..16.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover a single thread (no contention, the mutex just costs extra steps), many threads with no private work, private work that thins out the contention, one increment per thread, and invalid settings.