分頁表
分页表（page table）是一种数据结构，它用于计算机操作系统中的虚拟内存系统，其存储了虚拟地址到物理地址间的映射。虚拟地址在访问进程中是唯一的，而物理地址在硬件（比如内存）中是唯一的[1]。
分页表的角色
[编辑]在操作系统中使用虚拟内存，每个进程会认为使用一块大的连续的内存。事实上，每个进程的内存散布在物理内存的不同区域。或者可能被调出到备份存储中(一般在硬盘)。当一个进程请求自己的内存，操作系统负责把程序生成的虚拟地址，映射到实际存储的物理内存上。操作系统在分页表中存储虚拟地址到物理地址的映射。每个映射被称为分页表项（page table entry，PTE）。
转换过程
[编辑]CPU的内存管理单元（memory management unit MMU）存储最近用过的映射缓存，来自操作系统分页表。被称为轉譯後備緩衝區（translation lookaside buffer, TLB）。TLB是一个索引缓存。
当需要将虚拟地址转换为物理地址时，首先搜索TLB。如果找到匹配（TLB命中），则返回物理地址并继续存储器访问。然而，如果没有匹配（称为TLB未命中），则存储器管理单元或操作系统TLB未命中处理器通常会查找页表中的地址映射以查看是否存在映射（页面遍历）。如果存在，则将其写回TLB（这必须完成，因为硬件通过虚拟存储器系统中的TLB访问存储器），并且重启错误指令（这也可以并行发生）。此后续转换将找到TLB命中，并且内存访问将继续。
转换失败
[编辑]有两种原因导致分页表查找失败。第一种，如果该地址没有可用的转换，这意味该虚拟地址的存储器访问是无效的。这通常是程序错误导致，操作系统需要处理这个问题。现代操作系统会发送一个段错误信号给出错程序。
当物理内存中不存在这个页，也会引起分页表查找失败。如果请求的页面被调出物理内存，给其他页腾出空间，会引起这个错误。这种情况下，页被分配到存储在介质上的辅助存储，例如硬盘。（这种辅助存储，或叫备用存储，如果是一个硬盘分区或者交换文件, 经常称之为交换分区，如果是文件，叫做分区文件或页文件。）这时候，分页需要从硬盘放回到物理内存中，这类操作通常会导致一种称为系统抖动（thrashing）的情况，通过局部性原理（principle of locality）来预测将来可能会访问的块，避免出现系统抖动。
当物理内存没满的时候，这是一个简单操作。页被写回物理内存，页表和转换备用缓冲会更新，指令重启。然而，当物理内存已满，一个或多个页要被调、为请求的页面腾出空间时候。页表需要更新，标识出那些在物理内存被调出的页，然后标识那些从硬盘调入物理内存的页。TLB也需要更新，包括去掉调出的页，重启指令。页的调入调出请见页置换算法。
分页表数据
[编辑]最简单的分页表系统通常维护一个帧表和一个分页表。帧表处理帧映射信息。更高级系统中，帧表可以处理页属于的地址空间，统计信息和其他背景信息。
分页表处理页的虚拟地址和物理帧的映射。还有一些辅助信息，如当前存在标识位(present bit)，脏数据标识位或已修改的标识位，地址空间或进程ID信息。
辅助存储，比如硬盘可以用于增加物理内存。页可以调入和调出到物理内存和磁盘。当前存在标识位可以指出那些页在物理内存，哪些页在硬盘上。页可以指出如何处理这些不同页。是否从硬盘读取一个页，或把其他页从物理内存调出。
脏数据标识位可以优化性能。一个页从硬盘调入到物理内存中，读取后调出，当页没有更改不需要写回硬盘。但是如果页在调入物理内存后被修改，会标记其为脏数据，意味着该页必需被写回备用存储。这种策略需要当页被调入到内存后，后备存储保留一份页的拷贝。有了脏数据标志位，一些页随时会同时存在于物理内存和后备存储中。
如果不是单地址空间操作系统，地址空间或进程id信息是必要的，内存管理系统需要知道页对应的进程。两个不同意图的进程可以使用两个相同的虚拟地址。分页表必需为两个进程提供不同的虚拟内存。用虚拟内存页关联进程ID页可以帮助选择要调出的页，当页关联到不活跃进程上，特别是那些主要代码页被调出的进程，相比活跃进程需要页的可能性会更小。
分页表类型
[编辑]有一些不同的分页表类型，适合不同应用场景。本质上，准系统分页表必需存储虚拟地址，物理地址排在之后，还有一些可能的地址空间信息。
倒排分页表
[编辑]倒排分页表（IPT）被认为是一个标准RAM的TLB的off-chip扩展。不同于一个真实的分页表，IPT不需要处理所有当前映射。操作系统要准备处理丢失，就像mips风格的软件填充TLB。
IPT把分页表和帧表结合成一个数据结构。其核心是一个固定大小的表，表的行数等于内存中的帧数。如果有4000个帧，倒排分页表有4000行。每个行的表项对应虚拟内存页码，物理页页码（不是物理地址），一些其他数据，创建碰撞链。
从所有IPT内核结构中搜索表项效率很低，所以我们用哈希表来映射虚拟地址（或可能需要的地址空间/PID信息）对应的IPT索引，这里会使用冲突链。哈希表被称作哈希锚点表。哈希方式没对覆盖率做通常的优化，原始速度更理想。当然，哈希表会有冲突。由于这个哈希方式，我们使用时候会经历很多冲突，所以表中VPN创建的每个表项，会检查是否是已被检索的表项或冲突。
在搜索映射时候，使用哈希锚点表。如果没有表项存在，会出现一个页错误。否则，表项被找到。依赖于架构，表项被重新放入TLB，内存指令重启，或跟踪冲突链直到结束，然后出现页错误。
这种模式种，一个虚拟地址可以分成2部分。前半段是虚拟页码，后半段是页中的偏移量。
这种设计的主要问题在于哈希方式cache命中率较弱。基于树的设计，忽略在分页表表项中置换相邻位置的相邻页。但是一个倒排分页表把表项离散，会破坏引用的空间局部性。为了减少这个问题，操作系统会使哈希表空间最小，平衡增长的未命中比率。通常会有一个哈希表，在物理内存中连续，共享给所有进程。内存碎片会导致预处理分页表不现实，所以用一个预处理标识消除不同进程的页的歧义。从进程中去掉分页表项或许有点慢，操作系统会忽略重用预处理标识值，延迟面对这个问题，选择忍受大量内存浪费，用于映射预处理哈希表。
多级分页表
[编辑]倒排分页表为所有物理内存中的帧，建立一个映射列表。但是这个可能会比较浪费。相反，我们通过保持一些覆盖当前虚拟内存区块的分页表，建立一个包含虚拟页映射的分页表数据结构。比如，我们创建1024个小于4K的页，覆盖4M的虚拟内存。
这非常有用，因为通常虚拟内存的顶部和底部用于正在运行的进程，顶部通常用于文本和数据段，底部用于堆栈，空闲内存居中。多级分页表会保持少量较小分页表，仅覆盖内存顶部和底部，只有确实需要时候才创建新的。每种较小分页表被一个主分页表链接再一起，有效的创建一个树型数据结构。需要不只2级，可能有多级。
这种模式下，一个虚拟地址可以分成三部分：根分页表的索引，子分页表的索引，子分页表偏移量。多级分页表也叫做分级分页表。
虚拟分页表
[编辑]已经提到了，在虚拟地址空间中为每个虚拟页创建分页表结构，最终会导致浪费。但是我们可以把分页表放入虚拟内存，允许虚拟内存管理分页表内存，来避免过多空间被涉及。
但是一部分这种线性分页表结构，需要一直存在于物理内存，来防范循环页错误。会寻找一个不存在于分页表中的重要部分，在当前分页表中没有。
嵌套分页表
[编辑]嵌套分页表可以被用于增加硬件虚拟化的性能。为分页表虚拟化提供硬件支持，会大大降低模拟的需要。x86下虚拟化当前的选择是Intel的扩展分页表特性，和AMD的快速虚拟索引特性。
参考文献
[编辑]- ^ Home — Memory Management Reference 4.0 documentation. www.memorymanagement.org. [2018-08-15]. （原始内容存档于2020-12-13）.