Linux任务调度(2)

演进过程 ##

首先，简要描述下Linux进程调度器的一个发展历史：

• v0.01~v2.4.x: the very first scheduler，复杂度O(n)
• v2.6.0~v2.6.22: O(1) scheduler，复杂度O(1)
• v2.6.23~: Completely Fair Scheduler (CFS)，复杂度O(log(n))

可能会有点好奇，只有这么几种吗？这是出现在内核源码树中的实现方案，研究探索过程中，涌现出的实现方案多的多，前一篇文章任务调度(1)中就提到过很多种方案，感兴趣可以了解下。本文只重点介绍内核源码树中真实出现过的调度器实现方案。

最早的版本 v0.01 ##

v0.01是最早的Linux内核版本。它的进程调度器只有20行代码，非常简单。作为对比，最新的Linux内核由数万行代码组成。

在v0.01中，所有的任务都由一个数组表示。这个数组不仅是所有任务的列表，还是运行队列。这个数组的长度是64。这意味着这个版本中的任务数最多为64个。在这个数组中，空的条目用NULL表示。

调度器的时间片是150毫秒。当前任务是否用尽了它的时间片是由一个称为间隔定时器的硬件检测的。间隔定时器每10毫秒中断一次CPU，然后调度器注册的处理程序被调用。这个函数减少当前任务的时间片，如果时间片变为零，调度器就会在运行队列中调度下一个可运行的任务。

在这个版本之后，时间片的值和定时器中断的间隔都发生了变化。然而，为了简单起见，本文不会逐一解释这些变化。

ps：进程切换的时机，v0.01里面是在系统调用返回前、时钟中断服务程序中检测是否需要进行进程切换。时钟中断处理时会递减当前进程的剩余时间片，为0后就会调度其他进程执行。

以下是Linux v0.01的进程调度器的调度算法：

1. 逆序遍历运行队列，并调度第一个时间片大于零的可运行进程，并且要是剩余时间片最大的进程。
2. 如果没有这样的进程，调度器会重置所有任务的时间片。在这里，调度器给可运行进程150毫秒的时间片，并将当前时间片的一半添加到休眠任务中。后者的原因是为了尽快调度唤醒的任务，以提高交互性。

我将用图示来展示上述算法的流程。

初始状态如下所示，时间片的单位是10毫秒：

首先，调度器以逆序遍历运行队列。在这里，t4被跳过，因为它正在休眠。此外，t2也被跳过，因为该条目为空。在遍历整个任务数组后，它发现t1的时间片是所有可运行任务中最大的。调度器调度t1运行，直到t1用光剩余的时间片。

调度器继续遍历，发现接下来t0是可运行的、剩余时间片最大的，于是调度t0运行直到时间片用光。在逆序遍历的过程中，如果发现了多个任务的剩余时间片同时为最大，那么选择第一个扫描到的进程执行。

最终所有的可运行的进程都被调度执行了，并且时间片全部用光变为0：

然后调度器会重置runqueue中所有可运行进程的时间片，比如150ms，也就是timeslice=150ms/10ms=15，对于睡眠状态的t4为了能让其从睡眠中恢复后尽快被调度以改善交互性，它的时间片等于=15+12/2=15+6=21。

当t4从睡眠中恢复时，t4的剩余时间片就是最大的了，但是调度器不一定就立即会调度它，因为调度的发生是在固定的时机才会触发，比如时钟中断处理程序发现当前进程时间片耗光了，或者当前进程要睡眠、退出或者执行其他系统调用需要让出CPU时。

ps：其实，在内核代码里面写法是这样的，就是说：最开始的时间片15是由优先级（nice值）确定的，counter»1对应的就是睡眠进程的时间片除以2的操作。

void schedule(void) {
    ...
	(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
    ...
}

如果你对这部分的源码实现感兴趣可以参考：https://github.com/hitzhangjie/linux-0.0.1-learning/blob/master/linux-0.0.1/kernel/sched.c#L82。

本文小结 ##

本文简单介绍了Linux内核调度器在演进过程中主要的实现版本，并先介绍了最最最早期的一个版本，也就是linux kernel v0.0.1版本中的调度器版本，真的是非常简单。但是这里面已经有了进程优先级、交互性的一些考量。毕竟是一个玩具版本，后面的版本中也对这个调度器做了一些改进。到了v2.6.0的时候引入了O(1)调度器，再后来v2.6.23引入了对公平性支持更好的CFS调度器，并且不断完善中。

接下来，会写几篇文章，再继续介绍下O(1)调度器和CFS调度器，欢迎阅读交流。

参考文献 ##

1. Linux Scheduler History, https://ops-class.org/slides/2017-03-03-schedulingstory/
2. Linux Scheduler: the very first schedulerhttps://dev.to/satorutakeuchi/a-brief-history-of-the-linux-kernel-s-process-scheduler-the-very-first-scheduler-v0-01-9e4
3. v0.0.1内核源码解析，https://github.com/hitzhangjie/linux-0.0.1-learning/blob/master/linux-0.0.1/kernel/sched.c#L82