CSAPP

CSAPP-09虚拟内存

Posted by SH on May 23, 2020

CSAPP-09虚拟内存

虚拟内存（VM）：现代系统提供的一种对主存的抽象概念。

虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的和私有的地址空间。

通过一个很清晰的机制，虚拟内存提供了三个重要的能力：

  • 1）它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据，通过这种方式高效地使用了主存；
  • 2）它为每个进程提供了一致的地址空间，从而简化了内存管理；
  • 3）它保护了每个进程的地址空间不被其他进程破坏。

虚拟内存是计算机系统最重要的概念之一。

  • 虚拟内存是核心的。虚拟内存遍及计算机系统的所有层面，在硬件异常、汇编器、链接器、加载器、共享对象、文件和进程的设计中扮演着重要角色。
  • 虚拟内存是强大的。虚拟内存给予应用程序强大的能力，可以创建和销毁内存片（chunk）、将内存片映射到磁盘文件的某个部分，以及与其他进程共享内存。比如：
    • 可以通过读写内存位置读或者修改一个磁盘文件的内容；
    • 可以加载一个文件的内容到内存中，而不需要进行任何显式地复制；
  • 虚拟内存是危险的。每次应用程序引用一个变量、间接引用一个指针，或者调用一个诸如malloc这样的动态分配程序时，它就会和虚拟内存发生交互。
    • 一个带有错误指针的程序可以立即崩溃于“段错误”或“保护错误”，它可能在崩溃之前还默默地运行了几个小时，或者最令人惊慌地，运行完成却产生不正确的结果。

重点：

  • 虚拟内存如何工作；
  • 应用程序如何使用和管理虚拟内存。

物理和虚拟地址

image-20210119152810425

image-20210119152842113

将一个虚拟地址（Virtual Address，VA）转换为物理地址的任务叫做地址翻译（address translation）。就像异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。

CPU芯片上叫做内存管理单元（Memory Management Unit，MMU）的专用硬件，利用存放在主存中的查询表来动态翻译虚拟地址，该表的内容由操作系统管理。

地址空间

地址空间（address space）是一个非负整数地址的有序集合。

  • 在一个带虚拟内存的系统中，CPU从一个有N=2^n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间（virtual address space）。
    • 一个地址空间的大小是由表示最大地址所需的位数来描述的，例如：N=2^n叫做n位地址空间，现代系统通常支持32位、64位。
  • 一个系统还有一个物理地址空间（physical address space）。

地址空间清楚地区分了数据对象（字节）和它们的属性（地址）。推广，允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。这就是虚拟内存的基本思想：主存中的每字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

虚拟内存作为缓存的工具

概念上而言，虚拟内存被组织为一个由存放在磁盘上的N个连续的字节大小的单元组成的数组。每字节都有一个唯一的虚拟地址，作为到数组的索引。磁盘上数组的内容被缓存在主存中。

磁盘（较低层）上的数据被分割成块，这些块作为磁盘和主存（较高层）之间的传输单元。VM系统通过将虚拟内存分割为称为虚拟页（Virtual Page，VP）的大小固定的块来处理这个问题。类似地，物理内存被分割为物理页（Physical Page，PP），物理页也被称为页帧（page frame）。

在任意时刻，虚拟页面的集合都分为三个不相交的子集：

  • 未分配的：VM系统还未分配（或创建）的页，没有任何数据和它们相关联，因此也就不占用任何磁盘空间。
  • 缓存的：当前已缓存在物理内存中的已分配页。
  • 未缓存的：未缓存在物理内存中的已分配页。

DRAM缓存的组织结构

  • SRAM缓存：表示CPU和主存之间的L1、L2和L3高速缓存；
  • DRAM缓存：表示虚拟内存系统中的缓存，它在主存中缓存虚拟页。

命中：

DRAM比SRAM要慢大约10倍，而磁盘要比DRAM慢大约100000多倍。因此，DRAM缓存中的不命中比SRAM缓存中的不命中要昂贵得多。

虚拟页往往很大，通常是4KB~2MB。由于大的不命中处罚，DRAM缓存是全相联的，即任何虚拟页都可以放置在任何的物理页中，不命中时的替换策略（替换算法）也很重要。

因为对磁盘的访问时间很长，DRAM缓存总是使用写回，而不是直写。

页表

页表（page table）：存放在物理内存中，将虚拟页映射到物理页。每次地址翻译硬件将一个虚拟地址转换为物理地址时，都会读取页表。

image-20210119160023499

有效位：表明了该虚拟页当前是否被缓存在DRAM中。

  • 如果设置了有效位，那么地址字段就表示DRAM中相应的物理页的起始位置，这个物理页中缓存了该虚拟页；
  • 如果没有设置有效位，那么一个空地址表示这个虚拟页还未被分配，否则，这个地址就指向该虚拟页在磁盘上的起始位置。

页命中

image-20210119161010373

缺页

不命中称为缺页（page fault）。

image-20210119161304091

会触发缺页异常，调用内核中的缺页异常处理程序，该程序会选择一个牺牲页。然后进行替换。

image-20210119161334817

在磁盘和内存之间传送页的活动叫做交换（swapping）或者页面调度（paging）。

  • 按需页面调度（demand paging）：所有现代操作系统都使用的此种方法。
  • 尝试猜测不命中。

又是局部性

虚拟内存工作得相当好，主要归功于局部性。

尽管在整个运行过程中程序引用的不同页面的总数可能超过物理内存总的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页（active page）集合上工作，这个集合叫做工作集（working set）或者常驻集合（resident set）。在初始开销，也就是将工作页面调度到内存中后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。

虚拟内存作为内存管理的工具

实际上，操作系统为每个进程提供了一个独立的页表，因而也就是一个独立的虚拟地址空间。

image-20210119162540023

按需页面调度和独立的虚拟地址空间的结合，对系统中内存的使用和管理造成了深远的映像。特别地，VM简化了链接和加载、代码和数据共享，以及应用程序的内存分配。

虚拟内存作为内存保护的工具

控制内存的访问：

  • 不应该允许一个用户进程修改它的只读代码段；
  • 不应该允许它读或修改任何内核中的代码和数据结构；
  • 不应该允许它读或者写其他进程的私有内存；
  • 不允许它修改任何与其他进程共享的虚拟页面，除非所有的共享者都显示地允许它这么做。

image-20210119163923896

如果一个指令违反了这些许可条件，那么CPU就触发一个一般保护故障，将控制传递给一个内核中的异常处理程序。Linux shell一般将这种异常报告为”段错误（segmentation fault）“。

地址翻译

image-20210119164154992

形式上来说，地址翻译是一个N元素的虚拟地址空间（VAS）中的元素和一个M元素的物理地址空间（PAS）中元素之间的映射。

image-20210119164821923

image-20210119164908997

结合高速缓存和虚拟内存

image-20210119165020769

利用TLB加速地址翻译

在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器（Translation Lookaside Buffer，TLB）。

image-20210119165235372

多级页表

image-20210119165324919

Linux虚拟内存系统

image-20210119165626067

内存映射

Linux通过将一个虚拟内存区域与一个磁盘上的对象（object）关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射（memory mapping）。

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的交换文件（swap file）之间换来换去，也叫交换空间（swap space）或交换区域（swap area）。在任何时刻，交换空间都限制着当前运行着的进程能够分配的虚拟页面的总数。

再看共享对象

内存映射的概念来源于一个聪明的发现：如果虚拟内存系统可以集成到传统的文件系统中，那么就能提供一种简单而高效的把程序和数据加载到内存中的方法。

许多进程有同样的只读代码区域。

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象。

image-20210119170952830

私有对象使用一种叫做写时复制（copy-on-write）的巧妙技术被映射到虚拟内存

image-20210119171142464

再看fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。

再看execve函数

如下调用：

1

execve("a.out", NULL, NULL);

加载并运行a.out需要以下几个步骤：

  • 删除已存在的用户区域；
  • 映射私有区域；
  • 映射共享区域；
  • 设置程序计数器；

使用mmap函数的用户级内存映射

Linux进程可以使用mmap函数来创建新的虚拟内存区域，并将对象映射到这些区域中。

1
2
3
4

#include <unistd.h>
#include <sys/mman.h>

void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);

mmap函数要求内核创建一个新的内存区域，最后是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片（chunk）映射到这个新的区域。连续的对象片大小为length自己，从距文件开始处偏移量offset字节的地方开始。

munmap函数删除虚拟内存的区域：

1
2
3
4

#include <unistd.h>
#include <sys/mman.h>

int munmap(void *start, size_t length);

动态内存分配

动态内存分配器（dynamic memory allocator）。

动态内存分配器维护着一个进程的虚拟内存区，称为堆（heap）。

分配器有两种基本风格：

  • 显示分配器（explicit allocator）：C标准库的 malloc/free，C++的new/delete；
  • 隐式分配器（implicit allocator）：垃圾收集器。

malloc 和 free 函数

调用malloc函数来从堆中分配块：

1
2
3

#include <stdlib.h>
void *malloc(size_t size);
// 返回：若成功则为已分配块的指针，若出错则为NULL。

malloc返回一个指针，指向大小为至少size字节的内存块，这个内存块会为可能包含在这个块内的任何数据对象类型做对齐。

malloc不初始化它返回的内存，想要初始化可以使用calloc，calloc是一个基于malloc的瘦包装函数，它将分配的内存初始化为零。想要改变一个以前已分配的块大小，可以使用realloc函数。

可以通过使用mmap和munmap函数，显式地分配和释放内存，或者还可以使用sbrk函数：

1
2
3

#include <unistd.h>
void *sbrk(intptr_t incr);
// 返回：若成功则为旧地brk指针，若出错则为-1.

sbrk函数通过将内核的brk指针增加incr来扩展和搜索堆。

程序是通过调用free函数来释放已分配的堆块：

1
2

#include <stdlib.h>
void free(void *ptr);

ptr参数必须指向一个从malloc、calloc或者realloc获得的已分配块的起始位置。

image-20210119175823861

碎片

虽然有未使用的内存但不能用来满足分配请求。

  • 内部碎片（internal fragmentation）：在一个已分配块比有效载荷大时发生的。
  • 外部碎片（external fragmentation）：当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大。

隐式空闲链表

实际的分配器都需要一些数据结构，允许它来区别块边界，以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身。

image-20210119195313943

一个连续的已分配块和空闲块的序列：隐式空闲链表。

image-20210119195508814

空闲块是通过头部中的大小字段隐含地连接着的。

放置已分配的块

放置策略：

  • 首次适配（first fit）：
    • 优点：趋向于将大的空闲块保留在链表的后面。
    • 缺点：趋向于在靠近链表起始处留下空闲块的”碎片“，增加了对较大块的搜索时间。
  • 下一次适配（next fit）：如果上一次在某个空闲块里已经发现了一个匹配，那么很可能下一次也能在这个剩余块中发现匹配。
    • 优点：适配比首次适配明显要快一些，尤其是当链表前面布满了许多小的碎片。
    • 缺点：内存利用率要比首次适配低得多。
  • 最佳适配（best fit）：
    • 优点：内存利用率最高。
    • 缺点：对堆进行彻底的搜索，很慢。

分割空闲块

通常会选择将这个空闲块分割为两部分，第一部分变成分配块，剩下的变成一个新的空闲块。

获取额外的堆内存

如果合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块还不能满足足够大，或者如果空闲块已经最大程度地合并了，那么分配器就会通过调用sbrk函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

合并空闲块

假碎片（fault fragmentat）：相邻的空闲块。

何时合并：

  • 立即合并（immediate coalescing）：每一个块被释放时，就合并所有相邻块；这种方式会产生抖动，块会反复地合并，然后马上分割；
  • 推迟合并（deferred coalescing）：等到某个稍晚时候再合并。

显式空闲链接

例如：堆可以组织成一个双向空闲链表，在每个空闲块中，都包含前驱和后继指针。

垃圾收集

可达图：

image-20210119202149656

Mark&Sweep垃圾收集器

标记（mark）清除（sweep）：

image-20210119202403466

C程序中常见的与内存有关的错误

  • 间接引用坏指针；
  • 读未初始化的内存；
  • 允许栈缓冲区溢出；
  • 假设指针和它们指向的对象是相同大小的；
  • 造成错位错误；
  • 引用指针，而不是它所指向的对象；
  • 误解指针运算；
  • 引用不存在的变量；
  • 引用空闲堆块中的数据；
  • 引起内存泄漏；
CATALOG
    FEATURED TAGS
    Linux BBigData CSAPP LeetCode TOUR TensorFlow HADOOP Spark Java Kafka Kubernetes
    FRIENDS