本文最后修改时间:2019-01-14 20:53

第三章 虚拟内存

作者:Allen B. Downey

原文:Chapter 3 Virtual memory

译者:飞龙

协议:CC BY-NC-SA 4.0

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的地址最低,随后是globalplocal的地址会更大,它是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之间执行快速的翻译。

  1. 当程序读写变量时,CPU会得到VA。
  2. MMU将VA分成两部分,称为页码和偏移。“页”是一个内存块,页的大小取决于操作系统和硬件,通常为1~4KiB。
  3. MMU在“页表”里查找页码,然后获取相应的物理页码。之后它将物理页码和偏移组合得到PA。
  4. 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中。