14.2.13.1 Cache Coherency

Although cache-coherence protocols guarantee that a given CPU sees its own accesses in order, and that all CPUs agree on the order of modifications to a single variable contained within a single cache line, there is no guarantee that modifications to different variables will be seen in the same order by all CPUs -- although some computer systems do make some such guarantees, portable software cannot rely on them.

Figure: Split Caches
\includegraphics{advsync/SplitCache}

To see why reordering can occur, consider the two-CPU system shown in Figure [*], in which each CPU has a split cache. This system has the following properties:

  1. An odd-numbered cache line may be in cache A, cache C, in memory, or some combination of the above.
  2. An even-numbered cache line may be in cache B, cache D, in memory, or some combination of the above.
  3. While the CPU core is interrogating one of its caches,14.9 its other cache is not necessarily quiescent. This other cache may instead be responding to an invalidation request, writing back a dirty cache line, processing elements in the CPU's memory-access queue, and so on.
  4. Each cache has queues of operations that need to be applied to that cache in order to maintain the required coherence and ordering properties.
  5. These queues are not necessarily flushed by loads from or stores to cache lines affected by entries in those queues.

In short, if cache A is busy, but cache B is idle, then CPU 1's stores to odd-numbered cache lines may be delayed compared to CPU 2's stores to even-numbered cache lines. In not-so-extreme cases, CPU 2 may see CPU 1's operations out of order.

Much more detail on memory ordering in hardware and software may be found in Appendix [*].

Paul E. McKenney 2011-12-16