内核调度 · 到底有几种队列——运行队列、等待队列与它们的内部结构
每次聊到调度，"队列"这个词总被混着用：有人说运行队列、有人说红黑树、有人说等待队列。其实内核里的"队列"是一组结构，各有各的位置、装的都是不同的东西。本篇把"队列"这个词彻底拆开：每核一个的运行队列
rq里嵌套了哪些子结构、睡眠任务挂在什么样的等待队列上、调度器本身又是什么实体——最后用一张总表收口。
相关:被调度的实体是什么见 task-struct(task/
task_struct,R/S/D 状态);把 task 钉在固定核上见 thread-affinity;切换到另一个核上的代价见 scheduling-timing §五(负载均衡);"凭什么选人"见 调度类与 CFS。
破题：问"有几种队列"的人，到底在问什么
vmstat 里有个 r 列，top 里有 Load Average，教科书里讲"多级反馈队列"，内核源码里又冒出来 rb_root_cached、plist_head、wait_queue_head_t……新手最容易懵的就是：这些"队列"到底是不是一回事？
答案很干脆：不是一回事，但也没有多到失控。内核里跟调度有关的队列/队列式结构，按"装什么"分只有两大阵营，再加一个不装东西的容器：
- 运行队列（每核 1 个）：装此刻能上 CPU 跑的任务。它本身是个容器，肚子里按调度类再分三个子结构（dl 红黑树、rt 多级链表、cfs 红黑树）。
- 等待队列（按事件 N 个）：装睡着等事件的任务。一个事件一个队列，散布在各内核对象里。
- 调度器：不是队列，是纯软件函数。很多人以为它是个后台进程，其实不是。
下面一层层拆。
一、运行队列 rq：每个核一口"锅"，只装能跑的任务
内核给每个 CPU 核配一个运行队列（struct rq，per-CPU run queue），定义在 kernel/sched/sched.h。它只装此刻可运行（TASK_RUNNING） 的 task。调度器每次要切换，就从当前核的 rq 里按规则挑一个放上 CPU 跑。
三个要点：
- per-CPU 是硬约束：每个核只能从自己的
rq里挑人，不能直接抢别的核的队列——这也是多核间需要"负载均衡"把任务搬来搬去的根本原因（见 scheduling-timing §五）。 - 只装可运行：睡眠的任务不在
rq里，它们待在等待队列（见下节）。所以vmstat的r列数的是"可运行 task 总数"，不包括睡着等 IO 的。 - rq 是容器不是单一结构：它肚子里同时装着 dl 红黑树、rt 多级链表、cfs 红黑树三个子队列（详见 §三 总表）。
二、等待队列：不是"一个"，而是一堆——按等待原因各管各
如果说运行队列是"集中管理"的（每核一个 struct rq），等待队列就是分散管理的。实际内核中每个"可等待的事件源"都有自己的等待队列（本质是一个 wait_queue_head_t 链表头），task 睡眠时挂在对应事件的队列上：
| 等待队列类型 | 对应的内核对象 | 典型场景 | 唤醒者 |
|---|---|---|---|
| 磁盘 IO 等待 | block_device 的 io_queue、page 的 PG_locked | read() 等磁盘数据、write() 刷脏页 | 磁盘中断处理程序（DMA 完成后） |
| 缺页等待（major fault） | page 的 PG_locked（同一机制） | mmap 访问未载入的页，触发缺页中断后等磁盘读入 | 磁盘中断 → 页锁定释放 |
| futex 等待 | futex_q 链表（在 futex hash table 里） | pthread_mutex_lock() 抢不到锁 → futex(FUTEX_WAIT) | 持锁者 futex(FUTEX_WAKE) |
| 内核锁等待 | mutex->wait_list、sem->wait_list、rwsem->wait_list | 内核路径中 mutex_lock() 等内部锁 | 持锁者释放时调用 __mutex_unlock_slowpath() |
| Socket/网络等待 | socket 的 sk_wq | recv() 没数据可读、send() 发送缓冲区满、accept() 无新连接、connect() 等待握手 | 网卡中断处理程序（包到达/发送完成） |
| Pipe/FIFO 等待 | pipe 的 wait 队列头（pipe_inode_info->wait） | 读空管道、写满管道时阻塞 | 对方读写后触发唤醒 |
| epoll/poll/select 等待 | eventpoll->wq（epoll 的等待队列） | epoll_wait() 等任意 fd 就绪 | 任一被监控 fd 的事件到达 |
| 定时器等待 | 定时器红黑树 + timer wheel | sleep()、poll(timeout)、epoll_wait(timeout) | 时钟中断 → run_local_timers() |
| 信号等待 | sighand->wait（每个 task 的信号等待链） | sigsuspend()、sigwaitinfo()、pause() | 信号递达时 signal_wake_up() |
| 子进程等待 | task->signal->wait_chldexit | waitpid()/waitid() 等子进程退出 | 子进程退出时 do_notify_parent() |
| 内核 completion | struct completion 内嵌等待队列头 | 内核线程间同步，如 wait_for_completion() | 对方调 complete()/complete_all() |
| 通用 wait_event | wait_event_* 宏创建的任意等待队列头 | 内核代码等待自定义条件满足 | 条件满足方调用 wake_up_*() |
这张表值得停一下：你平时用的每个同步原语，背后都有一个自己的等待队列。锁有锁的、socket 有 socket 的、连"等子进程退出"这种场景都有专门的队列。这正是整个设计最巧妙的地方——也是下面三条关键认知的由来。
关键认知 0：内核没有全局等待队列注册表
不同于运行队列是集中分配的（每 CPU 一个 struct rq），内核根本没有一个 all_wait_queues[] 数组或全局链表来登记所有等待队列。每个等待队列头只是所属内核对象结构体里的一个字段：
struct mutex {
...
struct list_head wait_list; // ← 锁对象自带，不是全局分配的
};
struct socket {
...
struct socket_wq *wq; // ← socket 自带
};
struct page {
...
unsigned long flags; // PG_locked 位 + 等待者链表
};对象创建时自然就有了等待队列头，对象销毁时自然消失。内核不需要"管"等待队列——谁拥有这个对象，谁就拥有上面的等待队列。唤醒时，唤醒方直接操作那个特定对象的等待队列头，把 task 摘下来塞回运行队列。这就是为什么图中等待队列用 package 包起来——它们在逻辑上是一类东西，但在物理上散布在内核各处的对象结构体中，没有统一的存放位置。
关键认知 1：task 不存在"全局睡眠池"里
task 睡眠时，不是进了一个大池子，而是挂在某个具体事件的等待队列上。一个进程 read() 等磁盘，它挂在对应 page 的等待队列上，和等锁、等定时器的任务互不干扰。事件发生时，内核能精确找到"该叫醒谁"——这也是 O(1) 唤醒的基础：不用遍历找，直接操作那个对象自带的队列头就行。
关键认知 2：等待队列和 CPU 没有绑定关系
运行队列是 per-CPU 的（每个核一个 struct rq），但等待队列的归属实体就是被等待的内核对象本身：
mutex对象结构体里内嵌一个wait_list链表头 → 等这把锁的 task 全挂在这struct socket里内嵌sk_wq→ 等这个 socket 数据的 task 全挂在这- 文件 page cache 的
struct page有PG_locked标志和等待者链表 → 等这个 page IO 完成的 task 全挂在这
内核对象创建时等待队列头随之诞生，对象销毁时随之消亡。唤醒操作只是把 task 从该对象的等待队列摘下来、塞回某个 CPU 的运行队列——塞回哪个核是调度器决定的（优先唤醒核，见 scheduling-timing §五 负载均衡），等待队列本身不 care CPU 编号。
三、调度器是什么实体——纯软件，不是独立进程也不是硬件
一个常见的误解是以为调度器是一个"独立的后台守护进程"。调度器不是独立的进程/线程，而是内核代码路径：
- 它是软件：调度器的核心是
kernel/sched/core.c中的schedule()函数，由 C 代码实现。CPU 不内置"调度硬件"，调度全部靠软件逻辑做决策。 - 它没有自己的 task_struct：调度器不是一个 task，你在
ps aux里看不到叫 "scheduler" 的进程。pick_next_task()的代码只是一个函数调用链，不是独立执行的实体。 - 调度器代码跑在调用者的上下文中：谁触发了
schedule()，调度器代码就跑在谁的上下文里（用那个 task 的内核栈）。具体包括：- 被切换出去的 task：当前 task 主动阻塞（如
read()等 IO）、或被 tick 中断发现时间片用完了，它自己调用schedule()→pick_next_task()选出继承人 →context_switch()把 CPU 交出去。调度逻辑跑在"即将下 CPU 的人"的上下文中。 - idle task：某核完全没有可运行的 task 时，idle task（per-CPU 的
swapper/N，PID=0）在跑，它调schedule()试图找活干——一有 task 被唤醒，idle 的上下文切换就跑出去。 - 中断/系统调用返回路径：tick 中断或系统调用返回时，若
need_resched被置位，返回路径上的代码会调schedule()，此时跑在"刚被打断的那个 task"的上下文。
- 被切换出去的 task：当前 task 主动阻塞（如
一句话：调度器是内核里的纯软件函数，不独立存在，代码跑在触发调度的那个 task（或 idle task）的上下文/内核栈上，用完就返回——它不需要自己的 task_struct，也不需要独立调度。
四、到底有几种队列：一张总表
把"队列"这个词彻底拆开，内核调度涉及的队列/队列式结构有这么几种，别混为一谈：
| # | 队列 | 位置/数量 | 装什么 | 结构 | 谁看它 |
|---|---|---|---|---|---|
| 1 | 运行队列 rq | 每 CPU 核一个 | 该核上所有可运行的 task | 容器,内嵌下面 2/3/4 | 调度主循环 |
| 2 | CFS 红黑树 | 每核 rq 内一棵 | 普通任务(SCHED_OTHER) | 按 vruntime 排的红黑树 | CFS 类 |
| 3 | rt 多级队列 | 每核 rq 内 | 实时任务(FIFO/RR) | 每优先级(0-99)一条链表 + 优先级 bitmap | rt 类 |
| 4 | dl 红黑树 | 每核 rq 内一棵 | SCHED_DEADLINE 任务 | 按 deadline 排的红黑树 | dl 类 |
| 5 | 等待队列 wait queue | 每个"事件"一个(锁、IO、socket…) | 睡眠中等事件的 task(S/D 状态) | 链表 | 事件发生时唤醒,不属调度主循环 |
一张图把嵌套关系画清楚——运行队列是"锅"，里面三个子队列是"菜"；等待队列是"另一锅睡觉的菜"，事件到了才被端回来：
一句话理清：运行队列（每核 1 个，内含 dl/rt/cfs 三种子队列结构） 装可运行的，等待队列（按事件多个） 装睡着的。跨调度类是优先级分层（dl>rt>cfs），类内各用最合适的结构（实时用多级链表按固定优先级、普通用红黑树按 vruntime）。task 在"运行队列↔等待队列"之间来回搬，就是"可运行↔睡眠"状态转换（见 task-struct §三的 R/S/D）。
五、一句话总结
"有几种队列"要分两层看：每核一个运行队列
rq（只装可运行 task，内含 dl 红黑树、rt 每优先级一条链表、cfs 红黑树三个子结构）+ 按事件多个的等待队列（装睡着等事件的 task，各自内嵌在所属内核对象里，没有全局注册表、不绑定 CPU）。调度器不是队列也不是进程，而是内核里跑在调用者上下文中的纯软件函数schedule()。task 在运行队列与等待队列之间来回搬，就是可运行与睡眠状态的转换。