ティアフォーSystem Softwareチームの石川貴大です。ティアフォーには、学生アルバイトのエンジニアとして働き、そのまま新卒として入社したメンバーが多数在籍しています。
今回はSystem Softwareチームの学生エンジニアが調査に取り組んだ、ユーザー空間でLinux Kernel Schedulerをカスタムするための技術を紹介します。
System Softwareチームでは、「Autoware」で実装された自動運転システムに特化した、OS機構を研究・開発しています。特に、自動運転システムが持つリアルタイム制約を達成するため、タスクスケジューラに重点を置いています。「Autoware」が動作するOSとして様々な選択肢を想定しており、その一つがLinux Kernelです。
ティアフォーが研究・開発したタスクスケジューラを、Linux Kernelに自由に実装する基盤として、いくつかの先行研究を検討しています。その候補の一つを、学生エンジニアが実験しました。
過去にSystem Softwareチームの学生エンジニアの取り組みとして、plugschedというLinux Kernel Schedulerのライブアップデート技術について紹介しました。今回は比較対象として、SOSP 2021で発表された論文「ghOSt: Fast & Flexible User-Space Delegation of Linux Scheduling」で提案された、ghOStという仕組みについて紹介します。ghOStは、Linux Kernelのスケジューラを、ユーザー空間のアプリケーションとして実行可能にする革新的な技術です。スケジューラをアプリケーションとして動作させることには、以下のメリットがあります。
- スケジューラが抽象化されているため、Linux Kernelのスケジューラのソースコードを完全に理解していなくても、スケジューラを実装できる。
- スケジューラの変更のためにシステムを停止したり、カーネルを再コンパイルする必要がない。
- スケジューラの実装にバグがあったとしても、カーネルがクラッシュする心配がない。
- 使いたいプログラミング言語でスケジューラを開発できる。
一方でデメリットとして、以下が挙げられます。
- スケジューラが呼び出されるたびにカーネルとユーザーの切り替えが起きてしまうため、オーバーヘッドが生じる。
ghOStの実装によって生じるオーバーヘッドについては評価が行われており、ghOStはμsスケールでのスケジューリングを実現するのに十分な性能を備えていることが論文で示されています。既存のカーネルのスケジューラと比べたときに、ghOStのオーバーヘッドに大きく起因している部分は、「カーネルモードとユーザーモードの切り替えが2度行われる部分」と「メッセージ通信にかかる部分」です。論文での計測結果によると、どちらも処理にかかる時間は数百ns程度です。ghOStスケジューラのオーバーヘッドは、既存のカーネルのスケジューラと比較してもわずかに高い程度であり、様々なワークロードに対応可能だと論文では主張されています。
評価の内容に関しては論文をご参照ください。
以上から、ghOStは多少のオーバーヘッドを伴いますが、スケジューラの開発・運用を容易にする技術と言えます。ghOStを用いることで、単純なFIFOスケジューラであれば200行程度で実装可能です。
ghOStは、特定のアプリケーションに特化したスケジューラを実装することにも有用です。Linux Kernelに特定のアプリケーションを動かすことに特化したスケジューラを実装したとしても、それがmainlineにマージされる可能性は非常に低いです。そのため、アプリケーション特化型スケジューラを使う場合はmainlineの外部で開発していく必要がありました。しかし、この方法ではカーネルのバージョン変化に対応する必要があり、開発コストが高くなってしまいます。ghOStを利用すれば、スケジューラの実装をカーネルから分離できるため、開発コストを抑えることができます。
ghOStの概要
ghOStの動作原理
ghOStは、スケジューラが行う処理をユーザー側とカーネル側に分割し、これらが協力することでスケジューラの仕事を行っています。論文では、ユーザー側で動作するスケジューラ用のスレッドのことをagentと呼んでいるため、本記事でもagentとします。
ユーザー側では、その時点で存在しているスレッドの状態や優先度などを把握し、スケジューリングのタイミングで次に実行するタスクを選び、カーネルに伝達しています。カーネル側では、ユーザー側とやりとりを行い、実際にタスクの切り替えなどを行います。
カーネルとagentの間では以下のような仕組みを用い、スケジューリングに必要な情報がやり取りされます。
- メッセージ通信：タスクの状態変化やCPUイベントなどがメッセージキューを介してカーネルからagentに伝達されます。例えば、タスクがWakeupしたことを伝えるメッセージや、タイマー割り込みが発生したことを伝えるメッセージなどがやり取りされます。
- ステータスワード：スケジューリングに用いる、実行時間などのタスクの情報や同期用の変数などがカーネルからagentに公開されます。
- トランザクション：agentがスケジューリングの内容をカーネルに伝達するために使われます。
これらの仕組みについての詳細は、ghOStに関するこちらの記事の以下のセクションをご参照ください。
- 「メッセージ」
- 「ステータスワード」
- 「トランザクション」
スケジューラの分類
ghOStのスケジューラは大きく分けて、以下の2種類に分類することができます。
Per-CPU型
CPUごとにスケジューリングを行う方式です。各agentは関連付けられたCPUのみを管理し、そのCPU資源をスレッドに分配します。CPU間でスレッドを移動することで、負荷分散処理も可能です。
Centralized型
1つのagentが他の全てのCPUの管理を行う方式です。1つのCPUがスケジューラの処理のみを行う代わりに、他のCPUではagentとカーネルの切り替え処理を行わなくて済むようになります。
本記事ではPer-CPU型のスケジューラについてのみ扱いますが、Centralized型のスケジューラを実装する方法については先述のghOStに関する記事の「チュートリアル2」を参考にしてください。
複数のスケジューラを共存させる方法
ghOStでは、CPUをいくつかのグループに分け、それぞれで異なるスケジューラを動作させることができます。それぞれのグループを管理するものはEnclaveと呼ばれ、ここにスケジューラをアタッチする、といった使われ方をします。
例えば、CPU0〜CPU2を管理するEnclave1と、CPU3だけを管理するEnclave2を作り、Enclave1ではCFSスケジューラを動作させ、Enclave2ではFIFOスケジューラを動作させる、といった管理が簡単に行えます。
スケジューリングの流れ
スケジューラの動作の流れは以下の通りです。
- カーネル: タスクの状態変化やタイマー割り込みなどが起きると、その内容をメッセージにしてメッセージキューにpushする
- カーネル: スケジューリングのタイミングでagentスレッドの実行を開始する
- ユーザー: agentはメッセージキューに溜まっているメッセージを処理したり、ステータスワードを見たりすることで、カーネル内で発生したイベントを把握する
- ユーザー: 把握した情報をもとに、次に実行状態にするべきタスクを選択し、トランザクションによってカーネルに伝達する。トランザクションはシステムコールによって行われるため、カーネルに処理が移る
- カーネル: トランザクションの内容を確認し、そのタスクにコンテキストスイッチを行う
- カーネル: タスクの実行が開始される
つまり、スケジューリングのタイミングになると、一度agentスレッドに実行が切り替わり、ユーザー側で処理が行われた後に、カーネル側に戻ってきてコンテキストスイッチが行われる、という流れになっています。
実際に動作させてみる
ghOStの機能を提供するカーネルはghost-kernelというレポジトリで公開されており、Ubuntu 20.04 LTSで試せます。また、ユーザー側で動作するスケジューラの実装はghost-userspaceというレポジトリで公開されており、FIFOスケジューラやCFSスケジューラなど、様々なスケジューラの実装が含まれています。ここでは、実際にUbuntu 20.04 LTSにghost-kernelをインストールし、ghost-userspaceのスケジューラを動作させるまでの方法を紹介します。
環境構築の手順については先述のghOStに関する記事の「環境構築」を参考にしてみてください。
ghost-kernelのビルドとインストール
以下の手順でビルドとインストールを行います。
- ghost-kernelのソースコードをダウンロードする。
- ghost-kernelをビルドする。コンフィギュレーションでは、CONFIG_SCHED_CLASS_GHOST を有効にする。以下の図に示す、menuconfigから設定可能。
- ビルドしたghost-kernelをUbuntu 20.04 LTSにインストールする。このとき、カーネルヘッダもインストールする。
ghost-kernelのインストールが終了したら再起動します。これでカーネル側の準備は完了です。
ghost-userspaceのビルドと実行
以下の手順でインストールを行います。
- ghost-userspaceのソースコードをダウンロードする。
- ghost-userspaceのビルドに必要なツールをインストールする。
- bazelでビルドする。
ビルドの際は、ghost-kernelとghost-userspaceでバージョンを統一するよう、注意してください。バージョンは include/uapi/linux/ghost.h に以下のマクロで定義されています。
ビルドが正常に終了すると、bazel-bin/fifo_per_cpu_agentという名前で、スケジューラのバイナリが生成されています。これはPer-CPU型のFIFOスケジューラのバイナリです。スケジューラのロードには管理者権限が必要なので、sudoをつけて実行してください。
以上で、ghost-kernel上でアプリケーションとしてスケジューラを動作させることができました。
Per-CPU型のFIFOスケジューラで実験してみる
Per-CPU型のFIFOスケジューラのビルドと実行は以下の通りです。
Initialization complete, ghOSt active. という出力は、初期化処理が完了し、スケジューラが動き始めたことを示します。スケジューラが動き始めると、スケジューリングポリシーに SCHED_GHOST(=18) を設定しているタスクが、このスケジューラで管理され始めます。
しかしこのままでは、ghOstによるスケジューラの動作は実感することができないので、以下の実験を行いました。
スケジューラの実行では、コマンドライン引数から --ghost_cpus=0-1,4 と指定すると、スケジューラが動作するCPUを限定することができます。この設定の場合、スケジューラはCPU 0、1、4のみで動作します。そこで、コマンドライン引数から --ghost_cpus=0 と指定してスケジューラを実行し、CPU0のみでスケジューラが動作するようにします。
その後、スケジューリングポリシーに SCHED_GHOST を設定したbashを起動するようなsimple_bashというプログラムを実装し、そのbashでbusy処理を行いました。simple_bashのプログラムの実装については、先述のghOStに関する記事の「チュートリアル」を参照してください。
すると、busy処理を行うプログラムはghOStのスケジューラによって管理されているため、常にCPU0上で実行され続ける、という状況を観測することができました。
簡易的なスケジューラの実装方法
ghOStでカスタムスケジューラを実装する方法を紹介します。
スケジューラの実装にはghost-userspaceのライブラリを使用し、C++で実装します。上述の通り、スケジューラは好きな言語で実装可能ですが、スケジューラを1から実装していく場合、システムコールのラッパーなど低レベルの処理も実装する必要があり、手間がかるため、ghost-userspaceの実装を使うことをおすすめします。
また、スケジューラを実装するにはいくつかのクラスを実装する必要がありますが、本記事では重要な箇所に絞って紹介します。ライブラリの関数やクラスを利用して、1から段階的にスケジューラを実装していく方法もまとめていますので、気になる方は先述のghOStに関する記事の「チュートリアル」を参考にしてもらえればと思います。
スケジューラの動作に本質的に関わってくるクラスは Scheduler クラスです。カスタムスケジューラを実装するには、このクラスの派生クラスを実装する必要があります。今回は、TutorialScheduler という派生クラスを作成します。
スケジューラの主な処理は、Schedule というメンバ関数に実装します。Schedule はスケジューリングのタイミングで毎回実行されるメンバ関数です。大まかな実装は以下の通りです。
スケジューラの実装でもう1つ重要なのが、メッセージ処理用のメンバ関数です。 DispatchMessage というメンバ関数は、生のメッセージを解析し、メッセージの種類ごとに専用のメンバ関数を呼び出します。例えば、新しくタスクがghOStスケジューラの管理下に入ると、TASK_NEW というメッセージが送られてきますが、そのメッセージが送られてくると TutorialScheduler::TaskNew というメンバ関数が呼び出されます。スケジューラはこれらのメンバ関数内でタスクの状態を変更したり、ランキューを操作したりします。
TaskNew の実装例は以下の通りです。
今回は、単純なFIFOスケジューラを実装したかったため、TutorialScheduler クラスに std::deque 型のメンバ変数 rq_ を実装し、そこにタスクをpushしています。もし、何らかの指標に基づいて優先度を割り振り、最も優先度の高いタスクを選択できるようにしたい場合、優先度付きキューを使用することも可能です。スケジューラをアプリケーションとして実装しているため、様々なライブラリの力を借りることができて有用です。
きちんと動くスケジューラを実装するには、他にもカーネルとの同期処理などのプロセスを実装する必要があります。実装は短くないので、このブログでは説明を割愛させていただきますが、実装してみたいという方は先述のghOStに関する記事の「チュートリアル」を試してみてください。
まとめ
自動運転アプリケーションに特化したLinuxタスクスケジューラをカスタム実装する未来を見据え、SOSP 2021で発表されたghOStというユーザ空間でスケジューラを実装する技術に取り組みました。今後も引き続き、要素技術の基礎評価や自動運転アプリケーションに特化した新たなOS機構の研究開発を行い、無人自動運転移動サービスの実現に寄与するOS開発を引き続き行います。
ティアフォーでは、コンピューティングシステムの最先端研究・技術を自動運転システムに適用しています。System SoftwareチームではLinux Kernelを自動運転に特化させる改造を行うハッカーを募集しています。このブログを読み、興味を持ってくださった方の応募をお待ちしています。
Takahiro Ishikawa | 石川 貴大
System softwareチーム マネージャー
2022年4月入社。2020年からパートタイムエンジニアとして勤務。東京大学大学院・情報理工学系研究科修士課程修了後、現在は社会人博士課程に在籍。専門分野はオペレーティングシステムとリアルタイムシステム。
ティアフォーでは、「自動運転の民主化」というビジョンに共感を持ち、自らそれを実現する意欲に満ち溢れた新しい仲間を募集しています。
多くの職種で採用をしています。詳細は、ティアフォーの「求人ページ」をご覧ください。カジュアル面談をご希望の方は、応募する際に「カジュアル面談希望」と記載してください。
「どの職種で自分の経験を活かせるかが分からない」「希望する職種が見つからない」などの場合は、ぜひ「キャリア登録」をお願いします。
お問い合わせ先
- メディア取材やイベント登壇のご依頼：pr@tier4.jp
- ビジネスや協業のご相談：sales@tier4.jp
ソーシャルメディア
X (Japan/Global) | LinkedIn | Facebook | Instagram | YouTube
関連リンク