Cache

Cache的基本概念与原理

为了解决CPU与内存的速度矛盾，提出在两者间设置Cache(集成在CPU中)这一元件。

局部性原理

空间局部性：在最近的未来要用到的信息(指令和数据),很可能与现在正在使用的信息在存储空间上是邻近的
- 比如数组元素、顺序执行的指令代码
时间局部性：在最近的未来要用的信息，很可能是现在正在使用的信息
- 循环结构的指令代码

基于局部性原理，可以把CPU目前访问的地址周围的部分数据放到Cache中

“周围”的定义：将主存的存储空间分块，主存与Cache之间以“块”为单位进行数据交换

主存中这个“块”也称 “页/页面/页框”，Cache中也称为“行”

性能分析

设t_c为访问一次Cache所需时间，t_m为访问一次主存的时间

命中率H：CPU预访问的信息已在Cache中的比率
缺失率M = 1-H
Cache–主存系统的平均访问时间
1. 先访问Cache，若Cache未命中再访问主存，$t = Ht_{c}+(1-H)(t_{c}+t_{m})$
2. 同时访问Cache和主存，若Cache命中则立即停止访问主存，$t = Ht_{c}+(1-H)t_{m} $

Cache与主存的映射方式

如何区分Cache与主存的数据块对应关系？

设地址空间大小为2ⁿ,那么主存的地址就有n位，且可以分为主存块号m位与块内地址n-m位两个部分
每个Cache块的大小都与主存的块大小相同

全相联映射

主存块可以放在Cache的任意位置

当CPU访问主存地址时发生了下列事件：

主存地址的前m位(主存快号)对比Cache中所有块的标记
若标记匹配且有效位=1，则Cache命中，访问块内地址为指定地址的单元

直接映射

每个主存块只能放到一个特定的位置：

主存块在Cache中的位置=主存块号%Cache总块数

或：主存块在Cache中的位置=主存地址%Cache总容量，也就是主存低n位地址

如果Cache总块数为2ⁿ，则主存块号末尾n位直接反应它在Cache中的位置，所以将主存块号的其余位作为标记即可

步骤：组选择–行匹配–字抽取

缺点：其他地方有空闲Cache块，但是无法去存放

组相联映射

Cache块分为若干组，每个主存块可放到特定分组中的任意一个位置

组号 = 主存块号%分组数

Cache命中

组选择（Set）
行匹配（Tag）
查看有效位，为1则命中

小结

Cache替换算法

用于解决Cache满了以后需要在全局选择替换哪一块的问题

注：直接映射法别无选择，也不存在算法这一说

随机算法(RAND)

若Cache已满，随机选择一块替换。

完全没考虑局部性原理，实际使用时命中率较低且不稳定

先进先出算法(LIFO)

若Cache已满，则替换最先被调入Cache的块

实现简单，但仍然没考虑局部性原理，最先被调入Cache的块也有可能是被频繁访问的
存在抖动现象：频繁的换入换出

近期最少使用算法(LRU)

为每个Cache块设置“计数器”，用于记录每个Cache块已经有多久没被访问，当Cache满后替换“计数器”最大的。

命中时，所命中的的行的计数器清零，比其低的计数器+1，其余不变。
未命中且还有空闲块时，新装入的行的计数器清0，其余非空闲行全+1
未命中且无空闲行时，计数值最大的行的信息块被淘汰，新装行的快的计数器置0，其余全+1。
LRU的位数取决于Cache一组中有多少行

基于“局部性原理”，实际运行效果优秀，Cache命中率高

如果被频繁访问的主存块的数量>Cache块的数量，则有可能发生抖动现象

最不经常使用算法(LFU)

同样为每一个Cache块设置一个“计数器”，用于记录每个Cache块被访问过几次。当Cache满后替换“计数器”中最小的

当存在多个计数器最小值时，则通过行号递增、FIFO策略进行替换
曾经被经常访问的主存块在未来不一定会用到，并没有完全遵循局部性原理，因此实际运行效果不如LRU

Cache写策略

用于确保主存中数据母本的唯一性

写命中–写回法

当CPU对Cache写命中时，只修改Cache的内容，而不立即写入主存，只有当此块被换出时才写回主存

减少了访存次数，但存在数据不一致的隐患。
需要1位脏位，表示Cache有没有被修改

写命中–全写法

当CPU对Cache写命中时，同时向Cache和主存写入，一般先向写缓冲写入，当CPU执行连续读操作或其他操作，写缓存再通过专门的控制电路逐一写入进主存

访存次数增加

写缓冲同样使用SRAM,且为一个FIFO模型

可以使CPU写操作速度加快，若写操作很频繁，可能会因为写缓冲饱和而发生阻塞

写未命中–写分配法

当CPU对Cache写不命中时，把主存中的块调入Cache，在Cache中修改，通常搭配写回法使用

写未命中–非写分配法

当CPU对Cache写不命中时，只写入主存，不调入Cache，搭配全写法使用

多级Cache

离CPU越近，速度越快，容量越小
离CPU越远，速度越慢，容量越大

页式存储器

一个程序(进程)在逻辑上被分为若干个大小相等的“页面”，“页面”大小与“块”的大小相同。每个页面可以离散地放入不同的主存块中。

逻辑地址(虚地址)：程序员视角看到的地址,CPU执行的机器指令中用的也是逻辑地址
物理地址(实地址)：实际在主存中的地址

逻辑地址由逻辑页号与页内地址拼接而成，由操作系统将逻辑页号映射为主存块号，从而得出实际地址。

这种逻辑页号到主存块号的映射由一张页表来完成。存放在主存当中
页内地址位数取决于单位页面的大小(1KB页面有10位页内地址)

基于局部性原理(访问过的数据在未来很有可能再次被访问)，可以仿照Cache的思路，将页表复制一份到更高速的存储器(类似Cache)，用于加快地址变换的速度。

这个更高速的存储器叫做快表(TLB)，存储在主存的页表叫做慢表

快表	Cache
存储页表项的副本	存储主存块的副本
SRAM	DRAM
相联式存储器,可按内容寻访	按地址寻访
存储容量铰大	存储容量较大

CPU访问数据：取地址->取地址对应的数据

取地址：查快表/慢表，将逻辑地址转为物理地址

取数据：查Cache/主存，获取数据