Sequential Consistency

Consider this deceptively simple code, running on two threads:

Thread 1:

X = 1;
print(Y);

Thread 2:

Y = 1;
print(X);

Both X and Y start at 0. What outputs are possible?

Most developers would immediately answer:

• (1, 0) — Thread 1 runs completely first
• (0, 1) — Thread 2 runs completely first
• (1, 1) — Both writes happen before both reads

But surely (0, 0) is impossible? After all, one of the writes must happen before both reads complete.

On modern hardware, (0, 0) can actually occur.

If this surprises you—or if you don't immediately understand why—then you need to understand memory models and, specifically, sequential consistency.

Sequential consistency is a memory model formalized by Leslie Lamport in 1979. It defines what guarantees a system provides about the ordering of memory operations across multiple threads or processors.

Lamport's Definition:

A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.

Let's unpack this carefully—it contains two distinct requirements:

Requirement 1: Global Sequential Order

There must exist some total ordering of all memory operations from all processors such that the observed results are consistent with that ordering. In other words, you could take all the memory operations from every thread and arrange them in a single, global sequence where each operation's results make sense given the operations before it.

Requirement 2: Program Order Preserved

Within this global sequence, the operations from any single processor appear in the order that processor's program specifies. Thread 1's operations maintain their relative order; Thread 2's operations maintain their relative order. The interleaving between threads may vary, but within-thread order is preserved.

Example: Sequential consistency in action

Returning to our opening example with X=0, Y=0 initially:

Thread 1: X = 1; print(Y); Thread 2: Y = 1; print(X);

Under sequential consistency, we can form these possible global orderings:

Ordering A:

1. Thread 1: X = 1
2. Thread 1: print(Y) → outputs 0
3. Thread 2: Y = 1
4. Thread 2: print(X) → outputs 1 Result: (0, 1)

Ordering B:

1. Thread 2: Y = 1
2. Thread 2: print(X) → outputs 0
3. Thread 1: X = 1
4. Thread 1: print(Y) → outputs 1 Result: (1, 0)

Ordering C:

1. Thread 1: X = 1
2. Thread 2: Y = 1
3. Thread 1: print(Y) → outputs 1
4. Thread 2: print(X) → outputs 1 Result: (1, 1)

There is no valid sequential ordering where both prints occur before both writes (that would violate program order within each thread). Therefore, (0, 0) is impossible under sequential consistency.

Yet, as stated earlier, modern hardware can produce (0, 0). This means modern hardware does not provide sequential consistency by default.

Sequential consistency provides several properties that make reasoning about concurrent programs tractable:

1. Deterministic reasoning about interleavings

With sequential consistency, you can analyze a concurrent program by considering all possible interleavings of operations from different threads. While the number of interleavings may be large, they're finite and well-defined. Each interleaving produces a deterministic result.

2. Atomicity of individual operations

Under sequential consistency, each memory operation (read or write) appears to happen atomically—instantaneously, without overlap with other operations. An operation is either fully completed and visible to all threads, or it hasn't happened yet.

3. Causal reasoning

If Thread A writes a value and Thread B reads that value, then Thread B can reason that Thread A's write (and everything Thread A did before that write) has already happened. This enables building synchronization on top of shared memory.

4. Simple mental model

'Operations happen one at a time, in some order' is easy to understand and verify. You can trace through code manually, considering different interleavings.

If sequential consistency is so intuitive and useful, why don't modern processors provide it? The answer lies in performance optimization.

Modern CPUs achieve their remarkable speed through aggressive optimization techniques that fundamentally conflict with sequential consistency:

1. Store Buffers

When a CPU writes to memory, it doesn't immediately update main memory. Instead, the write goes into a store buffer—a small, fast queue local to the processor core. This allows the CPU to continue executing without waiting for the slow write to complete.

Problem: The write in the store buffer is visible to the local core but not yet visible to other cores. This breaks sequential consistency because other threads may read stale values.

2. Cache Hierarchies

Modern CPUs have multiple levels of cache (L1, L2, L3). Each core typically has private L1 and L2 caches. When core A writes a value, it may update its local cache without immediately propagating the change to core B's cache.

Problem: Different cores may temporarily have different views of the same memory location.

3. Out-of-Order Execution

CPUs reorder instructions for efficiency. If instruction A and instruction B are independent (no data dependency), the CPU may execute B before A even though A appears first in the program.

Problem: This can change the order in which memory operations become visible to other threads.

4. Compiler Reordering

Before code even reaches the CPU, compilers may reorder instructions. A compiler optimizing for a single-threaded view might move a write after a read if it seems safe—but this can break multi-threaded invariants.

5. Speculative Execution

CPUs may speculatively execute instructions ahead of time, later discarding results if speculation was wrong. This can affect memory operation ordering.

The performance rationale:

These optimizations are essential for modern CPU performance:

• Store buffers hide memory latency (writing to a buffer takes ~1 cycle; writing to memory takes ~100+ cycles)
• Caches reduce memory access from ~100 cycles to ~1-10 cycles
• Out-of-order execution keeps all CPU execution units busy instead of stalling
• Compiler reordering enables vast optimization opportunities

Enforcing sequential consistency would require:

• Flushing store buffers after every write
• Invalidating caches immediately across all cores
• Preventing instruction reordering around memory operations

This would devastate performance—potentially slowing CPUs by 10× or more for memory-intensive code.

Real hardware implements weaker (more relaxed) memory models that allow more reordering than sequential consistency. Different processor architectures have different models:

x86/x64: Total Store Order (TSO)

Intel and AMD processors provide TSO, which is fairly close to sequential consistency:

• Reads are never reordered with other reads
• Writes are never reordered with other writes
• Writes are never reordered with older reads
• But: Reads may be reordered with older writes (to different locations)

This is why our (0, 0) example can occur on x86: each thread's read can be reordered before its write, observing the other thread's initial value.

ARM/PowerPC: Relaxed Memory Models

ARM and PowerPC provide much weaker ordering:

• Reads may be reordered with other reads
• Writes may be reordered with other writes
• Reads and writes may be reordered with each other
• Dependent operations may not even execute in order

These architectures require explicit memory barriers (fences) to enforce any ordering at all.

What the (0, 0) result means:

Returning to our example:

// Thread 1       // Thread 2
X = 1;            Y = 1;
print(Y);         print(X);

Even on x86 (which allows read/write reordering to different locations), the hardware may:

1. Thread 1: Put X = 1 in store buffer (not visible yet)
2. Thread 2: Put Y = 1 in store buffer (not visible yet)
3. Thread 1: Read Y from memory → 0 (Thread 2's write still in buffer)
4. Thread 2: Read X from memory → 0 (Thread 1's write still in buffer)
5. Store buffers drain: X = 1, Y = 1 now visible (too late)

Result: (0, 0) — impossible under sequential consistency, but perfectly valid on real hardware.

Since hardware doesn't provide sequential consistency by default, programmers must explicitly request ordering where needed. This is done through memory barriers (also called fences).

What is a memory barrier?

A memory barrier is a special instruction that constrains the reordering of memory operations around it. It doesn't access memory itself—it's a synchronization point that affects how other memory operations are ordered.

Types of memory barriers:

1. Full Barrier (mfence on x86, dmb on ARM)

• No memory operations may be reordered across the barrier
• All operations before the barrier complete before any operation after it begins
• Expensive: may stall the CPU for many cycles

2. Store Barrier (sfence on x86, dmb st on ARM)

• Ensures all prior stores complete before subsequent stores
• Doesn't constrain reads

3. Load Barrier (lfence on x86, dmb ld on ARM)

• Ensures all prior loads complete before subsequent loads
• Doesn't constrain writes

4. Acquire Barrier

• Prevents subsequent operations from being reordered before the barrier
• Used when 'acquiring' a resource (e.g., taking a lock)

5. Release Barrier

• Prevents prior operations from being reordered after the barrier
• Used when 'releasing' a resource (e.g., releasing a lock)

Since hardware memory models vary by architecture, programming languages define their own memory models to provide portable semantics. These language models abstract away hardware differences.

C11/C++11 Memory Model:

C and C++ define a memory model with explicit ordering options:

• memory_order_seq_cst — Sequential consistency. Most restrictive, safest.
• memory_order_acquire — Acquire semantics (for reads). Subsequent operations can't move before.
• memory_order_release — Release semantics (for writes). Prior operations can't move after.
• memory_order_acq_rel — Both acquire and release (for read-modify-write).
• memory_order_relaxed — No ordering guarantees. Maximum performance, maximum danger.

Java Memory Model:

Java defines a memory model where:

• All volatile reads/writes are sequentially consistent
• Non-volatile accesses may be reordered
• Proper synchronization (locks, volatile, final) creates happens-before relationships

Go Memory Model:

Go defines happens-before relationships through:

• Goroutine creation
• Channel sends and receives
• sync package primitives (Mutex, WaitGroup, etc.)

Without these, no ordering is guaranteed between goroutines.

When reasoning about memory visibility in weak memory models, the concept of happens-before is essential. It defines when one operation is guaranteed to see the effects of another.

Definition:

Operation A happens-before operation B if A's effects are guaranteed to be visible to B.

This doesn't necessarily mean A completes before B in real time—it means the system guarantees B will observe A's effects.

Happens-before is established by:

1. Program order — Within a single thread, earlier operations happen-before later operations

2. Synchronization — Release operations happen-before acquire operations that observe them:

   • Mutex unlock (release) happens-before subsequent lock (acquire)
   • Volatile/atomic write (release) happens-before read that sees the written value (acquire)
   • Thread creation happens-before the new thread's first operation
   • Thread termination happens-before join() returns

3. Transitivity — If A happens-before B and B happens-before C, then A happens-before C