JPH05210523A - 適応スケジューリング方法及び装置 - Google Patents
適応スケジューリング方法及び装置Info
- Publication number
- JPH05210523A JPH05210523A JP4221476A JP22147692A JPH05210523A JP H05210523 A JPH05210523 A JP H05210523A JP 4221476 A JP4221476 A JP 4221476A JP 22147692 A JP22147692 A JP 22147692A JP H05210523 A JPH05210523 A JP H05210523A
- Authority
- JP
- Japan
- Prior art keywords
- access
- resource
- requester
- time
- adaptive scheduling
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/40—Transformation of program code
- G06F8/41—Compilation
- G06F8/45—Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
- G06F8/458—Synchronisation, e.g. post-wait, barriers, locks
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computer And Data Communications (AREA)
- Mobile Radio Communication Systems (AREA)
- Multi Processors (AREA)
Abstract
(57)【要約】
【目的】 本発明の一つの目的は、共有資源の動的サー
ビス時間割当のための改良された適応スケジューリング
スキームを提供することにあり、もう一つの目的は、多
重資源（接続）へのアクセスを授与するために適応スケ
ジューリングシステムを使用し、これによって、高いス
ループット、向上された公平さ、及び待ち時間の短縮を
実現する交換システムを提供することにある。 【構成】 コンピュータの共通資源に対するアクセス時
間をこの資源へのアクセスを要求する複数のリクエスタ
に割り当てるための方法及び装置が提供される。本発明
は、資源へのアクセスを要求する各リクエスタに対する
待ち時間を検出し、各リクエスタに対して最大アクセス
時間を割り当てるが、このアクセス時間は待ち時間の関
数である。リクエスタが資源へのアクセスを完結する
と、最大アクセス時間は定数に縮められる。
ビス時間割当のための改良された適応スケジューリング
スキームを提供することにあり、もう一つの目的は、多
重資源（接続）へのアクセスを授与するために適応スケ
ジューリングシステムを使用し、これによって、高いス
ループット、向上された公平さ、及び待ち時間の短縮を
実現する交換システムを提供することにある。 【構成】 コンピュータの共通資源に対するアクセス時
間をこの資源へのアクセスを要求する複数のリクエスタ
に割り当てるための方法及び装置が提供される。本発明
は、資源へのアクセスを要求する各リクエスタに対する
待ち時間を検出し、各リクエスタに対して最大アクセス
時間を割り当てるが、このアクセス時間は待ち時間の関
数である。リクエスタが資源へのアクセスを完結する
と、最大アクセス時間は定数に縮められる。
Description
【０００１】
【産業上の利用分野】本発明はコンピュータシステムの
資源へのアクセスを複数のリクエスタに供与することに
関する。より詳細には、本発明においては、各リクエス
タに最大アクセス時間が供与されるが、このアクセス時
間は待ち時間の関数であり、各リクエスタが資源にアク
セスした後は初期値にリターンする。
資源へのアクセスを複数のリクエスタに供与することに
関する。より詳細には、本発明においては、各リクエス
タに最大アクセス時間が供与されるが、このアクセス時
間は待ち時間の関数であり、各リクエスタが資源にアク
セスした後は初期値にリターンする。
【０００２】
【従来の技術】科学的及び技術的集団は共通資源の様々
なこれを要求するユーザ間での使用或は割り当てをサー
ビス要件に関する事前の情報無しにスケジュールするた
めの革新的なアルゴリズムの開発に非常に熱心である
［１−５］。このようなアルゴリズムは（単一或は多重
プロセッサシステム内における）プロセッサスケジュー
リング、交換機内での接続の割り当て、及び製造（生産
ライン）におけるプロセススケジューリング等のような
多数のアプリケーションのために開発されている。
なこれを要求するユーザ間での使用或は割り当てをサー
ビス要件に関する事前の情報無しにスケジュールするた
めの革新的なアルゴリズムの開発に非常に熱心である
［１−５］。このようなアルゴリズムは（単一或は多重
プロセッサシステム内における）プロセッサスケジュー
リング、交換機内での接続の割り当て、及び製造（生産
ライン）におけるプロセススケジューリング等のような
多数のアプリケーションのために開発されている。
【０００３】スケジューリングアルゴリズムの定義は幾
分困難である。本発明の目的においては、我々は、二つ
の主要なクラスのアルゴリズムを区別するために一つの
基準を強調する。これは、リクエスタがそれに資源を割
り当てられた後に共通資源を使用する継続期間である。
多くのアルゴリズムはリクエスタが資源を完結するまで
使用することを許す（例えば、ＦＣＦＳがこれに相当す
る）。幾つかの他のアルゴリズムは一定の割り当て量を
定義する。リクエスタは割り当てられた資源を割り当て
時間が満了するまで使用する。リクエスタがこの授与さ
れた時間内に完結できないときは、これは再び待ち行列
に入れられ、新たなサービス時間の割当が与えられるま
で次の順番を待たなければならない。この順番は、通
常、待ち行列内で待っている他の競合するリクエスタが
処理された後に来、これは通常、ある種の公平さを確保
するためにラウンドロビン（round robin ）ベースにて
行なわれる。この割り当て政策は、但し、待ち行列に入
る順番以外の他の基準に基づくこともある。一例は、ジ
ョブを完結するために要求される時間である。つまり、
資源は、そのジョブが競合者の中で完結するために最も
長い（或は最も短い）時間を必要とするリクエスタに与
えられる。但し、これらの全てのケースにおいて、リク
エスタには、一定の最大時間が与えられ、この期間内で
資源を使用した後に、これを解放する。
分困難である。本発明の目的においては、我々は、二つ
の主要なクラスのアルゴリズムを区別するために一つの
基準を強調する。これは、リクエスタがそれに資源を割
り当てられた後に共通資源を使用する継続期間である。
多くのアルゴリズムはリクエスタが資源を完結するまで
使用することを許す（例えば、ＦＣＦＳがこれに相当す
る）。幾つかの他のアルゴリズムは一定の割り当て量を
定義する。リクエスタは割り当てられた資源を割り当て
時間が満了するまで使用する。リクエスタがこの授与さ
れた時間内に完結できないときは、これは再び待ち行列
に入れられ、新たなサービス時間の割当が与えられるま
で次の順番を待たなければならない。この順番は、通
常、待ち行列内で待っている他の競合するリクエスタが
処理された後に来、これは通常、ある種の公平さを確保
するためにラウンドロビン（round robin ）ベースにて
行なわれる。この割り当て政策は、但し、待ち行列に入
る順番以外の他の基準に基づくこともある。一例は、ジ
ョブを完結するために要求される時間である。つまり、
資源は、そのジョブが競合者の中で完結するために最も
長い（或は最も短い）時間を必要とするリクエスタに与
えられる。但し、これらの全てのケースにおいて、リク
エスタには、一定の最大時間が与えられ、この期間内で
資源を使用した後に、これを解放する。
【０００４】サービス時間割当量は異なるクラスのリク
エスタに対しては異なるが、但し、ある一つのクラス内
の全てのリクエスタに対して同一である。このクラス分
けは、リクエスタの相対的な優先度或は重要性を反映す
るために使用される。また、幾つかのスケジューリング
規律では、リクエスタがシステム内に留まりながら異な
る優先度及び通常異なる割り当て量を持つあるクラスか
ら別のクラスに移ることが許される。このようなスキー
ムにおいては、プロセッサは、通常、最初に、より高い
優先度のクラスの全てのリクエスタをラウンドロビンベ
ースにて処理し、次に低い優先度のクラスの処理へと進
む。この考えは、リクエスタの優先度がその緊急性或は
要求される完結期限の差し迫りを表わす多くのリアルタ
イムシステムにおいて使用される。幾つかの他のスキー
ムにおいては、低レベルのリクエスタが最初に処理さ
れ、これらのレベルが各処理の後に上げられる。これは
入りリクエスタに対する早い初期応答（注意）を与え、
また、短いサービス要件を持つリクエスタを優遇する。
一つのこのようなスキームは前景背景アルゴリズムに実
現される［２］。
エスタに対しては異なるが、但し、ある一つのクラス内
の全てのリクエスタに対して同一である。このクラス分
けは、リクエスタの相対的な優先度或は重要性を反映す
るために使用される。また、幾つかのスケジューリング
規律では、リクエスタがシステム内に留まりながら異な
る優先度及び通常異なる割り当て量を持つあるクラスか
ら別のクラスに移ることが許される。このようなスキー
ムにおいては、プロセッサは、通常、最初に、より高い
優先度のクラスの全てのリクエスタをラウンドロビンベ
ースにて処理し、次に低い優先度のクラスの処理へと進
む。この考えは、リクエスタの優先度がその緊急性或は
要求される完結期限の差し迫りを表わす多くのリアルタ
イムシステムにおいて使用される。幾つかの他のスキー
ムにおいては、低レベルのリクエスタが最初に処理さ
れ、これらのレベルが各処理の後に上げられる。これは
入りリクエスタに対する早い初期応答（注意）を与え、
また、短いサービス要件を持つリクエスタを優遇する。
一つのこのようなスキームは前景背景アルゴリズムに実
現される［２］。
【０００５】リクエストの優先レベルがそれがシステム
内に存在する時間の関数として変化する様々なスケジュ
ーリング規律が存在する。我々はこのようなスケジュー
リング規律を３つのクラスに要約する［２］。これら
は、時間依存優先（Time-Dependent Priority ）、待ち
行列位置の買収（Bribing for Queue Position）、及び
利己的スケジューリング（Selfish Scheduling）であ
る。 １．時間依存優先 時間依存優先スケジューリング規律は要求の優先レベル
がこれが待ち行列内で待つに従って増加する単なる非先
取り優先（nonpreemptive priority）スケジューリング
規律である。優先レベルの増加の量は時間の線型関数或
は高次関数である。異なるクラスの要求は異なる優先関
数を持つ。資源が利用できるようになる度に、最も大き
な優先レベルを持つ要求が資源へのアクセスを得て、こ
れをサービスの完結まで使用する。つまり、サービスの
定量或は要求のフィードバックはない。 ２．待ち行列位置の買収 このシステムにおいては、各要求は緊急係数（impatien
ce factor ）α、及び対応する申出賄賂（offered brib
e ）ｙαを持つ。コスト関数Ｃ（α）がｙα及びＷ（ｙ
α）に基づいて計算され、その賄賂がｙαであるリクエ
スタに対する（待ち行列内の）平均待ち時間は、Ｃ
（α）＝ｙα＋αＷ（ｙα）である。目標は、平均賄賂
制約に従って予期されるコストを最小化し、こうして、
最適セットの賄賂ｙαを得ることである。このシステム
内には動的な挙動はなく、リクエストは、それらが資源
得の割り当てを得ると必ずこれをサービスの完結まで使
用する。 ３．利己的スケジューリング このシステムは、待ち行列ボックス及びサービスボック
スから成る二つのボックスから成る。到着すると、リク
エストは待ち行列ボックス内で待ち、それらの優先レベ
ルは任意のレートαにて時間と比例して線型的に増加す
る。サービスボックスは待ちルーム（セットの待ち行
列）及び割り当てられるべき資源を含む。同様に、サー
ビスボックス内の要求の優先レベルは時間と比例して線
型的に増加するが、但し、αよりも小さな任意のレート
βにて増加する。要求は、それらの優先レベルがサービ
スボックス内の優先レベルとマッチすると待ち行列ボッ
クスからサービスボックスへと移される。これは、βが
αよりも小さいために必ず起こる。サービスボックス内
のスケジューリング規律は（フィードバック待ち行列を
含めて）任意に選択でき、こうして、利己的スケジュー
リングは、大きなクラスのスケジューリング規律を定義
する。但し、サービスボックス内の要求の優先レベルは
時間とともに、その要求が待ち行列内で待っているか或
はサービスを受けているかに関係なく線型的に増加する
ことに注意する。さらに、この利己的スケジューリング
システムの構造に起因して、優先レベルは、要求がサー
ビス期間の満了等によって中断された場合でもかわらな
い。換言すれば、時間の任意のポイントにおいて、サー
ビスボックス内の全ての要求は、全ての要求間で一様に
時間とともに増加する同一の優先レベルを持つ。 参照文献 １．ダイテル（Dietel）、Ｈ．による『オペレーティン
グシステム入門（An Introduction to Operating Syste
ms）』、アディソン・ウェズレイ、１９８３年。 ２．クレインロック（Kleinroc）、Ｌ．による『待ち行
列システム、Ｖｏｌ．2.：コンピュータアプリケーショ
ン（Queueing Systems Vol. 2.: Computer Application
s ）』、Ｊ．ウィリー（Wiley ）、１９７６年。 ３．レフラ（Leffle）、Ｓ．、マクイジック（McKusic
k）、Ｍ．、及びクォータマン（Quarterman）、Ｊ．に
よる『４．３ＢＳＤユニックスオペレーティングシステ
ムの設計及び実現（The Design and Implementation of
the 4.3BSD UNIX Operating System ）』、アディソン
・ウェズレイ、１９８９年。 ４．ラベンバルグ（Lavenberg ）、Ｓ．編集『コンピュ
ータ性能モデリングハンドブック（Computer performan
ce Modeling Handbook）』、アカデミック・プレス、１
９８３年。５．ラスチツカ（Ruschitzka）、Ｍ．『ポリ
シー機能スケジューリング（Policy Function Scheduli
ng）』、性能評価（performance Evalution ）、１９８
１、ページ３１−４７。
内に存在する時間の関数として変化する様々なスケジュ
ーリング規律が存在する。我々はこのようなスケジュー
リング規律を３つのクラスに要約する［２］。これら
は、時間依存優先（Time-Dependent Priority ）、待ち
行列位置の買収（Bribing for Queue Position）、及び
利己的スケジューリング（Selfish Scheduling）であ
る。 １．時間依存優先 時間依存優先スケジューリング規律は要求の優先レベル
がこれが待ち行列内で待つに従って増加する単なる非先
取り優先（nonpreemptive priority）スケジューリング
規律である。優先レベルの増加の量は時間の線型関数或
は高次関数である。異なるクラスの要求は異なる優先関
数を持つ。資源が利用できるようになる度に、最も大き
な優先レベルを持つ要求が資源へのアクセスを得て、こ
れをサービスの完結まで使用する。つまり、サービスの
定量或は要求のフィードバックはない。 ２．待ち行列位置の買収 このシステムにおいては、各要求は緊急係数（impatien
ce factor ）α、及び対応する申出賄賂（offered brib
e ）ｙαを持つ。コスト関数Ｃ（α）がｙα及びＷ（ｙ
α）に基づいて計算され、その賄賂がｙαであるリクエ
スタに対する（待ち行列内の）平均待ち時間は、Ｃ
（α）＝ｙα＋αＷ（ｙα）である。目標は、平均賄賂
制約に従って予期されるコストを最小化し、こうして、
最適セットの賄賂ｙαを得ることである。このシステム
内には動的な挙動はなく、リクエストは、それらが資源
得の割り当てを得ると必ずこれをサービスの完結まで使
用する。 ３．利己的スケジューリング このシステムは、待ち行列ボックス及びサービスボック
スから成る二つのボックスから成る。到着すると、リク
エストは待ち行列ボックス内で待ち、それらの優先レベ
ルは任意のレートαにて時間と比例して線型的に増加す
る。サービスボックスは待ちルーム（セットの待ち行
列）及び割り当てられるべき資源を含む。同様に、サー
ビスボックス内の要求の優先レベルは時間と比例して線
型的に増加するが、但し、αよりも小さな任意のレート
βにて増加する。要求は、それらの優先レベルがサービ
スボックス内の優先レベルとマッチすると待ち行列ボッ
クスからサービスボックスへと移される。これは、βが
αよりも小さいために必ず起こる。サービスボックス内
のスケジューリング規律は（フィードバック待ち行列を
含めて）任意に選択でき、こうして、利己的スケジュー
リングは、大きなクラスのスケジューリング規律を定義
する。但し、サービスボックス内の要求の優先レベルは
時間とともに、その要求が待ち行列内で待っているか或
はサービスを受けているかに関係なく線型的に増加する
ことに注意する。さらに、この利己的スケジューリング
システムの構造に起因して、優先レベルは、要求がサー
ビス期間の満了等によって中断された場合でもかわらな
い。換言すれば、時間の任意のポイントにおいて、サー
ビスボックス内の全ての要求は、全ての要求間で一様に
時間とともに増加する同一の優先レベルを持つ。 参照文献 １．ダイテル（Dietel）、Ｈ．による『オペレーティン
グシステム入門（An Introduction to Operating Syste
ms）』、アディソン・ウェズレイ、１９８３年。 ２．クレインロック（Kleinroc）、Ｌ．による『待ち行
列システム、Ｖｏｌ．2.：コンピュータアプリケーショ
ン（Queueing Systems Vol. 2.: Computer Application
s ）』、Ｊ．ウィリー（Wiley ）、１９７６年。 ３．レフラ（Leffle）、Ｓ．、マクイジック（McKusic
k）、Ｍ．、及びクォータマン（Quarterman）、Ｊ．に
よる『４．３ＢＳＤユニックスオペレーティングシステ
ムの設計及び実現（The Design and Implementation of
the 4.3BSD UNIX Operating System ）』、アディソン
・ウェズレイ、１９８９年。 ４．ラベンバルグ（Lavenberg ）、Ｓ．編集『コンピュ
ータ性能モデリングハンドブック（Computer performan
ce Modeling Handbook）』、アカデミック・プレス、１
９８３年。５．ラスチツカ（Ruschitzka）、Ｍ．『ポリ
シー機能スケジューリング（Policy Function Scheduli
ng）』、性能評価（performance Evalution ）、１９８
１、ページ３１−４７。
【０００６】ファンデルメイ（Vander Mey）に交付され
た合衆国特許４，０９６，５７１号はどの要求が権利を
受けるかを決定するために待ち時間を使用する調停スキ
ームを開示する。このスキームは、基本的には、決定を
行なうために静的優先を使用するＦＩＦＯスキームであ
る。この発明は、サービス時間の割当問題には触れな
い。
た合衆国特許４，０９６，５７１号はどの要求が権利を
受けるかを決定するために待ち時間を使用する調停スキ
ームを開示する。このスキームは、基本的には、決定を
行なうために静的優先を使用するＦＩＦＯスキームであ
る。この発明は、サービス時間の割当問題には触れな
い。
【０００７】グリムズ（Grimes）に交付された合衆国特
許第４，４８８，２１８号はステーションがそれらの優
先度を様々なパラメータに従って動的に変えることを許
す回路を開示する。これらパラメータの一つとして、バ
ッファが満杯であるか、半分満たされているかが使用さ
れる。この発明において詳述される例においては、資源
が要求されるサービスの完結まで保持される。その他の
点においては、ステーションが資源を割り当てられた後
にそれをどれ位長く保持できるかに関しては何も示され
ない。
許第４，４８８，２１８号はステーションがそれらの優
先度を様々なパラメータに従って動的に変えることを許
す回路を開示する。これらパラメータの一つとして、バ
ッファが満杯であるか、半分満たされているかが使用さ
れる。この発明において詳述される例においては、資源
が要求されるサービスの完結まで保持される。その他の
点においては、ステーションが資源を割り当てられた後
にそれをどれ位長く保持できるかに関しては何も示され
ない。
【０００８】ジョージオ（Georgiou）らに交付された合
衆国特許第４，６３３，３９４号は固定した優先を実現
するための回路を開示する。リクエスタは二つの公平さ
グループ（fairness group）にグループ分けされ、これ
らグループ間でラウンドロビンが適用され、片方のグル
ープからの全てのリクエスタが他方のグループ内のリク
エスタの前に処理される。あるリクエスタはそれが完全
に処理されると直ちに他方のグループに移される。
衆国特許第４，６３３，３９４号は固定した優先を実現
するための回路を開示する。リクエスタは二つの公平さ
グループ（fairness group）にグループ分けされ、これ
らグループ間でラウンドロビンが適用され、片方のグル
ープからの全てのリクエスタが他方のグループ内のリク
エスタの前に処理される。あるリクエスタはそれが完全
に処理されると直ちに他方のグループに移される。
【０００９】ギロイア（Giroir）らに交付された合衆国
特許第４，６７２，５３６号は共通資源へのアクセスが
最も高い優先を持つリクエスタの中で最も古い要求を持
つリクエスタに授与される。資源の使用は中断されな
い。
特許第４，６７２，５３６号は共通資源へのアクセスが
最も高い優先を持つリクエスタの中で最も古い要求を持
つリクエスタに授与される。資源の使用は中断されな
い。
【００１０】レーデマン（Ludemann）らに交付された合
衆国特許第４，７１９，５６９号は、デバイスがそれに
対して授与された資源をそのデバイスが任意のレートを
超える新たな要求を発行し続ける限り保持することを可
能とする調停スキームを開示する。このスキームは、許
されるサービス時間の長さを決定するために、待ち時間
ではなく、緊急度を使用する。
衆国特許第４，７１９，５６９号は、デバイスがそれに
対して授与された資源をそのデバイスが任意のレートを
超える新たな要求を発行し続ける限り保持することを可
能とする調停スキームを開示する。このスキームは、許
されるサービス時間の長さを決定するために、待ち時間
ではなく、緊急度を使用する。
【００１１】
【発明が解決しようとする課題】従って、本発明の一つ
の目的は、共有資源の動的サービス時間割当のための改
良された適応スケジューリングスキームを提供すること
にある。より具体的には、本発明の一つの目的は、プロ
セッサ共有（processor sharing 、ＰＳ）の公平さ特性
（fairness property ）と先着順処理（first come fir
st serve、ＦＣＦＳ）との効率の均衡を保つ適応スケジ
ューリングスキームを提供することにある。
の目的は、共有資源の動的サービス時間割当のための改
良された適応スケジューリングスキームを提供すること
にある。より具体的には、本発明の一つの目的は、プロ
セッサ共有（processor sharing 、ＰＳ）の公平さ特性
（fairness property ）と先着順処理（first come fir
st serve、ＦＣＦＳ）との効率の均衡を保つ適応スケジ
ューリングスキームを提供することにある。
【００１２】本発明のもう一つの目的は、多重資源（接
続）へのアクセスを授与するために適応スケジューリン
グシステムを使用し、これによって、高いスループッ
ト、向上された公平さ、及び待ち時間の短縮を実現する
交換システムを提供することにある。
続）へのアクセスを授与するために適応スケジューリン
グシステムを使用し、これによって、高いスループッ
ト、向上された公平さ、及び待ち時間の短縮を実現する
交換システムを提供することにある。
【００１３】
【課題を解決するための手段及び作用】従って、本発明
は、コンピュータシステムの共通資源へのアクセスをこ
の資源へのアクセスを要求する複数のリクエスタに授与
するための方法及び装置を提供する。この発明において
は、各リクエスタに対する待ち時間が検出される。この
待ち時間は、リクエスタがアクセスを要求して以来資源
へのアクセスを待っている時間である。この待ち時間の
関数である最大アクセス時間がアクセス時に各リクエス
タに与えられる。リクエスタがそのアクセスを終了する
と、最大アクセス時間は、全てのリクエスタに対して同
一である初期値にリターンする。
は、コンピュータシステムの共通資源へのアクセスをこ
の資源へのアクセスを要求する複数のリクエスタに授与
するための方法及び装置を提供する。この発明において
は、各リクエスタに対する待ち時間が検出される。この
待ち時間は、リクエスタがアクセスを要求して以来資源
へのアクセスを待っている時間である。この待ち時間の
関数である最大アクセス時間がアクセス時に各リクエス
タに与えられる。リクエスタがそのアクセスを終了する
と、最大アクセス時間は、全てのリクエスタに対して同
一である初期値にリターンする。
【００１４】本発明の可変動的時間割当スキームは、シ
ステムが、例えば、長い待ち時間によって示されるよう
に重い負荷状態にあるときシステムが高効率にて応答す
ることを許す一方において短い待ち時間にて象徴される
ようにシステムが適度な負荷を持つとき公平さを確保す
る。
ステムが、例えば、長い待ち時間によって示されるよう
に重い負荷状態にあるときシステムが高効率にて応答す
ることを許す一方において短い待ち時間にて象徴される
ようにシステムが適度な負荷を持つとき公平さを確保す
る。
【００１５】本発明はまた初期のリクエスタのクラス分
けを保持し、これによって、リクエスタの実際の優先度
を反映する真の指標を維持する。例えば、この優先度
は、渋滞時において、より低いクラスのリクエスタに先
行するため、或はこれを破棄するために使用される。
けを保持し、これによって、リクエスタの実際の優先度
を反映する真の指標を維持する。例えば、この優先度
は、渋滞時において、より低いクラスのリクエスタに先
行するため、或はこれを破棄するために使用される。
【００１６】本発明による適応スケジューリングスキー
ムは待ち行列内で待っている要求の優先レベルがそれが
待ち行列に入った以来の待ち時間の関数として増加する
という概念を導入する。待ち行列内への参入は、リクエ
スタが新たに到着したとき、或は資源を使用しているリ
クエスタのサービスクジットの満了に続くフィードバッ
ク要求による。あるリクエストに割り当てられるサービ
スクレジットは、完結までのサービス（service-till-c
omplition)、つまり獲得した時間依存優先レベル（atta
ined time-dependent priority level）には影響されな
い量とは対比的なそのリクエストの優先レベルの関数と
して決定される量である。
ムは待ち行列内で待っている要求の優先レベルがそれが
待ち行列に入った以来の待ち時間の関数として増加する
という概念を導入する。待ち行列内への参入は、リクエ
スタが新たに到着したとき、或は資源を使用しているリ
クエスタのサービスクジットの満了に続くフィードバッ
ク要求による。あるリクエストに割り当てられるサービ
スクレジットは、完結までのサービス（service-till-c
omplition)、つまり獲得した時間依存優先レベル（atta
ined time-dependent priority level）には影響されな
い量とは対比的なそのリクエストの優先レベルの関数と
して決定される量である。
【００１７】
【実施例】図１は本発明を実現するシステム全体の略図
である。ここには、資源１６にアクセスを要求すること
ができるリクエスタ（requestor ）Ｒ1 、Ｒ2 、…ＲN
が示される。どのリクエスタが、どの程度の長さ、共通
資源へのアクセスを得るかの選択はスケジューラ（sche
duler ）１５によって達成され、これに関しては図２に
より詳細に示される。リクエスタが共通資源へのアクセ
スに対する要求を行なう場合、ラインｒ1 からｒN の一
つが起動され、これによって、タイマ２０−１から２０
−Ｎの一つがゼロにリセットされる。リセットタイマは
リクエスタにアクセスが与えられるまでランする。この
待ち時間は、タイマ２０−１から２０−Ｎの出力（Ｗ1
からＷN ）の一つの上に現われる。各リクエスタに対す
るサービスクレジット（service credits ）はサービス
クレジット２１−１から２１−Ｎの一つによって対応す
るタイマによって報告される待ち時間に基づいて決定さ
れる。これらサービスクレジット（Ｃ1 からＣN ）はク
レジットレートＣと待ち時間Ｗ1 の積として定義され
る。スケジューラがどのリクエスタが資源へのアクセス
を得るかを決定するとき、サービスクレジット値Ｃ1 か
らＣN が比較器２６によって比較され、最も大きなサー
ビスクレジット値を持つリクエスタが資源へのアクセス
を得るようにスケジュールされる。サービスクレジット
値の比較の結果は出力ラインＳ１からＳＮ上に現れる。
選択される値は最も大きなサービスクレジット値に等し
い。セレクタ２５は、次に、比較器の出力を使用して、
実際にどのリクエスタが共通資源へのアクセスを得るか
の選択を行なう。選択されたリクエスタＲM は資源を最
大アクセス時間ＴM だけ使用することを許される。ここ
で、最大アクセス時間ＴM は基本割り当て量ｑb とサー
ビスクレジットＣM の総和である。選択されたＲM は、
次に、資源を最大時間ＴM だけ、或はリクエスタの要求
されるサービスが資源によって満たされるまでのいずれ
かの期間だけ使用する。要求が完結すると、リスクエタ
はシステムを去る。要求がＴM 内に完結しないときは、
別の要求が行なわれ、これによってタイマがリセットさ
れる。
である。ここには、資源１６にアクセスを要求すること
ができるリクエスタ（requestor ）Ｒ1 、Ｒ2 、…ＲN
が示される。どのリクエスタが、どの程度の長さ、共通
資源へのアクセスを得るかの選択はスケジューラ（sche
duler ）１５によって達成され、これに関しては図２に
より詳細に示される。リクエスタが共通資源へのアクセ
スに対する要求を行なう場合、ラインｒ1 からｒN の一
つが起動され、これによって、タイマ２０−１から２０
−Ｎの一つがゼロにリセットされる。リセットタイマは
リクエスタにアクセスが与えられるまでランする。この
待ち時間は、タイマ２０−１から２０−Ｎの出力（Ｗ1
からＷN ）の一つの上に現われる。各リクエスタに対す
るサービスクレジット（service credits ）はサービス
クレジット２１−１から２１−Ｎの一つによって対応す
るタイマによって報告される待ち時間に基づいて決定さ
れる。これらサービスクレジット（Ｃ1 からＣN ）はク
レジットレートＣと待ち時間Ｗ1 の積として定義され
る。スケジューラがどのリクエスタが資源へのアクセス
を得るかを決定するとき、サービスクレジット値Ｃ1 か
らＣN が比較器２６によって比較され、最も大きなサー
ビスクレジット値を持つリクエスタが資源へのアクセス
を得るようにスケジュールされる。サービスクレジット
値の比較の結果は出力ラインＳ１からＳＮ上に現れる。
選択される値は最も大きなサービスクレジット値に等し
い。セレクタ２５は、次に、比較器の出力を使用して、
実際にどのリクエスタが共通資源へのアクセスを得るか
の選択を行なう。選択されたリクエスタＲM は資源を最
大アクセス時間ＴM だけ使用することを許される。ここ
で、最大アクセス時間ＴM は基本割り当て量ｑb とサー
ビスクレジットＣM の総和である。選択されたＲM は、
次に、資源を最大時間ＴM だけ、或はリクエスタの要求
されるサービスが資源によって満たされるまでのいずれ
かの期間だけ使用する。要求が完結すると、リスクエタ
はシステムを去る。要求がＴM 内に完結しないときは、
別の要求が行なわれ、これによってタイマがリセットさ
れる。
【００１８】図３は本発明を実現する一般化されたアル
ゴリズムの流れ図を示す。リクエスタＲ1 は資源を使用
するために要求を行なう。ブロック３０１を参照。待ち
時間Ｗ1 が要求がその待ち期間をいつ開始したかの時間
の追跡を行なうためにゼロにリセットされる（３０
２）。リクエスタは資源が使用できる状態になるのを待
つ（３０３）。サービスクレジットＣ1 が全ての待ちリ
クエスタに対して計算される。用語”サービスクレジッ
ト（service credits ）”が、クレジットレートＣとリ
クエスタが要求を最後に行なってから経過した待ち時間
（つまり、タイマ値Ｗ1 ）との積として定義される（３
０４）。待っている全てのリクエスタの中で最も大きな
クレジット値、例えばＲM を持つリクエスタがアクセス
を得ることを選択され、資源を使用する（３０５）。選
択されたリクエスタＲM は資源を最大アクセス時間ＴM
まで使用することを許されるが、これは、基本割り当て
量ｑbとサービスクレジットＣM の総和である（３０
６）。選択されたリクエスタＲMは、資源を時間ＴM だ
け、或は資源によって要求されたサービスが完結される
までのいずれかの期間だけ使用する（３０７）。要求が
完結された場合は、リクエスタは資源を解放し（３０
８）；完結しないときは、リクエスタはもう一つの要求
を行ない（３０１）、その待ち時間タイマをリセットす
る（３０２）。
ゴリズムの流れ図を示す。リクエスタＲ1 は資源を使用
するために要求を行なう。ブロック３０１を参照。待ち
時間Ｗ1 が要求がその待ち期間をいつ開始したかの時間
の追跡を行なうためにゼロにリセットされる（３０
２）。リクエスタは資源が使用できる状態になるのを待
つ（３０３）。サービスクレジットＣ1 が全ての待ちリ
クエスタに対して計算される。用語”サービスクレジッ
ト（service credits ）”が、クレジットレートＣとリ
クエスタが要求を最後に行なってから経過した待ち時間
（つまり、タイマ値Ｗ1 ）との積として定義される（３
０４）。待っている全てのリクエスタの中で最も大きな
クレジット値、例えばＲM を持つリクエスタがアクセス
を得ることを選択され、資源を使用する（３０５）。選
択されたリクエスタＲM は資源を最大アクセス時間ＴM
まで使用することを許されるが、これは、基本割り当て
量ｑbとサービスクレジットＣM の総和である（３０
６）。選択されたリクエスタＲMは、資源を時間ＴM だ
け、或は資源によって要求されたサービスが完結される
までのいずれかの期間だけ使用する（３０７）。要求が
完結された場合は、リクエスタは資源を解放し（３０
８）；完結しないときは、リクエスタはもう一つの要求
を行ない（３０１）、その待ち時間タイマをリセットす
る（３０２）。
【００１９】この一般化されたアルゴリズムは図４に示
されるように説明することができる。 １．リクエスタＲi はそれが共有資源の使用が必要とな
ったら直ちに初期サービス要求（４０１）を行なう。実
際には、全てのサービス要求は、資源へのアクセスを得
るための遅延があるため、サービスが許される少し前に
行なわれる。この遅延は、簡素化の目的で図４には示さ
れない。資源が空いているときは、サービスを受けるこ
とができるが、空いてないときは、ある時間ｔp だけ待
ち、これは再度サービスの要求を行なう。我々は、ｔp
を持続期間（persistence time interval ）と呼ぶが、
これは、長い持続リクエスタ（persistent requestors
）に対しては短く、短い持続リクエスタに対しては長
くセットされる。このメカニズムは、例えば、優先クラ
スを実現するために使用される。 ２．待つことなくサービスを受けるリクエスタには資源
を基本割り当て量を超えない期間だけ使用することが許
される（４０２）。これは、リクエスタは資源をｑb に
等しい期間、或は実際に必要とされるサービス時間のい
ずれか短い期間だけ使用できることを意味する。リクエ
スタが完結するためにさらに時間を必要とする場合は、
これは、これがあたかもシステムに新たに到着したかの
ようにサービス要求を新たにする（４０３）。但し、勿
論、これは、それが実際にサーバを使用した時間の量だ
け減少されたサービス要件を持つ。こうして、リクエス
タはシステム内でサービスを待っている他の全てのリク
エスタと再び競合する。 ３．要求を行なったがサーバの使用を拒否された（４０
４）リクエスタはクレジットレート（credit rate ）Ｃ
を与えられる。この授与は要求が拒否される度にこれと
同数だけ反復される。従って、リクエスタがサービスを
受けるために期間Ｗ1 （待ち時間）だけ待つと、これ
は、総サービスクレジットＣ1 ＝ＣｘＷ1 を累積する。
例えば、Ｗ1 ＝２ｔp の場合、Ｃ1 ＝Ｃｘ２ｔp とな
る。このリクエスタが資源の使用を授与されると（４０
５）、これはＴ1 ＝ｑb ＋Ｃ1 を超えない総時間（或は
完結のために必要とされる時間のいずれか短い期間）だ
け資源を使用することが許される（４０５）。図４の４
０７において、投与されたサービス時間がジョブの完結
のために十分でなかったために新たにされた要求が行な
われる。ここでは、この新たにされた要求が殆ど直ちに
受け入れられたために、基本割り当て量のサービス時間
のみが提供される。但し、サービスの完結には提供され
た全サービス時間は必要とされないために、リクエスタ
は提供されたサービス時間が終了する前に資源を解放す
る。多重優先システム内においてはクレジットレートは
様々なクラスのリクエスタに対して異なる値を持つとこ
に注意する。また、ここでの説明では、我々のスキーム
の説明を簡単にするために、Ｃ1 とＷ1 との間の直線的
な関係を使用したが、より一般的な関係Ｃ1 ＝ｆ（Ｗ1
）を定義することを排除するものではない。 ４．単一優先システム内での資源割り当て政策は単純で
ある。つまり、優先は、サーバの使用を要求しているリ
クエスタの中の最も大きな待ち時間ＷM を持つリクエス
タＲM に与えられる。多重優先システムにおいては、サ
ーバは以下の二つの方法に従って割り当てられる。 ａ．これは最も高い総クレジットＣM を持つリクエスタ
に与えられるか、或は ｂ．最も高い（先取り）優先クラスのリクエスタ間の最
も大きな待ち時間ＣM を持つリクエスタに与えられる。 ５．実用上の理由から任意のリクエスタによって累積さ
れる総サービスクレジットは妥当な最大値に制限され
る。但し、これは、アルゴリズムの動作に対しては必要
でない。これとの関連で、限界のないクレジット（つま
り、無限に接近する最大値）は、システムの挙動を極端
に重い負荷の場合のＦＣＦＳの挙動に類似させる。
されるように説明することができる。 １．リクエスタＲi はそれが共有資源の使用が必要とな
ったら直ちに初期サービス要求（４０１）を行なう。実
際には、全てのサービス要求は、資源へのアクセスを得
るための遅延があるため、サービスが許される少し前に
行なわれる。この遅延は、簡素化の目的で図４には示さ
れない。資源が空いているときは、サービスを受けるこ
とができるが、空いてないときは、ある時間ｔp だけ待
ち、これは再度サービスの要求を行なう。我々は、ｔp
を持続期間（persistence time interval ）と呼ぶが、
これは、長い持続リクエスタ（persistent requestors
）に対しては短く、短い持続リクエスタに対しては長
くセットされる。このメカニズムは、例えば、優先クラ
スを実現するために使用される。 ２．待つことなくサービスを受けるリクエスタには資源
を基本割り当て量を超えない期間だけ使用することが許
される（４０２）。これは、リクエスタは資源をｑb に
等しい期間、或は実際に必要とされるサービス時間のい
ずれか短い期間だけ使用できることを意味する。リクエ
スタが完結するためにさらに時間を必要とする場合は、
これは、これがあたかもシステムに新たに到着したかの
ようにサービス要求を新たにする（４０３）。但し、勿
論、これは、それが実際にサーバを使用した時間の量だ
け減少されたサービス要件を持つ。こうして、リクエス
タはシステム内でサービスを待っている他の全てのリク
エスタと再び競合する。 ３．要求を行なったがサーバの使用を拒否された（４０
４）リクエスタはクレジットレート（credit rate ）Ｃ
を与えられる。この授与は要求が拒否される度にこれと
同数だけ反復される。従って、リクエスタがサービスを
受けるために期間Ｗ1 （待ち時間）だけ待つと、これ
は、総サービスクレジットＣ1 ＝ＣｘＷ1 を累積する。
例えば、Ｗ1 ＝２ｔp の場合、Ｃ1 ＝Ｃｘ２ｔp とな
る。このリクエスタが資源の使用を授与されると（４０
５）、これはＴ1 ＝ｑb ＋Ｃ1 を超えない総時間（或は
完結のために必要とされる時間のいずれか短い期間）だ
け資源を使用することが許される（４０５）。図４の４
０７において、投与されたサービス時間がジョブの完結
のために十分でなかったために新たにされた要求が行な
われる。ここでは、この新たにされた要求が殆ど直ちに
受け入れられたために、基本割り当て量のサービス時間
のみが提供される。但し、サービスの完結には提供され
た全サービス時間は必要とされないために、リクエスタ
は提供されたサービス時間が終了する前に資源を解放す
る。多重優先システム内においてはクレジットレートは
様々なクラスのリクエスタに対して異なる値を持つとこ
に注意する。また、ここでの説明では、我々のスキーム
の説明を簡単にするために、Ｃ1 とＷ1 との間の直線的
な関係を使用したが、より一般的な関係Ｃ1 ＝ｆ（Ｗ1
）を定義することを排除するものではない。 ４．単一優先システム内での資源割り当て政策は単純で
ある。つまり、優先は、サーバの使用を要求しているリ
クエスタの中の最も大きな待ち時間ＷM を持つリクエス
タＲM に与えられる。多重優先システムにおいては、サ
ーバは以下の二つの方法に従って割り当てられる。 ａ．これは最も高い総クレジットＣM を持つリクエスタ
に与えられるか、或は ｂ．最も高い（先取り）優先クラスのリクエスタ間の最
も大きな待ち時間ＣM を持つリクエスタに与えられる。 ５．実用上の理由から任意のリクエスタによって累積さ
れる総サービスクレジットは妥当な最大値に制限され
る。但し、これは、アルゴリズムの動作に対しては必要
でない。これとの関連で、限界のないクレジット（つま
り、無限に接近する最大値）は、システムの挙動を極端
に重い負荷の場合のＦＣＦＳの挙動に類似させる。
【００２０】交換システム内において、このスキームは
入力／出力接続の割り当てのために使用される。一例と
して、我々のスキームの入力待ち行列を持つクロスバー
スイッチ内での実現が概説される（図５を参照）。図５
には、Ｎ個の入力ポートＰI1、…、ＰIN、Ｎ個の出力ポ
ートＰo1、…ＰON、及びスケジューラ３７を持つクロス
バースイッチ３８が示される。
入力／出力接続の割り当てのために使用される。一例と
して、我々のスキームの入力待ち行列を持つクロスバー
スイッチ内での実現が概説される（図５を参照）。図５
には、Ｎ個の入力ポートＰI1、…、ＰIN、Ｎ個の出力ポ
ートＰo1、…ＰON、及びスケジューラ３７を持つクロス
バースイッチ３８が示される。
【００２１】スケジューラ３７内には、グローバル変数
を持つ二つのレジスタが存在する。レジスタ３１は持続
期間（persistence interval）ｔp を含み、レジスタ３
２は基本割り当て量ｑb を含む。持続期間は同一リクエ
スタの二つの連続する要求間の時間を表わす。つまり、
入力ポートＰIiが接続に対する要求を行ない、これが接
続を認められないものと想定すると、これは、持続期間
ｔp に等しい値の時間間隔の後に要求を再度行なう。こ
のようにして、この持続期間は実質的にはクレジットが
授与されるレートを表わす。システムが初期設定される
とき、持続期間レジスタ３１及び基本割り当て量レジス
タ３２にはこれら値がロードされる。
を持つ二つのレジスタが存在する。レジスタ３１は持続
期間（persistence interval）ｔp を含み、レジスタ３
２は基本割り当て量ｑb を含む。持続期間は同一リクエ
スタの二つの連続する要求間の時間を表わす。つまり、
入力ポートＰIiが接続に対する要求を行ない、これが接
続を認められないものと想定すると、これは、持続期間
ｔp に等しい値の時間間隔の後に要求を再度行なう。こ
のようにして、この持続期間は実質的にはクレジットが
授与されるレートを表わす。システムが初期設定される
とき、持続期間レジスタ３１及び基本割り当て量レジス
タ３２にはこれら値がロードされる。
【００２２】各入力ポートはそれと関連する２つのレジ
スタを持つ。持続カウンタ５０−Ｉは図２のタイマ２０
−Ｉに対応し、サービスタイムレジスタ５１−Ｉは図２
サービスクレジット計算機２１−Ｉに対応する。スケジ
ューラは持続カウンタ５０−Ｉをレジスタ３１内の値に
初期化し、サービスタイマ５１−Ｉをレジスタ３２の値
に初期化する。
スタを持つ。持続カウンタ５０−Ｉは図２のタイマ２０
−Ｉに対応し、サービスタイムレジスタ５１−Ｉは図２
サービスクレジット計算機２１−Ｉに対応する。スケジ
ューラは持続カウンタ５０−Ｉをレジスタ３１内の値に
初期化し、サービスタイマ５１−Ｉをレジスタ３２の値
に初期化する。
【００２３】パケットが入りポート（例えば、ポートＰ
Ii）の入力待ち行列５２−Ｉの先頭に到達すると直ち
に、これは、スケジューラ３７に要求を行なう。即座の
接続が拒否されると、個のサービス時間カウンタ５１−
Ｉがリクエスタの優先クラスと関連するクレジットレー
トＣに等しい量だけ増分され、持続カウンタ５０−Ｉは
減分を開始する。ポートＰIiによる新たな要求は持続カ
ウンタが満了するまで（つまり、これがゼロになるま
で）考慮されない。ポートＰIiが接続を再度拒否される
と、上の手順が反復される。但し、これが接続を授与さ
れると、これは、サービス時間カウンタ５１−Ｉによっ
て示される期間、或は必要とされる接続期間のいずれか
小さい期間だけこの接続を使用する。ポートが接続の使
用を終えると、サービス時間カウンタ５１−Ｉは再び基
本割り当て量３２レジスタ（ｑb ）の値に初期化され
る。持続カウンタ５０−Ｉもカウンタがリセットされる
度に持続期間レジスタ３１の値に初期設定される。
Ii）の入力待ち行列５２−Ｉの先頭に到達すると直ち
に、これは、スケジューラ３７に要求を行なう。即座の
接続が拒否されると、個のサービス時間カウンタ５１−
Ｉがリクエスタの優先クラスと関連するクレジットレー
トＣに等しい量だけ増分され、持続カウンタ５０−Ｉは
減分を開始する。ポートＰIiによる新たな要求は持続カ
ウンタが満了するまで（つまり、これがゼロになるま
で）考慮されない。ポートＰIiが接続を再度拒否される
と、上の手順が反復される。但し、これが接続を授与さ
れると、これは、サービス時間カウンタ５１−Ｉによっ
て示される期間、或は必要とされる接続期間のいずれか
小さい期間だけこの接続を使用する。ポートが接続の使
用を終えると、サービス時間カウンタ５１−Ｉは再び基
本割り当て量３２レジスタ（ｑb ）の値に初期化され
る。持続カウンタ５０−Ｉもカウンタがリセットされる
度に持続期間レジスタ３１の値に初期設定される。
【００２４】複数の要求がスケジューラによって考慮さ
れる場合は、比較器３５（これは、図２の比較器２６に
対応する）が各出力ポートに対してこれへの接続を要求
し、それらのサービスタイマレジスタ内の同一の高い値
を持つ全ての入力ポートを識別する。この手順によっ
て、一つの入力ポートのみが出力ポートへの接続のため
に選択された場合は、上に説明されるように、この入力
ポートにその接続が授与される。そうでなく、一つ以上
の入力ポートが比較器３５によって選択された場合は、
セレクタ３６（図２のセレクタ２５に対応）はこれらの
中から任意の（事前に選択された）アルゴリズム、例え
ば、ラウンドロビン（round-robin ）或は固定優先（fi
xed priority）に従って一つのみを選択する。比較器３
５及びセレクタ３６の回路の実現は単純明解である。こ
れら実現の細部はここに説明の方法の動作に大きな影響
は持たないが、但し、我々は、セレクタのためのラウン
ドロビンスキームがより公平な特性を提供するものと信
じる。
れる場合は、比較器３５（これは、図２の比較器２６に
対応する）が各出力ポートに対してこれへの接続を要求
し、それらのサービスタイマレジスタ内の同一の高い値
を持つ全ての入力ポートを識別する。この手順によっ
て、一つの入力ポートのみが出力ポートへの接続のため
に選択された場合は、上に説明されるように、この入力
ポートにその接続が授与される。そうでなく、一つ以上
の入力ポートが比較器３５によって選択された場合は、
セレクタ３６（図２のセレクタ２５に対応）はこれらの
中から任意の（事前に選択された）アルゴリズム、例え
ば、ラウンドロビン（round-robin ）或は固定優先（fi
xed priority）に従って一つのみを選択する。比較器３
５及びセレクタ３６の回路の実現は単純明解である。こ
れら実現の細部はここに説明の方法の動作に大きな影響
は持たないが、但し、我々は、セレクタのためのラウン
ドロビンスキームがより公平な特性を提供するものと信
じる。
【００２５】
【発明の効果】以上説明したように本発明によれば、プ
ロセッサ共有の公平さ特性と先着順処理との効率の均衡
を保つ適応スケジューリングシステムが得られる。
ロセッサ共有の公平さ特性と先着順処理との効率の均衡
を保つ適応スケジューリングシステムが得られる。
【図１】本発明を実現するシステム全体の略図。
【図２】図１のスケジューラをより詳細に示すブロック
図面。
図面。
【図３】本発明を実現するために使用される一般化され
たアルゴリズムの流れ図。
たアルゴリズムの流れ図。
【図４】本発明の好ましい実施例を図解するために使用
される一例としてのタイミング図。
される一例としてのタイミング図。
【図５】データを入力と出力ポート間で交換するための
本発明の装置を簡略的に示すブロック図。
本発明の装置を簡略的に示すブロック図。
１５，３７ スケジューラ １６ 共通資源 ２０−１〜２０−Ｎ タイマ ２１−１〜２１−Ｎ サービスクレジット計算機 ２５，３６ セレクタ ２６，３５ 比較機 ３７ クロスバー交換器
───────────────────────────────────────────────────── フロントページの続き (72)発明者 アッサー、ナスレルディン、タンタウイ アメリカ合衆国ニューヨーク州、マホパッ ク、メイプル、ヒル、ドライブ、31 (72)発明者 アハメド、ナスル‐エル‐ディン、タンタ ウイ アメリカ合衆国ニューヨーク州、ヨークタ ウン、ハイツ、チエスナット、コート、 397
Claims (13)
- 【請求項１】コンピュータシステム内において使用され
る共通資源に対するアクセスをこの資源へのアクセスを
要求している複数のリクエスタＲ1 、Ｒ2 、…ＲN に授
与するための適応スケジューリング方法において、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタ（ＲI ）に対するその待ち時間（ＷI ）
を検出するステップと、 ＴI がＷI の関数であり、ＴI がＲI の前記資源への各
アクセスの後に初期値ｑb にリターンし、ｑb は定数で
あるとき各リクエスタＲI に最大アクセス時間ＴI を供
与するステップとを含むことを特徴とする適応スケジュ
ーリング方法。 - 【請求項２】コンピュータシステム内において使用され
る共通資源に対するアクセス時間をこの資源へのアクセ
スを要求している複数のリクエスタ（Ｒ1 、Ｒ2 、…Ｒ
N ）に動的に授与するための適応スケジューリング方法
において、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタＲI に対するその待ち時間ＷIを検出す
るステップと、 サービスクレジットＣI 前記待ち時間ＷI の関数であ
り、このクレジットＣIが各リクエスタＲI に前記資源
へのアクセスを要求した後に前記資源へのアクセスを拒
否されたときにのみ授与されるとしたとき前記の各リク
エスタに対するサービスクレジットＣI を決定するステ
ップと、 ＴI ＝ｑb ＋ＣI であり、ここで、ｑb は定数であり、
ＴI が前記資源へのＲI の各アクセスの後にｑb にリタ
ーンするとき、各リクエスタＲI に前記資源を使用する
ための最大アクセス時間ＴI を供与するステップと含む
ことを特徴とする適用スケジューリング方法。 - 【請求項３】各ＣI 及びｑb が前記複数のリクエスタの
リクエスタＲI と関連する優先クラスの関数でもあり、
この優先クラスが前記待ち時間ＴI を通じて一定に留ま
ることを特徴とする請求項２記載の適応スケジューリン
グ方法。 - 【請求項４】前記資源へのアクセスが前記複数のリクエ
スタの中の最も大きなサービスクレジットＣM を持つリ
クエスタＲM に授与され、ここで、１≦Ｉ≦Ｍであるこ
とを特徴とする請求項２記載の適応スケジューリング方
法。 - 【請求項５】コンピュータシステム内において使用され
る共通資源に対するアクセス時間をこの資源へのアクセ
スを要求している複数のリクエスタ（Ｒ1 、Ｒ2 、…Ｒ
N ）に授与するための適応スケジューリング方法におい
て、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタＲI に対する待ち時間ＷI を検出するス
テップと、 サービスクレジットＣI が前記待ち時間ＷI の関数であ
り、このクレジットＣI が各リクエスタＲI に前記資源
へのアクセスを要求した後に前記資源へのアクセスを拒
否されたときにのみ授与されるとしたとき、前記の各リ
クエスタに対するサービスクレジットＣI を決定するス
テップと、 １≦Ｍ≦Ｎ、及びＴM ＝ｑb ＋ＣM であり、ここで、ｑ
b は定数であり、ＴMは前記資源へのＲM の各アクセス
の後にｑb にリターンし、ＲM は各アクセスの直後にサ
ービスクレジットを持たないとしたとき、各リクエスタ
ＲI に最大アクセス時間ＴM を供与するステップと含む
ことを特徴とする適応スケジューリング方法。 - 【請求項６】交換システム内において使用される入力ポ
ートＰI1、ＰI2、…ＰINと出力ポートＰO1、ＰO2、…Ｐ
ONとの間でデータを交換するための適応スケジューリン
グ方法において、 ＷI がＰIIが前記出力ポートの一つへの接続を前記接続
に対する要求を行なって以来待っている時間ＰItであり
るとき、各入力ポートＰIIに対する待ち時間ＷI を検出
するステップと、 ＴI がＷI の関数であり、またＴI
が前記接続が切断された後に一定の値ｑb にリターンす
るとき、前記出力ポートへの一つへの接続を前記一つの
出力ポートへの接続を要求している各入力ポートＰIIに
ＴI の最大接続時間だけ供与するステップと含むことを
特徴とする適応スケジューリング方法。 - 【請求項７】コンピュータシステム内において使用され
る共通資源に対するアクセスをこの資源へのアクセスを
要求している複数のリクエスタＲ1 、Ｒ2 、…ＲN に供
与するための適応スケジューリング装置において、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタ（ＲI ）に対する待ち時間（ＷI ）を検
出する手段と、 ＴI がＷI の関数であり、ＴI はＲI の前記資源への各
アクセスの後に初期値ｑb にリターンし、ｑb は定数で
あるとしたとき、各リクエスタＲI に最大アクセス時間
ＴI を供与する手段と含むことを特徴とする適応スケジ
ューリング装置。 - 【請求項８】コンピュータシステム内において使用され
る共通資源に対するアクセス時間をこの資源へのアクセ
スを要求している複数のリクエスタ（Ｒ1 、Ｒ2 、…Ｒ
N ）に動的に供与するための適応スケジューリング装置
において、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタＲI に対する待ち時間ＷI を検出する手
段と、 サービスクレジットＣI が前記待ち時間ＷI の関数であ
り、このクレジットＣI が各リクエスタＲI に前記資源
へのアクセスを要求した後に前記資源へのアクセスを拒
否されたときにのみ授与されるものとしたとき、前記の
各リクエスタに対するそのサービスクレジットＣI を決
定する手段と、 ＴI ＝ｑb ＋ＣI であり、ここで、ｑb は定数であり、
ＴI は前記資源へのＲI の各アクセスの後にｑb にリタ
ーンするものとしたとき、各リクエスタＲI に前記資源
を使用するための最大アクセス時間ＴI を供与する手段
と含むことを特徴とする適応スケジューリング装置。 - 【請求項９】各ＣI 及びｑb が前記複数のリクエスタの
リクエスタＲI と関連する優先クラスの関数でもあり、
この優先クラスが前記待ち時間ＴI を通じて一定に留ま
ることを特徴とする請求項８記載の適応スケジューリン
グ装置。 - 【請求項１０】コンピュータシステム内において使用さ
れる共通資源に対するアクセス時間をこの資源へのアク
セスを要求している複数のリクエスタ（Ｒ1 、Ｒ2 、…
ＲN ）に供与するための適応スケジューリング装置にお
いて、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタ（ＲI ）に対する待ち時間ＷIを検出す
る手段と、 サービスクレジットＣI が前記待ち時間ＷI の関数であ
り、このクレジットＣI が各リクエスタＲI に前記資源
へのアクセスを要求した後に前記資源へのアクセスを拒
否されたときにのみ授与されるものとしたとき、前記の
各リクエスタに対するサービスクレジットＣI を決定す
る手段を含と、 １≦Ｍ≦Ｎ、及びＴM ＝ｑb ＋ＣM であり、ここで、ｑ
b は定数であり、ＴMは前記資源へのＲM の各アクセス
の後にｑb にリターンし、ＲM は各アクセスの直後にサ
ービスクレジットを持たないものとしたとき、各リクエ
スタＲI に最大アクセス時間ＴM を供与する手段と含む
ことを特徴とする適応スケジューリング装置。 - 【請求項１１】コンピュータシステム内において使用さ
れる共通資源に対するアクセスをこの資源へのアクセス
を要求している複数のリクエスタＲ1 、Ｒ2 、…ＲN に
供与するための適応スケジューリング方法において、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタ（ＲI ）に対する待ち時間（ＷI ）を検
出するステップと、 ＴI がＷI の関数であり、ＴI はＲI の前記資源への各
アクセスの後に初期値ｑb にリターンし、ｑb は定数で
り、また各リクエスタＲI が全セッションを通じて同一
の優先レベルを保持するとしたとき、各リクエスタＲI
に最大アクセス時間ＴI を供与するステップと含むこと
を特徴とする適応スケジューリング方法。 - 【請求項１２】コンピュータシステム内において使用さ
れる共通資源に対するアクセス時間をこの資源へのアク
セスを要求している複数のリクエスタ（Ｒ1 、Ｒ2 、…
ＲN ）に動的に供与するための適応スケジューリング装
置において、 ＷI をＲI がアクセスの要求以来前記共有資源へのアク
セスを待っている期間（１≦Ｉ≦Ｎ）としたとき、前記
の各リクエスタＲI に対する待ち時間ＷI を検出する手
段と、 サービスクレジットが前記待ち時間ＷI の関数であり、
このクレジットＣI が各リクエスタＲI に前記資源への
アクセスを要求した後に前記資源へのアクセスを拒否さ
れたときにのみ授与されるものとしたとき、前記の各リ
クエスタに対するサービスクレジットＣI を決定する手
段と、 ＴI ＝ｑb ＋ＣI であり、ここで、ｑb は定数であり、
ＴI は前記資源へのＲI の各アクセスの後にｑb にリタ
ーンし、また各リクエスタＲI は全セッションを通じて
同一の優先レベルを維持するとしたとき、各リクエスタ
ＲI に前記資源を使用するための最大アクセス時間ＴI
を供与する手段と含むことを特徴とする適応スケジュー
リング装置。 - 【請求項１３】交換システム内において使用される入力
ポートＰI1、ＰI2、…ＰINと出力ポートＰO1、ＰO2、…
ＰONとの間でデータを交換するための適応スケジューリ
ング装置において、 ＷI がＰIIが前記出力ポートの一つへの接続を前記接続
に対する要求を行なって以来待っている時間ＰItである
とき、各入力ポートＰIIに対する待ち時間ＷIを検出す
る手段と、 ＴI はＷI の関数であり、またＴI が前記接続が切断さ
れた後に一定の値ｑbにリターンするとしたとき、前記
出力ポートへの一つへの接続を前記一つの出力ポートへ
の接続を要求している各入力ポートＰIIにＴI の最大接
続時間だけ供与する手段と含むことを特徴とする適応ス
ケジューリング装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US77797091A | 1991-10-17 | 1991-10-17 | |
| US777970 | 1991-10-17 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05210523A true JPH05210523A (ja) | 1993-08-20 |
Family
ID=25111872
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4221476A Pending JPH05210523A (ja) | 1991-10-17 | 1992-08-20 | 適応スケジューリング方法及び装置 |
Country Status (3)
| Country | Link |
|---|---|
| EP (1) | EP0537509A3 (ja) |
| JP (1) | JPH05210523A (ja) |
| CA (1) | CA2072729A1 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2012505572A (ja) * | 2008-10-14 | 2012-03-01 | ノーテル・ネットワークス・リミテッド | 重み付けされた公平な待ち行列管理のための方法およびシステム |
| KR101491689B1 (ko) * | 2013-07-24 | 2015-02-11 | 한국과학기술정보연구원 | 다중 사용자를 위한 자원 할당 방법 및 장치 |
| JP2018005851A (ja) * | 2016-07-08 | 2018-01-11 | 株式会社デンソー | 電子装置 |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| DE69831857T2 (de) * | 1998-06-10 | 2006-06-14 | Sun Microsystems Inc | Verfahren und Vorrichtung zum Zeitplanen von Prozessen für Betriebsmittelzuteilung |
| EP0964333A1 (en) | 1998-06-10 | 1999-12-15 | Sun Microsystems, Inc. | Resource management |
| US8521472B2 (en) * | 2009-09-18 | 2013-08-27 | International Business Machines Corporation | Method to compute wait time |
| CN109558227B (zh) * | 2018-11-12 | 2023-03-31 | 中国航空工业集团公司西安飞行自动控制研究所 | 一种基于任务执行预算的单调速率任务调度方法 |
-
1992
- 1992-06-29 CA CA 2072729 patent/CA2072729A1/en not_active Abandoned
- 1992-08-20 JP JP4221476A patent/JPH05210523A/ja active Pending
- 1992-09-22 EP EP19920116148 patent/EP0537509A3/en not_active Withdrawn
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2012505572A (ja) * | 2008-10-14 | 2012-03-01 | ノーテル・ネットワークス・リミテッド | 重み付けされた公平な待ち行列管理のための方法およびシステム |
| US8711871B2 (en) | 2008-10-14 | 2014-04-29 | Rockstar Consortium US LLP | Method and system for weighted fair queuing |
| US9042224B2 (en) | 2008-10-14 | 2015-05-26 | Rpx Clearinghouse Llc | Method and system for weighted fair queuing |
| JP2015109672A (ja) * | 2008-10-14 | 2015-06-11 | ノーテル・ネットワークス・リミテッド | 重み付けされた公平な待ち行列管理のための方法およびシステム |
| KR101491689B1 (ko) * | 2013-07-24 | 2015-02-11 | 한국과학기술정보연구원 | 다중 사용자를 위한 자원 할당 방법 및 장치 |
| JP2018005851A (ja) * | 2016-07-08 | 2018-01-11 | 株式会社デンソー | 電子装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0537509A3 (en) | 1993-10-13 |
| CA2072729A1 (en) | 1993-04-18 |
| EP0537509A2 (en) | 1993-04-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6909691B1 (en) | Fairly partitioning resources while limiting the maximum fair share | |
| US7149227B2 (en) | Round-robin arbiter with low jitter | |
| US5301333A (en) | Tree structured variable priority arbitration implementing a round-robin scheduling policy | |
| US6804738B2 (en) | Method and apparatus for scheduling a resource to meet quality-of-service restrictions | |
| CN101266557B (zh) | 在客户机-服务器或主机环境中计算作业的多目标分配 | |
| US6052375A (en) | High speed internetworking traffic scaler and shaper | |
| JP4245693B2 (ja) | 待ち行列中での待ち時間推定方法 | |
| US6420901B2 (en) | Quantized queue length arbiter | |
| US5564062A (en) | Resource arbitration system with resource checking and lockout avoidance | |
| US20070174529A1 (en) | Queue manager having a multi-level arbitrator | |
| US8286173B2 (en) | Methods and apparatus for window-based fair priority scheduling | |
| US9361474B2 (en) | Network filesystem asynchronous I/O scheduling | |
| JP2006202244A (ja) | ソースデバイスに対するリクエストをスケジューリングする装置及び方法 | |
| JPH07200318A (ja) | 動的優先タスク・スケジューラを有するデータ処理システム | |
| US7142552B2 (en) | Method and system for priority enforcement with flow control | |
| JPH05210523A (ja) | 適応スケジューリング方法及び装置 | |
| US8140728B1 (en) | Data packet arbitration system | |
| JP3545931B2 (ja) | 呼制御スケジューリング方法 | |
| US20010043612A1 (en) | Apparatus and method for resource arbitration | |
| US8863134B2 (en) | Real time scheduling system for operating system | |
| US8254401B2 (en) | Device for shared management of a resource among several users | |
| JPS58107962A (ja) | スケジユ−リング方式 | |
| Karatza et al. | Performance analysis of parallel job scheduling in distributed systems | |
| CN121209799B (zh) | 存储设备的提交队列仲裁方法和电子设备 | |
| Bulgren et al. | A simulation study of time-slicing in non-exponential service environment |