Linux Kernel Schedulerのライブアップデート技術 ：自動運転に特化したOSを見据えて
ティアフォー System Softwareチームの石川貴大です。
ティアフォーには、学生アルバイトのエンジニアとして働き、そのまま新卒として入社したメンバーが多数在籍しています。今回はSystem Softwareチームの学生エンジニアが取り組んだLinux Kernel Schedulerのライブアップデート技術を紹介します。
System Softwareチームでは、Autowareを使用して実装された自動運転システムに特化したOS機構を研究・開発しています。自動運転システムが持つリアルタイム制約を達成するため、タスクスケジューラに重点を置いています。Autowareが動作するOSとして様々な選択肢を想定しており、その一つがLinux Kernelです。
ティアフォーが研究・開発したタスクスケジューラを、Linux Kernelに自由に実装する基盤として、いくつかの先行研究を検討しています。その候補の一つを、学生エンジニアが実験しました。
実験対象はASPLOS 2023で発表された論文「Efficient Scheduler Live Update for Linux Kernel with Modularization」で提案されたPlugschedという仕組みです。カスタムスケジューラ技術は他にもghOStというユーザープログラムや、eBPFプログラムでスケジューラを記述できる技術がありますが、Plugschedはスケジューラのコードを直接書き替えることから、オーバーヘッドの小ささと自由度の高さが利点です。
今回、Linux Kernel Schedulerをライブアップデートできる環境の構築と、タスクスケジューラをカスタマイズする実験を行いました。
Plugsched：Linux Kernel Schedulerライブアップデート技術
Linux Kernel Schedulerの動作を変更したり、新たなスケジューラクラスを加えたりするためには、従来はLinux Kernelのソースコードを直接変更し、ビルドし直す必要がありました。そのため開発サイクルを回しにくく、カスタムタスクスケジューラを導入する壁となっていました。
ASPLOS 2023で提案されたPlugschedでは、カーネルモジュールの更新により、タスクスケジューラのライブアップデートが可能です。
以下の手順によりLinux Kernel Schedulerをモジュール化し、カーネル本体のスケジューラ主要関数から、カーネルモジュール上のスケジューラのコードにジャンプさせます。主な動作原理は以下の通りです。
- Linux Kernelのタスクスケジューラ部分のソースコードに静的解析ツールを適用する。タスクスケジューラのカスタマイズ可能な部分を切り出し、カーネルモジュールの雛形として抽出する。
- プログラマーがカーネルモジュールの雛形を編集し、カスタムタスクスケジューラを実装する。
- カーネルモジュールをビルドしてロードする。カーネルモジュールでは、元のカーネルのタスクスケジューラ関連関数の呼び出しがカーネルモジュール上のカスタム実装にjmpするよう、メモリ上の命令を書き換える。
- その他 __schedule() 関数がうまく動作するようにstack pivotを行う（詳細は論文を参照）。
上記の手法により、カーネルをビルドし直すことなくタスクスケジューラをライブアップデートし、カスタムタスクスケジューラの動作が可能になります。
著者実装からの変更点
Plugschedの導入方法は論文実装レポジトリのREADMEに書かれていますが、書かれた内容の手順で動作させることができなかったため、著者に質問し、動作可能な段階まで環境や手順を書き換えました。
著者の実装方法からの主な変更点は、以下の通りです。
- Anolis OSというディストリビューションを想定していたが、より一般的なFedoraで動作するよう、コード解析部分で使うLLVMのオプションやrpmパッケージを扱うコマンドを変更。
- 使用されているpodman用のコンテナレジストリにアクセスできなかったため、ローカルでpodman用のコンテナイメージをビルドするよう変更。
実験環境にFedoraを選択した理由は、Plugschedの著者実装が、rpmパッケージの使用を前提としていたためです。rpmパッケージを使用するディストリビューションは複数ありますが、今回は使い慣れているFedoraを選択しました。その中でも、Fedora33を作業環境として選択し、実験を行いました。
現段階では、Plugschedがversion 6.x以降の新しいバージョンのカーネルでは動作しない点に留意したディストリビューションのバージョン選択が必要です。これは、こちらのissueの後半で議論している通り、コンパイラが認識しているvmlinuxに含まれるシンボル情報と実際のソースコード内の関数の場所が矛盾しているため、カーネルコードのスケジューラ部分をextractする処理がうまく走らないためです。
環境構築手順
1. Fedoraの環境上で対象バージョンのLinux Kernelをインストール
Fedora33の環境を構築後、Fedora向けの各種ビルドイメージを配布しているサイトから、kernel-5.10.11–200.fc33をダウンロードします。Plugschedの著者実装では、Linux kernel-5.10に対応した、静的解析のための設定ファイルを提供しているため、このバージョンのカーネルを実験対象とします。
ダウンロードするファイルは以下の3つです。
- kernel-<version>.rpm
- kernel-core-<version>.rpm
- kernel-modules-<version>.rpm
イメージをダウンロードしたら、以下のようにインストールを行います。GRUBの設定で、起動するカーネルのデフォルトインデックスを設定しておくと便利です。
2. Linux Kernelのソースコードの入手
前述のサイトから、手順1と同一バージョンのLinux Kernelのソースコードをrpmの形式でダウンロードします。
3. Plugschedビルド用コンテナの作成
Plugschedをビルドするためのpodmanコンテナイメージを作成します。
次に、ビルドしたイメージを用いてコンテナを立ち上げます。
/path/to/host_workspaceがホスト上での作業スペース、
/path/to/container_workspaceがコンテナ上での作業スペースです。
この部分を任意の場所に設定してください。
併せて、手順2で取得したLinux Kernelのソースコードを/path/to/host_workspaceに移動します。
4. Linux Kernelのソースコードを展開
コンテナ内部にて、Plugschedが提供するツールを利用して、rpmパッケージとしてダウンロードしたLinux Kernelのソースコードを指定したディレクトリに展開します。
5. タスクスケジューラをカーネルモジュールとして抽出
Linux Kernelのソースコードに対して静的解析を行い、タスクスケジューラ部分をカーネルモジュールの雛形として抽出します。抽出されたタスクスケジューラのコードは、./scheduler/kernel/sched/modに配置されます。
以上で、カスタムタスクスケジューラ作成環境が整いました。
独自のスケジューラのデプロイ手順
1. 抽出したスケジューラのコードを変更
./scheduler/kernel/sched/modに配置されている、カーネルモジュールの雛形としてのタスクスケジューラのコードを変更します。ここで独自のタスクスケジューラの機能を実装しますが、今回はチュートリアルとして著者実装レポジトリのREADMEと同様の変更を行います。
2. rpmパッケージとしてカーネルモジュールをビルド
独自タスクスケジューラの実装をrpmパッケージとしてビルドし、ロード可能なカーネルモジュールを作成します。
分かりやすくするため、生成されたrpmパッケージを作業ディレクトリのトップに移動し、コンテナからexitします。
3. カーネルモジュールとしてのタスクスケジューラをロード
rpmコマンドでパッケージのインストールを行うと、カーネルモジュールがロードされ、それに伴い、元のカーネルのスケジューラ部分のバイナリ書き換えがメモリ上で行われ、独自のタスクスケジューラがデプロイされます。
以下の例では、カーネルログやsched_featuresに追加したフラグの存在を通して、無事に独自タスクスケジューラがデプロイされたことを確認できます。
さらに、sched_featuresに追加したフラグをアクティベートすることで、独自のタスクスケジューラの動作を確認できます。
4. 独自のタスクスケジューラのアンロード
独自のタスクスケジューラをアンロードして、元のタスクスケジューラに戻す操作も、rpmコマンドを使います。rmmodコマンドで直接アンロードしないでください。
Plugschedの動作実験
以上の作業により、カーネルモジュールとしてタスクスケジューラを実装し、デプロイする環境を構築できました。
次に、独自のタスクスケジューラの実装に挑戦します。本来は、DAG Scheduling Theoryなどの自動運転アプリケーションに特化したタスクスケジューラを実装したかったのですが、作業時間の制約上、今回は簡単な実験的機能を試しました。
新しいスケジューリングポリシーの追加は、タスクスケジューラコードの広範囲に影響を与えるため、既存のスケジューリングポリシーの機能変更を試しました。Linux Kernelには、主に3種類のタスクスケジューラがありますが、今回は最も実装が簡単なFIFOスケジューラを改造します。
後述しますが、FIFOスケジューラでは優先度別にFIFOキューがあります。今回の改造実験では、特定の優先度のタスクのみカスタムスケジューラで扱い、それ以外の優先度のタスクを従来のFIFOスケジューラで扱うことが可能か試しました。改造コードは、こちらのリポジトリに置いています。
Linux Kernel Schedulerの予備知識
Linux Kernel上で管理されているタスク（スレッド）は、それぞれスケジューリングクラスを属性として持ち、この属性に応じてタスクを扱うスケジューラを決定します。
スケジューリングクラスは5つあり、優先度順にstop_sched、dl_sched、rt_sched、fair_sched、idle_schedとなります。
コアごとに次に実行するタスクを選ぶ際、まず優先度が高いスケジューリングクラスの順にReadyのタスクが存在するか確認します。Readyのタスクが存在するクラスを見つけると、タスクスケジューラはその中から次に実行するタスクを選びます。dl_schedクラスに属するタスクはEDF（Earliest Deadline First）スケジューラ、rt_schedクラスに属するタスクはFIFO（First In First Out）スケジューラ、fair_schedクラスに属するタスクはCFS（Completely Fair Scheduler）によりスケジューリングされます。
このスケジューリングはコアごとに独立して行われる一方、コア間の同じスケジューリングクラスでは、ロードバランシングが行われます。
今回改造の対象に選んだFIFOスケジューラは、優先度（1～99）ごとに独立したFIFOキューを持ち、優先度の高いキューの先頭タスクが取り出されます。
FIFOスケジューラの改造
前述した通り、FIFOスケジューラ上の特定の優先度のタスクのみカスタムスケジューラで扱う改造を行い、今回は任意に選択した優先度45のタスクのみ、従来のFIFOキューではなく、Plugschedで用意した新たなFIFOキューで管理させます。
Plugschedを使用する上での注意点は、タスクスケジューラ以外のサブシステムからもアクセスするデータ構造に変更を加えられない点です。これは、Plugschedは既存のカーネルのコードをビルドし直すことなく、カーネルモジュールとしてタスクスケジューラをデプロイするためです。
本来は、タスクを管理するキューのようなデータ構造を作る際、多数の構造体からポインタ変数としてアクセスできるようにしますが、今回はそのような実装にせず、グローバル変数として定義します。
Plugschedでは、上記のように独自のデータ構造を追加して実装することが一般的です。
この独自のデータ構造に、独自のスケジューリングアルゴリズムを実装していきます。今回は簡単な実験を行うことが目的であるため、この独自のキューからタスクを選ぶアルゴリズムについては、単純なFIFOとしました。また、動作を簡単にするため、各コアにある優先度45のキュー同士のロードバランシングは考慮していません。
動作確認
優先度45のReadyタスクが独自のFIFOから選択された際、デバッグプリントを行うように実装し、動作確認を行いました。優先度45のSCHED_FIFOポリシーのタスクを動作させるサンプルプログラムは、こちらのリポジトリに置いています。
以下の通り、動作実験を行い、dmesgの出力に該当するログを確認できました。printk_onceというマクロを使ったため、一度しか出力されません。
まとめ
自動運転アプリケーションに特化したタスクスケジューラをLinuxに実装する未来を見据えて、ASPLOS 2023で発表されたLinux Kernel Schedulerのライブアップデート技術についての基礎実験を行いました。今後は、要素技術の基礎評価や自動運転アプリケーションに特化した新たなOS機構の研究開発を行い、無人自動運転移動サービスの実現に寄与するOS開発を引き続き行います。
ティアフォーでは、コンピューティングシステムの最先端研究・技術を自動運転システムに適用しています。System softwareチームではLinux Kernelを自動運転に特化させる改造を行うハッカーを学生アルバイトとして募集しています。このブログを読み、興味を持ってくださった方の応募をお待ちしています。
Takahiro Ishikawa | 石川 貴大
System softwareチーム
2022年4月入社。2020年からパートタイムエンジニアとして勤務。東京大学大学院・情報理工学系研究科修士課程修了後、現在は社会人博士課程に在籍。専門分野はオペレーティングシステムとリアルタイムシステム。Autowareのリアルタイム性能に関する低レイヤソフトウェアなどを担当。
ティアフォーでは、「自動運転の民主化」というビジョンに共感を持ち、自らそれを実現する意欲に満ち溢れた新しい仲間を募集しています。
今回のチームで募集中の職種
その他にも多くの職種で採用をしています。詳細は、ティアフォーの「求人ページ」をご覧ください。
「どの職種で自分の経験を活かせるかが分からない」「希望する職種が見つからない」などの場合は、ぜひ「キャリア登録」をお願いします。
お問い合わせ先
メディア取材やイベント登壇のご依頼：pr@tier4.jp
ビジネスや協業のご相談：sales@tier4.jp
ソーシャルメディア
X (Japan/Global) | LinkedIn | Facebook | Instagram | YouTube
関連リンク
