ジョブスケジューリング方法
【課題】ＣＰＵ１３の能力を効率的に使うことができるジョブスケジューリング方法を提供する。
【解決手段】ジョブ管理情報を基に、ＣＰＵ１３が、予約時間内に複数の処理を実行する定周期実行方式のスケジューリングを行う、ジョブスケジューリング方法であって、ジョブ管理情報が、複数の処理のそれぞれの優先度情報と、複数の処理のそれぞれを実行可能な複数のジョブの実行時間情報とを有し、ＣＰＵ１３の空き時間が生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。
【解決手段】ジョブ管理情報を基に、ＣＰＵ１３が、予約時間内に複数の処理を実行する定周期実行方式のスケジューリングを行う、ジョブスケジューリング方法であって、ジョブ管理情報が、複数の処理のそれぞれの優先度情報と、複数の処理のそれぞれを実行可能な複数のジョブの実行時間情報とを有し、ＣＰＵ１３の空き時間が生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の処理を定周期実行方式で行う際のジョブスケジューリング方法に関する。
【背景技術】
【０００２】
一つのプロセッサを用いて異なる複数の処理を事実上、同時進行で行うマルチタスク処理においては、それぞれの処理を行う時間を予め予約時間として割り当てる定周期実行方式の処理が知られている。定周期実行方式の処理では、それぞれの処理は設定された定周期の時間で繰り返し実行される。また、データサンプリングのように、所定のサンプリング時間内に一連の予め定められた処理を繰り返し実行する処理も、サンプリング時間を予約時間と考えれば、定周期実行方式の一つの類型である。定周期実行方式では、予約時間内に処理を完了するために、予め、プロセッサが、それぞれの処理を実行するためのジョブの実行に要する時間をジョブ管理情報として記憶している。そして、定周期実行方式では、ジョブ管理情報を基に予約時間内に処理を完了するように、複数のジョブをキューとして登録するスケジューリングを行うスケジューラが用いられている。スケジューラは、予約時間内に処理を完了するだけでなく、処理の事象待ち、すなわちプロセッサの待機状態による無駄な空き時間を削減するために、ジョブ管理情報を基に、無駄な空き時間を最小とするスケジューリングを行う。
【０００３】
しかし、全く同じジョブの処理であっても、プロセッサが実際に処理を完了するまでの時間は常に一定という訳ではない。これはプロセッサ自体の処理速度の変動だけでなく、周辺バスの転送速度等、種々の要因による。このため、必ず予約時間内に処理を完了するためには、ジョブ管理情報として記憶しておく特定のジョブに要する時間は、最も時間がかかる最悪実行時間(WCET: Worst-Case Execution Time)を記憶しておく必要がある。
【０００４】
このため、プロセッサが実際に処理を完了するまでの時間が、最悪実行時間よりも短い場合には、プロセッサの空き時間が増加してしまい、プロセッサの能力を効率的に使うことが出来ないという問題があった。前記問題は、実行時間の変動が大きい処理の場合に特に顕著であった。
【０００５】
このため、特許文献１には、ＣＰＵの待ち時間が、指定値を越えると、優先度の高いタスクと優先度の低いタスクとを交互にスケジューリングするタスクスケジューリング方式が開示されている。
【０００６】
ここで、近年のテレビジョン受像機においては、デジタル化により複雑な多数の処理を同時並行で行うため、マルチコアプロセッサ、例えば1つのCPUの中に1個の汎用的なプロセッサコアと、8個のシンプルなプロセッサコアを組み合わせたヘテロジニアスマルチコアが使用されている。しかし、テレビジョン受像機においては、１秒間に６０枚の画像すなわち、奇数と偶数の走査線毎に３０枚／秒の計６０枚／秒の画像を表示しなければならない。このため、複数の処理を、１／３０秒を周期とする定周期実行方式で行うためのジョブスケジューリングが重要となっている。
【０００７】
またテレビジョン受像機のモニタの大画面化に伴い、複数のチャンネルおよび／または入力端子等から入力された複数の入力画像信号から取り出した複数の画像を、複数の領域に分割されたひとつの表示画面の各領域に表示するマルチ画面表示機能が利用されるようになってきている。
【０００８】
マルチ画面表示機能を持つテレビジョン受信機では、複数の入力画像信号の中から選択された複数の画像信号のそれぞれを、マルチ画面処理回路にて画像サイズ変換処理およびフォーマット変換処理してから１つの表示画面として合成する必要がある。このため、ジョブスケジューリングでは、少なくとも画像サイズ変換処理とフォーマット変換処理とを行うための予約時間を設定している。
【０００９】
しかし、マルチ画面表示する画像の数、すなわち入力画像信号の数によりマルチ画面処理回路が処理に要する時間は変化する。また、ヘテロジニアスマルチコアの他のプロセッサコアで動作しているプログラムがバンド幅を圧縮する処理を行ったりすると、マルチ画面処理しているＣＰＵの速度も影響を受けて遅くなることがある。
【００１０】
このため、最悪実行時間を基にした予定時間を用いると、プロセッサの空き時間が増加してしまい、プロセッサの能力を効率的に使うことが出来ないという問題が顕著であった。
【００１１】
本発明は上記問題に鑑みてなされたものであり、プロセッサの能力を効率的に使うことができるジョブスケジューリング方法を提供するものである。
【特許文献１】特開平４−１９１９３５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、プロセッサの能力を効率的に使うことができるジョブスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本願発明の一態様によれば、ジョブ管理情報を基に、ＣＰＵが、予約時間内に複数の処理を実行する定周期実行方式のスケジューリングを行う、ジョブスケジューリング方法であって、ジョブ管理情報が、複数の処理のそれぞれの優先度情報と、複数の処理のそれぞれを実行可能な複数のジョブの実行時間情報とを有し、ＣＰＵの空き時間が生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択することを特徴とするジョブスケジューリング方法が提供される。
【発明の効果】
【００１４】
本発明は、プロセッサの能力を効率的に使うことができるジョブスケジューリング方法を提供するものである。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の実施の形態を説明する。
＜第１の実施の形態＞
＜スケジューラの構成＞
最初に、図１から図５を用いて、本発明の第１の実施の形態にかかるスケジューラ１００の構成について説明する。
【００１６】
図１は、本実施の形態にかかるマルチ画面処理回路１１を有するテレビジョン受像機１の構成を示した構成図であり、図２はテレビジョン受像機１のマルチ画面の例を示した図であり、図３は、スケジューラ１００のブロック図であり、図４は、ジョブ管理情報１０５の例を示した表であり、図５は、画像サイズ変換処理Ａ２が実行可能なアルゴリズムが異なる複数のジョブを説明するための説明図である。
【００１７】
図１に示すように、本実施の形態にかかるテレビジョン受像機１は、多数の入力画像信号の中から選択された複数の画像信号をいったんメモリ１５に記憶し、そのデータを基に、マルチ画面処理回路１１にて、それぞれの画像信号の画像サイズ変換処理と、フォーマット変換処理を行い、再びメモリ１５を介して、１つの表示画面として画像出力手段であるモニタ１２に出力する。例えば、パラボラアンテナ２で受信されたデジタルテレビ放送の信号は、放送局および放送仕様により、それぞれ異なるデコーダーで処理される。図１では、簡略化し、４個のデコーダー４、５、６、７からなるデコーダー群を図示している。また、内蔵ハードディスクドライブ（ＨＤＤ）８に記録された画像信号や、外部端子９に接続された図示しないビデオカメラまたはゲーム機からの画像信号も、テレビジョン受像機１には入力される。これら複数の入力画像信号の中から切替回路１０により選択された画像信号がマルチ画面処理回路１１にて処理される。マルチ画面処理回路１１は、複数の画像信号を、１つの表示画像信号に合成する回路である。
【００１８】
マルチ画面処理回路１１の、ＣＰＵ１３は、１秒間に６０枚の画像すなわち、奇数と偶数の走査線毎に３０枚／秒の画像信号を処理するために、１／３０秒を周期とする定周期実行方式のジョブスケジューリングを行うスケジューラ１００が登録したキューメモリ情報に従い処理を行う。なお、ＣＰＵ１３は、マルチ画面処理回路１１の処理だけでなく、別の処理Ｂも、１／３０秒を周期とする定周期実行方式にて処理している。
【００１９】
次に、図２に、マルチ画面処理回路１１により合成されたマルチ画面を表示したテレビジョン受像機のモニタ表示画面２０の例を示す。図２（Ａ）は、通常の１画面２０Ａを表示しており、図２（Ｂ）は同じ大きさの２つの画面２０Ｂ、２０Ｃを並べて表示したダブルウィンドウ画面を示しており、図２（Ｃ）は、小さな子画面２０Ｄと、大きな親画面２０Ｅを並べて表示したダブルウィンドウ画面を示しており、図２（Ｄ）は、４つの画面２０Ｆ、２０Ｇ、２０Ｈ、２０Ｉを同時に表示したマルチウィンドウ画面を示している。通常の画面２０Ａは、（１９２０×１０８０）画素で表示されているが、マルチ画面の各画面は、縮小して表示されている。すなわち、画面２０Ｂ、２０Ｃ、２０Ｆ、２０Ｇ、２０Ｈおよび２０Ｉは、いずれも通常画面２０Ａの半分の（９６０×５４０）画素で表示され、２０Ｄは通常画面２０Ａの４分の１の（４８０×２７０）画素で表示され、２０Ｅは通常画面２０Ａの４分の３の（９６０×５４０）画素で表示されている。
【００２０】
次に、図３に、本実施の形態にかかるスケジューラ１００のブロック図を示す。スケジューラ１００は、ＣＰＵ１３が実行するジョブをキュー（Ｑｕｅｕｅ）として、キューメモリ１０８に登録する、すなわち、スケジューリングを行う。図２に示したようなマルチ画面を表示するために、マルチ画面処理回路１１は、少なくとも２つの異なる目的の処理を実行しなければならない。すなわち、元の画像信号のフォーマットを変換するフォーマット変換処理（以下、処理Ａ１という。）と、元の画像信号の画像サイズを変換する画像サイズ変換処理（以下、処理Ａ２という。）である。元の画像信号の画像サイズとしては、HD(1920×1080)やSD（720×480）等があるが、ここでは、元の画像信号の画像サイズをHDとし、処理A2を縮小する画像サイズ変換処理として説明する。もちろん、拡大する画像サイズ変換もある。
【００２１】
以下、処理Ａ１と処理Ａ２を合わせて処理Ａとし、処理Ａと共に同じＣＰＵで定周期実行する処理を処理Ｂとする。ここで、図３に示したキューメモリ１０８に登録されたキューは、定周期時間である３０分の１秒すなわち約３３ｍｓを四角形の縦の長さで表現し、そのうちの処理Ａを実行する予約時間が、例えば定周期時間の７０％であることを表している。処理Ａと処理Ｂのそれぞれの予約時間は再設定することが可能であるが、以下は、予約時間が固定されている状態のジョブスケジューリングについて説明する。すなわち、処理Ａは、約３３ｍｓの定周期時間の７０％である約２３ｍｓで、処理Ａ１と処理Ａ２を実行する例について説明する。
【００２２】
図３に示すように、スケジューラ１００は、キューメモリ１０８にジョブを登録するために、ジョブ管理情報メモリ１０５に記憶されている情報を基に、ジョブを選択する選択器１０３と、選択器１０３が選択したジョブをキューメモリ１０８に登録するリセット器１０２から構成されている。また、検出器１０４は定周期スケジューラ上で走る一連のプロセスのＣＰＵ１３の利用状況に関するデータを収集するものであり、例えば、登録されたキューメモリ１０８の情報に従い、ＣＰＵ１３が処理を行った時に処理を完了するまでに要した実際の時間（以下、「実測実行時間」という。）を検出する。
【００２３】
ジョブ管理情報メモリ１０５は、処理を実際に実行する複数のジョブの管理情報を記憶するメモリであり、図４に示すように本実施の形態のジョブスケジューリング方法においては、処理開始時には、少なくとも処理の優先度情報とジョブの最悪実行時間情報とを含む基本情報１０７を有している。基本情報１０７は処理開始前に定周期時間等と共にパラメータとして入力される。また、ジョブ管理情報メモリ１０５は、処理開始後に検出器１０４の情報を基に入力される実測実行時間情報である動的情報１０６も有している。
【００２４】
本実施の形態のジョブスケジューリングでは、図４に示すように、ある一つの処理が実行可能な複数のジョブから一のジョブを選択しスケジューリングを行う。ここでは、元の画像信号の画像サイズを縮小するという画像サイズ変換処理Ａ２に対して、ジョブＡ２１、ジョブＡ２２およびジョブＡ２３という３つのジョブを用いる例を示している。ジョブＡ２１、ジョブＡ２２およびジョブＡ２３は、それぞれが画像サイズ変換処理を単独で実行することが可能なジョブである。しかし、３つのジョブは、以下に説明するように画像サイズ変換処理を行うためのアルゴリズムが異なる。
【００２５】
ここで、図５を用いて、画像サイズ変換処理、すなわち、元の画像信号の画像サイズを縮小する処理に用いるジョブについて説明する。例えば、図２（Ｄ）に示したように、４つの画像を同時に画面に表示するためには、それぞれの画像サイズを４分の１に縮小しなければならない。なお、画像サイズを縮小するジョブには種々の異なるアルゴリズムを用いることができるが、ここでは説明を簡単にするために画素データを用いた簡単なアルゴリズムの例を用いて説明する。
【００２６】
すなわち、図５のａで示したように、元のフル画素データが横６画素縦４画素の２４画素から構成されている場合、画像サイズを４分の１に縮小するとは、横３画素縦２画素の６画素に変換することである。アルゴリズムａ２１では、フル画素データを縦２画素横２画素の４画素の中から、ランダムに１画素を選択し、その画素を集合して縮小画像データを作成する、いわゆる間引きアルゴリズムである。これに対して、アルゴリズムａ２２は、フル画素データの、縦２画素横２画素の４画素の情報を平均化して新規な画素を作成し、その画素を集合して縮小画像データを作成する、いわゆる単純平均化アルゴリズムである。アルゴリズムａ２３は、やはり縦３画素横３画素の９画素の情報を平均化する平均化アルゴリズムであるが、単純に平均化するのではなく、中心画素からの距離に応じて縮小画素への寄与度を変える。このため、フル画素のうちの１つの画素の情報が、複数の縮小画素に重み付けして反映される、いわゆる複合平均化アルゴリズムである。
【００２７】
間引きアルゴリズムであるアルゴリズムａ２１は最も簡単なアルゴリズムであるため、アルゴリズムａ２１を用いるジョブＡ２１は、図４に示すように、処理時間が短く、例えば最悪実行時間は１５ｍｓである。しかし、アルゴリズムａ２１は単なる間引きであるので、縮小された画像の品質は良くない、すなわち、アルゴリズムａ２１は処理の結果品質は低い。これに対して、単純平均化アルゴリズムであるアルゴリズムａ２２は比較的簡単なアルゴリズムであるため、アルゴリズムａ２２を用いるジョブＡ２２は、図４に示すように、処理時間が比較的短く、例えば最悪実行時間は２５ｍｓである。また、アルゴリズムａ２２は平均化処理しているので、縮小された画像の品質は普通、すなわち、アルゴリズムａ２２は処理の結果品質は中である。そして、複合平均化アルゴリズムであるアルゴリズムａ２３は複雑であるため、アルゴリズムａ２３を用いるジョブＡ２３は、図４に示すように、処理時間が長く、例えば最悪実行時間は３５ｍｓである。しかし、アルゴリズムａ２３は多数の画素を重み付けして平均化処理しているので、縮小された画像の品質はよい、すなわち、アルゴリズムａ２３は処理の結果品質は高である。
【００２８】
なお、上記説明で、例えば、アルゴリズムａ２１によるジョブ２１の処理の結果品質が低いといっても、他の処理時間が長いアルゴリズムによるジョブと比較しての相対的な品質であり、絶対的な品質が低いわけでなく、ジョブ２１の処理も、実用上、十分な結果品質を有している。
【００２９】
また、図４に示すように、元の画像信号のフォーマットを変換するフォーマット変換処理である処理Ａ１についても、処理Ａ１が実行可能な複数のジョブＡ１１、ジョブＡ１２およびジョブＡ１３という３つのジョブを用いる。ジョブＡ１１は簡単なアルゴリズムのため、処理時間が短く、例えば最悪実行時間は７ｍｓである。しかし、ジョブＡ１１は単純な処理のため、変換された画像の品質は悪い、すなわち、ジョブＡ１１は処理の結果品質は低である。これに対してジョブＡ１２は、やや簡単なアルゴリズムのため、処理時間が比較的短く、例えば最悪実行時間は１０ｍｓである。そして、ジョブＡ１２は変換された画像の品質は普通、すなわち、処理の結果品質は中である。そして、ジョブＡ１３は複雑なアルゴリズムのため、処理時間が長く、例えば最悪実行時間は１５ｍｓである。しかし、ジョブＡ１３は変換された画像の品質はよい、すなわち、処理の結果品質は高である。
【００３０】
なお、図４のジョブ管理情報処理に示したように、フォーマット変換処理である処理Ａ１の優先度は２であり、画像サイズ変換処理である処理Ａ２の優先度１よりも低く設定されている。優先度は基本情報１０７として処理の開始前に入力される。また、ジョブの実測実行時間ＴＡ１およびＴＡ２は後述するように、処理が実行された後に検出器１０４により記録される。
【００３１】
なお、図４に示したジョブ管理情報において、アルゴリズムと結果品質は説明のために付加したものであり、実際のジョブ管理情報には含まれていなくてもよい。
【００３２】
＜スケジューリング方法＞
次に、図６および図７を用いて、本実施の形態のスケジューリング方法について説明する。図６は、本実施の形態のスケジューラ１００によるスケジューリング処理の流れを説明するためのフローチャートであり、図７は、スケジューラ１００による再スケジューリングＡを説明するための説明図である。
【００３３】
以下、図６のフローチャートに従い、本実施の形態のスケジューリング方法について説明する。
【００３４】
本実施の形態のスケジューリング方法においては、ＣＰＵ１３の空き時間Ｔｉが生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。なお、ここで、空き時間が生じる場合とは、実際に空き時間Ｔｉが生じた場合、および／または生じる見込みの場合を意味する。また、実際に空き時間Ｔｉが生じた場合であっても、次の定周期処理において必ず空き時間Ｔｉが生じるわけではない。
【００３５】
＜ステップＳ１０＞
処理の開始前に、処理パラメータとして、ジョブ管理情報メモリ１０５に、ジョブ管理情報の基本情報１０７と定周期時間とが入力される。図４に示すように、ジョブ管理情報メモリ１０５に記憶された基本情報１０７は、複数の処理の処理名、Ａ１およびＡ２の優先度情報と、処理Ａ１が実行可能な複数のジョブのジョブＩＤであるＡ１１、Ａ１２およびＡ１３とそれぞれのジョブの最悪実行時間情報と、処理Ａ２が実行可能な複数のジョブのジョブＩＤであるＡ２１、Ａ２２およびＡ２３とそれぞれの最悪実行時間情報である。この時点において、ジョブ管理情報メモリ１０５の動的情報１０６、すなわちジョブの実測実行時間は、登録されていなくてもよいし、前回の処理の際の情報が含まれていてもよい。
【００３６】
＜ステップＳ１１＞
選択器１０３は、処理開始時点においては、複数の処理の各ジョブを、基本情報１０７の優先度情報と最悪実行時間情報とを基に、ＣＰＵ１３の空き時間Ｔｉが最小となるように選択し、キューメモリ１０８に登録する。すなわち、図８のスケジュールＡ０に示すように、選択器１０３は、予約時間の中で、ＣＰＵの空き時間Ｔｉが最小となるように、優先度に基づき、処理Ａ１および処理Ａ２を実行可能な複数のジョブの中から、それぞれ１つのジョブを選択する。
【００３７】
例えば、予約時間が２３ｍｓの場合は、選択器１０３は、まず優先度１の処理Ａ２から最悪実行時間１５ｍｓのジョブＡ２１を選択し、次に優先度２の処理Ａ１から最悪実行時間７ｍｓのジョブＡ１１を選択する。すると、図７のスケジュールＡ０に示すように、予約時間２３ｍｓに対して、空き時間Ｔｉは１ｍｓとなる。
【００３８】
なお、選択器１０３は、各ジョブの実測実行時間情報が、ジョブ管理情報メモリ１０５の動的情報１０６に記憶されている場合には、最悪実行時間情報の替わりに、実測実行時間情報を用いて各ジョブを選択する。すなわち、選択器１０３が最悪実行時間情報を基にジョブ選択を行うのは、それぞれのジョブが未実行の場合である。
【００３９】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したキューメモリ１０８の情報に従い、処理Ａ１をジョブＡ１１で、実行する。
【００４０】
＜ステップＳ１３＞
処理Ａ１が完了すると、検出器１０４は、処理Ａ１のジョブＡ１１の実測実行時間ＴＡ１であるｔＡ１１を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ１１、例えば４ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００４１】
＜ステップＳ１４＞
次に、検出器１０４は、実行予定のジョブＡ２１のジョブ管理情報メモリ１０５に記憶されている実行時間と予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００４２】
例えば、図７の実行結果１に示すようにジョブＡ１１の実測実行時間ｔＡ１１が４ｍｓの場合、最悪実行時間は７ｍｓだったため、３ｍｓの空き時間Ｔｉが生じる。このため、検出器１０４は、スケジュールＡ０での空き時間Ｔｉ１ｍｓと合わせると４ｍｓ以上の空き時間Ｔｉが生じると推算する。
【００４３】
＜ステップＳ１５＞
スケジューラ１００は、推定されたＣＰＵ１３の空き時間Ｔｉが、再スケジューリングＡを行うことができる程、生じるかを検討する。すなわち、処理Ａ２の複数のジョブの中で、実行予定のジョブＡ２１の次に実行時間の長いジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、最悪実行時間の２５ｍｓでありジョブＡ２１よりも１０ｍｓも長く、推算された空き時間Ｔｉ４ｍｓよりも長い。
【００４４】
このため、ジョブＡ２１をジョブＡ２２に入れ替えると、残りの予約時間内にジョブＡ２２を実行することはできない可能性が高い。このため、スケジューラ１００は、空き時間Ｔｉは十分ではないと判断（Ｎｏ）し、ステップＳ１９において処理終了（Ｎｏ）でなければ、再びステップＳ１２において、ＣＰＵ１３は未実行のジョブＡ２１を実行する。
【００４５】
なお、ＣＰＵ１３は、処理Ａの後に、キュー情報に従い処理Ｂを実行するが、以降の説明においては省略する。
【００４６】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ１に示したキューメモリ１０８の情報に従い、処理Ａ２をジョブＡ２１で実行する。
【００４７】
＜ステップＳ１３＞
処理Ａ２が完了すると、検出器１０４は、処理Ａ２のジョブＡ２１の実測実行時間ＴＡ２であるｔＡ２１を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ２１、例えば９ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００４８】
＜ステップＳ１４＞
さらに検出器１０４は、図７の実行結果２に示すように、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ１１の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。なお、ここで推算するとは実測実行時間から空き時間Ｔｉを算出し、次回の処理における空き時間Ｔｉと推定することである。
【００４９】
＜ステップＳ１５＞
スケジューラ１００は、推算されたＣＰＵ１３の空き時間Ｔｉが、再スケジューリングＡを行うことができる程、生じるかを検討する。
【００５０】
この場合には、次に実行する予定の処理が、処理Ａ１および処理Ａ２と複数であるため、優先度に基づき、まず優先度の高い処理Ａ２について検討する。ここでは、１０ｍｓの空き時間Ｔｉが生じるため、スケジューラ１００は、処理Ａ２の複数のジョブの中で、実行予定のジョブＡ２１の次に実行時間の長いジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、最悪実行時間の２５ｍｓであるが、ジョブＡ２１よりも、ちょうど１０ｍｓ長い。このため、ジョブＡ２１をジョブＡ２２に入れ替えても予約時間内にジョブＡ２２を実行できる可能性が高い。このため、スケジューラ１００は、再スケジューリングＡを行うための空き時間Ｔｉは十分と判断（Ｙｅｓ）し、ステップＳ１６に進む。
【００５１】
＜ステップＳ１６＞
なお、再スケジューリングＡでは、選択器１０３は、複数のジョブの中で、処理の優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。処理時間の長い複雑なアルゴリズムを用いるジョブは結果品質が高いからである。また、空き時間Ｔｉが生じたとしても、その空き時間Ｔｉは最悪実行時間で保証されたものではないため、選択器１０３は、予約時間内に処理が完了しないことがないように、前回選択され、予約時間内に処理が完了できたジョブの次に実行時間の長いジョブを選択する。
【００５２】
また、処理の優先度に基づいてジョブを選択するため、優先度の高い処理の品質を優先して上げることができる。なお、スケジューラ１００が、処理の優先度に基づいてジョブを選択する際には、結果品質のバランスを考慮し選択することが好ましい。すなわち、スケジューラ１００が、最初に優先度の最も高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択する再スケジューリングＡを行った場合には、次の再スケジューリングＡでは、優先度が２番目に高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択し、そして次の再スケジューリングＡでは、優先度が３番目に高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択していき、最も優先度が低い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択する再スケジューリングＡの後に、優先度の最も高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択する再スケジューリングＡを行う。複数の処理の中で優先度が高い処理のみの結果品質が突出して高くても、マルチ画面処理回路１１の全体としての結果品質が、高くはならない場合があるからである。
【００５３】
ここでは、選択器１０３は、優先度１の処理Ａ２のジョブ中で、ステップＳ１１で選択されたジョブＡ２１の次に実行時間の長いジョブＡ２２を選択し、リセット器１０２はキューメモリ１０８を、図７に示すスケジュールＡ１のように、リセットする。
【００５４】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ１に示したキューメモリ１０８の情報に従い、処理Ａ１をジョブＡ１１で実行する。
【００５５】
＜ステップＳ１３＞
処理Ａ１が完了すると、検出器１０４は、処理Ａ１のジョブＡ１１の実測実行時間ＴＡ１であるｔＡ１１を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ１１、例えば４ｍｓ、を、再びジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００５６】
＜ステップＳ１４＞
さらに検出器１０４は、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ２２の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００５７】
例えば、図７の実行結果３に示すように、ジョブＡ１１の実測実行時間ｔＡ１１が、再び、４ｍｓの場合、次に実行予定の処理Ａ２のジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、前回実行したジョブ２１より最悪実行時間で１０ｍｓ長いことから、ちょうど２３ｍｓで全ての処理が完了することになる。すなわち、予約時間２３ｍｓに対して空き時間Ｔｉは生じない。
【００５８】
＜ステップＳ１５＞
空き時間Ｔｉが生じないので、スケジューラ１００は、空き時間Ｔｉは十分ではないと判断（Ｎｏ）し、ステップＳ１９を経て、再びステップＳ１２において、未実行のジョブＡ２２を実行する。
【００５９】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ１に示したキューメモリ１０８の情報に従い、処理Ａ２をジョブＡ２２で実行する。
【００６０】
＜ステップＳ１３＞
処理Ａ２が完了すると、検出器１０４は、処理Ａ２のジョブＡ２２の実測実行時間ＴＡ２であるｔＡ２２を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ２２、例えば１５ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００６１】
＜ステップＳ１４＞
さらに検出器１０４は、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ１１の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００６２】
例えば、図７の実行結果４に示すように、ジョブＡ２２の実測実行時間ｔＡ２２が１５ｍｓの場合、既に実行したジョブＡ１１の実測実行時間ｔＡ２２が４ｍｓのため、１９ｍｓで処理を完了している。このため、予定時間の２３ｍｓに対して４ｍｓの空き時間Ｔｉが生じている。
【００６３】
＜ステップＳ１５＞
スケジューラ１００は、推定されたＣＰＵ１３の空き時間Ｔｉが、再スケジューリングＡを行うことができる程、生じるか検討する。
【００６４】
この場合には、次に実行する予定処理Ａ１および処理Ａ２のうち、優先度の１の処理Ａ１が既に中程度の結果品質のジョブＡ２２であるのに対して、優先度２の処理２が低い結果品質のジョブＡ２１であるため、バランスを考慮した優先度に基づき、スケジューラ１００は、まず処理２について検討する。ここでは、１０ｍｓの空き時間Ｔｉが生じるため、処理Ａ２の複数のジョブの中で、実行予定のジョブＡ１１の次に実行時間の長いジョブＡ１２のジョブ管理情報メモリ１０５に記憶されている実行時間は、最悪実行時間の１０ｍｓであるが、ジョブＡ２１よりも、３ｍｓ長いだけである。このため、スケジューラ１００は、ジョブＡ１１をジョブＡ１２に入れ替えても予約時間内にジョブＡ２２を実行できる可能性が高いと判断する。すなわち、スケジューラ１００は、再スケジューリングＡを行うための空き時間Ｔｉが生じる（Ｙｅｓ）と判断する。
【００６５】
＜ステップＳ１６＞
再スケジューリングＡでは、選択器１０３は、処理Ａ１のジョブ中で、前回選択されたジョブＡ１１の次に実行時間の長いジョブＡ１２を選択し、リセット器１０２はキューメモリ１０８を、図７に示すスケジュールＡ２にリセットし、再びステップＳ１２で、ＣＰＵ１３は処理を実行する。
【００６６】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ２に示したキューメモリ１０８の情報に従い、処理Ａ１をジョブＡ１２で実行する。
【００６７】
＜ステップＳ１３＞
処理Ａ１が完了すると、検出器１０４は、処理Ａ１のジョブＡ１２の実測実行時間ＴＡ１であるｔＡ１２を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ１２、例えば７ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００６８】
＜ステップＳ１４＞
検出器１０４は、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ２２の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００６９】
例えば、図７の実行結果５に示すように、ジョブの実測実行時間ｔＡ１２が７ｍｓの場合、次に実行予定の処理Ａ２のジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、実測実行時間の１５ｍｓであることから、２２ｍｓで全ての処理が完了することになる。すなわち、予約時間２３ｍｓに対して１ｍｓの空き時間Tiしか生じない。
【００７０】
＜ステップＳ１５＞
スケジューラ１００は、空き時間Ｔｉは十分ではないと判断（Ｎｏ）し、ステップＳ１９を経て、再びステップＳ１２において、未実行のジョブＡ２２を実行する。実行結果を図７の実行結果６に示す。
以下、同様に、処理の実行と再スケジューリングＡを繰り返す。
【００７１】
上記の説明のように、本実施の形態のジョブスケジューリング方法は、複数の処理を予約時間内で繰り返す定周期実行方式のスケジューリングを、ジョブ管理情報を基に行う、ジョブスケジューリング方法であって、ジョブ管理情報が、処理の優先度情報と、それぞれの前記処理を実行可能な複数のジョブの実行時間情報とを有し、ＣＰＵの空き時間Ｔｉが生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。また、ジョブ管理情報が、複数のジョブの実測実行時間情報を有し、実測実行時間情報を基に、ジョブを選択する。このため、本実施の形態のジョブスケジューリング方法は、マルチ画面処理回路が処理に要する時間が変化しても、プロセッサの能力を効率的に使うことができる。
【００７２】
＜第１の実施の形態の変形例＞
以下、第１の実施の形態の変形例のジョブスケジューリング方法について説明する。なお本変形例にかかるスケジューリング方法は、第１の実施の形態にかかるスケジューラ１００によるスケジューリング方法と類似しているため、同じ箇所の説明は省略する。本変形例のジョブスケジューリング方法を行うスケジューラ１０１は、各定周期処理の度に、必ず予約時間内に処理が完了するように、各ジョブの最悪実行時間に基づいてジョブスケジューリングを行う。そして、一のジョブを実行する度に、スケジューラ１０１は、そのジョブの実測実行時間情報と、これから実行予定の残りのジョブの実測実行時間情報とから空き時間Ｔｉを推算し、再スケジューリングＡができる程、空き時間Ｔｉがある場合にのみ、再スケジューリングＡを行う。そして、全てのジョブの実行が終了、すなわち１周期の定周期処理が終了後に、再び、最悪実行時間に基づくジョブスケジューリングにキュー情報をリセットする。
【００７３】
あるいは、スケジューラ１０１は、各定周期処理の度に、所定の空き時間Ｔｋが生じるように、各ジョブの実測実行時間情報に基づいてジョブスケジューリングを行ってもよい。ここで、所定の空き時間Ｔｋとは処理開始前に入力される情報であり、確実に予約時間内に処理を完了するための安全係数的なパラメータである。所定の空き時間Ｔｋは、処理速度の変動に応じて決定されるが、予約時間の１０〜３０％が好ましい。前記範囲未満では、予約時間内に処理が完了しないことがあり、前記範囲を超えるとプロセッサの使用効率が良くはない。
【００７４】
本変形例のジョブスケジューリング方法では、第１の実施の形態のジョブスケジューリング方法が有する効果に加えて、確実に予約時間内に処理を完了することができ、処理の信頼性が向上する。
【００７５】
＜第２の実施の形態＞
次に、本発明の第２の実施の形態にかかるスケジューラ１０２について説明する。なお、第２の実施の形態にかかるスケジューリング方法は、第１の実施の形態にかかるスケジューラ１００によるスケジューリング方法と類似しているため、同じ構成要素には同じ符号を付し説明は省略する。
【００７６】
図８は、第２の実施の形態にかかるスケジューリング方法の処理の流れを説明するためのフローチャートであり、り、図９は、スケジューラ１０２による再スケジューリングＢを説明するための説明図である。
【００７７】
本実施の形態にかかるスケジューリング方法においては、プロセッサの能力を効率的に使うために、最悪実行時間ではなく、実測実行時間を元にスケジューリングを行う。このため、処理が予約時間内に完了しない可能性がゼロではない。このため、本実施の形態にかかるスケジューリング方法においては、処理が予約時間内に完了しない場合には、再スケジューリングＢを行い、速やかに処理の完了を図る。ここで、処理が予約時間内に完了しない場合とは、実際に完了できなかった場合、および／または完了できない見込みの場合を意味する。
【００７８】
以下、図８のフローチャートに従い、本実施の形態のスケジューリング方法について説明する。
図８に示すように、本実施の形態にかかるスケジューリング方法は、ステップＳ１０から、ステップＳ１５およびステップＳ１６までは第１の実施の形態にかかるスケジューリング方法と同じであるため、ステップＳ１７以降の再スケジューリングＢについて説明する。
【００７９】
前述のように、本実施の形態のスケジューリング方法では、プロセッサの能力を効率的に使うために最悪実行時間を基にしたスケジューリングでは予約時間内に処理が完了しないジョブを登録している。このため、処理を実行した際に、処理が予約時間内に完了しないことがある。処理が予約時間内に完了しなかった場合、スケジューラ１０２は、ステップＳ１６において、Ｙｅｓと判断し、ステップＳ１７において再スケジューリングＢを行う。
【００８０】
＜ステップＳ１７＞
再スケジューリングＢについて、図９を用いて説明する。例えば、図９のスケジュールＢ０に示した様に、ジョブＡ１３の実測実行時間が４ｍｓで、ジョブＡ２３の実測実行時間が１９ｍｓであったために、スケジューラ１０２が予約時間２３ｍｓで処理が完了すると予定して、ジョブ１３およびジョブＡ２３をキューメモリ１０８に登録し実行していた場合に、入力画像信号等に変化が生じて、実測実行時間が増加することがある。
【００８１】
例えば、図９の実行予定結果７に示すように、ジョブＡ１３の実測実行時間ｔＡ１３が４ｍｓから１０ｍｓに急増すると、残りの予約時間は１３ｍｓしかないため、１９ｍｓを要する予定、すなわち、実測実行時間が１９ｍｓのジョブＡ２３を予約時間内には実行できない見込みとなってしまう。このように実測実行時間情報に基づき予約時間内に全ての処理が完了しない場合、スケジューラ１０２は、処理完了しないと判断し、ステップＳ１８において、再スケジューリングＢを行う。
【００８２】
＜ステップＳ１８＞
再スケジューリングＢでは、スケジューラ１０２は、未実行のジョブを、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の短いジョブを選択する。
【００８３】
この場合には、次に実行する予定の処理が、処理Ａ２のみであるので、処理Ａ２について再スケジューリングＢを行う。すなわち、選択器１０３は、実行予定のジョブＡ２３の次に実行時間の短いジョブＡ２２を選択し、リセット器１０２はキューメモリ１０８を、図９に示すスケジュールＢ１にリセットし、再びステップＳ１２で、ＣＰＵ１３はスケジュールＢ１に示したキューメモリ１０８の情報に従い、処理を行う。そして、スケジューラ１０２は、ステップＳ１３、ステップＳ１４、ステップＳ１５を行い、再び、ステップＳ１７で処理が予約時間内に完了したかの判断を行う。
【００８４】
＜ステップＳ１７＞
図９の実行結果８に示すように、ジョブＡ２２が予約時間内に完了しなかった場合には、スケジューラ１０２は、処理完了しないと判断し、ステップＳ１８において、再スケジューリングＢを行う。
【００８５】
＜ステップＳ１８＞
再スケジューリングＢでは、スケジューラ１０２は、未実行のジョブを、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の短いジョブを選択する。すなわち、再スケジューリングＢは、結果品質を低下するスケジューリングであるため、優先度に基づいて、とは、優先度の低い処理から結果品質の低いジョブを選択することを意味する。
【００８６】
この場合には、次に実行する予定の処理が、処理Ａ１および処理Ａ２と複数であるため、優先度に基づき、まず優先度の低い処理Ａ１について再スケジューリングＢを行う。すなわち、選択器１０３は、実行予定のジョブＡ１３の次に実行時間の短いジョブＡ１２を選択し、リセット器１０２はキューメモリ１０８を、図９に示すスケジュールＢ２にリセットし、再びステップＳ１２で、ＣＰＵ１３はスケジュールＢ２に示したキューメモリ１０８の情報に従い、処理を行う。そして、スケジューラ１０２は、ステップＳ１３、ステップＳ１４、ステップＳ１５を行い、再び、ステップＳ１７で処理が予約時間内に完了したかの判断を行う。
【００８７】
＜ステップＳ１７＞
図９の実行予定結果９に示すように、ジョブＡ１２の実測実行時間ｔＡ１２が８ｍｓであり、ジョブＡ２２の実測実行時間ｔＡ２２が１５ｍｓの場合には、スケジューラ１０２は、処理が完了できる見込み（Ｙｅｓ）と判断して、スケジューラ１０２は、再スケジューリングＢは行わないで、ステップＳ１９から、ステップＳ１２、ステップＳ１３、ステップＳ１４、ステップＳ１５を行い、再び、ステップＳ１７で処理が予約時間内に完了したかの判断を行う。
【００８８】
＜ステップＳ１７＞
図９の実行結果１０に示すように、ジョブＡ２２が予約時間内に完了した場合には、スケジューラ１０２は、処理完了（Ｙｅｓ）と判断して、処理を継続する。
【００８９】
このように、本実施の形態にかかるスケジューリング方法においては、第１の実施の形態のスケジューリング方法が有する効果に加えて、処理が予定時間内に完了しない場合には、再スケジューリングＢを行い、速やかに処理の完了を図ることができる。
【００９０】
なお、再スケジューリングＢを行った場合には、所定の期間あるいは入力画像信号の数等が変化するまで、再スケジューリングＡは行わないことが好ましい。再スケジューリングＡを行って結果品質を向上しても、次のフレーム処理の際に再び、処理が完了しないで、再スケジューリングＢが必要となる可能性が高いためである。
【００９１】
なお、マルチ画面処理が完了しないと、テレビジョン受像器はモニタに、最新の画像を表示できないため、前フレームの画像を表示する。すなわち、モニタ表示は、いわゆるフリーズ状態となる。しかし、フリーズ状態が、数フレーム分だけであれば、視聴者は気が付かない。このため、本実施の形態のジョブスケジューリング方法においては、第１の実施の形態のジョブスケジューリング方法に加えて、可能な限り高品質の出力画像を出力しつつ、処理未完了による悪影響は最小に留まるため、処理の信頼性が向上する
なお、上記実施の形態では、スケジューラ１００のジョブスケジューリング方法が、マルチ画像処理回路１１の画像サイズ変換処理とフォーマット変換処理との２の処理に用いられる例を示したが、３つ以上の処理のジョブスケジューリングに用いることもできる。また、それぞれの処理を実行可能なジョブを３ずつとしたが、４以上でもよいし、もちろん、処理毎のジョブの数は同数である必要はない。さらに、ジョブスケジューリングする処理が３つ以上の場合には、少なくとも２つの処理がそれぞれの処理を実行可能な複数のジョブを有していれば、他の処理を実行可能なジョブは、それぞれ１つのみでもよい。また、スケジューラ１００のジョブスケジューリング方法は、定周期実行する処理Ａについてのジョブスケジューリングだけでなく、処理Ａと組み合わせて定周期実行する処理Ｂについてのジョブスケジューリングも可能である。
【００９２】
さらに、再スケジューリングＡおよび再スケジューリングＢでは、１回の再スケジューリングで１つの処理のジョブを入れ替える例を示したが、１回の再スケジューリングで複数の処理のジョブを入れ替えてもよい。
【００９３】
また、スケジューラ１００によるジョブスケジューリングは、例えば、音声処理回路に用いてもよいし、データ誤り訂正回路に用いてもよい。さらに、スケジューラ１００によるジョブスケジューリングは、テレビジョン受像機１のデータ処理に限られるものではなく、定周期実行方式で、複数の異なる目的の処理を行うためのスケジューリングを、ジョブ管理情報を基に行うジョブスケジューリング方法であれば、汎用用途で用いることが可能であり、いずれの場合も、プロセッサの能力を効率的に使うことができる。
【００９４】
本発明は、上述した実施の形態に限定されるものではなく、本発明の要旨を変えない範囲において、種々の変更、改変等が可能である。
【図面の簡単な説明】
【００９５】
【図１】第１の実施の形態にかかるマルチ画面処理回路を有するテレビジョン受像機１の構成を示した構成図である。
【図２】テレビジョン受像機のマルチ画面の例を示した図である。
【図３】第１の実施の形態にかかるスケジューラのブロック図である。
【図４】第１の実施の形態にかかる、ジョブ管理情報の例を示した表である。
【図５】画像サイズ変換処理が実行可能な複数のアルゴリズムが異なるジョブを説明するための説明図である。
【図６】第１の実施の形態のスケジューリング処理の流れを説明するためのフローチャートである。
【図７】第１の実施の形態にかかるスケジューラによる再スケジューリングＡを説明するための説明図である。
【図８】第２の実施の形態のスケジューリング処理の流れを説明するためのフローチャートである。
【図９】第２の実施の形態にかかるスケジューラによる再スケジューリングＢを説明するための説明図である。
【符号の説明】
【００９６】
１…テレビジョン受像機、２…パラボラアンテナ、４、５、６、７…デコーダー、８…ＨＤＤ、９…外部端子、１０…切替回路、１１…マルチ画面処理回路、１２…モニタ、１３…キューメモリ、１５…メモリ、２０…モニタ表示画面、１００…スケジューラ、１０２…リセット器、１０３…選択器、１０５…ジョブ管理情報メモリ、１０６…動的情報、１０７…基本情報、１０８…キューメモリ、ＴＡ１、ＴＡ２…実測実行時間、Ｔｉ…空き時間
【技術分野】
【０００１】
本発明は、複数の処理を定周期実行方式で行う際のジョブスケジューリング方法に関する。
【背景技術】
【０００２】
一つのプロセッサを用いて異なる複数の処理を事実上、同時進行で行うマルチタスク処理においては、それぞれの処理を行う時間を予め予約時間として割り当てる定周期実行方式の処理が知られている。定周期実行方式の処理では、それぞれの処理は設定された定周期の時間で繰り返し実行される。また、データサンプリングのように、所定のサンプリング時間内に一連の予め定められた処理を繰り返し実行する処理も、サンプリング時間を予約時間と考えれば、定周期実行方式の一つの類型である。定周期実行方式では、予約時間内に処理を完了するために、予め、プロセッサが、それぞれの処理を実行するためのジョブの実行に要する時間をジョブ管理情報として記憶している。そして、定周期実行方式では、ジョブ管理情報を基に予約時間内に処理を完了するように、複数のジョブをキューとして登録するスケジューリングを行うスケジューラが用いられている。スケジューラは、予約時間内に処理を完了するだけでなく、処理の事象待ち、すなわちプロセッサの待機状態による無駄な空き時間を削減するために、ジョブ管理情報を基に、無駄な空き時間を最小とするスケジューリングを行う。
【０００３】
しかし、全く同じジョブの処理であっても、プロセッサが実際に処理を完了するまでの時間は常に一定という訳ではない。これはプロセッサ自体の処理速度の変動だけでなく、周辺バスの転送速度等、種々の要因による。このため、必ず予約時間内に処理を完了するためには、ジョブ管理情報として記憶しておく特定のジョブに要する時間は、最も時間がかかる最悪実行時間(WCET: Worst-Case Execution Time)を記憶しておく必要がある。
【０００４】
このため、プロセッサが実際に処理を完了するまでの時間が、最悪実行時間よりも短い場合には、プロセッサの空き時間が増加してしまい、プロセッサの能力を効率的に使うことが出来ないという問題があった。前記問題は、実行時間の変動が大きい処理の場合に特に顕著であった。
【０００５】
このため、特許文献１には、ＣＰＵの待ち時間が、指定値を越えると、優先度の高いタスクと優先度の低いタスクとを交互にスケジューリングするタスクスケジューリング方式が開示されている。
【０００６】
ここで、近年のテレビジョン受像機においては、デジタル化により複雑な多数の処理を同時並行で行うため、マルチコアプロセッサ、例えば1つのCPUの中に1個の汎用的なプロセッサコアと、8個のシンプルなプロセッサコアを組み合わせたヘテロジニアスマルチコアが使用されている。しかし、テレビジョン受像機においては、１秒間に６０枚の画像すなわち、奇数と偶数の走査線毎に３０枚／秒の計６０枚／秒の画像を表示しなければならない。このため、複数の処理を、１／３０秒を周期とする定周期実行方式で行うためのジョブスケジューリングが重要となっている。
【０００７】
またテレビジョン受像機のモニタの大画面化に伴い、複数のチャンネルおよび／または入力端子等から入力された複数の入力画像信号から取り出した複数の画像を、複数の領域に分割されたひとつの表示画面の各領域に表示するマルチ画面表示機能が利用されるようになってきている。
【０００８】
マルチ画面表示機能を持つテレビジョン受信機では、複数の入力画像信号の中から選択された複数の画像信号のそれぞれを、マルチ画面処理回路にて画像サイズ変換処理およびフォーマット変換処理してから１つの表示画面として合成する必要がある。このため、ジョブスケジューリングでは、少なくとも画像サイズ変換処理とフォーマット変換処理とを行うための予約時間を設定している。
【０００９】
しかし、マルチ画面表示する画像の数、すなわち入力画像信号の数によりマルチ画面処理回路が処理に要する時間は変化する。また、ヘテロジニアスマルチコアの他のプロセッサコアで動作しているプログラムがバンド幅を圧縮する処理を行ったりすると、マルチ画面処理しているＣＰＵの速度も影響を受けて遅くなることがある。
【００１０】
このため、最悪実行時間を基にした予定時間を用いると、プロセッサの空き時間が増加してしまい、プロセッサの能力を効率的に使うことが出来ないという問題が顕著であった。
【００１１】
本発明は上記問題に鑑みてなされたものであり、プロセッサの能力を効率的に使うことができるジョブスケジューリング方法を提供するものである。
【特許文献１】特開平４−１９１９３５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
本発明は、プロセッサの能力を効率的に使うことができるジョブスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本願発明の一態様によれば、ジョブ管理情報を基に、ＣＰＵが、予約時間内に複数の処理を実行する定周期実行方式のスケジューリングを行う、ジョブスケジューリング方法であって、ジョブ管理情報が、複数の処理のそれぞれの優先度情報と、複数の処理のそれぞれを実行可能な複数のジョブの実行時間情報とを有し、ＣＰＵの空き時間が生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択することを特徴とするジョブスケジューリング方法が提供される。
【発明の効果】
【００１４】
本発明は、プロセッサの能力を効率的に使うことができるジョブスケジューリング方法を提供するものである。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の実施の形態を説明する。
＜第１の実施の形態＞
＜スケジューラの構成＞
最初に、図１から図５を用いて、本発明の第１の実施の形態にかかるスケジューラ１００の構成について説明する。
【００１６】
図１は、本実施の形態にかかるマルチ画面処理回路１１を有するテレビジョン受像機１の構成を示した構成図であり、図２はテレビジョン受像機１のマルチ画面の例を示した図であり、図３は、スケジューラ１００のブロック図であり、図４は、ジョブ管理情報１０５の例を示した表であり、図５は、画像サイズ変換処理Ａ２が実行可能なアルゴリズムが異なる複数のジョブを説明するための説明図である。
【００１７】
図１に示すように、本実施の形態にかかるテレビジョン受像機１は、多数の入力画像信号の中から選択された複数の画像信号をいったんメモリ１５に記憶し、そのデータを基に、マルチ画面処理回路１１にて、それぞれの画像信号の画像サイズ変換処理と、フォーマット変換処理を行い、再びメモリ１５を介して、１つの表示画面として画像出力手段であるモニタ１２に出力する。例えば、パラボラアンテナ２で受信されたデジタルテレビ放送の信号は、放送局および放送仕様により、それぞれ異なるデコーダーで処理される。図１では、簡略化し、４個のデコーダー４、５、６、７からなるデコーダー群を図示している。また、内蔵ハードディスクドライブ（ＨＤＤ）８に記録された画像信号や、外部端子９に接続された図示しないビデオカメラまたはゲーム機からの画像信号も、テレビジョン受像機１には入力される。これら複数の入力画像信号の中から切替回路１０により選択された画像信号がマルチ画面処理回路１１にて処理される。マルチ画面処理回路１１は、複数の画像信号を、１つの表示画像信号に合成する回路である。
【００１８】
マルチ画面処理回路１１の、ＣＰＵ１３は、１秒間に６０枚の画像すなわち、奇数と偶数の走査線毎に３０枚／秒の画像信号を処理するために、１／３０秒を周期とする定周期実行方式のジョブスケジューリングを行うスケジューラ１００が登録したキューメモリ情報に従い処理を行う。なお、ＣＰＵ１３は、マルチ画面処理回路１１の処理だけでなく、別の処理Ｂも、１／３０秒を周期とする定周期実行方式にて処理している。
【００１９】
次に、図２に、マルチ画面処理回路１１により合成されたマルチ画面を表示したテレビジョン受像機のモニタ表示画面２０の例を示す。図２（Ａ）は、通常の１画面２０Ａを表示しており、図２（Ｂ）は同じ大きさの２つの画面２０Ｂ、２０Ｃを並べて表示したダブルウィンドウ画面を示しており、図２（Ｃ）は、小さな子画面２０Ｄと、大きな親画面２０Ｅを並べて表示したダブルウィンドウ画面を示しており、図２（Ｄ）は、４つの画面２０Ｆ、２０Ｇ、２０Ｈ、２０Ｉを同時に表示したマルチウィンドウ画面を示している。通常の画面２０Ａは、（１９２０×１０８０）画素で表示されているが、マルチ画面の各画面は、縮小して表示されている。すなわち、画面２０Ｂ、２０Ｃ、２０Ｆ、２０Ｇ、２０Ｈおよび２０Ｉは、いずれも通常画面２０Ａの半分の（９６０×５４０）画素で表示され、２０Ｄは通常画面２０Ａの４分の１の（４８０×２７０）画素で表示され、２０Ｅは通常画面２０Ａの４分の３の（９６０×５４０）画素で表示されている。
【００２０】
次に、図３に、本実施の形態にかかるスケジューラ１００のブロック図を示す。スケジューラ１００は、ＣＰＵ１３が実行するジョブをキュー（Ｑｕｅｕｅ）として、キューメモリ１０８に登録する、すなわち、スケジューリングを行う。図２に示したようなマルチ画面を表示するために、マルチ画面処理回路１１は、少なくとも２つの異なる目的の処理を実行しなければならない。すなわち、元の画像信号のフォーマットを変換するフォーマット変換処理（以下、処理Ａ１という。）と、元の画像信号の画像サイズを変換する画像サイズ変換処理（以下、処理Ａ２という。）である。元の画像信号の画像サイズとしては、HD(1920×1080)やSD（720×480）等があるが、ここでは、元の画像信号の画像サイズをHDとし、処理A2を縮小する画像サイズ変換処理として説明する。もちろん、拡大する画像サイズ変換もある。
【００２１】
以下、処理Ａ１と処理Ａ２を合わせて処理Ａとし、処理Ａと共に同じＣＰＵで定周期実行する処理を処理Ｂとする。ここで、図３に示したキューメモリ１０８に登録されたキューは、定周期時間である３０分の１秒すなわち約３３ｍｓを四角形の縦の長さで表現し、そのうちの処理Ａを実行する予約時間が、例えば定周期時間の７０％であることを表している。処理Ａと処理Ｂのそれぞれの予約時間は再設定することが可能であるが、以下は、予約時間が固定されている状態のジョブスケジューリングについて説明する。すなわち、処理Ａは、約３３ｍｓの定周期時間の７０％である約２３ｍｓで、処理Ａ１と処理Ａ２を実行する例について説明する。
【００２２】
図３に示すように、スケジューラ１００は、キューメモリ１０８にジョブを登録するために、ジョブ管理情報メモリ１０５に記憶されている情報を基に、ジョブを選択する選択器１０３と、選択器１０３が選択したジョブをキューメモリ１０８に登録するリセット器１０２から構成されている。また、検出器１０４は定周期スケジューラ上で走る一連のプロセスのＣＰＵ１３の利用状況に関するデータを収集するものであり、例えば、登録されたキューメモリ１０８の情報に従い、ＣＰＵ１３が処理を行った時に処理を完了するまでに要した実際の時間（以下、「実測実行時間」という。）を検出する。
【００２３】
ジョブ管理情報メモリ１０５は、処理を実際に実行する複数のジョブの管理情報を記憶するメモリであり、図４に示すように本実施の形態のジョブスケジューリング方法においては、処理開始時には、少なくとも処理の優先度情報とジョブの最悪実行時間情報とを含む基本情報１０７を有している。基本情報１０７は処理開始前に定周期時間等と共にパラメータとして入力される。また、ジョブ管理情報メモリ１０５は、処理開始後に検出器１０４の情報を基に入力される実測実行時間情報である動的情報１０６も有している。
【００２４】
本実施の形態のジョブスケジューリングでは、図４に示すように、ある一つの処理が実行可能な複数のジョブから一のジョブを選択しスケジューリングを行う。ここでは、元の画像信号の画像サイズを縮小するという画像サイズ変換処理Ａ２に対して、ジョブＡ２１、ジョブＡ２２およびジョブＡ２３という３つのジョブを用いる例を示している。ジョブＡ２１、ジョブＡ２２およびジョブＡ２３は、それぞれが画像サイズ変換処理を単独で実行することが可能なジョブである。しかし、３つのジョブは、以下に説明するように画像サイズ変換処理を行うためのアルゴリズムが異なる。
【００２５】
ここで、図５を用いて、画像サイズ変換処理、すなわち、元の画像信号の画像サイズを縮小する処理に用いるジョブについて説明する。例えば、図２（Ｄ）に示したように、４つの画像を同時に画面に表示するためには、それぞれの画像サイズを４分の１に縮小しなければならない。なお、画像サイズを縮小するジョブには種々の異なるアルゴリズムを用いることができるが、ここでは説明を簡単にするために画素データを用いた簡単なアルゴリズムの例を用いて説明する。
【００２６】
すなわち、図５のａで示したように、元のフル画素データが横６画素縦４画素の２４画素から構成されている場合、画像サイズを４分の１に縮小するとは、横３画素縦２画素の６画素に変換することである。アルゴリズムａ２１では、フル画素データを縦２画素横２画素の４画素の中から、ランダムに１画素を選択し、その画素を集合して縮小画像データを作成する、いわゆる間引きアルゴリズムである。これに対して、アルゴリズムａ２２は、フル画素データの、縦２画素横２画素の４画素の情報を平均化して新規な画素を作成し、その画素を集合して縮小画像データを作成する、いわゆる単純平均化アルゴリズムである。アルゴリズムａ２３は、やはり縦３画素横３画素の９画素の情報を平均化する平均化アルゴリズムであるが、単純に平均化するのではなく、中心画素からの距離に応じて縮小画素への寄与度を変える。このため、フル画素のうちの１つの画素の情報が、複数の縮小画素に重み付けして反映される、いわゆる複合平均化アルゴリズムである。
【００２７】
間引きアルゴリズムであるアルゴリズムａ２１は最も簡単なアルゴリズムであるため、アルゴリズムａ２１を用いるジョブＡ２１は、図４に示すように、処理時間が短く、例えば最悪実行時間は１５ｍｓである。しかし、アルゴリズムａ２１は単なる間引きであるので、縮小された画像の品質は良くない、すなわち、アルゴリズムａ２１は処理の結果品質は低い。これに対して、単純平均化アルゴリズムであるアルゴリズムａ２２は比較的簡単なアルゴリズムであるため、アルゴリズムａ２２を用いるジョブＡ２２は、図４に示すように、処理時間が比較的短く、例えば最悪実行時間は２５ｍｓである。また、アルゴリズムａ２２は平均化処理しているので、縮小された画像の品質は普通、すなわち、アルゴリズムａ２２は処理の結果品質は中である。そして、複合平均化アルゴリズムであるアルゴリズムａ２３は複雑であるため、アルゴリズムａ２３を用いるジョブＡ２３は、図４に示すように、処理時間が長く、例えば最悪実行時間は３５ｍｓである。しかし、アルゴリズムａ２３は多数の画素を重み付けして平均化処理しているので、縮小された画像の品質はよい、すなわち、アルゴリズムａ２３は処理の結果品質は高である。
【００２８】
なお、上記説明で、例えば、アルゴリズムａ２１によるジョブ２１の処理の結果品質が低いといっても、他の処理時間が長いアルゴリズムによるジョブと比較しての相対的な品質であり、絶対的な品質が低いわけでなく、ジョブ２１の処理も、実用上、十分な結果品質を有している。
【００２９】
また、図４に示すように、元の画像信号のフォーマットを変換するフォーマット変換処理である処理Ａ１についても、処理Ａ１が実行可能な複数のジョブＡ１１、ジョブＡ１２およびジョブＡ１３という３つのジョブを用いる。ジョブＡ１１は簡単なアルゴリズムのため、処理時間が短く、例えば最悪実行時間は７ｍｓである。しかし、ジョブＡ１１は単純な処理のため、変換された画像の品質は悪い、すなわち、ジョブＡ１１は処理の結果品質は低である。これに対してジョブＡ１２は、やや簡単なアルゴリズムのため、処理時間が比較的短く、例えば最悪実行時間は１０ｍｓである。そして、ジョブＡ１２は変換された画像の品質は普通、すなわち、処理の結果品質は中である。そして、ジョブＡ１３は複雑なアルゴリズムのため、処理時間が長く、例えば最悪実行時間は１５ｍｓである。しかし、ジョブＡ１３は変換された画像の品質はよい、すなわち、処理の結果品質は高である。
【００３０】
なお、図４のジョブ管理情報処理に示したように、フォーマット変換処理である処理Ａ１の優先度は２であり、画像サイズ変換処理である処理Ａ２の優先度１よりも低く設定されている。優先度は基本情報１０７として処理の開始前に入力される。また、ジョブの実測実行時間ＴＡ１およびＴＡ２は後述するように、処理が実行された後に検出器１０４により記録される。
【００３１】
なお、図４に示したジョブ管理情報において、アルゴリズムと結果品質は説明のために付加したものであり、実際のジョブ管理情報には含まれていなくてもよい。
【００３２】
＜スケジューリング方法＞
次に、図６および図７を用いて、本実施の形態のスケジューリング方法について説明する。図６は、本実施の形態のスケジューラ１００によるスケジューリング処理の流れを説明するためのフローチャートであり、図７は、スケジューラ１００による再スケジューリングＡを説明するための説明図である。
【００３３】
以下、図６のフローチャートに従い、本実施の形態のスケジューリング方法について説明する。
【００３４】
本実施の形態のスケジューリング方法においては、ＣＰＵ１３の空き時間Ｔｉが生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。なお、ここで、空き時間が生じる場合とは、実際に空き時間Ｔｉが生じた場合、および／または生じる見込みの場合を意味する。また、実際に空き時間Ｔｉが生じた場合であっても、次の定周期処理において必ず空き時間Ｔｉが生じるわけではない。
【００３５】
＜ステップＳ１０＞
処理の開始前に、処理パラメータとして、ジョブ管理情報メモリ１０５に、ジョブ管理情報の基本情報１０７と定周期時間とが入力される。図４に示すように、ジョブ管理情報メモリ１０５に記憶された基本情報１０７は、複数の処理の処理名、Ａ１およびＡ２の優先度情報と、処理Ａ１が実行可能な複数のジョブのジョブＩＤであるＡ１１、Ａ１２およびＡ１３とそれぞれのジョブの最悪実行時間情報と、処理Ａ２が実行可能な複数のジョブのジョブＩＤであるＡ２１、Ａ２２およびＡ２３とそれぞれの最悪実行時間情報である。この時点において、ジョブ管理情報メモリ１０５の動的情報１０６、すなわちジョブの実測実行時間は、登録されていなくてもよいし、前回の処理の際の情報が含まれていてもよい。
【００３６】
＜ステップＳ１１＞
選択器１０３は、処理開始時点においては、複数の処理の各ジョブを、基本情報１０７の優先度情報と最悪実行時間情報とを基に、ＣＰＵ１３の空き時間Ｔｉが最小となるように選択し、キューメモリ１０８に登録する。すなわち、図８のスケジュールＡ０に示すように、選択器１０３は、予約時間の中で、ＣＰＵの空き時間Ｔｉが最小となるように、優先度に基づき、処理Ａ１および処理Ａ２を実行可能な複数のジョブの中から、それぞれ１つのジョブを選択する。
【００３７】
例えば、予約時間が２３ｍｓの場合は、選択器１０３は、まず優先度１の処理Ａ２から最悪実行時間１５ｍｓのジョブＡ２１を選択し、次に優先度２の処理Ａ１から最悪実行時間７ｍｓのジョブＡ１１を選択する。すると、図７のスケジュールＡ０に示すように、予約時間２３ｍｓに対して、空き時間Ｔｉは１ｍｓとなる。
【００３８】
なお、選択器１０３は、各ジョブの実測実行時間情報が、ジョブ管理情報メモリ１０５の動的情報１０６に記憶されている場合には、最悪実行時間情報の替わりに、実測実行時間情報を用いて各ジョブを選択する。すなわち、選択器１０３が最悪実行時間情報を基にジョブ選択を行うのは、それぞれのジョブが未実行の場合である。
【００３９】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したキューメモリ１０８の情報に従い、処理Ａ１をジョブＡ１１で、実行する。
【００４０】
＜ステップＳ１３＞
処理Ａ１が完了すると、検出器１０４は、処理Ａ１のジョブＡ１１の実測実行時間ＴＡ１であるｔＡ１１を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ１１、例えば４ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００４１】
＜ステップＳ１４＞
次に、検出器１０４は、実行予定のジョブＡ２１のジョブ管理情報メモリ１０５に記憶されている実行時間と予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００４２】
例えば、図７の実行結果１に示すようにジョブＡ１１の実測実行時間ｔＡ１１が４ｍｓの場合、最悪実行時間は７ｍｓだったため、３ｍｓの空き時間Ｔｉが生じる。このため、検出器１０４は、スケジュールＡ０での空き時間Ｔｉ１ｍｓと合わせると４ｍｓ以上の空き時間Ｔｉが生じると推算する。
【００４３】
＜ステップＳ１５＞
スケジューラ１００は、推定されたＣＰＵ１３の空き時間Ｔｉが、再スケジューリングＡを行うことができる程、生じるかを検討する。すなわち、処理Ａ２の複数のジョブの中で、実行予定のジョブＡ２１の次に実行時間の長いジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、最悪実行時間の２５ｍｓでありジョブＡ２１よりも１０ｍｓも長く、推算された空き時間Ｔｉ４ｍｓよりも長い。
【００４４】
このため、ジョブＡ２１をジョブＡ２２に入れ替えると、残りの予約時間内にジョブＡ２２を実行することはできない可能性が高い。このため、スケジューラ１００は、空き時間Ｔｉは十分ではないと判断（Ｎｏ）し、ステップＳ１９において処理終了（Ｎｏ）でなければ、再びステップＳ１２において、ＣＰＵ１３は未実行のジョブＡ２１を実行する。
【００４５】
なお、ＣＰＵ１３は、処理Ａの後に、キュー情報に従い処理Ｂを実行するが、以降の説明においては省略する。
【００４６】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ１に示したキューメモリ１０８の情報に従い、処理Ａ２をジョブＡ２１で実行する。
【００４７】
＜ステップＳ１３＞
処理Ａ２が完了すると、検出器１０４は、処理Ａ２のジョブＡ２１の実測実行時間ＴＡ２であるｔＡ２１を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ２１、例えば９ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００４８】
＜ステップＳ１４＞
さらに検出器１０４は、図７の実行結果２に示すように、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ１１の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。なお、ここで推算するとは実測実行時間から空き時間Ｔｉを算出し、次回の処理における空き時間Ｔｉと推定することである。
【００４９】
＜ステップＳ１５＞
スケジューラ１００は、推算されたＣＰＵ１３の空き時間Ｔｉが、再スケジューリングＡを行うことができる程、生じるかを検討する。
【００５０】
この場合には、次に実行する予定の処理が、処理Ａ１および処理Ａ２と複数であるため、優先度に基づき、まず優先度の高い処理Ａ２について検討する。ここでは、１０ｍｓの空き時間Ｔｉが生じるため、スケジューラ１００は、処理Ａ２の複数のジョブの中で、実行予定のジョブＡ２１の次に実行時間の長いジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、最悪実行時間の２５ｍｓであるが、ジョブＡ２１よりも、ちょうど１０ｍｓ長い。このため、ジョブＡ２１をジョブＡ２２に入れ替えても予約時間内にジョブＡ２２を実行できる可能性が高い。このため、スケジューラ１００は、再スケジューリングＡを行うための空き時間Ｔｉは十分と判断（Ｙｅｓ）し、ステップＳ１６に進む。
【００５１】
＜ステップＳ１６＞
なお、再スケジューリングＡでは、選択器１０３は、複数のジョブの中で、処理の優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。処理時間の長い複雑なアルゴリズムを用いるジョブは結果品質が高いからである。また、空き時間Ｔｉが生じたとしても、その空き時間Ｔｉは最悪実行時間で保証されたものではないため、選択器１０３は、予約時間内に処理が完了しないことがないように、前回選択され、予約時間内に処理が完了できたジョブの次に実行時間の長いジョブを選択する。
【００５２】
また、処理の優先度に基づいてジョブを選択するため、優先度の高い処理の品質を優先して上げることができる。なお、スケジューラ１００が、処理の優先度に基づいてジョブを選択する際には、結果品質のバランスを考慮し選択することが好ましい。すなわち、スケジューラ１００が、最初に優先度の最も高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択する再スケジューリングＡを行った場合には、次の再スケジューリングＡでは、優先度が２番目に高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択し、そして次の再スケジューリングＡでは、優先度が３番目に高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択していき、最も優先度が低い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択する再スケジューリングＡの後に、優先度の最も高い処理のジョブの中から実行時間の長い、結果品質のより高いジョブを選択する再スケジューリングＡを行う。複数の処理の中で優先度が高い処理のみの結果品質が突出して高くても、マルチ画面処理回路１１の全体としての結果品質が、高くはならない場合があるからである。
【００５３】
ここでは、選択器１０３は、優先度１の処理Ａ２のジョブ中で、ステップＳ１１で選択されたジョブＡ２１の次に実行時間の長いジョブＡ２２を選択し、リセット器１０２はキューメモリ１０８を、図７に示すスケジュールＡ１のように、リセットする。
【００５４】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ１に示したキューメモリ１０８の情報に従い、処理Ａ１をジョブＡ１１で実行する。
【００５５】
＜ステップＳ１３＞
処理Ａ１が完了すると、検出器１０４は、処理Ａ１のジョブＡ１１の実測実行時間ＴＡ１であるｔＡ１１を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ１１、例えば４ｍｓ、を、再びジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００５６】
＜ステップＳ１４＞
さらに検出器１０４は、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ２２の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００５７】
例えば、図７の実行結果３に示すように、ジョブＡ１１の実測実行時間ｔＡ１１が、再び、４ｍｓの場合、次に実行予定の処理Ａ２のジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、前回実行したジョブ２１より最悪実行時間で１０ｍｓ長いことから、ちょうど２３ｍｓで全ての処理が完了することになる。すなわち、予約時間２３ｍｓに対して空き時間Ｔｉは生じない。
【００５８】
＜ステップＳ１５＞
空き時間Ｔｉが生じないので、スケジューラ１００は、空き時間Ｔｉは十分ではないと判断（Ｎｏ）し、ステップＳ１９を経て、再びステップＳ１２において、未実行のジョブＡ２２を実行する。
【００５９】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ１に示したキューメモリ１０８の情報に従い、処理Ａ２をジョブＡ２２で実行する。
【００６０】
＜ステップＳ１３＞
処理Ａ２が完了すると、検出器１０４は、処理Ａ２のジョブＡ２２の実測実行時間ＴＡ２であるｔＡ２２を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ２２、例えば１５ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００６１】
＜ステップＳ１４＞
さらに検出器１０４は、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ１１の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００６２】
例えば、図７の実行結果４に示すように、ジョブＡ２２の実測実行時間ｔＡ２２が１５ｍｓの場合、既に実行したジョブＡ１１の実測実行時間ｔＡ２２が４ｍｓのため、１９ｍｓで処理を完了している。このため、予定時間の２３ｍｓに対して４ｍｓの空き時間Ｔｉが生じている。
【００６３】
＜ステップＳ１５＞
スケジューラ１００は、推定されたＣＰＵ１３の空き時間Ｔｉが、再スケジューリングＡを行うことができる程、生じるか検討する。
【００６４】
この場合には、次に実行する予定処理Ａ１および処理Ａ２のうち、優先度の１の処理Ａ１が既に中程度の結果品質のジョブＡ２２であるのに対して、優先度２の処理２が低い結果品質のジョブＡ２１であるため、バランスを考慮した優先度に基づき、スケジューラ１００は、まず処理２について検討する。ここでは、１０ｍｓの空き時間Ｔｉが生じるため、処理Ａ２の複数のジョブの中で、実行予定のジョブＡ１１の次に実行時間の長いジョブＡ１２のジョブ管理情報メモリ１０５に記憶されている実行時間は、最悪実行時間の１０ｍｓであるが、ジョブＡ２１よりも、３ｍｓ長いだけである。このため、スケジューラ１００は、ジョブＡ１１をジョブＡ１２に入れ替えても予約時間内にジョブＡ２２を実行できる可能性が高いと判断する。すなわち、スケジューラ１００は、再スケジューリングＡを行うための空き時間Ｔｉが生じる（Ｙｅｓ）と判断する。
【００６５】
＜ステップＳ１６＞
再スケジューリングＡでは、選択器１０３は、処理Ａ１のジョブ中で、前回選択されたジョブＡ１１の次に実行時間の長いジョブＡ１２を選択し、リセット器１０２はキューメモリ１０８を、図７に示すスケジュールＡ２にリセットし、再びステップＳ１２で、ＣＰＵ１３は処理を実行する。
【００６６】
＜ステップＳ１２＞
ＣＰＵ１３はスケジューラ１００が登録したスケジュールＡ２に示したキューメモリ１０８の情報に従い、処理Ａ１をジョブＡ１２で実行する。
【００６７】
＜ステップＳ１３＞
処理Ａ１が完了すると、検出器１０４は、処理Ａ１のジョブＡ１２の実測実行時間ＴＡ１であるｔＡ１２を検出する。そして、検出器１０４は、ジョブＡ１１の実測実行時間ｔＡ１２、例えば７ｍｓ、を、ジョブ管理情報メモリ１０５の動的情報１０６に記録する。
【００６８】
＜ステップＳ１４＞
検出器１０４は、ジョブ管理情報メモリ１０５に記憶されている実行予定のジョブＡ２２の実行時間と、予約時間から、ＣＰＵ１３の空き時間Ｔｉを推算する。
【００６９】
例えば、図７の実行結果５に示すように、ジョブの実測実行時間ｔＡ１２が７ｍｓの場合、次に実行予定の処理Ａ２のジョブＡ２２のジョブ管理情報メモリ１０５に記憶されている実行時間は、実測実行時間の１５ｍｓであることから、２２ｍｓで全ての処理が完了することになる。すなわち、予約時間２３ｍｓに対して１ｍｓの空き時間Tiしか生じない。
【００７０】
＜ステップＳ１５＞
スケジューラ１００は、空き時間Ｔｉは十分ではないと判断（Ｎｏ）し、ステップＳ１９を経て、再びステップＳ１２において、未実行のジョブＡ２２を実行する。実行結果を図７の実行結果６に示す。
以下、同様に、処理の実行と再スケジューリングＡを繰り返す。
【００７１】
上記の説明のように、本実施の形態のジョブスケジューリング方法は、複数の処理を予約時間内で繰り返す定周期実行方式のスケジューリングを、ジョブ管理情報を基に行う、ジョブスケジューリング方法であって、ジョブ管理情報が、処理の優先度情報と、それぞれの前記処理を実行可能な複数のジョブの実行時間情報とを有し、ＣＰＵの空き時間Ｔｉが生じる場合、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択する。また、ジョブ管理情報が、複数のジョブの実測実行時間情報を有し、実測実行時間情報を基に、ジョブを選択する。このため、本実施の形態のジョブスケジューリング方法は、マルチ画面処理回路が処理に要する時間が変化しても、プロセッサの能力を効率的に使うことができる。
【００７２】
＜第１の実施の形態の変形例＞
以下、第１の実施の形態の変形例のジョブスケジューリング方法について説明する。なお本変形例にかかるスケジューリング方法は、第１の実施の形態にかかるスケジューラ１００によるスケジューリング方法と類似しているため、同じ箇所の説明は省略する。本変形例のジョブスケジューリング方法を行うスケジューラ１０１は、各定周期処理の度に、必ず予約時間内に処理が完了するように、各ジョブの最悪実行時間に基づいてジョブスケジューリングを行う。そして、一のジョブを実行する度に、スケジューラ１０１は、そのジョブの実測実行時間情報と、これから実行予定の残りのジョブの実測実行時間情報とから空き時間Ｔｉを推算し、再スケジューリングＡができる程、空き時間Ｔｉがある場合にのみ、再スケジューリングＡを行う。そして、全てのジョブの実行が終了、すなわち１周期の定周期処理が終了後に、再び、最悪実行時間に基づくジョブスケジューリングにキュー情報をリセットする。
【００７３】
あるいは、スケジューラ１０１は、各定周期処理の度に、所定の空き時間Ｔｋが生じるように、各ジョブの実測実行時間情報に基づいてジョブスケジューリングを行ってもよい。ここで、所定の空き時間Ｔｋとは処理開始前に入力される情報であり、確実に予約時間内に処理を完了するための安全係数的なパラメータである。所定の空き時間Ｔｋは、処理速度の変動に応じて決定されるが、予約時間の１０〜３０％が好ましい。前記範囲未満では、予約時間内に処理が完了しないことがあり、前記範囲を超えるとプロセッサの使用効率が良くはない。
【００７４】
本変形例のジョブスケジューリング方法では、第１の実施の形態のジョブスケジューリング方法が有する効果に加えて、確実に予約時間内に処理を完了することができ、処理の信頼性が向上する。
【００７５】
＜第２の実施の形態＞
次に、本発明の第２の実施の形態にかかるスケジューラ１０２について説明する。なお、第２の実施の形態にかかるスケジューリング方法は、第１の実施の形態にかかるスケジューラ１００によるスケジューリング方法と類似しているため、同じ構成要素には同じ符号を付し説明は省略する。
【００７６】
図８は、第２の実施の形態にかかるスケジューリング方法の処理の流れを説明するためのフローチャートであり、り、図９は、スケジューラ１０２による再スケジューリングＢを説明するための説明図である。
【００７７】
本実施の形態にかかるスケジューリング方法においては、プロセッサの能力を効率的に使うために、最悪実行時間ではなく、実測実行時間を元にスケジューリングを行う。このため、処理が予約時間内に完了しない可能性がゼロではない。このため、本実施の形態にかかるスケジューリング方法においては、処理が予約時間内に完了しない場合には、再スケジューリングＢを行い、速やかに処理の完了を図る。ここで、処理が予約時間内に完了しない場合とは、実際に完了できなかった場合、および／または完了できない見込みの場合を意味する。
【００７８】
以下、図８のフローチャートに従い、本実施の形態のスケジューリング方法について説明する。
図８に示すように、本実施の形態にかかるスケジューリング方法は、ステップＳ１０から、ステップＳ１５およびステップＳ１６までは第１の実施の形態にかかるスケジューリング方法と同じであるため、ステップＳ１７以降の再スケジューリングＢについて説明する。
【００７９】
前述のように、本実施の形態のスケジューリング方法では、プロセッサの能力を効率的に使うために最悪実行時間を基にしたスケジューリングでは予約時間内に処理が完了しないジョブを登録している。このため、処理を実行した際に、処理が予約時間内に完了しないことがある。処理が予約時間内に完了しなかった場合、スケジューラ１０２は、ステップＳ１６において、Ｙｅｓと判断し、ステップＳ１７において再スケジューリングＢを行う。
【００８０】
＜ステップＳ１７＞
再スケジューリングＢについて、図９を用いて説明する。例えば、図９のスケジュールＢ０に示した様に、ジョブＡ１３の実測実行時間が４ｍｓで、ジョブＡ２３の実測実行時間が１９ｍｓであったために、スケジューラ１０２が予約時間２３ｍｓで処理が完了すると予定して、ジョブ１３およびジョブＡ２３をキューメモリ１０８に登録し実行していた場合に、入力画像信号等に変化が生じて、実測実行時間が増加することがある。
【００８１】
例えば、図９の実行予定結果７に示すように、ジョブＡ１３の実測実行時間ｔＡ１３が４ｍｓから１０ｍｓに急増すると、残りの予約時間は１３ｍｓしかないため、１９ｍｓを要する予定、すなわち、実測実行時間が１９ｍｓのジョブＡ２３を予約時間内には実行できない見込みとなってしまう。このように実測実行時間情報に基づき予約時間内に全ての処理が完了しない場合、スケジューラ１０２は、処理完了しないと判断し、ステップＳ１８において、再スケジューリングＢを行う。
【００８２】
＜ステップＳ１８＞
再スケジューリングＢでは、スケジューラ１０２は、未実行のジョブを、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の短いジョブを選択する。
【００８３】
この場合には、次に実行する予定の処理が、処理Ａ２のみであるので、処理Ａ２について再スケジューリングＢを行う。すなわち、選択器１０３は、実行予定のジョブＡ２３の次に実行時間の短いジョブＡ２２を選択し、リセット器１０２はキューメモリ１０８を、図９に示すスケジュールＢ１にリセットし、再びステップＳ１２で、ＣＰＵ１３はスケジュールＢ１に示したキューメモリ１０８の情報に従い、処理を行う。そして、スケジューラ１０２は、ステップＳ１３、ステップＳ１４、ステップＳ１５を行い、再び、ステップＳ１７で処理が予約時間内に完了したかの判断を行う。
【００８４】
＜ステップＳ１７＞
図９の実行結果８に示すように、ジョブＡ２２が予約時間内に完了しなかった場合には、スケジューラ１０２は、処理完了しないと判断し、ステップＳ１８において、再スケジューリングＢを行う。
【００８５】
＜ステップＳ１８＞
再スケジューリングＢでは、スケジューラ１０２は、未実行のジョブを、優先度に基づき、かつ、複数のジョブの中で実行予定のジョブの次に実行時間の短いジョブを選択する。すなわち、再スケジューリングＢは、結果品質を低下するスケジューリングであるため、優先度に基づいて、とは、優先度の低い処理から結果品質の低いジョブを選択することを意味する。
【００８６】
この場合には、次に実行する予定の処理が、処理Ａ１および処理Ａ２と複数であるため、優先度に基づき、まず優先度の低い処理Ａ１について再スケジューリングＢを行う。すなわち、選択器１０３は、実行予定のジョブＡ１３の次に実行時間の短いジョブＡ１２を選択し、リセット器１０２はキューメモリ１０８を、図９に示すスケジュールＢ２にリセットし、再びステップＳ１２で、ＣＰＵ１３はスケジュールＢ２に示したキューメモリ１０８の情報に従い、処理を行う。そして、スケジューラ１０２は、ステップＳ１３、ステップＳ１４、ステップＳ１５を行い、再び、ステップＳ１７で処理が予約時間内に完了したかの判断を行う。
【００８７】
＜ステップＳ１７＞
図９の実行予定結果９に示すように、ジョブＡ１２の実測実行時間ｔＡ１２が８ｍｓであり、ジョブＡ２２の実測実行時間ｔＡ２２が１５ｍｓの場合には、スケジューラ１０２は、処理が完了できる見込み（Ｙｅｓ）と判断して、スケジューラ１０２は、再スケジューリングＢは行わないで、ステップＳ１９から、ステップＳ１２、ステップＳ１３、ステップＳ１４、ステップＳ１５を行い、再び、ステップＳ１７で処理が予約時間内に完了したかの判断を行う。
【００８８】
＜ステップＳ１７＞
図９の実行結果１０に示すように、ジョブＡ２２が予約時間内に完了した場合には、スケジューラ１０２は、処理完了（Ｙｅｓ）と判断して、処理を継続する。
【００８９】
このように、本実施の形態にかかるスケジューリング方法においては、第１の実施の形態のスケジューリング方法が有する効果に加えて、処理が予定時間内に完了しない場合には、再スケジューリングＢを行い、速やかに処理の完了を図ることができる。
【００９０】
なお、再スケジューリングＢを行った場合には、所定の期間あるいは入力画像信号の数等が変化するまで、再スケジューリングＡは行わないことが好ましい。再スケジューリングＡを行って結果品質を向上しても、次のフレーム処理の際に再び、処理が完了しないで、再スケジューリングＢが必要となる可能性が高いためである。
【００９１】
なお、マルチ画面処理が完了しないと、テレビジョン受像器はモニタに、最新の画像を表示できないため、前フレームの画像を表示する。すなわち、モニタ表示は、いわゆるフリーズ状態となる。しかし、フリーズ状態が、数フレーム分だけであれば、視聴者は気が付かない。このため、本実施の形態のジョブスケジューリング方法においては、第１の実施の形態のジョブスケジューリング方法に加えて、可能な限り高品質の出力画像を出力しつつ、処理未完了による悪影響は最小に留まるため、処理の信頼性が向上する
なお、上記実施の形態では、スケジューラ１００のジョブスケジューリング方法が、マルチ画像処理回路１１の画像サイズ変換処理とフォーマット変換処理との２の処理に用いられる例を示したが、３つ以上の処理のジョブスケジューリングに用いることもできる。また、それぞれの処理を実行可能なジョブを３ずつとしたが、４以上でもよいし、もちろん、処理毎のジョブの数は同数である必要はない。さらに、ジョブスケジューリングする処理が３つ以上の場合には、少なくとも２つの処理がそれぞれの処理を実行可能な複数のジョブを有していれば、他の処理を実行可能なジョブは、それぞれ１つのみでもよい。また、スケジューラ１００のジョブスケジューリング方法は、定周期実行する処理Ａについてのジョブスケジューリングだけでなく、処理Ａと組み合わせて定周期実行する処理Ｂについてのジョブスケジューリングも可能である。
【００９２】
さらに、再スケジューリングＡおよび再スケジューリングＢでは、１回の再スケジューリングで１つの処理のジョブを入れ替える例を示したが、１回の再スケジューリングで複数の処理のジョブを入れ替えてもよい。
【００９３】
また、スケジューラ１００によるジョブスケジューリングは、例えば、音声処理回路に用いてもよいし、データ誤り訂正回路に用いてもよい。さらに、スケジューラ１００によるジョブスケジューリングは、テレビジョン受像機１のデータ処理に限られるものではなく、定周期実行方式で、複数の異なる目的の処理を行うためのスケジューリングを、ジョブ管理情報を基に行うジョブスケジューリング方法であれば、汎用用途で用いることが可能であり、いずれの場合も、プロセッサの能力を効率的に使うことができる。
【００９４】
本発明は、上述した実施の形態に限定されるものではなく、本発明の要旨を変えない範囲において、種々の変更、改変等が可能である。
【図面の簡単な説明】
【００９５】
【図１】第１の実施の形態にかかるマルチ画面処理回路を有するテレビジョン受像機１の構成を示した構成図である。
【図２】テレビジョン受像機のマルチ画面の例を示した図である。
【図３】第１の実施の形態にかかるスケジューラのブロック図である。
【図４】第１の実施の形態にかかる、ジョブ管理情報の例を示した表である。
【図５】画像サイズ変換処理が実行可能な複数のアルゴリズムが異なるジョブを説明するための説明図である。
【図６】第１の実施の形態のスケジューリング処理の流れを説明するためのフローチャートである。
【図７】第１の実施の形態にかかるスケジューラによる再スケジューリングＡを説明するための説明図である。
【図８】第２の実施の形態のスケジューリング処理の流れを説明するためのフローチャートである。
【図９】第２の実施の形態にかかるスケジューラによる再スケジューリングＢを説明するための説明図である。
【符号の説明】
【００９６】
１…テレビジョン受像機、２…パラボラアンテナ、４、５、６、７…デコーダー、８…ＨＤＤ、９…外部端子、１０…切替回路、１１…マルチ画面処理回路、１２…モニタ、１３…キューメモリ、１５…メモリ、２０…モニタ表示画面、１００…スケジューラ、１０２…リセット器、１０３…選択器、１０５…ジョブ管理情報メモリ、１０６…動的情報、１０７…基本情報、１０８…キューメモリ、ＴＡ１、ＴＡ２…実測実行時間、Ｔｉ…空き時間
【特許請求の範囲】
【請求項１】
ジョブ管理情報を基に、ＣＰＵが、予約時間内に複数の処理を実行する定周期実行方式のスケジューリングを行う、ジョブスケジューリング方法であって、
前記ジョブ管理情報が、
前記複数の処理のそれぞれの優先度情報と、
前記複数の処理のそれぞれを実行可能な複数のジョブの実行時間情報とを有し、
前記ＣＰＵの空き時間が生じる場合、優先度に基づき、かつ、前記複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択することを特徴とするジョブスケジューリング方法。
【請求項２】
前記ジョブ管理情報が、前記複数のジョブの実測実行時間情報を有し、
前記実測実行時間情報を基に、前記ジョブを選択することを特徴とする請求項１に記載のジョブスケジューリング方法。
【請求項３】
前記実測実行時間情報に基づき予約時間内に全てのジョブが完了しない場合、未実行の前記ジョブを、前記優先度に基づき、かつ、前記複数のジョブの中で実行予定のジョブの次に実行時間の短いジョブを選択する請求項１または請求項２に記載のジョブスケジューリング方法。
【請求項４】
前記複数の処理の結果品質のバランスを考慮し、ジョブを選択することを特徴とする請求項１から請求項３のいずれか１項に記載のジョブスケジューリング方法。
【請求項５】
前記ＣＰＵが、テレビジョン受像機のマルチ画面処理のスケジューリングを行うことを特徴とする請求項１から請求項４のいずれか１項に記載のジョブスケジューリング方法。
【請求項１】
ジョブ管理情報を基に、ＣＰＵが、予約時間内に複数の処理を実行する定周期実行方式のスケジューリングを行う、ジョブスケジューリング方法であって、
前記ジョブ管理情報が、
前記複数の処理のそれぞれの優先度情報と、
前記複数の処理のそれぞれを実行可能な複数のジョブの実行時間情報とを有し、
前記ＣＰＵの空き時間が生じる場合、優先度に基づき、かつ、前記複数のジョブの中で実行予定のジョブの次に実行時間の長いジョブを選択することを特徴とするジョブスケジューリング方法。
【請求項２】
前記ジョブ管理情報が、前記複数のジョブの実測実行時間情報を有し、
前記実測実行時間情報を基に、前記ジョブを選択することを特徴とする請求項１に記載のジョブスケジューリング方法。
【請求項３】
前記実測実行時間情報に基づき予約時間内に全てのジョブが完了しない場合、未実行の前記ジョブを、前記優先度に基づき、かつ、前記複数のジョブの中で実行予定のジョブの次に実行時間の短いジョブを選択する請求項１または請求項２に記載のジョブスケジューリング方法。
【請求項４】
前記複数の処理の結果品質のバランスを考慮し、ジョブを選択することを特徴とする請求項１から請求項３のいずれか１項に記載のジョブスケジューリング方法。
【請求項５】
前記ＣＰＵが、テレビジョン受像機のマルチ画面処理のスケジューリングを行うことを特徴とする請求項１から請求項４のいずれか１項に記載のジョブスケジューリング方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２００９−１５１３７５（Ｐ２００９−１５１３７５Ａ）
【公開日】平成２１年７月９日（２００９．７．９）
【国際特許分類】
【出願番号】特願２００７−３２６３７２（Ｐ２００７−３２６３７２）
【出願日】平成１９年１２月１８日（２００７．１２．１８）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３９００１０３０８）東芝デジタルメディアエンジニアリング株式会社 (192)
【Ｆターム（参考）】
【公開日】平成２１年７月９日（２００９．７．９）
【国際特許分類】
【出願日】平成１９年１２月１８日（２００７．１２．１８）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【出願人】（３９００１０３０８）東芝デジタルメディアエンジニアリング株式会社 (192)
【Ｆターム（参考）】
[ Back to top ]