(57)【要約】【課題】改善されたＩ／Ｏ性能のためのデータ・キャッシングのレートを制御する方法を提供すること。【解決手段】データのキャッシングのための、また特に古くなり不要化したデータの識別のためのキャッシュ・デバイス、またはそのキャッシュ・デバイスの内部のスラッシング・イベントが説明される。さらに、スラッシング・イベント中のキャッシュ・デバイスにおけるキャッシュされたデータの優先順位付けのためのキャッシュ・デバイス、及びそのキャッシュ・デバイスにおける古くなり不要化したキャッシュされたデータが説明される。データのキャッシングのための、またスラッシング・イベントにおけるデータの識別、または古くなり不要化し、キャッシュされたデータの識別のためのキャッシング・デバイスの使用に関連する方法もまた、説明される。【選択図】図１
2014154138.tif 000002
【特許請求の範囲】
【請求項１】
ホット・データの量が、キャッシュ・デバイスのストレージ容量を超過するときに、前記キャッシュ・デバイス上にデータを記憶する方法であって、
最低使用頻度待ち行列ブロックを利用することにより、キャッシュ・デバイス内の１つまたは複数の物理キャッシュ・ウィンドウに記憶されたデータに対する参照を監視する工程と、
前記最低使用頻度待ち行列ブロック内の最低使用頻度待ち行列に対して前記１つまたは複数の物理キャッシュ・ウィンドウに記憶された前記データに優先順位を付ける工程と、
ある期間中に、前記１つまたは複数の物理キャッシュ・ウィンドウ内の前記データに対する前記参照の回数に基づいて、前記１つまたは複数の物理キャッシュ・ウィンドウを前記最低使用頻度待ち行列ブロック内のより高い優先順位の最低使用頻度待ち行列へと昇格させる工程と、
前記データがある期間中にアクセスされないときに、前記１つまたは複数の物理キャッシュ・ウィンドウを前記最低使用頻度待ち行列ブロック内のより低い優先順位の最低使用頻度待ち行列へと降格させる工程と、
前記最低使用頻度待ち行列ブロック内の１つまたは複数のカウンタを使用して、前記キャッシュ・デバイス内の降格された物理キャッシュ・ウィンドウの数を監視する工程と、
を含む方法。
【請求項２】
前記キャッシュ・デバイス内の降格された物理キャッシュ・ウィンドウの数と、自由な物理キャッシュ・ウィンドウの数とを識別するために、前記最低使用頻度待ち行列ブロックと通信するハッシュ・テーブルを検索する工程をさらに含む、請求項１に記載の方法。
【請求項３】
自由な物理キャッシュ・ウィンドウが、前記キャッシュ・デバイスにおいて使用可能でないことを識別する工程と、
前記最低優先順位の最低使用頻度待ち行列内の前記降格された物理キャッシュ・ウィンドウからのデータを置換する工程と、
前記降格された物理キャッシュ・ウィンドウに対する新しいデータを記憶する工程と、
前記最低使用頻度待ち行列ブロックを利用して、前記降格された物理キャッシュ・ウィンドウに記憶された前記新しいデータに対する参照を追跡する工程と、
をさらに含む、請求項２に記載の方法。
【請求項４】
仮想キャッシュ・ウィンドウを使用してホスト内のデータを追跡する工程と、
前記仮想キャッシュ・ウィンドウを使用して前記ホスト内の前記データに対する参照の回数を監視する工程と、
ある期間中にいくつかの前記参照を受信する前記ホストからの前記データに基づいて、前記１つまたは複数の物理キャッシュ・ウィンドウによって表される前記キャッシュ・デバイス上に前記ホストからの前記データを記憶する工程と、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記降格された物理キャッシュ・ウィンドウの総数がゼロに等しく、また前記自由な物理キャッシュ・ウィンドウの総数がゼロに等しいときに、前記キャッシュ・デバイスがスラッシングしていることを識別する工程をさらに含む、請求項２に記載の方法。
【請求項６】
前記降格された物理キャッシュ・ウィンドウに前記データを記憶するために必要とされる前記参照の回数を増大させる工程をさらに含む、請求項５に記載の方法。
【請求項７】
前記参照の前記回数における前記増大が、３回の参照よりも大きい、請求項６に記載の方法。
【請求項８】
前記降格された物理キャッシュ・ウィンドウの総数がゼロよりも大きく、また前記自由な物理キャッシュ・ウィンドウの総数がゼロに等しいときに、前記キャッシュ・デバイスが古くなり不要化したデータを有することを識別する工程をさらに含む、請求項２に記載の方法。
【請求項９】
前記降格されたキャッシュ・ウィンドウの総数がゼロに等しく、また前記自由なキャッシュ・ウィンドウの総数がゼロよりも大きいときに、いつ前記キャッシュ・デバイスが自由な物理キャッシュ・ウィンドウを有するかを識別する工程をさらに含む、請求項２に記載の方法。
【請求項１０】
データのキャッシングのためのキャッシュ・デバイスであって、
少なくとも１つの仮想キャッシュ・ウィンドウと、
少なくとも１つの物理キャッシュ・ウィンドウと、
前記少なくとも１つの物理キャッシュ・ウィンドウと通信する最低使用頻度待ち行列ブロックであって、前記最低使用頻度待ち行列ブロックは、少なくとも２つの最低使用頻度待ち行列と、少なくとも２つのカウンタと、１つのグローバル・カウンタとを備える、最低使用頻度待ち行列ブロックと、
前記最低使用頻度待ち行列ブロックと通信するハッシュ・テーブルと、
を備えるキャッシュ・デバイス。
【請求項１１】
前記少なくとも１つの物理キャッシュ・ウィンドウは、前記少なくとも１つの物理キャッシュ・ウィンドウに記憶されたデータに対する参照の回数に基づいて、前記最低使用頻度待ち行列ブロック内の前記最低使用頻度待ち行列に対して優先順位が付けられる、請求項１０に記載のキャッシュ・デバイス。
【請求項１２】
前記ハッシュ・テーブルは、前記少なくとも１つの物理キャッシュ・ウィンドウに記憶された前記データのロケーション、及び前記少なくとも１つの物理キャッシュ・ウィンドウのロケーションのリストを保持する、請求項１１に記載のキャッシュ・デバイス。
【請求項１３】
前記最低使用頻度待ち行列ブロックは、前記少なくとも１つの物理キャッシュ・ウィンドウに記憶された前記データに対する参照の回数を監視する、請求項１２に記載のキャッシュ・デバイス。
【請求項１４】
前記少なくとも２つのカウンタと１つのグローバル・カウンタは、前記最低使用頻度待ち行列ブロックと通信する前記少なくとも１つの物理キャッシュ・ウィンドウの降格を監視する、請求項１３に記載のキャッシュ・デバイス。
【請求項１５】
前記少なくとも１つの物理キャッシュ・ウィンドウは、前記データの記憶のための少なくとも１つのキャッシュ・ブロックをさらに備える、請求項１４に記載のキャッシュ・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般にコンピュータ・システムに関し、またより詳細には、ストレージ・システムに関する。
【背景技術】
【０００２】
ストレージ・デバイスまたはキャッシュ・デバイスは、データをシステムに記憶することを可能にし、将来、そのデータにより高速かつより効率的にアクセスすることを可能にする。データがストレージ・デバイスまたはキャッシュ・デバイスに記憶されると、データが、ある期間にわたってアクセスされない場合、そのデータは、既に不要なものになっているであろう。場合によっては、キャッシュ・デバイスにキャッシュされることが必要になるデータは、キャッシュ・デバイスの容量よりも大きくなるであろう。これらの場合においては、キャッシュ・デバイスは、データをキャッシュすることを開始するとともに、再びキャッシュされることが必要になる、より古いデータを取り除くこともできる。同じデータをキャッシュすること、および捨てることについての連続サイクルを作り出すことは、スラッシングと呼ばれる。
【発明の概要】
【課題を解決するための手段】
【０００３】
本発明の一実施形態は、頻繁にアクセスされるデータであるホット・データの量が、キャッシュ・デバイスのストレージ容量を超過するときに、キャッシュ・デバイスの上にデータを記憶するための方法であって、最低使用頻度待ち行列ブロックを使用してキャッシュ・デバイス内の１つまたは複数の物理キャッシュ・ウィンドウに記憶されるデータに対する参照を監視すること、最低使用頻度待ち行列ブロック内の最低使用頻度待ち行列に対して１つまたは複数の物理キャッシュ・ウィンドウに記憶されたデータに優先順位を付けること、ある期間中に１つまたは複数の物理キャッシュ・ウィンドウ内のデータに対する参照の回数に基づいて、１つまたは複数の物理キャッシュ・ウィンドウを最低使用頻度待ち行列ブロック内のより高い優先順位の最低使用頻度待ち行列へと昇格させること、データが、ある期間中にアクセスされないときに、１つまたは複数の物理キャッシュ・ウィンドウを最低使用頻度待ち行列ブロック内のより低い優先順位の最低使用頻度待ち行列へと降格させること、および最低使用頻度待ち行列ブロック内の１つまたは複数のカウンタを使用してキャッシュ・デバイス内の降格された物理キャッシュ・ウィンドウの数を監視することを含む方法を含むことができる。
【０００４】
本発明の一実施形態は、少なくとも１つの仮想キャッシュ・ウィンドウと、少なくとも１つの物理キャッシュ・ウィンドウと、その少なくとも１つの物理キャッシュ・ウィンドウと通信する最低使用頻度待ち行列ブロックと、その最低使用頻度待ち行列ブロックと通信するハッシュ・テーブルとを備えるキャッシュ・デバイスをさらに備えることができ、また最低使用頻度待ち行列ブロックは、少なくとも２つの最低使用頻度待ち行列と、少なくとも２つのカウンタと、１つのグローバル・カウンタとを備える。
【図面の簡単な説明】
【０００５】
【図１】キャッシュ・デバイス内のキャッシュ・ブロックを有する４つの物理キャッシュ・ウィンドウのブロック図である。
【図２】最低使用頻度の待ち行列およびカウンタを有する最低使用頻度待ち行列ブロックと通信するキャッシュ・ブロックを有する１ＭＢの物理キャッシュ・ウィンドウのクローズアップ図のブロック図である。
【図３】物理キャッシュ・ウィンドウに対するデータ入力の流れ図である。
【図４】物理キャッシュ・ウィンドウの優先順位付けのための流れ図である。
【図５】キャッシュ・デバイスが、スラッシング状態にあるときのホット・データの置換の方法を示す流れ図である。
【図６】キャッシュ・デバイスが、古くなり不要化したデータを有するかどうか、スラッシング状態にあるかどうか、または物理キャッシュ・ウィンドウが、記憶のために使用可能であるかどうかをどのようにして決定すべきかを示す流れ図である。
【発明を実施するための形態】
【０００６】
図１は、キャッシュ・データ１００の記憶のための、また特に、スラッシング・イベント中に、または古くなり不要化しているキャッシュされたデータがキャッシュ・デバイス内に存在するときに、スラッシング・イベントの識別、ならびにキャッシュ・デバイス内のストレージ・キャッシュ・データの優先順位付けのための、１ＭＢの物理キャッシュ・ウィンドウを有するフラッシュ・ストレージ・デバイスのブロック図である。図１に示される例においては、１００ＭＢの容量（図１に示される容量は、４００ＧＢである）を有するフラッシュ・ストレージ・デバイスなど、フラッシュ・ストレージ・デバイスまたはキャッシュ・デバイス１０２は、キャッシュ・ウィンドウ（ＣＷ：ｃａｃｈｅ  ｗｉｎｄｏｗｓ）１０４、１０６、１０８、および１１０と呼ばれ、サイズが１ＭＢのデータ・ストレージ領域へと分割される。キャッシュ・デバイス１０２は、全体で１００ＭＢのストレージ空間の場合に、おのおのが１ＭＢのサイズの１００個の物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０を有する。すべての物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０は、論理ブロック・アドレッシング・スキームを使用して、キャッシュ・デバイス１０２の内部で初期化され、ホスト、またはハード・ディスク１１２からキャッシュ可能なデータを記憶するために使用可能な自由ストレージ空間を有する物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０のプールへと挿入される。各物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０は、さらに、１６個のキャッシュ・ブロックへと分割され、ここでは各キャッシュ・ブロックは、サイズが６４ＫＢである。キャッシュ・ブロックは、６４ＫＢのデフォルト値を有して、サイズを４ＫＢ、８ＫＢ、１６ＫＢ、３２ＫＢ、６４ＫＢおよび１２８ＫＢとすることができる。
【０００７】
図１を参照すると、キャッシュ・デバイス１０２は、ハード・ディスクまたはホスト１１２から記憶するための入出力データ１１４を受信し、ここで、入出力データ１１４は、ホスト１１２から汎用入出力ポート１１６を通して送信される。入出力データ１１４が、記憶のために物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０へと送信される前に、本開示のシステムは、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０が、記憶のために使用可能であるかどうかを判定することになる。すべての入出力データ１１４は、入出力（Ｉ／Ｏ）アクセス信号１１８を用いてキャッシュ・デバイス１０２へと送信される。入出力（Ｉ／Ｏ）アクセス信号１１８を用いて、データ１１４は、データ１１４に対するアクセスが仮想キャッシュ・ウィンドウ１２０によって追跡され、また監視されて、仮想キャッシュ・ウィンドウ１２０として割り付けられるキャッシュ・デバイス１０２の一領域に、最初に記憶される。入出力データ１１４が、仮想キャッシュ・ウィンドウ１２０に位置していながら、通常３回の参照で、または参照の所定のしきい値が満たされるまで、繰り返してアクセスされ、または参照されるときに、仮想キャッシュ・ウィンドウ１２０内の入出力データ１１４は、１つの物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０へと変換され（１２２）、また物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０の内部のフラッシュ・ストレージ・アドレスのある特定領域へと変換される（１２２）。仮想キャッシュ・ウィンドウ１２０が、入出力データ１１４から解放されるが、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０は、仮想キャッシュ・ウィンドウ１２０からの入出力データ１１４で満たされる。ひとたび入出力データ１１４が、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０に割り付けられ、また記憶された後に、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０は、最低使用頻度（ＬＲＵ：ｌｅａｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ）待ち行列ブロック１２４の内部の最低使用頻度待ち行列へと挿入され、またそれによって監視される。ＬＲＵ待ち行列メンテナンス信号１２６および１２８を用いて、最低使用頻度待ち行列ブロック１２４は、後でさらに考察されることになる一連の最低使用頻度待ち行列（図１には示されず）を使用して、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０に記憶された入出力データ１１４に対する参照およびアクセス（入力要求および読取り要求）を追跡する。
【０００８】
図１に示される例示のキャッシュ・デバイス１０２においては、キャッシュ・デバイス１０２の１００個の物理キャッシュ・ウィンドウについての４つの物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０が示されるが、任意の数の物理キャッシュ・ウィンドウが、データ・ストレージのために使用される可能性がある。したがって、この説明の例は、４つの物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０を有するが、ひとたび当業者が本発明の原理を理解した後には、当業者によって理解されるように、この説明は、他の数の物理キャッシュ・ウィンドウを有するそのような任意の装置に対しても適用可能であることを理解されたい。
【０００９】
さらに、図１に示される例示のキャッシュ・デバイス１０２においては、１６個のキャッシュ・ブロックが、物理キャッシュ・ウィンドウ当たりに示されるが、任意の数のキャッシュ・ブロックが、物理キャッシュ・ウィンドウのサイズに応じて、物理キャッシュ・ウィンドウの内部のデータ・ストレージのために使用される可能性がある。それゆえに、この説明の例は、１６個のキャッシュ・ブロックを有するが、ひとたび当業者が本発明の原理を理解した後には、当業者によって理解されるように、この説明は、他の数のキャッシュ・ブロックを有するそのような任意の装置に対しても適用可能であることを理解されたい。
【００１０】
例として、本開示のシステムは、１００万個の構成可能なトラッキング・ヘッダまたは仮想キャッシュ・ウィンドウ１２０を有しており、また各トラッキング・ヘッダまたは仮想キャッシュ・ウィンドウ１２０は、１ＭＢの仮想データ空間を有する。仮想キャッシュ・ウィンドウ１２０は、フラッシュ・ストレージ・デバイスまたはキャッシュ・デバイス１０２の内部のメモリ・データ構造である。これらの仮想キャッシュ・ウィンドウ１２０を使用して、ハード・ディスク空間またはホスト１１２の１ＭＢの領域を追跡し、ここで、ホスト１１２の１ＭＢの領域は、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０にキャッシュされてはいない。
【００１１】
本開示の一例においては、仮想キャッシュ・ウィンドウ１２０によって追跡されるハード・ドライブ空間またはホスト１１２の特定の１ＭＢの領域が、３回以上アクセスされる場合、その領域の入出力データは、頻繁にアクセスされる、すなわち「ホット（ｈｏｔ）」であると判定され、物理キャッシュ・ウィンドウ構造１０４、１０６、１０８、および１１０は、最低使用頻度待ち行列ブロック１２４の内部の最低使用頻度待ち行列から取り出される。ハード・ディスクまたはホスト１１２内のホットな入出力データの１ＭＢの領域は、１ＭＢの物理キャッシュ・ウィンドウ構造１０４、１０６、１０８、および１１０によって表されるフラッシュ・ストレージ１０２のアドレス空間のある特定の領域の上にコピーされ、また記憶される。ホットな１ＭＢのハード・ディスク１１２の領域への以後の入出力データは、次に、より低速のハード・ディスクまたはホスト１１２ではなくて、より高速のキャッシュ・デバイスまたはフラッシュ・ストレージ・デバイス１０２の物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０のキャッシュされたデータの特定の領域に対してリダイレクトされることになる。
【００１２】
ホスト１１２のアプリケーションからのデータ１１４に対する参照を受信するとすぐに、ハッシュ・テーブル１３０は、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０のリストを保持し、またここでは、データ１１４は、キャッシュ・デバイス１０２に記憶され、または割り付けられている。ハッシュ・テーブル１３０は、通信信号１３２を用いて最低使用頻度待ち行列ブロック１２４と通信する。最低使用頻度待ち行列ブロック１２４は、仮想キャッシュ・ウィンドウ１２０のデータ構造と、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０のデータ構造との両方に対する参照を保持し、また監視する。ホスト１１２内のデータの領域のロケーションに基づいて、ハッシュ・テーブル１３０は、最低使用頻度待ち行列ブロック１２４によって検索されて、仮想キャッシュ・ウィンドウ１２０であるか、または物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０であるかにかかわらず、任意のタイプのキャッシュ・ウィンドウが、データについてのその１ＭＢの領域を追跡するように既に割り付けられているかどうかを決定する。物理キャッシュ・ウィンドウが、データについての１ＭＢの領域からのデータを既に追跡しており、また記憶していることが見出される場合に、図２を参照して考察されるように、物理キャッシュ・ウィンドウに関連する適切なカウンタ（図１には示されず）は、１だけアップデートされ、また増大される。ハード・ディスクまたはホスト領域１１２が、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０においてまだ追跡されていない場合、新しい仮想キャッシュ・ウィンドウ１２０が、新しい関心領域を追跡するために割り付けられる。
【００１３】
入出力データ１１４が、以前に決してアクセスされていない１ＭＢの領域にヒットする場合、仮想キャッシュ・ウィンドウ１２０は、仮想キャッシュ・ウィンドウの自由なリストから割り付けられ、またその領域のデータに対するアクセスの回数は、１に設定される。仮想キャッシュ・ウィンドウ１２０における各アクセスが追跡され、また入出力の回数によって測定され、入出力の時間によっては測定されない、所与の入出力データ期間中である場合には、仮想キャッシュ・ウィンドウ１２０のアクセスは、しきい値（仮想キャッシュ・ウィンドウ内のデータに対する通常３回の参照）に到達し、仮想キャッシュ・ウィンドウ１２０内の入出力データ１１４は、物理キャッシュ・ウィンドウ１０４、１０６、１０８、および１１０に対して転送される。仮想キャッシュ・ウィンドウ１２０は、今や、新しい入出力データ１１４を自由に受信することができる。
【００１４】
図２は、物理キャッシュ・ウィンドウおよび最低使用頻度待ち行列ブロック２００のクローズアップ例を提供するものである。図２に示されるように、最低使用頻度待ち行列ブロック１２４は、通信信号１３２を用いてハッシュ・テーブル１３０と通信する。最低使用頻度待ち行列ブロック１２４は、カウンタ１７０と、グローバル・カウンタ１７２と一緒に、最低使用頻度待ち行列（ＬＲＵ待ち行列）１３８、１４０、１４２、１４４、１４６、１４８、１５０、１５２、１５４、１５６、１５８、１６０、１６２、１６４、１６６、１６８（１３８乃至１６８）から構成されている。図２に示されるように、１６個の最低使用頻度待ち行列１３８乃至１６８と、１６個のカウンタ１７０と、１つのグローバル・カウンタ１７２とは、ＬＲＵ待ち行列メンテナンス信号１２６を用いて、物理キャッシュ・ウィンドウ１０４に記憶されたデータに対するデータ使用およびアクセスを監視し、また追跡する。１６個の最低使用頻度待ち行列と、１６個のカウンタとが、図２に示されているが、ひとたび当業者が本発明の原理を理解した後には、当業者によって理解されるように、この説明は、他の数の最低使用頻度待ち行列と、他の数のカウンタとを有するそのような任意の装置に対しても適用可能であることを理解されたい。
【００１５】
どのくらいの頻度で物理キャッシュ・ウィンドウ１０４内のデータがアクセスされるかに応じて、物理キャッシュ・ウィンドウ１０４は、より高い、またはより低い最低使用頻度待ち行列１３８乃至１６８へと移動させられることになる。最低使用頻度待ち行列ブロック１２４内の最低使用頻度待ち行列１３８乃至１６８における、より高い優先順位への物理キャッシュ・ウィンドウ１０４の移動は、物理キャッシュ・ウィンドウ１０４の昇格と呼ばれる。最低使用頻度待ち行列１３８乃至１６８における、より低い優先順位への物理キャッシュ・ウィンドウ１０４の移動は、降格と呼ばれる。
【００１６】
図２においてさらに示されるように、最低使用頻度ブロック１２４のうちの最低使用頻度待ち行列１３８乃至１６８は、０が最低の優先順位を有し、１５が最高の優先順位を有する、０から１５の番号が付けられた優先順位待ち行列を割り当てられる。各最低使用頻度待ち行列１３８乃至１６８は、最低使用頻度リストを保持し、またカウンタ１７０は、どれだけ多くの降格された物理キャッシュ・ウィンドウ１０４が、最低使用頻度待ち行列１３８乃至１６８内に存在するか（物理キャッシュ・ウィンドウ１０４の降格は、後で考察されることになる）と、後で考察されるように、どの降格された物理キャッシュ・ウィンドウ１０４が、新しく割り付けられた物理キャッシュ・ウィンドウ１０４のために再使用され得るか、とを監視する。グローバル・カウンタ１７２は、すべての最低使用頻度待ち行列１３８乃至１６８にわたって存在する。
【００１７】
任意の新しく割り付けられた物理キャッシュ・ウィンドウ１０４が、最低優先順位の最低使用頻度待ち行列１３８乃至１６８の終わりに追加され、図２においては、これは、ＬＲＵ待ち行列０  １６８になる。データに対する３回の参照など、物理キャッシュ・ウィンドウ１０４の内部の特定の領域におけるデータに対する十分な参照のすぐ後に、物理キャッシュ・ウィンドウ１０４は、ＬＲＵ待ち行列０  １６８からＬＲＵ待ち行列１  １６６へなど、より高い優先順位の最低使用頻度待ち行列へと昇格され、また移動される。物理キャッシュ・ウィンドウ１０４は、物理キャッシュ・ウィンドウ１０４に記憶されたデータが、ある所定の期間中にアクセスされないときに、以前の優先順位の最低使用頻度待ち行列へと降格される。降格するとすぐに、物理キャッシュ・ウィンドウ１０４は、ＬＲＵ待ち行列１  １６６からＬＲＵ待ち行列０  １６８へなど、次の最低の最低使用頻度待ち行列に追加される。グローバル・カウンタ１７２を使用して、最低使用頻度待ち行列ブロック１２４内の降格された物理キャッシュ・ウィンドウ１０４の総数を追跡し続ける。所与の任意の時点において、ハッシュ・テーブル１３０と、カウンタ１７０と、グローバル・カウンタ１７２との通信に基づいて、最低使用頻度待ち行列ブロック１２４は、どれだけ多くの物理キャッシュ・ウィンドウ１０４が割り付けられているかについて、及びどれだけ多くの物理キャッシュ・ウィンドウ１０４が実際に降格されるかについて、を知っている。特定の最低使用頻度待ち行列１３８乃至１６８に関連するカウンタ１７０は、物理キャッシュ・ウィンドウ１０４がいくつかの最低使用頻度待ち行列１３８乃至１６８を通して降格されているかどうかを説明しないことになる。そのような物理キャッシュ・ウィンドウ１０４は、依然として降格としてカウントされるが、しかしながら、カウンタ１７０は、各最低使用頻度カウンタ１７０が、最低使用頻度待ち行列ブロック１２４内に存在する降格された物理キャッシュ・ウィンドウの現在の数を表すことになるように調整される。グローバル・カウンタ１７２は、物理キャッシュ・ウィンドウ１０４が、いくつかの最低使用頻度待ち行列１３８乃至１６８を通して降格されるときに、同じままに留まることになる。フラグは、ある物理キャッシュ・ウィンドウ１０４が降格されたときに、同じ最低使用頻度待ち行列１３８乃至１６８において昇格されまた降格された物理キャッシュ・ウィンドウを識別するために、物理キャッシュ・ウィンドウ１０４の上で使用される。そのフラグは、物理キャッシュ・ウィンドウ１０４が昇格されるときに、リセットされることになる。
【００１８】
より高い優先順位の最低使用頻度待ち行列１３８乃至１６８への物理キャッシュ・ウィンドウ１０４の昇格のすぐ後に、最低使用頻度待ち行列１３８乃至１６８と通信するカウンタ１７０は、減分される。そのようにして、物理キャッシュ・ウィンドウ１０４の昇格のレートが、物理キャッシュ・ウィンドウ１０４の降格レートに等しい場合、このレートは、キャッシュ・デバイス１０２の作業負荷がスラッシングを受けていることを示唆しており、これについては、後で考察されることになる。物理キャッシュ・ウィンドウ１０４の降格レートが、高い場合、これは、古くなり不要化したデータの存在を示す表示であり、これについても、後で考察されることになる。
【００１９】
以下で説明される指数関数的な時間減衰を使用して、物理キャッシュ・ウィンドウ１０４は、より高い優先順位の最低使用頻度待ち行列１３８乃至１６８から、より低い優先順位の最低使用頻度待ち行列１３８乃至１６８へと移動される。物理キャッシュ・ウィンドウ１０４が、より高い最低使用頻度待ち行列１３８乃至１６８から、次の優先順位の最低使用頻度待ち行列１３８乃至１６８へと降格されるときに、各最低使用頻度待ち行列１３８乃至１６８に対応するものと通信する個別のカウンタ１７０は、物理キャッシュ・ウィンドウ１０４の移動を監視し、また物理キャッシュ・ウィンドウ１０４が降格される場合に、カウンタは、１の値だけ上昇させられる。物理キャッシュ・ウィンドウがＬＲＵ待ち行列２  １６４からＬＲＵ待ち行列１  １６６へと降格される場合には、カウンタは、２の倍数だけ上昇させられる。同様に、物理キャッシュ・ウィンドウ１０４が、ＬＲＵ待ち行列１５  １３８からＬＲＵ待ち行列１４  １４０へと移動されるときに、カウンタ１７０は、物理キャッシュ・ウィンドウ１０４について１５だけ上昇させられる。これらの降格された物理キャッシュ・ウィンドウ１０４が昇格されるときに、カウンタ１７０についての適切な値は、物理キャッシュ・ウィンドウ１０４が、ＬＲＵ待ち行列１４からＬＲＵ待ち行列１５の最低使用頻度待ち行列へと昇格されるときに、カウンタ１７０が、物理キャッシュ・ウィンドウ１０４について１５だけ差し引かれるなど、調整される。
【００２０】
より新しいデータが、そのデータに対する繰り返された参照に基づいてホットであると見なされるので、データは、キャッシュ・デバイス１０２の上にコピーされ、また物理キャッシュ・ウィンドウ１０４に記憶される。最低使用頻度ブロック１２４と通信するハッシュ・テーブル１３０に従って、物理キャッシュ・ウィンドウ１０４が割付けのために使用可能でない場合には、最低使用頻度待ち行列ブロック１２４は、最低使用頻度待ち行列１３８乃至１６８によって受信される情報に基づいて、物理キャッシュ・ウィンドウ１０４内のデータが最も長い持続時間にわたってアクセスされていない場合の物理キャッシュ・ウィンドウ１０４を識別することになる。
【００２１】
ある期間にわたって、かつてはホットであった物理キャッシュ・ウィンドウ１０４に割り付けられ、また記憶されたあるデータは、場合によっては、ホスト・アプリケーションからのそれに対する、限られたアクセス、またはアクセスのないことに起因して、古くなり不要化したものになっている可能性がある。データはキャッシュされるが、降格の使用を通して、データの物理キャッシュ・ウィンドウ１０４は、最終的には、最低優先順位の最低使用頻度待ち行列、すなわち図２におけるＬＲＵ待ち行列０  １６８に位置することになる。新しいデータはホットになり、またキャッシュされる必要があるので、物理キャッシュ・ウィンドウ１０４において使用可能な場所がない場合、最低使用頻度待ち行列１３８乃至１６８の優先順位に基づいて、古くなり不要化したデータは、最低優先順位の最低使用頻度待ち行列、すなわち図２におけるＬＲＵ待ち行列０  １６８に位置する物理キャッシュ・ウィンドウ１０４から置換される。削除すべきデータを識別するために、最低使用頻度待ち行列ブロック１２４は、最低使用頻度待ち行列１３８乃至１６８と通信するカウンタ１７０を使用して、最低優先順位の最低使用頻度待ち行列、すなわち図２におけるＬＲＵ待ち行列０  １６８に位置するフラグが付けられた降格された物理キャッシュ・ウィンドウ１０４を識別する。識別された物理キャッシュ・ウィンドウ１０４内のデータは、次いで切り捨てられる。ホスト１１２からのより新しいホット・データ１１４が、今やターゲットにされ、キャッシュ・デバイス１０２のバック・エンドにある仮想キャッシュ・ウィンドウへと方向づけられる。最低使用頻度待ち行列ブロック１２４は、物理キャッシュ・ウィンドウ１０４を再使用し始める。ここで、この物理キャッシュ・ウィンドウ１０４においては、より新しいホット・データのために先ほどデータが切り捨てられており、物理キャッシュ・ウィンドウ１０４は、以前に最低優先順位のＬＲＵ待ち行列０  １６８に位置していたものである。
【００２２】
小さな隣接する物理キャッシュ・ウィンドウ１０４は、大きなグループ（２５６Ｋ、５１２Ｋ、または１ＭＢ）を形成するようにグループ化されることもある。物理キャッシュ・ウィンドウのこのグループ化は、最小基準のためにデータをハード・ディスク・ドライブ（ＨＤＤ）に到達させることなく、隣接するウィンドウのより高速なデータ・キャッシングを促進する。このグループ化は、１２８ＫＢなど、より小さな物理キャッシュ・ウィンドウ・サイズが１ＭＢ領域へのより高速な増強を見込むことが求められるときに、必要とされる。１２８ＫＢのサイズの物理キャッシュ・ウィンドウ１０４がホットであると考えられる場合には、最低使用頻度ブロック１２４は、自動的に、より小さな物理キャッシュ・ウィンドウの１ＭＢの境界内の隣接する物理キャッシュ・ウィンドウを同様にホットであるように考えることになる。これは、キャッシングが最初にイネーブルにされるときに、より高速なキャッシュが増強されるように行われる。本開示のシステムは、物理キャッシュ・ウィンドウ・サイズが、１ＭＢのデフォルト値とともに、１２８ＫＢ、５１２ＫＢ、１ＭＢ、２ＭＢおよび４ＭＢであることを可能にしている。
【００２３】
ある期間にわたって、かつてはホットであったあるキャッシュされたデータは、ホスト１１２またはアプリケーションからのデータに対する、限られたアクセス、またはアクセスのないことに起因して、場合によっては古くなり不要化したものになるであろう。データは、物理キャッシュ・ウィンドウ１０４においてキャッシュされるが、データの物理キャッシュ・ウィンドウ１０４は、最低優先順位の最低使用頻度待ち行列、すなわち最低使用頻度待ち行列ブロック１２４内の図２におけるＬＲＵ  ０  １６８に位置することになる。システムが、最低使用頻度待ち行列ブロック１２４に基づいて、物理キャッシュ・ウィンドウ１０４において使用可能な追加の場所がないことを識別する場合、古くなり不要化したデータは、より新しいホット・データによって置換されることになる。古くなり不要化したデータは、どれだけのホット・データがある期間にわたってアクティブにアクセスされているかを理解すること、として定義され得る。これは、最低使用頻度待ち行列ブロック１２４とブロック１２４内の最低使用頻度の待ち行列またはバケットとを使用して、達成することができる。物理キャッシュ・ウィンドウが、そのキャッシュ・データに対するより少ないアクセスに起因して降格されるときはいつでも、最低使用頻度の待ち行列またはバケットに割り当てられるカウンタは、どれだけ多くのキャッシュ・ウィンドウが、現在、降格された状態にあるかを理解するように保持されることになる。図２に示されるように、２組のカウンタ、すなわち、ＬＲＵの待ち行列またはバケット１３８乃至１６８当たりに１つのカウンタ１７０と、グローバル・カウンタ１７２とが、存在している。現在降格されている物理キャッシュ・ウィンドウ１０４は、特別なフラグを用いて、そうであるものとしてマーク付けされる。降格された物理キャッシュ・ウィンドウ１０４が、新しいアクセスに起因して、再び昇格されるときはいつでも、未処理の降格されたカウンタは、それに応じて調整され、またフラグは、リセットされることになる。任意の所与の時刻に、全体の降格された物理キャッシュ・ウィンドウが、ゼロに等しくない場合、これは、ある量の古くなり不要化したデータが存在することを示すものである。任意の占有された物理キャッシュ・ウィンドウが存在する場合、または、古くなり不要化したデータが物理キャッシュ・ウィンドウ内に存在する場合には、ホットとして考えられるべきデータ領域（図１の仮想キャッシュ・ウィンドウ１２０）についての必要条件は、現在割り付けられている物理キャッシュ・ウィンドウ１０４の状態に依存することになる。使用されるべき自由な物理キャッシュ・ウィンドウ１０４、または古くなり不要化した（降格された）物理キャッシュ・ウィンドウ１０４が最低使用頻度待ち行列ブロック１２４の上に存在する場合には、しきい値は、３に設定されることになる。それゆえに、仮想キャッシュ・ウィンドウ１２０内のデータをキャッシュ可能と考えるべき必要条件は、デフォルト・アクセス・カウントの３倍（すなわち、そのそれぞれの領域に対する９回の読取りアクセス）を必要とすることになる。自由な物理キャッシュ・ウィンドウ１０４または降格された物理キャッシ��・ウィンドウ１０４がない場合には、必要とされるしきい値はより高くなる。例えば、デフォルト値の３倍、あるいはデータに対する９回の参照またはアクセスになるであろう。
【００２４】
場合によっては、ホット・データは、キャッシュ・デバイス１０２についての容量よりも大きくなることになる。物理キャッシュ・ウィンドウ１０４、１０６、１０８および１１０が、データのキャッシングのために選択されるときに、最低使用頻度待ち行列ブロック１２４のうちのより低い優先順位の最低使用頻度待ち行列１３８乃至１６８によって識別されるような物理キャッシュ・ウィンドウ内のあるデータは、切り捨てられることが必要になる。データのサイズに起因して、切り捨てられたデータは、再び迅速にホットになり、スラッシングと呼ばれる、新しいデータと切り捨てられたデータとのサイクルを作り出す。
【００２５】
スラッシング・モードにあるシステムについて補償するために、システムは、２つのやり方でデータのキャッシングに取り組むことができる。第１の方法においては、データは、最低優先順位の最低使用頻度待ち行列内の物理キャッシュ・ウィンドウから置換され、またその後により早いレートで新しい物理キャッシュ・ウィンドウに記憶される。第２の方法においては、データをホットとして識別するために必要とされる参照の回数は、例えば３回の参照から９回の参照などに修正され、その結果、新しいホット・データの記憶のために最低優先順位の最低使用頻度待ち行列から物理キャッシュ・ウィンドウに割り付けられ、または記憶されるようにするためは、データの９回の参照を要する。いくつかの例においては、システムは、システムがスラッシング・モードにある間に、物理キャッシュ・ウィンドウに対するデータのすべての割付けまたは記憶を停止させる可能性さえもある。
【００２６】
図３は、本開示のキャッシュ・デバイスへのデータ入力のキャッシングの流れ図３００を提供するものである。ステップ３０２において、データは、キャッシュ・デバイスへと入力される。ステップ３０４において、データは、キャッシュ・デバイスの仮想キャッシュ・ウィンドウまたはバックグラウンド領域に割り付けられ、またキャッシュ・デバイスの仮想キャッシュ・ウィンドウまたはバックグラウンド領域よって追跡される。ステップ３０６において、仮想キャッシュ・ウィンドウ内のデータが、外部ホストによって繰り返して、通常ではデータに対して少なくとも３回の参照で、アクセスされるときに、仮想キャッシュ・ウィンドウ内のデータは、物理キャッシュ・ウィンドウへと変換され、または送信され、ここでデータは、物理キャッシュ・ウィンドウに割り当てられ、また記憶される。ひとたび仮想キャッシュ・ウィンドウからのデータが、仮想キャッシュ・ウィンドウから取り除かれた後に、仮想キャッシュ・ウィンドウは、新しいデータが仮想キャッシュ・ウィンドウに割り付けられ、またその中で追跡されることを自由に許すことができる。ステップ３０８においては、１６個の最低使用頻度の待ち行列またはバケットを備える最低使用頻度待ち行列（ＬＲＵ）ブロックが保持され、またそれは、すべての物理キャッシュ・ウィンドウにわたって、データに対するアクセスを監視する。ステップ３１０において、最低使用頻度待ち行列（ＬＲＵ）ブロックは、どれくらいの頻度で物理キャッシュ・ウィンドウ内のデータがアクセスされるか、および／またはいつデータは最後にアクセスされたかに応じて、物理キャッシュ・ウィンドウに記憶されたデータに優先順位を付ける。
【００２７】
図４に示されるように、物理キャッシュ・ウィンドウ内のデータの優先順位付けを示す流れ図４００が、提供されている。ステップ４０２において、最低使用頻度待ち行列ブロックは、各物理キャッシュ・ウィンドウに優先順位を付ける。ステップ４０４において、すべての物理キャッシュ・ウィンドウが、最低使用頻度待ち行列ブロックの最低使用頻度待ち行列（ＬＲＵ待ち行列）に挿入され、その結果、物理キャッシュ・ウィンドウは、キャッシュ・ドライバのキャッシュ容量として再使用されることもあるようになり、またはキャッシュ・デバイスは、実際の物理的容量、またはハード・ディスク容量よりもずっと小さくなる。すべての物理キャッシュ・ウィンドウについての１つの単一の最低使用頻度の待ち行列またはバケットを保持するのではなくて、本開示は、すべての物理キャッシュ・ウィンドウについての１６個の最低使用頻度待ち行列を提供している。おのおのの最低使用頻度の待ち行列またはリストは、ＬＲＵバケットを表しており、ここで各最低使用頻度待ち行列は、低位（０）から高位（１５）に及ぶ優先順位を用いて優先順位が付けられる。最初に、すべての物理キャッシュ・ウィンドウが、最低の優先順位を有する最低使用頻度待ち行列、この場合にはＬＲＵ待ち行列０へと挿入される。ステップ４０６において、物理キャッシュ・ウィンドウ内のキャッシュされたデータに対するある量の参照またはアクセスを受信するとすぐに、物理キャッシュ・ウィンドウは、最低優先順位の最低使用頻度待ち行列からより高い優先順位のリストへと移動される。より低い最低使用頻度待ち行列からより高い最低使用頻度待ち行列への物理キャッシュ・ウィンドウの移動は、昇格と呼ばれる。ステップ４０８において、物理キャッシュ・ウィンドウが、ある長さの時間にわたってアクセスされていないときに、最低使用頻度待ち行列ブロックは、物理キャッシュ・ウィンドウ内のデータがアクセスされておらず、また物理キャッシュ・ウィンドウは、現在の最低使用頻度待ち行列からより低い最低使用頻度待ち行列へと移動されることを識別する。より高い最低使用頻度待ち行列から、より低い最低使用頻度待ち行列への物理キャッシュ・ウィンドウの移動は、降格と呼ばれる。デフォルトの必要条件または高い必要条件というよりもむしろ物理キャッシュ・ウィンドウの降格についての動的レートを有するために、降格重みファクタは、物理キャッシュ・ウィンドウを降格するときに使用される。物理キャッシュ・ウィンドウが、最高優先順位の物理キャッシュ・ウィンドウから次の優先順位の物理キャッシュ・ウィンドウへと降格されるときに、降格された物理キャッシュ・ウィンドウに関連する各最低使用頻度優先順位待ち行列に関連するカウンタは、１の値だけ上昇させられ、またフラグは、物理キャッシュ・ウィンドウにアタッチされる。物理キャッシュ・ウィンドウが、２つの最低使用頻度優先順位待ち行列だけ降格される場合には、最低使用頻度優先順位待ち行列に関連するカウンタは、２の倍数だけ上昇させられ、または増大させられる。同様に、物理キャッシュ・ウィンドウが、１５番目の最低使用頻度待ち行列から１４番目の最低使用頻度待ち行列へと移動されるときに、カウンタは、物理キャッシュ・ウィンドウごとに１５だけ増大させられる。これらの降格された物理キャッシュ・ウィンドウが、昇格されるときに、適切な値が、調整される。ステップ４１０において、ある期間にわたって、かつてはホットであったあるデータは、アプリケーションからのそれに対する限られたアクセス、またはアクセスがないことに起因して、場合によっては古くなり不要化したものになってしまう可能性がある。データは、キャッシュされるが、降格の使用を通して、データの物理キャッシュ・ウィンドウは、最終的には、最低優先順位の最低使用頻度待ち行列に位置している。ステップ４１２において、新しいデータはホットになり、またキャッシュされる必要があるので、物理キャッシュ・ウィンドウにおいて使用可能な場所がない場合、最低使用頻度待ち行列優先順位に基づいて、古くなり不要化したデータは、最低優先順位の最低使用頻度待ち行列内に位置する物理キャッシュ・ウィンドウから取り除かれる。本システムは、最低優先順位の最低使用頻度待ち行列からのより新しいホット・データのために物理キャッシュ・ウィンドウを再使用する。
【００２８】
図５において、本開示のシステムがスラッシング・モードにあるかどうかを識別するためのステップを示す流れ図５００が、提供されている。ステップ５０２において、ホット・データが、キャッシュ・デバイスに追加されるが、新しいデータは、キャッシュ・デバイスのキャッシング容量よりも大きい。ステップ５０４において、データをキャッシュするために使用可能な未使用の物理キャッシュ・ウィンドウが、存在しておらず、また最低優先順位の最低使用頻度待ち行列内の物理キャッシュ・ウィンドウから取り除くために使用可能な、古くなり不要化したデータがない場合には、システムはスラッシング・モードになる。ステップ５０６において、スラッシング・モードにあるシステムについて補償するために、最低優先順位の最低使用頻度待ち行列内の物理キャッシュ・ウィンドウからデータは取り除かれ、その後により高速のレートで新しい物理キャッシュ・ウィンドウに記憶される。ステップ５０８において、スラッシング・モードを処理するための代替的な方法は、ホットとしてデータを識別するために必要とされる参照の回数が修正され、一例が、３回の参照から９回の参照への可能性があり、その結果として、新しいホット・データの記憶のために、最低優先順位の最低使用頻度待ち行列からの物理キャッシュ・ウィンドウに記憶されるべきシステムからのデータについて、９回の参照を要することである。いくつかの例においては、本システムは、システムがスラッシング・モードにある間に、物理キャッシュ・ウィンドウに対するデータのすべての割付けまたは記憶を停止させる可能性さえある。
【００２９】
図６に示されるように、システム内に任意の古くなり不要化しているキャッシュされたデータが存在するかどうか、またはスラッシングが行われているかどうかを検出するロジックを示す流れ図６００が、提供されている。ステップ６０２において、最低使用頻度優先順位待ち行列は、どれだけの各物理キャッシュ・ウィンドウに記憶されたデータが時間とともにアクティブにアクセスされているかを監視する。ステップ６０４において、最低使用頻度優先順位待ち行列と通信するカウンタによるデータ使用の監視に基づいてデータがより低い優先順位になるにつれて、物理キャッシュ・ウィンドウは、最低使用頻度待ち行列において降格される。最低使用頻度待ち行列ブロック内のすべての１６個の最低使用頻度待ち行列のために割り付けられる追加の待ち行列を用いて、１つのカウンタが最低使用頻度待ち行列ごとに割り付けられる。上記で論じられているように、物理キャッシュ・ウィンドウが最高優先順位の物理キャッシュ・ウィンドウから次の優先順位の物理キャッシュ・ウィンドウへと降格されるときに、降格された物理キャッシュ・ウィンドウに関連する各最低使用頻度優先順位待ち行列に関連するカウンタは、１の値だけ上昇させられる。物理キャッシュ・ウィンドウが、２つの最低使用頻度優先順位待ち行列だけ降格される場合には、最低使用頻度優先順位待ち行列に関連するカウンタは、２の倍数だけ上昇させられ、また最低使用頻度待ち行列は、どの最低使用頻度待ち行列が降格された物理キャッシュ・ウィンドウの現在のロケーションを占めているかを示している。しかしながら、グローバル・カウンタは、同じままに留まる。同様に、物理キャッシュ・ウィンドウが、１４番目の最低使用頻度待ち行列から１５番目の最低使用頻度待ち行列へと移動されるときに、カウンタは、１５だけ上昇させられ、また次いで物理キャッシュ・ウィンドウの現在のロケーションを占める待ち行列を示すことになる。この計算は、キャッシュ・ウィンドウが部分的に満たされているかどうか、古くなり不要化したキャッシュされたデータが存在するかどうか、またはシステムがスラッシング・モードにあり、またそれゆえにキャッシング・レートのスロットリング（制御・抑制）を達成しているかどうかについての理解を提供する。ステップ６０６において、重みファクタに基づいて、降格された物理キャッシュ・ウィンドウの総数がゼロよりも大きく、また自由な物理キャッシュ・ウィンドウの総数がゼロに等しい場合には、ステップ６０８に示されるように、物理キャッシュ・ウィンドウにキャッシュされた古くなり不要化したデータが存在している。ステップ６１０において、降格された物理キャッシュ・ウィンドウの総数がゼロに等しく、また自由な物理キャッシュ・ウィンドウの総数がゼロに等しい場合には、ステップ６１２に示されるように、システムはスラッシング・モードにある。ステップ６１４において、降格された物理キャッシュ・ウィンドウの総数がゼロに等しく、また自由な物理キャッシュ・ウィンドウの総数がゼロよりも大きい場合には、ステップ６１６に示されるように、システムは割付けのために使用可能な自由なキャッシュ・ウィンドウを有する。
【００３０】
本発明の上記説明は、例証および説明の目的のために提示されている。網羅的であること、または本発明を開示される正確な形態だけに限定することは意図してはおらず、また他の修正形態および変形形態も、上記の教示を考慮して可能とすることができる。実施形態は、本発明の原理とその実用的な応用とを最もよく説明して、それによって他の当業者が、企図される特定の使用に適しているように、様々な実施形態および様々な修正形態において本発明を最も良く利用することを可能にするようにするために選択され、また説明されている。添付の特許請求の範囲は、先行技術によって限定される場合を除いて、本発明の他の代替的な実施形態を含むように解釈されることが意図される。
【図１】
2014154138.tif 000003
【図２】
2014154138.tif 000004
【図３】
2014154138.tif 000005
【図４】
2014154138.tif 000006
【図５】
2014154138.tif 000007
【図６】
2014154138.tif 000008