(57)【特許請求の範囲】
【請求項１】
データ処理を実行する複数のノードと、前記複数のノードと接続された中央管理装置であって当該データ処理を当該ノードの各々に振り分ける中央管理装置とから構成される分散データ処理システムにおいて、
前記中央管理装置は、
前記ノードの各々に振り分けられたデータ処理を識別するためのデータ処理識別情報、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理が振り分けられたノードを示す振り分け先ノード情報を対応づけて格納する振り分け情報格納手段と、
前記ノードに振り分けられていないデータ処理の対象となるデータおよび当該データ処理の目標終了時刻を示す目標終了時刻情報を入力する入力手段と、
前記振り分け情報格納手段に格納されている振り分け先ノード情報に基づいて、前記複数のノードの中にデータ処理が振り分けられていないノードが存在するかを判定する判定手段と、
前記データ処理が振り分けられていないノードが存在しないと判定された場合、前記ノード毎に、当該ノードを示す振り分け先ノード情報に対応づけて前記振り分け情報格納手段に格納されている目標終了時刻情報によって示される目標終了時刻のうち最も遅い目標終了時刻を抽出する抽出手段と、
前記ノード毎に抽出された目標終了時刻の中で最も早い目標終了時刻が抽出されたノードを特定する特定手段と、
前記入力されたデータおよび目標終了時刻情報を前記特定されたノードに送信し、当該入力されたデータに対するデータ処理を前記特定されたノードに振り分ける振り分け処理手段と、
前記入力されたデータに対するデータ処理を識別するためのデータ処理識別情報、前記入力された目標終了時刻情報および当該データ処理が振り分けられたノードを示す振り分け先ノード情報を対応づけて前記振り分け情報格納手段に格納する格納処理手段と
を含み、
前記入力されたデータに対するデータ処理が振り分けられたノードは、前記送信された目標終了時刻情報によって示される目標終了時刻に基づいて、前記送信されたデータに対するデータ処理を実行する
ことを特徴とする分散データ処理システム。
【請求項２】
前記入力手段は、前記入力されたデータに対するデータ処理の優先レベルを示す優先レベル情報を更に入力し、
前記振り分け処理手段は、前記入力された優先レベル情報を前記特定されたノードに更に送信し、
前記入力されたデータに対するデータ処理が振り分けられたノードは、
当該ノードで実行されているデータ処理を識別するためのデータ処理識別情報、当該データ処理の優先レベルを示す優先レベル情報、当該データ処理の目標終了時刻を示す目標終了時刻情報、当該データ処理の推定終了時刻を示す推定終了時刻情報および当該データ処理における単位処理量を対応づけて格納する実行情報格納手段と、
前記送信されたデータに対するデータ処理の一部を実行するデータ処理実行手段と、
前記データ処理実行手段によるデータ処理の一部の実行結果に基づいて前記送信されたデータに対するデータ処理における単位処理量を算出し、前記送信されたデータ、当該算出された単位処理量および前記実行情報格納手段に格納されている推定終了時刻情報によって示される推定終了時刻に基づいて前記送信されたデータに対するデータ処理の推定終了時刻を算出する第１の算出手段と、
前記送信された目標終了時刻情報によって示される目標終了時刻および前記第１の算出手段によって算出された推定終了時刻に基づいて、前記送信されたデータに対するデータ処理が当該目標終了時刻以前に終了するかを判定する第１の判定手段と、
前記送信されたデータに対するデータ処理が目標終了時刻以前に終了しないと前記第１の判定手段によって判定された場合、前記送信された優先レベル情報によって示される優先レベルおよび前記実行情報格納手段に格納されている優先レベル情報によって示される優先レベルに基づいて、前記送信されたデータに対するデータ処理および前記実行情報格納手段に格納されているデータ処理識別情報によって識別されるデータ処理が実行される順番を入れ替える入れ替え手段と、
前記順番が入れ替えられた場合、前記実行情報格納手段に格納されているデータ処理識別情報によって識別されるデータ処理を停止し、前記送信されたデータ、前記第１の算出手段によって算出された単位処理量および当該データ処理が停止された時刻に基づいて前記送信されたデータに対するデータ処理の推定終了時刻を算出する第２の算出手段と、
前記送信された目標終了時刻情報によって示される目標終了時刻および前記第２の算出手段によって算出された推定終了時刻に基づいて、前記送信されたデータに対するデータ処理が当該目標終了時刻以前に終了するかを判定する第２の判定手段と、
前記送信されたデータに対するデータ処理が目標終了時刻以前に終了しないと前記第２の判定手段によって判定された場合、前記送信された目標終了時刻情報によって示される目標終了時刻、前記第１の算出手段によって算出された単位処理量および前記第２の算出手段によって算出された推定終了時刻に基づいて、前記送信されたデータを、当該データに対するデータ処理において当該目標終了時刻までに処理できる前方のデータと当該目標終了時刻までに処理できない後方のデータとに分割する第１の分割手段と、
前記第１の分割手段によって分割された後方のデータを前記中央管理装置に返却する第１の返却手段と、
前記実行情報格納手段に格納されているデータ処理識別情報によって識別されるデータ処理の対象となるデータ、当該データ処理識別情報に対応づけて前記実行情報格納手段に格納されている単位処理量および前記第２の算出手段によって算出された推定終了時刻に基づいて前記実行情報格納手段に格納されているデータ処理識別情報によって識別されるデータ処理の推定終了時刻を算出する第３の算出手段と、
前記実行情報格納されている目標終了時刻情報によって示される目標終了時刻および前記第３の算出手段によって算出された推定終了時刻に基づいて、前記実行情報格納手段に格納されているデータ処理識別情報によって識別されるデータ処理が当該目標終了時刻以前に終了するかを判定する第３の判定手段と、
前記実行情報格納手段に格納されているデータ処理識別情報によって識別されるデータ処理が目標終了時刻以前に終了しないと判定された場合、当該データ処理識別情報に対応づけて前記実行情報格納手段に格納されている目標終了時刻情報によって示される目標終了時刻、単位処理量および前記第３の算出手段によって算出された推定終了時刻に基づいて、当該データ処理識別情報によって識別されるデータ処理の対象となるデータを、当該データ処理において当該目標終了時刻までに処理できる前方のデータと当該目標終了時刻までに処理できない後方のデータとに分割する第２の分割手段と、
前記第２の分割手段によって分割された後方のデータを前記中央管理装置に返却する第２の返却手段と
を含み、
前記データ処理実行手段は、前記第１の分割手段によって分割された前方のデータに対するデータ処理、前記第２の分割手段によって分割された前方のデータに対するデータ処理の順番で、当該各データ処理を実行する
ことを特徴とする請求項１記載の分散データ処理システム。
【請求項３】
前記振り分け処理手段は、前記第１および第２の返却手段によってデータが返却された場合、当該第１および第２の返却手段によって返却されたデータに対するデータ処理を前記特定されたノードに更に振り分けることを特徴とする請求項２記載の分散データ処理システム。
【請求項４】
前記中央管理装置は、前記入力されたデータに対するデータ処理が振り分けられたノードに含まれるデータ処理実行手段によって実行された前記第１の分割手段によって分割された前方のデータに対するデータ処理の結果および前記第１の返却手段によって返却されたデータに対するデータ処理が振り分けられたノードに含まれるデータ処理実行手段によって実行された当該データ処理の結果を集約して出力し、前記入力されたデータに対するデータ処理が振り分けられたノードに含まれるデータ処理実行手段によって実行された前記第２の分割手段によって分割された前方のデータに対するデータ処理の結果および前記第２の返却手段によって返却されたデータに対するデータ処理が振り分けられたノードに含まれるデータ処理実行手段によって実行された当該データ処理の結果を集約して出力する出力手段を更に含むことを特徴とする請求項３記載の分散データ処理システム。
【請求項５】
データ処理を実行する複数のノードと接続され、当該データ処理を当該ノードの各々に振り分ける中央管理装置において、
前記ノードの各々に振り分けられたデータ処理を識別するためのデータ処理識別情報、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理が振り分けられたノードを示す振り分け先ノード情報を対応づけて格納する振り分け情報格納手段と、
前記ノードに振り分けられていないデータ処理の対象となるデータおよび当該データ処理の目標終了時刻を示す目標終了時刻情報を入力する入力手段と、
前記振り分け情報格納手段に格納されている振り分け先ノード情報に基づいて、前記複数のノードの中にデータ処理が振り分けられていないノードが存在するかを判定する判定手段と、
前記データ処理が振り分けられていないノードが存在しないと判定された場合、前記ノード毎に、当該ノードを示す振り分け先ノード情報に対応づけて前期振り分け情報格納手段に格納されている目標終了時刻情報によって示される目標終了時刻のうち最も遅い目標終了時刻を抽出する抽出手段と、
前記ノード毎に抽出された目標終了時刻の中で最も早い目標終了時刻が抽出されたノードを特定する特定手段と、
前記入力されたデータおよび目標終了時刻情報を前記特定されたノードに送信し、当該入力されたデータに対するデータ処理を前記特定されたノードに振り分ける振り分け処理手段と、
前記入力されたデータに対するデータ処理を識別するためのデータ処理識別情報、前記入力された目標終了時刻情報および当該データ処理が振り分けられたノードを示す振り分け先ノード情報を対応づけて前記振り分け情報格納手段に格納する格納処理手段と
を具備することを特徴とする中央管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、複数のノードで分散してデータ処理を実行する分散データ処理システムおよび中央管理装置に関する。
【背景技術】
【０００２】
近年、複数のノード（計算機）で分散してデータ処理を実行する分散データ処理システムが知られている。なお、データ処理とは、例えば対応するプログラムが実行されることによって処理される１グループのデータ群で構成される処理単位である。
【０００３】
分散データ処理システムは、例えばデータ処理を実行する複数のノードと当該複数のノードを統括する中央管理装置とから構成される。
【０００４】
ところで、このような分散データ処理システムにおいて分散して実行されるデータ処理（分散データ処理）を目標終了時刻までに完了させるためには、当該分散データ処理システムにおいてデータ処理を適切なノードに振り分ける（割り振る）必要がある。
【０００５】
この場合、分散データ処理システムを構成する中央管理装置は、各ノードの性能および負荷状況を逐次把握し、当該各ノードの性能、負荷状況およびデータ処理の目標終了時刻に基づいて、当該データ処理をノードに振り分ける処理（スケジューリング）を行う。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−１２３２０５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、例えば分散データ処理システムを構成する複数のノードに既にデータ処理が振り分けられている状態で新たなデータ処理をノードに振り分けるような場合、中央管理装置は、当該複数のノードの全ての性能をチェックし、全体の最新状況を把握して全体のスケジューリングをし直さなければならない。この場合、複数のノード全体のスケジューリングに伴う通信処理のコストがかかる。
【０００８】
そこで、本発明が解決しようとする課題は、複数のノードの性能等を把握することなく、適切なスケジューリングを行うことが可能な分散データ処理システムおよび中央管理装置を提供することにある。
【課題を解決するための手段】
【０００９】
実施形態によれば、データ処理を実行する複数のノードと、前記複数のノードと接続された中央管理装置であって当該データ処理を当該ノードの各々に振り分ける中央管理装置とから構成される分散データ処理システムが提供される。
【００１０】
実施形態に係る分散データ処理システムを構成する中央管理装置は、振り分け情報格納手段と、入力手段と、判定手段と、抽出手段と、特定手段と、振り分け処理手段と、格納処理手段とを含む。
【００１１】
振り分け情報格納手段は、前記ノードの各々に振り分けられたデータ処理を識別するためのデータ処理識別情報、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理が振り分けられたノードを示す振り分け先ノード情報を対応づけて格納する。
【００１２】
入力手段は、前記ノードに振り分けられていないデータ処理の対象となるデータおよび当該データ処理の目標終了時刻を示す目標終了時刻情報を入力する。
【００１３】
判定手段は、前記振り分け情報格納手段に格納されている振り分け先ノード情報に基づいて、前記複数のノードの中にデータ処理が振り分けられていないノードが存在するかを判定する。
【００１４】
抽出手段は、前記データ処理が振り分けられていないノードが存在しないと判定された場合、前記ノード毎に、当該ノードを示す振り分け先ノード情報に対応づけて前記振り分け情報格納手段に格納されている目標終了時刻情報によって示される目標終了時刻のうち最も遅い目標終了時刻を抽出する。
【００１５】
特定手段は、前記ノード毎に抽出された目標終了時刻の中で最も早い目標終了時刻が抽出されたノードを特定する。
【００１６】
振り分け処理手段は、前記入力されたデータおよび目標終了時刻情報を前記特定されたノードに送信し、当該入力されたデータに対するデータ処理を前記特定されたノードに振り分ける。
【００１７】
格納処理手段は、前記入力されたデータに対するデータ処理を識別するためのデータ処理識別情報、前記入力された目標終了時刻情報および当該データ処理が振り分けられたノードを示す振り分け先ノード情報を対応づけて前記振り分け情報格納手段に格納する。
【００１８】
実施形態に係る分散データ処理システムを構成する前記入力されたデータに対するデータ処理が振り分けられたノードは、前記送信された目標終了時刻情報によって示される目標終了時刻に基づいて、前記送信されたデータに対するデータ処理を実行する。
【図面の簡単な説明】
【００１９】
【図１】実施形態に係る分散データ処理システムの主として機能構成を示すブロック図。
【図２】図１に示す中央管理装置１０に含まれる振り分け情報格納部１２のデータ構造の一例を示す図。
【図３】図１に示す中央管理装置１０に含まれる処理結果格納部１６のデータ構造の一例を示す図。
【図４】図１に示すノード２０に含まれる実行情報格納部２６のデータ構造の一例を示す図。
【図５】データ処理を実行している複数のノード２０の状態を説明するための図。
【図６】図５に示す状態においてノード１に対してデータ処理４が新たに振り分けられた場合の分散データ処理システムの動作について説明するための図。
【図７】本実施形態に係る分散データ処理システムにおいて実行される第１の処理の処理手順を示すフローチャート。
【図８】分散データ処理システムにおいて第１の処理が実行される前の中央管理装置１０に含まれる振り分け情報格納部１２のデータ構造の一例を示す図。
【図９】分散データ処理システムにおいて第１の処理が実行された後の振り分け情報格納部１２のデータ構造の一例を示す図。
【図１０】本実施形態に係る分散データ処理システムにおいて実行される第２の処理の処理手順を示すフローチャート。
【図１１】本実施形態に係る分散データ処理システムにおいて実行される第２の処理の処理手順を示すフローチャート。
【図１２】本実施形態に係る分散データ処理システムにおいて実行される第２の処理の処理手順を示すフローチャート。
【図１３】本実施形態に係る分散データ処理システムにおいて実行される第２の処理の処理手順を示すフローチャート。
【図１４】分散データ処理システムにおいて第２の処理が実行される前の対象ノード２０に含まれる実行情報格納部２６のデータ構造の一例を示す図。
【図１５】第２の処理において更新された実行情報格納部２６のデータ構造の一例を示す図。
【図１６】本実施形態に係る分散データ処理システムにおいて実行される第３の処理の処理手順を示すフローチャート。
【図１７】本実施形態に係る分散データ処理システムにおいて実行される第４の処理の処理手順を示すフローチャート。
【図１８】本実施形態に係る分散データ処理システムにおいて実行される第５の処理の処理手順を示すフローチャート。
【図１９】分散データ処理システムにおいて第５の処理が実行される際の中央管理装置１０に含まれる処理結果格納部１６のデータ構造の一例を示す図。
【図２０】第５の処理においてデータ処理ＩＤおよびデータ処理結果が格納された後の処理結果格納部１６のデータ構造を示す図。
【図２１】対象データ処理および親データ処理の処理状況が更新された後の振り分け情報格納部１２のデータ構造の一例を示す図。
【発明を実施するための形態】
【００２０】
以下、図面を参照して、実施形態について説明する。
【００２１】
まず、図１を参照して、本実施形態に係る分散データ処理システムについて説明する。本実施形態に係る分散データ処理システムは、例えばクラウドコンピューティングのような計算機環境においてデータ処理を分散させる際に適用されるものであり、複数の計算機資源で並列にデータ処理を実行させる場合を想定している。なお、データ処理は、例えば対応するプログラムが実行されることによって処理される処理単位である。
【００２２】
図１は、本実施形態に係る分散データ処理システムの主として機能構成を示すブロック図である。分散データ処理システムは、中央管理装置１０および複数のノード２０から構成される。中央管理装置１０は、例えばネットワークを介して複数のノード２０と接続されている。なお、図１においては、便宜的に、１つのノード２０のみが示されている。
【００２３】
中央管理装置１０は、データ処理を各ノード２０に振り分ける（割り振る）機能を有する。中央管理装置１０は、ヘッダ情報付与部１１、振り分け情報格納部１２、振り分け判定部１３、振り分け処理部１４、中央結果処理部１５および処理結果格納部１６を含む。
【００２４】
ヘッダ情報付与部１１は、ノード２０に振り分けられていないデータ処理（振り分けの対象となるデータ処理）の対象となるデータ（当該データ処理によって処理されるデータ）を入力する。
【００２５】
ヘッダ情報付与部１１は、入力されたデータに対するデータ処理（当該データに対して実行されるデータ処理）の目標終了時刻を示す目標終了時刻情報および当該データ処理（当該データの処理作業）の優先レベル（優先度）を示す優先レベル情報を入力する。
【００２６】
ヘッダ情報付与部１１は、入力されたデータに対して、当該データに対するデータ処理を識別するためのデータ処理ＩＤ（データ処理識別情報）、入力された目標終了時刻情報および優先レベル情報から構成されたヘッダ情報を付与する。なお、ヘッダ情報を構成するデータ処理ＩＤは、データが入力された際にヘッダ情報付与部１１によって発行される。
【００２７】
振り分け情報格納部１２には、データ処理の振り分けに関する情報が格納される。振り分け情報格納部１２には、例えばデータ処理ＩＤ、優先レベル情報、目標終了時刻情報および振り分け先ノード情報等が対応づけて格納される。
【００２８】
データ処理ＩＤは、ノード２０に振り分けられたデータ処理を識別するための識別子である。優先レベル情報は、データ処理ＩＤによって識別されるデータ処理の優先レベルを示す。目標終了時刻情報は、データ処理ＩＤによって識別されるデータ処理の目標終了時刻を示す。振り分け先ノード情報は、データ処理ＩＤによって識別されるデータ処理が振り分けられたノード２０（つまり、当該データ処理の振り分け先となるノード２０）を示す。なお、振り分け情報格納部１２のデータ構造の詳細については後述する。
【００２９】
振り分け判定部１３は、振り分け情報格納部１２を参照して、ヘッダ情報付与部１１によってヘッダ情報が付与されたデータ（ヘッダ情報付与部１１によって入力されたデータ）に対するデータ処理が振り分けられるノード２０を特定（振り分け判定）する。
【００３０】
また、振り分け判定部１３は、後述するようにノード２０からデータが返却された場合には、振り分け情報格納部１２を参照して、当該データに対するデータ処理が振り分けられるノード２０を特定する。
【００３１】
振り分け処理部１４は、振り分け判定部１３によって特定されたノード２０に対してデータ処理を振り分ける。この場合、振り分け処理部１４は、ヘッダ情報付与部１１によってヘッダ情報が付与されたデータを、振り分け判定部１３によって特定されたノード２０に対して送信する。
【００３２】
中央結果処理部１５は、各ノード２０において実行されたデータ処理の結果を受信する（受け取る）。中央結果処理部１５は、受信されたデータ処理の結果に基づいて、振り分け情報格納部１２（の内容）を更新する。中央結果処理部１５は、受信されたデータ処理の結果を処理結果格納部１６に格納する。また、中央結果処理部１５は、振り分け情報格納部１２および処理結果格納部１６を参照して、データ処理の最終結果を例えば中央管理装置１０の外部に出力する。
【００３３】
処理結果格納部１６には、データ処理の結果が格納される。処理結果格納部１６には、例えばデータ処理を識別するためのデータ処理ＩＤおよび当該データ処理の結果が対応づけて格納される。
【００３４】
ノード２０は、中央管理装置１０によって当該ノード２０に対して振り分けられたデータ処理を実行する機能を有する。上記したように、分散データ処理システムにおいては、複数のノード２０が存在する。これらの各ノード２０は、ノード管理部２１、ノードデータ格納部２２、データ処理実行部２３、データ処理推定部２４、データ処理分割部２５および実行情報格納部２６を含む。なお、これらの各部２１〜２６の説明において、当該各部２１〜２６を含むノード２０を、便宜的に、自ノード２０と称する。
【００３５】
ノード管理部２１は、中央管理装置１０（に含まれる振り分け処理部１４）によって送信されたデータを受信する。ノード管理部２１は、受信されたデータに対するデータ処理（自ノード２０に振り分けられたデータ処理）の実行を制御および管理する。具体的には、ノード管理部２１は、受信されたデータに付与されているヘッダ情報を構成する目標終了時刻情報によって示される目標終了時刻を満たすようにした上で、当該ヘッダ情報を構成する優先レベル情報によって示される優先レベルの高い順にデータ処理が実行されるように制御および管理する。
【００３６】
なお、ノード管理部２１は、データ処理実行部２３、データ処理推定部２４およびデータ処理分割部２５に対して各種指示を行うことができる。
【００３７】
ノードデータ格納部２２には、ノード管理部２１によって受信されたデータに対するデータ処理（つまり、自ノード２０に振り分けられたデータ処理）を識別するデータ処理ＩＤ（当該データに付与されているヘッダ情報を構成するデータ処理ＩＤ）および当該データが対応づけて格納される。
【００３８】
データ処理実行部２３は、ノードデータ格納部２２を参照して、中央管理装置１０によって自ノード２０に振り分けられたデータ処理を実行する。換言すれば、データ処理実行部２３は、ノードデータ格納部２２に格納されたデータに対するデータ処理を実行する。
【００３９】
また、データ処理実行部２３は、ノード管理部２１からの指示に応じて、自ノード２０に振り分けられたデータ処理の一部を実行する。
【００４０】
データ処理推定部２４は、データ処理実行部２３によってデータ処理の一部が実行された結果に基づいて、当該データ処理における単位処理量（例えば、２ＫＢｙｔｅ／分等）を算出する。データ処理推定部２４は、算出されたデータ処理における単位処理量を用いて、当該データ処理の推定終了時刻を算出する。なお、データ処理推定部２４によって算出されたデータ処理における単位処理量および当該データ処理の推定終了時刻は、ノード管理部２１に渡される。
【００４１】
データ処理分割部２５は、自ノード２０に振り分けられたデータ処理の対象となるデータ（当該データ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納されているデータ）に付与されているヘッダ情報を構成する目標終了時刻情報によって示される目標終了時刻より当該データ処理の推定終了時刻が遅い（つまり、当該データ処理を当該目標終了時刻以前に完了することができない）場合に、当該データを分割する。この場合、データ処理分割部２５は、自ノード２０に振り分けられたデータ処理の対象となるデータを、目標終了時刻までに処理できるサイズのデータと当該目標終了時刻までに処理できないデータ（当該目標終了時刻から溢れるデータ）とに分割する。なお、データ処理分割部２５によって分割された２つのデータのうち、目標終了時刻までに処理できるサイズのデータ（つまり、分割後の前方のデータ）をｆｒｏｎｔデータと称し、目標終了時刻までに処理できないサイズのデータ（つまり、分割後の後方のデータ）をｒｅａｒデータと称する。なお、データ処理分割部２５は、ノード管理部２１からの指示（分割指示）に応じて、分割処理を実行する。
【００４２】
データ処理分割部２５によって分割された２つのデータのうちのｆｒｏｎｔデータは、当該ｆｒｏｎｔデータに対するデータ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納される。なお、ｆｒｏｎｔデータに対するデータ処理を識別するためのデータ処理ＩＤには、当該ｆｒｏｎｔデータに分割される前のデータ（親データ）に対するデータ処理を識別するためのデータ処理ＩＤおよび当該ｆｒｏｎｔデータであることを示す情報が含まれる。
【００４３】
一方、データ処理分割部２５によって分割された２つのデータのうちのｒｅａｒデータは、データ処理ＩＤ、優先レベル情報および目標終了時刻情報から構成されるヘッダ情報が付与されて、中央管理装置１０に返却される。この場合、ｒｅａｒデータに付与されるヘッダ情報を構成するデータ処理ＩＤには、当該ｒｅａｒデータに分割される前のデータ（親データ）に対するデータ処理を識別するためのデータ処理ＩＤおよび当該ｒｅａｒデータであることを示す情報が含まれる。
【００４４】
実行情報格納部２６には、自ノード２０で実行されるデータ処理に関する情報（実行情報）が格納される。実行情報格納部２６には、データ処理に関する実行情報として、処理順、データ処理ＩＤ、優先レベル情報、目標終了時刻情報、推定終了時刻情報および単位処理量等が対応づけて格納される。
【００４５】
実行情報格納部２６に格納されるデータ処理ＩＤ、優先レベル情報および目標終了時刻情報は、自ノード２０に振り分けられたデータ処理の対象となるデータ（つまり、当該データ処理を識別するデータ処理ＩＤに対応づけてノードデータ格納部２２に格納されているアドレスに格納されているデータ）に付与されているヘッダ情報を構成するデータ処理ＩＤ、優先レベル情報および目標終了時刻情報である。
【００４６】
処理順は、データ処理ＩＤによって識別されるデータ処理が実行される順番を示す。なお、処理順は、優先レベル情報によって示される優先レベルに基づいてノード管理部２１によって決定（変更）される。推定終了時刻情報は、データ処理ＩＤによって識別されるデータ処理の推定終了時刻を示す。単位処理量は、データ処理ＩＤによって識別されるデータ処理における単位処理量を示す。なお、データ処理の推定終了時刻および単位処理量は、上記したようにデータ処理推定部２４によって算出される。なお、実行情報格納部２６のデータ構造の詳細については後述する。
【００４７】
図２は、図１に示す中央管理装置１０に含まれる振り分け情報格納部１２のデータ構造の一例を示す。図２に示すように、振り分け情報格納部１２には、ノード２０に振り分けられたデータ処理毎に、データ処理ＩＤ、優先レベル情報、目標終了時刻情報、振り分け時刻情報、振り分け先ノード情報、新規／返却状況情報および処理状況情報が対応づけて格納される。
【００４８】
データ処理ＩＤは、データ処理を識別するための識別子である。データ処理ＩＤにおいては、例えば識別名の後に「_」で連結して使用プログラムの識別名が示される。
【００４９】
優先レベル情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の優先レベル（優先度）を示す。なお、優先レベル情報によって示される優先レベルは例えば１〜５までの５段階であり、最高優先レベルは５であるものとする。
【００５０】
目標終了時刻情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の目標終了時刻を示す。振り分け時刻情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理がノード２０に振り分けられた時刻（振り分け時刻）を示す。振り分け先ノード情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理が振り分けられたノード２０を示す。
【００５１】
新規／返却状況情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の対象となるデータが外部から入力されたものであるか、または、ノード２０から溢れて返却されたものであるかを示す。新規／返却状況情報には、データ処理の対象となるデータが外部から入力されたものであることを示す「新規」およびノード２０から溢れて返却されたものであることを示す「返却」が含まれる。
【００５２】
処理状況情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理が完了したか否かを示す。処理状況情報には、データ処理ＩＤによって識別されるデータ処理が完了したことを示す「完了」および当該データ処理が完了していないことを示す「未」が含まれる。
【００５３】
図２に示す例では、振り分け情報格納部１２には、データ処理ＩＤ「data0_hokenryoukeisan」、優先レベル情報「３」、目標終了時刻情報「２０１０／１／２１  １５：００」、振り分け時刻情報「２０１０／１／２１  １０：００」、振り分け先ノード「ノード２」、新規／返却状況情報「新規」および処理状況情報「完了」が対応づけて格納されている。これによれば、データ処理ＩＤ「data0_hokenryoukeisan」によって識別されるデータ処理の優先レベルが「３」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  １５：００」であり、当該データ処理がノード２に振り分けられた時刻が「２０１０／１／２１  １０：００」であることが示されている。また、データ処理ＩＤ「data0_hokenryoukeisan」によって識別されるデータ処理の対象となるデータが外部から入力されたものであり、当該データ処理は完了していることが示されている。
【００５４】
また、振り分け情報格納部１２には、データ処理ＩＤ「data1_pai」、優先レベル情報「３」、目標終了時刻情報「２０１０／１／２１  １５：００」、振り分け時刻情報「２０１０／１／２１  １０：００」、振り分け先ノード「ノード１」、新規／返却状況情報「新規」および処理状況情報「未」が対応づけて格納されている。これによれば、データ処理ＩＤ「data1_pai」によって識別されるデータ処理の優先レベルが「３」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  １５：００」であり、当該データ処理がノード１に振り分けられた時刻が「２０１０／１／２１  １０：００」であることが示されている。また、データ処理ＩＤ「data1_pai」によって識別されるデータ処理の対象となるデータが外部から入力されたものであり、当該データ処理は完了していないことが示されている。
【００５５】
また、振り分け情報格納部１２には、データ処理ＩＤ「data2_tax」、優先レベル情報「５」、目標終了時刻情報「２０１０／１／２１  ５：００」、振り分け時刻情報「２０１０／１／２１  ３：００」、振り分け先ノード「ノード２」、新規／返却状況情報「新規」および処理状況情報「未」が対応づけて格納されている。これによれば、データ処理ＩＤ「data2_tax」によって識別されるデータ処理の優先レベルが「５」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  ５：００」であり、当該データ処理がノード２に振り分けられた時刻が「２０１０／１／２１  ３：００」であることが示されている。また、データ処理ＩＤ「data2_tax」によって識別されるデータ処理の対象となるデータが外部から入力されたものであり、当該データ処理は完了していないことが示されている。
【００５６】
また、振り分け情報格納部１２には、データ処理ＩＤ「data1_pai/rear」、優先レベル情報「３」、目標終了時刻情報「２０１０／１／２１  １５：００」、振り分け時刻情報「２０１０／１／２１  １３：００」、振り分け先ノード「ノード３」、新規／返却状況情報「返却」および処理状況情報「未」が対応づけて格納されている。これによれば、データ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理の優先レベルが「３」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  １５：００」であり、当該データ処理がノード３に振り分けられた時刻が「２０１０／１／２１  １３：００」であることが示されている。また、データ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理の対象となるデータがノード２０から返却されたものであり、当該データ処理は完了していないことが示されている。
【００５７】
ここで、データ処理ＩＤ「data1_pai/rear」のようにデータ処理ＩＤの後方に「/rear」が含まれている場合、当該データ処理ＩＤによって識別されるデータ処理の対象となるデータは、上述したようにノード２０に含まれるデータ処理分割部２５によって分割された後方のデータ（つまり、ｒｅａｒデータ）である。つまり、データ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理は、データ処理ＩＤ「data1_pai」によって識別されるデータ処理の対象となるデータが分割された後方のデータに対するデータ処理である。一方、振り分け情報格納部１２には格納されないが、データ処理ＩＤの後方に「/front」が含まれている場合、当該データデータ処理ＩＤによって識別されるデータ処理の対象となるデータは、上述したノード２０に含まれるデータ処理分割部２５によって分割された前方のデータ（つまり、ｆｒｏｎｔデータ）である。
【００５８】
なお、例えばデータ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理の対象となるデータが更に分割された場合、当該分割された後方のデータに対するデータ処理を識別するためのデータ処理ＩＤは、データ処理ＩＤ「data1_pai/rear/rear」となる。一方、分割された前方のデータに対するデータ処理を識別するためのデータ処理ＩＤは、データ処理ＩＤ「data1_pai/rear/front」となる。更にデータが分割された場合についても同様である。
【００５９】
また、振り分け情報格納部１２には、データ処理ＩＤ「data3_housedesign」、優先レベル情報「４」、目標終了時刻情報「２０１０／１／２１  ２０：００」、振り分け時刻情報「２０１０／１／２１  １３：３０」、振り分け先ノード「ノード４」、新規／返却状況情報「新規」および処理状況情報「未」が対応づけて格納されている。これによれば、データ処理ＩＤ「data3_housedesign」によって識別されるデータ処理の優先レベルが「４」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  ２０：００」であり、当該データ処理がノード４に振り分けられた時刻が「２０１０／１／２１  １３：３０」であることが示されている。また、データ処理ＩＤ「data3_housedesign」によって識別されるデータ処理の対象となるデータが外部から入力されたものであり、当該データ処理は完了していないことが示されている。
【００６０】
図３は、図１に示す中央管理装置１０に含まれる処理結果格納部１６のデータ構造の一例を示す。図３に示すように、処理結果格納部１６には、データ処理ＩＤおよびデータが対応づけて格納される。
【００６１】
データ処理ＩＤは、データ処理を識別するための識別子である。データ処理結果は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の結果である。
【００６２】
図３に示す例では、処理結果格納部１６には、データ処理ＩＤ「data0_hokenryoukeisan」およびデータ処理結果「データ処理結果０」が対応づけて格納されている。これによれば、データ処理ＩＤ「data0_hokenryoukeisan」によって識別されるデータ処理の結果が「データ処理結果０」であることが示される。
【００６３】
ここでは、図３が処理結果格納部１６のデータ構造の一例を示すものとして説明したが、ノード２０に含まれるノードデータ格納部２２についても処理結果格納部１６と同様のデータ構造を有する。図示しないが、ノードデータ格納部２２においては、図３に示す処理結果格納部１６に格納されているデータ処理結果に代えて、自ノード２０（当該ノードデータ格納部２２を含むノード２０）に振り分けられたデータ処理の対象となるデータが格納される。つまり、ノードデータ格納部２２には、自ノード２０に振り分けられたデータ処理を識別するためのデータ処理ＩＤおよび当該データ処理の対象となるデータが対応づけて格納される。
【００６４】
図４は、図１に示すノード２０に含まれる実行情報格納部２６のデータ構造の一例を示す。実行情報格納部２６には、当該実行情報格納部２６を含むノード２０（自ノード２０）に振り分けられたデータ処理に関する実行情報が格納される。図４に示すように、実行情報格納部２６には、データ処理毎に、処理順、データ処理ＩＤ、優先レベル情報、目標終了時刻情報、開始時刻情報、推定終了時刻情報、単位処理量および処理済情報が対応づけて格納される。
【００６５】
処理順は、自ノード２０に振り分けられたデータ処理（対応づけられているデータ処理ＩＤによって識別されるデータ処理）が実行される順番を示す。データ処理ＩＤは、自ノード２０に振り分けられたデータ処理を識別するための識別子である。優先レベル情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の優先レベルを示す。目標終了時刻情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の目標終了時刻を示す。なお、データ処理ＩＤ、優先レベル情報および目標終了時刻情報については、上述した図２において説明したデータ処理ＩＤ、優先レベル情報及び目標終了時刻情報と同様である。
【００６６】
開始時刻情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理が実際に開始された時刻（開始時刻）を示す。推定終了時刻情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の推定終了時刻（つまり、当該データ処理が終了すると推定される時刻）を示す。単位処理量は、対応づけられているデータ処理ＩＤによって識別されるデータ処理における単位処理量を示す。具体的には、単位処理量は、単位時間あたり（例えば、分単位）に処理されるデータサイズ（処理サイズ）を示す。
【００６７】
また、処理済情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の進捗状況（当該データ処理の対象となるデータに対して既に処理が完了した部分）を示す。具体的には、処理済情報は、対応づけられているデータ処理ＩＤによって識別されるデータ処理の対象となるデータのデータ量（例えば、ファイル数）およびサイズに対する当該処理が完了したデータ量およびサイズを示す。換言すれば、処理済情報には、データ処理の対象となるデータのデータ量およびサイズと、当該処理が完了したデータ量およびサイズが含まれる。
【００６８】
図４に示す例では、実行情報格納部２６には、処理順「２」、データ処理ＩＤ「data1_pai/front」、優先レベル情報「３」、目標終了時刻情報「２０１０／１／２１  １５：００」、推定終了時刻情報「２０１０／１／２１  １５：００」、単位処理量「２Ｋｂｙｔｅ／分」および処理済情報「６０／１８０ｆｉｌｅ：５６／１６８ＭＢｙｔｅ」が対応づけて格納されている。これによれば、データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理の処理順が「２」であり、当該データ処理の優先レベルが「３」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  １５：００」であり、当該データ処理の推定終了時刻が「２０１０／１／２１  １５：００」であることが示されている。また、データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理における１分あたりの処理量が２Ｋｂｙｔｅであることが示されている。更に、データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理の対象となるデータのデータ量「１８０ｆｉｌｅ」のうちの「６０ｆｉｌｅ」の処理が完了しており、また、当該データのサイズ「１６８ＭＢｙｔｅ」のうちの「５６ＭＢｙｔｅ」の処理が完了していることが示されている。
【００６９】
なお、処理順が「２」であるため、データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理は実行されていない（例えば、停止中である）。このため、データ処理ＩＤ「data1_pai/front」に対応づけられている開始時刻情報は空欄となっている。
【００７０】
また、データ処理ＩＤ「data1_pai/front」には「/front」が含まれているため、当該データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理は、データ処理ＩＤ「data1_pai」によって識別されるデータ処理の対象となるデータが分割された前方のデータに対するデータ処理である。
【００７１】
実行情報格納部２６には、処理順「１」、データ処理ＩＤ「data2_tax」、優先レベル情報「５」、目標終了時刻情報「２０１０／１／２１  ５：００」、開始時刻情報「２０１０／１／２１  ０：００」、推定終了時刻情報「２０１０／１／２１  ５：００」、単位処理量「４Ｋｂｙｔｅ／分」および処理済情報「２０／４０ｆｉｌｅ：３０／６０ＭＢｙｔｅ」が対応づけて格納されている。これによれば、データ処理ＩＤ「data2_tax」によって識別されるデータ処理の処理順が「１」であり、当該データ処理の優先レベルが「５」であり、当該データ処理の目標終了時刻が「２０１０／１／２１  ５：００」であり、当該データ処理の開始時刻が「２０１０／１／２１  ０：００」であり、当該データ処理の推定終了時刻が「２０１０／１／２１  ５：００」であることが示されている。また、データ処理ＩＤ「data2_tax」によって識別されるデータ処理における１分あたりの処理量が４Ｋｂｙｔｅであることが示されている。更に、データ処理ＩＤ「data2_tax」によって識別されるデータ処理の対象となるデータのデータ量「４０ｆｉｌｅ」のうちの「２０ｆｉｌｅ」の処理が完了しており、また、当該データのサイズ「６０ＭＢｙｔｅ」のうちの「３０ＭＢｙｔｅ」の処理が完了していることが示されている。
【００７２】
なお、データ処理ＩＤ「data1_pai/front」およびデータ処理ＩＤ「data2_tax」に対応づけられている処理順は、当該データ処理ＩＤ「data1_pai/front」およびデータ処理ＩＤ「data2_tax」に対応づけられている優先レベル情報によって示される優先レベルに基づいて決定される。具体的には、データ処理ＩＤ「data1_pai/front」に対応づけられている優先レベル情報によって示される優先レベルは「３」であり、データ処理ＩＤ「data2_tax」に対応づけられている優先レベル情報によって示される優先レベルは「５」であり、当該データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理の優先レベルの方が高い。このため、データ処理ＩＤ「data1_pai/front」に対応づけられている処理順が「２」となり、データ処理ＩＤ「data2_tax」に対応づけられている処理順が「１」となる。
【００７３】
以下、本実施形態に係る分散データ処理システムの動作について説明する。まず、分散データ処理システムを構成する中央管理装置１０および複数のノード２０の動作の概要について簡単に説明する。
【００７４】
分散データ処理システムを構成する中央管理装置１０は、例えば外部からデータ処理の対象となるデータ、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理の優先レベルを示す優先レベル情報を入力し、当該データ処理をノード２０に振り分ける。この場合、中央管理装置１０は、各ノード２０の例えばリソース性能等を確認することなくデータ処理をノードに対して振り分ける。また、中央管理装置１０は、ノードから返されたデータ処理の結果を外部に対して出力する。
【００７５】
一方、中央管理装置２０によってデータ処理が振り分けられたノード２０は、当該データ処理の優先レベルを考慮した上で、目標終了時刻を満たすようにデータ処理を実行する。この場合、ノード２０は、目標終了時刻までにデータ処理を完了できない場合であって当該データ処理の対象となるデータを分割できる場合には、当該データを分割する（当該データ処理を分割する）。ノード２０は、目標終了時刻までに処理を完了できないデータ（データ処理の対象となるデータ）を中央管理装置に返却する。
【００７６】
なお、ノード２０からデータが返却された場合、当該データに対するデータ処理は、中央管理装置１０によって再び他のノード２０に振り分けられる。
【００７７】
ここで、図５および図６を参照して、本実施形態に係る分散データ処理システムの動作の概要について具体的に説明する。ここでは、例えばデータ処理を実行しているノード２０に対して、当該データ処理よりも優先レベルが高いデータ処理が中央管理装置１０によって振り分けられた場合の動作について説明する。
【００７８】
図５は、データ処理を実行している複数のノード２０の状態を説明するための図である。ここでは、分散データ処理システムを構成する複数のノード２０として、ノード１〜３が含まれるものとする。また、図５に示すように、ノード１ではデータ処理１、ノード２ではデータ処理２、ノード３データはデータ処理３が実行されているものとする。なお、データ処理１の優先レベルは「３」であるものとする。また、データ処理２およびデータ処理３の優先レベルは「４」であるものとする。なお、ノード１〜３においては、データ処理１〜３をそれぞれの目標終了時刻以前に完了（終了）できる状態であるものとする。
【００７９】
ここで、図６を参照して、ノード１〜３が図５に示すような状態である場合において、ノード１に対してデータ処理４が新たに振り分けられた場合の分散データ処理システムの動作について説明する。なお、ノード１に振り分けられたデータ処理４の優先レベルは「５」であるものとする。
【００８０】
まず、ノード１は、データ処理４の対象となるデータを受信する（ステップＳ１）。ここで、ノード１に対して振り分けられたデータ処理４の優先レベルは、当該ノード１において実行されているデータ処理１の優先レベルよりも高い。この場合、ノード１においては、データ処理１よりもデータ処理４が優先的に実行される。つまり、ノード１においては、データ処理１の実行が停止され、データ処理４が実行される。これにより、データ処理４については、目標終了時刻以前に完了できる。
【００８１】
ここで、ノード１においてはデータ処理４が優先的に実行されるため、ノード１では、データ処理１を当該データ処理４の後ろにずらさなければならない。つまり、データ処理１は、データ処理４の終了後に実行されるように制御される。しかしながら、データ処理１がデータ処理４の終了後に実行された場合には、図６に示すように、当該データ処理１を当該データ処理１の目標終了時刻までに完了することができなくなる。
【００８２】
この場合、ノード１において、データ処理１の対象となるデータは、当該データ処理１の目標終了時刻までに処理できる部分５１（以下、データ処理１のｆｒｏｎｔデータ５１と表記）と当該目標終了時刻までに処理できない（つまり、当該目標終了時刻から溢れる）部分５２（以下、データ処理１のｒｅａｒデータ５２と表記）とに分割される（ステップＳ２）。このようにデータ処理１の対象となるデータが分割されると、当該データ処理１のｒｅａｒデータ５２は、中央管理装置１０に返却される。なお、データ処理１のｆｒｏｎｔデータ５１に対するデータ処理は、ノード１においてデータ処理４の終了後に実行される。
【００８３】
中央管理装置１０は、ノード１から返却されたデータ処理１のｒｅａｒデータ５２に対するデータ処理の再振り分けを行う。なお、データ処理は、例えば既に実行されているデータ処理の終了時刻（推定終了時刻）が目標終了時刻より前であるノードに振り分けられる。ここでは、データ処理１のｒｅａｒデータ５２に対するデータ処理は、ノード２に振り分けられたものとする。
【００８４】
この場合、ノード２は、データ処理１のｒｅａｒデータ５２を受信する（ステップＳ３）。ここで、データ処理１の優先レベルは、ノード２で実行されているデータ処理２の優先レベルよりも低い。この場合、ノード２においては、データ処理１よりもデータ処理２が優先的に実行される。つまり、ノード２においては、処理順は変更されず、データ処理２の終了後にデータ処理１のｒｅａｒデータ５２に対するデータ処理が実行される。しかしながら、データ処理１のｒｅａｒデータ５２に対するデータ処理がデータ処理２の終了後に実行された場合には、図６に示すように、データ処理１のｒｅａｒデータに対するデータ処理を当該データ処理１の目標終了時刻までに完了することはできない。
【００８５】
この場合、ノード２において、データ処理１のｒｅａｒデータ５２は、当該データ処理１の目標終了時刻までに処理できる部分５２１（以下、データ処理１のｒｅａｒデータのｆｒｏｎｔデータ５２１と表記）と当該目標終了時刻までに処理できない部分５２２（以下、データ処理１のｒｅａｒデータのｒｅａｒデータ５２２と表記）とに分割（再分割）される（ステップＳ４）。このように、データ処理１のｒｅａｒデータ５２が分割されると、当該データ処理１のｒｅａｒデータのｒｅａｒデータ５２２は、中央管理装置１０に返却される。なお、データ処理１のｒｅａｒデータのｆｒｏｎｔデータ５２１に対するデータ処理は、データ処理２の終了後に実行される。
【００８６】
中央管理装置１０は、ノード２から返却されたデータ処理１のｒｅａｒデータのｒｅａｒデータ５２２に対するデータ処理の再振り分けを行う。ここでは、データ処理１のｒｅａｒデータのｒｅａｒデータ５２２に対するデータ処理は、ノード３に振り分けられたものとする。
【００８７】
この場合、ノード３は、データ処理１のｒｅａｒデータのｒｅａｒデータ５２２を受信する（ステップＳ５）。ここで、データ処理１の優先レベルは、ノード３において実行されているデータ処理３の優先レベルよりも低い。この場合、ノード３においては、データ処理１よりもデータ処理３が優先的に実行される。つまり、ノード３においては、処理順は変更されず、データ処理３の終了後にデータ処理１のｒｅａｒデータのｒｅａｒデータ５２２に対するデータ処理が実行される。
【００８８】
ここで、データ処理１のｒｅａｒデータのｒｅａｒデータ５２２に対するデータ処理は、データ処理１の目標終了時刻までに完了することができる。したがって、ノード３において、データ処理１のｒｅａｒデータのｒｅａｒデータ５２２は分割されず、上記したようにデータ処理３の終了後に当該データ処理１のｒｅａｒデータのｒｅａｒデータ５２２に対するデータ処理が実行される。これによって、データ処理１は、ノード１〜３の各々によって分散して実行され、完了することができる。
【００８９】
次に、本実施形態に係る分散データ処理システムにおいて実行される処理について詳細に説明する。本実施形態に係る分散データ処理システムにおいては、第１〜第５の処理が実行される。なお、第１〜第５の処理は、例えば独立して実行される。
【００９０】
第１の処理は、外部から入力されたデータに対するデータ処理を振り分ける際の処理である。第２の処理は、中央管理装置１０によって振り分けられたデータ処理を実行する際の処理である。第３の処理は、ノード２０から溢れて返却されたデータに対するデータ処理を振り分ける際の処理である。第４の処理は、データ処理の結果を中央管理装置１０に送信する際の処理である。第５の処理は、ノード２０によって実行されたデータ処理の結果を出力する際の処理である。
【００９１】
なお、第１の処理、第３の処理および第５の処理は、中央管理装置１０が実行する処理である。また、第２の処理および第４の処理は、データ処理を振り分けられた各ノード２０が実行する処理である。
【００９２】
以下、本実施形態に係る分散データ処理システムにおいて実行される第１〜第５の処理の各々について説明する。
【００９３】
まず、図７のフローチャートを参照して、本実施形態に係る分散データ処理システムにおいて実行される第１の処理の処理手順について説明する。第１の処理は、外部から入力されたデータに対するデータ処理を振り分ける際の処理である。この第１の処理は、中央管理装置１０によって実行される。
【００９４】
中央管理装置１０に含まれるヘッダ情報付与部１１は、ノード２０に振り分けられていないデータ処理の対象となるデータを入力する（ステップＳ１１）。以下、第１の処理において、ヘッダ情報付与部１１によって入力されたデータに対するデータ処理（つまり、振り分けの対象となるデータ処理）を振り分け対象データ処理と称する。
【００９５】
また、ヘッダ情報付与部１１は、振り分け対象データ処理の目標終了時刻を示す目標終了時刻情報および当該振り分け対象データ処理の優先レベルを示す優先レベル情報を入力する（ステップＳ１２）。なお、ヘッダ情報付与部１１によって入力された目標終了時刻情報によって示される目標終了時刻情報および優先レベル情報によって示される優先レベルは、例えば分散データ処理システムを利用するユーザによって指定される。
【００９６】
次に、ヘッダ情報付与部１１は、振り分け対象データ処理を識別するためのデータ処理ＩＤ、入力された目標終了時刻情報および優先レベル情報から構成されるヘッダ情報を、入力されたデータに対して付与する（ステップＳ１３）。なお、ヘッダ情報付与部１１によってデータに付与されたヘッダ情報を構成するデータ処理ＩＤは、当該データが入力された際に、振り分け対象データ処理に対して当該ヘッダ情報付与部１１によって自動的に発行される。
【００９７】
振り分け判定部１３は、振り分け情報格納部１２に格納されている振り分け先ノード情報に基づいて、データ処理を実行していないノード２０があるか否かを判定する（ステップＳ１４）。具体的には、振り分け判定部１３は、複数のノード２０の中に、データ処理を実行しているノード２０以外のノード２０が存在するか否かを判定する。なお、データ処理を実行しているノード２０とは、処理状況情報「未」に対応づけて振り分け情報格納部１２に格納されている振り分け先ノード情報によって示されるノード２０である。
【００９８】
データ処理を実行していないノード２０がないと判定された場合（ステップＳ１４のＮＯ）、振り分け判定部１３は、振り分け情報格納部１２に格納されている目標終了時刻情報および振り分け先ノード情報に基づいて、ノード２０毎に最も遅い目標終了時刻を抽出する（ステップＳ１５）。この場合、振り分け判定部１３は、ノード２０毎に、当該ノード２０を示す振り分け先ノード情報に対応づけて振り分け情報格納部１２に格納されている目標終了時刻情報を取得し、当該取得された目標終了時刻情報によって示される目標終了時刻の中から最も遅い目標終了時刻を抽出する。つまり、振り分け判定部１３は、ノード２０毎に１つの目標終了時刻を抽出する。
【００９９】
次に、振り分け判定部１３は、ノード２０毎に抽出された目標終了時刻の中で最も早い目標終了時刻が抽出されたノード２０（最も早い目標終了時刻に関するノード）を特定する（ステップＳ１６）。
【０１００】
振り分け判定部１３は、特定されたノード２０が複数存在するか否かを判定する（ステップＳ１７）。
【０１０１】
ここで、振り分け判定部１３によって特定されたノード２０が複数存在すると判定された場合（ステップＳ１７のＹＥＳ）、振り分け判定部１３は、当該特定された複数のノード（以下、候補ノードと表記）２０の中から、目標終了時刻内にデータ処理を完了することができずに当該目標終了時刻から溢れたデータを返却したノード（つまり、返却元のノード）２０を特定する。振り分け判定部１３は、候補ノード２０のうち、溢れたデータを返却したノード２０以外のノード２０を、振り分け対象データ処理が振り分けられるノード（振り分け先ノード）として決定（特定）する（ステップＳ１８）。
【０１０２】
なお、溢れたデータを返却したノード２０とは、振り分け情報格納部１２において新規／返却状況情報「返却」に対応づけられているデータ処理ＩＤに「/rear」が含まれていない場合には当該データ処理ＩＤと同一のデータ処理ＩＤおよび処理状況情報「未」に対応づけて振り分け情報格納部１２に格納されている振り分け先ノード情報によって示されるノード２０、または、振り分け情報格納部１２において新規／返却状況情報「返却」に対応づけられているデータ処理ＩＤに「/rear」が含まれている場合には当該「/rear」の前部分と同一のデータ処理ＩＤおよび処理状況情報「未」に対応づけて振り分け情報格納部１２に格納されている振り分け先ノード情報によって示されるノード２０である。
【０１０３】
振り分け処理部１４は、振り分け判定部１３によって決定されたノード２０（つまり、振り分け先ノード）に対して振り分け対象データ処理を振り分ける（ステップＳ１９）。この場合、振り分け処理部１４は、ヘッダ情報付与部１１によってヘッダ情報が付与されたデータを、振り分け判定部１３によって決定されたノード２０に対して送信する。
【０１０４】
また、振り分け処理部１４は、振り分け対象データ処理の振り分けに関する情報（振り分け情報）を振り分け情報格納部１２に格納する（ステップＳ２０）。
【０１０５】
具体的には、振り分け処理部１４は、ヘッダ情報付与部１１によってデータに付与されたヘッダ情報を構成するデータ処理ＩＤ（振り分け対象データ処理を識別するためのデータ処理ＩＤ）、目標終了時刻情報および優先レベル情報を対応づけて振り分け情報格納部１２に格納する。更に、振り分け処理部１４は、振り分け対象データ処理を識別するためのデータ処理ＩＤに対応づけて、当該振り分け対象データ処理が振り分け判定部１３によって決定されたノード２０に振り分けられた時刻を示す振り分け時刻情報、当該ノード２０（振り分け先ノード）を示す振り分け先ノード情報、当該振り分け対象データ処理の対象となるデータが外部から入力されたものであること（つまり、ヘッダ情報付与部１１によって入力されたこと）を示す新規／返却状況情報「新規」および振り分け対象データ処理が完了していないことを示す処理状況情報「未」を振り分け情報格納部１２に格納する。なお、ステップＳ２０の処理が実行されると分散データ処理システムにおいて実行される第１の処理は終了される。
【０１０６】
一方、ステップＳ１４においてデータ処理を実行していないノード２０があると判定された場合、当該ノード２０を振り分け先ノードとして、上記したステップＳ１９およびＳ２０の処理が実行される。
【０１０７】
また、ステップＳ１７において、振り分け判定部１３によって特定されたノード２０が複数存在しないと判定された（つまり、１つのノード２０が特定された）場合、当該振り分け判定部１３によって特定されたノード２０を振り分け先ノードとして、上記したステップＳ１９およびＳ２０の処理が実行される。
【０１０８】
ここで、図８および図９を参照して、分散データ処理システムにおいて実行される第１の処理の具体例について説明する。
【０１０９】
図８は、分散データ処理システムにおいて第１の処理が実行される前の中央管理装置１０に含まれる振り分け情報格納部１２のデータ構造の一例を示す。なお、振り分け情報格納部１２に格納されている情報については、上述した図２において説明した通りであるため、その詳しい説明を省略する。
【０１１０】
また、ここでは分散データ処理システムを構成する複数のノード２０としてノード１〜３の３つのノードが存在するものとする。
【０１１１】
まず、分散データ処理システムにおいて実行される第１の処理では、中央管理装置１０に含まれるヘッダ情報付与部１１は、振り分け対象データ処理の対象となるデータを入力する。また、ヘッダ情報付与部１１は、振り分け対象データ処理の目標終了時刻を示す目標終了時刻情報および当該振り分け対象データ処理の優先レベルを示す優先レベル情報を入力する。ここでは、ヘッダ情報付与部１１は、ユーザによって指定された目標終了時刻情報「２０１０／１／２１  ８：００」および優先レベル情報「４」を入力したものとする。なお、振り分け対象データ処理を識別するためのデータ処理ＩＤとして「data2_housedesign」がヘッダ情報付与部１１によって自動的に発行されたものとする。
【０１１２】
ヘッダ情報付与部１１は、データ処理ＩＤ「data2_housedesign」、目標終了時刻「２０１０／１／２１  ８：００」および優先レベル情報「４」から構成されるヘッダ情報をデータに付与する。
【０１１３】
次に、振り分け判定部１３は、ノード１〜３の中から振り分け対象データ処理が振り分けられるノードを決定する処理（データ処理ＩＤ「data2_housedesign」に関する振り分け判定）を行う。
【０１１４】
まず、振り分け判定部１３は、振り分け情報格納部１２に格納されている振り分け先ノード情報に基づいて、ノード１〜３の中にデータ処理を実行していないノードがあるか否かを判定する。この場合、振り分け判定部１３は、振り分け情報格納部１２において、処理状況情報「未」に対応づけられているノード１〜３の各々を示す振り分け先ノード情報が存在するか否かを判定する。
【０１１５】
図８に示す振り分け情報格納部１２には、処理状況情報「未」に対応づけられているノード１〜３を示す振り分け先ノード情報が存在する。したがって、振り分け判定部１３は、ノード１〜３の中にデータ処理を実行していないノードはないと判定する。
【０１１６】
次に、振り分け判定部１３は、振り分け情報格納部１２に格納されている目標終了時刻情報および振り分け先ノード情報に基づいて、ノード毎（ここでは、ノード１〜３）に最も遅い目標終了時刻を抽出する。
【０１１７】
図８に示す振り分け情報格納部１２によれば、ノード１を示す振り分け先ノード情報（および処理済状況情報「未」）に対応づけて当該振り分け情報格納部１２に格納されている目標終了時刻情報によって示される目標終了時刻のうち最も遅い目標終了時刻は「２０１０／１／２１  １５：００」である。したがって、ノード１については、最も遅い目標終了時刻として「２０１０／１／２１  １５：００」が抽出される。
【０１１８】
また、ノード２を示す振り分け先ノード情報（および処理済状況情報「未」）に対応づけて振り分け情報格納部１２に格納されている目標終了時刻情報によって示される目標終了時刻のうち最も遅い目標終了時刻は「２０１０／１／２１  １７：００」である。したがって、ノード２については、最も遅い目標終了時刻として「２０１０／１／２１  １７：００」が抽出される。
【０１１９】
更に、ノード３を示す振り分け先ノード情報（および処理済状況情報「未」）に対応づけて振り分け情報格納部１２に格納されている目標終了時刻情報によって示される目標終了時刻のうち最も遅い目標終了時刻は「２０１０／１／２１  １５：００」である。したがって、ノード３については、最も遅い目標終了時刻として「２０１０／１／２１  １５：００」が抽出される。
【０１２０】
次に、振り分け判定部１３は、ノード毎に抽出された目標終了時刻の中で最も早い目標終了時刻が抽出されたノードを特定する。ここでは、振り分け判定部１３は、ノード１およびノード３を特定する。
【０１２１】
ここで、振り分け判定部１３によって特定されたノードはノード１およびノード３の２つである（つまり、振り分け判定部１３によって特定されたノードが複数存在する）。このため、振り分け判定部１３は、ノード１およびノード３（候補ノード）の中から、目標終了時刻から溢れたデータを返却したノードを特定する。
【０１２２】
この場合、図８に示す振り分け情報格納部１２において新規／返却状況情報「返却」に対応づけられているデータ処理ＩＤは、「data1_pai/rear」である。ここで、このデータ処理ＩＤ「data1_pai/rear」には「/rear」が含まれているため、当該「/rear」の前部分である「data1_pai」と同一のデータ処理ＩＤに対応づけて振り分け情報格納部１２に格納されている振り分け先ノード情報によって示されるノード１が目標終了時刻から溢れたデータを返却したノードである。つまり、ノード１は、データ処理ＩＤ「data1_pai」によって識別されるデータ処理の対象となるデータを分割し、当該分割された後方のデータ（つまり、ｒｅａｒデータ）を中央管理装置１０に返却している。よって、振り分け判定部１３は、目標終了時刻から溢れたデータを返却したノードとしてノード１を特定する。
【０１２３】
この場合、振り分け判定部１３は、候補ノードであるノード１およびノード３のうち、目標終了時刻から溢れたデータを返却したノード１以外のノードであるノード３を、振り分け先ノードとして決定する。
【０１２４】
振り分け処理部１４は、振り分け対象データ処理を振り分け先ノードとして決定されたノード３に振り分ける。この場合、振り分け処理部１４は、ヘッダ情報付与部１１によって入力されたデータ（振り分け対象データ処理の対象となるデータ）をノード３に送信する。
【０１２５】
また、振り分け処理部１４は、振り分け対象データ処理の振り分けに関する情報を振り分け情報格納部１２に格納（登録）する。
【０１２６】
ここで、図９は、分散データ処理システムにおいて第１の処理が実行された（つまり、振り分け対象データ処理が振り分けられた）後の振り分け情報格納部１２のデータ構造の一例を示す。
【０１２７】
図９に示すように、振り分け情報格納部１２には、図８に示す振り分け情報格納部１２と比較して、ヘッダ情報付与部１１によってデータに付与されたヘッダ情報を構成するデータ処理ＩＤ「data2_housedesign」、目標終了時刻情報「２０１０／１／２１  ８：００」および優先レベル情報「４」が対応づけて格納されている。更に、振り分け情報格納部１２には、データ処理ＩＤ「data2_housedesign」に対応づけて、振り分け対象データ処理がノード３に振り分けられた時刻を示す振り分け時刻情報「２０１０／１／２１  ７：００」、振り分け対象データ処理が振り分けられたノード３を示す振り分け先ノード情報「ノード３」、振り分け対象データ処理の対象となるデータが外部から入力されたものであることを示す新規／返却状況情報「新規」および振り分け対象データ処理が完了していないことを示す処理状況情報「未」が格納されている。
【０１２８】
上記したように分散データ処理システムにおいて第１の処理が実行されると、図８に示す振り分け情報格納部１２は、図９に示す振り分け情報格納部１２に更新される。
【０１２９】
次に、図１０〜図１３のフローチャートを参照して、本実施形態に係る分散データ処理システムにおいて実行される第２の処理の処理手順について説明する。第２の処理は、中央管理装置１０によって振り分けられたデータ処理を実行する際の処理である。この第２の処理は、データ処理を振り分けられたノード２０によって実行される。
【０１３０】
ここでは、第２の処理を実行するノード（データ処理を振り分けられたノード）２０を対象ノード２０と称する。また、対象ノード２０に振り分けられたデータ処理を対象データ処理と称する。
【０１３１】
まず、対象ノード２０に含まれるノード管理部２１は、中央管理装置１０によって送信されたデータを受信する（ステップＳ３１）。ノード管理部２１によって受信されたデータは、対象データ処理の対象となるデータである。なお、ノード管理部２１によって受信されたデータには、ヘッダ情報が付与されている。このヘッダ情報は、対象データ処理を識別するためのデータ処理ＩＤ、当該対象データ処理の目標終了時刻を示す目標終了時刻情報および当該対象データ処理の優先レベルを示す優先レベル情報から構成される。
【０１３２】
ノード管理部２１は、受信されたデータに付与されているヘッダ情報を構成するデータ処理ＩＤおよび当該データを対応づけてノードデータ格納部２２に格納する（ステップＳ３２）。
【０１３３】
次に、ノード管理部２１は、実行情報格納部２６を参照して、対象データ処理の一部を実行可能か否か、つまり、当該対象データ処理の一部が割り込み可能か否かを判定する（ステップＳ３３）。
【０１３４】
ノード管理部２１は、例えば実行情報格納部２６に対象データ処理以外の他のデータ処理（以下、既存データ処理と表記）に関する実行情報が格納されていない場合、つまり、対象ノード２０において既存データ処理が存在しない場合には、対象データ処理の一部が割り込み可能であると判定する。また、ノード管理部２１は、例えば実行情報格納部２６に既存データ処理に関する実行情報が格納されている場合、つまり、対象ノード２０において既存データ処理が存在する場合であっても、当該既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている目標終了時刻情報によって示される目標終了時刻と推定終了時刻情報によって示される推定終了時刻との間に予め定められた時間以上の間隔がある場合には、対象データ処理の一部が割り込み可能であると判定する。つまり、既存データ処理の目標終了時刻と推定終了時刻との間に所定の間隔があれば、対象データ処理の一部が割り込み可能であると判定される。
【０１３５】
これに対して、対象ノード２０において既存データ処理が存在する場合であって、当該既存データ処理の目標終了時刻と推定終了時刻との間に所定の間隔がない場合、対象データ処理の一部が割り込み可能でないと判定される。
【０１３６】
なお、対象データ処理の一部が割り込み可能でないと判定された場合（ステップＳ３３のＮＯ）、ノード管理部２１は、当該割り込み可能となるまで、つまり、既存データ処理が完了（終了）するまで待機する（ステップＳ３４）。なお、ステップＳ３４の処理が実行されると、ステップＳ３３に戻って処理が繰り返される。これにより、既存データ処理が完了した場合には、ステップＳ３３において対象データ処理の一部が割り込み可能であると判定される。
【０１３７】
対象データ処理の一部が割り込み可能であると判定された場合（ステップＳ３３のＹＥＳ）、ノード管理部２１は、対象データ処理の一部の実行をデータ処理実行部２３に指示する。
【０１３８】
データ処理実行部２３は、ノード管理部２１からの指示に応じて、対象データ処理の一部を実行する（ステップＳ３５）。データ処理実行部２３は、実行結果をデータ処理推定部２４に渡す。この実行結果には、例えばデータ処理実行部２３によって実行された対象データ処理の一部の実行の対象となったデータのサイズ（データサイズ）および当該対象データ処理の一部の実行に費やした時間（処理時間）等が含まれる。
【０１３９】
データ処理推定部２４は、データ処理実行部２３から渡された実行結果（に含まれるデータサイズおよび処理時間）に基づいて、対象データ処理における単位処理量を算出する（ステップＳ３６）。この場合、データ処理推定部２４は、例えばデータサイズを処理時間で除算することによって単位時間あたりの処理量（単位処理量）を算出する。
【０１４０】
また、データ処理推定部２４は、算出された対象データ処理における単位処理量を用いて、対象データ処理の推定終了時刻を算出する（ステップＳ３７）。
【０１４１】
この場合、データ処理推定部２４は、例えば対象データ処理の対象となるデータを当該対象データ処理における単位処理量で除算することによって当該対象データ処理の完了に必要な時間（以下、推定処理時間と表記）を算出する。
【０１４２】
ここで、対象ノード２０において既存データ処理が存在しない場合には、データ処理推定部２４は、例えばステップＳ３１においてデータが受信された時刻を基準として、当該時刻に推定処理時間を加算することによって推定終了時刻を算出する。
【０１４３】
一方、対象ノード２０において既存データ処理が存在する場合には、データ処理推定部２４は、当該既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている推定終了時刻情報によって示される時刻（つまり、既存データ処理の推定終了時刻）を基準として、当該時刻に推定処理時間を加算することによって推定終了時刻を算出する。
【０１４４】
ステップＳ３７の処理が実行されると、ノード管理部２１は、対象データ処理に関する実行情報として、受信されたデータに付与されているヘッダ情報を構成するデータ処理ＩＤ、目標終了時刻情報および優先レベル情報と、データ処理推定部２４によって算出された対象データ処理の推定終了時刻を示す推定終了時刻情報および対象データ処理における単位処理量とを対応づけて実行情報格納部２６に格納する。
【０１４５】
また、既存データ処理が存在する場合には、対象データ処理の処理順として当該既存データ処理の処理順の次の値が実行情報格納部２６に格納される。一方、既存データ処理が存在しない場合には、対象データ処理の処理順として「１」が実行情報格納部２６に格納される。
【０１４６】
また、例えば対象データ処理の対象となるデータのデータ量が２０ｆｉｌｅであり、サイズが５０ＭＢｙｔｅである場合には、処理済情報としては、「０／２０ｆｉｌｅ：０／５０ＭＢｙｔｅ」が実行情報格納部２６に格納される。
【０１４７】
次に、ノード管理部２１は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納された目標終了時刻情報によって示される対象データ処理の目標終了時刻および推定終了時刻情報によって示される対象データ処理の推定終了時刻に基づいて、対象データ処理が当該目標終了時刻以前に終了するか否かを判定する（ステップＳ３８）。この場合、対象データ処理の目標終了時刻が推定終了時刻以前であれば、対象データ処理が目標終了時刻以前に終了しないと判定される。一方、対象データ処理の目標終了時刻が推定終了時刻より後であれば、対象データ処理が目標終了時刻以前に終了すると判定される。
【０１４８】
対象データ処理が目標終了時刻以前に終了しないと判定された場合（ステップＳ３８のＮＯ）、ノード管理部２１は、対象ノード２０において既存データ処理（つまり、他のデータ処理）が存在するか（既存データ処理が実行されているか）否かを判定する（ステップＳ３９）。ここでは、上記したように実行情報格納部２６に既存データ処理に関する実行情報が格納されている場合には、対象ノード２０において既存データ処理が存在すると判定される。
【０１４９】
対象ノード２０において既存データ処理が存在すると判定された場合（ステップＳ３９のＹＥＳ）、ノード管理部２１は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている優先レベル情報によって示される対象データ処理の優先レベルと既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている優先レベル情報によって示される既存データ処理の優先レベルとを比較する。これによって、ノード管理部２１は、対象データ処理の優先レベルが既存データ処理の優先レベルより高いか否かを判定する（ステップＳ４０）。
【０１５０】
対象データ処理の優先レベルが既存データ処理の優先レベルより高いと判定された場合（ステップＳ４０のＹＥＳ）、ノード管理部２１は、当該対象データ処理および既存データ処理の処理順を入れ替える（ステップＳ４１）。具体的には、ノード管理部２１は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている処理順と既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている処理順とを入れ替える。これにより、対象データ処理の処理順が前（例えば、処理順「１」）となり、既存データ処理の処理順が後（例えば、処理順「２」）となる。
【０１５１】
次に、ノード管理部２１は、データ処理推定部２４に対して、実行情報格納部２６に格納されている処理順が前のデータ処理の推定終了時刻の再推定を依頼する。ここでは、上記したように処理順が入れ替えられているため、対象データ処理の推定終了時刻の再推定が依頼される。
【０１５２】
ノード管理部２１によって対象データ処理の推定終了時刻の再推定が依頼されると、既存データ処理の実行が停止される。
【０１５３】
データ処理推定部２４は、既存データ処理の実行が停止された時刻および対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている対象データ処理における単位処理量に基づいて対象データ処理（つまり、処理順が前のデータ処理）の推定終了時刻を算出する（ステップＳ４２）。
【０１５４】
具体的には、データ処理推定部２４は、対象データ処理の対象となるデータ（のサイズ）を当該対象データ処理における単位処理量で除算することによって当該対象データ処理の完了に必要な時間（推定処理時間）を算出し、当該推定処理時間を既存データ処理の実行が停止された時刻に加算することによって当該対象データ処理の推定終了時刻を算出する。なお、データ処理推定部２４によって算出された対象データ処理の推定終了時刻は、当該対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される（上書きされる）。
【０１５５】
次に、ノード管理部２１は、処理順が前のデータ処理である対象データ処理の対象となるデータが当該対象データ処理の目標終了時刻から溢れるか否かを判定する（ステップＳ４３）。この場合、ノード管理部２１は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納された目標終了時刻情報によって示される対象データ処理の目標終了時刻および推定終了時刻情報によって示される対象データ処理の推定終了時刻に基づいて、対象データ処理が当該目標終了時刻以前に終了するか否かを判定する。つまり、ノード管理部２１は、対象データ処理が目標終了時刻以前に終了する場合には対象データ処理の対象となるデータが当該対象データ処理の目標終了時刻から溢れないと判定し、対象データ処理が目標終了時刻以前に終了しない場合には対象データ処理の対象となるデータが当該対象データ処理の目標終了時刻から溢れると判定する。
【０１５６】
対象データ処理（処理順が前のデータ処理）の対象となるデータが溢れると判定された場合（ステップＳ４３のＹＥＳ）、ノード管理部２１は、当該対象データ処理の対象となるデータの分割が必要であるか否かを判定する（ステップＳ４４）。
【０１５７】
具体的には、対象データ処理の目標終了時刻が上記した既存データ処理を停止した時刻（つまり、対象データ処理の推定終了時刻を算出する際に基準とした時刻）以前であるような場合、または、対象データ処理の目標終了時刻は上記した既存データ処理を停止した時刻より後であるが、当該既存データ処理を停止した時刻から当該対象データ処理の目標終了時刻までの間で当該対象データ処理における１単位（例えば、１ファイル）も処理できないような場合には、ノード管理部２１は、当該対象データ処理の対象となるデータの分割は必要でないと判定する。なお、これら以外の場合については、ノード管理部２１は、対象データ処理の対象となるデータの分割が必要であると判定する。
【０１５８】
対象データ処理の対象となるデータの分割が必要であると判定された場合（ステップＳ４４のＹＥＳ）、ノード管理部２１は、データ処理分割部２５に対して当該データの分割を指示する（ステップＳ４５）。ここで、ノード管理部２１からの分割指示には、対象データ処理の対象となるデータのうちの当該対象データ処理において目標終了時刻までに処理できるデータのサイズが含まれる。
【０１５９】
この対象データ処理において目標終了時刻までに処理できるデータのサイズは、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている目標終了時刻情報によって示される対象データ処理の目標終了時刻、推定終了時刻情報によって示される対象データ処理の推定終了時刻および対象データ処理における単位処理量に基づいて算出される。
【０１６０】
具体的には、ノード管理部２１は、対象データ処理の目標終了時刻から推定終了時刻までの間に処理されるデータのサイズを対象データ処理における単位処理量を用いて算出し、当該算出されたサイズを対象データ処理の対象となるデータ全体のサイズから減算することによって、対象データ処理において目標終了時刻までに処理できるデータのサイズを算出できる。なお、対象データ処理の対象となるデータ全体のサイズは、当該対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている処理済情報から取得される。
【０１６１】
対象データ処理の対象となるデータの分割が指示されると、データ処理分割部２５は、当該分割指示に含まれる対象データ処理において目標終了時刻までに処理できるデータのサイズに基づいて、対象データ処理の対象となるデータ（対象データ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納されているデータ）を分割する（ステップＳ４６）。つまり、データ処理分割部２５は、対象データ処理の対象となるデータを、当該対象データ処理の目標終了時刻までに処理できるデータと当該目標終了時刻までに処理できないデータとに分割する。
【０１６２】
次に、ノード管理部２１は、データ処理分割部２５による分割後の後方のデータである対象データ処理の目標終了時刻までに処理できないデータ（ｒｅａｒデータ）を、中央管理装置１０に返却（送信）する（ステップＳ４７）。
【０１６３】
ここで、中央管理装置１０に返却されるデータには、当該データに対するデータ処理を識別するためのデータ処理ＩＤ、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理の優先レベルを示す優先レベル情報から構成されるヘッダ情報が付与される。なお、中央管理装置１０に返却されるデータに付与されるヘッダ情報を構成するデータ処理ＩＤは、対象データ処理を識別するためのデータ処理ＩＤおよび当該データがｒｅａｒデータであることを示す情報である「/rear」を含む。また、中央管理装置１０に返却されるデータに付与されるヘッダ情報を構成する目標終了時刻情報および優先レベル情報は、対象データ処理の対象となるデータ（つまり、対象データ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納されているデータ）に付与されているヘッダ情報を構成する目標終了時刻情報および優先レベル情報と同一である。換言すれば、中央管理装置１０に返却されるデータに付与されるヘッダ情報を構成する目標終了時刻情報および優先レベル情報は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている目標終了時刻および優先レベル情報と同一である。
【０１６４】
一方、データ処理分割部２５による分割後の前方のデータである対象データ処理の目標終了時刻までに処理できるデータ（ｆｒｏｎｔデータ）は、当該データに対するデータ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納される。なお、対象データ処理の目標終了時刻までに処理できるデータに対するデータ処理を識別するためのデータ処理ＩＤは、対象データ処理を識別するためのデータ処理ＩＤおよび当該データがｆｒｏｎｔデータであることを示す情報である「/front」を含む。また、実行情報格納部２６に格納されている対象データ処理を識別するためのデータ処理ＩＤは、対象データ処理の目標終了時刻までに処理できるデータに対するデータ処理を識別するためのデータ処理ＩＤに更新され、当該データ処理ＩＤに対応づけて実行情報格納部２６に格納されている推定終了時刻情報によって示される当該データ処理の推定終了時刻は、当該対象データ処理の目標終了時刻と同時刻に更新される。
【０１６５】
なお、上記したステップＳ４４において対象データ処理の対象となるデータの分割が必要でないと判定された場合には、ステップＳ４５およびＳ４６の処理は実行されず、ステップＳ４７の処理が実行される。この場合、対象データ処理の対象となるデータがそのまま返却される。対象データ処理の対象となるデータが返却されると、実行情報格納部２６に格納されている対象データ処理に関する実行情報は、当該実行情報格納部２６から削除される。
【０１６６】
次に、データ処理推定部２４は、実行情報格納部２６に格納されている処理順が後のデータ処理の推定終了時刻を算出する（ステップＳ４８）。ここでは、既存データ処理の推定終了時刻が算出される。この場合、データ処理推定部２４は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている推定終了時刻情報によって示される対象データ処理の推定終了時刻（ステップＳ４２において算出された対象データ処理の推定終了時刻）および既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている既存データ処理における単位処理量に基づいて、既存データ処理の推定終了時刻を算出する。
【０１６７】
具体的には、データ処理推定部２４は、既存データ処理の対象となるデータのうちの未処理のデータ（のサイズ）を当該既存データ処理における単位処理量で除算することによって当該既存データ処理の完了に必要な時間（推定処理時間）を算出し、当該推定処理時間を対象データ処理の推定終了時刻に加算することによって当該既存データ処理の推定終了時刻を算出する。
【０１６８】
なお、既存データ処理の対象となるデータのうちの未処理のデータのサイズは、既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている処理済情報に含まれる当該既存データ処理の対象となるデータのサイズと当該処理が完了したデータのサイズとの差により算出される。なお、処理済情報は、上記したように既存データ処理の実行が停止されるまで逐次更新されているものとする。
【０１６９】
上記したように既存データ処理の推定終了時刻が算出された場合、当該推定終了時刻を示す推定終了時刻情報は、既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される（上書きされる）。
【０１７０】
次に、ノード管理部２１は、処理順が後のデータ処理である既存データ処理の対象となるデータが当該既存データ処理の目標終了時刻から溢れるか否かを判定する（ステップＳ４９）。この場合、ノード管理部２１は、既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納された目標終了時刻情報によって示される既存データ処理の目標終了時刻および推定終了時刻情報によって示される既存データ処理の推定終了時刻に基づいて、既存データ処理が当該目標終了時刻以前に終了するか否かを判定する。つまり、ノード管理部２１は、既存データ処理が目標終了時刻以前に終了する場合には既存データ処理の対象となるデータが当該既存データ処理の目標終了時刻から溢れないと判定し、既存データ処理が目標終了時刻以前に終了しない場合には既存データ処理の対象となるデータが当該既存データ処理の目標終了時刻から溢れると判定する。
【０１７１】
既存データ処理（処理順が後のデータ処理）の対象となるデータが溢れると判定された場合（ステップＳ４９のＹＥＳ）、ノード管理部２１は、当該既存データ処理の対象となるデータの分割が必要であるか否かを判定する（ステップＳ５０）。
【０１７２】
具体的には、既存データ処理の目標終了時刻が上記した対象データ処理の推定終了時刻（つまり、既存データ処理の推定終了時刻を算出する際に基準とした時刻）以前であるような場合、または、既存データ処理の目標終了時刻は対象データ処理の推定終了時刻より後であるが、当該対象データ処理の推定終了時刻から当該既存データ処理の目標終了時刻までの間で当該既存データ処理における１単位（例えば、１ファイル）も処理できないような場合には、ノード管理部２１は、当該既存データ処理の対象となるデータの分割は必要でないと判定する。なお、これら以外の場合については、ノード管理部２１は、既存データ処理の対象となるデータの分割が必要であると判定する。
【０１７３】
既存データ処理の対象となるデータの分割が必要であると判定された場合（ステップＳ５０のＹＥＳ）、ノード管理部２１は、データ処理分割部２５に対して当該データの分割を指示する（ステップＳ５１）。ここで、ノード管理部２１からの分割指示には、既存データ処理の対象となるデータのうちの当該既存データ処理において目標終了時刻までに処理できるデータのサイズが含まれる。
【０１７４】
この既存データ処理において目標終了時刻までに処理できるデータのサイズは、既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている目標終了時刻情報によって示される既存データ処理の目標終了時刻、推定終了時刻情報によって示される既存データ処理の推定終了時刻および既存データ処理における単位処理量に基づいて算出される。
【０１７５】
具体的には、ノード管理部２１は、既存データ処理の目標終了時刻から推定終了時刻までの間に処理されるデータのサイズを対象データ処理における単位処理量を用いて算出し、当該算出されたサイズを既存データ処理の対象となるデータ全体のサイズから減算することによって、既存データ処理において目標終了時刻までに処理できるデータのサイズを算出できる。なお、既存データ処理の対象となるデータ全体のサイズは、当該既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている処理済情報から取得される。
【０１７６】
既存データ処理の対象となるデータの分割が指示されると、データ処理分割部２５は、当該分割指示に含まれる対象データ処理において目標終了時刻までに処理できるデータのサイズに基づいて、既存データ処理の対象となるデータ（既存データ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納されているデータ）を分割する（ステップＳ５２）。つまり、データ処理分割部２５は、既存データ処理の対象となるデータを、当該既存データ処理の目標終了時刻までに処理できるデータと当該目標終了時刻までに処理できないデータとに分割する。
【０１７７】
次に、ノード管理部２１は、データ処理分割部２５による分割後の後方のデータである既存データ処理の目標終了時刻までに処理できないデータ（ｒｅａｒデータ）を、中央管理装置１０に返却（送信）する（ステップＳ５３）。
【０１７８】
ここで、中央管理装置１０に返却されるデータには、当該データに対するデータ処理を識別するためのデータ処理ＩＤ、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理の優先レベルを示す優先レベル情報から構成されるヘッダ情報が付与される。なお、中央管理装置１０に返却されるデータに付与されるヘッダ情報を構成するデータ処理ＩＤは、既存データ処理を識別するためのデータ処理ＩＤおよび当該データがｒｅａｒデータであることを示す情報である「/rear」を含む。また、中央管理装置１０に返却されるデータに付与されるヘッダ情報を構成する目標終了時刻情報および優先レベル情報は、既存データ処理の対象となるデータ（つまり、既存データ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納されているデータ）に付与されているヘッダ情報を構成する目標終了時刻情報および優先レベル情報と同一である。換言すれば、中央管理装置１０に返却されるデータに付与されるヘッダ情報を構成する目標終了時刻情報および優先レベル情報は、既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納されている目標終了時刻および優先レベル情報と同一である。
【０１７９】
一方、データ処理分割部２５による分割後の前方のデータである既存データ処理の目標終了時刻までに処理できるデータ（ｆｒｏｎｔデータ）は、当該データに対するデータ処理を識別するためのデータ処理ＩＤに対応づけてノードデータ格納部２２に格納される。なお、既存データ処理の目標終了時刻までに処理できるデータに対するデータ処理を識別するためのデータ処理ＩＤは、既存データ処理を識別するためのデータ処理ＩＤおよび当該データがｆｒｏｎｔデータであることを示す情報である「/front」を含む。また、実行情報格納部２６に格納されている対象データ処理を識別するためのデータ処理ＩＤは、対象データ処理の目標終了時刻までに処理できるデータに対するデータ処理を識別するためのデータ処理ＩＤに更新され、当該データ処理ＩＤに対応づけて実行情報格納部２６に格納されている推定終了時刻情報によって示される当該データ処理の推定終了時刻は、当該既存データ処理の目標終了時刻と同時刻に更新される。
【０１８０】
なお、上記したステップＳ５０において既存データ処理の対象となるデータの分割が必要でないと判定された場合には、ステップＳ５１およびＳ５２の処理は実行されず、ステップＳ５３の処理が実行される。この場合、既存データ処理の対象となるデータがそのまま返却される。既存データ処理の対象となるデータが返却されると、実行情報格納部２６に格納されている既存データ処理に関する実行情報は、当該実行情報格納部２６から削除される。
【０１８１】
ここで、上記したように既存データ処理の実行は停止されたため、現在、対象ノード２０（に含まれるデータ処理実行部２３）においてはデータ処理が実行されていない。したがって、ノード管理部２１は、データ処理実行部２３に対してデータ処理の実行を指示する。
【０１８２】
データ処理実行部２３は、ノード管理部２１からの指示に応じて、データ処理を実行する（ステップＳ５４）。この場合、データ処理実行部２３は、実行情報格納部２６に格納されている処理順（上記したステップＳ４１において入れ替えられた処理順）に応じて、当該処理順に対応づけられているデータ処理ＩＤによって識別されるデータ処理を実行する。ここでは、データ処理実行部２３は、対象データ処理の目標終了時刻までに処理できるデータに対するデータ処理、既存データ処理の目標終了時刻までに処理できるデータに対するデータ処理の順番で、当該各データ処理を実行する。なお、対象データ処理の目標終了時刻までに処理できるデータに対するデータ処理および既存データ処理の目標終了時刻までに処理できるデータに対するデータ処理の実行に応じて、当該データ処理の各々の実行が開始された時刻（開始時刻）を示す開始時刻情報が当該データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される。このようにステップＳ５４の処理が実行されると、第２の処理は終了される。
【０１８３】
一方、上記したステップＳ３８において対象データ処理が目標終了時刻以前に終了すると判定された場合、第２の処理は終了される。なお、この場合において既存データ処理が存在しない場合には、第２の処理の終了の前に、対象データ処理の実行がデータ処理実行部２３によって開始される。このように対象データ処理が実行されると、当該対象データ処理の実行が開始された時刻（開始時刻）を示す開始時刻情報が当該対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される。
【０１８４】
また、ステップＳ３９において対象ノード２０において既存データ処理が存在しないと判定された場合、ノード管理部２１は、対象データ処理の対象となるデータの分割が必要であるか否かを判定する（ステップＳ５５）。
【０１８５】
具体的には、対象データ処理の目標終了時刻が上記したステップＳ３１においてデータが受信された時刻（つまり、対象データ処理の推定終了時刻を算出する際に基準とした時刻）以前であるような場合、または、対象データ処理の目標終了時刻は上記したステップＳ３１においてデータが受信された時刻より後であるが、当該データが受信された時刻か当該対象データ処理の目標終了時刻までの間で当該対象データ処理における１単位（例えば、１ファイル）も処理できないような場合には、ノード管理部２１は、当該対象データ処理の対象となるデータの分割は必要でないと判定する。なお、これら以外の場合については、ノード管理部２１は、対象データ処理の対象となるデータの分割が必要であると判定する。
【０１８６】
対象データ処理の対象となるデータの分割が必要であると判定された場合（ステップＳ５５のＹＥＳ）、ノード管理部２１は、上記したステップＳ４５〜Ｓ４７の処理と同様のステップＳ５６〜Ｓ５８の処理を実行する。なお、対象データ処理の対象となるデータの分割が必要でないと判定された場合（ステップＳ５５のＮＯ）、ステップＳ５６およびＳ５７の処理は実行されず、ステップＳ５８の処理が実行される。
【０１８７】
ここでは、上記したように対象ノード２０において既存データ処理が存在しないため、ノード管理部２１は、データ処理実行部２３に対して対象データ処理の実行を指示する。データ処理実行部２３は、ノード管理部２１からの指示に応じて、対象データ処理を実行する（ステップＳ５９）。なお、対象データ処理が実行されると、当該対象データ処理の実行が開始された時刻（開始時刻）を示す開始時刻情報が当該対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される。このようにステップＳ５９の処理が実行されると、第２の処理は終了される。
【０１８８】
一方、上記したステップＳ４３において対象データ処理の対象となるデータが溢れないと判定された場合、上記したステップＳ４８以降の処理が実行される。なお、この場合のステップＳ４９においては、対象データ処理を処理順が後のデータ処理として処理が実行される。
【０１８９】
ここで、図１４および図１５を参照して、分散データ処理システムにおいて実行される第２の処理の具体例について説明する。
【０１９０】
図１４は、分散データ処理システムにおいて第２の処理が実行される前の対象ノード２０に含まれる実行情報格納部２６のデータ構造の一例を示す。なお、実行情報格納部２６に格納されている情報については、上述した図４において説明した通りであるため、その詳しい説明を省略する。以下、図１４に示す実行情報格納部２６に格納されているデータ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理を既存データ処理とする。なお、対象ノード２０においては、実行情報格納部２６に格納されているデータ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理（つまり、既存データ処理）が実行されているものとする。
【０１９１】
ここでは、データ処理ＩＤ「data2_housedesign」によって識別されるデータ処理が対象ノード２０に振り分けられたものとして説明する。以下、データ処理ＩＤ「data2_housedesign」によって識別されるデータ処理を対象データ処理とする。
【０１９２】
この場合、ノード管理部２１は、中央管理装置１０によって送信された対象データ処理の対象となるデータを受信する。なお、ノード管理部２１によって受信されたデータには、データ処理ＩＤ「data2_housedesign」、目標終了時刻情報「２０１０／１／２１  ８：００」および優先レベル情報「３」から構成されるヘッダ情報が付与されているものとする。
【０１９３】
ノード管理部２１によって受信されたデータは、当該データに付与されているヘッダ情報を構成するデータ処理ＩＤ「data2_housedesign」に対応づけてノードデータ格納部２２に格納される。
【０１９４】
次に、ノード管理部２１は、対象データ処理の一部が割り込み可能であるか否かを判定する。図１４に示す実行情報格納部２６によれば既存データ処理が存在するが、当該データ処理の目標終了時刻と推定終了時刻との間には所定の間隔があるため、ノード管理部２１は、対象データ処理の一部が割り込み可能であると判定する。
【０１９５】
この場合、ノード管理部２１は、対象データ処理の一部の実行をデータ処理実行部２３に対して指示する。データ処理実行部２３は、ノード管理部２１からの指示に応じて、対象データ処理の一部を実行する。これにより、データ処理実行部２３は、対象データ処理の一部の実行の対象となったデータのサイズおよび当該対象データ処理の一部の実行に費やした時間（処理時間）を含む実行結果を取得する。データ処理実行部２３は、取得された実行結果をノード管理部２１に渡す。また、ノード管理部２１は、データ処理実行部２３から渡された実行結果をデータ処理推定部２４に渡す。
【０１９６】
データ処理推定部２４は、ノード管理部２１から渡された実行結果に含まれるデータサイズおよび処理時間に基づいて、対象データ処理における単位処理量を算出する。ここでは、対象データ処理における単位処理量として、例えば４ＫＢｙｔｅ／分が算出されたものとする。
【０１９７】
また、データ処理推定部２４は、算出された対象データ処理における単位処理量を用いて、対象データ処理の推定終了時刻を算出する。なお、対象データ処理の推定終了時刻は、図１４に示す実行情報格納部２６に格納されている推定終了時刻情報によって示される既存データ処理の推定終了時刻を基準として算出される。ここでは、対象データ処理の推定終了時刻として例えば「２０１０／１／２１  １９：００」が算出されたものとする。
【０１９８】
ここで、対象データ処理の処理順、対象データ処理を識別するためのデータ処理ＩＤ「data2_housedesign」、対象データ処理の目標終了時刻を示す目標終了時刻情報「２０１０／１／２１  ８：００」、対象データ処理の優先レベルを示す優先レベル情報「３」、データ処理推定部２４によって算出された対象データ処理の推定終了時刻を示す推定終了時刻情報「２０１０／１／２１  １９：００」、対象データ処理における単位処理量「４ＫＢｙｔｅ／分」および処理済情報が対応づけて実行情報格納部２６に格納される。なお、図１４に示すように既存データ処理の処理順が「１」であるため、対象データ処理の処理順としては「２」が格納される。また、対象データ処理は実行されていないため、例えば対象データ処理の対象となるデータのデータ量が２０ｆｉｌｅ、サイズが５０ＭＢｙｔｅである場合には、処理済情報としては例えば「０／２０ｆｉｌｅ：０／５０ＭＢｙｔｅ」が格納される。
【０１９９】
次に、ノード管理部２１は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納された目標終了時刻情報によって示される対象データ処理の目標終了時刻および推定終了時刻情報によって示される対象データ処理の推定終了時刻に基づいて、対象データ処理が目標終了時刻以前に終了するか否かを判定する。ここでは、対象データ処理の目標終了時刻「２０１０／１／２１  ８：００」が対象データ処理の推定終了時刻「２０１０／１／２１  １９：００」より前であるため、対象データ処理は目標終了時刻以前に終了しないと判定される。
【０２００】
また、上記したように図１４に示す実行情報格納部２６によれば既存データ処理に関する実行情報が格納されているため、対象ノード２０において既存データ処理が存在すると判定される。更に、上記したように対象データ処理の優先レベルは「４」であり、既存データ処理の優先レベルは「３」であるため、対象データ処理の優先レベルが既存データ処理の優先レベルより高いと判定される。
【０２０１】
この場合、ノード管理部２１は、対象データ処理の処理順と既存データ処理の処理順とを入れ替える。具体的には、実行情報格納部２６において、対象データ処理の処理順が「１」とされ、既存データ処理の処理順が「２」とされる。
【０２０２】
次に、データ処理推定部２４は、処理順が前のデータ処理（処理順が「１」のデータ処理）である対象データ処理の推定終了時刻を再推定する。この場合、既存データ処理の実行が停止される。データ処理推定部２４は、既存データ処理の実行が停止された時刻を基準として、実行情報格納部２６に格納されている対象データ処理における単位処理量を用いて当該対象データ処理の推定終了時刻を算出する。ここでは、対象データ処理の推定終了時刻として例えば「２０１０／１／２１  ８：００」が算出されたものとする。データ処理推定部２４によって算出された対象データ処理の推定終了時刻を示す推定終了時刻情報は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される（上書きされる）。
【０２０３】
ノード管理部２１は、対象データ処理（処理順が前のデータ処理）の対象となるデータが当該対象データ処理の目標終了時刻から溢れるか否かを判定する。ここでは、対象データ処理の目標終了時刻は「２０１０／１／２１  ８：００」であり、対象データ処理の推定終了時刻は「２０１０／１／２１  ８：００」である。したがって、対象データ処理の対象となるデータが対象データ処理の目標終了時刻から溢れない（つまり、対象データ処理は目標終了時刻までに完了できる）と判定される。
【０２０４】
次に、データ処理推定部２４は、処理順が後のデータ処理（処理順が「２」のデータ処理）である既存データ処理の推定終了時刻を再推定する。この場合、データ処理推定部２４は、実行情報格納部２６を参照して、既存データ処理の推定終了時刻を算出する。この場合、データ処理推定部２４は、対象データ処理の推定終了時刻を基準として、既存データ処理における単位処理量を用いて当該既存データ処理の推定終了時刻を算出する。ここでは、既存データ処理の推定終了時刻として例えば「２０１０／１／２１  １８：００」が算出されたものとする。データ処理推定部２４によって算出された既存データ処理の推定終了時刻を示す推定終了時刻情報は、既存データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される（上書きされる）。
【０２０５】
ノード管理部２１は、既存データ処理（処理順が後のデータ処理）の対象となるデータが当該既存データ処理の目標終了時刻から溢れるか否かを判定する。ここでは、既存データ処理の目標終了時刻は「２０１０／１／２１  １５：００」であり、既存データ処理の推定終了時刻は「２０１０／１／２１  １８：００」である。したがって、既存データ処理の対象となるデータが既存データ処理の目標終了時刻から溢れる（つまり、既存データ処理は目標終了時刻までに完了できない）と判定される。
【０２０６】
この場合、ノード管理部２１は、既存データ処理の対象となるデータの分割が必要であるか否かを判定する。ここでは、上記したように既存データ処理の目標終了時刻と当該既存データ処理の推定終了時刻を算出する際に基準とした時刻（ここでは、対象データ処理の推定終了時刻）との関係から、既存データ処理の対象となるデータの分割が必要であると判定される。
【０２０７】
次に、ノード管理部２１は、データ処理分割部２５に対して既存データ処理の対象となるデータの分割を指示する。このデータ処理分割部２５に対する分割指示には、既存データ処理の対象となるデータのうちの当該既存データ処理において目標終了時刻までに処理できるデータのサイズが含まれる。
【０２０８】
データ処理分割部２５は、ノード管理部２１からの分割指示に含まれる既存データ処理において目標終了時刻までに処理できるデータのサイズに基づいて、既存データ処理の対象となるデータを分割する。つまり、既存データ処理の対象となるデータは、既存データ処理の目標終了時刻までに処理できるデータと当該目標終了時刻までに処理できないデータとに分割される。
【０２０９】
ノード管理部２１は、データ処理分割部２５による分割後の後方のデータである既存データ処理の目標終了時刻までに処理できないデータ（ｒｅａｒデータ）を中央管理装置１０に返却する。中央管理装置１０に返却されるデータには、当該データに対するデータ処理を識別するためのデータ処理ＩＤ「data1_pai/rear/rear」、当該データ処理の目標終了時刻を示す目標終了時刻情報「２０１０／１／２１  １５：００」および当該データ処理の優先レベルを示す優先レベル情報「３」から構成されるヘッダ情報付与される。なお、このデータ処理ＩＤ「data1_pai/rear/rear」は、既存データ処理を識別するためのデータ処理ＩＤ「data1_pai/rear」およびｒｅａｒデータであることを示す情報である「/rear」から構成されている。また、目標終了時刻情報「２０１０／１／２１  １５：００」および優先レベル情報「３」は、既存データ処理の目標終了時刻を示す目標終了時刻情報および当該既存データ処理の優先レベルを示す優先レベル情報と同一である。
【０２１０】
また、ノード管理部２１は、データ処理分割部２５による分割後の前方のデータである既存データ処理の目標終了時刻までに処理できるデータ（ｆｒｏｎｔデータ）を当該データに対するデータ処理を識別するためのデータ処理ＩＤ「data1_pai/rear/front」に対応づけてノードデータ格納部２２に格納する。なお、このデータ処理ＩＤ「data1_pai/rear/front」は、既存データ処理を識別するためのデータ処理ＩＤ「data1_pai/rear」およびｆｒｏｎｔデータであることを示す情報である「/front」から構成されている。また、ノード管理部２１は、実行情報格納部２６に格納されている既存データ処理を識別するためのデータ処理ＩＤ「data1_pai/rear」を既存データ処理の目標終了時刻までに処理できるデータに対するデータ処理を識別するためのデータ処理ＩＤ「data1_pai/rear/front」に更新する。更に、ノード管理部２１は、このデータ処理ＩＤ「data1_pai/rear/front」に対応づけて実行情報格納部２６に格納されている推定終了時刻情報によって示される推定終了時刻を既存データ処理の目標終了時刻と同時刻に更新する。なお、図１５は、上記したような処理が実行されることによって更新された実行情報格納部２６のデータ構造の一例を示す。
【０２１１】
ここで、上記したように既存データ処理の実行は停止されているため、現在、対象ノード２０においては、データ処理が実行されていない。したがって、ノード管理部２１は、実行情報格納部２６を参照して、データ処理実行部２３に対してデータ処理の実行を指示する。
【０２１２】
この場合、データ処理実行部２３は、ノード管理部２１からの指示に応じて、処理順「１」に対応づけて図１５に示す実行情報格納部２６に格納されているデータ処理ＩＤ「data2_housedesign」によって識別されるデータ処理（対象データ処理）を実行し、当該データ処理が完了した後に処理順「２」に対応づけて実行情報格納部２６に格納されている「data1_pai/rear/front」によって識別されるデータ処理（既存データ処理の対象となるデータのうちの目標終了時刻までに処理できるデータに対するデータ処理）を実行する。
【０２１３】
このように分散データ処理システム（を構成する対象ノード２０）において第２の処理が実行されることによって、データ処理の優先レベルを考慮した上で、各データ処理の目標終了時刻を満たすように適切にデータ処理を実行することができる。
【０２１４】
次に、図１６のフローチャートを参照して、本実施形態に係る分散データ処理システムにおいて実行される第３の処理の処理手順について説明する。第３の処理は、ノード２０から溢れて返却されたデータに対するデータ処理を振り分ける際の処理である。この第２の処理は、中央管理装置１０によって実行される。
【０２１５】
中央管理装置に含まれる振り分け判定部１３は、ノード２０から返却されたデータを受信する（ステップＳ６１）。ノード２０から返却されたデータには、当該データに対するデータ処理を識別するためのデータ処理ＩＤ、当該データ処理の目標終了時刻を示す目標終了時刻情報および当該データ処理の優先レベルを示す優先レベル情報から構成されるヘッダ情報が付与されている。
【０２１６】
なお、ノード２０から返却されたデータとは、当該ノード２０において目標終了時刻までにデータ処理を完了することができずに当該目標終了時刻から溢れたデータである。
【０２１７】
以下、第３の処理において、振り分け判定部１３によって受信されたデータ（ノード２０から返却されたデータ）に対するデータ処理を振り分け対象データ処理と称する。
【０２１８】
分散データ処理システムにおいて実行される第３の処理においては、ステップＳ６１の処理が実行されると、上述した図７に示すステップＳ１４〜Ｓ２０の処理に相当するステップＳ６２〜ステップＳ６８の処理が実行される。ステップＳ６８の処理が実行されると、分散データ処理システムにおいて実行される第３の処理は終了される。
【０２１９】
なお、ステップＳ６７において振り分け先ノードに対して振り分け対象データ処理が振り分けられる場合、振り分け処理部１４は、振り分け判定部１３によって受信されたデータ（ステップＳ６１において受信されたデータ）を当該振り分け先ノードに対して送信する。
【０２２０】
また、ステップＳ６８においては、振り分け判定部１３によって受信されたデータに付与されているヘッダ情報を構成するデータ処理ＩＤ（振り分け対象データ処理を識別するためのデータ処理ＩＤ）、目標終了時刻情報、優先レベル情報が対応づけて振り分け情報格納部１２に格納される。更に、振り分け対象データ処理を識別するためのデータ処理ＩＤに対応づけて、振り分け対象データ処理が振り分け判定部１３によって決定されたノード２０に振り分けられた時刻を示す振り分け時刻情報、当該ノード２０（振り分け先ノード）を示す振り分け先ノード情報、当該振り分け対象データ処理の対象となるデータがノード２０から溢れて返却されたものであること（つまり、振り分け判定部１３によって受信されたこと）を示す新規／返却状況情報「返却」および振り分け対象データ処理が完了していないことを示す処理状況情報「未」が振り分け情報格納部１２に格納される。
【０２２１】
なお、ステップＳ６２においてデータ処理を実行していないノード２０があると判定された場合、当該ノード２０を振り分け先ノードとして、ステップＳ６７およびＳ６８の処理が実行される。
【０２２２】
また、ステップＳ６５において、振り分け判定部１３によって特定されたノード２０が複数存在しないと判定された（つまり、１つのノード２０が特定された）場合、当該振り分け判定部１３によって特定されたノード２０を振り分け先ノードとして、ステップＳ６７およびＳ６８の処理が実行される。
【０２２３】
次に、図１７のフローチャートを参照して、本実施形態に係る分散データ処理システムにおいて実行される第４の処理の処理手順について説明する。第４の処理は、データ処理の結果を中央管理装置１０に送信する際の処理である。この第４の処理は、データ処理を振り分けられたノード２０によって実行される。
【０２２４】
ノード２０に含まれるデータ処理実行部２３は、データ処理の実行が完了した場合、その旨をノード管理部２１に通知する（ステップＳ７１）。この際、データ処理実行部２３は、データ処理の結果（以下、データ処理結果と表記）をノード管理部２１に渡す。
【０２２５】
ノード管理部２１は、データ処理実行部２３からの通知を受けると、データ処理実行部２３によるデータ処理の実行の完了（終了）に伴って実行情報格納部２６（の内容）を更新する（ステップＳ７２）。
【０２２６】
この場合、ノード管理部２１は、データ処理実行部２３によって実行が完了されたデータ処理に関する実行情報を実行情報格納部２６から削除する。つまり、ノード管理部２１は、データ処理実行部２３によって実行が完了されたデータ処理を識別するためのデータ処理ＩＤおよび当該データ処理ＩＤに対応づけられている情報を実行情報格納部２６から削除する。また、ノード管理部２１は、データ処理実行部２３によって実行が完了されたデータ処理の実行情報の削除に応じて、他のデータ処理の処理順を繰り上げる。更に、処理順が繰り上げられたデータ処理の実行がデータ処理実行部２３によって開始された場合には、当該データ処理の実行の開始時刻を示す開始時刻情報が当該データ処理を識別するためのデータ処理ＩＤに対応づけて実行情報格納部２６に格納される。
【０２２７】
例えば上述した図１５に示す実行情報格納部２６に格納されているデータ処理ＩＤ「data2_housedesign」によって識別されるデータ処理の実行がデータ処理実行部２３によって完了された場合には、当該データ処理に関する実行情報が実行情報格納部２６から削除され、データ処理ＩＤ「data1_pai/rear/front」に対応づけられている処理順が「２」から「１」に繰り上げられる。また、データ処理ＩＤ「data1_pai/rear/front」によって識別されるデータ処理の実行が開始された場合には、当該開始時刻を示す開始時刻情報が当該データ処理ＩＤ「data1_pai/rear/front」に対応づけて実行情報格納部２６に格納される。
【０２２８】
次に、ノード管理部２１は、データ処理実行部２３から渡されたデータ処理結果および当該データ処理を識別するためのデータ処理ＩＤを中央管理装置１０に対して送信する（ステップＳ７３）。
【０２２９】
次に、図１８のフローチャートを参照して、本実施形態に係る分散データ処理システムにおいて実行される第５の処理の処理手順について説明する。第５の処理は、ノード２０によって実行されたデータ処理の結果を出力する処理である。この第５の処理は、中央管理装置１０によって実行される。
【０２３０】
中央管理装置１０に含まれる中央結果処理部１５は、ノード２０によって実行されたデータ処理の結果（データ処理結果）および当該データ処理を識別するためのデータ処理ＩＤを、当該ノード２０から受信する（ステップＳ８１）。ここでは、中央結果処理部１５によって受信されたデータ処理ＩＤによって識別されるデータ処理を対象データ処理と称する。
【０２３１】
中央結果処理部１５は、受信されたデータ処理ＩＤおよびデータ処理結果を対応づけて処理結果格納部１６に格納する（ステップＳ８２）。
【０２３２】
次に、中央結果処理部１５は、対象データ処理の対象となるデータが分割されている（つまり、分割後のデータである）か否かを判定する（ステップＳ８３）。ここでは、中央結果処理部１５は、受信されたデータ処理ＩＤの後方に「/front」または「/rear」が含まれている場合に、対象データ処理の対象となるデータが分割されていると判定する。
【０２３３】
対象データ処理の対象となるデータが分割されていると判定された場合（ステップＳ８３のＹＥＳ）、中央結果処理部１５は、当該分割後の他方のデータに対するデータ処理（以下、単に他方のデータ処理と表記）が完了しているか否かを判定する（ステップＳ８４）。
【０２３４】
この場合、中央結果処理部１５によって受信されたデータ処理ＩＤに対応するデータ処理ＩＤ（以下、対応データ処理ＩＤと表記）が処理結果格納部１６に格納されているか否かによって判定処理を実行する。なお、対応データ処理ＩＤとは、中央結果処理部１５によって受信されたデータ処理ＩＤの後方に例えば「/front」が含まれている場合には、当該「/front」に代えて当該データ処理ＩＤの後方に「/rear」が含まれているデータ処理ＩＤである。一方、中央結果処理部１５によって受信されたデータ処理ＩＤの後方に例えば「/rear」が含まれている場合には、当該「/rear」に代えて当該データ処理ＩＤの後方に「/front」が含まれているデータ処理ＩＤである。
【０２３５】
つまり、ステップＳ８４においては、中央結果処理部１５によって受信されたデータ処理ＩＤの対応データ処理ＩＤが処理結果格納部１６に格納されている場合には、他方のデータ処理が完了していると判定される。一方、中央結果処理部１５によって受信されたデータ処理ＩＤの対応データ処理ＩＤが処理結果格納部１６に格納されている場合には、他方のデータ処理が完了していると判定される。
【０２３６】
他方のデータ処理が完了していると判定された場合（ステップＳ８４のＹＥＳ）、中央結果処理部１５は、振り分け情報格納部１２を参照して、対象データ処理および親データ処理の処理状況（情報）を更新する（ステップＳ８５）。ここで、親データ処理とは、対象データ処理を識別するためのデータ処理ＩＤ（つまり、中央結果処理部１５によって受信されたデータ処理ＩＤ）の後方に含まれる「/front」または「/rear」を除いたデータ処理ＩＤによって識別されるデータ処理である。換言すれば、親データ処理とは、対象データ処理の対象となるデータに分割される前のデータ（親データ）に対するデータ処理である。
【０２３７】
この場合、中央結果処理部１５は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて振り分け情報格納部１２に格納されている処理状況情報を「完了」に更新する。また、中央結果処理部１５は、親データ処理を識別するためのデータ処理ＩＤに対応づけて振り分け情報格納部１２に格納されている処理状況情報を「完了」に更新する。
【０２３８】
なお、処理状況情報が「完了」に更新された親データ処理の対象となるデータが例えば分割後のデータである（つまり、分割されている）場合には、当該親データ処理に対して上記したステップＳ８４の処理に相当する処理が実行されるものとする。この処理によって、親データ処理に対する他方のデータ処理（分割後の他方のデータに対するデータ処理）が完了していると判定された場合には、当該親データ処理の親データ処理の処理状況情報についても「完了」に更新される。一方、親データ処理に対する他方のデータ処理が完了していないと判定された場合には、ステップＳ８６の処理が実行される。
【０２３９】
次に、中央結果処理部１５は、振り分け情報格納部１２を参照して、外部から入力されたデータに対するデータ処理（以下、外部入力データ処理と表記）が完了しているか否かを判定する（ステップＳ８６）。具体的には、中央結果処理部１５は、外部入力データ処理を識別するためのデータ処理ＩＤに対応づけて振り分け情報格納部１２に格納されている処理状況情報が「完了」であるか否かを判定する。
【０２４０】
ここで、外部入力データ処理とは、「/front」および「/rear」が含まれていないデータ処理ＩＤであって、新規／返却状況情報「新規」に対応づけて振り分け情報格納部１２に格納されているデータ処理ＩＤによって識別されるデータ処理である。
【０２４１】
外部入力データ処理が完了していると判定された場合（ステップＳ８６のＹＥＳ）、中央結果処理部１５は、当該外部入力データ処理に関するデータ処理結果を処理結果格納部１６から取得する（ステップＳ８７）。なお、外部入力データ処理を識別するためのデータ処理ＩＤが処理結果格納部１６に格納されている場合には、当該データ処理ＩＤに対応づけて処理結果格納部１６に格納されているデータ処理結果（つまり、外部入力データ処理のデータ処理結果）が取得される。一方、外部入力データ処理を識別するためのデータ処理ＩＤが処理結果格納部１６に格納されていない場合には、当該外部入力データ処理に関連するデータ処理（以下、外部入力データ処理の関連データ処理と表記）を識別するためのデータ処理ＩＤに対応づけて処理結果格納部１６に格納されているデータ処理結果（つまり、外部入力データ処理の関連データ処理のデータ処理結果）の全てが取得される。
【０２４２】
なお、外部入力データ処理の関連データ処理とは、外部入力データ処理の目標終了時刻から溢れてノード２０から返却されたデータ（つまり、外部入力データ処理の対象となるデータの分割後のデータ）に対するデータ処理である。つまり、外部乳旅行データ処理の関連データ処理とは、当該外部入力データ処理を識別するためのデータ処理ＩＤの後方に「/front」または「/rear」が含まれているデータ処理ＩＤによって識別されるデータ処理である。
【０２４３】
次に、中央結果処理部１５は、外部入力データ処理の最終結果を外部に出力する（ステップＳ８８）。上記したステップＳ８７において外部入力データ処理のデータ処理結果が取得された場合には、中央結果処理部１５は、当該外部入力データ処理のデータ処理結果を最終結果として出力する。一方、ステップＳ８７において外部入力データ処理の関連データ処理のデータ処理結果の全てが取得された場合には、中央結果処理部１５は、当該データ処理結果の全てを集約した結果（最終結果）を出力する。
【０２４４】
なお、ステップＳ８８の処理が実行されると、外部入力データ処理を識別するためのデータ処理ＩＤおよび当該データ処理ＩＤに対応づけられている情報は、振り分け情報格納部１２および処理結果格納部１６から削除される。同様に、外部入力データ処理の関連データ処理を識別するためのデータ処理ＩＤおよび当該データ処理ＩＤに対応づけられている情報についても、振り分け情報格納部１２および処理結果格納部１６から削除される。
【０２４５】
一方、外部入力データ処理が完了していないと判定された場合（ステップＳ８６のＮＯ）、ステップＳ８７およびＳ８８の処理は実行されない。
【０２４６】
また、ステップＳ８３において対象データ処理の対象となるデータが分割されていないと判定された場合、およびステップＳ８４において他方のデータ処理が完了していないと判定された場合、中央結果処理部１５は、振り分け情報格納１２を参照して、対象データ処理の処理状況を更新する（ステップＳ８９）。
【０２４７】
この場合、中央結果処理部１５は、対象データ処理を識別するためのデータ処理ＩＤに対応づけて振り分け情報格納部１２に格納されている処理状況情報を「完了」に更新する。なお、ステップＳ８３において対象データ処理の対象となるデータが分割されていないと判定された場合であって、対象データ処理を識別するためのデータ処理ＩＤが新規／返却状況情報「返却」に対応づけられている場合、つまり、対象データ処理の対象となるデータが分割されずにノード２０から返却されたデータである場合には、当該対象データ処理を識別するためのデータ処理ＩＤおよび新規／返却状況情報「新規」に対応づけて振り分け情報格納部１２に格納されている処理状況情報についても「完了」に更新されるものとする。
【０２４８】
上記したステップＳ８９の処理が実行されると、上記したステップＳ８６以降の処理が実行される。
【０２４９】
ここで、図１９および図２０を参照して、分散データ処理システムにおいて実行される第５の処理の具体例について説明する。
【０２５０】
図１９は、分散データ処理システムにおいて第５の処理が実行される前の中央管理装置１０に含まれる処理結果格納部１６のデータ構造の一例を示す。図１９に示す例では、処理結果格納部１６には、データ処理ＩＤ「data1_pai/front」およびデータ処理結果「データ処理結果１ｆ」が対応づけて格納されている。
【０２５１】
なお、中央管理装置１０に含まれる振り分け情報格納部１２は、上述した図８に示すデータ構造を有するものとする。また、分散データ処理システムを構成する複数のノード２０としてノード１〜３の３つのノードが存在するものとする。
【０２５２】
以下、データ処理ＩＤ「data1_pai/rear」および当該データ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理のデータ処理結果「データ処理結果１ｒ」がノード３から送信された場合について具体的に説明する。
【０２５３】
まず、分散データ処理システムにおいて実行される第５の処理では、中央管理装置１０に含まれる中央結果処理部１５は、ノード３によって送信されたデータ処理ＩＤ「data1_pai/rear」およびデータ処理結果「データ処理結果１ｒ」を受信する。
【０２５４】
中央結果処理部１５は、受信されたデータ処理ＩＤ「data1_pai/rear」およびデータ処理結果「データ処理結果１ｒ」を対応づけて処理結果格納部１６に格納する。なお、図２０は、データ処理ＩＤ「data1_pai/rear」およびデータ処理結果「データ処理結果１ｒ」が格納された後の処理結果格納部１６のデータ構造を示す。
【０２５５】
次に、中央結果処理部１５は、受信されたデータ処理ＩＤ「data1_pai/rear」によって識別されるデータ処理（以下、対象データ処理と表記）の対象となるデータが分割されている（分割後のデータである）か否かを判定する。ここで、中央結果処理部１５によって受信されたデータ処理ＩＤ「data1_pai/rear」には後方に「/rear」が含まれているため、対象データ処理の対象となるデータはｒｅａｒデータ（つまり、分割後の後方のデータ）である。したがって、中央結果処理部１５は、対象データ処理の対象となるデータが分割されていると判定する。
【０２５６】
対象データ処理の対象となるデータが分割されていると判定された場合、中央結果処理部１５は、他方のデータ処理（ここでは、データ処理ＩＤ「data1_pai/front」によって識別されるデータ処理）が完了しているか否かを判定する。
【０２５７】
この場合、図２０に示す処理結果格納部１６にはデータ処理ＩＤ「data1_pai/front」が格納されているため、中央結果処理部１５は、他方のデータ処理が完了していると判定する。
【０２５８】
他方のデータ処理が完了していると判定された場合、中央結果処理部１５は、振り分け情報格納部１２において、対象データ処理および親データ処理の処理状況を更新する。なお、対象データ処理を識別するためのデータ処理ＩＤが「data1_pai/rear」である場合における親データ処理は、データ処理ＩＤ「data1_pai」によって識別されるデータ処理である。
【０２５９】
ここでは、中央結果処理部１５は、対象データ処理を識別するためのデータ処理ＩＤ「data1_pai/rear」に対応づけて振り分け情報格納部１２に格納されている処理状況情報を「完了」に更新する。また、中央結果処理部１５は、親データ処理を識別するためのデータ処理ＩＤ「data1_pai」に対応づけて振り分け情報格納部８１２に格納されている処理状況情報を「完了」に更新する。なお、図２１は、対象データ処理および親データ処理の処理状況が更新された後の振り分け情報格納部１２のデータ構造の一例を示す。
【０２６０】
次に、中央結果処理部１５は、振り分け情報格納部１２を参照して、外部入力データ処理が完了しているか否かを判定する。ここで、図２１に示す振り分け情報格納部１２に格納されている例えばデータ処理ＩＤ「data1_pai」によって識別されるデータ処理は、「/front」および「/rear」が含まれていないデータ処理ＩＤであって新規／返却状況情報「新規」に対応づけられているデータ処理ＩＤによって識別されるデータ処理であるため、外部入力データ処理である。このデータ処理ＩＤ「data1_pai」に対応づけて振り分け情報格納部１２に格納されている処理状況情報は「完了」であるため、当該データ処理ＩＤ「data1_pai」によって識別される外部入力データ処理は完了していると判定される。
【０２６１】
この場合、中央結果処理部１５は、外部入力データ処理に冠するデータ処理結果を処理結果格納部１６から取得する。ここで、図２０に示す処理結果格納部１６には外部入力データ処理を識別するためのデータ処理ＩＤ「data1_pai」は格納されていないため、当該外部入力データ処理の関連データ処理を識別するためのデータ処理ＩＤ「data1_pai/front」および「data1_pai/rear」に対応づけて処理結果格納部１６に格納されているデータ処理結果「データ処理結果１ｆ」および「データ処理結果１ｒ」を取得する。
【０２６２】
次に、中央結果処理部１５は、データ処理ＩＤ「data1_pai」によって識別される外部入力データ処理の最終結果として、取得されたデータ処理結果「データ処理結果１ｆ」および「データ処理結果１ｒ」を集約した結果を外部に出力する。
【０２６３】
上記したように本実施形態において、分散データ処理システムを構成する中央管理装置１０は、振り分け情報格納部１２に格納されている振り分け先ノード情報に基づいてデータ処理が振り分けられていないノードが存在するか否かを判定し、データ処理が振り分けられていないノードが存在しないと判定された場合に、ノード毎に最も遅い目標終了時刻を抽出し、当該ノード毎に抽出された目標終了時刻の中で最も早い目標終了時刻が抽出されたノードを特定し、ノードに振り分けられていないデータ処理を当該特定されたノードに振り分ける。
【０２６４】
また、本実施形態において、分散データ処理システム構成する複数のノード２０のうちのデータ処理が振り分けられたノード２０は、当該ノード２０に振り分けられたデータ処理および当該ノード２０において実行されている他のデータ処理の処理順を優先レベルに基づいて入れ替え、当該データ処理の対象となるデータを当該データ処理の目標終了時刻までに処理できるデータおよび当該データ処理の目標終了時刻までに処理できないデータに分割し、当該分割された後の後方のデータ（つまり、目標終了時刻までに処理できないデータ）を中央管理装置１０に返却する。
【０２６５】
また、本実施形態において、中央管理装置１０は、ノード２０から返却されたデータを再び当該データを返却したノード２０以外のノード２０に振り分ける。
【０２６６】
また、本実施形態において、中央管理装置１０は、例えば外部入力データ処理の対象となるデータが分割されている場合には、当該分割されたデータに対するデータ処理の全てが各ノード２０で完了した場合に、当該データ処理結果を集約した結果を当該外部入力データ処理の最終結果として出力する。
【０２６７】
したがって、本実施形態においては、複数のノード２０の性能等を把握することなく、適切なスケジューリング（データ処理の振り分け）を行うことが可能となる。これにより、本実施形態においては、データ処理を複数のノード２０に振り分ける際の通信処理コストを低減することができる。更に、本実施形態においては、各データ処理の優先レベルを考慮した上で、目標終了時刻を満たした再スケジューリングを行うことが可能となる。
【０２６８】
なお、本実施形態においては、上記した第２の処理でデータ処理の目標終了時刻からデータが溢れる場合に当該データ処理の対象となるデータが分割されるものとして説明したが、例えば目標終了時刻の所定時間前にデータ処理を完了できないような場合には、当該データ処理の対象となるデータを強制的に分割するような構成であっても構わない。
【０２６９】
また、本願発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。更に、異なる実施形態に亘る構成要素を適宜組合せてもよい。  
【符号の説明】
【０２７０】
１０…中央管理装置、１１…ヘッダ情報付与部、１２…振り分け情報格納部、１３…振り分け判定部、１４…振り分け処理部、１５…中央結果処理部、１６…処理結果格納部、２０…ノード、２１…ノード管理部、２２…ノードデータ格納部、２３…データ処理実行部、２４…データ処理推定部、２５…データ処理分割部、２６…実行情報格納部。
【図１】
0005459675.tif 000002
【図２】
0005459675.tif 000003
【図３】
0005459675.tif 000004
【図４】
0005459675.tif 000005
【図５】
0005459675.tif 000006
【図６】
0005459675.tif 000007
【図７】
0005459675.tif 000008
【図８】
0005459675.tif 000009
【図９】
0005459675.tif 000010
【図１０】
0005459675.tif 000011
【図１１】
0005459675.tif 000012
【図１２】
0005459675.tif 000013
【図１３】
0005459675.tif 000014
【図１４】
0005459675.tif 000015
【図１５】
0005459675.tif 000016
【図１６】
0005459675.tif 000017
【図１７】
0005459675.tif 000018
【図１８】
0005459675.tif 000019
【図１９】
0005459675.tif 000020
【図２０】
0005459675.tif 000021
【図２１】
0005459675.tif 000022