PA4 - 虚实交错的魔法: 分时多任务

首先进行分支整理
task PA4.1: 实现基本的多道程序系统, 支持带参数的仙剑奇侠传与Hello内核线程的分时运行
task PA4.2: 实现支持虚存管理的多道程序系统
task PA4.3: 实现抢占式分时多任务系统, 并提交完整的实验报告

PA4.1

一、多道程序

多道程序(multiprogramming)系统的基本思想：
- 批处理系统的一个缺陷: 如果当前程序正在等待输入输出, 那么整个系统都会因此而停顿.
  - 不如用这些时间来进行一些有意义的工作
- 在系统一开始的时候加载多个程序
- 然后运行第一个;
- 当第一个程序需要等待输入输出的时候, 就切换到第二个程序来运行;
- 当第二个程序也需要等待的时候, 就继续切换到下一个程序来运行
- 如此类推.
实现一个多道程序操作系统
- 在内存中可以同时存在多个进程
- 在满足某些条件的情况下, 可以让执行流在这些进程之间切换

（一）上下文切换

“上下文”的概念: 上下文的本质就是进程的状态.
- 现在需要考虑的是, 如何在多个用户进程之间进行上下文切换.
am-kernels中准备了一个约30行的操作系统yield-os, 它创建了两个执行流, 在CTE的支撑下交替输出A和B. 你可以在native上运行yield-os来查看它的行为

1. 基本原理

上下文切换的实现：
- 当进程 A 运行过程中触发系统调用时，通过自陷指令进入内核。
- 在内核中，__am_asm_trap() 函数会将进程 A 的上下文结构保存到 A 的栈上。
- 系统调用处理完毕后，__am_asm_trap() 会根据栈上保存的上下文结构恢复 A 的上下文。
进程切换的巧妙方式：
- 如果在恢复 A 的上下文之前，将栈顶指针切换到另一个进程 B 的栈上。
- 由于 B 的栈上存放了之前 B 保存的上下文结构，接下来的操作会根据这一结构恢复 B 的上下文。
- 从 __am_asm_trap() 返回后，系统将开始运行进程 B。
进程挂起和唤醒：
- 进程 A 并没有消失，而是被暂时挂起了。
- 在被挂起之前，A 已经将上下文结构保存到自己的栈上。
- 当某一时刻栈顶指针切换回 A 的栈上时，代码会根据栈上的上下文结构恢复 A 的上下文，A 将被唤醒并继续执行。
总结：
- 上下文切换实际上就是不同进程之间的栈切换。
- 通过切换栈顶指针，操作系统可以在多个进程之间切换执行，确保每个进程都能得到公平的执行机会。

2. 进程控制块

为了找到其他进程的上下文结构，我们需要使用一个**上下文指针（cp）**来记录上下文结构的位置。由于上下文结构保存在栈上，而栈空间受到函数调用形成的栈帧影响，每次保存的位置并不固定，因此需要 cp 指针来定位上下文结构。
操作系统使用**进程控制块（PCB）**来管理进程相关的信息。PCB 包含了上下文指针（cp）和栈空间等信息。以下是 yield-os 中定义的 PCB 结构：

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

这个联合体将进程堆栈和上下文指针放在一起。每个进程分配了一个 32KB 的堆栈，足够使用且不会出现栈溢出。在进行上下文切换时，只需将 PCB 中的 cp 指针返回给 CTE的 __am_irq_handle() 函数，剩余部分的代码会根据上下文结构恢复上下文。

3. 内核线程

a. 创建内核线程上下文

对于刚刚加载完的进程, 我们要怎么切换到它来让它运行起来呢?
- 在进程的栈上人工创建一个上下文结构, 使得将来切换的时候可以根据这个结构来正确地恢复上下文即可.
yield-os提供了一个测试函数f(), 我们接下来的任务就是为它创建一个上下文, 然后切换到它来执行. 这样的执行流有一个专门的名称, 叫”内核线程“(kernel thread).
创建内核线程的上下文是通过CTE提供的kcontext()函数 (在abstract-machine/am/src/$ISA/nemu/cte.c中定义)来实现的, 其中的”k”代表内核. kcontext()的原型是

1	Context* kcontext(Area kstack, void (entry)(void ), void *arg);

其中
- kstack是栈的范围
- entry是内核线程的入口
- arg则是内核线程的参数.
此外, kcontext()要求内核线程不能从entry返回, 否则其行为是未定义的. 你需要在kstack的底部创建一个以entry为入口的上下文结构(目前你可以先忽略arg参数), 然后返回这一结构的指针.

b. 线程/进程调度

上下文的创建和切换是由 CTE 负责的，而具体切换到哪个上下文则由操作系统决定，这项任务称为进程调度。进程调度由 schedule() 函数完成，它返回将要调度的进程上下文。
为了实现多任务调度，需要记录当前正在运行的进程，这通过 current 指针实现，它指向当前运行进程的 PCB。在 schedule() 中，通过 current 指针决定接下来要调度的进程。
在调度之前，需要将当前进程的上下文指针保存在 PCB 中：

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

// switch between pcb[0] and pcb[1]
current = (current == &pcb[0] ? &pcb[1] : &pcb[0]);

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

目前 schedule() 总是切换到另一个进程。所选进程的上下文通过 kcontext() 创建，在 schedule() 中决定切换到它，并在 CTE 的 __am_asm_trap() 中真正恢复这一上下文。

必做：实现上下文切换

根据讲义的上述内容, 实现以下功能:
- CTE的kcontext()函数
- 修改CTE中__am_asm_trap()的实现, 使得从__am_irq_handle()返回后, 先将栈顶指针切换到新进程的上下文结构, 然后才恢复上下文, 从而完成上下文切换的本质操作
正确实现后, 你将看到yield-os不断输出 ? , 这是因为我们还没有为kcontext()实现参数功能, 不过这些输出的 ? 至少说明了CTE目前可以正确地从yield-os的main()函数切换到其中一个内核线程.

在kstack底部创建一个上下文结构(返回地址是entry)，然后返回这个上下文结构的指针

Context *kcontext(Area kstack, void (*entry)(void *), void *arg) {
  // return NULL;
  Context *ctx = (Context *)(kstack.end - sizeof(Context));
  ctx->mepc = (uintptr_t)entry;
  return ctx;
}

修改CTE中__am_asm_trap()

从__am_irq_handle()返回后, 先将栈顶指针切换到新进程的上下文结构, 然后才恢复上下文
abstract-machine/am/src/riscv/nemu/trap.S

.align 3
.globl __am_asm_trap
__am_asm_trap:
  addi sp, sp, -CONTEXT_SIZE

  MAP(REGS, PUSH)

  csrr t0, mcause
  csrr t1, mstatus
  csrr t2, mepc

  STORE t0, OFFSET_CAUSE(sp)
  STORE t1, OFFSET_STATUS(sp)
  STORE t2, OFFSET_EPC(sp)

  # set mstatus.MPRV to pass difftest
  li a0, (1 << 17)
  or t1, t1, a0
  csrw mstatus, t1

  mv a0, sp
  jal __am_irq_handle

  # 切换到新进程的上下文结构
  mv sp, a0

  LOAD t1, OFFSET_STATUS(sp)
  LOAD t2, OFFSET_EPC(sp)
  csrw mstatus, t1
  csrw mepc, t2

  MAP(REGS, POP)

  addi sp, sp, CONTEXT_SIZE
  mret

在/ics2024/am-kernels/kernels/yield-os目录下make run ARCH=riscv32-nemu

Welcome to riscv32-NEMU!
For help, type "help"
[src/monitor/monitor.c:36 welcome] Exercise: Please remove me in the source code and compile NEMU again.
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????[src/cpu/cpu-exec.c:147 statistic] host time spent = 10,105,245 us
[src/cpu/cpu-exec.c:148 statistic] total guest instructions = 105,536,449
[src/cpu/cpu-exec.c:149 statistic] simulation frequency = 10,443,729 inst/s
make: *** [/home/xiaoyao/ics2024/abstract-machine/scripts/platform/nemu.mk:32: run] 中断

成功！

c. 内核线程的参数

为了让yield-os的内核线程可以正确输出字符, 我们需要通过 kcontext() 给 f() 传参.
只需要让kcontext()按照调用约定将 arg 放置在正确的位置, 将来f()执行的时候就可以获取正确的参数了.

必做：实现上下文切换(2)

根据讲义的上述内容, 修改CTE的kcontext()函数, 使其支持参数arg的传递.
因为f()中每次输出完信息都会调用yield(), 因此只要我们正确实现内核线程的参数传递, 就可以观察到yield-os在两个内核线程之间来回切换的现象.

RISC-V调用约定:
- 函数参数传递
  - 前 8 个函数参数通过寄存器 a0 到 a7 传递。
  - 如果参数超过 8 个，多余的参数通过栈传递。

x0 (zero): 常数 0
x1 (ra): 返回地址
x2 (sp): 栈指针
x3 (gp): 全局指针
x4 (tp): 线程指针
x5-x7 (t0-t2): 临时寄存器
x8 (s0/fp): 保存寄存器/帧指针
x9 (s1): 保存寄存器
x10-x11 (a0-a1): 函数返回值/函数参数
x12-x17 (a2-a7): 函数参数
x18-x27 (s2-s11): 保存寄存器
x28-x31 (t3-t6): 临时寄存器

根据调用约定，把arg放到a0寄存器

在CTE的kcontext()函数添加

1	ctx->gpr[10] = (uintptr_t)arg;

成功！

Welcome to riscv32-NEMU!
For help, type "help"
[src/monitor/monitor.c:36 welcome] Exercise: Please remove me in the source code and compile NEMU again.
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA[src/cpu/cpu-exec.c:147 statistic] host time spent = 4,025,540 us
[src/cpu/cpu-exec.c:148 statistic] total guest instructions = 42,032,479
[src/cpu/cpu-exec.c:149 statistic] simulation frequency = 10,441,451 inst/s
make[1]: 离开目录“/home/xiaoyao/ics2024/nemu”

（二）OS中的上下文切换

Nanos-lite

Nanos-lite上下文切换需要用到的函数和数据结构和yield-os非常类似, 只不过由于Nanos-lite的代码规模更大, 它们分散在不同的文件中, 你需要RTFSC找到它们. 此外, Nanos-lite的框架代码已经定义了PCB结构体, 其中还包含其他目前暂不使用的成员, 我们会在将来介绍它们.

必做：在Nanos-lite中实现上下文切换

实现以下功能:
- Nanos-lite的context_kload()函数(框架代码未给出该函数的原型), 它进一步封装了创建内核上下文的过程: 调用kcontext()来创建上下文, 并把返回的指针记录到PCB的cp中
- Nanos-lite的schedule()函数
- 在Nanos-lite收到EVENT_YIELD事件后, 调用schedule()并返回新的上下文
Nanos-lite提供了一个测试函数 hello_fun()(在nanos-lite/src/proc.c中定义), 你需要在init_proc()中创建两个以hello_fun为入口的上下文:

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

其中调用switch_boot_pcb()是为了初始化current指针. 你可以自行约定用何种类型来解析参数arg(整数, 字符, 字符串, 指针等皆可), 然后修改hello_fun()中的输出代码, 来按照你约定的方式解析arg. 如果你的实现正确, 你将会看到hello_fun()会轮流输出不同参数的信息.

/ics2024/nanos-lite/src/proc.c中实现 context_kload() 函数

//实现 context_kload() 函数
void context_kload(PCB *pcb, void (*entry)(void *), void *arg) {
  Area kstack = (Area){.start = pcb->stack, .end = pcb->stack + sizeof(pcb->stack)};
  pcb->cp = kcontext(kstack, entry, arg);
}

实现**schedule()**函数

Context* schedule(Context *prev) {
  // return NULL;
  current->cp = prev;
  current = (current == &pcb[0] ? &pcb[1] : &pcb[0]);
  return current->cp;
}

在init_proc()中创建两个以hello_fun为入口的上下文:

void init_proc() {
  switch_boot_pcb();

  Log("Initializing processes...");

  // load program here
  // naive_uload(NULL, NULL);

  //创建两个以hello_fun为入口的上下文:
  context_kload(&pcb[0], hello_fun, " QAQ ");
  context_kload(&pcb[1], hello_fun, " TWT ");
  switch_boot_pcb();
}

在Nanos-lite收到EVENT_YIELD事件后, 调用schedule()并返回新的上下文

报错system panic: Unhandled event ID = 4
去把pa3做完了，继续看一下
后面准备不做了

PA4实验记录

Universe Hamster

PA4 - 虚实交错的魔法: 分时多任务

PA4.1

一、多道程序

（一）上下文切换

1. 基本原理

2. 进程控制块

3. 内核线程

a. 创建内核线程上下文

b. 线程/进程调度

必做：实现上下文切换

c. 内核线程的参数

必做：实现上下文切换(2)

（二）OS中的上下文切换

Nanos-lite

必做：在Nanos-lite中实现上下文切换

Other Articles

PA3实验记录

九、局域网交换和VLAN