操作系统：内存虚拟化

目标

虚拟内存具有以下目标：

• 透明：即程序会被欺骗得很好
• 效率：在虚拟化时，为了提高效率，需要硬件支持
• 保护：确保各个进程的隔离

地址转换

先从简单的机制入手（后面会更复杂）

动态重定位

基于硬件，最简单的重定位。每个cpu需要加入两个硬件寄存器：base和bound。当程序执行时，操作系统会决定其基址，设置base寄存器，然后该进程的所有进程引用都会被处理为物理地址：

paddr = vaddr + base

bound寄存器则提供了保护机制，当进程试图越界，会触发异常处理。

十分明显，这种方法效率低下，进程可能浪费大量内存。

分段机制

为了解决上面的问题，我们引入分段的机制。每个段都记录基址，以及界限。则处理地址的过程可以变为：

paddr = bias + base

偏移量可以通过虚拟地址计算出来。可以用虚拟地址的前几位来表示目标段：

[ s1 | s0 | v11 | ... | v0 ]

注意到栈的机制，我们不可以直接用虚拟地址来当偏移量，可以再增加一位用来记录是否反向增长。

该机制还可以提高保护，比如再引进一位用来记录段的权限。

物理内存的一个段可以映射到多个虚拟地址空间。

但该方法无法避免内存碎片，只能减少。需要更好的机制。

空闲空间管理

先考虑外部碎片，即由于空闲空间大小不一，导致总空闲空间足够，但因为不连续而导致无法分配。

主要讲了一些合并与寻找空闲块的策略。

基本策略

• 最优匹配：找候选块最小的可满足的，减少碎片大小
• 最差匹配：找候选最大的，留大块碎片（通常糟糕）
• 首次匹配：找第一个符合的，速度快
• 下次匹配：从上次分配的位置接着往后找

分离空闲列表

（不是很理解）

伙伴系统

将空闲空间一直二分，直到满足。这样释放的时候，检查伙伴的块，可以实现递归合并。且由于这种机制，一对伙伴之间的地址关系很显然：他们只有一位不同。

分页

前面分段的方法，将空间切分成长度不同的部分，造成碎片。我们可以试试将物理内存定长分割，每一块叫做页。这种方法抽象程度更高，通过虚拟页与物理页映射，不用考虑进程怎么使用地址。

通过页表，实现虚拟页号（VPN）到物理页号（PFN）的转换。页表记录vpn与pfn的映射关系。比如：
[vpn|offset] -> [pfn|offset]实际上就完成了地址的转换。

页表

在哪？我们可以建立一个页表基址寄存器(PTBR)来记录。现在我们可以用伪代码来模拟这个过程：

// extract vpn
vpn = (vaddr & vpn_mask) >> shift

// get pte
pte_addr = ptbr + vpn * sizeof(pte)
pte = M(pte_addr)

// check if can process page
if(pte.valid == false)
	error(segmentation fault)
else if(pte.ifprotect == true)
	error(protection fault)
else
	offset = vpn & offset_mask
	paddr = (pte.pfn << shift) | offset
	r = M(paddr)

TLB

由学过的储存器层次结构，caching是一种能加速内存访问的技术，应用于页表，就是TLB。TLB将前面的PTE表项拿来作为表项。

处理未命中时，系统抛出异常，加载更新TLB，再回到指令处重新执行。注意并非下一条指令，与之前讲的中断不一样。同时要注意无限递归，即异常处理程序本身不在TLB中。TLB为全相联的结构，所以可以直接并行查找，速度快。

因为不同的进程映射关系不同，理论上上下文切换时，应该清空TLB，但这样开销太大，可以考虑为TLB加上地址空间标识符（ASID）

一些替换策略：

• LRU
• 随机：避免上面方法的抖动现象

更小的页表

从上面知道，页表的项数为：2的 分配给页表的位数 次方，显然，页表本身为一笔不小的开销。我们思考以下方法：

更大的页：通过减少vpn的位数从而减少页表，但内部碎片过大

分段分页混合：我们不为整个进程提供页表，只对三个逻辑分段提供。之前每段都有一对基址界限寄存器，现在让基址寄存器记录该段的页表上的位置，界限记录有多少有效页。

多级页表：本质就是将之前的页表分成页，用高一级的页表记录。好处是，当有一个页的页表项没有记录东西，我们可以在高一级的页表上用有效为0的表项来表示，从而避免给空页表分配空间。如下：

[   vpn     |   offset  ]
[ pti | pfn |   offset  ]
[pd1|pd0|pfn|   offset  ]
...

超越物理内存

机制

我们之前都是假设虚拟内存的空间地址小于物理内存的，为了支持运行更多更大的进程需要在内存层级（memory hierarchy）上加层。

在这里，我们考虑在物理内存下加上硬盘，并在硬盘上开辟交换空间。

为了支持交换空间，我们需要添加更多机制。比如在页表项添加存在位，表示该页是否在物理内存中。如果不在，会触发页错误。触发之后，会通过硬盘的I/O来更新页表。注意在I/O运行时，进程阻塞，此时可以执行其他进程，就是cpu虚拟化里提到的[[CPU虚拟化#overlap]]

同时，操作系统并非等到内存满才会交换页，实际上它可以主动预留一小部分内存。设置高水位线（HW）和低水位线（LW），当操作系统发现少于LW个页可用，会执行后台释放内存的进程直到有HW个页可用。

还有，通过同时执行多个交换过程，可以提高性能。

策略

为了效率，应该思考在页替换时的选择策略。

最优替换策略：本质上需要可以预知未来。是一种无法实现，但可以作为参照（用于评估另一种算法好坏）的方法。具体是替换最远将来会访问的页（听着就很科幻）。

FIFO：最先进入缓存的页out，缺点是其无法确定页的重要性。

随机：看运气，也是不够智能

LRU：可以通过历史记录，在执行替换时，踢出最少最近使用的页。

近似LRU：LRU因为需要扫描所有页来实现替换，开销太大。以下是一种近似方法。给硬件增加使用位（use bit），每当页被引用时，使用位设置为1。我们采取时钟算法，当需要替换时，时钟指针检查当前指向的页的使用位，如果为1，则将其设置为0，并指向下一页，直到遇到使用位为0的页。

脏页。因为在内存中，一个没有修改过的页显然写回成本要小于修改过的（因为可以直接释放，不用进行I/O）。所以可以考虑加一个脏位（dirty bit）。

还有一些策略：比如预取，聚集写入等。

VAX/VMS

主要研究该操作系统的一些有意思的虚拟内存管理。

地址空间

内核虚拟空间是每个用户地址空间的一部分。在上下文切换时，该段的基址界限寄存器不会变，本质是将相同的地址空间映射到各个用户。

页替换策略

分段的FIFO的策略：每个进程都有一个可以保留在内存中的最大页数（resident set size），当超过RSS时，先入被驱逐。VMS还引入了二次机会列表（second- chance list），分别为一个全局干净列表和脏列表。页在被踢出之前放在这里。

页聚集：将大批量的脏页分组到一起，并一举写入磁盘。

惰性优化

按需置零：当用户添加页到堆，（比如malloc），并不直接分配一个置零的页，而是只在页表里放入一个不可访问的条目。当用户需要读取或者写入该页，才会寻找物理页，将其置0并映射到地址空间。而如果进程不访问这页，就直接省去了这个开销。

写时复制：若操作系统需要将一个页面从一个地址空间复制到另一个（比如fork），不会实际复制，而是将其映射到目标地址空间并标记为只读。当需要写的时候，才会分配新页填充数据并重新映射。