(57)【要約】  本発明は、リアルタイム・オペレーティング・システムにおいて異なる優先度を有する少なくとも２つのタスク間のプリエンプションを管理する方法に関し、カレントタスクの優先度より高い優先度を有するタスクの実行要求の間、前記カレントタスクの実行は、少なくとも前記カレントタスクおよび前記より高い優先度のタスクが、これらに割り当てられている実行デッドラインより前に実行されることを可能にするように計算される時間間隔の後においてのみ中断されることを特徴とする。【選択図】図１
2011501309.tif 000002
【特許請求の範囲】
【請求項１】
リアルタイム・オペレーティング・システムにおいて異なる優先度を有する少なくとも２つのタスク間のプリエンプションを管理する方法であって、
前記方法は、
カレントタスクの優先度より高い優先度を有するタスクによって実行要求が行われると、少なくとも前記カレントタスクおよび前記より高い優先度のタスクが、これらに割り当てられているデッドラインまでの時間の終わりより前に実行されることを可能にするように計算される時間間隔の終わりにおいてのみ、前記カレントタスクの実行が中断されることと、
デッドラインまでの時間の昇順に前記タスクがソートされるように選択される指数ｉを有する複数のタスクのプリエンプションを管理するために、最も短いデッドラインまでの時間を有するタスクへ指数１が与えられ、かつ最も長いデッドラインまでの時間を有するタスクへ指数ｐが与えられるまで、続いて指数が与えられ、前記階級ｉのタスクに関する非プリエンプション時間間隔ＮＰｉが値
ＮＰｉ＝Ｍｉｎ（ＮＰｉ−１，Ｌｉ−１ａｂｓ）
但し、
【数１】
2011501309.tif 000010
を有し、ここで、
Ｐｉは、前記タスクＴｉへ割り当てられるデッドラインまでの時間を指し、かつ、
Ｃｉは、前記タスクＴｉの最悪の場合の実行持続時間を指すことと、
を特徴とする方法。
【請求項２】
前記時間間隔は、各タスクについて、より高い優先度を有する他の全てのタスクが実行される場合があるという可能性を考慮する一定の方法で計算されることを特徴とする、請求項１記載の方法。
【請求項３】
前記時間間隔は予め計算されることを特徴とする、請求項２記載の方法。
【請求項４】
前記時間間隔は、前記カレントタスクについて、より高い優先度を有しかつそのための実行要求が実際に形成されている他の全てのタスクを考慮して動的に決定されることを特徴とする、請求項１記載の方法。
【請求項５】
前記カレントタスクの時間間隔は、前記カレントタスクより高い優先度を有するタスクに対して実行要求が形成される場面毎に、再度更新されることを特徴とする、請求項４記載の方法。
【請求項６】
前記タスクの各々が固定優先度を提示することを特徴とする、請求項１〜５のいずれかに記載の方法。
【請求項７】
前記タスクの各々が動的な優先度を提示することを特徴とする、請求項１から請求項５のいずれか一項に記載の方法。
【請求項８】
前記時間間隔ＮＰｉが、前記カレントタスクＴｉの実行時間Ｔｉよりも短いデッドラインまでの時間を有する全てのタスクを考慮して、固定方式で計算されることと、
前記カレントタスクＴｉが、その固有のデッドラインＰｉまでのよりも短いデッドラインまでの時間を有するタスクによってのみ、プリエンプトされてもよいこととを特徴とする、請求項１記載の方法。
【請求項９】
前記時間間隔ＮＰｉが、実行のためにコールされかつ前記カレントタスクＴｉの絶対デッドラインよりも早期の絶対デッドラインを有する全てのタスクを考慮して、動的に計算されることと、
前記カレントタスクが、その固有の絶対デッドラインｄｉよりも早期の絶対デッドラインを有するタスクによってのみプリエンプトされてもよいこととを特徴とする、請求項１記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リアルタイム・オペレーティング・システム（ＲＴＯＳ）における複数のタスク間のプリエンプションを管理する方法を提供する。
【背景技術】
【０００２】
より高い優先度を有するタスクによってタスクをプリエンプトして、より高い優先度のタスクを決められたデッドラインより前に終了できるようにすることは既知である。これは、固定優先度スケジューリング（ｆｉｘｅｄ  ｐｒｉｏｒｉｔｙ  ｓｃｈｅｄｕｌｉｎｇ：ＦＰＳ）またはアーリエスト・デッドライン・ファースト（ｅａｒｌｉｅｓｔ  ｄｅａｄｌｉｎｅ  ｆｉｒｓｔ：ＥＤＦ）スケジューリング等の動的スケジューリングを使用して、または他にリースト・ラクシティ（ｌｅａｓｔ  ｌａｘｉｔｙ）スケジューリングを使用して行われる。
【０００３】
それにも関わらず、タスクのプリエンプション、より一般的にはこのようなプリエンプションの回数は、ときとしてパフォーマンスに著しい影響を及ぼす可能性がある。各々のプリエンプションが各々のキャッシュメモリの状態（命令およびデータ）の修正に繋がり、これらの修正が、次にタスクの実行回数の増加に繋がり（これは、リアルタイムという制約がもはや保証されないことを意味する）、かつ、プリエンプションの時点とプリエンプションから復帰する時点との各々において、メモリの様々な階層レベル間のデータの移動に起因するエネルギー消費が増大することから、プロセッサは最大限には使用され得ない。
【０００４】
従って、プリエンプションの回数を減らすことが望ましい。
【０００５】
Ｒｅａｌ  Ｓｙｓｔｅｍｓ  ２００４  −  ２００４年度ＥＣＲＴ会報  −  リアルタイムシステムに関する第１６回Ｅｕｒｏｍｉｃｒｏ会議、２００４年６月３０日〜７月２日、１４４〜１５２ページ、において公開された、Ｒａｄｕ  Ｄｏｂｒｉｎ、Ｇｅｒｈａｒｄ  Ｆｏｈｌｅｒ共著の「Ｒｅｄｕｃｉｎｇ  ｔｈｅ  Ｎｕｍｂｅｒ  ｏｆ  Ｐｒｅｅｍｐｔｉｏｎｓ  ｉｎ  Ｓｔａｎｄａｒｄ  Ｆｉｘｅｄ  Ｐｒｉｏｒｉｔｙ  Ｓｃｈｅｄｕｌｉｎｇ」と題する論文は、固定優先度スケジューリング（ＦＰＳ）に基づくプリエンプションアルゴリズムを提案している。本アルゴリズムでは、まず、２つのタスクの周期の最小公倍数に等しい周期を有し、かつ固定優先度プリエンプションアルゴリズムによりスケジュールされる「アーティファクト」タスクのセットを解析し、次に、発生すると予想されるプリエンプションの回数を計算する。そして本アルゴリズムは、タスクが実行されている間、そのタスクのプリエンプションを防止するように、プリエンプトしているタスク又はプリエンプトされたタスクに強要し、なお同時に、これらのタスクが設定されたデッドライン内に実行されることを可能にする。
【０００６】
記述されている技術は、プロセッサの利用率が１００％を大幅に下回るときにのみ、プリエンプションの回数を減らすことを可能にする。
【０００７】
リアルタイム・コンピューティング・システム／アプリケーションに関する第３回国際会議の１９９８年度会報（１９９８年１０月２７日〜２９日、３１〜３６ページ）において公開された、Ｓｕｎｇ−Ｈｅｕｎ  Ｏｈ、Ｓｅｕｎｇ−Ｍｉｎ  Ｙａｎｇ共著の「Ａ  Ｍｏｄｉｆｉｅｄ  Ｌｅａｓｔ−Ｌａｘｉｔｙ−Ｆｉｒｓｔ  Ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  Ｒｅａｌ−Ｔｉｍｅ  Ｔａｓｋｓ」と題する論文は、リースト・ラクシティ・ファースト（ＬＬＦ）スケジューリングのアルゴリズムを提案している。本アルゴリズムは、２つのタスク間の非両立性問題を解決し、かつ２つのタスクがプリエンプションなしに完全に実行されることを可能にする。
【０００８】
ＬＬＴスケジューリングに関する同順位のラクシティの問題を専門に扱うこのアルゴリズムは、タスクセットにおける各タスクについて動作し、かつタスクセット内の各タスクへ、動的に計算されるリリース時間に関する個々の固定優先度を与える。これにより、タスク管理ブロック（ＴＣＢ）の複雑さが大幅に増大し、かつ実行時間が増大する。よって、より大きい処理能力のプロセッサが選択されない限り、タスクを実行しているプロセッサの、最も重要なタスクに対する利用率は低減される結果となる。
【０００９】
Ｃｅｃｉｌｉａ  Ｅｋｅｌｉｎ著の論文「Ｃｌａｉｒｖｏｙａｎｔ  Ｎｏｎ−Ｐｒｅｅｍｐｔｉｏｎ  ＥＤＦ  Ｓｃｈｅｄｕｌｉｎｇ」（リアルタイムシステムに関する第１８回Ｅｕｒｏｍｉｃｒｏ会議  ＥＣＲＴＳ’０６、２３〜３２ページ）は、新しいタスクの将来的な到来を考慮しながら、所定のタスクの実行を遅らせることを提案している。しかしながら、この技術は、プリエンプション規則を持たないタスクにしか適用されない。
【００１０】
Ｙｕｎ  Ｗａｎｇ、Ｍａｎａｓ  Ｓａｋｓｅｎａ共著の論文「Ｓｃｈｅｄｕｌｉｎｇ  Ｆｉｘｅｄ−Ｐｒｉｏｒｉｔｙ  Ｔａｓｋｓ  ｗｉｔｈ  Ｐｒｅｅｍｐｔｉｏｎ  Ｔｈｒｅｓｈｏｌｄ」（リアルタイム・コンピューティング・システム／アプリケーションに関する第６回会議  ＲＣＴＳＡ’９９、３２８〜３３５ページ）は、タスク毎にプリエンプションしきい値の計算を要求するプリエンプションを低減するためのアルゴリズムを提案するものであるが、タスク数ｎの２乗に比例する複雑さが生じる。
【００１１】
低電力電子機器／設計に関する２００４年度国際シンポジウム、ＩＳＰＬＥＤ’０４の会報、２００４年８月９日〜１１日、３９３〜３９８ページ、において公開されたＷｏｏｎｓｅｏｋ  Ｋｉｍ、Ｊｉｈｏｎｇ  Ｋｉｍ、Ｓａｎｇ  Ｌｙｕｌ  Ｍｉｎ共著の「Ｐｒｅｅｍｐｔｉｏｎ−Ａｗａｒｅ  Ｄｙｎａｍｉｃ  Ｖｏｌｔａｇｅ  Ｓｃａｌｉｎｇ  ｉｎ  Ｈａｒｄ  Ｒｅａｌ−Ｔｉｍｅ  Ｓｙｓｔｅｍｓ」と題する論文は、プロセッサの電力消費に与えるプリエンプションの悪影響を解析して、２つのソリューションを提案している。
【００１２】
提案されている第１のソリューションは、より低い優先度のタスクがより高い優先度のタスクの到来前に終了することが可能となるように、クロック速度を加速することである。これは、より高い優先度のタスクが到来する前にクロック速度が引き続き確立し直せるように、プロセッサの利用率が１００％をかなり下回ること、かつ効率を高めるために、プロセッサをオーバーディメンションにする必要があることを意味する。
【００１３】
提案されている第２のソリューションは、その総作業負荷に比較して大幅にオーバーディメンションされたプロセッサを用意し、かつより高い優先度のタスクが到来した時点で、低い優先度のタスクを終了することが可能なままであるように、低いクロック周波数を使用することより成る。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
上記から、現時点で、プロセッサのディメンショニングおよび／または利用可能性に関して付随する欠点を発生させずに、プリエンプションの回数を減らすことに適した技術は知られていないことが分かる。
【００１５】
本発明の基礎を成す発想は、より高い優先度のタスクが出現しても、その間はタスクの実行を継続してもよい非プリエンプション時間間隔を、各タスクについて決定することにある。
【課題を解決するための手段】
【００１６】
従って、本発明は、リアルタイム・オペレーティング・システムにおいて異なる優先度を有する少なくとも２つのタスク間のプリエンプションを管理する方法を提供し、本方法は、カレントタスクの優先度より高い優先度を有するタスクによって実行要求が行われると、少なくともカレントタスクおよびより高い優先度のタスクが、これらに割り当てられているデッドラインまでの時間の終わりより前に実行されることを可能にするように計算される時間間隔の終わりにおいてのみ、カレントタスクの実行が中断されることを特徴とする。
【００１７】
各タスクについて、時間間隔は、より高い優先度を有する他の全てのタスクが実行される必要があるという可能性を考慮して一度だけ計算されてもよく、もしくは代わりに、より高い優先度を有しかつそのための実行要求が実際に形成されている他の全てのタスクのみを考慮して、動的に計算されてもよい。このような状況下では、カレントタスクの時間間隔は、カレントタスクの優先度より高い優先度を有するタスクに対して実行要求が形成される場面毎に、更新されることが可能である。
【００１８】
また本発明は、先に定義した方法に加えて、実行優先度の昇順にタスクがソートされるように選択される指数ｉを有する複数のタスクのプリエンプションを管理するために、最も高い実行優先度を有するタスクへ指数１が与えられ、かつ最も低い実行優先度を有するタスクへ指数ｐが与えられるまで、続いて指数が与えられ、階級ｉのタスクに関する非プリエンプション時間間隔ＮＰｉが値
ＮＰｉ＝Ｍｉｎ（ＮＰｉ−１，Ｌｉ−１ａｂｓ）
但し、
【００１９】
【数１】
2011501309.tif 000003
を有することを特徴とする方法も提供する。
【００２０】
ここで、ＰｉはタスクＴｉへ割り当てられるデッドラインまでの時間を指す。定義から、この時間は、ＮＰｉ値の静的計算を伴うＥＤＦスケジューリングを使用する場合、およびレートモノトニック（ＲＭ）スケジューリングを使用する場合のタスクの周期に等しい。ＮＰｉ値の動的計算を使用するＥＤＦスケジューリングの場合、または事実上動的なモノトニック（ＤＭ）スケジューリングの場合、Ｐｉは、この数式において、かつ以後の全ての数式において、タスクの周期以下であるデッドラインＤｉの値に等しくてもよい。
【００２１】
Ｃｉは、タスクＴｉの最悪の場合の実行持続時間を指す。
【００２２】
本発明の他の特徴および利点は、図面を参照して下記の説明を読めば明らかとなる。
【図面の簡単な説明】
【００２３】
【図１】図１は、本発明のアルゴリズムの一実装例を示す。
【図２】図２は、カレントタスクＴの優先度よりも高い優先度を有するタスクのラクシティの累算を示す。
【図３】図３ａおよび３ｂは、Ｔ１が最も高い優先度を有する３つのタスクを実行するシステムにおける一実装例であり、各々、本発明のアルゴリズムを使用する場合と、従来のＥＤＦアルゴリズムを使用する場合とを示す。
【図４】図４は、従来のＥＤＦアルゴリズムにおいてプリエンプションがどのようにカスケードし得るかを示す。
【図５】図５は、本発明のアルゴリズムがプリエンプションのカスケードの回避またはカスケードの回数の低減をどのようにして可能にするかを示す。
【発明を実施するための形態】
【００２４】
例示として、リアルタイムタスクがアーリエスト・デッドライン・ファースト（ＥＤＦ）スキームを使用してスケジュールされるリアルタイムシステムについて考察する。タスクＴの数はｎであり、Ｔ１、Ｔ２、．．．、Ｔｎで参照される。タスクは互いに独立しているものとする。各タスクＴｉは、各々に課された固有のデッドラインＰｉを有し、かつ最悪の場合の実行時間（ｗｏｒｓｔ  ｃａｓｅ  ｅｘｅｃｕｔｉｏｎ  ｔｉｍｅ：ＷＣＥＴ）について計算される実行時間Ｃｉも有する。各タスクＴｉは、下記のように定義されるラクシティＬｉを呈する。
【００２５】
Ｌｉ  ＝  Ｐｉ  −  Ｃｉ
各タスクは繰り返し再現し、タスクＴｉのｋ番目のインプリメンテーションをＴｉ，ｋと書き表す。
【００２６】
タスクＴｉ，ｋの各インプリメンテーションｋは、ウェイクアップ時間ｒｉ，ｋ＝ｋＰｉと、実行デッドラインｄｉ，ｋ＝（ｋ＋１）Ｐｉとを有する。
【００２７】
ＥＤＦアルゴリズムを用いる場合、実行されるタスクは、最も近いデッドラインｄを有するタスクである。従って、このアルゴリズムは動的な優先度に基づく。以下において説明するアルゴリズムは、プリエンプションが実行される瞬間が、従来のＥＤＦ型アルゴリズムとは異なる。このアルゴリズムは、即時的なプリエンプションが必要であるかどうか、またはそれを遅らせることが可能であるかどうか、もし可能であればどのくらい遅らせることができるか、を知ることを可能にする。
【００２８】
慣例により、タスクは、全てのｉについてＰｉ＜Ｐｉ＋１であるように、その周期Ｐに関して昇順にソートされる。但し、Ｐ１は最も短いデッドラインＰ１を有するタスクである。
【００２９】
カレントタスクＴｉが、瞬間ｔにおいてカレントタスクの優先度より高い優先度を有する１つまたは複数のタスクの存在下でも困難なしに継続することができる持続時間は、ＮＰｉで書き表される。
【００３０】
この目的に沿って、３つの条件を明記することができる。
【００３１】
条件１：タスクＴｉのラクシティＬｉは、そのウェイクアップ時間とそのデッドラインＰｉとの間に画定される時間間隔全体にわたってシフトされてもよい。
【００３２】
プロセッサが、デッドラインＰｉまでの時間内でタスクＴｉにプロセッサ時間Ｃｉを割り当てている限り、このタスクＴｉは絶対にデッドラインを超えることはない。
【００３３】
条件２：タスクＴｉは、より高い優先度を有することで次のデッドラインＰｉまでのより短い時間を有するタスクによってのみプリエンプトされてもよい（ＥＤＦまたはＲＭアルゴリズムを使用する場合）。
【００３４】
より高い優先度のタスクが実行されることを必要としているにもかかわらず、より低い優先度のタスクに実行を継続させることは、優先度の逆転を構成し、これが、より高い優先度のタスクについて設定されたデッドラインが果たされない結果となり得る。
【００３５】
従って、より高い優先度のタスクのみが、より低い優先度のタスクをプリエンプトすることができる。
【００３６】
ＲＭアルゴリズムはプリエンプティブであり、かつ固定優先度に基づく。タスクは周期的であって周期Ｐｉを有するが、そのデッドラインは必ずしも周期の終わりに存在しない。タスクは増大する周期によって分類され、優先度は周期の逆関数として割り当てられる。
【００３７】
ＥＤＦアルゴリズムでは、優先度の基準は絶対デッドラインｄである。
【００３８】
タスクＴｉが、瞬間ｎにおいて、瞬間ｋのために準備が整っているタスクＴｊによってプリエンプトされれば、これは、
ｒｉ，ｎ  ＜  ｒｊ，ｋ
であることを意味する。
【００３９】
タスクＴｉは、瞬間ｎにおいてタスクＴｊによってプリエンプトされることから、これは、ＴｊのデッドラインがＴｉのデッドラインよりも近いことを意味し、よって、
ｄｊ，ｋ  ＜  ｄｉ，ｎ
となる。
【００４０】
その結果、Ｐｊ＜Ｐｉとなる。
【００４１】
従って、タスクＴｉは、デッドラインまでのより短い持続時間Ｐを有するタスクによってのみプリエンプトされることが可能である。
【００４２】
ＲＭアルゴリズムでは、出現頻度の低いタスクは、出現頻度の高いタスクによって常にプリエンプトされる。ＥＤＦアルゴリズムでは、出現頻度の高いタスクが出現頻度の低いタスクをプリエンプトする場合もあれば、しない場合もある。
【００４３】
ＥＤＦアルゴリズムでは、条件２は必要条件であり、ＲＭアルゴリズムでは、これは必要十分な条件である。必然的結果として、タスクＴｉに有利に優先度が逆転している場合には、タスクＴｉのデッドラインよりも短いデッドラインを有するタスクのみが、それ自身のデッドラインを果たせなくなる場合がある。
【００４４】
条件３：最も短いデッドラインへ優先度を与えるＥＤＦ型アルゴリズムについては、タスクＴｉは、静的な方法または動的な方法で計算され得る時間長さＮＰにわたって、逆転した優先順位で、かつ他の何れのタスクもそのデッドラインを逸することなく実行を継続することができる。
【００４５】
言い換えれば、各タスクＴｉは２つの主要パラメータを提示する。即ち、最悪の場合の条件下におけるその実行時間Ｃｉと、そのデッドラインまでの時間、つまり設定されたデッドライン内でタスクを終了するために利用可能な残り時間を決定する、その周期Ｐｉとを提示する。
【００４６】
タスクのデッドラインは、レートモノトニック（ＲＭ）スケジューリングを用いる場合と、静的に計算されたタスクのＮＰ値を用いて実行されるＥＤＦスケジューリングを用いる場合とにのみ、その周期として考慮される。デッドラインモノトニック（ＤＭ）として知られる、ＮＰｉ値を動的に計算するＥＤＦスケジューリングの場合、Ｐｉはタスクの周期以下であるデッドラインＤｉに等しくてもよい。
【００４７】
最初の２つのパラメータから生成される第３のパラメータは、ラクシティＬｉである。
【００４８】
より高い優先度レベルのタスクが十分なラクシティを提示する場合には、そのタスクの実行は、全てのタスクがこれらのデッドラインを逸することなく実行されるように適合する持続時間にわたって、プリエンプションを遅らせることにより、シフトされることが可能である。
【００４９】
図１には、論理アルゴリズムが示されている。タスクＴｊが到来した時点で、アクティブなタスクが存在しなければ、手順は従来的なものになる（例えば、ＥＤＦアルゴリズム）。タスクＴｉが既にアクティブである場合、Ｐｉ＜ＰｊであればＥＤＦ手順は継続され、そうでなければ、Ｔｉの残りの実行時間と、Ｔｉの非プリエンプション持続時間の値ＮＰｉとの何れか少ない方に等しい持続時間にわたって、一時的な待ち行列にタスクＴｊが挿入される。
【００５０】
この時間が経過すると、タスクＴｊは、当然ながらタスクＴｉが既にその実行を終了していない限り、タスクＴｉをプリエンプトし、終了している場合は、タスクＴｊはタスクＴｉが終了すると直ぐにその実行を開始する。
【００５１】
非プリエンプション持続時間の値ＮＰｉは、静的に決定されても、動的に決定されてもよい。
【００５２】
以下、静的な決定について説明する。
【００５３】
タスクＴｉのラクシティＬｉは、より低い優先度のタスクＴｉ＋１が、Ｔｉがそのデッドラインを逸することなく、優先度の逆転を生じさせ得る持続時間ＮＰｉ＋１を決定する。
【００５４】
これにより、
ＮＰ２  ＝  Ｌ１
が与えられる。
【００５５】
デッドラインへの時間長さが最も短いタスクＴ１は、他のどのタスクによってもプリエンプトされ得ず、タスクＴ２は、タスクＴ１によってのみプリエンプトされることが可能である。これはタスクＴｐまで同様に成り立ち、タスクＴｐは、より高い優先度を有する全てのタスクＴｐ−１、Ｔｐ−２、．．．、Ｔ１によってプリエンプトされることが可能である。
【００５６】
タスクＴ３のＮＰ３を計算するために仮想タスクが定義される。この仮想タスクは、Ｔ３よりも高い優先度を有するタスクにより誘発されるイベント時間および実行時間をモデリングするという発想によって、計算目的でのみ使用される。この仮想タスクは、ラクシティＬ２ａｂｓと実行時間Ｃ２ａｂｓとを有し、実行時間Ｃ２ａｂｓは、最悪の場合において定義され、Ｃ２と仮想タスクの周期に等しい周期でのタスクＴ１の実行時間に比例する実行時間との和に等しく、即ち、
【００５７】
【数２】
2011501309.tif 000004
である。
【００５８】
これにより、
ＮＰ３  ＝  Ｍｉｎ（ＮＰ２，Ｌ２ａｂｓ）
が与えられる。
【００５９】
言い替えれば、括弧内の２つの値のうちの小さい方が選択される。
【００６０】
同様に、
ＮＰ４  ＝  Ｍｉｎ（ＮＰ３，Ｌ３ａｂｓ）
である。
【００６１】
タスクＴ３は、タスクＴ４をプリエンプト可能なタスクＴ１、Ｔ２およびＴ３の中で、最も長いデッドラインまでの時間長さを有する。
【００６２】
概して、タスクＴｉは、その固有の持続時間Ｐｉよりも短いデッドラインまでの時間長さを有するタスクＴ１、Ｔ２、．．．、Ｔｉ−１によってプリエンプトされてもよい。タスクＴｉをプリエンプト可能な全てのタスクを考慮すれば、非プリエンプション持続時間ＮＰｉに一致するラクシティを有する仮想タスクＴｉ−１ａｂｓを定義することが可能である。従って、Ｔ１からＴｊへと全ての非プリエンプション持続時間ＮＰｉを計算することが可能である（ｉは１からｊまでの範囲の変数）。
【００６３】
仮想タスクの最悪の場合の実行時間を計算するために、タスクＴｉに関して、タスクＴｉの実行中に、より高い優先度レベルを有する全てのタスクが同時にコールされる状況を選択する。
【００６４】
仮想タスクＴｉ−１ａｂｓは、タスクＴｉ−１のデッドラインまでの時間Ｐｉ−１までの時間に等しい周期を提示し、かつＣｉ−１ａｂｓで書き表される最悪の場合におけるその実行時間は、タスクＴｉの持続時間Ｃｉよりも短いデッドラインまでの時間を有する全てのタスクの、最悪の場合の実行時間の加重和である。
【００６５】
これにより、
【００６６】
【数３】
2011501309.tif 000005
Ｌｉ−１ａｂｓ＝  Ｐｉ−１ａｂｓ  −  Ｃｉ−１ａｂｓ
が与えられる。
【００６７】
タスクＴｉ−１ａｂｓのラクシティＬｉ−１ａｂｓは、タスクＴｉよりも高い優先度を有する全てのタスクのラクシティを累算する。
【００６８】
図２は、仮想タスクＴｉ−１ａｂｓが、タスクＴｉよりも高い優先度を有する全てのタスクの累算されたラクシティＬｉ−１ａｂｓを順番に並べ、一方で、仮想タスクＴｉ−１ａｂｓの持続時間Ｐｉ−１ａｂｓは、Ｔｉよりも高い優先度を有するタスクの各々の値よりも大きい値を有し、かつＣｉ−１ａｂｓは、タスクの最悪の場合の実行時間の加重和であることを示す。
【００６９】
累算されたこのラクシティは、所定のタスクが、その実行がより高い優先度のタスクによってプリエンプトされることなくその実行を続けるための、より多くの余地を与える。
【００７０】
次に、タスクＴｉの非プリエンプション時間ＮＰｉは、次のように定義され、
ＮＰｉ＝Ｍｉｎ（ＮＰｉ−１，Ｌｉ−１ａｂｓ）
【００７１】
【数４】
2011501309.tif 000006
これら方法を所与として計算される。ＮＰｉの上記数式は、より低い階級を有するタスクの最小のラクシティの値を考慮している。従って、これらのタスクの何れもそのデッドラインを逸することはない。
【００７２】
上述のアルゴリズムは、カレントタスクのプリエンプションを、カレントタスクＴｉのＮＰｉの値に等しい持続時間にわたって遅らせる。
【００７３】
ＮＰがとり得る値は、予め計算されて表に載せられ、こうして各タスクの値ＮＰが与えられてもよいことに気付くべきである。
【００７４】
このデッドラインは、カウンタによってカウントダウンされ、カウンタがゼロに達すると、当然ながらカレントタスクが既に終了していない限り、カレントタスクがプリエンプトされ、終了している場合は、カレントタスクがプリエンプトされることなく実行を終えると直ぐに、新しいタスクが実行される。
【００７５】
カレントタスクＴｉの時間間隔ＮＰｉの間に他のタスクが出現する場合には、これらタスクは、時間間隔ＮＰｉが終了するまで遅延される。これらタスクのデッドラインは、ＮＰｉの終了後に初めて考慮される。
【００７６】
ＮＰの計算は、カレントタスクよりも高い優先度を有する全てのタスクが同時に出現する状況を考慮する。これは、最悪の場合において、タスクがひき続いて出現するかもしれないにも関わらず、これら全てのタスクがこれらのデッドライン内に完了することを意味する。
【実施例】
【００７７】
ここでは、３つのタスクＴ１、Ｔ２およびＴ３を有する単純なモデルについて考察する。Ｔ１が最も高い優先度を有し、これら３つのタスクはそれらの周期の関数として、下記のように優先度順にソートされる。
【００７８】
Ｔ１      Ｃ１＝４      Ｐ１＝１０
Ｔ２      Ｃ２＝６      Ｐ２＝２１
Ｔ３      Ｃ３＝９      Ｐ３＝３３
Ｔ１は、プリエンプトされ得ない。
【００７９】
Ｔ２は、Ｔ１によってのみプリエンプトされる可能性がある。
【００８０】
Ｔ３は、Ｔ１またはＴ２によってのみプリエンプトされる可能性がある。
【００８１】
【数５】
2011501309.tif 000007
より即ち、
【００８２】
【数６】
2011501309.tif 000008
ＮＰ２  ＝  Ｐ１  −  Ｃ１  ＝  ６
である。
【００８３】
図３ａおよび図３ｂはタイミング図であり、瞬間ｔ＝１および２１に到来するタスクＴ２（発生２回）、瞬間３、１３、２３および３３に到来するタスクＴ１（発生４回）、並びに瞬間０および３３に到来するタスクＴ３に関して、まず（図３ａ）、本発明によるアルゴリズムのオペレーションを示し、次に（図３ｂ）、従来のＥＤＦアルゴリズムのオペレーションを示す。
【００８４】
図３ａでは、もはやプリエンプションは存在しないが、図３ｂでは、２つのプリエンプションが存在する。
【００８５】
タスクＴ２は、ＮＰ２＝６であって、Ｔ２が終了するために必要な時間よりも長いことから、瞬間３において到来するタスクＴ１によって全くプリエンプトされない。タスクＴ１は、その実行を瞬間ｔ＝６において開始し、ｔ＝１０におけるそのデッドラインより前に終了する。タスクＴ３は、その実行を瞬間ｔ＝１０において開始し、瞬間ｔ＝１３においてタスクＴ１の第２の発生が出現するまで実行する。しかしながら、ＮＰ３＝６．６であることから、Ｔ３のプリエンプションは遅延され、これにより、タスクＴ３はプリエンプトされることなく終了することが可能となる。タスクＴ１の第２の発生は、瞬間ｔ＝１９とｔ＝２３との間で実行され、タスクＴ１の第３の発生は、瞬間ｔ＝２３とｔ＝２７との間で実行される。最も高い優先度を有するタスクＴ１がプリエンプトされ得ないことから、瞬間ｔ＝２０におけるＴ２の第２の発生は、タスクＴ１が終了するｔ＝２７まで遅延され、タスクＴ２の第２の発生は、ｔ＝２７からｔ＝３３まで実行される。
【００８６】
説明している静的アルゴリズムは、概して全てのプリエンプションの排除を可能とするのではなく、プリエンプションの回数を減らす働きをするだけである。
【００８７】
パフォーマンスの向上およびプリエンプションの回数のさらなる低減は、プリエンプションの持続時間を動的に調整することによって可能である。
【００８８】
上述の計算は、結局は、低い優先度を有するタスクは全て同時にコールされるという、実際に生じる事実を考慮するということに帰着する。
【００８９】
動的計算は、実際に実行のためにコールされるタスクのみを考慮しようと努める。
【００９０】
タスクＴｋが、コールされ、かつカレントタスクＴｉのデッドラインより前のデッドラインを提示すれば、ＮＰｉが計算されて、タスクＴｉは、持続時間ＮＰｉが経過するまでの間、またはタスクＴｉが終了するまでの間継続し、ＮＰｉが減分する。従って、新しくコールされるタスクが、問題のタスクのデッドラインよりも早いデッドラインを有する度に、ＮＰｉを再計算して、新しい値によるＮＰｉの減分を再開する必要があり、よって、この新しい始点から、上述の同じ数式を使用してＮＰｉの計算が実行される。但し、実行準備が整っており、且つタスクＴｉのデッドラインよりも早期の絶対デッドラインを有するタスクのみが考慮される。
【００９１】
この動的計算では、パラメータＮＰｉの計算に選択されるタスクは、それらのデッドラインＰｊまでの時間の値の関数としてではなしに、それらの絶対デッドラインｄｉの値の関数として順序づけされる。
【００９２】
Ｔｉが実行されている間に最初にコールされるべきタスクがタスクＴｋであれば（ｄｋ＜ｄｉ）、ＮＰｉはタスクＴｋのラクシティＬｋに等しくなるように選択される。新しいタスクＴ１の準備が整っていれば（ｄ１＜ｄｉ）、上述の数式を使用し、且つタスクＴｋおよびＴ１のパラメータを考慮して、ＮＰｉが再計算される。
【００９３】
再計算された値は、先の値以下の値でしかあり得ない。静的計算が、準備が整っているか否かに関わらずより高い優先度のタスクを全て考慮するのに対して、動的計算は、実際に実行準備が整っているタスクのみを考慮することから、静的な方法で計算されるＮＰｉの値が、必ず、動的な方法で計算されるＮＰｉの値以下の値になることに気付くべきである。
【００９４】
動的計算の複雑さはタスクの総数ｎに比例し、アルゴリズムは最悪の場合でｎ回の反復を必要とするが、反復の数は概してｎより遙かに少ない。ＮＰ値のこの計算は、実行のために新しくコールされているタスクを、待ち行列に入れるために使用するアルゴリズムに統合されることが可能であり、このアルゴリズムの複雑さは、概してｎに比例する。
【００９５】
ＲＭまたはＥＤＦ型のアルゴリズムに伴う特にやっかいな現象は、カスケード式に発生するプリエンプションの存在である。即ち、カレントタスクが、より高い優先度のタスクによってプリエンプトされ、カレントタスクをプリエンプトしたタスク自体が、さらに高い優先度を有するタスクによってプリエンプトされ、以下同様に続く。
【００９６】
本発明によるアルゴリズムは、静的または動的に関わらず、実行準備が整っている全てのタスク（静的アルゴリズムでは、準備が整っていると思われる全てのタスク、動的アルゴリズムでは、真に準備が整っている全てのタスク）を常に考慮することから、この現象を回避する、または減衰させることができる。
【００９７】
これは、先に記載した通りに優先度の高いものから順番付けされた６つのタスクＴ１からＴ６（Ｔ１が最も高い優先度のタスク）の場合のプリエンプションのカスケードに関して、図４および図５に示されている。
【００９８】
図４では、Ｔ６はＴ５によってプリエンプトされ、Ｔ５はＴ４に、Ｔ４はＴ３に、Ｔ３はＴ２に、かつ最後にＴ２はＴ１によってプリエンプトされて、５つのプリエンプションによるカスケードが生じているが、これは、本発明によるアルゴリズムによって回避される（図５）。
【００９９】
本発明によるアルゴリズムの導入は、例示としてＥＤＦアルゴリズムに関して下記に示すように、従来のアルゴリズムの実行可能性条件を変更するものではないことに気付くべきである。但し、Ｕはプロセッサの最大利用率である。
【０１００】
【数７】
2011501309.tif 000009
【図１】
2011501309.tif 000011
【図２】
2011501309.tif 000012
【図３】
2011501309.tif 000013
【図４】
2011501309.tif 000014
【図５】
2011501309.tif 000015
【手続補正書】
【提出日】平成22年4月26日(2010.4.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
リアルタイム・オペレーティング・システムにおいて異なる優先度を有する少なくとも２つのタスク間のプリエンプションを管理する方法であって、
前記方法は、
カレントタスクの優先度より高い優先度を有するタスクによって実行要求が行われると、少なくとも前記カレントタスクおよび前記より高い優先度のタスクが、これらに割り当てられているデッドラインまでの時間の終わりより前に実行されることを可能にするように計算される時間間隔の終わりにおいてのみ、前記カレントタスクの実行が中断されることと、
デッドラインまでの時間の昇順に前記タスクがソートされるように選択される指数ｉを有する複数のタスクのプリエンプションを管理するために、最も短いデッドラインまでの時間を有するタスクへ指数１が与えられ、かつ最も長いデッドラインまでの時間を有するタスクへ指数ｐが与えられるまで、続いて指数が与えられ、前記階級ｉのタスクに関する非プリエンプション時間間隔ＮＰｉが値
ｉ＞２について  ＮＰｉ＝Ｍｉｎ（ＮＰｉ−１，Ｌｉ−１ａｂｓ）
但し、
ＮＰ２  ＝  Ｐ１  −  Ｃ１
および
【数１】
2011501309.tif 000016
を有し、ここで、
Ｐｉは、前記タスクＴｉへ割り当てられるデッドラインまでの時間を指し、かつ、
Ｃｉは、前記タスクＴｉの最悪の場合の実行持続時間を指すことと、
を特徴とする方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
また本発明は、先に定義した方法に加えて、実行優先度の昇順にタスクがソートされるように選択される指数ｉを有する複数のタスクのプリエンプションを管理するために、最も高い実行優先度を有するタスクへ指数１が与えられ、かつ最も低い実行優先度を有するタスクへ指数ｐが与えられるまで、続いて指数が与えられ、階級ｉのタスクに関する非プリエンプション時間間隔ＮＰｉが値
ｉ＞２について  ＮＰｉ＝Ｍｉｎ（ＮＰｉ−１，Ｌｉ−１ａｂｓ）
但し、
ＮＰ２  ＝  Ｐ１  −  Ｃ１
および
【国際調査報告】
2011501309.tif 000017
2011501309.tif 000018