# EEVDF 理論與核心實作的比較對照
參考前人的筆記
[CFS 1](https://hackmd.io/@sysprog/Hka7Kzeap/%2FBJ9m_qs-5#enqueue_task)
[CFS 2](https://hackmd.io/@sysprog/Hka7Kzeap/%2FB18MhT00t)
[EEVDF １](https://hackmd.io/@sysprog/Hka7Kzeap/%2FSyG4t5u1a)
[EEVDF ２](https://hackmd.io/@sysprog/Hka7Kzeap/%2FHkyEtNkjA)
[EEVDF 論文筆記](https://hackmd.io/@salmonii/SkXQvDKZel)
## 定義
### 論文
論文中是用請求的概念，假設某個任務 $i$ 在時間 $t$ 發出使用 Cpu 資源的請求，並且會用到時間 $t$ 為止此任務所實際被服務的時間 $s_i$ 去計算虛擬合格時間 $V(e)$，進而搭配請求的長度 $r$ 去計算出虛擬截止時間 $V(d)$。以下附上對應公式：
$$V(e) = V(t^i_0) + \dfrac{s_i(t^i_0,t)}{w_i}$$
$$V(d) = V(e) + \dfrac{r}{w_i}$$
注意到 $V(d)$ $V(e)$ 是全局虛擬時間軸 $V(t)$ 上的座標點。
### 核心
從理論角度，寫出可以動態追蹤的每個任務的虛擬時間進展公式：
$$v_i(t) = V(t^i_0) + \dfrac{s_i(t^i_0, t)}{w_i}$$
這裡的 $t$ 是任意時刻，$v_i(t)$ 是任務 $i$ 的當下虛擬時間。
從論文可以看出，論文對於每個任務各自累積的動態增長的虛擬時間並不關心，論文的演算法關心的是請求們的虛擬合格、虛擬截止時間「點」。
這是因為 EEVDF 理論上是事件驅動的，演算法就是在這些點之間做選擇，而不是追蹤任務的狀態變化。
但是實作上不一樣，會去維護每個任務的累積 vruntime，簡化為任務級別的排程，以下繼續說明：
$$lag_i(t) = S_i(t^i_0, t) - s_i(t^i_0, t)
= w_i(V(t) - V(t^i_0)) - s_i(t^i_0, t)$$
得到：
$$lag_i(t) = S_i - s_i = w_i(V(t) - v_i(t))$$
實際去追蹤原始碼會發現 EEVDF 並不是用 $v_i(t) = V(t^i_0) + \dfrac{s_i(t^i_0, t)}{w_i}$ 的方式去維護每個任務的虛擬執行時間，而是保留了 CFS 的計算方式，要看到這當中的關鍵函式 `calc_delta_fair`：
此函式的目的是想要去計算 $\dfrac{r_i}{w_i}$ 或 $\dfrac{s_i(t^i_0, t)}{w_i}$，對照到理論公式就是 $\dfrac{r_i}{w_i}$ 用於計算 virtual deadline，$\dfrac{s_i(t^i_0, t)}{w_i}$ 用於更新任務本身的 virtual runtime，這兩個情況也是此函式的主要使用時機。
```c
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se){
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}
```
將實際時間（delta）根據該 se 的權重轉換成虛擬的時間單位。`__calc_delta` 函式會根據比例 `delta × NICE_0_LOAD / se->load.weight` 做轉換。因此以任務個別的虛擬時間 vruntime 來看，實際上是在計算：
`vruntime += actual_time × (NICE_0_LOAD / task_weight);`
實際舉例來看，假設兩個任務，任務 A 的權重是 1024，任務 B 的權重是 512。都執行 100ms：
理論方法 $v_i(t) = V(t^i_0) + \dfrac{s_i(t^i_0, t)}{w_i}$：
$v_A(t) = V(t^A_0) + \dfrac{100}{1024}$
$v_B(t) = V(t^B_0) + \dfrac{100}{512}$
個別任務基於全局虛擬時間 $V(t)$ 為標準計算 vruntime，需要知道目前全局虛擬時間，且如果全局的虛擬時間改變了（比如說有任務權重改變），所有任務的 vruntime 也要跟著更新。
核心實作，直接累積：
$v_A(t) += 100 \dfrac{1024}{1024} = 100$
$v_B(t) += 100 \dfrac{1024}{512} = 200$
乘上 `NICE_0_LOAD` （$1024$），將所有任務的時間進展標準化到 nice 0 的基準，權重高的任務 vruntime 增加較慢，權重低的任務 vruntime 增加較快。
如果宏觀來看，論文中的 $V(t)$ 會以與所有活躍任務權重總和成反比的速率增長，依照理論方法計算的 $v_i(t)$ 增長速率主要是取決於 $V(t)$。Linux 實作中，透過將所有任務的時間增量標準化到 `NICE_0_LOAD` 基準，來達成這個統一的虛擬時間概念，當任務權重改變時，vruntime 仍然保持在統一基準下，不需要重新計算所有任務的相對位置。
不過核心中還是有 $V(t)$ 的影子，因為 EEVDF 演算法的一個特點就是關於「合格」的概念，但是它跟論文計算方式就完全不一樣了，後續會說明。
::: info
我想問的是 EEVDF 這樣設計的原因主要是因為不想維護 $V(t)$ 跟所有任務的 vruntime，還是為了配合 CFS 的演化？
:::
#### 請求 request
```c
void __setparam_fair(struct task_struct *p, const struct sched_attr *attr)
{
struct sched_entity *se = &p->se;
p->static_prio = NICE_TO_PRIO(attr->sched_nice);
if (attr->sched_runtime) {
se->custom_slice = 1;
se->slice = clamp_t(u64, attr->sched_runtime,
NSEC_PER_MSEC/10, /* HZ=1000 * 10 */
NSEC_PER_MSEC*100); /* HZ=100 / 10 */
} else {
se->custom_slice = 0;
se->slice = sysctl_sched_base_slice;
}
}
```
```c
unsigned int sysctl_sched_base_slice = 750000ULL;
```
權重不影響 slice 大小，而是影響 deadline 計算，`se->slice` 是 EEVDF 中每個任務的標準請求大小，讓排程器知道這個任務預期要運行多久
這邊可以看出跟 CFS 已經不一樣了，CFS 任務的 slice 是會動態改變的。
#### time quantum $q$
在論文中的定義是系統分配資源的最小時間單位，不可被進一步分割的時間片段。
實作上對應到：
```c
#define TICK_NSEC ((NSEC_PER_SEC+HZ/2)/HZ)
```
目前只是推測，會這樣推測是因為 `update_entity_lag` 函式中限制 virtual lag 的部分（下面有說明）。
## 紅黑數的變遷
此 section 不探討論文實作比較，討論關於 CFS 到 EEVDF 的紅黑數差異，還有 EEVDF 中的紅黑數實作。
在 CFS 中 fairness 是透過選擇擁有最小 vruntime 的任務來實現的。紅黑樹依據 vruntime 排序，最左側節點就是目前應該被執行的任務，因此可以透過 cached leftmost 節點實現 $O(1)$ 的任務挑選成本。
但是 EEVDF 除了要 fairness 還要 responsiveness，即對任務延遲上界的保證。EEVDF 需要根據最早的 eligible deadline 來選擇任務，而不是像傳統 CFS 一樣使用 vruntime 判斷。這導致 Linux 核心原本針對 CFS 的紅黑樹設計無法直接套用，因為即使紅黑樹能 cache 最左節點（最小 vruntime），這對選出最小 deadline 的任務並沒有幫助。
因此 Linux 調整了紅黑樹的排序 key 為 virtual deadline，而不是 vruntime，以便盡可能在 $O(1)$ 時間內從 cached 最左節點挑出 deadline 最早的任務（不過挑選任務的演算法不一定會是 $O(1)$，$O(1)$ 只是 best case，後續會介紹）。
以下是幾個重點說明：
### 紅黑樹排序 key 改成 deadline
在最新的版本 v6.14 中，EEVDF 下的 `cfs->tasks_timeline` 是一棵以 deadline 為 key 的紅黑樹，`rb_first_cached` 巨集直接取得最小 key（也就是最早 deadline 的任務）。
```c
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};
#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
/* Same as rb_first(), but O(1) */
#define rb_first_cached(root) (root)->rb_leftmost
```
```c
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
if (!left)
return NULL;
return __node_2_se(left);
}
```
### Augmented 紅黑樹
引入了 `min_vruntime` 和 `min_slice` 作為每個 `sched_entity` 的 augmented 欄位，記錄其節點的子樹中所有節點的最小 vruntime 和最小 slice。
```c
struct sched_entity {
...
u64 min_vruntime;
u64 min_slice;
...
}
```
### 為什麼需要 `se->min_vruntime`
* 更有效率的的任務選擇：在 `pick_eevdf` 函式中，如果出現目前最小 deadline 的任務不為合格，而需要挑選別的任務的情況，可以透過維護每個 `sched_entity` 的 `min_vruntime`，直接跳過不看一半的子樹來避免逐一走訪樹狀結構。
* `cfs_rq->min_vruntime` 因為時間一直在走，也會一直去更新，在原本的 CFS `update_min_vruntime` 函式中，樹上最小 `vruntime` 可以直接由舊版的 `__pick_first_entity` 去抓到。但是 EEVDF 由於排序的 key 更改，為了避免逐一走訪來取得最小 `vruntime`，改為透過 `__pick_root_entity` 來拿到 root，再藉由 augmented 用法是 vruntime 的 heap 這件事去拿到整個樹的最小 `vruntime`，以維持取得最小 `vruntime` 這件事為 $O(1)$。
> 我目前只看到這兩點，函式詳細內容請看後續說明
### 維護 Augmented Data 的成本
`min_vruntime_update` 函式會遞迴更新左子節點、右子節點的 `min_vruntime`，並且記錄在目前節點：
```c
/*
* se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
*/
static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
{
u64 old_min_vruntime = se->min_vruntime;
u64 old_min_slice = se->min_slice;
struct rb_node *node = &se->run_node;
se->min_vruntime = se->vruntime;
__min_vruntime_update(se, node->rb_right);
__min_vruntime_update(se, node->rb_left);
se->min_slice = se->slice;
__min_slice_update(se, node->rb_right);
__min_slice_update(se, node->rb_left);
return se->min_vruntime == old_min_vruntime &&
se->min_slice == old_min_slice;
}
```
透過註解得知每個節點（`seche_entity`）的 `min_vruntime` 都遵循這個不變式：
```c
se->min_vruntime = min(se->vruntime,
se->left->min_vruntime, // 左子樹的最小值
se->right->min_vruntime) // 右子樹的最小值
```
因此對於每個節點作為根節點的子樹來說，整個子樹中的最小 vruntime 會是他的根節點的 `se->min_vruntime`。
```
節點A (vruntime=10, min_vruntime=5)
/
節點B
(vruntime=12,
min_vruntime=5)
節點C 節點D
(vr=5, (vr=7,
min=5) min=7)
```
::: info
目前出現了`update_min_vruntime` 和 `min_vruntime_update` 兩個函式，不過此 `min_vruntime` 非彼 `min_vruntime`：
* `update_min_vruntime`：`cfs_rq` 底下的
* `min_vruntime_update`：`se` 中，代表目前節點子樹中 vruntime 最小的值。
這是我覺得核心在取名上可以改進的部分？
:::
## 全局虛擬時間 $V(t)$ 和 $v_i$ 的計算方式
### 論文
論文中的 system virtual time：
$$
V(t) = \int_{0}^{t} \dfrac{1}{\sum_{j \in \mathcal{A}(\tau)} w_j} \, d\tau
$$
全局虛擬時間 $V(t)$ 會根據目前系統中活躍的任務的權重以動態的速率增長。連續的且每個任務並不會維護自己的 virtual runtime。
### 核心
排程實體 `sched_entity` 中的 `vruntime` 代表每個任務自己累計的虛擬執行時間 virtual runtime
```c
struct sched_entity {
...
u64 vruntime;
...
}
```
這裡的 `vruntime` 是累積的虛擬服務時間，不是全局的虛擬時間。任務從開始到現在累積獲得的虛擬服務時間，可以用來計算任務的 $\operatorname{lag}$ 和進度。
符號上以 $v_i$ 代表任務 $i$ 的虛擬執行時間。$v_i(t)$ 代表在目前時間 $t$ 時任務 $i$ 累計的虛擬執行時間。
#### $V(t)$ 的計算
從[原始碼](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L629)的註解可以看出實作上是怎麼維護 $V(t)$ 的：
```c
/* 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.
*/
```
利用每個任務的 $\operatorname{lag}$ 定義：
$$lag_i(t) = w_i(V(t) - v_i(t))$$
再結合：
$$\sum_{i \in \mathcal{A}(t)} \operatorname{lag}_i(t) = 0$$
可以反推出 $V(t)$：
$$\sum_{i \in \mathcal{A}(t)} lag_i(t) = \sum_{i \in \mathcal{A}(t)} w_iV(t)- \sum_{i \in \mathcal{A}(t)} w_iv_i(t)$$
$$V(t)\sum_{i \in \mathcal{A}(t)} w_i = \sum_{i \in \mathcal{A}(t)} w_iv_i(t)$$
$$V(t) = \dfrac{\sum_{i \in \mathcal{A}(t)} w_iv_i(t)}{\sum_{i \in \mathcal{A}(t)} w_i} = \dfrac{\sum w_iv_i(t)}{W}$$
也就是以權重 $w_i$ 加權平均各個任務的虛擬執行時間 $v_i$。對應到論文中的全局虛擬時間，但我不會說他是一個「時鐘」，他是由所有任務的 `vruntime` 去反推計算的，並不會連續的往前走。
::: info
問老師：
這部分還需要釐清 首先這個公式是建立在假設 lag 總和恆為 0 的情況下，但是從老師的[課堂討論筆記](https://hackmd.io/uiNwM35dQ6qeFQwfTypc_w#CFS-與-EEVDF-的-Fairness-探索)中提到：
> 藉由資格條件與虛擬截止時間機制，EEVDF 的 lag 嚴格控制在一個時間片段內：$0 \le \operatorname{lag}_i(t) \le \frac{s_i^{req} \cdot w_0}{w_i}$。
如果 lag 不會為負的話，要怎麼得到 lag 總和恆為 0？
> 老師說這邊寫的是預期
:::
::: info
為什麼維護每個任務的累積 `vruntime` 而不是直接維護全局虛擬時間？為什麼要靠反推的方式？
效率考量？實作上如果真的要在每一個極細微時間都重算積分，開銷太大。
改成離散累加後的結果
延伸自 CFS？Linux 的 CFS 本身就用 `vruntime` 校正的離散方法，EEVDF 在此基礎上改成更嚴格的理論模型
如果系統中有 n 個任務，理論方法中 1 的任務離開，會需要去調整其他 n-1 個任務的 `vruntime`。但是在核心中只要改 1 次 $V(t)$？
> 5/27 一對一討論老師解答：
為什麼要反推？
不能用系統時間來計算，CPU 不是隨時都在做事 ex.中斷、load balance 的時間也要排除
>
>論文講的是給足夠長的時間、上界
但是對於實作來說，很多事情是作業系統自己的成本，計算整個系統時間沒有幫助
:::
但是由於每個任務的 virtual runtime $v_i$ 是64 位元整數，當計算 $\dfrac{\sum w_iv_i(t)}{W}$ 時，乘法部分 $w_iv_i(t)$ 很容易會溢位。
因此真正的實作上轉換成相對的形式：
定義 $v_0$ 是某個基準 virtual runtime，公式改成：
$$V(t) = \dfrac{\sum w_i(v_i(t)-v_0)}{W} + v_0$$
$v_i(t)-v_0$ 的差值比較小，較不容易 overflow。
```c
/*
* 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.
*/
```
```c
struct cfs_rq {
...
s64 avg_vruntime;
u64 avg_load;
u64 min_vruntime;
...
}
```
從註解可以看到對應的實作變數在 `cfs_rq` 這個結構體裡面，`cfs_rq` 會以樹狀結構管理排程的實體 `sched_entity`，所以可以想成他是
* `avg_vruntime`：
$$\sum w_i(v_i(t)-v_0)$$
* `avg_load`：
$$\sum w_i$$
* `min_vruntime`：
$$v_0$$
它是單調遞增的，表示時間只會往前、不會倒退。進行 normalize 所需的參數。
::: info
目前不懂為什麼會這樣取 `avg_vruntime` `avg_load` 的變數名，單就代表的內容來看，我覺得比起 avg 比較像 total
:::
> 所以核心的 $V(t)$ 是 $\dfrac{\text{cfs_rq -> avg_vruntime}}{\text{cfs_rq -> avg_load}} + \text{cfs_rq -> min_vruntime}$ 嗎？？
找到了，在 `avg_vruntime` 函式：
```c
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) {
/* sign flips effective floor / ceiling */
if (avg < 0)
avg -= (load - 1);
avg = div_s64(avg, load);
}
return cfs_rq->min_vruntime + avg;
}
```
此函式計算 $V(t) = \dfrac{\sum w_i(v_i(t)-v_0)}{W} + v_0$
> 名字跟 cfs->avg_vruntime 長一樣...
只在 `update_entity_lag`、`place_entity` 函式中被呼叫。
當一個任務正在運行時（成為 `curr`），它會從 cfs runqueue 的統計數據中被移除，但在計算整體平均值時，仍然需要考慮這個正在運行的任務。雖然目前還沒看到，我猜想在 dequeue 或是 enqueue entity 相關的函式會去動到 `cfs->avg_vruntime` 相關參數。
所以這邊的條件判斷 `if (curr && curr->on_rq)` 目的在把 `curr` 的造成的貢獻一起加入計算。
`entity_key` 函式在做的事就是上述提到的相對概念 $v_i - v_0$，回傳任務 $i$ 虛擬執行時間和目前最小虛擬執行時間的差值。
```c
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
return (s64)(se->vruntime - cfs_rq->min_vruntime);
}
```
---
#### $v_i$ 的計算
主要在 [`update_curr`](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L1228) 函式：他的功能是更新目前任務的運行時統計資料，包括 `vruntime` 和截止時間。
首先檢查 runqueue 上是否有正在執行的任務，計算自上次更新以來實際執行的時間增量，如果沒有執行時間，直接返回。
```c
if (unlikely(!curr))
return;
delta_exec = update_curr_se(rq, curr);
if (unlikely(delta_exec <= 0))
return;
```
更新 `vruntime`，將實際執行時間轉換為虛擬時間：
```c
curr->vruntime += calc_delta_fair(delta_exec, curr);
```
更新 virtual deadline：
```c
resched = update_deadline(cfs_rq, curr);
```
更新最小虛擬執行時間還有全局虛擬時間：
```c
update_min_vruntime(cfs_rq);
```
---
[`update_deadline`](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L1021) 函式如下，`update_curr` 也是它的唯一進入點：
首先要比較任務目前已經消耗的虛擬時間和虛擬截止時間，如果 `vruntime < deadline`，表示任務還沒有達到其虛擬截止時間，即為目前請求尚未完成，不需要更新截止時間。
```clike
if ((s64)(se->vruntime - se->deadline) < 0)
return false;
```
如果目前請求已完成，需要為下一個請求計算新的截止時間，根據排程實體 se 目前累積的虛擬執行時間，加上根據權重計算出的虛擬時間單位，算出 virtual deadline。最後回傳 ture：
```c
/*
* For EEVDF the virtual time slope is determined by w_i (iow.
* nice) while the request time r_i is determined by
* sysctl_sched_base_slice.
*/
if (!se->custom_slice)
se->slice = sysctl_sched_base_slice;
/*
* EEVDF: vd_i = ve_i + r_i / w_i
*/
se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
```
---
`update_min_vruntime` 函式如下：
```c
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
struct sched_entity *se = __pick_root_entity(cfs_rq);
struct sched_entity *curr = cfs_rq->curr;
u64 vruntime = cfs_rq->min_vruntime;
if (curr) {
if (curr->on_rq)
vruntime = curr->vruntime;
else
curr = NULL;
}
if (se) {
if (!curr)
vruntime = se->min_vruntime;
else
vruntime = min_vruntime(vruntime, se->min_vruntime);
}
/* ensure we never gain time by being placed backwards. */
cfs_rq->min_vruntime = __update_min_vruntime(cfs_rq, vruntime);
}
```
首先先用 `__pick_root_entity` 函式去抓到目前的根節點，因為 EEVDF 中有 augmented 並且維護每個節點的 `min_vruntime`，可以透過取得根節點對應的 `se->min_vruntime` 來得知目前樹中最小的 vruntime。
可能會走到的一條路是去比較目前在 runqueue 中執行任務的 vruntime 和在紅黑樹中最小的 vruntime，用 `min_vruntime` 函式找到在以上兩個 vruntime 值中選擇較小的那個。
::: info
我自己覺得 `update_min_vruntime` 裡面的條件判斷不好理解
```c
if (curr && curr->on_rq && se){
vruntime = min_vruntime(curr->vruntime, se->min_vruntime);
}
else if (curr && curr->on_rq){ // 代表紅黑樹為空的情況
vruntime = curr->vruntime;
}
else if (se){ // 不管有沒有curr，只要有等待任務就用樹中最小值
vruntime = se->min_vruntime;
}
```
有機會重構原始碼的條件判斷嗎？
:::
```c
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;
}
```
隨著時間，變數 `min_vruntime` 勢必要跟著更新，而在更新 `cfs_rq->min_vruntime` 時，與之相關的 `cfs->avg_vruntime` 也需更新。`__update_min_vruntime` 函式達成上述目的，並且確保 `min_vruntime` 會是單調遞增的。
## `cfs->min_vruntime` 功能
> todo
到目前為止，發現自己對於 `cfs->min_vruntime` 了解不全，像是 `se->min_vruntime` 就有很清楚的定義是目前 `se` 作為根節點的子樹中的最小 `vruntime`，但是對於 `cfs->min_vruntime` 就只知道他會在計算 $V(t)$ 時用來標準化每個任務的 `vruntime`，以及代表系統時間的單調遞增性質，確保 `vruntime` 成長不會回退。
首先幾個問題：
* 他會是代表整個 `cfs->tasks_timeline` 紅黑樹中的最小 vruntime 嗎？
* 如果上述為真，是否與透過 `__pick_root_entity` 取得根節點，再取得其 augmented data `se->min_vruntime` 的值會是一樣的？
* 如果上述為否，`cfs->min_vruntime` 是代表什麼，他還有什麼其他的功能？
目前根據參考的 CFS 筆記中，有提及：
> `min_vruntime` 是 runqueue 中所有 entity 的 vruntime 之最小值，該值是用來在 enqueue `sched_entity` 的時候協助初始化其 vruntime。思考任務被移出 runqueue 時的議題: 假設有任務 A 需要處理 I/O 而被暫時移出 runqueue，其 `vruntime` 會維持同樣的值，而仍處在在 runqueue 中的任務則會持續增加。當這個任務 A 被喚醒並且放回 runqueue 時，如果 `vruntime` 是依離開時的值設定，這會導致這個任務的優先遠超其他原本在 runqueue 中的任務，這違反了 CFS "fair" 的精神。
>
>因此，CFS scheduler 會追蹤整個 runqueue 中的最小 `min_vruntime`，當每個任務被挑選並運行時，這個最小值也同步更新。如此一來，當新的任務被建立，就可以透過這個值去初始化其 `vruntime`。對於進入 wait queue 而後被喚醒的任務，則是確保其原本的 `vruntime` 需不小於記錄的最小值，否則就重設為該最小值再放回 runqueue 中，藉此避免被喚醒的任務會長時間的霸佔 CPU 資源。
可以看出在 CFS 中，`cfs->min_vruntime` 會用來初始化 enqueue `sched_entity` 的 `vruntime`。但是 EEVDF 已經不再單純根據 `vruntime` 來選擇 runqueue 中的任務，因此新的問題：
* 從 CFS 演進到 EEVDF 的過程中，`cfs->min_vruntime` 的意義是否有變化？
### `place_entity` 函式功能與呼叫點
既然剛剛提到了在 enqueue 時用來初始化 `vruntime` 的功能，以下先追蹤這條：
`enqueue_entity` -> `place_entity`
#### CFS
在 CFS 中，`place_entity` 函式主要用於調整剛被喚醒或新建的任務的 `vruntime`。
```c
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial);
```
```clike
u64 vruntime = cfs_rq->min_vruntime;
```
以 `cfs_rq->min_vruntime` 來重新初始化 se。
```c
if (initial && sched_feat(START_DEBIT))
vruntime += sched_vslice(cfs_rq, se);
```
在 CFS 中有一個 `START_DEBIT` 的 scheduler config。作用是在將新任務的 `vruntime` 增加一些時間，確保新任務不會立即搶佔，而是等待適當的時機，這避免了在 CFS 上可以透過 fork 來不斷取得 CPU，導致其他任務 starvation 之問題。
```c
if (!initial) {
unsigned long thresh;
if (se_is_idle(se))
thresh = sysctl_sched_min_granularity;
else
thresh = sysctl_sched_latency;
/*
* Halve their sleep time's effect, to allow
* for a gentler effect of sleepers:
*/
if (sched_feat(GENTLE_FAIR_SLEEPERS))
thresh >>= 1;
vruntime -= thresh;
}
```
如果不是新任務的話，也就是剛醒來的任務，睡眠期間任務沒有執行，`vruntime` 不會增加，但同時其他任務的 `vruntime` 會持續增加。如果希望剛醒來的任務可以盡快被排程，可以透過減少 `vruntime` 讓睡眠任務有機會較早被排程，因此額外又引入 thresh 來給這些任務一些補償。
thresh 選擇：
* 一般任務：使用 `sysctl_sched_latency`（6ms）
* idle 任務：使用 `sysctl_sched_min_granularity`（0.75ms）
idle 任務獲得較少的補償，因為它們優先級較低
```c
if (entity_is_long_sleeper(se))
se->vruntime = vruntime;
else
se->vruntime = max_vruntime(se->vruntime, vruntime);
```
* Long Sleeper：
長時間睡眠的任務可能已經遠遠落後，直接使用計算出的新 vruntime
* Short Sleeper：
取最大值：`se->vruntime = max_vruntime(se->vruntime, vruntime)`，防止 `vruntime` 倒退太多，確保任務不會獲得過多的優勢
#### 觀察 CFS 的 `place_entity` 呼叫點
* `initial` 為 0：
```c
enqueue_entity() {
...
// 只在任務從睡眠狀態喚醒的情況下呼叫 place_entity
if (flags & ENQUEUE_WAKEUP)
place_entity(cfs_rq, se, 0);
...
}
```
```c
detach_task_cfs_rq(){
/*
* Fix up our vruntime so that the current sleep doesn't
* cause 'unlimited' sleep bonus.
*/
place_entity(cfs_rq, se, 0);
}
```
* `initial` 為 1：
`task_fork_fair`
#### EEVDF
```c
enqueue_entity() {
...
// 每次都必須呼叫 place_entity 但要區分是否為 curr
/*
* If we're the current task, we must renormalise before calling
* update_curr().
*/
if (curr)
place_entity(cfs_rq, se, flags);
update_curr();
...
/*
* XXX now that the entity has been re-weighted, and it's lag adjusted,
* we can place the entity.
*/
if (!curr)
place_entity(cfs_rq, se, flags);
...
}
```
EEVDF 的 [`place_entity`](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L5203) 函式的主要作用就跟 CFS 的不一樣了。前者是校正一個排程實體 `sched_entity` 在虛擬時間軸上的位置，以 `cfs_rq->min_vruntime` 為基準。
但是在 EEVDF 中，目的是重新計算 EEVDF 演算法所需的時間參數，因此只要是做 enqueue 動作，都必須得做 `place_entity`，不過還是要區分是否為 curr 在不同時機進行。會做的事包括：
* 計算 `vlag`
* 透過計算好的 `vlag` 設定 `vruntime`
* 透過計算好的 `vruntime` 設定 deadline
```c
u64 vslice, vruntime = avg_vruntime(cfs_rq);
```
改為用 `avg_vruntime` 函式計算出加權平均 $V$，然後透過 $v_i = V - vl_i$ 來更新 `vrumtime`。
```c
if (sched_feat(PLACE_LAG) && cfs_rq->nr_queued && se->vlag) {
struct sched_entity *curr = cfs_rq->curr;
unsigned long load;
lag = se->vlag;
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);
}
```
加入一個新的任務後，全局 virtual time $V$ 改變為：
$$V' = V - \frac{w_i vl_i}{W + w_i}$$
表示整體 $V$ 會「下降」一點點，計算新的 $\operatorname{lag}$：
> 那個「下降」不代表變小的意思，取決於 $vl_i$ 是正還是負。
$$vl'_i = vl_i - \frac{w_i vl_i}{W + w_i} = \frac{W vl_i}{W + w_i}$$
可以看到加權平均的分母增加，影響整體平均值，代表新任務加入會稀釋現有的 $\operatorname{lag}$ 值，核心對此的做法是預先膨脹 $\operatorname{lag}$ 值來補償。
給 $vl_i$ 的解決方法：
\begin{align}
(W + w_i) \cdot vl'_i &= W \cdot vl_i \\[0.5em]
vl_i &= \frac{(W + w_i) \cdot vl'_i}{W}
\end{align}
膨脹對應的程式碼：
```c
lag *= load + scale_load_down(se->load.weight);
lag = div_s64(lag, load);
```
從程式碼中可看出，如果 `PLACE_LAG` 被採用，排程器在補償部份就會使用論文的策略 1，若關閉則是使用策略 2。
> * 策略 1：
任務們可以在任何時候加入或離開競爭，無論 $\operatorname{lag}$ 為何。當任務重新加入競爭時，會保留其離開時的 $\operatorname{lag}$，即如果任務在時間 $t$ 離開競爭並在 $t'$ 重新加入，則$\operatorname{lag}(t) = \operatorname{lag}(t')$。
> * 策略 2：
跟策略 1 很像，但主要區別在於任務離開競爭後不保留其 $\operatorname{lag}$，任何（重新）加入競爭的任務 $\operatorname{lag} =0$。這種策略適用於任務事件相互獨立的系統，像是 real-time 系統。
然後根據 $v_i = V - vl_i$ 設定 $v_i$：
```c
se->vruntime = vruntime - lag;
```
* $\operatorname{lag} > 0$：任務落後，需要較小的 vruntime（截止時間比較小->更早被選中）
* $\operatorname{lag} < 0$：任務超前，需要較大的 vruntime（稍後被選中）
最後設定 deadline：
```c
/*
* EEVDF: vd_i = ve_i + r_i/w_i
*/
se->deadline = se->vruntime + vslice;
```
### `cfs_rq->min_vruntime` 的意義演進
我目前的理解是 CFS 和 EEVDF 是一致的，只是在 CFS 中 `cfs_rq->min_vruntime` 會更直接拿來使用，像是參考以下註解中：
```c
/*
* MIGRATION
*
* dequeue
* update_curr()
* update_min_vruntime()
* vruntime -= min_vruntime
*
* enqueue
* update_curr()
* update_min_vruntime()
* vruntime += min_vruntime
*
* this way the vruntime transition between RQs is done when both
* min_vruntime are up-to-date.
*
* WAKEUP (remote)
*
* ->migrate_task_rq_fair() (p->state == TASK_WAKING)
* vruntime -= min_vruntime
*
* enqueue
* update_curr()
* update_min_vruntime()
* vruntime += min_vruntime
*
* this way we don't have the most up-to-date min_vruntime on the originating
* CPU and an up-to-date min_vruntime on the destination CPU.
*/
```
過去在做 migration 的時候，是透過 `cfs_rq->min_vruntime` 的加減來校準，以達到公平的目的。但隨著 EEVDF lag 的引入，migration 透過繼承 lag 的方式來允許 task 以更直接的方式在 queue 之間移動。
> todo place_entity 方式也改變
CFS 基於 `cfs_rq->min_vruntime` 來放
在 EEVDF 中，也不再用 `vruntime` 作為選擇任務的標準，`cfs_rq->min_vruntime` 主要用於計算 $V(t) = \dfrac{\sum w_i(v_i(t)-v_0)}{W} + v_0$ 中的標準化，防止計算溢位。
兩種不同的排程器中，都是作為 scheduler 所維護的 `vruntime` 基準值 ，用來保證 monotonicity。
> todo：閱讀完 group scheduling related paper 後重新理解
## $\operatorname{lag}$ 的計算方式
### 論文
假設任務 $i$ 在時間 $t^i_0$ 變為活躍，並且在整個時間間隔 $[t^i_0,t]$ 內都保持活躍，它在該時間間隔內實際接收到的服務時間是 $s_i(t^i_0, t)$。那麼任務 $i$ 在時間 $t$ 的應該接收到的服務時間與實際接收到的服務時間之間的差值可以用以下公式表示：
$$
\operatorname{lag}_i(t^i_0, t) = S_i(t^i_0, t) - s_i(t^i_0, t)
$$
> 若 $\operatorname{lag}_i > 0$，任務 $i$ 服務滯後；若 $\operatorname{lag}_i < 0$，則服務超前。Lag 是衡量 fairness 的重要指標，並與任務延遲特性密切相關。排程演算法致力於將 lag 控制在小且有界的範圍內。
$$\operatorname{lag}_i(t) = w_i(V(t) - V(e))$$
這裡的 $V(t) - V(e)$ 代表虛擬時間的進展量，但 $w_i × (虛擬時間進展)$ 就會對應到實際時間的服務量。實作上沒有乘上權重。
### 核心
$$lag_i(t) = S_i - s_i = w_i(V(t) - v_i(t))$$
```c
struct sched_entity {
...
s64 vlag;
...
}
```
對應的符號 $vl_i$ 代表任務 $i$ 的 virtual lag。為了避免到處都要乘上 $w_i$，引入 virtual lag：
$$vl_i = V - v_i$$
移項獲得 $v_i$ 的另一個計算方法：
$$v_i = V - vl_i$$
---
[`update_entity_lag`](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L695) 函式是計算並限制 EEVDF 中的一個 `sched_entity` 的 `vlag`
```c
static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
s64 vlag, limit;
SCHED_WARN_ON(!se->on_rq);
vlag = avg_vruntime(cfs_rq) - se->vruntime;
limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);
se->vlag = clamp(vlag, -limit, limit);
}
```
`avg_vruntime` 函式會計算 $V(t) = \dfrac{\sum w_i(v_i(t)-v_0)}{W} + v_0$，也就是每個任務加權後的全局虛擬時間。
已知 $vl_i = V - v_i$，由此計算出 vlag 變數。
論文的界線：
$$-r_{max} < \operatorname{lag}_k(t) < max(r_{max}, q)$$
我目前對程式碼的解讀：
$$-\dfrac{max(2r, q)}{w_i} < \dfrac{\operatorname{lag}_k(t)}{w_i} = vlag < \dfrac{max(2r, q)}{w_i}$$
> 以上省略 `NICE_0_LOAD`
::: info `max_t(u64, 2*se->slice, TICK_NSEC)` 為什麼是這樣？
我可以理解是因為要給 `vlag` 一個上限，就像論文中說明不能讓任務無限落後或是超前。
只是為什麼是 `se->slice` 乘以 2，論文給出的 bound 不是
$-r_{max} < \operatorname{lag}_k(t) < max(r_{max}, q)$ 嗎？
是因為如果時間太短會導致過度的搶佔發生，並且成本很高嗎？
我想問的是這個 2 是怎麼來的，根據實驗或是根據其他理論依據？
這樣還可以說 EEVDF 是公平的嗎？
還是這兩個沒關係 是我過度解讀？
:::
## 任務選擇
> todo
### 論文
### 核心
**資格檢查機制：**[`vruntime_eligible`](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L724) 函式，用來判斷任務是否有資格被排程。
```c
static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
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 >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
}
```
具體來說，是判斷 $lag_i = w_i(V - v_i)$ 是否是非負整數(>=0)，也就是 $V >= v_i$ 是否成立：
$$
V >= v_i \\
$$
$$
-> \frac{\sum_k w_k * (v_k - v_0)}{W} + v_0 >= v_i \\
$$
$$
-> \frac{\sum_k w_k * (v_k - v_0)}{W} >= v_i - v_0 \\
$$
$$
-> \sum_k w_k * (v_k - v_0) >= (v_i - v_0) * W
$$
相當於是在判斷最後一個式子。
`entity_eligible` 函式是 `vruntime_eligible` 的呼叫點之一：
```c
int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
return vruntime_eligible(cfs_rq, se->vruntime);
}
```
::: info
我不懂為什麼不直接呼叫 `vruntime_eligible`，我看核心中有大概十處是呼叫 `entity_eligible`
:::
**任務選擇機制：** [`pick_eevdf`](https://elixir.bootlin.com/linux/v6.14.8/source/kernel/sched/fair.c#L925) 函式。
原本 CFS 的紅黑樹是根據 vruntime 來排序，在後來的 EEVDF 改成用 virtual deadline 來排序。從程式碼的註解可以看出，EEVDF 選擇任務的規則，這部分跟論文的核心概念是一致的：
* 任務必須 eligible（即該任務應該獲得服務）
* 從符合條件的任務中選擇虛擬截止時間最早的那個
函式的輸入是一個 `cfs_rq` 的指標，回傳被選中的 `sched_entity`。
```c
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
```
```c
struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
struct sched_entity *se = __pick_first_entity(cfs_rq);
struct sched_entity *curr = cfs_rq->curr;
struct sched_entity *best = NULL;
```
這個函式很重要所以首先來看變數們：
* `node`：紅黑樹的根節點，用於後續 heap search 階段的逐一走訪
* `se`：樹中最左端的節點，最小虛擬截止時間。
* `curr`：目前正在運行的任務
* `best`：最終選定的最佳任務，作為函式的輸出結果
當只有一個待排程實體時，直接跳過後續的資格檢查，節省計算時間：
```c
if (cfs_rq->nr_queued == 1)
return curr && curr->on_rq ? curr : se;
```
檢查目前運行的實體是否仍然在 runqueue 中且符合排程的條件：
```clike
if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
curr = NULL;
if (sched_feat(RUN_TO_PARITY) && curr && protect_slice(curr))
return curr;
```
> 開啟 `RUN_TO_PARITY` 的話，當下選取的任務會一直被執行到 non-eligible 或者取得一個新的 slice，而不是選擇 deadline 最優先的那個，這主要是因應 EEVDF 在某些情境的測試(wakeup preeption)上發現效能低於 CFS 而引入的機制，詳細可參考 [`RUN_TO_PARITY`](https://lore.kernel.org/lkml/20230816134059.GC982867@hirez.programming.kicks-ass.net/) 討論串
已知 `se` 是樹中最小 deadline 的排程實體，先檢查它是否 eligible，如果是，直接選擇它（最優解 $O(1)$）如果不是，進入 heap search 尋找其他符合條件的實體：
```c
if (se && entity_eligible(cfs_rq, se)) {
best = se;
goto found;
}
```
EEVDF heap search 運作的主要邏輯：
* 左子樹優先：如果左子樹的最小 vruntime 都是 eligible 的，那可以歸納出左子樹中的所有節點都是 eligible 的。由於樹按 virtual deadline 排序，左子樹中的節點有更早的 deadline ，因此可以只搜索左子樹，忽略目前節點和右子樹。
* 目前節點檢查：如果左子樹為空或沒有 eligible 的實體，檢查目前節點
* 右子樹搜索：如果目前節點不符合條件，搜索右子樹
```c
while (node) {
struct rb_node *left = node->rb_left;
if (left && vruntime_eligible(cfs_rq,
__node_2_se(left)->min_vruntime)) {
node = left;
continue;
}
se = __node_2_se(node);
if (entity_eligible(cfs_rq, se)) {
best = se;
break;
}
node = node->rb_right;
}
```
pick_task_fair -> pick_next_entity
## 任務離開、加入競爭以及改變權重 - $\operatorname{lag}$
> 待整理
## 任務離開、加入競爭以及改變權重 - $V(t)$
> todo
### 論文
任務 $j$ 在時間 $t$ 離開競爭：
$$V(t) = V(t) + \dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$
任務 $j$ 在時間 $t$ 加入競爭：
$$V(t) = V(t) - \dfrac{\operatorname{lag}_j(t)}{\sum_{i \in \mathcal{A}(t^+)} w_i}$$
任務 $j$ 在時間 $t$ 把權重從 $w_j$ 改成 $w'_j$：
$$V(t) = V(t) + \dfrac{\operatorname{lag}_j(t)}{(\sum_{i \in \mathcal{A}(t)} w_i) - w_j} - \dfrac{\operatorname{lag}_j(t)}{(\sum_{i \in \mathcal{A}(t)} w_i) - w_j+ w'_j}$$
### 核心
首先定義 `avg_vruntime_add` 以及 `avg_vruntime_sub` 兩個函式，傳入的參數都是 `cfs_rq` 的指標以及目前任務的 `sched_entity` 指標。
這邊操作都是針對 `vruntime` 以及權重的，並不是像論文中的 $\operatorname{lag}$，呼叫這兩種函式會去更新 `cfs_rq` 中的 `avg_vruntime `和 `avg_load`。
```c
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;
}
```
`avg_vruntime_add` 的呼叫點就只有在 `__enqueue_entity` 中，同樣的 `avg_vruntime_sub` 的呼叫點也只出現在 `__dequeue_entity` 函式。
```c
/*
* Enqueue an entity into the rb-tree:
*/
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
avg_vruntime_add(cfs_rq, se);
se->min_vruntime = se->vruntime;
se->min_slice = se->slice;
rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
__entity_less, &min_vruntime_cb);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
&min_vruntime_cb);
avg_vruntime_sub(cfs_rq, se);
}
```
在 `__enqueue_entity` 中除了會更新 `cfs_rq` 中的 `avg_vruntime `和 `avg_load` 參數，也會記錄下此任務被放入紅黑樹時的 `min_vruntime` 和 `min_slice`。
繼續往上追，首先推測最基本的三種情況的行為：
* 任務加入競爭：呼叫 `__enqueue_entity`
* 任務離開競爭：呼叫 `__dequeue_entity`
* 任務改變權重：呼叫 `__dequeue_entity`，再以新的權重呼叫 `__enqueue_entity`，對應到論文
## 待整理
> todo
rb_erase_augmented_cached ...
參考 [issue 276](https://github.com/sysprog21/linux-kernel-scheduler-internals/issues/276)
是否改成 LTS v6.1.140 版本？
Sign in with Wallet
Connect another wallet