在 OS 中使用分页方法如何证明其开销合理？

Question

所以我正在阅读操作系统中的分页。使用分页作为内存管理方法（我遇到过）的最大优点之一是它解决了外部碎片问题（在操作内存和存储中）并允许进程在非操作内存中分配 -连续 way.However 来实现分页，我们需要跟上并搜索页面 table，它可能有大量的条目（在某些情况下数百万）。我想这样做会有很大的开销（时间和 space 明智）。

我不明白的是，为什么我们不能在每次将程序加载到操作 memory.We 时将程序分成任意个段] 可以按照这样的方式划分它，如果需要，每个段 "fills a hole" 在操作内存中，因此解决外部 fragmentation.Obviously 程序可以以非连续方式加载的问题，我们只需要每个段（上限和下限）存储 2 个地址，可能还有一些 table 段以保持顺序。

引用我正在阅读的书（OS 概念 - Abraham Silberschatz、Peter Baer Galvin、Greg Gagne，第 9 版）："Because of its advantages over earlier methods, paging in its various forms is used in most operating systems, from those for mainframes through those for smartphones"。

我是不是漏掉了什么？使用分页如何证明其开销合理？我们真的需要跟踪每一页吗？在选择用于内存管理的正确方法时是否考虑了其他一些因素？

Answer 1

将程序分成任意段。

他们不能太武断；例如，我可能想为某些应用制作一个非常大的向量：

#define N 10000000
int v[N];
....
for (i = 0; i < N; i++) {
    v[i] = ...
}

编译器确实希望 v 看起来占用连续的内存位置。因此，您的分段器需要了解这些项目；但情况变得更糟：

int *v;
v = malloc(sizeof(*v) * N);
for (i = 0; i < N; i++) {
   v[i] = ...;
}

证明开销：

现在您需要在运行时找到一大块物理上连续的 RAM，并且由于您没有重定位机制，因此您无法在先前分配的块之间移动。这就是碎片化问题；而且没有page-style mmu，很难解决

你可以把你的编译型语言变成伪解释型语言来解决；但是有更多的开销：编译：

a = v[i];

into:
    ld R0,R1+R2*4    ; + overhead of mmu.
or:
    mov R0, R1+R2*4
    call findseg
    ld R0, R0

在一般情况下，就 RAM 而言，开销大约为 0.1%；举个具体的例子，在 ARM64 或 AMD64 架构上一个 4k 页面需要 10 个字节。 libc.so，在我的 linux 系统上，大约是 2M 文本 + 40k 数据；大多数程序只使用其中的一小部分。由于分页，只有使用的 libc 位需要占用内存。在具有 32 个进程的 64G 系统上，仅 libc 的节省就足以淹没页面 table 开销。

3：跟踪。有多种途径可以对此进行攻击。一种是多种页面大小，大多数体系结构都支持这种大小。另一个是 OS 不必提供 MMU 的粒度。例如，在一个有 4k 页的系统上，它可以坚持只交出 64K 块的内存。从而将管理开销减少了 16 倍，同时适度增加了粒度浪费。

Answer 2

分页是各种"virtual memory tricks"的基础，比如：

而不是必须等待文件加载后才能使用；将页面标记为 "belonging to a memory mapped file" 然后假装文件已加载（并在实际需要时从磁盘中获取页面，可能在后台发生一些预取策略）。这减少了 RAM 消耗并可以加快可执行文件的启动时间。
而不是在进程启动时分配实际的物理 RAM（对于其“.bss 部分”/未初始化的数据，"not used yet" 堆 space 等），而不是在 fork() 期间逐字复制所有页面；使用 "copy on write" 技巧，这样您只需要 create/copy 实际修改数据即可。这减少了 RAM 消耗并加快了一切速度（尤其是当大量内存从未被修改时）。
如果没有足够的 RAM，那么您可以只发送页面以交换 space（例如磁盘）并保留所有内容运行。这比等待永远不会发生的事情要快得多（因为进程因内存不足而崩溃）。
以上所有减少实际使用 RAM 量的事情都意味着您可以将该 RAM 用于文件系统缓存。更大的文件系统缓存可能意味着更快的文件 IO（更少 "file cache miss"，更慢的磁盘 IO）。当然，如果数据在文件缓存中，您也可以将与 "copy on write" 相同的页面映射到多个不同的进程（无需复制数据或使用更多 RAM）。

用于开销； CPU 制造商付出了很多努力来最小化开销（使用 "translation look-aside buffers"、预取策略、乱序执行以在等待转换发生时保持 CPU 忙碌， ETC）。同样，操作系统开发人员也试图最小化开销（例如，减少进程之间的任务切换次数，试图让进程保持在同一个内核上，等等）。这意味着与许多巨大的好处相比，开销相当小。

当然，如果没有分页，您最终不得不处理外部碎片，这通常会导致浪费大量 CPU 时间将大量数据从一块 RAM 复制到另一块 "de-fragment"内存。最重要的是，您还需要其他东西来确保隔离不同的进程并强制执行任何权限（如 "this area is not executable"）are/can；并且这个 "something else" 可能会增加与分页本身一样多的开销（除非你想要一个巨大的安全灾难）。考虑到这一点，即使您忽略了分页的好处，分页的开销仍然可能比不使用分页要少。

The thing that I don't understand is why can't we just divide a program into an arbitrary number of segments each time we load it into operative memory.

处理不同的段大小会很痛苦（更少 "shift and mask to find the right index in a table" 而更多 "do a linear search through all segments to find the right segment"）。如果您使用固定大小的段，它会快得多；但这就是分页（"page" 是您的 "fixed size segment"）。

在 OS 中使用分页方法如何证明其开销合理？

How does using paging method in OS justify its overhead?

memory-management

operating-system

paging

memory-segmentation