(57)【特許請求の範囲】
【請求項１】
複数のタイプのそれぞれのジョブ用の最初および最後の期限を当該タイプ用の分類コードに関連付けて保持する臨界時間テーブルと、
前記複数のタイプのそれぞれのジョブ用の最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）を当該タイプ用の分類コードに関連付けて保持するＷＣＥＴテーブルと、
ユーザからのジョブを前記複数のタイプのいずれか１つに分類し、当該ジョブを当該タイプ用の分類コードに関連付ける分類ユニットと、
前記臨界時間テーブルおよび前記ＷＣＥＴテーブルに基づいて、前記分類されたジョブ用の最初および最後の期限ならびにＷＣＥＴを決定し、決定した最初および最後の期限ならびに決定したＷＣＥＴに従って、前記分類されたジョブ用のスケジュールを生成するコアユニットと、
前記複数のタイプのそれぞれについてジョブの数を監視し、ジョブの数がその移動平均から正の方向に外れているタイプを前記複数のタイプから抽出する認識ユニットと、を備え、
前記コアユニットは、前記ユーザからのジョブが前記分類ユニットにより抽出されたタイプに分類されている場合、当該ジョブを前記スケジュールにおいて優先的にスケジュールする、
クラウドコンピューティング用のリソース管理システム。
【請求項２】
前記複数のタイプのそれぞれのジョブ用の属性を当該タイプ用の分類コードに関連付けて保持する分類テーブルを備え、
前記分類ユニットは、前記ユーザからの前記ジョブを、前記分類テーブルにおける属性が前記ジョブ用の属性と同様である分類コードに関連付ける、
請求項１に記載のリソース管理システム。
【請求項３】
前記コアユニットは、前記ユーザからのジョブが前記分類ユニットにより抽出されたタイプに分類されている場合、当該ジョブ用の前記決定された最初および最後の期限を短くする、
請求項１または２に記載のリソース管理システム。
【請求項４】
前記複数のタイプのそれぞれのジョブについて実行時間を監視し、実行時間が１つでも当該タイプのＷＣＥＴを超えた場合、前記ＷＣＥＴテーブルにおいて当該タイプ用のＷＣＥＴを更新するジョブトレーサを備える、
請求項１ないし３のいずれか１項に記載のリソース管理システム。
【請求項５】
コンピュータが、複数のタイプのそれぞれのジョブ用の最初および最後の期限を当該タイプ用の分類コードに関連付けて臨界時間テーブルに保持するステップと、
前記複数のタイプのそれぞれのジョブ用の最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）を当該タイプ用の分類コードに関連付けてＷＣＥＴテーブルに保持するステップと、
ユーザからのジョブを前記複数のタイプのいずれか１つに分類するステップと、
前記ジョブを前記タイプ用の分類コードに関連付けるステップと、
前記臨界時間テーブルおよび前記ＷＣＥＴテーブルに基づいて、前記分類されたジョブ用の最初および最後の期限ならびにＷＣＥＴを決定するステップと、
前記決定した最初および最後の期限ならびに前記決定したＷＣＥＴに従って、前記分類したジョブ用のスケジュールを生成するステップと、
前記複数のタイプのそれぞれについてジョブの数を監視するステップと、
ジョブの数がその移動平均から正の方向に外れているタイプを前記複数のタイプから抽出するステップと、
前記ユーザからのジョブが前記抽出されたタイプに分類されている場合、当該ジョブを前記スケジュールにおいて優先的にスケジュールするステップと、を含む、
クラウドコンピューティング用のリソース管理方法。
【請求項６】
前記複数のタイプのそれぞれのジョブ用の属性を当該タイプ用の分類コードに関連付けて分類テーブルに保持するステップと、
前記ユーザからの前記ジョブを、前記分類テーブルにおける属性が前記ジョブ用の属性と同様である分類コードに関連付けるステップと、を含む、
請求項５に記載のソース管理方法。
【請求項７】
前記ユーザからのジョブが前記抽出されたタイプに分類されている場合、前記コンピュータが、当該ジョブ用の前記決定された最初および最後の期限を短くするステップを含む、
請求項５または６に記載のリソース管理方法。
【請求項８】
前記コンピュータが、前記複数のタイプのそれぞれのジョブについて実行時間を監視するステップと、
実行時間が１つでも当該タイプのＷＣＥＴを超えた場合、前記ＷＣＥＴテーブルにおいて当該タイプ用のＷＣＥＴを更新するステップと、を含む、
請求項５ないし７のいずれか１項に記載のリソース管理方法。
【請求項９】
複数のタイプのそれぞれのジョブ用の最初および最後の期限を当該タイプ用の分類コードに関連付けて臨界時間テーブルに保持する処理と、
前記複数のタイプのそれぞれのジョブ用の最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）を当該タイプ用の分類コードに関連付けてＷＣＥＴテーブル内に保持する処理と、
ユーザからのジョブを前記複数のタイプのいずれか１つに分類する処理と、
前記ジョブを前記タイプ用の分類コードに関連付ける処理と、
前記臨界時間テーブルおよび前記ＷＣＥＴテーブルに基づいて、前記分類されたジョブ用の最初および最後の期限ならびにＷＣＥＴを決定する処理と、
前記決定した最初および最後の期限ならびに前記決定したＷＣＥＴに従って、前記分類ジョブ用のスケジュールを生成する処理と、
前記複数のタイプのそれぞれについてジョブの数を監視する処理と、
ジョブの数がその移動平均から正の方向に外れているタイプを前記複数のタイプから抽出する処理と、
前記ユーザからのジョブが前記抽出されたタイプに分類されている場合、当該ジョブを前記スケジュールにおいて優先的にスケジュールする処理と、をコンピュータに実行させる、
プログラム。
【請求項１０】
前記複数のタイプのそれぞれのジョブ用の属性を当該タイプ用の分類コードと関連付けて分類テーブルに保持する処理と、
前記ユーザからの前記ジョブを、前記分類テーブルにおける属性が前記ジョブ用の属性と同様である分類コードに関連付ける処理と、を前記コンピュータに実行させる、
請求項９に記載のプログラム。
【請求項１１】
前記ユーザからのジョブが前記抽出されたタイプに分類されている場合、当該ジョブ用の前記決定された最初および最後の期限を短くする処理を、前記コンピュータに実行させる、
請求項９または１０に記載のプログラム。
【請求項１２】
前記複数のタイプのそれぞれのジョブについて実行時間を監視する処理と、
実行時間が１つでも当該タイプのＷＣＥＴを超えた場合、前記ＷＣＥＴテーブルにおいて当該タイプ用のＷＣＥＴを更新する処理と、を前記コンピュータに実行させる、
請求項９ないし１１のいずれか１項に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リソース管理システム、リソース管理方法、およびプログラムに関し、特に、リアルタイムのクラウドサービスを提供するリソース管理システム、リソース管理方法およびプログラムに関する。
【背景技術】
【０００２】
リアルタイムシステムのための技術のほとんどは、与えられたシステムの多くの特徴が予め知られていることを想定している（非特許文献１）。例えば、周期的タスクシステムは、ジョブリリース時刻、最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）、暗黙的または明示的な期限（非特許文献１、２）を想定している。散発的タスクシステムと非周期的タスクシステムの両方は、ジョブリリース時刻上の想定を軽減する（非特許文献１〜３）。ソフトリアルタイムシステムでは、パフォーマンスと信頼性が大きな危険にさらされない限り、期限を完全に保証するものではない（非特許文献４、５）。タスク期間を調整し、または、遅延した期限の余波を制御する技術がいくつか提案されている（非特許文献６、７）。非特許文献７は、タスク期間が与えられた弾性係数を有するスプリングとして扱われる弾性タスクモデルを開示している。しかしながら、タスク属性を知ることが必要とされ、十分なリソースが利用可能でない場合、タスクをスケジュールすることができない。
【０００３】
クラウドコンピューティングシステムは、仮想化技術（非特許文献８、９）によってリソースの増強を提供する。仮想化技術には、従来のコンピュータシステムには存在しない新しい特徴がある。例えば、クラウド・コンピュータシステムにおいては、より多くの物理リソースを使用したり、アプリケーションを配備したり、システム構成を変更することが容易である。従来のコンピュータシステムとは異なり、仮想世界で実行中のオブジェクトを移動することは、通常、実行中のオブジェクトを含む仮想マシンを全体として移動することを指す。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】J.W.S. Liu, "Real-time Systems," Prentice Hall, 2000.
【非特許文献２】J. Carpenter, et al., "A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms," J. Y-T. Leung eds. Handbook of Scheduling: Algorithms, Models and Performance Analysis, CRC Press, 2004.
【非特許文献３】N.W. Fisher, "The Multiprocessor Real-Time Scheduling of General Task Systems," Doctoral Dissertation, University of North Carolina at Chapel Hill, 2007.
【非特許文献４】J.W.S. Liu, W.K. Shih, K.J. Lin, R. Bettati and J.Y. Chung, "Imprecise Computations," Proc. IEEE, vol.82, no.1, pp.83-94, Jan. 1994.
【非特許文献５】U.C. Devi, "Soft Real-Time Scheduling on Multiprocessor," Doctoral Dissertation, University of North Carolina at Chapel Hill, 2006.
【非特許文献６】T. Chantem, X.S. Hu, and M.D. Lemmon, "Generalized Elastic Scheduling for Real-Time Tasks," IEEE Transactions on Computers, vol.58, no.4, pp.480-495, April 2009.
【非特許文献７】G. Buttazzo, G. Lipari, and L. Abeni, "Elastic Task Model for Adaptive Rate Control," Proc. 26th IEEE Real-Time Systems Symp. pp.399-409, 2005.
【非特許文献８】B. Hayes, "Cloud Computing," Communication of the ACM, vol.51, no.7, pp.9-11, 2008.
【非特許文献９】M. Armbrust, A. Fox, R. Griffith, et al., "A View of Cloud Computing," Communication of the ACM, vol.53, no.4, pp.50-58, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記非特許文献の全開示は、それらを参照することにより本明細書に組み込まれる。以下の分析は、本発明によって与えられる。
【０００６】
クラウドの中のアプリケーションおよびサービスは、ますますリアルタイムとなる傾向にある。しかしながら、これらのほとんどは、予め多くの特徴を把握できず、非常に一般的なものである。ユーザ要求の到着時間およびサービス時間は、従来のモデルによって容易かつ正確に表現することができない。些細なオペレーションについては言うまでもなく、多数のアプリケーションに対する最大応答時間、すなわち期限を定義することは困難である。データセンタは多くのリソースを備えており、リソースの増強により増大するリソース要求を満たすことができるが、不要なコストを回避するためにリソースの弾性を制御する必要がある。また、これまでユーザエンドとリソースエンドの双方に対して弾性が提供されず、したがって、これらの両エンドには協調的な弾性も提供されていない。
【０００７】
クラウドで実行される多くのサービスは、「リアルタイム（real time）」であることが要求される。リアルタイムのクラウドサービスを実現するために、以下のような技術的問題が挙げられる。
【０００８】
１．すべてのユーザ要求が、明確に定義された時間要件を有するわけではない。各ユーザ要求に対する時間要件を実際にどのように決めるかが問題となる。
【０００９】
２．多くのサービスに関して、それらがリアルタイムであるか否かはユーザの経験に依存する。通常、制御システム内で制御されるオブジェクトと比較して、ユーザの経験は時間の遅延に対して厳しくない。ユーザ要求をどの程度遅延させることができるかということと、どのユーザ要求を遅延させるべきかが問題となる。
【００１０】
３.同一のユーザ要求であっても、異なる時点、異なる社会事象、自然事象に際して、異なる時間の要件を有することがある。いかにスマートな方法での時間の要件を決定して状況の変化を認識するかが問題となる。
【００１１】
４．オペレーションの実行時間のすべてを、予め正確に知ることはできない。例えば、異なるユーザのデータの取得は、非常に異なっていることがある。さらに、オペレーションの集合の最悪実行時間（ＷＣＥＴ）を把握しておく方がよい場合がある。例えば、ボブ（Bob）は写真をアップロードするもののアリス（Alice）はアップロードしていないため、アリスがユーザデータを読み取るオペレーション「Ａ」は５秒必要とし、一方、ボブがユーザデータを読み取るオペレーション「Ｂ」は８秒必要とする。この場合、アリスとボブの間の最大時間は８秒である。一連のオペレーション（またはジョブ）に対していかにして適切にＷＣＥＴを知るかが問題となる。
【００１２】
５．既存の期限選択技術は、ジョブレベルではなくタスクレベルでのみ機能するため、期限があまり定義されていない多くの異なるジョブを扱うには融通がきかない。また、これらの技術は、期限を緩める点でリソースの弾性を考慮に入れない。これに関連した問題は、時間的に制約された多くのユーザ要求を処理し、ユーザエンドとリソースエンドの両エンドにおける弾性を調整する洗練された方法を必要する。
【００１３】
したがって、時間の要件が明確に定義されていないジョブのリアルタイム実行を実現することが望ましい。本開示の目的は、かかるニーズに貢献するリソース管理システム、リソース管理方法、および、プログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本開示の第１の側面によれば、
複数のタイプのそれぞれのジョブ用の最初および最後の期限を当該タイプ用の分類コードに関連付けて保持する臨界時間テーブルと、
前記複数のタイプのそれぞれのジョブ用の最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）を当該タイプ用の分類コードに関連付けて保持するＷＣＥＴテーブルと、
ユーザからのジョブを前記複数のタイプのいずれか１つに分類し、当該ジョブを当該タイプ用の分類コードに関連付ける分類ユニットと、
前記臨界時間テーブルおよび前記ＷＣＥＴテーブルに基づいて、前記分類されたジョブ用の最初および最後の期限ならびにＷＣＥＴを決定し、決定した最初および最後の期限ならびに決定したＷＣＥＴに従って、前記分類されたジョブ用のスケジュールを生成するコアユニットと、
前記複数のタイプのそれぞれについてジョブの数を監視し、ジョブの数がその移動平均から正の方向に外れているタイプを前記複数のタイプから抽出する認識ユニットと、を備え、
前記コアユニットは、前記ユーザからのジョブが前記分類ユニットにより抽出されたタイプに分類されている場合、当該ジョブを前記スケジュールにおいて優先的にスケジュールする、
クラウドコンピューティング用のリソース管理システムが提供される。
【００１５】
本開示の第２の側面によれば、
コンピュータが、複数のタイプのそれぞれのジョブ用の最初および最後の期限を当該タイプ用の分類コードに関連付けて臨界時間テーブルに保持するステップと、
前記複数のタイプのそれぞれのジョブ用の最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）を当該タイプ用の分類コードに関連付けてＷＣＥＴテーブルに保持するステップと、
ユーザからのジョブを前記複数のタイプのいずれか１つに分類するステップと、
前記ジョブを前記タイプ用の分類コードに関連付けるステップと、
前記臨界時間テーブルおよび前記ＷＣＥＴテーブルに基づいて、前記分類されたジョブ用の最初および最後の期限ならびにＷＣＥＴを決定するステップと、
前記決定した最初および最後の期限ならびに前記決定したＷＣＥＴに従って、前記分類したジョブ用のスケジュールを生成するステップと、
前記複数のタイプのそれぞれについてジョブの数を監視するステップと、
ジョブの数がその移動平均から正の方向に外れているタイプを前記複数のタイプから抽出するステップと、
前記ユーザからのジョブが前記抽出されたタイプに分類されている場合、当該ジョブを前記スケジュールにおいて優先的にスケジュールするステップと、を含む、
クラウドコンピューティング用のリソース管理方法が提供される。
【００１６】
本開示の第３の側面によれば、
複数のタイプのそれぞれのジョブ用の最初および最後の期限を当該タイプ用の分類コードに関連付けて臨界時間テーブルに保持する処理と、
前記複数のタイプのそれぞれのジョブ用の最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）を当該タイプ用の分類コードに関連付けてＷＣＥＴテーブル内に保持する処理と、
ユーザからのジョブを前記複数のタイプのいずれか１つに分類する処理と、
前記ジョブを前記タイプ用の分類コードに関連付ける処理と、
前記臨界時間テーブルおよび前記ＷＣＥＴテーブルに基づいて、前記分類されたジョブ用の最初および最後の期限ならびにＷＣＥＴを決定する処理と、
前記決定した最初および最後の期限ならびに前記決定したＷＣＥＴに従って、前記分類ジョブ用のスケジュールを生成する処理と、
前記複数のタイプのそれぞれについてジョブの数を監視する処理と、
ジョブの数がその移動平均から正の方向に外れているタイプを前記複数のタイプから抽出する処理と、
前記ユーザからのジョブが前記抽出されたタイプに分類されている場合、当該ジョブを前記スケジュールにおいて優先的にスケジュールする処理と、をコンピュータに実行させる、
プログラムが提供される。
【発明の効果】
【００１７】
本開示によるリソース管理システム、リソース管理方法およびプログラムは、時間の要件が明確に定義されていないジョブのリアルタイム実行を達成する必要性に寄与する。
【図面の簡単な説明】
【００１８】
【図１】図１は、実施形態に係るリソース管理システムの構成を例示する。
【図２】図２は、実施形態に係るリソース管理システムにおける分類ユニット用のキーワードテーブルおよび分類テーブルを例示する。
【図３】図３は、実施形態に係るリソース管理システムにおける分類ユニット用の階層グラフを例示する。
【図４】図４は、実施形態に係るリソース管理システムにおける認識ユニット用のランキングテーブルを例示する。
【図５】図５は、実施形態に係るリソース管理システムにおけるＷＣＥＴテーブルを例示する。
【図６】図６は、実施形態に係るリソース管理システムにおける臨界時間テーブルを例示する。
【図７】図７は、実施形態に係るリソース管理システムにおけるコアユニット用の擬似コードを例示する。
【発明を実施するための形態】
【００１９】
好ましい形態を、実施形態として以下に記載する。
【００２０】
（実施形態）
図１は、実施形態に係るリソース管理システムの構成を一例として示す。リソース管理システムは、リアルタイム・クラウドサービスを提供する。図１を参照すると、リソース管理システムは、分類ユニット１０３と、認識ユニット１０４と、臨界時間テーブル１０５と、最悪実行時間（ＷＣＥＴ：Worst Case Execution Time）テーブル１０６と、ジョブトレーサ１０７と、コアユニット１０８と、仮想マシンモニタ（ＶＭＭ：Virtual Machine Monitor）１１０と、スケジューラ１１１と、仮想マシン（ＶＭ：Virtual Machine）１１２と、を備えている。
【００２１】
ユーザ端末１０１は、通信ネットワーク１０２を介してリソース管理システムに接続されている。各ユーザ端末１０１は、リソース管理システムに要求を送信する。以下では、簡単のために、要求およびジョブという用語を同じ意味で使用する。
【００２２】
分類ユニット１０３および認識ユニット１０４は、ジョブに関する情報を取得する。分類ユニット１０３は、ジョブを分類して、各ジョブが既存のタイプに属するか否かを確認する。各ジョブには、分類コードが存在する場合、分類コードが割り当てられる。認識ユニット１０４は、ジョブおよびユーザの履歴を認識して、ユーザの行動の変化を識別する。臨界時間テーブル１０５は、典型的なオペレーションに対するデフォルト時間要件を保持する。ユーザの行動や臨界時間を認識する方法については、後に詳述する。認識ユニット１０４は、分類ユニット１０３および臨界時間テーブル１０５における分類に影響を及ぼして、状況の変化に適応する。
【００２３】
ＷＣＥＴテーブル１０６には、ＷＣＥＴが記載されている。特定のユーザの要求が、ＷＣＥＴに関連付けられているわけではない。その代わりに、要求の各タイプに対して、ＷＣＥＴが与えられる。分類ユニット１０３の分類の粗さ（grain）がユーザ要求を捉えるほど非常に細かい場合に限り、あるタイプのＷＣＥＴはユーザ要求のＷＣＥＴに完全に一致する。
【００２４】
コアユニット１０８は、分類ユニット１０３、臨界時間テーブル１０５、ＷＣＥＴテーブル１０６、ＶＭＭ１１０からのジョブの情報を受信する。そして、コアユニット１０８は、次の処理を行う。１）各ジョブをタイプにマッチさせて、適切なＷＣＥＴを見つける。２）臨界時間テーブル１０５を用いて、各ジョブに適した期限を決定する。３）期限およびリソース上の協調した弾性を有するジョブのスケジュールを計算する。４）ＶＭＭ１１０に通知して、新しいＶＭを有効化し、または、既存のＶＭを解放する。５）決められた期限１０９を有するジョブのプールを作成する。６）スケジュールをスケジューラ１１１に転送する。ジョブのエンティティは、プール１０９に格納される。
【００２５】
スケジューラ１１１は、計算されたスケジュールを用いて、ＶＭで実行するジョブを選択する。これは、中央キューを備えたマルチプロセッサシステムとしてモデル化することができる。ＶＭＭ１１０は、すべてのＶＭ１１２を管理し、新しいＶＭを作成し、使用されていない物理リソース１１３を解放する。ＶＭを調整するイベントと、ジョブをプール１０９中に準備するイベントの２つのイベントは並列に実行されることに注意されたい。ジョブトレーサ１０７は、実行中のジョブをトレースする。ジョブが終了すると、分類ユニット１０３およびＷＣＥＴテーブル１０６内のエントリを変更してもよい。
【００２６】
以下では、リソース管理システムの詳細について、図面を参照しつつ説明する。
【００２７】
本実施形態では、ユーザ要求の時間属性（例えば、時間要件）を明示的に定義する必要はない。実際には、ほとんどのサービスにおいて、時間属性は使用できない。各ユーザの要求（またはジョブ）は、例えば、ユーザ情報、ネットワーク情報、要求されたデータまたはオペレーション、いくつかの特別なリソース等の情報に関連付けられている必要がある。分類ユニット１０３は、異なるタイプの情報に基づいて、ジョブを分類する。
【００２８】
分類ユニット１０３は、キーワードテーブルおよび分類テーブルを参照してもよい。図２は、キーワードテーブルおよび分類テーブルを一例として示す。
【００２９】
図２を参照すると、キーワードテーブルＡはアプリケーションを格納し、キーワードテーブルＢはオペレーション内容を格納し、キーワードテーブルＣはユーザ名を格納する。キーワードテーブルＡ、ＢおよびＣにおいて、各エントリ２０２は、特定の特徴を表している。分類テーブル２０４は、これらのキーワードテーブルＡ、ＢおよびＣに基づいて構築することができる。これらのテーブルは、静的ではなく動的であることに注意されたい。新しいアプリケーション、オペレーション、またはデータ項目が表れたときに、新しいエントリをこれらのテーブルに追加してもよい。逆に、アプリケーションまたはデータの寿命が終わると、古いエントリをこれらのテーブルから削除してもよい。
【００３０】
分類テーブル２０４には、キーワードテーブルＡ、ＢおよびＣにこれらのエントリの様々な可能な組み合わせが記載される。新しいジョブの情報は、キーワードテーブルＡ、ＢおよびＣのエントリを用いて符号化され、新しいジョブのコードに対する最大類似性を有する分類テーブル２０４内のエントリは、新しいジョブを識別するのに用いられる。ジョブの各タイプは、例えば、ハードリアルタイム、ソフトリアルタイム、非リアルタイム、特別なリソースを必要とするかどうか、いくつかのさらなるイベント等を待機する必要があるかどうか等といった、固有の属性２０６を有する。属性は、サービスプロバイダまたは（許可された）ユーザによって明示的に設定してもよい。
【００３１】
例えば、ユーザであるダニエルがいくつかのシステム動作を監視するアプリケーションを登録し、彼がシステム管理者である場合、ジョブはハードリアルタイム属性と、例えばユーザ認証のような他のジョブとの依存関係とを有するＡ１Ｂ２Ｃ１と特定される。
【００３２】
分類テーブル２０４における分類コードは、臨界時間テーブル１０５における分類コード、および、ＷＣＥＴテーブル１０６における分類コードと同じである。すなわち、分類コードは、ＷＣＥＴおよび臨界時間とも関連付けられている。
【００３３】
キーワードテーブルＡ、ＢおよびＣ内のエントリは、階層グラフに編成することができる。この場合、分類テーブル２０４内のエントリは、階層グラフの頂点に対応する。最大類似度を決定することは、可能な限り低いレベルで頂点を見つけることに相当する。図３は、図２に示した分類テーブル２０４に対応する階層グラフを示す。
【００３４】
認識ユニット１０４は、サービスの変化を検出する。本実施形態では、以下の変更に着目している。ランタイムにおいて、多くの変更が起きることが想定されている。認識ユニット１０４は、ユーザが払う注意が増大することにより時間要件が暗黙的に変更される場合のみを対象とし、一方、明示的な変更は分類ユニット１０３によって捉えられる。
【００３５】
一例として、以下の例が考えられる。地震のような大災害が起こる場合、多くの人々は、災害に関する情報やデータを取得することを望む。そのような場合の要求が他の要求や以前の要求と同じように取り扱われる場合、サービスはリアルタイムにならない。なぜなら、ユーザの体感が変わるからである（すなわち、ユーザは大惨事の前には、大惨事の後に許容できる時間よりもはるかに長い待機時間を許容することができる）。強度を静的に検出する代わりに、タイムリーに強度を検出すべきである。
【００３６】
認識ユニット１０４は、発生の頻度を使用してもよい。同一の分類コードが付されたタイプに対して、ジョブの履歴が移動平均（ＭＡ:Moving Average）法によって記憶される。要求のソースと、移動平均のウィンドウ内のアクセス数の両方が記録される。その後、移動平均からのデータの変化を使用して、物理的な世界の変化が評価される。
【００３７】
認識ユニット１０４は、ランキングテーブルを使用してもよい。図４は、認識ユニット１０４用のランキングテーブルを一例として示す。図４を参照すると、各エントリは、分類コード３０２、ソース２０２、アクセス３０４、移動平均（ＭＡ：Moving Average）の傾向３０５、および、ランキング３０６を含む。
【００３８】
分類コード３０２は長さが異なるので、異なるランキングテーブルが存在しなければならない。使用すべきテーブルは、柔軟性が提供されるように、サービスプロバイダによって決定してもよい。プロバイダによって管理されているディスク使用量を報告する場合のように、一般的なオペレーションの集合が高感度であることが期待されている場合、短いコードを有するテーブルを使用することが好ましい。この例では、テーブル内において、最低レベルのコードが想定される。
【００３９】
ソース３０３は、ユーザまたはネットワークのアドレスを指定する。アクセス３０４は、コードに対する要求の数である。例えば５分間のような移動平均（ＭＡ：Moving Average）ウィンドウが、サービスプロバイダによって定義される。ソース３０３およびアクセス３０４は、ウィンドウ内の全カウントである。同一のコードの最後のウィンドウと比較し、ＭＡデータの傾向をフィールド３０５から知ることができる。他のコードとの比較により、ランキング３０６も知ることができる。
【００４０】
ランキング３０６は、様々な方法で使用することができる。例えば、サービスプロバイダは、コアユニット１０８のスケジュールの計算において最初の１０個の記録のジョブの期限を短くしてもよく、あるいは、異なるランクについて異なるスケールで期限を短縮してもよい。後で、コアユニット１０８用のアルゴリズムの一例を、バイナリマークと呼ばれる前者の場合について示す。
【００４１】
図５は、最悪実行時間（ＷＣＥＴ）テーブル１０６の一例を示す。図５を参照すると、ＷＣＥＴテーブル１０６は、ジョブの各タイプの最悪実行時間（ＷＣＥＴ）を各タイプに対する分類コードに関連付けて保持する。ＷＣＥＴテーブル１０６のレコードのうちのあるものは事前に設定することができ、その他のものはジョブの実行後にジョブトレーサ１０７によって登録することができる。
【００４２】
図６は、臨界時間テーブル１０５の一例を示す。図６を参照すると、臨界時間テーブル１０５は、あるタイプのジョブ用の臨界時間（例えば、最初の期限と最後の期限）を当該タイプの分類コードに関連付けて保持する。
【００４３】
臨界時間テーブル１０５とＷＣＥＴテーブル１０６は、同一の分類コードを保持する。ただし、データフィールドはこれらの２つのテーブル間で異なる。ＷＣＥＴテーブル１０６内のデータフィールドは、各エントリ（図５）に対するＷＣＥＴを保持する。一方、臨界時間テーブル１０５のデータフィールドは、各エントリに対する最も早い期限（ＥＤ：Earliest Deadline）、最も遅い期限（ＬＤ：Latest Deadline）、および、マークを格納する（図６）。
【００４４】
ＥＤおよびＬＤはユーザの経験に基づいて決定されるため、本開示に係るリソース管理システムはユーザ指向である。一例として、ユーザがウェブページのリンクをクリックすると、最終の応答時間は、ある報告によれば、４、８ないし１０秒を超えるものであってはならない。また、明らかに、誰も０．５秒の応答時間と０．１秒の応答時間とを区別することはできない。したがって、ＥＤおよびＬＤは、それぞれ０．５秒と１０秒に設定してもよい。
【００４５】
別の例として、ビデオオンデマンド（ＶＯＤ：Video on Demand）サービスにおいて、秒間フレーム数（ＦＰＳ：Flames per Second）は１４から２５の範囲である。１４よりも低いＦＰＳでは人が検出できる大幅な遅延が生じ、２５よりも高いＦＰＳでは明らかにユーザの体感を向上させない。このように、ＶＯＤに対するＥＤおよびＬＤを計算することができる。
【００４６】
ほとんどのＥＤおよびＬＤはユーザの経験によって決定される。いくつかのＥＤおよびＬＤは、システム性能を向上させるような特定の目的のためにサービスプロバイダによって任意に設定されてもよい。
【００４７】
マークは、サービスプロバイダまたはユーザによって明示的に与えられてもよく、あるいは、認識ユニット１０４によって暗黙的に与えられてもよい。自然数マークまたはバイナリマークのような２つのタイプのマークを使用することができる。マークの数がより多くなると、より細かいサービスとなり、結果としてより多くのコストが必要となる。
【００４８】
コアユニット１０８は、スケジュールを計算し、期限およびリソースの弾性を決定する。コアユニット１０８はアルゴリズムを備え、分類ユニット１０３（ジョブごとに分類コードを提供する）内の情報およびデータ、臨界時間テーブル１０５（ＥＤ、ＬＤ、およびマークを含む各ジョブ用の臨界時間を提供する）、ＷＣＥＴテーブル１０６（各ジョブ用のＷＣＥＴを提供する）、ＶＭＭ１１０（現在のＶＭの状態を提供する）、および、ジョブ自体が入力される。
【００４９】
アルゴリズムの例を図７に示す。図７に示す例はバイナリマークとジョブのリソース依存性を考慮し、パーティションアルゴリズムとしては、ＥＤＦ−ＦＦ（Earliest Deadline First - First Fix）アルゴリズムを想定している。このアルゴリズムは、異なるマークを使用してアルゴリズムを分割することによって、他のバージョンに変更することができる。
【００５０】
図７に示すアルゴリズムの基本的な考え方は、ジョブを２つの集合に分割し、２つの集合を異なる方法でスケジュールすることである。最初のセットは期限を遅らせることができず、分割アルゴリズムによって保証することができない期限が存在する場合は、より多くのＶＭが追加される。第２のセットの期限は遅らせることができるが、最も早い期限は守られるようにし、ＬＤが保証されない場合に限り、新しいＶＭが作成される。新しいＶＭが必要とされるたびに、アルゴリズムは、十分なリソースが利用可能であることを確認するためにＶＭＭ１１０に照会する。アルゴリズムが実行された後、スケジュールが作成され、現在のＶＭを拡張する情報も準備ができる。
【００５１】
その後、ジョブはスケジュールに基づいて期限と関連付けられる。臨界時間テーブル１０５の時間は期限ではなく、期限の下限と上限であることに注意されたい。一方、スケジュールはジョブスケジューラ１１１に送信され、拡大したＶＭの情報はＶＭＭ１１０に送信される。ＶＭ１１２が準備された場合、スケジューラ１１１は、スケジュールに基づいてジョブをディスパッチする。
【００５２】
ユーザエンドに対して、リソース管理システムは、ユーザ要求に対して適切な時間制約を自動で設定して調整することにより、非リアルタイムサービスをリアルタイムサービスに変換する。一方、リソースエンドに対して、リソース管理システムは、ユーザからのリソースへの要求と、クラウドデータセンタからのリソースの供給とのバランスをとる。したがって、リソース管理システムは、リアルタイムのクラウドサービスにおいて、ユーザエンドおよびリソースエンドの両エンドに対して２重の弾性を実現する。
【００５３】
なお、本開示に記載された図面を参照する参照符号または数字は、より良い図示の目的のために単に与えられ、本開示を図示された形態または実施例に限定するものではない。
【００５４】
上記非特許文献の開示は、その参照により本明細書に組み込まれる。実施形態の改変および調整は、本発明の全体的開示（特許請求の範囲を含む）の範囲内で可能であり、本発明の基本的技術思想に基づく。様々な組み合わせ、および、様々な開示された要素（各請求項の各要素、各実施形態の各要素、各図の各要素等を含む）の選択は、本発明の特許請求の範囲内で可能である。つまり、本発明はもちろん特許請求の範囲および技術的思想を含む全開示により当業者によってなされ得る様々な変形および調整を含む。特に、ここで開示される任意の数値範囲は、任意の中間値または開示された範囲内の部分範囲も、その特別な詳しい説明なくても具体的に開示されていると解釈されるべきである。
【符号の説明】
【００５５】
１０１  ユーザ端末
１０２  通信ネットワーク
１０３  分類ユニット
１０４  認識ユニット
１０５  臨界時間テーブル
１０６  最悪実行時間（ＷＣＥＴ）テーブル
１０７  ジョブトレーサ
１０８  コアユニット
１１０  仮想マシンモニタ（ＶＭＭ）
１１１  スケジューラ
１１２  仮想マシン（ＶＭｓ）
１１３  物理リソース
２０１  キーワードテーブル
２０２  エントリ
２０３  キーワード
２０４  分類テーブル
２０５  分類コード
２０６  属性
３０２  分類コード
３０３  ソース
３０４  アクセス
３０５  ＭＡの傾向
３０６  ランキング
【図１】
0005987987.tif 000002
【図２】
0005987987.tif 000003
【図３】
0005987987.tif 000004
【図４】
0005987987.tif 000005
【図５】
0005987987.tif 000006
【図６】
0005987987.tif 000007
【図７】
0005987987.tif 000008