Relaxed Memory Model Zoo

Memory model
← Back to the map

Total Store Order TSO

2004 · Owens, Sarkar, Sewell · hardware, formal

A write goes into a per-thread FIFO store buffer before becoming globally visible. Reads can observe a thread's own buffered write before others can. Store-load reordering is the principal relaxation over SC.

Ordering relationships

Strictly weaker than
Strictly stronger than
  • Partial Store Order (PSO) — PSO additionally allows store-store reordering to different addresses.
  • ARMv8 / AArch64 Memory Model — ARMv8 allows more reorderings than TSO though it is multi-copy-atomic. The TSO ⊆ ARMv8 containment is a model-level monotonicity argument over different instruction sets, not a cited theorem, so the edge is recorded as litmus-grade (provisional): the one-sided witness does not by itself exclude incomparability.
  • RISC-V Weak Memory Ordering (RVWMO) — RVWMO is weaker than TSO: it allows store-store and load-load reorderings TSO forbids. The containment rests on the same model-level monotonicity argument as TSO → ARMv8 (RISC-V's Ztso extension makes RVWMO+TSO near-definitional), recorded as litmus-grade for consistency under the stricter standard.
  • Relaxed Memory Models: an Operational Approach (RMMOA) — Like PSO, RMMOA's hierarchical store buffers additionally permit store→store reordering to distinct addresses, which TSO forbids.
Equivalent to
  • x86-TSO — x86-TSO formalises TSO for x86; behaviourally equivalent for standard operations.
  • Buffered Memory Model (BMM) — BMM is a pragmatic TSO-style buffered model proposed as a candidate Java memory model; on the store-buffer relaxations it coincides with TSO.

References

  • Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, Magnus O. Myreen. x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors. Communications of the ACM, 2010. doi:10.1145/1785414.1785443
  • Scott Owens, Susmit Sarkar, Peter Sewell. A Better x86 Memory Model: x86-TSO (Extended Version). TPHOLs 2009, 2009. doi:10.1007/978-3-642-03359-9_24