(57)【特許請求の範囲】
【請求項１】
タスクを前記タスクの実行を可能にするように複数のハードウェアスレッドのうちのハードウェアスレッドに割り当てるように構成されたマルチスレッドプロセッサの第１のハードウェアスレッドにおいて割り込みを受信するステップを有し、
前記第１のハードウェアスレッドは、第１の時間における前記マルチスレッドプロセッサにおける前記複数のハードウェアスレッドに割り当てられた複数のタスクのうちの最低優先度タスクの第１のハードウェアスレッドによる実行に基づいて特定され、
前記第１のハードウェアスレッドにおける前記割り込みの受信に基づいて、前記第１のハードウェアスレッドにおいて割り込みルーチンを開始して実行可能タスクリストから最高優先度タスクを選択するステップと、
前記マルチスレッドプロセッサの第２のハードウェアスレッドを識別するステップとをさらに有し、
前記第２のハードウェアスレッドは、前記第１の時間の後に発生する第２の時間における前記マルチスレッドプロセッサにおける前記複数のハードウェアスレッドに割り当てられた複数のタスクのうちの最低優先度タスクの第２のハードウェアスレッドによる実行に基づいて特定され、
後続の割り込みを前記第２のハードウェアスレッドにマッピングするステップをさらに有する方法。
【請求項２】
前記割り込みは、少なくとも１つのタスクが実行される準備ができていることを示す請求項１に記載の方法。
【請求項３】
前記第１の時間において、アイドルタスクが前記第１のハードウェアスレッドに割り当てられる請求項１に記載の方法。
【請求項４】
前記割り込みルーチンを実行することが、前記実行可能タスクリストからの前記最高優先度タスクの第１の優先度を、実行中タスクリストからの最低優先度タスクの第２の優先度と比較することを含み、前記実行中タスクリストが、前記マルチスレッドプロセッサの前記複数のハードウェアスレッドに割り当てられた１つ以上のタスクを記憶するように構成され、前記割り込みルーチンを実行することが、前記第１の優先度が前記第２の優先度より高い場合に前記最高優先度タスクと前記最低優先度タスクをスワップすることをさらに含む請求項１に記載の方法。
【請求項５】
前記第１の優先度が前記第２の優先度より高い場合に前記最高優先度タスクと前記最低優先度タスクをスワップした後、前記第１のハードウェアスレッドにおいて前記実行可能タスクリストからの前記最高優先度タスクを実行することと、以前に前記第１のハードウェアスレッドに割り当てられた前記最低優先度タスクを前記実行可能タスクリストに加えることとをさらに含む請求項４に記載の方法。
【請求項６】
前記複数のハードウェアスレッドに割り当てられた前記複数のタスクのうちの前記後続の最低優先度実行中タスクを判断するステップと、
前記割り込みルーチンを使用して前記後続の割り込みを前記第２のハードウェアスレッドにマッピングするステップと、をさらに有し、
前記第２のハードウェアスレッドは前記複数のハードウェアスレッドに割り当てられた前記複数のタスクのうちの前記後続の最低優先度実行中タスクを実行している請求項５に記載の方法。
【請求項７】
スケジュールを確認していずれかの実行可能タスクが前記複数のハードウェアスレッドに割り当てられた前記複数のタスクのうちの前記後続の最低優先度実行中タスクより高い優先度を有するかどうかを判断した結果に基づいて、前記後続の割り込みを選択的に設定するステップをさらに有する請求項６に記載の方法。
【請求項８】
前記第１のハードウェアスレッドが前記割り込みを受信できるようにするために、前記マルチスレッドプロセッサの割り込みコントローラが、前記複数のハードウェアスレッドのうちの前記第１のハードウェアスレッド以外のハードウェアスレッドが前記割り込みを受信することからマスクされるように指示するステップをさらに有する請求項１に記載の方法。
【請求項９】
タスクを前記タスクの実行を可能にするようにハードウェアスレッドに割り当てるように構成されたマルチスレッドプロセッサのハードウェアスレッドのセットのうちの第１のハードウェアスレッドにおいて割り込みを受信するステップを有し、前記ハードウェアスレッドのセットの各ハードウェアスレッドは、実行中タスクのセットのそれぞれのタスクを実行し、前記実行中タスクのセットの各タスクおよび実行可能タスクのセットの各タスクは、それぞれの優先度を有し、
前記第１のハードウェアスレッドにおける前記割り込みの受信の後で、前記実行中タスクのセットの各タスクが前記実行可能タスクのセットの全てのタスクの優先度より大きいかまたはそれに等しい優先度を有するまで、前記実行中タスクのセットのうちの最低優先度タスクを前記実行可能タスクのセットのうちの最高優先度タスクと反復的にスワップするステップをさらに有する方法。
【請求項１０】
前記反復的スワップの各反復は、前記実行中タスクのセットのうちの前記最低優先度タスクを前記実行可能タスクのセットのうちの前記最高優先度タスクとスワップした後、
前記実行中タスクのセットのうちの後続の最低優先度タスクを判断するステップと、
前記実行中タスクのセットのうちの前記後続の最低優先度タスクの後続の最低優先度が、前記実行可能タスクのセットのうちの後続の最高優先度タスクの後続の最高優先度より小さいとき、後続の割り込みを、前記実行中タスクのセットのうちの前記後続の最低優先度タスクを実行する特定のハードウェアスレッドに出力して、前記反復的スワップの次の反復を実行するステップとを含む請求項９に記載の方法。
【請求項１１】
タスクを前記タスクの実行を可能にするように複数のハードウェアスレッドのうちのハードウェアスレッドに割り当てるように構成され、前記複数のハードウェアスレッドが最高優先度タスクを実行しているように前記複数のハードウェアスレッドを実行するように構成され、そして、前記複数のハードウェアスレッドに割り当てられた複数のタスクのうちの最低優先度タスクを、前記複数のハードウェアスレッドのうちの前記最低優先度タスクを実行する特定のハードウェアスレッドが割り込みを受信した後、前記複数のハードウェアスレッドに割り当てられたすべてのタスクがすべての実行可能タスクの最高優先度と少なくとも同じ高さの優先度を有するように、最高優先度実行可能タスクとスワップすることによって、１つ以上のタスクをスケジュールするように構成されたマルチスレッドプロセッサを備えるシステム。
【請求項１２】
前記マルチスレッドプロセッサは、前記複数のハードウェアスレッドのうちの前記最低優先度タスクを実行する特定のハードウェアスレッドが、前記割り込みを受信した後に、割り込みルーチンを起動して実行可能タスクリストから最高優先度タスクを選択するように構成された請求項１１に記載のシステム。
【請求項１３】
前記マルチスレッドプロセッサは、タスクをそれぞれスワップして、実行可能タスクリストの最高優先度タスクを前記複数のハードウェアスレッドのうちの特定のハードウェアスレッドに割り当て、前記最低優先度タスクを前記実行可能タスクリストに加えた後、スケジュールが確認されて、前記実行可能タスクリストのうちのいずれかの実行可能タスクが前記複数のハードウェアスレッドに割り当てられたいずれかのタスクより高い優先度を有するかどうかを判断するように構成された請求項１１に記載のシステム。
【請求項１４】
第１のデータ構造が、前記複数のハードウェアスレッドに割り当てられたタスクの優先順位付けされた実行中タスクリストを含み、第２のデータ構造が、前記複数のハードウェアスレッドに割り当てられる準備ができているタスクの優先順位付けされた実行可能タスクリストを含む請求項１１に記載のシステム。
【請求項１５】
割り込みを、前記複数のハードウェアスレッドのうちの前記第１のデータ構造の前記優先順位付けされた実行中タスクリストからの最低優先度タスクを実行している特定のハードウェアスレッドにマッピングするように構成された割り込みコントローラをさらに備える請求項１４に記載のシステム。
【請求項１６】
割り込みマスクは、割り込みを前記複数のハードウェアスレッドのうちの特定のハードウェアスレッドにマッピングするように構成され、前記複数のハードウェアスレッドのうちの前記特定のハードウェアスレッドは、前記第１のデータ構造の前記優先順位付けされた実行中タスクリストからの最低優先度タスクを実行している請求項１４に記載のシステム。
【請求項１７】
前記最高優先度タスクを前記第２のデータ構造の前記優先順位付けされた実行可能タスクリストから前記第１のデータ構造の前記優先順位付けされた実行中タスクリストに移動して、前記最高優先度タスクを前記特定のハードウェアスレッドに割り当て、スケジュールを確認して前記第２のデータ構造中のいずれかの実行可能タスクが前記第１のデータ構造中の最低優先度実行中タスクより高い優先度を有するかどうかを判断するように構成されたスケジューラをさらに備える請求項１５に記載のシステム。
【請求項１８】
前記複数のハードウェアスレッドのうちの前記特定のハードウェアスレッドは、アイドルタスクと関連付けられたアイドルハードウェアスレッドである請求項１７に記載のシステム。
【請求項１９】
マルチスレッドプロセッサを備えるコンピュータに、
タスクを前記タスクの実行を可能にするように前記マルチスレッドプロセッサの複数のハードウェアスレッドのうちのハードウェアスレッドに割り当てるように構成された前記複数のハードウェアスレッドのうちの、最低優先度タスクを実行している特定のハードウェアスレッドを判定させると共に、
割り込みを前記複数のハードウェアスレッドのうちの前記特定のハードウェアスレッドにマッピングさせるように実行可能であるコンピュータ実行可能命令を含むコンピュータ読み取り可能な媒体であって、
前記割り込みは、少なくとも１つのタスクが実行される準備ができていることを示し、前記複数のハードウェアスレッドのうちの前記特定のハードウェアスレッドは、前記割り込みを受信し、前記割り込みに基づいて割り込みルーチンを開始して実行可能タスクリストから最高優先度タスクを選択するコンピュータ読み取り可能な媒体。
【請求項２０】
前記コンピュータ実行可能命令は、前記コンピュータに、
タスクをスワップさせて、前記実行可能タスクリストからの前記最高優先度タスクを前記複数のハードウェアスレッドのうちの前記特定のハードウェアスレッドに割り当てさせ、前記最低優先度タスクを前記実行可能タスクリストに加えさせた後、スケジュールを確認させていずれかの実行可能タスクがいずれかの実行中タスクより高い優先度を有するかどうかを判断させるようにさらに実行可能であり、前記スケジュールを確認させていずれかの実行可能タスクがいずれかの実行中タスクより高い優先度を有するかどうかを判断させることは、新しい最低優先度実行中タスクを新しい最高優先度実行可能タスクと比較させることを含み、
前記コンピュータ実行可能命令は、前記コンピュータに、割り込みルーチンを使用させて、後続の割り込みを、前記複数のハードウェアスレッドのうちの前記新しい最低優先度実行中タスクを実行している新しい特定のハードウェアスレッドにマッピングさせ、
前記スケジュールを確認させていずれかの実行可能タスクが前記新しい最低優先度実行中タスクより高い優先度を有するかどうかを判断させた結果に基づいて、前記後続の割り込みを選択的に出力させるようにさらに実行可能である請求項１９に記載のコンピュータ読み取り可能な媒体。
【請求項２１】
タスクを前記タスクの実行を可能にするようにハードウェアスレッドのセットのうちのハードウェアスレッドに割り当てるように構成されたマルチスレッドプロセッサの前記ハードウェアスレッドのセットのうちの第１のハードウェアスレッドにおいて割り込みを受信するための手段を備え、前記ハードウェアスレッドのセットの各ハードウェアスレッドは、実行中タスクのセットのそれぞれのタスクを実行し、前記実行中タスクのセットの各実行中タスクおよび実行可能タスクのセットの各実行可能タスクは、それぞれの優先度を有し、
前記割り込みに基づいて、前記実行中タスクのセットの各実行中タスクが前記実行可能タスクのセットの全ての実行可能タスクの優先度より大きいかまたはそれに等しい優先度を有するまで、前記実行中タスクのセットのうちの最低優先度タスクを前記実行可能タスクのセットのうちの最高優先度タスクと反復的にスワップするための手段をさらに備える装置。
【請求項２２】
前記マルチスレッドプロセッサは処理システムに含まれ、前記処理システムは複数の命令実行ユニットを備える請求項１に記載の方法。
【請求項２３】
前記マルチスレッドプロセッサは、最高第２の数までのタスクを処理するように、インターリーブされた方法で同時に実行可能である第１の数のハードウェアスレッドを備え、前記第１の数のハードウェアスレッドのうちの各ハードウェアスレッドは、実行のために単一の対応するタスクに割り当てられると共に、前記第１の数と前記第２の数は同じである請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、リアルタイムマルチスレッドスケジューラおよびスケジューリング方法を対象とする。
【背景技術】
【０００２】
技術の進歩により、コンピューティングデバイスは、より小型でより強力になった。たとえば、現在、小型で軽量な、ユーザが容易に持ち運べる携帯型無線電話、携帯情報端末(PDA)、およびページングデバイスなどの無線コンピューティングデバイスを含む様々な携帯型パーソナルコンピューティングデバイスが存在する。より具体的には、セルラー電話やインターネットプロトコル(IP)電話などの携帯型無線電話は、音声およびデータパケットを無線ネットワークを介して伝達することができる。さらに、多くのそのような無線電話は、その中に組み込まれた他のタイプのデバイスを含む。たとえば、無線電話は、デジタルスチルカメラ、デジタルビデオカメラ、デジタルレコーダ、およびオーディオファイルプレーヤをも含むことができる。また、そのような無線電話は、ウェブブラウザアプリケーションなど、インターネットにアクセスするために使用できるソフトウェアアプリケーションを含む実行可能命令を処理することができる。したがって、これらの無線電話はかなりの計算能力を含むことができる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
デジタル信号プロセッサ(DSP)、画像プロセッサ、および他の処理デバイスは、携帯型パーソナルコンピューティングデバイスにおいて頻繁に使用され、オペレーティングシステムと連携して動作する。リアルタイムオペレーティングシステム(RTOS)の1つの要件は、厳しい優先度スケジューリングである。シングルプロセッサ上では、この要件は、最高優先度実行可能タスクをスケジュールすべきであるということである。一般に、複数の中央処理ユニット(CPU)をもつマルチスレッドまたはマルチプロセッサシステムでは、特定のタスクが特定のハードウェアスレッドまたはCPUに結合され、シングルプロセッサスケジューラアルゴリズムが各ハードウェアスレッドまたはCPU上で独立して実行される。この手法は、最高優先度実行可能タスクを全体的にスケジュールすべきであるというRTOS制約条件を満たさず、どのハードウェアスレッドまたはCPUが先にタスクをスケジュールすべきかの知識という、入手可能でないことがある知識を必要とする。
【課題を解決するための手段】
【０００４】
特定の一実施形態では、第1のスレッドにおいて割り込みを受信するステップを含む方法が開示され、第1のスレッドは、第1の時間におけるプロセッサにおける複数の実行中スレッド(executing thread)のうちの最低優先度スレッドを含む。本方法はまた、第2のスレッドを識別するステップを含み、第2のスレッドは、第2の時間におけるプロセッサにおける複数の実行中スレッドのうちの最低優先度スレッドを含む。本方法はさらに、後続の割り込みを第2のスレッドに向けるステップを含む。
【０００５】
別の実施形態では、スレッドのセットのうちの第1のスレッドにおいて割り込みを受信するステップを含む方法が開示される。スレッドのセットの各スレッドは、実行中タスク(executing task)のセットのそれぞれのタスクを実行する。実行中タスクのセットの各タスクおよび実行可能タスク(ready task)のセットの各タスクは、それぞれの優先度を有する。本方法はまた、実行中タスクのセットの各タスクは、実行可能タスクのセットのあらゆるタスクの優先度よりも大きいかまたはそれに等しい優先度を有するまで、実行中タスクのセットのうちの最低優先度タスクを実行可能タスクのセットのうちの最高優先度タスクと反復的にスワップするステップを含む。
【０００６】
別の実施形態では、複数の実行中スレッドが最高優先度タスクを実行しているように複数のスレッドを実行するように構成されたマルチスレッドプロセッサを含むシステムが開示される。マルチスレッドプロセッサは、実行中タスクがすべての実行可能タスクの最高優先度と少なくとも同じ高さの優先度を有するようにタスクをスケジュールするように構成される。
【０００７】
別の実施形態では、コンピュータ読み取り可能な媒体が開示される。コンピュータ読み取り可能な媒体は、コンピュータに、割り込みを複数の実行中スレッドのうちの最低優先度スレッドに向けさせるように実行可能であるコンピュータ実行可能命令を含んでいる。割り込みは、少なくとも1つのタスクが実行される準備ができていることを示す。複数の実行中スレッドのうちの最低優先度スレッドは、最低優先度タスクを実行しているかまたはアイドルスレッドであるかのいずれかである。複数の実行中スレッドのうちの最低優先度スレッドは、割り込みを受信し、割り込みルーチンを開始して実行可能タスクリストから最高優先度タスクを選択する。
【０００８】
開示する実施形態によって与えられる1つの特定の利点は、割り込みからの妨げが軽減されて最高優先度スレッドが実行されるようにタスクがスケジュールされることである。優先度の低いスレッドが割り込みを受信するので、再スケジュール割り込みを起こすと、自動的に、最高優先度スレッドを妨げることなしに優先度の低いスレッドを再スケジュールする。さらに、外部割り込みは、最高優先度スレッドではなく最低優先度スレッドに割り込みをかける。
【０００９】
開示する実施形態によって与えられる別の特定の利点は、複数のタスクが、実行する準備が整えられ、2つ以上の実行中タスクよりも優先度が高いシナリオでは、優先度の低い実行中タスクは、最小数のスワップを用いて、他の優先度の高い実行中タスクへのオーバーヘッドなしに、新しいより高い優先度のタスクとスワップされることである。
【００１０】
開示する実施形態によって与えられる別の利点は、割り込みハンドラスレッドの優先度を、現在実行中スレッドの優先度と直接比較することができることである。現在実行中スレッドが割り込みハンドラスレッドよりも低い優先度を有する場合、割り込みハンドラスレッドは直ちにスケジュールされ得る。
【００１１】
本開示の他の態様、利点、および特徴は、以下のセクション、すなわち、図面の簡単な説明、発明を実施するための形態、および特許請求の範囲を含む、本出願全体の検討後に明らかになろう。
【図面の簡単な説明】
【００１２】
【図１】処理システムの特定の例示的な実施形態のブロック図である。
【図２】最低優先度実行中スレッドに向けられた割り込みを示す、処理システムの別の特定の例示的な実施形態のブロック図である。
【図３】タスクスワップを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図４】最低優先度実行中スレッドに向けられた別の割り込みを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図５】実行可能タスクリストから実行中タスクリストに移動しているタスクを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図６】最低優先度実行中スレッドに向けられた別の割り込みを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図７】タスクスワップを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図８】最低優先度実行中スレッドに向けられた別の割り込みを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図９】タスクスワップを示す、図２の処理システムの特定の例示的な実施形態のブロック図である。
【図１０Ａ】マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第1の例示的な実施形態の流れ図である。
【図１０Ｂ】スケジューラアルゴリズムの流れ図である。
【図１０Ｃ】スケジューラ確認の流れ図である。
【図１１】マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第2の例示的な実施形態の流れ図である。
【図１２】マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第3の例示的な実施形態の流れ図である。
【図１３】マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第4の例示的な実施形態の流れ図である。
【図１４】リアルタイムマルチスレッドスケジューラモジュールを含む携帯型通信デバイスの特定の一実施形態のブロック図である。
【発明を実施するための形態】
【００１３】
図１を参照すると、処理システムの特定の例示的な実施形態が示され、全体的に100と称される。マルチスレッドプロセッサ100は、バスインタフェース108を介して命令キャッシュ110に結合されたメモリ102を含む。マルチスレッドプロセッサ100はまた、バスインタフェース108を介してメモリ102に結合されたデータキャッシュ112を含む。命令キャッシュ110はバス111を介してシーケンサ114に結合される。特定の一例では、シーケンサ114は汎用割り込み116を受信することもでき、その汎用割り込み116は割り込みレジスタ(図示せず)から取り出され得る。特定の一実施形態では、命令キャッシュ110は複数のカレント命令レジスタを介してシーケンサ114に結合され得、それらのカレント命令レジスタは、バス111に結合され、マルチスレッドプロセッサ100の特定のスレッドに関連付けられ得る。特定の一実施形態では、マルチスレッドプロセッサ100は、6つのスレッドを含むインターリーブ型マルチスレッドプロセッサである。
【００１４】
特定の一実施形態では、バス111は64ビットバスであり、シーケンサ114は、それぞれ32ビット長を有する複数の命令を含む命令パケットを介してメモリ102から命令を取り出すように構成される。バス111は、第1の命令実行ユニット118と、第2の命令実行ユニット120と、第3の命令実行ユニット122と、第4の命令実行ユニット124とに結合される。各命令実行ユニット118、120、122、124は、第2のバス128を介して汎用レジスタファイル126に結合され得る。汎用レジスタファイル126はまた、第3のバス130を介してシーケンサ114と、データキャッシュ112と、メモリ102とに結合され得る。
【００１５】
マルチスレッドプロセッサ100はまた、1つまたは複数の優先度設定を記憶するためのスーパバイザ制御レジスタ132を含み得、それらの優先度設定は、処理スレッドの各々においてどのタスクを実行すべきかを判断するためにリアルタイム優先度スケジューラ158と割り込みコントローラ156とを含む制御ユニット150によってアクセスされ得る。リアルタイム優先度スケジューラ158はソフトウェアルーチンとして実装され得る。各処理スレッドは、特定のスレッドに専用のスーパバイザ状態レジスタに記憶される1つまたは複数のビット値など、1つまたは複数の関連する優先度設定を有し得る。
【００１６】
動作中、マルチスレッドプロセッサ100は、複数の実行中スレッドが最高優先度タスクを実行しているように複数のスレッドを実行し、マルチスレッドプロセッサ100は、すべての実行中タスクがすべての実行可能タスクの最高優先度と少なくとも同じ高さの優先度を有するようにタスクをスケジュールする。特定の一実施形態では、リアルタイム優先度スケジューラ158は、すべての実行中タスクがすべての実行可能タスクの最高優先度と少なくとも同じ高さの優先度を有するようにタスクをスケジュールする。特定の一実施形態では、マルチスレッドプロセッサ100は、複数の実行中スレッドのうちの最低優先度スレッドに向けられた割り込みが、複数の実行中スレッドのうちの最高優先度スレッドの性能に影響を及ぼさないように構成される。たとえば、割り込みコントローラ156は、複数の実行中スレッドのうちの最低優先度スレッドに向けられた割り込みが、複数の実行中スレッドのうちの最高優先度スレッドの性能に影響を及ぼさないように構成され得る。本明細書で使用する割り込みは、通常の実行を停止し、特殊ハンドラの実行を開始するいかなるものでもあり得る。割り込みは、通常のプログラムフローのいかなる中断をも意味し得る。
【００１７】
特定の一実施形態では、マルチスレッドプロセッサ100は、複数の実行中スレッドのうちの最低優先度スレッドが、割り込みを受信し、割り込みルーチンを実行して実行可能タスクリストから最高優先度タスクを選択するように構成される。たとえば、割り込みコントローラ156は、複数の実行中スレッドのうちの最低優先度スレッドが割り込みを受信し、リアルタイム優先度スケジューラ158が割り込みルーチンを実行して実行可能タスクリストから最高優先度タスクを選択することができるように構成され得る。割り込みロジックは、最低優先度スレッドのみが割り込みを受け取ることが可能であるように構成され得る。特定の一実施形態では、マルチスレッドプロセッサ100は、実行可能タスクリストの最高優先度タスクを実行し、前の実行中タスクを実行可能タスクリストに戻すためのタスクの各スワップの後に、スケジュールを確認していずれかの実行可能タスクがいずれかの実行中タスクよりも高い優先度を有するかどうかを判断するように構成され得る。たとえば、リアルタイム優先度スケジューラ158は、実行可能タスクリストの最高優先度タスクを実行し、前の実行中タスクを実行可能タスクリストに戻すためのタスクの各スワップの後に、スケジュールを確認していずれかの実行可能タスクがいずれかの実行中タスクよりも高い優先度を有するかどうかを判断し得る。
【００１８】
特定の一実施形態では、マルチスレッドプロセッサ100は、更新されたスケジュールのあらゆる実行中タスクが実行可能タスクの最高優先度と少なくとも同じ高さの優先度を有するように、実行中タスクと実行可能タスクとの可能な最小数のスワップを使用してスケジュールが更新されるように構成される。たとえば、リアルタイム優先度スケジューラ158は、更新されたスケジュールのあらゆる実行中タスクが実行可能タスクの最高優先度と少なくとも同じ高さの優先度を有するように、実行中タスクと実行可能タスクとの可能な最小数のスワップを使用してスケジュールが更新されるように構成され得る。
【００１９】
図２を参照すると、処理システムの特定の例示的な実施形態が示され、全体的に200と称される。特定の一実施形態では、マルチスレッドプロセッサ200は、図１のマルチスレッドプロセッサ100と実質的に同様である。マルチスレッドプロセッサ200は、割り込みコントローラ204と、割り込みマスク220と、第1のデータ構造206と、第2のデータ構造210とに結合されたリアルタイム優先度スケジューラ202を含む。第1のデータ構造206は、複数の実行中スレッド214上で実行されているタスクの優先順位付けされた実行中タスクリスト208を含む。タスクは、0が最高優先度タスクを示し、1が次に高い優先度タスクを示すなど、それぞれの優先度によって示されている。特定の一実施形態では、アイドルタスクが最低優先度を有する。第2のデータ構造210は、複数の実行中スレッド214上で実行する準備ができているタスクの優先順位付けされた実行可能タスクリスト212を含む。割り込みコントローラ204は、矢印218によって示されるように、割り込みを複数の実行中スレッド214のうちの最低優先度スレッドに向けるように構成され得る。割り込みマスク220は、割り込みを受信するための各スレッドの利用可能性を示すためのビットマスクとすることができる。特定の一実施形態では、割り込みマスク220は、矢印218によって示されるように、割り込みを複数の実行中スレッド214のうちの最低優先度スレッドに向けるように構成され得る。
【００２０】
リアルタイム優先度スケジューラ202は、最高優先度タスクを第2のデータ構造210の優先順位付けされた実行可能タスクリスト212から第1のデータ構造206の優先順位付けされた実行中タスクリスト208に移動して割り込まれた最低優先度スレッド上で最高優先度タスクを実行するように構成され得る。リアルタイム優先度スケジューラ202はまた、スケジュール222を確認して第2のデータ構造210中のいずれかの実行可能タスクが第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断するように構成され得る。スケジュール222を確認することは、第1のデータ構造206と第2のデータ構造210とを検査して第2のデータ構造210中のいずれかの実行可能タスクが第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断することを含み得る。特定の一実施形態では、複数の実行中スレッド214のうちの最低優先度スレッドは、第1のデータ構造206の優先順位付けされた実行中タスクリスト208からの最低優先度タスクを実行している。たとえば、図２において6の優先度をもつタスクを実行しているスレッドが最低優先度スレッドであり得る。
【００２１】
動作中、矢印216によって示されるように、複数の実行中スレッド214上で実行されている4の優先度をもつ2つのタスクのうちの一方が、2の優先度をもつタスクを起動または「ウェイクアップ」することができる。この優先度2のタスクは、第2のデータ構造210の優先順位付けされた実行可能タスクリスト212上に現れている。割り込みマスク220は、優先度6のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフする。割り込みコントローラ204は、優先度2のタスクの起動またはウェイクアップに応答して、矢印218によって示されるように、割り込みを、複数の実行中スレッド214のうちの最低優先度スレッドである優先度6のタスクを実行しているスレッドに向け得る。
【００２２】
図３を参照すると、リアルタイム優先度スケジューラ202は、矢印300によって示されるように、最高優先度タスクである優先度2のタスクを第2のデータ構造210の優先順位付けされた実行可能タスクリスト212から第1のデータ構造206の優先順位付けされた実行中タスクリスト208に移動して、割り込まれた最低優先度スレッド上で最高優先度タスクである優先度2のタスクを実行し得る。矢印300によって示されるように、タスクをスワップして、優先順位付けされた実行可能タスクリスト212からの最高優先度タスクである優先度2のタスクを実行し、前の実行中タスクである優先度6のタスクを優先順位付けされた実行可能タスクリスト212に戻した後、リアルタイム優先度スケジューラ202は、スケジュール222を確認して第2のデータ構造210中のいずれかの実行可能タスクが第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断し得る。図３では、矢印300によって示されるタスクのスワップの後、第2のデータ構造210中の実行可能タスクは、優先度6または優先度8のいずれかを有し、第1のデータ構造206中の最低優先度実行中タスクは2つの優先度4のタスクであり、したがって、第2のデータ構造210中の実行可能タスクのいずれも、第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有しない。割り込みマスク220は、優先度4のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフする。
【００２３】
図４を参照すると、動作の別の例として、矢印400によって示されるように、複数の実行中スレッド214上で実行されている6の優先度をもつタスクは、2の優先度をもつタスクと4の優先度をもつ2つのタスクとを起動または「ウェイクアップ」することができる。優先度2のタスクと2つの優先度4のタスクとは、第2のデータ構造210の優先順位付けされた実行可能タスクリスト212上に現れている。割り込みマスク220は、アイドルである最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフする。タスクの起動またはウェイクアップに応答して、割り込みコントローラ204は、矢印402によって示されるように、割り込みを複数の実行中スレッド214のうちの最低優先度スレッドに向け得る。特定の一実施形態では、複数の実行中スレッド214のうちの最低優先度スレッドは、そのアイドル状態により、第1のデータ構造206の優先順位付けされた実行中タスクリスト208上で最低優先度を有すると定義されるアイドルタスクを実行しているアイドルスレッドである。
【００２４】
図５を参照すると、図４のリアルタイム優先度スケジューラ202は、矢印500によって示されるように、割り込まれた最低優先度スレッド上で、最高優先度タスクである優先度2のタスクを実行するために、最高優先度タスクである優先度2のタスクを第2のデータ構造210の優先順位付けされた実行可能タスクリスト212から第1のデータ構造206の優先順位付けされた実行中タスクリスト208に移動し得る。矢印500によって示されるように、優先順位付けされた実行可能タスクリスト212から最高優先度タスクである優先度2のタスクを移動した後、リアルタイム優先度スケジューラ202は、スケジュール222を確認して第2のデータ構造210中のいずれかの実行可能タスクが第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断し得る。図５では、矢印500によって示されるタスクの移動後、第2のデータ構造210中の実行可能タスクは両方とも優先度4を有し、第1のデータ構造206中の最低優先度実行中タスクは優先度8のタスクであり、したがって、第2のデータ構造210中の実行可能タスクの両方は、第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有する。割り込みマスク220は、優先度8のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフする。
【００２５】
図６を参照すると、2つの優先度4のタスクが、第2のデータ構造210の優先順位付けされた実行可能タスクリスト212上に残っている。割り込みマスク220は、優先度8のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフしている。割り込みコントローラ204は、矢印600によって示されるように、割り込みを、複数の実行中スレッド214のうちの最低優先度スレッドである、優先度8のタスクを実行しているスレッドに向け得る。
【００２６】
図７を参照すると、リアルタイム優先度スケジューラ202は、矢印700によって示されるように、割り込まれた最低優先度スレッド上で最高優先度タスクである優先度4のタスクのうちの一方を実行するために、最高優先度タスクである優先度4のタスクのいずれかを第2のデータ構造210の優先順位付けされた実行可能タスクリスト212から第1のデータ構造206の優先順位付けされた実行中タスクリスト208に移動し得る。矢印700によって示されるように、タスクをスワップして、優先順位付けされた実行可能タスクリスト212からの最高優先度タスクである優先度4のタスクのうちの一方を実行し、前の実行中タスクである優先度8のタスクを優先順位付けされた実行可能タスクリスト212に戻した後、リアルタイム優先度スケジューラ202は、スケジュール222を確認して第2のデータ構造210中のいずれかの実行可能タスクが第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断し得る。図７では、矢印700によって示されるタスクのスワップの後、第2のデータ構造210中の実行可能タスクは優先度4および優先度8を有し、第1のデータ構造206中の最低優先度実行中タスクは優先度6のタスクであり、したがって、第2のデータ構造210中の実行可能タスクのうちの一方、すなわち、優先度4のタスクは、第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有する。割り込みマスク220は、優先度6のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフする。
【００２７】
図８を参照すると、優先度4のタスクが、優先度8のタスクとともに第2のデータ構造210の優先順位付けされた実行可能タスクリスト212上に残っている。割り込みマスク220は、優先度6のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフしている。図７の矢印700によって示されるタスクスワップに応答して、割り込みコントローラ204は、矢印800によって示されるように、割り込みを、複数の実行中スレッド214のうちの最低優先度スレッドである、優先度6のタスクを実行しているスレッドに向け得る。
【００２８】
図９を参照すると、リアルタイム優先度スケジューラ202は、矢印900によって示されるように、割り込まれた最低優先度スレッド上で、最高優先度タスクである優先度4のタスクを実行するために、最高優先度タスクである優先度4のタスクを第2のデータ構造210の優先順位付けされた実行可能タスクリスト212から第1のデータ構造206の優先順位付けされた実行中タスクリスト208に移動し得る。矢印900によって示されるように、タスクをスワップして、優先順位付けされた実行可能タスクリスト212からの最高優先度タスクである優先度4のタスクを実行し、前の実行中タスクである優先度6のタスクを優先順位付けされた実行可能タスクリスト212に戻した後、リアルタイム優先度スケジューラ202は、スケジュール222を確認して第2のデータ構造210中のいずれかの実行可能タスクが第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断し得る。図９では、矢印900によって示されるタスクのスワップの後、第2のデータ構造210中の実行可能タスクは優先度6および優先度8を有し、第1のデータ構造206中の最低優先度実行中タスクは優先度4のタスクであり、したがって、第2のデータ構造210中の実行可能タスクのいずれも、第1のデータ構造206中の最低優先度実行中タスクよりも高い優先度を有しない。割り込みマスク220は、優先度4のタスクを実行している最低優先度スレッドを除いて、割り込みコントローラ204から複数の実行中スレッド214上で実行されているすべてのタスクをマスクオフする。
【００２９】
図１０Ａを参照すると、マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第1の例示的な実施形態の流れ図が示され、全体的に1000と称される。特定の一実施形態では、方法1000は図１のマルチスレッドプロセッサ100上で実装される。方法1000は、1002において、割り込みを受信するステップと、割り込まれたタスクからのコンテキストを保存するステップとを含む。方法1000はまた、1004において、実行可能キューへの割り込みを待っている1つまたは複数のタスクを追加するステップを含む。特定の一実施形態では、実行可能キューは、複数の実行中スレッド214上で実行する準備ができているタスクの優先順位付けされた実行可能タスクリスト212を含む、図２に示す第2のデータ構造210に対応する。
【００３０】
方法1000はさらに、1006において、図１０Ｂに示すスケジューラアルゴリズムを実行するステップを含む。方法1000はまた、1008において、コンテキストを復元するステップと、割り込まれない演算に戻るステップとを含む。スケジューラは、割り込まれたタスクに戻る前に他のタスクを実行することがあるので、コンテキストを復元するステップと、割り込まれない演算に戻るステップとは後の時点において生じてもよい。
【００３１】
図１０Ｂを参照すると、スケジューラアルゴリズムが1010に示されている。スケジューラアルゴリズム1010は、1012において、実行中キューから現在実行中のタスクを削除するステップと、そのタスクを実行可能キューに追加するステップとを含む。特定の一実施形態では、実行中キューは、複数の実行中スレッド214上で実行されているタスクの優先順位付けされた実行中タスクリスト208を含む、図２に示す第1のデータ構造206に対応する。スケジューラアルゴリズム1010はまた、1014において、実行可能キューから最高優先度タスクを削除するステップと、そのタスクを実行中キューに追加してそのタスクを新しい現在実行中タスクにするステップとを含む。スケジューラアルゴリズム1010はさらに、1016において、新しい現在実行中タスクが最低優先度実行中タスクであるかどうかを判断するステップを含む。新しい現在実行中タスクが最低優先度実行中タスクである場合、1018において、新しい現在実行中タスクが実行されているスレッドは、割り込みを受け取るように構成される。新しい現在実行中タスクが最低優先度実行中タスクではない場合、1020において、新しい現在実行中タスクが実行されているスレッドは、割り込みを受け取らないように構成される。スケジューラアルゴリズム1010はさらに、1022において、図１０Ｃに示すスケジューラ確認を実行するステップを含む。
【００３２】
図１０Ｃを参照すると、スケジューラ確認が1024に示されている。スケジューラ確認1024は1026において開始する。スケジューラ確認1024は、1028において、いくつかのスレッドが割り込みを受け取るように構成されているかどうかを判断するステップを含む。どのスレッドも割り込みを受け取るように構成されていない場合、1034において、(1つまたは複数の)最低優先度スレッドは割り込みを受け取るように構成される。スケジューラ確認1024はまた、1030において、最低優先度実行中タスクが最高優先度実行可能タスクよりも低い優先度を有するかどうかを判断するステップを含む。最低優先度実行中タスクが最高優先度実行可能タスクよりも低い優先度を有する場合、1036において、再スケジューリングイベントを引き起こす割り込みがトリガされ、1038において、スケジューラ確認1024は終了する。
【００３３】
最低優先度実行中タスクが最高優先度実行可能タスクよりも低い優先度を有しない場合、スケジューラ確認1024はさらに、1032において、いずれかのタスクが実行可能である間、いずれかのスレッドがアイドルであるかどうかを判断するステップを含む。いずれかのタスクが実行可能である間、いずれかのスレッドがアイドルである場合、1036において、再スケジューリングイベントを引き起こす割り込みがトリガされ、1038において、スケジューラ確認1024は終了する。いずれかのタスクが実行可能である間、どのスレッドもアイドルでない場合、1038において、スケジューラ確認1024は終了する。特定の一実施形態では、割り込みコントローラは、1036においてトリガされる割り込みが最低優先度スレッドまたはアイドルスレッドに送出されるようにすでにセットアップされている。
【００３４】
図１１を参照すると、マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第2の例示的な実施形態の流れ図が示され、全体的に1100と称される。特定の一実施形態では、方法1100は図１のマルチスレッドプロセッサ100上で実装される。方法1100は、1102において、第1のスレッドにおいて割り込みを受信するステップを含み、第1のスレッドは、第1の時間におけるプロセッサにおける複数の実行中スレッドのうちの最低優先度スレッドを含む。方法1100はまた、1104において、第2のスレッドを識別するステップを含み、第2のスレッドは、第2の時間におけるプロセッサにおける複数の実行中スレッドのうちの最低優先度スレッドを含む。特定の一実施形態では、第2のスレッドは第1のスレッドとは異なる。方法1100はさらに、1106において、後続の割り込みを第2のスレッドに向けるステップを含む。たとえば、上記で説明したように、図２の矢印218、図４の矢印402、図６の矢印600、および図８の矢印800によって示されるように、割り込みは複数の実行中スレッド214のうちの最低優先度スレッドに向けられ得る。特定の一実施形態では、割り込みは、少なくとも1つのタスクが実行される準備ができていることを示す。たとえば、図２の矢印218によって示される割り込みは、優先度2のタスクが実行される準備ができていることを示し、図４の矢印402によって示される割り込みは、優先度2のタスクが実行される準備ができていることを示し、図６の矢印600によって示される割り込みは、優先度4のタスクが実行される準備ができていることを示し、図８の矢印800によって示される割り込みは、優先度4のタスクが実行される準備ができていることを示し得る。
【００３５】
特定の一実施形態では、第1のスレッドは、複数の実行中タスクのうちの最低優先度タスクを実行している。たとえば、図２の複数の実行中スレッド214のうちの最低優先度スレッドは優先度6のタスクを実行していることがあり得、図３の最低優先度スレッドは優先度4のタスクを実行しており、図５および図６の最低優先度スレッドは優先度8のタスクを実行していることがあり得、図７および図８の最低優先度スレッドは優先度6のタスクを実行していることがあり得、図９の最低優先度スレッドは優先度4のタスクを実行している。特定の一実施形態では、第1のスレッドはアイドルスレッドである。たとえば、図４の複数の実行中スレッド214のうちの最低優先度スレッドはアイドルスレッドであり得る。特定の一実施形態では、アイドルスレッドはアイドルタスクを実行している。
【００３６】
方法1100はまた、1108において、第1のスレッドが割り込みを受信したとき、割り込みルーチンを実行して実行可能タスクリストから最高優先度タスクを選択するステップを含む。実行可能タスクリストからの最高優先度タスクの第1の優先度は、実行中タスクリストからの最低優先度タスクの第2の優先度と比較され得、第1の優先度が第2の優先度よりも高いときのみ、タスクはスワップされる。たとえば、図２では、矢印218によって示されるように、複数の実行中スレッド214のうちの最低優先度スレッドである、優先度6のタスクを実行しているスレッドが割り込みを受信したとき、割り込みルーチンを実行して優先順位付けされた実行可能タスクリスト212から最高優先度タスクである優先度2のタスクを選択することができる。
【００３７】
方法1100はさらに、1110において、タスクをスワップして、第1のスレッドにおいて実行可能タスクリストの最高優先度タスクを実行し、前の実行中タスクを実行可能タスクリストに戻した後、実行可能タスクリストのいずれかの実行可能タスクが最低優先度実行中タスクよりも高い優先度を有するかどうかを判断するステップを含む。たとえば、図３の矢印300によって示されるように、優先度2のタスクと優先度6のタスクとをスワップした後、優先順位付けされた実行可能タスクリスト212の優先度6および優先度8をもつどの実行可能タスクも、優先順位付けされた実行中タスクリスト208の優先度4をもつ最低優先度実行中タスクよりも高い優先度を有しないことが判断され得る。同様に、図７の矢印700によって示されるように、優先度4のタスクと優先度8のタスクとをスワップした後、優先順位付けされた実行可能タスクリスト212の優先度4をもつ1つの実行可能タスクが、優先順位付けされた実行中タスクリスト208の優先度6をもつ最低優先度実行中タスクよりも高い優先度を有することが判断され得る。
【００３８】
特定の一実施形態では、必要に応じて方法1100を繰り返して、スケジュールを確認し、最低優先度実行中タスクを最高優先度実行可能タスクと比較することによっていずれかの追加の実行可能タスクが現在の最低優先度実行中タスクよりも高い優先度を有するかどうかを判断することができる。最低優先度実行中タスクを最高優先度実行可能タスクと比較するステップは、実行可能タスクリストのいずれかの実行可能タスクが最低優先度実行中タスクよりも高い優先度を有するかどうかを判断する1つの方法であり得る。たとえば、図３では、優先度4のタスクを最高優先度実行可能タスクである優先度6のタスクと比較することによって、どの実行可能タスクも最低優先度実行中タスクである優先度4のタスクよりも高い優先度を有しないことが判断され得る。同様に、図５では、優先度8のタスクを最高優先度実行可能タスクである優先度4のタスクと比較することによって、優先度4をもつ両方の実行可能タスクが最低優先度実行中タスクである優先度8のタスクよりも高い優先度を有することが判断され得る。
【００３９】
特定の一実施形態では、方法1100はさらに、最低優先度実行中タスクを判断するステップと、割り込みルーチンを使用して後続の割り込みを第2のスレッドに向けるステップとを含み、第2のスレッドは最低優先度実行中タスクを実行している。たとえば、図７の矢印700によって示されるように、優先度4のタスクと優先度8のタスクとをスワップした後、優先度6のタスクが最低優先度実行中タスクであると判断され得、図８の矢印800によって示されるように、割り込みルーチンを使用して、後続の割り込みを、複数の実行中スレッド214のうちの優先度6のタスクを実行している最低優先度スレッドに向け得る。
【００４０】
特定の一実施形態では、方法1100はさらに、スケジュールを確認していずれかの実行可能タスクが最低優先度実行中タスクよりも高い優先度を有するかどうかを判断した結果に基づいて、後続の割り込みを選択的に設定するステップを含む。たとえば、図８の矢印800によって示されるように、後続の割り込みは、図７のスケジュール222を確認し、実行可能タスクのうちの優先度4をもつ実行可能タスクが、優先度6のタスクである最低優先度実行中タスクよりも高い優先度を有すると判断した結果に基づいて、選択的に設定され得る。
【００４１】
特定の一実施形態では、図２〜図９の割り込みコントローラ204は、複数の実行中スレッド214のうちの最低優先度スレッド以外の、複数の実行中スレッド214のうちのスレッドが、割り込みを受信することからマスクされるように指示する。たとえば、図２〜図９に示すように、割り込みコントローラ204は、割り込みマスク220に指示して、複数の実行中スレッド214のうちの最低優先度スレッドを除いて、割り込みを受信することから複数の実行中スレッド214をマスクオフし得る。
【００４２】
図１２を参照すると、マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第3の例示的な実施形態の流れ図が示され、全体的に1200と称される。特定の一実施形態では、方法1200は図１のマルチスレッドプロセッサ100上で実装される。方法1200は、1202において、スレッドのセットのうちの第1のスレッドにおいて割り込みを受信するステップを含み、スレッドのセットの各スレッドは、実行中タスクのセットのそれぞれのタスクを実行し、実行中タスクのセットの各タスクおよび実行可能タスクのセットの各タスクは、それぞれの優先度を有する。たとえば、図６に示すように、優先度8のタスクを実行しているスレッドは、矢印600によって示されるように割り込みを受信し得、複数の実行中スレッド214の各スレッドは、優先順位付けされた実行中タスクリスト208のそれぞれのタスクを実行し、優先順位付けされた実行中タスクリスト208の各タスクおよび優先順位付けされた実行可能タスクリスト212の各タスクは、それぞれの優先度を有する。特定の一実施形態では、アイドルスレッドが、最低優先度を有するアイドルタスクを実行する。たとえば、図４に示すように、アイドルタスクを実行しているスレッドは、矢印402によって示されるように割り込みを受信し得る。
【００４３】
方法1200はまた、1204において、実行中タスクのセットの各タスクが、実行可能タスクのセットのあらゆるタスクの優先度よりも大きいかまたはそれに等しい優先度を有するまで、実行中タスクのセットのうちの最低優先度タスクを実行可能タスクのセットのうちの最高優先度タスクと反復的にスワップするステップを含む。たとえば、図４〜図９に示すように、優先順位付けされた実行中タスクリスト208の最低優先度タスクは、図９に示すように、優先順位付けされた実行中タスクリスト208の各タスクが、優先順位付けされた実行可能タスクリスト212のあらゆるタスクの優先度よりも大きいかまたはそれに等しい優先度を有するまで、優先順位付けされた実行可能タスクリスト212のそれぞれの最高優先度タスクと反復的にスワップされ得る。
【００４４】
特定の一実施形態では、反復的スワップは、1206において、各実行中タスクを実行可能タスクとスワップして実行中タスクの次のセットと実行可能タスクの次のセットとを形成した後、実行中タスクの次のセットのうちの最低優先度タスクを判断するステップを含む。反復的スワップの各反復は、実行中タスクの次のセットのうちの最低優先度タスクを判断するステップを含み得る。たとえば、図７の矢印700によって示されるように、優先度4のタスクを優先度8のタスクとスワップした後、実行中タスクの次のセットは、優先度0のタスクと、2つの優先度2のタスクと、2つの優先度4のタスクと、優先度6のタスクとを含み得、実行可能タスクの次のセットは、優先度4のタスクと、優先度8のタスクとを含み得、優先度6のタスクは、実行中タスクの次のセットのうちの最低優先度タスクであると判断され得る。反復的スワップはさらに、1208において、実行中タスクの次のセットのうちの最低優先度タスクの優先度が、実行可能タスクの次のセットのうちの最高優先度タスクの優先度よりも小さいとき、最低優先度スレッドに割り込みを送信して反復的スワップの次の反復を実行するステップを含む。たとえば、図８の矢印800によって示されるように、優先度6のタスクが、実行可能タスクの次のセットの最高優先度を有する優先度4のタスクよりも低い優先度を有するので、割り込みが実行中タスクの次のセットのうちの最低優先度タスクである優先度6のタスクに送信されて反復的スワップの次の反復を実行し得る。
【００４５】
図１３を参照すると、マルチスレッドプロセッサ上でリアルタイムにタスクをスケジュールするための方法の第4の例示的な実施形態の流れ図が示され、全体的に1300と称される。特定の一実施形態では、方法1300は図１のマルチスレッドプロセッサ100上で実装される。方法1300は、1302において、割り込みを複数の実行中スレッドのうちの最低優先度スレッドに向けるステップを含み、その割り込みは、少なくとも1つのタスクが実行される準備ができていることを示し、複数の実行中スレッドのうちの最低優先度スレッドは、最低優先度タスクを実行しているかまたはアイドルスレッドであるかのいずれかであり、複数の実行中スレッドのうちの最低優先度スレッドは、割り込みを受信し、割り込みルーチンを開始して実行可能タスクリストから最高優先度タスクを選択する。たとえば、図２の矢印218によって示されるように、割り込みは、複数の実行中スレッド214のうちの最低優先度スレッドに向けられ得、その割り込みは、優先度2のタスクが実行される準備ができていることを示し得、最低優先度スレッドは、優先度6のタスクである最低優先度タスクを実行していることがあり得、優先度6のタスクを実行している最低優先度スレッドは、割り込みを受信し得、割り込みルーチンを開始して優先順位付けされた実行可能タスクリスト212から優先度2のタスクである最高優先度タスクを選択し得る。
【００４６】
方法1300はまた、1304において、タスクをスワップして、実行可能タスクリストからの最高優先度タスクを実行し、前の実行中タスクを実行可能タスクリストに戻した後、スケジュールを確認していずれかの実行可能タスクがいずれかの実行中タスクよりも高い優先度を有するかどうかを判断するステップを含み、スケジュールを確認していずれかの実行可能タスクがいずれかの実行中タスクよりも高い優先度を有するかどうかを判断するステップは、最低優先度実行中タスクを最高優先度実行可能タスクと比較するステップを含む。たとえば、図７の矢印700によって示されるように、優先度4のタスクと優先度8のタスクとをスワップした後、スケジュール222を確認して、優先度6のタスクである最低優先度実行中タスクを優先度4のタスクである最高優先度実行可能タスクと比較することによって、いずれかの実行可能タスクがいずれかの実行中タスクよりも高い優先度を有するかどうかを判断し得る。
【００４７】
方法1300はさらに、1306において、割り込みルーチンを使用して、後続の割り込みを、複数の実行中スレッドのうちの最低優先度タスクを実行している特定のスレッドに向けるステップを含む。たとえば、図８の矢印800によって示されるように、割り込みルーチンを使用して、後続の割り込みを、複数の実行中スレッド214のうちの、優先度6のタスクである最低優先度タスクを実行している特定のスレッドに向け得る。方法1300はまた、1308において、スケジュールを確認していずれかの実行可能タスクが最低優先度実行中タスクよりも高い優先度を有するかどうかを判断した結果に基づいて、後続の割り込みを選択的に起こすかまたは開始するステップを含む。たとえば、図８の矢印800によって示されるように、後続の割り込みは、スケジュール222を確認し、優先度4の実行可能タスクが優先度6の実行中タスクである最低優先度実行中タスクよりも高い優先度を有すると判断した結果に基づいて、選択的に起こされるかまたは開始され得る。
【００４８】
図１４は、リアルタイムマルチスレッドスケジューラモジュール1464を含むシステム1400の特定の一実施形態のブロック図である。システム1400は、携帯型電子デバイスにおいて実装され得、メモリ1432に結合されたデジタル信号プロセッサ(DSP)などのプロセッサ1410を含む。例示的な例では、リアルタイムマルチスレッドスケジューラモジュール1464は、図１〜図９のシステムのいずれかを含み、図１０〜図１３の実施形態のいずれか、またはそれらの任意の組合せに従って動作する。リアルタイムマルチスレッドスケジューラモジュール1464は、プロセッサ1410中にあるか、または別個のデバイスもしくは回路(図示せず)とすることができる。特定の一実施形態では、図１のリアルタイムマルチスレッドスケジューラ106は、デジタル信号プロセッサにとってアクセス可能である。たとえば、図14に示すように、リアルタイムマルチスレッドスケジューラモジュール1464は、デジタル信号プロセッサ(DSP)1410にとってアクセス可能である。
【００４９】
カメラインタフェース1468は、プロセッサ1410に結合され、また、ビデオカメラ1470などのカメラに結合される。ディスプレイコントローラ1426は、プロセッサ1410とディスプレイデバイス1428とに結合される。コーダ/デコーダ(コーデック)1434も信号プロセッサ1410に結合され得る。スピーカー1436およびマイクロフォン1438がコーデック1434に結合され得る。無線インタフェース1440は、プロセッサ1410と無線アンテナ1442とに結合され得る。
【００５０】
リアルタイムマルチスレッドスケジューラモジュール1464は、メモリ1432のようなコンピュータ読み取り可能な媒体に記憶されたコンピュータ実行可能命令1466を実行して、リアルタイムマルチスレッドスケジューラモジュール1464に、割り込みを複数の実行中スレッドのうちの最低優先度スレッドに向けさせるように構成され、その割り込みは、少なくとも1つのタスクが実行される準備ができていることを示し、複数の実行中スレッドのうちの最低優先度スレッドは、最低優先度タスクを実行しているかまたはアイドルスレッドであるかのいずれかであり、複数の実行中スレッドのうちの最低優先度スレッドは、割り込みを受信し、割り込みルーチンを開始して実行可能タスクリストから最高優先度タスクを選択する。このようにして、リアルタイムマルチスレッドスケジューラモジュール1464は、モデムタスクなどの優先度の高いタスクが、ユーザインタフェースタスクなどの優先度のより低いタスクによって割り込まれないようにすることができる。
【００５１】
特定の一実施形態では、プロセッサ1410、ディスプレイコントローラ1426、メモリ1432、コーデック1434、無線インタフェース1440、およびカメラインタフェース1468は、システムインパッケージまたはシステムオンチップデバイス1422中に含まれる。特定の一実施形態では、入力デバイス1430および電源1444はシステムオンチップデバイス1422に結合される。その上、特定の一実施形態では、図１４に示すように、ディスプレイデバイス1428、入力デバイス1430、スピーカー1436、マイクロフォン1438、無線アンテナ1442、ビデオカメラ1470、および電源1444は、システムオンチップデバイス1422の外部にある。ただし、ディスプレイデバイス1428、入力デバイス1430、スピーカー1436、マイクロフォン1438、無線アンテナ1442、ビデオカメラ1470、および電源1444の各々は、インタフェースまたはコントローラなどのシステムオンチップデバイス1422の構成要素に結合され得る。
【００５２】
さらに、本明細書で開示した実施形態に関して説明した様々な例示的な論理ブロック、構成、モジュール、回路、およびアルゴリズムステップは、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装され得ることを、当業者は理解されよう。ハードウェアとソフトウェアのこの互換性を明確に示すために、様々な例示的な構成要素、ブロック、構成、モジュール、回路、およびステップを、上記では概して、それらの機能に関して説明した。そのような機能をハードウェアとして実装するか、ソフトウェアとして実装するかは、特定の適用例および全体的なシステムに課される設計制約に依存する。当業者は、説明した機能を特定の適用例ごとに様々な方法で実装することができるが、そのような実装の決定は、本開示の範囲からの逸脱を生じるものと解釈すべきではない。
【００５３】
本明細書で開示した実施形態に関して説明した方法またはアルゴリズムのステップは、直接ハードウェアで実施するか、プロセッサによって実行されるソフトウェアモジュールで実施するか、またはその2つの組合せで実施することができる。ソフトウェアモジュールは、ランダムアクセスメモリ(RAM)、フラッシュメモリ、読み取り専用メモリ(ROM)、プログラマブル読み取り専用メモリ(PROM)、消去的可能プログラマブル読み取り専用メモリ(EPROM)、電気的消去可能プログラマブル読み取り専用メモリ(EEPROM)、レジスタ、ハードディスク、リムーバブルディスク、コンパクトディスク読み取り専用メモリ(CD-ROM)、または当技術分野で知られている他の形態の記憶媒体中に存在することができる。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、記憶媒体に情報を書き込むことができるように、プロセッサに結合される。代替として、記憶媒体はプロセッサに一体化することができる。プロセッサおよび記憶媒体は特定用途向け集積回路(ASIC)中に存在することができる。ASICはコンピューティングデバイスまたはユーザ端末中に存在することができる。代替として、プロセッサおよび記憶媒体は、コンピューティングデバイスまたはユーザ端末中に個別構成要素として存在することができる。
【００５４】
開示した実施形態の上記の説明は、開示した実施形態を当業者が作成または使用できるように行ったものである。これらの実施形態への様々な修正は当業者には容易に明らかであり、本明細書で定義した一般原理は、本開示の趣旨または範囲から逸脱することなく他の実施形態に適用され得る。したがって、本開示は、本明細書に示した実施形態に限定されるものではなく、以下の特許請求の範囲によって定義される原理および新規の特徴と一致する可能な最も広い範囲を与えられるべきである。
【符号の説明】
【００５５】
100  マルチスレッドプロセッサ
102  メモリ
108  バスインタフェース
110  命令キャッシュ
111、128、130  バス
112  データキャッシュ
114  シーケンサ
116  汎用割り込み
118、120、122、124  命令実行ユニット
126  汎用レジスタファイル
132  スーパバイザ制御レジスタ
150  制御ユニット
156  割り込みコントローラ
158  リアルタイム優先度スケジューラ
200  マルチスレッドプロセッサ
202  リアルタイム優先度スケジューラ
204  割り込みコントローラ
206  第1のデータ構造
208  優先順位付けされた実行中タスクリスト
210  第2のデータ構造
212  優先順位付けされた実行可能タスクリスト
214  複数の実行中スレッド
220  割り込みマスク
222  スケジュール
1400  システム
1410  プロセッサ
1422  システムオンチップデバイス
1426  ディスプレイコントローラ
1428  ディスプレイデバイス
1430  入力デバイス
1432  メモリ
1434  コーデック
1436  スピーカー
1438  マイクロフォン
1440  無線インタフェース
1442  無線アンテナ
1444  電源
1464  リアルタイムマルチスレッドスケジューラモジュール
1466  コンピュータ実行可能命令
1468  カメラインタフェース
1470  ビデオカメラ
【図１】
0005538442.tif 000002
【図２】
0005538442.tif 000003
【図３】
0005538442.tif 000004
【図４】
0005538442.tif 000005
【図５】
0005538442.tif 000006
【図６】
0005538442.tif 000007
【図７】
0005538442.tif 000008
【図８】
0005538442.tif 000009
【図９】
0005538442.tif 000010
【図１０Ａ】
0005538442.tif 000011
【図１０Ｂ】
0005538442.tif 000012
【図１０Ｃ】
0005538442.tif 000013
【図１１】
0005538442.tif 000014
【図１２】
0005538442.tif 000015
【図１３】
0005538442.tif 000016
【図１４】
0005538442.tif 000017