6.1810 2024 第11讲：线程切换

主题：更深入地了解 xv6 的“底层”

• 之前：系统调用、中断、页表、锁
• 今天：进程/线程切换

为什么支持并发任务？

• 分时：许多用户和/或许多正在运行的程序。
• 程序结构：素数筛。
• 并行编程：利用多核硬件。

什么是线程？

• 想象一下正在以普通的串行方式执行的代码
• 假设我们想暂停它，把它放在一边，
  • 做其他事情，然后稍后再恢复该代码？
• 我们需要保留什么？
  • 内存、堆栈、CPU 寄存器、CPU 程序计数器
• 一个“线程”在以下状态之间交替
  • 执行代码，
  • 以及，当被挂起时，恢复它所需的已保存状态
• [简单的双线程交替图]
• 线程系统管理线程之间的切换

xv6 如何使用线程？

• [简单图]
• 每个 xv6 进程都有一个用户级线程，
  • 和一个内核线程
• 进程的内核线程执行系统调用实现
  • 并且可能需要挂起自己以等待输入等
  • 或者让其他进程的线程运行
• xv6 内核线程共享内存 —— 它们都在内核地址空间中执行，
  • 它们都使用内核数据结构，
  • 因此它们需要锁
• 进程的用户线程和内核线程不是独立的！
  • 如果在内核中执行，用户线程正在等待陷阱返回
  • 如果在用户空间中执行，内核线程是空的
• 我将交替使用“进程”和“线程”

如果一个 xv6 进程没有在执行

• 它通常在等待某个事件 —— 控制台、管道、磁盘等
  • 因为它向内核发出了一个系统调用，例如 read()
• 可能在复杂的内核系统调用实现中途等待
  • 需要在它离开的地方恢复内核系统调用代码
  • 因此它的内核寄存器（和堆栈）必须被保存

xv6 进程/线程的已保存状态

• 用户内存
• 用户保存的寄存器（在陷阱帧 (TF) 中）
• 内核堆栈
• 内核保存的寄存器（“上下文” (CTX)）
• 内核 p->state

p->state 告诉调度器如何处理进程

• RUNNING —— 现在正在一个 CPU 上执行（在用户态或内核态）
• RUNNABLE —— 想要执行，但没有在执行（已挂起，在内核中）
• SLEEPING —— 正在等待一个事件（已挂起，在内核的 read()、wait() 等中）
• 有助于避免诸如同时在两个 CPU 上执行之类的错误

xv6 如何从一个进程切换到另一个进程 —— “上下文切换”

• 例如 P1 调用 read() 并等待，P2 是 RUNNABLE
• [P1, TF1, KSTACK1, CTX1, swtch(), CTXs, STACKs, swtch(), CTX2, KSTACK2, TF2, P2]
• TF = 陷阱帧 = 保存的用户寄存器
• CTX = 上下文 = 保存的内核寄存器
• 从一个用户进程到另一个用户进程涉及多个转换：
  • 用户 -> 内核；在陷阱帧中保存用户寄存器
  • 内核线程 -> 调度器线程；在上下文中保存内核线程寄存器
  • 调度器线程 -> 内核线程；从上下文中恢复内核线程寄存器
  • 内核 -> 用户；从陷阱帧中恢复用户寄存器

proc.h 中的 struct proc

• p->trapframe 保存已保存的用户线程的寄存器
• p->context 保存已保存的内核线程的寄存器
• p->kstack 指向线程的内核堆栈
• p->state 是 RUNNING, RUNNABLE, SLEEPING 等
• p->lock 保护 p->state（以及其他东西...）

proc.c 中的 proc[NPROC] 数组 —— 每个进程一个

为什么需要一个单独的调度器线程？

• 这样总有一个堆栈可以运行调度器循环
• 例如，从一个正在退出的进程切换出去
• 例如，进程数少于 CPU 数

调度器线程细节

• 每个 CPU 一个；每个都有一个堆栈和一个 struct context
• 内核线程总是切换到这个 CPU 的调度器线程
  • 如果有 RUNNABLE 的线程，它会切换到另一个内核线程
  • 从来没有直接的进程到进程的切换
• 每个 CPU 的调度器线程不断扫描 proc[] 进程表
  • 直到找到一个 RUNNABLE 的线程
• 如果没有 RUNNABLE 的线程，调度器就“空闲”

如果用户代码在计算时从不进行系统调用会怎样？

• 这会阻止其他进程运行吗？
• CPU 的计时器硬件会强制进行周期性中断
  • xv6 计时器处理程序会进行切换（“yield”）
• “抢占”或“非自愿上下文切换”

代码

抢占式切换演示

• vi user/aaa.c, bbb.c
• 两个 CPU 密集型进程
• 我的 qemu 只有一个 CPU
• 我们将观察 xv6 在它们之间切换

make qemu-gdb
gdb
(gdb) c
aaa &
bbb

你可以看到它们交替执行。 xv6 正在它的一个 CPU 上在这两个进程之间切换。

• 由计时器中断驱动
• 我们可以看到计时器大约多久触发一次 切换是如何工作的？

我将在计时器中断处设置一个断点。 (gdb) tb trap.c:81(gdb) c(gdb) tui enable(gdb) where

我们在 usertrap() 中，处理来自计时器的设备中断， 该中断发生在用户空间。

计时器中断发生时正在运行什么？ (gdb) p p->name(gdb) p/x p->trapframe->epc

让我们在 user/aaa.asm 中查找保存的 epc 计时器在增量循环中中断了用户代码

(gdb) step into yield() in proc.c(gdb) next(gdb) p p->state

将 p->state 从 RUNNING 更改为 RUNNABLE -> 放弃 CPU 但想再次运行。 注意：yield() 获取了 p->lock

• 以防止另一个 CPU 运行这个 RUNNABLE 的线程！
• yield() 仍在使用它的内核堆栈！
• 我们还没有在它的上下文中保存它的内核寄存器

(gdb) next ...(gdb) step into sched()

sched() 进行一些健全性检查，然后调用 swtch()

(gdb) next (until about to call swtch())

vi kernel/swtch.S

swtch() 执行从一个内核线程到另一个内核线程的上下文切换 我将首先快速过一遍，然后看细节

(gdb) tb swtch(gdb) c(gdb) where 调用者是 yield()/sched()(gdb) si 28(gdb) where 突然我们进入了 main()/scheduler()，而不是 yield()/sched()！ (gdb) si 就好像我们刚刚从 scheduler() 中的一个 swtch() 调用返回

• 即使是 sched() 调用了 swtch() 这是怎么发生的？

让我们再做一次，看看细节。 (gdb) tb sched(gdb) c(gdb) tb swtch(gdb) c(gdb) wherevi kernel/swtch.S

swtch 将寄存器保存到 xx(a0) 即 p->context.xx 然后从 xx(a1) 即 c->context.xx 即 cpus[0]->context.xx 加载寄存器

问：什么决定了 swtch 的 ret 返回到哪里？问：那个值是从哪里来的？

首先，让我们看看当前的 ra(gdb) x/i $ra

swtch()（在保存当前 ra 之后）将从 0(a1) 加载一个新的 ra

• 在第 25 行
• 0(a1) 是 cpus[0]->context.ra(gdb) x/i cpus[0]->context.ra

那个 ra 地址在哪里？ 让我们看看 kernel/kernel.asm

• 它就在 scheduler 调用 (jal) swtch 之后
• 就好像我们现在正从 scheduler 之前对这个进程的 swtch() 调用返回

第 26 行还加载了一个新的 sp —— 堆栈指针 —— 它是什么？ (gdb) x cpus[0]->context.sp

加载 sp 实际上切换了堆栈

• 以及堆栈上的当前位置
• 每个线程都有自己的堆栈
• 包含有关调用者的信息（参数、变量、返回地址）

(gdb) si 28(gdb) x/i $ra(gdb) where

现在到 scheduler() 的线程切换完成了！

• 保存/恢复寄存器是它的核心

(gdb) si

swtch() 保存了 p 的寄存器，以便稍后我们可以 swtch() 回到 p(gdb) p/x p->context(gdb) x/i p->context.ra(gdb) p/x p->context.sp(gdb) p/x p->kstack 所以如果 scheduler() 稍后 swtch 到 p，swtch() 将返回到 sched()，

• 在 p 的内核堆栈上，
• 就好像 p 最初对 swtch() 的调用返回了一样

问：为什么 swtch 不需要保存/恢复 $pc？

问：为什么 swtch() 只保存 14 个寄存器 (ra, sp, s0..s11)？

• RISC-V 有 32 个寄存器 —— 其他 18 个呢？
  • zero, gp, tp
  • t0-t6, a0-a7

好的，我们现在在 scheduler() 中，在“调度器线程”中，

• 在调度器的堆栈上

[此图的前半部分]

  aaa                        bbb
  usertrap                   usertrap
  yield         main         yield
  sched       scheduler      sched
  swtch  ->  swtch  swtch -> swtch

scheduler() 刚刚从对 swtch() 的调用返回

• 它在不久前进行了该调用，以切换到我们进程的内核线程
• 那个之前的 swtch() 保存了 scheduler() 的寄存器
• 我们进程对 swtch() 的调用恢复了 scheduler() 保存的寄存器
• 这里的 p 指的是被中断的进程

(gdb) p p->name(gdb) p p->state

记住 yield() 获取了进程的锁

• 现在 scheduler 释放它
• scheduler() 代码看起来像一个普通的获取/释放对
  • 但 yield 获取，scheduler 释放
  • scheduler 获取，yield 释放
• 不寻常：锁由与获取它的线程不同的线程释放！

问：为什么在 swtch() 期间持有 p->lock？

p->lock 防止在这些步骤中发生干扰：

• p->state=RUNNABLE
• 在 p->context 中保存寄存器
• 停止使用 p 的内核堆栈
• 所以另一个 CPU 的调度器在所有步骤完成之前不会开始运行 p

scheduler() 的循环查看所有进程，找到一个 RUNNABLE 的

• 一直循环直到找到某个东西 —— 可能会空闲一段时间
• 在这个演示中，将找到另一个 aaa/bbb 进程

让我们快进到 scheduler() 找到一个 RUNNABLE 进程， 并准备 swtch() 到它的时候。

(gdb) tb proc.c:463(gdb) c

scheduler() 锁定了新进程，将状态设置为 RUNNING

• RUNNING 意味着另一个 CPU 的调度器不会运行它

p 是另一个 aaa/bbb 进程： (gdb) p p->name(gdb) p p->state

让我们看看新线程在 swtch() 后将从哪里开始执行

• 通过查看其上下文中的 $ra（返回地址）

(gdb) x/i p->context.ra

在 kernel/kernel.asm 中查找该地址...

• 它就在进程早期调用 swtch() 之后 新线程将返回到 sched()

[完成图表]

问：scheduler() 是否给了 proc[0] 不公平的优势？

• 因为它的 for 循环从 proc[0] 开始？

问：什么是“调度策略”？

• 即，如果多个线程是 RUNNABLE 的，xv6 如何决定接下来运行什么？
• 这是一个好的策略吗？

再次查看 kernel/swtch.S

(gdb) tb swtch(gdb) c(gdb) si 28 -- 现在即将执行 swtch() 的 ret(gdb) x/i $ra(gdb) where

现在我们在另一个 aaa/bbb 进程的计时器中断中

• 过去它被中断，调用了 yield() / sched() / swtch()
• 但现在它正在恢复，并将返回到用户空间

并且 swtch() 设置了 cpus[0].context，以便这个进程最终可以

• swtch 回到调度器。 (gdb) x/i cpus[0].context.ra

在内核中时的计时器中断会导致 yield 吗？

• 即，内核代码是否可以像用户代码一样被抢占？
• 是的 —— kerneltrap() 调用 yield()
• 进程保存的寄存器在哪里？
  • 三组保存的寄存器：
    • 用户寄存器在陷阱帧中，通过 trampoline
    • 被中断的内核代码寄存器在堆栈上，通过 kernelvec
    • 中断处理程序的寄存器在 p->context 中，通过 swtch()
• 内核中的抢占是必要的吗？
  • 不，因为内核没有无限的 CPU 密集型循环。
  • 但如果某些系统调用有大量计算，则很有价值。
  • 或者如果我们需要严格的线程优先级概念。

为什么代码不允许在上下文切换期间持有自旋锁？

• 除了 p->lock
• P1:
  • acquire(L1)
  • yield()
• P2:
  • acquire(L2)
  • acquire(L1)
• P2 持有 L2，因此在 P2 在 acquire(L1) 中自旋时中断是关闭的
  • -> 计时器中断不会发生
  • -> P2 不会放弃 CPU
  • -> P1 无法执行
  • -> P1 永远不会释放 L1

我们能去掉每个 CPU 单独的调度器线程吗？

• sched() 可以直接 swtch() 到一个新线程吗？
• 那样会更快 —— 避免了一次 swtch() 调用
• 我们会将 scheduler() 的循环移入 sched()
• 也许 —— 但是：
  • 调度循环将在 sched() 中在一个线程的内核堆栈上运行
  • 如果那个线程正在退出怎么办？
  • 如果线程数少于 CPU 数怎么办 —— 即堆栈太少？
• 所以可能很棘手

为什么 scheduler() 用 intr_on() 启用中断？

• (演示：将 intr_on() 更改为 intr_off()。注意 CPUS=1。)
• 可能没有 RUNNABLE 的线程
  • 它们可能都在等待 I/O，例如磁盘或控制台
• 启用中断，以便设备有机会发出完成信号
  • 从而唤醒一个线程
• 否则，系统将冻结

线程高效吗？

• 内存成本：每个线程一个堆栈
• CPU 时间成本：swtch()
• 通常足够高效 —— 而且当然方便
• 如果你有很多线程（内存），或者经常切换（cpu），就会成为问题
• 除了线程之外，还有其他技术可以交错任务
  • 查阅事件驱动编程或状态机
• 线程不是最高效的，但它们很方便

一个用户空间进程可以有多个用户空间线程吗？

• xv6 不支持这个
• 但其他系统支持，例如 Linux、MacOS
• 通常每个用户线程一个内核线程

下周：sleep() 和 wakeup() —— 等待事件