极客笔记操作系统 什么是散列页表
在本教程中，我们将学习用于构建 页表 的一些最常用的技术。操作系统中虚拟内存系统使用的数据结构，用于存储物理和逻辑地址之间的映射关系，通常称为 页表 。
由CPU生成的逻辑地址通过页表被转换为物理地址。因此，页表主要提供页面在主存中存储的相应帧号（帧的基地址）。页表的一些特点如下：
- 它存储在主存中。
- 页表中的条目数等于进程划分的页面数。
- 页表基址寄存器（PTBR）主要用于保存当前进程的页表的基地址。
- 每个进程都有自己独立的页表。
以下是用于构建页表的一些常见技术：
- 分层分页
- 散列页表
- 倒排页表
什么是分层分页
分层分页又称为多级分页。当CPU访问任何进程的页面时，它必须位于主存中。除了页面，相同进程的页表也必须存储在主存中。在某些情况下，页表太大以至于无法放入连续的空间中，因此我们可以使用多级层次来构建层次结构。
在这种类型的分页中，逻辑地址空间被分成多个页表。分层分页是一种最简单的技术，可以使用两级页表和三级页表来实现。让我们通过一个例子来了解这些层级。
1. 两级页表： 两级分页，其中一个页表本身也被分页。因此，我们会有两个页表：内页表和外页表。考虑一个具有32位逻辑地址空间和1 KB页面大小的系统。它进一步划分为包含20位的页号和包含12位的页偏移的页号。
当我们分页页表时，页号进一步划分为10位的页号和12位的页偏移。
因此，逻辑地址如下：
在上面的图像中，P1是指向 外部页面表 的索引，而P2表示 内部页面表 中的偏移。
由于地址转换是从外部页面表向内部进行的，因此被称为 前向映射的页面表 。
上图显示了一个两级页表的地址转换方案。
2. 三级页表： 对于一个64位逻辑地址空间的系统来说，使用两级分页方案是不合适的。假设页面大小为4KB。如果我们使用两级分页方案，那么地址将如下所示：
所以，为了避免这样一个庞大的表格，有一个解决方案是将外部页表分割，并且会产生一个如下所示的 三级页表。
什么是哈希页面表
哈希页面表 是一种用于在内存中存储页面表的技术。在哈希页面表中，虚拟地址被哈希成哈希表。表中的每个元素都包含一个链表以避免碰撞。使用的哈希值是虚拟页号，即除了页面偏移位之外的所有位。
哈希表中的每个元素都有虚拟页号、映射页面的值和指向下一个元素的指针。在大于32位的地址空间中，哈希页面表很常见。对于哈希表中的每个元素，有三个可用的字段，
- 虚拟页号（哈希值）。
- 映射页面帧的值。
- 指向链表中下一个元素的指针。
虚拟页号与第一个字段，即虚拟地址进行匹配，如果找到匹配项，则使用第二个字段中对应的映射地址形成所需的内存地址。如果找不到匹配项，则使用下一个指针遍历链表，直到找到匹配项为止。
虽然我们可以使用多级页面表来组织大页面表，但这会增加页面表的复杂性。
哈希页面表的工作原理
我们将通过一个示例来了解哈希页面表的工作原理。CPU生成所需页面的逻辑地址。现在，这个逻辑地址需要映射到物理地址。该逻辑地址有两个条目，即页号（P 3 ）和偏移量，如下所示。
- 逻辑地址的页面号码被传递到哈希函数。
- 哈希函数产生与页面号码对应的哈希值。
- 该哈希值指向哈希表中的一个条目。
- 如前所述，哈希表中的每个条目都有一个链接列表。在这里，将页面号码与第一个元素的第一个条目进行比较。如果找到匹配，则检查第二个条目。
在这个例子中，逻辑地址包括页面号码 P 3 与链接列表的第一个元素不匹配，因为它包括页面号码 P 1 。所以我们会继续检查下一个元素；现在，这个元素有一个页面号码条目，即 P3，所以接下来我们将检查元素的框架条目，即 fr 5 。我们将在逻辑地址中提供的偏移量附加到该框架号码上，以达到页面的物理地址。这就是哈希页表如何将逻辑地址映射到物理地址的工作原理。
聚集页表也用于使这个算法适用于64位的地址空间。
什么是聚集页表
聚集页表与哈希页表类似，只是哈希表中的每个条目不是指向一个单独的页面，而是指向多个页面。因此，聚集页表的一个条目可以存储多个物理页面帧的映射关系。
聚集页表对于稀疏地址空间很有用，其中内存引用分散在整个地址空间中（非连续）。
什么是反向页表
普通分页的概念是每个进程维护其自己的页表，包括属于该进程的所有页面的条目。大型进程可能具有数百万个条目的页表。这样的页表会占用大量内存。考虑到我们有六个正在执行的进程。因此，六个进程将在主存储器中有其某个页面，这将迫使它们的页表也在主存储器中占用大量空间。这是分页概念的缺点。
反向页表是解决这种内存浪费问题的解决方案。反向页表的概念包括每个主存框架的一个页面表条目。因此，反向页表中的页表条目数减少到物理内存中的框架数目。一个单独的页表代表所有进程的分页信息。
通过反向页表消除了为每个进程存储单独的页表的开销。只需要固定的内存部分来存储所有进程的分页信息。这种技术称为反向分页，因为索引是根据框架号而不是逻辑页号进行的。页表中的每个条目包含以下字段。
- 页号： 它指定逻辑地址的页面范围。
- 进程ID： 反转页表包含所有正在执行的进程的地址空间信息。由于两个不同的进程可以具有相似的虚拟地址集，因此有必要存储每个进程的进程ID，以在反转页表中唯一地标识其地址空间。这是通过使用Pid和Page Number的组合来完成的。因此，这个进程ID充当了地址空间标识符，并确保特定进程的虚拟页面正确映射到相应的物理帧。
- 控制位： 这些位用于存储额外的与分页相关的信息。这些信息包括有效位、脏位、引用位、保护位和锁定信息位。
- 链式指针： 有时可能会出现两个或多个进程共享主存的情况。在这种情况下，两个或多个逻辑页面映射到相同的页表项，然后使用链式指针来映射这些逻辑页面的详细信息到根页表。
反转页表的工作原理
CPU生成要访问的页面的逻辑地址。逻辑地址包含三个条目：进程ID、页号和偏移量，如下所示。
进程ID标识所需页面的进程，页面编号表示所需的进程页面编号，偏移值表示所需的位移。
在页面表中搜索进程ID和相关页码的匹配项，如果在页面表的第i项找到匹配，则i和偏移量一起生成所需页面的物理地址。这就是通过反转页表将逻辑地址映射到物理地址的方式。
虽然反转页表减少了内存的浪费，但增加了搜索时间，这是因为反转页表的条目是按物理地址排序的。相反，查找是使用逻辑地址进行的。有时需要搜索整个表来找到匹配项。
这些是用于构建帮助操作系统将CPU所需的页面逻辑地址映射到物理地址的页面表的三种技术。