マルチプログラミングをサポートするマルチプロセッサ上では、並列アプリケーションの実行要素であるスレフドをどのように管理するかが、システムの性能に大きな影響を与える。特に、スレッド管理の設計、実現上もっとも重要な課題は、スレッド管理コストを決定する3種類のスレッド切り替え(ユーザタスク内のコンテクストスイッチ、カーネル内のコンテクストスイッチ、及びユーザタスクとカーネルの間のドメインスイッチ)の頻度および個々のオーバーヘッドを低く抑えることである。

　マルチプログラミングを導入した汎用並列システムにおいては、しかし、システムソフトウェアの忰組みに対する再考察を必要とする困難な問題であった。その理由は、変化を続けるプロセッサ需要に対応しつつ、複数のアドレス空間(またはタスク)の間でプロセッサ資源を公平に分配する必要があるため、また、各ユーザプログラムで必要となるさまざまなスレッドスケジューリングポリシーに対応する必要があるためである。

　これまでもスレッド切り替えを低減する目的で、さまざまなスレッド管埋システムが提案、実現されてきた。これらのシステムの性能上の目標は、ユーザのアプリケーションが、その実行中にスレッド操作列(典型的には生成、削除、停止、再開、同期、通信からなる)を発生させた場合に、これをできるだけ少ないスレッド切り替えによって実現すること、すなわち「最適なスレッド切り替え動作」の実現である。

　しかし、従来のどのスレッド管理システムでも、最適なスレッド切り替え動作が実現されたものはなかった。この理由は、以下の4つにまとめられる。(1)Avoidable synchrony:ユーザとカーネルとの間で不必要な同期が起こる。代表例としては、ユーザが、システムコールによりカーネルスレッド(カーネルがプロセッサを多重化して実現するスレッド)の生成や停止、再開を要求することがある。これらはシステムコールインターフェイスを変更すれば取り除くことができる。(2)Harmful transparency:カーネルがシステムをアプリケーションの必要以上に仮想化することによるオーバーヘッドがある。代表例としては、無限の数のカーネルスレッドを実現することによる、カーネルレベルのスレッド管理コストの増大があげられる。(3)Mismatch of scheduling semantics:カーネルの提供するスケジューリングポリシーが、ユーザレベルで必要とするスケジューリングポリシーと必ずしも一致しない。(4)Uncontrolled timing of scheduling:カーネルによるスケジューリングが、ユーザレベルからは予測不能かつ制御不能である。このため、スピンロックなどの、プロセッサの割り当て戦略と結びついたプログラミング技法が有効に働かない。

　本論文は、既存のスレッド管理機構のこれらの欠点を克服した、新しいスレッド管理機構の枠組みを提案する。この枠組みでは、共有メモリ型マルチプロセッサにおいて、オペレーティングシステムカーネルがユーザレベルのスレッド管理機構の存在を仮定し、2つのレイヤが非同期的な協調動作を行なうことを基本としている。

　非同期的なカーネルとユーザレベルの協調動作を基本としたこのスレッド管理の枠組みにより、ユーザレベルのスケジューリングポリシーの変化、システムの負荷の変化、アプリケーションの通信同期パターンにかかわらずスレッド管理回数を低く抑えることができる。特に、ノンプレエンプティブスケジューリング、プレエンプティブスケジューリング、プライオリティつきスケジューリングの3つの代表的なスケジューリングポリシーをとった場合、本枠組みに基づくスレッド管理機構は、最適なスレッド切り替え動作を実現する。

　提案するスレッド管理の枠組みでは、カーネルとユーザレベルとの間の協調動作を、以下の3つのアブストラクションによって行なう。

　Unstableカーネルスレッドカーネルはユーザレベルの要求とは直接関係なくカーネルスレッドを生成、停止、再開、終了する。このためカーネルが、各ユーザタスクが使用するカーネルスレッド数を決定できる。これにより、harmful transparencyの問題を解決する。

　共有メモリ領域ユーザは、どのカーネルスレッドにプロセッサが割り当てられているかを知ることができる。Uostableカーネルスレッドは、任意に長い時間スケジュールされなかったり、場合によってはカーネルによって強制的に終了させられることがあるが、このようなカーネルスレッドの動作をユーザレベルで把握し、制御するためにシステムが定義した共有メモリ領域を用いる。これによりavoidable synchronyおよびuncontrolled timing of schedulingの問題を解決する。

　Notifierカーネルスレッド カーネルで発生するイベントで、ユーザが特に指定したものに関しては、アップコールにより同期的に通知する。これをnotifierカーネルスレッドと呼ぶ。このインターフェイスにより、mismatch of scheduling semanticsを解決する。

　本研究の貢献は、以下の3点である。(1)非同期的なカーネルとユーザレベルの協調動作の導入により、マルチプログラミングされた共有メモリマルチプロセッサ上の代表的なスレッドスケジューリングポリシー下で、最適なスレッド切り替え動作を行なうスレッド管理機構を実現する方法を確立した点、(2)設計した3つのアブストラクションを実現、動作させることにより、提案する枠組みが実際に使用可能であることを明らかにした点、そして、(3)実現したスレッド管理機構およびシミュレーションによる性能比較により、提案する枠組みに基づくスレッド管理機構が、既存のスレッド管理機構よりも優れた性能をもつことを確認した点である。

　本論文は7つの章からなる。第1章は序論であり、今日の並列計算機上の汎用オペレーティングシステムの果たすべき機能と課題について概説している。特に本論文の主題であるマルチスレッドの管理に関して、その重要性と、既存のシステムが持つ問題点を明らかにしている。スレッド管理の設計、実現上もっとも重要な課題は、スレッド管理コストを決定する3種類のスレッド切り替え(ユーザタスク内のコンテクストスイッチ、カーネル内のコンテクストスイッチ、及びユーザタスクとカーネルの間のドメインスイッチ)の頻度および個々のオーバーヘッドを低く抑えることである。

　本研究ではこの点をふまえ、研究目標を「最適なスレッド切り替え動作」の実現に設定した。最適なスレッド切り替え動作とは、ユーザのアプリケーションがスレッド操作列(典型的には生成、削除、停止、再開、同期、通信からなる)を発生させた場合に、これをできるだけ少ないスレッド切り替えによって実現することである。

　第2章は、現在にいたるスレッド管理に関する研究の包括的な概説である。これまでに提案されたスレッド管理システムの実行時動作を、オペレーティングシステムとユーザプログラムとの間の実行時の協調動作の違いに着目して分析している。

　第3章は、本論文で提案するスレッド管理の枠組みの中心となる3つの概念を提案している。本提案では、オペレーティングシステムとユーザプログラムとが、非同期的な協調動作を行なう点がもっとも特徴的である。この協調動作を以下の3つのアブストラクションを通じて行なう。(1)Unstableカーネルスレッド:カーネルはユーザレベルの要求とは直接関係なくスレッドを生成、停止、再開、終了する。(2)共有メモリ領域:ユーザプログラムはこの領域を通じて、どのスレッドが動作中かを知ることができる。(3)Notifierカーネルスレッド:カーネルで発生するイベントで、ユーザが特に指定したものに関しては、アップコールにより同期的に通知する。

　第4章は、第3章で提案したスレッド管埋の枠組みの3つの概念の実現方法の詳細を明らかにしている。オペレーティングシステムが、ユーザプログラムと非同期にスレッドの管理を行なう際に特に問題となる、スレッドの生成と消去、スタックの割り当てと解放、ページフォールトの処理などについて、実マシン上での実装に基づく詳細が明らかにされている。

　第5章は、第3章で提案したスレッド管理の枠組みの実行時動作を解析した章である。オペレーティングシステムのスレッドスケジューリングと、ユーザレベルのスレッドスケジューリングのそれぞれについて、提案した枠組みに基づくシステムが最適なスレッド切り替え動作を実現していることを示している。

　第6章は、第3、4、5章の議論をふまえ、提案したスレッド管理の枠組みに基づくシステムの性能を、既存のスレッド管理システムと比較している。ここでは数値計算を中心とする複数のプログラムと、複数のスレッドスケジューリング法を用いて、さまざまなワークロードに対する提案方式および既存の方式3つの実行時性能の比較を行なっている。結果として、提案方式が安定して既存の方式を上回る性能をみせ、多くの場合に有意な性能向上がみられることが明らかになっている。

　第7章は、論文全体の内容をまとめ、今後の研究課題について論じている。特に、本論文の成果が、多様な並列マシンアーキテクチャに広く適用可能であること、また、今後考えられるプロセッサ技術の変化に対しても良い性質を示すことが議論されている。

　以上を要するに、本論文は、汎用並列オペレーティングシステムにおいて複数のプロセッサを効率良く管理する機構であるスレッド管理機構の新たな構成法を提案したものであり、特にオペレーティングシステムとユーザプログラムとの協調動作を基礎として、並列ソフトウェアシステム全体の動作を再構成した点で、今後の関連分野の研究に寄与するところ大であると認められる。

　なお、本論文の内容は共著論文として印刷公表済みないし公表予定であるが、論文提出者が主体となって分析および検証を行なったもので、論文提出者の寄与は十分であると判断する。よって、本審査委員会は、論文提出者猪原茂和は博士(理学)の学位を授与できると認める。