skip to content

What is AtomicMarkableReference, how does it differ from AtomicStampedReference, and when would you choose it?

level: seniorimportance: nice to knowfreq 28%

answer

  1. Mark = one boolean; stamp = int version
  2. get(boolean[]) snapshot; compareAndSet(ref, ref', mark, mark')
  3. Canonical use: logical delete in lock-free linked lists (Harris/Michael)
  4. A toggling bit doesn't fully defeat ABA; a monotonic stamp does
  5. Both box an internal (ref, payload) holder

basics

~20 s

AtomicMarkableReference pairs a reference with a single boolean 'mark' instead of an int version. It's used to flag a node (e.g. logically deleted) atomically. It carries one bit, not a full history, so it doesn't fully defeat ABA the way a stamp does.

solid answer

~50 s

AtomicMarkableReference<V> bundles a reference with one boolean 'mark', whereas AtomicStampedReference bundles it with an int 'stamp' (a version counter). You read both with get(boolean[] markHolder) and update with compareAndSet(expRef, newRef, expMark, newMark), succeeding only if both the reference and the mark match. The mark is meant to attach a single piece of atomic state to a reference — classically, marking a node as logically deleted before it is physically unlinked in a lock-free linked list (the Harris/Michael algorithm), so that insertion and deletion don't race. The key difference: a stamp monotonically increases and thus detects A→B→A; a one-bit mark can toggle back to its prior value, so on its own it does not fully solve the general ABA problem. Choose the markable reference when your algorithm needs exactly one logical flag tied atomically to a reference; choose the stamped reference when you need true version-based ABA protection.

code

java · 14 lines
java
// next pointer of a lock-free list node, with a deletion mark:
AtomicMarkableReference<Node> next =
    new AtomicMarkableReference<>(successor, /*marked=*/ false);

// Logically delete: mark this node without changing its successor.
boolean[] holder = new boolean[1];
Node succ = next.get(holder);
boolean wasMarked = holder[0];
if (!wasMarked) {
    // flip only the mark, expecting the same successor reference
    boolean logicallyDeleted = next.attemptMark(succ, true);
}
// A concurrent insert sees next is marked and retries instead of
// linking after a node that is being removed.

go deeper

for a junior

Knows AtomicMarkableReference is a reference plus a boolean mark, versus AtomicStampedReference's int stamp.

for a middle

Can read with get(boolean[]) and update with compareAndSet(ref, ref', mark, mark'), and states the typical use is flagging a node (e.g. logically deleted).

for a senior

Explains the lock-free linked-list logical-vs-physical deletion algorithm, why the mark lives in the next pointer, and why a togglable bit is not general ABA protection while a stamp is.

for a principal

Discusses the Harris/Michael lock-free set design, why monotone marking makes the bit sufficient there, the allocation cost of the boxed holder under contention, and how the choice between mark, stamp, and plain reference follows from the invariant each enforces.

## What it is `AtomicMarkableReference<V>` (in `java.util.concurrent.atomic`) atomically holds a **reference** of type `V` together with a single **boolean mark**. Think of it as 'a reference with one sticky flag bit attached, and you can update the reference and the flag together atomically.' It is the sibling of `AtomicStampedReference`, which instead attaches an `int` **stamp** (a version counter). ## API shape ```java AtomicMarkableReference<Node> ref = new AtomicMarkableReference<>(node, false); // reference, initial mark boolean[] markHolder = new boolean[1]; Node current = ref.get(markHolder); // reference + mark as one snapshot boolean marked = markHolder[0]; boolean ok = ref.compareAndSet( current, // expected reference next, // new reference marked, // expected mark true); // new mark ``` Mirroring the stamped version: `get(boolean[])` gives an atomic (reference, mark) snapshot; `compareAndSet` succeeds only if **both** the reference and the mark still match; there are also `isMarked()`, `getReference()`, `attemptMark(expectedRef, newMark)` (flip just the mark), and `set(...)`. ## The canonical use: lock-free linked-list deletion The famous use is lock-free **set/list** algorithms (Harris 2001, Michael 2002). Deleting a node from a lock-free singly linked list is a two-step act: (1) **logically** delete it by marking it, then (2) **physically** unlink it by CAS-ing the predecessor's `next` past it. The mark lives in the node's `next` field as an `AtomicMarkableReference`. Marking and changing the successor atomically lets a concurrent insertion detect that the node is being deleted (its `next` is marked) and back off / retry, preventing a lost-update where an insert after a node that is concurrently being removed would vanish. ## Difference from AtomicStampedReference — and the ABA nuance - **Payload:** mark = one `boolean`; stamp = a full `int` version. - **ABA coverage:** a **stamp** is meant to **monotonically increase**, so a value returning to A carries a higher stamp and the stale CAS fails — that fully exposes A→B→A. A **mark** has only two states and can **toggle back** (true→false→true), so by itself it does **not** give general ABA protection. It solves a different problem: atomically associating one logical flag with a reference. (In the linked-list algorithm the mark is monotone in practice — a deleted node is never un-deleted — which is why the bit is sufficient *there*, not because a bit defeats ABA in general.) ## When to choose which - Use **AtomicMarkableReference** when you need exactly **one boolean flag** atomically bound to a reference — most often 'this node is logically deleted' in lock-free list/set implementations. - Use **AtomicStampedReference** when you need **version-based ABA detection** — lock-free stacks/queues/free-lists where a reference can return to a prior value with different surrounding state. - Use plain **AtomicReference** when neither extra bit nor version is needed. ## Cost Like the stamped variant, the (reference, mark) pair is boxed into an immutable internal holder swapped atomically, so each value-changing update allocates a small object (with an optimization to skip allocation when nothing changes). The overhead is minor relative to the correctness guarantees.

  • Why doesn't a boolean mark fully solve the ABA problem the way a stamp does?
    Because a stamp is meant to increase monotonically, so a value returning to A always carries a higher stamp and the stale CAS fails. A mark has only two states and can toggle true→false→true, returning to a prior value, so it cannot encode 'this changed since you last looked' in general. The mark solves a different problem: binding one atomic flag to a reference.
  • Why store the deletion mark inside the node's next-pointer reference rather than a separate boolean field?
    Because deletion must atomically tie 'I am logically deleted' to the current successor so an inserter can't link after a node that is concurrently being removed. Putting the mark in the AtomicMarkableReference next field lets the algorithm CAS the (successor, mark) pair as one unit, which a separate boolean field could not guarantee atomically.

saying these in an interview costs you the question

  • Claiming AtomicMarkableReference solves the ABA problem in general — a single togglable bit does not; only a monotonic stamp does.
  • Saying the mark carries a version number — it is a single boolean, not an int.
  • Treating get(boolean[]) and isMarked() as interchangeable for snapshots — use get(boolean[]) when you need reference and mark together atomically.
  • Assuming it's interchangeable with AtomicStampedReference for lock-free stacks — those need version detection, not one flag.

context

resolving links…