参考資料 : 並列・分散 OS ／分散システムにおける高速通信

４回生伊達新哉

1997 年 5 月 8 日／ 29 日（木）

1 並列・分散 OS(5 月 8 日分)

分散 OS Colonia を説明するため、分散 OS に関する本や、以前に書かれた論文を参考にして簡潔にまとめてみた。ここでは、まず前半で並列、分散 OS の概要を、後半でコンピュータ・コロニーと Colonia の説明を示すことにする。

2 並列・分散 OS の概要

2.1 プロセス

計算機システムにおいて、ユーザが依頼した仕事を計算機内部でユーザに代って実行する仮想的な実体をプロセスという。プロセスは、計算機システム内部において能動的に動作するもっとも基本的な実体であり、計算機で何らかの処理を行うにはプロセスによらなければならない。したがって、プロセスは計算機内におけるユーザの代理とみなされる。プロセスはプログラムの実行に対応し、その動作はプログラムに記述された内容に従う。

2.2 並列処理と分散処理

CPU を複数台備えたマルチプロセッサシステムにおいて、プログラムを同時に個々の CPU 上で実行することをマルチプロセッシングという。また、複数の CPU 上で物理的に同時に処理を行うことを並列処理という。

分散処理とは、複数の計算機をネットワークで結合し、互いに通信しあい利用しあうようにした処理形態を言う。これに対して、１台の計算機で処理する形態を集中処理という。

一般に、並列処理はマルチプロセッサの計算機で複数の CPU 上で同時に処理を行うことをいい、分散処理は異なる計算機上で同時に処理を行うこ

とをいう。しかしながら、両者の根本的な違いは、 プロセスあるいはプロセッサ間の距離である。距 離とは、表象的にはプロセッサ間の通信遅延であ るが、実際には物理的な距離や媒体に関わること が多い。距離が大きくなることによって、互いに作 用を及ぼし合うのに時間がかかるようになり、シ ステム内のすべてのプロセスが統一的なビューを 持つことが困難になる。これが分散処理を難しく している大きな理由である。 2.3 分散処理の目的 2.3.1 情報、資源の共用 我々が共同で作業を行う場合、互いの密接なコ ミュニケーションが必要である。計算機を使って 作業する場合は、互いに情報を交換し、共通の情 報、資源にアクセスすることができるよう、各人 が利用する計算機をネットワークで結合すること が一般に行われる。今日、ワークステーションや パソコンの普及により、作業環境のパーソナル化 は着実に進んでいるが、パーソナル化が進めばそ れだけ分散処理の必要性は増大する。そもそも人 が分散している以上、情報も分散し、それらを共 用するための機構が必要となる。情報、資源が容 易に共用できること、これが分散処理のもっとも 基本的な目的である。 2.3.2 性能の向上 複数の計算機が利用できるとき、１台の計算機 に与えられた処理のすべてを実行させるのではな く、利用可能な計算機に並行して処理を実行させ たほうがより計算機の利用効率が上がり、与えら れた処理を短時間で実行することができる。また、 負荷の軽い計算機と重い計算機があったとき、負 荷の軽い方により多くの処理を実行させたほうが

効果的である。負荷の分散は、システム全体の性能向上および個々の処理の効率化に不可欠の手法である。プロセッサの処理能力だけでなく、メモリやディスクの使用量についても負荷分散の手法が適用できる。

2.3.3 信頼性の向上

複数の計算機が利用できるとき、一つの処理を並行実行させるのではなく、同じ処理を複数の計算機に実行させることにより、システムに冗長性をもたせることができる。この場合、一台の計算機に障害が発生しても、ネットワークで接続された他の計算機に処理を代わりに実行させることにより、システム全体の機能を停止させることなく処理を継続して実行することが可能になる。すなわち危険が分散され、システム全体の可用性さらには信頼性を高めることができるわけである。

2.3.4 規模適用性

ネットワークに接続される計算機は一般に独立して動作可能で、また分散環境に対応するためシステムを構築する要素にモジュール性を持たせることが多い。したがって、ある部分の機能を変更したり、新しく機能を追加したりすることが、集中型システムに比べより柔軟に行える。システムに新しい計算機を接続したりシステム自身を変更したりするのに、システム全体の再構築を行わずに機能を維持しつつ、システムとしての性能が向上するようでなければならない。こうしたシステムの規模によらない性質を規模適用性（スケーラビリティ）という。

2.4 分散 OS の設計目標

分散処理を実現する上でもっとも重要な概念がネットワーク透過性（network transparency）である。ネットワーク透過性とは、ネットワークの存在を意識しなくてもよい性質をいう。ユーザが物理的な分散をできる限り意識せずに、全体で一つのタイムシェアリング型の計算機システムのように利用できるようにすることが重要である。物理的な分散を隠しつつ、論理的には 1 台の計算機を形成すること、これが分散システムのもっとも基本的な機能である。こうした利用を可能にする ; ことによって、先に述べたような分散処理の利点 ; を有効に生かすことができ、またその目的を達成 ; することができる。 ; 2.4.1 ネットワーク透過性 ; ネットワーク透過性が包含する概念には次のよ ; うなものがある。 ; • 位置透過性 ; オブジェクトの存在する物理的位置が意識さ ; れない。オブジェクトに対するアクセスがそ ; の物理的位置とは独立に指定できること。ま ; た、ネットワーク内のどこからでもこうした ; アクセスが可能であること。 ; • 性能安定性 ; 負荷の変動によってシステム全体の性能が左 ; 右されない。 ; • 同時実行透過性 ; 複数の作業が並行して行われることをユーザ ; に意識されない。特にオブジェクトの共有に ; 関して、同時に実行される複数の処理の干渉 ; が意識されない。 ; • 障害透過性 ; ハードウェア、ソフトウェアの障害が意識さ ; れない。障害が発生した場合、（性能は若干低 ; 下しても）機能を維持できなくてはならない。 ; • 複製透過性 ; オブジェクトがネットワークに複製を持って ; いても分割されていても、それが利用者から ; 見て意識されない。 ; • 移送透過性 ; オブジェクトの移送が意識されない。移送の ; 過程にあって、ユーザもしくはアプリケーショ ; ンの処理に影響を与えてはならない。 ; • 規模透過性 ; システムやアプリケーションの規模の変更が、 ; システムの構成やアプリケーションのアルゴ ; リズムを変更せずに、またシステムの機能を ; 停止せずに可能であること。

これらの概念は、単にネットワークの存在を意識しないというネットワーク透過性よりかなり広い意味で捉えたものである。したがって、ネットワーク透過性というよりは分散透過性などと呼ぶ方がよいかもしれない。

そのほか、分散 OS を設計する上で重要と思われる要求として、次のようなものがあげられる。

• 自立性ネットワーク内の最小限の計算機で機能が維持できる。単体の計算機でも機能することが望ましい。

• 局所操作の効率分散機能の実装によって局所的な操作の性能が低下しない。分散 OS として運用しても、操作のほとんどは局所操作であると考えられる。

• 再構成の容易性システムを停止せずにまた効率的にシステムの構成が変えられる。

• セキュリティネットワークを介して通信を行う以上、セキュリティは重要な問題である。

• 異種システムへの対応種々の計算機、ネットワークに対応できるシステムはオープンでなくてはならない。

• 従来システムとの互換性 UNIX など従来の OS と互換性がある。

これらは、ネットワーク透過性あるいは分散透過性に関する要求と競合する場合もあろうが、現実的な要求として無視することができない。

2.5 まとめ 1

ここまでに述べたように、分散処理の目的は多岐にわたり、システムの応用次第でどれに重点をおくか、どういった機能を OS として支援するかが決まる。したがって分散 OS を定義する明確な基準があるわけではない。強いていうならば、「ユーザに資源の共有、高信頼化、負荷分散など分散処理を効果的に行う機能を提供するオペレーティングシステム」ということになろう。

3 分散システム

以下では、並列アプリケーションの実行を指向した分散システム、「コンピュータ・コロニー」をとりあげる。これは、各計算機を高速ネットワークで結合したハードウェアの上に、ソフトウェアとしてオペレーティングシステムを搭載した、総合的な環境である。

3.1 コンピュータ・コロニー

「コロニー」 (colony) とは、英語で「群体」を意味する単語である。「群体」とは生物用語で、複数の個体が結合して生活し、互いに協調してあたかも単一の個体のようにふるまうものをいう。

ここでは、複数の計算機が「群体」のごとく協調し、単一の高性能計算機として扱えるシステムを構築するための、「コンピュータ・コロニー」を説明する。その背景にある設計目標は、次のようなものである。

• 並列アプリケーションの実行高速なネットワークや並列実行を指向した実行環境を開発し、細粒度の並列実行を実現する。

• 計算機資源の有効利用ネットワーク上で負荷が偏るために一部の計算機がほとんど利用されない状態を回避し、負荷をネットワーク全体で平均的に分散させる。

• 位置透過性ユーザは要素マシンの位置や負荷の状況について意識する必要はなく、システム全体に対して仕事を投入すれば自動的に負荷を分散させる。

• マルチユーザ環境複数のユーザがシステムに処理能力の要求 (QoS:Quality of Service) を出し、できるだけそれに応じた処理能力をユーザが得られるよう、計算機資源を適切に分配する。

3.2 ネットワーク構成

並列アプリケーションの効率よい実行には、高速な通信が不可欠である。そこで、物理メモリ空間へのメモリアクセスで直接通信できるようにするため高速な通信を提供する共有メモリベースのネットワークとともに、そのための専用通信ボードを開発する必要がある。

コンピュータ・コロニーのハードウェア環境は、高速ネットワークで結合した計算機群で構成されるが、その構成単位としては、次のようなものがある。このしくみを図 1に示す。

• プロセッサプロセッサは、アクティビティに割り当てる計算機資源の最小単位である。タイムスライスにより複数のアクティビティに微少時間ずつプロセッサが割り当てられる。

• ノードノードは、一つの物理メモリを共有するプロセッサの集合である。ネットワーク上の一台の要素マシンがノードであり、この中に搭載されるプロセッサは単数でも複数でも構わない。ノードは他のノードとの通信を行うため、それぞれ専用通信ボードを装備している。すべてのノードにディスク、コンソール入出力、外部への汎用ネットワークを装備する必要はない。

• テリトリネットワークで結合されたノード集合の全体をテリトリという。ユーザは原則としてテリトリに対して仕事を投入し、ノードやプロセッサ単位の負荷分散は Colonia が自動的に行う。

コンピュータ・コロニーにおけるハードウェア環境は、端的に言えば計算機資源の集合体である。コンピュータ・コロニーを構成するノードについて、特定の機種や条件は規定しなくてもよく、命令セットの異なるプロセッサが混在したコンピュータ・コロニーも構築することができる。

3.3 共有メモリと通信ボード

従来のネットワークは I/O バスを通してプロセッサに接続されているため、アクセスのたびに I/O 図 1: コンピュータ・コロニーのネットワーク構成

を扱うシステムコールを発行してオペレーティングシステムに制御を移す必要があり、またネットワーク自体が高速でも、低速な I/O バスを通過しなければならないため、どうしても通信時のオーバヘッドが大きくなる。

これに対しコンピュータ・コロニーは、高速な通信を行うハードウェア環境として、 I/O やシステムコールを使わずにメモリアクセスのみで通信ができるインタフェースをユーザに提供し、共有メモリを実現する。このため、専用通信ボードをプロセッサバスに付加し、物理メモリ空間に対するアクセスを直接ネットワークに接続する。

3.4 オペレーティングシステム Colonia の概要

高速な通信を提供する、共有メモリベースのネットワークというハードウェアを最大限に活用するには、オペレーティングシステムによる支援が必要である。以下、ソフトウェア環境として、コンピュータ・コロニーを構成する要素となる、並列アプリケーションの実行を指向した分散オペレーティングシステム「Colonia」が持つ、主な設計上の特徴を示す。

3.4.1 通信

Colonia における通信のプリミティブとしては、共有メモリとシグナルの二つを提供する。通常のデータ通信には共有メモリを用いる。共有メモリを用いることで高速かつ安全な通信が実現でき、異機種間でも統一されたインタフェースで通信が行える。また、シグナルは非同期イベントを効率よく伝達するために用いられる。これらを組み合わせて利用することでメッセージ通信を実現することもできる。

3.4.2 ミッション・ユニットモデル

Colonia では、一つのプログラムに相当する実行単位として「ミッション」を用意し、一つのミッションを遂行するための細分化した並列実行の単位として「ユニット」を提供する。ユニットはそれぞれ独立した仮想メモリ空間を持つが、必要なコードやデータはミッション全体で共有し、全体で協調した動作をとることができる。もし、仮想メモリ空間がアクティビティごとに独立せずにすべて共有していると、アクティビティが別ノードに分かれている場合、メモリアクセスごとに通信を行わねばならない。しかし、ミッション・ユニットモデルでは必要な部分だけ共有して通信を行うが、ユニット内部での処理は通信を行わずに高速に実行できる。

3.4.3 マイクロカーネル方式

オペレーティングシステム Colonia は「マイクロカーネル方式」で構成される。この方式では、システムの機能の追加・拡張が、システムサーバを変更するだけで行える。また、ディスクや汎用ネットワークなどの有無に応じてシステムサーバを追加することでシステム構成を変更することができる。

3.4.4 テリトリ・スケジューリング

テリトリ全体を対象としたスケジューリングを実現する。ユーザがテリトリに対して投入した仕事を、その時点での各ノードの動的な負荷状況やノード間距離から判断して動的に負荷分散する。また、特定のノードにユニットが集中しているような場合は、他のノードにユニットを移送する。このとき、ユーザがミッションごとに要求する QoS をできるだけ満足できるような負荷分散を行う。例えば、リアルタイム性が要求されるマルチメディア対応のアプリケーションを実行するときは、アプリケーションにおける時間の流れに処理が追い付くような性能をシステムは提供する。

3.5 まとめ 2

後半では、並列アプリケーションを指向した共有メモリベースの分散システムとしてコンピュータ・コロニーを紹介し、さらにコンピュータ・コロニーを実現するためのソフトウェア環境である分散 OS Colonia について述べた。

Colonia はコンピュータ・コロニーのハードウェアが提供する高速・低遅延な通信を積極的に利用し、並列アプリケーションの効率的な実行や動的負荷分散による計算機資源の有効利用、マルチユーザへの適切な資源の配分を目指すものである。しかし、 Colonia が上に述べたような機能を持つ OS となるためには、まだ今後様々な分野での研究開発が行われなければならないであろう。

4 分散システムにおける高速通信 (5 月 29 日分)

分散システムの設計目標は、先に述べたように、

• 並列アプリケーションの実行高速なネットワークや並列実行を指向した実行環境を開発し、細粒度の並列実行を実現する。

• 計算機資源の有効利用ネットワーク上で負荷が偏るために一部の計算機がほとんど利用されない状態を回避し、負荷をネットワーク全体で平均的に分散させる。

• 位置透過性ユーザは要素マシンの位置や負荷の状況について意識する必要はなく、システム全体に対して仕事を投入すれば自動的に負荷を分散させる。

• マルチユーザ環境複数のユーザがシステムに処理能力の要求 (QoS:Quality of Service) を出し、できるだけそれに応じた処理能力をユーザが得られるよう、計算機資源を適切に分配する。

というようなものがあった。しかし、今日の分散システムでは、マシン間の通信レイテンシが非常に大きいため、上記のような設計目標を満たすことができない。よってここでは、分散システムを実現するために必要となってくる、要素マシン間の高速通信について述べる。

5 分散システムにおける通信

5.1 現在の分散システムにおける通信の遅さ

現在の分散システムにおける通信の遅さは、以下の理由による。

現在一般に利用されている分散システムでは、各マシンのネットワークインタフェースが低速な I/O バスに接続されている。このため、

• I/O バスがデータ転送のボトルネックになる。そのため、ネットワーク自体のデータ転送能力がどれだけ高くても、その性能が十分に利用できない。

• 資源の保護のため、通信時には必ず OS が介在することになる。そのため、データコピーやコンテキストスイッチングのオーバヘッドが生じる。

という大きな問題が生じることになる。

また、汎用のネットワークとして用いるために、通信プロトコルとして従来からの TCP/IP を採用する場合が多い。 OS が介在することによるデータコピーの他に、 TCP/IP を実現させるためのデータコピーも必要になり、そのオーバヘッドは無視できないものになっている。

これらの要因により、現在の分散システムでは通信のコストが非常に高くなり、ノード間の協調動作を大きく阻害している。

5.2 高速・低遅延な通信機構

上記の問題を解決するために、ハードウェアに支援された共有メモリベースの通信を取り上げる。共有メモリをベースとした通信では、 MMU(Memory Management Unit, メモリ保護ユニット) によるメモリ保護機構を利用することで、通信機構をユーザに対して安全に解放することができる。通信資源の保護は MMU によって達成されるため、通信機構が一度ユーザに開放されると、個々の通信に対しては OS の介在を必要とせず、高速・低遅延な通信が達成される。

以下では、このようなハードウェア環境の実現例として、共有メモリベースのワークステーションクラスタを示す。

5.2.1 共有メモリベースのワークステーションクラスタの構成

従来のマシン（ワークステーションおよびパーソナルコンピュータ）に高速・低遅延な通信を提供する専用のハードウェアを付加し、共有メモリベースのワークステーションクラスタを構成する。具体的には、クラスタを構成する各要素マシン（ノード）のプロセッサバスに通信ボードを接続する。要素マシンの大まかな構成を図 2 に示す。図 2: 要素マシンの構成 この通信ボードの基本的な機能は、ローカルマ シンの物理アドレスとリモートマシンの主記憶を 対応づけることである。すなわち、メモリアクセ ス命令発行時にプロセッサバスを流れる物理アド レスを拾い、必要に応じてリモートメモリアクセ スという形の通信を実現するものである。 ここで、ユーザプログラムにおけるメモリアク セスは、仮想アドレスに対して行われることに注 意する。そのため、プログラムから本通信ボードを 利用してリモートマシンとの通信を行うには、仮 想アドレスから物理アドレスへの対応付けと、物 理アドレスからリモートマシンの主記憶への対応 付けを、あらかじめ設定しておく必要がある。し かし、一度そのコネクションを確立しさえすれば、 後は通常のメモリアクセスによって他ノードと通 信を行うことができる。具体的には、次のような 手順となる。 1. ユーザは仮想アドレス空間にアクセスする。 2. MMU が仮想アドレスを物理アドレスに変換 し、プロセッサバス上に流す。 3. 通信ボードが物理アドレスを拾い、他ノード との通信の必要性を検知すると、実際の通信 処理を行う。 データおよびアドレスの流れを、図 3 に示す。 個々の通信には MMU による仮想アドレスから 物理アドレスへの変換が含まれており、これによ

図 3: データおよびアドレスの流れ

り通信ボードは通常の主記憶と同じ形で保護されている。保護の問題が MMU によって解決されるため、通信機構をマルチユーザに対して安全に解放することができる。その結果、ユーザは OS の介在しない高速・低遅延な通信を利用することが可能になる。

高速通信用の通信プロトコルも、従来との互換性を意識した TCP/IP ベースのものである必要はなく、またそれほど高機能である必要もない。なぜなら、高速ネットワークはローカルな環境内で閉じたものであり、外部との TCP/IP による通信は、 I/O バスを経由した従来ネットワーク上で提供すればよいからである。単純な通信プロトコルを採用することで、通信時のオーバヘッドをさらに軽減することが可能となる。

5.2.2 ネットワークアドレス

共有メモリベースのワークステーションクラスタを実現するための通信ボードは、プロセッサバスを流れる物理アドレスを拾い、必要に応じてリモートメモリアクセスを行うものである。このリモートメモリアクセスを実行する際、通信ボードは相手ノードの通信ボードに対してネットワークアドレスを使ってアクセス要求を送る。そして、それを受けた通信ボードで、ネットワークアドレスから物理アドレスへの変換を行う。

ネットワークアドレスという中間形式にいったん変換することで、ノード内における物理アドレスの変更を他ノードに対して隠蔽することが可能になり、その結果、ノードの独立性が高まり、柔軟なシステム構築が可能になる。

参考文献

[1] 前川守, 所真理雄, 清水謙多郎：分散オペレーティング・システム− UNIX の次にくるもの, 共立出版 (1991).

[2] 青木秀貴：並列アプリケーションを指向した分散オペレーティングシステム Colonia, 特別研究報告書, 京都大学工学部情報工学科 (1997).

[3] 山添博史：分散オペレーティングシステム Colonia の共有メモリ管理とそのエミュレータ, 特別研究報告書, 京都大学工学部情報工学科 (1997).