Let's now look at this from the perspective of a cache line's worth
of data, initially residing in memory at address 0,
as it travels through the various single-line direct-mapped caches
in a four-CPU system.
Table
shows this flow of data, with the first column showing the sequence
of operations, the second the CPU performing the operation,
the third the operation being performed, the next four the state
of each CPU's cache line (memory address followed by MESI state),
and the final two columns whether the corresponding memory contents
are up to date (``V'') or not (``I'').
Initially, the CPU cache lines in which the data would reside are in the ``invalid'' state, and the data is valid in memory. When CPU 0 loads the data at address 0, it enters the ``shared'' state in CPU 0's cache, and is still valid in memory. CPU 3 also loads the data at address 0, so that it is in the ``shared'' state in both CPUs' caches, and is still valid in memory. Next CPU 0 loads some other cache line (at address 8), which forces the data at address 0 out of its cache via an invalidation, replacing it with the data at address 8. CPU 2 now does a load from address 0, but this CPU realizes that it will soon need to store to it, and so it uses a ``read invalidate'' message in order to gain an exclusive copy, invalidating it from CPU 3's cache (though the copy in memory remains up to date). Next CPU 2 does its anticipated store, changing the state to ``modified''. The copy of the data in memory is now out of date. CPU 1 does an atomic increment, using a ``read invalidate'' to snoop the data from CPU 2's cache and invalidate it, so that the copy in CPU 1's cache is in the ``modified'' state (and the copy in memory remains out of date). Finally, CPU 1 reads the cache line at address 8, which uses a ``writeback'' message to push address 0's data back out to memory.
Note that we end with data in some of the CPU's caches.
Quick Quiz C.5: What sequence of operations would put the CPUs' caches all back into the ``invalid'' state? End Quick Quiz
Paul E. McKenney 2011-12-16