CSAPP笔记之虚拟存储器

2019-04-27

笔记

CSAPP, 笔记

Catalogue

1. 物理和虚拟寻址
1. 1.1. 1. 物理地址
2. 1.2. 2. 虚拟地址
2. 虚拟内存的三个角色
3. 地址翻译
1. 3.1. 利用TLB加速地址翻译
2. 3.2. 多级页表
4. 动态内存分配
5. 参考资料

下面是对《深入理解计算机系统》以及虚拟内存与动态内存分配博客文章的学习笔记

物理和虚拟寻址

1. 物理地址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组，每字节都有唯一的物理地址，第一个字节的地址为0，接下来的字节地址为1，再下一个为2，依此类推。CPU访问存储器的最自然的方式就是使用物理地址，我们把这种方式称为物理寻址

物理寻址

当CPU执行这条加载指令时，它会生成一个有效的物理地址，通过存储器总线，把它传递给主存，主存取出从物理地址4处开始的4字节的字，将将它返回给CPU，CPU会将它存放到一个寄存器里。

物理地址一般应用在简单的嵌入式微控制器中（汽车、电梯、电子相框等），因为应用的范围有严格的限制，不需要在内存管理中引入过多的复杂度。

2. 虚拟地址

现代处理器使用一种称为虚拟寻址的寻址方式，如下图

虚拟寻址

使用虚拟地址时，CPU通过生成一个虚拟地址来访问主存，这个虚拟地址在被送到存储器之前先转换成适当的物理地址，将一个虚拟地址转换为物理地址的任务叫做地址翻译，这个任务就是靠MMU内存管理单元实现的。

虚拟内存的三个角色

虚拟存储器提供了三个重要的能力：

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

作为缓存工具

概念上讲，虚拟内存就是存储在磁盘上的N个连续字节的数组，这个数组的部分内容，会缓存在DRAM中，在DRAM中的每个缓存块称为页（page)，类似地，物理存储器被分割成物理页（页帧），页和页帧大小一致。

虚拟内存与物理内存

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

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

页表

同任何缓存一样，虚拟存储器必须有某种方法来判定一个虚拟页是否存放在DRAM中的某个地方，如果是，系统还必须确定这个虚拟页存放在哪个物理页中，如果不命中，系统必须判断这个虚拟页存放在磁盘的哪个位置，在物理存储器中选择一个牺牲页，并将虚拟页从磁盘拷到DRAM中，替换这个牺牲页。

这个机制就是通过页表（page table)，每个页表实际上是一个数组，数组中的每个元素都称为页表项(PTE，page table entry)，每个页表项负责把虚拟页映射到物理页上，在DRAM中，每个进程都有自己的页表，具体如下：

注意：页表是存放在物理存储器中的，每次地址翻译硬件一个虚拟地址转换为物理地址时都会读取页表

通常我们可以假设每个PTE是由一个有效位（valid bit)和一个n位地址字段组成的，有效位表明了该虚拟页当前是否被缓存在DRAM中

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

在一个页表中查询，就会遇到两种情况，一种是命中（page Hit)，另一种则是未命中（page Fault)

命中的时候，DRAM有对应的物理页，可以直接访问
不命中的时候，DRAM中并没有对应的数据，所以需要执行一系列的操作（从磁盘复制到DRAM中），具体为：
- 触发Page fault，也就是一个缺页异常
- 缺页异常调用内核的缺页异常处理程序，选择DRAM中需要被置换出的page，并将数据从磁盘复制到DRAMz中
- 重新启动导致缺页的指令，这时候就会命中

作为内存管理工具

每个进程都有自己的虚拟地址空间，这样一来，对于进程来说，它们看到的就是简单的线性空间（但实际上在物理内存中可能是间隔，支离破碎的），具体的映射过程如下：

内存管理

在内存分配中没有太多限制，每个虚拟页都可以被映射到任何的物理页上。这样也带来一个好处，如果两个进程间有共享的数据，那么直接指向同一个物理页即可

虚拟内存带来的另一个好处就是可以简化链接和载入的结构（因为有了统一的抽象，不需要纠结细节）

独立的地址空间允许每个进程的存储器映像使用相同的基本格式

作为内存保护工具

页表中的每个条目的高位部分是表示权限的位，MMU 可以通过检查这些位来进行权限控制（读、写、执行），如下图所示：

内存保护工具

每个PTE中已经添加了三个许可证：

SUP位表示进程是否必须运行在内核模式才能访问该页；运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问那些SUP为0的页面
READ位和WRITE位控制对页面的读和写访问

地址翻译

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

N=2^n： N表示虚拟地址空间中的地址数量
M=2^m: M表示物理地址空间中的地址数量

虚拟地址中的元素：

TLBI: TLB 的索引值
TLBT: TLB 的标签(tag)
VPO: 虚拟页偏移量
VPN: 虚拟页编号

物理地址中的元素：

PPO: 物理页偏移量
PPN: 物理页编号

下面看一个具体的例子来说明如何进行地址翻译：

地址翻译

具体的访问过程为：

通过虚拟地址找到页表(page table)中对应的条目
检查有效位(valid bit)，是否需要触发页错误(page fault)
然后根据页表中的物理页编号找到内存中的对应地址
最后把虚拟页偏移和前面的实际地址拼起来，就是最终的物理地址

在上述第二步中需要检查有效位，有效位如果等于0，那么页面就不在存储器中（也就是缺页），所以这里有两种情况：Page Hit 和Page Fault，先来看看Page Hit的情况：

页面命中

处理器生成一个虚拟地址，并把它传送给MMU
MMU生成PTE地址，并从高速缓存/主存请求得到它
高速缓存/主存向MMU返回PTE
MMU构造物理地址，并把它传送给高速缓存/主存
高速缓存/主存返回所请求的数据字给处理器

Page Fault就要复杂一点，第一次触发页错误会把页面载入内存/缓存，然后再以Page Hit的机制得到数据

这里有 7 步，前面和 Page Hit 是一致的，先把虚拟地址发给 MMU 进行检查，然后发现没有对应的页，于是触发异常，异常处理器会负责从磁盘中找到对应页面并与缓存/内存中的页进行置换，置换完成后再访问同一地址，就可以按照 Page Hit 的方式来访问了。

利用TLB加速地址翻译

每次CPU产生一个虚拟地址，MMU就必须查阅一个PTE，以便将虚拟地址翻译为物理地址，在最糟糕的情况下，这又会要求从存储器取一次数据，代价是几十到几百个周期。许多系统都试图消除这样的开销，它们在MMU中包括了一个关于PTE的小的缓存，称为翻译后备缓冲器（Translation Lookaside Buffer，TLB)

TLB是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。

使用TLB的流程是：

CPU生成一个虚拟地址
如果TLB中有对应的PTE，那么MMU从TLB中取出对应的PTE
MMU将虚拟地址翻译成物理地址，并且将它发送到主存
主存将所请求到的数据字返回给CPU

TLB命中

下面是TLB未命中的情况：

TLB未命中

多级页表

如果我们有一个32位的地址空间，4KB的页面和一个4字节的PTE，那么即使应用所引用的只是虚拟地址空间中很小的一部分，也总是需要一个4MB的页表驻留在存储器中。对于地址空间为64位的，情况更复杂。

所以我们需要一种多级页表的方法，第一层的页表中的条目指向第二层的页表，一个一个索引下去，最终寻找到具体的物理地址，整个翻译过程如下：

多级页表

动态内存分配

程序员通过动态内存分配（例如malloc)来让程序在运行时得到虚拟内存，动态内存分配器维护着一个进程的虚拟存储器区域，称之为堆(heap)。

分配器将堆视为一组不同大小的块（block)的集合来维护，每个块就是一个连续的虚拟存储器片，要么是已分配的，要么是空闲的。已分配的块显式地保留为供应用程序使用，空闲块是可用来分配的，空闲块保持空闲，直到它显式地被应用所分配。

分配器有两种类型的分配器：

显式分配器：应用分配并且回收空间（C语言中的malloc和free)
隐式分配器（又叫做垃圾收集器）：应用只负责分配，但是不负责回收，由垃圾收集器去回收内存空间（比如Java语言中的垃圾收集）

一个简单的使用 malloc 和 free 的例子：

#include <stdio.h>
#include <stdlib.h>
void foo(int n) {
    int i, *p;
    
    /* Allocate a block of n ints */
    p = (int *) malloc(n * sizeof(int));
    if (p == NULL) {
        perror("malloc");
        exit(0);
    }
    
    /* Initialize allocated block */
    for (i=0; i<n; i++)
        p[i] = i;
    /* Return allocated block to the heap */
    free(p);
}

分配器有如下的限制：

不能控制已分配块的数量和大小
必须立即响应malloc请求（不能缓存或者给请求重新排序）
必须在未分配的内存中分配
不同的块需要对齐（32位中的8byte，64位中16位byte)
只能操作和修改未分配的内存
不能移动已分配的块

性能指标

在以上分配器的限制之下，分配器的编写者试图实现吞吐率最大化和存储器使用率最大化，而这两个性能指标往往是相互冲突的。

吞吐率定义为每个单位时间里完成的请求数，例如，如果一个分配器在1秒钟内完成500个分配请求和500个释放请求，那么它的吞吐率就是每秒1000次操作。

另一个目标就是最大的内存利用率，影响内存利用率的主要因素就是【内存碎片】，内存碎片又分为内部碎片和外部碎片两种。

内部碎片

内部碎片指的是对于给定的块，如果需要存储的数据(payload)小于块大小，就会因为对齐和维护所需的数据结构的缘故而出现无法利用的空间，例如：

内部碎片

外部碎片

外部碎片指的是内存中没有足够的连续空间，如下图所示，内存中有足够的空间，但是空间不连续，所以成为了碎片：

垃圾回收

垃圾回收器是一种动态存储分配器，它自动释放程序不再需要的已分配块。这些块就称为垃圾。自动回收堆存储的过程叫做垃圾回收

垃圾收集器的基本知识

垃圾收集器将存储器视为一张有向可达图，其形式如下图

可达图

该图的节点被分成一组根节点和一组堆节点。每个堆节点对应于堆中的一个已分配块。当对于堆中的任何一个节点，如果从任何一个根节点出发都能到达，那么我们可以说该节点是可达的，那么该节点占据的内存块还是有用的，能够被再次利用。在任何时候，不可达节点就是垃圾，不能被应用程序再次利用，垃圾回收器会回收掉该节点，清除没有用的对象。垃圾回收器的作用就是一直维护这张可达图，直到应用程序不再运行。（类似Java虚拟机中的可达性分析算法）

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

C程序中常见的与存储器有关的错误：

间接引用坏指针
读未初始化的存储器
允许栈缓冲区溢出
错位错误
引用指针，而不是它所指向的对象
引用不存在的变量
引用空闲堆中的数据
引起存储器泄漏

参考资料

《深入理解计算机系统》
https://wdxtub.com/2016/04/16/thin-csapp-7/
https://www.alonehero.com/2018/01/17/v8-javascript%E5%BC%95%E6%93%8E-%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B61/