(57)【要約】  リアルタイム・オペレーティング・システム（30）において複数のタスクを制御する方法（１０）は、重要度レベルを2つ以上のタスク（31、32）に割り当てる。第１のタスク（31）は、より重要なタスクとして割り当てられる。第２のタスク（32）は、より重要でないタスクとして割り当てられる。保証バジェット・マージンは次いで、より重要な保証バジェットとともに、より重要なタスクに割り当てられる。より重要でない保証バジェットも、より重要でないタスクに割り当てられる。実行中の特定時点で、より高いレベル又はより重要なタスク(31)は次いで、保証バジェット・マージンを、より重要なタスクがもう必要としないことを判定し得る。その場合、条件付保証バジェット・マージンが次いで、より重要でないタスク(32)に、より重要な保証バジェットが消耗した場合にのみ、割り当てられる。より重要な保証バジェットが消耗していない場合、条件付保証バジェット・マージンは、保証バジェット・マージンを必要としない旨をより重要なタスクが判定していても、より重要でないタスクに割り当てられない。条件付保証バジェット・マージンの準備は、より重要な保証バジェットの消耗によって、より重要な保証バジェットの後続期間においてイネーブルされる。中間優先度で、より低レベルのタスクに予備容量を供給し、中間優先度でLITに条件付保証バジェットを供給する、本発明の他の局面（阻止時間の補正など）を備える。【特許請求の範囲】
【請求項１】
システムにおける複数のタスクを制御する方法であって、
第１のタスクよりも低い重要度を有する第２のタスクに条件付保証バジェット・マージンを、前記第１のタスクが保証バジェット・マージンを解放すると準備する工程と、
現行のより重要なバジェット期間及び後続するより重要なバジェット期間におけるより重要な保証バジェットの消耗によって前記条件付保証バジェット・マージンの供給をイネーブルする工程とを備えることを特徴とする方法。
【請求項２】
請求項1記載の方法であって、
前記第１のタスクを、より重要なタスクに割り当てる工程を更に備えることを特徴とする方法。
【請求項３】
請求項1記載の方法であって、
前記第２のタスクを、より重要でないタスクに割り当てる工程を更に備えることを特徴とする方法。
【請求項４】
請求項2記載の方法であって、
より重要な保証バジェットとともに保証バジェット・マージンを前記より重要なタスクに割り当て、該割り当てを前記より重要なタスクに明示的に通知する工程を更に備えることを特徴とする方法。
【請求項５】
請求項3記載の方法であって、
より重要でない保証バジェットを前記より重要でないタスクに割り当て、該割り当てを前記より重要でないタスクに明示的に通知する工程を更に備えることを特徴とする方法。
【請求項６】
請求項5記載の方法であって、
前記条件付保証バジェット・マージンを条件的に前記より重要でないタスクに割り当て、該割り当てを前記より重要でないタスクに明示的に通知する工程を更に備えることを特徴とする方法。
【請求項７】
請求項4記載の方法であって、
前記より重要なタスクが、該タスクの保証バジェット・マージンをもう必要としないことを判定する工程を更に備えることを特徴とする方法。
【請求項８】
請求項7記載の方法であって、
前記より重要なタスクが、該タスクの保証バジェット・マージンをもう必要としない旨のメッセージを送る工程を更に備えることを特徴とする方法。
【請求項９】
請求項8記載の方法であって、
前記より重要な保証バジェットが消耗した場合にのみ、前記条件付保証バジェット・マージンを前記より重要でないタスクに割り当てる工程を更に備えることを特徴とする方法。
【請求項１０】
請求項9記載の方法であって、
前記より重要な保証バジェットが消耗したか否かを判定する工程を更に備えることを特徴とする方法。
【請求項１１】
請求項9記載の方法であって、
より重要なタスクが、該タスクの保証バジェット・マージンを必要とすることを判定する工程を更に備えることを特徴とする方法。
【請求項１２】
請求項11記載の方法であって、
前記より重要なタスクが、該タスクの保証バジェット・マージンを必要とする旨のメッセージを送る工程を更に備えることを特徴とする方法。
【請求項１３】
請求項11記載の方法であって、
前記条件付保証バジェット・マージンを前記より重要でないタスクから取り除き、前記保証バジェット・マージンを前記より重要なタスクに供給する工程を更に備えることを特徴とする方法。
【請求項１４】
請求項13記載の方法であって、
前記条件付保証バジェット・マージンを取り除くことを前記より重要でないタスクを明示的に通知する工程を更に備えることを特徴とする方法。
【請求項１５】
請求項1記載の方法であって、
前記より重要な保証バジェットが消耗していない場合にのみ、前記保証バジェット・マージンを前記第１のタスクにすぐに割り当てる工程を更に備えることを特徴とする方法。
【請求項１６】
請求項1記載の方法であって、
前記条件付保証バジェット・マージンが前記第２のタスクに割り当てられていない場合にのみ、前記保証バジェット・マージンを前記第１のタスクにすぐに供給する工程を更に備えることを特徴とする方法。
【請求項１７】
装置であって、
第１の重要度レベルを有する第１のタスクと、
前記第１の重要度レベルよりも低い第２の重要度レベルを有する第２のタスクと、
リソース・バジェットを割り当てるための割り当て機構であって、該割り当て機構が、より重要な保証バジェット、及び保証バジェット・マージンについて前記第１のタスクに明示的に通知し、より重要でない保証バジェット、及び条件付保証バジェット・マージンについて前記第２のタスクに明示的に通知する割り当て機構と、
バジェット化された量を前記第１のタスク及び前記第２のタスクに供給するスケジューラであって、考えられる第１の場合に前記第１のタスクに、前記より重要な保証バジェット及び前記保証バジェット・マージンを供給し、考えられる第１の場合に前記第２のタスクに前記より重要でない保証バジェットを供給し、前記第１のタスクは、前記より重要な保証バジェットによってのみ前記第１のタスクが適切に実行することが可能であることを実行中に特定の時点で判定し、前記第１のタスクは、前記第１のタスクが該タスクの保証バジェット・マージンを必要としないことを前記スケジューラに明示的に通知するスケジューラとを備え、
前記スケジューラは、考えられる第１の場合の前記第１のタスクへの前記保証バジェット・マージンの供給を停止しており、
前記第１のタスクが、より重要な保証バジェットを消耗していない場合、前記スケジューラは前記条件付保証バジェット・マージンを前記第２のタスクに供給せず、前記第１のタスクが前記より重要な保証バジェットを消耗している場合、前記スケジューラは前記条件付保証バジェット・マージンを前記第２のタスクに供給し、
前記条件付保証バジェット・マージンを前記第２のタスクに供給すると、前記スケジューラは、前記条件付保証バジェット・マージンの前記供給を前記第２のタスクに通知し、
前記第１のタスクは、前記保証バジェット・マージンも前記第１のタスクが必要とすることを実行中に特定の時点で判定し、前記第１のタスクは、該第１のタスクが、該第１のタスクの保証バジェット・マージンを必要とすることを前記スケジューラに明示的に通知し、
前記保証バジェット・マージンが消耗していない場合に前記保証バジェット・マージンが先行して解放されているので、前記条件付バジェット・マージンが前記第２のタスクに供給されなかった場合に、前記スケジューラは前記第１のタスクに前記保証バジェット・マージンをすぐに転送し、
前記保証バジェット・マージンが先行して解放された際に、より重要な保証バジェット・マージンは消耗しているので、前記条件付保証バジェット・マージンは前記第２のタスクに供給された場合に撤回されることになることを前記スケジューラは前記第２のタスクに通知し、その場合、前記スケジューラは、考えられる第１の場合での前記第２のタスクへの前記条件付保証バジェットの供給を停止し、前記スケジューラは、考えられる第１の場合での前記第１のタスクへの前記保証バジェット・マージンの供給を開始することを特徴とする装置。
【請求項１８】
請求項１７記載の装置であって、前記より重要な保証バジェットの消耗によって、後続する1つ又は複数のより重要な保証バジェット期間における前記条件付保証バジェット・マージンの供給が可能になることを特徴とする装置。
【請求項１９】
装置であって、
第１の重要度レベルを有する第１のタスクと、
前記第１の重要度レベルよりも低い第２の重要度レベルを有する第２のタスクと、
リソース・バジェットを割り当てるための割り当て機構であって、前記第１のタスクが、より重要な保証バジェット、及び保証バジェット・マージンについて明示的に通知され、より重要でない保証バジェット、及び条件付保証バジェット・マージンについて前記第２のタスクが明示的に通知される割り当て機構と、
前記条件付保証バジェット・マージンの利用可能性を監視するための条件付バジェット監視器であって、前記より重要なタスクが前記保証バジェット・マージンをもう必要としない旨のメッセージを受け、前記保証バジェット・マージンを前記より重要なタスクが現時で必要とする旨のメッセージを受け、前記保証バジェット・マージン、前記条件付保証バジェット・マージン、前記より重要な保証バジェット・マージン及び前記より重要でない保証バジェットのバジェット割り当てを前記割り当て機構から受け、前記バジェット割り当てに関する予約コマンドを送出するものである条件付バジェット監視器と、
バジェット化された量を前記第１のタスク及び前記第２のタスクに前記予約コマンドに基づいて供給するスケジューラであって、考えられる第１の場合に前記第１のタスクに、前記より重要な保証バジェット及び前記保証バジェット・マージンを供給し、考えられる第１の場合に前記第２のタスクに前記より重要でない保証バジェットを供給し、前記第１のタスクは、前記より重要な保証バジェットによってのみ前記第１のタスクが適切に実行することが可能であることを実行中に特定の時点で判定し、前記条件付バジェット監視器は、前記第１のタスクの前記より重要な保証バジェットのみを有し、前記第２のタスクの前記より重要でない保証バジェット及び前記条件付保証バジェット・マージンを前記より重要な保証バジェットが消耗している場合に有するが、前記より重要な保証バジェットが消耗していない場合に有しない予約コマンドをスケジューラに送るスケジューラとを備え、
前記第１のタスクが後に、前記保証バジェット・マージンが前記第１のタスクによって先行して解放されている際に、前記より重要な保証バジェットが消耗しておらず、よって、前記条件付保証バジェット・マージンが前記第２のタスクに供給されていなかった場合に、現時に前記保証バジェット・マージンを必要としていることを判定し、これを前記条件付バジェット監視器に伝達すると、前記条件付バジェット監視器は、前記第１のタスクへの前記保証バジェット・マージン及び前記より重要な保証バジェット、並びに前記第２のタスクのみへの前記より重要でない保証バジェットを有する予約コマンドを前記スケジューラにすぐに送り、
前記第１のタスクが後に、前記保証バジェット・マージンが前記第１のタスクによって先行して解放されている際に、前記より重要な保証バジェットが消耗しており、よって、前記条件付保証バジェット・マージンが前記第２のタスクに供給されていた場合に、現時に前記保証バジェット・マージンを必要としていることを判定し、これを前記条件付バジェット監視器に伝達すると、前記条件付バジェット監視器は、前記第１のタスクへの前記保証バジェット・マージン及び前記より重要な保証バジェット、並びに前記第２のタスクのみへの前記より重要でない保証バジェットを有する予約コマンドを前記スケジューラに送り、前記条件付バジェット監視器は、前記条件付保証バジェット・マージンの撤回を前記第２のタスクに通知することを特徴とする装置。
【請求項２０】
請求項19記載の装置であって、前記より重要な保証バジェットの消耗によって、後続する1つ又は複数のより重要な保証バジェット期間における前記条件付保証バジェット・マージンの供給が可能になることを特徴とする装置。
【請求項２１】
システムにおける複数のタスクを制御する方法であって、
タスクが阻止状態に留まっている時間を、前記タスクに関連したバジェットに帰する工程と、前記タスクが阻止状態に留まっている期間中に、前記阻止タスクを備えたバジェットを維持する工程とを備えることを特徴とする方法。
【請求項２２】
請求項21記載の方法であって、
前記第１のタスク又は前記第２のタスクが阻止された状態になった場合に、前記第１のタスク又は前記第２のタスクの阻止状態を示すメッセージを送る工程を更に備えることを特徴とする方法。
【請求項２３】
請求項21記載の方法であって、
阻止時間が所定の閾値を超えたかを判定する工程を更に備えることを特徴とする方法。
【請求項２４】
請求項23記載の方法であって、
前記阻止時間が前記所定の閾値を超えた場合にバジェットを撤回し、もう一度割り当てる手法を実施する工程を更に備えることを特徴とする方法。
【請求項２５】
請求項23記載の方法であって、
前記阻止タスクが阻止状態に留まっている間、又は現行バジェットが失効するまで、前記阻止時間を前記阻止タスクに帰することを続ける工程を更に備えることを特徴とする方法。
【請求項２６】
装置であって、
タスクと、
該タスクにバジェット及びバジェット・マージンを割り当てるための割り当て機構と、
バジェット化された量を前記タスクに供給するスケジューラとを備え、前記タスクが阻止状態になると、前記阻止タスクは、阻止状態を示すメッセージを前記スケジューラに送り、前記スケジューラは、前記バジェット及び前記バジェット・マージンを前記阻止タスクに供給し続け、前記阻止タスクが非阻止状態になるか、又はバジェット期間が満了するまで阻止時間が前記阻止タスクのバジェットに帰されることを特徴とする装置。
【請求項２７】
システムにおける複数のタスクを制御する方法であって、
利得時間をもたらす側の優先度よりも低い優先度で利得時間の消費側に利得時間を供給する工程と、
次の定期的なバジェットの優先度よりも高い優先度で前記利得時間の消費側に前記利得時間を供給する工程とを備えることを特徴とする方法。
【請求項２８】
請求項27記載の方法であって、
第１のタスクに対して第１の優先度を設定する工程であって、前記第１のタスクが前記利得時間をもたらす側である工程と、
第２のタスクに対して第２の優先度を設定する工程であって、前記第２のタスクが前記利得時間の消費側であり、前記第２の優先度が前記第１の優先度よりも低い工程と、
前記第１の優先度と前記第２の優先度の間に中間優先度を設定する工程とを備え、前記利得時間の消費側に前記利得時間を供給する工程が、前記中間優先度で前記第２のタスクに前記利得時間を供給する工程を更に備えることを特徴とする方法。
【請求項２９】
装置であって、
第１の優先度実行レベルを有する第１のタスクと、
前記第１の優先度レベルよりも低い第２の優先度実行レベルを有する第２のタスクと、
利得時間を判定し、前記第１のタスク及び前記第２のタスクの間で利得時間を割り当て、前記第２の優先度レベルよりも高く、前記第１の優先度レベルよりも低い中間優先度レベルで前記第２のタスクに前記第１のタスクから利得時間を割り当て、前記第１の優先度レベルで前記第１のタスクにもう一度利得時間の再割り当てを行うスケジューラとを備えることを特徴とする装置。
【請求項３０】
請求項29記載の装置であって、前記スケジューラは、利得時間をもたらす側の優先度よりも低い優先度で利得時間の消費側に利得時間を供給し、次の定期的なバジェットの優先度よりも高い優先度で前記利得時間の消費側に利得時間を供給することを特徴とする装置。
【請求項３１】
請求項３０記載の装置であって、前記スケジューラは、第１のタスクに対して第１の優先度を設定し、前記第１のタスクは、前記利得時間をもたらす側であり、第２のタスクに対して第２の優先度を設定し、前記第２のタスクは、前記利得時間を消費する側であり、前記第２の優先度は、前記第１の優先度よりも低く、前記第１の優先度と前記第２の優先度の間に中間優先度を設定し、前記利得時間を消費する側への前記利得時間の供給は、前記中間優先度での前記第２のタスクへの前記利得時間の供給を更に備えることを特徴とする装置。
【請求項３２】
システムにおける複数のタスクを制御する方法であって、
より重要なバジェットの優先度よりも低い優先度で、より重要でないタスクに条件付保証バジェットを供給する工程と、
前記より重要なタスクに供給される前記より重要な保証バジェットの優先度のすぐ下の優先度で、前記より重要でないタスクに前記条件付保証バジェットを供給する工程とを備えることを特徴とする方法。
【請求項３３】
請求項32記載の方法であって、
前記より重要でないタスクに供給される、より重要でない保証バジェットよりも高い優先度ではあるが前記中間優先度で、前記より重要でないタスクに前記条件付保証バジェットを供給する工程を更に備えることを特徴とする方法。
【請求項３４】
請求項32記載の方法であって、
前記より重要でないタスクに供給される、より重要でない保証バジェットよりも低い優先度ではあるが前記中間優先度で、前記より重要でないタスクに前記条件付保証バジェットを供給する工程を更に備えることを特徴とする方法。
【請求項３５】
請求項32記載の方法であって、より高い重要度のタスクのバジェットに対して第１の優先度レベルを設定する工程と、該第１の優先度レベルのすぐ下の、次の優先度レベルを設定する工程とを備え、前記より重要でないタスクに前記条件付保証バジェット・マージンを供給する工程が、前記中間優先度レベルで前記より重要でないタスクに前記条件付保証バジェット・マージンを供給する工程を更に備えることを特徴とする方法。
【請求項３６】
請求項35記載の方法であって、
前記より重要でないタスクのバジェットに対して第２の優先度レベルを設定する工程を更に備え、前記第２の優先度レベルは前記第１の優先度レベルよりも低いことを特徴とする方法。
【請求項３７】
請求項35記載の方法であって、
前記より重要でないタスクのバジェットに対して第２の優先度レベルを設定する工程を更に備え、前記第２の優先度レベルは前記第１の優先度レベルよりも高いことを特徴とする方法。
【請求項３８】
請求項32記載の方法であって、
前記保証バジェット・マージンを前記第１のタスクが必要としないことを判定する工程と、前記中間優先度で前記より重要でないタスクに前記条件付保証バジェットを次いで供給する工程を更に備えることを特徴とする方法。
【請求項３９】
請求項38記載の方法であって、
前記保証バジェット・マージンを前記第１のタスクが現時に必要としていることを判定する工程と、
前記第１の優先度レベルで、前記第１のタスクによる消費のために前記第１のタスクに前記保証バジェット・マージンを戻す工程とを更に備えることを特徴とする方法。
【請求項４０】
装置であって、
第１のバジェット及び保証バジェット・マージンを消費する、第１の優先度実行レベルを有する第１のタスクと、
第２のバジェットを消費する、前記第１の優先度レベルとは異なる第２の優先度実行レベルを有する第２のタスクと、
前記第１の優先度レベルで前記第１のタスクに前記保証バジェット・マージンを供給し、前記第１の優先度レベルのすぐ下の中間レベルで前記第２のタスクに条件付保証バジェット・マージンを供給するスケジューラとを備えることを特徴とする装置。
【請求項４１】
請求項４０記載の装置であって、前記第２の優先度レベルが前記第１の優先度レベルよりも低いことを特徴とする装置。
【請求項４２】
請求項４０記載の装置であって、前記第２の優先度レベルが前記第１の優先度レベルよりも高いことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、システムにおけるリソースを管理する方法及び装置に関し、特に、リアルタイムで機能するオペレーティング・システムにおけるリソースを管理する方法及び装置に関する。
【背景技術】
【０００２】
条件付保証バジェット（CGB）は当初、図面をはじめとするその内容全体を本明細書及び特許請求の範囲に再現するかのように援用する欧州特許出願（代理人整理番号第PHNL０００６２４EPP号）明細書に開示されている。CGBの背後にある基本的な考え方は以下の通りである。より重要なタスク（MIT）は、より重要な保証バジェット（MIGB）、及び、更に、構造的な負荷増加を予期するための保証バジェット・マージン（GBM）を受ける。より重要でないタスク（LIT）は、より重要でない保証バジェット（LIGB）を受ける。更に、LITは、MITが一貫してそのGBMを用いない場合に条件付保証バジェット・マージン（CGBM）を受ける。このタイプのCGBでは、CGBMは暗黙に割り当てられる。このタイプのCGBを弱いCGBとして表すものとする。弱いという語は、保証が弱い（例えば、MITはそのGBM（の一部）を用い得るものであり、よって、LITはそのCGBMよりも少ないものを受け得る）ことを表す。
【０００３】
米国仮特許出願（代理人整理番号第613652号）明細書は、CGBの保証を強くする手法を開示しているので、本願では、この種類のCGBを強いCGBと表すものとする。強いという語は、保証が強い（例えば、MITがそのGBMを要求した場合にのみそのGBMを用いることが可能であるので、LITは、MITがGBMを解放すると、CGBMを実際に当てにすることが可能である）ということを表す。米国仮特許出願（代理人整理番号第613652号）明細書は、図面をはじめとするその内容全体を本明細書及び特許請求の範囲に援用する。
【０００４】
強いCGBも弱いCGBも、その、利点と、システムにおける用途とを有する。例として、入力読み取り器などのアプリケーションをスケーリングすることが可能でなく、よって、その負荷変動に対処するために最悪のケースのバジェット割り当てが必要な場合、強いCGBを施すことができず、よって、システムの費用効果性を向上させたい場合、弱いCGBを必要とする。
【０００５】
上記の更なる問題を説明する前に、ある程度の背景が必要である。
【０００６】
タスクは２つのタイプの消費を有することが可能である。
【０００７】
同期挙動：タスクはバジェット消費と同期して機能する（すなわち、タスクは、バジェットが補充されると開始し、バジェット期間内にその機能を完了する）。
【０００８】
非同期挙動：タスクはそのバジェットと同期して機能しない。タスクは、そのバジェット消費と比較して、進んで、又は遅れて機能し得る。
非同期挙動は、負荷を平滑化するのに用いられる場合が多い。
【０００９】
Method  of  and  System  for  Withdrawing  Budget  from  a  Blocking  Taskと題する西暦2001年3月付の欧州特許出願（代理人整理番号第PHNL０１０１２７EPP号）明細書は、図面をはじめとするその内容全体を本明細書及び特許請求の範囲に再現するかのように援用する。この出願（代理人整理番号第PHNL010127EPP号）明細書には、阻止（すなわち、入力が不足しているか、又は出力する容量が不足している場合にタスクが阻止される）期間中にバジェットをタスクから撤回する手法が開示されている。しかし、特定の場合、バジェット撤回は適切でない。
【００１０】
図面をはじめとするその内容全体を本明細書及び特許請求の範囲に再現するかのように援用する欧州特許出願（代理人整理番号第PHNL０１０８２８EPP号）明細書には、超過バジェットをタスクに割り当てる手法が開示されている。何れの欧州特許出願（代理人整理番号第PHNL000624EPP号及び第PHNL010828EPP号）明細書でも、現行期間中のバジェットの残りを、入力が不足しているか、又はその出力を格納する容量が不足している場合にタスクが阻止される際に（ストリーミング）タスク（すなわち、非同期挙動を備えたタスク）から撤回することが可能であることが暗黙的にみなされる。よって、これらの特許出願のシステムでは、MITがその現行作業を完了し、新たな作業が現れると、MITは、新たな作業を処理し始める前に次のバジェット期間まで待たなければならない。CGB供給を、予備容量割り当てと組み合わせる。
【００１１】
MITの超過バジェットがそのGBMよりも大きい場合、MITは更なる利得時間をもたらす（すなわち、MITは予備容量に寄与する）。上記参照特許出願によれば、この利得時間はLITにも供給される。しかし、この利得時間をLITに供給することは２つの欠点を有する。
【００１２】
(a)CGB及び予備容量割り当ては統計的に独立した概念であるが、これらの特許出願には両方の概念がそれらの説明/設計において組み合わせられている。一方で、これは、MITがそのGBM(の一部)を用いる場合に、LITが、そのCGBM未満を任意的に受けることに対してこのようにして補償されるという意味で強みとしてみることができる。他方で、これは、利用可能な予備容量の割り当てを予備容量マネ―ジャが制御できる度合いが低いことを意味する。
【００１３】
(b)（例えば、利得時間が利用可能になる時間が早すぎ、LITが入力をなお待っているために）LITがリソースを消費する準備ができていない場合にはいつでも、LITは、バジェットの撤回が理由で更なる予備的措置なしでそのCGBMを失うことにもなる（図面をはじめとするその内容全体を本明細書及び特許請求の範囲に援用する、Method  of  and  system  for  withdrawing  budget  from  a  blocking  taskと題する西暦2001年3月付の欧州特許出願（代理人整理番号第PHNL０１０１２７EPP号）明細書を参照されたい）。バジェットの撤回は、LITが厳密に周期的にそのバジェットを必要とする場合に特に問題である。
【００１４】
欠点(a)は米国仮特許出願（代理人整理番号第613652号）明細書記載のシステムでは生じないが、それは、CGB供給及び予備容量割り当てが、別個のバジェットによって適切に分離されるからである。欠点(b)は、米国仮特許出願（代理人整理番号第613652号）明細書のシステムにおいて、次の問題が解決されると解決されることになる。
【００１５】
適切な予備的措置なしではMITは、米国仮特許出願（代理人整理番号第６１３６５２号）明細書に記載されているシステムにおけるその現行バジェット期間中にそのGBMを取り戻すことができない場合があるが、それは、LITが、そのGBMに相当するCGBMの一部を既に消費したからである。上記文献に記載されているシステムは、MITがそのGBMを要求する際に、バジェットがMITにもう一度瞬間的に転送されることを保証するものでない。GBMの要求とGBMの供給との間の遅延によって、MITの出力品質の、受け入れることができない一時的な低下が生じ得る。
【００１６】
欧州特許出願（代理人整理番号第PHNL010828EPP号）明細書に記載されている、超過バジェットを処理するシステムは、強いCGBの場合、適切でないが、それは、MITが、とりわけ、そのMIGBに制限されないからである。よって、このシステムの改良が、米国仮特許出願（代理人整理番号第６１３６５２号）明細書に記載されたシステムに対処するのに必要である。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本発明はよって、前述の課題及び欠点を解決する一方で、重要度ベースのシステムにおけるリソース使用を向上させる方法及び装置を開発するという問題に関する。
【課題を解決するための手段】
【００１８】
本発明は、とりわけ、強いCGBの場合、条件付保証バジェット・マージンを、より重要な保証バジェットの消耗によってのみイネーブルし、それによって、保証バジェット・マージンが、より重要な保証バジェットのその消費中に、より重要なタスクによって再要求されると、保証バジェット・マージンを、より重要なタスクにもう一度、瞬間的（かつ全面的）に転送することが確実に可能であるようにすることによって前述及びその他の問題を解決する。
【００１９】
よって、本発明の一局面によれば、追って通知があるまで現行バジェット期間及び後続バジェット期間において保証バジェット・マージンが必要でない旨を、より重要なタスクが判定すると、条件付保証バジェット・マージンが次いで、より重要な保証バジェットの消耗によってのみ後続バジェット期間中にイネーブルされる。これによって、条件付保証バジェット・マージンが、より重要でないタスクにまだ供給されていないので、より重要なタスクが、より重要な保証バジェットを消費する期間中に、より重要なタスクによる保証バジェット・マージンの瞬間的な再要求が可能になる。更に、保証バジェット・マージンを現行バジェット期間中に通常のやり方（より重要でないタスクへの通知、及び、保証バジェット・マージンの再要求と、保証バジェット・マージンの供給との間の通常の遅延のみ（及び当然、条件付保証バジェット・マージンのどの程度が、より重要でないタスクによって消費されたかによって、保証バジェット・マージンが最大量未満である可能性）が必要である）で再要求することが可能である。
【００２０】
更に、本発明は、システムにおける複数タスクを制御する方法を提供することによって上記問題の一部も解決する。ここでは、タスクが阻止された状態に留まっている時間が、タスクに関連したバジェットに帰され、タスクが阻止された状態に留まっている間、バジェットは、阻止されたタスクによって維持される。
【００２１】
更に、本発明は、システムにおける複数のタスクを制御する方法を提供することによって前述の問題の一部も解決する。この方法では、利得時間が、利得時間をもたらす側の優先度よりも低い優先度ではあるが、次の定期的なバジェットの優先度よりも高い優先度で、利得時間を消費する側に供給される。
【００２２】
本発明の他の局面は、以下の添付図面に照らした詳細な説明の検討によって当業者に明らかになるであろう。
【発明を実施するための最良の形態】
【００２３】
本明細書における「一実施例」又は「実施例」の語は、そうした実施例に関して記載した特定の特徴、構造又は特性を、本発明の少なくとも一実施例が有することを意味することを特筆する。本明細書中の種々の箇所における句「一実施例における」は必ずしも、その全てが同じ実施例を表すものでない。
【実施例】
【００２４】
マルチメディア・コンシューマ端末（MCT）用ソフトウェアにおけるメディア処理には、ロバスト性、予測可能性及び安定性などの、大量生産電子装置の通常の特質を維持しながらも、費用対効果が高いことが要求される。費用対効果が高いことには、全体のサービス品質（QoS）を最大にするという目標に向けて、リソースの割り当て、供給、及び効果的な使用が行われることが要求される。例示的な実施例の１つは、アプリケーション適合と、QoSベースのリソース管理とを組み合わせるものである。MCT上で実行するアプリケーションは、別々のいくつかのモードにあり得る。適合的アプリケーションは、アプリケーション・モード内の種々の品質レベルで動作し、動作品質を制御することによって出力品質とリソース利用との実行時トレードオフを可能にすることができる。リソース推定は、各アプリケーション・モードにおける各品質レベルと関連付けられる。アプリケーションは、メディア処理の効果的かつ効率的なリソース利用に対する役割を果たす。
【００２５】
QoS手法の基礎は、QoSベースのリソース管理のソフトウェア・フレームワークによって構成される。このフレームワークは、複数層制御階層と、予約ベースのリソース・マネージャとの組み合わせを有する。
【００２６】
制御階層は、効果的な、動的に調節されたリソース割り当て、及び割り当てリソースの効果的な使用の役割を果たす。全体的な効果性は、全体的なQoSを動的に最大にすることによって実現される。
【００２７】
最適化は、アプリケーションの品質レベルからリソース・ニーズへの、瞬間的に利用可能なマッピングに基づくものであり、アプリケーションの相対的な重要度も考慮に入れる。アプリケーションの品質レベルを選択することによって、制御階層は、アプリケーションの実行が期待される動作設定を定める。制御階層は、制御層に適切な時間スケールを選ぶことによって安定性に対処する。
【００２８】
リソース・マネージャは、効率的なリソース供給の役割を果たす。リソース・マネージャは、保証リソース・バジェットを供給することによってロバスト性及び予測可能性に対処する（リソース予約に基づく）。オペレーティング・システムにおけるリソース予測は、ロバスト性及び予測可能性を向上させるものであり、QoS管理の基礎である。オペレーティング・システムにおけるリソース予測は、４つの構成部分（アドミッション制御、スケジューリング、アカウンティング、及びエンフォースメント）に基づいている。適切に組み合わせると、保証された予約が備えられる。リソース・バジェットは、いわゆるリソース消費エンティティ（RCE）（1つ又は複数のタスクを有するアクティブ構成部分である）に割り当てられる。リソース・マネージャは、予備容量供給の機構によって、バジェットを介したリソース供給を補足する。予備容量は、（いわゆる利得時間である）未使用の予約（と、再要求される予約）、及び、リソース予約によって割り当てられていない時間（いわゆる余裕時間）から生じる。
【００２９】
CPUバジェットはリソース・マネージャによって供給されるが、他のシステム・リソースを、本明細書及び特許請求の範囲記載の手法を用いて施すことも可能である。リソース・マネージャは、民用既製品（COTS）リアルタイム・オペレーティング・システム（RTOS）の上に構築される。CPUリソース予約は、そのRTOSによって使用される固定優先度スケジューリング（FPS）モデルに基づいており、アドミッション・テストはレート・モノトニック解析（RMA）に基づいている。システムは、既存の利用度限界を超えるプロセッサ利用度を目指すものである。デッドラインの近いタスクに高い優先度を与える手法（EDF）に基づいたCPUリソース予約も考えられる。
【００３０】
保証CPUバジェットは、アプリケーション間の時間的隔離を備える。しかし、ロバスト性を得るためには、アプリケーションも寄与しなければならない。平均ケースに近いリソース割り当てによって、かつ、動的な負荷変動を前提とすれば、アプリケーションは、時間的な（又は確率的な）過負荷及び構造的な（又は体系的な）過負荷に直面することになる。結果として生じるロバスト性の問題は、アプリケーション自体によって解決しなければならない。言い換えれば、アプリケーションは、そのバジェットでどうにかやっていかなければならない。この目的で、適合的アプリケーションは、その動作品質レベルの制御によって出力品質及びリソース利用を交換する。前述のアプリケーション特有制御は、制御階層の最下位層に位置する。
【００３１】
本明細書及び特許請求の範囲記載の実施例は、スケーラブルなビデオ及びスケーラブルな３次元グラフィックスの単一プロセッサ・システム、並びに分散システムに適用することが可能である。
【００３２】
本明細書及び特許請求の範囲記載の実施例は、適合的アプリケーション群をサポートする。容易に示すために、別途明記しない限り、各アプリケーションが単一のリソース消費エンティティ（RCE）を備え、各RCEが単一タスクを備えるものとする。複数層制御階層は、少なくとも２つの層を備える。下位層はアプリケーションの特定のコントローラ（RCE内にある）を備え、上位層は、いわゆる「品質マネージャ（QM）」である単一のコントローラを備える。更に、「バジェット・スケジューラ（BS）」を備える予約ベースのリソース・マネージャを備える。QMは、RCEが実行される品質レベルを選択する。更に、QMは、全体的なシステム利用が最大にされ、推定リソース要件がリソース利用可能性を満たすようにCPUバジェットをRCEに割り当てる。前述の大局最適化の実施に次いで、QMは、バジェット・スケジューラ（BS）によって供給されるリソース・ニーズに基づいて、実行中のRCEからの品質マッピングを維持する。アプリケーション数、アプリケーションの相対的な重要度、及びRCEの品質マッピングの変更は再最適化を必要とする。スケジューラは、CPUバジェットをRCEに供給する。こうしたバジェットは時間トリガされるものであり、厳密に周期的なものである。バジェットは、優先度操作によって実施される。バジェットのアカウンティング及びエンフォースメントは、タイマに基づくものである。
【００３３】
スケジューラは、レート・モノトニック・スケジューリング（RMS）に基づいており、よって、スケジューリングの不完全性を免れず、システムは通常、余裕時間を有するものである。更に、賢明な予備容量割り当てによって過負荷処理に（余裕）時間を明示的に予約することが考えられる。
【００３４】
CGBプロバイダの語は、CGBを供給するRCEに用い、CGBコンシューマの語は、CGBを消費するRCEに用いる。CGBプロバイダは、通常モードではMIGBを必要とし、見越モードでは更なるバジェット・マージン（GBM）を必要とする。逆に、CGBコンシューマは、見越モードではLIGBを必要とし、通常モードでは、条件付保証を備えた更なるバジェット・マージン（CGBM）が付与される。
【００３５】
LITは、厳密に周期的なバジェットを備えたCGBを受ける。バジェット・マージン全体がLITにCGBMとして供給されると、LITは（暗黙的に）、バジェット・マージンの残りに相当する利得時間全てを消費することが許される。両方のRCEがそれぞれのバジェットを消費すると（すなわち、できる限り後で消費すると）バジェット・マージンの残りが利用可能になる。RCEの何れかに予備容量を供給することは予備容量マネージャに委ねられる。この場合には、CGBコンシューマがそのCGBを消耗し、バジェット・マージンがなお残っている際に（すなわち、バジェット・マージンがもたらされる時間間隔中に）予備容量が利用可能になる。余裕時間又は利得時間としてこの予備容量を分類することは、採用される特定の観点によって変わってくるものであり得る。分類は、「スケジューリングの不完全性」の観点からは余裕時間として行われ、「バジェット・マージンの残り」の観点からは利得時間として行われ得る。もたらされる時点で利得時間を供給する機構を企図することは、CGBの代わりを企図することと同等である。
【００３６】
バジェットは、優先度操作によって実施される。バジェット内実行は高優先度で行われ、バジェット外実行は低優先度で行われる。これは、２つの主優先度帯（バジェット内実行用の高優先度帯（HP）、及びバジェット外実行（すなわち、予備容量の消費）用の低優先度帯（LP））をもたらす。複数のタスクを有するRCEは次優先度帯をもたらすので、RCE内のタスクの優先順位を付けることが可能である。RCEの優先度帯は、互いに素である（すなわち、重ならない）。バジェットは周期的なものであり、バジェット周期はRCE毎に異なり得る。HPでは、レート・モノトニック優先度順序でスケジューリングされる、すなわち、より小さなバジェット期間を備えたRCEがより高い優先度を得る。新たな期間それぞれの最初では、バジェットが補充され、RCEの優先度が、HP内のそのレート・モノトニック優先度に上げられる。バジェットが使い果たされると、RCEの優先度がLPに下げられる。複数タスクRCEの場合、内部優先度順序を変えずに、完全な次優先度帯が上げられるか、又は下げられる。
【００３７】
一実施例では、RCEの利得時間は、LPにおけるバジェット外実行についてのみ（すなわち、できる限り遅く）利用可能になる。よって、この機構を、最も直近の利得時間供給と呼ぶ。
【００３８】
本願の、利得時間の代わりの機構の基礎として、バジェットをサーバとみて、HPにおける次優先度帯とバジェットを関連付ける。バジェットを保有し、そのバジェットの次優先度帯でバジェット内実行を行うRCE以外に、次優先度帯よりも低い優先度を備えた各RCEも、そのバジェットで作動することが可能になる。RCEはよって、より低い優先度を備えたRCE全てとそのバジェットを事実上、共有する。よって、保有するRCEがプロセッサを解放すると、所有するRCEよりも低い最高優先度を備えたRCEは、プロセッサを解放するか、又はバジェットを使い果たすまで、保有するRCEのバジェットで作動することが可能である。要約すれば、最高優先度を備えたRCEの実行が、最高優先度（非消耗）バジェットに帰される。ここでは、システムは、実行RCEの次優先度帯が、帰されたバジェットの次優先度帯にせいぜい等しいことを保証する不変関係を維持する。この基本的な機構は、デフォールトの（すなわち、暗黙的な）利得時間供給を促進するだけであり、よって、利得時間の代わりのものの暗黙的な供給と呼ばれる。なお、前述の利得時間供給機構を、利得時間の代わりのものの暗黙的な供給の機構によって置き換えることは、バジェット・アカウンティングに影響を及ぼすが、RCEの優先度操作に影響を及ぼすものでない。
【００３９】
本発明の一局面によれば、次優先度帯は、高優先度における次優先度帯全てについて利得時間が供給されるようになっており、次優先度は、高優先度のすぐ下に位置する。高優先度と違って、次優先度に関連したバジェットは存在しない。中間優先度の導入は、利得時間供給のみに意図されている。予備容量マネージャは、低優先度に関連したバジェットの保有者の利得時間をRCEに、そのRCEの優先度を中間優先度に上げることによって後に明示的に割り当てることが可能である。この機構は、利得時間の代わりのものの明示的な供給と呼ばれる。
【００４０】
COBプロバイダの利得時間（すなわち、バジェットからの利得時間、及び、バジェット・マージンからの利得時間）は全て、弱いCGBの場合、CGBコンシューマに供給されるものとする。よって、利得時間の代わりのものの明示的な供給について説明した手法と同じ手法を施して、弱いCGBの場合、CGBの代わりのものの供給の実施（すなわち、HP内の、CGBプロバイダの主バジェットの次優先度帯のすぐ下の更なる次優先度帯の予約）を行うことが可能であり、HPにおけるCGBでのCGBコンシューマの実行が、CGBプロバイダの主バジェットに帰される。なお、この設定では、CGBは、欧州特許出願（代理人整理番号第PHNL01028EPP号）明細書における記載と違って、主バジェットよりも低い優先度レベルで消費される。
【００４１】
本発明の一局面によれば、CGBMはMIGBの消耗によってイネーブルされ、それによって、GBMがMITによってもう一度、MIGBのその消費中に要求される際に、GBMを、MITにもう一度、瞬間的（かつ全面的）に（すなわち、MITの現行期間中に）転送することが可能であることが確保される。なお、CGBMは、欧州特許出願（代理人整理番号第PHNL01028EPP号）明細書に記載されているようにMIGB及びGBMと同じ優先度で消費される。本発明の特定の局面によって備えられるような予備的措置なしで、CGBMはよって、MIGBの消耗の前に、すなわち、MIGBの消費が始まる前、又はMIGBの消費中、例えば、MITが、MIGBのその消費中にプロセッサを一時的に解放する際に、消費することができる。よって、本発明の特定の局面は、MITがGBMを再要求する前ではあるがMITがGBMを解放すると、後続バジェット期間中にMIGBが消費される前か、又は消費されている間にCGBMのこの消費を阻止する。
【００４２】
図１及び図２に移れば、図中には、システムにおける複数タスクを制御する方法の例示的な実施例１０が示されている。適用可能なシステムの例には、ディジタルTV受像機、ディジタル拡充アナログTV受像機、及びセットトップ・ボックス（STB）などの大量エレクトロニクス（HVE）マルチメディア・コンシュ―マ端末（MCT）内のソフトウェアにおけるメディア処理のリアルタイム・スケジューリングがある。本発明は、他のシステムにもしかし適用することが可能であり、その適用可能性は、これらの例に限定されるものでない。
【００４３】
この実施例10の中核には、より重要なタスクによる、より重要な保証バジェット（MIGB）の消耗に基づいて、条件付保証バジェット・マージン（CGBM）を、より重要でないタスク（LIT）に供給することを可能にする手法が存在している。一部の工程は、前後関係の目的で本明細書及び特許請求の範囲記載の方法に表しているが、本発明の範囲から逸脱することなく、こうした工程の一部は飛ばすか、又は他の工程をこの手法に追加することが可能である。
【００４４】
構成要素１１では、第１のタスクが、より重要なタスク（MIT）に割り当てられる。このMITは単に、少なくとも1つの他のタスクよりも重要であるとみなされるタスクである。アプリケーション・マネージャは、MITとしてのその呼称をMITに通知することができる。システムにおける他の装置もこの通知を行うことが可能である。
【００４５】
構成要素１２では、第２のタスクが、より重要でないタスク（LIT）に割り当てられる。このLITは単に、単にMITよりも重要でないが、システムにおける何れかの他のタスクよりも重要であり得るとみなされるタスクである。通常、種々のタスクの重要度の相対レベルを管理するアプリケーション・マネージャはこうした割り当てを行うが、システム内の他の装置は、システム・アーキテクチャによってこうしたタスクを行うことができる。アプリケーション・マネージャは、LITとしてのその呼称をLITに通知することができる。システムにおける他の装置もこの通知を行うことが可能である。
【００４６】
構成要素１３では、保証バジェット・マージン（GBM）が、より重要な保証バジェット（MIGB）とともに、より重要なタスクに割り当てられ、MITには、こうした割り当てが明示的に通知される。一部のアプリケーションでは、システム・アーキテクチャにもよるが、こうした割り当てを明示的にMITに必ずしも通知しなくてよい場合がある。
【００４７】
構成要素１４では、より重要でない保証バジェット（LIGB）が、条件付保証バジェット（CGBM）とともに、より重要でないタスクに割り当てられ、LITには、こうした割り当てが明示的に通知される。MITと同様に、必ずしも、全ての場合においてこうした割り当てをLITに明示的に通知しなくてよい場合がある。更に、システムにおける種々の装置が、システム・アーキテクチャによってMIT及びLITを通知する工程を行うことができる。例えば、図３に示すように、割り当て機構は、こうした割り当てをLIT及びMITに通知することができる。
【００４８】
構成要素１５では、より重要な保証バジェット、及び保証バジェット・マージンがMITに供給され、より重要でない保証バジェットがLITに供給される。こうしたバジェット及びバジェット・マージンは、システムにおける種々の装置によって供給することが可能であるが、図３に示すように、こうしたバジェット及びバジェット・マージンを供給するのにスケジューラが用いられることが多い。
【００４９】
構成要素１６では、MITは、そのGBMをもう必要としない旨を判定する（すなわち、MITはそのバジェット利用を任意で抑制する）。この判定は、現行バジェット期間について、又は、1つ又は複数の後続バジェット期間について行うことが可能である。通常、MITがこの判定を行う。しかし、システムにおける別の装置が、先行消費及び予定タスクに基づいてMITに代わってこの判定を行うことができる可能性が残されている。
【００５０】
構成要素１７では、MITがそのGBMをもう必要としない旨のメッセージが送られる。このメッセージは、MITによってスケジューラに送ることが可能であるか、又は、スケジューラによって、システムにおける、中央コントローラ若しくは割り当て機構に、又は、特定の他の装置（アプリケーション・マネージャなど）に送ることが可能である。ここで重要な局面は、この情報を保有しながら後続工程を行うことが可能であるように、メッセージが明示的に送られることである。下記の構成要素１９では、LITには、MITがGBMを解放し、MIGBが消耗された（すなわち、CGBMの供給のための初期状態）後で（かつ、当然、MITはGBMを再要求していない）通知される。
【００５１】
構成要素１８では、MITがなおGBMを再要求していない間にMIGBが消耗したか否かについて判定が行われる。MIT、又はシステムにおける別の構成要素（スケジューラ又は割り当て機構など）がこの判定を行うことが可能である。スケジューラは通常これを判定するが、それは、MITはMIGBの消耗を知らなくてよいからである（例えば、MITが非同期で実行する場合）。しかし、システムにおける別の装置を用いて、システム・アーキテクチャによってMIGBバジェット消費を追跡することができる。
【００５２】
（構成要素18で判定されるように）MIGBが消耗しており、GBMがGBMをなお再要求していない場合、構成要素１９で、保証バジェット・マージンはMITにもう供給されず、条件付保証バジェット・マージンが、より重要でないタスクに準備され、MIT及びLITにはこうした供給が明示的に通知される。（構成要素１８で判定されるように）MIGBが消耗しており、GBMがMITによって再要求された場合、構成要素１８１で処理は図２の構成要素２４に進む。なお。この段階で、LITはCGBMを受けておらず（すなわち、単一の期間も）、スケジューラはGBMをMITに通常のやり方で供給し続ける。
【００５３】
工程１９１で、CGBMが工程１９でLITに供給されており、MIGBバジェット期間が、MITによってGBMが再要求されることなく満了する場合、処理１０は構成要素１９３に進み、これは図２の構成要素２１に進む。
【００５４】
工程１９１で、CGBMが工程１９でLITに供給されており、MIGBバジェット期間が、MITによってGBMが再要求されることなく満了する訳でない場合、処理１０は構成要素１９４に進み、これは図２の構成要素２４に進む。そうした場合には、MITは、予備容量消費中に（すなわち、バジェット外実行中に）GBMを再要求している。
【００５５】
図２に移れば、構成要素２１では、処理１０は図１、構成要素１９３から到達する。MITがGBMを解放している場合でも、バジェット期間におけるMIGBの消耗前に、CGBMがLITに供給されることは決してない。よって、図２は、MITによってGBMが再要求されることなく、MIGBの各バジェット期間中にMIGBが消耗しているか否かについての明示的な検査（構成要素２２ｂ）を備えたループを表す。
【００５６】
構成要素22aでは、MIGBの新たなバジェット期間の最初に、CGBMがディセーブルされる、すなわち、LITにもう供給されない（先行して、MIGBのそのMIGBバジェット期間における消耗の結果、MITがGBMを解放し、CGBMがLITに供給していても）。構成要素22bでは、MITによってGBMが再要求されることなくMIGBが消耗した場合、構成要素22cでは、CGBMが次いでイネーブルされる、すなわち、LITに供給される。言い換えれば、GBMの消耗によって、CGBMの供給が「トリガ」される。
【００５７】
構成要素22bでは、MIGBの消耗前にMITによってGBMが再要求される場合、処理１０は構成要素２５に進む。
【００５８】
構成要素22dでは、MITによってGBMが再要求されることなくMIGBバジェット期間が終了する場合、処理１０は構成要素22aに進み、ループがもう一度始まる。構成要素22dで、MIGBバジェット期間が終了する前に（しかし、今度は、MIGBが消耗しており、よって、CGBMがLITに供給された後に）MITによってGBMが再要求される場合、処理は構成要素22eに進み、ここでは、MITはGBMを必要とする旨を判定し、MITがGBMを必要とする旨のメッセージが次いで送られ（構成要素22f）、CGBMが次いで、LITから除去され、GBMがMITに供給され、LITは、CGBMの撤回について明示的に通知される（構成要素22g）。処理は次いで図１中の構成要素192に（接続構成要素23を介して）戻る。
【００５９】
よって、（処理を構成要素１９２、図１に戻す）構成要素２３では、MIGB及びGBMがMITに供給され、LIGBがLITに供給される。
【００６０】
図２に示すように、本発明の一局面によれば、MIGBの（MITによるGBMの解放後の）各後続バジェット期間中に、MIGBの消耗（構成要素22b。当然、MITによるGBMの再要求なし）によって、LITへのCGBMの供給がトリガされる（構成要素２２ｃ）。構成要素22bは、MIGBのバジェット期間中のCGBMの供給のトリガを表す。MIGBがバジェット期間中に使い尽された場合（22bの「はい」と記した出口）、CGBMは、その同じバジェット期間中にLITに供給される（構成要素２２ｃ）。
【００６１】
MITが、構成要素２５で、バジェット期間中にGBMを要求する場合（MIGBが使い尽くされていない場合（構成要素２２ｂの「いいえ」と記した出口））、CGBMは、後続バジェット期間中にLITにもう供給されないことになるが、この段階では、MIGBのこのバジェット期間中のCGBMの供給はまだ始まっていなかった。よって、バジェット転送は、MIGBの現行バジェット期間中に、瞬間的にも全面的にも行うことが可能である。LITは撤回について明示的に通知され、GBMがMITに供給される（構成要素２６）。処理は構成要素２３で続く。
【００６２】
構成要素２３では、処理は図１（構成要素１９２）に進む。
【００６３】
構成要素２４では、処理は図１（構成要素１９４）からくる。よって、構成要素２４には、処理は同じMIGBバジェット期間中であり、かつMIGBが消耗されるまでは構成要素１９４からくるが、処理は、構成要素２５に構成要素２２ｂからくる場合、MIGBの別のバジェット期間にある。何れの場合も（同じMIGBバジェット期間の場合も別のMIGBバジェット期間の場合も）、MIGBは消耗しておらず、後続の応答は同じである、すなわち、現行バジェット期間においてCGBMがLITに一切準備されなかったのでGBMはMITに瞬時に利用可能になる。図３は、本明細書及び特許請求の範囲記載の種々の処理の役割及び相互作用の例示的な実施例を示す。第１のタスク３４は第１重要度レベルを有し、この第１のタスク３４は、より重要なタスクと呼ばれる。より高いこのタスク３４は、オペレーティング・システム３０の外部又はオペレーティング・システム３０の内部のタスクを有し得る。
【００６４】
第２のタスク３５は、第１重要度レベルよりも低い第２の重要度レベルを有する。より低いこのタスク（すなわち、より重要でないタスク）３５は、オペレーティング・システム３０の外部のタスク又はオペレーティング・システム３０の内部のタスクを有し得る。更に、第２のタスク３５は、単に第１のタスク３４よりも重要度が低いが、実行するうえで2番目に重要なタスクでもあり得る。前述の２つの段落において、重要度は全て、相対的な重要度である。アプリケーション・マネージャ３１は、重要度のレベルを割り当て、種々のタスクにその割り当てを通知し（構成要素１１、１２）、割り当て機構にこの割り当てを通知する（構成要素１１、１２）。
【００６５】
割り当て機構３２が、オペレーティング・システム３０によって行われる対象の種々のタスク３４、３５の間でリソース・バジェットを割り当てるよう備えられている。本発明の一局面によれば、割り当て機構３２は、より重要な保証バジェット、及び保証バジェット・マージンについて第１のタスク３４に明示的に通知する（構成要素１３）。より重要な保証バジェットは、第１のタスク３４によって用いるためにとっておくリソースや他の限定利用可能性アイテムの量である。保証バジェット・マージンは、第１のタスク３４が必要な場合に、より重要な保証バジェットを超える、第１のタスク３４によって用いるためにとっておくリソースや他の限定利用可能性アイテムの量である。
【００６６】
割り当て機構３２は又、より重要でない保証バジェット及び条件付保証バジェット・マージンについて第２のタスク３５に明示的に通知する（構成要素１４）。より重要でない保証バジェットは、第２のタスク３５によって用いるためにとっておくリソースや他の限定利用可能性アイテムの量である。条件付保証バジェット・マージンは、第２のタスク３５が必要とする場合に、より重要でない保証バジェットを超える、第２のタスク３５によって用いるためにとっておくリソースや他の限定利用可能性アイテムの量であるが、その量は、他の所（より重要なタスク３４によってなど）で必要でない場合にのみ供給される。割り当て機構は、割り当てについてもスケジューラに通知する（構成要素１３、１４）。
【００６７】
スケジューラ３３は、オペレーティング・システム３０によって行われる対象の種々のタスク３４、３５（第１のタスク３４及び第２のタスク３５をはじめとする）への、バジェット化されたリソース量の準備を制御する。スケジューラ３３は、考えられる第１の場合に第１のタスク３４に、前記より重要な保証バジェット及び前記保証バジェット・マージンを供給する（構成要素１５）。スケジューラは又、より重要でない保証バジェットを第２のタスク３５に、考えられる第１の場合に供給する（構成要素１５）。
【００６８】
第１のタスク３４は、より重要な保証バジェットのみによって第１のタスク３４が適切に実行することが可能であることを実行中の特定の時点で判定した場合、その保証バジェット・マージンを第１のタスク３４が必要としない旨をスケジューラ３３に明示的に通知する（構成要素１７）。
【００６９】
この時点で、より高い重要度の保証バジェットが消耗したか否かについての判定が行われる。本発明の一局面によれば、MIGBの消耗を用いて、第２のタスクへの条件付保証バジェット・マージンの供給を開始する。MITがGBMをもう一度要求する前にMIGBが消耗しない場合（構成要素２５）、CGBMの供給はイネーブルされず、第２のタスクはCGBMを受けない。MIGBが消耗した場合、CGBMがイネーブルされ（構成要素１９）、CGBMを第２のタスクに供給することが可能である（構成要素１９）。CGBMの準備（構成要素２２ｃ）は、MIGBの消耗（GBMをMITが再要求していないという前提で、構成要素２２ｂにおいて判定される）によって各後続MIGBバジェット期間においてイネーブルされる。
【００７０】
CGBMの準備をイネーブルすると、スケジューラ３３は、第１の考えられる場合での第１のタスク３４への保証バジェット・マージンの供給を停止し、第１の考えられる場合での第２のタスク３５への条件付保証バジェット・マ―ジンの供給を開始する（構成要素２２ｃ）。この後、スケジューラ３２は、条件付保証バジェット・マージンの付与を第２のタスク３５に通知する（構成要素２２ｃ）。条件付保証バジェット・マージンは、供給が開始されると、より重要な保証バジェットの後続期間中のより重要な保証バジェットの消耗によって供給されることになる（構成要素２２ｂ）、すなわち、その場合、より重要な保証バジェットの消耗（構成要素２２ｂ）は、条件付保証バジェット・マージンの供給を自動的にトリガし、それは、こうした供給をMIT及びLITに通知することを伴う（構成要素２２ｃ）。
【００７１】
後に、第１のタスク３４が保証バジェット・マージンも必要とすることを実行中の特定の時点で第１のタスク３４は判定し得るものであり、その場合、その保証バジェット・マージンを第１のタスク３４が必要とする旨を第１のタスク３４はスケジューラ３３に明示的に通知する（構成要素２２ｆ、構成要素２５、又は構成要素１８１）。
【００７２】
アプリケーション・マネージャ３１は、特定のタスクへのMITの役割の割り当て及び割り当て解除を行う（図１の構成要素１１）。アプリケーション・マネージャは、特定の別のタスクへのLITの役割の割り当て及び割り当て解除も行う（構成要素１２）。アプリケーション・マネージャ３１は次いで、割り当て機構３２がアクティブになる一方で、イナクティブになる。MITの役割及びLITの役割が失効すると、アプリケーション・マネージャ３１はもう一度アクティブになる一方、割り当て機構３２はイナクティブになる。割り当て機構３２はMIGB及びGBMをMITに割り当て、これらの割り当てをMITに明示的に通知する（図１の構成要素１３）。割り当て機構３２はLIGB及びCGBMをLITにも割り当て、これらの割り当てをLITに明示的に通知する（図１の構成要素14）。割り当て機構３２は予約をスケジューラ３３に送り、スケジューラ３３はスケジューラ処理（完了まで実行する）を起動させる。スケジューラ３３は、割り当て機構からの、LIT及びMITに対する予約コマンドを受け入れ、MITにMIGB及びGBMを付与し、LITへのLIGBの付与も行う。スケジューラは次いで、スケジューリング・アルゴリズムによって実行する。スケジューラ３３は、MITがGBMをもう必要としない旨のメッセージをMITから受ける。スケジューラは次いで、MIGBのみをMITに付与し、バジェット増加をLITに通知し、LIGB及びCGBMをLITに付与する（図１の構成要素１９）。スケジューラ３３は、そのGBMをMITが現時に必要とする旨のメッセージをMITから受ける（図１の構成要素22e）。
【００７３】
図４に移れば、図中には、本発明の別の局面による種々の処理の相互作用の例示的な実施例４０を示す。アプリケーション・マネージャ41は、特定のタスクへのMITの役割の割り当て及び割り当て解除を行う（図１の構成要素１１）。アプリケーション・マネージャは、特定の別のタスクへのLITの役割の割り当て及び割り当て解除も行う（構成要素１２）。アプリケーション・マネージャ41は次いで、割り当て機構42がアクティブになる一方で、イナクティブになる。割り当て機構42はMIGB及びGBMをMITに割り当て、これらの割り当てをMITに明示的に通知する（構成要素１３）。割り当て機構42はLIGB及びCGBMをLITにも割り当て、これらの割り当てをLITに明示的に通知する（構成要素14）。
【００７４】
割り当て機構４２は予約をCBM４６に送る。CBMは予約をスケジューラ処理（完了まで実行する）に送る。CBMは、MITがGBMをもう必要としない旨のメッセージをMITから受け（構成要素１７）、MITがGBMを現時に必要としている旨のメッセージをMITから受ける（構成要素２２ｆ、２５）。同様に、CBMは、CGBMが利用可能である旨のメッセージ（構成要素１９）及びCGBMがもう利用可能でない旨のメッセージ（構成要素２２ｇ）のそれぞれをLITに送る。更に、CBM４６は、予約変更をスケジューラに送り、肯定応答をスケジューラから受ける。スケジューラ43は、CBMからの、LIT及びMITに対する予約コマンドを受け入れ、MITにMIGB及びGBMを付与し（構成要素２２ｇ）、LITへのLIGBの付与も行う。スケジューラは次いで、スケジューリング・アルゴリズムによって実行する。予約における変更は、スケジューラ４３によってLIT及びMITに送られる。スケジューラ４３は、こうした変更の肯定応答を送り側に送る。
【００７５】
従来の手法の下では、タスクが阻止されると、バジェットが阻止タスクから撤回される。本明細書及び特許請求の範囲記載のタスク阻止時間は、タスクが阻止されており、かつ、より低い重要度の1つ又は複数のタスクが実行している時間である。
【００７６】
従来の手法とは対照的に、本発明の一局面によれば、タスクが阻止されるとタスクからバジェットを撤回するのではなく、阻止時間が、阻止されているタスクのバジェットに帰される。より低い重要度のタスクは、利用可能な場合、それ自身のバジェットで実行する。阻止されているタスクのバジェットに阻止時間を帰することによって、この阻止時間が（予備容量）消費に利用可能になる時点が事実上遅れる。そうすることによって、本発明は、非阻止状態になる阻止タスクが、現行バジェット期間中に実行できなくなることを妨げるものである。よって、現行バジェット期間中に、瞬間的に阻止され、次いで、非阻止状態になるタスクは、性能におけるわずかな犠牲（そのバジェットの、（阻止されなければ生じることになるものよりも）わずかな消費以外の）を伴って再開することが可能である。
【００７７】
この手法の拡張として、可変の限度若しくは閾値、又は調節可能な限度若しくは閾値を、阻止タスクによるバジェットのかなりの消費を妨げるよう阻止タスクのバジェットに帰される阻止時間に対して設定することが可能である。この手法の下では、バジェットの、撤回、及び他のタスクへの再割り当ては、欧州特許出願（代理人整理番号第PHNL０１０１２７EPP号）明細書及び欧州特許出願（代理人整理番号第PHNL０１０８２８EPP号）明細書に記載されたように行われることになる。
【００７８】
阻止タスクがスケジューラ（、又は、システム・アークテクチャに応じてシステムにおける他の装置）にその阻止状態について通知することをこの手法の実施は必要とし、その長さを監視することができる。しかし、バジェットはこの期間中には通常のやり方で阻止タスクに供給され続けるので、更なる工程は必要でない。阻止タスクが非阻止状態になると、通常のバジェット消費が再開するが、阻止タスクは阻止されていてもバジェットを通常のやり方で消費していたかのように阻止時間が阻止タスクのバジェットから控除されている。タスク間の重要度の通常レベルは有効であるので、タスクが阻止状態に留まっている間に阻止時間を補正する際に阻止タスクのバジェットが阻止タスクによって消費される場合、他のタスクを通常のやり方で開始することができる。阻止タスクのバジェットが補充されると、阻止に関する状況によって阻止タスクが非阻止状態になり得るか、又は、阻止タスクが阻止状態に留まり得るものであり、その場合、阻止時間が阻止タスク・バジェットにやはり帰される（阻止タスクが阻止されていなければそのバジェットを消費している際に阻止時間が生じる程度のみ）。
【００７９】
図5に移れば、図中には、システムにおける複数タスクを制御する方法の例示的な実施例500が示されている。
【００８０】
なお、阻止時間の補正は、弱いCGBにも強いCGBにも施すことが可能であるが、本願の説明は、強いCGBのみを包含している。更に、「阻止時間の補正」と同様な手法は、GBMの消費にもあてはまるが、ここでは、MIGBの消費についてのみ説明する。厳密に言えば、阻止時間の補正は、CGBとは全く無関係である。その結果、単一のタスク、及び図５の汎用的なタイプのバジェットをみることで十分であり、重要度レベルの必要性は消える。
【００８１】
本明細書及び特許請求の範囲記載の他の実施例の一部と同様に、構成要素５０１では、バジェットが、新たなバジェット期間の最初にタスクに供給される。この実施例５００では、他の実施例における上記装置は構成要素５０１を行うことができる。構成要素５０２では、タスクは阻止状態になる。これは、種々の理由（入力がないこと、又は出力を送る対象の容量がないことなど）で起こり得る。
【００８２】
構成要素５０３では、タスクが阻止されている旨のメッセージを送る。メッセージを送ることは常に必要という訳でないが、しかし、そうすることによって、システムにおけるスケジューラや特定の他の装置による阻止期間の監視を可能にして適切な動作を確保することが可能である。例えば、過度な時間長、タスクが阻止状態に留まっている場合、阻止タスクのバジェットの補正措置又は再割り当てが望ましいことがあり得る。タスクは、スケジューラ又は別の装置にメッセージを送って阻止時間を監視することができる。構成要素５０４では、阻止時間は、バジェットがタスクによって消費されたかのように通常のやり方でタスク・バジェットに帰される。実際に、バジェットはこの時点ではタスクから撤回されていないので、タスクは、阻止状態に留まっていてもそのバジェットを消費し続ける。
【００８３】
構成要素５０５では、阻止時間が特定の所定閾値を超えているかを判定するよう阻止時間を監視する。スケジューラや他の装置がこの監視を行うことができる。
【００８４】
阻止時間が所定の閾値（無限であり得るので、事実上、閾値は存在しない）を超えている場合、バジェットの撤回を実施する前述の従来技術の手法は、構成要素５０６と同様に実施することができる。
【００８５】
閾値を超えていない場合、処理は構成要素５０７に進み、構成要素５０７では、阻止タスクについてバジェット期間が満了したか否かについての判定を行う。システムにおけるスケジューラや他の装置がこの判定を行うことが可能である。
【００８６】
構成要素５０７で判定されるようにバジェット期間が満了している場合、処理５００は構成要素５０１に戻り、構成要素５０１では、バジェットは補充される。スケジューラは、この判定を行うことができる。
【００８７】
構成要素５０２では次いで、MITは、先行バジェット期間から阻止され続け得るか、又は、もう一度阻止状態になり得るものであり、その場合、処理５００は前述のように続く。構成要素５０７で判定されるように、バジェット期間が満了していない場合、処理が非阻止状態になったかを判定するよう、阻止処理を構成要素５０８で監視する。そうでない場合、阻止時間は（構成要素５０４におけるように）タスク・バジェットに帰され続け、阻止時間は（構成要素５０５におけるように）監視され続ける。
【００８８】
構成要素５０８で判定されるようにタスクが非阻止状態になっている場合、タスクは、（構成要素５０９におけるように）通常のやり方でそのバジェットの消費を再開するが、それは、バジェット期間が満了していないからであり、阻止状態になる（構成要素５１０で判定されるように（それによって、処理は構成要素５０２に戻る））か、又はバジェット期間が終わる（構成要素５１０で判定されるように（それによって、処理は構成要素５０１に戻る））までそうし続ける。
【００８９】
図３乃至図４に示す装置と同様な装置を用いて図５に表す方法５００を実施することが可能である。
【００９０】
本発明の更に別の局面によれば、利得時間が、利得時間をもたらす側の優先度よりも低い優先度ではあるが、次の定期的なバジェットの優先度よりも高い優先度で利得時間を消費する側に供給される。
【００９１】
本明細書及び特許請求の範囲記載の優先度は、相対的な重要度とは異なる。優先度操作は、リソース割り当て手法においてバジェットを供給する方法である。よって、優先度はバジェット・スケジューラに局所の機構であり、こうした優先度はオペレーティング・システムによって通常、供給される。バジェット・スケジューラのレベルを超える優先度は、利用可能でない。これはバジェットの保証を確保するが、それは、アプリケーションは、優先度を変更することができた場合、バジェットの保証を損ない得るからである。対照的に、相対的な重要度は、アプリケーション・マネージャによって考慮に入れられる課題である。種々のアプリケーションが、それら自体のうちで相対的な重要度を有する。相対的な重要度は、バジェットのサイズと、特定のアプリケーションに選択される品質レベルとを有する。
【００９２】
MITに供給されるバジェット・マージンは保証されている（GBM）。LITに供給されるバジェット・マージンは条件付きで保証されている（CGBM）。何れのバジェット・マージンも、半統計的に判定される（すなわち、バジェットのアドミッション・テストの一部として判定される）。対照的に、利得時間は、何れかのタスクに条件的に保証されている訳でも、その他の方法で保証されている訳でもない。利得時間は、タスクに利用可能であるが、そのタスクによって用いられない時間から生じる。利得時間は実行時に利用可能になる。その結果、その時間は、別のタスクに動的に供給し、別のタスクによって用いることが可能であり、その利得時間をどのタスクが用いることが可能であるかの判定は、例えば、予備容量マネージャによって行われる。よって、適切なストラテジに基づいてタスクを利得時間に供給するのは予備容量マネージャに委ねられる。MITもLITもそれらのバジェットに加えて利得時間（例えば、他のタスクから）を受けることができる。
【００９３】
よって、中間優先度レベルが利得時間消費に予約される。このようにして、利得時間をもたらす側は、必要な際に、現行バジェット期間中にもそのバジェットを取り戻すことが可能である。更に、利得時間の消費及び割り当ては、何れかの低優先度バジェットの供給、又は他のタイプの予備時間の供給に干渉しない。
【００９４】
本発明の更に別の局面によれば、専用サーバがバジェット毎に備えられ、そこでは、元のバジェットの「保有者」が最高優先度を有し、利得時間の消費側は、低優先度（それぞれは、例えば、予備容量マネージャによって割り当てられる）を有する。最後に、利得時間をもたらすことはバジェットのスケジューリングを変えないが、どのタスクがバジェットを消費するかを変える。
【００９５】
図6に移れば、図中には、２つのタスクの間でのリソース割り当てを制御する方法の例示的な実施例が示されている。単に、次のタスクの優先度レベルよりも高いが利得時間をもたらす側よりも低い優先度レベルで利得時間が常に消費されるように複数タスク間で中間優先度レベルを割り当てることによって3つ以上のタスクに同じ手法を施すことが可能である。
【００９６】
構成要素６０１では、第１のタスクに第１の優先度が割り当てられる。バジェット・スケジューラが通常、この割り当てを行う。
【００９７】
構成要素６０２では、第２のタスクに第２の優先度が割り当てられる。バジェット・スケジューラは通常、この割り当ても行う。
【００９８】
構成要素６０３では、中間優先度が利得時間消費に設定され、この中間優先度は、第１の優先度と第２の優先度との間に位置する。バジェット・スケジューラは、この中間優先度の割り当ても制御する。
【００９９】
実行中の特定時点で、第１のタスクは、そのバジェットに余剰時間（すなわち、利得時間）を残してその作業を完了することができる。よって、構成要素６０４では、バジェット・スケジューラは次いで、利得時間が再割り当てに利用可能である旨を判定することができる。バジェット・スケジューラは、現行バジェット期間において第１のタスクに割り当てた状態で残っている時間をバジェット・スケジューラが分かっているので、第１のタスクがその作業を完了したことをバジェット・スケジューラに示した場合に、これを判定することが可能である。
【０１００】
そういうものとして、構成要素６０５では、バジェット・スケジューラは次いで、この利得時間を別のタスク（第１のタスクよりも低い実行優先度を有する第２のタスクなど）に割り当てることが可能である。本発明の一局面によれば、この利得時間は次いで、第２のタスクの優先度レベルよりも高いが、第１のタスクよりも低い中間優先度レベルで第２のタスクに割り当てられる。これによって、第２のタスクは、そのバジェットを消費する前に利得時間を確実に消費する。更に、中間優先度レベルでのこの割り当てによって、他のバジェット割り当てに干渉することなくその時間の残り（消費利得時間を除く）を再要求することが可能であることも確保される。
【０１０１】
よって、構成要素６０６では、第１のタスクは、例えば、現行のバジェット期間中に新たな作業が到着したか、又は品質レベルの増加が更なる労力を必要とするので、現時にその実行を再開する必要があるので、利用可能な利得時間がもうないことを判定し得る。これは、第１のタスクからバジェット・スケジューラにメッセージを送ることによって達成することが可能である。バジェット・スケジューラは、（記録しているので）第１のタスクが現在、バジェット期間中のどこに存在しているか、及び残っている時間がどのくらいかをそれ自体が分かっている。そういうものとして、バジェット・スケジューラはその場合、他のタスクが消費するのに利用可能なものとして残っている利得時間（第１のタスクからの）がないことが分かっている。
【０１０２】
よって、構成要素６０７では、利得時間が第１のタスクに戻される。これは、中間レベルでの利得時間の第２のタスク実行を停止し、第１の優先度レベルでの第１のタスクに利得時間をもう一度割り当てることによって達成される。
【０１０３】
図７に移れば、図中には、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスク７４、７５を制御する装置の例示的な実施例７０が示されている。システム７０は、バジェット及びバジェット期間に応じて動作するバジェット・スケジューラ７３及び少なくとも２つのタスク７４、７５を有する。一方のタスク７４は、他方のタスク７５よりも高い優先度が割り当てられる。より高い優先度を備えるタスク８４は、利用可能な利得時間を有している（か、又はその作業を完了した）ことを特定時点で判定し、バジェット・スケジューラ７３に通知し、バジェット・スケジューラ７３は次いで、この利得時間を別のタスク７５（第２のタスク７５など）に割り当てることができる。利得時間は、第２のタスク７５のバジェットよりも高い優先度であるが、第１のタスク７４のバジェットよりも低い優先度である中間優先度レベルで第２のタスク７５に割り当てられる。
【０１０４】
前述のように、アプリケーション・マネージャ７１は、タスク１（７４）及びタスク２（７５）に対する優先度レベルの割り当て及び割り当て解除を行う。アプリケーション・マネージャ７１は次いで、割り当て機構７２がアクティブになる一方で、イナクティブになる。割り当て機構７２は、種々のバジェット及びバジェット・マージン（条件付及び保証）をタスク７４、７５に割り当て、これらの割り当てを明示的に通知する。
【０１０５】
割り当て機構72は予約をスケジューラ処理73に送り、スケジューラ処理７３は完了まで実行する。スケジューラ７３は、中間優先度で第２のタスク７５に利得時間を、第１のタスク７４が、バジェットに残っている時間でその作業を完了すると送る。更に、スケジューラ７３は、第１のタスク７４が先行して利得時間を解放したが現時にそれを必要とする場合に利得時間を第１のタスク７４に戻す。スケジューラは又、タスク７４、７５の間で種々の優先度を割り当てる。
【０１０６】
一般に、装置７０によって、次に並んだタスク（この実施例７０では第２のタスク７５）より高い優先度レベルではあるが、利得時間をもたらす側（この実施例７０では第１のタスク７４）よりも低いレベルで利得時間が消費されることが確保される。更に、バジェット・スケジューラ７３によって、バジェットの残り（消費された利得時間を除く）が、必要な場合、できる限り少ない中断で第１のタスク７４に戻されることが確保される。
【０１０７】
本発明の更に別の局面によれば、CGBMが、CGBプロバイダのMIGB及びGBMと同じ優先度を用いることなく弱いCGBのCGBコンシューマに供給される。従来の実施形態によれば、CGBプロバイダ（すなわち、MIT）の超過バジェットが、MITのスケジューリング特性とともにCGBコンシューマ（すなわち、LIT）に供給されており、そうした特性は、「第１のタスク（のバジェット）の期間及び優先度に相当する」。
【０１０８】
本発明の別の局面によれば、MIGB及びGBMと同じ優先度でCGBMを供給するのではなくCGBMの供給の代替策として、CGBMが別の、より低い優先度で供給される。この優先度は、MIGB及びGBMの優先度未満であるが、何れかの他のバジェットの優先度よりも高い。言い換えれば、CGBMは中間優先度レベルで供給される。その結果、弱いCGBを供給するための機構は、別のタスク（又はRCE）への、利得時間「の代わりのもの」の供給のための機構と同様である。
【０１０９】
CGB及び利得時間は、システム内の別々のエンティティによって処理される。GBM及びCGBMは、MIT及びLITそれぞれに割り当て機構によって割り当てられる。スケジューラは後に、GBM及びCGBMをMIT及びLITそれぞれに供給する。前述のように、CGBMはLITに条件的に、すなわち、MITがそのGBMを必要としない場合にのみ供給される。MITもLITもそれらの保証バジェット（MIGB・LIGB）及びバジェット・マージン（GBM・CGBM）並びにそれらの品質レベルについて通知されるので、CGBは、制御された品質向上を可能にする。
【０１１０】
利得時間は実行時にのみ利用可能になるが、それは、RCEがそのバジェットを全面的に必要としないからである。これは、例えば、入力データの処理に必要な処理時間の量が、予期したものよりも少ない（すなわち、RCEの「負荷」は通常、メディア処理などのストリーミング・アプリケーションについてその入力データに依存している）場合に起こり得る。利得時間は暗黙的に（すなわち、デフォールト設定によって）供給することが可能であるか、又は明示的に（すなわち、予備容量マネージャによって）供給することが可能である。CGBと違って、利得時間は割り当てられず、供給されるだけである。弱いCGBの場合、CGBコンシューマはCGBM全体を受けない場合があるが、それは、CGBプロバイダは、そのGBM部分を用いることが常に可能であるからである。言い換えれば、強いCGBと違って、CGBプロバイダは、弱いCGBの場合、そのMIGBのみに一切制限されない。よって、弱いCGBの場合、CGBプロバイダの利得時間全て（すなわち、MIGB及びGBMからの利得時間）がCGBコンシューマに利用可能にされるものとする。その結果、他のRCEは、LITが必要としない場合にのみ、MITの利得時間の消費が可能になる。よって、CGBMの消費は、MIGB及びGBMの優先度レベルのすぐ下の優先度で行われる。超過利得時間（すなわち、LITによって消費されない、MITの利得時間）は、CGBM消費の優先度レベルのすぐ下の優先度レベルで更に他のRCEに供給される。
【０１１１】
阻止の補正は、必要な場合に、現行バジェット期間中にバジェットの残りを再要求する選択肢を備えた利得時間供給をサポートする。
【０１１２】
阻止の補正は、必要な場合に、その現行バジェット期間中のそのバジェットの残りをすぐに取り戻し、それによって利得時間供給を停止することが可能であることを保証することができるよう何れのバジェットについても一般に必要である。
【０１１３】
特に、CGBの場合に必要である。
【０１１４】
弱いCGBの場合も強いCGBの場合も、必要な場合に、その現行バジェット期間中に、そのMIGBの残りをすぐにMITが取り戻し、そのLIGBの残りをすぐにLITが取り戻し、それによって、利得時間供給を停止することが可能であることを保証することができること。
【０１１５】
弱いCGBの場合、必要な場合にそのGBMの残りをMITがすぐに得ることが可能であるようにすること。
【０１１６】
強いCGBの場合、必要な場合にそのGBMの残りをMITがすぐに取り戻すことが可能であるようにするようCGBプロバイダがそのGBMに対する要求を有する。
【０１１７】
弱いCGBの場合も強いCGBの場合も、必要な場合にその現行バジェット期間中にそのCGBMの残りをLITがすぐに取り戻すことが可能であることを保証することができること。
【０１１８】
阻止の補正なしでは、弱いCGBの場合、CGBMが、LITにとって利用可能になるのが早過ぎる場合がある（その場合、LITは、現行の特許によれば、そのCGBMを失うことになる）。
【０１１９】
図8に移れば、図中には、システムにおける複数タスクを制御する方法の更に別の例示的な実施例800が示されている。本発明のこの局面に重要な工程のみをこの実施例に示す。他の工程も行うことができる。
【０１２０】
構成要素８０１では、第１の実行優先度レベルが、第１のタスクによる第１のバジェット及び保証バジェット・マージンの消費に割り当てられる。
【０１２１】
構成要素８０２では、第２の実行優先度レベルが、第２のタスクによる第２のバジェットの消費に割り当てられ、第２の実行優先度レベルは、第１の実行優先度レベルとは異なる（第１の実行優先度レベルより高いか、又は低い）。
【０１２２】
構成要素８０３では、中間実行優先度レベルが、第２のタスクによる条件付保証バジェット・マージンの消費のために設定され、この中間実行優先度レベルは、第１の実行優先度レベルのすぐ下である。
【０１２３】
構成要素８０４では、第１のタスクは保証バジェット・マージンを必要としないことが判定される。
【０１２４】
構成要素８０５では、条件付保証バジェット・マージンが、第１の実行優先度レベルのすぐ下の中間実行優先度レベルで第２のタスクに供給される。
【０１２５】
構成要素８０６では、第１のタスクは現時に保証バジェット・マージンを必要とすることが判定される。
【０１２６】
構成要素８０７では、保証バジェット・マージンが、第１の実行優先度レベルで第１のタスクによる消費のために第１のタスクに戻される（か、又はもう一度割り当てられる）。
【０１２７】
図9に移れば、図中には、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスク94、95を制御する装置の例示的な実施例90が示されている。システム90は、バジェット及びバジェット期間に応じて動作するバジェット・スケジューラ93及び少なくとも２つのタスク94、95を有する。一方のタスク９４による、バジェット消費（及び保証バジェット・マージンの消費）は、他のタスク９５によるバジェット消費よりも高い実行優先度レベルが割り当てられる。そのバジェットの消費のためのより高い実行優先度レベルを備えたタスク９４は、その保証バジェット・マージンをもう必要としないこと（又はその作業を完了したこと）を特定時点で判定し、バジェット・スケジューラ９３に通知し得る。バジェット・スケジューラ９３は次いで、条件付保証バジェット・マージンを、第２のタスク９５などの別のタスク９５に割り当てる。条件付保証バジェット・マージンの消費は、タスク９４の優先度の優先度レベルのすぐ下のレベルでの中間実行優先度レベルで第２のタスク９５に割り当てる。
【０１２８】
前述のように、アプリケーション・マネージャ９１は、タスク１（９４）及びタスク２（９５）への重要度レベルの割り当て及び割り当て解除を行う。アプリケーション・マネージャ９１は次いで、割り当て機構９２がアクティブになる一方でイナクティブになる。割り当て機構92は、種々のバジェット及びバジェット・マージン（条件付及び保証）をタスク94、95に割り当て、これらの割り当てを明示的に通知する。
【０１２９】
割り当て機構92は予約をスケジューラ処理93に送り、スケジューラ処理93は完了まで実行する。スケジューラ９３は、第１のタスク９４が、バジェットに残された時間でその作業を完了すると、中間実行優先度レベルにおいて第２のタスク９５に条件付保証バジェット・マージンを次いで供給する。更に、スケジューラ９３は、第１のタスク９４が保証バジェット・マージンを先行して解放しているが、現時にこれを必要としている場合に第１のタスク９４に保証バジェット・マージンを戻すか、又は供給する。スケジュ―ラは又、タスク９４、９５の間で種々の優先度（高、中間、低）を割り当てる。
【０１３０】
一般に、装置９０によって、条件付保証バジェット・マージンが、次に並んだタスク（この実施例９０では第２のタスク９５）より高い優先度レベルではあるが、第１のタスク９４の保証バジェット・マージン又はバジェットの消費よりも低いレベルで消費されることが確保される。更に、バジェット・スケジューラ９３によって、バジェット・マージンの残り（条件付保証バジェットとして消費されるものを除く）が、必要な場合に、できる限り少ない中断で第１のタスク９４に戻されることが確保される。
【０１３１】
本明細書及び特許請求の範囲の記載は、プリエンプティブな固定優先度スケジューリング（FPPS）を示唆しているが、上記考え方を、デッドラインの近いタスクに高い優先度を与える手法（EDF）などのデッドライン・ドリブン・スケジューリングとの組み合わせで同様にうまく適用することが可能である。
【０１３２】
種々の実施例を本明細書において特に示し、説明しているが、本発明の修正及び変形が上記教示によって包含され、本発明の趣旨及び範囲から逸脱することなく特許請求の範囲記載の範囲内に収まることが認識されよう。例えば、特定の語及びプロトコルを用いているが、しかし、他の名称及びプロトコルを、本発明の範囲から逸脱することなく用いることが可能である。更に、この例は、特許請求の範囲によって包含されているが、単に、考えられる変形を例証している、本発明の修正及び変形を限定するものとして解釈されるべきでない。
【図面の簡単な説明】
【０１３３】
【図１】本発明の一局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する方法の例示的な実施例を表す。
【図２】本発明の別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する方法の別の例示的な実施例を表す。
【図３】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する装置の例示的な実施例を表す。
【図４】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する装置の別の例示的な実施例を表す。
【図５】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する方法のなお別の例示的な実施例を表す。
【図６】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する方法のなお別の例示的な実施例を表す。
【図７】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する装置の例示的な実施例を表す。
【図８】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する方法のなお別の例示的な実施例を表す。
【図９】本発明のなお別の局面による、電子部品におけるリアルタイム・オペレーティング・システムなどのシステムにおける複数のタスクを制御する装置の例示的な実施例を表す。
【図１】
2007531145.tif 000002
【図２】
2007531145.tif 000003
【図３】
2007531145.tif 000004
【図４】
2007531145.tif 000005
【図５】
2007531145.tif 000006
【図６】
2007531145.tif 000007
【図７】
2007531145.tif 000008
【図８】
2007531145.tif 000009
【図９】
2007531145.tif 000010