来Offer习题讲解专题 | Virtual Memory究竟是什么？
作者介绍：汤老师
来Offer(www.laioffer.com)金牌算法讲师。清华大学计算机系信息学竞赛保送生，美国哥伦比亚大学计算机系软件系统实验室博士生，曾在 OSDI、CACM 等操作系统领域最顶级学术会议和期刊上发表多篇论文。曾参与 Chrome 和 Google Cloud Platform 的研发工作。
最近有不少转专业的同学问我们说尽管大家已经学会了很多数据结构和算法的知识，可是每当见到一些计算机系统方面的名词术语还是一头雾水。
于是我们打算写一些专题文章，帮助本科不是计算机专业的同学快速了解一些计算机系统的基本概念。今天先来讲讲Virtual Memory。
Virtual Memory（虚拟内存），顾名思义，是针对 physical memory（物理内存）来的。
远古时期的计算机（五十年前的大型机或者三十年前的个人电脑）是不用虚拟内存的，那时候要想跑一个程序，必须先把整个程序加载到物理内存里才能执行。
可是内存又小又贵，而人们不仅想跑大程序，还想同时跑好几个，有限的物理内存吃不消了可怎么办呢？
于是人们想到了虚拟化。
（注：其实不仅是虚拟内存，广义的虚拟化概念可以解决许许多多的计算机问题，比如大家常用的 virtual machine, virtual file system, VPN 等等都是虚拟化在各个领域的应用。）
简单来讲，虚拟内存就是让每个进程看起来都好像拥有一个大而独立的地址空间。
什么意思呢？我们一个词一个词来讲。
首先说什么是地址空间（address space）。计算机的内存说白了可以想象成一块连续的数组，数组里面的每个字节都有一个唯一的地址。
比方说我新买的（键盘手感巨烂的）电脑有 16GB（即 2³⁴ bytes）的物理内存，那它的物理地址空间就是 {0, 1, 2, …, 2³⁴ — 1}。
接下来再说大。
就是说不管我实际的物理内存有多大，虚拟内存都可以假装有很大。比如我的电脑号称是 64-bit 的，也就是说我电脑上跑的每一个进程都以为它拥有一块 {0, 1, 2, …, 2⁶⁴ — 1} 的虚拟地址空间。那要是物理内存不够了怎么办？
我们可以把虚拟内存看作一个缓存的工具，正在使用的部分放在物理内存里，暂时不用的部分就扔在磁盘上好了。
独立的意思是说尽管每个进程的虚拟地址空间长得都一样，但它们都是私有的。不同进程的同一个虚拟地址可以映射到不同的物理地址。
例如，所有 64-bit 程序的代码都是从内存地址 0x400000 开始的，然而不同程序其中的内容是不一样的。
这就好比说A住了个Town House，隔壁是B的Town House，尽管这两栋房子的外观设计一模一样，但A老师家门口挂了幅盗梦空间的海报，而B老师家同样的位置是这样一张风景画：
这是怎么实现的呢？简单来讲，系统把虚拟内存和物理内存都划分为等长的 page（页），并为每个进程维护一个 page table（页表）用来将虚拟页映射到物理页。
这样当我们访问一个虚拟地址时，系统就可以通过查表将其翻译为物理地址。如果这个地址所在的页当前不在物理内存中，则系统会先将它从磁盘取出来替换掉内存里另一个暂时不用的页。整个过程是由操作系统和硬件协同完成的，这里不再赘述，感兴趣的同学可以参考任何一本操作系统教材。
虚拟内存让进程的链接和加载、共享和分配内存、访问权限控制等都变得很容易。连续的虚拟页不必要在物理上连续，而不同的虚拟页也可以映射到同一个物理页。
举个简单的例子，几乎所有的C语言程序都会用到printf函数，于是我们在物理内存中可以只有一份printf的实现，而让各个进程对应的虚拟页全都映射到同一个物理页即可。
最后我们来简要讨论一些同学们在写程序时常犯的和虚拟内存有关的错误（以下以 C 语言为例；Java 也会相应地报错或抛出异常）：
1. 访问空指针或坏指针。比如指针指向的虚拟地址并没有映射到实际有意义的数据，或者我们试图去写一块只读的虚拟内存区域，都会导致 segmentation fault。
2. 访问未初始化的内存。如果一个局部变量没有初始化而我们误以为它是零，程序的结果就会不对。
3. 缓冲区溢出（buffer overflow）。例如一个函数的输入参数是一个字符串，函数里有一个固定大小的 buffer。如果我们没有检查该字符串的长度就将它拷贝到 buffer 中，一旦输入字符串超出了 buffer 的长度就会造成 buffer overflow，从而覆盖掉其它有意义的数据。
4. 缓冲区溢出有一个特例是所谓的 off-by-one error，也是同学们常犯的错误。一个长度为 n 的数组 index 是 0 到 n-1，此时如果访问 index 为 n 的元素就越界了，会读到甚至覆盖掉别的数据。
（本文在写作过程中参考了 Randal E. Bryant 和 David R. O’Hallaron 所著的 Computer Systems: A Programmer’s Perspective 第三版。）
更多科技求职资讯，请关注来Offer(www.laioffer.com)
来Offer软件工程师旗舰核心课程：https://www.laioffer.com/zh/course/software-development/
来Offer全栈开发项目实践课程：
https://www.laioffer.com/zh/course/full-stack-development/
人工智能与数据科学强化课程：
