# 2.2.4 核心概念 - 运行队列

调度器的核心工作就是把可运行的任务扔到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, "")
> ```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/concepts/runqueue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.