计算机读写设备, 越快越大, 就越贵. 并且计算机程序有一个称为局部性(locality)基本
属性. 具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合, 或是倾向于访问
邻近的数据项集合. 因此计算机存储器创建了层次结构, 称为memory mountain.
局部性原理(principle of locality), 是一个持久的概念, 更倾向于引用邻近于其他最
近引用过的数据项, 或者最近引用过的数据项本身.局部性通常有两种不同的形式: 时间局部性(temporal locality)和空间局部性(spatial
locality). 好的时间局部性程序中, 被引用过一次的存储器位置很可能在不远的将来再被
多次引用; 好的空间局部性程序中, 如果一个存储器位置被引用一次, 那么程序很可能在不
远的将来引用附近的一个存储器位置.
高速缓存在存储器层次中, 处于寄存器和主存之间. 访问速度快, 但是容量小, 成本高.
层次结构中的每一层都缓存来自较低一层的数据对象. 缓存一般使用固定大小划分成block,
也可以是可变大小的. block有唯一的编号和名称, 缓存都是以块为单位来传输(transfer unit).
当程序需要第k+1层的某个数据对象d时, 它首先在当前存储在第k层的一个块中查找d.
如果d刚好缓存在第k层中, 那么就是我们所说的缓存命中(cache hit). 如果第k层中
没有缓存数据对象d, 那么就是我们所说的缓存不命中(cache miss).覆盖一个现存的块的过程称为替换(replacing)或驱逐(evicting)这个块. 被驱逐的这个块
有时也称为牺牲块(victim block). 决定该替换哪个块是由缓存的替换策略(replacement policy)
来控制的.