多道程序

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

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

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

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

要实现第一点并不难, 我们只要让loader把不同的进程加载在不同的内存位置就可以了, 加载进程的过程本质上就是一些内存拷贝的操作, 因此并没有什么困难的地方.

为了简单起见, 我们可以在Nanos-lite中直接定义一些测试函数来作为程序, 因为程序本质上就是一些有意义的指令序列, 目前我们不必在意这些指令序列到底从何而来. 不过, 一个需要注意的地方是栈, 我们需要为每个进程分配各自的栈空间.

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

上下文切换

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

基本原理

事实上, 有了CTE, 我们就有一种很巧妙的方式来实现上下文切换了. 具体地, 假设进程A运行的过程中触发了系统调用, 陷入到内核. 根据__am_asm_trap()的代码, A的上下文结构(_Context)将会被保存到A的栈上. 在PA3中, 系统调用处理完毕之后, __am_asm_trap()会根据栈上保存的上下文结构来恢复A的上下文. 神奇的地方来了, 如果我们先不着急恢复A的上下文, 而是先将栈顶指针切换到另一个进程B的栈上, 那会发生什么呢? 由于B的栈上存放了之前B保存的上下文结构, 接下来的操作就会根据这一结构来恢复B的上下文. 从__am_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的堆栈, 已经足够使用了, 不会出现栈溢出导致UB. 在进行上下文切换的时候, 只需要把PCB中的cp指针返回给CTE的__am_irq_handle()函数即可, 剩余部分的代码会根据上下文结构恢复上下文. 我们只要稍稍借助数学归纳法, 就可以让我们相信这个过程对于正在运行的进程来说总是正确的.

那么, 对于刚刚加载完的进程, 我们要怎么切换到它来让它运行起来呢?

内核线程

创建内核线程上下文

答案很简单, 我们只需要在进程的栈上人工创建一个上下文结构, 使得将来切换的时候可以根据这个结构来正确地恢复上下文即可.

上文提到, 我们先把Nanos-lite中直接定义的一些测试函数作为程序. Nanos-lite提供了一个测试函数hello_fun()(在nanos-lite/src/proc.c中定义), 我们接下来的任务就是为它创建一个上下文, 然后切换到它来执行. 这样的执行流有一个专门的名称, 叫"内核线程"(kernel thread).

创建内核线程的上下文是通过CTE提供的_kcontext()函数 (在nexus-am/am/src/$ISA/nemu/src/cte.c中定义)来实现的, 其中的"k"就是代表内核. _kcontext()的原型是

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

其中kstack是栈的范围, entry是内核线程的入口, arg则是内核线程的参数. 你需要在kstack的底部创建一个以entry为返回地址的上下文结构(目前你可以先忽略arg参数), 然后返回这一结构的指针. Nanos-lite会调用_kcontext()来创建上下文, 并把返回的指针记录到PCB的cp中:

|               |
+---------------+ <---- kstack.end
|               |
|    context    |
|               |
+---------------+ <--+
|               |    |
|               |    |
|               |    |
|               |    |
+---------------+    |
|       cp      | ---+
+---------------+ <---- kstack.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的__am_asm_trap()中才真正地恢复这一上下文.

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

内核线程的参数

你也许会疑惑, 不就是执行hello_fun()函数吗, 为什么不能直接调用它, 搞这么复杂, 究竟有什么好处? 现在我们就来展示其中的好处. 还记得hello_fun()带了一个arg参数吗? 我们来创建两个内核线程, 给它们传递不同的参数, 然后在输出的信息中把参数也一同输出, 这样我们就能看到执行流在两个内核线程之间来回切换了!

首先需要解决的第一个问题是, 我们要如何通过_kcontext()给hello_fun()传参? 于是我们需要继续思考, hello_fun()将会如何读出它的参数? 噢, 这不就是调用约定的内容吗? 你已经非常熟悉了. 我们只需要让_kcontext()按照调用约定的内容将arg放好, 将来hello_fun()执行的时候就可以获取正确的参数了.

第二个问题是如何在两个内核线程之间来回切换. hello_fun()中每次输出完信息都会调用_yield(), 因此我们只需要对schedule()进行简单的修改即可:

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

在真实的操作系统中, 内核中的很多背景任务,守护服务和驱动程序都是以内核线程的形式存在的. 如果你执行ps aux, 你就会看到系统中有很多COMMAND中带有中括号的内核线程(例如[kthreadd]). 而创建和执行它们的原理, 也是和上面的实验内容非常相似(当然具体实现肯定会有所不同).

用户进程

创建用户进程上下文

创建用户进程的上下文则需要一些额外的考量. 在PA3的批处理系统中, 我们在naive_uload()中直接通过函数调用转移到用户进程的代码, 那时候使用的还是内核区的栈, 万一发生了栈溢出, 确实会损坏操作系统的数据, 不过当时也只有一个用户进程在运行, 我们也就不追究了. 但在多道程序操作系统中, 系统中运行的进程就不止一个了, 如果让用户进程继续使用内核区的栈, 万一发生了栈溢出, 就会影响到其它进程的运行, 这是我们不希望看到的.

因此, 和内核线程不同, 用户进程的代码, 数据和堆栈都应该位于用户区, 而且需要保证用户进程能且只能访问自己的代码, 数据和堆栈. 为了区别开来, 我们把PCB中的栈称为内核栈, 位于用户区的栈称为用户栈. 于是我们需要一个有别于_kcontext()的方式来创建用户进程的上下文, 为此AM额外准备了一个API _ucontext()(在nexus-am/am/src/$ISA/nemu/src/vme.c中定义), 它的原型是

_Context *_ucontext(_AddressSpace *as, _Area kstack, void *entry);

其中, 参数as用于限制用户进程可以访问的内存, 我们在下一阶段才会使用, 目前可以忽略它; kstack是内核栈, 用于分配上下文结构, entry则是用户进程的入口. 由于目前我们忽略了as参数, 所以_ucontext()的实现和_kcontext()几乎一样, 甚至比_kcontext()更简单: 连参数都不需要传递. 不过你还是需要思考, 对于用户进程来说, 它需要一个什么样的状态来开始执行呢?

咦, 说好的用户栈呢? 事实上, 用户栈的分配是ISA无关的, 所以用户栈相关的部分就交给Nanos-lite来进行, _ucontext()无需处理. 目前我们让Nanos-lite把heap.end作为用户进程的栈顶, 然后把这个栈顶赋给用户进程的栈指针寄存器就可以了.

哎呀, 用户进程的栈指针寄存器可是ISA相关的, 在Nanos-lite里面不方便处理. 别着急, 还记得用户进程的那个_start吗? 在那里可以进行一些ISA相关的操作. 于是Nanos-lite和Navy-apps作了一项约定: Nanos-lite把栈顶位置设置到GPRx中, 然后由Navy-apps里面的_start来把栈顶位置真正设置到栈指针寄存器中.

在context_uload()中实现以上内容之后, 我们就可以加载用户进程了. 我们把其中一个hello_fun()内核线程替换成仙剑奇侠传:

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

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

用户进程的参数

我们在实现内核线程的时候, 给它传递了一个arg参数. 事实上, 用户进程也可以有自己的参数, 那就是你在程序设计课上学习到的argc和argv了, 还有一个你也许不怎么熟悉的envp. envp是环境变量指针, 它指向一个字符串数组, 字符串的格式都是形如xxx=yyy, 代表有一个名为xxx的变量, 它的值为yyy. 我们在PA0中通过init.sh初始化PA项目的时候, 它会在.bashrc文件中定义一些环境变量, 比如AM_HOME. 当我们编译LiteNES的时候, make程序就会解析nexus-am/apps/litenes/Makefile中的内容, 当遇到

include $(AM_HOME)/Makefile.app

的时候, 就会尝试通过getenv()这个库函数在环境变量指针指向的字符串数组里面寻找是否有形如 AM_HOME=yyy的字符串, 如果有, 就返回yyy, 于是make程序就可以正确地找到nexus-am项目中的Makefile.app文件并包含进来.

事实上, main()函数完整的原型应该是

int main(int argc, char *argv[], char *envp[]);

那么, 当我们在终端里面键入

make ARCH=x86-nemu run

的时候, ARCH=x86-nemu和run这两个参数以及环境变量都是怎么传递给make程序的main()函数的呢?

既然用户进程是操作系统来创建的, 很自然参数和环境变量的传递就需要由操作系统来负责. 最适合存放参数和环境变量的地方就是用户栈了, 于是操作系统在加载用户进程的时候, 还需要负责把argc/argv/envp以及相应的字符串放在用户栈中, 并把它们的存放方式和位置作为和用户进程的约定之一, 这样用户进程在_start中就可以访问它们了.

这项约定其实属于ABI的内容, ABI手册有一节Process Initialization的内容, 里面详细约定了操作系统需要为用户进程的初始化提供哪些信息. 不过在我们的Project-N系统里面, 我们只需要一个简化版的Process Initialization 就够了:

操作系统`argc/argv/envp`及其相关内容放置到用户栈上, 然后将GPRx设置为`argc`的地址.
具体的放置格式可以参考ABI手册, 或者ICS课本第七章的某个图.

根据这一约定, 你还需要修改Navy-apps中_start的代码, 在其调用call_main()之前把它的参数设置成argc的地址. 然后修改navy-apps/libs/libc/src/plaform/crt0.c中call_main()的代码, 让它解析出真正的argc/argv/envp, 并调用main(). 这样以后, 用户进程就可以接收到属于它的参数了.

void context_uload(PCB *pcb, const char *filename, char *const argv[], char *const envp[]);

让操作系统为每一个用户进程手动设定参数是一件不现实的事情, 因为归根到底用户进程的参数应该是要让用户来指定的. 于是最好能有一个方法能把用户指定的参数告诉操作系统, 让操作系统来把指定的参数放到新进程的用户栈里面. 这个方法当然就是系统调用SYS_execve啦, 如果你去看man, 你会发现它的原型是

int execve(const char *filename, char *const argv[], char *const envp[]);

这也就说明了为什么我们在PA3中通过开机菜单程序运行超级玛丽, 最后还是运行功夫: 我们当时并没有让SYS_execve给用户进程传递正确的参数!

用户栈和内核栈

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