(57)【特許請求の範囲】
【請求項１】
処理要求を入力する入力部と、
前記処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析部と、
リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当て部と
を備え、
前記リソース割り当て部は、リソースを割り当てる計算時間を予め設定し、当該計算時間で割り当てできる処理要求の数を算出し、割り当てた処理要求の数が前記算出した処理要求の数に達した場合に、新たなタイムウインドウを設定することを特徴とするリソース割り当て装置。
【請求項２】
処理要求を入力する入力部と、
前記処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析部と、
リソースを割り当てる時間帯を表す所定の幅のタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当て部と
を備え、
前記リソース割り当て部は、リソースを割り当てる計算時間が、第１閾値以上の場合に前記タイムウインドウの幅を短縮させ、又は、前記計算時間が第２閾値以下の場合に前記タイムウインドウの幅を増加させることを特徴とするリソース割り当て装置。
【請求項３】
処理要求を入力する入力部と、
前記処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析部と、
リソースを割り当てる時間帯を表す所定の幅のタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当て部と
を備え、
前記リソース割り当て部は、当該タイムウインドウ内に含まれる前記処理要求の数が予め設定された一定の範囲内を維持するよう、所定時間内の前記処理要求の数が減少した場合に前記タイムウインドウの幅を長く設定し、前記所定時間内の前記処理要求の数が増加した場合に前記タイムウインドウの幅を短く設定することを特徴とするリソース割り当て装置。
【請求項４】
前記リソース割り当て部は、前記タイムウインドウに含まれる単位時間内の前記処理要求の数を計数し、積算した処理要求の数が第３閾値以下で且つ最小となる単位時間の経過後に、前記タイムウインドウを設定することを特徴とする請求項１又は３に記載のリソース割り当て装置。
【請求項５】
処理要求を入力する入力部と、
前記処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析部と、
リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当て部と
を備え、
前記リソース割り当て部は、前記タイムウインドウの開始時刻と終了時刻の何れか又は両方を、前記処理要求の数が増加と減少の変化を繰り返す周期の中で最少となる時刻に設定することを特徴とするリソース割り当て装置。
【請求項６】
前記リソース割り当て部は、前記タイムウインドウの外側に割り当てられた前記処理要求を、リソースの割り当ての対象から除外することを特徴とする請求項１乃至５の何れかに記載のリソース割り当て装置。
【請求項７】
前記リソース割り当て部は、前記タイムウインドウに含まれる前記処理要求の中の所定の処理要求を、前記要求分析部の計算対象にすることを特徴とする請求項１乃至６の何れかに記載のリソース割り当て装置。
【請求項８】
リソース割り当て装置が行うリソース割り当て方法であって、
要求分析部は、入力された処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析ステップを行い、
リソース割り当て部は、リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当てステップとを行い、
前記リソース割り当てステップは、リソースを割り当てる計算時間を予め設定し、当該計算時間で割り当てできる処理要求の数を算出し、割り当てた処理要求の数が前記算出した処理要求の数に達した場合に、新たなタイムウインドウを設定することを特徴とするリソース割り当て方法。
【請求項９】
リソース割り当て装置が行うリソース割り当て方法であって、
要求分析部は、入力された処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析ステップを行い、
リソース割り当て部は、リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当てステップとを行い、
前記リソース割り当てステップは、リソースを割り当てる計算時間が、第１閾値以上の場合に前記タイムウインドウの幅を短縮させ、又は、前記計算時間が第２閾値以下の場合に前記タイムウインドウの幅を増加させることを特徴とするリソース割り当て方法。
【請求項１０】
リソース割り当て装置が行うリソース割り当て方法であって、
要求分析部は、入力された処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析ステップを行い、
リソース割り当て部は、リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当てステップとを行い、
前記リソース割り当てステップは、当該タイムウインドウ内に含まれる前記処理要求の数が予め設定された一定の範囲内を維持するよう、所定時間内の前記処理要求の数が減少した場合に前記タイムウインドウの幅を長く設定し、前記所定時間内の前記処理要求の数が増加した場合に前記タイムウインドウの幅を短く設定することを特徴とするリソース割り当て方法。
【請求項１１】
前記リソース割り当てステップは、前記タイムウインドウに含まれる単位時間内の前記処理要求の数を計数し、積算した処理要求の数が第３閾値以下で且つ最小となる単位時間の経過後に、前記タイムウインドウを設定することを特徴とする請求項８又は１０に記載のリソース割り当て方法。
【請求項１２】
リソース割り当て装置が行うリソース割り当て方法であって、
要求分析部は、入力された処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析ステップを行い、
リソース割り当て部は、リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当てステップとを行い、
前記リソース割り当てステップは、前記タイムウインドウの開始時刻と終了時刻の何れか又は両方を、前記処理要求の数が増加と減少の変化を繰り返す周期の中で最少となる時刻に設定することを特徴とするリソース割り当て方法。
【請求項１３】
前記リソース割り当てステップは、前記タイムウインドウの外側に割り当てられた前記処理要求を、リソースの割り当ての対象から除外することを特徴とする請求項８乃至１２の何れかに記載のリソース割り当て方法。
【請求項１４】
前記リソース割り当てステップは、前記タイムウインドウに含まれる前記処理要求の中の所定の処理要求を、前記要求分析部の計算対象にすることを特徴とする請求項８乃至１３の何れかに記載のリソース割り当て方法。
【請求項１５】
請求項１乃至７の何れかに記載したリソース割り当て装置としてコンピュータを機能させるためのリソース割り当てプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一つ以上の処理要求（ジョブ、タスク等：以降、処理要求）に対して、一つ以上の処理装置から構成されるリソース（設備、プロセス、モジュール、ＣＰＵ、メモリ、ハードディスク、ネットワーク帯域等：以降、リソース）に、処理要求を割り当てるリソース割り当て装置、リソース割り当て方法、及びリソース割り当てプログラムに関する。
【背景技術】
【０００２】
従来、一つ以上の処理装置から構成されるリソースに、処理要求を割り当てる方法は、例えば特許文献１に開示された方法で行われていた。
【０００３】
特許文献１に開示された方法は、処理要求に基づいて必要なプロセッサ数・使用時間数等のリソース量を算出し、処理要求の優先順位に基づいて必要なリソース量を割り当て、リソース量分だけ処理要求を実行させる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平６−２８３２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
先行技術文献によれば、リソースの割り当てはできるが、そのリソース割り当て計算に必要となる時間が、処理要求数とリソース数に依存して増加するため、ある時間内にリソース割り当て計算を完了できなくなる可能性がある。
【０００６】
利用者が要求する処理要求においては、ある時刻区間において必ず処理の実行を必要とする要求（ライブ処理要求、リアルタイム処理要求）、又は、ある時刻までに処理が完了できればよい要求（ノンライブ処理要求、バッチ処理要求）が存在する。
【０００７】
各処理要求を実行するために必要なソフトウェア・ハードウェアは各処理要求によって異なるため、それぞれに固有のソフトウェアコンポーネント・ハードウェアコンポーネントが必要である。あるライブ処理要求・ノンライブ処理要求を実行するには、実行可能なリソースを特定し、該当リソースを必要な時刻区間確保するスケジューリングが必要となる。
【０００８】
可能な限り多くの処理要求を実行し、且つ、より少ないリソースを利用することで処理要求を実行するには、各処理要求と各リソースとの組み合わせ計算が必要となる。また、処理要求を追加した場合には、新しい処理要求を含めて適切なリソースとの組み合わせを計算する処理（プロビジョニング）が必要となる。また、障害発生や減設によって利用可能なリソースが減少した場合等には、リソースが減少した条件下での既存の処理要求との適切な組み合わせを計算する処理（再スケジューリング）が必要となる。以降において、プロビジョニングと再スケジューリングを合わせてスケジューリングと称し、スケジューリングの結果として出力される処理要求とリソースの組み合わせをリソースプランと称する。
【０００９】
処理要求数とリソース数が増えた場合には、その組み合わせ計算量が増えるため、計算結果の算出に時間が掛かるようになる。これにより、サービス利用者が処理要求を入力してから計算結果が出力されるまでの時間が長くなる。また、リアルタイム性の高い処理要求の場合は、障害等発生後の再スケジューリング結果に基づき新しいリソースプランで処理要求が実行されるまでの時間が長くなる。これにより、例えばメディア処理であればフレーム落ち等の映像品質の劣化が発生する等、サービスの品質劣化が継続するといった課題が生じる。
【００１０】
本発明は、この課題に鑑みてなされたものであり、スケジューリングにより新しいリソースプランが作成された処理要求に対しての計算結果出力までの時間を短くすると共に、再スケジューリングの結果に基づき新しいリソースプランで処理要求が実行されるまでのサービスの品質劣化時間を短縮したリソース割り当て装置、リソース割り当て方法、及びリソース割り当てプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明のリソース割り当て装置は、処理要求を入力する入力部と、前記処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析部と、リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当て部とを備え、前記リソース割り当て部は、リソースを割り当てる計算時間を予め設定し、当該計算時間で割り当てできる処理要求の数を算出し、割り当てた処理要求の数が前記算出した処理要求の数に達した場合に、新たなタイムウインドウを設定することを要旨とする。
【００１２】
また、本発明のリソース割り当て方法は、上記のリソース割り当て装置が行うリソース割り当て方法であって、要求分析部は、入力された処理要求の実行に必要なリソース消費量と処理時間とを計算する要求分析ステップを行い、リソース割り当て部は、リソースを割り当てる時間帯を表すタイムウインドウを設定し、前記タイムウインドウの時間帯の中で、前記リソース消費量と前記処理時間に基づいてリソースを割り当てるリソース割り当てステップとを行い、前記リソース割り当てステップは、リソースを割り当てる計算時間を予め設定し、当該計算時間で割り当てできる処理要求の数を算出し、割り当てた処理要求の数が前記算出した処理要求の数に達した場合に、新たなタイムウインドウを設定することを要旨とする。
【００１３】
また、本発明のリソース割り当てプログラムは、上記リソース割り当て装置としてコンピュータを機能させるようにしたものである。
【発明の効果】
【００１４】
本発明によれば、スケジューリングにより新しいリソースプランが作成された処理要求に対しての計算結果出力までの時間を短くすると共に、再スケジューリングの結果に基づき新しいリソースプランで処理要求が実行されるまでのサービスの品質劣化時間を短縮することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施の形態のリソース割り当て装置の機能構成例を示す図である。
【図２】本実施の形態のリソース割り当て装置の動作フローを示す図である。
【図３】リソース割り当ての計算結果（リソースプラン）を示す図であり、（ａ）は当初のリソースプランの一例、（ｂ）は処理要求が追加されて再計算したリソースプランの一例を示す図である。
【図４】（ａ）は処理要求数とリソースを割り当てる計算時間との関係を模式的に示す図であり、（ｂ）は対象リソース数とリソースを割り当てる計算時間との関係を模式的に示す図である。
【図５】タイムウインドウを設定して処理要求をリソースに割り当てる様子を模式的に示す図である。
【図６】タイムウインドウを設定することで計算時間を制限できる様子を模式的に示す図である。
【図７】時刻と処理要求数との関係例を模式的に示す図である。
【図８】リソースを割り当てるのに要する計算時間とタイムウインドウ時間幅との関係を例示する図である。
【図９】処理要求数が時間経と共に減少する場合において、一定時間幅のタイムウインドウ時間幅を設定した場合のタイムウインドウ内の処理要求数の変化を模式的に示す図である。
【図１０】タイムウインドウの幅に含まれる処理要求数が一定になるように、タイムウインドウの幅を可変した場合の処理要求数の変化を模式的に示す図である。
【図１１】タイムウインドウ内の処理要求数を計数し、計数した処理要求数が所定の値を超える場合に新たなタイムウインドウを開始する様子を累積処理要求数の変化で示す図である。
【図１２】リソースを割り当てるのに要する計算時間とリソース利用効率との関係を模式的に示す図である。
【図１３】各単位時間における処理要求を計数し、処理要求が少ない時間帯にタイムウインドウを設定する図である。
【図１４】時刻と処理要求数との関係を模式的に示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について図面を用いて説明する。
【００１７】
本実施の形態のリソース割り当て装置１の機能構成例は、図１に示すように表される。また、リソース割り当て装置１の動作フローは、例えば図２に示すように表される。
【００１８】
リソース割り当て装置１は、入力部１０、要求分析部２０、処理実績ＤＢ３０、リソース割り当て部４０、設備リソースＤＢ５０、実行管理部６０を備える。図１と図２を参照してリソース割り当て装置１の動作を説明する。なお、「ＤＢ」はデータベースを意味する。
【００１９】
入力部１０には、処理要求が入力される（ステップＳ１）。処理要求とは、例えばメディア処理であれば「映像受信」、「映像加工」、「映像圧縮」、「映像配信」等の処理（ジョブ）を、サーバ等のリソース上で処理することを要求することである。なお、処理要求はメディア処理に限られない。
【００２０】
入力部１０は、定期的又は不定期に到着する処理要求の入力を受け付ける。処理要求には、要求の種別（例えばライブ処理、バッチ処理）、要求開始希望時刻〜要求完了希望時刻、要求の中身（例えば上記の「映像加工」等のこと）を表す情報が含まれる。
【００２１】
また、処理要求は、一つ又は複数ジョブで構成される。複数ジョブで構成される場合には、各ジョブ間には依存関係が設定される場合がある。各ジョブに必要とされるリソース種別と量は均一ではなく、専用ハードウェアを必要とする処理や使用するＣＰＵコア数・スレッド数・メモリ量・ＨＤＤ容量・ネットワーク帯域等にもバラつきがある。
【００２２】
ライブ映像配信等のライブ処理は、要求開始希望時刻〜要求完了希望時刻までの時間、リソースを使用できる必要がある。また、ファイルエンコード等のバッチ処理は、要求開始可能時刻〜要求完了希望時刻を設定することができ、要求完了希望時刻までにリソースを使用して処理を完了する必要がある。
【００２３】
要求分析部２０は、処理要求を実行するために必要なリソース消費量と処理要求を処理するのに要する処理時間とを計算する（ステップＳ２）。要求分析部２０は、入力部１０から入力された処理要求に対して、処理実績ＤＢ３０を参照し、相当する処理実績を選択する。相当する処理実績であるか否かの判断は、例えばメディア処理の場合、ファイルの解像度（ＨＤ（登録商標）・４Ｋ（登録商標）・８Ｋ（登録商標））、エンコード種別（ＭＰＥＧ２・ＶＣ−１・ＭＰＥＧ４−Ｖｉｓｕａｌ・ＡＶＣ(登録商標)・ＨＥＶＣ）等を利用して行う。例えばファイルエンコードの処理では、解像度やエンコード種別、計算リソースの処理能力等が同じ条件であれば、映像の長さ（データ量）と処理時間は比例する。
【００２４】
また、処理実績は、事前に設定された処理ＩＤに基づいて選択するようにしても良い。同じ処理ＩＤを持つ処理要求は、同じ処理特性（必要なプロセッサ数・ＣＰＵ利用率・メモリ使用量・ネットワーク帯域・ディスク容量等）を持つため、処理ＩＤに基づいて選択した処理実績からリソース消費量を予測することができる。
【００２５】
要求分析部２０は、選択した処理実績と、処理要求から必要なリソース消費量と処理時間を計算する。要求分析部２０は、必要なリソース消費量が確保可能か否かの計算も実施する。
【００２６】
リソース割り当て部４０は、処理要求のリソースへの割当を表すリソースプランを作成する時間帯を表すタイムウインドウを設定し、タイムウインドウの時間帯において、各処理要求に対してリソース消費量と処理時間に基づいてリソースを割り当てる（ステップＳ３）。リソース割り当て部４０は、設備リソースＤＢ５０から処理要求を実行するのに必要なリソースを抽出する。設備リソースには、リソースの保有する処理特性毎に処理能力が規定されている。
【００２７】
抽出されたリソースのうち、該当する処理要求を実行可能なリソースの処理特性毎の処理能力の余力状況を確認し、空いていればリソースを予約する。リソースが予約されると、該当処理要求の開始時刻から終了時刻のリソース処理特性毎の処理能力から、処理要求を実行するために必要な処理特性毎の処理能力を減算し、リソースの処理能力を算出する。全ての処理要求が予約される、または、リソースの処理能力が不足するため、処理要求が予約できなくなるまで順次繰り返す。必要な処理特性に対して、リソースの処理余力が空いていなければ次のリソース候補の空き時間を確認する手順を繰り返す。
【００２８】
一つのリソースで複数の処理要求の中身（例えば「映像受信」、「映像加工」等）を処理可能な場合がある。処理要求を実行することで、該当リソースが持つ処理特性が消費される。複数の処理要求に対して、リソースの割り当てを偏らせてなるべく未使用のリソースを残すように処理要求を割り当てることで、消費電力の削減やリソースの利用時間に応じて課金されるリソース（クラウドサーバ等）利用時のコストを削減する事が出来る。また、複数の処理要求に対して、リソースの割り当てを平準化して未使用のリソースを減らすように処理要求を割り当てることで、サーバ障害発生時に影響が出る処理要求数を削減することが出来る。
【００２９】
処理要求にリソースを割り当てるには、処理要求の優先順位、リソースの希少性、リソースの余裕度を考慮することで、処理要求が追加された場合に使用可能なリソースを残すことができる。また、リソースの割り当てを偏らせることで、未使用のリソースが生じるように配慮する。リソースの利用時間に応じて課金されるので、未使用のリソースを増やすように処理要求を割り当てることで、消費電力の削減とコストダウンを図ることができる。
【００３０】
ライブ映像配信等、ある時刻範囲にわたって確実にリソースを使用して処理要求を実行する必要がある場合、数週間から数ヶ月先の処理要求が予約されることがある。この場合、処理要求の入力時点でリソースの予約可否を判定し、可と判定した場合には他の処理要求の入力時やリソース障害発生時においても予約された処理要求を実行できるように再びリソースを割り当てる（再スケジューリング）必要がある。特に障害発生時の再スケジューリングに関しては、リアルタイム性の高い処理要求の場合、その処理が途絶えてしまうため、リソースの再割り当てを短時間で実行する必要がある。
【００３１】
また、予約済みの処理要求を変更する場合は、該当の処理要求を変更すると、他の処理要求にも影響が発生する場合がある。例えば、ライブ処理の希望終了時刻を延長する場合、該当の処理要求が予約されているリソース上で予約されている他の処理要求に対しても、リソースの持つ処理能力に対してリソース要求量の総量が超過しない様に割り当てをする必要があるため、玉突きの様に他の処理要求の変更が必要となる場合がある。
【００３２】
例えば、各処理要求と処理要求を構成するジョブに順序性や依存間関係が無い場合、予約済みの処理要求を変更する場合は、各処理要求の開始から終了時刻の間、リソースの持つ能力に対してリソース要求量が超過しない様に割り当てをする必要がある。
例えばメディア処理要求であれば「映像受信」、「映像加工」、「映像圧縮」、「映像配信」等の各プロセスを一連の処理として、順に実施する必要がある。この場合は、順序性を保ちつつ、リソースの持つ能力に対して各処理要求が必要とするリソース要求量の総和が超過しない様に割り当てをする必要がある。
【００３３】
また、メディア処理（映像加工、映像圧縮等）の場合、映像フレーム間の差分情報を利用して動画を作成するため、処理の遅延時間を考慮すると複数のサーバに分割してリアルタイム処理することは困難なため、一台のサーバで処理する必要がある。この場合、処理要求を複数の処理単位に分割して複数のサーバに分散させて処理することができない。また、複数の処理時間に分散させて処理することもできない。特にライブ中継等の場合は、ライブ中継の開始時刻から終了時刻まで、メディア処理の遅延時間と処理単位の分割・結合遅延時間が発生しないようにその処理の実行予約をする必要がある。
【００３４】
入力部１０に入力される新たな処理要求、及び、リソース割り当て部４０が割り当てた後、再スケジューリングの対象となる処理要求を、以降において契機処理要求と称する。また、リソース割り当て部４０が割り当てた全ての処理要求を、全処理要求と称する。
【００３５】
実行管理部６０は、予約されたリソースを該当する時刻に起動し、処理要求を実行させる（ステップＳ４）。
【００３６】
〔リソース割り当て例〕
ここで、図３を参照して、処理要求を追加した場合におけるリソース割り当ての計算例について説明する。図３に、リソース割り当ての計算結果（リソースプラン）を示す。図３（ａ）は当初のリソースプランの一例、図３（ｂ）は処理要求が追加されて再計算したリソースプランの一例を示し、処理要求の追加前後を比較する。
【００３７】
図３の横方向は時刻、縦方向は各リソースの処理能力を表す。各リソースの処理能力は、縦方向の大きさで模式的に表している。また、リソースの処理特性は一つとは限らない。リソースＡの処理能力が最も大きく、リソースＢ，Ｃ，Ｄの処理能力は同等である。例えば、リソースＡ，Ｂ，Ｃは、オンプレミスサーバであり、リソースＤは、例えばクラウドサーバである。
【００３８】
図３中のハッチング有りの実線の四角形は、優先して処理する優先ライブを表す。また、ハッチング有りの破線の四角形は非優先ライブを、白抜きの実線の四角形は優先して処理する優先ノンライブを、白抜きの破線の四角形は非優先ノンライブを、それぞれ表す。
【００３９】
図３中に示す四角形は、各々の処理要求を表している。リソースの利用効率を重視してより少ないリソースで全ての処理要求を実行するため、８時〜１５時までの処理要求が、各リソースに割り当てられている。
【００４０】
各処理要求は、リソースの利用効率を上げ、運用コストを下げるため、例えば、全てのジョブは必要な計算リソースが大きいものから順番にリソースに割り当てられる。リソース消費量の大きな処理要求Ａ８は、処理能力の大きなリソースＡに割り当てられている。また、リソースＢには、リソースの利用効率を上げるため、他のリソースＣ，Ｄに空きが生ずるように処理要求Ｂ８ａとＢ８ｂとが割り当てられている。
【００４１】
ここで９時〜１１時に、メディア処理をライブ（実況放送）で行う処理要求Ａ９−１０が追加された場合を想定する。この場合、図３（ａ）に示すリソースプランはリセットされ、再スケジューリングが実行される。再スケジューリングは、全ての処理要求についてリソース割り当てを再計算する。
【００４２】
図３（ｂ）に、再計算したリソースプランの例を示す。優先ライブである処理要求Ａ９−１０は、リソースＡに優先的に割り当てられる。その結果、当初、リソースＡの９時に割り当てられていた処理要求Ａ９は、処理能力の小さなリソースＣへ、処理時間を拡大し、処理要求Ｃ８−１０として割り当てられる。その結果、当初のリソースプランにおいてリソースＣに割り当てられていた処理要求Ｃ９−１０は、リソースＢに新たな処理要求Ｂ９−１０として割り当てられる。また、同様に当初のリソースプランにおいてリソースＢに割り当てられていた処理要求Ｂ９は、リソースＣに新たな処理要求Ｃ８として割り当てられる。
【００４３】
このように、新たな処理要求が追加されると、全ての処理要求にリソースを割り当てる計算が繰り返される。したがって、処理要求の数が増加すると再計算時間は、処理要求の数に比例して増加することになる。以降、当初の処理要求と、再計算して新たに割り当てられる処理要求との関係は、両者を矢印で結び、その説明を省略する。
【００４４】
図４（ａ）に、処理要求数とリソースを割り当てる計算時間との関係を模式的に示す。図４（ａ）の横軸は処理要求数、縦軸は計算時間である。このように処理要求数と計算時間とは、比例する。
【００４５】
また、割り当て対象のリソース数が増加すると、再計算時間はリソースの数に比例して増加する。図４（ｂ）に、割り当て対象リソース数とリソースを割り当てる計算時間との関係を模式的に示す。図４（ｂ）の横軸は割り当て対象リソース数、縦軸は計算時間である。
【００４６】
図４（ａ）の比較例のリソース割り当て計算時間に対して、本実施形態のリソース割り当て部４０は、割り当て計算時間の上限を定めることを目的とし、リソースを配分する時間帯を表すタイムウインドウを設定し、タイムウインドウの時間帯の中で、リソース消費量と処理時間に基づいてリソースを割り当てる。
【００４７】
タイムウインドウは、タイムスライスに割り当てられたジョブの切れ目にタイムウインドウを設定する。しかし、例えば、図５のＢ８ｂ、Ｃ９−１０、Ｂ１１−１２、Ｂ１２−１４、Ｂ１４、Ｃ１４−１５の様に、複数のジョブの実行時刻帯が重複している場合には、ジョブの切れ目が無い。そうなるとタイムウインドウの区間が長くなり計算時間の削減につながらないため、本実施形態では、全処理要求のうちタイムウインドウの外側に割り当てられた処理要求を再割り当ての対象外としてもよい。
【００４８】
なお、タイムウインドウを設定する設定時刻は、契機処理要求の希望開始時刻〜希望終了時刻に対して、「タイムウインドウ開始時刻」≦「希望開始時刻」、「希望終了時刻」≦「タイムウインドウ終了時刻」となる範囲にタイムウインドウの開始時刻と終了時刻を設定する必要がある。これは、リソースを割り当てたい処理要求の希望開始時刻から希望終了時刻よりも、前後に長い時刻にタイムウインドウを設定することで、タイムウインドウ内の時刻に対して、リソース割り当て計算を実施出来る様にするためである。したがって、全処理要求のうち、契機処理要求を含み、タイムウインドウの内側に割り当てられた処理要求を再割り当ての対象とする。
【００４９】
リソースを割り当てる計算時間は、計算対象の処理要求数と割り当て対象のリソース数に比例するため、タイムウインドウ内の処理要求数が限定されることになる。その結果、計算時間を短縮（計算時間の上限を制限できる）することができる。
【００５０】
タイムウインドウを設定してリソースを予約する模式的概念図は、図５に示すように表される。また、タイムウインドウを設定した場合の処理要求数とリソースの割り当て計算時間との関係の模式図は、図６に示すように表される。図５の横方向と縦方向の関係は図３と同じであり、図６の横軸と縦軸の関係は図４（ａ）と同じである。
【００５１】
図５は、タイムウインドウの時間帯が８時から１２時に設定された例を示している。タイムウインドウを設定することで、対象の処理要求の数が削減できる。その結果、図６に示すように計算対象となる処理要求の数が、例えば、割り当て処理要求数Ｒ１に対しては、割り当て計算時間Ｃ１、割り当て処理要求数Ｒ２に対しては、割り当て計算時間Ｃ２に制限されるので、計算時間もＣ１，Ｃ２以上に増加することがない。なお、図５において、設定したタイムウインドウの１個前のタイムウインドウにも予約される処理要求Ｂ８ｂ、設定したタイムウインドウの１個後のタイムウインドウにも予約される処理要求Ｂ１１−１２等、複数のタイムウインドウをまたがる処理要求については、予約済みとして再計算の対象外とする。
【００５２】
これは設定したタイムウインドウ内の処理要求についてのみ再割り当て計算を実施し、タイムウインドウ外に既に割り当てられている処理要求に影響を与えない為である。例えば、図５においてＢ１１−１２については、リソースＡの１１時〜１２時の時刻に処理要求の割り当てがされていないため設定したタイムウインドウ内では処理余力のあるリソースに見えるが、タイムウインドウ外の１２時以降にＡ１２が割り当て済みのため実際には割り当てが出来ない。タイムウインドウをまたがる処理要求を予約済みとして再計算の対象外とすることで、再割り当て可能な処理要求とリソースが少なくなるため、リソース利用効率の低下が発生し得る。
【００５３】
このように本実施形態のリソース割り当て装置は、契機処理要求が生じた際に、全処理要求に対するリソースの割り当てを行わない（計算対象の処理要求を限定する）ため、サービス利用者が処理要求を入力してから計算結果が出力されるまでの時間を短縮することができる。また、リアルタイム性の高い処理要求の場合（例えばライブ処理）は、新しいリソースプランで処理要求が実行されるまでの時間が短くなり、サービスの品質劣化を生じ難くすることができる。
【００５４】
〔タイムウインドウの変形例〕
タイムウインドウの時間帯は、８時から１２時の４時間に設定する例を示した。しかし、タイムウインドウを設定する時刻は何時でも構わない。また、その時間幅も上記の例に限定されない。次にタイムウインドウの変形例について説明する。
【００５５】
（変形例１）
図７に、時刻と処理要求数との関係を示す。図７の横軸は時刻、縦軸は処理要求数である。
【００５６】
図７は、処理要求の数が一日の内に周期的に変化する例を示す。例えば午前１０時頃から処理要求が増加し、昼から午後３時頃まで処理要求数が最大になり、以降の時刻で減少する変化を繰り返す。この様な場合は、処理要求の数が少ない時刻にタイムウインドウを設定することで、タイムウインドウをまたがる処理要求を少なくすることが出来るため、再計算の時間短縮と、リソース利用効率の低下を抑止することができる。
【００５７】
つまり、タイムウインドウは、契機処理を含む範囲で所定周期で且つ所定の幅に設定しても良い。例えば、システムのメンテナンスのため処理を実行しない時刻が決まっているような場合は、処理の少ない時刻に所定の幅のタイムウインドウを定期的に設定しても良い。
【００５８】
（変形例２）
タイムウインドウの時間幅は可変してもよい。例えば、処理要求数が増加する場合に、一定の幅のタイムウインドウを設定するとリソースの割り当て計算時間が大きくなり過ぎることがある。そこで、計算時間に上限の目標閾値を設けてもよい。その場合のリソース割り当て部４０は、リソースを割り当てる計算時間が、第１閾値以上の場合にタイムウインドウの幅を短縮させる。
【００５９】
さらに、リソース割り当て部４０が、複数の閾値を設定された場合、例えば、その場合のリソース割り当て部４０は、リソースを割り当てる計算時間が、第１閾値以上の場合にタイムウインドウの幅を短縮させ、その計算時間が第２閾値以下の場合にタイムウインドウの幅を増加させる。例えば、第２閾値（２０）＜計算時間＜第１閾値（５０）で表されるように計算時間に対応したタイムウインドウの幅を設定する。閾値の次元は時間であり、その単位はｓ、ｍｓ、μｓの何れでもよい。また、「以下」は「未満」、「以上」は「大きい」でもよい。
【００６０】
図８に、リソースを割り当てる計算時間とタイムウインドウ時間幅との関係を例示する。図８の１列目は処理要求発生時刻、３列目はタイムウインドウ時間幅、４列目はタイムウインドウ内の処理要求数、５列目は処理要求割り当て計算時間である。
【００６１】
処理要求はランダムに発生しており、図８では１０分間隔で処理要求数を表記している。図８において、時刻０：４０に発生した処理要求に基づく計算時間が、第１閾値（５０）以上となるので、以降のタイムウインドウ時間幅を４時間から２時間に半減させる。タイムウインドウ時間幅を半減させることで、タイムウインドウ内の処理要求数も大よそ半減（２７５）させ、計算時間を短縮することができる。
【００６２】
また、計算時間が第２閾値（２０）以下になった場合は、タイムウインドウ時間幅を倍増させる。そうすることで計算時間を、目標とする時間に調整することが可能である。なお、タイムウインドウ時間幅を倍増させる例については、図８から容易に想定できるので図示を省略する。
【００６３】
このようにタイムウインドウは固定である必要は無い。なお、再スケジューリングの計算時間が閾値を越えた場合に、タイムウインドウの幅を増減することで、計算時間を一定時間に維持することも可能である。
【００６４】
（変形例３）
リソース割り当て部４０は、所定時間内の処理要求数が減少すればタイムウインドウの幅を長く設定し、所定時間内の処理要求数が増加すればタイムウインドウの幅を短く設定するようにしてもよい。
【００６５】
図９に、処理要求数が時間経過と共に減少する場合において、一定時間幅のタイムウインドウを設定した場合のタイムウインドウ内の処理要求数を示す。この場合、図９に示すようにタイムウインドウ内の処理要求数は、例えば１５０→１００→５０と漸減することになる。図９の横軸と縦軸の関係は、図７と同じである。
【００６６】
このように処理要求数が時間経過と共に減少する場合において、タイムウインドウを固定すると、近い将来の処理要求数が多くなるので、リソースの割り当て計算時間が長くなる。例えば、障害発生時に復旧させる場合を想定すると、近い将来の計算時間を短縮しておく方が得策である。
【００６７】
そこで、リソース割り当て部４０は、所定時間内の処理要求数が減少すればタイムウインドウの幅を長く設定し、所定時間内の処理要求数が増加すればタイムウインドウの幅を短く設定するようにしてもよい。このようにタイムウインドウの幅を設定することで、近い将来の計算時間を短縮することができる。
【００６８】
つまり、変形例３は、処理要求数に応じたタイムウインドウの幅を設定する例である。処理要求に周期性が見込めない場合（ランダムに発生する場合）は、固定のタイムウインドウを設定すると、タイムウインドウ内に含まれる処理要求数が変動するため、計算時間にバラつきが出る。
【００６９】
近い将来の予定の方が、遠い将来の予定よりも処理要求の数が多い場合は、近い将来の計算時間が長時間化する。何時起きるか分からない障害発生時の復旧を考えると、変形例３のように近い将来の計算時間を短縮できるようにタイムウインドウの幅を可変すると良い。
【００７０】
（変形例４）
リソース割り当て部４０は、タイムウインドウの幅に含まれる処理要求数を一定の範囲内に維持するように、タイムウインドウの幅を可変するようにしてもよい。
【００７１】
図１０に、処理要求数が時間経過と共に減少する場合において、タイムウインドウの幅に含まれる処理要求数が一定になるように、タイムウインドウの幅を可変した場合のタイムウインドウ内の処理要求数の変化を示す。図１０の横軸と縦軸の関係は、図９と同じである。
【００７２】
図１０に示すように、タイムウインドウの幅に含まれる処理要求数が例えば１００となるように、タイムウインドウの幅が漸増することになる。このようにタイムウインドウの幅を漸増するためには、例えば図１１に示すように、タイムウインドウ内の処理要求数を計数し、計数した処理要求数が所定の値を超える場合に新たなタイムウインドウを開始するようにすればよい。つまり、タイムウインドウの始点から処理要求の数を計数し、上限値に達した時点をタイムウインドウの終点とする。
【００７３】
図１１の１列目は単位時間開始時刻、２列目は単位時間終了時刻、３列目は単位期間、４列目は単位時間内の処理要求数、５列目はタイムウインドウ内の処理要求数の累積である。なお、図１１は、単位時間を１時間として処理要求数を計数する例を示すが、単位時間は１時間に限定されず、５秒、１０秒、５分など任意の時間である。
【００７４】
不定期に到着する処理要求を入力としてその数を累積し、累積した処理要求数が所定の数を超えた場合に新たなタイムウインドウを開始するようにしてもよい。図１１では、単位時間開始時刻２：００から３：００の間に、累積した処理要求数が１００を越え新たなタイムウインドウが開始する。この例のように処理要求数が漸減する場合、タイムウインドウの幅は漸増することになる。
【００７５】
このように処理要求数が漸減する場合に、タイムウインドウの幅を漸増させると、リソースの利用効率を向上させることができる。リソースの利用効率とは、リソースの割り当て計算時間を無限大にした場合の残存リソース量を分母、有限のある計算時間でリソースを割り当てた後の残存リソース量を分子とする比率である。
【００７６】
同様に、処理要求数が漸増する場合に、タイムウインドウの幅を漸減させると、リソースの割り当て計算時間を短縮させることができる。
【００７７】
リソースの割り当て計算時間とリソース利用効率とは、トレードオフの関係となる。したがって、処理要求数が低い場合にタイムウインドウの幅を増加することで、リソースの利用効率を向上させることが可能である。
【００７８】
（変形例５）
リソース割り当て部４０は、リソースを割り当てる計算時間を予め設定し、当該計算時間で割り当てられる処理要求の数を算出し、割り当てた処理要求の数が前記算出した処理要求の数に達した場合に、新たなタイムウインドウを開始するようにしてもよい。
【００７９】
図１２に、リソースを割り当てるのに要する計算時間とリソース利用効率との関係を示す。図１２の横軸は計算時間、縦軸はリソース利用効率である。
【００８０】
図１２に示すように、計算時間をある程度長くすると、リソース利用効率はそれ以上変化しなくなる特性を示す。つまり、計算時間に対してリソース利用効率は、飽和する特性を示す。リソース利用効率が飽和する計算時間にタイムウインドウの幅を設定できれば、最大のリソース利用効率を最小の計算時間で得ることになる。
【００８１】
まず、図１２に示す特性から計算時間を決定する。計算時間は、例えば２．５秒に決定する。そして、２．５秒の計算時間で割り当てられる処理要求数を例えば図６から求め、次に求めた処理要求数になるまで処理要求を計数し、計数した処理要求数が図６から求めた処理要求数に達した場合に、新たなタイムウインドウを開始させる。
【００８２】
このようにすることで、ソース利用効率がほとんど向上しない時間まで計算時間が延長されることが無い。したがって、タイムウインドウの幅を効率の良い時間幅に設定することができる。
【００８３】
つまり、図１２から再計算時間（計算時間）を有る程度長くするとリソース利用効率の向上が見込めなくなる点が生じることが分かる。そこで、そのリソース利用効率の向上が見込めなくなる計算時間となるタイムウインドウの幅を設定する。
【００８４】
（変形例６）
リソース割り当て部４０は、タイムウインドウに含まれる単位時間内の処理要求の数を計数し、積算した処理要求の数が第３閾値以下で且つ最小となる単位時間の経過後に、タイムウインドウを設定するようにしてもよい。
【００８５】
変形例５で説明したように、計算時間から求めた処理要求数を計数し、積算した処理要求数が図６から求めた処理要求数に達した場合に、新たなタイムウインドウを開始させることで、計算時間を所定の時間以下にすることができるが、他のタイムウインドウで予約済みの処理要求があるとリソースの利用効率の低下が見込まれる。
【００８６】
ここで他のタイムウインドウとは、例えば現在のタイムウインドウの１個前のタイムウンドウのことである。１個前のタイムウインドウで予約済みで且つ、現在のタイムウインドウにまたがる処理要求は計算の対象外とされ、動かせない処理要求として扱われる（図５に示す処理要求Ｂ８ｂ，Ｂ１１−１２）。
【００８７】
この動かせない処理要求の数が多いと、その分のリソースはスケジューリング時に利用できないものとして扱われるので、リソースの利用効率が低下する。これを防ぐためには、他のタイムウインドウで予約済みの処理要求数を減少させる必要がある。
【００８８】
タイムウインドウの開始時刻と終了時刻のそれぞれに対して、他のタイムウインドウで予約済みの処理要求数を減少させるには、単位時間内の処理要求数を計数し、計数した処理要求の数が最小となる単位時間の経過後に、タイムウインドウを設定するようにすればよい。
【００８９】
図１３に、図１１と同様の形式でリソースを割り当てる計算時間とタイムウインドウ時間幅との関係を例示する。図１３では、単位時間開始時刻５：００から６：００の間に、累積した処理要求数が第３閾値（１００）を超える。単位時間開始時刻４：００から５：００の単位時間に関しても第３閾値以下の条件を満たすが、単位時間開始時刻３：００から４：００の単位時間の単位時間内処理要求数（１０）が最小となる。このため、タイムウインドウの終了時刻を４：００に設定することで、他のタイムウインドウで予約済みの処理要求数を減少させることができる。
【００９０】
各単位時間における処理要求を計数し、処理要求が少ない時間帯にタイムウインドウを設定することで、タイムウインドウを跨ぐ処理要求の少ない時刻に新たなタイムウインドウを開始させることができる。その結果、リソースの利用効率の低下を抑制することができる。
【００９１】
（変形例７）
リソース割り当て部４０は、タイムウインドウの幅に含まれる処理要求の中の所定の処理要求を、リソース割り当ての対象にするようにしてもよい。つまり、タイムウインドウとは別に、リソースを分割するリソースウインドウを併用してもよい。
【００９２】
図１４に、時刻と処理要求数との関係を模式的に示す。図１４の横軸は時刻、縦軸は図３と同様に各リソースに割り当てられた処理要求数である。
【００９３】
図１４において、縦方向の破線の高さがリソースウインドウ、横方向の破線の幅がタイムウインドウを表す。このようにリソース割り当ての対象とする処理要求を限定することで、リソースの割り当て計算時間を短縮できる。
【００９４】
全ての処理要求を対象としたリソース利用効率≧リソースウインドウ内の処理要求を対象としたリソース効率、全ての処理要求を対象とした計算時間≧リソースウインドウ内の処理要求を対象とした計算時間の関係が常に成立する。
【００９５】
リソースウインドウをある程度大きくすると、リソースの利用効率の向上効果が見込めなくなる。その場合は、そのリソースウインドウの大きさでリソースウインドウを固定することで、効率的なリソースの割り当てを行うことができる。
【００９６】
なお、タイムウインドウとリソースウインドウは、それぞれを単独で使用しても良いし、併用しても良い。
【００９７】
以上説明したように本実施形態のリソース割り当て装置１によれば、処理要求の追加時に、新しいリソースプランで処理要求が実行されるまでの時間を短くすることができる。また、リソースの利用効率を向上させることもできる。
【００９８】
また、リソースに障害が生じた際には、該当するリソースで実行していた処理要求を、別のリソースで継続実行するまでに要する時間を短縮することができる。このようにリソース割り当て装置１は、処理要求とリソースとの組み合わせ計算時間の短縮と、リソースの利用効率の向上を実現できる。
【００９９】
具体的には、処理要求の追加（プロビジョニング）時には、該当する処理要求が実行可能かどうかの判定結果の提示に掛かる時間を短縮できる。また、利用者へのレスポンスタイムを短縮できる。また、リソース利用効率を高めることもできる。
【０１００】
また、リソース障害発生時には、該当リソースで実行していた処理を別のリソースで継続実行するまでに要する時間を短縮できる。その結果、設定された処理要求の終了時刻までに処理が終了しない事態を回避することができる。また、目標の時間内のリソース利用効率を高めることもできる。
【０１０１】
なお、実行管理部６０は、ノンライブ処理要求の予定終了時刻に対しての進捗状況を監視し、予定終了時刻までに完了しないと判断される場合は、該当の処理要求が予定終了時刻を満たすためにリソース割り当て部４０に通知し、契機処理要求として再スケジューリングを行うように指示するようにしても良い。また、実行管理部６０は、リソースを監視し、リソースに障害が発生した場合やリソースの利用率がある閾値を越えた場合に、該当の予約済みの処理要求を他のリソースで実行させるためにリソース割り当て部４０に通知し、契機処理要求として再スケジューリングを行うように指示するようにしても良い。
【０１０２】
本発明は、上記した実施形態に限定されるものではなく、その要旨の範囲内で数々の変形が可能である。
【符号の説明】
【０１０３】
１：リソース割り当て装置
１０：入力部
２０：要求分析部
３０：処理実績ＤＢ
４０：リソース割り当て部
５０：設備リソースＤＢ
６０：実行管理部
【図１】
0006467374.tif 000002
【図２】
0006467374.tif 000003
【図３】
0006467374.tif 000004
【図４】
0006467374.tif 000005
【図５】
0006467374.tif 000006
【図６】
0006467374.tif 000007
【図７】
0006467374.tif 000008
【図８】
0006467374.tif 000009
【図９】
0006467374.tif 000010
【図１０】
0006467374.tif 000011
【図１１】
0006467374.tif 000012
【図１２】
0006467374.tif 000013
【図１３】
0006467374.tif 000014
【図１４】
0006467374.tif 000015