"リアルタイム優先順位を有するアクセス要求を含む様々な優先順位のアクセス要求の作業負荷を有する記憶装置のためのストレージアクセススケジューリング方法であって、該記憶装置に関する少なくとも1つのパラメータにより該記憶装置を特徴付けし、該特徴付けが、該記憶装置に関する同時アクセス最大スループットに関する同時アクセス要求の平衡数を決定することを含み、前記作業負荷に関する少なくとも1つのパラメータにより該作業負荷を特徴付けし、所定のアクセス要求記憶場所値に関連付けられたリアルタイムアクセス要求を受信し、該アクセス要求記憶場所値並びに前記記憶装置及び前記作業負荷を特徴付ける取得された前記パラメータに基づいてプロセッサを使用して該リアルタイムアクセス要求を処理する、という各ステップを含む、ストレージアクセススケジューリング方法。前記記憶装置を特徴付ける前記ステップが、同時アクセス要求の平衡数に基づいて最悪の装置サービスレイテンシ値を決定するステップを含む、請求項1に記載の方法。前記記憶装置を特徴付ける前記ステップが、前記同時アクセス最大スループットに関連する最悪の最大スループットレート時間値を決定するステップを含み、前記記憶装置及び前記作業負荷の特徴付けから決定された値が時間に基づくものである、請求項1に記載の方法。前記作業負荷を特徴付ける前記ステップが、リアルタイム優先順位を有する作業負荷におけるアクセス要求についての最悪の総サービスアクセス時間に関連する最小初期スラックタイム値を決定し、リアルタイム優先順位を有する作業負荷におけるアクセス要求に関するバースト性値を決定し、及び前記記憶装置及び前記作業負荷の特徴付けから取得された値に基づいて最悪のキュー遅延値を決定する、という各ステップのうちの少なくとも1つを含む、請求項2に記載の方法。前記リアルタイムアクセス要求を処理する前記ステップが、リアルタイムアクセス要求のみを保持する保留キューにリアルタイムアクセス要求を割り当て、リアルタイムアクセス要求のみを保持する前記保留キューから前記リアルタイムアクセス要求を取り出し、該リアルタイムアクセス要求を一次キューに割り当てる、という各ステップを含む、請求項4に記載の方法。前記決定された最悪のキュー遅延値に関するパラメータが前記一次キューに関連付けられる、請求項5に記載の方法。前記決定されたバースト性値に関するパラメータが、リアルタイムアクセス要求のみを保持する前記保留キューに関連付けられる、請求項5に記載の方法。シグマタイムバジェット、ゼータタイムバジェット、及びデルタタイムバジェットの間で割り当てられるラムダタイムバジェットが、前記決定された最小初期スラックタイム値に関連付けられ、前記決定されたバースト性値が前記シグマタイムバジェットに関連付けられ、前記決定された最悪のキュー遅延値が前記ゼータタイムバジェットに関連付けられ、及び前記決定された最悪の装置サービスレイテンシ値が前記デルタタイムバジェットに関連付けられる、請求項7に記載の方法。前記一次キューが現在のキュー及び次のキューへと分割され、該現在のキュー及び該次のキューが異なる優先順位のアクセス要求を受容し、該受容した異なる優先順位のアクセス要求をそれぞれのアクセス要求記憶場所値に基づいて前記現在のキュー及び前記次のキューに割り当て、該現在のキューと該次のキューとのスワップを調整するためのカウントを該現在のキューに関連付け、該現在のキューにアクセス要求が割り当てられた際に該カウントを修正する、請求項5に記載の方法。前記一次キューが、リアルタイムアクセス要求のみを保持する前記保留キューからの要求を受容することに加えて、リアルタイム優先順位よりも低い優先順位の少なくとも1つの保留キューからリアルタイム優先順位よりも低い優先順位のアクセス要求を受容する、請求項6に記載の方法。前記リアルタイムアクセス要求を処理する前記ステップが、リアルタイム優先順位よりも低い優先順位のアクセス要求が前記一次キューに割り当てられた場合、該一次キューに対するリアルタイムアクセス要求の割り当てに応じて該一次キューから以前に割り当てられたリアルタイム優先順位よりも低い優先順位のアクセス要求を取り出す、という各ステップを含む、請求項10に記載の方法。前記最小初期スラックタイム値が、複数の異なる優先順位のアクセス要求の作業負荷に対する予想される将来の変化に関連する信号に応じて再決定される動的なパラメータである、請求項5に記載の方法。前記再決定される最小初期スラックタイム値が、複数の異なる優先順位のアクセス要求の作業負荷に対する予想される将来の変化に関連する信号に応じて前記記憶装置及び前記作業負荷の特徴付けから取得された少なくとも1つの値に基づいて決定される、請求項12に記載の方法。リアルタイム優先順位を有するアクセス要求を含む様々な優先順位のアクセス要求の作業負荷を有する記憶装置のためのストレージアクセススケジューリングを実行するための装置であって、プロセッサを備えており、該プロセッサが、前記記憶装置に関連する少なくとも1つのパラメータにより該記憶装置の特徴付けを行う装置特徴付けモジュールであって、該特徴付けが、前記記憶装置に関する同時アクセス最大スループットに関する同時アクセス要求の平衡数を決定することを含む、装置特徴付けモジュールと、前記作業負荷に関する少なくとも1つのパラメータにより該作業負荷の特徴付けを行う作業負荷特徴付けモジュールと、同時要求スケジューリングCRS処理モジュールであって、所定のアクセス要求記憶場所値に関連付けられたリアルタイムアクセス要求を受信し、該アクセス要求記憶場所値並びに前記記憶装置及び前記作業負荷を特徴付ける取得された前記パラメータに基づいて該リアルタイムアクセス要求を処理する、同時要求スケジューリングCRS処理モジュールとを動作させる、記憶装置のためのストレージアクセススケジューリングを実行するための装置。コンピュータシステムによる実行時にリアルタイム優先順位を有するアクセス要求を含む様々な優先順位のアクセス要求の作業負荷を有する記憶装置のためのストレージアクセススケジューリングを実行するコードを含むコンピュータ読み取り可能命令を格納した持続性コンピュータ読み取り可能媒体であって、該コンピュータ読み取り可能命令が、前記記憶装置に関する少なくとも1つのパラメータにより該記憶装置の特徴付けを行い、前記記憶装置に関する同時アクセス最大スループットに関する同時アクセス要求の最小数を決定し、前記作業負荷に関する少なくとも1つのパラメータにより該作業負荷の特徴付けを行い、所定のアクセス要求記憶場所値に関連付けられたリアルタイムアクセス要求を受信し、該アクセス要求記憶場所値並びに前記記憶装置及び前記作業負荷を特徴付ける取得された前記パラメータに基づいてプロセッサを使用して前記リアルタイムアクセス要求を処理する、という各ステップを実行するためのコードを含む、持続性コンピュータ読み取り可能媒体。異なる優先順位タイプが同時に処理される場合、記憶装置上で一層高い優先順位の要求が処理されている間にスケジューラが一層低い優先順位の要求を該記憶装置へ送ることができないのであれば、記憶装置の全体的なスループット性能は低下し得る。この種の環境は、システムスループットに劇的な悪影響を与える結果となることが多い。リアルタイムアクセス要求は、ベストエフォート又はバックグランド優先順位要求よりも高い優先順位を有する。一層低レベルの優先順位の要求とのリアルタイムアクセス要求の同時処理は、環境によっては特に厄介なものとなる。合併症スターべーションstarvationなどの可能性は一層深刻なものとなり、これは、リアルタイムディスク要求が通常は何らかのレベルの保証されたほぼ即座のIOデータのアクセスに関するものであるからである。かかる保証を満足させようとして、スケジューラは典型的には、総システム効率及びスループットに更なる制約を課す。更に、保証されたアクセス期限を守れず又は該アクセス期限に間に合わないことが、リアルタイムアクセス要求に関する別の種類の問題である。これら問題の全ては、リアルタイムアクセス要求のスケジューリングに関するものである。これらの問題は、リアルタイム要求と一層低い優先順位の要求とが混合したものの一部としてリアルタイムアクセス要求をスケジューリングする場合に一層悪化することが多い。単純化及び例示のため、本開示は主にその実施形態を参照することにより説明を行う。以下の記述では、本開示の十分な理解を提供すべく様々な特定の細部について説明する。しかし、本開示は、かかる特定の細部に限定することなく実施することが可能である、ということが容易に理解されよう。別の例では、本開示の説明が不必要に不明瞭なものとならぬよう幾つかの方法及び構造については詳細に説明していない。別の例では、本開示が不必要に曖昧とならぬよう幾つかの方法及び構造については詳細に説明していない。本書で用いる場合、用語含むとは、含むことを意味するがそれに限定されるものではなく、用語含んでいるとは、含んでいることを意味するがそれに限定されるものではない。用語に基づきとは、少なくとも部分的に基づくことを意味する。1.概説本書で開示するのは、リアルタイムアクセス要求を含む様々な優先順位のアクセス要求の作業負荷を有する記憶装置のための記憶装置アクセスのスケジューリングのための方法、装置、及びコンピュータ読み取り可能媒体である。本開示は、混合型作業負荷におけるリアルタイムアクセス要求に関する保証されたアクセスの最悪の総サービス時間を成功裏に満たす一方で記憶装置の高レベルのスループット性能を維持することに伴う問題に対処するものである。本開示は、広範な動作条件にわたって実質的に最適となるスループットを提供する。本開示は、記憶装置及び該記憶装置に関する作業負荷を特徴付ける少なくとも1つのパラメータを利用する。かかるパラメータを記述するデータは、動作中に動的に更新することが可能である。計算上の観点からすると、マシン読み取り可能命令は非常に効率的であり、及びO型マシン読み取り可能命令nは要求に関するキューのサイズを用いて実施することが可能である。該マシン読み取り可能命令は、比較的単純であり、及び非常に少数行のコードを用いて実施することが可能であり、このため、実施した命令の確認を一層低い複雑性で行うことが可能となる。2.定義本書で用いる場合、用語アクセス要求は、記憶装置に関するIOデータを取り出し又は提供するために記憶装置へ送られるディジタル命令である。該データの記憶アドレスは、該命令の一部とすることが可能である。プロセッサは、該命令をデコードする際に、要求された情報を読み出し及び又は格納することができる場所の記憶アドレスを取得する。本書で用いる場合、用語アクセス要求は用語要求と置換可能に使用される。本書で用いる場合、用語同時アクセス要求の平衡数Nは、記憶装置を特徴付けるパラメータである。該同時アクセス要求の平衡数Nは、該装置のスループットに対して総未処理IOをプロットすることにより導出することが可能である。図3に関して以下で一層詳細に説明するように、導出されたプロット中の膝領域が、同時アクセス要求の平衡数Nである。この決定により、許容可能な最悪のサービス時間を有する最大スループット性能を有するポイントNが見い出される。これは、Nの関数としてのスループット性能が平坦になる曲線の膝部分で一般に生じる。本書で用いる場合、用語バースト性burstiness値は、作業負荷におけるリアルタイム要求のバースト性に関する計数又は期間といった値である。本書で用いる場合、用語同時アクセス最大スループットは、平均要求サイズでの同時アクセス要求の平衡数Nに関するスループットである。本書で用いる場合、用語マシン読み取り可能命令セットMRISは、アルゴリズム、プログラム、コード、ソフトウェア等といった、マシンにより読み取ることが可能な一組のディジタル命令である。本書で用いる場合、用語最悪の最大スループットレート時間1IOPSは、一次キューを介した同時アクセス要求の平衡数Nの処理に関する時間値である。タウtauに関する値は、リード/ライト、ランダム/シーケンシャル、及び要求サイズ及び随意選択的にその他の値のための値に少なくとも関連することが可能な関数である。以下で定義するスループットレート時間も参照されたい。本書で用いる場合、用語記憶装置は、記憶装置、磁気テープ、ディスク等といったコンピュータ機器の1つであり、又はデータ及び命令を通常はバイナリ形式で格納することができる関連する複数のコンピュータ機器の組み合わせである。本書で用いる場合、用語最小初期スラックタイム値ラムダは、リアルタイムアクセス要求のための保留キュー、一次キュー、及びブラックボックス装置キューを介してCRSアーキテクチャでリアルタイムアクセス要求を通過させるための総処理時間に関する時間値である。本書で用いる場合、用語保留キューは、アクセス要求に関する特徴アクセス優先順位レベルなどに基づいて追加されたアクセス要求を保持するキューである。該保留キュー中のアクセス要求は、他のキュー一次キューなどに割り当てられるのを該保留キュー内で待機し、該他のキューに割り当てられた後、記憶装置に関する記憶場所へのIOアクセスのために処理されることになる。本書で用いる場合、用語一次キューは、記憶装置への直接アクセスが認められたものとして追加されたアクセス要求を保持するキューであり、該一次キュー内のアクセス要求は、記憶装置に関する記憶場所に対するIOアクセスのために該記憶装置に関する内部的なブラックボックスキューを介して割り当てられて処理されるのを待機する。本書で用いる場合、用語リアルタイム優先順位は、記憶装置でのサービスのためにリアルタイムアクセス要求を処理するための期限が関連付けられた該リアルタイムアクセス要求に対して割り当てられる高い優先順位である。本書で用いる場合、用語SCANは、ディスクに対する多数のアクセスをスケジューリングするためのマシン読み取り可能命令セットMRISであり、MRISとも呼ばれる。多数の要求が、記憶装置上のデータの位置に従って順序づけされる。これにより、最悪の場合にディスク全体にわたる1回のスキャン又は掃引のためのディスクアームの運動が低減される。サービス時間は、ディスクのトラック間シークタイム、最大シークタイム1回のスキャン、及び最大回転レイテンシから推定することができる。本書で用いる場合、用語記憶場所は、記憶装置内のディスク上にデータを格納することができる場所を識別する論理アドレスその他の場所決定因子である。本書で用いる場合、用語スループットレート時間は、各要求の完了間の平均時間であり、IOPS1秒あたりのIOの逆数として定義することができる。スループットレート時間は、そのアーキテクチャの並行処理のため、一要求の平均サービス時間の代わりに利用される。要求のための期待されるリソース要件としてスループットレート時間を使用することにより、ストレージデバイス又は記憶装置の利用のために総和summationを介して一層単純で一層精確な計算accountingが可能となる。本書で用いる場合、用語最悪の総サービスアクセス時間は、経過することができる最長期間であり、その経過後には、リアルタイムアクセス要求は、そのリアルタイムサービス期限を徒過する前に記憶装置でサービスされなければならない。本書で用いる場合、用語最悪の装置サービスレイテンシ値デルタは、記憶装置内に内部的なブラックボックスキューを含む該記憶装置に関するブラックボックス構成での総サービス時間に関する時間値である。本書で用いる場合、用語最悪のキュー遅延値ゼータは、CRSアーキテクチャでの一次キューを介した要求の処理に関する時間値である。ゼータは、本質的には作業負荷の特徴ではなく、CRSアーキテクチャ200等のCRSアーキテクチャに関して導出されるパラメータである。3.CRSアーキテクチャ図1を参照すると、図2に示すCRSアーキテクチャ200等のCRSアーキテクチャを実施するための例証となる同時要求スケジューリングCRSシステム100の実施形態を単純化したブロック図が示されている。以下、CRSシステム100について一層詳細に説明する。CRSアーキテクチャ200では、一例によれば、機能及び優先順位レベルに従って相関する複数のキュー202210が存在する。以下で一層詳細に説明するように、CRSアーキテクチャ200において該キュー202210にパラメータを関連付けることも可能である。CRSアーキテクチャ200は、記憶装置及びそのオペレーティングシステムの直前に従来の内部的なブラックボックスキュー202を含む。該ブラックボックスキュー202に先行して一次キュー204が存在する。この例では、該一次キュー204は、LCSCANなるラベルが付されたスケジューリングのためにマシン読み取り可能命令セットMRISを利用する。以下で一層詳細に説明するように、LCSCAN制限されたLimitedCSCAN又はLCSCANとも呼ばれるは、循環スキャンCSCANと題する周知のMRISの変種である。LCSCANは、最悪のキュー遅延保証を提供するようサイズが制限された一次キュー204を管理する。一次キュー204は、リアルタイム、ベストエフォート、及びバックグランドといった優先順位レベルのアクセス要求を含む異なる優先順位レベルを有する複数のアクセス要求を含むことが可能である。これらの異なる優先順位の要求は、性能の最適化のために一次キュー204内でソートされる。図2において、一次キュー204の左側には、リアルタイム要求のための保留キュー206が存在する。この例では、保留キュー206は、SCANEDFすなわちSCANEearliestDeadlineFirst:最も古い期限を最初にスキャンと題するMRISを使用して、一次キュー202に入れられるのを待っているリアルタイム優先順位の要求を管理する。また、CRSアーキテクチャ200では、ベストエフォート優先順位の要求のための保留キュー208は、CSCANと題するMRISにより管理されるバックグランド優先順位レベルの要求は、一次キュー204に入れることもまだ入れないことも可能なものであり、この例では、保留キュー210内に保持される。CRSアーキテクチャ200以外のリアルタイム要求なしの代替的なアーキテクチャでは、該代替的なアーキテクチャは、単純に、要求を記憶装置内に供給して該記憶装置に複数の同時要求の一定のプールを保持するCSCANキューのみとすることが可能である。この種の代替的なアーキテクチャをリアルタイム保証を提供するように変更し又は拡張させるのは困難である。第1に、CSCANキューの最悪のキュー遅延は、通常はCSCANキュー長さの約2倍となり、このため、CSCANキューの長さを制限すべきである。これは、該最悪のキュー遅延が、記憶装置の最悪のレイテンシよりも小さい最小初期スラックタイムよりも一般に小さくなるようにするということである。しかし、CSCANの最悪の挙動は、本質的に制限のないものである。この種の無制限の最悪の挙動を回避するために、CRSアーキテクチャ200は、以下で一層詳細に説明するように、CSCANLCSCANの変種を使用する。第2に、CSCANキューサイズが制限されると、該CSCANキューへ未だ送ることができない過度の要求を吸収するために、該制限されたCSCANキューの前に保留キューが存在する可能性がある。CRSアーキテクチャ200は、リアルタイム要求及びその他の優先順位の要求のためにLCSCANを使用する。このため、リアルタイム要求のための保留キュー206は、効率的で期限に感応するMRISとしてSCANEDFを使用して、リアルタイム要求のみを保持する該保留キュー206を管理する。非リアルタイム要求のための保留キューは効率的なものとすることが可能である。このため、この例によれば、CRSアーキテクチャ200は、ベストエフォート優先順位を有する要求を保持するCSCAN保留キュー208を使用する。第3に、リアルタイム要求の場合、CSCANキュー208のサイズは、リアルタイム要求がSCANEDFキュー206内で費やすことが可能な最大時間を構成するよう削減することが可能である。このSCANEDFキュー206のサイズの削減は、要求ストリームのバースト性の関数とすることが可能である。CRSアーキテクチャ200は、様々な他の例に従って変更することが可能である。例えば、CRSアーキテクチャ200は、単一のベストエフォートCSCANキュー208をFahhradlikeキューシステムに置換して、複数の装置にわたるベストエフォート要求ストリームのフェアネスを確保することが可能である。LCSCANは、そのフェアネス特性が故に、また複数の下位レベルスケジューラと十分に対話してほぼ最適な全体的なシステム性能を生み出すため、CSCANに基づくものである。しかし、最悪のキュー遅延が保証され又は要求の期限が満たされる限り、他のMRISスケジューリングプログラムをCRSアーキテクチャ200で使用して一次キュー204を管理することが可能である。かかる制限に達すると、新たな要求は、記憶装置内でスキャンされるディスク上の該要求の位置にかかわらず、次のスキャンにスケジューリングされる。図2はまた、リアルタイム期限を確実に守るべくCRSアーキテクチャ200におけるキュー202210の最悪の挙動を計算し制御する方法を例証するものである。CRSアーキテクチャ200は、互いに接続された複数のキューのパイプラインとして設計されているため、該パイプラインの各キューは別個に、SCANEDFキュー206、LCSCAN一次キュー204、並びにOS及び装置キュー202とみなすことが可能である。CRSアーキテクチャ200では、任意の内部的なOSスケジューラ、任意の内部的なRAIDコントローラ、及び任意の内部的な記憶装置スケジューラの組み合わせは全て、ブラックボックスキュー202に関連する単一のブラックボックス装置として取り扱われる。一例によれば、CRSアーキテクチャ200においてリアルタイム保証を提供するための第1の方法は、キュー202における記憶装置の性能の特徴付けを行うことである。この記憶装置の性能の特徴付けは、該記憶装置の最悪のレイテンシ及び最悪のスループットレート時間を実験データに基づいて予測するためのモデルを含むことが可能である。該最悪のスループットレート時間は、所与の並行処理レベルで所与のサイズの要求を処理する際の最悪の1秒あたりのIO動作の逆数として定義することが可能である。記憶装置の特徴付けの一要素は、LCSCANキュー204として図2に示す一次キュー204に関係する。LCSCANMRISは、最悪のLCSCANキュー待機時間ゼータ214が一次キュー204の長さの関数となるように設計することが可能である。次に考慮すべき事柄は、所与のLCSCAN一次キュー204の長さについての最悪の装置完了時間の決定である。CRSアーキテクチャ200の目標は、全てのリアルタイム要求が確実にその期限を守ってLCSCANキュー204に入ることにあり、該CRSアーキテクチャ200は、現在LCSCANキュー204内にある要求についての時間割当量に追加の時間を許容して、該時間割当量内にリアルタイム要求のための余地を作るべきである。換言すれば、最悪の総予測時間ラムダ218は、図2で例証した3つの時間割当量アイテム、すなわち、記憶装置における最悪の時間デルタ212、LCSCANキュー内で待機している最悪の時間ゼータ214、及びLCSCANキュー204に入るためにSCANEDFキュー内で待機している最悪の時間シグマ216を含むことが可能である。記憶装置における最悪の時間デルタ212は、一定また所与の値とすることが可能であり、その制御ポイントは、LCSCANキュー204のサイズとすることが可能である。次いでこれは、LCSCANキューにおける最悪の時間ゼータ214を支配することが可能である。このため、最大サイズのLCSCANキュー204は、該LCSCANキュー204に入るために待機しているSCANEDFキュー206内のリアルタイム要求にとって利用可能となる時間割当量すなわち最悪の予測時間シグマ216を制御することが可能である。該LCSCANキューにおける最悪の時間ゼータ214は、一次キュー204内の要求の個数及び/又は該要求がLCSCANMRISにより管理されているレートの関数とすることが可能である。CRSアーキテクチャ200におけるリアルタイム作業負荷のバースト性または可変性は、最悪の総予測時間ラムダ218のシグマ216に対する時間割当量の割り当てに影響を与え得るものである。1つの方法は、バースト性を測定すること、もう1つの方法はバースト性を宣言するために要求を生成するアプリケーションを有することとし得る。LCSCANキューゼータ214で費やした時間と同様に、リアルタイム要求がSCANEDFキューシグマ216中で費やした時間は、SCANEDFキュー206の長さ及び最悪のスループットレートの関数とすることが可能である。SCANEDFキュー206の目的は、バーストburstsを吸収すること、及びLCSCANキュー204へリアルタイム要求を提出することが可能となるまで該リアルタイム要求を保持することにある。これは、LCSCANキュー204が大きくなり過ぎるのを防止し、ひいてはLCSCANキュー204内で待機している要求が飢餓状態となってstarvingその期限を徒過することが防止される。SCANEDFキュー206を使用することにより、リアルタイム要求をその期限に従ってLCSCANキュー204へ提出することが確実となる。SCANEDFキュー206の使用はまた、スキャン順に反して提出されたリアルタイム要求がその期限を徒過しない可能性を低減させる。代替的な方法では、要求のサイズの可変性を考慮することが可能である。この方法では、要求は、その最悪のスループットレートに関して定義される。この場合には、LCSCAN待機時間ゼータ214及びSCANEDF待機時間シグマ216は、それらが保持することができる要求の個数ではなく時間に関して定義することが可能である。4.記憶装置の特徴付け以下の例では、様々な実例の結果を提示する。これらの結果は、2つのデュアルコアIntelプロセッサ及び4GBのRAMを有しWINDOWSSERVER2008を実行しているHPDL360サーバ上で生成されたものである。性能テストに使用したストレージアレイは、8つの146GB15kRPMのSASディスクからなり、HPP410iストレージコントローラに対して2つのSCSIケーブルで各ケーブルに4つのディスクが取り付けられている。該ストレージは、128kBストライプ及び11TBの総利用可能サイズを有するRAID0に構成されていた。これらの例で使用されたMRISは、ファイルシステムを使用するのではなく、使用される装置に直接アクセスし、また、スレッド処理及び非同期IO能力を使用して、前記装置へ複数のIOを一度に送信する。特に示さない限り、ベンチマークは、一様なランダムディスクアドレスによる閉ループ環境を使用した。通常、装置への送信を待機する4000のベストエフォート読み出し要求がキュー内に存在し、使用した装置は60の同時要求を受け付ける。リアルタイム要求は通常は、30秒の初期スラックタイムを有し、及びディスクアドレスの一様なランダムな分布を使用する。それらの期限は、所与の要求サイズについて所望のスループットレートを適合させるよう時間的に一様に隔置された。先行するリアルタイム要求についてのサービスの完了の有無又は該サービスの実行態様にかかわらず、前記30秒の初期スラックタイムを確保する必要がある場合に新たなリアルタイム要求がキューに追加された。また、RAIDコントローラの書き込みバッファキャッシュ及びSCSIディスクの即時書き込み報告から得られる性能の向上を除外するために読み出し専用要求ストリームを使用した。リアルタイム保証を提供するために、一例によれば、まず最初に記憶装置の特徴付けを行わなければならない。同時並行性、要求のサイズ、及び要求の逐次性といった、装置性能に影響を与え得る複数のパラーメータが存在する。オペレーティングシステム内のディスクスケジューラ、RAIDコントローラ内のディスクスケジューラ及び書き込みキャッシュ、並びにディスク自体のディスクスケジューラといった、互いに協働する複数の装置が潜在的に存在するという事実により、実際の記憶装置の精確な特徴付けの実行は複雑なものとなる。その個々の装置が記憶装置を構成することが可能であり、又はそれら装置の任意の組み合わせが記憶装置を構成することが可能である。所与の記憶装置に関する複数のパラメータの特徴付けを行う場合、その各パラメータ毎に該記憶装置の複数の同じ構成要素の特徴付けを行うことが可能である。リアルタイム要求が所与のアプリケーションにより記憶装置へ送信されたとき、未処理のリアルタイム要求が時間内に完了することを確実にするために該アプリケーションが行わなければならない制御は、該記憶装置に対する更なる要求を許可しないことにより、サービスすべき代替的な要求を装置間スケジューラから不足させることである。同時並行性を常に最大限にすること又は性能を最大限にすることが望ましい。これは、リアルタイム要求が少なくとも最悪の予測サービス時間よりも前にほぼ常に完了するように、該リアルタイム要求を十分に事前に装置へ提示すべきことを意味している。そうでない場合には、期限を徒過する危険性のあるリアルタイム要求を装置が完了させるまで同時並行性を確保し該装置から要求を不足させる必要がある。図3は、2つの例示的な要求サイズ4kB及び1MBについて装置における要求の同時並行性の関数としてスループットを示すグラフ300である。この例は、ディスクアドレスの一様なランダム分布を用いて4000個の要求について閉ループシステムを用いて完了させ、及びCSCANキューを介して送ったものである。図3で例証されるように、同時並行性の要求を使用することには大きな性能上の利益が存在する。図3は、記憶装置を特徴付けるパラメータとしての同時アクセス要求の平衡数Nの決定を例証している。該同時アクセス要求の平衡数Nは、以下で一層詳細に説明するCRS装置102内の装置特徴付けモジュール106を使用して導出することが可能である。該パラメータは、スループットに対する未処理のIOをプロットすることにより導出することが可能である。図3に示すように、この例の記憶装置の場合、同時並行性に関連する利益は、約60個の同時要求についての該プロットされた曲線の膝領域に達するものである。この導出されたプロットにおける膝領域は、同時アクセス要求の平衡数Nである。この決定により、最大スループット性能に関するポイントNがまた、許容可能な最悪のサービス時間を有することが見いだされる。通常の環境下では、これは、IOの個数の関数としてのスループット性能が平坦になる曲線の膝領域で生じる。図3に示すように、この例の決定では、60個の同時要求が、4kB~1MBの要求サイズの範囲にわたり記憶装置について一貫したものとなる。以下の例では、記憶装置についてのデフォルトのテスト済みの同時並行性が、該記憶装置の特徴付けに関連する他のパラメータを決定するため、60個の同時アクセス要求が平衡数Nとして使用される。図4は、記憶装置についての要求サイズの関数として総スループットを例証するグラフ400である。そのデータは図4に示す2つの曲線について生成されている。一方の曲線は、記憶装置において一度につき様々なサイズの単一要求が存在する例すなわち、テストされた同時並行性:1を示している。他方の曲線は、記憶装置において一度につき60個の同時要求が存在する例すなわち、テストされた同時並行性:60を示している。この2つの曲線は、利用可能な同時並行性を利用することによる利益が1kB-16MBの範囲の要求サイズにわたって一貫して大きなものとなることを例証している。図5は、テストされた記憶装置に関し、CSCANキューサイズの大きさの関数としてスループット性能が如何に変化するかを例証したグラフ500である。該CSCANキューは、シークタイムを最小限にするよう複数の要求を並べ換える。該CSCANキューはまた、装置上で空間的に隣接している複数の要求を時間的に一層近くで処理する。これは、一般に、位置知覚型スケジューリングMRISを使用する傾向にあるディスク内スケジューラがスループット性能を一層良好に最適化することを可能にする。CSCANキューが大きいほど、該CSCANキューによる要求の空間及び時間に関するクラスタ化が向上する。要求がそのディスクへの送信時に一層緊密にクラスタ化されている場合、これは、回転位置知覚型スケジューラが一回転で多数の要求をサービスするのに一層適したものとなる。図5は、60個の未処理の要求に関する2つの曲線502506を示している。曲線502は、1MBの要求サイズを有する60個の未処理の要求を有している。曲線504は、1MBの要求サイズを有する1個の未処理の要求を有している。曲線506は、4kBの要求サイズを有する60個の未処理の要求を有している。曲線508は、4kBの要求サイズを有する1個の未処理の要求を有している。図5に示すように、CSCANキューサイズが増大すると、ディスクのスループットも増大する。それらに鑑みると、図4及び図5における結果は、スループットを最大にするために、同時並行性の維持とCSCANキューサイズの最大化の両者が重要であることを示している。テストした装置について図示するように、スループットは、同時並行性及びCSCANキューサイズの関数として増大する。しかし、最大約60個の要求の同時並行性は、CSCANキューサイズよりも重要である。このため、記憶装置について60個の同時アクセス要求の平衡数Nを求めることにより同時並行性を最大限にすることは、CSCANキューサイズを最大限にすることよりも高い優先順位が与えられるべきである。作業負荷が増大した際にスループット性能が低下しないこともまた有益である。さもないと、記憶装置は、増大した負荷が性能を低下させるという負のフィードバックサイクルに入ってしまう可能性がある。これは、次いで更なる負荷の増大を生じさせるものとなり得る。この状況を回避すべく、CSCANMRISは、同時並行性を最大限にすることができるべきであり、又は負荷が与えられている場合の最大の同時並行性を少なくとも維持すべきである。この状況で、及び負荷が増大した結果としてキューサイズの増大又は非減少が生じる限り、増大した負荷の下で性能が低下することはない。これらの結果は、同時並行性とCSCANスケジューリングとの両方が、高い同時並行性と大きなCSCANキューとの両方について最適化されたスループット性能に影響を与えることを例証している。しかし、同時並行性は、テストされた記憶装置に著しく大きな影響を与えるものである。このため、スケジューラは、同時並行性及びCSCANキュー深さの何れか一方を選択しなければならない場合には、同時並行性を優先的に維持すべきである。次いで、同時アクセス要求の平衡数Nを求めた後、記憶装置の特徴付けを更に行うために他のパラメータを求めることも可能である。装置の特徴付けはまた、リード対ライト性能を考慮しなければならない。もう1つの装置特徴付けパラメータは、装置の最悪のレイテンシであり、これは、最悪の装置サービスレイテンシ値デルタと表すことが可能なものである。もう1つの装置特徴付けパラメータは、ランダム及びシーケンシャル要求ストリームについてのスループットレート時間である。CRS装置102内の装置特徴付けモジュール106を用いて導出された装置特徴付けパラメータの全てについて以下で一層詳細に説明する。例えば、ディスク自体にキューイングMRISが存在する場合、該MRISは、要求が不足し得るSATF等のMRISとすることが可能である。同様に、該ディスクにおける未処理の平衡数Nの同時要求が存在する場合、CRS装置102内の装置特徴付けモジュール106を用いてそれら要求について最悪のサービス時間を導出することが可能である。CRS装置102内の装置特徴付けモジュール106は、完全な同時並行性を用いて要求サイズのスペクトルにわたり及びCSCANキューサイズにわたり最悪のレイテンシを導出して、その最大値を選択することが可能である。図6は、60個の未処理の要求のために純粋にランダムな要求ストリームを使用して最悪のレイテンシを要求サイズの関数として示したグラフ600であり、該グラフ600には、ディスクの前に大きな4000個の要求のCSCANキューを使用した場合と、該ディスクの前にキューを全く有さない場合との両方が示されている。この最悪の時間は、要求がランダムな順序で与えられる場合CSCANキュー長さ=1に一層短くなる。60個の未処理要求及び4000個の要求のCSCANキューについての最悪のサービス時間は、一定範囲の要求サイズにわたって約1100msで比較的安定しており、これは、下位レベルのスケジューラが、一定のしきい値を有するある種の不足防止antistarvationパラメータ又はその値の近傍に設定された経時agingパラメータを有することを示唆している。最悪の性能が大きなCSCANキューサイズの場合に一般に遙かに悪化するため、及び最悪のレイテンシが複数の要求サイズにわたって比較的安定するため、両方のキューサイズについての16MBの要求サイズでの最大値による約16秒での最悪のレイテンシの推定は、最悪のレイテンシの妥当な推定値となる。最悪のスループットは、一様なランダム要求ストリームが装置に提示されるように空のCSCANキューを使用することを除き、図3の場合と同様の条件で測定される。CRS装置102内の装置特徴付けモジュール106を使用して導出された装置特徴付けパラメータを保持する構成ファイルは、完全な同時並行性を用いた最悪のレイテンシ及び最悪のスループットを要求サイズの関数として格納することが可能である。図7は、CSCANキューサイズ1及び装置における60個の同時要求に関し、ランダム要求ストリームについて要求サイズの関数としてスループットレート時間を示したグラフ700である。最悪のスループットレート時間はCSCANキューサイズ1の場合であり、これは、装置に提示される要求ストリームが最大限にランダム化されているからである。比較のため、図7はまた、CSCANキューが4000個の要求を有する場合のスループットレート時間を示しており、これは、シーク及び回転遅延のオーバーヘッドが総転送コストの大半を占める場合に、CRSアーキテクチャが特に要求が小さい場合に遙かに良好に実施されることを例証している。図8は、シーケンシャル要求ストリーム及びランダム要求ストリームの両方について最悪のスループットレート時間を要求サイズの関数として示していることを除き、上述した図7と同様のグラフ800である。図8に示すように、最悪のスループットレート時間は、ランダム要求ストリームの場合よりも小さくなる。要求サイズが小さい場合、該スループットレート時間は、ランダム要求ストリームの場合よりも大幅に小さくなる。所与の要求について予想されるスループットレート時間値を求める際、CRS装置102内の装置特徴付けモジュール106は、装置が完全な同時並行性平衡したN個の保留中の同時要求を有する場合にスループットMB秒を要求サイズで除算することによりIO秒を得る。但し、ランダム要求ストリームが完全にランダムになるように装置の前にキューは存在しない。ランダム要求についての最悪のスループットレート時間は図7に実線で示されており、シーケンシャル要求の場合は図8に実線で示されている。このため、4kBのランダム要求の場合、記憶装置の最悪のスループットレート時間は、図7に示すように、約04msとなる。4kBのシーケンシャル要求の場合、最悪のスループットレート時間は、図8に示すように、約003msとなる。5.CRSアーキテクチャでキューを管理するMRISCSCAN循環SCANは、周知の効率的なディスクスケジューリングMRISである。ランダム要求ストリームの場合、それは特に記憶装置において位置知覚型スケジューリングMRISと共に階層化アーキテクチャで使用した場合に卓越したフェアネス特性及び最適又はほぼ最適な性能を有するものとなる。CSCANは、MRIS12で示すように、2つのMRISすなわちAdd及びPopを含み、それぞれ、新たに要求をキューに追加し、及び次の要求をスケジューリングする。CSCANは、通常は、一対の順序づけされた一方は現在とラベル付けされ、他方は次とラベル付けされたセットとして実施される。現在のセットは、現在のディスク位置よりも大きなアドレスを有する要求を含み、次のセットは、現在のディスク位置よりも小さなディスク位置を有する要求を含む。現在のディスクヘッド位置及び開始位置へとジャンプする前にディスクの一端から他端へと掃引するオフセットという概念もまた存在する。CSCANMRIS1CSCANに要求を追加1procedureAdd2ifroffsetoffsetthen3nextinsert4else5currinsert6endifCSCANMRIS1は、新しい要求をCSCANキューに追加するためのMRISを示している。本質的に、該要求のアドレスがオフセットよりも小さい場合、該要求は次のスキャンでサービスされる必要があり、このため該要求は次のセットに追加される。そうでない場合には、該要求のアドレスは、現在のヘッド位置と等しいかそれよりも大きく、該要求は、依然として当該スキャンで処理することが可能であり、このため、該要求は現在のセットcurrに追加される。この例では、現在のセット及び次のセットは、バイナリツリーとして実施されるCSTLセットクラスを使用して実施され、このため、挿入、削除、及び最小演算はそれぞれO時間を要し、これは非常に効率的である。この例では、CSCANMRIS1はO時間を要する。CSCANMRIS2CSCANから要求をポップ1procedurePop2ifcurremptythen3Swap4endif5result←currsmallest6currdelete7offset←resultoffset8returnresultCSCANMRIS2は、装置に提示すべき次の要求を選択するためのMRISを示している。最初に、CSCANMRIS2は、現在のスキャンが完了しているか確認し、完了している場合には、現在のセットと次のセットとをスワップして次のスキャンを開始する。次いで現在のスキャンにおける最小の要求を選択して、何らかの基本的なブックキーピング操作を行い、選択された要求を現在のセットから削除し、現在のヘッド位置を更新する。CSCANMRIS2もまた、O時間を要する。2倍の性能改善を生み出すべく、2つの操作currsmallest及びcurrdeleteを単一操作へとマージするように又は少なくともツリー構造の2回目のトラバースを必要としないようにセットデータ構造を実施することが可能である。一様なランダムアクセスストリームとN個の要求を有する閉じたキューモデルとを用いる場合、最悪のサービス遅延の平均は、要求数で測定すると、キュー長さのおよそ2倍すなわち2Nとなる。新しいスキャンが開始された際に、初期のcurrスキャンが空となり、nextがN個の要求を収容する。スワップの後、nextが空となり、currがN個の要求を有する。LCSCAN一例によれば、一次キュー204を管理するためのMRISとして、CSCAN、制限されたCSCAN、又はLCSCANの変異MRISが実施される。LSCANMRISは、最悪のキュー遅延の確実な保証を提供し、及び単一スキャンの潜在的に無制限の期間の不足を生じさせる挙動を回避する。LCSCANキュー204のサイズを制限することが可能であるため、現在のスキャンに新しい要求を追加する前に追加のテストを用いて単一スキャンの長さを制御することが可能である。LCSCANMRIS1制限されたCSCANに要求を追加1procedureAdd2ifroffsetoffsetORcurrsizecountthen3nextinsert4else5currinsert6count7endifLCSCANMRIS1は、新しい要求をキューに追加するための制限されたCSCANMRISである。これは標準的なCSCANMRISとは異なるものである。2行目の標準的なCSCANに関する通常のテストは、ifである。LCSCANは、現在のスキャンに要求を追加することができる回数を制限する第2節currsizecountを追加する。LCSCANから要求が不足するのを防止するのがこの追加の節である。現在のスキャンキューに要求が所定回数だけ追加された後、全ての新しい要求がその位置にかかわらず次のキューに追加されるからである。LCSCANMRIS1における前記回数は、現在のキューに追加される要求のみを追跡するものであり、すなわち、該キューに追加される要求であっても該キューが最新のSwapの前にある次のキューである場合にはその全ての要求を無視する。LCSCANMRIS1は、CSCANMRIS9のように、非常に効率的であり、O時間を要するものである。LCSCANMRIS2制限されたCSCANから要求をポップ1procedurePop2ifcurremptythen3Swap4count←05endif6result←currsmallest7currdelete8offset←resultoffset9returnresultLCSCANMRIS2は、PopMRISのための擬似コードを示しており、これは、標準的なCSCANの場合とは4行目が異なり、この場合には、新しいスキャンを開始する際にカウントがリセットされる。この場合も、LCSCANMRIS2は、CSCANMRIS2と非常に似ており、性能Oを有する。上述したMRISの全てに関する上記計算は、要求の個数に基づくものであり、実際のサービス時間に基づくものではない。要求ストリームが一様な要求サイズを有する場合にはそれら2つの場合は同一となる。しかし、実際には、多数のシステムが異種の要求ストリームを有しており、またアプリケーションは広範な要求サイズを混在して有する可能性がある。この場合、最悪のレイテンシは時間に関して規定することが可能であり、また現在のスキャンに追加することが可能な要求の個数に関する上記計算はスループットレート時間に関して行われる。これを実施すべく、MRISは、キューに関するスループットレート時間の合計の計算を全体として及び各スキャン毎に実行し続ける。該MRISはまた、最新のSwap以降に現在のスキャンに追加されたスループットレート時間の合計を維持しなければならない。要求の個数ベースから時間ベースへと切り換えた場合には、スキャンを終了すべきときを決定するための基準を用いる必要がある。該基準は単調に増加するものである必要はない。例えば、1つの大きな要求を完了させるため及び1つの小さな要求を挿入するために、予想されるサービス時間がスキャン時間しきい値を下回る可能性がある。要求はシーケンシャルとなり得るため、システムに所定の状態パラメータを追加し、これにより、決定が行われた際に、予想されるスキャン時間が所望の限界を超えてしまうため、現在のスキャンに追加されているはずの要求が追加されなかった場合に、他の要求がそのスキャンに追加されるのを防止するフラグをセットすることができるようにする必要がある。LCSCANの時間ベースの変種は、5つの新しい状態パラメータ、すなわち、scan、start、sumcurrent、sumnext、及びclosedを使用することが可能であり、これは、各要求毎の最悪のスループットレート時間の精確な推定値によって決まる。scanは、単一のスキャンが要し得る最大時間量を規定し、startは、現在のスキャンが開始した時刻であり、sumcurrentは、現在のスキャンにおける要求についての予想されるスループットレート時間の合計であり、sumnextは、次のスキャンにおける要求についての予想されるスループットレート時間の合計であり、及びclosedは、新しい要求が現在のスキャンにまだ追加されるか否かを規定するブール代数である。最悪のスループットレート時間の推定値は、上述の記憶装置の評価から導出することが可能である。これは、要求の3つの特性、すなわち、size、readwrite、及びsequentialを考慮するものとなる。ここで、sizeは、バイトを単位とする要求サイズであり、readwriteは、要求がリード要求であるかライト要求であるかを規定し、sequentialは、要求がシーケンシャルであるか否かを規定するブール代数である。一般に、sequentialは、単純なフィルタを使用して求めることが可能であるが、かかる一般的な場合、sequentialは、現在の要求の開始アドレスの直前のバイトをアドレス指定する該現在の要求と同じreadwrite状態を有するキュー内に保留中の要求が存在するか否かを単に記述するものである。LCSCANMRIS3時間ベースの制限されたCSCANに要求を追加1procedureAdd2ifroffsetoffsetANDscanstartsumcurrentthen3closed←true4endif5ifroffsetoffsetORclosedthen6nextinsert7sumnext←sumnextrexpected8else9currinsert10sumcurrent←sumcurrentrexpected11endifLCSCANMRIS3は、制限が時間に関して規定される場合の制限されたCSCANMRISを示している。変数rexpectedは最悪のスループットレート時間として規定することが可能である。LCSCANMRIS1とLCSCANMRIS3との主な違いは、個数ベースのテストを時間ベースのテストに置換したことにあり、及び時間ベースのテストが単純に各挿入時に常に再テストを行うのではなく状態変数を変更するという事実にある。この場合も、LCSCANMRIS3の実行時間はOである。LCSCANMRIS4時間ベースの制限されたCSCANから要求をポップ1procedurePop2ifcurremptythen3Swap4start←now5sumcurrent←sumnext6sumnext←07closed←false8endif9result←currsmallest10currdelete11offset←resultoffset12returnresultLCSCANMRIS2とLCSCANMRIS4との主な違いは、各スキャンの開始時に様々な状態変数をリセットするためのブックキーピングの変更にあり、実行時間は依然としてOである。LSCANは、より長いスキャンでディスク性能を最適化する。CSCANは、可能な限り長いスキャンを生じさせ、スキャンが長い結果として、その性能が卓越したものとなる。リアルタイム優先順位の要求をスケジューリングするための既知のMRISは、単一のスキャンにまとめることができる要求の個数を適宜制限し、これにより、最悪のキュー遅延時間についての一層厳密な保証を提供することが可能となる。しかし、スキャンは一般に、必要とされるものよりも遙かに小さいものであり、その結果として、性能が必要とされるものよりも遙かに悪化することになる。CSchedCSchedは、リアルタイム期限の保証を提供すべく性能上の不利益が最小限であり最適な又はほぼ最適な性能を提供するよう設計されたMRISである。CSchedは、ユーザレベルアプリケーションで実施することが可能である。CSchedはまた、オペレーティングシステム、RAIDディスクコントローラ、又はストレージデバイスもしくはストレージサービスで実施することも可能である。CSchedは、装置の精確な特徴付けに加えて、2つの構成パラメータシグマ、ラムダを利用し、ここで、シグマは、秒を単位とする最大バーストサイズとして定義され、ラムダは、リアルタイム要求についての最小初期スラックタイムとして定義されるものである。次いで、ディスクの特徴付け及びこれらのパラメータが、スケジューラを制御する内部的な構成パラメータへと変換される。シグマは、要求に関して規定されるのではなく時間に関して規定されるという点を除き、リーキーバケットモデルを用いて計算することが可能である、ということに留意されたい。要するに、リーキーバケットモデルは以下のように説明することができる。要求ストリームについての到着関数Rは、期間st内のIO要求の総数である。全期間stについてR≦シグマrhoである場合、要求ストリームは正常に動作している。リーキーバケットモデルについては下記文献に詳細に説明されている:Parekh等のAgeneralizedprocessorsharingapproachtoflowcontrolinintegratedservicesnetworksthesinglenodecaseNetworkingIEEEACMTransactionson13344357、Sariowan等のSchedulingforqualityofserviceguaranteesviaservicecurvesComputerCommunicationsandNetworks1995ProceedingsFourthInternationalConferenceonpp512520、及びGulati等のpClockanarrivalcurvebasedapproachforQoSguaranteesinsharedstoragesystemsACMpp1324。主要な内部的な構成パラメータは、SCANEDF、LCSCAN、及び装置キューの間における利用可能なタイムバジェットであるラムダの割り当てである。装置のタイムバジェットが要求ストリームの最悪のサービス時間のみによって規定されるため、これは、ディスク特徴付けからデルタとして直接取得される。次のブロックは、バーストを吸収するためにSCANEDFキューに割り当てられなければならないタイムバジェットを決定することであり、これは、単に最大のバーストを処理するために必要な時間すなわちシグマである。残りのバジェットはLCSCANキューに割り当てられる。LCSCANキューサイズは、LCSCANキューが満杯であるか否かを判定するためにCSchedが使用するものであり、時間を単位として定義される。MRISCSched1CSchedキューの構成1classCSched2LCSCANlcscan3Schedpending4intnqueues5timetzeta6CSched7zeta←48lcscan←newLCSCAN9pending←newSchednqueues110pending0←newSCANEDF11foriin1nqueuesdo12pendingi←newCSCAN13endforMRISCSched1は、CSchedデータ構造を記述し、及び様々な要素が初期化される態様を示している。MRISCSched2CSchedへの要求の追加1procedureAdd2iflcscanexpectedrexpectedゼータthen3LCSCANisnotfull4lcscanAdd5elseif0rdeadlinethen6realtimerequest7pending0Add8else9besteffortorbackgroundrequest10pendingrpriorityAdd11endifMRISCSched2は、CSchedキューに要求が追加される態様を示している。lcscanexpectedは、lcscansumcurrentlcscansumnextとして計算され、lcscanキュー内に現在保持されている全ての要求についての最悪のスループットレート時間の合計である、という点に留意されたい。第1に、LCSCANキューへの要求の追加が、該LCSCANキューをその時間に関して指定された許容サイズを超えさせるものでない場合には、該要求はLCSCANキューに単純に追加される。そうでない場合には、該要求は適当な保留中のキューリアルタイム要求の場合にはSCANEDF、ベストエフォート及びバックグランド要求の場合にはCSCANに追加される。このコードは一般的なものであり、それらの非リアルタイム要求については他の任意のスケジューリングシステムを使用することが可能である、ということに留意されたい。MRISCSched3CSchedからの要求のポップ1procedurePop2result←lcscanPop3fori0tonqueuesdo4ifpendingi¬emptythen5r←pendingiHead6iflcscanexpectedrexpected≧ゼータthen7LCSCANisnowfull8break9endif10r←pendingiPop11lcscanAdd12endif13endfor14returnresultMRISCSched3は、記憶装置へ提示するために要求をキューから除去する際に生じることを示している。第1に、MRISCSched3は、2行目で次の要求をLCSCANキューから除去する。該LCSCANキューからの要求の除去は、保留中のキューからの要求を追加する余地があることを意味し得るものであるため、システムは、各保留中のキューを繰り返しチェックし、リアルタイムSCANEDFキューから開始して要求を探す。LCSCANキューに要求を追加する余地がある限り、この処理は行われる。LCSCANキューが満杯となり又は保留中のキューが空になるや否や、この処理は停止する。6行目のテストは、上記MRISCSched2の2行目と同じであることに留意されたい。また、5行目は、実際に要求を除去することなくキューからポップされるべき次の要求を単に返すものである。これは、上記MRISCSched1の9行目の行rcurrsmallestとほぼ等価である。ほぼ60の同時並行性を用いて実質的に最適な性能が得られるため図3参照、システムは、キューに入れられた要求が存在する限り、最大限の同時並行性を維持する。また、装置の前に大きなCSCAN又はLCSCANキューを有することにより性能が改善されるため図5参照、LCSCANキューサイズを最大限にすることが求められる。しかし、最悪のキュー遅延がバジェットを超えないことを確実にすべく、このキューサイズを制限することが求められる。制限されたCSCAN、LCSCAN、スケジューラの役割は、1低レベルの位置知覚型のスケジューラがその要求の再順序付け能力を一層良好に利用してスループットを最大限にすることができるように要求を最適な態様又はほぼ最適な態様で装置へ提示すること、及び2全体としてのソリューションによりリアルタイム保証を提供することが可能となるように最悪のスケジューリング遅延が制限されることを確実にすることである。SCANEDFSCANEDFキューは、バーストを吸収して、リアルタイム保証を提供すべくLSCANキューのサイズを制限することを可能にする。FIFO又はEDFキューではなくSCANEDFを使用する理由は、特に集中的なbursty作業負荷に関して潜在的に改善された性能にある。期限に関して順序通りに提示されないこともまた、リアルタイム要求にとって有用である。例えば、作業負荷は、非常に集中的なものとなる130ms毎に新たな複数のデータバッチが必要となる傾向にあり、この場合、1つのバッチは、ディスクアドレスに関してランダムな順序で記憶装置に提示される数千もの多数の小さな要求を含み得るものである。この場合、各バッチでのSCANの使用は、全体的なスループットを最大化することが可能となるように要求が部分的に最適化された態様でLCSCANキューへ送られることを意味している。SCANEDFは、サイズ自体は制限されないが、作業負荷の特徴付けが精確に行われていることを前提としたものであり、このため、一例によれば、SCANEDFは、シグマよりも多くの要求を保持することはなく又は要求に関連する期間よりも大きくなることはなく、SCANEDFキュー内の要求に生じる最悪のキュー遅延は、シグマexpectedであり、ここで、expectedは、要求ストリームについての予想される最悪のスループットレート時間である。CSCANスケジューラ複数のCSCANスケジューラは、LCSCANキュー内に利用可能な余地が存在するまで非リアルタイム要求を保持する。要求は、これらのキューから優先順位順に渡され、例えば、バックグランド要求は、リアルタイムSCANEDF及びベストエフォートCSCANキューの両者が空である場合に限り、バックグランドCSCANキューからLCSCANキューへと渡されることになる。代替的なアーキテクチャを利用することが可能であると共に潜在的に有用であり、かかる代替的なアーキテクチャの一例が、Gulati等のpClockanarrivalcurvebasedapproachforQoSguaranteesinsharedstoragesystemsProceedingsofthe2007ACMSIGMETRICSinternationalconferenceonMeasurementandmodelingofcomputersystemACMpp1324で開示されているpClockである。更に、他の適当な既知のアーキテクチャを使用して様々な非リアルタイムストリームからLCSCANキューへの要求の提示を制御することが可能である。6.結果CSchedMRISの性能は、CSchedが徒過した期限を有さずCSCANがリアルタイム保証を提供しないことを除き、CSCANの性能と類似している。CSchedMRISの性能は、2つの高い作業負荷条件すなわち、様々な作業負荷を有する一様且つランダムなリアルタイム要求ストリームと一様且つランダム又はシーケンシャルなベストエフォート要求ストリーム下でテストされる。該リアルタイム要求ストリーム及び該ベストエフォート要求ストリームの両者が一様且つランダムである場合、全体的な性能が最小となり、一方、シーケンシャルなベストエフォート要求ストリームは、フェアネスの観点からCSCANのために最も敵対的な要求ストリームを提供する。多くのベストエフォート作業負荷は、一様且つランダムな要求と一様且つシーケンシャルな要求とを混合したものである。このため、実際の性能は、それら2つの作業負荷の中間となる傾向にある。アプリケーションの作業負荷は、一様且つランダムなリアルタイム要求ストリームおよび一様且つランダムなベストエフォート要求ストリームを有する場合に特徴付けを行うことが可能である。しかし、通常は、一様な4kBサイズではなく、複数の要求サイズが混在する。図9は、標準的なCSCANキューを使用する場合にリアルタイムデータレート要件の関数として2つの作業負荷についてのスループットを示すグラフ900である。その第1の作業負荷は、リアルタイム要求及びベストエフォート要求の両者についての一様且つランダムな要求パターンであり、第2の作業負荷は、リアルタイム要求に関する一様且つランダムな要求パターンとベストエフォート要求についてのシーケンシャルパターンである。リアルタイム要求ストリームは滑らかなものとなる。リアルタイム要求は、30秒の初期スラックタイムを有し、CSchedは、SCANEDFに割り当てられる0秒と、装置の最悪の場合に割り当てられる14秒と、LSCANについての残りの286秒の最大レイテンシとを用いて構成される。留意すべきは、一様且つランダムな作業負荷についての性能がリアルタイム要求負荷に対して不変である、ということである。この曲線がリアルタイムデータレートに関して平坦であり、及びその値がこのワークフローについて観察されたほぼ最適な値図5の点線の曲線の最も右側のポイントと一致する、という事実は、CSchedがこの作業負荷について装置上でほぼ最適な達成可能な性能を得ることを実証するものである。予想通り、リアルタイム要求の割合が増大すると、シーケンシャルなベストエフォート要求ストリームを用いた総システムスループットが低下する。これは、利用可能なリソースの増大していく比率をリアルタイム要求が吸収するからである。しかし、その2つの曲線すなわち点線の曲線及び鎖線の曲線は、それぞれリアルタイム保証がある場合とない場合のほぼ最適な性能を表しており、これは、CSchedが他の高い作業負荷についてもほぼ最適なスループットを得ることを実証するものである。装置で同時要求を許可しない複数のリアルタイムディスクスケジューリングMRISの何れか又はその全てとの比較のため図5を参照されたい。同図は、様々な構成で単一の未処理要求を用いるシステムについての相対的な性能を例証する曲線すなわち曲線504508対60個の同時要求を用いるシステムについての相対的な性能を例証する曲線すなわち曲線502506を示している。作業負荷が4kBの要求を使用した場合、図5の一番下の実線の曲線508上の最も左のデータポイントにより、同じハードウェア構成で、EDFが08MBs未満を達成すること及びCSchedが約22MBsを達成することが予想されることを容易に理解することができる。同様に、同時要求に適合しないディスクスケジューリングMRISの上限は、たったの約14MBs曲線508上の最も右側のデータポイントの値であり、これは、装置の前にある1つの大きな効率的なキューを表している。1MBの要求ストリームに関して鎖線の曲線から同様の所見を述べることが可能である。EDFは、約100MBs該曲線の最も左側のポイントを提供し、一方、同時要求を許可しない最も効率的なリアルタイムディスクスケジューラは、約140MBs該曲線の最も右側のポイントに達し得ると思われる。CSchedは典型的には、同じ要求ストリームを用いて同じハードウェア上で約420MBs鎖線の曲線の最も右側のポイントに達する。上述のように、標準的なCSCANスケジューラのフェアネスは、要求ストリームが一層シーケンシャルになり及び一層ランダムでなくなるにつれて損なわれる。図10は、LCSCANキューの必要性を例証するグラフ1000であり、ベストエフォート要求ストリームがシーケンシャルである場合に要求の期限を徒過するリアルタイム要求の一部を示している。リアルタイム要求レートが低い場合には、ベストエフォート要求がCSCANキューに高速で入り続け、このため、各スキャンが、他のアドレスで切望しているリアルタイム要求のサービスへと進む前に、該シーケンシャルのベストエフォート要求について過度の量の時間を費やすことになる。図11は、図9と類似したグラフであるが、滑らかなリアルタイム要求ストリームを有するのではなく集中的な要求ストリームを有する点で異なり、この場合には、一度に5秒のバーストサイズに相当するリアルタイム要求を有する。テストハードウェア上で4kBのランダムなリアルタイム要求について予想される最悪のスループットレート時間が039msexpected000039であり及び所望のリアルタイムデータレートがXMBsである場合には、所与の1つのバーストにおける要求の個数は、シグマと等価な5000039であり、これは、12820個の要求または53MBのキャッシュと等価であり、4kBの要求についてのバースト到着間レートburstinterarrivalrateは4096シグマ1000000Xである。X=1MBsである場合には、バースト到着間レートは525秒である。この性能は図9に示したものと同様である。このため、システムがバーストを扱うよう設計されている限り、性能はリアルタイム要求ストリームのバースト性に対して比較的不変となる。上記計算は、最悪のスループットレート時間データを使用して行われ、これは、予想されるスループットレート時間図7参照とは実質的に異なり得るものである。最悪のスループットレート時間を用いたシステムのスループットは約105MBsであり、数千ものキューイングされた要求を用いた該システムの予想されるスループットは、おおよそ22MBSである。ラムダが増大するにつれて、初期スラックタイムの一層大きな部分が最悪の装置サービス時間に割り当てられて、LCSCANキューに割り当てられるレイテンシが残り少なくなる。これは、LCSCANキューのサイズが小さくなって性能に悪影響を与えることを示唆している。リアルタイム作業負荷が非常に集中的なものである場合、すなわち、シグマが大きい場合には、LCSCANキューから更なる時間が取られることになる。これは、ある方法により対処することが可能であり、該方法は、リアルタイム要求が、最も最近追加された非リアルタイム要求をLCSCANキューから先制的に除去してそれらを保持スタックにプッシュすることを可能とすることによりSCANEDFキューをなくす、というものである。LCSCANキュー上に空きが出来次第、前記保持スタック上の要求がLCSCANキューに再び追加され、これにより非リアルタイム要求間のフェアネスがほぼ維持される。もう1つの方法は、最小初期スラックタイム値ラムダが、複数の異なる優先順位のアクセス要求の作業負荷に対する予想される将来の変化に関連する信号に応じて再決定され得る動的なパラメータである場合である。この方法では、再決定される最小初期スラックタイム値ラムダは、複数の異なる優先順位のアクセス要求の作業負荷に対する予想される将来の変化に関連する信号に応じて記憶装置及び作業負荷の特徴付けから得られた少なくとも1つの値に基づいて決定される。図12は、一例による図1に示したスケジューリング装置100を使用して増大する最小初期スラックタイム値ラムダの関数としてスループットが変化する態様を例証するグラフ1200である。図12に示すように、スループットはラムダと共に変化し、この場合、一定のリアルタイムデータレートは95MBS、シグマ=0s、及びデルタ=14sである。ラムダが増大する1530とき、これはゼータが増大する01286ことも意味する。ゼータが増大し、その結果としてLCSCANキューサイズが増大するとき、性能は改善し、これは、上述の図4に示した結果と一致し、すなわち、スケジューリングキューのサイズを増大させることによりディスク性能が改善する。図13は、一例による図1に示したスケジューリング装置100を使用して等価条件下でベストエフォート要求と共にリアルタイム要求をスケジューリングする場合にランダムまたはシーケンシャルな要求の条件下で改善されるスループットを例証するグラフ1300である。図13は、図9に類似しているが、スケジューラCDSSCANが如何に挙動するかも示している点で異なる。CDSSCANについては、Staelin等のRealtimediskschedulingMRISallowingconcurrentIOrequestsTechRepHPL2009244HewlettPackardLaboratoriesOct2009に記載されている。リアルタイム要求が存在しない場合にはCSched及びCDSSCANの性能が同様となるが、これと比較して、ランダムなベストエフォート要求ストリームについてのCDSSCANの性能が低下する一方、CSchedの性能が一定に維持されることに留意されたい。また、リアルタイムレートが増大するにつれてシーケンシャルなベストエフォートストリームについてのCDSSCANの性能がCSchedの性能よりも一層急激に低下する態様について留意されたい。7.CRS装置及びCRS方法本書で開示されるのは、同時要求スケジューリングCRSを管理するための方法及び装置である。図1を参照すると、一例によるCRSシステム100の簡素化されたブロック図が示されている。図1は、一般化された実施形態を表すものであり、該CRSシステム100の範囲から逸脱することなく他の構成要素を追加することまたは図示の複数の構成要素を省略し、変更し、または再配置することが可能である、ということが当業者には自明である。CRSシステム100は、CRS装置102、プロセッサ120、入力装置130、出力インタフェイス140、及びデータ記憶装置118を含むものとして示されている。該プロセッサ120は、CRS装置102を実施し及び/又は実行するためのものである。このため、例えば、CRSシステム100をコンピューティング装置から構成することが可能であり、及びCRS装置102を該コンピューティング装置の一体型またはアドオン型のハードウェア装置から構成することが可能である。別の一例として、CRS装置102は、コンピュータにより読み取ることが可能な記憶装置図示せずとし、該記憶装置上にプロセッサ120が実行すべきコンピュータプログラムを格納することが可能である。図1に更に示すように、プロセッサ120は、入力インタフェイス130からの入力を受信する。該入力インタフェイス130は、例えば、ユーザがデータにアクセスすること、例えば、データ記憶装置118に格納されている要求、オブジェクト、MRIS、アプリケーション等にアクセスすることを可能にするユーザインタフェイスから構成することが可能である。追加的にまたは代替的に、ユーザは、入力インタフェイス130を介してデータ記憶装置118にデータを供給し及び/又は該データ記憶装置118に以前に格納されたデータを更新することが可能である。入力インタフェイス130はまた、データ記憶装置118に格納されているデータに出力インタフェイス140を介して出力された際にユーザがアクセスすることを可能にするユーザインタフェイスを構成することが可能である。一例によれば、CRS装置102は、データ記憶装置118等のメモリに格納されているアクセス要求を処理することになる。該アクセス要求は、リアルタイム優先順位を有するアクセス要求や、ベストエフォート要求及び/又はバックグランド要求等の一層低い優先順位の要求を含む、様々な優先順位のアクセス要求の作業負荷内に存在する。一例によれば、データ記憶装置118は、バッテリーバックアップ式のランダムアクセスメモリRAM、相変化RAMPCRAM、及びメモリスタといった、不揮発性バイトアドレス指定可能メモリから構成することが可能である。追加的または代替的に、データ記憶装置118は、リムーバブルPCRAM装置といった外部リムーバブルメディアに対してリード/ライトする装置から構成することが可能である。データ記憶装置118は、データ構造管理システム100の内部のもの又は該システム100に取り付けられたものとして示したが、該データ記憶装置118は、CRSシステム100から遠隔地に配置することが可能であることが理解されよう。この例では、CRSシステム100は、インターネット等のネットワーク接続を介してデータ記憶装置118にアクセスすることが可能である。図1に更に示すように、CRS装置102は、ユーザインタフェイスモジュール104、装置特徴付けモジュール106、作業負荷特徴付けモジュール108、CRS処理モジュール110、及び更新モジュール112を含む。該モジュール104112は、MRISコードモジュール、ハードウェアモジュール、又はMRIS及びハードウェアモジュールの組み合わせから構成することが可能である。このため、一例では、モジュール104112は、複数の回路要素から構成することが可能である。もう1つの例では、モジュール104112は、コンピュータ読み取り可能記憶媒体上に格納された、プロセッサ120が実行することになるコードから構成することが可能である。このため、一例では、CRS装置102は、コンピュータ、サーバ、回路といったハードウェア装置からなる。別の例では、CRS装置102は、モジュール104112の機能を実行するためのMRISコードが格納されたコンピュータ読み取り可能記憶媒体からなる。CRS装置102が実行する様々な機能について以下で詳細に説明する。一例によれば、CRS装置102は、所定のCRS方法を実施するものとなる。CRS装置102のモジュール104112を実施することが可能な様々な態様を図14及び図15に関して一層詳細に説明する。図14及び図15は、CRSを実行するための方法1400,1500のフローチャートを示している。当業者には自明であるように、該方法14001500は、一般化された実施形態を表したものであり、該方法14001500の範囲から逸脱することなく、本開示以外のブロックを追加し、又は本開示のブロックを削除し、変更し、若しくは再配置することが可能である。方法14001500についての説明は、図1に示すCRS装置102及び図2に示すCRSアーキテクチャ図200を特に参照して行うが、該方法14001500は、該方法の範囲から逸脱することなく、CRS装置102及びCRSアーキテクチャ200とは異なる装置で実施することが可能である、ということが理解されよう。先ず図14を参照すると、ブロック1402で、記憶装置の特徴付けが装置特徴付けモジュール106を使用して実行される。一例では、記憶装置の特徴付けは、同時アクセス要求の平衡数Nの決定を含む。図15の方法1500を参照すると、ブロック1502で、記憶装置の特徴付けは、同時アクセス要求の平衡数N、最悪の装置サービスレイテンシ値デルタ、及び最悪の最大スループットレート時間1IOPS値タウの決定を含む。タウに関する値は、リード/ライト、ランダム/シーケンシャル、及び要求サイズに関する値、並びに随意選択的にその他の値に少なくとも関連し得る関数となる。ブロック1404は、ブロック1402の記憶装置に関連するアクセス要求の作業負荷に応じて実施することが可能である。先ず図14の方法1400を参照すると、作業負荷の特徴付けが作業負荷特徴付けモジュール108を使用して実行される。一例では、作業負荷の特徴付けに関して任意の作業負荷の特徴付けパラメータを特徴付けることが可能である。図15の方法1500を参照すると、ブロック1504で、作業負荷の特徴付けは、最小初期スラックタイム値ラムダ、バースト性値シグマ、及び最悪のキュー遅延値ゼータによる決定を含む。この例によれば、ゼータは、作業負荷の特徴自体ではなく、CRSアーキテクチャ200に関して導出されるパラメータである。図14のブロック1406は、リアルタイムアクセス要求を受信することが可能であるという信号又は指示がアクセス要求記憶場所値を有することに応じて実施することが可能である。図15のブロック1506もまた、リアルタイムアクセス要求を受信することが可能であるという信号又は指示がアクセス要求記憶場所値を有することに応じて実施することが可能である。両方のブロック14061506は、CRS更新モジュール112を使用して実施することが可能である。図14のブロック1408は、アクセス要求記憶場所値と共にリアルタイムアクセス要求を受信することに応じて実施することが可能である。図15のブロック1508もまた、アクセス要求記憶場所値と共にリアルタイムアクセス要求を受信することに応じて実施することが可能である。ブロック14081508は、該アクセス要求記憶場所値並びにそれ以前のブロックで取得された記憶装置及び作業負荷を特徴付けるパラメータに基づくリアルタイムアクセス要求の処理を含む。ブロック14081508は、CRS処理モジュール110を使用して実施することが可能である。図示した上述の処理の一部又は全部は、ユーティリティ、プログラム、又はサブプログラムとして、あらゆる所望のコンピュータ読み取り可能記憶媒体に格納することが可能である。更に、該処理は、アクティブ又は非アクティブの両方の様々な形態で存在することができるコンピュータプログラムにより実施することが可能である。例えば、該処理は、ソースコード、オブジェクトコード、実行可能コード、又はその他の形態のプログラム命令からなる1つ又は2つ以上のMRISプログラムとして存在することが可能である。上記の何れも、記憶装置を含むコンピュータ読み取り可能記憶媒体上で実施することが可能である。コンピュータ読み取り可能記憶媒体の一例として、従来のコンピュータシステムRAM、ROM、EPROM、EEPROM、及び磁気又は光学ディスク又はテープが挙げられる。上記の具体例には、CDROM又はインターネットによるダウンロードを介したプログラムの配布が含まれる。よって、上記機能を実行することができる任意の電子的な装置は、上記で列挙した機能を実施することが可能なものとなる、ということが理解されよう。8.CRS方法、装置、コンピュータ読み取り可能媒体のためのプラットフォームここで図16を参照すると、図14及び図15に示した方法又は該方法に関連するコードを実施し又は実行するためのプラットフォームとして採用することが可能なコンピューティング装置1600が示されている。該コンピューティング装置1600の例示は一般化されたものであり、該コンピューティング装置1600は更なる構成要素を含むことが可能であり、該コンピューティング装置1600の範囲から逸脱することなく本開示の構成要素の幾つかを削除し及び/又は修正することが可能である、ということが理解されよう。該コンピューティング装置1600は、中央処理装置等のプロセッサ1602、モニタ等の表示装置1604、ローカルエリアネットワークLAN、ワイヤレス80211xLAN、3GモバイルWAN、又はWiMAXWAN等のネットワークインタフェイス1608、及びコンピュータ読み取り可能媒体1610を含む。これらの構成要素の各々は、バス1612に動作可能な状態で接続することが可能である。例えば、該バス1612は、EISA、PCI、USB、FireWire、NuBus、又はPDSとすることが可能である。コンピュータ読み取り可能媒体1610は、命令をその実行のためにプロセッサ1602へ提供することに関与するあらゆる適当な媒体とすることが可能である。例えば、コンピュータ読み取り可能媒体1610は、光又は磁気ディスク等の不揮発性媒体、メモリ等の揮発性媒体、並びに同軸ケーブル、導線、及び光ファイバ等の伝送媒体とすることが可能である。伝送媒体は、音響、光、又は電波といった形態を採ることが可能である。コンピュータ読み取り可能媒体1610はまた、ワードプロセッサ、ブラウザ、電子メール、インスタントメッセンジャ、メディアプレーヤ、及び電話MRISを含む、他のMRISアプリケーションを格納することが可能である。コンピュータ読み取り可能媒体1610はまた、MacOS、MSWindows、Unix、又はLinux等のオペレーティングシステム1614、ネットワークアプリケーション1616、及びデータ構造管理アプリケーション1618を格納することが可能である。オペレーティングシステム1614は、マルチユーザ、マルチプロセス、マルチタスク、マルチスレッド、リアルタイム等をサポートするものとすることが可能である。オペレーティングシステム1614はまた、キーボード又はキーパッド等の入力装置からの入力の認識、表示装置1604及び設計ツール1606への出力、媒体1610上のファイル及びディレクトリの追跡、ディスクドライブ、プリンタ、及びイメージキャプチャ装置等の周辺機器の制御、並びにバス1612上のトラフィックの管理といった基本タスクを実行することが可能である。ネットワークアプリケーション1616は、TCPIP、HTTP、Ethernet、及びFireWireを含む通信プロトコルを実施するためのMRISといったネットワーク接続を確立し維持するための様々なコンポーネントを含む。データ構造管理アプリケーション1618は、上述したような不揮発性メモリのためのCRSアーキテクチャ200等のCRSアーキテクチャを構築/更新するための様々なMRISコンポーネントを提供する。特定の例では、アプリケーション1618により実行される処理の一部又は全部をオペレーティングシステム1614に統合させることが可能である。特定の例では、該処理は、少なくとも部分的に、ディジタル電子回路、コンピュータハードウェア、ファームウェア、MRIS、又はそれらの任意の組み合わせにおいて実施することが可能である。本開示の全体を通して具体的に説明してきたが、例示した実施形態は、広範な用途にわたって有用性を有するものであり、上記説明は、制限を意図したものではなく、及び制限的なものと解釈すべきではない。本書で用いた用語、説明、及び図面は、例示のみを目的として提示したものであり、制限を意味するものではない。本開示の例の思想及び範囲内で多数の変形例が実施可能であることが当業者には認識されよう。複数の例に関して説明を行ってきたが、当業者であれば、特許請求の範囲に記載するような実施形態及びそれと等価なものの範囲から逸脱することなく本開示の例に対して様々な修正を加えることが可能である。"