タイムシェアリングシステムのモデル

本節では、プロセス間通信を行うのに特に適していると私が考えるタイムシェアリングシステムのモデルを述べる。このモデルタイムシェアリングシステムの基本構造は独創的なものではない [5][9]。

モデルタイムシェアリングシステムは2つの部分から成る。モニタとプロセスである。モニタはいくつかの機能を担う。すなわち、適切な時点で (例えばプロセスが「十分な」時間を使い切ったときや割り込みが発生したとき) 制御をプロセスからプロセスへ切り替えること、主記憶とスワップ媒体を管理すること、制御があるプロセスから別のプロセスへ渡ることを制御すること (すなわち保護機構)、プロセスを生成すること、眠っているプロセスの面倒を見ること、などである。

プロセスは、タイムシェアリングシステムで通常は管理プログラムの機能と考えられている機能の大部分 (システムプロセス) を担うと同時に、通常のユーザ機能 (ユーザプロセス) も担う。典型的なシステムプロセスはディスクハンドラやファイルシステムである。効率上の理由から、システムプロセスは主記憶に固定されていると考えると役に立つ場合がある。

プロセスはモニタに対していくつかの機能を要求できる。すなわち、別の同等で自律的なプロセスを開始すること (つまり、プログラムをロードするか、共有可能なプログラムの複製をどこかで見つけてそれを開始し、初期パラメータをいくつか渡すこと)、走っているプロセスを停止すること、現在のプロセスを指定された事象の発生まで眠らせること、指定されたプロセスにメッセージを送ること、指定されたプロセスからメッセージを受信できる状態になること、任意のプロセスからメッセージを受信できる状態になること、任意のプロセスから受信できるプロセスにメッセージを送ること、一意の番号を要求すること、である。疑いなく他にもモニタの機能があるべきである。自分が使わされているモニタにこれらの機能を備えさせられることを納得するのは、読者の演習問題として残しておく。ほとんどのモニタで可能である。

ここでは保護についての考察には立ち入らず、すべてのプロセスが決して誤りを犯さない「良い」プロセスであると仮定する。本覚書を読むにあたって念頭に置くべき保護構造が必要なら、[5][6][7][8] に述べられている capability システムで満足できるはずである。

次に、プロセスがモニタに要求できる上記の8つの操作を、もう少し詳しく見てみよう。

START. この操作は別のプロセスを開始する。パラメータは2つある。すなわち、ロードすべきプログラムの何らかの識別情報と、そのプログラム用のパラメータリストである。プログラムがロードされると、与えられたエントリポイントから開始され、パラメータリストは何らかのよく知られた方法で渡される。このプロセスは、自分自身を停止するまで存在し続ける。

HALT. この操作は、現在走っているプロセスを、何らかの事象の完了まで眠らせる。パラメータは1つで、待つべき事象である。事象の例としては、ハードウェア割り込みの到着、別のプロセスからのメッセージの到着などがある。プロセスは SLEEP 命令の次の命令から再開される。プロセスが自分のタイムクォンタムを使い切った場合を除き、モニタが一方的にプロセスを眠らせることはない。

RECEIVE. この操作は、別のプロセスがこのプロセスにメッセージを送ることを可能にする。パラメータは4つある。すなわち、メッセージを待つポート (定義は後述)、メッセージを受け付ける相手のポート、メッセージ受信用に用意できるバッファの指定、そして伝送完了時に移る先の位置である。[言い換えれば、割り込み位置である。割り込みや事象チャネルなどに使うために、どのメッセージポートを使ってもよい。何を使うかはユーザがプログラムする。]

SEND. この操作は、他の何らかのプロセスにメッセージを送る。[プロセスは自分自身にメッセージを送ることもできると思う。] パラメータは4つある。すなわち、メッセージを送る先のポート、メッセージを送り出す元のポート、メッセージそのもの、そして伝送完了時に移る先の位置である。

RECEIVE ANY. この操作は、任意のプロセスがこのプロセスにメッセージを送ることを可能にする。パラメータは4つある。すなわち、メッセージを待つポート、メッセージ受信用に用意できるバッファ、メッセージを受信したときに移る先の位置、そしてメッセージを送ったポートを記録できる位置である。

SEND FROM ANY. この操作は、任意のプロセスからメッセージを受信できるプロセスに、メッセージを送ることを可能にする。SEND と同じ4つのパラメータをもつ。この操作が必要な理由は後述する。

UNIQUE. この操作はモニタから一意の番号を得る。

port とは、プロセスへ向かう、あるいはプロセスから出る特定のデータ経路である。すべてのポートには、そのポートを識別するために使われる一意の番号が対応づけられている。ポートは、あるプロセスから別のプロセスへメッセージを伝送するのに次のように使われる。通信したい2つのプロセス A と B を考える。プロセス A は、ポート M からポート N へ RECEIVE を実行する。

プロセス B は、ポート M からポート N へ SEND を実行する。モニタはポート番号を突き合わせ、メッセージをプロセス B からプロセス A へ転送する。バッファがプロセス B から完全に送り出されるとすぐに、プロセス B は SEND 操作で指定された位置から再開される。メッセージがプロセス A で完全に受信されるとすぐに、プロセス A は RECEIVE 操作で指定された位置から再開される。プロセスが、他のプロセスと通信するための正しいポート番号をどうやって手に入れるかは、モニタの関心事ではない。この問題はプロセス側に残される。

一例。モデルタイムシェアリングシステムが、常に走っているいくつかのプロセスをもつように初期化されているとしよう。さらに、これらの常駐プロセスは、普遍的に知られていて恒久的に割り当てられたポートをいくつかもっている。[あるいは、恒久的に知られているポートがただ一つだけあり、それが常駐プロセスとよく知られたポートの対応表を保持するディレクトリプロセスに属している、という場合もあるかもしれない。] 常駐して走っているプロセスのうち2つが、ロガープロセスとテレタイプ走査プロセスであるとしよう。テレタイプ走査プロセスは最初に走り始めるとき、ハードウェアのテレタイプ走査装置からの割り込みを待って自分を眠らせる。ロガープロセスは最初、よく知られた恒久的な SEND ポートと RECEIVE ポートを介してテレタイプ走査プロセスからメッセージが届くのを待って自分を眠らせる。テレタイプ走査プロセスは、テレタイプ番号で索引づけられた表を保持しており、各項目には、そのテレタイプから文字を送る先のポートと、そのテレタイプ用の文字を受け取るポートが入っている。文字が到着し (テレタイプ走査プロセスが起き)、そのプロセスがそのテレタイプ用の項目をまだもっていなければ、モニタから (UNIQUE によって) 一意の番号を一対取り出し、その一対の番号を含むメッセージを、ロガープロセスが RECEIVE を保留していると分かっているポートを使ってロガープロセスへ送る。[実際、その一対のポート番号が同時に1つの実行プログラムの複製にしか渡されないのであれば、走査プロセスは特定のテレタイプに対して常に同じ一対のポート番号を使ってもよい。] 走査プロセスはその一対の番号をテレタイプ表にも登録し、そのテレタイプからの文字、および今後そのテレタイプから来るすべての文字を、2番目の番号のポートから1番目の番号のポートへ送る。走査プロセスはおそらく、テレタイプ出力に使うための2対目の一意の番号もロガープロセスに渡し、これらの番号を使って RECEIVE を行う。ロガープロセスは、走査プロセスからのメッセージを受け取ると、SDS 940 TSS [12] の利用者がエグゼクティブと呼ぶもの (ファイルのディレクトリを印字し、他のテレタイプに誰がいるかを教え、サブシステムを走らせるなどのプログラム) の複製を1つ立ち上げ、そのエグゼクティブの複製とポート番号を渡す。これにより、このエグゼクティブプロセスもこれらのポートを使ってテレタイプへの入出力を行える。ロガープロセスが利用者からジョブ番号とパスワードを得たい場合は、これらのポート番号をエグゼクティブに渡す前に、一時的に利用者との通信に使うことができる。

Port numbers はしばしばプロセス間で受け渡される。よりまれなのは、ポートそのものが別のプロセスへ移転される場合である。一度あるプロセスが port を他のプロセスへ移転したら、最初のプロセスはそのポートを使わなくなる、ということが決定的に重要である。これを強制する機構を追加することもできる。[8] の保護オブジェクトシステムはそのような機構の一つである。[もちろん、保護オブジェクトシステムが使えるのであれば、伝送が行われる前に2つのポート番号を指定する必要は実際にはない。プロセスが既存の RECEIVE ポート番号を知っていること自体が、そのポートへ送る権利の一応の証拠である。そうすると RECEIVE ポートと RECEIVE ANY ポートの違いは、ある特定のポート番号の複製が何部配られたかだけに依存する。この考え方に基づくシステムのほうが、ネットワーク内の自律的なタイムシェアリングシステムすべてがこの保護機構を採用すると仮定できるなら、明らかに本稿で述べるシステムより好ましいであろう。その仮定が置けないのであれば、両方のポート番号を要求するほうが実際的と思われる。]

モニタのどこかに、ポート番号をプロセスと再開位置に対応づける表がなければならないことに注意されたい。この表の項目は、SEND/RECEIVE の対応付けが行われるたびに消去される。また、あるプロセスが走っており (おそらく眠っており)、RECEIVE ANY を保留しているなら、その受信ポート番号を知っている任意のプロセスが、ロガーなどを通さずにそのプロセスと話せることにも注意されたい。これはローカルのタイムシェアリングシステム内では明らかに不可欠であり、資源共有という理想を達成するのであれば、より一般的なネットワークでも非常に有用と思われる。

SEND が実行されると、対応する RECEIVE が実行されるまで何も起こらない。しばらくの間、適切な RECEIVE が実行されなければ、その SEND は一定時間後にタイムアウトし、SEND を行ったプロセスに通知される。RECEIVE が実行されたのに対応する SEND が長い間起こらなければ、その RECEIVE はタイムアウトし、RECEIVE を行ったプロセスに通知される。

RECEIVE ANY は決してタイムアウトしないが、取り戻すことはできる。SEND FROM ANY のメッセージは常に直ちに送られ、適切な受信者が存在しなければ破棄される。エラーメッセージは返されず、確認応答があるかどうかはプロセス次第である。SEND と RECEIVE を対応づける表があふれた場合は、さらに SEND や RECEIVE を発したプロセスに、その SEND や RECEIVE がタイムアウトしたのと同じように通知される。

一般に、よく知られ恒久的に割り当てられたポートは、RECEIVE ANY と SEND FROM ANY を介して使われる。恒久的なポートは、プロセスを起動するために使われることが最も多く、したがってそれらを介して送られるデータはわずかである。

さらにもう一例。今度は FORTRAN コンパイラの使用を示す。利用者がテレタイプの前に座り、エグゼクティブにつながる様子はすでに説明した。そこから続けよう。利用者はエグゼクティブと入出力しており、エグゼクティブは SEND と RECEIVE を行っている。やがて利用者が RUN FORTRAN と入力すると、エグゼクティブはモニタに FORTRAN コンパイラの複製を1つ立ち上げるよう要求し、テレタイプと話すためにエグゼクティブが使っていた2つのポートを起動パラメータとして FORTRAN に渡す。FORTRAN はもちろんこれらのパラメータを期待しており、利用者がどの入出力ファイルを使いたいかを知るために、これらのポートへ SEND と RECEIVE を行う。FORTRAN は利用者に INPUT FILE? と印字し、利用者は F001 と答える。すると FORTRAN は、何かすることを待って眠っているファイルシステムプロセスにメッセージを送る。メッセージはよく知られたポートを介して送られ、F001 を入力用に開くようファイルシステムに要求する。メッセージには、ファイルシステムプロセスが返信を送るのに使える一対のポートも含まれている。ファイルシステムは F001 を調べ、入力用に開き、そのオープンファイル表にいくつか項目を作り、FORTRAN がそのファイルを読むのに使えるポートを含むメッセージを FORTRAN へ返す。出力ファイルについても同じ手順が踏まれる。コンパイルが完了すると、FORTRAN はテレタイプのポート番号を、FORTRAN からのメッセージを待って眠っていたエグゼクティブへ返し、その後 FORTRAN は自分自身を停止する。ファイルシステムプロセスは、他にすることがなくなると眠りに戻る。

[読者はもうお気づきだろうが、私は、別の利用者がそのプログラムを使いたくなるたびに新しいプロセス (そのプログラムの新しい概念上の複製から成る) が立ち上げられる、という考え方が好きではない。むしろ、そのプログラムを1つのプロセスと考え、それが多数の他のプロセスから同時に使われていることを自覚し、利用者の間で意識的に多重化するか、手が回るようになるまで利用者へのサービスを遅らせる、と考えるのが好きである。]

さらに、ファイルシステムプロセスは、ファイルシステムの利用者に使い終わったポート番号を返してもらえるなら、繰り返し使う小さなポート番号の集まりを保持できる。もちろん、このポート番号の集まりが最終的には少しずつなくなっていけば、ファイルシステムはモニタから新しい一意の番号をいくつか得ることができる。

2つのプロセスが通信したいとき、彼らは自分たちで接続を設定し、双方にとって都合のよい方法でそれを自由に行えることに注意されたい。例えば、ポート番号を交換してもよいし、一方のプロセスがすべてのポート番号を選び、もう一方にどれを使うかを指示してもよい。もちろん、タイムシェアリングシステムの特定の実装では、システムの作成者がプロセスによる SEND と RECEIVE の実行を制限し、ポート番号の勝手な受け渡しを禁じ、代わりにモニタ (または何か他の特別なプログラム) を呼び出してこれらの機能を行わせることを選ぶかもしれない。

本システムでは、流量制御は単純な方法で提供される。すなわち、受信側が RECEIVE を実行するまで、あるプロセスからの SEND を決して開始しないのである。もちろん、プロセス間でメッセージをやり取りし、あるプロセスに送信を止めるよう促したり、空間を割り当てるよう促したりすることはできる。