《操作系统导论》阅读笔记（十一）分页机制

阅读笔记主要来自原书第 18 章。该章对分页机制进行了详细的介绍。

0、前言

操作系统有两种方法，来解决大多数空间管理问题。第一种是将空间分割成不同长度的分片，就像虚拟内存管理中的分段。遗憾的是，这个解决方法存在固有的问题。具体来说，将空间切成不同长度的分片以后，空间本身会碎片化，随着时间推移，分配内存会变得比较困难。

因此，值得考虑第二种方法：将空间分割成固定长度的分片。在虚拟内存中，称这种思想为分页。分页不是将一个进程的地址空间分割成几个不同长度的逻辑段（即代码、堆、段），而是分割成固定大小的单元，每个单元称为一页。相应地，把物理内存看成是定长槽块的阵列，叫作页帧（page frame）。每个这样的页帧包含一个虚拟内存页。关键问题是：

如何通过页来实现虚拟内存，从而避免分段的问题？基本技术是什么？如何让这些技术运行良好，并尽可能减少空间和时间开销？

1、一个简单例子

为了让该方法看起来更清晰，用一个简单例子来说明。下图展示了一个只有 64 字节的小地址空间，有 4 个 16 字节的页（虚拟页0、1、2、3）。真实的地址空间肯定大得多，通常 32 位有 4GB 的地址空间，64 位有 256T 的空间（使用其中的 48 位）。

物理内存，如下图所示，也由一组固定大小的槽块组成。在这个例子中，有 8 个页帧（由 128 字节物理内存构成，也是极小的）。从图中可以看出，虚拟地址空间的页放在物理内存的不同位置。图中还显示，操作系统自己用了一些物理内存。

可以看到，与以前的方法相比，分页有许多优点。可能最大的改进就是灵活性：通过完善的分页方法，操作系统能够高效地提供地址空间的抽象，而不用管进程如何使用地址空间。例如，不会假定堆和栈的增长方向，以及它们如何使用。

另一个优点是分页提供的空闲空间管理的简单性。例如，如果操作系统希望将 64 字节的小地址空间放到 8 页的物理地址空间中，它只要找到 4 个空闲页。也许操作系统保存了一个所有空闲页的空闲链表，只需要从这个列表中拿出 4 个空闲页。在这个例子里，操作系统将地址空间的虚拟页 0 放在物理页帧 3，虚拟页 1 放在物理页帧 7，虚拟页 2 放在物理页帧 5，虚拟页 3 放在物理页帧 2。页帧 1、4、6 目前是空闲的。

为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，称为页表（page table）。页表的主要作用是为地址空间的每个虚拟页面保存地址转换，从而知道每个页在物理内存中的位置。

对于上面的简单示例，页表因此具有 4 个条目：虚拟页 0→物理帧 3、虚拟页 1→物理帧 7、虚拟页 2→物理帧 5 和虚拟页 3→物理帧 2。

重要的是要记住，这个页表是每个进程都有一个的数据结构。如果在上面的示例中运行另一个进程，操作系统将不得不为它管理不同的页表，因为它的虚拟页显然映射到不同的物理页面（共享除外）。

现在了解了足够的信息，可以完成一个地址转换的例子。设想拥有这个小地址空间（64 字节）的进程正在访问内存：

movl <virtual address>, %eax

具体来说，注意从地址到寄存器 eax 的显式数据加载（忽略之前肯定会发生的指令获取）。

为了转换该过程生成的虚拟地址，我们必须首先将它分成两个组件：虚拟页面号（virtual page number，VPN）和页内的偏移量（offset）。对于这个例子，因为进程的虚拟地址空间是 64 字节，所以虚拟地址总共需要 6 位（2^6 = 64）。因此，虚拟地址可以表示如下：

在上图中，Va5 是虚拟地址的最高位，Va0 是最低位。因为知道页的大小（16 字节），所以可以进一步划分虚拟地址，如下所示：

页面大小为 16 字节，位于 64 字节的地址空间。因此我们需要能够选择 4 个页，地址的前 2 位就是做这件事的。因此，我们有一个 2 位的虚拟页号。其余的位告诉我们，感兴趣该页的哪个字节，在这个例子中是 4 位，称之为偏移量。

当进程生成虚拟地址时，操作系统和硬件必须协作，将它转换为有意义的物理地址。例如，假设上面的加载是虚拟地址 21：

movl 21, %eax

将“21”变成二进制形式，是“010101”，因此可以检查这个虚拟地址，看看它是如何分解成虚拟页号和偏移量的：

因此，虚拟地址“21”在虚拟页 1（“01”）的第 5 个（“0101”）字节处。通过虚拟页号，现在可以检索页表，找到虚拟页 1 所在的物理页面。在上面的页表中，物理帧号（物理页号，physical page number，PFN）是 7（二进制 111）。因此，可以通过用 PFN 替换 VPN 来转换此虚拟地址，然后将载入发送给物理内存。

2、页表存在哪里

页表可以变得非常大，比之前讨论过的小段表或基址/界限对要大得多。例如，想象一个典型的 32 位地址空间，页的大小为 4KB。虚拟地址分成 20 位的 VPN 和 12 位的偏移量（2^12 = 4KB）。

一个 20 位的 VPN 意味着，操作系统必须为每个进程管理 2^20 个地址转换（大约一百万）。假设每个页表条目（page table entry，PTE）需要 4 个字节，来保存物理地址转换和任何其他有用的东西，每个页表就需要巨大的 4MB 内存！这非常大。现在想象一下有100个进程在运行：这意味着操作系统会需要 400MB 内存。

由于页表如此之大，我们没有在 MMU 中利用任何特殊的片上硬件，来存储当前正在运行的进程的页表，而是将每个进程的页表存储在内存中。稍后会看到，很多操作系统内存本身都可以虚拟化，因此页表可以存储在操作系统的虚拟内存中（甚至可以交换到磁盘上）。现在假设页表存在于操作系统管理的物理内存中。下图展示了操作系统内存中的页表，看到其中的一小组地址转换了吗？（虚拟页 0→物理帧 3、虚拟页 1→物理帧 7、虚拟页 2→物理帧 5 和虚拟页 3→物理帧 2）

3、页表中究竟有什么

现在来谈谈页表的组织。页表就是一种数据结构，用于将虚拟地址（或者实际上，是虚拟页号）映射到物理地址（物理帧号）。因此，任何数据结构都可以采用。最简单的形式称为线性页表，就是一个数组。操作系统通过虚拟页号检索该数组，并在该索引处查找页表项（PTE），以便找到期望的物理帧号（PFN）。现在，假设采用这个简单的线性结构。

至于每个 PTE 的内容，在其中有许多不同的位，值得了解。

有效位（valid bit）通常用于指示特定地址转换是否有效。例如，当一个程序开始运行时，它的代码和堆在其地址空间的一端，栈在另一端。所有未使用的中间空间都将被标记为无效，如果进程尝试访问这种内存，就会陷入操作系统，可能会导致该进程终止。因此，有效位对于支持稀疏地址空间至关重要。通过简单地将地址空间中所有未使用的页面标记为无效，我们不再需要为这些页面分配物理帧，从而节省大量内存。
保护位（protection bit），表明页是否可以读取、写入或执行。同样，以这些位不允许的方式访问页，会陷入操作系统。
存在位（present bit）表示该页是在物理存储器还是在磁盘上（即它已被换出）。当研究如何将部分地址空间交换到磁盘，从而支持大于物理内存的地址空间时，我们将进一步理解这一机制。交换允许操作系统将很少使用的页面移到磁盘，从而释放物理内存。
脏位（dirty bit）也很常见，表明页面的内容是否被修改过。
参考位（reference bit，也被称为访问位，accessed bit）有时用于追踪页是否被访问，也用于确定哪些页很受欢迎，因此应该保留在内存中。

下图显示了来自 x86 架构的示例页表项。它包含一个存在位（P），确定是否允许写入该页面的读/写位（R/W） ，确定用户模式进程是否可以访问该页面的用户/超级用户位（U/S），有几位（PWT、PCD、PAT 和 G）确定硬件缓存如何为这些页面工作，一个访问位（A）和一个脏位（D），最后是页帧号（PFN）本身。

4、分页：也很慢

内存中的页表，已经知道它们可能太大了。事实证明，它们也会让速度变慢。以简单的指令为例：

movl 21, %eax

同样，只看对地址 21 的显式引用，而不关心指令获取。在这个例子中，假定硬件执行地址转换。要获取所需数据，系统必须首先将虚拟地址（21）转换为正确的物理地址（117）。因此，在从地址 117获取数据之前，系统必须首先从进程的页表中提取适当的页表项，执行转换，然后从物理内存中加载数据。

为此，硬件必须知道当前正在运行的进程的页表的位置。现在假设一个页表基址寄存器（page-table base register）包含页表的起始位置的物理地址。为了找到想要的 PTE 的位置，硬件将执行以下功能：

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

在上述例子中，VPN_MASK 将被设置为 0x30（十六进制 30，或二进制 110000），它从完整的虚拟地址中挑选出 VPN 位；SHIFT 设置为 4（偏移量的位数），这样就可以将 VPN 位向右移动以形成正确的整数虚拟页码。例如，使用虚拟地址 21（010101），掩码将此值转换为 010000，移位将它变成 000001，或虚拟页 1，正是所期望的值。然后，使用该值作为页表基址寄存器指向的 PTE 数组的索引。

一旦知道了这个物理地址，硬件就可以从内存中获取 PTE，提取 PFN，并将它与来自虚拟地址的偏移量连接起来，形成所需的物理地址。具体来说，你可以想象 PFN 被 SHIFT 左移，然后与偏移量进行逻辑或运算，以形成最终地址。

offset   = VirtualAddress & OFFSET_MASK 
PhysAddr = (PFN << SHIFT) | offset

最后，硬件可以从内存中获取所需的数据并将其放入寄存器 eax。程序现在已成功从内存中加载了一个值！总之，我们现在描述了在每个内存引用上发生的情况的初始协议。基本方法如下所示。

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// Check if process can access the page
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
else
    // Access is OK: form physical address and fetch it
    offset   = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

对于每个内存引用（无论是取指令还是显式加载或存储），分页都需要我们执行一个额外的内存引用，以便首先从页表中获取地址转换。工作量很大！额外的内存引用开销很大，在这种情况下，可能会使进程减慢两倍或更多。

现在你应该可以看到，有两个必须解决的实际问题。如果不仔细设计硬件和软件，页表会导致系统运行速度过慢，并占用太多内存。