(57)【特許請求の範囲】
【請求項１】
プロセッサと記憶装置と要求をサービスするための複数の待ち行列とを含むデータ処理システムにおいて、待ち行列の優先順位を動的に調節する方法であって、
各待ち行列の最大カウントを定義するステップと、
要求が待ち行列に追加される時に、前記待ち行列にある要求の数が前記待ち行列の最大カウントより大きいかどうかを計算するステップと、
前記待ち行列にある要求の数が前記待ち行列の最大カウントより大きい場合に、最高優先順位ではない、より高い優先順位に前記待ち行列の優先順位を高めるステップと、
該高められた優先順位を有する他の待ち行列からの要求をサービスする前に前記最高優先順位の待ち行列中の、最大カウントよりも少ない所定の数の要求をサービスするステップと
を含む、前記方法。
【請求項２】
前記待ち行列が、プロセッサに記憶されることを特徴とする、請求項１に記載の方法。
【請求項３】
前記待ち行列が、記憶装置に記憶されることを特徴とする、請求項１に記載の方法。
【請求項４】
データ処理システムであって、
ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記ホストから受け取る要求をサービスするための、前記記憶装置コントローラ内で維持される複数の待ち行列と、
前記待ち行列にある要求の数が前記待ち行列の最大カウントより大きい場合に、最高優先順位ではない、より高い優先順位に前記待ち行列の優先順位を高めるためのプロセッサと、
を含み、
前記プロセッサは、該高められた優先順位を有する他の待ち行列からの要求をサービスする前に前記最高優先順位の待ち行列中の、最大カウントよりも少ない所定の数の要求をサービスする、前記データ処理システム。
【請求項５】
データ処理システムであって、
ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記記憶装置コントローラから受け取る要求をサービスするための、前記複数の記憶装置内で維持される複数の待ち行列と、
前記待ち行列にある要求の数が前記待ち行列の最大カウントより大きい場合に、最高優先順位ではない、より高い優先順位に前記待ち行列の優先順位を高めるためのプロセッサと
を含み、
前記プロセッサは、該高められた優先順位を有する他の待ち行列からの要求をサービスする前に前記最高優先順位の待ち行列中の、最大カウントよりも少ない所定の数の要求をサービスする、前記データ処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、要求を管理するために複数の待ち行列を有するデータ処理システムに関する。具体的に言うと、本発明は、記憶サブシステムを有するデータ処理システムで待ち行列優先順位づけを動的に管理するための方法およびシステムに関する。
【０００２】
【従来の技術】
ホスト・システム（ＣＰＵ）および記憶サブシステムを有し、記憶サブシステムに複数の記憶装置（装置）と記憶装置コントローラが含まれるデータ処理システム１００には、所与の記憶装置へのアクセスを求める未処理の要求のすべての現在の状況をリストするための非常に重要なリストがある（図１）。このリストを、通常はジョブ待ち行列、タスク待ち行列、レディ・リスト、作業リストまたは単に待ち行列と称する。各待ち行列の要求（「ジョブ」とも称する）は、通常は先入れ先出し（ＦＩＦＯ）方式でサービスされる。さらに、記憶装置へのアクセスを求める要求に異なる優先順位を与えるために、通常は、異なる優先順位を有する複数の待ち行列が、装置ごとに記憶サブシステム側で維持される。たとえば、ある記憶装置へのアクセス要求を処理するために、記憶サブシステムが、装置ごとに４つの待ち行列を維持し、設計上、Ｑ0は最低の優先順位の待ち行列、Ｑ1は低い優先順位の待ち行列、Ｑ2は中間の優先順位の待ち行列、Ｑ3は最高の優先順位の待ち行列である場合がある。この４つの待ち行列は、記憶装置コントローラまたは各装置のいずれかで維持することができる。
【０００３】
一般に、記憶装置コントローラは、要求を処理するために待ち行列をポーリングする。Ｑ3に保留中の要求がある場合、この待ち行列は最高の優先順位を有する待ち行列なので、コントローラは、Ｑ3からの次の要求を処理する。Ｑ3に保留中の要求がない場合、Ｑ2が次に高い優先順位の待ち行列なので、記憶装置コントローラは、Ｑ2からの次の要求を処理する。しかし、Ｑ2からの要求を完了する前にＱ3が装置へのアクセス要求を受け取る場合、通常はＱ2からの要求の処理が中断され、未完了の要求がＱ2に戻され、Ｑ3からの要求が処理される。
【０００４】
同様の形で、Ｑ3とＱ2に保留中の要求がない場合には、Ｑ1が次に高い優先順位の待ち行列なので、記憶装置コントローラは、Ｑ1からの次の要求を処理する。しかし、Ｑ1からの要求を完了する前にＱ3またはＱ2が装置へのアクセス要求を受け取る場合には、通常はＱ1からの要求の処理が中断され、未完了の要求がＱ1に戻され、Ｑ3またはＱ2からの要求が処理される。
【０００５】
この方法を使うと、高い優先順位を有する要求は非常にすばやく処理されるが、優先順位の高い待ち行列からの要求が優先順位の低い待ち行列からの要求の処理に継続的に割り込んでくるので、優先順位の低い待ち行列からの要求が長時間にわたって「スタックする」（凍り付く）可能性がある。優先順位の低い待ち行列からの要求の処理への割込みが続くと、システム資源の実質的な浪費がもたらされる。
【０００６】
一般に、この深刻な問題を処理するために、データ処理システムは、スタックした要求を検出し、それらが処理されるように優先順位の低い待ち行列から優先順位の高い待ち行列へ移動するための手段を有する必要がある。この手法は、現時点でスタックした要求を処理するための一般的な方法であるが、スタックした要求を検出し、それを実行するために優先順位の低い待ち行列から優先順位の高い待ち行列へ移動するために、複雑なコントローラ設計、待ち行列実施態様およびシステム・コーディングを必要とする。したがって、複数の待ち行列を有する任意のデータ処理システムでスタックした要求を管理し、要求割込みの数を最少にすることが、非常に重要である。
【０００７】
したがって、スタックした要求を処理するために優先順位の低い待ち行列から優先順位の高い待ち行列へ移動する処理で貴重なシステム資源を枯渇させることなく、スタックした要求をできる限り効率的に処理できる発明が求められている。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、複数の優先順位の待ち行列を有するデータ処理システムでの待ち行列管理を改良することである。
【０００９】
本発明のもう１つの目的は、スタックした要求の検出と処理でのシステム資源の枯渇を最少にすることである。
【００１０】
本発明のもう１つの目的は、複数の優先順位の待ち行列を有するデータ処理システムで、要求割込みの数を最少にすることである
【００１１】
本発明のもう１つの目的は、記憶サブシステムの記憶装置コントローラで複数の待ち行列が維持されるデータ処理システムでの待ち行列管理を改良することである。
【００１２】
本発明のもう１つの目的は、記憶サブシステムの各記憶装置で複数の待ち行列が維持されるデータ処理システムでの待ち行列管理を改良することである。
【００１３】
本発明のもう１つの目的は、優先順位の低い待ち行列から優先順位の高い待ち行列へ要求を移動せずに、スタックした要求を処理することである。
【００１４】
【課題を解決するための手段】
この目標のため、本発明に従い、複数の待ち行列を有するデータ処理システムにおいて、待ち行列の優先順位がもはや固定ではなく、システム走行中に動的に変更できる、待ち行列を管理するための方法および手段を開示する。待ち行列優先順位の動的調節によって、常に割り込まれている要求を含む、優先順位の低い待ち行列の優先順位を高めることができ、したがって、これらのスタックした要求を、優先順位の低い待ち行列から優先順位の高い待ち行列へ実際に移動する必要なしに、すばやく処理することができる。
【００１５】
記憶サブシステムに記憶装置コントローラと複数の記憶装置が含まれる本発明の１実施例では、記憶装置コントローラで、記憶装置ごとに待ち行列が維持され、待ち行列の優先順位が動的に管理される。さらに、各待ち行列の現行優先順位、待ち行列サービスの現行優先順位レベル、各待ち行列内のジョブ（要求）の数、現在要求をサービスされている待ち行列など、待ち行列に関連する情報も、記憶装置コントローラで維持される。
【００１６】
待ち行列に関連する情報は、待ち行列優先順位およびサービス・テーブル（ＱＰＳテーブル）および装置コントローラ状況テーブル（ＤＣＳテーブル）と称する１組のテーブルの形で維持できる。これらのテーブルは、通常は、高速アクセスのため、記憶装置コントローラ・プロセッサによってアクセス可能な高速半導体記憶媒体に格納される。記憶装置コントローラは、とりわけ、現時点でサービスされている待ち行列がどれであるかと、次にサービスしなければならない待ち行列がどれであるかを決定する際にこれら２つのテーブルを利用する。省略時ＱＰＳテーブルは、ホスト・システムによって提供される。
【００１７】
通常動作中に、所与の待ち行列Ｑi内の要求の数（保留中の要求の数とも称する）が、その待ち行列に関して確立された所定の最大要求カウント（上閾値または単に「最大カウント」と称する）を超える場合には、ホスト・システムが、Ｑiの優先順位を高めた更新されたＱＰＳテーブルを記憶装置コントローラに供給し、したがって、Ｑi内の要求がすばやく処理されるようにする。Ｑi内の要求の数が所定の最少要求カウント（下閾値または単に「最少カウント」と称する）未満になったならば、ホスト・プロセッサは、通常はＱiの優先順位が元の省略時値に戻されている新しいＱＰＳテーブルを記憶装置コントローラに供給する。
【００１８】
同様に、通常動作中に、複数の待ち行列Ｑi、ＱjおよびＱkの要求の数がそれぞれの所定の閾値を超える場合には、ホスト・プロセッサは、これらの待ち行列のすべての優先順位が高められ、したがってこれらの待ち行列の要求がより速く実行されるようになる更新されたＱＰＳテーブルを記憶装置コントローラに供給する。
【００１９】
やはり、Ｑi、ＱjおよびＱkの要求の数が、各待ち行列に関して確立されたそれぞれの所定の最少要求カウント未満になると、ホスト・プロセッサは、これらの待ち行列のすべての優先順位が通常はその初期値にセットされている新しいＱＰＳテーブルを記憶装置コントローラに供給する。
【００２０】
記憶サブシステムに記憶装置コントローラと複数の記憶装置が含まれ、記憶装置のそれぞれがそれ自体のプロセッサとメモリを有する場合の本発明のもう１つの実施例では、各装置自体がその装置の待ち行列を維持し、待ち行列の優先順位を動的に管理する。さらに、各待ち行列の現行優先順位、待ち行列サービスの現行優先順位レベル、各待ち行列内のジョブ（要求）の数、要求が現在サービスされている待ち行列などの待ち行列に関連する情報も、装置側で維持される。この情報は、待ち行列優先順位およびサービス・テーブル（ＱＰＳテーブル）および装置コントローラ状況テーブル（ＤＣＳテーブル）の形で維持できる。省略時ＱＰＳテーブルは、当初は記憶装置コントローラによって各記憶装置に供給される。その後、各記憶装置は、ホスト・システムによって発行され記憶装置コントローラによってその記憶装置に向けられた要求の管理に、それ自体の待ち行列の組を利用する。
【００２１】
やはり、所与の記憶装置ＳＤnの所与の待ち行列Ｑiの要求の数が所定の閾値を超える場合には、記憶装置コントローラが、Ｑiの優先順位を高めた更新されたＱＰＳnテーブルをＳＤnに供給し、したがって、Ｑiの要求のより速い実行を可能にする。Ｑiの要求の数が所定のカウント未満になったならば、記憶装置コントローラが、ＳＤnのＱiの優先順位を元の値に戻した新しいＱＰＳnテーブルを供給する。
【００２２】
【発明の実施の形態】
本明細書では、すべての図面を通じて同様の符号によって同様の要素を参照する。以下の説明は、本発明を実施するために現在最適と考えられる態様である。この説明および複数の代替実施例は、本発明の一般原理を説明する目的のために示されるものであり、請求の範囲で請求される発明的概念を制約する目的のものではない。
【００２３】
図２を参照すると、本発明の好ましい実施例によるデータ処理システムの概略図が示されている。データ処理システム２００には、送出側であるホスト・システム２０２が含まれ、ホスト・システム２０２は、通信チャネル２５４および２５６を介して記憶サブシステム２１０と通信する。ホスト・システム２０２には、さらに、リンク２５０を介してメモリ・ユニット２０８と通信し、リンク２５２を介してホスト・アダプタ２０６と通信するホスト・プロセッサ２０４が含まれる。メモリ・ユニット２０８には、通常は、とりわけ各待ち行列の未処理の要求の数の最大要求値および最少要求値を記憶する、ＤＲＡＭなどの高速メモリが含まれる。ホスト・アダプタ２０６は、ホスト・プロセッサ２０４と記憶サブシステム２１０の間のチャネル・インターフェースを提供する。
【００２４】
記憶サブシステム２１０には、受取側である記憶装置コントローラ２１１が含まれ、記憶装置コントローラ２１１は、通信チャネル２６６を介して複数の記憶装置２１２と通信する。本発明の好ましい実施例では、記憶装置は、直接アクセス記憶装置（ＤＡＳＤ）として既知のタイプの磁気装置である。記憶装置コントローラ２１１には、ホスト・システム２０２と通信するための受信器２１３および送信器２１４が含まれる。受信器２１３は、通信リンク２５４を介してホスト・システム２０２が発行するデータと命令（コマンド、要求）を受け取り、送信器２１４は、通信リンク２５６を介してホスト・システム２０２へデータと割込みを通信する。記憶装置コントローラ２１１には、さらに、ホストから受け取ったデータまたはホストへ送ろうとするデータを格納するための緩衝記憶が含まれる。緩衝記憶２１６は、通信リンク２５８を介して受信器２１３と、通信リンク２６０を介して送信器２１４と、通信リンク２６２を介して記憶装置コントローラ・プロセッサ２２０と、通信リンク２６６を介して記憶装置２１２と通信する。記憶装置コントローラ２１１には、記憶装置コントローラ・プロセッサ２２０も含まれ、記憶装置コントローラ・プロセッサ２２０は、記憶装置２１２とホスト・システム２０２の間のデータ通信処理を制御する。また、記憶装置コントローラ・プロセッサ２２０は、各記憶装置２３０の待ち行列と待ち行列サービスを管理する。記憶装置コントローラ２１１には、さらに、メモリ・ユニット２２２が含まれ、メモリ・ユニット２２２は、本発明の好ましい実施例では高速半導体メモリである。メモリ・ユニット２２２には、各記憶装置に関連する待ち行列が記憶され、さらに、ＱＰＳテーブルやＤＣＳテーブルなど、これらの待ち行列の管理に関連する他の情報も記憶される。
【００２５】
たとえば、メモリ・ユニット２２２には、記憶装置２３０（ＤＡＳＤ１）へのアクセス要求を管理するための待ち行列管理情報２２４と、記憶装置２３４（ＤＡＳＤｎ）へのアクセス要求を管理するための待ち行列管理情報２２８が含まれる。待ち行列管理情報２２４には、待ち行列２３６、２３７、２３８および２３９と、待ち行列優先順位およびサービス・テーブル（ＱＰＳテーブル）２４３と、装置コントローラ状況テーブル（ＤＣＳテーブル）２４４が含まれる。ＱＰＳテーブル２４３には、待ち行列の優先順位や、ＱＰＳテーブル２４３の項目に従って待ち行列２３６、２３７、２３８および２３９からの情報をどのようにサービスすべきか、などの情報が含まれる。ＤＣＳテーブル２４４には、各待ち行列の優先順位レベル、待ち行列２３６、２３７、２３８および２３９がサービスされている現行優先順位レベル（「待ち行列サービスの現行優先順位レベル」とも称する）、待ち行列のそれぞれで現在保留されている要求の数などの情報が含まれる。待ち行列管理情報２２４には、同一の優先順位を有する待ち行列からの要求のすべてがサービスされたかどうかを記録する待ち行列のジョブ完了カウンタ（ＱＪＣＣ）２４２も含まれる。したがって、待ち行列のジョブ完了カウンタ２４２の内容が、同一の優先順位を有する待ち行列の数と等しい場合には、同一の優先順位を有する待ち行列からの要求のすべてがサービスされていることになる。待ち行列管理情報２２４には、現行行（ＣＲ）レジスタ２４０および現行列（ＣＣ）レジスタ２４１も含まれ、これらのレジスタの内容によって、現在サービスされている待ち行列を含むＱＰＳテーブル２４３の項目が識別される。
【００２６】
図３は、ホスト・システム２０２によって記憶装置コントローラ２１１に送られる省略時の待ち行列優先順位およびサービス（ＱＰＳ）・テーブル３００を示す図である。ＱＰＳテーブル３００は、複数の行と列に分割されている。列の数は、データ処理システム２００で使用可能な待ち行列優先順位の数によって指示される。本発明の好ましい実施例では、ＱＰＳテーブル３００に、４つの列Ｃ３、Ｃ２、Ｃ１およびＣ０が含まれる。列３（Ｃ３）には、最高優先順位の列としてラベルが付けられ、したがって、Ｃ３内の待ち行列は、サービスに関して最高の優先順位を有する。列２（Ｃ２）には、中間の優先順位の列としてラベルが付けられ、したがって、Ｃ２内の待ち行列は、サービスに関して中間の優先順位を有する。列１（Ｃ１）には、低い優先順位の列としてラベルが付けられる。列０（Ｃ０）には、最低の優先順位の列としてラベルが付けられ、したがって、Ｃ０内の待ち行列は、サービスに関して最低の優先順位を有する。
【００２７】
ＱＰＳテーブル３００には、さらに、複数の行Ｒ０（行０）ないしＲｎ（行ｎ）が含まれ、行の数は、少なくとも列数＋１に等しい。ＱＰＳテーブル３００には、複数の項目も含まれ、このテーブル内の各項目は、その項目が格納される行と列への参照を含む表記によって識別される。たとえば、項目３３０は、表記Ｒ１Ｃ３によって識別され、この表記は、項目３３０が行１と列３の交点にあることを意味する。項目３４０は、Ｒ１Ｃ２によって識別され、これは、項目３４０が行１と列２の交点にあることを意味する。ＱＰＳテーブル３００内の各項目は、行０（Ｒ０）の項目を除いて、２つのサブフィールドすなわち、「待ち行列番号」と記された左のサブフィールドと「次行番号」と記された右のサブフィールドを有する。各項目の待ち行列番号は、その項目が選択された場合にサービスされる待ち行列を識別する。次行番号は、現行優先順位（現行列）の下で次にサービスされる項目を識別する。ＱＰＳテーブル３００のＲ０は、その項目に右のサブフィールド「次行番号」だけが含まれる特別な行である。行０の次行番号は、その列の項目がサービスに関して選択された場合に列内のどの項目を最初にサービスするのかを判定するのに記憶装置コントローラ２１１が使用する。
【００２８】
たとえば、Ｒ１Ｃ３にある項目には、待ち行列番号Ｑ3と次行番号１が含まれ、これは、Ｒ１Ｃ３の項目が選択された場合に即座にサービスされる待ち行列がＱ3であることを意味する。行１は、現行項目がもう一度サービスされる、すなわち、他の待ち行列からの要求を実行する前に、Ｑ3からの要求のすべての実行を継続することを意味する。Ｑ3内のジョブのすべてが実行されたならば、中間優先順位の待ち行列にあるジョブが処理される。したがって、ＱＰＳテーブル３００を使用して、記憶装置コントローラ・プロセッサ２２０は、どの待ち行列が中間の優先順位を有するかを判定する。記憶装置コントローラ・プロセッサ２２０は、Ｒ０Ｃ２の次行番号を読み取ることによって、列２のどの項目を最初にサービスするのかも判定する。ＱＰＳテーブル３００では、Ｒ０Ｃ２の次行番号が１であり、これは、列２（現行優先順位）の下で最初にサービスされる項目が、Ｒ１Ｃ２（行１、列２）の項目であることを意味する。したがって、記憶装置コントローラ・プロセッサ２２０は、次に、Ｒ１Ｃ２のサブフィールド（待ち行列番号と次行番号）を調べ、これによって、即座にサービスされる待ち行列としてＱ2が識別され、次にサービスされる項目としてＲ１Ｃ２が識別されるが、これは、他の待ち行列をサービスする前にＱ2からのすべての要求を実行しなければならないことを意味する。同様に、中間の優先順位を有する待ち行列のすべてがサービスされたならば、記憶装置コントローラ・プロセッサ２２０は、列１（低い優先順位）の待ち行列に要求があればそのサービスを開始し、その後、列０（最低の優先順位）の待ち行列に要求があれば、そのサービスを行う。
【００２９】
省略時のＱＰＳテーブル３００では、Ｒ１Ｃ０に示されるＱ0が、最低の優先順位（優先順位０）を有する。Ｒ１Ｃ１に示されるＱ1は、低い優先順位（優先順位１）を有し、Ｒ１Ｃ２に示されるＱ2は、中間の優先順位（優先順位２）を有し、Ｒ１Ｃ３に示されるＱ3は、最高の優先順位（優先順位３）を有する。
【００３０】
図４を参照すると、記憶装置コントローラ２１１がホスト・システム２０２から省略時のＱＰＳテーブル３００を受け取った後に記憶装置コントローラ・プロセッサ２２０によって作成される装置コントローラ状況（ＤＣＳ）テーブル３５０が示されている。ＤＣＳテーブル３５０には、省略時のＱＰＳテーブル３００を調べることによって決定されるＱ0、Ｑ1、Ｑ2およびＱ3に関する優先順位レベル情報が含まれる。各待ち行列の優先順位レベル情報は、優先順位レベルの列３５４に格納される。ＤＣＳテーブル３５０には、さらに、各待ち行列で現在保留されている要求の数も含まれ、これは、列３５２に格納される。ＤＣＳテーブル３５０には、記憶装置コントローラが待ち行列をサービスしている待ち行列サービスの現行優先順位レベルも含まれる。省略時のＤＣＳテーブル３５０では、待ち行列サービスの現行優先順位レベル（ＣＰＬＱＳ）の省略時値は、列３５４に示されるように−１にセットされている。
【００３１】
ここで図９を参照すると、本発明の好ましい実施例でホスト・システム２０２によって実行される初期設定アルゴリズムの流れ図が示されている。
【００３２】
ここで図２、図３、図４および図９を全体的に参照すると、ホスト・システム２０２は、各待ち行列の未処理の（保留されている）要求の数を０に初期設定することから開始する（ブロック７１０）。次に、各待ち行列の未処理の要求の数の最大要求値をセットし、その値をメモリ・ユニット２０８に格納する（ブロック７２０）。たとえば、ホスト・システム２０２は、未処理の要求の最大要求カウントに、Ｑ2は５、Ｑ1は１０、Ｑ0は２０をセットすることができる。これらの最大要求カウントを使用して、ホスト・プロセッサ２０２は、これらの最大値のうちのどれかを超えた場合に新しいＱＰＳテーブルを生成する。また、ホスト・プロセッサ２０２は、各待ち行列の未処理の要求の数の最少要求値をセットし、この値をメモリ・ユニット２０８に格納する（ブロック７３０）。各待ち行列の未処理カウントが、対応する最少要求カウント未満になった時には、ホスト・プロセッサ２０２は、記憶装置コントローラ２１１に省略時のＱＰＳテーブル３００を送ることによって、記憶装置コントローラ２１１で維持されるＱＰＳテーブルをその省略時値にリセットする（ブロック７４０）。図３に示された初期テーブルでは、最高の優先順位がＱ3、中間の優先順位がＱ2、低い優先順位がＱ1、最低の優先順位がＱ0に割り当てられる。
【００３３】
ここで図１０を参照すると、本発明の好ましい実施例でホスト・プロセッサ２０２（送出側）によって実行される要求処理アルゴリズムの流れ図が示されている。記憶装置２１２のいずれかにあるデータをアクセスする要求がホスト・システム２０２によって生成される時に、その要求に割り当てられた優先順位に基づいて、ホスト・システム２０２は、どのＱiでその要求を処理するかを決定する（ブロック８２０）。また、ホスト・プロセッサ２０２は、Ｑiに関する未処理要求のカウントを増やす（ブロック８２０）。その後、ホスト・システム２０２は、未処理要求のカウントが、Ｑiに関して確立された最大要求カウントを超えたかどうかを判定する（ブロック８３０）。未処理要求のカウントがＱiに関して確立された最大要求カウント以下の場合、その要求を記憶装置コントローラ２１１に送って次の処理を行う（ブロック８５０）。しかし、未処理要求のカウントがＱiに関して確立された最大要求カウントを超える場合、ホスト・システム２０２は、新しい（修正されたまたは更新された）ＱＰＳテーブルを生成し、記憶装置コントローラ２１１に送る（ブロック８４０）。記憶装置コントローラ２１１に送られる修正されたＱＰＳテーブルは、Ｑiの優先順位を高められており、その待ち行列にある要求がはるかに早く処理されるようになる。
【００３４】
たとえば、Ｑ1の最大要求カウントに２０がセットされ、未処理要求のカウントが２１の場合、ホスト・プロセッサ２０２は、記憶装置コントローラ２１１に新しいＱＰＳテーブルを送ることができ、このテーブルでＱ1の優先順位を最高優先順位の優先順位３または中間優先順位の優先順位２のいずれかに高め、したがって、Ｑ1内の要求のより早い処理を可能にすることができる。Ｑ1内の要求が実行される際に、その情報が記憶装置コントローラ２１１によってホスト・システム２０２に送り返され、ホスト・システム２０２は、Ｑ1の未処理要求のカウントを１つ減らす。Ｑ1の未処理カウントが所定の最少要求カウント未満になったならば、ホスト・システム２０２は、元のＱＰＳテーブルを記憶装置コントローラ２１１に送って、更新されたＱＰＳテーブルを上書きする。その際に、最高の優先順位３または中間の優先順位２に高められたＱ1の優先順位が、低い優先順位１という初期値に戻される。
【００３５】
図１１を参照すると、記憶サブシステム２１０内の記憶装置のそれぞれの待ち行列管理情報を初期設定するために記憶装置コントローラ２１１（受取側）によって実行される初期設定アルゴリズムの流れ図が示されている。前に述べたように、待ち行列管理情報には、４つの待ち行列、ＱＰＳテーブル、装置コントローラ状況（ＤＣＳ）テーブル、待ち行列ジョブ完了カウンタ、現行行（ＣＲ）レジスタおよび現行列（ＣＣ）レジスタが含まれる。
【００３６】
ここで図２、図３、図４および図１１を参照すると、記憶装置コントローラ２１１は、当初は待ち行列サービスの現行優先順位レベルに−１をセットする（ブロック９１０）。これによって、ホスト・システム２０２から受け取るどのような要求であっても記憶装置コントローラ２１１に割り込むことが保証される。というのは、ホスト・システム２０２から受け取る要求のいずれもが、−１より高い優先順位を有するからである。さらに、記憶装置コントローラ２１１は、各待ち行列内で当初保留されている要求の数に０をセットする（ブロック９２０）。その後、記憶装置コントローラ２１１は、ホスト・システム２０２から省略時のＱＰＳテーブル３００を受け取るのを待つ（ブロック９３０）。ＱＰＳテーブル３００を受け取ったならば、記憶装置コントローラ２１１は、各待ち行列の優先順位をＱＰＳテーブル３００から決定し、その情報をＤＣＳテーブル３５０に入力する（ブロック９４０）。その後、記憶装置コントローラ２１１は、現行行（ＣＲ）レジスタと現行列（ＣＣ）レジスタに−１をセットする。ある待ち行列からの要求の実行が開始されると、ＣＲとＣＣには、現在要求がサービスされている待ち行列を識別するＱＰＳテーブルの行と列がセットされる。さらに、記憶装置コントローラ２１１は、待ち行列のジョブ完了カウンタに０をセットする（ブロック９６０）。
【００３７】
図１２および図１３を参照すると、記憶装置をアクセスする要求を受け取った時に記憶装置コントローラ２１１によって実行される実行アルゴリズムの流れ図が示されている。図２、図１２および図１３を全体的に参照すると、記憶装置コントローラ２１１は、記憶装置へのアクセスの要求を受け取る時に（ブロック１０００）、その要求を特定の待ち行列Ｑiに追加し、対応するＤＣＳテーブル内でＱi内の要求の数のカウントを１つ増やす（ブロック１００５）。次に、記憶装置コントローラ２１１は、対応するＤＳＣテーブルからＱiの現行優先順位（Ｐi）と、待ち行列がサービスされている現行優先順位レベルＰrを読み取る（ブロック１０１０）。その後、記憶装置コントローラ２１１は、ＰiがＰrを超えるか、それ未満か、等しいかを判定する。ＰiがＰr以下の場合、記憶装置コントローラ２１１は、現行要求の実行を継続する。ブロック１０１５に示されるようにＰiがＰrより大きい場合、記憶装置コントローラ２１１は、実行中の現行要求が割込み可能であるかどうかを判定する（ブロック１０２０）。現行要求が割込み可能でない場合、記憶装置コントローラ２１１は、現行要求を完了してから新たに受け取った要求を実行する（ブロック１０２５）。
【００３８】
現行要求が割込み可能である場合、ＤＣＳテーブルの現行優先順位レベルをＰr＝Ｐiにセットし（ブロック１０３０）、現行要求の実行に割り込み（ブロック１０３５）、ＣＣレジスタの内容にＰiをセットする（ブロック１０４０）。次に、現行行レジスタの内容を判定するために、記憶装置コントローラ２１１は、列ＣＣの行０の次行番号ｒjを読み取る（ブロック１０４５）。行ｒjと列ＣＣによって識別される項目の待ち行列がＱiの場合、現行行レジスタ（ＣＲ）の内容にｒjをセットし（ブロック１０５５）、新たに受け取った要求を実行する（ブロック１０６０）。その一方で、行ｒjと列ＣＣによって識別される項目の待ち行列がＱiではない場合、記憶装置コントローラ２１１は、行ｒj、列ＣＣの項目の次行番号の値をｒjの新しい値にセットし（ブロック１０６５）、新しい行番号と列ＣＣによって識別される項目の待ち行列がＱiであるかどうかを判定する（ブロック１０５０）。この手順は、列ＣＣの中でＱi項目が置かれている適当な行が見つかるまで実行される。Ｑiを突き止めたならば、ＣＲの内容にＱiがある行の値をセットし、新たに受け取った要求を実行する。
【００３９】
図１４および図１５を参照すると、ある記憶装置用のＱＰＳテーブルから次にどの要求を実行するかを決定するために記憶装置コントローラ２１１が実行するアルゴリズムの流れ図が示されている。ここで図２、図１６および図１７を全体的に参照すると、要求の実行が完了した時（ブロック１１００）に、記憶装置コントローラ２１１は、対応するＤＣＳテーブルの適当な待ち行列の保留要求のカウントを１つ減らす（ブロック１１０５）。また、記憶装置コントローラは、ｒiにＣＲをセットし、待ち行列のジョブ完了カウンタに０をセットする（ブロック１１１０）。その後、記憶装置コントローラ２１１は、次にサービスする待ち行列を識別するＱＰＳテーブルの行と列を判定し、行と列の情報を下記の形でＣＲレジスタとＣＣレジスタに格納する。現在行が行ｒであると仮定すると、ＱＰＳテーブルの列ＣＣの行ｒの次行番号を読み取って、列ＣＣ内で次にサービスする行がどれであるかを判定する。次の行が行ｒiであると仮定すると、行ｒiの待ち行列番号を読み取って、要求をサービスされる次の待ち行列Ｑmがどれであるかを判定する（ブロック１１１５）。列ＣＣの行ｒiの待ち行列番号が空白の場合、これは、この優先順位レベルでこの待ち行列に要求がないことを意味するので、記憶装置コントローラは、列ＣＣ＝ＣＣ−１にある１つ下の優先順位レベルでの待ち行列のサービスを開始する（ブロック１１２５）。ＣＣ＝ＣＣ−１が−１と等しい場合、実行すべき要求は存在せず、記憶装置コントローラ２１１は、新しい要求を受け取るまで待機する（ブロック１１３０、１１３５および１１００）。ＣＣ＝ＣＣ−１が−１と異なる場合、記憶装置コントローラ２１１は、ｒiに０をセットし（ブロック１１３２）、その後、列ＣＣ＝ＣＣ−１のどの待ち行列を最初にサービスするのかを判定するために、記憶装置コントローラ２１１は、列ＣＣ＝ＣＣ−１の行０の次行番号を読み取り、行０、ＣＣ＝ＣＣ−１によって識別される待ち行列をサービスする（ブロック１１１５）。
【００４０】
ブロック１１２０に戻って、列ＣＣの行ｒiの待ち行列番号が空白ではなく（ブロック１１２０）、その待ち行列Ｑmの要求の数が０より多い場合（ブロック１１３７）、その待ち行列のジョブ完了カウンタに０をセットし（ブロック１１４０）、ＣＲにｒiをセットし、記憶装置コントローラ２１１は、Ｑmからの要求のサービスを開始する（ブロック１１４５）。しかし、行ｒiのＱmの要求の数も０である場合には、待ち行列のジョブ完了カウンタを１カウントだけ増やし（ステップ１１５０）、記憶装置コントローラ２１１は、その待ち行列のジョブ完了カウンタの内容がＱＰＳテーブルの列ＣＣの待ち行列の数と等しいかどうかを判定する（ブロック１１５５）。これらが等しい場合には、記憶装置コントローラ２１１は、待ち行列のジョブ完了カウンタの内容を０にセットし（ブロック１１５６）、前に説明したように（ブロック１１２５）列ＣＣ＝ＣＣ−１にある１つ下の優先順位レベルでの待ち行列のサービスを開始する。
【００４１】
ブロック１１５５に戻って、待ち行列のジョブ完了カウンタの内容（ブロック１１５０）が列ＣＣの待ち行列の数と等しくない場合、前に説明したように（ブロック１１１５）列ＣＣの行ｒiの次行番号を使用して、次にサービスする待ち行列を突き止める。
【００４２】
図５を参照すると、Ｑ0の優先順位が修正されている、ホスト・システム２０２が記憶装置コントローラ２１１に送るＱＰＳテーブル４００の例が示されている。ＱＰＳテーブル４００によれば、Ｑ3は最高の優先順位を有し、Ｑ1は低い優先順位を有し、最低の優先順位の待ち行列はなく、Ｑ0とＱ2の両方が中間の優先順位を有する。
【００４３】
図６は、ＱＰＳテーブル４００に関連するＤＣＳテーブル４５０を示す図である。ＤＣＳテーブル４５０を参照すると、Ｑ0内の要求の数が現在は１５個であることがわかる。
Ｑ0内で許容される要求の最大数が１０であると仮定すると、この場合、Ｑ0内に通常許容されるよりも５個多い実行要求がある。その結果、ホスト・システム２０２は、記憶装置コントローラ２１１にＱＰＳテーブル４００を送り、これを介してＱ0の優先順位を最低の優先順位から中間の優先順位に高め、したがって、記憶装置コントローラ２１１によるＱ0の要求のより早い実行を可能にする。ＱＰＳテーブル４００とＤＣＳテーブル４５０に戻ると、Ｑ3には要求が存在しないので、次に実行される要求は、中間の優先順位を有する列２から与えられる。記憶装置コントローラは、Ｒ０Ｃ２の次行番号を読み取ることによって、列２で最初にサービスされる待ち行列を決定する。Ｒ０Ｃ２の次行番号は２であり、これは、現行優先順位レベルで最初にサービスされる待ち行列がＱ0であることを意味する。Ｑ0からの要求がサービスされたならば、項目Ｒ２Ｃ２の次行番号を読み取って、現行優先順位レベルで調べる必要がある次の待ち行列がどれであるかを判定する。ＱＰＳテーブル４００によれば、項目Ｒ２Ｃ２の次行番号は１であり、これは、次にサービスされる待ち行列がＱ2であることを意味する。しかし、ＤＣＳテーブル４５０によれば、Ｑ2には保留されている要求がない。したがって、項目Ｒ１Ｃ２の次行番号に基づいて、記憶装置コントローラ２１１は、Ｑ0からのもう１つの要求をサービスする。記憶装置コントローラ２１１は、Ｑ0とＱ2の間でトグルを繰返し、Ｑ0が空になるか、所定の最少要求カウント未満になるまでＱ0の要求を実行する。Ｑ0が空になるか所定の最少要求カウント未満になったならば、この情報が記憶装置コントローラ２１１からホスト・システム２０２に送り返される。その後、ホスト・システム２０２は、記憶装置コントローラ２１１に元のＱＰＳテーブルを送り返して、ＱＰＳテーブル４００を上書きする。
【００４４】
図７は、もう１つの修正されたＱＰＳテーブル５００の例である。図８は、修正されたＱＰＳテーブル５００に関連するＤＣＳテーブル５５０である。この例からわかるように、Ｑ3は最も高い優先順位を有し、Ｑ0、Ｑ1およびＱ2は、すべてが中間の優先順位を有し、低い優先順位または最低の優先順位の待ち行列はない。ＤＣＳテーブル５５０を参照すると、Ｑ0には１５個の要求があり、Ｑ1には１５個、Ｑ2には４個の要求があることがわかる。Ｑ3には、保留されている要求はない。ＤＣＳテーブル５５０によれば、待ち行列サービスの現行優先順位レベルは２である。したがって、記憶装置コントローラ２１１は、まず項目Ｒ０Ｃ２を読み取って最初にサービスする待ち行列を決定することによって、列２の待ち行列のサービスを開始する。項目Ｒ０Ｃ２の次行番号は２であるから、記憶装置コントローラは、まずＱ1からの要求をサービスした後に、Ｑ0からの要求をサービスし、Ｑ1からの２つの要求を連続してサービスし、Ｑ2からの要求を１つサービスする。上で述べたように、待ち行列サービスの順序は、列２の各項目の次行番号サブフィールドによって決定される。記憶装置コントローラは、各項目の次行番号を使用して、待ち行列Ｑ0およびＱ1の要求の数がそれぞれの所定の最少要求カウント未満になるまで、Ｑ1、Ｑ0、Ｑ1、Ｑ1およびＱ2からの要求を繰返し実行する。Ｑ0およびＱ1の要求の数がそれぞれの所定の最少要求カウント未満になったならば、その情報をホスト・システム２０２に送り返し、このホスト・システム２０２は、記憶装置コントローラ２１１に省略時テーブルまたは別の修正されたテーブルを送って、ＱＰＳテーブル５００を上書きする。ＱＰＳテーブル５００を使用すると、Ｑ1からの要求が、Ｑ0およびＱ2からの要求よりも頻繁にサービスされることに留意されたい。したがって、Ｑ0、Ｑ1およびＱ2は、すべてが優先順位レベル２であるが、ホスト・システム２０２は、１つまたは複数の待ち行列の優先順位を高めるだけではなく、所与の優先順位レベル内で、１つまたは複数の待ち行列が同じ優先順位レベルの他の待ち行列より頻繁にサービスされるようにするＱＰＳテーブルを送ることができる。
【００４５】
図１６および図１７を参照すると、本発明の代替実施例が示されている。ホスト６０２と記憶サブシステム６１０を含むこの実施例では、待ち行列と関連情報は、記憶装置コントローラのレベルで維持されるのではなく、図１７に示されるように各装置のレベルで維持される。この実施例では、記憶サブシステム６１０に、送出側である記憶装置コントローラ６１１と受取側である複数の記憶装置６１２が含まれる。記憶装置６１２は、通信チャネル６６６を介して記憶装置コントローラ６１１と通信する。この実施例では、記憶装置コントローラ６１１が、各待ち行列の最大カウントと各待ち行列の最少要求カウントをセットし、必要に応じて省略時のＱＰＳテーブルと修正されたＱＰＳテーブルを生成する。この情報は、記憶装置コントローラ６１１から通信チャネル６６６を介してすべての記憶装置に送られる。
【００４６】
図１７からわかるように、通常の記憶装置６５０には、リンク６５４を介して記憶媒体６５６と通信する記憶装置プロセッサ６５２が含まれる。記憶媒体６５６は、リンク６５８を介して緩衝記憶６６０と通信する。緩衝記憶６６０は、リンク６６２を介して装置インターフェース論理機構６６４に接続される。装置インターフェース論理機構は、たとえば、ＳＣＳＩ（small computer system interface）またはＳＳＡ（serial storage architecture）タイプのインターフェースとすることができる。記憶装置プロセッサ６５２は、リンク６７２を介してメモリ・ユニット６７０と通信する。メモリ・ユニット６７０は、待ち行列と、ＱＰＳテーブル、ＤＣＳテーブル、現行行、現行列、待ち行列のジョブ完了カウンタなどの関連情報とを記憶する。要求の処理、待ち行列のサービスおよび優先順位の処理は、本発明の好ましい実施例で行われるのと同一の形で実行される。
【００４７】
本発明の複数の実施例を説明した。しかしながら、本発明の趣旨および範囲から逸脱せずに、さまざまな修正を行うことができることが理解される。たとえば、サービスに関する待ち行列の優先順位は、その待ち行列のサービスに関する平均応答時間が所定の閾時間値を超えた時に動的に調節することができる。また、各待ち行列の最大要求カウントおよび最少要求カウントは、送出側ではなく受取側で維持することができる。この実施態様では、受取側によって発行される割込みが頻繁になる代わりに送出側の記憶空間が節約される。また、本発明の好ましい実施例では各記憶装置に関連して４つの待ち行列だけを示したが、これより多数または少数の待ち行列を利用できることは当業者に明白であろう。さらに、最高優先順位の待ち行列を含むどの待ち行列の優先順位も、本明細書に開示された発明を使用して高めるか低めることができることも当業者には明白であろう。したがって、本発明は、具体的に示された実施例に制限されるものではなく、請求項の範囲のみによって制限される。
【００４８】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４９】
（１）プロセッサと記憶装置と要求をサービスするための複数の待ち行列とを含むデータ処理システムにおいて、
各待ち行列の最大カウントを定義するステップと、
要求が待ち行列に追加される時に、前記待ち行列にある要求の数が前記待ち行列の最大カウントより大きいかどうかを計算するステップと、
前記待ち行列にある要求の数が前記待ち行列の最大カウントより大きい場合に、所定の量だけ前記待ち行列の優先順位を高めるステップと
を含む、待ち行列の優先順位を動的に調節する方法。
（２）前記待ち行列が、プロセッサに記憶されることを特徴とする、上記（１）に記載の方法。
（３）前記待ち行列が、記憶装置に記憶されることを特徴とする、上記（１）に記載の方法。
（４）ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記ホストから受け取る要求をサービスするための、前記記憶装置コントローラ内で維持される複数の待ち行列と、
待ち行列にある要求の数が所定の数より少ない場合に前記待ち行列の優先順位を下げるためのプロセッサと
を含む、データ処理システム。
（５）ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記記憶装置コントローラから受け取る要求をサービスするための、前記複数の記憶装置内で維持される複数の待ち行列と、
待ち行列にある要求の数が所定の数より少ない場合に前記待ち行列の優先順位を下げるためのプロセッサと
を含む、データ処理システム。
（６）プロセッサと記憶装置と要求をサービスするための複数の待ち行列とを含むデータ処理システムにおいて、
各待ち行列の最少要求カウントを定義するステップと、
要求が待ち行列に追加される時に、前記待ち行列にある要求の数が前記待ち行列の最少カウントより少ないかどうかを計算するステップと、
前記待ち行列にある要求の数が前記待ち行列の最少カウントより少ない場合に、所定の量だけ前記待ち行列の優先順位を下げるステップと
を含む、待ち行列の優先順位を動的に調節する方法。
（７）前記待ち行列が、プロセッサに記憶されることを特徴とする、上記（６）に記載の方法。
（８）前記待ち行列が、記憶装置に記憶されることを特徴とする、上記（６）に記載の方法。
（９）ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記ホストから受け取る要求をサービスするための、前記記憶装置コントローラ内で維持される複数の待ち行列と、
待ち行列にある要求の数が所定の数より少ない場合に前記待ち行列の優先順位を下げるためのプロセッサと
を含む、データ処理システム。
（１０）ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記記憶装置コントローラから受け取る要求をサービスするための、前記複数の記憶装置内で維持される複数の待ち行列と、
待ち行列にある要求の数が所定の数より少ない場合に前記待ち行列の優先順位を下げるためのプロセッサと
を含む、データ処理システム。
（１１）ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記ホストから受け取る要求をサービスするための、前記記憶装置コントローラ内で維持される複数の待ち行列と、
待ち行列の平均応答時間が所定の数より大きい場合に前記待ち行列の優先順位を高めるためのプロセッサと
を含む、データ処理システム。
（１２）ホストと、
記憶装置コントローラと複数の記憶装置とを含む、前記ホストと通信する記憶サブシステムと、
前記記憶装置コントローラから受け取る要求をサービスするための、前記複数の記憶装置内で維持される複数の待ち行列と、
待ち行列の平均応答時間が所定の数より大きい場合に前記待ち行列の優先順位を高めるためのプロセッサと
を含む、データ処理システム。
【図面の簡単な説明】
【図１】複数の待ち行列を有する記憶サブシステムと通信するホスト・システムを有するデータ処理システムを示す図である。
【図２】本発明の好ましい実施例を示す図である。
【図３】省略時ＱＰＳテーブルを示す図である。
【図４】省略時ＤＣＳテーブルを示す図である。
【図５】待ち行列の優先順位が変更されているＱＰＳテーブルを示す図である。
【図６】図５のＱＰＳテーブルに関連するＤＣＳテーブルを示す図である。
【図７】待ち行列の優先順位が変更されている、修正されたＱＰＳテーブルを示す図である。
【図８】図７のテーブルに関連するＤＣＳテーブルを示す図である。
【図９】送出側によって実行される初期設定アルゴリズムの流れ図である。
【図１０】送出側によって実行される要求処理アルゴリズムの流れ図である。
【図１１】ＤＣＳテーブルを作成するために受取側によって実行される初期設定アルゴリズムの流れ図である。
【図１２】要求を受け取る時に受取側によって実行される実行アルゴリズムの流れ図である。
【図１３】要求を受け取る時に受取側によって実行される実行アルゴリズムの流れ図である。
【図１４】次にどの要求を実行する必要があるかを決定するために受取側によって実行される実行アルゴリズムの流れ図である。
【図１５】次にどの要求を実行する必要があるかを決定するために受取側によって実行される実行アルゴリズムの流れ図である。
【図１６】本発明の代替実施例を示す図である。
【図１７】図１６の直接アクセス記憶装置（ＤＡＳＤ）を示す図である。
【符号の説明】
２０２  ホスト・システム
２０４  ホスト・プロセッサ
２０６  ホスト・アダプタ
２１０  記憶サブシステム
２１１  記憶装置コントローラ
２１２  記憶装置
２２０  記憶装置コントローラ・プロセッサ
２２２  メモリ・ユニット
２２４  待ち行列管理情報
２３０  記憶装置
２３６  待ち行列
２４０  現行行（ＣＲ）レジスタ
２４１  現行列（ＣＣ）レジスタ
２４２  待ち行列のジョブ完了カウンタ（ＱＪＣＣ）
２４３  待ち行列優先順位およびサービス・テーブル（ＱＰＳテーブル）
２４４  装置コントローラ状況テーブル（ＤＣＳテーブル）
【図１】
0003659279.tif 000002
【図２】
0003659279.tif 000003
【図３】
0003659279.tif 000004
【図４】
0003659279.tif 000005
【図５】
0003659279.tif 000006
【図６】
0003659279.tif 000007
【図７】
0003659279.tif 000008
【図８】
0003659279.tif 000009
【図９】
0003659279.tif 000010
【図１０】
0003659279.tif 000011
【図１１】
0003659279.tif 000012
【図１２】
0003659279.tif 000013
【図１３】
0003659279.tif 000014
【図１４】
0003659279.tif 000015
【図１５】
0003659279.tif 000016
【図１６】
0003659279.tif 000017
【図１７】
0003659279.tif 000018