Lec11 Scheduling 1

进程切换、调度。

1 课前准备

Read “Scheduling” through Section 7.4, and kernel/proc.c, kernel/swtch.S.

1.1 多路复用

有两种情景会导致切换进程。当进程等待设备或管道 I/O 完成、等待子进程退出或等待 sleep 系统调用时，xv6 的 sleep 和 wakeup 机制会切换。其次，xv6 定期强制切换以应对长时间计算而不休眠的进程。

1.2 Code：上下文切换

用户进程切换的路径：一个用户-内核转换（系统调用或中断）到旧进程的内核线程、一个到当前 CPU 调度器线程的上下文切换、一个到新进程内核线程的上下文切换，和一个返回到用户进程的 trap。xv6 的调度器是每个 CPU 一个专门的线程（保存有寄存器和栈）。

从一个进程切换到另一个包含了保存旧内核线程的 CPU 寄存器，然后恢复先前保存的新内核线程的寄存器。swtch 就完成了这件事。

在实现调度的函数 sched 中，它将内核进程的上下文切换到每个 CPU 保有的调度器上下文中。

1.3 Code：调度

见 Lecture 部分。

1.4 Code：mycpu and myproc

xv6 为每个 CPU 维护一个结构体 (struct cpu)，记录了当前在该 CPU 上运行的进程（如果有的话）、CPU 调度器线程的保存寄存器，以及管理中断禁用所需的嵌套自旋锁计数。每个 CPU 的结构体中保存了一个 hartid，用于唯一标识该CPU。

mycpu() 返回指向当前 CPU 结构体的指针。在 RISC-V 中，每个 CPU 都有一个 hartid，而 xv6 保证每个 CPU 的 hartid 都存储在该 CPU 的 tp 寄存器中，这样就可以通过 tp 来索引一个 CPU 结构体数组，找到对应的 CPU。xv6 确保始终使 tp 保存该 CPU 的 hartid，这一过程包括在 CPU 引导序列中早期设置 tp、在用户态 trap 时保存 tp 的值 (usertrapret)、以及在进入内核时从保存的值中恢复 tp 的值 (uservec)。

为了保证返回值的正确性，在调用 cpuid 和 mycpu 时要保证中断关闭，否则定时器中断可能会改变线程执行的 CPU。

2 Lecture

2.1 线程概述

我们给线程一个宽松的定义：一个可以认为是串行执行代码的单元。线程还拥有状态，我们可以随时保存线程的状态并暂停线程的运行，并在之后恢复。它通常包括：

1. pc (program counter)，它表示当前执行命令的位置。
2. 保存变量的寄存器。
3. 程序的栈帧，通常来说每个线程有属于自己的栈。

线程之间共享内存、共享地址空间，因此多个线程同时运行时，修改数据需要加锁。xv6 的布局是这样的：每个用户进程都有一个对应的内核线程，它控制了用户进程代码指令的执行。因此多个内核线程共享一个地址空间。但是每个用户进程都只含有一个线程，这个线程拥有这个进程的地址空间。

2.2 线程调度

一般来讲，定时器中断会强制将 CPU 控制权从当前的用户进程给到对应的内核线程，这一步是 pre-emptive scheduling，之后内核线程会主动将 CPU 控制权 yield 给调度器，这一步是 voluntary scheduling。

在线程调度时，我们需要区分线程的状态：

1. RUNNING，线程正在某个 CPU 上运行；
2. RUNNABLE，线程还没有在某个 CPU 上运行，但是一旦有空闲的 CPU 就可以运行；
3. SLEEPING，意味着线程在等待一些 I/O 事件，它只会在 I/O 事件发生了之后运行。

接下来我们描述一个完整的故事，来详细讲述一个用户进程切换到另一个用户进程时发生的所有事：

1. 定时器中断强迫 CPU 从用户进程切换到对应的内核线程，用户进程的 trampoline 代码将用户寄存器保存于自己的 trapframe 中；
2. 到达内核线程，执行内核中的 usertrap()，执行实际的中断处理程序。
3. 内核线程决定让出 CPU，调用 swtch 将线程上下文保存，并切换到 CPU 对应的调度器线程，执行 scheduler()；
4. 在 scheduler 中，将旧用户进程设置为 RUNNABLE 状态，然后通过表单找到下一个 RUNNABLE 进程，改为 RUNNING，再次调用 swtch，保存自己的上下文，并恢复新进程对应的内核线程之前保存的上下文，返回到其所在的系统调用或者中断处理程序中；
5. 在系统调用或中断处理程序中，从 trapframe 恢复用户寄存器，返回用户进程，开始运行。