Linux调度原理
Linux调度器是操作系统内核的核心组件之一,负责决定哪个进程获得CPU的使用权以及何时使用，其设计目标是高效利用CPU资源，保证系统响应性，同时兼顾公平性和实时性，Linux调度器经历了从O（1）调度器到完全公平调度器（CFS）的演进，目前主流版本采用CFS及其变种，如实时调度器（SCHED_FIFO和SCHED_RR）和空闲调度器（SCHED_IDLE），本文将深入探讨Linux调度原理的核心机制，包括调度实体、调度策略、运行时管理以及负载均衡等方面。
调度实体与运行队列
Linux调度的基本单位是调度实体（Scheduling Entity，SE），每个SE关联一个任务（进程或线程），在CFS中，SE通过虚拟运行时间（virtual runtime，vruntime）衡量其执行进度，vruntime是实际运行时间的加权值，优先级越高的任务，vruntime增长越慢，从而获得更多的CPU时间。
调度实体被组织在红黑树（Red-Black Tree）中，按vruntime排序，红黑树的左子树节点具有最小的vruntime，因此CFS总是选择左子树节点作为下一个运行的任务，确保了短任务优先和长任务公平性，运行队列（runqueue）是每个CPU核心的数据结构，存储了该核心上可调度的SE。
调度策略分类
Linux支持多种调度策略,以满足不同场景的需求：
- SCHED_NORMAL（或SCHED_OTHER）：用于普通进程，采用CFS算法。
- SCHED_FIFO：实时进程，先到先服务，除非更高优先级进程就绪。
- SCHED_RR：实时进程，轮转调度，每个进程固定时间片。
- SCHED_BATCH：批量进程，类似SCHED_NORMAL，但降低交互性。
- SCHED_IDLE：最低优先级进程，仅在系统空闲时运行。
不同策略的优先级范围如下：
| 调度策略 | 优先级范围 | 用途 |
|---|---|---|
| SCHED_FIFO | 1-99 | 硬实时任务 |
| SCHED_RR | 1-99 | 软实时任务 |
| SCHED_NORMAL | 100-139 | 普通进程 |
| SCHED_BATCH | 100-139 | 批处理任务 |
| SCHED_IDLE | 140 | 后台低优先级任务 |
完全公平调度器（CFS）的核心机制
CFS的核心思想是“完全公平”，即每个任务应获得按比例分配的CPU时间，其实现依赖于以下概念：
- 虚拟运行时间（vruntime）：实际运行时间乘以权重（nice值），nice值越低（-20到+19），权重越高，vruntime增长越慢。
- 最小虚拟运行时间（min_vruntime）：运行队列记录的最小vruntime，用于平衡不同任务的时间。
- 理想运行时间（ideal_runtime）：任务在当前时间片内应运行的时间，通过
ideal_runtime = 实际运行时间 / 总权重 * 当前任务权重计算。
CFS通过红黑树管理任务,每次调度时选择vruntime最小的任务运行，当任务阻塞时，其vruntime保持不变；当任务唤醒时，若其vruntime小于min_vruntime，则被立即调度。
负载均衡与多核调度
在多核系统中,负载均衡是保证各核心利用率的关键，Linux采用两种负载均衡策略：
- 主动负载均衡（Active Load Balancing）：当某个核心的运行队列为空时，从其他核心窃取任务。
- 周期性负载均衡（Periodic Load Balancing）：定期检查各核心负载，将任务迁移到负载较低的核心。
负载均衡的触发条件包括：
- 新任务创建时。
- 任务唤醒时。
- 定时器中断时（如每1-4ms）。
调度延迟与时间片管理
CFS通过动态调整时间片避免任务饥饿,调度延迟（sched_latency）是每个任务在运行队列中等待的最大时间（默认为6ms），若任务数量增加，每个任务的时间片按比例减少：时间片 = 调度延迟 / 任务数量。
若有4个任务,则每个任务的时间片为1.5ms（6ms/4），若任务数量超过调度延迟允许的最大值（默认为8），则时间片固定为最小时间片（如0.75ms）。
实时调度器的特殊性
实时调度器（SCHED_FIFO和SCHED_RR）优先级高于普通进程，采用抢占式调度，SCHED_FIFO中，任务运行完毕或主动放弃CPU；SCHED_RR中，每个任务运行固定时间片后切换到同优先级任务。
实时任务的优先级通过chrt命令设置，
chrt -f 1 ./realtime_task # 设置SCHED_FIFO，优先级1
调度器的优化与挑战
Linux调度器在性能和公平性之间不断优化：
- NUMA感知调度：在多NUMA节点系统中，优先将任务调度到其内存所在的节点，减少内存访问延迟。
- 节能调度：通过
cpufreq调整CPU频率，在负载较低时降低频率以节省能源。 - Cgroup支持：通过控制组（cgroup）限制任务的CPU使用率，实现资源隔离。
调度器仍面临挑战,如实时任务的确定性保证、大规模集群的调度效率等，随着异构计算（如GPU与CPU协同）的普及，调度器需进一步适应多样化硬件资源的管理。
Linux调度原理通过动态调整任务优先级、虚拟运行时间和负载均衡，实现了高效、公平的CPU资源分配，CFS作为主流调度算法，通过红黑树和vruntime机制确保了短任务优先和长任务公平性；而实时调度器则为关键任务提供了低延迟保障，随着系统复杂度的增加，Linux调度器仍在持续演进，以适应新的硬件架构和应用场景需求。
