# Linux 核心專題: CPU 排程器
> 執行人: vax-r
> [專題解說影片](https://youtu.be/G6p0Y9DZJsM)
## 為何要關注 CPU 排程器？
Linux 作為一款通用作業系統，不僅應用於資料庫、行動裝置、雲端服務等多種領域，還經歷從 $O(n)$, $O(1)$ scheduler, CFS 到現在的 EEVDF 等排程器的演化。CPU 排程器的設計理念在於提供一種普遍適用的策略，以滿足各種不同的應用需求。儘管如此，CPU 排程器所提供的可調參數有限，這使得應用端想要達到最佳效能時，往往感到束手無策。
特別是對那些使用 Linux 的公司來說，當他們的平台只涉及特定工作負載時，通用的排程器可能無法滿足他們的特殊需求。因此，若能自訂排程器行為，將有機會帶來更多好處。然而，直接修改核心不僅技術難度高，且考慮到排程器是作業系統的核心元件，一旦實作出錯，可能導致嚴重後果。此外，Linux 社群不太可能接受針對廠商的自定擴充，這會導致程式碼冗餘和管理混亂。因此，開發自定義排程器的方式，既要降低開發和維護成本，又要確保效率和安全，是新的關鍵問題。
在此背景下，開發人員探索在 Linux 中引入「可插拔」排程器的可能性。這樣一來，開發者便可輕鬆撰寫並植入客製化的 CPU 排程器，又，eBPF 不僅支持將程式碼動態加載到核心執行，還提供檢查器以減少程式對作業系統核心的損害風險。因此，eBPF 無疑成為開發「可插拔」排程器的理想基礎。
## CPU 排程器對特定情境的改進
Linux 核心開發者 Andrea Righi 最近嘗試用 Rust 程式語言改寫 Linux CPU 排程器，藉由 sched-ext 的基礎，用 BPF 動態改寫預設的 CPU 排程器 (即 EEVDF)，目前在電玩遊戲這樣特定的場景中，可超越 EEVDF 的表現，下方動畫展示遊戲在 EEVDF 得到 30 fps，而在 Righi 改寫的 Rust/eBPF 排程器中，遊戲得到 60 fps，意味著電玩遊戲可獲得更多的系統資源，從而得到更好的遊戲體驗。
> [scx_rustland demo: sched_ext](https://youtu.be/oCfVbz9jvVQ)
技術細節：
* [Writing a scheduler for Linux in Rust that runs in user-space](https://arighi.blogspot.com/2024/02/writing-scheduler-for-linux-in-rust.html)
* [Writing a scheduler for Linux in Rust that runs in user-space (part 2)](https://arighi.blogspot.com/2024/03/writing-scheduler-for-linux-in-rust.html)
* [Getting started with sched-ext development](https://arighi.blogspot.com/2024/04/getting-started-with-sched-ext.html)
CPU 排程器對 Linux遊戲體驗有何影響？未能充分調整的排程可能會導致在 Steam Deck 遊戲主機上玩遊戲時出現卡頓現象。首先,我們必須確切地找出導致這個問題的元兇：什麼是「卡頓」，我們又該如何衡量它對\遊戲體驗造成的影響？Igalia 的工程人員分享改進 Linux 遊戲排程器方面的進展，特別是針對 Steam Deck 主機做出的改良。
> [Optimizing Scheduler for Linux Gaming](https://ossna2024.sched.com/event/07a5bb414c14ddacb573c147ba5f3435)
[Linux 核心設計: sched_ext](https://hackmd.io/@RinHizakura/r1uSVAWwp)
> [scx_playground](https://github.com/RinHizakura/scx_playground)
## TODO: 重現上述實驗
> 應涵蓋 [Optimizing Scheduler for Linux Gaming](https://ossna2024.sched.com/event/07a5bb414c14ddacb573c147ba5f3435) 演講所及
## Building & Setup
:::info
若你看到此文的時候已經釋出 Linux Kernel v6.11 ，可以直接跳到[編譯並執行 scx scheduler](#%E7%B7%A8%E8%AD%AF%E4%B8%A6%E5%9F%B7%E8%A1%8C-scx_lavd) 處，因為 sched_ext kernel branch 應該已經被整合進入正式的 Linux Kernel 當中。詳細可以參見以下連結
[Re: [PATCHSET v6] sched: Implement BPF extensible scheduler class](https://lore.kernel.org/bpf/CAHk-=wg8APE61e5Ddq5mwH55Eh0ZLDV4Tr+c6_gFS7g2AxnuHQ@mail.gmail.com/)
:::
此專案的程式碼主要在 [sched-ext/scx](https://github.com/sched-ext/scx) 當中，包含了數個不同 scheduling policy 的排程器，讓 scx 當中的排程器進行排程的基本要求是讓系統存在 Extensible Scheduling Class 這個定義在 [sched-ext/sched_ext](https://github.com/sched-ext/sched_ext) kernel branch 當中的一個 scheduling class ，重現演講當中的實驗包含效能測試，因此我們會在實體機器上運行，可以依照 [scx: Install instruction by Distros](https://github.com/sched-ext/scx?tab=readme-ov-file#install-instructions-by-distro) 的指示安裝不同的 kernel ，或者也可以從 [sched-ext/sched_ext](https://github.com/sched-ext/sched_ext) 當中編譯一個作業系統核心來啟動一個 scx enabled kernel 。
以下展示如何從 [sched-ext/sched_ext](https://github.com/sched-ext/sched_ext) 編譯一個可以開啟 ubuntu 機器的 kernel 。
### 編譯並執行 scx enabled kernel
首先取得程式碼
```shell
$ git clone git@github.com:sched-ext/sched_ext.git
```
因為編譯的核心要用來啟動實體機器， `.config` 需要正確設定，包括 kernel modules 的設定，建議直接從原本運行的 kernel config 複製一份再修改，編譯時間會較長但也較能保證在所有機器上都能運行
```shell
$ cd sched_ext
$ cp -v /boot/config-$(uname -r) .config
```
接下來開啟 scx 需要的選項，可以參照 [Linux 核心設計: Scheduler(7): sched_ext](https://hackmd.io/@RinHizakura/r1uSVAWwp?fbclid=IwZXh0bgNhZW0CMTAAAR3r72D14vgfxdKVvxpCztPRpBtzGdAgA_oB_WDAfZQudjhDOd-ran8wg-Y_aem_AVMUs6l1Qe_lzPuWSHBPlH63HjsIAflGxftI5wI4zUnYn0suOO6otjtcdy1v5eEV8IVCQ-fjpGUj_X8yNZkK_Q-X#%E5%A6%82%E4%BD%95%E4%BD%BF%E7%94%A8-sched_ext) 的設置。注意此處不需要用 clang 編譯，用預設的 gcc 即可， clang 是編譯 scx 當中排程器才需要，此處我們編譯 kernel 而已。
```shell
$ sudo make menuconfig
```
設定好之後就可以進行編譯，應該需要一段漫長的等待（可以利用此時開啟 `htop` 觀察 CPU 負載變化，可以觀察並推測預設 EEVDF/CFS 的行為）。
```shell
$ sudo make -j $(nproc)
```
:::warning
在 ubuntu 機器上編譯可能遇到以下錯誤訊息
```shell
No rule to make target 'debian/canonical-certs.pem
```
此時可以利用以下步驟繞過這個錯誤
```shell
$ scripts/config --disable SYSTEM_TRUSTED_KEYS
$ scripts/config --disable SYSTEM_REVOCATION_KEYS
```
:::
編譯完成之後利用以下幾個命令並更新 grub ，就可以重新開機了
```shell
$ sudo make modules_install
$ sudo make install
$ sudo update-initramfs -c -k <your_kernel_version>
$ sudo update-grub
$ sudo reboot
```
重新開機之後利用 `uname -r` 觀察 kernel version ，應該已經改變，例如我當前的版本是
```shell
$ uname -r
6.9.3-scx1
```
到此處就成功運行一台 scx enabled 的實體機器啦！
### 編譯並執行 `scx_lavd`
`scx_lavd` 即是演講當中提及的 LAVD scheduler ，重視 interactivity ，如果上述步驟都順利執行，只需要將 [sched-ext/scx](https://github.com/sched-ext/scx) 下載並編譯執行即可，步驟如下
```shell
$ git clone git@github.com:sched-ext/scx.git
$ cd scx
$ meson setup build --prefix ~
$ meson compile -C build
$ meson install -C build
```
編譯好的排程器執行檔依據使用 C 語言或 Rust 的不同，會分別位在 `build/scheds/c` 底下或者 `build/scheds/rust` 底下。此處我們想運行的是 `scx_lavd` ，位於 `build/scheds/rust/scx_lavd/debug/scx_lavd` ，因此使用以下命令
```shell
$ sudo ./build/scheds/rust/scx_lavd/debug/scx_lavd
...
```
如此一來應該可以看見 `scx_lavd` 順利被掛載到 kernel space 當中並開始運行。
:::warning
如果你啟動 kernel 的方式是按照 [scx: Install Instructions by Distros](https://github.com/sched-ext/scx?tab=readme-ov-file#install-instructions-by-distro) ，重新開機之後你不僅擁有新的 kernel ，系統預設應該也已經運行了 `scx_rustland` ，所以直接按照上述步驟啟動 `scx_lavd` 可能會無法掛載，利用 `systemctl` 命令觀察 `scx.service` 目前的狀態
```shell
$ sudo systemctl status scx.service
● scx.service - Start scx_scheduler
Loaded: loaded (/usr/lib/systemd/system/scx.service; enabled; preset: enabled)
Active: active (running) since Wed 2024-06-12 00:43:56 CST; 3s ago
Main PID: 238301 (scx_rustland)
...
```
我們可以修改 `/etc/default/scx` 的內容將排程器改為 `scx_lavd` ，不過我們後續希望可以對排程器程式碼進行修改並測試，因此我們先把預設的排程器都關掉
```shell
$ sudo systemctl stop scx.service
$ sudo systemctl disable scx.service
```
如此一來上述掛載 `scx_lavd` 的步驟就可以順利執行
:::
順利啟用並掛載 `scx_lavd` 了，此時為了重現演講實驗，我們需要安裝幾個 profiling tools ，分別是
* [MangoHud](https://github.com/flightlessmango/MangoHud)
* [vapormark](https://github.com/Igalia/vapormark)
* 新版本 perf （由於會用到 `perf sched` 命令）
安裝完 MangoHud 後，在你想測試的 Steam 遊戲開啟的進階選項中加上 `mangohud %command%` ，之後開啟遊戲應該會看到以下畫面
Ubuntu 上支援的 Steam 遊戲不多，主流的商業大作基本上都無法運作，我採用一款舊的免費遊戲 Left 4 Dead 2 進行測試，進入遊戲之後按下 `Ctrl + f2` 會開始進行 logging ，玩到一個段落後再度按下 `Ctrl + f2` 就會停止 logging 。然後就利用 vapormark 當中提供的工具 ginsight 對 log file 進行分析與作圖
可以看到 FPS 隨時間的變化以及其 CDF 做圖如下
另外也可以對 CPU load, GPU load , RAM 用量等 metric 進行 logging 與分析做圖。接下來我們利用 vapormark 的 schedmon 工具（其實是對 `perf sched` 的包裝）來監控系統當中更加微觀的 per-task event 。
```shell
$ sudo ./vapormark/bin/schedmon -o dir_name -l l4d
```
此處不建議監控並記錄太久，會產生超大量並非常佔空間的 log ，分析也非常耗時。分析工具利用 vapormark 提供的 schedinsight 對 log file 進行解析，需要一段時間並且會產生非常多圖片，此處只展示一部分
* **system wide task stats data**
* **system wide idle stats data**
* **steam's wait_time, sched_delay, and runtimes**
* **IPC:CSteamEngin[7888/7664]'s wait_time, sched_delay, and runtimes**
* **Distribution of waiters**
* **Distribution of wakers**
* **40-percentile of waker-waiter**
到此處為止我們就完整的重現了演講當中的 `scx_lavd` 排程器的運作以及如何進行實驗的 profiling 與做圖等等。
## TODO: 引入機器學習到 CPU 排程器
研讀〈[Machine Learning for Load Balancing in the Linux Kernel](https://doi.org/10.1145/3409963.3410492)〉
> [GitHub](https://github.com/Keitokuch/MLLB)
[Machine Learning for Load Balancing in the Linux Kernel 論文閱讀](https://hackmd.io/@vax-r/ML_LB)
> Emulate the CFS load balancer with ML model. Collect the load balancing relative data via kprobe on `can_migrate_task()`. A relativly simple ML model (15-10-1) is enough. The fixed-point number implementation reduces overhead compared to floating-point implementation. The paper indicates that the system load at the moment the traning data is collected will affect the accuracy of model. The paper only provides the accuracy that the model is under CPU intensive workload (PARSEC Benchmark suite), thus, the accuracy under different kind of workload should be double checked.
>
> The model used in the paper takes 15 features to make the decision. The customized function, `should_migrate_task()`, is inserted in the function `can_migrate_task()`, right above the condition that checks whether to migrate the given task aggressively, which was the only part replaced by the model. Thus, I think the model could be simplified by remove the 2nd, 3rd, 5th, 10th and 11th features since they are not used in the replaced code, furthermore, I think the 13th feature could be simplified by a boolean flag that indicates whether `dst_faults` is less than `src_faults`.
> See also: [Profiling CPU scheduler with eBPF](https://hackmd.io/@foxhoundsk/sched-profling)
研讀〈[KML: Using Machine Learning to Improve Storage Systems](https://arxiv.org/abs/2111.11554)〉
> [GitHub](https://github.com/sbu-fsl/kernel-ml)
### 搭配 scx 引入機器學習進入排程器
依照上述論文所述，我們可以利用機器學習模仿 EEVDF/CFS 的 load balance 機制當中的 `can_migrate_task()` 函式行為，來判斷一個任務是否該被搬移。談到負載平衡需要考慮的因素其實很多，就排程器而言任務挑選 CPU 其實就隱含了負載平衡的機制，理想上排程器為每個任務挑選 CPU 的邏輯就該完美的達到負載平衡，但實際上系統依舊會在某些情況當中出現極大的負載不平衡而影響 CPU 甚至整個系統的效能，因此我們才需要額外定期地做 load balance 的操作與檢查。
在 `scx` 專案當中，特別將負載平衡機制實作出來的排程器是 `scx_rusty` ，透過 Rust 在使用者層級另外實作 load balancer ，其中一大好處是計算 load 不再使用精度不高的定點數，觀察 `scx_rusty` 的 load balancer 可以看到它計算 load 的方式是直接採用 `f64` 。
所以 `scx_rusty` 是否有在任何場景勝過 EEVDF/CFS 呢？首先思考什麼場景讓系統出現極大的 load imbalance ，以及它帶來的衝擊是什麼。我們應該先有一個最基本的認知，不管我們排程的策略是什麼，我們的目標始終應該是優化該 workload 最直接相關的 metric ，例如 FPS 之於遊戲，訓練時間之於機器學習，編譯時間之於 kernel compilation 等等。
此處我們之所以談到 load balance 、 runqueue length 或者 task migration 的成本以及次數，都是在思考這些 *intermediate metrics* 是否會對上述我們最在意的 metric 造成影響，而這視情況而定，並非系統負載越平衡就是好事，或許有一個排程策略與 load balancer 搭配後系統負載 99% 的時間都非常均衡散佈在各個 CPU ，但由於花了過多力氣進行任務的遷移，真正執行我們想要運行之 workload 時間卻很少，反而讓性能變糟糕。因此我們在將這些 intermediate metric 納入考量並思考如何優化時，也不能過度著眼於優化它們而忘記我們最初且最重要的 metric 。更詳細可以參考我的筆記 [sched_ext(4): Generate CPU load unbalance](https://hackmd.io/@vax-r/sched_ext_4) 還有 [Large amount of redundant task migration](https://github.com/sched-ext/scx/issues/330) 的 github issue 討論，我和 htejun 討論了關於 task migration 成本等問題。
有了以上的認知，我們思考並嘗試創造一個容易因為 load imbalance 過大而誘發 task migration 的場景，其中一個可能是同時進行大量 CPU-intensive workload 與 I/O-intensive workload 的時候，例如同時編譯 kernel 又同時對 disk 做大量 I/O ，或者 file server 也可能在定期分析系統 log 的時候遇到這個問題（分析 log 是 CPU-intensive workload ，同時間用戶又繼續大量上傳下載檔案）。
我們採用 `fio` 這個工具進行大量 I/O ，並在同時間編譯 linux kernel ，再利用 `mpstat` 命令進行 logging 之後分析 CPU load maximum imbalance 情況，可以發現 EEVDF 和 `scx_rusty` 的結果如下
```shell
EEVDF: Maximum CPU load imbalance over the period: 98.99%
scx_rusty: Maximum CPU load imbalance over the period: 99.00%
```
兩者在這個場景的 CPU load imbalance 都是非常可觀的，如果利用 `perf` 觀察 task migration 次數，結果如下
* **EEVDF**
```shell
$ sudo perf stat -e sched:sched_migrate_task -a sleep 120
Performance counter stats for 'system wide':
5,1719 sched:sched_migrate_task
120.001858274 seconds time elapsed
```
* **scx_rusty**
```shell
$ sudo perf stat -e sched:sched_migrate_task -a sleep 120
Performance counter stats for 'system wide':
26,5801 sched:sched_migrate_task
120.055235563 seconds time elapsed
```
結果顯示 `scx_rusty` 在同樣兩分鐘內， task migration 次數幾乎是 EEVDF 的五倍，但 CPU maximum imbalance 情況沒有較好，但別忘記我們的目的是優化 workload 直接相關的 metric ，以這個情況來說是 linux kernel 的編譯時間，於是我們利用 `time` 命令協助測量(同時進行 `fio` 壓力測試創造以測試在極端環境下不同排程器的表現)
* **EEVDF**
```shell
$ time sudo make -j $(nproc)
...
real 6m20.062s
user 0m0.064s
sys 0m0.101s
```
* **scx_rusty**
```shell
$ time sudo make -j $(nproc)
...
real 7m10.187s
user 0m0.047s
sys 0m0.117s
```
編譯時間相較 EEVDF 還慢了一分鐘，這代表在 load imbalance 經常發生的情況 EEVDF 在編譯上的表現是優於 `scx_rusty` 的。
我們嘗試參考上述論文所採用的方法，利用機器學習模仿 `can_migrate_task()` 的行為並引入 `scx_rusty` 當中，實際改動的方式可以參考我的筆記 [sched_ext(5): Integrate Machine Learning into scx_rusty Load balancer](https://hackmd.io/@vax-r/sched_ext_5) 。此處顯示結果，首先就 task migration 次數而言有明顯的減少，同樣是在 `fio` 測試與 kernel compilation 同時進行的情況下
```shell
$ sudo perf stat -e sched:sched_migrate_task -a sleep 120
Performance counter stats for 'system wide':
6,1749 sched:sched_migrate_task
120.200994178 seconds time elapsed
```
task migration 次數從 26,0000 次降低至 6,0000 次左右，減少了大約 20,0000 次的 task migration ，這是否對編譯 kernel 的時間有正面的影響呢？還是反而讓編譯時間變長，同樣進行測試
```shell
$ time sudo make -j $(nproc)
...
real 5m41.276s
user 0m0.046s
sys 0m0.107s
```
比原本的 `scx_rusty` 編譯時間縮短了將近兩分鐘，是十分顯著的進步。此段 PoC 展示了機器學習在 CPU 排程器當中可以帶來的效益，還有許多可調整之處正在進行當中，包括是否能使用更輕量化的 package ，因為 tensorflow 或 pytorch 帶來的 overhead 都十分沈重，對於系統而言是傷害，不過上述看見效能的改進也可以說明機器學習在作業系統層級中的潛力。尤其是機器學習最在意的大量資料來源，需要大量資料並分析特徵，這對於作業系統而言反而非常簡單，僅僅是不到 10 分鐘的 logging 就可以搜集數十萬筆資料，每筆資料的 field 又非常多，每個都可以當成是一個特徵來訓練。
:::warning
上述編譯的 linux kernel 都利用以下命令產生一個簡單的 `.config` ，避免編譯過久
```shell
$ sudo make defconfig
```
:::
完整的程式碼更動可以參見 [vax-r/scx:scx_rusty_MLLB](https://github.com/vax-r/scx/tree/scx_rusty_MLLB) 。
在負載平衡的機制當中有一種 corner case 稱為 infeasible weight situation ，也就是某個任務的 weight 過大導致 duty cycle 計算結果大於 1 ，擠壓到剩下任務可使用的 CPU 資源，這時會產生許多閒置的資源沒有被分配，這即是問題所在，論文 [Infeasible Weights Solution](https://drive.google.com/file/d/1fAoWUlmW-HTp6akuATVpMxpUpvWcGSAv) 探討了兩個解決此情況的辦法（當前 linux kernel 預設的 scheduler 都有上述問題）。而且 core 數量越多的系統越容易有這個問題， scx 在 [rust/scx_utils/src/infeasible.rs](https://github.com/sched-ext/scx/blob/main/rust/scx_utils/src/infeasible.rs) 當中實作了此論文的解法。此處引發我思考的是這代表原本 Linux Kernel 預設的各種排程策略，在計算負載的方法上有改進空間，光是改善計算負載的方式就可能讓負載平衡機制得到改善。
第二點是負載平衡究竟要考慮哪些特徵，我在上述實作的 PoC 實際在排程器當中很難應用，因為機器學習本身任務的負載就可能很大，但可以透過機器學習找到幾個關鍵特徵並實作 deterministic 的方法使得 task migration 的決策變得較保守。
## Improve load balancer of scx_rusty
上個段落探討如何利用機器學習方法改進負載平衡機制，在對於當前 linux kernel 的 SCHE_NORMAL 當中的負載平衡不需要有任何知識，僅需要將 `lb_env` 當中的資料提取出來並訓練一個模仿 `can_migrate_task` 之模型即可。
但面臨到的除了 tensorflow, pytorch 等機器學習框架會引入可觀的成本以外，還要 scx_rusty 的負載平衡利用 Rust 在使用者層級實作，當前依舊只支援 single-thread 模式 ( Rust 的嚴格規定，若要支援 multi-threaded 情境要使用其他資料結構)。因此整體來說引入的執行時期負擔會更大。若能真正了解負載平衡機制並嘗試實作，可以對 scx_rusty 帶來更大的效益。
目前 scx_rusty 挑選可被遷移之任務邏輯十分單純，和 [/kernel/sched/core.c](https://) 當中的 `is_cpu_allowed` 相同，僅檢查任務是否被遷移過以及是否為 kthread ，以及目標 CPU 是否在任務的 domain mask 當中。
:::warning
core.c 和 core_sched.c 的定位完全不同， core_sched.c 當中實作了防範硬體漏洞的一些排程函式，尚須探討。
:::
以此為基礎，我將任務 `task_struct` 當中的 `core_cookie` 也納入任務遷移的考量，在 kernel 當中，同一個 core 上運行的任務應該具有相同的 cookie (偶爾還是會有一小段時間存在不一致的情況)。將 `core_cookie` 送入使用者空間並與當前 domain 運行任務之 `core_cookie` 進行比較，只有具相同 `core_cookie` 之任務可以被挑選。
同樣針對 kernel compilation 進行實驗，在同時進行 io test 的形況創造 load imbalance 情景，改動前編譯一次 kernel 所需時間為
```shell
6m29s
```
改動後編譯時間些微下降
```shell
6m24s
```
同時若以 perf 觀測一分鐘內搬移任務的次數，可以發現搬移次數從 **9,0161 下降至 7,1570** ，節省了約 20000 次的任務搬遷成本。
詳細 PR 可參見連結 : [scx_rusty: Support domain/core cookie policy](https://github.com/sched-ext/scx/pull/598)
:::warning
負載平衡效果顯著的情況通常要機器規模夠大，例如在 48 核或 64 核這樣規模的 CPU 才能顯著展現 NUMA 的威力。包括原本 EEVDF 為了避免每次檢查 load imbalance 都會引入 $O(n^2)$ 時間複雜度而衍伸出 CPU hierarchy 所帶來的好處。
load imbalance 發生的原因也會是值得探討的項目之一。
:::
## sched_ext 探討
* [eBPF and related tools](https://hackmd.io/@vax-r/ebpf_tools)
* [Rust learning note](https://hackmd.io/@vax-r/rust_learning_note)
* [Rust learning note(2)](https://hackmd.io/@vax-r/rust_learn_2)
* [sched_ext 研究](https://hackmd.io/@vax-r/sched_ext_exp)
* [sched_ext(2): 分析排程器程式碼](https://hackmd.io/@vax-r/sched_ext_2)
* [sched_ext(3): Write a scheduler to bomb a CPU core](https://hackmd.io/@vax-r/sched_ext3)
* [sched_ext(4): Generate CPU load unbalance](https://hackmd.io/@vax-r/sched_ext_4)
* [sched_ext(5): Integrate Machine Learning into scx_rusty Load balancer](https://hackmd.io/@vax-r/sched_ext_5)
* [sched_ext(6) : kernel branch breakdown](https://hackmd.io/@vax-r/sched_ext_6)
## Merged Pull Request
* [scx: Branchless implementation of highest_bit](https://github.com/sched-ext/sched_ext/pull/208)
* [Avoid redundant substraction in rsigmoid_u64](https://github.com/sched-ext/scx/pull/290)
* [scx_flatcg: Correct content error in comment](https://github.com/sched-ext/scx/pull/304)
* [scx_central: Provide backward compability](https://github.com/sched-ext/scx/commit/5881c61a5ee3aae4019c25fc042078af9923c107)
* [scx_lavd: Enforce memory barrier in flip_sys_cpu_util](https://github.com/sched-ext/scx/pull/318)
* [scx_lavd: Adding READ_ONCE()/WRITE_ONCE() macros](https://github.com/sched-ext/scx/pull/322)
* [scx_rusty: Elimate data races possibility for domain min_vruntime](https://github.com/sched-ext/scx/pull/341)
(還有更多此處就不逐一列出)
## 延伸問題
* 多數 scheduling policies 多為 heuristic algorithm 或是大量的 adaptive method 組合而成，考量因素過多，是否有更適用的 close form 形式的演算法？
* sched_ext 目前還未被 LKML 採納其中一個因素是因為尚未對於 cgroup 排程上有完整的支援，不過 htejun 已經著手進行實作，此處我好奇的是 cgroup 是一個資源控制器為何在 scheduling 當中如此重要？淺顯的理由是因為排程需要考量使用資源量等等，但從開發紀錄以及實作來看不僅如此， cgroup 還有在 linux kernel 當中還有什麼特別的特性？
* 如何利用工具分析一個 task 的各種特性，不僅僅是 CPU-intensive 或 I/O-intensive ，採集要優化場景當中各種 task 的細項特性才能有效設計對應排程演算法
* I/O-bound task 是 synchronize I/O 還是 async-I/O ? 這會導致是否對於 CPU 還造成多餘的壓力，應該採入實驗考量
Sign in with Wallet
Connect another wallet