L2: 内核线程管理 (kmt)

Soft Deadline: 同 Hard Deadline
本实验在 L1 代码的基础上完成。但如果你完全没有完成 L1,依然可以合并代码并开始 L2 (例如使用一个非常简单的 kalloc/kfree 实现)。

在命令行中 git pull origin L2 下载框架代码。本次实验提交时,需要设置环境变量 MODULEL2 (如果你将 export 写在了 Makefile 里,需要相应作出修改,否则将提交到过往的实验)。

本次实验的报告直接在 kernel/ 目录下原先的实验报告基础上添加。除非特殊情况,本次实验的实验报告不建议超过 2 页 A4 纸。请在实验报告中描述你在实验中遇到的特别值得一提的事件,例如你代码的架构设计、特别精巧的实现、遇到印象深刻的 bug 等。

⚖️L2 - kmt

请输入 Token 登录。

1. 背景

真正的 “操作系统内核” 开始于课堂上的示例代码 “线程操作系统”:

线程操作系统实现了共享内存的状态机 (线程) 之间的主动和被动切换:在线程执行时中断到来,操作系统代码开始执行并保存处理器运行的寄存器现场;在中断返回时,可以选择任何一个进程/线程已经保存的寄存器现场恢复。在这个实验中,我们扩展 thread-os,实现多处理器操作系统内核中的内核线程 API (就像 pthreads 库,或是课堂上展示的 thread.h)。在完成这个实验后,你就得到了一个可以分时抢占式运行多任务的 “嵌入式操作系统”。

2. 实验描述

2.1 操作系统内核:线程与同步

本次实验在 pmm 的基础上,增加中断和线程管理的功能。和 thread-os 类似,操作系统代码会设置接管中断/系统调用/异常时的回调函数,并且实现线程的生命周期函数以及同步机制。

🗒️更新你的 pmm

本次实验 pmm 模块的接口保持不变 (沿用你上一次的实现即可)。但因为处理器上的线程随时可能被中断,你需要在 Lab1 线程安全的基础上实现中断安全——这可以通过使用类似 xv6 spinlock 的方式实现。

本次实验在 os 模块中新增了 trapon_irq 两个函数,分别是系统中唯一中断/系统调用的入口和中断处理程序的回调注册。

🗒️实验要求:实现 Kernel Multi-threading

本次实验的主要任务是实现 kmt 模块中的函数,你需要完成 struct task, struct spinlock, struct semaphore 的定义,并实现 kmt 的全部 API。

typedef Context *(*handler_t)(Event, Context *);
MODULE(os) {
    void (*init)();
    void (*run)();
    Context *(*trap)(Event ev, Context *context);
    void (*on_irq)(int seq, int event, handler_t handler);
};

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

typedef struct task task_t;
typedef struct spinlock spinlock_t;
typedef struct semaphore sem_t;
MODULE(kmt) {
    void (*init)();
    int  (*create)(task_t *task, const char *name, void (*entry)(void *arg), void *arg);
    void (*teardown)(task_t *task);
    void (*spin_init)(spinlock_t *lk, const char *name);
    void (*spin_lock)(spinlock_t *lk);
    void (*spin_unlock)(spinlock_t *lk);
    void (*sem_init)(sem_t *sem, const char *name, int value);
    void (*sem_wait)(sem_t *sem);
    void (*sem_signal)(sem_t *sem);
};

2.2 OS (Operating Systems) 模块

框架代码的 main 函数发生了一些修改:

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

在上一个实验中,框架代码在 os->init() 后直接 mpe->init() 启动多个线程运行内存分配/回收。框架代码中的 ioe_init 和 cte_init 是本次实验新加入的,调用它们并不会立即生效——此时处理器的中断处于关闭状态,除非执行非法操作,否则 os->trap 不会被调用。

虽然你不能修改框架代码 (或者说你可以修改,但提交到 Online Judge 后,会被替换),但你可以控制 os->init() 的行为,例如,你可能需要在其中执行模块的初始化 (框架代码不会调用模块的初始化): 但你可能会在其中增加 kmt 模块的初始化:

static void os_init() {
    pmm->init();
    kmt->init();
}

os->init() 初始化完成后,mpe_init 会让每个处理器都运行相同的 os->run() 代码。此时,操作系统就真正化身成为了中断处理程序:

🗒️实验要求:实现中断处理和上下文切换

中断、系统调用、异常都会调用 os->trap(ev, context)。中断/异常发生后,AbstractMachine 会将寄存器保存到栈上,我们推荐你对 context 做一个拷贝 (这样容易保证正确性),并用 thread-os 类似的方式实现上下文切换。每个处理器都各自管理中断,os->trap() 也会在多处理之间并行执行,因此你需要用自旋锁保护好其中的共享变量 (小心死锁,并保持中断关闭)。

中断处理程序几乎就是 “整个操作系统”。为了增加代码的可维护性,防止在增加新的功能时都直接去修改 os->trap 的代码,我们提供了中断处理 API:

os->on_irq(seq, event, handler)

调用 os->on_irq 向操作系统内核 “注册” 一个中断处理程序:在 os->trap(ev, ctx) 执行时,当 ev.event (事件编号) 和 event 匹配时,调用 handler(event, ctx);。更多的细节:

  • seq 决定了 handler 被调用的顺序,seq 小的 handler 先被调用。seq 相同的按任意顺序调用;
  • event == EVENT_NULL 时,在任何中断/异常时都调用 handler
  • 我们允许一个且仅一个 handler 返回一个 Context,在中断返回时恢复到这个 conetxt。当多个 handler 都返回 context 时,是 undefined behavior。

os->on_irq 的设计类似于 “面向切面编程” (Aspected-Oriented Programming, AOP) 的设计。我们的 os 模块并不需要知道系统中有多少中断、多少设备驱动程序可能会处理中断,而是让每个需要响应中断的组件:设备驱动、系统调用,甚至是调度器自行注册中断处理程序。

例如,如果我们希望在 I/O 设备发生中断时,向键盘驱动的信号量执行一个 V 操作,我们只需要:

static Context *input_notify(Event ev, Context *context) {
    kmt->sem_signal(&sem_kbdirq); // 在 IO 设备中断到来时,执行 V 操作唤醒一个线程
    return NULL;
}

void input_init() {
    // seq == 100 是随意设置的,我们并不在意何时调用
    os->on_irq(100, EVENT_IRQ_IODEV, input_notify); 
    ...
}

甚至在 jyy 的参考实现中,寄存器现场保存、执行调度程序的代码,也都是用 on_irq 注册的 (尽管你并不必要这么做,可以把这部分代码直接写在 os->trap 中):

// thread.c,线程管理
static void kmt_init() {
    ...
    os->on_irq(INT_MIN, EVENT_NULL, kmt_context_save);   // 总是最先调用
    os->on_irq(INT_MAX, EVENT_NULL, kmt_schedule);       // 总是最后调用
    ...
}

如果上述代码被执行,那么按照注册时的 sequence number 进行调用:

  • 在时钟中断发生时依次调用 kmt_context_save (INT_MIN) 和 kmt_schedule (INT_MAX);
  • 在键盘中断发生时依次调用 kmt_context_save (INT_MIN), input_notify (100), 和 kmt_schedule (INT_MAX)

os->trap() 的实现依然保持简单:

static Context *os_trap(Event ev, Context *ctx) {
    Context *next = NULL;
    for (auto &h: handlers_sorted_by_seq) {
        if (h.event == EVENT_NULL || h.event == ev.event) {
            Context *r = h.handler(ev, ctx);
            panic_on(r && next, "return to multiple contexts");
            if (r) next = r;
        }
    }
    panic_on(!next, "return to NULL context");
    panic_on(sane_context(next), "return to invalid context");
    return next;
}
💡防御性的 Assertions
我们上面的代码中有很多防御性的 assertions——看起来有些多余,但可以逮住一些小错,最大程度保护你们不受伤害——例如在某个罕见的执行路径上,你忘记返回 context,或是 context 已经被损坏,你会得到 assertion failure 而不是虚拟机的神秘重启。你可以考虑一下 `sane_context` 是如何实现的——例如,我们要求 RIP 总是位于代码段。此外,当前的 assert failure 只能打印出失败的位置。如果你写一小段代码,能够打印出 call stack frame,那会极大程度简化你们调试的过程——虽然这不是必须的。

    2.3 PMM (Physical Memory Management) 模块

    pmm 与之前行为一致,但因为它被调用的场景增加了 (并不是每个 CPU 只是连续不断地执行代码,而是 CPU 可能被中断),我们需要稍稍对它进行改进:

    ⚠️实现线程安全的内存分配

    允许任意线程调用 pmm->allocpmm->free。此外,允许在中断处理程序中分配和回收内存。因此简单起见,不允许 pmm->alloc()pmm->free() 被中断。

    小心:如果你在 kmt->init() 的时候调用 pmm->alloc(),此时自旋锁可能还没有完成必要的初始化。

    2.4 KMT (Kernel Multi-Threading) 模块

    2.4.1 模块初始化

    kmt->init() 负责初始化必要的数据,例如分配一些重要的数据结构。我们预期你会在 os->init() 时调用 kmt->init()。整个系统启动只调用一次 kmt->init()

    2.4.2 线程管理

    int  (*create)(task_t *task, const char *name, void (*entry)(void *arg), void *arg);
    void (*teardown)(task_t *task);
    

    其中 create 在系统中创建一个线程 (task_t 应当事先被分配好),这个线程立即就可以被调度执行 (但调用 create 时中断可能处于关闭状态,在打开中断后它才获得被调度执行的权利)。我们假设 create 创建的线程永不返回——但它有可能在永远不会被调度执行的情况下被调用 kmt->teardown 回收。

    teardown 相应回收为线程分配的资源——例如你可能会为 task_t 动态分配内存:

    int kmt_create(task_t *task, const char *name, void (*entry)(void *arg), void *arg) {
        ...
        task->stack = pmm->alloc(STACK_SIZE); // 动态分配内核栈
        ...
    }
    

    这部分的内存需要在 teardown() 时被回收。线程只有在永远不会被调度到处理器上执行的前提下才能被回收。你可以假设回收的时候线程不再持有任何自旋锁或在信号量上等待。

    ⚠️create/teardown: 实现线程安全性

    允许任意线程调用 create/teardown。不会在中断处理程序中调用 create/teardown

    2.4.3 自旋锁

    void (*spin_init)(spinlock_t *lk, const char *name);
    void (*spin_lock)(spinlock_t *lk);
    void (*spin_unlock)(spinlock_t *lk);
    

    lock-unlock 实现保护一段强原子性 (任何其他线程、中断处理程序、其他处理器都不能同时得到同一把锁):

    • 允许在中断处理程序中调用自旋锁;
    • 允许任意在任意处理器的任意线程中调用自旋锁;
    • spin_lock 将会关闭处理器的中断,因此对一个处理器而言,持有任何一个自旋锁之后就不会再发生线程切换;
    • spin_unlock 在解除最后一个当前处理器持有的自旋锁之后,需要将处理器的中断状态恢复。例如在中断处理程序中,中断是关闭的,因此 spin_unlock 不应该打开中断;但在一般的线程中,spin_unlock 后应当恢复处理器的中断。
    ⚠️自旋锁:线程安全、中断安全

    允许任意线程调用 spin_init, spin_lockspin_unlock。中断处理程序允许调用 spin_lockspin_unlock

    2.4.4 信号量

    void (*sem_init)(sem_t *sem, const char *name, int value);
    void (*sem_wait)(sem_t *sem);
    void (*sem_signal)(sem_t *sem);
    

    在信号量初始化时,value 指定了它初始的数值。初始时 value == 1 可以把信号量当互斥锁;初始时 value == 0 可以把信号量作为生产者-消费者缓冲区管理实现。sem_waitsem_signal 分别对应了 P/V 操作。

    • 允许在线程中执行信号量的 sem_wait 操作。在 P 操作执行没有相应资源时,线程将被阻塞 (不再被调度执行)。中断没有对应的线程、不能阻塞,因此不能在中断时调用 sem_wait
    • 允许在任意状态下任意执行 sem_signal,包括任何处理器中的任何线程和任何处理器的任何中断。

    在信号量实现时,大约需要做以下几件事 (任何一本操作系统教材上都会提到类似的实现):

    void sem_wait(sem_t *sem) {
        spin_lock(&sem->lock); // 获得自旋锁
        sem->count--; // 自旋锁保证原子性
        if (...) {
            // 没有资源,需要等待
            ...
            mark_as_not_runnable(current); // 当前线程不能再执行
        }
        spin_unlock(&sem->unlock);
        if (...) {    // 如果 P 失败,不能继续执行
                      // (注意此时可能有线程执行 V 操作)
            yield();  // 引发一次上下文切换
        }
    }
    
    ⚠️信号量:线程安全、中断安全

    允许任意线程调用 sem_init, sem_waitsem_signal。中断处理程序不可睡眠,但可以在中断处理程序中调用 sem_signal

    3. 正确性标准

    (TBD)