分页

分段引入了外部碎片，并且仍然不够细粒度。

分页 (paging) 将地址空间划分成固定大小的内存块，称为页 (page)。物理空间也按照同样的大小分块，被称为页框 (page frame)。OS 需要做的就是将页嵌入页框。

分页有几个显著的优势：

• 与段不同，页的大小固定，这完全避免了外部碎片。
• 极大简化了空闲空间管理，任意线程的任何虚拟页都可以映射到任何空闲的物理页框。

页表

每个线程都有一个页表 (page table)，记录该线程虚拟页与物理页框的映射。

页表的索引是行号即虚拟页号 (virtual page number, VPN)，一个页表项 (page table entry, PTE) 将记录对应虚拟页的：

• 物理页框号 (page frame number, PFN)
• 有效位 (valid bit)：该页是否有效，为 0 表示空白，不可访问
• 存在位 (present bit)：该页是否在物理空间中（若页「换出」至磁盘上，为 0）
• 脏位 (dirty bit)：该页是否被修改
• 访问位 (reference bit)：该页近期是否被线程访问过。与换页策略 (page replacement policy) 如 LRU 密切相关。
• 保护位：该页的访问权限

地址翻译

分段机制中的地址翻译就已经能见出端倪：分页甚至更简单。分段中的 max size 此时是分页中的 actual size。

步骤：

• 从虚拟地址高位取出 VPN（位数由页数决定），剩余的为 offset
• 查页表，得到 VPN 对应的 PFN
• 连接 PFN 与 offset 即可得到物理地址

1
2
3
4
5
6
7
8
9
10
11
12

VPN      = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr  = PageTableBaseRegister + (VPN * sizeof(PTE))
PTE = AccessMemory(PTEAddr)

if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT);
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT);
else
    offset   = VirtualAddress & OFFSET_MASK
    PhysAddr = (PFN << SHIFT) | offset
    Register = AccessMemory(PhysAddr)

朴素分页的资源开销

以上描述的朴素分页的时空开销都不理想。

页表的空间占用很夸张，因此储存在内存而非 MMU 中。MMU 维护页表基址寄存器 (page-table base register, PTBR) 来定位对应线程页表的位置（因此上下文切换时 OS 也需要对其更新）。

每次地址翻译，需要访问一次物理内存中的页表，读取 PTE，最后再从计算得出的物理地址中读取数据：每次内存引用需要访问两次物理内存。

接下来的两节探讨如何改善分页的时空开销。