Linux任务调度(7): CFS调度器源码分析1

Posted 2024-06-27 12:36 +0800 by ZhangJie ‐ 7 min read

分享:  

Linux任务调度(7): CFS调度器源码分析

前面几篇文章介绍了Linux下调度器的演进过程，也对CFS调度器的大致工作原理进行了介绍，本文在CFS源码层面进行深入分析，帮助大家更深刻地理解CFS调度器的实现细节。Linux从开始引入CFS调度器到现在，已经发展了近20年的时间。在这一段时间里，CFS调度器经历了多次演进，我们选择相对比较新的版本 v5.12 版本内核为例进行说明。现在主流云厂商提供的Linux发行版内核都还有这个版本，我们的分析仍然具有一定的时效性方面的价值。OK，我们开始。

核心概念及源码分析

对“公平”的理解

CFS的目标是为所有任务提供公平的CPU时间分配，这里要先好好理解下 “公平” 的含义：

1）如果多个任务具有相同的优先级，那么它们理应获得相同的调度机会； 2）如果多个任务优先级有高低之分，那么它们在调度上要有对应的体现，优先级高的要获得更多的调度机会； 3）要防止高优先级任务始终霸占CPU，导致低优先级任务饿死（starvation）； 4）对于响应式任务、非响应式任务，要有必要的奖励和惩罚机制，以改善用户体验； 5）要有能力在用户层级、任务组层级、具体任务层级，建立这种“公平性”； 6）这种公平性在多CPU核心上，除了100%保证单CPU核心上的公平，也需要考虑负载均衡和任务迁移，尽力去做到多CPU核心上的整体调度的相对公平；

这是我对CFS中“公平性”的理解，接下来我们将结合CFS的源码来分析是如何做到的，让大家知其然知其所以然。

核心数据结构

  1. 被调度的具体任务，或者用户组、任务组，它们都用可调度实体来抽象表示，即 sched_entity；
    struct sched_entity {
    /* For load-balancing: */
    struct load_weight        load;
    struct rb_node            run_node;
    struct list_head		      group_node;
    unsigned int              on_rq;

    u64                       exec_start;
    u64                       sum_exec_runtime;
    u64                       vruntime;
    u64                       prev_sum_exec_runtime;

    u64                       nr_migrations;

    struct sched_statistics exec_statistics;

    #ifdef CONFIG_FAIR_GROUP_SCHED
        int                     depth;
        struct sched_entity     *parent;
        /* rq on which this entity is (to be) queued: */
        struct cfs_rq           *cfs_rq;
        /* rq "owned" by this entity/group: */
        struct cfs_rq           *my_q;
        /* cached value of my_q->h_nr_running */
        unsigned long           runnable_weight;
    #endif

    #ifdef CONFIG_SMP
        /*
         * Per entity load average tracking.
         *
         * Put into separate cache line so it does not
         * collide with read-mostly values above.
         */
       struct sched_avg        avg;
   #endif
}

2）每个处理器独立维护一个任务队列cfs_rq，避免1个全局队列的方式导致竞争问题：

   /* CFS-related fields in a runqueue */
    struct cfs_rq {
        struct load_weight    load;
        unsigned int          nr_running;
        unsigned int          h_nr_running;      /* SCHED_{NORMAL,BATCH,IDLE} */
        unsigned int          idle_h_nr_running; /* SCHED_IDLE */
  
        u64                   exec_clock;
        u64                   min_vruntime;
        ...
  
        struct rb_root_cached    tasks_timeline; /* 维护任务的vruntime的rbtree */
  
        /*
         * 'curr' points to currently running entity on this cfs_rq.
         * It is set to NULL otherwise (i.e when none are currently running).
         */
        struct sched_entity    *curr;
        struct sched_entity    *next;
        struct sched_entity    *last;
        struct sched_entity    *skip;
        ...
  
        /*
         * CFS load tracking
         */
        struct sched_avg    avg;
        ...
  
    // 组调度相关的内容，暂时忽略
    #ifdef CONFIG_FAIR_GROUP_SCHED
      ...
    #endif /* CONFIG_FAIR_GROUP_SCHED */
    };

内核为每个处理器维护一个任务队列cfs_rq, cfs_rq中通过指针成员next,last建立了一个双向链表，方便调度器遍历任务列表。

  1. 调度器为了能够快速找到任务队列cfs_rq中下一个vruntime最小的可运行任务，构建了1个rbtree：

    /* CFS-related fields in a runqueue */
 struct cfs_rq {
     ...
     struct rb_root_cached    tasks_timeline; /* 维护任务的vruntime的rbtree */
     struct sched_entity      *curr;
     ...
 }
 /*
  * Leftmost-cached rbtrees.
  *
  * We do not cache the rightmost node based on footprint
  * size vs number of potential users that could benefit
  * from O(1) rb_last(). Just not worth it, users that want
  * this feature can always implement the logic explicitly.
  * Furthermore, users that want to cache both pointers may
  * find it a bit asymmetric, but that's ok.
  */
  struct rb_root_cached {
      struct rb_root rb_root;
      struct rb_node *rb_leftmost;
   };

    红黑树的更新逻辑这里暂时按下不提，我们先关注核心逻辑，如果此时运行中的任务curr被抢占，那么下一个执行的就是cfs_rq.tasks_timeline->rb_leftmost。 在介绍调度器抢占逻辑时，我们会看到这部分的更多的源码细节。OK，理解cfs的核心数据结构大致就是这些，篇幅原因我们暂时移除了支持组调度相关的部分。

调度粒度

前面核心数据结构部分，我们介绍了sched_entity，从这里可以引申出一个重要概念，调度粒度。

struct sched_entity {
    /* For load-balancing: */
    struct load_weight        load;
    struct rb_node            run_node;
    struct list_head          group_node;
    unsigned int              on_rq;

    ...

    #ifdef CONFIG_FAIR_GROUP_SCHED
        int                     depth;
        struct sched_entity     *parent;

        /* rq on which this entity is (to be) queued: */
        struct cfs_rq           *cfs_rq;

        /* rq "owned" by this entity/group: */
        struct cfs_rq           *my_q;

        /* cached value of my_q->h_nr_running */
        unsigned long           runnable_weight;
    #endif
    ...
}

sched_entity，可以表示：

  1. 具体的1个任务；
  2. 任务组，此时sched_entity.cfs_rq表示当前任务组从属于哪个任务队列，并且sched_entity.my_q表示当前任务组包含的任务队列； 现在你明白了：
    • 调度器cfs_rq中的某个任务可以是一个“任务组”，
    • 该任务组内包含了自己的任务队列，任务组内的任务也是按照CFS vruntime进行调度，
    • 同时该任务组的vruntime是由其my_q中的所有可调度实体的vruntime求和计算而来，该任务组与其所在的cfs_rq中的其他调度实体按照CFS vruntime进行调度。
  3. 用户组是任务组的一种特殊应用形式，本质还是任务组这样的组调度；

关于组调度的实现源码，篇幅原因，本文中可能不涉及，但是看罢此文，我相信读者已经可以自己去阅读源码了。如果有时间我会再写一篇文章讲述组调度的细节。

任务的优先级

在前面介绍的楼梯调度算法、旋转楼梯调度算法，提到了多优先级队列来实现“公平性”对于“任务优先级”的理解。看上去它确实也是种解决办法，但是它真的很难被建模、量化然后说它到底好还是不好？任务在active、expire队列中挪来挪去，或者从高优先级队列挪到低优先级队列，真的是最优雅的解决办法吗？首先，理解起来它就不是那么简单，尽管我在信息流图文、视频链路处理过程中也使用过类似的方法来解决业务中的资源调度问题，但是我确实不认为那就是最好的解决方案。

CFS调度器的设计，核心思想更简单易懂，且非常容易比建模、量化评估： 1）任务的优先级，包括了初始的静态优先级(nice，从-20到19)和动态优先级(priority，根据是否响应式任务动态调整)； 2）调度器执行调度时，会检查任务列表中的任务是否是响应式任务，并调整其对应的动态优先级（奖励 or 惩罚，-5到+5）； 3）任务的最终优先级 = 静态优先级 + 动态优先级； 4）任务的优先级会被映射为一种“权重”，表示它在总的CPU执行时间里的一种占比，显然优先级越高对应的权重也应该越大；

虚拟运行时间

调度器执行调度时，很重要的一部操作就是迅速找到下一个被调度的可运行任务。Linux v0.01版本中找到下一个可运行任务的复杂度是O(n)，O(1)调度器是O(1)，CFS调度器是O(log(n))。 CFS调度器建立了一个红黑树（RBTree），树种每个节点表示一个任务，任务中包含了一个属性 vruntime。

vruntime是一个虚拟运行时间: vruntime = 实际执行时间 / weight

  1. 实际执行时间，就是任务被调度到CPU上执行的总时间； 2）处理器时钟中断定时触发，时钟中断服务程序此时会更新当前运行中的任务的实际执行时间，并更新vruntime；
    时钟中断服务入口 scheduler_tick(preempt):
   \-> scheduler_tick()
         \-> task_tick(rq, cur, 0)
               \-> task_tick_fair(rq, cur, 0)
                     \-> foreach se in cfs_rq: entity_tick(cfs_rq, se, queued)
                           \-> update_curr(cfs_rq)
                                 \-> curr->sum_exec_runtime += delta_exec;
                                 \-> curr->vruntime += calc_delta_fair(delta_exec, curr);

/*
* delta /= w
*/
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
   if (unlikely(se->load.weight != NICE_0_LOAD))
    delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
   return delta;
}

3）weight则是由前面提到的任务优先级，通过查表映射而来得到的权重值； vruntime的实际计算式为：

   virtual runtime = (real runtime) * (NICE_0_LOAD) / (weight of the process)

  • 其中virtual runtime指的就是vruntime;

  • real runtime指的是cpu上的实际执行时间;

  • NICE_0_LOAD表示nice==0时的默认权重（1024）;

  • 而weight of the process指的是由进程的实际优先级从映射表映射而来的权重;

    完整的映射表可以参考：

   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,
   };

当一个任务被调度执行时，时钟中断会定时触发，对应的时钟中断通过1）中代码序列会不断更新任务的实际执行时间和 vruntime，陷入阻塞状态的任务不会占用CPU，这里的时间也不会增加。

ps：sched_entity可以表示具体任务，也可以表示任务组、用户组（用户组是任务组的一种特殊应用方式），而vruntime是定义在sched_entity中的，对于组调度而言，计算vruntime的时候就是递归计算其包含的所有任务的vruntime，汇总起来。

调度周期

sched_latency，直译过来应该是调度延迟，但是理解成调度周期更好理解一点，它表示什么呢？ 1）任意一个可运行任务先后两次调度之间的时间差上限； 2）在这个时限内所有可运行任务都必须完成一次调度；

sched_latency，强调的是多久的时间窗口内所有运行任务可以都被调度一轮，它不等于任务执行时的时间片sched_slice。在传统调度器实现中，时间片是固定的，在CFS中不是的，时间片是动态计算的，后面会提到。

我们看下调度周期的相关计算逻辑：

/*
 * Targeted preemption latency for CPU-bound tasks:
 *
 * NOTE: this latency value is not the same as the concept of
 * 'timeslice length' - timeslices in CFS are of variable length
 * and have no persistent notion like in traditional, time-slice
 * based scheduling concepts.
 *
 * (to see the precise effective timeslice length of your workload,
 *  run vmstat and monitor the context-switches (cs) field)
 *
 * (default: 6ms * (1 + ilog(ncpus)), units: nanoseconds)
 */
unsigned int sysctl_sched_latency			= 6000000ULL;

/*
 * Minimal preemption granularity for CPU-bound tasks:
 *
 * (default: 0.75 msec * (1 + ilog(ncpus)), units: nanoseconds)
 */
unsigned int sysctl_sched_min_granularity			= 750000ULL;

/*
 * This value is kept at sysctl_sched_latency/sysctl_sched_min_granularity
 */
static unsigned int sched_nr_latency = 8;

 * 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;
}

不难看出:

  1. 当可运行任务数<=8时，调度周期sched_latency=6ms；
  2. 当>8时，调度周期sched_latency=可运行任务数*0.75ms，超过8个时就大于6ms。

这里的调度延迟和下面的动态时间片的计算有关系，注意看。

时间片

调度器中包含“时间片”这个设计，主要有两个目的： 1）为了避免进程频繁切换，必须要让任务执行一段时间后再切换，否则每次系统调用返回、时钟中断服务检测到vruntime最小时都会立即触发触发，开销极大； 2）为了避免进程长时间霸占CPU，有些进程不进行IO或者其他可能阻塞性的处理，就不会主动让出CPU，时钟中断服务每隔一段时间触发调度器进行检查，如果任务运行时间片就要强制抢占；

不同调度器实现都肯定需要考虑“时间片”的设计，不同于传统的基于固定时间片大小的调度器实现，CFS中的任务时间片是动态计算的，详见 sched_slice(...)。

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
   // if nr_running<=8, slice=6ms; else slice=nr_running*0.75ms
	u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

	for_each_sched_entity(se) {
		struct load_weight *load;
		struct load_weight lw;

		cfs_rq = cfs_rq_of(se);
		load = &cfs_rq->load;

		if (unlikely(!se->on_rq)) {
         // total load on this cfs_rq, sum(load-per-task)
			lw = cfs_rq->load;

			update_load_add(&lw, se->load.weight);
			load = &lw;
		}
		// slice = delta_exec * weight / lw.weight
      // or
      // (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
		slice = __calc_delta(slice, se->load.weight, load);
	}
	return slice;
}

首先根据可运行任务数量计算出一个调度周期，然后根据过去每个任务执行贡献的负载/总负载，按比例划分调度周期得到该任务的动态时间片。

ps: 这里的概念“负载”，就是占据CPU的时间，不是top中的loadavg的负载概念。

能不能确定动态时间片的一个上下界呢？接着往下看你就知道了。

调度节拍

检查任务是否需要切换，有这么几个时机:

  1. 时钟中断服务程序触发scheduler_tick(void)，如果检查逻辑发现需要触发会设置对应的标记位TIF_NEED_RESCHED；
  2. 任务执行到阻塞型系统调用时，任务需要阻塞执行、不可被调度，此时会主动让出CPU，如mutex, semaphore, waitqueue；
  3. 任务执行系统调用返回时，一般也会做个检查 （在看linux v0.01源码时就是会检查的，合理，推测后续版本也是这样的）；

这里的调度节拍，强调的更多的是硬件时钟中断触发时钟中断服务程序，进入这里的scheduler_tick执行任务切换逻辑:

  1. 更新任务执行时间、vruntime；
  2. 抢占逻辑check_preempty_check里检查任务执行时间是否已经超过时间片，超过则寻找下一个待调度任务，设置标志位TIF_NEED_RESCHED返回；
  3. 等待调度器__schedule(preempt)执行实际的任务切换逻辑。
时钟中断服务入口 scheduler_tick(preempt):
   \-> scheduler_tick()
         \-> task_tick(rq, cur, 0)
               \-> task_tick_fair(rq, cur, 0)
                     \-> foreach se in cfs_rq: entity_tick(cfs_rq, se, queued)
                           \-> update_curr(cfs_rq)
                                 \-> curr->sum_exec_runtime += delta_exec;
                                 \-> curr->vruntime += calc_delta_fair(delta_exec, curr);
                           \-> check_preempt_tick(cfs_rq, curr)

// Preempt the current task with a newly woken task if needed:
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{ ... }

任务抢占

当前正在执行的任务，在时钟中断到来时schedule_tick函数被执行，它里面会检查当前任务是否应该被抢占，如果需要被抢占，则会调用resched_cur 来标记任务的一些抢占标记为。检查当前任务是否运行足够久应该被抢占的函数，前面我们已经分析过了，就是check_preempt_tick函数。

/* 
 * Preempt the current task with a newly woken task if needed
 */
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;

	ideal_runtime = sched_slice(cfs_rq, curr);
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
	if (delta_exec > ideal_runtime) {
		resched_curr(rq_of(cfs_rq));
      ...
		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 - mark rq's current task 'to be rescheduled now'.
 *
 * On UP this means the setting of the need_resched flag, on SMP it
 * might also involve a cross-CPU call to trigger the scheduler on
 * the target CPU.
 */
void resched_curr(struct rq *rq)
{
   ...
	if (test_tsk_need_resched(curr))
		return;

	cpu = cpu_of(rq);
	if (cpu == smp_processor_id()) {
		set_tsk_need_resched(curr);
		set_preempt_need_resched();
		return;
	}

	if (set_nr_and_not_polling(curr))
		smp_send_reschedule(cpu);
	else
		trace_sched_wake_idle_without_ipi(cpu);
}

总结下 check_preempt_tick 的检查逻辑：

  1. 如果运行足够久了，超过了sched_slice返回的时间片（时间配额），则直接标记为抢占然后返回
  2. 如果运行任务时间很短，没有超过动态时间片，并且还不到最小的0.75ms，那么无需抢占、继续执行
  3. 如果运行时间不太短，虽然不到动态时间片大小，但是超过了0.75ms，可以检测下是否需要被抢占 则从当前cpu的cfs_rq（任务队列）中取出vruntime最小的一个se，进行比较。
    • 如果当前任务的vruntime更小，则不能被抢占，当前任务继续执行；
    • 如果当前任务的vruntime更大 (delta=curr.vruntime-se.vruntime，delta>0)
      • delta<=ideal_time，从全局来看有比我更应该优先调度的，但是也没等太久，让我再执行一会，一会就让出CPU；
      • delta>ideal_time，从全局来有比我更应该优先调度的，且已经等了比较久时间了；

进一步的说明:

  1. 任务的静态优先级以及CFS对交互式任务的奖励、惩罚带来的动态优先级调整，会直接影响到权重的计算，进而影响到理想时间片ideal_time的计算，尽管 sysctl_sched_min_granularity = 0.75ms，我们初看源码容易误认为时间片最少0.75ms，不是的，由于优先级、权重的影响，实际计算出来的ideal_time可能只有几到几十微秒。详见我们后面的bpftrace的测试。
  2. 如果任务优先级比较高，实际计算的理想时间片比较大，比如大于0.75ms，在执行时间不足ideal_time时会执行到此分支。如果不足0.75ms则继续执行，这是考虑到当前任务优先级较高，为了体现公平应该尽可能多执行一会。 3）………………………………………大于0.75ms，执行时间上不足ideal_time但是超过了0.75ms，达到了一个最小粒度，此时也够意思了，为了进一步的“公平性”，此时会要求检查“抢占”逻辑。

理想情况下，还是需要执行完ideal_time后再切换，才能体现公平是不是？确实。

那为什么现在就要执行检测呢？因为系统中随时可能会插入高优先级进程、考虑交互性程序的奖励、非交互性程序的处罚以及避免饿死问题。“公平”不仅要看过去、现在，也要看将来，不仅要看局部，也要看整体。So……此时在执行时间已经超过了最小粒度0.75ms的前提下，额外检查下是否需要被抢占十分合理，更何况是一个已经“等”了我一会的任务呢？

ps: 从这里可以看出，cfs并不是立即选一个vruntime更小的任务来立即执行，即使下一个任务的vruntime比当前任务小，当前任务也会尽量拖着再执行一会，要么等到执行完理想的时间片（这样最公平），要么拖到下一个任务再等我一会，这样我执行时间更接近理想时间片。

任务切换

schedule_tick(...) 只是时钟中断服务触发检查“是否需要抢占当前任务“，如果需要就设置标记位并返回。 我们知道此时当前任务还是在执行中的，顶多被设置了个抢占标记位而已，那么调度器什么时候执行了真正的切换呢？在 __schedule(preempt)这个调度器逻辑中。

/*
 * __schedule() is the main scheduler function.
 *
 * The main means of driving the scheduler and thus entering this function are:
 *
 *   1. Explicit blocking: mutex, semaphore, waitqueue, etc.
 *
 *   2. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
 *      paths. For example, see arch/x86/entry_64.S.
 *
 *      To drive preemption between tasks, the scheduler sets the flag in timer
 *      interrupt handler scheduler_tick().
 *
 *   3. Wakeups don't really cause entry into schedule(). They add a
 *      task to the run-queue and that's it.
 *
 *      Now, if the new task added to the run-queue preempts the current
 *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
 *      called on the nearest possible occasion:
 */
static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	unsigned long prev_state;
	struct rq_flags rf;
	struct rq *rq;
	int cpu;

	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	prev = rq->curr;

   ...

   // 寻找下一个可执行任务
	next = pick_next_task(rq, prev, &rf);
   // 清理旧任务的抢占标记位
	clear_tsk_need_resched(prev);
	clear_preempt_need_resched();

   // 如果next!=prev，更新上下文切换计数器，并执行上下文切换
   // 如果next==prev，说明当前runq上没有其他任务，需要检查下负载均衡了
	if (likely(prev != next)) {
		rq->nr_switches++;

      // ptrace时间上报，用于bpftrace分析
      trace_sched_switch(preempt, prev, next);

      // 执行上下文切换，从prev到next，切换完就开始执行next这个任务了
		rq = context_switch(rq, prev, next, &rf);
	} else {
		rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

      // 负载均衡相关的操作，rq.lock dropped之后会执行balance_callbacks
		rq_unpin_lock(rq, &rf);
		__balance_callbacks(rq);
		raw_spin_unlock_irq(&rq->lock);
	}
}

__schedule(preempt) 函数非常长，我们删减了不是很相关的代码，只看下任务切换的核心逻辑： 1）这个函数什么时候会被执行到呢？注释提到了有几个时机，任务阻塞主动让出CPU、任务被抢占、任务被唤醒任务重新加入run-queue； 我们刚才提到的任务抢占就会导致进入这个函数处理。 2）cfs调度器通过pick_next_task(…)从rq中找到下一个vruntime最小的任务； 3）清理之前设置的抢占标记位，更新抢占计数器； 4）执行上下文切换 context_switch，执行新任务逻辑； 5）再释放掉rq上的锁后，会执行负载均衡逻辑（work-sharing mode）；

这就是大致的任务抢占、任务切换、负载均衡的核心逻辑。

负载均衡

see: __balance_callbacks(rq)，因为我们了解go workstealing相关的迁移负载的做法，对linux cfs调度器做到负载均衡的思路并不十分好奇， 我们这里只是简单总结下负载均衡的核心思路，细节直接跳过。

1）这里笼统地说下cfs调度器负载均衡的时机，以及考虑因素。

负载均衡的时机，负载均衡通常在以下几种情况下触发：

  • 周期性负载均衡：调度器会定期检查各个CPU的负载，并在必要时进行任务迁移。
  • 任务唤醒：当一个任务从睡眠状态被唤醒时，调度器会检查当前CPU的负载情况，并可能将任务分配到负载较轻的CPU。
  • 任务创建：当一个新任务被创建时，调度器会选择一个负载较轻的CPU来运行该任务。

任务迁移的考虑因素，在决定是否迁移任务时，调度器会考虑多个因素，包括：

  • CPU负载：调度器会比较各个CPU的负载，选择负载较轻的CPU进行任务迁移。
  • 任务的vruntime：调度器会比较任务的vruntime，选择合适的任务进行迁移。
  • 任务的亲和性：某些任务可能对特定的CPU有亲和性（例如，缓存亲和性），调度器会尽量避免迁移这些任务。

2）CPU1上的P1的vruntime比CPU2上的P2的vruntime更小，CPU1负载高，会将P1迁迁移到CPU2上吗？

假设有两个CPU（CPU1和CPU2），每个CPU有自己的调度队列和红黑树：

  • CPU1上的任务P1的vruntime较大，暂时不被CPU1调度。
  • CPU2上的任务P2的vruntime最小，但P1的vruntime比P2更小。

在这种情况下，是否会将P1迁移到CPU2取决于负载均衡机制的具体实现和当前系统的负载情况：

  • 如果CPU1的负载较高，而CPU2的负载较低，负载均衡机制可能会将P1迁移到CPU2，以平衡负载。
  • 如果CPU1和CPU2的负载相对均衡，调度器可能不会进行任务迁移，因为任务迁移本身也有一定的开销。

如果您对负载均衡的细节感兴趣，可以看下相关的代码。

组调度

组调度，一个任务组是组，一个用户组是一个特殊的任务组的应用场景。前面介绍核心数据结构时，特别提了sched_entity中如何借助字段my_q来表示该任务组包含的任务队列，组内的任务也是按照CFS调度器算法进行调度。而这个任务组又作为一个调度实体从属于更上层的“组”，被CFS调度算法调度。

这里的“组调度”，在Linux的设计实现中： 1）需要有一个能力来灵活的定义组，然后灵活地在这个组中添加任务，灵活地建立一个sched_entity的树形结构。cgroups就是用来干这个事情的。 在cgroups中增加配置项来影响调度，如cpu.shares表示这个调度组的CPU开销的配额。 2) 对应地cfs调度器需要读取cgroups这里的这些配置项，来感知到有哪些任务组，每个任务组的配置是啥样的，进而整合成sched_entity的树形结构，让树形结构中的每个调度实体（任务、组）被CFS调度器调度。

OK，篇幅原因本文不打算继续介绍组调度相关的内容，读到这里了解了CFS关键的处理过程后，大家可以自行查看组调度相关的设计实现了。或者等我有时间时再补一篇文章，专门介绍组调度的源码分析。

本文总结

本文详细介绍了CFS调度器的核心概念、核心数据结构以及关键操作流程的源码级分析，相信读者对CFS调度器的工作原理也有了更加全面的认识。下一篇文章我们将讲述了一个曾经困扰在我们项目组心头的关于go进程混部时的一些担忧，以及由此引出的多进程混部时的隔离性问题，个别程序实现不健壮创建大量进程是否会推高上下文切换次数导致无谓的CPU开销的问题。我们将结合工具perf、bpftrace来深入观察并分析，以加深了对真实负载场景下任务调度的深层理解。

OK，欢迎点赞关注我，我们继续一起学习。

Edit this page on GitHub
← Linux任务调度(8): 任务越多调度就越频繁吗
vscode-常规配置以及同步说明 →