091110

シーズンオフ。減量しなくていいし、夜更ししていいし、なんといってもイン フルエンザにかかってもいい(不要不急の外出を控えてました)。さっそく新宿 に繰り出して、呑んだくれてきました。優勝のメダルを見せびらかしては、自 慢してきました。あっという間に3kg弱太ってしまった。
太るのは一瞬だけれど、落とすのは大変だ。このあたりにしておこう...。とい いつつ、呑み屋主催の旨い物食べに行くツアーに参加することにしてしまった。
菜園状況、やっとチンゲンサイが収穫できる大きさになった。これ夏の終わり に蒔いたのだけど、秋は意外に成長が遅い。

キャベツは寒冷紗をかけておいたにもかかわらず、一株完全にヨトウムシに食 べられてしまった。おおむね順調。まだキャベツっぽさはない。

さて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.、これで読み終わり。

5 関連する研究

言語のコミュニティは20年ほど継続についての研究をしてきた。Wardは継続を
μ計算よばれるメッセージの受け渡しの代数の基本要素として定義した[Ward
& Halstead 80]。そして、全ての制御の移行はその代数を使って表現できるこ
とを示した。並行実行と'first-class'の継続をサポートする関数型言語は後者
を使って前者を成功裏に実装した[Wand 80,Haynes & Friedman 84, Cooper &
Morrisett 90]。これらの試みは同じアドレス空間のユーザ層どうしのコンテキ
スト間の制御の移行に集中している。関数型言語はしばしば 関数呼び出しのス
タックを実装するのに、非連続なデータ構造を使う。そしてスタックを放棄す
る能率を部分的に減らす。(カーネルスレッドの放棄できる状態の多くの部分は
活動中の一番下のコールフレームの上の使われていないスタック領域である)
さらに、多くの関数型言語は関数オブジェクトが同一であることの評価を許し
ていないので、継続認識をやりにくくしている。Lampson[Lampson et al. 74]
は初期のMesa言語[Geschke et al.77]に対する、継続を基本にした一般的な制
御移行のインターフェースをに書いた。

とても制限されたLampsonのインターフェースが、後にTopaz[Schroeder &
Burrows 90]のアドレス空間をまたぐRPCの実装として現れた。TopazはDEC SRC
の実験的なマルチプロセッサワークステーション[Thacker et al 88]、
Fireflyのために設計されたOSである。そのインターフェースはアセンブリ言語
で実装され、スタック受け渡しはするが、継続認識を使わず、共有スタックも
使わない。(SRCのRPCは高度に最適化されていて、全てはレジスタに保存される
ので、スタックには重要なコンテキストない) Topazは、カーネルスレッドがブ
ロックする時、それが再スケジューリングされた時に即座にユーザ層で実行さ
れる場合にはスタックを放棄することを可能にしていた。Topazはセマフォと条
件変数をカーネルで実装していたので、これはユーザ層のイベントでブロック
するスレッドに重要な最適化である。この二つの最適化にもかかわらず、
Topazのカーネルでは、スレッドがプロセス形態のままスタックを持ったままブ
ロックする場面が多くあった。DEC SRCの5プロセッサ、96MBのFireflyでの最近
の計測では、886個のカーネルスレッドが、212個のカーネルスレッドを使用し
ている。カーネルの内部スレッド(28)、完了待ち(106)、ネットワークパッケッ
ト待ち(20)、例外処理の待ち(38)である。継続によってFireflyのアドレス空間
をまたぐRPCは向上しないと思うが、多数のカーネルスタックによって消費され
る、バス、キャッシュ、メモリは軽減されるだろう。例えばMachでは886の似た
ようなブロックしているカーネルスレッドがあったとしても、6スタックしか必
要としないだろう。Fireflyの5つのプロセッサそれぞれのと、特別なカーネル
スレッドのだ。

QuickSilver[Haskin et al.88]、V[Ceriton 88]、MS-DOS[Duncan 86]のような、
割込み形態で実装されているOSは継続と等価なものをそれだけで使う。例えば
Vカーネルでは、"finish_up"関数をスレッドの記述子に結びつけ、それがブロッ
ク後に再開するスレッドの算定を可能にしている。しかしながら、これらのシ
ステムでは、プロセス形態を安全網として使うことができないので、カーネル
内部の構造が複雑になってしまっている。例えば、カーネルの中で実行する場
合ページフォルトは一般的に許されない。そして、マルチプロセッサに必要な
カーネル層の単純なロックですら難しい[Cheriton 91]。

継続認識を一般的な最適化技法として使用、あるいは、ユーザ-カーネル境界の
行き来をユーザ層のアップリケーションによって作用されることができる継続
を基本とした制御移行として扱うようなプロセス形態と割込み形態を組み合わ
せたシステムは他に見つからなかった。

6 将来の研究と結論

Machにおける継続の研究は進行中である。目下、ユーザ層のスレッドパッケー
ジであるC-Threadsで継続を使う実験中だ。ユーザ層のスレッドで継続が使用で
きるようにして、スタックを放棄できるようにし、もし可能であれば継続認識
をするようにするつもりである。ユーザ層で自身でスケジュールし同期をする
ようなアプリケーションには、継続によってその多数のユーザ層のスレッドに
よる空間とオーバーヘッドの時間を軽減すると期待している。

当初、コンテキスト間の制御の移行の実装や記述をする機構としての継続の柔
軟性と力を認識していなかった。この研究の新規性は、継続を一般的なOSカー
ネルに適用できるようにしたことにある。継続を使って、可搬性のある新しい
最適化をすることができるようになり、他のOSにある、いくつかの最適化を一
つの抽象化を使って作り直すことができる。結果として、相当なシステム性能
の向上を図ることができた。

この論文で述べた方法論と技術は他のOSカーネルにも適用して、同じような結
果をもたらすと思う。Mach 3.0カーネルのソースを含む我々のシステムを
cs.cmu.eduの匿名ftpから手に入れて調べることを勧める。

さっそくマイOSに実装しはじめてます。マイOSはRAM2KBの状況もあるため、リ ソースの確保は全てユーザがすることとしている。カーネルは一切のリソース の確保をしない。スレッドは、その制御領域とスタックを連続領域でカーネル に渡すという仕様なので、まずはスタックを別体にできるようにインターフェー スを変えないといけない。そして、スレッドを放棄できるようにするという設 計ということは、スレッドを作成した時にスタックを確定できないので、これ は全ての場合を考え直して作り直さないといけない。結構難しい。