内存虚拟化

OSTEP(Operation Systems Three Easy Pieces)的内存虚拟化部分，12到24章。

早期的基于硬件的动态重定位使用一个基址寄存器和一个界限寄存器来简单地完成地址转换。操作系统需要在进程创建时分配内存，进程退出时回收内存，上下文切换时保存上下文到pcb中。提供异常处理机制给用户程序。

如果将整个内存段放入物理内存，类似堆和栈之间的大块空闲空间会造成物理内存的浪费，分段机制在 MMU 中引入不止一个基址和界限寄存器对，而是给地址空间内的每个逻辑段（segment）一对。段寄存器一般分为段号和段内偏移。还需要一些权限支持，保护位来指定它的权限。分段机制容易导致外部碎片，没有特别好的解决方案，唯一的办法是分配相同大小的内存块。分段还是不足以支持更一般化的稀疏地址空间，例如一个很大但是稀疏的堆。

空闲空间管理中，如果要管理的空闲空间由大小不同的单元构成，管理就变得困难。这种情况出现在用户级的内存分配库，或者操作系统用分段的方式实现虚拟内存，会出现外部碎片。管理空闲空间的结构通常称为空闲链表，空闲列表可以对节点进行分裂和合并。空闲列表初始化的时候只有一个大块。如果用户程序的内存耗尽，可以向系统申请扩大堆的内存。在分配空闲空间时，常见的策略有最优、最差、首次、下次匹配等。其它的一些策略还有分离不同大小的专用的空闲列表，使用伙伴系统等。

在空闲空间管理中，如果操作系统将空间划分为不同大小的块，空间本身会碎片化，随着时间推移，分配内存会变得比较透难。另一种方法把空间分为固定大小的片，也就是分页。每个逻辑单元称为页，相应的物理内存称为页帧（page frame）。操作系统为每个进程维护一个页表，用于地址转换。在切换进程的时候需要更换页表。虚拟地址分为虚拟页号和页内偏移，虚拟页号用于在页表中查找物理页号，页内偏移用于得到真正的物理地址。由于页表很大，所以它一般被放在内存中。页表是虚拟页号到物理页号的映射，分为许多页表项（PTE），PTE分为物理页号和一些标志位。页表需要增加内存引用和内存访问的次数，实际上会使进程的速度变慢。

使用页表可能会增加性能开销，主要是映射信息需要存在内存中，增加了存储开销和访问内存的次数。辅助来自硬件，增加了用于地址转换的缓存（TLB），现实中的TLB通常有极好的性能，命中率很高。TLB由硬件或者操作系统来管理，早期的CISC中由纯硬件管理，现代一点的RISC中操作系统也可以使用特权级指令来管理。常见的替换策略有LRU和随机。

要想减少页表所占的内存，可以使用更大的页，但是使用大页会造成内部碎片。分页和分段的混合方法不为进程的整个地址空间提供单个页表，而是每个逻辑段提供一个。这样虽然节省了内存，但是又带来了外部碎片，还有分段的缺点，不足以支持更一般化的稀疏地址空间。另一种方法是多级页表，只维护有效的映射，将线性页表改为多叉树的结构。多级页表减少了内存的占用和外部碎片，但是增加了TLB未命中情况下的访存次数，也增加了复杂性。

如果操作系统要透明地提供巨大的地址空间，需要提供比物理内存更大的地址空间，利用大而慢的存储设备（硬盘），在硬盘上开辟出一块空间作为交换空间。如果希望换页到硬盘中，需要在现有的页表和tlb中加入更多的机制，在pte中加入一位存在位指明在物理内存中还是在硬盘中，访问在硬盘中的页会触发页错误（page fault），操作系统这时被唤起处理，它会将请求发给硬盘并将页读回来，再更新pte中的存在位和tlb。在硬盘中的页不止是在物理内存耗尽时才被换到交换空间，操作系统可以主动的预留一小块物理内存，操作系统会设置高位流水线（HW）和低位流水线（LW），用来帮助决定何时换出页，当操作系统发现有少于 LW 个页可用时，后台负责释放内存的线程会开始运行，直到有HW个可用的物理页。

确定要踢出哪个页（或哪些页）封装在操作系统的替换策略中，由于内存只包含系统中所有页的子集，因此可以将其视为系统中虚拟内存页的缓存（cache）。因此，在为这个缓存选择替换策略时，我们的目标是让缓存未命中（cache miss）最少，即使得从磁盘获取页的次数最少。最优替换策略时替换内存中在最远将来才会被访问到的页，这很难实现。其它策略有fifo，随机，lru等。由于实现完美的lru算法的开销比较大，可以使用近似lru替代。由于分页到硬盘非常昂贵，因此频繁分页的成本太高。所以，过度分页的最佳解决方案往往很简单：购买更多的内存。（好想笑）