甩锅声明

从PA4开始, 讲义中就不再提供滴水不漏的代码指导了, 部分关键的代码细节需要你自己去思考和尝试(我们故意省略的). 我们会在讲义中将技术的原理阐述清楚, 你需要首先理解这些原理, 然后根据理解来阅读并编写相应的代码.

一句话总结, 与其抱怨讲义写得不清楚, 还不如自己多多思考. 现在都到PA4了, 为了让成绩符合正态分布, 拿高分总需要多付出点努力吧. 如果你之前都是"一切以完成实验优先"而不去深入理解系统如何工作, 现在到了该吃亏的时候了.

多道程序

通过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了!

context-switch

那进程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中还定义了其它成员, 目前可以忽略它们, 我们会在将来介绍它们.

更新变量名

由于我们的疏忽, 框架代码中的上下文指针仍然使用了旧的变量名tf, 为了和讲义保持一致, 你可以把变量名修改成cp. 在nanos-lite/src/loader.c的代码中也有对tf成员的两处引用, 你还需要修改它们.

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()中才真正地恢复这一上下文.

实现上下文切换

根据讲义的上述内容, 实现以下功能:

  • CTE的_kcontext()函数
  • Nanos-lite的schedule()函数
  • 在Nanos-lite收到_EVENT_YIELD事件后, 调用schedule()并返回其现场
  • 修改CTE中asm_trap()的实现, 使得从irq_handle()返回后, 先将栈顶指针切换到新进程的上下文结构, 然后才恢复上下文, 从而完成上下文切换的本质操作

为了测试实现的正确性, 框架代码提供了一个测试函数hello_fun()(在nanos-lite/src/proc.c中定义). 你需要在init_proc()中单独创建一个以hello_fun为返回地址的上下文:

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

其中, context_kload()nanos-lite/src/loader.c中定义, 它会调用CTE的kcontext()来创建一个上下文, 而调用switch_boot_pcb()则是为了初始化current指针. 如果你的实现正确, 你将会看到hello_fun()中的输出信息.

创建用户进程上下文

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

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

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

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

目前我们只需要把这一栈帧中的参数设置为0NULL即可, 至于返回地址, 我们永远不会从_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(), 来模拟设备访问缓慢的情况. 添加之后, 访问设备时就要进行上下文切换, 从而实现多道程序系统的功能.

实现多道程序系统

根据上述内容, 实现多道程序系统. 如果你的实现正确, 你将可以一边运行仙剑奇侠传的同时, 一边输出hello信息.

bug修复

我们在2018/12/09 16:30:00修复了native运行多道程序时触发段错误的bug. 如果你在此时间之前获得框架代码, 请根据这里手动更新该文件; 如果你在此时间之后获得框架代码, 你不需要进行额外的操作.

一山不能藏二虎?

尝试把hello_fun()换成Navy-apps中的hello:

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

你发现了什么问题? 为什么会这样? 思考一下, 答案很快揭晓!

温馨提示

PA4阶段1到此结束.

results matching ""

    No results matching ""