title: fair
categories:

  • linux
  • kernel
  • sched
    tags:
  • linux
  • kernel
  • sched
    abbrlink: 7c28162a
    date: 2025-10-03 09:01:49

文章目录


在这里插入图片描述

https://github.com/wdfk-prog/linux-study

kernel/sched/fair.c 完全公平调度器(Completely Fair Scheduler, CFS) Linux默认的普通进程调度策略

历史与背景

这项技术是为了解决什么特定问题而诞生的？

kernel/sched/fair.c 是Linux内核**完全公平调度器（Completely Fair Scheduler, CFS）**的核心实现。它的诞生是为了彻底取代在它之前的O(1)调度器，并解决其固有的复杂性和公平性问题。

O(1)调度器虽然调度决策速度快，但它依赖于一套非常复杂的、启发式的算法来“猜测”一个进程是否是“交互式”的，并动态地调整其优先级。这导致了以下问题：

  1. 公平性不足：其启发式算法并不完美，常常导致某些进程获得不公平的CPU时间份额。
  2. 代码复杂难懂：包含大量“魔法数字”和复杂的逻辑，难以维护和调试。
  3. 可调优性差：nice值对进程行为的影响不直观，难以预测。

CFS的出现，旨在用一个极其简单、优雅且可证明的公平模型来取代这一切。其核心目标不再是使用复杂的技巧去追踪进程行为，而是去模拟一个**“理想的、完美多任务的CPU”**。在这个理想模型中，每个进程都以同等的速度并行执行，绝对公平。CFS的所有设计都是为了在真实的、一次只能运行一个任务的CPU上，尽可能地逼近这个理想模型。

它的发展经历了哪些重要的里程碑或版本迭代？

CFS的发展是Linux调度器历史上的一次革命。

  • 诞生 (Kernel 2.6.23)：由Ingo Molnar主导开发，CFS在Linux 2.6.23中被合并，正式取代了O(1)调度器，成为SCHED_NORMAL和SCHED_BATCH策略的默认实现。这是Linux调度器发展史上最重要的里程碑之一。
  • 组调度（Group Scheduling）的集成：CFS与控制组（cgroups）紧密集成，实现了组调度功能。这使得可以公平地在不同的用户、服务或容器（cgroups）之间分配CPU时间，而不仅仅是在进程之间。
  • NUMA感知与负载均衡：CFS的负载均衡器不断演进，以更好地适应非统一内存访问（NUMA）架构，试图在CPU缓存亲和性和跨节点负载均衡之间取得最佳平衡。
  • 持续的微调与优化：自诞生以来，CFS的核心模型保持不变，但其内部实现（如唤醒抢占、负载跟踪等）一直在不断地被社区优化，以适应新的硬件特性和不断变化的工作负载。
目前该技术的社区活跃度和主流应用情况如何？

CFS是当前所有通用Linux系统（桌面、服务器、移动设备）的默认调度器，是内核中最核心、最活跃的组件之一。

  • 主流应用：它是Linux之所以能在从Android手机到世界顶级超级计算机等各种设备上都表现出色的关键因素之一。任何以SCHED_NORMAL（默认策略）运行的进程，其CPU时间的分配都由fair.c中的CFS逻辑来决定。

核心原理与设计

它的核心工作原理是什么？

CFS的核心原理出奇地简单，它围绕着一个关键概念——**虚拟运行时间（virtual runtime, vruntime）**来运转。

  1. 虚拟运行时间 (vruntime)：

    • vruntime不是进程真实运行的物理时间，而是一个标准化的、加权的运行时间。它记录了一个进程“理应”运行了多久。
    • 一个进程在CPU上运行得越久，它的vruntime就增长得越快。
    • 权重（Weight）：进程的nice值（-20到+19）被映射为一个权重。nice值越低（优先级越高），权重就越大。vruntime的增长速度与权重成反比。这意味着，高优先级的进程其vruntime增长得更慢。

  2. 数据结构：红黑树（Red-Black Tree）：

    • 每个CPU的CFS运行队列（struct cfs_rq）不再是简单的链表，而是一棵以vruntime为键值排序的红黑树。
    • 所有可运行的普通进程都存在于这棵树中。

  3. 调度决策：永远选择最“饥饿”的：

    • 当CFS需要选择下一个要运行的进程时，它的决策规则只有一个：永远选择红黑树最左边的那个节点。
    • 因为红黑树按vruntime排序，最左边的节点就是vruntime最小的那个。vruntime最小，意味着这个进程是当前所有可运行进程中，被“亏欠”CPU时间最多的，即最“饥apro饿”的。

  4. 时间片（Timeslice）的概念：

    • CFS中没有传统意义上的固定时间片。一个进程会一直运行，直到：
      a. 它自愿阻塞（如等待I/O）。
      b. 一个vruntime比它更小的进程被唤醒（抢占）。
      c. 它运行了一小段时间后，其vruntime不再是树中的最小值。
    • 这个“一小段时间”是由系统的目标延迟（sched_latency_ns）动态决定的。系统会尝试让每个可运行任务都在这个延迟周期内至少运行一次。
它的主要优势体现在哪些方面？
  • 极致的公平性：公平性是其设计的出发点和核心，不再是事后的弥补。
  • 模型简单优雅：用vruntime和红黑树取代了复杂的启发式算法，代码逻辑更清晰。
  • 天然的交互式任务支持：交互式任务（如编辑器）大部分时间都在睡眠等待用户输入。当它们被唤醒时，它们的vruntime因为长时间没有增长而非常小，因此能立即抢占CPU，获得极佳的响应速度。
  • 高效的进程选择：在红黑树上查找最小值和插入/删除操作的时间复杂度都是O(log N)，其中N是可运行进程的数量，扩展性非常好。
它存在哪些已知的劣势、局限性或在特定场景下的不适用性？
  • 非实时：CFS的目标是公平，而不是满足严格的时间截止。它不提供任何实时保证。
  • 对纯吞吐量场景可能非最优：对于一组纯粹的、长时间运行的计算任务，过于频繁的抢占以保证“公平”可能会导致不必要的上下文切换和缓存污染，从而轻微降低总吞吐量。SCHED_BATCH策略就是为了缓解这个问题而设计的。
  • NUMA调度的复杂性：在大型多CPU、多节点的NUMA系统上，是应该将任务保持在当前CPU以利用热缓存（cache hot），还是将其迁移到空闲的CPU以获得即时执行，这是一个极其复杂的权衡，CFS的负载均衡器一直在为此进行优化。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

CFS是所有非实时工作负载的默认和首选调度器。

  • 桌面系统：完美平衡了后台编译任务、前台视频播放和用户UI响应等多种需求。
  • 服务器：为Web服务器、数据库、应用服务器等承载的成千上万个线程和进程提供了公平的CPU时间分配。
  • 移动设备 (Android)：Android的内核就是标准的Linux内核，CFS负责调度所有的应用程序和系统服务。
是否有不推荐使用该技术的场景？为什么？
  • 硬实时或软实时应用：任何对任务执行延迟或截止时间有严格要求的场景，都绝对不能使用CFS。这些场景必须使用SCH-ED_FIFO、SCHED_RR（由rt.c实现）或SCHED_DEADLINE（由dl.c实现）。

对比分析

请将其 与 其他相似技术 进行详细对比。

在Linux内核中，最恰当的对比就是将其与其他调度类进行比较。

特性 CFS (SCHED_NORMAL/BATCH) 实时调度器 (SCHED_FIFO/RR) 截止时间调度器 (SCHED_DEADLINE)
核心调度目标 公平性 (Fairness) 可预测性 (Predictability) 保证截止时间 (Deadline Guarantee)
决策依据 虚拟运行时间 (vruntime) 静态优先级 (0-99) 任务的(runtime, period, deadline)参数
任务选择复杂度 O(log N) (N为可运行任务数) O(1) (位图查找) O(1) (从红黑树取最左节点)
公平性 非常好 (核心目标) 不保证 (高优先级会饿死低优先级) 不保证 (只关心截止时间)
对普通任务 专门为此设计 会被其完全抢占和饿死 会被其完全抢占和饿死
适用场景 所有通用计算负载（桌面、服务器）。 传统的软实时应用（工业控制、音频）。 需要可验证的硬实时保证的系统。

kernel/sched/fair.c

init_cfs_rq 初始化完全公平调度器运行队列

  • 这个设计的目的是为了解决vruntime的回绕（wrap-around）问题，并保证调度公平性。
    1. vruntime是单调递增的: 在CFS中，任务的vruntime会随着其运行而不断增加。理论上，它是一个无限增长的值。
    2. 回绕的风险: 作为一个64位的无符号整数，vruntime最终会达到最大值（2^64 - 1）然后回绕到0。如果处理不当，一个刚刚回绕到0的“老”任务，其vruntime会变得比所有其他任务都小，从而获得不公平的、超长的运行时间，饿死其他任务。
    3. min_vruntime的作用: min_vruntime是整个队列的“时间地平线”。所有任务的vruntime在进行比较和放置时，都是以vruntime - min_vruntime的形式，即相对值来进行的。调度器通过周期性地将所有任务的vruntime和队列的min_vruntime同时减去一个很大的值（重新归一化，normalize），来防止它们无限增长。
    4. 初始化的目的:
      将min_vruntime初始化为一个巨大的正数，就好像是把队列的“时间地平线”设置在了遥远的未来。
      当第一个任务被place_entity放置时，它的vruntime会被设置为大约等于avg_vruntime()，而avg_vruntime()又是基于min_vruntime计算的。
      关键在于: 内核不希望vruntime从0开始。如果从0开始，那么当系统运行很长时间后，一个新创建的任务以接近0的vruntime加入队列，它会获得巨大的抢占优势。更重要的是，从一个非常大的正数开始，可以给vruntime的回绕处理留下充足的缓冲空间。
      通过将vruntime置于一个远离0和2^64-1的中间地带，内核可以更安全、更从容地检测和处理即将到来的回绕，而不会在边界值附近出现突变。
      -(1LL << 20)这个具体的值并没有绝对的魔法。它只是选择了一个足够大的、可以提供充足缓冲的初始偏移量。选择2^20可能是因为它是一个不大不小、恰到好处的2的幂次方。
void init_cfs_rq(struct cfs_rq *cfs_rq)
{
	cfs_rq->tasks_timeline = RB_ROOT_CACHED;
	/* 虚拟运行时间是调度器用来衡量任务公平性的重要指标，任务的虚拟运行时间越小，调度器越倾向于优先调度该任务。 */
	cfs_rq->min_vruntime = (u64)(-(1LL << 20));
#ifdef CONFIG_SMP
	raw_spin_lock_init(&cfs_rq->removed.lock);
#endif
}

fair_server_init 初始化公平服务器

void fair_server_init(struct rq *rq)
{
	struct sched_dl_entity *dl_se = &rq->fair_server;

	init_dl_entity(dl_se);

	dl_server_init(dl_se, rq, fair_server_has_tasks, fair_server_pick_task);
}

DEFINE_SCHED_CLASS(fair)

/*
 * All the scheduling class methods:
 */
DEFINE_SCHED_CLASS(fair) = {

	.enqueue_task		= enqueue_task_fair,
	.dequeue_task		= dequeue_task_fair,
	.yield_task		= yield_task_fair,
	.yield_to_task		= yield_to_task_fair,

	.wakeup_preempt		= check_preempt_wakeup_fair,

	.pick_task		= pick_task_fair,
	.pick_next_task		= __pick_next_task_fair,
	.put_prev_task		= put_prev_task_fair,
	.set_next_task          = set_next_task_fair,

#ifdef CONFIG_SMP
	.balance		= balance_fair,
	.select_task_rq		= select_task_rq_fair,
	.migrate_task_rq	= migrate_task_rq_fair,

	.rq_online		= rq_online_fair,
	.rq_offline		= rq_offline_fair,

	.task_dead		= task_dead_fair,
	.set_cpus_allowed	= set_cpus_allowed_fair,
#endif

	.task_tick		= task_tick_fair,
	.task_fork		= task_fork_fair,

	.reweight_task		= reweight_task_fair,
	.prio_changed		= prio_changed_fair,
	.switched_from		= switched_from_fair,
	.switched_to		= switched_to_fair,

	.get_rr_interval	= get_rr_interval_fair,

	.update_curr		= update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
	.task_change_group	= task_change_group_fair,
#endif

#ifdef CONFIG_SCHED_CORE
	.task_is_throttled	= task_is_throttled_fair,
#endif

#ifdef CONFIG_UCLAMP_TASK
	.uclamp_enabled		= 1,
#endif
};

for_each_sched_entity 遍历调度实体

#define for_each_sched_entity(se) \
		for (; se; se = NULL)

sysctl_sched_base_slice 最小抢占粒度

  1. 调度延迟与粒度的权衡: CFS需要在一个矛盾中寻找平衡：
    • 低延迟（Low Latency）: 为了让交互式任务（如GUI、终端）感觉流畅，调度器应该频繁地切换任务，让每个任务都能尽快得到响应。这要求调度粒度非常小。
    • 高吞吐量（High Throughput）: 对于CPU密集型任务（如科学计算、视频编码），频繁的上下文切换是有害的。每次切换都会带来缓存失效（cache miss）、TLB刷新等开销。为了提高吞吐量，应该让任务尽可能长时间地运行。这要求调度粒度非常大。
  2. sysctl_sched_latency_ns: CFS引入了一个“目标抢占延迟”（sched_latency_ns，默认约6ms）。它试图保证在sched_latency_ns这么长的时间内，所有可运行的任务都至少能被调度一次。
  3. 时间片的计算: 一个任务的“时间片（timeslice）”是通过sched_latency_ns按其权重比例分配的。公式大致为：
    slice = sched_latency_ns * (task_weight / cfs_rq_total_weight)
  4. sched_base_slice的角色: 如果CPU上的可运行任务非常多，按比例计算出的slice可能会变得非常小（小于1ms），这将导致过于频繁的上下文切换，损害吞吐量。sysctl_sched_base_slice就是为了解决这个问题而存在的。它为时间片设定了一个下限。CFS计算出的时间片永远不会小于sched_base_slice。
  5. 动态调整: 注释中提到的0.70 msec * (1 + ilog(ncpus))是一个动态调整公式。它意味着在一个拥有更多CPU核心的系统上，这个最小抢占粒度会适当增大。这是因为在多核系统上，上下文切换的开销更大，而且通过任务迁移进行负载均衡的机会更多，因此可以容忍稍大的调度粒度。700000ULL (即0.7ms) 是这个公式的基础值。
/*
 * CPU密集型任务的最小抢占粒度：
 *
 * （默认值：0.70毫秒 * (1 + ilog(ncpus))，单位：纳秒）
 */
/* 定义了CFS调度器中一个CPU密集型任务在不被同等优先级的其他任务抢占的情况下，能够连续运行的最短时间保证。它本质上是CFS的最小抢占粒度 */
unsigned int sysctl_sched_base_slice			= 700000ULL;
static unsigned int normalized_sysctl_sched_base_slice	= 700000ULL;

__read_mostly unsigned int sysctl_sched_migration_cost	= 500000UL;

cfs_rq_min_slice 获取CFS运行队列的最小时间片

static inline u64 cfs_rq_min_slice(struct cfs_rq *cfs_rq)
{
	struct sched_entity *root = __pick_root_entity(cfs_rq);
	struct sched_entity *curr = cfs_rq->curr;
	u64 min_slice = ~0ULL;

	if (curr && curr->on_rq)
		min_slice = curr->slice;

	if (root)
		min_slice = min(min_slice, root->min_slice);

	return min_slice;
}

update_load_add update_load_sub update_load_set 更新负载权重

static inline void update_load_add(struct load_weight *lw, unsigned long inc)
{
	lw->weight += inc;
	lw->inv_weight = 0;
}

static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
{
	lw->weight -= dec;
	lw->inv_weight = 0;
}

static inline void update_load_set(struct load_weight *lw, unsigned long w)
{
	lw->weight = w;
	lw->inv_weight = 0;
}

__pick_root_entity 获取CFS运行队列的根调度实体

#define __node_2_se(node) \
	rb_entry((node), struct sched_entity, run_node)


struct sched_entity *__pick_root_entity(struct cfs_rq *cfs_rq)
{
	struct rb_node *root = cfs_rq->tasks_timeline.rb_root.rb_node;

	if (!root)
		return NULL;

	return __node_2_se(root);
}

avg_vruntime 算一个CFS运行队列（cfs_rq）的加权平均虚拟运行时（vruntime）

  • 在CFS/EEVDF调度器中，它的核心作用是计算一个CFS运行队列（cfs_rq）的加权平均虚拟运行时（vruntime）。这个“平均vruntime”代表了当前队列中所有可运行任务的“平均进度”，是新唤醒任务在队列中寻找其初始位置的核心基准点
/*
 * 特别说明：avg_vruntime() + 0 的结果必须使得 entity_eligible() := true。
 *           为此，本函数的计算结果必须有“左偏（向负无穷取整）”特性。
 *
 * @cfs_rq: 需要计算平均vruntime的CFS运行队列。
 * 返回值: u64类型的加权平均虚拟运行时。
 */
u64 avg_vruntime(struct cfs_rq *cfs_rq)
{
	/* @curr: 指向当前cfs_rq上正在运行的那个调度实体。*/
	struct sched_entity *curr = cfs_rq->curr;
	/* @avg:  64位有符号整型，用于存储vruntime的加权总和。
	 *         初始值为队列中除curr外所有任务的加权vruntime总和。*/
	s64 avg = cfs_rq->avg_vruntime;
	/* @load: 长整型，用于存储负载的总权重。
	 *         初始值为队列中除curr外所有任务的负载权重总和。*/
	long load = cfs_rq->avg_load;

	/* 检查当前cfs_rq上是否有正在运行的任务(curr)，并且该任务确实在运行队列上(on_rq)。*/
	if (curr && curr->on_rq) {
		/* 如果有，获取其经过缩放的负载权重。*/
		unsigned long weight = scale_load_down(curr->load.weight);

		/*
		 * 将当前任务的加权vruntime累加到总和中。
		 * entity_key()返回curr->vruntime - cfs_rq->min_vruntime，即相对vruntime。
		 */
		avg += entity_key(cfs_rq, curr) * weight;
		/* 将当前任务的负载权重累加到总权重中。*/
		load += weight;
	}

	/* 如果总权重不为零，则进行除法计算平均值。*/
	if (load) {
		/* 符号翻转会影响实际的下限/上限。*/
		/*
		 * 这是实现向负无穷取整（floor）的技巧。对于负数除法，
		 * C语言默认向零取整。例如 -7 / 4 = -1。
		 * 为了得到floor(-1.75) = -2，我们需要先将被除数调整。
		 * avg -= (load - 1) 就是这个调整步骤。
		 */
		if (avg < 0)
			avg -= (load - 1);
		/* 使用div_s64进行64位有符号整数除法。*/
		avg = div_s64(avg, load);
	}

	/*
	 * 将计算出的、相对于min_vruntime的平均值，加上队列的“时间基线”min_vruntime，
	 * 得到最终的、绝对的平均vruntime。
	 */
	return cfs_rq->min_vruntime + avg;
}

avg_vruntime_sub 从CFS运行队列（cfs_rq）的平均vruntime统计中减去一个调度实体（se）的vruntime贡献

static void
avg_vruntime_sub(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	unsigned long weight = scale_load_down(se->load.weight);
	s64 key = entity_key(cfs_rq, se);

	cfs_rq->avg_vruntime -= key * weight;
	cfs_rq->avg_load -= weight;
}

update_min_vruntime 重新计算并更新该队列的min_vruntime成员

  • 在CFS运行队列（cfs_rq）的成员发生变化（入队、出队、当前任务更新）后，重新计算并更新该队列的min_vruntime成员。 min_vruntime是整个CFS公平性得以实现、并防止vruntime无限增长的 “时间基线”或“水平面”。
/*
 * 这是一个静态函数，用于更新CFS运行队列的min_vruntime。
 * @cfs_rq: 指向需要更新的CFS运行队列。
 */
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	/* @se: 指向红黑树中获取CFS运行队列的根调度实体*/
	struct sched_entity *se = __pick_root_entity(cfs_rq);
	/* @curr: 指向当前正在CPU上运行的那个调度实体。*/
	struct sched_entity *curr = cfs_rq->curr;
	/* @vruntime: 64位无符号整型，用作计算新min_vruntime的临时变量，初始值为旧的min_vruntime。*/
	u64 vruntime = cfs_rq->min_vruntime;

	/* 检查当前cfs_rq上是否有正在运行的实体。*/
	if (curr) {
		/* 如果curr仍在运行队列上（on_rq为true）。*/
		if (curr->on_rq)
			/* 那么它的vruntime是新min_vruntime的一个候选值。*/
			vruntime = curr->vruntime;
		else
			/* 如果curr不在队列上（例如，正在被移除），则它不能作为候选者，将其视为NULL。*/
			curr = NULL;
	}

	/* 检查红黑树中是否存在实体（即树不为空）。*/
	if (se) {
		/* 如果当前没有正在运行的任务（curr为NULL）。*/
		if (!curr)
			/* 那么新的min_vruntime就由红黑树中最左边节点的min_vruntime决定。
			 * 注意：对于组实体，se->min_vruntime是其整个子树的最小vruntime。*/
			vruntime = se->min_vruntime;
		else
			/* 如果既有正在运行的任务，红黑树中也有任务，
			 * 则新的min_vruntime是这两者的vruntime中的较小者。*/
			vruntime = min_vruntime(vruntime, se->min_vruntime);
	}

	/*
	 * 确保我们永远不会因为被向后放置而获得时间。
	 */
	/*
	 * 调用__update_min_vruntime，它会确保最终的cfs_rq->min_vruntime
	 * 不会小于其旧值（参数vruntime是基于旧值计算的）。
	 * 这是防止vruntime“时间倒流”的关键保护。
	 */
	cfs_rq->min_vruntime = __update_min_vruntime(cfs_rq, vruntime);
}

update_curr 核算当前正在CPU上运行的CFS任务的虚拟运行时（vruntime）

  • 核算当前正在CPU上运行的CFS任务（cfs_rq->curr）从上次记账到当前时刻，所消耗的物理CPU时间，并将这段物理时间转换为加权的“虚拟运行时（vruntime）”，然后累加到该任务的vruntime上。
    这个函数是CFS实现其“完全公平”调度理念的数学和逻辑基石。调度器在做出任何重要决策之前（如抢占、入队、出队），都必须调用update_curr来确保所有任务的vruntime都是最新的，因为vruntime是CFS进行一切比较和排序的唯一度量衡
/*
 * 更新当前任务的运行时统计数据。
 */
static void update_curr(struct cfs_rq *cfs_rq)
{
	/* @curr: 指向当前CFS运行队列(cfs_rq)上，正在运行的那个调度实体。*/
	struct sched_entity *curr = cfs_rq->curr;
	/* @rq: 指向cfs_rq所属的物理运行队列。*/
	struct rq *rq = rq_of(cfs_rq);
	/* @delta_exec: 64位有符号整型，用于存储计算出的物理执行时间增量（单位：纳秒）。*/
	s64 delta_exec;
	/* @resched: 布尔标志，用于记录在更新过程中，是否有事件请求重新调度。*/
	bool resched;

	/* 如果当前cfs_rq上没有正在运行的实体（例如，CPU正处于idle状态），则直接返回。unlikely()是编译器优化提示。*/
	if (unlikely(!curr))
		return;

	/* 调用辅助函数update_curr_se，它会计算自上次更新以来，实体curr已执行的物理时间，并返回这个时间增量。*/
	delta_exec = update_curr_se(rq, curr);
	/* 如果时间增量为非正数（例如，由于时钟回绕或无实际执行），则无需进行后续更新，直接返回。*/
	if (unlikely(delta_exec <= 0))
		return;

	/*
	 * 将物理执行时间增量(delta_exec)通过calc_delta_fair函数，根据实体curr的负载权重，
	 * 转换为加权的虚拟运行时(vruntime)增量，然后累加到curr->vruntime上。
	 * 这是CFS公平性算法的核心。
	 */
	curr->vruntime += calc_delta_fair(delta_exec, curr);
	/* 检查并更新与调度延迟（deadline）相关的统计，该函数会判断任务是否运行了太久，如果需要抢占，则返回true。*/
	resched = update_deadline(cfs_rq, curr);
	/*
	 * 向前推进cfs_rq的min_vruntime。因为curr的vruntime刚刚增加了，
	 * 队列的“时间基线”min_vruntime可能也需要随之更新。
	 */
	update_min_vruntime(cfs_rq);

	/* 检查当前实体是否是一个真实的任务（而不是代表cgroup的组实体）。*/
	if (entity_is_task(curr)) {
		/* 如果是，获取其task_struct指针。*/
		struct task_struct *p = task_of(curr);

		/* 调用update_curr_task，更新与具体任务相关的其他统计（如CPU时间、perf事件等）。*/
		update_curr_task(p, delta_exec);

		/*
		 * 如果fair_server是激活的，我们需要对fair_server的时间进行记账，
		 * 无论该任务是否代表fair_server在运行：
		 *  - 如果任务代表fair_server运行，我们需要根据分配的运行时来限制它的时间。
		 *  - 在fair_server之外运行的公平任务，也应该对其进行记账，
		 *    以便fair_server能计入这段时间，并可能避免在本周期内运行。
		 */
		/* 检查用于SCHED_DEADLINE的公平服务器(fair_server)是否激活。*/
		if (dl_server_active(&rq->fair_server))
			/* 如果激活，则调用dl_server_update更新其消耗的带宽。*/
			dl_server_update(&rq->fair_server, delta_exec);
	}

	/* 为cfs_rq所属的cgroup带宽控制器记账已消耗的运行时delta_exec。*/
	account_cfs_rq_runtime(cfs_rq, delta_exec);

	/* 如果CFS运行队列中只有一个可运行任务（就是curr自己），那么不存在其他任务可以抢占它，直接返回。*/
	if (cfs_rq->nr_queued == 1)
		return;

	/* 如果update_deadline返回true要求抢占，或者did_preempt_short（检查是否是短暂运行后睡眠的任务）返回true。*/
	if (resched || did_preempt_short(cfs_rq, curr)) {
		/* 调用resched_curr_lazy，它会给当前任务(rq->curr)设置_TIF_NEED_RESCHED标志。*/
		resched_curr_lazy(rq);
		/* 清理与“伙伴调度”（一种让唤醒者和被唤醒者尽量在同一个CPU运行的优化）相关的提示，因为即将发生抢占。*/
		clear_buddies(cfs_rq, curr);
	}
}

account_entity_enqueue 更新CFS运行队列的负载和排队任务数

static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_add(&cfs_rq->load, se->load.weight);
#ifdef CONFIG_SMP
	if (entity_is_task(se)) {
		struct rq *rq = rq_of(cfs_rq);

		account_numa_enqueue(rq, task_of(se));
		list_add(&se->group_node, &rq->cfs_tasks);
	}
#endif
	cfs_rq->nr_queued++;
}

account_entity_dequeue 从CFS运行队列中移除一个调度实体，并更新负载和排队任务数

static void
account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_sub(&cfs_rq->load, se->load.weight);
#ifdef CONFIG_SMP
	if (entity_is_task(se)) {
		account_numa_dequeue(rq_of(cfs_rq), task_of(se));
		list_del_init(&se->group_node);
	}
#endif
	cfs_rq->nr_queued--;
}

## calc_delta_fair 将一个任务的物理执行时间（delta_exec），根据其负载权重，转换为虚拟运行时（vruntime）
- 计算 delta_exec * weight / lw->weight
- 在内核中，直接进行64位整数的乘法和除法是昂贵且容易溢出的。例如，delta_exec * weight的结果可能超过64位。直接使用浮点运算是不可接受的
	1. 反转权重 (inv_weight): 内核预先为每个可能的权重W计算了一个“反转权重” I = 2^32 / W。这个I是一个定点数，可以看作是1/W的放大表示。
	2. 变除法为乘法: 原始的 / lw->weight 操作，被转换为 * lw->inv_weight 再加上一个右移操作。即：X / W 约等于 (X * (2^32 / W)) >> 32。
	3. 防止溢出: 即便如此，delta_exec * fact (fact是另一个权重) 仍然可能溢出。因此，__calc_delta函数使用了一系列**位移（shift）和高位检查（fls）**的技巧。它会检查乘法操作的中间结果是否会溢出32位或64位，如果会，就先将操作数向右移动几位以“腾出空间”，然后将移动的位数从最终的右移位数中减去。这确保了所有中间计算都在64位整数的表示范围内。
```c
/*
 * delta_exec * weight / lw.weight
 *   或者
 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
 *
 * 要么 weight := NICE_0_LOAD 并且 lw 来自于 sched_prio_to_wmult[]，在这种情况下
 * 我们可以保证shift保持为正数，因为inv_weight保证能放入32位，而NICE_0_LOAD
 * 又提供了10位；因此 shift >= 22。
 *
 * 要么，weight <= lw.weight (因为lw.weight是运行队列的总权重)，因此
 * weight/lw.weight <= 1，所以我们的shift也同样会是正数。
 */
/*
 * 这是一个静态函数，用于执行核心的虚拟时间增量计算。
 * @delta_exec: 物理执行时间增量。
 * @weight:     一个权重，通常是NICE_0_LOAD。
 * @lw:         另一个负载权重结构体，包含了要作为除数的权重及其反转权重。
 */
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	/* @fact: 用于存储乘法因子的64位变量，初始值为传入的weight。*/
	u64 fact = scale_load_down(weight);
	/* @fact_hi: fact的高32位，用于溢出检查。*/
	u32 fact_hi = (u32)(fact >> 32);
	/* @shift: 最终右移的位数，初始为WMULT_SHIFT (通常是32)。*/
	int shift = WMULT_SHIFT;
	/* @fs: 临时变量，用于存储fls(find last set bit)的结果，即最高有效位的位数。*/
	int fs;

	/* 调用辅助函数，确保lw->inv_weight是最新的。*/
	__update_inv_weight(lw);

	/* 检查fact的高32位是否非零，即fact是否超过了32位。*/
	if (unlikely(fact_hi)) {
		/* 如果是，计算fact_hi的最高有效位的位置。*/
		fs = fls(fact_hi);
		/* 从最终的shift值中减去这个位数。*/
		shift -= fs;
		/* 将fact右移相应的位数，使其能够安全地放入一个稍大的32位空间，防止后续乘法溢出。*/
		fact >>= fs;
	}

	/* 执行核心的“反转乘法”：fact = fact * (2^32 / lw->weight)。*/
	fact = mul_u32_u32(fact, lw->inv_weight);

	/* 再次检查乘法结果fact的高32位是否非零。*/
	fact_hi = (u32)(fact >> 32);
	if (fact_hi) {
		/* 如果是，重复上述的溢出处理步骤，再次调整fact和shift值。*/
		fs = fls(fact_hi);
		shift -= fs;
		fact >>= fs;
	}

	/*
	 * 执行最终的乘法和右移操作：(delta_exec * fact) >> shift。
	 * mul_u64_u32_shr是一个优化的汇编函数，能高效地完成64位数与32位数的乘法并右移。
	 */
	return mul_u64_u32_shr(delta_exec, fact, shift);
}

/*
 * delta /= w
 * (此处的w是se->load.weight，但公式是用NICE_0_LOAD作为分子来归一化)
 */
/*
 * 这是一个静态内联函数，是上层代码调用的接口。
 * @delta: 物理执行时间增量。
 * @se:    目标调度实体。
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	/* 这是一个快速路径优化。如果任务的权重恰好等于基准权重NICE_0_LOAD... */
	if (unlikely(se->load.weight != NICE_0_LOAD))
		/* ...那么才需要调用__calc_delta来执行复杂的、带权重的缩放计算。
		 * 公式为: delta = delta * NICE_0_LOAD / se->load.weight */
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

	/* 如果权重等于基准权重，则虚拟时间增量就等于物理时间增量，直接返回delta。*/
	return delta;
}

reweight_task_fair 动态调整一个已在运行队列中的任务的调度权重

/*
 * 这是一个静态函数，负责在CFS运行队列中，动态地为一个调度实体调整权重。
 * @cfs_rq: se所属的CFS运行队列。
 * @se:     需要调整权重的调度实体。
 * @weight: 新的调度权重值。
 */
static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
			    unsigned long weight)
{
	/* @curr: 布尔标志，记录se是否就是当前正在CPU上运行的实体。*/
	bool curr = cfs_rq->curr == se;

	/* 检查se当前是否在运行队列上。*/
	if (se->on_rq) {
		/* 注释：提交未完成的执行时间。*/
		/* 调用update_curr，核算并累加se（如果是curr）或当前任务的vruntime。*/
		update_curr(cfs_rq);
		/* 更新se的vlag统计。*/
		update_entity_lag(cfs_rq, se);
		/* 这是一个与PLACE_REL_DEADLINE特性相关的vruntime到deadline的转换准备。*/
		se->deadline -= se->vruntime;
		se->rel_deadline = 1;
		/* 将cfs_rq的排队任务数减1，因为我们将要逻辑上将它取出。*/
		cfs_rq->nr_queued--;
		/* 如果se不是当前运行的任务，则调用__dequeue_entity将其从红黑树中物理移除。*/
		if (!curr)
			__dequeue_entity(cfs_rq, se);
		/* 从cfs_rq的总负载中减去se的旧权重。*/
		update_load_sub(&cfs_rq->load, se->load.weight);
	}
	/* 从cfs_rq的平均负载统计中，剥离se的贡献。*/
	// dequeue_load_avg(cfs_rq, se);

	/*
	 * 注释：因为我们保持 se->vlag = V - v_i，而 lag_i = w_i*(V - v_i)，
	 *       所以当w_i改变时，我们需要缩放se->vlag。
	 *
	 * 原理：为了保持物理lag的恒定，当权重w_i变化时，虚拟vlag必须反向缩放。
	 */
	se->vlag = div_s64(se->vlag * se->load.weight, weight);
	/* 如果使用了相对截止时间，也需要对deadline进行等比例缩放。*/
	if (se->rel_deadline)
		se->deadline = div_s64(se->deadline * se->load.weight, weight);

	/* 调用update_load_set，将新的权重值weight赋给se->load.weight。*/
	update_load_set(&se->load, weight);

/* 如果定义了SMP。*/
#ifdef CONFIG_SMP
	/* 这是一个do-while(0)的宏技巧，用于创建一个独立的作用域。*/
	do {
		/* 获取实体平均负载的PELT除数。*/
		u32 divider = get_pelt_divider(&se->avg);
		/* 根据新权重和旧的load_sum，重新计算实体的平均负载load_avg。*/
		se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
	} while (0);
#endif

	/* 将实体以新的权重，重新附加到cfs_rq的平均负载统计中。*/
	// enqueue_load_avg(cfs_rq, se);
	/* 再次检查se是否仍在运行队列上。*/
	if (se->on_rq) {
		/* 调用place_entity，根据se的新权重和当前vruntime，为其计算一个新的放置位置。*/
		place_entity(cfs_rq, se, 0);
		/* 将se的新权重加回到cfs_rq的总负载中。*/
		update_load_add(&cfs_rq->load, se->load.weight);
		/* 如果se不是当前运行任务，则将其物理地插回到红黑树中。*/
		if (!curr)
			__enqueue_entity(cfs_rq, se);
		/* 将cfs_rq的排队任务数加1，恢复计数。*/
		cfs_rq->nr_queued++;

		/*
		 * 注释：实体的vruntime已被调整，所以我们检查一下是否需要更新
		 *       整个rq范围的min_vruntime。因为上面的计算需要稳定的
		 *       而非最新的min_vruntime，所以我们在reweight过程的
		 *       最后进行更新。
		 */
		update_min_vruntime(cfs_rq);
	}
}

/*
 * 这是一个静态函数，是fair_sched_class的reweight_task方法的实现。
 * @rq:  指向物理运行队列。
 * @p:   指向需要调整权重的任务。
 * @lw:  指向包含新权重和新反转权重的load_weight结构体。
 */
static void reweight_task_fair(struct rq *rq, struct task_struct *p,
			       const struct load_weight *lw)
{
	/* @se: 指向任务p的调度实体。*/
	struct sched_entity *se = &p->se;
	/* @cfs_rq: 获取se所属的CFS运行队列。*/
	struct cfs_rq *cfs_rq = cfs_rq_of(se);
	/* @load: 指向se内部的load_weight结构体。*/
	struct load_weight *load = &se->load;

	/* 调用核心的reweight_entity函数，传递新的权重lw->weight。*/
	reweight_entity(cfs_rq, se, lw->weight);
	/* 单独更新反转权重值。*/
	load->inv_weight = lw->inv_weight;
}

place_entity 为一个调度实体（se）计算一个合适的初始vruntime（虚拟运行时）和deadline（虚拟截止时间），以决定它在红黑树中的初始位置

  • place_entity是CFS调度器中的一个核心辅助函数。当一个新唤醒的或迁移来的任务需要被放入CFS运行队列（红黑树）时，此函数被调用。
    它的核心作用是：为一个调度实体（se）计算一个合适的初始vruntime（虚拟运行时）和deadline（虚拟截止时间），以决定它在红黑树中的初始位置。 这个“放置”策略直接决定了新任务的响应速度和对现有任务的公平性。
    其工作原理基于**EEVDF (Earliest Eligible Virtual Deadline First)**调度算法，这是一种比传统CFS更先进的公平调度算法。其原理可以概括为：
/*
 * 这是一个静态函数，负责为一个调度实体se计算其在cfs_rq中的初始位置。
 * @cfs_rq: se将要被放入的CFS运行队列。
 * @se:     将要被放置的调度实体。
 * @flags:  一组标志，指示入队的类型（如ENQUEUE_INITIAL表示全新任务）。
 */
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/* @vslice: 存储根据实体的时间片(slice)和权重计算出的虚拟时间片。*/
	u64 vslice;
	/* @vruntime: 获取当前cfs_rq的平均虚拟运行时，作为放置的基准。*/
	u64 vruntime = avg_vruntime(cfs_rq);
	/* @lag: 64位有符号整型，用于存储se在被换出时，相对于平均水平的“延迟”或“领先”。*/
	s64 lag = 0;

	/* 如果se没有使用自定义的时间片长度。*/
	if (!se->custom_slice)
		/* 则将其时间片设置为系统默认的基础时间片(sysctl_sched_base_slice)。*/
		se->slice = sysctl_sched_base_slice;
	/* 调用calc_delta_fair，将物理时间片se->slice转换为加权的虚拟时间片vslice。*/
	vslice = calc_delta_fair(se->slice, se);

	/*
	 * 由于V(平均vruntime)是作为实体vruntime的加权平均值构建的，
	 * 添加具有正lag的任务，或移除具有负lag的任务，都会使“时间”倒退，
	 * 这会搞乱其他任务的lag。
	 *
	 * EEVDF：放置策略 #1 / #2
	 */
	/* 如果内核开启了PLACE_LAG特性，且队列非空，且se有历史lag值。*/
	if (sched_feat(PLACE_LAG) && cfs_rq->nr_queued && se->vlag) {
		/* curr: 指向当前正在运行的实体。*/
		struct sched_entity *curr = cfs_rq->curr;
		/* load: 用于存储队列的总负载。*/
		unsigned long load;

		/* 将se的历史vlag值赋给lag。*/
		lag = se->vlag;

		/*
		 * 如果我们想要放置一个任务并保留其lag，我们必须考虑新实体对加权
		 * 平均值的影响，并对此进行补偿，否则lag会迅速消失。
		 *
		 * Lag的定义为:
		 *
		 *   lag_i = S - s_i = w_i * (V - v_i)
		 *
		 * 为了避免到处都是'w_i'项，我们只跟踪虚拟lag:
		 *
		 *   vl_i = V - v_i  <=>  v_i = V - vl_i
		 *
		 * 我们取V为所有v的加权平均值:
		 *
		 *   V = (Σ w_j*v_j) / W
		 *
		 * 其中 W 是: Σ w_j
		 *
		 * 那么，在添加一个具有lag vl_i的实体后，加权平均值变为:
		 *
		 *   V' = (Σ w_j*v_j + w_i*v_i) / (W + w_i)
		 *      = (W*V + w_i*(V - vl_i)) / (W + w_i)
		 *      = ...
		 *      = V - w_i*vl_i / (W + w_i)
		 *
		 * 添加一个具有vl_i的实体后，实际的lag变为:
		 *
		 *   vl'_i = V' - v_i
		 *         = ...
		 *         = vl_i - w_i*vl_i / (W + w_i)
		 *
		 * 它严格小于vl_i。所以为了保留lag，我们应该在放置前膨胀lag，
		 * 以便放置后的有效lag恰好是我们出队前计算的lag。
		 *
		 * 因此，反转上述vl'_i的关系，得到我们需要的vl_i，以便放置后
		 * 的lag是我们出队前计算的lag。
		 *
		 *   vl_i = (W + w_i)*vl'_i / W
		 */
		/* load = 队列的总负载。*/
		load = cfs_rq->avg_load;
		/* 如果有当前运行的任务，并且它也在队列上，则将其负载也计入。*/
		if (curr && curr->on_rq)
			load += scale_load_down(curr->load.weight);

		/* 根据公式计算膨胀后的lag：lag = lag * (W + w_i)。*/
		lag *= load + scale_load_down(se->load.weight);
		/* 健壮性检查，防止除以零。*/
		if (WARN_ON_ONCE(!load))
			load = 1;
		/* 根据公式完成膨胀：lag = lag / W。*/
		lag = div_s64(lag, load);
	}

	/*
	 * 设置实体的初始vruntime。
	 * se->vruntime = V - vl_i(膨胀后)
	 * 这样，当它被加入队列后，其真实的vruntime(v_i)就会被正确地放置。
	 */
	se->vruntime = vruntime - lag;

	/* 如果这是一个设置了相对截止时间（用于PLACE_REL_DEADLINE）的实体。*/
	if (se->rel_deadline) {
		/* 将其相对截止时间转换为绝对截止时间。*/
		se->deadline += se->vruntime;
		/* 清除相对截止时间标志。*/
		se->rel_deadline = 0;
		/* 直接返回，因为它不使用EEVDF的deadline计算。*/
		return;
	}

	/*
	 * 当加入竞争时；现有的任务平均来说，将处于其时间片的一半。
	 * 因此，让新任务以半个时间片开始，以平滑地融入竞争。
	 */
	/* 如果开启了PLACE_DEADLINE_INITIAL特性，且这是一个全新任务的首次入队。*/
	if (sched_feat(PLACE_DEADLINE_INITIAL) && (flags & ENQUEUE_INITIAL))
		/* 将其初始的虚拟时间片减半。*/
		vslice /= 2;

	/*
	 * EEVDF: vd_i = ve_i + r_i/w_i
	 * (虚拟截止时间 = 虚拟入队时间 + 加权运行时)
	 */
	/* 根据EEVDF公式，计算出该实体的虚拟截止时间，这是它在红黑树中排序的键。*/
	se->deadline = se->vruntime + vslice;
}


## avg_vruntime_add 将一个调度实体（se）的vruntime贡献累加到CFS运行队列（cfs_rq）的平均vruntime统计中
```c
/*
 * 这是一个静态内联函数，用于计算一个实体在其cfs_rq中的排序键。
 * @cfs_rq: 该实体所属的CFS运行队列。
 * @se:     目标调度实体。
 * 返回值：实体相对于队列min_vruntime的“相对虚拟运行时”。
 */
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/* 返回实体的绝对vruntime与队列的最小vruntime基线之差。这是一个有符号值。*/
	return (s64)(se->vruntime - cfs_rq->min_vruntime);
}

/*
 * 从每个任务的服务数计算虚拟时间：
 *
 * 公平调度器遵循滞后守恒原则：
 *
 *   Σ lag_i = 0
 *
 * 其中lag_i由下式给出：
 *
 *   lag_i = S - s_i = w_i * (V - v_i)
 *
 * S是理想的服务时间，V是其虚拟时间对应物。因此：
 *
 *   Σ lag_i = 0
 *   Σ w_i * (V - v_i) = 0
 *   Σ w_i * V - w_i * v_i = 0
 *
 * 从中我们可以解出V关于v_i的表达式（v_i我们已在se->vruntime中持有）：
 *
 *       Σ v_i * w_i   Σ v_i * w_i
 *   V = -------------- = --------------
 *          Σ w_i            W
 *
 * 具体来说，这是所有实体虚拟运行时的加权平均值。
 *
 * [[ 注意：这只在加入/离开操作发生在lag_i = 0的条件下，才等于理想
 *          调度器。否则，虚拟时间会有相当于 V +-= lag_i / W 的
 *          非连续运动。另见place_entity()中处理此问题的注释。]]
 *
 * 然而，由于v_i是u64，乘法可能轻易溢出，因此将其转换为
 * 使用更小数值的相对形式：
 *
 * 替换：v_i == (v_i - v0) + v0
 *
 *     Σ ((v_i - v0) + v0) * w_i   Σ (v_i - v0) * w_i
 * V = ---------------------------- = --------------------- + v0
 *                  W                            W
 *
 * 我们使用以下变量来跟踪它：
 *
 *                    v0 := cfs_rq->min_vruntime
 * Σ (v_i - v0) * w_i := cfs_rq->avg_vruntime
 *              Σ w_i := cfs_rq->avg_load
 *
 * 由于min_vruntime是一个单调递增的、紧密跟踪每个任务服务的变量，
 * 这些增量：(v_i - v0)，将处于系统中由于量化而引起的最大（虚拟）
 * 滞后的数量级。
 *
 * 此外，我们使用scale_load_down()来减小数值的大小。
 *
 * 根据测量，(key * weight)的最大值在一次内核构建中约为44位。
 */
/*
 * 这是一个静态函数，当一个实体se被加入cfs_rq时，用于更新队列的平均vruntime统计。
 * @cfs_rq: 目标CFS运行队列。
 * @se:     被加入的调度实体。
 */
static void
avg_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/* @weight: 获取实体se的负载权重，并使用scale_load_down进行可能的缩放。*/
	unsigned long weight = scale_load_down(se->load.weight);
	/* @key: 调用entity_key计算实体se的相对vruntime。*/
	s64 key = entity_key(cfs_rq, se);

	/* 将该实体的加权相对vruntime，累加到cfs_rq的avg_vruntime总和中。*/
	cfs_rq->avg_vruntime += key * weight;
	/* 将该实体的权重，累加到cfs_rq的avg_load总和中。*/
	cfs_rq->avg_load += weight;
}

__enqueue_entity 将一个已经计算好vruntime和deadline的调度实体（se），物理地插入到CFS运行队列（cfs_rq）的**红黑树（tasks_timeline）**中

/*
 * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
 *
 * (此公式表明，一个节点的最小vruntime，等于它自身的vruntime、
 *  其左子树的最小vruntime、其右子树的最小vruntime，这三者中的最小值。)
 */
/*
 * 这是一个静态内联函数，作为增强红黑树的回调，用于重新计算并更新
 * 一个调度实体se的min_vruntime和min_slice聚合属性。
 * @se:   需要更新的目标调度实体。
 * @exit: 一个布尔值，在某些回调场景下有特殊用途，这里未使用。
 * 返回值: 如果se的聚合属性在更新后没有发生变化，则返回true，否则返回false。
 */
static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
{
	/* @old_min_vruntime: 用于保存更新前se->min_vruntime的原始值，以备后续比较。*/
	u64 old_min_vruntime = se->min_vruntime;
	/* @old_min_slice: 用于保存更新前se->min_slice的原始值。*/
	u64 old_min_slice = se->min_slice;
	/* @node: 指向se内部的红黑树节点成员。*/
	struct rb_node *node = &se->run_node;

	/*
	 * 步骤1：将se的min_vruntime首先重置为其自身的vruntime。
	 *        这是递归计算的起始基准值。
	 */
	se->min_vruntime = se->vruntime;
	/*
	 * 步骤2：与右子树的最小值进行比较并更新。
	 *        __min_vruntime_update会检查右子节点是否存在，如果存在，则
	 *        se->min_vruntime = min(se->min_vruntime, right_child->min_vruntime)。
	 */
	__min_vruntime_update(se, node->rb_right);
	/*
	 * 步骤3：与左子树的最小值进行比较并更新。
	 *        __min_vruntime_update会检查左子节点是否存在，如果存在，则
	 *        se->min_vruntime = min(se->min_vruntime, left_child->min_vruntime)。
	 */
	__min_vruntime_update(se, node->rb_left);

	/*
	 * 对min_slice执行完全相同的逻辑。
	 */
	/* 步骤1：重置为自身的slice。*/
	se->min_slice = se->slice;
	/* 步骤2：与右子树的min_slice比较。*/
	__min_slice_update(se, node->rb_right);
	/* 步骤3：与左子树的min_slice比较。*/
	__min_slice_update(se, node->rb_left);

	/*
	 * 步骤4：比较更新前后的值，并返回结果。
	 *        这个返回值是提供给_propagate回调的优化信号。如果返回true
	 *        (值未变)，向上的传播就可以安全地提前终止。
	 */
	return se->min_vruntime == old_min_vruntime &&
	       se->min_slice == old_min_slice;
}

/* 用于声明一组红黑树“增强（augmented）”功能所需的回调函数。
增强红黑树是一种在标准红黑树的节点上，额外存储一些“聚合”信息的数据结构。当树的结构发生旋转变化时，需要通过回调函数来高效地更新这些聚合信息。
在CFS中，这个聚合信息就是**“以该节点为根的子树中，所有实体min_vruntime的最小值”**。这个值被存储在每个rb_node的__rb_parent_color字段的额外位中（通过min_vruntime_update回调来维护） */
/*
 * 这是一个辅助宏，用于声明一组与红黑树增强功能相关的回调函数。
 * static:           回调函数为静态类型。
 * min_vruntime_cb:  这组回调函数的名称。
 * struct sched_entity: 红黑树节点所属的数据结构类型。
 * run_node:         红黑树节点(rb_node)在sched_entity结构中的成员名。
 * min_vruntime:     用于聚合的、sched_entity中的成员名。
 * min_vruntime_update: 当树结构改变时，用于更新父节点聚合信息的回调函数名。
 */
RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
		     run_node, min_vruntime, min_vruntime_update);

/*
 * 将一个实体入队到红黑树中。
 */
/*
 * 这是一个静态函数，负责将调度实体se物理地插入到cfs_rq的红黑树中。
 * @cfs_rq: se所属的CFS运行队列。
 * @se:     将要被插入的调度实体。
 */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/* 调用avg_vruntime_add，将实体se的加权vruntime贡献累加到cfs_rq的平均vruntime统计中。*/
	avg_vruntime_add(cfs_rq, se);
	/*
	 * 初始化实体自身的min_vruntime。对于一个叶子节点，
	 * 其子树中最小的vruntime就是它自己的vruntime。
	 * 这个值将在后续的树旋转中，被用于更新其父节点的聚合信息。
	 */
	se->min_vruntime = se->vruntime;
	/* 初始化实体的最小时间片。*/
	se->min_slice = se->slice;
	/*
	 * 调用通用的、带缓存的、增强红黑树插入函数。
	 * @&se->run_node:          要插入的节点。
	 * @&cfs_rq->tasks_timeline: 红黑树的根。
	 * @__entity_less:          一个函数指针，用于比较两个实体的大小（基于vruntime），以决定插入位置。
	 * @&min_vruntime_cb:       指向包含了更新回调函数的结构体。当插入导致树旋转时，
	 *                          此回调会被自动调用，以维持自底向上所有节点的
	 *                          “子树最小min_vruntime”这个聚合信息的正确性。
	 */
	rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
				__entity_less, &min_vruntime_cb);
}

enqueue_entity 将单个调度实体（sched_entity）插入到其所属的CFS运行队列（cfs_rq）的红黑树中

  • enqueue_entity是CFS调度器中负责将单个调度实体（sched_entity）插入到其所属的CFS运行队列（cfs_rq）的红黑树中的底层核心函数。它是上层enqueue_task_fair等函数的最终执行者，是“入队”操作的最小原子单位。
    它的核心作用是：在更新完所有与实体相关的统计数据（特别是vruntime和负载）之后，调用__enqueue_entity将实体物理地插入红黑树，并更新队列的状态。
/*
 * 这是一个静态函数，负责将单个调度实体se入队到其cfs_rq。
 * @cfs_rq: se所属的CFS运行队列。
 * @se:     将要被入队的调度实体。
 * @flags:  一组标志，指示入队的具体原因(如ENQUEUE_WAKEUP, ENQUEUE_MIGRATED)。
 */
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/* 声明一个布尔变量curr，并检查se是否就是cfs_rq当前正在运行的那个实体。*/
	bool curr = cfs_rq->curr == se;

	/*
	 * 如果我们是当前任务，我们必须在调用update_curr()之前进行重新归一化。
	 */
	/* 如果se是当前运行的实体。*/
	if (curr)
		/* 调用place_entity。对于当前任务，这通常是更新其vruntime和deadline。*/
		place_entity(cfs_rq, se, flags);

	/* 调用update_curr，核算当前运行任务的vruntime，以确保cfs_rq的vruntime时钟是最新、最准确的。这是所有后续操作的基础。*/
	update_curr(cfs_rq);

	/*
	 * 当一个sched_entity入队时，我们必须：
	 *   - 更新负载，使实体和cfs_rq都与当前时间同步。
	 *   - 对于group_entity，更新其runnable_weight以反映其组cfs_rq新的h_nr_runnable。
	 *   - 对于group_entity，更新其权重以反映其组cfs_rq新的份额。
	 *   - 将其新的权重加到cfs_rq->load.weight。
	 */
	/* 调用update_load_avg，更新实体和cfs_rq的平均负载(PELT)。DO_ATTACH表示实体正在被加入队列。*/
	// update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
	/* 调用se_update_runnable，更新实体自身的可运行状态统计。*/
	// se_update_runnable(se);
	/*
	 * XXX 上面的update_load_avg()已经将我们附加到pelt的总和中；
	 * 但这里的update_cfs_group()会重新调整权重，并且不得不撤销/重做
	 * 所有那些操作。看起来很浪费。
	 */
	/* 如果se是一个组实体，则递归更新整个组的负载信息。*/
	// update_cfs_group(se);

	/*
	 * XXX 既然实体已经被重新加权，并且它的延迟也已调整，
	 * 我们可以放置该实体了。
	 */
	/* 如果se不是当前运行的实体（即一个新唤醒或迁移来的任务）。*/
	if (!curr)
		/* 调用place_entity，为其计算一个合适的初始vruntime，以决定其在红黑树中的位置。*/
		place_entity(cfs_rq, se, flags);

	/* 调用account_entity_enqueue，更新cfs_rq的总负载权重和nr_running计数。*/
	account_entity_enqueue(cfs_rq, se);

	/* 实体已迁移，不再认为这个任务是热的。*/
	/* 如果这是一次迁移入队。*/
	if (flags & ENQUEUE_MIGRATED)
		/* 重置其执行开始时间，这会影响其能否被认为是“缓存热”的。*/
		se->exec_start = 0;

	/* 检查是否需要更新调度统计。*/
	// check_schedstat_required();
	/* 更新其他与入队相关的统计数据（如等待时间）。*/
	// update_stats_enqueue_fair(cfs_rq, se, flags);
	/* 如果se不是当前运行的实体。*/
	if (!curr)
		/* 调用__enqueue_entity，将其物理地插入到cfs_rq的红黑树中。*/
		__enqueue_entity(cfs_rq, se);
	/* 将se标记为在队列上。*/
	se->on_rq = 1;

	/* 如果这是cfs_rq中的第一个入队任务（队列从空变非空）。*/
	if (cfs_rq->nr_queued == 1) {
		/* 检查是否需要解除对该cfs_rq的节流（带宽控制）。*/
		// check_enqueue_throttle(cfs_rq);
		/* 如果该cfs_rq及其所有祖先都没有被节流。
		renturn 0*/
// 		if (!throttled_hierarchy(cfs_rq)) {
// 			/* 则将这个cfs_rq添加到全局的“叶子cfs_rq”链表中，表示它现在是活跃的。*/
// 			// list_add_leaf_cfs_rq(cfs_rq);
// 		} else {
// /* 如果内核配置了CFS带宽控制。*/
// #ifdef CONFIG_CFS_BANDWIDTH
// 			/* 获取cfs_rq所属的物理运行队列。*/
// 			struct rq *rq = rq_of(cfs_rq);

// 			/* 如果cfs_rq被节流了但还没有记录节流时钟，则记录下来。*/
// 			if (cfs_rq_throttled(cfs_rq) && !cfs_rq->throttled_clock)
// 				cfs_rq->throttled_clock = rq_clock(rq);
// 			/* 记录自身的节流时钟。*/
// 			if (!cfs_rq->throttled_clock_self)
// 				cfs_rq->throttled_clock_self = rq_clock(rq);
// #endif
// 		}
	}
}

enqueue_task_fair 将一个指定的任务（p）及其调度实体（se），正确地插入到CFS的运行队列（红黑树）中，并更新所有相关的调度统计数据（如虚拟运行时、负载、利用率等）

  • enqueue_task_fair是**公平调度类（fair_sched_class）**的enqueue_task方法实现。当一个属于CFS调度的任务变为可运行状态（例如，从睡眠中被唤醒，或新创建的任务被激活）时，调度器核心就会调用此函数。
    它的核心作用是：将一个指定的任务（p）及其调度实体（se），正确地插入到CFS的运行队列（红黑树）中，并更新所有相关的调度统计数据（如虚拟运行时、负载、利用率等）。
/*
 * enqueue_task方法在nr_running增加之前被调用。
 * 在这里，我们更新公平调度的统计数据，然后将任务放入红黑树中。
 */
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	/* 声明一个指向CFS运行队列的指针，用于在循环中指向当前层级的cfs_rq。*/
	struct cfs_rq *cfs_rq;
	/* 声明一个指向调度实体的指针，并用任务p自身的调度实体(&p->se)进行初始化。这是遍历的起点。*/
	struct sched_entity *se = &p->se;
	/* 声明并初始化一个标志，用于在cgroup层级间向上传播“有多少IDLE策略任务加入”。task_has_idle_policy判断任务p是否为IDLE策略。*/
	int h_nr_idle = task_has_idle_policy(p);
	/* 声明并初始化一个标志，用于在cgroup层级间向上传播“有多少可运行任务加入”。初始为1，代表任务p自身。*/
	int h_nr_runnable = 1;
	/* 声明并初始化一个布尔标志。如果入队标志flags中不包含ENQUEUE_WAKEUP，则为true，表示这是一个全新任务的首次入队。*/
	int task_new = !(flags & ENQUEUE_WAKEUP);
	/* 声明并初始化一个变量，用于在操作前保存根cfs_rq中已排队的层级任务数，用于后续比较判断队列是否从空闲变为非空闲。*/
	int rq_h_nr_queued = rq->cfs.h_nr_queued;
	/* 声明一个64位无符号整型，用于在cgroup层级间自顶向下传递和设置任务的时间片(slice)。*/
	u64 slice = 0;

	/*
	 * 下面的代码会（间接地）更新schedutil，它会查看cfs_rq的利用率
	 * 来选择一个CPU频率。让我们在更新schedutil之前，
	 * 将任务的估算利用率加到cfs_rq的估算利用率中。
	 */
	/* 检查任务是否不处于“延迟调度”状态，或者本次入队是一个“延迟入队”操作。*/
	// if (!p->se.sched_delayed || (flags & ENQUEUE_DELAYED))
	// 	/* 如果满足条件，调用util_est_enqueue，将任务p的利用率估算值贡献到根CFS队列(&rq->cfs)中。*/
	// 	util_est_enqueue(&rq->cfs, p);

	/* 检查入队标志是否为ENQUEUE_DELAYED，表示这是一个“延迟入队”的快速路径。*/
	if (flags & ENQUEUE_DELAYED) {
		/* 调用requeue_delayed_entity，仅处理延迟实体的状态，而不执行完整的入队逻辑。*/
		requeue_delayed_entity(se);
		/* 快速路径，直接返回。*/
		return;
	}

	/*
	 * 如果in_iowait被设置，下面的代码可能不会触发任何cpufreq
	 * 利用率更新，所以在这里用IOWAIT标志显式地更新它。
	 */
	/* 检查任务p是否处于等待I/O的状态。*/
	// if (p->in_iowait)
		/* 如果是，则显式调用cpufreq_update_util，通知CPU频率调控器有I/O等待负载，可能需要调整频率。*/
		// cpufreq_update_util(rq, SCHED_CPUFREQ_IOWAIT);

	/* 如果这是一个新任务(task_new为true)，并且它当前处于“延迟调度”状态(se->sched_delayed为true)...*/
	if (task_new && se->sched_delayed)
		/* ...则它虽然入队，但逻辑上尚不可运行，因此它对层级可运行任务数的贡献暂时为0。*/
		h_nr_runnable = 0;

	/*
	 * 开始沿着cgroup层级树自底向上遍历。这个循环会将实体及其所有可运行的祖先实体入队。
	 */
	for_each_sched_entity(se) {
		/* 检查当前实体se是否已在运行队列上（se->on_rq为true）。*/
		if (se->on_rq) {
			/* 如果已在队列上，但又被标记为延迟，则调用requeue_delayed_entity特殊处理。*/
			if (se->sched_delayed)
				requeue_delayed_entity(se);
			/* 既然已在队列上，无需继续向上遍历，中止循环。*/
			break;
		}
		/* 获取实体se所属的CFS运行队列cfs_rq。*/
		cfs_rq = cfs_rq_of(se);

		/*
		 * 基本上，将组条目的slice设置为它们各自cfs_rq的min_slice。
		 * 这确保了组可以在期望的时间范围内为其内部实体提供服务。
		 */
		/* 如果slice非零（表示从父队列传递下来了时间片信息）。*/
		if (slice) {
			/* 将继承的时间片赋给当前实体。*/
			se->slice = slice;
			/* 标记该实体使用了自定义时间片。*/
			se->custom_slice = 1;
		}
		/* 调用enqueue_entity，这是将实体插入cfs_rq红黑树的核心操作。*/
		enqueue_entity(cfs_rq, se, flags);
		/* 获取当前cfs_rq的最小时间片，以便在下一轮循环中传递给其父实体。*/
		slice = cfs_rq_min_slice(cfs_rq);

		/* 从本层cfs_rq开始，向上级联更新层级统计计数。*/
		cfs_rq->h_nr_runnable += h_nr_runnable;
		cfs_rq->h_nr_queued++;
		cfs_rq->h_nr_idle += h_nr_idle;

		/* 如果当前cfs_rq因为这个实体的加入而从空闲变为非空闲。*/
		if (cfs_rq_is_idle(cfs_rq))
			/* 那么它对上层来说，贡献了1个“非空闲”的子实体，所以向上传播的h_nr_idle应为1。*/
			h_nr_idle = 1;

		/* 在遇到一个被节流的cfs_rq时，结束评估。*/
		// if (cfs_rq_throttled(cfs_rq))
		// 	/* 如果cgroup的CPU带宽已用尽，它在父队列中是不可运行的，无需再向上传播，跳转到收尾步骤。*/
		// 	goto enqueue_throttle;

		/* 对于任务自身以上的祖先实体，其入队行为应被视为一次“唤醒”，而非“新建”。*/
		flags = ENQUEUE_WAKEUP;
	}

	/*
	 * 用于更新负载相关的统计。
	 */
	for_each_sched_entity(se) {
		/* 获取实体se所属的CFS运行队列cfs_rq。*/
		cfs_rq = cfs_rq_of(se);

		// /* 调用update_load_avg，更新实体se和cfs_rq的平均负载（PELT）。UPDATE_TG表示需要更新任务组。*/
		// update_load_avg(cfs_rq, se, UPDATE_TG);
		// /* 调用se_update_runnable，更新实体自身的可运行状态统计。*/
		// se_update_runnable(se);
		// /* 如果se是组实体，则递归更新整个组的负载信息。*/
		// update_cfs_group(se);

		/* 再次确保时间片的正确传递和设置。*/
		se->slice = slice;
		/* 如果se不是当前正在运行的任务，需要传播min_vruntime的回调。*/
		if (se != cfs_rq->curr)
			min_vruntime_cb_propagate(&se->run_node, NULL);
		/* 获取当前cfs_rq的最小时间片，为上层做准备。*/
		slice = cfs_rq_min_slice(cfs_rq);

		/* 在一些版本中，层级计数的更新可能放在这个循环中。*/
		cfs_rq->h_nr_runnable += h_nr_runnable;
		cfs_rq->h_nr_queued++;
		cfs_rq->h_nr_idle += h_nr_idle;

		// /* 同样，更新向上传播的h_nr_idle标志。*/
		// if (cfs_rq_is_idle(cfs_rq))
		// 	h_nr_idle = 1;

		// /* 在遇到一个被节流的cfs_rq时，结束评估。*/
		// if (cfs_rq_throttled(cfs_rq))
		// 	goto enqueue_throttle;
	}

	/* 如果物理CPU的根CFS队列之前是空的(rq_h_nr_queued为0)，但现在非空了。*/
	if (!rq_h_nr_queued && rq->cfs.h_nr_queued) {
		/* 核算空闲运行时 */
		/* 如果整个CPU都没有运行任务，则更新DL-server的空闲时间。*/
		if (!rq->nr_running)
			dl_server_update_idle_time(rq, rq->curr);
		/* 启动公平服务器（fair_server），这是用于让CFS任务能“借用”SCHED_DEADLINE带宽的机制。*/
		dl_server_start(&rq->fair_server);
	}

	/* 此时se为NULL，我们已在根级别。*/
	/* 将物理运行队列rq的总运行任务数加1。*/
	add_nr_running(rq, 1);

	/*
	 * 由于新任务被赋予的初始util_avg等于其CPU空闲容量的一半，
	 * 微小任务有可能越过超载阈值，这将导致负载均衡器破坏所有
	 * 由EAS完成的任务放置。作为缓解此影响的一种方法，在检测
	 * 超载标志时，不计入新任务的首次入队操作。
	 *
	 * 一个更好的解决方法是等待任务的PELT信号收敛后再将其计入，
	 * 但这实现起来不直接，而下面的方法在实践中通常足够好。
	 */
	/* 如果这不是一个新任务的首次入队。*/
	// if (!task_new)
	// 	/* 则调用check_update_overutilized_status，检查并更新CPU的超载状态。*/
	// 	check_update_overutilized_status(rq);

enqueue_throttle: /* 这是一个goto标签，作为前面循环中遇到节流队列时的跳出点。*/
	/* 这是一个调试断言，用于在内核开发阶段检查CFS运行队列的叶子节点列表的完整性和一致性。*/
	// assert_list_leaf_cfs_rq(rq);

	/* 更新高精度调度时钟(hrtick)。因为队列中加入了一个新任务，下一个理想的抢占点可能发生了变化，需要重新设置定时器。*/
	hrtick_update(rq);
}

update_entity_lag 计算并更新该实体se的“虚拟延迟（vlag）”值

  • vlag是一个度量，它反映了实体se的vruntime相对于其所属的CFS运行队列cfs_rq的平均vruntime的偏离程度。
  • 其基本原理如下：
    1. 理想的公平: 在一个理想的CFS系统中，所有可运行任务的vruntime都应该大致相等，并与队列的平均vruntime保持一致。
    2. 延迟（Lag）的定义:
      • lag_i = S - s_i，其中S是系统的虚拟时间（用avg_vruntime近似），s_i是任务i的虚拟时间（se->vruntime）。
      • 如果vlag为一个大的正数，意味着se->vruntime远小于平均值。这说明该任务被“亏欠”了很多运行时间，它是一个“受害者（victim）”，在下次被调度时应该得到补偿。
      • 如果vlag为一个大的负数，意味着se->vruntime远大于平均值。这说明该任务“超前”运行了太多时间，它是一个“超前者（over-runner）”，在下次调度时应该被延后。
    3. vlag的作用: se->vlag这个值主要被**Per-Entity Load Tracking (PELT)**算法所使用。PELT是内核用于计算任务和运行队列平均负载及利用率的机制。vlag作为PELT的一个输入，可以帮助算法更精 确地评估任务在遭受延迟或抢占时的真实负载贡献，从而影响负载均衡和CPU频率选择的决策。
    4. 限制（Clamping）: 由于avg_vruntime是一个近似的平均值，在任务加入/离开队列或权重改变时，它可能会跳变，导致计算出的vlag出现极端值。为了防止这种瞬时抖动对PELT算法造成过大影响，函数 会对计算出的vlag进行限制，将其“钳位（clamp）”在一个合理的范围内。这个范围由任务的时间片（slice）动态决定。
/*
 * lag_i = S - s_i = w_i * (V - v_i)
 *
 * 然而，由于V（系统虚拟时间）是通过所有实体的加权平均来近似的，
 * 有可能——通过向树中增加/移除/重加权实体——移动V的值，并最终
 * 得到一个比我们开始时更大的延迟（lag）。
 *
 * 将这个延迟限制在两倍时间片（slice）的长度，并设置一个TICK_NSEC的最小值，
 * 因为那是我们的计时粒度。
 *
 * EEVDF（最早最适虚拟截止时间优先算法）给出了一个稳态系统的如下限制：
 *
 *   -r_max < lag < max(r_max, q)
 *
 * XXX 或许可以增加max_slice到增强数据中来追踪这个值。
 */
/*
 * 这是一个静态函数，用于更新调度实体se的虚拟延迟(vlag)统计。
 * @cfs_rq: se所属的CFS运行队列。
 * @se:     需要更新延迟值的调度实体。
 */
static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/* @vlag: 64位有符号整型，用于存储计算出的原始虚拟延迟值。*/
	s64 vlag;
	/* @limit: 64位有符号整型，用于存储vlag的允许上限。*/
	s64 limit;

	/* 这是一个健壮性检查，确保我们只为在队列中的实体更新延迟值。如果se不在队列上，这是一个逻辑错误。*/
	WARN_ON_ONCE(!se->on_rq);

	/*
	 * 计算虚拟延迟vlag：
	 * vlag = 队列的平均vruntime - 实体自身的vruntime。
	 * avg_vruntime()函数返回cfs_rq的近似系统虚拟时间。
	 */
	vlag = avg_vruntime(cfs_rq) - se->vruntime;
	
	/*
	 * 计算vlag的限制值：
	 * 首先，取实体时间片的两倍(2*se->slice)和系统最小时间粒度(TICK_NSEC)中的较大者。
	 * 然后，调用calc_delta_fair，将这个物理时间转换为一个等效的虚拟时间增量，作为限制值。
	 */
	limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);

	/*
	 * 使用clamp()宏，将计算出的vlag值“钳位”在[-limit, +limit]这个闭区间内。
	 * 这可以防止因队列成员变动导致的vlag瞬时极端值，对PELT算法造成过度干扰。
	 * 最终结果存入se->vlag。
	 */
	se->vlag = clamp(vlag, -limit, limit);
}

__dequeue_entity 从CFS运行队列中移除一个调度实体（sched_entity）

/*
 * 这是一个静态函数，负责执行将调度实体se从cfs_rq的红黑树中
 * 物理移除的核心操作。它被上层的dequeue_entity()调用。
 * @cfs_rq: se所属的CFS运行队列。
 * @se:     将要被物理移除的调度实体。
 */
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/*
	 * 调用内核红黑树库的增强型、带缓存的节点删除函数。
	 * - &se->run_node: 指向要删除的红黑树节点。
	 * - &cfs_rq->tasks_timeline: 指向实体所在的红黑树。
	 * - &min_vruntime_cb: 指向一个回调函数。在红黑树因删除而进行旋转操作时，
	 *   此回调函数会被调用，以更新受影响节点的增强数据（主要是缓存的最小vruntime）。
	 *
	 * 这个函数会将se->run_node从红黑树中安全地摘下，并自动重新平衡树。
	 */
	rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
				  &min_vruntime_cb);
	
	/*
	 * 调用avg_vruntime_sub，从cfs_rq的平均虚拟运行时(avg_vruntime)的
	 * 计算中，减去被移除实体se的vruntime贡献。
	 * 这是为了在实体离开后，保持队列平均vruntime的准确性。
	 */
	avg_vruntime_sub(cfs_rq, se);
}

dequeue_entity 将单个调度实体（sched_entity）从其所属的CFS运行队列（cfs_rq）中移除

  • 在将一个实体从红黑树中摘下之前和之后，完成所有与该实体相关的、必要的统计数据更新和状态变更
/*
 * 这是一个静态函数，负责将单个调度实体se从其cfs_rq中移除。
 * @cfs_rq: se所属的CFS运行队列。
 * @se:     将要被移除的调度实体。
 * @flags:  一组标志，指示出队的具体原因。
 * 返回值: bool类型，如果出队被延迟，则返回false；否则返回true。
 */
static bool
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/* @sleep: 布尔标志，如果flags包含DEQUEUE_SLEEP，则为true，表示任务将要睡眠。*/
	bool sleep = flags & DEQUEUE_SLEEP;
	/* @action: 一个标志变量，用于传递给update_load_avg，初始为UPDATE_TG表示需要更新任务组。*/
	int action = UPDATE_TG;

	/* 调用update_curr，核算当前运行任务的vruntime，以确保cfs_rq的vruntime时钟是最新、最准确的。*/
	update_curr(cfs_rq);
	/* 清理与se相关的“伙伴调度”（一种调度优化）提示。*/
	clear_buddies(cfs_rq, se);

	/* 检查flags是否包含DEQUEUE_DELAYED，表示这是一个“延迟出队”的完成操作。*/
	if (flags & DEQUEUE_DELAYED) {
		/* 如果是，则确认se之前确实被标记为延迟了，否则是内核逻辑错误，触发一次性警告。*/
		WARN_ON_ONCE(!se->sched_delayed);
	} else {
		/* 如果不是延迟出队的完成操作，则考虑是否要启动一次延迟出队。*/
		/* @delay: 布尔标志，初始为任务是否要睡眠。*/
		bool delay = sleep;
		/*
		 * DELAY_DEQUEUE依赖于虚假唤醒。特殊任务状态不能遭受
		 * 虚假唤醒，将它们排除。
		 */
		/* 如果flags包含DEQUEUE_SPECIAL（表示这是一个特殊状态的任务），则禁止延迟出队。*/
		if (flags & DEQUEUE_SPECIAL)
			delay = false;

		/* 确认一个将被延迟的任务，当前没有被标记为延迟，否则是逻辑错误。*/
		WARN_ON_ONCE(delay && se->sched_delayed);

		/* 如果内核开启了DELAY_DEQUEUE特性，并且任务将要睡眠，并且它没有资格在近期被调度。*/
		if (sched_feat(DELAY_DEQUEUE) && delay &&
		    !entity_eligible(cfs_rq, se)) {
			/* 只更新负载，但不从红黑树移除。*/
			update_load_avg(cfs_rq, se, 0);
			/* 设置延迟标记，表示它逻辑上已出队，但物理上仍在树中。*/
			set_delayed(se);
			/* 返回false，通知上层调用者出队操作被推迟了。*/
			return false;
		}
	}

	/* 如果实体是一个正在被迁移到其他CPU的任务。*/
	if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
		/* 为action标志添加DO_DETACH，通知update_load_avg进行特殊处理。*/
		action |= DO_DETACH;

	/*
	 * 当一个sched_entity出队时，我们必须：
	 *   - 更新负载，使实体和cfs_rq都与当前时间同步。
	 *   - 对于group_entity，更新其runnable_weight以反映其组cfs_rq新的h_nr_runnable。
	 *   - 从cfs_rq->load.weight中减去它之前的权重。
	 *   - 对于group_entity，更新其权重以反映其组cfs_rq新的份额。
	 */
	/* 调用update_load_avg，更新实体和cfs_rq的平均负载（PELT）。*/
	// update_load_avg(cfs_rq, se, action);
	/* 调用se_update_runnable，更新实体自身的可运行状态统计。*/
	// se_update_runnable(se);

	/* 调用update_stats_dequeue_fair，更新其他与出队相关的统计数据（如等待时间）。*/
	// update_stats_dequeue_fair(cfs_rq, se, flags);

	/* 调用update_entity_lag，更新实体的PELT延迟（lag）统计。*/
	update_entity_lag(cfs_rq, se);
	/* 如果开启了PLACE_REL_DEADLINE特性，并且任务不是因为睡眠而出队。*/
	if (sched_feat(PLACE_REL_DEADLINE) && !sleep) {
		/* 则将其相对截止时间se->deadline转换为一个vruntime偏移量，并设置标志。*/
		se->deadline -= se->vruntime;
		se->rel_deadline = 1;
	}

	/* 如果se不是当前正在运行的实体。*/
	if (se != cfs_rq->curr)
		/* 则调用__dequeue_entity将其从红黑树中物理移除。*/
		__dequeue_entity(cfs_rq, se);
	/* 将se标记为不在队列上。*/
	se->on_rq = 0;
	/* 调用account_entity_dequeue，更新cfs_rq的总负载权重和nr_running计数。*/
	account_entity_dequeue(cfs_rq, se);

	/* 在最后一次出队时，归还超额的运行时。*/
	/* 这是一个用于cgroup带宽控制的函数，它会归还该cfs_rq剩余的运行时配额。*/
	// return_cfs_rq_runtime(cfs_rq);

	/* 如果se是一个代表cgroup的组实体，则调用update_cfs_group更新其父cgroup的状态。*/
	// update_cfs_group(se);

	/*
	 * 现在，如果@se是阻碍min_vruntime前进的那个实体，就推进min_vruntime。
	 * 但有一个例外：DEQUEUE_SAVE && !DEQUEUE_MOVE，在这种情况下，
	 * 我们会被立即放回队列，如果我们推进了min_vruntime，我们会被放回
	 * 一个比开始时更靠后的位置 —— 也就是说，我们会受到惩罚。
	 */
	/* 检查flags，确保这不是一个“保存并重新入队”的临时出队操作。*/
	if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) != DEQUEUE_SAVE)
		/* 如果是常规出队，则调用update_min_vruntime，检查并向前推进整个队列的vruntime基线。*/
		update_min_vruntime(cfs_rq);

	/* 如果这是一次延迟出队的完成步骤。*/
	if (flags & DEQUEUE_DELAYED)
		/* 调用finish_delayed_dequeue_entity完成最后的清理工作。*/
		finish_delayed_dequeue_entity(se);

	/* 如果cfs_rq因此次出队而变为空。*/
	// if (cfs_rq->nr_queued == 0)
	// 	/* 调用update_idle_cfs_rq_clock_pelt更新其空闲时钟的PELT统计。*/
	// 	update_idle_cfs_rq_clock_pelt(cfs_rq);

	/* 返回true，表示出队操作成功完成。*/
	return true;
}

dequeue_entities 执行跨越整个cgroup层级的、实际的“出队”操作

  • 从一个给定的调度实体（se）开始，沿着cgroup层级树向上，将该实体及其所有可运行的祖先实体，从它们各自所属的CFS运行队列（红黑树）中移除，并级联更新所有层级的统计数据
/*
 * 基本上是dequeue_task_fair()，但它可以处理dequeue_entity()中途失败
 * 的情况，并能在稍后恢复出队操作。
 *
 * 返回值:
 * -1 - 出队操作被延迟
 *  0 - 出队因为遇到被节流的cgroup而中止
 *  1 - 出队操作完全成功
 */
static int dequeue_entities(struct rq *rq, struct sched_entity *se, int flags)
{
	/* @was_sched_idle: 布尔标志，记录在操作开始前，整个运行队列rq是否为空闲状态。*/
	bool was_sched_idle = sched_idle_rq(rq);
	/* @rq_h_nr_queued: 整数，记录在操作开始前，根cfs_rq中已排队的层级任务数。*/
	int rq_h_nr_queued = rq->cfs.h_nr_queued;
	/* @task_sleep: 布尔标志，如果flags包含DEQUEUE_SLEEP，则为true，表示任务将要睡眠。*/
	bool task_sleep = flags & DEQUEUE_SLEEP;
	/* @task_delayed: 布尔标志，如果flags包含DEQUEUE_DELAYED，则为true，表示这是一次延迟出队。*/
	bool task_delayed = flags & DEQUEUE_DELAYED;
	/* @p: 指向task_struct的指针，如果se是一个真实任务的实体，则p指向该任务。*/
	struct task_struct *p = NULL;
	/* @h_nr_idle: 整数，用于在cgroup层级间传递和更新“有多少IDLE策略任务被移除”。*/
	int h_nr_idle = 0;
	/* @h_nr_queued: 整数，用于在cgroup层级间传递和更新“有多少排队任务被移除”。*/
	int h_nr_queued = 0;
	/* @h_nr_runnable: 整数，用于在cgroup层级间传递和更新“有多少可运行任务被移除”。*/
	int h_nr_runnable = 0;
	/* @cfs_rq: 指向当前正在处理的CFS运行队列的指针。*/
	struct cfs_rq *cfs_rq;
	/* @slice: 64位无符号整型，用于在cgroup层级间传递最小时间片信息。*/
	u64 slice = 0;

	/* 检查se是否是一个真实任务的实体。*/
	if (entity_is_task(se)) {
		/* 如果是，则p指向该任务。*/
		p = task_of(se);
		/* 初始化将要向上层传播的计数值。*/
		h_nr_queued = 1;
		h_nr_idle = task_has_idle_policy(p);
		/* 如果任务要睡眠、被延迟出队或它本身不是一个延迟实体，则它对可运行数的贡献为1。*/
		if (task_sleep || task_delayed || !se->sched_delayed)
			h_nr_runnable = 1;
	}

	/*
	 * 第一个循环：沿着cgroup层级向上，执行核心的出队操作。
	 */
	for_each_sched_entity(se) {
		/* 获取实体se所属的CFS运行队列cfs_rq。*/
		cfs_rq = cfs_rq_of(se);

		/* 尝试将实体se从cfs_rq中移除。如果dequeue_entity返回false，表示出队被延迟了。*/
		if (!dequeue_entity(cfs_rq, se, flags)) {
			/* 如果出队延迟发生在任务自身的实体上，则向上层返回-1。*/
			if (p && &p->se == se)
				return -1;

			/* 如果是组实体的出队被延迟，则记录下当前层的slice并中止遍历。*/
			slice = cfs_rq_min_slice(cfs_rq);
			break;
		}

		/* 如果出队成功，则从cfs_rq的层级计数中减去相应的值。*/
		cfs_rq->h_nr_runnable -= h_nr_runnable;
		cfs_rq->h_nr_queued -= h_nr_queued;
		cfs_rq->h_nr_idle -= h_nr_idle;

		/* 如果cfs_rq因此变为空闲，则它对上层的“空闲实体”贡献等于它内部的排队实体数。*/
		// if (cfs_rq_is_idle(cfs_rq))
			// h_nr_idle = h_nr_queued;

		/* 在遇到一个被节流的cfs_rq时，结束评估。*/
		// if (cfs_rq_throttled(cfs_rq))
			/* 返回0，表示出队因为遇到节流而中止。*/
			return 0;

		/* 如果父实体除了我们之外还有其他实体，就不要让父实体出队。*/
		if (cfs_rq->load.weight) {
			/* 记录当前层的slice。*/
			slice = cfs_rq_min_slice(cfs_rq);

			/* 避免为这个实体重新评估负载。*/
			se = parent_entity(se);
			/*
			 * 当p在其时间片内睡眠时，偏向于从这个cfs_rq中选择下一个任务。
			 */
			// if (task_sleep && se && !throttled_hierarchy(cfs_rq))
			// 	set_next_buddy(se);
			/* 中止向上的遍历。*/
			break;
		}
		/* 如果cfs_rq的权重为0，意味着这个cgroup空了，需要让其父实体也出队。*/
		/* 为下一轮循环设置flags，表示父实体是因为子实体睡眠而出队。*/
		flags |= DEQUEUE_SLEEP;
		/* 清除非必要的标志。*/
		flags &= ~(DEQUEUE_DELAYED | DEQUEUE_SPECIAL);
	}

	/*
	 * 第二个循环：沿着cgroup层级向上（从上一个循环中断的地方开始），更新负载等统计。
	 */
	for_each_sched_entity(se) {
		/* 获取实体se所属的CFS运行队列cfs_rq。*/
		cfs_rq = cfs_rq_of(se);

		/* 更新实体和cfs_rq的平均负载（PELT）。*/
		// update_load_avg(cfs_rq, se, UPDATE_TG);
		/* 更新实体的可运行状态统计。*/
		// se_update_runnable(se);
		/* 更新cfs_rq的组级别信息。*/
		// update_cfs_group(se);

		/* 确保时间片的正确性。*/
		se->slice = slice;
		/* 如果se不是当前运行的任务，传播min_vruntime的回调。*/
		if (se != cfs_rq->curr)
			min_vruntime_cb_propagate(&se->run_node, NULL);
		/* 获取当前cfs_rq的最小时间片，为上层做准备。*/
		slice = cfs_rq_min_slice(cfs_rq);

		cfs_rq->h_nr_runnable -= h_nr_runnable;
		cfs_rq->h_nr_queued -= h_nr_queued;
		cfs_rq->h_nr_idle -= h_nr_idle;

		/* 同样，更新向上传播的h_nr_idle标志。*/
		// if (cfs_rq_is_idle(cfs_rq))
			// h_nr_idle = h_nr_queued;

		/* 在遇到一个被节流的cfs_rq时，结束评估。*/
		// if (cfs_rq_throttled(cfs_rq))
			/* 返回0，表示出队因为遇到节流而中止。*/
			// return 0;
	}

	/* 从物理运行队列rq的总运行任务数中减去出队的任务数。*/
	sub_nr_running(rq, h_nr_queued);

	/* 如果根cfs_rq之前非空，但现在变为空，则停止相关的DL服务。*/
	if (rq_h_nr_queued && !rq->cfs.h_nr_queued)
		dl_server_stop(&rq->fair_server);

	/* 提前进行负载均衡，以拉取高优先级任务。*/
	/* 如果CPU因为这次出队而变为空闲，则立即设置下一次负载均衡的时间点为当前。*/
	if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
		rq->next_balance = jiffies;

	/* 如果这是一次延迟出队。*/
	if (p && task_delayed) {
		/* 确认任务此时不是睡眠状态，且仍在队列上，否则是逻辑错误。*/
		WARN_ON_ONCE(!task_sleep);
		WARN_ON_ONCE(p->on_rq != 1);

		/* 修复dequeue_task_fair()跳过的操作。*/
		hrtick_update(rq);

		/*
		 * 修复block_task()跳过的操作。
		 *
		 * 必须是最后一步，@p在此之后可能不再有效。
		 */
		/* 调用__block_task完成任务阻塞的最后状态转换。*/
		__block_task(rq, p);
	}

	/* 返回1，表示出队操作完全成功。*/
	return 1;
}

dequeue_task_fair 将一个指定的任务（p）及其相关的调度实体（se），从CFS的运行队列（红黑树）中正确地移除，并在此之前更新所有相关的调度统计数据

  • 当一个属于CFS调度的任务变为不可运行状态（例如，开始睡眠等待I/O，或者即将被迁移到另一个CPU）时，调度器核心就会调用此函数
/*
 * dequeue_task方法在nr_running减少之前被调用。
 * 我们从红黑树中移除任务，并更新公平调度的统计数据。
 */
/*
 * 这是一个静态函数，是fair_sched_class的dequeue_task方法的实现。
 * @rq:    指向任务p所在的运行队列。
 * @p:     指向即将被移出队列的任务。
 * @flags: 一组标志，指示出队的具体原因（如DEQUEUE_SLEEP表示任务要睡眠）。
 * 返回值: bool类型。如果出队被延迟，则返回false；否则返回true。
 */
static bool dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	/* 检查任务p的调度实体是否不处于“延迟调度”状态。*/
	// if (!p->se.sched_delayed)
		/* 如果不是，则调用util_est_dequeue，从根CFS队列(&rq->cfs)的
		 * 利用率估算统计中，原子地减去任务p的贡献。*/
		// util_est_dequeue(&rq->cfs, p);

	/*
	 * 调用util_est_update，根据任务是否将要进入睡眠状态（由DEQUEUE_SLEEP标志指示），
	 * 来更新其利用率估算的状态机。
	 */
	// util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP);
	
	/*
	 * 调用核心的辅助函数dequeue_entities来执行实际的、跨越cgroup层级的出队操作。
	 * 如果出队过程中，因为延迟调度（delayed dequeue）优化而导致操作被推迟，
	 * dequeue_entities会返回-1。
	 */
	if (dequeue_entities(rq, &p->se, flags) < 0)
		/* 如果出队被延迟，则向上层返回false。*/
		return false;

	/*
	 * 在调用dequeue_entities(DEQUEUE_DELAYED)之后，绝不能再引用@p。
	 * 这是一个非常重要的编程契约。在延迟出队并最终阻塞任务的路径上，
	 * 任务的task_struct可能会被并发地释放，因此再次访问p是不安全的。
	 */

	/*
	 * 调用hrtick_update，更新高精度调度时钟。因为队列中可运行的任务集合
	 * 发生了变化，下一个需要抢占的时刻可能也需要重新计算。
	 */
	// hrtick_update(rq);
	
	/* 返回true，表示出队操作（即使可能是逻辑上的）已成功启动或完成。*/
	return true;
}
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

一文搞懂！提示工程架构师多轮对话Agentic AI提示设计门道

在开始设计之前，我们需要先明确两个关键概念——Agentic AI和多轮对话的核心挑战。状态感知：能记住对话历史、用户信息、任务进度（比如“用户已经提供了订单号”）；意图推理：能从模糊输入中推导用户真实需求（比如“它啥时候到”中的“它”指之前提到的订单）；自主决策：能根据当前状态选择下一步动作（比如“用户没给订单号→追问”“订单号有效→查状态”）。简单来说，Agentic AI不是“被动回答问题的

avatar 2048 AI社区

价值投资中的垂直农业发展趋势

本部分旨在全面分析价值投资领域中垂直农业的发展趋势。通过深入研究垂直农业的技术原理、市场需求、商业模式等方面，为投资者提供有价值的参考，帮助他们评估垂直农业项目的投资潜力和风险。同时，也为垂直农业从业者、研究人员提供一个综合性的分析框架，促进该领域的技术创新和产业发展。范围涵盖垂直农业的各个环节，包括种植技术、环境控制、物流配送、市场营销等。背景介绍：阐述文章的目的、预期读者、文档结构和相关术语。

avatar 2048 AI社区
cover

从权威代理到智慧炼金术士：基于贾子智慧理论与鸽姆三非三共的AI重构路径研究

avatar 2048 AI社区