操作系统是如何实现虚拟内存的

要明白操作系统是如何实现虚拟内存的，首先应该明白操作系统为什么要需要虚拟内存

为什么需要虚拟内存

早期的程序中访问的内存地址都是实际的物理内存地址。

程序需要加载在内存上运行，即形成进程。起初，只有一个进程信息可以被加载到内存，需要运行另一个进程时，需要将当前进程的信息先存储到磁盘上，然后从磁盘上读取另一个进程的信息。但是磁盘I/O是很慢的，导致任务切换的效率很低 。因此，人们希望将多个进程可以共同存放在内存上，这就出现了一个问题：如何避免一个进程读取、篡改另一个进程的内存信息，即对进程间实现隔离和保护。

同时，程序在编写时，其访问数据和指令跳转时的目标地址很多是固定的。但是程序在加载在内存时，不可能说每次我们都能够分配固定地址的内存给它。尤其是在我们想运行同一程序的多个实例的时候，由于同一程序使用的物理地址是一样的，一起运行就会有冲突。

另外，程序使用的内存会被物理内存所限制，即程序使用的内存不能超过物理内存。

内存虚拟化就是为了解决这些问题出现的，它将程序给的地址看作是虚拟地址(Virtual Address)，然后通过将虚拟地址转换为实际的物理地址，通过操作系统对这个转化过程的控制，来实现隔离、保护、和易用。

如何实现虚拟内存

我们可以把我们为什么需要虚拟内存抽象成虚拟内存要实现的几个目标。

虚拟内存的几个目标

• 不可见性

  即对于程序来说，并不知道内存被虚拟化了，程序认为自己拥有独自的物理内存

• 高效率

  虚拟内存的效率要高,不能让程序运行变得太慢(时间效率),也不能因为实现虚拟内存占用太大空间(空间效率)。为了保证时间效率，需要用到硬件的支持。

• 保护

  操作系统需要保证进程间相互隔离，同时也要将操作系统与进程隔离开来。

实现虚拟内存的关键技术是：地址转化，实现地址转化的硬件称为内存管理单元MMU(Memory Management Unit)。我们先来看看地址转化最初的原型：base and bounds，也叫动态重定位(dynamic relocation)。

动态重定位

在动态重定位方法中，每个CPU需要两个寄存器来帮助它实现地址转化：base register 和 bounds register。

程序在编写和编译时，其使用的内存地址从0开始。当程序运行时，如OS打算在32KB处开始载入程序，则OS将base寄存器的值设为32KB。程序的地址转化成：
$$
实际物理地址 = 虚拟地址 + base
$$
因此，base寄存器实现了地址转化的作用，而bounds寄存器的作用则是进行保护，限制地址引用的范围。

当进行进程间切换时，需要保存base-bounds寄存器的值，以便恢复进程。这个值保存在进程控制块PCB(process control block)里。

动态重定位的缺点

动态重定位的缺点在于它会造成内部碎片(internal fragmentation)，造成内存的浪费。如图所示，由于进程的堆和栈不是很大，其中的内存就被浪费掉了

。

为了解决内部碎片的问题，出现了分段技术。

分段(Segmentation)

分段技术的出现是为了解决程序因占用连续的内存空间而产生内部碎片的问题，利用分段解决内部碎片问题的思想很简单：将进程的内存空间按照逻辑进行分段，每段可存放在物理内存的不同位置，在动态重定位一对base-bounds寄存器的基础上，给进程的每段都分配一对base-bounds寄存器。常见分段方式分为三段：代码段、栈和堆。比如说我们要对某个代码段的虚拟地址进行寻址，只需要根据代码段的base-bounds寄存器，按照动态重定位的方式寻址即可。那么，给定一个虚拟地址，如何判断它是属于哪个段的呢？

如何确定虚拟地址属于哪个段

有两种方法进行确定。

将地址前面几位当作段标志

比如一个14位的虚拟内存，我们可以将其前两位当做段的标志位，如00表示代码段，01表示堆，11表示栈。

根据虚拟地址如何产生的来判断

如果虚拟地址由程序计数器(program count)产生的，则为代码段，如果为栈指针，则为栈段，否则为堆段。

MMU记录的其它信息

除了每段的base-bounds寄存器外，MMU还记录了段的其它一些信息。

因为栈是反方向扩张的，因此需要记录内存扩张的方向。Protection用来表示段的属性，可以用来共享一些段。

分段的缺点

每个程序都不一样，其各段所占用的内存空间大小也不一样，造成内存的占用情况如下图所示

内存上出现了各种大小的小洞，如果我们需要分配一个新段，比这个新段大小小的内存空间对于我们来说都是没有用的，这就造成了内存的浪费，这种浪费称为外部碎片(external fragmentation)。为了解决这个问题，出现了各种方法，如内存整理(compact)，各种内存管理算法(best fit、first fit)。但是并没有完美的方法解决这个问题。

分页(Paging)

分段中引起外部碎片的原因是每段的大小都不一样。分页对内存的处理方式是:将虚拟内存和物理内存分为若干个固定长度的单元，这个单元称为页。

如何寻址

每个进程都对应一个页表(page table)，页表存储着虚拟内存页对应的实际物理内存页。虚拟地址需要分为两部分：虚拟页号VPN(virtual page number)和偏移量offset。通过页表可以知道VPN对应的PFN，通过offset进行准确寻址。

页表存放在哪

页表占用空间很大。举个例子，假设一个32位的地址空间，每页大小为4KB，则虚拟内存分为20位的VPN和12位的偏移量(10位1KB，4KB则为12位)。20位的VPN表示存在$2^{20}$条转化映射，假设每条映射占用4字节，则一个页表需要占用4M的大小。

由于页表太大，因此将内部存储在内存中。在MMU中的页表基(page-table base)寄存器中存放页表在内存中的起始位置。

分页的缺点

因为页表存放在内存上，在对虚拟地址进行转化时，首先需要从内存中的页表读到其对应物理页，相当于多了一次内存的读操作，因此分页会降低速度，同时页表的存储占用过多内存。

给分页加加速

要想加加速，就需要硬件来帮个忙。TLB (Translation-Lookaside Buffer)，中文译为快表。TLB是集成在MMU上的缓存，用来存储部分页表记录。

查询页表时，首先去TLB查，查到了称为TLB命中(hit)，如果没查到，称为TLB失败(miss)，此时去内存中的页表查。缓存大小有限，当有新记录放入到TLB，需要进行缓存置换，缓存置换有许多方法，这里不再展开。