(57)【特許請求の範囲】
【請求項１】
リアルタイム優先順位を有するアクセス要求を含む複数の異なる優先順位を有する複数のアクセス要求の処理に係る作業負荷を有する記憶装置のためのストレージアクセススケジューリング方法であって、
同時要求スケジューリング（ＣＲＳ）装置の装置特徴付けモジュールによって該記憶装置を特徴付けし、該記憶装置の特徴付けが、該記憶装置の性能に関する少なくとも１つの装置パラメータを決定することを含み、該少なくとも１つの装置パラメータの該決定が、該記憶装置の性能に関する許容可能な最悪のサービス時間を有する同時アクセス最大スループットに関する同時アクセス要求の平衡数を決定することを含み、
前記同時要求スケジューリング装置の作業負荷特徴付けモジュールによって前記作業負荷を特徴付けし、該作業負荷の該特徴付けが、最小初期スラックタイム値、バースト性値、及び最悪のキュー遅延値からなる複数の作業負荷パラメータのうちの少なくとも１つの作業負荷パラメータを決定することを含み、
前記同時要求スケジューリング装置のＣＲＳ更新モジュールによって所定のアクセス要求記憶場所値に関連付けられたリアルタイム優先順位を有するアクセス要求（以下「リアルタイムアクセス要求」と称す）を受信し、
前記同時要求スケジューリング装置のＣＲＳ処理モジュールによって前記アクセス要求記憶場所値並びに前記決定された少なくとも１つの装置パラメータ及び前記決定された少なくとも１つの作業負荷パラメータに基づいて前記リアルタイムアクセス要求を処理する、
という各ステップを含む、ストレージアクセススケジューリング方法。
【請求項２】
少なくとも１つの装置パラメータを決定する前記ステップが、同時アクセス要求の平衡数(N)に基づいて最悪の装置サービスレイテンシ値を決定するステップを更に含む、請求項１に記載の方法。
【請求項３】
少なくとも１つの装置パラメータを決定する前記ステップが、前記同時アクセス要求の平衡数の処理に関する最悪の最大スループットレート時間値を決定するステップを更に含む、請求項１又は請求項２に記載の方法。
【請求項４】
前記決定された値が時間に基づくものである、請求項１ないし請求項３の何れか一項に記載の方法。
【請求項５】
前記最小初期スラックタイム値が、リアルタイム優先順位を有するアクセス要求についての最悪の総サービスアクセス時間に関する時間値であり、
前記バースト性値が、リアルタイム優先順位を有するアクセス要求のバースト性に関する時間値であり、及び
前記最悪のキュー遅延値が、一次キューを介した前記アクセス要求の処理に関する時間値である、
請求項１ないし請求項４の何れか一項に記載の方法。
【請求項６】
前記リアルタイムアクセス要求を処理する前記ステップが、
リアルタイムアクセス要求のみを保持する保留キューに前記リアルタイムアクセス要求を入れ、
リアルタイムアクセス要求のみを保持する前記保留キューから前記リアルタイムアクセス要求を取り出し、
該リアルタイムアクセス要求を一次キューに入れる、
という各ステップを含む、請求項１ないし請求項５の何れか一項に記載の方法。
【請求項７】
前記決定されたバースト性値が、リアルタイムアクセス要求のみを保持する前記保留キューに関連付けられる、請求項６に記載の方法。
【請求項８】
前記決定された最小初期スラックタイム値が、前記バースト性値、前記最悪のキュー遅延値、及び前記最悪の装置サービスレイテンシ値の間で割り当てられる、
請求項５に記載の方法。
【請求項９】
前記一次キューが、リアルタイムアクセス要求のみを保持する前記保留キューからの要求を受け入れることに加えて、リアルタイム優先順位よりも低い優先順位の少なくとも１つの保留キューからリアルタイム優先順位よりも低い優先順位のアクセス要求を受け入れる、請求項６に記載の方法。
【請求項１０】
前記リアルタイムアクセス要求を処理する前記ステップが、
リアルタイム優先順位よりも低い優先順位のアクセス要求が前記一次キューに割り当てられた場合、
該一次キューに対するリアルタイムアクセス要求の割り当てに応じて該一次キューから以前に割り当てられたリアルタイム優先順位よりも低い優先順位のアクセス要求を取り出す、
という各ステップを含む、請求項９に記載の方法。
【請求項１１】
前記最小初期スラックタイム値が、複数の異なる優先順位を有する複数のアクセス要求の処理に係る作業負荷に対する予想される将来の変化に関する信号に応じて再決定される動的なパラメータである、請求項１ないし請求項１０の何れか一項に記載の方法。
【請求項１２】
前記再決定される最小初期スラックタイム値が、複数の異なる優先順位を有する複数のアクセス要求の処理に係る作業負荷に対する予想される将来の変化に関する信号に応じて前記記憶装置及び前記作業負荷の特徴付けから取得された少なくとも１つの値に基づいて決定される、請求項１１に記載の方法。
【請求項１３】
リアルタイム優先順位を有するアクセス要求を含む複数の異なる優先順位を有する複数のアクセス要求の処理に係る作業負荷を有する記憶装置のためのストレージアクセススケジューリングを実行するための装置であって、
プロセッサを備えており、該プロセッサが、
前記記憶装置の性能に関する少なくとも１つの装置パラメータを決定することにより該記憶装置の特徴付けを行う装置特徴付けモジュールであって、該少なくとも１つの装置パラメータの該決定が、前記記憶装置の性能に関する許容可能な最悪のサービス時間を有する同時アクセス最大スループットに関する同時アクセス要求の平衡数を決定することを含む、装置特徴付けモジュールと、
最小初期スラックタイム値、バースト性値、及び最悪のキュー遅延値からなる複数の作業負荷パラメータのうちの少なくとも１つの作業負荷パラメータを決定することにより該作業負荷の特徴付けを行う作業負荷特徴付けモジュールと、
同時要求スケジューリング（ＣＲＳ）処理モジュールであって、所定のアクセス要求記憶場所値に関連付けられたリアルタイム優先順位を有するアクセス要求（以下「リアルタイムアクセス要求」と称す）を受信し、該アクセス要求記憶場所値並びに前記決定された少なくとも１つの装置パラメータ及び前記決定された少なくとも１つの作業負荷パラメータに基づいて該リアルタイムアクセス要求を処理する、同時要求スケジューリング（ＣＲＳ）処理モジュールと
を動作させる、記憶装置のためのストレージアクセススケジューリングを実行するための装置。
【請求項１４】
コンピュータシステムによる実行時にリアルタイム優先順位を有するアクセス要求を含む複数の異なる優先順位を有する複数のアクセス要求の処理に係る作業負荷を有する記憶装置のためのストレージアクセススケジューリングを実行するコードを含むコンピュータ読み取り可能命令を格納した持続性コンピュータ読み取り可能媒体であって、該コンピュータ読み取り可能命令が、
前記記憶装置の性能に関する少なくとも１つの装置パラメータを決定することにより該記憶装置の特徴付けを行い、該少なくとも１つの装置パラメータの該決定が、前記記憶装置の性能に関する同時アクセス最大スループットに関する同時アクセス要求の最小数を決定することを含み、
最小初期スラックタイム値、バースト性値、及び最悪のキュー遅延値からなる複数の作業負荷パラメータのうちの少なくとも１つの作業負荷パラメータを決定することにより該作業負荷の特徴付けを行い、
所定のアクセス要求記憶場所値に関連付けられたリアルタイム優先順位を有するアクセス要求（以下「リアルタイムアクセス要求と称す」）を受信し、
該アクセス要求記憶場所値並びに前記決定された少なくとも１つの装置パラメータ及び前記決定された少なくとも１つの作業負荷パラメータに基づいてプロセッサを使用して前記リアルタイムアクセス要求を処理する、
という各ステップを実行するためのコードを含む、持続性コンピュータ読み取り可能媒体。 
【発明の詳細な説明】
【背景技術】
【０００１】
ディスクスケジューラは、入出力（I/O）データのための保留中のディスクアクセス要求のキューを管理し、該要求を記憶装置へ提示する時期及び順序を決定する。典型的には、複数のアクセス要求は、複数のアプリケーションからの進行中のストリームでプロセッサに到達する。該複数のアクセス要求は典型的には、記憶装置内の記憶場所に関連付けされた複数の論理ブロックへとアドレス指定される。随意選択的に、ディスクアクセス要求は優先順位値を含む。ディスクアクセス要求はまた、ディスクアクセス要求の処理を完了させなければならないときを指定する期限を含む。
【０００２】
スケジューラは、平均総サービス時間を最小限にし、及び総システムスループットを最大限にしようとすることが多い。更に、期限を有するディスクアクセス要求が存在する場合、スケジューラはまた、かかる要求の全てをそれらの期限までに確実に完了させようとする。総サービス時間とは、プロセッサでアクセス要求を受信してから記憶装置の内外へのデータ転送が完了するまでに要する時間である。総システムスループットとは、記憶装置の内外へのデータの平均転送速度に関するものである。総サービス時間は、要求がスケジューラのキュー内で待機して費やした時間の関数となる。総サービス時間はまた、I/OヘッドとI/Oデータに割り当てられたブロックに関連付けられたディスク位置とを隔てるシーク及び回転距離を含む装置機構の関数となる。総サービス時間はまた、ディスクの内外へデータを送信するための時間を含む。
【０００３】
スケジューラは、１グループの要求におけるブロックのサービス間のシーク及び回転遅延を最小限にするように該ブロックの位置に従って該要求を編成することにより、該１グループの要求についての総サービス時間を最小限にしようとすることが多い。単純なスケジューラは、論理的なブロック位置による増大するシーケンスに従ってブロックを編成することが多い。単純な処理環境は、同レベルの優先順位を有するアクセス要求しか含まないことが多い。しかし、ディスクアクセス要求は異なる優先順位を有し得るものである。一般的なタイプの優先順位の１つが、割り当てられた優先順を殆ど有さず又は全く有さないバックグランドタイプ要求である。それらは、スケジューラ内で一層高レベルの優先順位を有する要求（ベストエフォート優先順位要求など）と組み合わせられることが多い。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
異なる優先順位タイプが同時に処理される場合、記憶装置上で一層高い優先順位の要求が処理されている間にスケジューラが一層低い優先順位の要求を該記憶装置へ送ることができないのであれば、記憶装置の全体的なスループット性能は低下し得る。この種の環境は、システムスループットに劇的な悪影響を与える結果となることが多い。
【０００５】
リアルタイムアクセス要求は、ベストエフォート又はバックグランド優先順位要求よりも高い優先順位を有する。一層低レベルの優先順位の要求とのリアルタイムアクセス要求の同時処理は、環境によっては特に厄介なものとなる。合併症（スターべーション（starvation）など）の可能性は一層深刻なものとなり、これは、リアルタイムディスク要求が通常は何らかのレベルの保証されたほぼ即座のI/Oデータのアクセスに関するものであるからである。かかる保証を満足させようとして、スケジューラは典型的には、総システム効率及びスループットに更なる制約を課す。更に、保証されたアクセス期限を守れず又は該アクセス期限に間に合わないことが、リアルタイムアクセス要求に関する別の種類の問題である。これら問題の全ては、リアルタイムアクセス要求のスケジューリングに関するものである。これらの問題は、リアルタイム要求と一層低い優先順位の要求とが混合したものの一部としてリアルタイムアクセス要求をスケジューリングする場合に一層悪化することが多い。
【図面の簡単な説明】
【０００６】
【図１】本開示の一実施形態によるスケジューリング装置を示すブロック図である。
【図２】図１に示すスケジューリング装置で動作することができる本開示の一実施形態によるスケジューリングアーキテクチャを示すアーキテクチャ図である。
【図３】本開示の一実施形態による記憶装置に関する同時要求の最大平衡数（N）の決定を例証するグラフである。
【図４】本開示の一実施形態による記憶装置に関する同時要求の実質的に最適な最大数（N）の決定の有効性と該記憶装置のスループットを例証するグラフである。
【図５】本開示の一実施形態による記憶装置に関するキューサイズとスループットとの関係を例証するグラフである。
【図６】本開示の一実施形態による記憶装置に関する最悪の（worst-case）レイテンシと要求サイズとの関係を例証するグラフである。
【図７】本開示の一実施形態によるランダム要求に関する平均要求サイズの関数としてのスループットレート時間の決定を例証するグラフである。
【図８】本開示の一実施形態によるシーケンシャル要求の関数として及びランダム要求に関する平均要求サイズの関数としての最悪のスループットレート時間の決定を例証するグラフである。
【図９】本開示の一実施形態による図１に示すスケジューリング装置を用いた等価条件下での24MB/sよりも高い改善されたスループットを例証するグラフである。
【図１０】リアルタイム要求に関する改善された期限徒過比を例証するグラフであり、同図に示すように、本開示の一実施形態による図１に示すスケジューリング装置を用いた等価条件下でL-CSCANはゼロ期限徒過比を有している。
【図１１】本開示の一実施形態による図１に示すスケジューリング装置を用いた等価条件下で20MB/sよりも高い改善されたスループットを例証するグラフである。
【図１２】本開示の一実施形態による図１に示すスケジューリング装置を用いて増大する最小初期スラックタイム値（ラムダ）の関数としてスループットが変化する態様を例証するグラフである。
【図１３】本開示の一実施形態による図１に示すスケジューリング装置を用いて等価条件下でベストエフォート要求と共にリアルタイム要求をスケジューリングする際のランダム要求条件又はシーケンシャル要求条件下での改善されたスループットを例証するグラフである。
【図１４】本開示の一実施形態によるスケジューリング方法を示すフローチャートである。
【図１５】本開示の一実施形態による図１４に示すスケジューリング方法よりも一層詳細なスケジューリング方法を示すフローチャートである。
【図１６】本開示の一実施形態による図１に示すスケジューリング装置のためのハードウェアプラットフォームを提供するコンピュータシステムを示すブロック図である。
【発明を実施するための形態】
【０００７】
単純化及び例示のため、本開示は主にその実施形態を参照することにより説明を行う。以下の記述では、本開示の十分な理解を提供すべく様々な特定の細部について説明する。しかし、本開示は、かかる特定の細部に限定することなく実施することが可能である、ということが容易に理解されよう。別の例では、本開示の説明が不必要に不明瞭なものとならぬよう幾つかの方法及び構造については詳細に説明していない。別の例では、本開示が不必要に曖昧とならぬよう幾つかの方法及び構造については詳細に説明していない。本書で用いる場合、用語「含む」とは、含むことを意味するがそれに限定されるものではなく、用語「含んでいる」とは、含んでいることを意味するがそれに限定されるものではない。用語「に基づき」とは、少なくとも部分的に基づくことを意味する。
１．概説
本書で開示するのは、リアルタイムアクセス要求を含む様々な優先順位のアクセス要求の作業負荷を有する記憶装置のための記憶装置アクセスのスケジューリングのための方法、装置、及びコンピュータ読み取り可能媒体である。本開示は、混合型作業負荷におけるリアルタイムアクセス要求に関する保証されたアクセスの最悪の総サービス時間を成功裏に満たす一方で記憶装置の高レベルのスループット性能を維持することに伴う問題に対処するものである。
【０００８】
本開示は、広範な動作条件にわたって実質的に最適となるスループットを提供する。本開示は、記憶装置及び該記憶装置に関する作業負荷を特徴付ける少なくとも１つのパラメータを利用する。かかるパラメータを記述するデータは、動作中に動的に更新することが可能である。計算上の観点からすると、マシン読み取り可能命令は非常に効率的であり、及びO(log(n))型マシン読み取り可能命令（nは要求に関するキューのサイズ）を用いて実施することが可能である。該マシン読み取り可能命令は、比較的単純であり、及び非常に少数行のコードを用いて実施することが可能であり、このため、実施した命令の確認を一層低い複雑性で行うことが可能となる。
２．定義
本書で用いる場合、用語「アクセス要求」は、記憶装置に関するIOデータを取り出し又は提供するために記憶装置へ送られるディジタル命令である。該データの記憶アドレスは、該命令の一部とすることが可能である。プロセッサは、該命令をデコードする際に、要求された情報を読み出し及び/又は格納することができる場所の記憶アドレスを取得する。本書で用いる場合、用語「アクセス要求」は用語「要求」と置換可能に使用される。
【０００９】
本書で用いる場合、用語「同時アクセス要求の平衡数（N）」は、記憶装置を特徴付けるパラメータである。該同時アクセス要求の平衡数（N）は、該装置のスループットに対して総未処理I/Oをプロットすることにより導出することが可能である。図３に関して以下で一層詳細に説明するように、導出されたプロット中の膝領域が、同時アクセス要求の平衡数（N）である。この決定により、許容可能な最悪のサービス時間を有する最大スループット性能を有するポイントＮが見い出される。これは、Ｎの関数としてのスループット性能が平坦になる曲線の膝部分で一般に生じる。
【００１０】
本書で用いる場合、用語「バースト性（burstiness）値」は、作業負荷におけるリアルタイム要求のバースト性に関する計数又は期間といった値である。
【００１１】
本書で用いる場合、用語「同時アクセス最大スループット」は、平均要求サイズでの同時アクセス要求の平衡数（N）に関するスループットである。
【００１２】
本書で用いる場合、用語「マシン読み取り可能命令セット（MRIS）」は、アルゴリズム、プログラム、コード、ソフトウェア等といった、マシンにより読み取ることが可能な一組のディジタル命令である。
【００１３】
本書で用いる場合、用語「最悪の最大スループットレート時間（1/IOPS）」は、一次キューを介した同時アクセス要求の平衡数（N）の処理に関する時間値である。タウ（tau）に関する値は、リード／ライト、ランダム／シーケンシャル、及び要求サイズ（及び随意選択的にその他の値）のための値に少なくとも関連することが可能な関数である。以下で定義するスループットレート時間も参照されたい。
【００１４】
本書で用いる場合、用語「記憶装置」は、記憶装置、磁気テープ、ディスク等といったコンピュータ機器の１つであり、又はデータ及び命令を（通常はバイナリ形式で）格納することができる関連する複数のコンピュータ機器の組み合わせである。
【００１５】
本書で用いる場合、用語「最小初期スラックタイム値（ラムダ）」は、リアルタイムアクセス要求のための保留キュー、一次キュー、及びブラックボックス装置キューを介してＣＲＳアーキテクチャでリアルタイムアクセス要求を通過させるための総処理時間に関する時間値である。
【００１６】
本書で用いる場合、用語「保留キュー」は、アクセス要求に関する特徴（アクセス優先順位レベルなど）に基づいて追加されたアクセス要求を保持するキューである。該保留キュー中のアクセス要求は、他のキュー（一次キューなど）に割り当てられるのを該保留キュー内で待機し、該他のキューに割り当てられた後、記憶装置に関する記憶場所へのI/Oアクセスのために処理されることになる。
【００１７】
本書で用いる場合、用語「一次キュー」は、記憶装置への直接アクセスが認められたものとして追加されたアクセス要求を保持するキューであり、該一次キュー内のアクセス要求は、記憶装置に関する記憶場所に対するI/Oアクセスのために該記憶装置に関する内部的なブラックボックスキューを介して割り当てられて処理されるのを待機する。
【００１８】
本書で用いる場合、用語「リアルタイム優先順位」は、記憶装置でのサービスのためにリアルタイムアクセス要求を処理するための期限が関連付けられた該リアルタイムアクセス要求に対して割り当てられる高い優先順位である。
【００１９】
本書で用いる場合、用語「SCAN」は、ディスクに対する多数のアクセスをスケジューリングするためのマシン読み取り可能命令セット（MRIS）であり、MRISとも呼ばれる。多数の要求が、記憶装置上のデータの位置に従って順序づけされる。これにより、最悪の場合にディスク全体にわたる１回のスキャン又は掃引のためのディスクアームの運動が低減される。サービス時間は、ディスクのトラック間シークタイム、最大シークタイム（１回のスキャン）、及び最大回転レイテンシから推定することができる。
【００２０】
本書で用いる場合、用語「記憶場所」は、記憶装置内のディスク上にデータを格納することができる場所を識別する論理アドレスその他の場所決定因子である。
【００２１】
本書で用いる場合、用語「スループットレート時間」は、各要求の完了間の平均時間であり、IOPS（１秒あたりのI/O）の逆数として定義することができる。スループットレート時間は、そのアーキテクチャの並行処理のため、一要求の平均サービス時間の代わりに利用される。要求のための期待されるリソース要件としてスループットレート時間を使用することにより、ストレージデバイス又は記憶装置の利用のために総和（summation）を介して一層単純で一層精確な計算（accounting）が可能となる。
【００２２】
本書で用いる場合、用語「最悪の総サービスアクセス時間」は、経過することができる最長期間であり、その経過後には、リアルタイムアクセス要求は、そのリアルタイムサービス期限を徒過する前に記憶装置でサービスされなければならない。
【００２３】
本書で用いる場合、用語「最悪の装置サービスレイテンシ値（デルタ）」は、記憶装置内に内部的なブラックボックスキューを含む該記憶装置に関するブラックボックス構成での総サービス時間に関する時間値である。
【００２４】
本書で用いる場合、用語「最悪のキュー遅延値（ゼータ）」は、CRSアーキテクチャでの一次キューを介した要求の処理に関する時間値である。ゼータは、本質的には作業負荷の特徴ではなく、CRSアーキテクチャ200等のCRSアーキテクチャに関して導出されるパラメータである。
３．CRSアーキテクチャ
図１を参照すると、図２に示すCRSアーキテクチャ200等のCRSアーキテクチャを実施するための例証となる同時要求スケジューリング（CRS）システム100の実施形態を単純化したブロック図が示されている。以下、CRSシステム100について一層詳細に説明する。CRSアーキテクチャ200では、一例によれば、機能及び優先順位レベルに従って相関する複数のキュー202-210が存在する。以下で一層詳細に説明するように、CRSアーキテクチャ200において該キュー202-210にパラメータを関連付けることも可能である。
【００２５】
CRSアーキテクチャ200は、記憶装置及びそのオペレーティングシステムの直前に従来の内部的なブラックボックスキュー202を含む。該ブラックボックスキュー202に先行して一次キュー204が存在する。この例では、該一次キュー204は、L-CSCANなるラベルが付されたスケジューリングのためにマシン読み取り可能命令セット（MRIS）を利用する。以下で一層詳細に説明するように、L-CSCAN（制限された（Limited）CSCAN又はLCSCANとも呼ばれる）は、循環スキャン（CSCAN）と題する周知のMRISの変種である。
【００２６】
L-CSCANは、最悪のキュー遅延保証を提供するようサイズが制限された一次キュー204を管理する。一次キュー204は、リアルタイム、ベストエフォート、及びバックグランドといった優先順位レベルのアクセス要求を含む異なる優先順位レベルを有する複数のアクセス要求を含むことが可能である。これらの異なる優先順位の要求は、性能の最適化のために一次キュー204内でソートされる。
【００２７】
図２において、一次キュー204の左側には、リアルタイム要求のための保留キュー206が存在する。この例では、保留キュー206は、SCAN-EDF（すなわち SCAN-Eearliest Deadline First：最も古い期限を最初にスキャン）と題するMRISを使用して、一次キュー202に入れられるのを待っているリアルタイム優先順位の要求を管理する。また、CRSアーキテクチャ200では、ベストエフォート優先順位の要求のための保留キュー208は、CSCANと題するMRISにより管理されるバックグランド優先順位レベルの要求は、一次キュー204に入れることもまだ入れないことも可能なものであり、この例では、保留キュー210内に保持される。
【００２８】
CRSアーキテクチャ200以外のリアルタイム要求なしの代替的なアーキテクチャでは、該代替的なアーキテクチャは、単純に、要求を記憶装置内に供給して該記憶装置に複数の同時要求の一定のプールを保持するCSCANキューのみとすることが可能である。この種の代替的なアーキテクチャをリアルタイム保証を提供するように変更し又は拡張させるのは困難である。第１に、CSCANキューの最悪のキュー遅延は、通常はCSCANキュー長さの約２倍となり、このため、CSCANキューの長さを制限すべきである。これは、該最悪のキュー遅延が、記憶装置の最悪のレイテンシよりも小さい最小初期スラックタイムよりも一般に小さくなるようにするということである。しかし、CSCANの最悪の挙動は、本質的に制限のないものである。この種の無制限の最悪の挙動を回避するために、CRSアーキテクチャ200は、以下で一層詳細に説明するように、CSCAN,L-CSCANの変種を使用する。第２に、CSCANキューサイズが制限されると、該CSCANキューへ未だ送ることができない過度の要求を吸収するために、該制限されたCSCANキューの前に保留キューが存在する可能性がある。CRSアーキテクチャ200は、リアルタイム要求及びその他の優先順位の要求のためにL-CSCANを使用する。このため、リアルタイム要求のための保留キュー206は、効率的で期限に感応するMRISとしてSCAN-EDFを使用して、リアルタイム要求のみを保持する該保留キュー206を管理する。非リアルタイム要求のための保留キューは効率的なものとすることが可能である。このため、この例によれば、CRSアーキテクチャ200は、ベストエフォート優先順位を有する要求を保持するCSCAN保留キュー208を使用する。第３に、リアルタイム要求の場合、CSCANキュー208のサイズは、リアルタイム要求がSCAN-EDFキュー206内で費やすことが可能な最大時間を構成するよう削減することが可能である。このSCAN-EDFキュー206のサイズの削減は、要求ストリームのバースト性の関数とすることが可能である。
【００２９】
CRSアーキテクチャ200は、様々な他の例に従って変更することが可能である。例えば、CRSアーキテクチャ200は、単一のベストエフォートCSCANキュー208をFahhradlikeキューシステムに置換して、複数の装置にわたるベストエフォート要求ストリームのフェアネスを確保することが可能である。L-CSCANは、そのフェアネス特性が故に、また複数の下位レベルスケジューラと十分に対話してほぼ最適な全体的なシステム性能を生み出すため、CSCANに基づくものである。しかし、最悪のキュー遅延が保証され又は要求の期限が満たされる限り、他のMRISスケジューリングプログラムをCRSアーキテクチャ200で使用して一次キュー204を管理することが可能である。かかる制限に達すると、新たな要求は、記憶装置内でスキャンされるディスク上の該要求の位置にかかわらず、次のスキャンにスケジューリングされる。
【００３０】
図２はまた、リアルタイム期限を確実に守るべくCRSアーキテクチャ200におけるキュー202-210の最悪の挙動を計算し制御する方法を例証するものである。CRSアーキテクチャ200は、互いに接続された複数のキューのパイプラインとして設計されているため、該パイプラインの各キューは別個に、SCAN-EDFキュー206、L-CSCAN一次キュー204、並びにOS及び装置キュー202とみなすことが可能である。CRSアーキテクチャ200では、任意の内部的なOSスケジューラ、任意の内部的なRAIDコントローラ、及び任意の内部的な記憶装置スケジューラの組み合わせは全て、ブラックボックスキュー202に関連する単一のブラックボックス装置として取り扱われる。
【００３１】
一例によれば、CRSアーキテクチャ200においてリアルタイム保証を提供するための第１の方法は、キュー202における記憶装置の性能の特徴付けを行うことである。この記憶装置の性能の特徴付けは、該記憶装置の最悪のレイテンシ及び最悪のスループットレート時間を実験データに基づいて予測するためのモデルを含むことが可能である。該最悪のスループットレート時間は、所与の並行処理レベルで所与のサイズの要求を処理する際の最悪の１秒あたりのIO動作の逆数として定義することが可能である。
【００３２】
記憶装置の特徴付けの一要素は、L-CSCANキュー204として図２に示す一次キュー204に関係する。L-CSCAN MRISは、最悪のL-CSCANキュー待機時間（ゼータ）214が一次キュー204の長さの関数となるように設計することが可能である。次に考慮すべき事柄は、所与のL-CSCAN一次キュー204の長さについての最悪の装置完了時間の決定である。CRSアーキテクチャ200の目標は、全てのリアルタイム要求が確実にその期限を守ってL-CSCANキュー204に入ることにあり、該CRSアーキテクチャ200は、現在L-CSCANキュー204内にある要求についての時間割当量に追加の時間を許容して、該時間割当量内にリアルタイム要求のための余地を作るべきである。
【００３３】
換言すれば、最悪の総予測時間（ラムダ）218は、図２で例証した３つの時間割当量アイテム、すなわち、記憶装置における最悪の時間（デルタ）212、L-CSCANキュー内で待機している最悪の時間（ゼータ）214、及びL-CSCANキュー204に入るためにSCAN-EDFキュー内で待機している最悪の時間（シグマ）216を含むことが可能である。
【００３４】
記憶装置における最悪の時間（デルタ）212は、一定また所与の値とすることが可能であり、その制御ポイントは、L-CSCANキュー204のサイズとすることが可能である。次いでこれは、L-CSCANキューにおける最悪の時間（ゼータ）214を支配することが可能である。このため、最大サイズのL-CSCANキュー204は、該L-CSCANキュー204に入るために待機しているSCAN-EDFキュー206内のリアルタイム要求にとって利用可能となる時間割当量（すなわち最悪の予測時間（シグマ）216）を制御することが可能である。該L-CSCANキューにおける最悪の時間（ゼータ）214は、一次キュー204内の要求の個数及び／又は該要求がL-CSCAN MRISにより管理されているレートの関数とすることが可能である。
【００３５】
CRSアーキテクチャ200におけるリアルタイム作業負荷のバースト性または可変性は、最悪の総予測時間（ラムダ）218のシグマ216に対する時間割当量の割り当てに影響を与え得るものである。１つの方法は、バースト性を測定すること、もう１つの方法はバースト性を宣言するために要求を生成するアプリケーションを有することとし得る。L-CSCANキュー（ゼータ）214で費やした時間と同様に、リアルタイム要求がSCAN-EDFキュー（シグマ）216中で費やした時間は、SCAN-EDFキュー206の長さ及び最悪のスループットレートの関数とすることが可能である。
【００３６】
SCAN-EDFキュー206の目的は、バースト（bursts）を吸収すること、及びL-CSCANキュー204へリアルタイム要求を提出することが可能となるまで該リアルタイム要求を保持することにある。これは、L-CSCANキュー204が大きくなり過ぎるのを防止し、ひいてはL-CSCANキュー204内で待機している要求が飢餓状態となって（starving）その期限を徒過することが防止される。SCAN-EDFキュー206を使用することにより、リアルタイム要求をその期限に従ってL-CSCANキュー204へ提出することが確実となる。SCAN-EDFキュー206の使用はまた、スキャン順に反して提出されたリアルタイム要求がその期限を徒過しない可能性を低減させる。代替的な方法では、要求のサイズの可変性を考慮することが可能である。この方法では、要求は、その最悪のスループットレートに関して定義される。この場合には、LCSCAN待機時間（ゼータ）214及びSCAN-EDF待機時間（シグマ）216は、それらが保持することができる要求の個数ではなく時間に関して定義することが可能である。
４．記憶装置の特徴付け
以下の例では、様々な実例の結果を提示する。これらの結果は、２つのデュアルコアIntel プロセッサ及び4GBのRAMを有しWINDOWS SERVER 2008を実行しているHP DL360サーバ上で生成されたものである。性能テストに使用したストレージアレイは、８つの146GB（15k RPM）のSASディスクからなり、HP P410i ストレージコントローラに対して２つのSCSIケーブルで（各ケーブルに４つのディスクが）取り付けられている。該ストレージは、128kBストライプ及び1.1TBの総利用可能サイズを有するRAID0に構成されていた。これらの例で使用されたMRISは、ファイルシステムを使用するのではなく、使用される装置に直接アクセスし、また、スレッド処理及び非同期I/O能力を使用して、前記装置へ複数のI/Oを一度に送信する。
【００３７】
特に示さない限り、ベンチマークは、一様なランダムディスクアドレスによる閉ループ環境を使用した。通常、装置への送信を待機する4000のベストエフォート読み出し要求がキュー内に存在し、使用した装置は60の同時要求を受け付ける。リアルタイム要求は通常は、30秒の初期スラックタイムを有し、及びディスクアドレスの一様なランダムな分布を使用する。それらの期限は、所与の要求サイズについて所望のスループットレートを適合させるよう時間的に一様に隔置された。先行するリアルタイム要求についてのサービスの完了の有無又は該サービスの実行態様にかかわらず、前記30秒の初期スラックタイムを確保する必要がある場合に新たなリアルタイム要求がキューに追加された。また、RAIDコントローラの書き込みバッファキャッシュ及びSCSIディスクの即時書き込み報告から得られる性能の向上を除外するために読み出し専用要求ストリームを使用した。
【００３８】
リアルタイム保証を提供するために、一例によれば、まず最初に記憶装置の特徴付けを行わなければならない。同時並行性、要求のサイズ、及び要求の逐次性といった、装置性能に影響を与え得る複数のパラーメータが存在する。オペレーティングシステム内のディスクスケジューラ、RAIDコントローラ内のディスクスケジューラ及び書き込みキャッシュ、並びにディスク自体のディスクスケジューラといった、互いに協働する複数の装置が潜在的に存在するという事実により、実際の記憶装置の精確な特徴付けの実行は複雑なものとなる。その個々の装置が記憶装置を構成することが可能であり、又はそれら装置の任意の組み合わせが記憶装置を構成することが可能である。所与の記憶装置に関する複数のパラメータの特徴付けを行う場合、その各パラメータ毎に該記憶装置の複数の同じ構成要素の特徴付けを行うことが可能である。
【００３９】
リアルタイム要求が所与のアプリケーションにより記憶装置へ送信されたとき、未処理のリアルタイム要求が時間内に完了することを確実にするために該アプリケーションが行わなければならない制御は、該記憶装置に対する更なる要求を許可しないことにより、サービスすべき代替的な要求を装置間スケジューラから不足させることである。同時並行性を常に最大限にすること又は性能を最大限にすることが望ましい。これは、リアルタイム要求が少なくとも最悪の予測サービス時間よりも前にほぼ常に完了するように、該リアルタイム要求を十分に事前に装置へ提示すべきことを意味している。そうでない場合には、期限を徒過する危険性のあるリアルタイム要求を装置が完了させるまで同時並行性を確保し該装置から要求を不足させる必要がある。
【００４０】
図３は、２つの例示的な要求サイズ4kB及び1MBについて装置における要求の同時並行性の関数としてスループットを示すグラフ300である。この例は、ディスクアドレスの一様なランダム分布を用いて4000個の要求について閉ループシステムを用いて完了させ、及びCSCANキューを介して送ったものである。図３で例証されるように、同時並行性の要求を使用することには大きな性能上の利益が存在する。
【００４１】
図３は、記憶装置を特徴付けるパラメータとしての同時アクセス要求の平衡数（N）の決定を例証している。該同時アクセス要求の平衡数（N）は、以下で一層詳細に説明するCRS装置102内の装置特徴付けモジュール106を使用して導出することが可能である。該パラメータは、スループットに対する未処理のI/Oをプロットすることにより導出することが可能である。
【００４２】
図３に示すように、この例の記憶装置の場合、同時並行性に関連する利益は、約60個の同時要求についての該プロットされた曲線の膝領域に達するものである。この導出されたプロットにおける膝領域は、同時アクセス要求の平衡数（N）である。この決定により、最大スループット性能に関するポイントNがまた、許容可能な最悪のサービス時間を有することが見いだされる。通常の環境下では、これは、Ｉ/Oの個数の関数としてのスループット性能が平坦になる曲線の膝領域で生じる。図３に示すように、この例の決定では、60個の同時要求が、4kB〜1MBの要求サイズの範囲にわたり記憶装置について一貫したものとなる。以下の例では、記憶装置についてのデフォルトのテスト済みの同時並行性が、該記憶装置の特徴付けに関連する他のパラメータを決定するため、60個の同時アクセス要求が平衡数（N）として使用される。
【００４３】
図４は、記憶装置についての要求サイズの関数として総スループットを例証するグラフ400である。そのデータは図４に示す２つの曲線について生成されている。一方の曲線は、記憶装置において一度につき様々なサイズの単一要求が存在する例（すなわち、テストされた同時並行性：１）を示している。他方の曲線は、記憶装置において一度につき60個の同時要求が存在する例（すなわち、テストされた同時並行性：60）を示している。この２つの曲線は、利用可能な同時並行性を利用することによる利益が1kB−16MBの範囲の要求サイズにわたって一貫して大きなものとなることを例証している。
【００４４】
図５は、テストされた記憶装置に関し、CSCANキューサイズの大きさの関数としてスループット性能が如何に変化するかを例証したグラフ500である。該CSCANキューは、シークタイムを最小限にするよう複数の要求を並べ換える。該CSCANキューはまた、装置上で空間的に隣接している複数の要求を時間的に一層近くで処理する。これは、一般に、（位置知覚型スケジューリングMRISを使用する傾向にある）ディスク内スケジューラがスループット性能を一層良好に最適化することを可能にする。
【００４５】
CSCANキューが大きいほど、該CSCANキューによる要求の空間及び時間に関するクラスタ化が向上する。要求がそのディスクへの送信時に一層緊密にクラスタ化されている場合、これは、回転位置知覚型スケジューラが一回転で多数の要求をサービスするのに一層適したものとなる。図５は、60個の未処理の要求に関する２つの曲線502,506を示している。曲線502は、1MBの要求サイズを有する60個の未処理の要求を有している。曲線504は、1MBの要求サイズを有する1個の未処理の要求を有している。曲線506は、4kBの要求サイズを有する60個の未処理の要求を有している。曲線508は、4kBの要求サイズを有する1個の未処理の要求を有している。図５に示すように、CSCANキューサイズが増大すると、ディスクのスループットも増大する。
【００４６】
それらに鑑みると、図４及び図５における結果は、スループットを最大にするために、同時並行性の維持とCSCANキューサイズの最大化の両者が重要であることを示している。テストした装置について図示するように、スループットは、同時並行性及びCSCANキューサイズの関数として増大する。しかし、最大約60個の要求の同時並行性は、CSCANキューサイズよりも重要である。このため、記憶装置について60個の同時アクセス要求の平衡数（N）を求めることにより同時並行性を最大限にすることは、CSCANキューサイズを最大限にすることよりも高い優先順位が与えられるべきである。
【００４７】
作業負荷が増大した際にスループット性能が低下しないこともまた有益である。さもないと、記憶装置は、増大した負荷が性能を低下させるという負のフィードバックサイクルに入ってしまう可能性がある。これは、次いで更なる負荷の増大を生じさせるものとなり得る。この状況を回避すべく、CSCAN MRIS は、同時並行性を最大限にすることができるべきであり、又は負荷が与えられている場合の最大の同時並行性を少なくとも維持すべきである。この状況で、及び負荷が増大した結果としてキューサイズの増大又は非減少が生じる限り、増大した負荷の下で性能が低下することはない。
【００４８】
これらの結果は、同時並行性とCSCANスケジューリングとの両方が、高い同時並行性と大きなCSCANキューとの両方について最適化されたスループット性能に影響を与えることを例証している。しかし、同時並行性は、テストされた記憶装置に著しく大きな影響を与えるものである。このため、スケジューラは、同時並行性及びCSCANキュー深さの何れか一方を選択しなければならない場合には、同時並行性を優先的に維持すべきである。
【００４９】
次いで、同時アクセス要求の平衡数（N）を求めた後、記憶装置の特徴付けを更に行うために他のパラメータを求めることも可能である。装置の特徴付けはまた、リード対ライト性能を考慮しなければならない。もう１つの装置特徴付けパラメータは、装置の最悪のレイテンシであり、これは、最悪の装置サービスレイテンシ値（デルタ）と表すことが可能なものである。もう１つの装置特徴付けパラメータは、ランダム及びシーケンシャル要求ストリームについてのスループットレート時間である。CRS装置102内の装置特徴付けモジュール106を用いて導出された装置特徴付けパラメータの全てについて以下で一層詳細に説明する。
【００５０】
例えば、ディスク自体にキューイングMRISが存在する場合、該MRISは、要求が不足し得るSATF等のMRISとすることが可能である。同様に、該ディスクにおける未処理の平衡数Nの同時要求が存在する場合、CRS装置102内の装置特徴付けモジュール106を用いてそれら要求について最悪のサービス時間を導出することが可能である。CRS装置102内の装置特徴付けモジュール106は、完全な同時並行性を用いて要求サイズのスペクトルにわたり及びCSCANキューサイズにわたり最悪のレイテンシを導出して、その最大値を選択することが可能である。
【００５１】
図６は、60個の未処理の要求のために純粋にランダムな要求ストリームを使用して最悪のレイテンシを要求サイズの関数として示したグラフ600であり、該グラフ600には、ディスクの前に大きな4000個の要求のCSCANキューを使用した場合と、該ディスクの前にキューを全く有さない場合との両方が示されている。この最悪の時間は、要求がランダムな順序で与えられる場合（CSCANキュー長さ＝1）に一層短くなる。60個の未処理要求及び4000個の要求のCSCANキューについての最悪のサービス時間は、一定範囲の要求サイズにわたって約1100msで比較的安定しており、これは、下位レベルのスケジューラが、一定のしきい値を有するある種の不足防止（anti-starvation）パラメータ又はその値の近傍に設定された経時（aging）パラメータを有することを示唆している。最悪の性能が大きなCSCANキューサイズの場合に一般に遙かに悪化するため、及び最悪のレイテンシが複数の要求サイズにわたって比較的安定するため、両方のキューサイズについての16MBの要求サイズでの最大値による約1.6秒での最悪のレイテンシの推定は、最悪のレイテンシの妥当な推定値となる。
【００５２】
最悪のスループットは、一様なランダム要求ストリームが装置に提示されるように空のCSCANキューを使用することを除き、図３の場合と同様の条件で測定される。CRS装置102内の装置特徴付けモジュール106を使用して導出された装置特徴付けパラメータを保持する構成ファイルは、完全な同時並行性を用いた最悪のレイテンシ及び最悪のスループットを要求サイズの関数として格納することが可能である。
【００５３】
図７は、CSCANキューサイズ１及び装置における60個の同時要求に関し、ランダム要求ストリームについて要求サイズの関数としてスループットレート時間を示したグラフ700である。最悪のスループットレート時間はCSCANキューサイズ１の場合であり、これは、装置に提示される要求ストリームが最大限にランダム化されているからである。
【００５４】
比較のため、図７はまた、CSCANキューが4000個の要求を有する場合のスループットレート時間を示しており、これは、シーク及び回転遅延のオーバーヘッドが総転送コストの大半を占める場合に、CRSアーキテクチャが（特に要求が小さい場合に）遙かに良好に実施されることを例証している。
【００５５】
図８は、シーケンシャル要求ストリーム及びランダム要求ストリームの両方について最悪のスループットレート時間を要求サイズの関数として示していることを除き、上述した図７と同様のグラフ800である。図８に示すように、最悪のスループットレート時間は、ランダム要求ストリームの場合よりも小さくなる。要求サイズが小さい場合、該スループットレート時間は、ランダム要求ストリームの場合よりも大幅に小さくなる。
【００５６】
所与の要求について予想されるスループットレート時間値を求める際、CRS装置102内の装置特徴付けモジュール106は、装置が完全な同時並行性（平衡したN個の保留中の同時要求）を有する場合にスループット（MB/秒）を要求サイズで除算することによりIO/秒を得る。但し、ランダム要求ストリームが完全にランダムになるように装置の前にキューは存在しない。ランダム要求についての最悪のスループットレート時間は図７に実線で示されており、シーケンシャル要求の場合は図８に実線で示されている。このため、4kBのランダム要求の場合、記憶装置の最悪のスループットレート時間は、図７に示すように、約0.4msとなる。4kBのシーケンシャル要求の場合、最悪のスループットレート時間は、図８に示すように、約0.03msとなる。
５．CRSアーキテクチャでキューを管理するMRIS
CSCAN
循環SCANは、周知の効率的なディスクスケジューリングMRISである。ランダム要求ストリームの場合、それは（特に記憶装置において位置知覚型スケジューリングMRISと共に階層化アーキテクチャで使用した場合に）卓越したフェアネス特性及び最適又はほぼ最適な性能を有するものとなる。CSCANは、MRIS 1,2 で示すように、２つのMRIS（すなわちAdd 及び Pop）を含み、それぞれ、新たに要求をキューに追加し、及び次の要求をスケジューリングする。
【００５７】
CSCANは、通常は、一対の順序づけされた（一方は「現在」とラベル付けされ、他方は「次」とラベル付けされた）セットとして実施される。現在のセットは、現在のディスク位置よりも大きなアドレスを有する要求を含み、次のセットは、現在のディスク位置よりも小さなディスク位置を有する要求を含む。現在のディスクヘッド位置及び（開始位置へとジャンプする前にディスクの一端から他端へと掃引する）オフセットという概念もまた存在する。
【００５８】
CSCAN MRIS 1. CSCAN に要求を追加
1: procedure Add(Request r)
2: if r.offset < offset then
3:                  next.insert(r)
4: else
5:                  curr.insert(r)
6: end if
CSCAN MRIS 1 は、新しい要求をCSCANキューに追加するためのMRISを示している。本質的に、該要求のアドレスがオフセットよりも小さい場合、該要求は次のスキャンでサービスされる必要があり、このため該要求は次のセットに追加される。そうでない場合には、該要求のアドレスは、現在のヘッド位置と等しいかそれよりも大きく、該要求は、依然として当該スキャンで処理することが可能であり、このため、該要求は現在のセットcurrに追加される。この例では、現在のセット及び次のセットは、バイナリツリーとして実施される C++  STL セットクラスを使用して実施され、このため、挿入、削除、及び最小演算はそれぞれO(log(n))時間を要し、これは非常に効率的である。この例では、CSCAN MRIS 1 は O(log(n))時間を要する。
【００５９】
CSCAN MRIS 2. CSCAN から要求をポップ
1: procedure Pop() 
2: if curr.empty() then
3:                  Swap(curr, next)
4: end if
5: result ← curr.smallest()
6: curr.delete(result) 
7: offset ← result.offset
8: return result
CSCAN MRIS 2 は、装置に提示すべき次の要求を選択するためのMRISを示している。最初に、CSCAN MRIS 2 は、現在のスキャンが完了しているか確認し、完了している場合には、現在のセットと次のセットとをスワップして次のスキャンを開始する。次いで現在のスキャンにおける最小の要求を選択して、何らかの基本的なブックキーピング操作を行い、選択された要求を現在のセットから削除し、現在のヘッド位置を更新する。CSCAN MRIS 2 もまた、O(log(n))時間を要する。
【００６０】
２倍の性能改善を生み出すべく、２つの操作curr.smallest()及びcurr.delete()を単一操作へとマージするように又は少なくともツリー構造の２回目のトラバースを必要としないようにセットデータ構造を実施することが可能である。一様なランダムアクセスストリームとN個の要求を有する閉じたキューモデルとを用いる場合、最悪のサービス遅延の平均は、要求数で測定すると、キュー長さのおよそ２倍すなわち2Nとなる。新しいスキャンが開始された際に、初期のcurrスキャンが空となり、nextがN個の要求を収容する。スワップの後、nextが空となり、currがN個の要求を有する。
LCSCAN
一例によれば、一次キュー204を管理するためのMRISとして、CSCAN、制限されたCSCAN、又はL-CSCANの変異MRISが実施される。L-SCAN MRISは、最悪のキュー遅延の確実な保証を提供し、及び単一スキャンの潜在的に無制限の期間の不足を生じさせる挙動を回避する。L-CSCANキュー204のサイズを制限することが可能であるため、現在のスキャンに新しい要求を追加する前に追加のテストを用いて単一スキャンの長さを制御することが可能である。
【００６１】
L-CSCAN MRIS 1. 制限されたCSCAN に要求を追加
1: procedure Add(Request r)
2: if r.offset < offset OR curr.size() < count then
3:                  next.insert(r)
4: else
5: curr.insert(r)
6: count++
7: end if
L-CSCAN MRIS 1 は、新しい要求をキューに追加するための制限されたCSCAN MRISである。これは標準的なCSCAN MRISとは異なるものである。２行目の標準的なCSCANに関する通常のテストは、if (r.offset < offset) である。L-CSCANは、現在のスキャンに要求を追加することができる回数を制限する第２節 curr.size() < count を追加する。L-CSCANから要求が不足するのを防止するのがこの追加の節である。現在のスキャンキューに要求が所定回数だけ追加された後、全ての新しい要求がその位置にかかわらず次のキューに追加されるからである。
【００６２】
L-CSCAN MRIS 1 における前記回数は、現在のキューに追加される要求のみを追跡するものであり、すなわち、該キューに追加される要求であっても該キューが最新のSwap()の前にある次のキューである場合にはその全ての要求を無視する。L-CSCAN MRIS 1は、CSCAN MRIS 9 のように、非常に効率的であり、O(log(n))時間を要するものである。
【００６３】
L-CSCAN MRIS 2. 制限されたCSCAN から要求をポップ
1: procedure Pop() 
2: if curr.empty() then
3:                  Swap(curr, next)
4:                  count ← 0
5: end if
6: result ← curr.smallest()
7: curr.delete(result) 
8: offset ← result.offset
9: return result
L-CSCAN MRIS 2 は、Pop() MRIS のための擬似コードを示しており、これは、標準的なCSCANの場合とは４行目が異なり、この場合には、新しいスキャンを開始する際にカウントがリセットされる。この場合も、L-CSCAN MRIS 2 は、CSCAN MRIS 2 と非常に似ており、性能O(log(n))を有する。
【００６４】
上述したMRISの全てに関する上記計算は、要求の個数に基づくものであり、実際のサービス時間に基づくものではない。要求ストリームが一様な要求サイズを有する場合にはそれら２つの場合は同一となる。しかし、実際には、多数のシステムが異種の要求ストリームを有しており、またアプリケーションは広範な要求サイズを混在して有する可能性がある。この場合、最悪のレイテンシは時間に関して規定することが可能であり、また現在のスキャンに追加することが可能な要求の個数に関する上記計算はスループットレート時間に関して行われる。これを実施すべく、MRISは、キューに関するスループットレート時間の合計の計算を全体として及び各スキャン毎に実行し続ける。該MRISはまた、最新のSwap以降に現在のスキャンに追加されたスループットレート時間の合計を維持しなければならない。
【００６５】
要求の個数ベースから時間ベースへと切り換えた場合には、スキャンを終了すべきときを決定するための基準を用いる必要がある。該基準は単調に増加するものである必要はない。例えば、１つの大きな要求を完了させるため及び１つの小さな要求を挿入するために、予想されるサービス時間がスキャン時間しきい値を下回る可能性がある。要求はシーケンシャルとなり得るため、システムに所定の状態パラメータを追加し、これにより、決定が行われた際に、予想されるスキャン時間が所望の限界を超えてしまうため、現在のスキャンに追加されているはずの要求が追加されなかった場合に、他の要求がそのスキャンに追加されるのを防止するフラグをセットすることができるようにする必要がある。
【００６６】
L-CSCANの時間ベースの変種は、５つの新しい状態パラメータ、すなわち、scan、start、sum_current、sum_next、及び closedを使用することが可能であり、これは、各要求毎の最悪のスループットレート時間の精確な推定値によって決まる。scanは、単一のスキャンが要し得る最大時間量を規定し、startは、現在のスキャンが開始した時刻であり、sum_currentは、現在のスキャンにおける要求についての予想されるスループットレート時間の合計であり、sum_nextは、次のスキャンにおける要求についての予想されるスループットレート時間の合計であり、及び closedは、新しい要求が現在のスキャンにまだ追加されるか否かを規定するブール代数である。
【００６７】
最悪のスループットレート時間の推定値は、上述の記憶装置の評価から導出することが可能である。これは、要求の３つの特性、すなわち、size、read|write、及びsequentialを考慮するものとなる。ここで、sizeは、バイトを単位とする要求サイズであり、read|writeは、要求がリード要求であるかライト要求であるかを規定し、sequentialは、要求がシーケンシャルであるか否かを規定するブール代数である。一般に、sequentialは、単純なフィルタを使用して求めることが可能であるが、かかる一般的な場合、sequentialは、現在の要求の開始アドレスの直前のバイトをアドレス指定する該現在の要求と同じread|write状態を有するキュー内に保留中の要求が存在するか否かを単に記述するものである。
【００６８】
L-CSCAN MRIS 3. 時間ベースの制限されたCSCANに要求を追加
1: procedure Add(Request r)
2: if r.offset < offset AND scan < (now()-start) + sum_current then
3:                  closed ← true
4: end if
5: if r.offset < offset OR closed then
6:                  next.insert(r)
7:                  sum_next ← sum_next + r.expected()
8: else
9:                  curr.insert(r)
10:                  sum_current ← sum_current + r.expected()
11: end if
L-CSCAN MRIS 3 は、制限が時間に関して規定される場合の制限されたCSCAN MRISを示している。変数 r.expected()は（最悪の）スループットレート時間として規定することが可能である。L-CSCAN MRIS 1 と L-CSCAN MRIS 3 との主な違いは、個数ベースのテストを時間ベースのテストに置換したことにあり、及び時間ベースのテストが単純に各挿入時に常に再テストを行うのではなく状態変数を変更するという事実にある。この場合も、L-CSCAN MRIS 3 の実行時間はO(log(n))である。
【００６９】
L-CSCAN MRIS 4. 時間ベースの制限されたCSCAN から要求をポップ
1: procedure Pop() 
2: if curr.empty() then
3:                  Swap(curr, next)
4:                  start ← now
5:                  sumcurrent ← sumnext
6:                  sumnext ← 0
7:                  closed ← false
8: end if
9: result ← curr.smallest()
10: curr.delete(result) 
11: offset ← result.offset
12: return result
L-CSCAN MRIS 2 と L-CSCAN MRIS 4 との主な違いは、各スキャンの開始時に様々な状態変数をリセットするためのブックキーピングの変更にあり、実行時間は依然としてO(log(n))である。
【００７０】
L-SCANは、より長いスキャンでディスク性能を最適化する。CSCANは、可能な限り長いスキャンを生じさせ、スキャンが長い結果として、その性能が卓越したものとなる。リアルタイム優先順位の要求をスケジューリングするための既知のMRISは、単一のスキャンにまとめることができる要求の個数を適宜制限し、これにより、最悪のキュー遅延時間についての一層厳密な保証を提供することが可能となる。しかし、スキャンは一般に、必要とされるものよりも遙かに小さいものであり、その結果として、性能が必要とされるものよりも遙かに悪化することになる。
CSched
CSchedは、リアルタイム期限の保証を提供すべく性能上の不利益が最小限であり最適な又はほぼ最適な性能を提供するよう設計されたMRISである。CSchedは、ユーザレベルアプリケーションで実施することが可能である。CSchedはまた、オペレーティングシステム、（RAID）ディスクコントローラ、又はストレージデバイスもしくはストレージサービスで実施することも可能である。CSchedは、装置の精確な特徴付けに加えて、２つの構成パラメータ（シグマ、ラムダ）を利用し、ここで、シグマは、秒を単位とする最大バーストサイズとして定義され、ラムダは、リアルタイム要求についての最小初期スラックタイムとして定義されるものである。次いで、ディスクの特徴付け及びこれらのパラメータが、スケジューラを制御する内部的な構成パラメータへと変換される。
【００７１】
シグマは、要求に関して規定されるのではなく時間に関して規定されるという点を除き、リーキーバケットモデルを用いて計算することが可能である、ということに留意されたい。要するに、リーキーバケットモデルは以下のように説明することができる。要求ストリームについての到着関数R(s,t)は、期間[s,t]内のI/O要求の総数である。全期間[s,t]についてR(s,t) ≦ シグマ + rho(t-s)である場合、要求ストリームは正常に動作している。リーキーバケットモデルについては下記文献に詳細に説明されている：Parekh等の「A generalized processor sharing approach to flow control in integrated services networks: the single-node case」（Networking, IEEE/ACM Transactions on 1,3 (1993), 344-357）、Sariowan等の「Scheduling for quality of service guarantees via service curves」（Computer Communications and Networks, 1995. Proceedings, Fourth International Conference on (1995), pp.512-520）、及びGulati等の「pClock: an arrival curve based approach for QoS guarantees in shared storage systems」(Proceedings of the 2007 ACM SIGMTRICS international conference on Measurement and modeling of computer systems (San Diego, California, USA, 2007), ACM, pp.13-24)。
【００７２】
主要な内部的な構成パラメータは、SCAN-EDF、L-CSCAN、及び装置キューの間における利用可能なタイムバジェットであるラムダの割り当てである。装置のタイムバジェットが要求ストリームの最悪のサービス時間のみによって規定されるため、これは、ディスク特徴付けからデルタとして直接取得される。次のブロックは、バーストを吸収するためにSCAN-EDFキューに割り当てられなければならないタイムバジェットを決定することであり、これは、単に最大のバーストを処理するために必要な時間すなわちシグマである。残りのバジェットはL-CSCANキューに割り当てられる。L-CSCANキューサイズは、L-CSCANキューが満杯であるか否かを判定するためにCSchedが使用するものであり、時間を単位として定義される。
【００７３】
MRIS CSched 1 - CSchedキューの構成
1: class CSched
2:              LCSCAN* lcscan 
3:              Sched** pending
4:              int nqueues
5:              time t zeta
6: CSched(time t シグマ, time t ラムダ, time t デルタ)
7:              zeta ← (ラムダ - シグマ - デルタ)/4
8:              lcscan ← new LCSCAN(ゼータ)
9:              pending ← new Sched*[nqueues + 1] 
10:              pending[0] ← new SCAN EDF
11:              for i in 1:nqueues do 
12:                            pending[i] ← new CSCAN 
13:              end for 
MRIS CSched 1 は、CSchedデータ構造を記述し、及び様々な要素が初期化される態様を示している。
【００７４】
MRIS CSched 2 - CSchedへの要求の追加
1: procedure Add(Request r)
2: if lcscan.expected() + r.expected() < ゼータ then 
3:              {L-CSCAN is not full}
4:              lcscan.Add(r) 
5: else if 0 < r.deadline then
6:              {real-time request} 
7:              pending[0].Add(r) 
8: else
9:              {best-effort or background request} 
10:              pending[r.priority].Add(r)
11: end if
MRIS CSched 2 は、CSchedキューに要求が追加される態様を示している。lcscan.expected() は、 lcscan.sumcurrent + lcscan.sumnextとして計算され、lcscanキュー内に現在保持されている全ての要求についての最悪のスループットレート時間の合計である、という点に留意されたい。第１に、L-CSCANキューへの要求の追加が、該L-CSCANキューをその（時間に関して指定された）許容サイズを超えさせるものでない場合には、該要求はL-CSCANキューに単純に追加される。そうでない場合には、該要求は適当な保留中のキュー（リアルタイム要求の場合にはSCAN-EDF、ベストエフォート及びバックグランド要求の場合にはCSCAN）に追加される。このコードは一般的なものであり、それらの非リアルタイム要求については他の任意のスケジューリングシステムを使用することが可能である、ということに留意されたい。
【００７５】
MRIS CSched 3 - CSchedからの要求のポップ
1: procedure Pop()
2: result ← lcscan.Pop()
3: for i = 0 to nqueues do
4:                  if pending[i] ¬ empty then
5:                                    r ← pending[i].Head()
6:                                    if lcscan.expected() + r.expected() ≧
ゼータ
then
7:                                                {L-CSCAN is now full}
8:                                                break
9:                                    end if
10:                                    r ← pending[i].Pop() 
11:                                    lcscan.Add(r) 
12:                  end if
13: end for
14: return result 
MRIS CSched 3 は、記憶装置へ提示するために要求をキューから除去する際に生じることを示している。第１に、MRIS CSched 3 は、２行目で次の要求をL-CSCANキューから除去する。該L-CSCANキューからの要求の除去は、保留中のキューからの要求を追加する余地があることを意味し得るものであるため、システムは、各保留中のキューを繰り返しチェックし、リアルタイムSCAN-EDFキューから開始して要求を探す。L-CSCANキューに要求を追加する余地がある限り、この処理は行われる。LCSCANキューが満杯となり又は保留中のキューが空になるや否や、この処理は停止する。６行目のテストは、上記 MRIS CSched 2 の２行目と同じであることに留意されたい。また、５行目は、実際に要求を除去することなくキューからポップされるべき次の要求を単に返すものである。これは、上記 MRIS CSched 1 の９行目の行 r curr.smallest() とほぼ等価である。
【００７６】
ほぼ60の同時並行性を用いて実質的に最適な性能が得られるため（図３参照）、システムは、キューに入れられた要求が存在する限り、最大限の同時並行性を維持する。また、装置の前に大きなCSCAN（又はL-CSCAN）キューを有することにより性能が改善されるため（図５参照）、L-CSCANキューサイズを最大限にすることが求められる。しかし、最悪のキュー遅延がバジェットを超えないことを確実にすべく、このキューサイズを制限することが求められる。
【００７７】
制限されたCSCAN、L-CSCAN、スケジューラの役割は、（１）低レベルの位置知覚型のスケジューラがその要求の再順序付け能力を一層良好に利用してスループットを最大限にすることができるように要求を最適な態様又はほぼ最適な態様で装置へ提示すること、及び（２）全体としてのソリューションによりリアルタイム保証を提供することが可能となるように最悪のスケジューリング遅延が制限されることを確実にすることである。
SCAN-EDF
SCAN-EDFキューは、バーストを吸収して、リアルタイム保証を提供すべくL-SCANキューのサイズを制限することを可能にする。FIFO又はEDFキューではなくSCAN-EDFを使用する理由は、（特に集中的な（bursty）作業負荷に関して）潜在的に改善された性能にある。期限に関して順序通りに提示されないこともまた、リアルタイム要求にとって有用である。例えば、作業負荷は、非常に集中的なものとなる（130ms毎に新たな複数のデータバッチが必要となる）傾向にあり、この場合、１つのバッチは、ディスクアドレスに関してランダムな順序で記憶装置に提示される数千もの多数の小さな要求を含み得るものである。この場合、各バッチでのSCANの使用は、全体的なスループットを最大化することが可能となるように要求が部分的に最適化された態様でL-CSCANキューへ送られることを意味している。
【００７８】
SCAN-EDFは、サイズ自体は制限されないが、作業負荷の特徴付けが精確に行われていることを前提としたものであり、このため、一例によれば、SCAN-EDFは、シグマよりも多くの要求を保持することはなく又は要求に関連する期間よりも大きくなることはなく、SCAN-EDFキュー内の要求に生じる最悪のキュー遅延は、シグマ*expected であり、ここで、expected は、要求ストリームについての予想される最悪のスループットレート時間である。
CSCANスケジューラ
複数のCSCANスケジューラは、L-CSCANキュー内に利用可能な余地が存在するまで非リアルタイム要求を保持する。要求は、これらのキューから優先順位順に渡され、例えば、バックグランド要求は、リアルタイムSCAN-EDF及びベストエフォートCSCANキューの両者が空である場合に限り、バックグランドCSCANキューからL-CSCANキューへと渡されることになる。代替的なアーキテクチャを利用することが可能であると共に潜在的に有用であり、かかる代替的なアーキテクチャの一例が、Gulati等の「pClock: an arrival curve based approach for QoS guarantees in shared storage systems」（Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computersystem (San Diego, California, USA, 2007), ACM, pp.13-24）で開示されているpClockである。更に、他の適当な既知のアーキテクチャを使用して様々な非リアルタイムストリームからL-CSCANキューへの要求の提示を制御することが可能である。
６．結果
CSched MRISの性能は、CSchedが徒過した期限を有さずCSCANがリアルタイム保証を提供しないことを除き、CSCANの性能と類似している。CSched MRISの性能は、２つの高い作業負荷条件（すなわち、様々な作業負荷を有する一様且つランダムなリアルタイム要求ストリームと一様且つランダム又はシーケンシャルなベストエフォート要求ストリーム）下でテストされる。該リアルタイム要求ストリーム及び該ベストエフォート要求ストリームの両者が一様且つランダムである場合、全体的な性能が最小となり、一方、シーケンシャルなベストエフォート要求ストリームは、フェアネスの観点からCSCANのために最も敵対的な要求ストリームを提供する。多くのベストエフォート作業負荷は、一様且つランダムな要求と一様且つシーケンシャルな要求とを混合したものである。このため、実際の性能は、それら２つの作業負荷の中間となる傾向にある。アプリケーションの作業負荷は、一様且つランダムなリアルタイム要求ストリームおよび一様且つランダムなベストエフォート要求ストリームを有する場合に特徴付けを行うことが可能である。しかし、通常は、一様な４kBサイズではなく、複数の要求サイズが混在する。
【００７９】
図９は、標準的なCSCANキューを使用する場合にリアルタイムデータレート要件の関数として２つの作業負荷についてのスループットを示すグラフ900である。その第１の作業負荷は、リアルタイム要求及びベストエフォート要求の両者についての一様且つランダムな要求パターンであり、第２の作業負荷は、リアルタイム要求に関する一様且つランダムな要求パターンとベストエフォート要求についてのシーケンシャルパターンである。リアルタイム要求ストリームは滑らかなものとなる。リアルタイム要求は、30秒の初期スラックタイムを有し、CSchedは、SCAN-EDFに割り当てられる0秒と、装置の最悪の場合に割り当てられる1.4秒と、L-SCANについての残りの28.6秒の最大レイテンシとを用いて構成される。
【００８０】
留意すべきは、一様且つランダムな作業負荷についての性能がリアルタイム要求負荷に対して不変である、ということである。この曲線がリアルタイムデータレートに関して平坦であり、及びその値がこのワークフローについて観察されたほぼ最適な値（図５の点線の曲線の最も右側のポイント）と一致する、という事実は、CSchedがこの作業負荷について装置上でほぼ最適な達成可能な性能を得ることを実証するものである。予想通り、リアルタイム要求の割合が増大すると、シーケンシャルなベストエフォート要求ストリームを用いた総システムスループットが低下する。これは、利用可能なリソースの増大していく比率をリアルタイム要求が吸収するからである。しかし、その２つの曲線すなわち点線の曲線及び鎖線の曲線は、それぞれリアルタイム保証がある場合とない場合のほぼ最適な性能を表しており、これは、CSchedが他の高い作業負荷についてもほぼ最適なスループットを得ることを実証するものである。
【００８１】
装置で同時要求を許可しない複数のリアルタイムディスクスケジューリングMRISの何れか又はその全てとの比較のため図５を参照されたい。同図は、様々な構成で「単一の未処理要求を用いるシステムについての相対的な性能を例証する曲線（すなわち曲線504,508）」対「60個の同時要求を用いるシステムについての相対的な性能を例証する曲線（すなわち曲線502,506）」を示している。作業負荷が４kBの要求を使用した場合、図５の一番下の実線の曲線508上の最も左のデータポイントにより、同じハードウェア構成で、EDFが0.8MB/s未満を達成すること及びCSchedが約22MB/sを達成することが予想されることを容易に理解することができる。同様に、同時要求に適合しないディスクスケジューリングMRISの上限は、たったの約1.4MB/s（曲線508上の最も右側のデータポイントの値）であり、これは、装置の前にある１つの大きな効率的なキューを表している。
【００８２】
１MBの要求ストリームに関して鎖線の曲線から同様の所見を述べることが可能である。EDFは、約100MB/s（該曲線の最も左側のポイント）を提供し、一方、同時要求を許可しない最も効率的なリアルタイムディスクスケジューラは、約140MB/s（該曲線の最も右側のポイント）に達し得ると思われる。CSchedは典型的には、同じ要求ストリームを用いて同じハードウェア上で約420MB/s（鎖線の曲線の最も右側のポイント）に達する。上述のように、標準的なCSCANスケジューラのフェアネスは、要求ストリームが一層シーケンシャルになり及び一層ランダムでなくなるにつれて損なわれる。
【００８３】
図１０は、L-CSCANキューの必要性を例証するグラフ1000であり、ベストエフォート要求ストリームがシーケンシャルである場合に要求の期限を徒過するリアルタイム要求の一部を示している。リアルタイム要求レートが低い場合には、ベストエフォート要求がCSCANキューに高速で入り続け、このため、各スキャンが、他のアドレスで切望しているリアルタイム要求のサービスへと進む前に、該シーケンシャルのベストエフォート要求について過度の量の時間を費やすことになる。
【００８４】
図１１は、図９と類似したグラフであるが、滑らかなリアルタイム要求ストリームを有するのではなく集中的な要求ストリームを有する点で異なり、この場合には、一度に５秒のバーストサイズに相当するリアルタイム要求を有する。テストハードウェア上で４kBのランダムなリアルタイム要求について予想される最悪のスループットレート時間が0.39ms（expected = 0.00039）であり及び所望のリアルタイムデータレートがＸMB/sである場合には、所与の１つのバーストにおける要求の個数は、シグマと等価な5/0.00039であり、これは、12,820個の要求または53MBのキャッシュと等価であり、４kBの要求についてのバースト到着間レート（burst inter-arrival rate）は（4096・シグマ）/（1,000,000・Ｘ）である。Ｘ＝１MB/sである場合には、バースト到着間レートは52.5秒である。この性能は図９に示したものと同様である。このため、システムがバーストを扱うよう設計されている限り、性能はリアルタイム要求ストリームのバースト性に対して比較的不変となる。
【００８５】
上記計算は、最悪のスループットレート時間データを使用して行われ、これは、予想されるスループットレート時間（図７参照）とは実質的に異なり得るものである。最悪のスループットレート時間を用いたシステムのスループットは約10.5MB/sであり、数千ものキューイングされた要求を用いた該システムの予想されるスループットは、おおよそ22MB/Sである。ラムダが増大するにつれて、初期スラックタイムの一層大きな部分が最悪の装置サービス時間に割り当てられて、L-CSCANキューに割り当てられるレイテンシが残り少なくなる。これは、L-CSCANキューのサイズが小さくなって性能に悪影響を与えることを示唆している。リアルタイム作業負荷が非常に集中的なものである場合、すなわち、シグマが大きい場合には、L-CSCANキューから更なる時間が取られることになる。これは、ある方法により対処することが可能であり、該方法は、リアルタイム要求が、最も最近追加された非リアルタイム要求をLCSCANキューから先制的に除去してそれらを保持スタックにプッシュすることを可能とすることによりSCAN-EDFキューをなくす、というものである。L-CSCANキュー上に空きが出来次第、前記保持スタック上の要求がL-CSCANキューに再び追加され、これにより非リアルタイム要求間のフェアネスがほぼ維持される。
【００８６】
もう１つの方法は、最小初期スラックタイム値（ラムダ）が、複数の異なる優先順位のアクセス要求の作業負荷に対する予想される将来の変化に関連する信号に応じて再決定され得る動的なパラメータである場合である。この方法では、再決定される最小初期スラックタイム値（ラムダ）は、複数の異なる優先順位のアクセス要求の作業負荷に対する予想される将来の変化に関連する信号に応じて記憶装置及び作業負荷の特徴付けから得られた少なくとも１つの値に基づいて決定される。
【００８７】
図１２は、一例による図１に示したスケジューリング装置100を使用して増大する最小初期スラックタイム値（ラムダ）の関数としてスループットが変化する態様を例証するグラフ1200である。図１２に示すように、スループットはラムダと共に変化し、この場合、一定のリアルタイムデータレートは9.5MB/S、シグマ＝0s、及びデルタ＝1.4sである。ラムダが増大する（1.5,...,30）とき、これはゼータが増大する（0.1,...,28.6）ことも意味する。ゼータが増大し、その結果としてL-CSCANキューサイズが増大するとき、性能は改善し、これは、上述の図４に示した結果と一致し、すなわち、スケジューリングキューのサイズを増大させることによりディスク性能が改善する。
【００８８】
図１３は、一例による図１に示したスケジューリング装置100を使用して等価条件下でベストエフォート要求と共にリアルタイム要求をスケジューリングする場合にランダムまたはシーケンシャルな要求の条件下で改善されるスループットを例証するグラフ1300である。図１３は、図９に類似しているが、スケジューラCDS-SCANが如何に挙動するかも示している点で異なる。CDS-SCANについては、Staelin等の「Real-time disk scheduling MRIS allowing concurrent I/O requests」（Tech. Rep. HPL-2009-244, Hewlett-Packard Laboratories, Oct 2009）に記載されている。リアルタイム要求が存在しない場合にはCSched及びCDS-SCANの性能が同様となるが、これと比較して、ランダムなベストエフォート要求ストリームについてのCDS-SCANの性能が低下する一方、CSchedの性能が一定に維持されることに留意されたい。また、リアルタイムレートが増大するにつれてシーケンシャルなベストエフォートストリームについてのCDS-SCANの性能がCSchedの性能よりも一層急激に低下する態様について留意されたい。
７．CRS装置及びCRS方法
本書で開示されるのは、同時要求スケジューリング（CRS）を管理するための方法及び装置である。図１を参照すると、一例によるCRSシステム100の簡素化されたブロック図が示されている。図１は、一般化された実施形態を表すものであり、該CRSシステム100の範囲から逸脱することなく他の構成要素を追加することまたは図示の複数の構成要素を省略し、変更し、または再配置することが可能である、ということが当業者には自明である。
【００８９】
CRSシステム100は、CRS装置102、プロセッサ120、入力装置130、出力インタフェイス140、及びデータ記憶装置118を含むものとして示されている。該プロセッサ120は、CRS装置102を実施し及び／又は実行するためのものである。このため、例えば、CRSシステム100をコンピューティング装置から構成することが可能であり、及びCRS装置102を該コンピューティング装置の一体型またはアドオン型のハードウェア装置から構成することが可能である。別の一例として、CRS装置102は、コンピュータにより読み取ることが可能な記憶装置（図示せず）とし、該記憶装置上にプロセッサ120が実行すべきコンピュータプログラムを格納することが可能である。
【００９０】
図１に更に示すように、プロセッサ120は、入力インタフェイス130からの入力を受信する。該入力インタフェイス130は、例えば、ユーザがデータにアクセスすること、例えば、データ記憶装置118に格納されている要求、オブジェクト、MRIS、アプリケーション等にアクセスすることを可能にするユーザインタフェイスから構成することが可能である。追加的にまたは代替的に、ユーザは、入力インタフェイス130を介してデータ記憶装置118にデータを供給し及び／又は該データ記憶装置118に以前に格納されたデータを更新することが可能である。入力インタフェイス130はまた、データ記憶装置118に格納されているデータに（出力インタフェイス140を介して出力された際に）ユーザがアクセスすることを可能にするユーザインタフェイスを構成することが可能である。
【００９１】
一例によれば、CRS装置102は、データ記憶装置118等のメモリに格納されているアクセス要求を処理することになる。該アクセス要求は、リアルタイム優先順位を有するアクセス要求や、ベストエフォート要求及び／又はバックグランド要求等の一層低い優先順位の要求を含む、様々な優先順位のアクセス要求の作業負荷内に存在する。一例によれば、データ記憶装置118は、バッテリーバックアップ式のランダムアクセスメモリ（RAM）、相変化RAM（PCRAM）、及びメモリスタといった、不揮発性バイトアドレス指定可能メモリから構成することが可能である。追加的または代替的に、データ記憶装置118は、リムーバブルPCRAM装置といった外部リムーバブルメディアに対してリード／ライトする装置から構成することが可能である。データ記憶装置118は、データ構造管理システム100の内部のもの又は該システム100に取り付けられたものとして示したが、該データ記憶装置118は、CRSシステム100から遠隔地に配置することが可能であることが理解されよう。この例では、CRSシステム100は、インターネット等のネットワーク接続を介してデータ記憶装置118にアクセスすることが可能である。
【００９２】
図１に更に示すように、CRS装置102は、ユーザインタフェイスモジュール104、装置特徴付けモジュール106、作業負荷特徴付けモジュール108、CRS処理モジュール110、及び更新モジュール112を含む。該モジュール104-112は、MRISコードモジュール、ハードウェアモジュール、又はMRIS及びハードウェアモジュールの組み合わせから構成することが可能である。このため、一例では、モジュール104-112は、複数の回路要素から構成することが可能である。もう１つの例では、モジュール104-112は、コンピュータ読み取り可能記憶媒体上に格納された、プロセッサ120が実行することになるコードから構成することが可能である。このため、一例では、CRS装置102は、コンピュータ、サーバ、回路といったハードウェア装置からなる。別の例では、CRS装置102は、モジュール104-112の機能を実行するためのMRISコードが格納されたコンピュータ読み取り可能記憶媒体からなる。CRS装置102が実行する様々な機能について以下で詳細に説明する。
【００９３】
一例によれば、CRS装置102は、所定のCRS方法を実施するものとなる。CRS装置102のモジュール104-112を実施することが可能な様々な態様を図１４及び図１５に関して一層詳細に説明する。図１４及び図１５は、CRSを実行するための方法1400，1500のフローチャートを示している。当業者には自明であるように、該方法1400,1500は、一般化された実施形態を表したものであり、該方法1400,1500の範囲から逸脱することなく、本開示以外のブロックを追加し、又は本開示のブロックを削除し、変更し、若しくは再配置することが可能である。
【００９４】
方法1400,1500についての説明は、図１に示すCRS装置102及び図２に示すCRSアーキテクチャ図200を特に参照して行うが、該方法1400,1500は、該方法の範囲から逸脱することなく、CRS装置102及びCRSアーキテクチャ200とは異なる装置で実施することが可能である、ということが理解されよう。
【００９５】
先ず図１４を参照すると、ブロック1402で、記憶装置の特徴付けが装置特徴付けモジュール106を使用して実行される。一例では、記憶装置の特徴付けは、同時アクセス要求の平衡数（N）の決定を含む。図１５の方法1500を参照すると、ブロック1502で、記憶装置の特徴付けは、同時アクセス要求の平衡数（N）、最悪の装置サービスレイテンシ値（デルタ）、及び最悪の最大スループットレート時間（1/IOPS）値（タウ）の決定を含む。タウに関する値は、リード／ライト、ランダム／シーケンシャル、及び要求サイズに関する値、並びに随意選択的にその他の値に少なくとも関連し得る関数となる。
【００９６】
ブロック1404は、ブロック1402の記憶装置に関連するアクセス要求の作業負荷に応じて実施することが可能である。先ず図１４の方法1400を参照すると、作業負荷の特徴付けが作業負荷特徴付けモジュール108を使用して実行される。一例では、作業負荷の特徴付けに関して任意の作業負荷の特徴付けパラメータを特徴付けることが可能である。図１５の方法1500を参照すると、ブロック1504で、作業負荷の特徴付けは、最小初期スラックタイム値（ラムダ）、バースト性値（シグマ）、及び最悪のキュー遅延値（ゼータ）による決定を含む。この例によれば、ゼータは、作業負荷の特徴自体ではなく、CRSアーキテクチャ200に関して導出されるパラメータである。
【００９７】
図１４のブロック1406は、リアルタイムアクセス要求を受信することが可能であるという信号又は指示がアクセス要求記憶場所値を有することに応じて実施することが可能である。図１５のブロック1506もまた、リアルタイムアクセス要求を受信することが可能であるという信号又は指示がアクセス要求記憶場所値を有することに応じて実施することが可能である。両方のブロック1406,1506は、CRS更新モジュール112を使用して実施することが可能である。
【００９８】
図１４のブロック1408は、アクセス要求記憶場所値と共にリアルタイムアクセス要求を受信することに応じて実施することが可能である。図１５のブロック1508もまた、アクセス要求記憶場所値と共にリアルタイムアクセス要求を受信することに応じて実施することが可能である。ブロック1408,1508は、該アクセス要求記憶場所値並びにそれ以前のブロックで取得された記憶装置及び作業負荷を特徴付けるパラメータに基づくリアルタイムアクセス要求の処理を含む。ブロック1408,1508は、CRS処理モジュール110を使用して実施することが可能である。
【００９９】
図示した上述の処理の一部又は全部は、ユーティリティ、プログラム、又はサブプログラムとして、あらゆる所望のコンピュータ読み取り可能記憶媒体に格納することが可能である。更に、該処理は、アクティブ又は非アクティブの両方の様々な形態で存在することができるコンピュータプログラムにより実施することが可能である。例えば、該処理は、ソースコード、オブジェクトコード、実行可能コード、又はその他の形態のプログラム命令からなる１つ又は２つ以上のMRISプログラムとして存在することが可能である。上記の何れも、記憶装置を含むコンピュータ読み取り可能記憶媒体上で実施することが可能である。
【０１００】
コンピュータ読み取り可能記憶媒体の一例として、従来のコンピュータシステムRAM、ROM、EPROM、EEPROM、及び磁気又は光学ディスク又はテープが挙げられる。上記の具体例には、CD-ROM又はインターネットによるダウンロードを介したプログラムの配布が含まれる。よって、上記機能を実行することができる任意の電子的な装置は、上記で列挙した機能を実施することが可能なものとなる、ということが理解されよう。
８．CRS方法、装置、コンピュータ読み取り可能媒体のためのプラットフォーム
ここで図１６を参照すると、図１４及び図１５に示した方法又は該方法に関連するコードを実施し又は実行するためのプラットフォームとして採用することが可能なコンピューティング装置1600が示されている。該コンピューティング装置1600の例示は一般化されたものであり、該コンピューティング装置1600は更なる構成要素を含むことが可能であり、該コンピューティング装置1600の範囲から逸脱することなく本開示の構成要素の幾つかを削除し及び／又は修正することが可能である、ということが理解されよう。
【０１０１】
該コンピューティング装置1600は、中央処理装置等のプロセッサ1602、モニタ等の表示装置1604、ローカルエリアネットワーク（LAN）、ワイヤレス802,11x LAN、3GモバイルWAN、又はWiMAX WAN等のネットワークインタフェイス1608、及びコンピュータ読み取り可能媒体1610を含む。これらの構成要素の各々は、バス1612に動作可能な状態で接続することが可能である。例えば、該バス1612は、EISA、PCI、USB、FireWire、NuBus、又はPDSとすることが可能である。
【０１０２】
コンピュータ読み取り可能媒体1610は、命令をその実行のためにプロセッサ1602へ提供することに関与するあらゆる適当な媒体とすることが可能である。例えば、コンピュータ読み取り可能媒体1610は、光又は磁気ディスク等の不揮発性媒体、メモリ等の揮発性媒体、並びに同軸ケーブル、導線、及び光ファイバ等の伝送媒体とすることが可能である。伝送媒体は、音響、光、又は電波といった形態を採ることが可能である。コンピュータ読み取り可能媒体1610はまた、ワードプロセッサ、ブラウザ、電子メール、インスタントメッセンジャ、メディアプレーヤ、及び電話MRISを含む、他のMRISアプリケーションを格納することが可能である。
【０１０３】
コンピュータ読み取り可能媒体1610はまた、Mac OS、MS Windows、Unix、又はLinux等のオペレーティングシステム1614、ネットワークアプリケーション1616、及びデータ構造管理アプリケーション1618を格納することが可能である。オペレーティングシステム1614は、マルチユーザ、マルチプロセス、マルチタスク、マルチスレッド、リアルタイム等をサポートするものとすることが可能である。オペレーティングシステム1614はまた、キーボード又はキーパッド等の入力装置からの入力の認識、表示装置1604及び設計ツール1606への出力、媒体1610上のファイル及びディレクトリの追跡、ディスクドライブ、プリンタ、及びイメージキャプチャ装置等の周辺機器の制御、並びにバス1612上のトラフィックの管理といった基本タスクを実行することが可能である。ネットワークアプリケーション1616は、TCP/IP、HTTP、Ethernet、及びFireWireを含む通信プロトコルを実施するためのMRISといったネットワーク接続を確立し維持するための様々なコンポーネントを含む。
【０１０４】
データ構造管理アプリケーション1618は、上述したような不揮発性メモリのためのCRSアーキテクチャ200等のCRSアーキテクチャを構築／更新するための様々なMRISコンポーネントを提供する。特定の例では、アプリケーション1618により実行される処理の一部又は全部をオペレーティングシステム1614に統合させることが可能である。特定の例では、該処理は、少なくとも部分的に、ディジタル電子回路、コンピュータハードウェア、ファームウェア、MRIS、又はそれらの任意の組み合わせにおいて実施することが可能である。
【０１０５】
本開示の全体を通して具体的に説明してきたが、例示した実施形態は、広範な用途にわたって有用性を有するものであり、上記説明は、制限を意図したものではなく、及び制限的なものと解釈すべきではない。本書で用いた用語、説明、及び図面は、例示のみを目的として提示したものであり、制限を意味するものではない。本開示の例の思想及び範囲内で多数の変形例が実施可能であることが当業者には認識されよう。複数の例に関して説明を行ってきたが、当業者であれば、特許請求の範囲に記載するような実施形態及びそれと等価なものの範囲から逸脱することなく本開示の例に対して様々な修正を加えることが可能である。
【図１】
0005752267.tif 000002
【図２】
0005752267.tif 000003
【図３】
0005752267.tif 000004
【図４】
0005752267.tif 000005
【図５】
0005752267.tif 000006
【図６】
0005752267.tif 000007
【図７】
0005752267.tif 000008
【図８】
0005752267.tif 000009
【図９】
0005752267.tif 000010
【図１０】
0005752267.tif 000011
【図１１】
0005752267.tif 000012
【図１２】
0005752267.tif 000013
【図１３】
0005752267.tif 000014
【図１４】
0005752267.tif 000015
【図１５】
0005752267.tif 000016
【図１６】
0005752267.tif 000017