HackMD
2025q1 Homework1 (ideas)
contributed by < wurrrrrrrrrr >
還政於民的 sched_ext 及機器學習如何幫助 CPU 排程
在研讀過 Linux 核心專題: CPU 排程器 後我得知 Linux 排程器的演化，經歷了
在閱讀過程中我看到了以下這段話：『開發人員探索在 Linux 中引入「可插拔」排程器的可能性』而要支持這向技術的基礎為 eBPF。
eBPF 不僅支持將程式碼動態加載到核心執行，還提供檢查器以減少程式對作業系統核心的損害風險。這樣一來，開發者便可輕鬆撰寫並植入客製化的 CPU 排程器。
在閱讀這篇文章之前，我一直認為一旦設定好 CPU 排程器後，就只能使用該排程方式，然而「可插拔」排程器的概念顛覆了我的想法，但 eBPF 到底是什麼呢？於是我先閱讀了 eBPF 在這篇文章中我了解到 eBPF 就是 BPF 的擴充，所以如果要如果了解 eBPF 是什麼的話就必須先了解什麼是 BPF 。
傳統的封包過濾方法，需要先將 kernel 的封包複製進 userspace，再進一步於 userspace 分析封包，然而這個複製的過程 cost 是很高的，直到 The BSD Packet Filter: A New Architecture for User-level Packet Capture 中的 Berkeley Packet Filter (BPF)被提出來後，就避免了把無用的封包複製到 userspace 的過程。
從形式上來看，BPF 本質上是一個運行在 kernel 中的虛擬機，允許用戶將特定的過濾邏輯（用戶空間程式）轉換成位元組碼 (Bytecode)，即一種簡化的虛擬指令集，並將其注入內核空間執行。這樣封包篩選過程就在 kernel 內部完成，減少了不必要的數據複製提高了封包處理的性能。
之後 BPF 被擴展至網路以外的領域，而可以被應用在 kernel 效能分析，那便是 eBPF(extended BPF) 。
eBPF 基於 BPF 可將使用者定義的程式注入 kernel 中的架構做出了更多改進，而在核心專題所提到檢查器的是 eBPF 有 verifier 機制，在注入程式之前，先進行一系列的檢查，避免注入危險的程序損壞到 kernel。
sched_ext
Linux kernel 自 v6.12 開始支援 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 ：
#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 的子系統能夠使用者定義的函式。
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
圖片來源
在了解完上述的名詞後就到本次的重點將機器學習引入 cpu 的排程中，在演講中有提到 cpu load balance in linux kernel 當中的一個關鍵的函數為 can_migrate_task()，這個函數最主要的功能為檢查現在挑選出的任務他是不是適合在 cpu 之間做搬遷，如果適合這個函數會回傳 1 ，反之不適合回傳 0 ，而這個專題就是用機器學習來模仿這個函數的行為，於是先去觀看了 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 核心的紅黑樹知道了紅黑樹其新增、移除、搜尋的時間複雜度均維持在
cfs_rq也擁有自己的sched_entity且可以被其他cfs_rq排程。
在第二段中提到 CFS 會透過 timer interrupt handler 週期性的呼叫scheduler_tick()進行負載平衡，而負責處理負載平衡的程式會以softirq的方式運作，那什麼叫做softirq呢？於是我去閱讀了 Introduction to deferred interrupts (Softirq, Tasklets and Workqueues) 和 Linux 核心設計: Interrupt了解到在現代的作業系統中，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 了解到什麼叫做scheduling domain以下為他的解釋：
- Base Scheduling Domain 與層級結構
- 每個 CPU 都有一個 “base”
scheduling domain(struct sched_domain)，用來管理該 CPU 的任務調度。 scheduling domain的層級結構是由“base”scheduling domain組成，透過 ->parent 指標連接。- 每個
scheduling domain可以有一個parent scheduling domain，而這個鏈結必須以 NULL 結束（即最上層的父節點為 NULL） 而這個 parentscheduling domain有什麼作用呢？這邊舉個簡單的例子：當scheduling domainB 和scheduling domainC 內部的負載出現不均時，parent scheduling domainA 就會介入，協調這兩個基礎sched_domain之間的任務遷移，使得兩個 CPU 的負載更加平衡。 scheduling domain的數據結構是針對每個 CPU 設計的，且更新時不需要鎖（lockless updates），因為每個 CPU 更新的都是自己專用的數據，所以不會出現多個 CPU 同時修改同一份數據的情況。這樣就不需要使用鎖（如互斥鎖）來保護數據的一致性。
- 每個 CPU 都有一個 “base”
下列為第三點的圖示：
[`sched_domain` A] (頂層)
↑
->parent = NULL
↑
┌──────┴──────┐
│ │
[`sched_domain` B] [`sched_domain` C]
↑ ↑
└────────────->parent 指向 `sched_domain` A
下列為第四點的例子：
假設系統中有兩個 CPU，各自擁有獨立的 scheduling domain：
CPU0 CPU1
┌─────────────────┐ ┌─────────────────┐
│ sched_domain0 │ │ sched_domain1 │
│ load = 10 │ │ load = 8 │
└─────────────────┘ └─────────────────┘
當 CPU0 執行 update_load(2) 時，CPU0 自己的 load 由 10 變成 12，而 CPU1 的 scheduling domain 不會受到任何影響。由於每個 CPU 更新的都是自己專用的數據，所以這個過程中不需要加鎖同步。
scheduling domain的範圍（span）與其要求-
每個
scheduling domain會覆蓋一定數量的 CPU（這個數據存放在 ->span 欄位中）。(通常 ->span 是一個 bitmask，表示哪些 CPU 被納入這個scheduling domain中，用於後續的負載均衡決策。) -
一個域的覆蓋範圍必須是它的子域覆蓋範圍的超集。
- 例子：有一個父域，它的子域分別是 CPU0 和 CPU1 的基礎
sched_domain。那麼這個父域的覆蓋範圍必須是 {CPU0, CPU1} 或包含這個集合的更大集合，例如 {CPU0, CPU1, CPU2}，但至少要包含 {CPU0, CPU1}。
- 例子：有一個父域，它的子域分別是 CPU0 和 CPU1 的基礎
-
CPU i 的“base”
scheduling domain至少必須包含 CPU i。- 例如，對於 CPU2，它的“base”
scheduling domain的覆蓋範圍至少應該包含 CPU2。這保證了每個 CPU 都能夠獨立參與到負載均衡中，而不會出現某個 CPU 被完全排除的情況。
- 例如，對於 CPU2，它的“base”
-
但我要怎麼知道 span 是一個 bitmask 呢？於是我查看了 linux 的原始程式碼找到了相關的敘述。
下列證明 span 是一個 bitmask：
/*
* 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 這個標頭檔中，在仔細研讀程式碼後可以找到下列這行：
/*
* 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 知道了這是為了防止在系統擁有大量 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.
/*
* 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。
-
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 共享。
-
負載均衡的機制
sched domain內，負載均衡是在不同的 CPU groups 之間進行的。- groups 的負載定義為該 groups 內所有 CPU 的負載總和。
- 只有當某個 groups 的負載變得不均衡時，才會將任務從一個 groups 移動到另一個 groups ，以確保整個系統的負載均衡。
-
調度與負載均衡的具體運作流程
sched_balance_trigger()會定期運行，以確保負載均衡。當負載均衡的時間到達時，系統會觸發一個softirq，並執行sched_balance_domains()來遍歷所有排程域。- 在遍歷排程域的過程中，如果發現負載不均衡，則會執行
sched_balance_rq()來尋找最忙碌的 CPU，並嘗試將部分任務遷移到較空閒的 CPU。
Linux 核心專題: sched_ext 研究
本篇的是研究 sched_ext / scx，並撰寫簡易的使用者層級 CPU 排程器並予以驗證。
由本篇文章得知在 kernel/sched 資料夾 目錄中有 28505 行的程式碼，直接從 Linux 核心的 CFS (
在接下來可以看到 tteryc 設計了 Two-level Queue Scheduling ，並說明如何在 sched_ext/scx 的助力下，設計一套簡易的排程器。
以下是我認為能改進的點：
- 可以詳細說明 NICE 值是什麼，並不是只有點到而已。
- 可以提出實做的排程器設計的測試實驗數據。
- 可以測試更多的排程演算法。
- 可以在這基礎上自行實做排程演算法。
在我查看了NICE 值和 Scheduler Nice Design 後我了解到 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找到了相關的敘述：
/*
* 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 行程之謎在文章中得知 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）到下一個進程。
goodness 這個函數的註解:
/*
* 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.
*/
