1.物理和虚拟寻址

1.1 物理寻址

1.2 虚拟寻址

CPU 通过生成一个虚拟地址(Virtual Address,VA)来访问主存，这个虚拟地址在被送到内存之前先转换成适当的物理地址

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

• 虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。

• 和存储器层次结构中其他缓存一样，磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高层）之间的传输单元。

• VM 系统通过将虚拟内存分割为称为虚拟页(Virtual Page, VP) 的大小固定的块来处理这个问题。每个虚拟页的大小为P= 2^p字节。类似地，物理内存被分割为物理页(Physical Page, PP) , 大小也为P字节（物理页也被称为页帧(page frame)) 。

在任意时刻，虚拟页面的集合都分为三个不相交的子集

1. 未分配的:VM系统还未分配（或者创建）的页
2. 缓存的:当前已缓存在物理内存中的已分配页
3. 未缓存的：未缓存在物理内存中的已分配页。

上图展示了一个有8个虚拟页的小虚拟内存。虚拟页0和3还没有被分配，因此在磁盘上还不存在，虚拟页l4和6被缓存在物理内存中。页2、5和7已经被分配了，但是当前并未缓存在主存中。

2.1 DRAM 缓存的组织结构

使用术语SRAM缓存来表示位于CPU和主存之间的L1、L2和L3高速缓存，DRAM缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

DRAM比SRAM 要慢大约10 倍，而磁盘要比DRAM慢大约100000多倍。因此，DRAM缓存中的不命中比起SRAM 缓存中的不命中要昂贵得多，这是因为DRAM缓存不命中要由磁盘来服务，而SRAM缓存不命中通常是由于DRAM的主存来服务的。而且，从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约100000倍。归根到底，DRAM缓存的组织结构完全是由巨大的不命中开销驱动的。

2.2 页表

同任何缓存一样，虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在
DRAM 中的某个地方。如果是，系统还必须确定这个虚拟页存放在哪个物理页中。如果
不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理内存中选择一个牺牲
页，并将虚拟页从磁盘复制到DRAM 中，替换这个牺牲页。

这些功能是由软硬件联合提供的，包括操作系统软件、MMU(内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表(pagetable)的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容，以及在磁盘与DRAM 之间来回传送页。

虚拟地址空间中的每个页在页表中一个固定偏移处都有一个PTE（Page Table Entry,页表就是PTE数组）。如果设置了有效位，那么地址字段就表示DRAM 中相应的物理页的起始位置

上图展示了一个有8个虚拟页和4个物理页的系统的页表。四个虚拟页(VP1、VP2、VP4和VP7)当前被缓存在DRAM 中。两个页(VP0和VP5)还未被分配，而剩下的页(VP3和VP6)已经被分配了，但是当前还未被缓存

2.3 页命中

结合上图，考虑一下当CPU想要读包含在VP2中的虚拟内存的一个字时会发生什么（VP2被缓存在DRAM中）？

地址翻译硬件将虚拟地址作为一个索引来定位PTE2,并从内存中读取它。因为设置了有效位，那么地址翻译硬件就知道VP2是缓存在内存中的了。所以它使用PTE中的物理内存地址（该地址指向pp1中缓存页的起始位置），构造出这个字的物理地址。

2.4 缺页

DRAM缓存不命中称为缺页(page fault)。以上图中vp3为例

CPU引用了VP3中的一个字，VP3并未缓存在DRAM中。地址翻译硬件从内存中读取PTE3,从有效位推断出VP3未被缓存，并且触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在此例中就是存放在pp3中的VP4

接下来，内核从磁盘复制VP3到内存中的pp3,更新PTE3,随后返回。当异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重发送到地址翻译硬件，从而进行页命中流程，此时如图所示：

2.5 分配页面

下图展示了当操作系统分配一个新的虚拟内存页时对我们示例页表的影响，例如，调用malloc 的结果。在这个示例中，VP5的分配过程是在磁盘上创建空间并更新PTE5,使它指向磁盘上这个新创建的页面。

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

操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间

在这个示例中，进程i的页表将VPl映射到PP2, VP2映射到PP7,相似地，进程j的页表将VP1映射到PP 7,VP2映射到PP10,注意，多个虚拟页面可以映射到同一个共享物理页面上（共享内存？）

VM简化了链接和加载、代码和数据共享，以及应用程序的内存分配。

• 简化链接 :对于64位地址空间，代码段总是从虚拟地址0x400000开始。数据段跟在代码段之后，中间有一段符合要求的对齐空白。栈占据用户进程地址空间最高的部分，并向下生长。这样的一致性极大地简化了链接器的设计和实现，允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。
• 简化加载 ：虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射(memory mapping)。Linux提供一个称为mmap 的系统调用，允许应用程序自己做内存映射。
• 简化共享 ：操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包括单独的内核和C 标准库的副本， 如上图所示
• 简化内存分配 ：当一个运行在用户进程中的程序要求额外的堆空间时（如调用malloc 的结果），操作系统分配一个适当数字（例如k)个连续的虚拟内存页面，并且将它们映射到物理内存任意位置的K 个任意的物理页面（不需要连续物理内存）

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

提供独立的地址空间使得区分不同进程的私有内存变得容易。但是，地址翻译机制可以以一种自然的方式扩展到提供更好的访问控制。因为每次CPU生成一个地址时，地址翻译硬件都会读一个PTE,所以通过在PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单。

在这个示例中，每个PTE 中已经添加了三个许可位。SUP 位表示进程是否必须运行
在内核（超级用户）模式下才能访问该页。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些SUP为0的页面。READ 位和WRITE 位控制对页面的读和写访问。例如，如果进程i运行在用户模式下，那么它有读VP0和读写
VP1的权限。然而，不允许它访问VP2 。

如果一条指令违反了这些许可条件，那么CPU 就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell 一般将这种异常报告为"段错误(segmentation fault)"

5 地址翻译

形式上来说，地址翻译是一个N 元素的虚拟地址空间(VAS) 中的元素和一个M 元素
的物理地址空间(PAS) 中元素之间的映射

CPU中的一个控制寄存器，页表基址寄存器(Page Table Base Register, PTBR) 指向当前页表。n位的虚拟地址包含两个部分：一个p位的虚拟页面偏移(Virtual Page Offset, VPO)和一个(n—p)位的虚拟页号(Virtual Page Number, VPN) 。MMU利用VPN来选择适当的PTE 。例如， VPN0选择PTEO,VPN1选择PTE1,以此类推。将页表条目中物理页号(Physical Page Number, PPN) 和虚拟地址中的VPO串联起来，就得到相应的物理地址。注意，因为物理和虚拟页面都是P 字节的，所以物理页面偏移(Physical Page Off set, PPO) 和VPO是相同的。

此时两种情况：

页面命中

1. 处理器生成一个虚拟地址，并把它传送给MMU。
2. MMU生成PTE地址，并从高速缓存/主存请求得到它。
3. 高速缓存/主存向MMU 返回PTE。
4. MMU构造物理地址，并把它传送给高速缓存/主存。
5. 高速缓存/主存返回所请求的数据字给处理器。

缺页

1. 同上
2. 同上
3. 同上
4. PTE 中的有效位是零，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。
5. 缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘。
6. 缺页处理程序页面调入新的页面，并更新内存中的PTE。
7. 缺页处理程序返回到原来的进程，再次执行导致缺页的指令

页面命中完全是由硬件来处理的，与之不同的是，处理缺页要求硬件和操作系统内核协作完成

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

主要的思路是地址翻译发生在高速缓存查找之前。注意，页表条目可以缓存，就像其他的数据字一样。

5.2 利用TLB加速地址翻译

MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器(Translation Lookaside Buffer, TLB)

TLB是一个小的、虚拟寻址的缓存，每一行都保存着一个由单个PTE组成的块，TLB通常有高度的相联度。用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。

下图展示了当TLB 命中时（通常情况）所包括的步骤。关键点是，所有的地址翻译步骤都是在芯片上的MMU 中执行的，因此非常快。

1. CPU 产生一个虚拟地址。
2. MMU从TLB中取出相应的PTE。
3. MMU 将这个虚拟地址翻译成一个物理地址，并且将它发送到高速缓存/主存。
4. 高速缓存/主存将所请求的数据字返回给CPU

当TLB 不命中时， MMU 必须从L1 缓存中取出相应的PTE

5.3 多级页表

如果我们有一个32 位的地址空间、4KB的页面和一个4字节的PTE,那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个4MB的页表驻留在内存中。对于地址空间为64位的系统来说，问题将变得更复杂。

2^32 / 4096 * 4 = 4MB

用来压缩页表的常用方法是使用层次结构的页表,一个具体的示例如下：

假设32位虚拟地址空间被分为4KB的页，而每个页表条目都是4字节。还假设在这一时刻，虚拟地址空间有如下形式：内存的前2K个页面分配给了代码和数据，接下来的6K个页面还未分配，再接下来的1023个页面也未分配，接下来的1个页面分配给了用户栈，下图展示了我们如何为这个虚拟地址空间构造一个两级的页表层次结构。

一级页表中的每个PTE负责映射虚拟地址空间中一个4MB的片(chunk),这里每一片都是由1024个连续的页面组成的。比如， PTE0映射第一片，PTE1映射接下来的一片，以此类推。假设地址空间是4GB, 1024个PTE已经足够覆盖整个空间了。

如果片i中的每个页面都未被分配，那么一级PTEi就为空。例如，上图中，片2~7是未被分配的。然而，如果在片i中至少有一个页是分配了的，那么一级PTEi就指向一个二级页表的基址。例如，上图片0、1和8的所有或者部分已被分配，所以它们的一级PTE就指向二级页表。

二级页表中的每个PTE都负责映射一个4KB的虚拟内存页面，就像我们查看只有一级的页表一样。注意，使用4字节的PTE, 每个一级和二级页表都是4KB字节，这刚好和一个页面的大小是一样的

这种方法从两个方面减少了内存要求：

1. 如果一级页表中的一个PTE是空的，那么相应的二级页表就根本不会存在
2. 只有一级页表才需要总是在主存中；虚拟内存系统可以在需要时创建、页面调入或调出二级页表，这就减少了主存的压力；只有最经常使用的二级页表才需要缓存在主存中。

k级页表层次结构的地址翻译如下：

5.4 深入理解端到端的地址理解（示例）

示例运行在有一个TLB 和Ll cl-cache 的小系统上

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

则分析如下：

1. 每个页面64字节 = 2^6， 则vp与pp的低六位为VPO与PPO，vp高8位为VPN，pp高6为PPN

2. TLB 因为TLB有4个组，所以VPN的低2位就作为组索引(TLBI)。VPN中剩下的高6位作为标记(TLBT),

3. 页表，一共有2^8=256个页表条目(PTE)
   

4. 高速缓存,直接映射的缓存是通过物理地址中的字段来寻址的。因为每个块都是4字节，所以物理地址的低2位作为块偏移(CO) 。因为有16组，所以接下来的4位就用来表示组索引CCI)。剩下的6 位作为标记(CT) 。
   

此时假设CPU执行一条读地址0x03d4处自己的加载指令：

1. MMU 从虚拟地址中抽取出VPN(OxOF), 并且检查TLB, 看它是否因为前面的某个内存引用缓存了PTE OxOF的一个副本。TLB从VPN中抽取出TLB索引(Ox03)和TLB标记(Ox3),组Ox3的第二个条目中有效匹配，所以命中，然后将缓存的PPN(OxOD)返回给MMU。

2. 如果TLB不命中，那么MMU就需要从主存中取出相应的PTE。现在，MMU有了形成物理地址所需要的所有东西。它通过将来自PTE的PPN(OxOD)和来自虚拟地址的VPO(Ox14)连接起来，这就形成了物理地址(Ox354)。

3. 接下来， MMU发送物理地址给缓存，缓存从物理地址中抽取出缓存偏移CO(OxO)、缓存组索引CI(Ox5)以及缓存标记CT(OxOD)。

4. 因为组0x5中的标记与CT相匹配，所以缓存检测到一个命中，读出在偏移量CO处的数据字节(0x36), 并将它返回给MMU, 随后MMU将它传递回CPU。

6. Linux 虚拟内存系统

Linux 为每个进程维护了一个单独的虚拟地址空间，形式如上图，内核虚拟内存包含内核中的代码和数据结构。内核虚拟内存的某些区域被映射到所有进程共享的物理页面。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面

内核为系统中的每个进程维护一个单独的任务结构（源代码中的task_struct)。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息（例如，PID、指向用户栈的指针、可执行目标文件的名字，以及程序计数器）。

任务结构中的一个条目指向mm_struct,它描述了虚拟内存的当前状态。我们感兴趣的两个字段是pgd和mmap, 其中pgd 指向第一级页表（页全局目录）的基址，而mmap 指向一个vm_area_structs( 区域结构）的链表，其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将pgd存放在CR3控制寄存器中。

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

6.1 Linux 缺页异常处理

假设MMU在试图翻译某个虚拟地址A时，触发了一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序随后就执行下面的步骤：

1. 虚拟地址A是合法的吗?(A在某个区域结构定义的区域内吗),缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较。如果这个指令是不合法的，那么缺页处理程序就触发一个段错误，从而终止这个进程。
2. 试图进行的内存访问是否合法？（是否有读写执行权限）
3. 排除以上两种情况后，内核知道了这个缺页是由于对合法的虚拟地址进行合法的操作造成的，选择一个牺牲页面，如果这个牺牲页面被修改过，那么就将它交换出去，换入新的页面并更新页表。当缺页处理程序返回时，CPU重新启动引起缺页的指令，这条指令将再次发送A到MMU。这次，MMU就能正常地翻译A, 而不会再产生缺页中断了
   

7 内存映射

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

7.1 共享对象

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中。一个映射到共享对象的虚拟内存区域叫做共享区域。类似地，也有私有区域。

私有对象使用一种叫做写时复制(copy-on-write)的巧妙技术被映射到虚拟内存中

私有对象开始生命周期的方式基本上与共享对象的一样，在物理内存中只保存有私有对象的一份副本。比如，上图展示了一种情况，其中两个进程将一个私有对象映射到它们虚拟内存的不同区域，但是共享这个对象同一个物理副本。对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，并且区域结构被标记为私有的写时复制。只要没有进程试图写它自己的私有区域，它们就可以继续共享物理内存中对象的一个单独副本。然而，只要有一个进程试图写私有区域内的某个页面，那么这个写操作就会触发一个保护故障。

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

7.2 fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID 。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

7.3 execve函数

假设在当前进程中的程序执行了如下的execve 调用：

execve("a.out", NULL, NULL);

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

1. 删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。
2. 映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为a.out文件中的.text和.data区。bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。栈和堆区域也是请求二进制零的，初始长度为零。
3. 映射共享区域。如果a.out程序与共享对象（或目标）链接，比如标准C库libc.so,那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
4. 设置程序计数器(PC)。execve做的最后一件事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。

7.4 mmap函数

#include <unistd .h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot, int flags,int fd, off_t offset);

//返回：若成功时则为指向映射区域的指针，若出错则为MAP_FAILED(-1) 。

mmap函数要求内核创建一个新的虚拟内存区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片(chunk)映射到这个新的区域。连续的对象片大小为length字节，从距文件开始处偏移量为offset 字节的地方开始。

8 动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域，称为堆(heap)，假设堆是一个请求二进制零的区
域，它紧接在未初始化的数据区域后开始，并向上生长（向更高的地址）。对于每个进程，内核维护着一个变量brk( 读做"break"), 它指向堆的顶部。

分配器将堆视为一组不同大小的块(block)的集合来维护。每个块就是一个连续的虚拟内存片(chunk),要么是已分配的，要么是空闲的。本文只讨论显式分配器

8.1 分配器的要求和目标

显式分配器必须在一些相当严格的约束条件下工作：

• 处理任意请求序列
• 立即响应请求
• 只使用堆
• 对齐块（对齐要求）
• 不修改已分配的

8.2 碎片

有两种形式的碎片：

内部碎片(internal fragmentation)：在一个已分配块比有效载荷大时发生的，ex:分配器可能增加块大小以满足对齐约束条件。

外部碎片(external fragmentation):是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求时发生的

8.3 分配器实现

隐式空闲链表：
任何实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身

放置已分配的块：分配器执行这种搜索的方式是由放置策略(placement policy) 确定的。一些常见的策略是首次适配(first fit) 、下一次适配(next fit) 和最佳适配(best fit) 。

分割空闲块：一旦分配器找到一个匹配的空闲块，它就必须做另一个策略决定，那就是分配这个空闲块中多少空间。一个选择是用整个空闲块。虽然这种方式简单而快捷，但是主要的缺点
就是它会造成内部碎片。

然而，如果匹配不太好，那么分配器通常会选择将这个空闲块分割为两部分。第一部分变成分配块，而剩下的变成一个新的空闲块

获取额外的堆内存:如果分配器不能为请求块找到合适的空闲块,一个选择是通过合并那些在
内存中物理上相邻的空闲块来创建一些更大的空闲块,如果还是不满足，那么分配器就会通过调用sbrk 函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，
将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

合并空闲块：为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并(coalescing) 。这就出现了一个重要的策略决定，那就是何时执行合并。分配器可以选择立即合并(immediate coalescing),也就是在每次一个块被释放时，就合并所有的相邻块。或者它也可以选择推迟合并(deferred coalescing), 也就是等到某个稍晚的时候再合并空闲块

带边界标记的合井：在每个块的结尾处添加一个脚部(footer,边界标记），其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。