スケジューラの比較と リアルタイムスレッド調査 東芝情報システム株式会社 中嶋健一郎 k-nakajima( at mark )tjsys.co.jp 2006/05/26

Agenda 背景 実験の目的 実験環境 対象スケジューラの紹介 実行したベンチマークの紹介 考察 まとめ

背景 組込みとエンタープライズで同じスケジューラ？ →アプリケーションの特性や、 走っているプロセスの量は違うはず 万能なスケジューラは存在しないのでは？ 組込み向けのスケジューラというのはどうだろうか？ 御意見募集中 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験の目的 スケーラビリティをある程度犠牲にしても、 軽量高速なデジタル家電向けのスケジューラが作れないか検討する スケーラビリティをある程度犠牲にしても、 軽量高速なデジタル家電向けのスケジューラが作れないか検討する 手始めに各スケジューラの性能を比較 Non-RTスレッドとRTスレッドの扱いの違いを 確認する Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験環境 RBTX4400 TX4937 300MHz 128MB SDRAM Kernel 2.6.17-rc1 (linux-mips ツリー) Glibc-2.4 (mips ports) Root FS は PCI カードから繋がっている HDD 上 Plugsched-6.3.2 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Plugsched はどんなもの？ スケジューラをドライバ化して、起動時に差し替えられるようにするパッチ cpusched={ingosched, ingo_ll ,nicksched, staircase} スケジューリングに使用するパラメータのチューニングを sysfs からできるように echo 500 > /sys/cpusched/<sched_name>/<param> 更に拡張して動的に差し替えられるようにしたDynsched もある Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

各スケジューラの特徴紹介 Plugsched-6.3.2付属のもの ingosched ingo_ll nicksched staircase Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

ingosched 標準の O(1) スケジューラ sleep時間に基づいて、優先度にボーナス、ペナルティを設定 タイムスライスはnice値に基づいて計算 sprioはnice値を100..139にマッピングしたもの 𝑚𝑖𝑛𝑠𝑙𝑖𝑐𝑒=𝑚𝑎𝑥 5∗𝐻𝑍 1000, 1 𝑡𝑖𝑚𝑒𝑠𝑙𝑖𝑐𝑒= 𝑚𝑎𝑥 5∗𝐻𝑍 1000 ∗140−𝑠𝑝𝑟𝑖𝑜,𝑚𝑖𝑛𝑠𝑙𝑖𝑐𝑒 𝑛𝑖𝑐𝑒≥0 𝑚𝑎𝑥 20∗𝐻𝑍 1000 ∗140−𝑠𝑝𝑟𝑖𝑜,𝑚𝑖𝑛𝑠𝑙𝑖𝑐𝑒 𝑛𝑖𝑐𝑒0 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

ingo_ll レイテンシを改善した ingosched 高負荷状態では？ 現在は開発されていない(はず) Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

nicksched Nick Piggin が ingosched のインタラクティブ性をチューニングしたスケジューラ これも現在は開発されていない(はず。Kernel-2.6.4くらいで出てこなくなった) sleepの履歴に基づいて優先度を決定 動的優先度とexpiredキューの中も含めた最高優先度によって、タイムスライスを獲得 dprioは動的優先度、minprioは自分とexpiredに入っている中の最小優先度  60 𝑑𝑝𝑟𝑖𝑜−𝑚𝑖𝑛𝑝𝑟𝑖𝑜2  2 ∗  40 170−𝑚𝑖𝑛𝑖𝑝𝑟𝑖  2 ∗ 𝐻𝑍 1000  4 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

staircase Con Kolivas によるインタラクティブ性重視の スケジューラ Ckツリーで開発中 sleep時間で優先度にボーナスを設定 実行時間で優先度にペナルティを設定 静的優先度ベースでタイムスライス獲得 𝑚𝑖𝑛𝑠𝑙𝑖𝑐𝑒=  6∗𝐻𝑍 1001 1𝑛𝑖𝑐𝑒≥0  6∗𝐻𝑍 1001 1−𝑛𝑖𝑐𝑒𝑛𝑖𝑐𝑒0 𝑡𝑖𝑚𝑒𝑠𝑙𝑖𝑐𝑒=𝑚𝑖𝑛𝑠𝑙𝑖𝑐𝑒∗119−𝑛𝑖𝑐𝑒 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

ベンチマーク Interbench Hackbench 独自ベンチマーク Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Interbench Con Kolivas による、インタラクティブ性を 計るためのベンチマーク Xやゲームをエミュレートした負荷をかけて、 スケジュールによるレイテンシを計測 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Interbench 結果 (non-RT) 結果から抜粋すると load : X window, task : Video Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Interbench 結果 (RT) Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Interbench考察 Staircase の性能がやたらいいのが目立つ 欲しい CPU 使用量を請求してから、得られるまでの時間をここでは Latency として定義 RT はあんまりどれも変わらない その他の結果も見てみると、 I/O が発生してもDeadLines Met などが高いのでおかしいかも？ Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Hackbench 各スケジューラで Hackbench を実行してみた Hackbench はスケーラビリティを計るためのベンチ（らしい） 多数のプロセスがパイプを使って通信する fork() なのでかなり重い プロセス数は約1000個 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Hackbench 結果 ./hackbench 30 を実行 かかった時間 (sec) Ingosched 38.620 Ingo_ll 78.689 Nicksched 45.717 Staircase 43.845 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

Hackbench 考察 同じ量のタスクを終わらせる速度という点でIngosched は 優れているようだ Ingo_ll はちょっと… 他の二つもそうは悪くない成績 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

オリジナルベンチマーク RT スレッドから RT、 non-RT スレッドを起床させ、時刻のずれを計測する 負荷スレッドとして Interbench 由来の Hackbench を group 10 として使用 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

pthread_cond_broadcast()で起床 ベンチマークの構成 時間計測スレッド pthread_cond_broadcast()で起床 RT(Non-RT)スレッド 起こされるまで pthread_cond_wait() hackbench 10 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験結果 RT の場合 Non-RTの場合 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

RTスレッドの場合 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

NonRTスレッドの場合 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験結果 (RT) 単位は usec 平均 最小 最大 標準偏差 Ingosched 575.03 3 7 44826 2 1417 1 Ingo_ll 386.66 3 3 8275 0 400 0 Nicksched 119.31 3 4 101 3 12 0 staircase 167.15 3 6 6627 7 209 5 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験結果 (non-RT) 単位は usec 平均 最小 最大 標準偏差 Ingosched 1840.22 3 8 12932 8 1130 4 Ingo_ll 214211.99 15 2 155475 5 19233 4 Nicksched 117.19 3 4 118 3 11 5 staircase 162.75 3 8 184 9 17 7 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験結果 修正 1000 個中 1-4 個程 2 桁程度違う値が混ざるので、6σ を超えるデータを弾いてみる 実験結果　修正 1000 個中 1-4 個程 2 桁程度違う値が混ざるので、6σ を超えるデータを弾いてみる Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験結果 (RT) 単位は usec 平均 最小 最大 標準偏差 Ingosched 126.38 3 7 41 0 12 5 Ingo_ll 169.79 3 3 46 8 14 2 Nicksched 116.09 3 4 47 3 11 0 staircase 101.03 3 6 109 2 11 7 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

実験結果 (non-RT) 単位は usec 平均 最小 最大 標準偏差 Ingosched 776.66 3 8 4582 8 374 2 Ingo_ll 212868.76 15 2 96878 1 18768 8 Nicksched 116.12 3 4 40 6 11 0 staircase 155.49 3 8 122 1 14 5 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

オリジナルベンチマーク考察 RT と Non-RT のタスクの扱いの違い fork() した時の動作 yield()したプロセスの評価 得られるタイムスライスの違い Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

RTとNon-RTの扱いの違い 実は Nicksched はRT の方が結果が悪い バグの匂いが… 状況によっては、かなり大きなタイムスライスを得ることができる nicksched 平均 最小 最大 標準偏差 R T 119.31 3 4 101 3 12 0 Non- RT 116.12 3 4 40 6 11 0 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

fork() した時の動作 スレッドも内部的には do_fork() が呼ばれる Ingosched は fork() すると親子でタイムスライスをシェアする fork() するたびに親のタイムスライスは1/2になっていく→ schedule() されれば戻る (瞬間的な大量の fork() の阻止) 子には sleep 評価にペナルティ Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

fork() した時の動作2 Nicksched は fork() すると親の sleep 評価を悪化 させる → 親が選ばれにくくなることで fork() を遅延させ る？ Staircase は 子には一切のボーナスを加えない が、親には何もしない →子の動的優先度は単調減少するため結果とし て最低のタイムスライスしか取得できなくなる fork()した場合親は次にactivate()されるまでボー ナスを得られなくなる Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

sys_yield() された時の動作 Ingosched, Nicksched は特に何も Staircase はRTでなければ動的優先度を最高にする → yield() するタスクはいいタスク Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

NICE値に応じた タイムスライスの変化 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

NICE値に応じた タイムスライスの変化2 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

NICE値に応じた タイムスライスの変化3 Ingosched, Ingo_llは一次関数なので予想通り。 Staircaseも高々NICE値の2乗なのでそれなり。 Nickschedは、直接にはNICE値ではなく動的優先度ベースとなる。 最高優先度が1上がると他のタスクのタイムスライスが約半分になる。 最も優先されるタスク以外にはかなり厳しい。 →負荷タスクの優先度は下がる一方に対して、計測スレッドは上がる一方なので、負荷タスクがほぼ動けなっていたのかも？ Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

まとめ スケーラビリティ以外の面でも Ingosched は性能がいい。しかし、 non-RT のスレッドを起床させるときの遅延が結構ある。 →fork()された負荷スレッドの子プロセスの評価がそれほど落ちないことに起因？ 寝ないプロセスの場合、動的優先度は落ちるが、nice値さえよければそれなりのタイムスライスを獲得できるのは問題ではないのか？ (事故はあるけれども) RTスレッドにすれば、1ms以下の応答性は確保できそう。 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

今後の計画(妄想？) 新しいスケジューラを作るには 優先度の増減 動的優先度は本当に必要なの？ →固定優先度のスケジューラを作ってみる？ →KFT等でスケジュール関連の関数にかかっている時間を計ってみる →SCHED_INTERACTIVEの導入とか タイムスライスの割り当て NICE値ベースの妥当性の確認 動的に設定することの複雑さ fork() の制御 fork bombを避けるためには yield() の評価 動的優先度をいつでも見られる方法が欲しい Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

イメージ DPRIO 500ms 1500ms 100 PID 324 468 531 140 動的優先度の可視化 533 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

おまけ その他の話 Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

最初は… 定期的に起床させたかったので、sleep 系 API は使えなかった → 最低でも指定した時間寝られてしまう 例. usleep(330000) とすると、次に起きるのは… 33msec + 1/HZ sec + 実行が回ってくるまで Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

pthread… MIPS では、 pthread_cond_signal() を呼んでも寝ているスレッドが起きてくれない （glibc-portsのバグ） Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

I/O scheduler 実験してみたがあまり面白くなかったので、 今回は見送り 実験してみたがあまり面白くなかったので、 今回は見送り Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

優先度が変化するとき Ingosched 寝た時 (+, -) Ingo_ll Nicksched Staircase 実行されたとき (+) 寝た時 (-) Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved

参考 PlugSched https://sourceforge.net/projects/cpuse/ Hackbench http://developer.osdl.org/craiger/hackbench/ Interbench http://members.optusnet.com.au/ckolivas/interbench/ Copyright©2006 Toshiba Information Systems(JAPAN) Corp. All Rights Reserved