Total Store Ordering (TSO)

Total Store Ordering (TSO) is a concept that comes from the realm of computer architecture and specifically deals with memory ordering in multiprocessor systems (systems with multiple CPUs or cores). It defines how reads and writes to shared memory locations are seen by different processors in a system.

Breaking it Down

To understand TSO, we need to consider the concept of memory ordering. Memory ordering determines the sequence in which read and write operations on memory are observed by different processors. When multiple processors are accessing the same memory, if one processor writes to a memory location, how and when other processors can see that change depends on the memory model (e.g., TSO).

In a multiprocessor system, each processor may have its own cache, and the memory operations (like reading or writing to a shared variable) might not immediately be visible to other processors due to these caches. Different systems use different models to decide how and when memory operations are visible to other processors.

Get Cyber Gee’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

TSO is one such model used primarily in x86 architecture (the Intel and AMD CPUs, for example).

Key Points of TSO

1. Writes are visible in program order: In TSO, writes to memory by a processor are guaranteed to be visible to other processors in the order they were issued by that processor. In simpler terms, if Processor A writes to X and then writes to Y, any other processor that reads X or Y will see these writes in the same order: first X, then Y.
2. Reads can be out of order: While writes are seen in order, reads can be reordered. This means a processor might issue a read and get a stale value from its cache, not the most recent one written by another processor. However, the important thing is that a processor will never see a value from a write that happens after the read in program order, even if the read occurs out of order with respect to other operations.
3. Relaxed rules for reads: A processor might read a value from memory that doesn’t reflect the latest writes made by other processors, especially if the reads are not closely synchronized. But there’s a guarantee that no processor will see a write before the processor actually performs the write operation.
4. No full global ordering: TSO doesn’t guarantee that all operations will be seen in the same order across all processors (this would be much stricter and slower). Instead, it provides a compromise between performance and correctness. Only writes are observed in program order, but reads can be slightly out of order across different processors.

TSO in Comparison to Other Memory Models

• Total Store Order is more relaxed than stricter memory models like Sequential Consistency (SC), which would guarantee that all processors see every operation in the exact same order. TSO is designed to allow some flexibility for performance while still maintaining a reasonable level of correctness and predictability.
• In contrast, Relaxed Consistency models (like Release Consistency or Weak Consistency) allow even more freedom in how reads and writes can be reordered across processors, but this can lead to more complicated reasoning about program behavior.

Why Does TSO Matter?

When developing software that runs on multi-core processors, especially in parallel computing environments, developers need to be mindful of how memory is accessed. TSO affects how they write synchronization primitives (like mutexes, locks, or barriers) to make sure the program behaves correctly when multiple processors are reading from and writing to shared data.