HackMDsched_ext(4): Generate CPU load unbalance
Overview
scx 當中的排程器對於 load balance 部分多數沒有特別實作，除了 scx_rusty 有實作一個使用者層級的 load balancer 。我們希望可以量化來評估排程器對於負載平衡的機制是好還是壞。
CPU load unbalance
CPU 排程器在任務挑選 CPU 時其實就會嘗試讓 CPU load 是平衡的，因此我們要找到適當的 workload 和場景讓 CPU load 出現不平衡，以此觸發 task migration ，在其中比較 task migration 次數，或者 migration 成本等等。
其中一個情況會是 CPU-bound load 和 I/O bound load 大量混雜的情況，由於 I/O bound 的任務要對 disk 進行讀取會導致 CPU waiting ，同時間 CPU-bound 的任務會大量使用 CPU 資源，導致 CPU load unbalance 出現。以實際案例來說有以下幾種場景可能導致上述現象發生
- File server : NAS server 等會進行大量 I/O 操作的系統
- Log processing : 處理系統 log 時可能在邊讀取進行 I/O 時對資料進行分析，分析是 CPU bound 的任務
- Web backend with database operation : 網路應用程式後端時常需要進行 DB 的讀取與寫入，這只是部分工作還有其他可能的運算與操作，大量混雜的情況也可能導致上述情況發生。
Load generate
為了重現上述場景，我們可以撰寫程式創建 CPU bound 和 I/O bound 任務，或者利用 fio 此工具來建立大量 I/O 任務進行測試。
import threading
import os
import time
def io_bound_task(file_path, size_mb):
with open(file_path, 'wb') as f:
f.write(os.urandom(size_mb * 1024 * 1024))
with open(file_path, 'rb') as f:
data = f.read()
os.remove(file_path)
def generate_io_load(num_threads, size_mb):
threads = []
for i in range(num_threads):
file_path = f'test_file_{i}.dat'
t = threading.Thread(target=io_bound_task, args=(file_path, size_mb))
t.start()
threads.append(t)
for t in threads:
t.join()
def cpu_bound_task(duration):
end_time = time.time() + duration
while time.time() < end_time:
result = 0
for i in range(10000):
result += i ** 2
def generate_cpu_load(num_threads, duration):
threads = []
for i in range(num_threads):
t = threading.Thread(target=cpu_bound_task, args=(duration,))
t.start()
threads.append(t)
for t in threads:
t.join()
if __name__ == "__main__":
io_threads = threading.Thread(target=generate_io_load, args=(1200, 100))
cpu_threads = threading.Thread(target=generate_cpu_load, args=(12, 300))
io_threads.start()
cpu_threads.start()
io_threads.join()
cpu_threads.join()
執行上述程式碼，利用 htop 可以觀察到明顯的 CPU load unbalance 發生。
量化並量測 task migration 與其他事件
CPU load unbalance 若發生，不管是 linux kernel 預設的排程器還是 scx 當中的排程器 ，都會進行 CPU load balance 的操作嘗試解決這樣的現象，此時就會牽涉到大量的 task migration 。
我們量測不同 scheudler 與 EEVDF 在上述 workload 情況下 task migration 次數以及 maximum load imbalance 。
$ python load_gen.py
同時用以下命令量測 task migration 次數 (要用新版的 perf ，若沒有要自行下載並編譯) ，首先量測 EEVDF
$ sudo perf stat -e sched:sched_migrate_task -a sleep 60
Performance counter stats for 'system wide':
2,5733 sched:sched_migrate_task
60.002513562 seconds time elapsed
另外利用 mpstat 量測每個 CPU usage rate 變化情況。
$ mpstat -P ALL 1 60 > eevdf_cpu_usage.txt
接著量測 scx_lavd
$ sudo perf stat -e sched:sched_migrate_task -a sleep 60
Performance counter stats for 'system wide':
12,8343 sched:sched_migrate_task
60.004100279 seconds time elapsed
也利用 mpstat 觀測每個 CPU 的 usage rate
$ mpstat -P ALL 1 60 > lavd_cpu_usage.txt
之後利用 python 分析兩者的 log 可以發現如下結果
EEVDF Maximum CPU load imbalance over the period: 51.00%
LAVD Maximum CPU load imbalance over the period: 50.51%
scx_lavd 進行的 task migration 次數幾乎是 EEVDF 的五倍，但 maximum load imbalance 卻差不多，可以說 scx_lavd 進行更多的 task migration 卻沒有明顯成效，進行了多次無謂的 migration 。
但是否是無用的 migration 也端看情況，首先我們應該思考什麼情況會有 task migration 產生？當然每種不同 scheduling policy 觸發 task migration 的時機不同， EEVDF 在 load balance 時可能會引發 task migration ，在 scx 的排程器當中當一個 task 狀態變化從 waiting 變為 runnable ，不過原本運行的 CPU 正在運行其他任務時，同時有其他 idle CPU 存在，這時候就會觸發 task migration ，因此搞清楚 task migration 的目的很重要，不一定是要做負載平衡。
再來是 tasak migration 的代價其實不大，有以下幾點可以考慮
- 現在 CPU 架構下， core to core distance 比起以往的架構來說小很多，任務搬移的成本小很多
- 不搬移的狀況通常是希望保有任務和原本 CPU 的 affinity ，不過 L1/L2 caches 的 affinity 下降的速度非常快，與其花時間等待原本 CPU 可以執行自己，不如直接搬移到其他 CPU
以上是 Tejun Heo 給我的一些建議，與其針對不具有真正意義的 metric 進行優化（例如我原先想優化的 migration 次數），不如針對實際 workload 進行量測，在某些 workload 上或許我的策略會是有效的，但整體而言這取決於不同的 workload ，並不是將某個數值降低就一定比較好。
所以 task migration 與其說是為了讓 CPU 不要 overload ，不如想成 CPU overload 時會讓許多任務的 wait time 變長，導致整體效率不彰，進行任務搬遷是為了讓任務可以儘早被執行，哪怕犧牲一點 affinity ，等待原本 CPU 直到可以執行自己的時間，放在其他 CPU 上搞不好都執行完畢了。
runqueue latency
runqueue latency 意思是一個 task 從 runnable 到實際 running 中間經過的時間，理想上是越短越好，我們可以透過 BCC 的工具 runqlat 來量測系統的 runqueue latency 。若更多 task migration 是為了犧牲 affinity 而使能任務能更快被執行，則 scx 當中的排程器應該有更短的 runqueue latency 才對。
下述實驗當中為了讓系統負載更沉重，利用 stress-ng 讓每個 CPU 的負載先達到 70 ，然後在另外一個 terminal 執行上述所提及的 mixture of CPU-bound and I/O-bound workloads 。
$ stress-ng --cpu 12 -l 70 --timeout 90s | $ python load_gen.py
首先量測 EEVDF 的結果，以下每五秒鐘輸出一次 output ，輸出三次（實際實驗都會進行 12 次，此處簡潔的呈現只放三次）。
$ sudo runqlat 5 12
Tracing run queue latency... Hit Ctrl-C to end.
usecs : count distribution
0 -> 1 : 7038 |****************************************|
2 -> 3 : 4677 |************************** |
4 -> 7 : 6124 |********************************** |
8 -> 15 : 6631 |************************************* |
16 -> 31 : 3292 |****************** |
32 -> 63 : 881 |***** |
64 -> 127 : 365 |** |
128 -> 255 : 292 |* |
256 -> 511 : 304 |* |
512 -> 1023 : 670 |*** |
1024 -> 2047 : 1228 |****** |
2048 -> 4095 : 3757 |********************* |
4096 -> 8191 : 660 |*** |
8192 -> 16383 : 40 | |
usecs : count distribution
0 -> 1 : 5739 |********************************** |
2 -> 3 : 3586 |********************* |
4 -> 7 : 5428 |******************************** |
8 -> 15 : 6597 |****************************************|
16 -> 31 : 3807 |*********************** |
32 -> 63 : 1034 |****** |
64 -> 127 : 347 |** |
128 -> 255 : 276 |* |
256 -> 511 : 276 |* |
512 -> 1023 : 710 |**** |
1024 -> 2047 : 1333 |******** |
2048 -> 4095 : 4219 |************************* |
4096 -> 8191 : 712 |**** |
8192 -> 16383 : 62 | |
usecs : count distribution
0 -> 1 : 7045 |****************************************|
2 -> 3 : 4909 |*************************** |
4 -> 7 : 6753 |************************************** |
8 -> 15 : 6821 |************************************** |
16 -> 31 : 3283 |****************** |
32 -> 63 : 907 |***** |
64 -> 127 : 378 |** |
128 -> 255 : 249 |* |
256 -> 511 : 309 |* |
512 -> 1023 : 698 |*** |
1024 -> 2047 : 1335 |******* |
2048 -> 4095 : 4725 |************************** |
4096 -> 8191 : 913 |***** |
8192 -> 16383 : 71 | |
16384 -> 32767 : 1 | |
[...]
然後測量 scx_lavd 的成效
$ sudo runqlat 5 12
Tracing run queue latency... Hit Ctrl-C to end.
usecs : count distribution
0 -> 1 : 2125 |************ |
2 -> 3 : 4143 |************************ |
4 -> 7 : 2562 |************** |
8 -> 15 : 2050 |*********** |
16 -> 31 : 1288 |******* |
32 -> 63 : 607 |*** |
64 -> 127 : 369 |** |
128 -> 255 : 286 |* |
256 -> 511 : 384 |** |
512 -> 1023 : 4793 |**************************** |
1024 -> 2047 : 3237 |****************** |
2048 -> 4095 : 6846 |****************************************|
4096 -> 8191 : 438 |** |
8192 -> 16383 : 7 | |
usecs : count distribution
0 -> 1 : 795 |**** |
2 -> 3 : 2933 |****************** |
4 -> 7 : 2892 |****************** |
8 -> 15 : 2384 |************** |
16 -> 31 : 1347 |******** |
32 -> 63 : 589 |*** |
64 -> 127 : 437 |** |
128 -> 255 : 338 |** |
256 -> 511 : 461 |** |
512 -> 1023 : 5432 |********************************** |
1024 -> 2047 : 3022 |******************* |
2048 -> 4095 : 6362 |****************************************|
4096 -> 8191 : 416 |** |
8192 -> 16383 : 10 | |
usecs : count distribution
0 -> 1 : 631 |*** |
2 -> 3 : 2609 |************* |
4 -> 7 : 3141 |**************** |
8 -> 15 : 2408 |************ |
16 -> 31 : 1248 |****** |
32 -> 63 : 582 |*** |
64 -> 127 : 526 |** |
128 -> 255 : 405 |** |
256 -> 511 : 433 |** |
512 -> 1023 : 6663 |*********************************** |
1024 -> 2047 : 4776 |************************* |
2048 -> 4095 : 7480 |****************************************|
4096 -> 8191 : 476 |** |
8192 -> 16383 : 6 | |
16384 -> 32767 : 1 | |
[...]
可以明顯看出 scx_lavd 的 runqueue latency 分佈更傾向下方，也就是任務需要等待更長時間才會 running 。
再試驗 scx_central 觀看結果
Tracing run queue latency... Hit Ctrl-C to end.
usecs : count distribution
0 -> 1 : 288 |** |
2 -> 3 : 2295 |**************** |
4 -> 7 : 5693 |****************************************|
8 -> 15 : 4096 |**************************** |
16 -> 31 : 3056 |********************* |
32 -> 63 : 2284 |**************** |
64 -> 127 : 1772 |************ |
128 -> 255 : 1766 |************ |
256 -> 511 : 2267 |*************** |
512 -> 1023 : 4426 |******************************* |
1024 -> 2047 : 4418 |******************************* |
2048 -> 4095 : 2661 |****************** |
4096 -> 8191 : 635 |**** |
8192 -> 16383 : 35 | |
usecs : count distribution
0 -> 1 : 474 |*** |
2 -> 3 : 3053 |********************* |
4 -> 7 : 5701 |****************************************|
8 -> 15 : 4130 |**************************** |
16 -> 31 : 2881 |******************** |
32 -> 63 : 2504 |***************** |
64 -> 127 : 2194 |*************** |
128 -> 255 : 2150 |*************** |
256 -> 511 : 2931 |******************** |
512 -> 1023 : 5255 |************************************ |
1024 -> 2047 : 5140 |************************************ |
2048 -> 4095 : 3308 |*********************** |
4096 -> 8191 : 640 |**** |
8192 -> 16383 : 51 | |
16384 -> 32767 : 2 | |
usecs : count distribution
0 -> 1 : 255 |* |
2 -> 3 : 1908 |************ |
4 -> 7 : 4098 |*************************** |
8 -> 15 : 3473 |*********************** |
16 -> 31 : 3005 |******************* |
32 -> 63 : 2422 |**************** |
64 -> 127 : 2286 |*************** |
128 -> 255 : 2427 |**************** |
256 -> 511 : 3201 |********************* |
512 -> 1023 : 6014 |****************************************|
1024 -> 2047 : 5910 |*************************************** |
2048 -> 4095 : 4125 |*************************** |
4096 -> 8191 : 981 |****** |
8192 -> 16383 : 12 | |
16384 -> 32767 : 1 | |
[...]
整體來說比 scx_lavd 的分佈更好，沒有那麼多的任務堆積在 runqueue latency 長的地方，但不夠穩定，分布也不如 EEVDF 好。如果此時把系統負載量提升至 100% ，進行實驗。
首先是 EEVDF 的結果
$ sudo runqlat 5 12
Tracing run queue latency... Hit Ctrl-C to end.
usecs : count distribution
0 -> 1 : 9585 |****************************************|
2 -> 3 : 4559 |******************* |
4 -> 7 : 6865 |**************************** |
8 -> 15 : 7453 |******************************* |
16 -> 31 : 4279 |***************** |
32 -> 63 : 1466 |****** |
64 -> 127 : 426 |* |
128 -> 255 : 220 | |
256 -> 511 : 193 | |
512 -> 1023 : 381 |* |
1024 -> 2047 : 1069 |**** |
2048 -> 4095 : 6936 |**************************** |
4096 -> 8191 : 1987 |******** |
8192 -> 16383 : 348 |* |
16384 -> 32767 : 20 | |
usecs : count distribution
0 -> 1 : 10574 |****************************************|
2 -> 3 : 3974 |*************** |
4 -> 7 : 7108 |************************** |
8 -> 15 : 7726 |***************************** |
16 -> 31 : 3538 |************* |
32 -> 63 : 1254 |**** |
64 -> 127 : 533 |** |
128 -> 255 : 289 |* |
256 -> 511 : 179 | |
512 -> 1023 : 349 |* |
1024 -> 2047 : 1075 |**** |
2048 -> 4095 : 6385 |************************ |
4096 -> 8191 : 1699 |****** |
8192 -> 16383 : 153 | |
16384 -> 32767 : 2 | |
usecs : count distribution
0 -> 1 : 9571 |****************************************|
2 -> 3 : 3655 |*************** |
4 -> 7 : 7284 |****************************** |
8 -> 15 : 7333 |****************************** |
16 -> 31 : 2990 |************ |
32 -> 63 : 947 |*** |
64 -> 127 : 372 |* |
128 -> 255 : 196 | |
256 -> 511 : 143 | |
512 -> 1023 : 388 |* |
1024 -> 2047 : 1018 |**** |
2048 -> 4095 : 6023 |************************* |
4096 -> 8191 : 1690 |******* |
8192 -> 16383 : 200 | |
16384 -> 32767 : 8 | |
[...]
再來是 scx_central
$ sudo runqlat 5 12
Tracing run queue latency... Hit Ctrl-C to end.
usecs : count distribution
0 -> 1 : 28 | |
2 -> 3 : 151 | |
4 -> 7 : 27 | |
8 -> 15 : 47 | |
16 -> 31 : 656 |*** |
32 -> 63 : 2365 |*********** |
64 -> 127 : 2817 |************* |
128 -> 255 : 2204 |********** |
256 -> 511 : 1702 |******** |
512 -> 1023 : 8124 |****************************************|
1024 -> 2047 : 7656 |************************************* |
2048 -> 4095 : 6815 |********************************* |
4096 -> 8191 : 2084 |********** |
8192 -> 16383 : 267 |* |
16384 -> 32767 : 15 | |
usecs : count distribution
0 -> 1 : 27 | |
2 -> 3 : 130 | |
4 -> 7 : 79 | |
8 -> 15 : 334 |* |
16 -> 31 : 1303 |******* |
32 -> 63 : 2288 |************ |
64 -> 127 : 2305 |************ |
128 -> 255 : 1689 |********* |
256 -> 511 : 1542 |******** |
512 -> 1023 : 7223 |****************************************|
1024 -> 2047 : 6311 |********************************** |
2048 -> 4095 : 5147 |**************************** |
4096 -> 8191 : 1686 |********* |
8192 -> 16383 : 354 |* |
16384 -> 32767 : 21 | |
usecs : count distribution
0 -> 1 : 21 | |
2 -> 3 : 137 | |
4 -> 7 : 113 | |
8 -> 15 : 529 |** |
16 -> 31 : 1297 |******* |
32 -> 63 : 2254 |************ |
64 -> 127 : 2136 |*********** |
128 -> 255 : 1450 |******* |
256 -> 511 : 1450 |******* |
512 -> 1023 : 7277 |****************************************|
1024 -> 2047 : 6591 |************************************ |
2048 -> 4095 : 5476 |****************************** |
4096 -> 8191 : 1778 |********* |
8192 -> 16383 : 226 |* |
16384 -> 32767 : 10 | |
[...]
在 CPU 負載達到 100% 的時候，差距更加明顯， EEVDF 雖然同樣有更多任務的 runqueue latency 變長，但依舊有一大部分的任務 runqueue latency 很低，但 scx_central 分佈就大量往下移，顯示 runqueue latency 變長很多，因此更多的 task migration 並沒有給予系統更好的 runqueue latency 。
經過與 htejun 的討論後，我有幾點事項應該列入考慮並重新思考實驗
- task migration 成本並不高，現代 CPU 架構底下 CPU core 之間的距離不再如以往遙遠
- L1/L2 cache locality 和 L3 cache locality 性質差異很大， L1/L2 cache locality 隨著時間衰退的速度非常快，我們為了保存 cache locality 而不搬運任務，任務等待的時間可能就讓 cache locality 消散光了
- intermediate metric 不一定有意義， intermediate metric 指的就是如 runqueue latency 或 task migration 次數這類的 metric ，我們有很多方法優化它們，但優化之後對於 workload 本身是否有任何好處端看情境，多數情況可以說是毫無意義
- 要優化就要拿出實際的 workload 而非我上述撰寫的 python 腳本來製造 workload ，藉由觀察和 workload 最直接相關的 metric 來端看我們的是否真的對該 workload 友善
要如何尋找實際 workload 製造大量 CPU-intensive workload 和 I/O-intensive workload 呢？大概有以下幾種方法
- stress-ng 等壓力測試工具
- fio 此類工具可以對 disk 進行大量讀寫測試
- kernel 編譯、 KWIN 編譯
- ffmpeg 影像或音訊處理
我選擇編譯 linux kernel 同時利用 fio 工具產生大量 I/O-intensive workload ，測試 EEVDF 和 scx_rusty 。
開啟一個終端機編譯 kernel （先使用 make defconfig 設定預設的 .config 檔案）
$ sudo make -j $(nproc)
另外撰寫一個 fio 測試腳本並運行
[global]
ioengine=libaio # Use Linux native asynchronous I/O
direct=1 # Use direct I/O (bypass page cache)
rw=randrw # Perform random read/write operations
bs=4k # Block size of 4 kilobytes
size=4G # Each job file will handle 4GB of data
numjobs=12 # Number of jobs (simultaneous threads) to run
runtime=2400 # Run the test for 2400 seconds (40 minutes)
time_based=1 # Run the test for a specified time duration
group_reporting # Report results for the group of jobs
iodepth=64 # Number of I/O operations to keep in flight per job
[write_test]
filename=/tmp/fio_test_file_write
rw=write # Sequential write operations
[read_test]
filename=/tmp/fio_test_file_read
rw=read # Sequential read operations
$ fio io_test.fio
利用 mpstat -P ALL 1 120 > eevdf_cpu_usage.txt 觀測 EEVDF 底下兩分鐘 CPU 使用率，還有 mpstat -P ALL 1 120 > rusty_cpu_usage.txt 觀測在 scx_rusty 底下 CPU 使用率。
經過分析後可得
EEVDF: Maximum CPU load imbalance over the period: 98.99%
scx_rusty: Maximum CPU load imbalance over the period: 99.00%
同時利用 perf stat 量測 task migration 次數
EEVDF 結果如下
$ 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 結果如下
$ 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
透過 time 命令量測在這個情況下完整編譯的時間，首先量測 EEVDF 編譯 kernel 的時間
$ time sudo make -j $(nproc)
...
real 6m42.893s
user 0m0.053s
sys 0m0.110s
再量測 scx_rusty
$ time sudo make -j $(nproc)
...
real 5m40.720s
user 0m0.039s
sys 0m0.116s
編譯時間變快近乎一分鐘。但這是否和更頻繁地做 task migration 真的有關聯？我們是否能嘗試降低 migration 次數但不影響編譯時間？
task migration 時在 scx 當中是否有更動 cpumask ，應該要更動，但如何更動。
