操作系统复习之内存的虚拟化

这篇文章主要记录一下操作系统的内存虚拟化部分的复习。

地址空间

在早期的机器上并没有提供多少抽象给用户，操作系统就如同一个函数库占据了一部分内存的空间，则用户进程使用剩余的内存空间。一段时间后，人们希望能够更高效的共享一台机器，去执行一些进程任务，所以这就产生了对内存共享使用的一个需求。

首先是一种时分共享的方法，先让一个进程占用所有的可用内存并运行，当发生上下文切换的时候，将它所有的状态信息保存在磁盘上。但这种方法实在是太慢了，尤其是内存增长到一定程度的时候，上下文切换的开销显著的提高。

所以我们考虑空分共享方法，从剩余内存中划分一小部分分配给该进程，使得所有进程都能同时驻留在内存里面，但这样这进程与进程之间的隔离性就成了一个比较重要的安全问题：我们要确保一个进程不能读改另一个进程的内存。

因此这就需要操作系统提供一个易用的物理内存抽象，而这个抽象就叫做地址空间，指的是运行中的程序所看到的内存信息：程序的代码、程序的局部变量、函数调用信息、以及使用malloc()动态分配的内存等。

这个抽象主要有三个目标。第一是透明性，操作系统实现内存抽象的方式不应让程序看到、感知到。第二个目标是效率，也就是能够尽可能高效的完成这一种抽象，第三个目标是保护，保护进程不被其他进程所影响。

所以在这个基础上，在现代操作系统里面，我们执行的程序所看到的内存空间都并不是真实的内存空间（虚拟的），我们所看到的地址需要操作系统进行一个转换，才能指向一个真实的物理地址。

内存API

存的分配主要有两种，一种是显示的分配，一种是隐式的分配。

如一个局部变量，编译器会自动帮助我们在栈申请一个空间去存储这个数据，不需要我们手动的去获取和释放，这就是隐式的分配。

相对应的是显示的分配，这就需要程序员手动的去获取一段内存空间并使用，在使用完后会手动地去把这一段内存释放掉。

这就对应了两个常见的API调用：

malloc
- int *x = malloc(10 * sizeof(int));
- 手动的去获取一段内存，其大小为可以存储10个 int 型数据的空间长度
free
- free(x);
- 手动的把malloc所获取的内存释放掉

这种显示的分配内存必须非常的小心。一个是需要判断能否获取所需要的空间，否则会产生错误。另一个是使用完后需要及时的释放所获取的空间，否则会发生内存泄漏。还有一些是反复释放获取到的内存或是释放没获取到的内存，这也会产生错误。

早期的地址转换

在CPU虚拟化的实现中，我们遵循的原则是受限直接访问，这允许大部分程序直接通过命令访问硬件，只在一些关键的点让操作系统介入来确保能够安全的运行，避免一些恶意的操作。首先，我们需要判断这种方法能否直接应用于我们的内存虚化中。

我们首先考虑一个简单的、基于硬件的地址转换：

首先规定进程的地址空间小于物理内存的空间
相对应的，在物理内存中划分一个上界与一个下界
在程序访问内存时，根据其虚拟地址和上下界，自动把虚拟地址重定位到真实物理内存中
并且我们要保证虚拟内存所对应的物理内存地址仍在其界限内，不会发生越界访问，既不能够访问别的程序的内存空间

按照上述的方法，我们需要保存一些关键的数据，以确保在上下文切换的时候，我们的程序的状态能够顺利的恢复：

物理内存的基址
空间大小的上限

则进程在访问内存的时候会发生如下的转换：

物理地址 = 基址 + 虚拟地址（虚拟地址需小于空间大小的上限）

而系统对虚拟内存地址的控制，即地址转换，这对程序来说是透明的、是不可见的，程序并不知道自己所引用的内存被重定位了，这就制造了一种美妙假象。

但很遗憾，这种管理方法并不是很高效。我们的进程并不会使用完它虚拟内存空间里的所有内存，这就导致了有很大一部分的内存被浪费掉了，所以我们需要一个更复杂的机制，以便我们能够更充分的利用好这宝贵的内存空间。

分段

分段分配指的是我们按照程序对内存使用的逻辑关系，把内存空间划分为代码段、堆和栈三个部分，再相对应的给这三个部分分配具体的物理内存空间。而不是像之前一样把进程的所有地址空间都完整的加载进内存中。

另外分段机制在原有的基础上，仍需要额外保存一些关键的数据，以确保顺利进行上下文切换：

哪一段（表明该部分是分配给代码段还是堆和栈）
地址的增长方向（代码段和堆是从低地址增长到高地址，而栈是从高地址增长到低地址）
保护（可读、可写、可执行）

例如：

段	基址	大小	增长方向	保护
代码	32KB	2KB	低到高	读—执行
堆	34KB	2KB	低到高	读—写
栈	28KB	2KB	高到低	读—写

另外，如何判断当前这一虚拟空间地址是处于哪一个段的呢？

我们可以把虚拟地址二进制形式的前两位拿出来，让它代表哪一个段，剩余的代表段内的偏移量。

如：

这个方法相较于刚刚的直接分配，它更好的利用了我们的内存空间，但这貌似还不够，能否还有更好的方法可以更充分的利用物理内存空间呢？

空闲空间的管理

无论是操作系统给进程分配物理内存空间，还是进程在自己的虚拟地址空间内使用malloc动态分配空间，都需要找到一段空闲的空间才能进行分配。所以这就需要我们对空闲空间进行管理，以便在需要的时候更好的进行分配，也需要去尽量避免一些常见的问题，比如内存空间碎片问题。

首先，我们需要有一个列表，这个列表里边记录目前空间有哪些是空闲的、目前空间的大小是多少等关键的数据。比如我们可以使用链表，某个节点描述某一个区域有多少个空闲空间，再用一个指针指向下一个描述空闲空间的节点。

当我们把空闲空间分割一部分分配给需要的进程后，要及时的更新当前剩余的空间（更新列表项），当进程使用完这段空间，将其归还给操作系统后，操作系统需要检查归还的空间能否与旁边的空间进行一个合并，如果可以合并，则还需要进行一些合并的操作。

另外，当某个空间用完之后，将其归还给操作系统时，我们仅需要给free函数传入内存空间的起始地址并没有传入这个空间的大小，所以我们需要对所分配的空间大小进行一个记录，通常是在所分配的空间前面加一个小小的头部数据：

typedef struct header_t { 
    int size; 
    int magic; 
} header_t;

所以当我们需要分配空间时，并不仅仅只是分配参数所指定的空间大小，而是在这个基础上还要加上8个字节以保存头部数据，当然这一切对于我们的进程来说是透明的，并不会感知到有这么一个数据的存在。

另外存储空闲空间大小的这一个链表，可以开辟一个空间来专门存储，也可以像那个嵌在每段空间的头部记录里边，用指针指向下一段空间就可以了。

如：

说完了这些，我们还需要考虑如何基于这张空行空间列表来进行一个空间分配，才能在最大程度上避免产生内存碎片（内存碎片很难被消灭，只能说尽量去避免）。

我们有下列几种方法：

最优匹配
- 最优匹配是遍历空闲空间列表，找到最适合所需要空间大小的一块内存空间。
- 这种方法需要完整的进行遍历，开销非常大。
最差匹配
- 最差匹配与最优匹配恰恰相反，它是尝试寻找最大的空闲块并进行分割。
- 这种方法不仅性能开销大，也很容易产生内存碎片。
首次匹配
- 首次匹配是找到第一个足够大且能够满足需求的空间块。
- 这种方法并不需要遍历所有空闲块，但有时候会让空闲列表开头部分有很多碎片。
下次匹配
- 不同于首次匹配，每次从列表开始进行查找，下次匹配维护了一个指针，指向了上次查找结束的位置，从该位置进行一个查找，避免了对列表头部频繁的分割。

另外还有一种方法叫做伙伴算法，该算法所管理的空闲空间的大小都是二的幂次方。当有一个空间分配请求时，空间会被递归的一分为二，直到刚好可以满足大小为止。当空间被释放时，为检查其伙伴空间是否空闲，若空闲则会合二为一。

分页

在分段里边，物理内存空间会划分成大小不同的片段，这样很常容易产生碎片。那我们能否考虑将空间划分成大小一致的单元片段？我们把一个单元片段称为页。

简单来说就是把虚拟空间划分成等长的片段，且可以将其乱序的存放在物理内存中。

例如：

与分段机制类似，我们也可以将虚拟地址二进制形式的头两位用来表明该地址是哪一个页的，而剩余的作为页内偏移量。

如：

这样就可以很方便的通过地址转换操作，将其转化为物理地址。

那问题来了，我们地址转换所需要用到的数据如何存储？存储在哪呢？

例如，想象一个典型的 32 位地址空间，带有 4KB 的页。这个虚拟地址分成 20 位的 VPN 和 12 位的偏移量。一个 20 位的 VPN 意味着，操作系统必须为每个进程管理 220个地址转换（大约一百万）。假设每个页表格条目（PTE）需要 4 个字节，来保存物理地址转换和任何其他有用的东西，每个页表就需要巨大的 4MB 内存！这非常大。现在想象一下有 100 个进程在运行：这意味着操作系统会需要 400MB 内存，只是为了所有这些地址转换！32位况且如此，那64位的地址空间呢？

不仅消耗的内存大，而且开销也很大，例如一个指令需要访问内存，则会发生四次内存访问操作：

一次访问内存的代码处
一次访问数据处
两次访问地址转换列表

这样会带来一个非常大的性能开销。

TLB（快速地址转换）

那可不可以把地址转换列表缓存在某一个地方呢？就像我们处理器对内存的访问通常有一级、二级高速缓存。

这里介绍一下所谓的地址转换旁路缓冲存储器（translation-lookaside buffer，TLB[CG68,C95]），它就是频繁发生的虚拟到物理地址转换的硬件缓存（cache）。因此，更好的名称应该是地址转换缓存（address-translation cache）。

TLB是一个全相联的缓存器，对地址转换可以存储于其任意位置内，对每次内存访问，硬件先检查 TLB，看看其中是否有期望的转换映射，如果有，就完成转换（很快），不用访问页表。再加上时间局部性和空间局部性对缓存命中率的提升，因此 TLB 带来了巨大的性能提升。

稍微提一下，时间局部性是指，最近访问过的指令或数据项可能很快会再次访问。空间局部性是指，当程序访问内存地址 x 时，可能很快会访问邻近 x 的内存。

下边探讨一个小小的细节，TLB 到底存储了些什么数据呢？

简单的来说：VPN + PFN + 其他位

如果这样，进程进行一个上下文切换的时候，需要把 TLB 原有的内容清空，但这样每次进行完上下文切换后都会发生 TLB 未命中，也会带来一个不小的开销。

我们可以考虑将一个 TLB 项和某个进程联系在一起，例如添加一个 ASID段，与进程相互绑定，则 TLB 项应存储如下内容：

VPN + PFN + 有效位 + 保护位 + 其他位 + ASID

多级页表

时间开销可以通过 TLB 解决，那空间开销呢？

有一种简单的方案，就是使用更大的页，从而减少页表项，但这样也会带来一个内存碎片，导致宝贵的内存空间被浪费掉。所以这种简单的方法并不可行。

另一种方法，我们可以考虑分段和分页进行混合，将虚拟空间地址划分如下：

这样看起来似乎很不错，但如果有一个大而稀疏的堆，仍然可能导致大量的页表浪费。其次，这种杂合容易导致外部碎片再次出现。

另一种方法并不依赖于分段，但也试图解决相同的问题：如何去掉页表中的所有无效区域，而不是将它们全部保留在内存中？我们将这种方法称为多级页表（multi-level page table），因为它将线性页表变成了类似树的东西。这种方法非常有效，许多现代系统都用它。

多级页表的基本思想很简单。首先，将页表分成页大小的单元。然后，如果整页的页表项（PTE）无效，就完全不分配该页的页表。为了追踪页表的页是否有效（以及如果有效，它在内存中的位置），使用了名为页目录（page directory）的新结构。页目录因此可以告诉你页表的页在哪里，或者页表的整个页不包含有效页。

举一个简单的例子：

在线性页表中，中间有很大一部分空间被浪费掉了，而在多级页表中，能够紧凑的将它们组合在一起，而且也不用像线性页表一样，需要一段连续的空间来存储这个页表，这种间接方式，让我们能够将页表页放在物理内存的任何地方。

但多级页表并不是说没有代价的，虽然在节省了空间开销的同时，它增加了一次寻找二级页表的时间开销，所以说并不是页表分得越多级越好。但同样的，我们需要使用 TLB 为这一过程进行加速。

这里额外提一下，还有另外一种地址转换映射的方法。在上边我们是通过虚拟地址向物理地址进行一个转换，在反向页表中，每个项代表系统的每个物理页，页表项告诉我们哪个进程正在使用此页，以及该进程的哪个虚拟页映射到此物理页。但为了能够顺利的找到这么一个映射，需要做一个线性的扫描，这个线性扫描是的时间开销是非常大的。

内存页替换

下面讨论一下另一个问题，如果物理内存空间不够了怎么办？

一个解决方案是将物理内存的内容保存到交换空间里面（这个空间可以是磁盘）。

我们需要在我们的页表或我们的 TLB 里边标注该页是否存在于内存中，还是存在于磁盘中？当读到某一段内存，发现该段内存并不在物理空间，而在交换空间中，则抛出一个页错误并交由操作系统来进行处理，由操作系统将其从交换空间加载进内存。如果内存已满的话，会通过某些策略将物理内存的某些页交换出去，并把需要的页交换进来，这个策略后续会提到。

通常来说这个交换并不是等到内存已满的时候才会去执行，为了保证有少量的空闲内存，大多数操作系统会设置高水位线（HW）和低水位线（LW）来帮助决定何时从内存中清除页。原理是这样：当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程会开始运行，直到有 HW 个可用的物理页。通常也需要从交换成本来判断是否要把该页交换出去，例如该页是否被修改，如果被修改了，则需要将数据写回磁盘，若没被修改，则只需直接清空即可。

下面讲一下几个替换策略：

最优替换策略
- 替换内存中在最远将来才会被访问到的页，可以达到缓存未命中率最低。
- 这种方法非常难以实现。
简单策略：FIFO
- 页在进入系统时，简单地放入一个队列。当发生替换时，队列尾部的页（“先入”页）被踢出。
- 这种方法实现起来虽然非常简单，但是很容易错误的把重要的页踢出去，导致性能下降。
另一简单策略：随机
- 该方法是随机选择某些页将其踢出去。
- 虽然实现起来简单，但实际运行效果也有运气成分在内。
利用历史数据：LRU
- 该方法使用了局部性原则，意思是最近用过的，将来可能很快会被用到，所以可以选择剔除一些最近并没有被用到的页。
- 虽然该方法能够有效的逼近最优策略，但其性能开销和实现难度仍然不可忽视。

绝对的 LRU 实现起来性能开销不小，但我们可以采用近似 LRU 的方法：

该方法为每一个页表添加一个使用位，该页发生读或是写的操作时，将该位置 1 ，然后定时将其清除（置0）。当需要进行页交换时，可以线性的扫描该使用位，找到第 1 个 0 ，并将其对应的页替换出去。