计算机存储系统采用分级体系，目的是为了解决储存容量、成本和速度之间的矛盾问题

高速缓存 Cache

• 用来存储当前最活跃的程序和数据，直接与CPU交互，位于CPU和主存之间，容量小，速度为内存的5-10倍，由半导体材料构成。其内容是主存内容的副本拷贝。

• Cache 由控制部分和存储器组成，存储部分储存数据，控制部分判断CPU要访问的数据是否在 Cache 中，数据在 Cache 中为命中，不在则依据一定的算法从主存中替换

• 地址映射：在 CPU 工作时，送出的是主存单元的地址，而应从 Cache 储存器中读/写信息。这就需要将主存地址转换为 Cache 地址，这种地址转换称为地址映像，由硬件自动完成映射

  • 直接映像：容易冲突

  • 组相连映像：冲突率居中（实现方式参考了直接映像和全相连映像）

  • 全相连映像：不容易冲突

替换算法

替换算法的目标是使 Cache 获得尽可能高的命中率，当缓存满且需要加载新数据时，替换算法决定哪些数据应该被移出缓存，以腾出空间给新数据。

1. 随机替换算法

   • 当缓存满且需要加载新数据时，随机选择一个缓存块进行替换

2. 先进先出算法

   • 最早进入缓存的数据最先被替换

   • 维护一个队列，记录每个缓存块的进入顺序，最先进入的缓存块在队列头部

3. 近期最少使用算法

   • 替换最近最少使用的数据块

   • 维护一个链表或计数器，记录每个缓存块的最近访问时间，最近最少使用的块位于链表尾部或计数器值最小

4. 优化替换算法

   • 替换未来最长时间不会被访问的数据块。

   • 通过预知未来的访问模式，选择最优的替换策略。

命中率及平均时间

命中率即当 CPU 所访问的数据在 Cache 中时，命中，直接从 Cache 中读取数据，若 CPU 访问的数据不在 Cache 中则需要从内存中读取。