Cache（高速缓冲存储器）是位于主存与CPU之间的一级存储器， 由静态存储芯片（SRAM）组成，容量比较小但速度比主存高得多， 接近于CPU的速度。但其成本更高，因此Cache的容量要比内存小得多。Cache存储了频繁访问内存的数据。

一、Cache原理、命中率、失效率

使用Cache改善系统性能的主要依据是程序的局部性原理。

在Cache中能直接得到数据，称为命中；反之，为未命中。

• 时间局部性：现在访问的指令不久的将来还会访问到它
• 空间局部性：现在访问的指令还会访问到它附近的指令

Cache的访问命中率为h（通常1-h就是Cache的失效率），Cache的访问周期时间是t1，主存储器的访问周期时间是t2，则整个系统的平均访存时间就是：t3=h×t1+(1-h)×t2

例：某流水线计算机主存的读/写时间为100ns，有一个指令和数据合一的Cache，该Cache的读/写时间为10ns，取指令的命中率为98%，取数据的命中率为95%。在执行某类程序时，约有1/5指令需要存／取一个操作数。假设指令流水线在任何时候都不阻塞，则设置Cache后，每条指令的平均访存时间约为多少？

(2%×100ns+98%×10ns)+1/5×(5%×100ns+95%×10ns)=14.7ns

二、Cache存储器的映射机制

分配给Cache的地址存放在一个相联存储器（CAM）中。CPU发生访存请求时，会先让CAM判断所要访问的数据是否在Cache中，如果命中就直接使用。这个判断的过程就是Cache地址映射，这个速度应该尽可能快。常见的映射方法有：

• 直接映射
• 全相联映射
• 组相联映射

1、直接映射

是一种多对一的映射关系，但一个主存块只能够复制到Cache的一个特定位置上去。

Cache的行号 i 和主存的块号 j 有函数关系：i = j % m（其中m为Cache总行数）

例：某Cache容量为16KB（可用14位表示），每行的大小为16B（即可用4位表示），则说明其可分为1024行（可用10位表示）。主存地址的低4位为Cache的行内地址，中间10位为Cache行号。如果内存地址为1234E8F8H，那么最后4位就是1000（对应十六进制数的最后一位），而中间10位，则应从E8F(1110 1000 1111)中获取，得到10 1000 1111 。内存地址为1234E8F8H的单元装入的Cache地址为10 1000 1111 1000。

2、全相联映射

将主存中任一主存块能映射到Cache中任意行（主存块的容量等于Cache行容量）。

根据主存地址不能直接提取Cache页号，而是需要将主存块标记与Cache各页的标记逐个比较，直到找到标记符合的页（访问Cache命中），或者全部比较完后仍无符合的标记（访问Cache失败）。

主存块标记与Cache各页的标记逐个比较，所以这种映射方式速度很慢，失掉了高速缓存的作用，这是全相联映射方式的最大缺点。如果让主页标记与各Cache标记同时比较，则成本太高。

3、组相联映射

是前两种方式的折中方案。它将Cache中的块再分成组，各组之间是直接映像，而组内各块之间则是全相联映像。

主存地址=区号+组号+组内块号+块内地址号

例：容量为64块的Cache采用组相联方式映射，字块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应该为多少位？主存区号为多少位？

首先根据主存块与Cache块的容量必须一致，得出内存块大小也是128个字，因此共有128×4096个字，即219 (27×212)个字，因此需19位主存地址；其中：块内地址号为7位，以表示128个字。一组为4块，则组内块号用2位表示。Cache容量为64块，共分16组, 故组号需要4位地址表示。剩余的即为区号，为6位。

三、Cache淘汰算法

当Cache数据已满，并且出现未命中情况时，就要淘汰一些老的数据，更新一些新的数据进入Cache 。选择淘汰哪些数据的方法就是淘汰算法。常见的方法有三种：

• 随机淘汰算法
• 先进先出淘汰算法（FIFO）
• 最近最久未使用淘汰算法（LRU）

其中平均命中率最高的是LRU算法。

四、Cache存储器的写操作

在使用Cache时，需要保证其数据与主存一致，因此在写Cache时就要考虑与主存间的同步问题，通常使用以下三种方法：

• 写直达：当Cache写命中时，Cache与主存同时发生写修改。
• 写回：当CPU对Cache写命中时，只修改Cache的内容而不立即写入主存，当此行被换出才写回主存
• 标记法：数据进入Cache后,有效位置1;当CPU对该数据修改时，数据只写入主存并将该有效位置0。当要从Cache中读取数据时要测试其有效位，若为1则直接从Cache中取数，否则从主存中取数。