(57)【特許請求の範囲】
【請求項１】
各リクエストが複数の優先順位レベルの１つと関連づけられ、実行すべきリクエストをキューする方法であって、
複数のエントリを含むキューを生成するステップであって、各エントリがそれぞれ優先順位レベルに対応し、且つ複数のリクエストが１つのエントリにキューされ得る、ステップと、
関連する優先順位を持った新しいリクエストを、キューにエンキューするために受け取るステップと、
前記新しいリクエストを受け取った後に、先頭ポインタによって指し示されたエントリを決定するステップと、
調整された優先順位が前記先頭ポインタによって指し示されたエントリとは異なるエントリと関連づけられるように、前記新しいリクエストが持つ関連する優先順位に、先頭ポインタによって指し示されたエントリの優先順位を加えた値だけ調整するステップと、
前記調整された優先順位と関連する１つのエントリにおいて前記新しいリクエストをキューするステップと、
を含む方法。
【請求項２】
各エントリはリンク・リストを指し示すことができ、
先頭ポインタが指し示すエントリが保留のリクエストのリンク・リストを指し示すかどうかを決定するステップと、
これが否定される場合、先頭ポインタは、次のエントリを指し示すようにインクリメントするステップと、
前記先頭ポインタによって指し示されたエントリにおいてキューされたリクエストを処理するステップと、
を更に含む請求項１に記載の方法。
【請求項３】
前記キューされたリクエストは記憶システムに関する入出力（Ｉ／Ｏ）リクエストを含み、
前記リクエストを処理するステップはリクエストされたＩ／Ｏオペレーションを実行するために前記Ｉ／Ｏリクエストをディスパッチするステップを含む、
請求項２に記載の方法。
【請求項４】
各エントリはリンク・リストを指し示すことができ、
前記エントリにおいて新しいリクエストをキューするステップは前記リクエストに割り当てられた優先順位と関連するエントリによって指し示されたリンク・リストに前記新しいリクエストを加えるステップを含む、
請求項１に記載の方法。
【請求項５】
前記キューは、最後のエントリが先頭のエントリを指し示す循環式キューであり、
前記優先順位を調整するステップは、前記調整された優先順位が前記キューにおけるエントリの数よりも大きい場合、前記調整された優先順位をｐ’とし、前記キューにおけるエントリの数を（ｎ＋１）としたとき、ｐ’モジュロ（ｎ＋１）に設定するステップを更に含む、
請求項１に記載の方法。
【請求項６】
前記キューは前記システムにおける各優先順位に対応するエントリの他に１つのエクストラ・エントリを含む請求項１に記載の方法。
【請求項７】
前記新しいリクエストは、前記先頭ポインタによって指し示されたエントリではない前記調整された優先順位に対応するエントリにおいてキューされる請求項６に記載の方法。
【請求項８】
各リクエストが複数の優先順位レベルの１つと関連づけられ、実行すべきリクエストをキューするシステムであって、
複数のエントリを含むキューを生成する手段であって、各エントリがそれぞれ優先順位レベルに対応し、且つ複数のリクエストが１つのエントリにキューされ得る、手段と、
関連する優先順位を持った新しいリクエストを、キューにエンキューするために受け取る手段と、
前記新しいリクエストを受け取った後に、先頭ポインタによって指し示されたエントリを決定する手段と、
調整された優先順位が前記先頭ポインタによって指し示されたエントリとは異なるエントリと関連づけられるように、前記新しいリクエストが持つ関連する優先順位に、先頭ポインタによって指し示されたエントリの優先順位を加えた値だけ調整する手段と、
前記調整された優先順位と関連する１つのエントリにおいて前記新しいリクエストをキューする手段と、
を含むシステム。
【請求項９】
各リクエストが複数の優先順位レベルの１つと関連づけられているシステムにおいて、実行すべきリクエストをキューするために処理ユニットをプログラムする時に使用するためであって、前記処理ユニットに請求項１〜請求項７の何れかに記載された方法の各ステップを実行させる少なくとも１つの組み込まれたコンピュータ・プログラムを含むコンピュータ読み取り可能な記憶媒体。
【請求項１０】
複数のエントリを含むキューであって、各優先順位レベルに対応するエントリ及び少なくとも１つの更なるエントリが存在し、複数のリクエストが任意のエントリにおいてキューされ得る、キューと、
前記キューにおける１つのエントリをアドレスする先頭ポインタを含むメモリ装置であって、
調整された優先順位が前記先頭ポインタによって指し示されたエントリとは異なるエントリと関連づけられるように、前記新しいリクエストが持つ関連する優先順位に前記先頭ポインタによって指し示されたエントリの優先順位を加えることによって、前記新しいリクエストが持つ関連する優先順位が調整され、前記調整された優先順位と関連する１つのエントリにおいて前記新しいリクエストがキューされる、メモリ装置。
【請求項１１】
各エントリはリンク・リストを指し示すことができ、
先頭ポインタが指し示すエントリが保留のリクエストのリンク・リストを指し示すかどうかを決定し、これが否定される場合、先頭ポインタは、次のエントリを指し示すようにインクリメントする、  請求項１０に記載のメモリ装置。
【請求項１２】
少なくとも１つのリンク・リストを更に含み、
各エントリは１つのリンク・リストを指し示すことができ、
エントリにおいて１つの新しいリクエストをキューすることは、前記新しいリクエストに割り当てられた優先順位と関連するエントリによって指し示されたリンク・リストに前記新しいリクエストを加えることを含む、
請求項１０に記載のメモリ装置。
【請求項１３】
前記キューは、最後のエントリが先頭のエントリを指し示す循環式キューであり、
前記優先順位を調整することは、前記調整された優先順位が前記キューにおけるエントリの数よりも大きい場合、前記調整された優先順位をｐ’とし、前記キューにおけるエントリの数を（ｎ＋１）としたとき、ｐ’モジュロ（ｎ＋１）に設定する、
請求項１０に記載のメモリ装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、種々の優先順位レベルを持ち得るリクエストをキューするためのシステム、方法、プログラム、及びデータ構造に関するものである。
【０００２】
【従来の技術】
従来技術のサーバでは、サーバが複数のクライアントから入出力（Ｉ／Ｏ）リクエストを受け取り、記憶装置に対して実行するためにそれらのリクエストをその受け取った順序でキューする。或る従来技術のネットワーク・システムでは、クライアントはＩ／Ｏリクエストの優先順位をサーバに送らない。その代わり、各クライアントは内部的にリクエストを優先順位付け、低い優先順位のリクエストを送る前に高い優先順位のリクエストを送るであろう。クライアントは低い優先順位のリクエストを送ることを抑制する。それは、サーバがその優先順位を知らない場合、高優先順位のリクエストの前に低優先順位のリクエストを送ることはサーバに、高優先順位のリクエストの前に低優先順位リクエストをキューさせることがあり得るためである。従って、クライアントは、高優先順位のリクエストが送られてしまうまで低優先順位のリクエストを送ることを遅らせる。
【０００３】
各クライアントにＩ／Ｏリクエストを個々に優先順位付けさせるという技法は少なくとも２つの理由で問題がある。第１は、種々のサーバ資源を利用するＩ／Ｏリクエストをサーバが同時に処理することができるかも知れないということである。従って、サーバは、それが２つの高優先順位のリクエストを同時に処理することができない時に、異なる資源を必要とする高優先順位のリクエスト及び低優先順位のリクエストを同時に処理することができるかも知れない。クライアントは、それがサーバにおける処理能力及び資源の可用性を知らないので、サーバが高優先順位のリクエスト及び低優先順位のリクエストの両方を同時に処理することによって実際にスループットを最適化することができる時でも、高優先順位のリクエストだけを送り、低優先順位のリクエストを抑制するかも知れない。更に、低優先順位のリクエスト及び高優先順位のリクエストが記憶媒体における物理的に隣接したロケーションに記憶される場合、サーバが高優先順位のリクエストの前に低優先順位のリクエストを処理する方がより効果的であることもある。ディスク・ヘッドが既に低優先順位のリクエストのロケーションに隣接している時、その低優先順位のリクエストを高優先順位のリクエストの前に処理することは、低優先順位のリクエストの記憶ロケーションをシークしてそこに移動する必要を回避するであろう。
【０００４】
クライアントがリクエストを優先順位付けすることによるもう１つの問題は、クライアント相互間にリクエストの優先順位付けがないことである。例えば、クライアントＡが優先順位１及び２のＩ／Ｏリクエストを有し、クライアントＢが優先順位３のＩ／Ｏリクエストを有する時、両方が自分の最高優先順位のＩ／Ｏリクエストを送る場合、クライアントＡは優先順位１のリクエストを送るであろうし、クライアントＢは優先順位３のリクエストを送るであろう。クライアントＡは、すべての優先順位１のリクエストが送られてしまうまで優先順位２のリクエストを抑制するであろう。クライアントＢが優先順位３のリクエストを送った後にクライアントＡが優先順位２のＩ／Ｏリクエストを送る場合、サーバは優先順位３のリクエストを先に処理するであろう。この状況は、サーバがクライアントＡからの遅れて送られた優先順位２のリクエストを処理する前に、クライアントＢの優先順位３のＩ／Ｏリクエストを完了してしまうことがあるので最適ではない。
【０００５】
クライアントが自身の優先順位付けを行うことを可能にすることによって上記の非効率なことが生じるものと仮定して、クライアントがＩ／Ｏリクエストと共に優先順位情報を送ることを可能にするための従来技術の技法が開発された。例えば、小型コンピュータ用周辺機器インターフェース（ＳＣＳＩ）は２つの優先順位、即ち、高優先順位及び低優先順位を可能にし、インターナショナル・ビジネス・マシーンズ（ＩＢＭ）社のエンタープライズ・システム接続（Enterprise System Communication-ＥＳＣＯＮ）は、サーバが２５６個の異なる優先順位レベルでコミュニケートすることを可能にする。（なお、ＥＳＣＯＮはＩＢＭ社の商標である）。ＳＣＳＩの場合、サーバは、先頭部及び末尾部を持ったＩ／Ｏリクエストに対するキューを維持するであろう。高優先順位のリクエストはキューの先頭部でエンキューされ、低優先順位のリクエストは末尾部においてエンキューされる。ＳＣＳＩサーバはリクエストを先頭部からデキューする。
【０００６】
従来技術のＳＣＳＩ優先順位システムによる１つの問題点は、ＳＣＳＩサーバが高優先順位のリクエストを表すストリームを受け取る場合、それは、かなりの期間の間低優先順位のリクエストに達しないであろうということである。この期間はスターベーション（ｓｔａｒｖａｔｉｏｎ）とも呼ばれ、実際には、低優先順位のリクエストをタイムアウトさせるに十分な大きさである。従来技術のＥＳＣＯＮシステムでは、ＥＳＣＯＮサーバが２５６個の優先順位の各々に対して別個のキューを維持し、保留のＩ／Ｏリクエストを有する最高優先順位のキューからのＩ／Ｏリクエストをアクセスする。ＥＳＣＯＮでは、ＳＣＳＩの場合のように、高優先順位のＩ／Ｏリクエストの定常ストリームが低優先順位のリクエストの処理をかなり遅らせるであろう。
【０００７】
低優先順位のＩ／Ｏリクエストに関するこのスターベーションの問題に対する１つの従来技術の解決方法は、低優先順位のリクエストを高優先順位のリクエストに移すことによって低優先順位のリクエストの優先順位を一時的に高めることである。例えば、所定数の高優先順位のリクエストをエンキューした後、サーバは低優先順位のリクエストをより高い優先順位のキューに移してもよい。この技法は、わずかな数の優先順位レベルしかない時に幾分か効果的に作用する。しかし、サーバが追跡する可能な優先順位の数が増加するので、１つのキューから別にキューに優先順位を移すこと、即ち、Ｉ／Ｏリクエストをデキュー及びエンキューすることは、メモリ・パフォーマンスをかなり低下させるポイントまでかなりのメモリ資源を消費することがある。サーバ、例えば、Ｉ／Ｏプロセッサが複数優先順位のキューを維持する場合、そのサーバは、低優先順位のリクエストの優先順位が高くさせられる度にその低優先順位のリクエストを移さなければならないであろう。例えば、或る低優先順位のリクエストが２５６番目の優先順位キューにある場合、そのようなリクエストは、処理される前に、２５５回も移されることがあるということが考えられる。数多くのリクエストが移されようとしている場合、Ｉ／Ｏリクエストを移すための、即ち、キュー相互間でエンキュー及びデキューするためのメモリ・オペレーションがメモリ全体のパフォーマンスをかなり低下させることがあり得る。
【０００８】
サーバによって管理される優先順位キューの数が増加する時、従来技術の場合、メモリの負担は２つの部分を持つ。第１に、サーバは数多くの優先順位キューを管理しなければならない。第２に、優先順位がスターベーションを回避するために上向きに調整される時、低優先順位のリクエストをキューからキューに移すために必要なデキュー及びエンキュー・オペレーションにおけるかなりの増加がある。
【０００９】
【発明が解決しようとする課題】
従って、従来技術においては、メモリに大きな負担をかけないような方法で、クライアントがＩ／Ｏリクエストと共に優先順位を伝達する時、低優先順位のＩ／Ｏリクエストの優先順位を高くするための改良された機構を提供する必要がある。
【００１０】
【課題を解決するための手段】
上記の従来技術における制限事項を克服するために、本発明の望ましい実施例はリクエストをキューするための方法、システム、プログラム、及びデータ構造を開示する。各リクエストは複数の優先順位レベルの１つと関連づけられる。複数のエントリを含むキューが生成される。各エントリは１つの優先順位レベルに対応し、１つのエントリにおいて複数のリクエストがキューされることが可能である。関連の優先順位を持った新しいリクエストがそのキューにおいてエンキューするために受け取られる時、ポインタによって指し示されたエントリの決定が行われる。新しいリクエストと関連した優先順位は、調整後の優先順位がポインタによって指示されたエントリとは異なるエントリと関連するように或る値によって調整される。新しいリクエストは、その調整された優先順位と関連した１つのエントリにおいてキューされる。
【００１１】
更なる実施例では、キューされたリクエストを処理するために、リクエストがキューされるエントリに関する決定が行われる。その決定されたエントリを指し示すようにポインタが修正され、そのポインタによって指し示されたエントリにキューされたリクエストが処理される。
【００１２】
更なる実施例では、優先順位を調整することは、ポインタによって指し示されたエントリの優先順位を決定すること及びその決定された優先順位をリクエストの優先順位に加え、調整された優先順位を決定することを含む。キューの最後のエントリがキューの最初のエントリを指し示すという実施例では、優先順位を調整することは、更に、その調整された優先順位がキューにおけるエントリの数よりも大きいかどうかを決定することを含む。それが肯定される場合、調整された優先順位は、「調整された優先順位モジュロ・キューにおけるエントリの数」に設定される。
【００１３】
望ましい実施例は、低い優先順位を持った現在保留中のリクエストに関して新しいリクエストの優先順位を有効に下げる，Ｉ／Ｏリクエストをキューするための機構を提供する。望ましい実施例の場合、新しいリクエストの優先順位は、数学的演算の使用を通して低い優先順位のリクエストのスターベーションを防ぐように修正され、低い優先順位のキューされたエントリを新しいキューに移すことを必要とせずにポインタを調整する。これは、優先順位を調整してスターベーションを回避するためには保留のリクエストがキュー相互間で移されることを必要とする従来技術を改善するものである。望ましい実施例のキューは、たとえ複数の可能な優先順位が存在しても、実質的な負担を負わせることなく及びメモリ・パフォーマンスを低下させることなく、スターベーションを回避するように優先順位を調整することができる。
【００１４】
【発明の実施の形態】
以下の説明では、添付図面が参照される。それら図は、本発明の幾つかの実施例の一部を形成し、それらの実施例を図解するものである。別の実施例が利用可能であること、及び本発明の技術的範囲を逸脱することなく構造上及び動作上の変更が行われ得ることは勿論である。
【００１５】
図１は、望ましい実施例が実現されるコンピューティング環境を示す。複数のクライアント・システム２ａ、２ｂ、２ｃがネットワーク６を介してサーバ４にＩ／Ｏリクエストを伝達する。サーバ４は、そのサーバ４のメモリ１０におけるキュー・データ構造８にＩ／Ｏリクエストをエンキューする。サーバ４は、キュー・データ構造８におけるリクエストを処理し、そのリクエストを記憶システム１２に対して実行する。クライアント２ａ、２ｂ、２ｃは、メインフレーム・コンピュータのような任意のタイプの計算装置から成るものでよく、それらは、サーバ４に入出力（Ｉ／Ｏ）コマンドを伝達することができるコンピューティング・アーキテクチャを含んでいる。サーバ４は、複数のクライアントからのリクエストを処理することができる任意のタイプのサーバ装置を含み得るものである。サーバ４は、複数のクライアント２ａ、２ｂ、２ｃからリクエストを受け取り且つそれらのリクエストを１つ又は複数の記憶コントローラに送るＥＳＣＯＮを含み得るものである。
【００１６】
このような実施例では、記憶システム１２は、ＩＢＭ社の文献 "IBM 3990 Storage Control Reference (Models 1, 2, and 3)" ＩＢＭ文献番号 GA32-0099-06 (Copyright IBM Corp. 1988, 1994) において開示された IBM 3990 Storage Controller のような１つ又は複数の記憶装置コントローラ、又は、Brent C. Beardsley, Allan S. Merritt, Michael A. Paulsen, 及び Harry M. Yudenfriendを発明者として１９９８年１０月７日に出願された米国特許出願番号０９/１６７,７８２号の「アドレスを入出力装置に動的に割り当てるための方法及びシステム（Method And System For Dynamically Assigning Addresses To An Input/Output Device）」と題した米国特許出願、及び Brent C. Beardsley, James L. Iskiyan, James McIlvain, Phillip R. Mills, Michael A. Paulsen, William G. Thompson 及び Harry M. Yudenfriend を発明者として１９９８年１０月７日に出願された米国特許出願番号０９/１６８,０１７号の「複数のアドレスを使用する入出力装置をアクセスするためのシステム（System For Accessing An Input/Output Device Using Multiple Addresses）」と題した米国特許出願において開示された記憶装置コントローラ及びホスト・アーキテクチャを含むであろう。
【００１７】
別の方法として、記憶システム１２は、相互接続されたハード・ディスク・ドライブから成るダイレクト・アクセス記憶装置（ＤＡＳＤ）、テープ・ライブラリ等のような記憶媒体を含むものでもよい。このような実施例では、サーバ４は、クライアント２ａ、２ｂ、２ｃからのリクエストされたＩ／Ｏオペレーションを遂行するために、キューされたＩ／Ｏをディスパッチして記憶システム１２に対して実行するであろう。
【００１８】
図２は、望ましい実施例がインプリメントされるキュー・データ構造８の更なる詳細を示す。キュー・データ構造８は、各優先順位に対するエントリ１乃至ｎ及び先頭エントリ０の循環式バッファ又はリング・バッファから成る。そのキューには、先頭エントリ０の他に、そのシステムにおいてサポートされるｎ個の可能な優先順位レベルの各々に対して、ｎ個のエントリが存在する。例えば、ＥＳＣＯＮシステムには、２５７個のエントリ、即ち、２５６個の可能なＥＳＣＯＮ優先順位レベルの各々に対して１つのエントリ及び１つの付加的エントリが存在する。各エントリは、そのエントリの優先順位を持ったＩ／Ｏリクエストのキューに対するポインタ又はアンカを含む。
【００１９】
図２は、エントリ２及び４がその受け取られた順序で番号付けられたＩ／Ｏリクエストを有することを示している。エントリ２は、そのエントリに対応する優先順位、例えば、優先順位レベル２を持ったすべてのＩ／Ｏリクエスト、即ち、Ｉ／Ｏ １、Ｉ／Ｏ ２、Ｉ／Ｏ ４を含むリンク・リスト２２に対するポインタ２０を有する。従って、リンク・リスト２２は、各Ｉ／Ｏリクエストがそのリストにおける次のＩ／Ｏリクエストに対するポインタを含むという単独のリンク・リストから成る。同様に、エントリ４は、第３の受け取られたＩ／Ｏリクエスト（Ｉ／Ｏ ３）を含むリンク・リスト２６に対するポインタ２４を有する。他のエントリも、それぞれ、そのエントリと関連の優先順位である優先順位を持つキューされたＩ／Ｏリクエストを有するリンク・リストを指し示す。
【００２０】
図３は、クライアント２ａ、２ｂ、２ｃからのキューされたＩ／Ｏリクエストを処理するためにサーバ４において実装されるロジックを示す。制御はブロック１００で始まり、サーバ４がキュー８におけるＩ／Ｏリクエストを処理するためのオペレーションを開始し、エントリ０を指し示すように先頭ポインタ１８を初期設定する（ブロック１０２）。サーバ４は、先頭ポインタ１８によって指示されたエントリが保留のＩ／Ｏリクエストを含むリンク・リストを指し示すかどうかを決定する（ブロック１０４）。それが否定される場合、サーバ４は現在のエントリがキュー８における最後のｎ番目のエントリであるかどうかを決定する（ブロック１０６）。これが肯定される場合、サーバ４は、エントリ０を指し示すように先頭ポインタ１８を作動させる（ブロック１０８）。これが否定される場合、先頭ポインタは、キュー８における次のエントリを指し示すようにインクリメントされる（ブロック１１０）。このように、キュー８は、最後のエントリが先頭のエントリを指し示すという循環式キューである。ブロック１０８又は１１０から次のエントリにインクリメントした後、制御はブロック１０６へ再び進み、このエントリが保留のＩ／Ｏリクエストのリンク・リストを指し示すかどうかを決定する。
【００２１】
先頭ポインタ１８によって指し示されたエントリがＩ／Ｏリクエストのリンク・リスト、例えば、図２におけるリスト２２及び２６を指し示す場合、そのリンク・リストにおける各Ｉ／Ｏリクエストを処理するためのループがブロック１１２において始まる。そのリストにおける各Ｉ／Ｏリクエストに対して、サーバ４はそのＩ／Ｏリクエストをアクセスし（ブロック１１４）、そのＩ／Ｏリクエストを記憶システム１２にディスパッチする（ブロック１１６）。更なるＩ／Ｏリクエストが存在する場合、ブロック１１８において、サーバ４は、リンク・リストにおける次のＩ／Ｏリクエストをディスパッチするためにブロック１１２に進む。リンク・リストにおけるすべてのＩ／Ｏリクエストをディスパッチした後、サーバ４はブロック１１８からブロック１０６に進み、先頭ポインタ１８を次のエントリにインクリメントして更なるリンク・リストを考察する。
【００２２】
図４は、キュー８におけるＩ／Ｏリクエストをエンキューするためのサーバ４において実装されたロジックを示す。制御はブロック１５０で始まり、サーバ４は、優先順位ｐを持ったクライアント２ａ、２ｂ、２ｃの１つからＩ／Ｏリクエストを受け取る。そこで、サーバ４は、その受け取ったＩ／Ｏリクエストの優先順位を有効に低くすると同時にその受け取ったＩ／Ｏリクエストに関して既にキューされたＩ／Ｏリクエストの優先順位を高くする。このアルゴリズムは、先頭ポインタ１８が指し示すエントリの優先順位をその受け取ったＩ／Ｏリクエストの優先順位ｐに加えて調整優先順位ｐ' を得る（ブロック１５２）。ｐ' がｎよりも大きい場合、サーバ４は、キュー８の循環的な性質を説明するためにｐ' をｐ' モジュロ（ｎ＋１）に設定する（ブロック１５６）。そこで、サーバ４は、調整された優先順位ｐ' に対応するエントリがリンク・リストを指し示すかどうかを決定する（ブロック１５８）。それが否定される場合、サーバ４はリンク・リストを生成し（ブロック１６０）、その生成されたリンク・リストに対する優先順位ｐ' を有するエントリを指し示す。リンク・リストが存在するか又はそれが生成されていた場合、サーバ４は、エントリｐ' に対するリンク・リストの終わりにＩ／Ｏリクエストをエンキューする。
【００２３】
望ましい実施例のロジックの場合、低い優先順位を有する現在のキューされたＩ／Ｏリクエストは、より高い優先順位におけるＩ／Ｏリクエストの定常ストリームによって長時間停止状態にされないであろう。その理由は、サーバ４が或るエントリにおけるＩ／Ｏリクエストのリンク・リストを処理しようとしている時、如何なる新しいリクエストも（最高の優先順位を持ったリクエストでさえも）、サーバ４が現在処理しようとしている先頭ポインタのエントリに続くエントリにおいてキューされるためである。更に、１つの付加的エントリ、即ち、エントリ０が存在するため、新しいＩ／Ｏリクエストは、サーバ４が処理しようとしている同じエントリにおいて、即ち、先頭ポインタによって指し示されたエントリにおいてキューされることはない。従って、高優先順位のＩ／Ｏリクエストの定常ストリームは、サーバ４がそれらのエントリを通して移ることを妨げないであろう。更に、図４のロジックは、先頭エントリの優先順位を加えることによって新しいリクエストの優先順位を自動的に低くする。いずれかの新しいエントリの優先順位を下げるによって、より低いエントリの優先順位が相対的に高くされる。
【００２４】
図５及び図６は、図３及び図４のロジックが７つの異なるレベルの優先順位を持ったキューにおいて動作する方法を表す例を示す。図５に関しては、キュー２００が、優先順位５、２、及び７を有する３つのＩ／Ｏリクエストｏｐ１、ｏｐ２、及びｏｐ３でもって満たされる。図６では、サーバ４はキュー２００を処理し始め、先頭ポインタをエントリ２に移動する。そのエントリ２は、処理すべきＩ／Ｏリクエストｏｐ２を持った第１エントリである。
【００２５】
図６において、優先順位３を持った新しいＩ／Ｏリクエスト（ｏｐ４）が受け取られる場合、サーバ４は、ｏｐ４の調整された優先順位５を計算するために現在の先頭ポインタ位置２をｏｐ４の優先順位３に加えるであろう。そこで、サーバ４はエントリ５に対するリンク・リストにｏｐ４を加えるであろう。この方法で、サーバ４はｏｐ４の優先順位を低下させる。先頭ポインタがエントリ２にある時に優先順位７を持った別のＩ／Ｏリクエスト（ｏｐ５）が受け取られる場合、調整された優先順位は９である。それは、その調整された優先順位のモジュール及び８，即ち、エントリの数プラス１をサーバに取らせて１という調整された優先順位を得るであろう。そこで、図６に示されるように、サーバ４はｏｐ５をエントリ１に加えるであろう。更に、先頭ポインタに加えられたその調整された優先順位が最後のｎ番目のエントリを通してエントリ０まで延びる場合、新しいＩ／Ｏリクエストはエントリ０においてキューされるであろう。例えば、図６に関して、先頭ポインタがエントリ７にあり、新しいリクエストの優先順位が１である場合、調整された優先順位は８モジュロ８、即ち、０であり、それは第１エントリ、即ち、エントリ０に対応する。
【００２６】
望ましいロジック及びキュー・データ構造は、優先順位キュー相互間で既存のエントリを移動させるためにメモリ・オペレーションを消費することなく優先順位を高めるための技法を提供する。望ましいロジックによってＩ／Ｏリクエストの優先順位を修正するために遂行される唯一のオペレーションは、新しいエントリの優先順位を修正するための簡単なアルゴリズムである。新しいエントリの優先順位のこのような修正はその新しいエントリの優先順位を低くし、高い優先順位のＩ／Ｏリクエストのストリームが現在保留中の低い優先順位のＩ／Ｏリクエストを長時間の停止状態にしないような方法で既存のキューされたＩ／Ｏリクエストの相対的な優先順位を高める。従って、望ましい実施例のキューイング技法は、キュー相互間で保留のエントリを動かすための従来技術において使用される高価なメモリ・オペレーションを遂行することなく優先順位を操作する。
【００２７】
望ましい実施例の場合、システムは、低い優先順位のキューされたリクエストを種々の優先順位のキュー相互間で動かす必要がないので、メモリ処理に影響を与えることなく任意の数の優先順位レベルに適応するように設計可能である。これは、多数のキューを管理することに関連したメモリ管理オペレーションを減らす。従って、その望ましい技法の場合、リスト操作の必要がない。その代わり、優先順位の調整は、単一のキューに関する簡単な調整及びポインタの使用によって直裁的に遂行される。
【００２８】
更なる実施例は、保留のＩ／Ｏリクエストのリンク・リストを含む次のエントリに先頭ポインタ１８をインクリメントするという図３の動作ステップ１０６及び１０８の効率を高めるためにビット・マップを利用する。これらの実施例では、キュー８における各エントリに対する値を含んだビット・マップが維持される。まず、ビット・マップ・エントリが「オフ」、即ち、バイナリ０にセットされる。エントリによって指し示されたリンク・リストにおいてＩ／Ｏリクエストがエンキューされる度に、そのエントリに対する対応するビット・マップが「オン」、即ち、バイナリ１にされ、それによって、そのエントリに対する保留のＩ／Ｏリクエストが存在することを表す。サーバ４が、処理すべきＩ／Ｏリクエストのリンク・リストを含む次のエントリまで移動する必要がある時、サーバ４は、まず、先頭ポインタによって指し示されたビット・マップ・エントリに続く最初の「オン」の値を決定するためにそのビット・マップを処理するであろう。
【００２９】
そこで、サーバ４は、その分野では知られているビット・マップ・エンコーディング技法を使用して、その位置指定されたエントリに対するこの「オン」のビット・マップ値をエントリのバイナリ数に変換するであろう。この方法では、保留のＩ／Ｏリクエストのリンク・リストを指し示す処理すべきエントリを決定する時、サーバ４は、保留のＩ／Ｏリクエストを持った次のエントリを直接に決定するためにビット・マップを処理するであろう。この方法では、サーバ４は、保留のリクエストを有する１つのエントリを最終的に見つけるために各エントリをチェックする必要がない。
【００３０】
望ましい実施例は、標準的なプログラミング及び／又はエンジニアリング技法を使用してソフトウエア、ファームウエア、ハードウエア、又はそれらの任意の組み合わせを作るための方法、装置、又は製造物（article of manufacture）してインプリメント可能である。本願において使用される用語「製造物」（又は、「コンピュータ・プログラム製品」）は、１つ又は複数のコンピュータ読み取り可能な装置からアクセスし得る１つ又は複数のコンピュータ・プログラム及び／又はデータ・ファイル、キャリア、又は、磁気記憶媒体、フロッピ・ディスク、ＣＤ−ＲＯＭ、光ディスク、ホログラム装置、揮発性又は不揮発性電子メモリ等のような媒体を含むことを意図するものである。更に、製造物は、ネットワーク通信線、無線通信媒体、空中を伝播する信号、高周波、赤外線信号等のような通信媒体における望ましい実施例のインプリメンテーションを含み得る。勿論、本発明の技術的範囲から逸脱することなく、この構成に対して多くの修正を施し得ることも当業者には明らかであろう。
【００３１】
サーバ４によって遂行されるオペレーションに関連して望ましい実施例を説明した。サーバは、その分野で知られている任意のタイプの処理ユニットを含み得る。
【００３２】
望ましい実施例では、サーバ４はＩ／Ｏリクエストを記憶システム１２にディスパッチする。記憶システム１２が１つ又は複数のディスク・ドライブから成る場合、サーバ４はそのディスク・ドライブに対するＩ／Ｏリクエストを遂行するであろう。記憶システム１２が記憶装置コントローラを含む場合、サーバ４はリクエストを記憶装置コントローラに送るか、又はＩ／Ｏリクエストのターゲットであるデータ・ボリュームを含む制御装置に送るであろう。
【００３３】
望ましい実施例では、クライアント２ａ、２ｂ、２ｃがＩ／Ｏリクエストと共に優先順位を伝達する。しかし、更なる実施例では、クライアント２ａ、２ｂ、２ｃが優先順位を供給しない場合、サーバ４はデフォルト優先順位をＩ／Ｏリクエストに割り当ててもよい。
【００３４】
記憶システム１２に対するＩ／Ｏリクエストをエンキュー及びデキューすることに関連して望ましい実施例を説明した。しかし、別の実施例では、優先順位に従って処理される必要のある任意のタイプの作業又はリクエストをキューするために、望ましい実施例のキューが使用されてもよい。望ましい実施例は、Ｉ／Ｏリクエスト以外の作業をキューすることを伴うものでもよい。
【００３５】
望ましい実施例は、先頭ポインタによって指し示されたエントリの優先順位によって、新しいリクエストの優先順位を低くするためのアルゴリズムを説明した。別の実施例では、新しいＩ／Ｏリクエストの優先順位は、サーバが現在処理しようとしているエントリとは異なるエントリにその新しいリクエストを入れるという態様の別の方法でインクリメントされてもよい。
【００３６】
望ましい実施例では、最後のエントリが第１エントリを指し示す循環式キューとしてキューを説明した。別の実施例では、キューは循環式ではないリンク・リストから成るものでもよい。
【００３７】
要約すると、望ましい実施例は、リクエストをキューするための方法、システム、プログラム、及びデータ構造を開示する。各リクエストは複数の優先順位レベルの１つと関連づけられる。複数のエントリを含むキューが生成される。各エントリは優先順位レベルに対応し、複数のリクエストが１つのエントリにおいてキューされてもよい。関連の優先順位を持った新しいリクエストがそのキューにおいてエンキューするために受け取られる時、ポインタによって指し示されたエントリの決定が行われる。新しいリクエストに関連した優先順位は、ポインタによって指し示されたエントリとは異なるエントリと関連するような値によって調整される。新しいリクエストは、調整された優先順位と関連した１つのエントリにおいてキューされる。
【００３８】
本発明の望ましい実施例に関する上記の説明は、図示及び記述することを目的として与えられた。それは、網羅的であること及び開示された正確な形に本発明を限定することを意図するものではない。上記の教示するところに従って、多くの修正及び変更が可能である。本発明の技術的範囲がこの詳細な説明によって限定されるものではなく、むしろ特許請求の範囲によって限定されるものであることが意図される。上記の詳述、実施例、及びデータは本発明の構成の製造及び使用に関する十分な説明を提供する。本発明の精神及び技術的範囲を逸脱することなく、本発明の多くの実施例を作ることが可能であるので、本発明は特許請求の範囲における記載に存在する。
【００３９】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４０】
（１）実行すべきリクエストをキューするための方法であって、各リクエストが複数の優先順位レベルの１つと関連づけられている場合の方法にして、
複数のエントリを含むキューを生成するステップであって、各エントリが優先順位レベルに対応しており且つ複数のリクエストが１つのエントリにおいてキューされ得る、ステップと、
関連する優先順位を持った新しいリクエストを受け取り、前記キューにおいてエンキューするステップと、
ポインタによって指し示されたエントリを決定するステップと、
前記新しいリクエストと関連する優先順位を或る値だけ調整するステップであって、調整された優先順位が前記ポインタによって指し示されたエントリとは異なるエントリと関連づけられる、ステップと、
前記調整された優先順位と関連する１つのエントリにおいて前記新しいリクエストをキューするステップと、
を含む方法。
（２）リクエストがキューされるエントリを決定するステップと、
前記決定されたエントリを指し示すように前記ポインタを修正するステップと、
前記ポインタによって指し示されたエントリにおいてキューされたリクエストを処理するステップと、
を更に含む上記（１）に記載の方法。
（３）前記リクエストがキューされるエントリを決定するステップは、
キューされたリクエストを有するエントリを表すデータ構造を生成するステップと、
キューされたリクエストを有し、前記ポインタによって指し示されたエントリに続く最初のエントリを決定するために前記データ構造を処理するステップと、
を含む上記（２）に記載の方法。
（４）前記キューされたリクエストは記憶システムに関する入出力（Ｉ／Ｏ）リクエストを含み、
前記リクエストを処理するステップはリクエストされたＩ／Ｏオペレーションを実行するために前記Ｉ／Ｏリクエストをディスパッチするステップを含む、
上記（２）に記載の方法。
（５）各エントリはリンク・リストを指し示すことができ、
前記エントリにおいて新しいリクエストをキューするステップは前記リクエストに割り当てられた優先順位と関連するエントリによって指し示されたリンク・リストに前記新しいリクエストを加えるステップを含む、
上記（１）に記載の方法。
（６）前記優先順位を調整するステップは、
前記ポインタによって指し示されたエントリの優先順位を決定するステップと、
前記調整された優先順位を決定するために前記決定された優先順位を前記リクエストの優先順位に加えるステップと、
を含む上記（１）に記載の方法。
（７）前記キューの最後のエントリは前記キューの第１エントリを指し示し、
前記優先順位を調整するステップは、前記調整された優先順位が前記キューにおけるエントリの数よりも大きい場合、前記調整された優先順位を「前記調整された優先順位モジュロ前記キューにおけるエントリの数」に設定するステップを更に含む、
上記（６）に記載の方法。
（８）前記キューは前記システムにおける各優先順位に対して１つのエントリの他に１つのエクストラ・エントリを含む上記（１）に記載の方法。
（９）前記新しいリクエストは、前記ポインタによって指し示されたエントリではない前記調整された優先順位に対応するエントリにおいてキューされる上記（８）に記載の方法。
（１０）実行すべきリクエストをキューするためのシステムであって、各リクエストが複数の優先順位レベルの１つと関連づけられているシステムにして、
複数のエントリを含むキューを生成するための手段であって、各エントリが優先順位レベルに対応しており且つ複数のリクエストが１つのエントリにおいてキューされ得る、手段と、
関連する優先順位を持った新しいリクエストを受け取り、前記キューにおいてエンキューするための手段と、
ポインタによって指し示されたエントリを決定するための手段と、
前記新しいリクエストと関連する優先順位を或る値だけ調整するための手段であって、調整された優先順位が前記ポインタによって指し示されたエントリとは異なるエントリと関連づけられる、手段と、
前記調整された優先順位と関連する１つのエントリにおいて前記新しいリクエストをキューするための手段と、
を含むシステム。
（１１）リクエストがキューされるエントリを決定するための手段と、
前記決定されたエントリを指し示すように前記ポインタを修正するための手段と、
前記ポインタによって指し示されたエントリにおいてキューされたリクエストを処理するための手段と、
を更に含む上記（１０）に記載のシステム。
（１２）前記リクエストがキューされるエントリを決定するための手段は、
キューされたリクエストを有するエントリを表すデータ構造を生成するための手段と、
キューされたリクエストを有し、前記ポインタによって指し示されたエントリに続く最初のエントリを決定するために前記データ構造を処理するための手段と、
を含む上記（１１）に記載のシステム。
（１３）前記キューされたリクエストは記憶システムに関する入出力（Ｉ／Ｏ）リクエストを含み、
前記リクエストを処理するための手段はリクエストされたＩ／Ｏオペレーションを実行するために前記Ｉ／Ｏリクエストをディスパッチするための手段を含む、
上記（１１）に記載のシステム。
（１４）各エントリはリンク・リストを指し示すことができ、
前記エントリにおいて新しいリクエストをキューするための手段は前記リクエストに割り当てられた優先順位と関連するエントリによって指し示されたリンク・リストに前記新しいリクエストを加えるための手段を含む、
上記（１０）に記載のシステム。
（１５）前記優先順位を調整するための手段は、
前記ポインタによって指し示されたエントリの優先順位を決定するための手段と、
前記調整された優先順位を決定するために前記決定された優先順位を前記リクエストの優先順位に加えるための手段と、
を含む上記（１０）に記載のシステム。
（１６）前記キューの最後のエントリは前記キューの第１エントリを指し示し、
前記優先順位を調整するための手段は、前記調整された優先順位が前記キューにおけるエントリの数よりも大きい場合、前記調整された優先順位を「前記調整された優先順位モジュロ前記キューにおけるエントリの数」に設定するための手段を更に含む、
上記（１５）に記載のシステム。
（１７）前記キューは前記システムにおける各優先順位に対して１つのエントリの他に１つのエクストラ・エントリを含む上記（１０）に記載のシステム。
（１８）前記新しいリクエストは、前記ポインタによって指し示されたエントリではない前記調整された優先順位に対応するエントリにおいてキューされる上記（１７）に記載のシステム。
（１９）各リクエストが複数の優先順位レベルの１つと関連づけられているシステムにおいて、実行すべきリクエストをキューするために処理ユニットをプログラムする時に使用するための製造物であって、前記処理ユニットに下記の動作ステップを実行させる少なくとも１つの組み込まれたコンピュータ・プログラムを含むコンピュータ読み取り可能な記憶媒体を含む製造物：
複数のエントリを含むキューを生成する動作ステップであって、各エントリが優先順位レベルに対応し、複数のリクエストが１つのエントリにおいてキューされ得る、動作ステップと、
関連する優先順位を持った新しいリクエストを受け取り、前記キューにおいてエンキューする動作ステップと、
ポインタによって指し示されたエントリを決定する動作ステップと、
前記新しいリクエストと関連する優先順位を或る値だけ調整する動作ステップであって、調整された優先順位は前記ポインタによって指し示されたエントリとは異なるエントリと関連づけられる、動作ステップと、
前記調整された優先順位と関連する１つのエントリにおいて前記新しいリクエストをキューする動作ステップ。
（２０）リクエストがキューされるエントリを決定する動作ステップと、
決定されたエントリを指し示すように前記ポインタを修正する動作ステップと、
前記ポインタによって指し示されたエントリにおいてキューされたリクエストを処理する動作ステップと、
を更に含む上記（１９）記載の製造物。
（２１）前記リクエストがキューされるエントリを決定する動作ステップは、
キューされたリクエストを有するエントリを表すデータ構造を生成する動作ステップと、
キューされたリクエストを有し、前記ポインタによって指し示されたエントリに続く最初のエントリを決定するために前記データ構造を処理する動作ステップと、
を含む上記（２０）に記載の製造物。
（２２）前記キューされたリクエストは記憶システムに関する入出力（Ｉ／Ｏ）リクエストを含み、
前記リクエストを処理する動作ステップはリクエストされたＩ／Ｏオペレーションを実行するために前記Ｉ／Ｏリクエストをディスパッチする動作ステップを含む、
上記（２０）に記載の製造物。
（２３）各エントリはリンク・リストを指し示すことができ、
前記エントリにおいて新しいリクエストをキューする動作ステップは前記リクエストに割り当てられた優先順位と関連するエントリによって指し示されたリンク・リストに前記新しいリクエストを加える動作ステップを含む、
上記（１９）に記載の製造物。
（２４）前記優先順位を調整する動作ステップは、
前記ポインタによって指し示されたエントリの優先順位を決定する動作ステップと、
前記調整された優先順位を決定するために前記決定された優先順位を前記リクエストの優先順位に加える動作ステップと、
を含む上記（１９）記載の製造物。
（２５）前記キューの最後のエントリは前記キューの第１エントリを指し示し、
前記優先順位を調整する動作ステップは、前記調整された優先順位が前記キューにおけるエントリの数よりも大きい場合、前記調整された優先順位を「前記調整された優先順位モジュロ前記キューにおけるエントリの数」に設定する動作ステップを更に含む、
上記（２４）に記載の製造物。
（２６）前記キューは前記システムにおける各優先順位に対して１つのエントリの他に１つのエクストラ・エントリを含む上記（１９）に記載の製造物。
（２７）前記新しいリクエストは、前記ポインタによって指し示されたエントリではない前記調整された優先順位に対応するエントリにおいてキューされる上記（２６）に記載の製造物。
（２８）処理装置にアクセスし得るメモリ装置にして、
複数のエントリを含むキューであって、各優先順位レベルに対するエントリ及び少なくとも１つの更なるエントリが存在し、複数のリクエストが任意のエントリにおいてキューされ得る、キューと、
前記キューにおける１つのエントリをアドレスするポインタであって、調整された優先順位が前記ポインタによって指し示されたエントリとは異なるエントリと関連づけられるように或る値だけ新しいリクエストと関連する優先順位が調整される、ポインタと、
を含むデータ構造を含むメモリ装置。
（２９）キューされたリクエストを有するエントリを表すデータ構造を更に含み、
処理すべきキューされたリクエストを有し、前記ポインタによって指し示されたエントリに続く最初のエントリを決定するように前記データ構造が処理される、
上記（２８）に記載のメモリ装置。
（３０）少なくとも１つのリンク・リストを更に含み、
各エントリは１つのリンク・リストを指し示すことができ、
エントリにおいて１つの新しいリクエストをキューすることは、前記新しいリクエストに割り当てられた優先順位と関連するエントリによって指し示されたリンク・リストに前記新しいリクエストを加えることを含む、
上記（２８）に記載のメモリ装置。
（３１）前記キューの最後のエントリは前記キューの第１エントリを指し示し、
前記優先順位を調整することは、前記調整された優先順位が前記キューにおけるエントリの数よりも大きい場合、前記調整された優先順位を「前記調整された優先順位モジュロ前記キューにおけるエントリの数」に設定することを含む、
上記（２８）に記載のメモリ装置。
【図面の簡単な説明】
【図１】望ましい実施例がインプリメントされるコンピューティング環境を示すブロック図である。
【図２】本発明の望ましい実施例に従って、優先順位によりＩ／Ｏリクエストキューするためのキュー・データ構造を示す。
【図３】本発明の望ましい実施例に従って、図２に示されたキューにおけるＩ／Ｏリクエストをデキュー及び処理するためのロジックを示す。
【図４】本発明の望ましい実施例に従って、図２に示されたキューにおけるＩ／Ｏリクエストをエンキューするためのロジックを示す。
【図５】本発明の望ましい実施例に従って、図２に示されたキューからエントリをエンキュー及びデキューする方法の例を示す。
【図６】本発明の望ましい実施例に従って、図２に示されたキューからエントリをエンキュー及びデキューする方法の例を示す。
【符号の説明】
８  キュー・データ構造
２０  ポインタ
２２  リンク・リスト
２４  ポインタ
２６  リンク・リスト
【図１】
0004028686.tif 000002
【図２】
0004028686.tif 000003
【図３】
0004028686.tif 000004
【図４】
0004028686.tif 000005
【図５】
0004028686.tif 000006
【図６】
0004028686.tif 000007