分时多任务

上下文切换

我们已经可以让用户程序运行在相互独立的虚拟地址空间上了, 我们只需要再加入上下文切换的机制, 就可以实现一个真正的分时多任务操作系统了! 所谓上下文, 其实可以看作是程序运行时候的状态. 聪明的你应该马上能想起来, 我们在PA3中遇到的陷阱帧, 不就正好保存了程序的状态了吗? 没错, 要实现上下文切换, 就是要实现在不同程序的陷阱帧之间的切换!

具体地, 假设程序A运行的过程中触发了系统调用, 陷入到内核. 根据asm_trap()的代码, A的陷阱帧将会被保存到A的堆栈上. 本来系统调用处理完毕之后, asm_trap()会根据A的陷阱帧恢复A的现场. 神奇的地方来了, 如果我们先不着急恢复A的现场, 而是先将栈顶指针切换到另一个程序B的堆栈上, 接下来的恢复现场操作将会恢复成B的现场: 恢复B的通用寄存器, 弹出#irq和错误码, 恢复B的EIP, CS, EFLAGS. 从asm_trap()返回之后, 我们已经在运行程序B了!

那程序A到哪里去了呢? 别担心, 它只是被暂时"挂起"了而已. 在被挂起之前, 它已经把现场的信息保存在自己的堆栈上了, 如果将来的某一时刻栈顶指针被切换到A的堆栈上, 代码将会根据A的"陷阱帧"恢复A的现场, A将得以唤醒并执行. 所以, 上下文切换其实就是不同程序之间的堆栈切换!

我们只要稍稍借助数学归纳法, 就可以让我们相信这个过程对于正在运行的程序来说总是正确的. 那么, 对于刚刚加载完的程序, 我们要怎么切换到它来让它运行起来呢? 答案很简单, 我们只需要在程序的堆栈上人工初始化一个陷阱帧, 使得将来切换的时候可以根据这个人工陷阱帧来正确地恢复现场即可.

在讨论具体如何初始化陷阱帧之前, 我们先来看一个关键的问题: 我们要如何找到别的程序的陷阱帧呢? 注意到陷阱帧是在堆栈上的形成的, 但堆栈那么大, 受到函数调用形成的栈帧的影响, 每次形成陷阱帧的位置并不是固定的. 自然地, 我们需要一个指针tf来记录陷阱帧的位置, 当想要找到别的程序的陷阱帧的时候, 只要寻找这个程序相关的tf指针即可.

事实上, 有不少信息都是进程相关的, 除了刚才提到的陷阱帧位置tf之外, 还有我们之前遇到的虚拟地址空间, 以及用户进程堆区的位置. 对于用户进程, 还需要有一个堆栈. 为了方便对进程进行管理, 操作系统使用一种叫进程控制块(PCB, process control block)的数据结构, 为每一个进程维护一个PCB. Nanos-lite的框架代码中已经定义了我们所需要使用的PCB结构(在nanos-lite/include/proc.h中定义):

typedef union {
  uint8_t stack[STACK_SIZE] PG_ALIGN;
  struct {
    _RegSet *tf;
    _Protect as;
    uintptr_t cur_brk;
    uintptr_t max_brk;
  };
} PCB;

Nanos-lite使用一个联合体来把其它信息放置在进程堆栈的底部. 代码为每一个进程分配了一个32KB的堆栈, 已经足够使用了, 不会出现栈溢出导致PCB中的其它信息被覆盖的情况. 在进行上下文切换的时候, 只需要把PCB中的tf指针返回给ASYE的irq_handle()函数即可, 剩余部分的代码会根据上下文信息恢复现场. 在GNU/Linux中, 进程控制块是通过task_struct结构来定义的.

因此, 我们要做的事情, 就是在用户进程的堆栈上初始化一个陷阱帧. 具体来说, 就是如何初始化陷阱帧中的每一个域, 因此你需要仔细思考陷阱帧中的每一个域对一开始运行的用户进程有什么影响. 提醒一下, 为了保证differential testing的正确运行, 我们还是把陷阱帧中的cs设置为8. 这件事情是通过PTE提供的_umake()函数(在nexus-am/am/arch/x86-nemu/src/pte.c中定义)来实现的, 它的原型是

_RegSet *_umake(_Protect *p, _Area ustack, _Area kstack,
  void *entry, char *const argv[], char *const envp[]);

_umake()是专门用来创建用户进程的现场的, 但由于NEMU并没有实现ring 3, Nanos-lite也对用户进程作了一些简化, 因此目前_umake()只需要实现以下功能: 在ustack的底部初始化一个以entry为返回地址的陷阱帧. p是用户进程的虚拟地址空间, 在简化之后, _umake()不需要使用它. argv和envp分别是用户进程的main()函数参数和环境变量, 目前Nanos-lite暂不支持, 因此我们可以忽略它们. 但是, Navy-apps中程序的入口函数是navy-apps/libs/libc/src/start.c中的_start()函数, _start()函数认为它是有参数的, 因此我们还需要在陷阱帧之前设置好_start()函数的栈帧, 这是为了_start()开始执行的时候, 可以访问到正确的栈帧. 我们只需要把这一栈帧中的参数设置为0或NULL即可, 至于返回地址, 我们永远不会从_start()返回, 因此可以不设置它.

因此, _umake()函数需要在栈上初始化如下内容, 然后返回陷阱帧的指针, 由Nanos-lite把这一指针记录到用户进程PCB的tf中:

|               |
+---------------+ <---- ustack.end
|  stack frame  |
|   of _start() |
+---------------+
|               |
|   trap frame  |
|               |
+---------------+ <--+
|               |    |
|               |    |
|               |    |
|               |    |
+---------------+    |
|       tf      | ---+
+---------------+ <---- ustack.start
|               |

我们之前让Nanos-lite在加载用户程序后通过函数调用跳转到用户程序中执行. 事实上, 这并不是一个合理的方式, 从安全的角度来说, 高特权级的代码是不能直接跳转到低特权级的代码中执行的, 真实硬件的保护机制甚至会抛出异常来阻止这种情况的发生. 合理的做法是, 当操作系统初始化工作结束之后, 就会通过自陷指令触发一次上下文切换, 切换到第一个用户程序中来执行. 真实的操作系统就是这样做的.

为了测试_umake()的正确性, 我们也先通过自陷的方式触发第一次上下文切换. 内核自陷的功能与ISA相关, 是由ASYE的_trap()函数提供的. 在x86-nemu的AM中, 我们约定内核自陷通过指令int $0x81触发. ASYE的irq_handle()函数发现触发了内核自陷之后, 会包装成一个_EVENT_TRAP事件. Nanos-lite收到这个事件之后, 就可以返回第一个用户程序的现场了.

上下文切换只是AM的工作, 而具体切换到哪个进程的上下文, 是由操作系统来决定的, 这项任务叫做进程调度. 进程调度是由schedule()函数(在nanos-lite/src/proc.c中定义)来完成的, 它用于返回将要调度的进程的上下文. 因此, 我们需要一种方式来记录当前正在运行哪一个进程, 这样我们才能在schedule()中返回另一个进程的现场, 以实现多任务的效果. 这一工作是通过current指针(在nanos-lite/src/proc.c中定义)实现的, 它用于指向当前运行进程的PCB. 这样, 我们就可以在schedule()中通过current来决定接下来要调度哪一个进程了. 不过在调度之前, 我们还需要把当前进程的上下文信息的位置保存在PCB当中:

// save the context pointer
current->tf = prev;

// always select pcb[0] as the new process
current = &pcb[0];

// TODO: switch to the new address space,
// then return the new context

目前schedule()只需要总是切换到第一个用户进程即可, 即pcb[0]. 注意它的上下文是在加载程序的时候通过_umake()创建的, 在schedule()中才决定要切换到它, 然后在ASYE的asm_trap()中才真正地恢复这一上下文. 在schedule()返回之前, 还需要切换到新进程的虚拟地址空间. 这样, 等到从异常处理的代码返回之后, 我们就已经正确地在仙剑奇侠传的虚拟地址空间中运行仙剑奇侠传的代码了!

分时多任务

我们已经实现了虚拟内存和上下文切换机制, Nanos-lite已经能支持分时多任务了! 这时候, 我们就可以加载第二个用户程序了:

--- nanos-lite/src/main.c
+++ nanos-lite/src/main.c
@@ -33,3 +33,4 @@
   load_prog("/bin/pal");
+  load_prog("/bin/hello");

   _trap();

我们让仙剑奇侠传和hello程序分时运行. 需要注意的是, 我们目前只允许最多一个需要更新画面的进程参与调度, 这是因为多个这样的进程分时运行会导致画面被相互覆盖, 影响画面输出的效果. 在真正的图形界面操作系统中, 通常由一个窗口管理进程来统一管理画面的显示, 需要显示画面的进程与这一管理进程进行通信, 来实现更新画面的目的. 但这需要操作系统支持进程间通信的机制, 这已经超出了ICS的范围, 而且Nanos-lite作为一个裁剪版的操作系统, 也不提供进程间通信的服务. 因此我们进行了简化, 最多只允许一个需要更新画面的进程参与调度即可.

为此, 我们还需要修改调度的代码, 让schedule()轮流返回仙剑奇侠传和hello的现场:

current = (current == &pcb[0] ? &pcb[1] : &pcb[0]);

最后, 我们还需要选择一个时机来触发进程调度. 目前比较合适的时机就是处理系统调用之后: 修改do_event()的代码, 在处理完系统调用之后, 调用schedule()函数并返回其现场.

但我们会发现, 和hello程序分时运行之后, 仙剑奇侠传的运行速度有了明显的下降. 这其实再次向我们展现了"分时"的本质: 程序之间只是轮流使用处理器, 它们并不是真正意义上的"同时"运行. 为了让仙剑奇侠传尽量保持原来的性能, 我们可以在调度的时候进行一些修改.