Chapter 8 Cache(9)

这一节是讲解大题的。

题目一：

已知条件

虚拟地址：14位
物理地址：12位
页大小：64字节（$2^6$）
页表（前16项）：已提供表格。

问题 1：虚拟地址格式

虚拟地址由 虚拟页号（VPN） 和 页内偏移（Offset） 组成。
页大小为 $2^6 = 64$，所以页内偏移需要 6位。
总虚拟地址为 14 位，剩余 $14 - 6 = 8$ 位用于 虚拟页号（VPN）。

格式：

虚拟页号（VPN）：8 位
页内偏移：6 位

问题 2：物理地址格式

物理地址由 物理页号（PPN） 和 页内偏移（Offset） 组成。
页大小相同，页内偏移仍为 6位。
物理地址总长 12 位，剩余 $12 - 6 = 6$ 位用于 物理页号（PPN）。

格式：

物理页号（PPN）：6 位
页内偏移：6 位

问题 3：虚拟地址转换（0x030D）

将虚拟地址转为二进制：
- $0x030D = (00 0011 0000 1101)_2$。
- 虚拟页号（VPN）：前 8 位 $00001100_2 = 0x0C$。
- 页内偏移（Offset）：后 6 位 $001101_2 = 0x0D$。
查找页表：
- 根据页表，VPN = 0x0C 对应 PPN = 0x1E。
物理地址计算：
- 物理页号（PPN）：$0x1E = 011110_2$。
- 页内偏移（Offset）：$0x0D = 001101_2$。
- 合并为 物理地址：$011110 001101_2 = 0x78D$。

精华

虚拟地址格式：
- 虚拟页号（VPN）：8 位
- 页内偏移（Offset）：6 位
物理地址格式：
- 物理页号（PPN）：6 位
- 页内偏移（Offset）：6 位
转换过程：
- 虚拟地址 0x030D 转换为二进制 $00001100\ 001101$。
- VPN = 0x0C，在页表中查得 PPN = 0x1E。
- 组合 PPN 和 Offset 得到物理地址 0x78D。

题目2：

题目：内存系统分析

已知一个内存系统的具体参数如下：

字节寻址。
虚拟地址空间：4G 字节。
主存大小：16M 字节。
Cache 大小：256K 字节。
页面大小：64K 字节。
块大小：128 字节。
映射策略：
- 主存到 Cache：4 路组相联。
- 硬盘到主存：全相联。

虚拟地址首先会被转换成物理地址，然后用物理地址访问 Cache。

问题：

Cache 中有多少个组（sets）？
Cache 中的 tag 字段有多长？
给定虚拟地址 $0B45DA12$（十六进制），其对应的虚拟页被存储在物理页 $3E$（十六进制）。
- 1. 在此映射下，该虚拟地址的物理地址是什么？
- 1. 该地址可能在哪个 Cache 组中找到？
- 1. 该地址指向块内的哪个字节？

解答

(1) Cache 中的组数（Sets）

根据 Cache 的组相联映射公式：
$ = $ $ = = 512 $ Cache 中共有 512 组。

(2) Cache 的 Tag 字段长度

主存地址为 24 位（主存大小 $16M = 2^{24}$ 字节）。
每组有 512 组，因此组字段长度为： $ = _2() = _2(512) = 9 $
块大小为 128 字节，块内偏移字段为： $ = _2(128) = 7 $
Tag 字段长度为： $ = - - = 24 - 9 - 7 = 8 $

Tag 字段长度为 8 位。

(3) 虚拟地址 $0B45DA12$ 的分析

① 虚拟地址到物理地址转换

虚拟地址 $0B45DA12$（32 位）分为：
- 虚拟页号（高 16 位）：$0B45$
- 页内偏移（低 16 位）：$DA12$
根据题目，虚拟页 $0B45$ 对应的物理页号为 $3E$。
将物理页号 $3E$ 与页内偏移 $DA12$ 拼接，得到物理地址：
$ = 3E , | , DA12 = 3EDA12 $

物理地址为 $3EDA12$。

② 物理地址对应的 Cache 组号

物理地址 $3EDA12$（24 位）分为：
- Tag（高 8 位）：$0011\ 1110$ = 0x3E
- 组号（中 9 位）：$1101\ 1010\ 0$ = 0x1B4 或 436
- 块内偏移（低 7 位）：$0010010$ = 0x12
该地址可能对应 Cache 中的组号： $ = 0x1B4 , , 436 $

可能在组 436 中找到。

③ 块内字节偏移
物理地址的块内偏移部分为低 7 位，即： $0010010$

该地址指向块内第 18 个字节。

总结

Cache 中的组数：512 组。
Tag 字段长度：8 位。
物理地址转换：虚拟地址 $0B45DA12$ 转换为物理地址 $3EDA12$。
Cache 组号：可能在组号 436。
块内偏移：地址指向块内第 18 个字节。

问题3：

考虑以下二维数组 A：

1	int A[][] = new int[100][100];

其中，$A[0][0] $的起始地址是 200，在一个分页内存系统中，每页的大小为 200。

已知：

页面分配：小型进程位于页面 0（地址范围 0 至 199）中，用于操作矩阵，因此所有指令都会从页面 0 中获取。
数组存储方式：数组元素按行优先顺序存储在虚拟内存中。
页面替换算法：使用 LRU（最近最少使用）替换算法。
页面框数量：3个页面框架（Page Frame），其中页面框 1 已被进程占用，其余两个最初为空。

问题：
对于以下两种数组初始化循环，计算产生的页错误（Page Fault）数量。

循环 (1)

1
2
3

for (int j = 0; j < 100; j++)  
    for (int i = 0; i < 100; i++)  
        A[i][j] = 0;

循环 (2)

1
2
3

for (int i = 0; i < 100; i++)  
    for (int j = 0; j < 100; j++)  
        A[i][j] = 0;

结果：

循环 (1) 的页错误数：5000
循环 (2) 的页错误数：50

详细解析：

数组存储与页面划分

数组元素的存储方式：
- 按行优先顺序存储，每行包含 100 个元素，每个元素假定占用 1 字节。
- 因此，虚拟地址中数组的起始位置和每页的分布如下：
  - 每页大小为 200 字节（即每页可以容纳两行）。
  - 页 1：虚拟地址 200 - 399（包含 $A[0][0] $到$ A[1$][99]）
  - 页 2：虚拟地址 400 - 599（包含 $A[2][0]$ 到 $A[3$][99]）
  - 以此类推，每两行占用一个页面。
内存分配与页面框数量：
- 页面框 1：进程所在页面（地址 0 - 199），始终存在。
- 其余两个页面框用于存放数组页，且初始为空。

循环 (1) 分析

外层循环遍历列，内层循环遍历行。
对于每个列 $ j $，会依次访问 **$A[0][j], A[1][j], ..., A[99][j]$**。
由于数组是按行优先存储的，访问列时会跨越多个页面，每次跨页时会引发页面错误。

计算过程：

每列需要访问 100 个元素，每 2 行的元素分布在一个页面中，因此每列需要访问 50 个页面。
外层循环遍历 100 列，因此总页错误数为：
$ 100 = 5000 $

循环 (2) 分析

外层循环遍历行，内层循环遍历列。
对于每一行 $ i $，会依次访问 **$A[i][0], A[i][1], ..., A[i][99]$**。
由于数组是按行优先存储的，每一行的元素都存储在同一个页面中，因此每次内层循环只会引发一次页面错误。