Linux调度器核心数据结构

// include/linux/sched.h (约 780 行起)struct task_struct { // ── 基本标识 ── volatile long state; // 进程状态: TASK_RUNNING / TASK_INTERRUPTIBLE / ... pid_t pid; struct mm_struct *mm; // 进程地址空间 // ── 调度核心字段 ── int on_rq; // 是否在运行队列上 (0=不在, 1=在普通rq, 2=在isolate) int prio; // 动态优先级 (0-139, 0-99=RT, 100-139=CFS) int static_prio; // 静态优先级 (nice值映射: 120+nice) int normal_prio; // 归一化优先级 unsigned int rt_priority; // RT 优先级 (0-99) // ── 调度类指针 ── const struct sched_class *sched_class; // 指向所属调度类 // ── CFS 调度实体 ── struct sched_entity se; // 嵌入 CFS 调度实体 // ── RT 调度实体 ── struct sched_rt_entity rt; // 嵌入 RT 调度实体 // ── DL 调度实体 ── struct sched_dl_entity dl; // 嵌入 Deadline 调度实体 // ── CPU 亲和性 ── cpumask_t cpus_allowed; // 允许运行的 CPU 集合 // ── 调度策略 ── unsigned int policy; // SCHED_NORMAL/SCHED_FIFO/SCHED_RR/SCHED_DEADLINE // ── 运行统计 ── u64 utime, stime; // 用户态/内核态运行时间 struct sched_info sched_info; // 调度统计信息 // ── 上下文切换 ── struct thread_struct thread; // CPU 上下文（寄存器等） struct fs_struct *fs; struct files_struct *files; struct task_group *sched_task_group; // ... 总计约 800+ 字段};

// kernel/sched/sched.h (约 2190 行)struct sched_class { // 调度类链表：按优先级排序，next 指向下一个较低优先级的调度类 const struct sched_class *next; // ── 入队/出队 ── void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags); void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags); // ── 核心选择函数 ── struct task_struct *(*pick_next_task)(struct rq *rq); // ── 进程抢占/让出 ── void (*put_prev_task)(struct rq *rq, struct task_struct *p); void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first); // ── 时钟中断回调 ── void (*task_tick)(struct rq *rq, struct task_struct *p, int queued); // ── 进程切换回调 ── void (*switched_from)(struct rq *this_rq, struct task_struct *task); void (*switched_to)(struct rq *this_rq, struct task_struct *task); void (*reweight_task)(struct rq *rq, struct task_struct *p, ...); // ── 优先级变更 ── void (*prio_changed)(struct rq *this_rq, struct task_struct *task, int oldprio); // ── 负载均衡 ── int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf); int (*select_cpu)(struct task_struct *p, int task_cpu, int flags); void (*migrate_task_rq)(struct task_struct *p, int new_cpu); void (*task_woken)(struct rq *this_rq, struct task_struct *task); void (*set_cpus_allowed)(struct task_struct *p, struct affinity_context *ctx); // ── 调度域/组 ── unsigned int task_group; // 所属 task_group (cgroup 调度) // ...};

// kernel/sched/sched.h (约 100 行)struct rq { raw_spinlock_t __lock; // 保护 rq 的自旋锁 unsigned int cpu; // 此 rq 所属的 CPU 编号 unsigned int online; // ── 当前运行进程 ── struct task_struct *curr; // 当前正在运行的进程 struct task_struct *idle; // 此 CPU 的 idle 进程 struct task_struct *stop; // 此 CPU 的 stop 进程 // ── 各调度类子运行队列 ── struct cfs_rq cfs; // CFS 运行队列 struct rt_rq rt; // RT 运行队列 struct dl_rq dl; // Deadline 运行队列 // ── 调度类指针（快速访问）── const struct sched_class *idle_sched_class; // ── 调度统计 ── u64 nr_switches; // 上下文切换次数 u64 nr_running; // 总运行进程数 u64 clock; // rq 时钟 u64 clock_task; // 不含 IRQ 时间的时钟 // ── 负载均衡 ── struct sched_domain *sd; // 调度域链表 unsigned long cpu_capacity; // CPU 算力 unsigned long cpu_capacity_orig; // ── next_balance ── u64 next_balance; // 下次负载均衡时间 struct callback_head *balance_callback; // 负载均衡回调链表 // ── cgroup 调度 ── struct list_head cfs_tasks; // CFS 任务链表 // ...};// 每个 CPU 一个 rq，全局数组DEFINE_PER_CPU(struct rq, runqueues);

// kernel/sched/sched.h (约 580 行)struct cfs_rq { struct load_weight load; // 队列总负载权重 unsigned int nr_running; // 运行中的进程数 unsigned int h_nr_running; // 层级运行数（含子组） // ── 红黑树根节点 ── struct rb_root_cached tasks_timeline; // 按 vruntime 排序的红黑树 /* * rb_root_cached 包含: * - rb_root rb_root: 红黑树根 * - rb_node *rb_leftmost: 最左节点（vruntime 最小，即下一个要运行的） */ // ── 当前运行实体 ── struct sched_entity *curr; // 当前运行的调度实体 struct sched_entity *next; // 下一个待运行（preemption 用） struct sched_entity *last; // 上一个运行的 struct sched_entity *skip; // 跳过的实体（skip buddy） // ── vruntime 基准 ── u64 min_vruntime; // 队列最小 vruntime（新进程继承此值） u64 clock_task; // 不含 IRQ 的时钟 // ── 负载跟踪 (PELT) ── unsigned long runnable_avg; // 可运行平均负载 unsigned long util_avg; // 利用率平均值 unsigned long util_est; // 利用率预估 // ── 带宽控制 ── struct rq *rq; // 指向所属的 rq struct task_group *tg; // 所属 task_group (cgroup) int throttled; // 是否被限流 u64 throttled_clock; // 限流开始时间 struct cfs_bandwidth *cfs_b; // 带宽控制结构 // ...};

// include/linux/sched.h (约 520 行)struct sched_entity { // ── 负载权重 ── struct load_weight load; // 权重（nice 值映射，决定 CPU 时间比例） /* * nice -20 → weight 88761 (约 10% CPU) * nice 0 → weight 1024 (基准) * nice +19 → weight 15 (约 0.15% CPU) * 映射表: kernel/sched/sched.h 中的 prio_to_weight[] */ // ── 红黑树节点 ── struct rb_node run_node; // 嵌入 cfs_rq 红黑树的节点 // ── vruntime（CFS 核心）── u64 vruntime; // 虚拟运行时间（决定红黑树排序） /* * vruntime 增长速率 = delta_exec * NICE_0_LOAD / weight * nice 0 进程: vruntime == 实际运行时间 * 高优先级进程: weight 大, vruntime 增长慢 → 获得更多 CPU 时间 * 低优先级进程: weight 小, vruntime 增长快 → 获得更少 CPU 时间 */ // ── 运行统计 ── u64 exec_start; // 本次开始执行时间 u64 sum_exec_runtime; // 总执行时间 u64 prev_sum_exec_runtime; // 上次切换时的执行时间 u64 sleep_start; // 睡眠开始时间 // ── 负载跟踪 (PELT) ── struct sched_avg avg; // 调度平均负载 // ── cgroup 调度 ── struct cfs_rq *cfs_rq; // 所属的 cfs_rq struct cfs_rq *my_q; // 如果是 task_group，指向子 cfs_rq // ── on_rq 状态 ── unsigned char on_rq; // 是否在 cfs_rq 上 // ── vruntime 调整 ── u64 vlag; // virtual lag (v6.6 新增, 替代旧版 min_vruntime 补偿) s64 slice; // 时间片预算 (v6.6 新增)};

// kernel/sched/sched.h (约 700 行)struct rt_rq { struct rt_prio_array active; // 优先级位数组 /* * struct rt_prio_array { * DECLARE_BITMAP(bitmap, MAX_RT_PRIO); // 100 位优先级位图 * struct list_head queue[MAX_RT_PRIO]; // 每个优先级一个链表头 * }; * bitmap 第 i 位为 1 → 优先级 i 有进程在等待 * queue[i] → 优先级 i 的进程链表 * 查找最高优先级: sched_find_first_bit(bitmap) → O(1) */ unsigned int rt_nr_running; // RT 运行进程数 unsigned int rt_nr_migratory; // 可迁移进程数 // ── RT 带宽控制 ── struct rt_bandwidth rt_bandwidth; // RT 带宽限制 u64 rt_time; // RT 消耗时间 u64 rt_throttled; // 限流时间戳 int rt_throttled; // 是否被限流 // ── cgroup ── struct rq *rq; // 所属 rq struct task_group *tg; // 所属 task_group // ...};