页

有时有人说，操作系统在解决大多数空间管理问题时会采用两种方法之一。第一种方法是将事物切成可变大小的块，正如我们在虚拟内存中的分段中看到的那样。不幸的是，这个解决方案有其固有的困难。特别是，当将空间划分为不同大小的块时，空间本身可能会变得碎片化，因此随着时间的推移，分配变得更具挑战性。

因此，可能值得考虑第二种方法：将空间切成固定大小的块。在虚拟内存中，我们将这种想法称为分页，它可以追溯到一个早期且重要的系统，Atlas。我们不是将进程的地址空间划分为一定数量的可变大小的逻辑段（例如代码、堆、栈），而是将其划分为固定大小的单元，每个单元称为页面。相应地，我们将物理内存视为一组固定大小的槽（称为页框）；每个框都可以包含一个虚拟内存页；每个进程都需要页表来将虚拟地址转换为物理地址。。我们的挑战：

关键：如何使用页面虚拟化内存 ?

如何使用页面虚拟化内存，从而避免分段问题？有哪些基本技术？我们如何以最小的空间和时间开销使这些技术发挥良好作用？

1 示例：一个简单的分页

为了更清楚地说明这种方法，让我们来看一个简单的例子。下图展示了一个很小的地址空间，总大小只有 64 字节，有四个 16 字节的页面（虚拟页面 0、1、2 和 3）。

当然，真实的地址空间要大得多，通常为 32 位，因此有 4GB 的地址空间，甚至 64 位。

如下图所示，物理内存也由许多固定大小的槽组成，在本例中是 8 个页框（对于 128 字节的物理内存来说，也小得离谱）。虚拟地址空间的页面被放置在整个物理内存的不同位置；该图还显示操作系统自身使用一些物理内存。

正如我们将看到的，分页比我们以前的方法有许多优点。最重要的改进可能是灵活性：通过完全开发的分页方法，系统将能够有效地支持地址空间的抽象，无论进程如何使用地址空间；例如，我们不会对堆和栈的增长方向以及它们的使用方式做出假设。

另一个优点是分页提供的可用空间管理的简单性。例如，当操作系统希望将我们微小的 64 字节地址空间放入我们的八页物理内存中时，它只会找到四个空闲页；也许操作系统为此保留了所有空闲页面的空闲列表，并且只从该列表中获取前四个空闲页面。在示例中，操作系统已将地址空间 (AS) 的虚拟页 0 放置在物理页 3 中，将 AS 的虚拟页 1 放置在物理页7 中，将页 2 放置在物理页 5 中，将页 3 放置在物理页 2 中。 页框 1 、4 和 6 目前空闲。

为了记录地址空间的每个虚拟页在物理内存中的位置，操作系统通常会为每个进程保存一个名为页表的数据结构。页表的主要作用是存储地址空间中每个虚拟页的地址转换，从而让我们知道每个页位于物理内存中的位置。对于我们的简单示例，页表将具有以下四个条目：（虚拟页 0 → 物理页3）、（VP 1 → PF 7）、（VP 2 → PF 5）和（VP 3 → PF 2）。

重要的是要记住，这个页表是一个每个进程的数据结构（我们讨论的大多数页表结构都是每个进程的结构；我们将提到一个例外，即反向页表）。如果在上面的示例中运行另一个进程，则操作系统必须为其管理不同的页表，因为它的虚拟页面显然映射到不同的物理页面（除非有任何共享正在进行）。

现在，我们知道足够多以执行地址转换示例。让我们想象一下具有微小地址空间（64字节）的进程正在执行内存访问：

1

movl <virtual address>, %eax

具体来说，让我们注意将数据从地址<virtual address>显式加载到寄存器 eax 中（从而忽略之前必须发生的指令获取）。

为了转换进程生成的虚拟地址，我们必须首先将其分为两个部分：虚拟页号（Vitrual page number,VPN）和页面内的偏移量。对于此示例，由于进程的虚拟地址空间为 64 字节，因此我们的虚拟地址总共需要 6 位 ($2^6 = 64$)。因此，我们的虚拟地址可以概念化如下：

其中，Va5是虚拟地址的最高位，Va0是最低位。因为我们知道页面大小（16字节），则前两位代表虚拟页号，后四位代表页面偏移量。在 64 字节地址空间中，页面大小为 16 字节；因此我们需要能够选择 4 个页面，地址的前 2 位就可以做到这一点。因此，我们有一个 2 位虚拟页码 (VPN)。剩余的位则表示页面偏移量。

当进程生成虚拟地址时，操作系统和硬件必须结合起来将其转换为有意义的物理地址。例如，假设上述加载到虚拟地址 21：

1

movl 21, %eax

将“21”转换为二进制形式，我们得到“010101”，因此我们可以检查这个虚拟地址并查看它如何分解为虚拟页号（VPN）和偏移量：

因此，虚拟地址“21”位于虚拟页“01”（或1）的第5（“0101”）字节。有了虚拟页号，我们现在可以索引页表并找到虚拟页 1 所在的物理页。在上面的页表中，物理页号 (Physical page number, PPN)（有时也称为物理帧号或 PFN）为 7（二进制 111）。因此，我们可以通过用 PPN 替换 VPN 来转换这个虚拟地址，然后向物理内存加载数据，如下图所示。

请注意，偏移量保持不变（即，它没有被转换），因为偏移量只是告诉我们我们想要页面中的哪个字节。我们的最终物理地址是 1110101（十进制为 117），这正是我们希望加载获取数据的位置。

2 页表存储在哪？

页表可以变得非常大，比我们之前讨论的小分段表或基址/边界对大得多。例如，想象一个典型的 32 位地址空间，具有 4KB 页面。该虚拟地址分为 20 位 VPN 和 12 位偏移量（回想一下，1KB 页面大小需要 10 位，只需再添加两位即可达到 4KB）。

20 位 VPN 意味着操作系统必须为每个进程管理 $2^{20}$ 个转换（大约一百万个）；假设每个页表项 (page table entry, PTE) 需要 4 个字节来保存物理转换以及任何其他有用的内容，那么每个页表需要 4MB 的巨大内存！那是相当大的。现在假设有 100 个进程正在运行：这意味着操作系统需要 400MB 内存来用于所有这些地址转换！即使在机器拥有千兆字节内存的现代，将大量内存用于地址转换似乎也有点疯狂，不是吗？我们甚至没有考虑对于 64 位地址空间来说这样的页表有多大；那太可怕了，也许会把你完全吓跑。

由于页表太大，我们没有在MMU中保留任何特殊的片上硬件来存储当前运行进程的页表。相反，我们将每个进程的页表存储在内存中的某个位置。现在我们假设页表位于操作系统管理的物理内存中，下图是操作系统内存中页表的图片。

3 页表中到底有什么？

让我们来谈谈页表的组织结构。页表只是一种数据结构，用于将虚拟地址（或实际上是虚拟页码）映射到物理地址（物理页号）。因此，任何数据结构都可以使用。最简单的形式称为线性页表，它只是一个数组。操作系统根据虚拟页码（VPN）对数组进行索引，并查找该索引下的页表项（PTE），以找到所需的物理页号（PFN）。目前，我们将假设这种简单的线性结构；在后面的章节中，我们将使用更高级的数据结构来帮助解决分页中的一些问题。

至于每个 PTE 的内容，我们有许多不同的bit位值得在一定程度上了解。有效位通常用于指示特定转换是否有效。例如，当程序开始运行时，其地址空间的一端是代码和堆，另一端是栈。中间所有未使用的空间都会被标记为无效，如果进程试图访问这些内存，就会向操作系统发出中断，操作系统很可能会终止进程。因此，有效位对于支持稀疏地址空间至关重要；只需将地址空间中所有未使用的页面标记为无效，我们就无需为这些页面分配物理页号，从而节省了大量内存。

我们还可以使用保护位来表明是否可以读取、写入或执行页面。同样，如果以这些位不允许的方式访问页面，就会向操作系统发出中断。

还有一些其他的位也很重要，但我们现在就不多说了。存在位表示该页面是在物理内存中还是在磁盘上（即已被换出）。当我们研究如何将部分地址空间交换到磁盘以支持比物理内存更大的地址空间时，我们将进一步了解这一机制；交换允许操作系统通过将很少使用的页面移动到磁盘来释放物理内存。**脏位（dirty bit）**也很常见，表示页面进入内存后是否被修改过。

参考位（又称访问位）有时用于跟踪页面是否被访问过，它有助于确定哪些页面受欢迎，因此应保留在内存中；在页面替换过程中，这种知识至关重要。

下图显示了 x86 架构中的一个页表条目示例。它包含一个存在位 (P)；一个读/写位 (R/W)，用于确定是否允许写入该页面；一个用户/监管者位 (U/S)，用于确定用户模式进程是否可以访问该页面；几个位（PWT、PCD、PAT 和 G），用于确定这些页面的硬件缓存工作方式；一个已访问位 (A) 和一个脏位 (D)；最后是物理页号（PFN）本身。

4 分页：也太慢

对于内存中的页表，我们已经知道它们可能过大。事实证明，它们也会拖慢运行速度。举个简单的例子：

1

movl 21, %eax

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

为此，硬件必须知道当前运行进程的页表在哪里。现在我们假设单个页表基址寄存器包含页表起始位置的物理地址。为了找到所需 PTE 的位置，硬件将执行以下功能：

1
2

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

在我们的示例中，VPN_MASK 将设置为 0x30（十六进制 30，或二进制 110000），它从完整虚拟地址中挑选出 VPN 位； SHIFT 设置为 4（偏移量中的位数），以便我们将 VPN 位向下移动以形成正确的整数虚拟页号。例如，对于虚拟地址21（010101），掩码将该值变成010000；根据需要，移位会将其变为 01 或虚拟页 1。然后，我们使用该值作为页表基址寄存器指向的 PTE 数组的索引。

一旦知道这个物理地址，硬件就可以从内存中获取 PTE，提取 PFN，并将其与虚拟地址的偏移量连接起来，形成所需的物理地址。具体来说，可以认为 PFN 通过 SHIFT 左移，然后与偏移量按位或运算形成最终地址，如下所示：

1
2

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

最后，硬件可以从内存中取出所需的数据并将其放入寄存器eax中。程序现在已成功从内存加载一个值！

总而言之，我们现在描述每个内存引用上发生的情况的初始协议。下面这段代码显示了基本方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

# 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)

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

现在您有望看到我们必须解决两个真正的问题。如果没有仔细设计硬件和软件，页表会导致系统运行速度过慢，并且占用过多的内存。虽然这似乎是满足我们内存虚拟化需求的一个很好的解决方案，但必须首先克服这两个关键问题。

5 内存跟踪

在结束之前，我们现在通过一个简单的内存访问示例来演示使用分页时发生的所有结果内存访问。我们感兴趣的代码片段（在 C 语言中，在名为 array.c 的文件中）如下：

1
2
3
4

int array[1000];
...
for (i = 0; i < 1000; i++)
	array[i] = 0;

我们编译 array.c 并使用以下命令运行它：

1
2

gcc -o array array.c -Wall -O
./array

当然，为了真正理解内存访问此代码片段（它只是初始化一个数组）会产生什么，我们必须知道（或假设）更多的事情。首先，我们必须反汇编生成的二进制文件（在 Linux 上使用 objdump，在 Mac 上使用 otool）以查看使用哪些汇编指令来初始化循环中的数组。这是生成的汇编代码：

1
2
3
4

0x1024 movl $0x0,(%edi,%eax,4) #Power of CISC! edi+eax*4
0x1028 incl %eax #Increase counter
0x102c cmpl $0x03e8,%eax #Check if last element
0x1030 jne 0x1024 #Implicit (eflags) Zero bit access

如果您了解一点 x86，该代码实际上很容易理解。第一条指令将值零（显示为 $0x0）移动到数组位置的虚拟内存地址中；该地址是通过获取 %edi 的内容并添加 %eax 乘以四来计算的。因此，%edi 保存数组的基地址，而 %eax 保存数组索引 (i)；我们乘以四，因为该数组是整数数组，每个整数大小为四个字节。

第二条指令递增 %eax 中保存的数组索引，第三条指令将该寄存器的内容与十六进制值 0x03e8 或十进制 1000 进行比较。如果比较显示两个值还不相等（这就是 jne 指令测试的结果），第四条指令跳回循环顶部。

为了了解该指令序列访问哪些内存（在虚拟和物理级别），我们必须假设代码片段和数组在虚拟内存中的位置，以及页表的内容和位置。对于此示例，我们假设虚拟地址空间大小为 64KB（小得不切实际）。我们还假设页面大小为 1KB。

我们现在需要知道的是页表的内容及其在物理内存中的位置。假设我们有一个线性（基于数组）页表，并且它位于物理地址 1KB (1024)。

至于其内容，我们只需要担心在本示例中映射了几个虚拟页面。首先，代码所在的虚拟页面。由于页面大小为 1KB，因此虚拟地址 1024 驻留在虚拟地址空间的第二页上（VPN=1，因为 VPN=0 是第一页）。我们假设该虚拟页面映射到物理帧 4 (VPN 1 → PFN 4)。

接下来是数组本身。它的大小是 4000 字节（1000 个整数），我们假设它驻留在虚拟地址 40000 到 44000（不包括最后一个字节）。此十进制范围的虚拟页面为 VPN=39 … VPN=42。因此，我们需要这些页面的映射。我们假设以下虚拟到物理映射为示例：(VPN 39 → PFN 7)、(VPN 40 → PFN 8)、(VPN 41 → PFN 9)、(VPN 42 → PFN 10)。

我们现在准备跟踪程序的内存引用。当它运行时，每个指令获取都会生成两个内存引用：一个到页表以查找指令所在的物理页，另一个到指令本身以将其获取到 CPU 进行处理。此外，还有一个以 mov 指令形式出现的显式内存引用；这首先增加了另一个页表访问（将数组虚拟地址转换为正确的物理地址），然后才是数组访问本身。

下图描述了前五个循环迭代的整个过程。最下面的图以黑色显示 y 轴上的指令内存引用（左边是虚拟地址，右边是实际物理地址）；中间的图以深灰色显示数组访问（同样是左边是虚拟地址，右边是物理地址）；最后，最上面的图以浅灰色显示页表内存访问（只是物理访问，因为本例中的页表位于物理内存中）。整个跟踪的 x 轴显示了循环前五次迭代的内存访问；每个循环有 10 次内存访问，其中包括四次指令取回、一次内存显式更新和五次页表访问，以转换这四次取回和一次显式更新。