局部性原理
Q: 程序访问的局部性原理包括哪两种局部性？
A: 时间局部性：指程序倾向于重复使用最近访问过的数据或指令。空间局部性：指程序倾向于访问内存中彼此靠近的数据或指令。
Q: 时间局部性是如何体现的？请举例说明。
A: 例如：循环语句中，循环变量和循环体内的指令会被反复执行；子程序调用时，子程序的代码会被反复执行。
Q: 空间局部性是如何体现的？请举例说明。
A: 例如：顺序执行的指令通常存储在相邻的内存单元中；数组元素通常存储在连续的内存单元中。
Q: 高速缓存技术利用了什么原理来提高程序执行速度？
A: 高速缓存技术利用程序访问的局部性原理，将经常访问的数据或指令存储在速度更快的 Cache 中，减少访问主存的次数，从而提高程序执行速度。
数组的访问局部性
Q: 数组按行优先存储时，按行遍历数组和按列遍历数组，哪种方式的空间局部性更好？为什么？
A: 按行遍历数组的空间局部性更好。因为按行遍历时，访问的数组元素在内存中是连续存储的，符合空间局部性原理；而按列遍历时，访问的数组元素在内存中是不连续存储的，不符合空间局部性原理。
Cache 工作原理
Cache 的基本工作原理
Q: Cache 的基本工作原理是什么？
A: Cache 是位于 CPU 和主存之间的一级高速存储器，由 SRAM 组成，速度比主存快得多。它利用局部性原理，存储主存中频繁使用的数据块副本，加速 CPU 的访存速度。
当 CPU 需要访问某个数据时，首先检查 Cache 中是否存在该数据，如果存在（命中），则直接从 Cache 中读取，速度快；如果不存在（未命中），则需要从主存中读取数据，并将该数据块复制到 Cache 中，以便下次访问。CPU 与 Cache 之间的数据交换以字为单位，Cache 与主存之间的数据交换以块为单位。
Q: Cache 的命中率是什么？如何计算？
A: Cache 命中率是指 CPU 访问 Cache 时，所需数据已经在 Cache 中的比例。命中率 = Cache 命中次数 / CPU 总访存次数。
Q: Cache-主存系统的平均访问时间如何计算？
A: 平均访问时间 = 命中时间 × 命中率 + 未命中时间 × (1 - 命中率)。其中，未命中时间 = 访问 Cache 时间 + 访问主存时间。
Cache 的映射方式
Q: Cache 的三种映射方式是什么？它们的特点分别是什么？
A: 1. 直接映射：每个主存块只能映射到 Cache 中的唯一位置。特点：实现简单，成本低，但冲突率高。
2. 全相联映射：每个主存块可以映射到 Cache 中的任意位置。特点：冲突率低，利用率高，但成本高，速度慢。
3. 组相联映射：将 Cache 分成若干组，每个主存块映射到固定组内的任意一行。特点：结合了直接映射和全相联映射的优点，冲突率和成本适中。
Q: 如何根据主存地址找到其在 Cache 中的位置？
A: 主存地址被划分为三个部分：标记、组号（索引）和块内偏移。 1. 直接映射：组号直接对应 Cache 行号。
2. 全相联映射：不需要组号，直接比较标记。
3. 组相联映射：组号确定 Cache 组，然后在组内比较标记。
Q: r 路组相联映射需要多少个比较器？为什么？
A: r 路组相联映射需要 r 个比较器。因为每个主存块可以映射到组内的任意一行，需要同时比较组内所有 r 个 Cache 行的标记，才能确定是否命中。
Cache 的替换算法
Q: 当 Cache 已满，需要调入新的主存块时，如何选择替换的 Cache 行？
A: 需要使用替换算法来选择替换的 Cache 行。常用的替换算法有：
- 随机替换算法 (RAND)：随机选择一行替换。
- 先进先出算法 (FIFO)：选择最早进入 Cache 的一行替换。
- 近期最少使用算法 (LRU)：选择最近最长时间未被访问的一行替换。
- 最不经常使用算法 (LFU)：选择访问次数最少的一行替换。
Q: LRU 算法是如何工作的？
A: LRU 算法为每个 Cache 行设置一个计数器，记录该行最近一次被访问的时间。当需要替换 Cache 行时，选择计数器值最大（即最近最长时间未被访问）的行进行替换。
Q: 什么是 Cache 抖动？如何避免？
A: Cache 抖动是指频繁地替换 Cache 行，导致 Cache 命中率下降的现象。可以通过增加 Cache 容量、提高相联度、优化程序访存模式等方法来避免 Cache 抖动。
Cache 的一致性问题
Q: Cache 的一致性问题是什么？
A: 在多处理器系统或支持 DMA 的系统中，多个设备可能同时访问同一个主存单元，导致 Cache 中的数据与主存数据不一致的问题。
Q: 写操作策略有哪些？
A: 1. 全写法 (Write-Through)：每次写入数据时，同时写入 Cache 和主存。
2. 回写法 (Write-Back)：只写入 Cache，当 Cache 行被替换时才写回主存。
Q: 全写法和回写法的优缺点分别是什么？
A: 全写法：优点是数据一致性好，缺点是写操作速度慢。回写法：优点是写操作速度快，缺点是数据一致性差。
Q: 写分配法和非写分配法的区别是什么？
A: 写分配法：写操作未命中时，将主存块调入 Cache，然后更新 Cache。
非写分配法：写操作未命中时，只更新主存，不调入 Cache。
Q: 写缓冲的作用是什么？
A: 写缓冲用于缓存 CPU 写入的数据，减少 CPU 等待写操作完成的时间。
分离的指令 Cache 和数据 Cache
Q: 分离的指令 Cache 和数据 Cache 的作用是什么？
A: 分离指令 Cache 和数据 Cache 可以分别存储指令和数据，避免指令和数据访问的冲突，提高 CPU 的访存效率。