(57)【要約】  電子システム、特にネットワーク、データプロセッサまたは通信装置において実行される周期的プロセスをスケジューリングする方法を提供する。電子システムはスケジューリングを実行するコントローラを有する。Ｎ個のプロセスＰｉが既にスケジューリングされ、各プロセスＰｉはそれぞれサービス間隔ＳＩｉを有し、追加プロセスＰＮ＋１がサービス間隔ＳＩＮ＋１でスケジューリングされべきものとされる。追加プロセスＰＮ＋１は、追加プロセスＰＮ＋１の実行時刻とＮ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差が最大になるようにスケジューリングされることを特徴とする。また、これに対応して、電子システムにおいて実行される周期的プロセスをスケジューリングする装置が開示される。
2011529239.tif 000002
【特許請求の範囲】
【請求項１】
電子システム、特にネットワーク、データプロセッサまたは通信装置において実行される周期的プロセスをスケジューリングする方法において、前記電子システムは前記スケジューリングを実行するコントローラを有し、Ｎ個のプロセスＰｉが既にスケジューリングされ、各プロセスＰｉはそれぞれサービス間隔ＳＩｉを有し、追加プロセスＰＮ＋１がサービス間隔ＳＩＮ＋１でスケジューリングされべきものとされ、
前記追加プロセスＰＮ＋１は、前記追加プロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差が最大になるようにスケジューリングされることを特徴とする、周期的プロセスをスケジューリングする方法。
【請求項２】
前記プロセスが、タスク、フローまたは演算であることを特徴とする請求項１に記載の方法。
【請求項３】
複数のプロセスが前記コントローラに同時に到着する場合、所定のポリシーによる順次スケジューリングのために前記プロセスを順序づけるアルゴリズムが設けられることを特徴とする請求項１または２に記載の方法。
【請求項４】
各スケジューリング段階において、前記現在スケジューリングされているプロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差が、前記現在スケジューリングされているプロセスＰＮ＋１に適当な初期実行時刻ｔｉｅを割り当てることによって最大化されることを特徴とする請求項１ないし３のいずれか１項に記載の方法。
【請求項５】
前記スケジューリングされるべきプロセスＰＮ＋１の前記初期実行時刻ｔｉｅが、Ｎフロー問題をＮ個の相異なる２フロー問題に分解することによって決定されることを特徴とする請求項４に記載の方法。
【請求項６】
Ｎフロー問題が、前記現在スケジューリングされるべきプロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差を計算することによって、Ｎ個の相異なる２フロー問題に分解されることを特徴とする請求項５に記載の方法。
【請求項７】
前記現在スケジューリングされるべきプロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の前記最小時間差が、前記現在スケジューリングされるべきプロセスＰＮ＋１に割り当てるべき前記初期実行時刻ｔｉｅの関数として表されることを特徴とする請求項６に記載の方法。
【請求項８】
前記現在スケジューリングされるべきプロセスＰＮ＋１と前記Ｎ個の既にスケジューリングされた各プロセスＰｉとの間のすべての最小時間差の最小値、すなわち絶対最小時間差が、現在スケジューリングされるべきプロセスＰＮ＋１の初期実行時刻ｔｉｅの関数として絶対最小距離を表現する関数の周期Ｔを計算することによって最大化されることを特徴とする請求項１ないし７のいずれか１項に記載の方法。
【請求項９】
前記絶対最小時間差の周期Ｔが、前記現在スケジューリングされるべきプロセスＰＮ＋１のサービス間隔ＳＩＮ＋１と前記Ｎ個の既にスケジューリングされたプロセスＰｉのそれぞれのサービス間隔ＳＩｉとの最大公約数の最小公倍数として計算されることを特徴とする請求項８に記載の方法。
【請求項１０】
前記Ｎ個の既にスケジューリングされたプロセスＰｉのそれぞれについて、前記現在スケジューリングされるべきプロセスＰＮ＋１のサービス間隔ＳＩＮ＋１と前記Ｎ個の既にスケジューリングされたプロセスＰｉのそれぞれのサービス間隔ＳＩｉとの最大公約数の倍数あるいはそれをシフトしたものとして定義され、前記絶対最小距離の前記周期Ｔ内に含まれるすべての「零点」が生成されることを特徴とする請求項９に記載の方法。
【請求項１１】
ソートされた順序で前記「零点」を含む前記「零点」のリストが生成されることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記ソートされた「零点」のリスト内で、２個の連続する要素間の最大ギャップが検索されることを特徴とする請求項１１に記載の方法。
【請求項１３】
前記最大ギャップの中点が、前記初期実行時刻ｔｉｅとして選択されることを特徴とする請求項１２に記載の方法。
【請求項１４】
スケジューリングメカニズムが、周波数間隔、空間間隔、または時間間隔に適用されることを特徴とする請求項１ないし１３のいずれか１項に記載の方法。
【請求項１５】
電子システム、特にネットワーク、データプロセッサまたは通信装置において実行される周期的プロセスをスケジューリングするシステムにおいて、該システムは、Ｎ個のプロセスＰｉをスケジューリングしているコントローラを備え、各プロセスＰｉはそれぞれサービス間隔ＳＩｉを有し、前記コントローラは、追加プロセスＰＮ＋１をサービス間隔ＳＩＮ＋１でスケジューリングするように構成され、
前記コントローラは、さらに、前記追加プロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差が最大になるように、前記追加プロセスＰＮ＋１をスケジューリングするよう構成されることを特徴とする、周期的プロセスをスケジューリングするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子システム、特にネットワーク、データプロセッサまたは通信装置において実行される周期的プロセスをスケジューリングする方法に関する。前記電子システムは前記スケジューリングを実行するコントローラを有する。Ｎ個のプロセスＰｉが既にスケジューリングされ、各プロセスＰｉはそれぞれサービス間隔ＳＩｉを有する。追加プロセスＰＮ＋１がサービス間隔ＳＩＮ＋１でスケジューリングされべきものとされる。
【０００２】
また、本発明は、電子システム、特にネットワーク、データプロセッサまたは通信装置において実行される周期的プロセスをスケジューリングするシステムに関する。該システムは、Ｎ個のプロセスＰｉをスケジューリングしているコントローラを備える。各プロセスＰｉはそれぞれサービス間隔ＳＩｉを有する。コントローラは、追加プロセスＰＮ＋１をサービス間隔ＳＩＮ＋１でスケジューリングするように構成される。
【背景技術】
【０００３】
周期的プロセスのスケジューリングは、例えばコンピュータ科学やネットワーキングにおける共通の問題である。例えば、周期的プロセスは、（音声や動画等の）マルチメディアコーデックによって生成されるトラフィックや、リアルタイムオペレーティングシステムにおいて周期的に実行されるべきジョブを表す。特に、多数のプロセスが、リアルタイムシステムにおけるＣＰＵや無線スケジューリングにおける無線媒体等の共有リソースにアクセスしようとする場合、スケジューリングは、すべてのプロセスが期限を満たすことができることを保証する際に決定的役割を果たす。また、厳格なＱｏＳ保証を有するシステムでは、実行すべき多数のプロセスが正しくスケジューリングされないと、高いピーク負荷がネットワーク／システムによって観測されるため、ネットワーク／システム容量が低下する場合がある。
【０００４】
また、周期的タスクセットを処理する場合に、タスクのスケジューリングを担当するスケジューラエンティティが、各タスクごとに初期スケジューリング時刻を決定できるというのも共通の状況である。この場合、システムにおいてスケジューリングされるべき各タスクごとに最適な開始時刻をどのようにして決定するかが問題となる。この問題に対処するいくつかの解決法が、例えば非特許文献１や非特許文献２といった文献で提案されている。しかし、従来の解決法は、発見法に依拠しているために最適でないか、または、相異なるプロセスのサービス間隔（すなわちそれらの周期）のＬＣＭ（最小公倍数）を調べる（これは指数関数的に増大し得る）必要があるか、もしくは候補初期開始時刻のセットを調べる（このサイズも指数関数的に増大し得る）ため、計算コストが高い。
【０００５】
この問題の説明を明確にするために、プロセス周期のＬＣＭが、相異なるプロセスのサービス間隔に依存して、いかにして指数関数的に増大し得るかを考察するのが有益であろう。１０時間単位の整数倍の周期を有するプロセスのセットを考え、最小値は１０時間単位、最大値は１００、２００または３００時間単位とする。プロセス周期のＬＣＭの値は次のように増大し得る。
・ＬＣＭ（１０，２０，...，１００）＝２５２００
・ＬＣＭ（１０，２０，...，２００）＝２．３８・１０９
・ＬＣＭ（１０，２０，...，３００）＝２．３９・１０１３
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】独国特許出願公開第ＤＥ  １０  ２００５  ０４０  ０２７  Ａ１号明細書
【非特許文献】
【０００７】
【非特許文献１】X. Perez-Costa, et al., “Overlapping Aware Scheduled Automatic Power Save Delivery Algorithm”, European Wireless 2007, Section 3
【非特許文献２】J. Goossens, “Scheduling of offset free systems”, Journal of Real-Time Systems (2001)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
したがって、本発明の目的は、頭書のような方法およびシステムにおいて、実施の容易なメカニズムを使用することにより、アドミッション制御において考慮すべきピーク容量の低減と、遅延およびジッタの低減とを達成するような改良およびさらなる展開を行うことである。また、システムにおいてスケジューリング可能なプロセス数を増大させ、省電力性を向上させる。
【課題を解決するための手段】
【０００９】
本発明によれば、上記の目的は、請求項１の構成を備えた方法によって達成される。この請求項に記載の通り、本方法は、以下のことを特徴とする。すなわち、前記追加プロセスＰＮ＋１は、前記追加プロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差が最大になるようにスケジューリングされる。
【００１０】
また、上記の目的は、独立請求項１５の構成を備えたシステムによって達成される。この請求項に記載の通り、本システムは、以下のことを特徴とする。すなわち、前記コントローラは、さらに、前記追加プロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差が最大になるように、前記追加プロセスＰＮ＋１をスケジューリングするよう構成される。
【００１１】
本発明によって初めて認識されたこととして、多くの応用場面において、複数の周期的プロセスの実行時刻ができるだけ分散している場合に、最大のパフォーマンスが達成可能である。このために、本発明は、追加プロセスの実行時刻と既にスケジューリングされたプロセスの実行時刻との間の最小時間差が最大になるように、追加プロセスをスケジューリングすることを提案する。
【００１２】
相異なるプロセスの実行時刻間の時間差を最大にすることは、さまざまな理由から、多くの環境において有益である。例えば、リアルタイムオペレーティングシステムにおけるＣＰＵや無線スケジューリングにおける無線媒体等の共有リソースに、相異なるプロセスが同時にアクセスしようとする可能性が最小化される。この挙動はシステムの容量を向上させる。というのは、すべてのプロセスが期限を満たす可能性が増大するからである。相異なるプロセスの放出時刻間の時間差を最大にすることも、ネットワークによって観測されるピークレートを低減する。これは、例えば厳格なＱｏＳ保証を提供する場合に有益である。
【００１３】
端末がその周期的プロセスの実行時刻間に省電力スリープモードに入るようなネットワーキングシステムに本発明が適用される場合、本発明は、端末の復帰時に、端末のサービング基地局が別の端末にトラフィックを配信している間、待機しなければならない可能性を最小にする。それにより、端末の電池寿命を大幅に延ばすことができる。
【００１４】
本発明が提案する方法は、以下の２つの主要な理由により、時間および空間的な複雑さに関して、従来の解決法よりもすぐれている。第１に、本発明の解決法の複雑さは、相異なるプロセスのサービス間隔のＬＣＭ（最小公倍数）に依存しない。これにより、スケジューリング時間に関して大幅に高速化される。第２に、本発明が提案する方法は、候補オフセット値のサブセットを求めること（これは、プロセス数とともに指数関数的に増大し得る）が不要であり、最適なオフセット値が直接得られる。
【００１５】
なお、Ｎ個のプロセスが既にスケジューリングされているという仮定は、本発明を何ら限定するものではなく、Ｎが比較的大きい数である場合以外にも、例えばＮ＝０やＮ＝１の場合も含む。特に、スケジューリングされることを要求している複数のプロセスがすべて同時にコントローラに到着する場合、ｔ＜０においてプロセスがシステムで既に利用可能である場合、あるいは、要求がコントローラに相異なる時刻に到着する場合が含まれる。
【００１６】
スケジューリングされるべきプロセスは、タスク、フローまたは演算のいずれでもよい。一般に、スケジューリングされるべきプロセスは、多数の相異なる種類のプロセスを含んでもよい。例えば、以下のものに限定されないが、リアルタイムシステムにおいて周期的に実行されるべきジョブ、マルチメディアコーデックによって生成される周期的トラフィック、周波数スペクトラム拡散方式の櫛形フィルタ出力ＲＦ信号、ネットワークにおける（同期した）動画ダウンロードの開始時刻、分散ＣＰＵにおけるマルチプロセッサのバスアクセス時刻、将来のコンピュータ制御幹線道路における自動車交通流の合流等が挙げられる。
【００１７】
複数のプロセスがコントローラに同時に到着する場合、所定のポリシーによる順次スケジューリングのために前記プロセスを順序づけるアルゴリズムを設けてもよい。例えば、ポリシーは、ＱｏＳ保証を実施するために満たさなければならないプロセスの期限を考慮してもよい。このような場合、厳格な期限を有するプロセスを、より融通のきく期限を有するプロセスの前にスケジューリングすることができる。
【００１８】
各スケジューリング段階において、現在スケジューリングされているプロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差は、現在スケジューリングされているプロセスに適当な初期実行時刻（initial execution time）ｔｉｅを割り当てることによって最大にしてもよい。好ましい実施形態によれば、スケジューリングされるべきプロセスＰＮ＋１の初期実行時刻ｔｉｅは、Ｎフロー問題を、現在スケジューリングされるべきプロセスと既にスケジューリングされたプロセスのそれぞれとを考慮するＮ個の相異なる２フロー問題に分解することによって決定してもよい。このようなアプローチは、解くべき問題の複雑さを大幅に低減するので、スケジューリングプロセスに必要な時間、パワーおよび容量に関して、計算リソースがかなり低減される。具体的実施形態によれば、Ｎフロー問題は、現在スケジューリングされるべきプロセスＰＮ＋１の実行時刻とＮ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差を計算することによって、Ｎ個の相異なる２フロー問題に分解してもよい。
【００１９】
現在スケジューリングされるべきプロセスＰＮ＋１の実行時刻と前記Ｎ個の既にスケジューリングされたプロセスＰｉの実行時刻との間の最小時間差は、前記現在スケジューリングされるべきプロセスＰＮ＋１に割り当てるべき初期実行時刻ｔｉｅの関数として表してもよい。例えば、最小時間差は次のように定義することができる。
ｄｍｉｎ＝Φｉ  ｍｏｄ  ｇｃｄ（ＳＩｉ，ＳＩＮ＋１）
【００２０】
別法として、相異なるプロセスが相異なる継続時間を有する場合、最小時間差は次のように再定義することができる。
ｄｍｉｎ＝Φｉ  ｍｏｄ  ｇｃｄ（ＳＩｉ，ＳＩＮ＋１）−継続時間ｉ
【００２１】
次のステップで、「絶対最小時間差」の概念を導入してもよい。絶対最小時間差は、現在スケジューリングされるべきプロセスＰＮ＋１とＮ個の既にスケジューリングされた各プロセスＰｉとの間のすべての最小時間差の最小値として定義してもよい。なお、すべての関与するプロセスが周期的なので、絶対最小時間差は有限かつ周期的である。有利な態様として、絶対最小時間差は、現在スケジューリングされるべきプロセスＰＮ＋１の初期実行時刻ｔｉｅの関数として絶対最小距離を表現する関数の周期Ｔを計算することによって最大化される。
【００２２】
具体的には、絶対最小時間差の周期Ｔは、現在スケジューリングされるべきプロセスＰＮ＋１のサービス間隔ＳＩＮ＋１とＮ個の既にスケジューリングされたプロセスＰｉのサービス間隔ＳＩｉのそれぞれとの最大公約数（ＧＣＤ）
ｇｃｄ（ＳＩｉ，ＳＩＮ＋１），  ｉ＝１，...，Ｎ
を計算することによって計算してもよい。
【００２３】
こうして得られたすべての値から、ＬＣＭを計算することにより周期
Ｔ＝ｌｃｍ（ｇｃｄ（ＳＩ１，ＳＩＮ＋１），...，ｇｃｄ（ＳＩＮ，ＳＩＮ＋１））
を求めることができる。
【００２４】
複雑さは大幅に低減され、Ｔ＜ＳＩＮ＋１によって制限される。例えば、１０時間単位の整数倍の周期を有するプロセスのセットを考え、最小値はＳＩｍｉｎ＝１０時間単位、最大値はＳＩｍａｘ＝３００時間単位とする。従来の探索演算は、ｌｃｍ（１０，２０，...，３００）＝２．３９・１０１３回の演算を必要とするのに対して、本発明が提案する方法が必要とするのは３００回だけである。
【００２５】
有利な態様として、絶対最小時間差は、初期実行時刻ｔｉｅの関数として表される。そこで、好ましい実施形態によれば、Ｎ個の既にスケジューリングされたプロセスＰｉのそれぞれについて、周期Ｔ内に含まれる上記の関数のすべての零点を生成する。各零点の前後で関数は傾き１で減少および増大するので、絶対最小時間差は関数の零点によって定めることができる。したがって、絶対最小時間差は、傾き１で相異なる高さの三角形のセットとなる。
【００２６】
好ましい実施形態によれば、ソートされた順序で零点を含む零点のリストが生成される。次のステップで、ソートされた零点のリスト内で、２個の連続する要素間の最大ギャップを検索してもよい。有利な態様として、最大ギャップの中点が、初期実行時刻ｔｉｅとして選択される。なお、絶対最小距離は、連続する零点間の傾き１の三角形の列であるので、このような関数の最大値は、間に最大ギャップを有する２個の連続する零点の中点に見出される。
【００２７】
好ましい実施形態によれば、本発明による方法およびシステムは、特に周波数間隔、空間間隔、または時間間隔に一般化可能である。
【００２８】
例えば、特許文献１（その開示全体を参照により本明細書に援用する）には、無線ネットワーク上での移動局との通信を制御する方法において、本発明によるスケジューリングメカニズムがサービス開始時刻を決定するために適用可能であることが記載されている。
【００２９】
本発明を好適な態様で実施するにはいくつもの可能性がある。このためには、一方で請求項１および１５に従属する諸請求項を参照しつつ、他方で図面により例示された本発明の好ましい実施形態についての以下の説明を参照されたい。図面を用いて本発明の好ましい実施形態を説明する際には、本発明の教示による好ましい実施形態一般およびその変形例について説明する。
【図面の簡単な説明】
【００３０】
【図１】電子システムにおいて実行される３つの周期的プロセスのセットを模式的に例示する図である。
【図２】本発明による方法の第１実施形態による２つの周期的プロセスに対するスケジューリング手続きの一態様を模式的に例示する図である。
【図３】図２のスケジューリング手続きの別の態様を模式的に例示する図である。
【図４】本発明による方法の第２実施形態による３つの周期的プロセスに対するスケジューリング手続きを模式的に例示する図である。
【図５】リアルタイムオペレーティングシステムにおけるアドミッション制御テストの容量を例示する図である。
【発明を実施するための形態】
【００３１】
図１は、電子システムにおいて実行される３つの周期的プロセスのセットを模式的に例示している。各プロセスは相異なるサービス間隔（ＳＩ１，ＳＩ２，ＳＩ３）および相異なる開始時刻を有し、開始時刻はランダムに設定されると仮定する。図１からわかるように、２つ、さらには３つすべてのプロセスの実行時刻がほぼ重なり合う時刻が存在する。システムが３つすべてのプロセスを（例えば、利用可能なリソースが限られているために）同時に実行できない場合、少なくとも１つのプロセスは、他のプロセスが完全に実行されるまで待機しなければならないか、あるいは、待ち合わせが不可能な場合には、いずれかのプロセスを破棄しなければならない。
【００３２】
この挙動により、すべてのプロセスが期限を満たすとは限らない場合が生じる。これにより、リアルタイムオペレーティングシステムでは、ＣＰＵによって観測されるピーク負荷が増大するため、システムの容量が低下する。ポーリングどうしの間で局がスリープするような、ポーリング方式のＷＬＡＮシステムを考えると、局の復帰時に、基地局が別の局へのトラフィックを処理している間、局が待機しなければならない場合、消費電力が増大する。図１に例示するプロセスが、バースト型トラフィックを伝送するフローを表している場合、あるストリームには、別のストリームのバースト性により、遅延が生じる。
【００３３】
図２は、本発明による方法の第１実施形態による２つの周期的プロセスに対するスケジューリング手続きの一態様を模式的に例示している。すなわち、図２は、スケジューリングされるべき２つの相異なる周期的フローを表している。第１のフロー、すなわちフロー１を実線の矢印で示し、第２のフロー、すなわちフロー２を点線の矢印で示す。サービス間隔ＳＩ１を有するフロー１は、ある実行時刻で既にスケジューリングされていると仮定する。このフローがスケジューリングされている定期的な時刻を、このフローの放出時刻と称する。ある時点（一般性を失うことなく、ｔ＝０とする）において、新たなフロー２が、ＳＩ２というサービス間隔で、システムにおいてスケジューリングされることを要求する。
【００３４】
フロー２とフロー１の間の左側の距離を、フロー２の放出時刻とフロー１の最終放出時刻との間の時間差として定義し、ｄｌ（ｋ）で表す。同様に、右側の距離を、フロー２の放出時刻とフロー１の次の放出時刻との間の時間差として定義し、ｄｒ（ｋ）で表す。ｄｌ（ｋ）およびｄｒ（ｋ）の両者は図２に示されている。また、図２は、ｎｅｘｔ＿ｒｅｌ＿ｔｉｍｅ１を示している。これは、ｔ＝０から定義したフロー１の次の放出時刻を含む変数である。
【００３５】
フロー２の最適な初期実行時刻（ｔｉｅで表す）は、フロー１および２の放出時刻間の最小距離を最大にする。これを求めるためには、ｄｌ（ｋ）およびｄｒ（ｋ）を次のように表すことができることに注意するとよい。
ｄｌ（ｋ）＝（ｄｌ（０）＋ｋＳＩ２）  ｍｏｄ  ＳＩ１
ｄｒ（ｋ）＝ＳＩ１−ｄｌ（ｋ）
ただし、ｄｌ（０）は、基準とされる初期左側距離である。
【００３６】
次のステップで、ｄｌ（ｋ）およびｄｒ（ｋ）の最小値を、選択したｔｉｅの関数として表す。フロー１および２は周期的なので、チャネル内の状況は周期Ｔ＝ｌｃｍ（ＳＩ１，ＳＩ２）で周期的である。したがって、ｄｌ（ｋ）およびｄｒ（ｋ）もまた周期Ｎ＝Ｔ／ＳＩ２で周期的である。
【００３７】
一次合同式定理を用いることにより、次を証明することができる。
ｄｌｍｉｎ＝ｄｌ（０）  ｍｏｄ  ｇｃｄ（ＳＩ１，ＳＩ２）
ｄｒｍｉｎ＝ｇｃｄ（ＳＩ１，ＳＩ２）−ｄｌｍｉｎ
【００３８】
簡単な変換を用いて、最小の左側および右側距離を、選択したｔｉｅの関数として表すことができる。ｎｅｘｔ＿ｒｅｌ＿ｔｉｍｅ１に等しいｔｉｅをフロー２に与える場合、最小左側距離はゼロとなる。したがって次のようになる。
ｄｌｍｉｎ＝（ｔｉｅ−Φ）  ｍｏｄ  ｇｃｄ（ＳＩ１，ＳＩ２）
ｄｒｍｉｎ＝ｇｃｄ（ＳＩ１，ＳＩ２）−ｄｌｍｉｎ
ただし、Φは、Φ＝ｎｅｘｔ＿ｒｅｌ＿ｔｉｍｅ１  ｍｏｄ  ｇｃｄ（ＳＩ１，ＳＩ２）として定義される初期シフトである。
【００３９】
図３は、図２のスケジューリングプロセスのさらなるステップを模式的に例示している。すなわち、図３は、図２の説明に従い、ｄｌ（ｋ）およびｄｒ（ｋ）の最小値を、選択したｔｉｅの関数としてプロットしている。図３から容易にわかるように、両者の最小距離の最大値はｇｃｄ（ＳＩ１，ＳＩ２）に等しく、これは次の場合に起こる。
ｔｉｅ＝Φ＋ｋ・ｇｃｄ（ＳＩ１，ＳＩ２），  ｋ≧１
ただし、両方の最小距離が同時に最大になることはない。
【００４０】
再び図３を考えると、全体の最小距離、すなわちｍｉｎ｛ｄｌｍｉｎ，ｄｒｍｉｎ｝は、傾き１の連続する三角形のセットとなって現れる。したがって、フロー１およびフロー２の任意の２つの放出時刻間の最小距離を最大にするｔｉｅの値は、次のようになる。
ｔｉｅ＝Φ＋ｋ・（ｇｃｄ（ＳＩ１，ＳＩ２）／２）
したがって、任意の２つの周期的フロー間で達成可能な最小間隔の最大値は、ｇｃｄ（ＳＩ１，ＳＩ２）／２である。
【００４１】
図２および図３に関して上記で説明した２つのフローのみを有する実施形態は、本発明の基本原理を例示することを主に意図している。これに対して、図４は、全部で３つのフローを有する実施形態を模式的に例示しており、これはＮ＞３のＮフローの場合に容易に一般化可能である。
【００４２】
以下では、システムにおいて、Ｎ個の周期的フローがサービス間隔ＳＩｉ（ｉ＝１，...，Ｎ）で既にスケジューリングされ、新たなフローがサービス間隔ＳＩＮ＋１でスケジューリングされることを要求している、という状況を仮定する。この場合も、目標は、新たなフローに対して、その放出時刻と既にスケジューリングされたフローの放出時刻との間の最小距離を最大にする初期実行時刻ｔｉｅを求めることである。
【００４３】
図２および図３に関して説明した２フローの場合からの結果を活用して、Ｎフロー問題を、新たなフローと既にスケジューリングされたフローのそれぞれとを考えるＮ個の相異なる２フロー問題に分解することが可能である。新たなフロー（Ｎ＋１）と、既にスケジューリングされたフロー（ｉ，ｉ＝１，...，Ｎ）のそれぞれとの左側および右側距離を前と同様に定義すると、次を導出することができる。
ｄｌｍｉｎ（Ｎ＋１，ｉ）＝（ｔｉｅ−ΦＮ＋１，ｉ）  ｍｏｄ  ｇｃｄ（ＳＩｉ，ＳＩＮ＋１）
ｄｒｍｉｎ（Ｎ＋１，ｉ）＝ｇｃｄ（ＳＩｉ，ＳＩＮ＋１）−ｄｌｍｉｎ（Ｎ＋１，ｉ）
ただし、ΦＮ＋１，ｉは、ΦＮ＋１，ｉ＝ｎｅｘｔ＿ｒｅｌ＿ｔｉｍｅ（ｉ）  ｍｏｄ  ｇｃｄ（ＳＩＮ＋１，ＳＩｉ）として定義される初期シフトである。
【００４４】
図４は、２つのフローが既にスケジューリングされ、１つの新たなフローがアクセスを要求しているシステムにおける最小の左側および右側距離を表している。図中、ｄｌｍｉｎ（Ｎ＋１，ｉ）およびｄｒｍｉｎ（Ｎ＋１，ｉ）は別個に示さず、代わりに、それぞれのスケジューリングされたフローに対するｍｉｎ｛ｄｌｍｉｎ（Ｎ＋１，ｉ），ｄｒｍｉｎ（Ｎ＋１，ｉ）｝を直接プロットしている。
【００４５】
Ｎ個のフローがある場合、それぞれの可能なｔｉｅに対する最小距離は、すべてのｍｉｎ｛ｄｌｍｉｎ（Ｎ＋１，ｉ），ｄｒｍｉｎ（Ｎ＋１，ｉ）｝の距離のうちの最小値に対応する。この距離を絶対最小距離と称する。そこで、絶対最小距離の最大値を求める高速な方法は、以下の観察に基づいて定めることができる。
【００４６】
・絶対最小距離は、ｔｉｅに関して、周期Ｔ′＝ｌｃｍ（ｇｃｄ（ＳＩｉ，ＳＩＮ＋１），...，ｇｃｄ（ＳＩＮ，ＳＩＮ＋１））で周期的である。
【００４７】
・それぞれの最小距離、すなわちｍｉｎ｛ｄｌｍｉｎ（Ｎ＋１，ｉ），ｄｒｍｉｎ（Ｎ＋１，ｉ）｝は、ｔｉｅ＝ΦＮ＋１，ｉ＋ｋ・ｇｃｄ（ＳＩｉ，ＳＩＮ＋１），ｋ≧１、に零点を含む。すべての零点は、絶対最小距離に属する。
【００４８】
・絶対最小距離は各零点の前後で傾き１で減少および増大するので、絶対最小距離はその零点によって定めることができる。したがって、絶対最小距離は、傾き１で相異なる高さの三角形のセットとなる。
【００４９】
最後に、最適なｔｉｅを求める方法を、以下の観察に基づいて設計することができる。
【００５０】
絶対最小距離は、連続する零点間の傾き１の三角形の列であるので、このような関数の最大値は、間に最大ギャップを有する２個の連続する零点の中点に見出される。絶対最小距離を最大にするｔｉｅを見つける方法は次のように記述することができる。
【００５１】
１．Ｎ個の既にスケジューリングされたフローのすべてに対し、ｇｃｄ（ＳＩＮ＋１，ＳＩＮ）を計算する。
２．絶対最小距離の周期Ｔ′＝ｌｃｍ（ｇｃｄ（ＳＩｉ，ＳＩＮ＋１），...，ｇｃｄ（ＳＩＮ，ＳＩＮ＋１））を計算する。
３．それぞれの既にスケジューリングされたフローに対し、Ｔ′内に含まれるΦＮ＋１，ｉ＋ｋ・ｇｃｄ（ＳＩｉ，ＳＩＮ＋１）におけるすべての零点を生成する。
４．零点のリストをソートする。
５．ソートされた零点のリスト内で、２つの連続する要素間の最大ギャップを見つける。
【００５２】
図５は、図４に関して前述したリアルタイムオペレーティングシステムにおけるアドミッション制御テストの容量を例示している。与えられたタスクのセットに対して、遅延制約が満たされ得るかどうかをアドミッション制御テストが判定する。図５は、各タスクの初期時刻が本発明による方法に従って分散している場合（赤線）、あるいは、各タスクの初期時刻がランダムに割り当てられている場合（青線）に、厳格なＱｏＳ保証を有するシステムにおいて受付可能なタスクセットの百分率を例示している。
【００５３】
図５からわかるように、相異なるフローの放出時刻間の距離を最大にすると、アドミッション制御において考慮すべきピーク容量が低減され、したがって、システムにおいてスケジューリング可能なタスク数が大幅に増大する。
【００５４】
まとめると、従来の解決法と比較して、本発明による方法の主な特徴は次の通りである。
【００５５】
・達成されるオフセット割り当ては、相異なるタスク／フローの放出時刻間の最小距離が最大になるという意味で、最適である。
【００５６】
・本発明が提案する方法は、以下の２つの主要な理由により、時間および空間的な複雑さに関して、従来の解決法よりもすぐれている。
ｉ）本発明の方法の複雑さは、相異なるタスクの周期のＬＣＭに依存しない。これにより、スケジューリング時間に関して大幅に高速化される。
ｉｉ）本発明が提案する方法は、候補オフセット値のサブセットを求めること（これは、スケジューリングされるべきプロセス数とともに指数関数的に増大し得る）が不要であり、最適なオフセット値ｔｉｅが直接得られる。
【００５７】
本発明が提案する方法の実際の利点は、それが適用される個々の環境に依存する。いくつかの例を以下に示す。
【００５８】
・容量。リアルタイムシステムでは、タスクは、その遅延限界が決して破られないことが保証される場合にのみスケジューリング可能である。このようなシステムでは、与えられたタスクのセットに対して、遅延制約が満たされ得るかどうかを判定するアドミッション制御テストが存在する。相異なるフローの放出時刻間の距離を最大にすると、アドミッション制御において考慮すべきピーク容量が低減され、したがって、システムにおいてスケジューリング可能なタスク数が増大する。
【００５９】
・速度。アドミッション制御テストは通常、計算コストが高いので、相異なるタスクの開始時刻を最適にスケジューリングする高速な方法を有することが非常に重要である。同じ種類のもう１つの例として、保証サービスを実施する統合サービスネットワークがある。
【００６０】
・遅延／ジッタ。周期的ＶＢＲ（可変ビットレート）フローに、ある特定の遅延保証を提供しなければならない通信システムでは、これらのフローを相互にあまりに密にスケジューリングすると、あるフローのバーストが他のフローのトラフィックを遅延させる場合がある。ＶＢＲフローのスケジュール時刻間の距離を最大にすると、あるフローが他に及ぼす影響が最小になり、したがってジッタが低減される。このスケジューリングをオンラインで行わなければならない技術においては、高速な方法が不可欠である。
【００６１】
・省電力。ＶＢＲフローを伝送する局が省電力動作をし、スケジューリングされた時刻にだけ復帰してデータを送受信する通信システムでは、フロー間の距離を最大にすると省電力性が向上する。
【００６２】
本発明は、リアルタイムの周期的タスク／フローのスケジューリングが使用されるいかなる分野にも適用可能である。特に（ただし限定されない）、周期的／リアルタイムのマルチメディアパケットストリームに適用可能である。いくつかの例を以下に示す。
【００６３】
・集中化ＱｏＳをサポートし、それにより、リアルタイムマルチメディアコーデックのスケジューリングを扱うネットワーキング技術。例：
１．ＷｉＭＡＸ基地局のＵＧＳ（Unsolicited Grant Services）サービスクラスは、本発明が提案する方法によりスケジューリング可能であり、それにより、同じＷｉＭＡＸフレームでアクセスするフロー数が低減される。
２．８０２．１１ｅのＨＣＣＡモードは、フローの周期的スケジューリングに基づいているので、本発明が提案する方法を使用可能である。
・リアルタイムオペレーティングシステム、例えばＲＴ  Ｌｉｎｕｘ、ＶｘＷｏｒｋｓ、ＲＴ−１１、ｅＣｏｓの開発。
・産業用制御・自動化アプリケーション、例えば、自動車エンジンパラメータの制御、オンボードシステムのポーリング。
・ロボット工学。
・組み込みシステム（プログラム可能サーモスタット、家電製品コントローラ等）。
【００６４】
上記の説明および添付図面の記載に基づいて、当業者は本発明の多くの変形例および他の実施形態に想到し得るであろう。したがって、本発明は、開示した具体的実施形態に限定されるものではなく、変形例および他の実施形態も、添付の特許請求の範囲内に含まれるものと解すべきである。本明細書では特定の用語を用いているが、それらは総称的・説明的意味でのみ用いられており、限定を目的としたものではない。
【図１】
2011529239.tif 000003
【図２】
2011529239.tif 000004
【図３】
2011529239.tif 000005
【図４】
2011529239.tif 000006
【図５】
2011529239.tif 000007
【国際調査報告】
2011529239.tif 000008
2011529239.tif 000009
2011529239.tif 000010