今年26年一开始，工作性质就来了王炸，claude在工作的高效使用使得绝大部分专业人士都在推崇ai。当然，最近还有另一个东西很火，那就是openclaw，我也把openclaw搭建在自己的服务器上。可是我个人观点是，对于专业技术行业，我们更需要的是claude，而不是openclaw。

对于claude还是openclaw我们可以思考一下，我们自己更需要的是更强大的大脑，还是替你干活的小弟。

对我而言，我认为最需要的是更强大的大脑。所以，关于ai系列的文章，我选中claude而不是openclaw。

# 什么是claude
Claude 是 Anthropic 公司开发的专有大语言模型系列，Claude 强调少幻觉、更诚实、更安全，特别适合编码、文档分析、金融法律推理和企业级自动化场景

正是这些优点，使得目前绝大部分公司内的工作都可以让Claude代替你。

但是值得注意的是，是claude代替你，而不是openclaw代替你。

打个比方，openclaw是你的私人管家，它可以调用各种应用程序来执行任务，它干的活是你本身会的活

而claude更像是一个顶级大脑，超强的推理和编码，我们只需要提供想法，它能够聪明的自主完成工作。

也就是说，充分的使用claude，是我们工作性质接下来一环我认为必不可少的一个技能。

claude的最佳场景：
1. 软件开发全流程（架构设计、编码、调试、审查）。
2. 企业知识工作（合同分析、金融建模、法律研究、多文档总结）。
3. 自动化工作流（Agent Teams 处理跨工具任务）。
4. 教育、研究与内容创作（准确性要求高）。

大家可以对号入座，哪些场景是能够让claude替代我们工作的。

举个我构想的例子：

一个软件公司，从 测试环境，测试执行，BUG系统，日志分析，调试设备，代码提交，代码审核，问题复盘，问题汇总，代码注释，设计文档，技术方案 都可以让claude完美的接管执行。那么每个公司和部门只需要plugin和skills就可以替代这些工作内容了。

# claude的缺点
Claude的缺点我认为如下
1. 如何更精准的描述你的需求
2. 如何将工作抽象成skill/plugin
3. 如何让claude为你24小时干活

简单来说就是，怎么将Claude用的更好，就是每个人的实际竞争力。

当然，我仅仅针对个人工作观点，个人工作主要涉及操作系统及底层，其他非此行业不做评价。

# 安装
鉴于不是每个人都会linux，虽然我大部分时间都在linux上操作，为了更多的受众，我以windows为例介绍claude的搭建，比较claude搭建非常简单，跟着下面的办法就能够很快的将claude环境搭建成功。

## nvm安装
我们可以使用nvm来一键安装claude，所以先安装nvm，访问github
> https://github.com/coreybutler/nvm-windows/releases


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

下载后点击安装即可。

安装完成之后可以看到版本生效
```
nvm --version
1.2.2
```
## nodejs安装
管理员打开powershell，如下运行
```
# 安装最新 LTS 版本
nvm install lts

# 使用该版本
nvm use lts
```
安装完成之后，验证是否成功
```
node --version
v12.16.2
npm --version
11.9.0
```
## 安装claude
这里直接npm安装
```
npm install -g @anthropic-ai/claude-code
```

当然也有很多其他办法安装，claude官网说的很详细，可以自行查看
> https://claude.ai/downloads

安装成功后，查看版本
```
claude --version
2.1.78 (Claude Code)
```
## 配置config
我们直接创建.claude目录，如下命令
```
New-Item -Path "$env:USERPROFILE\.claude" -ItemType Directory -Force
```
可以看到创建成功
```


    目录: C:\Users\xxx


Mode                 LastWriteTime         Length Name
----                 -------------         ------ ----
d-----         2026/3/18     23:09                .claude
```
接下来新建文件，如下
```
@"
{
  "env": {
    "ANTHROPIC_AUTH_TOKEN": "YOUR_API_KEY",
    "ANTHROPIC_BASE_URL": "YOUR_BASE_URL",
    "ANTHROPIC_MODEL": "YOUR_MODEL"
  },
  "enabledPlugins": {
    "gopls-lsp@claude-plugins-official": true
  }
}
"@ | Out-File -FilePath "$env:USERPROFILE\.claude\settings.json" -Encoding UTF8
```
此时找到`C:\Users\xxx\.claude`目录，打开settings.json，我们需要填入
* YOUR_API_KEY
* YOUR_BASE_URL
* YOUR_MODEL

填入之后启动claude会提示如下错误
```
 Unable to connect to Anthropic services

 Failed to connect to api.anthropic.com: ERR_BAD_REQUEST

 Please check your internet connection and network settings.

 Note: Claude Code might not be available in your country. Check supported countries at
 https://anthropic.com/supported-countries
```
我们运行如下
```
@"
{
  "hasCompletedOnboarding": true
}
"@ | Out-File -FilePath "$env:USERPROFILE\.claude.json" -Encoding UTF8
```
然后输入claude即可出现如下画面
```
 claude

────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
 Accessing workspace:

 C:\WINDOWS\system32

 Quick safety check: Is this a project you created or one you trust? (Like your own code, a well-known open source
 project, or work from your team). If not, take a moment to review what's in this folder first.

 Claude Code'll be able to read, edit, and execute files here.

 Security guide

 > 1. Yes, I trust this folder
   2. No, exit

 Enter to confirm · Esc to cancel
```
此时正常了如下
```
 claude                                                                                          ╭─── Claude Code v2.1.78 ──────────────────────────────────────────────────────────────────────────────────────────╮
│                                              │ Tips for getting started                                          │
│                 Welcome back!                │ Run /init to create a CLAUDE.md file with instructions for Claude │
│                                              │ ───────────────────────────────────────────────────────────────── │
│                    ▐▛███▜▌                   │ Recent activity                                                   │
│                   ▝▜█████▛▘                  │ No recent activity                                                │
│                     ▘▘ ▝▝                    │                                                                   │
│                                              │                                                                   │
│   qwen-max             · API Usage Billing   │                                                                   │
│             D:\claude                        │                                                                   │
╰──────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

  ↑ Opus now defaults to 1M context · 5x more room, same pricing

────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
> Try "edit <filepath> to..."
────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
  ? for shortc… Claude Code has switched from npm to nativeinstall er. Run ` laude install` or see https://docs.anth…
```

# 总结
到这里claude就完全安装成功了。





















AI使用指南(1)-claude介绍

下面继续分析其他的patch
# [PATCH 12/15] sched: Introduce latency-nice as a per-task attribute
这里为 task_struct 提供了 latency_prio 字段，类似于 weight 的 nice value，所以latency_prio越低，则时延要求越高。
```
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -791,6 +791,7 @@ struct task_struct {
 	int				static_prio;
 	int				normal_prio;
 	unsigned int			rt_priority;
+	int				latency_prio;
 
 	struct sched_entity		se;
 	struct sched_rt_entity		rt;

```
所以新增一个 SCHED_FLAG_LATENCY_NICE 代表 用户态可以通过 sched_setattr 来定制化 sched_latency_nice
```
--- a/include/uapi/linux/sched.h
+++ b/include/uapi/linux/sched.h
@@ -132,6 +132,7 @@ struct clone_args {
 #define SCHED_FLAG_KEEP_PARAMS		0x10
 #define SCHED_FLAG_UTIL_CLAMP_MIN	0x20
 #define SCHED_FLAG_UTIL_CLAMP_MAX	0x40
+#define SCHED_FLAG_LATENCY_NICE		0x80
 
 #define SCHED_FLAG_KEEP_ALL	(SCHED_FLAG_KEEP_POLICY | \
 				 SCHED_FLAG_KEEP_PARAMS)
@@ -143,6 +144,7 @@ struct clone_args {
 			 SCHED_FLAG_RECLAIM		| \
 			 SCHED_FLAG_DL_OVERRUN		| \
 			 SCHED_FLAG_KEEP_ALL		| \
-			 SCHED_FLAG_UTIL_CLAMP)
+			 SCHED_FLAG_UTIL_CLAMP		| \
+			 SCHED_FLAG_LATENCY_NICE)
 
 #endif /* _UAPI_LINUX_SCHED_H */

```
 sched_latency_nice的范围是 -20 至 19 
```
 /*
  * Extended scheduling parameters data structure.
@@ -98,6 +99,22 @@ struct sched_param {
  * scheduled on a CPU with no more capacity than the specified value.
  *
  * A task utilization boundary can be reset by setting the attribute to -1.
+ *
+ * Latency Tolerance Attributes
+ * ===========================
+ *
+ * A subset of sched_attr attributes allows to specify the relative latency
+ * requirements of a task with respect to the other tasks running/queued in the
+ * system.
+ *
+ * @ sched_latency_nice	task's latency_nice value
+ *
+ * The latency_nice of a task can have any value in a range of
+ * [MIN_LATENCY_NICE..MAX_LATENCY_NICE].
+ *
+ * A task with latency_nice with the value of LATENCY_NICE_MIN can be
+ * taken for a task requiring a lower latency as opposed to the task with
+ * higher latency_nice.
  */
 struct sched_attr {
 	__u32 size;
@@ -120,6 +137,8 @@ struct sched_attr {
 	__u32 sched_util_min;
 	__u32 sched_util_max;
 
+	/* latency requirement hints */
+	__s32 sched_latency_nice;
 };
 
 #endif /* _UAPI_LINUX_SCHED_TYPES_H */

```
其初始值是 DEFAULT_PRIO
```
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -78,6 +78,7 @@ struct task_struct init_task
 	.prio		= MAX_PRIO - 20,
 	.static_prio	= MAX_PRIO - 20,
 	.normal_prio	= MAX_PRIO - 20,
+	.latency_prio	= DEFAULT_PRIO,
 	.policy		= SCHED_NORMAL,
 	.cpus_ptr	= &init_task.cpus_mask,
 	.user_cpus_ptr	= NULL,
@@ -89,7 +90,7 @@ struct task_struct init_task
 		.fn = do_no_restart_syscall,
 	},

```
fork的时候，prio是 nice 0
```
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -4719,6 +4719,8 @@ int sched_fork(unsigned long clone_flags
 		p->prio = p->normal_prio = p->static_prio;
 		set_load_weight(p, false);
 
+		p->latency_prio = NICE_TO_PRIO(0);
+
 		/*
 		 * We don't need the reset flag anymore after the fork. It has
 		 * fulfilled its duty:

```
__sched_setscheduler 的具体实现
```
+static void __setscheduler_latency(struct task_struct *p,
+				   const struct sched_attr *attr)
+{
+	if (attr->sched_flags & SCHED_FLAG_LATENCY_NICE)
+		p->latency_prio = NICE_TO_PRIO(attr->sched_latency_nice);
+}
+
 /*
  * Check the target process has a UID that matches the current process's:
  */
@@ -7641,6 +7650,13 @@ static int __sched_setscheduler(struct t
 			return retval;
 	}
 
+	if (attr->sched_flags & SCHED_FLAG_LATENCY_NICE) {
+		if (attr->sched_latency_nice > MAX_NICE)
+			return -EINVAL;
+		if (attr->sched_latency_nice < MIN_NICE)
+			return -EINVAL;
+	}
+
 	if (pi)
 		cpuset_read_lock();
 
@@ -7675,6 +7691,9 @@ static int __sched_setscheduler(struct t
 			goto change;
 		if (attr->sched_flags & SCHED_FLAG_UTIL_CLAMP)
 			goto change;
+		if (attr->sched_flags & SCHED_FLAG_LATENCY_NICE &&
+		    attr->sched_latency_nice != PRIO_TO_NICE(p->latency_prio))
+			goto change;
 
 		p->sched_reset_on_fork = reset_on_fork;
 		retval = 0;
@@ -7763,6 +7782,7 @@ static int __sched_setscheduler(struct t
 		__setscheduler_params(p, attr);
 		__setscheduler_prio(p, newprio);
 	}
+	__setscheduler_latency(p, attr);
 	__setscheduler_uclamp(p, attr);

```
# [PATCH 13/15] sched/fair: Implement latency-nice

新增设置 latency_prio 函数
```
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -1305,6 +1305,12 @@ static void set_load_weight(struct task_
 	}
 }
 
+static inline void set_latency_prio(struct task_struct *p, int prio)
+{
+	p->latency_prio = prio;
+	set_latency_fair(&p->se, prio - MAX_RT_PRIO);
+}
+

```
然后使用接口来实现设置latency prio，这样可以获得如下映射
* latency-nice 19: ~204.8ms (尽力而为)
* latency-nice -20: ~0.034ms (极低延迟)

```
 /*
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -952,6 +952,21 @@ int sched_update_scaling(void)
 }
 #endif
 
+void set_latency_fair(struct sched_entity *se, int prio)
+{
+	u32 weight = sched_prio_to_weight[prio];
+	u64 base = sysctl_sched_base_slice;
+
+	/*
+	 * For EEVDF the virtual time slope is determined by w_i (iow.
+	 * nice) while the request time r_i is determined by
+	 * latency-nice.
+	 *
+	 * Smaller request gets better latency.
+	 */
+	se->slice = div_u64(base << SCHED_FIXEDPOINT_SHIFT, weight);
+}
+

```
set_latency_fair 在 set_latency_prio 下使用，这里乘以1024，然后除上weight来计算期望的slice

# [PATCH 14/15] sched/fair: Add sched group latency support
这笔patch针对 cgroup 的 task_group 来完善set latency
```
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -378,6 +378,8 @@ struct task_group {
 
 	/* A positive value indicates that this is a SCHED_IDLE group. */
 	int			idle;
+	/* latency priority of the group. */
+	int			latency_prio;
 
 #ifdef	CONFIG_SMP
 	/*
@@ -488,6 +490,8 @@ extern int sched_group_set_shares(struct
 
 extern int sched_group_set_idle(struct task_group *tg, long idle);
 
+extern int sched_group_set_latency(struct task_group *tg, int prio);
+

```
```
+static int cpu_latency_nice_write_s64(struct cgroup_subsys_state *css,
+				     struct cftype *cft, s64 nice)
+{
+	int prio;
+
+	if (nice < MIN_NICE || nice > MAX_NICE)
+		return -ERANGE;
+
+	prio = NICE_TO_PRIO(nice);
+
+	return sched_group_set_latency(css_tg(css), prio);
+}
 #endif

```
```
@@ -11408,6 +11432,12 @@ static struct cftype cpu_files[] = {
 		.read_s64 = cpu_idle_read_s64,
 		.write_s64 = cpu_idle_write_s64,
 	},
+	{
+		.name = "latency.nice",
+		.flags = CFTYPE_NOT_ON_ROOT,
+		.read_s64 = cpu_latency_nice_read_s64,
+		.write_s64 = cpu_latency_nice_write_s64,
+	},
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH

```
这样在cgroup v2上的cpu.latency.nice，直接作用到cpu_latency_nice_read_s64和cpu_latency_nice_write_s64上

同样

新增的 sched_group_set_latency 可以对 task_group 更新 latency prio，这里lantency prio 一旦更新，group 下所有 se 的 slice 值也同步更新

# [PATCH 15/15] sched/eevdf: Use sched_attr::sched_runtime to set request/slice
```
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -7494,10 +7494,18 @@ static void __setscheduler_params(struct
 
 	p->policy = policy;
 
-	if (dl_policy(policy))
+	if (dl_policy(policy)) {
 		__setparam_dl(p, attr);
-	else if (fair_policy(policy))
+	} else if (fair_policy(policy)) {
 		p->static_prio = NICE_TO_PRIO(attr->sched_nice);
+		if (attr->sched_runtime) {
+			p->se.slice = clamp_t(u64, attr->sched_runtime,
+					      NSEC_PER_MSEC/10,   /* HZ=1000 * 10 */
+					      NSEC_PER_MSEC*100); /* HZ=100  / 10 */
+		} else {
+			p->se.slice = sysctl_sched_base_slice;
+		}
+	}
 
 	/*
 	 * __sched_setscheduler() ensures attr->sched_priority == 0 when
@@ -7689,7 +7697,9 @@ static int __sched_setscheduler(struct t
 	 * but store a possible modification of reset_on_fork.
 	 */
 	if (unlikely(policy == p->policy)) {
-		if (fair_policy(policy) && attr->sched_nice != task_nice(p))
+		if (fair_policy(policy) &&
+		    (attr->sched_nice != task_nice(p) ||
+		     (attr->sched_runtime && attr->sched_runtime != p->se.slice)))
 			goto change;
 		if (rt_policy(policy) && attr->sched_priority != p->rt_priority)
 			goto change;
@@ -8017,12 +8027,14 @@ static int sched_copy_attr(struct sched_
 
 static void get_params(struct task_struct *p, struct sched_attr *attr)
 {
-	if (task_has_dl_policy(p))
+	if (task_has_dl_policy(p)) {
 		__getparam_dl(p, attr);
-	else if (task_has_rt_policy(p))
+	} else if (task_has_rt_policy(p)) {
 		attr->sched_priority = p->rt_priority;
-	else
+	} else {
 		attr->sched_nice = task_nice(p);
+		attr->sched_runtime = p->se.slice;
+	}
 }
 
 /**

```
鉴于某些应用有精确的延迟要求，这里提供更精确的设置办法

# 总结
EEVDF的patch基本上都分析完成了，关于调度相关的原理的东西基本完结，但是针对调度而言，个人认为还有如下未尽事宜。
1. sched_ext 原理
2. eas 调度
3. PREEMPT_RT 补丁
4. RTLA分析：https://retis.sssup.it/~d.casini/papers/2025/TC2025/Timerlat_TC.pdf
5. Deadline 调度
6. bench工具：Schbench/Hackbench/Cyclictest
7. 维测工具：perfetto

鉴于现在AI特别的火，系统性的学习AI也至关重要，上面未尽事宜等什么时候有空再更新。转战AI。


# 参考
> https://lore.kernel.org/lkml/20230531124604.410388887@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.477939524@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.546980086@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.615053451@infradead.org/












调度(21)-EEVDF补丁解析5

继续分析eevdf的提交patch。

### [PATCH 07/15] sched/smp: Use lag to simplify cross-runqueue placement

首先，不需要再通过min_vruntime来更新vruntime，直接调用之前补丁实现的place_entity

```c
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
-       bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
        bool curr = cfs_rq->curr == se;

        /*
         * If we're the current task, we must renormalise before calling
         * update_curr().
         */
-       if (renorm && curr)
-               se->vruntime += cfs_rq->min_vruntime;
+       if (curr)
+               place_entity(cfs_rq, se, 0);
```
dequeue这部分，也是删除了之前cfs的自减min_vruntime，这个之前文章提过。

也因此 enqueue 时 不再只有ENQUEUE_WAKEUP的时候才 place_entity ，所以 dequeue 的时候对应要做 update_entity_lag
```c
@@ -5335,23 +5306,12 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 
 	clear_buddies(cfs_rq, se);
 
-	if (flags & DEQUEUE_SLEEP)
-		update_entity_lag(cfs_rq, se);
-
+	update_entity_lag(cfs_rq, se);
 	if (se != cfs_rq->curr)
 		__dequeue_entity(cfs_rq, se);
 	se->on_rq = 0;
 	account_entity_dequeue(cfs_rq, se);
 
-	/*
-	 * Normalize after update_curr(); which will also have moved
-	 * min_vruntime if @se is the one holding it back. But before doing
-	 * update_min_vruntime() again, which will discount @se's position and
-	 * can move min_vruntime forward still more.
-	 */
-	if (!(flags & DEQUEUE_SLEEP))
-		se->vruntime -= cfs_rq->min_vruntime;
-
 	/* return excess runtime on last dequeue */
 	return_cfs_rq_runtime(cfs_rq);
 

```
migrate_task_rq_fair 在cfs中的时候，需要重新计算vruntime，这里使用eevdf，删掉

```c
@@ -8102,18 +8062,6 @@ static void migrate_task_rq_fair(struct
 {
 	struct sched_entity *se = &p->se;
 
-	/*
-	 * As blocked tasks retain absolute vruntime the migration needs to
-	 * deal with this by subtracting the old and adding the new
-	 * min_vruntime -- the latter is done by enqueue_entity() when placing
-	 * the task on the new runqueue.
-	 */
-	if (READ_ONCE(p->__state) == TASK_WAKING) {
-		struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
-		se->vruntime -= u64_u32_load(cfs_rq->min_vruntime);
-	}
-
 	if (!task_on_rq_migrating(p)) {
 		remove_entity_load_avg(se);

```

task_fork_fair 也不需要调整vruntime，新版的place_entity 可以直接计算 se 的vruntime，所以删掉

值得注意的是 sysctl_sched_child_runs_first 本身是针对有child 需要先 于 parent 获得cpu的功能，这里eevdf直接删掉
```c
@@ -12492,22 +12440,9 @@ static void task_fork_fair(struct task_s
 
 	cfs_rq = task_cfs_rq(current);
 	curr = cfs_rq->curr;
-	if (curr) {
+	if (curr)
 		update_curr(cfs_rq);
-		se->vruntime = curr->vruntime;
-	}
 	place_entity(cfs_rq, se, 1);
-
-	if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
-		/*
-		 * Upon rescheduling, sched_class::put_prev_task() will place
-		 * 'current' within the tree based on its new key value.
-		 */
-		swap(curr->vruntime, se->vruntime);
-		resched_curr(rq);
-	}
-
-	se->vruntime -= cfs_rq->min_vruntime;
 	rq_unlock(rq, &rf);
 }

```
标准函数vruntime_normalized直接删掉，其本意是判断一个任务是否需要重平衡，这里在 detach_task_cfs_rq 和 detach_task_cfs_rq 一并删掉
```
@@ -12634,16 +12541,6 @@ static void attach_entity_cfs_rq(struct
 static void detach_task_cfs_rq(struct task_struct *p)
 {
 	struct sched_entity *se = &p->se;
-	struct cfs_rq *cfs_rq = cfs_rq_of(se);
-
-	if (!vruntime_normalized(p)) {
-		/*
-		 * Fix up our vruntime so that the current sleep doesn't
-		 * cause 'unlimited' sleep bonus.
-		 */
-		place_entity(cfs_rq, se, 0);
-		se->vruntime -= cfs_rq->min_vruntime;
-	}
 
 	detach_entity_cfs_rq(se);
 }
@@ -12651,12 +12548,8 @@ static void detach_task_cfs_rq(struct ta
 static void attach_task_cfs_rq(struct task_struct *p)
 {
 	struct sched_entity *se = &p->se;
-	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 	attach_entity_cfs_rq(se);
-
-	if (!vruntime_normalized(p))
-		se->vruntime += cfs_rq->min_vruntime;
 }
 

```

### [PATCH 08/15] sched: Commit to EEVDF

这里直接删掉原cfs的 sysctl_sched_latency 和 sysctl_sched_wakeup_granularity
```c
-unsigned int sysctl_sched_latency                     = 6000000ULL;
-unsigned int sysctl_sched_wakeup_granularity          = 1000000UL;
+unsigned int sysctl_sched_base_slice                  = 750000ULL;
```

删掉`LAST_BUDDY`、`SKIP_BUDDY`buddy机制
```
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -576,8 +576,6 @@ struct cfs_rq {
 	 */
 	struct sched_entity	*curr;
 	struct sched_entity	*next;
-	struct sched_entity	*last;
-	struct sched_entity	*skip;
 
```
在CFS的时候，需要做特殊处理如下
* 当任务yield的时候，标识为 skip buddy，这样可以判断跳过这个任务的选取
* 最后一次唤醒的时候，标识为 last buddy，这样cfs更容易选中这个被唤醒的任务

但是这在eevdf都是不需要的，因为它只需要一个关键 deadline

```
@@ -1098,35 +961,25 @@ static void update_deadline(struct cfs_r
 	if ((s64)(se->vruntime - se->deadline) < 0)
 		return;
 
-	if (sched_feat(EEVDF)) {
-		/*
-		 * For EEVDF the virtual time slope is determined by w_i (iow.
-		 * nice) while the request time r_i is determined by
-		 * sysctl_sched_min_granularity.
-		 */
-		se->slice = sysctl_sched_min_granularity;
-
-		/*
-		 * The task has consumed its request, reschedule.
-		 */
-		if (cfs_rq->nr_running > 1) {
-			resched_curr(rq_of(cfs_rq));
-			clear_buddies(cfs_rq, se);
-		}
-	} else {
-		/*
-		 * When many tasks blow up the sched_period; it is possible
-		 * that sched_slice() reports unusually large results (when
-		 * many tasks are very light for example). Therefore impose a
-		 * maximum.
-		 */
-		se->slice = min_t(u64, sched_slice(cfs_rq, se), sysctl_sched_latency);
-	}
+	/*
+	 * For EEVDF the virtual time slope is determined by w_i (iow.
+	 * nice) while the request time r_i is determined by
+	 * sysctl_sched_min_granularity.
+	 */
+	se->slice = sysctl_sched_min_granularity;
 
 	/*
 	 * EEVDF: vd_i = ve_i + r_i / w_i
 	 */
 	se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
+
+	/*
+	 * The task has consumed its request, reschedule.
+	 */
+	if (cfs_rq->nr_running > 1) {
+		resched_curr(rq_of(cfs_rq));
+		clear_buddies(cfs_rq, se);
+	}
 }

```
根据上面的代码，可以看到，直接给slice为sysctl_sched_min_granularity，把之前一些兼容cfs的东西删掉

```
-/*
- * 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 delta_exec;
-	struct sched_entity *se;
-	s64 delta;
-
-	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
-	if (delta_exec > curr->slice) {
-		resched_curr(rq_of(cfs_rq));
-		/*
-		 * The current task ran long enough, ensure it doesn't get
-		 * re-elected due to buddy favours.
-		 */
-		clear_buddies(cfs_rq, curr);
-		return;
-	}
-
-	/*
-	 * Ensure that a task that missed wakeup preemption by a
-	 * narrow margin doesn't have to wait for a full slice.
-	 * This also mitigates buddy induced latencies under load.
-	 */
-	if (delta_exec < sysctl_sched_min_granularity)
-		return;
-
-	se = __pick_first_entity(cfs_rq);
-	delta = curr->vruntime - se->vruntime;
-
-	if (delta < 0)
-		return;
-
-	if (delta > curr->slice)
-		resched_curr(rq_of(cfs_rq));
-}
-

```
删掉cfs独有的check_preempt_tick

```
 /*
  * Pick the next process, keeping these things in mind, in this order:
  * 1) keep things fair between processes/task groups
@@ -5420,53 +5189,14 @@ wakeup_preempt_entity(struct sched_entit
 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)) {
-		/*
-		 * Enabling NEXT_BUDDY will affect latency but not fairness.
-		 */
-		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);
-
 	/*
-	 * Avoid running the skip buddy, if running something else can
-	 * be done without getting too unfair.
+	 * Enabling NEXT_BUDDY will affect latency but not fairness.
 	 */
-	if (cfs_rq->skip && cfs_rq->skip == se) {
-		struct sched_entity *second;
+	if (sched_feat(NEXT_BUDDY) &&
+	    cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next))
+		return cfs_rq->next;
 
-		if (se == curr) {
-			second = __pick_first_entity(cfs_rq);
-		} else {
-			second = __pick_next_entity(se);
-			if (!second || (curr && entity_before(curr, second)))
-				second = curr;
-		}
-
-		if (second && wakeup_preempt_entity(second, left) < 1)
-			se = second;
-	}
-
-	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
-		/*
-		 * Someone really wants this to run. If it's not unfair, run it.
-		 */
-		se = cfs_rq->next;
-	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
-		/*
-		 * Prefer last buddy, try to return the CPU to a preempted task.
-		 */
-		se = cfs_rq->last;
-	}
-
-	return se;
+	return pick_eevdf(cfs_rq);
 }

```
pick_next_entity 全面删除cfs的逻辑，只留下eevdf的内容

其他一些删除的东西，这里略过一下。详细可以查看后面的参考链接

### [PATCH 09/15] sched/debug: Rename min_granularity to base_slice

```c
-unsigned int sysctl_sched_min_granularity           = 750000ULL;
+unsigned int sysctl_sched_base_slice           = 750000ULL;
```
重命名，其目的为：
- `min_granularity`暗示了CFS中时间片的最小保证
- `base_slice`明确表示这是EEVDF中任务的基本请求时间

在EEVDF中，slice不再是最小保证，而是计算虚拟deadline的基础参数：
```
se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
```

### [PATCH 10/15] sched/fair: Propagate enqueue flags into place_entity()

新增了 ENQUEUE_INITIAL 的flag
```c
-static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
+static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
        u64 vslice = calc_delta_fair(se->slice, se);
        u64 vruntime = avg_vruntime(cfs_rq);

        /*
         * on average, halfway through their slice, as such start tasks
         * off with half a slice to ease into the competition.
         */
-       if (sched_feat(PLACE_DEADLINE_INITIAL) && initial)
+       if (sched_feat(PLACE_DEADLINE_INITIAL) && (flags & ENQUEUE_INITIAL))
                vslice /= 2;
```

这个initial和wakeup，migrated平级了。

- `ENQUEUE_INITIAL`标志用于新fork的任务
- `ENQUEUE_WAKEUP`标志用于唤醒的任务
- `ENQUEUE_MIGRATED`标志用于迁移的任务

### [PATCH 11/15] sched/eevdf: Better handle mixed slice length
首先 引入 avg_slice 的概念。基本上和 avg_vruntime 的概念类似，是对时间的平均累加和。
```
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -642,6 +642,7 @@ avg_vruntime_add(struct cfs_rq *cfs_rq,
 	s64 key = entity_key(cfs_rq, se);
 
 	cfs_rq->avg_vruntime += key * weight;
+	cfs_rq->avg_slice += se->slice * weight;
 	cfs_rq->avg_load += weight;
 }
 
@@ -652,6 +653,7 @@ avg_vruntime_sub(struct cfs_rq *cfs_rq,
 	s64 key = entity_key(cfs_rq, se);
 
 	cfs_rq->avg_vruntime -= key * weight;
+	cfs_rq->avg_slice -= se->slice * weight;
 	cfs_rq->avg_load -= weight;
 }

```

entity_has_slept 先判断任务是否是sleep到wakeup，且不是迁移任务，如果满足，则将lag补足

```c
static inline bool
entity_has_slept(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
        u64 now;

        if (!(flags & ENQUEUE_WAKEUP))
                return false;

        if (flags & ENQUEUE_MIGRATED)
                return true;

        now = rq_clock_task(rq_of(cfs_rq));
        return (s64)(se->exec_start - now) >= se->slice;
}
```
添加一个启发式算法PLACE_FUDGE
```c
 static void
 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
@@ -4930,6 +4947,19 @@ place_entity(struct cfs_rq *cfs_rq, stru
 		lag = se->vlag;
 
 		/*
+		 * For latency sensitive tasks; those that have a shorter than
+		 * average slice and do not fully consume the slice, transition
+		 * to EEVDF placement strategy #2.
+		 */
+		if (sched_feat(PLACE_FUDGE) &&
+		    (cfs_rq->avg_slice > se->slice * cfs_rq->avg_load) &&
+		    entity_has_slept(cfs_rq, se, flags)) {
+			lag += vslice;
+			if (lag > 0)
+				lag = 0;
+		}
+
+		/*
 		 * 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

```

这个算法的核心思想是：
1. 当任务的slice小于平均slice时，认为它是延迟敏感任务
2. 如果该任务睡眠时间超过其slice，则将其移动到策略#2
3. 策略#2确保任务立即获得执行资格，避免被大slice任务压制

对于延迟敏感任务，我们希望：
$$
lag_i = w_i \times (V - v_i) \leq r_i
$$
其中`r_i`是任务的请求时间（slice）。当任务睡眠时间超过`r_i`时，我们重置其lag，确保它能够及时获得CPU时间。

## 总结

总结一下这些补丁的核心内容。
1. **SMP优化**：使用lag机制替代min_vruntime的计算
2. **策略统一**：移除了CFS的启发式丑代码
3. **命名清晰**：重命名参数
4. **场景感知**：新增enqueue initial flags
5. **混合负载**：为eevdf添加启发式算法优化不同slice长度任务的调度

# 参考
> https://lore.kernel.org/lkml/20230531124604.068911180@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.137187212@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.205287511@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.274010996@infradead.org/
> https://lore.kernel.org/lkml/20230531124604.341527144@infradead.org/



调度(20)-EEVDF补丁解析4

之前介绍了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/
