Some processor architectures provide load-linked and store-conditional instructions instead of a single compare-and-swap. Explain how that pair works, how it differs semantically from compare-and-swap, and what a programmer must account for when code runs on such hardware.

middlenice to knowfreq 22%

answer

LL reserves, SC stores only if reservation intact
detects any write, not just a changed value
free ABA resistance on the reserved location
spurious failure: context switch, line sharing, eviction
loop mandatory, body tiny, no nesting

basics

~20 s

Load-linked reads a location and registers a reservation on it; store-conditional writes only if nothing has touched that location since. It detects any intervening write rather than comparing values, so it is naturally immune to a value changing and changing back. It can also fail spuriously, so it must always sit in a retry loop.

solid answer

~1 min

Two semantic differences from compare-and-swap matter.

It watches the location, not the value. Compare-and-swap asks "is this equal to what I expected?", which a value that left and came back satisfies — the ABA problem. Store-conditional asks "has this been written at all?", so a value that changed and changed back still breaks the reservation. LL/SC is therefore naturally ABA-resistant at that granularity, without version tags.

It can fail spuriously. A context switch, an interrupt, a cache-line eviction, or a write to an unrelated variable on the same line can clear the reservation even though nothing you care about changed. Consequently a single attempt proves nothing and the loop is mandatory; the loop body must also be short and free of memory accesses that could themselves clear the reservation.

Compare-and-swap on such machines is simply implemented as an LL/SC loop, which is why portable code is written in terms of compare-and-swap and told to expect spurious failure.

Load-linked (LL) reads a word and marks a reservation, usually on the containing cache line. Store-conditional (SC) attempts to write that word and succeeds only if the reservation is still intact; otherwise it writes nothing and reports failure. The programmer wraps the pair in a retry loop. Two semantic differences from compare-and-swap matter. **It watches the location, not the value.** Compare-and-swap asks "is this equal to what I expected?", which a value that left and came back satisfies — the ABA problem. Store-conditional asks "has this been written at all?", so a value that changed and changed back still breaks the reservation. LL/SC is therefore naturally ABA-resistant at that granularity, without version tags. **It can fail spuriously.** A context switch, an interrupt, a cache-line eviction, or a write to an unrelated variable on the same line can clear the reservation even though nothing you care about changed. Consequently a single attempt proves nothing and the loop is mandatory; the loop body must also be short and free of memory accesses that could themselves clear the reservation. Compare-and-swap on such machines is simply implemented as an LL/SC loop, which is why portable code is written in terms of compare-and-swap and told to expect spurious failure.

code

text · 6 lines

text

CAS(addr, expected, new) -> bool:
  loop:
    v = LL(addr)
    if v != expected: return false      # genuine mismatch
    if SC(addr, new): return true       # installed
    # SC failed: real conflict OR spurious -> retry the whole sequence

go deeper

for a junior

Know the shape: the load registers a reservation, the store only lands if the reservation survives, and it lives inside a retry loop.

for a middle

Contrast detecting any write against comparing a value, and explain that spurious failure makes the loop mandatory.

for a senior

Connect reservation granularity to cache lines and unrelated-variable interference, and explain weak versus strong compare-and-swap in portable atomics.

for a principal

Discuss what portability guarantees you may lean on: write algorithms correct under plain compare-and-swap semantics, and treat any architecture-specific ABA immunity as a bonus, not a design assumption.

The mechanism

Load-linked/store-conditional (also called load-reserved/store-conditional) splits an atomic read-modify-write into two instructions with hardware state in between.

loop:
  old = LL(addr)          # read + set a reservation on addr's line
  new = f(old)            # compute in registers
  if SC(addr, new): break # store only if the reservation still holds
  # else retry

The reservation is tracked by the cache-coherence hardware: when another core takes the line for writing, the local reservation is cleared. Store-conditional checks the reservation, and if it is gone, performs no write and reports failure. Crucially, no lock is held between LL and SC — if the thread is preempted there, nothing is stuck; the SC simply fails later and the loop retries.

This design is common on load-store RISC architectures, where a single instruction that both reads and writes memory does not fit the pipeline model. Machines in that family implement compare-and-swap in software as an LL/SC loop with an explicit comparison inside.

Difference one: change detection versus value comparison

This is the semantically interesting part. Compare-and-swap tests a value: it succeeds if the current contents equal the expected contents, and cannot distinguish "never modified" from "modified and restored". That gap is the ABA problem, and the standard remedy is a monotonic version stamp packed alongside the value.

Store-conditional tests an event: it succeeds only if no write occurred to the reserved location since the load. A value that went from A to B and back to A still clears the reservation, so the store fails and the algorithm re-reads. LL/SC therefore gives ABA immunity for the single reserved location for free.

Two caveats stop this from being a complete ABA answer. First, the immunity covers only the reserved word or line — a lock-free stack still dereferences a node pointer between the load and the store, so unsafe reclamation of that node remains a separate problem. Second, code is usually written against a portable compare-and-swap abstraction, which erases the extra guarantee; you cannot rely on it unless you are targeting the architecture directly.

Difference two: spurious failure

Store-conditional may fail even when the reserved word was untouched. Common causes:

Context switch or interrupt between the LL and the SC — many implementations clear reservations to keep them from surviving a thread swap.
Granularity. The reservation typically covers a whole cache line, not a word, so a write to an unrelated variable sharing that line clears it. This is a close cousin of false sharing and has the same fix: separate hot variables onto their own lines.
Cache-line eviction for capacity or coherence reasons.
Intervening memory accesses in the loop body, which on some implementations may clear the reservation themselves.

The practical consequences are strict:

Never write a single attempt. "Try once and report failure" is not a correct use; it can report failure when nothing conflicted.
Keep the body tiny — register-only computation, no calls, no unrelated loads or stores, no allocation.
Do not nest reservations or interleave two LL/SC sequences; there is typically only one reservation per core.

This also explains why portable atomics interfaces expose both a "weak" compare-and-swap that may fail spuriously (cheap, intended for use inside a loop you already have) and a "strong" variant that internally loops to hide spurious failures (for use where a single call must be conclusive).

Why programmers should still think in compare-and-swap

Algorithms are described and reasoned about in terms of compare-and-swap because it is the portable, universal primitive: it composes into the read-compute-install pattern on every platform, and it is directly available on architectures that provide a single atomic instruction. LL/SC is the underlying mechanism on some machines, and knowing about it explains three otherwise puzzling facts — why retry loops are mandatory rather than merely defensive, why 'weak' compare-and-swap exists in modern atomics APIs, and why a variable sharing a cache line with an unrelated hot variable can slow down atomic updates that logically never conflict.

In an interview, the ideal answer names the reservation mechanism, contrasts event detection with value comparison (with ABA as the payoff), and states spurious failure as the constraint the programmer must obey.

## The mechanism Load-linked/store-conditional (also called load-reserved/store-conditional) splits an atomic read-modify-write into two instructions with hardware state in between. ``` loop: old = LL(addr) # read + set a reservation on addr's line new = f(old) # compute in registers if SC(addr, new): break # store only if the reservation still holds # else retry ``` The reservation is tracked by the cache-coherence hardware: when another core takes the line for writing, the local reservation is cleared. Store-conditional checks the reservation, and if it is gone, performs no write and reports failure. Crucially, no lock is held between LL and SC — if the thread is preempted there, nothing is stuck; the SC simply fails later and the loop retries. This design is common on load-store RISC architectures, where a single instruction that both reads and writes memory does not fit the pipeline model. Machines in that family implement compare-and-swap in software as an LL/SC loop with an explicit comparison inside. ## Difference one: change detection versus value comparison This is the semantically interesting part. Compare-and-swap tests a **value**: it succeeds if the current contents equal the expected contents, and cannot distinguish "never modified" from "modified and restored". That gap is the ABA problem, and the standard remedy is a monotonic version stamp packed alongside the value. Store-conditional tests an **event**: it succeeds only if no write occurred to the reserved location since the load. A value that went from A to B and back to A still clears the reservation, so the store fails and the algorithm re-reads. LL/SC therefore gives ABA immunity for the single reserved location for free. Two caveats stop this from being a complete ABA answer. First, the immunity covers only the reserved word or line — a lock-free stack still dereferences a node pointer *between* the load and the store, so unsafe reclamation of that node remains a separate problem. Second, code is usually written against a portable compare-and-swap abstraction, which erases the extra guarantee; you cannot rely on it unless you are targeting the architecture directly. ## Difference two: spurious failure Store-conditional may fail even when the reserved word was untouched. Common causes: - **Context switch or interrupt** between the LL and the SC — many implementations clear reservations to keep them from surviving a thread swap. - **Granularity.** The reservation typically covers a whole cache line, not a word, so a write to an unrelated variable sharing that line clears it. This is a close cousin of false sharing and has the same fix: separate hot variables onto their own lines. - **Cache-line eviction** for capacity or coherence reasons. - **Intervening memory accesses in the loop body**, which on some implementations may clear the reservation themselves. The practical consequences are strict: 1. **Never write a single attempt.** "Try once and report failure" is not a correct use; it can report failure when nothing conflicted. 2. **Keep the body tiny** — register-only computation, no calls, no unrelated loads or stores, no allocation. 3. **Do not nest** reservations or interleave two LL/SC sequences; there is typically only one reservation per core. This also explains why portable atomics interfaces expose both a "weak" compare-and-swap that may fail spuriously (cheap, intended for use inside a loop you already have) and a "strong" variant that internally loops to hide spurious failures (for use where a single call must be conclusive). ## Why programmers should still think in compare-and-swap Algorithms are described and reasoned about in terms of compare-and-swap because it is the portable, universal primitive: it composes into the read-compute-install pattern on every platform, and it is directly available on architectures that provide a single atomic instruction. LL/SC is the underlying mechanism on some machines, and knowing about it explains three otherwise puzzling facts — why retry loops are mandatory rather than merely defensive, why 'weak' compare-and-swap exists in modern atomics APIs, and why a variable sharing a cache line with an unrelated hot variable can slow down atomic updates that logically never conflict. In an interview, the ideal answer names the reservation mechanism, contrasts event detection with value comparison (with ABA as the payoff), and states spurious failure as the constraint the programmer must obey.

If store-conditional is naturally ABA-resistant, why do lock-free algorithms on such hardware still need version stamps or reclamation schemes?
The reservation protects only the single reserved location for the window between the load and the store. A lock-free stack pop also dereferences the node it read to fetch a next pointer, and that node may have been removed and freed in the meantime — a hazard the reservation says nothing about. Portable code also targets a compare-and-swap abstraction that hides the guarantee, so algorithms are written to be correct without it.
What does the distinction between weak and strong compare-and-swap in a portable atomics interface correspond to?
Weak compare-and-swap is allowed to fail spuriously and maps directly onto a single load-linked/store-conditional attempt, which is the cheapest form and is fine when the call already sits inside a retry loop. Strong compare-and-swap must only fail when the value genuinely differs, so on such hardware it wraps an internal loop to absorb spurious failures. Use weak inside loops and strong where a single conclusive attempt is required.

Putting a tamper seal on a document instead of memorising its text. Compare-and-swap re-reads the text and can be fooled by an edit that was undone; the seal is broken by any handling at all.

saying these in an interview costs you the question

Believing store-conditional fails only when the value actually changed
Writing a single load-linked/store-conditional attempt with no retry loop
Placing function calls, allocation, or unrelated memory accesses between the load and the store
Claiming load-linked/store-conditional makes reclamation and ABA concerns disappear entirely
Thinking the pair holds a lock between the two instructions

Some processor architectures provide load-linked and store-conditional instructions instead of a single compare-and-swap. Explain how that pair works, how it differs semantically from compare-and-swap, and what a programmer must account for when code runs on such hardware.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The mechanism

Difference one: change detection versus value comparison

Difference two: spurious failure

Why programmers should still think in compare-and-swap

▾common follow-ups2 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics4 topics

The mechanism

Difference one: change detection versus value comparison

Difference two: spurious failure

Why programmers should still think in compare-and-swap

answer

go deeper

context