operating-system - 分页：基本、分层、散列和倒置

Question

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

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

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

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

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

我只是想知道每种方法的优缺点是什么？看起来基本是更简单的方法，但也可能会占用更多内存空间以获得更大的地址空间。还有什么？

Answer 1

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

• Basic 会占用大量内存（对于使用 4GB 内存的现代系统，仅表可能会达到 300 MB），因此不切实际。

• 分层仅通过添加实际使用的子表来大大减少内存。尽管如此，每个进程都有一个根页表。并且如果进程的内存占用比较分散，那么辅助表中可能还会有很多不必要的条目。这是一个比 Basic 更好的内存解决方案，并且只引入了边际计算增加。

• 由于哈希冲突，哈希不起作用

• Inverted 是使 Hashed 工作的解决方案。内存使用非常小（与单个进程的基本表一样大，加上一些 PID 和链接开销）。问题是，如果存在哈希冲突（多个进程使用相同的虚拟地址），您将必须遵循链信息（就像在链表中一样），直到找到具有匹配 PID 的条目。除了散列计算之外，这可能会产生大量的计算开销，但会使内存占用尽可能小。