L0-hello, bare metal!

没有任何难度。

主要是我想说一下我的离谱实现：直接显示大色块，反正通过了（

除此之外还实现了 klib 的一些函数，包含一个简易版的 printf，支持除了浮点运算之外的一些基础功能。学到的教训是：在下手写代码之前，要先想好代码的架构，尽可能执行DRY原则，也可以防止为了达成DRY而频繁地修改主要函数的接口。

L1 - pmm

个人感想

  • 思维难度：⭐⭐⭐
  • 代码难度：⭐⭐⭐⭐
  • 消耗时长：⭐⭐⭐⭐⭐⭐
    对「一开始先使用一个简单有效的设计」这句话深有感触了，因为不然真的会「陷入Wrong Answer的泥潭」；总共改了 $3$ 版设计，累计写了三四千行代码；算法越改越简单，代码越改越少，通过的点越改越多。

这是我这辈子交过的最痛苦的OJ：

这是最好的一次：

得分情况

通过了所有 Easy Test 和 3 个 Hard Test。最后一个 Hard Test 由于 Kalloc fail on low memory pressure 未通过。

基本设计

在目前提交的版本中，我的设计如下：

  • 将所有空间以页为单位进行种类的划分，分别是：slab 页、缓存页、全局页。
  • 在初始状态下，每个 cpu 得到一些缓存页，剩余全部为全局页，不存在 slab 页。
  • 申请的顺序为：先申请 slab 页，若失败则再申请缓存页，若失败则最后申请全局页。
  • 当进行 alloc 请求时，根据申请空间的大小决定申请入口。若申请空间不足1页，则从 slab 页开始申请；若恰好为1页，则从缓存页开始申请；若大于1页，则直接申请全局页。
  • 当进行 free 请求时，首先判断其是否来自 slab 页，判断方法为检查 ptr 是否与页框对齐（在分配时保证非整页的分配一定不与页框对齐）。若其来自 slab 页，则归还到 slab 中；反之直接归还到调用 free 的 cpu 的缓存页。因此全局页会不断变少。

slab页机制：

  • 一个 slab 页会固定按照一个大小进行划分。根据 slab_size 的不同，每个 cpu 都会保存一系列当前正在使用的 slab 页。
  • slab 页在它整个生命周期中顺序地向后分配它掌握的内存。提前归还的内存不会重新分配。
  • 当一个 slab 页所有内存全部被分配后，它会下线；当所有内存全部归还后，它会被回收至最后一次调用 free 的 cpu 的缓存页中。
  • 当一个 cpu 目前缺少对应大小的 slab 页，但又需要分配它时，它会首先尝试从自己的缓存页中拿出一页变为目标 slab 页并初始化；若该操作失败，则会再从全局页中拿出一个页变为目标 slab 页并初始化。
  • 由于 slab 的获取和 slab 的归还操作的是不同的变量，因此可以将 slab 的锁拆开，使得对于同一 slab 的获取和归还可以并发进行。
  • slab 页的结构体中，前 128B 用作元数据不进行分配。这为 free 判断内存来源提供了便利（当 free 接受的指针与4096对齐时，则来源一定不为 slab 页，否则来源一定是 slab 页）。
  • 以下是 slab 的结构体声明：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    typedef union slab_page {
        struct {
            int slab_size;
            int capacity;
            int item_head;
            int cnt_used;
            int cnt_returned;
            int is_online;
            spinlock_t lock;
            spinlock_t ret_lock;
        };
        uint8_t data[PAGE_SIZE];
    } slab_page;

缓存页与全局页机制：

  • 一个 cpu 所拥有的所有缓存页使用一个单向链表维护。
  • 全局页的实现较为简陋：维护一个指针，当需要分配时，将指针跳转到相应位置。这会在频繁需要对齐时产生较大浪费；但是当大内存分配非常罕见时，该方法在分配时不会造成过大浪费；尤其是当申请一个页时，可以做到 100% 的返还率，且返还到 cpu 的缓存页中，为之后再次分配降低开销。
  • 另外实现了使用块状链表的全局页分配方法。由于效率过低最后没有采纳。

印象深刻的 bug

  • 在 2023 年的实验报告中，提到不会存在频繁的 >128B 但不足 4096B 的分配。该约定在今年的 OJ 上完全不成立。由于我将 slab 页的大小设置为 4B~128B，导致略微超过 128B 的请求全部得到了一整个页，导致一直出现 kalloc failed on low memory pressure。

L2 - kmt

个人感想

  • 思维难度：⭐⭐⭐⭐
  • 代码难度：⭐⭐
  • 消耗时间：⭐⭐⭐
    是一个比较符合我对「操作系统实验」想象的实验；把一开始的设计做好之后，代码一晚上就敲完了；最后 CPU Starvation 怎么也没查出来原因，本地测试是能够公平调度的，可能是一些 Corner Case 卡住了。

期末考完就一直在算：假设期中期末能拿到 $85%$ 的分，我L2不同的完成程度会带来怎样的总评。在不断回忆L1的痛苦折磨时，还是和自己和解了：只要能过 Easy Test 就算过了。所以第一次（有效的提交）交出 $4/5$ 还是挺开心的。只是没想到最后一个点这么难调……

得分情况

通过了所有 Easy Test 和 2 个 Hard Test。最后一个 Hard Test 由于 CPU starvation 未通过。

基本设计

自旋锁与pmm模块的修改

仿照xv6的代码，让自旋锁提供了 push_off 和 pop_off 的功能，使得上锁过程中中断一定处于关闭状态。

kmt模块和中断模块

任何调度（包括：KMT对于进程的调度、信号量对于睡眠进程的调度与唤醒）的最小单位都是 task，其结构体定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct task {
    union {
        struct {
            int pid;
            int cpu;
            int status;
            
            const char *name;
            void (*entry)(void*);
            void *arg;
            Context *context;

            struct task *blocked_next;
            struct task *next_task;
            struct task *prev_task;

            uint32_t canary;
        };
        uint8_t data[TASK_SIZE];
    };
} __attribute__((packed)) task_t;

对于KMT的调度：

  • 维护一系列任务链表，任务链表使用 next_task 和 prev_task 表示。
  • 在调度时，每个CPU仅可能被切换到当前任务所在的任务链表中的其他任务。
  • 对于「每个线程绑定在一个CPU上」的设计，为每个CPU单独开一个任务链表。
  • 每个CPU都存在一个空转任务 idle，用于在闲置时进行分配。
  • 朴素的调度器实现是：新建任务时插入到 idle 后方，调度时每次选择当前任务在任务链表中的下一个任务作为目标。

对于信号量的调度：

  • 维护一个等待链表，用于记录正在共同等待同一个信号量的任务，用 blocked_next 表示。
  • 具体见下一节

为了完成以上设计，我设计了 cpustatus 结构体，用于存储每个 CPU 的当前任务和空转任务（静态分配）。

1
2
3
4
5
6
typedef struct cpustatus {
    task_t *current_task;
    task_t idle_task;
    int cpu_task_cnt;
} cpustatus_t;
cpustatus_t cpustat[MAX_CPU];

有关 trap_lk 的设计：

  • 我将中断时任何多处理器可访问内存的读写视为临界区，任何触及 cpustat 的行为、在栈上对上下文的操作、对 task_t 结构变量的修改，都会被 trap_lk 保护。这从根本上保证了并发安全性。
  • 在 kmt 模块中，对上述的操作体现在 kmt_schedule 和 kmt_context_save 时，由于其二者注册为中断处理函数，因此必定从 os_trap 处进行调用。考虑到处理中断本身就需要防止并发，不妨直接在 os_trap 中给 trap_lk 上锁，这把锁同时保护了中断安全和并发安全。这样也就并不需要再在 kmt_schedule 和 kmt_context_save 函数中给 trap_lk 上锁了。

信号量模块

我在信号量的实现中进行了如下设计：

  • 如果一个任务需要在 sem_wait 时等待，就将其加入到该信号量的等待链表中。该链表为单向链表，以 blocked_next 作为前向指针。加入链表后，设置其状态为 STAT_WAIT，而后yield() 出去让出处理器。由于其状态并非 STAT_SLEEP，因此调度器不可能唤醒他。
  • 一个任务在 sem_signal 时会遍历当前信号量的等待链表，并尝试唤醒状态为 STAT_WAIT 的任务。这也是状态为 STAT_WAIT 的任务被唤醒的唯一方式。

一些思考

空转任务需要定义具体的函数入口和初始化Context吗？（也即，idle线程究竟是什么）

  • 不需要。 因为 idle 线程在初始时不会由我们主动进入。我们实际上是在运行 os.c 的 main 函数中的 while(1) { yield(); }，并强行告诉 CPU：你正在运行的这个线程叫做 idle。因此，当 CPU 第一次被中断时，main 中的 while(1) { yield(); } 上下文会被保存到 idle 任务的 Context 中，因此直接使用 NULL 初始化 idle 的参数不会造成影响。

在 os_trap 和 on_irq 的处理时，需要给 irq_handlers 上锁吗？

  • 需要。对 irq_handlers 和 irq_num 的修改明显是临界区。但这里存在重复拿锁导致死锁的问题：我们可能会在 os_trap 的中断处理程序中调用 on_irq 注册新的中断。两种解决办法是：
    • 在 os_trap 中进入中断处理程序前释放 irq_lk，在从处理函数返回后获取 irq_lock
    • 使用类似于多重关中断的机制防止重复拿锁。但这涉及到 holding() 和 spin_lock() 两个语句组合的非原子性，实现起来每个“可嵌套锁”都需要另一个基础的锁来保护这里的原子性，较为复杂。

在 os_trap 中，需要关中断吗？

  • 直觉上需要：在处理中断时再次被中断会导致很糟糕的后果。
  • 但经过实验，在 os_trap 内部一直处于关中断模式。我没有扒出来具体的代码，但应该是框架代码在调用 os_trap 前进行了关中断的操作。

印象深刻的bug

  • （非常建议明年修改/给出更详细的建议） 我认为让 L2 通过编译比通过前4个Tests难多了（（（
    • 由于我新建了一个 common.h 用于存放所有的定义，这导致 os.h 里面除了一个 #include <common.h> 以外啥都没有。建议以后直接在 L0 下发时给出 os.h，推荐同学们在其中实现定义，降低这种迷惑代码出现的可能性。
    • 我使用 guard 避免了 common.h 里重复定义的报错，这顺带解决了 kernel.h ：仅在 common.h 的 guard 范围内去 #include <kernel.h> 即可。这也给出了一种不能控制头文件下，使用 guard 的思路：新建一个 kernel_wrapper.h，里面是使用 guard 的 #include <kernel.h>，所有需要引用 kernel.h 的地方全部改成 kernel_wrapper.h 即可。
    • 框架代码没有给出评测机可能会替换的 main.c 的样例，我不清楚他是否会 #include <os.h>，（当然大部分原因也是我使用不熟练）导致我花了很长时间在本地自我内耗，尝试在不 #include <os.h> 的前提下，让 main.c 中定义的 static sem_t sem 能够通过编译。
  • 我延续 L0/L1 的代码保留了开机时 Hello World From CPU #%d 的输出，评测机一直报错 thread starvation，删去该输出后即可正常评测。
  • 发现了一个并发bug（已解决，这压根就不是bug）：在tty里按住Ctrl+C不放，然后尝试按Alt+2切换tty，会稳定触发直接黑屏，但是不会死机（仍然有调度）；继续按住Ctrl+C，然后按Alt+1可以切回去，后面恢复正常。但我对自己的操作系统压测没测出问题。后来发现 Alt+Ctrl+1/2 是 qemu 切换视频输入信号的快捷键……我按了之后会切换一个视图……就顺理成章地黑屏了……