倒排页表(Inverted Page Table)

倒排页表是虚拟内存管理中的一种页表组织方式。与传统页表按虚拟页号索引不同,它以物理页框号为索引,全系统仅有一张表,表项数量等于物理页框数,记录每个物理页当前被哪个进程的哪个虚拟页所使用。

概述

传统的正向页表为每个进程维护独立映射,虚拟地址空间越大页表越大。倒排页表反其道而行:因为物理内存大小是固定且有限的,所以用物理页框做索引,表的规模只与内存容量相关,与进程数量和虚拟空间大小无关。这在拥有巨大地址空间的系统中显著节省了页表内存。查找时需要根据进程标识和虚拟页号在表中反查对应的物理页框。

核心原理

• 物理索引:表项按物理页框号排列,每个物理页对应唯一条目。
• 条目内容:记录使用该页框的进程标识与虚拟页号。
• 哈希加速:由于按虚拟地址查找需要遍历,系统通常引入哈希表把虚拟页号快速映射到表项。
• 全局共享:整个系统只需一张表,而非每进程一张。

应用场景

倒排页表历史上被用于 IBM 的 PowerPC、RS/6000 以及部分安腾等地址空间很大的架构中,以控制页表内存开销。它特别适合物理内存相对有限而虚拟地址空间极大的场景。不过由于查找复杂和共享内存处理不便,通用桌面架构仍多采用多级正向页表,倒排页表更多出现在特定服务器与处理器设计中。

常见问题

问:倒排页表如何加快查找?答:直接扫描全表代价高昂,因此通常配合哈希函数,把进程标识和虚拟页号映射到候选表项,再解决哈希冲突,从而把查找降到接近常数时间。

问:它为什么不普及?答:倒排页表节省了内存,但处理共享内存(多个虚拟页映射到同一物理页)较为困难,查找逻辑也更复杂,权衡之下多数通用系统仍偏好多级页表。