假设计算机主存大小256MB，按字节编址，数据cache有8行，数据块大小64B。主存数据在cache里应该怎么存放？二者应该建立怎样的对应关系？
【分析】主存和cache是以数据块为单位进行数据交换的，因此主存块大小
≡
\equiv
≡cache块大小
数据块大小64B(26B)，以字节编址，占 6 位；
主存大小256MB(228B)，以字节编址，共占28位；
采用不同的映射方式，会对主存地址（28位）有不同的划分方式：
cache的所有行均可用于存放主存任何一块数据
（助记：空位子全都可以坐）
缺点：查找最慢，当cache块装满的时候，可能需要遍历所有的cache行
主存地址结构划分：
| 主存块号 | 块内地址 |
|---|---|
| 22位 | 6位 |
查找策略：
假如访问地址为：1…1101 001110
每个主存块只能放到某个固定的cache行，每个主存块所属的cahe行是 主存块号 % cache总行数
（助记：一家公司员工每天都是不假思索直接去自己所属的公司）
缺点：所以多个块会映射到同一行，这样会产生不必要的换入换出，因为即使cache有空行，也不能利用。
（助记：公司有特定技能的人员需要，恰好当前团队没有这样的人才，但是刚好公司人员已经饱和了，那么就得有人先离开，新人再进来，这真是一个悲伤的故事）
针对上例，「0号，8号，16号……」主存块被映射到0号cache行，「1号，9号，17号……」主存块被映射到1号cache行，以此类推……
由于cache行总共8行(23)，占 3 位；
而恰好主存块号22位的后三位跟cache行号是一致的，所以将主存块号再拆分：
主存地址结构划分：
| 主存块号 | 块内地址 |
|---|---|
| 主存字块标记（19位） + cache行号（3位） = 22位 | 6位 |
查找策略：
假如访问地址为：0…01000 001110
首先要对所有的cache行进行分组，每个主存块只能放到固定的cache组，每个主存块所属的cahe组是 主存块号 % cache总组数
（这种方式是上面两种方式的结合，主存数据先找到自己对应的组，组内的空位随便放，这样既提高了查找效率，又减少了因为冲突而导致的换入换出次数）
仍然针对上例，以 2 路组相联为例，cache行可被划分为8/2=4组（22），组号占 2 位
「0号，4号，8号……」主存块被映射到0号cache组，「1号，5号，9号……」主存块被映射到1号cache行，以此类推……
而恰好主存块号22位的后 2 位跟cache组号是一致的，于是主存块号就有了另外一种划分方式：
主存地址结构划分：
| 主存块号 | 块内地址 |
|---|---|
| 主存字块标记（20位） + cache组号（2位） = 22位 | 6位 |
查找策略：
假如访问地址为：1…0101 001110
三种映射方式附图：
由于Cache行数比主存块数少得多，因此Cache只能存放主存中的一部分信息，于是Cache要为每一块数据增加一个标记项，来指明它是主存中哪一块的副本，所以在计算cache容量时，需要同时分析标记项位数和cache数据块的位数。
每个cache行都会对应一个标记项，用于标记当前cache行保存的数据状态，cache行标记项包含：
| 有效位 | 标记位 | 脏位 | 替换控制位 |
|---|---|---|---|
| 1bit | 主存字块标记 | 1bit | 与替换算法有关 |
* 有效位：（一定有）固定占 1 位，由于cache未装进数据块时，主存字块标记默认为0，所以有效位是为了区分当前cache块是没装数据还是装了一个主存第0的数据
* 标记位：（一定有）主存字块标记位数，用于标识当前cache行存放的主存哪一行数据，计算方法见上
脏位：（特定条件下才有）也叫一致性维护位，只有当cache写策略采用 写回法 时，该位生效并且占 1 位
替换控制位： （特定条件下才有）或叫替换算法位，用于标记替换cache哪一行会被换出，在cache替换策略中，当采用 LRU和LFU替换算法 时，这个控制位会作为被换出的依据。
见脏位和替换控制位相关：计组——cache替换算法及cache写策略
注意：由于Cache是相联存储器，是按内容寻址的，并没有划分地址结构，Cache行标记项里面子项的顺序不需要刻意追究。
题目中一般会以各种方式较为直观的给出，cache块大小和主存块大小是一致的，很方便算出一个块所占据的位数。
数据位：由于主存块和cache块的交换是以 块 为单位，所以数据位即就是一个数据块的数据位数。
c a c h e 行的位数＝ c a c h e 行标记项位数＋ c a c h e 块位数 cache行的位数＝cache行标记项位数＋cache块位数 cache行的位数＝cache行标记项位数＋cache块位数
⭐⭐⭐注意：2021年408考察了这个知识点，见下面［真题嗅探］部分
根据cache总容量和cache块大小求得cache行数，最后
c
a
c
h
e
总容量
=
c
a
c
h
e
行数
×
c
a
c
h
e
行的位数
cache总容量=cache行数\times cache行的位数
cache总容量=cache行数×cache行的位数
即
c
a
c
h
e
总容量
=
c
a
c
h
e
行数
×
(
c
a
c
h
e
行标记项位数
+
c
a
c
h
e
块位数
)
cache总容量=cache行数\times(cache行标记项位数+cache块位数)
cache总容量=cache行数×(cache行标记项位数+cache块位数)
【例】（2020年408）主存地址32位，按字节编址，指令Cache和数据Cache与主存之间均采用8路组相联，直写策略和LRU替换算法，主存块大小为64B，数据区容量各为32KB。
【分析】主存块大小为64B=26B，则块内地址占6位，再根据主存地址32位，可知主存块号占32-6=26位，32位主存地址划分为：
| 主存块号 | 块内地址 |
|---|---|
| 26位 | 6位 |
8路组相联 --> 每个分组包含8个块（每个分组都会进到特定的Cache组）
再由数据块大小32KB --> 总共有32KB/64B=512块，8块一组，512/8=64=26个分组，组号占6位
主存块号进一步被划分为：字块标记和组号
得到最终的地址结构：
| 字块标记 | 组号 | 块内地址 |
|---|---|---|
| 20位 | 6位 | 6位 |
LRU替换算法，淘汰最近最久未访问的Cache块，当一个分组内8个块已满时，要进行选择淘汰，8个块需用3位进行标记，因此LRU占3位
题目中给出采用直写策略，那么数据发生变更时，会同时修改Cache和主存，因为不需要修改位（脏位）。
那么对应的Cache行标记项结构：
| 有效位 | 标记位 | 脏位 | 替换控制位 |
|---|---|---|---|
| 1bit | 20位 | 0位 | 3位 |
Cache块的匹配过程：
若CPU最先开始访问地址为0001003H的指令：
| 字块标记 | 组号 | 块内地址 |
|---|---|---|
| 00000000000000010000 {\color{blue} 0000 0000 0000 0001 0000} 00000000000000010000 | 000000 {\color{DarkOrange} 0000 00 } 000000 | 00 0011 |
步骤：
【例】（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的学习过程中还有难懂的问题，欢迎在评论区留言，我会在空闲时间挨个整理更新出来～
