深入剖析Linux CFS调度器：调度周期的计算逻辑与抢占实现

CFS（完全公平调度器）为了维持调度队列内部的公平性，引入了一个核心概念：调度周期。简单来说，调度周期的目标是确保在CFS队列上的每个进程，都能在一个周期内至少获得一次运行机会。那么，这个周期是如何定义和实现的呢？本文将结合Linux内核源码，详细解析其背后的机制。

调度周期的实现

调度周期的计算逻辑最终体现在 __sched_period 函数中。它的设计思路很直观：当运行队列中的任务数量不多时，使用一个固定的周期时长；当任务数量过多时，则动态拉伸这个周期，以防止每个任务分到的时间片过小而引入过多的调度开销。

我们先从代码调用链入手。调度周期的触发源于系统的周期性定时器（tick）：

if (td->mode == TICKDEV_MODE_PERIODIC)
                tick_setup_periodic(newdev, 0);

在周期性的定时器中断处理中，最终会调用到调度类的 task_tick 函数：

tick_handle_periodic
  tick_periodic
    update_process_times
      scheduler_tick
        curr->sched_class->task_tick(rq, curr, 0);

对于CFS调度器，其 task_tick 函数是 task_tick_fair，它会进一步调用 entity_tick 和 check_preempt_tick。在 check_preempt_tick 函数中，为了判断是否需要抢占当前任务，需要计算一个“理想运行时间”（ideal_runtime），这个时间就是当前任务在一个调度周期内应分得的时间片，其计算依赖于调度周期 __sched_period。

__sched_period 函数的实现清晰地展示了其计算规则：

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
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;
}

理解这个函数，需要知道三个关键的内核参数：

static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_latency               = 6000000ULL;
unsigned int sysctl_sched_min_granularity               = 750000ULL;

这些值通常以纳秒（ns）为单位。那么，这些默认值代表什么意思呢？

1. sched_nr_latency（默认值8）：这是一个经验性的临界值。它表示单个CPU核心上，能在一个固定延迟周期内保证每个任务都运行一次的最大任务数量。
2. sysctl_sched_latency（默认值6,000,000 ns = 6 ms）：这就是基础的“调度延迟”或“调度周期”。当运行队列中的任务数 小于等于 sched_nr_latency（即8个）时，调度周期就固定为6ms。
3. sysctl_sched_min_granularity（默认值750,000 ns = 0.75 ms）：这是最小调度粒度。当运行队列中的任务数 超过 sched_nr_latency 时，调度周期将不再是固定的6ms，而是变为 任务数量 * 0.75ms。这样做的目的是防止任务过多时，每个任务分到的时间片过小（低于0.75ms），导致上下文切换开销占比过大。

值得注意的是，这些参数都是可以通过 sysctl 接口动态调整的经验值，你可以根据具体的工作负载进行调优，观察不同的效果。

如何保证周期性

知道了调度周期的计算方式，那么CFS是如何利用它来保证“每个任务在一个周期内至少运行一次”的呢？其核心机制就是抢占。

简单来说，内核会通过 update_curr 函数不断更新当前运行任务的虚拟运行时间（vruntime），然后在定时器中断的 check_preempt_tick 函数中，判断当前任务是否已经“超时”。如果超出了一个调度周期内它应分得的时间片，就实施抢占，让出CPU给其他任务。

我们来看看 check_preempt_tick 函数中的具体策略：

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
        s64 delta;
    bool skip_preempt = false;

        ideal_runtime = sched_slice(cfs_rq, curr);
        delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
        trace_android_rvh_check_preempt_tick(current, &ideal_runtime, &skip_preempt,
                        delta_exec, cfs_rq, curr, sysctl_sched_min_granularity);
    if (skip_preempt)
        return;
    if (delta_exec > ideal_runtime) {
                resched_curr(rq_of(cfs_rq));
        /*
         * The current task ran long enough, ensure it doesn't get
         * re-elected due to buddy favours.
         */
        clear_buddies(cfs_rq, curr);
        return;
        }

    /*
         * Ensure that a task that missed wakeup preemption by a
         * narrow margin doesn't have to wait for a full slice.
         * This also mitigates buddy induced latencies under load.
         */
    if (delta_exec < sysctl_sched_min_granularity)
        return;

        se = __pick_first_entity(cfs_rq);
        delta = curr->vruntime - se->vruntime;

    if (delta < 0)
        return;

    if (delta > ideal_runtime)
                resched_curr(rq_of(cfs_rq));
}

函数 resched_curr 就是发起抢占的操作。从代码中可以看到，有两个主要的条件会触发抢占：

抢占点一：运行时间超限

if (delta_exec > ideal_runtime)

delta_exec 是当前任务自上次被调度以来实际的运行时间，ideal_runtime 是根据调度周期计算出的、它本次应分得的理论时间片。如果实际运行时间已经超过了应得的时间片，那么立即抢占。这是实现调度周期最直接、最主要的逻辑。

抢占点二：避免任务饿死

if (delta > ideal_runtime)

这段逻辑需要结合其上下文来理解：

se = __pick_first_entity(cfs_rq);
delta = curr->vruntime - se->vruntime;

由于CFS使用红黑树来组织可运行任务，__pick_first_entity 取出的是红黑树最左侧的节点，即 vruntime 最小的任务，也就是最应该被调度运行的任务。
delta 计算的是当前运行任务的 vruntime 减去最应该被调度任务的 vruntime 的差值。

如果这个差值（即当前任务比最饿的任务多运行了多久）超过了当前任务的理想运行时间片（ideal_runtime），那么即使当前任务自己的时间片还没用完，也会被强制抢占。这个抢占点主要是一种定制化保障，用于缓解CFS调度中可能出现的任务饿死（Starvation） 问题，确保没有任务会等待过长时间。

一个重要的优化：避免过频抢占

除了两个抢占点，check_preempt_tick 中还有一个提前返回的条件：

if (delta_exec < sysctl_sched_min_granularity)
    return;

这里的意图非常明确：如果当前任务的实际运行时间 还小于最小调度粒度（0.75ms），那么就不进行抢占检查，直接返回。这笔操作的核心目的是缓解调度器自身开销。如果允许任务运行极短时间就被抢占，会导致上下文切换过于频繁，反而降低系统整体吞吐量。这也解释了为什么之前调度周期会随着任务数增加而拉伸——就是为了保证每个任务得到的时间片不低于这个最小粒度。

总结

本文深入探讨了Linux内核中完全公平调度器（CFS）的一个关键设计：调度周期。CFS通过引入调度周期的概念，并围绕其设计抢占策略，有效地维护了运行队列内的局部公平性，防止了任务饿死现象的发生。

其实现本质是通过定时器中断，周期性检查当前任务的运行状况，并在两个主要条件下实施抢占：一是任务运行时间超过其应得的时间片；二是当前任务相对于最饿任务的领先优势过大。同时，通过“最小调度粒度”的设置，巧妙地平衡了公平性和调度开销。理解这些底层的内核机制，对于进行性能分析和深度调优非常有帮助。如果你想了解更多操作系统底层或其他技术细节，欢迎在云栈社区交流讨论。