Concurrent Data Structures

Why Concurrent Data Structures Matters

Two threads pop the same shared stack. Both read its top value 10 and successor 20. If both blindly write the successor into Head and return 10, one value has been removed twice. A concurrent structure must define which update wins, how a loser retries, and when an unlinked node may finally be destroyed.

Concurrent data structures implement shared operations such as push/pop and enqueue/dequeue while overlapping callers observe a valid abstract stack or queue. The challenge has three distinct parts: logical correctness, progress under contention, and memory lifetime. Compare-and-swap helps with the first two; it does not by itself make a pointer safe to dereference.

This lesson covers CAS, a Treiber-style lock-free stack, the Michael–Scott queue, ABA, and hazard pointers. It follows one paused pop through a competing removal, a failed CAS and a protected reclamation scan; then follows an enqueue that takes effect before its caller returns while a dequeue helps its lagging Tail.

The programs deliberately implement a sequentially consistent step simulator in Python, C++, and Java. All three use node IDs and explicitly scheduled actions, with identical output. They are runnable models of the protocols, not production lock-free containers: there are no actual threads, atomic library objects, hardware fences, or physical frees. Stack reclamation marks nodes dead and checks later dereferences; queue nodes are retained throughout. These choices let us explain interleavings without presenting a partially specified low-level memory-management implementation.

Core Concepts and Terminology

A stack is LIFO: pushing 20 then 10 gives pops 10 then 20. A queue is FIFO: enqueuing 7 then 9 gives dequeues 7 then 9. For concurrency, these rules apply to a suitable ordering of overlapping calls, with each call appearing once.

Linearizability requires a point between an operation's invocation and response at which it takes effect. If $\operatorname{inv}(o)$ and $\operatorname{resp}(o)$ are its event positions, a proposed point satisfies

$$\operatorname{inv}(o)\le\operatorname{LP}(o)\le\operatorname{resp}(o).$$

The resulting sequential history must obey the object's specification and preserve real-time precedence: a call that returns before another begins must come first. Overlapping calls can linearize in a different order from their return times. An enqueue may publish its node, pause, and return after another thread has already dequeued that item.

Compare-and-swap (CAS) atomically compares one location with an expected value and writes a desired value only if they match:

$$\operatorname{CAS}(x,e,d)=\begin{cases}\text{success and }x\gets d,&x=e,\\\text{failure and }x\text{ unchanged},&x\ne e.\end{cases}$$

Our modeled CAS is strong: it has no spurious failures and takes expected by value. Real APIs can update an expected argument on failure or provide weak CAS that may fail spuriously; translate retry logic using that API's exact contract. CAS changes one selected location, not a whole multi-step algorithm or every field of a node.

Lock-free is a system progress guarantee: under the algorithm's assumptions, an infinite execution in which threads keep taking steps cannot have all operations remain pending forever. Individual operations may starve. Wait-free additionally bounds an individual operation's own steps, independently of competitors' delays. A mutex can provide simple linearizable behavior but a stopped lock owner can block its contenders. Lock-free does not imply fairness, bounded latency, or that allocation and reclamation are automatically nonblocking.

Retire means a node is unlinked and queued for later reclamation. Reclaim means its lifetime may end or its storage may become reusable. A hazard slot publishes a reader's candidate node; the reader must re-read the shared source and validate it before dereferencing that candidate. Publishing after a node has already been reclaimed cannot retroactively make an earlier dereference safe. Our simulator can publish an already-dead ID tentatively, but validation then fails before any node fields are accessed.

ABA occurs when a compared value changes from A to something else and back to A, making a stale equality check succeed. Reuse of a node address is one cause; reinsertion of the same live node is another. A pointer/version pair can detect intervening changes only when compared atomically and when the tag has not wrapped. A version does not keep the pointed-to object alive. Proper hazard reclamation blocks reuse of a protected old node, but does not alone forbid all logical ABA patterns.

In the following timeline, event numbers describe SC transition order, not elapsed CPU time. The meaningful metrics here are correctness, retry work, operation intervals and progress; bulk-parallel work/span speedup formulas do not explain a contender's latency by themselves.

How Concurrent Data Structures Works, Step by Step

The model has a stack arena and a separate queue arena; the same numeric ID in them refers to different nodes. ID 0 is null. New pushes/enqueues always receive fresh increasing IDs, and removed nodes are never reinserted. Stack nodes can be marked dead after a hazard scan; queue nodes are never reclaimed. The separate address-reuse example illustrates ABA without dereferencing a dead node.

Treiber-style push. Allocate and initialize a private node. Load Head into a local expected value, set the private node's next link to that expected Head, then CAS Head from expected to the new node. A successful CAS is the push's linearization point. On failure, reload Head and rebuild the private next link before retrying. The private node is not reachable until its successful publication.

Hazard-protected pop. Load a Head candidate. If it is null, return EMPTY with that load as the linearization point. Otherwise publish the candidate in this thread's hazard slot, then re-read Head. If it differs, clear the slot and retry before dereferencing. If it matches, read the protected node's immutable next link and copy its value. Attempt CAS Head from the candidate to its saved successor. Success linearizes the pop; retire the removed node, clear protection, and return the copied value. Failure clears protection and restarts from a fresh Head. There is one hazard slot per thread here because the stack pop dereferences only its protected candidate; it never dereferences the saved successor in the same attempt.

In a real implementation, retirement, clearing and local completion are separate actions. The simulator combines their bookkeeping with a successful pop transition; its scans occur at explicit scheduled steps. The candidate remains protected through its dereferences, and no node is reclaimed before being retired. This model checks the stated safety protocol under SC, not every machine-level implementation detail. A scan is one model transition, so interleavings within a native multi-slot hazard scan are outside this simulator.

Reclamation scan. Snapshot the published hazard IDs. For each retired stack node, keep it if protected; otherwise mark it dead and record its ID as reclaimed. A stopped reader may delay reclaiming its protected node without preventing other pushes or pops. Clear hazards when the attempt finishes or restarts. A scan compares IDs and examines retirement metadata; it must not dereference a tentatively protected, possibly already-dead candidate. Physical arena metadata remains allocated so the simulator can detect an invalid dereference instead of executing one.

Michael–Scott enqueue. Start with one dummy node and Head=Tail=dummy. Prepare a fresh node with null next. Read Tail, read that node's next, and validate that Tail still matches the saved Tail. If its next is non-null, another enqueue has already linked a node but Tail lags: try to advance Tail to that successor and retry. If next is null, CAS that next link from null to the new node. The successful next-link CAS is the enqueue's linearization point. Finally try to advance Tail; even if that last CAS fails, the enqueue has already succeeded. Another thread may have helped or progressed further.

Michael–Scott dequeue. Read Head, Tail, and Head.next, then validate Head. If Head changed, retry. If saved Head equals saved Tail and saved next is null, the queue was empty at the validated next-pointer observation; return EMPTY. If Head equals Tail but next is non-null, Tail is behind: help it advance and retry. Otherwise copy the successor's value before CAS, then CAS Head to that successor. Success is the dequeue's linearization point and turns the successor into the new dummy; failure retries. The old dummy is not the value returned. Our queue retains all nodes, so these saved-node dereferences remain valid; adding queue reclamation requires its own validated protection protocol for every dereferenced pointer, not simply copying the stack's one-slot pattern.

A subtle empty case matters: a new enqueue can link after a dequeue reads null next but before its validation/return. If Head still validates, the empty dequeue may linearize at its earlier null-next read. The program records that earlier event in lp rather than falsely claiming the queue is empty at the later return event. A test explicitly exercises this interleaving.

The flowchart below describes the protected stack-pop loop. Queue helping and publication follow the procedures above. Every T command advances just one modeled transition; F repeatedly advances the selected operation while other threads stay paused.

flowchart TD
    A["Load Head candidate"] --> B{"Candidate is null?"}
    B -->|Yes| C["Return EMPTY; LP is this load"]
    B -->|No| D["Publish candidate in hazard slot"]
    D --> E{"Head still equals candidate?"}
    E -->|No| F["Clear hazard and retry"]
    F --> A
    E -->|Yes| G["Read protected next link and copy value"]
    G --> H["CAS Head from candidate to saved next"]
    H --> I{"CAS succeeded?"}
    I -->|No| F
    I -->|Yes| J["Pop LP; retire node and clear hazard"]
    J --> K["Return copied value; scan later"]

Worked Example with a Full Trace

The sample uses two logical threads, numbered 0 and 1. It begins by pushing 20 into stack node 1 and 10 into node 2. At event 8, the top-to-bottom stack is [10,20], Head=2, and both hazard slots are zero. The queue has its own dummy node 1 and is still empty.

Protected pop race, events 9–27. Thread 0 begins a pop, loads candidate 2 at event 10, publishes hazard 2 at 11, validates Head at 12, and reads next=1/value=10 at 13. It pauses immediately before its CAS. Thread 1 begins another pop at 14, protects the same node, and successfully CASes Head from 2 to 1 at 19. That pop returns 10, retires node 2, and clears thread 1's hazard. Thread 0 still holds hazard 2.

The scan at event 20 therefore releases nothing: node 2 is retired but remains alive. At 21, thread 0's CAS expecting Head 2 fails because actual Head is 1. It neither removes another node nor returns its stale cached value 10. It clears its hazard, reloads/protects node 1, reads value 20 and null successor, and successfully CASes Head to null at 26. It returns 20 and retires node 1. The scan at 27 releases model nodes 1 and 2; neither is now protected or reachable. An additional pop returns EMPTY at 29. The two overlapping pops have legal linearization order: thread 1 at 19, then thread 0 at 26.

Queue helping, events 30–47. Thread 0 begins enqueueing 7 in fresh queue node 2 at 30. At 34 it successfully links dummy.next from null to node 2. This is the enqueue LP, so logical Q is already [7] even though Tail still points to dummy 1. Thread 0 pauses before its final Tail update.

Thread 1 begins dequeue at 35. It reads Head=Tail=1 and next=2, so this is a lagging Tail, not an empty queue. It helps Tail from 1 to 2 at 40, retries the snapshot, reads value 7, and successfully CASes Head from 1 to 2 at 46. It returns 7 and node 2 becomes the new dummy. Thread 0 resumes at 47; its final Tail CAS expecting 1 fails because Tail is already 2. It still returns OK with LP=34. A dequeue returning before that enqueue caller returns is legal because their call intervals overlap and publication already occurred.

Ordinary queue operations, events 48–65. Enqueue 9 links fresh node 3 at 52, its LP, advances Tail at 53, and returns OK. A dequeue advances Head from 2 to 3 and returns 9 at 60. The final dequeue observes null next at event 64 and validates/returns EMPTY at 65, recording LP=64. Final Q is empty, with Head=Tail=3; node 3 is the dummy. Queue nodes 1–3 remain allocated in this model, including obsolete dummies.

There are 12 CAS attempts and 10 successes. The failures are thread 0's stale stack-pop CAS and the original enqueuer's already-helped Tail update. A failed CAS means no write by that attempt; it does not mean that the entire object stopped making progress. The full log below includes all 65 events, every intermediate Head/Tail/hazard/retirement state, and operation return/LP events.

Separate ABA address model. A paused thread saves Head address 1 and successor 2 from chain 1→2→3. Other operations remove 1, remove 2, and reuse address 1 for a fresh node pointing to 3. Address-only CAS expecting 1 succeeds and installs stale successor 2, which now denotes freed storage. If every Head change also increments an atomically compared stamp, the saved pair $(1,0)$ differs from current $(1,3)$ and the stale pair-CAS fails. No actual invalid pointer dereference occurs in this numeric demonstration.

Implementation in Python, C++, and Java

Every panel contains the full simulator: a fresh-node stack, protected-pop state machine, hazard scan, Michael–Scott enqueue/dequeue state machines, and a separate numeric ABA/version check. They use identical commands and print identical events. Python requires 3.9 or later; C++ uses C++17; Java uses Java 8 or later and should be saved as Main.java. Run python3 main.py; compile/run C++ with g++ -std=c++17 -O2 main.cpp -o concurrent-model then ./concurrent-model; compile/run Java with javac Main.java then java Main.

simulate(workers,commands) accepts 1–4 modeled threads and at most 256 commands. A command has kind, thread ID, and an integer value defaulting to zero. P starts a stack push, O starts a stack pop, E starts an enqueue, and D starts a dequeue. T advances one transition; F finishes the selected pending operation while others stay paused; R scans retired stack nodes. All command thread IDs must be valid and all value fields must lie in $[-100,100]$, including unused fields. Only push/enqueue use the value as payload.

Validation checks WORKERS, then script SIZE, then each command's COMMAND, THREAD, and VALUE fields before creating the machine. During execution, starting a new operation on a thread with a pending call raises BUSY; stepping/finishing a thread with no pending call raises IDLE. Scripts may intentionally end with pending operations for inspection. Python rejects booleans and other non-integer runtime types in numeric fields. The command containers and command records are left unchanged.

An Operation stores private expected pointers, stage pc, cached value, invocation/return events, and LP. Node ID 0 is null; stack and queue IDs belong to separate arenas. A retired stack node's alive marker becomes false at reclamation, but its metadata remains available for checking. The model's guarded stack dereference rejects dead IDs. Queue nodes are retained and their lifetime is not handled by the stack's hazard scanner. The independent ABA demo operates only on integers; it never constructs or dereferences an invalid native pointer.

Modeled pointer loads, hazard publication/validation, CAS actions, and small local bookkeeping are serialized into SC transitions. This is deliberately a model of atomic behavior, not the use of native atomics: replacing the single-thread scheduler with ordinary threads would introduce data races. Production C++ needs the appropriate atomic pointer/link/hazard fields, publication ordering and a proven reclamation protocol; Java reference lifetime, Python runtime behavior, and language memory models must be treated on their own terms. The code is useful for inspecting histories and correctness arguments, not claiming measured throughput or production lock-free behavior.

Verification: 2,113 scripts were checked per language, with 2,102 accepted and 11 rejected. Accepted scripts contain 17,382 modeled operations and 134,019 logged events, including intentionally pending prefixes. Bounded two-operation exploration visits 1,092 normalized structural/control states and 60 terminal states; timestamps are normalized for state deduplication, so this is not an enumeration of every timed history. Seeded multi-operation schedules use two, three, and four threads. Independent checks compare LP-ordered histories with sequential stack/deque specifications, enforce invocation/response bounds, and check reachability, acyclicity, retirement/hazard eligibility, safe protected dereferences, CAS counts, and unchanged commands. Across exploration/generation/replay, 125,916 invariant checks pass. Full formatted traces agree across languages and sample stdout matches byte for byte. Eight extra Python cases check invalid runtime types. C++ passes address/undefined-behavior sanitizers; Java compiles with all lint warnings enabled. These tests establish properties of this SC node-ID model, not weak-memory correctness or every unbounded execution.

from dataclasses import dataclass

@dataclass
class Command:
    kind: str
    tid: int
    value: int = 0

@dataclass
class Node:
    value: int = 0
    next: int = 0
    alive: bool = True

@dataclass
class Operation:
    kind: str
    tid: int
    value: int
    node: int
    invoked: int
    pc: int = 0
    a: int = 0
    b: int = 0
    c: int = 0
    read_tick: int = 0
    lp: int = 0
    returned: int = 0
    result: str = "PENDING"

def numbers(a: list[int]) -> str:
    return "[" + ",".join(map(str, a)) + "]"

def cas_text(label: str, expected: int, desired: int, ok: bool) -> str:
    return f"{label} expect={expected} set={desired} ok={int(ok)}"

class Machine:
    def __init__(self, workers: int):
        self.workers = workers
        self.stack = [Node(alive=False)]
        self.queue = [Node(alive=False), Node()]  # One retained dummy.
        self.head = 0
        self.qhead = self.qtail = 1
        self.hp = [0] * workers
        self.retired: list[int] = []
        self.freed: list[int] = []
        self.active = [-1] * workers
        self.operations: list[Operation] = []
        self.log: list[str] = []
        self.clock = self.attempts = self.wins = 0

    def sn(self, index: int) -> Node:
        if not 0 < index < len(self.stack) or not self.stack[index].alive:
            raise RuntimeError("BAD_STACK_DEREFERENCE")
        return self.stack[index]

    def qn(self, index: int) -> Node:
        if not 0 < index < len(self.queue):
            raise RuntimeError("BAD_QUEUE_DEREFERENCE")
        return self.queue[index]

    def chain(self, queue: bool = False) -> list[int]:
        out: list[int] = []
        current = self.qn(self.qhead).next if queue else self.head
        seen: set[int] = set()
        while current:
            if current in seen: raise RuntimeError("CYCLE")
            seen.add(current)
            node = self.qn(current) if queue else self.sn(current)
            out.append(node.value)
            current = node.next
        return out

    def record(self, note: str) -> None:
        state = (f"S={numbers(self.chain())} head={self.head} hp={numbers(self.hp)} "
                 f"R={numbers(sorted(self.retired))} F={numbers(sorted(self.freed))} "
                 f"Q={numbers(self.chain(True))} H={self.qhead} T={self.qtail}")
        self.log.append(f"{self.clock:03d} {note} | {state}")

    def pending(self, tid: int) -> bool:
        return self.active[tid] >= 0 and self.operations[self.active[tid]].result == "PENDING"

    def begin(self, kind: str, tid: int, value: int = 0) -> None:
        if self.pending(tid): raise ValueError("BUSY")
        self.clock += 1
        node = 0
        if kind in ("P", "E"):
            arena = self.stack if kind == "P" else self.queue
            node = len(arena); arena.append(Node(value))
        op = Operation(kind, tid, value, node, self.clock)
        self.active[tid] = len(self.operations); self.operations.append(op)
        self.record(f"begin {kind} t={tid} value={value} node={node}")

    def cas(self, where: str, target: int, expected: int, desired: int) -> bool:
        self.attempts += 1
        current = (self.head if where == "S" else self.qhead if where == "H"
                   else self.qtail if where == "T" else self.qn(target).next)
        ok = current == expected
        if ok:
            self.wins += 1
            if where == "S": self.head = desired
            elif where == "H": self.qhead = desired
            elif where == "T": self.qtail = desired
            else: self.qn(target).next = desired
        return ok

    def complete(self, op: Operation, result: str, lp: int = 0) -> None:
        op.result = result; op.returned = self.clock
        if lp: op.lp = lp

    def step(self, tid: int) -> None:
        if not self.pending(tid): raise ValueError("IDLE")
        self.clock += 1
        o = self.operations[self.active[tid]]
        note = ""
        if o.kind == "P":
            if o.pc == 0:
                o.a = self.head; o.pc = 1; note = f"P.read head={o.a}"
            elif o.pc == 1:
                self.sn(o.node).next = o.a; o.pc = 2
                note = f"P.private-next={o.a}"
            else:
                ok = self.cas("S", 0, o.a, o.node)
                note = cas_text("P.cas-head", o.a, o.node, ok)
                if ok: self.complete(o, "OK", self.clock)
                else: o.pc = 0
        elif o.kind == "O":
            if o.pc == 0:
                o.a = self.head; note = f"O.read head={o.a}"
                if not o.a: self.complete(o, "EMPTY", self.clock)
                else: o.pc = 1
            elif o.pc == 1:
                self.hp[tid] = o.a; o.pc = 2; note = f"O.publish hp={o.a}"
            elif o.pc == 2:
                valid = self.head == o.a
                note = f"O.validate ok={int(valid)}"
                if valid: o.pc = 3
                else: self.hp[tid] = 0; o.pc = 0
            elif o.pc == 3:
                if self.hp[tid] != o.a: raise RuntimeError("UNPROTECTED")
                node = self.sn(o.a); o.b = node.next; o.value = node.value; o.pc = 4
                note = f"O.read-next={o.b} value={o.value}"
            else:
                ok = self.cas("S", 0, o.a, o.b)
                note = cas_text("O.cas-head", o.a, o.b, ok)
                self.hp[tid] = 0
                if ok:
                    self.retired.append(o.a); self.complete(o, str(o.value), self.clock)
                else: o.pc = 0
        elif o.kind == "E":
            if o.pc == 0:
                o.a = self.qtail; o.pc = 1; note = f"E.read-tail={o.a}"
            elif o.pc == 1:
                o.b = self.qn(o.a).next; o.pc = 2; note = f"E.read-next={o.b}"
            elif o.pc == 2:
                valid = self.qtail == o.a; note = f"E.validate ok={int(valid)}"
                o.pc = (3 if o.b else 4) if valid else 0
            elif o.pc == 3:
                ok = self.cas("T", 0, o.a, o.b); o.pc = 0
                note = cas_text("E.help-tail", o.a, o.b, ok)
            elif o.pc == 4:
                ok = self.cas("N", o.a, 0, o.node)
                note = cas_text("E.link-next", 0, o.node, ok)
                if ok: o.lp = self.clock; o.pc = 5
                else: o.pc = 0
            else:
                ok = self.cas("T", 0, o.a, o.node)
                note = cas_text("E.advance-tail", o.a, o.node, ok)
                self.complete(o, "OK")
        else:  # Michael-Scott dequeue; queue nodes are never reclaimed here.
            if o.pc == 0:
                o.a = self.qhead; o.pc = 1; note = f"D.read-head={o.a}"
            elif o.pc == 1:
                o.b = self.qtail; o.pc = 2; note = f"D.read-tail={o.b}"
            elif o.pc == 2:
                o.c = self.qn(o.a).next; o.read_tick = self.clock; o.pc = 3
                note = f"D.read-next={o.c}"
            elif o.pc == 3:
                valid = self.qhead == o.a; note = f"D.validate ok={int(valid)}"
                if not valid: o.pc = 0
                elif o.a == o.b:
                    if not o.c: self.complete(o, "EMPTY", o.read_tick)
                    else: o.pc = 4
                else: o.pc = 5
            elif o.pc == 4:
                ok = self.cas("T", 0, o.b, o.c); o.pc = 0
                note = cas_text("D.help-tail", o.b, o.c, ok)
            elif o.pc == 5:
                o.value = self.qn(o.c).value; o.pc = 6; note = f"D.read-value={o.value}"
            else:
                ok = self.cas("H", 0, o.a, o.c)
                note = cas_text("D.cas-head", o.a, o.c, ok)
                if ok: self.complete(o, str(o.value), self.clock)
                else: o.pc = 0
        if o.result != "PENDING": note += f" return={o.result} lp={o.lp}"
        self.record(f"t={tid} " + note)

    def finish(self, tid: int) -> None:
        if not self.pending(tid): raise ValueError("IDLE")
        while self.pending(tid): self.step(tid)

    def scan(self) -> None:
        self.clock += 1
        protected = set(self.hp)
        keep: list[int] = []; released: list[int] = []
        for node in self.retired:
            if node in protected: keep.append(node)
            else:
                self.sn(node).alive = False; self.freed.append(node); released.append(node)
        self.retired = keep
        self.record("scan released=" + numbers(sorted(released)))

def simulate(workers: int, commands: list[Command]) -> Machine:
    if type(workers) is not int or not 1 <= workers <= 4: raise ValueError("WORKERS")
    if len(commands) > 256: raise ValueError("SIZE")
    for c in commands:
        if c.kind not in ("P", "O", "E", "D", "T", "F", "R"): raise ValueError("COMMAND")
        if type(c.tid) is not int or not 0 <= c.tid < workers: raise ValueError("THREAD")
        if type(c.value) is not int or not -100 <= c.value <= 100: raise ValueError("VALUE")
    machine = Machine(workers)
    for c in commands:
        if c.kind in ("P", "O", "E", "D"): machine.begin(c.kind, c.tid, c.value)
        elif c.kind == "T": machine.step(c.tid)
        elif c.kind == "F": machine.finish(c.tid)
        else: machine.scan()
    return machine

def aba_demo() -> str:
    saved_head, saved_next = 1, 2
    current_head, current_next = 1, 3  # Address 1 reused; old address 2 is freed.
    raw_ok = current_head == saved_head
    new_head = saved_next if raw_ok else current_head
    saved_version, current_version = 0, 3
    tagged_ok = (saved_head, saved_version) == (current_head, current_version)
    return (f"ABA raw current-next={current_next} CAS={int(raw_ok)} new-head={new_head} dangling={int(new_head == 2)}\n"
            f"ABA tagged expected=(1,0) current=(1,3) CAS={int(tagged_ok)}")

def format_result(machine: Machine) -> str:
    return "\n".join(machine.log + [f"CAS attempts={machine.attempts} wins={machine.wins}", aba_demo()])

def sample_commands() -> list[Command]:
    C = Command
    return [C("P",0,20),C("F",0),C("P",0,10),C("F",0),
            C("O",0),C("T",0),C("T",0),C("T",0),C("T",0),
            C("O",1),C("F",1),C("R",0),C("F",0),C("R",0),C("O",0),C("F",0),
            C("E",0,7),C("T",0),C("T",0),C("T",0),C("T",0),
            C("D",1),C("F",1),C("F",0),C("E",0,9),C("F",0),
            C("D",1),C("F",1),C("D",0),C("F",0)]

if __name__ == "__main__":
    print(format_result(simulate(2, sample_commands())))

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
struct Command { char kind; int tid, value = 0; };
struct Node { int value = 0, next = 0; bool alive = true; };
struct Operation {
    char kind;
    int tid, value, node, invoked;
    int pc = 0, a = 0, b = 0, c = 0, read_tick = 0, lp = 0, returned = 0;
    std::string result = "PENDING";
};
std::string numbers(const std::vector<int>& a) {
    std::ostringstream out; out << '[';
    for (std::size_t i=0; i<a.size(); ++i) { if (i) out << ','; out << a[i]; }
    out << ']'; return out.str();
}
std::string cas_text(const std::string& label, int expected, int desired, bool ok) {
    return label+" expect="+std::to_string(expected)+" set="+std::to_string(desired)+" ok="+std::to_string(ok);
}
class Machine {
public:
    int workers, head=0, qhead=1, qtail=1, clock=0, attempts=0, wins=0;
    std::vector<Node> stack, queue;
    std::vector<int> hp, retired, freed, active;
    std::vector<Operation> operations;
    std::vector<std::string> log;
    explicit Machine(int count) : workers(count), hp(count,0), active(count,-1) {
        stack.push_back(Node{0,0,false}); queue.push_back(Node{0,0,false}); queue.push_back(Node{});
    }
    Node& sn(int i) {
        if (i<=0 || i>=static_cast<int>(stack.size()) || !stack[i].alive)
            throw std::logic_error("BAD_STACK_DEREFERENCE");
        return stack[i];
    }
    Node& qn(int i) {
        if (i<=0 || i>=static_cast<int>(queue.size())) throw std::logic_error("BAD_QUEUE_DEREFERENCE");
        return queue[i];
    }
    std::vector<int> chain(bool is_queue=false) {
        std::vector<int> out; std::set<int> seen;
        int current=is_queue ? qn(qhead).next : head;
        while (current) {
            if (!seen.insert(current).second) throw std::logic_error("CYCLE");
            auto& node=is_queue ? qn(current) : sn(current);
            out.push_back(node.value); current=node.next;
        }
        return out;
    }
    void record(const std::string& note) {
        auto r=retired, f=freed; std::sort(r.begin(),r.end()); std::sort(f.begin(),f.end());
        std::ostringstream out; out << std::setw(3) << std::setfill('0') << clock << ' ' << note
            << " | S=" << numbers(chain()) << " head=" << head << " hp=" << numbers(hp)
            << " R=" << numbers(r) << " F=" << numbers(f) << " Q=" << numbers(chain(true))
            << " H=" << qhead << " T=" << qtail;
        log.push_back(out.str());
    }
    bool pending(int tid) const {
        return active[tid]>=0 && operations[active[tid]].result=="PENDING";
    }
    void begin(char kind, int tid, int value=0) {
        if (pending(tid)) throw std::invalid_argument("BUSY");
        ++clock; int node=0;
        if (kind=='P' || kind=='E') {
            auto& arena=kind=='P' ? stack : queue;
            node=static_cast<int>(arena.size()); arena.push_back(Node{value,0,true});
        }
        active[tid]=static_cast<int>(operations.size());
        operations.push_back(Operation{kind,tid,value,node,clock});
        record("begin "+std::string(1,kind)+" t="+std::to_string(tid)+" value="+std::to_string(value)+" node="+std::to_string(node));
    }
    bool cas(char where, int target, int expected, int desired) {
        ++attempts;
        int current=where=='S' ? head : where=='H' ? qhead : where=='T' ? qtail : qn(target).next;
        bool ok=current==expected;
        if (ok) {
            ++wins;
            if (where=='S') head=desired;
            else if (where=='H') qhead=desired;
            else if (where=='T') qtail=desired;
            else qn(target).next=desired;
        }
        return ok;
    }
    void complete(Operation& o, const std::string& result, int lp=0) {
        o.result=result; o.returned=clock; if (lp) o.lp=lp;
    }
    void step(int tid) {
        if (!pending(tid)) throw std::invalid_argument("IDLE");
        ++clock; auto& o=operations[active[tid]]; std::string note;
        if (o.kind=='P') {
            if (o.pc==0) { o.a=head; o.pc=1; note="P.read head="+std::to_string(o.a); }
            else if (o.pc==1) { sn(o.node).next=o.a; o.pc=2; note="P.private-next="+std::to_string(o.a); }
            else {
                bool ok=cas('S',0,o.a,o.node); note=cas_text("P.cas-head",o.a,o.node,ok);
                if (ok) complete(o,"OK",clock); else o.pc=0;
            }
        } else if (o.kind=='O') {
            if (o.pc==0) {
                o.a=head; note="O.read head="+std::to_string(o.a);
                if (!o.a) complete(o,"EMPTY",clock); else o.pc=1;
            } else if (o.pc==1) { hp[tid]=o.a; o.pc=2; note="O.publish hp="+std::to_string(o.a); }
            else if (o.pc==2) {
                bool valid=head==o.a; note="O.validate ok="+std::to_string(valid);
                if (valid) o.pc=3; else { hp[tid]=0; o.pc=0; }
            } else if (o.pc==3) {
                if (hp[tid]!=o.a) throw std::logic_error("UNPROTECTED");
                auto& node=sn(o.a); o.b=node.next; o.value=node.value; o.pc=4;
                note="O.read-next="+std::to_string(o.b)+" value="+std::to_string(o.value);
            } else {
                bool ok=cas('S',0,o.a,o.b); note=cas_text("O.cas-head",o.a,o.b,ok); hp[tid]=0;
                if (ok) { retired.push_back(o.a); complete(o,std::to_string(o.value),clock); } else o.pc=0;
            }
        } else if (o.kind=='E') {
            if (o.pc==0) { o.a=qtail; o.pc=1; note="E.read-tail="+std::to_string(o.a); }
            else if (o.pc==1) { o.b=qn(o.a).next; o.pc=2; note="E.read-next="+std::to_string(o.b); }
            else if (o.pc==2) {
                bool valid=qtail==o.a; note="E.validate ok="+std::to_string(valid); o.pc=valid ? (o.b ? 3 : 4) : 0;
            } else if (o.pc==3) {
                bool ok=cas('T',0,o.a,o.b); o.pc=0; note=cas_text("E.help-tail",o.a,o.b,ok);
            } else if (o.pc==4) {
                bool ok=cas('N',o.a,0,o.node); note=cas_text("E.link-next",0,o.node,ok);
                if (ok) { o.lp=clock; o.pc=5; } else o.pc=0;
            } else {
                bool ok=cas('T',0,o.a,o.node); note=cas_text("E.advance-tail",o.a,o.node,ok); complete(o,"OK");
            }
        } else {
            if (o.pc==0) { o.a=qhead; o.pc=1; note="D.read-head="+std::to_string(o.a); }
            else if (o.pc==1) { o.b=qtail; o.pc=2; note="D.read-tail="+std::to_string(o.b); }
            else if (o.pc==2) { o.c=qn(o.a).next; o.read_tick=clock; o.pc=3; note="D.read-next="+std::to_string(o.c); }
            else if (o.pc==3) {
                bool valid=qhead==o.a; note="D.validate ok="+std::to_string(valid);
                if (!valid) o.pc=0;
                else if (o.a==o.b) { if (!o.c) complete(o,"EMPTY",o.read_tick); else o.pc=4; }
                else o.pc=5;
            } else if (o.pc==4) {
                bool ok=cas('T',0,o.b,o.c); o.pc=0; note=cas_text("D.help-tail",o.b,o.c,ok);
            } else if (o.pc==5) { o.value=qn(o.c).value; o.pc=6; note="D.read-value="+std::to_string(o.value); }
            else {
                bool ok=cas('H',0,o.a,o.c); note=cas_text("D.cas-head",o.a,o.c,ok);
                if (ok) complete(o,std::to_string(o.value),clock); else o.pc=0;
            }
        }
        if (o.result!="PENDING") note+=" return="+o.result+" lp="+std::to_string(o.lp);
        record("t="+std::to_string(tid)+" "+note);
    }
    void finish(int tid) {
        if (!pending(tid)) throw std::invalid_argument("IDLE");
        while (pending(tid)) step(tid);
    }
    void scan() {
        ++clock; std::set<int> protected_nodes(hp.begin(),hp.end());
        std::vector<int> keep,released;
        for (int node : retired) {
            if (protected_nodes.count(node)) keep.push_back(node);
            else { sn(node).alive=false; freed.push_back(node); released.push_back(node); }
        }
        retired=keep; std::sort(released.begin(),released.end()); record("scan released="+numbers(released));
    }
};
Machine simulate(int workers, const std::vector<Command>& commands) {
    if (workers<1 || workers>4) throw std::invalid_argument("WORKERS");
    if (commands.size()>256) throw std::invalid_argument("SIZE");
    for (auto c : commands) {
        if (std::string("POEDTFR").find(c.kind)==std::string::npos) throw std::invalid_argument("COMMAND");
        if (c.tid<0 || c.tid>=workers) throw std::invalid_argument("THREAD");
        if (c.value < -100 || c.value > 100) throw std::invalid_argument("VALUE");
    }
    Machine machine(workers);
    for (auto c : commands) {
        if (std::string("POED").find(c.kind)!=std::string::npos) machine.begin(c.kind,c.tid,c.value);
        else if (c.kind=='T') machine.step(c.tid);
        else if (c.kind=='F') machine.finish(c.tid);
        else machine.scan();
    }
    return machine;
}
std::string aba_demo() {
    int saved_head=1,saved_next=2,current_head=1,current_next=3;
    bool raw_ok=current_head==saved_head;
    int new_head=raw_ok ? saved_next : current_head;
    int saved_version=0,current_version=3;
    bool tagged_ok=saved_head==current_head && saved_version==current_version;
    return "ABA raw current-next="+std::to_string(current_next)+" CAS="+std::to_string(raw_ok)
         +" new-head="+std::to_string(new_head)+" dangling="+std::to_string(new_head==2)
         +"\nABA tagged expected=(1,0) current=(1,3) CAS="+std::to_string(tagged_ok);
}
std::string format_result(const Machine& machine) {
    std::ostringstream out;
    for (const auto& line : machine.log) out << line << '\n';
    out << "CAS attempts=" << machine.attempts << " wins=" << machine.wins << '\n' << aba_demo();
    return out.str();
}
std::vector<Command> sample_commands() {
    return { {'P',0,20},{'F',0},{'P',0,10},{'F',0},
             {'O',0},{'T',0},{'T',0},{'T',0},{'T',0},
             {'O',1},{'F',1},{'R',0},{'F',0},{'R',0},{'O',0},{'F',0},
             {'E',0,7},{'T',0},{'T',0},{'T',0},{'T',0},
             {'D',1},{'F',1},{'F',0},{'E',0,9},{'F',0},
             {'D',1},{'F',1},{'D',0},{'F',0} };
}
int main() {
    std::cout << format_result(simulate(2,sample_commands())) << '\n';
    return 0;
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static final class Command {
        char kind; int tid, value;
        Command(char kind, int tid) { this(kind,tid,0); }
        Command(char kind, int tid, int value) { this.kind=kind; this.tid=tid; this.value=value; }
    }
    static final class Node {
        int value, next; boolean alive=true;
        Node(int value) { this.value=value; }
    }
    static final class Operation {
        char kind; int tid, value, node, invoked, pc, a, b, c, readTick, lp, returned;
        String result="PENDING";
        Operation(char kind, int tid, int value, int node, int invoked) {
            this.kind=kind; this.tid=tid; this.value=value; this.node=node; this.invoked=invoked;
        }
    }
    static String numbers(List<Integer> a) {
        StringBuilder out=new StringBuilder("[");
        for (int i=0; i<a.size(); ++i) { if (i!=0) out.append(','); out.append(a.get(i)); }
        return out.append(']').toString();
    }
    static List<Integer> integers(int[] a) {
        List<Integer> out=new ArrayList<>(); for (int x : a) out.add(x); return out;
    }
    static String casText(String label, int expected, int desired, boolean ok) {
        return label+" expect="+expected+" set="+desired+" ok="+(ok ? 1 : 0);
    }
    static final class Machine {
        int workers, head, qhead=1, qtail=1, clock, attempts, wins;
        List<Node> stack=new ArrayList<>(), queue=new ArrayList<>();
        int[] hp, active;
        List<Integer> retired=new ArrayList<>(), freed=new ArrayList<>();
        List<Operation> operations=new ArrayList<>();
        List<String> log=new ArrayList<>();
        Machine(int workers) {
            this.workers=workers; hp=new int[workers]; active=new int[workers]; Arrays.fill(active,-1);
            Node unused=new Node(0); unused.alive=false;
            stack.add(unused); queue.add(unused); queue.add(new Node(0));
        }
        Node sn(int i) {
            if (i<=0 || i>=stack.size() || !stack.get(i).alive) throw new IllegalStateException("BAD_STACK_DEREFERENCE");
            return stack.get(i);
        }
        Node qn(int i) {
            if (i<=0 || i>=queue.size()) throw new IllegalStateException("BAD_QUEUE_DEREFERENCE");
            return queue.get(i);
        }
        List<Integer> chain(boolean isQueue) {
            List<Integer> out=new ArrayList<>(); Set<Integer> seen=new HashSet<>();
            int current=isQueue ? qn(qhead).next : head;
            while (current!=0) {
                if (!seen.add(current)) throw new IllegalStateException("CYCLE");
                Node node=isQueue ? qn(current) : sn(current);
                out.add(node.value); current=node.next;
            }
            return out;
        }
        void record(String note) {
            List<Integer> r=new ArrayList<>(retired), f=new ArrayList<>(freed);
            Collections.sort(r); Collections.sort(f);
            String time=Integer.toString(clock); while (time.length()<3) time="0"+time;
            log.add(time+" "+note+" | S="+numbers(chain(false))+" head="+head+" hp="+numbers(integers(hp))
                    +" R="+numbers(r)+" F="+numbers(f)+" Q="+numbers(chain(true))+" H="+qhead+" T="+qtail);
        }
        boolean pending(int tid) { return active[tid]>=0 && operations.get(active[tid]).result.equals("PENDING"); }
        void begin(char kind, int tid, int value) {
            if (pending(tid)) throw new IllegalArgumentException("BUSY");
            ++clock; int node=0;
            if (kind=='P' || kind=='E') {
                List<Node> arena=kind=='P' ? stack : queue;
                node=arena.size(); arena.add(new Node(value));
            }
            active[tid]=operations.size(); operations.add(new Operation(kind,tid,value,node,clock));
            record("begin "+kind+" t="+tid+" value="+value+" node="+node);
        }
        boolean cas(char where, int target, int expected, int desired) {
            ++attempts;
            int current=where=='S' ? head : where=='H' ? qhead : where=='T' ? qtail : qn(target).next;
            boolean ok=current==expected;
            if (ok) {
                ++wins;
                if (where=='S') head=desired;
                else if (where=='H') qhead=desired;
                else if (where=='T') qtail=desired;
                else qn(target).next=desired;
            }
            return ok;
        }
        void complete(Operation o, String result, int lp) {
            o.result=result; o.returned=clock; if (lp!=0) o.lp=lp;
        }
        void step(int tid) {
            if (!pending(tid)) throw new IllegalArgumentException("IDLE");
            ++clock; Operation o=operations.get(active[tid]); String note;
            if (o.kind=='P') {
                if (o.pc==0) { o.a=head; o.pc=1; note="P.read head="+o.a; }
                else if (o.pc==1) { sn(o.node).next=o.a; o.pc=2; note="P.private-next="+o.a; }
                else {
                    boolean ok=cas('S',0,o.a,o.node); note=casText("P.cas-head",o.a,o.node,ok);
                    if (ok) complete(o,"OK",clock); else o.pc=0;
                }
            } else if (o.kind=='O') {
                if (o.pc==0) {
                    o.a=head; note="O.read head="+o.a;
                    if (o.a==0) complete(o,"EMPTY",clock); else o.pc=1;
                } else if (o.pc==1) { hp[tid]=o.a; o.pc=2; note="O.publish hp="+o.a; }
                else if (o.pc==2) {
                    boolean valid=head==o.a; note="O.validate ok="+(valid ? 1 : 0);
                    if (valid) o.pc=3; else { hp[tid]=0; o.pc=0; }
                } else if (o.pc==3) {
                    if (hp[tid]!=o.a) throw new IllegalStateException("UNPROTECTED");
                    Node node=sn(o.a); o.b=node.next; o.value=node.value; o.pc=4;
                    note="O.read-next="+o.b+" value="+o.value;
                } else {
                    boolean ok=cas('S',0,o.a,o.b); note=casText("O.cas-head",o.a,o.b,ok); hp[tid]=0;
                    if (ok) { retired.add(o.a); complete(o,Integer.toString(o.value),clock); } else o.pc=0;
                }
            } else if (o.kind=='E') {
                if (o.pc==0) { o.a=qtail; o.pc=1; note="E.read-tail="+o.a; }
                else if (o.pc==1) { o.b=qn(o.a).next; o.pc=2; note="E.read-next="+o.b; }
                else if (o.pc==2) {
                    boolean valid=qtail==o.a; note="E.validate ok="+(valid ? 1 : 0); o.pc=valid ? (o.b!=0 ? 3 : 4) : 0;
                } else if (o.pc==3) {
                    boolean ok=cas('T',0,o.a,o.b); o.pc=0; note=casText("E.help-tail",o.a,o.b,ok);
                } else if (o.pc==4) {
                    boolean ok=cas('N',o.a,0,o.node); note=casText("E.link-next",0,o.node,ok);
                    if (ok) { o.lp=clock; o.pc=5; } else o.pc=0;
                } else {
                    boolean ok=cas('T',0,o.a,o.node); note=casText("E.advance-tail",o.a,o.node,ok); complete(o,"OK",0);
                }
            } else {
                if (o.pc==0) { o.a=qhead; o.pc=1; note="D.read-head="+o.a; }
                else if (o.pc==1) { o.b=qtail; o.pc=2; note="D.read-tail="+o.b; }
                else if (o.pc==2) { o.c=qn(o.a).next; o.readTick=clock; o.pc=3; note="D.read-next="+o.c; }
                else if (o.pc==3) {
                    boolean valid=qhead==o.a; note="D.validate ok="+(valid ? 1 : 0);
                    if (!valid) o.pc=0;
                    else if (o.a==o.b) { if (o.c==0) complete(o,"EMPTY",o.readTick); else o.pc=4; }
                    else o.pc=5;
                } else if (o.pc==4) {
                    boolean ok=cas('T',0,o.b,o.c); o.pc=0; note=casText("D.help-tail",o.b,o.c,ok);
                } else if (o.pc==5) { o.value=qn(o.c).value; o.pc=6; note="D.read-value="+o.value; }
                else {
                    boolean ok=cas('H',0,o.a,o.c); note=casText("D.cas-head",o.a,o.c,ok);
                    if (ok) complete(o,Integer.toString(o.value),clock); else o.pc=0;
                }
            }
            if (!o.result.equals("PENDING")) note+=" return="+o.result+" lp="+o.lp;
            record("t="+tid+" "+note);
        }
        void finish(int tid) {
            if (!pending(tid)) throw new IllegalArgumentException("IDLE");
            while (pending(tid)) step(tid);
        }
        void scan() {
            ++clock; Set<Integer> protectedNodes=new HashSet<>(integers(hp));
            List<Integer> keep=new ArrayList<>(), released=new ArrayList<>();
            for (int node : retired) {
                if (protectedNodes.contains(node)) keep.add(node);
                else { sn(node).alive=false; freed.add(node); released.add(node); }
            }
            retired=keep; Collections.sort(released); record("scan released="+numbers(released));
        }
    }
    static Machine simulate(int workers, List<Command> commands) {
        if (workers<1 || workers>4) throw new IllegalArgumentException("WORKERS");
        if (commands.size()>256) throw new IllegalArgumentException("SIZE");
        for (Command c : commands) {
            if ("POEDTFR".indexOf(c.kind)<0) throw new IllegalArgumentException("COMMAND");
            if (c.tid<0 || c.tid>=workers) throw new IllegalArgumentException("THREAD");
            if (c.value < -100 || c.value > 100) throw new IllegalArgumentException("VALUE");
        }
        Machine machine=new Machine(workers);
        for (Command c : commands) {
            if ("POED".indexOf(c.kind)>=0) machine.begin(c.kind,c.tid,c.value);
            else if (c.kind=='T') machine.step(c.tid);
            else if (c.kind=='F') machine.finish(c.tid);
            else machine.scan();
        }
        return machine;
    }
    static String abaDemo() {
        int savedHead=1, savedNext=2, currentHead=1, currentNext=3;
        boolean rawOk=currentHead==savedHead;
        int newHead=rawOk ? savedNext : currentHead;
        int savedVersion=0, currentVersion=3;
        boolean taggedOk=savedHead==currentHead && savedVersion==currentVersion;
        return "ABA raw current-next="+currentNext+" CAS="+(rawOk ? 1 : 0)+" new-head="+newHead
             +" dangling="+(newHead==2 ? 1 : 0)+"\nABA tagged expected=(1,0) current=(1,3) CAS="+(taggedOk ? 1 : 0);
    }
    static String formatResult(Machine machine) {
        StringBuilder out=new StringBuilder();
        for (String line : machine.log) out.append(line).append('\n');
        return out.append("CAS attempts=").append(machine.attempts).append(" wins=").append(machine.wins)
                  .append('\n').append(abaDemo()).toString();
    }
    static List<Command> sampleCommands() {
        return Arrays.asList(new Command('P',0,20),new Command('F',0),new Command('P',0,10),new Command('F',0),
            new Command('O',0),new Command('T',0),new Command('T',0),new Command('T',0),new Command('T',0),
            new Command('O',1),new Command('F',1),new Command('R',0),new Command('F',0),new Command('R',0),new Command('O',0),new Command('F',0),
            new Command('E',0,7),new Command('T',0),new Command('T',0),new Command('T',0),new Command('T',0),
            new Command('D',1),new Command('F',1),new Command('F',0),new Command('E',0,9),new Command('F',0),
            new Command('D',1),new Command('F',1),new Command('D',0),new Command('F',0));
    }
    public static void main(String[] args) { System.out.println(formatResult(simulate(2,sampleCommands()))); }
}

Identical expected output (each item is one printed line; R/F are retired/reclaimed stack IDs, and H/T are queue Head/Tail):

• 001 begin P t=0 value=20 node=1 | S=[] head=0 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 002 t=0 P.read head=0 | S=[] head=0 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 003 t=0 P.private-next=0 | S=[] head=0 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 004 t=0 P.cas-head expect=0 set=1 ok=1 return=OK lp=4 | S=[20] head=1 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 005 begin P t=0 value=10 node=2 | S=[20] head=1 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 006 t=0 P.read head=1 | S=[20] head=1 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 007 t=0 P.private-next=1 | S=[20] head=1 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 008 t=0 P.cas-head expect=1 set=2 ok=1 return=OK lp=8 | S=[10,20] head=2 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 009 begin O t=0 value=0 node=0 | S=[10,20] head=2 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 010 t=0 O.read head=2 | S=[10,20] head=2 hp=[0,0] R=[] F=[] Q=[] H=1 T=1
• 011 t=0 O.publish hp=2 | S=[10,20] head=2 hp=[2,0] R=[] F=[] Q=[] H=1 T=1
• 012 t=0 O.validate ok=1 | S=[10,20] head=2 hp=[2,0] R=[] F=[] Q=[] H=1 T=1
• 013 t=0 O.read-next=1 value=10 | S=[10,20] head=2 hp=[2,0] R=[] F=[] Q=[] H=1 T=1
• 014 begin O t=1 value=0 node=0 | S=[10,20] head=2 hp=[2,0] R=[] F=[] Q=[] H=1 T=1
• 015 t=1 O.read head=2 | S=[10,20] head=2 hp=[2,0] R=[] F=[] Q=[] H=1 T=1
• 016 t=1 O.publish hp=2 | S=[10,20] head=2 hp=[2,2] R=[] F=[] Q=[] H=1 T=1
• 017 t=1 O.validate ok=1 | S=[10,20] head=2 hp=[2,2] R=[] F=[] Q=[] H=1 T=1
• 018 t=1 O.read-next=1 value=10 | S=[10,20] head=2 hp=[2,2] R=[] F=[] Q=[] H=1 T=1
• 019 t=1 O.cas-head expect=2 set=1 ok=1 return=10 lp=19 | S=[20] head=1 hp=[2,0] R=[2] F=[] Q=[] H=1 T=1
• 020 scan released=[] | S=[20] head=1 hp=[2,0] R=[2] F=[] Q=[] H=1 T=1
• 021 t=0 O.cas-head expect=2 set=1 ok=0 | S=[20] head=1 hp=[0,0] R=[2] F=[] Q=[] H=1 T=1
• 022 t=0 O.read head=1 | S=[20] head=1 hp=[0,0] R=[2] F=[] Q=[] H=1 T=1
• 023 t=0 O.publish hp=1 | S=[20] head=1 hp=[1,0] R=[2] F=[] Q=[] H=1 T=1
• 024 t=0 O.validate ok=1 | S=[20] head=1 hp=[1,0] R=[2] F=[] Q=[] H=1 T=1
• 025 t=0 O.read-next=0 value=20 | S=[20] head=1 hp=[1,0] R=[2] F=[] Q=[] H=1 T=1
• 026 t=0 O.cas-head expect=1 set=0 ok=1 return=20 lp=26 | S=[] head=0 hp=[0,0] R=[1,2] F=[] Q=[] H=1 T=1
• 027 scan released=[1,2] | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 028 begin O t=0 value=0 node=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 029 t=0 O.read head=0 return=EMPTY lp=29 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 030 begin E t=0 value=7 node=2 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 031 t=0 E.read-tail=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 032 t=0 E.read-next=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 033 t=0 E.validate ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=1 T=1
• 034 t=0 E.link-next expect=0 set=2 ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=1
• 035 begin D t=1 value=0 node=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=1
• 036 t=1 D.read-head=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=1
• 037 t=1 D.read-tail=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=1
• 038 t=1 D.read-next=2 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=1
• 039 t=1 D.validate ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=1
• 040 t=1 D.help-tail expect=1 set=2 ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=2
• 041 t=1 D.read-head=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=2
• 042 t=1 D.read-tail=2 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=2
• 043 t=1 D.read-next=2 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=2
• 044 t=1 D.validate ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=2
• 045 t=1 D.read-value=7 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[7] H=1 T=2
• 046 t=1 D.cas-head expect=1 set=2 ok=1 return=7 lp=46 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=2 T=2
• 047 t=0 E.advance-tail expect=1 set=2 ok=0 return=OK lp=34 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=2 T=2
• 048 begin E t=0 value=9 node=3 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=2 T=2
• 049 t=0 E.read-tail=2 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=2 T=2
• 050 t=0 E.read-next=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=2 T=2
• 051 t=0 E.validate ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=2 T=2
• 052 t=0 E.link-next expect=0 set=3 ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=2
• 053 t=0 E.advance-tail expect=2 set=3 ok=1 return=OK lp=52 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 054 begin D t=1 value=0 node=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 055 t=1 D.read-head=2 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 056 t=1 D.read-tail=3 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 057 t=1 D.read-next=3 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 058 t=1 D.validate ok=1 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 059 t=1 D.read-value=9 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[9] H=2 T=3
• 060 t=1 D.cas-head expect=2 set=3 ok=1 return=9 lp=60 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=3 T=3
• 061 begin D t=0 value=0 node=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=3 T=3
• 062 t=0 D.read-head=3 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=3 T=3
• 063 t=0 D.read-tail=3 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=3 T=3
• 064 t=0 D.read-next=0 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=3 T=3
• 065 t=0 D.validate ok=1 return=EMPTY lp=64 | S=[] head=0 hp=[0,0] R=[] F=[1,2] Q=[] H=3 T=3
• CAS attempts=12 wins=10
• ABA raw current-next=3 CAS=1 new-head=2 dangling=1
• ABA tagged expected=(1,0) current=(1,3) CAS=0

Complexity, Correctness, and Invariants

Concurrency requires separate correctness, progress, cost, and lifetime arguments. A finite passing trace is evidence for the stated model; it does not replace a proof for all legal executions or a language's memory-order rules.

Stack linearizability. The reachable chain from Head represents the abstract top-to-bottom stack. A push publishes one initialized private node through a successful Head CAS, placing it ahead of the previous chain. A successful pop removes exactly the Head candidate whose identity still matches its expected value and returns that node's previously copied value. These CAS actions are the respective LPs. A failed pop CAS removes nothing and must retry; an empty pop linearizes at its observed null Head. Fresh IDs and no reinsertion rule out logical reuse in the modeled stack, while the hazard protocol handles its modeled node lifetime.

Queue linearizability. The abstract queue is the linked sequence after the Head dummy. A successful null-to-new-node next-link CAS appends one initialized value and is the enqueue LP. Tail is a hint that may lag the last node; helping Tail changes a hint, not queue membership. A successful Head CAS advances the dummy to its successor and removes exactly that successor's copied value from the abstract queue, making it the dequeue LP. An empty dequeue's validated null-next observation supplies a point at which the queue is empty; in this code that point can precede its final validation and response. Reading only Head==Tail is insufficient because a linked successor may already exist.

The representation stays acyclic, Head is a retained dummy on the queue chain, and Tail is reachable from Head and at most one link behind the physical last node in this version. Link fields change only from null to a fresh successor. Fresh IDs/no queue reclamation make saved queue references valid; the original memory-management assumptions must be revisited before porting these arguments to reusable pointer storage.

Hazard safety under SC. Suppose a pop has published hazard h, re-read Head equal to h, and is about to dereference it. If h is removed afterward, a scan while this protection is held sees the slot and keeps h. If removal/reclamation happened before publication, validation sees the changed Head and rejects h before dereference, because IDs never cycle back. A scan that occurs before publication while h is still reachable cannot reclaim it: only retired nodes are candidates. Therefore the modeled pop does not dereference a reclaimed node. Keeping a node alive does not force its CAS to succeed; structural freshness and lifetime are different checks. This is why the sample can safely fail its stale CAS after a competing pop.

Progress. Under the usual assumptions of nonblocking strong CAS, finite local steps, safe memory lifetime, and continued scheduling, a stale strong-CAS failure witnesses some intervening modification. Stack Head changes are successful structural operations. A queue next-link or Head change makes abstract progress; Tail helping supports already-linked publication and prevents a paused enqueuer from becoming an owner others must wait for. Persistent contention can prevent one caller from winning forever while others complete, so Treiber/MS core loops are lock-free rather than wait-free. Weak CAS spurious failure alone does not witness another thread's progress; a proof using that API must account for it. Blocking allocation, logging, a blocking reclaimer or a non-lock-free wide atomic can change the end-to-end progress contract.

Core operation cost. Let f be the number of failed/restarted attempts, including repeated snapshot validation failures, before a particular call completes. Each modeled attempt has a bounded number of pointer actions, so its structural step cost is $O(1+f)$, excluding allocation, scans, and logging. The uncontended successful/empty paths are $O(1)$. Under unbounded contention, a single operation's worst-case steps are unbounded; lock-freedom supplies no finite individual upper bound. There is no universal average-case bound without a scheduler/contention distribution. A queue method's final Tail CAS can fail after its enqueue LP without requiring the completed publication to be repeated.

Reclamation cost. With H published hazard slots and R retired candidates, collecting slots into a hash set and testing each candidate takes expected $O(H+R)$ time, subject to the set's assumptions. A deterministic ordered-set implementation instead gives $O((H+R)\log(H+1))$ as a convenient upper bound. Python/Java use hashed sets here; C++ uses an ordered set. These bounds cover eligibility testing; sorting released IDs and full-state logging add separate simulator costs. A scanner must also synchronize its observations correctly in a real memory model. This lesson scans explicitly, so it makes no automatic amortized scan-frequency claim. A protected node can remain unreclaimed indefinitely if its owner stops; that does not by itself block unrelated stack operations.

Space. A real linked structure retains live nodes plus retired nodes not yet safe to reclaim, hazard records, and any allocator metadata. H hazard slots cost $O(H)$; the total retired backlog is not automatically bounded by H. A particular hazard scheme can establish stronger bounds with its own thresholds and ownership assumptions. This simulator keeps metadata for every allocated node, including reclaimed stack markers and obsolete queue dummies. Its storage therefore grows with total pushes/enqueues, not merely current stack/queue length. Saved events also grow with the trace length.

Simulator overhead is intentional. Each logged event traverses the live stack/queue, checks cycles, sorts retired/freed IDs for display, and formats state. If V bounds allocated nodes and E is the event count, a coarse bound is $O(E(V\log(V+1)+H+1))$ word-level work for this verbose model, with additional text-size costs; saved text can likewise scale with E times displayed state size. These costs are unrelated to the core's uncontended constant-time pointer actions. The node arenas and plain fields are not production lock-free storage, and the deterministic scheduler does not measure throughput.

The proofs above also assume initialized payloads become visible when a node is published, link/head/tail accesses obey the chosen memory model, and only a validated live node is dereferenced. Logical linearizability without those lifetime/publication conditions is not enough for a valid native implementation.

Variants, Pitfalls, and Optimizations

CAS does not protect a stale dereference. Reading p->next before publishing/revalidating protection can access freed memory even if the later CAS fails. A second Head check after that dereference is too late. In our stack protocol, the hazard stays published through the node-field reads and the CAS attempt, and value copying finishes before protection is cleared. The modeled scanner may encounter a tentative hazard that names dead metadata, but it only compares the ID; the reader must fail validation before using fields.

ABA has two separate dimensions. A stale address may equal a different node's recycled address; a live node may also be removed and reinserted with a changed successor. The fresh-node/no-reinsertion model rules both out within its actual arenas, while the separate address demonstration makes the danger visible. Correct hazard reclamation prevents freeing/reusing a validated protected node, but cannot alone forbid arbitrary reinsertion of the same live object. Atomic stamped pointers can detect version changes, provided the entire pair is compared atomically and the stamp has not wrapped. After $2^b$ increments a b-bit stamp cycles, so its adequacy needs a bound or another argument. Stamps do not make dereferencing an already-freed node safe.

Publish initialized nodes with the required ordering. Payload and next initialization must become visible before a reader consumes the newly published node. Real head/tail/link/hazard locations need appropriate atomic accesses and an established memory-ordering protocol. A release store to a hazard slot and acquire loads in a scan are not, by themselves, a proof that the protect/validate/scan race matches this SC model. Use a verified algorithm/library and its required fences/orderings. The plain assignments here are valid because the host runs one modeled transition at a time; adding OS threads to this code is not a correct port.

Tail equality and failed Tail CAS are easy to misread. In MS enqueue, successful linking already commits the item. Requiring the final Tail CAS to succeed before reporting that publication would misunderstand helping. In dequeue, Head=Tail with non-null next means Tail lags; returning EMPTY there loses a queued item. Keep dummy movement distinct from value removal and never return the old dummy's payload. A queue reclaimer must protect every pointer it may dereference and validate the relevant snapshot; the stack's one-slot recipe is not an automatic MS-queue reclamation implementation.

Garbage collection changes lifetime, not all correctness obligations. Holding a managed reference can keep that object alive, but logical ABA through removal/reinsertion remains possible. Moving between Python, Java and C++ changes APIs, atomic contracts, object lifetime, and reclamation mechanisms; identical state-machine outputs do not erase those differences. A runtime lock or GIL also does not make an arbitrary multi-step abstract operation linearizable automatically.

Progress extends beyond a CAS loop. Dynamic allocation, destruction, reference counting, scans, logging, or fallback atomics may block or add unbounded work. Backoff can reduce contention but does not make an operation wait-free. Elimination techniques can let complementary stack pushes/pops meet away from Head, but require their own matching/linearization proof. Epoch-based reclamation, RCU-style techniques, bounded ring buffers, and queue locks offer different costs and lifetime/progress assumptions. A stalled participant can prevent epoch advancement; hazard pointers have a different retention pattern. Measure allocator behavior, cache-line contention, false sharing, fairness and tail latency under the actual workload.

Testing limits and useful tools. Explore adversarial interleavings, validate LP witnesses or search for a valid sequential history, and test lifetime separately from return values. A sanitizer can expose some memory bugs; passing it cannot prove atomic ordering or linearizability. An SC node-ID model cannot expose all weak-memory reorderings, platform-level lock-free guarantees, or real address reuse. Those require implementation-specific tests and proofs. Our test report deliberately names its bounded state normalization and retained-node assumptions so its scope is reviewable.

Practice Problems and Real-World Use

Begin with sequential stack and queue specifications. Record each operation's invocation, response and result. For a proposed LP ordering, verify that each point lies inside its call interval and replay that ordering against the specification. Include effects of an enqueue that has linked but has not yet returned when checking a partial history. Real-time precedence is preserved automatically by a valid in-interval witness, but the witness must still reproduce every result and final abstract state.

Construct schedules that pause a stack pop before hazard publication, after validation, and immediately before CAS. Interleave removal and scans at each location. A scan before publication may reclaim a removed candidate, so the later validation must reject it without dereferencing. A scan while a validated hazard is held must retain it. After protection clears, a later scan may reclaim it. Deliberately schedule two successful pops competing for one top candidate and verify the loser retries rather than returns a duplicate value.

For MS queues, pause an enqueuer immediately after successful linking. A second enqueuer or dequeue should be able to help Tail. Try two competing dequeues, empty queues, repeated payload values, and enqueue-after-null-next histories; distinguish identity from payload equality. Extend the model with actual address reuse only together with an explicit identity/lifetime policy, then test raw, stamped and protected variants against that policy. Never turn an illustrative unsafe dereference into executable native test code.

The exercises below move from state-machine reasoning toward real implementations. A practical next step is a small linearizability checker for recorded histories, followed by a memory-model-aware implementation built on a proven reclamation scheme. Benchmark a well-engineered locked baseline as well as the nonblocking version. Report correctness assumptions, progress conditions, allocator/reclaimer behavior, thread counts, contention, throughput and latency distributions; “uses CAS” is not an adequate performance result.

Primary reading: Michael and Scott's corrected queue pseudocode documents the link/help/dummy algorithm and its memory-management assumptions. Maged Michael's hazard-pointer paper develops safe reclamation for lock-free objects; IBM's publication record identifies the original work. The node-ID lifetime guards, exact event numbering and finite script tests above belong to this lesson's SC teaching model.