Editing Cache coherence (section)

==Definition==
Coherence defines the behavior of reads and writes to a single address location.<ref name=":0" />

In a multiprocessor system, consider that more than one processor has cached a copy of the memory location X. The following conditions are necessary to achieve cache coherence:<ref name=":3">{{Cite book|title=Computer Organization and Design - 4th Edition|last=Patterson and Hennessy|isbn=978-0-12-374493-7}}</ref>
# In a read made by a processor P to a location X that follows a write by the same processor P to X, with no writes to X by another processor occurring between the write and the read instructions made by P, X must always return the value written by P.
# In a read made by a processor P1 to location X that follows a write by another processor P2 to X, with no other writes to X made by any processor occurring between the two accesses and with the read and write being sufficiently separated, X must always return the value written by P2. This condition defines the concept of coherent view of memory. Propagating the writes to the shared memory location ensures that all the caches have a coherent view of the memory. If processor P1 reads the old value of X, even after the write by P2, we can say that the memory is incoherent.
The above conditions satisfy the Write Propagation criteria required for cache coherence. However, they are not sufficient as they do not satisfy the Transaction Serialization condition. To illustrate this better, consider the following example:

A multi-processor system consists of four processors - P1, P2, P3 and P4, all containing cached copies of a shared variable ''S'' whose initial value is 0. Processor P1 changes the value of ''S'' (in its cached copy) to 10 following which processor P2 changes the value of ''S'' in its own cached copy to 20. If we ensure only write propagation, then P3 and P4 will certainly see the changes made to ''S'' by P1 and P2. However, P3 may see the change made by P1 after seeing the change made by P2 and hence return 10 on a read to ''S''. P4 on the other hand may see changes made by P1 and P2 in the order in which they are made and hence return 20 on a read to ''S''. The processors P3 and P4 now have an incoherent view of the memory.

Therefore, in order to satisfy Transaction Serialization, and hence achieve Cache Coherence, the following condition along with the previous two mentioned in this section must be met:
* Writes to the same location must be sequenced. In other words, if location X received two different values A and B, in this order, from any two processors, the processors can never read location X as B and then read it as A. The location X must be seen with values A and B in that order.<ref>Neupane, Mahesh (April 16, 2004). [https://web.archive.org/web/20100620091706/http://cse.csusb.edu/schubert/tutorials/csci610/w04/MN_Cache_Coherence.pdf "Cache Coherence"] (PDF). Archived from [http://cse.csusb.edu/schubert/tutorials/csci610/w04/MN_Cache_Coherence.pdf the original] (PDF) on 20 June 2010.</ref>
The alternative definition of a coherent system is via the definition of [[sequential consistency]] memory model: "the cache coherent system must appear to execute all threads’ loads and stores to a ''single'' memory location in a total order that respects the program order of each thread".<ref name=":2" /> Thus, the only difference between the cache coherent system and sequentially consistent system is in the number of address locations the definition talks about (single memory location for a cache coherent system, and all memory locations for a sequentially consistent system).

Another definition is: "a multiprocessor is cache consistent if all writes to the same memory location are performed in some sequential order".<ref>{{Cite journal|last1=Steinke|first1=Robert C.|last2=Nutt|first2=Gary J.|date=2004-09-01|title=A Unified Theory of Shared Memory Consistency|journal=J. ACM|volume=51|issue=5|pages=800–849|doi=10.1145/1017460.1017464|issn=0004-5411|arxiv=cs/0208027|s2cid=3206071}}</ref>

Rarely,  but especially in algorithms, coherence can instead refer to the [[locality of reference]].
Multiple copies of the same data can exist in different cache simultaneously and if processors are allowed to update their own copies freely, an inconsistent view of memory can result.