(57)【要約】【課題】処理装置に余計な処理をさせることなく、実態に即した処理負荷の低い処理装置を選択してこの処理装置に処理データを配分する。【解決手段】判定手段２６が、ある処理装置に対応する、複数の数値のうちの１つと、蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であるか否かを判定する。配分手段２２が、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であると判定された場合に、処理装置に処理データを配分する。実行手段２６が、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して検出処理及び判定処理を実行させる。【選択図】    図２
2004355227.tif 000002
【特許請求の範囲】
【請求項１】
処理データを入力する入力手段と、
前記処理データを配分することが可能な複数の処理装置を識別する識別手段と、
前記処理装置の数に基づいて、前記処理データを配分すべき処理装置を決定するための複数の数値を算出する算出手段と、
前記処理装置のうちのある処理装置の処理負荷を検出する検出処理を実行する検出手段と、
前記検出処理によって検出された処理負荷を蓄積してゆく蓄積手段と、
前記ある処理装置に対応する、前記複数の数値のうちの１つと、前記蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が前記処理データを配分すべき処理装置であるか否かを判定する判定処理を実行する判定手段と、
最も近い過去に蓄積した処理負荷に対応する前記処理装置が前記処理データを配分すべき処理装置であると判定された場合に、該処理装置に前記処理データを配分する配分手段と、
最も近い過去に蓄積した処理負荷に対応する前記処理装置が前記処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して前記検出処理及び前記判定処理を実行させる実行手段を具備することを特徴とする負荷分配装置。
【請求項２】
前記複数の数値の各数値は、処理負荷を検出する順番に対応していて、検出された複数の処理負荷のうちで処理負荷の値が小さい順に付与される順位と比較されることを特徴とする請求項１に記載の負荷分配装置。
【請求項３】
前記判定手段は、処理負荷の小さい順でのある処理装置の順位が前記比較される順位と同一又は該順位より上位である場合に、該処理装置に前記処理データを配分することに決定することを特徴とする請求項２に記載の負荷分配装置。
【請求項４】
前記検出手段は、前記配分手段が前記処理装置に前記処理データを配分した後、前記複数の処理装置のうち、前記処理データを配分するために判定処理された処理装置に続く処理装置の処理負荷を検出することを特徴とする請求項１から請求項３のいずれかに記載の負荷分配装置。
【請求項５】
処理データを入力し、
前記処理データを配分することが可能な複数の処理装置を識別し、
前記処理装置の数に基づいて、前記処理データを配分すべき処理装置を決定するための複数の数値を算出し、
前記処理装置のうちのある処理装置の処理負荷を検出する検出処理を実行し、
前記検出処理によって検出された処理負荷を蓄積し、
前記ある処理装置に対応する、前記複数の数値のうちの１つと、前記蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が前記処理データを配分すべき処理装置であるか否かを判定する判定処理を実行し、
最も近い過去に蓄積した処理負荷に対応する前記処理装置が前記処理データを配分すべき処理装置であると判定された場合に、該処理装置に前記処理データを配分し、
最も近い過去に蓄積した処理負荷に対応する前記処理装置が前記処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して前記検出処理及び前記判定処理を実行させることを特徴とする負荷配分方法。
【請求項６】
前記複数の数値の各数値は、処理負荷を検出する順番に対応していて、検出された複数の処理負荷のうちで処理負荷の値が小さい順に付与される順位と比較されることを特徴とする請求項５に記載の負荷配分方法。
【請求項７】
前記判定処理は、処理負荷の小さい順でのある処理装置の順位が前記比較される順位と同一又は該順位より上位である場合に、該処理装置に前記処理データを配分することに決定することを特徴とする請求項６に記載の負荷配分方法。
【請求項８】
前記検出処理は、前記処理装置に前記処理データを配分した後、前記複数の処理装置のうち、前記処理データを配分するために判定処理された処理装置以外のある処理装置の処理負荷を検出することを特徴とする請求項５から請求項７のいずれかに記載の負荷配分方法。
【請求項９】
コンピュータを、
処理データを入力する入力手段と、
前記処理データを配分することが可能な複数の処理装置を識別する識別手段と、
前記処理装置の数に基づいて、前記処理データを配分すべき処理装置を決定するための複数の数値を算出する算出手段と、
前記処理装置のうちのある処理装置の処理負荷を検出する検出処理を実行する検出手段と、
前記検出処理によって検出された処理負荷を蓄積してゆく蓄積手段と、
前記ある処理装置に対応する、前記複数の数値のうちの１つと、前記蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が前記処理データを配分すべき処理装置であるか否かを判定する判定処理を実行する判定手段と、
最も近い過去に蓄積した処理負荷に対応する前記処理装置が前記処理データを配分すべき処理装置であると判定された場合に、該処理装置に前記処理データを配分する配分手段と、
最も近い過去に蓄積した処理負荷に対応する前記処理装置が前記処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して前記検出処理及び前記判定処理を実行させる実行手段として機能させるための負荷配分プログラム。
【請求項１０】
前記複数の数値の各数値は、処理負荷を検出する順番に対応していて、検出された複数の処理負荷のうちで処理負荷の値が小さい順に付与される順位と比較されることを特徴とする請求項９に記載の負荷配分プログラム。
【請求項１１】
前記判定手段は、処理負荷の小さい順でのある処理装置の順位が前記比較される順位と同一又は該順位より上位である場合に、該処理装置に前記処理データを配分することに決定することを特徴とする請求項１０に記載の負荷配分プログラム。
【請求項１２】
前記検出手段は、前記配分手段が前記処理装置に前記処理データを配分した後、前記複数の処理装置のうち、前記処理データを配分するために判定処理された処理装置以外のある処理装置の処理負荷を検出することを特徴とする請求項９から請求項１１のいずれかに記載の負荷配分プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、処理データを生成する負荷発生装置から受け取った処理データを複数の処理装置に配分するための負荷配分装置、負荷配分方法、及び負荷配分プログラムに関するものである。
【０００２】
【従来の技術】
従来、処理データを生成する負荷発生装置から受け取った処理データを複数の処理装置に配分するための負荷配分装置としては以下に示す３種類が典型的である。
【０００３】
１．負荷発生装置から受け取る処理データを処理するために必要とする処理量は一定であると仮定して、各処理装置に順番に処理データを配分する負荷配分装置（例えば、非特許文献１参照）。
【０００４】
２．上記１を性能の異なる処理装置に対して実行するために、各処理装置に一定の重み付けを行い、重みの比率に従って各処理装置に順番に処理データを配分する負荷配分装置（例えば、非特許文献２参照）。
【０００５】
３．各処理装置の処理負荷を示す負荷データを各処理装置から取得し、その処理負荷を数値化して処理負荷の低い処理装置に処理データを配分する負荷配分装置（例えば、非特許文献３参照）。
【０００６】
【非特許文献１】
Ｆ５  Ｎｅｔｗｏｒｋｓ，  ”ＢＩＧ−ＩＰ（登録商標）Ｃｏｎｔｒｏｌｌｅｒ  Ｒｅｆｅｒｅｎｃｅ  Ｇｕｉｄｅ”，  ｖｅｒｓｉｏｎ  ３．３，  Ｆ５  Ｎｅｔｗｏｒｋｓ，  ｐ．  １−４６
【０００７】
【非特許文献２】
Ｆ５  Ｎｅｔｗｏｒｋｓ，  ”ＢＩＧ−ＩＰ（登録商標）Ｃｏｎｔｒｏｌｌｅｒ  Ｒｅｆｅｒｅｎｃｅ  Ｇｕｉｄｅ”，  ｖｅｒｓｉｏｎ  ３．３，  Ｆ５  Ｎｅｔｗｏｒｋｓ，  ｐ．  １−４７
【０００８】
【非特許文献３】
Ｆ５  Ｎｅｔｗｏｒｋｓ，  ”ＢＩＧ−ＩＰ（登録商標）Ｃｏｎｔｒｏｌｌｅｒ  Ｒｅｆｅｒｅｎｃｅ  Ｇｕｉｄｅ”，  ｖｅｒｓｉｏｎ  ３．３，  Ｆ５  Ｎｅｔｗｏｒｋｓ，  ｐｐ．  １−４７，  １−４８
【０００９】
【発明が解決しようとする課題】
上記１又は２のように、各処理装置に順番に処理データを配分する負荷配分装置では、各処理装置の性能が同一であって、配分される各処理データの内容が均等で、かつ、各処理時間が一定であれば各処理装置の処理負荷は同一になる。しかし、ほとんどの場合、処理データの内容は各処理データ間で少しずつ異なっており、順番に処理データを配分してゆくと処理装置の負荷が不均等になってしまう。
また、負荷配分装置によって選択された処理装置が配分された処理データの処理をいったん滞らせると、この処理データの処理が終わらないうちに、後続の処理データが次々と配分されてしまう。その結果、その処理装置はますます処理を滞らせてしまうという悪循環に陥ってしまう。
【００１０】
上記３のように、処理負荷の低い処理装置に処理データを配分する負荷配分装置では、処理装置が処理を滞らせてしまうことは避けられる。しかし、負荷配分装置が処理装置から負荷データを取得する動作が処理装置に一定の負担を与えてしまい、処理装置全体が単位時間に処理することが可能な処理データ量が少なくなってしまう。すなわち、処理装置全体のパフォーマンスが低下してしまう。
【００１１】
また、処理装置が多数であればあるほど、それらの処理装置を対象として処理データを配分しようとした場合に、負荷配分装置は全ての処理装置の負荷データを取得しなければ処理データを配分する処理装置を決定することができない。多数の処理装置から負荷データを取得する必要があるため、負荷配分装置が取得する負荷データの取得間隔が長くなってしまう。負荷データの取得間隔が長くなると、負荷配分装置が処理データを配分する時点で、収集した負荷データが既に各処理装置の処理負荷の実情を反映しないものになる可能性が高くなってしまう。負荷配分装置がこれらの負荷データを使用すると、各処理処置への処理データの配分が均等でなくなる可能性が高くなる。
換言すれば、全ての処理装置の負荷を同時に知ることはできないため、処理装置によって取得時間の異なる各処理装置の処理負荷を、仮想的な時刻における処理負荷と仮定して処理データを配分する処理装置の選択基準としなければならず、実情に合っていない場合が多い。その結果として、各処理処置への処理データの配分が均等でなくなる可能性が高くなる。
【００１２】
本発明は、上述した従来の技術に鑑み、処理装置に余計な処理をさせることなく、実態に即した処理負荷の低い処理装置を選択してこの処理装置に処理データを配分するための負荷配分装置、負荷配分方法、及び負荷配分プログラムを提供することを目的とする。
【００１３】
【課題を解決するための手段】
本発明の負荷配分装置は、処理データを入力する入力手段と、処理データを配分することが可能な複数の処理装置を識別する識別手段と、処理装置の数に基づいて、処理データを配分すべき処理装置を決定するための複数の数値を算出する算出手段と、処理装置のうちのある処理装置の処理負荷を検出する検出処理を実行する検出手段と、検出処理によって検出された処理負荷を蓄積してゆく蓄積手段と、ある処理装置に対応する、複数の数値のうちの１つと、蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であるか否かを判定する判定処理を実行する判定手段と、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であると判定された場合に、処理装置に処理データを配分する配分手段と、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して検出処理及び判定処理を実行させる実行手段を備えている。
【００１４】
本発明の負荷配分方法は、処理データを入力し、処理データを配分することが可能な複数の処理装置を識別し、処理装置の数に基づいて、処理データを配分すべき処理装置を決定するための複数の数値を算出し、処理装置のうちのある処理装置の処理負荷を検出する検出処理を実行し、検出処理によって検出された処理負荷を蓄積し、ある処理装置に対応する、複数の数値のうちの１つと、蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であるか否かを判定する判定処理を実行し、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であると判定された場合に、処理装置に処理データを配分し、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して検出処理及び判定処理を実行させるものである。
【００１５】
本発明の負荷配分プログラムは、コンピュータを、処理データを入力する入力手段と、処理データを配分することが可能な複数の処理装置を識別する識別手段と、処理装置の数に基づいて、処理データを配分すべき処理装置を決定するための複数の数値を算出する算出手段と、処理装置のうちのある処理装置の処理負荷を検出する検出処理を実行する検出手段と、検出処理によって検出された処理負荷を蓄積してゆく蓄積手段と、ある処理装置に対応する、複数の数値のうちの１つと、蓄積されている複数の処理負荷に基づいて、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であるか否かを判定する判定処理を実行する判定手段と、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置であると判定された場合に、処理装置に処理データを配分する配分手段と、最も近い過去に蓄積した処理負荷に対応する処理装置が処理データを配分すべき処理装置でないと判定された場合に、他のある処理装置に関して検出処理及び判定処理を実行させる実行手段として機能させるためのものである。
【００１６】
以上によれば、処理負荷を検出する処理装置を限定するので、ほとんどの処理装置に余計な処理をさせることがなくなる。また、処理装置に処理データを配分するときは、この処理装置の処理負荷を検出した直後に配分するので、実態に即した処理負荷の低い処理装置を選択してこの処理装置に処理データを配分することが可能になる。
【００１７】
【発明の実施の形態】
以下、図面を参照しながら本発明の実施形態に係る負荷配分装置、負荷配分方法、及び負荷配分プログラムを説明する。
【００１８】
図１は、本発明の実施形態に係る負荷配分装置２０を含むシステム例を示す図である。
本実施形態に係る負荷配分装置２０を含むシステムは、例えば、図１に示すように、複数の負荷発生装置１０、１つの負荷配分装置２０、及び、複数の処理装置３０を備えている。
【００１９】
各負荷発生装置１０は、ある処理データを生成する。各負荷発生装置１０は、その処理データを負荷配分装置２０にそれぞれ出力する。それらの処理データの内容は様々であり、負荷配分装置２０に出力される時刻も一般に一様ではない。
負荷配分装置２０は、複数の負荷発生装置１０から処理データを入力する。負荷配分装置２０は、複数の処理装置３０から順に処理装置の処理負荷を示している負荷データを入力する。この負荷データに基づいて、負荷配分装置２０はある処理装置を選択し、この処理装置に、入力した処理データを配分する。
処理装置３０は、負荷配分装置２０に負荷データを出力する。その後、負荷配分装置２０から処理データが出力されてきた場合に、その処理データを処理する。
【００２０】
図２は、図１の負荷配分装置のブロック図である。
処理データ入力部２１は、各負荷発生装置１０から処理データを入力する。処理データ配分部２２は、後述の判定部２６が判定した判定結果に基づいて、処理データ入力部２１から入力した処理データをある処理装置３０に配分する。
処理装置識別部２３は、処理データを処理することが可能な処理装置３０を把握するために、処理装置３０を識別する。処理装置識別部２３は、複数の処理装置３０に対して処理データを処理することが可能であるか否かを確認するために確認信号を送信し、応答があった各処理装置３０に対応して何らかの識別名称を付与する。すなわち、負荷配分装置２０内で応答があった各処理装置３０が一意的に定まるように名称が付与される。例えば、処理装置識別部２３は、応答があった各処理装置３０に対応して番号を付与する。この結果、処理装置識別部２３は、処理データを処理することが可能な処理装置数を把握することができる。
【００２１】
負荷検出部２４は、処理装置識別部２３が識別した処理装置３０からある処理装置３０を選択し、この処理装置３０の負荷データを負荷配分装置２０に出力するように処理装置３０に指示信号を出力する。この指示信号を出力する処理装置３０をどのように選択するかは後述される。
【００２２】
選択決断順位算出部２５は、処理装置識別部２３から処理データを処理することが可能な処理装置数を入力し、この処理装置数に基づいて、処理装置数分（正確には処理装置数−１の個数）の選択決断順位を算出する。選択決断順位とは、この選択決断順位に対応する処理装置３０に処理データを処理するように指示するか否かを判定するための閾値である（詳細は、後に図３を参照して説明する）。換言すれば、第ｉ番目（１≦ｉ≦Ｎ−１）に負荷検出部２４によって選択された処理装置３０の、最初のｉ個の処理装置の中での相対順位が第ｉ番目の選択決断順位より下位である場合はこの処理装置３０に処理データを処理させず、一方、最初のｉ個の処理装置の中での処理装置３０の相対順位が第ｉ番目の選択決断順位と同一又はその選択決断順位よりも上位である場合はこの処理装置３０に処理データを処理させる。これは判定部２６が実行する処理である。
ここで、第ｉ番目に負荷検出部２４によって選択された処理装置３０の、最初のｉ個の処理装置の中での相対順位とは、第ｉ番目までに負荷検出部２４によって選択された処理装置３０の処理負荷の小さい順の順位がｓ１、・・・、ｓｉであるとすると、ｓ１、・・・、ｓｉのうちのｓｉと同一又はその順位よりも上位である処理装置３０の個数のことである。
【００２３】
メモリ２７は、処理装置識別部２３が識別した処理装置数を記憶している。また、メモリ２７は、処理装置識別部２３が識別した処理装置３０のうち、負荷検出部２４が検出した処理装置３０の処理負荷を、検出した処理装置３０ごとに記憶している。
【００２４】
判定部２６は、処理装置識別部２３から付与された識別名称の一覧を入力する。また、判定部２６は、負荷検出部２４から負荷データを負荷配分装置２０に出力するように指示された処理装置３０の負荷データを入力する。さらに、判定部２６は、選択決断順位算出部２５から処理装置数分の選択決断順位を入力する。判定部２６は、メモリ２７を参照して、判定部２６が今回入力した負荷データを出力した処理装置３０が第何番目に負荷データを出力したものかを確認する。判定部２６は、この順番に対応する選択決断順位を探し出し、その選択決断順位と、判定部２６が今回入力した負荷データが示す処理負荷が前回までに取得したメモリに記憶されている処理負荷で決まる相対順位と比較される。
すなわち、今回、負荷検出部２４によって選択された処理装置３０であって、メモリ２７に記憶されている処理装置３０の中での相対順位が対応する選択決断順位より下位である場合はこの処理装置３０に処理データを処理させず、一方、メモリ２７に記憶されている処理装置の中での処理装置３０の相対順位が対応する選択決断順位と同一又はその選択決断順位よりも上位である場合はこの処理装置３０に処理データを処理させる。
【００２５】
図３は、図１の選択決断順位算出部で利用される数式及びテーブルを示す図である。図２の選択決断順位算出部２５が選択決断順位を算出する計算手順を示す。
本実施形態の負荷配分装置２０は、Ｎ個の処理装置３０がある場合に、この処理装置３０の処理負荷を順番に調査して、小さい処理負荷の処理装置３０を効率よく発見するためのアルゴリズムを備えるものである。ここで、小さい処理負荷の処理装置３０を決定するときは、処理負荷を調査したその時のものとする。すなわち、処理装置３０の処理負荷は時々刻々と変化しているので、以前に調査した処理装置を選択することはしない。例えば、第５回目に処理装置３０の処理負荷を調査したとする。このとき、第５回目の処理装置３０の処理負荷よりも第２回目の処理装置３０の処理負荷が小さいとしても、もはや第２回目の処理装置を「小さい処理負荷の処理装置」と決定することはしない。
さらに、処理装置３０は、処理負荷が小さいものから順に、１位からＮ位までの順位付けが可能であり、その並び方はＮ！通りの順列が等確率で現れるものと仮定する。以上の条件の下で、より小さい処理負荷の処理装置３０を選択する順位の期待値を最小、すなわち、より小さい処理負荷の処理装置３０を選択するためのアルゴリズムが本実施形態には必要となる。
【００２６】
このアルゴリズムは、Ｃｈｏｗ，  Ｍｏｒｉｇｕｔｉ，  Ｒｏｂｂｉｎｓ，  ａｎｄ  Ｓａｍｕｅｌｓ，  “Ｏｐｔｉｍａｌ  ｓｅｌｅｃｔｉｏｎ  ｂａｓｅｄ  ｏｎ  ｒｅｌａｔｉｖｅ  ｒａｎｋ”，  Ｉｓｒａｅｌ  Ｊ．  ｏｆ  Ｍａｔｈ．，  ｖｏＬ２  （１９６４），  ｐｐ．  ８１−９０、又は、「海辺の美女の問題」、森口繁一、日本評論社、“数学セミナー増刊数学１００の問題”、１９８４年９月２５日発行、ｐｐ．３９によれば、以下のように定式化される。
選択決断順位算出部２５は、処理装置識別部２３から処理データを処理することが可能な処理装置数Ｎを入力する。このＮによって定まる数列｛ｓ（１），ｓ（２），・・・ｓ（ｉ）｝があり、第ｉ番目の処理装置３０の相対順位ｙ（ｉ）がｓ（ｉ）よりも大きい場合はｉを１だけ増加させて次の処理装置３０に進み、一方、ｙ（ｉ）がｓ（ｉ）以下である場合はその第ｉ番目の処理装置３０が「小さい処理負荷の処理装置」であると見なす。この手順を最初の処理装置３０であるｉ＝１から、最後の処理装置３０の直前の処理装置３０であるｉ＝Ｎ−１まで行う。ｉ＝Ｎ−１まで処理データを配分する処理装置３０が決定しない場合は、最後の処理装置３０であるＮ番目の処理装置３０に処理データを配分する。
このとき第ｉ番目までに「小さい処理負荷の処理装置」であると見なすことのできる処理装置３０がなかったという条件の下での順位の期待値ｃ（ｉ）とすると、ｃ（ｉ）及びｓ（ｉ）は図３に示したように定式化される。ここで［ｘ］の括弧はガウス記号を示し、［ｘ］は実数ｘを超えない最大の整数を示す。また、図３で順位の期待値ｃ（ｉ−１）では、ｉ＝Ｎ−１，・・・，２であり、選択決断順位ｓ（ｉ）では、ｉ＝Ｎ−１，・・・，２，１である。
【００２７】
選択決断順位算出部２５が入力した処理装置数Ｎにより、最終期待順位ｃ（Ｎ−１）が決定する。図３の選択決断順位ｓ（ｉ）の数式よりｃ（ｉ）が決定するとｓ（ｉ）が決定するので、ｃ（Ｎ−１）が決定するとｓ（Ｎ−１）が決定する。図３の順位の期待値の数式ｃ（ｉ−１）によりｃ（ｉ）及びｓ（ｉ）が決定すれば、ｃ（ｉ−１）が決定する。この様に、ｃ（Ｎ−１）、ｓ（Ｎ−１）、ｃ（Ｎ−２）、ｓ（Ｎ−２）、・・・、ｃ（１）、ｓ（１）の順で全ての選択決断順位ｓ（ｊ）（１≦ｊ≦Ｎ−１）が算出される。
【００２８】
図４は、図１の処理装置３０の数が１０である場合の計算例を示す図である。図４は、具体的な例であり、Ｎ＝１０の場合である。図４の左に示したテーブルは、図３に示した数式によりＮ＝１０の場合に算出した順位の期待値ｃ（ｉ）及び選択決断順位ｓ（ｉ）（１≦ｉ≦９）を示す。この場合テーブルの左端に示したｉ（ｉ＝１，・・・，９）は各処理装置３０に付与された識別番号である。図４の右に示したフローは判定部２６で実行される。
第１から第３の処理装置３０は選択決断順位が０であるので、これらの処理装置３０は選択されない。ここでは、第１から第３の処理装置３０の各処理負荷がメモリ２７に記憶されるだけである（ステップＳ１）。
【００２９】
第４及び第５の処理装置３０は選択決断順位が１であるので、それまでに調査した処理負荷の中で１番低い場合は、その処理装置３０が選択される（ステップＳ２）。例えば、第４の処理装置３０の相対順位が２で、かつ第５の処理装置３０の相対順位が１である場合は、第５の処理装置３０が選択される。一方、それまでに調査した処理負荷の中で１番低くない場合は、第４及び第５の処理装置３０の各処理負荷がメモリ２７に記憶される。
【００３０】
第６及び第７の処理装置３０は選択決断順位が２であるので、それまでに調査した処理負荷の中で１番低いか、又は２番目に低い場合は、その処理装置３０が選択される（ステップＳ３）。例えば、第６の処理装置３０の相対順位が４で、かつ第７の処理装置３０の相対順位が２である場合は、第７の処理装置３０が選択される。一方、それまでに調査した処理負荷の中で２番以内に低くない場合は、第６及び第７の処理装置３０の各処理負荷がメモリ２７に記憶される。
【００３１】
第８の処理装置３０は選択決断順位が３であるので、それまでに調査した処理負荷の中で３番目以内に低い場合は、第８の処理装置３０が選択される（ステップＳ４）。例えば、第８の処理装置３０の相対順位が２である場合は、第８の処理装置３０が選択される。一方、それまでに調査した処理負荷の中で３番以内に低くない場合は、第８の処理装置３０の処理負荷がメモリ２７に記憶される。
【００３２】
第９の処理装置３０は選択決断順位が５であるので、それまでに調査した処理負荷の中で５番目以内に低い場合は、第９の処理装置３０が選択される（ステップＳ５）。例えば、第９の処理装置３０の相対順位が４である場合は、第９の処理装置３０が選択される。一方、それまでに調査した処理負荷の中で５番以内に低くない場合は、次のステップで選択される処理装置３０は１つしかないので、第９の処理装置３０の処理装置に関する処理負荷をメモリ２７に記憶することはしない。
【００３３】
上記のステップＳ１から上記のステップＳ５までで選択すべき処理装置３０が決定されない場合は、残りは１つの処理装置３０しか選択する余地はないので処理負荷を調査することなく、第１０の処理装置３０が選択される（ステップＳ６）。
【００３４】
以上に示したように、本実施形態の負荷配分装置２０は、従来全ての処理装置３０にわたって負荷状況を取得しなければ処理の配分が行えなかったものを、上述したアルゴリズムを用いることで、負荷データを取得する処理装置３０の数を減らしながらも負荷の低い処理装置３０に処理データを配分することが可能になる。
また、図４に示した例では、最初の処理装置３０の順位の期待値は２．５５７９であるので、平均して約３位の処理負荷を有する処理装置３０を選択することになる。
また、メモリ２７に記憶された処理負荷は、処理データを配分する処理装置３０が選択された時点でメモリ２７から消去される。
【００３５】
本実施形態の負荷配分装置２０は、全ての処理装置３０について処理負荷を取得することは稀であり、確率的に処理負荷を示している負荷データを取得する処理を少なくすることができる。したがって、処理装置３０は、負荷データに関する処理の負担を受けることが少なくなり、処理装置３０は本来の処理に能力を集中することができる。
【００３６】
また、過去に取得した処理装置３０の負荷データは、負荷配分装置２０が各処理装置３０の負荷データを取得した時系列において各処理装置３０に相対的な順位を定める目的のみに利用される。さらに、本実施形態の負荷配分装置２０は、処理データを配分する処理装置３０を決定するとき、決定する直前に負荷データを取得した処理装置３０を選択するため、選択された処理装置３０の負荷データは実態に即している。その結果、負荷配分装置２０は、最適な処理装置３０に負荷データを配分する確率を高くすることが可能になる。
【００３７】
図５は、図４の場合の処理装置３０を決定する様子を示す図である。図６は、図４の場合の処理装置３０を決定する、図５とは別の例の様子を示す図である。図５は、上述したアルゴリズムをそのまま用いた、単純な例である。この場合は、処理装置識別部２３が負荷データを配分する処理装置３０に１からＮまでの固定的な番号を付ける。図５の例では、Ｎ＝１０である。まず、１回目に処理データを配分する処理装置３０を決定する。処理データ入力部２１に処理データが入力されると、まず、負荷検出部２４は番号１の処理装置３０から処理負荷を調査する。以後、上述したアルゴリズムにしたがい、負荷検出部２４が番号ｉ（ｉは２から始まる）の処理装置３０の処理負荷を調査する。判定部２６がその処理装置３０の処理負荷に対する相対順位と選択決断順位ｓ（ｉ）を比較する。その処理装置３０の処理負荷に対する相対順位が選択決断順位ｓ（ｉ）と同一又はｓ（ｉ）よりも上位である場合は、処理データ配分部２２が番号ｉの処理装置に処理を配分し、一方、相対順位が選択決断順位ｓ（ｉ）よりも下位である場合はｉを１増やして負荷検出部２４が番号ｉ＋１の処理装置３０の処理負荷を調査して、判定部２６が選択決断順位ｓ（ｉ＋１）と順位を比較する。
【００３８】
２回目に処理データを配分する処理装置３０を決定する際に、図５の例では、再び番号１の処理装置３０から処理負荷を調査しはじめる。以下の手順は上述した１回目の場合と同様である。図５の例では、２回目以降の全ての場合において、処理データを配分する処理装置３０を決定する際に、常に、番号１の処理装置３０から処理負荷を調査しはじめる。
【００３９】
常に、番号１の処理装置３０から処理負荷を調査しはじめると、最初の約４分の１の処理装置は処理負荷を調査されるだけで処理データを配分されることがない。図５の例ではＮ＝１０だから、番号１、番号２、及び番号３の処理装置３０は処理データが配分されることはない。したがって、図５の例では、処理を配分されることが全くない処理装置３０が存在し、それらよりも大きな番号が付与されている処理装置３０にのみ処理データが配分されることになり、全ての処理装置３０において処理負荷が偏ってしまう。
【００４０】
図６の例では、処理データを選択された処理装置３０に配分した後に、毎回、番号１の処理装置３０から開始していた処理装置３０の負荷調査を、前回処理データを配分した処理装置３０に続く次の処理装置３０から開始する。例えば、図６に示したように１回目に番号４の処理装置３０が選択された場合は、２回目に処理データを配分する処理装置３０を決定する際は、１回目に選択された番号４の次の番号である番号５の処理装置３０から処理負荷の調査を開始する。
【００４１】
２回目以降に処理負荷の調査を開始する直前に、処理装置識別部２３が、前回に選択された処理装置３０の次の処理装置３０から番号を１から順に付与して、負荷検出部２４は、常に番号１の処理装置３０から各処理装置３０の処理負荷を調査する。
また、各処理装置３０に付与されている番号は固定のままにしておき、前回に選択された処理装置３０の番号をメモリ２７に記憶しておいてもよい。そして、今回の処理負荷の調査する際は、メモリ２７に記憶されている前回に選択された処理装置３０の番号が参照されて、その番号＋１の番号が付与されている処理装置３０から処理負荷が調査されてもよい。以後は、図５を参照して説明したように相対順位と選択決断順位を比較して、処理データを配分する処理装置３０を決定する。
【００４２】
このように前回選択された処理装置３０の次の処理装置３０から処理負荷を調査しはじめると、図５の例では存在した、処理負荷を調査されるだけで処理データを配分されることがない処理装置３０はなくなると期待される。その結果、図６を参照して説明した手順によって処理装置３０を選択すれば、処理負荷を調査する対象を処理装置３０全体にすることが可能になる。したがって、処理データを配分する回数が増えるにしたがい、全ての処理装置３０において処理負荷が均一に近づくと期待することができる。
また、処理データを選択された処理装置３０に配分した後に、前回処理データを配分した処理装置３０とは無関係に、ランダムに処理装置３０を選択し、選択されたこの処理装置３０の処理負荷を調査してもよい。すなわち、処理負荷を調査する処理装置３０はランダムに毎回選択してもよい。処理装置３０の処理負荷をランダムに調査することは、図６に示した例と同様な効果を奏する。
【００４３】
以上に述べたように、本実施形態の負荷配分装置２０によれば、ほとんどの場合、選択決断順位が、最初の処理装置３０の順位の期待値を超えた時点で処理負荷を配分する処理装置３０を決定できる。例えば、図４では、最初の処理装置３０の順位の期待値は２．５５７９であり、選択決断順位がこの値を超えるのは識別名称が番号８の処理装置３０を選択した場合である。図４の例では処理装置３０がＮ＝１０と少ないため効果が明確ではないが、Ｎが１０００のオーダーになると、選択決断順位が、最初の処理装置３０の順位の期待値を超えるのは識別名称が番号約５００の処理装置３０を選択した場合になることを上記に示したアルゴリズムによって示すことができる。
したがって、本実施形態の負荷配分装置２０によれば、負荷を調べる処理装置数を約半分に減らすことができる。逆に、処理装置３０に対する処理負荷調査の負担が同じ場合、約２倍の頻度で処理負荷を調べることができ、処理装置３０の処理負荷をより正確に知ることができる。
【００４４】
図７は、図２の負荷配分装置が２つある場合のシステム例を示す図である。図７を参照して、負荷配分装置が複数ある場合の特徴を説明する。
従来の、例えば全ての処理装置３０の処理負荷を調査して処理データを配分する処理装置３０を選択する方法では、負荷配分装置２０が最初に全ての処理装置３０の処理負荷を調査する。そして、負荷配分装置２０が最も処理負荷が小さい処理装置３０を選択して、処理データを配分する。次に、負荷配分装置２０が２番目に処理負荷の小さい処理装置３０を第２の負荷配分装置４０に通知して、負荷配分装置４０がその２番目に処理負荷の小さい処理装置３０を選択して、処理データを配分する。
【００４５】
本実施形態の負荷配分装置２０の実行するアルゴリズムは、全ての処理負荷を調べる必要がなく、確率論的に処理装置３０は選択されるので、上述したように、負荷配分装置２０と負荷配分装置４０との間で処理データの配分方法を調整する必要はない。ただし、調査を開始する処理装置３０は負荷配分装置２０と負荷配分装置４０とで異なるように設定することが望ましい。このように設定しておけば、負荷配分装置２０と負荷配分装置４０が同一の処理装置３０を選択して１つの処理装置３０にのみ処理負荷が莫大にかかってしまうということはほとんど発生しないと期待することができる。
【００４６】
したがって、本実施形態の負荷配分装置２０では、複数の負荷配分装置があったとしても、それらの負荷配分装置間は互いの負荷配分装置とはほとんど無関係に各処理装置３０の処理負荷を計測し、効率的に処理データを配分することができる。図７のように負荷配分装置が複数存在していても、負荷配分装置間でほぼ完全に独立して処理を配分することができる。
【００４７】
負荷配分装置のこの特徴により、負荷配分装置自体の処理能力が不足した場合でも、単純に負荷配分装置を増設するだけで、負荷配分装置の数にほぼ比例した負荷配分の能力を発揮させることが可能になる。
【００４８】
また、負荷配分装置が複数ある場合でも、負荷配分装置間で独立して処理負荷の調査と処理データを配分する処理装置３０の決定を行うことができるため、負荷配分装置間での調整に負担をかける必要がなくなる。
【００４９】
また、上述の実施形態の中で示した手順に示された指示、及び流れ図の各ステップに示された指示は、ソフトウェアであるプログラムに基づいて実行されることが可能である。汎用の計算機システムが、このプログラムを予め記憶しておき、このプログラムを読み込むことにより、上述した実施形態の負荷配分装置による効果と同様な効果を得ることも可能である。上述の実施形態で記述された指示は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フレキシブルディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤなど）、半導体メモリ、又はこれに類する記録媒体に記録される。コンピュータは、この記録媒体からプログラムを読み込み、このプログラムに基づいてプログラムに記述されている指示をＣＰＵで実行させれば、上述した実施形態の負荷配分装置と同様な動作を実現することができる。
【００５０】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【００５１】
【発明の効果】
本発明の負荷配分装置、負荷配分方法、及び負荷配分プログラムによれば、処理装置に余計な処理をさせることなく、実態に即した処理負荷の低い処理装置を選択してこの処理装置に処理データを配分することができる。
【図面の簡単な説明】
【図１】本発明の実施形態に係る負荷配分装置を含むシステム例を示す図。
【図２】図１の負荷配分装置のブロック図。
【図３】図１の選択決断順位算出部で利用される数式及びテーブルを示す図。
【図４】図１の処理装置の数が１０である場合の計算例を示す図。
【図５】図４の場合の処理装置を決定する様子を示す図。
【図６】図４の場合の処理装置を決定する、図５とは別の例の様子を示す図。
【図７】図２の負荷配分装置が２つある場合のシステム例を示す図。
【符号の説明】
１０・・・負荷発生装置、２０・・・負荷配分装置、２１・・・処理データ入力部、２２・・・処理データ配分部、２３・・・処理装置識別部、２４・・・負荷検出部、２５・・・選択決断順位算出部、２６・・・判定部、２７・・・メモリ、３０・・・処理装置、４０・・・負荷配分装置
【図１】
2004355227.tif 000003
【図２】
2004355227.tif 000004
【図３】
2004355227.tif 000005
【図４】
2004355227.tif 000006
【図５】
2004355227.tif 000007
【図６】
2004355227.tif 000008
【図７】
2004355227.tif 000009