In cache coherency

Cache coherency

In computing, cache coherence refers to the consistency of data stored in local caches of a shared resource.When clients in a system maintain caches of a common memory resource, problems may arise with inconsistent data. This is particularly true of CPUs in a multiprocessing system...

 protocol literature, Write-Once was the first write-invalidate protocol defined. It has the optimization of executing write-update on the first write and a write-invalidate on all subsequent writes, reducing the overall bus traffic in consecutive writes to the computer memory

Computer storage

Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....

. It was first described by James R. Goodman

James R. Goodman

James Richard "Jim" Goodman is a professor of computer science at the University of Auckland in Auckland, New Zealand, and emeritus professor at the University of Wisconsin–Madison.-Education and research:...

 in http://portal.acm.org/citation.cfm?id=800046.801647 (1983). Cache coherence protocols are an important issue in Symmetric multiprocessing

Symmetric multiprocessing

In computing, symmetric multiprocessing involves a multiprocessor computer hardware architecture where two or more identical processors are connected to a single shared main memory and are controlled by a single OS instance. Most common multiprocessor systems today use an SMP architecture...

 systems, where each CPU

Central processing unit

The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...

 maintains a Cache

Cache

In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...

 of the memory.

States

In this protocol, each block in the local cache is in one of these four states:

• Invalid: This block has an incoherent copy of the memory.
• Valid: This block has a coherent copy of the memory. The data may be possibly shared, but its content is not modified.
• Reserved: The block is the only copy of the memory, but it is still coherent. No write-back is needed if the block is replaced.
• Dirty: The block is the only copy of the memory and it is incoherent. This copy was written one or more times. This is the only state that generates a write-back when the block is replaced in the cache.

These states have exactly the same meanings as the four states of the MESI protocol

MESI protocol

The MESI protocol is a widely used cache coherency and memory coherence protocol. It is the most common protocol which supports write-back cache...

 (they are simply listed in reverse order), but this is a simplified form of it that avoids the Read for Ownership operation. Instead, all invalidation is done by writes to main memory.

For any given pair of caches, the permitted states of a given cache line are as follows (abbreviated in the order above):

	I	V	R	D
I
V
R
D

Transitions

The protocol follows some transition rules for each event:

• Read hit: The information is supplied by the current cache. No state change.
• Read miss: The data is read from main memory. The read is snooped
  Bus sniffing
  Bus sniffing or Bus snooping is a technique used in distributed shared memory systems and multiprocessors to achieve cache coherence. Although there is one main memory, there are several caches , and unless preventative steps are taken, the same memory location may be loaded into two caches, and...
  
  by other caches; if any of them have the line in the Dirty state, the read is interrupted long enough to write the data back to memory before it is allowed to continue. Any copies in the Dirty or Reserved states are set to the Valid state.
• Write hit: If the information in the cache is in Dirty or Reserved state, the cache line is updated in place and its state is set to Dirty without updating memory. If the information is in Valid state, a write-through operation is executed updating the block and the memory and the block state is changed to Reserved. Other caches snoop the write and set their copies to Invalid.
• Write miss: A partial cache line write is handled as a read miss (if necessary to fetch the unwritten portion of the cache line) followed by a write hit. This leaves all other caches in the Invalid state, and the current cache in the Reserved state.

This is a variant of the MESI protocol, but there is no explicit read-for-ownership or broadcast invalidate operation to bring a line into cache in the Exclusive state without performing a main memory write. Instead, the first write to a Valid (a.k.a. Shared) cache line performs a write through to memory, which implicitly invalidates other caches. After that, the line is in the Reserved (Exclusive) state, and further writes can be done without reference to main memory, leaving the cache line in the Dirty (Modified) state.