xv6-riscv 使用一个非常简单且经典的调度算法：轮询调度（Round-Robin）。

它没有复杂的优先级或时间片计算，其核心思想是公平地让每个处于“可运行”状态的进程轮流使用 CPU。

下面我将从几个关键方面来解析它：

1. 核心思想

  1. 公平轮换：调度器会遍历一个进程列表，寻找状态为 RUNNABLE（可运行）的进程。
  2. 找到即运行：一旦找到一个 RUNNABLE 的进程，调度器就会切换到该进程的上下文中，让它开始执行。
  3. 协作式放弃：一个正在运行的进程会一直执行，直到它主动放弃 CPU。放弃 CPU 的情况通常有以下几种：
    • I/O 等待：进程需要等待磁盘、键盘等设备的数据，这时它会调用 sleep() 进入 SLEEPING 状态。
    • 时间片中断：硬件定时器会周期性地触发中断。在中断处理程序中，会调用 yield()，使当前进程放弃 CPU，变为 RUNNABLE 状态，从而让其他进程有机会运行。
    • 进程主动让出：进程可以显式调用 yield() 来主动让出 CPU。
    • 进程终止：进程执行完毕或被杀死，会进入 ZOMBIE 状态，等待父进程回收资源。

2. 关键数据结构

调度系统的核心是进程控制块（Process Control Block, PCB）和进程表。

  • struct proc（定义于 kernel/proc.h）：这是 xv6 的 PCB。它包含了关于一个进程的所有信息，其中与调度最相关的字段是：
    • state：一个枚举类型（enum procstate），表示进程的当前状态（UNUSED, USED, SLEEPING, RUNNABLE, RUNNING, ZOMBIE）。
    • context：一个 struct context，保存了进程的寄存器状态。当进程不在 CPU 上运行时，它的所有寄存器值（包括程序计数器 pc 和栈指针 sp）都保存在这里，以便将来恢复执行。
    • kstack：指向该进程的内核栈。
  • 进程表 proc[]（定义于 kernel/proc.c):这是一个全局数组，struct proc proc[NPROC];，它包含了系统中所有可能存在的进程的 struct proc 结构。调度器就是通过遍历这个数组来寻找下一个要运行的进程。

3. 主要函数和执行流程

调度的逻辑主要分布在几个关键函数中。

  • scheduler()（定义于 kernel/proc.c）： 这是调度器的核心循环，每个 CPU 核心都有一个独立的 scheduler 线程。它的逻辑非常简单：
    1. 进入一个无限循环（for(;;)）。
    2. 遍历 proc 进程表。
    3. 如果发现一个进程的状态是 RUNNABLE：
      • a. 将该进程状态设置为 RUNNING。
      • b. 通过调用 swtch() 函数，进行上下文切换，开始执行该进程。
      • c. swtch() 返回后（意味着该进程已放弃 CPU），将当前 CPU 的 proc 指针清空。
  • yield()（定义于 kernel/proc.c）： 当一个进程想要主动放弃 CPU 时调用。
    1. 将当前进程的状态从 RUNNING 改为 RUNNABLE。
    2. 调用 sched()，sched() 内部会调用 swtch() 切换到调度器（scheduler）的上下文中。
  • sleep(channel, lock)（定义于 kernel/proc.c）： 当进程需要等待某个事件（由 channel 标识）时调用。
    1. 设置进程的 chan 字段为 channel。
    2. 将进程状态设置为 SLEEPING。
    3. 调用 sched() 切换到调度器。
      • 注意：lock 参数是为了解决“丢失唤醒”（Lost Wakeup）问题，确保进程在进入睡眠状态前，不会错过唤醒信号。
  • wakeup(channel)（定义于 kernel/proc.c）： 唤醒所有在 channel 上等待的进程。
    1. 遍历 proc 进程表。
    2. 找到所有状态为 SLEEPING 且 chan 字段匹配的进程。
    3. 将它们的状态改为 RUNNABLE，这样它们就有机会在下一次调度中被执行。
  • swtch()（定义于 kernel/swtch.S）： 这是一个底层的汇编函数，负责实际的上下文切换。它做两件事：
    1. 保存：保存当前上下文（寄存器）到指定的 struct context 中。
    2. 恢复：从目标 struct context 中加载寄存器，从而切换到新的执行流。

4. 代码位置

如果你想深入研究代码，可以关注以下几个文件：

  • kernel/proc.c：实现了 scheduler(), yield(), sleep(), wakeup() 等核心调度逻辑。
  • kernel/proc.h：定义了 struct proc, struct context 和进程状态 enum procstate。
  • kernel/swtch.S：实现了底层上下文切换的汇编代码。
  • kernel/trap.c：在 usertrap() 函数中处理时钟中断，并调用 yield() 来强制进程放弃 CPU，实现抢占效果。

总而言之，xv6 的调度器通过一个简单的轮询策略，在 RUNNABLE 进程之间进行切换。它依赖于进程状态的转换（通过 sleep, wakeup, yield 等函数）和底层的上下文切换机制（swtch）来实现多任务处理。这是一个学习操作系统调度的绝佳范例。