U3 Part 2: 内存管理 | Memory Management¶

按需换页系统概述¶

按需换页(demand paging)^Wiki和交换技术中的页置换很类似，指只把被需要的页载入内存，是一种内存管理系统。

可以想象，现在给定任意一个虚拟地址，有三种可能：

1. 该“地址”在物理内存中，页表中存在虚拟内存到物理内存的映射关系，是 valid 的；
2. 该“地址”在后备存储中，页表中不存在虚拟内存到物理内存的映射关系，是 invalid 的；
3. 该“地址”并没有被分配，页表中不存在虚拟内存到物理内存的映射关系，是 invalid 的，或权限不符（如试图写入一个只读页）；

与引入交换技术之前的页表设计相比，多出来的就是情况 2.。如果系统访问了一个在页表中是 invalid 的页，就会生成异常，我们称这种情况为缺页(page fault)。

区别于之前的页表设计——访问 invalid 的表项是一种预期外行为，现在产生缺页反而更多是一种预期内的行为——系统对某个被 page out 了的页产生了“需求”。当然，情况 3. 这种非法操作也会引起异常，所以我们需要在之后的异常处理过程中对此做区分并分别处理。

说实话其实我感觉这里的逻辑稍微有点绕，可能是一些历史原因。

操作系统就需要去处理这个异常的大概流程如下：

page fault 处理流程

1. 检查一张 PCB 里的内部表，来区分这个地址到底是情况 2. 还是情况 3.；
   1. 如果是情况 2.，则继续如下操作以将其 page in；
   2. 如果是情况 3.，则终止进程；
2. 从可用帧列表里拿出 frame 用来写入；
   • 如果可用帧列表为空，则进行页置换；
3. 开始从后备存储读取内容，并写入 frame；
4. 完成读写后，更新内部表和页表等元信息；
5. 重新执行引起 page fault 的 instruction；
   • 该操作十分关键，类似于死锁里的回滚操作，支持这项操作也具有一定的难度，包括如何确切地恢复回指令执行之前的状态、如何消除执行了一半的指令的效果等；

Steps in handling a page fault.

我们可以在 Lab5 里对这一系列步骤有跟深刻的影响，Lab5 中的 vma 大概就是这里的“内部表”。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

const int N = PAGE_SIZE;

void foo() {
    /* ... */
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            a[i][j] = 0;
        }
    }
    /* ... */
}

void bar() {
    /* ... */
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            a[i][j] = 0;
        }
    }
    /* ... */
}

程序执行的局部性假设下，应当不会因为 page fault 太频繁导致带来不可接受的额外开销。需要注意，单条指令是有可能带来若干次 page fault 的（例如可能在 instruction fetch 的时候产生、可能在 operand fetch 的时候产生等）。

回顾 copy on write¶

我们在进程管理一节中提出了 copy on write 技术和 vfork 技术，现在读者可以尝试再回顾一下这两个知识点与本节内容的联系。

可用帧列表¶

在 demand paging 系统里，页是动态地被映射到帧的，所以我们需要维护一个可用帧列表(free-frame list)，用来记录当前哪些帧是空闲的。

Example of free-frame list.

在系统启动后，我们需要将所有可用的帧都加入到 free-frame list 中；当有用户需要物理内存时候，就从 free-frame list 中取出一项，对其进行擦除，即被需求时清零(zero-fill-on-deman)。

如果读者足够敏锐就会发现，我们只说了怎么取出 free-frame，而没说 free-frame 如何“再生”。

当我们发现 free-frame list 为空，即没有空闲的 frame 时，我们考虑将一些先前已经被分配的 frame 给 page out 走，拿来给当前这个页用。而具体如何选择换走哪个 frame，我们会在置换策略一节中介绍。

free-frame buffer pool

虽然我们还没介绍置换策略，但是想象一下，如果等到没有 free-frame 的时候再去做置换，那么进程就需要等待置换完成以后再分配。

我们可以考虑在这里引入一个抽象的 buffer，我们可以保证 free-frame list 始终有一定数量的空闲帧，例如 3 个。这样当进程来索取 free-frame 的时候，free-frame list 大概率总是能够直接给出一个 free-frame 的，而给出 free-frame 后，如果发现 free-frame list 中的剩余帧数小于 3，那么就可以独立地开始进行置换，而不必阻塞进程。

---

又或者，我们不使用一个确切的界，而是通过一种负反馈控制，维护一个上界和下界：当 free-frame 数小于下界时，一类叫收割者(reapers)的内核例程就开始使用 replacement algorithm 来 reclaim 已经被分配的 frame，直到 free-frame 的数量触碰到上界。

Reclaiming pages.

---

进一步的，万一此时出现了一些特殊情况，导致实际的 free-frame 数非常少，达到了一个非常低的界，此时就出现了 OOM(out-of-memory)。此时，一个叫做 OOM killer 的例程就会杀死一个进程，以腾出内存空间。

在 Linux 中，每个进程会有一个 OOM score，OOM score 越高约容易被 OOM killer 盯上，而 OOM score 与进程使用的内存的百分比正相关，所以大概的感觉就是谁内存用的最多就杀谁。¹如果读者对 Linux 的 OOM 机制有兴趣，可以看看角注 1。

分配策略¶

在 pure demand paging 里，每个进程通过 page fault 不断“蚕食” free-frame，但如果我们不适用 pure 的 demand paging，那么就需要决定一开始分配多少 frames 给一个 process。

首先，对于单个进程的分配，存在一个较严格的上下界：

早期分配算法(frame-allocation algorithm)按照分配的帧的大小来分，主要有这么两种：

我们发现，上面关于内存分配大小的式子中，有一项 \(n\) 表示 #process，区别于其它相对静态的参数，这个参数是会在调度过程中动态变化的，所以实际上分配给每个进程的 frame 数量也是会动态变化的。

在多核设计下，有一种设计叫做 NUMA^Wiki，我们在 Overview 其实也提到过。在这种设计里，由于硬件设计问题，不同的 CPU 都有自己“更快”访问的内存。读者可以通过上面的 Wiki 链接做详细了解。

置换策略¶

当 free-frame list 为空，但用户仍然需要 frame 来进行 page in 时，就需要进行页置换(page replacement)，将并没有正在被使用的页腾出来给需要 page in 的内容用，而这个“被要求腾出地方”的页，我们称之为牺牲帧(victim frame)。

显然这里的 “page” 是基于 Definition 2。

我们细化 page fault 处理流程的 2.a. 项，大概是如下的步骤：

如果这个 victim frame 在被 page in 以后没有被修改过，那么我们可以直接将它覆盖，不需要写回后备存储，能节省一次内存操作；反之，如果这个 victim frame 被修改过，那么我们需要将它写回后备存储，类似于将修改给 “commit” 了。而为了实现这个优化，我们用一个修改位(dirty bit 或 modified bit)来记录页是否被修改过，当 frame 刚被载入内存时，dirty bit 应当为 0；而一旦帧内有任何写入操作发生，dirty bit 就会被置 1。

现在我们来讨论具体的置换算法(replacement algorithm)。

OPT¶

理论上最优，即 ⓵ 能带来最低的 page fault rate，⓶ 绝对不会遭受 Belady's anomaly 的做法是：在未来最久的时间内不会被访问到的页作为 victim frame。这句话说起来有点绕，用英文描述是：Replace the page that will not be used for the longest period of time.

换句话来说就是选之后再也不会被用到的或（如果没有前者）下一次用到的时间最晚的页作为 victim frame。

可以发现，我们实际上很难来预测一个 frame 下一次被使用是什么时候，所以该方法只是一个理论上的最优建模，我们在后面应当考虑去逼近这个建模。

FIFO¶

先入先出(first-in, first-out, FIFO)策略，即选择正在使用中的、最早进入内存的 frame 作为 victim frame。我们可以通过在内存中完整地维护一个 FIFO 队列来实现这个策略。

FIFO 策略的优点就是简单，方便实现；缺点是并不够好——早被载入的 page 也可能会被频繁的使用。换句话来说，这个方法用被载入的早晚来建模 page 的使用频率，但是这个建模相比 optimal 的建模并不足够接近。

LRU¶

我们的目标是为了逼近难以实现的 optimal，而 optimal 之所以难以实现，是因为我们很难“预知未来”，我们能利用的只有已经经历过的事情。

Least recently used(LRU) 算法的思路是，基于「很久没被用过的 page 可能在短期不太会被再次使用，刚刚用过的 page 可能在短期被频繁地用」的假设，用“最久没用过”来建模「未来最久时间内不会被访问」，即选择最久没被访问过的 frame 作为 victim。

LRU 是比较常用的 replacement algorithm（实际上是 LRU-Approximation），因为是被认为比较好的 replacement algorithm。

现在我们来考虑如何实现 LRU，或者说，如何来维护一个 frame 有多久没被访问过。

LRU Approx.¶

由于我们在 Stack Algorithm 里提到的诸多弊端，我们考虑近似地，实现 LRU 算法——实际上是近似实现 Stack Algorithm。

多数操作系统会提供一个叫 reference bit 的功能。所有 frame 都有一个与之关联的 reference bit，在初始化的时候都会被置 0；而每当 frame 被使用时，reference bit 就会被置 1。于是，我们可以通过观察 reference bit 来观察某些 frame 是否被使用过。

开始之前，我们分析 LRU 的限制，主要体现在两个方面：⓵ 需要全部历史信息，维护成本较大（需要设计数据结构来存储）；⓶ 数据维护过于频繁，每次使用 frame 都需要用一段不小的开销去更新状态。

对应的解决方案是：⓵ 我们完全可以只关注一个邻域里的历史信息，⓶ 我们可以降低更新 frame 信息的频率。（虽然对于后者，实际上如果对应于 reference bit 的更新，其实并没有降低频率。）

基于计数的置换¶

我们考虑用 counter 来记录正在使用的 frame 中每个 frame 被使用的次数，用 counter 的值来建模“使用频率”。按照后续操作不同分为这两种：

• Least frequently used(LFU) 选择 counter 最小的 frame 作为 victim frame；
• Most frequently used(MFU) 选择 counter 最大的 frame 作为 victim frame；
  • 这个做法基于「counter 小的 frame 可能才刚刚被 load 进来」这个假设；

抖动¶

倘若系统的多道程度过高，那么可能分配给每一个 process 的 frames 数量就会比较少，process 所使用的 frames 中被频繁使用的 page 占比更大。这时候可能就会产生较为频繁的 paging 活动——几乎所有 frames 都正在被使用，相当于每次置换都会导致一个新的 page fault——进而导致 CPU 的利用率下降，这种现象被称为抖动(thrashing)。

例如，process A 可能抢走了 process B 的正要被使用的 frame，于是导致 process B 之后会产生一次 page fault；而在处理这个 page fault 的时候，可能又把 process C 的正要使用的 frame 给抢走了……

使用 Priority¶

可以想象到，这里出现了一种类似于互相抢 frame 的情况。我们可以通过让一方“让步”来解决，例如使用 priority replacement algorithm 来解决。

Working Set¶

还有一种基于局部性假设的做法，叫 working set model。它的大致思路是将「每一个进程在一个 \(\Delta\) 时间窗口内用到过的 frame」建模为一个进程的 working set \(WS_i\)，如果 \(\sum_i |WS_i| > m\)，即所有进程的 working set 的大小之和大于可用 frame 的数量，那么就可能会出现 thrashing。此时操作系统可能就会选择挂起某个 process，以降低 degree of multiprogramming。这个做法的一个问题和 LRU 是类似的，要去维护 \(WS_i\) 是比较吃力的，而解决办法也是类似的，我们可以近似地去维护 \(WS_i\)。

详细内容不再展开，读者可以参考 Wiki 做更多了解。此外，working set 的思路可以用于实现 pre-paging。

PFF¶

或者也能利用缺页频率(Page-Fault Frequency, PFF)来做动态调节，由于 PFF 与进程可用的 frames 数量大致成负相关，我们可以设定上下界并进行负反馈控制：process 的 PFF 过高时增加它可用的 frames 数量，当 process 的 PFF 较低时可以减少它可用的 frames 数量。

不过，对于该问题，先行的最佳解决方案其实是增加物理内存，从硬件上解决问题。

内存压缩¶

内存压缩(memory compression)的思路区别于 swap，把 frame 换到 backing store 里，而且尝试去 merge 一些 frame，即利用内部碎片。

内核内存¶

我们之前讨论的内存管理机制，尤其是内存的分配和置换机制，都是针对 user process 的。而内核的运行同样需要 memory，但它不能使用和 user process 相同的内存设计。由于 kernel 程序是一直运行的，所以我们必须更保守地使用内存，诸内部碎片的问题应当尽可能避免，事实上，许多操作系统都对 kernel 使用 paging 设计。再加上由于 kernel 需要和一些硬件做交互，而许多硬件设备都只直接与物理内存做交互，所以我们还需要对 kernel 内存在物理内存上的连续性有一定保证。

Buddy 系统¶

Buddy system^Wiki 可以用来分配物理连续的内存，它由 power-of-2 allocator 实现。

当 kernel 需要 \(n\) KB 的内存时候，Buddy system 会分配一块 \(2^k\) KB 的空间，其中 \(k = \lceil \log_2{n} \rceil\)。

显而易见的，这样还是容易出现内部碎片，Buddy system 无法解决这种内部碎片，但是稍候接受的 Slab allocation 可以。

具体来说，Buddy system 通过不断二分的方式来寻找一块合适的内存，如下图：

例如 kernel 申请一块 21KB 的内存，那么 \(C_L\) 就是我们最终分配的内存。

Buddy system 还有一个特点是，它通过 coalesce 相邻的空闲块来形成更大的内存块，例如上图可以按照分裂的方式合并回 256 KB 的大内存块（合并大内存）。

Slab 分配¶

Slab 分配的大概思路是预先了解到 kernel 内的常见数据结构（被称为各种 object）的大小，并预先准备好对应粒度的小内存块，注册到每类 object 的 cache 里。当一个 object 需要使用内存时，就查询对应的 cache 里是否有空闲的内存块，如果有就分配给它，如果没有就向 Buddy system 申请。

相当于预先把内存分成了苹果小盒、冰箱大箱、超大车库，然后根据要放的东西的大小选择合适的空间来放。

激励

评论