进程调度算法（CFS）
Linux 使用 CFS（Completely Fair Scheduler）完全公平调度器作为默认的进程调度算法。本章深入探讨 CFS 的设计原理和实现机制。
调度器演进历史
Linux 2.4
├─ O(n) 调度器
└─ 遍历所有进程，复杂度 O(n)
Linux 2.6.0 - 2.6.22
├─ O(1) 调度器
├─ 固定时间片
└─ 140 个优先级队列
Linux 2.6.23+
├─ CFS (Completely Fair Scheduler)
├─ 红黑树结构
├─ 虚拟运行时间
└─ 完全公平
CFS 核心概念
虚拟运行时间（vruntime）
公式：
vruntime = 实际运行时间 × (NICE_0_LOAD / 进程权重)
其中：
- NICE_0_LOAD = 1024 (nice 值为 0 的权重)
- 进程权重根据 nice 值确定
- nice 值越低，权重越大，vruntime 增长越慢
nice 值与权重对应表：
// kernel/sched/core.c
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
// nice 值每增加 1，权重约减少 10%
// nice 值每减少 1，权重约增加 10%
红黑树调度队列
// kernel/sched/sched.h
struct cfs_rq {
struct load_weight load; // 队列总权重
unsigned int nr_running; // 运行进程数
u64 min_vruntime; // 最小 vruntime
struct rb_root_cached tasks_timeline; // 红黑树根节点
struct rb_node *rb_leftmost; // 最左节点（最小 vruntime）
struct sched_entity *curr; // 当前运行的调度实体
struct sched_entity *next; // 下一个调度实体
struct sched_entity *last; // 上一个调度实体
struct sched_entity *skip; // 跳过的调度实体
};
红黑树特性：
- 查找最小 vruntime：O(1) - 直接取 leftmost
- 插入/删除：O(log n)
- 自平衡二叉搜索树
调度实体（sched_entity）
// include/linux/sched.h
struct sched_entity {
struct load_weight load; // 权重
unsigned int on_rq; // 是否在运行队列
u64 exec_start; // 开始执行时间
u64 sum_exec_runtime; // 累计运行时间
u64 vruntime; // 虚拟运行时间
u64 prev_sum_exec_runtime;
u64 nr_migrations;
struct sched_statistics statistics;
#ifdef CONFIG_FAIR_GROUP_SCHED
int depth;
struct sched_entity *parent;
struct cfs_rq *cfs_rq; // 所在 CFS 队列
struct cfs_rq *my_q; // 组调度队列
#endif
};
CFS 调度流程
选择下一个进程
// kernel/sched/fair.c
static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
struct cfs_rq *cfs_rq = &rq->cfs;
struct sched_entity *se;
// 如果队列为空，返回 NULL
if (!cfs_rq->nr_running)
return NULL;
// 将当前进程重新放回红黑树
put_prev_task(rq, prev);
// 选择 vruntime 最小的进程（红黑树最左节点）
se = pick_next_entity(cfs_rq, NULL);
return task_of(se);
}
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq);
// 返回最左节点（vruntime 最小）
return left;
}
进程唤醒
// kernel/sched/fair.c
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &p->se;
// 将调度实体加入 CFS 队列
for_each_sched_entity(se) {
if (se->on_rq)
break;
cfs_rq = cfs_rq_of(se);
enqueue_entity(cfs_rq, se, flags);
cfs_rq->h_nr_running++;
}
// 更新 CPU 负载
add_nr_running(rq, 1);
}
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
// 更新 vruntime
update_curr(cfs_rq);
// 如果是新进程或睡眠唤醒，调整 vruntime
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED))
se->vruntime += cfs_rq->min_vruntime;
// 插入红黑树
__enqueue_entity(cfs_rq, se);
se->on_rq = 1;
// 更新最小 vruntime
if (cfs_rq->nr_running == 1) {
list_add_leaf_cfs_rq(cfs_rq);
}
}
时间片和调度周期
// kernel/sched/fair.c
// 调度周期（默认 6ms）
unsigned int sysctl_sched_latency = 6000000ULL;
// 最小粒度（默认 0.75ms）
unsigned int sysctl_sched_min_granularity = 750000ULL;
// 计算时间片
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
u64 slice = __sched_period(cfs_rq->nr_running);
// 根据权重分配时间片
slice *= se->load.weight;
do_div(slice, cfs_rq->load.weight);
return slice;
}
// 调度周期 = max(nr_running * min_granularity, latency)
static u64 __sched_period(unsigned long nr_running)
{
if (unlikely(nr_running > sched_nr_latency))
return nr_running * sysctl_sched_min_granularity;
else
return sysctl_sched_latency;
}
优先级和 nice 值
设置进程优先级
# 查看进程优先级
ps -eo pid,ni,pri,comm
# 启动时设置 nice 值
nice -n 10 ./program
# 调整运行中进程的 nice 值
renice -n 5 -p <PID>
# 只有 root 可以降低 nice 值（提高优先级）
sudo renice -n -5 -p <PID>
实时优先级
// 实时调度策略
#define SCHED_FIFO 1 // 先进先出
#define SCHED_RR 2 // 时间片轮转
#define SCHED_DEADLINE 6 // 截止时间调度
// 设置实时优先级（需要 root）
#include <sched.h>
struct sched_param param;
param.sched_priority = 50; // 1-99
// 设置为 FIFO 调度
sched_setscheduler(getpid(), SCHED_FIFO, ¶m);
// 设置为 RR 调度
sched_setscheduler(getpid(), SCHED_RR, ¶m);
查看实时进程：
# 显示实时优先级
ps -eo pid,rtprio,cls,comm
# chrt 工具
chrt -p <PID> # 查看
chrt -f -p 50 <PID> # 设置 FIFO，优先级 50
chrt -r -p 50 <PID> # 设置 RR，优先级 50
CPU 亲和性
设置 CPU 亲和性
// 使用 sched_setaffinity
#define _GNU_SOURCE
#include <sched.h>
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(0, &cpuset); // 绑定到 CPU 0
CPU_SET(1, &cpuset); // 绑定到 CPU 1
sched_setaffinity(getpid(), sizeof(cpuset), &cpuset);
// 查看当前亲和性
cpu_set_t current;
sched_getaffinity(getpid(), sizeof(current), ¤t);
使用 taskset：
# 查看进程的 CPU 亲和性
taskset -p <PID>
# 设置 CPU 亲和性
taskset -p 0x3 <PID> # 绑定到 CPU 0 和 1 (二进制 11)
taskset -cp 0,1 <PID> # 绑定到 CPU 0 和 1
# 启动时指定
taskset -c 0,1 ./program
组调度（Control Groups）
cgroup CPU 控制
# 创建 cgroup
sudo mkdir /sys/fs/cgroup/cpu/mygroup
# 设置 CPU 份额（相对权重）
echo 512 > /sys/fs/cgroup/cpu/mygroup/cpu.shares
# 设置 CPU 配额（绝对限制）
echo 50000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_quota_us # 50ms
echo 100000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_period_us # 100ms
# 限制为 50% CPU
# 将进程加入 cgroup
echo <PID> > /sys/fs/cgroup/cpu/mygroup/cgroup.procs
# 查看统计
cat /sys/fs/cgroup/cpu/mygroup/cpuacct.usage
systemd cgroup 管理
# 查看服务的 CPU 使用
systemctl show nginx.service -p CPUQuotaPerSecUSec
# 设置 CPU 配额（50%）
systemctl set-property nginx.service CPUQuota=50%
# 设置 CPU 权重
systemctl set-property nginx.service CPUWeight=500
# 查看 cgroup 树
systemd-cgls
调度器性能分析
查看调度统计
# 查看进程调度统计
cat /proc/<PID>/sched
# 关键指标：
# nr_switches: 上下文切换次数
# nr_voluntary_switches: 自愿切换
# nr_involuntary_switches: 非自愿切换
# se.sum_exec_runtime: 总运行时间
# se.vruntime: 虚拟运行时间
调度延迟分析
# 使用 perf 分析调度延迟
perf sched record -- sleep 10
perf sched latency
# 输出示例：
# Task | Runtime ms | Switches | Average delay | Maximum delay |
# :26656:26656 | 1000.00 | 100 | 0.50 ms | 5.00 ms |
实时性测试
#!/bin/bash
# test-scheduling-latency.sh
# 编译测试程序
cat > latency_test.c << 'EOF'
#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() {
struct timespec start, end;
long long latency;
for (int i = 0; i < 1000; i++) {
clock_gettime(CLOCK_MONOTONIC, &start);
usleep(1000); // 睡眠 1ms
clock_gettime(CLOCK_MONOTONIC, &end);
latency = (end.tv_sec - start.tv_sec) * 1000000000LL +
(end.tv_nsec - start.tv_nsec);
printf("Iteration %d: %lld ns\n", i, latency);
}
return 0;
}
EOF
gcc -o latency_test latency_test.c -lrt
./latency_test | awk '{sum+=$3; count++} END {print "Average:", sum/count, "ns"}'
调度器调优
调整调度参数
# 查看当前调度参数
sysctl -a | grep sched
# 调度延迟（默认 6ms）
sysctl -w kernel.sched_latency_ns=10000000
# 最小粒度（默认 0.75ms）
sysctl -w kernel.sched_min_granularity_ns=1000000
# 唤醒粒度（默认 1ms）
sysctl -w kernel.sched_wakeup_granularity_ns=2000000
# 持久化
echo "kernel.sched_latency_ns=10000000" >> /etc/sysctl.conf
sysctl -p
负载均衡
# 查看负载均衡域
cat /proc/sys/kernel/sched_domain/cpu*/domain*/name
# 调整负载均衡间隔
# /proc/sys/kernel/sched_migration_cost_ns
sysctl -w kernel.sched_migration_cost_ns=500000
实践案例
高性能计算场景
#!/bin/bash
# optimize-for-hpc.sh
# 1. 设置实时优先级
chrt -f -p 99 <HPC_PID>
# 2. 绑定 CPU
taskset -cp 0-7 <HPC_PID>
# 3. 禁用 CPU 频率调节
for cpu in /sys/devices/system/cpu/cpu[0-7]; do
echo performance > $cpu/cpufreq/scaling_governor
done
# 4. 禁用中断均衡
systemctl stop irqbalance
# 5. 调整调度参数
sysctl -w kernel.sched_min_granularity_ns=10000000
sysctl -w kernel.sched_wakeup_granularity_ns=15000000
Web 服务器场景
#!/bin/bash
# optimize-for-web.sh
# 1. 使用默认 CFS 调度
# 2. 适度调整 nice 值
renice -n -5 -p $(pgrep nginx)
# 3. 使用 cgroup 限制资源
systemctl set-property nginx.service CPUQuota=200%
systemctl set-property nginx.service CPUWeight=1000
# 4. 启用自动 NUMA 平衡
sysctl -w kernel.numa_balancing=1
下一步：学习 进程间通信（IPC） 章节。