(57)【要約】【課題】第１のキャッシュおよび第２のキャッシュのデータを管理するためのコンピュータ・プログラム製品、システム、および方法を提供すること。【解決手段】ページが第２のキャッシュに記憶されたときにページについて第２のキャッシュに参照カウントを維持する。ページを第２のキャッシュから第１のキャッシュにプロモートすることを決定する。参照カウントがゼロより大きいと判定するのに応じて、ページを、第１のキャッシュ内のＬＲＵリストのＬＲＵ（Least Recently Used）側に追加する。参照カウントがゼロ以下と判定するのに応じて、ページを、第１のキャッシュ内のＬＲＵリストのＭＲＵ（Most Recently Used）側に追加する。【選択図】図８
2015516613.tif 000002
【特許請求の範囲】
【請求項１】
第１のキャッシュおよび第２のキャッシュのデータを管理する方法であって、
コンピュータのプロセッサを使用して、ページが前記第２のキャッシュに記憶されたときに前記ページについて前記第２のキャッシュに参照カウントを維持するステップと、
前記ページを前記第２のキャッシュから前記第１のキャッシュにプロモートすることを決定するステップと、
前記参照カウントがゼロより大きいと判定するのに応じて、前記ページを、前記第１のキャッシュ内のＬＲＵリストのＬＲＵ（Least Recently Used）側に追加するステップと、
前記参照カウントがゼロ以下と判定するのに応じて、前記ページを、前記第１のキャッシュ内の前記ＬＲＵリストのＭＲＵ（Most Recently Used）側に追加するステップと
を含む方法。
【請求項２】
前記第１のキャッシュおよび前記第２のキャッシュがストレージに結合される、請求項１に記載の方法。
【請求項３】
前記第１のキャッシュが前記第２のキャッシュよりも高速にアクセスできるデバイスであり、前記第２のキャッシュが前記ストレージよりも高速にアクセスできるデバイスである、請求項１または請求項２に記載の方法。
【請求項４】
前記第１のキャッシュがランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２のキャッシュがフラッシュ・デバイスを含み、前記ストレージが順次書き込みデバイスを含む、請求項１に記載の方法。
【請求項５】
前記参照カウントが第１の参照カウントを含み、前記方法がさらに、
前記ページが前記第１のキャッシュに記憶されたときに前記ページについて前記第１のキャッシュに第２の参照カウントを維持するステップを含み、前記第１のキャッシュにある前記ページについての前記第２の参照カウントは、前記第１のキャッシュで前記ページが参照されるたびに増分される、請求項１ないし４のいずれかに記載の方法。
【請求項６】
前記第２のキャッシュで前記ページが参照されるたびに前記第２のキャッシュ内の前記ページの前記参照カウントを減分するステップをさらに含む、請求項１ないし５のいずれかに記載の方法。
【請求項７】
前記参照カウントが第１の参照カウントを含み、前記方法がさらに、
前記ページが前記第１のキャッシュから前記第２のキャッシュにデモートされると決定されるのに応じて、
前記第１の参照カウントがゼロ未満であるかどうかを判定するステップと、
前記第１の参照カウントがゼロ未満であると判定されるのに応じて、前記第１の参照カウントを、第２の参照カウントに定数（ｋ）を乗じた値に等しく設定するステップと
を含む、請求項１に記載の方法。
【請求項８】
第１のキャッシュおよび第２のキャッシュのデータを管理するコンピュータ・プログラム製品であって、実行されると請求項１ないし７のいずれかに記載の方法を行うコンピュータ可読プログラム・コードが具現化されたコンピュータ可読記憶媒体を含むコンピュータ・プログラム製品。
【請求項９】
データを管理するシステムであって、
第１のキャッシュと、
第２のキャッシュと、
プロセッサと、
前記プロセッサに実行されて、請求項１ないし７のいずれかに記載の方法を行うコードを有するコンピュータ可読記憶媒体と
を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２レベルのキャッシュ・システムにおける適合的なキャッシュのプロモートに関する。
【背景技術】
【０００２】
キャッシュ管理システムは、読出し動作および書き込み動作の結果最近アクセスされた記憶装置内のページを、要求されたページを記憶している記憶装置よりも高速にアクセスできるメモリなどの記憶装置にバッファしておく。後にアクセスが高速なキャッシュ・メモリのページに読出し要求があると、そのページは、アクセスに時間がかかるストレージから要求されるページを返す場合よりも速い速度で返され、それにより読み出しの待ち時間が短縮される。キャッシュ管理システムは、記憶装置を行き先とする変更後のページがキャッシュ・メモリに書き込まれたときに、変更されたページがハード・ディスク・ドライブなどの記憶装置に書き出される前に、書き込み要求の完了を返すこともできる。記憶装置に書き込む際の待ち時間は、通例、キャッシュ・メモリに書き込みを行う際の待ち時間と比べて大幅に長い。そのため、キャッシュを使用すると書き込みの待ち時間も短縮する。
【０００３】
キャッシュ管理システムは、キャッシュに記憶されたページごとに１つのエントリを持つ連結リストを保持することができ、この連結リストは、記憶装置に書き込む前にキャッシュにバッファされている書き込みデータか、または読み出されたデータを含むことができる。一般に使用されるＬＲＵ（Least Recently Used：最も過去に使用された）方式のキャッシュ技術では、キャッシュのページがアクセスされる、すなわちキャッシュ「ヒット」があると、アクセスされたページに対応するＬＲＵリストのエントリがリストのＭＲＵ（Most Recently Used：最近使用された）側に移動される。要求されるページがキャッシュにない場合、すなわちキャッシュ・ミスの場合は、エントリがリストのＬＲＵ側にあるキャッシュのページを削除する（またはデステージ（destage）してストレージに戻す）ことができ、ストレージからキャッシュにステージされたページ・データのエントリをＬＲＵリストのＭＲＵ側に追加する。このＬＲＵキャッシュ技術では、より頻繁にアクセスされるページがキャッシュ内に残る可能性が高く、アクセスの頻度が少ないデータはリストのＬＲＵ側から削除されて、新たにアクセスされるページのためにキャッシュに余地を作る可能性が高い。
【０００４】
ＬＲＵキャッシュ技術は、デステージ動作の回数を最小にするために、近いうちに再書き込みされる可能性が最も低いページをデステージするように時間的な局所性をシークして最適化する。つまり、デステージされない書き込みが上書きされると、その上書きされた書き込みのデステージが回避され、それによりそのデータをキャッシュからディスクに書き込む時間と手間が節減される。一方で、空間的な局所性を活用するようにデステージすることも求められる。つまり、データを互いに最も近い記憶場所に書き込むことにより、次の書き込みを行う記憶場所に到達するために記憶装置の書き込み機構と記憶媒体を移動しなければならない距離を最小にする。
【０００５】
時間的な局所性と空間的な局所性の両方を利用する技術の１つはＷＯＷ（WiseOrdering for Writes）アルゴリズムである。ＷＯＷアルゴリズムは循環連結リストまたはクロックを用い、循環連結リストにはキャッシュにバッファされた書き込み要求ごとに１つのエントリがある。エントリは関連する書き込み要求が行き先とする記憶場所に従って連結リスト内で順序付けして、空間的な局所性の利点を活かす。さらに、各エントリは、キャッシュ内の記憶場所に対応する書き込みデータが最近更新されたかどうかを示すビットを含む。エントリに対応するビットは、そのエントリの書き込みデータが更新されたときに設定される。ポインタが循環連結リスト内の現在のエントリを指す。ＷＯＷアルゴリズムを使用するタスクは、このポインタでアドレス指定されるエントリにアクセスする。エントリのビットが、キャッシュ内でそのエントリのデータが最近更新されたことを示すと、書き込みデータが最近更新されていないと示すようにビットを設定し、ポインタを増分して次のエントリを指すようにして、前回書き込まれた記憶場所に空間的に次に近い記憶場所に書き込むデータを持つエントリが考慮されるようにする。前回書き込みが行われた記憶場所に空間的に最も近く、かつビットがそのエントリの書き込みデータが最近更新されていないことを示すエントリが書き込みのために選択される。
【０００６】
そのようにして最後にデステージされた書き込み要求に空間的に最も近いエントリが次の書き込み対象として選択されるため、ＷＯＷアルゴリズムでは空間的な局所性が活かされる。さらに、最近書き込まれたエントリはポインタが一周してそのエントリを検討対象として指すまでスキップされるため、時間的な局所性も活かされる。
【０００７】
ディスク・ドライブは、ＷＯＷアルゴリズム、および書き込みページの線形位置と角度位置の両方を考慮し、現在の書き込みヘッドの位置に対して両方を最適化して最小の合計サービス時間を決定する他のアルゴリズムを実装することができる。この処理は、「シークと回転の最適化に基づくコマンドの並べ替え」と呼ばれる。ディスク・ドライブのロジック・ボードは書き込み要求を分析し、各種のシリンダと書き込むページの角度位置までシークするために要する時間と、データが回転してヘッドの下に来るのを待つ時間の両方に基づいて、どの要求を最初に処理するかを決定する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
当技術分野では、２レベルのキャッシュ・システムを使用するための改良された技術が必要とされる。
【課題を解決するための手段】
【０００９】
第１のキャッシュおよび第２のキャッシュのデータを管理するためのコンピュータ・プログラム製品、システム、および方法が提供される。ページが第２のキャッシュに記憶されたときにページについて第２のキャッシュに参照カウントを維持する。ページを第２のキャッシュから第１のキャッシュにプロモート（promote）することを決定する。参照カウントがゼロより大きいと判定するのに応じて、ページを、第１のキャッシュ内のＬＲＵリストのＬＲＵ（Least Recently Used）側に追加する。参照カウントがゼロ以下であると判定するのに応じて、ページを、第１のキャッシュ内のＬＲＵリストのＭＲＵ（Most Recently Used）側に追加する。
【００１０】
以下で添付図面を参照して単なる例として本発明の実施形態を説明する。
【図面の簡単な説明】
【００１１】
【図１】コンピューティング環境の一実施形態の図である。
【図２】第１のキャッシュ管理情報の一実施形態の図である。
【図３】第２のキャッシュ管理情報の一実施形態の図である。
【図４】第１のキャッシュ制御ブロックの一実施形態の図である。
【図５】第２のキャッシュ制御ブロックの一実施形態の図である。
【図６】空間インデックス・エントリの一実施形態の図である。
【図７】第１のキャッシュから無変更のページをデモート（demote）する動作の一実施形態を説明する図である。
【図８】第１のキャッシュから変更ページをデステージする動作の一実施形態を説明する図である。
【図９】第１のキャッシュにページを追加する動作の一実施形態を説明する図である。
【図１０】第２のキャッシュにページをプロモートする動作の一実施形態を説明する図である。
【図１１】第２のキャッシュの空間を解放する動作の一実施形態を説明する図である。
【図１２】第２のキャッシュから変更ページをデステージする動作の一実施形態を説明する図である。
【図１３】読出し要求に対して返すページの要求を処理する動作の一実施形態を説明する図である。
【図１４】２レベルのキャッシュ・システムおよびストレージの一実施形態の図である。
【図１５】第２のキャッシュから第１のキャッシュにページを追加する動作の一実施形態を説明する図である。
【発明を実施するための形態】
【００１２】
図１は、コンピューティング環境の一実施形態を示す。複数のホスト２ａ、２ｂ、．．．２ｎが、ネットワーク６を通じてストレージ・コントローラ４に入出力（Ｉ／Ｏ）要求を発行して、ストレージ・コントローラ４に結合されたストレージ１０のボリューム８（例えば、論理単位番号、論理デバイス、論理サブシステム等）でデータにアクセスすることができる。ストレージ・コントローラ４はプロセッサ複合体１２を含み、プロセッサ複合体１２は、シングル・コアまたはマルチ・コアの１つまたは複数のプロセッサ、第１のキャッシュ１４、キャッシュ１４のページをバックアップする第１のキャッシュ・バックアップ・デバイス１６、および第２のキャッシュ１８を含む。第１のキャッシュ１４および第２のキャッシュ１８は、ホスト２ａ、２ｂ、．．．２ｎとストレージ１０との間で転送されるデータをキャッシュする。第１のキャッシュ・バックアップ・デバイス１６は、第１のキャッシュ１４のページの不揮発性のストレージを提供することができる。他の実施形態では、第１のキャッシュ・バックアップ・デバイス１６は、第１のキャッシュ１４とは異なる電力境界にあるクラスタまたはハードウェアに配置することができる。
【００１３】
ストレージ・コントローラ４はメモリ２０を有し、メモリ２０は、ホスト２ａ、２ｂ、．．．２ｎとストレージ１０間で転送されるページの転送を管理するストレージ・マネジャ２２と、第１のキャッシュ１４、第１のキャッシュ・バックアップ・デバイス１６、および第２のキャッシュ１８でホスト２ａ、２ｂ、．．．２ｎとストレージ１０間で転送されるデータを管理するキャッシュ・マネジャ２４とを含む。ページは、ページや論理ブロック・アドレス（ＬＢＡ）等のストレージ１０で設定される任意のデータ単位からなっていてもよく、ページは、ボリュームや論理デバイス等のより大きなページのグループ化の一部である。キャッシュ・マネジャ２４は、第１のキャッシュ管理情報２６および第２のキャッシュ管理情報２８を保持して、第１のキャッシュ１４および第２のキャッシュ１８における読み出し（無変更）と書き込み（変更）ページを管理する。第１のキャッシュ・バックアップ・デバイス・インデックス３０は、第１のキャッシュ・バックアップ・デバイス１６内の位置を示すページ識別子のインデックスを提供する。
【００１４】
図１では、ストレージ・マネジャ２２およびキャッシュ・マネジャ２４は、メモリ２０にロードされてプロセッサ複合体１２で実行されるプログラム・コードとして示している。それに代えて、機能の一部またはすべてを特定用途集積回路（ＡＳＩＣ）等のストレージ・コントローラ４内のハードウェア・デバイスとして実装してもよい。
【００１５】
第２のキャッシュ１８は、ログ構造配列（ＬＳＡ）３２でページを記憶することができ、ページは受け取られた順序で書き込まれ、それにより第２のキャッシュ１８に書き込まれるページの時間的な順序付けを提供する。ＬＳＡでは、ＬＳＡにすでにあるページのより新しいバージョンはＬＳＡ３２の最後に書き込まれる。代替実施形態では、第２のキャッシュ１８はＬＳＡ以外の形式でデータを記憶することができる。
【００１６】
ある実施形態では、第１のキャッシュ１４は動的ランダム・アクセス・メモリ（ＤＲＡＭ）等のランダム・アクセス・メモリ（ＲＡＭ）であってもよく、第２のキャッシュ１８は固体素子デバイス等のフラッシュ・メモリであってもよく、ストレージ１０は、ハード・ディスク・ドライブや磁気テープ等の１つまたは複数の順次アクセス記憶装置からなる。ストレージ１０は、１つの順次アクセス記憶装置からなっても、ＪＢＯＤ（Just a Bunch of Disks）、ダイレクト・アクセス記憶装置（ＤＡＳＤ）、ＲＡＩＤ（Redundant Array of Independent Disks）アレイ、仮想化装置等の記憶装置の配列からなってもよい。ストレージ１０は、第１のキャッシュ１４および第２のキャッシュ１８の少なくとも１つに結合される。ある実施形態では、第１のキャッシュ１４は第２のキャッシュ１８より高速にアクセスできるデバイスであり、第２のキャッシュ１８はストレージ１０より高速にアクセスできるデバイスである。さらに、第１のキャッシュ１４は第２のキャッシュ１８よりも記憶単位あたりのコストが高く、第２のキャッシュ１８はストレージ１０の記憶装置よりも記憶単位あたりのコストが高い場合がある。さらに、ある実施形態では、第２のキャッシュ１８は第１のキャッシュ１４よりもはるかに大きい場合がある。
【００１７】
第１のキャッシュ１４は、メモリ２０の一部としても、または、ＤＲＡＭなど、別個のメモリ装置に実装してもよい。ある実施形態では、第１のキャッシュ・バックアップ・デバイス１６は、不揮発性のメモリ、例えば、バッテリでバックアップされたランダム・アクセス・メモリ（ＲＡＭ）、静的ＲＡＭ（ＳＲＡＭ）などの不揮発性バックアップ・ストレージ（ＮＶＳ）から構成することができる。
【００１８】
ネットワーク６は、ストレージ・エリア・ネットワーク（ＳＡＮ）、ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット等からなることができる。
【００１９】
本明細書の実施形態のいくつかではページのキャッシュ・インデックスの粒度を参照するが、他の実施形態は、トラックやエクステントなどの異なるキャッシュ・インデックスの粒度のデータに適用される。
【００２０】
図２は、第１のキャッシュ管理情報２６の一実施形態の図であり、キャッシュ管理情報２６は、制御ブロック・ディレクトリ５２のブロックを制御する第１のキャッシュ１４のページのインデックスを提供するページ・インデックス５０、第１のキャッシュ１４で無変更の連続したページの時間的な順序付けを提供する無変更連続ＬＲＵリスト５４、第１のキャッシュ１４で変更された連続したページおよび不連続ページの時間的な順序付けを提供する変更ＬＲＵリスト５６、第１のキャッシュ１４で無変更の不連続ページの時間的な順序付けを提供する無変更不連続ＬＲＵリスト５８、参照カウンタ６０、および高速ＬＲＵ６２を含む。
【００２１】
図３は、第２のキャッシュ管理情報２８の一実施形態を示し、キャッシュ管理情報２８は、制御ブロック・ディレクトリ７２のブロックを制御する第２のキャッシュ１８のページのインデックスを提供するページ・インデックス７０、第２のキャッシュ１８の無変更のページの時間的な順序付けを提供する無変更リスト７４、ストレージ１０内で変更ページが記憶された物理的な位置に基づいて第２のキャッシュ１８の変更ページの空間的な順序付けを提供する空間インデックス７６、および参照カウンタ７８を含む。
【００２２】
ＬＲＵリスト５４、５６、５８、および７４はすべて、特定されたページが前回アクセスされた時間に従って順序付けされた第１のキャッシュ１４および第２のキャッシュ１８内のページのページＩＤを含むことができる。ＬＲＵリスト５４、５６、５８、および７４は、一番最近アクセスされたページを示すＭＲＵ（most recently used：一番最近使用された）側と、最も長く使用またはアクセスがないページを示すＬＲＵ側とを有する。キャッシュ１４および１８に追加されるページのページＩＤは（ページの「熱さ（heat）」に応じて）ＬＲＵリストのＭＲＵ側かＬＲＵ側のどちらかに追加され、キャッシュ１４および１８からデモートされたページはＬＲＵ側からアクセスされる。ページ・インデックス５０および７０、ならびに空間インデックス７６は、スキャッタ・インデックス・テーブル（ＳＩＴ）を構成することができる。代替の種類のデータ構造を使用してキャッシュ１４および１８におけるページの時間的な順序付けと、第２のキャッシュ１８のページの空間的な順序付けを提供することができる。
【００２３】
不連続のページはＯＬＴＰ（Online Line TransactionProcessing）ページ等であり、これは多くの場合、完全にはランダムでなく参照に多少の局所性がある、すなわち繰り返しアクセスされる可能性がある小さなブロックの書き込みである。
【００２４】
図４は、制御ブロック・ディレクトリ５２の第１のキャッシュ制御ブロック１００のエントリの一実施形態の図であり、制御ブロック識別子（ＩＤ）１０２、第１のキャッシュ１４内のページの物理的な位置である第１のキャッシュ位置１０４、ページが変更されているか無変更であるかを示す情報１０６、およびページが順次アクセスであるか不連続のアクセスであるかを示す情報１０８を含む。
【００２５】
図５は、第２のキャッシュ制御ブロック・ディレクトリ７２の第２のキャッシュ制御ブロック１２０のエントリの一実施形態の図であり、制御ブロック識別子（ＩＤ）１２２、ＬＳＡ３２内のページが位置するＬＳＡ位置１２４、およびページが変更されているか無変更であるかを示す情報１２６を含む。
【００２６】
図６は空間インデックス・エントリ１４０の一実施形態を示し、これは、第２のキャッシュ１８のページのページ識別子１４２、およびシリンダ、プラッタ、ブロック・アドレス、記憶装置の識別子など、ストレージ１０のページが記憶された物理的な位置１４４を含む。
【００２７】
図７は、第１のキャッシュ１４から無変更のページをデモートするためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示す。デモート動作は、第１のキャッシュ１４の空間を解放することを決定すると開始することができる。第１のキャッシュ１４からページを削除して第１のキャッシュ１４の空間を解放するかどうかを決定する動作を開始すると（ブロック２００）、キャッシュ・マネジャ２４は、種々の種類の無変更のページへの予想されるヒット率に基づいて不連続の無変更ページをデモートするか、連続した無変更のページをデモートするかを決定する（ブロック２０２）。無変更の連続したページをデモートすると決定する（ブロック２０４）と、キャッシュ・マネジャ２４は無変更連続ＬＲＵリスト５４を使用して、リストのＬＲＵ側からデモートする無変更の連続したページを決定し（ブロック２０６）、それらのページは第２のキャッシュ１８にプロモートされない。無変更の不連続ページをデモートすると決定した場合（ブロック２０４）、キャッシュ・マネジャは無変更不連続ＬＲＵリスト５８を使用してデモートする無変更の不連続ページを決定する（ブロック２０８）。その無変更の不連続ページを第２のキャッシュ１８にプロモートする（ブロック２１０）。
【００２８】
図８は、変更ページを第１のキャッシュ１４からデステージするためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示す。キャッシュ・マネジャ２４は、スケジュールされた動作の一部として周期的にページをデステージすることができ、第１のキャッシュ・バックアップ・デバイス１６に空間が必要とされる場合はデステージの率を上げることができる。変更ページをデステージする動作を開始すると（ブロック２５０）、キャッシュ・マネジャ２４は変更ＬＲＵリスト５６を処理して、ＬＲＵリスト５６のＬＲＵ側からデステージする変更ページを決定する（ブロック２５２）。決定された変更ページが連続している場合（ブロック２５４）、キャッシュ・マネジャ２４は、決定された変更された連続したページをストレージ１０に書き込んで（ブロック２５６）、第２のキャッシュ１８を迂回する。変更ページが不連続である場合（ブロック２５４）、キャッシュ・マネジャ２４は、決定された変更された不連続ページを第２のキャッシュ１８にプロモートし（ブロック２５８）、決定された変更ページのコピーを第１のキャッシュ・バックアップ・デバイス１６から破棄する（ブロック２６０）。
【００２９】
図７および図８の動作では、不連続のページがデモートされるが、第２のキャッシュ１８にはプロモートされない。連続した変更ページ（書き込み）は直接ストレージ１０に書き込まれ、第２のキャッシュを迂回する。連続した無変更のページ（読み出し）は破棄され、どこにもコピーされず、第１のキャッシュ１４からデモートされた無変更の不連続ページは第２のキャッシュ１８にプロモートされる。
【００３０】
図９は、ページを第１のキャッシュ１４に追加、すなわちプロモートするためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示し、このページは、ホスト２ａ、２ｂ、．．．２ｎからの書き込みまたは変更ページであるか、またはキャッシュ１４にも１８にもなく、ストレージ１０から取り出される読み出しが要求されるデータであってもよい。第１のキャッシュ１４に追加するページを受け取ると（ブロック３００）、キャッシュ・マネジャ２４は、追加するページの制御ブロック１００（図４）を作成して（ブロック３０１）、第１のキャッシュ１４内の位置１０４と、そのページが変更／無変更であるか１０６および連続している／不連続であるか１０８を示す。この制御ブロック１００は第１のキャッシュ１４の制御ブロック・ディレクトリ５２に追加される。キャッシュ・マネジャ２４は、追加するページのページＩＤを持つ第１のキャッシュ・ページ・インデックス５０にエントリを追加し、作成されたキャッシュ制御ブロック１００へのインデックスを制御ブロック・ディレクトリ５２に追加する（ブロック３０２）。追加するページのページ・タイプのＬＲＵリスト５４、５６、または５８のＭＲＵ側にエントリが追加される（ブロック３０４）。追加するページが変更された不連続ページである場合（ブロック３０６）は、追加するページも第１のキャッシュ・バックアップ・デバイス１６にコピーし、追加されるページについて第１のキャッシュ・バックアップ・デバイス・インデックス３０にエントリが追加される（ブロック３０８）。追加するページが無変更で連続している場合（ブロック３０６）は制御が終了する。
【００３１】
図１０は、第１のキャッシュ１４からデモートされる不連続のページを第２のキャッシュ１８にプロモートするためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示す。第２のキャッシュ１８にページをプロモートする動作を開始すると（ブロック３５０）、キャッシュ・マネジャ２４はプロモートするページを第２のキャッシュ１８のＬＳＡ３２に追加し（ブロック３５２）、追加するページの制御ブロック１２０（図５）を作成して（ブロック３５４）、ＬＳＡ３２におけるページの位置１２４を示し、ページが変更／無変更であるか１２６を示す。プロモートしたページのページＩＤを持つ第２のキャッシュ・ページ・インデックス７０にエントリを追加し、第２のキャッシュ１８に対応する制御ブロック・ディレクトリ７２に作成したキャッシュ制御ブロック１２０へのインデックスを追加する（ブロック３５６）。（ブロック３５８の「ＮＯ」の分岐から）プロモートするページが無変更のデータである場合、キャッシュ・マネジャ２４はページＩＤをＭＲＵ側に追加する等により、無変更ＬＲＵリスト７４のＭＲＵ側にプロモートされたページを示す（ブロック３６０）。プロモートするページが変更データである場合（ブロック３５８）、キャッシュ・マネジャ２４は、ストレージ１０で変更されたプロモートされたページを書き込む物理的な位置を決定し（ブロック３６２）、空間インデックス７６にエントリを追加して（ブロック３６４）、プロモートされたページのページＩＤ１４２と、ストレージ１０におけるプロモートされたページの決定された物理的な位置１４４を示す。
【００３２】
図１１は、第２のキャッシュ１８に追加する新しいページ、すなわち第１のキャッシュ１４からデモートされるページのために第２のキャッシュ１８の空間を解放するためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示す。この動作を開始すると（ブロック４００）、キャッシュ・マネジャ２４は、無変更ＬＲＵリスト７４のＬＲＵ側から第２のキャッシュ１８の無変更のページを決定し（ブロック４０２）、決定した無変更のページを、無効化した無変更のページをストレージ１０にデステージせずに無効化する（ブロック４０４）と共に、無効化した無変更のページを無変更ＬＲＵリスト７４から削除する。
【００３３】
図１２は、第２のキャッシュ１２の変更ページをストレージ１０にデステージするためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示す。デステージ動作を開始すると（ブロック４２０）、キャッシュ・マネジャ２４は空間インデックス７６を使用して、場所で順序付けされた空間インデックス７６で連続しているエントリ１４０（図６）にあるページのグループなど、空間インデックス７６におけるページの順序に基づいて、ストレージ１０で互いに近接した物理的な位置にある第２のキャッシュ１８の変更ページをグループ化対象として決定する（ブロック４２２）。決定したグループ化された変更ページが第２のキャッシュ１８からストレージ１０にデステージされる（ブロック４２４）。
【００３４】
図１２の動作は、ストレージ１０でストレージ１０の書き込み面上で物理的に最も近接した物理的な位置にページを書き込ませて、第２のキャッシュ１８のページをストレージ１０に書き込む際のストレージ１０の書き込みヘッドのシークと移動の量を最小にすることにより、順次アクセス記憶装置からなるストレージ１０への書き込み動作を最適化する。ページは、ハード・ディスク・ドライブなどの順次アクセス・ストレージ１０への連続した書き込みのために最適化された順序ではなく、ＬＲＵリスト５４、５６、５８における各自の位置などの時間的な要素に基づいて第１のキャッシュ１６から第２のキャッシュ１８にプロモートされる。すなわち、図１２の動作は、ストレージ１０における各自の空間的な位置に基づいて時間的に順序付けされた変更ページを最適化して、ストレージ１０の書き込みを最適化する。
【００３５】
図１３は、読出し要求に対応する要求されるページをキャッシュ１４および１８ならびにストレージ１０から取り出すためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示す。読出し要求を処理するストレージ・マネジャ２２が、要求されるページについてキャッシュ・マネジャ２４に要求を発行することができる。ページの要求を受け取ると（ブロック４５０）、キャッシュ・マネジャ２４は第１のキャッシュ・ページ・インデックス５０を使用して、要求されるページがすべて第１のキャッシュ１４にあるかどうかを判定する（ブロック４５４）。要求されるページがすべては第１のキャッシュ１４にない場合（ブロック４５４）、キャッシュ・マネジャ２４は第２のキャッシュ・ページ・インデックス７０を使用して、要求されるページの中で、第１のキャッシュ１４にはなく第２のキャッシュ１８にあるものがあるかどうかを判定する（ブロック４５６）。要求されるページの中で第１のキャッシュ１４にも第２のキャッシュ１８にもないページがある場合（ブロック４５８）、キャッシュ・マネジャ２４は、要求されるページの中で、第１のキャッシュ１４および第２のキャッシュ１８になくストレージ１０にあるページがあるかどうかを、第２のキャッシュ・ページ・インデックス７０から判定する（ブロック４６０）。キャッシュ・マネジャ２４は次いで第２のキャッシュ１８およびストレージ１０にあると判定されたページを第１のキャッシュ１４にプロモートする（ブロック４６２）。キャッシュ・マネジャ２４は第１のキャッシュ・ページ・インデックス５０を使用して、第１のキャッシュ１４から要求されるページを取り出して、読出し要求に対して返す（ブロック４６４）。取り出されたページのエントリを、取り出されたページのエントリを含むＬＲＵリスト５４、５６、５８のＭＲＵ側に移動する（ブロック４６６）。図１３の動作では、キャッシュ・マネジャ２４は、要求されるページを最上位のキャッシュ１４から取り出した後、まず第２のキャッシュ１８に行ってから、ストレージ１０に行く。これは、キャッシュ１４および１８に要求されるページの最も新しい変更されたバージョンがあるためである。最も新しいバージョンは初めに第１のキャッシュ１４で見つかり、第１のキャッシュ１４にない場合は第２のキャッシュ１８に見つかり、キャッシュ１４、１８にもない場合はストレージ１０にある。
【００３６】
図１３の動作では、キャッシュ・マネジャ２４は要求されるページを最上位のキャッシュ１４から取り出した後、まず第２のキャッシュ１８に行ってから、ストレージ１０に行く。これは、キャッシュ１４および１８に要求されるページの最も新しい変更されたバージョンがあるためである。最も新しいバージョンは初めに第１のキャッシュ１４で見つかり、第１のキャッシュ１４にない場合は第２のキャッシュ１８に見つかり、キャッシュ１４、１８にもない場合はストレージ１０にある。
【００３７】
記載される実施形態は、最も高速にアクセスできる第１のキャッシュ１４が１バイトあたりの費用で最も高費用の空間を有し、第１のキャッシュよりも低費用であるがストレージよりも高速の第２のキャッシュを使用してシステム内でキャッシュされるデータ量を増大させることができる場合に、一次または第１レベルのキャッシュとストレージの間で第２レベルのキャッシュを使用できるようにしてキャッシュ空間を増大する技術を提供する。高速のアクセスが可能なキャッシュ記憶空間を増やすと、要求されるデータがキャッシュにあり、アクセスに時間がかかる低費用のストレージから取り出す代わりにキャッシュから返すことができる場合に、キャッシュ・データへのアクセスが改善される。さらに、記載される実施形態では、第１のキャッシュにおける時間的な順序付けに基づいて第２のキャッシュにページが追加され、次いで順次アクセス・ストレージにおける空間的な物理位置に基づいて第２のキャッシュ内で並べ替えられるので、デステージされたページがストレージ内で近接または連続した物理的な位置にページのグループとして書き込まれて、ストレージへのページの書き込みが最適化される。
【００３８】
図１４は、２レベルのキャッシュ・システム１４、１８、およびストレージ１０の一実施形態を示す。２レベルのキャッシュは第１のキャッシュ１４および第２のキャッシュ１８である。
【００３９】
キャッシュ・マネジャ２４は、第１のキャッシュ１４と第２のキャッシュ１８が２レベルのキャッシュ・システムを形成する２つのキャッシュである２レベルのキャッシュ・システムで第１のキャッシュ１４を最適化する。キャッシュ・マネジャ２４は、第２のキャッシュ１８から第１のキャッシュ１４にページがプロモートされるときにページの有用性を予測する。ページの有用性に基づいて、キャッシュ・マネジャ２４はページを適切なＬＲＵリスト５４、５６、５８の適切な位置に挿入することにより、第１のキャッシュ１４を最適化する。
【００４０】
キャッシュ・マネジャ２４は、第１のキャッシュ１４の利用を改善して、第２のキャッシュ１８から第１のキャッシュ１４にプロモートされるページが、第１のキャッシュ１４におけるヒット率を最大にするように第１のキャッシュ１４のＬＲＵリスト５４、５６、５８に挿入されるようにする。
【００４１】
ある実施形態では、ページは参照されると第１のキャッシュ１４に入れられる。そのため、ページは、そのページが第２のキャッシュ１８でヒットするたびに第１のキャッシュ１４にプロモートされる。それでも、第２のキャッシュ１８でページの「熱さ」が「冷たい（cold）」（すなわちあまり頻繁にアクセスされない）場合、キャッシュ・マネジャ２４はその「冷たい」ページに第１のキャッシュ１４のページ・フレームを長時間占有させたくない。したがって、キャッシュ・マネジャ２４はその「冷たい」ページを、ＭＲＵではなく第１のキャッシュ１４のＬＲＵリストに挿入して、「冷たい」ページが直ちに追い出されるようにする。キャッシュ・マネジャ２４は、「熱い（hot）」（すなわち頻繁にアクセスされる）ページは、第１のキャッシュ１４のＬＲＵリストのＭＲＵに挿入することができる。
【００４２】
キャッシュ・マネジャ２４は、第１のキャッシュ１４および第２のキャッシュ１８に参照カウンタ６０、７８を維持することにより、ページが第１および第２のキャッシュ１４、１８にある間のページの「熱さ」を特定する。第２のキャッシュ１８にキャッシュされるページはいずれもその前に第１のキャッシュ１４にあり、第１のキャッシュ１４で経過しているので、キャッシュ・マネジャ２４は以下の規則を利用して、現在第２のキャッシュ１８にキャッシュされているページがまだ「熱い」か、または「冷たく」なっているか（すなわちそれぞれ第１のキャッシュ１４のＬＲＵリストのＭＲＵ側にプロモートすべきか、第１のキャッシュ１４のＬＲＵリストのＬＲＵ側にプロモートすべきか）を特定する。すなわち、第２のキャッシュ１８にあるページは、そのページが以前に第１のキャッシュ１４にキャッシュされていたときのヒットよりも第２のキャッシュ１８の方でヒットが多い場合は、第１のキャッシュ１４のＬＲＵリストのＭＲＵ側にプロモートする。詳細には、
１．第１のキャッシュ１４と第２のキャッシュ１８の両方について、ページごとに参照カウンタ６０、７８を維持する。「ｃＲ」および「ｃＦ」をそれぞれ第１のキャッシュ１４および第２のキャッシュ１８のカウンタとする。
２．ページが第１のキャッシュ１４にキャッシュされている間は、ページが参照されるたびにｃＲを増分する。
３．ページが第１のキャッシュ１４から第２のキャッシュ１８にデモートされるときにｃＦ＜０であれば、ｃＦを初期化してｋｃＲにする（ｋ＝１，２，３，．．．）。ｋは、ページの「熱さ」を調整するために使用される定数である。
４．ページが第２のキャッシュにキャッシュされている間は、ページが参照されるとｃＦを減分する。
ｃＦ＞０の場合、ページを第１のキャッシュ１４のＬＲＵリストのＬＲＵ側にプロモートして、ページが間もなく追い出されるようにする。
それ以外の場合、ページは第１のキャッシュ１４のＬＲＵリストのＭＲＵ側にプロモートする。
【００４３】
このようにして、長時間にわたって「熱い」状態を保つページが第１のキャッシュ１４のフレームを占有する。「冷たく」なり始めたページは、第２のキャッシュ１８に送り、第２のキャッシュ１８にはるかに長い時間とどまり、それにより、それらのページが近い将来に再び「熱く」なった場合に第１のキャッシュ１４のＬＲＵリストのＭＲＵ位置に入れる機会をもう一度与える。ある実施形態では、第２のキャッシュ１８で少なくともＫ回のヒットがあったページだけを第１のキャッシュ１４のＬＲＵリストのＭＲＵ位置にプロモートすべき場合に、ｃＦをｋｃＲおよび定数Ｋの最大値に初期化することができる。
【００４４】
ある実施形態では、ｋは静的な設定パラメータであり、システム管理者によって設定される。特定の代替実施形態では、ｋは動的な設定パラメータであり、自動的に調整される（例えばキャッシュ・マネジャ２４により）。それらの代替実施形態の一部では、ｋは、２つのキャッシュ１４、１８の平均の「熱さ」として決定される。そのため、ｋは、２つのキャッシュ１４、１８についての適切な調整係数となる。
【００４５】
ある実施形態では、「冷たい」ページは、第１のキャッシュ１４の別のＬＲＵリストのＬＲＵ側に追加されるのではなく、第２のキャッシュ１８から高速ＬＲＵリスト６２にプロモートされる。第１のキャッシュ１４からページを追い出す場合は、追い出すページを高速ＬＲＵリスト６２から選択する。
【００４６】
図１５は、第１のキャッシュ１４にページを追加、すなわちプロモートするためにキャッシュ・マネジャ２４によって行われる動作の一実施形態を示し、このページは、読出し要求が発生し、その結果第２のキャッシュ１８から第１のキャッシュ１４に移動される第２のキャッシュ１８にある不連続ページであってもよい。第１のキャッシュ１４に追加するページを受け取ると（ブロック５００）、キャッシュ・マネジャ２４は、追加するページについての制御ブロック１００（図４）を作成して（ブロック５０２）、第１のキャッシュ１４内の位置１０４と、そのページが変更／無変更であるか１０６および連続している／不連続であるか１０８を示す。この制御ブロック１００を第１のキャッシュ１４の制御ブロック・ディレクトリ５２に追加する。キャッシュ・マネジャ２４は、追加ページのページＩＤを持つ第１のキャッシュ・ページ・インデックス５０にエントリを追加し、制御ブロック・ディレクトリ５２に作成したキャッシュ制御ブロック１００へのインデックスを追加する（ブロック５０４）。
【００４７】
ブロック５０６で、キャッシュ・マネジャ２４はそのページがｃｆ＞０であるかどうかを判定する。ｃｆ＞０である場合、処理はブロック５１０に進み、そうでない場合処理はブロック５１２に進む。追加するページのページ・タイプのＬＲＵリスト５４、５６、または５８のＭＲＵ側にエントリを追加する（ブロック５０８）。追加するページのページ・タイプのＬＲＵリスト５４、５６、または５８のＬＲＵ側にエントリを追加する（ブロック５１０）。追加するページが変更された不連続ページである場合（ブロック５１２）、追加するページも第１のキャッシュ・バックアップ・デバイス１６にコピーし、追加するページについて第１のキャッシュ・バックアップ・デバイス・インデックス３０にエントリを追加する（ブロック５１４）。追加するページが無変更で連続している場合は（ブロック５１２）、制御が終了する。
【００４８】
このように、実施形態は、第２レベルのキャッシュ（すなわち第２のキャッシュ１８）から第１レベルのキャッシュ（すなわち第１のキャッシュ１４）にページが入れられる２レベル・キャッシュにおけるプロモートを対象とする。実施形態は、プロモート対象のページの最近の履歴に着目する。ページが比較的「熱い」場合、キャッシュ・マネジャ２４は第１レベルのキャッシュのＬＲＵリストのＭＲＵ側にその「熱い」ページを入れる。ページが比較的「冷たい」場合、キャッシュ・マネジャ２４は、ページをすぐに追い出されるような状態にする（すなわち第１レベルのキャッシュのＭＲＵリストのＬＲＵ側に入れる）。
【００４９】
記載される動作は、ソフトウェア、ファームウェア、ハードウェア、もしくはその組み合わせを製造する標準的なプログラミング技術または工学技術あるいはその両方を使用して、方法、装置、またはコンピュータ・プログラム製品として実施することができる。したがって、実施形態の態様は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、または、本明細書で一般に「回路」、「モジュール」、もしくは「システム」と称するソフトウェアの態様とハードウェアの態様を組み合わせた実施形態の形をとることができる。さらに、実施形態の態様は、コンピュータ可読のプログラム・コードが具現化された１つまたは複数のコンピュータ可読媒体として実施されたコンピュータ・プログラム製品の形をとることができる。
【００５０】
１つまたは複数のコンピュータ可読媒体の任意の組み合わせを利用することができる。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体である。コンピュータ可読記憶媒体は、これらに限定されないが、例えば、電子、磁気、光学、電磁気、赤外線、もしくは半導体のシステム、装置、もしくはデバイス、またはそれらの任意の適切な組み合わせである。コンピュータ可読記憶媒体のより具体的な例（ただし完全な網羅ではない列挙）は、１つまたは複数の配線を有する電気接続、携帯可能コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、消去可能プログラム可能読取専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、携帯可能コンパクト・ディスク読取専用メモリ（ＣＤ−ＲＯＭ）、光学記憶装置、磁気記憶装置、またはそれらの任意の適切な組み合わせを含む。本文献の文脈では、コンピュータ可読記憶媒体は、命令実行システム、装置、またはデバイスによる使用のために、またはそれらとの関連でプログラムを保持または記憶することが可能な任意の有形媒体とすることができる。
【００５１】
コンピュータ可読信号媒体は、例えばベースバンドや搬送波の一部としてコンピュータ可読のプログラム・コードが内部に具現化された伝搬データ信号を含んでもよい。そのような伝搬信号は、これらに限定されないが、電磁気、光学、またはそれらの任意の適切な組み合わせを含む各種形態のいずれかをとることができる。コンピュータ可読信号媒体は、命令実行システム、装置、またはデバイスによる使用のために、またはそれらとの関連でプログラムを通信、伝搬、または移送することが可能な、コンピュータ可読記憶媒体以外の任意のコンピュータ可読媒体であってよい。
【００５２】
コンピュータ可読媒体に具現化されるプログラム・コードは、これらに限定されないが、ワイヤレス、電線、光ファイバ・ケーブル、ＲＦ等、またはそれらの任意の適切な組み合わせを含む任意の適当な媒体を使用して伝送することができる。
【００５３】
本発明の態様の動作を実施するためのコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋等のオブジェクト指向のプログラミング言語と、「Ｃ」プログラミング言語または類似のプログラミング言語等の従来の手続き型プログラミング言語を含む１つまたは複数のプログラミング言語の任意の組み合わせで書くことができる。プログラム・コードは、独立型のソフトウェア・パッケージとして、すべてがユーザのコンピュータで実行されても、一部がユーザのコンピュータで実行されても、一部がユーザのコンピュータで実行され、一部がリモート・コンピュータで実行されても、またはすべてがリモート・コンピュータまたはサーバで実行されてもよい。後者の場合は、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）やワイド・エリア・ネットワーク（ＷＡＮ）を含む任意種のネットワークを通じてユーザのコンピュータに接続しても、または外部のコンピュータに接続してもよい（例えばインターネット・サービス・プロバイダを使用してインターネットを通じて）。
【００５４】
本発明の態様について、上記では本発明の実施形態に係る方法、装置（システム）、およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して説明した。フローチャート図またはブロック図あるいはその両方の各ブロック、およびフローチャート図またはブロック図あるいはその両方のブロックの組み合わせはコンピュータ・プログラム命令によって実施できることが理解されよう。コンピュータまたは他のプログラム可能なデータ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実施する手段を生成するべく、このようなコンピュータ・プログラム命令は汎用コンピュータ、専用コンピュータ、または他のプログラム可能なデータ処理装置のプロセッサに提供されてマシンを作り出すものであってよい。
【００５５】
コンピュータ可読媒体に記憶された命令により、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実施する命令を含んだ製造品を作製するべく、このようなコンピュータ・プログラム命令はコンピュータ可読媒体に記憶され、コンピュータ、他のプログラム可能なデータ処理装置、または他のデバイスに特定の方式で機能するように指示するものであってよい。
【００５６】
コンピュータまたは他のプログラム可能装置で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックに指定される機能／動作を実施する処理を提供するように、コンピュータによって実施される処理を生成するべく、コンピュータ・プログラム命令はコンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラム可能装置、または他のデバイス上で一連の動作ステップを実行させるものであってよい。
【００５７】
用語「一実施形態」、「実施形態」、「実施形態（複数形）」、「この実施形態」、「この実施形態（複数形）」、「１つまたは複数の実施形態」、「一部の実施形態」、および「１つの実施形態」は、明示的に指定しない限り、「（１つまたは複数の）本発明の１つまたは複数の（しかしすべてではない）実施形態」を意味する。
【００５８】
用語「〜を含む（including）」、「〜を含む（comprising）」、「〜を有する（having）」およびそれらの変形は、明示的に指定しない限り、「〜を含むがそれらに限定されない」ことを意味する。
【００５９】
要素の列挙は、明示的に指定しない限り、それらの要素のいずれかまたはすべてが相互排他的であることを意味しない。
【００６０】
用語「ａ」、「ａｎ」、および「ｔｈｅ」は、明示的に指定しない限り、「１つまたは複数」を意味する。
【００６１】
相互と通信状態にあるデバイスは、明示的に指定しない限り、相互と継続的な通信状態にある必要はない。また、相互と通信状態にあるデバイスは、直接、または１つもしくは複数の媒介を通じて間接的に互いと通信することができる。
【００６２】
相互と通信状態にあるいくつかの構成要素を持つ実施形態の記載は、それらの構成要素のすべてが必要であることを意味しない。その逆に、各種の任意選択の構成要素を記載して、本発明の可能な実施形態の多様性を示す。
【００６３】
さらに、処理のステップ、方法のステップ、アルゴリズム等は連続した順序で説明する場合があるが、そのような処理、方法、およびアルゴリズムは、代替の順序で動作するように構成してもよい。すなわち、記載され得るステップのいずれの順番または順序も、必ずしも、それらのステップをその順序で行うことが必要であることを意味しない。本明細書に記載される処理のステップは任意の実際的な順序で行うことができる。さらに、いくつかのステップを同時に行ってもよい。
【００６４】
単一のデバイスまたは物品が本明細書に記載される場合、１つのデバイス／物品に代えて２つ以上のデバイス／物品（それらが協働するか否かに関わらず）を使用してよいことは直ちに明らかであろう。同様に、２つ以上のデバイスまたは物品（それらが協働するか否かに関わらず）が本明細書に記載される場合、２つ以上のデバイスまたは物品に代えて１つのデバイス／物品を使用する、または記載される数のデバイスまたはプログラムに代えて異なる数のデバイス／物品を使用することも可能であることは直ちに明らかであろう。デバイスの機能または特徴あるいはその両方は、代わりに、そのような機能／特徴を有すると明示的には記載されない１つまたは複数の他のデバイスによって実現することもできる。したがって、本発明の他の実施形態はそのデバイス自体を含む必要はない。
【００６５】
図７〜１３および図１５に示す動作は、一定の順序で発生するいくつかの事象を示している。代替実施形態では、ある動作は、異なる順序で行う、変更を加える、または排除することができる。さらに、上記のロジックにステップを追加することができ、それでもなお記載の実施形態に準ずる。さらに、本明細書に記載の動作は順に行う、または一部の動作は並行して処理することができる。さらに、動作は、１つの処理装置で行っても、分散した処理装置で行ってもよい。
【００６６】
前述の本発明の各種実施形態の説明は、例示と説明の目的で提示した。この説明は網羅的なものでも、本発明を開示される通りの形態に限定するものでもない。上記の教示に照らして多数の変更と変形が可能である。本発明の範囲は上記の詳細な説明で限定されるのではなく、添付の特許請求の範囲で限定されることが企図される。上記の詳細な説明、例、およびデータは、本発明の構成の製造および使用の完全な説明を提供する。本発明の主旨および範囲から逸脱することなく、本発明の多数の実施形態を作製できるため、本発明は添付の特許請求の範囲にある。
【図１】
2015516613.tif 000003
【図２】
2015516613.tif 000004
【図３】
2015516613.tif 000005
【図４】
2015516613.tif 000006
【図５】
2015516613.tif 000007
【図６】
2015516613.tif 000008
【図７】
2015516613.tif 000009
【図８】
2015516613.tif 000010
【図９】
2015516613.tif 000011
【図１０】
2015516613.tif 000012
【図１１】
2015516613.tif 000013
【図１２】
2015516613.tif 000014
【図１３】
2015516613.tif 000015
【図１４】
2015516613.tif 000016
【図１５】
2015516613.tif 000017
【手続補正書】
【提出日】平成26年10月27日(2014.10.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１のキャッシュおよび第２のキャッシュのデータを管理する方法であって、
コンピュータのプロセッサを使用して、ページが前記第２のキャッシュに記憶されたときに前記ページについて前記第２のキャッシュに参照カウントを維持するステップと、
前記ページを前記第２のキャッシュから前記第１のキャッシュにプロモートすることを決定するステップと、
前記参照カウントがゼロより大きいと判定するのに応じて、前記ページを、前記第１のキャッシュ内のＬＲＵリストのＬＲＵ（Least Recently Used）側に追加するステップと、
前記参照カウントがゼロ以下と判定するのに応じて、前記ページを、前記第１のキャッシュ内の前記ＬＲＵリストのＭＲＵ（Most Recently Used）側に追加するステップと
を含む方法。
【請求項２】
前記第１のキャッシュおよび前記第２のキャッシュがストレージに結合される、請求項１に記載の方法。
【請求項３】
前記第１のキャッシュが前記第２のキャッシュよりも高速にアクセスできるデバイスであり、前記第２のキャッシュが前記ストレージよりも高速にアクセスできるデバイスである、請求項１または請求項２に記載の方法。
【請求項４】
前記第１のキャッシュがランダム・アクセス・メモリ（ＲＡＭ）を含み、前記第２のキャッシュがフラッシュ・デバイスを含み、前記ストレージが順次書き込みデバイスを含む、請求項１に記載の方法。
【請求項５】
前記参照カウントが第１の参照カウントを含み、前記方法がさらに、
前記ページが前記第１のキャッシュに記憶されたときに前記ページについて前記第１のキャッシュに第２の参照カウントを維持するステップを含み、前記第１のキャッシュにある前記ページについての前記第２の参照カウントは、前記第１のキャッシュで前記ページが参照されるたびに増分される、請求項１ないし４のいずれかに記載の方法。
【請求項６】
前記第２のキャッシュで前記ページが参照されるたびに前記第２のキャッシュ内の前記ページの前記参照カウントを減分するステップをさらに含む、請求項１ないし５のいずれかに記載の方法。
【請求項７】
前記参照カウントが第１の参照カウントを含み、前記方法がさらに、
前記ページが前記第１のキャッシュから前記第２のキャッシュにデモートされると決定されるのに応じて、
前記第１の参照カウントがゼロ未満であるかどうかを判定するステップと、
前記第１の参照カウントがゼロ未満であると判定されるのに応じて、前記第１の参照カウントを、第２の参照カウントに定数（ｋ）を乗じた値に等しく設定するステップと
を含む、請求項１に記載の方法。
【請求項８】
第１のキャッシュおよび第２のキャッシュのデータを管理するコンピュータ・プログラムであって、
コンピュータに請求項１ないし７のいずれか１項に記載のステップを実行させるコンピュータ・プログラム。
【請求項９】
データを管理するシステムであって、
第１のキャッシュと、
第２のキャッシュと、
プロセッサと、
請求項１ないし７のいずれか１項に記載のステップを前記プロセッサに実行させるコンピュータ・プログラムと、
を備えるシステム。
【国際調査報告】
2015516613.tif 000018
2015516613.tif 000019
2015516613.tif 000020