背景

大家都知道，操作系统的一个最核心功能之一就是做任务的调度。通过将某个CPU 核在多个可执行的任务之间切换运行，任务调度器可实现多个任务共享一个或多个CPU 核，从而最大化的利用CPU核心资源。同时，通过快速的任务切换，可以让用户感觉大于CPU 核心的数量的任务被同时执行，实现并发操作。

一般来说，根据需要，常见的任务调度算法有: FCFS， SJF， RR， priority-scheduling， multilevel queue， multilevel feedback queue。 这些算法很多操作系统书籍都有详细描述，这里就不详细介绍了。

任务调度器是否要用单独的线程

操作系统任务调度器是否需要一个单独的线程？答案是可以用也可以不用。本章节分别用MIT Operating System Engineering 课程教学用的xv6 操作系统 和 linux 操作系统 作为 示例来说明两种实现方案。

xv6

xv6 是运行在由qemu 模拟的多核RISC-V 处理器上的, ，qemu还模拟了 UART 16550 芯片， CLINT，和磁盘镜像，以实现基本的输入输出，时间中断和文件系统功能。

xv6 的详细代码 可通过git 获取:

git clone git://github.com/mit-pdos/xv6-riscv.git

xv6 启动时，所有的RISC-V 核 会从0x80000000 开始执行内核代码。在完成一系列的操作系统初始化后，所有的核都会进到自己的线程调度器。调度器函数是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);
    }
  }
}

由于在初始化阶段，每个CPU核都有自己单独的栈区域，所以此时每个核的调度器都在一个单独的线程里执行。

scheduler() 会从进程数组中选择一个状态为RUNNABLE的，然后通过调用swtch() 将上下文切换到这个进程运行。

当时间中断发生时，中断处理程序会调用yield()，yield() 先将进程的状态从RUNNING 改为 RUNNABALE，然后再通过sched() 调用swtch 将上下文切换到当前CPU 核的调度线程，调度线程按照以上方式完成任务切换。

void
yield(void)
{
  struct proc *p = myproc();
  acquire(&p->lock);
  p->state = RUNNABLE;
  sched();
  release(&p->lock);
}
```

```c
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;
}

进程也会主动放弃CPU资源进入睡眠状态，这时sleep() 先将进程的状态从RUNNING 改为 SLEEPING, 然后同样再通过sched() 调用swtch 将上下文切换到当前CPU 核的调度线程，由调度线程完成任务切换。

void
sleep(void *chan, struct spinlock *lk)
{
  struct proc *p = myproc();
  
  // Must acquire p->lock in order to
  // change p->state and then call sched.
  // Once we hold p->lock, we can be
  // guaranteed that we won't miss any wakeup
  // (wakeup locks p->lock),
  // so it's okay to release lk.

  acquire(&p->lock);  //DOC: sleeplock1
  release(lk);

  // Go to sleep.
  p->chan = chan;
  p->state = SLEEPING;

  sched();

  // Tidy up.
  p->chan = 0;

  // Reacquire original lock.
  release(&p->lock);
  acquire(lk);
}

可见，xv6将调度器放在单独的线程中，系统需要任务切换时，需要先将当前任务切换到调度器线程，然后调度器线程根据调度算法切换到其他的任务。

xv6将调度器放在专门的线程中主要考虑是用简单的方法避免多个CPU 核 同时执行同一个RUNNABLE状态的任务，从而造成栈使用干涉:

如下图所示当时间中断发生时，当前任务调用yield()， 将任务状态从RUNNING 改成UNNABLE，接下来通过swtch()做任务切换；每个任务的状态由一个自旋锁保护，这个锁必须在swtch() 完成任务切换时才能释放，否则在任务切换过程中，另一个CPU 核可能会执行当前任务，造成混乱。xv6将当前任务切换到任务调度线程后，scheduler() 第一件事就是释放前一个任务的状态保护自旋锁，前一个任务便可以被其他的CPU 核执行。而当前CPU核的任务调度线程可以按照任务调度算法选择切换到其他RUNNABLE任务执行。

如果任务调度器不在一个专门的线程中，xv6需要在下一个任务中改变上一个任务的状态，并释放任务状态保护自旋锁，导致内核的设计比较复杂。 

 将任务调度器放在一个专门的线程中，缺点是增加了任务切换的开销，每次需要通过两次任务切换才能将一个进程切换到另一个进程。但是，由于xv6只是用于教学用的比较简单的操作系统，任务切换的开销很小，因此两次任务切换对系统性能影响不大。

Linux

linux内核代码可从官方网站下下载: http://www.kernel.org

linux内核启动的过程比xv6复杂的多，这里就不详细描述了。本章节主要描述linux任务调度器是否由专门的线程实现。

<未完待续>