今度は
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.
を読みはじめてみました。これはなにか示唆がありそうだと思って以前プリン
トアウトしておいたんだ。
以下、日本語の羅列。途中まで。これははやく実装してみたい欲に狩られるけ れど一応最後まで読んで見通しをつけよう。マイOSにもはやくユーザ空間で動 くプロセスが欲しいとこだ。
以下、日本語の羅列。途中まで。これははやく実装してみたい欲に狩られるけ れど一応最後まで読んで見通しをつけよう。マイOSにもはやくユーザ空間で動 くプロセスが欲しいとこだ。
OSのスレッド制御と通信の実装に継続を使う
Richard P. Draves Brian N.Bershad Richard F.Rashid Randall W.Dean
Oct 1991
要約
我々は。内部のスレッドとプロセス間通信の枠組を継続をその制御の移行の基
本として使うように再設計することによって、Mach3.0 OSの性能を向上させた。
以前の版のMach 3.0に較べて、新しいシステムはスレッドあたり85%の少ない
空間を消費する。アドレス空間をまたがる、遠隔手続き呼び出しでは14%早くな
る。例外処理は60%速くなる。
システム性能の向上に加えて、継続をOSに共通な制御移行の最適化として一般
化し、これらの最適化を一つの実装方法論の視点から作り直した。この論文で
はMach OSで継続を使用するにあたっての我々の経験について記述する。
1. 導入
継続を実行コンテキスト間の制御移行の基底として使うように、Mach 3.0 OS
を再設計することで大幅な性能の向上を達成した。我々のシステムでカーネル
内でスレッドがブロックされるのは二つの方法がある。一つは、レジスタ状態
とスタックを保存し、その状態を元に戻すことで実行を再開する。もう一つは、
継続としての再開(スレッドが走る時に実行されるべき関数)を指定する。継続
としてスレッドをブロックすることを許すことによって、カーネルプログラマ
は、スレッドの管理の時間と空間を押さえることができる。継続を使うことに
よって、スレッドはそのスタックをブロックされている間、捨てることができ
る。その結果カーネルの中のスレッドの空間を押さえることができる。
継続によってまたスレッドはブロックされている間の実行状態の高レベルの表
現をすることができ、その状態を調べて、作用することができるので、制御移
行のオーバーヘッドを軽減することができる。
継続を使うことが難しい場合には、継続によってスレッドをブロックしないこ
とによって、カーネルプログラマは伝統的な様式の並行処理プログラミングが
できる。
継続によってMachカーネルの記憶領域の必要量を減らすことができ、実行時の
性能も向上した。以前に較べて、例えばDECstation 3100上の最適化版のMach
3.0はスレッド毎に資源を持つのではなくプロセッサ毎にカーネルスタックを持
つスレッドは85%の空間で済む。
アドレス空間をまたぐ遠隔手続き呼びだし(RPC)は14%速い。例外処理の性能は
UNIXではないOSのエミュレーションに決定的で、2倍から3倍で性能が向上した。
さらに、継続によって一つの実装方法論の見地から多くの制御移行の最適化が
可能になった。
この論文で述べるシステムはカーネギーメロンや他の場所の研究者が日常的に
使用している。マルチスレッドプログラミングと分散コンピューティングをサ
ポートするのにスレッドとプロセス間通信に頼ったMachのようなOSのカーネル
に対して、この制御移行を管理するのに継続を使う技術は似たような結果をも
たらすと信じている。
1.1 OSカーネル内での制御の流れの管理。
過去において、OSはカーネル内の実行形態は二つのうちのどちらかによってき
た。プロセス形態と割り込み形態だ。プロセス形態では
カーネルのアドレス空間はシステム内の全てのスレッドのために一つのスタッ
クを持っている。スレッドが、システムコールやフォルトによってカーネルに
トラップされると実行状態を保持するために専用のカーネルスタックを使う。
このやり方では、スレッドはブロックされている間その全ての状態を保持して
あるので、カーネル内の実行中はいつでも、そのスケージュリングをすること
ができる。UNIX[Ritchie & Thompson 78]はこのプロセス形態によるOSの例だ。
プロセス形態とは対照的に、割り込み形態はシステムコールとフォルトを割り
込みのように扱う。:全てのカーネル内実行は、カーネルアドレス空間内のプロ
セッサ毎の一つのスタックを使う。カーネル内でブロックしたスレッドは、は
じめにその実行コンテキストに対する情報を退避しなければならない。この退
避された情報は後にブロックされたスレッドが適切な状態で再開するために使
われる。QuickSilver[Haskin et al. 88]とV[Cheriton 88]はこの割り込み形態
によるOSの例だ。
プロセス形態の一番の利点はプログラムが簡単なことだ。カーネルスレッドは
ブロックしたり、ページング可能な記憶領域を参照するのに「特別な」制限が
ない。残念ながらプロセス形態には性能に関する問題が二つある。一つ目はそ
れぞれのスレッドがカーネルアドレス空間のスタックを必要とするため、プロ
セス形態は大量の記憶領域を消費してしまう。二つ目は、カーネルスタックが
ブロックされたスレッドの状態が、リターンアドレスや退避されたレジスタ、
自動変数を機械レベルで反映しているので、その状態を評価するのと、スレッ
ドの移行管理の遅延を減らすための最適化をすることが難しい。
1.2 Machにおける制御移行の歴史の概要
初期の版のMachカーネルは二つの理由によりプロセス形態によっていた。一つ
はMachカーネルはAccent[Rachid & Robertson 81]の後に作られ、それはプロセ
ス形態を使っていた。Machの全体的な設計と実装は直接Accentに由来していた
のでAccentのプロセス形態を使うのが自然だった。二つ目は初期の版のMachは
UNIX互換層をカーネルモードで実行していた。この層はプロセス形態である
BSD Unix[Leffler et al.89]を使って実装されていた。これらのコードがカー
ネル内に残っているため異なる形態を使うことは大変な努力が必要だ。
Machの発展につれて、プロセス形態は適切でないことが明らかになってきた。
Accentではスレッド管理の基本操作はマイクロコードによって行なわれ、そし
てそれらは機械のCPU速度にくらべて十分に速かった。対象的にMachは広い範囲
のアーキテクチャで動くように設計された。なのでマイクロコードがスレッド
管理の手間を軽減するという仮定はできなかった。さらにAccentと違って、
Machは一つのアドレス空間に対して多数のスレッドの管理をサポートする。こ
れは結果として少量のプログラムが大量のカーネルスレッドを使うことになっ
た。プロセス形態ではこれらのスレッドはそれぞれ4KBのスタックをカーネルア
ドレス空間にもつ。最終的にUnix互換コードはカーネルからユーザ空間に移動
[Golub et al.90]したので、純粋にUnix互換をサポートするためのプロセス形
態を使う必要はもはやなくなった
プロセス形態の再検討は小さいシステムや、速いRISC単一プロセッサ、マルチ
プロセッサへの効果的な実装の要求によって加速した。今日一般に見つかるワー
クステーションは32MB、それ以上のメモリを積んでいるけれど、我々はMachを
小さいPC、ラップトップやノートブックで効率的に走らせたいと欲した。それ
らは大抵8MB以下程度のメモリである。結果としてカーネルのメモリ消費量の低
減が重要になった。さらに、プロセッサの速度の増大とともに、キャッシュと
TLBのミスの相対的なコストも増した。もしカーネルスタックをスレッド毎では
なくプロセッサ毎とできれば、カーネルスタックを参照する時のキャッシュ、
TLBミスの数が減るだろうと期待した。さらに、Machはキャッシュ一貫性マルチ
プロセッサの上でも走る。そのような機械ではプロセッサ毎のデータ構造とし
て扱うと最も効率的だ。[Anderson et al. 89]
あるスレッドから他のスレッドに制御が移行する遅延時間についても関与した。
我々の高速プロセス間通信(IPC)システム[Draves 90, Bershad 90]のデザイン
の経験では低い遅延時間の制御移行についていくつかの重要な教えがあった。
我々はこの知恵を一般的な方法として、カーネル層での制御移行に適用したかっ
た。とりわけOSは多くの部分はユーザ層で実装されているので、アドレス空間
間のRPCに低遅延は重要とはいえ、それ以外例外処理のような経路も重要になっ
てきた。高速例外処理は、例えば、仮想メモリの基本操作をユーザ層から使う
[Appel & Li 91]場合や、OSの上で他のOSをエミュレートする時に必要になって
くる。さらに、Machは広範囲のプロセッサ上で動くので一般的な解決方を機種
非依存に適用できることが重要だ。その場限りのアセンブリ言語による性能の
向上策は許容できない。
1.3 いくつかの適切でない解決策
非常に初期、カーネル内の大量のスレッドを管理に関連する大きさと速度のの
問題を処置をする必要があることに気付いた。最初の解決策として、ユーザ層
のスレッド、C-Threads[Cooper & Daves 88]を、ユーザ層のスレッドをカーネ
ル層のスレッドの上に多重化するように変更した[Golub et al 90]。一つのカー
ネル層スレッドが同じアドレス空間を同じくする多数のユーザ層スレッドをサ
ポートすることで、大量のスレッドのために必要とされるカーネル空間を低減
しようという狙いだ。さらに他[Anderson et al. 91, Marsh et al.91]で注意
したように、ユーザ層のスレッドは、同じアドレス空間内でのスレッドスイッ
チの遅延を低減できる。
我々のC-Threadsの使用は緩和したが、プロセス形態の空間的問題は解決されな
かった。第一に、カーネルスレッドはアドレス空間の間で共有できないので、
アドレス空間毎に少くとも一つのカーネル層のスレッドがまだ必要だ。Machを
このようにしたことで、重大な保護の問題が発生した。それぞれのエミュレー
トされたUnixプログラムは一つのカーネルスレッドをUnix「プロセス」として
使う。そして、C-Threadのマルチスレッドプログラムは少なくとも一つのカー
ネルスレッドをそれを「仮想プロセッサ」として使う。
ユーザ層スレッドをカーネルのプロセスの上に置く形態の二番目の問題はカー
ネルの中で実行中にブロックされたスレッドはカーネルスタックを消費したま
まだということだ。結果として平均して、C-Thredadはシステム中のカーネル層
スレッドの数の低減は1/2程度にしかならないことに気付いた。
ユーザ層スレッドはアプリケーションとカーネルの関わりが少ない場合、性能
の向上に優れているマルチプロセッサプログラムはカーネルから離れている傾
向にあるが、サーバのようなマルチスレッドプログラムの我々の経験では、そ
れらは例えばIPC、ページフォルト、例外によってカーネルに集中する。なので、
ユーザ層スレッドは部分的にマルチスレッドプログラムの空間要求に手段を講
じるが、それだけでは十分ではない。カーネルの問題を、カーネル側の解決方
が必要だった。
QuickSilverやRIG[Ball et al. 76]のようなシステムの経験により、割込み形
態を考慮することになったが、最終的にはMachカーネルには不適切と結論づけ
た。割り込み形態は、スレッドがそれ専用のカーネルスタックを持たないため、
カーネルの使う資源が少ないのが魅力だ。他方で、この形態はプログラムが難
しい。というのは、ブロックする可能性のある操作は全て、状態を退避/復帰す
るための特別の目的のコードを必要とするからだ。
さらにこのコードはモジュールの境界を越えて覗かないといけないかもしれな
い、ブロックするモジュールはその状態をその呼び出し元のために保存するこ
とができるため。これはシステムの維持管理性の障害となる。Machはマルチプ
ロセッサ上で動く(すなわち内部でロックが使われる)、そして仮想メモリをサ
ポートする(つまりカーネルはページフォルトできる)ので割込み形態では管理
不能と感じ、だから許容できない。
1.4 継続による再構成
スレッドがブロックする際にプロセス形態でも割込み形態でも使えるように
Machカーネルを再構成した。プロセス形態を使ってスレッドがブロックする時
はその現在の実行状態はスタックに記録される。ブロックされたスレッドはコ
ンテキストスイッチによって再開される。スレッドが割込み形態を使ってブロッ
クする時は、実行状態をそれが再開されるべき場所の補助的なデータ構造に記
録する。それは継続[Milne & Strachey 76]と呼ばれる。ブロックしたスレッド
はとっておいた継続を呼び出すことで再開される。この新しいやり方は、プロ
セス形態、割込み形態をそれひとつで使うより、いくつかの利点がある。
+ プロセス形態の「使い易い」という利点がある。スレッドはそのスタックの
内容をそのままでカーネル内のどんな時でもブロックしてもいい。これは割
込み形態が便利ではない状況の時に重要だ。セマフォでブロックする時スレッ
ドが深くネストした関数の中である時や、カーネルで実行中にページフォル
トをする場合だ。
+ 割込み形態の性能のよさがある。 カーネルのコンテキストがない、あるいは
ほとんどないスレッドの時、言ってみればそれが他のスレッドからのメッセー
ジを受信するために待っている時、あるいは、次の命令がユーザ空間で実行
すべき時、そのカーネルスタックは全部放棄していい。さらに、継続は機種
非依存なインターフェースで使われるので継続を実行時に調べて、そしてそ
れを使うのを回避するすることがしばしば可能だ。システムの現在の状態は
その使用が必要ないようにできる。XXX
+ 他のOSに見つかる、多くの実行時の最適化の実装を一般的なフレームワーク
とインターフェースとして提供できる。多くの制御の移行に対する低層の最
適化は継続によって作り直すことができる。例えばハンドオフスケジューリ
ング[Black 90b, Thacker et al 88]、スタックなしカーネルスレッド
[Thacker et al.88],非同期I/O[Levy & Eckhouse 89]、カーネルからユーザ
のアップコール[Hutchinson et al.89, Anderson et al.91, Scott et
al.89]、軽量遠隔手続き呼出し[Bershad et al. 90]それぞれはIPCの最適化
と、継続を使って記述し実装できるスレッド管理システムを表現している。
さらに、継続の機種非依存なインターフェースを定義することによって、こ
れらの最適化は可搬性のあるコードで達成できる。
Machカーネルの中の様々な制御の移行を継続によって扱い、多くの場所に小さ
い最適化を一様なやり方で適用することでシステムの性能の向上を可能にした。
この論文ではMach 3.0 OSでの継続の使用とその性能について述べる。二章では
Machでの継続の実装について述べる。三章では継続を使用し、それによる最適
化の性能向上について調べる。四章では他のOSで見られるいくつかの制御移行
の関数にどうやって継続を実装することができるかを明らかにする。五章では
関連する研究について議論する。最後六章では我々の結論を要約し、紹介する。
2. OSカーネルで継続を使用する
この章ではカーネルプログラマの視点で継続を述べる。プロセス形態のカーネ
ルを継続が使えるように変換し、継続によっていくつかの一般的な最適化技術
が可能になる。そしていくつかの重要なカーネルサービスの継続による効果を
明らかにする。最後にMachカーネルでの継続を管理する機種非依存なインター
フェースを紹介する。
2.1 継続を作る
継続を必要とする二種類の制御の移行がある。スレッドがトラップあるいはフォ
ルトしてユーザ空間からカーネル空間に入る時のユーザとカーネルの境界の移
行と、カーネルの中であるスレッドから他のスレッドに制御が移る時だ。
ユーザ層でのシステムコール、例外、割込みは制御をカーネルに移行する。カー
ネルの入口では、カーネルから呼ばれた時に、制御をユーザ層に戻す継続を作
成する。制御は呼び出し元に戻らない。システムコールはそれを呼び出した所
へシステムコールの返り値とともに戻る継続を生成する。ユーザプログラムへ
の返り値はない例外と割込みは、後に呼び出されるところに継続を生成する。
カーネルの中ではスレッドはプロセッサを放棄する時に継続を作成する。スレッ
ドをブロックするカーネル手続きに関数ポインタを渡すことでこれはなされる。
関数はスレッドの継続になり、それはカーネルの機種非依存なスレッドデータ
構造として保存される。一層の実行時最適化がなければ、スレッドはその継続
の呼び出しによって再開される。
/* よく使われるシステムコール (変換前)*/
example(arg1, arg2) {
P1(arg1, arg2);
if (ブロックする必要) {
/* プロセス形態を使う */
thread_block();
P2(arg1);
} else {
P3();
}
/* 制御をユーザに戻す */
return SUCCESS;
}
/* よく使われるシステムコール (変換後)*/
example(arg1, arg2) {
P1(arg1, arg2);
if (ブロックする必要) {
/* 継続を使う */
コンテキストをスレッドに退避する;
thread_block(example_continue);
/* NOTREACHED */
} else {
P3();
}
/* 制御をユーザに戻す */
thread_syscall_return(SUCCESS);
}
example_continue() {
コンテキストをスレッドから復帰する;
P2(復帰したarg1);
/* 制御をユーザに戻す */
thread_syscall_return(SUCCESS);
}
図1: ブロックするカーネル手続きの変形
継続として特定された関数は通常の関数のように返らない。それは他の関数を
呼ぶか、継続のみしてよい。この点がクロージャと継続の違いだ。割込み形態
として、もしブロックするスレッドがどんな状態もブロック中に保持していな
ければならないのなら、明示的に全て保持しないといけない。カーネルのスレッ
ドデータ構造体は、28バイトのスクラッチ領域を含んでいる。もし、スレッド
がもっと大きな状態を保持しておきたいのなら、追加のデータ構造を割当てな
いといけない。そのような、簡便に、あるいは有効に継続とともにブロックを
することが不可能な場合、NULLを引数としてブロックする関数を呼べば、プロ
セス形態としてスレッドをブロックする。スレッドのコンテキストはスタック
に保持され、スレッドは同じコンテキストで再開する。
2.2 カーネルを継続を使うように変換する。
Machカーネルを継続を使うように変換するのは卒直な処理だった。まず最初に
カーネルの関数のうち、ブロックする可能性があり、そして少量の状態だけが
ブロックされている間に保持されればいい関数を見きわめた。そして、これら
の関数を二つの部分に分けた。:ブロック前と、その後に。ブロックの後、ある
いは継続からなる新しい関数を定義し、ブロック前の部分だけを元の関数に残
した。次に二つの部分のに共通なスタックの内容を見きわめて、それらをブロッ
クするスレッドのスクラッチ領域に蓄えるようにした。ブロック前の関数にお
いて、カーネルのブロックする関数に、ブロック後の関数を引数とするように
変更した。その関数はスレッドの継続となる。最後に、ブロック後の関数を呼
び出し元に戻るのではなく、継続を呼ぶように変更した。図1は変換例を図解し
ている。一つの関数は二つになり、二番目の関数はブロックする一番目の関数
の引数になる。
ほとんどの場合、ロックするカーネルの関数を継続に書き替えるのは難しくな
かった。ユーザスレッドがトラップされてカーネルに入る場合、一番最初にブ
ロックが起きるのはメッセージの受信、例外、ページフォルト、プリエンプショ
ンだ。それぞれは、ユーザからカーネルの移行(システムコール、例外、割込
み)の結果として起き、そしてそれぞれは処理されて、制御がカーネルに移った
時に作成された継続を使って、ユーザ層へ戻る。
カーネルの中だけで走るスレッドに対しては「ユーザ層に戻る」継続はない。
実際問題として、ほとんどのカーネルスレッドは無限ループで、イベントが起
こるまでブロックし、なにか作業をして、またブロックに入る。このようなス
レッドに対して、ループの本体を含む関数への継続を定義する。関数の最後の
文はこの関数自体への継続を共なったブロックになるので、その結果、末尾再
帰呼び出しによって無限ループを作ることになる。
2.3 継続を使った最適化技法
継続によってカーネルの性能を高める三つの一般的な制御の移行の最適化をす
ることができる。スタック放棄、スタック渡し、継続認識の三つだ。
継続はスレッドが再開するコンテキストを指定する。なのでスレッドのカーネ
ルスタックはブロックしている間、放棄することができる。これは空間と時間
を節約する。カーネルはブロックされているスレッドのスタックを他のスレッ
ドのスタックとして使うことができるので、空間を節約できる。さらに、もし
次に走るスレッドが継続を共なってブロックされていて、そのスタックを放棄
していたら、スレッドはブロックしているスレッドが放棄したスタックを直接
使うことができる。この二番目の最適化は「スタック渡し」と呼ばれる。カー
ネルのメモリ要求の軽減によって、継続は時間も節約することができる。それ
はカーネルの作業領域が減るので、TLBとキャッシュを有効に使えるようになる
からだ。
継続に制御を移す間の時間は最初に継続を実行時に(保持された継続、それは関
数ポインタであり、知られた値と比較することができる)調べることで減らすこ
とができる。この技術は継続認識と呼ばれ、スレッドが再開される時に、より
特定の(そして速い)コードを、スレッドの継続の替わりに使うことができる。
XXX さらに、スタック渡しの後にスタックポインタの変更なしに、再開された
スレッドは特定のコードをブロックしているスレッドの関数呼び出しコンテキ
ストで実行することができる。XXX
2.4 アドレス空間をまたいだRPCで継続を使う
MachにおけるOSサービスはアドレス空間をまたぐRPCを用いてユーザ層のサーバ
によって使われる。継続を使ってカーネルのRPC経路を再構成して、性能を向上
させた。
