Chap. 8 HW

虚拟地址 (Virtual Address, VA)：CPU生成的地址，由“虚拟页号 (VPN)”和“页内偏移量 (Offset)”两部分组成。
物理地址 (Physical Address, PA)：内存中的实际地址，由“物理页框号 (PFN)”和“页内偏移量 (Offset)”组成。偏移量在虚拟地址和物理地址中是完全相同的。
页面大小 (Page Size)：决定了偏移量需要占用多少个二进制位。例如，1024字节（ $2^{10}$ ）的页面，偏移量就是10位。

以下是所有题目的详细解答。

第一题解析

【英文原题】

Suppose the page table for the process currently executing on the processor looks like the following. All numbers are decimal, everything is numbered starting from zero, and all addresses are memory byte addresses. The page size is 1024 bytes. The following table: (Virtual page number, Valid bit, Reference bit, Modify bit, Page frame number) -> (0, 1, 1, 0, 4), (1, 1, 1, 1, 7), (2, 0, 0, 0, -), (3, 1, 0, 0, 2), (4, 0, 0, 0, -), (5, 1, 0, 1, 0). a. Describe exactly how, in general, a virtual address generated by the CPU is translated into a physical main memory address. b. What physical address, if any, would each of the following virtual addresses correspond to? (Do not try to handle any page faults, if any.) (i) 1052 (ii) 2221 (iii) 5499

【中文翻译】

假设当前正在处理器上执行的进程的页表如下所示。所有数字均为十进制，所有编号均从零开始，所有地址均为内存字节地址。页面大小为 1024 字节。下表： (虚拟页号, 有效位, 访问位, 修改位, 页框号) -> (0, 1, 1, 0, 4), (1, 1, 1, 1, 7), (2, 0, 0, 0, 空), (3, 1, 0, 0, 2), (4, 0, 0, 0, 空), (5, 1, 0, 1, 0)。 a. 准确描述一般情况下，CPU生成的虚拟地址是如何转换为物理主存地址的。 b. 以下每个虚拟地址（如果有的话）将对应哪个物理地址？（尽量不要处理任何缺页异常，如果有的话。） (i) 1052 (ii) 2221 (iii) 5499

【深入解析】a. 地址转换过程：

拆分地址：当CPU生成一个虚拟地址时，系统首先根据页面大小将该虚拟地址拆分为两部分：虚拟页号（VPN）和页内偏移量（Offset）。拆分公式为：VPN = 虚拟地址 / 页面大小（取整数部分）；Offset = 虚拟地址 % 页面大小（取余数部分）。
查表：硬件使用VPN作为索引去查找页表。
检查有效位：检查该表项的“有效位（Valid bit）”。如果有效位为0，说明该页面不在内存中，触发“缺页异常（Page Fault）”。
生成物理地址：如果有效位为1，则从页表中提取对应的“物理页框号（PFN）”。最终的物理地址计算公式为：物理地址 = (PFN * 页面大小) + Offset。

b. 具体地址计算： 已知页面大小为 1024 字节。

(i) 虚拟地址 1052
VPN = $1052 \div 1024 = 1$
Offset = $1052 \pmod{1024} = 28$
查表：虚拟页号1对应的有效位是1，页框号是7。
物理地址 = $7 \times 1024 + 28 = 7168 + 28 =$ 7196。
(ii) 虚拟地址 2221
VPN = $2221 \div 1024 = 2$
Offset = $2221 \pmod{1024} = 173$
查表：虚拟页号2对应的有效位是0。
结果：发生缺页异常（Page Fault），无对应的物理地址。
(iii) 虚拟地址 5499
VPN = $5499 \div 1024 = 5$
Offset = $5499 \pmod{1024} = 379$
查表：虚拟页号5对应的有效位是1，页框号是0。
物理地址 = $0 \times 1024 + 379 = 0 + 379 =$ 379。

【英文原题】 2. Consider a paged virtual memory system with 32-bit virtual addresses and 1K-byte pages. Each page table entry requires 32 bits. It is desired to limit the page table size to one page. a. How many levels of page tables are required? b. What is the size of the page table at each level? Hint: One page table size is smaller. c. The smaller page size could be used at the top level or the bottom level of the page table hierarchy. Which strategy consumes the least number of pages?

【中文翻译】 2. 考虑一个具有32位虚拟地址和1KB页面的分页虚拟内存系统。每个页表项需要32位。希望将页表大小限制为一个页面。 a. 需要多少级页表？ b. 每一级的页表大小是多少？提示：其中一个页表的大小较小。 c. 较小的页表大小可以用于页表层次结构的顶层或底层。哪种策略消耗的页面数量最少？

【深入解析】前置计算：

页面大小 = 1KB = $2^{10}$ 字节，因此页内偏移量占用 10位。
虚拟地址总长32位，所以虚拟页号（VPN）占用 $32 - 10 =$ 22位。
每个页表项大小 = 32位 = 4字节（ $2^2$ 字节）。
一个页面最多可以容纳的表项数 = 页面大小 / 表项大小 = $2^{10} / 2^2 = 2^8 =$ 256 个表项。
因为一个页表最多有256个表项，所以每一级页表最多只能映射 $\log_2(256) =$ 8位的虚拟地址。

解答：

a. 需要的页表级数 我们需要用每次最多8位的块来覆盖总共22位的VPN。 $22 \div 8 = 2$ 余 6。这意味着我们需要 $8 + 8 + 6 = 22$ 。因此，需要 3级页表。
b. 每一级的页表大小 其中两级页表负责映射8位，需要 $2^8 = 256$ 个表项，大小为 $256 \times 4$ 字节 = 1024 字节（1个页面，即1KB）。有一级较小的页表负责映射剩余的6位，需要 $2^6 = 64$ 个表项，大小为 $64 \times 4$ 字节 = 256字节（占用四分之一个页面）。
c. 较小页表的放置策略顶层策略消耗的页面数量最少。 原因分析：树状数据结构在扩展时，高层节点越少，底层产生的分支总数就越少。
如果放在顶层（顶级6位，第二级8位，第三级8位）：顶级有1个页表（大小为256字节），它最多指向64个二级页表；这64个二级页表最多指向 $64 \times 256 = 16384$ 个三级页表。极端填满情况下，总页表数为 $1 + 64 + 16384 = 16449$ 。
如果放在底层（顶级8位，第二级8位，第三级6位）：顶级有1个页表，它最多指向256个二级页表；这256个二级页表最多指向 $256 \times 256 = 65536$ 个三级页表。总页表数为 $1 + 256 + 65536 = 65793$ 。因此，将较小的页表放在顶层可以极大地减少所需的内存开销。

第三题解析

【英文原题】 3. Assume that a task is divided into four equal-sized segments and that the system builds an eight-entry page descriptor table for each segment. Thus, the system has a combination of segmentation and paging. Assume also that the page size is 2 Kbytes. a. What is the maximum size of each segment? b. What is the maximum logical address space for the task? c. Assume that an element in physical location 00021ABC is accessed by this task. What is the format of the logical address that the task generates for it? What is the maximum physical address space for the system?

【中文翻译】 3. 假设一个任务被划分为四个大小相等的段，并且系统为每个段构建了一个包含8个表项的页描述符表。因此，系统采用了分段和分页相结合的方式。假设页面大小为 2KB。 a. 每个段的最大大小是多少？ b. 该任务的最大逻辑地址空间是多少？ c. 假设该任务访问了物理位置 00021ABC 中的一个元素。该任务为其生成的逻辑地址格式是什么？系统的最大物理地址空间是多少？

【深入解析】

a. 每个段的最大大小 每个段的页表有8个表项，这意味着每个段最多包含8个页面。每个页面大小为 2KB。所以每个段的最大大小 = 8 个页面 $\times$ 2 KB/页面 = 16 KB。
b. 最大逻辑地址空间 任务被分为4个段。最大逻辑地址空间 = 4 个段 $\times$ 16 KB/段 = 64 KB。
c. 逻辑地址格式与物理地址空间逻辑地址格式： 逻辑地址空间为64KB，总共需要 $\log_2(64 \times 1024) = 16$ 位。具体分配如下：
段号 (Segment Number)：共有4个段，需要 $\log_2(4) =$ 2位。
页号 (Page Number)：每个段有8个页面，需要 $\log_2(8) =$ 3位。
页内偏移量 (Offset)：页面大小为2KB（ $2^{11}$ 字节），需要 11位。
格式为：2位段号 + 3位页号 + 11位偏移量（共16位）。

最大物理地址空间： 物理地址给出的示例是十六进制数 00021ABC。这个数有8位十六进制字符，每个十六进制字符占用4个二进制位，因此该物理地址长度为 $8 \times 4 = 32$ 位。最大物理地址空间 = $2^{32}$ 字节 = 4 GB。

第四题解析

【英文原题】 4. Four page frames in main memory. The following page trace occurs: 1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3 a. Show the successive pages residing in the four frames using the LRU replacement policy. Compute the hit ratio in main memory. Assume that the frames are initially empty. b. Repeat part (a) for the FIFO replacement policy. c. Compare the two hit ratios and comment on the effectiveness of using FIFO to approximate LRU with respect to this particular trace.

【中文翻译】 4. 主存中有四个页框。发生以下页面访问轨迹：1, 0, 2, 2, 1, 7, 6, 7, 0, 1, 2, 0, 3, 0, 4, 5, 1, 5, 2, 4, 5, 6, 7, 6, 7, 2, 4, 2, 7, 3, 3, 2, 3 a. 使用LRU（最近最少使用）替换策略显示连续驻留在四个页框中的页面。计算主存中的命中率。假设页框最初为空。 b. 对于FIFO（先进先出）替换策略，重复部分(a)。 c. 比较两种命中率，并评论针对此特定轨迹使用FIFO来近似LRU的有效性。

【深入解析】 页面访问总次数为 33 次。内存有 4 个页框。

a. LRU (Least Recently Used) 策略：替换最长时间未被访问的页面
1: 未命中 1
0: 未命中 1, 0
2: 未命中 1, 0, 2
2: 命中 1, 0, 2
1: 命中 0, 2, 1
7: 未命中 0, 2, 1, 7
6: 未命中 2, 1, 7, 6 (替换最久未用的0)
7: 命中 2, 1, 6, 7
0: 未命中 1, 6, 7, 0 (替换最久未用的2)
1: 命中 6, 7, 0, 1
2: 未命中 7, 0, 1, 2 (替换最久未用的6)
0: 命中 7, 1, 2, 0
3: 未命中 1, 2, 0, 3 (替换最久未用的7)
0: 命中 1, 2, 3, 0
4: 未命中 2, 3, 0, 4 (替换最久未用的1)
5: 未命中 3, 0, 4, 5 (替换最久未用的2)
1: 未命中 0, 4, 5, 1 (替换最久未用的3)
5: 命中 0, 4, 1, 5
2: 未命中 4, 1, 5, 2 (替换最久未用的0)
4: 命中 1, 5, 2, 4
5: 命中 1, 2, 4, 5
6: 未命中 2, 4, 5, 6 (替换最久未用的1)
7: 未命中 4, 5, 6, 7 (替换最久未用的2)
6: 命中 4, 5, 7, 6
7: 命中 4, 5, 6, 7
2: 未命中 5, 6, 7, 2 (替换最久未用的4)
4: 未命中 6, 7, 2, 4 (替换最久未用的5)
2: 命中 6, 7, 4, 2
7: 命中 6, 4, 2, 7
3: 未命中 4, 2, 7, 3 (替换最久未用的6)
3: 命中 4, 2, 7, 3
2: 命中 4, 7, 3, 2
3: 命中 4, 7, 2, 3
LRU结果：总命中次数 = 16次。命中率 = 16 / 33 $\approx$ 48.48%。
b. FIFO (First-In-First-Out) 策略：替换最早进入内存的页面
1: 未命中 1
0: 未命中 1, 0
2: 未命中 1, 0, 2
2: 命中 1, 0, 2
1: 命中 1, 0, 2
7: 未命中 1, 0, 2, 7
6: 未命中 0, 2, 7, 6 (替换最早进入的1)
7: 命中 0, 2, 7, 6
0: 命中 0, 2, 7, 6
1: 未命中 2, 7, 6, 1 (替换最早进入的0)
2: 命中 2, 7, 6, 1
0: 未命中 7, 6, 1, 0 (替换最早进入的2)
3: 未命中 6, 1, 0, 3 (替换最早进入的7)
0: 命中 6, 1, 0, 3
4: 未命中 1, 0, 3, 4 (替换最早进入的6)
5: 未命中 0, 3, 4, 5 (替换最早进入的1)
1: 未命中 3, 4, 5, 1 (替换最早进入的0)
5: 命中 3, 4, 5, 1
2: 未命中 4, 5, 1, 2 (替换最早进入的3)
4: 命中 4, 5, 1, 2
5: 命中 4, 5, 1, 2
6: 未命中 5, 1, 2, 6 (替换最早进入的4)
7: 未命中 1, 2, 6, 7 (替换最早进入的5)
6: 命中 1, 2, 6, 7
7: 命中 1, 2, 6, 7
2: 命中 1, 2, 6, 7
4: 未命中 2, 6, 7, 4 (替换最早进入的1)
2: 命中 2, 6, 7, 4
7: 命中 2, 6, 7, 4
3: 未命中 6, 7, 4, 3 (替换最早进入的2)
3: 命中 6, 7, 4, 3
2: 未命中 7, 4, 3, 2 (替换最早进入的6)
3: 命中 7, 4, 3, 2
FIFO结果：总命中次数 = 16次。命中率 = 16 / 33 $\approx$ 48.48%。
c. 命中率对比与评论 通过严格演算可以看出，针对这个特定的访问轨迹，FIFO和LRU的命中率是完全相同的（均为16/33）。评论：这表明在某些特定的内存访问模式下（例如工作集变化剧烈，或者存在淘汰旧页面的循环访问模式），最老的页面恰好也是最近最少使用的页面，此时FIFO可以作为LRU的极佳近似。FIFO的优势在于其实现极其简单（只需要维护一个队列指针），不需要像LRU那样在每次访问时都去更新时间戳或链表，从而大幅降低了系统开销。然而需要指出的是，FIFO存在Belady异常（分配更多内存页框时缺页率反而上升的现象），而LRU不存在。

第五题解析

【英文原题】 5. Assuming a page size of 4 Kbytes and that a page table entry takes 4 bytes, how many levels of page tables would be required to map a 64-bit address space, if the top level page table fits into a single page?

【中文翻译】 5. 假设页面大小为 4KB，且每个页表项占用 4 字节，如果顶级页表正好适合放在一个页面中，那么映射一个 64 位地址空间需要多少级页表？

【深入解析】

虚拟地址总长度 = 64位。
页面大小 = 4KB = $2^{12}$ 字节，因此页内偏移量占用 12位。
虚拟页号 (VPN) 长度 = $64 - 12 =$ 52位。我们需要用多级页表来映射这52位。
页表项大小 = 4字节（ $2^2$ 字节）。
一个页面最多可以容纳的表项数 = 页面大小 / 表项大小 = $2^{12} / 2^2 = 2^{10} = 1024$ 个表项。
因此，每一个占满一整页的页表，可以映射 $\log_2(1024) =$ 10位 的虚拟地址。
题目规定“顶级页表适合放在一个页面中”，为了使层级最少，除了顶级页表外，每一级都应该最大化利用（即每级映射10位）。
计算所需级数： $52 \div 10 = 5.2$ 。这意味着5级页表只能映射50位，不足以覆盖52位。因此我们必须向上取整，需要 6级页表。

具体划分：前五级每级映射10位，最顶级页表映射剩余的2位（顶级页表只有 $2^2=4$ 个表项，完全符合“正好适合放在一个页面中”的条件）。

第六题解析

【英文原题】 6. A process has four page frames allocated to it. (All the following numbers are decimal, and everything is numbered starting from zero). The time of the last loading of a page into each page frame, the time of last access to the page in each page frame, the virtual page number in each page frame, and the referenced (R) and modified (M) bits for each page frame are as shown (the times are in clock ticks from the process start at time 0 to the event not the number of ticks since the event to the present). Table data: Frame 0(VPN 2, Load 60, Ref 161, R 0, M 1), Frame 1(VPN 1, Load 130, Ref 160, R 1, M 0), Frame 2(VPN 0, Load 26, Ref 162, R 1, M 0), Frame 3(VPN 3, Load 20, Ref 163, R 1, M 1) A page fault to virtual page 4 has occurred at time 164.Which page frame will have its contents replaced for each of the following memory management policies? Explain why in each case. a. FIFO b. LRU c. Clock d. Optimal (Use the following reference string.) e. Given the aforementioned state of memory just before the page fault, consider the following virtual page reference string: 4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2 How many page faults would occur if the working set policy with LRU were used with a window size of 4 instead of a fixed allocation? Show clearly when each page fault would occur.

【中文翻译】 6. 分配给某个进程四个页框。（以下所有数字均为十进制，一切从零开始编号）。每个页框中页面的最后加载时间、最后访问时间、虚拟页号，以及每个页框的访问(R)位和修改(M)位如下所示（时间是从进程在时间0开始到事件发生的时钟滴答数，而不是从事件发生到现在的滴答数）。表格数据: 框0(页2, 载入60, 访问161, R=0, M=1), 框1(页1, 载入130, 访问160, R=1, M=0), 框2(页0, 载入26, 访问162, R=1, M=0), 框3(页3, 载入20, 访问163, R=1, M=1) 在时间164，发生了对虚拟页面4的缺页异常。对于以下每种内存管理策略，哪个页框的内容将被替换？请分别解释原因。 a. FIFO（先进先出） b. LRU（最近最少使用） c. Clock（时钟算法） d. Optimal（最佳算法） e. 假设在缺页之前的上述内存状态下，考虑引用串：4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2。如果使用窗口大小为4的LRU工作集策略而不是固定分配，会发生多少次缺页异常？清楚地说明每次缺页发生的时间。

【深入解析】 我们先整理一下当前在内存中的页面及其属性：

框0: 页2 (载入: 60, 访问: 161, R=0, M=1)
框1: 页1 (载入: 130, 访问: 160, R=1, M=0)
框2: 页0 (载入: 26, 访问: 162, R=1, M=0)
框3: 页3 (载入: 20, 访问: 163, R=1, M=1)
a. FIFO 策略：替换最早被装入内存的页面。比较四个页框的“载入时间(Time loaded)”，框3的时间最小（为20）。解释：所以 页框3 的内容将被替换。
b. LRU 策略：替换最长时间未被访问的页面。比较四个页框的“访问时间(Time referenced)”，框1的时间最小（为160，距离当前时间164最远）。解释：所以 页框1 的内容将被替换。
c. Clock (时钟) 策略：时钟算法扫描页框集合，寻找引用位(R bit)为0的页面进行替换。当前R位的情况是：框0(R=0)，框1(R=1)，框2(R=1)，框3(R=1)。无论时钟指针从哪里开始扫描，只要遇到R=1就将其清零并向后移动，遇到R=0则直接替换。因为框0是唯一一个当前R=0的页面。解释：所以 页框0 的内容将被替换。
d. Optimal (最佳) 策略：替换在未来最晚才会被访问到的页面。未来的引用序列是：4, 0, 0, 0, 2, 4, 2, 1, 0, 3, 2。当前内存里的页面是 2, 1, 0, 3。
页0在未来第2个被访问。
页2在未来第5个被访问。
页1在未来第8个被访问。
页3在未来第10个被访问。解释：因为页3在未来最晚被访问，所以 页框3 的内容将被替换。
e. 窗口大小为4的工作集策略：工作集策略中，窗口大小 $\Delta = 4$ 指的是包含最近 4次内存访问 的窗口。在时间164之前，最近的4次访问时间分别是163(页3)、162(页0)、161(页2)、160(页1)。所以初始窗口内容是 [1, 2, 0, 3]。工作集（去重后的页面集合）为 {1, 2, 0, 3}。接下来我们逐一跟踪未来的访问，窗口不断向前滑动，如果被访问的页面不在当前的工作集中，就会触发一次缺页异常：

访问 4: 窗口变为 [2, 0, 3, 4]，工作集 {2, 0, 3, 4}。4 不在原集合中，发生第1次缺页异常。
访问 0: 窗口变为 [0, 3, 4, 0]，工作集 {0, 3, 4}。0 在集合中，命中。
访问 0: 窗口变为 [3, 4, 0, 0]，工作集 {0, 3, 4}。0 在集合中，命中。
访问 0: 窗口变为 [4, 0, 0, 0]，工作集 {0, 4}。0 在集合中，命中。
访问 2: 窗口变为 [0, 0, 0, 2]，工作集 {0, 2}。2 不在集合中，发生第2次缺页异常。
访问 4: 窗口变为 [0, 0, 2, 4]，工作集 {0, 2, 4}。4 不在集合中，发生第3次缺页异常。
访问 2: 窗口变为 [0, 2, 4, 2]，工作集 {0, 2, 4}。2 在集合中，命中。
访问 1: 窗口变为 [2, 4, 2, 1]，工作集 {1, 2, 4}。1 不在集合中，发生第4次缺页异常。
访问 0: 窗口变为 [4, 2, 1, 0]，工作集 {0, 1, 2, 4}。0 不在集合中，发生第5次缺页异常。
访问 3: 窗口变为 [2, 1, 0, 3]，工作集 {0, 1, 2, 3}。3 不在集合中，发生第6次缺页异常。
访问 2: 窗口变为 [1, 0, 3, 2]，工作集 {0, 1, 2, 3}。2 在集合中，命中。结论：总共会发生 6次缺页异常。分别发生在访问首个页面4、页面2、第二个页面4、页面1、页面0和页面3时。

第七题解析

【英文原题】 7. Consider a paged logical address space (composed of 32 pages of 2 Kbytes each) mapped into a 1-Mbyte physical memory space. a. What is the format of the processor's logical address? b. What is the length and width of the page table (disregarding the "access rights"bits)? c. What is the effect on the page table if the physical memory space is reduced by half?

【中文翻译】 7. 考虑一个分页逻辑地址空间（由32个页面组成，每个页面2KB），将其映射到1MB的物理内存空间。 a. 处理器逻辑地址的格式是什么？ b. 页表的长度和宽度是多少（不考虑“访问权限”位）？ c. 如果物理内存空间减半，对页表有什么影响？

【深入解析】

a. 逻辑地址格式 逻辑地址空间共有32个页面。虚拟页号(VPN)需要 $\log_2(32) =$ 5位。每个页面大小为2KB（ $2^{11}$ 字节），所以页内偏移量需要 11位。总逻辑地址长度 = $5 + 11 = 16$ 位。 格式为：5位页号 + 11位页内偏移量。
b. 页表的长度和宽度

长度：页表的长度指的是页表中有多少个表项。因为逻辑地址空间有32个页面，所以页表长度为 32个表项。

宽度：页表的宽度指的是每个表项需要多少个二进制位来存储物理页框号。物理内存空间为 1MB = $2^{20}$ 字节。页面大小为 $2^{11}$ 字节。物理内存中的总页框数 = $2^{20} / 2^{11} = 2^9 = 512$ 个页框。因此，物理页框号需要 $\log_2(512) =$ 9位。所以宽度为 9位。

c. 物理内存减半的影响 如果物理内存减半，变为 512KB（ $2^{19}$ 字节）。新的总页框数 = $2^{19} / 2^{11} = 2^8 = 256$ 个页框。此时表示物理页框号所需的位数变为 $\log_2(256) =$ 8位。影响：页表的长度（表项数量）完全取决于逻辑地址空间，因此长度保持32个表项不变；但是由于物理页框数量减少，表项的宽度将减少1位（从9位减少到8位）。

第一题解析

第二题解析

第三题解析

第四题解析

第五题解析

第六题解析

第七题解析