Chapter 8 Cache(7)

这一节是讲解Virtual Memory and Paging的。被第六节整的有点不会，先来看看后面两节。 😪

中英对照

Why? (为什么需要虚拟内存?)
- Virtual memory allows a computer to use more memory than physically available by using disk space as an extension of RAM.
  (虚拟内存使计算机能够使用超过实际可用内存的内存，通过使用磁盘空间作为 RAM 的扩展。)
What? (虚拟内存是什么?)
- It is a memory management technique that gives an "idealized abstraction of the storage resources that are actually available on a given machine"
  (它是一种内存管理技术，提供了一个“理想化的存储资源抽象，这些资源在给定机器上实际可用”。)
Paging (分页)
- Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus eliminates the problems of fitting varying sized memory chunks into physical memory.
  (分页是一种内存管理方案，消除了物理内存连续分配的需求，从而消除了将不同大小的内存块适配到物理内存中的问题。)
One of the implementations of Virtual Memory (虚拟内存的实现之一)
- Paging allows processes to be divided into smaller, fixed-size chunks called "pages", which can then be loaded into any available memory location.
  (分页允许将进程分为较小的固定大小的块，称为“页”，这些块可以被加载到任何可用的内存位置。)

概述

两个问题需要解决：

当主内存（DRAM）不足以执行程序时怎么办？是否使用磁盘？如何使用？
- 如果计算机的主内存不足以运行程序，通常使用虚拟内存技术。通过将部分数据交换到硬盘（磁盘）上，允许程序使用比实际物理内存更多的内存。
如果想同时运行多个程序（进程）怎么办？如何加载它们？
- 为了能够同时运行多个程序，需要使用内存管理技术，如多任务处理、进程隔离和虚拟内存。操作系统将每个程序分配到独立的虚拟内存空间，并在物理内存中按需加载。

在虚拟内存之前的内存管理方法

叠加（Overlaying）

程序员必须将程序分为多个段，并利用局部性原理选择在程序执行期间保持在内存中的段。
手动完成这一过程非常繁琐。
确定叠加集很困难，特别是在考虑多程序（多任务）时。

示例：

假设有一个程序需要使用以下内存：

A: 20K
B: 50K
C: 30K
D: 20K
E: 40K
F: 30K

叠加方法的内存分配：

内存总量： 190K
驻留内存： 20K
叠加 0： 50K
叠加 1： 40K
内存总使用量： 110K

替代方法（100K）：

A(20K): 20K
B(50K)、D(20K)、E(40K): 50K
C(30K)、F(30K): 30K

总结： 在虚拟内存出现之前，叠加方法依赖于程序员手动管理内存，且效率低下。

虚拟内存

虚拟内存是什么

虚拟内存不是一种物理设备，而是一个抽象概念。
它是一种技术（抽象），通过使用磁盘扩展物理内存的表观大小，使得程序可以认为它拥有比实际物理内存更大的内存。
目标：每个进程都认为它拥有一个巨大的内存空间。

虚拟内存作为缓存工具

虚拟内存是存储在磁盘上的一组连续的字节数组。
这个数组的内容在物理内存中被缓存。

相关术语

物理内存： 计算机中实际可用的内存。
逻辑或虚拟内存： 操作系统允许程序认为它拥有的内存。
物理地址： 物理内存中的实际位置，标识实际存储位置。
逻辑或虚拟地址： 程序使用的常规地址，操作系统必须将其转换为物理地址。

虚拟内存的典型组织

数据、数据DMA传输： 物理地址与虚拟地址之间的映射。
MMU（内存管理单元）： 硬件将虚拟地址转换为物理地址，通过操作系统管理的查找表（页表）实现。

虚拟内存的好处

大地址空间： 通过虚拟地址到物理地址的映射，程序可以访问更大的内存空间。
简化地址重定位： 相同的程序可以在物理内存的任何位置运行。
减少启动程序的时间： 启动程序时不需要所有的代码和数据都加载到物理内存中。
减轻程序员的叠加管理负担： 虚拟内存自动管理主存和二级存储之间的两级内存层次结构。

虚拟内存的实现

实现方法

分页（Paging）
- 将程序的虚拟地址空间分割成固定大小的块，称为“页”（Page）。
- 主内存也被分割成固定大小的块，称为“页框”（Page Frame）。
- 每个虚拟页可以映射到任意的物理页框，允许非连续的物理内存分配。
分段（Segmentation）
- 将程序的虚拟地址空间分割成不同大小的段（Segment），每个段通常包含程序的不同部分，如代码段、数据段、堆栈段等。
- 每个段有一个独立的基地址和长度，可以动态地扩展或缩减。
分页与分段结合（Segmentation with Paging）
- 结合了分页和分段的优点。
- 程序的虚拟地址空间首先被分为段，然后每个段内再进行分页。
- 这样既可以管理程序的逻辑结构，又能通过分页提供灵活的内存管理。

分页（Paging）

虚拟内存和主内存的组织

页面（Page）：连续字的块。
页框（Page Frame）：可以容纳一个页面的主内存区域。

虚拟内存地址空间	主内存地址空间
页 0	页框 0
页 1	页框 1
页 2	页框 2
页 3	页框 3

分页基本概念

页面是在主内存和磁盘之间传输的基本单位。
页面通常大小为 2K 至 16K 字节，不能太小或太大。

地址结构

虚拟地址（Virtual Address）：由两个部分组成：
- 虚拟页号（高位）
- 偏移量（低位）：指定页面内某个字节的位置。
物理地址（Physical Address）：由两个部分组成：
- 物理页号（高位）
- 偏移量（低位）

页表（Page Table）

页表是一个包含页表项（PTEs）的数组，负责将虚拟页映射到物理页。
虚拟页号用作页表索引，查找该虚拟页的页表项。
页表存储在主内存中。
页表基址寄存器（Page Table Base Register）：指向页表在内存中的位置。

页表项（Page Table Entry）

页框号：物理页号或指向二级存储的指针。
有效位（Valid bit）：指示页面是否已加载到主内存。
修改位（Modify bit）：指示页面在主内存中是否已修改。
使用位（Use bit）：指示页面是否被最近使用过。
访问控制位（Access Control bit）：指定读、写、执行权限。

地址转换

虚拟地址通过页表转换为物理地址，过程由内存管理单元（MMU）完成。

分页命中与缺页

页面命中（Page Hit）：引用的虚拟内存字已经在主内存中。
缺页（Page Fault）：引用的虚拟内存字不在主内存中，需要从磁盘加载。

TLB（Translation Lookaside Buffer）

TLB 是一个小型缓存，包含页表的部分内容。
TLB命中（TLB Hit）：通过 TLB 可以直接获得物理地址，避免额外的内存访问。
TLB缺失（TLB Miss）：如果 TLB 中没有对应的条目，则需要访问页表。

TLB一致性

当操作系统更改页表内容时，必须同时使 TLB 中的相关条目无效。

页面替换算法

LRU（最近最少使用）：需要使用位来记录。
FIFO（先进先出）：最早进入内存的页面最先被替换。

写策略

回写（Write back）：修改的数据先写入内存，待需要时才写回磁盘。
直写（Write through）：每次修改都同步写入磁盘，不适用于虚拟内存。

内存碎片

内部碎片：由于最后一页可能未满，导致浪费空间。
- 如果页面大小为 n 字节，程序最后一页的平均浪费空间为 n/2 字节。

页面大小

选择页面大小需要权衡大页面和小页面的优缺点。
- 大页面的优点：
  - 页面表大小与页面大小成反比，较大的页面可以节省内存。
  - 较大页面的传输效率更高。
- 大页面的缺点：
  - 如果虚拟内存的连续区域大小不等于页面大小的倍数，会导致更多的内部碎片。

测验

Quiz (1)

问题1：以下关于虚拟内存的好处，哪一项是错误的？

A. 提供大地址空间
B. 减轻程序员的叠加存储负担
C. 解决内部碎片问题
D. 简化重定位

正确答案：C. 解决内部碎片问题

解析：

A. 提供大地址空间：虚拟内存通过将磁盘空间作为扩展，提供了比物理内存更大的地址空间，因此是正确的。
B. 减轻程序员的叠加存储负担：虚拟内存管理了内存与磁盘之间的数据交换，程序员不再需要手动处理叠加存储的问题，所以也是正确的。
C. 解决内部碎片问题：虚拟内存并不能解决内部碎片问题，尤其是当页面较大时，仍然会存在最后一页未被完全使用的情况，导致空间浪费，因此这项说法是错误的。
D. 简化重定位：虚拟内存使得程序可以在任何位置加载到内存中，因此简化了程序的重定位过程，选项正确。

总结：虚拟内存能够提供大地址空间、简化重定位并减轻叠加存储负担，但它并不解决内部碎片问题。

问题2：在分页系统中，以下哪一项是不正确的？

A. 当发生 TLB 未命中时，操作系统必须将请求的页面从磁盘复制到主存中
B. 将较大的页面从或到辅助存储传输，比传输较小的页面更高效
C. 分页系统存在称为内部碎片的问题
D. "写直达"（Write through）不适用于该系统

正确答案：A. 当发生 TLB 未命中时，操作系统必须将请求的页面从磁盘复制到主存中

解析：

A. 当发生 TLB 未命中时，操作系统必须将请求的页面从磁盘复制到主存中：这是错误的。发生 TLB 未命中时，操作系统并不直接将页面从磁盘复制到主存，而是先通过页表进行地址转换，查看该页面是否已经在内存中。如果页面不在内存中，则发生页面缺失（page fault），然后操作系统才会将页面从磁盘加载到内存。因此，正确的说法是页面缺失时才会涉及从磁盘加载数据。
B. 将较大的页面从或到辅助存储传输，比传输较小的页面更高效：这是正确的。较大的页面可以减少磁盘访问次数，减少传输开销。
C. 分页系统存在称为内部碎片的问题：这是正确的。在分页系统中，最后一页可能未被完全使用，从而产生内部碎片。
D. "写直达"（Write through）不适用于该系统：这是正确的。在虚拟内存系统中，"写直达"会导致每次修改数据时都需要更新主存和缓存，这样会增加开销，因此不适合虚拟内存。

总结：A 选项的描述是不准确的，发生 TLB 未命中时不直接从磁盘加载页面，必须经过页面表查找和可能的页面缺失过程。

问题 3：一个处理器使用 46 位虚拟地址，并且页面大小为 2MB。在虚拟地址中，哪个部分对应于“偏移”字段？

A. 最重要的 34 位
B. 最不重要的 12 位
C. 最重要的 25 位
D. 最不重要的 21 位

解析：

虚拟地址的总长度是 46 位，页面大小是 2MB。要计算偏移量所占的位数，我们可以先计算页面的大小：2MB = 2 × 1024 × 1024 字节 = 2^21 字节。所以，页面的偏移量需要 21 位来表示。
因此，虚拟地址中的 最不重要的 21 位 是“偏移”字段，用于标识页面内的具体位置。

正确答案：D. 最不重要的 21 位

问题 4：页面错误（Page Fault）是指 ______。

A. 计算机试图运行存储在硬盘上的指令
B. 计算机启动时使用的过程
C. 计算机在缺少设备驱动程序时发生的错误
D. 内存不足错误

解析：

页面错误发生在虚拟内存系统中，当程序访问的虚拟页面不在主存中时，操作系统会产生页面错误并加载所需的页面。
A. 计算机试图运行存储在硬盘上的指令：错误的描述，页面错误与硬盘指令无关。
B. 计算机启动时使用的过程：与页面错误无关。
C. 计算机在缺少设备驱动程序时发生的错误：也不属于页面错误。
D. 内存不足错误：页面错误是由于内存中缺少所需页面引起的，并不是内存不足的错误。

正确答案：D. 内存不足错误

问题 5：关于 TLB（Translation Lookaside Buffer），以下哪项是正确的？

A. 它是一个小缓存，包含了部分页表
B. 当发生 TLB 缺失时，操作系统必须从磁盘中将请求的页面复制到主存
C. TLB 缺失只能通过硬件处理
D. 它的内容是根据地址访问的

解析：

A. 它是一个小缓存，包含了部分页表：TLB 确实是一个小的缓存，其目的是加速虚拟地址到物理地址的转换。它存储页表中的一部分内容。
B. 当发生 TLB 缺失时，操作系统必须从磁盘中将请求的页面复制到主存：这描述的是页面错误（Page Fault）的情况，而不是 TLB 缺失。TLB 缺失时，操作系统只是从页表中获取页面映射，而不是从磁盘加载整个页面。
C. TLB 缺失只能通过硬件处理：虽然大部分 TLB 缺失是由硬件处理的，但操作系统也可以参与处理，比如更新 TLB。
D. 它的内容是根据地址访问的：这也是正确的，TLB 是通过虚拟地址的页面号来查找其内容的。

正确答案：A. 它是一个小缓存，包含了部分页表

问题 6：假设分页硬件与 TLB 的命中率为 90%。在 TLB 中找到的页号的总访问时间为 100 纳秒，未找到时的总访问时间为 200 纳秒。那么，平均访问时间是多少？

解析：平均访问时间（Average Access Time）可以通过以下公式计算：

$ = (TLB ) () + (1 - TLB ) () $

给定条件：

TLB 命中率 = 90% = 0.9
TLB 命中时的访问时间 = 100 纳秒
TLB 未命中时的访问时间 = 200 纳秒

代入公式：

$ = (0.9 ) + (0.1 ) = 90 + 20 = 110 $

正确答案：B. 110ns

问题 7： True or False? 翻译后备缓冲区（TLB）作为页表的缓存。

解析：

答案：True。TLB（Translation Lookaside Buffer）确实作为页表的缓存。它用来加速虚拟地址到物理地址的转换，通过缓存部分页表的内容，从而减少查找页表的次数。

问题 8：在分页系统中，选择较小页面大小的优缺点是什么？

优点：

较小的页面大小会导致更少的存储空间浪费，特别是当一个连续的虚拟内存区域的大小不是页面大小的整数倍时。

缺点：

页表的大小与页面大小成反比：较小的页面会导致页表变得较大，这会浪费内存。
从辅助存储器（如硬盘）传输较小的页面效率较低：当通过网络或磁盘传输较小的页面时，其传输效率通常不如较大的页面。

总结：

优点：减少内存浪费。
缺点：增加页表的开销，且较小页面的传输效率较低。

问题 9： 在什么情况下会发生页面错误？当发生页面错误时，操作系统会采取什么措施？

页面错误发生的情况：

页面错误发生在访问一个尚未加载到主内存的页面时。也就是说，当程序尝试访问的虚拟页面没有在物理内存中时，就会发生页面错误。

操作系统的处理步骤：

验证内存访问：操作系统会检查该内存访问是否合法。如果访问无效（如访问了不存在的页面），则会终止程序。
寻找空闲页框：如果访问是有效的，操作系统会查找一个空闲的页框（即主内存中的空闲空间）来加载所需的页面。
请求I/O操作：操作系统发出I/O请求，将所需的页面从磁盘（或其他辅助存储）读取到空闲的页框中。
更新页表：I/O操作完成后，操作系统会更新进程的页表，将该页面标记为已加载到内存。
重新执行指令：更新完成后，操作系统会让程序重新执行触发页面错误的指令。

总结：

页面错误发生在访问未加载到内存的页面时。
操作系统处理页面错误的流程包括验证访问、寻找空闲页框、执行I/O操作、更新页表并重新执行指令。