利きプロセススケジューラ

kernel/vm探検隊part7の発表スライドです。
https://kernelvm.connpass.com/event/330079/

以下再演動画のテキストでもあります。
https://youtu.be/kJzG-o0_m24

Transcript

1. 利きプロセススケジューラ Nov. 9th, 2024 Satoru Takeuchi X: satoru_takeuchi 1
2. 利き酒 2 利き酒（ききざけ、唎き酒、聞き酒とも）とは、酒の品質を判定すること[1]。 引用元: 「利き酒」（2024年7月22日 (月) 07:14 UTCの版）『ウィキペディア日本語版』。 酒
3. 利き酒 3 利き酒（ききざけ、唎き酒、聞き酒とも）とは、酒の品質を判定すること[1]。 引用元: 「利き酒」（2024年7月22日 (月) 07:14 UTCの版）『ウィキペディア日本語版』。 酒 ペロリ… これは菊姫
4. 利きプロセススケジューラ 4 カーネルソースのバージョン見ず、ソースも読まず、プロセスの挙動のみからプロセスス ケジューラが何かを判定すること[要出典][独自研究][誰によって?]。
5. 利きプロセススケジューラ 5 カーネルソースのバージョン見ず、ソースも読まず、プロセスの挙動のみからプロセスス ケジューラが何かを判定すること[要出典][独自研究][誰によって?]。 ペロリ… これはCFS!
6. 今日のお題 • 3つの環境A,B,Cのプロセススケジューラが何かを判定する • プロセススケジューラは以下のうちのいずれか ◦ O(1)スケジューラ: Linux v2.6.0~v2.6.22 ◦ CFS(Completely Fair Scheduler): Linux v2.6.23~v6.5 ◦ EEVDF(Earliest Eligible Virtual Deadline First ): Linux v6.6~ • 実験プログラムを動かした結果得られるグラフから判定 6 がんばります
7. 実験プログラム • 使い方 ◦ ./sched.py <並列度> • やること ◦ 1. CPU時間を所定量使った後に終了する負荷処理を <並列度>の数だけ起動する ▪ 全て1つのコア上で動作させる ◦ 2. すべての負荷処理の終了を待つ ◦ 3. 負荷処理の開始時からの経過時間と進捗をあらわすグラフを描く ▪ x軸は経過時間[ms]、y軸は進捗[%] • ソース ◦ https://github.com/satoru-takeuchi/sched-tasting/blob/main/sched.py 7
8. グラフの見かた 8 負荷処理0,1が同じ量のCPU時間(タイムスライス)を交 互に使いながら進捗する。 進捗が100%になったら終了
9. 利きプロセススケジューラ、開始! • 環境A,B,C上で./sched.pyを動かし、得られたグラフを見る • パラメタ ◦ 並列度: 2,3 ◦ nice値: 0(デフォルト値), 19(最高値。優先度でいうと最低 ) ▪ niceコマンドを使って指定 • グラフの特徴からプロセススケジューラが何かを判定する 9 みんなもやってみよう !
10. 環境Aで得たグラフ 10 nice値=0 nice値=0 nice値=19 nice値=19
11. 環境Bで得たグラフ 11 nice値=0 nice値=0 nice値=19 nice値=19
12. 環境Cで得たグラフ 12 nice値=19 nice値=19 nice値=0 nice値=0
13. 答え合わせ 13 わかったかな?
14. 環境Aは… 14 nice値=0 nice値=0 nice値=19 nice値=19
15. 環境Aは… 15 nice値=0 nice値=0 nice値=19 nice値=19 ペロリ… これはO(1)スケジューラ!
16. 根拠 • O(1)スケジューラの特徴 ◦ nice値が変わるとタイムスライスが変わる ◦ 実行可能プロセス数を変えてもタイムスライスは不変 • 2つの特徴を兼ね備えるのはO(1)スケジューラのみ 16
17. nice値が大きくなるとタイムスライスが短くなっている 17 nice値=0 nice値=19
18. nice値が大きくなるとタイムスライスが短くなっている 18 nice値=0 nice値=19 📝 nice値0: タイムスライスは100ms nice値19: タイムスライスは5ms
19. 並列数が増えてもタイムスライスが変わらない 19 nice値=19 nice値=19
20. 並列数が増えてもタイムスライスが変わらない 20 nice値=19 nice値=19 📝 実行可能プロセス数が増えるとCPU時間が全然もら えなくなりがちという問題がある
21. 環境Bは… 21 nice値=0 nice値=0 nice値=19 nice値=19
22. 環境Bは… 22 nice値=0 nice値=0 nice値=19 nice値=19 ペロリ… これはCFS!
23. 根拠 • CFSは実行可能プロセス数が多くなるとタイムスライスが短くなる ◦ 全プロセスの実行が一周する期間を指す「レイテンシターゲット」という概念がある ◦ レイテンシターゲットは一定値に保たれる ▪ タイムスライスは”<レイテンシターゲット >/<実行可能なプロセス数 >”になる • この特徴を持つのはCFSだけ 23
24. レイテンシターゲットが一定 24 並列度2, nice値0 並列度3, nice値0
25. レイテンシターゲットが一定 25 並列度2, nice値0 並列度3, nice値0 📝 • レイテンシターゲットは”<定数>*(1 + log 2 (<コア数>))” ◦ 環境Bは定数が6[ms]でコア数8なので6*4＝24[ms] • 実行可能プロセス数が増えすぎるとタイムスライスは無限に小さくならず、最低保 証値がある。この場合はレイテンシターゲットが長くなる
26. 環境Cは… 26 nice値=19 nice値=19 nice値=0 nice値=0
27. 環境Cは… 27 nice値=19 nice値=19 nice値=0 nice値=0 ペロリ… これはEEVDF!
28. 根拠 • EEVDFの特徴 ◦ 実行可能プロセス数が増えてもタイムスライスは不変 ◦ nice値を大きくしてもタイムスライスは不変 • 2つの特徴を兼ね備えるのはEEVDFのみ 28
29. 実行可能プロセス数が増えてもタイムスライスは不変 29 並列度2, nice値0 並列度3, nice値0
30. nice値を大きくしてもタイムスライスは不変 30 並列度2, nice値0 並列度2, nice値19
31. nice値を大きくしてもタイムスライスは変わらない 31 並列度2, nice値0 並列度2, nice値19 📝 • タイムスライスは”<定数>*(1+log 2 (<コア数>)” ◦ 環境Cは定数が0.75[ms]で8コアなので0.75*4=3ms
32. まとめ • 実行可能プロセスが数個程度なら以下のことが言える 32 実行可能プロセスが増えるとタ イムスライスが… nice値が大きくなるとタ イムスライスが… O(1)スケジュー ラ 変わらない 短くなる CFS 短くなる 短くなる EEVDF 変わらない 変わらない
33. • 各環境 ◦ 環境A: Ubuntu 7.04, linux v2.6.20 -> 💮 O(1)スケジューラ ◦ 環境B: Ubuntu 24.04, linux v5.15 -> 💮 CFS ◦ 環境C: Ubuntu 24.04, linux v6.8 -> 💮 EEVDF • ./sched.pyのソース、全グラフと元データのありか ◦ https://github.com/satoru-takeuchi/sched-tasting 参考情報 33
34. 終わり 34 プロセススケジューラおいしい