# 開發紀錄 (2): FCFS/RR scheduler
> [Repo](https://github.com/cce-underdogs/scx/tree/otteryc_exp) : 重現 FIFO/RR scheduler 實驗, with Rust :crab:
contributed by < [`charliechiou`](https://github.com/charliechiou) > < [`EricccTaiwan`](https://github.com/EricccTaiwan) >
<!-- :::danger
## 問題
1. $NICE$ 值不對，全部都是 0
* 根據 Andrea 建議，改用 task.weight 取代
* 至於為什麼無法讀取，有待釐清
2. Time slice 的表現錯誤，目前也沒有辦法驗證
::: -->
## 產生 trace 檔案
**Terminal 1**
```shell
$ # scxtop
$ sudo LC_ALL=C scxtop
$ # 按下 a 錄製 perfetto 檔案
```
**Terminal 2**
```shell
$ # stress-ng
$ stress-ng --cpu 3 --verbose
```
**Terminal 3**
```shell
$ # scx
$ sudo ./bin/scx_rlfifo
```
接著便可用 perfetto UI 開啟
流程影片 : https://www.youtube.com/watch?v=tIEW7PNKnR4
## 實測 scx_rlfifo
實際跑測試，用 [Perfetto](https://perfetto.dev/) 視覺化排程
開啟 `scx_rlfifo` 前
開啟 `scx_rlfifo` 後
:::warning
問題 : 如果不能鎖定只使用 1 個 CPU，task 就可以做 migrate ，這樣如何確認其 fifo 的特性 ?
=> 要試著限制 CPU migration，stress-ng 可以透過 `--taskset CPU_NUM` 的方式來把任務綁定在 CPU_NUM 的 CPU 上。
:::
## stress-ng
單看上述的實驗結果無法分辨有沒有真的成功，需要加入額外的 workload 做測試。使用 [stress-ng](https://github.com/ColinIanKing/stress-ng?tab=readme-ov-file) 來測試。
```shell
$ stress-ng --cpu 3 --verbose
```
增加三個 cpu 的 workload ，並觀察輸出如下
- 未使用 scx_lavd 前，有三個 workload 產生分別為 [59042][59043][59044] 。
重點觀察 [59042]
- 使用 scx_lavd 後
同樣重點觀察 [59042]
可以實際看見使用 scx_lavd 的排程結果，會設定 time slice ， 時間到便將任務 sleep，因此和未載入前相比較為零碎。
## 改寫 `scx_rlfifo`
> Commit [`ac88851`](https://github.com/sched-ext/scx/commit/ac888518da46bc1e0eefd3a72bf3bd5bcd7ee2e8)
**參照 [Linux 核心專題: sched_ext 研究 (by otteryc)](https://hackmd.io/@sysprog/H1u6D9LI0)**
因為要限制 CPU migration ，因此做了以下的更動
```diff
let cpu = self.bpf.select_cpu(task.pid, task.cpu, task.flags);
- dispatched_task.cpu = if cpu >= 0 { cpu } else { task.cpu };
+ dispatched_task.cpu = task.cpu;
```
以下重現 otteryc 期末專題的設計概念：
* 當 $NICE \lt 0$ 時，執行 FIFO
* 當 $NICE \geq 0$ 時，執行 Round Robin (Time Slice = 50 $\mu$s)
---
### exp 1
> Follow otteryc
```rust
if nice < 0 {
// Nice < 0 => Treat as FIFO
self.served_fifo += 1;
dispatched_task.slice_ns = u64::MAX;
} else {
// Nice >= 0 => Treat as RR
self.served_rr += 1;
// dispatched_task.slice_ns = SLICE_NS / (nr_waiting + 1);
dispatched_task.slice_ns = SLICE_NS / 50_000; // 固定 rr 大小
}
```
### exp 2
> 變體: rr 的 Time Slice 由須排程的 task 數量所決定
```rust
// Get the amount of tasks that are waiting to be scheduled.
let nr_waiting = *self.bpf.nr_queued_mut();
```
```rust
if nice < 0 {
// Nice < 0 => Treat as FIFO
self.served_fifo += 1;
dispatched_task.slice_ns = u64::MAX;
} else {
// Nice >= 0 => Treat as RR
self.served_rr += 1;
dispatched_task.slice_ns = SLICE_NS / (nr_waiting + 1);
}
```
上述兩項的 Perfetto 輸出圖無法有效確認是否有按照我們所想的不同的 nice 值設定不同的排程方式，且可以發現程式碼無法正確讀取到 nice 值的設定。
---
### 改善實驗
和 jserv 老師討論後修正實驗設計，應該考量 scx 的時間分配是否正確運作，因此修改 stress-ng 所產生的 workflow 如下，透過限制 workflow 的時間為 1 sec 並使用 watch 不斷產生 task 。
```shell
$ sudo watch nice -n -5 stress-ng --cpu 1 --timeout 1s
```
重複安排 1 sec 的任務並將 NICE 值設定為 -5，觀察以下結果並配合 `htop` 確認 NICE 數值有正確被設定。
實驗發現，雖然在 `htop` 中有正確的設定 NICE 數值，但 scx_rlfifo 中無論將 NICE 值設定成 5 或是 -5 讀取到的值皆為 0 。
>In this case you can simply use task.weight which is determined as a function of task's nice (see https://web.git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/sched/core.c#n10148 for detils)
>[name=Andrea Righi]
在向其他 scx_ext 的開發人員 ([`arighi`](https://github.com/arighi)) 詢問後得知，可以**使用 `task.weight` 做代替**，`task.weight` 為 NICE 值的映射。
接著為了測試是否能夠有效的取得 weight 數值，將程式碼做以下改變，讀取 `task.weight` 數值並輸出 PID 及對應的 weight 值。
```rust
let nice = task.weight;
println!("PID={} weight={}", task.pid, nice);
```
分別測試以下兩種不同 NICE 值，並使用 `grep` 過濾出指定的 PID 方便觀察。
#### NICE = -5
```rust
$ sudo nice -n -5 stress-ng --cpu 1
stress-ng: info: [250733] defaulting to a 1 day run per stressor
stress-ng: info: [250733] dispatching hogs: 1 cpu
```
執行結果：
```rust
$ sudo ./bin/scx_rlfifo | grep "250734"
PID=250734 weight=305
PID=250734 weight=305
PID=250734 weight=305
PID=250734 weight=305
...
```
#### NICE = 5
```rust
$ sudo nice -n 5 stress-ng --cpu 1
stress-ng: info: [250928] defaulting to a 1 day run per stressor
stress-ng: info: [250928] dispatching hogs: 1 cpu
```
執行結果：
```rust
$ sudo ./bin/scx_rlfifo | grep "250929"
PID=250929 weight=33
PID=250929 weight=33
PID=250929 weight=33
PID=250929 weight=33
...
```
透過上述實驗可以發現，當 NICE 值越小優先度越高，因此所設定的權重 `weight` 也越大，反之亦然。而對應關係是透過 cgroup weight，而非直接使用 prio_to_wight 。
> The weight used by sched_ext is the same as the "cgroup weight", after resolving the weight from prio_to_weight[] the value is normalized in the cgroup weight range [1 .. 10000], where 100 is the logarithmic center (so 1024 becomes 100). Search for [sched_weight_to_cgroup()](https://elixir.bootlin.com/linux/v6.14.5/source/kernel/sched/sched.h#L268), [CGROUP_WEIGHT_MIN](https://elixir.bootlin.com/linux/v6.14.5/source/include/linux/cgroup.h#L33) and [CGROUP_WEIGHT_MAX](https://elixir.bootlin.com/linux/v6.14.5/source/include/linux/cgroup.h#L33)
<!-- ### exp 1
> Follow otteryc
$NICE$ = 0 <-> `task.weight` = 100
* 當 `tast.weight` > 100 ($NICE \lt 0$) 時，執行 FIFO
* 當 `tast.weight` <= 100 ($NICE \geq 0$) 時，執行 Round Robin
```rust
if t_weight > 100 {
// Nice < 0 => Treat as FIFO
self.served_fifo += 1;
dispatched_task.slice_ns = u64::MAX;
} else {
// Nice >= 0 => Treat as RR
self.served_rr += 1;
// dispatched_task.slice_ns = SLICE_NS / (nr_waiting + 1);
dispatched_task.slice_ns = 500_000_000; // 0.5 s = 500 ms
}
```
#### 生成 perfetto
```$
sudo scxtop trace --trace-ms 5000 --output-file test
```
#### NICE < 0
workflow : `$ sudo watch nice -n -5 stress-ng --cpu 1 --timeout 1s`
輸出結果：
#### NICE > 0
workflow : `$ sudo watch nice -n 5 stress-ng --cpu 1 --timeout 1s `
輸出結果：
### exp 2 -->
## 問題
:::warning
如何實際用指標計算排程效率 ? Throughput ? Latency ? 或單純計算執行時間就好 ?
=> 目前先著重在實驗的重現，驗證程式碼確實是 rr 的
電腦可能同時有很多其餘執行序在跑，如何確保每次實驗執行環境都相同？
=> 只能透過 p-value 確保其他因素是不顯著的
---
scx_rlfifo 的啟動時機？
=>
context_switch 的時間會計算在前一個任務還是後一個任務？
=>
:::
## After office-hours 測試
### RR test
$NICE = 5$
```shell
$ watch -n 5 '
nice -n 5 taskset -c 3 bash -c "
stress-ng --cpu 1 --timeout 2s &
stress-ng --cpu 1 --timeout 2s &
stress-ng --cpu 1 --timeout 2s &
wait
"'
```
因為 $NICE \ge 0$ ，因此預期為 RR 和 time slice 10 ms
發現 stress-ng 的最小單位確實是 10ms，但同時卻觀察到有 20ms, 30ms 的出現，這明顯不符合應該全部 time slice 皆是 10ms 的期待。
>根據 office-hour 詢問的結果， perfetto 會紀錄 task 的執行，因此同任務第一個 time slice 及 第二個 time slice 中間並未有其他任務產生 (i.e., 未有 context switch) 則兩者會顯示在一起，出現形如 20 ms 或 30 ms 的結果。
為了更進一步測試，我們增加 stress-ng 分派的任務，改為一次分派 6 個 task 。預期 Avg Wall duration(ms) 會因為更頻繁的交換任務而降低兩個 time slice 相連的現象。
可以發現確實每個任務相較於前次實驗的 16.9, 12.9, 14.1 更為接近理想的 10 ms 。
#### schedbrench
未使用
```shell
$ taskset -c 3 nice -n 5 ./schbench/schbench -t 6 -r 2
Wakeup Latencies percentiles (usec) runtime 2 (s) (1145 total samples)
50.0th: 5160 (524 samples)
90.0th: 6872 (234 samples)
* 99.0th: 7048 (63 samples)
99.9th: 8880 (10 samples)
min=1, max=9008
Request Latencies percentiles (usec) runtime 2 (s) (1145 total samples)
50.0th: 5160 (466 samples)
90.0th: 7016 (336 samples)
* 99.0th: 27744 (103 samples)
99.9th: 32960 (10 samples)
min=1868, max=40500
RPS percentiles (requests) runtime 2 (s) (3 total samples)
20.0th: 0 (1 samples)
* 50.0th: 563 (1 samples)
90.0th: 573 (1 samples)
min=562, max=572
average rps: 572.50
```
使用 rr
```shell
$ taskset -c 3 nice -n 5 ./schbench/schbench -t 6 -r 2
Wakeup Latencies percentiles (usec) runtime 2 (s) (207 total samples)
50.0th: 2002 (62 samples)
90.0th: 7064 (79 samples)
* 99.0th: 29024 (18 samples)
99.9th: 30624 (2 samples)
min=3, max=30616
Request Latencies percentiles (usec) runtime 2 (s) (207 total samples)
50.0th: 30048 (62 samples)
90.0th: 132352 (83 samples)
* 99.0th: 204032 (18 samples)
99.9th: 208640 (2 samples)
min=1883, max=208466
RPS percentiles (requests) runtime 2 (s) (3 total samples)
20.0th: 0 (1 samples)
* 50.0th: 91 (1 samples)
90.0th: 104 (1 samples)
min=91, max=104
average rps: 103.50
```
- Wakeup Latencies percentiles (usec)
| | RR | Rustland| Default |
| -------- | ---------- | ------- | ----------- |
| 50.0th | 2002 µs | 21 µs | 5160 µs |
| 90.0th | 7064 µs | 1734 µs | 6872 µs |
| 99.0th | 29024 µs | 8496 µs |7048 µs |
| Max | 30616 µs | 32881 µs|9008 µs |
| Total samples | 207 | 934 | 1145 |
- Request Latencies percentiles (usec)
| | RR | Rustland | Default |
| -------- | --------- | ---------- |--------- |
| 50.0th | 30048 µs | 6888 µs | 5160 µs |
| 90.0th | 132352 µs | 10480 µs | 7016 µs |
| 99.0th | 204032 µs | 55232 µs | 27744 µs |
| Max | 208466 µs | 69299 µs | 40500 µs |
| Total samples | 207 | 934 | 1145 |
- RPS percentiles (requests)
| | RR |Rustland | Default |
| ------------ | -------- | -------- | ------- |
| Average RPS | 103.5 | 467.0 | 572.5 |
| 50.0th | 91 | 438 | 563 |
| Max | 104 | 484 | 573 |
### FIFO test
$NICE = -5$
```shell
$ watch -n 5 'nice -n -5 taskset -c 3 bash -c "stress-ng --cpu 1 --timeout 2s & stress-ng --cpu 1 --timeout 2s & stress-ng --cpu 1 --timeout 2s & wait"'
```
### Time slice 設定確認
為了確認 scx 可以正確設定 time_slice 因此我們更改原先 scx_rlfifo 的設定。
```diff
- dispatched_task.slice_ns = SLICE_NS / (nr_waiting + 1);
+ dispatched_task.slice_ns = 10_000_000;
```
原先是依照任務數量平均分配，為了更好觀察 time_slice 設定是否符合 Perfetto 的觀察結果，我們將其設定為定值，分別為 10ms, 20ms, 30ms。結果如下
- 10ms
- 20ms
- 30ms
可以確認 scx 可以有效設定 time_slice。
## Ref
[Linux 核心專題: sched_ext 研究 by otteryc](https://hackmd.io/@sysprog/H1u6D9LI0)
[GitHub - scx](https://github.com/sched-ext/scx)
[eBPF 隨筆（七）：sched_ext](https://medium.com/@ianchen0119/ebpf-%E9%9A%A8%E7%AD%86-%E4%B8%83-sched-ext-f7b60ea28976)
[Perfetto Docs](https://perfetto.dev/docs/)
<!-- ## else
for meson compile
> 0428 的實驗，好像又不須要了，原本要的說
```$
sudo systemctl restart scx_loader
``` -->
Sign in with Wallet
Connect another wallet