091106

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. 続き。
スタックを放棄するのはこれは使いどころがある。要するに、カーネル スタックの一番上くらいしか使ってなくて、毎回ブロックする時には巻き上る ようなスレッドがたくさんあるなら、それらはブロックしている間にスタック の内容を保持している必要がないから共有で使ってしまおうという戦略だ。し かし、RPCの受信者から送信者にスタックを移行してデータを渡してしまおうと いうのはどうだ。これはマイクロカーネルだと、アドレス空間をまたいだデー タ転送が大量になる。サーバをユーザ空間で動かしているから。そのボトルネッ クを解消する狙いなのだろうけど、やり過ぎかな。この論文でも指摘している ように継続というのはとても使いどころが難しい。マイOSでも継続はファイバ という形で実装しているけれど、これも当初いろいろ遊んでみて、よっぽど縛 りをきつくしない限りデバッグ不可能なものになると感じて、結構縛りをきつ くしてある。それでもこの前のGPSパーサでは、結構はまった。

2.4 アドレス空間をまたいだRPCで継続を使う

MachにおけるOSサービスはアドレス空間をまたぐRPCを用いてユーザ層のサーバ
によって使われる。継続を使ってカーネルのRPC経路を再構成して、性能を向上
させた。

図2はMach RPCの半分を呼び出しの高速な経路を示している。単一のシステムコー
ルmach_msgはRPCの送信と受信の段階を一つの操作に統合する。依頼スレッドは
mach_msg をRPC要求メッセージをサーバにに送り、返信メッセージを受信する
ために使う。サーバスレッドはmach_msgを返信メッセージを依頼スレッドに送
り、そして次の要求メッセージを受信するのに使う。両方の場合で送信スレッ
ドは受信スレッドを起こし、そしてメッセージが届くまで自分自身をブロック
する。

送信スレッドはカーネルに入り、そしていずれユーザ層に戻る時の継続を作成
する。そして、受信することのできるスレッドを探す。もしそのようなスレッ
ドがみつからなかったら、遅い経路を使い、メッセージは待ち行列に入る。も
し送信者がスレッドを見つけたら、スタック渡しを受信者に対して行なう。こ
れは、送信スレッドをmach_msg_continueで、継続を共なったブロックされた状
態にしておき、そして、カーネルスタックを持たない。受け渡しは現在走行中
のスレッドから受信スレッドに変更するが、すぐには受信スレッドの継続を呼
ばない。その代わりに受信スレッドは送信者のmach_msgシステムコールのコン
テキストで走る。ここでスレッドは自分自身の継続をそれを使う前に確認する。

もしそれがmach_msg_continueであれば、受信者は同じ経路でブロックしたので、
mach_msgは高速RPC経路で完成し、カーネルの外に受信者のコンテキストで移行
する。それ以外に、mach_msgは受信者の保持された継続をカーネル内のメッセー
ジの処理のために呼びだす。XXXこれは起こり得る。例えば、受信者が最大量の
ような珍しいオプションや制限を特定した時。これは余分な処理が全ての受信
に対して必要で、なので受信者はさらに仕事をするために別の継続でブロック
しているかもしれない。実際のところ、余分な仕事はまれに必要になるだけで、
ほとんどのスレッドはmach_msg_continueと共にブロックする。

 継続を使用することによってRPC中の空間と時間のオーバーヘッドが軽減する。
Machの中のほとんど全てのスレッドは、通常メッセージを待っていているので、
それらがブロックしている間、そのカーネルスタックを放棄している。呼出し
の遅延は受渡しによって、ブロックしているスレッドはそのまだ活動中の関数
が再開するスレッドのコンテキストを呼ぶことができるので軽減される。XXX
再開するスレッドは以前に退避した継続を使って制御の以降を完成させてもい
いし、あるいは継承されたコンテキストの情報を使って、別の高速な経路を使っ
てもいい。この状況で、送信者と受信者のメッセージ処理はお互いに最適化す
ることができる。例えば、高速RPC経路は待ち行列の操作、何度もの同期、何度
も例外状況を調べるためにメッセージを解析することを避ける。その替わりに
メッセージは暗黙的に共通のスタックの上にあり、送信者は共有データ構造を
ロックし、受信者はそのロックを外す。そして送信者だけが、受信者でなく、
メッセージの例外的な状況(大きいデータのような)を確認する。

2.5 他の種類の制御の移行に継続を使う

RPC経路が一番繁雑に使われるけれど、いくつかの他のカーネル経路についても
継続を使用した。これらの経路は三つで、例外処理、スレッドプリエンプショ
ン、ユーザ層ページフォルトで、それぞれ異なるやり方で継続を適用すること
ができることを示そう。

 + 例外処理
 Machにおいて、全てのスレッドは例外サーバを持っていて、それはカーネルが
RPCとともにスレッドが例外を起こした時には呼ぶ。例えば、スレッドが読み込
み専用ページに書き込もうとして例外が起きた(それは共有の仮想メモリ上で動
いているため[Appel & li 91])、あるいは、特権命令を実行した(Machは
MS-DOS、Macintosh OSのような別のOSをエミュレートするため[Rose & Hacker
85])。例外サーバはカーネルカラの要求メッセージを受信して、それを処理し
ようと試み、ちょうど受けとった例外の状況の返答メッセージをカーネルに送
り返す。ほとんどの場合、サーバは例外を処理することができ、その返答メッ
セージによってカーネルが即座にフォルトを起こしたユーザ空間のスレッドを
再開する。
ユーザからユーザのRPCと違うにもかかわらず、例外サーバとやりとりでは、カー
ネルは通信の終点になる。継続を使って例外処理の遅延を軽減した。例外メッ
セージを送信するのに通常の経路に入る前に、フォルトを起こしたスレッドは
ここではカーネルモードで実行されているが、サーバスレッドがメッセージを
待っている状態かどうかを調べる(継続、mach_msg_continueを使って)。もしフォ
ルトしたスレッドがサーバを見つけたら、要求メッセージを作るのを延期して、
即座にサーバスレッドに対してスタック受け渡しをして、フォルトの情報を共
有されたスタックで直接渡す。これはフォルトしたスレッドがメッセージを送
信し、サーバがこれを受けとるようにした時のコピー、解析、待ち行列を操作
することを回避する。もし、mach_msg_continueで待っているサーバがない時は
遅い経路が使われる。

 + プリエンプティブスケジュール
スレッドの横取りは時計割込み中、もし現在のスレッドの実行単位が終了した
ら行なわれる。もし割込まれたスレッドがユーザ層であれば、割込まれてから
積まれたスタックは重要でなくなる。なぜならスレッドは単純にユーザ層の場
所から再開されるからだ。なので割り込まれたスレッドはユーザ層へのスレッ
ドに戻る継続を共なってブロックする。
 横取りへ継続を使うことが意味することは、最も走ることができて、しかし実
際には走っていないスレッドはカーネルスタックを必要としないということだ。
それはまた再スケジュールの遅延を少し軽減する。というのは、横取りされた
スレッドは再スケジュールされた後にカーネルスタックを巻き戻す必要がない
からだ。

 + ユーザ層ページフォルト
スレッドがユーザ空間の用意されていないページでフォルトした鴇、カーネル
が空いている物理ベージを見つけてそこにデータを積むまでブロックしないと
いけない。カーネルのフォルト処理はスレッドを、新しいページをマップして、
そしてユーザ層のスレッドを再開する継続と共にブロックする。フォルトした
スレッドのスタックの消費を軽減し、ほとんどメモリが残っていない時のカー
ネルのメモリの消費を簡便に軽減する。
 この最適化はユーザ層ページフォルトにのみ適用できる。カーネルでフォルト
した場合、そのカーネルの状態とスタックは保存される。カーネル層のページ
フォルトは継続を適用することがとても難しい例で、それは一般的にスレッド
はカーネル内の実行中のどこでもフォルトするからだ。この難しさのため、こ
の場合については、プロセス形態に頼ることにした。

継続はスレッドがユーザ層から自発的にそのプロセッサを放棄する時や、カー
ネルの内部スレッドが作業を待つためにブロックする時にも使われる。最初の
場合では、保存するカーネルの状態はない(横取りの時と同じように)。二番目
の場合では、2.2章で述べた末尾再帰を実装するのに継続を使用できる。

2.6 可搬性のあるOSカーネルでの継続の実装

stack_attach(thread, stack, cont)
  	switch_contextがスレッドを再開し、制御を用意された継続の関数に
	前に走っていたスレッドを引数として渡し、制御を移行するように、
	機種非依存な継続を機種依存の変形し、割当てられたカーネルスタッ
	クに積み、スタックを初期化する。
	
stack_detach(thread)
	スレッドのカーネルスタックを取り外して返す。

stack_handoff(new-thread)
	スタック受渡しをする。つまり現在のスレッドのカーネルスレッドを
	新しいスレッドに移動する。stack_handoffは必要であればアドレス空
	間を変更する。stack_handoffは新しいスレッドとして返る。

call_continuation(cont)
	現在のカーネルスタックポインタを初期化して、提供された継続を呼
	ぶ。この関数は、長く継続の呼び出し続く時にスタックが溢れるのを
	防ぐ。

switch_context(cont, new-thread)
	新しいスレッドをその保存されたカーネルスタックで再開する。もし
	必要ならアドレス空間を変更する。もし、現在のスレッドの継続が提
	供されたらswitch_contextはレジスタを保存せず、返らない。そうで
	なければ、switch_contextは現在のスレッドのレジスタとスタックを
	保存し、呼び出し元のスレッドが再スケジュールされたら、以前走っ
	ていたスレッドに返る。

thread_syscall_return(return-value)
	ユーザ空間からのシステムコールに返り値を特定して現在のスレッド
	のユーザシステムコールの継続を呼ぶ。(低層の機種依存トラップが
	システムコールの継続を作成する)

thread_exception_return()
	ユーザ空間から例外あるいはページフォルトしたスレッドに戻るために
	現在のスレッドの例外継続を呼ぶ。(低層の機種依存トラップが例外の
	継続を作成する)	

図3:機種依存の制御移行関数のカーネルインターフェース


thread_handoff(cont, new_thread) {
	old_thread = current_thread();
	old_thread->cont = cont;

	/* stack_handoff は current_thread()を変更する */
	stack_handoff(new_thread)
	/* ここで current_thread() == new_thread */

	/* スケージュリング状態を更新 */
	old_thread->state = WAITING;
	new_thread->state = RUNNABLE;
}

thread_continue(old_thread) {
	new_thread = current_thread();
	thread_dispatch(old_thread);
	(*new_thread->cont)();
	/*NOTREACHED*/
}

thread_dispatch(old_thread) {
	if (old_thread->cont) {
		stack = stack_detach(old_thread);
		/* スタックをプールに返す */
		stack_free(stack);
	}
	if (old_thread->state == RUNNABLE)	
		/* old_threadをrun queueに返す */
		thread_setrun(old_thread);
}

thraed_block(cont) {
	/* 現在のスレッドを止める */
	old_thread = current_thread();
	
	/* ready queueから次に走るスレッドを選択 */
	new_thread = thread_select();
	
	if (new_thread->cont) {
		if (cont) {
		   /* stack_handoffはcurrent_thread()を変更する */
		   stack_handoff(new_thread);
		   /* ここでcurrent_thread() == new_thread */
		   
		   old_thread->cont = cont;
		   if (old_thread->state == RUNNABLE)
			/* old_threadをready queue に返す */
			thread_setrun(old_thread);
		   call_continuation(new_thread->cont);
		   /*NOTREACHED*/
		} else {
		   /* 新しいスタックを作成 */
		   stack = stack_allocate();
		   stack_attach(new_thread, stack, thread_continue);
		}
	}
	
	thread_dispatch(switch_context(cont, newthread));
}

図4:制御移行インターフェースの使用


Mach 3.0カーネルはあらゆるプロセッサで動く。この可搬性はカーネルを機種
非依存部分、これはMachのカーネルインターフェースであり、機種依存の部分
は機械を管理する。機種非依存の部分は、スケージュリング、プロセス間通信、
仮想記憶を管理する。機種依存の部分は下層の機械的なトラップ、例外やMMUを
実装し、新しくスタックと継続の内部インターフェースを提供する。

新しいインターフェースは機種非依存のスレッド管理とIPC部分が、アドレス空
間を変更したり、スタックとスレッドの関係を管理したり、継続を生成、呼び
出すことを可能にする。その操作は図3に表にした。インターフェースはブロッ
クしたスレッドの継続に対して確認をしない。それはカーネルの機種非依存な
スレッドのデータ構造として保存されているので、カーネルモードで走るスレッ
ドは直接調べることができる。

図3のルーチンは高レベルのスレッド管理の操作をする操作の基本部分である。
図4に、いくつかのこれらの操作と、インターフェースがカーネルの中でどのよ
うに使われるかを紹介する。thread_handoffは特定されたスレッドに対して制
御を与える。それは、スタック受渡しをして、スレッドのスケジューリングの
情報を、古いスレッドはブロックされ、新しいスレッドが走っているように更
新する。関数は新しいスレッドの制御として返るけれど、新しいスレッドの継
続は呼ばない。これによって、thread_handoffの呼び出し元は継続認識(RPCや
例外処理の経路のような)をする機会がある。対称的にthread_blockは実行可能
なスレッドを選ぶ。もし、新しいスレッドが継続を持っていて、thread_block
の呼び出し元が継続を提供していたら、より効果的なstack_handoffの経路を使
う。そうでなかったら、witch_contextを呼ばなくてはならなくて、これはスタッ
クを変更する。

thread_blockの実装はswitch_context,stack_attach,stack_detachの相互作用
を説明している。thread_blockは古いスレッドのスタックの上で実行している
間は、古いスレッドのスタックを外すことも開放することもできないし、他の
プロセッサが見つかるかもしれない走行待ち行列にこの古いスレッドを置くこ
ともできない。したがって、その実装の最初のswitch_cotextは新しいスレッド
のスタックに変更し、新しいスレッドはthread_dispatchを使って古いスレッド
を処分する。もし新しいスレッドがスタックを持ってなかったら、
stack_attachはそれを初期化して、thread_continueを実行する。それは新しい
スレッドが古いスレッドを処分した後に呼ばれる継続を呼ぶ。

2.7 マイクロカーネル(原文Kernelized)の優位さ

Machにおける継続の有効さはMachがマイクロカーネルのOSだとい事実に起因す
ると思う。それは少ないインターフェースを提供し、いくつかの抽象概念だけ
を実装している。結果として、Machカーネルの中でスレッドがブロックするの
は小数の場所であり、実際にスレッドがそこでブロックするのいはさらに少な
い。Mach 3.0カーネルでスレッドがブロックし得る場所は大体60の場所がるけ
れど、99%以上のブロックは6つの場所だけである。期待されたように、この再
構成をこれらの「熱い場所」に焦点をあてた。カーネルの中の経路でまだ継続
が使用されていない場所はあるけれど、それらはまれな経路であり、それらの
性能への影響は無視できる範囲だ。
 対照的に、Mach 2.5のようなモノリシックOSに、継続を使うことはより難しい
ことだと思う。あのシステムではBSD Unixインターフェースを全部カーネルの
アドレス空間で実装していた。大くのスレッドはUnix互換層の深い位置でブロッ
クする。このようなスレッドに対して継続を作成するのは、大量の状態がその
カーネルスタックに乗った状態であるため、難しい。さらに、Mach 2.5では
180以上の場所でスレッドはブロックする可能性があり、「熱い場所」もない。
これらの理由から、少ない場所で継続を使うことができて、それが全体的な空
間と時間の軽減となったと思う。

2.8 ソフトウェア工学との関係

実際の継続の懸念はそれを使い過ぎることにある。割込み形態のカーネルが導
入で記述した問題に苦しんで終わってしまったことを避けるために、継続は思
慮深く適用されなければならない。この継続の使い方の鍵は、プロセス形態の
上でほとんどのカーネルの作業が同じように作業(ブロック)するというところ
だ。結果として大部分のシステムは、割込みモデルにするより、安定している。
継続を使った経路のコードは、呼び出し元が確実であることを信用しないとい
けないのでそういう意味では壊れやすい(例えば、thread_syscall_returnを使
うコードは、これ用に実装されたシステムコールでないといけない)。しかし、
システムの性能の向上の高く抽象化された方法を適用して、妥当な譲歩だと思
う。XXX

2.9 要約

継続はOSの抽象化の'first-class object'を進めることによって得られる一貫
性とその作用によって表現される。'first-class object'とはカーネルによっ
て操作されるものである。この意味で、継続はMachのpmapの抽象化[Rashid et
al. 87]に似ている。pmapは仮想から物理のメモリのアドレスマップを反映す
る'first-class object'である。メモリマップを抽象化し、それを機種依存の
実装(ページテーブルやセグメントレジスタ)と分離することで、pmapインター
フェースは可搬性があり、本来できなかった方法で最適化[Young et al. 87]す
ることができた。カーネルの'first-class'の抽象化としての継続は似たような
結果をあげた。