(57)【要約】【課題】  複数の情報処理ユニット毎にジョブが投入されるキューが設けられた分散処理システムに対して、高優先度のジョブについては高優先度ではない通常ジョブより先に実行させる制御を行うジョブのスケジューリングにおいて、キューに投入された通常ジョブの実行開始を、できるだけキューへの投入順となるよう平準化させる。【解決手段】  各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各キューに投入された高優先度のジョブの処理実行予想時間とに基づいて、キュー毎にキュー選択基準値を算出する。移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を、全てのキューに投入された通常ジョブについてキューへの投入時刻の早い順番に移動処理対象ジョブとして選択し順次実行する。【選択図】図５
2008090507.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御がコンピュータにより実行されるジョブ実行のスケジューリングプログラムであって、
上記コンピュータを、
各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、
全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、
上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、
上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、
して機能させることを特徴とするジョブ実行のスケジューリングプログラム。
【請求項２】
上記コンピュータには、１つまたは複数のキューをグループとして定義するキューグループ定義の記憶手段が更に設けられ、
上記投入されるジョブには、キューグループを指定するための情報が付加されており、
上記第三の手段は、上記キューグループを指定するための情報に基づいて上記キューグループ定義を検索して、得られた該キューグループに含まれるキューのうちキュー選択基準値が最も小さいキューに上記移動処理対象ジョブを移動させることを特徴とする請求項１に記載のジョブ実行のスケジューリングプログラム。
【請求項３】
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御がコンピュータにより行われるジョブ実行のスケジューリング方法であって、
上記コンピュータを、
各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、
全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、
上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、
上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、
して機能させることを特徴とするジョブ実行のスケジューリング方法。
【請求項４】
上記コンピュータには、１つまたは複数のキューをグループとして定義するキューグループ定義の記憶手段が更に設けられ、
上記投入されるジョブには、キューグループを指定するための情報が付加されており、
上記第三の手段は、上記キューグループを指定するための情報に基づいて上記キューグループ定義を検索して、得られた該キューグループに含まれるキューのうちキュー選択基準値が最も小さいキューに上記移動処理対象ジョブを移動させることを特徴とする請求項３に記載のジョブ実行のスケジューリング方法。
【請求項５】
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御を行うジョブ実行のスケジューリング装置であって、
各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、
全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、
上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、
上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、
を有することを特徴とするジョブ実行のスケジューリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムにおけるジョブ実行のスケジューリングに関する。
【背景技術】
【０００２】
企業内に分散配置されているパーソナルコンピュータ等の情報処理装置（以下、「マシン」と称する）を遊休時に有効に利用するために、各マシンを用いてグリッドコンピューティングシステムを構築することが考えられている。
【０００３】
このようなグリッドコンピューティングシステムを用いて、シミュレーションジョブ等の大規模計算が行われるジョブを実行する立場からは、ジョブの特定に応じて最適なマシンで実行したいという要求がある。例えば、大規模計算が必要なジョブについては、大容量メモリを搭載したマシンにジョブを投入するケース等が該当する（以下、処理を実行させるマシンを指定したジョブを「マシン指定ジョブ」と称する）。
【０００４】
グリッドコンピューティングシステムにおける一般的なスケジューラでは、複数のマシンに共通するキュー（実行待ち行列）を設け、このキューに対してジョブを投入する構成となっている。このような構成では、マシンを指定してジョブを投入することはできない。
【０００５】
このため、マシン毎にキューを設け、マシン指定ジョブについては指定されたマシンに対応するキューへ投入する構成も採用されつつある。また、部門等で複数のマシンをグルーピングし、部門を指定したジョブについては該部門に対応する部門グループに属するいずれかのマシンのキューに投入する構成も考えられている。このような構成の例を図９を用いて説明する。
図９の例では、部門Ｘに２台のマシン＃１、マシン＃２を設け、部門Ｙに１台のマシン＃３を設けられている。このうちマシン＃２は他のマシン＃１、＃３と比較して大容量のメモリを搭載したマシンであり、ジョブの処理能力が高い。一方投入されるジョブは、特定のマシンを指定することなくキューに投入されるジョブ、部門を指定して該部門に設けられたマシンのキューに投入されるジョブ、マシンを指定して該マシンに対応するキューに投入されるジョブがある。図９の例では部門Ｘを指定したジョブについてはマシン＃１、マシン＃２に対応するキュー＃１、キュー＃２に投入され、部門Ｙを指定したジョブについてはマシン＃３に対応するキュー＃３に投入される。
【０００６】
なお、図中（図９及び後述する図１０）における○はジョブを示し、○内の数字はキューグループに投入された順番を示す。図９では、ジョブ１、ジョブ２、ジョブ３がそれぞれマシン１，２，３で実行中であり、ジョブ４からジョブ１５が、マシンに対応するキューに投入されて実行待ちの状態にある。
【特許文献１】特開平３−１９０３５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
上記のような構成において、通常ジョブ（高い優先度が設定されていないジョブ）はマシンが特定されずいずれかのマシンに対応するキューに投入されるか、あるいは指定された部門グループのキューに投入される。
【０００８】
一方マシン指定ジョブはマシンを特定した実行依頼であり、実行環境の選択肢が少なくなることから、通常ジョブと同じ条件で待たせることは好ましくなく、高い優先度で待ち状態にする必要がある場合が多い。
【０００９】
このようにマシン指定ジョブを高優先度設定で投入した場合、指定されたマシンに対応するキューで実行待ちとなっている通常ジョブは、マシン指定ジョブの投入の都度割り込まれてしまう。
【００１０】
この例を図１０に示す。この図１０は、図９に示した各ジョブの実行状態において、新たにマシン＃２に対応するキュー＃２に対して優先度の高いジョブＡ、Ｂが投入された状態を示す。ジョブＡ，Ｂは優先度が高いので、マシン＃２が実行中のジョブ２の次に処理がなされるようキューの先頭に割り込みがなされ、ジョブ５，８，１１，１４はジョブＡ，Ｂが終了するまで待たされることとなる。したがって部門Ｘ内ではジョブ５より後に投入がなされたジョブ７が先に実行されることとなる。また、アプリＡ全体では、ジョブ８よりもジョブ９，１０、１２が先に実行されることとなる。
【００１１】
上記特許文献１を含む従来技術では、上述したように優先度の高くないジョブが早い時刻にキューに投入されたにも係わらず、当該キューに優先度の高いジョブが投入されると待たされてしまい、より遅い時刻に他のキューに投入されたジョブよりも実行が遅くなるという問題点を解消するものはなかった。
【００１２】
この発明は、上述した従来技術による問題点を解消するためになされたものであって、複数の情報処理ユニット毎に該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムにおいて、複数のキューに投入された通常ジョブの実行開始を、できるだけキューへの投入順となるよう平準化させる方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記の問題を、
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御がコンピュータにより実行されるジョブ実行のスケジューリングプログラムであって、上記コンピュータを、各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、して機能させる構成により解決するものである。
【００１４】
更に、上記コンピュータには、１つまたは複数のキューをグループとして定義するキューグループ定義の記憶手段が更に設けられ、  上記投入されるジョブには、キューグループを指定するための情報が付加されており、上記第三の手段は、上記キューグループを指定するための情報に基づいて上記キューグループ定義を検索して、得られた該キューグループに含まれるキューのうちキュー選択基準値が最も小さいキューに上記移動処理対象ジョブを移動させるよう構成を採用しても良い。
【発明の効果】
【００１５】
上記の構成により、複数の情報処理ユニット毎に該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムにおいて、複数のキューに投入された通常ジョブ（高い優先度が設定されていないジョブ）の実行開始を、キューへの投入順となるよう平準化させることができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態を、図面を参照して詳細に説明する。
１）本発明の概念の説明
まず、本発明の概念について説明し、その後、実施の形態の具体的な内容を説明する。
【００１７】
図１は、本発明の概念を示す図である。
本発明では、対象となるキューから通常ジョブを選択し、優先度の高いマシン指定ジョブの割り当て及び各キューの実行待ち（マシンにおける処理中のジョブの終了予測）に基づいて、キューへの投入順にジョブが実行されるよう調整がなされる。
図１の例では、図の左側が平準化処理前の各キューにおける実行待ちジョブの状態が示されており、これから説明する通常ジョブ平準化機能がなされた状態は図の右側に示されている。
より具体的に説明すると、通常ジョブ平準化機能の実行前は、マシン♯２に対応するキュー＃２に優先度の高いマシン指定ジョブであるジョブＡ，ジョブＢ、ジョブＣが投入されているため、ジョブ５以降のジョブが他のキューに投入されたジョブより待たされた状態となっている。この状態で通常ジョブ平準化機能を実施することにより、投入順に通常ジョブが実行されるよう調整がなされる。
２）本発明の一実施形態におけるシステム構成
次に、本発明の一実施形態におけるシステム構成を図２のブロック図を用いて説明する。
【００１８】
図中、１は本実施形態のジョブのスケジューリングを実行するマスタサーバである。このマスタサーバ１には、図示しないが後述する処理を実行するプロセッサ、該プロセッサを動作させるプログラムや各種テーブル（リスト）及び各種データベース(以下の説明及び図中ではデータベースを「DB」と称する)、キューに投入されたジョブの情報等を保持するための記憶手段（半導体メモリやハードディスクドライブ等）、アプリを実行している利用者端末からのジョブを受信したりキューに投入されたジョブを送出して各マシンに実行させるためにネットワークにアクセスする通信手段を少なくとも有する。
【００１９】
上記のようなハードウェア構成を有するマスタサーバ１において、ジョブスケジューリング機能１１は、マシン＃１からマシン＃３に対応して設けられたキュー＃１（２１）、キュー＃２（２２）、キュー＃３（２３）に利用者端末から受付けたジョブの投入を行う。またこのジョブスケジューリング機能１１はジョブ平準化機能を含むものであり、各キューに投入されたジョブの平準化処理を行う。
【００２０】
更にマスタサーバ１には、ジョブスケジューリング機能１１がジョブの投入およびジョブの平準化を行うために、利用者情報DB３１、キューグループ定義DB３２、キュー状況DB３３、資源定義DB３４が設けられ、また通常ジョブ実行待ちリスト３５、通常ジョブ実行待ち投入順リスト３６、キュー選択基準値テーブル３７といったリスト（テーブル）が設けられる。これらのDBまたはテーブルの具体的な構造については後述する。なお、上述したDB等は、必ずしも物理的にマスタサーバ１上の記憶手段上に構築する必要はなく、マスタサーバ１が容易にアクセスし得る別のハードウェア資源上に構築する構成としても良い。
【００２１】
また、図上ではキュー＃１からキュー＃３の３つのキューのみを図示しているが、これは後述するアプリAを実施することができる3台のマシンに対応するものである。図示は省略したが複数のアプリに係わるジョブを実施が依頼された場合には、それぞれアプリに対応するマシンにジョブが投入される。
【００２２】
以下、このようなシステムにおけるジョブ投入時の処理およびジョブ平準化処理を説明する。
３）ジョブ投入時の処理
まず、ジョブ投入コマンドの例を以下に示す。
qsub -q キュー名 [-m マシン名] [-local] 実行バッチファイル
ジョブ投入コマンドの命令qsubに付与されるオプションは下記のとおりである。
-q  ：キュー名としてアプリ名称を指定する。
【００２３】
-ｍ ：実行を行うマシンを指定する。
【００２４】
このオプションが指定された場合に、ジョブは指定された計算サーバでのみ実      行される。
【００２５】
-local  ：ジョブを自部門内のマシンでのみ実行する場合にこれを指定するものであ          。る。
【００２６】
このような指定を可能としたのは、各マシンは（図２では図示を省略した          が）各部門に設けられたDBなどの情報資源にアクセスしてジョブを実行する          ものであるので、当該部門に設けられたマシンにジョブを実行させたほうが          、他の部門に設けられたマシンにジョブを実行させるよりも、余分なトラフ          ィックが生じることがなくなり好都合なためである。
【００２７】
つぎに、ジョブ投入の依頼を受けたマスタサーバ１上のジョブ投入制御処理を図３を用いて説明する。なお、以下の１）から１５）で示した各ステップは、図中では丸で囲んだ数字で表記している。
1)ジョブ投入コマンドの-ｑオプションにて指定されたアプリ名を得る。
2)ジョブ投入コマンドのコマンド列中に-localが指定されているかを解析し、指定され
ている場合は下記のステップ3からステップ6を実行する。一方指定がない場合は    、  下記のステップ7に進む。
3)−localが指定されている場合は、利用者と所属情報（部門名）とを対応づけて記録さ  れた利用者情報ＤＢから、利用者の所属情報（部門名）を得る。なお、利用者について  は予めマスタサーバ１により認証がなされているのでこの認証情報を用いて利用者を特  定し、該利用者の所属情報を利用者情報DBから検索が成される。
4)利用者の所属に一致する部門名とステップ1で求めたアプリ名から、キューグループ定  義ＤＢのアプリ（部門名）を検索し、ジョブを投入すべきキューリストを得る。例え    ば、部門Ｘの利用者であれば、キュー＃１、＃２がリストとして得られる。
5)範囲として部門名を設定する。（ここで設定された範囲は後述するステップ15におい    てジョブ名に対応する範囲フィールドに記録される。後述するステップ9、１２も同    様。）
6)キューリストとして得られたキューから、割り当てられたジョブの数が少ないキュー    を選び、ジョブ投入対象のキューとして指定する。
7)上記ステップ2でコマンド列中に-localの指定がない場合には、更に-ｍでマシン名      が指定されているか否かを解析し、マシン名が指定されている場合はステップ8か      ら10に進む。一方マシン名が指定されていない場合はステップ11から13に進む。
8)-ｍで指定されたマシン名とステップ1で求めたアプリ名から、キューグループ定義ＤＢ  のアプリ（マシン名）をを検索し、キュー情報を得る。
9)範囲としてマシン名を設定する。
10)ジョブに対して高優先度設定を行う。
11)マシン名が指定されていない場合は、-ｑオプションに一致するアプリ名から、キュ
ーグループ定義ＤＢのアプリ（全社）を検索し、キューリストを得る。
12)範囲として「全社」を設定する。
13)キューリストとして得られたキューから、割り当てられたジョブの数が少ないキュー
を選び、ジョブ投入対象のキューとして指定する。
14)選択されたキューにジョブを投入する。
【００２８】
なお、上記ステップ10にて高優先度として設定されたジョブについては、割り込みがな  されて通常ジョブよりも早く実行されるようキューに投入される。
15)投入されたジョブの状況をキュー状況ＤＢに記録する。
【００２９】
キュー状況ＤＢには、ジョブ名と対応づけて、範囲（上記ステップ5、9、12にて設定  された情報）、優先度（通常ジョブは「中」とする）、投入日時が記録される。
【００３０】
上述した各ステップは、依頼者端末からジョブ投入コマンドを受信するたびに実行さ  れる。
【００３１】
４）通常ジョブ平準化機能
次に、キューに投入されたジョブの実行順序を平準化する処理の例を図４及び図５を用いて説明する。
【００３２】
1)  キューグループ定義DBから、平準化を行うアプリに対応するキューを選定する。        
【００３３】
図４における実施形態では、アプリAを実行するマシンに対応するキューに投入    されたジョブの平準化を行うものであり、キュー＃１、＃２、＃３が選定される      。
【００３４】
なお、図示は省略するが、キューグループ定義DBにはアプリ毎にキューグループ定義がなされており、アプリA以外のアプリに係わるキューについても、同様の平準化制御がなされるものとする（例えば、他のアプリBを実行するマシンに対応してキュー＃４、＃５、＃６が設けられている場合には、キューグループ定義DBからこれらのキューが選定され、後述の動作と同様の平準化処理がなされる）。
【００３５】
2)キュー状況ＤＢを参照して、各キューから実行待ち状態の通常ジョブ（優先度中の      ジョブ）を抽出し、通常ジョブ実行待ちリストに記録する。
【００３６】
3)通常ジョブ実行待ちリストに記録された通常ジョブについて、投入日時順に並び替      え、通常ジョブ実行待ち投入順リストに記録する。
【００３７】
4)各キューから、実行中ジョブの経過時間を得る。
【００３８】
5)各キューの実行中ジョブの残り時間を算出する。
【００３９】
この実行中ジョブの残り時間は、下記の計算式で算出される。
【００４０】
実行中ジョブの残り時間（秒）
＝アプリの実行制限時間（秒）−実行中ジョブの経過時間（秒）
なお、資源定義DBには各アプリ毎に、マシンがジョブを実行する際の制限時間      が定義されている（図４ではアプリAの制限時間のみを示している）。
【００４１】
本実施形態においては、各マシンの制限時間は均等として設定されている。こ      れは、マシン＃１、＃２、＃３がアプリAに係わるジョブの処理時間がほぼ同一とし    ているためである。（但し、大規模演算が必要なジョブについてはメモリ容量の大き    いマシン＃２の処理能力が高いものとする。）
本発明は、マシン毎の処理時間が全く同一か、ほぼ同一の場合に好適である。  
【００４２】
6)キュー状況ＤＢから「範囲」のフィールドを参照して、各キューの実行待ち指定ジ      ョブ数を得る。
【００４３】
7)各キュー毎に、キュー選択基準値を作成する。
【００４４】
このキュー選択値は、例えば以下の計算式にて算出される。
【００４５】
選択基準値＝実行中ジョブの残り時間（秒）
＋アプリの実行制限時間（秒）×実行待ちのマシン指定ジョブ数
これは、実行中ジョブの残り時間に加え、高優先度で実行がなされるマシンを考      慮してジョブが全て終了する時間を予測して加算することを意味しており、次に        処理がなされる通常ジョブの処理開始時間を予測してこれを選択基準値とするこ        とを意味する。
【００４６】
図４の例では、キュー＃２にマシン指定ジョブが３つ投入されているので、通        常ジョブはこれらのマシン指定ジョブが終了してから実行されることとなる。こ      のため、制限時間３６００秒にジョブ数３を掛けた値を実行中ジョブの残り時間        に加算することで、通常ジョブの処理開始予想時間である13860秒が、キュー＃        ２の選択基準値として設定される。
【００４７】
8)通常ジョブ実行待ち投入順リストに記載された通常ジョブについて、投入日時の早      いジョブから順に、対応するジョブ情報を読み出して下記9から１２の平準化処理
を実行する。
【００４８】
9)読み出したジョブ情報における「範囲」の情報について、キューグループ定義ＤＢ      を参照して対応するキューを抽出する。図５の例では、ジョブ４ならば範囲は「        全社」である全てのキュー（キュー＃1、＃２、＃３）が抽出される。（（ジョ        ブ５であれば範囲は「部門Ｘ」であるので、部門Ｘに対応するキューであるキュ        ー＃１、キュー＃２が抽出されることとなる。）
上記ステップ9)で抽出されたキューのうち、キュー選択基準値が小さいキューを選      択する。図５の例では、キュー＃１が選択されることとなる。
現在の平準化処理対象ジョブを上記ステップ10で選択されたキューに移動する。な
お、選択されたキューが当該ジョブが投入されたキューであれば移動処理は実行      されない。
現在の平準化処理対象ジョブが存在するキュー（上記ステップ10で移動がなされた
場合は移動先のキュー）について、アプリの制限時間を加算する。
実行待ち投入順リスト上にある全てのジョブ情報についてステップ8から13の処理を    実行した場合は終了する。まだ未実行のジョブ情報があれば、ステップ8から13の処理を実行    する。
【００４９】
５）遷移例
上記の実施形態による平準化処理の一例を図６、図７を用いて説明する。
【００５０】
図６の例では、通常ジョブ実行待ち投入順リストに記載された各通常ジョブのうち、ジョブ４が最も投入日時が早いので、まずジョブ４について移動処理がなされる（図５のステップ8）。
【００５１】
ジョブ４の範囲は全社であり、キューグループ定義DBを参照すると範囲が全社である場合はキュー＃１、＃２、＃３の全てのキューが移動範囲となる（図５のステップ9）。
【００５２】
したがって、移動範囲となるキュー＃１、＃２、＃３のうち、最もキュー選択基準値が小さいキューであるキュー＃１が移動先として選択される（図５のステップ10）。
【００５３】
但し、ジョブ４はもともとキュー＃１に投入されたジョブであるので、実際には移動処理はされない。
【００５４】
選択されたキュー＃１の基準値に、アプリの制限時間を加算する（図５のステップ12）。
【００５５】
ジョブ４について平準化処理が終了したので、ジョブ４の次に投入日時の早いジョブ５が選択される（図５のステップ13、8）。
【００５６】
ジョブ５の範囲は部門Xであり、キューグループ定義DBを参照すると範囲が部門Xである場合はキュー＃１、＃２が移動範囲となる（図５のステップ9）。
【００５７】
したがって、移動範囲となるキュー＃１、＃２のうち、最もキュー選択基準値が小さいキューであるキュー＃１が移動先として選択される（図５のステップ10）。
【００５８】
ジョブ５がキュー＃２から選択されたキュー＃１に移動がなされる（図５のステップ11）。
【００５９】
選択されたキュー＃１の基準値に、アプリの制限時間を加算する（図５のステップ12
）。
【００６０】
ジョブ５について平準化処理が終了したので、ジョブ５の次に投入日時の早いジョブ６が選択される（図５のステップ13、8）。
【００６１】
以下、ジョブ投入日時が早い通常ジョブから順番に図５のステップ8から12の平準化処理が実行されるが、図６及び図７を参照すれば容易に理解できよう。
【００６２】
このようにして平準化された結果を図８に示す。
【００６３】
以上の前記各実施形態により本発明を説明したが、本発明の技術的範囲は実施形態に記載の範囲には限定されず、これら各実施形態に多様な変更又は改良を加えることが可能である。そして、かような変更又は改良を加えた実施の形態も本発明の技術的範囲に含まれる。このことは、特許請求の範囲及び課題を解決する手段からも明らかなことである。
【００６４】
例えば、本発明においてはグリッドコンピューティングシステムに適用する例を説明したが、他の分散システムに適用しても良い。ジョブを実行する情報処理ユニットはパーソナルコンピュータ等のマシンを例にしたが、物理的には１台のコンピュータ上に実装された複数の情報処理ユニットで分散処理を行うシステムに適用しても良い。
（付記１）
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御がコンピュータにより実行されるジョブ実行のスケジューリングプログラムであって、
上記コンピュータを、
各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、
全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、
上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、
上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、
して機能させることを特徴とするジョブ実行のスケジューリングプログラム。
（付記２）
上記コンピュータには、１つまたは複数のキューをグループとして定義するキューグループ定義の記憶手段が更に設けられ、
上記投入されるジョブには、キューグループを指定するための情報が付加されており、
上記第三の手段は、上記キューグループを指定するための情報に基づいて上記キューグループ定義を検索して、得られた該キューグループに含まれるキューのうちキュー選択基準値が最も小さいキューに上記移動処理対象ジョブを移動させることを特徴とする付記１に記載のジョブ実行のスケジューリングプログラム。
（付記３）
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御がコンピュータにより行われるジョブ実行のスケジューリング方法であって、
上記コンピュータを、
各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、
全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、
上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、
上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、
して機能させることを特徴とするジョブ実行のスケジューリング方法。
（付記４）
上記コンピュータには、１つまたは複数のキューをグループとして定義するキューグループ定義の記憶手段が更に設けられ、
上記投入されるジョブには、キューグループを指定するための情報が付加されており、
上記第三の手段は、上記キューグループを指定するための情報に基づいて上記キューグループ定義を検索して、得られた該キューグループに含まれるキューのうちキュー選択基準値が最も小さいキューに上記移動処理対象ジョブを移動させることを特徴とする付記３に記載のジョブ実行のスケジューリング方法。
（付記５）
複数の情報処理ユニット毎に、該情報処理ユニットにより処理されるジョブが投入されるキューが設けられた分散処理システムに対して、高優先度として設定されたジョブについては高優先度ではない通常ジョブより先に実行されるようキューに投入する制御を行うジョブ実行のスケジューリング装置であって、
各情報処理ユニットにおいて実行中のジョブの処理終了予想時間と、各情報処理ユニットに対応するキューに投入された高優先度のジョブの処理実行予想時間とに基づいて、各情報処理単位に対応するキュー毎にキュー選択基準値を算出する第一の手段と、
全てのキューに投入された通常ジョブのうち、キューへの投入時刻の最も早い通常ジョブを移動処理対象ジョブとして抽出する第二の手段と、
上記移動処理対象ジョブをキュー選択基準値が最も小さいキューに移動させると共に、該移動処理対象ジョブの処理実行予想時間に基づいて当該キューにおける新たなキュー選択基準値を算出する処理を実行する第三の手段と、
上記第三の手段において処理がなされた移動処理対象ジョブの次にキューへの投入時刻の早い通常ジョブを新たな移動処理対象ジョブとして抽出し、上記第三の手段における処理を実行させる第四の手段と、
を有することを特徴とするジョブ実行のスケジューリング装置。
（付記６）
上記装置には、１つまたは複数のキューをグループとして定義するキューグループ定義の記憶手段が更に設けられ、
上記投入されるジョブには、キューグループを指定するための情報が付加されており、
上記第三の手段は、上記キューグループを指定するための情報に基づいて上記キューグループ定義を検索して、得られた該キューグループに含まれるキューのうちキュー選択基準値が最も小さいキューに上記移動処理対象ジョブを移動させることを特徴とする付記５に記載のジョブ実行のスケジューリング装置。
【図面の簡単な説明】
【００６５】
【図１】本発明の概念を示す図である。
【図２】本発明の一実施形態のシステム構成を示す図である。
【図３】本発明の一実施形態におけるジョブ投入処理を説明するフローチャートで          ある。
【図４】本発明の一実施形態の通常ジョブ平準化機能を説明するフローチャート（          その１）である。
【図５】本発明の一実施形態の通常ジョブ平準化機能を説明するフローチャート（        その２）である。
【図６】本発明の一実施形態における通常ジョブ平準化の遷移の例を示すフローチ          ャート（その１）である。
【図７】本発明の一実施形態における通常ジョブ平準化の遷移の例を示すフローチ          ャート（その２）である。
【図８】本発明の一実施形態における通常ジョブ平準化の結果の例を示す図である。
【図９】従来の分散処理システムにおけるジョブのスケジューリング処理の例を示          す図である。
【図１０】従来の分散処理システムにおけるジョブのスケジューリング処理の問題          点の例を示す図である。
【符号の説明】
【００６６】
１  マスタサーバ１
１１  ジョブスケジューリング機能
２１〜２３  キュー
３１  利用者情報DB
３２  キューグループ定義DB３２
３３  キュー状況DB３３
３４  資源定義DB
３５  ジョブ実行待ちリスト
３６  通常ジョブ実行待ち投入順リスト
３７  キュー選択基準値テーブル
【図１】
2008090507.tif 000003
【図２】
2008090507.tif 000004
【図３】
2008090507.tif 000005
【図４】
2008090507.tif 000006
【図５】
2008090507.tif 000007
【図６】
2008090507.tif 000008
【図７】
2008090507.tif 000009
【図８】
2008090507.tif 000010
【図９】
2008090507.tif 000011
【図１０】
2008090507.tif 000012