Linux调度子系统整体架构

1 为什么需要进程调度

我们实际的情况其实是任务数多于CPU数量的，并且一个时刻CPU只能运行一个任务。
假设只有一个CPU，有三个任务ABC，这时候如果A占用CPU，那么B和C就只能等待，
那为什么我们有时候感觉所有任务都是一起运行的呢？
这是因为操作系统让任务在CPU上并发执行，简单的说就是不停的快速切换任务。
把CPU想象成超人就行了。

那什么是进程调度呢？就是决定那个任务在当前时刻可以获取CPU的使用权，以及任务可以运行多长时间。
内核中的调度对象是一个task

struct task_struct

最简单的调度模型如下

每次切换前先保存当前任务的运行现场，方便切换回来。这个过程叫上下文切换，后面会讲。

调度器要解决那些问题呢？就是调度指标是什么呢？

• 公平性：首先就是CPU的使用权，不可能让一个任务一直运行，没有意义，
  应该尽量合理的安排每个CPU的使用时间
• 响应速度：比如一些重要的交互任务要快速反应
• 吞吐量：单位时间内完成的任务
• 优先级：有些任务比较急，优先占用CPU的使用权
• CPU亲和性：有些任务只允许在指定 CPU 上运行。

把调度器想成一个选择器，输入是各种调度指标，输出是下一个占用CPU的task。

2 进程、线程和 task

这三个东西，傻傻分不清吧？😛
进程就是运行的程序，比如你在终端执行的

./app

不同的进程都是隔离，有自己独立的资源，就像QQ农场里面的一块一块的田地。

线程是进程里面的一条执行路线（就是种的菜），一个进程可以包含多个线程（一块地种多个菜）。
他们会共享进程的资源，但是有自己的独立现场。（共享一块地，各自长的不同）
如图所示，假设一个进程由两个线程

在内核中对应的就是task，表示一个可执行对象。
其定义简化为

struct task_struct {
    pid_t pid;
    pid_t tgid;

    volatile long state;

    int prio;
    unsigned int policy;

    struct mm_struct *mm;
    struct files_struct *files;

    struct sched_entity se;

    struct task_struct *parent;

    ...
};

进程和线程在内核中的对应形式都是task，区别就是资源的占有权。
比如同一个进程的线程会使用同一个struct mm_struct *mm。

内核中会为每个task分配唯一id

task->pid

对于同一进程的不同线程会被分到一个线程组里，并给一个线程组id

task->tgid

假设三个线程ABC

task	pid	tgid
A	1000	1000
B	1001	1000
C	1002	1000

3 task状态

进程和线程的整个生命周期由五个状态，如图

对于调度而言，有三个非常重要的概念

Running    正在CPU上执行
Runnable   已经具备运行条件，正在等待CPU
Sleeping   暂时不能运行，正在等待某个事件

怎么获取当前正在Running的指针呢？当然是用指针啦，
在内核中，每个 CPU 都有一个当前任务指针，简单理解为current

struct task_struct *p = current;

而每个CPU的 runqueue 中有rq->curr指向当前运行的task

在内核中通过pick_next_task()选中Runnable的task，完成一次调度
上面两种状态都被定义为

#define TASK_RUNNING 0x00000000

对于Sleeping，内核中定义了两种重要的睡眠状态

TASK_INTERRUPTIBLE
TASK_UNINTERRUPTIBLE

可中断睡眠：表示 task 正在等待某个事件，但信号也可以唤醒或中断它。
不可中断睡眠：表示 task 正在等待某个内核事件，普通信号不能使它立即离开等待状态；预期由它正在等待的事件完成后唤醒，而不是随意被普通信号打断

4 runqueue 是什么

runqueue就是每个CPU管理可运行task的数据结构，调度器从当前 CPU 的 runqueue 中选择下一个要运行的 task。
在内核中定义为

struct rq

为什么需要呢？统一时刻具备运行条件的task不止一个。
虽然它叫runqueue，但是并不是一个队列，内核支持多种调度策略，
不同类型任务的选择规则不同，struct rq内部包含多套调度类队列

与其说是队列，不如说是调度状态容器，其核心结构如下

struct rq {
    raw_spinlock_t __lock;      /* 保护当前 runqueue */

    unsigned int nr_running;    /* 可运行 task 数量 */

    struct task_struct *curr;   /* 当前 CPU 正在运行的 task */
    struct task_struct *idle;   /* 当前 CPU 的 idle task */
    struct task_struct *stop;   /* 当前 CPU 的 stop task */

    struct cfs_rq cfs;          /* 普通任务调度队列 */
    struct rt_rq rt;            /* 实时任务调度队列 */
    struct dl_rq dl;            /* Deadline 任务调度队列 */

    u64 clock;                  /* 调度器使用的时钟 */
    u64 clock_task;

    int cpu;                    /* 这个 rq 属于哪个 CPU */

    ...
};

5 sched_class

内核中有很多调度算法，sched_class是 Linux 调度器定义的一套统一接口。
不同类型的调度算法分别实现这套接口，调度核心通过函数指针调用具体算法。
跟C++的面向对象的编程思想差不多。
不需要知道task属于什么任务，提供接口就行。
整体框架如图

先看其核心代码

struct sched_class {
    void (*enqueue_task)(struct rq *rq,
                         struct task_struct *p,
                         int flags);

    void (*dequeue_task)(struct rq *rq,
                         struct task_struct *p,
                         int flags);

    void (*yield_task)(struct rq *rq);

    void (*check_preempt_curr)(struct rq *rq,
                               struct task_struct *p,
                               int flags);

    struct task_struct *(*pick_next_task)(
                         struct rq *rq);

    void (*put_prev_task)(struct rq *rq,
                          struct task_struct *p);

    void (*set_next_task)(struct rq *rq,
                          struct task_struct *p,
                          bool first);

    void (*task_tick)(struct rq *rq,
                      struct task_struct *p,
                      int queued);

#ifdef CONFIG_SMP
    int (*select_task_rq)(struct task_struct *p,
                          int task_cpu,
                          int flags);

    int (*balance)(struct rq *rq,
                   struct task_struct *prev,
                   struct rq_flags *rf);
#endif

    ...
};

在v6.1的内核中，调度类主要包括

stop_sched_class
dl_sched_class
rt_sched_class
fair_sched_class
idle_sched_class

优先级从高到低，意思就是从上往下依次问有没有可以运行的task？没有就向下，如图所示

其中SCHED_***表示调度策略。