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, "")

Last updated