MIT 6.S081 Lecture 11: Scheduling 1

13 Sep 2022

Sometimes life hits you in the head with a brick. Don’t lose faith.

6.S081第十一课，需要阅读课本第七章。课程教授OS调度的知识，详细介绍了xv6的调度实现。

Multiplexing

任何操作系统运行的进程都可能比计算机的cpu多，因此需要计划在进程之间共享cpu。理想情况下，共享对用户流程应该是透明的。一种常见的方法是，通过将进程多路复用到硬件CPU上，让每个进程误以为它拥有自己的虚拟CPU。

XV6在两种情况下将每个CPU从一个过程切换到另一个过程来多路复用。

当进程等待设备或管道I/O完成时，XV6的 sleep 和 wakeup 机制会切换进程，或者 wait 子进程 exit 或在 sleep 系统调用中等待。这是睡眠等待场景，下节课详细介绍。
定期切换，以应对长期计算而无需 sleep 的进程。这种多路复用产生了一个幻觉，即每个过程都有自己的CPU，就像XV6使用内存分配器和硬件页面表创建了每个过程都有自己的内存的幻觉。

针对这两个场景实现多路复用，有些不得不考虑的问题，

如何从一个进程切换到另一个进程？尽管上下文切换的思想很简单，但实现是xv6中最不透明的代码之一。
如何以一种对用户进程透明的方式强制切换？Xv6使用硬件计时器中断驱动上下文切换。
所有的cpu都在相同的进程集合之间切换，所以需要一个锁计划来避免竞争。
当进程退出时，必须释放进程的内存和其他资源，但它不能自己完成所有这些，因为它不能在使用自己的内核堆栈时释放它自己的内核堆栈。这需要内核的工作。
多核计算机的每个核心必须记住它正在执行的进程，以便系统调用影响正确进程的内核状态。
sleep 和 wakeup 允许进程放弃CPU，等待被另一个进程或中断唤醒。需要小心竞争 race，以避免丢失唤醒通知。

Context switching

像大部分 OS ，xv6 同样用到了线程抽象执行流与调度。不同的是，其用户进程只有一个线程：

xv6 kernel threads: they share kernel memory (thus locks)
xv6 user processes: one thread per process, so no sharing
linux: supports multiple threads sharing a user process’s memory

xv6的线程切换就是让CPU交错执行不同线程，一般说到的上下文，在这里是内核态某线程的寄存器（因为切换一定会进入内核态，用户的PC与控制寄存器等都已经存于 trapframe 了），

Trapframe: saved user registers
Context: saved kernel registers

切换流程是，

user -> kernel; saves user registers in trapframe
kernel thread -> scheduler thread; saves kernel thread registers in context
scheduler thread -> kernel thread; restores kernel thread registers from ctx
kernel -> user; restores user registers from trapframe

其中，xv6让每个CPU核上有一个 scheduler thread (也是内核态)。每一个CPU核运行的线程，

无限循环的 scheduler thread 调度 runnable 线程
或，运行一个实际的用户/内核线程

Scheduling

调度线程时重点关注的 struct proc 字段是，

p->trapframe holds saved user thread’s registers
p->context holds saved kernel thread’s registers
p->kstack points to the thread’s kernel stack
p->state is RUNNING, RUNNABLE, SLEEPING, &c
p->lock protects p->state (and other things…)

其中，锁保护 proc 的一致性，让以下步骤原子化，

p->state=RUNNABLE
save registers in p->context
stop using p’s kernel stack

其他的 CPU’s scheduler 就不会开始运行这个进程 p 直到它完成出让CPU，避免了多个CPU运行同一个线程。同理，让以下步骤原子化，

p->state=RUNNING
move registers from context to RISC-V registers

中断就不会 yield CPU ，可以让运行时的寄存器保证完全还原，进程可以正常运行。

因此，xv6的每个CPU一个 scheduler 线程会使得这里的加锁/解锁策略有点特殊。简单说就是，在不同的线程里加解同一个锁，

在将要切换的内核态线程的 yield 函数中加锁，则在 scheduler 线程解锁。
在 scheduler 线程解锁，则在内核态线程的 yield 函数中解锁，

Code

代码上，以下是将要切换的内核态线程将执行代码，

// in kernel/proc.c file
// Switch to scheduler.  Must hold only p->lock
// and have changed proc->state. Saves and restores
// intena because intena is a property of this
// kernel thread, not this CPU. It should
// be proc->intena and proc->noff, but that would
// break in the few places where a lock is held but
// there's no process.
void
sched(void)
{
  int intena;
  struct proc *p = myproc();

  if(!holding(&p->lock))
    panic("sched p->lock");
  if(mycpu()->noff != 1)
    panic("sched locks");
  if(p->state == RUNNING)
    panic("sched running");
  if(intr_get())
    panic("sched interruptible");

  intena = mycpu()->intena;
  swtch(&p->context, &mycpu()->context);
  mycpu()->intena = intena;
}

// Give up the CPU for one scheduling round.
void
yield(void)
{
  struct proc *p = myproc();
  acquire(&p->lock);
  p->state = RUNNABLE;
  sched();
  release(&p->lock);
}

而 scheduler 线程代码，

// Per-CPU process scheduler.
// Each CPU calls scheduler() after setting itself up.
// Scheduler never returns.  It loops, doing:
//  - choose a process to run.
//  - swtch to start running that process.
//  - eventually that process transfers control
//    via swtch back to the scheduler.
void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  
  c->proc = 0;
  for(;;){
    // Avoid deadlock by ensuring that devices can interrupt.
    intr_on();

    for(p = proc; p < &proc[NPROC]; p++) {
      acquire(&p->lock);
      if(p->state == RUNNABLE) {
        // Switch to chosen process.  It is the process's job
        // to release its lock and then reacquire it
        // before jumping back to us.
        p->state = RUNNING;
        c->proc = p;
        swtch(&c->context, &p->context);

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;
      }
      release(&p->lock);
    }
  }
}

其中的 swtch 函数，切换上下文，通过修改寄存器 ra 的内容，在函数返回时就返回到目标线程的代码地址。而只有 switch() 写入上下文(初始化除外)，只有 sched() 和 scheduler() 调用 switch()，因此对于内核线程，上下文中的 ra 总是指向 sched() 中，而对于 scheduler 线程，则指向 scheduler() 。

在这里，sched() 与 scheduler() 就是 “co-routines” 也就是所谓的协程。协程的每个线程都知道它切换的下一个线程，也都知道从何线程切换而来，并同时协调处理数据，在这里 yield() 与 scheduler 协调处理 p->lock 与 p->state 。而普通的线程切换机制下，没有线程知道哪个线程在之前/之后。

Why does scheduler() enable interrupts periodically?

可能没有 RUNNABLE 线程。因为所有线程有可能都在等待 I/O 操作。打开中断以便设备有机会标记一个 I/O 的完成，然后唤醒相关线程。否则，可能陷入死锁。

What is xv6’s scheduling policy?

xv6调度策略十分简单，每次查找 RUNNABLE 线程，如果有多个，优先级没有考虑。现代 OS 有多级反馈队列用以调度。

Why does sched() forbid locks from being held when yielding the CPU?

除了 p->lock 其他锁都会被检查（通过 mycpu()->noff 检查锁的个数是否为一），禁止在调度时持有。这也是为了避免死锁。

比如 P1 持有自旋锁 L1 然后让出CPU，CPU调度 P2 且 P2 申请 L1 。由于 P2 关闭中断，计时器中断不会产生效果，所以 P2 不会让出 CPU 而 P1 也无法完成执行释放 L1 。最后死锁。

Could we get rid of separate, percore scheduler thread?

这样实现也可以，甚至更快，因为避免了一个 swtch 调用。但这样需要仔细考虑，

scheduling loop 在一个线程的内核栈上运行。
线程的退出变得更为复杂。
如何让其他 CPU 有可能运行这个线程。
当线程数少于 CPU 时如何工作?

Conclusion

Xv6通过计时器中断抢占，通过透明地交换寄存器与栈，为内核代码提供了一个方便的线程模型。多核需要仔细处理栈、锁，做到保证无死锁的切换线程。通过每个CPU一个 scheduler 线程，以协程的思路完成线程切换，xv6的多路复用模型相对易懂，值得学习。

Reference

system-programming