(57)【要約】本発明は、データ要素の時間依存ストリームを処理するハードリアルタイムシステムにおいて、部品がスケジューリング可能であるときを決める方法に関する。前記部品の数が前記部品を処理するのに利用可能なプロセッサの数よりも多く、これら部品の各々は少なくとも１つの入力と少なくとも１つの出力とを持つ。前記部品は、部品が前記システムの出力に寄与することができる最も早い時間を決め、前記最も早い時間で出力に寄与することができる部品をスケジューリングすることにより、スケジューリングされる。本発明は上記スケジューリングを行うための手段を用いて、データ要素の時間依存ストリームを処理するハードリアルタイムシステムにも関する。
2006509285.tif 000002
【特許請求の範囲】
【請求項１】
データ要素の時間依存ストリームを処理するハードリアルタイムシステムにおけるスケジューリング可能な部品をスケジューリングする方法であり、前記スケジューリング可能な部品の数は、当該部品を処理するのに利用可能なプロセッサの数よりも多く、前記部品の各々は少なくとも１つの入力及び１つの出力を持つ方法において、前記方法は、
−前記部品が前記ハードリアルタイムシステムの前記出力に寄与することができる最も早い時間を、各スケジューリング可能な部品に対し決定するステップと、
−全体的な前記最も早い時間で前記リアルタイムシステムの前記出力に寄与することができる前記スケジューリング可能な部品をスケジューリングするステップと、
を連続して有することを特徴とする方法。
【請求項２】
多数のスケジューリング可能な部品が同じ前記全体的な最も早い時間で、前記リアルタイムシステムの前記出力に寄与する場合、前記多数の部品のスケジューリングはプッシュスケジューリングを用いて行われる請求項１に記載の方法。
【請求項３】
各部品に対し既定の時間間隔の長さが指定され、タイムスタンプ付きデータ要素の前記時間依存ストリームの前記既定の時間間隔からの前記タイムスタンプ付きデータ要素が前記部品の全ての入力において利用可能である場合、部品がスケジューリング可能である請求項１又は２に記載の方法。
【請求項４】
前記タイムスタンプ付きデータ要素の前記既定の時間間隔の利用可能性は、前記既定の時間間隔の開始時間及び終了時間を規定し、先行する部品によりデータが処理されるまでの時間が前記既定の時間間隔の終了時間よりも新しいときをチェックすることにより決められる請求項３に記載の方法。
【請求項５】
前記部品が前記出力に寄与することができる前記最も早い時間を決めるステップは、
−前記部品から前記システムの出力に達するために、前記データ要素が処理されなければならない後続する部品の可能な経路を識別するステップと、
−前記既定の時間間隔の開始時間から、前記経路における前記後続する部品の各々に指定される前記既定の時間間隔の各々の長さを減算することにより、各可能な経路に対する最も早い寄与時間を決めるステップと、
−前記部品が前記出力に寄与することができる前記最も早い時間を最も早い決められた寄与時間と決めるステップと、
により行われる請求項３又は４に記載の方法。
【請求項６】
前記部品が前記出力に寄与することができる前記最も早い時間を決めるステップは、
−前記部品から前記システムの出力に達するために、前記データ要素が処理されなければならない後続する部品の経路を識別するステップと、
−前記既定の時間間隔の前記開始時間から、前記経路における前記後続する部品の各々に指定される前記既定の時間間隔の各々の長さを減算することにより、各可能な経路に対する最も早い寄与時間を決めるステップであり、前記既定の時間間隔の少なくとも幾つかは変位値を減算してあるステップと、
−前記部品が前記出力に寄与することができる前記最も早い時間を前記最も早く決められた寄与時間と決めるステップと、
により行われる請求項３又は４に記載の方法。
【請求項７】
データ要素の時間依存ストリームを処理するハードリアルタイムシステムにおいて、前記システムは多数の部品と、部品を処理するための多数のプロセッサとを有し、前記部品の数は前記プロセッサの数よりも多く、前記部品の各々は少なくとも１つの入力と少なくとも１つの出力とを持ち、前記システムは、前記部品が前記ハードリアルタイムシステムの出力に寄与することができる最も早い時間を、各スケジューリング可能な部品に対し決める手段と、前記全体的な最も早い時間で前記リアルタイムシステムの前記出力に寄与することができる前記スケジューリング可能な部品をスケジューリングする手段とを有するハードリアルタイムシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ要素の時間依存ストリームを処理するハードリアルタイムシステム(hard real-time system)における部品をスケジューリングする方法に関する。本発明はさらに、データ要素の時間依存ストリームを処理するハードリアルタイムシステムにも関する。
【背景技術】
【０００２】
リアルタイムソフトウェアシステムにおいて、部品の数は利用可能なプロセッサの数よりも多く、部品は処理時間を争い、部品のスケジューリングは信頼性と素早さとを必要とする。このコンテキストにおいて、出力が生成される時間が必須である如何なるソフトウェアシステムもリアルタイムソフトウェアシステムと呼ばれる。リアルタイムソフトウェアシステムの入力時間からその出力時間までのラグ、すなわち遅延は許容できる適時性(timeliness)に対し十分小さいものでなければならない。ハードリアルタイムソフトウェアは、境界付けされた時間間隔内において外部に生成された入力に応答しなければならない。このコンテキストにおけるソフトウェアシステムは一般に、多くの相互接続された部品から構成され、これら部品間における唯一の相互作用はこれら部品のインタフェースによるものであり、部品は状態情報を共有しない。
【０００３】
この種類のシステムにおいて、スケジューラはシステムレベルにおけるリアルタイムの制約が満たされるように処理間隔を部品に割り当てる。部品のスケジューリングは、ある期間にわたり継続的に繰り返される２つのフェーズから成る。最初に、スケジューリング可能な部品の組が決められ、次いでこの組から、且つ何らかの優先順位付け方式に従って、（１つの部品が各プロセッサ上で実行される）プロセッサ上で実際に実行される部品の一部(sub set)が選択される。
【０００４】
多くの優先順位付け方式は知られている。
・ラウンドロビン方式(Round Robin Scheme)
スナップショット(snapshot)はスケジューリング可能な部品の組から作られる。この組は、任意に順位付けされ、これら部品は１つずつスケジューリングされる。全てのスケジューリング可能な部品がスケジューリングされた後、これらスケジューリング可能な部品の組が更新される。
・固定優先順位方式(Fixed Priority Scheme)
各部品はある固定された優先順位を持つ。これらスケジューリング可能な部品の組から、最も高い優先順位を持つ部品が選択される。次に、これらスケジューリング可能な部品の組が更新され、この新しい組から、最も高い優先順位を持つ部品が選択される、等である。
・フレキシブル優先順位方式(Flexible Priority Scheme)
各部品は、時間の経過に連れて変化する優先順位を得る。スケジューリング可能な部品の組から、そのときに最も高い優先順位を持つ部品が選択される。次に、これらスケジューリング可能な部品の組が更新され、これら部品の優先順位が再計算される。この新しい組から、最も高い優先順位を持つ部品が選択される、等である。
・優先順位ベースのプリエンプティブスケジューリング(Priority-based Pre-emptive Scheduling)
このスケジューリングに対する手法は、固定の又はフレキシブルな優先順位と組み合わされることができる。高い優先順位を持つ部品が、低い優先順位を持つ部品を処理している間にスケジューリング可能となる場合、低い優先順位を持つ部品の処理が中断され、最初に高い優先順位を持つ部品を処理することができる。
・パイプライン又はプッシュスケジューリング(Pipeline or Push Scheduling)
部品の有向グラフ(directed-graph)のソースが任意に順位付けされる。これらスケジューリング可能なソースは１つずつ処理されるが、各ステップの後に、スケジューリング可能な組が更新され、データはグラフを介して可能な限りプッシュされる。ソースの処理によって、もはや部品がスケジューリングされない場合、次のスケジューリングソースが処置される。
【０００５】
ここで考慮される問題は、スケジューリング可能な部品の組からスケジューリング可能な部品の最適な選択を行う有効な優先順位付け方式を見つけることである。
【０００６】
米国特許公開番号2002/0062435は、複数のスレッドを処理するために複数のストリームを備えるマルチストリーミングプロセッサと、１つ又は複数のストリームのためのプライオリティコードのプライオリティレコードを備える命令スケジューラとを記載している。これらプライオリティコードは幾つかの実施例において、どのストリームがいかなる時点でアクセスしたかを決めるだけでなく、リソースへの相対的アクセスを決定する。他の実施例では、プライオリティは動的に決定され、即座に変更される、すなわち、オンチップ処理統計情報のような様々な基準によって、１つ又は複数のプライオリティアルゴリズムを実行することにより、オフチップからの入力によって、ストリーム負荷に従って、あるいは、これら方法を組み合わせにより決定、変更が行われる。
【０００７】
米国特許US6,195,701は、多数のデータストリーム及び実時間タスクを同期及びスケジュールする方法を記載している。スケジュールの基準は、例えばストリーミング処理の状態に関するようなトリガ条件により決められる。このような状態は次に、ストリームの時間マーク及びシステムの時間に再び関係する。この文書は、部品をスケジューリングを行うことにより、１つのプロセッサを用いてストリーミングを実行し、ストリーミングを制御する問題は解決していない。
【０００８】
一方では、上述されたデータ処理（ハンドリング）は、システムにとって利用可能である最も高い出力レートに適合しないことが分かっている。従来技術は一般的に、データシーケンスにおける次のデータに利用可能な処理リソースを割り当てる。これは、処理パイプラインにおいて同じ処理優先順位が割り当てられた２つのデータストリームが処理リソースを待っている場合、ラインにおいて最初のデータストリームが第１のストリームとして処理されることを意味する。これは、処理ツリー構造における処理動作は、出力が生成される前のかなりの時間、ロックされているので、幾つかのアプリケーションにおいては不便である。この不便さは前記処理ツリーの深さと共に大きく増大する。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、システムのハードリアルタイム動作を達成し、上述した問題を解決するのに適した、スケジューリングする方法を提供することである。
【課題を解決するための手段】
【００１０】
これはデータ要素の時間依存ストリームを処理するハードリアルタイムシステムにおいてスケジューリング可能な部品をスケジューリングすることにより得られ、ここで、スケジューリング可能な部品の数は前記部品を処理するのに利用可能なプロセッサの数よりも多く、前記部品の各々は少なくとも１つの入力及び１つの出力を持つ方法において、前記方法は、
−前記部品が前記ハードリアルタイムシステムの出力に寄与することができる最も早い時間を、各スケジューリング可能な部品に対し決定するステップと、
−全体的な最も早い時間で前記リアルタイムシステムの出力に寄与することができる前記スケジューリング可能な部品をスケジューリングするステップと、
を連続して有することを特徴とする。
【００１１】
これは、前記出力に寄与するスケジューリング可能な部品が存在する場合、出力の生成に寄与しないスケジューリング可能な部品には処理時間を費やさないことを意味している。
【００１２】
ある実施例において、前記多数の部品をスケジューリングすることは、多数のスケジューリング可能な部品が同じ全体的な最も早い時間で、前記リアルタイムシステムの出力に寄与する場合、プッシュスケジューリング(push scheduling)を用いて行われる。プッシュスケジューリングは、この場合、他のスケジューリング方法よりもより少ないコンテキストの切り換えを取り入れる。コンテキストの切り換えを最小にすることは、低いポート間遅延もサポートする。
【００１３】
他の実施例において、各部品に対し既定の時間間隔の長さが指定され、タイムスタンプ付きデータ要素の時間依存ストリームの既定の時間間隔からのタイムスタンプ付きデータ要素が前記部品の全ての入力において利用可能である場合、部品はスケジューリング可能である。出力への最も早い寄与をある程度決めるための時間ボックススケジューリングと組み合わせが可能であり、これは再計算するのに容易である。
【００１４】
特定の実施例において、前記タイムスタンプ付きデータ要素の前記既定の時間間隔の利用可能性は、前記既定の時間間隔の開始時間及び終了時間を規定し、先行する部品によりデータが処理されるまでの時間が前記既定の時間間隔の終了時間よりも新しいときをチェックすることにより決められる。これは、部品がスケジューリング可能であるかチェックすることを簡単な方法で可能にする。
【００１５】
ある実施例において、前記部品が出力に寄与することができる最も早い時間を決めるステップは、
−前記部品から前記システムの出力に達するために、データ要素が処理されなければならない後続する部品の可能な経路を識別するステップと、
−前記既定の時間間隔の開始時間から、前記経路における前記後続する部品の各々に指定される既定の時間間隔の各々の長さを減算することにより、各可能な経路に対する最も早い寄与時間を決めるステップと、
−前記部品が出力に寄与することができる最も早い時間を前記最も早い決められた寄与時間と決めるステップと、
により行われる。
【００１６】
これは、如何なる出力、すなわち出力に達する如何なる経路も優先しない“最も早い寄与”をある程度規定するやり方である。
【００１７】
特定の実施例において、前記部品が出力に寄与することができる最も早い時間を決めるステップは、
−前記部品から前記システムの出力に達するために、データ要素が処理されなければならない後続する部品の経路を識別するステップと、
−前記既定の時間間隔の開始時間から、前記経路における前記後続する部品の各々に指定される既定の時間間隔の各々の長さを減算することにより、各可能な経路に対する最も早い寄与時間を決めるステップであり、前記既定の時間間隔の少なくとも幾つかは変位値を減算してあるステップと、
−前記部品が出力に寄与することができる最も早い時間を最も早く決められた寄与時間と選択するステップと、
により行われる。
【００１８】
これは、データフローを前記システムに流させるために変位が用いられる場合、どのスケジューリング可能な部品が最も早い時間で出力に寄与することができるかを決めることを簡単なやり方で可能にする。
【００１９】
本発明は、データ要素の時間依存ストリームを処理するハードリアルタイムシステムにも関し、このシステムは多数の部品と、これら部品を処理するための多数のプロセッサを有し、前記部品の数は前記プロセッサの数よりも多く、前記部品の各々は少なくとも１つの入力と少なくとも１つの出力とを持ち、前記システムは、前記部品が前記ハードリアルタイムシステムの出力に寄与することができる最も早い時間を、各スケジューリング可能な部品に対し決定する手段と、前記全体的な最も早い時間で前記リアルタイムシステムの出力に寄与することができるスケジューリング可能な部品をスケジューリングする手段とを有する。
【００２０】
本発明は、例えばビデオ及びオーディオ処理システムのような処理済（ＭＰＥＧ２、ＭＰＥＧ４）及び未処理領域におけるリアルタイムシステムに用いられることができる。さらに、リアルタイムシステムは画像処理、画像認識、工業的オートメーション、パターン認識及びレーダー並びにテレコミュニケーションである。
【発明を実施するための最良の形態】
【００２１】
以下に、本発明は、ストリーミング処理を行うためのハードリアルタイムシステムにおけるソフトウェア部品を時間ボックス駆動型スケジューリングするのに用いられることが記載されている。最初に、時間ボックス駆動型スケジューリングが記載され、スケジューリング可能な部品が本発明に従ってスケジューリングされる方法の記載が続く。
【００２２】
システムは、あるタスクを行う装置であり、このタスクを行うやり方は管理及び制御により影響する。好ましい実施例において、前記あるタスクはストリーミングデータのハードリアルタイム処理に制限される。部品は前記システムの自己完結型(self-contained)の部分であり、“原子(atomic)”であるサブタスク、すなわちこのサブタスクをさらに分割することが有用であるとは考えられないサブタスクを実行する。サブタスクをさらに分割するかの動機付けは、リマルチプレクサ、符号化器等のアプリケーション領域における経験に基づいている。タイムスタンプ付きデータ要素は、ストリームにおけるデータの表示である。ストリーミングデータはデータコンテンツ及び時間情報を持つと仮定される。この時間情報は、前記要素を順番に並べると共に、データを時間と関連付けるのに用いられる。時間ボックスはタイムスタンプ付きデータ要素からなる既定の時間間隔である。
【００２３】
本発明によるシステム内では、アルゴリズム時間が用いられる。最後に、出力ストリームに対する生成される時間情報は、再びリアルタイムに関連する。システム時間からアルゴリズム時間への変換は、例えばシステムの入力及びシステムの出力に置かれる従来の時間フィルタにより行われる。
【００２４】
図１は２つの部品間にあるコネクタを説明している。このコネクタはシステムの自己完結型の部品である。ソース部品１０１はコネクタ１０５によりシンク部品１０３に接続されている。コネクタ１０５の動的状態は、データ要素及び生成までの時間(produced-until time)（ソース部品によりデータが生成されるまでの時間）ｓｐｃを有するコネクタ１０５における多数の要素から成る。データ要素は、アルゴリズム時間ｓｉを用いてマーキングされ、コネクタのソース側にあるソース部品のスケジューリングのために、コネクタに追加されることができる。前記ソース部品をスケジューリングすることは、特定のコネクタに対する前記生成までの時間も更新する。前記コネクタのシンク側にある部品は、この部品がスケジューリングされる場合、データ要素を処理することにより、これらデータ要素を取り除くことができる。各部品に対し、現在の時間ボックスが規定され、この時間ボックスは開始時間と終了時間とを持つ。部品をスケジューリングするために、前記時間ボックスは、前記部品の入力において全てのコネクタに対し満たされなければならず、これは、時間ボックスの開始時間から終了時間までの時間間隔におけるタイムスタンプｓｉを持つ全てのデータ要素は、準備が整っている／表されていることを意味する、言い換えると、前記生成までの時間が現在の時間ボックスの終了時間よりも新しいことを意味する。
【００２５】
図２は、部品のスケジューリング能力(scheduleability)を規定し、スケジューリングされた部品を実行する処理を一般的なステップで説明する。この処理は、時間ボックスを部品の各コネクタに割り当てるステップと、このスケジューリングされた部品を実行するステップとを有する。２０１において、現在の時間ブロックが前記部品に割り当てられる。これは、前記部品により処理されるべき次のデータ要素の時間間隔の開始時間と終了時間とを規定することにより行われる。スケジューラは、例えば現在の時間ボックスの割り当てを行うことができる。特定のコネクタにおけるデータ要素が、これらデータ要素がソース部品により処理されたことを意味する、準備が整っている場合、現在の時間ボックス内のデータは準備が整っている。部品がスケジューリング可能となるために、この現在の時間ボックスが部品の各入力コネクタに対し満たされなければならない。２０３において、この部品がスケジューリングされ、現在の時間ボックスの境界内にある、全てのコネクタにおけるデータ要素が部品により消費及び処理される。処理されたデータ要素は、部品の出力部において準備が整ってあり、各出力コネクタに対する生成までの時間ｓｐｃが更新される。２０１において、新しい現在の時間ボックスが前記部品に割り当てられる。これは、前記部品に対し先行する時間ボックスの終了時間に等しい新しい開始時間を規定することにより行われる。
【００２６】
図３は、特定の部品に対する現在の時間ボックスを割り当てることが可能であるかを判断する方法を説明する流れ図である。この判断は、部品の形式に依存する２つのシナリオに従って行われる。第１の形式はΔｓ部品であり、第２の形式は＃ｎ部品である。３０１において、部品がΔｓ部品である場合、３０３において、現在のアルゴリズム時間ＣＳが、現在の時間ボックスの開始時間ＢＳに時間ボックスの長さである既定の時間間隔Δｓを加えたものよりも大きいかチェックされる。現在の時間ボックスの開始時間は先行する時間ボックスの終了時間に等しい。それが真である場合、３０５において、この時間ボックスは部品を規定され、割り当てられることができ、それが偽である場合、３０７において、部品が時間ボックスにおけるデータ要素を最後に処理してから十分な時間がまだ経過していないとして、時間ボックスの無い！ＴＢが規定され、割り当てられる。３０９において部品が＃ｎ部品である場合、特定のコネクタ、つまり＃ｎコネクタにおいて利用可能な既定数のデータ要素があるか３１１において最初にチェックされる。それが真である場合、時間ボックスＴＢが３０５において規定される。ここで開始時間は先行する時間ボックスの終了時間であり、終了時間は特定のコネクタにおいて利用可能な最新のデータ要素のタイムスタンプである。それが真ではない場合、現在のアルゴリズム時間が現在の時間ボックスの開始時間に変位値ｄを加えたものよりも大きいか３１３においてチェックされる。それが真である場合、データ要素は準備が整ってあり、３０５において時間ボックスが規定される。それが偽である場合、十分なデータ要素がまだｎ番目のコネクタに現れていないと、時間ボックスの無い！ＴＢが規定される。一般的に、Δｓ部品は、現在の時間ボックスにおけるデータの僅かな変化量を扱うことができる一方、＃ｎ部品は＃ｎコネクタとして特定される入力から同じデータ量を得る。
【００２７】
実施例において、部品を割り当てられた現在の時間ボックスは、図４に説明されるように、各コネクタに対し時間で移動する。４０１において、多数の入力部（Ｉ１…Ｉｎ）と３つの出力部（Ｑ１、Ｑ２、Ｑ３）とを持つ１つの部品が記載されている。時間ボックスＴＢは、４０３により示されるように、開始時間ＢＳ及び終了時間ＥＳを持つ部品に割り当てられる。本実施例において、出力部Ｑ１は変位しない、出力部Ｑ２は正の変位であり、出力部Ｑ３は負の変位である。ある出力コネクタに対する生成までの時間は、出力の変位を加えることにより、時間ボックスの終了時間に直接リンク付けされる。
ｓｐＣＱ＝ＥＳ（ＴＢ）＋ΔｓＱ
ここで、ＣＱは、部品の出力Ｑに取り付けられたコネクタであり、ｓｐＣＱは、コネクタＣＱの生成までの時間であり、ＥＳ（ＴＢ）は、部品４０１がスケジューリングされるのに用いた時間ボックスＴＢの終了時間であり、ΔｄＱは前記部品の出力Ｑの変位である。
【００２８】
図５を用いて、部品のスケジューリング可能性を決定する場合、スケジューラが時間ボックスを使用する方法が記載されている。このスケジューリング可能性は、部品の各入力コネクタをチェックすることにより決められ、コネクタに対する生成するまでの時間ｓｐｃが部品の時間ボックスの終了時間ＥＳに等しいか又は大きい場合、５０３において、このコネクタは前記部品にスケジューリングされる資格を与えさせる。そうでなければ、５０５において、この部品はスケジューリングされる準備が整っていない。前述したように、部品の各入力コネクタは、前記部品にスケジューリングされる資格を与えるように、資格を与えなければならない。
【００２９】
部品が時間ボックス駆動型スケジューリングによりスケジューリング可能となる方法が記載されてあり、以下において、本発明の実施例に従い、スケジューリングされるべき部品を選択する方法と、前記スケジューリング可能な部品が柔軟な優先順位方式で順序付けされる方法を記載している。
【００３０】
全てのスケジューリング可能な部品は、その部品のスケジューリングが出力に寄与し、最も高い優先順位は、出力に最も早く寄与する部品に与えられる時点に基づく柔軟な優先順位を得る。各ステップの後、スケジューリング可能な部品の組は更新され、これらスケジューリング可能な部品の優先順位が再計算される。これにより、データはグラフを介し、ここで最終結果により早く寄与する部品が最初に扱われる。１つより多くの部品が最も高い優先順位を持つ場合、これら部品にプッシュスケジューリングが適用される。
【００３１】
ある部品が出力に寄与する最も早い時間を計算する１つの方法は、前記部品から出力への経路を用いて、次に、前記部品から前記出力への前記経路上にある全ての時間ボックスの時間長を減算した新しい時間ボックスの開始時間として、最も早い時間を計算することにより行われる。この計算を行うことにより、最も早い可能な時間が計算される。部品がスケジューリングされるときに処理される、時間ボックスにおける第１のタイムスタンプ付きデータ要素は、前記経路における次の部品に対する時間ボックスにおける欠落したタイムスタンプ付きデータ要素に等しいと仮定される。この仮定は出力への経路における各部品に対し行われ、これにより前記部品が出力に寄与する最も早い時間が見つけられる。
【００３２】
多数の部品がスケジューリング可能である場合、
Ｍｉｎ｛ｓｐＸ−ΔｓＸｐ｜ｐは部品Ｘから出力への経路である｝
の式が用いられ、どの部品が最も早い時間で出力に寄与することができ、これにより、どの部品がスケジューリングするかが分かる。ｓｐＸは、部品Ｘの現在の時間ボックスの開始時間に等しい部品Ｘの生成までの時間であり、ΔｓＸｐは部品Ｘから出力への経路ｐにおける部品の各時間ボックスに関連する各既定の時間間隔である長さの合計である。特定の実施例において、時間的遅延が存在し、これにより、経路における２つ以上の部品間の接続における時間的変位が存在する。この場合において、経路ｐに沿った全変位ΔｄＸｐは、
Ｍｉｎ｛ｓｐＸ−（ΔｓＸｐ−ΔｄＸｐ）｝
のように減算されるべきである。
【００３３】
２つの部品が上述したようにスケジューリングされるべき場合、これら２つの部品が同じ最も早い時間で出力に寄与することができ、次にプルスケジューリング(pull scheduling)が、どの部品をスケジューリングするかを決めるのに用いられることを意味する。
【００３４】
図６において、上記に従うシステムにおけるスケジューリング可能な部品のスケジューリングを説明するのに用いられるハードリアルシステムの一例が記載されている。このシステムは４つの部品Ａ、Ｂ、Ｃ及びＤからなり、これら全てはΔｓ部品である。ここで、部品Ａはコネクタ６０１を介して部品Ｂに接続される入力部品であり、部品Ｂはコネクタ６０３を介して出力部品である部品Ｃに接続され、部品Ｄはコネクタ６０５を介して出力部品Ｃに接続される入力部品である。各コネクタにおいて、時間ボックス６０７、６０９、６１１及び６１３が記載されてあり、各時間ボックスと一緒に、各時間ボックスに関連する既定の時間間隔の長さを説明する時間間隔ΔｓＡ、ΔｓＢ、ΔｓＣ及びΔｓＤが示されている。入力部品Ａ及びＤはデータの一定のストリームを入力し、これにより十分なデータ要素が常に時間ボックス６０７及び時間ボックス６１１を満たしていることが示される。これは、部品Ａ及びＤが常にスケジューリング可能であることも意味している。
【００３５】
以下において、部品Ａ、Ｂ、Ｃ及びＤのスケジューリングは図７ａから図７ｆを用いて説明される。全ての図において、各部品Ａ、Ｂ、Ｃ及びＤは、これら部品Ａ、Ｂ、Ｃ及びＤに関連する既定の時間間隔からなる時間間隔ΔｓＡ、ΔｓＢ、ΔｓＣ及びΔｓＤと一緒に示されている。さらに、時間ライン７００はアルゴリズム時間ｓを記載し、各部品Ａ、Ｂ、Ｃ及びＤに対し、生成までの時間はそれぞれ、ｓｐＡ、ｓｐＢ、ｓｐＣ及びｓｐＤと示され、スケジューリングする時間ボックスの一般的な特性により、各部品に対する生成までの時間は、この部品に関連する現在の時間ボックスの開始時間に等しい。最初に、全ての時間ボックスの開始時間は同じであり、点で印されている。
【００３６】
図７ａにおいて、部品Ａが最初にスケジューリングされ、Ａ及びＤが共にスケジューリング可能となり、プッシュスケジューリングを用いてＡが選択される。
【００３７】
時間間隔７０１におけるデータ要素は、部品Ａにより処理され、生成までの時間ｓｐＡが増大する。部品Ａをスケジューリングした後、部品Ａ、部品Ｂ及び部品Ｄをスケジューリングするのに十分なデータが利用可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
により決められる。
【００３８】
この場合、Ｂ及びＤは共に、同じ最も早い時間で出力に寄与することができ、これによりプッシュスケジューリングが用いられ、部品Ｂがスケジューリングされる。
【００３９】
Ｂの時間軸において時間間隔７０２により記載される部品Ｂをスケジューリングした後、生成までの時間ｓｐＢは増大する。部品Ａ、部品Ｂ及び部品Ｄをスケジューリングするのに十分なデータが利用可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
により決められる。
【００４０】
部品Ｄは最も早い時間で出力に寄与することができ、これにより部品Ｄは時間間隔７０３に記載されるようにスケジューリングされる。Ｄの時間軸において、生成までの時間ｓｐＤは増大する。
【００４１】
図７ｂにおいて、部品Ａ、Ｂ及びＤをスケジューリングするのに十分なデータが依然として唯一利用可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
により決められる。
【００４２】
この時間部品Ｂは最も早い時間で出力に寄与することができ、これにより部品Ｂは時間間隔７０４に記載されるようにスケジューリングされる。
【００４３】
次に、部品Ａ、Ｂ及びＤが再びスケジューリングされ、上記計算を用いて、部品Ｄは時間間隔７０５に記載されるように再びスケジューリングされる。
【００４４】
図７ｃに記載されるように、部品Ｃをスケジューリングするのに十分なデータがここで利用可能であり、これにより、部品Ａ、Ｂ、Ｃ及びＤは共にスケジューリング可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
部品Ｃ：ｓｐＣ
により決められる。
【００４５】
部品Ｃは最も早い時間で出力に寄与することができ、これにより部品Ｃは時間間隔７０６に記載されるようにスケジューリングされる。
【００４６】
図７ｄから分かるように、これら部品をスケジューリング可能にさせる部品Ａ、Ｂ及びＤをスケジューリングするのに十分なデータがここで唯一利用可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
により決められる。
【００４７】
部品Ｂは最も早い時間で出力に寄与することができ、これにより部品Ｂは時間間隔７０７に記載されるようにスケジューリングされる。
【００４８】
図７ｅにおいて、これら部品をスケジューリング可能にさせる部品Ａ、Ｂ及びＤをスケジューリングするのに十分なデータが利用可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
により決められる。
【００４９】
部品Ｄは最も早い時間で出力に寄与することができ、これにより部品Ｄは時間間隔７０８に記載されるようにスケジューリングされる。
【００５０】
図７ｆにおいて、これら部品をスケジューリング可能にさせる部品Ａ、Ｂ及びＤをスケジューリングするのに十分なデータが利用可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
により決められる。
【００５１】
部品Ｂは最も早い時間で出力に寄与することができ、これにより部品Ｂは時間間隔７０９に記載されるようにスケジューリングされる。
【００５２】
図７ｇに記載されるように、部品Ｃをスケジューリングするのに十分なデータがここで利用可能であり、これにより部品Ａ、Ｂ、Ｃ及びＤは共にスケジューリング可能である。どの部品をスケジューリングするかは、最小数又は最も早い時間となる計算、つまり
部品Ａ：ｓｐＡ−（ΔｓＢ＋ΔｓＣ）
部品Ｂ：ｓｐＢ−ΔｓＣ
部品Ｄ：ｓｐＤ−ΔｓＣ
部品Ｃ：ｓｐＣ
により決められる。
【００５３】
部品Ｃは最も早い時間で出力に寄与することができ、これにより部品Ｃは時間間隔７１０に記載されるようにスケジューリングされる。
【００５４】
このスケジューリングは上述したのと同じように続けることができる。
【図面の簡単な説明】
【００５５】
【図１】２つの部品間にあるコネクタを示す。
【図２】部品のスケジューリング可能性を規定し、スケジューリングされた部品を実行する処理を一般的なステップで説明する。
【図３】特定の部品に対する現在の時間ボックスを割り当てることを可能にするかを決定する方法を記載するフロー図。
【図４】各コネクタに対する前記時間ボックスの変位を示す。
【図５】部品のスケジューリング可能性を決める場合、スケジューラが時間ボックスを使用する方法を説明する。
【図６】スケジューリング可能なスケジューリングを説明するのに用いられるハードリアルタイムシステムを説明する。
【図７ａ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図７ｂ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図７ｃ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図７ｄ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図７ｅ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図７ｆ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図７ｇ】図６のシステムにおける部品をスケジューリングするステップを説明する。
【図１】
2006509285.tif 000003
【図２】
2006509285.tif 000004
【図３】
2006509285.tif 000005
【図４】
2006509285.tif 000006
【図５】
2006509285.tif 000007
【図６】
2006509285.tif 000008
2006509285.tif 000009
2006509285.tif 000010
2006509285.tif 000011
2006509285.tif 000012
2006509285.tif 000013
2006509285.tif 000014
2006509285.tif 000015
【国際調査報告】
2006509285.tif 000016
2006509285.tif 000017
2006509285.tif 000018