计算机基础之虚拟内存概述

计基之虚拟内存

Author：onceday Date：2022年8月4日
漫漫长路，才刚刚开始。

1.引言

虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互。

三个重要的能力：

• 将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存上只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，高效地使用了主存。

• 为每个进程提供了一致的地址空间，从而简化了内存管理。

• 保护了每个进程的地址空间不被其他进程破坏。

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址（Physical Address）。

现代处理器使用虚拟寻址(virtual addressing) 的寻址形式。

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

虚拟内存系统会将虚拟内存分割为固定大小的块，即虚拟页(Virtual Page,VP)。物理内存也会被分割成物理页（Physical Page，PP），大小一般为4KB，被称为页帧（page frame）.

虚拟页面的集合有三个，互不相交：

• 未分配的：VM系统还未分配的页，未分配的块没有任何数据和他们相关联，因此也就不占任何磁盘。

• 缓存的：当前已缓存在物理内存中的已分配页。

• 未缓存的：未缓存在物理内存中的已分配的页。

内存不命中带来的处罚开销较大，因此程序优化在于尽可能使用局部性原理。

2.页表

虚拟内存系统通过页表(page table)来判定一个虚拟页是否缓存在DRAM中的某个地方。

页表存储在物理内存中。

每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表，维护或者更新其内容。

2.1 缺页(page fault)

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

在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)。

当有不命中发现时，才换入页面的这种策略称为按需页面调度（demand paging)。

为什么虚拟内存的存在不会大幅破坏程序性能：

程序有局部性原则，在任意一个时刻，程序总是趋向在一个较小的活动页面(active page)集合工作，这个集合叫做工作集(working set)，常驻集合(resident set)。初始开销比较大，当工作集页面调集到内存中之后，接下来的开销就很小了。

如果工作集的大小超出了物理内存的大小，那么程序将产生一种抖动(thrashing)的状态。

这会导致程序运行很慢。

2.2 虚拟地址空间

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

简化链接：

• 独立的地址空间允许每个进程的内存映像使用相同的基本格式。

简化加载：

• 虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。加载器不从磁盘到内存实际复制任何数据，只是将它们标记成未被缓存的虚拟页。
• 将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作内存映射(memory mapping)。

简化共享：

• 独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间共享的一致机制。

虚拟地址页面可以映射到同一个物理页面，已实现对共享代码，共享数据的高效利用。

在分配内存时，只要虚拟地址满足连续即可，实际物理页面分配可以任意分散分配。

2.2 虚拟内存限制内存访问

可以用过页表项的控制位，明确当前页面所需的权限，如内核模式可访问、只读、读/写等。如果违反了限制，将报出段错误。

2.3 虚拟地址翻译

页表基址寄存器(Page Table Base Register，PTBR)指向当前页表。

n位的虚拟地址包含两个部分，一个p位的虚拟页面偏移(Virtual Page Offset，VPO)，和一个(n-p)位的虚拟页号(Virtual Page Number，VPN)。

地址管理单元MMU利用虚拟页号VPN来选择页表条目PTE。

物理页面偏移(Physical Page Offset,PPO)和虚拟页面偏移VPO是相同的。

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

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

2. MMU生成PTE地址，并从高速缓存/主存请求得到它。

3. 高速缓存/主存向MMU返回PTE。

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

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

当页面未命中时的缺页请求：

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

2. MMU生成PTE地址，并从高速缓存/主存请求得到它。

3. 高速缓存/主存向MMU返回PTE。

4. PTE中的有效位为0，所以MMU触发了一次异常，传递CPU中的控制到操作系统内核中的缺页异常处理程序。

5. 缺页处理程序确定出物理内存中的牺牲页，如果这个页面已被修改，则将它写回到硬盘。

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

7. 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。因为此时虚拟页面已被缓存，所以接下来会命中。

2.4 利用翻译后备缓冲器(Translation Lookaside Buffer，TLB)

为了降低MMU查阅PTE时的时间消耗，在MMU中包括了一个关于PTE的小缓存。

用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟号提取出来的。

当TLB不命中时，也需要从L1缓存中取出相应的PTE。

2.5 多级页表

使用层次分明的页表结构有助于降低空间消耗。

例如，一级页表指向二级页表的一个集合，而二级页表再指向实际物理内存页的一个集合。

如果每个页表条目大小4字节，1024个条目组成一个二级页表，则二级页表代表4KB页面，1024个二级页表再组成一级页表，则只需1024个一级页表可代表4GB空间。

优势如下：

• 如果以及页表中的一个PTE是空的，那么相应的二级页表根本就不会存在，极大节约。

• 只有一级页表才需要总是在主存中，二级页表只有在经常使用时，才需要缓存在主存中。

现代64位系统一般使用多级页表，如core i7 使用4级页表：

前三级页表中条目的格式一样：

第四级页表的页表格式如下：

虽然是多级页表，但会使用硬件进行加速，比如翻译和虚拟地址和查找物理缓存，能同步开始。

2.6 Linux的虚拟内存区域

内核会为每个进程维护一个单独的任务模块，任务结构中的元素包括指向该内核运行该进程所需要的所有信息。

其中条目mm_struct描述了虚拟内存的当前状态：

• 包含指向第一级页表的基址，立即描述当前虚拟地址空间区域信息的一个链表。

当触发缺页异常时：

• 缺页处理程序会检查当前的虚拟地址是否合法。

• 当前的进程是否有访问、读写、执行当前地址页面的权限。

• 只有在缺页是由合法操作引起的情况下，才会进行页面更新。

2.7 内存映射(memory mapping)

linux通过将虚拟内存区域与一个磁盘上的对象(object)关联起来，以初始化这个虚拟内存区域的内容。

• linux文件系统的普通文件：一个区域可以映射到一个普通磁盘文件的连续部分，列入可执行目标文件。文件不是及时交换进物理内存，而是在CPU第一次引用时，按需调入。如果区域比文件区要大，那么就用零来填充这个区域的余下部分。

• 匿名文件：直接用二进制零覆盖牺牲页面，并更新页表，磁盘和内存之间没有实际的数据传输。这个也叫请求二进制零的页(demand-zero page)。

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

• 共享对象对所有进程都是可见的，修改会反应在原始对象上。

• 私有对象只对当前进程可见，一旦被修改，就按写时复制的原则，创建一个新的单独副本。

2.8 fork和execve

fork函数创建新进程的过程：

• fork被调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。将两个进程的每个页面都标记为只读，并且将两个进程中的每个区域结构都标记为私有的写时复制。

execve加载过程：

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

• 删除已存在的用户区域。删除当前进程虚拟地址的用户部分中已存在的区域结构。

• 映射虚拟区域。所有段都是私有对象、写时复制。bss段和堆栈区域直接映射匿名文件，请求二进制零。

• 映射共享区域。静态库、动态库文件等。

• 设置程序计数器。指向代码区域的入口点。

2.9 使用mmap函数创建用户级内存映射

#include 
#include 

void *mmap(void *start,size_t length,int prot,int flags,
            int fd,off_t offset);
1
2
3
4
5

mmap函数要求内核创建一个新的虚拟内存区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片(chunk)映射到这个新的区域。

连续的对象片大小为length字节，从距文件开始处偏移量为offset字节的地方开始。

start地址只是一个暗示，通常被定义为NULL。

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

• PROT_EXEC：这个区域内的页面由可以被CPU执行的指令组成。

• PROT_READ：这个区域内的页面可读。

• PROT_WRITE：这个区域内的页面可写。

• PROT_NONE：这个区域内的页面不能访问。

参数flags描述了被映射对象的类型：

• MAP_ANON标记位，那么被映射的对象就是一个匿名对象。相应的虚拟界面是请求二进制零的。

• MAP_PRIVATE表示被映射的对象是一个私有的、写时复制的对象。

• MAP_SHARED表示是一个共享对象。

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

#include 
#include 

int munmap(void *start, size_t length);#成功返回0，若出错返回-1
1
2
3
4

3.动态内存分配

使用动态内存分配器(dynamic memory allocator)。

动态内存分配器维护着一个进程的虚拟内存区域，称为堆(heap)。

有两种风格：

• 显示分配器(explicit allocator)，要求应用显式地释放任何分配的块。如c程序的malloc函数和free函数。c++的new和delete操作符。

• 隐式分配器(implicit allocator)，另一方面，要求分配器检测一个已分配块何时不再被程序使用，那么就释放这个块。也叫垃圾收集器(garbage collection)。诸如java，Lisp等。

3.1 malloc函数

#include 

void *malloc(size_t size);//成功返回已分配的指针，出错则为NULL。
1
2
3

该地址会为了可能包含的任何数据类型做对齐，在32位系统中，默认为8的倍数，在64位系统中，默认为16的倍数。

使用 sbrk函数可以直接移动当前内核的brk指针(堆指针)位置 。

#include 

void *sbrk(intptr_t incr);
1
2
3

使用free函数可以释放已分配的内存：

#include 

void free(void *ptr);
1
2
3

如果指针不是由堆分配的返回的，而对它使用了free函数，那么行为是未定义的，而且也不会返回任何信息。

3.2 显示分配器的要求和目标

以下是一些严格的约束条件：

• 处理任意请求序列。一个应用可以有任意的分配请求和释放请求序列，只要每个释放请求对应一个当前的已分配的块。

• 立即响应请求。不可以为了性能重新排列或者缓冲请求。

• 只使用堆。为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。

• 对齐块(对齐要求)。以便保存各种数据类型。

• 不修改已分配的块。分配器只能操作或者改变空闲块。压缩已分配块的技术是不允许使用的。

通常有两个性能指标，它们是相互冲突的：

• 最大化吞吐率。吞吐率定义为每个单位时间里完成的请求数。

• 最大化内存利用率。虚拟内存空间也是有限，受到磁盘速度的限制。

一般分配请求的最糟运行时间与空闲块的数量成线性关系，而一个释放请求的运行时间是个常数。

3.3 堆碎片化

碎片(fragmentation)现象，即虽有未使用的内存但不能用来分配内存，会造成堆的利用率降低。

有两种类型的碎片：

• 内部碎片。已分配块比有效载荷大时，通常是由于对齐会额外增加块大小。

• 外部碎片。是空闲内存虽然合计足够，但单独一个无法满足分配请求，此时就会额外申请虚拟内存。

3.4 分配器的数据结构

主要使用链表结构，具体方法参阅数据结构书籍或专业的操作系统书籍。

占位符

3.5垃圾收集器

可以使用有达图来说明，即堆中分配的节点，外部是否可以访问。

具体暂时不谈，可以参考McCarthy独创的Mark&Sweep(标记/清除)算法。

像c和c++这类指针宽松的语言，一般只能建立保守的垃圾收集器(conservative garbage collector)，即一些不可达节点被错误标记为可达！

4.C程序中常见的与内存有关的错误

1. 间接引用坏指针，如scanf("%d",x)忘记取地址。

2. 读未初始化的内存，不能假设堆内存被初始化为0。

3. 允许栈缓冲区溢出，需要检查缓冲区输入序列的大小。

4. 假设指针和它们指向的对象是相同大小的，如int和指针类型在32位系统上一样大，但是在64位上，是不一样的。

5. 造成错位错误，如数组越位访问和赋值。

6. 引用指针，而不是它所指向的对象。小心运算符的优先级(与*比较)。

7. 误解指针运算，指针运算ptr + 4 = (long int)ptr + 4 * sizeof(*ptr)。

8. 引用不存在的变量。函数的局部变量在返回后是处于未知的状态。

9. 引用空闲堆块中的数据。引用被释放了的堆块中的数据。

10. 引起内存泄露。忘记释放已分配的块，而在堆里创建垃圾时，就会发生这种情况。