JP5737057B2 - プログラム、ジョブスケジューリング方法、および情報処理装置 - Google Patents

Description

本発明は、ジョブ実行のスケジューリングのためのプログラム、ジョブスケジューリング方法、および情報処理装置に関する。

複数の計算資源を用いて、ジョブを処理するコンピュータシステムがある。計算資源は、例えばプロセッサ、プロセッサ内のコア、または計算ノードの単位で管理される。例えばＨＰＣ（High Performance Computing）を実現するコンピュータシステムでは、計算資源として複数の計算ノードが設けられ、計算ノードによってジョブが実行される。計算ノードでのジョブの実行スケジュールは、例えば管理ノードによって管理される。管理ノードは、例えば計算ノードが効率的に稼働するように、ジョブ実行のスケジューリングを行う。

コンピュータシステムで実行されるジョブには、逐次ジョブと並列ジョブとがある。逐次ジョブは、１つの計算資源で処理されるジョブである。並列ジョブは、複数の計算資源によって並列に処理されるジョブである。並列ジョブにおいて、ジョブの並列処理に使用する計算資源数は、並列度と呼ばれる。またジョブの実行に要する時間は、ジョブごとに異なる。例えば、数分または数時間程度の比較的短い時間で処理が完了するジョブがある。他方、処理の完了に数日または数週間を要する、比較的処理時間の長いジョブもある。

そこで、逐次ジョブか並列ジョブか、並列ジョブであれば並列度はどの程度か、および各ジョブの処理に要する最大の時間（最大実行時間）などに基づいて、各計算資源へのジョブ実行のスケジューリングが行われる。例えば、ＣＰＵ（Central Processing Unit）の高稼働率を実現するスケジューリングシステムが考えられている。また、実行中のジョブのチェックポイント取得・ジョブ再開技術を利用して、効率的なスケジューリングを行うことも提案されている。チェックポイント取得・ジョブ再開技術は、実行中のジョブをチェックポイントで一時停止し、後にチェックポイントからジョブを再開するものである。

特開２０１０−１８２１９９号公報

Duell, J.; Hargrove, P.; and Roman, E., "Requirements for Linux Checkpoint/Restart", Berkeley Lab Technical Report (publication LBNL-49659), May 2002.

しかし、ジョブの一時停止を許容したジョブスケジューリングを行うと、ジョブの一時停止を許容したことにより利益を享受できるユーザがいる一方、ジョブの一時停止を許容したことで損失を受けるユーザもいる。例えば、ジョブスケジューリングでは、通常は先に依頼されたジョブから順に実行を開始するようにスケジューリングされる。このときジョブの一時停止を許容したスケジューリングを行うと、先に依頼されたジョブの実行が一時停止し、そのジョブより後に依頼されたジョブを先行して実行するようなスケジュールが組まれる可能性がある。この場合、一時停止されたジョブの実行を依頼したユーザにとっては、時間的な損失が生じたこととなる。このようなジョブの実行順の入れ替えが頻発すると、それぞれのジョブの実行を依頼したユーザに対するサービスの公平性が低下してしまう。

従来では、このようなジョブを一時停止することによる損失の発生を受け入れてまでジョブ一時停止による稼働率向上を図ることが適切なのか否かについて十分な検討をせずに、ジョブの一時停止を許容したスケジューリングが行われることとなる。

１つの側面では、本発明は、ジョブの一時停止を許容したスケジューリングが適切か否かを判断することができるプログラム、ジョブスケジューリング方法、および情報処理装置を提供することを目的とする。

１つの案では、以下の処理をコンピュータに実行させるプログラムが提供される。
コンピュータは、複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成する。またコンピュータは、複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成する。その後、コンピュータは、第１のスケジュールと第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算する。そしてコンピュータは、利益を示す値と損失を示す値とを比較して、第１のスケジュールと第２のスケジュールとのうち、適切なスケジュールを決定する。

１態様によれば、ジョブの一時停止を許容したスケジューリングが適切か否かを容易に判断することができる。

第１の実施の形態に係る装置の機能の一構成例を示す図である。 第１の実施の形態におけるスケジューリングの手順の一例を示すフローチャートである。 第１の実施の形態による適切なスケジュールの判定例を示す図である。 第２の実施の形態のシステムの一構成例を示す図である。 本実施の形態に用いる管理ノードのハードウェアの一構成例を示す図である。 管理ノードの機能を示すブロック図である。 ジョブ情報の一例を示す図である。 スケジュール記憶部のデータ構造の一例を示す図である。 スケジューリング処理の手順を示すフローチャートである。 待機ジョブのスケジューリング過程の一例を示す図である。 スケジューリング結果の一例を示す図である。 スケジュール最適化処理の手順の一例を示すフローチャートである。 稼働率の判定例を示す図である。 １つ目の実行中ジョブの凍結候補リストへの追加状況を示す図である。 ２つ目の実行中ジョブの凍結候補リストへの追加状況を示す図である。 ジョブ凍結による利益と損失との比較例を示す図である。 ジョブ凍結による稼働率の向上度合いの判断例を示す図である。 再スケジューリング処理の手順を示すフローチャートである。 再スケジューリング処理に伴う各キューの状態遷移の一例を示す図である。

以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
図１は、第１の実施の形態に係る装置の機能の一構成例を示す図である。情報処理装置１は、複数の計算資源２ａ，２ｂ，２ｃ，・・・に実行させるジョブの実行スケジュールを作成する。情報処理装置１は、作成手段１ａ、記憶手段１ｂ、計算手段１ｃ、決定手段１ｄ、および実行制御手段１ｅを有する。

作成手段１ａは、第１のスケジュールと第２のスケジュールとを作成する。第１のスケジュールは、複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるスケジュールである。第２のスケジュールは、複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと実行待ちのジョブとのそれぞれを計算資源に実行させるスケジュールである。例えば作成手段１ａは、実行の依頼を受けたジョブに関するジョブ情報に基づいて、スケジュールを作成する。ジョブ情報には、例えば実行するジョブが逐次ジョブか並列ジョブかを示すジョブ種、並列ジョブの場合の並列度、ジョブの最大実行時間などの情報が含まれる。作成手段１ａは、作成した第１のスケジュールと第２のスケジュールとを、例えば記憶手段１ｂに格納する。

記憶手段１ｂは、第１のスケジュールと第２のスケジュールとを記憶する。
計算手段１ｃは、第１のスケジュールと第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算する。例えば計算手段１ｃは、第１のスケジュールよりも第２のスケジュールにおいて実行開始時刻が早く設定されたジョブについての、第１のスケジュールと第２のスケジュールとにおける実行開始時刻の差に基づいて、利益を示す値を計算する。例えば計算手段１ｃは、第１のスケジュールでは即時に実行開始できないが、第２のスケジュールでは即時に実行開始可能なジョブを検出する。次に計算手段１ｃは、検出したジョブそれぞれについて、第１のスケジュールと第２のスケジュールとにおけるジョブの実行開始時刻の差に、そのジョブの実行に使用する計算資源の数を乗算する。そして計算手段１ｃは、ジョブごとの乗算結果の合計を、利益を示す値とする。

また計算手段１ｃは、例えば、第２のスケジュールにおいて一時停止されるジョブの一時停止期間の長さに基づいて、損失を示す値を計算する。例えば計算手段１ｃは、複数の計算資源のいずれかで実行中のジョブのうち、第２のスケジュールにおいて一時停止されるジョブを検出する。次に計算手段１ｃは、検出したジョブそれぞれについて、第２のスケジュールにおけるジョブの一時停止期間の長さに、そのジョブの実行に使用する計算資源の数を乗算する。そして計算手段１ｃは、ジョブごとの乗算結果の合計を、損失を示す値とする。

決定手段１ｄは、利益を示す値と損失を示す値とを比較して、第１のスケジュールと第２のスケジュールとのうち、適切なスケジュールを決定する。例えば決定手段１ｄは、利益と損失との比率に基づいて適切なスケジュールを決定する。例えば決定手段１ｄは、利益を示す値を、損失を示す値で除算する。決定手段１ｄは、除算した結果が所定の閾値より大きい場合、第２のスケジュールが適切であると決定する。このときの閾値は、例えば１以上の値とする。

実行制御手段１ｅは、決定手段１ｄによって適切であると決定されたスケジュールに従って、計算資源２ａ，２ｂ，２ｃ，・・・に対するジョブの実行を指示する。
なお、作成手段１ａ、計算手段１ｃ、決定手段１ｄ、および実行制御手段１ｅは、情報処理装置１が有するＣＰＵにより実現することができる。また、記憶手段１ｂは、情報処理装置１が有するＲＡＭ（Random Access Memory）やハードディスクドライブ（ＨＤＤ:Hard Disk Drive）などにより実現することができる。

また、図１に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
このような機能を有する情報処理装置１により、ジョブのスケジューリングが行われる。

図２は、第１の実施の形態におけるスケジューリングの手順の一例を示すフローチャートである。以下、図２に示す処理をステップ番号に沿って説明する。
［ステップＳ１］作成手段１ａは、複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成する。作成手段１ａは、作成した第１のスケジュールを、例えば記憶手段１ｂに格納する。

［ステップＳ２］作成手段１ａは、複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成する。作成手段１ａは、作成した第２のスケジュールを、例えば記憶手段１ｂに格納する。

なおステップＳ１とステップＳ２との処理は、実行順が逆であってもよい。
［ステップＳ３］計算手段１ｃは、例えば、記憶手段１ｂから第１のスケジュールと第２のスケジュールとを取得する。そして計算手段１ｃは、第１のスケジュールと第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算する。

［ステップＳ４］決定手段１ｄは、利益を示す値と損失を示す値とを比較して、第１のスケジュールと第２のスケジュールとのうち、適切なスケジュールを決定する。例えば決定手段１ｄは、利益を示す値を、損失を示す値で除算する。決定手段１ｄは、除算した結果が所定の閾値より大きい場合、第２のスケジュールが適切であると決定する。逆に、除算した結果が所定の閾値以下の場合、決定手段１ｄは、第１のスケジュールが適切であると決定する。

［ステップＳ５］実行制御手段１ｅは、適切であると決定されたスケジュールに従って、計算資源にジョブを実行させる。
このようにして、ジョブの一時停止を許容しないスケジューリングが適切なのか、ジョブの一時停止を許容するスケジューリングが適切なのかが判断される。そして、適切と判断された方法でスケジューリングされたスケジュールに従って、ジョブの実行が制御される。

図３は、第１の実施の形態による適切なスケジュールの判定例を示す図である。図３の例では、２つのジョブ５ａ，５ｂが実行中のときに、並列度の高いジョブ５ｃの実行スケジュールを決定する場合を想定している。ジョブ５ｃは、すべての計算資源を使用して実行する。

第１のスケジュール３では、実行中のジョブ５ａ，５ｂは、一時停止されずに最後まで実行される。そしてジョブ５ｂの処理が終了した時点でジョブ５ｃが実行される。
第２のスケジュール４では、実行中のジョブ５ａ，５ｂの処理が一時停止される。そしてジョブ５ｃが即時に実行される。一時停止されたジョブ５ａ，５ｂは、ジョブ５ｃの処理終了後に再開される。

このような場合、例えばジョブの一時停止による利益を示す値として、ジョブの一時停止を許容することでジョブ５ｃの実行開始時刻が早まる時間Ｔ_cと、ジョブ５ｃの並列度Ｒ_cとが用いられる。例えば、時間Ｔ_c×並列度Ｒ_cの乗算結果が利益を示す値となる。

またジョブの一時停止による損失を示す値として、一時停止するジョブ５ａ，５ｂの一時停止期間の長さを示す時間Ｔ_a，Ｔ_bと、ジョブ５ａ，５ｂの並列度Ｒ_a，Ｒ_bとが用いられる。例えば、時間Ｔ_a×並列度Ｒ_aの乗算結果と時間Ｔ_b×並列度Ｒ_bの乗算結果との合計が、損失を示す値となる。

例えば、利益を示す値を、損失を示す値で除算した結果が、所定の閾値Ｐ₀より大きければ、第２のスケジュール４が適切であると判断される。また利益を示す値を損失を示す値で除算した結果が、所定の閾値Ｐ₀以下であれば、第１のスケジュール３が適切であると判断される。

閾値Ｐ₀は、例えば１以上の値が設定される。ここで、ジョブの一時停止に伴うリスクを、閾値Ｐ₀に反映させることができる。例えば閾値Ｐ₀が大きくなるほど、ジョブの一時停止を許容したスケジュールが適切であると判断するための条件が厳しくなる。そこで、ジョブ一時停止に伴うリスクが大きい場合、閾値Ｐ₀を大きくすることで、そのリスクを凌駕するメリットがある場合にのみ、ジョブの一時停止を許容したスケジュールが適用されることとなる。

なおジョブの一時停止に伴うリスクとしては、例えばジョブの一時停止または再開の失敗の可能性がある。一時停止または再開に失敗すると、ジョブを改めて最初から実行することになり、処理効率が悪化する。そこでジョブの一時停止または再開の失敗の可能性を高い場合、閾値Ｐ₀の値を大きくすることで、ジョブの一時停止または再開が失敗するという事態の発生頻度を抑止できる。

以上のようにして、ジョブの一時停止を行うことによる利益と損失とのバランスを取ったスケジュールの作成が可能となる。これにより、必要以上のジョブの一時停止を抑止でき、ジョブの実行を依頼したユーザに対する公平なサービスの提供が可能となる。

〔第２の実施の形態〕
第２の実施の形態は、計算資源として複数の計算ノードを用いたコンピュータシステムにおいて、ジョブ実行の適切なスケジューリングを行うものである。なお、以下の説明では、ジョブを一時停止させることを、ジョブを凍結すると呼ぶこととする。

また第２の実施の形態では、ジョブを凍結することによる利益と損失とのバランスに加え、ジョブを凍結することによる稼働率の向上度合いも考慮して、適切なスケジューリングを行う。

すなわち、ジョブの凍結を許容するスケジューリングを行っても、ジョブの凍結を許容しない場合に比べ、稼働率がほとんど向上しないこともあり得る。このような場合、ジョブの凍結に伴うリスクを負ってまで、稼働率の向上させるメリットがない。ところが、ＨＰＣでは、様々なジョブが数百、数千の単位で存在し、稼働率の向上度合いの把握は容易ではない。そこで第２の実施の形態では、ジョブの凍結を許容しない場合と比べたときの、ジョブの凍結を許容してスケジューリングした場合の計算ノードの稼働率の向上度合いを把握し、適切なスケジュールを作成する。

図４は、第２の実施の形態のシステムの一構成例を示す図である。管理ノード１００には、複数の計算ノード３１，３２，３３，・・・が接続されている。管理ノード１００は、計算ノード３１，３２，３３，・・・を管理するコンピュータである。計算ノード３１，３２，３３，・・・は、ジョブを実行するコンピュータである。計算ノード３１，３２，３３，・・・は、並列ジョブの場合、複数の計算ノードが互いに連携してジョブを実行する。

また管理ノード１００には、端末装置２１が接続されている。端末装置２１は、実行するジョブの内容を指示するユーザが使用するコンピュータである。ジョブの実行内容を指示する場合、ユーザは、例えば端末装置２１に対して、実行するジョブの内容を入力する。ジョブの内容としては、例えばジョブの実行に用いるプログラムやデータ、逐次ジョブか並列ジョブかのジョブ種の指定、並列ジョブであれば並列度、ジョブの実行に要する最大の時間（最大実行時間）などが含まれる。そしてユーザの指示に応じて、端末装置２１から管理ノード１００へ、ジョブの実行内容が送信される。

管理ノード１００は、端末装置２１からのジョブの実行依頼を受け付ける。そして、管理ノード１００は、計算ノード３１，３２，３３，・・・にジョブの実行要求を送信し、計算ノード３１，３２，３３，・・・からジョブの処理結果を受け取る。

図５は、本実施の形態に用いる管理ノードのハードウェアの一構成例を示す図である。管理ノード１００は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０９を介してＲＡＭ１０２と複数の周辺機器が接続されている。

ＲＡＭ１０２は、管理ノード１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。

バス１０９に接続されている周辺機器としては、ＨＤＤ１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７，１０８がある。

ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、管理ノード１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。

グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。

入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。

光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。

通信インタフェース１０７は、ネットワークを介して、端末装置２１に接続されている。通信インタフェース１０７は、端末装置との間でデータの送受信を行う。
通信インタフェース１０８は、ネットワークを介して、計算ノード３１，３２，３３，・・・に接続されている。通信インタフェース１０８は、計算ノード３１，３２，３３，・・・との間でデータの送受信を行う。

以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。なお図５には管理ノード１００のハードウェア構成例を示したが、計算ノード３１，３２，３３，・・・も、管理ノード１００と同様のハードウェアで実現することができる。また、第１の実施の形態に示した情報処理装置１も、図５に示した管理ノードと同様のハードウェアにより実現することができる。

図６は、管理ノードの機能を示すブロック図である。図６の例では、管理ノード１００が有する機能のうち、ジョブ実行のスケジュールに関する機能のみを示している。
管理ノード１００は、ジョブ実行のスケジュール管理を行うスケジューラ１００ａを有している。スケジューラ１００ａは、ジョブ管理部１１０、待機キュー１２０、実行中キュー１３０、凍結キュー１４０、ジョブスケジューリング部１５０、スケジュール情報記憶部１６０、およびジョブ操作部１７０を有している。

ジョブ管理部１１０は、端末装置２１から入力されたジョブの実行依頼に応じて、実行依頼で指定されたジョブの内容を示すジョブ情報を生成する。生成されるジョブ情報は、そのジョブの実行に利用される各種情報を含んでいる。例えば生成されるジョブ情報には、ジョブの実行の手順が記述されたプログラムを一意に指定する情報や、そのプログラムに渡すデータが格納されたファイルを一意に指定する情報が含まれる。ジョブ管理部１１０は、ジョブ情報を生成すると、生成したジョブ情報を、待機キュー１２０に登録（キューイング）する。またジョブ管理部１１０は、ジョブの実行結果をジョブ操作部１７０から受け取ると、受け取った実行結果を、例えば端末装置２１に送信する。

またジョブ管理部１１０は、所定のタイミングでジョブスケジューリング部１５０に対してスケジューリングを要求する。例えばジョブ管理部１１０は、新たに生成したジョブ情報を待機キュー１２０に登録した際に、ジョブスケジューリング部１５０に対してスケジューリングを要求する。また、ジョブ管理部１１０は、ジョブの処理結果をジョブ操作部１７０から取得した際にも、ジョブスケジューリング部１５０に対してスケジューリングを要求する。

待機キュー１２０は、待機状態のジョブのジョブ情報を保持するバッファである。以下、待機キュー１２０に登録されているジョブ情報に対応するジョブを、特に待機ジョブと呼ぶこととする。

実行中キュー１３０は、実行中のジョブのジョブ情報を保持するバッファである。以下、実行中キュー１３０に登録されているジョブ情報に対応するジョブを、特に実行中ジョブと呼ぶこととする。

凍結キュー１４０は、凍結されたジョブのジョブ情報を記憶するバッファである。
待機キュー１２０、実行中キュー１３０、および凍結キュー１４０としては、例えばＲＡＭ１０２またはＨＤＤ１０３の記憶領域の一部が使用される。

ジョブスケジューリング部１５０は、スケジューリング要求に応じて、待機キュー１２０に登録されたジョブ情報で示されるジョブを計算ノードに実行させるスケジュールを作成する。ジョブスケジューリング部１５０は、例えば、ジョブの凍結を許容しない場合と許容する場合との２通りのスケジュールを作成する。ジョブスケジューリング部１５０は、作成したスケジュールを、スケジュール情報記憶部１６０に格納する。

ジョブスケジューリング部１５０は、例えば作成したスケジュールのうち、ジョブの凍結の利益と損失などを考慮し、適切なスケジュールを決定する。そしてジョブスケジューリング部１５０は、適切と判断したスケジュールに従って、実行可能なジョブの実行開始をジョブ操作部１７０に依頼する。その際、ジョブスケジューリング部１５０は、ジョブ情報と、ジョブの実行に使用するハードウェア資源およびソフトウェア資源を示す実行資源情報とを、ジョブ操作部１７０に渡す。実行資源情報には、例えばジョブを実行する計算ノードの指定が含まれる。ジョブスケジューリング部１５０は、実行開始を依頼したジョブのジョブ情報を、待機キュー１２０から実行中キュー１３０に移動させる。

ジョブスケジューリング部１５０は、ジョブの凍結を行う場合、ジョブ操作部１７０に対してジョブの凍結要求を通知する。またジョブスケジューリング部１５０は、凍結したジョブのジョブ情報を、実行中キュー１３０から凍結キュー１４０に移動する。そしてジョブスケジューリング部１５０は、作成したスケジュールに従って実行要求が計算ノードに送信された後、凍結キュー１４０に移動したジョブのジョブ情報を、待機キュー１２０に移動する。

スケジュール情報記憶部１６０は、スケジュールを記憶する。例えばＲＡＭ１０２またはＨＤＤ１０３の記憶領域の一部がスケジュール情報記憶部１６０として使用される。
ジョブ操作部１７０は、ジョブの実行に関する操作を行う。例えばジョブ操作部１７０は、実行するジョブのジョブ情報と実行資源情報を受け取ると、そのジョブの実行要求を、実行資源情報に示される計算ノードに送信する。送信される実行要求には、例えばジョブの実行に用いられるプログラムやデータを指定する情報が含まれる。なおジョブ操作部１７０は、実行するジョブが並列ジョブであれば、複数の計算ノードに対してジョブの実行要求を送信する。これにより、並列ジョブの実行要求を受信した複数の計算ノードが、互いに連携して並列ジョブを実行する。さらに、ジョブ操作部１７０は、計算ノードから、処理が完了したジョブの実行結果を取得し、その実行結果をジョブ管理部１１０に通知する。

なお、図１に示す第１の実施の形態の作成手段１ａ、計算手段１ｃ、および決定手段１ｄの機能は、図６のジョブスケジューリング部１５０で実現される。また図１に示す第１の実施の形態の実行制御手段１ｅの機能は、ジョブスケジューリング部１５０とジョブ操作部１７０との連携動作により実現される。さらに図１に示す記憶手段１ｂの機能は、スケジュール情報記憶部１６０で実現される。

また、図６に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
次に、ジョブ管理部１１０が生成するジョブ情報について説明する。

図７は、ジョブ情報の一例を示す図である。ジョブ情報５１には、例えばジョブ識別番号、並列度、最大実行時間などの情報が含まれる。ジョブ識別番号は、実行するジョブの識別番号である。並列度は、ジョブを並列処理で実行するノード数である。なおジョブが逐次ジョブであれば、並列度に「１」が設定される。最大実行時間は、ジョブの実行に要する最大時間である。

なお図７に示した情報以外にも、ジョブ情報５１には、例えばジョブの実行に用いるソフトウェア名、パラメータ、使用データが格納されたファイル名などの各種情報が含まれる。

ジョブスケジューリング部１５０は、待機キュー１２０に格納されたジョブ情報を参照することで、ジョブを実行する計算ノード、およびジョブの実行開始時刻を示すスケジュールを作成できる。例えば、ジョブの凍結を許容しない場合と、ジョブの凍結を許容する場合との２通りのスケジュールが作成される。作成されたスケジュールは、スケジュール情報記憶部１６０に格納される。

図８は、スケジュール記憶部のデータ構造の一例を示す図である。スケジュール情報記憶部１６０には、現行スケジュール１６１、凍結候補リスト１６２、および仮スケジュール１６３が格納されている。

現行スケジュール１６１は、現時点で適用されているジョブの実行スケジュールである。現行スケジュール１６１には、ジョブ識別番号、ノード番号、開始時刻、および終了時刻の欄が設けられている。ジョブ識別番号の欄には、計算ノードに実行させるジョブのジョブ識別番号が設定される。ノード番号の欄には、ジョブ識別番号で示されるジョブを実行させる計算ノードのノード番号が設定される。実行するジョブが逐次ジョブであれば、ノード番号の欄には、１つの計算ノードのノード番号が設定される。実行するジョブが並列ジョブであれば、ノード番号の欄には、そのジョブの並列度に応じた数のノードのノード番号が設定される。開始時刻の欄には、ジョブ識別番号で示されるジョブの実行開始時刻が設定される。終了時刻の欄には、ジョブ識別番号で示されるジョブの実行終了時刻が設定される。なおジョブの実行終了時刻は、実行開始時刻から、そのジョブの最大実行時間経過後の時刻である。

凍結候補リスト１６２は、仮スケジュールを作成する際の凍結候補のジョブのリストである。凍結候補リスト１６２には、実行を凍結する対象として選択されたジョブのジョブ識別番号が設定される。

仮スケジュール１６３は、スケジュール最適化の際に、現行スケジュール１６１との比較用に作成されるスケジュールである。例えば、仮スケジュール１６３は、凍結候補リスト１６２に示されるジョブを凍結した場合のスケジュールである。仮スケジュール１６３の方が現行スケジュール１６１より適切と判断されれば、その時点で凍結候補リスト１６２に登録されているジョブを凍結して、現行スケジュール１６１が更新される。仮スケジュール１６３には、ジョブ識別番号、ノード番号、開始時刻、および終了時刻の欄が設けられている。仮スケジュール１６３の各欄に設定される情報は、現行スケジュール１６１の同名の欄と同種の情報である。

このような機能のスケジューラ１００ａによって、効率的に処理が実行されるように、計算ノード３１，３２，３３，・・・にジョブの実行要求が送信される。なお、図６に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。

次に、管理ノード１００によるスケジューリング処理について詳細に説明する。
図９は、スケジューリング処理の手順を示すフローチャートである。以下、図９に示す処理をステップ番号に沿って説明する。

［ステップＳ１０１］ジョブスケジューリング部１５０は、スケジューリング開始のトリガとなるイベント（トリガイベント）が発生したか否かを判断する。トリガイベントは、例えば、端末装置２１からのジョブの投入、計算ノードによるジョブの実行終了、直近予想イベントなどである。直近予想イベントとは、前回のスケジューリング処理で適用したスケジュールにおいて、最も早く発生する予定の今後のイベントの発生予定時刻（ジョブの実行開始時刻、ジョブの実行終了時刻）になったときに発生するイベントである。直近予想イベントは、例えばジョブスケジューリング部１５０が、スケジュール情報記憶部１６０内の前回のスケジューリング処理で適用したスケジュールを参照して発生させる。

トリガイベントが発生した場合、ジョブスケジューリング部１５０は、スケジュール情報記憶部１６０内の現行スケジュール１６１における待機ジョブに関する設定内容を削除して、処理をステップＳ１０２に進める。またトリガイベントが発生していなければ、ジョブスケジューリング部１５０はステップＳ１０１の処理を繰り返し、トリガイベントが発生するのを待つ。

［ステップＳ１０２］ジョブスケジューリング部１５０は、未選択の待機ジョブを、待機キュー１２０の先頭から順に選択する。
［ステップＳ１０３］ジョブスケジューリング部１５０は、選択したジョブのスケジューリングを行う。例えばジョブスケジューリング部１５０は、選択したジョブのジョブ種（逐次ジョブ／並列ジョブ）と、ジョブの並列度、ジョブの最大実行時間に基づいて、計算ノードの空き時間帯を、選択したジョブの実行時間に割り当てる。計算ノードの空き時間帯とは、そのジョブの実行に割り当てられていない時間帯である。このときジョブスケジューリング部１５０は、選択したジョブをできるだけ早い時間帯に実行できるような計算ノードの空き時間帯を検索し、その空き時間帯を選択したジョブの実行時間に割り当てる。なお選択したジョブが並列ジョブであれば、そのジョブの並列度に応じた数の計算ノードの空き時間帯を、選択したジョブの実行時間に割り当てる。ジョブスケジューリング部１５０は、選択したジョブのスケジューリング結果を、スケジュール情報記憶部１６０内の現行スケジュール１６１に設定する。

［ステップＳ１０４］ジョブスケジューリング部１５０は、選択したジョブが、すぐに実行可能か否かを判断する。例えばジョブスケジューリング部１５０は、ステップＳ１０３において選択したジョブの実行時間に割り当てられた時間帯の開示時刻が、現在の時刻であれば、ジョブをすぐに実行可能と判断する。ジョブスケジューリング部１５０は、ジョブをすぐに実行可能な場合、処理をステップＳ１０５に進める。またジョブ管理部１１０は、ジョブをすぐには実行できない場合、処理をステップＳ１０６に進める。

［ステップＳ１０５］ジョブスケジューリング部１５０は、選択したジョブを、ステップＳ１０３で実行要求先に決定した計算ノードで実行させる。例えばジョブスケジューリング部１５０は、選択したジョブのジョブ情報と実行資源情報とをジョブ操作部１７０に渡し、ジョブの実行開始を依頼する。するとジョブ操作部１７０は、実行資源情報において実行要求先に指定された計算ノードに対して、ジョブの実行要求を送信する。このときジョブスケジューリング部１５０は、選択したジョブを、待機キュー１２０から実行中キュー１３０に移動する。

［ステップＳ１０６］ジョブスケジューリング部１５０は、ステップＳ１０２においてすべての待機ジョブを選択したか否かを判断する。例えばジョブスケジューリング部１５０は、最後に選択した待機ジョブが待機キュー１２０内の最後尾のジョブであれば、すべての待機ジョブを選択したものと判断する。ジョブスケジューリング部１５０は、すべての待機ジョブを選択した場合、処理をステップＳ１０７に進める。またジョブスケジューリング部１５０は、未選択の待機ジョブがある場合、処理をステップＳ１０２に進める。

［ステップＳ１０７］ジョブスケジューリング部１５０は、スケジュール最適化処理を行う。スケジュール最適化処理の詳細は後述する（図１２参照）。
このような手順でスケジュールが作成され、その後スケジュールの最適化が行われる。以下、ステップＳ１０１〜Ｓ１０６の処理によって作成されたスケジュールを、現行スケジュールと呼ぶこととする。

図１０は、待機ジョブのスケジューリング過程の一例を示す図である。図１０の例では、実行するジョブとして９個のジョブ４１〜４９がある。これらのジョブ４１〜４９を、１４台の計算ノードで実行するものとする。なお図１０中、各ジョブ４１〜４９を示す矩形内に、ジョブ識別番号を示している。またジョブ４１〜４９を示す矩形は、縦幅が並列度を表しており、横幅が最大実行時間を表している。

図１０の右側に示すスケジュールには、計算ノードごとに実行するジョブの割り当て状況が示されている。スケジュールは、横軸が時間経過である。そして計算ノードのノード番号に対応付けて、その計算ノードで実行するジョブの実行時間帯が示されている。

９個のジョブ４１〜４９のうち、２つのジョブ４１，４２については実行要求先の計算ノードが決定され、決定された計算ノードの空き時間帯が、ジョブ４１，４２の実行に割り当てられている。

残りのジョブ４３〜４９のキュー情報が待機キュー１２０に登録されている。図１０の例では、上位に示されているジョブほど、そのジョブのジョブ情報の待機キュー１２０内での順位が早い。従って、次に選択されるのはジョブ４３となる。

ジョブ４３は、並列度が「１４」である。すなわちジョブ４３は、１４台の計算ノードによって並列に処理される。図１０に示す状況では、１４台の計算ノードのうち８台はジョブを実行しており、空き状態の計算ノードは６台のみである。そのため、ジョブ４３は、ジョブ４１，４２の実行終了後にしか実施することができない。そこで、ジョブ４２の終了後の各計算ノードの時間帯が、ジョブ４３の実行時間に割り当てられる。すると、ジョブ４３の実行時間の前には、多くの計算ノードにおいて空き時間が生じる。ジョブ４３のスケジューリングが完了すると、その後、他のジョブ４４〜４９のスケジューリングが順次行われる。

図１１は、スケジューリング結果の一例を示す図である。図１１に示すように、ジョブ４４〜４９は、最大実行時間が長すぎて、ジョブ４３の実行前の空き時間に納まらない。そのため、ジョブ４４〜４９は、高並列度の並列ジョブであるジョブ４３の実行終了後に実行するように、スケジュールされる。

図１１のようなスケジュールが作成された場合、ジョブ４３の実行開始前に、多くの計算ノードで空き時間が生じる。すなわち、計算ノードの稼働率が低い状態が生じる。このような場合、実行中のジョブ４１，４２を凍結すれば、より効率的なスケジュールを作成できる可能性がある。そこで、ジョブの凍結を許容しないでスケジュールを作成した後、ジョブの凍結を許容したスケジュール最適化処理が実行される。

図１２は、スケジュール最適化処理の手順の一例を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。
［ステップＳ１１１］ジョブスケジューリング部１５０は、現行スケジュールにおいて、稼働率が所定の閾値以下に低下する時間帯があるか否かを判断する。稼働率は、例えば全計算ノードのうち、ジョブを実行している計算ノードの割合で示される。稼働率が所定の閾値以下となる時間帯がある場合、その時間帯の直後に実行する予定の待機ジョブが、稼働率低下の原因であると判断できる。そこで、稼働率が所定の閾値以下となる時間帯の直後に実行する予定の待機ジョブを、特に原因ジョブと呼ぶこととする。

ジョブスケジューリング部１５０は、稼働率が所定の閾値以下となる時間帯があれば、処理をステップＳ１１２に進める。ジョブスケジューリング部１５０は、稼働率が所定の閾値以下となる時間帯がなければスケジュール最適化処理を終了する。

［ステップＳ１１２］ジョブスケジューリング部１５０は、実行中のジョブのなかで終了時刻が最も遅いジョブを、凍結候補リストに追加する。以下、凍結候補リストに登録されたジョブを、特に凍結候補ジョブと呼ぶこととする。

［ステップＳ１１３］ジョブスケジューリング部１５０は、凍結候補リストに登録されたジョブをすべて凍結した場合の仮スケジューリングを行う。例えばジョブスケジューリング部１５０は、凍結候補ジョブについては、凍結し、稼働率が低下した直後に実行するジョブの後に再度実行するように仮スケジューリングを行う。またジョブスケジューリング部１５０は、凍結候補ジョブは、待機ジョブよりも優先して実行するように仮スケジューリングを行う。ジョブスケジューリング部１５０は、仮スケジューリングにより作成された仮スケジュール１６３を、スケジュール情報記憶部１６０に格納する。

［ステップＳ１１４］ジョブスケジューリング部１５０は、仮スケジューリングの結果、原因ジョブが実行開始可能となったか否かを判断する。ジョブスケジューリング部１５０は、原因ジョブが実行開始可能となった場合、処理をステップＳ１１５に進める。またジョブスケジューリング部１５０は、原因ジョブが実行可能とならなければ、処理をステップＳ１１２に進め、別の実行中ジョブを凍結する。

［ステップＳ１１５］ジョブスケジューリング部１５０は、ジョブ凍結による利益（Ｇａｉｎ）と損失（Ｌｏｓｓ）とを数値化し、利点と欠点との比を計算する。そして、ジョブスケジューリング部１５０は、利点と欠点との比が所定の閾値より大きいか否かを判断する。この判断は、例えば以下の式（１）で表される。

式（１）において、ｉは、仮スケジューリングで実行開始可能になったジョブのジョブ識別番号である（ｉは１以上の整数）。仮スケジューリングで実行開始可能になったジョブには、原因ジョブが含まれる。原因ジョブ以外のジョブについても、仮スケジューリングの過程で実行開始可能となる場合がある。Ｔ_iは、ジョブ識別番号ｉのジョブの開示時刻が、仮スケジューリングによって早まった時間である。Ｒ_iは、ジョブ識別番号ｉのジョブの並列度である。ｊは、凍結候補ジョブのジョブ識別番号である（ｊは１以上の整数）。Ｔ_jは、ジョブ識別番号ｊの凍結候補ジョブが、仮スケジュールによって遅延した時間である。Ｒ_jは、ジョブ識別番号ｊの凍結候補ジョブの並列度である。Ｐ₁は、予め管理者によって設定された閾値である。なおＰ₁には、例えば１以上の値が設定される。

ジョブスケジューリング部１５０は、利点の値を欠点の値で除算した結果が、所定の閾値より大きい場合、処理をステップＳ１１６に進める。またジョブスケジューリング部１５０は、利点の値を欠点の値で除算した結果が、所定の閾値以下の場合、スケジュール最適化処理を終了する。

［ステップＳ１１６］ジョブスケジューリング部１５０は、現行スケジュールから仮スケジュールに変更した場合の計算ノードの稼働率の向上度合いが、所定の閾値より大きいか否かを判断する。

稼働率の算出期間は、例えば現行スケジュールにおける、現在から原因ジョブの終了時刻までの期間である。稼働率は、算出期間内での各計算ノードの稼働時間の合計値を、各計算ノードの最大稼働時間の合計値で除算した値である。このとき算出期間の長さが、計算ノードそれぞれの最大稼働時間となる。

また、第２の実施の形態では、現行スケジュールにおける稼働率の算出期間と、仮スケジュールにおける稼働率の算出期間とは、同じ期間を用いる。この場合、各計算ノードの最大稼働時間の合計値は、現行スケジュールにおいても、仮スケジュールにおいても同じ値となる。すると、現行スケジュールから仮スケジュールに変更した場合の稼働率の向上度合いは、稼働率の算出期間内での各計算ノードの稼働時間の合計値を、現行スケジュールと仮スケジュールとで比較することによって求められる。そこで、以下の式（２）で、稼働率の向上度合いが所定の閾値より大きいか否かが判断できる。

式（２）において、Ｓ₁は、現行スケジュールにおいて、稼働率の算出期間内で計算ノードが稼働する時間の総量である。Ｓ₂は、仮スケジューリングにおいて、稼働率の算出期間内で計算ノードが稼働する時間の総量である。Ｐ₂は、予め管理者によって設定された閾値である。なおＰ₂には、例えば１以上の値が設定される。

ジョブスケジューリング部１５０は、稼働率の向上度合いが所定の閾値より大きい場合、処理をステップＳ１１７に進める。またジョブスケジューリング部１５０は、稼働率の向上度合いが所定の閾値以下の場合、スケジュール最適化処理を終了する。

［ステップＳ１１７］ジョブスケジューリング部１５０は、凍結候補ジョブの凍結を伴う再スケジューリング処理を行う。再スケジューリング処理の詳細は後述する（図１８参照）。

このように、稼働率が所定の閾値以下となる時間帯がある場合、ジョブの凍結を考慮に入れた仮スケジューリングが行われる。そして仮スケジューリングによるジョブの入れ替えの利益が損失より所定値以上に大きく、稼働率が所定値以上向上する場合に、仮スケジューリングに沿ったジョブ入れ替え処理が行われる。

図１３は、稼働率の判定例を示す図である。図１３の例では、計算ノードの総数Ｎ₁が１４台である。そしてジョブ４３の実行開始時刻（時刻ｔ₀）の直前の時間帯には、ジョブ４２のみが実行される。ジョブ４２は、並列度が「３」の並列ジョブである。そのため時刻ｔ₀の直前の時間帯の計算ノードの稼働数Ｎ₂は、３台である。すると、稼働率（Ｎ₂／Ｎ₁）は、約０．２１４（３／１４）となる。ここで、稼働率の閾値が、例えば０．５であれば、時刻ｔ₀の直前で稼働率の低下が検出される。

稼働率の低下が検出された場合、実行中ジョブのうち、終了時刻が最も遅いジョブが凍結候補リストに追加される。図１３の例では、ジョブ４２が凍結候補リストに追加される。また時刻ｔ₀から実行される予定のジョブ４３が、原因ジョブとして決定される。

図１４は、１つ目の実行中ジョブの凍結候補リストへの追加状況を示す図である。凍結候補リスト１５１には、ジョブ４２のジョブ識別番号「２」が追加されている。凍結候補リスト１５１にジョブが追加されると、追加された凍結候補ジョブを凍結した場合の仮スケジューリングが行われる。図１４の例では、仮スケジューリングによりジョブ４２が凍結されることで、ジョブ４２とジョブ４３との実行順が入れ替わる。

ジョブ４２の凍結により原因ジョブであるジョブ４３の開始時刻は早まるものの、すぐに実行することはできない。そこで別の実行中ジョブが凍結候補リストに追加される。
図１５は、２つ目の実行中ジョブの凍結候補リストへの追加状況を示す図である。凍結候補リスト１５１には、ジョブ４１のジョブ識別番号「１」が追加されている。凍結候補リスト１５１にジョブが追加されると、追加された凍結候補ジョブを凍結した場合の仮スケジューリングが行われる。図１５の例では、仮スケジューリングによりジョブ４１が凍結されることで、ジョブ４１とジョブ４３との実行順が入れ替わる。これにより、原因ジョブであるジョブ４３は、即時に実行可能となる。

原因ジョブが実行開始可能となると、まず、ジョブ凍結による利益と損失とが比較される。
図１６は、ジョブ凍結による利益と損失との比較例を示す図である。図１６では、上段に現行スケジュール１６１を示し、下段に仮スケジュール１６３を示している。ジョブ凍結による利益と損失とは、現行スケジュール１６１から仮スケジュール１６３へ変更した場合の原因ジョブと凍結候補ジョブとの実行開始時間の変化によって求められる。

図１６の例では、稼働率低下の原因となっている原因ジョブは、ジョブ４３である。仮スケジューリングによってジョブ４３の開始時刻が早まった時間は、Ｔ₃である。またジョブ４３の並列度はＲ₃である。すると、ジョブ凍結による利益は、Ｔ₃×Ｒ₃となる。

また凍結候補ジョブは、ジョブ４１とジョブ４２である。ジョブ４１が仮スケジューリングによって遅延する時間は、Ｔ₁である。ジョブ４１の並列度は、Ｒ₁である。ジョブ４２が仮スケジューリングによって遅延する時間は、Ｔ₂である。ジョブ４２の並列度は、Ｒ₂である。すると、ジョブ凍結による損失は、Ｔ₁×Ｒ₁＋Ｔ₂×Ｒ₂となる。そして利益を損失で除算した値が、閾値Ｐ₁より大きいかどうかが判定される。

また、原因ジョブが実行開始可能となった場合、稼働率の向上度合いが判断される。
図１７は、ジョブ凍結による稼働率の向上度合いの判断例を示す図である。図１７では、上段に現行スケジュール１６１を示し、下段に仮スケジュール１６３を示している。ジョブ凍結による稼働率の向上度合いは、現行スケジュール１６１と仮スケジュール１６３とのそれぞれにおける稼働率を比較することによって求められる。

図１７の例では、稼働率の算出期間は、現在から原因ジョブの処理の終了時刻Ｔ₁までの期間である。式（２）におけるＳ₁は、現行スケジュール１６１に示す領域６１の面積である。領域６１の面積は、計算ノードごとに、算出期間内での現行スケジュール１６１における稼働時間を計算し、その計算結果を合計することで求められる。式（２）におけるＳ₂は、仮スケジュール１６３に示す領域６２の面積である。領域６２の面積は、計算ノードごとに、算出期間内での仮スケジュール１６３における稼働時間を計算し、その計算結果を合計することで求められる。そして、Ｓ₂をＳ₁で除算した値が、閾値Ｐ₂より大きいかどうかが判定される。

図１６、図１７に示した判定により、利益が損失を所定値以上に上回り、稼働率の向上度合いが所定値以上であると判定された場合、凍結候補ジョブの凍結を伴う再スケジューリング処理が行われる。

図１８は、再スケジューリング処理の手順を示すフローチャートである。以下、図１８に示す処理をステップ番号に沿って説明する。
［ステップＳ１２１］ジョブスケジューリング部１５０は、スケジュール情報記憶部１６０内の現行スケジュール１６１の設定内容を全て削除する。そしてジョブスケジューリング部１５０は、凍結候補リスト１５１に設定されている凍結候補ジョブを凍結する。例えばジョブスケジューリング部１５０は、凍結候補ジョブのジョブ識別番号を指定して、ジョブ操作部１７０に対してジョブの凍結を依頼する。するとジョブ操作部１７０は、凍結候補ジョブを実行している計算ノードに対し、凍結候補ジョブの実行の一時停止を指示する。この指示に応じて、計算ノードが凍結候補ジョブの実行を一時停止する。

［ステップＳ１２２］ジョブスケジューリング部１５０は、実行中キュー１３０に登録されている凍結候補ジョブのジョブ情報を、凍結キュー１４０に移動する。
［ステップＳ１２３］ジョブスケジューリング部１５０は、未選択の待機ジョブを、待機キュー１２０の先頭から順に選択する。

［ステップＳ１２４］ジョブスケジューリング部１５０は、選択したジョブのスケジューリングを行う。スケジューリングの詳細は、例えば図９のステップＳ１０３の処理と同様である。

［ステップＳ１２５］ジョブスケジューリング部１５０は、選択したジョブが、すぐに実行可能か否かを判断する。例えばジョブスケジューリング部１５０は、ステップＳ１２４において選択したジョブの実行時間に割り当てられた時間帯の開示時刻が、現在の時刻であれば、ジョブをすぐに実行可能と判断する。ジョブスケジューリング部１５０は、ジョブをすぐに実行可能な場合、処理をステップＳ１２６に進める。またジョブ管理部１１０は、ジョブをすぐには実行できない場合、処理をステップＳ１２７に進める。

［ステップＳ１２６］ジョブスケジューリング部１５０は、選択したジョブを、ステップＳ１０３で実行要求先に決定した計算ノードで実行させる。この処理の詳細は、図９のステップＳ１０５の処理と同様である。その後、ジョブスケジューリング部１５０は処理をステップＳ１２３に進める。

［ステップＳ１２７］ジョブスケジューリング部１５０は、すべての待機ジョブを選択したか否かを判断する。例えばジョブスケジューリング部１５０は、最後に選択した待機ジョブが待機キュー１２０内の最後尾のジョブであれば、すべての待機ジョブを選択したものと判断する。ジョブスケジューリング部１５０は、すべての待機ジョブを選択した場合、処理をステップＳ１２８に進める。またジョブスケジューリング部１５０は、未選択の待機ジョブがある場合、処理をステップＳ１２３に進める。

［ステップＳ１２８］ジョブスケジューリング部１５０は、凍結候補ジョブのジョブ情報を、凍結キュー１４０から待機キュー１２０に移動する。例えば、ジョブスケジューリング部１５０は、凍結候補ジョブのジョブ情報を、待機キュー１２０の先頭に挿入する。これにより、凍結されているジョブが、次のスケジューリングの際に優先的に選択され、実行が再開される。

［ステップＳ１２９］ジョブスケジューリング部１５０は、凍結候補リスト１５１をクリアする。例えばジョブスケジューリング部１５０は、凍結候補リスト１５１からジョブ識別番号を削除する。その後、再スケジューリング処理が終了する。

図１９は、再スケジューリング処理に伴う各キューの状態遷移の一例を示す図である。図１９の例では、待機キュー１２０、実行中キュー１３０、凍結キュー１４０に格納されているジョブ情報を、各キュー内に円で示している。ジョブ情報を示す円内には、ジョブ情報に対応するジョブのジョブ識別番号が示されている。また各キュー内のジョブ情報の配列は、右側が先頭である。

第１の状態は、再スケジューリング処理開始時の状態である。この時点では、２つのジョブ４１，４２が計算ノードで実行されている。そのため、実行中キュー１３０には、ジョブ識別番号「１」のジョブ４１のジョブ情報と、ジョブ識別番号「２」のジョブ４２のジョブ情報とが登録されている。また待機キュー１２０には、ジョブ４３〜４９それぞれに対応するジョブ情報が登録されている。

第２の状態は、凍結候補ジョブを凍結し、仮スケジュールに基づいて原因ジョブの実行を開始した直後の状態である。この時点では、第２の状態で実行されていた２つのジョブ４１，４２の処理は、凍結されている。そこで実行中キュー１３０から凍結キュー１４０へ、ジョブ識別番号「１」のジョブ４１のジョブ情報と、ジョブ識別番号「２」のジョブ４２のジョブ情報とが移動されている。また２つのジョブ４１，４２の処理が凍結されたことで、原因ジョブであるジョブ４３の実行開始が可能となり、ジョブ４３の実行が開始されている。そこで待機キュー１２０から実行中キュー１３０へ、ジョブ識別番号「３」のジョブ４３のジョブ情報が移動されている。

第３の状態は、再スケジューリング処理が完了後の状態である。凍結キュー１４０に登録されていたジョブ識別番号「１」のジョブ４１のジョブ情報と、ジョブ識別番号「２」のジョブ４２のジョブ情報とは、待機キュー１２０の先頭に移動されている。これにより、スケジューリング処理を開始するためのトリガイベントが次に発生した場合、凍結状態のジョブ４１，４２が優先的に実行開始される。

以上のようにして、ジョブ凍結による利益と損失とを考慮した上で、ジョブ凍結をしてでも稼働率を向上させることが有益である場合に、ジョブ凍結を伴うスケジュールを作成し、そのスケジュールに沿ってジョブを実行させることができる。その結果、不必要なジョブ凍結を抑止することができ、ジョブ凍結による損失の発生を抑止することができる。例えば不必要なジョブ凍結が行われないことで、ジョブの凍結・再開の失敗により処理効率が低下する可能性が抑止される。

また不必要なジョブ凍結が行われないことで、ジョブの投入順とジョブの実行順とが入れ替わる頻度が少なくなる。これにより、ジョブの投入順とジョブの実行順とが入れ替わることによるサービスの公平性の低下が抑止される。例えばＨＰＣでは、処理に数週間を要するようなジョブ（長時間ジョブ）を実行する場合がある。ジョブの凍結を許容するスケジューリングを行うと、長時間ジョブよりも投入時刻が前のジョブが凍結され、長時間ジョブの後に再開される場合も想定される。この場合、凍結されたジョブを依頼したユーザにとっては、自身が依頼したジョブの投入よりも後に長期間ジョブが投入されたことが原因で、ジョブの実行結果を取得するのが数週間遅れることになる。このような事態が多発すると、ジョブの依頼したユーザ間でのサービスの公平性が低下する。第２の実施の形態では、仮スケジューリングにおいて長期にわたって凍結されるジョブが発生するような場合、式（１）の左辺の分母の値が大きくなる。その結果、図１２のステップＳ１１５でＮＯと判断され、ジョブの入れ替えは行われない可能性が高くなる。その結果、ジョブ凍結が最小限に抑えられ、サービスの公平性の低下が抑止される。

しかも第２の実施の形態では、計算ノードの稼働率の向上度合いがあまり大きくない場合、ジョブ凍結を許容したスケジューリングは行われない。これにより、リスクを負ってまでジョブ凍結をするメリットがない場合には、ジョブ凍結は行われずにすみ、無駄なジョブ凍結は抑止され、システムの安定性が向上する。

このように、第２の実施の形態では、ジョブ凍結の利益と損失とのバランス、および稼働率向上度合いとジョブ凍結のリスクとのバランスを考慮して、ジョブ実行の適切なスケジュールを作成することができる。

〔その他の実施の形態〕
第２の実施の形態では、ジョブの実行単位の計算資源は計算ノードであるが、ジョブの実行単位がＣＰＵまたはコアであっても、同様の技術を適用できる。

また第２の実施の形態では、ジョブ凍結を許容することで即時に実施可能となるジョブの実行開始時刻が早まる時間に基づいて、利益を示す値を算出している。しかし、即時に実施可能となるジョブ以外にも、ジョブ凍結を許容することで実行開始時刻の早まるジョブがある。そこでジョブ凍結を許容することで、即時に実行可能とはならないものの、実行開始時刻の早まるジョブに関する、実行開始時刻が早まる時間に基づく利益を、ジョブ凍結を許容する場合の利益を示す値に加算してもよい。

さらに第２の実施の形態では、ジョブ凍結を許容することで凍結されるジョブの遅延時間（一時停止時間）に基づいて、損失を示す値を算出している。しかし、凍結するジョブ以外にも、ジョブ凍結を許容することで実行開始時刻が遅延するジョブが発生する可能性がある。そこでジョブ凍結を許容することで、実行開始時刻の遅延が生じるジョブに関する、実行開始時刻の遅延時間に基づく損失を、ジョブ凍結を許容する場合の損失を示す値に加算してもよい。

なお、上記の各実施の形態に示した処理機能は、コンピュータによって実現することができる。その場合、管理ノードが有する機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disc）などがある。

プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。

プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。

また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。

以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。

以上の実施の形態に開示された技術には、以下の付記に示す技術が含まれる。
（付記１） 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
前記第１のスケジュールと前記第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算し、
前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
処理をコンピュータに実行させるプログラム。

（付記２） 前記第１のスケジュールよりも前記第２のスケジュールにおいて実行開始時刻が早く設定されたジョブについての、前記第１のスケジュールと前記第２のスケジュールとにおける実行開始時刻の差に基づいて、前記利益を示す値を計算し、
前記第２のスケジュールにおいて一時停止されるジョブの一時停止期間の長さに基づいて、前記損失を示す値を計算する、
処理をコンピュータに実行させる付記１記載のプログラム。

（付記３） 前記第１のスケジュールでは即時に実行開始できないが、前記第２のスケジュールでは即時に実行開始可能なジョブそれぞれについて、前記第１のスケジュールと前記第２のスケジュールとにおけるジョブの実行開始時刻の差に、該ジョブの実行に使用する計算資源の数を乗算し、ジョブごとの乗算結果の合計を、前記利益を示す値とする、
処理をコンピュータに実行させる付記１または２のいずれかに記載のプログラム。

（付記４） 複数の計算資源のいずれかで実行中のジョブのうち、前記第２のスケジュールにおいて一時停止されるジョブそれぞれについて、前記第２のスケジュールにおけるジョブの一時停止期間の長さに、該ジョブの実行に使用する計算資源の数を乗算し、ジョブごとの乗算結果の合計を、前記損失を示す値とする、
処理をコンピュータに実行させる付記１乃至３のいずれかに記載のプログラム。

（付記５） 前記利益を示す値を前記損失を示す値で除算した結果が、所定の閾値より大きい場合、前記第２のスケジュールが適切であると決定する、
処理をコンピュータに実行させる付記１乃至４のいずれかに記載のプログラム。

（付記６） 前記第１のスケジュールにおいて、前記複数の計算資源の稼働効率が所定値以下となる時間帯を検出し、該時間帯の直後に実行予定のジョブを特定し、
前記特定したジョブが即時実行可能となるように前記第２のスケジュールを作成する、
処理をコンピュータに実行させる付記１乃至５のいずれかに記載のプログラム。

（付記７） 前記第１のスケジュールにおいて、前記複数の計算資源の稼働効率が所定値以下となる時間帯が存在しない場合、前記第２のスケジュールを作成することなく、前記第１のスケジュールが適切であると判断する、
処理をコンピュータに実行させる付記６記載のプログラム。

（付記８） 前記第１のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率と、前記第２のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率との比較結果を加味して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
処理をコンピュータに実行させる付記１乃至７のいずれかに記載のプログラム。

（付記９） 前記利益を示す値と前記損失を示す値との比較により、前記第２のスケジュールが適切であると判断でき、かつ、前記第１のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率と、前記第２のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率との比較により、前記第２のスケジュールが適切であると判断できる場合、前記第２のスケジュールが適切であると決定する、
処理をコンピュータに実行させる付記８記載のプログラム。

（付記１０） 前記第２のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率を、前記第１のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率で除算した結果が、所定の閾値より大きい場合、前記第２のスケジュールが適切であると決定する、
処理をコンピュータに実行させる付記８または９のいずれかに記載のプログラム。

（付記１１） 適切であると決定されたスケジュールに従って、前記複数の計算資源にジョブを実行させる、
処理をコンピュータに実行させる付記１乃至１０のいずれかに記載のプログラム。

（付記１２） コンピュータが、
複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
前記第１のスケジュールと前記第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算し、
前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
ことを特徴とするジョブスケジューリング方法。

（付記１３） 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールと、複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールとを作成する作成手段と、
前記第１のスケジュールと前記第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算する計算手段と、
前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する決定手段と、
を有する情報処理装置。

１ 情報処理装置
１ａ 作成手段
１ｂ 記憶手段
１ｃ 計算手段
１ｄ 決定手段
１ｅ 実行制御手段
２ａ，２ｂ，２ｃ，・・・ 計算資源

Claims (10)

1. 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
   前記第１のスケジュールよりも前記第２のスケジュールにおいて実行開始時刻が早く設定されたジョブについての、前記第１のスケジュールと前記第２のスケジュールとにおける実行開始時刻の差に基づいて、ジョブの一時停止を許容することの利益を示す値を計算すると共に、前記第２のスケジュールにおいて一時停止されるジョブの一時停止期間の長さに基づいて、ジョブの一時停止を許容することの損失を示す値を計算し、
   前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
   処理をコンピュータに実行させるプログラム。
2. 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
   前記第１のスケジュールと前記第２のスケジュールとに基づいて、前記第１のスケジュールでは即時に実行開始できないが、前記第２のスケジュールでは即時に実行開始可能なジョブそれぞれについて、前記第１のスケジュールと前記第２のスケジュールとにおけるジョブの実行開始時刻の差に、該ジョブの実行に使用する計算資源の数を乗算し、ジョブごとの乗算結果の合計を、ジョブの一時停止を許容することの利益を示す値として計算すると共に、ジョブの一時停止を許容することの損失を示す値を計算し、
   前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
   処理をコンピュータに実行させるプログラム。
3. 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
   前記第１のスケジュールと前記第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値を計算すると共に、複数の計算資源のいずれかで実行中のジョブのうち、前記第２のスケジュールにおいて一時停止されるジョブそれぞれについて、前記第２のスケジュールにおけるジョブの一時停止期間の長さに、該ジョブの実行に使用する計算資源の数を乗算し、ジョブごとの乗算結果の合計を、ジョブの一時停止を許容することの損失を示す値として計算し、
   前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
   処理をコンピュータに実行させるプログラム。
4. 前記利益を示す値を前記損失を示す値で除算した結果が、所定の閾値より大きい場合、前記第２のスケジュールが適切であると決定する、
   処理をコンピュータに実行させる請求項１乃至３のいずれかに記載のプログラム。
5. 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
   前記第１のスケジュールにおいて、前記複数の計算資源の稼働効率が所定値以下となる時間帯を検出し、該時間帯の直後に実行予定のジョブを特定し、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを、前記特定したジョブが即時実行可能となるように作成し、
   前記第１のスケジュールと前記第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算し、
   前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
   処理をコンピュータに実行させるプログラム。
6. 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
   前記第１のスケジュールと前記第２のスケジュールとに基づいて、ジョブの一時停止を許容することの利益を示す値と損失を示す値とを計算し、
   前記利益を示す値と前記損失を示す値とを比較すると共に、前記第１のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率と、前記第２のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
   処理をコンピュータに実行させるプログラム。
7. 前記利益を示す値と前記損失を示す値との比較により、前記第２のスケジュールが適切であると判断でき、かつ、前記第１のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率と、前記第２のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率との比較により、前記第２のスケジュールが適切であると判断できる場合、前記第２のスケジュールが適切であると決定する、
   処理をコンピュータに実行させる請求項６記載のプログラム。
8. 前記第２のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率を、前記第１のスケジュールに従ってジョブを実行させた場合の前記複数の計算資源の稼働効率で除算した結果が、所定の閾値より大きい場合、前記第２のスケジュールが適切であると決定する、
   処理をコンピュータに実行させる請求項６または７のいずれかに記載のプログラム。
9. コンピュータが、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールを作成し、
   複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールを作成し、
   前記第１のスケジュールよりも前記第２のスケジュールにおいて実行開始時刻が早く設定されたジョブについての、前記第１のスケジュールと前記第２のスケジュールとにおける実行開始時刻の差に基づいて、ジョブの一時停止を許容することの利益を示す値を計算すると共に、前記第２のスケジュールにおいて一時停止されるジョブの一時停止期間の長さに基づいて、ジョブの一時停止を許容することの損失を示す値を計算し、
   前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する、
   ことを特徴とするジョブスケジューリング方法。
10. 複数の計算資源のいずれかで実行中のジョブの一時停止を許容せずに、実行待ちのジョブを計算資源に実行させるための第１のスケジュールと、複数の計算資源のいずれかで実行中のジョブの一時停止を許容して、一時停止したジョブと前記実行待ちのジョブとのそれぞれを計算資源に実行させるための第２のスケジュールとを作成する作成手段と、
    前記第１のスケジュールよりも前記第２のスケジュールにおいて実行開始時刻が早く設定されたジョブについての、前記第１のスケジュールと前記第２のスケジュールとにおける実行開始時刻の差に基づいて、ジョブの一時停止を許容することの利益を示す値を計算すると共に、前記第２のスケジュールにおいて一時停止されるジョブの一時停止期間の長さに基づいて、ジョブの一時停止を許容することの損失を示す値を計算する計算手段と、
    前記利益を示す値と前記損失を示す値とを比較して、前記第１のスケジュールと前記第２のスケジュールとのうち、適切なスケジュールを決定する決定手段と、
    を有する情報処理装置。
    

Images