Upgrade to Pro — share decks privately, control downloads, hide ads and more …

[試して理解] Linuxのプロセススケジューラのしくみ

[試して理解] Linuxのプロセススケジューラのしくみ

Satoru Takeuchi

November 10, 2018
Tweet

More Decks by Satoru Takeuchi

Other Decks in Technology

Transcript

  1. はじめに • Linuxのスケジューラのしくみを紹介 ◦ カーネルソースを一切見ずに図解と実験によって確認 • 用語 ◦ タスク: カーネルのスケジューリング単位。プロセスまたはスレッド

    ◦ LCPU: カーネルがCPUとして認識するもの(物理CPU or コア or スレッド) • 実験環境 ◦ ハードウェア ▪ CPU: Ryzen 1800x (8 core, 16 thread => 16LCPU) ◦ ソフトウェア ▪ Ubuntu 18.04 ▪ Kernel v4.15.0-34-generic 2
  2. 前振り: 詳解Linuxカーネル第三版曰く… • ランキューはactiveキューとinactiveキューの二本 • タスクの優先度は動的に変化する • タスクごとのタイムスライスは100ms 7 •

    今は全然違う • 約11年前にスケジューラは殆ど全て書き直されている • O(1)スケジューラ -> Completely Fair Scheduler(CFS)
  3. まずは1LCPUから • 16個のLCPUのうち15個をオフラインにする • CPUホットプラグという機能を利用 • これで論理的に「1コア1スレッド」のシステムになる 9 # grep

    -c processor /proc/cpuinfo 16 # for ((i=1;i<16;i++)) ; do > echo 0 >/sys/devices/system/cpu/cpu${i}/online > done # grep -c processor /proc/cpuinfo 1 #
  4. LCPU上で動くタスク 11 タスク数2 タスク数3 タスク数4 時間 t0 t1 t0 t1

    t0 t1 t2 t0 t1 t2 t0 t1 t2 t3 t0 t1 t2 t3 レイテンシターゲット レイテンシターゲット
  5. スケジューラの挙動: 初期状態 • 仮定 ◦ レイテンシターゲット : 6 [ms] •

    タイムスライス=6/(runnableタスク数=3) [ms] 12 0 0 0 t0 t1 t2 vruntime(簡単のため簡略化している ) LCPU ランキュー(vruntime順にソートされた赤黒木 )
  6. 実験プログラム • 実行方法 ◦ ./sched <nproc> <total> <granularity> • 引数の意味

    ◦ Nproc: 同時実行プロセス(タスク)数 ◦ Total: 各プロセスの実行時間 (ms単位) ◦ granularity: 測定粒度(ms単位) • 説明 ◦ Nproc個のタスクを同時に動かす ◦ 各タスクはtotal[ms]だけ無限ループする。このとき granularity[ms]に一回進捗を記録する ◦ 全タスク終了時に、各タスクの ID, 経過時間(us単位), 進捗(%単位)を出力 17
  7. 実験プログラム実行例 • 1つのタスクを1000ms実行。1msごとにデータをとる 18 $ ./sched 1 1000 1 0

    180 0 ... 0 10613 1 # 1%時点でだいたい1ms … 0 20384 2 # 2%時点でだいたい2ms … 0 979192 100 # 100%時点でだいたい1000ms $
  8. タイムスライスは無限に小さくなるのか? • 例: レイテンシターゲットが6msでnproc=1000 ◦ 各タスクのタイムスライスはたったの 6us? • タイムスライスの最低保証値がある ◦

    目的: コンテキストスイッチのコストを増やしすぎないようにするため ◦ sysctlのkernel.sched_min_granularity_ns 24 $ sysctl kernel.sched_min_granularity_ns kernel.sched_min_granularity_ns = 750000 # 0.75ms $
  9. nice値の意味 • Niceの変化によってタイムスライスの比率が変わる ◦ nice値が低い(高優先度): 比率が上がる ◦ nice値が低い(低優先度): 比率が下がる 25

    T0 0 T1 -1 T0 0 T1 0 T0 0 T1 1 時間 T0 0 T1 0 nice値 T0のnice値 > t1のnice値 T0のnice値 == t1のnice値 T0のnice値 < t1のnice値 T0 0 T1 -1 T0 0 T1 1
  10. nice値によるタイムスライスの変化量 • Nice値が1低いとタイムスライスが1.25倍になる • nice値を考慮したタイムスライスの計算式 ◦ Weight = 1.25 ^

    (-nice値) ◦ Slice = latency_target * (weight / Σweight) • 例: 2つのタスクt0, t1がnice値0, -1が存在する ◦ T0のweight = 1.25 ^ 0 = 1 ◦ T1のweight = 1.25 ^ 1 = 1.25 ◦ Σweight = 1 + 1.25 = 2.25 ◦ T0のタイムスライス = 6 * 1 / 2.25 ◦ T1のタイムスライス = 6 * 1.25 / 2.25 26
  11. 実験プログラム • 実行方法 ◦ ./sched <nvalue> <total> <resolution> • 引数の意味

    ◦ nvalue: nice値 ◦ Total: 各プロセスの実行時間 (ms単位) ◦ granularity: 測定粒度(ms単位) • 説明 ◦ 2個のタスクt0, t1を同時に動かす ◦ T0のnice値は0, t1のnice値はnvalue ◦ 2つのタスクはtotal[us]だけ無限ループする。このとき granularity[ms]に一回進捗を記録する ◦ 2つのタスク終了時に、各タスクの ID, 経過時間(us単位), 進捗(%単位)を出力 27
  12. ここから複数LCPUの話 • LCPUの数を2にする 30 # echo 1 >/sys/devices/system/cpu/cpu8/online # …(*1)

    # grep -c processor /proc/cpuinfo 2 # *1) LCPU8はLCPU0と一番共有するリソースが少ないので実験が楽。詳細は割愛
  13. ロードバランサ • ランキューはLCPUごとに存在 • ロードバランサ: 負荷の高いLCPUから負荷の低いLCPUにタスクを移動 ◦ 基本: 負荷 ==

    ランキュー長 ◦ 正確にはnice値やスケジューリングポリシーを考慮して重み付け (説明は省略) • 動作契機 ◦ 新規タスクの生成時 ◦ LCPUがアイドルになった時 ◦ スリープしていたタスクの起床時 ◦ 所定期間の経過時 31
  14. LCPU数とレイテンシターゲットの関係 • LCPU数が増えるほどレイテンシターゲットは長くなる • 計算式 ◦ レイテンシターゲット = LCPUが1のときのレイテンシターゲット *

    (1+floor(lg(LCPU数))) • 理由 ◦ スループット向上のためにレイテンシターゲットは長くしたい ◦ しかし応答性向上のためにはレイテンシターゲットを短くしたい ▪ 1LCPUに閉じると、スリープ状態から起床したタスクが CPU時間を得るまでの長さはレイテン シターゲットの長さに比例 ◦ LCPU数が多ければレイテンシターゲットが長くてもスリープしていたタスクはアイドルな別 LCPU上 で起床後即座に実行開始できる可能性が高いはず 34
  15. 実験 • LCPU数の増加しながらレイテンシターゲットの値を確認 35 # grep -c processor /proc/cpuinfo 1

    # sysctl kernel.sched_latency_ns kernel.sched_latency_ns = 6000000 # echo 1 >/sys/devices/system/cpu/cpu1/online # LCPU数 -> 2 # sysctl kernel.sched_latency_ns kernel.sched_latency_ns = 12000000 # 6000000 * 2 # echo 1 >/sys/devices/system/cpu/cpu2/online # LCPU数 -> 3 # sysctl kernel.sched_latency_ns kernel.sched_latency_ns = 12000000 # 6000000 * 2 # echo 1 >/sys/devices/system/cpu/cpu3/online # LCPU数 -> 4 # sysctl kernel.sched_latency_ns kernel.sched_latency_ns = 18000000 # 6000000 * 3 #
  16. CPU affinity • タスクを動作させるLCPUの集合を決められる ◦ 用途: 全CPUで1つづつ動かしたいハートビート処理 , VMやコンテナが動ける CPUの制限

    ◦ sched_setaffinity()システムコールやtasksetコマンドによって設定 37 T0 Affinity: 0, 1 T1 Affinity: 0 T2 Affinity: 1 LCPU0 LCPU1 × 移動可 〇 移動不可
  17. ロードバランサの階層構造 • ハードウェア構成によってロードバランサは階層構造を持つ • 階層の例 ◦ NUMAノード間 ◦ NUMAノード内のソケット間 ◦

    ソケット内のコア間 ◦ コア内のスレッド間 • 動作の概略 ◦ 最上位階層でバランス -> 1つ下の階層でバランス -> … -> 最下階層でバランス 40
  18. 一番busyなnodeと暇なnodeを見つける • 42 t0 t1 t5 t4 t3 LCPU0 LCPU1

    LCPU2 LCPU3 t2 node0 node1 タスク数4 タスク数2
  19. 一番busyなnode内の一番忙しいLCPUを選ぶ • 43 t0 t1 t5 t4 t3 LCPU0 LCPU1

    LCPU2 LCPU3 t2 node0 node1 タスク数3 タスク数1
  20. 一番暇なnode内の一番暇なLCPUを選ぶ • 44 t0 t1 t5 t4 t3 LCPU0 LCPU1

    LCPU2 LCPU3 t2 node0 node1 タスク数0 タスク数2
  21. • 1物理CPU, 2CCX(*1), 4コア, 2スレッド => 16LCPU 1. 物理CPU内CCX間のバランス 2.

    CCX内コア間のバランス 3. コア内スレッド間のバランス CCX 複雑なアーキテクチャ(AMD Ryzen 1800X) 47 *1) L3キャッシュを共有するコアの塊 CCX コア スレッド スレッド CCX コア コア コア 物理CPU
  22. 階層構造の確認方法 • /proc/schedstat • 実験環境の場合 48 # cat /proc/schedstat …

    Cpu0 ... domain0 0003 ... domain1 00ff ... domain2 ffff ... ... cpu2 ... domain0 000c ... domain1 00ff ... domain2 ffff … … # コア内スレッド間のバランス CCX内コア間のバランス 物理CPU内CCX間のバランス
  23. 実験環境におけるCPUの物理構成とLCPU番号 49 LCPU番号 CCX コア スレッド 0 0 0 0

    1 1 2 1 2 3 3 4 2 4 5 5 6 3 6 7 7 LCPU番号 CCX コア スレッド 8 1 4 8 9 9 10 5 10 11 11 12 6 12 13 13 14 7 14 15 15
  24. ロードバランスの例: 無限ループプログラムの同時実行 • n=1 50 0 1 0 0 1

    2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 5 6 7 CCX core thread p0
  25. ロードバランスの例: 無限ループプログラムの同時実行 • n=8: 各コアに均等配置 52 0 1 0 0

    1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 5 6 7 CCX core thread p0 p1 p2 p3 p4 p5 p6 p7
  26. ロードバランスの例: 無限ループプログラムの同時実行 • n=16: 各スレッドに均等配置 53 0 1 0 0

    1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 5 6 7 CCX core thread p0 p2 p4 p6 p8 p10 p12 p14 p1 p3 p5 p7 p9 p11 p13 p15
  27. おまけ: 変態アーキテクチャ(AMD EPYC7601フル構成) • 2物理CPU, 4ダイ(*1), 2CCX, 4コア, 2スレッド =>

    128LCPU 1. 物理CPU間のバランス 2. 物理CPU内ダイ間のバランス 3. ダイ内CCX間のバランス 4. CCX内コア間のバランス 5. コア内スレッド間のバランス 54 *1) CCXを2つ繋いだもの 物理CPU 物理CPU ダイ ダイ ダイ ダイ CCX CCX コア コア コア コア スレッド スレッド
  28. fair group scheduling • Cpu cgroup 1. グループ間でCPUを均等配分 2. グループ内でさらに均等配分

    • Cpu cgroupのcpu.sharesパラメタによって重み付け • ネストも可能 57 Cpu cgroup “Foo” Shaers = 1024 Cpu cgroup “Bar” Shares = 1024 t0 t1 t2 1. Foo, bar間でCPU 時間を均等配分 1. Foo: T0, t1間で均等配分 2. Bar: t2に全部配分
  29. LCPU上で動くタスク 58 時間 t0 t1 t2 t0 t1 t2 cgroupなし

    Cgroupあり グループfoo: t0, t1 グループbar: t2 t0 t1 t2 t0 t1 t2 1 1/3 1/3 1/3 1 1/4 1/4 1/2 1/2
  30. LCPU上で動くタスク: 重み付けあり 59 時間 t0 t1 t0 t1 Cgroupあり  グループfoo:

    t0   share: 1024  グループbar: t1   share: 1024 Cgroupあり グループfoo: t0 Share: 1024 グループbar: t1 Share: 2048 1 1/2 1/2 t0 t1 1 1/3 2/3 t0 t1
  31. Usecase: ユーザ間でCPU資源を均等配分 • 例: ユーザAがt0, ユーザBがt1-t3を動かしているとする 60 Fair share scheduler不使用

    ユーザごとにcpu cgroup作成 時間 T0 (ユーザA) T1 (ユーザB) T2 (ユーザB) T3 (ユーザC) 時間 T0 (ユーザA) T1 (ユーザB) T2 (ユーザB) T3 (ユーザB) タスク同士が公平 ユーザ同士は不公平 ユーザ同士が公平
  32. 実験プログラム 1. 2つのcpu cgroup, fooとbarを作る 2. fooにbarの二倍のCPU時間を与える 3. Fooとbar上でそれぞれloopプログラムを動かす 4.

    topで%cpuを監視 61 # mkdir /sys/fs/cgroup/cpu/foo # mkdir /sys/fs/cgroup/cpu/bar # echo 2048 > /sys/fs/cgroup/cpu/foo/cpu.shares # echo 1024 > /sys/fs/cgroup/cpu/bar/cpu.shares # # ./loop & [1] 25688 # ./loop & [2] 25689 # echo 25688 >/sys/fs/cgroup/cpu/foo/tasks # echo 25689 >/sys/fs/cgroup/cpu/bar/tasks # top -b -d 1 -p 25688 -p 25689
  33. 実験結果 62 # top -b -d 1 -p 25688 -p

    25689 … PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 25688 root 20 0 4376 800 736 R 66.0 0.0 1:11.55 loop 25689 root 20 0 4376 744 684 R 33.0 0.0 1:08.45 loop … PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 25688 root 20 0 4376 800 736 R 66.3 0.0 1:12.22 loop 25689 root 20 0 4376 744 684 R 32.7 0.0 1:08.78 loop Fooに属するloopプログラムがbarに 属するそれの1.5倍CPU時間を得ている 時間 Loop (foo) Loop (bar) current Loop (foo) Loop (bar) レイテンシターゲット (lt) lt*(⅔) lt*(⅓)
  34. Fair group schedulingの課題: 上限設定ができない • 例: 2ユーザA, Bが同居するマルチテナントシステム ◦ やりたいこと:

    個々のユーザにCPU資源を”最大”1/2与えたい ▪ ユーザ間の不平等、過剰なサービスの提供を避けたい ◦ Fair group schedulingにできること: ユーザごとにグループ作成 64 時間 Aだけがタスクを動かしている状態 (あるべき姿) Aのタスク Aだけがタスクを動かしている状態 (現実) Aのタスク idle Aのタスク idle
  35. CFS bandwidth controller • あるcpu cgroupが所定期間内に動ける時間を制限 ◦ cpu.Cfs_period_us: 期間([us]単位) ◦

    Cpu.cfs_quota_us: 動ける時間([us]単位) • ネストも可能 • 主な用途: VMやコンテナのリソース制限 65 時間 Aのタスク idle Aのタスク idle quota period quota切れ quotaチャージ
  36. 実験プログラム 1. fooという名前のCpu cgroupを作る 2. Fooに属するタスクはCPU資源の半分しか使えないようにする 3. Loopプログラムをバックグラウンドで動かしてfooに属させる 4. Topで%cpuを監視

    66 # Mkdir /sys/fs/cgroup/cpu/foo Echo 100000 > /sys/fs/cgroup/cpu/foo/cpu.cfs_period_us Echo 50000 > /sys/fs/cgroup/cpu/foo/cpu.cfs_quota_us # ./loop & [1] 25676 # echo 25676 > /sys/fs/cgroup/cpu/foo/tasks # Top -b 1 -d 1 -p 25676
  37. 実験結果 67 # top -b -d 1 -p 25576 ...

    PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 25676 root 20 0 4376 856 796 R 50.0 0.0 2:56.33 loop ... PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 25676 root 20 0 4376 856 796 R 51.0 0.0 2:56.84 loop ... LCPU上でこのプロセスしか動いていないのに 50%しかCPU資源を使えていない 時間 loop idle current loop idle loop idle quota period loopのquota切れ loopのquotaチャージ
  38. おわりに • より深く知りたければ… ◦ 実験プログラムのパラメタを色々変えながら実行 ◦ ソースを読む(Linuxカーネルソースのkernel/sched/以下) ◦ 実験プログラムを作る ◦

    Ftraceなどのトレーサを使う • 漫然とソースを読むより実験しながらのほうが理解しやすいよ! ◦ これはどのソフトウェアでも同じ 68