操作系统中的哈希页表是什么？

在本教程中，我们将学习用于组织页表的一些最常见技术。操作系统虚拟内存系统用于存储物理地址和逻辑地址之间映射的数据结构通常被称为页表。

CPU生成的逻辑地址在页表的帮助下被翻译成物理地址。因此，页表主要提供存储该页面在主内存中的相应帧号（帧的基地址）。页表的一些特性如下：

• 它存储在主内存中。
• 页表中的条目数等于进程被划分为的页面数。
• 页表基址寄存器（PTBR）基本上用于保存当前进程页表的基地址。
• 每个进程都有自己独立的页表。

以下是一些用于组织页表的常用技术，例如：

1. 分层分页
2. 哈希页表
3. 倒排页表

什么是分层分页？

分层分页的另一个名称是多级分页。当 CPU 访问任何进程的页面时，该页面必须在主内存中。除了页面之外，同一进程的页表也必须存储在主内存中。可能存在页表太大的情况，以至于无法将其放在连续的空间中，从而可能出现多级层次结构。

在这种分页类型中，逻辑地址空间被分成多个页表。分层分页是最简单的技术之一，可以使用两级页表和三级页表来实现。让我们通过一个例子来理解这些级别。

1. 两级页表：两级分页是指页表本身被分页。因此，我们将拥有两个页表：内部页表和外部页表。考虑一个具有 32 位逻辑地址空间和 1 KB 页大小的系统。它被进一步划分为由 20 位组成的页号和由 12 位组成的页偏移量。

当我们分页页表时，页号被进一步划分为：由 10 位组成的页号和由 12 位组成的页偏移量。

因此，逻辑地址如下：

在上图中，P1 是外部页表的索引，P2 表示内部页表页内的偏移量。

由于地址转换从外部页表向内工作，因此称为正向映射页表。

上图显示了两级页表的地址转换方案。

2. 三级页表：两级分页方案不适用于具有 64 位逻辑地址空间的系统。假设页大小为 4KB。如果我们使用两级页表方案，则地址将如下所示：

因此，为了避免如此大的表，可以通过将外部页表进行划分来解决，这将导致如下所示的三级页表。

什么是哈希页表？

哈希页表是内存中组织页表的一种技术。在哈希页表中，虚拟地址被哈希到哈希表中。表中的每个元素都包含一个元素链表以避免冲突。使用的哈希值是虚拟页号，即不属于页偏移量的所有位。

哈希表中的每个元素都包含虚拟页号、映射页的值以及指向下一个元素的指针。哈希页表在地址空间大于 32 位时很常见。对于哈希表中的每个元素，都有三个可用字段：

1. 虚拟页号（即哈希值）。
2. 映射页帧的值。
3. 指向链表中下一个元素的指针。

虚拟页号与第一个字段（即虚拟地址）进行匹配，如果找到匹配项，则使用第二个字段中相应的映射地址来形成所需的内存地址。如果未找到匹配项，则使用下一个指针遍历链表，直到找到匹配项。

尽管我们可以使用多级页表来组织大型页表，但它会包含多个级别，从而增加了页表的复杂性。

哈希页表的工作原理

我们将通过一个例子来理解哈希页表的工作原理。CPU 生成其需要的页面的逻辑地址。现在，这个逻辑地址需要映射到物理地址。这个逻辑地址有两个条目，即页号（P₃）和偏移量，如下所示。

• 逻辑地址中的页号被导向哈希函数。
• 哈希函数会为页号生成一个哈希值。
• 此哈希值指向哈希表中的一个条目。
• 正如我们之前所学，哈希表中的每个条目都有一个链表。这里，页号与链表第一个元素的第一个条目进行比较。如果找到匹配项，则检查第二个条目。

在此示例中，逻辑地址包含页号 P₃，它与链表的第一项不匹配，因为它包含页号 P₁。因此，我们将继续检查下一项；现在，该项具有页号条目，即 P3，因此，我们将进一步检查该项的帧条目，即 fr₅。我们将逻辑地址中提供的偏移量附加到此帧号，以找到页面的物理地址。这就是哈希页表如何工作以将逻辑地址映射到物理地址。

聚类页表也用于使该算法适用于 64 位地址空间。

什么是聚类页表？

聚类页表与哈希页表类似，不同之处在于哈希表中的每个条目指向多个页面而不是单个页面（如哈希页表）。因此，聚类页表的单个条目可以存储多个物理页帧的映射。

聚类页表对于稀疏地址空间很有用，在稀疏地址空间中，内存引用分散在整个地址空间（不连续）中。

什么是倒排页表？

正常分页的概念是每个进程维护自己的页表，其中包含属于该进程的所有页面的条目。大进程可能有一个包含数百万个条目的页表。这样的页表会占用大量内存。假设我们有六个进程正在执行。因此，六个进程将有或多或少一些页面在主内存中，这将迫使它们的页表也必须在主内存中占用大量空间。这是分页概念的一个缺点。

倒排页表是解决此内存浪费问题的方法。倒排页表概念包含主内存中每个帧的一个页表条目。因此，倒排页表中的页表条目数减少到物理内存中的帧数。一个页表代表所有进程的分页信息。

倒排页表消除了为每个进程存储单独页表的开销。只需固定一部分内存即可存储所有进程的分页信息。这种技术称为倒排分页，因为它是根据帧号而不是逻辑页号进行索引的。页表中的每个条目都包含以下字段：

• 页号：它指定逻辑地址的页号范围。
• 进程 ID：倒排页表包含所有正在执行的进程的地址空间信息。由于两个不同的进程可能具有相同的虚拟地址集，因此必须存储每个进程的进程 ID 以在倒排页表中唯一标识其地址空间。这是通过使用 Pid 和 Page Number 的组合来实现的。因此，这个进程 ID 作为地址空间标识符，并确保特定进程的虚拟页正确映射到相应的物理帧。
• 控制位：这些位用于存储额外的分页相关信息。这些包括有效位、脏位、引用位、保护位和锁定信息位。
• 链式指针：有时可能发生两个或多个进程共享主内存的一部分。在这种情况下，两个或多个逻辑页面映射到相同的页表条目，然后使用链式指针将这些逻辑页面的详细信息映射到根页表。

倒排页表的工作原理

CPU 生成其需要访问的页面的逻辑地址。逻辑地址由三个条目组成：进程 ID、页号和偏移量，如下所示。

进程 ID 标识了请求页面的进程，页号指明了请求的是该进程的哪个页面，偏移量指明了所需的位移量。

在页表中搜索进程 ID 和关联的页号的匹配项，并且如果搜索在页表的第 i^th 个条目处找到，则 i 和偏移量一起生成所请求页面的物理地址。这就是使用倒排页表将逻辑地址映射到物理地址的方法。

虽然倒排页表减少了内存浪费，但它增加了搜索时间，因为倒排页表中的条目是根据物理地址排序的。相比之下，查找是使用逻辑地址执行的。有时会搜索整个表才能找到匹配项。

因此，这三种技术可用于组织页表，这些页表帮助操作系统将 CPU 所需页面的逻辑地址映射到其物理地址。