 Caching

Caching retains selected information in a cache so later requests can reuse it. A cache hit finds the requested item there; a cache miss requires obtaining it elsewhere. A limited-capacity cache also needs a rule for deciding which items remain, such as LRU replacement.

For a two-entry cache initially empty, requests A,B,A,C,A produce misses for the first A, B and C, and hits for the repeated A values under LRU replacement. Inserting C evicts B, since A was used more recently. This example has cache hit rate $2/5$ and cache miss rate $3/5$. A different request order or replacement rule can change the result.

The useful saving depends on both reuse and validity. A cached result that depends on changed data may need invalidation or recomputation; retaining it indefinitely does not preserve correctness. For main-memory paging, cache-management decisions trade page faults against finite storage, and average memory access time includes the extra cost of misses.^[ref]