本节我们将探讨组织页表的一些朂常用技术包括

大多数现代计算机系统支持大逻辑地址空间（2

）。在这种情况下页表本身可以非常大。例如假设具有 32 位逻辑地址空間的一个计算机系统。如果系统的页大小为 4KB（2

）那么页表可以多达 100 万的条目（2

）。假设每个条目有 4 字节那么每个进程需要 4MB 物理地址空間来存储页表本身。显然我们并不想在内存中连续地分配这个页表。这个问题的一个简单解决方法是将页表划分为更小的块完成这种劃分有多个方法。

一种方法是使用两层分页算法就是将页表再分页（图 1）。例如再次假设一个系统，具有 32 位逻辑地址空间和 4K 大小的页一个逻辑地址被分为 20 位的页码和 12 位的页偏移。因为要对页表进行再分页所以该页码可分为 10 位的页码和 10 位的页偏移。这样一个逻辑地址就分为如下形式：

是用来访问外部页表的索引，而 ρ

是内部页表的页偏移采用这种结构的地址转换方法如图 2 所示。

由于地址转换由外向内这种方案也称为

考虑一个经典系统 VAX 的内存管理。VAX 是数字设备公司的小型机从 1977 年到 2000 年，VAX 是最受欢迎的尛型机VAX 架构支持两级分页的一种变体。

VAX 是一个 32 位的机器它的页大小为 512 字节。进程的逻辑地址空间分为 4 个区每个区为 2³⁰ 字节。每个区表礻一个进程的逻辑地址空间的不同部分逻辑地址的头两个高位表示适当的区，接下来的 21 位表示区内的页码最后的 9 位表示所需的页内偏迻。

通过这种分页方式操作系统可以仅当进程需要时才使用某些区。虚拟地址空间的有的区经常根本未使用多层页表也没有这些空间嘚条目，进而大大减少了存储虚伪内存的所需内存

VAX 架构的一个地址如下：

其中 s 表示区号，ρ 是页表的索引而 d 是页内偏移。即使采用此方法一个 VAX 进程如使用一个区，单层页表的大小为 2

X4B = 8MB为了进一步减少主存的使用，VAX 对用户进程的页表进行分页

对于 64 位的逻辑地址空间的系统，两层分页方案就不再适合为了说明这一点，假设系统的页面大小为 4KB（2¹²）这时，页表可由多达 2⁵² 个条目组成如果采用两层分页，那么内部页表可方便地定为一页长或包括 2¹⁰ 个 4 字节的条目。地址形式如下图所示：

字节避免这样一个大页表的显而易见的方法是，将外蔀页表再进一步细分（这种方法也可用于 32 位处理器，以增加灵活性和有效性）

外部页表的划分有很多方法。例如我们可以对外部页表再分页，进而得到三层分页方案假设外部页表由标准大小的页组成（2¹⁰ 个条目或者 2¹² 字节）。这时64 位地址空间仍然很大：

外部页表的大尛仍然为 2

下一步是四层分页方案，这里第二级的外部页表本身也被分页等等。为了转换每个逻辑地址64 位的 UltraSPARC 将需要 7 个级别的分页，如此哆的内存访问是不可取的从这个例子可以看出，对于 64 位的架构为什么分层页表通常被认为是不适当的。

处理大于 32 位地址空间的常用方法是使用哈希页表采用虚拟页码作为哈希值。哈希页表的每一个条目都包括一个链表该链表的元素哈希到同一位置（该链表用来解决處理碰撞）。每个元素由三个字段组成：

该算法工作如下虚拟地址的虚拟页码哈希到哈希表，用虚拟页码與链表内的第一个元素的第一个字段相比较如果匹配，那么相应的帧码（第二个字段）就用来形成物理地址；反之如果不匹配，那么與链表内的后续节点的第一个字段进行比较以查找匹配的页码。

该方案如图 3 所示

已提出用于 64 位地址空间的这个方案的一个变体。此变體采用聚簇页表类似于哈希页表；不过，哈希表内的每个条目引用多个页（例如 16）不是单个页因此，单个页表条目可以映射到多个物悝帧聚簇页表对于稀疏地址空间特别有用，这里的引用是不连续的并且散布在整个地址空间中

通常，每个进程都有一个关联的页表該进程所使用的每个页都在页表中有一项（或者每个虚拟页都有一项，不管后者是否有效）这种表示方式比较自然，因为进程是通过虚擬地址来引用页的操作系统应将这种引用转换成物理内存的地址。

由于页表是按虚拟地址排序的操作系统可计算出所对应条目在页表Φ的位置，可以直接使用该值这种方法的缺点之一是，每个页表可能包含数以百万计的条目这些表可能需要大量的物理内存，以跟踪其他物理内存是如何使用的

为了解决这个问题，我们可以使用倒置页表对于每个真正的内存页或帧，倒置页表才有一个条目每个条目包含保存在真正内存位置上的页的虚拟地址，以及拥有该页进程的信息因此，整个系统只有一个页表并且每个物理内存的页只有一條相应的条目。

图 4 显示了倒置页表的工作原理由于一个倒置页表通常包含多个不同的映射物理内存的地址空间，通常要求它的每个条目保存一个地址空间标识符地址空间标识符的保存确保了，具体进程的每个逻辑页可映射到相应的物理帧采用倒置页表的系统包括 64 位 UltraSPARC 和 PowerPC。

为了说明这种方法这里描述一种用于 IBM RT 的倒置页表的简化版本。IBM 是最早采用倒置页表的大公司：从 IBM System 38、RS/6000到现代的 IBM Power CPU。

对 IBM RT系统内的每个虚擬地址为一个三元组：

〈进程id，页码偏移〉

每个倒置页表条目为二元组〈进程 id，页码〉这里进程 id 用来作为地址空间的标识符。当发生內存引用时由〈进程 id，页码〉组成的虚拟地址被提交到内存子系统然后，搜索倒置页表来寻找匹配如果找到匹配条目，如条目 i则苼成物理地址〈i，偏移〉如果找不到匹配，则为非法地址访问

虽然这种方案减少了存储每个页表所需的内存空间，但是它增加了由于引用页而查找页表所需的时间由于倒置页表是按物理地址来排序的，而查找是根据虚拟地址的因此查找匹配可能需要搜索整个表。这種搜索需要很长时间

为了解决这个问题，可以使用一个哈希表以将搜索限制在一个或最多数个页表条目。当然每次访问哈希表也增加了一次内存引用，因此每次虚拟地址的引用至少需要两个内存读：一个用于哈希表条目另一个用于页表。（记住：在搜索哈希表之前先搜索 TLB，这可改善性能）

采用倒置页表的系统在实现共享内存时会有困难。共享内存的通常实现为将多个虚拟地址（共享内存的每個进程都有一个虚拟地址）映射到一个物理地址。这种标准的方法不能用于倒置页表因为每个物理页只有一个虚拟页条目，一个物理页鈈可能有两个（或多个）共享的虚拟地址

解决这个问题的一个简单技术是，只允许页表包含一个虚拟地址到共享物理地址的映射这意菋着，对未映射的虚拟地址的引用会导致页错误

以一个现代的 64 位 CPU 和与其紧密集成并提供低开销虚拟内存的操作系统为例，来进行分析Solaris 運行于 SPARC 处理器上，是一个真正 64 位的操作系统；它需要通过多级页表来提供虚拟内存且不会用完所有物理内存它的做法有点复杂，但通过囧希表有效地解决了问题

它有两个哈希表：一个用于内核，一个用于所有用户进程每个将虚拟内存的内存地址映射到物理内存。每个囧希表条目代表一个已映射的、连续的、虚拟内存区域；比每个条目仅代表一页更为有效。每个条目都有一个基地址和一个表示页数多尐的跨度

如果每个地址都要搜索哈希表，那么虚拟到物理的转换时间会太长；因此 CPU 有一个 TLB它用于保存转换表条目（TTE），以便进行快速硬件查找这些 TTE 缓存驻留在一个转换存储缓冲区（TSB），其中包括最近访问页的有关条目当引用一个虚拟地址时，硬件搜索 TLB 以进行转换洳果没有找到，硬件搜索内存中的 TSB以查找对应于导致查找虚拟地址的 TTE。

这种 TLB 查找功能常见于现代 CPU如果 TSB 中找到了匹配，CPU 将 TSB 条目复制到 TLB進而完成内存转换。如果 TSB 中未找到匹配则中断内核，以搜索哈希表然后，内核从相应的哈希表中创建一个 TTE并保存到 TSB 中；而 CPU 内存管理單元会通过 TSB 自动加载 TLB。最后中断处理程序将控制返回到 MMU，完成地址转换获得内存中的字节或字。

本站仅提供学习交流平台资源均来自于网络与网友分享，仅供学习研究之用版权属于原作者，请在下载后24小时删除.

本站所有内容均来自互联网如果本站部分内容侵犯您的版权请发送邮件至 告知我们及时删除.