(57)【要約】      （修正有）【課題】プロセス、スレッドの異なるリソース要求を効率的にスケジュールする。【解決手段】システムは、リソースと、このリソースに要求を出すように構成された実行エンティティと、各実行エンティティに対するスロット割当てを含むテーブル或いはテーブルセグメント２０２Ａ〜２０２Ｅとをそれぞれ含んでいる。スケジュールコントローラ３１４は、テーブル或いはテーブルセグメントにアクセスし、スロット割当てに従って実行エンティティからの要求を処理するように構成される。このシステムは、スロット割当てを更新するスケジューラ２３２も含んでいる。さらに、このシステムは、実行エンティティと交渉し、リソース使用要求を決定するオペレーティングシステム２２０を含んでもよい。テーブル或いはテーブルセグメントは、リソース使用要求に基づいて、オペレーティングシステムによって更新されてもよい。【選択図】図２Ａ
2010044784.tif 000002
【特許請求の範囲】
【請求項１】
リソースと、
前記リソースに要求を出すように構成される実行エンティティと、
各実行エンティティからの前記リソースに対する要求に関連するスロット割当てを含む記憶ロケーションと、
前記リソースに結合され、かつ、前記記憶ロケーションにアクセスし、前記スロット割当てに従って前記実行エンティティから前記リソースに対する要求を処理するように構成されるコントローラと
をそれぞれ備えることを特徴するシステム。
【請求項２】
前記記憶ロケーションのスロット割当てを更新するように構成されたスケジューラをさらに含むことを特徴とする請求項１に記載のシステム。
【請求項３】
前記スケジューラによってアクセスでき、かつ、前記実行エンティティためのスロット割当てを含む第２の記憶ロケーションをさらに含むことを特徴とする請求項２に記載のシステム。
【請求項４】
前記リソースが前記第２の記憶ロケーションのスロット割当て及び未実行の要求に基づいて実行エンティティによって出された要求に対して利用可能であるかどうかについて、前記スケジューラが決定するように構成されることを特徴とする請求項３に記載のシステム。
【請求項５】
前記スケジューラが、各実行エンティティのリソースに対する帯域幅を認識しており、かつ、前記スケジューラが、前記帯域幅の情報に基づいて実行エンティティによって出された要求に対して利用可能であるかどうかを決定するように構成されていることを特徴とする請求項４に記載のシステム。
【請求項６】
前記要求が、１つ或いはそれ以上のパラメータに関連したアプリケーションプログラマブルインタフェース呼び出しを含むことを特徴とする請求項４に記載のシステム。
【請求項７】
前記スケジューラが、要求が処理されたかどうかを決定するために前記コントローラにアクセスするように構成されていることを特徴とする請求項２に記載のシステム。
【請求項８】
どのスロットがアクティブであるかどうかを決定するためにコントローラによってアクセスできるカウンタをさらに含むことを特徴とする請求項１に記載のシステム。
【請求項９】
各スロットが、１つ或いはそれ以上のチャネルを含み、前記カウンタが、前記チャネルを計数するように構成されることを特徴とする請求項８に記載のシステム。
【請求項１０】
複数のスロットが、スケジューリングサイクルで規定され、かつ、前記コントローラが、対応するスロットにおいて前記実行エンティティからの要求を処理するように構成されることを特徴とする請求項１に記載のシステム。
【請求項１１】
リソース使用要求を決定するために実行装置と協働するオペレーティングシステムと、
前記オペレーティングシステムによって更新可能であり、その割当てられたチャネルの期間中にシステムリソースにアクセスできる実行装置の前記リソース使用要求に基づいて、チャネルを前記実行装置に割当てる記憶ロケーションと
を含むことを特徴とする請求項１に記載のシステム。
【請求項１２】
前記実行エンティティが、前記リソースのための帯域幅の情報を前記オペレーティングシステムに通信するように構成されていることを特徴とする請求項１１に記載のシステム。
【請求項１３】
前記実行エンティティが、前記リソースのための呼び出し時間の情報を前記オペレーティングシステムにさらに通信するように構成されていることを特徴とする請求項１２に記載のシステム。
【請求項１４】
システムにおいて実行装置からの要求をスケジューリングする方法であって、
システムリソースのための前記実行装置のデータフロー情報を決定し、
前記データフロー情報に基づいて、前記システムリソースへのアクセスのためにタイムスロットを前記実行装置に割当て、
前記割当てられたタイムスロットに基づいて、コントローラをプログラミングすることを含み、かつ前記コントローラが、現在どのタイムスロットがアクティブであるかという情報及び前記タイムスロット割当てに基づいて、前記システムリソースのための要求を処理する
ことを特徴とする方法。
【請求項１５】
前記データフロー情報を決定することが、前記システムリソースへのアクセスのために前記実行装置によって使用される帯域幅情報を決定することを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記データフロー情報を決定するステップは、前記システムリソースへのアクセスのために前記実行装置によって使用される呼び出し時間の情報を決定するステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１７】
前記システムリソースのための前記時間スロット割当て及び前記システムリソースの使用可能度に基づいて、第１の実行装置からの要求が処理され得るかどうかについて決定するステップをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１８】
前記データフロー情報及び前記システムリソースに対する未実行の要求に基づいて、前記システムリソースの使用可能度を決定するステップをさらに含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
実行エンティティからの要求をスケジューリングする命令を含む記憶媒体を有する装置であって、
前記命令に基づいてプロセッサが、
システムリソースへのアクセスを含む実行エンティティから第１の要求を受信し、
前記システムリソースのための所定の他の未実行の要求が処理されたかどうかを決定するために、前記システムリソースに結合されたコントローラにアクセスし、かつ
前記システムリソースが前記第１の要求に対して利用可能であるかどうかを決する、
ことを特徴とする装置。
【請求項２０】
前記リソースが利用可能でないために前記要求を処理できないかどうか前記実行エンティティをさらに通知するように前記プロセッサを作動させるための命令を含むことを特徴とする請求項１９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
本発明は、システムにおける要求（リクエスト）の決定論的なスケジューリングに関するものである。
【背景技術】
【０００２】
システム（例えば、コンピュータ）のソフトウェアレイヤは、一般的には、オペレーティングシステム及びアプリケーションプログラムを含んでいる。アプリケーションプログラムが実行される場合、１つ或いはそれ以上のプロセス、或いは、ワーク又は実行エンティティの他の基本ユニットが構築されてもよい。マイクロソフト社からのウィンドウズ（登録商標）９５或いはウィンドウズ（登録商標）ＮＴオペレーティングシステムのような所定のオペレーティングシステムの場合には、各プロセスは、割当てられた機能を実行するためにプロセスのアドレス空間に含まれたコードを実行するワークの１つ或いはそれ以上のユニット（スレッドと呼ばれる）を含んでいてもよい。親プロセスに属するスレッドは、異なる機能を実行するように割当てられてもよい。例えば、スプレッドシートプロセスの場合、スレッドは、ユーザ入力を計算し、印刷し、受信し、ヘルプ機能等を行うように構築されてもよい。他のオペレーティングシステムの場合、タスク或いはプロセスは、中央処理装置（ＣＰＵ）によって実行するためにスケジューリングされるワーク或いは実行エンティティの基本ユニットを構成してもよい。
【０００３】
オペレーティングシステムは、複数のアクティブスレッド或いはプロセスを管理するスケジューラを含んでもよい。異なる形式のオペレーティングシステムは、異なるスケジューリング方式を有してもよい。例えば、いくつかのウィンドウズ（登録商標）オペレーティングシステムの場合、タイムスロットは、対応するスレッドが実行することができるラウンドロビン方式でアクティブスレッドに割当てられる。さらに、いくつかのウィンドウズ（登録商標）オペレーティングシステムの場合、優先順位クラスは、スレッドに割当てられてもよい。最高優先順位クラスのスレッドは、それらに割当てられたタイムスライス（より低い優先順位クラスのスレッドが後に続く）において最初に実行される。従って、いかなる特定の優先順位クラスにおいて、スケジューリングは、ラウンドロビン方法で実行されてもよい。１つ或いはそれ以上の事象が生じるまで、スレッドは実行し続ける。タイムスライスは、終了するか、或いは、スレッドは、実行する用意ができているより高い優先順位の他のスレッドによって取って代わられる。
【０００４】
異なるプロセス、スレッド、或いはワークの他のユニットは、システムリソースを異なって使用してもよい。例えば、ビデオ再生及びデコードプロセスでは、データは、コンパクトディスク（ＣＤ）或いはディジタルビデオディスク（ＤＶＤ）ドライブからシステムメモリに転送され、ＣＰＵとシステムメモリとの間で転送され、モニタ上のグラフィックスカードによって表示するためにシステムメモリからビデオメモリへ転送されてよい。一般に、ＣＤ或いはＤＶＤドライブからシステムメモリに転送されるデータは、ＣＰＵとシステムメモリとの間のデータの転送よりも遅くてもよい、グラフィックスカードとシステムメモリとの間に転送されるデータよりも遅い。このように、システムリソース（例えば、システムメモリ、バス、及び他の装置を含む）は、ワーク或いは実行エンティティの異なるユニットの要求に応じて異なって使用されてもよい。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のオペレーティングシステムは、一般的には異なるプロセス、スレッド或いはワークの他のユニットの異なるリソース要求を効率的に明らかにしない。このような従来のオペレーティングシステムは、プロセス、スレッド、ワークの他のユニットを適切なレベルでスケジュール（スケジューリング）する。すなわち、例えば、各アプリケーションに関連するプロセス、スレッド或いはワークの他のユニットは、所定の優先順位クラスに割当てられる。一般的には、ユニットのワークからの要求は、必要とされたシステムリソースが利用可能であるかどうかに関係なく、予め割当てられた優先順位及びスケジューリングプロトコルに従ってスケジュールされるようになっている。
【課題を解決するための手段】
【０００６】
概要
一般に、一実施形態では、システムは、リソースと、システムに要求を出すように構成される実行エンティティと、各実行エンティティからのリソースに対する要求に関連したスロット割当てを含む記憶ロケーション（記憶場所）とを含んでいる。コントローラは、リソースに結合され、記憶ロケーションにアクセスし、スロット割当てに従って実行エンティティからリソースに対する要求を処理するように構成される。
【０００７】
他の機能は、下記の説明及び特許請求の範囲から明らかとなるであろう。
【発明の効果】
【０００８】
本発明によれば、要求されたリソースの利用可能度及び利用の状態がスケジューラによって決定される決定方式を利用することによって、スケジューラは、実行エンティティからの要求が、要求されているエンティティの帯域幅要求及び呼び出し時間要求に従ってサービスされることをより良く保証できる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施形態に係るシステムのブロック図である。
【図２Ａ】図１のシステムのレイヤのブロック図である。
【図２Ｂ】図１のシステムのレイヤのブロック図である。
【図３】実施形態によるスケジューリングサイクルを示す図である。
【図４】図１のシステムの実施形態におけるスケジューリングモジュールのフローチャートである。
【図５】図１のシステムの実施形態における基本入力／出力システム（ＢＩＯＳ）のフローチャートである。
【図６】図１のシステムの実施形態におけるオペレーティングシステムのフローチャートである。
【発明を実施するための形態】
【００１０】
詳細な説明
本発明の実施形態によるシステムは、ファームウェアレイヤのソフトウェアによって使用されるか或いはアクセスされる。例として、システムリソースは、システムメモリ、１つ或いはそれ以上のバスと、他の装置とを含んでもよい。システムで実行する実施形態に係るスケジューラは、いくつかの実施形態では、所定のシステムリソースが利用可能であるかどうか及び要求の呼び出し時間及び帯域幅を含んでいるソフトウェアレイヤ及びハードウェアレイヤによって所定の基準に従って作成されるワーク或いは実行エンティティの基本ユニット（例えば、プロセス、タスク或いはスレッド）からの要求をスケジュールする。いつかの実施形態においては、スケジューラには、システムリソース利用可能度及び利用の状態のフィードバックが提供される。要求されたリソースの利用可能度及び利用の状態がスケジューラによって決定される決定方式を利用することによって、スケジューラは、実行エンティティからの要求が、要求されているエンティティの帯域幅要求及び呼び出し時間要求に従ってサービスされることをより良く保証できる。
【００１１】
図１を参照すると、例えば、汎用コンピュータ又は専用コンピュータ、他のマイクロプロセッサ或いはマイクロコントローラ方式システム、携帯計算装置、セットトップボックス、電気器具、ゲームシステム、或いは特定用途向け集積回路（ＡＳＩＣ）又はプログラマブルゲートアレイ（ＰＧＡ）のような制御装置を含む他のシステムであってもよいシステム１０のブロック図が示されている。
【００１２】
ここでの説明は、システム１０の種々のレイヤについての特定の構成及びアーキテクチャを参照しているけれども、記載された実施形態及び例示された実施形態に関して多数の修正及び変更が可能である。
【００１３】
図１の実施形態では、システム１０は、主メモリ（システムメモリ）１０４に結合されたメモリコントローラ１０３及びグラフィックスカード１０６に結合されたグラフィックスインタフェース１０５を含んでいるホストブリッジコントローラ１０２に結合された中央処理装置（ＣＰＵ）１００を有している。グラフィックスインタフェース１０５は、例えば、１９９８年５月に発行されたアクセレートグラフィックスポートインタフェース仕様、改訂２．０に記載のアクセレートグラフィックスポート（Ａ.Ｇ.Ｐ.）であってよい。ホストブリッジコントローラ１０２は、第２レベル（Ｌ２）キャッシュメモリ１０９を制御するためにキャッシュコントローラ１０７も含んでいる。ホストブリッジコントローラ１０２は、システムバス１１２に結合されたバスインタフェース１１１を含んでいる。なお、このバスインタフェース１１１は、一実施形態においては、１９９５年６月に発行されたＰＣＩローカルバス仕様、製造版、改訂２．１に記載されているように作動する周辺構成要素相互接続（ＰＣＩ）バスであってもよいし、他の実施形態においては、他の種類のインタフェースプロトコルであってもよい。
【００１４】
例えば、他の構成では、ホストコントローラ及びブリッジコントローラは、リンクによって結合されるメモリハブ及び入出力ハブと置き換えられてもよい。このような構成では、メモリ及びグラフィックスインタフェース回路は、メモリハブにあってもよく、ブリッジコントローラはＩ／Ｏハブであってもよい。
【００１５】
システムバス１１２は、ハードディスクドライブ１１５或いはコンパクトディスク（ＣＤ）又はディジタルビデオディスク（ＤＶＤ）ドライブ１１６のような１つ或いはそれ以上の記憶装置へのアクセスを制御する記憶装置コントローラ１１４に結合されている。ネットワークインタフェースや、周辺装置に結合されたスロット（図示せず）のような他のデバイスが、システムバス１１２に結合されてもよい。種々の他の統合レベルに従うシステムは、異なるブロックで実行されるコントローラを有してもよい。例えば、ハードディスクドライブや、ＣＤ又はＤＶＤドライブコントローラは、システムブリッジコントローラ１１０に含まれてもよい。
【００１６】
システム１０は、二次バス若しくは拡張バス１２０を有している。システムブリッジコントローラ１１０は、システムバス１１２と拡張バス１２０との間に結合されている。システムブリッジコントローラ１１０は、システムバス１１２に結合されたシステムバスインタフェース１１３及び拡張バス１２０に結合された拡張バスインタフェース１１９を含んでいる。このシステムブリッジコントローラ１１０も、１９９６年１月に発行された汎用バス仕様、改訂１．０に記載されているようにＵＳＢポート１１８に結合された汎用直列バス（ＵＳＢ）インタフェース１１７を含んでいる。拡張バス１２０は、種々の周辺装置（入力／出力装置）１２２及び不揮発性メモリ１２４に結合されている。バス、バスそのもの、及びシステムメモリに結合された構成要素及び装置は、システム１０内のワーク或いは実行エンティティのユニットのからの要求によって使用或いはアクセスされるシステムリソースの一部を形成する。
【００１７】
図２Ａ〜図２Ｂを参照すると、システム１０の種々のソフトウェアレイヤ及びハードウェアレイヤは、より詳細に示されている。例として、システム１０は、オペレーティングシステム（ＯＳ）２２０及びプロセス２２２及び２２４を含んでもよい。次の説明では、オペレーティングシステム２２０は、各プロセスが１つ或いはそれ以上のスレッドを含んでもよいあるウィンドウズ（登録商標）オペレーティングシステムのようなスレッドベースシステムであると仮定される。しかしながら、前述の実施形態による要求スケジューリング方式は、異なって構成された実行エンティティ或いはワークのユニットによってオペレーティングシステムで実行されてもよい。
【００１８】
図２Ａに示されるように、スレッド２２８及び２２９は、プロセス２２２に属し、スレッド２３０及び２３１はプロセス２２４に属する。スレッドは、オペレーティングシステムの下で規定されるアプリケーションプログラマブルインタフェース（ＡＰＩ）のような所定のインタフェースを介してオペレーティングシステム（ＯＳ）２２０と通信してもよい。それとは別に、「サードパーティ」ＡＰＩが使用されてもよい。オペレーティングシステム（ＯＳ）２２０は、所定のインタフェースを介してアクティブスレッドからの要求をスケジュールするスケジューラ２３２を有している。一実施形態では、本発明の実施形態に従ってスケジューリング動作を実行するために、スケジューラ２３２は、メモリ、Ｉ／Ｏ、システム１０の他の所定の位置にアクセスし得てハードウェア構成要素と通信するデバイスドライバ２４０に関連されていてよい。これらの要素２３２及び２４０は、ひとまとめにしてスケジューラと呼ばれる。他の実施形態では、スケジューラは、より多くのモジュール或いはレイヤに分離されてもよい。
【００１９】
スレッドからの要求を受信する際に、スケジューラ２３２は、この要求をハードウェア構成要素からのフィードバック通信、未だ実行されていない要求の数、要求スレッドの呼び出し時間及び帯域幅要求に基づいてスケジュール（スケジューリング）する。
【００２０】
一実施形態によれば、スケジューラ２３２は、所定のエンティティ数を有する要求待ち行列（キュー）２０４に要求を記憶する。要求待ち行列２０４の各エントリは、特定の要求が処理されたかどうかを示す状態フィールド２０６の状態フラグに関連してもよい。
【００２１】
デバイスドライバ２４０を介してスケジューラ２３２によってアクセスできる、システムメモリ１０４（或いは、ある他の適当な記憶ロケーション）に記憶されたテーブルのセット或いはテーブルセグメント２０２は、各々がスレッド識別子（ＩＤ）を有する対応アクティブスレッドのためのチャネル割当てを識別する。各チャネルは、クロック発生器２５０によって発生されたクロックのような基本クロックの所定サイクル数を有するものとして規定される。チャネル毎の基本クロック数は所望の細分性（グラニュラリティ）に基づいて選択される。テーブル或いはテーブルセグメント２０２の各々は、例えば、システムメモリ１０４、グラフィックスカード１０６、システムバス１１２、拡張バス１２０、ＵＳＢポート１１８等を含むシステム１０のリソースに対応する。
【００２２】
実施形態においては、ブリッジコントローラ１０２、１１０は、スレッドＩＤによって特定のスレッドに対するチャネル割当てを監視する各種のシステムリソースに対応するテーブル或いはテーブルセグメントも記憶する。ブリッジコントローラのテーブル或いはテーブルセグメントは、オペレーティングシステム（ＯＳ）２２０によって保有される対応するテーブル２０２に基づいてロードされる。例示された実施形態では、テーブル或いはテーブルセグメント３０２Ａ、３０２Ｂ、及び３０２Ｃは、システムメモリ１０４、システムバス１１２、及びグラフィックスカード１０６のそれぞれに対するチャネル割当てを監視するためにホストブリッジコントローラ１０２によって記憶されてもよい。システムブリッジコントローラ１１０は、ＵＳＢポート１１８及び拡張バス１２０に対するチャネル割当てを監視するためにテーブル或いはテーブルセグメント３０２Ｄ及び３０２Ｅを記憶してもよい。他のテーブルも他のシステムリソースのために保有されてもよい。
【００２３】
ブリッジコントローラ１０２、１１０に記憶されているものとして示されているけれども、テーブル３０２Ａ〜３０２Ｅは、システムメモリ１０４或いは外部記憶装置のような他の適当な位置に記憶されてもよい。それとは別に、異なるシステムリソースは、図示されるようにブリッジコントローラ１０２、１１０に統合されるよりもむしろシステム中に配設されたコントローラによって制御されてもよい。
【００２４】
テーブル３０２Ａ〜３０２Ｅは、チャネル割当て変更としてオペレーティングシステム（ＯＳ）２２０によって周期的に更新されてもよい。テーブル３０２Ａ〜３０２Ｅの各々において、スレッドは同じ或いは異なる数のチャネルを割当てられてもよい。例えば、第１のスレッドＩＤに関連したスレッドは第１のチャネル数を割当てられてもよいし、第２のスレッドＩＤに関連したスレッドは異なるチャネル数を割当てられてもよい。
【００２５】
テーブル３０２Ａ〜３０２Ｅのスレッドに割当てられたチャネルは、図３に示されるように全スケジューリングサイクル４００内のスレッド要求実行ウィンドウ或いはスロットを規定する。スケジューリングサイクル４００は、各々が割当てられたチャネル数を含む複数のスレッド要求実行ウィンドウ或いはスロット４２０0、４０２1、．．．、４０２N-1、及び４０２Nを含んでいる。各要求実行ウィンドウ４０２は、スレッドからの要求の実行に割当てられる。
【００２６】
一実施形態では、第１のウィンドウ４２０0は、ブリッジコントローラ１０２、１１０のＯＳテーブル２０２と対応するテーブル３０２との間のコヒーレンシー（coherency）を保持するスケジューラ２３２に割当てられる。残りのウィンドウ４０２1〜４０２Nは、種々の他のスレッドからの要求に割当てられてもよい。例示された実施形態では、テーブル３０２Ａ〜３０２Ｅは、コピーレンシー・ウィンドウズ（登録商標）４２０0のスケジューリングサイクル４００毎に１回、スケジューラ・デバイスドライバ２４０によって更新される。コヒーレンシー・ウィンドウ４２０0の時間中、或いは、それとは別に他のウィンドウ４０２iでは、スケジューラ・デバイスドライバ２４０は、また、どの要求が完了したかを決定するためにブリッジコントローラ１０２、１１０の状態レジスタ３０４Ａ〜３０４Ｅの内容を読み出してもよい。従って、スケジューラ２３２は、どのシステムリソースが利用可能であるか監視をすることができるようにどの要求が完了され、どの要求が未だ実行されていないかについての情報がフィードバックされるように構成されている。このように、スレッドからの要求がスケジューラ２３２によって受信される場合、スケジューラ２３２は、十分なリソースが要求を処理するために利用可能であるかどうかを決定できる。
【００２７】
再度、図２Ａ及び図２Ｂを参照すると、実施形態によれば、ブリッジコントローラ１０２、１１０の各々は、システム１０の種々のリソースに対する要求を記憶する種々の呼び出し時間を含んでいる。例として、ホストブリッジコントローラ１０２は、メモリコントローラ１０３のメモリ待ち行列３１０を有している。ＣＰＵバスインタフェース３１２を介して接続されたＣＰＵ１００、及び、システムバスインタフェース１１１を介して接続されたシステムバス１１２上の各種のデバイスをそれぞれ含むシステム１０の種々のソースからメモリコントローラ１０３によって受信された要求は、実行するためにメモリ待ち行列３１０に記憶される。メモリアドレス及びデータ情報に加えて、メモリ待ち行列３１０は、また、メモリ要求の関連ＩＤを記憶するように構成されている。
【００２８】
本発明のいくつかの実施形態では、ＣＰＵ１００は関連スレッドＩＤとともに命令をフェッチ（命令取り出し動作）する。スレッドＩＤは、ブリッジコントローラ１０２、１１０に送られ、ブリッジコントローラ１０２、１１０の待ち行列に記憶される。
【００２９】
ホストブリッジコントローラ１０２のスケジューラコントローラ３１４は、カウンタ３０６及びテーブル或いはテーブルセグメント３０２Ａ〜３０２Ｃからの出力値を受信する。クロック発生器２５０からの基本クロックによってクロックされるカウンタ３０６は、スケジューリングサイクル４００でチャネルを通して計数するように構成されてもよい。カウンタ３０６の値に基づいて、スケジューラコントローラ３１４は、スケジューリングサイクル４００の範囲内で現スレッド要求実行ウィンドウ４００i（ｉ＝０〜Ｎ）を決定できる。どのウィンドウ４００iがアクティブであるか、並びに、テーブル３０２Ａのチャネル割当てに基づいて、メモリ待ち行列３１０の対応するスレッドＩＤに関連した要求がメモリコントローラ１０３によって処理するために選択されてもよい。
【００３０】
選択された要求は、現ウィンドウ４００i内で実行される。要求の完了の際に、ホストブリッジコントローラ１０２は、状態レジスタ３０４Ａの適切なビットをプログラミングすることによって要求完了状態に戻してもよい。次のコヒーレンシー・ウィンドウ４０２0では、スケジューラ・デバイスドライバ２４０の制御の下でＣＰＵ１００は、状態レジスタ３０４Ａ（並びに他の状態レジスタ３０４Ｂ〜３０４Ｅ）を読み出し、どの要求が完了したかを決定する。次に、スケジューラ・デバイスドライバ２４０は、要求待ち行列２０４の完了要求のフラグ２０６を更新する。
【００３１】
メモリ待ち行列３１０に加えて、一実施形態のホストブリッジコントローラ１０２は、また、システムバスインタフェース１１１のシステムバス待ち行列３１６及びグラフィックスインタフェース１０５のグラフィックスカード要求待ち行列３１８を含んでいてよい。システムバス１１２に対する要求は、システムバス待ち行列３１６に入れられるのに対して、グラフィックスカード１０６に対する要求は、グラフィックスカード待ち行列３１８に入れられる。要求はスレッドＩＤに関連しているので、スケジューラコントローラ３１４は、現スレッド要求実行ウィンドウ４０２i及びテーブル３０２Ｂ，３０２Ｃに記憶されたチャネル割当てに基づいて、バスインタフェース１１１或いはグラフィックインタフェース１０５による適切な処理を選択できる。待ち行列３１６及び３１８の要求の完了は、状態レジスタ３０４Ｂ及び３０４Ｃのそれぞれによって示される。
【００３２】
同様に、システムブリッジコントローラ１１０は、拡張バス１２０に供給される要求を記憶する拡張バス待ち行列３２０と、ＵＳＢポート１１８に供給すう要求を記憶するＵＳＢバス待ち行列３２２とを含んでいる。クロック発生器２５０からの基本クロックによってクロックされるカウンタ３０８は、スケジューリングサイクル４００のチャネルを計数する。カウンタ３０８によって示されるような現スレッド要求実行ウィンドウ４０２i、及び、テーブル３０２Ｄ，３０２Ｅに記憶されたチャネル割当てに基づいて、システムブリッジコントローラ１１０のスケジューラコントローラ３２４は、待ち行列３２０及び３２２それぞれの要求の中のどれが処理されるべきであるかを決定する。要求の完了は、状態レジスタ３０４Ｄ，３０４Ｅによって示される。
【００３３】
図４に示すように、スケジューラ２３２と協動するスケジューラ・デバイスドライバ２４０は、（ステップ５０２において）所定のイベントの受信を待つ。アプリケーション・プログラマブル・インタフェース（ＡＰＩ）呼び出しの形であってもよい、スレッドからの要求が、受信された場合、スケジューラ・デバイスドライバ２４０は、（ステップ５０４において）要求待ち行列２０４及びチャネル割当てテーブル２０２にアクセスするので、スケジューラ２３２は、リソースがスレッド要求を処理するために利用可能であるかどうかを（ステップ５０６において）決定することができる。
【００３４】
リソースが要求を適切に処理するために利用可能でないことをスケジューラ２３２が決定する場合には、要求されているスレッドが（ステップ５０８において）通知される。この通知に応じて、スレッドは、要求を再度出す前に若干の時間だけ待つことができるか、或いは、スレッドは、さもなければこの状態を特に適切に処理できる。要求されたリソースが利用可能である場合には、スレッドからの要求は、要求待ち行列２０４に（ステップ５１０において）加えられる。
【００３５】
スケジュール待ち行列２０４の特定要求が処理され、完了される場合、待ち行列２０４のフラグフィールド２０６の全フラグは、前述のように設定されてもよい。
【００３６】
スケジューラ・デバイスドライバ２４０そのものは、要求待ち行列及びスレッドチャネル割当てテーブルに対応するメモリ位置にアクセスするような要求を出すことができるスレッドである。（ステップ５２０において）要求待ち行列２０４に入れられたスケジュール・デバイスドライバ・スレッドからの要求は、スケジュールサイクル４００の第１のウィンドウ４０２0で処理されてもよい。それに代えて、他のウィンドウ４０２iは、スケジューラ・デバイスドライバ２４０に割当てられてもよい。
【００３７】
コヒーレンシー・ウィンドウ４０２0の期間中、スケジューラ・デバイスドライバ２４０の制御の下でのＣＰＵ１００は、必要に応じてブリッジコントローラテーブル３０２Ａ〜３０２Ｅを（ステップ５２２において）更新し、チャネル割当てを変える。ＣＰＵ１００は、（ステップ５２４において）どの要求が完了されたかを決定するために状態レジスタ３０４Ａ〜３０４Ｅにアクセスしてもよい。それに代えて、テーブル更新動作及び状態レジスタ読み出し動作が別々に行われてもよい。次に、デバイスドライバ２４０の制御の下でのＣＰＵ１００は、（ステップ５２６において）要求待ち行列２０４を更新してもよい。
【００３８】
スケジューラ２３２は、要求そのもの及びＡＰＩ呼出しのパラメータのような要求パラメータを調べることによって、何のシステムリソースが要求によって求められているかを決定することができる。例えば、パラメータは、システムメモリ１０４のメモリアドレス空間の位置へのアクセスを指定してもよい。他のパラメータは、ＵＳＢポート１１８に結合されたＵＳＢバス上のグラフィックスカード１０６のバス１１２、１２０の中の１つにあるＩ／Ｏアドレス空間の位置或いはシステム１０の他の位置を指定してもよい。要求リソース、待ち行列２０４に既にある要求、及びスケジューラ・デバイスドライバ２４０によって検索されるようなテーブル或いはテーブルセグメント２０２に指定されたチャネル割当てに基づいて、スケジューラ・デバイスドライバ２３２は、要求がある程度妥当な方法で処理されてよいかどうかを決定することができる。これは、システム１０に予めプログラム化され、起動ルーチン（例えば、基本入出力システム或いはＢＩＯＳルーチン）によってロードされる基準に従って規定されてもよい。スケジューラ２３２は、システムの種々のスレッドの呼び出し時間要求及び帯域幅要求を認識している。呼び出し時間要件及び帯域幅要件は、十分なリソースがスレッド要求を満たすために利用可能であるかどうかを決定するためにスケジューラ２３２によって使用されてもよい。
【００３９】
一例として、スレッドは、グラフィックスカード１０６のビデオメモリからのビデオデータのフレームをシステムメモリ１０４に転送する要求を出してもよい。フレームサイズ（例えば、７２０×４８０ピクセル）及び各ピクセルに対して規定された多数のビットが与えられると、ビデオ転送の帯域幅要求は、転送が発生しなければならない特定の時間に基づいて決定されてもよい。さらに、転送要求の呼び出し時間は既知であってよい。帯域幅及び呼び出し時間情報に基づいて、及び未だ実行されていないリソースに対する未実行の要求に基づいて、スケジューラ２３２は、ビデオ転送要求が利用可能なリソースによって処理できるかどうかを決定することができる。処理できない場合には、スレッドはスケジューラ２３２によって知らされ、スレッドは、他の要求を出す前に或いは要求をいくつかの部分に分割する前に待機することを含む多数の方法の１つで応答してよい。
【００４０】
図５に示すように、システム初期化は、実施形態によるシステムＢＩＯＳルーチンによって実行される。システムリセットによりシステムハードウェアが初期状態にされた後に、ＣＰＵ１００は、システム１０の構成要素を既知の状態に初期設定し、使用するオペレーティングシステム（ＯＳ）２２０のためのシステム構成情報を構成する責務を持つＢＩＯＳの電源オン自己試験（ＰＯＳＴ）手順の命令を実行し始める。いくつかの初期化タスクがシステム１０で（ステップ６０２において）実行され、ＢＩＯＳルーチンは、次に、システムメモリ１０４或いは他の適当な記憶ロケーションを（ステップ６０４において）設定し、チャネル割当てテーブル或いはテーブルセグメント２０２を記憶する。ＢＩＯＳルーチンは、各チャネルに対する基本クロック数（例えば、チャネル毎に１クロック或いは数クロック）及びスケジュールサイクル４００の全幅を指定してもよい。特定のメモリアドレスは、テーブル或いはテーブルセグメント２０２を記憶するために予約されていてもよい。さらに規準は、スレッド要求を受諾するか或いは拒否するかどうかを決定する際に、スケジューラ２３２によって使用するために指定されてもよい。
【００４１】
次に、デフォルトチャネル割当ては、（ステップ６０６において）テーブルにロードされてもよい。例えば、オペレーティングシステム（ＯＳ）に関連した所定のスレッド（例えば、スケジューラ及び他のシステム管理レイヤ）は、サイクル４００でウィンドウに割当てられる。さらに、ＢＩＯＳは、特定のウィンドウに割り当てられないスレッド要求を処理するために所定数のチャネルを有するデフォルトウィンドウを設定してもよい。ＢＩＯＳは、プロセッサがマルチ処理システムである場合に利用可能なプロセッサの型式を決定するシステムの構成空間及び他の情報をポーリングできる。この情報から、ＢＩＯＳはシステムの通信処理能力を決定できる。このような決定された通信処理能力に基づいて、ＢＩＯＳは、それに応じてデフォルトウィンドウのチャネル数を割当てることができる。次に、システム構成要素は、（ステップ６０８において）ＢＩＯＳルーチンによって初期化され、構成される。次に、オペレーティングシステム（ＯＳ）２２０は（ステップ６１０において）ブート（起動）される。
【００４２】
図６に示すように、オペレーティングシステム（ＯＳ）２２０がブートされた後に、オペレーティングシステム（ＯＳ）２２０は、（ステップ６５０において）システム１０におけるいくつかのアクティブスレッドを識別する。オペレーティングシステム（ＯＳ）２２０は、（ステップ６５２において）システム１０のリソースに対するその帯域幅要求及び呼び出し時間要求に対する各スレッドを照会する。いくつかのスレッドは、どのような呼び出し時間要求及び帯域幅要求が各システムリソースに対してあるかを認識している。例えば、マルチメディアプロセスに関連したスレッドは、データ転送に対する比較的小さい呼び出し時間を許容できる、高いデータ転送スループットを必要とする「実時間」要求を有してもよい。他のスレッドは、より高い呼び出し時間、及び、より低いデータ転送帯域幅を許容することができるものであってよい。アクティブスレッドからの異なる呼び出し時間要求及び帯域幅要求の比較に基づいて、異なるスレッドに対応する異なる要求ウィンドウ４０２iを割当てるいくつかのチャネルは、より低い呼び出し時間及びより高い帯域幅を有するスレッドを促進するためにオペレーティングシステム（ＯＳ）によって（ステップ６５４において）セットされてもよい。結果として、これらの種類のスレッドは、多数のチャネル及び多分複数のウィンドウ４０２iを割当てられてもよい。多数の割当てられたウィンドウ４０２iは、スケジューリングサイクル４００で連続してもよいし或いは分散されてもよい。スレッドが、システムリソースに対する呼び出し時間及び帯域幅情報を供給しない場合には、このスレッドは、テーブル或いはテーブルセグメント２０２のスケジューリングサイクル４００でデフォルトウィンドウ４０２iに割当てられてもよい。
【００４３】
算定された数のチャネルに基づいて、テーブル或いはテーブルセグメント２０２は、スレッドＩＤに従ってチャネル割当てで（ステップ６５６において）ロードされてもよい。
【００４４】
従って、いくつかの実施形態によれば、スケジューリング方式は、データフロー要求がリソースの利用可能度及びチャネル割当てに基づいて満たされてもよいかどうかを決定することによって、システムのスレッドからの要求をスケジュール（スケジューリング）する。リソースの利用可能度は、ハードウェア要求によってシステムのスケジューラに示される。さらに、要求の種類及び要求パラメータに基づいて、スケジューラは、どのようなリソースが特定の要求によって必要とされるかを決定することができる。
【００４５】
他の実施形態は、上記の特許請求の範囲内にある。例えば、異なるオペレーティングシステムの場合には、システムにおけるワーク或いは実行エンティティの基本ユニットは、スレッドでなくてもよくプロセス或いは他の規定ユニットであってもよい。さらに、システムのハードウェア構成要素は異なって構成されてもよい。ソフトウェア或いは図示のファームウェアモジュール或いはレイヤによって実行された動作は、変更されてもよい。
【００４６】
本発明は、限られた数の実施形態に関して開示されているが、当業者は、それらからの多数の修正及び変更を理解するであろう。添付された特許請求の範囲が本発明の真の精神及び範囲内にあるような全ての修正及び変更を含むことが意図される。
【図１】
2010044784.tif 000003
【図２Ａ】
2010044784.tif 000004
【図２Ｂ】
2010044784.tif 000005
【図３】
2010044784.tif 000006
【図４】
2010044784.tif 000007
【図５】
2010044784.tif 000008
【図６】
2010044784.tif 000009
【手続補正書】
【提出日】平成21年11月12日(2009.11.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
リソースと、
前記リソースに要求を出すように構成される、異なる呼び出し時間要求及び帯域幅要求を有する複数の実行エンティティと、
各実行エンティティからの前記リソースに対する要求に関連するスロット割当てを含む、オペレーティングシステムに関連する記憶ロケーションと、
各実行エンティティからの前記リソースに対する要求に関連するスロット割当てを記憶するブリッジコントローラであって、前記リソースに結合され、前記実行エンティティの呼び出し時間要求及び帯域幅要求に基づいてスロットに優先順位をつけ、かつ、前記スロット割当てにアクセスし、前記スロット割当に従って前記実行エンティティからの前記リソースに対する要求を処理するように構成されるコントローラを含むブリッジコントローラと、
をそれぞれ備えることを特徴とするシステム。
【請求項２】
前記記憶ロケーションのスロット割当てを更新するように構成されたスケジューラをさらに含むことを特徴とする請求項１に記載のシステム。
【請求項３】
前記スケジューラによってアクセスでき、かつ、前記実行エンティティためのスロット割当てを含む第２の記憶ロケーションをさらに含むことを特徴とする請求項２に記載のシステム。
【請求項４】
前記リソースが前記第２の記憶ロケーションのスロット割当て及び未実行の要求に基づいて実行エンティティによって出された要求に対して利用可能であるかどうかについて、前記スケジューラが決定するように構成されることを特徴とする請求項３に記載のシステム。
【請求項５】
前記スケジューラが、各実行エンティティのリソースに対する帯域幅を認識しており、かつ、前記スケジューラが、前記帯域幅の情報に基づいて実行エンティティによって出された要求に対して利用可能であるかどうかを決定するように構成されていることを特徴とする請求項４に記載のシステム。
【請求項６】
前記要求が、１つ或いはそれ以上のパラメータに関連したアプリケーションプログラマブルインタフェース呼び出しを含むことを特徴とする請求項４に記載のシステム。
【請求項７】
前記スケジューラが、要求が処理されたかどうかを決定するために前記コントローラにアクセスするように構成されていることを特徴とする請求項２に記載のシステム。
【請求項８】
どのスロットがアクティブであるかどうかを決定するためにコントローラによってアクセスできるカウンタをさらに含むことを特徴とする請求項１に記載のシステム。
【請求項９】
各スロットが、１つ或いはそれ以上のチャネルを含み、前記カウンタが、前記チャネルを計数するように構成されることを特徴とする請求項８に記載のシステム。
【請求項１０】
複数のスロットが、スケジューリングサイクルで規定され、かつ、前記コントローラが、対応するスロットにおいて前記実行エンティティからの要求を処理するように構成されることを特徴とする請求項１に記載のシステム。
【請求項１１】
リソース使用要求を決定するために実行装置と協働するオペレーティングシステムと、 前記オペレーティングシステムによって更新可能であり、その割当てられたチャネルの期間中にシステムリソースにアクセスできる実行装置の前記リソース使用要求に基づいて、チャネルを前記実行装置に割当てる記憶ロケーションとを含むことを特徴とする請求項１に記載のシステム。
【請求項１２】
前記実行エンティティが、前記リソースのための帯域幅の情報を前記オペレーティングシステムに通信するように構成されていることを特徴とする請求項１１に記載のシステム。
【請求項１３】
前記実行エンティティが、前記リソースのための呼び出し時間の情報を前記オペレーティングシステムにさらに通信するように構成されていることを特徴とする請求項１２に記載のシステム。