マイクロプロセッサ技術の急速な発展に伴って、コンピュータシステムはますます多くの分野に利用されるようになってきている。実世界に利用されるシステムに対しては何らかのリアルタイム性が要求される場合が多く、リアルタイムコンピューティング技術の重要性は急速に高まってきている。大規模・高性能なリアルタイムシステムに対する要求も高く、それに対する有力なアプローチとして、マルチプロセッサシステム、とりわけ機能分散マルチプロセッサの採用が挙げられる。

　マルチプロセッサ上に構築されたリアルタイムシステムの保守コストを低減するためには、システムの一部の変更やプロセッサの追加によって、変更が加えられなかった部分の最悪時の振る舞いの変化が最小限になることが望ましい。この性質を我々はスケーラビリティと呼ぶ。理想的には、あるプロセッサ上で実行される各ルーチンの最大実行時間が、システム内のプロセッサの数や他のプロセッサの動作に関わらず、一定の上限を持つことが望ましい。ところが、共有資源を排他的にアクセスするルーチンの最大実行時間が、競合するプロセッサ数の増加に応じて長くなることは避けられない。

　機能分散マルチプロセッサ上にリアルタイムシステムを構築する場合に、外部機器やそれを処理するタスクは、プロセッサ間の同期・通信が最小限となること、厳しい時間制約を持つ処理ができる限り1つのプロセッサ内で完結して実行できることの2つの性質を満たすように、各プロセッサに割り付けられる。そのため、プロセッサ内で閉じて行うことができる処理の最悪時の振る舞いが、システム内の他のプロセッサの動作やプロセッサ数に依存せずに決まることは、大きなメリットとなる。

　この論文では、既存の共有メモリマルチプロセッサシステム上のスケーラブルなアプリケーションの構築を支援するリアルタイムカーネルの実現を目標として、仕様・実現方法の両面から議論する。スケーラブルなアプリケーションシステムを可能にするためには、リアルタイムカーネルそれ自身がスケーラブルでなくてはならない。共有メモリマルチプロセッサで動作するリアルタイムカーネルに関しては、盛んに研究が行われているにも関わらず、最悪時の振る舞いのスケーラビリティに着目した研究はこれまで行われてこなかった。

　我々は最初に、機能分散マルチプロセッサ上のスケーラブルなリアルタイムカーネルに求められる性質を、4つの要件にまとめる。次に、共有メモリマルチプロセッサ上にリアルタイムカーネルを実現するためのアプローチについて議論し、4つの要件を満たすために障害になる点を指摘する。具体的には、障害になる点として、プロセッサ内で閉じた処理の最大実行時間がシステム内のプロセッサ数に依存してしまうという問題と、予測可能なプロセッサ間同期とシステム内のプロセッサ数に依存しない割り込み応答性が両立しないという問題を指摘する。次に我々は、セマフォやイベントフラグなどのタスク独立な同期・通信オブジェクトを持たないカーネルモデルにおいて、この問題を解決するための実現方法を提案する。提案する方法を用いることにより、4つの要件をすべて満たすことができ、カーネルの各サービスの最大実行時間・最大レスポンス時間が満足できる上限値を持つ。これらの議論の中では、カーネルの下位レイヤとなるプロセッサ間同期プリミティブおよびハードウェアが、必要な性質を満たしていることが前提となる。

　また我々は、プロセッサ内に閉じた処理の性能を向上させるために、カーネル資源を、異なった性質を持ついくつかのクラスに分類するアプローチを提案する。例えば、あるプロセッサのプライベートクラスに属するタスクは、その最大実行時間が競合するプロセッサ数に依存しないという性質を満たすが、他のプロセッサと直接同期・通信を行うことができないという制限を持つ。

　次に、これらの提案の有効性を、既存のマルチプロセッサシステムを用いた性能評価によって検証する。我々の評価環境は、プロセッサ間同期プリミティブおよびハードウェアに対する仮定を完全に満たしてはいないが、スケーラブルなリアルタイムカーネルに求められる4つの要件が、我々の提案する方法によって現実的にはすべて満たされることが確認できた。それに対して他の方法では、4つの要件のすべてを同時に満たすことはできない。

　この論文の後半では、機能分散マルチプロセッサシステムのためのスケーラブルなリアルタイムカーネルに用いるためのスピンロックアルゴリズムについて議論する。上で述べたスケーラブルなリアルタイムカーネルの実現に必要となるプロセッサ間同期プリミティブとして、中断可能なキューイングスピンロックアルゴリズムと優先権付スピンロックアルゴリズムを提案する。また我々は、ロックがネストする状況におけるスケーラビリティの問題について議論し、ネストしたスピンロックをスケーラブルに実現する方法を提案する。さらに、そこで必要となるアルゴリズムとして、優先度継承スピンロックを提案する。また、これらのアルゴリズム単体の有効性を、性能評価によって検証する。

　本論文は、大きく分けて4つのパートと付録からなる。パート1は序論であり、本論文の主題である機能分散マルチプロセッサのためのリアルタイムカーネルのスケーラビリティについて、用語の定義や現状を概説し、その問題点について述べている。

　マルチプロセッサ上に構築されたリアルタイムシステムの保守コストを低減するためには、システムの一部の変更やプロセッサの追加によって、変更されなかった部分の最悪時の振舞の変化が最小限になることが望ましい。この性質を本論文ではスケーラビリティと呼んでいる。理想的には、各処理の最大実行時間が、システム内のプロセッサの数や他のプロセッサの動作に依存しないことが望ましい。ところが、共有資源を排他的にアクセスする場合には、最大実行時間が競合するプロセッサの数に応じて長くなることは避けられないという本質的な限界がある。

　本論文は、この点を踏まえ、既存の共有メモリマルチプロセッサシステム上でスケーラビリティを持ったリアルタイムカーネルを実現する機構を、仕様・実装方法の両面から明らかにすることを目的としている。特に、機能分散マルチプロセッサにおいては、プロセッサ内で閉じた処理の最悪時の振舞がシステム内の他のプロセッサの動作やプロセッサ数に依存しないことが大きなメリットとなることに着目し、プロセッサ内の同期とプロセッサ間の同期を分けて考えている点に新規性がある。

　パート2は、機能分散マルチプロセッサ上のスケーラブルなリアルタイムカーネルの実現機構について議論しており、8つの章からなる。第1章で本論文の背景となるリアルタイムカーネル仕様ITRONについて概説した後、第2章では、機能分散マルチプロセッサ上のリアルタイムカーネルの基本的なモデルを提示し、その2種類の実装アプローチの適否について議論している。

　第3章は、スケーラブルなリアルタイムカーネルに求められる性質を4つの要件にまとめ、それらの要件を満たすために障害になる点を指摘している。具体的に障害となる点として、プロセッサ内に閉じた処理の最大実行時間がプロセッサ数に依存してしまう問題と、予測可能なプロセッサ間同期とプロセッサ数に依存しない割込応答性が両立しない問題を指摘している。第4章は、タスク独立な同期・通信オブジェクトを持たないカーネルモデルにおいて、これらの問題を解決するための方法を提案している。提案された方法を用いることで、第3章に述べられた4つの要件をすべて満たすことができ、カーネルの各サービスの最大実行時間/最大応答時間が満足できる上限値を持つことが示される。また、その前提となる条件についても述べてられている。

　第5章は、プロセッサ内に閉じた処理の性能を向上させるために、カーネル資源を異なる性質を持ついくつかのクラスに分類するアプローチを提案している。例えば、あるプロセッサのプライベートクラスに属するタスクは、その最大実行時間がプロセッサ数に依存しないという性質を満たすが、他のプロセッサと直接同期・通信を行うことができないという制限を持つ。

　第6章は、ここまでの提案の有効性を、既存のマルチプロセッサシステムを用いた性能評価によって検証している。性能評価の結果、第3章に述べられた4つの要件が提案された方法によって現実的にはすべて満たされること、他の方法ではすべての要件を同時に満たすことはできないことが確認されている。第7章は、4つの要件を満たしながらタスク独立な同期・通信オブジェクトをサポートすることの困難性について議論し、第8章では、パート2の結論を述べている。

　以上パート2では、マルチプロセッサ上にリアルタイムシステムを構築する場合の本質的な限界点から出発し、機能分散マルチプロセッサシステムにおいて、その限界条件ぎりぎりの性能を持つリアルタイムカーネルの実現手法を明らかにしたもので、問題設定・解決アプローチの両面に新規性がみられる。またこの成果は、従来極めて保守的な方法しかなかったマルチプロセッサ上のハードリアルタイムシステムの設計手法に、より柔軟な設計手法の導入の可能性を大きく広げるもので、実用的な観点からも高い価値がある。

　パート3は、機能分散マルチプロセッサシステムのためのスケーラブルなリアルタイムカーネルの実現に用いるためのスピンロックアルゴリズムについて議論しており、6つの章からなる。最初に第1章では、スピンロックアルゴリズムに関する研究動向をサーベイしている。第2章および第3章では、それぞれパート2で提案された方法の実現に必要となる中断可能なキューイングスピンロック(2種類)および優先権付スピンロックの具体的なアルゴリズムを提案し、それらの有効性を実機を用いた性能評価によって検証している。第4章は、ロックがネストする状況におけるスケーラビリティの問題について議論し、ネストしたスピンロックをスケーラブルに実現する方法を提案している。第5章は、提案した方法を採用した場合に、ロックが3段以上ネストする状況で必要となる優先度継承スピンロックアルゴリズムを提案している。第6章では、パート3の結論をまとめ、スピンロックアルゴリズムに関する将来の課題について論じている。

　以上よりこのパートでは、スケーラブルなリアルタイムシステムの構築に必要となる種々のスピンロックアルゴリズムを新たに提案し、その有効性の検証を行っている。特に第4章で提案されている方法は、非常に基本的な問題でありながら従来取り組まれていなかったもので、それに対して明解な解法を与えたことは高い評価に値する。

　パート4では、本論文全体の結論をまとめて述べ、将来の課題について論じている。付録においては、本論文で評価に用いたマルチプロセッサ用のリアルタイムカーネルの実装の詳細の紹介と、パート3の第2章において提案したアルゴリズムの正当性の証明を掲載している。

　共有メモリマルチプロセッサで動作するリアルタイムカーネルに関しては、盛んに研究が行われているにも関わらず、最悪時の振る舞いのスケーラビリティに着目した研究はこれまで行われてこなかった。本論文は、マルチプロセッサリアルタイムシステムにおけるスケーラビリティという新たな研究目標を設定し、リアルタイムカーネルという分野においてその実現手法を明らかにしたいう点において、今後の関連分野の研究に寄与するところが大であると認められる。

　なお、本論文の内容は、一部を除いて坂村健氏との共著論文として印刷公表済みであるが、論文提出者が主体となって開発、分析および検証を行ったもので、論文提出者の寄与は十分であると判断する。よって本審査委員会は、論文提出者高田広章に、博士(理学)の学位を授与できると認める。