第二章 · Stride 步长调度

TODO

运行方式：

make clean && make qemu SCHED=STRIDE CPUS=1

进入 xv6 shell 后运行：

stridetest

系统调用是怎么注册的？

以 getpinfo(ps) 为例，从用户程序到内核逻辑一共 4 步：

1. 用户态：user/user.h 定义 struct pstat，声明 int getpinfo(struct pstat*)，用户程序把数组地址传给它。

2. 陷入内核：每个系统调用都需要一段完全重复的汇编——把调用号写进 a7 寄存器，执行 ecall，然后 ret 返回。手写几十份太麻烦了，所以 xv6 用了一个 perl 脚本 user/usys.pl 来自动生成这些 stub 代码。本实验已经写好 entry("getpinfo")，make 时它会生成：

   .globl getpinfo
   getpinfo:
     li a7, SYS_getpinfo  # li = load immediate，把立即数加载到寄存器
     ecall
     ret

3. 分派：ecall 指令陷入内核后，kernel/syscall.c 的 syscall() 读取 a7 的值，在 syscalls[] 数组里找到对应的处理函数。

4. 执行：kernel/sysproc.c 的处理函数用 argaddr() 取出用户数组地址，调用 kernel/proc.c 里的 getpinfo()，再由内核侧 copyout() 拷回用户空间。

每加一个系统调用，需要改 5 个文件：

本章中，settickets 和 getpinfo 的注册样板都已经接好。你需要读懂这条路径，然后在 kernel/proc.c 里真正实现 getpinfo() 的状态采集和 copyout()。

1. 从 RR 到 Stride

RR 调度默认所有可运行进程平等：大家轮流获得 CPU。Stride 调度多了一个目标：允许不同进程按权重获得不同份额。

这个权重用 tickets 表示：

• tickets 多：应该获得更多 CPU 时间。
• tickets 少：应该获得更少 CPU 时间。

Stride 的核心思想只有一句话：

每次选择 pass 最小的进程运行；进程每运行一次，就让它的 pass += stride。

三个字段的含义如下：

2. 一个 1:2:4 的例子

假设：

STRIDE_BIG = 1000000
A: tickets=1, stride=1000000
B: tickets=2, stride=500000
C: tickets=4, stride=250000

初始时三者 pass 都是 0。遇到相同 pass 时，可以用 pid 小的进程作为稳定的 tie-break。

7 轮之后，A 跑了 1 次，B 跑了 2 次，C 跑了 4 次。比例就是 1:2:4。

这不是巧合。pass 可以理解成“每个进程自己的虚拟里程”。调度器总是让最落后的进程先走一步。tickets 越多，单步越短，所以它需要走更多步才能追上别人。

3. 为什么 STRIDE_BIG 要大？

stride = STRIDE_BIG / tickets 是整数除法。整数除法会截断小数，所以 STRIDE_BIG 太小时，不同比例会被压扁。

举一个极端例子：

STRIDE_BIG = 10
tickets=6  -> stride=1
tickets=9  -> stride=1

这两个进程明明票数不同，但算出来的 stride 一样，调度器就看不出它们的权重差异。

如果改成：

STRIDE_BIG = 1000000
tickets=6  -> stride=166666
tickets=9  -> stride=111111

差异就保留下来了。

可以用一个简单判断来理解当前常量：

SCHED_MAX_TICKETS = 10000
STRIDE_BIG = 1000000
最小 stride = 1000000 / 10000 = 100

最小 stride 仍然不是 0，说明最大票数的进程每次运行后也会推进虚拟时间。

4. 用 2π 的圆周理解循环加法

pass 一直增加，理论上总有一天会超过整数能表示的最大值。无符号整数不是一条无限长的数轴，而是一圈固定长度的圆：走到最大值后，下一步会回到 0。

这就是“循环加法”：走到圆周末尾后，不是停下，而是回到起点继续走。它和时钟很像：23 点再过 2 小时不是 25 点，而是 1 点。

如果你更习惯用圆周率想象，可以把一圈看成 2π。角度从 0 开始不断加，超过 2π 后不会离开圆，而是回到同一个圆周上继续走。无符号整数的加法也是这个感觉：最大值后面接着的是 0。

如果以后要写长期运行的内核，才需要认真处理“绕回 0 后如何比较先后”的问题。本实验重点仍然是 stride 的比例思想和锁协议。

5. 代码怎么写？

初始化进程

新进程创建时，需要给调度字段默认值：

void
sched_init_proc(struct proc *p)
{
  p->tickets = SCHED_DEFAULT_TICKETS;
  p->stride = stride_for_tickets(p->tickets);
  p->pass = 0;
}

在 freeproc() 中清零这些字段，是为了避免 proc 槽位复用时带入旧进程的 pass。

settickets

settickets(n) 的系统调用路径已经接好，你只需要实现内核里的更新逻辑：

int
sched_set_tickets(struct proc *p, int tickets)
{
  if(tickets < 1 || tickets > SCHED_MAX_TICKETS)
    return -1;

  acquire(&p->lock);
  p->tickets = tickets;
  p->stride = stride_for_tickets(tickets);
  release(&p->lock);
  return 0;
}

选择 pass 最小的进程

核心逻辑拆成两个函数：

sched_scan_best() 扫描 proc[]，找到 pass 最小的 RUNNABLE 进程：

struct proc *best = 0;

for(p = proc; p < &proc[NPROC]; p++) {
  acquire(&p->lock);
  if(p->state == RUNNABLE && 比 best 更应该运行) {
    if(best != 0)
      release(&best->lock);
    best = p;
  } else {
    release(&p->lock);
  }
}

return best;

比较规则：p->pass < best->pass || (p->pass == best->pass && p->pid < best->pid)。

sched_commit() 更新被选中进程的虚拟时间：

if(best != 0)
  best->pass += best->stride;

sched_pick_stride() 只是串起这两步。返回时 best 保持锁，交给 scheduler() 在切回来后释放。

6. stridetest 测什么？

stridetest 是本章的正确性检查程序，需要你在 user/stridetest.c 中补全。它沿用 ch1 练过的 pipe -> fork -> read -> wait 结构，但检查重点变成 stride 调度的三个核心行为：

写 stridetest 时不要重新设计一套并发结构。它的 pipe/fork/read/wait 和 schedtest 基本相同，新增的是三组状态：

check_pinfo() 的逻辑可以按三步写：先调用 getpinfo(ps)；再遍历 ps[]，用 ps[i].pid == pids[j] 找到目标子进程并检查 ps[i].tickets == tickets[j]；最后检查 seen[]，确认三个子进程都被找到。

三个子进程分别调用：

settickets(1);
settickets(2);
settickets(4);

子进程忙循环一段固定 tick 数，父进程收集每个子进程的 loops，并调用 getpinfo() 确认内核记录的 tickets 与 1、2、4 对应。你要补全的不是“再写一个 schedtest”，而是把用户态结果和内核态调度状态对上：哪个 pid 设置了多少 tickets，最终循环次数是否符合大致比例趋势。

正确时应该看到：

stridetest: tickets 1:2:4, 120 ticks
child 0: tickets=1 elapsed=122 loops=50092
child 1: tickets=2 elapsed=121 loops=98546
child 2: tickets=4 elapsed=120 loops=190619
stridetest: PASS

具体数字会因机器而变。判断重点是：

loops[0] < loops[1] < loops[2]

stridetest 不要求每次调度都严格按 1:2:4 出现，也不要求短时间窗口内的 delta 精确成比例。调度受 tick、启动顺序、父进程收集结果等因素影响，短期数字会抖动；只要长期趋势稳定递增，并且 getpinfo() 能返回正确状态，就说明这个测试覆盖的行为成立。

7. schedtrace 看什么？

schedtrace 是已经提供好的时间序列观察工具，不需要你补代码。它适合在 getpinfo() 基本可用之后运行，用来观察 stride 调度“一步步如何变化”，而不是作为 PASS/FAIL 判题程序。

它会启动几个不同 tickets 的 CPU-bound 子进程，并每隔一段时间调用 getpinfo()，打印这些进程的调度状态：

• tickets
• stride
• pass
• sched_count
• 本轮 sched_count 增量，也就是这一小段时间里进程又被调度了多少次

推荐在单核 stride 下观察：

make clean && make qemu SCHED=STRIDE CPUS=1
schedtrace

输出形态类似：

tick 128
pid tickets state  count delta stride pass
4   1       runble  10    +2   1000000 9010000
5   2       runble  19    +6   500000 9010000
6   4       runble  37    +12  250000 9010000

读这个输出时，重点看三件事：

因此，schedtrace 主要帮助你看懂时间序列：高 tickets 进程的 delta 通常更大，多个进程的 pass 会围绕相近的虚拟时间来回追赶。它不要求每一轮 delta 都严格等于 1:2:4，也不替代 stridetest 的最终正确性检查。

常见错误