《深入理解计算机系统(CSAPP)》第9章虚拟内存 - 学习笔记

写在前面的话：此系列文章为笔者学习CSAPP时的个人笔记，分享出来与大家学习交流，目录大体与《深入理解计算机系统》书本一致。因是初次预习时写的笔记，在复习回看时发现部分内容存在一些小问题，因时间紧张来不及再次整理总结，希望读者理解。

---

《深入理解计算机系统(CSAPP)》第3章 程序的机器级表示 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第5章 优化程序性能 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第6章 存储器层次结构 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第7章 链接- 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第8章 异常控制流 - 学习笔记_友人帐_的博客-CSDN博客

《深入理解计算机系统(CSAPP)》第9章虚拟内存 - 学习笔记_友人帐_的博客-CSDN博客

---

第九章 虚拟内存

内存管理单元(Memory Management Unit, MMU)：专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

1. 地址空间

• 地址空间(address space)：一个非负整数地址的有序集合：{0, 1, 2, …}

• 线性地址空间(linear address space)：地址空间中的整数是连续的，则称为线性地址空间

• 物理地址空间(physical address sapce)：$M=2^m$个物理地址的集合{0, 1, 2, 3, …, M-1}

• 虚拟地址空间(virtual address space)：$N=2^n$个虚拟地址的集合{0, 1, 2, 3,…, N-1}

虚拟地址的思想：允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。

为什么要使用虚拟内存Virtual Memory(VM)?

• 有效使用主存：使用DRAM作为部分虚拟地址空间的缓存
• 简化内存管理：每个进程都使用统一的线性地址空间
• 独立地址空间：个进程不能影响其他进程的内存；用户程序无法获取特权内核信息和代码

2. 虚拟内存作为缓存的工具

虚拟内存：存放在磁盘上、有N个连续字节的数组。

磁盘上这个数组的内容被缓存在物理内存中(DRAM cache)，缓存块被称为页(页面大小为$P=2^p$)。

虚拟页分类：

• 未分配的：VM系统还未分配（或者创建）的页。未分配的块没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
• 缓存的：当前已缓存在物理内存中的已分配页。
• 未缓存的：未缓存在物理内存中的已分配页。

2.1 DRAM缓存的组织结构

DRAM若不命中，会产生巨大的不命中开销，因此采用：

• 大的虚拟页面。标准4KB，可达到4MB/页。
• DRAM缓存使用全相联映射：任何虚拟页都可以放置在任何物理页中。
• 不命中时使用了更复杂精密的替换算法。
• DRAM缓存使用写回法(磁盘访问时间长)。

2.2 页表(Page Table, PT)

存放**页表条目(Page Table Entry, PTE)**的数组，将虚拟页地址映射到物理页地址。DRAM中的每个进程都有自己的页表。

• 如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页。
• 如果没有设置有效位，
  • 那么一个空地址表示这个虚拟页还未被分配。
  • 否则，这个地址就指向该虚拟页在磁盘上的起始位置。

2.3 页命中

要访问的虚拟内存中的内容存在于物理内存中，即DRAM缓存命中。

2.4 缺页

DRAM缓存不命中称为缺页(page fault)。

缺页处理：

以访问VP3，选择VP4作为牺牲页为例：

1. CPU引用了VP3中的一个字，地址翻译硬件从内存中读取PTE3，有效位为0推断出VP3未被缓存，并且触发一个缺页异常。

2. 缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在PP3中的VP4。如果VP4已经被修改了，那么内核就会将它复制回磁盘。接着内核将VP4的页表条目有效位置0。

3. 接下来，内核从磁盘复制VP3到内存中的PP3，更新PTE3，随后异常处理程序返回，重新执行导致缺页的指令，然后页命中。

使用按需页面调度：只有当不命中时，才换入页面。

2.5 分配页面

内核在磁盘上分配一个新的虚拟内存页，并且将某个PTE指向这个新的位置(该虚拟页在磁盘上的起始位置)。

仅是分配，未载入内存，有效位是0。

2.6 虚拟内存效率高的原因

尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面(active page)集合上工作，这个集合叫做工作集(working set)或者常驻集合(resident set)。在初始开销，也就是将工作集页面调度到内存中之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。

如果工作集的大小超出了物理内存的大小，这时页面将不断地换进换出，叫做抖动(thrashing)，性能暴跌。

3. 虚拟内存作为内存管理的工具

核心思想：每个进程都拥有一个独立的虚拟地址空间。

页表将虚拟地址映射到物理地址，多个虚拟页面可以映射到同一个共享物理页面上。

• 简化链接

独立的地址空间允许每个进程的内存映像使用相同的基本格式，而不管代码和数据实际存放在物理内存的何处(结构一致)。

• 简化加载

使向内存中加载可执行文件和共享对象文件更容易。

要把目标文件中.text和.data节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，把它们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。

加载器从不从磁盘到内存实际复制任何数据。而是在每个页初次被引用时，由虚拟内存系统会按照需要自动地调入数据页。

• 简化共享

将不同进程中适当的虚拟页面映射到相同的物理页面，使得进程共享代码和数据，而不必在各进程私有区域内重复复制。

• 简化内存分配

当一个运行在用户进程中的程序要求额外的堆空间时（如调用ma1loc的结果），操作系统分配适当多个连续的虚拟内存页面，并且将它们映射到物理内存中任意位置的物理页面。

4. 虚拟内存作为内存保护的工具

通过在PTE上扩展许可位以对访问控制做权限限制。

（内核模式才可访问；可读；可写；可执行）

内存管理单元(MMU)每次访问数据都要检查许可位。如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell一般将这种异常报告为"段错误(segmentation fault)"。

5. 地址翻译

地址翻译就是由一个虚拟地址A获得其物理地址(DRAM)的过程。若结果未空，则说明虚拟地址A是无效的地址，或其对应的内容存储在磁盘上。

5.1 基于页表的地址翻译

• 页表基址寄存器CR3(Page Table Base Register, PTBR)：CR3控制寄存器指向第一级页表(L1)的起始位置。CR3的值是每个进程上下文的一部分，每次上下文切换时，CR3的值都会被恢复。
• 由VPN在页表中匹配PTE，获取PPN，与页偏移量PO拼接得到物理地址。
• VPO与PPO是相同的。

（1）页面命中时硬件执行步骤：

第1步：处理器生成一个虚拟地址，并把它传送给MMU。

第2步：MMU生成PTE地址(PTEA)，并从高速缓存/主存请求得到PTE。

第3步：高速缓存/主存向MMU返回PTE。

第4步：MMU构造物理地址，并把它传送给高速缓存/主存。

第5步：高速缓存/主存返回所请求的数据字给处理器。

• 整个过程完全由硬件处理。
• 需要访存两次(在高速缓存/主存中获取PTE以构造虚拟地址、由物理地址在高速缓存/主存找数据)。

（2）缺页异常时执行步骤：

第1步：处理器生成一个虚拟地址，并将其传送给MMU。

第2步：MMU生成PTE地址(PTEA)，并从高速缓存/主存请求得到PTE。

第3步：高速缓存/主存向MMU返回PTE。

第4步：PTE中的有效位是零，所以MMU触发缺页异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。

第5步：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。

第6步：缺页处理程序页面调入新的页面，并更新内存中的PTE。

第7步：缺页处理程序返回到原来的进程，再次执行导致缺页的指令。

• 由硬件、OS内核协作完成。
• 2x2次访存，(1次内存写入磁盘+1次磁盘写入内存)。

5.2 结合高速缓存和虚拟内存

高速缓存采用物理寻址，多个进程同时在高速缓存中有存储块和共享来自相同虚拟页面的块。

注意，页表条目可以缓存，就像其他的数据字一样。

5.3 利用快表TLB加速地址翻译

后备缓冲器(Translation Lookaside Buffer, TLB)。

目的：为了减少寻找PTE的开销。

TLB是MMU中一个小的、具有高相联度的缓存，实现虚拟页号VPN向物理页号PPN的映射，页数很少的页表可以完全放在TLB中。

（1）访问TLB

TLB的每行都保存着一个由单个PTE组成的块。MMU使用虚拟地址的VPN部分来访问TLB：将VPN划分为TLB的组选择和行匹配的标记字段。

（2）TLB的命中与不命中操作

注意：不命中时MMU从L1缓存中取出相应的PTE，并同时存放在TLB中、提供给MMU。

5.4 多级页表

目的：压缩页表的大小。

思想：虚拟地址空间中每个虚拟页不一定全部都分配，也即都还未被使用，也就没必要保存一条PTE在页表中占用空间。

（1）二级页表示例

• **基本情况：**假设32位虚拟地址空间被分为4KB的页，每个页表条目都是4字节。分配情况：内存的前2K个页面分配给了代码和数据，接下来的6K个页面还未分配，再接下来的1023个页面也未分配，接下来的1个页面分配给了用户栈。

**使用一级页表：**需要有$\frac{2^{32}}{2^{12}}=2^{20}=1M$个PTE。

使用二级页表：

一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的片(chunk)，这里每一片都是由1024个连续的页面组成的。一级页表中仅需要1K个PTE。

如果片$i$中的每个页面都未被分配，那么一级$PT{E}_i$就为空。如果在片$i$中至少有一个页是分配了的，那么一级$PT{E}_i$就指向一个二级页表的基址。二级页表中的每个PTE都负责映射一个4KB的虚拟内存页面。

• 为什么二级页表可以减少内存要求：

①如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在。

②只有一级页表才需要总是在主存中(因为使用最频繁)；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

（2）K级页表的地址翻译

• 虚拟地址被划分成为k个VPN和1个VPO，每个$VP{N}_i$都是一个到第$i$级页表的索引。

• 前k-1级页表中的每个PT都指向下一级的某个页表的基址。

• 第k级页表中的每个PTE包含某个物理页面的PPN，或者一个磁盘块的地址。

为了构造物理地址，在能够确定PPN之前，MMU必须访问k个PTE。对于只有一级的页表结构，PPO和VPO是相同的。

通过将不同层次上页表的PTE缓存起来，带多级页表的地址翻译并不比单级页表慢很多。

5.5 一个端到端的地址翻译示例

（1）基本假设

• 内存是按字节寻址的。
• 虚拟地址是14位长的(n=14)。
• 物理地址是12位长的(m=12)。
• 页面大小是64字节(P=64)。
• TLB是四路组相联的，总共有16个条目。
• L1d-cache是物理寻址、直接映射的，行大小为4字节，而总共有16个组。

（2）虚拟地址和物理地址的格式

每个页面大小为64B，需要6位地址做页内偏移量。故低6位为VPO、PPO，其余的作为VPN和PPN。

（3）TLB的格式

TLB是四路组相联的，总共有16个条目。故共有4组，需要2位作为组索引TLBI，其余作为标记TLBT。

(TLB是利用VPN的位进行虚拟寻址的)

（4）页表格式

采用单级页表。共需要$\frac{2^{14}}{2^6}=2^8=256$条PTE(虚拟页面大小/页面大小)

使用VPN来进行标识，VPN并不是页表的一部分，也不存储在内存中。

（5）Cache格式

由每行4字节，需要块内偏移量2位；

直接映射(1行就是1组)，共16个组，需要4位组索引。

使用物理地址寻址。

（6）读取示例

1. TLB读取命中示例

假设CPU读取0x03d4处的1个字节：

• CPU给出的即虚拟地址，故写出VPN和VPO，在VPN中划分出TLBT和TLBI：

• 先上TLB中去寻找第0x3组中有无标记为0x03的块，发现有且valid为1。故此时TLB命中，不存在缺页故障，找到PPN为0x0D

• MMU将来自PTE的PPN和来自虚拟地址的VPO连接起来，形成物理地址0x354。

• MMU将物理地址发给高速缓存L1，缓存从物理地址中划分出块内偏移CO(0x0)、组索引CI(0x5)和缓存表及CT(0x0D)。在Cache中找到对应块，且valid有效，读出在偏移量CO处的数据字节0x36返回给MMU，由MMU传递给CPU。

2. TLB不命中示例

如果TLB不命中，那么MMU必须从页表中的PTE中取出PPN。如果得到的PTE是无效的，那么就产生一个缺页，内核必须调入合适的页面，重新运行这条加载指令。

3. TLB命中但是Cache不命中

另一种可能性是PTE是有效的，但是所需要的内存块在缓存中不命中。

6. Core i7/Linux内存系统

6.1 虚拟内存系统

（1）四级页表层次结构

（2）地址翻译概况

为了简化，没有显示i-cache、i-TLB和L2统一TLB。

（3）各级页表中条目格式

第1~3级

每个条目引用一个4KB子页表。注意PS位

当P=1时：地址字段包含一个40位，对于的下一级页表的基地址。

当P=0时：前面保存的都是磁盘上的页表位置。

第4级

注意D位

P=1时：地址字段包括一个40位PPN，指向物理内存中某一页的基地址。

当P=0时：前面保存的都是磁盘上的页表位置。

（4）页表翻译过程

当MMU翻译每一个虚拟地址时：

• 每次访问一个页时，MMU都会设置A位，称为引用位(reference bit)。内核可以用这个引用位来实现它的页替换算法。
• 每次对一个页进行了写之后，MMU都会设置D位，又称修改位或脏位(dirty bit)。修改位告诉内核在复制替换页之前是否必须写回牺牲页
• 内核可以通过调用一条特殊的内核模式指令来清除引用位或修改位。

下图给出了Core i7MMU如何使用四级的页表来将虚拟地址翻译成物理地址。

36位VPN被划分成四个9位的片，每个片被用作到一个页表的偏移量。CR3寄存器包含L1页表的物理地址。VPN1提供到一个L1PET的偏移量，这个PTE包含L2页表的基地址。VPN2提供到一个L2PTE的偏移量，以此类推。

6.2 单个进程的虚拟地址空间

物理内存：方便内核访问物理内存中任何特定的位置。

（1）Linux虚拟内存区域

任务结构中的一个条目指向mm_struct，它描述了虚拟内存的当前状态：

• pgd指向第一级页表（页全局目录）的基址；
• mmap指向一个vm_area_structs(区域结构)的链表，其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将pgd存放在CR3控制寄存器中。

其中，每个vm_area_structs包含：

• vm_start：指向这个区域的起始处。
• vm_end：指向这个区域的结束处。
• vm_prot：描述这个区域内包含的所有页的读写许可权限。
• vm_flags：描述这个区域内的页面是与其他进程共享的，还是这个进程私有的（还描述了其他一些信息)。
• vm_next：指向链表中下一个区域结构。

（2）Linux缺页异常处理

缺页处理程序检查：

• 地址是否合法？搜索区域链表，确认地址在(合法的某个区域内？否则，非法->段错误
• 访问是否合法？有读、写或执行区域内页面的权限。否则，违反许可，触发保护异常->段错误

7. 内存映射

Linux通过将一个虚拟内存区域与一个磁盘上的对象(object)关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射(memory mapping)。

虚拟内存区域可以映射到两种类型的对象中的一种：

• 磁盘上的普通文件(eg,一个可执行目标文件)
  • 文件区被分成页大小的片，对虚拟页面初始化
• 匿名文件(内核创建，全是二进制零)
  • 首次访问该区域的虚拟页会引发缺页异常->分配一个全零的物理页(demand-zero pagei请求二进制零的页)
  • 一旦该页面被修改，即和其他页面一样

无论在哪种情况中，一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件(swap file)，之间换来换去。交换文件也叫做交换空间(swap space)或者交换区域。

7.1 再看共享对象

两个进程映射了同一个共享对象，两个进程的虚拟地址可以是不同的：

对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。只要没有进程试图写它自己的私有区域，它们就可以继续共享物理内存中对象的一个单独副本。

然而，只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。当故障处理程序注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的，它就会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限，当故障处理程序返回时，CPU重新执行这个写操作，现在在新创建的页面上这个写操作就可以正常执行了。

7.2 再看fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。

为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。

当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

即：

• 完全copy，标为只读，也使得能够共享虚拟内存对应的物理空间
• 写操作时，写时复制机制就会创建新页面，保持了每个进程的私有地址空间

7.3 再看execve函数

假设调用execve("a.out", NULL, NULL)

execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out程序有效地替代了当前程序。加载并运行a.out需要以下几个步骤：

• 删除当前进程虚拟地址的用户部分中的已存在的区域结构(页表、结构体、vm_area_strcut链表)。
• 映射私有区域(创建自己的新的区域结构)。为新程序的代码、数据、bss和栈区域创建新的区域结构，所有这些新的区域都是私有的、写时复制的。
  • 代码和数据区域被映射为a.out文件中的.text和.data区。
  • bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。
  • 栈和堆区域也是请求二进制零的，初始长度为零。
• 映射共享区域。将共享对象动态链接到这个程序，然后再映射到用户虚拟地址空间中的共享区域内。
• 设置程序计数器(PC)。设置当前进程上下文中的PC，使之指向代码区域的入口点。

7.4 使用mmap函数的用户级内存映射

Linux进程可以使用rmap函数来创建新的虚拟内存区域，并将对象映射到这些区域中。

void *mmap(void *start, int len, int prot, int flags, int fd, int offset)

从fd指定磁盘文件的offset处，映射len个字节到一个新创建的虚拟内存区域，该区域从地址stat处开始。

• start：虚拟内存的起始地址，通常定义为NULL
• prot：虚拟内存区域的访问权限
  • PROT_READ(可读)
  • PROT_WRITE(可写)
  • PROT_EXEC(可执行)
  • PROT_NONE(不能被访问)
• flags：被映射对象的类型
  • MAP_ANON(匿名对象)
  • MAP_PRIVATE(私有的写时复制对象)
  • MAP_SHARED(共享对象)
• 返回值：指向映射区域开始处的指针