(57)【要約】【課題】プリフェッチデータの残存を抑えること。【解決手段】制御部１ａは、第１ＬＲＵリストＬ１で管理されるメモリブロックＢＬ２が参照されたとき、メモリブロックＢＬ２のデータがプリフェッチされたデータの場合、メモリブロックＢＬ２の第１ＬＲＵリストＬ１による管理を維持する。制御部１ａは、メモリブロックＢＬ２のデータがプリフェッチされていないデータの場合、メモリブロックＢＬ２を管理するＬＲＵリストを第１ＬＲＵリストＬ１から第２ＬＲＵリストＬ２に変更する。【選択図】図１
2017117179.tif 000002
【特許請求の範囲】
【請求項１】
複数のメモリブロックをキャッシュメモリとして制御し、前記メモリブロックを第１ＬＲＵ（Least Recently Used）リストおよび第２ＬＲＵリストにより管理する情報処理装置であって、
前記第１ＬＲＵリストで管理される第１メモリブロックが参照されたとき、前記第１メモリブロックのデータがプリフェッチされたデータの場合、前記第１メモリブロックの前記第１ＬＲＵリストによる管理を維持し、前記第１メモリブロックのデータがプリフェッチされていないデータの場合、前記第１メモリブロックを管理するＬＲＵリストを前記第１ＬＲＵリストから前記第２ＬＲＵリストに変更する制御部、
を有する情報処理装置。
【請求項２】
前記制御部は、前記第１メモリブロックのデータがプリフェッチされたデータの場合、前記第１メモリブロックに対応するリスト要素を前記第１ＬＲＵリストの末尾に移動させ、前記第１メモリブロックのデータがプリフェッチされていないデータの場合、前記第１メモリブロックに対応するリスト要素を前記第２ＬＲＵリストの末尾に移動させる、請求項１記載の情報処理装置。
【請求項３】
前記制御部は、新たにデータが書き込まれた前記メモリブロックを前記第１ＬＲＵリストに登録する、請求項１または２記載の情報処理装置。
【請求項４】
前記制御部は、プリフェッチされたデータを何れかのメモリブロックに新たに書き込むと、当該メモリブロックに対応するリスト要素に、プリフェッチされたデータが書き込まれたことを示す識別情報を設定する、請求項１乃至３の何れか１項に記載の情報処理装置。
【請求項５】
前記制御部は、データの書き込み先の空きメモリブロックがない場合、前記第１ＬＲＵリストに属するリスト要素の数と当該リスト要素の数の制限値との比較に応じて、書き込み先のメモリブロックの取得に、前記第１ＬＲＵリストおよび前記第２ＬＲＵリストの何れを用いるかを選択する、請求項１乃至４の何れか１項に記載の情報処理装置。
【請求項６】
複数のメモリブロックをキャッシュメモリとして制御し、前記メモリブロックを第１ＬＲＵリストおよび第２ＬＲＵリストにより管理するキャッシュ制御プログラムであって、
コンピュータに、
前記第１ＬＲＵリストで管理される第１メモリブロックが参照されたとき、前記第１メモリブロックのデータがプリフェッチされたデータの場合、前記第１メモリブロックの前記第１ＬＲＵリストによる管理を維持し、前記第１メモリブロックのデータがプリフェッチされていないデータの場合、前記第１メモリブロックを管理するＬＲＵリストを前記第１ＬＲＵリストから前記第２ＬＲＵリストに変更する、
処理を実行させるキャッシュ制御プログラム。
【請求項７】
複数のメモリブロックをキャッシュメモリとして制御し、前記メモリブロックを第１ＬＲＵリストおよび第２ＬＲＵリストにより管理するキャッシュ制御方法であって、
コンピュータが、
前記第１ＬＲＵリストで管理される第１メモリブロックが参照されたとき、前記第１メモリブロックのデータがプリフェッチされたデータの場合、前記第１メモリブロックの前記第１ＬＲＵリストによる管理を維持し、前記第１メモリブロックのデータがプリフェッチされていないデータの場合、前記第１メモリブロックを管理するＬＲＵリストを前記第１ＬＲＵリストから前記第２ＬＲＵリストに変更する、
キャッシュ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、キャッシュ制御プログラムおよびキャッシュ制御方法に関する。
【背景技術】
【０００２】
現在、データを記憶する種々の装置が用いられている。例えば、ある記憶装置に対し、当該記憶装置よりも高速にアクセス可能なキャッシュメモリを設けることがある。今後アクセスされる可能性の高いデータを記憶装置から読み出してキャッシュに格納する。該当のデータが要求された際、キャッシュメモリからデータを読み出して要求元へ送ることで、データアクセスを高速化できる。
【０００３】
キャッシュメモリの記憶容量は有限である。そこで、キャッシュメモリのリソースの管理に、ＬＲＵ（Least Recently Used）と呼ばれるアルゴリズムが利用され得る。例えば、キャッシュ内のデータに対し、前回使用からの経過時間が長いほどＬＲＵ優先度を低く設定して、キャッシュメモリを管理する方法がある。キャッシュメモリに新データを記録する際、キャッシュメモリに空きがなければ、ＬＲＵ優先度が最も低いデータをキャッシュメモリから追い出し、新データをＬＲＵ優先度が最高のデータとしてキャッシュメモリに記憶する。あるいは、新データのＬＲＵ優先度を無条件に最高にするのではなく、データの現在のＬＲＵ優先度、データの属性などを用いて次のＬＲＵ優先度を導出することも考えられている。また、読み出しデータがシーケンシャル性を有すると判定されてプリフェッチを行う際に、キャッシュメモリの残容量に応じて、プリフェッチサイズおよびプリフェッチ量を動的に変更する提案もある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０００−３４７９４１号公報
【特許文献２】特開２００８−２２５９１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ＬＲＵでは、ＬＲＵリストと呼ばれるリスト構造のデータによりメモリブロックを管理し得る。この場合、複数のＬＲＵリストを利用して、アクセス数が比較的少ないデータを第１ＬＲＵリストで、アクセス数が比較的多いデータを第２ＬＲＵリストでそれぞれ別個に管理する方法が考えられる。すると、例えば第２ＬＲＵリストのサイズを大きくするほど、アクセス数が比較的多い有用なデータがキャッシュメモリに留まる時間を増やせる。
【０００６】
ここで、キャッシュメモリにはプリフェッチされたデータ（プリフェッチデータ）も格納され得る。プリフェッチは、シーケンシャルにアクセスされるデータの読み出しに利用されることが多く、プリフェッチデータは、短期間に１回以上参照された後は参照されることがなくなる。複数のＬＲＵリストを用いて上記方法によりキャッシュメモリを管理すると、ほとんど参照されなくなったプリフェッチデータが第２ＬＲＵリストに残存してしまうおそれがあるという問題がある。
【０００７】
１つの側面では、本発明は、プリフェッチデータの残存を抑える情報処理装置、キャッシュ制御プログラムおよびキャッシュ制御方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの態様では、複数のメモリブロックをキャッシュメモリとして制御し、メモリブロックを第１ＬＲＵリストおよび第２ＬＲＵリストにより管理する情報処理装置が提供される。この情報処理装置は、制御部を有する。制御部は、第１ＬＲＵリストで管理される第１メモリブロックが参照されたとき、第１メモリブロックのデータがプリフェッチされたデータの場合、第１メモリブロックの第１ＬＲＵリストによる管理を維持し、第１メモリブロックのデータがプリフェッチされていないデータの場合、第１メモリブロックを管理するＬＲＵリストを第１ＬＲＵリストから第２ＬＲＵリストに変更する。
【０００９】
また、１つの態様では、複数のメモリブロックをキャッシュメモリとして制御し、メモリブロックを第１ＬＲＵリストおよび第２ＬＲＵリストにより管理するキャッシュ制御プログラムが提供される。このキャッシュ制御プログラムは、コンピュータに、第１ＬＲＵリストで管理される第１メモリブロックが参照されたとき、第１メモリブロックのデータがプリフェッチされたデータの場合、第１メモリブロックの第１ＬＲＵリストによる管理を維持し、第１メモリブロックのデータがプリフェッチされていないデータの場合、第１メモリブロックを管理するＬＲＵリストを第１ＬＲＵリストから第２ＬＲＵリストに変更する、処理を実行させる。
【００１０】
また、１つの態様では、複数のメモリブロックをキャッシュメモリとして制御し、メモリブロックを第１ＬＲＵリストおよび第２ＬＲＵリストにより管理するキャッシュ制御方法が提供される。このキャッシュ制御方法では、コンピュータが、第１ＬＲＵリストで管理される第１メモリブロックが参照されたとき、第１メモリブロックのデータがプリフェッチされたデータの場合、第１メモリブロックの第１ＬＲＵリストによる管理を維持し、第１メモリブロックのデータがプリフェッチされていないデータの場合、第１メモリブロックを管理するＬＲＵリストを第１ＬＲＵリストから第２ＬＲＵリストに変更する。
【発明の効果】
【００１１】
１つの側面では、プリフェッチデータの残存を抑えることができる。
【図面の簡単な説明】
【００１２】
【図１】第１の実施の形態の情報処理装置を示す図である。
【図２】第２の実施の形態のストレージ装置のハードウェア例を示す図である。
【図３】キャッシュページの例を示す図である。
【図４】プリフェッチデータのアクセスパターンの例を示す図である。
【図５】ランダムデータのアクセスパターンの例を示す図である。
【図６】制御装置の機能例を示す図である。
【図７】２つのＬＲＵによるページ管理の例を示す図である。
【図８】ページ管理構造体の例を示す図である。
【図９】各ＬＲＵの先頭・末尾へのポインタの管理構造体の例を示す図である。
【図１０】ＦｒｅｅＬｉｓｔの先頭へのポインタの管理構造体の例を示す図である。
【図１１】ＬＲＵｘにページ管理構造体が繋がる様子の例を示す図である。
【図１２】ＦｒｅｅＬｉｓｔにページ管理構造体が繋がる様子の例を示す図である。
【図１３】置換ページ決定部が使用するパラメータの例を示す図である。
【図１４】プリフェッチ制御部が使用するパラメータの例を示す図である。
【図１５】キャッシュヒット判定の例を示すフローチャートである。
【図１６】置換ページ決定の例を示すフローチャートである。
【図１７】プリフェッチ制御の例を示すフローチャートである。
【図１８】サーバコンピュータのハードウェア例を示す図である。
【発明を実施するための形態】
【００１３】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。情報処理装置１は、制御部１ａおよびメモリ１ｂを有する。情報処理装置１は、記憶装置２に接続されている。記憶装置２は、情報処理装置１に外付けされてもよい。記憶装置２は、情報処理装置１に内蔵されてもよい。記憶装置２は、例えば情報処理装置１の補助記憶装置である。記憶装置２は、例えばＨＤＤ（Hard Disk Drive）でもよい。
【００１４】
制御部１ａは、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）などを含み得る。制御部１ａはプログラムを実行するプロセッサであってもよい。「プロセッサ」には、複数のプロセッサの集合（マルチプロセッサ）も含まれ得る。メモリ１ｂは、情報処理装置１の主記憶装置である。メモリ１ｂは、ＲＡＭ（Random Access Memory）と呼ばれるものでもよい。情報処理装置１は、コンピュータと呼ばれるものでもよい。
【００１５】
制御部１ａは、記憶装置２に記憶されたデータにアクセスする。例えば、制御部１ａは、情報処理装置１で実行されるアプリケーションソフトウェアにより発行されたデータへのアクセス要求を受け付ける。あるいは、制御部１ａは、情報処理装置１にネットワークを介して接続された他のコンピュータ（図１では図示を省略している）から、データへのアクセス要求を受け付けてもよい。制御部１ａは、アクセス要求で要求されたデータを記憶装置２から読み出し、要求元（情報処理装置１上のソフトウェアやネットワークを介して接続された他のコンピュータ）に応答する。
【００１６】
メモリ１ｂは、キャッシュメモリＭ１として用いられる。具体的には、メモリ１ｂは、複数のメモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・を有する。メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・それぞれは、メモリ１ｂにおいて使用可能な記憶領域の１単位である。例えば、メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・それぞれは、所定サイズの共通の記憶容量を有する。キャッシュメモリＭ１は、メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・の集合である。
【００１７】
制御部１ａは、キャッシュメモリＭ１を用いて、データへのアクセスを高速化し得る。
第１に、制御部１ａは、アクセス要求に基づいて、記憶装置２へのシーケンシャルなアクセスを検出すると、記憶装置２内の今後アクセスされるデータを予測して、該当データがアクセスされる前に、キャッシュメモリＭ１に先読み（プリフェッチ）する。ここで、シーケンシャルなアクセスとは、記憶装置２におけるアクセス対象のアドレスに連続性（完全に連続でなくてもよい）があるデータアクセスである。プリフェッチされたデータは、今後アクセスされる可能性が高いデータであるといえる。
【００１８】
第２に、制御部１ａは、アクセス要求に応じて、キャッシュメモリＭ１に格納されていないデータを、記憶装置２から読み出して応答する際、キャッシュメモリＭ１に当該データを格納する。該当のデータは、アクセス要求元などから再度アクセスされる可能性が高いからである。このようにしてキャッシュメモリに格納されるデータを、前述のプリフェッチされるデータ（シーケンシャルにアクセスされるデータ）に対して、ランダムデータと呼ぶことができる。
【００１９】
制御部１ａは、ＬＲＵのアルゴリズムを用いて、キャッシュメモリＭ１に含まれるメモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・を管理する。あるいは、メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・それぞれには、記憶装置２から読み出されたデータが格納される。このため、制御部１ａは、ＬＲＵのアルゴリズムを用いて、メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・それぞれに格納されるデータを管理するということもできる。
【００２０】
制御部１ａは、メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・それぞれの管理に、ＬＲＵリストを用いる。ＬＲＵリストは、例えば、構造体と呼ばれるリスト要素がポインタによって順番に連結されたデータ構造をもつデータである。例えば、ＬＲＵリストの先頭のリスト要素が、ＬＲＵ側（当該ＬＲＵリストに属するメモリブロックのうち、前回のアクセスから最も時間が経過しているメモリブロックまたは当該メモリブロックに格納されたデータ）に対応する。一方、ＬＲＵリストの末尾のリスト要素が、ＭＲＵ（Most Recently Used）側（当該ＬＲＵリストに属するメモリブロックのうち、最後にアクセスされたメモリブロックまたは当該メモリブロックに格納されたデータ）に対応する。制御部１ａは、新データをキャッシュメモリＭ１に格納する際、キャッシュメモリＭ１に空きがなければ、ＬＲＵリストのＬＲＵ側（先頭）のリスト要素に対応するメモリブロックに新データを格納する（該当メモリブロック内の旧データは消される）。
【００２１】
ここで、制御部１ａは、２つのＬＲＵリストを用いる。１つ目は第１ＬＲＵリストＬ１である。２つ目は第２ＬＲＵリストＬ２である。例えば、第１ＬＲＵリストＬ１および第２ＬＲＵリストＬ２は、ある時点で次のリスト要素を有する。
【００２２】
第１ＬＲＵリストＬ１は、リスト要素Ｌ１ａ，Ｌ１ｂ，Ｌ１ｃ，・・・，Ｌ１ｍを有する。リスト要素Ｌ１ａ，Ｌ１ｂ，Ｌ１ｃ，・・・，Ｌ１ｍはこの順番でポインタにより連結されている。リスト要素Ｌ１ａが第１ＬＲＵリストＬ１の先頭である。リスト要素Ｌ１ｍが第１ＬＲＵリストＬ１の末尾である。
【００２３】
第２ＬＲＵリストＬ２は、リスト要素Ｌ２ａ，Ｌ２ｂ，Ｌ２ｃ，・・・，Ｌ２ｎを有する。リスト要素Ｌ２ａ，Ｌ２ｂ，Ｌ２ｃ，・・・，Ｌ２ｎはこの順番でポインタにより連結されている。
【００２４】
メモリブロックＢＬ１，ＢＬ２，ＢＬ３，・・・それぞれは、第１ＬＲＵリストＬ１または第２ＬＲＵリストＬ２のリスト要素に対応付けられている。例えば、メモリブロックＢＬ１はリスト要素Ｌ１ａに対応付けられている。メモリブロックＢＬ２はリスト要素Ｌ１ｂに対応付けられている。メモリブロックＢＬ３はリスト要素Ｌ２ｂに対応付けられている。
【００２５】
第１ＬＲＵリストＬ１は、記憶装置２から新たに読み出されたデータを書き込んだメモリブロックを管理するために用いられる。例えば、制御部１ａは、第１ＬＲＵリストＬ１を用いて、プリフェッチされたデータおよびキャッシュヒット回数０回のランダムデータを格納したメモリブロックを管理する。
【００２６】
第２ＬＲＵリストは、キャッシュヒットの実績のあるデータが書き込まれたメモリブロックを管理するために用いられる。例えば、制御部１ａは、第１ＬＲＵリストＬ１で管理されるメモリブロックのうち、キャッシュヒット回数１回以上のデータを格納したメモリブロックを、第２ＬＲＵリストＬ２を用いて管理する。すると、第２ＬＲＵリストＬ２のサイズを、第１ＬＲＵリストＬ１のサイズよりも大きくすることで、第２ＬＲＵリストで管理されるメモリブロックに格納されたデータを、キャッシュメモリＭ１に長く留めることができる。
【００２７】
このようにヒット回数の多いデータを保護するためのＬＲＵリストと、それ以外のデータ用のＬＲＵリストとを設け、何度もヒットする有用データを保護するメモリブロックの管理方式としてＡＲＣ（Adaptive Replacement Cache）と呼ばれる方法がある。
【００２８】
一方、制御部１ａは次のような制御を行う。
制御部１ａは、第１ＬＲＵリストＬ１で管理される第１メモリブロックが参照されたとき、第１メモリブロックのデータがプリフェッチされたデータであるか否かを判定する。第１メモリブロックのデータがプリフェッチされたデータの場合、制御部１ａは、第１メモリブロックの第１ＬＲＵリストＬ１による管理を維持する。第１メモリブロックのデータがプリフェッチされていないデータの場合、制御部１ａは、第１メモリブロックを管理するＬＲＵリストを第１ＬＲＵリストＬ１から第２ＬＲＵリストＬ２に変更する。
【００２９】
例えば、制御部１ａは、メモリブロックＢＬ２（上記第１メモリブロックに相当）に格納されたデータに対するアクセス要求を受け付けたとする。この場合、制御部１ａは、要求されたデータが、メモリブロックＢＬ２に格納されていることを検出する。そして、制御部１ａは、メモリブロックＢＬ２に格納されたデータが、プリフェッチされたデータであるか否かを判定する。例えば、制御部１ａは、メモリブロックＢＬ２に該当のデータを格納する際に、該当のデータがプリフェッチによりメモリブロックＢＬ２に格納されたものであるか否かを示す識別情報を、メモリブロックＢＬ２に対応するリスト要素Ｌ１ｂに設定してもよい。すると、制御部１ａは、メモリブロックＢＬ２に格納されたデータが、プリフェッチされたデータであるか否かを、リスト要素Ｌ１ｂを参照することで判定できる。
【００３０】
制御部１ａは、メモリブロックＢＬ２に格納されたデータが、プリフェッチされたデータの場合、メモリブロックＢＬ２に対応するリスト要素Ｌ１ｂを、第１ＬＲＵリストＬ１の末尾に移動させる。より具体的には、制御部１ａは、リスト要素Ｌ１ｍの次のリスト要素を示すポインタにリスト要素Ｌ１ｂのアドレスを設定する。制御部１ａは、リスト要素Ｌ１ａの次のリスト要素を示すポインタにリスト要素Ｌ１ｃのアドレスを設定する。すなわち、制御部１ａは、メモリブロックＢＬ２の第１ＬＲＵリストＬ１による管理を維持する。
【００３１】
制御部１ａは、メモリブロックＢＬ２に格納されたデータが、プリフェッチされていないデータの場合（プリフェッチされたデータでない場合）、メモリブロックＢＬ２に対応するリスト要素Ｌ１ｂを、第２ＬＲＵリストＬ２の末尾に移動させる。より具体的には、制御部１ａは、リスト要素Ｌ２ｎの次のリスト要素を示すポインタにリスト要素Ｌ１ｂのアドレスを設定する。制御部１ａは、リスト要素Ｌ１ａの次のリスト要素を示すポインタにリスト要素Ｌ１ｃのアドレスを設定する。すなわち、制御部１ａは、メモリブロックＢＬ２を管理するＬＲＵリストを、第１ＬＲＵリストＬ１から第２ＬＲＵリストＬ２に変更する。
【００３２】
こうして、制御部１ａは、第１ＬＲＵリストＬ１で管理されるデータのうち、プリフェッチされたデータについては、キャッシュヒットしても、第１ＬＲＵリストＬ１による管理を維持する。すなわち、制御部１ａは、当該プリフェッチされたデータを格納したメモリブロックについては、キャッシュヒットしても、第２ＬＲＵリストＬ２での管理に変更しない。
【００３３】
ところで、プリフェッチされたデータとランダムデータとを同等に扱うことも考えられる。すなわち、プリフェッチされたデータを格納したメモリブロックもキャッシュヒットに応じて、第１ＬＲＵリストＬ１から第２ＬＲＵリストＬ２に移行して管理することが考えられる。しかし、その場合、参照されなくなったデータがキャッシュメモリＭ１に残存してしまう可能性が高まる。プリフェッチされたデータは、シーケンシャルにアクセスされるデータ（例えば、ストリーミングされるデータなど）の読み出しに利用されることが多く、ある短期間に１回以上参照された後は参照されなくなることが多いからである。
【００３４】
そこで、制御部１ａは、プリフェッチされたデータを格納したメモリブロックについては、ＬＲＵリスト間の移動を抑え、第１ＬＲＵリストＬ１での管理に留めることで、当該メモリブロックが第２ＬＲＵリストＬ２で管理されることを抑制する。制御部１ａは、第２ＬＲＵリストＬ２では、キャッシュヒットの実績のあるランダムデータを格納したメモリブロックを管理し、プリフェッチされたデータを格納したメモリブロックを管理しない。すると、第２ＬＲＵリストＬ２において、プリフェッチされたデータを格納したメモリブロックのリスト要素が残存することを防げる。したがって、キャッシュメモリＭ１にプリフェッチされたデータが残存することを抑えることができ、キャッシュメモリＭ１を効率的に利用できる。
【００３５】
［第２の実施の形態］
図２は、第２の実施の形態のストレージ装置のハードウェア例を示す図である。ストレージ装置１０は、制御装置１００およびディスク装置２００を有する。制御装置１００は、コントローラマネージャ（ＣＭ：Controller Manager）あるいは単にコントローラと呼ばれるものでもよい。制御装置１００は、ディスク装置２００に対するデータアクセスを制御する。制御装置１００は、第１の実施の形態の情報処理装置１の一例である。
【００３６】
ディスク装置２００は、１または複数のＨＤＤを含む。ディスク装置２００は、ドライブエンクロージャ（ＤＥ：Drive Enclosure）やディスクシェルフなどと呼ばれるものでもよい。制御装置１００は、ＲＡＩＤ（Redundant Arrays of Independent Disks）の技術により、ディスク装置２００に含まれる複数のＨＤＤを組み合わせて論理的な記憶領域を実現してもよい。ストレージ装置１０は、ディスク装置２００と併せて、ＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよい。
【００３７】
制御装置１００は、プロセッサ１０１、ＲＡＭ１０２、ＮＶＲＡＭ（Non-Volatile RAM）１０３、ＤＩ（Drive Interface）１０４、媒体リーダ１０５およびＮＡ（Network Adapter）１０６を有する。各ユニットは制御装置１００のバスに接続されている。
【００３８】
プロセッサ１０１は、制御装置１００の情報処理を制御する。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ１０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【００３９】
ＲＡＭ１０２は、制御装置１００の主記憶装置である。ＲＡＭ１０２は、プロセッサ１０１に実行させるＯＳ（Operating System）やファームウェアのプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ１０２は、プロセッサ１０１による処理に用いる各種データを記憶する。ＲＡＭ１０２は、例えば、ＤＲＡＭ（Dynamic RAM）である。
【００４０】
ＲＡＭ１０２には、ディスク装置２００から読み出したデータを格納するためのキャッシュメモリ（キャッシュと称する）Ｃ１が設けられている。キャッシュＣ１は、ＲＡＭ１０２のある記憶領域を所定サイズに区分した複数のメモリブロックの集合である。メモリブロックを「キャッシュページ」または「ページ」と称することがある。すなわち、キャッシュＣ１は複数のキャッシュページ（または複数のページ）の集合であるともいえる。
【００４１】
ＮＶＲＡＭ１０３は、制御装置１００の補助記憶装置である。ＮＶＲＡＭ１０３は、ＯＳのプログラム、ファームウェアのプログラム、および各種データを記憶する。
ＤＩ１０４は、ディスク装置２００と通信するためのインタフェースである。例えば、ＤＩ１０４として、ＳＡＳ（Serial Attached SCSI）などのインタフェースを用いることができる。なお、ＳＣＳＩは、Small Computer System Interfaceの略である。
【００４２】
媒体リーダ１０５は、記録媒体２１に記録されたプログラムやデータを読み取る装置である。記録媒体２１として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することができる。媒体リーダ１０５は、例えば、プロセッサ１０１からの命令に従って、記録媒体２１から読み取ったプログラムやデータをＲＡＭ１０２またはＮＶＲＡＭ１０３に格納する。
【００４３】
ＮＡ１０６は、ネットワーク２０を介して他の装置と通信を行う。例えば、ネットワーク２０には、ストレージ装置１０に格納されたデータを用いて業務処理を行うコンピュータ（図２では図示を省略している）が接続される。その場合、ＮＡ１０６は、当該コンピュータから、ネットワーク２０を介して、ディスク装置２００に格納されたデータに対するアクセス要求を受信する。
【００４４】
図３は、キャッシュページの例を示す図である。キャッシュＣ１は、複数のキャッシュページ（単にページと称する）を有する。ページは、キャッシュＣ１の記憶領域を一定サイズ毎に分割した、キャッシュＣ１の管理単位である。キャッシュＣ１は、ページＰ０，Ｐ１，Ｐ２，Ｐ３，・・・を含む。
【００４５】
例えば、プロセッサ１０１は、あるアクセス要求に対してキャッシュミスした際には、ディスク装置２００からデータを取得し、キャッシュＣ１に格納する。あるいは、プロセッサ１０１は、あるデータをディスク装置２００からプリフェッチして、キャッシュＣ１に格納することもある。何れの場合でも、キャッシュＣ１に空きがなければ、何れかのページを選択して、データを置換することになる。制御装置１００は、何れのページを置換対象とするかを決定するために、ＬＲＵのアルゴリズムを用いる。
【００４６】
図４は、プリフェッチデータのアクセスパターンの例を示す図である。プロセッサ１０１は、連続的にアクセスされ、将来読み出し要求が来ると予測されるデータを、事前にディスク装置２００から読み出して、キャッシュＣ１に格納しておき、当該データに対する読み出し要求への応答時間を削減する。このような手法は、データの先読み（プリフェッチ）と呼ばれる。先読みを行うことを、「プリフェッチする」ということがある。ただし、プリフェッチされたデータ（プリフェッチデータ）は、被アクセスを予測してキャッシュＣ１に格納したデータであるため、プリフェッチ時点においては、実際に使用されるかどうかは未確定である。
【００４７】
また、プリフェッチデータは、シーケンシャルにアクセスされるデータであるため、ある期間において一時的にアクセスされることが多い。すなわち、各ページは、アドレス連続的・一時的にアクセスされた後、アクセスされなくなる。なお、当該期間において、１つのページが複数回アクセスされることはある。
【００４８】
図５は、ランダムデータのアクセスパターンの例を示す図である。前述のシーケンシャルアクセスされるデータに対して、ランダムアクセスされるデータをランダムデータと呼べる。ランダムデータは、あるアクセス要求に対してキャッシュミスした際に、プロセッサ１０１によりディスク装置２００から読み出され、キャッシュＣ１に格納される。キャッシュＣ１に格納されたランダムデータに対するアクセスは、様々である。このため、ランダムデータに対するその後のアクセス状況に応じて、一度しかアクセスされないページや、同じ箇所（ページ）が何度もアクセスされる、いわゆる“ホットスポット”となるページも存在することになる。
【００４９】
制御装置１００は、このようにプリフェッチデータやランダムデータが格納されるキャッシュＣ１の各ページを効率的に管理する機能を提供する。
図６は、制御装置の機能例を示す図である。制御装置１００は、キャッシュ制御部１１０および管理情報記憶部１２０を有する。キャッシュ制御部１１０の機能は、ＲＡＭ１０２に記憶されたプログラムをプロセッサ１０１が実行することで発揮される。管理情報記憶部１２０は、ＲＡＭ１０２またはＮＶＲＡＭ１０３に確保された記憶領域として実現される。
【００５０】
キャッシュ制御部１１０は、ディスク装置２００に格納されたデータに対するアクセス要求を受信する。アクセス要求は、例えば、ネットワーク２０に接続されたコンピュータによって発行される。キャッシュ制御部１１０は、キャッシュミスした場合はディスク装置２００から要求されたデータを読み出してアクセス要求元に応答し、当該データをキャッシュＣ１に格納する。キャッシュ制御部１１０は、キャッシュヒットした場合はキャッシュＣ１から読み出したデータをアクセス要求元に応答する。キャッシュ制御部１１０は、キャッシュＣ１に含まれる複数のページを、２つのＬＲＵリストによって管理する。第１のＬＲＵリストを“ＬＲＵ１”と呼ぶ。第２のＬＲＵリストを“ＬＲＵ２”と呼ぶ。キャッシュ制御部１１０が管理するＬＲＵリストは、先頭側がＬＲＵ側に相当し、末尾側がＭＲＵ側に相当する。
【００５１】
キャッシュ制御部１１０は、キャッシュヒット判定部１１１、置換ページ決定部１１２およびプリフェッチ制御部１１３を有する。
キャッシュヒット判定部１１１は、アクセス要求で要求されたデータが、キャッシュＣ１に存在する（キャッシュヒット）か、または、キャッシュＣ１に存在しない（キャッシュミス）か、を判定する。
【００５２】
キャッシュヒット判定部１１１は、キャッシュヒットした場合には、要求されたデータをキャッシュＣ１から読み出して、アクセス要求元に送信する。このとき、キャッシュヒット判定部１１１は、要求されたデータを、ＬＲＵ１で管理されるページから読み出したか、または、ＬＲＵ２で管理されるページから読み出したかに応じて、ＬＲＵ１およびＬＲＵ２に対する操作が異なる。
【００５３】
まず、ＬＲＵ１で管理されるページからデータを読み出した場合である。このとき、読み出したデータがプリフェッチデータであれば、キャッシュヒット判定部１１１は、当該プリフェッチデータを格納したページのＬＲＵ１による管理を維持する。すなわち、キャッシュヒット判定部１１１は、当該ページのリスト要素をＬＲＵ１のＭＲＵ側（末尾）に移動させる。一方、読み出したデータがプリフェッチデータでなければ、キャッシュヒット判定部１１１は、当該データを格納したページを管理するＬＲＵリストを、ＬＲＵ１からＬＲＵ２に変更する。すなわち、キャッシュヒット判定部１１１は、当該ページのリスト要素をＬＲＵ２のＭＲＵ側（末尾）に移動させる。
【００５４】
次に、ＬＲＵ２で管理されるページからデータを読み出した場合である。このとき、読み出したデータは、プリフェッチデータではなく、ランダムデータである。キャッシュヒット判定部１１１は、当該データを格納したページのリスト要素をＬＲＵ２のＭＲＵ側（末尾）に移動させる。
【００５５】
キャッシュヒット判定部１１１は、キャッシュミスした場合には、要求されたデータ（ランダムデータ）をディスク装置２００から読み出して、アクセス要求元に送信する。キャッシュヒット判定部１１１は、キャッシュミスした場合、キャッシュＣ１の新たなページを置換ページ決定部１１２から取得し、ディスク装置２００から読み出したデータを当該ページに格納する。このとき、キャッシュヒット判定部１１１は、ＬＲＵ１を操作して、新たなデータを格納したページに対応するリスト要素を、ＬＲＵ１のＭＲＵ側（末尾）に連結する。
【００５６】
置換ページ決定部１１２は、キャッシュヒット判定部１１１またはプリフェッチ制御部１１３からの新たなページの要求に応じて、キャッシュＣ１の何れかのページを、要求元のキャッシュヒット判定部１１１またはプリフェッチ制御部１１３に提供する。置換ページ決定部１１２は、キャッシュＣ１に空きページがあれば、空きページを提供する。置換ページ決定部１１２は、キャッシュＣ１に空きページがなければ、ＬＲＵ１またはＬＲＵ２に基づいて、置換対象とするページを決定する。
【００５７】
プリフェッチ制御部１１３は、ディスク装置２００に格納されたデータに対するシーケンシャルなアクセスを検出し、プリフェッチを行う。プリフェッチ制御部１１３は、プリフェッチを行う際に、プリフェッチデータを格納するための新たなページを置換ページ決定部１１２から取得し、プリフェッチデータを格納する。
【００５８】
管理情報記憶部１２０は、キャッシュヒット判定部１１１、置換ページ決定部１１２およびプリフェッチ制御部１１３の処理に用いられる各種のデータを記憶する。例えば、管理情報記憶部１２０は、前述のＬＲＵ１およびＬＲＵ２を記憶する。また、管理情報記憶部１２０は、プリフェッチ制御部１１３がシーケンシャルなアクセスを検出するためのパラメータを記憶する。
【００５９】
図７は、２つのＬＲＵによるページ管理の例を示す図である。前述のように、キャッシュ制御部１１０は、２つのＬＲＵリスト（ＬＲＵ１およびＬＲＵ２）を用いてキャッシュＣ１に格納したデータを管理する。図７では、プリフェッチデータを格納したページをプリフェッチページと称している。また、ランダムデータを格納したページをランダムページと称している。
【００６０】
キャッシュ制御部１１０は、プリフェッチデータのページ（プリフェッチページ）、および、キャッシュヒット０回のランダムデータのページ（ランダムページ）を、ＬＲＵ１により管理する。キャッシュ制御部１１０は、キャッシュヒット１回以上のランダムデータのページ（ランダムページ）を、ＬＲＵ２により管理する。
【００６１】
具体的には、キャッシュヒット判定部１１１は、ＬＲＵ１で管理されるページが参照されたとき、該当ページに格納されたデータが、プリフェッチデータである場合、当該ページのＬＲＵ１による管理を維持する。この処理は、次のように表わすこともできる。すなわち、キャッシュヒット判定部１１１は、ＬＲＵ１で管理されるページが参照されたとき、当該ページがプリフェッチページである場合、当該ページのＬＲＵ１による管理を維持する。
【００６２】
一方、キャッシュヒット判定部１１１は、ＬＲＵ１で管理されるページが参照されたとき、該当ページに格納されたデータが、プリフェッチデータではない場合（ランダムデータである場合）、当該ページを管理するＬＲＵリストを、ＬＲＵ１からＬＲＵ２に変更する。この処理は、次のように表わすこともできる。すなわち、キャッシュヒット判定部１１１は、ＬＲＵ１で管理されるページが参照されたとき、当該ページがプリフェッチページでない場合（ランダムページである場合）、当該ページを管理するＬＲＵリストを、ＬＲＵ１からＬＲＵ２に変更する。
【００６３】
図８は、ページ管理構造体の例を示す図である。ページ管理構造体は、ＬＲＵリストおよび後述するＦｒｅｅＬｉｓｔ（空きページを管理するためのリスト）のリスト要素である。図８では、各ページ管理構造体と各ページとの対応関係が分かり易いように、キャッシュＣ１におけるページＰ０，Ｐ１，Ｐ２，Ｐ３，・・・も図示している。
【００６４】
ページ管理構造体は、ページＰ０，Ｐ１，Ｐ２，Ｐ３，・・・それぞれに対して１つずつ設けられる。各ページ管理構造体は、管理情報記憶部１２０（すなわち、ＲＡＭ１０２上の所定の記憶領域）に格納される。
【００６５】
ページ管理構造体は、論理ブロックアドレス（ＬＢＡ：Logical Block Address）、フラグｆ、次のページ管理構造体を示すポインタｎｅｘｔ、前のページ管理構造体を示すポインタｐｒｅｖを含む。
【００６６】
ＬＢＡは、該当のページに格納したデータのディスク装置２００におけるＬＢＡである。ページが空きの場合、ＬＢＡは設定なし（ｎｕｌｌ）である。
フラグｆは、該当のページに格納したデータが、プリフェッチデータであるか否かを示す識別情報である。プリフェッチデータである場合、フラグｆは“ｔｒｕｅ”（“１”と表わしてもよい）である。プリフェッチデータでない場合、フラグｆは“ｆａｌｓｅ”（“０”と表わしてもよい）である。ページが空きの場合、フラグｆは“ｆａｌｓｅ”である。
【００６７】
ポインタｎｅｘｔは、次のページ管理構造体が格納されたＲＡＭ１０２上のアドレスを示す情報である。ポインタｐｒｅｖは、前のページ管理構造体が格納されたＲＡＭ１０２上のアドレスを示す情報である。
【００６８】
例えば、図８では、ページＰ０のページ管理構造体（図８では管理構造体と略記）に対して、ＬＢＡ＝ＬＢＡ0、フラグｆ＝ｆ0、ポインタｎｅｘｔ＝ｎｅｘｔ0、ポインタｐｒｅｖ＝ｐｒｅｖ0が設定されている。他のページのページ管理構造体も、同様に、ＬＢＡ、フラグｆ、ポインタｎｅｘｔ、ポインタｐｒｅｖが設定される。
【００６９】
ここで、あるページに対応するページ管理構造体をあるＬＲＵリストに追加することを、「該当ページをＬＲＵリストに登録する」と表わすこともできる。
図９は、各ＬＲＵの先頭・末尾へのポインタの管理構造体の例を示す図である。各ＬＲＵの先頭・末尾へのポインタの管理構造体は、ＬＲＵ１およびＬＲＵ２それぞれに対して設けられる。ＬＲＵ１の先頭・末尾へのポインタの管理構造体を、「ＬＲＵ１の管理構造体」と称する。ＬＲＵ２の先頭・末尾へのポインタの管理構造体を、「ＬＲＵ２の管理構造体」と称する。ＬＲＵ１の管理構造体およびＬＲＵ２の管理構造体は、管理情報記憶部１２０に格納される。
【００７０】
ＬＲＵ１の管理構造体は、ポインタｎｅｘｔLRU1およびポインタｐｒｅｖLRU1を含む。ポインタｎｅｘｔLRU1は、ＬＲＵ１の先頭のページ管理構造体が格納されているＲＡＭ１０２上のアドレスを示す情報である。ポインタｐｒｅｖLRU1は、ＬＲＵ１の末尾のページ管理構造体が格納されているＲＡＭ１０２上のアドレスを示す情報である。
【００７１】
ＬＲＵ２の管理構造体は、ポインタｎｅｘｔLRU2およびポインタｐｒｅｖLRU2を含む。ポインタｎｅｘｔLRU2は、ＬＲＵ２の先頭のページ管理構造体が格納されているＲＡＭ１０２上のアドレスを示す情報である。ポインタｐｒｅｖLRU2は、ＬＲＵ２の末尾のページ管理構造体が格納されているＲＡＭ１０２上のアドレスを示す情報である。
【００７２】
図１０は、ＦｒｅｅＬｉｓｔの先頭へのポインタの管理構造体の例を示す図である。ＦｒｅｅＬｉｓｔの先頭へのポインタの管理構造体は、ＦｒｅｅＬｉｓｔと呼ばれるリストに対して設けられる。ＦｒｅｅＬｉｓｔは、キャッシュＣ１における空きページを管理するためのリストである。ＦｒｅｅＬｉｓｔの先頭へのポインタの管理構造体を、「ＦｒｅｅＬｉｓｔの管理構造体」と称する。ＦｒｅｅＬｉｓｔの管理構造体は、管理情報記憶部１２０に格納される。
【００７３】
ＦｒｅｅＬｉｓｔの管理構造体は、ポインタｈｅａｄFreeListを含む。ポインタｈｅａｄFreeListは、ＦｒｅｅＬｉｓｔの先頭のページ管理構造体が格納されているＲＡＭ１０２上のアドレスを示す情報である。
【００７４】
図１１は、ＬＲＵｘにページ管理構造体が繋がる様子の例を示す図である。図１１のＬＲＵｘの表記は、“ＬＲＵ１”および“ＬＲＵ２”の何れかを示す。ＬＲＵ１およびＬＲＵ２それぞれは、ページ管理構造体がポインタにより連結されたリスト構造をもつ。
【００７５】
例えば、ＬＲＵ１の管理構造体のポインタｎｅｘｔLRU1を起点に、ページ管理構造体のポインタｎｅｘｔを辿ることで、ＬＲＵ１の先頭のページ管理構造体から、ＬＲＵ１の末尾のページ管理構造体までを順番に辿れる。ＬＲＵ１の末尾のページ管理構造体のポインタｎｅｘｔは、ＬＲＵ１の管理構造体を示す。
【００７６】
同様に、ＬＲＵ１の管理構造体のポインタｐｒｅｖLRU1を起点に、ページ管理構造体のポインタｐｒｅｖを辿ることで、ＬＲＵ１の末尾のページ管理構造体から、ＬＲＵ１の先頭のページ管理構造体までを順番に辿れる。ＬＲＵ１の先頭のページ管理構造体のポインタｐｒｅｖは、ＬＲＵ１の管理構造体を示す。
【００７７】
また、例えば、ＬＲＵ２の管理構造体のポインタｎｅｘｔLRU2を起点に、ページ管理構造体のポインタｎｅｘｔを辿ることで、ＬＲＵ２の先頭のページ管理構造体から、ＬＲＵ２の末尾のページ管理構造体までを順番に辿れる。ＬＲＵ２の末尾のページ管理構造体のポインタｎｅｘｔは、ＬＲＵ２の管理構造体を示す。
【００７８】
同様に、ＬＲＵ２の管理構造体のポインタｐｒｅｖLRU2を起点に、ページ管理構造体のポインタｐｒｅｖを辿ることで、ＬＲＵ２の末尾のページ管理構造体から、ＬＲＵ２の先頭のページ管理構造体までを順番に辿れる。ＬＲＵ２の先頭のページ管理構造体のポインタｐｒｅｖは、ＬＲＵ２の管理構造体を示す。
【００７９】
キャッシュ制御部１１０は、各構造体に含まれるポインタの設定を変更することで、ＬＲＵ１およびＬＲＵ２に連結されたページ管理構造体の連結順序を変更できる。キャッシュ制御部１１０は、ＬＲＵｘの先頭または末尾のページ管理構造体を変更する場合は、ＬＲＵｘの管理構造体に含まれるポインタｎｅｘｔLRUxやポインタｐｒｅｖLRUxの設定を、該当のページ管理構造体を指すように変更する。
【００８０】
図１２は、ＦｒｅｅＬｉｓｔにページ管理構造体が繋がる様子の例を示す図である。ＦｒｅｅＬｉｓｔは、ページ管理構造体がポインタにより連結されたリスト構造をもつ。
例えば、ＦｒｅｅＬｉｓｔの管理構造体のポインタｈｅａｄFreeListを起点に、ページ管理構造体のポインタｎｅｘｔを辿ることで、ＦｒｅｅＬｉｓｔの先頭のページ管理構造体から、ＦｒｅｅＬｉｓｔの末尾のページ管理構造体までを順番に辿れる。ＦｒｅｅＬｉｓｔに属するページ管理構造体は、ポインタｐｒｅｖを管理しなくてよい。キャッシュＣ１にデータを格納する際、ＦｒｅｅＬｉｓｔの先頭のページ管理構造体に対応するページから使用していけばよいからである。したがって、ＦｒｅｅＬｉｓｔに属するページ管理構造体では、ポインタｐｒｅｖは、設定なし（ｎｕｌｌ）である。
【００８１】
上記のように、ページ管理構造体を連結するリストは、ＬＲＵ１，ＬＲＵ２およびＦｒｅｅＬｉｓｔの計３系統存在することになる。１つのページ管理構造体は、ＬＲＵ１，ＬＲＵ２およびＦｒｅｅＬｉｓｔのうちの何れかのリストに属する（ストレージ装置１０の電源オン直後は、各ページは空き状態でありＦｒｅｅＬｉｓｔに属することになる）。
【００８２】
図１３は、置換ページ決定部が使用するパラメータの例を示す図である。置換ページ決定部１１２は、ＬＲＵ１のサイズ制限値Ｓを使用する。サイズ制限値Ｓは、ＬＲＵ１の最大サイズを規定する値である。例えば、サイズ制限値Ｓは、ＬＲＵ１に属するページ管理構造体の数（ＬＲＵ１に属するページの数）により表わされる。サイズ制限値Ｓは、管理情報記憶部１２０に予め格納される。
【００８３】
なお、管理情報記憶部１２０は、ＬＲＵ２のサイズ制限値も予め記憶している。ＬＲＵ２のサイズ制限値は、ＬＲＵ１のサイズ制限値Ｓよりも大きな値である。
図１４は、プリフェッチ制御部が使用するパラメータの例を示す図である。図１４（Ａ）は、アクセス管理テーブルＴ１，Ｔ２，・・・，Ｔｔを例示している。管理情報記憶部１２０は、ｔ個のアクセス管理テーブルＴ１，Ｔ２，・・・，Ｔｔを記憶する。ここで、ｔは、１以上の整数である。プリフェッチ制御部１１３は、アクセス管理テーブルＴ１，Ｔ２，・・・，Ｔｔを用いて、ｔ個の連続するアクセスを管理する。
【００８４】
例えば、ストレージ装置１０が、ネットワーク２０に接続された複数のコンピュータからアクセス要求を受け付ける場合、１つのコンピュータから発行されたアクセスを１つのアクセス管理テーブルで管理することが考えられる。または、１つのコンピュータで複数のソフトウェアが実行されており、アクセス要求を基にアクセス元のソフトウェアを識別できる場合、当該コンピュータの１つのソフトウェアから発行されたアクセスを１つのアクセス管理テーブルで管理してもよい。以下では、アクセス管理テーブルＴ１のデータ構造を説明するが、アクセス管理テーブルＴ２，・・・，Ｔｔも同様のデータ構造となる。
【００８５】
アクセス管理テーブルＴ１は、最近実際にアクセスされた最後のアドレスＡlast、プリフェッチ済データの最後尾のアドレスＡprefetchおよびアドレス連続性アクセスの回数カウンターＣを含む。
【００８６】
アドレスＡlastは、ある１つのアクセス元（着目するアクセス元）が連続して発行したアドレス要求で要求されたディスク装置２００の論理アドレスのうち、最後の論理アドレス（直近にアクセスされた論理アドレス）を示す。
【００８７】
アドレスＡprefetchは、着目するアクセス元によるアクセスに対してプリフェッチ済であるデータの、ディスク装置２００における最後尾の論理アドレスを示す。
カウンターＣは、アクセス先の論理アドレスに連続性があると判断された回数をカウントするためのカウンターである。
【００８８】
図１４（Ｂ）は、プリフェッチ制御部１１３が使用する定数値として、管理情報記憶部１２０に予め格納する値を例示している。第１に、プリフェッチ制御部１１３は、間隔のあるアドレス連続性で許容する間隔Ｒを使用する。第２に、プリフェッチ制御部１１３は、プリフェッチを開始するまでのアドレス連続性のあるアクセス回数Ｎ（Ｎは２以上の整数）を使用する。第３に、プリフェッチ制御部１１３は、プリフェッチにおける先読み量Ｐ（ＰはＲよりも大きいサイズ）を使用する。
【００８９】
間隔Ｒは、連続して発行されたアクセス要求によりディスク装置２００がシーケンシャルにアクセスされているとみなす論理アドレスの間隔である。例えば、プリフェッチ制御部１１３は、第１のアクセス要求で指定された論理アドレス範囲の末尾の論理アドレスと、第１のアクセス要求の次の第２のアクセス要求で指定された論理アドレス範囲の先頭の論理アドレスとの差によって、連続する２つのアクセス要求によりアクセスされる論理アドレスの間隔を求めることができる。ディスク装置２００の論理アドレスに対する、ある程度飛び飛びのアクセスもシーケンシャルなアクセスとして許容する場合には、１よりも大きな所定のサイズをＲに設定できる。
【００９０】
アクセス回数Ｎは、前述のカウンターＣの値と比較される値であり、プリフェッチを行うまでにカウントされるべきカウンターＣの閾値である。
先読み量Ｐは、プリフェッチの際に、ディスク装置２００から読み出すデータのサイズである。例えば、先読み量Ｐは、論理アドレスの範囲として指定される。
【００９１】
次に、以上のような制御装置１００による処理手順を説明する。
図１５は、キャッシュヒット判定の例を示すフローチャートである。以下、図１５に示す処理をステップ番号に沿って説明する。
【００９２】
（Ｓ１１）キャッシュヒット判定部１１１は、ユーザからのデータに対するアクセス要求（データアクセス要求）を検出する。例えば、ストレージ装置１０にネットワーク２０を介して接続されたコンピュータを、ここでいうユーザと考えてもよい。
【００９３】
（Ｓ１２）キャッシュヒット判定部１１１は、アクセス要求に応じてユーザに通知すべきページのうち、最小アドレスのページがキャッシュＣ１にあるか否かを判定する。最小アドレスのページがキャッシュにある場合（キャッシュヒット）、処理をステップＳ１３に進める。最小アドレスのページがキャッシュにない場合（キャッシュミス）、処理をステップＳ１６に進める。ここで、アクセス要求には、ディスク装置２００におけるアクセス対象の論理アドレス範囲が含まれる。最小アドレスとは、当該アクセス対象の全論理アドレス範囲のうち、ユーザに未だ通知していない（対象のデータを応答していない）部分に属する最小の論理アドレス（ディスク装置２００上の論理アドレス）である。最小アドレスのデータを格納したページがキャッシュＣ１にあるか否かは、管理情報記憶部１２０に記憶されたＬＲＵ１またはＬＲＵ２によりページ管理構造体に設定されたＬＢＡ値を参照することで判定できる。
【００９４】
（Ｓ１３）キャッシュヒット判定部１１１は、最小アドレスに対応するページ管理構造体のフラグｆが“ｔｒｕｅ”であるか否かを判定する。フラグｆが“ｔｒｕｅ”である場合、処理をステップＳ１４に進める。フラグｆが“ｔｒｕｅ”でない場合（すなわち、“ｆａｌｓｅ”である場合）、処理をステップＳ１５に進める。
【００９５】
（Ｓ１４）キャッシュヒット判定部１１１は、該当のページ管理構造体をＬＲＵ１の末尾（ＭＲＵ側）に移動させる（ポインタの設定変更を行う）。そして、処理をステップＳ１８に進める。
【００９６】
（Ｓ１５）キャッシュヒット判定部１１１は、該当のページ管理構造体をＬＲＵ２の末尾（ＭＲＵ側）に移動させる（ポインタの設定変更を行う）。このとき、移動元のＬＲＵリストが、ＬＲＵ１であることもある。その場合、キャッシュヒット判定部１１１は、該当のページ管理構造体を管理するＬＲＵリストを、ＬＲＵ１からＬＲＵ２に変更することになる。そして、処理をステップＳ１８に進める。
【００９７】
（Ｓ１６）キャッシュヒット判定部１１１は、置換ページ決定部１１２に新たなページを要求する。キャッシュヒット判定部１１１は、置換ページ決定部１１２から新たなページを取得する。
【００９８】
（Ｓ１７）キャッシュヒット判定部１１１は、ディスク装置２００からページにデータを読み込み、該当のページに対応するページ管理構造体をＬＲＵ１の末尾に移動させる（ポインタの設定変更を行う）。すなわち、キャッシュヒット判定部１１１は、キャッシュミスしたランダムデータをディスク装置２００から読み出し、キャッシュＣ１に新たに格納する。このとき、キャッシュヒット判定部１１１は、該当のページに対応するページ管理構造体に、ランダムデータの読み出し元の論理アドレス（ディスク装置２００における論理アドレス）を設定する（ＬＢＡ値を設定）。
【００９９】
（Ｓ１８）キャッシュヒット判定部１１１は、ユーザに該当のページを通知する。すなわち、キャッシュヒット判定部１１１は、該当のページに格納されたデータをユーザに送信する。
【０１００】
（Ｓ１９）キャッシュヒット判定部１１１は、アクセス要求で要求されたアドレス範囲のページを全てユーザに通知したか否かを判定する。全てユーザに通知した場合、処理を終了する。全てユーザに通知していない場合（未通知部分がある場合）、処理をステップＳ１２に進める。
【０１０１】
なお、ステップＳ１５ではキャッシュヒット判定部１１１は、ＬＲＵ１からＬＲＵ２の末尾にページ管理構造体を移動させる際、ＬＲＵ２のサイズがＬＲＵ２に関するサイズ上限値を上回ったならば、ＬＲＵ２の先頭に相当するページを解放してＦｒｅｅＬｉｓｔの末尾に追加してもよい。
【０１０２】
図１６は、置換ページ決定の例を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
（Ｓ２１）置換ページ決定部１１２は、キャッシュヒット判定部１１１またはプリフェッチ制御部１１３から新たなページの要求を受け付ける。置換ページ決定部１１２は、１つのページの要求を受け付けることもあるし、複数のページの要求を受け付けることもある。
【０１０３】
（Ｓ２２）置換ページ決定部１１２は、管理情報記憶部１２０に記憶されたＦｒｅｅＬｉｓｔを参照して、ＦｒｅｅＬｉｓｔにページがあるか否かを判定する。ＦｒｅｅＬｉｓｔにページがある場合（ＦｒｅｅＬｉｓｔに属するページ管理構造体がある場合）、処理をステップＳ２３に進める。ＦｒｅｅＬｉｓｔにページがない場合（ＦｒｅｅＬｉｓｔに属するページ管理構造体がない場合）、処理をステップＳ２４に進める。
【０１０４】
（Ｓ２３）置換ページ決定部１１２は、ＦｒｅｅＬｉｓｔにあるページを選択し、要求元（キャッシュヒット判定部１１１またはプリフェッチ制御部１１３）に通知する。ＦｒｅｅＬｉｓｔにあるページとは、例えば、ＦｒｅｅＬｉｓｔの先頭のページ管理構造体（ポインタｈｅａｄFreeListで示されるページ管理構造体）に対応するページである。そして、処理をステップＳ２８に進める。
【０１０５】
（Ｓ２４）置換ページ決定部１１２は、ＬＲＵ１のページ管理構造体の数がＳよりも大きいか否かを判定する。ＬＲＵ１のページ管理構造体の数がＳよりも大きい場合、処理をステップＳ２５に進める。ＬＲＵ１のページ管理構造体の数がＳよりも大きくない場合（Ｓ以下の場合）、処理をステップＳ２６に進める。
【０１０６】
（Ｓ２５）置換ページ決定部１１２は、ＬＲＵ１の先頭ページを選択する。より具体的には、置換ページ決定部１１２は、ＬＲＵ１の先頭のページ管理構造体に対応するページを選択する。ＬＲＵ１の先頭のページ管理構造体は、ＬＲＵ１の管理構造体のポインタｎｅｘｔLRU1で示されるページ管理構造体である。置換ページ決定部１１２は、選択したページを置換対象ページとする。そして、処理をステップＳ２７に進める。
【０１０７】
（Ｓ２６）置換ページ決定部１１２は、ＬＲＵ２の先頭ページを選択する。より具体的には、置換ページ決定部１１２は、ＬＲＵ２の先頭のページ管理構造体に対応するページを選択する。ＬＲＵ２の先頭のページ管理構造体は、ＬＲＵ２の管理構造体のポインタｎｅｘｔLRU2で示されるページ管理構造体である。置換ページ決定部１１２は、選択したページを置換対象ページとする。そして、処理をステップＳ２７に進める。
【０１０８】
（Ｓ２７）置換ページ決定部１１２は、置換対象ページを要求元に通知する。置換ページ決定部１１２は、置換対象ページに対応するページ管理構造体の各設定値を初期値（空き状態である場合の値）に初期化する。
【０１０９】
（Ｓ２８）置換ページ決定部１１２は、要求された数のページを通知したか否かを判定する。要求された数のページを通知した場合、処理を終了する。要求された数のページを通知していない場合、処理をステップＳ２２に進める。
【０１１０】
図１７は、プリフェッチ制御の例を示すフローチャートである。以下、図１７に示す処理をステップ番号に沿って説明する。
（Ｓ３１）プリフェッチ制御部１１３は、ユーザがアドレスＡ〜Ａ＋Ｌの範囲のデータにアクセス要求したことを検出する。例えば、ストレージ装置１０にネットワーク２０を介して接続されたコンピュータを、ユーザと考えてもよい。また、アドレスＡ〜Ａ＋Ｌの範囲は、ディスク装置２００における論理アドレスの範囲を示す。Ｌは、論理アドレスＡに対するオフセット値であり、アクセス対象範囲の終点を定める。
【０１１１】
（Ｓ３２）プリフェッチ制御部１１３は、論理アドレスＡに最も近いＡlastをもつアクセス管理テーブルＴk（図１７ではテーブルＴkと表記）を特定する。
（Ｓ３３）プリフェッチ制御部１１３は、ステップＳ３２で特定したアクセス管理テーブルＴkについて、Ａlast＜Ａ＜Ａlast＋Ｒが成立するか否かを判定する。成立する場合、処理をステップＳ３４に進める。成立しない場合、処理をステップＳ４０に進める。
【０１１２】
（Ｓ３４）プリフェッチ制御部１１３は、アクセス管理テーブルＴkのカウンターＣをインクリメントする（カウンターＣの設定値に１を加算する）。
（Ｓ３５）プリフェッチ制御部１１３は、カウンターＣがＮ以上であるか否かを判定する。カウンターＣがＮ以上である場合、処理をステップＳ３６に進める。カウンターＣがＮ以上でない場合（Ｎよりも小さい場合）、処理をステップＳ３９に進める。
【０１１３】
（Ｓ３６）プリフェッチ制御部１１３は、アドレスＡprefetch〜Ａ＋Ｌ＋Ｐの範囲（論理アドレスの範囲）のプリフェッチに必要な数のページを置換ページ決定部１１２に要求する。
【０１１４】
（Ｓ３７）プリフェッチ制御部１１３は、置換ページ決定部１１２から要求した数のページの通知を受け付ける（プリフェッチデータを格納するページを確保）。プリフェッチ制御部１１３は、確保したページにディスク装置２００からデータをプリフェッチし、該当のページに対応するページ管理構造体のフラグｆを“ｔｒｕｅ”に設定する。また、プリフェッチ制御部１１３は、プリフェッチデータの読み出し元の論理アドレス（ディスク装置２００の論理アドレス）を該当のページに対応するページ管理構造体に設定する（ＬＢＡ値を設定）。そして、プリフェッチ制御部１１３は、プリフェッチデータを格納したページのページ管理構造体を、ＬＲＵ１の末尾に移動させる（ポインタの設定変更を行う）。
【０１１５】
（Ｓ３８）プリフェッチ制御部１１３は、アクセス管理テーブルＴkのＡprefetchを、Ａ＋Ｌ＋Ｐに更新する。そして、処理をステップＳ４１に進める。
（Ｓ３９）プリフェッチ制御部１１３は、アクセス管理テーブルＴkのＡprefetchを、Ａ＋Ｌに更新する。論理アドレスＡ＋Ｌまでは今回のアクセス要求によりアクセス済になるからである。そして、処理をステップＳ４１に進める。
【０１１６】
（Ｓ４０）プリフェッチ制御部１１３は、アクセス管理テーブルＴkのカウンターＣを０に更新する。そして、処理をステップＳ４１に進める。
（Ｓ４１）プリフェッチ制御部１１３は、アクセス管理テーブルＴkのＡlastを、Ａ＋Ｌに更新する。
【０１１７】
このようにして、キャッシュ制御部１１０は、ＬＲＵ１で管理されるページのうち、プリフェッチデータを格納したページについては、キャッシュヒットしても、ＬＲＵ１による管理を維持する。また、キャッシュ制御部１１０は、ＬＲＵ１で管理されるページのうち、ランダムデータを格納したページについては、キャッシュヒットすると、当該ページを管理するＬＲＵリストをＬＲＵ１からＬＲＵ２に変更する。
【０１１８】
ところで、プリフェッチデータは、シーケンシャルにアクセスされるデータの読み出しに利用されることが多く、ある短期間に１回以上参照された後は参照されることがなくなることが多い。すなわち、プリフェッチデータを格納したページは、アドレス連続的に一時的にアクセスされた後はアクセスされなくなることが多い。上記のように、ヒット回数によって使用するＬＲＵリストを分けて有用データを保護するキャッシュページ管理方式において、プリフェッチデータをランダムデータと同等に扱うことも考えられる。具体的には、プリフェッチデータのページがヒットした際に、当該ページを有用ＬＲＵリスト（例えば、ＬＲＵ２）に登録すると、アクセスされなくなったプリフェッチデータがキャッシュに残存してしまう。
【０１１９】
そこで、キャッシュ制御部１１０は、上記のように、プリフェッチデータを格納したページについては、ＬＲＵ１での管理に留める。すなわち、プリフェッチデータを格納したページに対応するページ管理構造体のＬＲＵリスト間の移動（ＬＲＵ１からＬＲＵ２への移動）を抑止する。キャッシュ制御部１１０は、ＬＲＵ２では、キャッシュヒットの実績のあるランダムデータを格納したページを管理し、プリフェッチデータを格納したページを管理しない。すると、ＬＲＵ２において、プリフェッチデータを格納したページのページ管理構造体が残存することを防げる。その結果、プリフェッチデータがキャッシュＣ１に残存するのを防ぎ、キャッシュＣ１を有効活用できるようになる。
【０１２０】
ここで、第２の実施の形態の例では、キャッシュ制御部１１０は、ランダムデータを格納したページのページ管理構造体についてキャッシュヒット１回の実績で、ＬＲＵ１からＬＲＵ２へ移動させるものとした。一方、キャッシュ制御部１１０は、２回以上の所定回のヒット実績があった場合に当該移動を行ってもよい。
【０１２１】
なお、第２の実施の形態では、ストレージ装置１０を例示したが、キャッシュ制御部１１０の機能をサーバコンピュータやクライアントコンピュータが有してもよい。すなわち、サーバコンピュータやクライアントコンピュータを第１の実施の形態の情報処理装置１の一例と考えてもよい。
【０１２２】
図１８は、サーバコンピュータのハードウェア例を示す図である。サーバコンピュータ３００は、プロセッサ３０１、ＲＡＭ３０２、ＨＤＤ３０３、画像信号処理部３０４、入力信号処理部３０５、媒体リーダ３０６および通信インタフェース３０７を有する。各ユニットはサーバコンピュータ３００のバスに接続されている。クライアントコンピュータもサーバコンピュータ３００と同様のユニットを用いて実現できる。
【０１２３】
プロセッサ３０１は、サーバコンピュータ３００の情報処理を制御する。プロセッサ３０１は、マルチプロセッサであってもよい。プロセッサ３０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ３０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【０１２４】
ＲＡＭ３０２は、サーバコンピュータ３００の主記憶装置である。ＲＡＭ３０２は、プロセッサ３０１に実行させるＯＳのプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ３０２は、プロセッサ３０１による処理に用いる各種データを記憶する。
【０１２５】
ＲＡＭ３０２には、ＨＤＤ３０３から読み出したデータを格納するためのキャッシュＣ２が設けられている。キャッシュＣ２は、キャッシュＣ１と同様に、ＲＡＭ３０２のある記憶領域を所定サイズに区分したページの集合である。
【０１２６】
ＨＤＤ３０３は、サーバコンピュータ３００の補助記憶装置である。ＨＤＤ３０３は、内蔵した磁気ディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ３０３は、ＯＳのプログラム、アプリケーションプログラム、および各種データを記憶する。サーバコンピュータ３００は、フラッシュメモリやＳＳＤなどの他の種類の補助記憶装置を備えてもよく、複数の補助記憶装置を備えてもよい。
【０１２７】
画像信号処理部３０４は、プロセッサ３０１からの命令に従って、サーバコンピュータ３００に接続されたディスプレイ３１に画像を出力する。ディスプレイ３１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【０１２８】
入力信号処理部３０５は、サーバコンピュータ３００に接続された入力デバイス３２から入力信号を取得し、プロセッサ３０１に出力する。入力デバイス３２としては、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【０１２９】
媒体リーダ３０６は、記録媒体３３に記録されたプログラムやデータを読み取る装置である。記録媒体３３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。また、記録媒体３３として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することもできる。媒体リーダ３０６は、例えば、プロセッサ３０１からの命令に従って、記録媒体３３から読み取ったプログラムやデータをＲＡＭ３０２またはＨＤＤ３０３に格納する。
【０１３０】
通信インタフェース３０７は、ネットワーク３４を介して他の装置と通信を行う。通信インタフェース３０７は、有線通信インタフェースでもよいし、無線通信インタフェースでもよい。
【０１３１】
サーバコンピュータ３００は、ＲＡＭ３０２に記憶されたプログラムをプロセッサ３０１により実行することで、ＨＤＤ３０３へのデータアクセスに対し、キャッシュ制御部１１０と同様の機能を発揮することができる。
【０１３２】
ここで、第１の実施の形態の情報処理は、制御部１ａにプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、プロセッサ１０１，３０１にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体２１，３３に記録できる。
【０１３３】
例えば、プログラムを記録した記録媒体２１，３３を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体２１，３３に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＲＡＭ１０２やＮＶＲＡＭ１０３（あるいは、ＲＡＭ３０２やＨＤＤ３０３）などの記憶装置に格納（インストール）してもよい。コンピュータは、当該記憶装置からプログラムを読み込んで実行してもよい。
【符号の説明】
【０１３４】
１  情報処理装置
１ａ  制御部
１ｂ  メモリ
２  記憶装置
Ｍ１  キャッシュメモリ
ＢＬ１，ＢＬ２，ＢＬ３  メモリブロック
Ｌ１  第１ＬＲＵリスト
Ｌ２  第２ＬＲＵリスト
Ｌ１ａ，Ｌ１ｂ，Ｌ１ｃ，・・・，Ｌ１ｍ，Ｌ２ａ，Ｌ２ｂ，Ｌ２ｃ，・・・，Ｌ２ｎ  リスト要素
【図１】
2017117179.tif 000003
【図２】
2017117179.tif 000004
【図３】
2017117179.tif 000005
【図４】
2017117179.tif 000006
【図５】
2017117179.tif 000007
【図６】
2017117179.tif 000008
【図７】
2017117179.tif 000009
【図８】
2017117179.tif 000010
【図９】
2017117179.tif 000011
【図１０】
2017117179.tif 000012
【図１１】
2017117179.tif 000013
【図１２】
2017117179.tif 000014
【図１３】
2017117179.tif 000015
【図１４】
2017117179.tif 000016
【図１５】
2017117179.tif 000017
【図１６】
2017117179.tif 000018
【図１７】
2017117179.tif 000019
【図１８】
2017117179.tif 000020