Understand Memory Barriers and Memory Ordering

Topic Overview

Ordering Across Cores

CPUs and compilers reorder memory operations for speed. Memory barriers (fences) restrict reordering so other cores observe writes in intended order. Lock implementations depend on acquire/release semantics.

cCopy
Loading…

Architecture Fence Instructions

• x86: MFENCE, SFENCE, LFENCE; locked ops imply strong ordering
• ARM: DMB, DSB, ISB
• C11: memory_order_seq_cst maps to fences on weak ISAs

For this exercise, you will demonstrate a litmus test where missing barriers lets a second thread observe ready==1 but stale data. This task asks you to fix ordering with atomics, matching what the Linux kernel documents for spinlock release.

Working Through the Exercise

Keep the relevant datasheet, ISA manual, or architecture textbook chapter open while you implement. When your output disagrees with the reference trace on the same program, the bug is usually a mis-decoded opcode, a stale register read, or a flag bit left unchanged after arithmetic.

• Trace first: walk one failing input by hand before changing random lines
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

For this exercise, you will use those habits while implementing the requirement in the starter code. Microarchitectural product names change across CPU generations, but the control ideas (fetch, bypass, cache lines, vector lanes) stay stable enough to debug from first principles.

Your Task

Run litmus tests for memory ordering. Two threads each execute a few loads and stores, and a memory model decides which interleavings, and which reorderings, are allowed. Enumerate every execution and report which results can be observed. You'll see the classic outcomes: store-buffer (r1 = r2 = 0) and message-passing (reading the flag but not the data), and how a barrier removes them.

Input

cCopy
Loading…

Operations, where X, Y are shared variables (initially 0) and rN is thread-local:

Models

Each thread's operations are considered in program order, except that a thread may locally reorder two adjacent operations when the model allows it and neither is a fence (a fence may never move, and nothing may move across one):

• sc (sequentially consistent): no reordering.
• tso (x86): a store followed by a load of a different variable may swap. Nothing else moves.
• relaxed (ARM/Power): any two adjacent operations may swap, unless the later one depends on the earlier: they use the same variable, or the second reads a register the first wrote.

Enumerate every reordered program per thread (apply swaps repeatedly until no new orders appear), then every interleaving of the two threads' sequences. Execute each on a single shared memory.

Output

Per test:

cCopy
Loading…

List every combination of the final register values, in ascending order (registers sorted by name, values ascending, first register most significant), over the value range 0..max, where max is the largest value stored anywhere in the test. Registers are the ones loaded into, sorted by name. Print a blank line between tests.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Under sc the same test forbids r1=0 r2=0: no interleaving produces it, and no reordering is allowed. Under tso each thread may float its load ahead of its store, and both read 0.

Requirements

1. Generate each thread's allowed orders by repeated adjacent swaps, deduplicating; then enumerate interleavings recursively.
2. One interpreter executes a full interleaving against a fresh memory.

Hidden tests cover message passing (store data; store flag against load flag; load data) under relaxed, the same test with fences, two threads accessing one location with three possible values, and the load-buffer test.