(57)【要約】【課題】計算ノードの性能がどのように動的に変化しても、ジョブの優先度に基づいてジョブの処理を行うことができ、計算ノードの利用効率の向上を図ることができるジョブ割当装置、及びジョブ割当方法を提供する。【解決手段】ジョブを選択するジョブ管理部３と、ジョブのタスクを選択するタスク管理部４と、タスクを計算ノードに割り当てる割当手段５とを備えたジョブ割当装置である。タスクの割り当てを保留する保留手段６を備え、保留手段６は、選択したタスクが属するジョブにおいてタスクが最後の未割り当てである第１条件と、選択したタスクが属するジョブがサーバに投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件のいずれかが満たさなくなるまで、タスクの割り当てを保留する。【選択図】図１
2008226023.tif 000002
【特許請求の範囲】
【請求項１】
ジョブを選択するジョブ管理部と、前記ジョブ管理部にて選択されたジョブのタスクを選択するタスク管理部と、タスクを計算機に割り当てる割当手段とを備えたジョブ割当装置であって、
タスクの割り当てを保留する保留手段を備え、この保留手段は、前記タスク管理部にて選択したタスクが属するジョブにおいてタスクが最後の未割当状態である第１条件と、選択したタスクが属するジョブが投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件のいずれかが満たさなくなるまでタスクの割り当てを保留することを特徴とするジョブ割当装置。
【請求項２】
前記割当手段は、タスクの実行が終了するまでにタスクの割当が一巡して、同じタスクが割当の対象となる場合に、タスクを複製して別の計算機に割当てる複製部を備えることを特徴とする請求項１のジョブ割当装置。
【請求項３】
前記請求項１又は請求項２のジョブ割当装置を、グリッドコンピューティングに用いたことを特徴とするグリッドコンピューティングシステム。
【請求項４】
ジョブを選択した後、当該ジョブのタスクを選択し、その後、そのタスクを計算機に割り当てるジョブ割当方法であって、
選択したタスクが属するジョブにおいてタスクが最後の未割当状態である第１条件と、選択したタスクが属するジョブが投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件のいずれかが満たされなくなるまで、タスクの割り当てを保留することを特徴とするジョブ割当方法。
【請求項５】
選択したタスクの実行が終了するまでにタスクの割当が一巡して、同じタスクが割当の対象となる場合に、タスクを複製して別の計算機に割当てることを特徴とする請求項３のジョブ割当方法。
【請求項６】
タスクの割り当てを、ラウンドロビン方式にて行うことを特徴とする請求項３又は請求項４のジョブ割当方法。
【請求項７】
前記請求項４〜請求項６のジョブ割当方法を、グリッドコンピューティングに用いることを特徴とするジョブ割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ジョブ割当装置、及び該装置におけるジョブ割当方法に関し、コンピュータシステムにグリッドコンピューティングを適用した場合のジョブの割り当てに関するものである。
【背景技術】
【０００２】
グリッドコンピューティング（Grid computing：以下、単に「グリッド」とも称する）は、ＬＡＮ（Local Area Network）やインターネットなどのネットワーク上の様々な場所にある複数の計算機を、仮想的に１つの高性能な計算機として利用する技術である（特許文献１）。個々の計算機の性能が低くても、グリッドコンピューティングによって、複数の計算機を仮想的に統合して各計算機に協調作業を行なわせることで、高速で大量の計算をスーパーコンピュータ並みに行うことが可能となる。グリッドには、デスクトップグリッド、プロセッシンググリッド、データグリッド等種々のものが存在する。その中でも、デスクトップＰＣなどの遊休資源（余剰計算力）を利用するタイプのデスクトップグリッドは、近年の高速なインターネットの普及や高性能な計算機の低価格化に伴い、様々な分野への適用が試みられている。
【０００３】
図７は、グリッドコンピューティングのアーキテクチャである。クライアント１０１は、複数のタスクから構成されるジョブをグリッドサーバ１０２に投入する。ここでジョブとは、複数のタスクから構成されるひとまとまりの計算処理であり、タスクとは、ジョブを構成する部分処理で１つの計算機（計算ノード）で実行できる単位をいう。グリッドサーバ１０２は、ジョブを選択するジョブ管理部１０３と、タスクを選択するタスク管理部１０４とを備えている。
【０００４】
一方、デスクトップＰＣ等の計算ノード１０５、１０６、１０７が遊休状態である場合、各計算ノード１０５、１０６、１０７は、ジョブを受付可能であることをグリッドサーバ１０２に通知する。これにより、グリッドサーバ１０２は計算ノード１０５、１０６、１０７にタスクを割当てる。ここで、遊休状態とは、計算ノードのＣＰＵの処理能力に空きがある状態をいう。
【０００５】
そして、計算ノード１０５、１０６、１０７のタスク実行機能部１０８、１０９、１１０によりタスクが実行され、計算ノード１０５、１０６、１０７は、グリッドサーバ１０２にその結果を通知する。
【０００６】
このようにして、グリッドサーバ１０２に投入されたジョブは、全てのタスクが実行されると終了する。その後、グリッドサーバ１０２は、クライアント１０１にその結果を通知する。
【０００７】
このような仕組みで、通常は利用されていない計算ノードにジョブを配分し、ユーザーが意識することなく複数の機器での分散処理を可能にすることで、デスクトップグリッドが実現されている。
【０００８】
ところで、グリッドを使用するユーザーが複数存在する場合、投入されるジョブが順次発生し、そのジョブに設定されたタスクを複数の計算ノード１０５、１０６、１０７にどのような順序で割り当てるかを計画するスケジューリングがグリッドサーバ１０２にて行われる。
【０００９】
このスケジューリングアルゴリズムとしては、ジョブの投入順（発生順）にタスクを計算ノードに割り当てて処理するいわゆる先着順方式がある。すなわち、ジョブサイズや計算ノードの処理速度等の情報を必要とすることなく、ジョブの投入順にタスクを計算ノードに割り当てて処理させるスケジューリング方式である。
【００１０】
また、計算ノード全体をジョブ数の分だけ均等になるように分割し、分割したノード群とジョブを対応づけてタスクを割り当てるいわゆる空間分割法がある。これにより、計算ノードの数がジョブの数より多ければ、各ジョブは必ず１台以上の計算ノードを使用することができる。
【特許文献１】特開２００５−７０８９６号公報
【発明の開示】
【発明が解決しようとする課題】
【００１１】
前記のようなデスクトップグリッドにおいて、タスクの実行時間は、投入された計算ノードの処理速度や余剰計算力に依存することになる。余剰計算力は各計算ノードの所有者の使用状況に応じて変動するため、余剰計算力の変動を高い精度で予測することが難しく、タスク実行時間を予測することは困難である。
【００１２】
このため、複数のユーザーが同じグリッドを利用している場合、ジョブのスケジューリングに前記先着順方式や空間分割法を採用すると、後から投入されたジョブが先に投入されたジョブよりも先に完了する、いわゆる「ジョブの追い越し」が生じる可能性がある。図８は、スケジューリングアルゴリズムに先着順方式を用いたタスク状態の変移を表す図であり、図９は、スケジューリングアルゴリズムに空間分割法を用いたタスク状態の変移を表す図である。図８及び図９において、左のブロックはジョブ管理部におけるタスク表であり、中央のブロックはタスク管理部におけるタスクキュー（実行可能待ち行列）であり、右のブロックは計算ノードを示している。また、ハッチングは、実行済のタスクの状態を表し、模様なしは未割当状態のタスクを表し、ドットは割当済のタスクを表している。実行済とは、計算ノードに割当てられて処理が完了したタスクであり、未割当状態とは、計算ノードで実行できる状態にあるタスクであって、タスクの優先順位に応じてタスクキューに格納されているタスクをいう。割当済とは、優先順位に応じてタスクが実行されている状態のタスクをいう。
【００１３】
図８のステップｔ１において、先に投入されたジョブＪn（Ｊn：ｎ番目に投入されたジョブ）のタスクＡ１、Ａ２、Ａ３と、後に投入されたジョブＪn+1（Ｊn+1：ｎ＋１番目に投入されたジョブ）のタスクＢ１、Ｂ２、Ｂ３がタスクキューに投入される。ステップｔ２〜ｔ４において、ジョブＪnとジョブＪn+1のタスクが、優先度の高いものから計算ノードに割当てられて実行される。
【００１４】
この場合、先に投入されたジョブＪnのタスクＡ１、Ａ２、Ａ３が、性能が低い（処理速度が遅い）計算ノードばかりに投入される一方、後から投入されたジョブＪn+1のタスクＢ１、Ｂ２、Ｂ３が、性能が高い（処理速度が速い）計算ノードばかりに投入されると、後から投入されたジョブＪn+1が、先に投入されたジョブＪnよりも早期に終了する（ステップｔ５）。そして、ジョブＪn+1の終了に続いてジョブＪnの処理が終了する（ステップｔ７）。
【００１５】
同様に、図９においても、投入されたジョブＪn+1が、先に投入されたジョブＪnよりも早期に終了する（ステップｔ６）。そして、ジョブＪn+1の終了に続いてジョブＪnの処理が終了する（ステップｔ７）。これにより、ジョブの追い越しが生じる。
【００１６】
また、タスクの実行中に、計算機の電源を落とされる等の予測不能な事態が生じた場合、実行中のタスクの処理が中断される可能性があり、タスクの処理が完了する保証がない。
【００１７】
前記のようなジョブの追い越しや、タスクの中断が生じると、ユーザー間の公平性が担保されないおそれがある。
【００１８】
一方、ジョブに予め優先度が設定され、優先度の高いジョブＪAが発生した場合は、優先度の低いジョブＪBよりも優先度の高いジョブＪAを先に処理するように優先させることが必要な場合もある。この場合、優先度に基づいてジョブの実行順序を完全に制御するためには、図１０に示すように、優先度の高いジョブＪAの全てのタスクＡ１、Ａ２、Ａ３が完全に終了するまで、優先度の低いジョブＪBのタスクＢ１、Ｂ２を待機させる。換言すると、タスクＡ１、Ａ２、Ａ３の実行中は、タスクＢ１、Ｂ２を実行することができず、計算ノードの利用効率が悪い。
【００１９】
本発明は、上記課題に鑑みて、計算ノードの性能がどのように動的に変化しても、ジョブの優先度に基づいてジョブの処理を行うことができ、計算ノードの利用効率の向上を図ることができるジョブ割当装置、及びジョブ割当方法を提供する。
【課題を解決するための手段】
【００２０】
本発明のジョブ割当装置は、ジョブを選択するジョブ管理部と、前記ジョブ管理部にて選択されたジョブのタスクを選択するタスク管理部と、タスクを計算機に割り当てる割当手段とを備えたジョブ割当装置であって、タスクの割り当てを保留する保留手段を備え、この保留手段は、前記タスク管理部にて選択したタスクが属するジョブにおいてタスクが最後の未割当状態である第１条件と、選択したタスクが属するジョブが投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件のいずれかが満たさなくなるまでタスクの割り当てを保留するものである。ここで、未割当状態とは、計算機で実行できる状態にあるタスクの状態をいう。
【００２１】
本発明のジョブ割当装置は、優先度の低いジョブの最後のタスクの計算機への割当を、保留手段にて保留することができる。これにより、優先度の高いジョブから順に処理を行うことができる。また、優先度の低いジョブであっても、保留状態のタスク以外のタスクは、優先度の高いジョブのタスクと並行して実行することができる。ここで、「タスクが最後の未割当状態である」とは、当該タスクが単一の場合と複数の場合の両方を含むものをいう。
【００２２】
割当手段は、タスクの実行が終了するまでにタスクの割当が一巡して、同じタスクが割当の対象となる場合に、タスクを複製して別の計算機に割り当てる複製部を備えることができる。これにより、性能の劣る計算機にタスクが割り当てられた場合には、タスク複製部によりタスクを複製して、この複製タスクを別の計算機に割り当てることができる。
【００２３】
また、前記ジョブ割当装置を、グリッドコンピューティングに用いることができる。
【００２４】
本発明のジョブ割当方法は、ジョブを選択した後、ジョブのタスクを選択し、その後、当該タスクを計算機に割り当てるジョブ割当方法であって、選択したタスクが属するジョブにおいてタスクが最後の未割当状態である第１条件と、選択したタスクが属するジョブが投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件のいずれかが満たされなくなるまで、タスクの割り当てを保留するものである。
【００２５】
この場合、選択したタスクの実行が終了するまでにタスクの割当が一巡して、同じタスクが割当の対象となる場合に、タスクを複製して別の計算機に割当てることができる。
【００２６】
前記タスクの割当をラウンドロビン方式にて行うことができる。ラウンドロビン方式とは、複数のタスクについて、タスク毎に設定された順序でタスクを計算機に順番に割当てる割当て方式をいう。
【００２７】
また、前記ジョブ割当方法を、グリッドコンピューティングに用いることができる。
【発明の効果】
【００２８】
本発明のジョブ割当装置及びジョブ割当方法は、ジョブのタスクが最後の未割り当てタスクであって、優先度の高いジョブが計算中である場合には、タスクの計算機への割り当てを保留することができる。このため、ジョブの優先度のみに従って順次処理結果を得ることができる。すなわち、プロセッサの性能がどのように動的に変化しても、ジョブの優先度に基づいて確実にジョブの処理を行うことができ、ユーザー間の公平性を担保することができる。また、優先度の低いジョブであっても、保留中のタスク以外のタスクは、優先度の高いジョブのタスクと並行して実行することができるため、効率良く処理することが可能となる。
【００２９】
性能の劣るプロセッサにタスクが割り当てられた場合には、タスク複製部によりタスクを複製して、この複製タスクを別のプロセッサに割り当てることができる。このため、ジョブの処理時間を短縮することができて、一層効率の良い処理が可能となる。
【００３０】
前記タスクの割当をラウンドロビン方式にて行うことができるため、優先度の低いタスクであっても公平に計算機に割当てられることとなって、ユーザー間の公平性を一層担保することができる。
【発明を実施するための最良の形態】
【００３１】
以下本発明の実施の形態を図１〜図６に基づいて説明する。
【００３２】
本発明のジョブ割当装置は、先に投入されたジョブが、後に投入されたジョブよりも先に完了する「ジョブの追い越し」の発生を防止することができるスケジューリングアルゴリズムを構成することができる装置である。このため、本発明の主構成は、選択したタスクが属するジョブにおいてタスクが最後の未割り当てである第１条件と、選択したタスクが属するジョブがサーバに投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件のいずれかが満たさなくなるまで、タスクの割り当てを保留するものである。
【００３３】
ジョブ割当装置は、図１に示すように、グリッドサーバ２と、タスクの処理を行う複数の計算機（計算ノード）９、１０、１１とを備えている。グリッドサーバ２は、ジョブの選択を行うジョブ管理部３と、タスクの選択を行うタスク管理部４と、タスクを計算ノード９、１０、１１に割り当てる割当手段５と、タスクの割り当てを保留する保留手段６とを備える。
【００３４】
ジョブ管理部３は、投入されたジョブの優先度を検知して記憶するとともに、ジョブの優先度に基づいてジョブの選択を行うものである。優先度とは、ジョブの投入順に基づいて定められたり、ジョブに予め設定されていたりするものである。ジョブ管理部３は、この優先度に基づいてジョブの処理順序を決定して、タスク管理部４にジョブの処理を転送する。すなわち、タスクの優先順位に応じてタスク管理部４の実行可能待ち行列（タスクキュー）にタスクを格納する。
【００３５】
割当手段５は、タスクキューにある未割当状態のタスクを計算ノード９、１０、１１に割当てて、タスクの状態を割当済とするものである。ここで、未割当状態とは、計算ノードで実行できる状態にあるタスクであって、タスクの優先順位に応じて実行可能待ち行列（タスクキュー）に格納されているタスクをいう。割当済とは、優先順位に応じてタスクが実行されている状態のタスクをいう。
【００３６】
保留手段６は、選択したタスクが属するジョブにおいて、タスクが最後の未割当状態である第１条件と、選択したタスクが属するジョブがグリッドサーバ２に投入された時点で優先度の高いジョブが計算中である第２条件とを同時に満たす場合に、その条件もいずれかが満たさなくなるまで、タスクの割り当てを保留するものである。すなわち、ジョブの優先度に基づいて、優先度の低いジョブがグリッドサーバ２に投入されたときに優先度の高いジョブがグリッドで計算中である場合には、当該ジョブの最後のタスク割り当ての保留を行う。そして、優先度の高いジョブの実行状況を監視して、この優先度の高いジョブの実行が終了したことを検知した後に、保留タスクの保留解除を行って、タスクを未割当状態とすることを決定する。
【００３７】
これにより、ジョブの優先度が高い順にジョブの処理を行うことができる。また、優先度の低いジョブであっても、保留状態のタスク以外のタスクは、優先度の高いジョブのタスクと並行して実行することができる。
【００３８】
次に、このジョブ割当装置を用いたジョブ割当方法について説明する。図２は、ジョブ割当方法の手順を示すフローチャートであり、図３は、時間毎のタスクの状態変移を示す説明図である。図３において、左のブロックは、ジョブ管理部３におけるタスク表であり、中央のブロックは、タスク管理部４におけるタスクキューであり、右のブロックは、計算ノード９、１０、１１である。また、ハッチングは、実行済のタスクの状態を表し、模様なしは未割当状態のタスクを表し、ドットは割当済のタスクを表し、網掛けは保留状態のタスクを表している。
【００３９】
本実施形態では、例えば、２つのジョブが投入される状態について説明する。まず、クライアント１は、複数のタスクＡ１、Ａ２、Ａ３から構成されるジョブＪｎ（Ｊn：ｎ番目に投入されたジョブ）を、グリッドサーバ２に投入する。この場合、ジョブ管理部３により、ジョブの投入順に基づいて優先度が検出される。
【００４０】
一方、デスクトップＰＣ等の計算ノード９、１０、１１が遊休状態である場合、各計算ノード９、１０、１１は、ジョブを受付可能であることをグリッドサーバ２のジョブ管理部３に通知する。これにより、ジョブ管理部３は、各タスクの優先度に基づいて、ジョブＪnの全てのタスクＡ１、Ａ２、Ａ３を、タスク管理部４のタスクキューに投入する。ここで、遊休状態とは、計算ノードのＣＰＵの処理能力に空きがある状態をいう。
【００４１】
また、別のクライアント１によりタスクＢ１、Ｂ２を備えたジョブＪn+1（Ｊn+1：ｎ＋１番目に投入されたジョブ）がグリッドサーバ２に投入される。この場合も、前記ジョブＪnと同様、ジョブ管理部３により、ジョブの投入順序に基づいて優先度が検出される。これにより、後に投入されたジョブＪn+1は、先に投入されたジョブＪnと比較して優先度が劣ることになる。
【００４２】
この場合も、ジョブＪn+1の全てのタスクＢ１、Ｂ２を、タスク管理部４のタスクキューに投入する。すなわち、図３に示すように、グリッドサーバ２に投入された全てのジョブの全てのタスクＡ１、Ａ２、Ａ３、Ｂ１、Ｂ２がタスク管理部４のタスクキューに投入されることになる（ステップＳ１、ｔ１）。
【００４３】
そして、タスク管理部４によりタスクを選択して、割当手段４がタスクを計算ノード９、１０、１１に転送し、タスク実行機能部１２、１３、１４によりタスクＡ１が実行される。
【００４４】
ここで、優先度の高いジョブＪnのタスクＡ１がグリッドで計算中である場合、優先度の低いジョブＪn+1の最後のタスクＢ２を、保留手段６にて保留状態とする（ステップＳ２、ｔ２）。すなわち、この保留タスクＢ２は、タスクキューに投入されたものであっても、計算ノード９、１０、１１への割当を行わない。
【００４５】
次に、割当手段５により、未割当の状態のタスクを実行可能な計算ノードに割当てて、タスクの状態を割当済にする（ステップＳ３、ｔ３〜ｔ６）。つまり、ジョブＪnの全てのタスクＡ１、Ａ２、Ａ３の実行を行うとともに、ジョブＪn+1の保留タスクＢ２以外のタスクＢ１の実行を行う。この場合、タスクの割当はラウンドロビン方式にて行うのが望ましい。
【００４６】
また、タスクの割当中にパソコンの電源がＯＦＦになる等、計算ノードへの割当中止が生じた場合（ステップＳ５）、当該計算ノードで処理されていた中止タスクの状態を未割当とする（ステップＳ６）。そして、再びステップＳ３に戻ってタスクを実行可能な計算ノードに割当てて、タスクの状態を割当済とする。
【００４７】
タスクの実行中に割当中止がなければ、ジョブ管理部３は、全てのジョブの処理が終了したか否かを判断して（ステップＳ７）、全てのジョブが完了している場合は終了する。一方、全てのジョブの処理が完了していない場合、保留手段６は、優先ジョブＪnの実行状況を監視して（ステップＳ８）、保留タスクＢ２の保留継続又は保留解除の判断を行う。すなわち、優先ジョブＪnの処理が完了していない場合は、保留手段６は保留タスクＢ２の保留を継続する。そして、再びステップＳ３に戻り、ジョブＪnの全てのタスクＡ１、Ａ２、Ａ３、及びジョブＪn+1の保留状態のタスクＢ２以外のタスクＢ１を実行可能な計算ノードに割当てる。
【００４８】
保留手段６により優先ジョブＪnの実行状況を監視した結果（ステップＳ８）、ジョブＪnの実行が終了したことを検知すると、保留手段６は、保留タスクＢ２の保留解除を行い、このタスクＢ２を未割当状態とする（ステップＳ９、ｔ７）。その後、ステップＳ３に戻って、保留状態であったタスクＢ２を計算ノードに割当てて実行する（ｔ８）。そして、タスクＢ２の処理が完了することにより、ジョブＪn+1が完了する（ｔ９）。
【００４９】
このように、本発明のジョブ割当装置及びジョブ割当方法によれば、ジョブのタスクが最後の未割り当てタスクであって、優先度の高いジョブが計算中である場合には、タスクの計算ノードへの割り当てを保留することができる。このため、ジョブの優先度のみに従って順次処理結果を得ることができる。すなわち、プロセッサの性能がどのように動的に変化しても、ジョブの優先度に基づいて確実にジョブの処理を行うことができる。また、優先度の低いジョブであっても、保留状態のタスク以外のタスクは、優先度の高いジョブのタスクと並行して実行することができるため、効率良く処理することが可能となる。
【００５０】
前記タスクの割当をラウンドロビン方式にて行うことができるため、それぞれのタスクは公平に計算ノードに割当てられることとなって、ユーザー間の公平性を一層担保することができる。
【００５１】
次に、本発明のジョブ割当装置の他の実施形態としては、割当手段５に、タスクを複製して別の計算ノードに割当てる複製部を設けることができる。例えば、性能の劣る計算ノードにサイズの大きいタスクが割り当てられた場合に、タスクが実行終了するまでにタスクの割当が一巡して、同じタスクが割当の対象となる場合がある。このため、タスク複製部によりタスクを複製して、別の計算ノードに割り当てる。すなわち、元のタスクの処理と、複製タスクの処理を並行して行う。
【００５２】
このように、本発明の他の実施形態のジョブ割当装置及びジョブ割当方法によれば、性能の劣るプロセッサにサイズの大きいタスクが割り当てられた場合には、タスク複製手段によりタスクを複製して、この複製タスクを別のプロセッサに割り当てることができる。このため、ジョブの処理時間を短縮することができて、効率のよい処理が可能となる。
【００５３】
以上、本発明の実施形態につき説明したが、本発明は前記実施形態に限定されることなく種々の変形が可能であって、例えば、タスクの割当方式としては、ラウンドロビン方式に限られることなく、ＦＩＦＯ（First In First Out）、ＳＪＦ（Short Job First）等種々の割当方式を採用することができる。要は、優先度の低いタスクにも計算ノードへの割当機会が保証されていれば、いずれの割当方式を用いてもよい。また、グリッドサーバに投入されるジョブの数としても、２つに限られるものではない。さらには、本実施形態では、優先度はジョブの投入順に基づいて定められるものであったが、予め優先度が設定されたものであってもよい。グリッドとしては、デスクトップグリッドに限られるものではなく、プロセッシンググリッド、データグリッド等種々のものを採用することができる。
【００５４】
次に、前記ジョブスケジューリングシステムのシミュレーション結果について説明する。シミュレーションに用いたスケジューリングアルゴリズムは、本発明のジョブスケジューリングシステムと、従来の方法である先着順、及び空間分割法である。
【００５５】
シミュレーション条件を表１に示す。企業や研究機関のＰＣが３年間使用されるものと仮定し、デスクトップグリッド中のＰＣのピーク性能の比率を、１、２、４とした。ピーク性能とは、各々のプロセッサが何のロスも生じさせずに計算し、その上、プロセッサ間には一切の通信も行わない場合の計算機全体の性能をいう。ＰＣ１台について、プロセッサは１台であるとし、各プロセッサは負荷が低く余剰計算力が大きい定常状態と、負荷が高く余剰計算力が小さい高負荷状態の２つの状態を一定の確率で遷移する。各状態では、プロセッサ毎に決められた範囲内でランダムに性能を決定する。使用するＰＣは１２８台とし、３２個のジョブを等間隔で投入する。ジョブはそれぞれサイズの異なる１２８個のタスクから構成され、ジョブは全て同じタスク構成となっている。そして、各アルゴリズム毎に、ジョブの投入間隔を５０、１００、２００の３段階に変化させてシミュレーションを行った。その結果をそれぞれ表２、表３、表４に示す。
【００５６】
【表１】
2008226023.tif 000003
【００５７】
【表２】
2008226023.tif 000004
【００５８】
【表３】
2008226023.tif 000005
【００５９】
【表４】
2008226023.tif 000006
【００６０】
表２〜表４に示すように、ジョブの投入間隔が５０、１００、２００のいずれにおいても、本発明のジョブ割当装置を用いたものがジョブを実行するまでの待機時間が短いことがわかる。
【００６１】
図４〜図６は、前記条件のうち、ジョブの投入間隔を５０としてシミュレーションを行った結果を表すグラフである。図４は本発明のスケジューリングアルゴリズムを用いたシミュレーション結果であり、図５はスケジューリングアルゴリズムに先着順、図６はスケジューリングアルゴリズムに空間分割法を用いた結果である。図４〜図６において、ハッチングはジョブを実行するまでの待機時間であり、模様なしはラストタスク以外のタスクの実行時間であり、黒色はラストタスクブロック時間であり、ドットはラストタスク実行時間を表す。ここで、ラストタスクブロック時間とは、ジョブの最後の未割り当てタスクの割り当てが保留され続けた時間をいう。
【００６２】
図４のグラフからわかるように、本発明のスケジューリングアルゴリズムは、投入されたジョブの順に処理が終了している。また、ジョブの処理が開始するまでの待機時間が最も短く、その分散値も先着順や空間分割法と比較すると小さいものとなっている。一方、先着順は図５のグラフの範囲５０に示すように、先に投入されたジョブが、後に投入されたジョブよりも遅く終了する「ジョブの追い越し」が生じている。また、待機時間も長時間に及ぶものである。さらには、空間分割法は図６に示すように、ジョブの投入の先後を問わず、ジョブの終了順序が予測できないものとなっている。また、待機時間も各ジョブによってばらつきが生じている。
【００６３】
以上より、本発明によれば、プロセッサの性能がどのように動的に変化しても、ジョブの追い越しの発生を防止することができるものである。
【図面の簡単な説明】
【００６４】
【図１】本発明のジョブ割当装置を示すブロック図である。
【図２】本発明のジョブ割当方法を示すフローチャートである。
【図３】本発明のジョブ割当装置のタスク変移状態を示す説明図である。
【図４】本発明のジョブ割当装置のアルゴリズムのシミュレーション結果を示すグラフである。
【図５】ジョブ割当装置の従来のアルゴリズムである先着順方式でのシミュレーション結果を示すグラフである。
【図６】ジョブ割当装置の従来の他のアルゴリズムである空間分割法でのシミュレーション結果を示すグラフである。
【図７】従来のジョブ割当装置を示すブロック図である。
【図８】従来のジョブ割当装置のタスク変移状態を示す説明図である。
【図９】従来のジョブ割当装置の他のタスク変移状態を示す説明図である。
【図１０】従来のジョブ割当装置の別のタスク変移状態を示す説明図である。
【符号の説明】
【００６５】
３      ジョブ管理部
４      タスク管理部
５      割当手段
６      保留手段
【図１】
2008226023.tif 000007
【図２】
2008226023.tif 000008
【図３】
2008226023.tif 000009
【図４】
2008226023.tif 000010
【図５】
2008226023.tif 000011
【図６】
2008226023.tif 000012
【図７】
2008226023.tif 000013
【図８】
2008226023.tif 000014
【図９】
2008226023.tif 000015
【図１０】
2008226023.tif 000016