# Target latency 相關研究
> 為什麼 EEVDF target latency 相關的 patch 會多次被拒絕
> 你要去了解
> by jserv
https://hackmd.io/@Kuanch/eevdf#Main-Patches-1-of-EEVDF
https://github.com/rsy56640/triviality/tree/master/content/sched-eevdf
## What is target latency ?
### Target Latency 的起源 - CFS
> 80% of CFS’s design can be summed up in a single sentence: CFS basically models an “ideal, precise multi-tasking CPU” on real hardware.
> 節錄自 [linux kernel doc](https://www.kernel.org/doc/html/v6.6/scheduler/sched-design-CFS.html) 很想吐嘈這份官方文件實在是很簡短
關於 target latency 的起源必須要追溯到 CFS。CFS 是為了模擬一種理想狀況：每個可以執行的任務同時在 CPU 上以等比例執行，也就是 perfect multitasking。
但現實中 CPU 一次只能執行一個任務，所以 CFS 必須透過 time slice 來模擬這種並行的效果。Target latency 定義了一個時間長度，在這段時間內每個任務都會獲得執行機會，進而去逼近理想的同時執行效果。長度越小，就越接近理想狀態，但也會帶來更多的 context switch 成本。
以下參考書中 CFS 章節對於 target latency 的說明：
> The target latency, also called the scheduler period. It is the minimum amount of time idealized to an infinitely small duration required for every runnable task to get at least one turn on the processor. Thus, it refers to the period of time in which each task runs once, for at least a fixed amount of time: the minimum granularity. If such a duration could be infinitely small, then each runnable task would have had a turn on the processor during any given timespan, which must be approximated in real world.
整理出以下：
* Target latency = scheduler period
代表理想系統下每個可以執行的任務都有機會在 CPU 上執行一次的最短週期，如果此週期能趨近於 0，那麼在任何時刻都可視為所有任務都在同時執行。
* Minimum Granularity（最小時間粒度）
是每個任務至少可以執行的最小單位時間。當有太多任務時，若平分 target latency，會導致每個任務可執行的時間太短，進而產生 context switch 開銷過高，因此系統限制這個時間不能小於 minimum granularity。
當任務數量增加到一定程度時，系統會優先保證 minimum granularity，這時實際的 scheduler period 會超過 target latency。這部分可以參考以下 `v4.4` 的程式碼：
```c
/*
* The idea is to set a period in which each task runs once.
*
* When there are too many tasks (sched_nr_latency) we have to stretch
* this period because otherwise the slices get too small.
*
* p = (nr <= nl) ? l : l*nr/nl
*/
static u64 __sched_period(unsigned long nr_running)
{
if (unlikely(nr_running > sched_nr_latency))
return nr_running * sysctl_sched_min_granularity;
else
return sysctl_sched_latency;
}
```
```c
extern unsigned int sysctl_sched_latency;
extern unsigned int sysctl_sched_min_granularity;
```
用來計算每個任務被分配到的 time slice。
```
time_slice = target_latency * (task_weight / total_weight)
```
## [Improving scheduler latency](https://lwn.net/Articles/404993/)
Thu Oct 14 2010
> The level of interactive response provided by the kernel's CPU scheduler is the subject of endless discussion and tweaking.
經由剛剛的簡單介紹，已知 CFS 排程器將時間劃分成多個週期，即為 target latency，在每個週期內每個任務都期望可以運行一次。這個週期的長度決定了任何給定任務可以期望等待運行的最大時間量，即最大延遲。在當時預設這個長度是 6ms。
如果有 n 個任務，CFS 就會把這個排程週期切成 n 份給每個任務，但它有一個 minimum granularity，預設是 2ms，所以任務變多時，就只能延長整體週期，導致延遲增加。
低的 latency -> 更頻繁的排程 -> 更快的 response
但也可能會導致 CPU 更忙，context switch 多 -> 系統整體 throughput 降低
可以看出來這個議題本身關於到 latency-sensitive 還有 throughput-sensitive 的 tradeoff，因此在 CFS 漫長的歷史中，這兩個重要的參數也歷經多次的發展和修改，以下是對其中一個具代表性的 patch 的研讀：
### [[RFC patch 1/2] sched: dynamically adapt granularity with nr_running](https://lore.kernel.org/all/20100911174003.051303123@efficios.com/)
> 很推薦去看這個 RFC patch，可以看到開發者小吵架的過程
這個 RFC patch 是由 Mathieu Desnoyers 所提出，主要是關於修改 `sysctl_sched_min_granularity`，Mathieu Desnoyers 提到：
* 如果把它設得太小，排程器就會太頻繁地搶佔任務
* 如果設得太大，當系統中同時執行的任務數變多時，整體的延遲期間就可能變得非常長
他當時提出的解決方式：
把 `sysctl_sched_min_granularity` 從 2ms 降到 750us，並且新增 `sysctl_sched_std_granularity` 代表原本的 2ms，以及 `sched_nr_latency_max`。
* 當系統上執行的任務數很少（最多 3 個）時，使用較大的 `sysctl_sched_std_granularity`，減少不必要的 context switch
* 當執行的任務數超過 3 個時，就動態的縮小 minimum granularity，讓每個任務能在更短時間內輪到執行
* 但這種縮小是有限的，當任務數達到 8 個（這個數字是任意挑的）時，系統就不再繼續縮小 granularity，而是改為拉長整體 latency 週期，這樣可以避免排程器過於頻繁被呼叫。
> My approach try to get lower latencies without sacrificing throughput when there are few threads running, which IMHO is the common case where throughput really matters.
A system running tons of threads should already expect some sort of throughput degradation anyway,so we might as well favor low-latency rather than throughput on those systems running lots of threads.
做法的目標是：在任務數量少的情況下，不犧牲 throughput 的前提下降低延遲。而如果系統已經有大量任務在跑，那它本來就得接受 throughput 會降低，所以在這種情況下，更應該優先考慮延遲表現。
對應新增的 `__sched_gran` 函式，實作出動態的 minimum granularity 計算：
```c
static unsigned int __sched_gran(unsigned long nr_running)
{
unsigned int gran = sysctl_sched_std_granularity;
unsigned long nr_latency = sched_nr_latency;
if (unlikely(nr_running > nr_latency)) {
gran = sysctl_sched_latency;
gran /= nr_running;
gran = max(gran, sysctl_sched_min_granularity);
}
return gran;
}
```
`__sched_period` 函式基於 `sched_nr_latency_max` 的改動：
```diff
static u64 __sched_period(unsigned long nr_running)
{
+ unsigned long nr_latency_max = sched_nr_latency_max;
u64 period = sysctl_sched_latency;
- unsigned long nr_latency = sched_nr_latency;
- if (unlikely(nr_running > nr_latency)) {
+ if (unlikely(nr_running > nr_latency_max)) {
period = sysctl_sched_min_granularity;
period *= nr_running;
}
-
return period;
}
```
Mathieu Desnoyers 的實驗結果是
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Peter Zijlstra](https://lore.kernel.org/all/1284231470.2251.52.camel@laptop/)
在閱讀這個 patch 會發現 Peter Zijlstra 的蹤影，這位就是在 2023 年首次提交 EEVDF 相關 patch 的最主要的貢獻者。他當時直接對 Mathieu Desnoyers 所提出的解決方式作出反駁和批評：
> Its not at all clear what or why you're doing what exactly.
> Not at all charmed, this look like random changes without conceptual
integrity.
他主要在批評 `__sched_gran` 函式的做法：
> Now you introduce a separate preemption measure, sched_gran as:
>
> sched_gran := {
> sched_std_granularity; nr_running <= 8
max(sched_min_granularity, sched_latency / nr_running)
>
>Which doesn't make any sense at all, because it will either be larger or as large as the current sched_min_granularity.
這個函式的回傳值不是大於就是等於原本的 `sched_min_granularity`，多此一舉。
:::info
看了 Peter 的反駁，他好像打錯了
`__sched_gran` 函式跟 `sched_nr_latency_max`，也就是他說到的 8 並沒有關係， Peter 想說的應該是 3 吧？
:::
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Linus Torvalds](https://lore.kernel.org/all/AANLkTin0LOuTOcJPiZcZGeZMdqsy2dohyrREw2GGhddJ@mail.gmail.com/)
Linus Torvalds 對於 Peter Zijlstra 批評的回覆：
> I wish people actually looked at the _numbers_ and reacted to them,
rather than argue theory.
Guys, we have cases of bad latency under load. That's a pretty
undeniable fact. Arguing against a patch because of some theoretical
issue without at all even acknowledging the latency improvements is, I
think, really bad form.
So please. Acknowledge the latency issue. And come up with better
patches, rather than just shoot down alternatives.
任何帶來實質改善的 patch 都值得被認真對待：）
在後續的信件中，還可以看出 Linus 本人的立場是非常非常重視 CPU 排程器 latency 相關的問題：
> But latency really _is_ important. And it's often overlooked, because few benchmarks actually test it.
> And I don't like how you dismissed the measured latency improvement. And yes, I do think latency matters. A _lot_.
也可能因此後續排程器的演進時常是為了 latency 相關的考量。
### 延伸出的 START_DEBIT 問題
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Mathieu Desnoyers](https://lore.kernel.org/all/20100913201913.GC28294@Krystal/)
在開發者們討論的過程中，對於 wakeup‑latency 測試數據的對比，發現 `START_DEBIT` 會導致 latency 翻倍。
> This is because SIGEV_THREAD creates a new thread each time the timer fires, and newly created tasks are put at the end of the runqueue with START_DEBIT.
`START_DEBIT` 是 CFS 中用來控制新建立任務在 runqueue 中初始位置（透過`place_entity` 函式）的方式。這些新任務的 `vruntime` 會被設為目前 `min_vruntime` 加上一筆債務，也就是說新任務會被放到 runqueue 的最右邊（`vruntime` 最大），藉此避免它一產生就去搶走原本還沒跑完的任務的 CPU 時段。這種策略本意是為了公平性，防止大量的 fork 造成 starvation。
對應的 `v4.4` 程式碼：
```c
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
u64 vruntime = cfs_rq->min_vruntime;
...
if (initial && sched_feat(START_DEBIT))
vruntime += sched_vslice(cfs_rq, se);
...
```
但這種方法也會導致如果有大量新 thread（例如 `SIGEV_THREAD`）被產生，這些 thread 幾乎無法被及時執行。在像 POSIX timer 這種以 `SIGEV_THREAD` 實作的情況中，每次 timer 到點都會產生一個新 thread，這些 thread 因 `START_DEBIT` 被嚴重 delay，造成極高 latency。
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Peter Zijlstra](https://lore.kernel.org/all/1284366936.2275.27.camel@laptop/)
> Like maybe re-inventing O(1)'s fork penalty + return on exit instead of START_DEBIT penalizing the child? Child of lagging parent needs to run NOW, just as any other lagging task wakeup, but fork/clone dare not be an advantage.
這個回覆主要是 Peter Zijlstra 提出對於以上問題的改動，也就是不要用到 `START_DEBIT` 的機制來逞罰子任務。Peter 的方法是在 `cfs_rq` 中新增兩個欄位：
```diff
struct cfs_rq {
struct load_weight load;
unsigned long nr_running;
+ s64 avg_vruntime;
+ u64 avg_load;
+
```
```diff
+/*
+ * Compute virtual time from the per-task service numbers:
+ *
+ * Fair schedulers conserve lag: \Sum lag_i = 0
+ *
+ * lag_i = S_i - s_i = w_i * (V - v_i)
+ *
+ * \Sum lag_i = 0 -> \Sum w_i * (V - v_i) = V * \Sum w_i - \Sum w_i * v_i = 0
+ *
+ * From which we solve V:
+ *
+ * \Sum v_i * w_i
+ * V = --------------
+ * \Sum w_i
+ *
+ * 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 - v) + v
+ *
+ * \Sum ((v_i - v) + v) * w_i \Sum (v_i - v) * w_i
+ * V = -------------------------- = -------------------- + v
+ * \Sum w_i \Sum w_i
+ *
+ * min_vruntime = v
+ * avg_vruntime = \Sum (v_i - v) * w_i
+ * cfs_rq->load = \Sum w_i
```
從這段註解可以看出，當時 Peter 就提出了全局虛擬時間還有 lag 的概念了，並且假設系統中所有可執行任務的 lag（落後量）加總為零。
* `min_vruntime`：
`min_vruntime` 在 CFS 中，這個值代表公平性的 baseline，用來計算新的任務該從哪裡開始（新任務不該比目前任何任務的 `vruntime` 還低，否則會立即被執行）。
在 Peter 提出的版本中，`min_vruntime` 是選定的基準虛擬時間，藉此讓所有其他任務的 `vruntime` 都變成相對值，避免大數溢位。
* `avg_vruntime`：runqueue 中所有任務相對於 `min_vruntime` 的虛擬時間乘上權重的加總。這裡就會把每個任務的落後程度考慮進去。
* `avg_load`：加總了所有可執行任務的 `se->load.weight`。
新增函式 `avg_vruntime`：
```diff
+static u64 avg_vruntime(struct cfs_rq *cfs_rq)
+{
+ struct sched_entity *se = cfs_rq->curr;
+ s64 lag = cfs_rq->avg_vruntime;
+ long load = cfs_rq->avg_load;
+
+ if (se) {
+ lag += entity_key(cfs_rq, se) * se->load.weight;
+ load += se->load.weight;
+ }
+ if (load)
+ lag = div_s64(lag, load);
+
+ return cfs_rq->min_vruntime + lag;
+}
+
```
透過此函式計算出 `V = min_vruntime + lag / load` ，代表要插入新任務的 `vruntime`，讓它從整體的加權平均虛擬時間開始。以下 `place_entity` 也要有相對的改動：
```diff
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
- u64 vruntime = cfs_rq->min_vruntime;
-
- if (initial && sched_feat(START_DEBIT))
- vruntime += sched_vslice(cfs_rq, se);
+ u64 vruntime = avg_vruntime(cfs_rq);
```
用一種公平但不會過度懲罰新任務的方法來初始化 `vruntime`，讓子任務不會一開始就極端延遲。
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Mike Galbraith](https://lore.kernel.org/all/1284371457.14888.9.camel@marge.simson.net/)
繼續看下去就會再次很驚訝的發現原來在 2010 年 deadline 的詞就有被提出過了：
> Yeah, pretty much has to be fair_sleepers holding others off for too long. (A shiny new preemption model is about the only thing that can make that go away) Perhaps lag should be negated if you've received a reasonable chunk or something.. but what we really want is a service
deadline.
在 CFS 中，sleep 過後醒來的任務會有較小的 `vruntime`，因為應該要公平的讓它儘快補上沒跑的時間，所以醒來的任務可能會立即得到 CPU。但這會導致如果某些 thread 持續 sleep/wakeup，它們會頻繁佔用 CPU，而新任務或其他任務反而一直被跑不到。Mike Galbraith 認為真正需要的是一個 service deadline 機制。
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Peter Zijlstra](https://lore.kernel.org/all/1284371756.2275.108.camel@laptop/)
於是針對 Mike 的建議 Peter 繼續發出改動，以下只節錄少少部分，可以看到是基於 EEVDF：
```diff
+/*
+ * Earliest Eligible Virtual Deadline First
+ *
+ * In order to provide latency guarantees for different request sizes
+ * EEVDF selects the best runnable task from two criteria:
+ *
+ * 1) the task must be eligible (must be owed service)
+ *
+ * 2) from those tasks that meet 1), we select the one
+ * with the earliest virtual deadline.
```
然後也是使用 augmented 紅黑樹，樹的每個節點維護其子樹中最小虛擬截止時間。
#### [Re: [RFC patch 1/2] sched: dynamically adapt granularity with nr_running - Peter Zijlstra](https://lore.kernel.org/all/1284378235.2275.227.camel@laptop/)
> I just realized, this doesn't do what we wanted.. the virtual deadline stuff is handy when you've got tasks with different QoS, but we don't have that, they're all the same due to our task model.
What we want is real deadlines, the patch provides the infrastructure, let me frob something for that.
Peter 想透過 virtual deadline 機制，讓排程器能更準確的安排任務優先順序，並讓新任務能插入在公平的位置，而不是被 `START_DEBIT` 強制加債。這個想法來自類似 EEVDF 排程概念中的 virtual deadline，每個任務根據自己的服務需求計算出下一次 deadline。
過程中他也意識到這個方式的問題：
當每個任務有不同的服務需求和權重，才需要使用 virtual deadline 去排序誰比較急。但當時他們測試的任務模型中所有任務的權重相同，沒有指定不同的 QoS。這會導致每個任務的虛擬 deadline 算出來幾乎一樣，排程器的排序時無法產生有效的差異。
:::info
尚未理解為什麼此測試情境會不符合 Qos，是因為只是關於新的執行序創建嗎，新創建的執行緒預設會繼承親代任務的權重？
:::
#### 未收錄原因
> Much sadness in that tracking that costs a u64 mult per enqueu/dequeue and using it adds a s64 div.
根據以上 Peter 的話，目前猜測其中一個原因是因為開銷太大：會有許多 64 位元的乘法除法運算。
---
看到這裡，如果對於目前 EEVDF 的核心原始碼多少有點印象，就會發現原來早在 2010 年就對後來 CFS 到 EEVDF 的轉變有跡可循了。從 [GPS、WFQ 相關的論文](https://hackmd.io/@salmonii/HJSvKVOlle)可以知道早在 1993 年的網路領域 Fair Queueing 理論中，lag 概念就已經出現。CFS 雖然很大一部分是借鑑於 Fair Queueing 理論，但是他一直沒有去處理全局的 lag 控制，`vruntime` 只記錄了任務自己的進度，不管整體的平均進度，而且在處理新任務的時後還是用粗糙的 `START_DEBIT` 方法。
不過以上的改動在最終並未被收錄，`avg_vruntime` 的概念也是在 v6.6 才正式收錄進去 linux 核心。Linux CPU 排程器也從一個 heuristic 的公平模型，正式進入 service-driven 與理論基礎的時代。
2010 時的 patch 中，Peter（也就未來正式把 EEVDF 拉近核心的主要開發者）明確使用了 lag conservation 還有 deadline 原理，而這是有經過理論證明的。那為什麼中間會是這麼漫長的 13 年才有 CFS 到 EEVDF 的過渡？
## Latency-Nice（2019-2022）
開發者們試圖讓 CPU 排程器變得更為 latency-sensitive，除了透過上述介紹到的對於 target latency 相關的參數修改，在這 13 年間，還出現了關於 `latency-nice` 的討論。
`latency-nice` 的概念最早在 2019 年被提出，後續的演進過程中，其代表的意義也更迭為不盡相同了。
### [[RFC PATCH 0/9] Task latency-nice](https://lwn.net/ml/linux-kernel/20190830174944.21741-1-subhra.mazumdar@oracle.com/)
這個 patch 是在 Linux 核心的 CFS 中加入一個名為 `latency-nice` 的新功能，目的是控制排程器在尋找閒置 CPU 時的搜尋範圍，以平衡延遲和搜尋的成本。
> Introduce new per task property latency-nice for controlling scalability in scheduler idle CPU search path. Valid latency-nice values are from 1 to 100 indicating 1% to 100% search of the LLC domain in select_idle_cpu. New CPU cgroup file cpu.latency-nice is added as an interface to set and get. All tasks in the same cgroup share the same latency-nice value. Using a lower latency-nice value can help latency intolerant tasks e.g very short running OLTP threads where full LLC search cost can be significant compared to run time of the threads. The default latency-nice value is 5.
Subhra Mazumdar 發現在大型系統上，排程器的 idle CPU 搜索過程本身就成為了效能的瓶頸。當一個任務醒來需要找到空閒 CPU 時，`select_idle_cpu` 函式會在整個 LLC（Last Level Cache）中搜尋可用的處理器。對於像 OLTP（Online Transaction Processing）的工作負載，一個任務的執行時間可能非常短，有時只有幾微秒到幾毫秒。在這種情況下，如果排程器花費的搜尋時間與任務實際運行時間一樣甚至更長，就會產生巨大的效能損失。當時首先提出的 `latency-nice` 採用了百分比的概念，從 1% 到 100% 控制搜索範圍。
可以看到這又是另外一個關於 CPU 排程器 latency-sensitive 和 throughput-sensitive 的 tradeoff 問題了。更徹底的搜尋可能找到更理想的 CPU 放置位置，從而獲得更好的整體 throughput，但代價是增加了任務開始執行的延遲。對於延遲敏感的任務，寧可接受不好一點的 CPU 選擇，也要確保任務能夠快速開始執行。核心排程器悠久的歷史中常常圍繞的這個議題在展開而前進。
2019 年時 Subhra Mazumdar 首先使用了 `latency-nice` 這個名稱，作為控制 `select_idle_cpu` 函式搜索 LLC domain 範圍的大小。繼續查看此 patch 後續的討論會發現，`latency-nice` 後面演變為跟搶占行為和排程優先權相關的意涵，也就是更廣為人知的延遲控制概念。
#### [Re: [RFC PATCH 1/9] sched,cgroup: Add interface for latency-nice - Patrick Bellasi](https://lwn.net/ml/linux-kernel/87r24v2i14.fsf@arm.com/)
> I'm sure there will be discussion about some of these features, that's why it's important in the proposal presentation to keep a well defined distinction among the "mechanisms and API" and how we use the new concept to "bias" some scheduler policies.
從這個討論開始，開發者們已經在思考 `latency-nice` 超越原本搜尋控制的用途，像是影響 wakeup 行為和影響 load balance 決策等等。
> Regarding the range for the latency-nice values, I guess we have two options:
> - [-20..19], which makes it similar to priorities downside: we quite likely end up with a kernel space representation which does not match the user-space one, e.g. look at task_struct::prio.
> - [0..1024], which makes it more similar to a "percentage"
`latency-nice` 應該成為更通用的排程機制，但當時還沒有關於範圍應該是什麼以及具體功能實作的共識。
#### [Re: [RFC PATCH 1/9] sched,cgroup: Add interface for latency-nice - Peter Zijlstra](https://lwn.net/ml/linux-kernel/20190905104616.GD2332@hirez.programming.kicks-ass.net/)
對於新提出的 `latency-nice`，Peter 也是非常活躍的在參與討論，雖然大多時候都是站在不贊同的立場。
> I really feel that if we call it nice, it should be like nice. Otherwise we should call it latency-bias and not have the association with nice to confuse people.
語意混淆問題
> Secondly; the default should be in the middle of the range. Naturally this would be a signed range like nice [-(x+1),x] for some x. but if you want [0,1024], then the default really should be 512, but personally I like 0 better as a default, in which case we need negative numbers.
>
> This is important because we want to be able to bias towards less importance to (tail) latency as well as more importantance to (tail) latency.
在這個回覆，Peter 指出 Oracle 和 Facebook 的需求正好相反：
* Oracle 的需求：犧牲一些延遲來換取吞吐量
* Facebook 的需求：犧牲一些吞吐量來換取延遲
他也因此強調需要負數範圍，像是 Oracle 希望降低搶占的頻率，寧可等待也要避免頻繁的 context switch，這就需要正數的 `latency-nice` 值來表示任務可以等待不急著執行。這種大公司之間需求的分歧也讓設計一個統一的 interface 變得困難。
:::info
這概念跟 EEVDF lag 挺像的？
:::
#### [Re: [RFC PATCH 1/9] sched,cgroup: Add interface for latency-nice - Peter Zijlstra](https://lwn.net/ml/linux-kernel/20190905114709.GM2349@hirez.programming.kicks-ass.net/)
在此回覆更清楚看到 Peter Zijlstra 對於 Patrick Bellasi 所提出 `latency-nice` 對 CPU 排程器行為的影響，所持有的態度和看法，尤其是最後一句：
> Placing relative and absolute behaviour on the same scale is going to be
'fun' :-)
所謂相對行為指的是排程器只需知道某個任務 A 比另一個任務 B 更需要快速響應，而不需知道具體的時限，這是目前 CFS 所支援的模式，即以公平為基礎，考慮任務之間的相對優先程度。而絕對行為則要求排程器理解並滿足具體的時間需求，例如任務 A 必須在 10 毫秒內被執行，否則就會違反服務品質或造成錯誤。Peter 所擔憂的是當核心試圖用一個單一的數值 `latency-nice` 來同時描述這兩種本質不同的需求時，會造成語意上的混淆與排程邏輯的不穩定，甚至讓整體行為變得難以預測與調整。
另外，Peter 的回應也說明了 CFS 中的一些限制，包括為了追求執行效率而簡化公平性的邏ㄒ輯，導致理論上的正確性有所犧牲。
#### 未收錄原因
這個關於最初的 `latency-nice` 概念的 RFC patch 最後也是不了了之，除了最初的控制搜尋範圍實作版本因為選定的預設值過於隨機而被駁回，以及遭到 Peter 的反對之外，後續延伸出而涉及的討論範圍也相當的廣泛，像是有包括 Energy-Aware-Scheduling (EAS) 用更多的能耗以換取更短的 latency 等等。
目前猜測除了上述提及的原因，另一個是因為涉及的議題太廣泛，開發者們也沒有取的共識
### [2020 OSPM](https://lwn.net/Articles/820659/)
到了 2020 OSPM 高峰會，Parth Shah, Chris Hyser, and Dietmar Eggemann 等人延續了 2019 年的討論，聚焦在 Linux 核心中的提案 `latency-nice` 參數
[2020 年被擱置的 Parth Shah 版本](https://lore.kernel.org/lkml/20200228090755.22829-1-parth@linux.ibm.com/)
[Latency_nice：Implementation and Use-case for Scheduler Optimization](https://static.lwn.net/images/conf/2020/ospm/latency-nice-slides.pdf)
> todo
### [[PATCH v12 0/8] Add latency priority for CFS class](https://lore.kernel.org/lkml/20230224093454.956298-1-vincent.guittot@linaro.org/)
2020 之後 `latency-nice` 相關的 patch 跟討論後來都被擱置了，2022 年 Vincent Guittot 重啟了這個專案，並且在 2023 二月完成最終版 v12，`latency-nice` 的具體功用也在這個不斷迭代的 patch 中臻至明確。
但這個 patch 的結果是也沒被收錄，EEVDF 也在緊接著的三月被 Peter 再次提出，不過這些也都是後話了。
---
原本方式的限制是：
* `nice`：調整的是任務得到多少 CPU 時間，但不保證什麼時候能拿到 CPU。
* RT priority：能保證快速執行，尤其在開啟 `PREEMPT_RT` 的情況下。但也可能造成某些任務壟斷 CPU。
#### 什麼是 `latency-nice`？
是一個新的延遲友善度設定，用來幫助對延遲敏感的任務更快取得 CPU。並且整合在 CFS 中，不需使用 real-time 排程。和 `nice` 類似，是一個範圍為 -20（最高優先）~ +19（最低優先） 的整數。不會改變能用的 CPU 時間總量（這點不像 `nice` 值），改變的是什麼時候能開始執行，即延遲行為。
#### 核心行為上的改變
當一個被阻塞的任務醒來（如 I/O 完成）時，如果它的 `latency-nice` 優先於正在執行的任務，而且它還有可用的 time slice（尚未用完的 CPU 配額），那麼它可以搶先執行，搶下 CPU（preempt），只是它不會因此獲得更多 CPU，只是更快開始用它應得的時間。
`latency-nice` 高（例如 +19）的任務，不會去打斷其他任務。它會被安排在最後用完自己的時間，這樣不會拖慢對延遲敏感的任務，也會減少 context switch 發生次數。
#### [[PATCH v12 1/8] sched/fair: fix unfairness at wakeup](https://lore.kernel.org/lkml/20230224093454.956298-2-vincent.guittot@linaro.org/)
當一個任務睡眠很久後被喚醒，它的 `vruntime` 會落後其他任務太多。如果不加限制，它會瞬間變得極高優先權。CFS 為了避免這種現象，會限制 `vruntime` 最多只能比 `min_vruntime` 小 `sched_latency`。但這樣會有其他問題，如果 `wakeup_gran()`（喚醒後搶佔容忍度）比 `sched_latency` 還大，那麼這個剛醒來的任務可能就無法成功搶占 curr，而導致自己必須等到下一個 tick 才有機會被執行。
`wakeup_preempt_entity` 函式修改：
```diff
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
s64 gran, vdiff = curr->vruntime - se->vruntime;
if (vdiff <= 0)
return -1;
gran = wakeup_gran(se);
+
+ /*
+ * At wake up, the vruntime of a task is capped to not be older than
+ * a sched_latency period compared to min_vruntime. This prevents long
+ * sleeping task to get unlimited credit at wakeup. Such waking up task
+ * has to preempt current in order to not lose its share of CPU
+ * bandwidth but wakeup_gran() can become higher than scheduling period
+ * for low priority task. Make sure that long sleeping task will get a
+ * chance to preempt current.
+ */
+ gran = min_t(s64, gran, get_latency_max());
if (vdiff > gran)
return 1;
```
加入一個邏輯，將 gran（搶占容忍值）限制為最大不能大於 `get_latency_max` 函式的回傳值：
```diff
+static inline unsigned long get_latency_max(void)
+{
+ unsigned long thresh = get_sleep_latency(false);
+
+ /*
+ * If the waking task failed to preempt current it could to wait up to
+ * sysctl_sched_min_granularity before preempting it during next tick.
+ */
+ thresh -= sysctl_sched_min_granularity;
+
+ return thresh;
+}
```
```
thresh = sysctl_sched_latency - sysctl_sched_min_granularity
```
確保一個長時間睡眠後喚醒的任務 `se`，如果它的 `vruntime` 已經被 capped（最多早於 `min_vruntime` 一個 `sched_latency`），就一定能成功搶佔，因為 `vdiff ≈ sched_latency`，而 `gran ≤ sched_latency - min_granularity`。
#### [[PATCH v12 2/8] sched: Introduce latency-nice as a per-task attribute](https://lore.kernel.org/lkml/20230224093454.956298-3-vincent.guittot@linaro.org/)
在 `task_struct` 結構體中添加 `latency_nice` 欄位
```diff
struct task_struct {
int static_prio;
int normal_prio;
unsigned int rt_priority;
+ int latency_nice;
```
延遲優先級範圍是 -20 到 +19（類似於 `nice`），設定預設值是`DEFAULT_LATENCY_NICE (0)`
#### [[PATCH v12 3/8] sched/core: Propagate parent task's latency requirements to the child task](https://lore.kernel.org/lkml/20230224093454.956298-4-vincent.guittot@linaro.org/)
```diff
int sched_fork(unsigned long clone_flags, struct task_struct *p)
p->prio = p->normal_prio = p->static_prio;
set_load_weight(p, false);
+ p->latency_nice = DEFAULT_LATENCY_NICE;
```
當親代任務被設定了 clone_flags 中的 `CLONE_RESET_ON_FORK`，就會重設子任務的 `latency_nice` 為預設值。如果沒有設 `CLONE_RESET_ON_FORK`，子任務就會繼承親代任務的 `latency_nice` 值。
初始化 `init_task` 的 `latency_nice`：
```diff
struct task_struct init_task
.prio = MAX_PRIO - 20,
.static_prio = MAX_PRIO - 20,
.normal_prio = MAX_PRIO - 20,
+ .latency_nice = DEFAULT_LATENCY_NICE,
```
#### [[PATCH v12 4/8] sched: Allow sched_{get,set}attr to change latency_nice of the task](https://lore.kernel.org/lkml/20230224093454.956298-5-vincent.guittot@linaro.org/)
```diff
+#define SCHED_FLAG_LATENCY_NICE 0x80
```
加入 `sched_attr.sched_flags` 的一個新選項，表示有設定 `latency_nice`。
```diff
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;
};
```
讓使用者可以透過 `sched_setattr` 和 `sched_getattr` 系統呼叫來指定單一任務對 latency 的敏感程度。
#### [[PATCH v12 5/8] sched/fair: Take into account latency priority at wakeup](https://lore.kernel.org/lkml/20230224093454.956298-6-vincent.guittot@linaro.org/)
```diff
struct task_struct {
int static_prio;
int normal_prio;
unsigned int rt_priority;
- int latency_nice;
+ int latency_prio;
```
舊有的 `latency_nice` 被替換為 `latency_prio`。`latency_nice` 會作為 user interface 的值， [-20, 19] 對照到核心內部值 `latency_prio` 會是便池 [0, 39]，中間點為 `DEFAULT_LATENCY_PRIO = 20`。
新增了兩者之間轉換用的巨集：
```diff
+#define NICE_TO_LATENCY(nice) ((nice) + DEFAULT_LATENCY_PRIO)
+#define LATENCY_TO_NICE(prio) ((prio) - DEFAULT_LATENCY_PRIO)
```
每個任務的 `sched_entity` 結構體新增 `latency_offset` ，代表該任務可接受的延遲程度：
```diff
struct sched_entity {
/* cached value of my_q->h_nr_running */
unsigned long runnable_weight;
#endif
+ /* preemption offset in ns */
+ long latency_offset;
```
`latency_offset` 由 `calc_latency_offset` 函式計算：
```diff
+/*
+ * Calculate the latency offset for a priority level.
+ * We use a linear mapping of the priority in the range:
+ * [-sysctl_sched_latency:sysctl_sched_latency]
+ */
+static inline long calc_latency_offset(int prio)
+{
+ return (long)get_sleep_latency(false) * LATENCY_TO_NICE(prio) /
+ (LATENCY_NICE_WIDTH/2);
+}
```
可以看出 `latency_offset` 是由 `latency_nice` 推導出來的，代表任務可以容忍多少延遲。如果任務對延遲較為敏感，則其 `latency_offset` 較小甚至為負。另外會控制 `latency_offset` 的大小在正負 `sysctl_sched_latency` 之間。
改動 `wakeup_preempt_entity` 函式，修改搶佔邏輯：
```diff
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
s64 gran, vdiff = curr->vruntime - se->vruntime;
+ s64 offset = wakeup_latency_gran(curr, se);
- if (vdiff <= 0)
+ if (vdiff < offset)
return -1;
- gran = wakeup_gran(se);
+ gran = offset + wakeup_gran(se);
gran = min_t(s64, gran, get_latency_max());
if (vdiff > gran)
return 1;
```
可以看到原本的方式是若如果新來的 `se` 比目前正在執行的 `curr` 有較小的 `vruntime`，且差距大於一定 gran，則允許搶占。而新的方式考慮進去對於延遲的敏感度，也就是 `latency_offset`。
新增的 `wakeup_latency_gran` 函式會根據兩個任務的 `latency_offset` 差值，動態調整搶占的門檻。
```diff
+static long wakeup_latency_gran(struct sched_entity *curr, struct sched_entity *se)
+{
+ long latency_offset = se->latency_offset;
+
+ /*
+ * A negative latency offset means that the sched_entity has latency
+ * requirement that needs to be evaluated versus other entity.
+ * Otherwise, use the latency weight to evaluate how much scheduling
+ * delay is acceptable by se.
+ */
+ if ((latency_offset < 0) || (curr->latency_offset < 0))
+ latency_offset -= curr->latency_offset;
+ latency_offset = min_t(long, latency_offset, get_latency_max());
+
+ return latency_offset;
+}
```
假設目前執行任務 A 的`latency_offset` = +3ms (延遲不敏感)，喚醒任務 B 的`latency_offset` = -2ms (延遲敏感)。計算出`offset = -2ms - 3ms = -5ms` -> 搶占可以發生的條件會是 `vdiff < -5ms`。
這代表即使任務 B 的 `vruntime` 比任務 A 大 5ms，B 仍然可以搶占 A，因為 B 對延遲更敏感。
`latency_offset` 讓排程器能夠知道哪些任務需要快速回應，在保證公平性的同時，也考慮了不同任務的需求。
#### [PATCH v12 6/8] sched/fair: Add sched group latency support
#### [PATCH v12 7/8] sched/core: Support latency priority with sched core
#### [[PATCH v12 8/8] sched/fair: Add latency list](https://lore.kernel.org/lkml/20230224093454.956298-9-vincent.guittot@linaro.org/)
增加一個新的 latency 紅黑樹來幫助排程 latency-sensitive 的任務，補足目前 CFS 排程器在某些 corner case 下對延遲敏感任務處理不夠即時的問題。像是 CFS 會在 wakeup 時利用 `wakeup_preempt_entity` 函式嘗試搶占正在執行的任務，但這樣的搶占判斷可能會失敗，導致對延遲敏感的任務無法立刻獲得 CPU。此外，即使對延遲敏感的任務被排進 runqueue，它也可能因為 `vruntime` 不夠小，在下一次排程時輸給其他 non-latency-sensitive 任務。
這個 patch 會讓這種 latency-sensitive 任務被放進 latency tree，在下一次排程時再給它一次機會先被選中。
```diff
struct sched_entity {
/* For load-balancing: */
struct load_weight load;
struct rb_node run_node;
+ struct rb_node latency_node;
```
```diff
struct cfs_rq {
#endif
struct rb_root_cached tasks_timeline;
+ struct rb_root_cached latency_timeline;
```
`__enqueue_latency` 函式：
```diff
+static void __enqueue_latency(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
+{
+
+ /* Only latency sensitive entity can be added to the list */
+ if (se->latency_offset >= 0)
+ return;
+
+ if (!RB_EMPTY_NODE(&se->latency_node))
+ return;
+
+ /*
+ * The entity is always added the latency list at wakeup.
+ * Then, a not waking up entity that is put back in the list after an
+ * execution time less than sysctl_sched_min_granularity, means that
+ * the entity has been preempted by a higher sched class or an entity
+ * with higher latency constraint. In thi case, the entity is also put
+ * back in the latency list so it gets a chance to run 1st during the
+ * next slice.
+ */
+ if (!(flags & ENQUEUE_WAKEUP)) {
+ u64 delta_exec = se->sum_exec_runtime - se->prev_sum_exec_runtime;
+
+ if (delta_exec >= sysctl_sched_min_granularity)
+ return;
+ }
```
如果任務 `se->latency_offset < 0`，代表它是 latency-sensitive，就會在 wakeup 時加入 `latency_timeline`。
如果不是 wakeup，而是搶佔回來，則會檢查上次執行時間是否短於 `sched_min_granularity`，如果是的話代表這次也很短，也會重新加入 `latency_timeline`。
排程時挑選執行任務的方式 `pick_next_entity` 函式也進行改動：
```diff
+ /* Check for latency sensitive entity waiting for running */
+ latency = __pick_first_latency(cfs_rq);
+ if (latency && (latency != se) &&
+ wakeup_preempt_entity(latency, se) < 1)
+ se = latency;
```
如果 latency tree 裡有任務，且比目前候選的 se 更急，就選 latency 的。
:::info
其實看到又是新增 `latency_offset` 又是新增一顆紅黑樹的
就為了處理各種延遲問題
有點治標不治本的感覺
:::
#### 未收錄原因
目前還沒找到關於反駁的討論
> todo
## EEVDF latency-nice to slice-attr
### [[PATCH 00/10] sched: EEVDF using latency-nice ](https://lore.kernel.org/lkml/20230306132521.968182689@infradead.org/T/)
### [[PATCH 00/17] sched: EEVDF using latency-nice](https://lore.kernel.org/lkml/20230328092622.062917921@infradead.org/T/)
在 Vincent 發布 CFS `latency-nice` v12 的 patch 之後過了不到一個月的時間，Peter Zijlstra 就提交了新的演算法 EEVDF 整合 `latency-nice` 的 patch。
> Ever since looking at the latency-nice patches, I've wondered if EEVDF would not make more sense, and I did point Vincent at some older patches I had for that (which is here his augmented rbtree thing comes from).
> Also, since I really dislike the dual tree, I also figured we could dynamically switch between an augmented tree and not
可以在 patch 的討論中看出 Peter 對 `latency-nice` 的看法，他認為 EEVDF 可能是比起 CFS 更好的解決方案。原因包括他不喜歡雙樹的設計，且 EEVDF 也提供了更理論的基礎。
完整 patch 請詳閱[學長筆記](https://hackmd.io/@sysprog/Hka7Kzeap/%2FSyG4t5u1a#PATCH-0615-sched-Commit-to-lag-based-placement)，以下想要聚焦在 EEVDF `latency-nice` 的部分。
---
首先移除 `sysctl_sched_latency` 相關參數：
```diff
-unsigned int sysctl_sched_latency = 6000000ULL;
-static unsigned int normalized_sysctl_sched_latency = 6000000ULL;
```
在 CFS 中，`sysctl_sched_latency` 定義了一個排程周期，在這個周期內所有可運行的任務都應該至少運行一次。但在 EEVDF 中不再需要固定周期概念，因為 EEVDF 使用 deadline 來決定排程順序。任務的排程優先級由其 virtual deadline 決定，而不是在固定時間內的輪轉。
把 `sysctl_sched_min_granularity` 改名為 `sysctl_sched_base_slice`：
```diff
-unsigned int sysctl_sched_min_granularity = 750000ULL;
-static unsigned int normalized_sysctl_sched_min_granularity = 750000ULL;
+unsigned int sysctl_sched_base_slice = 750000ULL;
+static unsigned int normalized_sysctl_sched_base_slice = 750000ULL;
```
CFS 中的 `sysctl_sched_min_granularity` 表示任務能獲得的最小 time slice，用於防止 time slice 過小導致過度的 context switce。
EEVDF 中的 `sysctl_sched_base_slice` 對應論文中的 time quantum 概念，更小的 slice 提供更好的比例分配精度，更大的 slice 減少排程開銷。另外論文中也證明了 service lag 受 time quantum 大小限制。
```diff
struct task_struct {
int static_prio;
int normal_prio;
unsigned int rt_priority;
+ int latency_prio;
```
CFS 主要的問題是只有 weight 這個參數可以控制延遲。而 EEVDF 中則存在其他參數，因此新增了幾個欄位到 `sched_entity` 結構體中：
> EEVDF has two parameters:
> - weight, or time-slope; which is mapped to nice just as before
> - relative deadline; which is related to slice length and mapped to the new latency nice.
```diff
struct sched_entity {
/* For load-balancing: */
struct load_weight load;
struct rb_node run_node;
+ u64 deadline;
+ u64 min_deadline;
+
struct list_head group_node;
unsigned int on_rq;
@@ -556,6 +559,7 @@ struct sched_entity {
u64 vruntime;
u64 prev_sum_exec_runtime;
s64 vlag;
+ u64 slice;
```
> Basically, by setting a smaller slice, the deadline will be earlier and the task will be more eligible and ran earlier.
#### latency-nice（`latency_prio` 的對照）與 `slice` 的關係
改成新增的 `set_latency_prio` 和 `set_latency_fair` 函式來計算 `slice`。
```c
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);
}
```
如同註解所說，論文中的 request length 對應到 `slice`，然後 slice 在實作上是基於 `latency-nice` 來設定。
```c
+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);
}
```
```c
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
```
`latency_prio` 轉換成 `latency_nice` 之後，使用與 `nice` 相同的 `sched_prio_to_weight` 權重對照表查表取得該 prio 對應的 weight。
```c
se->slice = div_u64(base << SCHED_FIXEDPOINT_SHIFT, weight);
```
代表任務 slice 時間的大小會反比於任務權重，在之後計算任務的 virtual deadline 時是根據以下公式：
```
virtual_deadline = virtual_runtime + (time_slice / weight)
```
虛擬截止時間是通過將 time slice 加到符合條件的時間來計算的，具有較短 time slice 的任務擁有更接近的虛擬截止時間，因此會優先執行。
* `latency_prio` 越小，權重越高，slice 越小 → deadline 越早 → latency 越好。
* `latency_prio` 越大，權重越低，slice 越大 → deadline 越晚 → latency 越差。
### [[PATCH 00/15] sched: EEVDF and latency-nice and/or slice-attr](https://lore.kernel.org/lkml/20230531115839.089944915@infradead.org/T/)
不過現今核心中的 EEVDF 並不是使用 `latency-nice` 來決定 slice 長度，`latency-nice` 相關的參數也都被拔掉了。此改動可以從這個 patch 看出端倪，也可以看到開發者對此的討論跟想法。
> The big question is what additional interface to expose; some people have voiced objections to the latency-nice interface, the 'obvious' alternative is to directly expose the slice length as a request/hint.
> As an alternative to the latency-nice interface; allow applications to directly set the request/slice using sched_attr::sched_runtime.
#### [[RFC][PATCH 15/15] sched/eevdf: Use sched_attr::sched_runtime to set request/slice](https://lore.kernel.org/lkml/20230531115839.089944915@infradead.org/T/#m26bd7644677e99b39ea08a87f31a2ab2f608cc63)
讓使用者可以透過 `sched_attr.sched_runtime` 欄位來直接設定任務的 time slice / request length，進而影響排程器如何考慮延遲與服務量。
```diff
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.custom_slice = 1;
+ 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.custom_slice = 0;
+ p->se.slice = sysctl_sched_base_slice;
+ }
+ }
```
只要是 `SCHED_NORMAL` 任務，使用者可以呼叫 `sched_setattr` 設定 `sched_runtime`，kernel 會把它當作這個任務的請求 slice。
用 `sched_attr.sched_runtime` 來設定 slice 比起用 `latency_prio`（`latency-nice`）更符合論文中 request length 的特性：允許請求具有任意長度且不同的應用可以根據自己的需求調整請求長度。
#### [Re: [RFC][PATCH 15/15] sched/eevdf: Use sched_attr::sched_runtime to set request/slice - Vincent Guittot](https://lore.kernel.org/lkml/20230531115839.089944915@infradead.org/T/#m129998711797f315c9bb9ac296e4d329ff2cd1fd)
Vincent Guittot 對 `sched_attr.sched_runtime` 提出的質疑：
> what does this raw time value mean? and how it applies to the scheduling latency of the task...
當使用者設定 `sched_runtime = 1ms` 時，這個值到底代表什麼？
使用者可能預期在 1ms 內被排程，但實際上只是保證在排程週期內執行 1ms。
另外，`SCHED_DEADLINE` 中的 `sched_runtime`：
```c
struct sched_attr {
...
/* SCHED_DEADLINE */
__u64 sched_runtime;
__u64 sched_deadline;
__u64 sched_period;
...
};
```
`sched_runtime` 在 deadline scheduler 中已經代表執行時間限制，如果 EEVDF 重用會造成混淆。
> you will probably end up with everybody setting 0.1ms and expecting 0.1ms latency
使用者可能會濫用最小值，導致過多搶占與錯誤期望。
#### [Re: [RFC][PATCH 15/15] sched/eevdf: Use sched_attr::sched_runtime to set request/slice - Peter Zijlstra](https://lore.kernel.org/lkml/20230531115839.089944915@infradead.org/T/#m2572525a623b14cb5753ccc82b9907401a459c8a)
> Confusing only if you don't know how to look at it; users are confused in general and that's unfixable, nature will always invent a better moron. The best we can do is provide enough clues for someone that does know what he's doing.
Peter 承認 `sched_runtime` 對某些人可能會混淆，但他主張對了解系統的人來說是有價值的的工具。
> By keeping the tasks in the same order, we ensure the max latency is the min latency -- consistency is king.
> Given this is a best effort overcommit scheduling class, we *CANNOT* guarantee actual latency. The best we can offer is consistency (and this is where EEVDF is *much* better than CFS).
CFS 與 EEVDF 同屬於 Linux 的 best-effort scheduling class，也就是預設的非即時排程類別。這代表它們不像 `SCHED_DEADLINE` 等 real-time class，無法保證任務會在某個確定的延遲時間內被排到 CPU 上執行。然而，雖然不能保證絕對的 latency，但可以追求另一種近似即時的特性 -- latency 的 consistency。代表應該要盡力使得每次排程延遲相對穩定，也就是讓最大延遲趨近最小延遲，進而降低 jitter。
EEVDF 被認為是比 CFS 更適合提供 latency consistency 的演算法。CFS 的機制雖然已經引入 `vruntime` 概念來模擬公平性，但在許多任務激烈競爭下，任務實際被排入 CPU 的間隔仍可能出現明顯抖動。
ex.
1. `place_entity` 時的 heuristic 放置任務方法
2. 如果系統中有 bursty 任務，像是短時間內產生大量互搶 CPU 的任務，較低權重的任務獲得 CPU 的時間可能會被無限延期，造成 starvation 以及產生高 jitter。
EEVDF 則進一步使用 `request`（所需執行時間）和 `weight`（任務權重）計算 virtual deadline，較為明確的控制 latency spacing。並且基於理論，提供了 lag 的上下界，讓排程行為更穩定以及可預測。
> Now, notably I used sched_attr::sched_runtime, not _deadline nor _period. Runtime is how long you expect each job-execution to take (WCET and all that) in a periodic or sporadic task model.
另外，slice 是 job-level latency control，語意更直接。如果任務大概每次要跑 1.5ms，直接用 `sched_runtime = 1.5ms` 告訴核心即可。
再次複習 EEVDF 中，virtual deadline 是根據以下公式計算：
```
virtual_deadline = virtual_runtime + (time_slice / weight)
```
EEVDF 是明確使用 `request` 和 `weight` 的模型。借用在上一個連結中 Vincent 的形容，`latency-nice` 是一個 opaque relative latency hint。若使用 `latency_nice` 這種比較模糊的權重值，會讓系統只能間接推論 `time_slice` 長度。因此如果目標是控制排程間隔的一致性與可預測性，EEVDF 配合明確的 slice/request 參數會比使用模糊的 latency hint 更透明。
### [[RFC][PATCH 00/10] sched/fair: Complete EEVDF](https://lore.kernel.org/lkml/20240405102754.435410987@infradead.org/T/)
> I've chosen to use sched_attr::sched_runtime for this over a nice-like value because some workloads actually know their slice length (can be dynamically measured in the same way as for deadline using CLOCK_THREAD_CPUTIME_ID) and using the real request size is much more effective than some relative measure.
Peter 選擇只用 `sched_runtime` 而不是 `latency-nice` 了
>todo
## EEVDF 中 的 target Latency ？
:::info
目前追了 target latency 和 latency-nice 相關的 patch
因此我認為目前書中 EEVDF 的 latency-nice 部分還可以再追溯到 CFS
另外重看 [2024 期末專題](https://www.youtube.com/watch?v=kwYgfkD1dWA)的第一組的說明影片，覺得有些錯誤之處。當中說明到 EEVDF 引入 latency-nice，以及現今 EEVDF 的實作上跟 1995 年論文的差距是因為沒有 latency-nice 的實作。
首先 latency-nice 自 2019 就已提出，後來經過多次迭代才被初期的 EEVDF 所引入。
再來有鑒於 1995 年的論文並沒有明確提及 target latency 以及 latency-nice
且參考 latency-nice 刪去過程的開發者討論，我認為 latency-nice 的消失並不是目前 EEVDF 實作上的缺失。
當然也可能是我在考古過程中有所缺漏
:::
:::info
呈上一部分
不理解為什麼目前的《Demystifying the Linux CPU Scheduler》 EEVDF 章節要如此著重介紹 latency-nice？
:::
Sign in with Wallet
Connect another wallet