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 worksABA bites when a CAS compares only the pointer value, not the generation. Thread A reads head H, stalls, other threads pop H and push a new node that reuses the same address H. A's CAS succeeds even though the stack changed underneath.
Tagged pointers (version in high bits), hazard pointers, epoch reclamation, or never freeing nodes until quiescence. Windows uses a per-stack sequence counter in SLIST_HEADER.
cLoading…
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.
You will demonstrate ABA on a naive lock-free stack and fix it with tagged pointers or a hazard-pointer scheme. This exercise asks you to show a failing scenario and a corrected one.
The ABA problem: thread X reads top = A and A.next = B, then stalls. Meanwhile other threads pop A and B, free them, and push a new value whose node reuses A's memory. top is A again, so X's CAS(top, A, B) succeeds, and it installs B, a freed node. Reproduce this on a Treiber stack with node recycling, detect the corruption, then fix it with a tagged (stamped) pointer: every successful CAS bumps a counter stored next to top, and CAS compares both.
cLoading…
top; (1) node.next = top_read; (2) CAS.top (NULL means empty, done); (1) next = t.next; (2) CAS.(reuses #N)), otherwise a new one (#1, #2, …). A successful pop frees its node at once.top and the tag are unchanged. Every successful CAS increments the tag (it starts at 0).(freed!) and stopping at a cycle), and checks it. The number of nodes and the sum of values must equal pushes minus pops, and no reachable node may be freed. Then it prints each thread's retries and popped values.cLoading…
A tag failure prints CAS(top, P tag T -> Q) failed, tag is U, retry when the pointer matched but the tag did not. Other messages are as in the Treiber stack task.
Input:
cLoading…
Output:
cLoading…
Hidden tests cover the same ABA schedule with and without tags, node reuse in a different order, where the stale CAS fails anyway, a longer interleaving with three threads, and pops of an empty stack.