物理和虚拟寻址

物理地址PA、虚拟地址VA、内存管理单元MMU（利用存放在主存中的查询表来动态地翻译虚拟地址，该表的内容由操作系统管理）。

地址空间

非负整数地址的有序集合。

目前x86使用39位物理地址空间、49位虚拟地址空间。

虚拟内存作为缓存的工具

VM系统通过将虚拟内存分割为大小为$P=2^p$字节的虚拟页来处理，同样地，物理内存也被分割为大小为P的物理页（页帧）。

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

• 未分配的
• 缓存的
• 未缓存的

DRAM缓存的组织结构

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

在存储层次结构中，DRAM缓存的位置对它的组织结构有很大的影响。DRAM比SRAM慢大约10倍，磁盘比DRAM慢大约100000倍。DRAM缓存的不命中（缺页）比SRAM缓存的不命中要昂贵的多。

与硬件对SRAM缓存相比，操作系统对DRAM缓存使用了更复杂精密的替换算法。对磁盘的访问时间很长，DRAM缓存总是使用写回，而不是直写。

页表

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

页表就是一个页表条目（PET）的数组。虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。假设每个PTE由一个有效位和一个n位地址字段组成的。有效位表明该虚拟页当前是否被缓存在DRAM中。

页命中

页面缓存在DRAM缓存中。

缺页

DRAM缓存不命中称为缺页。

在磁盘和内存之间传送页的活动叫作交换或页面调度。只有当不命中发生时，才换入页面，这种策略称为按需页面调度。

所有现代系统都采用按需页面调度的方式。

局部性

局部性原理保证了在任意时刻，程序将趋向于在一个较小的活动页面集合上工作，这个集合称为工作集或常驻集。

只要程序具有良好的时间局部性，虚拟内存系统就能工作得相当好。如果工作集的大小超出了物理内存的大小，程序将产生一种不幸的抖动状态，这时页面将不断地换进换出。

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

虚拟内存大大简化了内存管理，并提供了一种自然的保护内存的方法。

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

多个虚拟页面可以映射到同一个共享的物理页面上。

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

简化链接

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

一个给定的Linux系统上的每个进程都使用类似的内存格式。对于64位地址空间，代码段总是从虚拟地址0x400000开始。数据段跟在代码段后，中间有一段符合要求的对齐空白。栈占用用户地址空间最高的部分，并向下生长。

这样的一致性简化了链接器的设计和实现。允许链接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置的。

简化加载

虚拟内存使得很容易向内存中加载可执行文件和共享对象文件。要把目标文件中.text和.data节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，把它们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。加载器从不从磁盘到内存实际复制任何数据。在每个页被初次引用时，要么是CPU取指令时引用的，要么是一条正在执行的指令引用一个内存位置时引用的，虚拟内存系统会按照需要自动地调入数据页。

将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称为内存映射。Linux提供一个称为mmap的系统调用，允许应用程序自己做内存映射。详见后面小节。

简化共享

一般情况下，每个进程都有自己私有的代码、数据、堆以及栈区域，是不和其他进程进行共享的。但在另一些情况下，需要进程来共享数据和代码。例如，每个进程必须调用相同的操作系统内核代码，操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面，从而安排多个进程共享这部分代码的一个副本。

简化内存分配

虚拟内存为用户进程提供了一个简单的分配额外内存的机制。当一个运行在用户进程的程序要求额外的堆空间时（调用malloc），操作系统分配一个适当数字大小的连续的虚拟内存页面，并将其映射到物理内存中任意位置的k个任意的物理页面。

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

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

例如：

每个PTE添加了三个许可位：

• SUP位：进程是否必须运行在内核（超级用户）模式下才能访问该页
• READ位和WRITE位控制对页面的读和写访问

如果一条指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。

地址翻译

页面命中时CPU硬件执行的步骤：

• 处理器生成一个虚拟地址，将其传送给MMU
• MMU生成PTE（Page Table Entry）地址，并从高速缓存/主存请求得到它
• 高速缓存/主存向MMU返回PTE
• MMU构造物理地址，并把它传送给高速缓存/主存
• 高速缓存/主存返回所请求的数据字给处理器

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

• 第1-3步：与页面命中时的前三步相同
• PTE中的有效位为0，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。
• 缺页处理程序确定出物理内存中的牺牲页，如果该页面已经被修改，则把它换出到磁盘。
• 缺页处理程序页面调入新的页面，并更新内存中的PTE。
• 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。CPU将引起缺页的虚拟地址重新发送给MMU。虚拟页面现在缓存在物理内存中，所以就会命中。

结合高速缓存和虚拟内存

在任何既使用高速缓存SRAM又使用虚拟内存的系统中，一般使用物理内存来访问高速缓存。

使用物理内存，多个进程同时在高速缓存中由存储块和共享来自相同虚拟页面的块非常简单。并且高速缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。

利用TLB加速地址翻译

多级页表

用来压缩页表的常用方法是使用层次结构的页表。

案例研究：Linux虚拟内存系统

Linux为每个进程维护了一个单独的虚拟地址空间。内核虚拟内存位于用户栈之上。

下图中为一个Linux进程的虚拟内存。

内核虚拟内存包含内核中的代码和数据结构。内核虚拟内存的某些区域被映射到所有进程共享的物理页面。例如，每个进程共享内核的代码和全局数据结构。内核虚拟内存的其他区域包含每个进程都不相同的数据，比如，页表、内核在进程的上下文执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

Linux虚拟内存区域

Linux将虚拟内存组织成一些区域（又称段）的集合。一个区域就是已存在的虚拟内存的连续片。代码段、数据段、堆、共享库以及用户栈都是不同的区域。每个虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。区域很重要，因为其允许虚拟地址空间有间隙。

下图强调了记录一个进程中虚拟内存区域的内核数据结构。内核为系统中的每个进程维护一个单独的任务结构task_struct。任务结构中的元素包含或指向内核运行该进程所需要的所有信息（如PID、指向用户栈的指针、可执行目标文件的名字以及程序计数器）。

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

一个具体区域的区域结构包含以下字段：

• vm_start：指向该区域的起始
• vm_end：指向该区域的结尾
• vm_port：描述这个区域内包含的所有页的读写许可权限
• vm_flags：描述这个区域内的页面是与其他进程共享的还是这个进程私有的
• vm_next：指向链表中下一个区域的结构

Linux缺页异常处理

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

• 判断虚拟地址A是否合法？即A是否在某个区域结构定义的区域内。为了找到答案，缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end作比较。如果该指令不合法，则触发一个段错误，从而终止该进程。由于一个进程可以创建任意数量的新虚拟内存，因此顺序搜索链表的开销可能很大，Linux在链表中构建一棵树，并在这棵树上查找。
• 试图进行的内存访问是否合法？即进程是否有读、写或执行这个区域内页面的权限。如果试图进行的访问是不合法的，缺页处理程序就会触发一个保护异常，从而终止这个进程。
• 此时内核知道这个缺页是由于对合法的虚拟内存进行合法的操作造成的。这样进行处理：选择一个牺牲页面，如果该页面被修改过，则将其交换出去，换入新的页面并更新页表。当缺页处理程序返回时，CPU重新启动引起缺页的指令，这条指令再次发送A到MMU。此时MMU就能正常翻译A，不会再产生缺页中断。

内存映射

内存映射：Linux通过一个虚拟内存区域与一个磁盘上的对象关联起来，以初始化这个虚拟内存区域的内容。虚拟内存区域可以映射到两种类型的对象中的一种：

• Linux文件系统中的普通文件
• 匿名文件

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件swap file之间换来换去。交换文件也叫做交换空间或交换区域。

共享对象

许多程序要访问只读运行时库代码的相同副本，例如每个C程序都需要来自标准C库的诸如printf这样的函数。如果每个进程都在物理内存中保存这些常用代码的副本，就是极端的浪费。

内存映射为我们提供了一种清晰的机制，用来控制多个进程如何共享对象。

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。

若一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么该进程对这个地址区域的任何写操作，对于那些同样将该共享对象映射到自己的虚拟内存的进程也是可见的。这些变化会反映在磁盘的原始对象上。另一方面，对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域的任何写操作都不会反映在磁盘的对象中。

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

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

通过这种延迟私有对象中的副本直到最后可能的时刻，写时复制最充分地使用了稀有的物理内存。

fork函数

fork函数创建一个带有自己独立虚拟地址空间的新进程。

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

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

execve函数

虚拟内存和内存映射在将程序加载到内存的过程中也扮演着关键的角色。

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

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

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

• 删除已存在的用户区域。
• 映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构，所有这些新区域都是私有的、写时复制的。代码和数据区域被映射为a.out文件中的.text和.data区。.bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。栈和堆区域也是请求二进制零的，初始长度为零。
• 映射共享区域。如果a.out程序与共享对象或目标链接（比如标准C库libc.so），那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
• 设置程序计数器PC。设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。下一次调度这个进程时，它将从这个入口点开始执行。Linux将根据需要换入代码和数据页面。

下图显示了加载器如何映射用户地址空间区域。

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

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

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

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

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

参数prot包含描述新映射的虚拟内存区域的访问权限位：

• PROT_EXEC
• PROT_READ
• PROT_WRITE
• PROT_NONE

参数flag由描述被映射对象类型的位组成。

munmap函数删除虚拟内存的区域：

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

int munmap(void *start, size_t length);

删除从虚拟地址start开始的，由接下来length字节组成的区域。

动态内存分配

动态内存分配器维护着一个进程的虚拟内存区域，称为堆。对于每个进程，内核维护着一个变量brk，指向堆的顶部。

分配器将堆视为一组不同大小的块的集合，每个块就是一个连续的虚拟内存片，要么是已分配的，要么是空闲的。

分配器有两种基本风格：

• 显式分配器：要求应用显式地释放任何已有的块。C标准库提供称为malloc程序包的显式分配器，C程序通过调用malloc分配内存，通过调用free释放一个块。C++通过new和delete分配和释放。
• 隐式分配器：又称为垃圾收集器。自动释放未使用的已分配的块的过程称为垃圾收集。

接下来主要讨论显式分配器的设计与实现。

malloc和free函数

C标准库提供成为malloc的显示分配器，程序通过调用malloc函数来从堆中分配块。

#include <stdlib.h>
void *malloc(size_t size);

malloc函数返回一个指针，指向大小至少为size字节的额内存块。

如果malloc遇到问题（例如程序要求的内存块比可用的虚拟内存还要大），那么它就返回NULL，并设置errno。

动态分配器还可以使用sbrk函数：

#include <unistd.h>
void *sbrk(intptr_t incr);

sbrk函数通过将内核的brk指针增加incr来扩展和收缩堆。如果成功则返回brk的旧值，否则返回-1，并将errno设置为ENOMEM。如果incr为零，那么sbrk就返回brk的当前值。

程序通过调用free函数来释放已分配的堆块。

#include <stdlib.h>
void free(void* ptr);

使用动态内存分配的原因

经常直到程序实际运行时，才知道某些数据结构的大小。

分配器的要求和目标

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

碎片

造成堆利用率很低的主要原因是一种称为碎片的现象，当虽然有未使用的内存但不能用来满足分配请求时，就会发发生这种现象。由以下两种碎片：

• 内部碎片：已分配块的大小和它们的有效荷载大小之差的和。内部碎片的数量取决于以前请求的模式和分配器的实现方式。比如分配器可能增加块大小以满足对齐约束条件。
• 外部碎片：当空闲内存合计起来足够满足一个分配请求，但没有一个单独的空闲块足够大可以来处理这个请求。如果不向内核请求额外的虚拟内存就无法满足这个请求。

外部碎片难以量化且不可能预测，所以分配器通常采用启发式策略来试图维持少量的大空闲块。

实现问题

要实现一个在吞吐率和利用率之间把握好平衡的分配器，要考虑以下问题：

• 空闲块组织
• 放置
• 分割
• 合并

隐式空闲链表

分配器需要一些数据结构，允许它来区分块边界，以及区别已分配和空闲块。大多数分配器将这些信息嵌入块本身。

一个块由一个字（4B）的头部、有效荷载以及可能的一些额外的填充组成。头部编码了这个块的大小以及这个块是已分配的还是空闲的。

放置已分配的块

应用请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大可以放置所请求快的空闲块。这种搜索方式是由放置策略确定的。常见的策略有首次适配、下一次适配和最佳适配。

分隔空闲块

分配器找到一个匹配的块后，就必须作出一个决策，就是分配这个空闲块中多少空间。一个选择是分配整个空闲块，但这种方式可能造成内部碎片。

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

获取额外的堆内存

如果不能请求到合适的空闲块，一个解决方法是合并那些在物理内存中相邻的空闲块来创建一个更大的块。如果还是不能生成一个足够大的块，那么分配器会调用sbrk函数，向内核请求额外的堆内存。

合并空闲块

任何分配器都必须合并相邻的空闲块，这个过程称为合并。分配器可以选择立即合并，就是在每次一个块被释放时，就合并所有相邻块。或者也可以选择推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有的空闲块。

立即合并对于某些请求模式而言，会产生一种形式的抖动，块会反复地合并，然后马上分割。

带边界标记的合并

边界标记技术允许在常数时间内进行对前面块的合并。这种思想是在每个块的结尾处添加一个脚部（footer，边界标记），其中脚部就是头部的一个副本。如果每个块包含一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。

显式空闲链表

分离的空闲链表

垃圾收集

未能释放已分配的块是一种常见的编程错误。

垃圾收集器是一种动态内存分配器，它自动释放不再需要的已分配块。这些块被称为垃圾。在一个支持垃圾收集的系统中，应用显式地分配块，但从不显式地释放它们。

这里讨论McCarthy独创的标记、清除算法，这个算法可以建立在已存在的malloc包的基础之上，为C/C++提供垃圾收集。

C语言常见的与内存有关的错误

间接引用坏指针

常见的是经典的scanf错误。

scanf("%d", &val);

使用scanf从stdin读取一个整数到一个变量。很容易错误地传递val的内容而不是它的地址：

scanf("%d", val);

scanf将把val的内容解释为一个地址，并试图将一个字写到这个位置。在最糟糕的情况下，val的内容对应于虚拟内存的合法读/写区域，于是我们就覆盖了这块内存，这在相当长一段时间后会造成灾难性后果。

读未初始化的内存

虽然bss内存位置总是被加载器初始化为零，但对于堆内存并不是这样。一个常见的错误就是假设堆内存被初始化为零。我们在使用堆内存的变量是要先将其初始化。

允许栈缓冲区溢出

如果一个程序不检查输入串的大小就写入栈中的目标缓冲区，那么这个程序就会有缓冲区溢出错误。例如：

void bufferflow() {
	char buf[64];
	gets(buf);
	
	return;
}

该函数就有缓冲区溢出错误，因为gets函数复制一个任意长度的串到缓冲区。为了纠正这个错误，必须使用fgets函数，该函数限制了输入串的大小。

假设指针和它们指向的对象是相同大小的

int **makeArray1(int n, int m) {
	int i;
	int **A = (int **)Malloc(n * sizeof(int));
	
	for (i = 0; i < n; i++) {
		A[i] = (int *)Malloc(m * sizeof(int));
	}
	
	return A;
}

该函数的目的是创建一个由n个指针组成的数据，每个指针都指向包含m个int的数组。然后创建A时错误地将sizeof(int *)写成了sizeof(int)，代码实际上创建的是一个int数组。

引用指针，而不是它所指向的对象

下面的函数，其目的是删除一个有size项的二叉堆里的第一项，然后对剩下的*size-1项重新建堆：

int *binheapDelete(int **binheap, int *size) {
	int *packet = binheap[0];
	binheap[0] = binheap[*size - 1];
	*size--;
	heapify(binheap, *size, 0);
	return(packet);
}

该函数错误地将(*size)--写作了*size--导致代码实际上减少的是指针自己的值，而不是它所指向整数的值。程序运行后很有可能发生的是，当程序在执行过程后很久才出现一个错误的结果。

误解指针的运算

指针的算数操作是以它们指向对象的大小为单位来进行的，这种大小单位不一定是字节。

引用不存在的变量

有时候不理解栈的规则的程序员可能会引用不合法的本地变量，例如：

int *stackref()
{
	int val;
	
	return &val;
}

该函数返回一个指针，指向栈中的一个局部变量，然后弹出它的栈帧，尽管&val仍然指向一个合法地址，但它已经不再指向一个合法的变量了。当以后在程序中调用其他函数时，内存将重用它们的栈帧。再后来，如果程序分配某个值给*p，那么其可能在修改另一个函数的栈帧中的一个条目，带来潜在的灾难性后果。

引用空闲堆块中的数据

一个相似的错误是引用已经被释放了的堆块中的数据。

引起内存泄漏

忘记释放已经分配的块，而在堆里创建了垃圾。

最后修改于 2022-01-12