分页:基本分页、分层分页、散列分页和反转分页

Question

关于操作系统和页表，似乎有4种通用的分页和页表方法

Basic -存储页码和偏移量的单页表

Hierarchical -将虚拟地址分成多个部分的多层表

哈希表-一个哈希页表，通常可能包含映射到同一条目的多个哈希

反转-逻辑地址还包括PID、页码和偏移量。然后，使用PID查找表中的页面，并将表中的行数与偏移量相加，以查找主内存的物理地址。(定义很粗糙，可能也很糟糕)

我想知道每种方法的优缺点是什么？basic似乎是更简单的方法，但对于更大的地址空间，也可能占用更多的内存空间。还有什么？

Answer 1

构建一个可用的页面模型的关键是最小化不需要的条目的未使用空间。您希望最小化所需的内存量，同时保持较低的内存查找计算成本。

• Basic会占用大量内存(对于使用4 4GB内存的现代系统，仅表的内存就可能达到300MB)，因此impractical.
• Hierarchical只添加实际正在使用的子表，从而大大减少了内存。尽管如此，每个进程都有一个根页表。如果进程的内存占用是分散的，那么在辅助表中可能仍然会有许多不必要的条目。在内存方面，这是一个比Basic好得多的解决方案，并且只引入了边缘计算，由于散列，increase.
• Hashed无法工作，因为collisions
• Inverted是使散列工作的解决方案。内存使用量非常小(与单个进程的基本表一样大，外加一些PID和链接开销)。问题是，如果存在散列冲突(多个进程使用相同的虚拟地址)，则必须跟踪链信息(就像在链表中一样)，直到找到具有匹配PID的条目。除了哈希计算之外，这可能会产生大量的计算开销，但会使内存占用尽可能小。