分页:基本分页、分层分页、散列分页和倒排分页

发布于 2024-10-30 08:14:20 字数 297 浏览 3 评论 0原文

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

基本 - 存储页号和偏移量的单个页表 分层

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

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

反转 - 逻辑地址还包括 PID、页号和偏移量。然后使用 PID 来查找表中的页,并将表中的行数添加到偏移量中以查找主内存的物理地址。 (粗糙的,可能是糟糕的定义)

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

With respect to operating systems and page tables, it seems there are 4 general methods to paging and page tables

Basic - A single page table which stores the page number and the offset

Hierarchical - A multi-tiered table which breaks up the virtual address into multiple parts

Hashed - A hashed page table which may often include multiple hashings mapping to the same entry

Inverted - The logical address also includes the PID, page number and offset. Then the PID is used to find the page in to the table and the number of rows down the table is added to the offset to find the physical address for main memory. (Rough, and probably terrible definition)

I am just wondering what are the pros and cons of each method? It seems like basic is the easier method but may also take up more space in memory for a larger address space.
What else?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

我做我的改变 2024-11-06 08:14:20

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

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

  • 分层结构仅添加实际使用的子表,从而大大减少了内存。尽管如此,每个进程都有一个根页表。而且,如果进程的内存占用是分散的,则辅助表中仍然可能存在大量不必要的条目。这是一个比 Basic 更好的内存解决方案,并且仅带来边际计算增加。

  • 由于哈希冲突,Hashed 不起作用

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

The key to building a usable page model is minimizing the unused space for entries that are not necessary. You want to minimize the amount of memory needed while keeping the computation cost of a memory lookup low.

  • Basic can take up a lot of memory (for a modern system using 4GB of memory, that might amount to 300 MB only for the table) and is therefore impractical.

  • Hierarchical reduces that memory a lot by only adding subtables that are actually in use. Still, every process has a root page table. And if the memory footprint of the processes is scattered, there may still be a lot of unnecessary entries in secondary tables. This is a far better solution regarding memory than Basic and introduces only a marginal computation increase.

  • Hashed does not work because of hash collisions

  • Inverted is the solution to make Hashed work. The memory use is very small (as big as a Basic table for a single process, plus some PID and chaining overhead). The problem is, if there is a hash collision (several processes use the same virtual address) you will have to follow the chain information (just as in a linked list) until you find the entry with a matching PID. This may produce a lot of computing overhead in addition to the hash computing, but will keep the memory footprint as small as possible.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文