Skip to content
Gains Summary
Main Navigation 首页 / Home
C++ 编程 / C++ Programming
系统与高性能 / Systems & Performance
Web 开发 / Web Development
人工智能 / Artificial Intelligence
工业软件 / Industrial Software
其他内容 / Other Topics
C++ 编程 / C++系统与性能 / SystemsWeb 开发 / Web人工智能 / AI工业软件 / Industrial

外观

Sidebar Navigation

← 系统与高性能 / Systems & Performance

xv6 源码学习 / xv6 Source Learning

1. xv6 源码学习专题 / xv6 Source Learning

2. xv6 学习路线：从 C 指针到操作系统源码 / xv6 Learning Roadmap

3. 读 xv6 必备的 C 语言和指针基础 / C And Pointers For xv6

4. 读 xv6 必备的 RISC-V 基础 / RISC-V Basics For xv6

5. 如何阅读 xv6 源码 / How To Read xv6 Source

6. xv6 启动与内核入口 / xv6 Boot And Kernel Entry

7. xv6 内存布局与页表 / xv6 Memory Layout And Page Tables

8. xv6 trap、中断与系统调用 / xv6 Traps Interrupts And System Calls

9. xv6 进程与 struct proc / xv6 Process And struct proc

10. xv6 上下文切换与调度器 / xv6 Context Switch And Scheduler

11. xv6 sleep/wakeup、wait 与 exit / xv6 Sleep Wakeup Wait And Exit

12. xv6 锁与并发 / xv6 Locks And Concurrency

13. xv6 文件描述符与 inode / xv6 File Descriptor And Inode

14. xv6 文件系统与日志 / xv6 File System And Log

15. xv6 设备驱动、console、UART 与磁盘 / xv6 Device Driver Console UART And Disk

16. xv6 用户程序与 shell / xv6 User Programs And Shell

17. 用 QEMU/GDB 调试 xv6 / Debugging xv6 With QEMU And GDB

18. 从 xv6 过渡到 Linux 0.11 / Bridge From xv6 To Linux 0.11

19. xv6 专题总结与实践项目 / xv6 Summary And Practice Projects

本页目录

xv6 上下文切换与调度器 / xv6 Context Switch And Scheduler ​

1. 这篇文章解决什么问题 ​

进程已经有了 struct proc。

但进程不会自己跑起来。

CPU 每一刻只能执行某条控制流。

操作系统必须决定：

  • 哪个进程可以运行。
  • 当前进程什么时候让出 CPU。
  • CPU 如何从调度器切到进程。
  • 进程如何再切回调度器。
  • 寄存器和栈如何保存。

这就是调度和上下文切换。

最小主线：

text
RUNNABLE process
  |
  v
scheduler chooses it
  |
  v
swtch to process context
  |
  v
process runs in kernel/user path
  |
  v
yield / sleep / exit
  |
  v
swtch back to scheduler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

本篇重点文件：

text
kernel/proc.c
  |
  +-- scheduler()
  +-- sched()
  +-- yield()

kernel/swtch.S
  |
  +-- low-level register context switch

kernel/proc.h
  |
  +-- struct context
  +-- struct cpu
  +-- struct proc

kernel/trap.c
  |
  +-- timer interrupt may call yield()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.1 本文基础词小注释 ​

调度 scheduler：调度就是“CPU 下一个给谁用”。CPU 同一时刻只能沿着一条执行路径往前走，所以内核要在多个进程之间做选择。xv6 里的 scheduler() 就是每个 CPU 长期运行的选择循环。

上下文 context：上下文不是上下文语境，而是“一段代码暂停后，将来还能继续跑所需要的少量寄存器状态”。在 xv6 中，struct context 主要保存内核线程切换时必须恢复的寄存器。

text
--------------------+
| saved registers    |
| ra, sp, s0..s11    |
+--------------------+
          |
          v
 resume kernel code later
1
2
3
4
5
6
7

上下文切换 context switch：把当前执行路径的关键寄存器保存起来，再恢复另一条执行路径之前保存的寄存器。它不是复制整个进程内存，也不是复制所有变量。xv6 的低层切换在 kernel/swtch.S。

RUNNABLE：表示“这个进程已经准备好，只是还没轮到它用 CPU”。它和 RUNNING 不同，RUNNING 表示“正在某个 CPU 上执行”。

RUNNING：表示进程正在占用 CPU。多核系统里，正确的不变量是：同一个进程不能同时在两个 CPU 上都是 RUNNING。

yield：字面意思是“让出”。在 xv6 里，yield() 表示当前进程主动或被时钟中断推动着让出 CPU，状态通常会变回 RUNNABLE，然后切回调度器。

切回调度器：不要把调度器想成一个普通函数被调用一下就结束。它更像每个 CPU 的“基地”。进程运行一会儿之后，会通过 sched() 和 swtch() 回到这个基地。

2. 调度器不是魔法 ​

调度器本质上是一个循环。

它扫描进程表，寻找 RUNNABLE 进程。

找到后切换过去。

简化图：

text
scheduler()
  |
  v
loop forever
  |
  v
scan proc[NPROC]
  |
  +-- if p->state == RUNNABLE
          |
          v
       run p
1
2
3
4
5
6
7
8
9
10
11
12

RUNNABLE 表示进程已经准备好运行。

RUNNING 表示进程正在某个 CPU 上运行。

text
RUNNABLE
  |
  | scheduler chooses it
  v
RUNNING
  |
  | yield / sleep / exit
  v
not running anymore
1
2
3
4
5
6
7
8
9

调度器只选择能运行的进程。

它不会运行 SLEEPING。

也不会运行 ZOMBIE。

3. struct cpu 和 struct proc ​

每个 CPU/hart 有一个 struct cpu。

每个进程有一个 struct proc。

两者关系：

text
struct cpu
  |
  +-- proc -------> currently running struct proc
  |
  +-- context ----> scheduler context

struct proc
  |
  +-- context ----> process kernel context
1
2
3
4
5
6
7
8
9

CPU 是执行资源。

进程是被执行对象。

一个 CPU 某一刻最多运行一个进程。

一个进程某一刻也最多在一个 CPU 上运行。

text
CPU 0 -> proc A
CPU 1 -> proc B
CPU 2 -> scheduler idle loop
1
2
3

cpu->proc 表示当前 CPU 正在运行哪个进程。

当 CPU 回到调度器时，通常会清空这个指针。

4. struct context ​

上下文是恢复执行所需的寄存器集合。

xv6 的 struct context 保存：

text
ra
sp
s0-s11
1
2
3

图：

text
struct context
  |
  +-- return address
  +-- stack pointer
  +-- saved registers
1
2
3
4
5

为什么保存这些？

因为它们足以恢复内核执行路径。

swtch.S 不是保存用户寄存器。

用户寄存器由 trapframe 负责。

区别：

text
trapframe
  |
  +-- user registers
  +-- user/kernel trap boundary

context
  |
  +-- kernel saved registers
  +-- scheduler/process switch boundary
1
2
3
4
5
6
7
8
9

这是 xv6 学习最重要的区分之一。

5. swtch.S 做什么 ​

swtch.S 接收两个 context 指针。

text
swtch(old, new)
1

它做：

text
save current registers into old
  |
  v
load registers from new
  |
  v
return into new context
1
2
3
4
5
6
7

这句“return into new context”很关键。

恢复了新的 ra 和 sp 后，函数返回的位置和栈都变了。

图：

text
before swtch

CPU executing Process A kernel stack
  |
  v
swtch(&A.context, &CPU.context)

after swtch

CPU executing Scheduler stack/context
1
2
3
4
5
6
7
8
9
10

再切到 B：

text
Scheduler
  |
  v
swtch(&CPU.context, &B.context)
  |
  v
Process B resumes
1
2
3
4
5
6
7

swtch.S 不负责选择进程。

它只负责低层寄存器切换。

选择进程是 scheduler() 的工作。

6. scheduler() 主循环 ​

scheduler() 每个 CPU 都会运行。

它大致做：

text
for ever:
  enable interrupts
  for p in proc:
    acquire p->lock
    if p->state == RUNNABLE:
      p->state = RUNNING
      c->proc = p
      swtch(&c->context, &p->context)
      c->proc = 0
    release p->lock
1
2
3
4
5
6
7
8
9
10

图：

text
CPU scheduler context
  |
  v
scan process table
  |
  v
choose RUNNABLE proc
  |
  v
mark RUNNING
  |
  v
swtch to proc context
  |
  v
process runs
  |
  v
process eventually swtch back
  |
  v
scheduler continues loop
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里的锁很重要。

调度器查看和修改 p->state 时，需要持有 p->lock。

否则其他 CPU 可能同时改变这个进程状态。

7. yield()：主动让出 CPU ​

yield() 表示当前进程主动放弃 CPU。

常见触发：

  • 定时器中断后内核希望让出。
  • 内核代码主动让其他进程运行。

简化流程：

text
yield()
  |
  v
current proc p
  |
  v
acquire p->lock
  |
  v
p->state = RUNNABLE
  |
  v
sched()
  |
  v
release p->lock
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

状态：

text
RUNNING
  |
  | yield
  v
RUNNABLE
1
2
3
4
5

yield() 不代表进程结束。

它只是说：

我现在可以以后再运行。

调度器稍后可能再次选择它。

8. sched()：切回调度器 ​

sched() 是当前进程切回调度器的核心函数。

它会检查一些条件。

例如：

  • 当前进程锁是否持有。
  • 当前进程不应该还是 RUNNING。
  • 中断状态是否符合预期。

然后调用：

text
swtch(&p->context, &mycpu()->context)
1

图：

text
process kernel context
  |
  v
sched()
  |
  v
swtch process -> scheduler
  |
  v
scheduler context
1
2
3
4
5
6
7
8
9
10

sched() 通常由：

  • yield()
  • sleep()
  • exit()

这些路径调用。

它表示当前进程不再继续占用 CPU。

9. 定时器中断如何引发调度 ​

定时器中断让内核获得周期性控制权。

路径：

text
user process running
  |
  v
timer interrupt
  |
  v
trap.c:usertrap()
  |
  v
yield()
  |
  v
sched()
  |
  v
scheduler()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这实现分时。

如果没有定时器中断，一个进程可能长期占用 CPU。

当然，进程也可能通过系统调用进入内核并阻塞。

调度发生的入口不只一个。

text
timer interrupt
  |
  +-- preemption-like yield

sleep syscall/path
  |
  +-- wait for event

exit
  |
  +-- stop running forever
1
2
3
4
5
6
7
8
9
10
11

10. 为什么调度器有自己的 context ​

调度器不是普通函数工具。

它也有执行上下文。

每个 CPU 的 struct cpu 中有 context。

text
struct cpu
  |
  +-- context: scheduler context
1
2
3

进程切回调度器时，要恢复 CPU 的 scheduler context。

否则 CPU 不知道回到调度循环哪里继续。

text
process p
  |
  v
swtch(&p->context, &cpu->context)
  |
  v
resume scheduler after previous swtch
1
2
3
4
5
6
7

这解释了 swtch 的神奇之处。

它返回时，可能不是返回到调用它的原始逻辑。

它返回到被恢复 context 的 ra。

11. 调度中的锁 ​

调度状态必须受锁保护。

例如：

text
p->state
c->proc
p->context
1
2
3

p->lock 保护进程状态。

调度器选择进程时持锁。

进程切回调度器时也要遵守锁约定。

为什么这么麻烦？

因为多 CPU 可能同时扫描进程表。

如果没有锁，可能两个 CPU 都看到同一个进程是 RUNNABLE。

然后两个 CPU 都运行它。

这会破坏进程隔离。

text
CPU 0 sees p RUNNABLE
CPU 1 sees p RUNNABLE
  |
  v
without lock both run p
1
2
3
4
5

锁阻止这种情况。

12. 调度不是公平算法研究 ​

xv6 调度器很简单。

它扫描进程表，选择 RUNNABLE 进程。

它不是复杂的现代调度器。

没有优先级队列。

没有 CFS。

没有实时调度类。

这正适合教学。

你先理解：

text
state
  |
  v
scheduler selection
  |
  v
context switch
1
2
3
4
5
6
7

以后学 Linux 时，再看更复杂的调度策略。

不要一开始就问 xv6 为什么不公平、不高效。

先理解它如何正确切换。

13. 常见误解 ​

误解一：调度器就是一个普通函数调用。

不准确。

调度器通过 swtch 和进程上下文来回切换。

误解二：swtch.S 负责选择下一个进程。

不是。

选择由 scheduler() 做。

swtch.S 只保存和恢复寄存器。

误解三：trapframe 和 context 都是上下文，所以一样。

不是。

trapframe 保存用户态现场。

context 保存内核调度现场。

误解四：RUNNABLE 就是正在运行。

不是。

RUNNABLE 是可运行但未必正在运行。

RUNNING 才是正在 CPU 上执行。

误解五：yield() 结束进程。

不是。

它只是让进程回到 RUNNABLE。

误解六：一个进程可以同时在多个 CPU 上运行。

不应该。

锁和状态转换要防止这种情况。

14. 小实验：打印调度切换 ​

实验目标：

观察进程从 RUNNABLE 到 RUNNING，再回到调度器。

可以在 scheduler() 中少量打印：

text
scheduler: hart=0 run pid=3
1

在 yield() 中打印：

text
yield: pid=3
1

注意：

打印不要太多。

调度非常频繁。

可以只打印特定 pid。

观察问题：

  • 同一个 pid 是否多次被调度？
  • 多个 hart 是否都进入 scheduler？
  • yield() 后进程是否还能继续运行？

15. 进程第一次被调度时发生了什么 ​

新进程不是一出生就在用户态运行。

它先拥有一个内核上下文。

allocproc() 会初始化这个上下文，让它第一次被调度时进入一条准备好的内核路径。

可以先用抽象图理解：

text
allocproc
  |
  +-- prepare p->context
  |
  v
process becomes RUNNABLE
  |
  v
scheduler chooses process
  |
  v
swtch to p->context
  |
  v
process starts at prepared kernel return path
  |
  v
eventually returns to user mode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里的重点不是某个单独字段。

重点是：

调度器切换到进程时，进程必须有一个可恢复的内核上下文。

否则 swtch 恢复后不知道从哪里继续执行。

所以 context 不只是“保存现场”。

对新进程来说，它还承担“首次运行入口”的作用。

text
existing process
  |
  +-- context saves where it yielded/slept

new process
  |
  +-- context is initialized to a prepared start path
1
2
3
4
5
6
7

这能帮助你理解为什么进程创建和调度紧密相关。

进程不是只要有 pid 就能跑。

它还要有：

  • 用户地址空间。
  • trapframe。
  • 内核栈。
  • context。
  • RUNNABLE 状态。

这些条件合起来，调度器才能真正切过去。

16. 调度时 CPU、栈和寄存器的关系 ​

上下文切换最难的地方，是它同时改变了寄存器和栈。

普通函数调用时，栈通常还在同一个执行流里。

swtch 之后，sp 会变成另一个上下文保存的栈指针。

text
before swtch

CPU registers
  |
  +-- sp -> Process A kernel stack
  +-- ra -> A's kernel path

after swtch to scheduler

CPU registers
  |
  +-- sp -> Scheduler stack/context
  +-- ra -> scheduler path
1
2
3
4
5
6
7
8
9
10
11
12
13

这就是为什么 swtch 看起来像函数，却不像普通函数。

它确实被调用。

但它返回时，返回到哪个路径取决于恢复的 ra。

如果恢复的是调度器上下文，就回到调度器。

如果恢复的是进程上下文，就回到进程之前停止的地方。

可以把 CPU 想象成一个“执行头”。

text
CPU execution head
  |
  +-- attach to scheduler context
  |
  +-- attach to process A context
  |
  +-- attach to process B context
1
2
3
4
5
6
7

上下文切换就是把这个执行头接到另一组寄存器和栈上。

17. 为什么调度器循环里要打开中断 ​

调度器循环中通常会允许中断。

原因是：

如果没有可运行进程，CPU 仍然要能接收设备中断或定时器中断。

否则系统可能停住。

text
no RUNNABLE process
  |
  v
scheduler idle scanning
  |
  v
interrupt arrives
  |
  v
device/timer event may wake process
1
2
3
4
5
6
7
8
9
10

例如某个进程正在等磁盘。

如果磁盘完成中断不能被处理，这个进程就无法被唤醒。

所以调度器不是简单“关起门来扫描数组”。

它要让硬件事件有机会进入内核。

这也说明：

调度、设备中断、sleep/wakeup 是一个整体。

text
process sleeps for I/O
  |
  v
scheduler runs something else
  |
  v
device interrupt arrives
  |
  v
wakeup sleeping process
  |
  v
scheduler can choose it again
1
2
3
4
5
6
7
8
9
10
11
12
13

18. 调度章节的源码阅读清单 ​

读本章相关源码时，建议按这个顺序：

text
proc.h
  |
  +-- struct context
  +-- struct cpu
  +-- struct proc

proc.c
  |
  +-- scheduler
  +-- yield
  +-- sched
  +-- sleep

swtch.S
  |
  +-- save old context
  +-- restore new context

trap.c
  |
  +-- timer interrupt calls yield
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

每个函数都问：

text
before function:
  |
  +-- current proc state?
  +-- which lock is held?
  +-- current CPU context?

after function:
  |
  +-- proc state changed?
  +-- did swtch happen?
  +-- who will run next?
1
2
3
4
5
6
7
8
9
10
11

如果能回答这些问题，调度器就不再神秘。

19. 小实验：区分 trapframe 和 context ​

实验目标：

观察 struct proc 中两个不同现场。

打印：

text
p->trapframe
&p->context
1
2

并记录：

text
trapframe used by syscall return
context used by swtch
1
2

尝试在 fork() 中观察：

text
child->trapframe->a0 = 0
1

再在 scheduler() 中观察：

text
swtch(&c->context, &p->context)
1

这能帮助你把两套机制分开。

20. 本篇总结 ​

xv6 调度可以压缩成：

text
proc state machine
  |
  v
scheduler selects RUNNABLE
  |
  v
swtch to process context
  |
  v
process eventually yields/sleeps/exits
  |
  v
swtch back to scheduler context
1
2
3
4
5
6
7
8
9
10
11
12
13

核心对象：

text
struct proc
  |
  +-- state
  +-- context

struct cpu
  |
  +-- proc
  +-- context

swtch.S
  |
  +-- save old context
  +-- restore new context
1
2
3
4
5
6
7
8
9
10
11
12
13
14

下一篇进入：

text
10-sleep-wakeup-and-wait-exit.md
1

调度解释“如何切换”。

sleep/wakeup 解释“进程为什么停止运行，又如何被唤醒”。

最后更新于:

Pager
上一篇9. xv6 进程与 struct proc / xv6 Process And struct proc
下一篇11. xv6 sleep/wakeup、wait 与 exit / xv6 Sleep Wakeup Wait And Exit

持续记录，持续成长

Copyright © Tidenflow