多核时代的调度器演进与Per-CPU架构

随着处理器架构从早期的单核设计演进至现代的众核NUMA拓扑，Linux调度器面临着严峻的线性扩展挑战。为了在不重构核心调度算法的前提下支撑数千个逻辑核心，内核引入了Per-CPU运行队列（Run Queue, rq）机制。这一设计将全局共享的调度数据结构拆解为每个物理核心独占的本地队列，从根本上消除了多核环境下的自旋锁竞争。

时代背景	硬件特征	核心瓶颈	架构演进方案
1990年代	单处理器	算法复杂度	O(n) 简单轮转调度
2000年代初	对称多处理(SMP)	全局自旋锁竞争	O(1) 调度器与 Per-CPU rq 引入
2000年代末	多核/多缓存	缓存行伪共享	CFS 引入与 PELT 负载追踪
2010年代	大规模 NUMA	跨节点内存延迟	层次化调度域与拓扑感知
2020年代后	超大规模众核	跨芯片同步开销	Core-sched 与 动态热插拔优化

Per-CPU运行队列结合层次化调度域和分布式负载均衡策略，实现了以下核心优势：

• 锁竞争降至O(1)：每个核心仅操作本地队列，彻底移除全局大锁。
• 缓存命中率极高：任务控制块（task_struct）和虚拟运行时间（vruntime）等热点数据驻留在本地L1/L2缓存中。
• NUMA拓扑感知：调度域层级与硬件物理拓扑严格对齐，大幅降低跨节点内存访问惩罚。

Per-CPU运行队列的内存布局与数据结构

为了最大化缓存利用率，struct rq 的内存布局经过精心设计，将高频访问的"热数据"与低频访问的"冷数据"进行物理隔离。

+-------------------------------------------------------------------------+
|                        单核视角：运行队列 (rq) 内存布局                 |
|                                                                         |
|  +-------------------------------------------------------------------+  |
|  | [热数据区 - 驻留 L1 Cache Line]                                   |  |
|  |  • raw_spinlock_t queue_lock      <- 保护本地队列的自旋锁         |  |
|  |  • struct task_struct *current    <- 当前正在执行的任务指针       |  |
|  |  • struct cfs_rq cfs_tasks        <- CFS 红黑树根节点与统计信息   |  |
|  |  • struct sched_avg cpu_avg       <- PELT 负载衰减追踪数据        |  |
|  +-------------------------------------------------------------------+  |
|                                                                         |
|  +-------------------------------------------------------------------+  |
|  | [温数据区 - 调度类与时间管理]                                     |  |
|  |  • struct rt_rq rt_tasks          <- 实时任务优先级队列           |  |
|  |  • struct dl_rq dl_tasks          <- 截止期限调度队列             |  |
|  |  • u64 clock_task                 <- 任务时钟（剔除中断时间）     |  |
|  |  • unsigned long compute_capacity <- 核心算力（受频率/微架构影响） |  |
|  +-------------------------------------------------------------------+  |
|                                                                         |
|  +-------------------------------------------------------------------+  |
|  | [冷数据区 - 按需加载，避免缓存污染]                               |  |
|  |  • struct sched_domain *domain_sd <- 关联的调度域层级链表         |  |
|  |  • struct task_struct *idle_task  <- 空闲任务（Swapper）          |  |
|  |  • struct task_struct *stop_task  <- 迁移与停止内核线程           |  |
|  +-------------------------------------------------------------------+  |
+-------------------------------------------------------------------------+

底层支撑：Per-CPU变量与无锁化路径

Per-CPU变量的底层实现依赖于架构相关的段寄存器（如x86_64的 %gs）或专用基址寄存器。通过将变量偏移量映射到每个核心的私有内存区域，内核实现了无需原子操作的O(1)数据访问。

/*
 * 内核 Per-CPU 运行队列声明与访问宏重写
 * 文件: kernel/sched/sched.h
 */

/* 声明对齐的 Per-CPU 运行队列实例 */
DECLARE_PER_CPU_ALIGNED(struct run_queue, cpu_rq_instances);

/* 获取当前核心的运行队列（编译为单条段偏移指令） */
static inline struct run_queue *get_current_rq(void) {
    return raw_cpu_ptr(&cpu_rq_instances);
}

/* 获取指定逻辑核心的运行队列（用于跨核负载均衡） */
static inline struct run_queue *get_cpu_rq(int target_cpu) {
    return &per_cpu(cpu_rq_instances, target_cpu);
}

/* 获取任务当前绑定的运行队列 */
static inline struct run_queue *get_task_rq(struct task_struct *tsk) {
    return get_cpu_rq(task_cpu(tsk));
}

在任务唤醒的高频路径中，Per-CPU设计使得调度器只需获取目标核心的本地锁，避免了全局锁导致的缓存行 bouncing（伪共享）。

/*
 * 任务唤醒核心路径：无锁化设计体现
 * 文件: kernel/sched/core.c
 */
static int wake_up_task(struct task_struct *target_task, unsigned int prev_state, int wake_flags) {
    struct run_queue *dest_rq;
    int dest_cpu, wake_success = 0;

    /* 1. 选择目标核心（基于唤醒亲和性与负载均衡策略） */
    dest_cpu = select_target_cpu(target_task, target_task->wake_cpu, wake_flags);

    /* 2. 获取目标核心的本地运行队列 */
    dest_rq = get_cpu_rq(dest_cpu);

    /* 3. 仅锁定目标队列，不产生全局竞争 */
    raw_spin_lock(&dest_rq->queue_lock);

    if (target_task->state & prev_state) {
        wake_success = 1;

        /* 4. 将任务插入目标核心的 CFS 队列 */
        enqueue_task(dest_rq, target_task, ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK);

        /* 5. 若唤醒任务优先级更高，触发抢占标记 */
        if (target_task->prio < dest_rq->current->prio)
            set_tsk_need_resched(dest_rq->current);
    }

    raw_spin_unlock(&dest_rq->queue_lock);
    return wake_success;
}

拓扑感知：调度域与层次化负载均衡

为了在大规模SMP系统中控制负载均衡的开销，Linux引入了调度域（Sched Domain）概念。调度域将CPU划分为多个层次（如SMT、Core、Package、NUMA Node），每个层级拥有独立的负载均衡触发频率和迁移阈值。

/*
 * 调度域结构体与负载均衡参数
 * 文件: kernel/sched/sched.h
 */
struct sched_domain {
    /* 拓扑层级标识 (0=SMT, 1=MC, 2=DIE, 3=NUMA) */
    int topology_level;
    
    /* 包含的 CPU 位图 */
    unsigned long span_mask[0];

    /* 树状结构指针 */
    struct sched_domain *parent_domain;
    struct sched_domain *child_domain;

    /* 负载均衡时间窗口控制 */
    unsigned int balance_min_ms;
    unsigned int balance_max_ms;
    unsigned int busy_delay_factor;

    /* 迁移决策阈值 */
    unsigned int imbalance_threshold_pct;
    unsigned int cache_hot_retries;

    /* 域特性标志 (如 SD_LOAD_BALANCE, SD_NUMA) */
    unsigned int domain_flags;

    /* 统计与调度组 */
    unsigned long last_balance_jiffies;
    struct sched_group *sched_groups;
};

/* 核心负载均衡执行逻辑 */
static void execute_domain_rebalancing(struct run_queue *local_rq, enum cpu_idle_state idle_state) {
    int current_cpu = local_rq->cpu_id;
    unsigned long next_tick = jiffies + 60 * HZ;
    bool update_tick = false;
    struct sched_domain *domain;

    rcu_read_lock();
    /* 自底向上遍历调度域树 */
    for_each_domain(current_cpu, domain) {
        unsigned long balance_interval;

        if (!(domain->domain_flags & SD_LOAD_BALANCE))
            continue;

        balance_interval = calculate_balance_interval(domain, idle_state != CPU_IDLE);

        if (time_before(jiffies, domain->last_balance_jiffies + balance_interval))
            continue;

        /* 执行当前层级的任务迁移 */
        if (perform_load_balance(current_cpu, local_rq, domain, idle_state)) {
            domain->last_balance_jiffies = jiffies;
        }

        if (time_after(next_tick, domain->last_balance_jiffies + balance_interval)) {
            next_tick = domain->last_balance_jiffies + balance_interval;
            update_tick = true;
        }
    }
    rcu_read_unlock();

    if (update_tick)
        local_rq->next_balance_tick = next_tick;
}

环境构建与可扩展性验证

验证Per-CPU架构在众核环境下的表现，需要搭建包含多NUMA节点的硬件环境，并使用自动化工具收集调度统计信息。

#!/usr/bin/env python3
"""
调度器扩展性与负载分布量化分析工具
"""
import json
import subprocess
import re
import numpy as np
import matplotlib.pyplot as plt
from dataclasses import dataclass
from typing import List, Dict

@dataclass
class CoreMetrics:
    core_id: int
    runnable_tasks: int
    load_avg: float
    ctx_switches: int
    migrations: int

class SchedMetricsEvaluator:
    def __init__(self):
        self.core_count = int(subprocess.getoutput('nproc'))
        self.numa_topology = self._parse_numa_topology()
        self.metrics: List[CoreMetrics] = []

    def _parse_numa_topology(self) -> Dict[int, List[int]]:
        try:
            output = subprocess.getoutput('numactl --hardware')
            nodes = {}
            for line in output.split('\n'):
                match = re.search(r'node (\d+) cpus: (.+)', line)
                if match:
                    node_id, cores = match.groups()
                    nodes[int(node_id)] = [int(c) for c in cores.split()]
            return nodes
        except Exception:
            return {0: list(range(self.core_count))}

    def fetch_sched_statistics(self) -> List[CoreMetrics]:
        """解析 /proc/schedstat 获取核心调度指标"""
        metrics = []
        with open('/proc/schedstat') as f:
            content = f.read()
        
        pattern = re.compile(r'cpu(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)')
        for match in pattern.finditer(content):
            core_id = int(match.group(1))
            metrics.append(CoreMetrics(
                core_id=core_id,
                runnable_tasks=0,
                load_avg=0.0,
                ctx_switches=int(match.group(3)),
                migrations=int(match.group(7)) if len(match.groups()) > 6 else 0
            ))
        return metrics

    def compute_load_imbalance(self) -> Dict[str, float]:
        """计算系统负载的变异系数与不平衡度"""
        if not self.metrics:
            return {}
        
        loads = [m.load_avg for m in self.metrics if m.load_avg > 0]
        if not loads:
            return {'cv': 0.0, 'imbalance_ratio': 1.0}

        mean_load = np.mean(loads)
        std_load = np.std(loads)
        
        return {
            'mean': mean_load,
            'std': std_load,
            'cv': std_load / mean_load if mean_load > 0 else 0.0,
            'max_min_ratio': max(loads) / min(loads) if min(loads) > 0 else float('inf')
        }

    def generate_visual_report(self, output_path="sched_metrics.png"):
        """生成负载分布与迁移热力图"""
        if not self.metrics:
            return

        fig, ax = plt.subplots(figsize=(12, 6))
        cores = [m.core_id for m in self.metrics]
        migrations = [m.migrations for m in self.metrics]
        
        ax.bar(cores, migrations, color='teal', alpha=0.8)
        ax.set_xlabel('Logical Core ID')
        ax.set_ylabel('Task Migrations Count')
        ax.set_title('Per-Core Task Migration Distribution')
        
        plt.tight_layout()
        plt.savefig(output_path, dpi=150)
        print(f"Visual report saved to {output_path}")

if __name__ == '__main__':
    evaluator = SchedMetricsEvaluator()
    evaluator.metrics = evaluator.fetch_sched_statistics()
    
    imbalance = evaluator.compute_load_imbalance()
    print(f"Load Imbalance CV: {imbalance.get('cv', 0):.4f}")
    
    evaluator.generate_visual_report()

深度调优：锁竞争、NUMA感知与定制开发

在极端负载下，Per-CPU队列仍可能面临局部锁竞争或NUMA远程访问惩罚。通过BPF工具链和内核参数调整，可以精准定位并优化这些瓶颈。

诊断运行队列自旋锁竞争

#!/bin/bash
# 使用 bpftrace 追踪运行队列锁的持有时间与等待延迟

sudo bpftrace -e '
kprobe:_raw_spin_lock {
    @acquire_timestamp[tid] = nsecs;
}

kretprobe:_raw_spin_lock {
    if (@acquire_timestamp[tid]) {
        @spinlock_wait_us = hist((nsecs - @acquire_timestamp[tid]) / 1000);
        delete(@acquire_timestamp[tid]);
    }
}

interval:s:5 {
    print(@spinlock_wait_us);
    clear(@spinlock_wait_us);
}
'

NUMA亲和性感知调度优化

当任务被唤醒时，调度器需权衡"本地核心高负载"与"远程核心低负载"之间的收益。以下代码展示了如何在任务放置决策中强化NUMA本地性权重。

/*
 * NUMA 感知任务放置策略优化
 * 文件: kernel/sched/fair.c
 */
static int select_numa_aware_cpu(struct task_struct *tsk, int prev_cpu, int wake_flags) {
    int preferred_node = task_node(tsk);
    int fallback_cpu = prev_cpu;

    /* 快速路径：前一个 CPU 仍在首选 NUMA 节点且负载不高 */
    if (cpu_to_node(prev_cpu) == preferred_node) {
        struct run_queue *prev_rq = get_cpu_rq(prev_cpu);
        if (prev_rq->cfs_tasks.avg.load_avg < SCHED_CAPACITY_SCALE / 2)
            return prev_cpu;
    }

    /* 遍历首选 NUMA 节点内的所有可用核心 */
    for_each_cpu_and(target_cpu, cpumask_of_node(preferred_node), &tsk->cpus_mask) {
        struct run_queue *target_rq = get_cpu_rq(target_cpu);

        /* 发现完全空闲的核心，立即返回 */
        if (!target_rq->nr_running)
            return target_cpu;

        /* 记录负载最低的核心作为后备 */
        if (target_rq->cfs_tasks.avg.load_avg < get_cpu_rq(fallback_cpu)->cfs_tasks.avg.load_avg)
            fallback_cpu = target_cpu;
    }

    return fallback_cpu;
}

内核扩展：添加Per-CPU调度延迟直方图

为了在云原生环境中实现更细粒度的调度延迟监控，可以在 struct rq 中扩展自定义统计字段，并通过 debugfs 暴露给的用户态监控代理。

/*
 * 扩展运行队列结构体以支持延迟直方图
 * 文件: kernel/sched/sched.h & kernel/sched/core.c
 */

struct run_queue {
    /* ... 原有字段 ... */

#ifdef CONFIG_SCHED_LATENCY_HISTOGRAM
    /* 指数分桶延迟统计：1us, 2us, 4us ... 2^31 us */
    u64 latency_buckets[32];
    u64 total_switch_samples;
#endif
};

static inline void record_switch_latency(struct run_queue *rq, u64 latency_ns) {
#ifdef CONFIG_SCHED_LATENCY_HISTOGRAM
    /* 将纳秒转换为微秒，并计算最高有效位以确定桶索引 */
    int bucket_idx = fls64(latency_ns / 1000);
    if (bucket_idx < 32) {
        rq->latency_buckets[bucket_idx]++;
        rq->total_switch_samples++;
    }
#endif
}

/* 在上下文切换完成时调用 */
static __always_inline void finish_context_switch(struct run_queue *rq, u64 start_time) {
    u64 switch_latency = rq_clock(rq) - start_time;
    record_switch_latency(rq, switch_latency);
}

/* debugfs 导出接口 */
static int show_latency_histogram(struct seq_file *m, void *v) {
    int cpu;
    for_each_online_cpu(cpu) {
        struct run_queue *rq = get_cpu_rq(cpu);
        seq_printf(m, "CPU%d:", cpu);
#ifdef CONFIG_SCHED_LATENCY_HISTOGRAM
        for (int i = 0; i < 32; i++) {
            if (rq->latency_buckets[i])
                seq_printf(m, " %dus:%llu", 1 << i, rq->latency_buckets[i]);
        }
        seq_printf(m, " [Total:%llu]\n", rq->total_switch_samples);
#else
        seq_puts(m, " Disabled\n");
#endif
    }
    return 0;
}

大规模系统调度域定制策略

针对不同规模的硬件拓扑，调度域的层级深度和均衡频率需要进行差异化配置，以避免过度均衡导致的系统抖动。

• 1-8核（边缘计算/桌面）：保持默认拓扑，重点优化SMT超线程间的 SD_SHARE_CPUCAPACITY 标志，确保计算资源公平分配。
• 9-64核（标准服务器）：启用 numa_balancing，适当缩短MC（Multi-Core）层级的 balance_min_ms，加速短生命周期任务的收敛。
• 65-256核（高端NUMA）：分离热/冷数据结构，减少跨Socket的缓存行弹跳。对于数据库等对延迟敏感的应用，可通过 isolcpus 隔离特定核心并禁用其所在调度域的 SD_LOAD_BALANCE 标志。
• 257核以上（超算/大型云）：禁用跨NUMA节点的主动推模式（Push），全面采用空闲核心主动拉取（Pull）策略。结合 Core-sched 机制隔离安全域，防止侧信道攻击并降低跨域同步开销。