第三章 虚拟内存

    比特是二进制的数字，也是信息的单位。一个比特有两种可能的情况，写为0或者1。如果是两个比特，那就有四种可能的组合，00、01、10和11。通常，如果你有个比特，你就可以表示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。

    然而，许多操作系统提供“虚拟内存”，也就是说程序永远不需要处理物理地址，也不需要知道有多少物理内存是有效的。

    作为代替，程序处理虚拟地址，它被编码为从0到M-1，其中M是有效虚拟地址的大小。虚拟地址空间的大小取决于所处的操作系统和硬件。

    你一定听过人们谈论32位和64位系统。这些术语表明了寄存器的尺寸，也通常是虚拟地址的大小。在32位系统上，虚拟地址是32位的，也就是说虚拟地址空间为从0到0xffff ffff。这一地址空间的大小是2 ** 32个字节，或者4GiB。

    在64位系统上，虚拟地址空间大小为个字节，或者4 * 1024 ** 6个字节。这是16个EiB，大约比当前的物理内存大十亿倍。虚拟内存比物理内存大很多，这看上去有些奇怪，但是我们很快就就会看到它如何工作。

    当一个程序读写内存中的值时，它使用虚拟地址。硬件在操作系统的帮助下，在访问主存之前将物理地址翻译成虚拟地址。翻译过程在进程层级上完成，所以即使两个进程访问相同的虚拟地址，它们所映射的物理地址可能不同。

    因此，虚拟内存是操作系统隔离进程的一种重要途径。通常，一个进程不能访问其他进程的数据，因为没有任何虚拟地址能映射到其他进程分配的物理内存。

    3.4 内存段

    一个运行中进程的数据组织为4个段：

    • text段包含程序文本，即程序所组成的机器语言指令、
    • stack段包含运行时栈，它由栈帧组成。每个栈帧包含函数参数、本地变量以及其它。
    • heap段包含运行时分配的内存块，通常通过调用C标准库函数malloc来分配。

    这些段的组织方式部分取决于编译器，部分取决于操作系统。不同的操作系统中细节可能不同，但是下面这些是共同的：

    • text段靠近内存“底部”，即接近0的地址。
    • static段通常刚好在text段上面。
    • stack段靠近内存顶部，即接近虚拟地址空间的最大地址。在扩张过程中，它向低地址的方向增长。
    • heap通常在static段的上面。在扩张过程中，它向高地址的方向增长。

    为了搞清楚这些段在你操作系统上的布局，可以尝试运行这个程序，它就是这本书的仓库中的aspace.c：

    main是函数的名称，当它用作变量时，它指向main中第一条机器语言指令的地址，我们认为它在text段内。

    global是一个全局变量，所以我们认为它在static段内。local是一个局部变量，所以我们认为它在栈上。

    p持有malloc所返回的地址，它指向堆区所分配的空间。代表“内存分配”（memory allocate）。

    格式化占位符%p告诉printf把每个地址格式化为“指针”，它是地址的另一个名字。

    当我运行这个程序时，输出就像下面这样（我添加了空格使它更加易读）：

    作为一个练习，你需要在你的电脑上运行这个程序，并将你的结果与我的结果比较。添加对malloc的第二个调用来检查你系统上的堆区是否向上增长（地址更高）。添加一个函数来打印出局部变量的地址，检查栈是否向下增长。

    栈上的局部变量有时称为“自动变量”，因为它们当函数创建时自动被分配，并且当函数返回时自动被释放。

    C语言中又另一种局部变量，叫做“静态变量”，它分配在在static段上。它在程序启动时初始化，并且在函数调用之间保存它的值。

    例如，下面的函数跟踪了它所调用的次数：

    static关键字表示counter是静态局部变量。它的初始化只发生一次，就是程序启动的时候。

    如果你将这个函数添加到aspace.c，你可以确定counter和全局变量一起分配在static段上，而不是在栈上。

    3.6 地址翻译

    虚拟地址（VA）如何翻译成物理地址（PA）？基本的机制十分简单，但是简单的实现方式十分耗时，并且占据大量空间。所以实际的实现会复杂一点。

    大多数处理器提供了内存管理单元（MMU），位于CPU和主存之间。MMU在VA和PA之间执行快速的翻译。

    1. 当程序读写变量时，CPU会得到VA。
    2. MMU在“页表”里查找页码，然后获取相应的物理页码。之后它将物理页码和偏移组合得到PA。
    3. 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个虚拟页，页面共需要个字节，或16MiB。

    由于我们需要为每个进程创建一个页表，一个运行256个进程的系统就需要2 ** 32个字节，或者4GiB，这还只是页表的空间！这些就占用了全部32位虚拟地址。而在48或64位的虚拟地址上，这个数量更加荒谬。

    幸运的是，并不需要这么大的空间，因为大多数进程不使用虚拟地址空间的每个小片段。而且，如果一个进程不使用某个虚拟页面，我们也不需要在页表中为其分配条目。

    也就是说，页表是“稀疏”的，这暗示了最简单的实现，即页表条目的数组是个糟糕的想法。幸运的是，稀疏数组有一些不错的实现方式。

    一种选择是多级页表，它被多数操作系统例如Linux所采用。另一种选择是关联表，其中每个条目包含虚拟页码和物理页码。在软件上搜索关联表会非常慢，但是硬件上我们可以并行搜索整个表，所以关联数组经常用于在MMU中表示页表。

    我之前提到了操作系统可以中断一个运行中的进程，保存它的状态，之后运行其它进程。这个机制叫做“上下文切换”。由于每个进程都有自己的页表，操作系统需要和MMU配合来保证每个进程拿到了正确的页表。在旧机器上，MMU中的页表信息在每次上下文切换时会被替换掉，开销非常大。在新的系统中，MMU的每个页表条目包含进程ID，所以多个进程的页表可以同时储存在MMU中。