Linux 核心專題: CPU 排程器研究

執行人: linhoward0522
專題解說錄影

提問清單

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 來各產生 2 個 CPU-bound 任務，並且利用 taskset 將其指定到對應的處理器核編號上
我利用 perf 來簡單觀察一下，以下是收集 10 秒鐘的結果

 -------------------------------------------------------------------------------------------------------------------------------------------
  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 及 schedgraph 的描述，採用 Linux v6.1。

事前準備

Demystifying the Linux CPU Scheduler 筆記

更新至 Linux v6.1

後來發現應該要使用自行編譯的 Linux 核心，改用以下方法：

查看目前版本

$ uname -mrs
Linux 5.19.0-41-generic x86_64

更新所有 package

$ sudo apt update

新增 cappelikan repository 以及下載 Ubuntu Mainline Kernel Installer

$ sudo add-apt-repository ppa:cappelikan/ppa -y
$ sudo apt install mainline -y

打開 Ubuntu Mainline Kernel Installer 找出所需要的版本並安裝，最後重開機即可

$ uname -mrs
Linux 6.1.28-060128-generic x86_64

下載需要的套件

$ sudo apt install gcc make libncurses-dev flex bison libssl-dev libelf-dev initramfs-tools-bin

下載指定的核心版本並解壓縮

$ 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 檔

$ cd linux-6.1.29
$ cp /boot/config-5.19.0-41-generic .config

建立編輯選單，進入選單後將 config 檔載入

$ make menuconfig

選擇 load .config
選擇 save .config
按兩次 ESC 離開選單

修改 .config 檔案，將下列兩行內容刪除，如下所示

$ vim .config
CONFIG_SYSTEM_TRUSTED_KEYS=""
CONFIG_SYSTEM_REVOCATION_KEYS=""

編譯模組，安裝核心後重開機

$ make -j 8
$ sudo make modules_install
$ sudo make install
$ sudo reboot

確認是否安裝成功

$ uname -mrs
Linux 6.1.29 x86_64

開發環境

$ 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 並解釋其原理

參見 BORE (Burst-Oriented Response Enhancer) CPU Scheduler 及 BMQ 排程器研究，搭配《Demystifying the Linux CPU Scheduler》的第 3 章，在 Linux v6.1 (LTS) 重現實驗，解讀實驗數據，並評估是否該更新電子書描述。

留意 BORE 專案頁面的 "How it works"，已更新 BORE 的設計描述和相關圖表，其中 EEVDF 可參照 LWN: An EEVDF CPU scheduler for Linux

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 增加以下成員

@@ -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()`














@@ -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()`
















+#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 。

依據劍橋辭典，"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 補丁並重新編譯核心

$ patch -p1 -i 0001-linux6.1.y-bore2.2.8.patch

同時編譯另一個使用 EEVDF 排程器的核心。先使用 EEVDF 的補丁，接著再使用 EEVDF-BORE 的補丁

以 jitterdebugger 搭配 stress-ng 測量， jitterdebugger 扮演的是 interactive task，而 stress-ng 扮演的則是背景工作負載。

jitterdebugger 測量 wake up latency。
jitterdebugger 在每個 CPU 上使用一個執行緒然後進行睡眠。在睡眠結束後，獲取當下 timestamp，也就是實際 wake up 時間，並與預期的 wake up 時間相減，即是 wake up latency

可以透過以下命令來切換要實驗的排程器

$ sudo sysctl -w kernel.sched_bore=3

若是基於 CFS 版本的 BORE

3 是 BORE
0 是 CFS

若是基於 EEVDF 版本的 BORE

1 是 BORE
0 是 EEVDF

產生在背景執行的工作負載以測試排程器並製圖。設定 stressor 個數為 48，測試 10 分鐘

$ 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 的表現其實所有排程器都差不多。

TODO: 搭配上方排程器設計的描述，解讀實驗結果，特別是為何 EEVDF 與宣稱不同。
jserv

TODO: 理解 schedgraph 原理並實驗

INRIA 的 Julia Lawall 教授在 FOSDEM 2023 有場精彩的演講〈Graphing tools for scheduler tracing〉(內附簡報檔案和錄影)，談及 schedgraph 這工具，預期產出:

在本頁面介紹 schedgraph 原理
設計實驗 (對照《Demystifying the Linux CPU Scheduler》第 7 章)，並以 schedgraph 展現 CFS 排程行為
對照 BORE 和 CFS 行為，使用 schedgraph 展現

介紹 schedgraph 原理

參考資料 :

schedgraph

FOSDEM 2023 演講

Graphing Tools for Scheduler Tracing

trace-cmd 是用於收集和視覺化追蹤執行的 ftrace 的前端工具。

我們主要使用的工具是 schedgraph，由 dat2graph 和 running_waiting 組成。這兩個工具都依賴於 trace-cmd。

我們使用 dat2graph 和 running_waiting 而不是 trace-cmd 或是它的圖形化介面 kernelshark ，是因為較難追蹤擁有大量處理器核系統的排程器活動。

首先介紹一些名詞 :

Work conservation : 如果有處理器核空閒，則不應使處理器核過載。也就是當一個任務準備好執行時，排程器應該傾向於將任務放在一個空閒的處理器核上，而不是放在有任務已經在執行的處理器核上。
Locality : NUMA 機器的影響很大，其中處理器核對本地記憶體的存取速度較快，而對其他 NUMA 節點上的記憶體存取速度較慢。 work conservation 與 locality 會發生衝突，將任務放在目前空閒但位於不同 NUMA 節點的處理器核上，可能會降低存取速度。

注意用語:

kernel : 核心
(processor) core : 處理器核 (避免寫「核心」)

了解，接下來會注意用語。

dat2graph 和 running_waiting 分別提供在處理器核上的任務活動的視覺化，了解大型多核機器上排程器的行為。兩種不同的方法提供了互補的資訊 :

dat2graph2 : 了解何時、在哪個處理器核執行。只有顯示正在執行的任務，沒有顯示正在等待的任務。
- x 軸是執行時間(秒)
- y 軸是處理器核，顏色代表 PID

從上圖可以看出並非所有任務都在相同的處理器核上執行，例如接近 3 秒和 15 秒時，任務可能會移動到其他處理器核上或暫停執行。
若任務移動頻繁，可能會喪失 Locality。

running_waiting : 有多少任務在執行或是等待
- x 軸是執行時間(秒)
- y 軸是任務數
- 綠線表示正在執行的任務數量
- 紅線表示可執行任務的數量，即正在執行與正在等待的任務
- 黑色水平虛線表示機器的處理器核數

如果紅線可視，即高於綠線，則表示某些可執行任務正在等待，即出現過載。
如果紅線在黑色虛線上方，則任務多於處理器核數，則過載是不可避免的。但如果紅線可視，且低於黑色虛線，則表示存在 Work conservation 問題，代表一些處理器核過載、但有些處理器核是空閒的。也就是上圖中 15 到 20 秒之間。

設計實驗並以 schedgraph 展現 CFS 排程行為

參考資料 :

trace-cmd

Ocaml 安裝

Ocaml 安裝手冊

jgraph

安裝必要工具

為了執行 schedgraph 專案，首先需要安裝一些必要的工具。

安裝 trace-cmd 以及相關套件

$ 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 專案利用 OCaml 程式語言撰寫，所以我們需要安裝 OCaml 以及其套件管理器 opam

$ bash -c "sh <(curl -fsSL https://raw.githubusercontent.com/ocaml/opam/master/shell/install.sh)"

安裝完後對 opam 進行初始化，接著下載開發工具

$ opam init
$ opam install dune merlin ocaml-lsp-server odoc ocamlformat utop dune-release

安裝特定版本的 OCaml 並運行該版本

$ opam switch create 4.14.0
$ eval opam env

實驗過若下載 5.0.0 版本， schedgraph 目前不支援

確認版本是否正確

$ which ocaml
/home/howard/.opam/4.14.0/bin/ocaml
$ ocaml -version
The OCaml toplevel, version 4.14.0

安裝製圖工具

$ sudo apt-get install jgraph
$ sudo apt-get install ps2eps
$ sudo apt-get install texlive-font-utils

取得 schedgraph 專案程式碼

$ 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 來更新設定，最後重新開機

$ sudo vi /etc/default/grub
GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=2,3"
$ sudo update-grub
$ sudo reboot

重新開機後檢查 CPU affinity

$ cat /sys/devices/system/cpu/isolated 
2-3

實驗

利用 mktasks 程式產生 workload ，並執行 start.py 來利用以下命令進行追蹤並產生對應的 .dat 檔案

$ 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 圖片

$ ./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 來做排程。但仔細看的話可以發現在執行結束時，有出現非常小的點。所以我利用以下命令來放大來看

$ ./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 圖片

$ ./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

實驗過 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 , EEVDF 和 CFS 行為，使用 schedgraph 展現

以下實驗皆有在處理器核編號 3 上執行任務，任務內容為不做任何事。僅為了能讓 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

Image Not Showing Possible Reasons

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

Learn More →

EEVDF

CFS

Image Not Showing Possible Reasons

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

Learn More →

由實驗結果可以看出當每次輪到 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 操作且尚未完成。

結論 : BORE 會讓長時間使用 CPU 資源的任務賦予它更高的 vruntime ，所以該任務會較不容易被排程到。而使用 CPU 資源較少的任務會有較高的 burst score ，也就是會被賦予更多的 timeslice 並且會增加搶佔目前執行任務的積極度。

TODO: 針對 EEVDF 進行實驗，可能需要更新的 Linux 核心: linux-cachyos。BORE 的作者在 CachyOS 的 Telegram 很活躍。

BORE 及 schedgraph 的英文描述

TODO: 探討 CPU 排程器延遲的議題

研讀以下技術報告和論文:

解讀 CPU 排程器的延遲和調整機制，分析如何設計實驗來理解實作的表現。

解讀 CPU 排程器的延遲和調整機制

參考資料 :

perf 用法

perf bench

sysctl output changed from kernel 5.10 to 5.13

hackbench

排程延遲 : 當一個行程可以運行卻不能有進展，因為排程器將 CPU 時間分配給其它不同的行程

首先在處理器核編號 2,3 號上使用 stress 來各產生 2 個 CPU-bound 任務，並且利用 taskset 將其指定到對應的處理器核編號上

$ taskset -c 2 stress -c 2
$ taskset -c 3 stress -c 2

接著我們利用 perf 來觀察排程延遲的時間，並利用 sudo perf sched latency 來產生報告

$ sudo perf sched record -C 2,3 sleep 10
$ sudo perf sched latency

sched 表示獲取排程相關的資訊
record 紀錄資訊
-C 指定收集該處理器核的資訊
sleep 表示要收集幾秒鐘

以下是收集 10 秒鐘的結果

 -------------------------------------------------------------------------------------------------------------------------------------------
  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 的排程器參數

$ 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 工具來進行實驗。 hackbench 是在核心中透過 IPC 的方式來測量延遲的工具。 hackbench 會建立幾對任務，同一組內的任務可以互相通訊。這些任務來回通訊，而延遲即是每對任務通訊的時間。

我寫了一隻測試程式，調整 sched_min_granularity_ns , sched_wakeup_granularity_ns 數值的同時，使用以下命令來測量排程延遲的時間

測試程式

$ 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

執行時間
平均延遲時間
最大延遲時間

由以上實驗可以觀察出，調整 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

執行時間
平均延遲時間
最大延遲時間

同時調整 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 數值越高時，最大延遲時間較好。同樣是因為透過減少不必要的搶佔來提昇效能。