Scheduling

课前准备

任何操作系统可能都会运行比计算机 CPU 数量更多的进程，我们需要分时共享 CPU。这种共享对用户进程来说是透明的。一种常见的方法是通过将进程多路复用到硬件 CPU 上，给每个进程提供它拥有自己虚拟 CPU 的假象。

Multiplexing 多路复用

xv6 实现 sleep 和 wakeup 使进程休眠或唤醒

什么时候切换进程？

• 一个进程等待设备或管道 I/O 完成、等待子进程退出、主动调用 sleep

• 定期切换。防止进程长时间霸占CPU

面对的一些问题

1. 如何切换进程？
   • 尽管上下文切换的概念很简单，但其实现是 xv6 中最复杂的代码之一
2. 如何保证透明性、以及强制切换？
3. 多核上运行进程，需要锁
4. 如何释放进程资源？
5. 进程切换时如何保存上下文？
6. 唤醒线程时，如何避免竞争？

xv6 尽量以最简单的方式解决这些问题，但结果代码仍然相当复杂。

Code: Context switching

旧进程的用户线程–旧进程的内核线程–调度器线程–新进程的内核线程–新用户线程

scheduler 线程

每个CPU都有一个调度器线程，它有自己的上下文：寄存器和栈。

它不能运行在旧进程的内核线程的上下文中，因为旧进程可能会被其他核唤醒并运行

切换上下文

切换线程需要保存旧线程的寄存器，并恢复新线程的寄存器——这意味着恢复了SP和PC，也就恢复了栈和执行的代码

swtch：切换上下文

swtch：纯汇编函数，无情的保存和恢复寄存器的机器

注意，只保存并恢复了callee saved 寄存器与 ra，在 ra 中是 swtch 的返回地址。于是从 swtch 就会返回到调用它的那条指令。无需保存与恢复pc

context

context 结构体包含了这些信息：

proc 和 cpu 都使用了 context 结构体

yield、sched 与调度器

yield 会调用 sched，后者调用 swtch，用于保存和恢复上下文。

切换到 cpu->scheduler，也即每个CPU的调度器的上下文。它不会返回到 sched，而是返回到调度器

Code: Scheduling

分析通过调度器从一个进程的内核线程切换到另一个进程

调度器

调度器是每个 CPU 有一个特殊的线程，负责选择下一个要运行的进程。

调度器循环遍历进程表，寻找一个可以运行的进程，即 p->state == RUNNABLE 的进程。一旦找到则更新 state 与当前 cpu 的 proc，然后通过 swtch 开始运行该线程

调度中的不变量

在不变量不成立时必须拥有进程的锁。而在进程停止运行前、以及开始运行时，我们会修改一些元数据，所以此时必须持有锁。

这里的不变量有：CPU当前运行的进程、CPU的寄存器值（保存到p->context）、进程的状态。

这些不变量保证了 yield 可以安全切换该进程，以及调度器可以安全地调度运行它。

在不持有锁时，应当保证：寄存器值保存到了 context、没有CPU在其内核栈上运行、以及没有cpu的 c->proc 指向它

yield

如上文所述，一个想要放弃 CPU 的进程必须获取其自身的进程锁，释放它持有的其他锁，更新自己的状态（p->state），然后调用 sched

yield、sleep 、exit 均遵循这个惯例。

sched

sched 会仔细检查这些条件，并断言中断应该已经被关闭了。最后调用 swtch 切换到调度器上下文

注意，此时不变量的属性被打破， sched 的调用者必须持有进程的锁。

不同的线程中释放锁

这个锁在切换后的代码，也即调度器中释放它。

这种使用方式不同寻常，通常持有锁的线程负责释放锁，但在切换线程上下文时有必要打破这一惯例，以维护进程的不变量

协程：sched 和 scheduler

内核线程通常会在 sched 中放弃CPU，然后跳转（通过swtch）到 scheduler 中某个固定的位置，scheduler 又会跳转到某个线程的 sched 末尾，进而返回到一个线程中。

这种在线程之间发生的程式化切换有时被称为协程（？？）。这个例子中，sched 和 scheduler 是彼此的协程。

swtch 不返回到 sched：首次调度

有一种情况，调度器调用 swtch 不会返回到 sched。当一个新进程首次被调度时，它从 forkret 开始。

forkret 的存在是为了释放 p->lock；否则，新进程可以从 usertrapret 开始。

p->lock 保护的其他内容

p->lock 还保护其他内容：exit 和 wait 之间的交互，避免丢失唤醒通知的机制（见第 7.5 节），以及避免进程退出与其他进程读取或写入其状态之间的竞争（例如，exit 系统调用查看 p->pid 并设置 p->killed（kernel/proc.c:611））。考虑是否可以将 p->lock 的不同功能拆分开来，可能会对代码的清晰度和性能有所帮助。

Code: mycpu and myproc

Xv6 经常需要指向当前进程的 proc 结构体指针。在单核处理器上可以通过一个全局变量解决，但在多核处理器上就可能需要上锁了，或者

struct cpu

这个结构体记录了当前cpu上运行的进程、保存的调度器线程的上下文、管理中断的自旋锁计数器

cpuid 与 mycpu

xv6为每个cpu编号，并将其id保存到寄存器 tp 中，访问 tp 即可获取 id，进而索引到正确的 cpu 结构体

如何确保 tp 是当前CPU id？

确保每个 CPU 的 tp 寄存器始终保存该 CPU 的 hartid 需要一些额外的步骤。

• mstart 在 CPU 启动序列的早期阶段（仍处于机器模式下）设置 tp 寄存器

• usertrapret 将 tp 保存在跳板页中，因为用户进程可能会修改 tp。

• 当从用户空间进入内核时，uservec 会恢复保存的 tp

• 编译器保证绝不会使用 tp 寄存器。

如果 RISC-V 允许 Xv6 直接读取当前的 hartid 会更方便，但这只能在机器模式下进行，而不能在超级用户模式下进行。

中断与tp

cpuid 和 mycpu 的返回值是脆弱的：如果定时器中断并导致线程让出 CPU 并移至另一个 CPU，那么先前返回的值将不再正确。

为避免这个问题，Xv6 要求调用者禁用中断，并且只能在完成对返回的 struct cpu 的使用后再启用中断。

myproc

禁用中断–获取cpu–获取proc–启用中断–返回

线程概述

今天我们将讨论XV6如何在多个线程之间完成切换。

一个线程可以认为是串行执行代码的单元，它只占用一个CPU并且以普通的方式一个接一个的执行指令。

为什么需要多线程？

• 人们希望计算机可以并发执行任务。有可能计算机需要执行分时复用的任务

• 多线程可以让程序变简单。如 lab1 中的 primes

• 多线程可以进行并行运算，在拥有多核CPU的计算机上获得更快的处理速度

线程的状态

• PC。当前指令位置
• 保存变量的寄存器
• stack。函数调用的记录，以及当前线程的执行点

并发策略

• 一个核一个线程。无法应对过多线程的情况
• 在线程间切换

大多数操作系统结合了这两种策略。

线程系统与共享地址空间

共享内存

一个线程系统内部可以互相看到对方对共享的地址空间的修改，所以需要使用锁

内核线程

对于每个用户进程都有一个内核线程来执行来自用户进程的系统调用。所有的内核线程都共享了内核内存

用户线程

每一个用户进程都有独立的内存地址空间，并且仅包含了一个执行用户代码的线程，所以XV6中的用户线程之间没有共享内存

在一些其他更加复杂的系统中，例如Linux，允许在一个用户进程中包含多个线程，进程中的多个线程共享进程的地址空间。

并发，但是不使用线程

event-driven programming、state machine

XV6线程调度

面临的问题

实现内核中的线程系统存在以下挑战：

1. 如何实现线程切换，即如何进行线程调度

2. 需要保存并恢复线程的哪些状态？

3. 如何从运算密集型线程 compute bound thread 中取得CPU的控制？

定时器中断与 pre-emptive scheduling

强制从程序手中拿回CPU的控制。可以处理运算密集型线程。

被中断的程序会进入内核，内核通过 yield 让出CPU，切换到调度器线程，然后由调度器决定下一个进程，再切换到该进程。这样的处理流程被称为pre-emptive scheduling，与之相对的是 voluntary scheduling

说起来幽默，pre-emptive 中内核会代表用户进程使用 voluntary scheduling

线程分类

• RUNNING，当前在CPU上运行的线程

• RUNABLE，一旦CPU有空闲时间就想要运行在CPU上的线程

• SLEEPING，以及不想运行在CPU上的线程，因为这些线程可能在等待I/O或者其他事件

这里不同的线程是由状态区分，但是实际上线程的完整状态会要复杂的多（包含了程序计数器，寄存器，栈等等）

pre-emptive scheduling：running->runable

通过出让CPU，pre-emptive scheduling将一个正在运行的线程转换成了一个当前不在运行但随时可以再运行的线程。即 running 转为 runable

CPU状态

切换进程时，需要保存CPU状态，通常指一部分寄存器。线程处于不同状态时，运行他的CPU状态需要保存到不同的地方

• RUNNING：保存到正在运行它的CPU硬件中

• RUNABLE线程没有CPU与之关联，需要将这些数据拷贝到内存中

将一个线程从running 转为 runable时，需要将它的CPU状态拷贝到内存中。同理，一个线程转为 running 时，需要从内存中将CPU状态加载回去

XV6线程切换

用户线程切换概述

如果程序执行了一个系统调用或者因为响应中断走到了内核中，那么用户空间的状态会被保存到 trapframe 中，同时激活了属于这个用户进程的内核线程。

如果需要切换到别的进程，那么会从原进程的内核线程切换到新进程的内核线程，然后再返回到新进程的用户线程，返回时会恢复 trapframe 中用户空间的数据。即：

内核线程切换

以上图为例，xv6首先将 shell 内核线程的寄存器保存到 context 中，恢复另一个内核线程的 context（会经过一个中间线程：调度器线程）

scheduler 恢复前的状态是 runable

然后继续这个内核线程之前的工作，最后返回新用户线程

比如被定时器打断，则从yield返回，也就是说中断处理完毕，返回用户空间即可

更完整的故事

假设我们有进程P1正在运行，进程P2是RUNABLE当前并不在运行。假设在XV6中我们有2个CPU核，这意味着在硬件层面我们有CPU0和CPU1。

1. 一个定时器中断强迫CPU从用户空间进程切换到内核，trampoline代码将用户寄存器保存于用户进程对应的trapframe对象中；

2. 之后在内核中运行usertrap，来实际执行相应的中断处理程序。这时，CPU正在进程P1的内核线程和内核栈上，执行内核中普通的C代码；

3. 假设进程P1对应的内核线程决定它想出让CPU，它会做很多工作，这个我们稍后会看，但是最后它会调用swtch函数（switch 是C 语言关键字，因此这个函数命名为swtch 来避免冲突），这是整个线程切换的核心函数之一；

4. swtch函数会保存用户进程P1对应内核线程的寄存器至context对象。所以目前为止有两类寄存器：用户寄存器存在trapframe中，内核线程的寄存器存在context中。

swtch 概述

调度器线程

swtch函数并不是直接从一个内核线程切换到另一个内核线程。XV6中，一个CPU上运行的内核线程可以直接切换到的是这个CPU对应的调度器线程。

每一个CPU都有一个完全不同的调度器线程。调度器线程也是一种内核线程，它也有自己的context对象。

任何内核线程决定让出CPU时都要经过它，由它决定切换到哪个线程

swtch 的工作

swtch 会保存旧的寄存器到一个 context 对象，然后把新线程的 context 加载到寄存器中

恢复栈

恢复的寄存器中包含sp，于是也就恢复了栈，之后就可以在当前context下执行 schedulder

schedulder 概述

schedulder 会做一些清理工作，然后找到下一个 runable 进程，调用 swtch；

清理工作例如将进程P1设置成RUNABLE状态

下一个进程必然也是从 swtch 进入 scheduler 然后变为 runable 状态的，于是我们就返回到了之前的 swtch，swtch 结束后就返回到了该进程所在的系统调用或中断handler中，紧接着我们就可以返回到用户空间，从 trapframe 中获取到用户上下文。最终，用户进程P2就恢复运行了。

注：调用swtch函数肯定在系统调用或者中断处理程序中

context 当然可以存储到 trapframe 中，但是出于简化代码的目的，trapframe 还是只包含用户空间的数据

尽管有这么多种、这么多同类的线程，一个CPU在任意时间只能运行一个线程

demo 示例

两个运算密集型线程不断输出内容：

它们都会响应定时器中断：

• （usertrap)

在yield函数中，当前进程会出让CPU并让另一个进程运行。

用户进程的pre-emptive scheduling能工作的原因是，用户进程运行时，中断总是打开的。xv6内核偶尔会关闭中断，但在返回前保证打开中断

如果定时器中断的硬件坏了，那么就可能得买个新电脑了。有的时候软件会尝试弥补硬件的错误，但是对于计算机内部的问题，人们倾向于不用软件来尝试弥补硬件的错误。

yield

接下来要修改和进程相关的元数据（如state），所以 yield 获取了进程的 锁，确保在释放锁前其他CPU不会运行这个线程：

sched

sched 进行了一些参数检查，发现异样就会panic：

swtch 与 context

context

线程切换中我们没有改变堆栈的任何数据，寄存器是唯一的不稳定因素

context 不包含 PC，因为无论如何PC都会随着指令不断更新。我们关心的是谁调用了 swtch 以及返回到哪，这需要我们保存 RA，它是swtch的调用点。

另外 context 中只保存了 callee-saved register 和 ra，因为 swtch 作为一个函数被调用，所以只需要保存它们

swtch

负责保存和恢复 context：

ret 前的sp为：

这是启动顺序中非常早的一个位置，start.s在这个区域创建了栈，这样才可以调用第一个C函数。所以调度器线程运行在CPU对应的 bootstack 上。

ra 指向 scheduler 中的一个固定位置

schedulder

每一个进程都是从 swtch 进入到 scheduler 中的，于是切换到某个进程的上下文时就会从它的 swtch 中返回

下次本进程让出CPU、切换到调度器线程时，便会切换到 c->proc=0，这里是在告知其他CPU，没有任何CPU此时运行在这个线程上

目前我们已经切换到了调度器线程，所以可以释放该进程的锁了（因为之前在 yield 中获取过）

然后 scheduler 挑选一个 runable 的线程，然后修改它的运行状态、CPU上运行的线程，然后切换到该线程

如果不是因为定时器中断进入的sched，那么swtch会返回到sched然后返回到别的函数中，比如系统调用中，而非yield

p->lock 的作用

从调度的角度来说，这里的锁完成了两件事情。

1. 确保 停止进程过程的原子性：更新进程状态为runable、保存context、停止使用当前进程栈

2. 确保 进程启动过程的原子性：更新进程状态为running、加载context

锁还关闭了中断，防止死锁

进程第一次被调度：forkret

进程与线程

Robert教授：Linux是支持一个进程包含多个线程，Linux的实现比较复杂，或许最简单的解释方式是：几乎可以认为Linux中的每个线程都是一个完整的进程。

Linux中，我们平常说一个进程中的多个线程，本质上是共享同一块内存的多个独立进程。所以Linux中一个进程的多个线程仍然是通过一个内存地址空间执行代码。如果你在一个进程创建了2个线程，那基本上是2个进程共享一个地址空间。之后，调度就与XV6是一致的，也就是针对每个进程进行调度。

进程第一次被调度

kernel/proc.c：allocproc

fork 会调用 allocproc 启用一个新进程，allocproc 会初始化新进程的context；这里还设置了ra和sp

于是该进程首次被调度时 swtch 就会返回到 forkret，就好像forkret刚调用了swtch，此时正从它中返回一样——尽管我们并没有实际上在这个进程中调用swtch，我们仅仅设置了它context的ra

forkret

它只会在启动一个新进程时运行：

释放调度器之前获取的锁，然后返回到 usertrapret —— 这也是一个伪造的调用，我们并没有从 usertrap 中调用 forkret，但此时就好像我们是从一个 trap 中返回用户空间一样

由于fork拷贝了父进程的 trapframe，也就得到了epc，所以我们可以继续接着之前的指令执行

学生提问：在fortret函数中，if(first)是什么意思？

Robert教授：文件系统需要被初始化，具体来说，需要从磁盘读取一些数据来确保文件系统的运行，比如说文件系统究竟有多大，各种各样的东西在文件系统的哪个位置，同时还需要有crash recovery log。完成任何文件系统的操作都需要等待磁盘操作结束，但是XV6只能在进程的context下执行文件系统操作，比如等待I/O。所以初始化文件系统需要等到我们有了一个进程才能进行。而这一步是在第一次调用forkret时完成的，所以在forkret中才有了if(first)判断。

第一个进程

唯一不是通过 fork 创建一个进程的场景就是第一个用户进程，在 userinit 中。此时我们需要设置 epc 为0