(57)【要約】本発明は、サービス品質保証に適合するリソース３５をスケジューリングする方法及び装置に向けられる。３つのレベルの優先順位を有する一実施形態において、第１の優先レベル１５のチャンネルがバンド幅割り当て内にある場合、そのチャンネルから要求が発行される。割り当て内にある第１の優先レベルでのチャンネル内に何の要求もない場合、そのバンド幅割り当て内にある第２の優先レベル２０でのチャンネルからの要求が選択される。ここでも何の要求がなければ、第３の優先レベル２５でのチャンネルからの要求、又はバンド幅割り当て外にある第１及び第２のレベルでのチャンネルからの要求が発行される。本システムはレート型スケジューリングを用いて実行されることができる。【選択図】図１
2005505857.tif 000002
【特許請求の範囲】
【請求項１】
リソースが要求をサービス可能であるかを判断し、
リソースバンド幅が使用できる場合であって、
（ａ）第１のレベルの少なくとも１つのチャンネルが、少なくとも１つの要求を含み、かつ割り当て内である場合は、前記第１のレベルの少なくとも１つのチャンネルから少なくとも１つの要求を発行し、
（ｂ）前記第１のレベルのチャンネルが、少なくとも１つの要求を含まず、かつ割り当てを超える場合、及び第２のレベルのチャンネルが少なくとも１つの要求を含む場合は、前記第２のレベルのチャンネルから要求を発行することを含む方法。
【請求項２】
前記第１のレベルのチャンネルが、少なくとも１つの要求を含まず、かつ割り当てを超える場合、及び第２のレベルのチャンネルが少なくとも１つの要求を含まず、かつ割り当てを超える場合、及び第３のレベルのチャンネルが少なくとも１つの要求を含む場合は、前記第３のレベルのチャンネルから要求を発行することを特徴とする請求項１に記載の方法。
【請求項３】
第１のレベルのチャンネルが、少なくとも１つの要求を含み、かつ割り当てを超える場合は、前記第１のレベルのチャンネルが割り当て内にある間は前記第２のレベルのチャンネルから要求を発行し、割り当て内で動作するとき前記第１のレベルのチャンネル要求に優先度を付与することを特徴とする請求項１に記載の方法。
【請求項４】
第１のレベルのチャンネルが割り当てを超える場合は、前記第１のレベル及び前記第２のレベルに第３のレベルの低い優先度を有したチャンネルを再割り当てし、その結果、第２のレベルのチャンネル要求後、前記第１のレベルのチャンネル要求を発行することを特徴とする請求項１に記載の方法。
【請求項５】
前記第１のレベルの元々のチャンネル、及び前記第３のレベルでの現在のチャンネルが、割り当て内で動作している場合、前記チャンネルを前記第１のレベルへ再割り当てすることを特徴とする請求項４に記載の方法。
【請求項６】
要求に関する少なくとも１つのスケジューリング経緯を参照することを更に含み、前記発行は、前記少なくとも１つのスケジューリング経緯に基づくことを特徴とする請求項１に記載の方法。
【請求項７】
前記レベルは、サービス品質保証（ＱＯＳ）を表わすことを特徴とする請求項１に記載の方法。
【請求項８】
前記レベルは、優先チャンネル、割り当てバンド幅チャンネル、及びベスト・エフォートチャンネルからなる集合より特徴づけられたチャンネルを表わすことを特徴とする請求項１に記載の方法。
【請求項９】
前記少なくとも１つのチャンネルは複数の要求を含み、チャンネル内の要求発行を命じることは、前記チャンネルから前記リソースへの実質的に独立した要求発行あることを特徴とする請求項１に記載の方法。
【請求項１０】
リソースが要求をサービス可能であるかを判断し、
リソースバンド幅が使用できる場合であって、
（ａ）第１のレベルの少なくとも１つのチャンネルが、少なくとも１つの要求を含み、かつ割り当て内である場合は、前記第１のレベルの少なくとも１つのチャンネルから少なくとも１つの要求を発行し、
（ｂ）前記第１のレベルのチャンネルが、少なくとも１つの要求を含まず、かつ割り当てを超える場合、及び前記第１のレベルよりも低い優先度を有する第２のレベルのチャンネルが少なくとも１つの要求を含む場合は、前記第２のレベルのチャンネルから要求を発行し、
第１のレベルのチャンネルが、少なくとも１つの要求を含まず、かつ割り当てを超える場合、及び前記第２のレベルのチャンネルが少なくとも１つの要求を含まない場合は、割り当てを超える前記第１のレベルのチャンネルから要求を発行することを含む方法。
【請求項１１】
前記第１のレベルのチャンネルが、少なくとも１つの要求を含まず、かつ割り当てを超える場合、及び前記第２のレベルのチャンネルが、少なくとも１つの要求を含まず、かつ割り当てを超え、及び第３のレベルのチャンネルが少なくとも１つの要求を含む場合、前記第１のレベル及び第２のレベルよりも優先度の低い前記第３のレベルは、前記第３のレベルのチャンネルから要求を発行することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記第１のレベルのチャンネルが少なくとも１つの要求を含み、かつ割り当てを超える場合、前記第１のレベルのチャンネルが割り当て内にあるまで、前記第２のレベルのチャンネルから要求を発行し、前記第１のレベルのチャンネルの要求は、割り当て内で動作するときには所与の優先度であることを特徴とする請求項１０に記載の方法。
【請求項１３】
前記第１のレベルのチャンネルが割り当てを超える場合、前記第１のレベル及び第２のレベルよりも優先度の低い第３のレベルに前記チャンネルを再割り当てし、その結果、前記第１のレベルのチャンネルの要求が、前記第２のレベルのチャンネルの要求後に発行されることを特徴とする請求項１０に記載の方法。
【請求項１４】
前記第１のレベルの本来のチャンネル、及び前記第３のレベルでの現在のチャンネルが、割り当て内で動作している場合、前記チャンネルを前記第１のレベルへ再割り当てすることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記第１のレベルのチャンネルが優先チャンネルを含み、前記第２のレベルのチャンネルが割り当てバンド幅チャンネルを含み、前記第３のレベルのチャンネルがベスト・エフォートチャンネルを含むことを特徴とする請求項１１に記載の方法。
【請求項１６】
複数のレベルのチャンネルからの要求を受信するために結合された調整器であって、各レベルは、リソースが処理する要求伝達を制御するように構成された少なくとも１つのチャンネルを含み、前記調整器は、リソースが要求をサービスできるかどうかを判断するように構成され、そしてリソースバンド幅が使用可能で、かつ第１のレベルの少なくとも１つのチャンネルが、少なくとも１つの要求を含みかつ割り当て内である場合、前記調整器は、前記第１のレベルの少なくとも１つのチャンネルから少なくとも１つの要求の発行を制御し、そして前記第１のレベルのチャンネルが、少なくとも１つの要求を含まずかつ割り当てを超え、かつ第２のレベルのチャンネルが少なくとも１つの要求を含む場合、前記調整器は、前記第２のレベルのチャンネルから少なくとも１つの要求の発行を制御することを特徴とする調整器。
【請求項１７】
各レベルは、サービス品質（ＱＯＳ）保証の優先度を表わしていることを特徴とする請求項１６に記載の調整器。
【請求項１８】
前記チャンネル用のスケジューリング経緯及びサービス品質（ＱＯＳ）保証の特定をさらに含み、スケジューリング経緯及びＱＯＳ保証に基づいて、少なくとも１つの要求の発行を制御することを特徴とする請求項１６に記載の調整器。
【請求項１９】
前記スケジューリング経緯がバンド幅を使用することを含み、チャンネルのバンド幅使用経緯の軌跡を維持するために連結されたカウンタを更に含むことを特徴とする請求項１６に記載の調整器。
【請求項２０】
前記スケジューリング経緯がバンド幅を使用することを含み、前記調整器がサチュレーションロジック（saturation logic）を更に含み、その結果、チャンネルのバンド幅を使用することの経緯が、サチュレーションの使用値によって特定された範囲内であることを特徴とする請求項１６に記載の調整器。
【請求項２１】
前記連結されたカウンタは、レートカウンタ及び割り当てカウンタを含み、前記レートカウンタは単位サイクルごとに増分し、前記割り当てカウンタは確定されたレートカウンタ数ごとに増分するとともに、要求が前記チャンネルから受信されるごとに減分されることを特徴とする請求項１６に記載の調整器。
【請求項２２】
前記第１のレベルのチャンネルが少なくとも１つの要求を含まず、かつ割り当てを超える場合、前記第２のレベルのチャンネルが少なくとも１つの要求を含まず、かつ割り当てを超える場合、前記第３のレベルのチャンネルが少なくとも１つの要求を含む場合、前記第３のレベルのチャンネルからの要求を発行するよう構成されていることを特徴とする請求項１６に記載の調整器。
【請求項２３】
動的ランダムアクセスメモリ（ＤＲＡＭ）への要求を調整することを特徴とする請求項１６に記載の調整器。
【請求項２４】
リソースからサービスのための少なくとも１つの要求を含む少なくとも１つの優先チャンネルと、前記優先チャンネルは規定された第１の割り当てを供給し、
前記リソースからサービスのための少なくとも１つの要求を含む少なくとも１つの割り当てバンド幅チャンネルと、前記割り当てバンド幅チャンネルは規定された第２の割り当てを供給し、
レート型スケジューリング処理を用いて、要求の順序を判断するように構成されたロジックを含む調整器とを含むことを特徴とするシステム。
【請求項２５】
前記リソースが、動的ランダムアクセスメモリ（ＤＲＡＭ）であることを特徴とする請求項２４に記載のシステム。
【請求項２６】
前記レート型スケジューリング処理は、単位サイクルごとにレートカウンタを増分すること、確定されたレートカウンタ数ごとに第１の割り当てカウンタを増分すること、優先チャンネル要求が受信されるごとに前記第１の割り当てカウントを減分することを含み、前記第１の割り当てカウントが特定の閾値を下回る場合、前記割り当てバンド幅チャンネルからの要求が、前記優先チャンネルからの要求前に処理されることを特徴とする請求項２４に記載のシステム。
【請求項２７】
前記閾値がサチュレーション値に一致し、前記第１の割り当てカウントが、サチュレーション正値及びサチュレーション負値の少なくとも１つをサチュレートすることを特徴とする請求項２６に記載のシステム。
【請求項２８】
前記調整器がレートカウンタ及び割り当てカウントを含み、前記レートカウンタは単位サイクルごとに増分し、前記割り当てカウンタは確定されたレートカウンタ数ごとに増分するとともに、要求が前記チャンネルから受信されるごとに減分されることを特徴とする請求項２４に記載のシステム。
【請求項２９】
前記割り当てカウンタはサチュレーション値でサチュレートし、その結果、前記割り当てカウンタ値は、サチュレーション正値及びサチュレーション負値によって定義された範囲内にあることを特徴とする請求項２８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、個別のサービス品質を提供するためにリソースへのアクセスをスケジュール設定するシステムに関し、このリソースにアクセスする２以上の要求側が競合する場合についてのものである。
【背景技術】
【０００２】
コンピュータシステムの場合、所定のリソース（システムバス、メモリバンク等）が、そのリソースを使用したいと望む競合する要求装置又はプロセス（”要求側”）の間で共有されることは普通である。したがって、リソースに対する同時かつ競合する要求がある場合、要求側がリソースへアクセス可能であるかを決定するために、このリソースへのアクセスを調整する必要がある。システムが正しく動作できるようにするため、各要求側がそれぞれのサービス品質（ＱＯＳ）保証を指定できることが望ましい。ＱＯＳ保証の例は、データバンド幅及び待ち時間を含む。例えば、プロセッサが非常に高い優先順位を持てることが望ましく、これによりメモリシステムにアクセスする待ち時間が少なくなる。別の例では、システムバス上に予備のバンド幅をもつビデオシステムが要求され、固定フレームレートで要求された場合にビデオスクリーンを更新することができる。
【０００３】
ＱＯＳ保証の提供をめざす既存の調整スキームは、固定優先での調整、及び時分割多重方式（time division multiplexing）を含む。固定優先での調整の場合、各要求側は、固定優先で割り当てられ、優先順位どおりにサービスされる。時分割多重方式の場合、リソースにアクセス可能な間、固定的に設定されたアクセス時間が各要求側に予め割り当てられる。これらの調整スキームは、所定のシステムの場合にそれらの価値が見出せるのだが、それぞれのＱＯＳ要求があって、要求到達時間を予測できない混合した要求側が存在するような場合には、ＱＯＳ保証を提供することにならない。例えば、各イニシエータの正確な要求パターンが前もって既知でない限りは、固定優先での調整が使用される場合、複数の異なる要求側に対して任意の種類のバンド幅保証を付与することは不可能である。要求の到達時間が決定的でない場合、又要求の種類又は他の要求の最新経緯に左右されるリソースからのサービス時間量とは異なる要求が必要である場合、時分割多重方式は非効率である。
【０００４】
必要とされる要件は、異なる要求側へそれぞれのＱＯＳ保証を提供できるリソーススケジューリングスキームであり、更に、非決定的な到着及びサービス時間を効率的に処理することができることである。
【０００５】
（発明の概要）
本発明は、サービス品質保証に適合するリソースをスケジューリングする方法及び装置に向けられる。３つのレベルの優先順位を有する一実施形態において、第１の優先レベルのチャンネルがバンド幅割り当て内にある場合、そのチャンネルから要求が発行される。割り当て内にある第１の優先レベルでのチャンネル内に何の要求もない場合、そのバンド幅割り当て内にある第２の優先レベルでのチャンネルからの要求が選択される。ここでも何の要求がなければ、第３の優先レベルでのチャンネルからの要求、又はバンド幅割り当て外にある第１及び第２のレベルでのチャンネルからの要求が発行される。レート型スケジューリングを用いて本システムを実行する。
【０００６】
（発明の詳細な説明）
本発明のオブジェクト、特徴、及び利点は、以下の詳細な説明から明らかになるであろう。
図１は、調整システムの一実施形態を示している。個々の要求装置又はプロセスから要求１０が到着し、チャンネルに格納される。例えば、チャンネル１５，２０，２５がそのように意図されていて、論理的且つ物理的に実行される。本実施形態の場合、各チャンネルが１つの要求側からの要求を受け入れる。したがって、装置Ａからの要求がチャンネル０（１５）に格納され、装置Ｂからの要求がチャンネル１（２０）に格納される。本実施形態では、受信された各チャンネルの順序で各チャンネル内の要求がサービスされることを仮定としているが、これは本発明にとって必須要件ではない。
【０００７】
調整ユニット３０が、各チャンネルによるリソース３５へのスケジューリングアクセスを担当する。メモリなどを含む様々な個々の装置又はプロセスがリソースである。調整ユニット３０は、サービス品質構成ユニット（ＱＯＳユニット）４０を用いて、それぞれのチャンネルにとって所望のサービス品質（ＱＯＳ）保証により構成される。ＱＯＳは、個々のデータフロー、プロセス、又は装置のための１以上の最小、最大、又は実行範囲の基準を包含する様々な基準を含むことができる。また、調整ユニット３０は、スケジューリング経緯ユニット４５を用いて、最新のスケジューリング決定の軌跡を維持する。ＱＯＳユニット４０及びスケジューリング経緯ユニット４５が分離したユニットとして示されているが、ＱＯＳユニット４０及びスケジューリング経緯ユニット４５の片方又は両方の機能が、調整ユニット３０の部分として構成されたり、調整ユニット３０と結びついて１つのユニットに結合されたりもする。さらに、１以上のユニット３０，４０，４５が、リソース３５の物理的な部分とすることもできる。
【０００８】
１以上のチャンネル１５，２０，２５が、サービスを待つ要求を持つ場合、調整ユニット３０は、続けてサービスできるチャンネルを選択し、スケジューリング経緯ユニット４５及びＱＯＳユニット４０からそれぞれ再生したスケジューリング経緯及び所望のＱＯＳ情報を用いる。選択されたチャンネルの次の要求は、リソースにアクセスし、システムを終了することへと進行する。
【０００９】
ある実施形態において、調整ユニット３０は、所定のＱＯＳ保証に適合できるかどうかを判断するためにスケジューリング経緯ユニット４５を用いる。例えば、リソースへアクスするために必要な時間量を、リソースに対するアクセスの相対タイミング又は要求の種類に依存させることができる。例えば、双方向システムバスにアクセスするとき、読み出し要求にアクセスした直後では、まずバス方向が方向転換する必要があるので、書き込み要求がバスにアクセスするのに時間がかかる。スケジューリング経緯ユニット４５からこの情報を判断し、次にスケジューリング経緯ユニット４５に影響を及ぼす。前述したように、リソースにアクセスするのに必要な時間量は、要求の種類にも依存する。例えば、動的ランダムアクセスメモリ（ＤＲＡＭ）システムにアクセスする場合、オープンＤＲＡＭページに対する要求は、クローズドＤＲＡＭページに対する要求よりもはるかに短時間である。
【００１０】
ある実施形態では、スケジューリング用として使用される異なるＱＯＳモードが、優先サービス、割り当てバンド幅サービス、及びベスト・エフォートサービスを含むことができる。各チャンネルが１つのＱＯＳモードに割り当てられる。優先サービス又は割り当てバンド幅サービスを受信するチャンネルのために、バンド幅割り当てを与える必要がある。優先サービスは、割り当てられたバンド幅プラス最小待ち時間サービスになるまでバンド幅保証をもたらす。割り当てバンド幅サービスは、割り当てられたバンド幅になるまでのバンド幅保証にみをもたらす。ベスト・エフォートサービスは、ＱＯＳ保証をまったくもたらさず、そして実際には何のサービスも受信しないことができる。
【００１１】
同じレベルのＱＯＳで、複数の未処理要求の中から１つを選択する判断に、例えば、スケジューリング経緯を用いた別の調整を使用することができる。例えば、バス等のリソースを指示するスケジューリング経緯がある方向に動作している場合、調整により、対立する動作を同じ方向にする要求が優先して行われるようにする。
【００１２】
本発明の実施形態の場合、１つのＱＯＳモードは、各チャンネル１５、２０、２５を割り当て、そしてＱＯＳ構成ユニット４０にこの情報を配置する。異なるチャンネルへバンド幅を割り当てるために、アクセスされるリソース内で使用可能な全バンド幅を計算することが重要である。この全バンド幅を計算することは、比較的容易であり、又は要求ストリーム自体に左右され、このため、特定のシステムのために特別に期待された要求ストリームを用いて見積もる必要がある。例えば、ＤＲＡＭシステムの使用可能な全バンド幅を見積もる場合、要求ストリームのページ的中とページ失敗の期待された割合を見積もることが必要である。使用可能な全バンド幅を正確に見積もることが不可能な場合、過少見積もりによって、所与のシステムにおいて予測し得る状況の全て又は実質的に全てを下回るように行われるべきである。
【００１３】
本発明の実施形態の場合、割り当てられた所定分のバンド幅全てが、優先チャンネル及び割り当てバンド幅チャンネルである。すべての条件下で、ＱＯＳ保証に適合させるために、多くともリソースの使用可能な全バンド幅がこれらのチャンネルに割り当てられるべきである。
【００１４】
優先ＱＯＳモード又は割り当てバンド幅モードを用いたチャンネルは、ベスト・エフォートモードを使用するチャンネルよりも高いＱＯＳを受信するが、このチャンネルはそれぞれのバンド幅割り当て内で継続して動作するだけである。チャンネルが割り当てられたバンド幅以上の要求を行うことが可能だが、この場合、ＱＯＳはベスト・エフォートチャンネルと同等又はそれよりも悪くなり得る。
【００１５】
図２は、チャンネルがリソースへのアクセスを得る優先順位の一例を示している。バンド幅の割り当て内に存在する優先チャンネルがトップレベル２０５を確保する。このカテゴリーの要求を有する任意のチャンネルがある場合、可能な限り迅速な（サービスされた）アクセスがこのチャンネルに提供され、このため、少ない待ち時間でリソースへのアクセスが行われる。次に低いレベル２１０が、バンド幅の割り当て内に存在する割り当てバンド幅チャンネル用である。したがって、適当な優先要求がない場合、割り当てバンド幅要求がサービスされる。ベスト・エフォートチャンネル、及び割り当てられたバンド幅外にある優先チャンネル又は割り当てバンド幅チャンネルが、低い優先度によってサービスされる。図２に示すような２つの分離した優先度２１５、２２０として、これら２つのグループを組み合わすか又はサービスするかの何れかを行うことができる。
【００１６】
このスケジューリング方法を用いて、割り当てバンド幅チャンネル及び優先チャンネルが実質的に保証され、割り当てられたバンド幅を受信する。両者の間で、優先チャンネルは、高い優先度でサービスされ、これらのチャンネルはリソースに対して待ち時間の少ないアクセスを実行する。優先チャンネル及び割り当てバンド幅チャンネルが、リソースを使用できる全バンド幅を使い果たさない場合で、かつそのときに、割り当て外にあるベスト・エフォートチャンネル及び他のチャンネルがリソースを使用することができる場合、リソースは、待ち要求があるが遊休（アイドル）状態でないようにする。
【００１７】
図３は、調整処理の一実施形態を示す。説明のため、あるチャンネルが各レベルに割り当てられると仮定する。しかしながら、同一のレベルで複数のチャンネルが動作可能であることも考えられる。特定のリソースによりサービスされる未処理の要求がある場合（ステップ３００）で、リソースのバンド幅が使用可能な場合（ステップ３０５）、例えば、最も高い優先度をもつサービスのレベルである第１のレベルが実行される（ステップ３１０）。第１のレベルでのチャンネルからの任意の要求がバンド幅の割り当て内にある場合（ステップ３１５）、第１のレベルの１チャンネルから要求を発行する（ステップ３２０）。第１のレベルでのチャンネルからの要求が割り当て内にない場合、ある実施形態では、次に低い優先度のレベルである次のレベルでのチャンネルからの要求が実行される（ステップ３２５）。このレベルでのチャンネルが割り当て内にある場合、或いはまた割り当てバンド幅が指定されない場合（ステップ３３０）、そのレベルのチャンネルから要求を発行する（ステップ３３５）。チャンネルの各レベルでこの処理が続く（ステップ３４０）。
【００１８】
本発明のスケジューリングシステムを用い、システムは、所定のチャンネルが割り当てられたバンド幅内又は超えて動作しているかどうかを判断することができる。このメカニズムを実行する１つの方法を、図４の実施形態によって説明する。図４に示すように、同じ大きさのスケジュール期間、例えば、期間４１０，４２０，４３０に時間を分割する。スケジュール期間あたりの固定された要求数に基づいて、バンド幅を割り当てる。スケジューリングユニットは、これらの要求をスケジュール期間の間、適当な任意の時間でスケジュールすることを決定する。説明のため、このスケジュール方法を「レート型」スケジューリングと称する。スケジューリングユニットが、スケジューリング期間の間の任意の時点で要求をスケジュールできることにより、スケジューリングユニットは、既知の要求到着時間に左右されなくなる。さらに、スケジューリングユニットは、リソース効率を最大限にするための要求をスケジュールすることができる。図４の例の場合、４つの要求４１２，４１４，４１６，４１８が、各スケジュール期間で常にスケジュールされるが、リソースが各要求を処理する正確な時間は、例えば期間４２０のスケジュール期間から、例えば期間４３０のスケジュール期間へと変化する。
【００１９】
レート型スケジューリングの一実施形態を図５に示す。この実施形態の利点は、ほんの僅かな状態である、まさにチャンネルあたり２つのカウンタを要求することである。示されたメカニズムは、１つのチャンネル用のものであり、所定のチャンネルがバンド幅を超えているか又は下回っているかを判断するのに十分なものである。この複数のバージョンを実行することができ、複数のチャンネルをサポートする。加えて、様々な方法により前述した機能を実行することが考えられる。
【００２０】
各サイクル１回というような、レートカウンタ５１０を小さな時間間隔で増加する。本実施形態の場合、チャンネルに割り当てられたバンド幅に基づいた最大値を有するようにレートカウンタ５１０を構成する。例えば、特定のチャンネルに割り当てられたバンド幅が、各１００サイクルのスケジューリング期間で１０個の要求である場合、最大値１０によりレートカウンタをセットアップするであろう。
【００２１】
レートカウンタ５１０が最大値に達すると、レートカウンタ５１０は、割り当てカウンタ５１５を増加させていき、これによりそのチャンネルを使用できる「信頼（credit）」の要求が１以上存在することを表現する。レートカウンタ５１０は、カウントをリセットするとともに再びカウントの開始を行う。ある実施形態の場合、レートカウンタは、単純なレジスタとして実行されたり、又はカウンタ値をテストするロジックに関連するメモリ内に配置されたりする。或いはまた、カウンタのオーバフロービットが、割り当てカウンタ５１５を増加させるために用いられ、かつレートカウンタ５１０をリセットすることができる。
【００２２】
要求がチャンネルからリソースへ送られるたびごとに、割り当てカウンタが減分され、これにより信頼（credit）が減じられていく。割り当てカウンタが正である限り、そのチャンネルはバンド幅割り当て内で動作している。
【００２３】
ある実施形態の場合、割り当てカウンタは、スケジューリング期間あたりの割り当て要求数より下になることはない（正又は負のいずれか）。割り当てカウンタが指定された限界値を超えないことを保証するために、サチュレーションロジック（saturation logic）を含んでいる。例えば、カウンタ５１５に対応するレジスタ又はメモリは制御ロジックを含み、正の限界値又は負の限界値を超えてカウンタの値を変更することはしない。これは、時間とともに消えていく経緯（history）をバンド幅が使用できるようにしている。そして、バンド幅が使用可能な場合、ある期間の間にチャンネルが割り当て以上に使用できるようにするが、バンド幅が再度ぎっしり詰まるようになる場合には、バンド幅の保証を維持する。
【００２４】
前述したスケジューリング方法は、共有リソースが競合される複数の要求側をもつ全ての種類のシステムに適するが、特に、共有動的ランダムアクセスメモリ（ＤＲＡＭ）システムによく適する。各要求のサービス時間は、要求の種類（例えば、読み出し又は書き込み、バーストサイズなど）に左右され、特定の要求がオープンのページを的中するかどうか、又はページがアクセスされる前にページをまずオープンする必要があるかどうかを判断する経緯を要求するので、ＤＲＡＭシステムのスケジューリングは特に難しい。異なるイニシエータ（要求側）装置又は処理からの要求ストリームの一定の集まりにより実行され得るバンド幅の見積もりが控えめになされると、前述したスケジューリング方法は、異なる要求側に対して異なるＱＯＳを保証するが、非常に高効率なＤＲＡＭを実現する。
【００２５】
望ましい実施形態の組合せにとともに本発明を説明してきた。本技術分野の当業者であれば、前述の記述の理解において多くの代替、修正、変形、及び慣例が明白であろう。
【図面の簡単な説明】
【００２６】
【図１】図１は、本発明の技術に従って動作する調整システムの一形態を示す概略図である。
【図２】図２は、優先順位の一形態を示す図である。
【図３】図３は、調整処理の一形態を示す概略フロー図である。
【図４】図４は、レート型スケジューリングの一形態を示す図である。
【図５】図５は、本発明の技術に従ったレート型スケジューリングの一形態を示す概略図である。
【図１】
2005505857.tif 000003
【図２】
2005505857.tif 000004
【図３】
2005505857.tif 000005
【図４】
2005505857.tif 000006
【図５】
2005505857.tif 000007
【国際公開パンフレット】
2005505857.tif 000008
2005505857.tif 000009
2005505857.tif 000010
2005505857.tif 000011
2005505857.tif 000012
2005505857.tif 000013
2005505857.tif 000014
2005505857.tif 000015
2005505857.tif 000016
2005505857.tif 000017
2005505857.tif 000018
2005505857.tif 000019
2005505857.tif 000020
2005505857.tif 000021
2005505857.tif 000022
2005505857.tif 000023
2005505857.tif 000024
【国際調査報告】
2005505857.tif 000025