Loading page…
Master the fundamental concepts of lock-free & wait-free programming through this focused micro-challenge.
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 worksA 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.
Read head, link new node to head, CAS head from observed value to new node. On failure, retry with updated head.
cLoading…
compare_exchange_weak may spuriously fail; loops must retryKeep 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 implement a lock-free stack with CAS push and pop. This exercise requires correct retry loops and a concurrent test with multiple threads.
The Treiber stack is the classic lock-free stack: push and pop read top, prepare the change, and publish it with one compare-and-swap. If another thread changed top in the meantime, the CAS fails and the operation retries. Simulate it at the level of individual steps, so you can choose the exact interleaving and watch CAS failures happen.
cLoading…
| Operation | Step 0 | Step 1 | Step 2 |
|---|---|---|---|
| push V | t = top (on the first attempt, allocate the next node id #1, #2, … holding V) | node.next = t | CAS(top, t, node): done, or retry from step 0 |
| pop | t = top; if NULL the stack is empty and the pop is done | next = t.next | CAS(top, t, next): done (returns t's value), or retry from step 0 |
Popped nodes are never freed (there is no reclamation in this task). A thread with no operations left prints NAME: finished if it is scheduled, and the rest of that schedule entry is skipped.
cLoading…
finish prints the final stack and, for each thread in definition order, its retries and popped values in order (EMPTY for a pop that found the stack empty). Errors: thread NAME: bad operation: TEXT, thread: at most 4 threads, and schedule: unknown thread NAME.
Input:
cLoading…
Output:
cLoading…
t it read, the node being pushed, the next it read) between steps. That state is exactly what goes stale when another thread wins a race.top, and make it compare against the value read in step 0.Hidden tests cover several threads racing pushes, pops racing each other for the same node, popping an empty stack, a thread that keeps losing (many retries), schedules that name finished or unknown threads, and bad operations.