2.2.4 核心概念 - 运行队列

简要介绍runqueue

调度器的核心工作就是把可运行的任务扔到CPU上去运行。如何有效、合理地组织可运行的任务，是调度器需要考虑的重要问题。

Linux 内核使用一个运行队列（runqueue）来存放可运行的任务，该数据结构的定义如下：

/* file: kernel/sched/sched.h */
struct rq {
    unsigned int nr_running;

    u64 nr_switches;

    /*
     * runqueue 采用的模块化的实现方式，各个不同的 Scheduling Class 都有自己的
     runqueue 实现。不同的 runqueue 的数据结构保存在如下属性之中
    */
    struct cfs_rq cfs; /* CFS runqueue 的实现 */
    struct rt_rq rt;   /* RT runqueue 的实现 */
    struct dl_rq dl;   /* Deadline runqueue 的实现 */

    struct task_struct __rcu *curr; /* 当前 runqueue 中正在运行的进程 */
    struct task_struct *idle;       /* Idle 调度类的任务 */
    struct task_struct *stop;       /* Stop 调度类的任务 */
    struct mm_struct *prev_mm;

    atomic_t nr_iowait;

#ifdef CONFIG_SMP
    struct root_domain *rd;
    struct sched_domain __rcu *sd;

    unsigned long cpu_capacity;
    unsigned long cpu_capacity_orig;
#endif /* CONFIG_SMP */

#ifdef CONFIG_SCHEDSTATS
    /* latency stats */
    struct sched_info rq_sched_info;
    unsigned long long rq_cpu_time;
    /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */

    /* sys_sched_yield() stats */
    unsigned int yld_count;

    /* schedule() stats */
    unsigned int sched_count;
    unsigned int sched_goidle;
#endif
};

此处我们删除了该结构体的大多数字段，仅仅保留了一些主要的字段一探究竟，这些字段涉及如下几个方面：

1. 具体调度类的运行队列。不同的调度类选择下一个任务的逻辑是不同的，因此不同的调度类会有不同的调度队列实现方式，例如字段 struct cfs_rq cfs 就是 CFS 的调度队列

2. 当前正在运行的进程，以及 stop 与 idle 这种特殊任务

3. 如果是 SMP 架构，则 rq 中还会包含调度域的字段，调度器使用调度域中的信息来做负载均衡

4. 一些统计信息

rq 是系统可运行任务的容器，调度器的很多工作都是围绕着 rq 来进行的，调度类 struct sched_class 所申明的函数中，绝大多数函数都与 rq 相关。在系统中，每个 CPU 都有一个自己的 rq, 这样可以避免多个 CPU 访问同一个 rq 时产生的并发问题，提升调度器效率。

在 Linux 的早期实现中，系统只维护一个全局的 rq，为了解决同步问题，调度器通过自旋锁来保护对队列的同步访问。2.4 版本的 O(n) 调度器采用的就是这种实现方式。

对于有些变量，内核会为每个 CPU 单独维护一份拷贝，这种变量叫着 per-cpu 变量（per-cpu variable），除了 rq, 还有很多其他的场景需要这种变量。内核定义了各种宏和工具函数来对这类变量进行处理，所有的定义都在文件 include/linux/percpu-defs.h 中。例如申明 per-cpu 变量的宏定义如下：

#define DEFINE_PER_CPU(type, name)              \
    DEFINE_PER_CPU_SECTION(type, name, "")