(57)【要約】  メインメモリ要求に基づきタスクプリエンプションポイントを選択するため、マルチプロセッサデータ処理システムのスケジューラにより利用される方法及び装置が提供される。タスクのプロセッサへの割当に応じて３つの好適な実施例がある。（１）固定的割当：すべてのタスクがあるプロセッサに割り当てられる。すなわち、各タスクは、与えられたプロセッサ上で排他的に実行される。本実施例は、プロセッサが専用的なものであるとき、すなわち、各プロセッサが他のすべてのプロセッサと実質的に異なっている場合に好適である。（２）可変的割当：すべてのタスクが、すべてのプロセッサ上で実行されるかもしれない。実行時、スケジューラは、何れのプロセッサがどのタスクを実行するか決定する。タスクは、１つのプロセッサ上で実行中にプリエンプトされてもよく、その後、他のプロセッサ上で続けられる。本実施例は、すべてのプロセッサが同じものであるとき好適である。（３）混合的割当：すべてのタスクは、プロセッサの一部に割り当てられる。これは、プロセッサ群がプロセッサが同一であるサブセットに分割可能であるときに自然なアプローチである。
2007519103.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサを有するデータ処理システムにおける複数のタスクをスケジューリングする方法であって、
前記複数のタスクの各タスクについて、使用されるメモリに基づき前記タスクのサスペンションを示すサスペンションデータを提供するステップと、
前記複数のタスクのそれぞれを前記複数のプロセッサのあるプロセッサに割り当てるステップと、
を有し、
各プロセッサは、
（ｉ）該プロセッサに割り当てられたタスクを処理するステップと、
（ｉｉ）前記タスクに係るサスペンションデータに一致する前記タスクにより使用されるメモリを示す入力を監視するステップと、
（ｉｉｉ）前記監視される入力に基づき前記タスクをサスペンドするステップと、
（ｉｖ）該プロセッサに割り当てられるタスクの異なるタスクを処理するステップと、
を実行することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
タスクのプロセッサへの割当ては、
ａ．すべてのタスクをあるプロセッサに割り当てる固定的割当と、
ｂ．すべてのタスクをすべてのプロセッサに割り当てる可変的割当と、
ｃ．すべてのタスクを前記複数のプロセッサの一部に割り当てる混合的割当と、
の１つに基づくことを特徴とする方法。
【請求項３】
請求項２記載の方法であって、
前記入力は、サスペンションリクエストを示すデータを有することを特徴とする方法。
【請求項４】
請求項３記載の方法であって、さらに、
前記複数のタスクに係る最大メモリ使用を特定する第１データを受け付けるステップと、
前記複数のタスクを処理するのに利用可能なメモリを特定する第２データを受け付けるステップと、
前記第１及び第２データに基づき、前記タスクを処理するのに利用可能な十分なメモリが存在するか特定するステップと、
を有し、
前記監視するステップと前記サスペンドするステップは、不十分なメモリを特定することに応答してのみ実行されることを特徴とする方法。
【請求項５】
請求項４記載の方法であって、さらに、
タスクの終了を監視するステップと、
タスク終了に応答して、タスク終了に応答したメモリの利用性を特定する前記ステップを繰り返すステップと、
を有することを特徴とする方法。
【請求項６】
請求項５記載の方法であって、
残りのタスクを実行するのに十分なメモリを特定することに応答して、前記監視するステップは、不要とみなされることを特徴とする方法。
【請求項７】
請求項６記載の方法であって、さらに、
前記複数のタスクに係る最大メモリ使用を特定する第１データを受け付けるステップと、
前記複数のタスクを処理するのに利用可能なメモリを特定する第２データを受け付けるステップと、
前記第１及び第２データに基づき、前記タスクを処理するのに利用可能な十分なメモリが存在するか特定するステップと、
を有し、
前記監視するステップと前記サスペンドするステップは、不十分なメモリを特定することに応答してのみ実行されることを特徴とする方法。
【請求項８】
請求項７記載の方法であって、さらに、
タスクの終了を監視するステップと、
タスク終了に応答して、タスク終了に応答したメモリの利用性を特定する前記ステップを繰り返すステップと、
を有することを特徴とする方法。
【請求項９】
請求項８記載の方法であって、
残りのタスクを実行するのに十分なメモリを特定することに応答して、前記監視するステップは、不要とみなされることを特徴とする方法。
【請求項１０】
請求項２記載の方法であって、さらに、
前記複数のタスクに係る最大メモリ使用を特定する第１データを受け付けるステップと、
前記複数のタスクを処理するのに利用可能なメモリを特定する第２データを受け付けるステップと、
前記第１及び第２データに基づき、前記タスクを処理するのに利用可能な十分なメモリが存在するか特定するステップと、
を有し、
前記監視するステップと前記サスペンドするステップは、不十分なメモリを特定することに応答してのみ実行されることを特徴とする方法。
【請求項１１】
請求項１０記載の方法であって、さらに、
タスクの終了を監視するステップと、
タスク終了に応答して、タスク終了に応答したメモリの利用性を特定する前記ステップを繰り返すステップと、
を有することを特徴とする方法。
【請求項１２】
請求項１１記載の方法であって、
残りのタスクを実行するのに十分なメモリを特定することに応答して、前記監視するステップは、不要とみなされることを特徴とする方法。
【請求項１３】
複数のプロセッサを有するデータ処理システムにおける複数のタスクをスケジューリングする方法であって、
前記複数のタスクの各タスクについて、使用されるメモリに基づき前記タスクのサスペンションを示すサスペンションデータを提供するステップと、
すべてのタスクをあるプロセッサに割り当てる固定的割当と、すべてのタスクをすべてのプロセッサに割り当てる可変的割当と、すべてのタスクを前記複数のプロセッサの一部に割り当てる混合的割当との１つに基づき、前記複数のタスクのそれぞれを前記複数のプロセッサのあるプロセッサに割り当てるステップと、
を有し、
各プロセッサは、
（ｉ）該プロセッサに割り当てられたタスクを処理するステップと、
（ｉｉ）前記タスクに係るサスペンションデータに一致する前記タスクにより使用されるメモリを示す入力を監視するステップと、
（ｉｉｉ）前記監視される入力に基づき前記タスクをサスペンドするステップと、
（ｉｖ）該プロセッサに割り当てられるタスクの異なるタスクを処理するステップと、
を実行することを特徴とする方法。
【請求項１４】
複数のプロセッサを有するデータ処理システムにおいて使用されるスケジューラであって、
前記データ処理システムは、前記複数のプロセッサ上で複数のタスクを実行するよう構成され、前記タスクを実行するのに利用される指定された量のメモリにアクセスし、
前記スケジューラは、
タスクに係る最大メモリ使用を特定するデータを受け付けるよう構成されるデータ受信機と、
前記受け付けたデータに基づき、前記タスクを実行するのに十分なメモリが存在するか特定するよう構成される評価装置と、
ａ．すべてのタスクをあるプロセッサに割り当てる固定的割当と、ｂ．すべてのタスクをすべてのプロセッサに割り当てる可変的割当と、ｃ．すべてのタスクを前記複数のプロセッサの一部に割り当てる混合的割当との１つに基づき、前記複数のタスクのそれぞれを前記複数のプロセッサのあるプロセッサに割り当てるよう構成される割当装置と、
前記タスクの実行中、前記タスクにより指定されるメモリ使用と一致するサスペンションのため少なくとも１つのタスクを選択するよう構成される選択装置と、
前記割り当てられたタスクの実行を開始し、前記選択されたタスクをサスペンドするよう構成されるスケジューラと、
を有し、
前記評価装置が前記複数のタスクを実行するのに不十分なメモリしか存在しないと特定することに応答して、前記選択装置は、サスペンションのための少なくとも１つのタスクを、それの指定されたメモリ使用と前記データ処理システムに利用可能な指定されたメモリ量に基づき選択し、
前記スケジューラは、前記タスクが前記指定されたメモリを使用することに応答して、前記少なくとも１つの選択されたタスクの実行をサスペンドすることを特徴とするスケジューラ。
【請求項１５】
請求項１４記載のスケジューラであって、
前記評価装置は、タスクの終了を監視し、タスクの終了に応答して、残りのタスクを実行するのに十分なメモリが存在するか特定するよう構成されることを特徴とするスケジューラ。
【請求項１６】
請求項１５記載のスケジューラであって、
前記評価装置が残りのタスクを実行するのに十分なメモリを特定することに応答して、前記選択装置は、前記選択された少なくとも１つのタスクを選択解除するよう構成されることを特徴とするスケジューラ。
【請求項１７】
複数のタスクを実行するよう構成される複数のプロセッサを有するデータ処理システムであって、
タスクの実行中に命令及びデータを保持するよう構成されるメモリと、
タスクに係る最大メモリ使用を特定するデータと、前記タスクのプリエンプション可能性を示すデータとを受け付けるよう構成される受付手段と、
前記受け付けたデータに基づき、前記タスクを実行するのに十分なメモリが存在するか特定するよう構成される評価手段と、
すべてのタスクをあるプロセッサに割り当てる固定的割当と、すべてのタスクをすべてのプロセッサに割り当てる可変的割当と、すべてのタスクを前記複数のプロセッサの一部に割り当てる混合的割当との１つに基づき、前記複数のタスクのそれぞれを前記複数のプロセッサのあるプロセッサに割り当てるよう構成される割当装置と、
前記評価手段から受け付けた入力に基づき、前記タスクの実行をスケジューリングするよう構成されるスケジューラと、
を有し、
前記複数のタスクを実行するのに十分なメモリが存在しないと特定することに応答して、前記スケジューラは、前記タスクによるメモリ使用に応じて少なくとも１つのタスクの実行をサスペンドするよう構成されることを特徴とするデータ処理システム。
【請求項１８】
複数のプロセッサを有するデータ処理システムにデータを送信する方法であって、
すべてのタスクをあるプロセッサに割り当てる固定的割当と、すべてのタスクをすべてのプロセッサに割り当てる可変的割当と、すべてのタスクを前記複数のプロセッサの一部に割り当てる混合的割当との１つに基づき、複数のタスクのそれぞれを前記複数のプロセッサのあるプロセッサに割り当てるステップと、
前記複数のタスクの各タスクの処理において、前記データ処理システムにより使用されるデータを送信するステップと、
処理中のメモリ使用に基づき、前記複数のタスクの各タスクのサスペンションを示すサスペンションデータを送信するステップと、
を有し、
前記データ処理システムは、前記タスクに係るサスペンションデータに一致する各タスクのメモリ使用を示す入力を監視し、前記監視された入力に基づき、前記各タスクの処理をサスペンドする処理を実行するよう構成されることを特徴とする方法。
【請求項１９】
請求項１８記載の方法であって、
前記サスペンションデータは、前記各タスクに係る最大メモリ使用を特定するデータを有することを特徴とする方法。
【請求項２０】
請求項１８記載の方法であって、
前記サスペンションデータは、前記各タスクのメモリ使用に基づき、各タスクの処理がサスペンド可能な少なくとも１つのポイントを特定することを特徴とする方法。
【請求項２１】
請求項２０記載の方法であって、
前記各タスクは、複数のサブジョブを有し、
前記各タスクの処理がサスペンド可能な少なくとも１つのポイントを特定するデータは、各サブジョブに対応する、
ことを特徴とする方法。
【請求項２２】
請求項２０記載の方法であって、
前記サスペンションデータは、前記各タスクに係る最大メモリ使用を特定するデータを有することを特徴とする方法。
【請求項２３】
請求項２２記載の方法であって、
前記各タスクは、複数のサブジョブを有し、
前記各タスクの処理がサスペンド可能な少なくとも１つのポイントを特定するデータは、各サブジョブに対応する、
ことを特徴とする方法。
【請求項２４】
複数のプロセッサを有するデータ処理システムにおいて使用するため複数のタスクを構成する方法であって、
当該方法は、関連するメモリ使用に基づきタスクのサスペンションを示すサスペンションデータを前記タスクに関連付けするステップを有し、
前記データ処理システムは、複数のプロセッサ上で実行される複数のタスクに関して処理を実行するよう構成され、
前記処理は、
すべてのタスクをあるプロセッサに割り当てる固定的割当と、すべてのタスクをすべてのプロセッサに割り当てる可変的割当と、すべてのタスクを前記複数のプロセッサの一部に割り当てる混合的割当との１つに基づき、複数のタスクのそれぞれを前記複数のプロセッサのあるプロセッサに割り当て、
前記タスクに係るサスペンションデータに一致する前記タスクのメモリを示す入力を監視し、
前記監視される入力に基づき前記タスクの処理をサスペンドすることを有することを特徴とする方法。
【請求項２５】
請求項１記載の方法を処理システムに実行させるよう構成される命令セットを有するコンピュータプログラム。
【請求項２６】
請求項２記載の方法を処理システムに実行させるよう構成される命令セットを有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、限定されるものではないが特に、マルチプロセッサリアルタイムシステムのリソース管理に適したリソース管理方法及び装置に関する。
【背景技術】
【０００２】
システム・オン・シリコン（ＳｏＳ）又はシステム・オン・チップ（ＳｏＣ）について、必要とされるシリコン量の観点から、他の処理コアを追加することはもはや問題ではないため、メモリは支配的な制限要因となりつつある。この結果、ＳｏＳ又はＳｏＣは複数のプロセッサコアを含むかもしれない。
【０００３】
メモリの管理は、マルチプロセッサシステムのリソース管理の重要な側面である。特にリアルタイムシステムにおいて、プリエンプションポイント（ｐｒｅｅｍｐｔｉｏｎ  ｐｏｉｎｔ）の使用をメインメモリの管理に一般化することを含むシングルプロセッサシステムのためのメモリ使用を最適化するための各種方法が開発されてきた。これらのアプローチでは、実行中の任意の時点においてタスクをプリエンプトするのではなく、当該タスクは、好ましくは、それらのメモリ使用に基づき専用のプリエンプションポイントにおいてのみプリエンプトされる。
【０００４】
典型的な従来技術によるアプローチでは、タスクのサスペンションはタスクプリエンプション又はタスクのプリエンプションと呼ばれ、「タスク」という用語は、メモリ、ＣＰＵ、Ｉ／Ｏ装置などのシステムリソースのためそのままで競合し得る実行ユニットを表すのに利用される。説明のため、タスクとは、各々が１以上のサブジョブを有する連続的に実行される一連のジョブであると仮定される。例えば、タスクは「映像ストリームの多重化」を有し、入力ストリームのリードイン（ｒｅａｄｉｎｇ−ｉｎ）、当該ストリームの処理及び対応するデータの出力に関するものとすることができる。これらのステップは、各入力データストリームに関して実行され、この結果、単一のストリームに関する読み込み、処理及び出力が各々３つのサブジョブを有する１つのジョブを実行することに対応するように、各入力データストリームに関して上記ステップが実行される。従って、リードイン及び処理対象となるデータパケットが複数存在するときには、当該ジョブは、対応する回数だけ実行される。サブジョブは、ジョブの機能コンポーネントに関するものとみなすこができ、マルチプロセッサシステムでは、各ストリームは異なるプロセッサ又はプロセッサ群の一部に割り当てられる。
【０００５】
データ処理システムにおいて複数のタスクをスケジューリングする既知の方法は、タスクの各サブジョブが、サスペンションデータ（ｓｕｓｐｅｎｓｉｏｎ  ｄａｔａ）と呼ばれ、それのメモリ使用に基づきサブジョブのサスペンションのため、処理中のプリエンプションポイントと対応する状態を特定するサスペンション基準群を有することを要求する［４］［５］。従って、データ処理システムにより使用されるメモリ量は、これらのプリエンプションポイントを介し、ジョブの実行において上記プリエンプションポイントにおいて要求されるメモリ量を示す上記サスペンションデータにより間接的に制御される。
【０００６】
従って、これらのプリエンプションポイントは、メモリの不足によるデータ処理システムのクラッシュを回避するのに利用可能である。リアルタイムタスクは複数のサブジョブを有するものとして特徴付けされるとき、それのプリエンプションポイントは、好ましくは、当該タスクのサブジョブ境界と一致する。
【０００７】
タスクの各サブジョブに係るサスペンションデータに従うタスクのメモリ使用を示すデータは、例えば、タスク処理においてプリエンプションポイントに到達したこと、すなわち、サブジョブ境界に到達したことを示すデスケジューリング（ｄｅｓｃｈｅｄｕｌｉｎｇ）イベントをリクエストするコードラインを介しタスクに埋め込むことができる。すなわち、タスクのサブジョブのスタートポイント群は、当該タスクのプリエンプションポイント群を構成する。タスクτｉの第ｊプリエンプションポイントＰｉ，ｊは、プリエンプションポイント自体に関する情報と、第ｊプリエンプションポイントと次のプリエンプションポイント、すなわち、第（ｊ＋１）プリエンプションポイントとの間の後続するプリエンプト不可なサブジョブインターバルＩｉ，ｊに関する情報とにより特徴付けされる。
【０００８】
実行時、タスクは、それがサブジョブをスタートし、サブジョブ間のスイッチを行い、サブジョブを完了させるときなど、プリエンプションポイントに到達したときを制御するオペレーティングシステムに通知し、オペレーティングシステムは、タスクの実行がいつ、どこでプリエンプトされるか決定する。理想的には、タスクの実行中にプリエンプションポイント又は他の何れかのポイントにおいてプリエンプションが実行されるかもしれない。しかしながら、そのようなプリエンプションの選択のフレキシビリティは、プリエンプションがコンシスタンシを維持するようプリエンプションポイントに限定されるように、コンシスタンシを犠牲にして得られる。
【０００９】
システムのコンシスタンシを脅かさないメインメモリ要求に基づく従来技術によるプリエンプションポイントアプローチは、すべてのタスクのプリエンプションをそれらのプリエンプションポイントとマッチする同期プリミティブに、サブジョブ境界内に両者が存在するようにリソースの排他的使用を制御するため必然的に制限する。従来技術において知られているように、コンポーネント（例えば、１以上のタスクを有することが可能なソフトウェアコンポーネントなど）は、当該コンポーネントが規定するプロパティ、ファンクション又はメソッド及びイベントを有するプログラマブルインタフェースを有することができる。説明のため、タスクは、図１に示されるように、タスクＭＰｉ，Ｊ１０１ｂにより要求される最小でもメインメモリデータを含むインタフェース１００に伴うものであると仮定される。
【００１０】
説明のため、タスクは、周期的でリアルタイムなものであると仮定され、ピリオドＴとフェージングＦ（０≦Ｆ＜Ｔ）により特徴付けされ、そのことは、タスクが各々時点Ｆ＋ｎＴ（ｎ＝０，．．．，Ｎ）においてリリースされるサブジョブシーケンスを有することを意味する。単なる一例として、図２に示されるように、セットトップボックス２００は、（１）ユーザインタフェース２０５上でのメニューの表示、（２）コンテンツプロバイダからのテキスト情報の抽出、及び（３）映像信号の処理の３つのタスクを実行すると仮定され、これら２つのタスクのそれぞれは、複数のサブジョブを有すると仮定される。説明の簡単化のため、これらのサブジョブはシーケンシャルに実行されると仮定される。
【００１１】
上記サブジョブの少なくとも一部は、プリエンプト可能であり、プリエンプト可能な上記サブジョブ間の境界は、プリエンプションポイントを提供し、テーブル１に要約される。
【００１２】
【表１】
2007519103.tif 000003
また図３を参照するに、各タスクについて、サスペンションデータ１０１は、プリエンプションポイントＰｉ，ｊ３０１に関する情報、例えば、当該プリエンプションポイントにおいて求められるメモリＭＰｉ，ｊ３０２の最大量などと、連続するプリエンプションポイントの間のインターバルＩｉ，ｊ３０３に関する情報、例えば、イントラプリエンプションポイントインターバルにおいて求められるメモリＭＩｉ，ｊ３０４のワーストケース量などを有する（ｉはタスクτｉを表し、ｊはプリエンプションポイントを表す）。
【００１３】
より詳細には、サスペンションデータ１０１は、
１．タスクτｉ（Ｐｉ，ｊ）のプリエンプションポイントｊ（１０１ａ）と、
２．当該タスクのプリエンプションポイントｊにおけるタスクτｉＭＰｉ，ｊの最大メモリ要求（ただし、１≦ｊ≦ｍ（ｉ））（１０１ｂ）と、
３．タスクτｉのサブジョブに対応する連続するプリエンプションポイントｊと（ｊ＋１）との間のインターバルＩｉ，ｊ（ただし、１≦ｊ≦ｍ（ｉ））（１０１ｃ）と、
４．当該タスクのインターバルｊにおけるタスクτｉＭＩｉ，ｊの最大（すなわち、ワーストケース）メモリ要求（ただし、１≦ｊ≦ｍ（ｉ））（１０１ｄ）と、
を示すデータを有する。
【００１４】
テーブル２は、本例のサスペンションデータ１０１を示す（本例では、第１タスクτ１に対応するサスペンションデータ１０１がテーブル２の第１行のデータを有し、第２タスクτ２に対応するサスペンションデータ１０１がテーブル２の第２行を有するなどとなるように、各タスクは自らのインタフェースを有する）。
【００１５】
【表２】
2007519103.tif 000004
セットトップボックス２００には１．５メガバイトのメモリが備えられていると仮定する。通常又は非メモリベースプリエンプション状態では、このセットトップボックス２００は以下のように動作する。
【００１６】
ここで図４Ａを参照するに、プロセッサ４０１は、３つすべてのタスクが同時に実行され、すなわち、同時に効果的に実行されることを意味する、ある種のタイムスライシング又はプライオリティベースプリエンプションに従ってタスクをスケジューリングすることが期待されるかもしれない。従って、各タスクは同時にそれの最もメモリを消費するサブジョブを実行させるようスケジューリングさせることが可能である。これら３つのタスクのワーストケースのメモリ要求ＭＰは、
【００１７】
【数１】
2007519103.tif 000005
により与えられる。タスクτ１、τ２及びτ３について、ＭＰは、τ１の最大メモリ要求（ＭＩ１，１である）と、タスクτ２の最大メモリ要求（ＭＩ２，２である）と、タスクτ３の最大メモリ要求（ＭＩ３，２である）とを加えたものとなる。これら最大要求は、太字によるテーブル２のエントリにより示される。
【００１８】
【数２】
2007519103.tif 000006
これは、セットトップボックス２００に利用可能なメモリを０．２メガバイトだけ超過し、予防的措置がなく、これらのサブジョブが同時に処理される場合、セットトップボックス２００はクラッシュする。
【００１９】
ここで図５を参照するに、各タスクはスケジューリングアルゴリズムによりスケジューリングされ、生成された後、各タスクτｉについてデータ構造が維持され、リソースの排他的使用のためのプリミティブの当該マッチングしたペアがサブジョブ境界に広がらないことを仮定する。さらに、スケジューラ５０１は、何れの時点においても、現在実行中のタスクがシステムにおいて実行準備が完了したすべてのタスクのうち最も高いプライオリティを有するものであるということを実質的に保証する従来のプライオリティベースのプリエンプティブスケジューリングアルゴリズムを利用する。当該技術において知られているように、スケジューリング動作は、実行中又は実行準備が完了したタスクのためのプリエンプションを選択的にイネーブル及び非イネーブルとすることによって変更可能である。
【００２０】
タスクマネージャ５０３は、新たに受け付けたタスクに対応するサスペンションデータ１０１を受け取り、プリエンプションが必要か評価し、必要な場合には、当該新たに受け付けた情報をスケジューラ５０１にわたし、プリエンプションを要求する。タスクの詳細はテーブル２に規定されるようなものであり、タスクτ１（そしてτ１のみ）が現在処理中であり、スケジューラはメモリベース制約が存在しないモードにより初期的に動作していると仮定する。
【００２１】
ここで、タスクτ２は、タスクマネージャ５０３により受け取られ、タスクマネージャ５０３は、それのインタフェースＩｎｔ２１００からサスペンションデータ１０１を読み出し、スケジューラ５０１がメモリベースプリエンプションに従って動作しているか特定すると仮定する。本例では、スケジューラ５０１は当該動作を行っていないため、タスクマネージャ５０３は、スケジューラ５０１がメモリベースプリエンプションに変更する必要があるか評価する。従って、これは、タスクマネージャ５０３がサスペンションデータストア５０５から現在実行中のすべてのタスク（本例では、タスクτ１）に対応するワーストケースサスペンションデータを抽出し、式１を評価し、評価されたワーストケースメモリ要求と利用可能なメモリリソースとを比較することに関する。テーブル２により導入された例により続けると、τ１及びτ２について式１は、
【００２２】
【数３】
2007519103.tif 000007
となる。
【００２３】
これは、利用可能なメモリより小さく、そのため、スケジューラ５０１の動作モードをメモリベースプリエンプションに変更する必要はない（すなわち、メモリ使用に基づきスケジューラを制限する必要はない）。従って、スケジューラ５０１がタスクτ１とタスクτ２との間を、例えば、両方のタスクが同時に効果的にメモリに存在することを意味するタスクτ２の実行時間制限を満たすようスイッチする場合、プロセッサは、利用可能なものより多くのメモリにはアクセスしない。
【００２４】
次に、タスクτ１とτ２が完了する前に、他のタスクτ３が受け付けられる。タスクマネージャ５０３は、タスクτ３に係るインタフェースＩｎｔ３からサスペンションデータ１０１を読み出し、スケジューラ５０１がメモリベースプリエンプションに変更しなければならないか評価する。スケジューラ５０１がタスクτ１及びτ２をマルチタスク処理していると仮定すると、３つすべてのタスクのワーストケースメモリ要求は、
【００２５】
【数４】
2007519103.tif 000008
となる。
【００２６】
これは利用可能なメモリを超過し、このため、タスクマネージャ５０３は、サスペンションデータストア５０５から３つすべてのタスクに対してメモリ使用データＭＰｉ，ｊ１０１ｂとＭＩｉ，ｊ１０１ｄをリクエスト及び抽出し、この抽出されたメモリ使用データに基づき、３つすべてのタスクを実行するのに十分なメモリリソースが存在するか評価する。これは、以下の式を評価することを通じて確認することができる。
【００２７】
【数５】
2007519103.tif 000009
このメモリ要求は、利用可能なメモリより低く、タスクがそれらのメモリ使用に基づきプリエンプトされる場合、３つすべてのタスクが同時に実行可能であることを意味する。
【００２８】
従って、タスクマネージャ５０３は、タスクにそれらの指定されたプリエンプションポイントＭＰｉ，ｊにおいてスケジューラ５０１にデスケジュール命令を送信するよう命令することによって、「メモリベースプリエンプションモード」を呼び出す。このモードでは、スケジューラ５０１は、任意の時点において、ある時点の高々１つのタスクがそれのプリエンプションポイントの１つ以外のポイントにあることが可能であるという制約により、各タスクが１つのプリエンプションポイントから次のポイントに非プリエンプティブに実行されることを可能にする。新たに到着したタスクがプリエンプションポイントにおいてスタートすると仮定すると、スケジューラ５０１は、当該状態が現在実行されているタスクについて維持されることを保証し、これにより、１つを除いてすべてのタスクがプリエンプションポイントにあるよう制限される。
【００２９】
従って、１つの既知のメモリベースプリエンプションモードでは、スケジューラ５０１は、各タスクをそれらのメモリプリエンプションポイントにおいてのみプリエンプトすることが可能とされる（すなわち、それらのメモリベースプリエンプションポイントにおけるタスクからのデスケジュールリクエストに応答して）。
【００３０】
タスクの１つが終了すると、終了するタスクは、それが終了するところであることをタスクマネージャ５０３に通知し、タスクマネージャ５０３に式１を評価させ、ワーストケースメモリ使用（当該タスクの削除を考慮して）がスケジューラ５０１に利用可能なものより小さい場合、タスクマネージャ５０３はメモリベースプリエンプションをキャンセルすることが可能であり、それは、システムが外部イベントにより迅速に反応することを可能にするという効果を有する（プロセッサは、サブジョブの期間においてもはや「ブロック」されないためである）。一般に、タスクの終了は、典型的には、ユーザによるチャネルのスイッチ又は適用される符号化のデータストリームの変更などのそれの環境により引き起こされ（他のタイプの復号化を要する）、このことは、タスクマネージャ５０３及び／又はスケジューラ５０１が、タスクの終了を認識し、おそらくタスクに終了する指示さえすべきである。
【００３１】
呼び出されると、メモリベースプリエンプション制約は必須であるということに留意すべきである。
【００３２】
これらのタスクは、ソフトウェアタスクとして説明されたが、タスクはまたハードウェアにより実現することも可能である。典型的には、ハードウェア装置（ハードウェアタスクとして動作する）がソフトウェアタスクにより制御され、ソフトウェアタスクは、ハードウェア装置により必要とされる（ワーストケース）メモリを配分し、その後にハードウェアタスクが実行されるよう指示する。ハードウェアタスクが完了すると、それはソフトウェアタスクに通知し、その後、メモリをデアロケート（ｄｅ−ａｌｌｏｃａｔｅ）する。従って、制御するソフトウェアタスクを有することによって、ハードウェアタスクは単に上述のように処理することが可能である。
【発明の開示】
【発明が解決しようとする課題】
【００３３】
このアプローチは、シングルプロセッサシステムに適用され、マルチプロセッサシステムについては最適化されておらず、このため、マルチプロセッサ最適化が必要とされる。
【００３４】
本発明は、マルチプロセッサシステムについて、シングルプロセッサアプローチを上述のメモリベースリソース管理に最適化する。ｎ個のタスクτｉの集合Γ（１≦ｉ≦ｎ）と、ｐ個のプロセッサπｋの集合Ｐ（１≦ｋ≦ｐ）を検討し（ただし、ｎは典型的にはｐよりはるかに大きい）、非制限モードについてＦＰＰＳ（Ｆｉｘｅｄ−Ｐｒｉｏｒｉｔｙ  Ｐｒｅｅｍｐｔｉｖｅ  Ｓｃｈｅｄｕｌｉｎｇ）スキームと、メモリベースプリエンプションモードについてＦＰＤＰ（Ｆｉｘｅｄ−Ｐｒｉｏｒｉｔｙ  ｓｃｈｅｄｕｌｉｎｇ  ｗｉｔｈ  Ｄｅｆｅｒｒｅｄ  Ｐｒｅｅｍｐｔｉｏｎ）スキームとを仮定する。
【課題を解決するための手段】
【００３５】
タスクのプロセッサへの割当てに応じて、３つの好適な実施例が存在する。
１．固定的割当：すべてのタスクτｉがあるプロセッサπｋに割当て、すなわち、タスクτｉがプロセッサπｋ上で排他的に実行される。本実施例は、プロセッサが専用であるとき、すなわち、各プロセッサが他のすべてのプロセッサと本質的に異なっている場合、好ましい。
２．可変的割当：すべてのタスクτｉが、すべてのプロセッサπｋ上で実行されてもよい。実行時、スケジューラは、何れのプロセッサがどのタスクを実行するか決定する。タスクは１つのプロセッサ上での実行中にプリエンプトされ、その後、他のプロセッサ上で続けられる。本実施例は、すべてのプロセッサが同一であるとき好ましい。
３．混合的割当：すべてのタスクτｉがプロセッサの一部に割り当てられる。これは、当該プロセッサ群が同一なプロセッサのサブセットに分割可能であるとき自然なアプローチである。
【００３６】
本発明の上記及び他の特徴及び効果が、添付された図面に示されるような以下の好適な実施例の詳細な説明から明らかである、当該図面において、各図を通じて参照記号は同一の部分を参照している。
【発明を実施するための最良の形態】
【００３７】
以下の説明は限定のためのではなく、例示のために与えられるものであるということは、当業者により理解されるべきである。当業者は、本発明の趣旨及び添付した請求項の範囲内に属する変形が多数存在することを理解している。既知の機能及び処理の不要な詳細は、本発明を不明りょうにしないように本説明から省略されるかもしれない。
【００３８】
デジタルテレビセット、デジタル改良されたアナログテレビセット、セットトップボックスなどのＨＶＥ（Ｈｉｇｈ  Ｖｏｌｕｍｅ  Ｅｌｅｃｔｒｏｎｉｃ）家電システムは、コスト効率とロウバスト性を維持しながら、リアルタイムサービスを提供しなければならない。家電機器は、その性質により、大きくリソース制約的なものである。この結果、利用可能なリソースは、ロウバスト性などのＨＶＥ家電システムの代表的な品質を維持し、厳密なタイミング要求を満たしながら、大変効率的に利用される必要がある。ロウバスト性に関して、誰もテレビセットなどが「システムをリブートしてください」というメッセージにより落ちることを予想しない。
【００３９】
ＨＶＥ家電システムにおけるメディア処理の重要な部分は、複数の同時データストリームを処理し、特にマルチタスク処理環境においてメインメモリなどのシステムリソースを大変効率的に管理しなければならないオンボードソフトウェアにより実現される。リアルタイムリソース管理を要するＨＶＥ家電システムの一例として、セットトップボックスを検討する。従来、図２に示されるように、セットトップボックス２００は、コンテンツプロバイダ２０３（サーバ又はケーブル）とユーザインタフェース２０５からテレビ２０１の入力を受信する。ユーザインタフェース２０５は、携帯型の赤外線リモート送信機など、ユーザにより制御されるリモート装置２０２から信号を受信するリモートコントロールインタフェースを有する。セットトップボックス２００は、アンテナとケーブルテレビアウトレットの少なくとも１つから少なくとも１つのデータストリームを受信し、当該データストリームの処理と当該データストリーム２０１のテレビ２０１への転送の少なくとも１つを実行する。ユーザは、テレビ２０１上に表示される少なくとも１つのデータストリームを視聴し、ユーザインタフェース２０５を介し、表示中のものに基づき選択する。セットトップボックス２００は、ユーザ選択入力を処理し、この入力に基づき、コンテンツプロバイダ２０３にユーザ入力と共に、セットトップ２００とその機能を特定する他の情報を送信するようにしてもよい。
【００４０】
図４Ｂは、タスクをプロセッサ４６０．１〜４６０．３に割当て、セットトップボックス２００の全体処理を制御する制御割当ロジックモジュールにより管理される複数のプロセッサ４６０．１〜４６０．３を含む典型的なセットトップボックス２００の一例となるシステム４５０の簡単化されたブロック図を示す。制御割当ロジックモジュール４５１は、ネットワーク４０７とストレージ４０６から入力データを受信するデータ受信機４５２と、メモリ使用を評価する評価装置４５３と、タスクをプロセッサに割り当てる割当装置４５４と、その実行を開始及び終了するタスクを選択する選択装置４５５と、実行のためタスクをスケジューリングし、実行中のタスクをデスケジューリングするスケジューラ５０１とを有する。制御割当ロジックモジュール４５１は、テレビチューナー４０３、メモリ４０５、長期記憶装置４０６、通信インタフェース４０７及びリモートインタフェース４０９に接続される。テレビチューナー４０３は、送信ライン４１１を介しテレビ信号を受信し、これらの信号は、アンテナ（図示せず）とケーブルテレビアウトレット（図示せず）の少なくとも１つからのものであってもよい。制御割当ロジックモジュール４５１は、ライン４１３を介しテレビ２０１にデータ、音声及び映像出力を提供するユーザインタフェース２０５を管理する。リモートインタフェース４０９は、無線接続４１５を介しリモートコントロールから信号を受信する。通信インタフェース４０７は、データパス４１７を介しウェブサーバなどの少なくとも１つのリモート処理システムとセットトップボックス２００との間のインタフェースをとる。通信インタフェース４１７は、電話モデム、ＩＳＤＮ（Ｉｎｔｅｇｒａｔｅ  Ｓｅｒｖｉｃｅ  Ｄｉｇｉｔａｌ  Ｎｅｔｗｏｒｋ）アダプタ、ｘＤＳＬ（Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）、ケーブルテレビモデム及び他の任意の適切なデータ通信装置の少なくとも１つである。図４Ｂの一例となるシステム４５０は、単なる説明のためのものである。本説明はあるセットトップボックス２００を説明するのに通常用いられる用語を参照しているが、本説明及びコンセプトは、図４Ｂに示されるものと類似しないアーキテクチャを有するシステムを含む他のコントロールプロセッサに等しく適用される。
【００４１】
好適な実施例では、制御割当ロジックモジュール４５１は、好適な実施例では、セットトップボックス２００の制御に関する複数のリアルタイムタスクをメモリ４０５を共有する複数のマルチプロセッサ４６０．１〜４６０．３に割り当てるよう構成される。これらのリアルタイムタスクは、チャンネル変更、ユーザインタフェース２０５に表示されるメニューオプションの選択、入力データストリームの復号化、長期記憶装置４０６を用いた入力データストリームの記録及び再生などを含む。セットトップボックスの動作は、セットトップボックス１００の特徴、ライン４１１を介した入力映像信号、ユーザインタフェース２０５を介したユーザ入力及び他の任意の補助入力に基づき、リアルタイムコントロールタスクにより決定される。
【００４２】
好適な実施例では、マルチプロセッサはメモリ４０５を共有する。これらマルチプロセッサ４６０．１〜４６０．３はそれぞれ、ＣＰＵ、コプロセッサ又は他の処理装置であってもよい。好適な実施例では、同一のタスクは、２つの（又はそれ以上の）プロセッサにより同時に実行されることはない。好適な実施例では、制御割当ロジックモジュールは、プロセッサ４６０．１〜４６０．３の全体のための単一のタスクマネージャを有する。これは、単なる説明のための集中化アプローチである。本発明は、集中化アプローチに制限されず、分散化アプローチが当業者により容易に想到されるかもしれない。
【００４３】
すべてのタスクτがあるプロセッサπに割り当てられるときは常に、タスク集合Γが、ｐ個の互いに素な集合Γ１〜Γｐに分割される（ただし、部分集合Γｋはプロセッサπｋに割り当てられる）。プロセッサπｋにより実行されるようなＦＰＰＳにおいてタスクの部分集合Γｋにより要求されるメモリの最大量が、式１の変形である式１ｓ’により与えられる。式１ｓ’の項ｎｋは、プロセッサπｋに割り当てられるタスクの個数（すなわち、部分集合Γｋの濃度）を示し、変数ｉは、Γｋのタスク上の範囲内である仮定する。
【００４４】
【数６】
2007519103.tif 000010
タスクの全体集合Γのトータルのメモリ要求ＭＰは、各タスクサブセットについて求められた結果を加えることによって決定される。式１ｍｆｉｘを参照されたい。
【００４５】
【数７】
2007519103.tif 000011
ＭＰが利用可能なメモリＭｓｙｓを超過しないとき、プロセッサの何れかへのタスクのスケジューリングを制限する必要はない。ＭＰがＭｓｙｓを超えるとき、１以上のタスクの１以上のプロセッサ上へのスケジューリングを制限するかもしれない。すべてのタスクの単一のプロセッサ上へのスケジューリングを制限する効果は、式２ｓの変形である式２ｓ’を用いて決定することができる。
【００４６】
【数８】
2007519103.tif 000012
すべてのタスクのすべてのプロセッサへのスケジューリングを制限する効果は、式２ｍｆｉｘにより決定することが可能であり、トータルのメモリ要求ＭＤは、各集合Γｋのメモリ要求ＭｋＤの和である。
【００４７】
【数９】
2007519103.tif 000013
明らかに、すべてのタスクをプロセッサのある部分集合に限定し、タスクの部分集合のみをプロセッサの部分集合に限定するなど、他の多数の中間的な実施例が存在する。
【００４８】
あるいは、すべてのタスクは、すべてのプロセッサ４６０．１〜４６０．３上で実行されてもよく、タスクのスケジューリングは制御割当ロジックモジュール４５１により実行される。非制限モードの最大メモリ要求ＭＰは同じままであり、すなわち、式１ｓを用いて決定することができる。
【００４９】
【数１０】
2007519103.tif 000014
制限モードは、式２ｓの変形を要する（すなわち、すべてのタスクが、それらのプリエンプションポイントにおいてのみプリエンプトされる）。
【００５０】
【数１１】
2007519103.tif 000015
なぜならば、ｐ個のタスクが現在ｐ個のプロセッサ上でパラレルに実行可能であるためである。このとき、トータルのメモリ要求ＭＤは、式２ｍｖａｒにより与えられる。
【００５１】
【数１２】
2007519103.tif 000016
式２ｍｖａｒはｎ≧ｐであることを仮定すると共に、式２ｍｖａｒがｎ≧ｐについてのみ有効であることに留意されたい。ｎ＜ｐの特別なケースでは、当該式は、
【００５２】
【数１３】
2007519103.tif 000017
に簡単化することができる。
【００５３】
明らかに、タスクの一部のみを制限するなど、多数の中間的な実施例が存在する。
【００５４】
一例として、２つのプロセッサ（すなわち、ｐ＝２）と３つのタスク（すなわち、ｎ＝３）のケースを検討する。これらのタスクは、上記テーブル１と２及びそれらに関する説明に記載されているものと同一の特徴（すなわち、メモリ要求）を有すると仮定される。非制限モードの最大メモリ要求ＭＰは同一を維持し、すなわち、式１を用いて決定することができ、従って、利用可能なメモリＭｓｙｓを超過する。式２ｍｖａｒを用いて、メモリベースプリエンプションの最大メモリ要求ＭＤは、
【００５５】
【数１４】
2007519103.tif 000018
となる。
【００５６】
メモリ要求は、利用可能なメモリより小さく、このことは、タスクがそれらのプリエンプションポイントにおいてのみプリエンプトされる場合、３つすべてのタスクが同時に実行可能であるということを意味する。
【００５７】
プロセッサのｓ個のペアワイズな互いに素である部分集合Ｐ１，．．．，Ｐｓが存在すると仮定する。すべてのタスクがあるプロセッササブセットＰｌに割り当てられているとする（１≦ｌ≦ｓ）。従って、タスクの集合は、ペアワイズな互いに素であるタスクのサブセットΓ１，．．．，Γｓに分割されてもよい。説明の簡単化のため、サブセットΓ１のタスクはτｉにより示され（１≦ｉ≦ｎｌ）、すなわち、タスクのサブセット毎のタスクが番号付けされる。上述された可変的割当と同様に、非制限モードのサブセットＰｌの最大メモリ要求ＭｌＰは、式１ｓ”を用いて決定可能である。
【００５８】
プロセッサπｋのサブセットＰｌにより実行される非制限モードによりタスクのサブセットΓｌにより求められる最大メモリ量は、式１の変形である式１ｓ”により与えられる。
【００５９】
【数１５】
2007519103.tif 000019
式１ｓ”は式１ｓ’と類似しているが、同一ではないことに留意されたい。ｌは前者の式のプロセッサのサブセットを範囲とし、ｋは後者の式のサブセットのプロセッサを範囲とする。ｓ個すべてのプロセッサのサブセットのトータルのメモリ要求ＭＰは、各サブセットの要求の和をとることによって求めることができる。
【００６０】
【数１６】
2007519103.tif 000020
ＭＰがＭｓｙｓを超過するとき、関連するプロセッササブセット上で実行されるタスクの１以上のサブセットの１以上のタスクのスケジューリングが限定される。ｐｌ個のプロセッサの単一のサブセットＰｌ上でのΓｌのすべてのｎｌ個のタスクのスケジューリングを制限する効果は、式２ｍｖａｒに類似した式２ｍｍｉｘを用いて決定することができる。
【００６１】
【数１７】
2007519103.tif 000021
式２ｍｖａｒと同様に、式２ｍｍｉｘは、ｎｌ≧ｐｌについてのみ成り立つ。
【００６２】
すべてのプロセッササブセット上のすべてのタスクサブセットのすべてのタスクのスケジューリングを制限する効果は、式２ｍｍｉｘ‘により決定することが可能であり、ＭＤのトータルメモリ要求は各プロセッササブセットＰｌのメモリ要求ＭｌＤの和である。
【００６３】
【数１８】
2007519103.tif 000022
上述された固定的割当及び可変的割当のケースに関して、混合的割当について、すべてのタスクがそれらのプリエンプションポイントにおいてのみプリエンプトされるメモリベースプリエンプションモードと非制限モードとの間の多数の中間的な手段が存在する。
【００６４】
本発明の好適な実施例が図示及び説明されたが、本発明の真の範囲から逸脱することなく、様々な変更及び改良が可能であり、それの要素について均等なものと置換されるかもしれないということは、当業者によって理解されるであろう。さらに、その中心的な範囲から逸脱することなく、本発明の教示をある状況に適応させるための多数の改良が可能である。従って、本発明は、本発明を実行するのに想定されるベストモードとして開示された特定の実施例に限定されるものではなく、本発明は添付した請求項の範囲内に属するすべての実施例を含むことが意図される。
【図面の簡単な説明】
【００６５】
【図１】図１は、本発明の実施例によるタスクインタフェースのコンポーネントの概略図を示す。
【図２】図２は、本発明の実施例が動作するデジタルテレビシステムの一例の概略図を示す。
【図３】図３は、シングルプロセッサについて図１に示されたタスクインタフェースのコンポーネント間の関係の概略図を示す。
【図４Ａ】図４Ａは、シングルプロセッサシステムの図２のセットトップボックスを構成するコンポーネントを示す。
【図４Ｂ】図４Ｂは、マルチプロセッサシステムの図２のセットトップボックスを構成するコンポーネントを示す。
【図５】図５は、図２及び４Ａに示されるセットトップボックスのプロセッサのコンポーネントを示す。
【図１】
2007519103.tif 000023
【図２】
2007519103.tif 000024
【図３】
2007519103.tif 000025
【図４Ａ】
2007519103.tif 000026
【図４Ｂ】
2007519103.tif 000027
【図５】
2007519103.tif 000028
【国際調査報告】
2007519103.tif 000029
2007519103.tif 000030
2007519103.tif 000031
2007519103.tif 000032
2007519103.tif 000033
2007519103.tif 000034