cache的工作原理：为了解决CPU和主存之间速度不匹配的问题，从而引入Cache，将某些主存块复制到Cache中。
那么， 如何区分Cache与主存的数据块的对应关系呢？

一、三种映射方式

假设计算机主存大小256MB，按字节编址，数据cache有8行，数据块大小64B。主存数据在cache里应该怎么存放？二者应该建立怎样的对应关系？
【分析】主存和cache是以数据块为单位进行数据交换的，因此主存块大小$\equiv$cache块大小

数据块大小64B(2⁶B)，以字节编址，占 6 位；
主存大小256MB(2²⁸B)，以字节编址，共占28位；

采用不同的映射方式，会对主存地址（28位）有不同的划分方式：

1. 全相联映射

cache的所有行均可用于存放主存任何一块数据
（助记：空位子全都可以坐）

缺点：查找最慢，当cache块装满的时候，可能需要遍历所有的cache行

主存地址结构划分：

主存块号	块内地址
22位	6位

查找策略：
假如访问地址为：1…1101 001110

1. 用前22位依次与cache块标记进行对比
2. 如果标记匹配且有效位为1，则cache命中，访问块内地址为001110的单元
3. 若cache不命中或有效位为0，则正常访问内存

2. 直接映射

每个主存块只能放到某个固定的cache行，每个主存块所属的cahe行是 主存块号 % cache总行数
（助记：一家公司员工每天都是不假思索直接去自己所属的公司）

缺点：所以多个块会映射到同一行，这样会产生不必要的换入换出，因为即使cache有空行，也不能利用。
（助记：公司有特定技能的人员需要，恰好当前团队没有这样的人才，但是刚好公司人员已经饱和了，那么就得有人先离开，新人再进来，这真是一个悲伤的故事）

针对上例，「0号，8号，16号……」主存块被映射到0号cache行，「1号，9号，17号……」主存块被映射到1号cache行，以此类推……

由于cache行总共8行(2³)，占 3 位；
而恰好主存块号22位的后三位跟cache行号是一致的，所以将主存块号再拆分：

主存地址结构划分：

主存块号	块内地址
主存字块标记（19位） + cache行号（3位） = 22位	6位

查找策略：
假如访问地址为：0…01000 001110

1. 根据主存块号后3位确定cache行号
2. 如果主存块号前19位与cache标记匹配且有效位为1，则cache命中，访问块内地址为001110的单元
3. 若cache不命中或有效位为0，则正常访问内存

3. 组相联映射

首先要对所有的cache行进行分组，每个主存块只能放到固定的cache组，每个主存块所属的cahe组是 主存块号 % cache总组数

（这种方式是上面两种方式的结合，主存数据先找到自己对应的组，组内的空位随便放，这样既提高了查找效率，又减少了因为冲突而导致的换入换出次数）

仍然针对上例，以 2 路组相联为例，cache行可被划分为8/2=4组（2²），组号占 2 位

「0号，4号，8号……」主存块被映射到0号cache组，「1号，5号，9号……」主存块被映射到1号cache行，以此类推……

而恰好主存块号22位的后 2 位跟cache组号是一致的，于是主存块号就有了另外一种划分方式：

主存地址结构划分：

主存块号	块内地址
主存字块标记（20位） + cache组号（2位） = 22位	6位

查找策略：
假如访问地址为：1…0101 001110

1. 根据主存块号后2位确定cache组号
2. 如果主存块号前20位与cache分组内某行标记匹配且有效位为1，则cache命中，访问块内地址为001110的单元
3. 若cache不命中或有效位为0，则正常访问内存

三种映射方式附图：

二、cache容量计算

由于Cache行数比主存块数少得多，因此Cache只能存放主存中的一部分信息，于是Cache要为每一块数据增加一个标记项，来指明它是主存中哪一块的副本，所以在计算cache容量时，需要同时分析标记项位数和cache数据块的位数。

1. 先计算cache行标记项位数

每个cache行都会对应一个标记项，用于标记当前cache行保存的数据状态，cache行标记项包含：

有效位	标记位	脏位	替换控制位
1bit	主存字块标记	1bit	与替换算法有关

* 有效位：（一定有）固定占 1 位，由于cache未装进数据块时，主存字块标记默认为0，所以有效位是为了区分当前cache块是没装数据还是装了一个主存第0的数据
* 标记位：（一定有）主存字块标记位数，用于标识当前cache行存放的主存哪一行数据，计算方法见上
脏位：（特定条件下才有）也叫一致性维护位，只有当cache写策略采用 写回法 时，该位生效并且占 1 位
替换控制位： （特定条件下才有）或叫替换算法位，用于标记替换cache哪一行会被换出，在cache替换策略中，当采用 LRU和LFU替换算法 时，这个控制位会作为被换出的依据。
见脏位和替换控制位相关：计组——cache替换算法及cache写策略

注意：由于Cache是相联存储器，是按内容寻址的，并没有划分地址结构，Cache行标记项里面子项的顺序不需要刻意追究。

2. 再计算cache块位数

题目中一般会以各种方式较为直观的给出，cache块大小和主存块大小是一致的，很方便算出一个块所占据的位数。
数据位：由于主存块和cache块的交换是以 块 为单位，所以数据位即就是一个数据块的数据位数。

3. 计算cache行的位数

$cache行的位数＝cache行标记项位数＋cache块位数$

注意：2021年408考察了这个知识点，见下面［真题嗅探］部分

4. 最后计算cache总容量

根据cache总容量和cache块大小求得cache行数，最后
$cache总容量=cache行数\times cache行的位数$
即 $cache总容量=cache行数\times (cache行标记项位数+cache块位数)$

三、真题嗅探

【例】（2020年408）主存地址32位，按字节编址，指令Cache和数据Cache与主存之间均采用8路组相联，直写策略和LRU替换算法，主存块大小为64B，数据区容量各为32KB。
【分析】主存块大小为64B=2⁶B，则块内地址占6位，再根据主存地址32位，可知主存块号占32-6=26位，32位主存地址划分为：

主存块号	块内地址
26位	6位

8路组相联 --> 每个分组包含8个块（每个分组都会进到特定的Cache组）
再由数据块大小32KB --> 总共有32KB/64B=512块，8块一组，512/8=64=2⁶个分组，组号占6位
主存块号进一步被划分为：字块标记和组号
得到最终的地址结构：

字块标记	组号	块内地址
20位	6位	6位

LRU替换算法，淘汰最近最久未访问的Cache块，当一个分组内8个块已满时，要进行选择淘汰，8个块需用3位进行标记，因此LRU占3位

题目中给出采用直写策略，那么数据发生变更时，会同时修改Cache和主存，因为不需要修改位（脏位）。

那么对应的Cache行标记项结构：

有效位	标记位	脏位	替换控制位
1bit	20位	0位	3位

Cache块的匹配过程：

若CPU最先开始访问地址为0001003H的指令：

字块标记	组号	块内地址
$00000000000000010000$	$000000$	00 0011

步骤：

1. 首先根据组号，组号为0
2. 检查0号分组内的Cache行，有效位均为0，因此Cache访问缺失
3. 然后去主存读取 $00000000000000010000$ $000000$ 主存块，并将其整块放入Cache第0组的任意一行
4. 将Cache行标记项的有效位设为1，标记位设为 $00000000000000010000$，并修改LRU位
5. 之后再访问该指令，根据组号找到Cache分组，再根据标记位找到对应的Cache块（此时有效位是1），再根据块内地址 000011 在Cache行中读出指定的数据。

【例】（2021年408）若计算机主存地址为32位，按字节编址，cache数据区大小为32KB，主存块大小为32B，采用直接映射方式和回写（Write back）策略，则cache行的位数至少是（）
［分析］这里采用「直接映射方式」，特点是：多个块会映射到同一行，这样会产生不必要的换入换出，只要缺页发生，就一定会发生替换，因此不需要替换算法位，故我们不考虑这个替换算法位。

评论区有位同学很严谨，发现并指出了这里的先前的错误分析，这里已做修正.

第一步，确定主存地址划分
主存块大小＝32B，按字节编址 －－> 字块内地址占5位
主存块大小＝cache块大小＝32B，cache数据区大小为 32KB －－> cache总共有32KB/32B=1K行
cache主存采用直接映射方式 －－> cache行号占10位
所以字块内标记占32－10－5＝17位
因此主存地址划分如下：

字块内标记	cache行号	块内地址
17位	10位	5位

第二步，确定cache行对应标记项
采用回写法，脏位1位

有效位	标记位	脏位	替换控制位
1位	17位	1位	－

第三步，得到cache行的位数
cache行位数＝cache数据块位数＋对应标记项位数
＝32B＋19bit
＝32＊8bit ＋19bit
＝275bit

无它，惟有勤习之～各位加油！

感谢你的认真阅读，如果你觉得这篇文章对你有用，欢迎点赞和加关注。
如果你在计算机408的学习过程中还有难懂的问题，欢迎在评论区留言，我会在空闲时间挨个整理更新出来～