Concurrency vs. Parallelism

Concurrency is a property of the program: multiple tasks are active and unordered. If scheduled fairly, they logically make forward progress together. Parallelism is a property of the execution: tasks are actually progressing at the same instant on different processing elements.

OpenMP threads are concurrent, which means unordered by default. Synchronization is the only mechanism available to impose ordering. Everything that follows is about what “ordering” actually means and how to get it.

More details can be found here

Memory Models

The problem

A variable can exist simultaneously in DRAM, in shared last-level cache, in each core’s private cache, and in each core’s registers – with different values in each. Hardware does not decide which copy is authoritative. A memory consistency model is the set of rules that answers “which value should a thread observe?”

What “observe” means

A thread has no clock, cannot see other threads’ instruction pointers, and cannot inspect other caches. Its only channel for learning about other threads is: a load returns a value.

So “thread 1 observed thread 0’s store” means “a load in thread 1 returned the value that store wrote.” And “thread 1 observed A before B” is inferential: the sequence of values thread 1’s loads returned is only explicable by an ordering where A preceded B.

So, the consistency herein really just about when the data or values are changed and the changes are observed over time.

Sequential consistency

SC does not mean threads run in a predictable order – different runs still interleave differently. It means there exists a single global total order of all memory operations, and every thread’s behavior is consistent with that one order. Each thread’s operations appear in that order in program order, and every load returns the value of the most recent store in that order. The order is arbitrary, but it is shared: everyone sees the same shuffled deck.

Relaxed consistency

Each thread’s operations respect its own program semantics, but different threads may observe different orders. This is what every real system chose, because enforcing SC everywhere would require synchronizing on every shared access.

Thread 0:  x = 1;   r1 = y;
Thread 1:  y = 1;   r2 = x;

Under SC, r1 == 0 && r2 == 0 is impossible: whichever store is first globally, the other thread’s load must see it. On real x86 both frequently return 0, because each core’s store buffer lets the load proceed before the store is globally visible.

Thread 0:  x = 1;
Thread 1:  y = 1;
Thread 2:  r1 = x;  r2 = y;     // sees 1, 0 → concludes x was written first
Thread 3:  r3 = y;  r4 = x;     // sees 1, 0 → concludes y was written first

What relaxed consistency still guarantees

“Relaxed” describes what was given up relative to SC — a total order — not that ordering was abandoned. What you get is a partial order instead of a total order, and you decide which pairs are ordered by placing synchronization.

Guaranteed unconditionally, even with zero synchronization: a thread always sees its own prior writes, and single-threaded semantics are fully preserved. Coherence holds — for any single location, all writes form a total order every thread agrees on, so you may read stale values but never out-of-order ones for that location. Loads return values that were actually written, not invented ones. Address dependencies are respected. And once you establish a happens-before edge, its guarantee is absolute.

What you lose: no global order across different locations, no bound on visibility latency for ordinary accesses (a store may formally never become visible, which is why the spin loop hangs), and permission to reorder across locations.

Useful summary: relaxed consistency is roughly “SC per variable, nothing across variables.” Every failure mode in these slides involves two different variables.

Happens-before

Happens-before is not primitive. It is constructed from two simpler relations, and neither is useful alone.

Sequenced-before: program order within a single thread. Free, automatic, private to that thread. Plain English: “this line comes before that line, in the same thread.”

Synchronizes-with: a single edge connecting one operation in one thread to one operation in another. The only way information crosses between threads. Plain English: “this exact moment in one thread is connected to this exact moment in another.”

Happens-before: the transitive closure of the two combined. Plain English: “whatever A did, B is guaranteed to see.”

Terminology Aside: “Consistency” Elsewhere

Worth knowing, since the word is badly overloaded.

Coherence vs. consistency. Coherence is the per-location guarantee, provided by the cache protocol in hardware. Consistency is the cross-location question — how operations on different addresses order relative to each other. Coherence is necessary but nowhere near sufficient.

Distributed systems consistency is the same subject. Linearizability is essentially SC plus a real-time constraint; causal consistency corresponds closely to release/acquire. This isn’t coincidence — a multicore machine is a distributed system: independent agents, private replicas, a network with latency, trying to agree on shared state. Cache coherence is a replication protocol; store buffers are write-behind caches.

Database ACID consistency is unrelated. The C in ACID means transactions preserve application-level invariants (foreign keys, check constraints, “debits equal credits”). No ordering content at all, and largely the application’s responsibility. It’s widely considered the weakest letter; Gray’s original 1981 formulation folded isolation into it, and Härder and Reuter separated them in 1983.

ACID’s ordering notion is Isolation, not Consistency. Serializability is structurally the same statement as sequential consistency. Weaker isolation levels — read committed, repeatable read, snapshot isolation — are relaxed models permitting specific anomalies, just as weak memory models permit specific reorderings. Strict serializability corresponds to linearizability.

CAP’s C is not ACID’s C. CAP consistency is linearizability — pure ordering and visibility, the memory-model notion. A system can be “eventually consistent” in the CAP sense while enforcing every foreign key you declared.

The Most Important Concepts

Threads are unordered by default, and synchronization is the only way to create order.

A memory model exists to answer “which value should a thread see?”, because shared memory is many replicas rather than one thing.

Relaxed consistency provides no global order — only the partial order you build.

Happens-before is assembled from sequenced-before plus synchronizes-with, and means guaranteed visible, not earlier in time.

Synchronization has two separable parts: the synchronizes-with edge, and the memory order determining how much work crosses it. You need both.

Atomics are the underlying primitive, not just a fast mutex.

Data-race-free programs behave as if sequentially consistent — which is why none of this normally intrudes on your work.

Correctness and performance are separate problems, and the cheapest synchronization is none.

In one sentence: memory is replicated and unordered; ordering is something you construct with paired synchronization operations; and if you construct enough of it to eliminate races, you can safely forget the whole model exists.