调度器作为操作系统的核心子系统，具有非常重要的意义。linux的调度器随着内核的更新也不断的进行着更新。 本文通过redhat的kernel（linux-3.10.0-862）源码进行调度器的学习和分析，一步一步将调度器的细节展示出来。 相信大家通过对本文的学习，能够轻松的分析其它内核版本的调度器源码。

调度器介绍

随着时代的发展，linux也从其初始版本稳步发展到今天，从2.4的非抢占内核发展到今天的可抢占内核，调度器无论从代码结构还是设计思想上也都发生了翻天覆地的变化，其普通进程的调度算法也从O(1) 到现在的CFS，一个好的调度算法应当考虑以下几个方面：

  • 公平：保证每个进程得到合理的CPU时间。
  • 高效：使CPU保持忙碌状态，即总是有进程在CPU上运行。
  • 响应时间：使交互用户的响应时间尽可能短。
  • 周转时间：使批处理用户等待输出的时间尽可能短。
  • 吞吐量：使单位时间内处理的进程数量尽可能多。
  • 负载均衡：在多核多处理器系统中提供更高的性能。

而整个调度系统至少包含两种调度算法，是分别针对实时进程和普通进程，所以在整个linux内核中，实时进程和普通进程是并存的，但它们使用的调度算法并不相同，普通进程使用的是CFS调度算法(红黑树调度)。之后会介绍调度器是怎么调度这两种进程。

进程

在linux中，进程主要分为两种，一种为实时进程，一种为普通进程：

  • 实时进程：对系统的响应时间要求很高，它们需要短的响应时间，并且这个时间的变化非常小，典型的实时进程有音乐播放器，视频播放器等。
  • 普通进程：包括交互进程和非交互进程，交互进程如文本编辑器，它会不断的休眠，又不断地通过鼠标键盘进行唤醒，而非交互进程就如后台维护进程，他们对IO，响应时间没有很高的要求，比如编译器。

它们在linux内核运行时是共存的，实时进程的优先级为0-99，实时进程优先级不会在运行期间变(静态优先级)，而普通进程的优先级为100-139，普通进程的优先级会在内核运行期间进行相应的改变(动态优先级)。

调度策略

在linux系统中，调度策略分为：

  • SCHED_NORMAL: 普通进程使用的调度策略，现在此调度策略使用的是CFS调度器。
  • SCHED_FIFO： 实时进程使用的调度策略，此调度策略的进程一旦使用CPU则一直运行，直到有比其优先级高的实时进程进入队列，或者其自动放弃CPU，适用于时间性要求比较高，但每次运行时间比较短的进程。
  • SCHED_RR:实时进程使用的时间片轮转法策略，实时进程的时间片用完后，调度器将其放到队列的末尾，这样每个实时进程都可以执行一段时间。适用于每次运行时间比较长的实时进程。
  • SCHED_BATCH：
  • SCHED_IDLE：
  • SCHED_DEADLINE：

内核源码中，调度策略的定义存在于文件include/uapi/linux/sched.h:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/*
 * Scheduling policies
 */
#define SCHED_NORMAL            0
#define SCHED_FIFO              1
#define SCHED_RR                2
#define SCHED_BATCH             3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE              5
#define SCHED_DEADLINE          6

调度

内核中__schedule函数是调度器的核心函数，其作用是让调度器选择和切换到一个合适进程运行。

首先，我们需要清楚，什么样的进程会进入调度器进行选择，就是处于TASK_RUNNING状态的进程，而其他状态下的进程都不会进入调度器进行调度。系统发生调度的时机是什么呢？大致可以分为以下几种： （1）阻塞操作：互斥量(mutex)，信号量(semaphore)，等待队列(waitqueue)等。 （2）在中断返回前和系统调用返回用户空间前，去检查TIF_NEED_RESCHED标志位来判断是否需要调度。 （3）将要被唤醒的进程并不会立刻调用schedule()要求被调度，这些进程会被添加到CFS就绪队列中，并设置了TIF_NEED_RESCHED标志位。那么这些唤醒的进程什么时候被调度呢？根据内核是否具有可抢占功能分两种情况：

  • 如果可抢占（默认开启），则
    • 如果唤醒动作发生在系统调用或者异常处理上下文中，在下一次调用preempt_enable()时会检查是否需要抢占调度(多次调用preempt_enable()时，系统只会在最后一次调用时会调度)
    • 如果唤醒动作发生在硬中断处理上下文中，硬件中断处理返回前夕会检查是否需要抢占当前进程。
  • 如果内核不可抢占，则
    • 当前进程调用cond_resched()时会检查是否要调度
    • 显式调用schedule()时
    • 从系统调用或者异常处理返回用户空间时
    • 从中断处理上下文返回用户空间时

注意：硬件中断返回前夕和硬件中断返回用户空间前夕是两个不同的概念。前者是每次硬件中断返回前夕都会检查是否有进程需要被抢占调度，不管中断发生点是在内核空间，还是用户空间；后者是只有中断发生点在用户空间才会检查。

而在系统启动调度器初始化时会初始化一个调度定时器，调度定时器每隔一定时间执行一个中断，在该中断处理程序中会对当前运行进程运行时间进行更新，如果进程需要被调度，在调度定时器中断中会设置一个调度标志位，之后从定时器中断返回，因为上面已经提到从中断上下文返回时是有调度时机的，在内核源码的汇编代码中所有中断返回处理都必须去判断调度标志位是否设置，如设置则执行schedule()进行调度。

而我们知道实时进程和普通进程是共存的，调度器是怎么协调它们之间的调度的呢，其实很简单，每次调度时，会先在实时进程运行队列中查看是否有可运行的实时进程，如果没有，再去普通进程运行队列找下一个可运行的普通进程，如果也没有，则调度器会使用idle进程进行运行。之后的章节会放上代码进行详细说明。

系统并不是每时每刻都允许调度的发生，当处于硬中断期间的时候，调度是被系统禁止的，之后硬中断过后才重新允许调度。而对于异常，系统并不会禁止调度，也就是在异常上下文中，系统是有可能发生调度的。