4.5.2 CFS —— 进程选择

公平的本质，是让时间在不同权重间流动时，依然保持其相对价值的守恒。

概要：本文详细介绍了 Linux CFS（完全公平调度器）中进程的加入、删除及选择的实现。通过分析关键函数 enqueue_entity、place_entity、__enqueue_entity、dequeue_entity、__dequeue_entity 和 __pick_next_entity，深入理解 CFS 如何维护进程调度的公平性，特别是在红黑树结构中的操作过程与调度策略。

1. 向树中加入进程

进程被唤醒或通过 fork() 创建时，会被加入调度器的红黑树中。

源码路径：kernel/sched_fair.c

1.1 enqueue_entity 函数

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/*
	 * Update the normalized vruntime before updating min_vruntime
	 * through callig update_curr().
	 */
	if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
		se->vruntime += cfs_rq->min_vruntime;

	/*
	 * Update run-time statistics of the 'current'.
	 */
	update_curr(cfs_rq);
	account_entity_enqueue(cfs_rq, se);

	if (flags & ENQUEUE_WAKEUP) {
		place_entity(cfs_rq, se, 0);
		enqueue_sleeper(cfs_rq, se);
	}

	update_stats_enqueue(cfs_rq, se);
	check_spread(cfs_rq, se);
	if (se != cfs_rq->curr)
		__enqueue_entity(cfs_rq, se);
}

说明：

• vruntime 调整：

  if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
  	se->vruntime += cfs_rq->min_vruntime;
  

  • 非唤醒/迁移入队时，要对 vruntime 进行补偿。
  • 原因：迁移或非唤醒实体可能保存的是相对于原队列的 vruntime 差值，需补偿当前队列的 min_vruntime 以维持公平性。
• 唤醒入队处理：

  if (flags & ENQUEUE_WAKEUP) {
      place_entity(cfs_rq, se, 0);
      enqueue_sleeper(cfs_rq, se);
  }
  

  • place_entity：根据调度策略设置 vruntime。
    • 新任务：延迟调度，避免抢占。
    • 唤醒任务：合理补偿休眠时间，但不过度优待。
• 插入红黑树：

  if (se != cfs_rq->curr)
      __enqueue_entity(cfs_rq, se);
  

  • 若 se 不是当前运行实体，调用 __enqueue_entity 将其插入红黑树。

---

1.2 place_entity 函数

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	u64 vruntime = cfs_rq->min_vruntime;

	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice(cfs_rq, se);

	if (!initial && sched_feat(FAIR_SLEEPERS)) {
		unsigned long thresh = sysctl_sched_latency;

		if (sched_feat(NORMALIZED_SLEEPER) && (!entity_is_task(se) ||
				 task_of(se)->policy != SCHED_IDLE))
			thresh = calc_delta_fair(thresh, se);

		if (sched_feat(GENTLE_FAIR_SLEEPERS))
			thresh >>= 1;

		vruntime -= thresh;
	}

	vruntime = max_vruntime(se->vruntime, vruntime);
	se->vruntime = vruntime;
}

说明：

• START_DEBIT 特性：
  • 对新任务设置初始 vruntime 加上一个额外延迟。
  • 防止新任务初始 vruntime 过小而立即抢占 CPU，导致老任务饥饿。
• FAIR_SLEEPERS 特性：
  • 对唤醒任务进行“睡眠补偿”：减小 vruntime，增加调度机会。
  • NORMALIZED_SLEEPER：根据权重调整补偿幅度。
  • GENTLE_FAIR_SLEEPERS：将补偿减半，防止补偿过度。

---

1.3 __enqueue_entity 函数

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	s64 key = entity_key(cfs_rq, se);
	int leftmost = 1;

	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_entity, run_node);
		if (key < entity_key(cfs_rq, entry)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = 0;
		}
	}

	if (leftmost)
		cfs_rq->rb_leftmost = &se->run_node;

	rb_link_node(&se->run_node, parent, link);
	rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

说明：

• 红黑树插入策略：
  • 根据 key 值（虚拟运行时间）决定插入位置。
  • key 小的放左边，大的放右边。
• rb_leftmost 缓存：
  • 指向红黑树中最左侧节点，即 vruntime 最小的实体。
  • 调度时直接使用这个字段，无需遍历红黑树。
• rb_link_node & rb_insert_color：
  • 将节点插入红黑树并调整平衡。

---

2. 从树中删除进程

2.1 dequeue_entity 函数

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
{
	update_curr(cfs_rq);

	update_stats_dequeue(cfs_rq, se);
	clear_buddies(cfs_rq, se);

	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);

	account_entity_dequeue(cfs_rq, se);
	update_min_vruntime(cfs_rq);

	if (!sleep)
		se->vruntime -= cfs_rq->min_vruntime;
}

说明：

• __dequeue_entity：实际删除操作。
• se->vruntime 调整：
  • 若不是因为睡眠而移除，则需要将 vruntime 还原为未补偿状态。

---

2.2 __dequeue_entity 函数

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if (cfs_rq->rb_leftmost == &se->run_node) {
		struct rb_node *next_node;

		next_node = rb_next(&se->run_node);
		cfs_rq->rb_leftmost = next_node;
	}

	rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

说明：

• 若当前删除的是最左节点（rb_leftmost），则更新为下一个最小节点。
• 使用 rb_erase 删除节点，并更新红黑树结构。

---

3. 挑选下一个任务

3.1 __pick_next_entity 函数

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
	struct rb_node *left = cfs_rq->rb_leftmost;

	if (!left)
		return NULL;

	return rb_entry(left, struct sched_entity, run_node);
}

说明：

• 直接返回红黑树中 vruntime 最小的实体。
• 利用 rb_leftmost 缓存实现 O(1) 级别的调度选择。