操作系统中的哈希表详细介绍

以下是用于构建页表–分层分页, 哈希表和倒页表.

让我们在本文中探索更多有关哈希页面表及其工作的信息。

散页表：

在哈希页表中, 虚拟地址中的虚拟页号被哈希到哈希表中。它们用于处理高于32位的地址空间。散列表中的每个条目都有一个散列到相同位置的元素的链接列表(为避免冲突, 因为我们可以为不同的页码获得相同的散列函数值)。哈希值是虚拟页码。虚拟页码是不属于页偏移量的所有位。

对于哈希表中的每个元素, 都有三个字段–

1. 虚拟页码(这是哈希值)。
2. 映射的页面框架的值。
3. 指向链表中下一个元素的指针。

散页表：

虚拟页码与链接列表的第一个元素中的字段1进行比较。如果匹配, 则使用相应的页面框架(字段2)来形成所需的物理地址。否则, 将检查链接列表中的后续条目, 直到虚拟页码匹配为止。

为了使该算法也适用于64位地址空间, 使用了群集页表。

集群页表与哈希页表类似, 不同之处在于哈希表中的每个条目都引用许多页面, 而不是单个页面(就像在哈希页表中一样)。因此, 群集页面表的单个条目可以存储多个物理页面框架的映射。

群集页表对于稀疏地址空间特别有用, 在稀疏地址空间中, 内存引用分散在整个地址空间中(不连续)。

---