(57)【要約】【課題】ＣＰＵの高稼働率を実現するスケジューリングシステム等を提供することである。【解決手段】第一の資源領域と、第二の資源領域と、第一のジョブスケジューリング部と、第二のジョブスケジューリング部とを具備するジョブスケジューリングシステムによって解決することができる。第一の資源領域においては、ジョブの実行を、少なくとも一つのＣＰＵを用いて行う。第二の資源領域においては、第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、未使用のＣＰＵを第一の資源領域から借りて、ジョブの実行を行う。第一のジョブスケジューリング部は、投入されるジョブを、第一の資源領域で実行される通常ジョブとしてスケジューリングする。第二のジョブスケジューリング部は、通常ジョブと同一のジョブを、第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする。【選択図】図３
2010182199.tif 000002
【特許請求の範囲】
【請求項１】
ジョブの実行を、少なくとも一つのＣＰＵを用いて行う第一の資源領域と、
前記第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、前記未使用のＣＰＵを前記第一の資源領域から借りて、ジョブの実行を行う第二の資源領域と、
投入されるジョブを、前記第一の資源領域で実行される通常ジョブとしてスケジューリングする第一のジョブスケジューリング部と、
前記通常ジョブと同一のジョブを、前記第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする第二のジョブスケジューリング部とを具備する
ジョブスケジューリングシステム。
【請求項２】
前記第二のジョブスケジューリング部は、
前記通常ジョブの中から、所定のポリシーに従ってジョブを選択するジョブ選択部を備え、
前記ジョブ選択部が選択した通常ジョブと同一のジョブを、前記第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする
請求項１記載のジョブスケジューリングシステム。
【請求項３】
前記第二のジョブスケジューリング部は、
前記先行重複実行ジョブを、前記先行重複実行ジョブに対応する通常ジョブよりも前の時間にスケジューリングする
請求項２記載のジョブスケジューリングシステム。
【請求項４】
前記第二のジョブスケジューリング部は、
同一のジョブについて行われた前記先行重複実行ジョブのスケジューリングと、前記先行重複実行ジョブに対応する通常ジョブのスケジューリングとの重複スケジューリングを解決する重複スケジューリング解決部を更に備え、
前記重複スケジューリング解決部は、
前記先行重複実行ジョブが、前記先行重複実行ジョブに対応する通常ジョブの開始前に終了しなかった場合に、前記先行重複実行ジョブを、前記第二の資源領域から前記第一の資源領域へ移し、前記先行重複実行ジョブを、前記先行重複実行ジョブに対応する通常ジョブとして継続して実行する
請求項３記載のジョブスケジューリングシステム。
【請求項５】
前記重複スケジューリング解決部は、
前記先行重複実行ジョブが、前記先行重複実行ジョブに対応する通常ジョブの開始前に終了した場合に、前記先行重複実行ジョブに対応する通常ジョブのスケジューリングをキャンセルする
請求項３又は４記載のジョブスケジューリングシステム。
【請求項６】
前記第二の資源領域は、
前記第一の資源領域から借りたＣＰＵを使用して、前記先行重複実行ジョブを実行しているときに、前記第一の資源領域によって、前記借りたＣＰＵを奪い取られた場合には、前記先行重複実行ジョブの実行を中断し、再度未使用のＣＰＵを借りられるまで、前記先行重複実行ジョブを待機状態にする
請求項２〜５いずれか１項に記載のジョブスケジューリングシステム。
【請求項７】
前記第二のジョブスケジューリング部は、
前記所定のポリシーを設定するポリシー設定部を更に備え、
前記ポリシー設定部は、
前記先行重複実行ジョブとして実行するジョブを選択するためのポリシーを、投入されたジョブについて宣言された使用ＣＰＵの数量に基づいて設定する
請求項２〜６いずれか１項に記載のジョブスケジューリングシステム。
【請求項８】
前記第一のジョブスケジューリング部と、前記第二のジョブスケジューリング部との両方を擁する一のジョブスケジューラを具備する
請求項２〜７いずれか１項に記載のジョブスケジューリングシステム。
【請求項９】
ジョブの実行を、少なくとも一つのＣＰＵを用いて行う第一の資源領域を作成することと、
前記第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、前記未使用のＣＰＵを前記第一の資源領域から借りて、ジョブの実行を行う第二の資源領域を作成することと、
投入されるジョブを、前記第一の資源領域で実行される通常ジョブとしてスケジューリングすることと、
前記通常ジョブと同一のジョブを、前記第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングすることとを具備する
ジョブスケジューリング方法。
【請求項１０】
前記先行重複実行ジョブとしてスケジューリングすることにおいては、
前記先行重複実行ジョブを、所定のポリシーに従って、前記通常ジョブの中から選択することを含む
請求項９記載のジョブスケジューリング方法。
【請求項１１】
前記先行重複実行ジョブとしてスケジューリングすることにおいては、
前記先行重複実行ジョブを、前記先行重複実行ジョブに対応する通常ジョブよりも前の時間にスケジューリングすることを更に含む
請求項１０記載のジョブスケジューリング方法。
【請求項１２】
同一のジョブについて行われた前記先行重複実行ジョブのスケジューリングと、前記先行重複実行ジョブに対応する通常ジョブのスケジューリングとの重複スケジューリングを解決することを更に具備し、
前記解決することにおいては、
前記先行重複実行ジョブが、前記先行重複実行ジョブに対応する通常ジョブの開始前に終了しなかった場合に、前記先行重複実行ジョブを、前記第二の資源領域から前記第一の資源領域へ移し、前記先行重複実行ジョブを、前記先行重複実行ジョブに対応する通常ジョブとして継続して実行することと、
前記先行重複実行ジョブが、前記先行重複実行ジョブに対応する通常ジョブの開始前に終了した場合に、前記先行重複実行ジョブに対応する通常ジョブのスケジューリングをキャンセルすることとを含む
請求項１１記載のジョブスケジューリング方法。
【請求項１３】
ジョブの実行を、少なくとも一つのＣＰＵを用いて行う第一の資源領域を作成するステップと、
前記第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、前記未使用のＣＰＵを前記第一の資源領域から借りて、ジョブの実行を行う第二の資源領域を作成するステップと、
投入されるジョブを、前記第一の資源領域で実行される通常ジョブとしてスケジューリングするステップと、
前記通常ジョブと同一のジョブを、前記第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングするステップとをコンピュータに実行させるための
ジョブスケジューリングプログラム。
【請求項１４】
前記先行重複実行ジョブとしてスケジューリングするステップにおいては、
前記先行重複実行ジョブを、所定のポリシーに従って、前記通常ジョブの中から選択するステップを含む
請求項１３記載のジョブスケジューリングプログラム。
【請求項１５】
前記先行重複実行ジョブとしてスケジューリングするステップにおいては、
前記先行重複実行ジョブを、前記先行重複実行ジョブに対応する通常ジョブよりも前の時間にスケジューリングするステップを更に含む
請求項１４記載のジョブスケジューリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ジョブスケジューリングシステム、方法、及びプログラムに関する。
【背景技術】
【０００２】
複数のＣＰＵを搭載したコンピュータを、複数台組み合わせて作られる大規模システムが構築されている。このような大規模システムで用いられる効率的なスケジューリング手法として、バックフィル型スケジューリングが知られる。バックフィル型スケジューリングでは、バッチ処理システムにおいて、ジョブが必要とする計算機資源量（ＣＰＵ数若しくはＣＰＵコア数やメモリ量）と実行に必要な時間を元に、計画的に計算機資源を割り当ててスケジューリングを行う。これらの資源量や時間は、いずれもユーザが宣言する。
【０００３】
図１は、バックフィル型スケジューリングの説明図である。図１において、スケジューラに、複数のジョブＡ〜Ｆがエンキューされている。エンキューされた順番は、ジョブＡ、ジョブＢ、ジョブＣ、ジョブＤ、ジョブＥ、ジョブＦの順である。図示するように、バックフィル型スケジューリングでは、計算機資源の空き時間枠を管理し、ジョブを計画的に割り当てることでシステム全体の利用効率を向上させる。ジョブＡ〜Ｆは、割り当てられた時間枠において、割り当てられた資源を占有できるので外乱なく実行でき、また、ジョブ実行開始時間が保障されるなどの特徴がある。先に投入されたジョブに影響を与えることなく、後から投入されたジョブを先に実行できる未割り当て枠があれば、後から投入されたジョブでも前方にスケジュールされることから、「バックフィル」と呼ばれている。
【０００４】
バックフィル型スケジューリングにおいて、割り当てられたＣＰＵをジョブが全て使い切っておらず、ＣＰＵ稼働率の低下を招いているケースが見受けられる。図２は、ＣＰＵ資源を使い切らない原因を説明する図である。図２において、ジョブ［ｊｏｂ１］と、ジョブ［ｊｏｂ２］との２つのジョブがスケジューリングされている。また、ジョブ［ｊｏｂ１］は、アプリケーション［ＡＰ０］と、アプリケーション［ＡＰ１］との２つのアプリケーションを有している。
【０００５】
図２において、Ｉ／Ｏ処理が、ジョブ［ｊｏｂ１］におけるアプリケーション［ＡＰ１］の実行中に発生している。このＩ／Ｏ処理の発生により、その間はＣＰＵを手放している時間帯が生じる（第１原因）。それから、複数のアプリケーション［ＡＰ０，ＡＰ１］を有しているジョブ［ｊｏｂ１］では、図示するように、必要とするＣＰＵ数がアプリケーション［ＡＰ０，ＡＰ１］毎に異なる場合がある。しかし、スケジューリングの際には、ジョブ［ｊｏｂ１］に対して、アプリケーション［ＡＰ１］で必要な８つのＣＰＵを割り当てる。この場合、５つのＣＰＵが必要なアプリケーション［ＡＰ０］の処理中に、３つの遊休ＣＰＵが生じる（第２原因）。それから、ジョブ［ｊｏｂ２］の実行では、ユーザが過大申告を行っている。図中、ユーザは、ジョブ［ｊｏｂ２］の実行に必要なＣＰＵ数として、８を宣言している。このユーザの過大申告のために、宣言した８つのＣＰＵの全てが稼動していない時間帯が生じる（第３原因）。
【０００６】
近年、ＨＰＣ（Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐｕｔｉｎｇ）分野を中心にバックフィル型スケジューリングの関心が高まっており、いくつかの新しいスケジューリング方法が提案されている。バックフィル型スケジューリングの応用例としては、例えば、特開２００１−１４７９０１号公報（特許文献１参照）に記載された「ローカル・ジョブ制御システムを有する分散処理システム内での外部ジョブ・スケジューリング方法及びシステム」の発明がある。この発明は、既存のスケジューラを強化することを目的とし、既存のスケジューラに外部スケジューラを追加する。バックフィル型スケジューリングを使って、最適かつ公平にジョブをスケジューリングする。
【０００７】
米国特許出願公開第２００４／０１９９９１８号明細書（特許文献２参照）に記載された「Ｂａｃｋｆｉｌｌ  Ｓｃｈｅｄｕｌｉｎｇ  Ｏｆ  Ａｐｐｌｉｃａｔｉｏｎｓ  Ｂａｓｅｄ  Ｏｎ  Ｄａｔａ  Ｏｆ  Ｔｈｅ  Ａｐｐｌｉｃａｔｉｏｎｓ」の発明においては、バックフィル型スケジューリングを使用した環境で、あるノードにスケジュールされているジョブを、別のノードにマイグレーション（移動）した方がいいかどうかを判断する。
【０００８】
特開２００５−３１０１３９号公報（特許文献３参照）に記載された「トポロジを意識したジョブ・スケジューリングとバックフィルとをＨＰＣ環境において行うシステム及び方法」の発明は、トポロジを意識したジョブスケジューリングとバックフィルに関する。この公知文献には、複数ノードから非割り当て部分集合を判定してジョブを実行する方法が開示されている。
【０００９】
特開２００１−１８４３２６号公報（特許文献４参照）には、「マルチプロセッサスケジューリング方法」などの発明が記載されている。この「マルチプロセッサスケジューリング方法」は、メモリを共有する複数プロセッサからなる計算機システムにおけるマルチプロセッサスケジューリング方法である。分割可能な処理であるデータ処理要求を登録するデータ処理要求キューと、各々のプロセッサで動作するデータ処理機能を設ける。プロセッサの実行ジョブからのデータ処理要求がデータ処理要求キューに登録されたとき、該データ処理要求を全プロセッサに通知する。各プロセッサは、自プロセッサの実行ジョブの優先度がデータ処理要求の優先度より低い場合、自プロセッサの実行ジョブの動作を中断する。そして、データ処理要求で指定されたデータ処理機能によりデータ処理要求の分割した一部を処理する。このようにして、データ処理要求を複数のプロセッサで処理する。
【００１０】
特開２００５−０５６３９１号公報（特許文献５参照）には、「コンピューティング環境の作業負荷を均衡させる方法」などの発明が記載されている。この「コンピューティング環境の作業負荷を均衡させる方法」の発明は、コンピュータ環境の作業負荷を均衡させる方法であって、取得するステップと、均衡させるステップとを備える。取得するステップにおいては、グリッド・コンピューティング環境の複数のシステムのうちの少なくとも１つのシステムに関する情報を取得する。均衡させるステップにおいては、取得した情報の少なくとも一部を用いて複数のシステムのうちの少なくとも２のシステムの作業負荷を均衡させる。
【００１１】
特開平１０−２４０５４９号公報（特許文献６参照）には、「並列ジョブ多重スケジューリング方法」などの発明が記載されている。この「並列ジョブ多重スケジューリング方法」の発明では、計算機システムを構成する同等の機能を有する複数の演算プロセッサを、逐次演算プロセッサと、並列演算プロセッサ群に論理的に分割する。逐次演算プロセッサは、並列ジョブの逐次処理部分あるいは並列処理部分を実行する。並列演算プロセッサ群は、並列ジョブの並列処理部分を並列的に実行する複数個の演算プロセッサからなる。並列演算プロセッサ群は、複数の逐次演算プロセッサによって共用できる。また、１時期には、１つの逐次演算プロセッサからのみ、並列演算プロセッサ群の使用を可能とする。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００１−１４７９０１号公報
【特許文献２】米国特許出願公開第２００４／０１９９９１８号明細書
【特許文献３】特開２００５−３１０１３９号公報
【特許文献４】特開２００１−１８４３２６号公報
【特許文献５】特開２００５−０５６３９１号公報
【特許文献６】特開平１０−２４０５４９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
特許文献１〜３に記載されたようなスケジューリング手法では、ユーザのリソース使用宣言値に基づいて、いかに最適かつ公平にジョブをスケジュールするかに主眼がおかれている。一方、各ジョブ内でアプリケーションがＣＰＵを手放している間の遊休資源を活用する方法などに関しては研究されていないという問題点がある。
【００１４】
特許文献４に記載された発明には、次のような問題点がある。すなわち、この公知文献における図４や図６に図示されているように、データ処理要求割り込みやタイマ割り込みによるオーバーヘッドがあるという問題点、割り当てられたＣＰＵを占有することができず、ジョブ実行中に割り込まれた場合には、ＣＰＵを放さなければいけない（ジョブの実行を一時中断しなければいけない）という問題点、ジョブのターンアラウンドタイム（ＴＡＴ）が保障されていないという問題点などがある。
【００１５】
特許文献５に記載された発明は、バックフィル型スケジューリングそのものではなく、一例として、バックフィル型スケジューリングを使ったスケジューリング方法を提供するものである。
【００１６】
特許文献６に記載された発明には、次のような問題点がある。特許文献６における図１に示されているように、演算プロセッサ間同期機構と同期到達通知信号線ＳＲＬと同期完了通知信号線ＳＣＬなど、特別な機構が必要になるという問題点、特許文献６における図８に示されているように、同期処理や終了通知によるオーバーヘッドが発生するという問題点がある。
【００１７】
それから、特許文献６における図７や図８を参照すると、並列処理部分（図７：Ｕ２〜Ｕ６，Ｕ８〜Ｕ１２  図８：Ｐ１０２〜Ｐ１０６，Ｐ２０２〜Ｐ２０６）は都合よく全て同じ大きさになっている。すなわち、同時に開始して同時に終了するように図示されているが、実際の運用では個々の並列処理部分の処理時間はバラバラになることがほとんどである。この場合、最も処理時間の長い並列処理部分が終了するまで他の並列処理部分のＣＰＵは遊休ＣＰＵとなる（実行待ちジョブがあったとしても）という問題点がある。さらに、図８を参照すると、Ｔ１〜Ｔ２の間で動作しているＣＰＵは２台だけで、その他のＣＰＵは遊休ＣＰＵとなっているという問題点がある。さらに、明細書の段落［００７０］〜［００７４］によると、逐次処理と並列処理の比率に応じて計算機システム内の演算プロセッサの構成比率を変更することができるとのことだが、図８を見ると構成変更に相当の時間（Ｔ６〜Ｔ７）を要しているという問題点がある。
【００１８】
本発明の目的は、ＣＰＵの高稼働率を実現するスケジューリングシステム、方法、及びプログラムを提供することである。
【課題を解決するための手段】
【００１９】
本発明の一つ目のアスペクトによるジョブスケジューリングシステムは、第一の資源領域と、第二の資源領域と、第一のジョブスケジューリング部と、第二のジョブスケジューリング部とを具備する。第一の資源領域においては、ジョブの実行を、少なくとも一つのＣＰＵを用いて行う。第二の資源領域においては、第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、未使用のＣＰＵを第一の資源領域から借りて、ジョブの実行を行う。第一のジョブスケジューリング部は、投入されるジョブを、第一の資源領域で実行される通常ジョブとしてスケジューリングする。第二のジョブスケジューリング部は、通常ジョブと同一のジョブを、第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする。
【００２０】
本発明の二つ目のアスペクトによるジョブスケジューリング方法は、第一の資源領域を作成することと、第二の資源領域を作成することと、通常ジョブとしてスケジューリングすることと、先行重複実行ジョブとしてスケジューリングすることとを具備する。第一の資源領域を作成することにおいては、ジョブの実行を、少なくとも一つのＣＰＵを用いて行う第一の資源領域を作成する。第二の資源領域を作成することにおいては、第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、未使用のＣＰＵを第一の資源領域から借りて、ジョブの実行を行う第二の資源領域を作成する。通常ジョブとしてスケジューリングすることにおいては、投入されるジョブを、第一の資源領域で実行される通常ジョブとしてスケジューリングする。先行重複実行ジョブとしてスケジューリングすることにおいては、通常ジョブと同一のジョブを、第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする。
【００２１】
本発明の三つ目のアスペクトによるジョブスケジューリングプログラムは、第一の資源領域を作成するステップと、第二の資源領域を作成するステップと、通常ジョブとしてスケジューリングするステップと、先行重複実行ジョブとしてスケジューリングするステップとをコンピュータに実行させる。第一の資源領域を作成するステップにおいては、ジョブの実行を、少なくとも一つのＣＰＵを用いて行う第一の資源領域を作成する。第二の資源領域を作成するステップにおいては、第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、未使用のＣＰＵを第一の資源領域から借りて、ジョブの実行を行う第二の資源領域を作成する。通常ジョブとしてスケジューリングするステップにおいては、投入されるジョブを、第一の資源領域で実行される通常ジョブとしてスケジューリングする。先行重複実行ジョブとしてスケジューリングするステップにおいては、通常ジョブと同一のジョブを、第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする。なお、このプログラムは、記録媒体に記録し、記録媒体からコンピュータに読み込ませることができる。
【発明の効果】
【００２２】
本発明によれば、ＣＰＵの高稼働率を実現するスケジューリングシステム、方法、及びプログラムを提供することができる。
【図面の簡単な説明】
【００２３】
【図１】バックフィル型スケジューリングシステムの説明図
【図２】ＣＰＵ資源を使い切らない原因を説明する図
【図３】第１の実施の形態におけるジョブスケジューリングシステムの構成説明図
【図４】第２の実施の形態におけるジョブスケジューリング方法を説明するフローチャート
【図５】第３の実施の形態におけるジョブスケジューリングシステムの構成を説明するブロック図
【図６】実行ホストにて動作環境を構築する手順を説明するフローチャート
【図７】先行重複実行部１１０の動作を説明するフローチャート
【図８】第４の実施の形態におけるジョブスケジューリングシステムの構成を説明するブロック図
【図９】関連システムによるスケジューリングの説明図
【図１０】第３及び第４の実施の形態におけるスケジューリングの説明図
【図１１】先行重複実行ジョブから通常ジョブへの移行についての説明図
【発明を実施するための形態】
【００２４】
本発明を実施するための形態について、図面を参照して詳細に説明する。図３は、一つ目の実施の形態におけるジョブスケジューリングシステムの構成説明図である。図３において、ジョブスケジューリングシステム１０は、第一の資源領域１３と、第二の資源領域１４と、第一のジョブスケジューリング部１１と、第二のジョブスケジューリング部１２とを具備している。これらのブロック１１〜１４は、コンピュータプログラムによって実現可能である。第一の資源領域１３においては、ジョブの実行を、少なくとも一つのＣＰＵを用いて行う。第二の資源領域１４においては、第一の資源領域１３で使用されていない未使用のＣＰＵがあった場合に、未使用のＣＰＵを第一の資源領域１３から借りて、ジョブの実行を行う。第一のジョブスケジューリング部１１は、投入されるジョブを、第一の資源領域１３で実行される通常ジョブとしてスケジューリングする。第二のジョブスケジューリング部１２は、通常ジョブと同一のジョブを、第二の資源領域１４で実行される先行重複実行ジョブとしてスケジューリングする。
【００２５】
図４は、二つ目の実施の形態におけるジョブスケジューリング方法を説明するフローチャートである。図４において、ジョブスケジューリング方法は、第一の資源領域を作成すること（ステップ２０）と、第二の資源領域を作成すること（ステップ２１）と、通常ジョブとしてスケジューリングすること（ステップ２２）と、先行重複実行ジョブとしてスケジューリングすること（ステップ２３）とを具備する。これらのステップ２０〜２３は、コンピュータプログラムによって、コンピュータに実行させることができる。第一の資源領域を作成すること（ステップ２０）においては、ジョブの実行を、少なくとも一つのＣＰＵを用いて行う第一の資源領域を作成する。第二の資源領域を作成すること（ステップ２１）においては、第一の資源領域で使用されていない未使用のＣＰＵがあった場合に、未使用のＣＰＵを第一の資源領域から借りて、ジョブの実行を行う第二の資源領域を作成する。通常ジョブとしてスケジューリングすること（ステップ２２）においては、投入されるジョブを、第一の資源領域で実行される通常ジョブとしてスケジューリングする。先行重複実行ジョブとしてスケジューリングすること（ステップ２３）においては、通常ジョブと同一のジョブを、第二の資源領域で実行される先行重複実行ジョブとしてスケジューリングする。
【００２６】
通常のスケジューリング方式によってスケジューリングされ、実行されるジョブのことを、通常ジョブと呼ぶことにする。通常ジョブは既存のスケジューリング方式と何ら変わり無くスケジューリングすることが可能である。通常ジョブは、第一の資源領域で実行されるので、優先的にＣＰＵを使うことができ、ターンアラウンドタイムを保障される。一方、本発明における第二のスケジューリング部によってスケジューリングされるジョブを先行重複実行ジョブと呼ぶことにする。先行重複実行ジョブは、通常ジョブとしてスケジューリングされたジョブと同じジョブを、第二の資源領域で実行するためにスケジューリングするものである。後方にスケジュールされている通常ジョブと同一のジョブを、先行重複実行ジョブとして先に実行することで、ＣＰＵの高稼働率の実現が可能になる。
【００２７】
図５は、三つ目の実施の形態におけるジョブスケジューリングシステムの構成を説明するブロック図である。図５を参照すると、第３の実施の形態におけるジョブスケジューリングシステムは、バッチ処理システム部１００と、第二のスケジューリング部として機能する先行重複実行部１１０とを具備している。これらのブロック１００，１１０は、コンピュータプログラムによって実現されている。図中、バッチ処理システム部１００は、第一のスケジューリング部として機能する通常ジョブスケジューラ１０１と、［キュー０］１０２と、［キュー１］１０３と、第一の資源領域として機能する［実行ホスト資源領域０］１０４と、第二の資源領域として機能する［実行ホスト資源領域１］１０５とを備えている。［キュー０］１０２は、ユーザ（クライアント）から通常ジョブを受け付ける。［キュー１］１０３は、先行重複実行ジョブを受け付ける。［実行ホスト資源領域０］１０４と、［実行ホスト資源領域１］１０５とは、資源分割管理機能を用いて作成されている。バッチ処理システム部１００は、既存の技術を適用して構築できるブロックである。
【００２８】
第３の実施の形態では、既存のオペレーティングシステムが提供している資源分割管理機能を利用する。この資源分割管理機能は、次のような機能を含んでいる。
−１台のコンピュータ上のＣＰＵを、複数の資源領域に分割して管理する機能。
−各資源領域に対して、優先して使用できるＣＰＵ量を設定することができる機能。
−ある資源領域で使用できるＣＰＵ量を超える要求があった場合に、他の資源領域で優先利用できるＣＰＵが限界に達していない場合には、余裕のあるＣＰＵを貸し出して割り当てることができる機能。
−余裕のあるＣＰＵを他の資源領域に貸し出しているときに、貸し出し元の資源領域でＣＰＵが必要になった場合には、貸し出しているＣＰＵを、例え貸し出し先で使用中であっても取り戻すことができる機能。
−ある資源領域で実行されているジョブを、別の資源領域に移行させて実行を継続する機能。
【００２９】
第３の実施の形態では、このような資源分割管理機能を利用してシステムのＣＰＵ資源を、２つの資源領域に分割する。図５において、［実行ホスト資源領域０］１０４は、ＣＰＵ保障ありの領域である。この［資源領域０］１０４で実行されるジョブは、資源分割管理機能によって設定されたＣＰＵを優先して使用することができる。一方、［実行ホスト資源領域１］１０５は、ＣＰＵ保障なしの領域である。この［資源領域１］１０５で実行されるジョブは、［実行ホスト資源領域０］１０４でＣＰＵが余っている場合に限り、その余っているＣＰＵを用いて実行される。
【００３０】
先行重複実行部１１０は、通常ジョブスケジュール状態把握部１１１と、先行重複実行ジョブ把握部１１２と、重複スケジューリング解決部１１３と、先行重複実行ジョブ選択部１１４と、ポリシー（方針）設定部１１５と、先行重複実行ジョブ発行部１１６とを備えている。
【００３１】
通常ジョブスケジュール状態把握部１１１は、通常ジョブスケジューラ１０１と通信して、通常ジョブのスケジューリング状態を把握する。先行重複実行ジョブ把握部１１２は、［キュー１］１０３と通信して、先行重複実行されているジョブの状態を把握する。重複スケジューリング解決部１１３は、［キュー１］１０３と通信して、同一のジョブについて行われた通常ジョブとしての第一のスケジューリングと、先行重複実行ジョブとしての第二のスケジューリングとの重複したスケジューリングの解決を行う。具体的には、先行重複実行ジョブが通常ジョブ枠の開始前に終了した場合には、［キュー１］１０３と通信して、通常ジョブ枠をキャンセルする。逆に、通常ジョブ枠が始まる迄に、先行重複実行ジョブが終了しなかった場合には、［キュー１］１０３と通信して、先行重複実行ジョブを［資源領域１］１０４から［資源領域０］１０３へ移行させる。このジョブは、［資源領域０］１０３にて、通常ジョブとして実行を継続する。
【００３２】
ポリシー設定部１１５は、どのような方針で通常ジョブの中から先行重複実行させるジョブを選択するかのポリシーを設定する。ポリシーは、管理者の操作によって登録され、更新される。また、ポリシー設定部１１５は、設定されたポリシーを先行重複実行部１１０の該当変数に反映させる。先行重複実行ジョブ選択部１１４は、通常ジョブスケジュール把握部１１１、及び、先行重複実行ジョブ把握部１１２で得られた情報と、ポリシー設定部１１５で設定されたポリシーを元に、先行重複実行させるジョブを選択する。先行重複実行ジョブ発行部１１６は、［キュー１］１０３と通信して、先行重複実行ジョブ選択部１１４で選択された通常ジョブと同じジョブを先行重複実行ジョブとして、［実行ホスト資源領域１］１０５で実行させる。
【００３３】
次に、第３の実施の形態におけるジョブスケジューリングシステムの動作について、図５の構成図と、図６及び図７のフローチャートとを参照して詳細に説明する。図６は、実行ホストにて動作環境を構築する手順を説明するフローチャートである。管理者が実行ホストに対して操作を行うと、図６のフローチャートに従って、実行ホストが、先行重複実行を可能にする環境を構築する。図６に示すように、まず、実行ホストは、資源分割管理機能により、既存の［資源領域０］１０４に加えて、［資源領域１］１０５を作成する（ステップ２０１）。次に、先行重複実行の候補となるジョブを受け付けるキューとして、［キュー１］１０３を作成する（ステップ２０２）。続いて、先行重複実行部１１０を起動する（ステップ２０３）。最後に、先行重複実行のポリシー設定を行う（ステップ２０４）。
【００３４】
先行重複実行のポリシー設定を行う場合には、例えば、管理者（ユーザ）向けに、ＣＵＩ（Ｃｈａｒａｃｔｅｒ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）／ＧＵＩ（Ｇｒａｐｈｉｃａｌ  Ｕｓｅｒ  Ｉｎｔｅｒｆａｃｅ）インタフェースを用意し、管理者が設定した値を、先行重複実行部１１０における当該変数の値として設定する方式を採用できる。また、管理者が設定ファイルを直接編集し、実行ホストに保存する方法なども考えられる。ここまでが動作環境の準備であり、管理者の操作に基づいて、実行ホストへの設定などが行われる。
【００３５】
次に、先行重複実行部１１０の動作を説明する。図７は、先行重複実行部１１０の動作を説明するフローチャートである。図７において、まず、先行重複実行部１１０における通常ジョブスケジュール状態把握部１１１が、通常ジョブスケジューラ１０１と通信して、通常ジョブのスケジュール状態を確認する（ステップ３０１）。通常ジョブスケジューラ１０１には、新たなジョブが投入され、スケジュール状態が刻々と変化している。そのため、通常ジョブスケジュール状態把握部１１１が、都度通常ジョブのスケジュール状態を確認している。次に、先行重複実行ジョブ把握部１１２が、［キュー１］１０３と通信して、先行重複実行ジョブの実行状況を確認する（ステップ３０２）。
【００３６】
このとき、先行重複実行ジョブ把握部１１２は、既に先行重複実行ジョブとして投入されているジョブについて、先行重複実行ジョブ枠の終了時間前に、通常ジョブ枠の開始時間が来ているものがあるか否かを判断する（ステップ３０３）。そのようなジョブがあった場合には、重複スケジューリング解決部１１３が［キュー１］１０３と通信して、その先行重複実行ジョブを［資源領域１］１０５から［資源領域０］１０４へ移す（ステップ３０４）。これにより、既に先行重複実行ジョブとして投入されていたジョブが、通常ジョブとして実行を継続することになる。一方、先行重複実行ジョブとして投入されたジョブが、通常ジョブ枠の開始前に終了していた場合には（ステップ３０５）、重複スケジューリング解決部１１３が［キュー１］１０３と通信して、そのジョブに割り当てられた通常ジョブ枠をキャンセルする（ステップ３０６）。
【００３７】
先行重複実行ジョブとしての実行が終了し、先行重複実行ジョブ枠に空きができると、先行重複実行部１１０は、新しい先行重複実行ジョブをその空き枠にスケジューリングできるようになる。先行重複実行ジョブ選択部１１４は、ポリシー設定部１１５と通信して、設定されているポリシーを確認する（ステップ３０７）。続いて、先行重複実行ジョブ選択部１１４は、［資源領域１］１０５に先行重複実行ジョブを投入するための先行重複実行ジョブ枠の空きがあるかどうかを確認する（ステップ３０８）。先行重複実行ジョブの空き枠がある場合、先行重複実行ジョブ選択部１１４は、その空き枠に先行重複実行ジョブとして投入できる適当なジョブがあるかどうかを通常ジョブの中から探す（ステップ３０９）。適当なジョブがあれば、先行重複実行ジョブ発行部１１６が［キュー１］１０３と通信して、そのジョブを［資源領域１］１０５で先行重複実行ジョブとして実行する（ステップ３１０）。
【００３８】
図７において、ステップ３１０が終了すると、最初に戻って一連の動作を繰り返す。ステップ３０８で［資源領域１］１０５に先行重複実行ジョブの空き枠がなかったり、ステップ３０９で先行重複実行ジョブとして適当なジョブが見つからなかったりした場合も同様に、最初に戻って一連の動作を繰り返す。
【００３９】
なお、［資源領域１］１０５で使用しているＣＰＵは、必要に応じて、［資源領域０］１０４に取り戻されてしまう場合がある。この場合、［資源領域１］１０５において、先行重複実行ジョブ枠で行われていた先行重複実行ジョブの実行は中断される。中断した先行重複実行ジョブは、［資源領域１］１０５が、再度ＣＰＵを借りられるようになるまで待機状態になる。［資源領域１］１０５が、［資源領域０］１０４から、再度ＣＰＵを借りてくると、中断した先行重複実行ジョブの実行が再開される。
【００４０】
このような中断によって、先行重複実行ジョブが、割り当てられた先行重複実行ジョブ枠の枠内で終了せず、通常ジョブの開始時間になったような場合には、通常ジョブ枠に移行して、通常ジョブとしてジョブの実行を継続する。通常ジョブ枠に移行する動作は、図７のステップ３０３〜ステップ３０６で説明した動作と同様である。
【００４１】
図８は、四つ目の実施の形態におけるジョブスケジューリングシステムの構成を説明するブロック図である。図５に示した第３の実施の形態では、既存システムをそのまま残して、これに先行重複実行部１１０を追加する構成になっている。しかし、既存システムにこだわる必要がなければ、図８に示すように、通常のジョブスケジューラの中に先行重複実行部の機能を組み込んで１つのスケジューラとしてしまうこともできる。この場合、通常ジョブスケジュール状態把握部などが不要になるので、第３の実施の形態と比べて構成を簡単にすることができる。
【００４２】
図８を参照すると、第４の実施の形態におけるジョブスケジューリングシステムは、ジョブスケジューラ４００と、通常ジョブを受け付ける［キュー０］４０３と、先行重複実行用のジョブを受け付ける［キュー１］４０４と、第一の資源領域として機能する［実行ホスト資源領域０］４０５と、第二の資源領域として機能する［実行ホスト資源領域１］４０６とを具備している。これらのブロックは、コンピュータプログラムによって実現されている。図８において、［キュー０］４０３、［キュー１］４０４、［資源領域０］４０５、［資源領域１］４０６は、それぞれ、第３の実施の形態における［キュー０］１０２、［キュー１］１０３、［資源領域０］１０４、［資源領域１］１０５と同じ機能を有するブロックである。
【００４３】
図示するように、第４の実施の形態におけるジョブスケジューラ４００は、第一のジョブスケジューリング部として機能する通常ジョブ処理部４０１と、第二のジョブスケジューリング部として機能する先行重複実行ジョブ処理部４０２とを備えている。通常ジョブ処理部４０１は、第３の実施の形態における通常ジョブスケジューラ１０１に相当するもので、バックフィル型又はその他の方式でスケジューリングを行う機能を有する。先行重複実行ジョブ処理部４０２が新たに提供されるブロックである。先行重複実行ジョブ処理部４０２は、第３の実施の形態における先行重複実行ジョブ把握部１１２と、重複スケジューリング解決部１１３と、先行重複実行ジョブ選択部１１４と、ポリシー選択部１１５と、先行重複実行ジョブ発行部１１６との各機能を合わせたものに相当する。
【００４４】
第３の実施の形態では、所定の方式、例えば、バックフィル型でスケジューリングを行っている既存のシステムに新たな機能を追加する構成になっていた。一方、第４の実施の形態では、既存のシステムが採用するスケジューリング方式に制約されないので、任意のスケジューリング方式を採用できる構成になっている。動作に関しては、第４の実施の形態における動作は、図６及び図７に示した第３の実施の形態における動作と同様になる。
【００４５】
図９及び図１０の説明図を参照して、本発明を適用していない関連技術のスケジューリングと、本発明による第３及び第４の実施の形態におけるスケジューリングとを対比してみる。具体的に、それぞれのスケジューリングシステムに、ジョブ［ｊｏｂ１］〜ジョブ［ｊｏｂ８］が投入された場合について説明する。図９は、関連システムによるスケジューリングの説明図である。図９に示すように、関連技術のジョブスケジューリングシステムによりジョブ［ｊｏｂ１］〜ジョブ［ｊｏｂ８］をスケジューリングすると、まず、ジョブ［ｊｏｂ１］が実行される。ジョブ［ｊｏｂ１］が終了すると、次に、ジョブ［ｊｏｂ２］が実行される。ジョブ［ｊｏｂ２］が終了すると、次に、ジョブ［ｊｏｂ３］〜ジョブ［ｊｏｂ５］が並行して実行される。それから、ジョブ［ｊｏｂ６］は、ジョブ［ｊｏｂ３］の終了後に実行される。ジョブ［ｊｏｂ７］，ジョブ［ｊｏｂ８］は、ジョブ［ｊｏｂ４］の終了後に並行して実行される。
【００４６】
図１０は、第３及び第４の実施の形態におけるジョブスケジューリングシステムによるスケジューリングの説明図である。図１０において、横軸の上側は、［資源領域０］１０４又は［資源領域０］４０５で実行される通常ジョブのスケジューリング状態を示している。横軸の下側は、［資源領域１］１０５又は［資源領域１］４０６で実行される先行重複実行ジョブのスケジューリング状態を示している。図中、横軸の上側に示されているように、通常ジョブのスケジューリング状態は、図９のスケジューリングと同一になっている。すなわち、通常ジョブのスケジューリングは、関連技術のジョブスケジューリングシステムによってスケジューリングすることが可能である。通常ジョブは、常に優先的にＣＰＵを使うことができるので、ターンアラウンドタイムは保障される。
【００４７】
一方、横軸の下側に示されているように、先行重複実行ジョブのスケジューリングは、第３の実施の形態における先行重複実行部１１０の機能や第４の実施の形態における先行重複実行ジョブ処理部４０２の機能を用いて行われている。先行重複実行ジョブは、後方にスケジューリングされている通常ジョブの中から選択する。どのジョブを選択するかは運用ポリシーやシステムの特性による。例えば、先行重複実行ジョブとして選択するジョブは、２ＣＰＵ分までのジョブのみとかシングルＣＰＵのジョブのみを対象にするなど、使用ＣＰＵの数量に基づくポリシーを設定することが可能である。
【００４８】
図１０の例では、シングルＣＰＵのジョブのみを先行重複実行ジョブの選択対象にするというポリシーが設定されている。このポリシーに従って、シングルＣＰＵのジョブであるジョブ［ｊｏｂ３］，ジョブ［ｊｏｂ７］，ジョブ［ｊｏｂ８］が、先行重複実行ジョブとして選択されている。そして、ジョブ［ｊｏｂ３］，ジョブ［ｊｏｂ７］，ジョブ［ｊｏｂ８］に対して、それぞれ１ＣＰＵ分の先行重複実行ジョブ枠が割り当てられている。図中、同一のジョブではあるが、先行重複実行ジョブ枠で実行される方には、“ａ”の文字を付記している。例えば、ジョブ［ｊｏｂ３］は、通常ジョブ枠の方で実行されるときには“ｊｏｂ３”と表記し、先行重複実行ジョブ枠の方で実行されるときには“ｊｏｂ３ａ”と表記している。
【００４９】
先行重複実行ジョブは、［資源領域１］１０５又は［資源領域１］４０６で実行される。［資源領域１］１０５又は［資源領域１］４０６では、通常ジョブがＣＰＵを使っていないときに、その遊休ＣＰＵを［資源領域０］１０４又は［資源領域０］４０５から借りてきて、ジョブを実行する。通常ジョブが、先行重複実行ジョブで使用しているＣＰＵを必要としたら、［資源領域１］１０５又は［資源領域１］４０６は、借りているＣＰＵを即座に［資源領域０］１０４又は［資源領域０］４０５へ返却する。このＣＰＵの貸し借り処理は、オペレーティングシステムの資源分割管理機能に任せることが可能である。
【００５０】
第３及び第４の実施の形態では、通常ジョブを先行重複実行ジョブとして実行しても、ターンアラウンドタイムを保障する。そのために、先行重複実行ジョブとして実行を開始した後も、図１０の横軸の上側に確保した通常ジョブ枠を確保したままにしている。その後、先行重複実行ジョブ枠で実行されていた先行重複実行ジョブが、通常ジョブ枠の開始前に終了した場合には、通常ジョブ枠の取り消しを行う。一方、先行重複実行ジョブが、先行重複実行ジョブ枠で終了しなかった場合には、その先行重複実行ジョブを、先行重複実行ジョブ枠から通常ジョブ枠へ移して、ジョブの実行を継続する。
【００５１】
図１１は、先行重複実行ジョブから通常ジョブへの移行についての説明図である。図１１において、横軸は時間の経過を示している。横軸と交差する縦軸が位置する時間は、ジョブ［ｊｏｂ１］に割り当てられた通常ジョブ枠の開始時間を示している。また、横軸の上側は、［資源領域０］１０４又は［資源領域０］４０５で実行されるジョブのスケジューリング状態を示し、横軸の下側は、［資源領域１］１０５又は［資源領域１］４０６で実行されるジョブのスケジューリング状態を示している。
【００５２】
図１１において、ジョブ［ｊｏｂ１］は、まず、［資源領域１］１０５又は［資源領域１］４０６にて割り当てられた先行重複実行ジョブ枠で、先行重複実行ジョブ“ｊｏｂ１ａ”として実行される。先行重複実行ジョブ“ｊｏｂ１ａ”は、この先行重複実行ジョブ枠の枠内では終了しない。その後、通常ジョブ枠の開始時間になると、先行重複実行ジョブ“ｊｏｂ１ａ”は、［資源領域１］１０５又は［資源領域１］４０６から［資源領域０］１０４又は［資源領域０］４０５へ移される。先行重複実行ジョブ“ｊｏｂ１ａ”は、［資源領域０］１０４又は［資源領域０］４０５へ移されると、［資源領域０］１０４又は［資源領域０］４０５にて割り当てられた通常ジョブ枠にて、通常ジョブ“ｊｏｂ１”として継続して実行される。
【００５３】
第１〜第４の実施の形態における効果について説明する。第１〜第４の実施の形態における第１の効果は、遊休ＣＰＵを減らし、システム全体の利用率を向上させることができることである。その理由は、第二のジョブスケジューリング部などが、先行重複実行ジョブのスケジューリングを行うので、通常ジョブが一時的にＣＰＵを開放しても、そのＣＰＵは遊休状態にならず、先行重複実行ジョブの処理に使われるためである。
【００５４】
第２の効果は、ジョブのターンアラウンドタイムが改善される可能性があることである。すなわち、第一のジョブスケジューリング部などが、通常ジョブのスケジューリングを行うので、通常ジョブ枠の確保は常に保障され、最低でもターンアラウンドタイムが保障されている。一方で、第二のジョブスケジューリング部などが、先行重複実行ジョブのスケジューリングを行うので、もし先行重複実行ジョブとして選択されて通常ジョブ枠の前で終了すれば、ターンアラウンドタイムは短くなる。また、通常ジョブ枠の前で終了しなかった場合でも、先行重複実行ジョブ枠から通常ジョブ枠へ移行してジョブの実行を継続できるので、ターンアラウンドタイムは短縮される。
【符号の説明】
【００５５】
１０  ジョブスケジューリングシステム
１１  第一のジョブスケジューリング部
１２  第二のジョブスケジューリング部
１３  第一の資源領域
１４  第二の資源領域
１００  バッチ処理システム部
１０１  通常ジョブスケジューラ
１０２，４０３  キュー０
１０３，４０４  キュー１
１０４，４０５  実行ホスト資源領域０
１０５，４０６  実行ホスト資源領域１
１１０  先行重複実行部
１１１  通常ジョブスケジュール状態把握部
１１２  先行重複実行ジョブ把握部
１１３  重複スケジューリング解決部
１１４  先行重複実行ジョブ選択部
１１５  ポリシー設定部
１１６  先行重複実行ジョブ発行部
４００  ジョブスケジューラ
４０１  通常ジョブ処理部
４０２  先行重複実行ジョブ処理部
【図１】
2010182199.tif 000003
【図２】
2010182199.tif 000004
【図３】
2010182199.tif 000005
【図４】
2010182199.tif 000006
【図５】
2010182199.tif 000007
【図６】
2010182199.tif 000008
【図７】
2010182199.tif 000009
【図８】
2010182199.tif 000010
【図９】
2010182199.tif 000011
【図１０】
2010182199.tif 000012
【図１１】
2010182199.tif 000013