多道程序

通过Nanos-lite的支撑, 我们已经在NEMU中成功运行了一个批处理系统, 并把仙剑奇侠传跑起来了! 这说明我们亲自构建的NEMU这个看似简单的机器, 同样能支撑真实程序的运行, 丝毫不逊色于真实的机器! 不过, 这个批处理系统目前还是只能同时运行一个程序, 只有当一个程序结束执行之后, 才会开始执行下一个程序.

这也正是批处理系统的一个缺陷: 如果当前程序正在等待输入输出, 那么整个系统都会因此而停顿. 和CPU的性能相比, 输入输出是非常缓慢的: 以磁盘为例, 磁盘进行一次读写需要花费大约5毫秒的时间, 但对于一个2GHz的CPU来说, 它需要花费10,000,000个周期来等待磁盘操作的完成. 但事实上, 与其让系统陷入无意义的等待, 还不如用这些时间来进行一些有意义的工作. 一个简单的想法就是, 在系统一开始的时候加载多个程序, 然后运行第一个; 当第一个程序需要等待输入输出的时候, 就切换到第二个程序来运行; 当第二个程序也需要等待的时候, 就继续切换到下一个程序来运行, 如此类推.

这就是多道程序(multiprogramming)系统的基本思想. 多道程序的想法看着很简单, 但它也是一种多任务系统, 这是因为它已经包含了多任务系统的基本要素. 换句话说, 要把批处理的Nanos-lite改造成一个多道程序操作系统, 我们只需要实现以下两点就可以了:

• 在内存中可以同时存在多个进程
• 在满足某些条件的情况下, 可以让执行流在这些进程之间切换

第一点的实现很简单, 我们只要让loader把不同的进程加载在不同的内存位置就可以了, 加载进程的过程本质上就是一些内存拷贝的操作, 因此并没有什么困难的地方. 甚至我们可以在Nanos-lite中直接定义一些测试函数来作为程序, 因为程序本质上就是一些有意义的指令序列, 目前我们不必在意这些指令序列到底从哪里来. 不过, 一个需要注意的地方是栈, 我们需要为每个进程分配各自的栈空间.

反而需要深思熟虑的是第二点, 怎么让执行流在进程之间切换表面上看并不是一件直观的事情.

上下文切换

在PA3中, 我们已经提到了操作系统和用户进程之间的执行流切换, 并介绍了"上下文"的概念: 上下文本质上就是进程的状态. 换句话说, 我们现在需要考虑的是, 如何在多个用户进程之间进行上下文切换.

基本原理

事实上, 有了CTE, 我们就有一种很巧妙的方式来实现上下文切换了. 具体地, 假设进程A运行的过程中触发了系统调用, 陷入到内核. 根据asm_trap()的代码, A的上下文结构(_Context)将会被保存到A的栈上. 本来系统调用处理完毕之后, asm_trap()会根据栈上保存的上下文结构来恢复A的上下文. 神奇的地方来了, 如果我们先不着急恢复A的上下文, 而是先将栈顶指针切换到另一个进程B的栈上, 那会发生什么呢? 由于B的栈上存放了之前B保存的上下文结构, 接下来的操作就会根据这一结构来恢复B的上下文: 恢复B的通用寄存器, 弹出#irq和错误码, 恢复B的EIP, CS, EFLAGS. 从asm_trap()返回之后, 我们已经在运行进程B了!

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

进程控制块

但是, 我们要如何找到别的进程的上下文结构呢? 注意到上下文结构是保存在栈上的, 但栈空间那么大, 受到函数调用形成的栈帧的影响, 每次保存上下文结构的位置并不是固定的. 自然地, 我们需要一个cp指针(context pointer)来记录上下文结构的位置, 当想要找到其它进程的上下文结构的时候, 只要寻找这个进程相关的cp指针即可.

事实上, 有不少信息都是进程相关的, 除了刚才提到的上下文指针cp之外, 上文提到的栈空间也是如此. 为了方便对这些进程相关的信息进行管理, 操作系统使用一种叫进程控制块(PCB, process control block)的数据结构, 为每一个进程维护一个PCB. Nanos-lite的框架代码中已经定义了我们所需要使用的PCB结构(在nanos-lite/include/proc.h中定义):

typedef union {
  uint8_t stack[STACK_SIZE] PG_ALIGN;
  struct {
    _Context *cp;
  };
} PCB;

PCB中还定义了其它成员, 目前可以忽略它们, 我们会在将来介绍它们.

Nanos-lite使用一个联合体来把其它信息放置在进程堆栈的底部. 代码为每一个进程分配了一个32KB的堆栈, 已经足够使用了, 不会出现栈溢出导致未定义行为. 在进行上下文切换的时候, 只需要把PCB中的cp指针返回给CTE的irq_handle()函数即可, 剩余部分的代码会根据上下文结构恢复现场. 我们只要稍稍借助数学归纳法, 就可以让我们相信这个过程对于正在运行的进程来说总是正确的.

创建上下文

那么, 对于刚刚加载完的进程, 我们要怎么切换到它来让它运行起来呢? 答案很简单, 我们只需要在进程的栈上人工创建一个上下文结构, 使得将来切换的时候可以根据这个结构来正确地恢复上下文即可. 具体来说, 我们还需要思考如何初始化上下文结构中的每一个成员, 因此我们需要仔细思考这些成员对一开始运行的进程有什么影响. 提醒一下, 为了保证DiffTest的正确运行, 我们还是把上下文结构中的cs设置为8.

创建上下文是通过CTE提供的_kcontext()函数 (在nexus-am/am/arch/x86-nemu/src/cte.c中定义)来实现的, 它的原型是

_Context *_kcontext(_Area stack, void (*entry)(void *), void *arg);

你需要在stack的底部创建一个以entry为返回地址的上下文结构(目前你可以先忽略arg参数). 然后返回这一结构的指针, 由Nanos-lite把这一指针记录到进程PCB的cp中:

|               |
+---------------+ <---- stack.end
|               |
|    context    |
|               |
+---------------+ <--+
|               |    |
|               |    |
|               |    |
|               |    |
+---------------+    |
|       cp      | ---+
+---------------+ <---- stack.start
|               |

进程调度

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

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

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

// then return the new context
return current->cp;

目前我们让schedule()总是切换到第一个用户进程, 即pcb[0]. 注意它的上下文是通过_kcontext()创建的, 在schedule()中才决定要切换到它, 然后在CTE的asm_trap()中才真正地恢复这一上下文.

void init_proc() {
  context_kload(&pcb[0], (void *)hello_fun);
  switch_boot_pcb();
}

创建用户进程上下文

创建用户进程的上下文则需要一些额外的考量. 我们知道, 用户进程的main()函数是有参数的, ABI规定, main()函数的参数需在用户进程开始运行之前要由运行时环境准备好. 为了遵循这一约定, AM额外准备了一个API _ucontext(), 专门用于创建用户进程的上下文. _ucontext()的原型是

_Context *_ucontext(_Protect *p, _Area ustack, _Area kstack, void *entry, void *arg);

其中, 参数p, kstack和arg目前不会用到, 可以忽略它们. 与_kcontext()相比, 除了在栈上创建必要的上下文信息之外, _ucontext()还需要在栈上准备一个栈帧, 用于存放main()函数的参数信息. 这个栈帧将来会被navy-apps/libs/libc/src/platform/crt0.c中的_start()函数使用, 它会把参数信息传给main()函数.

|               |
+---------------+ <---- ustack.end
|  stack frame  |
|   of _start() |
+---------------+
|               |
|    context    |
|               |
+---------------+ <--+
|               |    |
|               |    |
|               |    |
|               |    |
+---------------+    |
|       cp      | ---+
+---------------+ <---- ustack.start
|               |

目前我们只需要把这一栈帧中的参数设置为0或NULL即可, 至于返回地址, 我们永远不会从_start()返回, 因此可以不设置它.

实现_ucontext()后, 我们就可以加载用户进程了. 我们添加一个开机画面进程, 同时修改调度的代码, 让其轮流返回两个进程的上下文:

// init_proc()
context_uload(&pcb[1], "/bin/init");

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

最后, 我们还需要在serial_write(), events_read() 和fb_write()的开头调用_yield(), 来模拟设备访问缓慢的情况. 添加之后, 访问设备时就要进行上下文切换, 从而实现多道程序系统的功能.

-context_kload(&pcb[0], (void *)hello_fun);
+context_uload(&pcb[0], "/bin/hello");