091107

今日読んだところでは継続を使って書き直したMachの性能向上と、継続のいろ いろな使い道を示しています。
例えば、Unixのシグナルの配送をこの文脈にしてみると... 例外や割り込みが 入るとトラップフレームにレジスタを保存する。(トラップフレームは例外、割 込みの際に退避するフレームで全レジスタを退避する。スイッチフレームとい うのはカーネル内から明示的にプロセスをスイッチする時のフレームなので、 caller-savedはいらない。)これはアドレス空間とトラップフレームの組で、カー ネルから戻るべき継続になる。ここでシグナルを配送するとなると、シグナル スタックと、シグナルトランポリンの関数ポインタ、そして送られるプロセス のアドレス空間が、シグナル配送の継続になる。ここで「継続」とするのは、 元の関数に戻らないから。シグナルトランポリンはシグナルコードと、戻るべ きプロセスの継続(これはトラップフレームあるいはスイッチフレームから構成 したものだ)を引数に呼ばれ、シグナルハンドラを実行した後に、プロセスの継 続を呼ぶ。という風になる。

Richard P. Draves Brian N.Bershad Richard F.Rashid Randall W.Dean.
Using Continuations to Implement Thread Management and Communication
in Operating Systems. SOSP, Octover 1991.


3 性能

この章では性能における継続の効果を調べる。空間に関しては、カーネルの中
の制御の移行のほぼ全てを継続を使うようにして、スタックなしでスレッドを
ブロックできるようになったことを示した。これは効果的にカーネルのスタッ
クをプロセッサ毎の資源とできる。時間に関しては、大くの制御移行を継続認
識を使うようにした。これはアドレス空間をまたぐ通信と、ユーザ層の例外処
理の遅延を軽減する。

3.1 実験環境

三つの版のMachカーネルを評価した: MK32, MK40とMach2.5。 MK32とMK40は
Mach 3.0の純粋カーネルで、Unixシステムコールインターフェースをカーネル
アドレス空間で実装していない。MK32は継続を使っていないが、アドレス空間
をまたぐRPCのオーバーヘッドを軽減する最適化[Draves 90]を含んでいる。
MK40は二章で述べた継続を使っている。Mach 2.5はBSD Unixインターフェース
をカーネル空間で実装した、合いの子カーネルで、MK32におけるRPCの最適化も、
継続も使っていない。

全てのカーネルはDECstation 3100(DS3100)とToshiba 5200/100で動く。
DS3100はMIPS R2000を基本としたワークステーションで、64KBの命令データ分
離キャッシュと4段の書き込みバッファをを持つ。それは16.67MHzで、キャッシュ
落ちや、書き込みストールがなければ、1サイクルごとに1命令を実行する。我々
のDS3100は16MBのメモリと250MBのHitachiのディスクドライブで構成されてい
た。Toshiba 5200はIntel 80386 20MHzを基本にしたラップトップで、32KBの命
令、データ統合キャッシュである。我々のToshiba 5200は8MBのメモリと100MB
のConnerディスクドライブから構成されていた。

Mach 3.0カーネルはUnixサーバへのRPCとして実装されたUnixシステムの環境で
試験した。さらにToshiba 5200ではMS-DOSエミュレーションも測定した。
MS-DOSエミュレータMS-DOSのシステムコールと特権命令から起きるフォルトを
ユーザ層の例外処理が掴まえる。その例外処理スレッドはエミュレートした
MS-DOSプログラムのアドレス空間で動く。

3.2 継続の使用の動的な頻度

継続の価値はどれだけの頻度でそれが使われるかによる。これを測定するため
に、Toshiba 5200でMK40カーネルでブロックする処理が継続を使う回数を計測
する3つのテストをした。一つ目のテストは短かいCのコンパイルベンチマーク。
二つ目はAFS(分散Andrewファイルシステム[Satyanarayanan et al.85]上で
Mach 3.0カーネルを作成。三つ目のテストはMS-DOSのビデオゲームである「ウィ
ングコマンダー」で測定した。小さいコンパイルと、MS-DOSはシングルユーザ
モードでテストした。カーネルの作成はマルチユーザモードでテストした。
AFSはネットワークサービスとユーザ層のファイルキャッシュマネージャが必要
だからだ。表1に結果をまとめた。DS3100 でも頻度は似ている。MS-DOSのゲー
ムはToshibaでしか動かないので例外。
 表によって99%の制御移行が継続を使い、スタック放棄を使っている。一番頻
度が高いのはメッセージの受信と例外処理である。他の処理は、ページフォル
ト、自発的な再スケージューリング[Balck 90a]、自発的でない横取り、そして、
カーネル内部のスレッドによるブロックである。残る、継続を使わずにブロッ
クする処理はカーネルのページフォルト、メモリ割当て、ロックの獲得で起こ
る。これらの状況で継続を作成することは難しいため、MK40ではプロセス形態
を使ってカーネルスタックをブロックの間保持したままとしている。
 表2はスタック渡しがほぼ全ての制御移行で起っていることを示している。さ
らにアドレス空間をまたぐRPCと例外処理で起こる、継続認識は、ブロック処理
の60%以上で起こる。

3.3 継続に起因する速度の向上

継続がアドレス空間をまたぐRPCと例外処理の実行時の性能を向上されることを
示す。RPCテストはアドレス空間をまたぐ"null"RPCの往復の時間を測定した。
例外処理のテストはスレッドの例外をユーザ層のサーバが処理する時間を測定
した。例外サーバはフォルトするスレッドと同じアドレス空間で動かした。フォ
ルトを起したスレッドの状態は調べず、変更もしないので、例外は出続ける。
MK40, MK32, Mach2.5に対して、この二つのテストを大量に反復した平均結果を
表3に示した。

RPC性能の向上

MK32のRPC経路はMach 2.5に比較して既にかなり最適化されていたので、向上の
余地は少ししかなかった。プロセス形態(スレッド毎にスタックをもつ)だが、
MK32はRPC転送の間の一般的なスケジューラのコードを回避した。その代わりに
直接、送信スレッドから受信スレッドにコンテキストスイッチするようにした。
対照的に、Mach 2.5はメッセージを待ち行列に入れ、一般的なスケジューラが
次に走る受信スレッドを決定していた。

以前の最適化にもかかわらず、MK40のRPCは14%速い。その向上は主に、コンテ
キストスイッチをスタック渡しによって取って代えたことによる(2)。表4がス
タック渡しとコンテキストスイッチの命令、読み込み、書き込みの数の差であ
る。十分にスタック渡しはコンテキストスイッチより効果的である。

(2) MK40のToshiba 5200のRPC遅延は、バグによって少々増加している。
Toshiba 5200のトラップ処理はカーネルに入る時にユーザのレジスタを、別の
機種依存のデータ構造でなく、スタックに保存する。結果として、機種依存の
スタック渡しの手続きは現在のスレッドの状態をスタックからコピーし、新し
いスレッドのスタックにコピーしなくてはならない。この修正によって
Toshiba 5200の時間は50usecほど向上すると予想している。

継続の実行時の犠牲

Machで継続を使うことにに関連する実行時の犠牲が少しある。表4にあるように、
カーネルに入るのと出るのにかかる時間がMK40はMK32較べて少し長い。これは
継続と、そのアーキテクチャの呼び出し規約の相互作用によるものである。
MK32では、カーネルのシステムコールの入口ではどのレジスタもスタックに保
存する必要がない。呼び出し元退避(caller-saved)のレジスタは既にユーザ層
のスタックに保存されていて、そして呼び出し先退避(callee-saved)のレジス
タはカーネル層のスタックにコンパイラがシステムコールの必要に応じて保存
する。これは暗黙的にプロセス形態であることを想定していて、呼び出し先退
避のレジスタは、'return'の際にスタックから元に戻される。

継続を使って、そしてスタックが放棄されると、呼び出し先退避のレジスタで
あっても、返る際に元に戻されなくなってしまう。('return'は決っして起こら
ないからだ)結果として、カーネルの入口で全ての呼び出し先退避のレジスタを
補助的な機種依存のデータ構造に保持し、カーネルの出口ではこれらを元に戻
さないといけなくなった。DS3100の例では、9つの呼び出し先退避のレジスタが
あり、表4の追加の犠牲になる。例外と割込みに関しては、カーネルの入口では
呼び出し先退避でなくとも、必ず全てのレジスタを(退避しなくてはならない。
これはMK32でも同じように必要である。なので呼び出し先退避のレジスタを保
存することの相対的な犠牲は減っている。

例外処理の向上

表3に示すように、例外処理はMK40は2,3倍MK32に較べて速い。RPCと違い、
MK32では例外処理は最適化されていなかった。結果としてMK40の例外処理は継
続の一番良い状況を示した。そして、OSのカーネルで一般的な枠組のように継
続を使う重要な点も示している。高速だが可搬性のあるアドレス空間をまたぐ
RPC構造にから、制御移行の一般的な枠組みを開発することになった。一度イン
ターフェースが決まれば、簡単にそれを例外処理の経路に適用することができ
た。3日程の作業で、例外処理の実行時の性能の向上が見れた。スタック放棄に
よる空間の削減も実感した。さらに、最適化は機種非依存に実装されているの
で、一度作業するだけである。カーネルの経路に継続を使う経験も同じである。
継続を性能に重大な経路に適用することができ、それは少ない努力の割に良い
結果をもたらしたと結論づけた。

3.4 継続に起因する空間の節約

継続によって効果的にカーネルのスタックをスレッド毎でなく、プロセッサ毎
の資源に変更できる。カーネルスレッドの数を24から43で変化する(我々がメー
ルを読む機械は通常100から200スレッドあるが)3つのテストプログラムのため
に、MK32では多くのカーネルタックがカーネル層スタックとしてある。MK40で
はカーネルスタックの数は平均で2.002である。99%以上の時間でたた二つのス
タックが使われる。一つは、現在走行中のスレッドのためで、もう一つは継続
とともにブロックしていない、内部のカーネルスレッドのためである。そのス
レッドは継続を使うには難しい制御の流れである。そのスタックは機械毎(プロ
セッサ毎ではない)の不変のオーバーヘッドを表現する。残りの0.002スタック
はいくつかの制御移行が継続を使わないことに起因する(表1の下の行を見よ)。
最悪の状況では、コンパイルテストとMS-DOSエミュレーションは3スタックを使
い、カーネル作成では6使う。しかし安定した状況では2カーネルスタックだけ
が使われる。

表5: DS3100におけるスレッド管理のオーバーヘッド(byte)

継続に起因する節約を評価する別の方法としては、それぞれのスレッドが消費
するカーネルメモリの平均を考察する。表5はDS3100上のMK32とMK40のスレッド
毎のデータ構造のサイズを示している。この機械では継続によって平均でスレッ
ドに使う量を85%削減している。Toshibaでは同程度の削減がある。

 カーネルスレッドによって要求される空間は機種依存と機種非依存の状態と、
スタックがある。MK40では機種非依存状態は継続(4バイトの関数ポインタ)と
28バイトのスクラッチ領域の空間の分、MK32より大きい。機種依存スレッド状
況は例えば、カーネルに突入した時のユーザレジスタ等を含む。MK32において
はスレッドの機種依存状態はそのスレッドの専用スタックに保存される。MK40
は専用のカーネルスタックを持たないので、機種依存状態は別のデータ構造に
保存される。

スタックによって消費される空間はスタックそれ自体(4KB)と、カーネルアドレ
ス空間のスタックを維持する仮想メモリシステムによって使われる全てのデー
タ構造を含む。MK32ではカーネルスタックはページ可能で、なので追加の116バ
イト(4)のVMデータ構造を必要とした。MK40ではカーネルスタックが少ないので、
スタックをページ可能とする必要がなく、VMシステムの空間を節約する。さら
にMK40はタックを物理メモリから割り合てできるアーキテクチャであれば、
TLBエントリの節約になる。(他の目的に使える)

(4) カーネルスタックがページ可能だとしても、それらのスタックがメモリに
残っているのに十分な頻度で走る。MK32での例では、90%のカーネルスタックは
ステムがページを別のメモリにしたとしてもメモリに残っていた。休眠してい
るスレッドのスタックが実際にページアウトされている時、追加的なスレッド
毎に220バイトのVMに関係するデータ構造が必要なので、ページアウトされたス
タックは336バイトを消費する。

4. 以前の最適化の継続による一般化


継続は他のOSに見つかる制御移行の最適化に機種非依存な枠組を提供する。例
として、Machの継続を基本にしたRPCと、軽量遠隔手続き呼び出し
(LRPC)[Bershad et al. 90]の制御移行の様子を比較することができる。LRPCは
アドレス空間をまたぐRPC一般に対しての高性能プロセス間通信として設計され
た。LRPCの一部は高性能で、それはスレッドがアドレス空間の境界を越えるこ
とができるということによっていた。呼び出し元のアドレス空間のスレドはカー
ネルにトラップされ、それはサーバのアドレス空間に入り、そこでサーバのコー
ドを即座に実行し始める。戻る時は呼び出し元のスレッドはサーバのアドレス
空間からカーネルにトラップして戻り、次に続くトラップの命令で呼び出し元
のアドレス空間に戻る。シングルスレッドやり方の一番の性能的な優位性は、
全ての作業はシングルスレッドのコンテキストで終了するため、スケジューリ
ングとメッセージの待ち行列がLRPCの経路からまったくなくすことができるこ
とだ。

Machの継続を基本としたRPCはLRPCのような性能的な優位性の多くを達成するこ
とができた。:待ち行列なし、スケジューリングなし、そしてカーネルスタック
を呼び出し元と呼び出し先で共有する。実際、カーネルのロックを通る制御の
流れは二つのシステムで似ている。: 制御は、あるアドレス空間からカーネル
の手続きに入り、そして同じ手続きをもう一方にもして、出る。さらに、継続
を基本にしたRPCはクライアントとサーバの論理的な分離も支える。スレッドは
それらのアドレス空間の中で固定されたままで、スレッドがアドレス空間の間
を移動する時に起る保護、デバッグ、ごみ集めの問題の多くを取り除いた。
[Bershad 90]

継続の自然な拡張によって、完全にLRPC転送規約を真似することができた。
Machのスレッドがカーネルにトラップされる時、このトラップが起きたユーザ
層のコンテキストに制御を戻すための継続を作成する。IPCインターフェースを
スレッドがシステムコールから返るためのユーザ層の継続を上書きできるよう
にする拡張する実験をしている(5)。この拡張はサーバスレッドがレジスタを退
避/復旧する手間を取り除き、サーバスレッドはRPC要求の待ちでブロックして
いる間、ユーザ層のスタックを放棄することが可能になる。

カーネルの外部に戻る時の継続を一つではなくカーネルが入った時に活性であっ
た継続のどれかに戻ることができるようにすることで、継続は制御移行の機構
を豊富に集めたものをを一般的なやり方として実装することに使える。例えば、
上への呼びだし(upcall)はx-kernel[Hutchinson et al.89]に必要であり、
Scheduler Activations[ANderson et al. 91]は、基本「ユーザ層に戻る」継続
のブロックしたスレッドのプールをカーネルにとっておくことで実装できる。
上への呼びだしを実行するため、基本の継続はユーザ層の特定したアドレスへ
とカーネルの外に制御を移す継続によって取り替えられる。非同期I/O [Levy
& Eckhouse 89]は似たように作用する。非同期I/Oをスケジューリングすると、
スレッドはI/Oが完了した時に呼ばれる継続をカーネルに、提供する。

(5)この拡張はMachのメインリリースの一部ではない。