inverted_page_table.pdf

虚拟内存是现代操作系统中至关重要的一个特性，它使得程序可以使用超出实际物理内存大小的地址空间。在虚拟内存系统中，页表是用来管理虚拟地址到物理地址映射的数据结构。本篇文章将深入探讨反置页表（Inverted Page Table）的概念、动机以及多级分页的原理。 我们来理解一下单级页表的工作方式。在单级页表中，每个进程的虚拟页面都有一个对应的页表条目。例如，如果有一个64位的虚拟地址空间，每页大小为4KB，那么理论上存在2^52个可寻址的字节。由于每个页面包含2^12字节，因此需要2^52 / 2^12 = 2^40个页表条目。每个条目通常包含访问控制位和物理页号。如果物理内存限制为512MB（2^29字节），则每个条目需要大约2^29 / 2^12 = 2^17个物理页面，即17位来表示物理页号。加上访问控制位，每个页表条目大约为4字节。因此，整个页表需要2^40 * 4字节 = 2^42字节，这相当于16PB的内存，对于每个进程来说，这是一个巨大的开销。 为了缓解这种内存压力，引入了多级分页机制。在多级页表中，较高层次的表包含对下级页表的指针，而不是直接的物理地址。以Pentium III为例，它使用了页目录表（Page Directory Table）作为高层表，而页表（Page Tables）作为低层表。这样，只有活动页面对应的页表才会被加载到内存中，大大减少了所需内存。 以64位地址空间、4KB页面大小和512MB物理内存为例，我们来计算需要多少级分页才能确保任何页表只占用一个4KB的页面。如果每个页表条目为4字节，那么4KB的页面可以容纳1024个条目，这就需要10位地址空间。由于总共需要52位地址空间，我们需要将这52位分段，每段最多10位。天花板函数（ceiling）表示向上取整，所以需要6级分页。然而，6级分页会导致6次内存访问，这会降低性能。 反置页表的动机在于解决上述问题。在反置页表中，不再为每个虚拟页创建一个条目，而是为每个物理页创建一个条目，存储指向所有映射到该物理页的虚拟页的指针。这样，即使物理内存很大，页表所需的内存也会显著减少。例如，在512MB物理内存的情况下，只需要2^17个物理页面的页表条目，每个条目存储映射到该物理页的虚拟页号和其他控制信息。这种方法有效地减少了页表所需的内存空间，提高了效率，尤其是在物理内存资源有限的情况下。 虚拟内存中的页表管理和分页策略是优化系统性能和资源利用率的关键。反置页表和多级分页是两个重要的技术手段，它们允许操作系统高效地处理大量的虚拟地址空间，同时最小化物理内存的使用。在实际操作系统的实现中，还会结合其他优化技术，如快表（TLB）来进一步提高地址转换的速度，以实现更高效的内存管理。