(57)【特許請求の範囲】
【請求項１】
複数のプロセッサ要素を有するマルチコアプロセッサにおいて実行可能トランザクションをスケジュールする方法であって、前記マルチコアプロセッサ内の少なくとも１つのプロセッサ要素が、実行時に再構成可能である再構成可能論理を含み、
再構成可能論理の構成ごとに、実行可能な状態の実行可能トランザクションをリストし、前記再構成可能なプロセッサ要素の個々の構成に割り振られる実行可能トランザクションの構成待ち行列を設けるステップであって、コストメトリックが、各構成待ち行列に対して当該構成待ち行列の実行可能トランザクションに基づいて定義されている、ステップと、
現在選択されている前記構成と関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、
現在選択されている前記構成の前記コストメトリックと他の構成の前記コストメトリックとの差が事前定義された閾値に達したときに、現在選択されている前記構成を切り換えるステップと、を備える方法。
【請求項２】
実行の適格性の順に実行可能トランザクションをリストする配布待ち行列を設けるステップと、
それぞれが、実行可能な状態のいくつかの候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを決定するスケジューリングアルゴリズムを含む複数の個別実行可能トランザクションスケジューラを設けるステップと、
前記複数の個別実行可能トランザクションスケジューラを、多重レベルスケジューラを提供するように相互にリンクするステップと、
前記多重レベルスケジューラから前記配布待ち行列に最も適格な実行可能トランザクションを出力するステップと、
前記プロセッサ要素ごとのディスパッチ待ち行列であって、前記実行可能トランザクションを当該プロセッサ要素上での実行の順にリストする当該ディスパッチ待ち行列、を複数設けるステップと、
１つ以上の前記ディスパッチ待ち行列に前記配布待ち行列を関連付けるステップと、
前記配布待ち行列の内容を、当該配布待ち行列に関連付けられたディスパッチ待ち行列に出力するステップと、
をさらに備える、請求項１に記載の方法。
【請求項３】
前記構成を切り換えるステップが、さらに、
現在選択されている前記構成と関連付けられた前記構成待ち行列の内容の出力を停止するステップと、
利用可能な前記構成の別の１つを選択し、前記再構成可能論理の前記構成を、前記選択された利用可能な前記構成の別の１つに変更するステップと、
前記新しく選択された構成に関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、をさらに備える、請求項２に記載の方法。
【請求項４】
前記再構成可能論理がメモリである、請求項２または３に記載の方法。
【請求項５】
各構成待ち行列の前記コストメトリックが、前記アプリケーションの保全性を維持するために個々の実行可能トランザクションが実行されねばならなくなるまでの最大許容時間に基づいている、請求項２〜４のいずれか一項に記載の方法。
【請求項６】
各構成待ち行列の前記コストメトリックが、前記構成待ち行列のそれぞれの長さに基づいている、請求項３に記載の方法。
【請求項７】
各構成待ち行列の前記コストメトリックと前記事前定義された閾値とが、最も長い構成待ち行列に関連付けられた前記構成が選択されるように定義されている、請求項６に記載の方法。
【請求項８】
コンピュータに請求項１〜７のいずれか一項に記載の方法を実行させる命令を備えるコンピュータプログラム。
【請求項９】
コンピュータによって実行されると、請求項１〜７のいずれか一項に記載の方法を実行する命令を含むコンピュータ可読媒体。
【請求項１０】
複数のプロセッサ要素を有し、当該マルチコアプロセッサ内の少なくとも１つのプロセッサ要素が、実行時に再構成可能である再構成可能論理を含むマルチコアプロセッサであって、コストメトリックが、各構成待ち行列に対して当該構成待ち行列の実行可能トランザクションに基づいて定義されている、マルチコアプロセッサと、
再構成可能論理の構成ごとに、実行可能な状態の実行可能トランザクションをリストするように設けられ、前記再構成可能なプロセッサ要素の個々の構成に割り振られる実行可能トランザクションの構成待ち行列であって、現在選択されている前記構成と関連付けられた当該構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するように構成された前記構成待ち行列と、
現在選択されている前記構成の前記コストメトリックと他の構成の前記コストメトリックとの差が事前定義された閾値に達したときに、現在選択されている前記構成を切り換えるコントローラと、
を備えるマルチコアプロセッサ。
【請求項１１】
実行の適格性の順に実行可能トランザクションをリストする配布待ち行列と、
それぞれが、実行可能な状態のいくつかの候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを決定するスケジューリングアルゴリズムを含む複数の個別実行可能トランザクションスケジューラと、
前記プロセッサ要素ごとのディスパッチ待ち行列であって、前記実行可能トランザクションを当該プロセッサ要素上での実行の順にリストする複数の当該ディスパッチ待ち行列と、
をさらに備え、
前記複数の個別実行可能トランザクションスケジューラは、多重レベルスケジューラを提供するように相互にリンクされ、
前記多重レベルスケジューラは、前記配布待ち行列に最も適格な実行可能トランザクションを出力し、
１つ以上の前記ディスパッチ待ち行列は、前記配布待ち行列が関連付けられ、
前記配布待ち行列の内容が、当該配布待ち行列に関連付けられたディスパッチ待ち行列に出力される、請求項１０に記載のマルチコアプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコアアーキテクチャにおいてスレッドをスケジュールする方法および装置に関する。
【０００２】
近年、シリコン効率（すなわち、「アプリケーション利用可能」ＭＩＰＳ／ｍｍ２またはＭＩＰＳ／ｍＷ）を最大にするために、複数のコアを含むプロセッサの生産へと向かう傾向がある。このようなマルチコアアーキテクチャは、スレッドに基づいてアプリケーションを実行するのに適しているのが理想的である。なぜなら、スレッドは、定義上、他のスレッドと並行して実行し得る実行状態、命令ストリームおよびデータセットを含む自律的作業パッケージを定義するものだからである。
【０００３】
スケジューリングとは、実行に最適なスレッド（すなわち命令セット）の発見および個々の処理リソースへの割り振りの一般的な用語であり、アプリケーションプログラムと、アプリケーションプログラムがそこで実行される基礎ハードウェアプラットフォームの両方によって必要とされる。
【０００４】
マルチコアアーキテクチャ内での実行の並行性は、個々のスレッドを実行するのに適した複数のコアが利用できる可能性と組み合わさって、これらのマルチコアアーキテクチャ内でスレッドを割り振るのに使用されるスケジューリングにさらなる問題を発生させる。
【発明の概要】
【０００５】
本発明の第１の態様によれば、請求項１に記載されるマルチコアプロセッサ内で、往々にしてスレッドと呼ばれる実行可能トランザクションをスケジュールする方法が提供される。
【０００６】
多重レベルの、より好ましくは、階層的なスケジューリングシステムを提供することにより、本発明は、１つ以上のより単純なスケジューリングアルゴリズムからの、複雑なスケジューリングアルゴリズムの構築を可能とする。このような複雑なスケジューリングアルゴリズムを使用することができれば、複数のスレッドを備えるアプリケーションの実行時の性能が向上する。本発明は、実行可能トランザクション、すなわちスレッドを処理リソースにより効率よく割り振ることによってアプリケーションの実行時性能を向上させる。これは、実行速度を高め、いくつかのリソース上でのボトルネックを低減することができる。また、マルチコアプロセッサの通常はあまり活動的でない部分の使用頻度も高めることができる。
【０００７】
好ましい実施形態において、本方法は、専用のハードコーディングされた、したがって効率のよい実施形態によって実行される。好ましいハードコーディング実施形態は、マルチコアプロセッサ内に、システムサーバ（以後ＳｙｓｔｅｍＷｅａｖｅｒという）と、処理リソース、すなわちコアごとのクライアントとを備える、サーバ／クライアントトポロジのものである。他の実施形態では、当該の処理リソースの能力が許せば、単一のクライアントが複数の処理リソースへのアクセスを集約してもよい。
【０００８】
本発明を組み込んだシステム全体の性能をさらに向上させるために、好ましい実施形態は、専用メモリ内のポインタを使って、割り振りをスケジューリングしたり、決定のための値を格納したりする。これらのポインタは、好ましくは、スケジューリング決定がそれに関して行われるパラメータを格納するフィールドを含み、好ましくは、その後の決定に使用するための値を格納し、または単に、他の対象となる値を格納するためのさらなるフィールドも含む。以下では、上記のフィールドをメトリックまたは演算子と総称する。
【０００９】
本発明の第２の態様によれば、複数のプロセッサ要素を有するマルチコアプロセッサ内でアプリケーションを定義する実行可能トランザクションをスケジュールする方法であって、実行可能トランザクションスケジューラの階層を維持するステップを備え、階層は、使用時のアプリケーションの要件に従って実行可能トランザクションをスケジュールするように適合され、上記スケジューラ階層の各レベルは、少なくとも１つのスケジューラを備え、少なくとも１つのスケジューラは、上記実行可能トランザクションを、プロセッサ要素の１つ以上で実行するのに最も適格なトランザクションの順にソートするための少なくとも１つの規則を備える方法が提供される。
【００１０】
本発明の第３の態様によれば、請求項３７に記載されるマルチコアプロセッサにおいて電力消費を管理する方法が提供される。
【００１１】
マルチコアプロセッサが、それぞれが個々のスレッドを実行することのできる複数の処理リソースを有する場合、本発明は、これら複数の処理リソースがまとめてプールに配置されるようにする。その場合、スレッドが割り振られるのはこの処理リソースのプールである。しかしながら、このような状況では、実行を必要とするスレッドの数がプールの実行能力を超えないとき、すなわち、そのプール内の処理リソースの一部が利用されているか、そうではなく全く利用されていないときに、本発明は、処理リソースのそれぞれを節電モードにすることができる。処理リソースは、複数の異なるレベルの節電機能を有することさえ可能である。
【００１２】
好ましくは、処理リソースは、スレッド実行負荷が必要とするときには、節電モードから除かれ、または少なくとも、それに関連付けられた全出力モードへの復帰のコストがより低い、より緩やかな節電モードに移行される。
【００１３】
本発明の第４の態様によれば、請求項３８に記載される、再構成可能論理を含む少なくとも１つのプロセッサ要素を有するマルチコアプロセッサ内で実行可能トランザクション、すなわちスレッドをスケジュールする方法が提供される。
【００１４】
プロセッサ要素の１つ以上が再構成可能論理部分を有する場合、例えば、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）の再構成可能実行部分などの場合、本発明は、論理の同じ構成を利用するスレッドをまとめて集約することによって性能を向上させることができる。これは、再構成可能論理部分が再構成されるときの、コンテキスト切換えの必要を減らし、またはその影響を緩和するのに役立つ。
【００１５】
また、本発明は、再構成可能な論理の場合に、当該のプロセッサ要素上での次に実行可能な状態の命令を格納するローカルキャッシュメモリの形で性能を向上させることもできる。
【００１６】
これは、実行のために、キャッシュされたメモリの同じ領域を使用するスレッドを集約することによって、ローカルキャッシュミス、またはローカルキャッシュフラッシュの影響を最小限に抑えることができるからである。
【００１７】
本発明の第５の態様によれば、ディジタル論理によって実行されると、請求項１に記載の方法を実行するコンピュータプログラムが提供される。また、上記コンピュータプログラムを含むコンピュータ可読媒体も提供される。
【００１８】
プロセッサ要素、処理リソース、コア、およびプロセッサは、本明細書における説明の教示を利用するときには、等価であると解釈されるべきである。
【００１９】
プロセッサ要素の使用状況は、その現在の作業負荷に相当し得る。
【００２０】
その他の有利な特徴は、付記される従属請求項で定義される。
【００２１】
本発明のさらなる態様によれば、複数のプロセッサ要素と、実行適格性の順に実行可能トランザクションをリストする少なくとも１つの配布待ち行列と、それぞれが、いくつかの実行可能な状態の候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを決定するスケジューリングアルゴリズムを含む、複数の個別実行可能トランザクションスケジューラを備える多重レベルスケジューラとを備えるマルチコアプロセッサが提供され、各スケジューラは相互にリンクされ、多重レベルスケジューラは、その中から、少なくとも１つの配布待ち行列に、最も適格な実行可能トランザクションを出力するように構成される。
【００２２】
実行可能トランザクションは、複数の状態から選択され得るスレッド記述子を備えていてもよい。スレッド記述子は、状態遷移構成に従って、それら複数の状態からの各状態間で変更されてもよく、それによって、実行可能トランザクションが、複数の実行可能トランザクション間で、低いスケジューリング待ち時間およびスケジューリング階層の保全性を実現するよう管理され得るように、実行可能トランザクションを識別してもよい。スケジューラは、スレッド記述子を識別することができる。スケジューラは、複数のスケジューリング状態の中から選択されたスケジューラ状態を備えていてもよい。スケジューラ状態は、動的スケジューリング階層をサポートするように制御され、スケジューリング階層は、システムの通常動作時に、その階層内でスケジュールされた項目の順序および保全性を維持したままで、調整されてもよい。
【００２３】
マルチコアプロセッサは、ウォッチドッグタイムアウトを提供するように構成され得るハードウェアタイミングリソースをさらに備えていてもよく、ウォッチドッグタイムアウトは、処理リソースインスタンスが動作不能状態に入っていることを示す。ハードウェアタイミングリソースは、代替として、処理リソースインスタンス、または処理リソースインスタンスのグループが、複数の同等に適格な実行可能トランザクションの間で公平に共用されていることを示すタイムスライスタイムアウトを提供してもよい。公平な共用は、平等な時間割り当て、または実行可能トランザクションの要件に応じた時間割り当てを提供することを含んでいてもよい。ハードウェアタイミングリソースは、ウォッチドッグタイムアウトを提供するように構成される第１のモードと、タイムスライスタイムアウトを提供するように構成される第２のモードの間で切り換わるように構成されてもよい。ハードウェアタイミングリソースは、好ましくは、タイムスライスタイムアウトが提供された後で第１のモードに切り換わるように構成される。
【００２４】
マルチコアプロセッサの保留マネージャは、それぞれがタイマ待ち行列要素を受け取るように構成されているタイマ待ち行列をさらに備えていてもよい。タイマ待ち行列は、実行可能トランザクションを含んでいてもよい。タイマ待ち行列内の第１の実行可能トランザクションは、第１の時間パラメータと関連付けられてもよい。第１の時間パラメータは、関連付けられた実行可能トランザクションが実行するのに適格となるべき時刻であるタイムアウト時刻を示す。好ましくは、第１の実行可能トランザクションのタイムアウト時刻は、現在時刻に最も近いものである。第２の実行可能トランザクションは、第２の時間パラメータと関連付けられてもよい。第２の時間パラメータは、第２の実行可能トランザクションのタイムアウト時刻と第１の実行可能トランザクションのタイムアウトの間の差を示す。第３の実行可能トランザクションは、第３の時間パラメータと関連付けられてもよい。第３の時間パラメータは、第３の実行可能トランザクションのタイムアウト時刻と、第２の実行可能トランザクションのタイムアウト時刻の間の差を示す。
【００２５】
待ち行列内の第１の実行可能トランザクションは、時間パラメータと関連付けられてもよい。この時間パラメータは、関連付けられた実行可能トランザクションのタイムアウトと、やはりその待ち行列内の、第２の実行可能トランザクションのタイムアウトの間の時間差を示す。好ましくは、第２の実行可能トランザクションは、第１の実行可能トランザクションのタイムアウトの前に、それに最も近接して発生するタイムアウトを有する、その待ち行列内の実行可能トランザクションである。
【００２６】
マルチコアプロセッサは、複数のディスパッチ待ち行列をさらに備えていてもよい。好ましくは、ディスパッチ待ち行列は、さらなるディスパッチ待ち行列を識別するように構成される。各ディスパッチ待ち行列は、ディスパッチ待ち行列記述子を備えていてもよい。これは、サービス提供される処理リソースインスタンスの数を自由に変えられるようにすると共に、ディスパッチ待ち行列記述子に逐次応答させることも可能にする。ディスパッチ待ち行列は、さらに、優先使用実行可能トランザクションのグループの中から、現在プロセッサ要素を使用している実行可能トランザクションを識別するように構成されてもよい。ディスパッチ待ち行列は、さらに、優先使用実行可能トランザクションのグループの中から、続いてプロセッサ要素を使用する実行可能トランザクションを識別するように構成されてもよい。それによって、ディスパッチ待ち行列は、スケジュールマネージャによって行われた最新のスケジューリング決定のインデックスを保持する。
【００２７】
多重レベルスケジューラを提供する個別実行可能トランザクションスケジューラのリンケージは、各実行可能トランザクションスケジューラが関連付けられたスケジューリング層を有するスケジューリング階層を定義する。実行可能トランザクションスケジューラは、以前に実行可能トランザクションをスケジュールした実行可能トランザクションスケジューラを識別するように構成されてもよい。場合によって、実行可能トランザクションスケジューラは、実行可能トランザクションが、プロセッサ要素と関連付けられた配布待ち行列からのものであるかどうか識別することもできる。実行可能トランザクションスケジューラは、実行可能トランザクションが、優先使用実行可能トランザクションのグループからのものであるかどうか識別することもできる。処理は、スケジューリングイベントが「プッシュ」イベントである場合に最適化されてもよい。実行可能トランザクションが実行可能トランザクションスケジューラによってスケジュールされるときに、実行可能トランザクションスケジューラは、さらに、以前にその実行可能トランザクションをスケジュールした各実行可能トランザクションスケジューラに訂正パラメータを送るように構成されてもよい。訂正パラメータは、スケジューリング決定の伝搬および多重レベルスケジューラ内のカウンタの保全性の維持を可能にする。
【００２８】
また、マルチコアプロセッサシステムを運用する方法であって、クライアントを設けるステップと、クライアントの対話状態を選択するステップとを備える方法も提供され得る。対話状態は、クライアントがその間電力管理モードで動作するように構成され得るアイドル状態と、クライアントがその間ユーザまたは通常モードで実行可能トランザクションを実行するように構成されるユーザ状態とを備えていてもよい。好ましくは、対話状態は、クライアントがその間特権状態で実行可能トランザクションを実行するように構成されるＡＰＩ対話状態を備えていてもよい。場合によって、対話状態は、クライアントがその間実行可能トランザクションのコンテキストを準備するように構成され得るクライアントシム状態を備えていてもよい。好ましくは、本方法はサーバを設けるステップも備え、対話状態は、クライアントとサーバの間で共用される。好ましくは、対話状態を変更させるために帯域外信号が提供されてもよい。サーバは、帯域外信号を提供してもよい。場合によって、実行可能トランザクションが、対話状態を変更させてもよい。
【００２９】
本発明の別の実施形態の一態様によれば、方法が提供される。該方法は、
複数のプロセッサ要素を有するマルチコアプロセッサ内で実行可能トランザクションをスケジュールする方法であって、
実行の適格性の順に実行可能トランザクションをリストする少なくとも１つの配布待ち行列を設けるステップと、
それぞれが、実行可能な状態のいくつかの候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを決定するスケジューリングアルゴリズムを含む複数の個別実行可能トランザクションスケジューラを設けるステップと、
前記スケジューラを、多重レベルスケジューラを提供するように相互にリンクするステップと、
前記多重レベルスケジューラから前記少なくとも１つの配布待ち行列に最も適格な実行可能トランザクションを出力するステップと
を備える方法である。
【００３０】
上記一態様において、前記多重レベルスケジューラが、階層構造を有してもよい。
【００３１】
上記一態様において、前記実行可能トランザクションの一部または全部が合わさってアプリケーションを定義し、
前記アプリケーションの実行時に実行可能トランザクションの実行を開始するステップと、
前記実行時に、新しい個別実行可能トランザクションスケジューラを動的に作成するステップと、
前記新しい個別実行可能トランザクションスケジューラを前記多重レベル階層スケジューラにリンクさせるステップと
をさらに備えてもよい。
【００３２】
上記一態様において、新しい動的に作成された個別実行可能トランザクションスケジューラをリンクさせるステップが、
前記新しい個別実行可能トランザクションスケジューラに１つ以上の実行可能な状態の実行可能トランザクションを割り当てるステップを含んでもよい。
【００３３】
上記一態様において、動的に作成された個別実行可能トランザクションスケジューラによる処理のためにマークされたすべての前記実行可能トランザクションの完了時に前記動的に作成された個別実行可能トランザクションスケジューラをリンク解除するステップと、
前記個別実行可能トランザクションスケジューラを前記多重レベル階層スケジューラから除去するステップと、
をさらに備えてもよい。
【００３４】
上記一態様において、前記候補実行可能トランザクションを前記複数の個別トランザクションスケジューラに提供するための少なくとも１つの保留待ち行列を設けるステップ
をさらに備えてもよい。
【００３５】
上記一態様において、各プロセッサ要素ごとに、前記実行可能トランザクションを前記関連付けられたプロセッサ要素上での実行の順にリストするディスパッチ待ち行列を設けるステップをさらに備えてもよい。
【００３６】
上記一態様において、前記配布待ち行列の１つを複数の個々のプロセッサ要素と関連付け、前記配布待ち行列の内容を前記関連付けられたプロセッサ要素の前記ディスパッチ待ち行列に直接出力するステップをさらに備えてもよい。
【００３７】
上記一態様において、前記配布待ち行列の１つを複数のプロセッサ要素に関連付け、前記配布待ち行列の内容を前記関連付けられたプロセッサ要素の前記ディスパッチ待ち行列の１つ以上に出力することにより、そのディスパッチ待ち行列と関連付けられた前記プロセッサ要素の個々の実行可能トランザクションを実行する適格性に依存するプロセッサ要素プールを設けるステップをさらに備えてもよい。
【００３８】
上記一態様において、前記配布待ち行列の別の１つの内容を、前記プロセッサ要素プールの前記ディスパッチ待ち行列の１つに出力するステップをさらに備えてもよい。
【００３９】
上記一態様において、前記配布待ち行列の別の１つをさらなる複数のプロセッサ要素に関連付け、前記配布待ち行列の内容を前記関連付けられたプロセッサ要素の前記ディスパッチ待ち行列の１つ以上に出力することにより、そのディスパッチ待ち行列と関連付けられた前記プロセッサ要素の個々の実行可能トランザクションを実行する適格性に依存するさらなるプロセッサ要素プールを設けるステップをさらに備えてもよい。
【００４０】
上記一態様において、関連付けられたプロセッサ要素の個々の実行可能トランザクションを実行する前記適格性が、そのプロセッサ要素の使用状況に依存するものであってもよい。
【００４１】
上記一態様において、プロセッサ要素の前記使用状況が、すでに前記ディスパッチ待ち行列内にあるその特定のプロセッサ要素のための実行可能トランザクションの数に依存するものであってもよい。
【００４２】
上記一態様において、関連付けられたプロセッサ要素の個々の実行可能トランザクションを実行する前記適格性が、前記プロセッサ要素の電源状況に依存するものであってもよい。
【００４３】
上記一態様において、前記プロセッサ要素の１つ以上が、複数のプロセッサ要素プール内にあってもよい。
【００４４】
上記一態様において、プロセッサ要素プール間で実行可能トランザクションを移動するステップをさらに備えてもよい。
【００４５】
上記一態様において、前記プロセッサ要素の１つと関連付けられている、実行可能トランザクションの少なくとも１つのタイムスライスグループであって、前記タイムスライスグループ内の各実行可能トランザクションが前記関連付けられたプロセッサ要素上の実行時間の事前定義された部分を有するタイムスライスグループを設けるステップをさらに備えてもよい。
【００４６】
上記一態様において、前記プロセッサ要素プールと関連付けられている、実行可能トランザクションの少なくとも１つのタイムスライスグループであって、前記タイムスライスグループ内の各実行可能トランザクションが前記関連付けられたプロセッサ要素プール上の実行時間の事前定義された部分を有するタイムスライスグループを設けるステップをさらに備えてもよい。
【００４７】
上記一態様において、実行可能トランザクションの各タイムスライスグループごとに、前記実行可能トランザクションのタイムスライスグループのいずれにも優る、前記関連付けられたプロセッサ要素またはプロセッサ要素プール上での実行の優先権を得る実行可能トランザクションの優先使用グループを設けるステップをさらに備えてもよい。
【００４８】
上記一態様において、前記実行可能トランザクションの優先使用グループが前記関連付けられたプロセッサ要素プールからの他の前記プロセッサ要素の少なくとも１つで実行されているときに、前記実行可能トランザクションの少なくとも１つのタイムスライスグループに、前記関連付けられたプロセッサ要素プールからの前記プロセッサ要素の少なくとも１つでの実行時間の事前定義された部分を提供するステップをさらに備えてもよい。
【００４９】
上記一態様において、前記少なくとも１つのタイムスライスグループからの実行可能トランザクションを、関連付けられたプロセッサ要素上で実行させるステップと、
前記実行可能トランザクションを、前記優先使用グループからの実行可能トランザクションに取って代わらせるステップと、
前記優先使用グループからの前記実行可能トランザクションの実行が完了したときに、前記関連付けられたプロセッサ要素上で前記少なくとも１つのタイムスライスグループからの前記実行可能トランザクションの実行を再開するステップと、
をさらに備えてもよい。
【００５０】
上記一態様において、プロセッサ要素プール内の各プロセッサ要素が少なくとも１つの節電モードを有し、
プロセッサ要素プールに割り振られた実行可能トランザクションの数が、前記利用可能なプロセッサ要素のごく一部分が実行可能トランザクションの実行に使用されるような数になったときに、前記プロセッサ要素プール内の前記プロセッサ要素の１つ以上を第１の節電モードにするステップ
をさらに備えてもよい。
【００５１】
上記一態様において、前記プロセッサ要素プール内の各プロセッサ要素が少なくとも２つの節電モードを有し、
事前定義された期間の後、プロセッサ要素プール内の前記プロセッサ要素の１つ以上を、前記第１の節電モードより多くのエネルギーを節約する第２の節電モードにするステップをさらに備えてもよい。
【００５２】
上記一態様において、前記プロセッサ要素プール内の前記プロセッサ要素には、事前定義された順序で割り振られ、前記プロセッサ要素プール内のプロセッサ要素に実行可能トランザクションを割り振るのに使用される前記スケジューリングアルゴリズムが、常に、実行可能トランザクションを、前記事前定義された順序で最初の利用可能なプロセッサ要素に割り振ってもよい。
【００５３】
上記一態様において、前記プロセッサ要素プールに割り振られた実行可能トランザクション数の増加に応答して、現在節電モードにある前記プロセッサ要素プール内の前記プロセッサ要素の１つ以上を通常の電力モードに戻すステップをさらに備えてもよい。
【００５４】
上記一態様において、前記少なくとも１つの節電モードが、前記プロセッサ要素が実行する実行可能トランザクションの最低実行優先度を上げることによって開始されてもよい。
【００５５】
上記一態様において、前記実行可能トランザクションおよびマルチコアプロセッサの少なくとも１つでの変更を識別するステップと、
前記識別された変更の結果として、個別実行可能トランザクションスケジューラのために、実行可能な状態の前記いくつかの候補実行可能トランザクションの中から実行するのに最も適格な実行可能トランザクションを再決定するステップと、
をさらに備えてもよい。
【００５６】
上記一態様において、再決定するステップが、前記識別された変更の影響を受ける各個別実行可能トランザクションスケジューラごとに実行されてもよい。
【００５７】
上記一態様において、前記マルチコアプロセッサ内の少なくとも１つのプロセッサ要素が、実行時に再構成可能である再構成可能論理を含み、
再構成可能論理の構成ごとに、実行可能な状態の実行可能トランザクションをリストし、前記再構成可能なプロセッサ要素の個々の構成に割り振られる実行可能トランザクションの構成待ち行列を設けるステップと、
現在選択されている前記構成インスタンスと関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、
事前定義された閾値に達したときに、現在選択されている前記構成インスタンスを切り換えるステップと、
をさらに備えてもよい。
【００５８】
上記一態様において、前記構成インスタンスを切り換えるステップが、さらに、
現在選択されている前記構成と関連付けられた前記構成待ち行列の内容の出力を停止するステップと、
利用可能な前記構成インスタンスの別の１つを選択し、前記再構成可能論理の前記構成を、前記選択された利用可能な前記構成インスタンスの別の１つに変更するステップと、
前記新しく選択された構成インスタンスに関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、
をさらに備えてもよい。
【００５９】
上記一態様において、前記再構成可能論理がメモリであってもよい。
【００６０】
上記一態様において、前記事前定義された閾値が、前記アプリケーションの保全性を維持するために個々の実行可能トランザクションが実行されねばならなくなるまでの最大許容時間であってもよい。
【００６１】
上記一態様において、前記別の構成インスタンスの選択が、前記構成待ち行列のそれぞれの長さに依存するものであってもよい。
【００６２】
上記一態様において、最も長い構成待ち行列に関連付けられた前記構成インスタンスが選択されてもよい。
【００６３】
上記一態様において、前記複数の個別実行可能トランザクションスケジューラによって少なくとも２つの異なるスケジューリングアルゴリズムが使用されてもよい。
【００６４】
上記一態様において、前記使用されるスケジューリングアルゴリズムが、先入れ先出しスケジューリング、優先度ベースのスケジューリング、ラウンドロビンスケジューリング、または重み付き公平待ち行列スケジューリングを含み得てもよい。
【００６５】
上記一態様において、前記マルチコアプロセッサ内の実行可能トランザクションの操作および／または割り振りが、前記実行可能トランザクションを備える命令を含むメインメモリを参照する、専用メモリ内のポインタを使って実行されてもよい。
【００６６】
上記一態様において、前記配布待ち行列またはディスパッチ待ち行列が、前記専用メモリ内に格納された、リンクされたポインタのセットであってもよい。
【００６７】
上記一態様において、前記ポインタが、スケジューリング決定を行う対象となる前記実行可能トランザクションの特性を定義する複数の実行可能トランザクションパラメータを含み、前記実行可能トランザクションパラメータが、実行可能トランザクションをスケジュールするのに使用されてもよい。
【００６８】
上記一態様において、前記スケジューリングアルゴリズムが、時間が経つにつれて前記パラメータを操作してもよい。
【００６９】
上記一態様において、前記複数の実行可能トランザクションパラメータが、実行可能トランザクションパラメータの第１および第２のサブセットを含み、前記実行可能トランザクションパラメータの第２のサブセットが、前記実行可能トランザクションパラメータの第１のサブセットが事前定義された構成にあるときにだけ利用されてもよい。
【００７０】
本発明の別の実施形態の一態様によれば、方法が提供される。該方法は、
複数のプロセッサ要素を有するマルチコアプロセッサ内でアプリケーションを定義する実行可能トランザクションをスケジュールする方法であって、
実行可能トランザクションスケジューラの階層を維持するステップを備え、前記階層が、使用時の前記アプリケーションの要件に従って実行可能トランザクションをスケジュールするように適合され、前記スケジューラ階層の各レベルが少なくとも１つのスケジューラを備え、前記少なくとも１つのスケジューラが、前記実行可能トランザクションを、前記プロセッサ要素の１つ以上での実行に最も適格なトランザクションの順にソートするための少なくとも１つの規則を備える方法である。
【００７１】
本発明の別の実施形態の一態様によれば、方法が提供される。該方法は、
少なくとも１つのプロセッサ要素プールとして構成されている、それぞれが少なくとも１つの節電モードを有する複数のプロセッサ要素を有するマルチコアプロセッサにおいて電力消費を管理する方法であって、
前記プロセッサ要素プールに割り振られた実行可能トランザクションの数が、前記利用可能なプロセッサ要素のごく一部分が実行可能トランザクションの実行に使用されるような数になったときに、前記プロセッサ要素プール内の前記プロセッサ要素の１つ以上を第１の節電モードにするステップをさらに備える方法である。
【００７２】
本発明の別の実施形態の一態様によれば、方法が提供される。該方法は、
複数のプロセッサ要素を有するマルチコアプロセッサにおいて実行可能トランザクションをスケジュールする方法であって、前記マルチコアプロセッサ内の少なくとも１つのプロセッサ要素が、実行時に再構成可能である再構成可能論理を含み、
再構成可能論理の構成ごとに、実行可能な状態の実行可能トランザクションをリストし、前記再構成可能なプロセッサ要素の個々の構成に割り振られる実行可能トランザクションの構成待ち行列を設けるステップと、
現在選択されている前記構成インスタンスと関連付けられた前記構成待ち行列の内容を、実行のために前記再構成可能なプロセッサ要素に出力するステップと、
事前定義された閾値に達したときに、現在選択されている前記構成インスタンスを切り換えるステップと、
を備える方法である。
【００７３】
本発明の別の実施形態の一態様によれば、コンピュータプログラムが提供される。該コンピュータプログラムは、
ディジタル論理によって実行されると、上記一態様のいずれかの方法を実行する命令を備えるコンピュータプログラムである。
【００７４】
本発明の別の実施形態の一態様によれば、コンピュータ可読媒体が提供される。該コンピュータ可読媒体は、
コンピュータによって実行されると、上記一態様のいずれかの方法を実行する命令を含むコンピュータ可読媒体である。
【図面の簡単な説明】
【００７５】
【図１】マルチコアシステムにおけるタスクまたはスレッドの管理のためにＳｙｓｔｅｍＷｅａｖｅｒで実施されるものと類似のタスク状態図を示す。
【図２】スケジューリング点が発生させる待ち行列点に対するスケジューリング点の図を示す。
【図３】ソフトウェアクライアントシムの基本要素を示す。
【図４】動作時のＳｙｓｔｅｍＷｅａｖｅｒクライアントの状態図を示す。
【図５】スケジューリングコーンと配布コーンを示す。
【図６】親子関係を例示するスケジューラ階層図を示す。
【図７】スケジューリングコーン実装の一例を示す。
【図８】典型的な処理リソースプール構成を示す。
【図９】タスク記述子内に存在するスケジューリングメトリックを示す。
【図１０】単一プロセッサの最も基本的な構成を示す。
【図１１】単一の処理リソースインスタンスでのより代表的なスケジューリング構造を示す。
【図１２】ＦＩＦＯスケジューリング層の１つの詳細図を示す。
【図１３】２つの処理リソースインスタンスを含むプールでのこの種の構造の図を示す。
【図１４】処理リソースが２つのプールに関与する構造例を示す。
【図１５】５つの処理リソースインスタンスと、２つの配布プールを備える構成を示す。
【図１６】スケジューリング解析、ポリシおよび演算子の例を示す。
【図１７】基本スケジューリング階層上のイベントでの再スケジューリング範囲を示す。
【図１８】単純な２インスタンス処理リソースプールでの再スケジューリング範囲を示す。
【図１９】単純なプッシュ操作での再スケジューリング範囲を示す。
【図２０】図１８に示すプッシュイベントの結果として発生する再スケジューリングでのシーケンス図を示す。
【図２１】処理リソースプールにおけるメトリック伝搬を示す。
【図２２】実行状態の２つの部分、通常状態および非推奨状態を示す。
【図２３】タイムスライスグループが、バックグラウンドにおいて、フォアグラウンドの、イベント駆動型タスクのグループと共に動作し、サービスを必要とするときに優先権を得る、典型的なタイムスライス構成を示す。
【図２４】タスク優先度デルタ図である。
【図２５】単一のプロセッサと３つのタイムスライスタスクを用いる従来の場合を示す。
【図２６】２つのプロセッサを用いる同じシナリオを示す。
【図２７】利用可能な処理リソースの数がタイムスライスタスクの数と等しいときに、各タイムスライスタスクが、プロセッサの１つで間断なく実行されることを例示する。
【図２８】配布層スケジューリングの例を示す。
【図２９】昇順優先度を使ったアイドル状態における時間の経過に従った処理リソースインスタンス（ＰＲＩ）の「実行優先度」を示す。
【図３０】未完了タスクの管理の論理図を示す。
【図３１】アーキテクチャの一例を示す。
【図３２】最小限のコンテキストスラッシングのためのスケジューラグループ化のアルゴリズムを示す。
【図３３】アルゴリズムを実施するために選択され得るスケジューリング階層を示す。
【図３４】スケジューリングアルゴリズムのシミュレーションの結果を示す。
【図３５】複合スケジューリングアルゴリズムの例を示す。
【図３６】図７以後のすべてのスケジューリング図での図参照凡例を示す。
【図３７】システム構成図である。
【図３８】コア周辺で見られるインターフェースグループを示す。
【図３９】ＳｙｓｔｅｍＷｅａｖｅｒサーバエンティティの主要な論理構成要素を示す。
【図４０】ＳｙｓｔｅｍＷｅａｖｅｒアーキテクチャの基本サブブロックを示す。
【図４１】スレッド記述子とマーカスレッド記述子の両方がトラバースする内部スレッド状態図を示す。
【図４２】スケジューラ層が存在する状態の間の相関を示す。
【図４３】ＴＳＩＦ１次入出力を示す。
【図４４】１サイクル当たりのウォッチドッグ割り込み制御の流れ図である。
【図４５】ＴＳＩＦ内のタイムスライスサポート論理のシステムごとクロックサイクル挙動を示す。
【図４６】Ａは、各プレスケールウォッチドッグクロックサイクルごとの、各処理リソースインスタンスごとの挙動を示し、Ｂは、プレスケールタイムスライスクロックの各サイクルごとの、各処理リソースごとの挙動を示す。
【図４７】ＴＳＩＭ１次入出力を示す。
【図４８】ＴＳＩＭ内部アーキテクチャを示す。
【図４９】ＴＳＰＭ１次入出力を示す。
【図５０】ＴＳＰＭ保留待ち行列構造を示す。
【図５１】タイムアウト待ち行列の基本構造を示す。
【図５２】各プレスケールクロックティックごとに行われる操作を示す。
【図５３】タイムアウト論理の動作モードの非常に基本的な表現を示す。
【図５４】スレッド１タイムアウトが経過し、関連付けられたポップ操作が行われた後の前のタイマ待ち行列構造を示す。
【図５５】スレッド２のポップ後の待ち行列の状態を示す。
【図５６】スレッド３のポップ後の状態を示す。
【図５７】ＴＳＯＭ１次入出力を示す。
【図５８】ＴＳＩＭ内部アーキテクチャを示す。
【図５９】ＴＳＳＭ１次入出力を示す。
【図６０】再スケジュール操作の基本的流れを示す。
【図６１】単一受け渡しスケジューリング操作を示す。
【図６２】ポップでの層内スケジューリングおよび汎用スケジューリング操作を示す。
【図６３】層間スケジューリングの基本的流れを示す。
【図６４】層間スケジューリングルーチンにおけるディスパッチ待ち行列処理を示す。
【図６５】プール間スケジューリングにおけるプール配布層の反復を示す。
【図６６】図６５に図示する、プール層間スケジューリング操作の流れを示す。
【図６７】プール層内スケジューリングの流れを示す。
【図６８】スレッド記述子の静的スケジューリング要素へのプッシュに関連付けられるＴＳＳＭスケジューラ処理を示す。
【図６９】より階層化されたスケジューリング階層を示す。
【図７０】プールスケジューリング操作の第３の例を示す。
【図７１】ＴＳＭＭ１次入出力を示す。
【図７２】プッシュイベントのＴＳＯＭとＴＳＳＭ間の対話のシーケンス図である。
【図７３】ポップイベントのＴＳＯＭとＴＳＳＭ間の対話のシーケンス図である。
【図７４】ＳｙｓｔｅｍＷｅａｖｅｒサーバサブブロック間の作業待ち行列アーキテクシャを示す。
【発明を実施するための形態】
【００７６】
［概要］
図１に、マルチコアシステムにおけるタスクまたはスレッドの管理のためにＳｙｓｔｅｍＷｅａｖｅｒで実施されるものと類似のタスク状態図を示す。
【００７７】
マルチコアシステムにおいて、スケジューラは、１組の事前定義された規則（「スケジュール」）に従い、最適な時刻に、最適なリソースに対して作業パケットを提供する。スケジューリングは、以下のように、アプリケーションと基礎ハードウェアプラットフォームの両方によって必要とされる。
−アプリケーションスケジューリングは、同期および適格性を備える。同期は、システム内のリソースが、データおよび、おそらく、システム全体の保全性を損なうことなく共用され得るよう保証する。適格性は、作動可能タスクが、スケジューリングポリシーで表されるアプリケーションの必要と整合する方法で処理リソースに発行されるよう保証する。
−プラットフォームベースの／配布スケジューリングは、アプリケーションタスクが適切な処理リソースインスタンス間で配布されるポリシーを定義する。これは、複数のユーザおよび／または複数の異なるアルゴリズム間で処理リソースを共用することを示唆してもよい。
【００７８】
図２に、スケジューリング点が発生させる待ち行列点に対するスケジューリング点の図を示す。
【００７９】
左から右に向かって、発生する第１の待ち行列点は保留待ち行列である。ブロックされたタスクは、それらの優先度に従って保留待ち行列に格納され、同期イベントによって解放される。保留待ち行列の構造および挙動についてのこれ以上の考察は、本明細書の範囲を超えるものである。第２の待ち行列点は作動可能待ち行列であり、これは、アプリケーションと配布両方のスケジューリングを備える。図２では、これが３つの論理部分、すなわちアプリケーションおよび配布スケジューリングに分かれている。概念的には、これら２つのスケジューリング段の間にあるのが、すべての現在作動可能なアプリケーションタスクが、（ユーザ定義のメトリックおよびスケジューリングポリシーで表される）それらの適格性に従ってソートされている点である。これが、配布ノードと呼ばれる点である。
【００８０】
配布ノードの前に、異なるクラスのタスクおよび共通クラスのタスクインスタンスが、処理リソースインスタンスへのアクセスを求めてどのようにして競合するかを決定する１組のアプリケーション特有のスケジューリングポリシーが構成される。このスケジューリングポリシーの階層をスケジューリングコーンといい、アプリケーション特有のものである。
【００８１】
スケジューリングコーンの後で、最も適格なアプリケーションタスクが、基礎ハードウェアプラットフォームに存在する処理リソースインスタンスにどのようにして配布されるかを決定する、１組のプラットフォーム特有のスケジューリングポリシーが構成される。このスケジューリングポリシーの階層を配布コーンといい、プラットフォーム特有のものである。
【００８２】
スケジューリングポリシーおよび実装の有効性は、以下の多くの特性の組み合わせに基づいて判断され得る。
−スループット−  毎秒行われ得るスケジューリング決定の数
−待ち時間−  システム内のイベントと、そのイベントに関連付けられたスケジューリング操作の完了の間に経過する時間
−予測可能性／決定性−  システムが、あらゆる環境下でどのようにして振る舞うか決定する能力
−効率性−  任意の所与のスケジューリングアルゴリズムがその範囲内で実施され得る効率性。これは、１決定当たりの命令数（命令セット効率の測定値）および／またはシリコンフットプリント（メモリその他のダイ面積）として測定され得る。
−ポリシー−  サポートされるポリシーの多様性およびそれらを組み合わせて複雑な階層を形成することのできる能力。
【００８３】
［構成要素］
サーバコアとクライアントシムという、ＳｙｓｔｅｍＷｅａｖｅｒの２つの主要な構成要素がある。これらは様々な方法で接続され得る。ＳｙｓｔｅｍＷｅａｖｅｒ対応システムは、サーバコアと、少なくとも１つのクライアントシムとを備えるはずである。
【００８４】
［ＳｙｓｔｅｍＷｅａｖｅｒコア］
ＳｙｓｔｅｍＷｅａｖｅｒコアは、ハードウェアエンジンと密結合メモリとを備える。メモリは、スケジューリング構成と、システム内の作業単位を表すのに使用される動的記述子とを含む。各ＳｙｓｔｅｍＷｅａｖｅｒコアは、命令セットベースのアーキテクチャとすることも、ハードウェアアクセラレータとすることもできる複数のクライアントにまたがって集約される。ＳｙｓｔｅｍＷｅａｖｅｒは、以下の２つの論理的に別個のデータパスを介して各クライアントと個別にやりとりする。
−クライアントに、注意を必要とするシステム状態の変更を知らせる帯域外信号。ＳｙｓｔｅｍＷｅａｖｅｒコアは、通常、割り込みとして実施される（これ以降仮定される）このインターフェースのマスタである。
−クライアントがそれを介してＳｙｓｔｅｍＷｅａｖｅｒに応答させることのできるデータパス。クライアントは、バス、二重シリアルインターフェースまたは他の任意の双方向実装として実施され得るこのインターフェースのマスタである。
【００８５】
ブートプロセスの間に、ＳｙｓｔｅｍＷｅａｖｅｒコアは初期設定されなければならない。通常は、１つのクライアントがブートマスタに指定され、システムの残りの部分に代わって、ＳｙｓｔｅｍＷｅａｖｅｒおよびそれに関連付けられたメモリを初期設定する。
【００８６】
［ＳｙｓｔｅｍＷｅａｖｅｒクライアントシム］
従来の構成では、各クライアントは、個別のクライアントシムを有するが、より保守的な実装形態では、複数のクライアントにわたってクライアントシムを集約することもある。クライアントシムは、ハードウェアとしてもソフトウェアとして実施され得る。図３に、以下のソフトウェアクライアントシムの基本要素を示す。
−ＳｙｓｔｅｍＷｅａｖｅｒＨＡＬは、ＳｙｓｔｅｍＷｅａｖｅｒコアのレジスタインターフェースに必要なコマンドフォーマット設定を実施する。
−ＳｙｓｔｅｍＷｅａｖｅｒＡＰＩは、アプリケーションが、タスクベースの抽象化においてＳｙｓｔｅｍＷｅａｖｅｒコアへの呼び出しを行うことを可能にする。
−ユーザスレッドは、ＳｙｓｔｅｍＷｅａｖｅｒタスク管理機能を使用するアプリケーションスレッドである。任意の時点において、ただ１つのユーザスレッドだけが、直接、各個別クライアントの管理下にある。
−クライアントシムは、帯域外信号サービス（通常は、割り込みサービス）を処理する。主として、クライアントシムは、処理リソースインスタンス内のコンテキストを管理し、タスク切換えおよび優先使用を介して保全性が保存されるようにする。通常、クライアントシムは、アーキテクチャ上不可知の部分および命令セットアーキテクチャ特有の部分を含む。
−アイドルエージェントは、個別処理リソースインスタンスの電源遮断モードまたはマクロアーキテクチャを処理する管理タスクを実施する。
【００８７】
図４に、動作時のＳｙｓｔｅｍＷｅａｖｅｒクライアントの状態図を示す。クライアントシムは、以下の２つの主要な機能を果たす。
−内部で処理リソースインスタンスが実行されている「コンテキスト」（従来のプロセッサでは、コンテキストは、プロセッサスタック空間および内容、レジスタ値、プログラムカウンタなどを含むことができる）の管理（適切な時刻における割り振り、格納および復元）。内部でユーザタスクが実行されるコンテキストであるユーザまたはタスクコンテキストと、クライアントシム管理操作専用のコンテキストである処理インスタンス特有のコンテキストという、２種類のコンテキストがある。
−動作モードの管理（従来のプロセッサでは、いくつかの重要なシステムリソースにアクセスする権限を定義する、ユーザ（通常）モードおよびスーパバイザ（特権）モードが利用可能である。例えば、スーパバイザモードタスクとは異なり、ユーザモードタスクには、処理リソースを共用する他のユーザモードタスクに悪影響を及ぼし得るリソースへのアクセスは許可されない）。
【００８８】
以下の説明は汎用プロセッサでのものであるが、あらゆる種類のクライアントに類似性が存在する。
−「アイドル」状態−  アイドル状態の間、ユーザ定義のアルゴリズムは、エンド処理リソースインスタンスによって供与される電源遮断モード（例えば、クロックゲーティングや他の低電力状態）あるいはシステムアーキテクチャ全体によって供与される電源遮断モード（例えば、クロックゲーティングや、個々の処理リソースインスタンスへの電力供給の低減または除去）を利用することができる。この状態の間、処理リソースインスタンスは、特権モードで動作することができ、処理リソース特有のコンテキストを使用することになる。
【００８９】
ＳｙｓｔｅｍＷｅａｖｅｒサーバは、クライアントに、アイドル状態に入るように命令しないことに留意されたい。クライアントは、スケジュールされたタスクが無いことの結果としてアイドル状態に入るのである。各クライアントは、ＳｙｓｔｅｍＷｅａｖｅｒサーバからの帯域外信号（通常は割り込み）を介して応答するよう命令されるまで「アイドル」状態のままに留まる。
−「クライアントシム」状態−  クライアントシム状態は、ユーザおよびアイドルタスクの実行コンテキストを管理する。「クライアントシム」状態にあるとき、クライアントシムは、実行を終了しており、取って代わられており、またはブロックしている任意のタスクのコンテキストを保存し、次の実行タスクのコンテキスト（アイドルタスクの場合には、これは、処理リソースインスタンス特有のコンテキストである）を回復し、または作成する。この状態になる間、処理リソースインスタンスは、特権モードで動作してもよい。場合によっては、クライアントシムは、処理リソース特有のコンテキスト、あるいはユーザまたはタスクコンテキストのどちらかで動作してもよい。
【００９０】
「クライアントシム」状態に入るのは、ＳｙｓｔｅｍＷｅａｖｅｒサーバからの帯域外信号の結果として（「ユーザ」または「アイドル」状態から「クライアントシム」状態への遷移）、あるいは実行中のタスクをブロックさせているＳｙｓｔｅｍＷｅａｖｅｒＡＰＩ呼び出しの結果として（例えば、セマフォをロックしようとする試みが失敗した結果としての、「ＳｙＷＡＰＩ」状態から「クライアントシム」状態）である。
【００９１】
処理が完了すると、クライアントシムは、それ以上の外部信号なしで、「クライアントシム」状態を、（その処理リソースインスタンスでの未完了のタスクが無い場合には）「アイドル」状態に、または（その処理リソースインスタンスでの適格なタスクが存在する場合には）「ユーザ」状態に遷移させてもよい。
−「ユーザ」状態−  「ユーザ」状態にあるとき、クライアントシムは、ユーザアプリケーションコードを実行する。この状態にある間、処理リソースインスタンスは、通常、「ユーザ」モードまたは「通常」モードで動作するはずである。「ユーザ」状態は、完全にユーザまたはタスクコンテキスト内で動作するはずである。
【００９２】
「ユーザ」状態には、ユーザタスクを開始し、または再開した結果として、「クライアントシム」状態から、あるいはＳｙｓｔｅｍＷｅａｖｅｒサーバＡＰＩ呼び出しからの戻りの結果として、ＳｙＷＡＰＩ状態から入ることができる。
【００９３】
クライアントシムは、タスク完了または優先使用（ＳｙｓｔｅｍＷｅａｖｅｒサーバからの帯域外信号の受け取り）の結果として、「ユーザ」状態から「クライアントシム」状態に遷移し得る。クライアントシムは、ＳｙｓｔｅｍＷｅａｖｅｒサーバＡＰＩへの呼び出しの結果として「ユーザ」状態からＳｙＷＡＰＩ状態に遷移し得る。
−「ＳｙＷＡＰＩ」状態−  ユーザタスクがＳｙｓｔｅｍＷｅａｖｅｒコアとの対話を必要とする場合、ユーザタスクは、「ＳｙＷＡＰＩ」へのクライアントシム状態変更を生じさせるＳｙｓｔｅｍＷｅａｖｅｒＡＰＩを介して対話する。この状態にある間、処理リソースインスタンスは、特権モードで動作してもよい。「ＳｙＷＡＰＩ」状態は、完全にユーザまたはタスクコンテキスト内で動作するはずである。
【００９４】
「ＳｙＷＡＰＩ」状態になるのは、ＳｙｓｔｅｍＷｅａｖｅｒＡＰＩへの呼び出しの後である。非ブロック呼び出しでは、クライアントシムは、「ＳｙＷＡＰＩ」状態から「ユーザ」状態に戻るが、例えば、セマフォに関連付けられるものなど、いくつかのアクセスは、ユーザタスクをブロックさせることになり得る（ブロックされたタスクは、何らかの共用システムリソースが利用可能になるまで待機しなければならない）。この場合、クライアントシムは、「クライアントシム」状態に遷移する。
【００９５】
［概念］
以下の項では、ＳｙｓｔｅｍＷｅａｖｅｒスケジューラの動作を理解するのに必要とされる概念を論じる。
【００９６】
［ＳｙｓｔｅｍＷｅａｖｅｒメモリ要素］
ＳｙｓｔｅｍＷｅａｖｅｒは、接続された密結合メモリを必要とし、スケジューリングポリシー格納のためにこのメモリを使用することで、システム開発プロセス全体を通しての完全なスケジューリング変更および柔軟な調整が可能になる。ＳｙｓｔｅｍＷｅａｖｅｒメモリは、ＳｙｓｔｅｍＷｅａｖｅｒメモリ要素（ＷＭＥ）に分割される。ＷＭＥは、以下で論じるタスクおよびスケジューリング記述子を表すのに使用される。
【００９７】
［タスク記述子］
タスク記述子は、ＳｙｓｔｅｍＷｅａｖｅｒアーキテクチャの基本「通貨単位」である。タスク記述子は、スケジューリング階層内で構成された規則に従って処理リソースインスタンスへのアクセスを求めて競合する作業単位を表す。タスク記述子は以下のものを含む。
−実行されるべきタスクへの参照およびタスクがそれに対して実行されなければならないデータセットをさらに含む、タスク制御ブロックへの参照。
−タスクの適格性を定義するスケジューリングメトリック。
−また、最初にブロックされるタスクのための同期参照およびタイムアウトが含まれてもよい。ブロックされるタスク挙動の詳細な説明は、本明細書の範囲外である。
−タスク記述子が（おそらく、同期後に）そこに追加されなければならないスケジューリング階層の部分を定義する「入口ノード」への参照。
【００９８】
［スケジューリングおよび配布コーン］
スケジューリングおよび配布コーンという２種類のコーンを使って、ＳｙｓｔｅｍＷｅａｖｅｒスケジューリング挙動が記述される。スケジューリングコーンは、多数の「入口」点から単一の集約点に収束するスケジューラの階層、すなわち多対１マッピングを記述するのに使用される。配布コーンは、単一の集約点から多数の「ディスパッチ」点へと発散するスケジューラの階層、すなわち、１対多マッピングを記述するのに使用される。
【００９９】
「スケジューリングコーン」
（図５に赤で示す）スケジューリングコーンは、図２の作動可能状態内の「アプリケーションスケジューリング」としても示す）アプリケーションの必要によって駆動される、「アプリケーション決定ノード」階層を定義する。スケジューリングコーンは、複数のタスククラスおよびタスククラスの複数のインスタンスがシステムリソースを求めて競合するための規則を定義する、多対１マッピングである。
【０１００】
「配布コーン」
（図５に紫で示す）配布コーンは、（図２の作動可能状態内の「配布スケジューリング」としても示す）主に、基礎ハードウェアプラットフォームの特性によって駆動される、「配布決定ノード」階層を定義する。配布コーンは、スケジューリングコーンの最も適格な候補を利用できる適切な処理リソース間で分配するための規則を定義する。
【０１０１】
「１次スケジューリングノード」
スケジューリング構成を記述するのに使用される３つの１次ノードがあり、それらは、入口ノード、配布ノードおよびディスパッチである。１次ノードは、スケジューラの詳細な実装をより綿密に反映する、基礎をなす２次ノード構造の上のオーバーレイである。
【０１０２】
「入口ノード」
入口ノードは、新規タスクが待ち行列に入れられる点を定義する。入口ノードは、通常、スケジューリングコーンの両極端として配布ノード上に多対１でマップする。入口ノードは、特定のタスククラスに関連付けられてもよく、他のアプリケーション駆動ポリシーに従ってもよい。所与の入口ノードは、単一の配布ノード上にのみマップし得る。
【０１０３】
配布ノード
配布ノードは、スケジューリングと配布コーンの間の記述を定義する。配布ノードは、通常、処理リソースのクラスを表す。スケジューリングコーンは、通常、単一の配布ノード上に１つ以上の入口ノードをマップし、配布コーンは、通常、複数のディスパッチノード、従って最終的には処理リソースインスタンス上に、単一の配布ノードをマップする。
【０１０４】
「ディスパッチノード」
ディスパッチノードは、個別処理リソースインスタンスに関連付けられた出口点を定義する。ディスパッチノードは、通常、ハードウェアプラットフォーム内に存在するＩＰコアと１対１でマップする（但し、ハードウェアマルチスレッドプロセッサコアには、複数のディスパッチ待ち行列が割り振られてもよい）。複数の配布コーンが個別ディスパッチノード上にマップしてもよい。
【０１０５】
「２次スケジューリングノード」
２種類の決定ノード、すなわち、アプリケーション決定ノードおよび配布決定ノードが定義される。アプリケーション決定ノードおよび配布決定ノードは、スケジューリング層上に直接マップするが、これらは、スケジューラ実装内の基礎をなす層の数または種類を網羅的に定義するものではない。
【０１０６】
「アプリケーション決定ノード」
アプリケーション決定ノードは、スケジューリングコーン内の中間スケジューリング点または集約点を定義する。各アプリケーション決定ノードは、１組の候補のうちで最も適格な候補を選択するための規則を定義する。
【０１０７】
「配布決定ノード」
複数の配布ノードが単一のディスパッチノード上にマップする場合、処理リソースインスタンスにアクセスすることのできる配布コーンを決定するポリシーを設定するために、配布決定ノードが必要とされる。
【０１０８】
［スケジュール構成］
作動可能状態構造（図２）は、実行可能な状態のスレッドを含む。作動可能状態構造全体でとしては、多数のスケジューリングおよび配布コーンを備えることができる。これらのスレッドは、独立のスレッドプリミティブを用いて作成された（すなわち、作動可能状態において作成された）ものであり、またはこれらが依存する同期プリミティブまたはタイムアウトを受け取っているものである。同期スレッドは、以前に、ブロック状態から遷移している。
【０１０９】
作動可能状態構造は、スケジューラノード記述子および独立のスレッド記述子を含んでいてもよい。この構造は、システム初期設定時におおむね定義されるが、スレッド記述子およびそれらに関連付けられた動的スケジューラ層記述子は、実行時に出入りすることを許される。
【０１１０】
作動可能状態構造は、スレッドが、処理ノードのプール、または特定の処理ノードに対してスケジュールされることを可能にする。これは、特定のタスクを特定の機能を有する処理リソース（例えば、ハードウェアアクセラレータや入出力装置など）に向けることのできる能力を維持しつつ、複数の互換性のある処理リソースにまたがる負荷均衡化またはその他の配布挙動を可能にするものである。
【０１１１】
スケジューリング層は、作動可能状態構造を構成する１次および２次スケジューリングノードを実施するのに使用される基本リソースである。スケジューリング層は、他のスケジューリング層およびタスク記述子と、親、子またはピア関係を持ち得る。
【０１１２】
図６に、親子関係を例示するスケジューラ階層図を示す。この例において、ｙはａ、ｂおよびｃの親である。ｙは、ｘとｚのピアである。親は、スケジューリング層とすることしかできないが、子は、スケジューリング層とすることも、タスク記述子とすることもできる。所与のピアグループ（例えば、ａ、ｂおよびｃ）は、タスク記述子とスケジューリング層の混ざったもので構成されていてもよい。また、すべてのスケジューリング層は親を持つ（ディスパッチノードは、親を定義しない唯一の記述子である）。
【０１１３】
実行時に、親層は、ユーザ定義のポリシーに従って最も適格な子から「メトリック」（優先度など）を継承してもよい。この機能は、深く組み込まれたスケジューリングポリシーが、比較されているスケジューリング分岐からの適格な候補の何らかの知識を必要とする場合に使用されてもよい（この問題は、以下のメトリック伝搬の項で詳細にカバーする）。
【０１１４】
以下の各項では、任意のＳｙｓｔｅｍＷｅａｖｅｒスケジューリング階層の基本構成要素を説明する。
【０１１５】
「基本スケジューラ層」
スケジューラ層は、スレッド記述子をスケジュールするのに使用される階層を定義する。各スケジューラ層は、通常、スケジューリングアルゴリズム、スケジューリング決定を行うのに使用されるいくつかのメトリック、メトリックがどのようにして子から親に伝搬されるか定義するのに使用される継承ポリシー、および別のスケジューラ層またはスレッド記述子とすることのできる子要素のリストを定義する。３種類のスケジューラ層記述子があり、それらは、ルート、静的および動的である（動的層は、特殊な種類の静的スケジューリング層である）。図７に、スケジューリングコーン実装の一例を示す。図３６に、図７以後のすべてのスケジューリング図での図参照凡例を示す。
【０１１６】
「スケジューラルート記述子」
スケジューラルート記述子は、ディスパッチ待ち行列との１対１マッピングを有する。スケジューラルート記述子は、作動可能状態構造における最終ノードを表す。ルート記述子メトリックは、常に、定義された継承ポリシーに従って作動可能状態構造から導出されるメトリックのコピーを含む。
【０１１７】
スケジューラルート記述子は、システム初期設定時に構成され、永続的に存在する。
【０１１８】
「静的スケジューラ記述子」
スケジューラ静的記述子は、スケジューリング階層のルートノード下に存在する。静的スケジューラ記述子の親は、他の静的スケジューラ記述子とすることも、ルート記述子とすることもできる。スケジューラ静的記述子は、その親によって定義されるスケジューラアルゴリズムおよび独自のスケジューラメトリックに従って兄弟ノードと競合する。
【０１１９】
スケジューラ静的記述子は、システム初期設定時に構成され、永続的に存在する。動作時に、ＳｙｓｔｅｍＷｅａｖｅｒは、選択されたスケジューリングおよびメトリック伝搬アルゴリズムに従ってスケジューラメトリックを維持する。
【０１２０】
「動的スケジューラ記述子」
スケジューラ動的記述子は、スケジューリング階層のルートノード、および、場合によって、静的ノードの下に存在する。動的スケジューラ記述子の親は、静的スケジューラ記述子とすることも、ルート記述子とすることもできる。動的スケジューラ記述子は、その親によって定義されるスケジューラアルゴリズムおよび独自のスケジューラメトリックに従って兄弟ノードと競合する。
【０１２１】
動的スケジューラ記述子は、いつも構成されてもよい。これは、システムが、純粋に静的な備えで可能なはずのスケジューリング層よりはるかに多数のスケジューリング層をサポートすることを可能にする。ＳｙｓｔｅｍＷｅａｖｅｒは、全期間にわたって、多数の多様なスレッドおよび動的スケジューラ層記述子が使用されるが、ある有限期間に過渡的要求がより小さくなる可能性を利用することによってこれを実現する。例えば、最大４０００の動的要素（スレッドおよび動的スケジューラ記述子）をサポートするメモリが接続されたネットワークシステムでは、１６０００接続をサポートすることが可能であると考えられる。なぜなら、任意の時点において、プロセッサでは、全接続空間のほんの一部からのデータ単位だけが活動状態だからである。この柔軟性は、性能をわずかに犠牲にして達成される。なぜなら、動的スケジューラ記述子が存在しない場合、子スレッド記述子の追加の前にそれが作成されなければならないからである。
【０１２２】
動作時に、ＳｙｓｔｅｍＷｅａｖｅｒは、選択されたスケジューリングアルゴリズムに従ってスケジューラメトリックを維持する。いくつかの状況下において、ＳｙｓｔｅｍＷｅａｖｅｒは、動的スケジューラ記述子を解放してＷＭＥフリーリストに戻す。
【０１２３】
「プロセッサリソースプール」
プロセッサリソースプールは、特定の処理リソースのインスタンスの単一の配布ノードへの集約を可能にする。その場合、配布ノードは、処理リソースプールの個別メンバにまたがって負荷均衡化、インテリジェント優先使用および電源管理を提供してもよい。
【０１２４】
図８に、典型的な処理リソースプール構成を示す。以下のＷｅａｖｅｒメモリ要素の３つの新しい定義がプロセッサプール構成構造をサポートする。
【０１２５】
プール接続ノード
プール接続ノード（ＰＡＮ）は、スケジューラルート層を処理リソースプールルート層に接続するのに使用される。ＰＡＮは、スケジューラルート層内に存在しなければならない（すなわち、その親は、スケジューラルートノードでなければならない）。動作時に、ＰＡＮメトリックは、スケジューリングコーンから継承されたものである、プールルートノード（ＰＲＮ）のメトリックのコピーで自動的に更新される。
【０１２６】
ＰＡＮ内で定義されるスケジュール演算子は使用されない。
【０１２７】
プール静的ノード
プール静的ノード（ＰＳＮ）は、スケジューラルート層を処理リソースプールルート層に接続するのに使用される。プール静的ノードは、プールルート層内に存在し（すなわち、その親はＰＡＮでなければならない）、ディスパッチノード（すなわち、現在実行中のスレッド）のメトリックのコピーを自動的に保持する。
【０１２８】
所与のプールのＰＳＮ内のスケジューラ演算子は、すべて、取って代わられるべき適切な処理リソースインスタンスを選択するのに使用されるポリシーを定義する、同じアルゴリズムに設定されなければならない。
【０１２９】
プールルートノード
各処理リソースプールごとに１つのプールルートノード（ＰＲＮ）がある。プールルートノードは、処理リソースプールの配布ノードを定義する。ＰＲＮ内のメトリックは、配布ノードに関連付けられたスケジューリングコーン内で保持される最も適格なスレッドを反映する。ＰＲＮ親ポインタは、プール静的ノードの１つを指し示すように設定されなければならない。
【０１３０】
スケジューラアルゴリズムは、基本的に、スケジューリングコーンの隣接する層の必要に従って設定されるべきである。
【０１３１】
「動的スケジューラ構成」
ＳｙｓｔｅｍＷｅａｖｅｒは、実行時におけるスケジューリングノードの作成および削除をサポートすると共に、喪失や順序付け間違いなしで、ある入口ノードから別の入口ノードにタスククラスを移行させる機能も提供する。動的スケジューラ構成を論じるときには、さらに２つの概念、休止スケジューリング層およびマーカスレッドを導入しなければならない。
−休止スケジューリング層は、階層内に存在し、プッシュ操作を受け入れてもよい（すなわち、子エントリを蓄積してもよい）が、スケジューリングには不適格であり、したがって、決してポップされることがない。
−マーカスレッドは、それらがスケジューリング階層の特定の部分に依存する最後のスレッドであるときに限ってスケジュールされる。スケジューリング階層の一部に依存するスレッド数は、作動可能なスレッドの数、および、作動可能になったときにスケジューリング階層のこの部分を使用することになるブロックされたスレッドの数を含む。マーカスレッドは、他の任意のスレッドと同様にタスク参照を保持することができ、通常は、スケジューリング階層のある部分と別の部分の間の遷移操作の管理を完了するのに使用される。
【０１３２】
以下の項では、階層のある部分からのタスクストリームの遷移シーケンスの一例を詳述する。これは、スケジューリング階層の一部の削除の上位機能であることに留意されたい。
【０１３３】
操作シーケンス
適切な操作シーケンスが確実に順守されるようにするのは、上位レベルのソフトウェアの役割である。このシーケンスを遵守し損なうと予期しない挙動を生じることがあり、特に、新しいスレッドは、マーカスレッドが挿入されているスケジューリング階層の一部に導入されてはならない。
【０１３４】
このシーケンス例では、タスクストリームｔｓｔｒｅａｍが、スケジューラ階層ｈ１から新しいスケジューリング階層ｈ２に遷移するものと仮定する。
−休止スケジューラ階層ｈ２を作成する。
−ｔｓｔｒｅａｍ上のすべての新しいタスク記述子をｈ２に割り当てる。
−マーカスレッドをｈ１に挿入する。
−マーカスレッドの出現を待ち受ける。
−休止階層ｈ２を覚醒させる。
【０１３５】
［スケジューラ解析、アルゴリズム、演算子およびオペランド］
スケジューリング解析は多くの形（ＥＤＦ、ＲＭＡなど）を取り、通常は、アプリケーション、または少なくともセクタに特有のものである。スケジューリング解析の結果は、静的または動的にアプリケーションの実行時配置を制御する１組のポリシーである。その一意のマイクロアーキテクチャを介して、ＳｙｓｔｅｍＷｅａｖｅｒは、これらの事前定義されたポリシー／アルゴリズムを、実行時に効率よく実行する。
【０１３６】
「スケジューリングアルゴリズム」
ＳｙｓｔｅｍＷｅａｖｅｒは、シリコン設計時に、アーキテクチャまたは実装を中断せずに、専門化されたアルゴリズムが定義され得るように設計される。しかしながら、以下のように、いくつかのアルゴリズムがデフォルトで提供される。
−ＦＩＦＯスケジューリング：単純な先入れ先出し待ち行列法。
−優先度スケジューリング：最も適格な候補が、最高（昇順の優先度）または最低（降順の優先度）の優先度メトリックを有する。
−ラウンドロビン：スケジューリング階層からタスクがポップされるときにスケジューリング決定を次のピアに更新する。ラウンドロビンは、スケジューリング階層の「左端」にある関連するスケジューリングポリシーではないことに留意されたい。
−重み付き公平待ち行列法：適格な候補が、割り当てられた重みおよび何らかの負荷尺度（すなわち、パケット長）に従って選択される複雑なスケジューラ。
【０１３７】
スケジューラ階層全体に多少注意すれば、アプリケーションシステムにおいて洗練されたトラフィックおよびタスク管理機能を提供するための、スケジューラアルゴリズムの複雑な組み合わせを容易に作成することができる。
【０１３８】
「演算子」
スケジューリングアルゴリズムは、さらに、以下の個別のスケジューリングおよびメトリック演算子に分解され、これらは２つとも親ノード内で定義される。
−スケジューリング演算子：子ノード内に格納されるオペランドを使って最も適格な候補を決定する方法を定義する。スケジューリング演算子は、子ノード内のオペランドを変更しない。
−メトリック演算子：最も適格な子のオペランドが、親のオペランドに伝搬される方法を定義する。伝搬演算子は、ヌル（親への更新なし）、コピー（親のオペランドの上書き）とすることもでき、子および親オペランドの一部または全部に対する数学的演算が関与してもよい。いかなる場合にも、子オペランドは変更されない。
【０１３９】
スケジューリングおよびメトリック演算子は、ＳｙｓｔｅｍＷｅａｖｅｒスケジューラハードウェアにおいてネイティブで実施される。通常は、スケジューリングとメトリックを組み合わせた演算子を使って、所与のスケジューラアルゴリズムが定義される。スケジューリングアルゴリズムは、一般に、（新しいタスクがスケジューラ階層にプッシュされている）プッシュイベント下における挙動を示唆し、（タスクがスケジューリング階層からポップされる）ポップイベント下とは異なる。例えば、ＦＩＦＯスケジューラを考えると、新しいタスクが空でないＦＩＦＯスケジューリング段にプッシュされるときには、スケジューリング更新は行われず、項目がＦＩＦＯスケジューリング段からポップされるときには、スケジューラは、更新されなければならない。
【０１４０】
スケジューリング演算子
スケジューリング演算子は、拡張可能であるように設計されるが、デフォルト演算子の選択が定義される。スケジューリング演算子は、通常、比較によるものであり、したがってその結果は常にブール値である。以下の表において、Ｍは、以下の方式に従って、スケジューリング層のメンバまたはスケジューリング層記述子自体における２つのメトリックの１つを表す。
−Ｍｃｕｒｒｅｎｔｎは、現在最も適格な候補に属するメトリックを指す。
−Ｍｃａｎｄｉｄａｔｅｎは、スケジューリング更新の過程で現在の記述子が比較される相手の候補に属するメトリックを指す。
−Ｍｔｉｅｒｎは、現在および候補の記述子の接続先のスケジューラ層記述子に属するメトリックを指す。
【表１】
0005386572.tif 000002
【０１４１】
複合スケジューリング演算子
また、複合スケジューリング演算子も利用可能であり、それらは、表１のスケジューリング演算子の組み合わせである。例えば、次式の通りである。
必要な更新＝（MCURRENT0＞MCANDIDATE0）&&（MCURRENT1＜MCANDIDATE1）式中、問題のパラメータは、親と子両方の記述子メトリックを利用することができる。これらの複合演算子は、従来のスケジューリング層とプール配布層の両方で使用され得る。
【０１４２】
さらなる情報および例については、以下のスケジューリングシーケンス図の項を参照されたい。
【０１４３】
メトリック演算子
メトリック演算子は、事実上に算術的である。スケジューリング演算子と同様に、メトリック演算子は、拡張可能であるように設計されるが、１組のデフォルト演算子を有する。表２を参照されたい。メトリック演算子の複雑度の幅は、ヌルまたは単なるコピー演算から複雑な積和演算にまで及ぶ。
【表２】
0005386572.tif 000003
【０１４４】
「オペランド」
スケジューリングオペランド、またはメトリックは、以下の２つのグループに分けられる。
−ローカルメトリックは、処理リソースインスタンス、スケジューラ層およびスレッド記述子と関連付けられる。ローカルメトリックの操作は、自動的に、再スケジュールイベントを発生させる。
−グローバルメトリックは、場合によって、通常は、システムリソース状態（バス使用度やフリーメモリなど何らかのヒューリスティックス）と関連付けられる。
【０１４５】
所与のスケジューリングアルゴリズムは２つのメトリックだけを使用することができ、その一方はローカルでなければならない。第２のメトリックの種類は、Ｍｅｔｒｉｃ１ＩｓＧｌｏｂａｌフラグによって決定される。
−Ｍｅｔｒｉｃ１ＩｓＧｌｏｂａｌがリセットされるとき、メトリック１はローカルであり、スケジューリング操作においてリテラルとして使用される。
−Ｍｅｔｒｉｃ１ＩｓＧｌｏｂａｌが設定されるとき、メトリック１は、グローバルメトリックポートの配列へのインデックスである。
【０１４６】
ローカルメトリック
タスク記述子もスケジューリング層記述子も２つの３２ビットオペランド、すなわちスケジューリングメトリックを含む。これらのオペランドは、スケジューリング操作時に、それぞれの親によって使用され、後続の階層上位のスケジューリングのために、スケジューリング操作時に変換され、かつ／または親のオペランドに伝搬されてもよい。
【０１４７】
図９に、タスク記述子内に存在するスケジューリングメトリックを示す。タスク記述子内では、メトリック０は、通常、タスクの優先度を表すのに使用される。このメトリックの最下位バイトは、ＳｙｓｔｅｍＷｅａｖｅｒハードウェアおよびクライアントソフトウェア内での内部使用のために予約される。スケジューラ層メトリックに対する制限はない。
【０１４８】
グローバルメトリック
グローバルメトリックは事実上受動的であり、グローバルメトリック値の変更は、すべての潜在的に影響を受けるスケジューリングリソース上での再スケジュールイベントを発生させない。グローバルメトリックは、他の何らかのイベントの結果として、従属スケジューリングリソースがスケジュールされるときに問い合わせを受ける。ＳｙｓｔｅｍＷｅａｖｅｒアーキテクチャは、グローバルメトリックの使用に対しては制限を課さないが、グローバルメトリックは、システムヒューリスティックス（バス利用度、ある時間枠にわたるメモリフィルなど）に使用されてもよく、したがって、変化率は比較的低くなる。また、データを平均化するためにフィルタが適用されてもよい。
【０１４９】
［スケジューリング階層構成の詳細］
以下の各項で参照するすべての構成図で、図３６に示す共通フォーマットを使用する。
【０１５０】
図１０に、単一プロセッサの最も基本的な構成を示す。これには、その必須スケジューリングルートノードを有する、単一の処理リソースインスタンス（単一のディスパッチノード）の構成が示されている。この最も単純な場合には、単一のプロセッサだけしかないため、スケジューラコーンは、単一のＦＩＦＯ段からなり、配布段はヌルである。したがって、スケジューラルートノードは、入口ノードと配布ノードの両方である。
【０１５１】
スケジューラノード実装上の矢印は右から左（親から子）に向かって示されており、これは、子から処理リソースインスタンスへと流れるタスクの「フロー」と反対であることに留意されたい。
【０１５２】
スケジューラはモジュール方式で実装され、揮発性メモリとして構成される。これは、異なるポリシーの連続したスケジューラ層から、非常に洗練されたスケジューラ階層を構築し、開発プロセス全体を通じて調整し、カスタマイズすることを可能にする。しかしながら、無効な構成も可能であり、深くネストされたスケジューラ層から適切なメトリックが使用できるように、特に注意が払われなければならない。
【０１５３】
［層内構造］
スケジューリング層は、到着順に、またはデフォルトのＦＩＦＯ待ち行列ポリシーに従ってエントリを格納する。定義されたスケジューリングポリシーがこの構造上にオーバーレイされる方法については、後述する。新しいノード（または記述子）がプッシュ操作によって層内構造に追加され、ポップ操作の結果として除去される。スケジューリング操作は、層内リンクを操作しない。
【０１５４】
図１１に、単一の処理リソースインスタンスでのより代表的なスケジューリング構造を示す。左から、この例では、２つのＦＩＦＯ段が優先度段に入力する。階層の２つの段において３つのスケジューリング層がある。スケジューリング層は、（図の右側に示す）ただ１つの「出口」ノードだけしか持たないが、潜在的に（図の右側に示す）多くの入口ノードを有することに留意されたい。
【０１５５】
図１２に、ＦＩＦＯスケジューリング層の１つの詳細図を示す。この図には、この層上のすべてのピア間の二重リンクリストを維持する１組のポインタが示されている。二重リンクリストは、層の任意のメンバの除去（ポップ）の性能を最大にするのに使用される。
【０１５６】
この詳細図にはタスク記述子のみを示すが、この構造は、スレッドとスケジューリングノードが混ざったものを含む層にも同様に適用することができる。
【０１５７】
ピア要素間の層内リンクは、プッシュおよびポップ操作時にのみ操作される。
【０１５８】
［層間構造］
プールルート層を除く、層間リンクの構造を図１２に示す。各層は、スケジューラルートノードまたはスケジューリングノードでなければならない、親ノードを持つ。これらのノードは、この層の最も適格なメンバを指し示すポインタを格納する。これらの子ポインタは、親ノード内と子ノード内でそれぞれ定義されるスケジューリングポリシーおよびメトリックに従ってスケジューリングイベントの受け取り時に更新される。
【０１５９】
また、各子ノードは、その親も参照しなければならない。
【０１６０】
［プールルート層構造］
プールルート層構造は、層が、単一の入口ノードおよび多くの出口ノードを持つ特殊な場合である。入口ノードは、（図２の作動可能待ち行列構造の「アプリケーションスケジューリング」部分によって示されるように）スケジューリングコーンが収束する点であり、「配布ノード」ともいう。「出口ノード」は、タスクがそれらを介して配布され得る処理リソースインスタンスのためにプールルート層を「配布スケジューリング」構造にリンクさせる。図１３に、２つの処理リソースインスタンスを含むプールでのこの種の構造の図を示す。
【０１６１】
各プール配布層は、プールルートノード（ＰＲＮ）および１つ以上のプール静的ノード（ＰＳＮ）を含まねばならず、他のどんな種類のノードも許容されない。ＰＲＮは、（ＨｅａｄＩｎｄｅｘフィールド内に格納される）スケジューリングコーンの第１層への参照および配布を考慮されるべき第１のＰＳＮエントリへの参照を含む。共通の配布およびメトリック更新ポリシーが、あらゆるＰＳＮのスケジューラならびにメトリックプッシュおよびポップ演算子内に、それぞれ、格納されなければならない。
【０１６２】
あらゆるＰＳＮが、（ＨｅａｄＩｎｄｅｘフィールドを使って）ＰＲＮをその子として参照しなければならない。
【０１６３】
プール静的ノードの親は、プール接続ノード（ＰＡＮ）でなければならない。ＰＡＮとＰＳＮは、１対１マッピングを持たなければ成らない。しかしながら、各処理リソースインスタンスには、それが関与する各配布プールに関連付けられた複数のＰＡＮがあってもよい。図１４に、処理リソースが２つのプールに関与する構造例を示す。所与の処理リソースがメンバとなり得るプール数は制限されない。さらに、任意のプールが、任意の数の他のプールと、任意の数のその構成処理リソースを共用してもよい。
【０１６４】
スケジューリングルートノード内には、処理リソースインスタンスが関与する配布コーンのそれぞれに関連付けられた２つのＰＡＮがある。加えて、必要に応じて、処理リソースインスタンスへの特定のアクセスを可能にするスケジューリングノードもある。
【０１６５】
プール配布層の各ＰＳＮ内で定義されるスケジューリングポリシーは、所与のタスクの実行に最も適格な処理リソースインスタンスが選択される方法を識別する。例えば、このポリシーは、関連付けられたスケジューリングコーンからの優先度の高いタスクの到着時に、現在優先度の最も低いタスクを実行中の処理リソースインスタンスが優先使用のために選択される、優先度のポリシーとすることもできる。
【０１６６】
図１５に、５つの処理リソースインスタンスと、２つの配布プールを備える構成を示す。ＰＲＩ＃３は両方のプールに関与することに留意されたい。
【０１６７】
［挙動］
以下の項では、ＳｙｓｔｅｍＷｅａｖｅｒスケジューリングの挙動を説明する。
【０１６８】
［一般原則］
以下の各項では、ＳｙｓｔｅｍＷｅａｖｅｒスケジューリングアーキテクチャの主要な基本原則の一部を説明する若干の基本背景情報を示す。
【０１６９】
「ポインタベースの待ち行列法」
図２に詳しく示すように、ＳｙｓｔｅｍＷｅａｖｅｒ内には複数の潜在的待ち行列点があるが、これらはポインタのみを使って実現される。待ち行列に入れられたエンティティ、ＳｙｓｔｅｍＷｅａｖｅｒメモリ要素（ＷＭＥ）は、決してコピーされない。
【０１７０】
「イベントベースのスケジューリング」
ＳｙｓｔｅｍＷｅａｖｅｒは、システム状態の何らかの変更によってそうすることが必要とされたときにのみスケジューリング決定を更新する。状態の変更は、以下の３つのイベントクラスに分けることができる。
−「プッシュイベント」、システム状態の変更が、作動可能待ち行列構造への新しいスレッド記述子（これは、新しいスレッド記述子とすることも、システム状態の変更が、そのスレッドを作動可能させている既存のスレッド記述子とすることもできることに留意されたい）の導入を生じさせている。
−「ポップイベント」、システム状態の変更が、作動可能待ち行列構造からのスレッド記述子の除去を発生させている。
−「更新イベント」、スケジューリングパラメータが変更され、スケジューリング決定の再評価を必要としている。
【０１７１】
これらの変更は、以下のものとすることができる。
−割り込み（すなわち、「プッシュイベント」。割り込みに関連付けられるブロックされたスレッドが作動可能状態に移行するため）。
−実行中のタスクによって作成された新しいタスクの到着（これは、新しいタスクが他の要因またはイベントに依存しない場合には、プッシュイベントとすることができる）。
−同期イベント。例えば、セマフォ信号など（信号を待ち受けてブロックされている信号があると仮定すると、これは、「プッシュイベント」である。なぜなら、ブロックされたスレッド記述子が、作動可能状態に遷移するからである）。
−タスクの実行「優先度」の変更、「更新イベント」。
−処理リソースインスタンス内のタスクの消費（作動可能状態から実行状態への遷移）（「ポップイベント」）。
−タスクのスケジューリングメトリックの変更（「更新イベント」）。
−スケジューラ層のスケジューリングアルゴリズムまたはメトリックの変更（「更新イベント」）。
−スケジューラ階層自体の変更（「更新イベント」）。
【０１７２】
システムが定常状態にある場合、ＳｙｓｔｅｍＷｅａｖｅｒはアイドル状態のままである。原則的に、最も電力効率のよい解決法において、これは、追加のスケジューリングを必要とするイベントの到着を保留にして、ＳｙｓｔｅｍＷｅａｖｅｒの電源を遮断させることを可能にするはずである。グローバルメトリックへの変更は、再スケジュールイベントを発生させないことに留意されたい。
【０１７３】
「“ジャストインタイム”スケジューリング」
所与のスケジューリング層の待ち行列に入れられた新しいエントリが、現在最も適格な（エントリであると親ＨｅａｄＩｎｄｅｘによって識別されている）エントリとのみ比較される。層スケジューリングポリシーにより、それらが現在の先頭より適格である場合には、ＨｅａｄＩｎｄｅｘフィールドが、新しいエントリを参照するように更新される。新しいエントリは、常に、現在のリンクリスト構造の後に配置される。
【０１７４】
スケジューリングポリシーがＦＩＦＯである場合、ＨｅａｄＩｎｄｅｘポインタは、待ち行列が空でない限り、新しいエントリが到着したときに決して更新されない。したがって、新しいエントリが待ち行列の後に配置されるデフォルト挙動は、ＦＩＦＯアルゴリズムと等しい。
【０１７５】
この方式は、プッシュ操作の処理に最小限の時間だけが費やされることを保証し、これは、一般に、スケジューリング性能の待ち時間とみなされる。結果として、ポップスケジューリングは、最悪の場合、ポップ操作時の都度スケジューリング決定を更新するためにスケジューリング層の全内容が評価されなければならないため、より厄介である。しかしながら、物理待ち行列構造において常にネイティブＦＩＦＯアルゴリズムを使用することは望ましい。なぜなら、スケジューリングアルゴリズムの変更は、スケジューラ層が再リンクされることを必要としないからである。さらに、ポップスケジューリングは、一般に、アプリケーション実行と並列で実行することができ、したがって、システム性能全体に及ぼす影響がより小さい。
【０１７６】
「スケジューリング解析、ポリシーおよび演算子」
リアルタイムデッドラインを満たすようにシステムを解析する多くの方法があり、その例としては、ＥＤＦ（Ｅａｒｌｉｅｓｔ  Ｄｅａｄｌｉｎｅ  Ｆｉｒｓｔ）方式やＲＭＳ（Ｒａｔｅ  Ｍｏｎｏｔｏｎｉｃ  Ｓｃｈｅｄｕｌｉｎｇ）や、他の様々な確率論的な方法がある。これらの手法は、アプリケーション特有であり、おそらくは、事実上、固有のものである傾向がある。しかしながら、いかなる場合にも、このようなスケジューリング解析の結果は、１組のスケジューリングポリシー（すなわち、優先度、ＦＩＦＯ、ラウンドロビン、重み付き公平待ち行列法）をもたらし、それらは、実行時に効率よく配置されなければならない。ＳｙｓｔｅｍＷｅａｖｅｒ技術は、スケジューリング解析によって識別されるポリシーの効率のよい実行時実行を目標とするものである。ＳｙｓｔｅｍＷｅａｖｅｒ内の配置のために、各スケジューリングポリシーは、さらに、１組のスケジューリング演算子に復号化される。
【０１７７】
各スケジューラ層は、スケジューリング決定が、スケジューリング層（または下位のスケジューリング層）へのプッシュ、あるいはスケジューリング層（または下位のスケジューリング層）からのポップの結果としてどのように更新されるかを決定するのに使用される２つの演算子を有する。場合によっては、スケジューリング演算子は、スケジューラとタスク記述子両方のメトリックフィールド内に同様に格納されるオペランドを必要とする。
【０１７８】
「スケジューリングメトリックおよびメトリック伝搬演算子」
スケジューリングメトリックは、選択されたスケジューリングアルゴリズムによって必要とされ得る情報を格納し、その最も基本的な例が優先度である。その情報を、後続のスケジューリング決定において直接、またはメトリック更新操作でのオペランドとして使用することができるように、メトリックを、最も適格な候補から親ノードに転送する必要がある場合もある。メトリック伝搬演算子は、プッシュとポップ両方のシナリオで、これがどのようにして達成されるかを定義する。
【０１７９】
階層内のスケジューリングノードの配置に従って、メトリックフィールドは、所与の処理リソース上で現在実行中のスレッドの優先度を反映してもよい。この場合、メトリックフィールドは、優先使用が必要とされるかどうか決定するのに使用される（以下のスケジューリング挙動の項を参照されたい）。
【０１８０】
「スケジューリングリソース」
以下の項では、実行時にスケジューリングアルゴリズムを実施するのに使用される様々なリソースを説明する。
【０１８１】
層スケジューラ層
スケジューラ層は、図６の、スケジューラルートノードとすることのできる親、プールルートノードまたは基本スケジューリングノードおよびいくつかの子からなる。子は、基本スケジューリングノード、スレッドまたはタスク記述子またはプール接続ノードとすることができる。子ノードを、それら自体の権限におけるスケジューリングノード（すなわち、さらなるスケジューラ層の親ノード）とし得るようにすることにより、複雑なスケジューラ階層が構築され得る。
【０１８２】
プール配布層
プール配布層は、プールルートノード（１つのみ）とプール静的ノードだけを含んでいてもよい。１つの処理クラス当たりただ１つのプールルートノードがある。
【０１８３】
ディスパッチ待ち行列記述子
−スケジューラ演算子：現在実行中のタスクが取って代わられるべきかどうか決定するスケジューリングポリシーを定義するのに使用される。
−メトリック伝搬演算子：ディスパッチ待ち行列記述子にはメトリック伝搬演算子はない。
−メトリック：メトリック要素は、通常、現在実行中のスレッドのメトリックを格納する。
【０１８４】
スケジューラおよびプールルートノード
−スケジューラ演算子：スケジューリングコーンの最も適格な候補を決定するのに使用される。
−メトリック伝搬演算子：これらは、常に、スケジューリングコーンの最も適格な候補のメトリックを継承するように設定される。
−メトリック：スケジューリングコーンの現在最も適格な候補のメトリックを保持する。
【０１８５】
スケジューラ層要素
−スケジューラ演算子：接続された層から最も適格な子候補を決定するのに使用される。
−メトリック伝搬演算子：ユーザ定義される。後続のスケジューリング段の必要に従って設定される。
−メトリック：ユーザ定義される。後続のスケジューリング段の必要に従って設定される。メトリック伝搬演算子の中には、これらのフィールドを自動的に更新するものもあることに留意されたい。
【０１８６】
プール静的ノード
−スケジューラ演算子：プール配布層における優先使用に最も適格な候補を決定するのに使用される。
−メトリック伝搬演算子：実行タスクメトリックの伝搬を決定するのに使用される。
−メトリック：プール配布アルゴリズムの必要に従って設定される。デフォルトでは、これらは、現在実行中のスレッドのメトリックを反映するが、いくつかの配布戦略では、静的割り振りが必要とされることもある。
【０１８７】
プール接続ノード
−スケジューラ演算子：使用されない。
−メトリック伝搬演算子：最も適格なタスクメトリックの伝搬を制御するのに使用される。
−メトリック：関連するプールルートノードに接続されたスケジューリングコーンの最も適格なタスクのメトリックを格納するのに使用される。
【０１８８】
スレッド要素
−メトリック：スケジューリングでのタスクの適格性に直接関わる情報またはスケジューラがそこから適格性を計算することのできる情報を伝えるのに使用される。
【０１８９】
［スケジューリング挙動］
スケジューリング操作は、以下の２つのサブカテゴリに分けられる。
−標準層スケジューリング、スケジューラ層内の１つ以上のエントリが、層内で最も適格なエントリと競い合う。
−プール配布スケジューリング、選ばれた処理リソースインスタンスのどれが割り込まれるべきか識別すること。
【０１９０】
スケジューリングイベントが受け取られない限りスケジューリングアクティビティは行われない。
【０１９１】
「スケジューリングプッシュおよびポップイベント」
前述のように、システム状態の変更は、「プッシュイベント」または「ポップイベント」を発生させることがある。すなわち、これらのイベントは、再スケジュールを発生させる。すべてのスケジューリング操作は処理保存的である。所与のイベントからおそらく影響を受けるはずのスケジューリング階層の部分だけが再評価され、これらを、再スケジューリング範囲内に存在するという。図１７に、基本スケジューリング階層上のイベントでの再スケジューリング範囲を示し、図１８に、単純な２インスタンス処理リソースプールでの再スケジューリング範囲を示す。
【０１９２】
「層スケジューリング」
層スケジューリングは、ＳｙｓｔｅｍＷｅａｖｅｒスケジューリングアルゴリズムの最も基本的な構成要素である。スケジューリングイベントは、ユーザ構成可能スケジューリング階層によって定義される連続した層スケジューリング操作を生じさせることができる。各層スケジューリング操作の結果は、親スケジューラ（スケジューリングノードまたはスケジューラルートノード）ＨｅａｄＩｎｄｅｘポインタの更新である。また、親スケジューラのメトリックも、定義されたメトリック伝搬アルゴリズムに従って更新され得る。
【０１９３】
原則として、層スケジューリングは、現在のＨｅａｄＩｎｄｅｘから開始し、スケジューラ層のメンバの周囲で反復して（実際には、待ち時間を最小限に抑えるために、プッシュ操作は、現在の先頭ポインタに対するスケジューリング決定を更新するだけである）、以下に従ってＨｅａｄＩｎｄｅｘへの更新が必要であるかどうか明らかにする。
−プッシュまたはポップ操作とすることのできるイベント
−イベントの種類（プッシュまたはポップ）に関連付けられたスケジューリングアルゴリズム
−層メンバのメトリック
【０１９４】
より適格なエントリが見つかった場合、ＨｅａｄＩｎｄｅｘはしかるべく更新される。スケジューリング操作の挙動を洗練させるいくつかの特殊な場合も認められる。いかなる場合にも、スケジューリング操作において休止スケジューラ層は無視される。
【０１９５】
常に、各スケジューリングノードは、主要なフィルパラメータが維持されるように、その子階層内に存在するスレッドまたはタスク記述子の数を知っていなければならない。しかしながら、必ずしも各層を常に完全にスケジュールする必要はなく、直近の下流再スケジュール操作がどこでスケジューリング決定更新を発生させているか識別するフラグが維持される。スケジューリング決定更新を発生させている場合、親層も完全に評価されなければならず、スケジューリング決定更新を発生させていない場合、残りの上流側スケジューラ階層をそれ以上再スケジュールする必要はない（但し、他のいくつかの状態更新が必要とされる）。
【０１９６】
任意の再スケジュールにおける最後の操作は、最も適格な作動可能タスクに、所与のＰＲＩ上で現在実行中のタスクに取って代わらせるべきかどうか決定することである。ディスパッチ待ち行列記述子は、スケジューリングアルゴリズムと現在実行中のタスクのメトリックの両方を含む。これらは、スケジューリングコーンからの最も適格なスレッドメトリックのコピーを含むスケジューラルートノードメトリックに対して評価され得る。
【０１９７】
「プール配布スケジューリング」
プール配布スケジューリングは、プール配布層内でのみ行われる。基本層スケジューリングは実行するのに最も適格なスレッド／タスク候補を見つけようとするが、プール配布スケジューリングは、優先使用に最も適格な処理リソースインスタンス候補を見つけようとする。通常、これは、リソースプールの最も適格性の低いタスクを実行中の処理リソースインスタンスを識別し、それと、接続されたスケジューリングコーンからの最も適格な「作動可能」タスクのメトリックとを比較することを意味する。
【０１９８】
最も適格な作動可能タスクが、すべての実行中のタスクよりも適格性の低いものである場合、すべてのスケジューリング層がそれぞれアクセス可能な下流タスクの総数を知ったままであるように、あらゆる接続処理リソースインスタンス上の残りの配布コーンが更新されるが、それ以上のスケジューリングは不要である。
【０１９９】
優先使用候補が識別される場合、スケジューリング更新は、その処理リソースインスタンスだけに向かって伝搬する。
【０２００】
図２０に、図１８に示すプッシュイベントの結果として発生する再スケジューリングでのシーケンス図を示す。基本層スケジューリング操作がプールルート層（層＃６）で行われ、続いてプール配布スケジューリング操作が行われる。この例では、ノード５が優先使用に適したものとして選択されたために、層＃１における層スケジューリング操作が実行される。後続のディスパッチ層スケジューリング操作は、接続された処理リソースインスタンスに対する優先使用を生じる。その後、その下流タスク／スレッドのカウントが維持されるように、層＃２も更新される。
【０２０１】
「協働および優先使用スケジューリング」
優先使用スケジューリングは、現在実行中のタスクが、より適格な（優先度の高い）タスクによって非同期的に割り込まれることを可能にする。優先使用は、実行側処理リソースおよびコンテキストのいくつかの要求、例えば、状態を格納し、優先使用タスクがそのリソースから出た後で再開できることなどを行う。通常、優先使用可能なタスクまたはスレッドは、作動可能状態および実行状態を通じて同じスケジューリング適格性を保持する。
【０２０２】
これに対して、協働スレッドは完了時にのみ取って代わられ、より優先度の高いタスクはそれを待たなければならない。ＳｙｓｔｅｍＷｅａｖｅｒタスク管理解決法において、協働スレッドは、それらが実行状態に入るときにその適格性が最大になり、それによって、より優先度の高いタスクの存在および潜在的にその結果として生じる優先使用を排除する。
【０２０３】
［メトリック伝搬挙動］
メトリック伝搬は、実行タスクまたはスレッドのメトリックにおけるスケジューリングイベントまたは変更によって引き起こされ得る。
【０２０４】
「スケジューリングイベントメトリック伝搬」
スケジューリングイベントの結果として親のスケジューリング層へのＨｅａｄＩｎｄｅｘが更新されるとき、親層における定義されたメトリック伝搬演算子に従って、メトリックが、最も適格な子メトリックから親メトリックに伝搬される。これらは、操作（プッシュまたはポップイベント）の性質に依存し、その複雑度の幅は単純なコピーから積和にまで及ぶ。
【０２０５】
「実行スレッドメトリック伝搬」
現在実行中のスレッドのメトリックは動的に変更されてもよい。これは、ロックされたリソース上での優先度逆転条件を除去するのに使用されてもよい。実行処理リソースインスタンスが配布コーンに関与していない場合、ディスパッチ待ち行列記述子メトリックのみが更新される。配布プールの場合、実行メトリックは、処理リソースインスタンスに関連付けられたプール静的ノードに伝搬される（図２１）。ＰＳＮメトリックの更新は、ＰＳＮ自体の内に保持されるメトリック伝搬演算子によって制御される。いくつかのスケジューリングシナリオでは、静的値がプール静的ノード内において永続的でなければならない。
【０２０６】
どちらの場合においても、新しい実行メトリックが、実行タスクおよび作動可能タスクの比較適格性に変更を生じないように、再スケジューリングイベントが促される。非プールの場合、これは、単に、新しい実行メトリックに関するスケジューラルートノードメトリックの再スケジュールにすぎない。プールされる場合、プール配布層およびすべての後続層は、再評価されなければならない。
【０２０７】
「アイドル処理」
処理リソースインスタンスは、アイドル状態に入るときに、実行メトリックを使ってスケジューリング構造を知らせる。本質的に、アイドル処理リソースインスタンスとは、可能な限り優先度の低いタスクを「実行している」ものであり、したがって、任意のタスクの到着によって取って代わられることになる。実行メトリックのアイドル値への設定は、通常の方法での再スケジューリングイベントを促し、それによって、作動可能状態構造においてこの処理リソースインスタンスを待ち受けるタスクによるアイドルタスクの「強制排除」を引き起こす。
【０２０８】
「アイドルタスク」およびそれが処理リソースプールにおける電源管理に及ぼす影響の詳細については、以下のプールシナリオにおける電源管理の項を参照されたい。
【０２０９】
［拡張スケジューリングモード］
いくつかの拡張モードおよび挙動が、固有に、またはいくつかのＳｙｓｔｅｍＷｅａｖｅｒ構成を用いることによって可能である。以下の項では以下の各モードを説明する。
【０２１０】
これはＳｙｓｔｅｍＷｅａｖｅｒ内で利用可能なスケジューリングモードの網羅的リストではないことに留意されたい。
【０２１１】
［タイムスライシング］
ＳｙｓｔｅｍＷｅａｖｅｒシステムは、主として、イベント駆動型であるが、タイムスライシングなど、従来のタイマベースのシステムが利用可能である。タイムスライスされたタスクは、タスクが処理リソースを占有してよい間隔を（この間隔の間に優先使用タスクが作動可能になることはないと仮定して）決定する個別のタイムスライス期間に従って処理リソースを共用する。
【０２１２】
タイムスライスされたタスクは、（図１に示す）通常のタスクに対してわずかに変更された「実行」挙動を呈する。図２２に、実行状態の２つの部分、通常状態および非推奨状態を示す。
【０２１３】
この項では、タイムスライスタスクの挙動を、それらを構成するときに遵守されねばならない規則と共に説明する。
【０２１４】
「ＳｙｓｔｅｍＷｅａｖｅｒコアリソース」
以下の項では、ＳｙｓｔｅｍＷｅａｖｅｒサーバコア内のタイムスライス機能を実施するのに使用されるリソースを論じる。
【０２１５】
カウンタ
ＳｙｓｔｅｍＷｅａｖｅｒコア内では、タイムスライス挙動を円滑化するために処理リソースインスタンスごとのカウンタが使用される。また、システムクロックによって供給される単一のプリスケーラも設けられる。プリスケーラのビット分解能は、チップ設計時に設定される。
【０２１６】
タイムスライス状況標識
処理リソースインスタンスごとの割り込み状況レジスタ内の状況ビットがタイムスライス挙動のために設けられる。この状況ビットは、タイムスライスカウンタの有効期限を登録し、ソフトウェアによって、タイムスライスイベントが発生しているかどうか決定するのに使用され得る。
【０２１７】
「構成」
タイムスライスグループ内のすべてのタスクは、同じ優先度および同じ親スケジューリング層を共用しなければならず、さらに、タイムスライスタスクは、他の非タイムスライスタスクとスケジューリング層を共用すべきではない。タイムスライス親のスケジューリングアルゴリズムは、ＦＩＦＯに設定されるべきである。図２３に、タイムスライスグループが、バックグラウンドにおいて、フォアグラウンドの、イベント駆動型タスクのグループと共に動作し、サービスを必要とするときに優先権を得る、典型的なタイムスライス構成を示す。
【０２１８】
「挙動」
タイムスライスタスクが最初に実行を開始するとき、システム規模のタイムスライス値が、処理リソースインスタンスに関連付けられたタイムスライスカウンタにコピーされる。タイムスライスタスクが、その「通常の」実行状態に入るという（図２４）。通常の状態において、各サイクルはこのカウンタを減分する。０に達すると、（ディスパッチ待ち行列記述子内に格納された）タスクの実行優先度がハードウェアによって自動的に減分され、タスクは、「非推奨」状態に入る。この時点において、タイムスライス間隔カウンタは、従来のウォッチドッグモードに切り換わる。
【０２１９】
いくつかのタイムスライスタスクにサービス提供する単一の処理リソースインスタンスの場合、（関連付けられた再スケジュール操作で）実行優先度を減分する動作は、作動可能状態構造内のタイムスライスグループの別のメンバによる優先使用を発生させる。タイムスライス状況ビットに問い合わせることによって、ソフトウェアクライアントは、タイムスライス期間が満了していると決定し、現在取って代わられているタスクをＦＩＦＯ待ち行列の後にプッシュすることができる。したがって、グループは、構成されたタイムスライス規則に従うと同時に、おおむね、ＳｙｓｔｅｍＷｅａｖｅｒコアスケジューリングおよびクライアント挙動の通常の動作モードを維持する。
【０２２０】
タイムスライスタスクが、「通常の」タイムスライス状態にある間に非タイムスライスタスクに取って代わられるとき、未完了のタイムスライス期間がタスク制御ブロックにコピーされる。次いで、タスクは、タイムスライスグループの、ＦＩＦＯ待ち行列の先頭のところにプッシュバックされる。任意の優先使用タスク処理が完了すると、タイムスライスタスクが、タイムスライスカウンタに再指定されている割り込まれたタスクの残りのタイムスライスを用いて再開される。
【０２２１】
タイムスライスタスクは、「非推奨」状態において割り込まれるとき、タイムスライスグループＦＩＦＯ待ち行列の末尾にプッシュバックされる。どちらの場合にも、タイムスライスタスクの優先度メトリックは、その最初に構成された値のままである。
【０２２２】
タイムスライスグループが、（優先使用タスクがないものと仮定して）処理リソースインスタンスのプールによってサービス提供される場合、「非推奨」状態に入ったからといって、必ずしも、別のタイムスライスグループメンバに即座の切り換かわるとは限らない。以下の所見に留意されたい。
Ｔｐ＝（ｔ＊ｄ）／ｐ（式中、１≦ｐ≦ｔ）
Ｔｒｅａｄｙ＝Ｔｐ−ｄ
Ｔｐ  （各メンバタスクを１度実行する）タイムスライスグループの完全なローテーションの期間。
Ｔｒｅａｄｙ  所与のタスクがその間作動可能状態で待機する１サイクル当たりの時間量。
ｔ  タイムスライスタスクの数
ｐ  プール内の処理リソースインスタンスの数
ｄ  各タイムスライス間隔の期間
【０２２３】
ｐ＝ｔのとき、他の任意の優先使用タスクがなければ、タイムスライスタスクは間断なく実行されることに留意されたい。
【０２２４】
「実行プロファイル」
以下の実行プロファイルは、ＳｙｓｔｅｍＷｅａｖｅｒタイムスライス挙動を示す。
【０２２５】
図２５に、単一のプロセッサと３つのタイムスライスタスクを用いる従来の場合を示す。これらのタスクは、それぞれ、優先使用タスクが、タイムスライスタスク（この場合には＃２）が取って代わられる時点に到達するまで、タイムスライス間隔に従って時分割する。優先度の高い優先使用タスクが完了すると、元のタイムスライスタスクが再開して割り込まれた間隔を完了する。
【０２２６】
図２６に、２つのプロセッサを用いる同じシナリオを示す。最初に、２つのプロセッサの間で３つのタイムスライスタスクが共用される。優先使用が到着すると、タイムスライスタスクは、残りのプロセッサを共用し、優先使用タスクが完了すると、２つのプロセッサでの実行を再開する。
【０２２７】
図２７に、利用可能な処理リソースの数がタイムスライスタスクの数と等しいときに、各タイムスライスタスクが、プロセッサの１つで間断なく実行されることを例示する。優先度の高いタスクがプロセッサの１つの制御権を獲得すると、タイムスライスグループは、定義されたタイムスライス間隔に従って残りのプロセッサを自動的に共用する。
【０２２８】
［プールシナリオにおける電源管理］
処理リソースプールのデフォルト挙動は、配布層内の第１のプール静的ノードからのスケジューリング決定を評価することである。プールルートノード（ＰＲＮ）は、通常、配布層内の第１のプール静的ノード（ＰＳＮ）を指し示す親ポインタを有する（図２８）。優先使用の候補を評価するとき、比較は、このエントリから開始し、ピアポインタを使ってリストの周りを進む。
【０２２９】
すべての静的ノードが同じ適格性のものであり、その適格性が、スケジューリングコーンからの候補より低い場合には、最初に遭遇したノードが選択される。したがって、プロセッサの１つ以上がアイドルである（そのメトリックをアイドル値に設定している）低負荷シナリオでは、ＰＲＮの親ポインタに最も近い処理リソースインスタンスが新しいタスクの処理に好都合であり、親ポインタから最も遠い処理リソースは、長いアイドル期間を呈することになる。
【０２３０】
この挙動は、処理リソースインスタンスまたはマクロアーキテクチャが電力消費を調整する（すなわち、クロックゲーティング、電圧／周波数変調、電源分離などによる）ができるときに有用である。これらの機能は、ソフトウェアクライアントシムに適切なドライバコードを付加することによって利用され得る。
【０２３１】
異なる節電対策は、処理リソースが再覚醒しなければならないときに、異なる影響を呈する傾向がある。例えば、クロックゲーティングは、マイクロアーキテクチャ内にすべての状態を維持し得るが、他方、積極的な電圧／周波数スケーリングは、すべての既存の状態を犠牲にし、再覚醒されるときに望ましくない突入電流を示すこともある。所与のＰＲＩが、前述のスケジューリング挙動と共に、異なるコストの多くの電源遮断オプションを有する場合、アイドル状態で費やされる時間に従ってそれらの利用法を管理することは理にかなっている。
【０２３２】
「アイドル」状態は、処理リソースインスタンスおよびシステムマクロアーキテクチャの機能に従って、複数の下位状態に分けることができる。いくつかの状態から再開することは、他の状態から再開するよりも高くつくことになる可能性が高い（例えば、クロックゲーティング電源遮断を保持する状態を、電源が分離された状態と対比されたい）。これらのシナリオをサポートするために、ＳｙｓｔｅｍＷｅａｖｅｒは、複数のアイドル優先度をサポートする。
【０２３３】
それらの複数の下位状態を有する処理リソースでは、割り込み応答は、スレッド実行が再開する前に徐々に遷移してアイドル状態に戻ることとしてもよい。これは、処理リソースの、所与の配布のアクティブセットへの漸進的再導入を可能にする。
【０２３４】
［例］
図２９に、昇順優先度を使ったアイドル状態における時間の経過に従った処理リソースインスタンス（ＰＲＩ）の「実行優先度」を示す。最初のインスタンスにおいて、アイドルタスクは、優先度を、その可能な限り低い設定に設定し、ＰＲＩに、スケジューラからのタスク割り当ての、その配布プールピアと比べて可能な限り高い機会を与える。
【０２３５】
その後、アイドルタスクは、おそらく、処理リソースマイクロアーキテクチャ内でサポートされる電源遮断モードを呼び出す。この時点において、アイドルタスクは、ＰＲＩの実行優先度を高めて、タスク割り当ての可能性を低下させる（前の状態のＰＲＩが優先する）。
【０２３６】
同様に、さらなる期間の後、アイドルタスク（または他の何らかのエージェント）は、実行優先度をさらに一層高める（おそらく、ＰＲＩへの電源を分離し、それによって静的漏れをなくする）。優先度の調節は、ＰＲＩのタスク割り振りでの適格性を、一層低い、この処理リソースを再覚醒させるコスト（この場合、突入電流、コールドキャッシュ効果など）に見合ったものにする。
【０２３７】
注意：配布層内の第１のエントリの優遇された優先使用は望ましくないこともある。これが該当する場合、前のスケジューリング決定が、後続のスケジューリング操作の新しい開始点になる、異なる挙動が選択されてもよい。この選択は、配布プール内の処理リソースインスタンスの間での優先度の高い優先使用タスクのより公平な配布を示す。
【０２３８】
［ヒステレシスベースのスケジューリング］
進行中の絶対的な正当性に関わり無く、スケジューリング決定を維持することが望ましい場合もある。一般に、これは、個々のタスククラスまたはデータセットのコンテキストを設定するコストが高く、したがって、許容される場合には、複数のタスクにわたって集約されるべき場合である。これが該当する場合には以下が含まれる。
−プロセッサキャッシュ−  履歴アルゴリズムまたはデータセットのためにデータが取り込まれているキャッシュメモリは、異種のアルゴリズムおよび／またはデータセットとの親和性が低い。これをコールドキャッシュ効果といい、高いキャッシュミス率、したがって、低い性能を示す。
−再構成可能なＦＰＧＡ区画−  部分的な実行時再構成可能性は、チップが配置され、動作する間に、ＦＰＧＡの一部が動的に再構成されることを可能にし、時間が経つにつれて異なるアルゴリズムの実行を可能にする。しかしながら、あるアルゴリズムから別のアルゴリズムに切り換わるコストは高く、システム効率を保証するためにより大きなデータセットにわたって集約されなければならない。
【０２３９】
これらは両方とも、高くつくコンテキスト切換えの例である。
【０２４０】
ヒステレシスベースのスケジューリングは、複数のユーザ動作にまたがってコンテキス切換えのコストを集約することによって、悪影響の一部を回避するのに使用されてもよい。メトリックの１つを使って「システムコスト」パラメータを表すことによって、ヒステレシスベースのスケジューリングを可能にすることができる。ヒステレシスメトリックは、以下のシステム内の多数のコスト尺度に基づくものとすることができる。
−タスクメモリ占有。メモリに余裕がない場合、所与のタスク待ち行列の蓄積されたフットプリントを使って、新しい構成をいつスケジュールすべきかが決定されてもよい。
−処理要件。実質的な「能動的処理」期間にわたるコンテキスト切換えのコストを集約することが望ましい場合。
−タイムスライス。待ち時間のジッタが重要である場合。
【０２４１】
例えば、動的に再構成可能なＦＰＧＡの場合、メモリが、再構成可能なファブリックの単一部分上で多重化されたアルゴリズムコンテキストのそれぞれについて作業を蓄積してもよい。この場合、メモリ占有を、いつ配列を再プログラムすべきか決定する際の要因とすることができる。いかなる場合にも、スケジューラ階層を、優先度の高いタスクの到着による強制切換えに対応するよう設計することが可能である。
【０２４２】
以下に、主要なシステムレベルの課題を要約する。
−コンテキスト切換えのコストの影響（切換えまでの時間、突入電流）
−切換えのタイミング
−所与のコンテキストが活動状態でない間にその作業の累積をどのようにして管理すべきか
【０２４３】
以下の各項では、ＳｙｓｔｅｍＷｅａｖｅｒを使って動的なＦＰＧＡ再構成を管理する可能な手法を説明する。コールドキャッシュの管理は、類似のスケジューリング技法およびより単純なソフトウェアクライアントシム挙動を使って実現され得る。
【０２４４】
「ＦＰＧＡ実行時再構成」
プロセッサコンテキスト切換えとの非常に強い相似性があるが、２、３の（再）定義が必要である。
構成−  ＦＰＧＡファブリックの所与の部分を対象とすることのできる様々なプログラムの組の１つ。
コンテキスト切換え−  ＦＰＧＡの再構成可能な部分の構成を変更する動作。
タスク−  所与のＦＰＧＡ構成によって実行される単一の作業単位。
【０２４５】
この提案では、ＦＰＧＡの再構成可能な部分を対象とする構成を（割り込み型とは異なり）協働的である、すなわち、個別タスクは不可分であり、コンテキスト切換えが行われる前に完了しなければならないものとみなされる。これは、タスクが再入可能である必要がないことを保証し、コンテキスト間の状態保存の問題を、個々の構成を待ち受けるタスクの数が整数値でなければならないという問題に限定する。図３０に、未完了タスクの管理の論理図を示す。
【０２４６】
タスクは待ち行列に編成される。これらの待ち行列は永続的に存在する。特に、これらの待ち行列は、現在活動状態でないＦＰＧＡ構成の作業を累積する。スケジューラは、いつタスクを切り換えるべきか決定し、タスクグループ内のタスクの実行順序を管理する。再構成サポート論理は、ファブリックを再プログラムし、それがいつ完了するかを知らせる仕組みを管理する。このモデルの協働的性質によれば、コンテキストがスケジュールされるときに、ファブリック内での保存を必要とするデータはない。
【０２４７】
スケジューラ
スケジューラは、以下の２つの異なる機能を実行する。
−スケジューラは、タスク待ち行列の変化する状態に従って現在のスケジューリング決定を評価する。
−スケジューラは、個別タスク待ち行列内のタスクの実行順序を管理する。
【０２４８】
あらゆるタスク到着が、ＦＰＧＡファブリックが常に正しい状態にあるように、スケジューリング決定の更新を引き起こす（貪欲なスケジューリング）。タスク待ち行列内では、スケジューラは、システム設計者によって定義される属性に従って実行順序を規定する。最低限でも、スケジューラは、ＦＩＦＯ、ラウンドロビンおよび優先度ポリシーを提供する必要がある。
【０２４９】
ＳｙｓｔｅｍＷｅａｖｅｒを使った再構成可能管理
ＳｙｓｔｅｍＷｅａｖｅｒ解決法は、実行時並列実行およびプロセス間通信を管理するために配置され得る、豊富なスケジューリングおよびプロセッサ間通信機能のセットを提供する。ＳｙｓｔｅｍＷｅａｖｅｒの機能は、同様に、従来の命令セットアーキテクチャ、固定ハードウェア要素および再構成可能なＦＰＧＡブロック内部のタスクおよびコンテキスト切換えを効率よく管理することができる。図３１にアーキテクチャの一例を示す。
【０２５０】
ＳｙｓｔｅｍＷｅａｖｅｒは、ＦＰＧＡファブリックコンテキスト切換えのスケジューリング管理および個別タスク待ち行列内のタスクの順序付けを処理する。当然ながら、これは、プラットフォーム内の固定構成要素への従来からのタスクのスケジューリングに加えて行われるものである。
【０２５１】
再構成自体は、個々のＳｙｓｔｅｍＷｅａｖｅｒハードウェアクライアントシムを用いて処理される。キャッシュの「暖かさ」を管理する類似のスケジューリング技法は、標準のクライアントシムにそれ以上の要件を課さないことに留意されたい。クライアントシムによって受け取られる各スケジュール済みタスク制御ブロックは、ファブリックの既存の構成と比較される。現在ロードされている構成とスケジュール済みタスクの構成が異なる場合、クライアントシムは、ＳｙｓｔｅｍＷｅａｖｅｒコアとそれ以上対話せずにファブリックを再構成する。その場合、ファブリック更新決定は、もっぱら、スケジューラによって指図される、タスクの出力順序付けの制御下に置かれる。クライアントシムは、異なる再構成戦略に対応するように再設計され得る。
【０２５２】
スケジューリングポリシー
スケジューリングポリシーは、システム設計者によって決定されるべきである。しかしながら、この機能をサポートするのに利用可能でなければならない重要な機能がある。特に、スケジューリングアルゴリズムが、ヒステレシスを示す、すなわち、代替の決定への切換えを保証するのに十分なコストがどこか他の場所に累積されるまであるスケジューリング決定を離れないことが可能である必要である。
【０２５３】
図示の例では、各「タスク」は、タスクグループを表す累積されたメトリックに追加されるランダムに生成されるメトリックを有する。所与のタスクグループが処理されるとき、待ち行列からタスクを除去する「ポップ」操作は、この累積カウントを減分する。
【０２５４】
「プッシュ」（新しいタスクの到着）または「ポップ」操作が発生すると、ファブリックスケジューラは、各候補を、現在実行中のタスクグループのメトリックに対して評価する。図３２に示すアルゴリズムによれば、
必要な更新＝（Ｃｃａｎｃｉｄａｔｅ＞Ｃｃｕｒｒｅｎｔ＋ヒステレシス）
Ｃｃａｎｃｉｄａｔｅ  候補スケジューリング層内のタスクの累積コスト
Ｃｃｕｒｒｅｎｔ  現在選択されているスケジューリング層内の未完了タスクの累積コスト
ヒステレシス−  コンテキストスラッシングを回避するために加えられるヒステレシス
【０２５５】
図３３に、前述のアルゴリズムを実施するために選択され得るスケジューリング階層を示す。この場合、「ヒステレシススケジューラ」のメトリック１は、ヒステレシスオペランドを格納する。メトリック０は、ヒステレシスグループの静的優先度を格納するのに使用されてもよく、この優先度は、ヒステレシスグループと優先使用グループの間でスケジュールするときに使用される。想定されているのは、コンテキスト変更を強制するのに十分な優先度のタスクがあるということである。
【０２５６】
結果
図３２に、このようなシステムの概念的影響を示す。タスクスケジューリング出力は、事実上、意図的にブロックごととされており、これは、システムトラフィック成形に対する影響を管理しながら、所与の任意の構成を最大限利用しようとするものである。
【０２５７】
図３４に、提示されるスケジューリングアルゴリズムのシミュレーションの結果を示す。４つの構成それぞれを待ち受けるタスクの累積「コスト」が、すべてのコスト（「累積」）の総計と共にグラフ化されている。選択トレースは、利用可能な構成のうちのどれがアルゴリズムによって選択されるかを示す。
【０２５８】
［複合スケジューリングアルゴリズムの例］
複合スケジューリング演算子は、例えば、プール配布層内の処理リソースプールをスケジュールするときになど役立つ。例えば、処理を待ち受けるタスクの待ち行列の中身がある一定の閾値を超えるときには、おそらく、メンバの一部だけが適格にはるはずである。
【０２５９】
３つの処理リソース、１つのＲＩＳＣプロセッサおよび２つのＤＳＰ（図３５）が利用可能な場合を考える。理論的には、３つのリソースのそれぞれが、音声符号化操作を実行することができるが、ＤＳＰデバイスの方がより効率がよい。この場合、図示のように、音声符号化プール内にＲＩＳＫプロセッサが存在するはずであるが、その実行に関与する適格性は、その機能を待ち受けるタスクの待ち行列の深さに依存するはずである。
【０２６０】
このような構成では、プールルートノードメトリック０は優先度を表し、メトリック１は待ち行列の中身を表していてもよい。候補ＰＳＮのそれぞれにおいて、メトリック０は、通常、それぞれの処理リソースインスタンス（ＰＲＩ）上で実行中のタスクの実行優先度を表す。この場合、メトリック１は、関連付けられたＰＲＩをスケジューリングに適格なものとするのに必要とされる待ち行列の中身を表す。この場合、複合スケジューリングアルゴリズムは以下の通りである。
必要な更新＝（MCURRENT0＞MCANDIDATE0）＆＆（MCURRENT1＞MCANDIDATE1）
【０２６１】
ＤＳＰデバイスと関連付けられたＰＳＮでは、Ｍ１は０に設定され、したがって、アルゴリズムは、純粋に、優先度に基づいて決定される。ＲＩＳＫプロセッサの場合、Ｍ１は非ゼロであり、したがって、ＲＩＳＫプロセッサがアルゴリズムの実行に関与するには、Ｍｃｕｒｒｅｎｔ１によって表される待ち行列の中身がこの値を上回る大きさに達していなければならない。
【０２６２】
以下では、マクロアーキテクチャまたはトランザクションレベルでのＳｙｓｔｅｍＷｅａｖｅｒサーバを説明する。
【０２６３】
前述のように、ＳｙｓｔｅｍＷｅａｖｅｒハードウェア解決法には以下の４つの要素がある。
−ＳｙｓｔｅｍＷｅａｖｅｒサーバコア
−ＳｙｓｔｅｍＷｅａｖｅｒ密結合メモリ
−ＳｙｓｔｅｍＷｅａｖｅｒデバッグマネージャ
−ＳｙｓｔｅｍＷｅａｖｅｒクライアントシム
【０２６４】
グローバルメトリックエージェントは、場合によって、システム設計がスケジューリング決定にシステムグローバル状態を含めることを必要とするときに使用される。
【０２６５】
［１次接続グループ］
図３８に、コア周辺で見られるインターフェースグループを示す。
【０２６６】
ＳｙｓｔｅｍＷｅａｖｅｒコアが容易に統合され得るようにするために、すべての信号は単方向であり、単一のクロックに同期する。以下にこれらのグループの構成メンバの詳細を示す。すべての信号方向は、ＳｙｓｔｅｍＷｅａｖｅｒコアとの関連で示す。
【０２６７】
［システム制御グループ］
システム制御グループは、ＳｙｓｔｅｍＷｅａｖｅｒコアの正しい動作を保証するのに必要な雑多な信号を含む。これらには、クロック、リアルタイムクロックおよびリセット信号が含まれる。
【０２６８】
［グローバルメトリックグループ］
システムによっては、スケジューリング決定時にいくつかのシステムメトリックが使用されることが望ましい。これらのメトリックは、相互接続使用度、キャッシュヒット率、メモリ占有度など、様々な要因を表し得る。
【０２６９】
［周辺割り込みグループ］
周辺割り込みグループは、ＳｙｓｔｅｍＷｅａｖｅｒ制御システム外部から供給される割り込みのグループからなる。周辺割り込みグループ内の信号は、例えば、外界との入力インターフェースから、あるいはピンを介してＳｏＣデバイス外部から直接駆動されてもよい。周辺割り込み入力の数は、ＳｏＣ設計時に定義される。
【０２７０】
［内部割り込みグループ］
内部グループは、ＳｙｓｔｅｍＷｅａｖｅｒシステムが発する同期割り込みの２つのグループと、実行時システムデバッグ信号の単一グループからなる。信号グループ内の各信号の数は、通常、システム内の処理リソースの数と一致し、ＳｏＣ設計時に定義される。
【０２７１】
［密結合メモリインターフェースグループ］
このグループは、ＳｙｓｔｅｍＷｅａｖｅｒを、独自の専用密結合メモリリソースにインターフェースする。接続メモリは、同期ＳＲＡＭデバイスであるものとする。アドレスパスの幅ｎおよびデータパスの幅ｍは、ＳｏＣ設計時に定義される。
【０２７２】
［相互接続グループ］
プロトコルおよびレイヤ数を含む個別相互接続戦略は、ＳｏＣ設計時に設定されなければならない。任意の所与のバスインターフェース信号の詳細は、対応するバス特有の実装で見ることができる。
【０２７３】
［デバッグインターフェースグループ］
デバッグマネージャへのインターフェースの詳細については、参照として本明細書に組み込まれる、同時係属の国際出願ＰＣＴ／ＧＢ２００５／００３５２５明細書を参照されたい。
【０２７４】
［密結合メモリ（ＴＣＭ）］
ＳｙｓｔｅｍＷｅａｖｅｒＴＣＭは、多数のＥＤＡベンダによって供給される標準コンパイラＳＳＲＡＭ技術である。ＴＣＭは、アプリケーションの必要に従ってＳｏＣ設計時に定義される整数個のＳｙｓｔｅｍＷｅａｖｅｒメモリ要素（ＷＭＥ）を含む。各ＷＭＥは２５６ビットのメモリ空間を消費する。ＳｙｓｔｅｍＷｅａｖｅｒは、最大で６５５３６ＷＭＥ、すなわち１６ＭＢのメモリをサポートする。
【０２７５】
待ち行列記述子はＷＭＥを消費するが、典型的なシステムでは、必要なＷＭＥの数は、スレッドサポート要件によって決まるはずである。例えば、ＳｙｓｔｅｍＷｅａｖｅｒサーバ内で同時に４００スレッドをサポートすることのできるシステムは、おおよそ、１２８ＫＢの接続メモリを必要とするはずである。
【０２７６】
ＳｏＣ設計時に、メモリインターフェースは、経路指定を簡略化するように変更され得る。
【０２７７】
［サーバコアサブブロック記述］
図３９に、ＳｙｓｔｅｍＷｅａｖｅｒサーバエンティティの主要な論理構成要素を示す。これらの機能は、図４０に示すアーキテクチャ上にマップされる。機能は、４つの１次内部並列処理要素の間で分けられ、以下の機能を実行する。
−スレッドスケジューラ入力マネージャ（ＴＳＩＭ）：フリーリスト維持、ＷＭＥ回復。
−スレッドスケジューラ保留マネージャ  （ＴＳＰＭ）：保留リスト維持、同期、作動可能待ち行列構造への格上げ。スレッド同期マネージャは、保留待ち行列構造の保全性を維持する（挿入および抽出）。
−スレッドスケジューラ出力マネージャ（ＴＳＯＭ）：作動可能待ち行列維持、ディスパッチ待ち行列維持、処理リソース電源管理、割り込み生成。作動可能待ち行列構造の保全性の維持（挿入および抽出）。
−スレッドスケジューラスケジュールマネージャ（ＴＳＳＭ）：作動可能待ち行列構造内の各処理リソースごとのスケジューリング決定の維持。
【０２７８】
さらに、いくつかのブロックが以下の機能をサポートする。
−スレッドスケジューラメモリマネージャ（ＴＳＭＭ）：相互排他およびロッキングを含む、接続されたＳｙｓｔｅｍＷｅａｖｅｒメモリへのアクセスを集約する。
−スレッドスケジューラ割り込みマネージャ（ＴＳＩＣ）：入ってくるシステム割り込みを内部同期プリミティブに変換する。
−スレッドスケジューラインターフェースマネージャ（ＴＳＩＦ）：相互接続インターフェースおよび構成およびＳｙｓｔｅｍＷｅａｖｅｒリソースへの実行時アクセスの提供。
【０２７９】
図４０に、ＳｙｓｔｅｍＷｅａｖｅｒアーキテクチャの基本サブブロックを示す。以下の各項では、これらの構成要素間でのサブブロック内対話を詳述する。各サブブロックは、他のサブブロックに１組の「共通メソッド」を提示し、それぞれがそのピアに、それぞれによって維持される構造に対する操作を実行することができるようにする。
【０２８０】
コマンドが個々の条件と共に完了し得る場合、サブブロック内で状況フラグが管理される。
【０２８１】
サブブロックインターフェース図上の矢印方向はバスの支配を示すものであり、信号グループの個別要素の方向に対する反映ではない。
【０２８２】
［ステートフル記述子挙動］
ＳｙｓｔｅｍＷｅａｖｅｒの動作時には多数の記述子型が使用される（詳細については、参照として本明細書に組み込まれる、同時係属の国際出願ＰＣＴ／ＧＢ２００５／００１１５４明細書を参照されたい）。これらの記述子の大部分は、ステートレスであるが、スレッド記述子およびスケジューラ記述子は、一定の状況下において多くの状態を経て遷移し得る。本明細書では、これらの状態遷移およびそれらを発生させるイベントを説明する。
【０２８３】
「スレッド記述子」
ＳｙｓｔｅｍＷｅａｖｅｒによって内部で認識される２種類のスレッド記述子があり、それらは標準スレッド記述子およびマーカスレッド記述子である。後者は、もっぱら、以前に待ち行列に入れられたスレッド記述子の保全性および順序付けを保証しながら、スケジューリング階層を除去するプロセスを同期させるのに使用される。
【０２８４】
図４１に、スレッド記述子とマーカスレッド記述子の両方がトラバースする内部スレッド状態図を示す。新規状態および空き状態は、ＳｙｓｔｅｍＷｅａｖｅｒ内の永続的状態と直接の相関を持たないメタ状態であることに留意されたい。スレッド記述子内にはリテラル状態変数が存在しないが、代わりに、この状態は、いくつかのフラグによって表される。表３に、フラグ状態と、図４１におけるスレッドが存在する状態の間の相関を示す。
【０２８５】
標準スレッド記述子状態記述
以下の各項では、状態、ならびにエントリおよびエントリの終了を生じさせるイベントの簡単な記述を示す。
【０２８６】
新規状態
新規状態は過渡的なものである。新しいスレッドは、プッシュ独立または従属スレッドコマンドによってＴＳＩＦに導入される。これら２つの場合は以下のように処理される。
−独立スレッド（時間または同期依存性のないスレッド）は、即座にプッシュ状態に遷移する。このインスタンスでは、ＴＳＩＦは、ＴＳＳＭに、スレッドを作動可能待ち行列構造に導入するよう命令する。
−従属スレッド（時間または同期依存性を有するスレッド）は、ブロック状態に遷移する。ＴＳＩＦは、ＴＳＰＭに、スレッドを、適宜、保留またはタイミング待ち行列構造に導入するよう命令する。
【０２８７】
ブロック状態
ブロック状態において、スレッド記述子は、外部同期および／またはタイミングベースの同期を待ち受ける。ブロックされたスレッドはＴＳＩＦから発せられる。適切な同期が受け取られたとき、ＴＳＰＭは、スレッドをプッシュ状態に遷移させ、ＴＳＳＭに、スレッドを作動可能待ち行列構造に導入するよう命令する。
【０２８８】
プッシュ状態
プッシュ状態のスレッドは、同期されており、あるいは、元々独立である場合には、ＴＳＰＭ（従属スレッド）およびＴＳＩＦ（独立スレッド）が、それぞれの場合にプッシュ状態への遷移を管理しているはずである。ＴＳＳＭは、スレッドを作動可能待ち行列構造にプッシュし、スレッドを作動可能状態に遷移させる。作動可能状態への遷移は、再スケジュールを発生させる。
【０２８９】
作動可能状態
作動可能状態のスレッドは、プッシュ状態から遷移したものであり、あるいは、（ＴＳＳＭによって）フラッシュされて作動可能待ち行列構造に戻されたものである。作動可能状態への遷移は、常に、再スケジュールを促す。スレッドは、作動可能状態から、ポップ状態またはフラッシュ状態に遷移することができ、後者は、ポップ状態を単一操作でフラッシュ状態にトラバースする特定の条件の結果として発生する。スレッドは、それらがＴＳＳＭによってスケジューリングに最も適格な候補として指定されたときにポップ状態に遷移する。
【０２９０】
ポップ状態
ポップ状態のスレッドは、個々の処理リソースインスタンスまたはインスタンスグループによる処理に最も適格なスレッドとしてスケジューラ（ＴＳＳＭ）によって指定されており、ＴＳＯＭによってこの状態に遷移される。スレッドは、以下のようにポップ状態からフラッシュ状態またはゾンビ状態に遷移することができる。
−スレッドは、再スケジュールの結果としてより適格なスレッドが識別されていることの結果として、ＴＳＯＭによってフラッシュ状態に遷移される。
−スレッドは、システム処理リソースインスタンスの１つにおける処理の開始の結果として、ＴＳＯＭによってゾンビ状態に遷移される。ゾンビ状態は、スレッド記述子を、それが解放され得るようになるまで維持する。
【０２９１】
ゾンビ
ゾンビスレッドは、ＴＳＳＭ内で処理される。ゾンビ状態の存在は、所与のスレッド記述子に関するすべての依存関係が、そのスレッドを解放する前に不要にされていることを保証するためのものである。これは、スレッドがＴＳＳＭ処理待ち行列の前部に到達した後で保証され、したがって、それ以上の処理を必要としない。
【０２９２】
フラッシュ状態
フラッシュスレッドは、ＴＳＳＭによって処理される。フラッシュスレッドは、作動可能待ち行列構造に再導入され、再スケジュール操作を発生させなければならない。これが完了すると、スレッドは、ＴＳＳＭによって遷移されて作動可能状態に戻される。
【０２９３】
空き状態
空き状態は、スレッド記述子によって消費されたＷＭＥがフリーリスト上に戻されることを示す過渡的状態である。
【０２９４】
マーカスレッド記述子状態記述
以下の各項に、状態、ならびにエントリおよびエントリの終了を生じさせるイベントの簡単な記述を示す。
【０２９５】
新規状態
新規状態は過渡的なものである。プッシュマーカスレッドコマンドによって新規のマーカスレッドがＴＳＩＦに導入される。マーカスレッドは、常に、ブロック状態をトラバースして、マーカスレッドが最終的に削除するスケジューラ層の状況に影響を及ぼし得るＴＳＰＭの入力および出力作業待ち行列内に存在する任意の処理が、マーカスレッド自体の到着前に完了されているようにする。
【０２９６】
ブロック状態
ＴＳＰＭは、即座に、マーカスレッドをプッシュ状態に遷移させ、ＴＳＳＭに、スレッドを作動可能待ち行列構造に導入するよう命令する。
【０２９７】
プッシュ状態
ＴＳＳＭは、マーカスレッドを作動可能待ち行列構造にプッシュし、スレッドを作動可能状態に遷移させる。作動可能状態への遷移は、再スケジュールを発生させる。
【０２９８】
作動可能状態
マーカスレッドは、作動可能待ち行列構造に導入されると、その直接の親をロック解除する。その場合、その親スケジューリング層の解放は、従属スレッド数のカウントの制御下にある。マーカスレッドは、それらの親の従属スレッドカウントがゼロに到達している、すなわち、ＳｙｓｔｅｍＷｅａｖｅｒ内に、親スケジューリング層の存在に依存するスレッド記述子がそれ以上ないときにのみ、作動可能状態から遷移するのに適する。
【０２９９】
標準スレッドと同様に、マーカスレッドは、作動可能状態から、ポップ状態またはフラッシュ状態に遷移することができ、後者は、単一動作でポップ状態をフラッシュ状態にトラバースする特定の状態の結果としてものである。マーカスレッドは、ＴＳＳＭによってスケジューリングに最も適格な候補であると指定されているときにポップ状態に遷移する。
【０３００】
ポップ状態
ポップ状態のマーカスレッドは、スケジューラ（ＴＳＳＭ）によって特定の処理リソースインスタンスまたはインスタンスグループによる処理に最も適格なスレッドであると指定されている。このスケジューリング決定は、スケジューリング層が空であり、それ以上従属スレッドが存在しないことを示す特殊な場合であることに留意されたい。マーカスレッドは、以下のように、ポップ状態からフラッシュ状態またはゾンビ状態に遷移することができる。
−マーカスレッドは、再スケジュールの結果としてより適格なスレッドが識別された結果として、フラッシュ状態に遷移される。
−マーカスレッドは、システム処理リソースインスタンスの１つにおける処理の開始の結果としてゾンビ状態に遷移される。ゾンビ状態は、解放され得るようになるまで、マーカスレッド記述子を維持する。さらに、マーカスレッドの親も、この状態にある間に、削除のためにマークされる。
【０３０１】
ゾンビ状態
ゾンビマーカスレッドの処理は、通常のスレッド記述子の処理と類似している。また、マーカスレッドの親スケジューリング層も、この状態内で削除される。
【０３０２】
空き状態
空き状態は、スレッド記述子によって消費されたＷＭＤがフリーリストに戻されることを示す過渡的状態である。
【０３０３】
「スケジューラ層状態図」
また、スケジューラ層も、暗黙的状態を有する。静的な層、すなわち、システムの実行時全体を通じて永続的である層では、唯一の状態が活動状態である。残りの状態は、動的スケジューリング層、すなわち、実行時に出入りする層によって使用される。表４に、フラグ状態と、図４２にスケジューラ層が存在する状態の間の相関を示す。
【０３０４】
スケジューラ層記述子状態記述
以下の項では、状態、ならびにエントリおよびエントリの終了を生じさせるイベントの簡単な記述を示す。
【０３０５】
新規状態
新規状態は過渡的なものである。初期設定時または実行時に、新規のスケジューラ層がプッシュ独立要素によってＴＳＩＦに導入される。
【０３０６】
休止状態
休止状態において、スケジューラ層は、スレッドおよび潜在的に追加の子階層を累積することを許されるが、ＴＳＳＭによってスケジュールされることは決してない。休止状態には以下の２つの方法で入ることがある。
−休止状態で新しいスケジューリング記述子が作成されることがある。
−スケジューリング層が実行時に変更され、ＴＳＩＦを介して発行された明示的システムコマンドによって休止状態に置かれることがある。
【０３０７】
休止状態は、明示的システムコマンドによってのみ終了され得る。
【０３０８】
活動状態
活動状態のスケジューラ層は、能動的にスケジューリングに関与し、ロックされる。すなわち、活動状態のスケジューラ層は、空になったときに除去されない。静的スケジューラは、通常、この状態で作成される。動的スケジューラは、ＴＳＩＦを介して受け取られる明示的システムコマンドによってこの状態に遷移する。スケジューラ層は、マーカスレッドが受け取られるときにのみ活動状態を終了し、そこで「保留空き」状態に入る。
【０３０９】
保留空き状態
スケジューラ層は、以下の基準が両方とも満たされるまで保留空き状態に留まる。
−この層を参照する記述子の数の尺度を保持するカウントである、従属要素の数が０になる。
−子要素の数がゼロになる。
【０３１０】
これは、保留空き状態への遷移を引き起こしたマーカスレッド記述子もポップされていることを示唆し、スケジューラ層がそれ以上の依存関係を持たないときにのみ発生する動作であることに留意されたい。
【０３１１】
空き状態
空き状態は、スケジューリング層記述子によって消費されたＷＭＥがフリーリスト上に戻されることを示す過渡的状態である。
【０３１２】
［サブブロック間挙動］
以下の項では、複数のサブブロックが関与するＳｙｓｔｅｍＷｅａｖｅｒ挙動の態様をカバーする。
【０３１３】
「動的スケジューリング階層操作」
システム実行時にスケジューリング階層を追加し、除去することができる。いくつかのユーザレベル手順が守られる場合、ＳｙｓｔｅｍＷｅａｖｅｒは、システムの保全性、および、スケジューリング階層のある部分から別の部分に遷移するスレッド記述子の順序付けを保証する。詳細については、上記を参照されたい。
【０３１４】
「動的スケジューリングメトリック更新」
標準またはマーカスレッド内のメトリックを更新することができる。挙動は、以下のようにスレッド状態に依存する。
−スレッドがブロック状態にある場合、適切なコマンドがＴＳＰＭに送られる。保留待ち行列はソートされるため、スレッドは、適切な時点において再度出現するようにメトリックが更新されるときに待ち行列から除去され、再挿入される。
−スレッドが別の任意の永続的状態にある場合、メトリック更新を実行し、スケジューリング階層の適切な部分を再スケジュールするコマンドが、ＴＳＳＭに発行される。
【０３１５】
「スケジューリングのためのＴＳＯＭ／ＴＳＳＭ対話」
処理リソースインスタンスに対するスレッド記述子のスケジューリングでは、ＴＳＯＭとＴＳＳＭの両方が機能を果たす。ＴＳＯＭとＴＳＳＭの間の対話のいくつかのシーケンス図の例を図７２および７３に示す。
【０３１６】
［サブブロック内アーキテクチャおよび挙動］
各サブブロックは、その１次入出力、またはそのピアおよび外界への物理インターフェースの観点から、また、そのコマンドインターフェース、または適切な物理インターフェースを介してコマンドプロトコルを使って呼び出され得るメソッドの観点から論じられる。
【０３１７】
［ＴＳＩＦ  インターフェースマネージャ］
インターフェースマネージャは、相互接続グループから受け取られるコマンドの実行を調整し、それらを他のサブブロックに配布する役割を果たす。
【０３１８】
以下の項では、ＴＳＩＦ内に存在し、内部消費のためのコマンドの単なる変換の範囲を超える機能エンティティを説明する。
【０３１９】
「アーキテクチャ」
ＴＳＩＦは、主に、相互接続インターフェースを介して受け取られるコマンドを解釈して、残りのサブブロックに対する１つまたは多くの内部コマンドにする。以下の各項では、ＴＳＩＦ内に存在するアーキテクチャリソースの詳細を示す。
【０３２０】
セマフォ領域ロック
セマフォ領域ロック（ＳＲＬ）は、システムリソースへの排他アクセスを得るために任意のシステムリソースによって原子的に試験され、ロックされ得るリソースを提供する。セマフォ領域ロックは、以下の任意の数の理由で使用され得る
−１つ以上の共用リソース（例えば、セマフォオブジェクト、タスク制御オブジェクトなど）を含むシステムメモリの領域をロックし、それによって保全性を保証するため。
−マルチサイクルコマンドアクセスのためのＳｙｓｔｅｍＷｅａｖｅｒコマンドインターフェースをロックするため。
−マルチサイクルイベントのためのＳｙｓｔｅｍＷｅａｖｅｒデバッグイベントインターフェースをロックするため。
【０３２１】
ＳＲＬは、ロックされた状態とロック解除された状態の２つの状態を有する。ＳＲＬからの読出しは、ロックを得ようとする試行として定義され、ＳＲＬへの書込みは、ロック解除しようとする試行として定義される。個々のＳＲＬをロックする処理リソースインスタンスと、個々のＳＲＬを解除する処理リソースインスタンスの間に必要な相関はない。その挙動を以下で説明する。
−ロック解除状態：ロック解除状態では、ＳＲＬからの読出しが、読取装置に、ロック試行が成功したかどうか示す制御コードを返す。この状態では書込みは影響を及ぼさない。
−ロック状態：ロック状態では、ＳＲＬからの読出しが、ＳＲＬが利用できないことを示す。書込みはＳＲＬを解放する。
【０３２２】
コマンド処理
ＴＳＩＦは、システム相互接続から受け取られるコマンドを、おそらく、複数の内部コマンドに分解する。
【０３２３】
ウォッチドッグおよびタイムスライスサポート
各処理リソースインスタンスごとに、場合によって、デュアルモードタイマカウンタが設けられる。２つのタイマモードは、ウォッチドッグとタイムスライスであり、デフォルトモードはウォッチドッグである。
【０３２４】
ウォッチドッグ挙動は、ウォッチドッグサイクルおよび個別カウントによって定義される（図４４）。ウォッチドッグサイクルは、システムクロックの降圧バージョンであり、降圧は、シリコン設計時にシステム定数によって定義される。図４６（ａ）に、各プレスケールウォッチドッグクロックサイクルごとの、各処理リソースインスタンスごとの挙動を示す。
−ウォッチドッグ割り込みが適切であるかどうか決定するために個別ウォッチドッグカウンタに問い合わせが行われる。
−必要な場合、ウォッチドッグ割り込みが生成される。
【０３２５】
ウォッチドッグタイマカウントは、タイマが関連する処理リソースインスタンスからの各制御アクセスごとにリセットされ、したがって、そのウォッチドッグ間隔の間にＳｙｓｔｅｍＷｅａｖｅｒにアクセスしない処理リソースのみがウォッチドッグ割り込みを受ける。
【０３２６】
前述のタイムスライシング挙動は、ＴＳＩＦとＴＳＯＭの間で区切られる。ＴＳＩＦでは、各処理リソースに割り振られるタイマは、タイムスライスサポート専用とすることができる。タイムスライス割り込みが発生すると、ＴＳＯＭにおいて自動化メトリック操作が提供される（実行優先度が減分される）。処理リソース自体は、自動化メトリック更新の結果として、標準の優先使用が適切になった場合にのみ取って代わられる。
【０３２７】
図４５に、ＴＳＩＦ内のタイムスライスサポート論理のシステムごとクロックサイクル挙動を示す。図４６（ｂ）に、プレスケールタイムスライスクロックの各サイクルごとの、各処理リソースごとの挙動を示す。タイムスライスイベントが発生した後、タイマモードがウォッチドッグモードに戻されることに留意されたい。
【０３２８】
割り込み処理
ＳｙｓｔｅｍＷｅａｖｅｒは、システムからの割り込み、すなわち周辺割り込みを受け入れ、システムへの割り込み、すなわち処理リソースインスタンス割り込みを供給する。
【０３２９】
周辺割り込み
周辺割り込みは、ＴＳＩＦ内でマスクされ、調整されてもよい（エッジ／レベルトリガ、負／正論理など）。
【０３３０】
処理リソースインスタンス割り込み
以下の機能を提供するために、ＴＳＩＦ内に割り込み処理リソースが設けられる。
−割り込み表明のソースを含む、割り込み状況を維持する（優先使用、タイムスライス、ウォッチドッグ）
−マスク機能
【０３３１】
ＴＳＩＦ内では、ＳｙｓｔｅｍＷｅａｖｅｒコマンドインターフェース上での割り込みマスキングを自動化するための特別な機能が実装される。コマンドインターフェースはシステム内のすべての処理リソースに共通のアクセス点であるため、保全性および効率性が維持されなければならない。このために、ＳｙｓｔｅｍＷｅａｖｅｒは、処理リソースがＳｙｓｔｅｍＷｅａｖｅｒコマンドインターフェース上でのロックを獲得すると、その処理リソースがこの重要なコード部分の間に割り込みされないように、割り込みマスキングを自動的に処理する。
【０３３２】
各処理リソースインスタンスごとに、受け取られている正常なＳｙｓｔｅｍＷｅａｖｅｒコマンドインターフェースセマフォ領域ロック要求の数を追跡するカウンタが維持される。各ロック要求はカウントを増分し、各ロック解除要求はカウントを減分する。カウンタがゼロから増分されると、割り込みが自動的にマスクされ、カウントがゼロに減分されると、割り込みが自動的にアンマスクされる。
【０３３３】
［ＴＳＩＭ  入力マネージャ］
入力マネージャは、ＷＭＥフリーリストを助けて、ＴＳＩＦからのポップ要求および多くのサブブロック（ＴＳＩＦ、ＴＳＰＭ、ＴＳＯＭ、ＴＳＳＭ）からのプッシュ要求を処理する。
【０３３４】
「アーキテクチャ」
ＴＳＩＭはただ１つのアーキテクチャエンティティ、ＳｙｓｔｅｍＷｅａｖｅｒメモリ要素（ＷＭＥ）フリーリストを含む。図４８に、このリストの構造を示す。
【０３３５】
フリーリストは、後入れ先出し（ＬＩＦＯ）ポリシーに従って動作する。リストのあらゆるメンバがＣ＿ＳＣＨＥＤ＿ＥＮＴＲＹ＿ＦＲＥＥ型のものであり、Ｃ＿ＦＲＥＥ＿ＱＵＥＵＥ＿ＰＯＩＮＴＥＲ＿ＩＮＤＥＸによって参照されるポインタを使って個々にリンクされる。
【０３３６】
「メソッドインターフェース」
基本リンクリストハウスキーピングメソッド（状況の取得および設定）と共に、入力マネージャは、そのインターフェース上で以下のコマンドを提示する。
【０３３７】
プッシュフリーインデックス（Ｃ＿ＴＳＩＭ＿ＣＭＤ＿ＰＵＳＨ＿ＩＮＤＥＸ）呼び出し元：（ＴＳＩＦ、ＴＳＳＭ、ＴＳＯＭ、ＴＳＰＭ）
プッシュフリーインデックスコマンドは、解放されたＷＭＥインデックスをフリーリスト上にプッシュバックするのに使用される。その引数を以下に要約する。
【表３】
0005386572.tif 000004
【０３３８】
ポップフリーインデックス（Ｃ＿ＴＳＩＭ＿ＣＭＤ＿ＰＯＰ＿ＩＮＤＥＸ）呼び出し元：ＴＳＩＦ
ポップフリーインデックスコマンドは、フリーリストから空きＷＭＥインデックスをポップするのに使用される。その引数を以下に要約する。
【表４】
0005386572.tif 000005
【０３３９】
［ＴＳＰＭ  保留マネージャ］
保留マネージャは、同期またはタイマベースの、何らかのイベントを保留にしているブロック状態のタスクまたはスレッド記述子を助ける。個別保留リストのアソシエーションは、ユーザ制御下（またはより上位層のソフトウェアの制御下）にあり、セマフォ、競合ドメイン、割り込みまたはこれらの任意の組み合わせを表し得る。
【０３４０】
「アーキテクチャ」
保留マネージャは、２つの主要要素、可変数の保留待ち行列および１つのタイマ待ち行列を備える。保留待ち行列は、何らかの外部イベントによる同期を待ち受けるスレッドのリストを格納し、タイマ待ち行列は、タイムアウトを待ち受けるスレッドのリストを格納する。スレッド記述子が両方のリストのメンバであることが可能であり、実際には一般的であり、そのため、スレッド記述子には、外部同期イベントを、限られた長さの時間にわたって待ち受けることが許容される。
【０３４１】
保留待ち行列構造
図５０の保留待ち行列構造は、その内容を処理するＴＳＰＭ内のリソースおよび機能と共に、主に、密結合メモリ内でインスタンス化される。ＴＳＰＭ自体は、先頭ポインタ、および保留待ち行列記述子のリスト、すなわち、リストのリストを参照するいくつかの要素を含む。各保留待ち行列はスレッド記述子のリストを含み、保留待ち行列の数は、実行時に動的に増減し得る。保留待ち行列には（スレッドが定義されたタイムアウトを有する場合にのみ現れるタイマ待ち行列と異なり）ブロック状態のすべてのスレッド記述子が存在する。複数の保留待ち行列の使用は、アプリケーションおよびアプリケーションプログラマの必要と好みに依存する。保留待ち行列は、特に、以下と関連付けられ得る。
−セマフォ。これは、それぞれスレッドをほとんど含まない多数の保留待ち行列を生じる可能性が高い。したがって、最悪の場合の同期応答時間は、これらの状況下では低くなる。
−競合ドメイン。競合ドメインは、同じリソースを求めて競合する複数のエンティティ内のゾーンである。例えば、（スレッドに対して）プロセスが競合ドメインとみなされ得る。
−割り込み。最速の応答時間のために、割り込みは、通常、専用保留待ち行列に集められる。
【０３４２】
タイマ待ち行列と異なり、保留待ち行列は、純粋に、イベントベースのものである。これらのイベントとは以下のものである。
−プッシュイベント。新しいスレッドが、すでに存在し、または作成されなければならない保留待ち行列に導入される。
−同期イベント。１つ以上のスレッドが作動可能待ち行列構造に遷移しなければならない。
【０３４３】
以下の各項では、これらの状況下での挙動を説明する。
【０３４４】
プッシュイベント
プッシュイベント時に、ＴＳＰＭは、（識別されたソート演算子ｍｅｔｒｉｃ［０］に従って）スレッド記述子をリスト中のどこに挿入すべきか決定しなければならない。考慮されなければならない以下の２つの状況がある。
−既存の保留待ち行列へのプッシュ
−新しい保留待ち行列へのプッシュ
【０３４５】
前者の場合は単純であり、リストは、挿入点が見つかるまで順番に問い合わせされる。従来の昇順優先度の場合、ソート演算子は、（Ｃ＿ＰＥＮＤ＿ＭＮＧＲ＿ＰＵＳＨ＿ＧＴＲ）「より大きい」に設定され、既存のリストがサーチされる。挿入点は、新しいスレッドのｍｅｔｒｉｃ［０］が次のリストメンバｍｅｔｒｉｃ［０］より大きいときの点によって定義される。
【０３４６】
新しい保留待ち行列が必要とされるとき、その保留待ち行列挿入は、新しいスレッドエントリの挿入の直前に行われる。
【０３４７】
同期イベント
同期イベントは、割り込みコントローラ（ＴＳＩＣ）から、またはコマンドインターフェースを介して受け取られ得る。同期は、以下の２つのモードで行われ得る。
−リテラルモード。コマンド引数がＷＭＥインデックスへのリテラル参照を行う。
−相関モード。スレッド記述子内のフィールドと同期プリミティブ内のフィールドの間の相関が求められる。
【０３４８】
リテラルモードでは、スレッド記述子のインデックスがコマンドに渡されるため、最も適格な候補に必要とされるサーチはない。相関モードは、最も適格な（１つ以上の）同期候補が最初に見つかることを必要とする。
【０３４９】
相関モードは、以下の３つのサブタイプからなる。
−通常。指定された保留待ち行列内の最も適格な候補だけが同期される。
−マルチキャスト。指定された保留待ち行列内のすべての適格な候補が同期される。
−ブロードキャスト。すべての保留待ち行列内のすべての適格な候補が同期される。
【０３５０】
最も適格な候補は、コマンドおよびやはりコマンド内の要素識別子と共に渡される引数によって識別される。要素識別子は、適格性を識別するために、候補スレッド記述子のフィールドのどれが渡された引数に比較されるか決定する。通常モードでは、アルゴリズムは、適格な候補が見つかるまで保留待ち行列を上から下へ反復し、見つかった時点において、適格な候補が保留リストおよび、該当する場合には、タイマ待ち行列から取り除かれ、作動可能待ち行列構造に送られる。マルチキャストおよびブロードキャストモードでは、このプロセスが、その保留待ち行列または各保留待ち行列がそれぞれ空になるまで続く。
【０３５１】
タイマ待ち行列のメンバの除去には特別な条件が関連付けられる。詳細については次項を参照されたい。
【０３５２】
タイミング待ち行列構造および操作
タイムアウト待ち行列に導入される各新しいスレッドは、最初に、絶対タイムアウト値を含んでいる。この値は、インターフェースマネージャによって、引数として受け取られる３２ビット相対または絶対タイムアウトから導出されていてもよい。
【０３５３】
タイマ待ち行列は、Ｃ＿ＴＨＲＥＡＤ＿ＰＥＮＤＩＮＧ＿ＱＵＥＵＥ＿ＴＩＭＥＲ＿ＰＴＲ＿ＩＮＤＥＸを使って、スレッド記述子のリストを、最も近いタイムアウトをリストの先頭にして、それらのタイムアウトの順に格納する。これらのスレッド記述子は、Ｃ＿ＴＨＲＥＡＤ＿ＰＥＮＤＩＮＧ＿ＱＵＥＵＥ＿ＰＲＩＯＲＩＴＹ＿ＰＴＲ＿ＩＮＤＥＸによって索引付けされる第２のポインタセットによって、優先度リストのメンバにもなることに留意されたい。図５１に、タイムアウト待ち行列の基本構造を示す。タイマ待ち行列の個別スレッド記述子メンバ内の絶対タイムアウト値を格納するのではなく、直前のスレッド記述子のタイムアウトに対するタイムアウトが格納される。この値は、浮動小数点表現を使って１６ビットフィールド内に格納され、浮動小数点タイマ形式の仮数は、５ビットの指数を有する無名数の１１の有効ビットを含む。タイマ待ち行列の先頭要素のタイムアウトフィールドは、常に、ＴＳＰＭＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔレジスタにコピーされ、その後リセットされる。
【０３５４】
タイミング同期アーキテクチャの動作は、以下のいくつかの永続的内部リソースを使用する。
−ＴｉｍｅｒＨｅａｄＩｎｄｅｘ。タイマリストを指し示す先頭ポインタ
−ＴｉｍｅｒＮｕｍＥｌｅｍｅｎｔｓ。タイマ待ち行列内の要素数
−ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔ。先頭要素のタイムアウトのスナップショット
−ＴｉｍｅｒＤｉｖｉｄｅｒ。システムクロックのプリスケーラ
−ＴｉｍｅｒＤｉｖｉｄｅｒｃｏｕｎｔｅｒ。除算器のカウントダウンリソース
−ＴｉｍｅｒＣｏｕｎｔｅｒ。各プレスケールクロックティックごとに単調に増加し続ける３２ビットカウンタリソース
−ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒ。エラーを累積し、収容するのに使用される３２ビットカウンタ
【０３５５】
ＴｉｍｅｒＤｉｖｉｄｅｒレジスタが０に設定される場合、タイマ機能は使用不可とされる。
【０３５６】
タイマ待ち行列サイクル挙動
図５２に、各プレスケールクロックティックごとに行われる操作を示す。ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔは、保留タイマベースの同期がない（タイマ待ち行列が待機状態にある）ときには非ゼロであり、したがって、どんな処置も行われない。ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔが０になり、タイマ待ち行列が空でないときに、システムは、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒの値に従って２つの状態の一方を採用する。ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒが０である場合、このサイクルでＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔの失効が発生しており、最終的にはタイマ待ち行列（および、ハウスキーピングのためには優先度待ち行列）からのポップを生じさせるタイマ同期プリミティブが作成される。その直後に、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒは、それが、タイムイベントプリミティブの処理が完了した後でリセットされるまで、単調に増分され続ける。
【０３５７】
タイマ待ち行列イベント
タイマ待ち行列操作を引き起こす以下の３つのイベントがある。
−タイムイベントプリミティブ（Ｃ＿ＴＳＰＭ＿ＣＭＤ＿ＴＩＭＥ＿ＰＲＩＭＩＴＩＶＥ）
−非ゼロタイムアウトを用いるスレッドプッシュイベント（ゼロに設定されたタイムアウトを有するスレッドはタイマ待ち行列に入れられない）
−結果としてハウスキーピング実行としてのタイマ待ち行列からのスレッドの除去を生じる非タイマベースの同期イベント
【０３５８】
図５３に、タイムアウト論理の動作モードの非常に基本的な表現を示す。待機状態にあるとき、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔは非ゼロであり、プレスケールクロックに従って単調に減分する。ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒは、この状態ではゼロに維持される。ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔが０に達すると、タイマ待ち行列の先頭はタイムアウトしており、ＦＳＭは活動状態に遷移し、そこでポップ操作が処理される。この状態内では、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔはゼロであり、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒは、各サイクルごとに単調に増分する。このエラーカウントを使って、前のタイムアウトイベントを実行するのに費やされた時間が後続のタイムアウトイベントを適格にしているかどうかが判定される。次の未完了の適格なタイムアウトイベントがなくなると、ＦＳＭは遷移して待機状態に戻り、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒがリセットされる。
【０３５９】
タイマ導出ポップ操作の潜在的シーケンスの最初のものが、スレッド記述子内のリセットタイムアウトフィールドから推論される（図５２参照）。タイマ待ち行列の先頭として、このスレッドが常にポップされる。その後、ＴＳＰＭは、後続のポップが適格であるかどうか評価して、この追加リソースＴｉｍｅｒＬａｓｔＥｒｒｏｒが、累積されたポップスレッド記述子タイムアウトデルタの合計を維持するのに使用されるのを容易にしなければならない。タイマ待ち行列の後続メンバの次の反復の都度、ＴｉｍｅｒＬａｓｔＥｒｒｏｒがＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒから差し引かれ、タイマ待ち行列先頭のところの新しいスレッド記述子のタイムアウトと比較される、正規化エラーカウントを生成する。このスレッド内のタイムアウトデルタが正規化エラーカウントより小さい場合、このスレッド記述子もポップされるべきである。最初、ＴｉｍｅｒＬａｓｔＥｒｒｏｒはゼロであり、したがって、スレッドタイムアウトデルタは、直接、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒに対して比較される。図５４に、スレッド１タイムアウトが経過し、関連付けられたポップ操作が行われた後の前のタイマ待ち行列構造を示す。ＴｉｍｅｒＬａｓｔＥｒｒｏｒは、スレッド２デルタによって更新されており、スレッド１ポップ操作の期間は、今やスレッド２も適格であることを意味することに留意されたい。
【０３６０】
図５５に、スレッド２のポップ後の待ち行列の状態を示す。スレッド２デルタがＴｉｍｅｒＬａｓｔＥｒｒｏｒに加算され、スレッド記述子デルタの合計の実行累積を生成していることに留意されたい。また、スレッド２に対するポップ操作は、スレッド３が適格になるのに十分な長さの時間を要したことにも留意されたい。
【０３６１】
図５６に、スレッド３のポップ後の状態を示す。この場合、後続のスレッド、スレッド４はポップに適格ではなく、そのため、タイマ待ち行列の状態は、待機に戻ってもよい。ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔは図示のようにリセットされなければならない。
【０３６２】
活動状態から遷移して待機状態に戻るとき、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔは正しくリセットされなければならないことに留意されたい。これは、新しいタイミング待ち行列先頭のデルタからＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒとＴｉｍｅｒＬａｓｔＥｒｒｏｒの差を差し引くことによって達成される。
【０３６３】
新しいスレッドがタイミング待ち行列に導入され、またはプッシュされるときには、２つの場合、すなわち、タイミング待ち行列の先頭へのプッシュと本体へのプッシュが考慮されなければならない。
−先頭へのプッシュでは、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔは、単に、スレッドデルタに設定される。待ち行列が空でない場合、旧い先頭記述子デルタは、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔマイナス新しいスレッドデルタに設定される。
−本体へのプッシュでは、タイマ待ち行列ブロックは、タイマリストをウォークして、スレッド記述子をどこに挿入すべきか識別しなければならない。次いで、リストの次のデルタが、新しいスレッドのデルタの追加を受け入れるように調整される（新しいスレッドデルタが次のスレッドデルタから差し引かれる）。
【０３６４】
ポップ操作
ポップ操作は、タイマの結果であれ、外部イベント同期イベントの結果であれ、同様に処理される。ポップされるスレッドがタイマ待ち行列の先頭にある場合とそうでない場合の２つ場合を考察すべきである。前者の場合には、タイマ待ち行列が待機状態にある場合と、タイマ待ち行列が活動状態にある場合の３つのシナリオがある。
−「待機中」のタイマ待ち行列の先頭からのポップ操作では、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔが、タイマ待ち行列の次のメンバのタイマデルタに加算されて新しいＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔを形成する（タイマベースのポップでは、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔの値は、常ＮＨＴＳＡに、ゼロになることに留意されたい）。
−「活動状態」のタイマ待ち行列の先頭からのポップ操作で、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒが次のスレッド記述子のデルタより大きい、すなわち、次のスレッドがタイマベースの同期に適格である場合、エラーカウンタ、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒは、ポップされるスレッドのデルタにリベースされる。
−「活動状態」のタイマ待ち行列の先頭からのポップ操作で、ＴｉｍｅｒＥｒｒｏｒＡｄｊｕｓｔＣｏｕｎｔｅｒが次のスレッド記述子のデルタ以下である、すなわち、次のスレッドがタイマベースの同期に適格ではない場合、デルタは、エラーカウンタによって減分され、ＴｉｍｅｒＨｅａｄＴｉｍｅｏｕｔが結果で更新される。タイマ待ち行列は、事実上、待機状態に戻る。
【０３６５】
ポップされたスレッド記述子がタイマリストの先頭でない場合、タイマ待ち行列の次のスレッドのデルタが、現在除去されているスレッド内のデルタ分増分されなければならない。
【０３６６】
「メソッドインターフェース」
保留およびタイマ待ち行列の基本リンクリスト状況操作（取得および設定状況）と共に、保留マネージャは、そのインターフェース上で以下のコマンドを提示する。
【０３６７】
同期プリミティブ（Ｃ＿ＴＳＰＭ＿ＣＭＤ＿ＳＹＮＣ＿ＰＲＩＭＩＴＩＶＥ）呼び出し元：ＴＳＩＦ、ＴＳＩＣ
同期プリミティブコマンドは、保留待ち行列内に格納されているブロックされたスレッド記述子を解放する制御パケットを発行する。引数を以下に示す。
【表５】
0005386572.tif 000006
【０３６８】
保留待ち行列へのスレッドの追加呼び出し元：ＴＳＩＦ
このコマンドは、新しいまたは既存の作業待ち行列にスレッド記述子を追加する。このコマンドは、作業待ち行列におけるスレッド記述子の存在によって保留マネージャに示唆される。以下の表に、このコマンドに関連するスレッド記述子のフィールドを示す。
【表６】
0005386572.tif 000007
【０３６９】
マーカスレッド処理呼び出し元：ＴＳＩＦ
このコマンドは、単に、マーカスレッドをスケジュールマネージャ作業待ち行列に渡す。これは、マーカスレッドがスケジューラ解体を引き起こす可能性が生じる前にすべての従属スレッドが保留マネージャによって処理されるよう保証するのに使用される。
【０３７０】
同期プリミティブ呼び出し元：ＴＳＩＦ
このコマンドは、指定された保留待ち行列に同期プリミティブを発行する。このコマンド構造には以下の引数がある。
【表７】
0005386572.tif 000008
【０３７１】
メトリック更新呼び出し元：ＴＳＩＦ
このコマンドは、ブロックされたスレッドのメトリックを更新し、適切な保留待ち行列の再ソートを行わせる。このコマンドは、識別されたスレッドがブロックされなくなった場合、ＴＳＳＭに渡されてもよい。このコマンド構造には以下の引数がある。
【表８】
0005386572.tif 000009
【０３７２】
保留待ち行列ロック解除呼び出し元：ＴＳＩＦ
このコマンドは、保留待ち行列が空になったときに、解放されてフリーリストに戻されるように、保留待ち行列をロック解除する。このコマンド構造には以下の引数がある。
【表９】
0005386572.tif 000010
【０３７３】
［ＴＳＯＭ  出力マネージャ］
出力マネージャは、次の実行スレッド記述子、および現在実行中のスレッドの実行メトリックを参照するディスパッチ待ち行列構造を助ける。
【０３７４】
１．１．１  アーキテクチャ
ＴＳＯＭのアーキテクチャは、図５８に示すディスパッチ待ち行列構造を中心とする。出力マネージャは、各ＤＱＤがＰｒｏｃＥｌｅｍｅｎｔＩＤフィールドを介してシステム処理リソースインスタンスと関連付けられるディスパッチ待ち行列記述子のリストを維持する。ＴＳＯＭの機能全体を詳細に参照するＤＱＤへの２つの要素グループがある。第１のグループ、実行中心の要素は、ＰｒｏｃＥｌｅｍｅｎｔＩＤ、メトリック０、メトリック１およびデフォルトメトリック０を備え、タスクの実行状態を参照し、タスクの実行状態内で管理される。第２のグループ、作動可能待ち行列中心の要素は、ルートスケジューラインデックス、優先使用インデックスおよび次の優先使用インデックスを備え、実行を待ち受けるスレッドの作動可能待ち行列構造を参照する。また、ＴＳＯＭは、システム内処理リソースインスタンスへの帯域外信号（通常は割り込み）、および作動可能待ち行列構造からのスレッド記述子のポップも管理する。
【０３７５】
実行中心の要素
以下は、ディスパッチ待ち行列記述子内の実行中心の要素の用法の簡単な説明である。
−ＰｒｏｃＥｌｅｍｅｎｔＩＤ  これは、ディスパッチ待ち行列記述子が結合される処理リソースインスタンスを参照するインデックスを格納する静的フィールドである。
−メトリック０、１は、（「アイドルタスク」および潜在的に多数の電源遮断状態を含む）現在実行中のタスクの実行メトリックを格納するのに使用される、動的に更新されるフィールドである。
−デフォルトメトリック０は、現在実行中のスレッドをＳｙｓｔｅｍＷｅａｖｅｒサーバにプッシュバックし、したがって、定義上アイドル状態になるときに、アイドルメトリックを自動的に復元するための最適化をサポートするのに使用される静的フィールドである。
【０３７６】
作動可能待ち行列中心の要素
以下は、ディスパッチ待ち行列記述子内の作動可能待ち行列中心の要素の用法の簡単な説明である。
−ルートスケジューラインデックスは、ディスパッチ待ち行列と関連付けられたスケジューリングルート層への静的参照である。
−優先使用インデックスは、所与のリソースの次の実行に現在最も適格な候補を格納する動的フィールドである。優先使用インデックスは、完全にＴＳＯＭ内で管理され、適切な場合には、ディスパッチ待ち行列イベントの結果として設定される。
−次の優先使用インデックスは、スケジューリング階層内の次に最も適格なスレッドの親またはスレッドインデックス自体を格納する動的フィールドである。次の優先使用インデックスは、ＴＳＳＭによってのみ設定され、ＴＳＯＭに、最も適格なスレッドの作動可能待ち行列構造内の位置を知らせる伝達手段として使用される。ＴＳＯＭは、通常、処理後にこのフィールドをリセットする。
【０３７７】
ディスパッチ待ち行列イベント
ディスパッチ待ち行列イベントは、以下の２つの理由で発生する。
−再スケジュールイベント：ディスパッチ待ち行列イベントは、スケジュールマネージャ（ＴＳＳＭ）内の再スケジュール操作が、ディスパッチ待ち行列に必要とされる状態の変更、すなわち、通常は、作動可能待ち行列イベント（プッシュ、ポップまたはメトリック操作）を処理した結果としての優先使用を識別する都度発生する。
−ディスパッチ待ち行列ポップイベント：優先使用インデックスによって参照されたスレッドインデックスがインターフェースマネージャ（ＴＳＩＦ）によってポップされている。このイベントは、ディスパッチ待ち行列自体の内の（Ｃ＿ＤＩＳＰＡＴＣＨ＿ＤＥＳＣ＿ＰＯＰＰＥＤ＿ＦＬＡＧによって索引付けされる）「ディスパッチ待ち行列ポップ」フラグによってＴＳＯＭに通知される。
【０３７８】
ディスパッチ待ち行列ポップイベントの場合、ポップされたスレッドは、ゾンビ状態（図４１参照）に遷移し、まだそこに存在しない場合には、ＴＳＳＭによる解放のために作業待ち行列にプッシュバックされる。その後、ＴＳＯＭは、作動可能待ち行列階層からそのスレッドをリンク解除する。
【０３７９】
再スケジュールイベントとディスパッチ待ち行列ポップイベントの両方で、ディスパッチ待ち行列イベントの処理が続いて、ディスパッチ待ち行列記述子内での優先使用インデックスの再取り込みが開始される。デフォルトでは、次の優先使用インデックスがスレッド自体の権限内のスレッドインデックスでない場合、これは、次の優先使用インデックスによって識別されるスケジューリング層からスケジューリング階層をウォークすることによって取り込まれる。これが完了すると、識別されたスレッドインデックスは、優先使用インデックスフィールド内に配置され、スレッドは、事実上、作動可能待ち行列からポップされる。すなわち、スレッドは、作動可能状態からポップ状態に遷移する（図４１参照）。この仮想ポップは、最も適格なスレッドをロックし、それをポップ状態とマークし、再スケジューリングのためにＴＳＳＭにフラグでイベントを知らせることによって明示される。
【０３８０】
一定の状況下で、ディスパッチ待ち行列イベントは結果として割り込みを生じる。再取り込みされた優先使用インデックスが有効なスレッド記述子インデックスを含み、割り込みが使用可能にされている場合、このディスパッチ待ち行列に関連付けられたシステムプロセッサへの割り込みは、先の割り込み表明フラグが使用可能にされており、次の優先使用インデックスがスレッドであって、すでにＴＳＳＭによってアサートされている場合を除いて、あらゆる状況下でアサートされる。
【０３８１】
また、ディスパッチ待ち行列メトリックも更新される。
【０３８２】
ディスパッチ待ち行列メトリックは現在実行中のスレッドの適格性を表すが、ディスパッチ待ち行列は、割り込みされており、またはディスパッチ待ち行列ポップが行われている。したがって、実行スレッドは、割り込みされようとしており（その場合、メトリックの更新は、最悪の場合、少々時期尚早である）、または新しいスレッドが実行中で、ディスパッチ待ち行列メトリックがいずれにしても上書きされることになる。
【０３８３】
既存の次の優先使用インデックスを不当に使用している再スケジュールが発生している場合、既存の優先使用インデックスは、事実上、作動可能待ち行列構造にフラッシュバックされなければならない（図４１参照）。ＴＳＯＭ内では、スレッドは、単に、フラッシュされたとマークされるだけであり、処理のためにＴＳＳＭ作業待ち行列にプッシュバックされる。
【０３８４】
適格なスレッドが見つからない場合、操作は、単に、完了し、クライアント（処理リソース）は、これらの状況下ではアイドル状態になる。
【０３８５】
ディスパッチ待ち行列適格性メトリックの設定
ディスパッチ待ち行列適格性メトリックは、ＰｒｏｃＥｌｅｍｅｎｔＩＤで索引付けされる処理リソースインスタンス上で現在実行中のタスクの実行優先度を反映する。しかしながら、いくつかの最適化の下では、ディスパッチ待ち行列適格性メトリックは、実行開始寸前のタスクの実行優先度を反映してもよい。
【０３８６】
ディスパッチ待ち行列優先度メトリックは、優先使用を制御するのに使用され、以下のような様々な理由で操作される。
−新しいタスクの開始
−現在のタスクの完了
−優先度逆転
−電源管理
【０３８７】
いずれの場合にも、その目的は、作動可能待ち行列のスケジューリングの操作を調整することである。更新の結果としてプールルートノードの変更を生じる場合、そのノードは、再スケジュール操作のためにＴＳＳＭにフラグで通知される。プール参加ノードおよび非プール参加ノード内のメトリック伝搬の詳細については、上記を参照されたい。
【０３８８】
最適化として、処理リソースインスタンスが現在実行中のスレッドを、ＳｙｓｔｅｍＷｅａｖｅｒ内の作動可能またはブロック状態にプッシュバックするときに、実行優先度は、自動的に、デフォルトメトリックにリセットされる。
【０３８９】
「メソッドインターフェース」
ディスパッチ待ち行列リンクリスト上での基本状況操作（取得および設定状況）と共に、出力マネージャは、そのインターフェース上で以下のコマンドを提示する。
【０３９０】
自動化実行メトリック更新（Ｃ＿ＴＳＯＭ＿ＣＭＤ＿ＳＥＲＶＩＣＥ＿ＴＩＭＥ＿ＳＬＩＣＥ＿ＥＸＰＩＲＥ）呼び出し元：ＴＳＩＦ
このコマンドは、識別されたプロセッサＩＤのために、ディスパッチ待ち行列内に保持されるメトリックのメトリック０の最下位ビットを自動的に変更する。引数は、ディスパッチ待ち行列記述子自体ではなく、プロセッサの識別情報であるため、このコマンドは、最初に、ディスパッチ待ち行列記述子リストをウォークして適切な記述子を見つける。変更は、最下位ビットの単なる反転であり、メトリックフィールドの予約部分が適切に設定されると仮定すると、これは、優先度が昇順であるにせよ、降順であるにせよ、実行スレッドの優先度を下げる効果を有する。
【０３９１】
引数を以下に示す。
【表１０】
0005386572.tif 000011
【０３９２】
ディスパッチ待ち行列メトリック設定呼び出し元：ＴＳＩＦ（明示的システム呼び出しから）
このコマンドは、個々のディスパッチ待ち行列の実行メトリックを設定する。このコマンド構造には以下の引数がある。
【表１１】
0005386572.tif 000012
【０３９３】
デフォルトディスパッチ待ち行列メトリック設定呼び出し元：ＴＳＩＦ
このコマンドは、個々のディスパッチ待ち行列の実行メトリック（０）を、やはりディスパッチ待ち行列内に保持されるデフォルト値にリセットする。この関数には引数はない。
【０３９４】
ディスパッチ待ち行列イベント（Ｃ＿ＳＣＨＥＤ＿ＥＮＴＲＹ＿ＤＩＳＰＡＴＣＨ＿ＬｉＳＴ）呼び出し元：ＴＳＳＭ
このコマンドは、作動可能待ち行列の状態変更によって必要とされたときに、ディスパッチ待ち行列記述子を更新させる。
【０３９５】
［ＴＳＳＭ  スケジュールマネージャ］
スケジュールマネージャは、作動可能待ち行列構造の親子リンケージに固有のスケジューリング決定を助ける。
【０３９６】
「アーキテクチャ」
ＴＳＳＭには、もっぱらその作業待ち行列インターフェースからコマンドが供給され、純粋に、イベント駆動型である。しかしながら、一定の挙動がいくつかのコマンドに共通であり、以下でこの挙動を説明する。
【０３９７】
再スケジュール
再スケジュール関数は、スケジューリング階層内の定義された点からスケジューリング決定を再評価する。再スケジュール操作は処理保存的であり、その状態がおそらくイベントによって影響を受けるはずの階層の部分に関連付けられる処理を上回る追加処理は行われない。
【０３９８】
ＵｐｄａｔｅＲｅｑｕｉｒｅｄという、再スケジュール関数への１つの特に興味深い引数がある。ＵｐｄａｔｅＲｅｑｕｉｒｅｄは、スケジューラ層操作間で更新状況を伝搬するのに使用される。例えば、他の状態は依然として管理されなければならないが、子層内の決定を更新しなかったポップ操作は、親層内の全スケジューリング反復を行わせる必要がない。この場合、ＵｐｄａｔｅＲｅｑｕｉｒｅｄは偽になるはずである。
【０３９９】
図６０に、再スケジュール操作の基本的流れを示す。層内スケジューラは、層内スケジューリングを実行し、結果として層親先頭インデックスポインタの更新をもたらす。層間スケジューラは、ディスパッチノードに向かってスケジューリング階層内の連続する層をスケーリングする。層間スケジュール関数は、親インデックスを用いて呼び出され、それによって、階層のレベルを即座にスケーリングすることに留意されたい。プール層間スケジュールは、特殊なスケジューリングアルゴリズムであり、単一のノード、プールノードから多数のノード、プール静的ノードに展開する唯一のアルゴリズムである。
【０４００】
この項の残りの部分では、スケジューリングアルゴリズムの操作を説明する。
【０４０１】
層内スケジューラ
最も基礎的なスケジューリング操作は、スケジューリング層内の要素のリンクリストをトラバースしてどれが最も適格であるか識別し、親の先頭ポインタをしかるべく更新することである。
【０４０２】
適切な記述子が空のスケジューリング層にプッシュされる単純な場合には、親の先頭ポインタおよび要素数は無条件で更新され、メトリックは、（メトリック伝搬演算子に従って）新しい子から親に条件付きで伝搬される。
【０４０３】
図６１に、プッシュ操作でのより一般的な場合を示す。現在の選択および候補選択の妥当性は、以下のいくつかの要因の組み合わせである。
−選択は、スケジュールされ得る内容を持たねばならない。スレッドでは、これは常に真であるが、スケジューラでは、これはその下位階層の内容に依存する。
−記述子がスケジューラである場合、それは、休止状態であってはならず、その無効線活動状態フラグが設定されてもならない。
−記述子が標準スレッドである場合、それは、ロックされてはならず、作業待ち行列内にあってもならない。
−記述子がマーカスレッドである場合、親の合計依存関係カウントはゼロでなければならず、マーカスレッドは、層内に残る唯一のエントリでなければならない。
【０４０４】
候補は、現在の選択、すなわち前のスケジューリング操作からの最も適格な記述子とだけ比較されることに留意されたい。候補がその勝者に勝った場合、それは新しい勝者にならなければならない。「対スケジュール」は、前述の、親スケジューリング層内に保持されるアルゴリズムに関連する。「親更新」変数は、この操作の結果としてこの層の親も更新されるべきであるという、呼び出し元へ返される命令を保持する。
【０４０５】
再スケジュールの一般的な場合、例えば、メトリックが更新されている場合や、ポップが発生している場合には、最も適格な候補を見つけるために全層が再評価されねばならない。このプロセスは、図６２に示すように、全層が再評価されるまで、図６１の操作を複数回実行する。
【０４０６】
層間スケジュール
層間スケジュールは、１スケジューラ層当たり１回実行され、これは、１スケジューリングイベント当たりでは数回になり得る。層間スケジューリングは、親の種類に大きく依存する。要約すると、層間スケジューリングは、親がディスパッチ待ち行列になるまで、層内スケジューリングを呼び出し続ける。これには１つの例外があり、それは、プール配布ノードに遭遇した場合である。
【０４０７】
図６３に、層間スケジューリングの基本的流れを示す。ディスパッチ待ち行列記述子（ＤＱＤ）親およびプールルートノード（ＰＲＮ）と関連付けられた固有の挙動がある。しかしながら、層間スケジューラが、単に、現在の子インデックスを、現在の親で置換し（それによって、スケジューリング階層を反復し）、それ自体を再呼び出しするだけの場合もある。
【０４０８】
図６４に、層間スケジューリングルーチンにおけるディスパッチ待ち行列処理を示す。まず、ディスパッチ待ち行列記述子（ＤＱＤ）内に含まれる実行メトリックが、ＤＱＤで定義されるアルゴリズムに従って、スケジューラルートノード内に保持されるメトリックに対してスケジュールされる。この操作で、優先使用が必要とされると決定された場合、再スケジュール操作を開始したイベントの種類に従ってＤＱＤの次の優先使用インデックスへの更新が行われる。このイベントがスレッドプッシュであった場合、スケジュールされたスレッドインデックスが次の優先使用インデックスフィールドに直接配置され、そうでなかった場合、スケジューラルートノードインデックスが使用される。次いで、ＴＳＯＭ上で、スケジューリング階層を反復してスレッド記述子を見つける。
【０４０９】
プール層間スケジューリング
プール層間スケジューリングは、もしあれば、関連付けられた処理リソースインスタンスのうちのどれが、現在のプール内に保持されるスレッド記述子を処理するのに選択されるべきか識別するのに使用される。その意味で、これは、固有の方法で動作する。なぜなら、本明細書で説明する他のすべてのスケジューリングアルゴリズムと異なり、通常、プール層間スケジューリングは、最も適格性の低い候補を求めようとするからである。
【０４１０】
図６６に、図６５に図示する、プール層間スケジューリング操作の流れを示す。初期の層内スケジューリング操作は、プール配布層内のプール静的ノード内に保持されるメトリックによって指示されるように、スケジューリング階層からの候補が実行タスクのいずれかより適格であるかどうか判定する。更新が必要とされるかどうかの指示と、更新が適用されなければならないノードの識別という２つの結果がある。
【０４１１】
次いで、アルゴリズムは、プールルートノードの適切な「次のポインタ」によって指示されるプール静的ノードから、全プール配布層の周りで反復し始める。
【０４１２】
反復の都度、ハウスキーピング機能（スレッドカウンタや他の状態の維持など）を助けると共に、層間スケジューリングがプール接続層上で呼び出される。通常はそうであるように、層間スケジューリングは、ディスパッチノードに到達するまで、全スケジューリング階層を上へ伝搬し続ける。層間スケジューリングは、さらなるスケジューリング層が、「更新必要」というスケジューリング決定を完全に再評価すべきかどうか指示する引数を取る。このフラグは、プール間スケジューリングのコンテキストにおいて、以下の２つの状況下で設定される。
−現在処理されているプール静的ノードが、プール内スケジューリングによって、プールルートノードの下で最も適格なスレッドを処理するのに最も適格なノードであると識別されたノードである。
−プールルートノードの下の階層に、適格なスケジューリング候補がない。
【０４１３】
プール層内スケジューリング
図６７に、プール層内スケジューリングの流れを示す。第１の例には、プッシュのみの操作でのスケジューリング時間を短縮する最適化がある。これは、利用可能になる新しいタスクへのシステムの応答性を向上させる。
【０４１４】
これが排他的プッシュ操作ではないと仮定すると、スケジューリング操作は、現在の選択および候補選択を、プール内の最初の２つのＰＳＮノードに設定する。次いで、アルゴリズムは、全プール配布層の周りのループに入る。反復の都度、現在の選択が候補に対してスケジュールされる。プール配布層には、他のスケジューリング層と同じスケジューリングアルゴリズムが使用されるが、選択される個別アルゴリズムは異なる可能性が高いことに留意されたい。なぜなら、このシナリオでは、正しい選択が、通常の標準による最も適格性の低いメトリックを示すことになるからである。
【０４１５】
候補が現在の選択を統括する場合、現在の選択が候補に更新され、候補が層内の次のエントリに更新され、処理は、候補がＰＲＮになるまで続く。
【０４１６】
排他的プッシュ操作では、この反復が回避される。現在の選択待ち行列および更新ノードは、単に、（現在のスケジューリング選択を定義する）ＰＲＮの親に設定され、候補は、ＰＲＮ自体である。
【０４１７】
いずれの場合にも、次いで、プールルートノードにスケジュール可能な内容があるかどうかチェックされ、何もない場合、「更新なし」状況が設定され、アルゴリズムが戻る。しかしながら、スケジュール可能な内容がある場合、プロセスは、第２段階に進み、（排他プッシュ操作における）ＰＲＮからの既存の選択または（他の場合の）反復の結果が、ＰＲＮ自体に対してスケジュールされる。ＰＲＮがこの競争に勝った場合には、更新が必要とされ、そうでない場合には、不要とされる。
【０４１８】
例
図６８に、スレッド記述子（ノード＃５）の静的スケジューリング要素（ノード＃３）へのプッシュに関連付けられるＴＳＳＭスケジューラ処理を示す。最初の層内スケジューリング操作は、再スケジュール関数のコンテキスト内で行われ、親ノード＃３に関するものである。次いで、再スケジュールは、階層の上位層へ移動し、親ノード＃２との層間スケジューリングを呼び出す。この直後の反復は親ノード＃１を見つけ、これはＤＱＤである。したがって、層内スケジューラへのそれ以上の呼び出しはなく、スケジューリング比較が、ルートノード内に格納される最も適格な候補のメトリックと、ディスパッチノード内に格納される実行スレッドの間で行われる。この場合、優先使用が適切であり、ディスパッチ待ち行列イベントがＴＳＯＭに伝達される。
【０４１９】
図６９に、より階層化されたスケジューリング階層を示す。この場合、階層の別の層ために層内スケジューリング関数へのさらなる呼び出しが行われる。ただし、再スケジュール操作を引き起こしたスケジューリングイベントはその範囲外であるため、スケジューリング層５および３は影響を受けないことに留意されたい。
【０４２０】
図７０に、このプールスケジューリング操作の場合の第３の例を示す。前述のように、そこへのスレッドプッシュイベントが発生する層は層内スケジューリング操作の対象とされ、この例では、新しいスレッドは、プールルート層内で最も適格なものである。次いで、プール層間スケジューラが、プール層内スケジューラへの呼び出しを行って、システム処理リソースのいずれかが新しく到着したスレッドに取って代わられるべきかどうか判定する。この場合、プール層内スケジューリングの結果は、ＷＭＥインデックス７のところのディスパッチ待ち行列記述子に関連付けられた処理リソースインスタンスが取って代わられるべきであるというものである。
【０４２１】
次いで、プール層間スケジューラは、プール配布層の周りで反復し、まず、ノード４上で層間スケジュールを呼び出す。次に、層間スケジュールが層内スケジュールを呼び出してスケジューラ層１を更新するが、網羅的なスケジューリングは必要とされない。なぜなら、これは取って代わられた層ではなく、処理は状態情報の維持に限定され、したがって、ＴＳＯＭへのディスパッチ待ち行列イベントも、システム処理リソースへの割り込みもないからである。
【０４２２】
次の呼び出しは、層２上の層間スケジューリングである。この場合、層は、新しくプッシュされたスレッド記述子が他のどんな候補よりも適格であるかどうか明示するように適正にスケジュールされる。候補メトリックは、最終的には、優先使用が適切であるかどうか判定するために、ディスパッチ待ち行列記述子内に格納された実行スレッドのメトリックと比較される。この例では、メトリック、したがって、ディスパッチ待ち行列イベントがＴＳＯＭに送られ、システム処理リソースインスタンス割り込みにフラグが立てられる。
【０４２３】
この場合もやはり、プッシュスレッドイベントの範囲の影響を受けるスケジューリング層だけが再評価される。
【０４２４】
「メソッドインターフェース」
ＴＳＳＭは、もっぱら、作業待ち行列を介してのみ宛先指定される。
【０４２５】
スレッド記述子イベントサービス呼び出し元：ＴＳＩＦ、ＴＳＰＭ、ＴＳＯＭ
このコマンドの挙動は、以下のように、受け取られたスレッドのフラグ内の設定に依存する。
−プッシュまたはフラッシュフラグが設定されている場合、親の合計スレッド要素カウントを増加させる。ポップフラグが設定されている場合、親の合計スレッド要素カウントを減少させる（上記の組み合わせの最終結果はヌルとなり得ることに留意されたい）。
−次いで、プッシュフラグが設定されたスレッドが作動可能待ち行列階層にリンクされる。それらのスレッドがブロック状態から遷移している場合、従属スレッドの親のカウントも減らされる。
−マーカスレッドだけに限定される唯一の挙動が、親のロック解除である（スケジューラ層の「保留空き」状態への遷移。図４参照）。
−ＴＳＳＭは、このコマンドを処理するときに、ゾンビ状態で受け取られた任意のスレッド記述子が解放されるよう要求する。
【０４２６】
このコマンドは、常に、再スケジュールを必要とする。
【０４２７】
再スケジュールプール配布層呼び出し元：ＴＳＯＭ
このコマンドは、実行スレッドのメトリックの変更の結果として呼び出される。ディスパッチ記述子がプールに関与する場合、これらのメトリックは、配布階層を介して伝搬され、最終的に、この関数を呼び出してスケジューリング決定を再評価する。
【０４２８】
スケジューラ層の再スケジュールまたは削除呼び出し元：ＴＳＯＭ
このコマンドは、以下の２つの理由でＴＳＯＭによって呼び出される。
−ディスパッチ記述子がプールに関与しない場合の、実行スレッドのメトリックの変更の結果として、優先使用が適切であるかどうか再評価するため。この操作は、スケジューリングルートノードを通過する。スケジューリング層がその階層にスレッド記述子を含む場合、再スケジュールが要求される。
−ＴＳＯＭが、そうするのが妥当であると決定している場合に、スケジューリング層を削除するため。この決定は、ロックされたフラグ、従属スレッドカウントおよび子要素の数（それぞれ、偽、０、０）に基づくものである。記述子の実際の解放は、ＴＳＩＭへの要求として現れる。
【０４２９】
独立要素のプッシュ呼び出し元：ＴＳＩＦ
このコマンドは、初期設定時に、静的スケジューリング層をスケジューリング階層にプッシュするのに使用されてもよく、実行時にスレッド記述子または動的スケジューリング階層を動的に追加するのに使用されてもよい。
【０４３０】
スレッドメトリックの更新呼び出し元：ＴＳＩＦ
作動可能待ち行列階層内のスレッド記述子のメトリックを更新する。メトリックは、スレッド記述子が作動可能状態にあるときにだけ更新されてもよい（図４１）。
【０４３１】
このコマンドは再スケジュールを発生させる。
【０４３２】
スケジューラ状態の更新呼び出し元：ＴＳＩＦ
このコマンドは、スケジューラアルゴリズム、メトリックおよびメトリック伝搬アルゴリズムの更新を可能にする。このコマンドは再スケジュールを発生させる。
【０４３３】
スケジューラ層の活動化呼び出し元：ＴＳＩＦ
このコマンドは、休止スケジューラ層を活動化する。このコマンドは再スケジュールを発生させる。
【０４３４】
スケジューラ層の非活動化呼び出し元：ＴＳＩＦ
このコマンドは、休止スケジューラ層を非活動化する。
【０４３５】
［ＴＳＭＭ  メモリマネージャ］
メモリマネージャ（図７１）は、ＴＣＭへのアクセスを集約するための挙動の多重化／逆多重化を提供する。また、複数のサブブロック間で共用されるリソースの保全性を保証するロッキング機能も提供する。
【０４３６】
「アーキテクチャ」
アーキテクチャ上の観点から見ると、メモリマネージャは、主に、６つの可能な要求元の間でＴＣＭへのアクセスを集約するマルチプレクサ／デマルチプレクサとみなすことができる。また、ロックキャッシュを実装することによって、複数のサブブロックが同じリソースへのアクセスを試みようとする場合の、ＷＭＥの保全性も維持する。
【０４３７】
アクセス集約
アクセス集約は、スケジューラの制御下にある。このスケジューラは、以下のように、非対称である。
−ＴＳＩＦは最高の優先度を有する
−ＴＳＯＭは次に高い優先度を有する
−残りすべての要求元は、等しい優先度を有し、処理保存的ラウンドロビンで扱われる。
【０４３８】
ロックキャッシング
各ブロックは、１から４ロックの間の割り振りを有する。これらの数は、サブブロック要求元が排他的にアクセスすることのできるＷＭＥの数を表す。ロックされたリソースを要求するサブブロックは、そのリソースが利用可能になるまでブロックされる。同じリソース上で回転する複数のブロック間の競合は、優先度によって解決される。
【０４３９】
［スケジューリングシーケンス図］
［プッシュイベント］
図７２のシーケンス図に、プッシュイベントに続くサブブロック間対話を示す。ＴＳＳＭおよびＴＳＯＭは、自ずと、シングルスレッドであるため、コマンドを格納するために作業待ち行列が導入されていることに留意されたい。代表的なスケジューリング階層については、図６８を参照されたい。
【０４４０】
プッシュイベント前の状態は、スレッド＃４がディスパッチ待ち行列記述子＃１内の現在の優先使用インデックスであるというものである。第１の再スケジュールは、スレッド＃５が、スレッド＃４より適格であると識別し、結果として、ディスパッチ待ち行列記述子＃１がＴＳＯＭ作業待ち行列にプッシュされる。
【０４４１】
ＴＳＯＭ作業待ち行列内のディスパッチ待ち行列記述子が、ＴＳＯＭ内のディスパッチ待ち行列イベントを発生させる。このイベントは、事実上、スレッド記述子＃５をポップし、ディスパッチ待ち行列メトリックをしかるべく設定する。このポップ操作は、作動可能待ち行列内の状態の変更を生じ、したがって、再スケジュールが呼び出されなければならない。これは、ポップフラグを設定してスレッド＃５をＴＳＳＭ作業待ち行列にプッシュすることによって達成される。
【０４４２】
スレッド＃４は、事実上以前にポップされているため、今や、作動可能待ち行列構造にフラッシュバックされる必要がある。これもやはり、作動可能待ち行列構造内の状態変更を構成し、したがって、別の再スケジュールが必要とされる。これは、フラッシュフラグを設定してスレッド＃４をＴＳＳＭ作動可能待ち行列構造にプッシュすることによって達成される。
【０４４３】
事実上ポップされたスレッドおよびフラッシュされたスレッドは、大部分が作動可能待ち行列階層の異なる部分に存在し得るため、第２および第３の再スケジュール操作をマージすることはできないことに留意されたい。
【０４４４】
［ポップイベント］
図７３のシーケンス図に、「仮想」ディスパッチ待ち行列からスレッド記述子がポップされるときの、ＴＳＩＦとＴＳＯＭとＴＳＳＭの間の対話を示す。
【０４４５】
ポップコマンド自体は、コマンドインターフェース、またはシステム相互接続を介してＴＳＩＦによって受け取られる。ＴＳＩＦは、ポップフラグを設定してディスパッチ待ち行列記述子をＴＳＯＭ作業待ち行列上にプッシュすることによって、ディスパッチ待ち行列ポップコマンドを発行する。
【０４４６】
ＴＳＯＭ作業待ち行列内のディスパッチ待ち行列記述子は、ＴＳＯＭ内のディスパッチ待ち行列イベントを発生させる。ディスパッチ待ち行列イベントハンドラは、ＴＳＳＭに、ポップされたばかりのスレッド記述子、この場合はスレッド＃５をフリーリスト上に戻すよう要求するように指示する。次いで、実行するのに次に最も適格な候補を格納する次の優先使用インデックスが、事実上、ＴＳＯＭによってポップされる。これは、作動可能待ち行列構造での状態変更を表し、したがって、ＴＳＳＭは、ＴＳＯＭによって再スケジュールするよう命令され、ポップフラグを設定して次の優先使用スレッドが、ＴＳＳＭ作業待ち行列にプッシュされる。
【図１】
0005386572.tif 000013
【図２】
0005386572.tif 000014
【図６】
0005386572.tif 000015
【図１４】
0005386572.tif 000016
【図１６】
0005386572.tif 000017
【図２０】
0005386572.tif 000018
【図２４】
0005386572.tif 000019
【図２５】
0005386572.tif 000020
【図２６】
0005386572.tif 000021
【図２７】
0005386572.tif 000022
【図２８】
0005386572.tif 000023
【図２９】
0005386572.tif 000024
【図３０】
0005386572.tif 000025
【図３６】
0005386572.tif 000026
【図３８】
0005386572.tif 000027
【図４３】
0005386572.tif 000028
【図４４】
0005386572.tif 000029
【図４５】
0005386572.tif 000030
【図４６】
0005386572.tif 000031
【図４７】
0005386572.tif 000032
【図４９】
0005386572.tif 000033
【図５２】
0005386572.tif 000034
【図５３】
0005386572.tif 000035
【図５７】
0005386572.tif 000036
【図５９】
0005386572.tif 000037
【図６０】
0005386572.tif 000038
【図６１】
0005386572.tif 000039
【図６２】
0005386572.tif 000040
【図６３】
0005386572.tif 000041
【図６４】
0005386572.tif 000042
【図６６】
0005386572.tif 000043
【図６７】
0005386572.tif 000044
【図７１】
0005386572.tif 000045
【図７２】
0005386572.tif 000046
【図７３】
0005386572.tif 000047
【図３】
0005386572.tif 000048
【図４】
0005386572.tif 000049
【図５】
0005386572.tif 000050
【図７】
0005386572.tif 000051
【図８】
0005386572.tif 000052
【図９】
0005386572.tif 000053
【図１０】
0005386572.tif 000054
【図１１】
0005386572.tif 000055
【図１２】
0005386572.tif 000056
【図１３】
0005386572.tif 000057
【図１５】
0005386572.tif 000058
【図１７】
0005386572.tif 000059
【図１８】
0005386572.tif 000060
【図１９】
0005386572.tif 000061
【図２１】
0005386572.tif 000062
【図２２】
0005386572.tif 000063
【図２３】
0005386572.tif 000064
【図３１】
0005386572.tif 000065
【図３２】
0005386572.tif 000066
【図３３】
0005386572.tif 000067
【図３４】
0005386572.tif 000068
【図３５】
0005386572.tif 000069
【図３７】
0005386572.tif 000070
【図３９】
0005386572.tif 000071
【図４０】
0005386572.tif 000072
【図４１】
0005386572.tif 000073
【図４２】
0005386572.tif 000074
【図４８】
0005386572.tif 000075
【図５０】
0005386572.tif 000076
【図５１】
0005386572.tif 000077
【図５４】
0005386572.tif 000078
【図５５】
0005386572.tif 000079
【図５６】
0005386572.tif 000080
【図５８】
0005386572.tif 000081
【図６５】
0005386572.tif 000082
【図６８】
0005386572.tif 000083
【図６９】
0005386572.tif 000084
【図７０】
0005386572.tif 000085
【図７４】
0005386572.tif 000086