之前介绍了eevdf的patchset-v1的前3个补丁，现在继续深入解析patch 4-6的内容。这三笔提交引入了EEVDF调度器的核心算法：基于虚拟截止时间的任务选择机制。

# [PATCH 04/15] rbtree: Add rb_add_augmented_cached() helper

这笔提交虽然是一个辅助函数的添加，但为EEVDF调度器的核心算法奠定了基础。

## 问题背景

在EEVDF调度器中，我们需要维护一个**增强型红黑树（augmented RB-tree）**，这个树不仅要按虚拟运行时间（vruntime）排序，还要维护每个子树的最小截止时间（min_deadline）。这样我们才能高效地找到具有最早截止时间的可运行任务。

## 核心改动

添加了一个通用的辅助函数`rb_add_augmented_cached`，用于向增强型缓存红黑树中插入节点：

```c
static __always_inline struct rb_node *
rb_add_augmented_cached(struct rb_node *node, struct rb_root_cached *tree,
			bool (*less)(struct rb_node *, const struct rb_node *),
			const struct rb_augment_callbacks *augment)
{
	struct rb_node **link = &tree->rb_root.rb_node;
	struct rb_node *parent = NULL;
	bool leftmost = true;

	while (*link) {
		parent = *link;
		if (less(node, parent)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = false;
		}
	}

	rb_link_node(node, parent, link);
	augment->propagate(parent, NULL); /* suboptimal */
	rb_insert_augmented_cached(node, tree, leftmost, augment);

	return leftmost ? node : NULL;
}
```

## 关键点

1. **通用性**：这个函数是通用的，不仅用于调度器，也可用于其他需要增强型红黑树的场景
2. **子优化警告**：注释中提到`augment->propagate(parent, NULL)`是suboptimal的，因为理论上可以在向下遍历树时就更新增强数据，但当前的增强接口不支持这样做
3. **返回值**：返回插入的节点（如果是最左侧）或NULL

## 为什么需要这个函数？

在EEVDF中，每个任务实体（sched_entity）需要维护：
- `deadline`：虚拟截止时间
- `min_deadline`：以该节点为根的子树中的最小截止时间

当我们插入新任务时，需要确保从该节点到根节点路径上的所有节点的`min_deadline`都被正确更新。这个辅助函数简化了这个过程。

# [PATCH 05/15] sched/fair: Implement an EEVDF like policy

这笔提交是EEVDF调度器的核心实现，引入了基于**最早可运行虚拟截止时间优先（Earliest Eligible Virtual Deadline First）**的调度算法。

## 核心设计

### 1. 从WFQ到EEVDF

传统CFS是一个基于**加权公平队列（WFQ）**的调度器，只有单一的权重（weight）参数，映射到nice值。

EEVDF引入了**第二个参数**——延迟导向的参数，使得类似WF2Q或EEVDF的调度算法更适合：

> "Where CFS is currently a WFQ based scheduler with only a single knob, the weight. The addition of a second, latency oriented parameter, makes something like WF2Q or EEVDF based a much better fit."

### 2. EEVDF的两个参数

EEVDF有两个关键参数：

1. **weight（权重）**：时间斜率，与nice值的映射关系保持不变
2. **request size/slice length（请求大小/时间片长度）**：用于计算虚拟截止时间

虚拟截止时间的计算公式：
```
vd_i = ve_i + r_i / w_i
```

其中：
- `vd_i`：任务i的虚拟截止时间
- `ve_i`：任务i的虚拟运行时间
- `r_i`：请求大小（时间片）
- `w_i`：任务权重

### 3. 关键洞察

> "Basically, by setting a smaller slice, the deadline will be earlier and the task will be more eligible and ran earlier."

**更小的时间片意味着更早的截止时间**，任务会更早被调度，这提供了控制延迟的手段。

## 数据结构改动

### 新增字段

```c
struct sched_entity {
	struct load_weight		load;
	struct rb_node			run_node;
	u64				deadline;       // 新增：虚拟截止时间
	u64				min_deadline;   // 新增：子树最小截止时间

	// ... 现有字段 ...

	u64				vruntime;
	s64				vlag;
	u64				slice;          // 新增：时间片长度
};
```

## 关键实现

### 1. 任务入队（增强型红黑树）

```c
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	avg_vruntime_add(cfs_rq, se);
	se->min_deadline = se->deadline;  // 初始化最小截止时间为自己的截止时间
	rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
				__entity_less, &min_deadline_cb);
}
```

### 2. 更新最小截止时间

```c
static inline bool min_deadline_update(struct sched_entity *se, bool exit)
{
	u64 old_min_deadline = se->min_deadline;
	struct rb_node *node = &se->run_node;

	se->min_deadline = se->deadline;
	__update_min_deadline(se, node->rb_right);
	__update_min_deadline(se, node->rb_left);

	return se->min_deadline == old_min_deadline;
}

RB_DECLARE_CALLBACKS(static, min_deadline_cb, struct sched_entity,
		     run_node, min_deadline, min_deadline_update);
```

这个回调函数在树结构变化时自动更新每个节点的`min_deadline`，保证：
```
se->min_deadline = min(se->deadline, left->min_deadline, right->min_deadline)
```

### 3. EEVDF核心算法：pick_eevdf

```c
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
{
	struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
	struct sched_entity *curr = cfs_rq->curr;
	struct sched_entity *best = NULL;

	if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
		curr = NULL;

	while (node) {
		struct sched_entity *se = __node_2_se(node);

		// 如果这个实体不可运行，尝试左子树
		if (!entity_eligible(cfs_rq, se)) {
			node = node->rb_left;
			continue;
		}

		// 如果这个实体的截止时间比之前找到的更早，选择它
		// 如果它也是其子树中截止时间最早的，我们就找到了
		if (!best || deadline_gt(deadline, best, se)) {
			best = se;
			if (best->deadline == best->min_deadline)
				break;
		}

		// 如果这个子树中最早的截止时间在完全可运行的左半部分，
		// 去那里查找
		if (node->rb_left &&
		    __node_2_se(node->rb_left)->min_deadline == se->min_deadline) {
			node = node->rb_left;
			continue;
		}

		node = node->rb_right;
	}

	if (!best || (curr && deadline_gt(deadline, best, curr)))
		best = curr;

	if (unlikely(!best)) {
		struct sched_entity *left = __pick_first_entity(cfs_rq);
		if (left) {
			pr_err("EEVDF scheduling fail, picking leftmost\n");
			return left;
		}
	}

	return best;
}
```

#### 算法复杂度

通过增强型红黑树，这个算法可以在**O(log n)**时间复杂度内完成任务选择。

### 4. 任务资格判断：entity_eligible

```c
int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct sched_entity *curr = cfs_rq->curr;
	s64 avg = cfs_rq->avg_vruntime;
	long load = cfs_rq->avg_load;

	if (curr && curr->on_rq) {
		unsigned long weight = scale_load_down(curr->load.weight);

		avg += entity_key(cfs_rq, curr) * weight;
		load += weight;
	}

	return avg >= entity_key(cfs_rq, se) * load;
}
```

**资格条件**：任务必须被欠服务（lag >= 0）才可运行。

数学推导：
```
lag_i = S - s_i = w_i * (V - v_i)

lag_i >= 0  ->  V >= v_i

     ∑(v_i - v) * w_i
V = ------------------ + v
          ∑w_i

lag_i >= 0  ->  ∑(v_i - v) * w_i >= (v_i - v) * (∑w_i)
```

### 5. 更新截止时间：update_deadline

```c
static void update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if ((s64)(se->vruntime - se->deadline) < 0)
		return;

	if (sched_feat(EEVDF)) {
		// 对于EEVDF，虚拟时间斜率由w_i决定（即nice值）
		// 请求时间r_i由sysctl_sched_min_granularity决定
		se->slice = sysctl_sched_min_granularity;

		// 任务已消耗其请求，需要重新调度
		if (cfs_rq->nr_running > 1) {
			resched_curr(rq_of(cfs_rq));
			clear_buddies(cfs_rq, se);
		}
	} else {
		// CFS模式下的处理
		se->slice = min_t(u64, sched_slice(cfs_rq, se), sysctl_sched_latency);
	}

	// EEVDF: vd_i = ve_i + r_i / w_i
	se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
}
```

### 6. 任务选择：pick_next_entity

```c
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	struct sched_entity *left, *se;

	if (sched_feat(EEVDF)) {
		// 启用NEXT_BUDDY会影响延迟但不影响公平性
		if (sched_feat(NEXT_BUDDY) &&
		    cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next))
			return cfs_rq->next;

		return pick_eevdf(cfs_rq);
	}

	se = left = pick_cfs(cfs_rq, curr);

	// ... CFS的buddy处理逻辑 ...

	return se;
}
```

## 预抢占机制

### 1. Tick驱动的预抢占

由请求/时间片完成驱动：
```c
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	unsigned long delta_exec;
	// ...
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
	if (delta_exec > curr->slice) {
		resched_curr(rq_of(cfs_rq));
		// ...
	}
}
```

### 2. 唤醒预抢占

由截止时间驱动：
```c
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
	// ...
	if (sched_feat(EEVDF)) {
		if (pick_eevdf(cfs_rq) == pse)
			goto preempt;
		return;
	}
	// ...
}
```

## 调试输出增强

```c
SEQ_printf(m, "%15s %5d %9Ld.%06ld %c %9Ld.%06ld %9Ld.%06ld %9Ld.%06ld %9Ld %5d ",
	p->comm, task_pid_nr(p),
	SPLIT_NS(p->se.vruntime),
	entity_eligible(cfs_rq_of(&p->se), &p->se) ? 'E' : 'N',  // E/N标识是否可运行
	SPLIT_NS(p->se.deadline),                                  // 截止时间
	SPLIT_NS(p->se.slice),                                     // 时间片
	SPLIT_NS(p->se.sum_exec_runtime),
	(long long)(p->nvcsw + p->nivcsw),
	p->prio);
```

# [PATCH 06/15] sched: Commit to lag based placement

这笔提交删除了旧的`FAIR_SLEEPERS`机制，完全采用新的基于lag的放置策略。

## 背景

`FAIR_SLEEPERS`是一个非常粗略的近似方案，用来弥补缺乏基于lag的放置机制的问题，特别是"欠服务（service owed）"部分。这对于`starve`和`hackbench`这类测试很重要。

## 问题

`FAIR_SLEEPERS`导致了某种程度的不公平：
- 对于一个睡眠50%时间的任务和一个100%运行的任务
- 按照`FAIR_SLEEPERS`会产生50%/50%的时间分配
- 但严格来说应该是33%/67%的分配（CFS在睡眠时间超过阈值时也会这样处理）

## 核心改动

### 1. 删除FAIR_SLEEPERS相关代码

```c
// 删除了整个FAIR_SLEEPERS逻辑块
if (sched_feat(FAIR_SLEEPERS)) {
	// ... 40+行代码被删除 ...
}
```

### 2. 简化place_entity

```c
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	u64 vslice = calc_delta_fair(se->slice, se);
	u64 vruntime = avg_vruntime(cfs_rq);
	s64 lag = 0;

	/*
	 * Due to how V is constructed as the weighted average of entities,
	 * adding tasks with positive lag, or removing tasks with negative lag
	 * will move 'time' backwards, this can screw around with the lag of
	 * other tasks.
	 *
	 * EEVDF: placement strategy #1 / #2
	 */
	if (sched_feat(PLACE_LAG) && cfs_rq->nr_running > 1) {
		lag = se->vlag;

		/*
		 * Compensate for the effect of adding this entity on
		 * the weighted average.
		 */
		load = cfs_rq->avg_load;
		if (curr && curr->on_rq)
			load += scale_load_down(curr->load.weight);

		lag *= load + scale_load_down(se->load.weight);
		if (WARN_ON_ONCE(!load))
			load = 1;
		lag = div_s64(lag, load);
	}

	vruntime -= lag;

	// 新任务加入竞争时的特殊处理
	if (sched_feat(PLACE_DEADLINE_INITIAL) && initial)
		vslice /= 2;

	// EEVDF: vd_i = ve_i + r_i/w_i
	se->vruntime = vruntime;
	se->deadline = vruntime + vslice;
}
```

### 3. 新增调度特性

在`kernel/sched/features.h`中新增：

```c
SCHED_FEAT(PLACE_DEADLINE_INITIAL, true)

// ...

SCHED_FEAT(EEVDF, true)
```

## 关键改进

1. **删除了`entity_is_long_sleeper`函数**：不再需要特殊处理长睡眠任务
2. **简化了放置逻辑**：直接使用lag进行放置，不再需要复杂的睡眠时间阈值判断
3. **统一了新任务初始化**：新任务的slice默认为`sysctl_sched_min_granularity`

## 优势

- **更精确的公平性**：基于lag的放置策略提供了更精确的欠服务计算
- **更简单的代码**：删除了40+行复杂逻辑
- **更好的可维护性**：单一的放置策略替代了多个特性的组合

# 总结

本文介绍了如下
* 增强型红黑树的基础实现
* 基于最早可运行虚拟截止时间的任务选择
* 删除了旧的公平睡眠者机制，完全采用基于lag的放置策略

# 参考
> https://lore.kernel.org/lkml/20230531124603.862983648@infradead.org/
> https://lore.kernel.org/lkml/20230531124603.931005524@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.000198861@infradead.org/


调度(19)-EEVDF补丁解析3

之前介绍了eevdf的patchset-v1，现在继续介绍

# [PATCH 02/15] sched/fair: Remove START_DEBIT
引入 avg_vruntime() 就不需要使用更差的了近似值。以0滞后点为插入起点新任务。

在cfs中，为了解决任务fork时cfs的min_vruntime过小导致其他任务starvation，所以提供了一个cfs的转述feature：START_DEBIT，在eevdf中se->vruntime不再是原cfs的min_vruntime了，所以这个feature天然消失，消失就删掉

```
@@ -906,16 +906,6 @@ static u64 sched_slice(struct cfs_rq *cf
 	return slice;
 }
 
-/*
- * We calculate the vruntime slice of a to-be-inserted task.
- *
- * vs = s/w
- */
-static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
-{
-	return calc_delta_fair(sched_slice(cfs_rq, se), se);
-}
-
 #include "pelt.h"
 #ifdef CONFIG_SMP
 
@@ -4862,16 +4852,7 @@ static inline bool entity_is_long_sleepe
 static void
 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
 {
-	u64 vruntime = cfs_rq->min_vruntime;
-
-	/*
-	 * The 'current' period is already promised to the current tasks,
-	 * however the extra weight of the new task will slow them down a
-	 * little, place the new task so that it fits in the slot that
-	 * stays open at the end.
-	 */
-	if (initial && sched_feat(START_DEBIT))
-		vruntime += sched_vslice(cfs_rq, se);
+	u64 vruntime = avg_vruntime(cfs_rq);

```
可以看到，eevdf的vruntime是获取了avg_vruntime，avg_vruntime的计算上一篇介绍过了。
# [PATCH 03/15] sched/fair: Add lag based placement
这笔提交给se添加了lag概念
```
@@ -555,8 +555,9 @@ struct sched_entity {
 
 	u64				exec_start;
 	u64				sum_exec_runtime;
-	u64				vruntime;
 	u64				prev_sum_exec_runtime;
+	u64				vruntime;
+	s64				vlag;
 
 	u64				nr_migrations;
```
reweight的时候，lag需要重新计算，
```
@@ -3492,6 +3501,8 @@ dequeue_load_avg(struct cfs_rq *cfs_rq,
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight)
 {
+	unsigned long old_weight = se->load.weight;
+
 	if (se->on_rq) {
 		/* commit outstanding execution time */
 		if (cfs_rq->curr == se)
@@ -3504,6 +3515,14 @@ static void reweight_entity(struct cfs_r
 
 	update_load_set(&se->load, weight);
 
+	if (!se->on_rq) {
+		/*
+		 * Because we keep se->vlag = V - v_i, while: lag_i = w_i*(V - v_i),
+		 * we need to scale se->vlag when w_i changes.
+		 */
+		se->vlag = div_s64(se->vlag * old_weight, weight);
+	}
+
```
这里`vlag = lag_i / w_i`，所以reweight的时候，vlag需要更新。

我们在更新lag的时候，之前提到的公式是S-s，所以如下
```
/*
 * lag_i = S - s_i = w_i * (V - v_i)
 */
void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	SCHED_WARN_ON(!se->on_rq);
	se->vlag = avg_vruntime(cfs_rq) - se->vruntime;
}
```
因为lag是 `w_i * (V - v_i)`，而vlag是`vlag = lag_i / w_i`，所以计算vlag就是直接 `V-v_i`

更新lag的实际是dequeue的时候，所以如下
```
@@ -5066,6 +5155,9 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 
 	clear_buddies(cfs_rq, se);
 
+	if (flags & DEQUEUE_SLEEP)
+		update_entity_lag(cfs_rq, se);
+
 	if (se != cfs_rq->curr)
 		__dequeue_entity(cfs_rq, se);
 	se->on_rq = 0;
```
eevdf在client requeue的时候有三个策略，所以place_entity实现这些策略，这里只实现了策略1和策略2，我们先看看代码
```
 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
 {
 	u64 vruntime = avg_vruntime(cfs_rq);
+	s64 lag = 0;
 
-	/* sleeps up to a single latency don't count. */
-	if (!initial) {
-		unsigned long thresh;
+	/*
+	 * Due to how V is constructed as the weighted average of entities,
+	 * adding tasks with positive lag, or removing tasks with negative lag
+	 * will move 'time' backwards, this can screw around with the lag of
+	 * other tasks.
+	 *
+	 * EEVDF: placement strategy #1 / #2
+	 */
+	if (sched_feat(PLACE_LAG) && cfs_rq->nr_running > 1) {
```
## 策略1
client 的场景: 

client 离开
$$
V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i}
$$

client 加入
$$
V(t) = V(t) - \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i}
$$

client reweight
$$
V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i - w_j}  + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i + w_j^{'}}
$$
来更新  
## 策略2
和策略1一致，但是client reweight不做任何操作，也就是
$$
V(t) = V(t)
$$


我们看一下代码
```
 		/*
		 * If we want to place a task and preserve lag, we have to
		 * consider the effect of the new entity on the weighted
		 * average and compensate for this, otherwise lag can quickly
		 * evaporate.
		 *
		 * Lag is defined as:
		 *
		 *   lag_i = S - s_i = w_i * (V - v_i)
		 *
		 * To avoid the 'w_i' term all over the place, we only track
		 * the virtual lag:
		 *
		 *   vl_i = V - v_i <=> v_i = V - vl_i
		 *
		 * And we take V to be the weighted average of all v:
		 *
		 *   V = (\Sum w_j*v_j) / W
		 *
		 * Where W is: \Sum w_j
		 *
		 * Then, the weighted average after adding an entity with lag
		 * vl_i is given by:
		 *
		 *   V' = (\Sum w_j*v_j + w_i*v_i) / (W + w_i)
		 *      = (W*V + w_i*(V - vl_i)) / (W + w_i)
		 *      = (W*V + w_i*V - w_i*vl_i) / (W + w_i)
		 *      = (V*(W + w_i) - w_i*l) / (W + w_i)
		 *      = V - w_i*vl_i / (W + w_i)
		 *
		 * And the actual lag after adding an entity with vl_i is:
		 *
		 *   vl'_i = V' - v_i
		 *         = V - w_i*vl_i / (W + w_i) - (V - vl_i)
		 *         = vl_i - w_i*vl_i / (W + w_i)
		 *
		 * Which is strictly less than vl_i. So in order to preserve lag
		 * we should inflate the lag before placement such that the
		 * effective lag after placement comes out right.
		 *
		 * As such, invert the above relation for vl'_i to get the vl_i
		 * we need to use such that the lag after placement is the lag
		 * we computed before dequeue.
		 *
		 *   vl'_i = vl_i - w_i*vl_i / (W + w_i)
		 *         = ((W + w_i)*vl_i - w_i*vl_i) / (W + w_i)
		 *
		 *   (W + w_i)*vl'_i = (W + w_i)*vl_i - w_i*vl_i
		 *                   = W*vl_i
		 *
		 *   vl_i = (W + w_i)*vl'_i / W
 		 */
		load = cfs_rq->avg_load;
		if (curr && curr->on_rq)
			load += curr->load.weight;

		lag *= load + se->load.weight;
		if (WARN_ON_ONCE(!load))
			load = 1;
		lag = div_s64(lag, load);

		vruntime -= lag;
 	}

```
假设V为任务i加入前的virtual time，那么V此时的公式为
$$
V = \frac{\sum_j w_j*v_j}{W} W = \sum_j w_j
$$

此时任务i加入了，那么我们要计算的新的V应该是
$$
V(t) = V(t) - \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i}
$$
而lag是
```
lag_i = S - s_i = w_i * (V - v_i)
```
所以新的V公式为
$$
V' = (\sum_j w_j*v_j + w_i*v_i) / (W + w_i) \\
		 = (W*V + w_i*(V - vl_i)) / (W + w_i) \\
		 = (W*V + w_i*V - w_i*vl_i) / (W + w_i) \\
		 = (V*(W + w_i) - w_i*l) / (W + w_i) \\
		 = V - w_i*vl_i / (W + w_i)
$$
这样可以计算i加入后的lag v_i，如下
```
vl'_i = V' - v_i \\
	  = V - w_i*vl_i / (W + w_i) - (V - vl_i) \\
      = vl_i - w_i*vl_i / (W + w_i)
```
两边乘以`W + w_i`

$$
(W + w_i) vl'_i = (W + w_i) vl_i - w_i*vl_i (W + w_i) vl'_i = W * vl_i vl_i = \frac{(W + w_i) vl'_i}{W}
$$

这样求出来就是lag值，
又因为 
$$
v_i = V - vl_i
$$

所以可以通过`vruntime -= lag`求出vruntime值

# 总结
这笔patch突出了lag的计算，我们需要反复的结合论文的公式和内核注释来进行分析，论文中提到了策略1和策略2，而内核默认是策略2，也可以通过feature启用策略1。

# 参考
> https://lore.kernel.org/lkml/20230531124603.722361178@infradead.org/
> https://lore.kernel.org/lkml/20230531124603.794929315@infradead.org/


调度(18)-EEVDF补丁解析2

现在基于EEVDF的社区patch进行逐一解析，尽可能抓住重点来介绍eevdf

# [PATCH 01/15] 
添加两个参数avg_vruntime 和 avg_load
```
@@ -554,6 +554,9 @@ struct cfs_rq {
 	unsigned int		idle_nr_running;   /* SCHED_IDLE */
 	unsigned int		idle_h_nr_running; /* SCHED_IDLE */
 
+	s64			avg_vruntime;
+	u64			avg_load;
+
 	u64			exec_clock;
 	u64			min_vruntime;
```
核心说明
```
/*
 * Compute virtual time from the per-task service numbers:
 *
 * Fair schedulers conserve lag:
 *
+ *   \Sum lag_i = 0
 *
 * Where lag_i is given by:
 *
 *   lag_i = S - s_i = w_i * (V - v_i)
 *
 * Where S is the ideal service time and V is it's virtual time counterpart.
 */
```
这个注释很容易理解，上篇论文提过，lag为S-s，因为引入了V，所以是w * (v-vi)，然后我们要满足sum(lag)=0，所以可以转换公式如下
```
 /* Therefore:
 *
 *   \Sum lag_i = 0
 *   \Sum w_i * (V - v_i) = 0
 *   \Sum w_i * V - w_i * v_i = 0
 *
 * From which we can solve an expression for V in v_i (which we have in
 * se->vruntime):
 *
 *       \Sum v_i * w_i   \Sum v_i * w_i
 *   V = -------------- = --------------
 *          \Sum w_i            W
 *
 * Specifically, this is the weighted average of all entity virtual runtimes.
 */
```
因为sum(lag)=0，所以得到v的公式是
$$
V = \frac{\sum_i w_i * v_i}{\sum_i w_i} = \frac{\sum_i w_i * v_i}{W}
$$
```
 /*
  * [[ NOTE: this is only equal to the ideal scheduler under the condition
  *          that join/leave operations happen at lag_i = 0, otherwise the
  *          virtual time has non-continguous motion equivalent to:
  *
  *	      V +-= lag_i / W
  *
  *	    Also see the comment in place_entity() that deals with this. ]]
  *
  * However, since v_i is u64, and the multiplcation could easily overflow
  * transform it into a relative form that uses smaller quantities:
  *
  * Substitute: v_i == (v_i - v0) + v0
  *
  *     \Sum ((v_i - v0) + v0) * w_i   \Sum (v_i - v0) * w_i
  * V = ---------------------------- = --------------------- + v0
  *                  W                            W
  *
  * Which we track using:
  *
  *                    v0 := cfs_rq->min_vruntime
  * \Sum (v_i - v0) * w_i := cfs_rq->avg_vruntime
  *              \Sum w_i := cfs_rq->avg_load
  *
  * Since min_vruntime is a monotonic increasing variable that closely tracks
  * the per-task service, these deltas: (v_i - v), will be in the order of the
  * maximal (virtual) lag induced in the system due to quantisation.
  *
  * Also, we use scale_load_down() to reduce the size.
  *
  * As measured, the max (key * weight) value was ~44 bits for a kernel build.
  */
```
为了避免u64的overflow，所以引用一个替代`v_i == (v_i - v0) + v0`，代入原公式如下
$$
V = \frac{\sum_i w_i * v_i}{W} = \frac{\sum_i w_i * (v_i - v0) + \sum_i w_i * v0}{W} = \frac{\sum_i w_i * (v_i - v0)}{W} + v0
$$
这里将公式对接到代码上
```
 v0                  = cfs_rq->min_vruntime
 sum(v_i - v0) * w_i = cfs_rq->avg_vruntime
 sum(w_i)            = cfs_rq->avg_load
```
对于`v_i - v0`的函数如下
```
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return (s64)(se->vruntime - cfs_rq->min_vruntime);
}
```
那么`cfs_rq->avg_vruntime`和`cfs_rq->avg_load`的计算函数就是
```
static void
avg_vruntime_add(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;
}

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;
}
```
随着时间的推移，min_vruntime会不断更新，所以函数如下
```
static u64 __update_min_vruntime(struct cfs_rq *cfs_rq, u64 vruntime)
{
	u64 min_vruntime = cfs_rq->min_vruntime;
	/*
	 * open coded max_vruntime() to allow updating avg_vruntime
	 */
	s64 delta = (s64)(vruntime - min_vruntime);
	if (delta > 0) {
		avg_vruntime_update(cfs_rq, delta);
		min_vruntime = vruntime;
	}
	return min_vruntime;
}
```
同样的avg_vruntime 也会随着时间更新，所以函数如下
```
static inline
void avg_vruntime_update(struct cfs_rq *cfs_rq, s64 delta)
{
	/*
	 * v' = v + d ==> avg_vruntime' = avg_runtime - d*avg_load
	 */
	cfs_rq->avg_vruntime -= cfs_rq->avg_load * delta;
}
```
还记得计算V的公式吗，如下
$$
V = \frac{\sum_i w_i * (v_i - v0)}{W} + v0 = 
$$
其实就是
```
V = cfs_rq->avg_vruntime / cfs_rq->avg_load + cfs_rq->min_vruntime
```
所以对于V的函数实现如下
```
u64 avg_vruntime(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	s64 avg = cfs_rq->avg_vruntime;
	long load = cfs_rq->avg_load;

	if (curr && curr->on_rq) {
		unsigned long weight = scale_load_down(curr->load.weight);

		avg += entity_key(cfs_rq, curr) * weight;
		load += weight;
	}

	if (load)
		avg = div_s64(avg, load);

	return cfs_rq->min_vruntime + avg;
}
```
和之前的CFS的计算vruntime一致，我们要在enqueue和dequeue的时候主动update_curr，这里直接调用add/sub来更新V，如下
```
@@ -642,12 +767,14 @@ static inline bool __entity_less(struct
  */
 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	avg_vruntime_add(cfs_rq, se);
 	rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
 }
 
 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
+	avg_vruntime_sub(cfs_rq, se);
 }
 
 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
@@ -3379,6 +3506,8 @@ static void reweight_entity(struct cfs_r
 		/* commit outstanding execution time */
 		if (cfs_rq->curr == se)
 			update_curr(cfs_rq);
+		else
+			avg_vruntime_sub(cfs_rq, se);
 		update_load_sub(&cfs_rq->load, se->load.weight);
 	}
 	dequeue_load_avg(cfs_rq, se);
@@ -3394,9 +3523,11 @@ static void reweight_entity(struct cfs_r
 #endif
 
 	enqueue_load_avg(cfs_rq, se);
-	if (se->on_rq)
+	if (se->on_rq) {
 		update_load_add(&cfs_rq->load, se->load.weight);
-
+		if (cfs_rq->curr != se)
+			avg_vruntime_add(cfs_rq, se);
+	}
 }

```
# 总结
这里介绍了eevdf的第一个patch，其作用是添加了avg_vruntime和avg_load，并结合论文提供了v的计算函数

# 参考
> https://lore.kernel.org/lkml/20230531115839.089944915@infradead.org/
> https://lore.kernel.org/lkml/20230531124603.654144274@infradead.org/

调度(17)-EEVDF补丁解析1

这篇论文是 EEVDF 算法的理论基石，Linux 6.6+ 内核的 EEVDF 实现基本就是基于它来的。
本文根据论文描述的内容进行介绍

# EEVDF的提出
现代操作系统的调度器类型分为两类
* 比例份额
* 实时调度

很明显，这种归类下，可以得出如下结论
1. 步幅调度，CFS调度这类，属于比例份额，它要做到的事公平的让程序分配到应有的份额
2. FIFO，EDF这类，属于实时调度，这类调度器基于事件驱动模型，例如EDF通过截止事件来决定任务的优先级

```
In this paper we propose a new scheduler (called Earliest Eligible Virtual Deadline First (EEVDF)which, while retaining all the advantages of the proportional share schedulers, provides strong timeliness guarantees for the service time received by a client. In this way, our algorithm provides a unied approach for scheduling continuous media, interactive and batch applications.
```

而EEVDF要解决的问题是保留了比例份额的优势的前提上，融合实时调度通过截止时间来保证及时性。这样的情况下，调度器在多媒体和交互式以及批处理三类型的任务上都能够统一的使用一种调度策略满足其需求

# 服务滞后
我们按照比例份额来计算一个任务的应有份额，那么其计算应该如下

![image.png](/static/img/f747a0e12981aad95c3fb19748ba8ee5.image.webp)

很好理解，就是自身权重占总权重的比值

但实际调度的过程中，我们不可能简单的任务一个任务的应该开始运行时间和实际开始运行时间一致，那么我们把这两个值相减，提供一个新的概念叫做lag。

![image.png](/static/img/8812388516f9b471d8bd2bc22603114e.image.webp)

这里Si就是理论认为的运行时间，而si是实际获得的运行时间，将`Si-si`就是我们称作的lag。

在上一文中我们介绍了一个linux很好的通俗化含义，就是欠条。那么这个lag就很好理解了。

我调度器按照比例分给你任务，但是等你真的运行的时候，肯定存在滞后，那么这个滞后时间是你欠我的，我要找你要回来。

# EEVDF Algorithm
虚拟时间的定义

![image.png](/static/img/7f1f6e800a84755ba1e69d00bdb87b55.image.webp)

直观的看

* 当竞争激烈（总权重很大）时，虚拟时间走得慢。
* 当竞争减少（总权重变小）时，虚拟时间走得快。

如果虚拟时间的概念引入了，那么我们计算`Si-si`就可以简单的认为是两个时间点的虚拟时间相减乘以权重

![image.png](/static/img/2b4440c58611974cc7743ff039e26dc6.image.webp)

现在为了计算虚拟时间，再关联两个新的时间
* Ve： virtual eligible time，合格时间，所谓合格，就是应获得的时间等于其在发出请求前已获得的服务时间。我们称作合格，那么合格时间就是，不合格时间到合格时间的这个差值。如果lag是负数，那么它已经不合格了，我们等到它再次合格的时间，就是Ve
* Vd： virtual deadline， 截止时间，这个不用解释了

我们看Ve的计算

![image.png](/static/img/697e9239c9a37e34d4d4350fbf5e2cc5.image.webp)

就是 `T0的虚拟数据V + 实际运行实际si / 权重`

这里我们看si的值，如果si已经开始运行了，那么Ve是合格的，这是没问题的   
如果si是负数，那么Ve是不合格的，我们得让Vt继续推进，使得Ve合格

再看Vd的计算

![image.png](/static/img/80536205884e6a391354889a0fffbc89.image.webp)

就是 `合格时间Ve + 申请的runtime / 权重`

# 示例

![image.png](/static/img/06945ff95bce583c0d71396d958542da.image.webp)

这里假设有两个client，他们的权重都是2，对于的r分别是r1=2，r2=1，时间的粒度是1。那么分析如下
* t=0： 只有client1，Ve1=0，Vd1=Ve+r1/w1=0+2/2=1
* t=1： V1=1/2=0.5
* t=1： Ve2=V1=0.5，Vd2=Ve2+1/2=1，此时我们看到Vd1和Vd2都是1，下一次其实可以任意挑选client1和client2
* t=2： client2的Ve2=Vd1=1，Vd2=Ve2+1/2=1.5，此时Ve2是1，但是V1是0.5，优先级降低，让client1运行
* t=3： client1完成，Ve1=Vd1=1，Vd1=Ve1+2/2=2，由于client 2 的dl比client1要早，1.5<2，所以运行clietn2

以此类推

# 公平性分析
在实际场景中，公平性在EEVDF是通过lag来衡量vt的计算，如下

![image.png](/static/img/20dac4065d1447a75f63a976e7937e12.image.webp)

假设三个client在t0没有lag，此时client3在t时刻离开，那么计算lag的方法为

$$
lag_i(t) = S_i(t_0,t) - s_i(t_0, t) \\
  = \int_{t_0}^{t_1}f_i(\tau)d\tau - s_i(t_0, t) \\
  = w_i \frac{t - t_0}{w_1 + w_2 + w_3} - s_i(t_0, t) -- (1)
$$

eevdf设计没有所谓的resource idle，则在t0时间中，client1和client2获得的时间为
$$
t - t_0 - s_3(t_0, t)
$$
那么对于client1和client2，其计算为
$$
S_i(t_0, t^+) = (t - t_0 - s_3(t_0, t)) \frac{w_i}{w_1 + w_2} -- (2)
$$
根据前面的公式代入
$$
lag_3(t) = w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - s_3(t_0, t) \\
s_3(t_0, t) =  w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - lag_3(t) -- (3)
$$
再将3代入2
$$
S_i(t_0, t^+) = (t - t_0 - ( w_3 \frac{t - t_0}{w_1 + w_2 + w_3} - lag_3(t))) \frac{w_i}{w_1 + w_2} \\
= (t - t_0 + \frac{-w_3t + w_3 t_0}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\
= (\frac{w_1 + w_2t - w_1t_0 - w_2t_0}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\
= (\frac{(w_1 + w_2)(t - t_0)}{w_1 + w_2 + w_3}) * \frac{w_i}{w_1 + w_2} + w_i\frac{lag_3(t)}{w1 + w2} \\
= (\frac{(t - t_0)}{w_1 + w_2 + w_3}) * w_i + w_i\frac{lag_3(t)}{w1 + w2} \\
= w_i(V(t) - V(t_0)) + w_i\frac{lag_3(t)}{w1 + w2}
$$
我们可以看到client3离开时，client1和2分摊了client3的lag

所以当一个client离开，那么其Vt的计算为

$$
V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i} -- (4)
$$

同理，当一个client加入，其Vt计算为

$$
V(t) = V(t) - \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i} -- (5)
$$

那么reweight的时候，其Vt计算为

$$
V(t) = V(t) + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i - w_j}  + \frac{lag_j(t)}{\sum_{i\in{A(t^+)}}w_i + w_j^{'}} -- (6)
$$

所以我们可以认为EEVDF是work-conserving最优的

# 总结
本论文是eevdf的开篇基石，里面详细论证了EEVDF的优势，了解这个论文的熟悉linux eevdf来说至关重要。为了理解这个论文，我重新啃了一些里面的公式，计算过程在上文中。


# 参考
> https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564



调度(16)-EEVDF论文

EEVDF（Earliest Eligible Virtual Deadline First）为了解决上文中CFS的无法低延时的痛点而诞生的。它在保持 CFS 公平性的基础上，引入了“虚拟截止期限”和“lag”概念，让调度器既能公平分配资源，又能显著降低延迟。
本文就来详细拆解 EEVDF 的核心思路，以及它如何通过 latency-nice 值优雅平衡吞吐与响应。

# Lag
所谓lag，我们可以简单理解为欠条，谁欠得最多（lag 正值最大）谁最先玩

假设 5 个进程共享一个 CPU，nice 值相同。
理想情况下，每秒每个进程应该得到 200ms CPU 时间。  但实际运行中，由于中断、抢占、迁移等原因，每个进程得到的真实时间会有偏差。
EEVDF 把这个偏差定义为 lag：
```
lag = 理想时间 - 实际获得时间
```
1. lag > 0：进程“欠债”了，得到的 CPU 时间比应得的少 → 应该优先调度  
2. lag < 0：进程“超支”了，得到的 CPU 时间比应得的多 → 应该降低优先级  
3. lag = 0：正好公平

只有 lag ≥ 0 的进程才“eligible”（有资格被调度）。
lag < 0 的进程要等到时间继续前进、它的“应得时间”赶上“已得时间”后，才重新 eligible。这段时间差叫 eligible time。简单来说：EEVDF 通过 lag 实时追踪每个进程的“公平欠账”，让“欠得最多”的进程最先上场。

# Virtual deadline
这个很好理解，EDF调度通过实际deadline来判断截止时间，EEVDF通过虚拟截止时间来判断，EEVDF挑选 virtual deadline 最早的进程。

virtual deadline 的计算公式：
```
virtual deadline = eligible time + time slice
```
* eligible time：进程从不 eligible 到重新 eligible 所需的时间（基于 lag 追赶）
* time slice：本次分配的时间片（类似 CFS 的 sched_slice）  

这里time slice的关键在于latency-nice的影响，主要如下：
1. latency-nice 低（延迟敏感）：time slice 短 → virtual deadline 早 → 优先级高  
2. latency-nice 高（延迟不敏感）：time slice 长 → virtual deadline 晚 → 优先级低

如下图

![image.png](/static/img/597bb8640056d3e3fbefbad7401dd035.image.webp)

两个程序A和B，我们留意到A是属于latency-nice 低，time slice 短的程序，B就是latency-nice 高，time slice 长的程序，他们调度的特性就是，让延迟敏感的程序优先运行，但是切的更短。而实际上，A和B的运行时间是一致的。

这种将延迟敏感任务分成很多小片段，频繁调度的办法，换来的低延迟，而对延迟不敏感的任务，分成长片段，换来的是高吞吐，所以这完美解决了 CFS 的痛点：nice 值只管“总量”，latency-nice 可以管“响应速度”。

回到virtual deadline 的概念，我们如果latency-nice 低，那么virtual deadline低，这样也就越低延迟

在EEVDF中，可以通过sched_runtime设置一个自定义的time slice，这样用户的可操作性更强。但是需要注意关键点
* time slice小，抢占多，低延迟
* time slice大，吞吐高，延迟高

如果设置这个值，其范围是
```
0.1ms - 100ms
```
当然，如果不设置这个值，就是内核默认的经验值，和cfs的sysctl_sched_min_granularity一致，为sysctl_sched_base_slice。

其默认值为
* 0.70 msec * (1 + ilog(ncpus))

```
unsigned int sysctl_sched_base_slice            = 700000ULL;
/*
 * Increase the granularity value when there are more CPUs,
 * because with more CPUs the 'effective latency' as visible
 * to users decreases. But the relationship is not linear,
 * so pick a second-best guess by going with the log2 of the
 * number of CPUs.
 *
 * This idea comes from the SD scheduler of Con Kolivas:
 */
static unsigned int get_update_sysctl_factor(void)
{
    unsigned int cpus = min_t(unsigned int, num_online_cpus(), 8);
    unsigned int factor;

    switch (sysctl_sched_tunable_scaling) {
    case SCHED_TUNABLESCALING_NONE:
        factor = 1;
        break;
    case SCHED_TUNABLESCALING_LINEAR:
        factor = cpus;
        break;
    case SCHED_TUNABLESCALING_LOG:
    default:
        factor = 1 + ilog2(cpus);
        break;
    }

    return factor;
}

static void update_sysctl(void)
{
    unsigned int factor = get_update_sysctl_factor();

#define SET_SYSCTL(name) \
    (sysctl_##name = (factor) * normalized_sysctl_##name)
    SET_SYSCTL(sched_base_slice);
#undef SET_SYSCTL
}
```
假设系统有 8 个核，那么 `factor=4`，最终的 `base_slice` 就为 `0.70ms * 4 = 2.8ms`

# 调度周期
* 在 EEVDF 的情况下，调度周期 P 的计算方法如下：
  * `W` 是所有任务的权重累计
  * s_i 是任务 `i` 的时间片（slice）
  * w_i 是任务 `i` 的权重（weight）
```
P_max = W * max(s_i / w_i)
```

* 对于某个特定任务 `i` 的平均周期 P<sub>i</sub> 是：

```
P_i = W * (s_i / w_i)
```

* 由此可见，整个 EEVDF 的调度周期，也是所有任务中平均调度周期最大的那个任务的平均调度周期。
* 每个任务公平地获得调度周期中的如下时间：

```
S_i = P * (w_i / W)
```
# 总结
CFS为了公平去实现公平，最终陷入了公平，而EEVDF为了延迟去实现低延迟，目前来看，其是EDF的Linux推广版，我们可以从解决问题的角度思考为何如此演进。

一个任务在OS上调度，你究竟要的是公平，还是要的是更低延迟的运行。

公平是一个虚幻的概念，而低延迟是目标体验。所以linux从CFS转移到EEVDF也就意味着，调度应该为了解决实际问题为根本点考虑，而不是为了理论公平，理论响应度最高来考虑设计。

当然，EEVDF可能因为低时延牺牲一定的高响应，最终取舍还是看实际OS产品落地的程序员












