# 2025q1 Homework1 (ideas)
contributed by < wurrrrrrrrrr >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 還政於民的 sched_ext 及機器學習如何幫助 CPU 排程
在研讀過[ Linux 核心專題: CPU 排程器](https://hackmd.io/@sysprog/BJdyxvxX0) 後我得知 Linux 排程器的演化，經歷了$O(n)$ $O(1)$ scheduler, CFS 到現在的 EEVDF。CPU 排程器的設計理念在於提供一種普遍適用的策略，以滿足各種不同的應用需求，但有些使用Linux 的公司來說，當他們的平台只涉及特定工作負載時，通用的排程器可能無法滿足他們的特殊需求，所以要是能自訂排程器的行為，將有機會帶來更多好處。
在閱讀過程中我看到了以下這段話：『開發人員探索在 Linux 中引入「可插拔」排程器的可能性』而要支持這向技術的基礎為 eBPF。
eBPF 不僅支持將程式碼動態加載到核心執行，還提供檢查器以減少程式對作業系統核心的損害風險。這樣一來，開發者便可輕鬆撰寫並植入客製化的 CPU 排程器。
在閱讀這篇文章之前，我一直認為一旦設定好 CPU 排程器後，就只能使用該排程方式，然而「可插拔」排程器的概念顛覆了我的想法，但 eBPF 到底是什麼呢？於是我先閱讀了[ eBPF ](https://hackmd.io/@RinHizakura/S1DGq8ebw)在這篇文章中我了解到 eBPF 就是 BPF 的擴充，所以如果要如果了解 eBPF 是什麼的話就必須先了解什麼是 BPF 。
傳統的封包過濾方法，需要先將 kernel 的封包複製進 userspace，再進一步於 userspace 分析封包，然而這個複製的過程 cost 是很高的，直到 [The BSD Packet Filter: A New Architecture for User-level Packet Capture](https://www.tcpdump.org/papers/bpf-usenix93.pdf) 中的 [Berkeley Packet Filter (BPF)](https://en.wikipedia.org/wiki/Berkeley_Packet_Filter)被提出來後，就避免了把無用的封包複製到 userspace 的過程。
從形式上來看，BPF 本質上是一個運行在 kernel 中的虛擬機，允許用戶將特定的過濾邏輯（用戶空間程式）轉換成位元組碼 (Bytecode)，即一種簡化的虛擬指令集，並將其注入內核空間執行。這樣封包篩選過程就在 kernel 內部完成，減少了不必要的數據複製提高了封包處理的性能。
之後 BPF 被擴展至網路以外的領域，而可以被應用在 kernel 效能分析，那便是 **eBPF(extended BPF)** 。
eBPF 基於 BPF 可將使用者定義的程式注入 kernel 中的架構做出了更多改進，而在核心專題所提到檢查器的是 eBPF 有 verifier 機制，在注入程式之前，先進行一系列的檢查，避免注入危險的程序損壞到 kernel。
**sched_ext**
Linux kernel 自 v6.12 開始支援 [sched_ext](https://www.phoronix.com/news/Linux-6.12-Lands-sched-ext)
>Merge tag 'sched_ext-for-6.12' of git://git.kernel.org/pub/scm/linux/kernel/git/tj/sched_ext Pull sched_ext support from Tejun Heo:
"This implements a new scheduler class called ‘ext_sched_class’, or sched_ext, which allows scheduling policies to be implemented as BPF programs.
主要目標包括下列三點：
便於實驗與探索：可快速迭代新的排程策略。
> - Ease of experimentation and exploration: Enabling rapid iteration of new scheduling policies.
客製化：構建應用程式專用的排程器，實作不適用於通用排程器的策略。
> - Customization: Building application-specific schedulers which implement policies that are not applicable to general-purpose schedulers.
快速部署排程器：在生產環境中，無需中斷運行即可更換排程策略。
> - Rapid scheduler deployments: Non-disruptive swap outs of scheduling policies in production environments"
在其中關鍵的下列這個巨集叫做 BPF_STRUCT_OPS ：
```c
#define BPF_STRUCT_OPS(name, args...) \
SEC("struct_ops/"#name) \
BPF_PROG(name, ##args)
```
這個巨集會將函式轉換為 BPF struct_ops（也就是 BPF_PROG_TYPE_STRUCT_OPS 類型的 eBPF program ），BPF struct_ops 是 Kernel 提供的一個方法，讓 Kernel 的子系統能夠使用者定義的函式。
[圖片來源](https://lpc.events/event/17/contributions/1607/attachments/1164/2407/lpc-struct_ops.pdf)
在了解完上述的名詞後就到本次的重點將機器學習引入 cpu 的排程中，在演講中有提到 cpu load balance in linux kernel 當中的一個關鍵的函數為 can_migrate_task()，這個函數最主要的功能為檢查現在挑選出的任務他是不是適合在 cpu 之間做搬遷，如果適合這個函數會回傳 1 ，反之不適合回傳 0 ，而這個專題就是用機器學習來模仿這個函數的行為，於是先去觀看了[ Machine Learning for Load Balancing in the Linux Kernel ](https://hackmd.io/@vax-r/ML_LB#Machine-Learning-for-Load-Balancing-in-the-Linux-Kernel)了解前人所作的貢獻，在這篇文章中我了解到 Linux 核採用的 Completely Fair Scheduler 的排程策略是每次挑選當前 virtual runtime 最小的`sched_entity`來執行，並且盡量平衡每個 CPU 的 utilization 還有 Linux 核心對於每個 CPU 都會配置一個 runqueue `cfs_rq` 來達到更快的 local access ，負載平衡就是在不同的 runqueue 之間進行任務的遷移。排程的單位雖然是 thread ，但並不直接針對 thread 進行排程，而是對 `sched_entity` 。
`cfs_rq`利用 virtual runtime 作為 key ，利用紅黑樹對 `sched_entity`排序，至於為什麼是紅黑樹呢？這是我現在不了解的地方，於是我去閱讀[ Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)知道了紅黑樹其新增、移除、搜尋的時間複雜度均維持在$O(\log{n})$且其重新平衡所需的時間成本較其他平衡樹小，因為排程需要頻繁地插入跟移除節點(任務)所以選用紅黑樹會有較好的表現，比起同樣是$O(\log{n})$的 AVL tree。
`cfs_rq`也擁有自己的`sched_entity`且可以被其他`cfs_rq`排程。
在第二段中提到 CFS 會透過 timer interrupt handler 週期性的呼叫`scheduler_tick()`進行負載平衡，而負責處理負載平衡的程式會以`softirq`的方式運作，那什麼叫做`softirq`呢？於是我去閱讀了[ Introduction to deferred interrupts (Softirq, Tasklets and Workqueues) ](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html)和[ Linux 核心設計: Interrupt](https://hackmd.io/@RinHizakura/B14d-o24v#Softirq)了解到在現代的作業系統中，ISR 會被切成 top half 和 botton half 兩個部份，而Top half 和 botton half 的區分使得系統可以把 interrupt 的處理推遲，在 top half 中，disable interrupt ，做最小而重要的任務後(例如 pending 發生的 interrupt 類型)enable interrupt，如果接著沒有 interrupt 進來，再對 bottom half 去做處理。藉此降低處理 interrupt 產生的 latency。
在 linux 中主要有三種延遲 intterupt 處理的機制:
* softirqs
* tasklets
* workqueues
**Scheduler Domains**
而以下這段話：『sched_domain 當中的 CPU core 又會被分到不同的 sched_group ，負載平衡則是在不同的 groups 之間進行，來確保 group 的 workload 在不同 domain 之間都是平衡的。』
我不理解什麼叫做`sched_domain`，因此我查閱了 [Scheduler Domains](https://docs.kernel.org/scheduler/sched-domains.html) 了解到什麼叫做`scheduling domain`以下為他的解釋：
1. Base Scheduling Domain 與層級結構
* 每個 CPU 都有一個 “base” `scheduling domain` (struct sched_domain)，用來管理該 CPU 的任務調度。
* `scheduling domain`的層級結構是由“base” `scheduling domain`組成，透過 ->parent 指標連接。
* 每個`scheduling domain`可以有一個 `parent scheduling domain`，而這個鏈結必須以 NULL 結束（即最上層的父節點為 NULL） 而這個 parent`scheduling domain`有什麼作用呢？這邊舉個簡單的例子：當`scheduling domain` B 和`scheduling domain` C 內部的負載出現不均時，`parent scheduling domain` A 就會介入，協調這兩個基礎`sched_domain`之間的任務遷移，使得兩個 CPU 的負載更加平衡。
* `scheduling domain`的數據結構是針對每個 CPU 設計的，且更新時不需要鎖（lockless updates），因為每個 CPU 更新的都是自己專用的數據，所以不會出現多個 CPU 同時修改同一份數據的情況。這樣就不需要使用鎖（如互斥鎖）來保護數據的一致性。
下列為第三點的圖示：
```
[`sched_domain` A] (頂層)
↑
->parent = NULL
↑
┌──────┴──────┐
│ │
[`sched_domain` B] [`sched_domain` C]
↑ ↑
└────────────->parent 指向 `sched_domain` A
```
下列為第四點的例子：
假設系統中有兩個 CPU，各自擁有獨立的 `scheduling domain`：
```lua
CPU0 CPU1
┌─────────────────┐ ┌─────────────────┐
│ sched_domain0 │ │ sched_domain1 │
│ load = 10 │ │ load = 8 │
└─────────────────┘ └─────────────────┘
```
當 CPU0 執行 `update_load(2)` 時，CPU0 自己的 load 由 10 變成 12，而 CPU1 的 `scheduling domain` 不會受到任何影響。由於每個 CPU 更新的都是自己專用的數據，所以這個過程中不需要加鎖同步。
2. `scheduling domain`的範圍（span）與其要求
* 每個`scheduling domain`會覆蓋一定數量的 CPU（這個數據存放在 ->span 欄位中）。(通常 ->span 是一個 bitmask，表示哪些 CPU 被納入這個`scheduling domain`中，用於後續的負載均衡決策。)
* 一個域的覆蓋範圍必須是它的子域覆蓋範圍的超集。
* 例子：有一個父域，它的子域分別是 CPU0 和 CPU1 的基礎`sched_domain`。那麼這個父域的覆蓋範圍必須是 {CPU0, CPU1} 或包含這個集合的更大集合，例如 {CPU0, CPU1, CPU2}，但至少要包含 {CPU0, CPU1}。
* CPU i 的“base” `scheduling domain`至少必須包含 CPU i。
* 例如，對於 CPU2，它的“base”`scheduling domain`的覆蓋範圍至少應該包含 CPU2。這保證了每個 CPU 都能夠獨立參與到負載均衡中，而不會出現某個 CPU 被完全排除的情況。
但我要怎麼知道 span 是一個 bitmask 呢？於是我查看了 linux 的原始程式碼找到了相關的敘述。
下列證明 span 是一個 bitmask：
```c
/*
* We add the notion of a root-domain which will be used to define per-domain
* variables. Each exclusive cpuset essentially defines an island domain by
* fully partitioning the member CPUs from any other cpuset. Whenever a new
* exclusive cpuset is created, we also create and attach a new root-domain
* object.
*
*/
struct root_domain {
atomic_t refcount;
atomic_t rto_count;
struct rcu_head rcu;
cpumask_var_t span;
```
首先可以看到在` root_domain `這個結構，那 `root_domain` 這個結構是什麼呢？在 Linux 裡，`root domain`是一種用來管理 CPU 分工的機制。
想像你有一台多核心的電腦（例如 8 顆 CPU），正常情況下，作業系統會自動幫你安排哪些程式（工作負載）應該跑在哪些 CPU 上，確保整體效能最好。
但有時候我們希望把特定的 CPU 分配給特定的任務，不讓它們和其他工作混在一起。這時候我們可以使用 cpuset 來建立「專屬 CPU 區域」，讓某些 CPU 只負責特定的工作。
當我們建立這種「獨占（exclusive）」的 CPU 分組時，Linux 會同時建立一個 `root domain` 來管理這些 CPU，確保：
* 這些 CPU 真的只跑指定的工作，不被其他應用程式占用。
* 這些 CPU 的負載均衡在自己的範圍內處理，不會影響到其他 CPU。
而在` root_domain` 的這個 span 就是我們所要找的，它的型態為 `cpumask_var_t` 因此我開始找尋這個結構的定義，發現到他在 [cpumask.h](https://github.com/spotify/linux/blob/master/include/linux/cpumask.h#L2) 這個標頭檔中，在仔細研讀程式碼後可以找到下列這行：
```c
/*
* cpumask_var_t: struct cpumask for stack usage.
*
* Oh, the wicked games we play! In order to make kernel coding a
* little more difficult, we typedef cpumask_var_t to an array or a
* pointer: doing &mask on an array is a noop, so it still works.
*
* ie.
* cpumask_var_t tmpmask;
* if (!alloc_cpumask_var(&tmpmask, GFP_KERNEL))
* return -ENOMEM;
*
* ... use 'tmpmask' like a normal struct cpumask * ...
*
* free_cpumask_var(tmpmask);
*/
#ifdef CONFIG_CPUMASK_OFFSTACK
typedef struct cpumask *cpumask_var_t;
#else
typedef struct cpumask cpumask_var_t[1];
```
當` CONFIG_CPUMASK_OFFSTACK `被啟用的時候，`cpumask_var_t `會變成` struct cpumask * ` 指標，代表這個變數將會在堆上動態分配，而不是直接放在堆疊上，反之沒被啟用的時候為陣列。為什麼要這樣做呢在我閱讀完[ CONFIG_CPUMASK_OFFSTACK: Force CPU masks off stack ](https://cateee.net/lkddb/web-lkddb/CPUMASK_OFFSTACK.html)知道了這是為了防止在系統擁有大量 CPU 時堆疊溢位的問題。
>Use dynamic allocation for cpumask_var_t, instead of putting them on the stack. This is a bit more expensive, but avoids stack overflow.
```c
/*
* Cpumasks provide a bitmap suitable for representing the
* set of CPU's in a system, one bit position per CPU number. In general,
* only nr_cpu_ids (<= NR_CPUS) bits are valid.
*/
typedef struct cpumask { DECLARE_BITMAP(bits, NR_CPUS); } cpumask_t;
```
這行證明了 span 為一個 bitmask。
4. sched_group 的組織
* `scheduling domain `必須包含一個或多個 CPU groups (struct sched_group) ，這些群組透過 ->groups 指標組織成單向循環鏈結串列。
* 這些群組的 cpumask 的聯集必須與該`scheduling domain `的 span 相同。
* sched_group 在設置完成後，其內部資料不再變動，變成唯讀數據，因此可以被多個 CPU 共享使用。
* ->groups 指標所指向的群組，必須包含該`scheduling domain `所屬的 CPU。
* 不同群組的 cpumask 可能有交集，如果確實有交集，則會在對應的`scheduling domain ` 上設置`SD_OVERLAP`標誌，此時這些群組不可以被不同 CPU 共享。
5. 負載均衡的機制
* `sched domain` 內，負載均衡是在不同的 CPU groups 之間進行的。
* groups 的負載定義為該 groups 內所有 CPU 的負載總和。
* 只有當某個 groups 的負載變得不均衡時，才會將任務從一個 groups 移動到另一個 groups ，以確保整個系統的負載均衡。
6. 調度與負載均衡的具體運作流程
* `sched_balance_trigger() `會定期運行，以確保負載均衡。
* `當負載均衡的時間到達時`，系統會觸發一個 `softirq`，並執行 `sched_balance_domains() `來遍歷所有排程域。
* 在遍歷排程域的過程中，如果發現負載不均衡，則會執行 `sched_balance_rq() `來尋找最忙碌的 CPU，並嘗試將部分任務遷移到較空閒的 CPU。
## Linux 核心專題: sched_ext 研究
本篇的是研究 sched_ext / scx，並撰寫簡易的使用者層級 CPU 排程器並予以驗證。
由本篇文章得知在 kernel/sched 資料夾 目錄中有 28505 行的程式碼，直接從 Linux 核心的 CFS ( $\lt$ v6.6) 或 EEVDF ( $\geq$ v6.6) 排程器著手進行研究，其所需要的時間成本顯然過高，因此這項專案的誕生無疑是對排程器的發展產生了巨大的引響。
在接下來可以看到 [tteryc](https://hackmd.io/@otteryc) 設計了 Two-level Queue Scheduling ，並說明如何在 sched_ext/scx 的助力下，設計一套簡易的排程器。
以下是我認為能改進的點：
* 可以詳細說明 NICE 值是什麼，並不是只有點到而已。
* 可以提出實做的排程器設計的測試實驗數據。
* 可以測試更多的排程演算法。
* 可以在這基礎上自行實做排程演算法。
在我查看了[NICE 值](https://zh.wikipedia.org/zh-tw/Nice%E5%80%BC)和 [Scheduler Nice Design](https://docs.kernel.org/scheduler/sched-nice-design.html) 後我了解到 Nice 值是類UNIX作業系統中表示靜態優先級的數值。每個行程都有自己的靜態優先級，優先級高的行程得以優先執行。
下列為 Nice 值的說明：
* Nice 值的範圍是 -20~+19 ，擁有 Nice 值越大的行程的實際優先級越小。
* 預設的 Nice 值是 0 。由於 Nice 值是靜態優先級，所以一經設定就不會再被核心修改，除非使用者或系統管理員手動更改（例如使用 renice 指令）。
* Nice 值只影響 CPU 時間的分配，本身不直接決定進程的最終調度順序，而是影響進程獲取 CPU 時間的機率。
## Linux 核心專題: 排程器研究
在閱讀過程中我得知到在 Linux 中最小的排程單位是 thread 而不是 process，thread 的 ID 叫做 PID (process identifier)，process 的 id 叫做 TGID (thread group identifier)。如果 process 只有一個 thread 那該 process 的 PID 等於 TGID。
Thread 和 Process 最大的差異在於：thread 之間共享 address space；process 則無，其他都一樣。在 Linux 中則以 "task" (task_struct) 來稱呼。
在 Linux 中是使用 hash table 來紀錄 PID 的這點是我之前所不知道的於是我查閱了[/linux/pid.h](https://github.com/torvalds/linux/blob/master/include/linux/pid.h)找到了相關的敘述：
```
/*
* What is struct pid?
*
* A struct pid is the kernel's internal notion of a process identifier.
* It refers to individual tasks, process groups, and sessions. While
* there are processes attached to it the struct pid lives in a hash
* table, so it and then the processes that it refers to can be found
* quickly from the numeric pid value. The attached processes may be
* quickly accessed by following pointers from struct pid.
*
```
在找的過程中我也看到一篇有趣的文章[PID 0 行程之謎](https://hackmd.io/@sysprog/linux-pid0)在文章中得知 PID 0 為執行 Linux 核心早期的初始化，然後成為 bootstrap core 的 idle 任務，並作為 CPU 排程和電源管理的配角。
最早的 CPU scheduler 十分簡單，沒有考慮到多核的環境。有 timeslice，以相反方向走訪 runqueue，根據 timeslice 大小、狀態 (sleep/runnable/nil) 來決定誰會先被執行。我不了解這裡為何是相反方向走訪
當所有在 runqueue 中 runnable task 的 timeslice 都為 0，將任務加上一半的 timeslice + priority。從這裡開始 TASK_RUNNING 表示的就不是「正在執行」，而是「可以被執行/準備好被執行」，`NR_TASK` 為最大任務數量。不過，這裡有一個疑問：通常在許多系統中，數值較小的 priority 代表更高的優先級，但依照上述的時間片計算方式，較小的 priority 會導致較少的時間片分配。這似乎與直覺相反，因為高優先級的任務應該獲得更多的 CPU 執行時間，才能更快完成工作。這是否意味著此設計反而讓高優先級的任務拿到較少的 CPU 時間呢？
Timeslice 是指每個進程可以執行的 CPU 時間，當時間片用完後，系統會切換（context switch）到下一個進程。
$O(n)$ scheduler 用 Linked list 來紀錄任務們，每個任務有一個 goodness score，這個分數是根據像是 nice 值或是 timeslice 來決定。那關於 goodness score 並沒有給出原始程式碼的註解具體的算法於是我找尋了[linux-archive/2.4.0/kernel/sched.c](https://github.com/draveness/linux-archive/blob/master/2.4.0/kernel/sched.c#L137)找到了` goodness` 這個函數的註解:
```c
/*
* This is the function that decides how desirable a process is..
* You can weigh different processes against each other depending
* on what CPU they've run on lately etc to try to handle cache
* and TLB miss penalties.
*
* Return values:
* -1000: never select this
* 0: out of time, recalculate counters (but it might still be
* selected)
* +ve: "goodness" value (the larger, the better)
* +1000: realtime process, select this.
*/
```
$O(n)$ scheduler 引進了 epoch 的概念，當所有任務的 timeslice 都被用完了，則表示這次 epoch 結束了。若還有剩下的 timeslice，就把這剩下的 timeslice / 2 加到該任務的新 timeslice。這段話至於為什麼是 timeslice / 2 這是我不了解的地方？
## Linux 核心專題: 針對共用程式碼的測試模組
## Linux 核心專題: 以 eBPF 打造 TCP 伺服器
## Linux 核心專題: 排程器研究
## Linux 核心專題: 透過 Netfilter 自動過濾廣告
Sign in with Wallet
Connect another wallet