L1：物理内存管理 (pmm)

⏰Soft Deadline: 2024 年 5 月 5 日 23:59:59

在命令行中 git pull origin L1 下载框架代码。我们总是在 kernel 目录下工作，因此如果你遇到了 Git 冲突(合并问题)，请以我们的新版本为准。

在获取到框架后，请把你 L0 的代码手工从 kernel 目录中移除。本实验需要提交以学号命名的 .pdf 格式实验报告 (保存在kernel/目录下)，之后的 OSLabs 将不断在此实验报告基础上添加。

此外，我们提倡拒绝内卷。除非特殊情况，本次实验的实验报告不建议超过 2 页 A4 纸。请在实验报告中描述你在实验中遇到的特别值得一提的事件，例如你代码的架构设计、特别精巧的实现、遇到印象深刻的 bug 等。

由于之后的实验会使用同一个 repo；你需要修改 Makefile，设置 export MODULE := L1，确保你提交到 L1 的 Online Judge。

1. 背景

如果你希望实现任何稍稍复杂一些的程序，对象 (内存) 的动态分配和回收几乎都是难以避免的。同时，作为一个多处理器编程 (互斥)的练习，我们实现多处理器上的物理内存管理，完成物理内存的分配和回收。

💡内存分配和回收

在从今往后的实验里，我们会逐步帮助大家纠正在面向算法竞赛的 Online Judge 编程时一个不好的习惯：只管分配，不管回收。大家在做 “算法题”时，不管是大数组 int dp[N][N]，还是 new Tree[N]，都指望操作系统在进程结束后自动回收资源。但在《操作系统》课上你不能这么做，因为你就是操作系统的实现者！

2. 实验描述

2.1 实现多处理器安全的内存分配和回收

🗒️实验要求：kalloc/kfree

框架代码 (实际上是 AbstractMachine) 会在 main 函数调用前初始化 heap 变量，[heap.start, heap.end)标记了一段操作系统内核可用的物理内存。所有操作系统内核所需的动态内存，以及所有应用程序所需的内存都来自 heap。因此，你需要实现允许多个处理器并发地申请或释放内存的分配器，包括以下两个函数：

static void *kalloc(size_t size) {
    // 内存分配
}

static void kfree(void *ptr) {
    // 内存释放
}

我们要求分配和回收满足：

• 原子性 ：当多个处理器同时请求内存分配或释放时，分配器必须确保同时进行的分配/回收操作能够正确完成。注意，在一个处理器上分配的内存，可能在另一个处理器上被释放。
• 无重叠 ：分配器返回的内存块之间不能有重叠。每次调用 kalloc 时，它必须返回一个独特的内存区域，该区域在其生命周期内不与任何其他分配的内存块共享地址空间。
• 对齐 ：对于大小为 s 的内存分配请求，返回的内存地址必须对齐到 $2^i$，其中 i 是最小的正整数满足 $2^i >= s$。例如，4 KiB 的内存分配请求返回的地址必须是 4,096 的整数倍 (页面边界)。例如，分配 17 字节内存返回的地址必须是 32 的整数倍。看似浪费，但这个实验要求简化了大家的实现。
• 无内存泄漏 ：当内存不再需要时，应该通过 kfree 正确释放。分配器需要确保所有释放的内存都可以被重新分配，不应该有任何内存泄漏。这意味着分配器需要准确跟踪哪些内存是空闲的，哪些是已分配的。
• 错误处理 ：当无法满足内存分配请求时（例如，因为没有足够的空闲内存），kalloc 应该返回 NULL (0)。
• 最后，不必初始化返回的内存，当然，对返回的内存赋上初始值 (例如零) 也许是个不错的主意。
• 由于我们在自制的操作系统内核中使用，你可以直接拒绝超过 16 MiB 的内存分配 。

2.2 性能优化 (Hard Tests)

🗒️实验要求：高性能的 kalloc/kfree

我们希望你的分配器应该尽量高效地使用内存，减少碎片，同时保持快速的分配和释放操作：

• 在 kalloc/kfree 实现正确的前提下，尽可能使不同处理器上的内存分配能够并行。
• 受分配算法的局限，可能系统中仍然有空闲的内存，但形成了碎片的内存，或是你的算法不能找到它从而分配失败。这是允许的；但在系统内存压力很小的时候依然频繁分配失败，可能导致 hard test failure。
• 如果你代码的性能过低 (例如用全局的锁保护空闲链表，并用遍历链表的方式寻找可用的内存)，可能会导致 hard test failure。

多处理器上的内存分配和释放带来额外的挑战：

1. 我们希望保证分配的正确性。这意味着用一把大锁保护一个串行数据结构 (例如算法导论上的 “区间树” 就能在 O(log⁡n) 的时间内完成分配和释放操作) 就能正确实现多处理器上的内存分配。
2. 我们希望保证分配在多处理器上的性能和伸缩性 (scalability)。这意味着不同的处理器能够并行地申请内存，尽可能减少因为同时申请而发生一个处理器等另一个处理器的情况。

上面两点需求是矛盾的，这也是本次实验的重点挑战。在这个实验里，我们通过 “system”的方法解决问题，而不是巧妙的算法/数据结构——这不意味着算法/数据结构在计算机系统中没有应用，只是在这个问题上并不非常必要。

☕️不要使用区间树

树型的数据结构很容易在并行时遇到瓶颈——虽然不代表你不能实现高效的树型数据结构，但现代流行的内存分配器都使用了更简单、更 “system”的方式解决问题：我们观察实际操作系统中内存分配的模式，提出最佳的算法。

2.3 实现 AbstractMachine 中 klib 中缺失的函数

在 Lab0 中，我们已经提出了这个实验要求。这个实验建议大家实现 klib 里缺失的函数——没有 printf, sprintf 等函数，你根本就是在用汇编语言写操作系统，你无法活到最后。我们不会检查大家的 klib 实现，但也请大家不要抄袭——虽然互联网上有很多代码，但自己写一遍依然是掌握这些库函数原理的最好方式。

3. 正确性标准

这个实验维护一个数据结构 (抽象数据类型)，维护一个不相交区间的集合 (堆区)：

初始时，\(H=∅\)。假设 heap.start\(=L\), heap.end\(=R\)。对于任意时刻的当前堆区 \(H\):

• kalloc(s) 分配 \(s\) 字节的内存 \([l, r)\) 满足：
  1. 分配发生在堆区中 \(L \le l < r < R\)
  2. 分配的内存不与已分配内存重叠 \(\forall[l_i,r_i) \in H, [l,r) \cap [l_i, r_i) = \emptyset\)
  3. 分配后新的堆区 \(H' = H \cup \{[l,r)\}\)
  4. 返回分配区间的左端点 \(l\)。
• kfree(l) 删除一个已有区间 \([l,r) \in H\)，得到新的堆区 \(H' = H \setminus \{[l,r)\}\). 当 \(l\) 不是 \(H\) 中任何一个区间左端点时，产生 undefined behavior——即 kfree 的调用者有义务保证一定释放一个已分配的空间。

⚠️重视正确性

如果你的 kalloc/kfree “几乎完全不正确”，问题反而容易排查。但如果在犄角旮旯的情况里有一个并发 bug，又恰好到很晚(比如文件系统等都实现完以后) 才以非确定性的方式暴露出来，灾难就来了：这么大的系统，你可能不会想到问题出在先前实验的模块。大家毕业以后就需要脱离 Online Judge，去实现 “从没人做过的东西”，所以你可能会抱怨 Online Judge 的无情拒绝和冷却时间，但也请坚持住！

🗒️实验要求：使用动态方式管理内存

为了强迫大家使用动态的方式管理大小不同的堆区，我们规定你使用的所有静态内存 (64-bit 模式下的代码、数据、bss) 不能超过 1MiB。我们将会在运行之前对内核使用 size 命令进行检查，并拒绝过大的 kernel。管理堆区的数据结构应当在堆区中而不是静态区中进行分配。

3.1 测试用例说明

我们会使用来自类似于真实操作系统系统内核的多处理器内存分配/回收 workload 来测试大家的程序。我们的内存分配：

• 不超过 8 个处理器、不少于 64 MiB、不多于 4 GiB 内存的堆区；
• 大量、频繁的小内存分配/释放；其中绝大部分不超过 128 字节；
• 较为频繁的，以物理页面大小为单位的分配/释放 (4 KiB)；
• 非常罕见的大内存分配。

我们预期你的 kalloc/kfree 具有足够的 robustness，足以承载操作系统内核的实现:

1. Safety: 我们预期你的 kalloc/kfree 实现是正确的。一旦以下情况发生，将被立即被 Online Judge 判定为错误：
   • 虚拟机重启、crash、测试代码中的 assert fail 等 (通常由 undefined behavior 触发，例如数据竞争)
   • kalloc 的返回值不满足 API 规约，例如分配的内存不位于堆区、错误的内存对齐等
   • kalloc 返回一段尚未被 kfree 的内存
2. Liveness: 我们还需要系统有一定的 liveness，即系统中有充足剩余内存时，内存分配不应过于频繁的频繁失败。这是为了防止你为了 safety 进行一些 “投机取巧”：对所有 kalloc 都返回 NULL，safety trivially 被满足。
   • liveness 并不是一个 “硬性” 的要求。在合理的 workload 上，你程序的表现只要不比一个 (实现得非常一般) 的 baseline 差太多 (你依然允许在某些你认为无法满足的 kalloc 上返回 NULL)，就会被判定为正确

与 L0 类似，我们会链接我们 klib 的参考实现，因此你不必担心你的 klib 有些许问题；但你要保持 klib 库函数的行为与 libc 一致。注意 native 会链接系统本地的 glibc (而非 klib)。

⚠️难度、策略与 Academic Integrity

首次接触并发编程的同学会感到高性能的实现有一定难度——不用着急，从 “总是正确” 的实现开始慢慢改进。甚至，如果你觉得能力实在有限，可以从 “不实现” kfree 开始:

static void kfree(void *ptr) {}

这样 kalloc 的实现就非常简单了——简单到只需要维护一个指针即可，依然能确保有 easy tests 通过，并且可以继续后续的实验，获得后续实验的部分分数。我们不严格禁止这样的实现，而且你会发现，如果内存充足，你之后编写的操作系统依然是可以运行的 (只是运行一段时间以后，就会 out of memory 无法再运行下去，会影响后续实验测试用例的得分)。

3.2 Online Judge 运行测试代码的方式

⚠️framework/代码会被我们替换

我们会使用我们 framework/main.c 的代码，但保持你 src/ 目录下的文件不变。测试时，我们会改变 mpe_init 的入口(不再从 os->run 开始执行，而是直接运行测试的 workload)。因此你必须在 os->init() 中完成所有必要的初始化，例如调用pmm->init()。

以下是一个我们测试代码的例子，它会不断生成随机的 kalloc/kfree 请求 (你可以假设我们的生成器总是生成合法的请求，例如不会发生 double-free 等)，并且检查 kalloc/kfree 返回结果的合法性；当检测到问题后会 assert fail 退出，然后你可能会得到 “Runtime Error”。

#include <common.h>
#include <klib.h>

enum ops { OP_ALLOC = 1, OP_FREE };

struct malloc_op {
 enum ops type;
 union {
     size_t sz;  // OP_ALLOC: size
     void *addr; // OP_FREE: address
 };
};

void stress_test() {
 while (1) {
     // 根据 workload 生成操作
     struct malloc_op op = random_op();

     switch (op.type) {
         case OP_ALLOC: {
             void *ptr = pmm->alloc(op.sz);
             alloc_check(ptr, op.sz);
             break;
         }
         case OP_FREE:
             free(op.addr);
             break;
     }
 }
}

int main() {
 os->init();
 mpe_init(stress_test);
}

我们鼓励你参考上面的方式 (或者用你想到的任何方式)，实现自己的压力测试。

4. 实验指南

4.1. 代码组织与运行

实验框架代码由三个目录组成：

.
├── framework  -> 框架代码；可以在本地修改，但 Online Judge 评测时会被替换成我们的版本
│   ├── kernel.h
│   └── main.c
├── include    -> 头文件；可以自由修改/创建文件 (Online Judge 会复制)
│   └── common.h
├── Makefile
└── src        -> 源文件；可以自由修改/创建文件 (Online Judge 会复制)
    ├── os.c
    └── pmm.c

理解框架代码的编译，最好的办法是看 Makefile 啦。在课堂上我们已经讲解了如何阅读 Makefile (大家可以查看视频回看)，并讲解了镜像的生成过程。好奇操作系统是如何被 “编译” 出来的？如果觉得阅读 Makefile (和里面奇奇怪怪的语法) 有点困难，我们不妨把 make 工具的执行也想象成是状态机——没错，程序就是状态机，而我们如果观测这个状态机的执行，我们最关心的当然是 make 工具执行的所有命令了，因为是这些命令产生了我们编译出的 .o 文件、链接得到的 ELF 二进制文件，以及我们的操作系统镜像。

GNU make 自然为我们提供了这个功能：

$ make -nB # RTFM!
... (完全不可读的输出)

但如果你稍稍对输出做一些处理

make -nB | grep -v '^mkdir' | vim -

并且在 Vim 里做一些你舒适的文本处理，例如 :%s/^/\r 在命令之间插入空行；:%s/ /\r /g 将命令的参数缩进排版……你很快就会得到 “可读” 的代码，例如编译一个 .c 文件的命令：

x86_64-linux-gnu-gcc
  -std=gnu11 -O2
  -MMD -Wall -Werror -ggdb
  -Iinclude/ -Iframework/ -I$KERNEL/include -I$AM/am/include/ -I$AM/klib/include/
  -D__ISA__=\"x86_64\"
  -D__ISA_X86_64__
  -D__ARCH__=x86_64-qemu
  -D__ARCH_X86_64_QEMU
  -D__PLATFORM__=qemu
  -D__PLATFORM_QEMU
  -DARCH_H=\"arch/x86_64-qemu.h\"
  -fno-asynchronous-unwind-tables -fno-builtin -fno-stack-protector -Wno-main -m64 -fPIC -mno-sse
  -c -o $BUILD/x86_64-qemu/framework/main.o
  $KERNEL/framework/main.c

链接生成 ELF 文件的命令：

x86_64-linux-gnu-ld
  -melf_x86_64 -N
  -Ttext-segment=0x00100000
  -o $BUILD/kernel-x86_64-qemu.elf
  $BUILD/x86_64-qemu/framework/main.o
  $BUILD/x86_64-qemu/./src/pmm.o
  $BUILD/x86_64-qemu/./src/os.o
  $AM/am/build/am-x86_64-qemu.a
  $AM/klib/build/klib-x86_64-qemu.a

以及最终生成可运行的磁盘镜像的过程：

( cat $AM/am/src/x86/qemu/boot/bootblock.o;
  head -c 1024 /dev/zero;
  cat $BUILD/kernel-x86_64-qemu.elf
) > $BUILD/kernel-x86_64-qemu

哇哦！操作系统好像也没有那么可怕了。真的是《计算机系统基础》课上学过的编译-链接，对照着手册，就能知道个大概了 (个别参数的具体含义也并不需要理解得非常清楚，只需要知道这些是用于编译出一个 “不借助操作系统” 能直接运行在硬件上的程序的就够了)。

使用 make run 编译运行，你将会看到一个处理器输出 Hello World：

$ make run ARCH=x86_64-qemu
# Building kernel-image [x86_64-qemu]
...
Got 125 MiB heap: [0x300000, 0x8000000)
Hello World from CPU #0

如果要启动多个处理器，可以为 make run 传递 smp 环境变量，例如 smp=2 代表启动 2 个处理器；smp=4 代表启动 4 个处理器：

$ make run ARCH=x86_64 smp=4
...
Got 125 MiB heap: [0x300000, 0x8000000)
Hello World from CPU #1
Hello World from CPU #2
Hello World from CPU #3
Hello World from CPU #0

4.2. 框架代码导读

框架代码很短，它的 main 函数首先执行 os 的初始化，然后启动多个处理器，每个处理器都跳转到 os->run 执行：

int main() {
  int main() {
  os->init();
  mpe_init(os->run);
  return 1;
}

os 是一个操作系统的 “模块”，可以看成是我们用 C 实现的面向对象编程，能增加代码的可读性。整个框架代码中唯一有些难以理解的部分就是模块的声明和定义 (framework/kernel.h)：

#define MODULE(mod) \
  typedef struct mod_##mod##_t mod_##mod##_t; \
  extern mod_##mod##_t *mod; \
  struct mod_##mod##_t

#define MODULE_DEF(mod) \
  extern mod_##mod##_t __##mod##_obj; \
  mod_##mod##_t *mod = &__##mod##_obj; \
  mod_##mod##_t __##mod##_obj

我们用 MODULE 声明一个模块，用 MODULE_DEF 实际定义它。

这个宏的视觉效果很差，为了阅读它，大家不妨可以在刚才看到的编译命令中把 -c -o ... 替换成 -E，就得到了预编译后的代码：

typedef struct mod_os_t mod_os_t;
extern mod_os_t *os;
struct mod_os_t {
  void (*init)();
  void (*run)();
};

...

extern mod_os_t __os_obj;
mod_os_t *os = &__os_obj;
mod_os_t __os_obj = {
  .init = os_init,
  .run = os_run,
};

然后你就可以对照着阅读预编译的代码 (用对了方法，也就没有那么难了)，只需要记住以下两点：

1. 宏是字面替换，MODULE(mod) 中所有的 “mod” 都会被替换掉；
2. ## 是 C 语言用来拼接标识符的机制，sys ## tem 将会得到 system;

如果你阅读上述代码感到障碍，你可能需要补充：(1) typedef 类型别名定义, (2) extern 关键字, (3) C11 结构体初始化的知识。另外，下划线 _ 也可以是标识符的一部分。随着实验的进展，你会发现模块机制清晰地勾勒出了操作系统中各个部分以及它们之间的交互，能够帮助大家更好地理解操作系统的实现原理。

4.3. 框架代码的执行

好消息：实验做出的简化

在这个实验中，我们只启动了 AbstractMachine 中的 TRM 和 MPE，因此你不必考虑中断和多处理器同时带来的诸多麻烦 (下一个实验才开始考虑)。你不妨把每个处理器想象成一个线程。

我们的操作系统内核，目前只有两个函数：

• os->init() 完成操作系统所有部分的初始化。os->init() 运行在系统启动后的第一个处理器上，中断处于关闭状态；此时系统中的其他处理器尚未被启动。因此在 os->init 的实现中，你完全不必考虑数据竞争等多处理器上的问题。
• os->run() 是所有处理器的入口，在初始化完成后，框架代码调用 _mpe_init(os->run) 启动所有处理器执行。框架代码中，os->run 只是打印 Hello World 之后就开始死循环；你之后可以在 os->run 中添加各种测试代码。

所以就想象成是你的 os->run() 就是 threads.h 里创建的一个线程，仅此而已！

4.4. 实现 kalloc/kfree

我们的实现主要在 pmm (physical memory management) 模块：

MODULE(pmm) {
  void  (*init)();
  void *(*alloc)(size_t size);
  void  (*free)(void *ptr);
};

模块包含三个函数指针：

• pmm->init() 初始化 pmm 模块，它应当在多处理器启动前 (os->init() 中) 调用。你会在这里完成数据结构、锁的初始化等；
• pmm->alloc() 对应实验要求中的 kalloc；
• pmm->free() 对应实验要求中的 kfree。

框架代码中包含了 “空的” pmm 实现，它对任何内存分配的请求都返回失败，因此它满足 safety，但完全没有 liveness，仿佛堆区的大小为零：

static void *kalloc(size_t size) { return NULL; }
static void kfree(void *ptr) { } 
static void pmm_init() { } 
MODULE_DEF(pmm) = {
  .init  = pmm_init,
  .alloc = kalloc,
  .free  = kfree,
};

思考题：static 函数

为什么 kalloc/kfree/pmm_init 声明成了 static？我把 static 去掉依然可以编译呀？

这是一个好的编程习惯，在 C 这样缺少 module/package/namespace 机制的编程语言上有效减少意外发生。

我们在讲解 “并发数据结构” 时讲解了 kalloc/free 的算法和实现。你应该阅读：

• 教科书第 29 章 (并发数据结构)，学习如何对数据结构进行并发控制；
• 教科书第 17 章 (空闲空间管理)，学习如何管理物理内存；
• 互联网上的其他资料。如果你希望了解现代 malloc 实现，你可以参考来自两个代码巨头的设计：Google 的 tcmalloc 和 Microsoft 的 mimalloc。

4.5. 测试/调试你的代码

4.5.1. 做一个测试框架

AbstractMachine 代码的调试并不容易——不论是 native 还是运行在模拟器里，AM APIs 都和系统有紧密的耦合。大家有没有想过，你们的代码是否可以链接 threads.h 直接运行测试呢？答案当然是肯定的！在这个实验里，做一个测试框架对你找到 bug 其实是非常有用的。

你可以创建一个 test 目录，用于存放和测试相关的代码，例如我们提供的 threads.h:

$ tree test 
test
├── am.h # 一个空的 am.h
├── common.h
├── test.c
└── threads.h # 上课时给出的代码

除此之外，所有的操作系统/框架代码等都和之前保持一致——我们通过最小的、非侵入式的项目修改确保你在任何时候都可以通过 make submit 直接提交代码而不需要做出任何额外的修改。这些自动工具/代码框架对于做实验 (包括做 Online Judge) 都是非常值得的。

为了让我们的代码能够兼容，你可以需要增加一些条件编译，例如，在 pmm.c 中，虽然你的 kalloc 和 kfree 的实现可以保持不变，但初始化代码则需要不同：

#ifndef TEST
// 框架代码中的 pmm_init (在 AbstractMachine 中运行)
static void pmm_init() {
  uintptr_t pmsize = ((uintptr_t)heap.end - (uintptr_t)heap.start);
  printf("Got %d MiB heap: [%p, %p)\n", pmsize >> 20, heap.start, heap.end);
}
#else
// 测试代码的 pmm_init ()
static void pmm_init() {
  char *ptr  = malloc(HEAP_SIZE);
  heap.start = ptr;
  heap.end   = ptr + HEAP_SIZE;
  printf("Got %d MiB heap: [%p, %p)\n", HEAP_SIZE >> 20, heap.start, heap.end);
}
#endif

在你相应完成两个不同环境的条件编译后，在你的 Makefile 里增加一个编译目标 (我们添加了 git 的依赖，使得你的提交被正确追踪)：

test: git
        @gcc $(shell find src/ -name "*.c")  \
             $(shell find test/ -name "*.c") \
             -Iframework -Itest -DTEST -lpthread \
             -o build/test
        @build/test

然后就可以愉快地写测试代码啦 (test.c):

static void entry(int tid) { pmm->alloc(128); }
static void goodbye()      { printf("End.\n"); }
int main() {
  pmm->init();
  for (int i = 0; i < 4; i++)
    create(entry);
  join(goodbye);
}

把时间投资在框架建设上

你可能需要花一点时间才能完成 make 和 make test 共用同一份 kalloc/kfree 代码的框架。但这绝对是值得的。一旦完成，直接测试/调试本地代码的好处是巨大的——它节省了编译、运行、调试……整个开发流程的 overhead。任何想用 “蛮力” 把实验糊弄过去都将导致巨大的时间浪费。

4.5.2. 设计测试用例

如果不想被 Online Judge 折磨得死去活来，你应当设计一个自己的测试框架，尝试不同类型的测试，例如：

• 针对数据结构的单元测试；
• 最基本的 smoke test，测试单线程版本是否正确；
• 基本的并发测试，例如多个处理器并发地分配 (但不回收)；
• 针对回收专门设计的测试；
• 极端情况下的压力测试 (我们会这么做！)
  • 在多个处理器上模拟各种不同类型的内存访问模式
    • 频繁的小内存申请；
    • 频繁的大内存申请；
    • 混合的内存申请；
    • 多处理器竞争的申请/释放……
  • 你还需要有个办法验证你的 kalloc/free 是否正确
    • 一个可行的方案是，每次分配/释放都用 printf 打印一条记录，然后再写一个小脚本解析记录，确保例如同一段内存没有被分配给两个 kalloc。

这时候，代码框架的威力就显示出来了！你可以很容易地批量运行很多测试，例如

int main(int argc, char *argv[]) {
  if (argc < 2) exit(1);
  switch(atoi(argv[1])) {
    case 0: do_test_0();
    case 1: do_test_1();
    ...
  }
}

然后在你的 Makefile 里批量运行它们：

testall: test
        @build/test 0
        @build/test 1
        @build/test 2
        ...

警惕并发

很可能你的顺序测试完全通过，但多处理器跑起来就挂了。不要慌，多加点 printf logs，慢慢诊断可能的问题。然后你可能会惊奇地发现，也许加了一个 printf，错误就不见了。此时的建议是调整 workloads、增加延迟等保证 bug 的稳定再现，然后再进行诊断。如果你希望实现各种 fancy 的算法，不妨从一把大锁保护 kalloc/free 开始。这是个不错的主意——这样你一开始就只需要关注单线程 kalloc/free 的正确性。当你需要性能的时候，再逐步把锁拆开。

4.5.3 性能调优

抛开 workload 谈优化，就是耍流氓

Premature optimization is the root of all evil. —— D. E. Knuth

要考虑好你优化的场景，否则一切都是空谈。

你需要选取适当的 workload 进行调优，并且理解你程序的性能瓶颈在哪里。这时候，靠 “猜” 和随机修改程序以获得性能提升的方式是不专业的表现。理解程序性能的最好方法是使用正确的工具：profiler。作为本地进程运行的测试用例也能更容易地 profile——你可以用 Linux 系统自带的各种工具找到你实现的性能瓶颈。当然，这个实验对性能的要求并不高，大家体验一下即可。

当然，这个实验给大家的剧透是：如果数据结构选择得不太差，性能瓶颈就主要在于多个线程并发访问时的互斥，由于多个线程都需要获得同一把锁，就会出现 “一核出力、他人围观” 的情况。正如课本上所说，现代 malloc/free 实现的主要思想就是区分 fast/slow path，使得 fast path 分配在线程本地完成，从而不会造成锁的争抢。你也可以为每个 CPU 分配页面的缓存——可以借鉴 slab，也可以预先把页面分配给 CPU，在内存不足时再上锁从其他 CPU “偷取” 页面。

5. 操作系统中的内存管理

很多现代编程语言都运行在自动管理内存的的运行时环境上：Java, Python, Javascript, …它们的特点是：没有 raw pointer，也没有 API 用于 “释放” 内存。当一个对象从一系列的 root objects (例如栈上的局部变量、全局变量等……) 通过引用关系不可达，它们就会自动被运行时环境回收。这真是程序员的福音——再也没有 use-after-free, double-free 等问题了，memory leak 的可能性也大大降低 (虽然依然可能会有)。

当然，自动内存管理带来的问题是内存回收是个 highly non-trivial 的问题，至今仍然不能算彻底完美地解决，生产系统依然经常受到垃圾回收 (回收不可达对象) 停顿/降低性能的困扰。由于操作系统的性能至关重要，让垃圾回收占据处理器运行似乎不是个好主意……未必！

• 阅读材料：Cody Cutler, M. Frans Kaashoek, and Robert T. Morris. The benefits and costs of writing a POSIX kernel in a high-level language. In Proc. of OSDI , 2018. (硬核/专业人士警告)

当然，操作系统内核的有趣故事也没有停过：

• Kevin Boos, Namitha Liyanage, Ramla Ijaz, and Lin Zhong. Theseus: An experiment in operating system structure and state management. In Proc. of OSDI , 2020.

谨慎使用动态内存分配

如果你没有写过相当规模的程序，在对象的种类增加时，内存管理会带来相当麻烦。 对于对迷你自制操作系统来说，用固定大小的数组管理对象是一个好办法 (xv6 中就经常这么做)，分类管理的对象 (而不是混在一个全局的 “池子” 里) 对调试更友好，而且对象的大小通常有限，如果存在泄漏也很容易触发。