(57)【特許請求の範囲】
【請求項１】
複数の記憶領域を有する記憶部と、
タスクの内容が示されるタスク情報の格納先を、前記複数の記憶領域の中から選択し、選択した記憶領域にタスク情報を格納するタスク情報格納部と、
単位時間の経過ごとに繰り返し到来するタスク情報の読み出しタイミングが到来する度に、選択する記憶領域を読み出しタイミングごとに変化させて、前記複数の記憶領域の中からタスク情報の読み出し対象の記憶領域を選択し、選択した記憶領域に格納されているタスク情報を読み出し、読み出したタスク情報に示されるタスクを実行リソースに実行させるタスク管理部とを有し、
前記記憶部は、
全ての読み出しタイミングにおいて読み出し対象の記憶領域として選択される１つの優先記憶領域と、優先記憶領域以外の２つ以上の通常記憶領域とに区分され、
それぞれの通常記憶領域には、読み出し対象の記憶領域として選択される順序として、読み出し順位が指定され、
優先記憶領域には、現在時刻から、次の読み出しタイミングの時刻までの時間帯が指定され、
第１位の読み出し順位が指定されている記憶領域には、次の読み出しタイミングの時刻から、次の読み出しタイミングの時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
第２位以降の読み出し順位の記憶領域には、１つ上位の読み出し順位の記憶領域に指定されている時間帯の終期に後続する時刻から、当該時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
前記タスク情報格納部は、
タスクごとに、実行リソースにおいてタスクの実行を開始することが可能な時刻を実行開始可能時刻として予測し、予測した実行開始可能時刻を包含する時間帯が指定されている記憶領域を格納先として選択し、選択した記憶領域にタスク情報を格納し、
前記タスク管理部は、
読み出しタイミングが到来する度に、
優先記憶領域と第１位の読み出し順位が指定されている通常記憶領域を読み出し対象の記憶領域として選択し、第１位の読み出し順位が指定されている通常記憶領域に格納されているタスク情報を優先記憶領域に移動させ、
最下位の読み出し順位の通常記憶領域に指定されている時間帯の終期に後続する時刻から、当該時刻に前記単位時間を加えて得られる時刻までの時間帯を第１位の読み出し順位の通常記憶領域の新たな時間帯として指定し、第１位の読み出し順位が指定されている通常記憶領域の順位を最下位の読み出し順位にするとともに、第２位以降の読み出し順位の記憶領域の順位をそれぞれ１つずつ繰り上げ、それぞれの通常記憶領域に対して新たな読み出し順位を指定し、
通常記憶領域から移動させたタスク情報を含む、優先記憶領域に格納されているタスク情報を読み出し、読み出したタスク情報に示されるタスクを実行リソースに実行させることを特徴とする情報処理装置。
【請求項２】
前記タスク情報格納部は、
タスクを実行させる実行リソースとして複数の実行リソースのうちのいずれかの実行リソースが示されるタスク情報の格納先を、タスク情報に示されている実行リソースと無関係に、前記複数の記憶領域の中から選択し、選択した記憶領域にタスク情報を格納し、
前記タスク管理部は、
選択した記憶領域に格納されているタスク情報を順次読み出し、読み出したタスク情報ごとに、タスク情報に示されるタスクを、タスク情報に示される実行リソースに実行させることを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記タスク情報格納部は、
早期に実行リソースに実行させるタスクのタスク情報ほど、上位の読み出し順位が指定されている記憶領域に格納することを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記情報処理装置は、更に、
実行リソースが１つのタスクを実行する際に要する平均時間を平均タスク実行時間として示し、実行リソースにより実行済みのタスクの数を実行済みタスク数として示し、実行リソースによる実行待ちのタスクの数を実行待ちタスク数として示す実行リソース管理テーブルを保持する実行リソース管理テーブル保持部を有し、
前記タスク情報格納部は、
実行リソースに実行させるタスクごとに、前記リソース管理テーブルに示される平均タスク実行時間と実行待ちタスク数とを用いて実行開始可能時刻を予測し、予測した実行開始可能時刻を包含する時間帯が指定されている記憶領域をタスク情報の格納先として選択し、
前記タスク管理部は、
読み出しタイミングが到来する度に、
優先記憶領域からタスク情報を読み出し、更に、読み出したタスク情報に示されるタスクを実行リソースに実行させた後に、
実行リソースに実行させたタスクの実行時間と、前記リソース管理テーブルに示される平均タスク実行時間と実行済みタスク数とに基づき、平均タスク実行時間を更新し、
更新後の平均タスク実行時間を前記実行リソース管理テーブルに反映させることを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記タスク情報格納部は、
タスク情報を記憶領域に格納する度に、前記リソース管理テーブルの実行待ちタスク数を増加させ、
前記タスク管理部は、
実行リソースにタスクを実行させる度に、前記リソース管理テーブルの実行待ちタスク数を減少させ、実行済みタスク数を増加させることを特徴とする請求項４に記載の情報処理装置。
【請求項６】
複数の記憶領域を有する記憶部と、
実行周期ごとの実行が要求される周期タスクの内容が示される周期タスクのタスク情報の格納先と、１回限りの実行が要求される非周期タスクの内容が示される非周期タスクのタスク情報の格納先とを、前記複数の記憶領域の中から選択し、周期タスクのタスク情報及び非周期タスクのタスク情報の各々を、各々について選択した記憶領域に格納するタスク情報格納部と、
単位時間の経過ごとに繰り返し到来するタスク情報の読み出しタイミングが到来する度に、選択する記憶領域を読み出しタイミングごとに変化させて、前記複数の記憶領域の中からタスク情報の読み出し対象の記憶領域を選択し、選択した記憶領域に格納されている周期タスクのタスク情報及び非周期タスクのタスク情報の少なくともいずれかを読み出し、読み出したタスク情報に示されるタスクを実行リソースに実行させるタスク管理部とを有し、
前記記憶部は、
全ての読み出しタイミングにおいて読み出し対象の記憶領域として選択される１つの優先記憶領域と、優先記憶領域以外の２つ以上の通常記憶領域に区分され、
それぞれの通常記憶領域には、読み出し対象の記憶領域として選択される順序として、読み出し順位が指定され、
優先記憶領域には、現在時刻から、次の読み出しタイミングの時刻までの時間帯が指定され、
第１位の読み出し順位が指定されている記憶領域には、次の読み出しタイミングの時刻から、次の読み出しタイミングの時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
第２位以降の読み出し順位の記憶領域には、１つ上位の読み出し順位の記憶領域に指定されている時間帯の終期に後続する時刻から、当該時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
前記タスク情報格納部は、
周期タスクに対しては、実行リソースにより周期タスクが実行された直近の時刻に前記実行周期を加算して得られる時刻を包含する時間帯が指定されている記憶領域をタスク情報の格納先として選択し、選択した記憶領域にタスク情報を格納し、
非周期タスクに対しては、実行リソースにおいて非周期タスクの実行を開始することが可能な時刻を実行開始可能時刻として予測し、予測した実行開始可能時刻を包含する時間帯が指定されている記憶領域をタスク情報の格納先として選択し、選択した記憶領域にタスク情報を格納し、
前記タスク管理部は、
読み出しタイミングが到来する度に、
優先記憶領域と第１位の読み出し順位が指定されている通常記憶領域を読み出し対象の記憶領域として選択し、第１位の読み出し順位が指定されている通常記憶領域に格納されているタスク情報を優先記憶領域に移動させ、
第１位の読み出し順位が指定されている通常記憶領域の順位を最下位の読み出し順位にするとともに、第２位以降の読み出し順位の記憶領域の順位をそれぞれ１つずつ繰り上げ、それぞれの通常記憶領域に対して新たな読み出し順位を指定し、
通常記憶領域から移動させたタスク情報を含む、優先記憶領域に格納されているタスク情報を読み出し、読み出したタスク情報に示されるタスクを実行リソースに実行させることを特徴とする情報処理装置。
【請求項７】
前記情報処理装置は、更に、
実行リソースが１つのタスクを実行する際に要する平均時間を平均タスク実行時間として示し、実行リソースにより実行済みのタスクの数を実行済みタスク数として示し、実行リソースによる実行待ちの非周期タスクの数を実行待ちタスク数として示し、前記単位時間における周期タスクの実行数を周期タスク実行頻度として示す実行リソース管理テーブルを保持する実行リソース管理テーブル保持部を有し、
前記タスク情報格納部は、
非周期タスクに対して、前記リソース管理テーブルに示される平均タスク実行時間と実行待ちタスク数と周期タスク実行頻度とを用いて実行開始可能時刻を予測し、予測した実行開始可能時刻を包含する時間帯が指定されている記憶領域をタスク情報の格納先として選択し、
前記タスク管理部は、
読み出しタイミングが到来する度に、
優先記憶領域からタスク情報を読み出し、更に、読み出したタスク情報に示されるタスクを実行リソースに実行させた後に、
実行リソースに実行させたタスクの実行時間と、前記リソース管理テーブルに示される平均タスク実行時間と実行済みタスク数とに基づき、平均タスク実行時間を更新し、
更新後の平均タスク実行時間を前記実行リソース管理テーブルに反映させることを特徴とする請求項６に記載の情報処理装置。
【請求項８】
前記タスク情報格納部は、
非周期タスクのタスク情報を記憶領域に格納する度に、前記リソース管理テーブルの実行待ちタスク数を増加させ、
周期タスクのタスク情報を記憶領域に格納する度に、当該周期タスクの実行周期の逆数を用いて前記リソース管理テーブルの周期タスク実行頻度を更新し、
前記タスク管理部は、
実行リソースに非周期タスクを実行させる度に、前記リソース管理テーブルの実行待ちタスク数を減少させ、実行済みタスク数を増加させることを特徴とする請求項７に記載の情報処理装置。
【請求項９】
複数の記憶領域を有する記憶部と、
優先度が指定されているタスクの内容が示されるタスク情報の格納先を、前記複数の記憶領域の中から選択し、選択した記憶領域にタスク情報を格納するタスク情報格納部と、
単位時間の経過ごとに繰り返し到来するタスク情報の読み出しタイミングが到来する度に、選択する記憶領域を読み出しタイミングごとに変化させて、前記複数の記憶領域の中からタスク情報の読み出し対象の記憶領域を選択し、選択した記憶領域から優先度が指定されているタスクのタスク情報を読み出し、読み出したタスク情報に示されるタスクを実行リソースに実行させるタスク管理部とを有し、
前記記憶部は、
全ての読み出しタイミングにおいて読み出し対象の記憶領域として選択される１つの優先記憶領域と、優先記憶領域以外の２つ以上の通常記憶領域に区分され、
それぞれの通常記憶領域には、読み出し対象の記憶領域として選択される順序として、読み出し順位が指定され、
優先記憶領域には、現在時刻から、次の読み出しタイミングの時刻から、次の読み出しタイミングの時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
第１位の読み出し順位が指定されている記憶領域には、次の読み出しタイミングの時刻から、次の読み出しタイミングの時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
第２位以降の読み出し順位の記憶領域には、１つ上位の読み出し順位の記憶領域に指定されている時間帯の終期に後続する時刻から、当該時刻に前記単位時間を加えて得られる時刻までの時間帯が指定され、
更に、
実行リソースが１つのタスクを実行する際に要する平均時間を平均タスク実行時間として示し、実行リソースにより実行済みのタスクの数を実行済みタスク数として示し、優先度ごとに、実行リソースによる実行待ちのタスクの数を実行待ちタスク数として示す実行リソース管理テーブルを保持する実行リソース管理テーブル保持部を有し、
前記タスク情報格納部は、
実行リソースに実行させるタスクに対して、前記リソース管理テーブルに示される平均タスク実行時間と、当該タスクの優先度での実行待ちタスク数と当該タスクの優先度よりも高い優先度での実行待ちタスク数とを用いて、実行リソースにおいて当該タスクの実行を開始することが可能な時刻を実行開始可能時刻として予測し、予測した実行開始可能時刻を包含する時間帯が指定されている記憶領域をタスク情報の格納先として選択し、
前記タスク管理部は、
読み出しタイミングが到来する度に、
優先記憶領域と第１位の読み出し順位が指定されている通常記憶領域を読み出し対象の記憶領域として選択し、第１位の読み出し順位が指定されている通常記憶領域に格納されているタスク情報を優先記憶領域に移動させ、
第１位の読み出し順位が指定されている通常記憶領域の順位を最下位の読み出し順位にするとともに、第２位以降の読み出し順位の記憶領域の順位をそれぞれ１つずつ繰り上げ、それぞれの通常記憶領域に対して新たな読み出し順位を指定し、
通常記憶領域から移動させたタスク情報を含む、優先記憶領域に格納されているタスク情報を読み出し、読み出したタスク情報に示されるタスクを実行リソースに実行させ、
実行リソースに実行させたタスクの実行時間と、前記リソース管理テーブルに示される平均タスク実行時間と実行済みタスク数とに基づき、平均タスク実行時間を更新し、
更新後の平均タスク実行時間を前記実行リソース管理テーブルに反映させることを特徴とする情報処理装置。
【請求項１０】
前記タスク情報格納部は、
タスク情報を記憶領域に格納する度に、記憶領域に格納したタスク情報が対象とするタスクの優先度の実行待ちタスク数を前記リソース管理テーブルにおいて増加させ、
前記タスク管理部は、
実行リソースにタスクを実行させる度に、前記リソース管理テーブルにおいて、当該タスクの優先度の実行待ちタスク数を減少させ、更に、実行済みタスク数を増加させることを特徴とする請求項９に記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の実行リソースによる周期的及び非周期的タスクの実行スケジュールを制御する技術に関し、例えば、多数の情報源（Ｗｅｂサーバ装置、センサ装置等）からの高頻度なデータ取得のスケジュールを制御する技術に関する。
【背景技術】
【０００２】
マルチタスクのコンピュータシステムにおいては、少数のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を時分割により共有し、より多くのタスクの実行を可能にしている。
各タスクへのＣＰＵ割当ては、オペレーティングシステムが提供するスケジューリング機能により実現され、実行優先度や実行期限に基づいて適切なタスクを選択することでＣＰＵの利用効率を高める。
ＣＰＵが割り当てられていないタスクの情報は優先度付き待ち行列（プライオリティキュー）に格納され、優先度をキーとするタスクの挿入や、最高優先度を持つタスクの取出し操作が行われる。
プライオリティキュー（以下、単にキューと記す）を主記憶装置上で効率的に実現するためのデータ構造として、二分ヒープ（バイナリヒープ）などが知られている（例えば、非特許文献１参照）。
また、特許文献１には、キューを主記憶上に置く従来のスケジューリング装置の例が開示されている。
【０００３】
一方、現在の主要な二次記憶装置は磁気ディスク装置であり、主記憶装置に用いられる半導体メモリと比較して単に低速であるだけでなく、連続するアドレスに対するアクセス（シーケンシャルアクセス）の速度（〜２００ＭＢ／ｓ）に対し、不連続なアドレスに対するアクセス（ランダムアクセス）の速度（数ＭＢ／ｓ）が著しく低いという特性がある。
そのため、主記憶装置上で効率的に動作するデータ構造をそのまま二次記憶装置上で実現しても、十分なアクセス速度が得られないことが通常である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−１３２４１１号公報  第１頁  図１
【非特許文献】
【０００５】
【非特許文献１】ＩＳＢＮ  ４７６４９０２２２２  アルゴリズムＣ＋＋（セジウィック著、野下ほか訳）  第１６５頁〜第１８４頁
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来のスケジューリング装置では、扱うタスク数は多くて数百〜数千程度であり、キューを二次記憶装置上に格納することは想定されていなかった（実行頻度が低く、性能がクリティカルでないバッチジョブ等を除く）。
また、マルチプロセッサシステム等、複数の実行リソースを有する場合、各実行リソースの性能は均一であり、タスクと実行リソースの対応に関する強い制約（特定実行リソースでしか実行できないタスク）がないことが前提であった。
【０００７】
一方、センサ装置やＷｅｂサーバ装置等の多数の情報源からのデータ取得においては、個々の情報源が実行リソースに、各情報源から取得するデータの項目（測定値の種別、Ｗｅｂページ等）がタスクに相当することになる。
日本のＷｅｂサーバ装置全体からのデータ収集においては、情報源の数は数千万に上り、各Ｗｅｂサーバ装置から平均５０ページずつ取得すると仮定すると、ＵＲＬ（Ｕｎｉｆｏｒｍ  Ｒｅｓｏｕｒｃｅ  Ｌｏｃａｔｏｒ）文字列（平均１００バイトと仮定）だけで１００ＧＢを超えることになり、キューを主記憶上に配置することは現実的でなくなる。
また、個々の情報源はそれぞれ異なる通信速度を有するため、データ取得タスクの進捗には実行リソースごとに差異が生じる。
さらに、取得対象データはそれぞれ固有の情報源から取得する必要があり、データ取得タスクと実行リソースの対応を変更することはできない。
【０００８】
このようなタスクのスケジューリングにおいては、タスクの内容が示されるタスク情報をキューから読み出し、タスク情報に示されるタスクを実行リソースに実行させるが、従来のスケジューリング装置におけるキューを単純に二次記憶装置上に配置しただけでは、キューの操作に伴うオーバヘッドが大幅に増大し、タスクの実行性能が低下してしまう。
例えば、キューを全体で１つとした場合、高速な情報源（実行リソース）に関するタスクのタスク情報を、キューの先頭から探索して任意の位置から取り出す必要があり、二次記憶アクセスの回数が増加してしまう。
一方、情報源（実行リソース）ごとにキューを分離し、複数のキューを用いることにすると、タスク情報の読み出しの際に二次記憶装置に対するランダムアクセスが避けられず、シーク・回転待ちにより入出力性能が低下してしまう。
【０００９】
この発明は、上記の課題を解決することを主な目的としており、タスク情報の読み出しの際のオーバヘッドを最小限にして、タスクのスケジューリングを効率化することを主な目的とする。
【課題を解決するための手段】
【００１０】
本発明に係る情報処理装置は、
複数の記憶領域を有する記憶部と、
タスクの内容が示されるタスク情報を、前記複数の記憶領域の中から選択し、選択した記憶領域にタスク情報を格納するタスク情報格納部と、
繰り返し到来するタスク情報の読み出しタイミングが到来する度に、選択する記憶領域を読み出しタイミングごとに変化させて、前記複数の記憶領域の中からタスク情報の読み出し対象の記憶領域を選択し、選択した記憶領域に格納されているタスク情報を読み出し、読み出したタスク情報に示されるタスクを所定の実行リソースに実行させるタスク管理部とを有することを特徴とする。
【発明の効果】
【００１１】
本発明では、複数の記憶領域にタスク情報を格納するので、全体で１つのキューとした場合に発生するアクセス回数の増加を回避することができる。
また、読み出しタイミングでは、選択された記憶領域のみからタスク情報を読み出すので、複数の記憶領域からのランダムアクセスを回避することができる。
また、選択される記憶領域が読み出しタイミングごとに変化するため、複数の記憶領域に記憶されている各タスク情報を順次読み出すことができる。
このように、本発明によれば、タスク情報の読み出しの際のオーバヘッドを最小限にして、タスクのスケジューリングを効率化することができる。
【図面の簡単な説明】
【００１２】
【図１】実施の形態１に係るスケジューリング装置の構成例を示す図。
【図２】実施の形態１に係るタスク要求の例を示す図。
【図３】実施の形態１に係るタスク情報の例を示す図。
【図４】実施の形態１に係る書込バッファにおけるタスク情報の格納例を示す図。
【図５】実施の形態１に係る実行リソース管理情報の例を示す図。
【図６】実施の形態１に係るスケジューリング装置の動作例を示すフローチャート図。
【図７】実施の形態１に係るスケジューリング装置の動作例を示すフローチャート図。
【図８】実施の形態１に係るスケジューリング装置の動作例を示すフローチャート図。
【図９】実施の形態１に係るスケジューリング装置の動作例を示すフローチャート図。
【図１０】実施の形態２に係るスケジューリング装置の構成例を示す図。
【図１１】実施の形態２に係るタスク要求の例を示す図。
【図１２】実施の形態２に係るタスク情報の例を示す図。
【図１３】実施の形態２に係る実行リソース管理情報の例を示す図。
【図１４】実施の形態３に係るタスク要求の例を示す図。
【図１５】実施の形態３に係るタスク情報の例を示す図。
【図１６】実施の形態３に係る実行リソース管理情報の例を示す図。
【図１７】実施の形態１〜３に係るスケジューリング装置のハードウェア構成例を示す図。
【発明を実施するための形態】
【００１３】
実施の形態１．
本実施の形態及び以降の実施の形態では、処理速度の異なる多数の実行リソースに対する大量タスクのスケジューリングを、大容量の主記憶に依存することなく、効率的に実施することを可能にする構成を説明する。
【００１４】
図１は、本実施の形態に係るスケジューリング装置１の構成例を示す図である。
【００１５】
図１において、スケジューリング装置１は、外部から受け取ったタスク要求２に基づき、適切なタイミングで実行リソース３によるタスクの実行を制御する。
タスク要求２には、実行対象のタスクの内容と、タスクを実行させる実行リソースが示される。
詳細は後述するが、タスク要求２は例えば図２に示す形式をとる。
実行リソース３は、タスクを実行するシステム（ハードウェアとソフトウェアの組合せ）であり、例えば、Ｗｅｂサーバ装置やセンサ装置である。
スケジューリング装置１は、複数の実行リソース３を管理している。
なお、スケジューリング装置１は、情報処理装置の例に相当する。
【００１６】
スケジューリング装置１の構成要素の詳細を説明する前に、ここで、スケジューリング装置１におけるバッファ構成を概説する。
【００１７】
スケジューリング装置１には、複数のバッファが設けられる。
より具体的には、スケジューリング装置１のランダムアクセスメモリ上の複数の記憶領域が、複数のバッファとして機能する。
各バッファには、タスク情報２ａが格納される。
タスク情報２ａは、タスク要求２に、タスクの実行予定時刻が追加された情報である。
詳細は後述するが、タスク情報２ａは例えば図３に示す形式をとる。
そして、複数のバッファは、１つの読込バッファ９と、２つ以上の書込バッファ８に区分される。
読込バッファ９は優先記憶領域の例に相当し、書込バッファ８は通常記憶領域の例に相当する。
２つ以上の書込バッファ８には、タスク情報２ａの読み出しの順序として、読み出し順位が指定されている。
第１位の読み出し順位が指定されているバッファが書込バッファ８ｂとなり、第２位の読み出し順位が指定されているバッファが書込バッファ８ｃとなり、最下位の読み出し順位が指定されているバッファが書込バッファ８ｄとなる。
例えば、スケジューリング装置１に、バッファα、バッファβ、バッファγ、バッファδと４つのバッファが存在し、バッファαが読込バッファ９に指定され、バッファβ、バッファγ、バッファδが書込バッファ８に指定されていると仮定する。
バッファβに第１位の読み出し順位が指定され、バッファγに第２位の読み出し順位が指定され、バッファδに第３位の読み出し順位が指定されていれば、バッファβが書込バッファ８ｂとなり、バッファγが書込バッファ８ｃとなり、バッファδが書込バッファ８ｄとなる。
なお、後述するように、読込バッファ９となるバッファは固定されるが、書込バッファ８ｂ〜８ｄとなるバッファは、読み出しタイミングごとに更新される。
読み出しタイミングとは、タスク情報２ａを読み出すタイミングであり、所定の単位時間ｕごとに繰り返し到来する。
【００１８】
また、各バッファには、単位時間ｕを共通の時間帯幅にして、それぞれに異なる時間帯が指定されている。
上位の読み出し順位が指定されているバッファほど、現在時刻に近い時間帯が指定されている。
読込バッファ９には、現在時刻から最も近い時間帯、より具体的には次の読み出しタイミングまでの時間帯が指定されている。
書込バッファ８ｂには、次の読み出しタイミングに単位時間ｕを加えて得られる時間帯が指定されている。
書込バッファ８ｃ、書込バッファ８ｄには、１つ上位の読み出し順位のバッファに指定されている時間帯に単位時間ｕを加えて得られる時間帯が指定されている。
タスク情報２ａの格納については、タスクの実行予定時刻を包含する時間帯が指定されているバッファがタスク情報２ａの格納先として選択され、選択されたバッファにタスク情報２ａが格納される。
【００１９】
タスク情報２ａの読み出しは、単位時間ｕごとの読み出しタイミングが到来した際に行われる。
より具体的には、読込バッファ９と、読み出しタイミングが到来した時点で書込バッファ８ｂとなっているバッファが読み出し対象として選択され、書込バッファ８ｂに格納されているタスク情報２ａを読込バッファ９に移動させる。
また、書込バッファ８の読み出し順位が更新される。
前出の例でいえば、第１位の読み出し順位であり書込バッファ８ｂであるバッファβの読み出し順位が第３位となり、新たな書込バッファ８ｄとなる。
また、第２位の読み出し順位であり書込バッファ８ｃであるバッファγの読み出し順位が１つ繰り上がり第１位となり、新たな書込バッファ８ｂとなる。
また、第３位の読み出し順位であり書込バッファ８ｄであるバッファδの読み出し順位が１つ繰り上がり第２位となり、新たな書込バッファ８ｃとなる。
次の読み出しタイミングでは、読込バッファ９であるバッファαと書込バッファ８ｂであるバッファγが読み出し対象として選択され、次の読み出しタイミングでも、同様にして、書込バッファ８の読み出し順位が更新される。
そして、読込バッファ９に格納されているタスク情報２ａ（書込バッファ８ｂから移動したタスク情報２ａを含む）を読み出して、タスク情報２ａに示されているタスクを、対象となる実行リソースに実行させる。
【００２０】
次に、スケジューリング装置１の各構成要素を説明する。
【００２１】
タスク受付部４は、タスク要求２を受信する。
また、タスク受付部４は、受信したタスク要求２に示されるタスクの実行の開始が可能な時刻（実行開始可能時刻）を算出し、算出した時刻を実行予定時刻としてタスク要求２に付加してタスク情報２ａを生成する。
更に、タスク受付部４は、実行予定時刻を包含する時間帯が指定されているバッファを選択して、選択したバッファにタスク情報２ａを格納する。
なお、タスク受付部４は、タスク情報格納部の例に相当する。
【００２２】
タスク駆動部５は、読み出しタイミングが到来する度に、選択するバッファを読み出しタイミングごとに変化させて、複数のバッファの中からタスク情報２ａの読み出し対象のバッファを選択する。
つまり、上述のように、読込バッファ９と、読み出しタイミング時点で書込バッファ８ｂとなっているバッファをタスク情報２ａの読み出し対象として選択する。
そして、タスク駆動部５は、選択したバッファに格納されているタスク情報２ａを読み出し、読み出したタスク情報２ａに示されるタスクを、読み出したタスク情報２ａに示される実行リソースに実行させる。
また、前述のように、読み出しタイミングごとに、書込バッファ８の読み出し順位を更新する。
なお、タスク駆動部５は、タスク管理部の例に相当する。
【００２３】
実行リソース管理テーブル保持部６０は、実行リソース管理テーブル６を記憶する。
実行リソース管理テーブル６は、複数の実行リソース管理情報６ａで構成される。
詳細は後述するが、実行リソース管理情報６ａは、例えば図５に示す形式をとる。
【００２４】
複数の格納領域７ａ〜７ｄは、タスク情報２ａを格納する。
格納領域７ａは、読込バッファ９と対応付けられている。
格納領域７ｂは、書込バッファ８ｂと対応付けられている。
格納領域７ｃは、書込バッファ８ｃと対応付けられている。
格納領域７ｄは、書込バッファ８ｄと対応付けられている。
【００２５】
スケジューリング装置１は一般的なコンピュータを用い、格納領域７ａ〜７ｄを磁気ディスク装置で、書込バッファ８ｂ〜８ｄ及び読込バッファ９をランダムアクセスメモリで実現することができる。
書込バッファ８ｂ〜８ｄ及び読込バッファ９を構成するランダムアクセスメモリが、記憶部の例に相当する。
また、実行リソース管理テーブル保持部６０をランダムアクセスメモリをキャッシュとして使用する磁気ディスク装置で、タスク受付部４及びタスク駆動部５をランダムアクセスメモリに格納されＣＰＵで実行されるコンピュータプログラムとして、それぞれ実現することができる。
また、格納領域７ａ〜７ｄはＬｉｎｕｘ（登録商標）やＷｉｎｄｏｗｓ（登録商標）等の一般的なオペレーティングシステムが提供するファイルとして、実行リソース管理テーブル６はＰｏｓｔｇｒｅＳＱＬ（登録商標）等の一般的な関係データベース管理システムが提供する関係表として、それぞれ実現することができる。
さらに、タスク受付部４はＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）等の通信回線を介して外部からタスク要求２を受け取ることができる。
【００２６】
図２は、タスク受付部４が受け取るタスク要求２の形式を示したものである。
【００２７】
タスク要求２は、実行リソース３のいずれか１つを指定する実行リソースＩＤ２１と、実行するタスクの内容であるタスク内容２２からなる。
図２ではＷｅｂサーバ装置からのＷｅｂページデータ取得をタスクの例とし、実行リソースＩＤ２１を取得対象Ｗｅｂサーバ装置のホスト名で、タスク内容２２を通信プロトコルとそのパラメータで表すものとした。
【００２８】
図３は、タスク受付部４が受け取ったタスク要求２に対応して作成され、書込バッファ８ｂ〜８ｄ、格納領域７ａ〜７ｄ、及び読込バッファ９に格納されるタスク情報２ａの形式を示したものである。
【００２９】
タスク情報２ａは実行リソースＩＤ２１ａ、タスク内容２２ａ、及び実行予定時刻２３ａからなり、タスク要求２の情報に、実行予定時刻２３ａを付与した値を持つ。
タスク情報２ａが格納される書込バッファ８ｂ〜８ｄや格納領域７ａ〜７ｄは、実行予定時刻２３ａと現在時刻の差を、所定の単位時間ｕで除した結果に基づいて決定される。すなわち、除算の結果がｔ−１以上ｔ未満（ただしｔは整数であり、１＜ｔ＜Ｔ）となるタスク情報２ａは、書込バッファ（ｔ）または格納領域（ｔ）に存在する。
また、除算の結果が０以上１未満となるタスク情報２ａは、読込バッファ９または格納領域（１）に存在し、除算の結果がＴ−１以上となるタスク情報２ａは、書込バッファ（Ｔ）または格納領域（Ｔ）に存在する。
【００３０】
図４は書込バッファ８ｂ〜８ｄの形式を示す図である。
【００３１】
書込バッファ８ｂ〜８ｄは固定長ページ単位で拡張され、先頭からタスク情報２ａが順に格納され、末尾は空き領域となっている。
格納領域７ａ〜７ｄも同様に先頭からタスク情報２ａを順に格納した形式を持つが、領域の拡張はオペレーティングシステムの機能により自動的に行われ、末尾の空き領域も隠蔽される。
読込バッファ９には、書込バッファ８と同様の線形リスト構造、または、タスク情報２ａの実行リソースＩＤ２１ａをキーとする探索構造（例えば、非特許文献１等に記載のハッシュ表など）を用いることができる。
【００３２】
図５は実行リソース管理テーブル６に格納される実行リソース管理情報６ａの形式を示したものである。
【００３３】
実行リソース管理情報６ａは実行リソース３ごとに１エントリ存在し、実行リソースＩＤ６１、平均タスク実行時間６２、実行済みタスク数６３、実行待ちタスク数６４からなる。
実行待ちタスク数６４は、当該実行リソース３に対応するタスクのうち、書込バッファ８ｂ〜８ｄ、読込バッファ９、または格納領域７ａ〜７ｄのいずれかに格納されたタスク情報の総数を表す。
また、実行済みタスク数６３は、当該実行リソース３に関して過去に実行したタスクの累積数を表す。
また、平均タスク実行時間６２はその際のタスク実行時間の平均値、つまり、実行リソースが１つのタスクを実行する際に要する平均時間を表す。
実行リソース管理テーブル保持部６０は、実行リソースＩＤをキーとする実行リソース管理情報６ａの検索及び更新と、新たな実行リソース管理情報６ａの挿入操作を実現する。
実行リソース管理テーブル６は、データの永続化のため磁気ディスク装置に格納する必要があるが、スケジューリング装置１の動作中はランダムアクセスメモリをキャッシュとして用いることで、頻繁にアクセスされる実行リソース管理情報６ａは磁気ディスク装置にアクセスすることなく参照することが可能である。
【００３４】
次に、動作についてフローチャートを用いて説明する。
図６は、タスク受付部４がタスク要求２を受け取った際の動作を示すフローチャートである。
【００３５】
まず、ステップＳ４１で、タスク受付部４は、受け取ったタスク要求２の実行リソースＩＤ２１により実行リソース管理テーブル６を検索する。
【００３６】
ステップＳ４２で、タスク受付部４は、検索の結果を判定し、実行リソース管理情報６ａが得られた場合はステップＳ４３に、得られなかった場合はステップＳ４８に進む。
【００３７】
ステップＳ４３では、タスク受付部４は、実行リソース管理情報６ａに基づいて新たなタスクの実行予定時刻を決定し、実行リソースＩＤ２１ａをタスク要求２の実行リソースＩＤ２１とし、タスク内容２２ａをタスク要求２のタスク内容２２とし、実行予定時刻２３ａを決定した実行予定時刻とするタスク情報２ａを作成する。
ここで、実行予定時刻の値は、以下の式１により算出される。
現在時刻＋平均タスク実行時間６２×実行待ちタスク数６４・・・式１
これは、当該実行リソース３において、受付済みのタスクを順次実行した際の完了時刻、すなわち、当該実行リソース３においてタスク要求２に示されるタスクの実行を開始することが可能な時刻（実行開始可能時刻）に相当する。
【００３８】
続いてステップＳ４４で、タスク受付部４は、実行リソース管理情報６ａの実行待ちタスク数６４の値に１を加えた結果により、実行リソース管理テーブル保持部６０に実行リソース管理テーブル６の更新を行わせる。
【００３９】
ステップＳ４５では、タスク受付部４は、ステップＳ４３で作成したタスク情報２ａの格納先バッファを、実行予定時刻２３ａに基づいて決定する。
すなわち、以下の式２によりｔを算出し、算出したｔの値により格納先バッファを決定する。
ｔ＝１＋［（実行予定時刻２３ａ−現在時刻）／ｕ］（但し、［ｘ］はｘの整数部分）・・・式２
式２においてｔ＝１であればタスク情報２ａの格納先を読込バッファ９とし、１＜ｔ＜Ｔであれば格納先を書込バッファ（ｔ）とし、ｔ≧Ｔであれば格納先を書込バッファ（Ｔ）とする。
【００４０】
ステップＳ４６では、タスク受付部４は、格納先が読込バッファ９であるかどうかを判定し、読込バッファ９であればステップＳ５０に進み、そうでなければステップＳ４７に進む。
【００４１】
ステップＳ４７では、タスク受付部４は、タスク情報２ａを格納先の書込バッファ８に追加し、タスク受付処理を終了する。
ステップＳ４７の動作の詳細は後述する。
【００４２】
ステップＳ４２からステップＳ４８に進んだ場合、タスク受付部４は、実行リソースＩＤ２１ａをタスク要求２の実行リソースＩＤ２１とし、タスク内容２２ａをタスク要求２のタスク内容２２とし、実行予定時刻２３ａを現在時刻とするタスク情報２ａを作成する。
【００４３】
続いてステップＳ４９で、タスク受付部４は、実行リソースＩＤ６１をタスク要求２の実行リソースＩＤ２１とし、平均タスク実行時間６２を０とし、実行済みタスク数６３を０とし、実行待ちタスク数６４を１とする実行リソース管理情報６ａを作成し、実行リソース管理テーブル保持部６０に実行リソース管理テーブル６への挿入を行わせる。
【００４４】
ステップＳ５０では、タスク受付部４は、ステップＳ４３またはステップＳ４８で作成したタスク情報２ａを読込バッファに追加し、タスク受付処理を終了する。
【００４５】
図７は、タスク受付部４のステップＳ４７における動作の詳細を示すフローチャートである。
【００４６】
まず、ステップＳ４７１で、タスク受付部４は、格納先の書込バッファ８にタスク情報２ａを追加できる空き領域が存在するかどうかを判定し、空き領域が存在すればステップＳ４７６へ進み、そうでなければステップＳ４７２に進む。
【００４７】
ステップＳ４７２では、タスク受付部４は、書込バッファ８を拡張するための１ページ分の空きメモリが割当可能かどうかを判定し、割当可能であればステップＳ４７５へ進み、そうでなければステップＳ４７３へ進む。
【００４８】
ステップＳ４７３では、２≦ｔ≦Ｔとなる整数ｔについて順次、書込バッファ（ｔ）に格納されているタスク情報２ａを格納領域（ｔ）に追加する。
続いてステップＳ４７４では、各書込バッファに割り当てられたメモリを解放する。
【００４９】
ステップＳ４７５では、タスク受付部４は、１ページ分の空きメモリを割り当て、格納先の書込バッファ８を拡張する。
【００５０】
ステップＳ４７６では、タスク受付部４は、格納先の書込バッファ８の空き領域にタスク情報２ａを格納し、タスク受付処理を終了する。
【００５１】
図８は、タスク駆動部５の動作のうち、所定の単位時間ｕごとに行う動作を示すフローチャートである。
【００５２】
まず、ステップＳ５１で、タスク駆動部５は、格納領域（１）７ａに格納されたタスク情報２ａを削除して格納領域（１）７ａを空にした後に、格納領域（１）７ａを新たな格納領域（Ｔ）７ｄに、格納領域（ｔ）を新たな格納領域（ｔ−１）に（ｔは２≦ｔ≦Ｔとなる整数）、それぞれ読み替える。
【００５３】
続いてステップＳ５２で、タスク駆動部５は、書込バッファ（２）８ｂとなっているバッファを読み出し対象として選択し、書込バッファ（２）８ｂに格納されているタスク情報２ａを読込バッファ９に移動させて書込バッファ（２）８ｂに割り当てられたメモリを解放した後に、書込バッファ（２）８ｂを新たな書込バッファ（Ｔ）８ｄに、書込バッファ（ｔ）を新たな書込バッファ（ｔ−１）に（ｔは３≦ｔ≦Ｔとなる整数）、それぞれ読み替える。
【００５４】
ステップＳ５３で、タスク駆動部５は、新たな格納領域（１）７ａ（元の格納領域（２）７ｂ）に格納されたタスク情報２ａを一括して読み込み、読込バッファ９に空きメモリを必要なだけ割り当てて格納する。
【００５５】
ステップＳ５４では、タスク駆動部５は、読込バッファ９の全てのタスク情報２ａ（書込バッファ（２）８ｂ及び新たな格納領域（１）７ａから移動させたタスク情報２ａを含む）に対し、ステップＳ５５〜ステップＳ５９の処理を行ったかどうかを判定し、行っていれば処理を終了し、そうでなければステップＳ５５に進む。
【００５６】
ステップＳ５５では、タスク駆動部５は、読込バッファ９から未処理のタスク情報２ａのうち、先頭の要素を取得する（読み出す）。
【００５７】
続いてステップＳ５６で、タスク駆動部５は、取得したタスク情報２ａの実行リソースＩＤ２１ａに対応する実行リソース３の状態を調べ、タスク実行中でない空き状態かどうかを判定する。
当該実行リソース３が空き状態であればステップＳ５７に進み、そうでなければステップＳ５４に戻る。
【００５８】
ステップＳ５７で、タスク駆動部５は、ステップＳ５５で取得したタスク情報２ａに基づき、実行リソースＩＤ２１ａに対応する実行リソース３で、タスク内容２２ａに指定されたタスクの実行を起動する。
【００５９】
続いてステップＳ５８で、タスク駆動部５は、取得したタスク情報２ａを読込バッファ９から削除する。
【００６０】
ステップＳ５９で、タスク駆動部５は、実行リソース管理テーブル保持部６０を用いて、取得したタスク情報２ａの実行リソースＩＤ２１ａに基づいて実行リソース管理テーブル６を検索し、得られた実行リソース管理情報６ａの実行待ちタスク数６４を１減じて実行リソース管理テーブル６を更新し、ステップＳ５４に戻る。
【００６１】
ステップＳ５４で読込バッファ９の末尾に達し、処理を終了した後は、図８の動作開始時刻から単位時間ｕが経過するか、実行リソース３のいずれか１つからタスクの実行完了通知を受け取るまで、タスク駆動部５は待機状態となる。
【００６２】
図９は、タスク駆動部５が実行リソース３からタスクの実行完了通知を受け取った際に行う動作を示すフローチャートである。
【００６３】
まず、ステップＳ６１で、タスク駆動部５は、完了したタスクの実行時間ｅを求めるとともに、実行リソース管理テーブル保持部６０を用いて、当該実行リソース３の実行リソースＩＤに基づいて実行リソース管理テーブル６を検索し、実行リソース管理情報６ａを取得して次のように更新する。
すなわち、浮動小数点数値ｄを、以下の式３で算出する。
ｄ＝（ｅ−平均タスク実行時間６２）／（実行済みタスク数６３）・・・式３
更に、タスク駆動部５は、平均タスク実行時間６２に浮動小数点数値ｄを加え、実行済みタスク数６３に１を加えた結果を新たな実行リソース管理情報６ａとする。
さらに、更新した実行リソース管理情報６ａを実行リソース管理テーブル６に反映する。
【００６４】
続いてステップＳ６２で、タスク駆動部５は、読込バッファ９を検索し、当該実行リソース３に対応するタスク情報２ａの取得を試みる。
【００６５】
タスク駆動部５は、ステップＳ６３でタスク情報２ａが得られたかどうかを判定し、得られた場合はステップＳ６４に進み、そうでなかった場合は処理を終了する。
【００６６】
ステップＳ６４では、タスク駆動部５は、ステップＳ６２で取得したタスク情報２ａに基づき、当該実行リソース３で、タスク内容２２ａに指定されたタスクの実行を起動する。
【００６７】
続いてステップＳ６５で、タスク駆動部５は、取得したタスク情報２ａを読込バッファ９から削除する。
ステップＳ６６では、タスク駆動部５は、ステップＳ６１で取得した実行リソース管理情報６ａの実行待ちタスク数６４を１減じた内容を用いて実行リソース管理テーブル保持部６０に実行リソース管理テーブル６を更新させ、処理を終了する。
【００６８】
以上のように、本実施の形態によれば、タスクを起動する時刻を単位時間ｕで量子化し、量子化された時刻ごとに二次記憶装置上の格納領域７を設けて複数のタスク情報を分割して格納するので、大量のタスク情報を効率的に管理することができる。
【００６９】
また、タスク起動時のタスク情報の二次記憶装置からの読込みは、実行リソース数やタスク数によらず、格納領域（１）７ａに対して１度だけ行われるので、二次記憶装置の入出力性能を低下させるランダムアクセスを回避し、高速な動作を実現することができる。
【００７０】
また、実際のタスクの実行時間に基づく平均タスク実行時間と、実行待ちタスク数を保持する実行リソース管理テーブル６を有するので、新たに要求されたタスクの実行時刻を適切に決定し、実行リソースの利用効率低下を防ぐことができる。
【００７１】
また、実行リソース管理テーブル６は、実行リソースごとに実行リソース管理情報６ａを保持するので、実行リソースによる処理速度の差異が大きい場合に、低速な実行リソースのタスク情報への不要なアクセスを発生させることなく、高速な動作を維持することができる。
【００７２】
また、格納領域７ごとに主記憶上に書込バッファ８を設け、空きメモリが存在する限り任意のサイズに拡張することを許すことで、時刻ごとのタスク発生頻度が均一でない場合にも主記憶を有効活用し、二次記憶装置への書込みを効率化して高速な動作を実現することができる。
【００７３】
実施の形態２．
図１０は、本実施の形態にかかるスケジューリング装置１の構成図である。
【００７４】
実施の形態２では、タスク駆動部５が実行済みタスクのタスク情報２ａを読込バッファ９や書込バッファ８を介して格納領域７に再度格納できる点が実施の形態１と異なる。
これにより、実施の形態２のスケジューリング装置は、周期的に繰り返し実行するタスク（周期タスク）と、随時外部から要求される非周期タスクを同時に扱うことが可能になる。
なお、本実施の形態では、タスク駆動部５も周期タスクのタスク情報２ａを読込バッファ９、書込バッファ８に格納するため、タスク受付部４に加えて、タスク駆動部５もタスク情報格納部の例に相当する。
【００７５】
図１１は、実施の形態２におけるタスク要求２の形式を示したものである。
図２に示した実施の形態１のタスク要求２とは、実行周期２４が加わっている点が異なる。
タスク要求元は、周期タスクの実行を要求する際に、タスク要求２の実行周期２４に０以外の値を設定するものとする。
つまり、周期タスクは、実行周期２４ごとの実行が要求されるタスクである。
非周期タスクの実行を要求する際は、実行周期２４に０を設定する。
つまり、非周期タスクは、１回限りの実行が要求されるタスクである。
【００７６】
図１２は、実施の形態２におけるタスク情報２ａの形式を示したものである。
タスク要求２の実行周期２４に対応する実行周期２４ａが加わっている点が、図３に示した実施の形態１のタスク情報２ａと異なる。
【００７７】
また、図１３は実施の形態２における実行リソース管理情報６ａの形式を示したものである。
図５に示した実施の形態１の実行リソース管理情報６ａとは、周期タスク実行頻度６５が加わっている点が異なる。
【００７８】
上記以外の構成においては、実施の形態２は実施の形態１と同様である。
【００７９】
次に動作について、実施の形態１との差異に基づいて説明する。
【００８０】
タスク受付部４は、タスク要求２を受け付けた際の図６ステップＳ４３において、実行周期２４が０でない場合は、新たに作成するタスク情報２ａの実行予定時刻２３ａを現在時刻に設定する。
実行周期２４が０の場合、実行予定時刻２３ａの値は実行リソース管理情報６ａを用いて、以下の式４の値に設定する。
現在時刻＋実行待ちタスク数６４／（１／平均タスク実行時間６２−周期タスク実行頻度６５）・・・式４
式４において、平均タスク実行時間６２の逆数は単位時間内に実行可能なタスク数であり、この値から周期タスクの実行に必要な分を差し引いたものを非周期タスクの実行可能数として分母に用いている。
これにより、周期タスクの実行頻度が高くなるほど非周期タスクの実行が延期されるが、非周期タスクにより周期タスクの実行が妨げられることはない。
周期タスクの負荷が高過ぎる場合、数式４の分母が負の値となるが、この場合、分母を小定数εで置き換えるものとする。
【００８１】
また、ステップＳ４３及びステップＳ４８では、タスク受付部４は、新たに作成するタスク情報２ａの実行周期２４ａに、タスク要求２の実行周期２４の値を設定する。
【００８２】
ステップＳ４４では、タスク受付部４は、タスク要求２の実行周期２４の値が０でない場合、実行リソース管理情報６ａの周期タスク実行頻度６５に実行周期２４の逆数を加える。
【００８３】
ステップＳ４９では、タスク受付部４は、タスク要求２の実行周期２４の値が０の場合、実行リソース管理情報６ａの実行待ちタスク数６４を１に、周期タスク実行頻度６５を０に、そうでない場合、実行待ちタスク数６４を０に、周期タスク実行頻度６５を実行周期２４の逆数に、それぞれ設定する。
【００８４】
タスク駆動部５は、図８のステップＳ５９及び図９ステップＳ６６において、タスク情報２ａの実行周期２４ａが０でない場合、処理をスキップする。
【００８５】
また、図８のステップＳ５８及び図９ステップＳ６５において、タスク駆動部５は、タスク情報２ａを読込バッファ９から削除した後に、実行周期２４ａが０でない場合、実行予定時刻２３ａを「現在時刻＋実行周期２４ａ」に設定し、タスク受付部の図６ステップＳ４５以降と同様の処理を実行する。
【００８６】
以上のようにこの発明の実施の形態によれば、実行リソース管理テーブル６の実行リソース管理情報６ａに周期タスク実行頻度６５を設け、周期タスクの実行に必要な時間を除いた空き時間で非周期タスクを実行するようにしたので、周期タスクの実行周期を優先しつつ大量の非周期タスクを扱うことが可能になる。
【００８７】
また、周期タスク及び非周期タスクのいずれのタスク情報２ａも、実行予定時刻２３ａに基づいて共通の書込バッファ８及び格納領域７に格納されるので、周期タスク及び非周期タスクのそれぞれごとに独立した管理を行う必要がなく、記憶容量や入出力における効率を高めることができる。
【００８８】
実施の形態３．
本実施の形態に係るスケジューリング装置は、実施の形態２と同様に図１０の構成を取る。
実施の形態３では、タスクに優先度を設けている点が実施の形態２と異なる。
【００８９】
図１４は、実施の形態３におけるタスク要求２の形式を示したものである。
図１１に示した実施の形態２のタスク要求２とは、優先度２５が加わっている点が異なる。
優先度は一定範囲内の整数値を用い、タスク要求元が指定するものとする。また、優先度の値が小さいほど、高い優先度を表すものとする。
【００９０】
図１５は、実施の形態３におけるタスク情報２ａの形式を示したものである。
タスク要求２の優先度２５に対応する優先度２５ａが加わっている点が、図１２に示した実施の形態２のタスク情報２ａと異なる。
【００９１】
また、図１６は実施の形態３における実行リソース管理情報６ａの形式を示したものである。
図１３に示した実施の形態２の実行リソース管理情報６ａとは、実行待ちタスク数６４及び周期タスク実行頻度６５が優先度ごとの複数の値を持つ点が異なる。
【００９２】
上記以外の構成においては、実施の形態３は実施の形態２と同様である。
【００９３】
次に動作について、実施の形態２との差異に基づいて説明する。
【００９４】
タスク受付部４は、タスク要求２を受け付けた際の図６ステップＳ４３において、実行周期２４が０の場合、実行予定時刻２３ａの値を実行リソース管理情報６ａを用いて、以下の式５の値に設定する。
現在時刻＋実行待ちタスク数６４［優先度２５］／（１／平均タスク実行時間６２−周期タスク実行頻度６５［優先度２５］）・・・式５
ただし、Ｘ［Ｙ］は優先度１〜Ｙに対応するＸの値の総和を表すものとする。
式５の分母が負の値となる場合は、分母を小定数εで置き換えるものとする。
【００９５】
また、ステップＳ４３及びステップＳ４８では、タスク受付部４は、新たに作成するタスク情報２ａの実行周期２４ａにタスク要求２の実行周期２４の値を、優先度２５ａにタスク要求２の優先度２５の値を、それぞれ設定する。
【００９６】
ステップＳ４４では、タスク受付部４は、タスク要求２の実行周期２４の値が０でない場合、実行リソース管理情報６ａの周期タスク実行頻度６５の優先度２５に対応する値に実行周期２４の逆数を加える。
【００９７】
ステップＳ４９では、タスク受付部４は、実行リソース管理情報６ａの実行待ちタスク数６４の全ての値を０に、周期タスク実行頻度６５の全ての値を０に初期化した上で、タスク要求２の実行周期２４の値が０の場合、実行待ちタスク数６４の優先度２５に対応する値を１に、そうでない場合、周期タスク実行頻度６５の優先度２５に対応する値を実行周期２４の逆数に、それぞれ設定する。
【００９８】
タスク駆動部５は、図８のステップＳ５９及び図９ステップＳ６６において、タスク情報２ａの実行周期２４ａが０でない場合、実施の形態２と同様に処理をスキップする。
一方、実行周期２４ａが０の場合、実行リソース管理情報６ａの実行待ちタスク数６４の優先度２５ａに対応する値を１減じて実行リソース管理テーブル保持部６０を用いて、実行リソース管理テーブル６を更新する。
【００９９】
図８のステップＳ５８及び図９ステップＳ６５における動作は、実施の形態２と同様であるが、実行リソース３の負荷を考慮して異なる動作を行うようにしてもよい。
すなわち、実行リソース管理情報６ａの周期タスク実行頻度６５の全ての優先度に関する値の総和が、平均タスク実行時間６２の逆数より大きい場合、当該実行リソース３において全ての周期タスクを実行周期通りに実行することはできない。
このような状況下においても高優先度の周期タスクを実行周期通りに実行するため、低優先度の周期タスクの実行周期をタスク要求２の値より大きくすることが考えられる。
例えば、周期タスク実行頻度６５［Ｙ］（優先度１〜Ｙに関する周期タスク実行頻度６５の和）が平均タスク実行時間６２の逆数より大きくなる優先度Ｙを持つ周期タスク（実行周期２４ａが０でないタスク）について、実行予定時刻２３ａを「現在時刻＋実行周期２４ａ×優先度２５ａ」等に設定し、タスク受付部の図６ステップＳ４５以降と同様の処理を実行するようにしてもよい。
【０１００】
以上のように、本実施の形態によれば、実行リソース管理テーブル６の実行リソース管理情報６ａにおける実行待ちタスク数６４及び周期タスク実行頻度６５をタスクの優先度ごとに分離するので、単純な先着順ではなく優先度に基づいて非周期タスクの実行時刻を決定し、重要なタスクの応答時間（要求から実行までの時間）を短縮することができる。
【０１０１】
ここで、実施の形態１〜３で説明した内容を以下に記す。
【０１０２】
実施の形態１では、
実行リソースに実行させるタスクを受け付ける受付部と、
前記受付部が受け付けた前記タスクの実行内容を格納する記憶部と、
前記記憶部に格納された前記タスクの実行内容を前記実行リソースに実行させる駆動部と、
を備えるスケジューリング装置であって、
前記記憶部は複数の格納領域からなり、
前記受付部は受け付けた前記タスクの実行内容を前記記憶部のいずれか１つの格納領域に記憶させ、
前記駆動部は所定時間ごとに前記記憶部のいずれか１つの格納領域を選択し、
当該格納領域に記憶された前記タスクの実行内容を順次取り出して前記実行リソースに実行させ、
当該格納領域に記憶された前記タスクを全て前記実行リソースに実行させた後に、
当該格納領域から前記タスクの実行内容を全て削除し、
当該格納領域と異なる前記格納領域のいずれか１つを次の所定時間における実行対象とするスケジューリング装置を説明した。
【０１０３】
また、実施の形態１では、
前記タスクは、複数の前記実行リソースのいずれか１つに対応付けられ、
前記駆動部は前記記憶部のいずれか１つの格納領域から前記タスクの実行内容を取り出すとともに、
当該タスクに対応付けられた前記実行リソースのいずれか１つに当該タスクの実行内容を実行させる
ことを説明した。
【０１０４】
また、実施の形態１では、
実行リソース管理情報を記憶する実行リソース管理テーブルをさらに備える前記スケジューリング装置であって、
前記実行リソース管理情報は前記記憶部に格納された前記タスク数を表す実行待ちタスク数を含み、
前記受付部は、受け付けた前記タスクの実行内容を、前記実行リソース管理情報の前記実行待ちタスク数に基づいて選択した前記記憶部のいずれか１つの格納領域に記憶させるとともに、
前記実行リソース管理情報の前記実行待ちタスク数に１を加え、
前記駆動部は前記格納領域から前記タスクの実行内容を取り出して前記実行リソースに実行させるとともに、
前記実行リソース管理情報の前記実行待ちタスク数から１を減じるスケジューリング装置を説明した。
【０１０５】
また、実施の形態１では、
前記タスクは、複数の前記実行リソースのいずれか１つに対応付けられ、
前記実行リソース管理テーブルは、前記実行リソースと１対１に対応して実行リソース管理情報を複数記憶し、
前記受付部及び前記駆動部は、前記タスクに対応付けられた前記実行リソースに対応する前記実行リソース管理情報を参照及び更新の対象とすることを説明した。
【０１０６】
また、実施の形態３では、
前記タスクは有限数の優先度のいずれか１つと対応付けられており、
前記実行リソース管理情報の前記実行待ちタスク数は、前記優先度に対応して複数の値を保持し、
前記受付部は、受け付けた前記タスクの実行内容を、前記実行リソース管理情報の前記実行待ちタスク数の複数の値の内、前記タスクの前記優先度に対応する値に基づいて選択した前記記憶部のいずれか１つの格納領域に記憶させるとともに、
前記実行リソース管理情報の前記実行待ちタスク数の複数の値の内、前記タスクの前記優先度に対応する値に１を加え、
前記駆動部は前記格納領域から前記タスクの実行内容を取り出して前記実行リソースに実行させるとともに、
前記実行リソース管理情報の前記実行待ちタスク数の複数の値の内、前記タスクの前記優先度に対応する値から１を減じることを説明した。
【０１０７】
また、実施の形態１では、
前記実行リソース管理情報はさらに、
前記実行リソースに実行させたタスク数の累計を表す実行済みタスク数と、
前記実行リソースによるタスク実行時間の実績の平均値を表す平均タスク実行時間と、
を含み、
前記受付部は、受け付けた前記タスクの実行内容を、前記実行リソース管理情報の前記実行待ちタスク数と前記平均タスク実行時間に基づいて選択した前記記憶部のいずれか１つの格納領域に記憶させ、
前記駆動部は前記実行リソースによる前記タスクの実行内容の実行が完了した際に、
当該タスクの実行時間と、
前記実行リソース管理情報の前記実行済みタスク数と、
前記平均タスク実行時間と、
に基づいて前記実行リソース管理情報の前記平均タスク実行時間を更新することを説明した。
【０１０８】
実施の形態２では、
前記タスクは固有の実行周期ごとの実行を要求される周期タスクと、
１回限りの実行を要求される非周期タスクと、からなり、
前記実行リソース管理情報はさらに、
前記周期タスクの全てに関する前記実行周期の逆数の和を表す周期タスク実行頻度を含み、
実施の形態１に示した前記受付部は、受け付けた前記タスクが前記周期タスクである場合に、
当該周期タスクの実行内容を、前記駆動部の現在の処理対象である前記格納領域の１つに記憶させるとともに、
前記実行周期を前記実行リソース管理情報の前記周期タスク実行頻度に加え、
前記実行待ちタスク数に１を加えず、
受け付けた前記タスクが前記非周期タスクである場合に、
当該非周期タスクの実行内容を、
前記実行リソース管理情報の前記実行待ちタスク数と、前記平均タスク実行時間と、前記周期タスク実行頻度と、
に基づいて選択した前記記憶部のいずれか１つの格納領域に記憶させるとともに、
前記実行待ちタスク数に１を加え、
実施の形態１に示した前記駆動部は前記実行リソースによる前記周期タスクの実行内容の実行が完了した際に、
前記実行待ちタスク数から１を減じず、
前記周期タスクの実行内容を前記実行周期に基づいて選択した前記記憶部のいずれか１つの格納領域に記憶させるスケジューリング装置を説明した。
【０１０９】
また、実施の形態３では、
前記タスクは有限数の優先度のいずれか１つと対応付けられており、
前記実行リソース管理情報の前記周期タスク実行頻度は、前記優先度に対応して複数の値を保持し、
前記受付部は、
受け付けた前記周期タスクの前記実行周期を、前記実行リソース管理情報の前記周期タスク実行頻度の複数の値の内、前記周期タスクの前記優先度に対応する値に加え、
受け付けた前記非周期タスクの実行内容を、
前記実行リソース管理情報の前記実行待ちタスク数の複数の値の内、前記非周期タスクの前記優先度に対応する値と、前記平均タスク実行時間と、前記周期タスク実行頻度の複数の値の内、前記優先度に対応する値と、
に基づいて選択した前記記憶部のいずれか１つの格納領域に記憶させることを説明した。
【０１１０】
また、実施の形態１では、
前記記憶部は、所定の整数をＴとして、Ｔ個の格納領域からなり、
前記受付部は、受け付けた前記タスクの実行内容を記憶させる前記記憶部の前記格納領域のいずれか１つを選択する際に、
前記実行リソース管理情報の前記実行待ちタスク数と前記平均タスク実行時間の積を、
前記駆動部が動作する所定時間で除した値の整数部分に１を加えたものを指標とし、
前記指標が１であれば第１の格納領域を選択し、
前記指標がｔ（ｔは２以上Ｔ未満の整数）であれば第ｔの格納領域を選択し、
前記指標がＴ以上であれば第Ｔの格納領域を選択することを説明した。
【０１１１】
また、実施の形態２では、
前記記憶部は、所定の整数をＴとして、Ｔ個の格納領域からなり、
前記受付部は、受け付けた前記タスクの実行内容を記憶させる前記記憶部の前記格納領域のいずれか１つを選択する際に、
前記実行リソース管理情報の前記実行待ちタスク数をＡ、
前記平均タスク実行時間をＥ、
前記周期タスク実行頻度をＰ、
前記駆動部が動作する所定時間をＵとして、
（Ａ／（１／Ｅ−Ｐ）／Ｕ）の整数部分に１を加えたものを指標とし、
前記指標が１であれば第１の格納領域を選択し、
前記指標がｔ（ｔは２以上Ｔ未満の整数）であれば第ｔの格納領域を選択し、
前記指標がＴ以上であれば第Ｔの格納領域を選択することを説明した。
【０１１２】
また、実施の形態１では、
前記記憶部は、高速に読み書き可能で小容量の第１の記憶部と、低速で大容量の第２の記憶部からなり、
前記第１の記憶部と前記第２の記憶部のそれぞれごとに、複数の格納領域を１対１に対応させて設け、
前記受付部は、受け付けた前記タスクの実行内容を記憶させる際に、
前記第１の記憶部に空きがあれば前記第１の記憶部の前記格納領域のいずれか１つに前記タスクの実行内容を記憶させ、
前記第１の記憶部に空きがなければ前記第１の記憶部の前記格納領域のそれぞれごとに、前記第１の記憶部の前記格納領域の内容を当該格納領域に対応する前記第２の記憶部の前記格納領域の１つに記憶させた後に、
前記第１の記憶部の前記格納領域を全て空にし、
前記第１の記憶部の前記格納領域のいずれか１つに前記タスクの実行内容を記憶させることを説明した。
【０１１３】
最後に、実施の形態１〜３に示したスケジューリング装置１のハードウェア構成例について説明する。
図１７は、実施の形態１〜３に示すスケジューリング装置１のハードウェア資源の一例を示す図である。
なお、図１７の構成は、あくまでもスケジューリング装置１のハードウェア構成の一例を示すものであり、スケジューリング装置１のハードウェア構成は図１７に記載の構成に限らず、他の構成であってもよい。
【０１１４】
図１７において、スケジューリング装置１は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７と接続していてもよい。また、磁気ディスク装置９２０の代わりに、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
実施の形態１で説明したように、格納領域７ａ〜７ｄは、例えば磁気ディスク装置９２０上に構成され、書込バッファ８ｂ〜８ｄ及び読込バッファ９はＲＡＭ９１４上に構成される。
通信ボード９１５、キーボード９０２、マウス９０３、スキャナ装置９０７などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。
【０１１５】
通信ボード９１５は、ＬＡＮに接続されている。
また、通信ボード９１５は、ＬＡＮを介して、インターネット、ＷＡＮ（ワイドエリアネットワーク）、ＳＡＮ（ストレージエリアネットワーク）などに接続可能である。
【０１１６】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【０１１７】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【０１１８】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
スケジューリング装置１の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【０１１９】
上記プログラム群９２３には、実施の形態１〜３の説明において「〜部」（「記憶部」及び「実行リソース管理テーブル保持部」以外、以下同様）として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【０１２０】
ファイル群９２４には、実施の形態１〜３の説明において、「〜の判断」、「〜の判定」、「〜の選択」、「〜の指定」、「〜の決定」、「〜の設定」、「〜の更新」、「〜の生成」、「〜の作成」、「〜の反映」、「〜の比較」、「〜の登録」、「〜の取得」、「〜の入力」、「〜の出力」等として説明している処理の結果を示す情報やデータや信号値や変数値や暗号鍵・復号鍵や乱数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。
ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出される。
そして、読み出された情報やデータや信号値や変数値やパラメータは、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、実施の形態１〜３で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示す。
データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。
また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【０１２１】
また、実施の形態１〜３の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。
すなわち、実施の形態１〜３で説明したフローチャートに示すステップ、手順、処理により、本発明に係る「情報処理方法」を実現することができる。
また、「〜部」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。
或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。
ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。
プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。
すなわち、プログラムは、実施の形態１〜３の「〜部」としてコンピュータを機能させるものである。あるいは、実施の形態１〜３の「〜部」の手順や方法をコンピュータに実行させるものである。
【０１２２】
このように、実施の形態１〜３に示すスケジューリング装置１は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータである。
そして、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【符号の説明】
【０１２３】
１  スケジューリング装置、２  タスク要求、２ａ  タスク情報、３  実行リソース、４  タスク受付部、５  タスク駆動部、６  実行リソース管理テーブル、６ａ  実行リソース管理情報、７  格納領域、８  書込バッファ、９  読込バッファ、６０  実行リソース管理テーブル保持部。
【図１】
0005791478.tif 000002
【図２】
0005791478.tif 000003
【図３】
0005791478.tif 000004
【図４】
0005791478.tif 000005
【図５】
0005791478.tif 000006
【図６】
0005791478.tif 000007
【図７】
0005791478.tif 000008
【図８】
0005791478.tif 000009
【図９】
0005791478.tif 000010
【図１０】
0005791478.tif 000011
【図１１】
0005791478.tif 000012
【図１２】
0005791478.tif 000013
【図１３】
0005791478.tif 000014
【図１４】
0005791478.tif 000015
【図１５】
0005791478.tif 000016
【図１６】
0005791478.tif 000017
【図１７】
0005791478.tif 000018