複数のプロセッサ要素を有するマルチコアプロセッサにおいて実行可能トランザクションをスケジュールする方法であって、前記マルチコアプロセッサ内の少なくとも1つのプロセッサ要素が、実行時に再構成可能である再構成可能論理を含み、再構成可能論理の構成ごとに、実行可能な状態の実行可能トランザクションをリストし、前記再構成可能なプロセッサ要素の個々の構成に割り振られる実行可能トランザクションの構成待ち行列を設けるステップと、現在選択されている前記構成インスタンスと関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、事前定義された閾値に達したときに、現在選択されている前記構成インスタンスを切り換えるステップと、を備える方法。実行の適格性の順に実行可能トランザクションをリストする配布待ち行列を設けるステップと、それぞれが、実行可能な状態のいくつかの候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを決定するスケジューリングアルゴリズムを含む複数の個別実行可能トランザクションスケジューラを設けるステップと、前記複数の個別実行可能トランザクションスケジューラを、多重レベルスケジューラを提供するように相互にリンクするステップと、前記多重レベルスケジューラから前記配布待ち行列に最も適格な実行可能トランザクションを出力するステップと、前記プロセッサ要素ごとのディスパッチ待ち行列であって、前記実行可能トランザクションを当該プロセッサ要素上での実行の順にリストする当該ディスパッチ待ち行列、を複数設けるステップと、1つ以上の前記ディスパッチ待ち行列に前記配布待ち行列を関連付けるステップと、前記配布待ち行列の内容を、当該配布待ち行列に関連付けられたディスパッチ待ち行列に出力するステップと、をさらに備える、請求項1に記載の方法。前記構成インスタンスを切り換えるステップが、さらに、現在選択されている前記構成と関連付けられた前記構成待ち行列の内容の出力を停止するステップと、利用可能な前記構成インスタンスの別の1つを選択し、前記再構成可能論理の前記構成を、前記選択された利用可能な前記構成インスタンスの別の1つに変更するステップと、前記新しく選択された構成インスタンスに関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、をさらに備える、請求項2に記載の方法。前記再構成可能論理がメモリである、請求項2または3に記載の方法。前記事前定義された閾値が、前記アプリケーションの保全性を維持するために個々の実行可能トランザクションが実行されねばならなくなるまでの最大許容時間である、請求項2~4のいずれか一項に記載の方法。前記別の構成インスタンスの選択が、前記構成待ち行列のそれぞれの長さに依存するものである、請求項3に記載の方法。最も長い構成待ち行列に関連付けられた前記構成インスタンスが選択される、請求項6に記載の方法。ディジタル論理によって実行されると、請求項1~7のいずれか一項に記載の方法を実行する命令を備えるコンピュータプログラム。コンピュータによって実行されると、請求項1~7のいずれか一項に記載の方法を実行する命令を含むコンピュータ可読媒体。複数のプロセッサ要素を有し、当該マルチコアプロセッサ内の少なくとも1つのプロセッサ要素が、実行時に再構成可能である再構成可能論理を含むマルチコアプロセッサと、再構成可能論理の構成ごとに、実行可能な状態の実行可能トランザクションをリストするように設けられ、前記再構成可能なプロセッサ要素の個々の構成に割り振られる実行可能トランザクションの構成待ち行列であって、現在選択されている前記構成インスタンスと関連付けられた当該構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するように構成された前記構成待ち行列と、事前定義された閾値に達したときに、現在選択されている前記構成インスタンスを切り換えるコントローラと、を備えるマルチコアプロセッサ。実行の適格性の順に実行可能トランザクションをリストする配布待ち行列と、それぞれが、実行可能な状態のいくつかの候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを決定するスケジューリングアルゴリズムを含む複数の個別実行可能トランザクションスケジューラと、前記プロセッサ要素ごとのディスパッチ待ち行列であって、前記実行可能トランザクションを当該プロセッサ要素上での実行の順にリストする複数の当該ディスパッチ待ち行列と、をさらに備え、前記複数の個別実行可能トランザクションスケジューラは、多重レベルスケジューラを提供するように相互にリンクされ、前記多重レベルスケジューラは、前記配布待ち行列に最も適格な実行可能トランザクションを出力し、1つ以上の前記ディスパッチ待ち行列は、前記配布待ち行列が関連付けられ、前記配布待ち行列の内容が、当該配布待ち行列に関連付けられたディスパッチ待ち行列に出力される、請求項10に記載のマルチコアプロセッサ。少なくとも1つのプロセッサ要素プールとして構成されている、それぞれが少なくとも1つの節電モードを有する複数のプロセッサ要素を有するマルチコアプロセッサにおいて電力消費を管理する方法であって、前記プロセッサ要素プールに割り振られた実行可能トランザクションの数が、前記利用可能なプロセッサ要素のごく一部分が実行可能トランザクションの実行に使用されるような数になったときに、前記プロセッサ要素プール内の前記プロセッサ要素の1つ以上を第1の節電モードにするステップをさらに備える方法。複数のプロセッサ要素を有するマルチコアプロセッサ内でアプリケーションを定義する実行可能トランザクションをスケジュールする方法であって、実行可能トランザクションスケジューラの階層を維持するステップを備え、前記階層が、使用時の前記アプリケーションの要件に従って実行可能トランザクションをスケジュールするように適合され、前記スケジューラ階層の各レベルが少なくとも1つのスケジューラを備え、前記少なくとも1つのスケジューラが、前記実行可能トランザクションを、前記プロセッサ要素の1つ以上での実行に最も適格なトランザクションの順にソートするための少なくとも1つの規則を備える方法。[概要]図1に、マルチコアシステムにおけるタスクまたはスレッドの管理のためにSystemWeaverで実施されるものと類似のタスク状態図を示す。マルチコアシステムにおいて、スケジューラは、1組の事前定義された規則スケジュールに従い、最適な時刻に、最適なリソースに対して作業パケットを提供する。スケジューリングは、以下のように、アプリケーションと基礎ハードウェアプラットフォームの両方によって必要とされる。-アプリケーションスケジューリングは、同期および適格性を備える。同期は、システム内のリソースが、データおよび、おそらく、システム全体の保全性を損なうことなく共用され得るよう保証する。適格性は、作動可能タスクが、スケジューリングポリシーで表されるアプリケーションの必要と整合する方法で処理リソースに発行されるよう保証する。-プラットフォームベースの/配布スケジューリングは、アプリケーションタスクが適切な処理リソースインスタンス間で配布されるポリシーを定義する。これは、複数のユーザおよび/または複数の異なるアルゴリズム間で処理リソースを共用することを示唆してもよい。図2に、スケジューリング点が発生させる待ち行列点に対するスケジューリング点の図を示す。左から右に向かって、発生する第1の待ち行列点は保留待ち行列である。ブロックされたタスクは、それらの優先度に従って保留待ち行列に格納され、同期イベントによって解放される。保留待ち行列の構造および挙動についてのこれ以上の考察は、本明細書の範囲を超えるものである。第2の待ち行列点は作動可能待ち行列であり、これは、アプリケーションと配布両方のスケジューリングを備える。図2では、これが3つの論理部分、すなわちアプリケーションおよび配布スケジューリングに分かれている。概念的には、これら2つのスケジューリング段の間にあるのが、すべての現在作動可能なアプリケーションタスクが、ユーザ定義のメトリックおよびスケジューリングポリシーで表されるそれらの適格性に従ってソートされている点である。これが、配布ノードと呼ばれる点である。配布ノードの前に、異なるクラスのタスクおよび共通クラスのタスクインスタンスが、処理リソースインスタンスへのアクセスを求めてどのようにして競合するかを決定する1組のアプリケーション特有のスケジューリングポリシーが構成される。このスケジューリングポリシーの階層をスケジューリングコーンといい、アプリケーション特有のものである。スケジューリングコーンの後で、最も適格なアプリケーションタスクが、基礎ハードウェアプラットフォームに存在する処理リソースインスタンスにどのようにして配布されるかを決定する、1組のプラットフォーム特有のスケジューリングポリシーが構成される。このスケジューリングポリシーの階層を配布コーンといい、プラットフォーム特有のものである。スケジューリングポリシーおよび実装の有効性は、以下の多くの特性の組み合わせに基づいて判断され得る。-スループット-毎秒行われ得るスケジューリング決定の数-待ち時間-システム内のイベントと、そのイベントに関連付けられたスケジューリング操作の完了の間に経過する時間-予測可能性/決定性-システムが、あらゆる環境下でどのようにして振る舞うか決定する能力-効率性-任意の所与のスケジューリングアルゴリズムがその範囲内で実施され得る効率性。これは、1決定当たりの命令数命令セット効率の測定値および/またはシリコンフットプリントメモリその他のダイ面積として測定され得る。-ポリシー-サポートされるポリシーの多様性およびそれらを組み合わせて複雑な階層を形成することのできる能力。[構成要素]サーバコアとクライアントシムという、SystemWeaverの2つの主要な構成要素がある。これらは様々な方法で接続され得る。SystemWeaver対応システムは、サーバコアと、少なくとも1つのクライアントシムとを備えるはずである。[SystemWeaverコア]SystemWeaverコアは、ハードウェアエンジンと密結合メモリとを備える。メモリは、スケジューリング構成と、システム内の作業単位を表すのに使用される動的記述子とを含む。各SystemWeaverコアは、命令セットベースのアーキテクチャとすることも、ハードウェアアクセラレータとすることもできる複数のクライアントにまたがって集約される。SystemWeaverは、以下の2つの論理的に別個のデータパスを介して各クライアントと個別にやりとりする。-クライアントに、注意を必要とするシステム状態の変更を知らせる帯域外信号。SystemWeaverコアは、通常、割り込みとして実施されるこれ以降仮定されるこのインターフェースのマスタである。-クライアントがそれを介してSystemWeaverに応答させることのできるデータパス。クライアントは、バス、二重シリアルインターフェースまたは他の任意の双方向実装として実施され得るこのインターフェースのマスタである。ブートプロセスの間に、SystemWeaverコアは初期設定されなければならない。通常は、1つのクライアントがブートマスタに指定され、システムの残りの部分に代わって、SystemWeaverおよびそれに関連付けられたメモリを初期設定する。[SystemWeaverクライアントシム]従来の構成では、各クライアントは、個別のクライアントシムを有するが、より保守的な実装形態では、複数のクライアントにわたってクライアントシムを集約することもある。クライアントシムは、ハードウェアとしてもソフトウェアとして実施され得る。図3に、以下のソフトウェアクライアントシムの基本要素を示す。-SystemWeaverHALは、SystemWeaverコアのレジスタインターフェースに必要なコマンドフォーマット設定を実施する。-SystemWeaverAPIは、アプリケーションが、タスクベースの抽象化においてSystemWeaverコアへの呼び出しを行うことを可能にする。-ユーザスレッドは、SystemWeaverタスク管理機能を使用するアプリケーションスレッドである。任意の時点において、ただ1つのユーザスレッドだけが、直接、各個別クライアントの管理下にある。-クライアントシムは、帯域外信号サービス通常は、割り込みサービスを処理する。主として、クライアントシムは、処理リソースインスタンス内のコンテキストを管理し、タスク切換えおよび優先使用を介して保全性が保存されるようにする。通常、クライアントシムは、アーキテクチャ上不可知の部分および命令セットアーキテクチャ特有の部分を含む。-アイドルエージェントは、個別処理リソースインスタンスの電源遮断モードまたはマクロアーキテクチャを処理する管理タスクを実施する。図4に、動作時のSystemWeaverクライアントの状態図を示す。クライアントシムは、以下の2つの主要な機能を果たす。-内部で処理リソースインスタンスが実行されているコンテキスト従来のプロセッサでは、コンテキストは、プロセッサスタック空間および内容、レジスタ値、プログラムカウンタなどを含むことができるの管理適切な時刻における割り振り、格納および復元。内部でユーザタスクが実行されるコンテキストであるユーザまたはタスクコンテキストと、クライアントシム管理操作専用のコンテキストである処理インスタンス特有のコンテキストという、2種類のコンテキストがある。-動作モードの管理従来のプロセッサでは、いくつかの重要なシステムリソースにアクセスする権限を定義する、ユーザ通常モードおよびスーパバイザ特権モードが利用可能である。例えば、スーパバイザモードタスクとは異なり、ユーザモードタスクには、処理リソースを共用する他のユーザモードタスクに悪影響を及ぼし得るリソースへのアクセスは許可されない。以下の説明は汎用プロセッサでのものであるが、あらゆる種類のクライアントに類似性が存在する。-アイドル状態-アイドル状態の間、ユーザ定義のアルゴリズムは、エンド処理リソースインスタンスによって供与される電源遮断モード例えば、クロックゲーティングや他の低電力状態あるいはシステムアーキテクチャ全体によって供与される電源遮断モード例えば、クロックゲーティングや、個々の処理リソースインスタンスへの電力供給の低減または除去を利用することができる。この状態の間、処理リソースインスタンスは、特権モードで動作することができ、処理リソース特有のコンテキストを使用することになる。SystemWeaverサーバは、クライアントに、アイドル状態に入るように命令しないことに留意されたい。クライアントは、スケジュールされたタスクが無いことの結果としてアイドル状態に入るのである。各クライアントは、SystemWeaverサーバからの帯域外信号通常は割り込みを介して応答するよう命令されるまでアイドル状態のままに留まる。-クライアントシム状態-クライアントシム状態は、ユーザおよびアイドルタスクの実行コンテキストを管理する。クライアントシム状態にあるとき、クライアントシムは、実行を終了しており、取って代わられており、またはブロックしている任意のタスクのコンテキストを保存し、次の実行タスクのコンテキストアイドルタスクの場合には、これは、処理リソースインスタンス特有のコンテキストであるを回復し、または作成する。この状態になる間、処理リソースインスタンスは、特権モードで動作してもよい。場合によっては、クライアントシムは、処理リソース特有のコンテキスト、あるいはユーザまたはタスクコンテキストのどちらかで動作してもよい。クライアントシム状態に入るのは、SystemWeaverサーバからの帯域外信号の結果としてユーザまたはアイドル状態からクライアントシム状態への遷移、あるいは実行中のタスクをブロックさせているSystemWeaverAPI呼び出しの結果として例えば、セマフォをロックしようとする試みが失敗した結果としての、SyWAPI状態からクライアントシム状態である。処理が完了すると、クライアントシムは、それ以上の外部信号なしで、クライアントシム状態を、その処理リソースインスタンスでの未完了のタスクが無い場合にはアイドル状態に、またはその処理リソースインスタンスでの適格なタスクが存在する場合にはユーザ状態に遷移させてもよい。-ユーザ状態-ユーザ状態にあるとき、クライアントシムは、ユーザアプリケーションコードを実行する。この状態にある間、処理リソースインスタンスは、通常、ユーザモードまたは通常モードで動作するはずである。ユーザ状態は、完全にユーザまたはタスクコンテキスト内で動作するはずである。ユーザ状態には、ユーザタスクを開始し、または再開した結果として、クライアントシム状態から、あるいはSystemWeaverサーバAPI呼び出しからの戻りの結果として、SyWAPI状態から入ることができる。クライアントシムは、タスク完了または優先使用SystemWeaverサーバからの帯域外信号の受け取りの結果として、ユーザ状態からクライアントシム状態に遷移し得る。クライアントシムは、SystemWeaverサーバAPIへの呼び出しの結果としてユーザ状態からSyWAPI状態に遷移し得る。-SyWAPI状態-ユーザタスクがSystemWeaverコアとの対話を必要とする場合、ユーザタスクは、SyWAPIへのクライアントシム状態変更を生じさせるSystemWeaverAPIを介して対話する。この状態にある間、処理リソースインスタンスは、特権モードで動作してもよい。SyWAPI状態は、完全にユーザまたはタスクコンテキスト内で動作するはずである。SyWAPI状態になるのは、SystemWeaverAPIへの呼び出しの後である。非ブロック呼び出しでは、クライアントシムは、SyWAPI状態からユーザ状態に戻るが、例えば、セマフォに関連付けられるものなど、いくつかのアクセスは、ユーザタスクをブロックさせることになり得るブロックされたタスクは、何らかの共用システムリソースが利用可能になるまで待機しなければならない。この場合、クライアントシムは、クライアントシム状態に遷移する。[概念]以下の項では、SystemWeaverスケジューラの動作を理解するのに必要とされる概念を論じる。[SystemWeaverメモリ要素]SystemWeaverは、接続された密結合メモリを必要とし、スケジューリングポリシー格納のためにこのメモリを使用することで、システム開発プロセス全体を通しての完全なスケジューリング変更および柔軟な調整が可能になる。SystemWeaverメモリは、SystemWeaverメモリ要素WMEに分割される。WMEは、以下で論じるタスクおよびスケジューリング記述子を表すのに使用される。[タスク記述子]タスク記述子は、SystemWeaverアーキテクチャの基本通貨単位である。タスク記述子は、スケジューリング階層内で構成された規則に従って処理リソースインスタンスへのアクセスを求めて競合する作業単位を表す。タスク記述子は以下のものを含む。-実行されるべきタスクへの参照およびタスクがそれに対して実行されなければならないデータセットをさらに含む、タスク制御ブロックへの参照。-タスクの適格性を定義するスケジューリングメトリック。-また、最初にブロックされるタスクのための同期参照およびタイムアウトが含まれてもよい。ブロックされるタスク挙動の詳細な説明は、本明細書の範囲外である。-タスク記述子がおそらく、同期後にそこに追加されなければならないスケジューリング階層の部分を定義する入口ノードへの参照。[スケジューリングおよび配布コーン]スケジューリングおよび配布コーンという2種類のコーンを使って、SystemWeaverスケジューリング挙動が記述される。スケジューリングコーンは、多数の入口点から単一の集約点に収束するスケジューラの階層、すなわち多対1マッピングを記述するのに使用される。配布コーンは、単一の集約点から多数のディスパッチ点へと発散するスケジューラの階層、すなわち、1対多マッピングを記述するのに使用される。スケジューリングコーン図5に赤で示すスケジューリングコーンは、図2の作動可能状態内のアプリケーションスケジューリングとしても示すアプリケーションの必要によって駆動される、アプリケーション決定ノード階層を定義する。スケジューリングコーンは、複数のタスククラスおよびタスククラスの複数のインスタンスがシステムリソースを求めて競合するための規則を定義する、多対1マッピングである。配布コーン図5に紫で示す配布コーンは、図2の作動可能状態内の配布スケジューリングとしても示す主に、基礎ハードウェアプラットフォームの特性によって駆動される、配布決定ノード階層を定義する。配布コーンは、スケジューリングコーンの最も適格な候補を利用できる適切な処理リソース間で分配するための規則を定義する。1次スケジューリングノードスケジューリング構成を記述するのに使用される3つの1次ノードがあり、それらは、入口ノード、配布ノードおよびディスパッチである。1次ノードは、スケジューラの詳細な実装をより綿密に反映する、基礎をなす2次ノード構造の上のオーバーレイである。入口ノード入口ノードは、新規タスクが待ち行列に入れられる点を定義する。入口ノードは、通常、スケジューリングコーンの両極端として配布ノード上に多対1でマップする。入口ノードは、特定のタスククラスに関連付けられてもよく、他のアプリケーション駆動ポリシーに従ってもよい。所与の入口ノードは、単一の配布ノード上にのみマップし得る。配布ノード配布ノードは、スケジューリングと配布コーンの間の記述を定義する。配布ノードは、通常、処理リソースのクラスを表す。スケジューリングコーンは、通常、単一の配布ノード上に1つ以上の入口ノードをマップし、配布コーンは、通常、複数のディスパッチノード、従って最終的には処理リソースインスタンス上に、単一の配布ノードをマップする。ディスパッチノードディスパッチノードは、個別処理リソースインスタンスに関連付けられた出口点を定義する。ディスパッチノードは、通常、ハードウェアプラットフォーム内に存在するIPコアと1対1でマップする但し、ハードウェアマルチスレッドプロセッサコアには、複数のディスパッチ待ち行列が割り振られてもよい。複数の配布コーンが個別ディスパッチノード上にマップしてもよい。2次スケジューリングノード2種類の決定ノード、すなわち、アプリケーション決定ノードおよび配布決定ノードが定義される。アプリケーション決定ノードおよび配布決定ノードは、スケジューリング層上に直接マップするが、これらは、スケジューラ実装内の基礎をなす層の数または種類を網羅的に定義するものではない。アプリケーション決定ノードアプリケーション決定ノードは、スケジューリングコーン内の中間スケジューリング点または集約点を定義する。各アプリケーション決定ノードは、1組の候補のうちで最も適格な候補を選択するための規則を定義する。配布決定ノード複数の配布ノードが単一のディスパッチノード上にマップする場合、処理リソースインスタンスにアクセスすることのできる配布コーンを決定するポリシーを設定するために、配布決定ノードが必要とされる。[スケジュール構成]作動可能状態構造図2は、実行可能な状態のスレッドを含む。作動可能状態構造全体でとしては、多数のスケジューリングおよび配布コーンを備えることができる。これらのスレッドは、独立のスレッドプリミティブを用いて作成されたすなわち、作動可能状態において作成されたものであり、またはこれらが依存する同期プリミティブまたはタイムアウトを受け取っているものである。同期スレッドは、以前に、ブロック状態から遷移している。作動可能状態構造は、スケジューラノード記述子および独立のスレッド記述子を含んでいてもよい。この構造は、システム初期設定時におおむね定義されるが、スレッド記述子およびそれらに関連付けられた動的スケジューラ層記述子は、実行時に出入りすることを許される。作動可能状態構造は、スレッドが、処理ノードのプール、または特定の処理ノードに対してスケジュールされることを可能にする。これは、特定のタスクを特定の機能を有する処理リソース例えば、ハードウェアアクセラレータや入出力装置などに向けることのできる能力を維持しつつ、複数の互換性のある処理リソースにまたがる負荷均衡化またはその他の配布挙動を可能にするものである。スケジューリング層は、作動可能状態構造を構成する1次および2次スケジューリングノードを実施するのに使用される基本リソースである。スケジューリング層は、他のスケジューリング層およびタスク記述子と、親、子またはピア関係を持ち得る。図6に、親子関係を例示するスケジューラ階層図を示す。この例において、yはa、bおよびcの親である。yは、xとzのピアである。親は、スケジューリング層とすることしかできないが、子は、スケジューリング層とすることも、タスク記述子とすることもできる。所与のピアグループ例えば、a、bおよびcは、タスク記述子とスケジューリング層の混ざったもので構成されていてもよい。また、すべてのスケジューリング層は親を持つディスパッチノードは、親を定義しない唯一の記述子である。実行時に、親層は、ユーザ定義のポリシーに従って最も適格な子からメトリック優先度などを継承してもよい。この機能は、深く組み込まれたスケジューリングポリシーが、比較されているスケジューリング分岐からの適格な候補の何らかの知識を必要とする場合に使用されてもよいこの問題は、以下のメトリック伝搬の項で詳細にカバーする。以下の各項では、任意のSystemWeaverスケジューリング階層の基本構成要素を説明する。基本スケジューラ層スケジューラ層は、スレッド記述子をスケジュールするのに使用される階層を定義する。各スケジューラ層は、通常、スケジューリングアルゴリズム、スケジューリング決定を行うのに使用されるいくつかのメトリック、メトリックがどのようにして子から親に伝搬されるか定義するのに使用される継承ポリシー、および別のスケジューラ層またはスレッド記述子とすることのできる子要素のリストを定義する。3種類のスケジューラ層記述子があり、それらは、ルート、静的および動的である動的層は、特殊な種類の静的スケジューリング層である。図7に、スケジューリングコーン実装の一例を示す。図36に、図7以後のすべてのスケジューリング図での図参照凡例を示す。スケジューラルート記述子スケジューラルート記述子は、ディスパッチ待ち行列との1対1マッピングを有する。スケジューラルート記述子は、作動可能状態構造における最終ノードを表す。ルート記述子メトリックは、常に、定義された継承ポリシーに従って作動可能状態構造から導出されるメトリックのコピーを含む。スケジューラルート記述子は、システム初期設定時に構成され、永続的に存在する。静的スケジューラ記述子スケジューラ静的記述子は、スケジューリング階層のルートノード下に存在する。静的スケジューラ記述子の親は、他の静的スケジューラ記述子とすることも、ルート記述子とすることもできる。スケジューラ静的記述子は、その親によって定義されるスケジューラアルゴリズムおよび独自のスケジューラメトリックに従って兄弟ノードと競合する。スケジューラ静的記述子は、システム初期設定時に構成され、永続的に存在する。動作時に、SystemWeaverは、選択されたスケジューリングおよびメトリック伝搬アルゴリズムに従ってスケジューラメトリックを維持する。動的スケジューラ記述子スケジューラ動的記述子は、スケジューリング階層のルートノード、および、場合によって、静的ノードの下に存在する。動的スケジューラ記述子の親は、静的スケジューラ記述子とすることも、ルート記述子とすることもできる。動的スケジューラ記述子は、その親によって定義されるスケジューラアルゴリズムおよび独自のスケジューラメトリックに従って兄弟ノードと競合する。動的スケジューラ記述子は、いつも構成されてもよい。これは、システムが、純粋に静的な備えで可能なはずのスケジューリング層よりはるかに多数のスケジューリング層をサポートすることを可能にする。SystemWeaverは、全期間にわたって、多数の多様なスレッドおよび動的スケジューラ層記述子が使用されるが、ある有限期間に過渡的要求がより小さくなる可能性を利用することによってこれを実現する。例えば、最大4000の動的要素スレッドおよび動的スケジューラ記述子をサポートするメモリが接続されたネットワークシステムでは、16000接続をサポートすることが可能であると考えられる。なぜなら、任意の時点において、プロセッサでは、全接続空間のほんの一部からのデータ単位だけが活動状態だからである。この柔軟性は、性能をわずかに犠牲にして達成される。なぜなら、動的スケジューラ記述子が存在しない場合、子スレッド記述子の追加の前にそれが作成されなければならないからである。動作時に、SystemWeaverは、選択されたスケジューリングアルゴリズムに従ってスケジューラメトリックを維持する。いくつかの状況下において、SystemWeaverは、動的スケジューラ記述子を解放してWMEフリーリストに戻す。プロセッサリソースプールプロセッサリソースプールは、特定の処理リソースのインスタンスの単一の配布ノードへの集約を可能にする。その場合、配布ノードは、処理リソースプールの個別メンバにまたがって負荷均衡化、インテリジェント優先使用および電源管理を提供してもよい。図8に、典型的な処理リソースプール構成を示す。以下のWeaverメモリ要素の3つの新しい定義がプロセッサプール構成構造をサポートする。プール接続ノードプール接続ノードPANは、スケジューラルート層を処理リソースプールルート層に接続するのに使用される。PANは、スケジューラルート層内に存在しなければならないすなわち、その親は、スケジューラルートノードでなければならない。動作時に、PANメトリックは、スケジューリングコーンから継承されたものである、プールルートノードPRNのメトリックのコピーで自動的に更新される。PAN内で定義されるスケジュール演算子は使用されない。プール静的ノードプール静的ノードPSNは、スケジューラルート層を処理リソースプールルート層に接続するのに使用される。プール静的ノードは、プールルート層内に存在しすなわち、その親はPANでなければならない、ディスパッチノードすなわち、現在実行中のスレッドのメトリックのコピーを自動的に保持する。所与のプールのPSN内のスケジューラ演算子は、すべて、取って代わられるべき適切な処理リソースインスタンスを選択するのに使用されるポリシーを定義する、同じアルゴリズムに設定されなければならない。プールルートノード各処理リソースプールごとに1つのプールルートノードPRNがある。プールルートノードは、処理リソースプールの配布ノードを定義する。PRN内のメトリックは、配布ノードに関連付けられたスケジューリングコーン内で保持される最も適格なスレッドを反映する。PRN親ポインタは、プール静的ノードの1つを指し示すように設定されなければならない。スケジューラアルゴリズムは、基本的に、スケジューリングコーンの隣接する層の必要に従って設定されるべきである。動的スケジューラ構成SystemWeaverは、実行時におけるスケジューリングノードの作成および削除をサポートすると共に、喪失や順序付け間違いなしで、ある入口ノードから別の入口ノードにタスククラスを移行させる機能も提供する。動的スケジューラ構成を論じるときには、さらに2つの概念、休止スケジューリング層およびマーカスレッドを導入しなければならない。-休止スケジューリング層は、階層内に存在し、プッシュ操作を受け入れてもよいすなわち、子エントリを蓄積してもよいが、スケジューリングには不適格であり、したがって、決してポップされることがない。-マーカスレッドは、それらがスケジューリング階層の特定の部分に依存する最後のスレッドであるときに限ってスケジュールされる。スケジューリング階層の一部に依存するスレッド数は、作動可能なスレッドの数、および、作動可能になったときにスケジューリング階層のこの部分を使用することになるブロックされたスレッドの数を含む。マーカスレッドは、他の任意のスレッドと同様にタスク参照を保持することができ、通常は、スケジューリング階層のある部分と別の部分の間の遷移操作の管理を完了するのに使用される。以下の項では、階層のある部分からのタスクストリームの遷移シーケンスの一例を詳述する。これは、スケジューリング階層の一部の削除の上位機能であることに留意されたい。操作シーケンス適切な操作シーケンスが確実に順守されるようにするのは、上位レベルのソフトウェアの役割である。このシーケンスを遵守し損なうと予期しない挙動を生じることがあり、特に、新しいスレッドは、マーカスレッドが挿入されているスケジューリング階層の一部に導入されてはならない。このシーケンス例では、タスクストリームtstreamが、スケジューラ階層h1から新しいスケジューリング階層h2に遷移するものと仮定する。-休止スケジューラ階層h2を作成する。-tstream上のすべての新しいタスク記述子をh2に割り当てる。-マーカスレッドをh1に挿入する。-マーカスレッドの出現を待ち受ける。-休止階層h2を覚醒させる。[スケジューラ解析、アルゴリズム、演算子およびオペランド]スケジューリング解析は多くの形EDF、RMAなどを取り、通常は、アプリケーション、または少なくともセクタに特有のものである。スケジューリング解析の結果は、静的または動的にアプリケーションの実行時配置を制御する1組のポリシーである。その一意のマイクロアーキテクチャを介して、SystemWeaverは、これらの事前定義されたポリシー/アルゴリズムを、実行時に効率よく実行する。スケジューリングアルゴリズムSystemWeaverは、シリコン設計時に、アーキテクチャまたは実装を中断せずに、専門化されたアルゴリズムが定義され得るように設計される。しかしながら、以下のように、いくつかのアルゴリズムがデフォルトで提供される。-FIFOスケジューリング:単純な先入れ先出し待ち行列法。-優先度スケジューリング:最も適格な候補が、最高昇順の優先度または最低降順の優先度の優先度メトリックを有する。-ラウンドロビン:スケジューリング階層からタスクがポップされるときにスケジューリング決定を次のピアに更新する。ラウンドロビンは、スケジューリング階層の左端にある関連するスケジューリングポリシーではないことに留意されたい。-重み付き公平待ち行列法:適格な候補が、割り当てられた重みおよび何らかの負荷尺度すなわち、パケット長に従って選択される複雑なスケジューラ。スケジューラ階層全体に多少注意すれば、アプリケーションシステムにおいて洗練されたトラフィックおよびタスク管理機能を提供するための、スケジューラアルゴリズムの複雑な組み合わせを容易に作成することができる。演算子スケジューリングアルゴリズムは、さらに、以下の個別のスケジューリングおよびメトリック演算子に分解され、これらは2つとも親ノード内で定義される。-スケジューリング演算子:子ノード内に格納されるオペランドを使って最も適格な候補を決定する方法を定義する。スケジューリング演算子は、子ノード内のオペランドを変更しない。-メトリック演算子:最も適格な子のオペランドが、親のオペランドに伝搬される方法を定義する。伝搬演算子は、ヌル親への更新なし、コピー親のオペランドの上書きとすることもでき、子および親オペランドの一部または全部に対する数学的演算が関与してもよい。いかなる場合にも、子オペランドは変更されない。スケジューリングおよびメトリック演算子は、SystemWeaverスケジューラハードウェアにおいてネイティブで実施される。通常は、スケジューリングとメトリックを組み合わせた演算子を使って、所与のスケジューラアルゴリズムが定義される。スケジューリングアルゴリズムは、一般に、新しいタスクがスケジューラ階層にプッシュされているプッシュイベント下における挙動を示唆し、タスクがスケジューリング階層からポップされるポップイベント下とは異なる。例えば、FIFOスケジューラを考えると、新しいタスクが空でないFIFOスケジューリング段にプッシュされるときには、スケジューリング更新は行われず、項目がFIFOスケジューリング段からポップされるときには、スケジューラは、更新されなければならない。スケジューリング演算子スケジューリング演算子は、拡張可能であるように設計されるが、デフォルト演算子の選択が定義される。スケジューリング演算子は、通常、比較によるものであり、したがってその結果は常にブール値である。以下の表において、Mは、以下の方式に従って、スケジューリング層のメンバまたはスケジューリング層記述子自体における2つのメトリックの1つを表す。-Mcurrentnは、現在最も適格な候補に属するメトリックを指す。-Mcandidatenは、スケジューリング更新の過程で現在の記述子が比較される相手の候補に属するメトリックを指す。-Mtiernは、現在および候補の記述子の接続先のスケジューラ層記述子に属するメトリックを指す。複合スケジューリング演算子また、複合スケジューリング演算子も利用可能であり、それらは、表1のスケジューリング演算子の組み合わせである。例えば、次式の通りである。必要な更新=MCURRENT0>MCANDIDATE0MCURRENT1<MCANDIDATE1式中、問題のパラメータは、親と子両方の記述子メトリックを利用することができる。これらの複合演算子は、従来のスケジューリング層とプール配布層の両方で使用され得る。さらなる情報および例については、以下のスケジューリングシーケンス図の項を参照されたい。メトリック演算子メトリック演算子は、事実上に算術的である。スケジューリング演算子と同様に、メトリック演算子は、拡張可能であるように設計されるが、1組のデフォルト演算子を有する。表2を参照されたい。メトリック演算子の複雑度の幅は、ヌルまたは単なるコピー演算から複雑な積和演算にまで及ぶ。オペランドスケジューリングオペランド、またはメトリックは、以下の2つのグループに分けられる。-ローカルメトリックは、処理リソースインスタンス、スケジューラ層およびスレッド記述子と関連付けられる。ローカルメトリックの操作は、自動的に、再スケジュールイベントを発生させる。-グローバルメトリックは、場合によって、通常は、システムリソース状態バス使用度やフリーメモリなど何らかのヒューリスティックスと関連付けられる。所与のスケジューリングアルゴリズムは2つのメトリックだけを使用することができ、その一方はローカルでなければならない。第2のメトリックの種類は、Metric1IsGlobalフラグによって決定される。-Metric1IsGlobalがリセットされるとき、メトリック1はローカルであり、スケジューリング操作においてリテラルとして使用される。-Metric1IsGlobalが設定されるとき、メトリック1は、グローバルメトリックポートの配列へのインデックスである。ローカルメトリックタスク記述子もスケジューリング層記述子も2つの32ビットオペランド、すなわちスケジューリングメトリックを含む。これらのオペランドは、スケジューリング操作時に、それぞれの親によって使用され、後続の階層上位のスケジューリングのために、スケジューリング操作時に変換され、かつ/または親のオペランドに伝搬されてもよい。図9に、タスク記述子内に存在するスケジューリングメトリックを示す。タスク記述子内では、メトリック0は、通常、タスクの優先度を表すのに使用される。このメトリックの最下位バイトは、SystemWeaverハードウェアおよびクライアントソフトウェア内での内部使用のために予約される。スケジューラ層メトリックに対する制限はない。グローバルメトリックグローバルメトリックは事実上受動的であり、グローバルメトリック値の変更は、すべての潜在的に影響を受けるスケジューリングリソース上での再スケジュールイベントを発生させない。グローバルメトリックは、他の何らかのイベントの結果として、従属スケジューリングリソースがスケジュールされるときに問い合わせを受ける。SystemWeaverアーキテクチャは、グローバルメトリックの使用に対しては制限を課さないが、グローバルメトリックは、システムヒューリスティックスバス利用度、ある時間枠にわたるメモリフィルなどに使用されてもよく、したがって、変化率は比較的低くなる。また、データを平均化するためにフィルタが適用されてもよい。[スケジューリング階層構成の詳細]以下の各項で参照するすべての構成図で、図36に示す共通フォーマットを使用する。図10に、単一プロセッサの最も基本的な構成を示す。これには、その必須スケジューリングルートノードを有する、単一の処理リソースインスタンス単一のディスパッチノードの構成が示されている。この最も単純な場合には、単一のプロセッサだけしかないため、スケジューラコーンは、単一のFIFO段からなり、配布段はヌルである。したがって、スケジューラルートノードは、入口ノードと配布ノードの両方である。スケジューラノード実装上の矢印は右から左親から子に向かって示されており、これは、子から処理リソースインスタンスへと流れるタスクのフローと反対であることに留意されたい。スケジューラはモジュール方式で実装され、揮発性メモリとして構成される。これは、異なるポリシーの連続したスケジューラ層から、非常に洗練されたスケジューラ階層を構築し、開発プロセス全体を通じて調整し、カスタマイズすることを可能にする。しかしながら、無効な構成も可能であり、深くネストされたスケジューラ層から適切なメトリックが使用できるように、特に注意が払われなければならない。[層内構造]スケジューリング層は、到着順に、またはデフォルトのFIFO待ち行列ポリシーに従ってエントリを格納する。定義されたスケジューリングポリシーがこの構造上にオーバーレイされる方法については、後述する。新しいノードまたは記述子がプッシュ操作によって層内構造に追加され、ポップ操作の結果として除去される。スケジューリング操作は、層内リンクを操作しない。図11に、単一の処理リソースインスタンスでのより代表的なスケジューリング構造を示す。左から、この例では、2つのFIFO段が優先度段に入力する。階層の2つの段において3つのスケジューリング層がある。スケジューリング層は、図の右側に示すただ1つの出口ノードだけしか持たないが、潜在的に図の右側に示す多くの入口ノードを有することに留意されたい。図12に、FIFOスケジューリング層の1つの詳細図を示す。この図には、この層上のすべてのピア間の二重リンクリストを維持する1組のポインタが示されている。二重リンクリストは、層の任意のメンバの除去ポップの性能を最大にするのに使用される。この詳細図にはタスク記述子のみを示すが、この構造は、スレッドとスケジューリングノードが混ざったものを含む層にも同様に適用することができる。ピア要素間の層内リンクは、プッシュおよびポップ操作時にのみ操作される。[層間構造]プールルート層を除く、層間リンクの構造を図12に示す。各層は、スケジューラルートノードまたはスケジューリングノードでなければならない、親ノードを持つ。これらのノードは、この層の最も適格なメンバを指し示すポインタを格納する。これらの子ポインタは、親ノード内と子ノード内でそれぞれ定義されるスケジューリングポリシーおよびメトリックに従ってスケジューリングイベントの受け取り時に更新される。また、各子ノードは、その親も参照しなければならない。[プールルート層構造]プールルート層構造は、層が、単一の入口ノードおよび多くの出口ノードを持つ特殊な場合である。入口ノードは、図2の作動可能待ち行列構造のアプリケーションスケジューリング部分によって示されるようにスケジューリングコーンが収束する点であり、配布ノードともいう。出口ノードは、タスクがそれらを介して配布され得る処理リソースインスタンスのためにプールルート層を配布スケジューリング構造にリンクさせる。図13に、2つの処理リソースインスタンスを含むプールでのこの種の構造の図を示す。各プール配布層は、プールルートノードPRNおよび1つ以上のプール静的ノードPSNを含まねばならず、他のどんな種類のノードも許容されない。PRNは、HeadIndexフィールド内に格納されるスケジューリングコーンの第1層への参照および配布を考慮されるべき第1のPSNエントリへの参照を含む。共通の配布およびメトリック更新ポリシーが、あらゆるPSNのスケジューラならびにメトリックプッシュおよびポップ演算子内に、それぞれ、格納されなければならない。あらゆるPSNが、HeadIndexフィールドを使ってPRNをその子として参照しなければならない。プール静的ノードの親は、プール接続ノードPANでなければならない。PANとPSNは、1対1マッピングを持たなければ成らない。しかしながら、各処理リソースインスタンスには、それが関与する各配布プールに関連付けられた複数のPANがあってもよい。図14に、処理リソースが2つのプールに関与する構造例を示す。所与の処理リソースがメンバとなり得るプール数は制限されない。さらに、任意のプールが、任意の数の他のプールと、任意の数のその構成処理リソースを共用してもよい。スケジューリングルートノード内には、処理リソースインスタンスが関与する配布コーンのそれぞれに関連付けられた2つのPANがある。加えて、必要に応じて、処理リソースインスタンスへの特定のアクセスを可能にするスケジューリングノードもある。プール配布層の各PSN内で定義されるスケジューリングポリシーは、所与のタスクの実行に最も適格な処理リソースインスタンスが選択される方法を識別する。例えば、このポリシーは、関連付けられたスケジューリングコーンからの優先度の高いタスクの到着時に、現在優先度の最も低いタスクを実行中の処理リソースインスタンスが優先使用のために選択される、優先度のポリシーとすることもできる。図15に、5つの処理リソースインスタンスと、2つの配布プールを備える構成を示す。PRI3は両方のプールに関与することに留意されたい。[挙動]以下の項では、SystemWeaverスケジューリングの挙動を説明する。[一般原則]以下の各項では、SystemWeaverスケジューリングアーキテクチャの主要な基本原則の一部を説明する若干の基本背景情報を示す。ポインタベースの待ち行列法図2に詳しく示すように、SystemWeaver内には複数の潜在的待ち行列点があるが、これらはポインタのみを使って実現される。待ち行列に入れられたエンティティ、SystemWeaverメモリ要素WMEは、決してコピーされない。イベントベースのスケジューリングSystemWeaverは、システム状態の何らかの変更によってそうすることが必要とされたときにのみスケジューリング決定を更新する。状態の変更は、以下の3つのイベントクラスに分けることができる。-プッシュイベント、システム状態の変更が、作動可能待ち行列構造への新しいスレッド記述子これは、新しいスレッド記述子とすることも、システム状態の変更が、そのスレッドを作動可能させている既存のスレッド記述子とすることもできることに留意されたいの導入を生じさせている。-ポップイベント、システム状態の変更が、作動可能待ち行列構造からのスレッド記述子の除去を発生させている。-更新イベント、スケジューリングパラメータが変更され、スケジューリング決定の再評価を必要としている。これらの変更は、以下のものとすることができる。-割り込みすなわち、プッシュイベント。割り込みに関連付けられるブロックされたスレッドが作動可能状態に移行するため。-実行中のタスクによって作成された新しいタスクの到着これは、新しいタスクが他の要因またはイベントに依存しない場合には、プッシュイベントとすることができる。-同期イベント。例えば、セマフォ信号など信号を待ち受けてブロックされている信号があると仮定すると、これは、プッシュイベントである。なぜなら、ブロックされたスレッド記述子が、作動可能状態に遷移するからである。-タスクの実行優先度の変更、更新イベント。-処理リソースインスタンス内のタスクの消費作動可能状態から実行状態への遷移ポップイベント。-タスクのスケジューリングメトリックの変更更新イベント。-スケジューラ層のスケジューリングアルゴリズムまたはメトリックの変更更新イベント。-スケジューラ階層自体の変更更新イベント。システムが定常状態にある場合、SystemWeaverはアイドル状態のままである。原則的に、最も電力効率のよい解決法において、これは、追加のスケジューリングを必要とするイベントの到着を保留にして、SystemWeaverの電源を遮断させることを可能にするはずである。グローバルメトリックへの変更は、再スケジュールイベントを発生させないことに留意されたい。ジャストインタイムスケジューリング所与のスケジューリング層の待ち行列に入れられた新しいエントリが、現在最も適格なエントリであると親HeadIndexによって識別されているエントリとのみ比較される。層スケジューリングポリシーにより、それらが現在の先頭より適格である場合には、HeadIndexフィールドが、新しいエントリを参照するように更新される。新しいエントリは、常に、現在のリンクリスト構造の後に配置される。スケジューリングポリシーがFIFOである場合、HeadIndexポインタは、待ち行列が空でない限り、新しいエントリが到着したときに決して更新されない。したがって、新しいエントリが待ち行列の後に配置されるデフォルト挙動は、FIFOアルゴリズムと等しい。この方式は、プッシュ操作の処理に最小限の時間だけが費やされることを保証し、これは、一般に、スケジューリング性能の待ち時間とみなされる。結果として、ポップスケジューリングは、最悪の場合、ポップ操作時の都度スケジューリング決定を更新するためにスケジューリング層の全内容が評価されなければならないため、より厄介である。しかしながら、物理待ち行列構造において常にネイティブFIFOアルゴリズムを使用することは望ましい。なぜなら、スケジューリングアルゴリズムの変更は、スケジューラ層が再リンクされることを必要としないからである。さらに、ポップスケジューリングは、一般に、アプリケーション実行と並列で実行することができ、したがって、システム性能全体に及ぼす影響がより小さい。スケジューリング解析、ポリシーおよび演算子リアルタイムデッドラインを満たすようにシステムを解析する多くの方法があり、その例としては、EDFEarliestDeadlineFirst方式やRMSRateMonotonicSchedulingや、他の様々な確率論的な方法がある。これらの手法は、アプリケーション特有であり、おそらくは、事実上、固有のものである傾向がある。しかしながら、いかなる場合にも、このようなスケジューリング解析の結果は、1組のスケジューリングポリシーすなわち、優先度、FIFO、ラウンドロビン、重み付き公平待ち行列法をもたらし、それらは、実行時に効率よく配置されなければならない。SystemWeaver技術は、スケジューリング解析によって識別されるポリシーの効率のよい実行時実行を目標とするものである。SystemWeaver内の配置のために、各スケジューリングポリシーは、さらに、1組のスケジューリング演算子に復号化される。各スケジューラ層は、スケジューリング決定が、スケジューリング層または下位のスケジューリング層へのプッシュ、あるいはスケジューリング層または下位のスケジューリング層からのポップの結果としてどのように更新されるかを決定するのに使用される2つの演算子を有する。場合によっては、スケジューリング演算子は、スケジューラとタスク記述子両方のメトリックフィールド内に同様に格納されるオペランドを必要とする。スケジューリングメトリックおよびメトリック伝搬演算子スケジューリングメトリックは、選択されたスケジューリングアルゴリズムによって必要とされ得る情報を格納し、その最も基本的な例が優先度である。その情報を、後続のスケジューリング決定において直接、またはメトリック更新操作でのオペランドとして使用することができるように、メトリックを、最も適格な候補から親ノードに転送する必要がある場合もある。メトリック伝搬演算子は、プッシュとポップ両方のシナリオで、これがどのようにして達成されるかを定義する。階層内のスケジューリングノードの配置に従って、メトリックフィールドは、所与の処理リソース上で現在実行中のスレッドの優先度を反映してもよい。この場合、メトリックフィールドは、優先使用が必要とされるかどうか決定するのに使用される以下のスケジューリング挙動の項を参照されたい。スケジューリングリソース以下の項では、実行時にスケジューリングアルゴリズムを実施するのに使用される様々なリソースを説明する。層スケジューラ層スケジューラ層は、図6の、スケジューラルートノードとすることのできる親、プールルートノードまたは基本スケジューリングノードおよびいくつかの子からなる。子は、基本スケジューリングノード、スレッドまたはタスク記述子またはプール接続ノードとすることができる。子ノードを、それら自体の権限におけるスケジューリングノードすなわち、さらなるスケジューラ層の親ノードとし得るようにすることにより、複雑なスケジューラ階層が構築され得る。プール配布層プール配布層は、プールルートノード1つのみとプール静的ノードだけを含んでいてもよい。1つの処理クラス当たりただ1つのプールルートノードがある。ディスパッチ待ち行列記述子-スケジューラ演算子:現在実行中のタスクが取って代わられるべきかどうか決定するスケジューリングポリシーを定義するのに使用される。-メトリック伝搬演算子:ディスパッチ待ち行列記述子にはメトリック伝搬演算子はない。-メトリック:メトリック要素は、通常、現在実行中のスレッドのメトリックを格納する。スケジューラおよびプールルートノード-スケジューラ演算子:スケジューリングコーンの最も適格な候補を決定するのに使用される。-メトリック伝搬演算子:これらは、常に、スケジューリングコーンの最も適格な候補のメトリックを継承するように設定される。-メトリック:スケジューリングコーンの現在最も適格な候補のメトリックを保持する。スケジューラ層要素-スケジューラ演算子:接続された層から最も適格な子候補を決定するのに使用される。-メトリック伝搬演算子:ユーザ定義される。後続のスケジューリング段の必要に従って設定される。-メトリック:ユーザ定義される。後続のスケジューリング段の必要に従って設定される。メトリック伝搬演算子の中には、これらのフィールドを自動的に更新するものもあることに留意されたい。プール静的ノード-スケジューラ演算子:プール配布層における優先使用に最も適格な候補を決定するのに使用される。-メトリック伝搬演算子:実行タスクメトリックの伝搬を決定するのに使用される。-メトリック:プール配布アルゴリズムの必要に従って設定される。デフォルトでは、これらは、現在実行中のスレッドのメトリックを反映するが、いくつかの配布戦略では、静的割り振りが必要とされることもある。プール接続ノード-スケジューラ演算子:使用されない。-メトリック伝搬演算子:最も適格なタスクメトリックの伝搬を制御するのに使用される。-メトリック:関連するプールルートノードに接続されたスケジューリングコーンの最も適格なタスクのメトリックを格納するのに使用される。スレッド要素-メトリック:スケジューリングでのタスクの適格性に直接関わる情報またはスケジューラがそこから適格性を計算することのできる情報を伝えるのに使用される。[スケジューリング挙動]スケジューリング操作は、以下の2つのサブカテゴリに分けられる。-標準層スケジューリング、スケジューラ層内の1つ以上のエントリが、層内で最も適格なエントリと競い合う。-プール配布スケジューリング、選ばれた処理リソースインスタンスのどれが割り込まれるべきか識別すること。スケジューリングイベントが受け取られない限りスケジューリングアクティビティは行われない。スケジューリングプッシュおよびポップイベント前述のように、システム状態の変更は、プッシュイベントまたはポップイベントを発生させることがある。すなわち、これらのイベントは、再スケジュールを発生させる。すべてのスケジューリング操作は処理保存的である。所与のイベントからおそらく影響を受けるはずのスケジューリング階層の部分だけが再評価され、これらを、再スケジューリング範囲内に存在するという。図17に、基本スケジューリング階層上のイベントでの再スケジューリング範囲を示し、図18に、単純な2インスタンス処理リソースプールでの再スケジューリング範囲を示す。層スケジューリング層スケジューリングは、SystemWeaverスケジューリングアルゴリズムの最も基本的な構成要素である。スケジューリングイベントは、ユーザ構成可能スケジューリング階層によって定義される連続した層スケジューリング操作を生じさせることができる。各層スケジューリング操作の結果は、親スケジューラスケジューリングノードまたはスケジューラルートノードHeadIndexポインタの更新である。また、親スケジューラのメトリックも、定義されたメトリック伝搬アルゴリズムに従って更新され得る。原則として、層スケジューリングは、現在のHeadIndexから開始し、スケジューラ層のメンバの周囲で反復して実際には、待ち時間を最小限に抑えるために、プッシュ操作は、現在の先頭ポインタに対するスケジューリング決定を更新するだけである、以下に従ってHeadIndexへの更新が必要であるかどうか明らかにする。-プッシュまたはポップ操作とすることのできるイベント-イベントの種類プッシュまたはポップに関連付けられたスケジューリングアルゴリズム-層メンバのメトリックより適格なエントリが見つかった場合、HeadIndexはしかるべく更新される。スケジューリング操作の挙動を洗練させるいくつかの特殊な場合も認められる。いかなる場合にも、スケジューリング操作において休止スケジューラ層は無視される。常に、各スケジューリングノードは、主要なフィルパラメータが維持されるように、その子階層内に存在するスレッドまたはタスク記述子の数を知っていなければならない。しかしながら、必ずしも各層を常に完全にスケジュールする必要はなく、直近の下流再スケジュール操作がどこでスケジューリング決定更新を発生させているか識別するフラグが維持される。スケジューリング決定更新を発生させている場合、親層も完全に評価されなければならず、スケジューリング決定更新を発生させていない場合、残りの上流側スケジューラ階層をそれ以上再スケジュールする必要はない但し、他のいくつかの状態更新が必要とされる。任意の再スケジュールにおける最後の操作は、最も適格な作動可能タスクに、所与のPRI上で現在実行中のタスクに取って代わらせるべきかどうか決定することである。ディスパッチ待ち行列記述子は、スケジューリングアルゴリズムと現在実行中のタスクのメトリックの両方を含む。これらは、スケジューリングコーンからの最も適格なスレッドメトリックのコピーを含むスケジューラルートノードメトリックに対して評価され得る。プール配布スケジューリングプール配布スケジューリングは、プール配布層内でのみ行われる。基本層スケジューリングは実行するのに最も適格なスレッド/タスク候補を見つけようとするが、プール配布スケジューリングは、優先使用に最も適格な処理リソースインスタンス候補を見つけようとする。通常、これは、リソースプールの最も適格性の低いタスクを実行中の処理リソースインスタンスを識別し、それと、接続されたスケジューリングコーンからの最も適格な作動可能タスクのメトリックとを比較することを意味する。最も適格な作動可能タスクが、すべての実行中のタスクよりも適格性の低いものである場合、すべてのスケジューリング層がそれぞれアクセス可能な下流タスクの総数を知ったままであるように、あらゆる接続処理リソースインスタンス上の残りの配布コーンが更新されるが、それ以上のスケジューリングは不要である。優先使用候補が識別される場合、スケジューリング更新は、その処理リソースインスタンスだけに向かって伝搬する。図20に、図18に示すプッシュイベントの結果として発生する再スケジューリングでのシーケンス図を示す。基本層スケジューリング操作がプールルート層層6で行われ、続いてプール配布スケジューリング操作が行われる。この例では、ノード5が優先使用に適したものとして選択されたために、層1における層スケジューリング操作が実行される。後続のディスパッチ層スケジューリング操作は、接続された処理リソースインスタンスに対する優先使用を生じる。その後、その下流タスク/スレッドのカウントが維持されるように、層2も更新される。協働および優先使用スケジューリング優先使用スケジューリングは、現在実行中のタスクが、より適格な優先度の高いタスクによって非同期的に割り込まれることを可能にする。優先使用は、実行側処理リソースおよびコンテキストのいくつかの要求、例えば、状態を格納し、優先使用タスクがそのリソースから出た後で再開できることなどを行う。通常、優先使用可能なタスクまたはスレッドは、作動可能状態および実行状態を通じて同じスケジューリング適格性を保持する。これに対して、協働スレッドは完了時にのみ取って代わられ、より優先度の高いタスクはそれを待たなければならない。SystemWeaverタスク管理解決法において、協働スレッドは、それらが実行状態に入るときにその適格性が最大になり、それによって、より優先度の高いタスクの存在および潜在的にその結果として生じる優先使用を排除する。[メトリック伝搬挙動]メトリック伝搬は、実行タスクまたはスレッドのメトリックにおけるスケジューリングイベントまたは変更によって引き起こされ得る。スケジューリングイベントメトリック伝搬スケジューリングイベントの結果として親のスケジューリング層へのHeadIndexが更新されるとき、親層における定義されたメトリック伝搬演算子に従って、メトリックが、最も適格な子メトリックから親メトリックに伝搬される。これらは、操作プッシュまたはポップイベントの性質に依存し、その複雑度の幅は単純なコピーから積和にまで及ぶ。実行スレッドメトリック伝搬現在実行中のスレッドのメトリックは動的に変更されてもよい。これは、ロックされたリソース上での優先度逆転条件を除去するのに使用されてもよい。実行処理リソースインスタンスが配布コーンに関与していない場合、ディスパッチ待ち行列記述子メトリックのみが更新される。配布プールの場合、実行メトリックは、処理リソースインスタンスに関連付けられたプール静的ノードに伝搬される図21。PSNメトリックの更新は、PSN自体の内に保持されるメトリック伝搬演算子によって制御される。いくつかのスケジューリングシナリオでは、静的値がプール静的ノード内において永続的でなければならない。どちらの場合においても、新しい実行メトリックが、実行タスクおよび作動可能タスクの比較適格性に変更を生じないように、再スケジューリングイベントが促される。非プールの場合、これは、単に、新しい実行メトリックに関するスケジューラルートノードメトリックの再スケジュールにすぎない。プールされる場合、プール配布層およびすべての後続層は、再評価されなければならない。アイドル処理処理リソースインスタンスは、アイドル状態に入るときに、実行メトリックを使ってスケジューリング構造を知らせる。本質的に、アイドル処理リソースインスタンスとは、可能な限り優先度の低いタスクを実行しているものであり、したがって、任意のタスクの到着によって取って代わられることになる。実行メトリックのアイドル値への設定は、通常の方法での再スケジューリングイベントを促し、それによって、作動可能状態構造においてこの処理リソースインスタンスを待ち受けるタスクによるアイドルタスクの強制排除を引き起こす。アイドルタスクおよびそれが処理リソースプールにおける電源管理に及ぼす影響の詳細については、以下のプールシナリオにおける電源管理の項を参照されたい。[拡張スケジューリングモード]いくつかの拡張モードおよび挙動が、固有に、またはいくつかのSystemWeaver構成を用いることによって可能である。以下の項では以下の各モードを説明する。これはSystemWeaver内で利用可能なスケジューリングモードの網羅的リストではないことに留意されたい。[タイムスライシング]SystemWeaverシステムは、主として、イベント駆動型であるが、タイムスライシングなど、従来のタイマベースのシステムが利用可能である。タイムスライスされたタスクは、タスクが処理リソースを占有してよい間隔をこの間隔の間に優先使用タスクが作動可能になることはないと仮定して決定する個別のタイムスライス期間に従って処理リソースを共用する。タイムスライスされたタスクは、図1に示す通常のタスクに対してわずかに変更された実行挙動を呈する。図22に、実行状態の2つの部分、通常状態および非推奨状態を示す。この項では、タイムスライスタスクの挙動を、それらを構成するときに遵守されねばならない規則と共に説明する。SystemWeaverコアリソース以下の項では、SystemWeaverサーバコア内のタイムスライス機能を実施するのに使用されるリソースを論じる。カウンタSystemWeaverコア内では、タイムスライス挙動を円滑化するために処理リソースインスタンスごとのカウンタが使用される。また、システムクロックによって供給される単一のプリスケーラも設けられる。プリスケーラのビット分解能は、チップ設計時に設定される。タイムスライス状況標識処理リソースインスタンスごとの割り込み状況レジスタ内の状況ビットがタイムスライス挙動のために設けられる。この状況ビットは、タイムスライスカウンタの有効期限を登録し、ソフトウェアによって、タイムスライスイベントが発生しているかどうか決定するのに使用され得る。構成タイムスライスグループ内のすべてのタスクは、同じ優先度および同じ親スケジューリング層を共用しなければならず、さらに、タイムスライスタスクは、他の非タイムスライスタスクとスケジューリング層を共用すべきではない。タイムスライス親のスケジューリングアルゴリズムは、FIFOに設定されるべきである。図23に、タイムスライスグループが、バックグラウンドにおいて、フォアグラウンドの、イベント駆動型タスクのグループと共に動作し、サービスを必要とするときに優先権を得る、典型的なタイムスライス構成を示す。挙動タイムスライスタスクが最初に実行を開始するとき、システム規模のタイムスライス値が、処理リソースインスタンスに関連付けられたタイムスライスカウンタにコピーされる。タイムスライスタスクが、その通常の実行状態に入るという図24。通常の状態において、各サイクルはこのカウンタを減分する。0に達すると、ディスパッチ待ち行列記述子内に格納されたタスクの実行優先度がハードウェアによって自動的に減分され、タスクは、非推奨状態に入る。この時点において、タイムスライス間隔カウンタは、従来のウォッチドッグモードに切り換わる。いくつかのタイムスライスタスクにサービス提供する単一の処理リソースインスタンスの場合、関連付けられた再スケジュール操作で実行優先度を減分する動作は、作動可能状態構造内のタイムスライスグループの別のメンバによる優先使用を発生させる。タイムスライス状況ビットに問い合わせることによって、ソフトウェアクライアントは、タイムスライス期間が満了していると決定し、現在取って代わられているタスクをFIFO待ち行列の後にプッシュすることができる。したがって、グループは、構成されたタイムスライス規則に従うと同時に、おおむね、SystemWeaverコアスケジューリングおよびクライアント挙動の通常の動作モードを維持する。タイムスライスタスクが、通常のタイムスライス状態にある間に非タイムスライスタスクに取って代わられるとき、未完了のタイムスライス期間がタスク制御ブロックにコピーされる。次いで、タスクは、タイムスライスグループの、FIFO待ち行列の先頭のところにプッシュバックされる。任意の優先使用タスク処理が完了すると、タイムスライスタスクが、タイムスライスカウンタに再指定されている割り込まれたタスクの残りのタイムスライスを用いて再開される。タイムスライスタスクは、非推奨状態において割り込まれるとき、タイムスライスグループFIFO待ち行列の末尾にプッシュバックされる。どちらの場合にも、タイムスライスタスクの優先度メトリックは、その最初に構成された値のままである。タイムスライスグループが、優先使用タスクがないものと仮定して処理リソースインスタンスのプールによってサービス提供される場合、非推奨状態に入ったからといって、必ずしも、別のタイムスライスグループメンバに即座の切り換かわるとは限らない。以下の所見に留意されたい。Tp=td/p式中、1≦p≦tTready=Tp-dTp各メンバタスクを1度実行するタイムスライスグループの完全なローテーションの期間。Tready所与のタスクがその間作動可能状態で待機する1サイクル当たりの時間量。tタイムスライスタスクの数pプール内の処理リソースインスタンスの数d各タイムスライス間隔の期間p=tのとき、他の任意の優先使用タスクがなければ、タイムスライスタスクは間断なく実行されることに留意されたい。実行プロファイル以下の実行プロファイルは、SystemWeaverタイムスライス挙動を示す。図25に、単一のプロセッサと3つのタイムスライスタスクを用いる従来の場合を示す。これらのタスクは、それぞれ、優先使用タスクが、タイムスライスタスクこの場合には2が取って代わられる時点に到達するまで、タイムスライス間隔に従って時分割する。優先度の高い優先使用タスクが完了すると、元のタイムスライスタスクが再開して割り込まれた間隔を完了する。図26に、2つのプロセッサを用いる同じシナリオを示す。最初に、2つのプロセッサの間で3つのタイムスライスタスクが共用される。優先使用が到着すると、タイムスライスタスクは、残りのプロセッサを共用し、優先使用タスクが完了すると、2つのプロセッサでの実行を再開する。図27に、利用可能な処理リソースの数がタイムスライスタスクの数と等しいときに、各タイムスライスタスクが、プロセッサの1つで間断なく実行されることを例示する。優先度の高いタスクがプロセッサの1つの制御権を獲得すると、タイムスライスグループは、定義されたタイムスライス間隔に従って残りのプロセッサを自動的に共用する。[プールシナリオにおける電源管理]処理リソースプールのデフォルト挙動は、配布層内の第1のプール静的ノードからのスケジューリング決定を評価することである。プールルートノードPRNは、通常、配布層内の第1のプール静的ノードPSNを指し示す親ポインタを有する図28。優先使用の候補を評価するとき、比較は、このエントリから開始し、ピアポインタを使ってリストの周りを進む。すべての静的ノードが同じ適格性のものであり、その適格性が、スケジューリングコーンからの候補より低い場合には、最初に遭遇したノードが選択される。したがって、プロセッサの1つ以上がアイドルであるそのメトリックをアイドル値に設定している低負荷シナリオでは、PRNの親ポインタに最も近い処理リソースインスタンスが新しいタスクの処理に好都合であり、親ポインタから最も遠い処理リソースは、長いアイドル期間を呈することになる。この挙動は、処理リソースインスタンスまたはマクロアーキテクチャが電力消費を調整するすなわち、クロックゲーティング、電圧/周波数変調、電源分離などによるができるときに有用である。これらの機能は、ソフトウェアクライアントシムに適切なドライバコードを付加することによって利用され得る。異なる節電対策は、処理リソースが再覚醒しなければならないときに、異なる影響を呈する傾向がある。例えば、クロックゲーティングは、マイクロアーキテクチャ内にすべての状態を維持し得るが、他方、積極的な電圧/周波数スケーリングは、すべての既存の状態を犠牲にし、再覚醒されるときに望ましくない突入電流を示すこともある。所与のPRIが、前述のスケジューリング挙動と共に、異なるコストの多くの電源遮断オプションを有する場合、アイドル状態で費やされる時間に従ってそれらの利用法を管理することは理にかなっている。アイドル状態は、処理リソースインスタンスおよびシステムマクロアーキテクチャの機能に従って、複数の下位状態に分けることができる。いくつかの状態から再開することは、他の状態から再開するよりも高くつくことになる可能性が高い例えば、クロックゲーティング電源遮断を保持する状態を、電源が分離された状態と対比されたい。これらのシナリオをサポートするために、SystemWeaverは、複数のアイドル優先度をサポートする。それらの複数の下位状態を有する処理リソースでは、割り込み応答は、スレッド実行が再開する前に徐々に遷移してアイドル状態に戻ることとしてもよい。これは、処理リソースの、所与の配布のアクティブセットへの漸進的再導入を可能にする。[例]図29に、昇順優先度を使ったアイドル状態における時間の経過に従った処理リソースインスタンスPRIの実行優先度を示す。最初のインスタンスにおいて、アイドルタスクは、優先度を、その可能な限り低い設定に設定し、PRIに、スケジューラからのタスク割り当ての、その配布プールピアと比べて可能な限り高い機会を与える。その後、アイドルタスクは、おそらく、処理リソースマイクロアーキテクチャ内でサポートされる電源遮断モードを呼び出す。この時点において、アイドルタスクは、PRIの実行優先度を高めて、タスク割り当ての可能性を低下させる前の状態のPRIが優先する。同様に、さらなる期間の後、アイドルタスクまたは他の何らかのエージェントは、実行優先度をさらに一層高めるおそらく、PRIへの電源を分離し、それによって静的漏れをなくする。優先度の調節は、PRIのタスク割り振りでの適格性を、一層低い、この処理リソースを再覚醒させるコストこの場合、突入電流、コールドキャッシュ効果などに見合ったものにする。注意:配布層内の第1のエントリの優遇された優先使用は望ましくないこともある。これが該当する場合、前のスケジューリング決定が、後続のスケジューリング操作の新しい開始点になる、異なる挙動が選択されてもよい。この選択は、配布プール内の処理リソースインスタンスの間での優先度の高い優先使用タスクのより公平な配布を示す。[ヒステレシスベースのスケジューリング]進行中の絶対的な正当性に関わり無く、スケジューリング決定を維持することが望ましい場合もある。一般に、これは、個々のタスククラスまたはデータセットのコンテキストを設定するコストが高く、したがって、許容される場合には、複数のタスクにわたって集約されるべき場合である。これが該当する場合には以下が含まれる。-プロセッサキャッシュ-履歴アルゴリズムまたはデータセットのためにデータが取り込まれているキャッシュメモリは、異種のアルゴリズムおよび/またはデータセットとの親和性が低い。これをコールドキャッシュ効果といい、高いキャッシュミス率、したがって、低い性能を示す。-再構成可能なFPGA区画-部分的な実行時再構成可能性は、チップが配置され、動作する間に、FPGAの一部が動的に再構成されることを可能にし、時間が経つにつれて異なるアルゴリズムの実行を可能にする。しかしながら、あるアルゴリズムから別のアルゴリズムに切り換わるコストは高く、システム効率を保証するためにより大きなデータセットにわたって集約されなければならない。これらは両方とも、高くつくコンテキスト切換えの例である。ヒステレシスベースのスケジューリングは、複数のユーザ動作にまたがってコンテキス切換えのコストを集約することによって、悪影響の一部を回避するのに使用されてもよい。メトリックの1つを使ってシステムコストパラメータを表すことによって、ヒステレシスベースのスケジューリングを可能にすることができる。ヒステレシスメトリックは、以下のシステム内の多数のコスト尺度に基づくものとすることができる。-タスクメモリ占有。メモリに余裕がない場合、所与のタスク待ち行列の蓄積されたフットプリントを使って、新しい構成をいつスケジュールすべきかが決定されてもよい。-処理要件。実質的な能動的処理期間にわたるコンテキスト切換えのコストを集約することが望ましい場合。-タイムスライス。待ち時間のジッタが重要である場合。例えば、動的に再構成可能なFPGAの場合、メモリが、再構成可能なファブリックの単一部分上で多重化されたアルゴリズムコンテキストのそれぞれについて作業を蓄積してもよい。この場合、メモリ占有を、いつ配列を再プログラムすべきか決定する際の要因とすることができる。いかなる場合にも、スケジューラ階層を、優先度の高いタスクの到着による強制切換えに対応するよう設計することが可能である。以下に、主要なシステムレベルの課題を要約する。-コンテキスト切換えのコストの影響切換えまでの時間、突入電流-切換えのタイミング-所与のコンテキストが活動状態でない間にその作業の累積をどのようにして管理すべきか以下の各項では、SystemWeaverを使って動的なFPGA再構成を管理する可能な手法を説明する。コールドキャッシュの管理は、類似のスケジューリング技法およびより単純なソフトウェアクライアントシム挙動を使って実現され得る。FPGA実行時再構成プロセッサコンテキスト切換えとの非常に強い相似性があるが、2、3の再定義が必要である。構成-FPGAファブリックの所与の部分を対象とすることのできる様々なプログラムの組の1つ。コンテキスト切換え-FPGAの再構成可能な部分の構成を変更する動作。タスク-所与のFPGA構成によって実行される単一の作業単位。この提案では、FPGAの再構成可能な部分を対象とする構成を割り込み型とは異なり協働的である、すなわち、個別タスクは不可分であり、コンテキスト切換えが行われる前に完了しなければならないものとみなされる。これは、タスクが再入可能である必要がないことを保証し、コンテキスト間の状態保存の問題を、個々の構成を待ち受けるタスクの数が整数値でなければならないという問題に限定する。図30に、未完了タスクの管理の論理図を示す。タスクは待ち行列に編成される。これらの待ち行列は永続的に存在する。特に、これらの待ち行列は、現在活動状態でないFPGA構成の作業を累積する。スケジューラは、いつタスクを切り換えるべきか決定し、タスクグループ内のタスクの実行順序を管理する。再構成サポート論理は、ファブリックを再プログラムし、それがいつ完了するかを知らせる仕組みを管理する。このモデルの協働的性質によれば、コンテキストがスケジュールされるときに、ファブリック内での保存を必要とするデータはない。スケジューラスケジューラは、以下の2つの異なる機能を実行する。-スケジューラは、タスク待ち行列の変化する状態に従って現在のスケジューリング決定を評価する。-スケジューラは、個別タスク待ち行列内のタスクの実行順序を管理する。あらゆるタスク到着が、FPGAファブリックが常に正しい状態にあるように、スケジューリング決定の更新を引き起こす貪欲なスケジューリング。タスク待ち行列内では、スケジューラは、システム設計者によって定義される属性に従って実行順序を規定する。最低限でも、スケジューラは、FIFO、ラウンドロビンおよび優先度ポリシーを提供する必要がある。SystemWeaverを使った再構成可能管理SystemWeaver解決法は、実行時並列実行およびプロセス間通信を管理するために配置され得る、豊富なスケジューリングおよびプロセッサ間通信機能のセットを提供する。SystemWeaverの機能は、同様に、従来の命令セットアーキテクチャ、固定ハードウェア要素および再構成可能なFPGAブロック内部のタスクおよびコンテキスト切換えを効率よく管理することができる。図31にアーキテクチャの一例を示す。SystemWeaverは、FPGAファブリックコンテキスト切換えのスケジューリング管理および個別タスク待ち行列内のタスクの順序付けを処理する。当然ながら、これは、プラットフォーム内の固定構成要素への従来からのタスクのスケジューリングに加えて行われるものである。再構成自体は、個々のSystemWeaverハードウェアクライアントシムを用いて処理される。キャッシュの暖かさを管理する類似のスケジューリング技法は、標準のクライアントシムにそれ以上の要件を課さないことに留意されたい。クライアントシムによって受け取られる各スケジュール済みタスク制御ブロックは、ファブリックの既存の構成と比較される。現在ロードされている構成とスケジュール済みタスクの構成が異なる場合、クライアントシムは、SystemWeaverコアとそれ以上対話せずにファブリックを再構成する。その場合、ファブリック更新決定は、もっぱら、スケジューラによって指図される、タスクの出力順序付けの制御下に置かれる。クライアントシムは、異なる再構成戦略に対応するように再設計され得る。スケジューリングポリシースケジューリングポリシーは、システム設計者によって決定されるべきである。しかしながら、この機能をサポートするのに利用可能でなければならない重要な機能がある。特に、スケジューリングアルゴリズムが、ヒステレシスを示す、すなわち、代替の決定への切換えを保証するのに十分なコストがどこか他の場所に累積されるまであるスケジューリング決定を離れないことが可能である必要である。図示の例では、各タスクは、タスクグループを表す累積されたメトリックに追加されるランダムに生成されるメトリックを有する。所与のタスクグループが処理されるとき、待ち行列からタスクを除去するポップ操作は、この累積カウントを減分する。プッシュ新しいタスクの到着またはポップ操作が発生すると、ファブリックスケジューラは、各候補を、現在実行中のタスクグループのメトリックに対して評価する。図32に示すアルゴリズムによれば、必要な更新=Ccancidate>CcurrentヒステレシスCcancidate候補スケジューリング層内のタスクの累積コストCcurrent現在選択されているスケジューリング層内の未完了タスクの累積コストヒステレシス-コンテキストスラッシングを回避するために加えられるヒステレシス図33に、前述のアルゴリズムを実施するために選択され得るスケジューリング階層を示す。この場合、ヒステレシススケジューラのメトリック1は、ヒステレシスオペランドを格納する。メトリック0は、ヒステレシスグループの静的優先度を格納するのに使用されてもよく、この優先度は、ヒステレシスグループと優先使用グループの間でスケジュールするときに使用される。想定されているのは、コンテキスト変更を強制するのに十分な優先度のタスクがあるということである。結果図32に、このようなシステムの概念的影響を示す。タスクスケジューリング出力は、事実上、意図的にブロックごととされており、これは、システムトラフィック成形に対する影響を管理しながら、所与の任意の構成を最大限利用しようとするものである。図34に、提示されるスケジューリングアルゴリズムのシミュレーションの結果を示す。4つの構成それぞれを待ち受けるタスクの累積コストが、すべてのコスト累積の総計と共にグラフ化されている。選択トレースは、利用可能な構成のうちのどれがアルゴリズムによって選択されるかを示す。[複合スケジューリングアルゴリズムの例]複合スケジューリング演算子は、例えば、プール配布層内の処理リソースプールをスケジュールするときになど役立つ。例えば、処理を待ち受けるタスクの待ち行列の中身がある一定の閾値を超えるときには、おそらく、メンバの一部だけが適格にはるはずである。3つの処理リソース、1つのRISCプロセッサおよび2つのDSP図35が利用可能な場合を考える。理論的には、3つのリソースのそれぞれが、音声符号化操作を実行することができるが、DSPデバイスの方がより効率がよい。この場合、図示のように、音声符号化プール内にRISKプロセッサが存在するはずであるが、その実行に関与する適格性は、その機能を待ち受けるタスクの待ち行列の深さに依存するはずである。このような構成では、プールルートノードメトリック0は優先度を表し、メトリック1は待ち行列の中身を表していてもよい。候補PSNのそれぞれにおいて、メトリック0は、通常、それぞれの処理リソースインスタンスPRI上で実行中のタスクの実行優先度を表す。この場合、メトリック1は、関連付けられたPRIをスケジューリングに適格なものとするのに必要とされる待ち行列の中身を表す。この場合、複合スケジューリングアルゴリズムは以下の通りである。必要な更新=MCURRENT0>MCANDIDATE0MCURRENT1>MCANDIDATE1DSPデバイスと関連付けられたPSNでは、M1は0に設定され、したがって、アルゴリズムは、純粋に、優先度に基づいて決定される。RISKプロセッサの場合、M1は非ゼロであり、したがって、RISKプロセッサがアルゴリズムの実行に関与するには、Mcurrent1によって表される待ち行列の中身がこの値を上回る大きさに達していなければならない。以下では、マクロアーキテクチャまたはトランザクションレベルでのSystemWeaverサーバを説明する。前述のように、SystemWeaverハードウェア解決法には以下の4つの要素がある。-SystemWeaverサーバコア-SystemWeaver密結合メモリ-SystemWeaverデバッグマネージャ-SystemWeaverクライアントシムグローバルメトリックエージェントは、場合によって、システム設計がスケジューリング決定にシステムグローバル状態を含めることを必要とするときに使用される。[1次接続グループ]図38に、コア周辺で見られるインターフェースグループを示す。SystemWeaverコアが容易に統合され得るようにするために、すべての信号は単方向であり、単一のクロックに同期する。以下にこれらのグループの構成メンバの詳細を示す。すべての信号方向は、SystemWeaverコアとの関連で示す。[システム制御グループ]システム制御グループは、SystemWeaverコアの正しい動作を保証するのに必要な雑多な信号を含む。これらには、クロック、リアルタイムクロックおよびリセット信号が含まれる。[グローバルメトリックグループ]システムによっては、スケジューリング決定時にいくつかのシステムメトリックが使用されることが望ましい。これらのメトリックは、相互接続使用度、キャッシュヒット率、メモリ占有度など、様々な要因を表し得る。[周辺割り込みグループ]周辺割り込みグループは、SystemWeaver制御システム外部から供給される割り込みのグループからなる。周辺割り込みグループ内の信号は、例えば、外界との入力インターフェースから、あるいはピンを介してSoCデバイス外部から直接駆動されてもよい。周辺割り込み入力の数は、SoC設計時に定義される。[内部割り込みグループ]内部グループは、SystemWeaverシステムが発する同期割り込みの2つのグループと、実行時システムデバッグ信号の単一グループからなる。信号グループ内の各信号の数は、通常、システム内の処理リソースの数と一致し、SoC設計時に定義される。[密結合メモリインターフェースグループ]このグループは、SystemWeaverを、独自の専用密結合メモリリソースにインターフェースする。接続メモリは、同期SRAMデバイスであるものとする。アドレスパスの幅nおよびデータパスの幅mは、SoC設計時に定義される。[相互接続グループ]プロトコルおよびレイヤ数を含む個別相互接続戦略は、SoC設計時に設定されなければならない。任意の所与のバスインターフェース信号の詳細は、対応するバス特有の実装で見ることができる。[デバッグインターフェースグループ]デバッグマネージャへのインターフェースの詳細については、参照として本明細書に組み込まれる、同時係属の国際出願PCT/GB2005/003525明細書を参照されたい。[密結合メモリTCM]SystemWeaverTCMは、多数のEDAベンダによって供給される標準コンパイラSSRAM技術である。TCMは、アプリケーションの必要に従ってSoC設計時に定義される整数個のSystemWeaverメモリ要素WMEを含む。各WMEは256ビットのメモリ空間を消費する。SystemWeaverは、最大で65536WME、すなわち16MBのメモリをサポートする。待ち行列記述子はWMEを消費するが、典型的なシステムでは、必要なWMEの数は、スレッドサポート要件によって決まるはずである。例えば、SystemWeaverサーバ内で同時に400スレッドをサポートすることのできるシステムは、おおよそ、128KBの接続メモリを必要とするはずである。SoC設計時に、メモリインターフェースは、経路指定を簡略化するように変更され得る。[サーバコアサブブロック記述]図39に、SystemWeaverサーバエンティティの主要な論理構成要素を示す。これらの機能は、図40に示すアーキテクチャ上にマップされる。機能は、4つの1次内部並列処理要素の間で分けられ、以下の機能を実行する。-スレッドスケジューラ入力マネージャTSIM:フリーリスト維持、WME回復。-スレッドスケジューラ保留マネージャTSPM:保留リスト維持、同期、作動可能待ち行列構造への格上げ。スレッド同期マネージャは、保留待ち行列構造の保全性を維持する挿入および抽出。-スレッドスケジューラ出力マネージャTSOM:作動可能待ち行列維持、ディスパッチ待ち行列維持、処理リソース電源管理、割り込み生成。作動可能待ち行列構造の保全性の維持挿入および抽出。-スレッドスケジューラスケジュールマネージャTSSM:作動可能待ち行列構造内の各処理リソースごとのスケジューリング決定の維持。さらに、いくつかのブロックが以下の機能をサポートする。-スレッドスケジューラメモリマネージャTSMM:相互排他およびロッキングを含む、接続されたSystemWeaverメモリへのアクセスを集約する。-スレッドスケジューラ割り込みマネージャTSIC:入ってくるシステム割り込みを内部同期プリミティブに変換する。-スレッドスケジューラインターフェースマネージャTSIF:相互接続インターフェースおよび構成およびSystemWeaverリソースへの実行時アクセスの提供。図40に、SystemWeaverアーキテクチャの基本サブブロックを示す。以下の各項では、これらの構成要素間でのサブブロック内対話を詳述する。各サブブロックは、他のサブブロックに1組の共通メソッドを提示し、それぞれがそのピアに、それぞれによって維持される構造に対する操作を実行することができるようにする。コマンドが個々の条件と共に完了し得る場合、サブブロック内で状況フラグが管理される。サブブロックインターフェース図上の矢印方向はバスの支配を示すものであり、信号グループの個別要素の方向に対する反映ではない。[ステートフル記述子挙動]SystemWeaverの動作時には多数の記述子型が使用される詳細については、参照として本明細書に組み込まれる、同時係属の国際出願PCT/GB2005/001154明細書を参照されたい。これらの記述子の大部分は、ステートレスであるが、スレッド記述子およびスケジューラ記述子は、一定の状況下において多くの状態を経て遷移し得る。本明細書では、これらの状態遷移およびそれらを発生させるイベントを説明する。スレッド記述子SystemWeaverによって内部で認識される2種類のスレッド記述子があり、それらは標準スレッド記述子およびマーカスレッド記述子である。後者は、もっぱら、以前に待ち行列に入れられたスレッド記述子の保全性および順序付けを保証しながら、スケジューリング階層を除去するプロセスを同期させるのに使用される。図41に、スレッド記述子とマーカスレッド記述子の両方がトラバースする内部スレッド状態図を示す。新規状態および空き状態は、SystemWeaver内の永続的状態と直接の相関を持たないメタ状態であることに留意されたい。スレッド記述子内にはリテラル状態変数が存在しないが、代わりに、この状態は、いくつかのフラグによって表される。表3に、フラグ状態と、図41におけるスレッドが存在する状態の間の相関を示す。標準スレッド記述子状態記述以下の各項では、状態、ならびにエントリおよびエントリの終了を生じさせるイベントの簡単な記述を示す。新規状態新規状態は過渡的なものである。新しいスレッドは、プッシュ独立または従属スレッドコマンドによってTSIFに導入される。これら2つの場合は以下のように処理される。-独立スレッド時間または同期依存性のないスレッドは、即座にプッシュ状態に遷移する。このインスタンスでは、TSIFは、TSSMに、スレッドを作動可能待ち行列構造に導入するよう命令する。-従属スレッド時間または同期依存性を有するスレッドは、ブロック状態に遷移する。TSIFは、TSPMに、スレッドを、適宜、保留またはタイミング待ち行列構造に導入するよう命令する。ブロック状態ブロック状態において、スレッド記述子は、外部同期および/またはタイミングベースの同期を待ち受ける。ブロックされたスレッドはTSIFから発せられる。適切な同期が受け取られたとき、TSPMは、スレッドをプッシュ状態に遷移させ、TSSMに、スレッドを作動可能待ち行列構造に導入するよう命令する。プッシュ状態プッシュ状態のスレッドは、同期されており、あるいは、元々独立である場合には、TSPM従属スレッドおよびTSIF独立スレッドが、それぞれの場合にプッシュ状態への遷移を管理しているはずである。TSSMは、スレッドを作動可能待ち行列構造にプッシュし、スレッドを作動可能状態に遷移させる。作動可能状態への遷移は、再スケジュールを発生させる。作動可能状態作動可能状態のスレッドは、プッシュ状態から遷移したものであり、あるいは、TSSMによってフラッシュされて作動可能待ち行列構造に戻されたものである。作動可能状態への遷移は、常に、再スケジュールを促す。スレッドは、作動可能状態から、ポップ状態またはフラッシュ状態に遷移することができ、後者は、ポップ状態を単一操作でフラッシュ状態にトラバースする特定の条件の結果として発生する。スレッドは、それらがTSSMによってスケジューリングに最も適格な候補として指定されたときにポップ状態に遷移する。ポップ状態ポップ状態のスレッドは、個々の処理リソースインスタンスまたはインスタンスグループによる処理に最も適格なスレッドとしてスケジューラTSSMによって指定されており、TSOMによってこの状態に遷移される。スレッドは、以下のようにポップ状態からフラッシュ状態またはゾンビ状態に遷移することができる。-スレッドは、再スケジュールの結果としてより適格なスレッドが識別されていることの結果として、TSOMによってフラッシュ状態に遷移される。-スレッドは、システム処理リソースインスタンスの1つにおける処理の開始の結果として、TSOMによってゾンビ状態に遷移される。ゾンビ状態は、スレッド記述子を、それが解放され得るようになるまで維持する。ゾンビゾンビスレッドは、TSSM内で処理される。ゾンビ状態の存在は、所与のスレッド記述子に関するすべての依存関係が、そのスレッドを解放する前に不要にされていることを保証するためのものである。これは、スレッドがTSSM処理待ち行列の前部に到達した後で保証され、したがって、それ以上の処理を必要としない。フラッシュ状態フラッシュスレッドは、TSSMによって処理される。フラッシュスレッドは、作動可能待ち行列構造に再導入され、再スケジュール操作を発生させなければならない。これが完了すると、スレッドは、TSSMによって遷移されて作動可能状態に戻される。空き状態空き状態は、スレッド記述子によって消費されたWMEがフリーリスト上に戻されることを示す過渡的状態である。マーカスレッド記述子状態記述以下の各項に、状態、ならびにエントリおよびエントリの終了を生じさせるイベントの簡単な記述を示す。新規状態新規状態は過渡的なものである。プッシュマーカスレッドコマンドによって新規のマーカスレッドがTSIFに導入される。マーカスレッドは、常に、ブロック状態をトラバースして、マーカスレッドが最終的に削除するスケジューラ層の状況に影響を及ぼし得るTSPMの入力および出力作業待ち行列内に存在する任意の処理が、マーカスレッド自体の到着前に完了されているようにする。ブロック状態TSPMは、即座に、マーカスレッドをプッシュ状態に遷移させ、TSSMに、スレッドを作動可能待ち行列構造に導入するよう命令する。プッシュ状態TSSMは、マーカスレッドを作動可能待ち行列構造にプッシュし、スレッドを作動可能状態に遷移させる。作動可能状態への遷移は、再スケジュールを発生させる。作動可能状態マーカスレッドは、作動可能待ち行列構造に導入されると、その直接の親をロック解除する。その場合、その親スケジューリング層の解放は、従属スレッド数のカウントの制御下にある。マーカスレッドは、それらの親の従属スレッドカウントがゼロに到達している、すなわち、SystemWeaver内に、親スケジューリング層の存在に依存するスレッド記述子がそれ以上ないときにのみ、作動可能状態から遷移するのに適する。標準スレッドと同様に、マーカスレッドは、作動可能状態から、ポップ状態またはフラッシュ状態に遷移することができ、後者は、単一動作でポップ状態をフラッシュ状態にトラバースする特定の状態の結果としてものである。マーカスレッドは、TSSMによってスケジューリングに最も適格な候補であると指定されているときにポップ状態に遷移する。ポップ状態ポップ状態のマーカスレッドは、スケジューラTSSMによって特定の処理リソースインスタンスまたはインスタンスグループによる処理に最も適格なスレッドであると指定されている。このスケジューリング決定は、スケジューリング層が空であり、それ以上従属スレッドが存在しないことを示す特殊な場合であることに留意されたい。マーカスレッドは、以下のように、ポップ状態からフラッシュ状態またはゾンビ状態に遷移することができる。-マーカスレッドは、再スケジュールの結果としてより適格なスレッドが識別された結果として、フラッシュ状態に遷移される。-マーカスレッドは、システム処理リソースインスタンスの1つにおける処理の開始の結果としてゾンビ状態に遷移される。ゾンビ状態は、解放され得るようになるまで、マーカスレッド記述子を維持する。さらに、マーカスレッドの親も、この状態にある間に、削除のためにマークされる。ゾンビ状態ゾンビマーカスレッドの処理は、通常のスレッド記述子の処理と類似している。また、マーカスレッドの親スケジューリング層も、この状態内で削除される。空き状態空き状態は、スレッド記述子によって消費されたWMDがフリーリストに戻されることを示す過渡的状態である。スケジューラ層状態図また、スケジューラ層も、暗黙的状態を有する。静的な層、すなわち、システムの実行時全体を通じて永続的である層では、唯一の状態が活動状態である。残りの状態は、動的スケジューリング層、すなわち、実行時に出入りする層によって使用される。表4に、フラグ状態と、図42にスケジューラ層が存在する状態の間の相関を示す。スケジューラ層記述子状態記述以下の項では、状態、ならびにエントリおよびエントリの終了を生じさせるイベントの簡単な記述を示す。新規状態新規状態は過渡的なものである。初期設定時または実行時に、新規のスケジューラ層がプッシュ独立要素によってTSIFに導入される。休止状態休止状態において、スケジューラ層は、スレッドおよび潜在的に追加の子階層を累積することを許されるが、TSSMによってスケジュールされることは決してない。休止状態には以下の2つの方法で入ることがある。-休止状態で新しいスケジューリング記述子が作成されることがある。-スケジューリング層が実行時に変更され、TSIFを介して発行された明示的システムコマンドによって休止状態に置かれることがある。休止状態は、明示的システムコマンドによってのみ終了され得る。活動状態活動状態のスケジューラ層は、能動的にスケジューリングに関与し、ロックされる。すなわち、活動状態のスケジューラ層は、空になったときに除去されない。静的スケジューラは、通常、この状態で作成される。動的スケジューラは、TSIFを介して受け取られる明示的システムコマンドによってこの状態に遷移する。スケジューラ層は、マーカスレッドが受け取られるときにのみ活動状態を終了し、そこで保留空き状態に入る。保留空き状態スケジューラ層は、以下の基準が両方とも満たされるまで保留空き状態に留まる。-この層を参照する記述子の数の尺度を保持するカウントである、従属要素の数が0になる。-子要素の数がゼロになる。これは、保留空き状態への遷移を引き起こしたマーカスレッド記述子もポップされていることを示唆し、スケジューラ層がそれ以上の依存関係を持たないときにのみ発生する動作であることに留意されたい。空き状態空き状態は、スケジューリング層記述子によって消費されたWMEがフリーリスト上に戻されることを示す過渡的状態である。[サブブロック間挙動]以下の項では、複数のサブブロックが関与するSystemWeaver挙動の態様をカバーする。動的スケジューリング階層操作システム実行時にスケジューリング階層を追加し、除去することができる。いくつかのユーザレベル手順が守られる場合、SystemWeaverは、システムの保全性、および、スケジューリング階層のある部分から別の部分に遷移するスレッド記述子の順序付けを保証する。詳細については、上記を参照されたい。動的スケジューリングメトリック更新標準またはマーカスレッド内のメトリックを更新することができる。挙動は、以下のようにスレッド状態に依存する。-スレッドがブロック状態にある場合、適切なコマンドがTSPMに送られる。保留待ち行列はソートされるため、スレッドは、適切な時点において再度出現するようにメトリックが更新されるときに待ち行列から除去され、再挿入される。-スレッドが別の任意の永続的状態にある場合、メトリック更新を実行し、スケジューリング階層の適切な部分を再スケジュールするコマンドが、TSSMに発行される。スケジューリングのためのTSOM/TSSM対話処理リソースインスタンスに対するスレッド記述子のスケジューリングでは、TSOMとTSSMの両方が機能を果たす。TSOMとTSSMの間の対話のいくつかのシーケンス図の例を図72および73に示す。[サブブロック内アーキテクチャおよび挙動]各サブブロックは、その1次入出力、またはそのピアおよび外界への物理インターフェースの観点から、また、そのコマンドインターフェース、または適切な物理インターフェースを介してコマンドプロトコルを使って呼び出され得るメソッドの観点から論じられる。[TSIFインターフェースマネージャ]インターフェースマネージャは、相互接続グループから受け取られるコマンドの実行を調整し、それらを他のサブブロックに配布する役割を果たす。以下の項では、TSIF内に存在し、内部消費のためのコマンドの単なる変換の範囲を超える機能エンティティを説明する。アーキテクチャTSIFは、主に、相互接続インターフェースを介して受け取られるコマンドを解釈して、残りのサブブロックに対する1つまたは多くの内部コマンドにする。以下の各項では、TSIF内に存在するアーキテクチャリソースの詳細を示す。セマフォ領域ロックセマフォ領域ロックSRLは、システムリソースへの排他アクセスを得るために任意のシステムリソースによって原子的に試験され、ロックされ得るリソースを提供する。セマフォ領域ロックは、以下の任意の数の理由で使用され得る-1つ以上の共用リソース例えば、セマフォオブジェクト、タスク制御オブジェクトなどを含むシステムメモリの領域をロックし、それによって保全性を保証するため。-マルチサイクルコマンドアクセスのためのSystemWeaverコマンドインターフェースをロックするため。-マルチサイクルイベントのためのSystemWeaverデバッグイベントインターフェースをロックするため。SRLは、ロックされた状態とロック解除された状態の2つの状態を有する。SRLからの読出しは、ロックを得ようとする試行として定義され、SRLへの書込みは、ロック解除しようとする試行として定義される。個々のSRLをロックする処理リソースインスタンスと、個々のSRLを解除する処理リソースインスタンスの間に必要な相関はない。その挙動を以下で説明する。-ロック解除状態:ロック解除状態では、SRLからの読出しが、読取装置に、ロック試行が成功したかどうか示す制御コードを返す。この状態では書込みは影響を及ぼさない。-ロック状態:ロック状態では、SRLからの読出しが、SRLが利用できないことを示す。書込みはSRLを解放する。コマンド処理TSIFは、システム相互接続から受け取られるコマンドを、おそらく、複数の内部コマンドに分解する。ウォッチドッグおよびタイムスライスサポート各処理リソースインスタンスごとに、場合によって、デュアルモードタイマカウンタが設けられる。2つのタイマモードは、ウォッチドッグとタイムスライスであり、デフォルトモードはウォッチドッグである。ウォッチドッグ挙動は、ウォッチドッグサイクルおよび個別カウントによって定義される図44。ウォッチドッグサイクルは、システムクロックの降圧バージョンであり、降圧は、シリコン設計時にシステム定数によって定義される。図46aに、各プレスケールウォッチドッグクロックサイクルごとの、各処理リソースインスタンスごとの挙動を示す。-ウォッチドッグ割り込みが適切であるかどうか決定するために個別ウォッチドッグカウンタに問い合わせが行われる。-必要な場合、ウォッチドッグ割り込みが生成される。ウォッチドッグタイマカウントは、タイマが関連する処理リソースインスタンスからの各制御アクセスごとにリセットされ、したがって、そのウォッチドッグ間隔の間にSystemWeaverにアクセスしない処理リソースのみがウォッチドッグ割り込みを受ける。前述のタイムスライシング挙動は、TSIFとTSOMの間で区切られる。TSIFでは、各処理リソースに割り振られるタイマは、タイムスライスサポート専用とすることができる。タイムスライス割り込みが発生すると、TSOMにおいて自動化メトリック操作が提供される実行優先度が減分される。処理リソース自体は、自動化メトリック更新の結果として、標準の優先使用が適切になった場合にのみ取って代わられる。図45に、TSIF内のタイムスライスサポート論理のシステムごとクロックサイクル挙動を示す。図46bに、プレスケールタイムスライスクロックの各サイクルごとの、各処理リソースごとの挙動を示す。タイムスライスイベントが発生した後、タイマモードがウォッチドッグモードに戻されることに留意されたい。割り込み処理SystemWeaverは、システムからの割り込み、すなわち周辺割り込みを受け入れ、システムへの割り込み、すなわち処理リソースインスタンス割り込みを供給する。周辺割り込み周辺割り込みは、TSIF内でマスクされ、調整されてもよいエッジ/レベルトリガ、負/正論理など。処理リソースインスタンス割り込み以下の機能を提供するために、TSIF内に割り込み処理リソースが設けられる。-割り込み表明のソースを含む、割り込み状況を維持する優先使用、タイムスライス、ウォッチドッグ-マスク機能TSIF内では、SystemWeaverコマンドインターフェース上での割り込みマスキングを自動化するための特別な機能が実装される。コマンドインターフェースはシステム内のすべての処理リソースに共通のアクセス点であるため、保全性および効率性が維持されなければならない。このために、SystemWeaverは、処理リソースがSystemWeaverコマンドインターフェース上でのロックを獲得すると、その処理リソースがこの重要なコード部分の間に割り込みされないように、割り込みマスキングを自動的に処理する。各処理リソースインスタンスごとに、受け取られている正常なSystemWeaverコマンドインターフェースセマフォ領域ロック要求の数を追跡するカウンタが維持される。各ロック要求はカウントを増分し、各ロック解除要求はカウントを減分する。カウンタがゼロから増分されると、割り込みが自動的にマスクされ、カウントがゼロに減分されると、割り込みが自動的にアンマスクされる。[TSIM入力マネージャ]入力マネージャは、WMEフリーリストを助けて、TSIFからのポップ要求および多くのサブブロックTSIF、TSPM、TSOM、TSSMからのプッシュ要求を処理する。アーキテクチャTSIMはただ1つのアーキテクチャエンティティ、SystemWeaverメモリ要素WMEフリーリストを含む。図48に、このリストの構造を示す。フリーリストは、後入れ先出しLIFOポリシーに従って動作する。リストのあらゆるメンバがC_SCHED_ENTRY_FREE型のものであり、C_FREE_QUEUE_POINTER_INDEXによって参照されるポインタを使って個々にリンクされる。メソッドインターフェース基本リンクリストハウスキーピングメソッド状況の取得および設定と共に、入力マネージャは、そのインターフェース上で以下のコマンドを提示する。プッシュフリーインデックスC_TSIM_CMD_PUSH_INDEX呼び出し元:TSIF、TSSM、TSOM、TSPMプッシュフリーインデックスコマンドは、解放されたWMEインデックスをフリーリスト上にプッシュバックするのに使用される。その引数を以下に要約する。ポップフリーインデックスC_TSIM_CMD_POP_INDEX呼び出し元:TSIFポップフリーインデックスコマンドは、フリーリストから空きWMEインデックスをポップするのに使用される。その引数を以下に要約する。[TSPM保留マネージャ]保留マネージャは、同期またはタイマベースの、何らかのイベントを保留にしているブロック状態のタスクまたはスレッド記述子を助ける。個別保留リストのアソシエーションは、ユーザ制御下またはより上位層のソフトウェアの制御下にあり、セマフォ、競合ドメイン、割り込みまたはこれらの任意の組み合わせを表し得る。アーキテクチャ保留マネージャは、2つの主要要素、可変数の保留待ち行列および1つのタイマ待ち行列を備える。保留待ち行列は、何らかの外部イベントによる同期を待ち受けるスレッドのリストを格納し、タイマ待ち行列は、タイムアウトを待ち受けるスレッドのリストを格納する。スレッド記述子が両方のリストのメンバであることが可能であり、実際には一般的であり、そのため、スレッド記述子には、外部同期イベントを、限られた長さの時間にわたって待ち受けることが許容される。保留待ち行列構造図50の保留待ち行列構造は、その内容を処理するTSPM内のリソースおよび機能と共に、主に、密結合メモリ内でインスタンス化される。TSPM自体は、先頭ポインタ、および保留待ち行列記述子のリスト、すなわち、リストのリストを参照するいくつかの要素を含む。各保留待ち行列はスレッド記述子のリストを含み、保留待ち行列の数は、実行時に動的に増減し得る。保留待ち行列にはスレッドが定義されたタイムアウトを有する場合にのみ現れるタイマ待ち行列と異なりブロック状態のすべてのスレッド記述子が存在する。複数の保留待ち行列の使用は、アプリケーションおよびアプリケーションプログラマの必要と好みに依存する。保留待ち行列は、特に、以下と関連付けられ得る。-セマフォ。これは、それぞれスレッドをほとんど含まない多数の保留待ち行列を生じる可能性が高い。したがって、最悪の場合の同期応答時間は、これらの状況下では低くなる。-競合ドメイン。競合ドメインは、同じリソースを求めて競合する複数のエンティティ内のゾーンである。例えば、スレッドに対してプロセスが競合ドメインとみなされ得る。-割り込み。最速の応答時間のために、割り込みは、通常、専用保留待ち行列に集められる。タイマ待ち行列と異なり、保留待ち行列は、純粋に、イベントベースのものである。これらのイベントとは以下のものである。-プッシュイベント。新しいスレッドが、すでに存在し、または作成されなければならない保留待ち行列に導入される。-同期イベント。1つ以上のスレッドが作動可能待ち行列構造に遷移しなければならない。以下の各項では、これらの状況下での挙動を説明する。プッシュイベントプッシュイベント時に、TSPMは、識別されたソート演算子metric[0]に従ってスレッド記述子をリスト中のどこに挿入すべきか決定しなければならない。考慮されなければならない以下の2つの状況がある。-既存の保留待ち行列へのプッシュ-新しい保留待ち行列へのプッシュ前者の場合は単純であり、リストは、挿入点が見つかるまで順番に問い合わせされる。従来の昇順優先度の場合、ソート演算子は、C_PEND_MNGR_PUSH_GTRより大きいに設定され、既存のリストがサーチされる。挿入点は、新しいスレッドのmetric[0]が次のリストメンバmetric[0]より大きいときの点によって定義される。新しい保留待ち行列が必要とされるとき、その保留待ち行列挿入は、新しいスレッドエントリの挿入の直前に行われる。同期イベント同期イベントは、割り込みコントローラTSICから、またはコマンドインターフェースを介して受け取られ得る。同期は、以下の2つのモードで行われ得る。-リテラルモード。コマンド引数がWMEインデックスへのリテラル参照を行う。-相関モード。スレッド記述子内のフィールドと同期プリミティブ内のフィールドの間の相関が求められる。リテラルモードでは、スレッド記述子のインデックスがコマンドに渡されるため、最も適格な候補に必要とされるサーチはない。相関モードは、最も適格な1つ以上の同期候補が最初に見つかることを必要とする。相関モードは、以下の3つのサブタイプからなる。-通常。指定された保留待ち行列内の最も適格な候補だけが同期される。-マルチキャスト。指定された保留待ち行列内のすべての適格な候補が同期される。-ブロードキャスト。すべての保留待ち行列内のすべての適格な候補が同期される。最も適格な候補は、コマンドおよびやはりコマンド内の要素識別子と共に渡される引数によって識別される。要素識別子は、適格性を識別するために、候補スレッド記述子のフィールドのどれが渡された引数に比較されるか決定する。通常モードでは、アルゴリズムは、適格な候補が見つかるまで保留待ち行列を上から下へ反復し、見つかった時点において、適格な候補が保留リストおよび、該当する場合には、タイマ待ち行列から取り除かれ、作動可能待ち行列構造に送られる。マルチキャストおよびブロードキャストモードでは、このプロセスが、その保留待ち行列または各保留待ち行列がそれぞれ空になるまで続く。タイマ待ち行列のメンバの除去には特別な条件が関連付けられる。詳細については次項を参照されたい。タイミング待ち行列構造および操作タイムアウト待ち行列に導入される各新しいスレッドは、最初に、絶対タイムアウト値を含んでいる。この値は、インターフェースマネージャによって、引数として受け取られる32ビット相対または絶対タイムアウトから導出されていてもよい。タイマ待ち行列は、C_THREAD_PENDING_QUEUE_TIMER_PTR_INDEXを使って、スレッド記述子のリストを、最も近いタイムアウトをリストの先頭にして、それらのタイムアウトの順に格納する。これらのスレッド記述子は、C_THREAD_PENDING_QUEUE_PRIORITY_PTR_INDEXによって索引付けされる第2のポインタセットによって、優先度リストのメンバにもなることに留意されたい。図51に、タイムアウト待ち行列の基本構造を示す。タイマ待ち行列の個別スレッド記述子メンバ内の絶対タイムアウト値を格納するのではなく、直前のスレッド記述子のタイムアウトに対するタイムアウトが格納される。この値は、浮動小数点表現を使って16ビットフィールド内に格納され、浮動小数点タイマ形式の仮数は、5ビットの指数を有する無名数の11の有効ビットを含む。タイマ待ち行列の先頭要素のタイムアウトフィールドは、常に、TSPMTimerHeadTimeoutレジスタにコピーされ、その後リセットされる。タイミング同期アーキテクチャの動作は、以下のいくつかの永続的内部リソースを使用する。-TimerHeadIndex。タイマリストを指し示す先頭ポインタ-TimerNumElements。タイマ待ち行列内の要素数-TimerHeadTimeout。先頭要素のタイムアウトのスナップショット-TimerDivider。システムクロックのプリスケーラ-TimerDividercounter。除算器のカウントダウンリソース-TimerCounter。各プレスケールクロックティックごとに単調に増加し続ける32ビットカウンタリソース-TimerErrorAdjustCounter。エラーを累積し、収容するのに使用される32ビットカウンタTimerDividerレジスタが0に設定される場合、タイマ機能は使用不可とされる。タイマ待ち行列サイクル挙動図52に、各プレスケールクロックティックごとに行われる操作を示す。TimerHeadTimeoutは、保留タイマベースの同期がないタイマ待ち行列が待機状態にあるときには非ゼロであり、したがって、どんな処置も行われない。TimerHeadTimeoutが0になり、タイマ待ち行列が空でないときに、システムは、TimerErrorAdjustCounterの値に従って2つの状態の一方を採用する。TimerErrorAdjustCounterが0である場合、このサイクルでTimerHeadTimeoutの失効が発生しており、最終的にはタイマ待ち行列および、ハウスキーピングのためには優先度待ち行列からのポップを生じさせるタイマ同期プリミティブが作成される。その直後に、TimerErrorAdjustCounterは、それが、タイムイベントプリミティブの処理が完了した後でリセットされるまで、単調に増分され続ける。タイマ待ち行列イベントタイマ待ち行列操作を引き起こす以下の3つのイベントがある。-タイムイベントプリミティブC_TSPM_CMD_TIME_PRIMITIVE-非ゼロタイムアウトを用いるスレッドプッシュイベントゼロに設定されたタイムアウトを有するスレッドはタイマ待ち行列に入れられない-結果としてハウスキーピング実行としてのタイマ待ち行列からのスレッドの除去を生じる非タイマベースの同期イベント図53に、タイムアウト論理の動作モードの非常に基本的な表現を示す。待機状態にあるとき、TimerHeadTimeoutは非ゼロであり、プレスケールクロックに従って単調に減分する。TimerErrorAdjustCounterは、この状態ではゼロに維持される。TimerHeadTimeoutが0に達すると、タイマ待ち行列の先頭はタイムアウトしており、FSMは活動状態に遷移し、そこでポップ操作が処理される。この状態内では、TimerHeadTimeoutはゼロであり、TimerErrorAdjustCounterは、各サイクルごとに単調に増分する。このエラーカウントを使って、前のタイムアウトイベントを実行するのに費やされた時間が後続のタイムアウトイベントを適格にしているかどうかが判定される。次の未完了の適格なタイムアウトイベントがなくなると、FSMは遷移して待機状態に戻り、TimerErrorAdjustCounterがリセットされる。タイマ導出ポップ操作の潜在的シーケンスの最初のものが、スレッド記述子内のリセットタイムアウトフィールドから推論される図52参照。タイマ待ち行列の先頭として、このスレッドが常にポップされる。その後、TSPMは、後続のポップが適格であるかどうか評価して、この追加リソースTimerLastErrorが、累積されたポップスレッド記述子タイムアウトデルタの合計を維持するのに使用されるのを容易にしなければならない。タイマ待ち行列の後続メンバの次の反復の都度、TimerLastErrorがTimerErrorAdjustCounterから差し引かれ、タイマ待ち行列先頭のところの新しいスレッド記述子のタイムアウトと比較される、正規化エラーカウントを生成する。このスレッド内のタイムアウトデルタが正規化エラーカウントより小さい場合、このスレッド記述子もポップされるべきである。最初、TimerLastErrorはゼロであり、したがって、スレッドタイムアウトデルタは、直接、TimerErrorAdjustCounterに対して比較される。図54に、スレッド1タイムアウトが経過し、関連付けられたポップ操作が行われた後の前のタイマ待ち行列構造を示す。TimerLastErrorは、スレッド2デルタによって更新されており、スレッド1ポップ操作の期間は、今やスレッド2も適格であることを意味することに留意されたい。図55に、スレッド2のポップ後の待ち行列の状態を示す。スレッド2デルタがTimerLastErrorに加算され、スレッド記述子デルタの合計の実行累積を生成していることに留意されたい。また、スレッド2に対するポップ操作は、スレッド3が適格になるのに十分な長さの時間を要したことにも留意されたい。図56に、スレッド3のポップ後の状態を示す。この場合、後続のスレッド、スレッド4はポップに適格ではなく、そのため、タイマ待ち行列の状態は、待機に戻ってもよい。TimerHeadTimeoutは図示のようにリセットされなければならない。活動状態から遷移して待機状態に戻るとき、TimerHeadTimeoutは正しくリセットされなければならないことに留意されたい。これは、新しいタイミング待ち行列先頭のデルタからTimerErrorAdjustCounterとTimerLastErrorの差を差し引くことによって達成される。新しいスレッドがタイミング待ち行列に導入され、またはプッシュされるときには、2つの場合、すなわち、タイミング待ち行列の先頭へのプッシュと本体へのプッシュが考慮されなければならない。-先頭へのプッシュでは、TimerHeadTimeoutは、単に、スレッドデルタに設定される。待ち行列が空でない場合、旧い先頭記述子デルタは、TimerHeadTimeoutマイナス新しいスレッドデルタに設定される。-本体へのプッシュでは、タイマ待ち行列ブロックは、タイマリストをウォークして、スレッド記述子をどこに挿入すべきか識別しなければならない。次いで、リストの次のデルタが、新しいスレッドのデルタの追加を受け入れるように調整される新しいスレッドデルタが次のスレッドデルタから差し引かれる。ポップ操作ポップ操作は、タイマの結果であれ、外部イベント同期イベントの結果であれ、同様に処理される。ポップされるスレッドがタイマ待ち行列の先頭にある場合とそうでない場合の2つ場合を考察すべきである。前者の場合には、タイマ待ち行列が待機状態にある場合と、タイマ待ち行列が活動状態にある場合の3つのシナリオがある。-待機中のタイマ待ち行列の先頭からのポップ操作では、TimerHeadTimeoutが、タイマ待ち行列の次のメンバのタイマデルタに加算されて新しいTimerHeadTimeoutを形成するタイマベースのポップでは、TimerHeadTimeoutの値は、常NHTSAに、ゼロになることに留意されたい。-活動状態のタイマ待ち行列の先頭からのポップ操作で、TimerErrorAdjustCounterが次のスレッド記述子のデルタより大きい、すなわち、次のスレッドがタイマベースの同期に適格である場合、エラーカウンタ、TimerErrorAdjustCounterは、ポップされるスレッドのデルタにリベースされる。-活動状態のタイマ待ち行列の先頭からのポップ操作で、TimerErrorAdjustCounterが次のスレッド記述子のデルタ以下である、すなわち、次のスレッドがタイマベースの同期に適格ではない場合、デルタは、エラーカウンタによって減分され、TimerHeadTimeoutが結果で更新される。タイマ待ち行列は、事実上、待機状態に戻る。ポップされたスレッド記述子がタイマリストの先頭でない場合、タイマ待ち行列の次のスレッドのデルタが、現在除去されているスレッド内のデルタ分増分されなければならない。メソッドインターフェース保留およびタイマ待ち行列の基本リンクリスト状況操作取得および設定状況と共に、保留マネージャは、そのインターフェース上で以下のコマンドを提示する。同期プリミティブC_TSPM_CMD_SYNC_PRIMITIVE呼び出し元:TSIF、TSIC同期プリミティブコマンドは、保留待ち行列内に格納されているブロックされたスレッド記述子を解放する制御パケットを発行する。引数を以下に示す。保留待ち行列へのスレッドの追加呼び出し元:TSIFこのコマンドは、新しいまたは既存の作業待ち行列にスレッド記述子を追加する。このコマンドは、作業待ち行列におけるスレッド記述子の存在によって保留マネージャに示唆される。以下の表に、このコマンドに関連するスレッド記述子のフィールドを示す。マーカスレッド処理呼び出し元:TSIFこのコマンドは、単に、マーカスレッドをスケジュールマネージャ作業待ち行列に渡す。これは、マーカスレッドがスケジューラ解体を引き起こす可能性が生じる前にすべての従属スレッドが保留マネージャによって処理されるよう保証するのに使用される。同期プリミティブ呼び出し元:TSIFこのコマンドは、指定された保留待ち行列に同期プリミティブを発行する。このコマンド構造には以下の引数がある。メトリック更新呼び出し元:TSIFこのコマンドは、ブロックされたスレッドのメトリックを更新し、適切な保留待ち行列の再ソートを行わせる。このコマンドは、識別されたスレッドがブロックされなくなった場合、TSSMに渡されてもよい。このコマンド構造には以下の引数がある。保留待ち行列ロック解除呼び出し元:TSIFこのコマンドは、保留待ち行列が空になったときに、解放されてフリーリストに戻されるように、保留待ち行列をロック解除する。このコマンド構造には以下の引数がある。[TSOM出力マネージャ]出力マネージャは、次の実行スレッド記述子、および現在実行中のスレッドの実行メトリックを参照するディスパッチ待ち行列構造を助ける。1.1.1アーキテクチャTSOMのアーキテクチャは、図58に示すディスパッチ待ち行列構造を中心とする。出力マネージャは、各DQDがProcElementIDフィールドを介してシステム処理リソースインスタンスと関連付けられるディスパッチ待ち行列記述子のリストを維持する。TSOMの機能全体を詳細に参照するDQDへの2つの要素グループがある。第1のグループ、実行中心の要素は、ProcElementID、メトリック0、メトリック1およびデフォルトメトリック0を備え、タスクの実行状態を参照し、タスクの実行状態内で管理される。第2のグループ、作動可能待ち行列中心の要素は、ルートスケジューラインデックス、優先使用インデックスおよび次の優先使用インデックスを備え、実行を待ち受けるスレッドの作動可能待ち行列構造を参照する。また、TSOMは、システム内処理リソースインスタンスへの帯域外信号通常は割り込み、および作動可能待ち行列構造からのスレッド記述子のポップも管理する。実行中心の要素以下は、ディスパッチ待ち行列記述子内の実行中心の要素の用法の簡単な説明である。-ProcElementIDこれは、ディスパッチ待ち行列記述子が結合される処理リソースインスタンスを参照するインデックスを格納する静的フィールドである。-メトリック0、1は、アイドルタスクおよび潜在的に多数の電源遮断状態を含む現在実行中のタスクの実行メトリックを格納するのに使用される、動的に更新されるフィールドである。-デフォルトメトリック0は、現在実行中のスレッドをSystemWeaverサーバにプッシュバックし、したがって、定義上アイドル状態になるときに、アイドルメトリックを自動的に復元するための最適化をサポートするのに使用される静的フィールドである。作動可能待ち行列中心の要素以下は、ディスパッチ待ち行列記述子内の作動可能待ち行列中心の要素の用法の簡単な説明である。-ルートスケジューラインデックスは、ディスパッチ待ち行列と関連付けられたスケジューリングルート層への静的参照である。-優先使用インデックスは、所与のリソースの次の実行に現在最も適格な候補を格納する動的フィールドである。優先使用インデックスは、完全にTSOM内で管理され、適切な場合には、ディスパッチ待ち行列イベントの結果として設定される。-次の優先使用インデックスは、スケジューリング階層内の次に最も適格なスレッドの親またはスレッドインデックス自体を格納する動的フィールドである。次の優先使用インデックスは、TSSMによってのみ設定され、TSOMに、最も適格なスレッドの作動可能待ち行列構造内の位置を知らせる伝達手段として使用される。TSOMは、通常、処理後にこのフィールドをリセットする。ディスパッチ待ち行列イベントディスパッチ待ち行列イベントは、以下の2つの理由で発生する。-再スケジュールイベント:ディスパッチ待ち行列イベントは、スケジュールマネージャTSSM内の再スケジュール操作が、ディスパッチ待ち行列に必要とされる状態の変更、すなわち、通常は、作動可能待ち行列イベントプッシュ、ポップまたはメトリック操作を処理した結果としての優先使用を識別する都度発生する。-ディスパッチ待ち行列ポップイベント:優先使用インデックスによって参照されたスレッドインデックスがインターフェースマネージャTSIFによってポップされている。このイベントは、ディスパッチ待ち行列自体の内のC_DISPATCH_DESC_POPPED_FLAGによって索引付けされるディスパッチ待ち行列ポップフラグによってTSOMに通知される。ディスパッチ待ち行列ポップイベントの場合、ポップされたスレッドは、ゾンビ状態図41参照に遷移し、まだそこに存在しない場合には、TSSMによる解放のために作業待ち行列にプッシュバックされる。その後、TSOMは、作動可能待ち行列階層からそのスレッドをリンク解除する。再スケジュールイベントとディスパッチ待ち行列ポップイベントの両方で、ディスパッチ待ち行列イベントの処理が続いて、ディスパッチ待ち行列記述子内での優先使用インデックスの再取り込みが開始される。デフォルトでは、次の優先使用インデックスがスレッド自体の権限内のスレッドインデックスでない場合、これは、次の優先使用インデックスによって識別されるスケジューリング層からスケジューリング階層をウォークすることによって取り込まれる。これが完了すると、識別されたスレッドインデックスは、優先使用インデックスフィールド内に配置され、スレッドは、事実上、作動可能待ち行列からポップされる。すなわち、スレッドは、作動可能状態からポップ状態に遷移する図41参照。この仮想ポップは、最も適格なスレッドをロックし、それをポップ状態とマークし、再スケジューリングのためにTSSMにフラグでイベントを知らせることによって明示される。一定の状況下で、ディスパッチ待ち行列イベントは結果として割り込みを生じる。再取り込みされた優先使用インデックスが有効なスレッド記述子インデックスを含み、割り込みが使用可能にされている場合、このディスパッチ待ち行列に関連付けられたシステムプロセッサへの割り込みは、先の割り込み表明フラグが使用可能にされており、次の優先使用インデックスがスレッドであって、すでにTSSMによってアサートされている場合を除いて、あらゆる状況下でアサートされる。また、ディスパッチ待ち行列メトリックも更新される。ディスパッチ待ち行列メトリックは現在実行中のスレッドの適格性を表すが、ディスパッチ待ち行列は、割り込みされており、またはディスパッチ待ち行列ポップが行われている。したがって、実行スレッドは、割り込みされようとしておりその場合、メトリックの更新は、最悪の場合、少々時期尚早である、または新しいスレッドが実行中で、ディスパッチ待ち行列メトリックがいずれにしても上書きされることになる。既存の次の優先使用インデックスを不当に使用している再スケジュールが発生している場合、既存の優先使用インデックスは、事実上、作動可能待ち行列構造にフラッシュバックされなければならない図41参照。TSOM内では、スレッドは、単に、フラッシュされたとマークされるだけであり、処理のためにTSSM作業待ち行列にプッシュバックされる。適格なスレッドが見つからない場合、操作は、単に、完了し、クライアント処理リソースは、これらの状況下ではアイドル状態になる。ディスパッチ待ち行列適格性メトリックの設定ディスパッチ待ち行列適格性メトリックは、ProcElementIDで索引付けされる処理リソースインスタンス上で現在実行中のタスクの実行優先度を反映する。しかしながら、いくつかの最適化の下では、ディスパッチ待ち行列適格性メトリックは、実行開始寸前のタスクの実行優先度を反映してもよい。ディスパッチ待ち行列優先度メトリックは、優先使用を制御するのに使用され、以下のような様々な理由で操作される。-新しいタスクの開始-現在のタスクの完了-優先度逆転-電源管理いずれの場合にも、その目的は、作動可能待ち行列のスケジューリングの操作を調整することである。更新の結果としてプールルートノードの変更を生じる場合、そのノードは、再スケジュール操作のためにTSSMにフラグで通知される。プール参加ノードおよび非プール参加ノード内のメトリック伝搬の詳細については、上記を参照されたい。最適化として、処理リソースインスタンスが現在実行中のスレッドを、SystemWeaver内の作動可能またはブロック状態にプッシュバックするときに、実行優先度は、自動的に、デフォルトメトリックにリセットされる。メソッドインターフェースディスパッチ待ち行列リンクリスト上での基本状況操作取得および設定状況と共に、出力マネージャは、そのインターフェース上で以下のコマンドを提示する。自動化実行メトリック更新C_TSOM_CMD_SERVICE_TIME_SLICE_EXPIRE呼び出し元:TSIFこのコマンドは、識別されたプロセッサIDのために、ディスパッチ待ち行列内に保持されるメトリックのメトリック0の最下位ビットを自動的に変更する。引数は、ディスパッチ待ち行列記述子自体ではなく、プロセッサの識別情報であるため、このコマンドは、最初に、ディスパッチ待ち行列記述子リストをウォークして適切な記述子を見つける。変更は、最下位ビットの単なる反転であり、メトリックフィールドの予約部分が適切に設定されると仮定すると、これは、優先度が昇順であるにせよ、降順であるにせよ、実行スレッドの優先度を下げる効果を有する。引数を以下に示す。ディスパッチ待ち行列メトリック設定呼び出し元:TSIF明示的システム呼び出しからこのコマンドは、個々のディスパッチ待ち行列の実行メトリックを設定する。このコマンド構造には以下の引数がある。デフォルトディスパッチ待ち行列メトリック設定呼び出し元:TSIFこのコマンドは、個々のディスパッチ待ち行列の実行メトリック0を、やはりディスパッチ待ち行列内に保持されるデフォルト値にリセットする。この関数には引数はない。ディスパッチ待ち行列イベントC_SCHED_ENTRY_DISPATCH_LiST呼び出し元:TSSMこのコマンドは、作動可能待ち行列の状態変更によって必要とされたときに、ディスパッチ待ち行列記述子を更新させる。[TSSMスケジュールマネージャ]スケジュールマネージャは、作動可能待ち行列構造の親子リンケージに固有のスケジューリング決定を助ける。アーキテクチャTSSMには、もっぱらその作業待ち行列インターフェースからコマンドが供給され、純粋に、イベント駆動型である。しかしながら、一定の挙動がいくつかのコマンドに共通であり、以下でこの挙動を説明する。再スケジュール再スケジュール関数は、スケジューリング階層内の定義された点からスケジューリング決定を再評価する。再スケジュール操作は処理保存的であり、その状態がおそらくイベントによって影響を受けるはずの階層の部分に関連付けられる処理を上回る追加処理は行われない。UpdateRequiredという、再スケジュール関数への1つの特に興味深い引数がある。UpdateRequiredは、スケジューラ層操作間で更新状況を伝搬するのに使用される。例えば、他の状態は依然として管理されなければならないが、子層内の決定を更新しなかったポップ操作は、親層内の全スケジューリング反復を行わせる必要がない。この場合、UpdateRequiredは偽になるはずである。図60に、再スケジュール操作の基本的流れを示す。層内スケジューラは、層内スケジューリングを実行し、結果として層親先頭インデックスポインタの更新をもたらす。層間スケジューラは、ディスパッチノードに向かってスケジューリング階層内の連続する層をスケーリングする。層間スケジュール関数は、親インデックスを用いて呼び出され、それによって、階層のレベルを即座にスケーリングすることに留意されたい。プール層間スケジュールは、特殊なスケジューリングアルゴリズムであり、単一のノード、プールノードから多数のノード、プール静的ノードに展開する唯一のアルゴリズムである。この項の残りの部分では、スケジューリングアルゴリズムの操作を説明する。層内スケジューラ最も基礎的なスケジューリング操作は、スケジューリング層内の要素のリンクリストをトラバースしてどれが最も適格であるか識別し、親の先頭ポインタをしかるべく更新することである。適切な記述子が空のスケジューリング層にプッシュされる単純な場合には、親の先頭ポインタおよび要素数は無条件で更新され、メトリックは、メトリック伝搬演算子に従って新しい子から親に条件付きで伝搬される。図61に、プッシュ操作でのより一般的な場合を示す。現在の選択および候補選択の妥当性は、以下のいくつかの要因の組み合わせである。-選択は、スケジュールされ得る内容を持たねばならない。スレッドでは、これは常に真であるが、スケジューラでは、これはその下位階層の内容に依存する。-記述子がスケジューラである場合、それは、休止状態であってはならず、その無効線活動状態フラグが設定されてもならない。-記述子が標準スレッドである場合、それは、ロックされてはならず、作業待ち行列内にあってもならない。-記述子がマーカスレッドである場合、親の合計依存関係カウントはゼロでなければならず、マーカスレッドは、層内に残る唯一のエントリでなければならない。候補は、現在の選択、すなわち前のスケジューリング操作からの最も適格な記述子とだけ比較されることに留意されたい。候補がその勝者に勝った場合、それは新しい勝者にならなければならない。対スケジュールは、前述の、親スケジューリング層内に保持されるアルゴリズムに関連する。親更新変数は、この操作の結果としてこの層の親も更新されるべきであるという、呼び出し元へ返される命令を保持する。再スケジュールの一般的な場合、例えば、メトリックが更新されている場合や、ポップが発生している場合には、最も適格な候補を見つけるために全層が再評価されねばならない。このプロセスは、図62に示すように、全層が再評価されるまで、図61の操作を複数回実行する。層間スケジュール層間スケジュールは、1スケジューラ層当たり1回実行され、これは、1スケジューリングイベント当たりでは数回になり得る。層間スケジューリングは、親の種類に大きく依存する。要約すると、層間スケジューリングは、親がディスパッチ待ち行列になるまで、層内スケジューリングを呼び出し続ける。これには1つの例外があり、それは、プール配布ノードに遭遇した場合である。図63に、層間スケジューリングの基本的流れを示す。ディスパッチ待ち行列記述子DQD親およびプールルートノードPRNと関連付けられた固有の挙動がある。しかしながら、層間スケジューラが、単に、現在の子インデックスを、現在の親で置換しそれによって、スケジューリング階層を反復し、それ自体を再呼び出しするだけの場合もある。図64に、層間スケジューリングルーチンにおけるディスパッチ待ち行列処理を示す。まず、ディスパッチ待ち行列記述子DQD内に含まれる実行メトリックが、DQDで定義されるアルゴリズムに従って、スケジューラルートノード内に保持されるメトリックに対してスケジュールされる。この操作で、優先使用が必要とされると決定された場合、再スケジュール操作を開始したイベントの種類に従ってDQDの次の優先使用インデックスへの更新が行われる。このイベントがスレッドプッシュであった場合、スケジュールされたスレッドインデックスが次の優先使用インデックスフィールドに直接配置され、そうでなかった場合、スケジューラルートノードインデックスが使用される。次いで、TSOM上で、スケジューリング階層を反復してスレッド記述子を見つける。プール層間スケジューリングプール層間スケジューリングは、もしあれば、関連付けられた処理リソースインスタンスのうちのどれが、現在のプール内に保持されるスレッド記述子を処理するのに選択されるべきか識別するのに使用される。その意味で、これは、固有の方法で動作する。なぜなら、本明細書で説明する他のすべてのスケジューリングアルゴリズムと異なり、通常、プール層間スケジューリングは、最も適格性の低い候補を求めようとするからである。図66に、図65に図示する、プール層間スケジューリング操作の流れを示す。初期の層内スケジューリング操作は、プール配布層内のプール静的ノード内に保持されるメトリックによって指示されるように、スケジューリング階層からの候補が実行タスクのいずれかより適格であるかどうか判定する。更新が必要とされるかどうかの指示と、更新が適用されなければならないノードの識別という2つの結果がある。次いで、アルゴリズムは、プールルートノードの適切な次のポインタによって指示されるプール静的ノードから、全プール配布層の周りで反復し始める。反復の都度、ハウスキーピング機能スレッドカウンタや他の状態の維持などを助けると共に、層間スケジューリングがプール接続層上で呼び出される。通常はそうであるように、層間スケジューリングは、ディスパッチノードに到達するまで、全スケジューリング階層を上へ伝搬し続ける。層間スケジューリングは、さらなるスケジューリング層が、更新必要というスケジューリング決定を完全に再評価すべきかどうか指示する引数を取る。このフラグは、プール間スケジューリングのコンテキストにおいて、以下の2つの状況下で設定される。-現在処理されているプール静的ノードが、プール内スケジューリングによって、プールルートノードの下で最も適格なスレッドを処理するのに最も適格なノードであると識別されたノードである。-プールルートノードの下の階層に、適格なスケジューリング候補がない。プール層内スケジューリング図67に、プール層内スケジューリングの流れを示す。第1の例には、プッシュのみの操作でのスケジューリング時間を短縮する最適化がある。これは、利用可能になる新しいタスクへのシステムの応答性を向上させる。これが排他的プッシュ操作ではないと仮定すると、スケジューリング操作は、現在の選択および候補選択を、プール内の最初の2つのPSNノードに設定する。次いで、アルゴリズムは、全プール配布層の周りのループに入る。反復の都度、現在の選択が候補に対してスケジュールされる。プール配布層には、他のスケジューリング層と同じスケジューリングアルゴリズムが使用されるが、選択される個別アルゴリズムは異なる可能性が高いことに留意されたい。なぜなら、このシナリオでは、正しい選択が、通常の標準による最も適格性の低いメトリックを示すことになるからである。候補が現在の選択を統括する場合、現在の選択が候補に更新され、候補が層内の次のエントリに更新され、処理は、候補がPRNになるまで続く。排他的プッシュ操作では、この反復が回避される。現在の選択待ち行列および更新ノードは、単に、現在のスケジューリング選択を定義するPRNの親に設定され、候補は、PRN自体である。いずれの場合にも、次いで、プールルートノードにスケジュール可能な内容があるかどうかチェックされ、何もない場合、更新なし状況が設定され、アルゴリズムが戻る。しかしながら、スケジュール可能な内容がある場合、プロセスは、第2段階に進み、排他プッシュ操作におけるPRNからの既存の選択または他の場合の反復の結果が、PRN自体に対してスケジュールされる。PRNがこの競争に勝った場合には、更新が必要とされ、そうでない場合には、不要とされる。例図68に、スレッド記述子ノード5の静的スケジューリング要素ノード3へのプッシュに関連付けられるTSSMスケジューラ処理を示す。最初の層内スケジューリング操作は、再スケジュール関数のコンテキスト内で行われ、親ノード3に関するものである。次いで、再スケジュールは、階層の上位層へ移動し、親ノード2との層間スケジューリングを呼び出す。この直後の反復は親ノード1を見つけ、これはDQDである。したがって、層内スケジューラへのそれ以上の呼び出しはなく、スケジューリング比較が、ルートノード内に格納される最も適格な候補のメトリックと、ディスパッチノード内に格納される実行スレッドの間で行われる。この場合、優先使用が適切であり、ディスパッチ待ち行列イベントがTSOMに伝達される。図69に、より階層化されたスケジューリング階層を示す。この場合、階層の別の層ために層内スケジューリング関数へのさらなる呼び出しが行われる。ただし、再スケジュール操作を引き起こしたスケジューリングイベントはその範囲外であるため、スケジューリング層5および3は影響を受けないことに留意されたい。図70に、このプールスケジューリング操作の場合の第3の例を示す。前述のように、そこへのスレッドプッシュイベントが発生する層は層内スケジューリング操作の対象とされ、この例では、新しいスレッドは、プールルート層内で最も適格なものである。次いで、プール層間スケジューラが、プール層内スケジューラへの呼び出しを行って、システム処理リソースのいずれかが新しく到着したスレッドに取って代わられるべきかどうか判定する。この場合、プール層内スケジューリングの結果は、WMEインデックス7のところのディスパッチ待ち行列記述子に関連付けられた処理リソースインスタンスが取って代わられるべきであるというものである。次いで、プール層間スケジューラは、プール配布層の周りで反復し、まず、ノード4上で層間スケジュールを呼び出す。次に、層間スケジュールが層内スケジュールを呼び出してスケジューラ層1を更新するが、網羅的なスケジューリングは必要とされない。なぜなら、これは取って代わられた層ではなく、処理は状態情報の維持に限定され、したがって、TSOMへのディスパッチ待ち行列イベントも、システム処理リソースへの割り込みもないからである。次の呼び出しは、層2上の層間スケジューリングである。この場合、層は、新しくプッシュされたスレッド記述子が他のどんな候補よりも適格であるかどうか明示するように適正にスケジュールされる。候補メトリックは、最終的には、優先使用が適切であるかどうか判定するために、ディスパッチ待ち行列記述子内に格納された実行スレッドのメトリックと比較される。この例では、メトリック、したがって、ディスパッチ待ち行列イベントがTSOMに送られ、システム処理リソースインスタンス割り込みにフラグが立てられる。この場合もやはり、プッシュスレッドイベントの範囲の影響を受けるスケジューリング層だけが再評価される。メソッドインターフェースTSSMは、もっぱら、作業待ち行列を介してのみ宛先指定される。スレッド記述子イベントサービス呼び出し元:TSIF、TSPM、TSOMこのコマンドの挙動は、以下のように、受け取られたスレッドのフラグ内の設定に依存する。-プッシュまたはフラッシュフラグが設定されている場合、親の合計スレッド要素カウントを増加させる。ポップフラグが設定されている場合、親の合計スレッド要素カウントを減少させる上記の組み合わせの最終結果はヌルとなり得ることに留意されたい。-次いで、プッシュフラグが設定されたスレッドが作動可能待ち行列階層にリンクされる。それらのスレッドがブロック状態から遷移している場合、従属スレッドの親のカウントも減らされる。-マーカスレッドだけに限定される唯一の挙動が、親のロック解除であるスケジューラ層の保留空き状態への遷移。図4参照。-TSSMは、このコマンドを処理するときに、ゾンビ状態で受け取られた任意のスレッド記述子が解放されるよう要求する。このコマンドは、常に、再スケジュールを必要とする。再スケジュールプール配布層呼び出し元:TSOMこのコマンドは、実行スレッドのメトリックの変更の結果として呼び出される。ディスパッチ記述子がプールに関与する場合、これらのメトリックは、配布階層を介して伝搬され、最終的に、この関数を呼び出してスケジューリング決定を再評価する。スケジューラ層の再スケジュールまたは削除呼び出し元:TSOMこのコマンドは、以下の2つの理由でTSOMによって呼び出される。-ディスパッチ記述子がプールに関与しない場合の、実行スレッドのメトリックの変更の結果として、優先使用が適切であるかどうか再評価するため。この操作は、スケジューリングルートノードを通過する。スケジューリング層がその階層にスレッド記述子を含む場合、再スケジュールが要求される。-TSOMが、そうするのが妥当であると決定している場合に、スケジューリング層を削除するため。この決定は、ロックされたフラグ、従属スレッドカウントおよび子要素の数それぞれ、偽、0、0に基づくものである。記述子の実際の解放は、TSIMへの要求として現れる。独立要素のプッシュ呼び出し元:TSIFこのコマンドは、初期設定時に、静的スケジューリング層をスケジューリング階層にプッシュするのに使用されてもよく、実行時にスレッド記述子または動的スケジューリング階層を動的に追加するのに使用されてもよい。スレッドメトリックの更新呼び出し元:TSIF作動可能待ち行列階層内のスレッド記述子のメトリックを更新する。メトリックは、スレッド記述子が作動可能状態にあるときにだけ更新されてもよい図41。このコマンドは再スケジュールを発生させる。スケジューラ状態の更新呼び出し元:TSIFこのコマンドは、スケジューラアルゴリズム、メトリックおよびメトリック伝搬アルゴリズムの更新を可能にする。このコマンドは再スケジュールを発生させる。スケジューラ層の活動化呼び出し元:TSIFこのコマンドは、休止スケジューラ層を活動化する。このコマンドは再スケジュールを発生させる。スケジューラ層の非活動化呼び出し元:TSIFこのコマンドは、休止スケジューラ層を非活動化する。[TSMMメモリマネージャ]メモリマネージャ図71は、TCMへのアクセスを集約するための挙動の多重化/逆多重化を提供する。また、複数のサブブロック間で共用されるリソースの保全性を保証するロッキング機能も提供する。アーキテクチャアーキテクチャ上の観点から見ると、メモリマネージャは、主に、6つの可能な要求元の間でTCMへのアクセスを集約するマルチプレクサ/デマルチプレクサとみなすことができる。また、ロックキャッシュを実装することによって、複数のサブブロックが同じリソースへのアクセスを試みようとする場合の、WMEの保全性も維持する。アクセス集約アクセス集約は、スケジューラの制御下にある。このスケジューラは、以下のように、非対称である。-TSIFは最高の優先度を有する-TSOMは次に高い優先度を有する-残りすべての要求元は、等しい優先度を有し、処理保存的ラウンドロビンで扱われる。ロックキャッシング各ブロックは、1から4ロックの間の割り振りを有する。これらの数は、サブブロック要求元が排他的にアクセスすることのできるWMEの数を表す。ロックされたリソースを要求するサブブロックは、そのリソースが利用可能になるまでブロックされる。同じリソース上で回転する複数のブロック間の競合は、優先度によって解決される。[スケジューリングシーケンス図][プッシュイベント]図72のシーケンス図に、プッシュイベントに続くサブブロック間対話を示す。TSSMおよびTSOMは、自ずと、シングルスレッドであるため、コマンドを格納するために作業待ち行列が導入されていることに留意されたい。代表的なスケジューリング階層については、図68を参照されたい。プッシュイベント前の状態は、スレッド4がディスパッチ待ち行列記述子1内の現在の優先使用インデックスであるというものである。第1の再スケジュールは、スレッド5が、スレッド4より適格であると識別し、結果として、ディスパッチ待ち行列記述子1がTSOM作業待ち行列にプッシュされる。TSOM作業待ち行列内のディスパッチ待ち行列記述子が、TSOM内のディスパッチ待ち行列イベントを発生させる。このイベントは、事実上、スレッド記述子5をポップし、ディスパッチ待ち行列メトリックをしかるべく設定する。このポップ操作は、作動可能待ち行列内の状態の変更を生じ、したがって、再スケジュールが呼び出されなければならない。これは、ポップフラグを設定してスレッド5をTSSM作業待ち行列にプッシュすることによって達成される。スレッド4は、事実上以前にポップされているため、今や、作動可能待ち行列構造にフラッシュバックされる必要がある。これもやはり、作動可能待ち行列構造内の状態変更を構成し、したがって、別の再スケジュールが必要とされる。これは、フラッシュフラグを設定してスレッド4をTSSM作動可能待ち行列構造にプッシュすることによって達成される。事実上ポップされたスレッドおよびフラッシュされたスレッドは、大部分が作動可能待ち行列階層の異なる部分に存在し得るため、第2および第3の再スケジュール操作をマージすることはできないことに留意されたい。[ポップイベント]図73のシーケンス図に、仮想ディスパッチ待ち行列からスレッド記述子がポップされるときの、TSIFとTSOMとTSSMの間の対話を示す。ポップコマンド自体は、コマンドインターフェース、またはシステム相互接続を介してTSIFによって受け取られる。TSIFは、ポップフラグを設定してディスパッチ待ち行列記述子をTSOM作業待ち行列上にプッシュすることによって、ディスパッチ待ち行列ポップコマンドを発行する。TSOM作業待ち行列内のディスパッチ待ち行列記述子は、TSOM内のディスパッチ待ち行列イベントを発生させる。ディスパッチ待ち行列イベントハンドラは、TSSMに、ポップされたばかりのスレッド記述子、この場合はスレッド5をフリーリスト上に戻すよう要求するように指示する。次いで、実行するのに次に最も適格な候補を格納する次の優先使用インデックスが、事実上、TSOMによってポップされる。これは、作動可能待ち行列構造での状態変更を表し、したがって、TSSMは、TSOMによって再スケジュールするよう命令され、ポップフラグを設定して次の優先使用スレッドが、TSSM作業待ち行列にプッシュされる。