反向页表

倒置页表（Inverted Page Table）是由操作系统为所有进程维护的全局页表。在倒置页表中，条目数量等于主内存中的页框数量。它可以用来克服页表的缺点。无论页面是否驻留在主内存中，总会为其保留一个空间。然而，如果页面不存在，这仅仅是内存的浪费。

什么是倒置页表？

倒置页表（IPT）是一种用于启用虚拟内存的操作系统中的数据结构，用于连接物理内存页和虚拟内存页。与传统的页表（每个进程一个数据结构）不同，IPT是一个系统范围的数据结构，每个物理内存页都有一个条目。使用倒置页表结构，即每个主内存页框有一个页表条目，是一种替代方法。因此，使用一个页表来表示所有进程的分页信息，并且倒置页表中的页表条目数量减少到物理内存中的页框数量。

倒置页表将所有进程的分页信息保存在一起，只需要恒定的内存量，从而消除了为每个进程维护单独页表的开销。由于索引是使用页框号而不是逻辑页号进行的，因此这种方法称为倒置分页。

倒置页表的必要性

与标准分页类似，大多数操作系统为每个进程使用一个单独的页表。在典型分页场景中，100 个进程对应于主内存中的 100 个页表。有时，进程的页表大小会随着其进程大小显着增加。倒置页表消除了为每个任务维护单独页表的开销。有一个全局页表供所有活动使用。

例如，如果页面大小为 512 字节，进程大小为 2 GB，页表条目大小为 4 字节，则进程的页面数量为 2 GB / 512 B = 222，页表大小为 222 * 22 = 224 字节。

当大型操作系统中多个进程并发运行时，页表仅占用了大量内存。为了有效利用 RAM 并保持多道程序设计和有效的 CPU 利用率平衡，已进行了大量尝试。

倒置页表组件

每个页表条目都包含以下字段。

• 页号：指示逻辑地址的页号范围。
• 进程 ID：每个正在运行进程的地址空间详细信息都包含在倒置页表中。由于两个不同的进程可能共享一组相似的虚拟地址，因此必须在倒置页表中存储每个进程的进程 ID，以唯一标识其地址空间。PID 和页号结合使用可实现此目的。因此，此进程 ID 作为地址空间标识符，并确保特定进程的虚拟页正确地转换为相应的物理页框。
• 控制位：这些位存储了其他与分页相关的数据。它们包括引用位、保护位、有效位、脏位和锁定信息位。
• 链式指针：主内存的一部分有时可能由两个或多个进程共享。当两个或多个逻辑页映射到同一个页表条目时，这些逻辑页的信息通过链式指针映射到根页表。

倒置页表如何工作

以下说明了倒置页表的工作原理。

CPU 生成的虚拟地址中包含这些字段，并且每个页表条目都包含分页相关机制所需的其他相关数据。内存管理单元（MMU）在发生内存引用时匹配此虚拟地址，搜索倒置页表，并检索相应的页框号。如果 i 号条目匹配成功，则将进程的物理地址作为实际地址传输；否则，将产生分段错误。

注意：物理地址空间（PAS）中的页框数量等于倒置页表中的条目数量。

示例：PowerPC、UltraSPARC 和 IA-64 架构只是使用倒置页表及其变体的系统中的一小部分。Mach 操作系统也使用此方法在 RT-PC 上实现。

通过反转页表，我们可以节省这种浪费。我们只能保存驻留在主内存中的页面的详细信息。页框是索引，存储在块内的信息将是进程 ID 和页号。

倒置页表的好处

以下是倒置页表的主要优点

• 内存空间减少：一般来说，在物理内存空间限制内，倒置页表需要更少的内存来存储页表。物理内存中的页框数量可以是最大条目数。
• 查询时间较长：倒置页表是根据页框号排列的，但由于需要对虚拟地址进行内存查询，因此找到正确的条目通常需要更长的时间。通常，哈希数据结构用于构建倒置页表，以加快查找过程。
• 共享内存实现困难：由于倒置页表每个页框只保留一个条目，因此在页表中实现共享内存很困难。使用链式方法，多个虚拟地址可以映射到以页框号顺序给出的条目。
• 更简单、更优：它比基本分页过程更简单、更优。
• 简化页面交换：当进程需要从内存中换出时，IPT 可用于快速识别与该进程关联的所有物理页面。这可以减少内存管理的总体开销，并使页面交换更容易。
• 更好的缓存性能：由于其尺寸较小，IPT 比页表更容易存储在 CPU 缓存中，这可以提高内存访问操作的速度。

每个 IPT 条目都包含映射到该物理页面的虚拟地址以及其他详细信息，例如页面的访问权限、拥有虚拟地址的进程的进程 ID 以及其他页面属性。操作系统使用这些数据来管理物理内存页的分配和释放，并确保程序只能以受控和安全的方式使用内存。然而，使用 IPT 存在一些潜在的缺点，包括搜索成本更高以及进程竞争物理内存页的可能性。是使用 IPT 还是页表，取决于所使用的操作系统和硬件平台的具体需求和限制，这与任何内存管理策略一样。

实际应用

• PowerPC 架构：PowerPC CPU 使用主内存中的哈希表以及一个小的 TLB 来存储最近的翻译，以在硬件中实现 IPT。
• UltraSPARC 处理器：Sun 的 UltraSPARC 使用 (PID VPN) 的硬件哈希函数索引其 IPT，并通过主内存中的链表来处理冲突。
• IA-64 架构（Itanium）：Intel 的 IA-64 设计通过使用带有大型直接映射哈希表和每个进程标签位的倒置页表，在非常大的地址空间中权衡了表大小以实现快速查找。
• IBM 的 System/38 和 801：早期 IBM 系统，如 System/38（1981 年）和 IBM 801 小型机，是最早采用 IPT 的系统之一，它们在通用采用之前很久就展示了固定大小的页框索引表。
• RT-PC Mach 内核：在 RT-PC 平台上，Mach 微内核使用 IPT 的有界大小来简化内核级内存簿记，并实现 IPT 的变体，以在进程之间保留一个单一的映射表。
• 当代趋势：尽管这些架构展示了该概念，但大多数现代操作系统（OS）（Windows、Linux）更喜欢分层和多级页表，并通过大型 TLB 进行增强，因为它们在没有全局哈希冲突的情况下提供了更好的局部性，并且软件支持更简单。
• 带哈希辅助的查找：为了实现平均 O(1) 的查找时间并弥补纯页框索引设计的原始搜索开销，IPT 的实际实现总是将表与硬件或软件哈希配对。

总结

最终，我们现在了解了倒置页表概念在操作系统中的重要性。对于具有大地址空间的选择，系统是解决内存页监控和管理问题的最佳方案。通过根据其真实内存位置而非虚拟地址索引页面，它降低了内存使用率和感知时间。理解倒置页表对于系统开发人员至关重要，因为它在内存分配和效率方面发挥着重要作用，这支持了操作系统的整体响应能力和稳定性。

常见问题

Q1. 按需分页是如何工作的？

与交换分页系统类似，按需分页系统将大部分进程存储在主内存中，而主内存通常位于硬盘驱动器上。因此，按需分页是一个仅在需要时才移动页面的过程，以解决上述问题。这也称为懒惰交换程序，因为它只在需要时才将页面交换到内存中。

Q2. 页表的结构是怎样的？

页表的结构基本上决定了它可以组合的各种方式。顾名思义，分页是一种内存管理技术，它将一个大的操作划分为页面并将其以页面的形式存储在物理内存中，作为页框。页面和页框的大小相同。CPU 生成的页面的逻辑地址由操作系统使用页表转换为其在主内存中的实际位置。

Q3. 在倒置页表中，有多少个条目？

物理地址空间除以页面大小等于倒置页表中的条目数。

Q4. 倒置页表与常规页表有什么区别？

传统页表将虚拟页面映射到物理页框，并为每个进程维护一个单独的表。而 IPT 有一个全局表，将进程 ID 与虚拟页面和物理页框关联起来。虽然这种设计使用的内存更少，但可能会使查找过程更加困难。

Q5. 为什么倒置页表使用哈希函数？

为了加快搜索速度，IPT 使用哈希函数。通过哈希化虚拟地址（有时也包括进程 ID），系统可以快速找到 IPT 中的匹配条目。然而，可能会发生哈希冲突，通常通过链式方法解决。