Linux进程调度算法深度解析

进程调度是操作系统的核心功能，Linux的CFS（Completely Fair Scheduler）调度器实现了高效的公平调度。

1. 调度器架构

调度类层次

Linux支持多种调度类，按优先级排序：

1. stop_sched_class：停止进程
2. dl_sched_class： deadline调度（实时）
3. rt_sched_class：实时调度
4. fair_sched_class：完全公平调度（CFS）
5. idle_sched_class：空闲进程

CFS核心思想

CFS不使用传统时间片概念，而是基于虚拟运行时间（vruntime）：

// vruntime计算
vruntime += physical_time * (NICE_0_LOAD / weight)

// 权重表（nice值-20到19）
static const int prio_to_weight[40] = {
    88761, 71755, 56483, 46273, 36291, // nice -20 ~ -16
    ...
    1024,                               // nice 0
    ...
    1024, 820, 655, 526, 423, 335       // nice 15 ~ 19
};
​

2. 红黑树调度队列

CFS使用红黑树维护可运行进程队列，按vruntime排序：

           最小vruntime
              ↓
          [进程A]
           /    \
      [进程B]  [进程C]
       /  \      /  \
   [D]  [E]  [F]  [G]
​

选择过程：

1. 取最左节点（最小vruntime）
2. 更新其vruntime
3. 重新插入红黑树

3. 调度延迟与 granularity

调度延迟（sched_latency）

目标：在sched_latency时间内，所有可运行进程至少运行一次。

sched_latency = 6ms（默认） * nr_cpus

每个进程时间片 = sched_latency / nr_running
​

最小粒度（sched_min_granularity）

防止时间片过小：

min_granularity = 0.75ms（默认）

实际时间片 = max(调度延迟/进程数, min_granularity)
​

4. 负载均衡

负载计算

// CPU负载
load = runnable_tasks + blocked_tasks / 2

// 进程负载贡献
contribution = nr_running * weight
​

负载均衡触发时机

1. 周期性负载均衡（每200ms）
2. 创建新进程时
3. 进程唤醒时
4. CPU空闲时

迁移策略

• pull：从繁忙CPU拉取任务到空闲CPU
• push：从繁忙CPU推送任务到其他CPU

5. 实时调度

SCHED_FIFO

• 先进先出
• 不支持时间片
• 适合高优先级短任务

SCHED_RR

• 时间片轮转
• 同优先级轮流执行
• 防止饥饿

6. 调优参数

# 调整最小粒度
echo 1000000 > /proc/sys/kernel/sched_min_granularity_ns

# 调整唤醒抢占粒度
echo 5000000 > /proc/sys/kernel/sched_wakeup_granularity_ns

# 设置CPU亲和性
taskset -pc 0-3 1234  # 进程1234绑定到CPU 0-3
​

通过理解Linux调度算法，可以优化系统性能，确保关键任务得到及时执行。