(57)【要約】【課題】  従来の生成時刻割当と複数タスクを同時に割り当てることができるという特徴を活かした上で、未割当タスクのリング周回数を抑えて通信コストを下げる。【解決手段】  未割当タスクをリング上を周回させながらサーバにとって最適な時間でタスクを割当てる際に、メッセージに最小負荷量のサーバを記憶させ、メッセージが一度も割当処理実行中のサーバに遭遇することなくリングを１周以上した場合に、そこに記憶している最小負荷量のサーバで強制的に割当処理を起動させる。【選択図】  図２
2005190133.tif 000002
【特許請求の範囲】
【請求項１】
ｎ台のサーバから仮想的に論理リングが構成され、
前記サーバの中でタスクを実行しているサーバは、
そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の負荷量Ｌと自身の識別情報ｉLとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、
あるいは、受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身の識別情報ｉLに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信し、
前記サーバの中でタスクの実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバは、
割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′と識別情報ｉ′Lとの組の情報と起点サーバの識別情報ｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信し、
割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点でタスクの情報を保持していればそのタスクの実行を開始し、あるいは、自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身の識別情報からなるメッセージを前記論理リングに沿って送信し、
ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信し、
前記サーバの中でタスクを実行している識別情報ｉのサーバが負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う
ことを特徴とするタスク割当方法。
【請求項２】
タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる請求項１記載のタスク割当方法。
【請求項３】
前記サーバの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバがタスク情報を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てる請求項１記載のタスク割当方法。
【請求項４】
ｎ台のサーバから仮想的に論理リングが構成され、
前記サーバの中で資源を割当られているサーバは、
そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の資源使用時間Ｔと自身の識別情報ｉＴとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、
あるいは、受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身の識別情報ｉＴに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信し、
前記サーバの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバは、
割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′と識別情報ｉ′Ｔとの組の情報と起点サーバの識別情報ｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信し、
割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し、その時点で資源割当要求を保持していなければ再度自身の識別情報からなるメッセージを前記論理リングに沿って送信し、
ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信し、
前記サーバの中で資源を割当てられている識別情報ｉのサーバが資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源を解放したサーバと同様の割当処理を行う
ことを特徴とする資源割当方法。
【請求項５】
資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる請求項４記載の資源割当方法。
【請求項６】
前記サーバの中で資源使用時間が０のサーバが資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身の資源をその資源割当要求に対応するサーバに割り当てる請求項４記載の資源割当方法。
【請求項７】
ｎ台のサーバから仮想的に論理リングが構成され、
前記サーバの中でタスクを実行しているサーバの有する手段として、
そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の負荷量Ｌと自身の識別情報ｉLとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信する手段と、
受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身の識別情報ｉLに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する手段と
を備え、
前記サーバの中でタスクの実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバが有する手段として、
割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′と識別情報ｉ′Lとの組の情報と起点サーバの識別情報ｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する手段と、
割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点でタスクの情報を保持していればそのタスクの実行を開始し、あるいは、自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身の識別情報からなるメッセージをリングに沿って送信する手段と、
ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信する手段と
を備え、
前記サーバの中でタスクを実行している識別情報ｉのサーバが有する手段として、負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う手段を備えた
ことを特徴とするタスク割当装置。
【請求項８】
タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる手段を備えた請求項７記載のタスク割当装置。
【請求項９】
前記サーバの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバが有する手段として、タスク情報を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てる手段を備えた請求項７記載のタスク割当装置。
【請求項１０】
ｎ台のサーバから仮想的に論理リングが構成され、
前記サーバの中で資源を割当られているサーバが有する手段として、
そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の資源使用時間Ｔと自身の識別情報ｉＴとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信する手段と、
受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の負荷量Ｌの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身の識別情報ｉＴに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する手段と
を備え、
前記サーバの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバが有する手段として、
割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′と識別情報ｉ′Ｔとの組の情報と起点サーバの識別情報ｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する手段と、
割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し、その時点で資源割当要求を保持していなければ再度自身の識別情報からなるメッセージを前記論理リングに沿って送信する手段と、
ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信する手段と
を備え、
前記サーバの中で資源を割当てられている識別情報ｉのサーバが有する手段として、負荷量が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源を解放したサーバと同様の割当処理を行う手段を備えた
ことを特徴とする資源割当装置。
【請求項１１】
資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる手段を備えた請求項１０記載の資源割当装置。
【請求項１２】
前記サーバの中で資源使用時間が０のサーバが有する手段として、資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てる手段を備えた請求項１０記載の資源割当装置。
【請求項１３】
ｎ台のサーバから仮想的に論理リングが構成され、
情報処理装置にインストールすることにより、その情報処理装置に、
前記サーバの中でタスクを実行しているサーバに相応する機能として、そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の負荷量Ｌと自身の識別情報ｉLとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信する機能と、
受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身の識別情報ｉLに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する機能と
を実現させ、
前記サーバの中でタスクの実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバに相応する機能として、
割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′と識別情報ｉ′Lとの組の情報と起点サーバの識別情報ｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する機能と、
割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点でタスクの情報を保持していればそのタスクの実行を開始し、あるいは、自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身の識別情報からなるメッセージを前記論理リングに沿って送信する機能と、
ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信する機能と
を実現させ、
前記サーバの中でタスクを実行している識別情報ｉのサーバに相応する機能として、負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う機能を実現させる
ことを特徴とするプログラム。
【請求項１４】
タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる機能を実現させる請求項１３載のプログラム。
【請求項１５】
前記サーバの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバに相応する機能として、タスク情報を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てる機能を実現させる請求項１３記載のプログラム。
【請求項１６】
ｎ台のサーバから仮想的に論理リングが構成され、
情報処理装置にインストールすることにより、その情報処理装置に、
前記サーバの中で資源を割当られているサーバに相応する機能として、
そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の資源使用時間Ｔと自身の識別情報ｉＴとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信する機能と、
受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身の識別情報ｉＴに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する機能と
を実現させ、
前記サーバの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバに相応する機能として、
割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′と識別情報ｉ′Ｔとの組の情報と起点サーバの識別情報ｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する機能と、
割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当てキューへ前記他サーバからの資源割当要求を挿入し、その時点で資源割当要求を保持していなければ再度自身の識別情報からなるメッセージを前記論理リングに沿って送信する機能と、
ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信する機能と
を実現させ、
前記サーバの中で資源を割当てられている識別情報ｉのサーバが有する機能として、資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源を解放したサーバと同様の割当処理を行う機能を実現させる
ことを特徴とするプログラム。
【請求項１７】
資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる機能を実現させる請求項１６記載のプログラム。
【請求項１８】
前記サーバの中で資源使用時間が０のサーバに相応する機能として、資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てる機能を実現させる請求項１６記載のプログラム。
【請求項１９】
請求項１３ないし１８のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散システムにおけるタスク割当および資源割当に関する。なお、並列システムは分散システムの一種であるため、本発明は並列システムでも分散システムでも使えるが、それぞれのシステムにおいては用語が異なるため、以下では並列システムにおけるプロセッサ、ＣＰＵ、分散システムにおけるエージェント、サーバ、計算機、プロセス等の用語を一括してサーバと呼ぶ。なお、厳密にはサーバとプロセスまたはプロセッサは異なるが、本発明の範囲では区別の必要がないためサーバと呼んで差し支えない。
【背景技術】
【０００２】
タスク割当手法は従来から数多く存在し、その実施方法も集中的な手法から分散的な手法までさまざまである。ここでは、完全分散環境において、大域的な負荷分散を実現する動的なタスク割当を考える。
【０００３】
従来の分散環境における動的なタスク割当いわゆる負荷分散は基本的に、マルチキャストを利用して他サーバの負荷量を収集し、各サーバが他のサーバと一対一で交渉してタスクを移動させることにより、局所的に負荷を均衡化させ、それを各サーバが自律的に繰り返すことで大域的な負荷の均衡化を実現しようというものである。
【０００４】
これに対し、局所的な均衡化でなく、最初から大域的な均衡化を目指す手法も存在する。その一つが特許文献１において述べられている論理リング上で生成時刻順にタスクを割り当てる手法である。この手法は、未割当タスクを論理リング上に周回させ、割当済のタスクの実行が終わった、あるいは、もうすぐ終わりそうなサーバが自身の識別情報（以下、ＩＤという）を論理リングに沿って送信することで割当処理を開始し、以後、そのサーバを通過するタスクのうち、最も生成時刻が早いタスクのみを保持し、自身のＩＤが論理リングを１周して戻ってきた時点で保持しているタスクを自身に割り当てて実行する、というものである。
【０００５】
なお、集中的環境（集中制御の並列環境やタスク受付サーバまたはタスク割当装置が１台だけ用意されている分散環境の場合）には、通信遅延の影響や情報の局所性の問題が生じないため、数理計画法に基づいた厳密解法や近似解法を採用することができ、さらに、生成時刻順に割り当てる場合にはタスクを受け取った順番に割り当てるだけで簡単に実現できる。
【特許文献１】特開２００３−０５０７１０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
論理リング上のタスク割当に関する従来手法は、同時に複数のタスクが割り当てられる利点がある一方、未割当タスクが長時間論理リング上を周回する可能性があるため、通信コストが非常に大きくなるという欠点がある。
【０００７】
そこで本発明においては、特許文献１の手法を改良し、特許文献１の手法が保証している理論的性質（生成時刻順割当）と複数タスクを同時に割り当てることができるという特徴を活かした上で、未割当タスクの論理リング周回数を抑えて通信コストを下げることを目的とする。そのため、システムモデル等は特許文献１に開示されているものに準拠する。
【課題を解決するための手段】
【０００８】
本発明は、従来のタスク割当手法の生成時刻順実行という性質を保証した上で、従来法で問題になっていた通信量を削減することにより、通信量が多いために阻害されていた効率を向上することができる。
【０００９】
具体的には、未割当タスクを論理リング上を周回させながらサーバにとって最適な時間でタスクを割当てる際に、メッセージに最小負荷量のサーバを記憶させ、メッセージが一度も割当処理実行中のサーバに遭遇することなく論理リングを１周以上した場合に、そこに記憶している最小負荷量のサーバで強制的に割当処理を起動させる。
【００１０】
すなわち、本発明の第一の観点はタスク割当方法であって、本発明の特徴とするところは、ｎ台のサーバから仮想的に論理リングが構成され、前記サーバの中でタスクを実行しているサーバは、そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバのＩＤｉtおよび自身の負荷量Ｌと自身のＩＤｉLとの組に、さらに自身のＩＤを起点サーバのＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、あるいは受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身のＩＤｉLに書き直し、また、ｉ′0が有効でないときには自身のＩＤｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信し、前記サーバの中でタスクの実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバは、割当処理を起動し、自身のＩＤからなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′とＩＤｉ′Lとの組の情報と起点サーバのＩＤｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信し、割当処理を起動中のサーバが自身のＩＤからなるメッセージを受信したとき、その時点でタスクの情報を保持していればそのタスクの実行を開始し、あるいは、自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身のＩＤからなるメッセージを前記論理リングに沿って送信し、ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信し、前記サーバの中でタスクを実行しているＩＤｉのサーバが負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行うところにある（請求項１）。
【００１１】
また、タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てることができる（請求項２）。
【００１２】
また、前記サーバの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバがタスク情報を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てることができる（請求項３）。
【００１３】
本発明の第二の観点は資源割当方法であって、本発明の特徴とするところは、ｎ台のサーバから仮想的に論理リングが構成され、前記サーバの中で資源を割当られているサーバは、そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバのＩＤｉtおよび自身の資源使用時間Ｔと自身のＩＤｉＴとの組に、さらに自身のＩＤを起点サーバのＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、あるいは受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身のＩＤｉＴに書き直し、また、ｉ′0が有効でないときには自身のＩＤｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信し、前記サーバの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバは、割当処理を起動し、自身のＩＤからなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′とＩＤｉ′Ｔとの組の情報と起点サーバのＩＤｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信し、割当処理を起動中のサーバが自身のＩＤからなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し、その時点で資源割当要求を保持していなければ再度自身のＩＤからなるメッセージを前記論理リングに沿って送信し、ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信し、前記サーバの中で資源を割当てられているＩＤｉのサーバが資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源を解放したサーバと同様の割当処理を行うところにある（請求項４）。
【００１４】
また、資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てることができる（請求項５）。
【００１５】
また、前記サーバの中で資源使用時間が０のサーバが資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てることができる（請求項６）。
【００１６】
本発明の第三の観点は、タスク割当装置であって、本発明の特徴とするところは、ｎ台のサーバから仮想的に論理リングが構成され、前記サーバの中でタスクを実行しているサーバの有する手段として、そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバのＩＤｉtおよび自身の負荷量Ｌと自身のＩＤｉLとの組に、さらに自身のＩＤを起点サーバのＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信する手段と、受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身のＩＤｉLに書き直し、また、ｉ′0が有効でないときには自身のＩＤｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する手段とを備え、前記サーバの中でタスクの実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバが有する手段として、割当処理を起動し、自身のＩＤからなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′とＩＤｉ′Lとの組の情報と起点サーバのＩＤｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する手段と、割当処理を起動中のサーバが自身のＩＤからなるメッセージを受信したとき、その時点でタスクの情報を保持していればそのタスクの実行を開始し、あるいは、自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身のＩＤからなるメッセージを前記論理リングに沿って送信する手段と、ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信する手段とを備え、前記サーバの中でタスクを実行しているＩＤｉのサーバが有する手段として、負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う手段を備えたところにある（請求項７）。
【００１７】
また、タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる手段を備えることができる（請求項８）。
【００１８】
また、前記サーバの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバが有する手段として、タスク情報を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てる手段を備えることができる（請求項９）。
【００１９】
本発明の第四の観点は、資源割当装置であって、本発明の特徴とするところは、ｎ台のサーバから仮想的に論理リングが構成され、前記サーバの中で資源を割当られているサーバが有する手段として、そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバのＩＤｉtおよび自身の資源使用時間Ｔと自身のＩＤｉＴとの組に、さらに自身のＩＤを起点サーバのＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信する手段と、受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身のＩＤｉＴに書き直し、また、ｉ′0が有効でないときには自身のＩＤｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する手段とを備え、前記サーバの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバが有する手段として、割当処理を起動し、自身のＩＤからなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′とＩＤｉ′Ｔとの組の情報と起点サーバのＩＤｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する手段と、割当処理を起動中のサーバが自身のＩＤからなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し、その時点で資源割当要求を保持していなければ再度自身のＩＤからなるメッセージを前記論理リングに沿って送信する手段と、ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信する手段とを備え、前記サーバの中で資源を割当てられているＩＤｉのサーバが有する手段として、資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源の解放したサーバと同様の割当処理を行う手段を備えたところにある（請求項１０）。
【００２０】
また、資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる手段を備えることができる（請求項１１）。
【００２１】
また、前記サーバの中で資源使用時間が０のサーバが有する手段として、資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てる手段を備えることができる（請求項１２）。
【００２２】
本発明の第五の観点は、プログラムであって、本発明の特徴とするところは、ｎ台のサーバから仮想的に論理リングが構成され、情報処理装置にインストールすることにより、その情報処理装置に、前記サーバの中でタスクを実行しているサーバに相応する機能として、そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバのＩＤｉtおよび自身の負荷量Ｌと自身のＩＤｉLとの組に、さらに自身のＩＤを起点サーバのＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信する機能と、受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身のＩＤｉLに書き直し、また、ｉ′0が有効でないときには自身のＩＤｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する機能とを実現させ、前記サーバの中でタスクの実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバに相応する機能として、割当処理を起動し、自身のＩＤからなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′とＩＤｉ′Lとの組の情報と起点サーバのＩＤｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する機能と、割当処理を起動中のサーバが自身のＩＤからなるメッセージを受信したとき、その時点でタスクの情報を保持していればそのタスクの実行を開始し、あるいは、自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身のＩＤからなるメッセージを前記論理リングに沿って送信する機能と、ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信する機能とを実現させ、前記サーバの中でタスクを実行しているＩＤｉのサーバに相応する機能として、負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う機能を実現させるところにある（請求項１３）。
【００２３】
また、タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる機能を実現させることができる（請求項１４）。
【００２４】
また、前記サーバの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバに相応する機能として、タスク情報を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てる機能を実現させることができる（請求項１５）。
【００２５】
あるいは、本発明のプログラムは、ｎ台のサーバから仮想的に論理リングが構成され、情報処理装置にインストールすることにより、その情報処理装置に、前記サーバの中で資源を割当られているサーバに相応する機能として、そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバのＩＤｉtおよび自身の資源使用時間Ｔと自身のＩＤｉＴとの組に、さらに自身のＩＤを起点サーバのＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信する機能と、受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身のＩＤｉＴに書き直し、また、ｉ′0が有効でないときには自身のＩＤｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信する機能とを実現させ、前記サーバの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバに相応する機能として、割当処理を起動し、自身のＩＤからなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′とＩＤｉ′Ｔとの組の情報と起点サーバのＩＤｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信する機能と、割当処理を起動中のサーバが自身のＩＤからなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し、その時点で資源割当要求を保持していなければ再度自身のＩＤからなるメッセージを前記論理リングに沿って送信する機能と、ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信する機能とを実現させ、前記サーバの中で資源を割当てられているＩＤｉのサーバが有する機能として、資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源の割当を解放したサーバと同様の割当処理を行う機能を実現させることを特徴とする（請求項１６）。
【００２６】
また、資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる機能を実現させることができる（請求項１７）。
【００２７】
また、前記サーバの中で資源使用時間が０のサーバに相応する機能として、資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てる機能を実現させることができる（請求項１８）。
【００２８】
本発明の第六の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である（請求項１９）。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２９】
これにより、汎用の情報処理装置を用いて、従来のタスク割当手法の生成時刻順実行という性質を保証した上で、従来法で問題になっていた通信量を削減することにより、通信量が多いために阻害されていた効率も向上することが期待できるタスク割当装置または資源割当装置を実現することができる。
【発明の効果】
【００３０】
本発明により、従来のタスク割当手法の生成時刻順実行という性質を保証した上で、従来法で問題になっていた通信量を削減することが期待できる。これにより、通信量が多いために阻害されていた効率も向上することが期待できる。
【発明を実施するための最良の形態】
【００３１】
本方法は、図１に示すｎ台のサーバから仮想的に構成される論理リングに適用される。図１におけるＰ1、Ｐ2、…、Ｐnは前記ｎ台のサーバを表す。当該サーバは、図２に示すように、メッセージ受信装置１、負荷量計測装置７、内部状態保持装置５、タスク割当装置２、タスク処理装置３、タスク完了見込み推定装置６、メッセージ送信装置４を主な構成要素とする。また、前記サーバが送受信するメッセージは、制御メッセージ、タスク情報、サーバ負荷情報、起点サーバＩＤから構成される。さらに、タスク情報は、タスクの生成時刻を表す優先度、タスクの重み、タスク生成サーバ、またはタスク保持元サーバを表すＩＤから構成され、サーバ負荷情報は、サーバの負荷量と当該サーバＩＤとからなる。
【００３２】
メッセージは次のように表現される。
【００３３】
構成：（ｓｔａｔｅ，（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）
各要素の意味：
ｓｔａｔｅ：制御メッセージ∈｛ｉｄ，ｔａｓｋ｝
ｐ：タスクの優先度（生成時刻）．ｓｔａｔｅ＝ｔａｓｋのときのみ有効
ｗ：タスクの重み、ｓｔａｔｅ＝ｔａｓｋのときのみ有効
ｉt：タスク保持元サーバＩＤ、ｓｔａｔｅ＝ｔａｓｋのときのみ有効
Ｌ：サーバｉLの負荷量、ｎｕｌｌはデータなしを意味し、ｓｔａｔｅ＝ｔａｓｋのときのみ有効
ｉL：サーバＩＤ、ｎｕｌｌはデータなしを意味し、ｓｔａｔｅ＝ｔａｓｋのときのみ有効
ｉ0：ｓｔａｔｅ＝ｔａｓｋのときは起点サーバＩＤであり、ｎｕｌｌはデータなしを、ｌｏｃｋは負荷量の確定を意味する。ｓｔａｔｅ＝ｉｄのときは割当処理を起動したサーバＩＤを表す。
【００３４】
また、ｓｔａｔｅ：メッセージの状態を表す。
【００３５】
ｉｄ：メッセージを送信したサーバのｉｄが当該メッセージに含まれていることを表す。
【００３６】
ｔａｓｋ：メッセージがタスクの情報を持っていることを表す。
【００３７】
また、ｔａｓｋの重みｗは、サーバがタスクを処理する実行時間を表す。
【００３８】
タスクを実行しているサーバは、そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報（優先度（生成時刻）ｐ，重みｗ，生起サーバＩＤｉt）および自身の負荷量ＬとＩＤｉL（ＩＰアドレス等）のペアにさらに自身のＩＤを起点サーバＩＤｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を論理リングに沿って送信し、あるいは受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量が確定されていないときにそのメッセージに記録されている負荷量Ｌ′よりも自身の負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身のＩＤに書き直し、また、ｉ′0が有効でない場合には自身のＩＤを設定したメッセージを論理リングに沿って送信する。
【００３９】
そして、タスク実行を完了した、あるいは、タスクの実行完了までの残り時間が所定時間内であるサーバのみが割当処理を起動し、自身のＩＤのみからなるメッセージを論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度のなかで最も優先度が高いタスクの情報のみを保持し、それ以外については、メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′とＩＤｉ′Lのペア情報と起動サーバＩＤｉ′0をクリアしてそのタスクの情報（優先度ｐ′、重みｗ′、生成サーバＩＤｉ′t）で構成されたメッセージを論理リングに沿って送信する。
【００４０】
なお、負荷量Ｌ′は、未確定の値が入っている場合と、既に確定された値が入っている場合と、クリアされている場合とがあるが、クリアされている場合は、Ｌ′の値が無限大と解釈することにより、未確定の場合と同等に扱うことができる。
【００４１】
ここで「タスクの実行完了までの残り時間が所定時間内であるサーバ」と述べたが、当該所定時間は、タスクの割当が決定していない初期状態では「サーバ数×１回あたりの通信遅延＋タスクの移動に要する時間の予測平均値」により定める。その後は、タスクの割当が決定してから実際に処理開始できるまでの時間の平均値をとり、その値を反映する。
【００４２】
その後、割当処理を起動中のサーバが自身のＩＤのみからなるメッセージを受信したら、その時点でタスクの情報を保持していればそのタスクの実行を開始、あるいは、自身のタスクキューへ前記タスクの情報を挿入（つまり割当）して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身のＩＤのみからなるメッセージを論理リングに沿って送信する。
【００４３】
また、ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がＩＤｉ′0のサーバに受信されたら、そのサーバはそのメッセージを送信することになったら負荷量を確定して（例えばｉ′Oに特別な値をセットして）送信する。
【００４４】
タスクを実行しているＩＤｉのサーバが負荷量を確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う。
【００４５】
このような処理を反復することでタスクの割当が行われる（請求項１）。これが基本的な手法であるが、さらに、自身のＩＤが既に１周以上周回しているときには、
１．タスクが生成された時点で、自身の負荷量がメッセージが論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる（請求項２）。
【００４６】
２．自身の負荷量が０（またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度）になった後、タスク情報を含んだメッセージを受信したら、割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てるという変更を施すことにより、論理的な生成時刻順の実行開始を保証したままで、サーバのＣＰＵパワーを無駄にする可能性が軽減する手法となる（請求項３）。ただし、この場合には、割当処理を終えた後に自身のＩＤを受信することになるが、その場合には、そのメッセージを単純に無視すればよい。この手法を形式的に表現すると以下のようになる。
【００４７】
内部処理命令：
ｓｅｎｄ  Ｒ：メッセージＲを論理リング上の隣接サーバへ送信
外的要因により自動設定される各サーバの内部変数：
ｆ：ｂｏｏｌｅａｎ．タスク実行完了（見込み）を表す。
【００４８】
ｃ：ｂｏｏｌｅａｎ．タスク生成を表す。
【００４９】
ｒ：ｂｏｏｌｅａｎ．メッセージ受信を表す。
【００５０】
ｐｃ：生成タスクがあるとき、生成タスクの優先度（生成時刻＝現時刻）を表す。
【００５１】
ｗｃ：生成タスクがあるとき、生成タスクの重みを表す。
【００５２】
Ｒ：受信メッセージ（ｓｔａｔｅ（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）
各サーバの内部定数：
Ｉ：自身のＩＤ
各サーバの内部変数：
ｅ：ｂｏｏｌｅａｎ．割当処理実行中かどうか。
【００５３】
ｌｏｏｐ：ｂｏｏｌｅａｎ．制御メッセージ（ＩＤ）が１周したかどうか。
【００５４】
Ｌ：現時点の負荷量。新しいタスクの割当時の負荷量増加以外は自動更新。
【００５５】
ｐ：現時点で保持しているタスクの優先度（生成時刻）。
【００５６】
ｗ：現時点で保持しているタスクの重み。
【００５７】
ｉt：現時点で保持しているタスクの本体を保持するサーバＩＤ。
【００５８】
なお、ｂｏｏｌｅａｎという表現は、内部変数ｆ，ｃ，ｒ，ｅ，ｌｏｏｐがｔｒｕｅまたはｆａｌｓｅの２値を取る変数であることを表している。
【００５９】
起動条件：メッセージ受信、タスク生成、タスク実行完了（見込み）
処理順：タスク実行完了（見込み）、生成タスク、受信メッセージ
割当アルゴリズム（タスクの移動要求の処理、移動処理、実行開始処理、タスク実行完了時の処理は除く）：
図１９に示すように、
ｉｆ  ｆ＝ｔｒｕｅ  ａｎｄ  ｅ＝ｆａｌｓｅ  ｔｈｅｎ
ｓｅｎｄ（ｉｄ，（ｎｕｌｌ，ｎｕｌｌ，ｎｕｌｌ），（ｎｕｌｌ，ｎｕｌｌ），Ｉ）
ｅ：＝ｔｒｕｅ
ｌｏｏｐ：＝ｆａｌｓｅ
ｉｆ  ｃ＝ｔｒｕｅ  ｔｈｅｎ
ｉｆ  ｅ＝ｔｒｕｅ  ａｎｄ  ｌｏｏｐ＝ｔｒｕｅ  ａｎｄ  ｐ＝ｎｕｌｌ  ａｎｄ  Ｌ＝０  ｔｈｅｎ
生成タスクを自身に割り当て、すぐに実行開始
ｅ：＝ｆａｌｓｅ
ｌｏｏｐ：＝ｆａｌｓｅ
ｉｆ  ｅ＝ｔｒｕｅ  ｔｈｅｎ
ｉｆ  ｐ＜ｐｃ  ｔｈｅｎ
ｓｅｎｄ（ｔａｓｋ，（ｐｃ，ｗｃ，Ｉ），（ｎｕｌｌ，ｎｕｌｌ），ｎｕｌｌ）
ｅｌｓｅ
ｓｅｎｄ（ｔａｓｋ，（ｐ，ｗ，ｉt），（ｎｕｌｌ，ｎｕｌｌ），ｎｕｌｌ）
ｐ：＝ｐｃ
ｗ：＝ｗｃ
ｉt＝Ｉ
ｅｌｓｅ
ｓｅｎｄ（ｔａｓｋ，（ｐｃ，ｗｃ，Ｉ），（Ｌ，Ｉ），Ｉ）
また、図２０に示すように、
ｉｆ  ｒ＝ｔｒｕｅ  ｔｈｅｎ
ｉｆ  ｓｔａｔｅ＝ｉｄ  ｔｈｅｎ
ｉｆ  ｅ＝ｆａｌｓｅ  ａｎｄ  ｉ′0＝Ｉ  ｔｈｅｎ
受信メッセージを破棄
ｅｌｓｅ  ｉｆ  ｅ＝ｔｒｕｅ  ａｎｄ  ｉ′0＝Ｉ  ｔｈｅｎ
ｉｆ  ｐ≠ｎｕｌｌ  ｔｈｅｎ
優先度ｐのタスクを自身に割り当て、サーバｉtへ移動要求
Ｌ：＝Ｌ＋ｗ
ｅ：＝ｆａｌｓｅ
ｐ：＝ｎｕｌｌ
ｗ：＝０
ｉt：＝ｎｕｌｌ
ｅｌｓｅ
ｌｏｏｐ：＝ｔｒｕｅ
ｓｅｎｄ  Ｒ
ｅｌｓｅ
ｓｅｎｄ  Ｒ
ｅｌｓｅ
ｉｆ  ｅ＝ｔｕｒｅ  ｔｈｅｎ
ｉｆ  ｐ＝ｎｕｌｌ  ｔｈｅｎ
ｉｆ  Ｌ＝０  ａｎｄ  ｌｏｏｐ＝ｔｒｕｅ  ｔｈｅｎ
受信タスクを自身に割り当て、ｉ′tへタスク移動要求
ｅ：＝ｆａｌｓｅ
ｌｏｏｐ：＝ｆａｌｓｅ
ｅｌｓｅ
ｐ：＝ｐ′
ｗ：＝ｗ′
ｉt：＝ｉ′t
ｅｌｓｅ  ｉｆ  ｐ＜ｐ′ｔｈｅｎ
ｓｅｎｄ（ｔａｓｋ，（ｐ′，ｗ′，ｉ′t），（ｎｕｌｌ，ｎｕｌｌ），ｎｕｌｌ）
ｅｌｓｅ
ｓｅｎｄ（ｔａｓｋ，（ｐ，ｗ，ｉt），（ｎｕｌｌ，ｎｕｌｌ），ｎｕｌｌ）
ｐ：＝ｐ′
ｗ：＝ｗ′
ｉt：＝ｉ′t
また、図２１に示すように、
ｅｌｓｅ
ｉｆ  ｉ′0＝ｎｕｌｌ  ｔｈｅｎ
ｓｅｎｄ（ｔａｓｋ，（ｐ′，ｗ′，ｉ′t），（Ｌ，Ｉ），Ｉ）
ｅｌｓｅ  ｉｆ  ｉ′0＝ｌｏｃｋ  ａｎｄ  ｉ′L＝Ｉ  ｏｒ  ｉ′0＝Ｉ  ａｎｄ  ｉ′L＝Ｉ  ｔｈｅｎ
ｅ：＝ｔｒｕｅ
ｐ：＝ｐ′
ｗ：＝ｗ′
ｉt：＝ｉ′t
ｓｅｎｄ（ｉｄ，（ｎｕｌｌ，ｎｕｌｌ，ｎｕｌｌ），（ｎｕｌｌ，ｎｕｌｌ），Ｉ）
ｅｌｓｅ  ｉｆ  ｉ′0＝ｌｏｃｋ  ａｎｄ  ｉ′L≠Ｉ  ｔｈｅｎ
ｓｅｎｄ  Ｒ
ｅｌｓｅ  ｉｆ  ｉ′0＝Ｉ  ａｎｄ  ｉ′L≠Ｉ  ｔｈｅｎ
ｓｅｎｄ（ｔａｓｋ，（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｌｏｃｋ）
ｅｌｓｅ  ｉｆ  Ｌ＜Ｌ′  ｔｈｅｎ
ｓｅｎｄ（ｔａｓｋ，（ｐ′，ｗ′，ｉ′t），（Ｌ，Ｉ），ｉ′0）
ｅｌｓｅ
ｓｅｎｄ  Ｒ
なお、図１９〜図２１において、例えば「ｅ＝ｆａｌｓｅ」は変数値ｅがｆａｌｓｅであることを表す。また、「ｅ：＝ｔｒｕｅ」は変数値ｅにｔｒｕｅを代入することを表す。以下、「＝」、「：＝」は同様の意味を表す。
【００６０】
また、図１９、図２０におけるタスク生成とメッセージ受信とは同時に発生しないものとする。具体的には「処理の優先順位をあらかじめ決めておく」、「２つのイベントは同時に発生しないと仮定する」などのルールを設ける。
【００６１】
以下では、具体的な実行例を挙げて本方法を説明する。特許文献１との比較のため、特許文献１の「動的な問題に対する実行例」に類似した状況において動作を説明する。
【００６２】
この例では、初期状態として全てのサーバがタスクを実行中で、かつ、未割当タスクが存在しない状態を対象とする。ここで、到着または生成時刻が０になっているタスクは、そのサーバで実行中のタスクである。
【００６３】
なお、新たに到着または生成したタスクの優先度はその論理時刻であるが、ここでは仮想的に大域的な時計が存在するものとして時刻（優先度）を与える。
【００６４】
また、実際には各メッセージの通信時間は異なるが、以下の説明では基本的に１回の通信に要する時間は１単位時間とする。ただし、説明をわかりやすくするために、一部においてこの時間を２単位時間にしている部分もある。さらに、途中の単なるメッセージ（ＩＤやタスク）の中継処理については煩雑になるので説明を省き、簡単のために、タスク実行完了見込みの判断はせず、完全にタスクの実行が完了したときのみｆ＝ｔｒｕｅとなるとして説明する。
【００６５】
１．全てのサーバがタスクを実行中で、かつ、未割当タスクが存在しないので、アルゴリズムが停止している状態とほとんど同値、図４のようにメッセージは何も送信されず、かつ、内部に保持されているタスクもない（実行中のタスクは割当済なので）。各サーバの負荷量（割当済タスクの残り実行時間）は図５のとおりである。
【００６６】
２．サーバＰ1がタスクの実行を完了（ｆ＝ｔｒｕｅ）してｅ＝ｔｒｕｅとなり、同時に、Ｐ2において新しいタスク１（優先度２、重み３０）が生成される。図６に示すようにメッセージ（ＩＤ，タスク）が送信され、内部状態は図７のようになる。
【００６７】
３．サーバＰ1において新しいタスク２（優先度４、重み２５）が生成される。Ｐ1はまだタスクを何も持っていないのでタスク２を保持する。図８に示すように、メッセージが流れていて、内部状態は図９のようになる。
【００６８】
４．サーバＰ1にタスク１が届く。優先度はタスク１の方が保持しているタスク２よりも高いので、タスク１を保持し、メッセージのｉ0に自身のＩＤをセットしてタスク２を送信する。その他、図１０に示すようにメッセージが流れていて、内部状態は図１１のようになる。
【００６９】
５．タスク２がサーバＰ2に届き、Ｐ2の負荷量情報が付加されて送信される。Ｐ2の負荷量はＰ3、Ｐ4よりも遥かに軽いので、Ｐ3、Ｐ4によって更新されることはない。その他、図１２に示すようにメッセージが流れていて、内部状態は図１３のようになる。
【００７０】
６．サーバＰ1に自身のＩＤ１が一周して戻ってきたので、その時点で保持しているタスク１の実行を開始する。そして、ｅ＝ｆａｌｓｅとなる。すると、ｅ＝ｔｒｕｅとなっているサーバが存在しなくなるが、まだ、タスク２は未割当で残っているので、図１４に示すようにメッセージが流れていて、内部状態は図１５のようになる。
【００７１】
７．タスク２が起点サーバＰ2に届く。ｉ′L＝２のため、強制的にタスク２を保持して割当アルゴリズムを起動し、自身のＩＤを送信し、図１６に示すようにメッセージが流れていて、内部状態は図１７のようになる。なお、もし、ｉ′L＝２でない場合には、ｉ0をｌｏｃｋにセットして送信する。
【００７２】
８．サーバＰ2に自身のＩＤ２が一周して戻ってきたので、その時点で保持しているタスク２を自身に割り当て、ｅ＝ｆａｌｓｅとなる。この時点でｅ＝ｔｒｕｅとなっているサーバも未割当タスクも存在しなくなるので、図４のように論理リング中を流れるメッセージは一つもなくなり、内部状態は図１８に示すような状態になる。
【００７３】
以上の説明は、本実施例のタスク割当方法についての説明である。以下では、本実施例のタスク割当方法を用いた資源割当方法（請求項４〜６）、タスク割当装置（請求項７〜９）、資源割当装置（請求項１０〜１２）、プログラム（請求項１３〜１８）、記録媒体（請求項１９）について説明する。
【００７４】
本実施例の資源割当方法は、図１に示すように、ｎ台のサーバＰ1〜Ｐnから仮想的に論理リングが構成され、サーバＰ1〜Ｐnの中で資源を割当られているサーバは、そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の資源使用時間Ｔと自身の識別情報ｉＴとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、あるいは受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身の識別情報ｉＴに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージを前記論理リングに沿って送信し、サーバＰ1〜Ｐnの中で資源を解放した、あるいは、資源の解放までの残り時間が所定時間内であるサーバは、割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求と受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′と識別情報ｉ′Ｔとの組の情報と起点サーバの識別情報ｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージを前記論理リングに沿って送信し、割当処理を起動中のサーバが自身の識別情報からなるメッセージを受信したとき、その時点で自身の資源割当要求を保持していればその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し（１）、その時点で他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し（２）、その時点で資源割当要求を保持していなければ再度自身の識別情報からなるメッセージを前記論理リングに沿って送信し、ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′L），ｉ′0）がｉ′0のサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信し、サーバＰ1〜Ｐnの中で資源を割当てられている識別情報ｉのサーバが資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）を受信したら割当処理を起動して資源を解放したサーバと同様の割当処理を行うことを特徴とする（請求項４）。
【００７５】
ここで「資源の割当解放までの残り時間が所定時間内であるサーバ」と述べたが、当該所定時間は、資源の割当が決定していない初期状態では「サーバ数×１回あたりの通信遅延」により定める。その後は、資源の割当が決定してから実際に資源の運用が開始できるまでの時間の平均値をとり、その値を反映する。
【００７６】
また、上記の「自身の資源割当キューへ前記資源割当要求を挿入し（１）」という処理は、その資源が現在使用中の場合には、すぐに資源運用開始ができないため、現在の資源運用が完了するまで待つために自身の資源割当キューへ自身の資源割当要求を挿入する必要がある場合に行われる。また、「自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し（２）」という処理は、他サーバからの資源割当要求の場合も同様に、資源が運用中ならば、すぐに資源提供を開始することができないため、自身の資源割当要求の場合と同様に、資源割当キューに挿入する必要がある場合に行われる。
【００７７】
すなわち、タスク割当てでは、タスクを受け取って自身のＣＰＵという資源を使って処理するのに対し、資源割当てでは、単に自身の資源を提供する、ということしかしないという点でタスク割当てとは大きく異なる。したがって、タスク割当ての際には、すぐにタスクを実行できるか否かに関わらず、タスクを受け取ることができるが、一般に、資源割当てではそれと異なり、例えば、データベースなどの場合には書き込みや読み込みなどの資源運用がその前に読み書きされたデータの内容などに影響されるため、あらかじめ処理すべき内容（資源の運用内容）を受け取ることはできない。したがって、自身あるいは他サーバの資源割当要求を資源割当キューに挿入するという処理が必要になる。
【００７８】
また、資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる（請求項５）。
【００７９】
あるいは、サーバＰ1〜Ｐnの中で資源使用時間が０のサーバが資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てる（請求項６）。
【００８０】
本実施例のタスク割当装置は、図１に示すように、ｎ台のサーバＰ1〜Ｐnから仮想的に論理リングが構成され、図２に示すように、サーバＰ1〜Ｐnの中でタスクを実行しているサーバの有するタスク割当装置２は、そのサーバで生成されるかそのサーバへシステム外から到着したタスクの情報として当該タスクの優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび自身の負荷量Ｌと自身の識別情報ｉLとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信する手段と、メッセージ受信装置１により受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）の負荷量Ｌ′が未だ確定されていないときには、当該メッセージに記録されている負荷量Ｌ′よりも自身の負荷量計測装置７により計測した負荷量Ｌの方が小さな場合にはＬ′をＬに、ｉ′Lを自身の識別情報ｉLに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージをメッセージ送信装置４により論理リングに沿って送信する手段とを備える。
【００８１】
また、サーバＰ1〜Ｐnの中でタスクの実行を完了した、あるいは、タスク完了見込み推定装置６により推定されたタスクの実行完了までの残り時間が所定時間内であるサーバが有するタスク割当装置２は、割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｌ，ｉL），ｉ0）を前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着したタスクと受信したメッセージに記録されているタスクの優先度の中で最も優先度が高いタスクの情報を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）に記録されている負荷量Ｌ′と識別情報ｉ′Lとの組の情報と起点サーバの識別情報ｉ′0をクリアしてそのタスクの情報（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージをメッセージ送信装置４により論理リングに沿って送信する手段と、割当処理を起動中のサーバが自身の識別情報からなるメッセージをメッセージ受信装置１により受信したとき、その時点で内部状態保持装置５にタスクの情報を保持していればタスク処理装置３は、そのタスクの実行を開始し、あるいは、内部状態保持装置５の自身のタスクキューへ前記タスクの情報を挿入して割当処理を完了してからタスク保持元へタスクの移動要請を出してタスクを受け取り、タスクの情報を保持していなければ再度自身の識別情報からなるメッセージをメッセージ送信装置４により論理リングに沿って送信する手段と、ｉ′L＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）がｉ′0のメッセージ受信装置１によりサーバに受信されたとき、そのサーバはそのメッセージを送信するときに負荷量が確定した旨の情報を付与して当該メッセージを送信する手段とを備える。
【００８２】
また、サーバＰ1〜Ｐnの中でタスクを実行している識別情報ｉのサーバが有するタスク割当装置２は、負荷量が確定されていてｉ′L＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｌ′，ｉ′L），ｉ′0）を受信したら割当処理を起動してタスクの実行を完了したサーバと同様の割当処理を行う手段を備える（請求項７）。
【００８３】
また、タスク割当装置２は、タスクが生成された時点で、自身の負荷量が前記メッセージが前記論理リングを１周する時間に相当する負荷量よりも小さければ、割当処理を起動せずに、無条件に自身にそのタスクを割り当てる手段を備える（請求項８）。
【００８４】
あるいは、サーバＰ1〜Ｐnの中で負荷量が０またはタスクを当該タスクの保持元から自サーバへ移動する時間分程度のサーバが有するタスク割当装置２は、タスク情報を含んだメッセージをメッセージ受信装置１により受信したときには、前記割当処理に沿った動作をせず、すぐに自身にそのタスクを割り当てる手段を備える（請求項９）。
【００８５】
本実施例の資源割当装置は、図１に示すように、ｎ台のサーバＰ1〜Ｐnから仮想的に論理リングが構成され、図３に示すように、サーバＰ1〜Ｐnの中で資源を割当られているサーバが有する資源割当装置１２は、そのサーバで生成されるかそのサーバへシステム外から到着した資源割当要求として当該資源割当の優先度ｐ、重みｗ、生起サーバの識別情報ｉtおよび資源使用時間計測装置１７により計測された自身の資源使用時間Ｔと自身の識別情報ｉＴとの組に、さらに自身の識別情報を起点サーバの識別情報ｉ0として添えて構成されたメッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）をメッセージ送信装置４により前記論理リングに沿って送信する手段と、メッセージ受信装置１により受信したメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）の資源使用時間Ｔ′が未だ確定されていないときには、当該メッセージに記録されている資源使用時間Ｔ′よりも自身の資源使用時間Ｔの方が小さな場合にはＴ′をＴに、ｉ′Ｔを自身の識別情報ｉＴに書き直し、また、ｉ′0が有効でないときには自身の識別情報ｉ0をｉ′0に代入したメッセージをメッセージ送信装置４により論理リングに沿って送信する手段とを備える。
【００８６】
また、サーバＰ1〜Ｐnの中で資源を解放した、あるいは、資源解放見込み推定装置１６により資源の解放までの残り時間が所定時間内であるサーバが有する資源割当装置１２は、割当処理を起動し、自身の識別情報からなる前記メッセージ（（ｐ，ｗ，ｉt），（Ｔ，ｉＴ），ｉ0）をメッセージ送信装置４により前記論理リングに沿って送信し、以後、自身で生成されるかシステム外から到着した資源割当要求とメッセージ受信装置１により受信したメッセージに記録されている資源割当要求の優先度の中で最も優先度が高い資源割当要求を保持し、それ以外については、前記メッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）に記録されている資源使用時間Ｔ′と識別情報ｉ′Ｔとの組の情報と起点サーバの識別情報ｉ′0をクリアしてその資源割当要求（優先度ｐ′，重みｗ′，生起サーバｉ′t）により構成されたメッセージをメッセージ送信装置４により論理リングに沿って送信する手段と、割当処理を起動中のサーバが自身の識別情報からなるメッセージをメッセージ受信装置１により受信したとき、その時点で内部状態保持装置５に資源割当要求を保持していれば資源運用装置１３によりその資源運用を開始し、あるいは、自身の資源割当キューへ前記資源割当要求を挿入し、その時点で内部状態保持装置５に他サーバからの資源割当要求を保持していれば、そのサーバへの資源提供を開始し、あるいは、自身の資源割当キューへ前記他サーバからの資源割当要求を挿入し、その時点で内部状態保持装置５に自身の資源割当要求を保持していなければ再度自身の識別情報からなるメッセージをメッセージ送信装置４により論理リングに沿って送信する手段と、ｉ′Ｔ＝ｉ′0でないメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）がｉ′0のメッセージ受信装置１によりサーバに受信されたとき、そのサーバはそのメッセージを送信するときに資源使用時間が確定した旨の情報を付与して当該メッセージを送信する手段とを備える。
【００８７】
また、サーバＰ1〜Ｐnの中で資源を割当てられている識別情報ｉのサーバが有する資源割当装置１２は、資源使用時間が確定されていてｉ′Ｔ＝ｉとなっているメッセージ（（ｐ′，ｗ′，ｉ′t），（Ｔ′，ｉ′Ｔ），ｉ′0）をメッセージ受信装置１により受信したら割当処理を起動して資源を解放したサーバと同様の割当処理を行う手段を備える（請求項１０）。
【００８８】
また、資源割当装置１２は、資源割当要求が生成された時点で、自身の資源使用時間が前記メッセージが前記論理リングを１周する時間に相当する資源使用時間よりも小さければ、割当処理を起動せずに、無条件に自身にその資源を割り当てる手段を備える（請求項１１）。
【００８９】
あるいは、サーバＰ1〜Ｐnの中で資源使用時間が０のサーバが有する資源割当装置１２は、資源割当要求を含んだメッセージを受信したときには、前記割当処理に沿った動作をせず、すぐに自身にその資源を割り当てる手段を備える（請求項１２）。
【００９０】
なお、本実施例では、説明をわかりやすくするために、様々な状況下にあるサーバを説明し、これらのサーバが有するタスク割当装置２あるいは資源割当装置１２はそれぞれ異なる機能を有しているかのような説明を行ったが、実際には、全てのサーバが同じ機能を有し、当該サーバが置かれた状況に応じて必要な機能を発揮するものである。
【００９１】
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のタスク割当装置または資源割当装置に相応する機能を実現させるプログラムとして実現することができる（請求項１３〜１８）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項１９）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、メッセージ受信装置１、タスク割当装置２、タスク処理装置３、メッセージ送信装置４、内部状態保持装置５、タスク完了見込み推定装置６、負荷量計測装置７、資源割当装置１２、資源運用装置１３、資源解放見込み推定装置１６、資源使用時間計測装置１７にそれぞれ相応する機能を実現させることができる。
【産業上の利用可能性】
【００９２】
本発明により、従来のタスク割当手法の生成時刻順実行という性質を保証した上で、従来法で問題になっていた通信量を削減することが期待できる。これにより、通信量が多いために阻害されていた効率も向上することが期待できる。したがって、サーバに対するタスク割当または資源割当を効率的に行うことができため、ネットワークユーザあるいはネットワーク管理者の利便性を向上させることができる。
【図面の簡単な説明】
【００９３】
【図１】単方向リングネットワークを示す図。
【図２】タスク割当装置のブロック構成図。
【図３】本実施例の資源割当装置のブロック構成図。
【図４】実行例の最初の状態を示す図。
【図５】徐行例の最初の内部状態を示す図。
【図６】実行例の途中経過（メッセージの状況）を示す図。
【図７】実行例の途中経過（内部状態）を示す図。
【図８】実行例の途中経過（メッセージの状況）を示す図。
【図９】実行例の途中経過（内部状態）を示す図。
【図１０】実行例の途中経過（メッセージの状況）を示す図。
【図１１】実行例の途中経過（内部状態）を示す図。
【図１２】実行例の途中経過（メッセージの状況）を示す図。
【図１３】実行例の途中経過（内部状態）を示す図。
【図１４】実行例の途中経過（メッセージの状況）を示す図。
【図１５】実行例の途中経過（内部状態）を示す図。
【図１６】実行例の途中経過（メッセージの状況）を示す図。
【図１７】実行例の途中経過（内部状態）を示す図。
【図１８】実行例の途中経過（最終状態）を示す図。
【図１９】本実施例のタスク割当手順を示すフローチャート。
【図２０】本実施例のタスク割当手順を示すフローチャート。
【図２１】本実施例のタスク割当手順を示すフローチャート。
【符号の説明】
【００９４】
１  メッセージ受信装置
２  タスク割当装置
３  タスク処理装置
４  メッセージ送信装置
５  内部状態保持装置
６  タスク完了見込み推定装置
７  負荷量計測装置
１２  資源割当装置
１３  資源運用装置
１６  資源解放見込み推定装置
１７  資源使用時間計測装置
Ｐ1〜Ｐn  サーバ
【図１】
2005190133.tif 000003
【図２】
2005190133.tif 000004
【図３】
2005190133.tif 000005
【図４】
2005190133.tif 000006
【図５】
2005190133.tif 000007
【図６】
2005190133.tif 000008
【図７】
2005190133.tif 000009
【図８】
2005190133.tif 000010
【図９】
2005190133.tif 000011
【図１０】
2005190133.tif 000012
【図１１】
2005190133.tif 000013
【図１２】
2005190133.tif 000014
【図１３】
2005190133.tif 000015
【図１４】
2005190133.tif 000016
【図１５】
2005190133.tif 000017
【図１６】
2005190133.tif 000018
【図１７】
2005190133.tif 000019
【図１８】
2005190133.tif 000020
【図１９】
2005190133.tif 000021
【図２０】
2005190133.tif 000022
【図２１】
2005190133.tif 000023