【CS】（奇妙的）虚拟存储器

虚拟存储器，Virtual Machine，简称VM，是对主存（DRAM）的一种抽象，是计算机系统中最重要的概念之一。计算机中有各种存储器，而VM的存在，就是为了帮助我们有效地管理这些存储器，减少错误，提供一种简单的数据交互方法。VM，将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存中来回传送数据，而且为每个进程提供了一致的地址空间，并保护这个地址空间不被其它的进程破坏。下面逐渐介绍VM的奇妙之处。

1、寻址和地址空间

早期的PC使用物理寻址，而且诸如数字信号处理器、嵌入式微控制器以及Cray超级计算机这样的系统仍然继续使用这种寻址方式。主存，在计算机系统中被认为是一个由M个连续字节构成的大数组，每个字节都有一个唯一的物理地址，从0开始，到M-1结束。CPU访问存储器时，直接使用物理地址进行寻址称为物理寻址。物理寻址如下图所示，CPU执行一条加载指令，从物理地址4开始的地方读取4个字节，这个物理地址由CPU生成，然后通过存储器总线把物理地址传递给主存，主存取出从物理地址4开始的4个字节的数据，然后把数据返回给CPU，最后，CPU将数据存放在寄存器。

然而，现代的处理器多使用虚拟寻址，如下图所示，CPU首先生成一个虚拟地址，然后通过MMU转换成合适的物理地址，后面的步骤同物理寻址。

地址空间是一个非负整数地址的有序结合，地址连续时称为线性地址空间。地址空间包括物理地址空间和虚拟地址空间。物理地址空间见前面的图例，它与系统中物理存储器的M个字节相对应，从0开始，到M-1结束。虚拟地址空间在有虚拟存储器的系统中，CPU从这个地址空间中生成虚拟地址，地址空间的大小由表示最大地址所需的位数来描述，如32位地址空间，虚拟地址从0开始，到2的32次方-1结束。

2、缓存

VM作为一个大的数组，数组索引为对应的虚拟地址，数组内容缓存在主存。主存与磁盘的数据传输单元是块，同样，物理存储器、虚拟存储器被分割成了物理页、虚拟页，以页为单位，物理页又称为页帧。在任意时刻，虚拟页或者未分配，或者已分配但未缓存在物理存储器，或者已分配并缓存在物理存储器。下图是存储器的层次结构，我们用SRAM缓存表示位于CPU和主存之间的L1、L2和L3高速缓存，用DRAM缓存表示虚拟存储器系统的缓存，它在主存中缓存虚拟页，由于DRAM相对于磁盘的速度远大于SRAM相对于DRAM的速度，所以DRAM缓存的不命中比SRAM缓存的不命中的代价要昂贵得多。

3、页表

同任何缓存一样，虚拟存储器系统必须有某种方法来判定一个虚拟页是否存放在DRAM中的某个地方，如果是，系统还必须确定这个虚拟页存放在哪个物理页中，如果不是，系统必须判定这个虚拟页存放在磁盘的哪个位置，在物理存储器中选择一个牺牲页，并将虚拟页从磁盘拷贝到DRAM中，替换这个牺牲页。这些功能是由许多软硬件联合提供的，包括操作系统软件、MMU中的地址翻译硬件和一个存放在物理存储器中叫做页表的数据结构，页表将虚拟页映射到物理页，每次地址翻译硬件将一个虚拟地址转换为物理地址时都会读取页表，操作系统负责维护页表的内容，以及在磁盘与DRAM之间来回传送页。

下图展示了一个页表的基本组织结构，有8个虚拟页和4个物理页，4个虚拟页VP1、VP2、VP4和VP7当前被缓存在DRAM中，2个虚拟页VP0和VP5还未被分配，剩下的2个虚拟页VP3和VP6已经被分配但当前还未被缓存。页表就是一个页表条目的数组，页表条目Page Table Entry即PTE，虚拟地址空间中的每个页在页表中的一个固定偏移处都有一个PTE。我们假设每个PTE是由一个有效位和一个地址字段组成的，有效位表示该虚拟页当前是否被缓存在DRAM中，1表示缓存，0表示没缓存；有效位为1时，地址字段表示DRAM中相应的物理页的起始地址，这个物理页中缓存了该虚拟页，任意物理页都可以包含任意虚拟页，有效位为0时，地址字段为空地址，表示这个虚拟页还未被分配，地址字段不为空地址，这个地址就指向该虚拟页在磁盘上的起始位置。

操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间，多个虚拟页面可以映射到同一个共享的物理页面上。任何现代计算机系统必须为操作系统提供手段来控制对存储器系统的访问，典型的做法是在页表条目中添加标志位，表示为普通用户还是超级用户、可读、可写权限等。页表需要驻留在存储器中，可能很大，压缩页表的常用方法是使用多级页表。

4、命中和缺页

根据上面的页表，当CPU读虚拟存储器的虚拟页VP2的内容时，地址翻译硬件将这个虚拟地址作为索引来定位页表中的页表条目PTE2，得知其有效位为1，所以根据其地址字段定位到了物理存储器的物理页PP1，从而获得相应的物理地址，这个过程称为页命中。相反，当CPU读虚拟存储器的虚拟页VP3的内容时，地址翻译硬件将这个虚拟地址作为索引来定位页表中的页表条目PTE3，得知其有效位为0，虚拟页VP3未被缓存，所以触发一个缺页异常，这个过程称为不命中或缺页。缺页异常之后，内核中的缺页异常处理程序会选择一个牺牲页，比如说物理存储器的物理页PP3中的虚拟页VP4，如果VP4已经被修改了，那么内核就会将它拷贝回磁盘，这称为页面调出，然后内核修改VP4的页表条目PTE4，表示出VP4不再缓存在主存中，接着内核从磁盘拷贝虚拟页VP3到主存的物理页PP3，这称为页面调入，并更新VP3的页表条目PTE3，表示出VP3已经缓存在主存中，最后返回。缺页异常处理程序返回之后，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重新发到地址翻译硬件，而这时，地址已经缓存在主存中了，可以命中。

上面提到的页面调出和页面调入即页面调度，当有不命中发生时，一直等待，直到最后时刻才换入页面的策略称为按需页面调度。如果尝试着预测不命中，在页面实际被引用之前就换入页面，这种策略称为超前页面调度，不过，所有现代系统使用的都是按需页面调度的方式。

缺页是需要代价的，页面调度会破坏程序性能，然而，VM实际上工作得很好，这得益于程序有良好的局部性，在任意时刻，程序将在一个较小的活动页面集合上工作，只是在初始时将活动页面集合调度到DRAM中有一定的开销，之后对这些页面的引用将是命中，不会有额外的磁盘流量。但是如果活动页面集合的大小超出了物理存储器的大小，页面将不断地换进换出，发生悲剧的颠簸thrash现象，严重影响程序性能，Linux中的getrusuage函数可以检查缺页的数量。

地址翻译基于CPU中一个的控制寄存器，页表基址寄存器Page Table Base Register，即PTBR，指向当前页表，MMU负责虚拟地址翻译为物理地址。在地址翻译过程中，CPU每次都要生成一个虚拟地址，然后在页表中查找PTE，所以MMU包括了一个关于PTE的小缓存TLB，翻译后备缓冲器Translation Lookaside Buffer，用于加速地址翻译。

在任何既使用虚拟存储器又使用SRAM高速缓存的系统中，大多数系统选择物理寻址，地址翻译发生在高速缓存查找之前。

5、Linux虚拟存储器

Linux虚拟存储器如下图所示。MMU翻译虚拟地址时，如果触发了缺页异常，内核首先判断这个虚拟地址是否合法，然后判断存储器访问是否有合适的权限，最后选择一个牺牲页面进行后续操作。

6、存储器映射mmap

Linux通过将一个虚拟存储器的区域与一个磁盘上的对象关联起来，以初始化这个虚拟存储器区域的内容，这个过程称为虚拟存储器映射memory mapping，简称mmap。mmap可以映射到Linux文件系统中个普通文件，或者映射到匿名文件，匿名文件由内核创建，包含的全是二进制零，因此又称做二进制零的页。mmap映射的对象要么是共享对象，要么是私有对象，共享对象对其它进程可见，会修改磁盘上的原始对象；私有对象对其它进程不可见，不会修改磁盘上的原始对象，使用了一种写时拷贝copy-on-write的技术。Linux上使用mmap和munmap完成虚拟存储器映射。

#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

7、动态存储器分配

动态存储器分配，如C中的malloc/free，C++中的new/delete，在堆heap上进行，内核维护着一个指向堆顶的指针brk，地址向上增长，如下图所示。

动态内存分配，需要处理任意请求序列，立即响应请求，只使用堆，对齐块，不修改已分配的块。一个常见问题是内存碎片，存储器虽然有多个小的空闲块，加起来可以满足请求，但是没有一个大的连续的空闲块，所以分配器常采用启发式策略来试图维持少量的大空闲块，而不是维持大量的小空闲块，这需要考虑几个地方，如何纪录空闲块，如何选择一个合适的空闲块来放置新分配的块，如何处理空闲块中的剩余部分，如何处理一个刚刚被释放的块。

8、常见错误

下面列举几个C程序中常见的与存储器有关的错误。

间接引用坏指针——
见下面的例子，scanf函数从标准输入stdin读入一个整数到变量value，错误的做法是直接使用value而不是其地址，这样程序将覆盖value的内容可以表示的地址上的数据，最好的情况是程序立即异常终止，不幸的是，有时候这个地址对应的恰巧是存储器上合法的读写区域，程序将运行很长一段时间后才出现错误，这种错误往往很难发现。

scanf("%d", &value); // ok
scanf("%d", value); // wrong

读未初始化的存储器——
见下面的例子，malloc函数并不会初始化变量，正确的做法是使用之前进行初始化，或者使用calloc函数。

int *pi = malloc(sizeof(int));
*pi += 100;

栈缓冲区溢出——
见下面的例子，数组buf的大小为64，而gets函数没有限制输入字符串的长度，很可能导致缓冲区溢出，正确的做法是使用fgets函数限制输入字符串的长度。

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

错误使用指针——
指针和指针指向的对象是两个不同的东西，它们的大小有时候可能相等，但必须正确使用，区别对待。使用指针时，注意操作的对象是指针本身还是指针指向的对象。对指针使用加减运算时，步长是指针指向的对象的大小，例如char*步长为1，int*步长为4。不能引用空闲堆块中的数据，指针free后，不能再引用它指向的对象。同理，malloc之后如果忘记free，将造成内存泄漏。

越界——
数组或指针越界，注意它们的上下边界，见下面的例子，是个越界操作。

int* p = new int(10);
p[10] = 100;

结束