ネットワーク上には多数の計算機が存在しているが,その全てが常時使われているわけではない.不使用のまま放置されてい計算資源が大量にあると言える.本研究では,この大量にあるアイドル状態計算資源を有効に利用するシステムとして"BGタスクスペース"を提案する.

　提案手法では,ユーザが席を立つなどで計算機が不使用状態になるとシステムからタスクが投入され,ユーザが使っていない間はそのタスクを処理し続ける.ユーザが席に戻り作業を再開する際には,そのタスクはユーザの作業の妨げとなるので速やかにその計算機から移送される(図1参照).また,提案システムの概要は図2のようになり,各計算機のプロセスで協調してタスク実行環境を構築する.

　本研究で下記の分散環境を想定している.(1)使用する計算資源群はヘテロジーニアスである,(2)計算機群そのものを管理しておらず計算機にはプロセスを立ち上げるのみである,(3)システムの環境が動的である,(4)構成する資源群は信頼性が低い.提案システムは様々なユーザから空いている計算資源を提供されるため計算機群がヘテロジーニアスになることは避けられない.不使用資源を提供してもらうためにユーザに特定のOSなどの使用を強要するのは現実的ではないと考え各ユーザにはプロセスを1個立ち上げることのみ要求することとした.ユーザは頻繁に計算機の使用/不使用を切り替えるためシステム環境は動的であり同時に信頼性が低いものとなる.また,上記の環境において特に下記の4項目の実現を目指している.(1)"BGタスク"(後述)が"FGタスク"(後述)の作業を可能な限り妨げない,(2)協調システムの一部に障害が発生してもシステム全体がダウンしない高い耐障害性がある,(3)協調システムにユーザ認証機構があり認証ユーザレベルでの資源割り当てが可能である,(4)動的な環境における適切な資源割当が可能である.ここで,"FGタスク"とは各ユーザが本来その計算機で行う対話的なタスク(ワードプロセッサやブラウザなど)のことであり,"BGタスク"とは計算機不使用時にシステムから投入されるバッチ型のタスク(シミュレーションや数値計算など)のことである.すなわち,提案システムはユーザが席を離れるなどで"FGタスク"の処理が行われていない時に"BGタスク"を処理するシステムであると言える.ユーザがアイドル状態計算資源を提供するためにユーザ本来の"FGタスク"が妨げられてはならないと考え,"FGタスク"を妨げないことを最重要課題とした.使用計算機群は信頼性が低いことが予想されるので耐障害性も重要課題とした.さらにタスクスケジューリングも重要と考え,動的な環境に対応したスケジューリングや公平資源割当スケジューリングの実現も重要課題とした.ただし,これら2目標はともにスケジューリングであり必ずしも両立しない.

　想定環境はユーザの動作に依存するため非常に不安定なものとしたが,Watch Dog TimerやTokenの導入によりシステム内の一部の計算機が障害を起こしてもシステム全体ダウンしたり投入されたタスクが失われないなどを実現した.

　スケジューリングとしては効率のよい(スループットの高い)スケジューリングや公平なスケジューリングなどが望まれるが,効率の良いスケジューリング(公平性は無視)として負荷分散型スケジューリング,公平なスケジューリングとしてシステム制御型と市場経済モデル型を提案し実装した.具体的には,効率の高いスケジューリングとして下記のような機能を実装し,負荷分散を実現した.まず,定期的に各スペースは自スペースの負荷状態を計測する.各スペースは定期的に自スペースの負荷情報を他スペースに通知しする.これによりスペース内の負荷状況を把握しタスクをより負荷の低いスペースに移送する(スケーラビリティ,タスク移送に関しては後述).1000個のタスクを1台の計算機に投入した結果,4分程度で全ての計算機(9台)の負荷が均等化された.また,各計算機の能力が異なる状況でも計算機の能力を考慮することにより負荷を適切に分散することが可能であることが確認され低能力の計算機でもその能力を考慮することによりシステム全体のスループットの向上に貢献できることが確認された(PentiumIII 1GHz程度の計算機群に486 66MHzの計算機を追加し実験).また,応用例としてパスワード解析プログラムを作成し提案システム上で処理させその実用性を確認した.

　次に,システム制御型の公平なスケジューリングであるが,ユーザをアカウントで管理し,各アカウントごとの消費資源量を監視し制御することにより各ユーザアカウントごとの消費資源量を等しくすることを実現した.実環境(各タスクの大きさが異なり計算量比1,5,10のタスクが等確率で発生.計算機7台,アカウント数100の環境で実際にネットワーク越しにタスクを投入し処理させ測定)において,消費資源量(CPU)の標準偏差10%程度の公平性を実現した.大規模システムへの対応としては,計算機200台での環境を理想的な環境(各タスクの計算量と計算機能力が完全に評価できる環境)を想定しシミュレーションした結果,消費資源の偏りは,物理的近隣への接続方式(計算機が2次元平面上に配置されているとし距離が一定以内の計算機と論理的に接続をし,接続がされている計算機のみを管理し公平化を図る)において標準偏差10%以下を実現し,ランダム接続方式(ランダムに計算機同士の論理リンクを確立し,管理単位ごとの偏りを軽減する)においては標準偏差4%以下を実現させた.これにより,システム全体の把握が不可能な大規模システムにおいても接続されている計算機のみを管理することにより各ユーザの消費資源量を公平とすることが実現されたと言える.

　最後に,市場経済モデル資源融通システムでは資源消費ユーザが資源提供ユーザに代価を払い資源を購入することにより資源を消費しタスクを処理する.この方式では各資源提供者エージェントおよび各資源消費者エージェントが資源販売および資源購入を各エージェントの戦略により行う.これにより各ユーザは自分の消費権以内で自分の嗜好に応じた資源消費を自由に行えるようになり,様々な嗜好を持つユーザが同一システム内で資源を消費や提供を行える.資源の割り当ては各ユーザの戦略に依存するが,提案システムの実装では提供者エージェントが強い(資源提供による利益が高い)ほど価格は安定し,結果としてシステムが安定となり消費者の利益となることが確認された.すなわち,ユーザが利益を求めるほどシステムは安定すると言える.また,提案システムの実装の経済システムとしての健全性を評価したところ,均衡価格は経済学における需要と供給が一致する価格(需要曲線と供給曲線の交点)とほぼ一致し(5%程度のずれ),実装システムの経済システムとしての健全性も確認された.

　提案システムはJava言語で実装されているが,タスクの移送は以下の方法で実現されている.Java言語ではJava言語ソースコードをコンパイルしJava Byte Codeと呼ばれる中間言語で記述されたファイルを作成し,そのByte Codeを各プラットフォームのインタプリタで実行する.提案システムではJavaコンパイラで作成された通常(移送不可能)のByte Codeファイルを移送可能なByte Codeファイルに変換することによりタスク移送を実現している.具体的には,Byte Codeのメソッドコールをフックしプログラム実行コンテンツ(StackやPC)を獲得できる命令を挿入する.この方法の利点としては,拡張VMを使わないためタスクのポータビリティーが失われない,言語拡張を行う必要がなく従来のJava言語と高い親和性を持つことがあげられる.

　既存の研究としては,まずCONDORがあげられる.これは各計算機Nativeのタスクを用いるため高機能な負荷分散やタスク移送(ファイルなどのリソースの管理など)が実現されているが,提案システムのような高いタスクの移送性は実現されていない.市場経済モデルに基づくアイドル状態計算資源融通システムとしてPOPCORNがあげられるがこれは細かいサブタスク("computelet"と呼ぶ)に分割できる特殊なタスクのみを対象としているが,提案システムはタスクの移送が可能であり汎用的なタスク実行プラットフォームを実現したと言える.

　本研究では,アイドル状態計算資源融通システムとして"BGタスクスペース"を提案し実装した.提案システムを用いることにより,自分の本来の作業に支障をきたすことなしに他人のアイドル状態計算資源を用いてタスクを処理させることが可能となった.また,タスク移送により"FGタスク"を妨げないことが,トークンやWatch Dog Timerにより耐障害性が,前述のスケジューリングにより動的な環境な対応したスケジューリングや公平なスケジューリングが実現されたと言える.

図1:提案システムの概要(各計算機の動作)

図2:提案システムの構造

　本論文は「アイドル状態計算資源融通システムに関する研究」と題し、多数のコンピュータがインターネットに常時接続されている環境において、持ち主が使用中でないコンピュータの計算能力を有効利用する方式につき検討を行ったものであり、11章から構成されている。

　第1章は「はじめに」であり、本論文の位置づけならびに構成について述べている。

　第2章「研究背景」では、本論文で想定している環境として、異なる機種のコンピュータが混在していること、それらのコンピュータの間をつなぐネットワークの信頼性は必ずしも高くないことを述べた後、本研究の目標として、コンピュータの持ち主が行う対話型のタスクを妨げないこと、耐障害性、ユーザ認証ならびにユーザ間での公平な資源割り当てなどを挙げている。また、既存の研究を紹介し、それらとの比較を行っている。

　第3章「アイドル状態計算資源融通システムBGTSの提案」は、第2章で述べた目的を達成するためのシステムの基本的な枠組みとして、バックグラウンドタスクスペース(BGTS)を提案している。コンピュータの持ち主が対話型のタスク(フォアグラウンドタスク)を再開した時にはバックグラウンドタスクを他のコンピュータに移送すること、耐障害性を実現するためウォッチドッグタイマやトークンパッシングを用いることなどが述べられている。

　第4章はBGTSの実装方法の紹介であり、Javaで記述されたバックグラウンドタスクをコンパイルして得られるバイトコードを解析して、コンピュータ間を移送するための命令群を挿入することにより、Java言語仕様やJava実行環境に変更を加えることなく実装することが可能であり、ポータビリティに優れていることが述べられている。

　第5章から第9章にかけては、BGTSにおけるスケジューリング手法に関して、3通りの手法をとりあげて、比較検討を行っている。

　まず第5章においては、システム側で可能な限り負荷の平準化を行う手法を実装し、動的タスク移送が性能向上に有効であること、コンピュータの性能差をスケジューリングに反映させることで、能力の低いコンピュータを有効活用することができることを示している。

　第6章では、ユーザ間での公平な資源分配を行うための簡便な手法として、メタサーバを用いる方式を実装し、ユーザ数がBGTS数の7倍程度までであればユーザ間の資源使用量のばらつきを5%以内に抑えることができることを示している。

　続いて第7章では、第6章で述べた方式のスケーラビリティを向上させるため、ユーザとBGTSの間の接続関係のランダム性が高ければ、各BGTSが直接接続しているユーザ間に対して公平に資源分配を行うことで、システム全体としても公平な資源分配を行うことができることを示している。

　第8章では、市場原理を用いて資源分配を行う方式を提案している。資源提供者および資源利用者がエージェントを通じて自分の嗜好に沿った売買を行うことで、公平性を実現することを目指している。

　続く第9章では、実際にエージェントに簡単な売買戦略を実装した結果について述べており、市場価格と理論値のずれは5%以内であり、提示価格の安定性の高い資源提供者の方が得る富が大きいなど、好ましい性質が示されている。

　第10章「考察」では、これら3通りのスケジューリング手法の比較、提案システムのスケーラビリティなどに関して議論を行っている。

　第11章「おわりに」では、本論文の成果ならびに残された課題を整理している。

　以上のように、本論文は、インターネット上に接続されている多数のコンピュータの計算能力を、持ち主の対話型タスクを邪魔することなく有効利用する方式について、基本的原理、スケジューリング方式などを提案した上、実装を通じてその有効性を示したものであって、電子情報工学に貢献するところ少なくない。

　よって本論文は博士(工学)の学位請求論文として合格と認められる。