# Linux 核心專題: CPU 排程器研究
> 執行人: linhoward0522
> [專題解說錄影](https://youtu.be/la0i6O4JS48)
:::success
:question: 提問清單
* BORE 排程器跟CFS比犧牲了什麼??數據看的出來嗎
> 我認為犧牲的是「公平性」，可以從下面實驗看出來
> 公平性 ： 兩個具有相同優先權級的任務應該要運行幾乎相同的時間
> #### CPU-bound and yield
> 在處理器核編號 2 上執行的任務分別是 CPU-bound 與 yield 類型的任務
> - CPU_bound 任務 : 在 main 函數中有一個 for 迴圈，每次迭代都會進行矩陣乘法，共迭代四次
> - yield 任務 : 與 CPU-bound 任務相同，只是每次迭代進行矩陣乘法後，會呼叫 `sched_yield` 主動放棄處理器資源
> - [ ] BORE
>
> - [ ] CFS
>
>
>由實驗結果可以看出當每次輪到 yield 類型的任務使用 CPU 資源時， BORE 會給予更多的 timeslice (因為可以看到最後面 CPU-bound 任務使用一大段時間的 CPU 資源，表示 yield 類型的任務被給予更多的 timeslice)，所以 yield 類型的任務會比 CPU-bound 類型的任務還要早執行完成。而 CFS 則是非常公平的平均分配 timeslice 給兩種任務。此實驗結果也與 BORE 原作者所說的 ： 「稍微偏離 CFS 原有的 complete fairness 原則」相同。
* 「EEVDF 非常頻繁的切換執行，因為 EEVDF 的 timeslice 較短」這陳述是否意味著 EEVDF 的執行成本較高？
> 在處理器核編號 2,3 號上使用 [stress](https://linux.die.net/man/1/stress) 來各產生 2 個 CPU-bound 任務，並且利用 taskset 將其指定到對應的處理器核編號上
> 我利用 [perf](https://perf.wiki.kernel.org/index.php/Main_Page) 來簡單觀察一下，以下是收集 10 秒鐘的結果
- CFS
```
-------------------------------------------------------------------------------------------------------------------------------------------
Task | Runtime ms | Switches | Avg delay ms | Max delay ms | Max delay start | Max delay end |
-------------------------------------------------------------------------------------------------------------------------------------------
stress:(4) | 20001.528 ms | 1255 | avg: 15.907 ms | max: 16.008 ms | max start: 101497.845449 s | max end: 101497.861457 s
migration/3:34 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
migration/2:28 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
-----------------------------------------------------------------------------------------------------------------
TOTAL: | 20001.528 ms | 1257 |
---------------------------------------------------
```
- BORE
```
-------------------------------------------------------------------------------------------------------------------------------------------
Task | Runtime ms | Switches | Avg delay ms | Max delay ms | Max delay start | Max delay end |
-------------------------------------------------------------------------------------------------------------------------------------------
stress:(4) | 20001.590 ms | 3308 | avg: 6.042 ms | max: 8.014 ms | max start: 101527.792998 s | max end: 101527.801012 s
migration/3:34 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
migration/2:28 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
-----------------------------------------------------------------------------------------------------------------
TOTAL: | 20001.590 ms | 3310 |
---------------------------------------------------
```
- EEVDF
```
-------------------------------------------------------------------------------------------------------------------------------------------
Task | Runtime ms | Switches | Avg delay ms | Max delay ms | Max delay start | Max delay end |
-------------------------------------------------------------------------------------------------------------------------------------------
stress:(4) | 20005.383 ms | 5007 | avg: 3.994 ms | max: 4.009 ms | max start: 21546.291197 s | max end: 21546.295206 s
migration/3:34 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
migration/2:28 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
-----------------------------------------------------------------------------------------------------------------
TOTAL: | 20005.383 ms | 5009 |
---------------------------------------------------
```
可以看出 EEVDF 的切換次數遠高於 CFS , BORE，切換次數越高表示執行成本較高。
:::
## 任務簡述
研讀《Demystifying the Linux CPU Scheduler》，更新書中關於 [BORE](https://github.com/firelzrd/bore-scheduler) 及 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 的描述，採用 Linux v6.1。
## 事前準備
[Demystifying the Linux CPU Scheduler 筆記](https://hackmd.io/@linhoward0522/HyC28W9N3)
### 更新至 Linux v6.1
:::spoiler 後來發現應該要使用自行編譯的 Linux 核心，改用以下方法：
查看目前版本
```shell
$ uname -mrs
Linux 5.19.0-41-generic x86_64
```
更新所有 package
```shell
$ sudo apt update
```
新增 `cappelikan` repository 以及下載 Ubuntu Mainline Kernel Installer
```shell
$ sudo add-apt-repository ppa:cappelikan/ppa -y
$ sudo apt install mainline -y
```
打開 Ubuntu Mainline Kernel Installer 找出所需要的版本並安裝，最後重開機即可
```shell
$ uname -mrs
Linux 6.1.28-060128-generic x86_64
```
:::
下載需要的套件
```shell
$ sudo apt install gcc make libncurses-dev flex bison libssl-dev libelf-dev initramfs-tools-bin
```
下載指定的核心版本並解壓縮
```shell
$ wget https://cdn.kernel.org/pub/linux/kernel/v6.x/linux-6.1.29.tar.xz
$ tar -xvf linux-6.1.29.tar.xz
```
進入該目錄，並複製核心開啟的檔案到當下目錄的 config 檔
```shell
$ cd linux-6.1.29
$ cp /boot/config-5.19.0-41-generic .config
```
建立編輯選單，進入選單後將 config 檔載入
```shell
$ make menuconfig
```
- 選擇 load .config
- 選擇 save .config
- 按兩次 ESC 離開選單
修改 `.config` 檔案，將下列兩行內容刪除，如下所示
```shell
$ vim .config
CONFIG_SYSTEM_TRUSTED_KEYS=""
CONFIG_SYSTEM_REVOCATION_KEYS=""
```
編譯模組，安裝核心後重開機
```shell
$ make -j 8
$ sudo make modules_install
$ sudo make install
$ sudo reboot
```
確認是否安裝成功
```shell
$ uname -mrs
Linux 6.1.29 x86_64
```
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ uname -mrs
Linux 6.1.29 x86_64
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12400
CPU family: 6
Model: 151
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
CPU max MHz: 5600.0000
CPU min MHz: 800.0000
BogoMIPS: 4992.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 288 KiB (6 instances)
L1i: 192 KiB (6 instances)
L2: 7.5 MiB (6 instances)
L3: 18 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-11
```
## TODO: 在 Linux v6.1 測試 [BORE](https://github.com/firelzrd/bore-scheduler) 並解釋其原理
參見 [BORE (Burst-Oriented Response Enhancer) CPU Scheduler](https://hackmd.io/@foxhoundsk/bore-sched) 及 [BMQ 排程器研究](https://hackmd.io/@SmallHanley/linux2022-projects)，搭配《Demystifying the Linux CPU Scheduler》的第 3 章，在 Linux v6.1 (LTS) 重現實驗，解讀實驗數據，並評估是否該更新電子書描述。
> 留意 [BORE](https://github.com/firelzrd/bore-scheduler) 專案頁面的 "How it works"，已更新 BORE 的設計描述和相關圖表，其中 EEVDF 可參照 LWN: [An EEVDF CPU scheduler for Linux
](https://lwn.net/Articles/925371/)
### BORE（Burst-Oriented Response Enhancer）
是 CFS 和 EEVDF 的改進，在既有的程式碼基礎之上，儘快對應用程式作出回應。
BORE 為每個任務引入 `burstiness` ，稍微偏離 CFS 原有的 complete fairness 原則。 `Burstiness` 是指一個任務在明確放棄 CPU 後消耗的 CPU 時間所得出的分數，無論是進入睡眠、 I/O waiting 或放棄 CPU 資源。
利用這個 `burstiness` 指標，BORE 動態調整每個任務的權重和延遲。因此在不同類型負載的系統中，BORE 會優先處理需要快速回應的任務，以提高整體系統回應能力。
#### How it works
- 排程器會追蹤每個任務的 burst time，也就是任務從上次放棄 CPU 資源、睡眠或 I/O waiting 以來消耗的 CPU 時間。
- 當任務處於活動狀態時，透過正規化的 burst time 以及使用預設的偏移量跟係數來計算 burst score。
- burst score 的功能類似於 niceness ，介於 0-39 之間。當數值每減少 1，任務可以消耗大約 1.25 倍長的 timeslice。
- burst score 會影響剛睡醒任務搶佔目前執行任務的積極度。(只有 CFS 版本，EEVDF 版本沒有)。
- 較不貪婪的任務被賦予更多 timeslice 以及睡醒任務搶佔目前執行任務的積極度；貪婪任務則被賦予較少的權重。
- 最終是希望在各種工作負載共存的情況下，在 CPU-bound 與 I/O-bound 任務之間取得平衡，提高整體系統回應能力。
### BORE 程式碼解釋
>
BORE 主要實作於 `update_curr()` 中，用來更新目前行程在 CPU 上執行所花費的實際時間以及 vruntime
首先在 `include/linux/sched.h` 中的 [`struct sched_entity`](https://github.com/torvalds/linux/blob/master/include/linux/sched.h#L549) 增加以下成員
```diff
@@ -555,6 +555,12 @@ struct sched_entity {
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
+#ifdef CONFIG_SCHED_BORE
+ u64 prev_burst_time;
+ u64 burst_time;
+ u64 max_burst_time;
+ u8 penalty_score;
+#endif // CONFIG_SCHED_BORE
```
#### `update_curr()`
```diff=
@@ -905,6 +1005,14 @@ static void update_curr(struct cfs_rq *cfs_rq)
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);
+#ifdef CONFIG_SCHED_BORE
+ curr->burst_time += delta_exec;
+ curr->max_burst_time = max(curr->max_burst_time, curr->burst_time);
+ update_burst_score(curr);
+ if (sched_bore & 1)
+ curr->vruntime += penalty_scale(calc_delta_fair(delta_exec, curr), curr);
+ else
+#endif // CONFIG_SCHED_BORE
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);
```
- 第 6 行是更新 burst_time ，delta_exec 是指任務到目前為止的執行時間
- 第 7 行是更新 max_burst_time ，取 burst_time 與 max_burst_time 的最大值
- 若呼叫 `dequeue_task_fair()` 或 `yield_task_fair()` 函式時，會透過 `restart_burst()` 函式將 burst_time 與 prev_burst_time 做正規化（依照目前設定是相加除以二）來更新 max_burst_time
- 第 8 行是呼叫 `update_burst_score()` 函式來更新 burst_score
- 第 10 行是透過 `penalty_scale()` 函式來更新 vruntime
- 呼叫 `calc_delta_fair()` 函式來更新 vruntime
- 將 vruntime 乘上對 `sched_prio_to_wmult` 查表後得到的數值
- burst_score 越高，查表得到的數值越大，相乘後使得 vruntime 成長幅度越大
#### `update_burst_score()`
```diff=
+#define FIXED_SHIFT 10
+static void update_burst_score(struct sched_entity *se) {
+ u64 burst_time = se->max_burst_time;
+
+ int msb = fls64(burst_time);
+ fixed integer_part = msb << FIXED_SHIFT;
+ fixed fractional_part = burst_time << (64 - msb) << 1 >> (64 - FIXED_SHIFT);
+ fixed greed = integer_part | fractional_part;
+
+ fixed tolerance = sched_burst_penalty_offset << FIXED_SHIFT;
+ fixed penalty = max(0, (s32)greed - (s32)tolerance);
+ fixed scaled_penalty = penalty * sched_burst_penalty_scale >> 10;
+
+ u8 score = min(39U, scaled_penalty >> FIXED_SHIFT);
+ se->penalty_score = score;
+}
```
- 第 3 行是把 burst_time 設定成透過 `update_curr()` 函式中更新過的 max_burst_time
- 第 5 ~ 8 行是將 burst_time 以 2 為底取對數並加上 1
- integer_part 是以 2 為底取對數並加上 1 的結果
- fractional_part 是以 2 為底取對數時所失去的小數部份。最後會儲存在 `greed` 中較低位元的 `FIXED_SHIFT` 長度
- 第 11 行是將 `penalty` 設為 `greed` 減去 `tolerance` 並與 0 取 `max`
- `tolerance` 是透過預設的偏移量所計算出來
- `sched_burst_penalty_offset` 增加這個數值可防止較短 burst_time 的任務過於強大。
- 第 12 ~ 15 行是先對 `penalty` 做 scaling ，並右移 10 位將小數部份去掉，最後將該數值與 39 取 min 作為 burst score
- `sched_burst_penalty_scale` 增加這個數值會使 burst score 隨著 burst time 的增加而快速增長。導致 CPU-Bound 任務可能很難被執行到
### EEVDF (Earliest Eligible Virtual Deadline First)
某些行程可能不需要大量的 CPU 時間，但當行程需要 CPU 時間時，必須盡快分配給該行程。 CFS 沒有給行程表示 `latency requirements` 的方法，確保某些行程(即時任務)可以快速存取 CPU 。
與 CFS 一樣，EEVDF 會公平的分配 CPU 時間。較低的 nice value 具有較高優先級。
對於每個行程，EEVDF 計算行程本應獲得的時間與實際獲得的時間之間的差值，稱為 `lag` 。 具有 `positive lag value` 的行程表示未獲得其應獲得的時間，要比具有 `negative lag value` 的行程更早被排程到。
當行程的 `lag value` 大於等於 0 ，才會被認為是 `eligible` 。任何 `negative lag value` 行程都沒有資格運行。在未來某個時間，該行程本應獲得的時間追上實際獲得的時間，會再次被認為是 `eligible` ，該時間稱為 `eligible time` 。
> 依據[劍橋辭典](https://dictionary.cambridge.org/dictionary/english/eligible)，"eligible" 寓意是合格、具備特定資格者，用於 CPU 排程器就是挑選出有資格成為下個任務的候選者
`lag value` 的計算是 EEVDF 排程的關鍵部分，而另一個因素是 `virtual deadline` 。是行程收到其應有的 CPU 時間的最早時間，透過行程分配到的 timeslice 加上 `eligible time` 來計算的。 EEVDF 會優先執行 `virtual deadline` 最早的行程。
> 例如一個行程具有 10 ms timeslice，其 `eligible time` 為未來 20 ms，則 `virtual deadline` 為未來 30 ms。
具有較短 timeslice 的行程會有較小的 `virtual deadline` ，所以 EEVDF 會分配較短的 timeslice ，讓有 `latency requirements` 的行程優先執行，能夠快速回應事件。
### 重現 BORE 實驗
使用 `0001-linux6.1.y-bore2.2.8.patch` 補丁並重新編譯核心
```shell
$ patch -p1 -i 0001-linux6.1.y-bore2.2.8.patch
```
同時編譯另一個使用 EEVDF 排程器的核心。先使用 EEVDF 的補丁，接著再使用 EEVDF-BORE 的補丁
以 [`jitterdebugger`](https://github.com/igaw/jitterdebugger) 搭配 [`stress-ng`](https://wiki.ubuntu.com/Kernel/Reference/stress-ng) 測量， `jitterdebugger` 扮演的是 interactive task，而 `stress-ng` 扮演的則是背景工作負載。
> `jitterdebugger` 測量 wake up latency。
> `jitterdebugger` 在每個 CPU 上使用一個執行緒然後進行睡眠。在睡眠結束後，獲取當下 timestamp，也就是實際 wake up 時間，並與預期的 wake up 時間相減，即是 wake up latency
可以透過以下命令來切換要實驗的排程器
```shell
$ sudo sysctl -w kernel.sched_bore=3
```
若是基於 CFS 版本的 BORE
- 3 是 BORE
- 0 是 CFS
若是基於 EEVDF 版本的 BORE
- 1 是 BORE
- 0 是 EEVDF
產生在背景執行的工作負載以測試排程器並製圖。設定 stressor 個數為 48，測試 10 分鐘
```shell
$ sudo ./jitterdebugger -D 10m -c 'stress -c 48' -o result
$ ./jitterplot --output res.jpg hist result/results.json
```
- CFS 版本的 BORE
- CFS
- EEVDF 版本的 BORE
- EEVDF
上面為 `jitterdebugger` 的測量結果，橫軸為 scheduling latency，縱軸為次數。
由實驗結果可以看出 CFS 的 max scheduling latency 是所有排程器中最差的(cpu5 達到 1068)。而兩種版本的 BORE 多數的 max scheduling latency 都相當的低，表示 BORE 的確會優先處理需要快速回應的任務。而 avg scheduling latency 的表現其實所有排程器都差不多。
:::warning
TODO: 搭配上方排程器設計的描述，解讀實驗結果，特別是為何 EEVDF 與宣稱不同。
:notes: jserv
:::
## TODO: 理解 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 原理並實驗
INRIA 的 Julia Lawall 教授在 FOSDEM 2023 有場精彩的演講〈[Graphing tools for scheduler tracing](https://fosdem.org/2023/schedule/event/sched_tracing/)〉(內附簡報檔案和錄影)，談及 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 這工具，預期產出:
* 在本頁面介紹 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 原理
* 設計實驗 (對照《Demystifying the Linux CPU Scheduler》第 7 章)，並以 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 展現 CFS 排程行為
* 對照 [BORE](https://github.com/firelzrd/bore-scheduler) 和 CFS 行為，使用 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 展現
### 介紹 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 原理
> 參考資料 :
> * [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph)
> * [FOSDEM 2023 演講](https://fosdem.org/2023/schedule/event/sched_tracing/)
> * [Graphing Tools for Scheduler Tracing](https://inria.hal.science/hal-04001993/preview/RR-9498.pdf)
`trace-cmd` 是用於收集和視覺化追蹤執行的 `ftrace` 的前端工具。
我們主要使用的工具是 [`schedgraph`](https://gitlab.inria.fr/schedgraph/schedgraph)，由 `dat2graph` 和 `running_waiting` 組成。這兩個工具都依賴於 `trace-cmd`。
我們使用 `dat2graph` 和 `running_waiting` 而不是 `trace-cmd` 或是它的圖形化介面 `kernelshark` ，是因為較難追蹤擁有大量處理器核系統的排程器活動。
首先介紹一些名詞 :
- Work conservation : 如果有處理器核空閒，則不應使處理器核過載。也就是當一個任務準備好執行時，排程器應該傾向於將任務放在一個空閒的處理器核上，而不是放在有任務已經在執行的處理器核上。
- Locality : NUMA 機器的影響很大，其中處理器核對本地記憶體的存取速度較快，而對其他 NUMA 節點上的記憶體存取速度較慢。 work conservation 與 locality 會發生衝突，將任務放在目前空閒但位於不同 NUMA 節點的處理器核上，可能會降低存取速度。
:::warning
注意用語:
* kernel : 核心
* (processor) core : 處理器核 (避免寫「核心」)
> 了解，接下來會注意用語。
:::
`dat2graph` 和 `running_waiting` 分別提供在處理器核上的任務活動的視覺化，了解大型多核機器上排程器的行為。兩種不同的方法提供了互補的資訊 :
- `dat2graph2` : 了解何時、在哪個處理器核執行。只有顯示正在執行的任務，沒有顯示正在等待的任務。
- x 軸是執行時間(秒)
- y 軸是處理器核，顏色代表 PID
從上圖可以看出並非所有任務都在相同的處理器核上執行，例如接近 3 秒和 15 秒時，任務可能會移動到其他處理器核上或暫停執行。
若任務移動頻繁，可能會喪失 Locality。
- `running_waiting` : 有多少任務在執行或是等待
- x 軸是執行時間(秒)
- y 軸是任務數
- 綠線表示正在執行的任務數量
- 紅線表示可執行任務的數量，即正在執行與正在等待的任務
- 黑色水平虛線表示機器的處理器核數
如果紅線可視，即高於綠線，則表示某些可執行任務正在等待，即出現過載。
如果紅線在黑色虛線上方，則任務多於處理器核數，則過載是不可避免的。但如果紅線可視，且低於黑色虛線，則表示存在 Work conservation 問題，代表一些處理器核過載、但有些處理器核是空閒的。也就是上圖中 15 到 20 秒之間。
### 設計實驗並以 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 展現 CFS 排程行為
> 參考資料 :
> - [trace-cmd](https://github.com/rostedt/trace-cmd)
> - [Ocaml 安裝](https://ocaml.org/install)
> - [Ocaml 安裝手冊](https://ocaml.org/docs/up-and-running#first-steps-with-ocaml)
> - [jgraph](http://web.eecs.utk.edu/~jplank/plank/jgraph/jgraph.html)
#### 安裝必要工具
為了執行 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 專案，首先需要安裝一些必要的工具。
安裝 trace-cmd 以及相關套件
```shell
$ sudo apt-get install build-essential git pkg-config -y
$ sudo apt-get install libtracefs-dev libtraceevent-dev -y
$ git clone https://git.kernel.org/pub/scm/libs/libtrace/libtraceevent.git
$ cd libtraceevent
$ make
$ sudo make install
$ git clone https://git.kernel.org/pub/scm/libs/libtrace/libtracefs.git
$ cd libtracefs
$ make
$ sudo make install
$ git clone https://github.com/rostedt/trace-cmd.git
$ cd trace-cmd
$ make
$ sudo make install
$ sudo make install_libs
```
[schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 專案利用 OCaml 程式語言撰寫，所以我們需要安裝 OCaml 以及其套件管理器 opam
```shell
$ bash -c "sh <(curl -fsSL https://raw.githubusercontent.com/ocaml/opam/master/shell/install.sh)"
```
安裝完後對 opam 進行初始化，接著下載開發工具
```shell
$ opam init
$ opam install dune merlin ocaml-lsp-server odoc ocamlformat utop dune-release
```
安裝特定版本的 OCaml 並運行該版本
```shell
$ opam switch create 4.14.0
$ eval opam env
```
> 實驗過若下載 5.0.0 版本， schedgraph 目前不支援
確認版本是否正確
```shell
$ which ocaml
/home/howard/.opam/4.14.0/bin/ocaml
$ ocaml -version
The OCaml toplevel, version 4.14.0
```
安裝製圖工具
```shell
$ sudo apt-get install jgraph
$ sudo apt-get install ps2eps
$ sudo apt-get install texlive-font-utils
```
取得 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 專案程式碼
```shell
$ git clone https://gitlab.inria.fr/schedgraph/schedgraph.git
$ cd schedgraph
$ make all
```
#### 將行程固定在特定的 CPU 中執行
修改 /etc/default/grub 內的 `GRUB_CMDLINE_LINUX_DEFAULT` ，加入 `isolcpus=2,3` 來指定編號 2,3 的處理器核不會被排程器賦予任務，修改完成後需 `sudo update-grub` 來更新設定，最後重新開機
```shell
$ sudo vi /etc/default/grub
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=2,3"
$ sudo update-grub
$ sudo reboot
```
重新開機後檢查 CPU affinity
```shell
$ cat /sys/devices/system/cpu/isolated
2-3
```
#### 實驗
利用 `mktasks` 程式產生 workload ，並執行 `start.py` 來利用以下命令進行追蹤並產生對應的 `.dat` 檔案
```shell
$ sudo trace-cmd record -e sched -v -e sched_stat_runtime
```
- `record` : 記錄追蹤的事件
- `-e sched` : 追蹤所有排程相關的事件
- `-v -e sched_stat_runtime` : 忽略統計收集事件，因為它們數量多且與理解為什麼將任務放置在各個處理核上無關
接著利用 `dat2graph` 和 `running_waiting` 來產生追蹤事件的視覺化圖片
#### Difference between FIFO and RR
參數設定與書中第七章的設定一樣。首先分為兩組，每一組各有三個任務。執行的任務都是 CPU-bound 類型。第一組的任務利用 FIFO 排程，第二組的任務利用 RR 排程，並分別運行在處理核編號 3 跟 2 號。
使用下列命令來產生 `dat2graph` 圖片
```shell
$ ./dat2graph2 --save-tmp /path/to/fifo-rr-trace.dat
$ jgraph fifo-rr-trace.jgr | ps2eps -q -l -r 600 | epstopdf --filter > fifo-rr-trace.pdf
```
利用 `--save-tmp` 命令列引數來儲存產生的 jgraph 檔案，接著利用 jgraph 命令來將檔案轉換成 pdf 檔
可以看得很清楚處理核編號 3 的任務是利用 FIFO 來做排程，而處理核編號 2 的任務是利用 RR 來做排程。但仔細看的話可以發現在執行結束時，有出現非常小的點。所以我利用以下命令來放大來看
```shell
$ ./dat2graph2 --color-by-command --min 1.136 --max 1.138 --save-tmp /path/to/fifo-rr-trace.dat
$ jgraph fifo-rr-trace_color_from_1.315_upto_1.318_color.jgr | ps2eps -q -l -r 600 | epstopdf --filter > fifo-rr-trace_color_zoomin.pdf
```
`--color-by-command` 會根據正在執行的任務名稱來上色
可以發現任務執行結束時， kworker 會執行。所以我利用 kernelshark 去細看資訊時發現當任務執行結束時，kworker 會去執行 swapper 。因為沒有其它可執行的任務。
使用下列命令來產生 `running_waiting` 圖片
```shell
$ ./running_waiting --save-tmp --range 0.0-1.4 /path/to/fifo-rr-prio-trace.dat
$ jgraph fifo-rr-prio-trace_rw_from_0.0_upto_1.4.jgr | ps2eps -q -l -r 600 | epstopdf --filter > fifo-rr-prio-trace_rw.pdf
```
圖中可以看到有紅線，表示存在 Work conservation 問題，但是是正常的。因為我們只有在兩個處理核上執行任務，其它尚未被排程到的任務只能等待。
#### Priority of FIFO and RR
一樣分為兩組，每一組各有四個任務。執行的任務都是 CPU-bound 類型。第一組的任務利用 FIFO 排程，第二組的任務利用 RR 排程，且任務的優先權級分別為 97,98,98,99 ，並分別運行在處理核編號 3 跟 2 號。
觀察 `dat2graph` 圖片
處理核編號 3 號的任務一樣是利用 FIFO 來做排程，會按照優先權級依序執行。而處理核編號 2 號的任務是利用 RR 來做排程，會先執行優先權級最高的任務，然後因為有兩個任務的優先權級相同，所以當它們的 timeslice 消耗完時會切換執行，最後執行優先權級最低的任務。
一樣可以發現在執行結束時，有出現非常小的點，將這個部份放大來看。
一樣利用 kernelshark 來查看詳細資訊，因為沒有其它可執行的任務，所以 kworker 會去執行 swapper 。
觀察 `running_waiting` 圖片
一樣存在 Work conservation 問題，因為尚未被排程到的任務只能等待。
#### Block the FIFO
:::info
實驗過 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 必須將任務運行在多個處理核上，故讓處理器核編號 3 上也有執行任務，但任務內容為不做任何事。
:::
處理核編號 2 號有 I/O_block 跟 yield 類型的任務各兩個，皆是利用 FIFO 來做排程
觀察 `dat2graph` 圖片
因為任務數量較多搭配以下 `dat2graph` 圖片來觀察
可以發現在處理核編號 2 號上是依序執行 I/O_block 跟 yield 類型的任務。當任務進行 I/O 操作或是呼叫 `sched_yield` 時，會釋放 CPU 資源並讓下一個任務執行
觀察 `running_waiting` 圖片
同樣存在 Work conservation 問題
### 對照 [BORE](https://github.com/firelzrd/bore-scheduler) , [EEVDF](https://lwn.net/Articles/925371/) 和 CFS 行為，使用 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 展現
::: info
以下實驗皆有在處理器核編號 3 上執行任務，任務內容為不做任何事。僅為了能讓 [schedgraph](https://gitlab.inria.fr/schedgraph/schedgraph) 正常運作
而出現 unknown 是因為 trace-cmd 初始化的副作用所產生
:::
為了方便觀察 BORE , EEVDF 與 CFS 的排程行為，所以我設計以下三種實驗。分別是扮演使用 CPU 時間較長的 CPU-bound 類型的任務以及扮演使用 CPU 時間較少(會主動放棄 CPU )的任務，並都具有相同的優先權級
#### CPU-bound and yield
在處理器核編號 2 上執行的任務分別是 CPU-bound 與 yield 類型的任務
- CPU_bound 任務 : 在 main 函數中有一個 for 迴圈，每次迭代都會進行矩陣乘法，共迭代四次
- yield 任務 : 與 CPU-bound 任務相同，只是每次迭代進行矩陣乘法後，會呼叫 `sched_yield` 主動放棄處理器資源
#### BORE
#### EEVDF
#### CFS
由實驗結果可以看出當每次輪到 yield 類型的任務使用 CPU 資源時， BORE 會給予更多的 timeslice (因為可以看到最後面 CPU-bound 任務使用一大段時間的 CPU 資源，表示 yield 類型的任務被給予更多的 timeslice)，所以 yield 類型的任務會比 CPU-bound 類型的任務還要早執行完成。因為優先權級一樣，所以 EEVDF 會公平的分配 CPU 時間，但可以發現 EEVDF 非常頻繁的切換執行，因為 EEVDF 的 timeslice 較短。最後 CFS 則是非常公平的平均分配 timeslice 給兩種任務。
#### CPU-bound and sleep
在處理器核編號 2 上執行的任務分別是 CPU-bound 與 sleep 類型的任務
- CPU_bound 任務 : 迭代進行矩陣乘法
- sleep 任務 : 每次迭代進行矩陣乘法後，會呼叫 `usleep(1)` 讓任務去睡眠 1 微秒
#### BORE
#### EEVDF
#### CFS
由實驗結果可以看出每次輪到 sleep 類型的任務使用 CPU 資源時， BORE 同樣給予更多的 timeslice (可以看到最後面 CPU-bound 任務使用一大段時間的 CPU 資源)。同樣的 EEVDF 非常頻繁的切換執行，同時公平分配 CPU 時間。而 CFS 則是平均分配 timeslice 。
#### CPU-bound and I/O_block
在處理器核編號 2 上執行的任務分別是 CPU-bound 與 I/O_block 類型的任務
- CPU-bound 任務 : 迭代進行矩陣乘法
- I/O_block 任務 : 每次迭代進行矩陣乘法後，會進行 I/O 操作
#### BORE
#### EEVDF
#### CFS
由實驗結果可以看出每次輪到 I/O_block 類型的任務使用 CPU 資源時， BORE 有給予更多的 timeslice ，所以執行過程中沒有出現 idle 。同樣的 EEVDF 非常頻繁的切換執行，且當 I/O_block 類型的任務完成寫檔後，又繼續與 CPU-bound 任務公平分配 CPU 時間，因為具有相同的優先權級。而 CFS 則是因為平均分配 timeslice ，導致有 idle 的情況發生。因為 CPU-bound 任務已經完成，但是 I/O_block 任務還在進行 I/O 操作且尚未完成。
::: info
結論 : BORE 會讓長時間使用 CPU 資源的任務賦予它更高的 vruntime ，所以該任務會較不容易被排程到。而使用 CPU 資源較少的任務會有較高的 burst score ，也就是會被賦予更多的 timeslice 並且會增加搶佔目前執行任務的積極度。
:::
:::warning
TODO: 針對 EEVDF 進行實驗，可能需要更新的 Linux 核心: [linux-cachyos](https://github.com/CachyOS/linux-cachyos)。BORE 的作者在 CachyOS 的 Telegram 很活躍。
:::
### [BORE 及 schedgraph 的英文描述](https://hackmd.io/@linhoward0522/HyHb3BsPh)
## TODO: 探討 CPU 排程器延遲的議題
研讀以下技術報告和論文:
* [Reducing CPU scheduler latency in Linux](https://www.diva-portal.org/smash/get/diva2:1630380/FULLTEXT01.pdf)
* [Reducing latency spikes by tuning the CPU scheduler](https://www.scylladb.com/2016/06/10/read-latency-and-scylla-jmx-process/)
* [Efficient Scheduler Live Update for Linux Kernel with Modularization](https://dl.acm.org/doi/abs/10.1145/3582016.3582054)
解讀 CPU 排程器的延遲和調整機制，分析如何設計實驗來理解實作的表現。
### 解讀 CPU 排程器的延遲和調整機制
> 參考資料 :
> - [perf 用法](https://jasonblog.github.io/note/linux_tools/perf_--_linuxxia_de_xi_tong_xing_neng_diao_you_gon2.html)
> - [perf bench](https://man7.org/linux/man-pages/man1/perf-bench.1.html)
> - [sysctl output changed from kernel 5.10 to 5.13](https://forum.endeavouros.com/t/sysctl-output-changed-from-kernel-5-10-to-5-13-why/17097)
> - [hackbench](https://lkml.iu.edu//hypermail/linux/kernel/0112.1/0702.html)
排程延遲 : 當一個行程可以運行卻不能有進展，因為排程器將 CPU 時間分配給其它不同的行程
首先在處理器核編號 2,3 號上使用 [stress](https://linux.die.net/man/1/stress) 來各產生 2 個 CPU-bound 任務，並且利用 taskset 將其指定到對應的處理器核編號上
```shell
$ taskset -c 2 stress -c 2
$ taskset -c 3 stress -c 2
```
接著我們利用 [perf](https://perf.wiki.kernel.org/index.php/Main_Page) 來觀察排程延遲的時間，並利用 `sudo perf sched latency` 來產生報告
```shell
$ sudo perf sched record -C 2,3 sleep 10
$ sudo perf sched latency
```
- `sched` 表示獲取排程相關的資訊
- `record` 紀錄資訊
- `-C` 指定收集該處理器核的資訊
- `sleep` 表示要收集幾秒鐘
以下是收集 10 秒鐘的結果
- CFS
```
-------------------------------------------------------------------------------------------------------------------------------------------
Task | Runtime ms | Switches | Avg delay ms | Max delay ms | Max delay start | Max delay end |
-------------------------------------------------------------------------------------------------------------------------------------------
stress:(4) | 20001.528 ms | 1255 | avg: 15.907 ms | max: 16.008 ms | max start: 101497.845449 s | max end: 101497.861457 s
migration/3:34 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
migration/2:28 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
-----------------------------------------------------------------------------------------------------------------
TOTAL: | 20001.528 ms | 1257 |
---------------------------------------------------
```
- BORE
```
-------------------------------------------------------------------------------------------------------------------------------------------
Task | Runtime ms | Switches | Avg delay ms | Max delay ms | Max delay start | Max delay end |
-------------------------------------------------------------------------------------------------------------------------------------------
stress:(4) | 20001.590 ms | 3308 | avg: 6.042 ms | max: 8.014 ms | max start: 101527.792998 s | max end: 101527.801012 s
migration/3:34 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
migration/2:28 | 0.000 ms | 1 | avg: 0.000 ms | max: 0.000 ms | max start: 0.000000 s | max end: 0.000000 s
-----------------------------------------------------------------------------------------------------------------
TOTAL: | 20001.590 ms | 3310 |
---------------------------------------------------
```
可以看出 CFS 的平均以及最大排程延遲時間都大於 BORE 的數值，因為 BORE 會比較快回應任務，所以 BORE 的切換次數遠高於 CFS
所以我想透過調整 CFS 的排程器參數，來實驗看看是否這些參數會影響排程延遲的時間
首先，進入 root 權限並列出所有 CFS 的排程器參數
```shell
$ cd /sys/kernel/debug/sched/
$ ls
debug latency_warn_ms numa_balancing
domains latency_warn_once preempt
features migration_cost_ns tunable_scaling
idle_min_granularity_ns min_granularity_ns verbose
latency_ns nr_migrate wakeup_granularity_
```
> 現在使用 `sudo sysctl -a | grep "sched" | grep -v "domain"` 命令僅能列出以下資訊 :
>```
>kernel.sched_autogroup_enabled = 1
>kernel.sched_cfs_bandwidth_slice_us = 5000
>kernel.sched_child_runs_first = 0
>kernel.sched_deadline_period_max_us = 4194304
>kernel.sched_deadline_period_min_us = 100
>kernel.sched_energy_aware = 1
>kernel.sched_rr_timeslice_ms = 100
>kernel.sched_rt_period_us = 1000000
>kernel.sched_rt_runtime_us = 950000
>kernel.sched_schedstats = 0
>kernel.sched_util_clamp_max = 1024
>kernel.sched_util_clamp_min = 1024
>kernel.sched_util_clamp_min_rt_default = 1024
>```
我使用 `sched_min_granularity_ns` , `sched_wakeup_granularity_ns` 這兩個參數來進行實驗
- `sched_min_granularity_ns` : 表示分配給每個任務 timeslice 的下限，也就是每個任務被搶佔之前能夠執行的最短時間。
目前預設值為 : 3000000 ns
- `sched_wakeup_granularity_ns` : 表示當另外一個任務睡醒時，會延遲當前正在執行任務的搶佔，目的是為了不要頻繁的排程。所以在設定的範圍內，非常接近當前任務 vruntime 數值的任務不會搶佔當前任務。
目前預設值為 : 4000000 ns
### 設計實驗
為了進行測量排程延遲的時間，我使用 [hackbench](https://lkml.iu.edu//hypermail/linux/kernel/0112.1/0702.html) 工具來進行實驗。 [hackbench](https://lkml.iu.edu//hypermail/linux/kernel/0112.1/0702.html) 是在核心中透過 IPC 的方式來測量延遲的工具。 [hackbench](https://lkml.iu.edu//hypermail/linux/kernel/0112.1/0702.html) 會建立幾對任務，同一組內的任務可以互相通訊。這些任務來回通訊，而延遲即是每對任務通訊的時間。
我寫了一隻測試程式，調整 `sched_min_granularity_ns` , `sched_wakeup_granularity_ns` 數值的同時，使用以下命令來測量排程延遲的時間
> [測試程式](https://github.com/linhoward0522/Latency_test)
```shell
$ sudo perf record -e sched:* perf bench sched messaging -p -t -g 20 -l 1000
$ sudo perf sched latency
```
- `-p` : 透過使用 pipe 來消除 socket communication 的開銷
- `-t` : 透過使用執行緒來消除建立行程的開銷
- `-g` : 指定組的數量。每一組裡面各有 20 個 sender 跟 receiver 執行緒。同組的任務互相通訊
- `-l` : 指定通訊次數
#### sched_min_granularity_ns
- 執行時間
- 平均延遲時間
- 最大延遲時間
#### sched_wakeup_granularity_ns
- 執行時間
- 平均延遲時間
- 最大延遲時間
:::info
由以上實驗可以觀察出，調整 `sched_min_granularity_ns` 數值似乎對於執行時間或是平均,最大延遲時間沒有太大的影響。反而是調整 `sched_wakeup_granularity_ns` 數值比較有影響。
當 `sched_wakeup_granularity_ns` 數值越高時，執行時間與最大延遲時間越低。而 `sched_wakeup_granularity_ns` 數值介於 5000000 ~ 20000000 ns 時平均延遲時間的表現比較好。因為透過減少了不必要的搶佔來提昇效能。
:::
#### sched_min_granularity_ns vs sched_wakeup_granularity_ns
- 執行時間
- 平均延遲時間
- 最大延遲時間
:::info
同時調整 `sched_min_granularity_ns` , `sched_wakeup_granularity_ns`數值。對於執行時間來說，調整 `sched_wakeup_granularity_ns` 數值比較有影響。而對於平均延遲時間來說， `sched_wakeup_granularity_ns` 數值介於 5000000 ~ 15000000 ns 時較好，與調整 `sched_min_granularity_ns` 較無關連。最後是對於最大延遲時間， `sched_wakeup_granularity_ns` 數值越高時，最大延遲時間較好。同樣是因為透過減少不必要的搶佔來提昇效能。
:::
Sign in with Wallet
Connect another wallet