「ゼロからのOS自作入門」を Rust でやる (第13章)

13章もなかなかに難産でした。 マルチスレッドプログラミングは難しい...

第13章の前に

第13章に取り組む前にいくつかバグ修正をしました。

unaligned memory access を修正

デバッグモードでビルドしたOSを起動したところ、 debug_assert!() で異常終了してしまいました。 原因は、XSDTのエントリ (u64) が 8byte 境界に揃えられていなかったためです (4byteずれていた)。 x86_64 は unaligned なメモリアクセスも可能なので修正前のプログラムでも動いてしまうのですが、 デバッグビルドを動作させられないのも困るので修正しました。

github.com

修正自体は簡単で、ポインタの指す先を一度 [u8; 4] として読み込んだ後、 u64::from_le_bytesu64 へと変換しているだけです。

オーバーフローの修正

同じくデバッグモードで検出したバグです。 タイマーの初期化時に整数のオーバーフローを検出していました。

github.com

let lapic_timer_freq = elapsed * 10;

上記が問題のあった処理です。 上記の演算結果が u32::MAX を越えてしまうためオーバーフローが発生していました。 オーバーフローが発生しないよう修正しました。

第13章

プリエンプティブマルチタスクを実装する章です。

コンテキストスイッチの実装 (day13a)

コンテキストスイッチを実装します。

github.com

コンテキストスイッチのためにはアセンブリでの実装が必要です。 Rust のインラインアセンブラを使いたかったので、 naked function を使ってみました (関数のプロローグ・エピローグを生成させないため)。

コンテキストスイッチを実装しましたが、この節の段階では協調的マルチタスクの実装であること、また、C++版と異なりウインドウへの画像描画ではなくコンソールへの文字列出力しかしていないため、この段階では特に難しいことはありませんでした。

Makefile + Cargo から Cargo への以降

本筋とは関係ないのですが、 Makefile を利用するのをやめ、 Cargo だけで OS をビルド & 実行できるようにしました。

github.com

また、ユニットテストも実行できるようにしました。

github.com

saibos のブートローダーである bootloader クレートに example が追加されたので、それを参考に実装しました。

ユニットテストが書けるようになると複雑なロジックもある程度安心して書くことができますね。

ログのリフォーム

ログ関連コードを整理しました。

github.com

具体的な修正内容は以下です。

  • ログをシリアルポート経由で QEMU を起動した端末にも出力する
  • ログ出力関数呼び出し元のファイル名、行番号をログに出力する
  • ログレベルに Trace を追加し、 USB ドライバ関連ログのレベルを落とした

LayerWindow が描画バッファを共有していたのをやめる

従来処理では LayerArc<Mutex<Window>> を所有し、描画処理時はロックを取得していました。 このような構造では描画スレッドと Window 関連処理のスレッドが同時に Window にアクセスしようとした場合、片方のスレッドが次のコンテキストスイッチ発生まで長時間待たされてしまいます。 描画スレッドが待ち状態になってしまうと、他の Window の描画も行われなくなるため問題です。 この問題を解消するため、 LayerWindow を所有しなくなるように修正しました。

github.com

従来処理では layer_managerCoTask に描画を依頼するために DrawLayer イベントを送信していましたが、同時に描画するデータを含むバッファも送信するようにしました。 描画完了後バッファを元の CoTask に oneshot チャンネル経由で返却します。 これにより、画面描画処理時に Mutex ロックを取得する必要がなくなります。

サブタスクからウインドウを描画する

従来はメインタスクからのみウインドウの更新をしていましたが、サブタスクでもウインドウの描画を更新するようにしました。 前節までの準備が実を結びましたね。

github.com

メインタスクとサブタスクが同時に oneshot チャンネルのロックを取得する場合があったため、ロック待ち時に panic するのではなく、コンテキストスイッチ発生までスピンロックで待ち続けるようにしました。

定期的なコンテキストスイッチ (day13b)

タイマー契機で複数のタスク間でコンテキストスイッチを発生させるようにしました。 プリエンプティブマルチタスクです!

github.com

実行してみると、動作が非常に遅いです。 タスクBではウインドウの描画を更新する度に oneshot チャンネルからバッファを受信するのですが、このときメインタスク側の処理が実行されるまで待ち続けてしまうため、タスクBのコンテキストではほとんど処理が進まずフリーズして見えることが原因のようです。

描画処理ではロックを使わないようにしたのですが、それだけではだめで、待ち時間をなくさなければならないようですね。 なんてこった...

トリプルバッファの導入

タスクが待たされてしまう問題に対してどうしたものかと思い悩みいろいろ調べてみたところ、どうやらトリプルバッファというものが利用できそうということが分かりましたので、実装してみました。

github.com

トリプルバッファにはいろいろな流儀があるようなのですが、ここでは以下のような仕組みを実装しています。

  • in_progress, ready, present の3種類のバッファを用意する
  • 描画内容生成元タスク (producer) は in_progress バッファを所有する
  • 画面への描画処理タスク (consumer) は present バッファを所有する
  • producer は描画処理完了後、 in_progress バッファと readyスワップする (アトミック操作)
  • consumer は画面への描画開始時、 ready バッファと present バッファを比較し、 ready バッファの内容の方が新しい場合、 両者をスワップする (アトミック操作)

この仕組みにより、producer (consumer) は常時 in_progress バッファ (present バッファ) にアクセス可能 (=待ち時間がなし) になります。

トリプルバッファのアルゴリズムは 以下を参考にしました。

codereview.stackexchange.com

値が一致しない場合に値を差し替えるアトミック操作 (compare and swap の逆?) の実装は以下を参考にしました。

stackoverflow.com

ロックフリーアルゴリズムは頭の体操みたいで楽しいのですが、難しいですね...

また、例によってアトミック操作のオーダーについては自信が持てなかったので、複数スレッドによりアクセスされる領域の操作は SeqCst にしています。

トリプルバッファの実装にあたり、デバッグのためにユニットテストが非常に役立ちました。

トリプルバッファを使ってウインドウを描画する

前の節で用意したトリプルバッファでウインドウを描画するようにしました。 合わせてコードの整理も行っています (Window 生成にビルダーパターンを使うようにした)。

github.com

タスクBが動作している間は画面の描画は更新されませんが、画面描画は高速化されました。いい感じですね。 なお、タスクBが動作している間に大量のイベントがキューイングされるため、 layer_managerCoTask のキューのサイズを大きくしています。

まとめ

プリエンプティブマルチタスクの仕組みを実装しました。 トリプルバッファを導入するなど C++ とは実装が大きく乖離したため、結構大変な章でした。 まだ性能はイマイチなのですが、次章以降で改善していきましょう。