3. GORDO における実装

3.1 GORDO の紹介

GORDO は SDS Sigma 7 上に実装されたタイムシェアリングシステムである。以下に、本稿に関連するいくつかの特性を概説する。

3.1.1 GORDO ファイルシステム

ファイルシステムはページ指向である。ファイルとディレクトリから構成される。ファイルは見出しと、ファイルの本体を構成する多数のページから成る。ディレクトリは、ファイルまたは他のディレクトリのいずれかを指す多数のエントリから成る。

3.1.2 GORDO プロセス

• プロセスは、プログラム（手続きとデータ）とその論理的環境から成る。言い換えれば、プロセスは GORDO のスケジューラによって認識され制御されるプログラムである。
• ユーザー（ジョブ）は、コンパイラ、ローダ、エディタ、アプリケーションプログラムなど、さまざまに異なる複数のプロセスを持ち得る。プロセスはシステムコール (FORK) によって生成される。
• プロセスが参照できる空間は、128k ワード長の仮想空間である。その一部（8k）はオペレーティングシステム用に予約され、他の部分（120k）はユーザーが直接アクセスする。後者は、結合時に異なるファイルから取得したページを仮想空間の自分の部分に埋めたり変更したりすることができる。（後述のサービスコール参照。）図 3 はこの結合を例示している。
• プロセスはシステムコールによってサービスを要求できる。本稿に関連するシステムコールは次のとおりである:

WAKE: スリープ中のプロセスを起こす（アクティブにする）ためのもの SLEEP: 他のプロセス（または自分自身）をスリープ状態にするためのもの COUPLE: ファイル空間から仮想空間へページを結合するためのもの。

• プロセスは通常スレーブモードで動作する。しかし、I/O プロセスとして設定されていれば、特権命令にアクセスできる。
• プロセスは、"mail box" ディレクトリに付けられたファイルを通じてデータを共有できる。

注記: 本ノートでは、プロセスとプログラムという語は互換的に用いられる。

[図 3 - 仮想空間と結合 - PDF ファイル参照]

3.2 ソフトウェア構成の概要

図 4 は全体構成を例示している。

システムは二つの主要なプログラム、"Network" と "Handler" に基づいている。

ハンドラは、IMP-HOST ハードウェアインターフェースに密接に関係する I/O 割込みルーチンである。ネットワークメッセージの送信および受信においてネットワークプロセスにサービスを提供する。

ネットワークプロセスが作業の大部分を実行する。

その主な機能は、コネクションの開閉およびネットワークメッセージの送受信に関するユーザーの要求を満たすことである。そのために、

• 割当表（HOST、CONNECT、INPUT LINK。3.3.1.1 参照）を用いてリンクを確立、識別、および切断する。
• ネットワークのメールボックスディレクトリを探索して新しいユーザーの存在を認識する。
• メッセージと要求が交換される共有ページ（コネクション共有ページ）を介してアクティブなユーザーと通信する。
• 受信／発信メッセージを作業ページ内でフォーマットする。この作業ページには拡張部分（緊急リング）がある。
• I/O 通信バッファを含む共有ページ（I/O 通信ページ）を介してハンドラと通信する。

[図 4 - ソフトウェア構成の概要 - PDF ファイル参照]

3.3 ソフトウェアの記述

3.3.1 データ構造

3.3.1.1 割当表: HOST、CONNECT、INPUT LINK

ネットワークプログラムは、3 つのテーブルを用いてリンクとコネクションを確立、識別、および切断する:

遠隔 HOST # でソートされたテーブル。

コネクション # でソートされたテーブル。

入力リンク # でソートされたテーブル。

(a) HOST テーブル（図 5 参照）

これは空きの発信リンクを示すビットテーブルである。次の特性を持つ:

• 位置: ディスク常駐
• 結合: ネットワークプロセスの仮想空間に結合される。
• サイズ: 遠隔 HOST[s] と同じ数のスロット。
• スロット構造: 遠隔 HOST への可能な発信リンクと同じ数のビット、すなわち 256。
• アクセス: インデックス。各スロットは遠隔 HOST # を通じてアクセスされる。
• 特有の事項: テーブル全体を通じて、オンにできるビットは 64 個以下である。この数は、一度にアクティブにできる発信リンクの最大数に対応する（遠隔 HOST[s] の数がいくつであっても関係ない）。

(b) CONNECT テーブル

このテーブルはすべてのコネクションの環境を追跡する。

次の特性を持つ:

• 位置: ディスク常駐
• 結合: ネットワークプロセスの仮想空間に結合される
• サイズ: 使用中のコネクションと同じ数のスロット。
• スロット構造: 図 6 参照。各スロットは 2 ワード長である
• アクセス: インデックス。各スロットはコネクション # を通じてアクセスされる。その扱い方は 3.4 参照。
• 特有の事項 1: 主コネクションに対応するスロット構造は、補助コネクションのものと同一ではない（図 7 参照）。これは、ユーザーの識別と要求が主共有ページを通じて行われるためである。
• 特有の事項 2: このテーブルはコネクションページと並行して扱われる（3.3.2 (b) 参照）
• 特有の事項 3: このテーブルは主にメッセージの送信に使用される。（各コネクションについて、発信リンク # と遠隔 HOST #、すなわちメッセージの送信に必要なすべての情報を含む。）

(c) INPUT LINK テーブル

このテーブルはすべての着信（入力）リンクを追跡するため、CONNECT テーブルと密接に関係している。

[図 5 - HOST テーブル - PDF ファイル参照]

[図 6 - CONNECT テーブル: スロット構造 - PDF ファイル参照]

[図 7 - INSERT LINK テーブル: スロット構造 - PDF ファイル参照]

次の特性を持つ:

• 位置: ディスク常駐。
• 結合: ネットワークプロセスの仮想空間に結合される。
• サイズ: 着信リンク、すなわちコネクションと同じ数のスロット
• スロット構造: 図 7 参照。各スロットは 1 ワード長である
• アクセス: ハッシュ。ハッシュされるキー値は主に着信リンク # と遠隔 HOST # に基づく。
• 特有の事項 1: このテーブルは、次のコネクションを確立する間、コネクション番号を一時的に記憶するためにも使用される。その扱い方は 3.4 参照。
• 特有の事項 2: このテーブルは主にメッセージの受信時に使用される。（各着信リンクについて、対応するコネクション #、すなわちメッセージを渡すべきユーザー識別を間接的に含む）

3.3.1.2 バッファページ

これから記述するすべてのページは二つのバッファ（入力と出力）を含む。これらのバッファは、メッセージを受け渡すため、または処理するために使用される。

これらの各バッファのサイズは少なくともメッセージのサイズ、すなわち 8095 ビットに等しいべきである。両方のバッファが 1 ページ（512 ワード）内に収まるように、バッファサイズとして 253 ワード（8096 ビット）を選んだ。ページの残り 6 ワードは一般に制御用に使用される。

典型的なバッファページ構造を図 8 に示す。

(a) I/O 通信ページ

図 9 参照。

この I/O 通信ページは、ハンドラとネットワークプログラムの間のインターフェースとして使用される。

このページのバッファ内で、メッセージはハンドラによってワード単位で組み立てられ（入力）、または分解される（出力）。例えば、ネットワークプログラムによって出力バッファ内に整えられた "ready to go" メッセージは、ハンドラによってワード単位で送出される。

主な特性:

• 位置: コア常駐: ロックされたページ
• 結合: ネットワークプロセスの仮想空間に結合される
• 内容: * 着信メッセージ用の入力バッファ（253 ワード） 発信メッセージ用の出力バッファ（253 ワード）
  • 入力制御ゾーン（6 ハーフワード）
  • 出力制御ゾーン（6 ハーフワード）
• 構造: 図 9 参照。
• 特有の事項: * 入力バッファはハンドラによって満たされ（ハードウェアから読み取る）、ネットワークプログラムによって空にされる
  • 出力バッファについてはその逆である

(b) コネクション共有ページ（ユーザー・ネットワーク共有ゾーン）

一般的特徴:

• 共有ページはコネクションと同じ数だけある。
• ネットワークとユーザープロセスの間で共有されるこれらのページは、(1) メッセージをやり取りし、(2) 制御情報、例えば新しいコネクションを確立する要求を交換するための通信ゾーンを構成する。

主な特性:

• 位置: ディスク常駐
• 結合: ユーザープロセスの仮想空間とネットワークプロセスの仮想空間の両方に結合される。
• 内容: - 着信メッセージ用の入力バッファ（253 ワード）
  • 発信メッセージ用の出力バッファ（253 ワード）
  • 入力制御ゾーン（6 ハーフワード）
  • 出力制御ゾーン（6 ハーフワード）
• 構造: 図 10 参照。
• 特有の事項 1: - 入力バッファはネットワークによって満たされ、ユーザーによって空にされる。
  • 出力バッファについてはその逆である。
• 特有の事項 2: 主コネクション共有ページに対応する制御ゾーンは、補助コネクションのものとは異なる。これは、補助コネクション確立要求が "主コネクション制御ゾーン" を介してネットワークプロセスに伝えられるためである。

(c) 作業ページ

一般的特徴:

• このページにより、ネットワークプログラムとハンドラプログラムは異なるメッセージに対して独立に作業でき、したがってオーバーラップに寄与する。例えば、ハンドラがハードウェアへのメッセージ送信でビジーであるとき、ネットワークプログラムは次に送出されるメッセージをフォーマット（リーダ、マーキングなど）できるので、ハンドラが空きになり次第それを再起動できる。

主な特性:

• 位置: ディスク常駐
• 結合: ネットワークプロセスの仮想空間に結合される
• 内容: - 着信メッセージ用の入力バッファ（253 ワード）
  • 発信メッセージ用の出力バッファ（253 ワード）

注記:

受信時に、ユーザープログラムが新しいメッセージを受け入れる準備ができていないことがある。その場合、システムの詰まりを避けるため、ネットワークは着信メッセージを緊急リングのバッファの一つに一時的に格納する。（このリングが満杯であれば、ヘルプルーチンが呼び出される。）

送信時にはすべての操作が RFNM[s] と同期されるため、そのような手順を設ける必要はない。（ネットワークプログラムは、前に送信したメッセージの RFNM を受け取ったときにのみ、ユーザーが再送信することを許す。）

[図 8 - 典型的なバッファページ - PDF ファイル参照]

[図 9 - I/O 通信ページ構造 - PDF ファイル参照]

[図 10 - コネクション共有ページ構造 - PDF ファイル参照]

3.3.2 プログラム

3.3.2.1 ハンドラプログラム

一般的特徴:

これは、メッセージを送信または受信するために IMP/HOST ハードウェアインターフェースを駆動する I/O 割込みルーチンである。送信と受信は全二重モードで行われる。

主な特性:

• 位置: コア常駐。ハンドラはオペレーティングシステムと同じメモリゾーンにあり、その一部と見なすことができる。
• 起動: IMP-HOST ハードウェア割込みによる。この割込みは次のいずれかで発生する:
• 送信中に、メッセージのワードが IMP へ完全に送られたとき
• 受信中に、メッセージのワードが IMP から完全に受信されたとき
• アイドル時に、ハードウェアが Sigma 7 CPU から 'start input' または 'start output' 命令を受け取ったとき。これらの命令は、割込みを引き返させるため（結果としてハンドラを間接的に起動するため）にネットワークプログラムによって発行される。
• 主な機能: * 出力バッファの内容を送信して出力バッファを空にする（発信メッセージを IMP へ）。この操作はワード単位（32 ビット）で行われ、HOST-IMP ハードウェアを駆動するために "Write" 命令を利用する。
• HOST-IMP ハードウェアから受信したデータ（着信メッセージ）で入力バッファを満たす。この操作もワード単位で行われ、HOST-IMP ハードウェアを駆動するために "Read" 命令を利用する。
• 前述の操作のいずれかが完了したときにネットワークプログラムを起こす。

3.3.2.2 ネットワークプログラム

一般的特徴:

このプログラムは、コネクションの開閉およびメッセージの送受信のためにユーザーにサービスを提供する。ハードウェアとのインターフェースのためにハンドラを補助として使用する。

GORDO の観点からは、これは通常のプロセスであり、そのように扱われる。

主な特性:

• 位置: ディスク常駐。より正確には、スリープ中はディスク上にあり、プログラムによって起こされるとコアに呼び込まれる。
• 起動: ユーザープロセスまたはハンドラのいずれかによって発行される 'WAKE' サービスコールを通じて起動される。
• 主な機能: * ユーザーの要求に応じて発信コネクションを確立／削除する。そのために遠隔 HOST[s] へ制御メッセージ（2.4.2 参照）を送り、リンクを確立／解放させ、その後ユーザーに通知を返す。
  • 着信制御メッセージ（制御リンク上で伝送される）の処理を保証する。例えば、コネクションの確立／削除（遠隔 HOST によって要求されたもの）に寄与するためである。
• 発信メッセージの送信を準備する。共有ページからテキストメッセージを取り出し（メッセージはユーザーによってそこに格納される）、それらをフォーマットし（リーダ、マーキング、チェックサム…を追加）、送信のためにハンドラへ渡す。
• 着信メッセージの配送を保証する。これは上記の操作の逆である。メッセージを配送すべきユーザーはリーダを通じて識別される。
• 仮想空間構成: 図 11 参照。
• 特有の事項: I/O プロセスとして統合されているため、特権命令（ハンドラを間接的に起動するための RD/WD）にアクセスできる。

[図 11 - ネットワークプロセスの仮想空間 - PDF ファイル参照]

3.4 ソフトウェア手順

詳細なソフトウェア手順は、付録 A に添付されたフローチャートに示されている。

ただし、実装を素早く理解するために、以下にいくつかの典型的なソフトウェア手順を挙げる。

3.4.1 いくつかの典型的なシーケンスの記述

ユーザーが利用できるトランザクションのいくつかを考察し（2.4 参照）、それらが伴う基本的なソフトウェア手順を指摘する。各ケースについて、(i) ユーザープログラムが何をするか、および (ii) ネットワークプログラムが何をするかを記述する。

(a) 主リンクを開く（2.4.2 も参照）

(i) ユーザープログラムが行うこと[1]:

• ネットワークのメールボックスディレクトリにファイル名、例えば DATA を格納する。
• このファイルの最初のページを自分の仮想空間に結合する。
• このページに情報（自分のジョブ／プロセス #、遠隔 HOST #、例えば (i)）を格納する。
• ネットワークプロセスを起こす。
• スリープ状態になる。

(ii) ネットワークプログラムが行うこと:

• ネットワークのメールボックスディレクトリを探索し、ファイル DATA にアクセスする。
• このファイルの最初のページを自分の仮想空間に結合する（共有ゾーン、3.3.1.2 参照）。このページが共有ゾーン内で k 番目であるとする。k が内部コネクション # である。
• HOST テーブル（3.3.1.1 (a) 参照）の i 番目のスロットを探索し、最初のビット = 0、例えば (alpha) 番目のビットを選ぶ。alpha が発信リンク # に対応する。
• CONNECT テーブル（3.3.1.2 参照）の k 番目のスロットに情報（ジョブ／プロセス #、遠隔 HOST # (i)、発信リンク # (alpha)）を格納する。
• INPUT LINK テーブルにコネクション # (k) を一時的に格納する。これはこのテーブルにエントリを作成する際に行われる（キー値 "発信リンク # (alpha) + 遠隔 HOST # (i) + 発信フラグ" をハッシュする）。
• メッセージテキスト ENQ PRIM 0 0 a を準備し、リーダ、マーキング、チェックサムなどを追加して完全なメッセージをフォーマットする。
• ハンドラの状態（I/O ロックページ内のビット）を調べる。ハンドラが空きであれば、'ready to go' 制御メッセージを I/O ロックページの出力バッファに格納し、ハンドラを起動してスリープ状態になる。そうでなければスリープ状態になる。

しばらくして、ハンドラは完全なメッセージを受信したため、ネットワークプロセスを起こす。このメッセージは、コネクションの確立を確認応答するために遠隔 HOST によって送られた制御メッセージであると仮定する。メッセージテキストは次のとおりであるはずである:

ACK ENQ PRIM 0 0 alpha 0 0 beta

ここで beta は着信リンク # である。（2.4.2 参照）

次に、上記の制御メッセージを受信したときにネットワークプログラムが何をするかを見る:

• 同じキー値を再ハッシュすることにより、以前に INPUT LINK テーブルに格納されたコネクション # を取り出す（上記参照）。また、このエントリを削除する。
• 着信リンクのために INPUT LINK テーブルにエントリを作成する。そのためにキー値 "着信リンク # (beta]) + 遠隔 HOST # (i) + "着信フラグ" をハッシュする。このエントリに HOST # (i)、着信リンク # (beta)、およびコネクション # (k) を格納する。
• CONNECT テーブルの k 番目のスロットを、着信リンク # (beta) を格納して更新する。
• k 番目の共有ページ（ちょうど開かれた主コネクションに対応するページ）の 'net-user' ビットをオンにし、ユーザープロセスを起こす。
• スリープ状態になる。

(b) 主リンク上でメッセージを送信する

(i) ユーザープログラムが行うこと[1]。

• メッセージテキストを主コネクション共有ページの出力バッファに格納する（3.3.1.2 参照）。
• このページの 'user-net' ビットをオンにし、ネットワークプロセスを起こす。
• スリープ状態になる。

(ii) ネットワークプログラムが行うこと:

• ユーザー要求を探す。すなわち、コネクション共有ページを順に探索し、'user-net' ビットがオンになっているものを選ぶ。共有リスト上で選択されたページ # を k とし、K をコネクション # とする。
• 共有ページ k の 'request bits' を調べることにより、要求の型を判定する。それがメッセージ送信の要求であることを見出す。
• 共有ページ k の出力バッファからメッセージテキストを取り出し、完全なメッセージにフォーマットし、上記と非常によく似た方法でハンドラへ送る（主リンクを開くを参照）。
• スリープ状態になる。

[1] 注記: 第一段階では、ユーザーはネットワーク機能を自分のプログラムに直接書くことになる。後にサブルーチンがユーザーの利用に供される。これらのサブルーチンは 2.4 で記述されたものに非常に近いものになる。