第三章 虚拟内存
译者：飞龙
3.1 简明信息理论
比特是二进制的数字，也是信息的单位。一个比特有两种可能的情况，写为0或者1。如果是两个比特，那就有四种可能的组合，00、01、10和11。通常，如果你有b个比特，你就可以表示2 ** b个值之一。一个字节是8个比特，所以它可以储存256个值之一。
从其它方面来讲，假设你想要储存字母表中的字母。字母共有26个，所以你需要多少个比特呢？使用4个比特你可以表示16个值之一，这是不够的。使用5个比特你可以表示32个值，这对于所有字母是够用的，同时还有一点点浪费。
通常，如果你想要表示N个值之一，你就需要求出最小的b使2 ** b >= N。在两边计算以2为底的对数，就会得到b >= log(2, N)。
假设我投掷一枚硬币并且告诉你结果，我就向你提供了1比特的信息。如果我投掷六个面的筛子并告诉你结果，我就向你提供了log(2, 6)比特的信息。并且通常，如果结果的概率是1/n，结果应该包含log(2, N)比特的信息。
同样，如果结果的概率为p，那么信息的内容为-log(2, p)。这个数量叫做“自信息”（self-information）。它度量了结果有多么令人意外，所以也叫作“惊异度”。如果你的赛马只有十六分之一的几率获胜，并且它获胜了，那么你就得到了4比特的信息（以及奖金）。但是如果它的获胜几率为75%，这条新闻只含有0.42个比特。
可以由直觉得出，非预期的新闻会带有大量信息；与之相反，如果你对一件事情很有自信，对它的验证只会得到少量的信息。
对于书中的一些话题，我们只需要熟练于在比特数量b和它们所编码的值的数量N = 2 ** b之间进行转换。
3.2 内存（Memory）和储存器（Storage）
当进程处于运行期间，它的多数数据都放在“主存”（内存）之中，它通常是一些随机储存器（RAM）。在当前的大多数电脑上，主存非常易失，也就是说，当电脑关闭时，主存的内容就没了。一个典型的台式电脑拥有2~8GiB的内存。GiB代表“gibibyte”，相当于2 ** 30个字节。
如果进程会读写文件，这些文件通常放在机械硬盘（HDD）或固态硬盘（SSD）里面。这些储存器都是非易失的，所以他们可用于长时间储存。当前，一个典型的台式电脑拥有500GB到2TB的HDD。GB代表“gigabyte”，相当于10 ** 9个字节。TB代表“terabyte”，相当于10 ** 12个字节。
你可能会注意到我使用二进制单位GiB来描述主存大小，并使用十进制单位GB和TB来描述HDD的大小。由于历史和技术因素，内存以二进制单位度量，并且硬盘以十进制单位度量。本书中我会小心区分二进制和十进制单位，但是你应该注意到“gigabyte”以及GB缩写通常在使用上非常模糊。
非正式的用法中，“内存”有时会用于HDD和SSD（特别是移动设备），以及RAM。然而，这些设备的属性大相径庭，所以我们需要区分它们。我会使用“储存器”来指代HDD和SSD。
3.3 地址空间
主存中的每个字节都由一个“物理地址”整数所指定，物理地址的集合叫做物理“地址空间”。它的范围通常为0到N-1，其中N是主存的大小。在带有1GiB主存的的系统上，最高的有效地址是2 ** 30 - 1，十进制表示为1,073,741,823，16进制表示为0x03ff ffff（前缀0x表示十六进制）。
然而，许多操作系统提供“虚拟内存”，也就是说程序永远不需要处理物理地址，也不需要知道有多少物理内存是有效的。
作为代替，程序处理虚拟地址，它被编码为从0到M-1，其中M是有效虚拟地址的大小。虚拟地址空间的大小取决于所处的操作系统和硬件。
你一定听过人们谈论32位和64位系统。这些术语表明了寄存器的尺寸，也通常是虚拟地址的大小。在32位系统上，虚拟地址是32位的，也就是说虚拟地址空间为从0到0xffff ffff。这一地址空间的大小是2 ** 32个字节，或者4GiB。
在64位系统上，虚拟地址空间大小为2 ** 64个字节，或者4 * 1024 ** 6个字节。这是16个EiB，大约比当前的物理内存大十亿倍。虚拟内存比物理内存大很多，这看上去有些奇怪，但是我们很快就就会看到它如何工作。
当一个程序读写内存中的值时，它使用虚拟地址。硬件在操作系统的帮助下，在访问主存之前将物理地址翻译成虚拟地址。翻译过程在进程层级上完成，所以即使两个进程访问相同的虚拟地址，它们所映射的物理地址可能不同。
因此，虚拟内存是操作系统隔离进程的一种重要途径。通常，一个进程不能访问其他进程的数据，因为没有任何虚拟地址能映射到其他进程分配的物理内存。
3.4 内存段
一个运行中进程的数据组织为4个段：
text段包含程序文本，即程序所组成的机器语言指令、static段包含由编译器所分配的变量，包括全局变量，和使用static声明的局部变量。stack段包含运行时栈，它由栈帧组成。每个栈帧包含函数参数、本地变量以及其它。heap段包含运行时分配的内存块，通常通过调用C标准库函数malloc来分配。
这些段的组织方式部分取决于编译器，部分取决于操作系统。不同的操作系统中细节可能不同，但是下面这些是共同的：
text段靠近内存“底部”，即接近0的地址。static段通常刚好在text段上面。stack段靠近内存顶部，即接近虚拟地址空间的最大地址。在扩张过程中，它向低地址的方向增长。heap通常在static段的上面。在扩张过程中，它向高地址的方向增长。
为了搞清楚这些段在你操作系统上的布局，可以尝试运行这个程序，它就是这本书的仓库中的aspace.c：
#include <stdio.h>
#include <stdlib.h>
int global;
int main ()
{
int local = 5;
void *p = malloc(128);
printf ("Address of main is %p\n", main);
printf ("Address of global is %p\n", &global);
printf ("Address of local is %p\n", &local);
printf ("Address of p is %p\n", p);
}
main是函数的名称，当它用作变量时，它指向main中第一条机器语言指令的地址，我们认为它在text段内。
global是一个全局变量，所以我们认为它在static段内。local是一个局部变量，所以我们认为它在栈上。
p持有malloc所返回的地址，它指向堆区所分配的空间。malloc代表“内存分配”（memory allocate）。
格式化占位符%p告诉printf把每个地址格式化为“指针”，它是地址的另一个名字。
当我运行这个程序时，输出就像下面这样（我添加了空格使它更加易读）：
Address of main is 0x 40057c
Address of global is 0x 60104c
Address of local is 0x7fffd26139c4
Address of p is 0x 1c3b010
正如预期的那样，main的地址最低，随后是global和p。local的地址会更大，它是12个十六进制数字，每个十六进制数字对应4比特，所以它是48位的地址。这表明虚拟内存的可用部分为2 ** 48个字节。
作为一个练习，你需要在你的电脑上运行这个程序，并将你的结果与我的结果比较。添加对malloc的第二个调用来检查你系统上的堆区是否向上增长（地址更高）。添加一个函数来打印出局部变量的地址，检查栈是否向下增长。
3.5 静态局部变量
栈上的局部变量有时称为“自动变量”，因为它们当函数创建时自动被分配，并且当函数返回时自动被释放。
C语言中又另一种局部变量，叫做“静态变量”，它分配在在static段上。它在程序启动时初始化，并且在函数调用之间保存它的值。
例如，下面的函数跟踪了它所调用的次数：
int times_called()
{
static int counter = 0;
counter++;
return counter;
}
static关键字表示counter是静态局部变量。它的初始化只发生一次，就是程序启动的时候。
如果你将这个函数添加到aspace.c，你可以确定counter和全局变量一起分配在static段上，而不是在栈上。
3.6 地址翻译
虚拟地址（VA）如何翻译成物理地址（PA）？基本的机制十分简单，但是简单的实现方式十分耗时，并且占据大量空间。所以实际的实现会复杂一点。
大多数处理器提供了内存管理单元（MMU），位于CPU和主存之间。MMU在VA和PA之间执行快速的翻译。
- 当程序读写变量时，CPU会得到VA。
- MMU将VA分成两部分，称为页码和偏移。“页”是一个内存块，页的大小取决于操作系统和硬件，通常为1~4KiB。
- MMU在“页表”里查找页码，然后获取相应的物理页码。之后它将物理页码和偏移组合得到PA。
- PA传递给主存，用于读写指定地址。
作为一个例子，假设VA为32位，物理内存为1GiB，划分为1KiB的页面。
- 由于1GiB为
2 ** 30个字节，物理页的数量为2 ** 20个，它们也称为“帧”。 - 虚拟地址空间的大小为
2 ** 32字节，这个例子中，页的大小为2 ** 10字节，所以共有2 ** 22个虚拟页。 - 偏移的大小取决于页的大小。这个例子中页的大小为
2 ** 10字节，所以需要10位来指定页中的一个字节。 - 如果VA是32位，而偏移是10位，剩余的22位构成了虚拟页码。
- 由于共有
2 ** 20个物理页，每个物理页码是20位。加上10位的偏移，PA的结果为30位。
到目前为止，看上去是是可行的。但是让我们考虑一下页表应该占多大。页表最简单的实现是一个数组，每个虚拟页面是一个条目。每个条目都包含一个物理页码，在例子中它是20位，加上每帧的一些额外的数据，所以我们认为每个条目占用3~4个字节。由于共有2 ** 22个虚拟页，页面共需要2 ** 24个字节，或16MiB。
由于我们需要为每个进程创建一个页表，一个运行256个进程的系统就需要2 ** 32个字节，或者4GiB，这还只是页表的空间！这些就占用了全部32位虚拟地址。而在48或64位的虚拟地址上，这个数量更加荒谬。
幸运的是，并不需要这么大的空间，因为大多数进程不使用虚拟地址空间的每个小片段。而且，如果一个进程不使用某个虚拟页面，我们也不需要在页表中为其分配条目。
也就是说，页表是“稀疏”的，这暗示了最简单的实现，即页表条目的数组是个糟糕的想法。幸运的是，稀疏数组有一些不错的实现方式。
一种选择是多级页表，它被多数操作系统例如Linux所采用。另一种选择是关联表，其中每个条目包含虚拟页码和物理页码。在软件上搜索关联表会非常慢，但是硬件上我们可以并行搜索整个表，所以关联数组经常用于在MMU中表示页表。
你可以在页表的维基百科页面阅读更多关于这些实现的信息。你也可能会找到有趣的细节。但是基本的想法就是页表应做成稀疏的，所以我们需要为稀疏数组选择一个好的实现方式。
我之前提到了操作系统可以中断一个运行中的进程，保存它的状态，之后运行其它进程。这个机制叫做“上下文切换”。由于每个进程都有自己的页表，操作系统需要和MMU配合来保证每个进程拿到了正确的页表。在旧机器上，MMU中的页表信息在每次上下文切换时会被替换掉，开销非常大。在新的系统中，MMU的每个页表条目包含进程ID，所以多个进程的页表可以同时储存在MMU中。