漫游计算机系统之虚拟存储器

漫游计算机系统之虚拟存储器

1. 背景

一个典型的计算机系统如下图所示：

直接让应用使用硬件可能会导致滥用，并且应用需要处理复杂的硬件细节，容易出错。所以我们引入了操作系统来管理硬件资源，如下图所示：

操作系统为了让应用能更好更简单地使用硬件资源，对硬件资源做了进一步抽象，如下图所示：

2. 虚拟存储器

虚拟存储器把进程访问的存储设备抽象成一个巨大的字节数组，并对每个字节做唯一的地址编码。它提供了三个重要的功能：

1. 将主存看做存储在磁盘上的地址空间的高速缓存，从而提高了主存使用效率。
2. 为每个进程提供一致的地址空间，简化存储器管理。
3. 保护每个进程的地址空间不被其他进程破坏。

虚拟存储器在幕后自动地工作，无需应用程序员干涉，既然如此，为什么我们还需要去理解它呢？我想理解它可以带来以下几点好处：

1. 虚拟存储器是计算机系统的核心。它涉及计算机系统的所有层面（硬件异常、汇编器、链接器、加载器、共享对象、文件、进程），理解它将帮助我们更好地理解计算机系统是怎么工作的。
2. 虚拟存储器的功能非常强大。它赋予应用程序强大的功能，比如加载一个文件到存储器中，不需要任何显示拷贝。
3. 虚拟存储器非常危险。对于编写像c/c++程序，一个错误指针就可以让程序立即崩溃。理解它可以让我们更好地避免错误；或者当错误发生时，更好地定位问题所在。

3. 虚拟寻址

进程看到是虚拟地址，但是信息是存在物理内存上的，那么系统是如何用虚拟地址来获取对应物理内存的字节信息的呢？简单来说，可以分为三步：

1. CPU会把虚拟地址发送到MMU（Memory Management Unit）
2. MMU把虚拟地址翻译为物理地址后传送给主存
3. 主存把物理地址对应的字节传送给CPU

具体过程如下图：

3.1. 页表

MMU是如何把虚拟地址翻译为物理地址的呢？
OS会把物理内存、虚拟内存分为同样大小的块（linux默认为4k），并称之为页。同时为每个进程分配页表，页表是一个页表条目（PTE）数组，其中每个PTE记录了虚拟页与物理页的映射关系。

一个虚拟地址可以分为两部分：虚拟页号×××和虚拟页偏移量VPO。由于虚拟页与物理页是同样大小，因此虚拟页偏移量就是物理页偏移量；虚拟页号是页表中PTE的索引，对应的PTE中存储着物理页号和有效位（表示页面是否有对应物理页），这样MMU通过查询PTE就可以找到虚拟页对应的物理页，再加上虚拟页偏移量就可以得到物理地址，如下图：

3.2. 多级页表

如果每个进程只有一个页表（假设物理页大小为4k），那么对于32位系统，需要占用4M内存（每个PTE是4字节）；对于64位系统（实际只用了48位用来寻址），则需要256G内存，实在是太大了。为了解决这个问题，我们用多级页表，如下图：

在多级页表中，所有级别的页表大小是一样的，我们以linux的4级页表为例，则最少要4个页表，假设一个页表4k，总共16k；随着进程消耗内存的增长，第k级页表数目随之线性增长，由于其他级别的页表数目远远小于k级页表，因此总页表消耗内存页页接近于线性增长。由于进程实际占用内存大小远小于256T，因此页表消耗内存远小于一级页表。

4. 进程内存布局

从上述小结，我们知道每个进程都有一个独立的虚拟存储器空间，那么其布局是否有规律呢？我们以linux下的64位进程举例，见下图：

linux将用户虚拟存储器组织成一些段的集合。一个段就是已分配的虚拟存储器的连续片。只有存在于段的虚拟存储器页是可以被进程访问的。

#include <stdlib.h>

int main()
{
    char *p = (char*)malloc(1);
    while(1);
    return 0;
}

编译上述代码并运行，通过top获取此进程PID后，我们可以打开/proc/PID/maps文件查看进程的内存布局：

00400000-00401000 r-xp 00000000 fd:01 723899                             /home/wld/test/a.out
00600000-00601000 r--p 00000000 fd:01 723899                             /home/wld/test/a.out
00601000-00602000 rw-p 00001000 fd:01 723899                             /home/wld/test/a.out
0148c000-014ad000 rw-p 00000000 00:00 0                                  [heap]
7fb917267000-7fb917425000 r-xp 00000000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb917425000-7fb917625000 ---p 001be000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb917625000-7fb917629000 r--p 001be000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb917629000-7fb91762b000 rw-p 001c2000 fd:01 1731435                    /lib/x86_64-linux-gnu/libc-2.19.so
7fb91762b000-7fb917630000 rw-p 00000000 00:00 0
7fb917630000-7fb917653000 r-xp 00000000 fd:01 1731443                    /lib/x86_64-linux-gnu/ld-2.19.so
7fb917835000-7fb917838000 rw-p 00000000 00:00 0
7fb917850000-7fb917852000 rw-p 00000000 00:00 0
7fb917852000-7fb917853000 r--p 00022000 fd:01 1731443                    /lib/x86_64-linux-gnu/ld-2.19.so
7fb917853000-7fb917854000 rw-p 00023000 fd:01 1731443                    /lib/x86_64-linux-gnu/ld-2.19.so
7fb917854000-7fb917855000 rw-p 00000000 00:00 0
7ffe8b3e1000-7ffe8b402000 rw-p 00000000 00:00 0                          [stack]
7ffe8b449000-7ffe8b44b000 r--p 00000000 00:00 0                          [vvar]
7ffe8b44b000-7ffe8b44d000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]

上面每一行表示一个段，每个段的有6列，各列含义如下：

1. 此段虚拟地址空间起始地址-结束地址。
2. 此段虚拟地址空间的属性。每种属性用一个字段表示，r表示可读，w表示可写，x表示可执行，p和s共用一个字段，互斥关系，p表示私有段，s表示共享段，如果没有相应权限，则用’-’代替。
3. 对有名映射，表示此段虚拟存储器起始地址在文件中以页为单位的偏移。对匿名映射，它等于0或者vm_start/PAGE_SIZE。
4. 映射文件所属设备号。对匿名映射来说，因为没有文件在磁盘上，所以没有设备号，始终为00:00。对有名映射来说，是映射的文件所在设备的设备号
5. 映射文件所属节点号。对匿名映射来说，因为没有文件在磁盘上，所以没有节点号，始终为00:00。对有名映射来说，是映射的文件的节点号
6. 对有名来说，是映射的文件名。对匿名映射来说，是此段虚拟存储器在进程中的角色。[stack]表示在进程中作为栈使用，[heap]表示堆。其余情况则无显示

5. 缺页异常处理

假如MMU在尝试翻译某个虚拟地址A时，没有对应的物理地址，则会触发了一个缺页异常。这个异常会导致控制转移到内核的缺页异常处理程序，处理程序随后执行如下步骤：

1. 虚拟地址是合法的吗？即虚拟地址是否在已分配的段的地址范围内。如果找不到就会触发段错误。
2. 试图进行的虚拟地址访问是合法的吗？即权限是否符合所在段的权限。如果没有权限就会触发保护异常。
3. 分配物理页，更新页表。缺页处理程序返回时，CPU会重新执行引起缺页的指令。

通过执行以下两种的任意一种命令可查看某个进程的缺页中断信息
ps -o majflt,minflt -C program_name
ps -o majflt,minflt -p pid
majflt和minor这两个数值表示一个进程自启动以来所发生的缺页中断的次数。
其中majflt与minflt的不同是，majflt表示需要读写磁盘，可能是内存对应页面在磁盘中需要load到物理内存中，也可能是此时物理内存不足，需要淘汰部分物理页面至磁盘中。

6. 内存映射

linux通过将虚拟内地段与一个磁盘上的文件关联起来，以初始化这个虚拟存储器段的内容，这个过程称之为内存映射（memory mapping）。内存映射有两种：

1. 有名文件映射：一个段可以映射到一个普通磁盘文件的连续部分，例如一个可执行文件。
2. 匿名文件映射：一个段也可以映射到一个匿名文件，匿名文件由内核创建，包含的是全二进制零。

###6.1 共享对象
内存映射可以让我们简单高效地把程序和数据加载到虚拟存储器空间中。在实际中，许多进程会映射同一个文件到内存中，比如glic动态库，如果物理内存中存在多份，那就是极端的浪费。我们可以通过共享对象技术来消除浪费。

对于私有对象，我们可以用写时拷贝技术来共享物理内存页。

6.2 思考题

1. 能否通过动态库的全局变量在进程间传递信息？
2. 进程A使用动态库S，更新S版本，再启动使用S的进程B后，进程A是否还能正常访问S的函数？

7. 动态内存分配

类unix操作系统下的动态内存分配器有很多，比如ptmalloc（linux默认），tcmalloc（google出品），jemalloc（FreeBSD、NetBSD和firefox默认）。这三种分配器的详细介绍可以参考http://www.360doc.com/content/13/0915/09/8363527_314549128.shtml。
本文以ptmalloc为例介绍动态内存分配。在linux下os提供两种动态内存分配brk和mmap。ptmalloc对于申请内存小于128k的采用brk方式，大于128k的采用mmap方式。

7.1. mmap

对于大内存，malloc会直接调用系统函数mmap分配内存，以物理页为最小单位做对齐。free会直接调用系统函数munmap释放内存。

7.2. brk

进程有一个指针指向堆的顶部的地址，通过系统函数brk可以改变这个指针的位置，从而改变堆的大小（堆可以扩大也可以收缩）。当已有的堆不能分配内存时，brk会扩大堆来分配动态内存。当顶部的内存被释放，切释放内存大于128k，brk就会收缩堆，如下图：

从上面的堆分配释放方式，我们知道实际上很多小内存申请后是不会马上释放给OS，为了将这些内存重复利用，内存分配器需要由一个算法，下面介绍下ptmalloc是如何处理的。

7.3. ptmalloc

ptmalloc通过chunk的数据结构来组织每个内存单元。当我们使用malloc分配得到一块内存的时候，这块内存就会通过chunk的形式被记录到glibc上并且管理起来。你可以把它想象成自己写内存池的时候的一个内存数据结构。chunk的结构可以分为使用中的chunk和空闲的chunk。使用中的chunk和空闲的chunk数据结构基本项同，但是会有一些设计上的小技巧，巧妙的节省了内存。
使用中的chunk：

1. chunk指针指向chunk开始的地址；mem指针指向用户内存块开始的地址。
2. p=0时，表示前一个chunk为空闲，prev_size才有效
3. p=1时，表示前一个chunk正在使用，prev_size无效 p主要用于内存块的合并操作
4. ptmalloc 分配的第一个块总是将p设为1, 以防止程序引用到不存在的区域
5. M=1 为mmap映射区域分配；M=0为heap区域分配
6. A=1 为非主分区分配；A=0 为主分区分配

空闲的chunk结构会复用User data来保存双向链表指针。

ptmalloc一共维护了128bin。每个bins都维护了大小相近的双向链表的chunk。
通过上图这个bins的列表就能看出，当用户调用malloc的时候，能很快找到用户需要分配的内存大小是否在维护的bin上，如果在某一个bin上，就可以通过双向链表去查找合适的chunk内存块给用户使用。

1. fast bins。fast bins是bins的高速缓冲区，大约有10个定长队列。当用户释放一块不大于max_fast（默认值64）的chunk（一般小内存）的时候，会默认会被放到fast bins上。当用户下次需要申请内存的时候首先会到fast bins上寻找是否有合适的chunk，然后才会到bins上空闲的chunk。ptmalloc会遍历fast bin，看是否有合适的chunk需要合并到bins上。
2. unsorted bin。是bins的一个缓冲区。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会进入unsorted bin上。当用户malloc的时候，先会到unsorted bin上查找是否有合适的bin，如果没有合适的bin，ptmalloc会将unsorted bin上的chunk放入bins上，然后到bins上查找合适的空闲chunk。
3. small bins和large bins。small bins和large bins是真正用来放置chunk双向链表的。每个bin之间相差8个字节，并且通过上面的这个列表，可以快速定位到合适大小的空闲chunk。前64个为small bins，定长；后64个为large bins，非定长。
4. Top chunk。并不是所有的chunk都会被放到bins上。top chunk相当于分配区的顶部空闲内存，当bins上都不能满足内存分配要求的时候，就会来top chunk上分配。
5. mmaped chunk。当分配的内存非常大（大于分配阀值，默认128K）的时候，需要被mmap映射，则会放到mmaped chunk上，当释放mmaped chunk上的内存的时候会直接交还给操作系统。

7.3.1. 内存分配malloc流程

1. 获取分配区的锁，防止多线程冲突。
2. 计算出需要分配的内存的chunk实际大小。
3. 判断chunk的大小，如果小于max_fast（64b），则取fast bins上去查询是否有适合的chunk，如果有则分配结束。
4. chunk大小是否小于512B，如果是，则从small bins上去查找chunk，如果有合适的，则分配结束。
5. 继续从 unsorted bins上查找。如果unsorted bins上只有一个chunk并且大于待分配的chunk，则进行切割，并且剩余的chunk继续扔回unsorted bins；如果unsorted bins上有大小和待分配chunk相等的，则返回，并从unsorted bins删除；如果unsorted bins中的某一chunk大小 属于small bins的范围，则放入small bins的头部；如果unsorted bins中的某一chunk大小 属于large bins的范围，则找到合适的位置放入。
6. 从large bins中查找，找到链表头后，反向遍历此链表，直到找到第一个大小 大于待分配的chunk，然后进行切割，如果有余下的，则放入unsorted bin中去，分配则结束。
7. 如果搜索fast bins和bins都没有找到合适的chunk，那么就需要操作top chunk来进行分配了（top chunk相当于分配区的剩余内存空间）。判断top chunk大小是否满足所需chunk的大小，如果是，则从top chunk中分出一块来。
8. 如果top chunk也不能满足需求，则需要扩大top chunk。主分区上，如果分配的内存小于分配阀值（默认128k），则直接使用brk()分配一块内存；如果分配的内存大于分配阀值，则需要mmap来分配；非主分区上，则直接使用mmap来分配一块内存。通过mmap分配的内存，就会放入mmap chunk上，mmap chunk上的内存会直接回收给操作系统。

7.3.2. 内存释放free流程

1. 获取分配区的锁，保证线程安全。
2. 如果free的是空指针，则返回，什么都不做。
3. 判断当前chunk是否是mmap映射区域映射的内存，如果是，则直接munmap()释放这块内存。前面的已使用chunk的数据结构中，我们可以看到有M来标识是否是mmap映射的内存。
4. 判断chunk是否与top chunk相邻，如果相邻，则直接和top chunk合并（和top chunk相邻相当于和分配区中的空闲内存块相邻）。转到步骤8
5. 如果chunk的大小大于max_fast（64b），则放入unsorted bin，并且检查是否有合并，有合并情况并且和top chunk相邻，则转到步骤8；没有合并情况则free。
6. 如果chunk的大小小于 max_fast（64b），则直接放入fast bin，fast bin并没有改变chunk的状态。没有合并情况，则free；有合并情况，转到步骤7
7. 在fast bin，如果当前chunk的下一个chunk也是空闲的，则将这两个chunk合并，放入unsorted bin上面。合并后的大小如果大于64KB，会触发进行fast bins的合并操作，fast bins中的chunk将被遍历，并与相邻的空闲chunk进行合并，合并后的chunk会被放到unsorted bin中，fast bin会变为空。合并后的chunk和topchunk相邻，则会合并到topchunk中。转到步骤8
8. 判断top chunk的大小是否大于mmap收缩阈值（默认为128KB），如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统。free结束。

7.4. 内存碎片

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

1. 内部碎片：已分配块比有效载荷大。往往在实现内存池或者自己管理内存时会存在内部碎片。
2. 外部碎片：空闲内存合起来可以满足分配要求，但是没有一个单独的空闲块足够大可以满足分配请求。目前一些好的第三方分配器，如tcmalloc、jemalloc可以很好地解决外部碎片问题。

7.5. 思考题

####提问1：请问下面代码运行后，OS会立即分配1G物理内存吗？

#include <cstdlib>

int main()
{
    char *p = (char*)malloc(1024*1024*1024);
    while(1);
    return 0;
}

###提问2：请问下面代码运行后，OS会分配多少物理内存？

#include <cstdlib>
#include <cstring>

int main()
{
    const size_t MAX_LEN = 1024*1024*1024;
    char *p = (char*)malloc(MAX_LEN);
    memset(p, 0, MAX_LEN/2);
    while(1);
    return 0;
}