(57)【要約】多重処理のデータ処理システムのスケジューラによる使用のための、メインメモリ要求および排他的なリソース使用に基づいてタスク優先割り込み点を選択する方法および装置が提供される。該方法および装置はコスト効率がよく、システム一貫性を維持し、特に、追加的な優先割り込み方針を可能にする。該方法および装置においては：一致する諸同期プリミティブは優先割り込み点すなわちサブジョブ境界をまたがない；特定のリソースRkについて、このリソースを使用する（そして同期プリミティブを使ってそれを保護する）すべてのタスクのすべての区間／サブジョブは、すべて優先割り込み可能であるかすべて優先割り込み不可能であるかのいずれかであり、ｉ．すべて優先割り込み可能である場合、同期プリミティブは実行されなければならず、ｉｉ．すべて優先割り込み不可能である場合、同期プリミティブを実行する必要はない；ある部分集合に属する諸タスクへの優先割り込みはこの部分集合の優先割り込み点に限定され、一方では他のすべてのタスクには任意の優先割り込みを許容する；ある部分集合に属する諸タスクへの優先割り込みはそれらのタスクの優先割り込み点に限定され、他の諸タスクへの優先割り込みはそれらのタスクの優先割り込み点の部分集合に限定され一方ではそれらの残りの区間への任意の優先割り込みを許容する。すなわち、本発明は、所定の優先割り込み点のみでの優先割り込みに制限されず、リソースの排他的使用に起因するハングアップを回避する、メインメモリに基づく優先割り込み技術である。
2007511819.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムにおいて複数のタスクのスケジューリングをする方法であって：
前記複数のタスクのそれぞれを、リソースを解放する同期プリミティブで、そこに含まれるリソースを保護する別の同期プリミティブに一致するものがタスク境界をまたぐことのないよう定義し、
ある部分集合の諸タスクを、該諸タスクが少なくとも一つの同じリソースの使用を保護するか否かに依存して優先割り込み可能または優先割り込み不可能として指定し、
前記複数のタスクのそれぞれについて、該タスクによって使われるメモリと該タスクの前記指定された優先割り込み可能性とに基づいて該タスクのサスペンドを規定するサスペンドデータを提供し、
前記複数のタスクのうちの一つを処理し、
前記タスクに関連付けられたサスペンドデータに一致する、前記タスクによって使用されるメモリを示す入力を監視し、
前記サスペンドデータが前記タスクが優先割り込み可能であると規定していれば：
（ｉ）前記監視にかかった入力に基づいて前記タスクをサスペンドし、
（ｉｉ）前記サスペンドされたタスクの保護されているリソースに関する同期プリミティブを前記サスペンドされたタスクが終止するまで執行し、
（ｉｉｉ）前記複数のタスクのうちの別のものを処理する、
ステップを実行する、
ステップを有することを特徴とする方法。
【請求項２】
前記入力がサスペンド要求を示すデータを有することを特徴とする、請求項１記載の方法。
【請求項３】
請求項２記載の方法であって、さらに：
前記複数のタスクに関連付けられた最大メモリ使用量を識別する第一のデータを受け取り、
前記複数のタスクを処理するために利用可能なメモリを識別する第二のデータを受け取り、
前記第一および第二のデータに基づいて、前記諸タスクを処理するために利用可能な十分なメモリがあるかどうかを識別する、
ステップを有しており、前記監視ステップ、サスペンドステップおよび執行ステップがメモリ不足の識別に反応してのみ実行されることを特徴とする方法。
【請求項４】
請求項３記載の方法であって、さらに：
タスクの終止を監視し、
タスク終止に反応して、メモリの利用可能性を識別する前記ステップをタスクの終止に反応したメモリについて繰り返す、
ステップを有することを特徴とする方法。
【請求項５】
残っているタスクを執行するための十分なメモリを識別するのに反応して、前記監視ステップが不必要と見なされることを特徴とする、請求項４記載の方法。
【請求項６】
請求項１記載の方法であって、さらに：
前記複数のタスクに関連付けられた最大メモリ使用量を識別する第一のデータを受け取り、
前記複数のタスクを処理するために利用可能なメモリを識別する第二のデータを受け取り、
前記第一および第二のデータに基づいて、前記諸タスクを処理するために利用可能な十分なメモリがあるかどうかを識別する、
ステップを有しており、前記監視ステップ、サスペンドステップおよび執行ステップがメモリ不足の識別に反応してのみ実行されることを特徴とする方法。
【請求項７】
請求項６記載の方法であって、さらに：
タスクの終止を監視し、
タスク終止に反応して、メモリの利用可能性を識別する前記ステップを繰り返す、
ステップを有することを特徴とする方法。
【請求項８】
残っているタスクを執行するための十分なメモリを識別するのに反応して、前記監視ステップが不必要と見なされることを特徴とする、請求項７記載の方法。
【請求項９】
請求項１記載の方法であって、さらに：
前記複数のタスクに関連付けられた最大メモリ使用量を識別する第一のデータを受け取り、
前記複数のタスクを処理するために利用可能なメモリを識別する第二のデータを受け取り、
前記第一および第二のデータに基づいて、前記諸タスクを処理するために利用可能な十分なメモリがあるかどうかを識別する、
ステップを有しており、前記監視ステップ、サスペンドステップおよび執行ステップがメモリ不足の識別に反応してのみ実行されることを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、さらに：
タスクの終止を監視し、
タスク終止に反応して、メモリの利用可能性を識別する前記ステップを繰り返す、
ステップを有することを特徴とする方法。
【請求項１１】
残っているタスクを執行するための十分なメモリを識別するのに反応して、前記監視ステップが不必要と見なされることを特徴とする、請求項１０記載の方法。
【請求項１２】
リソースを解放する同期プリミティブで、そこに含まれるリソースを保護する別の同期プリミティブに一致するものがタスク境界をまたぐことがないように定義される複数のタスクを実行するよう構成されているデータ処理システムであって前記諸タスクを執行するのに使用する特定の量のメモリへのアクセスを有するデータ処理システムにおいて使用するためのスケジューラであって、当該スケジューラが：
あるタスクに関係付けられている最大メモリ使用量、該タスクの排他的リソース使用および該タスクの優先割り込み可能性を識別するデータを受け取るよう構成されており、同じリソースの使用を保護している前記複数のタスクのある部分集合のタスクがすべて優先割り込み可能または優先割り込み不可能の一方として識別されるようなデータ受信器と、
前記受け取られたデータに基づいて前記諸タスクを執行するのに十分なメモリがあるかどうかを識別するよう構成されている評価器と、
少なくとも一つのタスクを該タスクの執行の間のサスペンドのために選択するよう構成されており、該サスペンドが該タスクによる特定のメモリ使用量および該タスクが優先割り込み可能であることと符合するような選択器、
とを有しており、
前記評価器が前記複数のタスクを実行するのにメモリが不足していると識別するのに反応して、
・前記選択器が、タスクの特定のメモリ使用量およびタスクの優先割り込み可能性ならびに当該データ処理システムに利用可能な特定のメモリ量に基づいて、少なくとも一つのタスクをサスペンドのために選択し、
・前記スケジューラが、前記少なくとも一つの選択されたタスクの執行を、該タスクが前記特定のメモリを使用しており該タスクが優先割り込み可能であることに反応してサスペンドし、
・前記評価器が、前記サスペンドされた少なくとも一つのタスクの保護されたリソースに関する同期プリミティブのその後の執行を、前記サスペンドされた少なくとも一つのタスクが終止するまで監督する、
ことを特徴とするスケジューラ。
【請求項１３】
前記評価器がタスクの終止を監視し、タスクが終止するのに反応して残りのタスクを執行するために十分なメモリがあるかどうかを識別するようさらに構成されていることを特徴とする、請求項１２記載のスケジューラ。
【請求項１４】
前記評価器が残りのタスクを執行するための十分なメモリを識別するのに反応して、前記選択器が前記選択された少なくとも一つのタスクの選択を解除するよう構成されていることを特徴とする、請求項１３記載のスケジューラ。
【請求項１５】
複数のタスクを執行するよう構成されたデータ処理システムであって、前記複数のタスクのそれぞれは、同期プリミティブでそこに含まれる別の同期プリミティブに一致するものがタスク境界をまたぐことがないように定義されており、当該データ処理システムが：
あるタスクの執行の間に命令およびデータを保持するよう構成されたメモリと、
あるタスクに関連付けられている最大メモリ使用量を識別するデータと、前記タスクの優先割り込み可能性を指定するデータとを受け取るよう構成された受信手段と、
前記受け取られたデータに基づいて前記諸タスクを執行するのに十分なメモリがあるかどうかおよび前記諸タスクが優先割り込み可能かどうかを識別するよう構成されている評価手段と、
前記諸タスクの執行を、前記評価手段から受け取られる入力に基づいてスケジューリングするよう構成されているスケジューラとを含んでおり、
前記複数のタスクを執行するためのメモリが不十分であることを識別するのに反応して、
前記スケジューラが少なくとも一つのタスクの執行を該タスクによるメモリ使用量、該タスクによる排他的リソース使用および該タスクの優先割り込み可能性に依存してサスペンドし、前記サスペンドされた少なくとも一つのタスクの保護されたリソースに関する同期プリミティブのその後の執行を、前記サスペンドされたタスクが終止するまで監督するよう構成されていることを特徴とする、データ処理システム。
【請求項１６】
前記複数のタスクのある部分集合が、前記部分集合の複数のタスクが同じリソースの使用を保護しているか否かに依存して優先割り込み可能または優先割り込み不可能と決定されることを特徴とする、請求項１５記載のデータ処理システム。
【請求項１７】
データをデータ処理システムに送信する方法であって、当該方法は：
そこに含まれる別の同期プリミティブに一致するリソースの使用を保護する同期プリミティブがタスク境界をまたがないようにタスクを定義し、
すべてのタスクを、該諸タスクが少なくとも一つの同じリソースの使用を保護しているか否かに依存して優先割り込み可能または優先割り込み不可能として定義し、
タスクの処理においてデータ処理システムによって使用するためのデータを送信し、
処理の間のメモリ使用量と優先割り込み可能性とに基づいてタスクのサスペンドを指定するサスペンドデータを送信する、
ことを有しており、
前記データ処理システムが：
前記タスクに関連付けられているサスペンドデータに一致する前記タスクのメモリ使用量を示す入力を監視し、
前記サスペンドデータが前記タスクが優先割り込み可能であると規定していれば、前記監視にかかった入力に基づいて前記タスクの処理をサスペンドし、その後、前記サスペンドされたタスクによって保護されているリソースに関する同期プリミティブを前記サスペンドされたタスクが終止するまで執行する、
ことを有するプロセスを実行するよう構成されていることを特徴とする方法。
【請求項１８】
前記サスペンドデータが、前記タスクに関連付けられている最大メモリ使用量、前記タスクに関連付けられている排他的リソース使用および前記タスクの優先割り込み可能性を含むことを特徴とする、請求項１７記載の方法。
【請求項１９】
前記サスペンドデータが、前記タスクの処理をサスペンドできる少なくとも一つの点を、前記タスクのメモリ使用量、前記タスクの排他的リソース使用および前記タスクの優先割り込み可能性に基づいて識別することを特徴とする、請求項１７記載の方法。
【請求項２０】
前記タスクが複数のサブジョブを有しており、前記タスクの処理をサスペンドできる少なくとも一つの点を識別する前記データが、優先割り込み可能なそのようなサブジョブのおのおのに対応することを特徴とする、請求項１９記載の方法。
【請求項２１】
前記サスペンドデータが、前記タスクに関連付けられた最大メモリ使用量を識別するデータおよび前記タスクに関連付けられた排他的リソース使用を含むことを特徴とする、請求項１９記載の方法。
【請求項２２】
前記タスクが複数のサブジョブを有しており、前記タスクの処理をサスペンドできる少なくとも一つの点を識別する前記データが、優先割り込み可能なそのようなサブジョブのおのおのに対応することを特徴とする、請求項２１記載の方法。
【請求項２３】
データ処理システムにおいて使うための、タスクを構成する方法であって、当該方法が当該タスクに関連付けられたメモリ使用量、当該タスクの排他的リソース使用および当該タスクの優先割り込み可能性に基づいて当該タスクのサスペンドを指定するサスペンドデータを当該タスクに関連付けることを含んでおり、前記データ処理システムが複数のタスクに関してあるプロセスを実行するよう構成されており、該プロセスが：
当該タスクを、そこに含まれる別の同期プリミティブに一致する同期プリミティブがタスク境界をまたがないように定義し、
当該タスクに関連付けられたサスペンドデータに一致する、前記タスクのメモリ使用量を示す入力を監視し、
前記サスペンドデータが当該タスクが優先割り込み可能であると規定していれば、
・前記監視にかかった入力に基づいて前記タスクの処理をサスペンドし、
・その後、前記サスペンドされた少なくとも一つのタスクの排他的使用リソースに関する同期プリミティブを前記タスクが終止するまで執行する、
ことを有することを特徴とする方法。
【請求項２４】
処理システムをして、請求項１記載の方法を実行せしめるよう構成されている命令のセットを有することを特徴とする、メモリに保存されたコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はリソース管理の方法および装置に関する。それはリアルタイムシステムにリソース管理に特に好適であるがそれに限られるものではない。
【背景技術】
【０００２】
メモリ管理はリソース管理の決定的な側面であり、その使用を最適化するためにさまざまな方法が開発されてきた。非特許文献1,2,3で議論されている好ましい優先割り込み点（preemption  points）を扱う方法は、優先割り込み点の使用を特にリアルタイムシステムにおいてメインメモリの管理にまで一般化することによってデータ処理システムの効率を改善する手段として提案されている非特許文献4。任意の時点においてタスクの実行中に該タスクに優先割り込みするのに代わる、メモリ管理へのこのアプローチにおいては、タスクは好ましくは、そのメモリ使用に基づいて専用の優先割り込み点においてのみ優先割り込みされる。
【０００３】
以下の記述では、タスクのサスペンドをタスク優先割り込みあるいはタスクへの優先割り込みと称し、「タスク」の用語はメモリ、CPU、I/O機器などといったシステムリソースを自らの立場で求めて競合することのできる実行単位を表すものとして用いる。タスクとは、連続して実行される一連のジョブと見なすことができ、ジョブのそれぞれは一つまたは複数のサブジョブからなる。たとえば、タスクは「ビデオストリームを多重化解除する」で、はいってくるストリームを読み込んで、該ストリームを処理し、対応するデータを出力することを含みうる。これらのステップははいってくる各データストリームに関して実行されるので、単一のストリームに関する読み込み、処理および出力が一つのジョブの実効に対応する。よって、読み込んで処理すべきデータの複数の束があるとき、ジョブはその数に対応する回数だけ実行される。サブジョブは、ジョブの機能的な構成要素に関係するものと考えることができる。
【０００４】
データ処理システムにおいて複数のタスクのスケジューリングをする既知の方法は、タスクの各サブジョブがサスペンドデータと呼ばれるサスペンド基準の集合を有しており、それがメモリ使用量に基づいて処理優先割り込み点とサブジョブの対応するサスペンド条件とを指定する非特許文献4,5。データ処理システムによって使用されるメモリ量は、よって、こうした優先割り込み点を通じて、前記サスペンドデータによって間接的に制御される。前記サスペンドデータは、あるジョブの実行においてこれらの優先割り込み点において要求されるメモリ量を指定するのである。
【０００５】
よって、これらの優先割り込み点は、メモリ不足によるデータ処理システムのクラッシュを避けるために利用することができる。リアルタイムタスクが複数のサブジョブからなるものとして特徴付けられるとき、その優先割り込み点は好ましくは、あるいは典型的には、当該タスクのサブジョブの境界と一致する。しかし、サブジョブの途中でタスク自身が自らをサスペンドさせることのないよう、注意を払う必要がある。実施形態によっては、優先割り込み不可能なサブジョブのこのようなサスペンドは、ハングアップに、あるいはメモリの過大消費につながりうる。
【０００６】
あるタスクの各サブジョブに関連付けられたサスペンドデータに従う、タスクのメモリ使用量を示すデータは、たとえば、スケジューリング解除イベントを要求するコード行を通じてタスク中に埋め込まれることができる。スケジューリング解除イベントによって当該タスクの処理において優先割り込み点に到達した、すなわちサブジョブの境界に到達したことを明示するのである。つまり、あるタスクのサブジョブの開始点の集合が、そのタスクの優先割り込み点の集合をなす。タスクτiのj番目の優先割り込み点Pi,jを特徴付けるのは、その優先割り込み点そのものに関係した情報およびそれに続く、該j番目の優先割り込み点と次の優先割り込み点つまり(j+1)番目の優先割り込み点との間の優先割り込み不可能なサブジョブ区間に関係する情報である。
【０００７】
ランタイムには、タスクは制御オペレーティングシステムにいつ優先割り込み点に着くかを、たとえばいつサブジョブを開始し、サブジョブを切り換え、そしてサブジョブを完了するかを通知し、オペレーティングシステムはいつどこでタスクの実行が優先割り込みされるかを決定する。理想的には、優先割り込みは、優先割り込み点においてでも、あるいはタスク実行中の他の任意の点においてでも生起しうる。
【０００８】
しかし、上述したハングアップの問題に加えて、優先割り込みの選択のそのような柔軟性は、以下の条件のもとで一貫性を犠牲にして得られるものである：
（１）ある部分集合のタスクへの優先割り込みは該部分集合の優先割り込み点に限定され、一方では他のすべてのタスクへは任意の優先割り込みを許容する；
（２）ある部分集合のタスクへの優先割り込みはそれらのタスクの優先割り込み点に限定され、他のタスクへの優先割り込みはそれらのタスクの優先割り込み点の部分集合に限定され一方ではそれらの残りの区間への任意の優先割り込みを許容する。
優先割り込み点をもつタスクの区間に任意に優先割り込みがされる場合、こうしたサブシステムの予測可能性が劣化させられることがありうる。構成要素の設計、解析および試験はタスクの諸区間が優先割り込み点においてのみ優先割り込みされるという想定に基づいて行われているからである。結果として得られるシステムは、タスク区間の任意の優先割り込みが行われる場合には、リソースへの排他的なアクセスが保証されないので、一貫しないものとなりうる。
【０００９】
システムの一貫性を損なわない、メインメモリ要求に基づく従来技術の優先割り込み点アプローチは、必然的にすべてのタスクの優先割り込みを優先割り込み点に限定する。当技術分野において知られているように、コンポーネント（たとえば一つまたは複数のタスクを構成しうるソフトウェアコンポーネント）は、当該コンポーネントが定義する属性、機能もしくは方法およびイベントを有するプログラム可能なインターフェースを有することができる非特許文献6。議論のため、タスクτiには、最低限でも当該タスクによって要求される図１に示すようなメインメモリデータMPi,j１０１ｂを含むインターフェース１００が付随しているものと想定される。さらに、優先割り込み点は、一致する諸同期プリミティブ（matching  synchronization  primitives）がサブジョブの境界（すなわち優先割り込み点）をまたぐことはないように定義されていると想定される。
【００１０】
議論のため、タスクは周期的でリアルタイムであり、周期Tおよび位相F（0≦F＜T）によって特徴付けられるものと想定される。これはタスクがサブジョブの系列を有しており、同じ系列が周期的に反復され、そのそれぞれはn＝0,...,Nとして時刻F+nTにリリースされるということを意味している。単なる例として挙げるが、図２に示したように、セットトップボックス２００は３つのタスクを実行する――（１）ユーザーインターフェース２０５上にメニューを表示し、（２）コンテンツプロバイダー２０３からテキスト情報を取得し、（３）いくつかのビデオ信号を処理する――ものと想定される。そしてこれら３つのタスクのおのおのは、複数のサブジョブを有するものと想定される。呈示の簡単のため、サブジョブはシーケンシャルに実行されるものと想定される。
【００１１】
これらのサブジョブの少なくともいくつかは優先割り込みされることができ、優先割り込みされることのできるそれらのサブジョブの間の境界は優先割り込み点を与えるもので、表１にまとめられている。
【００１２】
【表１】
2007511819.tif 000003
図３も参照すると、各タスクについて、サスペンドデータ１０１は：優先割り込み点（preemption-point）Pi,j３０１に関係する、優先割り込み点において要求される最大メモリ量MPi,j３０２といった情報と、相続く優先割り込み点の間の区間（interval）Ii,j３０３に関係する、優先割り込み点内の区間において要求される最悪ケースのメモリ量MIi,j３０４といった情報とを含む（iはタスクτiを表し、jは優先割り込み点を表す）。
【００１３】
より具体的には、サスペンドデータ１０１は、次のものを指定するデータを有している。
１．タスクτiの優先割り込み点j（Pi,j）１０１ａ；
２．タスクτiの、該タスクの優先割り込み点jにおける最大メモリ要求MPi,j１０１ｂ（ここで、1≦j≦m(i)）；
３．タスクτiのサブジョブjに対応する相続く優先割り込み点jおよび(j+1)の間の区間Ii,j１０１ｃ（ここで、1≦j≦m(i)）；
４．タスクτiの区間jにおける、そのタスクτiの最大（すなわち、最悪ケースの）メモリ要求MIi,j１０１ｄ（ここで、1≦j≦m(i)）。
【００１４】
表２は、現在の例についてのサスペンドデータ１０１を示している（各タスクはその独自のインターフェースをもち、現在の例では、第一のタスクτ1に対応するサスペンドデータ１０１は表２の第１行のデータをなし、第二のタスクτ2に対応するサスペンドデータ１０１は表２の第２行のデータをなす、など）。
【００１５】
【表２】
2007511819.tif 000004
セットトップボックス２００が1.5メガバイトのメモリを具備しているとする。通常の、すなわちメモリに基づかない優先割り込み条件のもとでは、このセットトップボックス２００は以下のように振る舞う。
【００１６】
ここで図４を参照すると、プロセッサ４０１は、何らかの種類のタイムスライシングまたは優先度に基づく優先割り込みに従ってタスクのスケジューリングを行うよう期待されうる。これはすなわち、３つのタスクすべてが同時並行して、すなわち実効的に同時に走るということを意味している。したがって、各タスクがその最もメモリ集約的なサブジョブを同時に走らせるようスケジューリングされうることが可能である。これら３つのタスクの最悪ケースのメモリ要求MPは次式によって与えられる：
【００１７】
【数１】
2007511819.tif 000005
タスクτ1、τ2、τ3にとってMPはこのように、τ1の最大メモリ要求（つまりMI1,1）と、タスクτ2の最大メモリ要求（つまりMI2,2）と、タスクτ3の最大メモリ要求（つまりMI3,2）とを合算したものである。これらの最大メモリ要求は表２でボールドで示された項目によって示されている：
MP＝0.7+0.8+0.3＝1.8メガバイト
これはセットトップボックス２００にとって利用可能なメモリを0.3メガバイト超過しており、よって何らの予防手段も講じていなければ、これらのサブジョブが同時に処理される場合、セットトップボックス２００はクラッシュする。
【００１８】
ここで図５を参照して、タスクはスケジューリング・アルゴリズムに従ってスケジューリングされており、データ構造は各タスクτiについてそのタスクが生成されたのちは維持されるものとする。さらに、スケジューラ５０１が従来の優先度に基づく優先割り込みスケジューリング・アルゴリズムを用いているとする。これは本質的には、どの時点においても、現在実行中のタスクがシステム中の実行準備のできたすべてのタスクのうちで最高の優先度をもつタスクであることを保証するというものである。当技術分野において知られているように、スケジューリングの振る舞いは、実行中のタスクまたは実行準備のできたタスクについての優先割り込みを選択的に有効にしたり無効にしたりすることによって修正できる。
【００１９】
タスクマネージャ５０３は、新たに受領されたタスクに対応するサスペンドデータ１０１を受領し、優先割り込みが要求されているかどうかを評価し、要求されていればこの新たに受領された情報をスケジューラ５０１に渡して優先割り込みを要求する。タスクの詳細が表２に定義したようになっているとし、タスクτ1（そしてτ1のみ）が現在処理されていて、スケジューラが初期にはメモリに基づく制約がないモードで動作していると想定する。
【００２０】
ここでタスクマネージャ５０３がタスクτ2を受領したとする。該タスクマネージャ５０３はそのインターフェースInt2１００からサスペンドデータ１０１を読み込み、スケジューラ５０１がメモリに基づく優先割り込みに従ってはたらいているかどうかを識別する。この例ではそうではないので、タスクマネージャ５０３はスケジューラ５０１がメモリに基づく優先割り込みに移行する必要があるかどうかを評価する。したがって、このことはタスクマネージャ５０３が現在実行中のタスクすべて（この例ではタスクτ1）に対応する最悪ケースのサスペンドデータをサスペンドデータ記憶５０５から取得し、式（１）を評価し、その評価された最悪ケースのメモリ要求を利用可能なメモリリソースと比較することに関わる。表２で導入された例を続けると、τ1およびτ2についての式（１）は：
【００２１】
【数２】
2007511819.tif 000006
これは利用可能なメモリにちょうど等しいので、スケジューラ５０１の動作のモードをメモリに基づく優先割り込みに変更する必要はない（すなわち、スケジューラをメモリ使用に基づいて制約する必要はない）。よって、スケジューラ５０１がタスクτ1とタスクτ2との間で切り替わることになっていたとする場合――たとえばタスクτ2の実行時間制約条件を満たすために――、すなわち両方のタスクが実効的に同時にメモリに存在するとする場合にも、当該プロセッサは利用可能なよりも多くのメモリをアクセスすることは決してない。
【００２２】
次に、タスクτ1およびタスクτ2が完了する前に、もう一つのタスクτ3が受領される。タスクマネージャ５０３は該タスクτ3に対応するインターフェースInt3からサスペンドデータ１０１を読み込み、スケジューラ５０１がメモリに基づく優先割り込みに移行する必要があるかどうかを評価する。スケジューラ５０１がタスクτ1およびτ2をマルチタスクしているとすると、３つのタスクすべてについての最悪ケースのメモリ要求は今では次のようになる：
【００２３】
【数３】
2007511819.tif 000007
これは利用可能メモリを超過するので、タスクマネージャ５０３は、サスペンドデータ記憶５０５から３つのタスクすべてについてのメモリ使用量データMPi,j、MIi,j１０１ｂ、１０１ｄを要求して取得し、この取得されたメモリ使用量データに基づいて３つのタスクすべてを実行するための十分なメモリリソースがあるかどうかを評価する。これは次の式を評価することを通じて確かめることができる：
【００２４】
【数４】
2007511819.tif 000008
このメモリ要求は利用可能メモリより低く、タスクが優先割り込み点でのみ優先割り込みされることを前提とすれば３つのタスクすべてが同時並行して実行できるということになる。
【００２５】
したがって、タスクマネージャ５０３は、各タスクに、指定された優先割り込み点MPi,jにおいてスケジューリング解除命令をスケジューラ５０１に送信するよう指示することによって「メモリに基づく優先割り込みモード」を呼び出す。このモードでは、スケジューラ５０１は各タスクが一つの優先割り込み点から次の優先割り込み点まで優先割り込みなしで走ることを許容するが、どの時点においても、同時に優先割り込み点以外の点にあることができるのは高々一つのタスクのみであるという制約条件が付く。新たに到着したタスクが優先割り込み点において開始されると想定すると、スケジューラ５０１はこの条件が現在走っている諸タスクについて成立することを保証し、よって一つのタスクを除いたすべてが優先割り込み点にあるよう制約する。
【００２６】
こうして、既知のメモリに基づく優先割り込みモードにおいては、スケジューラ５０１がタスクに優先割り込みすることが許容されるのはタスクのメモリ優先割り込み点において（すなわち、各タスクからのメモリに基づく優先割り込み点におけるスケジューリング解除要求に反応して）のみである。あるタスクが他のタスクによって保持されているリソースの排他的な使用のために待とうとして自らをサスペンドした場合にはハングアップの可能性が残っている。これは、前記他のタスクが前記リソースへのロックを保持したまま優先割り込みされたときに生じうる。これは、タスクが優先割り込み点においてはリソースへのロックを保持しないこと、換言すれば、あるリソースを保護する諸同期プリミティブが優先割り込み点すなわちサブジョブ境界をまたがないよう保証することによって防止できる。
【００２７】
タスクの一つが終止した場合、終止するタスクはタスクマネージャ５０３に自らが終止することを通知し、タスクマネージャ５０３は式（１）を評価する。最悪ケースの（前記タスクの除去を考慮に入れての）メモリ使用量がスケジューラ５０１に利用可能であるより低い場合には、タスクマネージャ５０３はメモリに基づく優先割り込みを取り消し、これによりシステムが外部イベントに対してよりすばやく反応できる（プロセッサがもはやサブジョブの期間中「ブロック」されないので）ようにするという恩恵が得られる。一般に、タスクの終止は典型的にはその環境によって引き起こされる。引き起こす要因はたとえば、ユーザーによるチャネルの切り換えまたはデータストリーム中における適用エンコード方式の変更（別の種類のデコードを要求する）である。これはすなわち、タスクマネージャ５０３および／またはスケジューラ５０１はタスクの終止を認識すべきであり、おそらくはタスクに終止を指示しさえするということを意味している。
【００２８】
呼び出されたとき、メモリに基づく優先割り込み制約条件が義務的であることを注意しておくべきである。
【００２９】
タスクはソフトウェアタスクとして述べてきたが、タスクはハードウェアで実装されることもできる。典型的には、ハードウェアデバイス（ハードウェアタスクとして振る舞う）はソフトウェアタスクによって制御され、該ソフトウェアタスクが前記ハードウェアデバイスによって要求される（最悪ケースの）メモリを割り当て、その後前記ハードウェアタスクに実行を指示する。ハードウェアタスクは完了したときに前記ソフトウェアタスクに通知し、該ソフトウェアタスクがその後前記メモリの割り当てを解除する。よって、制御ソフトウェアタスクを有することによって、ハードウェアタスクは単に上記したようにして扱うことができる。
【００３０】
以下の文献は本文中での対応する文献番号を裏付けるものであり、よってここに参照によってあたかもここに全文が記載されているかのごとくに含められる。
【非特許文献１】R.  Gopalakrishnan  and  G.M.  Parulkar,  “Bringing  Real-Time  Scheduling  Theory  And  Practice  Closer  For  Multimedia  Computing,”  In:  Proc.  ACM  Sigmetrics  Conf.  on  Measurement  &  modeling  of  computer  systems,  pp.1-12,  May  1996.
【非特許文献２】S.  Lee,  C.-G.  Lee,  M.  Lee,  S.L.  Min,  and  C.-S.  Kim,  “Limited  Preemptible  Scheduling  to  Embrace  Cache  Memory  In  Real-Time  Systems,  In:  Proc.  ACM  Sigplan  Workshop  on  Languages,  Compilers  and  Tools  for  Embedded  Systems  (LCTES),  LNCS-1474,  pp.51-64,  June  1998.
【非特許文献３】J.  Simonson  and  J.H.  Patel,  “Use  Of  Preferred  Preemption  Points  In  Cache-Based  Real-Time  Systems,”  In:  Proc  IEEE  International  Computer  Performance  and  Dependability  Symposium  (IPDS'95),  pp.316-325,  April  1995.
【非特許文献４】R.J.  Bril  and  D.J.C.  Lowet,  “A  Method  For  Handling  Preemption  Points,”  Philips  Research  Laboratories,  Eindhoven,  The  Netherlands,  Internal  IST/IPA  document,  30  September  2002.
【非特許文献５】R.J.  Bril  and  D.J.C.  Lowet,  “A  Method  For  Handling  Preemption  Points―Remarks―,”  Philips  Research  Laboratories,  Eindhoven,  The  Netherlands,  Internal  IST/IPA  document,  31  October  2002.
【非特許文献６】Clemens  Szyperski,  Component  Software―Beyond  Object-oriented  Programming,  Addison-Wesley,  ISBN  0-201-17888-5,  1997.
【発明の開示】
【発明が解決しようとする課題】
【００３１】
前記のアプローチは、タスクに優先割り込みをするのが優先割り込み点に制限されているため、いつもサブジョブ優先割り込みの最良の選択を許容するとは限らず、そのためいつも最高のシステム高速化を得られるとは限らず、同期プリミティブを正しく扱うよう注意を払わなければハングアップを起こすこともありうる。
【課題を解決するための手段】
【００３２】
本発明は、メインメモリ要求に基づく優先割り込み点の選択のための、よりコスト効率がよく、システム一貫性を維持し、とりわけ追加的な優先割り込み方針を可能にする方法および装置を提供する。該方法および装置においては：
１．一致する諸同期プリミティブはサブジョブ境界をまたがない；
２．特定のリソースRkについて、このリソースを使用する（そして同期プリミティブを使ってそれを保護する）すべてのタスクのすべての区間／サブジョブは、すべて優先割り込み可能であるかすべて優先割り込み不可能であるかのいずれかであり、
ｉ．すべて優先割り込み可能である場合、同期プリミティブは実行されなければならず、
ｉｉ．すべて優先割り込み不可能である場合、同期プリミティブを実行する必要はない；
３．ある部分集合に属する諸タスクへの優先割り込みはこの部分集合の優先割り込み点に限定され、一方では他のすべてのタスクには任意の優先割り込みを許容する；
４．ある部分集合に属する諸タスクへの優先割り込みはそれらのタスクの優先割り込み点に限定され、他の諸タスクへの優先割り込みはそれらのタスクの優先割り込み点の部分集合に限定され一方ではそれらの残りの区間への任意の優先割り込みを許容する。
すなわち、本発明は、所定の優先割り込み点での優先割り込みに制限されず、従来技術の優先割り込み点アプローチのハングアップの問題を回避する、メインメモリに基づく優先割り込み技術である。
【発明の効果】
【００３３】
本発明は、上記したように従来技術のメモリに基づく優先割り込み点技術に関する問題を解決するばかりでなく、以下の効果を有する。システム一貫性を保証しつつ任意に諸区間に優先割り込みができることによって、メモリをＣＰＵサイクルとトレードすることを可能にする。すなわち、
・システムが諸区間に優先割り込みをしないときに同時並行制御を呼び出す必要を解消する；
・タスク集合が優先割り込みなしではスケジューリング不可能であるとき諸区間への優先割り込みを許容する。
従来技術のメモリに基づく優先割り込み点技術に対する本発明の利点は、ブロッキングの二つの含意を考えることによってさらに説明できる。第一に、ブロッキングはブロッキングをしているタスクの最悪ケースの応答時間を低減させうる（そのタスクの最後のサブジョブに関わる場合）。第二に、より優先度の高い諸タスクの最悪ケースの応答時間を増加させうる（そのブロッキング時間が、ブロッキングされるタスクより低い優先度をもつすべてのタスクのうちで最大のブロッキング時間である場合）。したがって、ある区間への優先割り込みは、優先割り込みを受けるタスクの最悪ケースの応答時間を増加させ、ブロッキングするタスクよりも優先度の高い諸タスクの最悪ケースの応答時間を減少させうる。したがって、特定の状況では、ある区間への優先割り込みはタスク集合をスケジューリング可能にしうる。
【００３４】
上記のことを含む本発明のさまざまな利点は、以下の、付属の図面に示されるような好ましい諸実施形態のより詳細な記述から明らかであろう。図面においては、さまざまな図を通じて同じ参照符号は同じ部分を指す。
【発明を実施するための最良の形態】
【００３５】
通常の当業者は以下の記述が解説のために与えられるものであって限定のためではないことを理解するであろう。技術者は本発明の精神および付属の特許請求の範囲内にはいる多くの変形があることを理解するものである。既知の機能および動作の無用な詳細は、本発明を埋没させないよう、本記述からは省略されることがある。
【００３６】
デジタルテレビ、デジタル的に改善したアナログテレビおよびセットトップボックス（STB:  set-top  box）といった高容量エレクトロニクス（HVE:  high  volume  electronic）消費者向けシステムは、コスト効率と堅牢さを保ったままリアルタイムサービスを提供しなければならない。消費者向け製品はその性質上、リソースが大幅に制約を受けている。結果として、堅牢性のようなHVE消費者向けシステムの典型的な品質を保ち、厳格なタイミング要求を満たしながら、利用可能なリソースを非常に効率的に使用することが必要になる。堅牢性に関しては、たとえばテレビが「システムを再起動してください」といったメッセージを出して不具合を起こすことは誰も想定していないということである。
【００３７】
HVE消費者システムにおけるメディア処理のかなりの部分が、複数の同時並行データストリームを扱うオンボードソフトウェアにおいて実装されており、特にマルチタスク環境においてはメインメモリのようなシステムリソースを非常に効率的に管理しなければならない。リアルタイムリソース管理を要求するHVE消費者システムの例としてセットトップボックスを考えよう。従来では、図２に示されるように、セットトップボックス２００はテレビ２０１のための入力をコンテンツプロバイダー２０３（サーバーまたはケーブル）から、およびユーザーインターフェース２０５から受け取る。ユーザーインターフェース２０５は、ユーザー制御されるリモート装置２０２から信号を受け取るためのリモコンインターフェース、たとえばハンドヘルドの赤外線リモート送信機を有している。セットトップボックス２００は、アンテナおよびケーブルテレビ接続口のうちの少なくとも一つから少なくとも一つのデータストリームを受け取り、該データストリームを処理するか該データストリームをテレビ２０１に転送するかのうちの少なくとも一つを実行する。ユーザーは前記少なくとも一つのデータストリームがテレビ２０１上に表示されるのを見、表示されている内容に基づいてユーザーインターフェース２０５を通じて選択を行う。セットトップボックス２００はユーザーの選択入力を処理し、この入力に基づいて前記ユーザー入力をコンテンツプロバイダー２０３に、セットトップボックス２００およびその機能を識別するその他の情報とともに送信しうる。
【００３８】
図４は典型的なセットトップボックス２００の例示的なシステム４００の単純化したブロック図を示している。典型的なセットトップボックス２００は、該セットトップボックス２００の全体としての動作を制御するための制御プロセッサ４０１を含みうる。制御プロセッサ４０１はテレビチューナー４０３、メモリ４０５、長期記憶装置４０６、通信インターフェース４０７およびリモートインターフェース４０９に結合されている。テレビチューナー４０３は伝送線４１１を通じてテレビ信号を受信し、これらの信号はアンテナ（図示せず）およびケーブルテレビ接続口（図示せず）のうちの少なくとも一つから発するものでよい。制御プロセッサ４０１はユーザーインターフェース２０５を管理し、データ、オーディオおよびビデオ出力をテレビ２０１に線４１３を通じて提供する。リモートインターフェース４０９はリモコンから無線接続４１５を通じて信号を受信する。通信インターフェース４０７はセットトップボックス２００とウェブサーバーのような少なくとも一つのリモート処理システムとの間でデータ路４１７を通じたインターフェースとなる。通信インターフェース４０７は、電話モデム、統合サービスデジタル通信網（ISDN）アダプター、デジタル加入者線（xDSL）、ケーブルテレビモデムおよびその他任意の好適なデータ通信デバイスのうちの少なくとも一つである。図４の例示的なシステム４００は説明のためだけのものである。記述では特定のセットトップボックス２００を記述するのに一般的に使われる用語を使用することもありうるが、本記述および概念は、図４に示したものとは異質のその他の制御プロセッサにも等しくあてはまるものである。
【００３９】
ある好ましい実施形態では、制御プロセッサ４０１はセットトップボックス２００の制御に関係する複数のリアルタイムタスクを処理するよう構成されている。そうしたタスクには、チャンネルの変更、ユーザーインターフェース２０５に表示されるメニューオプションの選択、はいってくるデータストリームのデコード、はいってくるデータストリームを長期記憶装置４０６を使った記録およびそれらの再生などが含まれる。セットトップボックスの動作は、セットトップボックス２００の特性、線４１１を通じたはいってくるビデオ信号、ユーザーインターフェース２０５を通じたユーザー入力およびその他の任意の補助的な入力に基づいてこれらのリアルタイム制御タスクによって決定される。
【００４０】
図１に示されているように、制御プロセッサ４０１によって制御される各リアルタイムタスクτiは、少なくとも一つのサブジョブまたは優先割り込み点Pi,jを有し、それは対応するサスペンドデータの集合をもち、そのデータは要求されるメモリの最大量Mki,j１０１を含んでいる。すなわち、前記少なくとも一つのタスクτiのサブジョブの開始点Pi,jの集合は、そのタスクの優先割り込み点Pi,jの集合をなす。タスクτiのj番目の優先割り込み点Pi,jを特徴付けるのは、その優先割り込み点そのものに関係した情報およびそれに続く、該j番目の優先割り込み点と次の優先割り込み点つまり(j+1)番目の優先割り込み点との間のプログラム区間に関係する情報である。ある好ましい実施形態では、以下のアプローチによってプロセッサは、前記の続くプログラム区間Ii,jの間、その区間の間の任意の点で処理に優先割り込みできるかどうかを判定できる：
１．一致する諸同期プリミティブはサブジョブ境界をまたがない；
２．特定のリソースRkについて、このリソースを使用する（そして同期プリミティブを使ってそれを保護する）すべてのタスクのすべての区間／サブジョブは、すべて優先割り込み可能であるかすべて優先割り込み不可能であるかのいずれかであり、
ｉ．すべて優先割り込み可能である場合、同期プリミティブは実行されなければならず、
ｉｉ．すべて優先割り込み不可能である場合、同期プリミティブを実行する必要はない；
３．ある部分集合に属する諸タスクへの優先割り込みはこの部分集合の優先割り込み点に限定され、一方では他のすべてのタスクには任意の優先割り込みを許容する；
４．ある部分集合に属する諸タスクへの優先割り込みはそれらのタスクの優先割り込み点に限定され、他の諸タスクへの優先割り込みはそれらのタスクの優先割り込み点の部分集合に限定され一方ではそれらの残りの区間への任意の優先割り込みを許容する。
より具体的には、優先割り込み点を扱うとき、以下のステップに従う必要がある。
・ある特定のリソースのすべての保護プリミティブが同じサブジョブ内にはいることを保証する（すなわち、一対のプリミティブを含んでいる決定的な区間がサブジョブ境界をまたがない）
・新規のタスクが開始されるとき、タスクマネージャ／スケジューラは、どの区間が優先割り込み可能に、あるいは優先割り込み不可能に設定されているかを決定するとき、保護されたリソースを考慮に入れなければならない。
【００４１】
上記の一つの自明な実装は、同期プリミティブを優先割り込み点と一致させることである。その欠点は、同期プリミティブがコード中で頻繁に呼び出されるとき、多数の小さな区間が導入されるということである。
【００４２】
より一般的な実装は次のようになる。ある区間のサスペンドデータに、その区間内で保護されているリソースkの識別子Rkが追加される。スケジューラ／タスクマネージャはこの情報を使って、リソースRkを使っているすべての区間が優先割り込み可能か、すべて優先割り込み不可能かのいずれかであることを保証することができる。
１．ある好ましい実施形態では、市販の既成の（COTS:  commercial-off-the-shelf）リアルタイムオペレーティングシステム（RTOS:  real-time  operating  system）の上にかぶさるミドルウェア層が諸タスクのメモリ使用量およびスケジューリング可能性に関する試験の機能を実装する。この層はまた、どの区間が優先割り込みのために選択されるかをも決定する。
タグRkをもつ区間で優先割り込みのために選択されているものがあるときは常に、Rkをパラメータとしてもつあらゆるシステムコールは前記ミドルウェア層によってRTOSに渡される。タグRkをもつ区間が一つも優先割り込みのために選択されていないときには常に、前記ミドルウェア層は前記システムコールを無視してよい（すなわち、該システムコールからすぐに戻る）。
【００４３】
ある好ましい実施形態では、本方法は、それぞれのタスクをプリミティブの対がタスク（または該タスクのサブジョブ）境界をまたぐことのないよう定義し、ある部分集合の諸タスクを該諸タスクが少なくとも一つの共通リソースの使用を保護するか否かに依存して優先割り込み可能または優先割り込み不可能として指定し、複数のタスクのそれぞれに関連付けられた、最大メモリおよび排他的リソースRk使用を識別する第一のデータを受け取り、前記複数のタスクを処理するために利用可能なメモリを識別する第二のデータを受け取り、前記第一および第二のデータに基づいて前記諸タスクを処理するために十分な利用可能メモリがあるかどうかを識別する、ことを含む。次いで次の区間において、メモリが不十分と識別されたときにのみ、監視ステップおよびサスペンドステップが優先割り込み可能なタスクに適用される。
【００４４】
ここで図５を参照して、タスクはスケジューリング・アルゴリズムに従ってスケジューリングされており、データ構造は各タスクτiについてそのタスクが生成されたのちは維持されるものとする。さらに、スケジューラ５０１が従来の優先度に基づく優先割り込みスケジューリング・アルゴリズムを用いているとする。これは本質的には、どの時点においても、現在実行中のタスクがシステム中の実行準備のできたすべてのタスクのうちで最高の優先度をもつタスクであることを保証するというものである。当技術分野において知られているように、スケジューリングの振る舞いは、実行中のタスクまたは実行準備のできたタスクについての優先割り込みをタスクのメモリ要求に基づいて選択的に有効にしたり無効にしたりすることによって修正できる。
【００４５】
タスクマネージャ５０３は、新たに受領されたタスクに対応するサスペンドデータ１０１を受領し、優先割り込みが要求されていて可能であるかどうかを評価し、要求されていて可能であればこの新たに受領された情報をスケジューラ５０１に渡して優先割り込みを要求する。サスペンドデータは、メモリ使用量情報のみならず当該タスクによって排他的に使用されているリソースRkをも含む。タスクの詳細が表２に定義したようになっているとし、タスクτ1（そしてτ1のみ）が現在処理されていて、スケジューラが初期にはメモリに基づく制約がないモードで動作していると想定する。
【００４６】
ここでタスクマネージャ５０３がタスクτ2を受領したとする。該タスクマネージャ５０３はそのインターフェースInt2１００からサスペンドデータ１０１を読み込み、スケジューラ５０１がメモリおよびリソースに基づく優先割り込みに従ってはたらいているかどうかを識別する。この例ではそうではないので、タスクマネージャ５０３はスケジューラ５０１がメモリおよびリソースに基づく優先割り込みに移行する必要があるかどうかを評価する。したがって、このことはタスクマネージャ５０３が現在実行中のタスクすべて（この例ではタスクτ1）に対応する最悪ケースのメモリ使用サスペンドデータをサスペンドデータ記憶５０５から取得し、式（１）を評価し、その評価された最悪ケースのメモリ要求を利用可能なメモリリソースと比較することに関わる。表２で導入された例を続けると、τ1およびτ2についての式（１）は：
【００４７】
【数５】
2007511819.tif 000009
これは利用可能なメモリにちょうど等しいので、スケジューラ５０１の動作のモードをメモリおよびリソースに基づく優先割り込みに変更する必要はない（すなわち、スケジューラをメモリ使用および排他的リソース使用に基づいて制約する必要はない）。よって、スケジューラ５０１がタスクτ1とタスクτ2との間で切り替わることになっていた場合――たとえばタスクτ2の実行時間制約条件を満たすために――、すなわち両方のタスクが実効的に同時にメモリに存在して同時に最大メモリ量を使っている可能性がある場合にも、当該プロセッサは利用可能であるより多くのメモリをアクセスすることは決してない。
【００４８】
次に、タスクτ1およびタスクτ2が完了する前に、もう一つのタスクτ3が受領される。タスクマネージャ５０３は該タスクτ3に対応するインターフェースInt3からサスペンドデータ１０１を読み込み、スケジューラ５０１がメモリおよびリソースに基づく優先割り込みに移行する必要があるかどうかを評価する。３つのタスクがすべて優先割り込み可能であり、スケジューラ５０１がタスクτ1およびτ2をマルチタスクしているとすると、３つのタスクすべてについての最悪ケースのメモリ要求は今では次のようになる：
【００４９】
【数６】
2007511819.tif 000010
これは利用可能メモリを超過するので、タスクマネージャ５０３は、サスペンドデータ記憶５０５から３つのタスクすべてについてのメモリ使用量データMPi,j、MIi,j１０１ｂ、１０１ｄおよび優先割り込み可能性データを要求して取得し、この取得されたメモリ使用量データおよび優先割り込み可能性データに基づいて３つのタスクすべてを実行するための十分なメモリリソースがあるかどうかを評価する。これは次の式を評価することを通じて確かめることができる：
【００５０】
【数７】
2007511819.tif 000011
このメモリ要求は利用可能メモリより低く、タスクがそのメモリ使用に基づいて優先割り込みされることを前提とすれば、３つのタスクすべてが同時並行して実行できるということになる。
【００５１】
したがって、タスクマネージャ５０３は、各タスクに、指定された優先割り込み点MPi,jにおいてスケジューリング解除命令をスケジューラ５０１に送信するよう指示することによって「メモリおよびリソースに基づく優先割り込みモード」を呼び出す。このモードでは、スケジューラ５０１は次のような動作を許容する。タスクの優先割り込みデータが諸リソースRkのタスク集合の排他的な使用を指定している場合、スケジューラはオペレーティングシステムに、３つのタスクすべてについて前記諸リソースRkに関するすべてのシステムコールを実行するよう指示し、前記諸リソースRkが、タスクが実行を開始したときにシステムコールが実行される諸リソースのシステム集合に追加される。
【００５２】
表３において、RIi,jはタスクiの区間jにおける同期プリミティブによって保護されるリソースの集合である。
【００５３】
【表３】
2007511819.tif 000012
すべての区間が優先割り込み不可能であるときには、システムはスケジューリング可能である。また、この場合リソースの同期については問題ないし、同期プリミティブを実行する必要もない。
【００５４】
しかし、システムの遅延を低減させるため、利用可能メモリ限界を超過することなくいくつかの区間を優先割り込み可能にすることができる。たとえば、システムは：
・τ1は優先割り込み点P1,1およびP1,3において、ならびに区間I1,2の間においてのみ優先割り込みされ、
・τ2はその優先割り込み点においてのみ優先割り込みされ、
・τ3は任意に優先割り込みされる
ときでもまだスケジューリング可能である。表３では、優先割り込み可能な区間を斜体で示してある。
【００５５】
τ1の優先度がτ2の優先度よりも高く、τ2の優先度は今度はτ3の優先度よりも高いとすると、τ3の諸区間が優先割り込み可能なのでτ2の遅延が低減されることになる。タスクマネージャ／スケジューラはさらに、あるリソースを保護するすべての区間がすべて優先割り込み可能であるかすべての優先割り込み不可能であるかのいずれかであることを保証しなければならない。Rbについては問題がある：I2,1は優先割り込み可能だがI3,2は優先割り込み不可能だからである。解決法は、区間I2,1も優先割り込み可能にするか、またはI3,2も優先割り込み不可能にするかのいずれかである。I2,1を優先割り込み可能にすることはシステムのメモリ要求を増やすことはなく、したがって好ましい（遅延を低減させる）。
【００５６】
タスクの一つが終止した場合、終止するタスクはタスクマネージャ５０３に自らが終止することを通知し、タスクマネージャ５０３は諸リソースのシステム集合から諸リソースRkのタスク集合を除去し、それから式（１）を評価する。最悪ケースの（前記タスクの除去を考慮に入れての）メモリ使用量がスケジューラ５０１に利用可能であるより低い場合には、タスクマネージャ５０３はメモリおよびリソースに基づく優先割り込みを取り消して諸リソースのシステム集合をクリアし、これによりシステムが外部イベントに対してよりすばやく反応できる（プロセッサがもはやサブジョブの期間中「ブロック」されないので）ようにするという恩恵が得られる。一般に、タスクの終止は典型的にはその環境によって引き起こされる。引き起こす要因はたとえば、ユーザーによるチャネルの切り換えまたはデータストリーム中における適用エンコード方式の変更（別の種類のデコードを要求する）である。これはすなわち、タスクマネージャ５０３および／またはスケジューラ５０１はタスクの終止を認識すべきであり、おそらくはタスクに終止を指示しさえするということを意味している。
【００５７】
したがって、本方法は、タスクの終止の監視と、タスクの終止に反応してメモリ利用可能性および優先割り込み可能性を識別する前記ステップを繰り返すこととを含む。ある実施形態では、あるタスクが終止したのちに残りのタスクを同時に実行するのに十分なメモリがある場合、前記監視ステップは不要と見なされ、タスクはメモリ使用量に関係する入力のいかなる監視もなしに進行することが許される。
【００５８】
別の好ましい実施形態では、リソースを解放する同期プリミティブとそこに含まれるリソースを保護する一致する別の同期プリミティブとがタスク境界をまたぐことがないように定義される複数のタスクを実行するよう構成されているデータ処理システムであって、前記諸タスクを実行するのに使用する指定された量のメモリへのアクセスを有するデータ処理システムにおいて使用するためのスケジューラが提供される。該スケジューラは：
あるタスクに関係付けられる最大メモリ使用量、該タスクの排他的リソース使用および該タスクの優先割り込み可能性を識別するデータを受け取るよう構成されており、同じリソースの使用を保護している前記複数のタスクのある部分集合のタスクがすべて優先割り込み可能または優先割り込み不可能の一方として識別されるようなデータ受信器と、
前記受け取られたデータに基づいて前記諸タスクを実行するのに十分なメモリがあるかどうかを識別するよう構成されている評価器と、
少なくとも一つのタスクを該タスクの実行の間のサスペンドのために選択するよう構成されており、該サスペンドが該タスクによる特定のメモリ使用量および該タスクが優先割り込み可能であることと符合するような選択器、
とを有しており、前記評価器が前記複数のタスクを実行するのにメモリが不足していると識別するのに反応して、
・前記選択器が、タスクの特定のメモリ使用量およびタスクの優先割り込み可能性ならびに当該データ処理システムに利用可能な特定のメモリ量に基づいて、少なくとも一つのタスクをサスペンドのために選択し、
・前記スケジューラが、前記少なくとも一つの選択されたタスクの実行を、該タスクが前記特定のメモリを使用しており該タスクが優先割り込み可能であることに反応してサスペンドし、
・前記評価器が、前記サスペンドされた少なくとも一つのタスクの保護されたリソースに関する同期プリミティブのその後の実行を監督する。
【００５９】
この実施形態では、スケジューラはハードウェアおよびソフトウェアのうちの一方において実装され、データ処理システムはデジタルテレビシステムのような高容量消費者電子機器である。
【００６０】
別の実施形態では、データをデータ処理システムに送信する方法が提供される。該方法は：
そこに含まれる別の同期プリミティブに一致するリソースの使用を保護する同期プリミティブがタスク境界をまたがないようにタスクを定義し、
すべてのタスクを、該諸タスクが少なくとも一つの同じリソースの使用を保護しているか否かに依存して優先割り込み可能または優先割り込み不可能として定義し、
タスクの処理においてデータ処理システムによって使用するためのデータを送信し、
処理の間のメモリ使用量と優先割り込み可能性とに基づいてタスクのサスペンドを指定するサスペンドデータを送信し、
前記データ処理システムは：
当該タスクに関連付けられたサスペンドデータに一致する当該タスクのメモリ使用量を示す入力を監視し、
前記サスペンドデータが当該タスクが優先割り込み可能であると規定していれば、前記監視にかかった入力に基づいて当該タスクの処理をサスペンドする、
ことを含むプロセスを実行するよう構成されている。
したがって、この実施形態は、データ処理システムによって処理されるべきタスクに対応するサスペンドデータの配送に関わっている。サスペンドデータは、規則的に放送される信号の一部として配送されるか（たとえば、他のソースに伴うサスペンドデータをもつ追加的なタスク）、あるいはデータ処理システムの一般的な更新の一部としてサービスプロバイダーによって配送される。さらに、データ処理システムは別個のリンクまたはデバイス（たとえばフロッピー（登録商標）ディスクもしくはCD-ROM）を通じて更新されることができる。
【００６１】
本発明の好ましい実施形態が図解され、説明されてきたが、当業者には、本発明の真の範囲から外れることなく、さまざまな変更および修正を施すことができ、その要素を等価物をもって代えることもできることは理解されるであろう。さらに、中心的な範囲から外れることなく、本発明の思想を特定の状況に合わせて適合させるために多くの修正を施すことができる。したがって、本発明が本発明を実施するための考えられている最良の形態として開示されている特定の実施形態に限定されるのではなく、本発明が付属の特許請求の範囲内にはいるあらゆる実施形態を含むことが意図されている。
【図面の簡単な説明】
【００６２】
【図１】本発明のある実施形態に基づくタスク・インターフェースの構成要素の概略図である。
【図２】本発明のある実施形態が動作するデジタルテレビシステムの例の概略図である。
【図３】図１に示したタスク・インターフェースの構成要素の間の関係の概略図である。
【図４】図２のセットトップボックスを構成する要素を示す図である。
【図５】図２および図４で示されたセットトップのプロセッサの構成要素を示す図である。
【図１】
2007511819.tif 000013
【図２】
2007511819.tif 000014
【図３】
2007511819.tif 000015
【図４】
2007511819.tif 000016
【図５】
2007511819.tif 000017
【国際調査報告】
2007511819.tif 000018
2007511819.tif 000019
2007511819.tif 000020