(57)【要約】【課題】通信コストを削減したタスク割当または資源割当を行う。【解決手段】メッセージの負荷量が自身の負荷量よりも小さければ、取り出した負荷量に書き換え、添えられていた識別情報も記録する。同様に、受信した優先度の方が自身の優先度よりも高ければ、受信した優先度に書き換え、添えられていた識別情報も記録する。メッセージの負荷量および優先度が共に自身のものでなければ、その割当処理は終了する。また、負荷量および優先度が共に自身のものならば、記録されている優先度のタスクまたは資源割当要求を自身に割り当てる。タスクの優先度が自身のものならば、そのタスクが記録されている負荷量最小のサーバへタスクを送り、割当処理を終了する。未割当タスクがまだ残っていたら再度起動する。【選択図】  図２
2004348549.tif 000002
【特許請求の範囲】
【請求項１】
ｎ台のサーバにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返すタスク割当方法であって、
自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が自サーバの負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割当てるステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了するステップと、
これらのステップを未割当タスクがなくなるまで繰り返すステップと
を実行することを特徴とするタスク割当方法。
【請求項２】
ｎ台のサーバにより仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す資源割当方法であって、
自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記自サーバの資源割当要求の優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が自サーバの待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割当てるステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了するステップと、
これらのステップを未割当資源がなくなるまで繰り返すステップと
を実行することを特徴とする資源割当方法。
【請求項３】
ｎ台のサーバにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返す分散システムに適用され、前記サーバに設けられたタスク割当装置であって、
自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が前記記録した負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割当てる手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する手段と
を備えたことを特徴とするタスク割当装置。
【請求項４】
ｎ台のサーバにより仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す分散システムに適用され、前記サーバに設けられた資源割当装置であって、
自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が前記記録した待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した待ち時間と共に保存されている識別情報に相当するサーバへ送信するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割当てる手段と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する手段と
を備えたことを特徴とする資源割当装置。
【請求項５】
請求項３記載のタスク割当装置を備えたサーバが単方向仮想的に論理リングを構成して接続されたことを特徴とする分散システム。
【請求項６】
請求項４記載の資源割当装置を備えたサーバが仮想的に単方向論理リングを構成して接続されたことを特徴とする分散システム。
【請求項７】
ｎ台のサーバにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返す分散システムに適用され、前記サーバに設けられたタスク割当装置に適用されるプログラムであって、
情報処理装置にインストールすることにより、その情報処理装置に、
自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が前記記録した負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割当てる機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する機能と
を実現させることを特徴とするプログラム。
【請求項８】
ｎ台のサーバによりから仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す分散システムに適用され、前記サーバに設けられた資源割当装置に適用されるプログラムであって、
情報処理装置にインストールすることにより、その情報処理装置に、
自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が前記記録した待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した待ち時間と共に保存されている識別情報に相当するサーバへ送信する機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割当てる機能と、
メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する機能と
を実現させることを特徴とするプログラム。
【請求項９】
請求項７または８記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、分散システムにおけるタスク割当および資源割当に関する。なお、並列システムは分散システムの一種であるため、本発明は並列システムでも分散システムでも使えるが、それぞれのシステムにおいては用語が異なるため、以下では並列システムにおけるプロセッサ、ＣＰＵ、分散システムにおけるエージェント、プロセス、計算機、サーバ等の用語を一括してサーバと呼ぶ。なお、厳密にはサーバとプロセスまたはプロセッサは異なるが、本発明の範囲では区別の必要がないためサーバと呼んで差し支えない。
【０００２】
【従来の技術】
例えば、特許文献１において述べているタスク割当方法は、未割当タスクをリング上に周回させておき、タスクの実行が終わった、あるいは、もうすぐ終わりそうなサーバがメッセージを送信し、そのメッセージが１周する間に受信したタスクの中で最も優先度が高いタスクを実行するというものである。
【０００３】
【特許文献１】
特開２００３−５０７１０号公報
【非特許文献１】
亀田恒彦、山下雅史、分散アルゴリズム、近代科学社、１９９４
【非特許文献２】
Ｎａｎｃｙ  Ａ．Ｌｙｎｃｈ，Ｄｉｓｔｒｉｂｕｔｅｄ  Ａｌｇｏｒｉｔｈｍｓ，Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，１９９６
【０００４】
【発明が解決しようとする課題】
特許文献１のタスク割当方法は、サーバが主体となり、サーバにとって最適な（メッセージが１周する）時間で次のタスクを割り当てている。しかし、この方法では未割当タスクが空きサーバができるまでずっと周回し続けることになり、莫大な通信コストを要する。
【０００５】
本発明は、このような背景に行われたものであって、例えば特許文献１よりも通信コストを削減したタスク割当または資源割当が可能となり、また、タスクはメッセージが１周する時間で一つずつ割り当てられるが、同時に記録する情報量によっては、同じ時間で複数のタスクを割り当てることが可能となるタスク割り当てまたは資源割り当てのための方法または装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
本発明では、タスクの実行時間が見積もれるという前提で、負荷量が最小のサーバに優先度が最も高いタスクを順次割り当てる方法を考える。なお、優先度としてはそのタスクの生成時刻が望ましい。他の優先度であっても動作するが、割当の結果、優先度順に実行されるという保証はない。また、優先度の代わりにそのタスクの実行時間を用いることも一つの方法だろう。以下では、これらをまとめて単に優先度として扱う。なお、本発明を資源割当方法として利用する場合も、タスク割当方法とほぼ同じ要領で実現できる。
【０００７】
本発明が対象とするネットワークは、特許文献１と同じく、単方向の論理リングである。単方向リングとは、図１に示すように、サーバＰ１，Ｐ２，…，Ｐｎが、その添字が時計方向に昇順に並ぶようにリング状に並べられ、各サーバ間を時計方向に有向辺として表される通信リンクが結ぶネットワークである。サーバＰｉはその添字ｉとサーバ数ｎの情報は持っていないが、代わりにそのサーバ固有の識別情報を持つ。これは現実にはＩＰアドレスと等価なものと考えて差し支えない。また、各サーバの局所メモリの大きさをＯ（ｌｏｇＬ＋ｌｏｇＭ＋ｌｏｇｎ）ビット、サーバ間の通信に用いられるメッセージの長さをｌｏｇＬ＋ｌｏｇＭ＋ｌｏｇｎ＋Ｏ（１）ビットに制限する。ただし、Ｌは各タスクの優先度を表す値の最大値、Ｍは各サーバの負荷量を表す値の最大値である。
【０００８】
このような仮定の下で、各サーバは隣接サーバと適切な回数だけ通信を行うことで問題を解決する。このようなシステムのモデルには主に同期モデルと非同期モデルとがある。これらの詳細は、例えば、非特許文献１または非特許文献２に詳しい。
【０００９】
すなわち、割当処理が起動されていないあるサーバでタスクが発生したら、割当処理を起動し、そのサーバは自身の負荷量とそのタスクの優先度およびそのタスクの重みに自身の識別情報を添えて一つのメッセージを構成して、それぞれの値を局所メモリ中に記録してから、そのメッセージをリングに沿って送信する。そして、まだ起動していないサーバがそのようなメッセージを受信したら、自身の負荷量と、もし未割当タスクを持っていたらそのタスクの優先度に自身の識別情報を添えて一つの新しいメッセージを構成し、その情報を局所メモリ中に記録してからそのメッセージをリングに沿って送信する。
【００１０】
そして、受信したメッセージから負荷量の情報とタスクの優先度を取り出し、取り出した負荷量が局所メモリ中に記録してある負荷量よりも小さければ、受信した負荷量に書き換え、受信メッセージに添えられていた識別情報も記録する。同様に、受信したタスクの優先度の方が記録してあるタスクの優先度よりも高ければ、受信したタスクの優先度に書き換え、受信メッセージに添えられていた識別情報も記録する。そして、受信したメッセージをそのままリングに沿って送信する。
【００１１】
一方、起動しているサーバが他のサーバの識別情報が添えられたメッセージを受信した場合には、上記と同様の情報の更新を行った後、そのメッセージをリングに沿って送信する。最後に、自身の識別情報が添えられたメッセージも受信するが、そのとき、局所メモリに記録してある負荷量およびタスクの優先度が共に自身のものでなければ、その割当処理は終了する。また、局所メモリに記録してある負荷量およびタスクの優先度が共に自身のものならば、記録されている優先度のタスクを自身に割り当てる。実際には、そのタスクは他のサーバにあることが多いので、そのタスクを割り当てる予約のみしておき、割当処理を終了する。
【００１２】
最後に、局所メモリに記録してあるタスクの優先度が自身のもの（即ち、自身よりも優先度が高いタスクが無く書き換えられていない）ならば、そのタスクが記録されている負荷量最小のサーバへタスクを送り、割当処理を終了する。もし、未割当タスクがまだ残っていたら割当処理で使用した変数をクリアした後、再度起動する。
【００１３】
この処理により、未割当タスクがｋ個あればメッセージがｋ周する時間で割当先が決まる。なお、各サーバが割当処理中に局所的に記録する負荷量の情報とタスクの優先度の情報を増やすことにより、１周で割当先が決まるタスクの数を増やすことが可能になる。しかし、その代わりに必要な局所メモリ量が増える。全ての情報を収集することができれば、１周で全てのタスクを割り当てることが可能である。ただし、このように複数のタスクを同時に割り当てるときには、タスクの割当先を一つ決める毎に負荷量を更新する必要があるので、タスクの優先度だけでなく、タスクの重み（実行時間）の情報もメッセージに入れて放送する必要がある。
【００１４】
また、各サーバが送信するタスクの情報も一つに限定されることはない。その場合は一つのサーバが発信する（そのサーバの識別情報が添えられる）メッセージは一つではなくタスク数と同じ数になる。ただし、実行途中で発生したタスクを加えることはできない。
【００１５】
すなわち、本発明の第一の観点は、ｎ台のサーバにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返すタスク割当方法である。
【００１６】
ここで、本発明の特徴とするところは、自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が前記記録した負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信するステップと、
メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割当てるステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了するステップと、これらのステップを未割当タスクがなくなるまで繰り返すステップとを実行するところにある（請求項１）。
【００１７】
また、本発明の第二の観点は、ｎ台のサーバにより仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す資源割当方法である。
【００１８】
ここで、本発明の特徴とするところは、自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の情報と共に保存するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が前記記録した待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した待ち時間と共に保存されている識別情報に相当するサーバへ送信するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新するステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割当てるステップと、メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了するステップと、これらのステップを未割当資源がなくなるまで繰り返すステップとを実行するところにある（請求項２）。
【００１９】
また、本発明の第三の観点は、ｎ台のサーバにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返す分散システムに適用され、前記サーバに設けられたタスク割当装置である。
【００２０】
ここで、本発明の特徴とするところは、自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が前記記録した負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割り当てる手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する手段とを備えたところにある（請求項３）。
【００２１】
また、本発明の第四の観点は、ｎ台のサーバにより仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す分散システムに適用され、前記サーバに設けられた資源割当装置である。
【００２２】
ここで、本発明の特徴とするところは、自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が前記記録した待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した待ち時間と共に保存されている識別情報に相当するサーバへ送信する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新する手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割り当てる手段と、メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する手段とを備えたところにある（請求項４）。
【００２３】
また、本発明の第五の観点は、本発明のタスク割当装置を備えたサーバが仮想的に単方向論理リングを構成して接続されたことを特徴とする分散システムである（請求項５）。あるいは、本発明の資源割当装置を備えたサーバが仮想的に単方向論理リングを構成して接続されたことを特徴とする分散システムである（請求項６）。
【００２４】
本発明の第六の観点は、ｎ台のサーバにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返す分散システムに適用され、前記サーバに設けられたタスク割当装置に適用されるプログラムである。
【００２５】
ここで、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを送信する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が前記記録した負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割り当てる機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する機能とを実現させるところにある（請求項７）。
【００２６】
あるいは、本発明の第六の観点であるプログラムは、ｎ台のサーバにより仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す分散システムに適用され、前記サーバに設けられた資源割当装置に適用されるプログラムである。
【００２７】
ここで、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含みに自サーバの識別情報を付与したメッセージを送信する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が前記記録した待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した待ち時間と共に保存されている識別情報に相当するサーバへ送信する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新する機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割当てる機能と、メッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する機能とを実現させるところにある（請求項８）。
【００２８】
本発明の第七の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項９）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２９】
これにより、情報処理装置を用いて、例えば特許文献１よりも通信コストを削減したタスク割当または資源割当が可能となり、また、タスクはメッセージが１周する時間で一つずつ割り当てられるが、同時に記録する情報量によっては、同じ時間で複数のタスクを割り当てることが可能となるタスク割り当てまたは資源割り当てのための方法または装置を実現することができる。
【００３０】
【発明の実施の形態】
（第一実施形態）
本発明の第一の実施形態であるタスク割当装置の構成を図１および図２を参照して説明する。図１は単方向リングネットワークを示す図である。図２はタスク割当を行うサーバの構成例を示す図である。
【００３１】
本発明の第一の実施形態は、図１に示すように、ｎ台のサーバＰ１〜Ｐｎにより仮想的に構成される単方向論理リング上で、負荷量最小のサーバと優先度最高の未割当タスクとを探し出し、探し出した優先度最高のタスクを、探し出した負荷量最小のサーバに割り当てる処理を未割当タスクがなくなるまで繰り返す分散システム（請求項５）に適用され、図２に示すように、サーバＰ１〜Ｐｎに設けられたタスク割当装置である。メッセージ受信装置により隣接するサーバからのメッセージの受信を行う。また、メッセージ送信装置により隣接するサーバへのメッセージの送信を行う。また、タスク処理部により自サーバに割当てられたタスクの処理を行う。
【００３２】
ここで、第一の実施形態の特徴とするところは、自サーバが生成したタスクの優先度、重み、現時点の自サーバの負荷量を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを前記論理リングを介して隣接するサーバに送信する手段と、当該メッセージを送信した前記隣接サーバとは異なる隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その負荷量が前記記録した負荷量未満であるときには、その負荷量により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバへ送信する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度のタスクを受け入れて自サーバの負荷量を更新する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および負荷量が共に前記記録した優先度および負荷量と同じであれば、前記自サーバが生成したタスクを自サーバに割当てる手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する手段とを備えたところにある（請求項３）。
【００３３】
まず、概要を簡単に述べる。割当処理が起動されていないあるサーバＰｉでタスクが発生したら、割当処理を起動し、そのサーバは自身の負荷量とそのタスクの優先度およびそのタスクの重みに自身の識別情報であるｉｄを添えて一つのメッセージを構成して、それぞれの値を局所メモリ中に記録してから、そのメッセージをリングに沿って送信する。そして、まだ起動していないサーバがそのようなメッセージを受信したら、自身の負荷量と、もし未割当タスクを持っていたらそのタスクの優先度に自身のｉｄを添えて一つの新しいメッセージを構成し、その情報を局所メモリ中に記録してからそのメッセージをリングに沿って送信する。
【００３４】
そして、受信したメッセージから負荷量の情報とタスクの優先度を取り出し、取り出した負荷量が局所メモリ中に記録してある負荷量よりも小さければ、受信した負荷量に書き換え、受信メッセージに添えられていたｉｄも記録する。同様に、受信したタスクの優先度の方が記録してあるタスクの優先度よりも高ければ、受信したタスクの優先度に書き換え、受信メッセージに添えられていたｉｄも記録する。そして、受信したメッセージをそのままリングに沿って送信する。
【００３５】
一方、起動しているサーバが他のサーバのｉｄが添えられたメッセージを受信した場合には、上記と同様の情報の更新を行った後、そのメッセージをリングに沿って送信する。最後に、自身のｉｄが添えられたメッセージも受信するが、そのとき、局所メモリに記録してある負荷量とタスクの優先度とが共に自身のものでなければ、その割当処理は終了する。また、局所メモリに記録してある負荷量とタスクの優先度とが共に自身のものならば、記録されている優先度のタスクを自身に割り当てる。実際には、そのタスクは他のサーバにあることが多いので、そのタスクを割り当てる予約のみしておき、割当処理を終了する。
【００３６】
最後に、局所メモリに記録してあるタスクの優先度が自身のものならば、そのタスクを記録されている負荷量最小のサーバへ送り、割当処理を終了する。もし、未割当タスクがまだ残っていたら割当処理で使用した変数をクリアした後、再度起動する。
【００３７】
この処理により、未割当タスクがｋ個あればメッセージがｋ周する時間で割当先が決まる。なお、各サーバが割当処理中に局所的に記録する負荷量の情報とタスクの優先度の情報を増やすことにより、１周で割当先が決まるタスクの数を増やすことが可能になる。しかし、その代わりに必要な局所メモリ量が増える。全ての情報を収集することができれば、１周で全てのタスクを割り当てることが可能である。ただし、このように複数のタスクを同時に割り当てるときには、タスクの割当先を一つ決める毎に負荷量を更新する必要があるので、タスクの優先度だけでなく、タスクの重み（実行時間）の情報もメッセージに入れて放送する必要がある。
【００３８】
また、各サーバが送信するタスクの情報も一つに限定されることはない。その場合は一つのサーバが発信する（そのサーバのｉｄが添えられる）メッセージは一つではなくタスク数と同じ数になる。ただし、実行途中で発生したタスクを加えることはできない。
【００３９】
以下では、具体的な実行例を挙げて本方法を説明する。システムの起動時点は全てのサーバの負荷量が０で、タスクが一つも割り当てられていない特殊な状況であるため、例として挙げるには適当ではない。そこで、ある程度システムの運用が行われた後の状態を対象にする。また、説明を簡単にするために、メッセージの通信時間はどれも同じであるとし、一つのメッセージが隣のサーバに移動する時間を１単位時間として説明する。実際には通信ディレイがリンク毎に時々刻々と変化するためこのような同期的な動作はしないが、そのような場合でもタイミング以外は下記の説明と同様の動作となる。なお、サーバＰｉのｉｄは、便宜上、その添字ｉと一致させる。また、未割当タスクはτｊで表し、その添字ｊが小さいほど優先度が高いとする。各サーバの負荷量は図中でＬ：に続いて明示する。
【００４０】
初期状態：この説明における初期状態を図３に示す。実際にはタスク割当がある程度進んだ状態である。未割当タスクが存在するので、直前に一つ前のタスクτ０の割当が完了したことになる。この時点で未割当タスクを持つＰ１，Ｐ３が割当処理を起動し、必要な情報を局所メモリに記憶してからメッセージを送信する。この時点の各サーバの局所変数の内容を図４に、送信完了時の状態を図５に示す。図５におけるメッセージの内容は左から順に、そのサーバの負荷量、そのサーバが持つタスクの優先度、そのタスクの重み、そのサーバのｉｄである。また、∞はそのサーバが未割当タスクを持っていないことを表す。
【００４１】
１単位時間後：Ｐ２，Ｐ４がそれぞれＰ１，Ｐ３からのメッセージを受信する。まず、一旦自身の情報を局所メモリに保存してから自身の情報を送信し、受信したメッセージの情報を局所メモリに保存されている情報と比較して負荷量、優先度共に数値が小さい方を保存する。すなわち、優先度は、局所メモリに保存されているものと比較して数値が小さければ局所メモリに保存されているものより優先度が高いことを示す。そして受信したメッセージをそのまま送信する。この時点の各サーバの局所変数の内容を図６に、送信完了時の状態を図７に示す。
【００４２】
２単位時間後〜４単位時間後：メッセージを受信したら１単位時間後と同様に処理する。４単位時間後の送信が完了した時点の各サーバの局所変数の内容を図８に、状態を図９に示す。
【００４３】
５単位時間後：各サーバが自身のｉｄが添えられたメッセージを受信する。この時点で、どのサーバの局所変数の内容も同一の内容になっている。この例においては、最小負荷量がＰ４の６６、優先度最高のタスクがＰ１が持つτ１なので、Ｐ１からＰ４へタスクτ１が移動することになる。なお、このタスクの移動は論理リングに沿って行う必要はない。この時刻における具体的な各サーバの処理は次の四通りに分類される。
【００４４】
場合１：自身の持つタスクが優先度最高で、かつ、自身が負荷量最小のとき：単にその優先度最高のタスクを自身に割り当てる。
【００４５】
場合２：自身の持つタスクが優先度最高で、かつ、自身が負荷最小でないとき：自身の持つ優先度最高のタスクを負荷量最小のサーバへ送信する。
【００４６】
場合３：自身の持つタスクが優先度最高でなく、かつ、自身が負荷量最小のとき：優先度最高のタスクが送られてきたら受信する。また、割当タスク受信前に次の割当処理が開始された場合には、この割当タスクの重みを自身の負荷量に加算した負荷量を割当処理で使用する。
【００４７】
場合４：自身の持つタスクが優先度最高でなく、かつ、自身が負荷量最小でもないとき：何もしない。
【００４８】
これで１回分のタスク割当が終了した。この時点でまだτ２が残っているので、この割当に使用した局所変数の値を初期化した後、Ｐ３から起動して次のタスク割当に移る。ただし、τ１がＰ４に割当られるので、Ｐ４がＰ１からタスクτ１を受け取る前にＰ３から次の割当処理のメッセージを受信した場合には、自身の負荷量にこれから受け取るはずのτ１の負荷量１０を加算した負荷量を自身の負荷量として次の割当処理を行う。
【００４９】
図１０、図１１にフローチャートを示す。なお、Ｉは自身（自サーバ）のｉｄを示す。また、このフローチャートの処理は、タスク生成時かメッセージ受信時のみ開始される。まず、割当処理未起動の場合で（ステップ１）、タスク生成の場合は（ステップ２）、割当処理を起動し、生成タスクの優先度Ｐ、生成タスクの重みＷ、現時点の自身の負荷量Ｌを記録して自身の識別情報（ｉｄ）を付与する（Ｉｐ，ＩＬ）（ステップ３）。これらの記録内容を書き込んだメッセージ（Ｌ，Ｐ，Ｗ，Ｉ）を送信する（ステップ４）。
【００５０】
また、タスク生成でない場合は（ステップ２）、割当処理を起動し、現時点の自身の負荷量Ｌ、優先度Ｐ（∞）、重みＷ（∞）を記録して自身の識別情報（ｉｄ）を付与する（ステップ６）。これらの記録内容を書き込んだメッセージ（Ｌ，Ｐ，Ｗ，Ｉ）を送信する（ステップ７）。なお、前述したように∞はそのサーバが未割当タスクを持っていないことを表す。
【００５１】
隣接サーバからメッセージ（Ｌ′，Ｐ′，Ｗ′，Ｉ′）を受信し（ステップ５）、そのｉｄが自己のｉｄではなく（Ｉ′≠Ｉ）（ステップ８）、その優先度が前記記録した優先度よりも高い（Ｐ＞Ｐ′：即ち数値はＰよりも小さい）ときには、前記記録した優先度Ｐ、重みＷを受信したメッセージの優先度Ｐ′、重みＷ′に書き換える（ステップ１０）。さらに、その負荷量Ｌ′が前記記録した負荷量未満（Ｌ′＜Ｌ）であれば（ステップ１１）、前記記録した負荷量を受信したメッセージの負荷量に書き換える（Ｌ′）（ステップ１２）。メッセージ（Ｌ′，Ｐ′，Ｗ′，Ｉ′）はそのまま隣接サーバに送信される（ステップ１３）。
【００５２】
また、隣接サーバからメッセージを受信し（ステップ５）、そのｉｄが自己のｉｄであり（Ｉ′＝Ｉ）（ステップ８）、さらに、前記自サーバが生成したタスクの優先度が前記記録した優先度と同じであり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバでないときには（ステップ１４：Ｉｐ＝Ｉ、ＩＬ≠Ｉ）、前記自サーバが生成したタスクを前記記録した負荷量と共に保存されている識別情報に相当するサーバＩＬに送信する（ステップ１６）。
【００５３】
また、隣接サーバからメッセージを受信し（ステップ５）、そのｉｄが自己のｉｄであり（Ｉ′＝Ｉ）（ステップ８）、さらに、前記自サーバが生成したタスクの優先度が前記記録した優先度と異なり、前記記録した負荷量と共に保存されている識別情報に相当するサーバが自サーバのときには（ステップ１４：ＩＰ≠Ｉ、ＩＬ＝Ｉ）、前記記録した優先度に相当するタスクを受け入れて自サーバの負荷量を更新する（ステップ１５）。
【００５４】
また、その優先度および負荷量が共に前記記録した優先度および負荷量と同じ（Ｉｐ＝Ｉ、ＩＬ＝Ｉ）であれば（ステップ１４）、自身が生成して持つ優先度Ｐのタスクを自身に割り当てる（ステップ１７）。続いて、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する（ステップ１８）。未割当タスクがあれば（ステップ１９）、ステップ３に戻る（請求項１）。
【００５５】
（第二実施形態）
本発明の第二の実施形態である資源割当装置の構成を図１および図１２を参照して説明する。図１２は資源割当を行うサーバの構成例を示す図である。
【００５６】
本発明の第二の実施形態は、図１に示すように、ｎ台のサーバＰ１〜Ｐｎから仮想的に構成される単方向論理リング上で、資源が利用可能になるまでの時間である待ち時間が最小のサーバと資源割当要求の優先度が最高の未割当資源とを探し出し、探し出した優先度最高の資源を、探し出した待ち時間が最小のサーバに割り当てる処理を未割当資源がなくなるまで繰り返す分散システム（請求項６）に適用され、図１２に示すように、サーバＰ１〜Ｐｎに設けられた資源割当装置である。メッセージ受信装置により隣接するサーバからのメッセージの受信を行う。また、メッセージ送信装置により隣接するサーバへのメッセージの送信を行う。また、資源処理部により自サーバに割り当てられた資源の処理を行う。
【００５７】
ここで、第二の実施形態の特徴とするところは、自サーバの資源割当要求の優先度、重み、現時点の自サーバの待ち時間を記録すると共に当該記録内容を含み自サーバの識別情報を付与したメッセージを前記論理リングを介して隣接するサーバに送信する手段と、当該メッセージを送信した前記隣接サーバとは異なる隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その優先度が前記記録した優先度よりも高いときには、その優先度、重みにより前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報ではなく、その待ち時間が前記記録した待ち時間未満であるときには、その待ち時間により前記記録を書き換え当該メッセージの生成元の識別情報と共に保存する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と同じであり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバではないときには、前記自サーバの資源割当要求を前記記録した待ち時間と共に保存されている識別情報に相当するサーバへ送信する手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であり、前記自サーバの資源割当要求の優先度が前記記録した優先度と異なり、前記記録した待ち時間と共に保存されている識別情報に相当するサーバが自サーバのときには、前記記録した優先度の資源割当要求を受け入れて自サーバの待ち時間を更新するステップと、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であり、その優先度および待ち時間が共に前記記録した優先度および待ち時間と同じであれば、前記自サーバの資源割当要求によって要求した資源を自サーバに割り当てる手段と、隣接サーバからメッセージを受信し、その識別情報が自サーバを示す識別情報であるときには、当該割当処理で使用した内部変数を初期化し、受信メッセージを消去して割当処理を終了する手段とを備えたところにある（請求項４）。
【００５８】
資源割当の説明は、タスク割当の説明から容易に類推できるので詳細な説明は省略する。第一の実施形態の説明におけるタスク優先度が資源割当要求の優先度に、負荷量は資源が利用可能になるまでの時間である待ち時間（例：プリンタ：現在溜まっている文書をすべて印刷し終わるまでの時間）、タスクの重みはその資源を占有する時間（例：プリンタ：その文書を印刷するのに要する時間）に置き換えることで各資源割当要求の割当先資源が、上記タスク割当と同様に本発明により決まる（請求項２）。ただし、自身のｉｄを受信したときの処理は以下に置き換えられる。
【００５９】
場合１：自身の出した資源割当要求が優先度最高で、かつ、自身が負荷量最小のとき、自身の資源を自身で利用するように割当。
【００６０】
場合２：自身の出した資源割当要求が優先度最高で、かつ、自身が負荷量最小でないとき、負荷量最小のサーバの資源へアクセスして資源を利用できる状態になる（割当先サーバから利用可能という通知を受ける）まで待つ。資源がプリンタのようなものなら単にプリントする文書などを送付。
【００６１】
場合３：自身の出した資源割当要求が優先度最高でなく、かつ、自身が負荷量最小のとき、その割当要求を自身に割り当て、その要求を受け入れる順番が来たらその要求元へ通知して資源を提供する。資源がプリンタのようなものなら単にプリントする文書などを受け取り、順番どおりに印刷する。
【００６２】
場合４：自身の持つタスクが優先度最高でなく、かつ、自身が負荷量最小でもないとき、何もしない。
【００６３】
（第三実施形態）
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のタスク割当装置または資源割当装置に相応する機能を実現させるプログラムとして実現することができる（請求項７、８）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項９）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、タスク割当装置または資源割当装置にそれぞれ相応する機能を実現させることができる。
【００６４】
【発明の効果】
本発明により、特許文献１よりも通信コストを削減したタスク割当または資源割当が可能になる。タスクはメッセージが１周する時間で一つずつ割り当てられるが、同時に記録する情報量によっては、同じ時間で複数のタスクを割り当てることも可能になる。
【図面の簡単な説明】
【図１】単方向リングネットワークを示す図。
【図２】第一の実施形態のタスク割当を行うサーバの構成例を示す図。
【図３】実行例の初期状態を示す図。
【図４】実行例の１単位時間後の局所メモリの内容を示す図。
【図５】実行例の１単位時間後の状態を示す図。
【図６】実行例の２単位時間後の局所メモリの内容を示す図。
【図７】実行例の２単位時間後の状態を示す図。
【図８】実行例の５単位時間後の局所メモリの内容を示す図。
【図９】実行例の５単位時間後の状態を示す図。
【図１０】実行例の動作を示すフローチャート。
【図１１】実行例の動作を示すフローチャート。
【図１２】第二の実施形態のタスク割当を行うサーバの構成例を示す図。
【符号の説明】
Ｐ１〜Ｐｎ  サーバ
【図１】
2004348549.tif 000003
【図２】
2004348549.tif 000004
【図３】
2004348549.tif 000005
【図４】
2004348549.tif 000006
【図５】
2004348549.tif 000007
【図６】
2004348549.tif 000008
【図７】
2004348549.tif 000009
【図８】
2004348549.tif 000010
【図９】
2004348549.tif 000011
【図１０】
2004348549.tif 000012
【図１１】
2004348549.tif 000013
【図１２】
2004348549.tif 000014