虚拟存储器
相关概念和基本工作原理
虚拟存储器的概念
虚拟存储器由操作系统和相关硬共同协作实现，涉及操作系统部分的内容（例如进程、存储器管理、虚拟地址空间、缺页处理等），会在操作系统课程中深入讨论，本课程主要介绍虚拟存储器所涉及到的硬件部分。
- 定义：指通过软硬件结合，使应用程序认为它拥有一个比实际物理内存大得多的连续地址空间的技术。它将一部分不常用的程序和数据存储在辅存中，只把常用的部分调入内存，实现内存的逻辑扩充。虚拟存储器技术是将主存作为辅存的缓存。
- 虚拟地址空间与物理地址空间：
- 虚拟地址（逻辑地址）：CPU 发出的地址，是程序在虚拟地址空间中的地址。
- 物理地址（实地址）：内存单元的实际地址。
- 地址转换：将虚拟地址转换为物理地址的过程由**内存管理单元（MMU）**完成。
- 局部性原理：
- 时间局部性：程序中的某条指令一旦执行，不久后可能再次执行；某个数据一旦被访问，不久后可能再次被访问。
- 空间局部性：一旦程序访问了某个存储单元，不久后其附近的存储单元也可能被访问。
- 虚拟存储器利用局部性原理，按需调入数据，提高内存利用率。
- 中断与异常：在地址转换过程中，若所需内容不在内存中，会产生缺页中断或缺段中断，由操作系统负责将其从辅存调入内存。
页式虚拟存储器
概述
- 特点：
- 页式虚拟存储器的缺页处理代价远大于 cache 数据缺失（未命中）的处理代价。因此，通常将页式虚拟存储器中主存与辅存之间交换的页面的大小设置得比较大，常见的页面大小为 4KB，也有更大容量的页面。
- 由于缺页处理的代价较大，因此，主存与辅存之间采用全相联映射方式，以提高命中率。
- 由于辅存的访问速度远小于主存的访问速度，因此在进行写操作时，应采取的写入策略为写回法，而不是写穿法。
地址映射和页表
页表结构
- 有效位 (Valid Bit)：指示本页表项对应的虚拟页是否已装入主存。若为 0，表示未装入或非法，访问将导致缺页中断。
- 脏位 (Dirty Bit / Modified Bit)：指示本页表项对应的虚拟页在主存中是否被修改过。若为 1，表示被修改，当该页被替换出主存时，需要将其写回辅存。
- 访问位 / 引用位 (Accessed Bit / Reference Bit)：指示本页表项对应的虚拟页在最近一段时间内是否被访问过（读或写）。用于页面置换算法（如 LRU、Clock 算法）判断页面的活跃程度。
- 访问权限位 (Access Control Bits)：指示本页表项对应的虚拟页的访问权限，如只读、可读写、可执行等。用于内存保护。
- 禁止缓存位 (Cache Disable Bit)：指示本页表项对应的虚拟页是否允许被高速缓存（Cache）缓存。对于某些特殊 I/O 区域或共享内存，可能需要禁止缓存以保证数据一致性。
- 物理页框号 (Physical Frame Number / PFN)：指示本页表项对应的虚拟页在主存中实际存放的物理页框（块）的编号。这是页表项最核心的内容，用于地址转换。
地址映射
- 物理地址 (Physical Address, PA)：由内存管理单元 (MMU) 最终访问主存的地址，是内存的真实地址。
- 物理页号 (Physical Page Number, PPN)：物理地址的高位部分，指示数据所在物理页框的编号。
- 物理页内偏移 (Physical Page Offset, PPO)：物理地址的低位部分，指示数据在物理页框内的具体位置。
- 虚拟地址 (Virtual Address, VA)：由 CPU 发出的地址，是程序看到的逻辑地址，通常是 32 位或 64 位。
- 虚拟页号 (Virtual Page Number, VPN)：虚拟地址的高位部分，指示数据所在虚拟页的编号。
- 虚拟页内偏移 (Virtual Page Offset, VPO)：虚拟地址的低位部分，指示数据在虚拟页内的具体位置。
访问流程
- CPU 生成一个虚拟地址 VA。
- 内存管理单元 (MMU) 将 VA 分解为虚拟页号 VPN和虚拟页内偏移 VPO。
- MMU 使用虚拟页号 VPN作为索引，查询页表 (Page Table)，找到对应的页表项 (Page Table Entry, PTE)。页表是操作系统为每个进程维护的重要进程控制信息，通常存放在该进程的内核地址空间中。
- 页表基址寄存器 (Page Table Base Register, PTBR) 存储当前进程页表的起始物理地址。
- 页表项的物理地址 = PTBR + VPN × PTE 大小。
- 检查页表项的有效位：
- 若有效位为 0，则发生缺页中断 (Page Fault)。此时，操作系统会接管控制权，缺页处理程序从磁盘（辅存）调入所需的虚拟页到主存（物理内存）中的一个空闲物理页框，并更新相应的页表项，将有效位设置为 1，并填入新的物理页框号 PPN。
- 若有效位为 1，则检查访问权限位。若权限不符，则产生保护性中断。
- 在缺页处理完成后，缺页处理程序返回到原来的进程，该进程中之前引起缺页的指令会重新启动（通常是从引起缺页的指令的开头重新执行）。
- 从页表项中取出物理页框号 (PPN)。
- 将取出的物理页框号 PPN与原虚拟地址的虚拟页内偏移 VPO（VPO 的长度与 PPO 的长度相同，因此直接用作 PPO）拼接，形成最终的物理地址 PA。
- PA = PPN << 页内偏移位数 + VPO
- MMU 使用生成的物理地址 PA访问主存。
结合 cache 的页式虚拟存储器的访问流程
-
理想：页表项和数据都在 cache 中
-
比较糟糕：页表项和数据都不在 cache 中
使用快表 TLB 加速地址转换
- 为了加快 MMU 进行虚拟地址到物理地址转换的速度，现代处理器内部都包含有一个转换后备缓冲器 （Translation Lookaside Buffer,TLB），专门用于缓存经常访问的页表项。
- 可将 TLB 看作是一个容量较小的 cache（只不过仅用于缓存经常访问的页表项，数据项仍在 cache 中缓存），由于 TLB 的访问速度远高于主存，因此通常将 TLB 表称为快表，相应地将主存中的页表称为慢表。
- 为了提高查找速度，TLB 一般采用全相联或组相联方式，出现 TLB 缺失时常采用 随机替换算法。
两种映射方式
- 全相联
- 组相联
基于 TLB 的访问过程
习题
基于 TLB 和 Cache 的内存访问流程
在现代计算机体系结构中，为了提高虚拟地址到物理地址的转换速度以及数据访问速度，系统采用了多级缓存机制，其中最关键的就是 TLB (Translation Lookaside Buffer, 快表) 和 Cache (高速缓存)。
核心原则
TLB 命中，则页一定命中。
原因: TLB 本质上是页表（Page Table）的一个高速缓存。如果一个页表项（Page Table Entry, PTE）的映射关系存在于 TLB 中，就意味着这个页面当前必定存在于物理内存（主存）中。如果该页面被换出到磁盘，操作系统会负责将对应的 TLB 条目置为无效。因此，不可能出现 TLB 命中但页面却不在主存（即缺页）的情况。
详细访存步骤
整个访存流程可以分为两大步：地址转换 和 数据获取。
第一步：地址转换 (查询 TLB 和页表)
当 CPU 发出虚拟地址后，MMU (内存管理单元) 开始进行地址转换。
- 查询 TLB
- 情况 A: TLB 命中 (TLB Hit)
- 流程: 直接从 TLB 中获取物理页号。
- 结果: 这是最快的情况。得到物理页号后，与虚拟地址中的页内偏移量组合，形成最终的物理地址。
- 后续: 直接进入第二步 数据获取。
- 情况 B: TLB 未命中 (TLB Miss)
- 流程: TLB 中没有找到对应的页表项，需要查询存放在主存中的页表 (Page Table)，这个过程称为 页表遍历 (Page Walk)。
- (优化): 在查询主存中的页表之前，系统会先检查 Cache 中是否缓存了该页表项。
- 如果在 Cache 中找到页表项，则可以更快地获取。
- 如果 Cache 中也没有，则必须访问主存来获取页表项。
- 获取页表项后，检查其状态：
- 子情况 B1: 页面命中 (Page Hit)
- 描述: 页表项有效，表明该页面已在物理内存中。
- 动作:
- 从页表项中得到物理页号，形成物理地址。
- 将该页表项更新到 TLB 中，以便下次访问时能够命中。
- 进入第二步 数据获取。
- 子情况 B2: 页面缺失 (Page Fault)
- 描述: 页表项无效或表明页面不在主存中，此时产生缺页异常。
- 动作:
- CPU 控制权转交给操作系统的缺页异常处理程序。
- 操作系统从磁盘中找到对应的页面，将其调入物理内存。如果内存已满，则执行页面置换算法。
- 更新页表，记录新的物理页号。
- 重新执行导致缺页的指令。这次执行时，会从 TLB Miss → Page Hit 的流程开始。
- 子情况 B1: 页面命中 (Page Hit)
- 情况 A: TLB 命中 (TLB Hit)
第二步：数据获取 (查询 Cache)
在通过第一步成功获得物理地址后，开始用此物理地址获取数据。
- 查询 Cache
- 情况 A: Cache 命中 (Cache Hit)
- 流程: 直接从 Cache 中读取数据，并返回给 CPU。
- 结果: 访存成功，流程结束。
- 情况 B: Cache 未命中 (Cache Miss)
- 流程: 需要从主存 (Main Memory) 中读取包含该物理地址的数据块。
- 动作:
- 从主存中读取数据。
- 将该数据块加载到 Cache 中（可能会替换掉 Cache 中的其他数据）。
- 将数据返回给 CPU。
- 结果: 访存成功，流程结束。
- 情况 A: Cache 命中 (Cache Hit)
命中/缺失组合可能性分析
| 序号 | TLB | 页 (Page) | Cache | 可能性 | 解释 |
|---|---|---|---|---|---|
| 1 | 命中 | 命中 | 命中 | 可能 | 最佳情况。地址转换快，数据获取也快。 |
| 2 | 命中 | 命中 | 缺失 | 可能 | 地址转换快，但数据不在 Cache 中，需访问主存。 |
| 3 | 缺失 | 命中 | 命中 | 可能 | TLB 未命中，通过查页表找到物理地址，幸运的是数据在 Cache 中。 |
| 4 | 缺失 | 命中 | 缺失 | 可能 | TLB 未命中，查页表得到物理地址，数据也不在 Cache 中，需访问主存。 |
| 5 | 缺失 | 缺失 | 缺失 | 可能 | 最差情况。发生缺页中断，需从磁盘调页，之后重新访存。数据自然也不在 Cache。 |
| 6 | 命中 | 缺失 | 缺失 | 不可能 | 违反核心原则：TLB 命中意味着页面一定在主存中，不可能缺页。 |
| 7 | 命中 | 缺失 | 命中 | 不可能 | 同上，TLB 命中时不可能发生缺页。 |
| 8 | 缺失 | 缺失 | 命中 | 不可能 | 如果发生缺页 (Page Fault)，说明数据根本不在物理内存中。由于 Cache 是主存的子集，数据也绝不可能在 Cache 中。只有在确定物理地址后才会查询 Cache。 |
- cache 缺失处理由硬件完成。
- 缺页处理由操作系统通过缺页异常处理程序来完成，即由软件完成。
- TLB 缺失处理，既可以用硬件也可以用软件来完成。若用软件完成，则操作系统通过专门的 TLB 缺失异常处理程序来完成。
习题
段式虚拟存储器
参考操作系统中关于段式虚拟存储器的内容，
- 定义：将程序的逻辑地址空间划分为若干个逻辑意义完整的“段”（Segment），每个段有独立的段名。段的大小可以不同。
- 特点：
- 分段是按程序的逻辑结构划分的，便于程序共享和保护。
- 段大小可变，易产生外部碎片。
- 内存分配和回收相对复杂。
- 虚拟地址结构：由段号 (S) 和段内偏移量 (W) 组成。
- 虚拟地址 = (S, W)
- 段表 (Segment Table)：存放段号与段的起始物理地址（基址）、段长、访问权限等信息。
- 段表寄存器 (Segment Table Base Register, STBR)：指向当前进程段表的起始地址，并记录段表长度。
- 访问流程：
- CPU 生成逻辑地址：由段号 S 和段内偏移量 W 组成。
- 根据 STBR 找到段表起始地址：利用段号 S 计算出对应段表项在内存中的地址。
- 访问内存中的段表：读取段表项，获取段的起始物理地址和段长。
- 检查越界和权限：
- 若段内偏移量 W 大于段长，则产生越界中断。
- 若权限不符，则产生保护中断。
- 若段表项无效（缺段），则产生缺段中断。操作系统介入，从辅存调入该段，更新段表，然后重新执行指令。
- 形成物理地址：将段的起始物理地址与段内偏移量 W 相加，形成最终的物理地址。
- 物理地址 = 段基址 + W
- 访问物理内存：根据物理地址访问主存中的数据。
段页式虚拟存储器
- 定义：结合了段式和页式存储管理的优点。先将程序按逻辑结构分段，再将每个段划分为固定大小的页。
- 特点：
- 兼顾了程序的逻辑结构（分段）和内存的利用率（分页）。
- 消除了外部碎片，但仍可能存在内部碎片。
- 地址转换需要两次查表（段表和页表）。
- 虚拟地址结构：由段号 (S)、段内页号 (P) 和页内偏移量 (W) 组成。
- 虚拟地址 = (S, P, W)
- 地址转换流程：
- CPU 生成逻辑地址 (S, P, W)。
- 查段表：根据段号 S，在段表中找到对应的段表项。段表项中存放的是该段的页表起始地址和段长。
- 检查 S 是否越界（段号是否合法）。
- 查页表：根据段表项中获得的页表起始地址，结合段内页号 P，在该段的页表中找到对应的页表项。页表项中存放的是物理页框号 F。
- 检查 P 是否越界（页号是否合法）。
- 检查页表项的有效位（是否缺页）。若缺页，产生缺页中断。
- 形成物理地址：将物理页框号 F 与页内偏移量 W 拼接，形成最终的物理地址。
- 物理地址 = (F, W)
- 访问物理内存。
- TLB 的应用：在段页式系统中，TLB 通常存储的是 (段号, 段内页号) 到 (物理页框号) 的映射，或者更复杂的 (段号, 段内页号, 物理页框号) 组合，以加速两次查表的过程，减少访存次数。