【组成原理-存储】Cache 和页式虚拟存储器

1 高速缓冲存储器（Cache）

1.1 组相联映射

将 Cache 分为 Q 个大小相等的组，每组有 r 个 Cache行，称为 r 路组相联。

• Cache 组号 = 主存块号 mod Cache 组数 (Q)

例 1（按字节编址）

【假设】

• 某计算机的主存地址空间为 256MB，按字节编址（1B），则有 256MB/1B = 256M = 2²⁸ 个存储单元，地址位数为 28
• 一个主存块大小为 64B（即 Cache 行长为 64B），则一个主存块的存储单元个数为 64B/1B = 64
• Cache 有 16 行，又已知 Cache 行长为 64B，二路组相联，一共 16/2=8 组

【解答】

• 主存的物理地址的结构：

Cache 一共 2³ = 8 组，所以组号占 3 位；主存块（行长）存储单元个数为 2⁶ = 64，所以块内地址占 6 位；因此标记占 28-3-6=19 位。

• Cache 结构（组号、行号不是 Cache 的组成部分）：

• Cache 行位数 = 标记阵列位数 + Cache 行长 = 1 + 19 + 64 * 8 = 532
• Cache 总容量 = Cache 总行数 * Cache 行位数 = 16 * (1 + 19 + 64 * 8) b = 8512b

【注】有些题目中， Cache 的容量大小指的是 Cache 存储容量，不包括标记阵列（标记位、有效位、脏位等）。比如某个 Cache 容量大小为 64KB，指的是 Cache 存储容量为 64KB，若再加条件：Cache 行长（即主存块大小）为 128B，则该 Cache 总行数为 64KB/128B = 512 行。

例 2（按字编址）

【假设】

• 某计算机的主存地址空间为 256MB，按字编址（4B），则有 256MB/4B = 64M = 2²⁶ 个存储单元，地址位数为 26
• 一个主存块大小为 64B（即 Cache 行长为 64B），则一个主存块的存储单元个数为 64B/4B = 16
• Cache 有 16 行，又已知 Cache 行长为 64B，二路组相联，一共 16/2=8 组

【解答】

• 主存的物理地址的结构：

Cache 一共 2³ = 8 组，所以组号占 3 位；主存块（行长）存储单元个数为 2⁴ = 16，所以块内地址占 4 位；因此标记占 26-3-4=19 位。

• Cache 结构（组号、行号不是 Cache 的组成部分）：

• Cache 行位数 = 标记阵列位数 + Cache 行长 = 1 + 19 + 64 * 8 = 532
• Cache 总容量 = Cache 总行数 * Cache 行位数 = 16 * (1 + 19 + 64 * 8) b = 8512b

例 3（按字节编址，考虑 LRU 算法、回写策略）

【假设】

• 某计算机的主存地址空间为 256MB，按字节编址（1B），则有 256MB/1B = 256M = 2²⁸ 个存储单元，地址位数为 28
• 一个主存块大小为 16B（即 Cache 行长为 16B），则一个主存块的存储单元个数为 16B/1B = 16
• Cache 有 64 行，又已知 Cache 行长为 16B，四路组相联，一共 64/4=16 组
• 考虑 LRU 算法、回写策略

【解答】

• 主存的物理地址的结构：

Cache 一共 2⁴ = 16 组，所以组号占 4 位；主存块（行长）存储单元个数为 2⁴ = 16，所以块内地址占 4 位；因此标记占 28-4-4=20 位。

• Cache 结构（组号、行号不是 Cache 的组成部分）：

考虑 LRU 算法，因为是四路组相联，2^2=4，所以替换控制位占 2 位；考虑回写策略，所以脏位占 1 位。（注意：如果题目中没有要求考虑，则不需要加这些东西）

• Cache 行位数 = 标记阵列位数 + Cache 行长 = 1 + 2 + 1 + 20 + 16 * 8 = 152
• Cache 总容量 = Cache 总行数 * Cache 行位数 = 64 * (1 + 2 + 1 + 20 + 16 * 8) b = 9728b

1.2 全相联映射

当 Q=1 时变为全相联映射，即整个 Cache 都是一个组。

例 4（按字节编址）

【假设】

• 某计算机的主存地址空间为 256MB，按字节编址（1B），则有 256MB/1B = 256M = 2²⁸ 个存储单元，地址位数为 28
• 一个主存块大小为 64B（即 Cache 行长为 64B），则一个主存块的存储单元个数为 64B/1B = 64
• Cache 有 16 行，又已知 Cache 行长为 64B

【解答】

• 主存的物理地址的结构：

主存块（行长）存储单元个数为 2⁶ = 64，所以块内地址占 6 位；因此标记占 28-6=22 位。

• Cache 结构（组号、行号不是 Cache 的组成部分）：

• Cache 行位数 = 标记阵列位数 + Cache 行长 = 1 + 22 + 64 * 8 = 279
• Cache 总容量 = Cache 总行数 * Cache 行位数 = 16 * (1 + 22 + 64 * 8) b = 4464b

例 5（按字编址）

【假设】

• 某计算机的主存地址空间为 256MB，按字编址（4B），则有 256MB/4B = 64M = 2²⁶ 个存储单元，地址位数为 26
• 一个主存块大小为 64B（即 Cache 行长为 64B），则一个主存块的存储单元个数为 64B/4B = 16
• Cache 有 16 行，又已知 Cache 行长为 64B

【解答】

• 主存的物理地址的结构：

主存块（行长）存储单元个数为 2⁴ = 16，所以块内地址占 4 位；因此标记占 28-4=24 位。

• Cache 结构（组号、行号不是 Cache 的组成部分）：

• Cache 行位数 = 标记阵列位数 + Cache 行长 = 1 + 24 + 64 * 8 = 281
• Cache 总容量 = Cache 总行数 * Cache 行位数 = 16 * (1 + 24 + 64 * 8) b = 4496b

1.3 直接映射

当 r=1 时变为直接映射，即每行 Cache 都是一个组。

• Cache 组号 = 主存块号 mod Cache 总行数

例 6（按字节编址）

【假设】

• 某计算机的主存地址空间为 256MB，按字节编址（1B），则有 256MB/1B = 256M = 2²⁸ 个存储单元，地址位数为 28
• 一个主存块大小为 64B（即 Cache 行长为 64B），则一个主存块的存储单元个数为 64B/1B = 64
• Cache 有 16 行，又已知 Cache 行长为 64B

【解答】

• 主存的物理地址的结构：

Cache 一共 2⁴ = 16 行，所以行号占 4 位；主存块（行长）存储单元个数为 2⁶ = 64，所以块内地址占 6 位；因此标记占 28-4-6=18 位。

• Cache 结构（组号、行号不是 Cache 的组成部分）：

• Cache 行位数 = 标记阵列位数 + Cache 行长 = 1 + 18 + 64 * 8 = 275
• Cache 总容量 = Cache 总行数 * Cache 行位数 = 16 * (1 + 18 + 64 * 8) b = 4400b

2 页式虚拟存储器

2.1 页表

假设虚拟地址空间为 32 位，一页为 4KB，物理地址空间为 28 位，则：

• 虚拟地址的结构（一共 2²⁰ 页）：

• 页表结构（虚页号不属于页表结构）：

• 得到的物理地址结构：

2.2 快表（TLB）

2.2.1 组相联 TLB

【假设】

• 主存空间大小为 256MB，按字节编址，则物理地址位数为 28 位
• 虚拟地址空间大小为 4GB，页面大小为 4KB，则地址位数为 32 位，有 4GB/4KB = 2²⁰ 页，所以虚拟地址的虚页号占高 20 位，虚拟地址的页内地址占低 12 位；物理地址的页内地址也占低 12 位，因而物理地址的页号占高 16 位
• TLB 为二路组相联，一共四组，2²=4，则虚页号中组号还要占低 2 位

【则有】

• （4GB）虚拟地址的结构：

• 二路组相联 TLB 结构（组号、行号不是 TLB 的组成部分）：

• （256MB）得到的物理地址的结构：

2.2.2 全相联 TLB

【假设】

• 主存空间大小为 256MB，按字节编址，则物理地址位数为 28 位
• 虚拟地址空间大小为 4GB，页面大小为 4KB，则地址位数为 32 位，有 4GB/4KB = 2²⁰ 页，所以虚拟地址的虚页号占高 20 位，虚拟地址的页内地址占低 12 位；物理地址的页内地址也占低 12 位，因而物理地址的页号占高 16 位
• TLB 为全相联，共 8 行

【则有】

• （4GB）虚拟地址的结构：

• 四路组相联 TLB 结构（组号、行号不是 TLB 的组成部分）：

• （256MB）得到的物理地址的结构：

2.2.3 直接相联 TLB

【假设】

• 主存空间大小为 256MB，按字节编址，则物理地址位数为 28 位
• 虚拟地址空间大小为 4GB，页面大小为 4KB，则地址位数为 32 位，有 4GB/4KB = 2²⁰ 页，所以虚拟地址的虚页号占高 20 位，虚拟地址的页内地址占低 12 位；物理地址的页内地址也占低 12 位，因而物理地址的页号占高 16 位
• TLB 为直接相联，共 8 行，2³=8，所以虚页号中行号还要占低 3 位

【则有】

• （4GB）虚拟地址的结构：

• 直接相联 TLB 结构（组号、行号不是 TLB 的组成部分）：

• （256MB）得到的物理地址的结构：

3 LRU 替换算法

3.1 直接映射的 LRU 算法

计数器变化规则：

• 命中时，所命中的行计数器清零，比其低的计数器加 1，其余不变；
• 未命中且有空闲行时，新装入的行的计数器置 0，其余全加 1；
• 未命中且无空闲行时，计数值为 3 的行的信息块被淘汰，新装入的行的块计数器置 0，其余全加 1。

【假设】内存容量为 4 个页面，使用 LRU 页面替换算法，考虑以下页面访问顺序：{1, 8, 1, 7, 2, 7, 2, 1, 8, 3, 8, 3, 2, 7}

【解答】（斜体表示命中，加粗表示替换）

无空闲行且需要替换时，从上一次替换的位置开始，从左往右找每一行的最后一个命中，最后一个命中出现最早（或没有出现命中）的那一行说明访问频率较少（或没有访问），替换那一行。

综上，失效次数（未命中次数）为 6 次，命中率为 8/14。

3.2 组相联的 LRU 算法

先计算 Cache 组号 = 主存块号 mod Cache 组数 (Q)，看对应的 Cache 组里面有无命中的行，然后按照以下计数器变化规则处理（注意只处理对应组里面的所有行，其他组不用管）：

• 命中时，所命中的行计数器清零，比其低的计数器加 1，其余不变；
• 未命中且有空闲行时，新装入的行的计数器置 0，其余全加 1；
• 未命中且无空闲行时，计数值为 3 的行的信息块被淘汰，新装入的行的块计数器置 0，其余全加 1。

【假设】Cache 采用二路组相联方式，访问主存地址顺序：{0, 4, 8, 2, 0, 6, 8, 6, 4, 8}

【解答】（斜体表示命中或有空闲行插入，加粗表示替换）

无空闲行且需要替换时，从上一次替换的位置开始，从左往右找每一行的最后一个命中，最后一个命中出现最早（或没有出现命中）的那一行说明访问频率较少（或没有访问），替换那一行。注意该操作需要在对应组内进行。

【注意】

• 主存的 0、1 块对应 Cache 的 0、1 块，也就是 Cache 的第 0 组；
• 主存的 2、3 块对应 Cache 的 2、3 块，也就是 Cache 的第 1 组；
• 以此类推，主存的 4、5、8、9 块就对应 0 组，6、7 块对应 1 组；
• 所以，0、1、4、5、8、9 只能放在 0 组。2、3、6、7 只能放在 1 组。

命中次数为 3，命中率为 3/10。