(57)【要約】【課題】プリフェッチを行う場合におけるキャッシュ用メモリの利用効率を向上させる。【解決手段】制御部１３は、アクセスされたデータブロック１４ａ，１４ｂの記憶装置１１上における位置関係に基づいて、アクセスのストリーム１５を示すストリーム情報１６を生成する。制御部１３は、ストリーム情報１６に基づいてメモリ１２に先読みされたデータブロック１４ｃ，１４ｄに、記憶装置１１上における位置関係に応じたシーケンス情報１７ａ，１７ｂを対応付ける。制御部１３は、データブロック１４ｄがアクセスされた場合、シーケンス情報１７ａ，１７ｂに基づいて、ストリーム１５によるアクセスの順序がデータブロック１４ｄより前であると判断されるデータブロック１４ｃを検索する。制御部１３は、データブロック１４ｃをメモリ１２から削除する。【選択図】図１
2017072981.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置に記憶されたデータブロックをキャッシュするメモリと、
アクセスされた複数の第１のデータブロックの前記記憶装置上における位置関係に基づいて、所定の規則条件を満たすアクセスのストリームを検出し、前記ストリームを示すストリーム情報を生成し、前記ストリーム情報に基づいて前記記憶装置から前記メモリに先読みされた複数の第２のデータブロックそれぞれに、前記記憶装置上における前記複数の第２のデータブロックの位置関係に応じたシーケンス情報を対応付け、前記複数の第２のデータブロックのうち一の第２のデータブロックがアクセスされた場合、前記シーケンス情報に基づいて、前記複数の第２のデータブロックのうち前記ストリームによるアクセスの順序が前記一の第２のデータブロックより前であると判断される１または２以上の他の第２のデータブロックを検索し、前記１または２以上の他の第２のデータブロックを前記メモリから削除する制御部と、
を有する情報処理装置。
【請求項２】
前記１または２以上の他の第２のデータブロックの削除は、前記ストリーム情報に基づく先読み以外の方法によって前記メモリにキャッシュされた第３のデータブロックの削除よりも優先的に実行される、
請求項１記載の情報処理装置。
【請求項３】
前記１または２以上の他の第２のデータブロックの削除は、前記ストリームによるアクセスがスキップされた第２のデータブロックを削除することを含む、
請求項１記載の情報処理装置。
【請求項４】
前記シーケンス情報は、昇順のシーケンス番号を含み、
前記１または２以上の他の第２のデータブロックの検索は、前記複数の第２のデータブロックのうち前記シーケンス番号が前記一の第２のデータブロックより小さい第２のデータブロックを検索することによって行う、
請求項１記載の情報処理装置。
【請求項５】
コンピュータが実行するキャッシュ制御方法であって、
アクセスされた複数の第１のデータブロックの記憶装置上における位置関係に基づいて、所定の規則条件を満たすアクセスのストリームを検出し、前記ストリームを示すストリーム情報を生成し、
前記ストリーム情報に基づいて前記記憶装置からメモリに先読みされた複数の第２のデータブロックそれぞれに、前記記憶装置上における前記複数の第２のデータブロックの位置関係に応じたシーケンス情報を対応付け、
前記複数の第２のデータブロックのうち一の第２のデータブロックがアクセスされた場合、前記シーケンス情報に基づいて、前記複数の第２のデータブロックのうち前記ストリームによるアクセスの順序が前記一の第２のデータブロックより前であると判断される１または２以上の他の第２のデータブロックを検索し、
前記１または２以上の他の第２のデータブロックを前記メモリから削除する、
キャッシュ制御方法。
【請求項６】
コンピュータに、
アクセスされた複数の第１のデータブロックの記憶装置上における位置関係に基づいて、所定の規則条件を満たすアクセスのストリームを検出し、前記ストリームを示すストリーム情報を生成し、
前記ストリーム情報に基づいて前記記憶装置からメモリに先読みされた複数の第２のデータブロックそれぞれに、前記記憶装置上における前記複数の第２のデータブロックの位置関係に応じたシーケンス情報を対応付け、
前記複数の第２のデータブロックのうち一の第２のデータブロックがアクセスされた場合、前記シーケンス情報に基づいて、前記複数の第２のデータブロックのうち前記ストリームによるアクセスの順序が前記一の第２のデータブロックより前であると判断される１または２以上の他の第２のデータブロックを検索し、
前記１または２以上の他の第２のデータブロックを前記メモリから削除する、
処理を実行させるキャッシュ制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、キャッシュ制御方法およびキャッシュ制御プログラムに関する。
【背景技術】
【０００２】
情報処理システムでは、大量のデータを記憶するために比較的低速な記憶装置（例えば、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）などの補助記憶装置）を使用することが多い。アクセス要求が発行される毎に低速な記憶装置にアクセスすると、データアクセスが処理性能のボトルネックになることがある。そこで、低速な記憶装置に記憶されたデータの一部を、比較的高速なメモリ（例えば、ＲＡＭ（Random Access Memory）などの主記憶装置）にキャッシュしておくことがある。メモリにキャッシュされたデータは、元の記憶装置にアクセスせずに提供することができる。
【０００３】
例えば、使用される可能性の高い所定のデータをメモリにキャッシュしておくことが考えられる。また、例えば、一度使用されたデータは再度使用される可能性が高いというアクセスの局所性を仮定して、使用されたデータをメモリに残しておくことが考えられる。ここで、データをキャッシュするメモリは元の記憶装置よりも容量が小さいことが多いため、キャッシュするデータの置換が発生する。メモリから削除するデータを選択する方法として、ＬＲＵ（Least Recently Used）アルゴリズムなどのページ置換アルゴリズムが用いられる。ＬＲＵアルゴリズムは、最近最も使用されていないデータ（連続して使用されていない時間が最も長いデータ）を優先的に削除するものである。
【０００４】
ところで、データアクセスの中には、元の記憶装置上の連続した領域をシーケンシャルにアクセスするものや一定間隔ずつ空いた領域をアクセスするものなど、連続性のあるデータアクセスが存在する。連続性のあるデータアクセスが検出された場合、アクセス要求を待たずに次に要求されるデータを予測してメモリに先読みすること（プリフェッチ）を行うことがある。プリフェッチによって、短時間に繰り返し使用されるものではないデータについてもデータアクセスを高速化することができる。
【０００５】
なお、バッファに先読みされた複数のデータブロックの中から削除するものを決定する置換決定回路が提案されている。提案の置換決定回路は、ＬＲＵアルゴリズムによって２以上の削除候補のデータブロックが選択されると、選択された削除候補のうちバッファ上で１度もアクセスされなかったデータブロックを優先的に削除する。
【０００６】
また、プロセッサとは別に、プロセッサが使用するデータをキャッシュメモリに先読みするキャッシュ制御部を有するデータ処理装置が提案されている。当該キャッシュ制御部は、キャッシュメモリに記憶されたデータのうちプロセッサによって使用されたデータを優先的に削除する。また、複数の記憶領域のうちプリフェッチに使用可能な記憶領域を制限するキャッシュ記憶装置が提案されている。提案のキャッシュ記憶装置は、新たなデータを先読みするとき、プリフェッチ用の記憶領域に記憶されたデータを削除し、プリフェッチ用でない記憶領域に記憶されたデータは削除しない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭６３−３１８６５４号公報
【特許文献２】特開平９−２１２４２１号公報
【特許文献３】特開２００１−１９５３０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
連続性のあるデータアクセスは広範囲の領域のデータを要求することが多く、連続性のあるデータアクセスが継続している間は次々とデータがメモリに先読みされることになる。しかし、連続性のあるデータアクセスでは、記憶装置上の複数の領域のデータが一定の方向性をもって要求され、その方向性が崩れることは少ない。例えば、記憶装置上の複数の領域のデータがアドレスの昇順に要求されている場合、ある領域のデータが要求された後に当該領域よりアドレスの小さい領域のデータが要求されるようにアクセス順序が変わる可能性は低い。連続性のあるデータアクセスの進行に伴って、メモリに先読みされたデータの一部が使用される可能性の低いデータになっていく。
【０００９】
このとき、先読みしたデータとそれ以外の他のデータとを纏めて通常のページ置換アルゴリズムを適用すると、以降使用される可能性の低い先読みデータよりも、使用される可能性がある他のデータが先にメモリから削除されてしまうことが発生し得る。そのため、キャッシュ用メモリの利用効率が低下するという問題がある。また、上記特許文献３に記載された技術のようにプリフェッチ用の記憶領域と他の記憶領域を分離すると、２種類の記憶領域の一方に空きがあり他方に空きがない状況が発生する可能性があり、キャッシュ用メモリの利用効率が低下してしまうおそれがある。
【００１０】
１つの側面では、本発明は、プリフェッチを行う場合におけるキャッシュ用メモリの利用効率を向上できる情報処理装置、キャッシュ制御方法およびキャッシュ制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
１つの態様では、メモリと制御部とを有する情報処理装置が提供される。メモリは、記憶装置に記憶されたデータブロックをキャッシュする。制御部は、アクセスされた複数の第１のデータブロックの記憶装置上における位置関係に基づいて、所定の規則条件を満たすアクセスのストリームを検出し、ストリームを示すストリーム情報を生成する。制御部は、ストリーム情報に基づいて記憶装置からメモリに先読みされた複数の第２のデータブロックそれぞれに、記憶装置上における複数の第２のデータブロックの位置関係に応じたシーケンス情報を対応付ける。制御部は、複数の第２のデータブロックのうち一の第２のデータブロックがアクセスされた場合、シーケンス情報に基づいて、複数の第２のデータブロックのうちストリームによるアクセスの順序が一の第２のデータブロックより前であると判断される１または２以上の他の第２のデータブロックを検索する。制御部は、１または２以上の他の第２のデータブロックをメモリから削除する。
【００１２】
また、１つの態様では、コンピュータが実行するキャッシュ制御方法が提供される。また、１つの態様では、コンピュータに実行させるキャッシュ制御プログラムが提供される。
【発明の効果】
【００１３】
１つの側面では、プリフェッチを行う場合におけるキャッシュ用メモリの利用効率が向上する。
【図面の簡単な説明】
【００１４】
【図１】第１の実施の形態の情報処理装置の例を示す図である。
【図２】情報処理装置のハードウェア例を示すブロック図である。
【図３】キャッシュのページ管理の例を示す図である。
【図４】連続性のあるデータアクセスとプリフェッチの例を示す図である。
【図５】ＬＲＵアルゴリズムの例を示す図である。
【図６】ストリームが通過したページの例を示す図である。
【図７】情報処理装置の機能例を示すブロック図である。
【図８】管理構造体の例を示す図である。
【図９】ハッシュテーブルの例を示す図である。
【図１０】シーケンスＩＤテーブルの例を示す図である。
【図１１】ＬＲＵ管理リストと優先置換ページリストの例を示す図である。
【図１２】ストリームテーブルの例を示す図である。
【図１３】プリフェッチ制御の手順例を示すフローチャートである。
【図１４】置換ページ決定の手順例を示すフローチャートである。
【図１５】キャッシュヒット判定の手順例を示すフローチャートである。
【図１６】ストリーム通過判定の手順例を示すフローチャートである。
【図１７】連続性検出の手順例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態を説明する。
【００１６】
図１は、第１の実施の形態の情報処理装置の例を示す図である。
第１の実施の形態の情報処理装置１０は、情報処理装置１０で実行されるプロセスまたは他の情報処理装置で実行されるプロセスからの要求に応じて、データアクセスを行う。データアクセスには、データの読み出しとデータの書き込みとが含まれる。情報処理装置１０は、サーバコンピュータなどのサーバ装置でもよいし、クライアントコンピュータなどのクライアント装置でもよい。また、情報処理装置１０は、ストレージ装置でもよい。
【００１７】
情報処理装置１０は、記憶装置１１、メモリ１２および制御部１３を有する。ただし、記憶装置１１は情報処理装置１０からアクセス可能であればよく、情報処理装置１０の外部に存在していてもよい。記憶装置１１は、アクセスが比較的低速な記憶装置である。例えば、記憶装置１１は、ＨＤＤやＳＳＤなどの不揮発性の記憶装置である。メモリ１２は、記憶装置１１よりもアクセスが高速なメモリである。例えば、メモリ１２は、ＲＡＭなどの揮発性の半導体メモリである。メモリ１２の記憶容量は記憶装置１１よりも小さい。
【００１８】
制御部１３は、例えば、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）などのプロセッサである。ただし、制御部１３は、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路を含んでもよい。プロセッサは、ＲＡＭなどのメモリに記憶されたプログラムを実行する。プログラムには、キャッシュ制御プログラムが含まれる。複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼ぶこともある。
【００１９】
記憶装置１１は、データブロック１４ａ，１４ｂ，１４ｃ，１４ｄを含む複数のデータブロックを記憶する。各データブロックは、記憶装置１１からメモリ１２にロードされるデータ単位であり、例えば、所定サイズのデータ単位である。データブロックは、ページやセグメントなどと言うこともできる。データブロック１４ａ，１４ｂ，１４ｃ，１４ｄの位置は、記憶装置１１の物理アドレスを用いて特定することができる。
【００２０】
データブロック１４ａ，１４ｂ，１４ｃ，１４ｄは、物理アドレスの小さい順または物理アドレスの大きい順に並んでいる。例えば、データブロック１４ｂはデータブロック１４ａより物理アドレスが大きく、データブロック１４ｃはデータブロック１４ｂより物理アドレスが大きく、データブロック１４ｄはデータブロック１４ｃより物理アドレスが大きい。データブロック１４ａ，１４ｂ，１４ｃ，１４ｄが存在する領域は、記憶装置１１上で隣接していてもよいし、閾値未満の距離だけ離れていてもよい。
【００２１】
メモリ１２は、記憶装置１１に記憶された複数のデータブロックのうちの一部のデータブロックをキャッシュする。キャッシュ用に使用可能なメモリ１２の領域が満杯であるときに、キャッシュされていないデータブロックが要求されると、メモリ１２に記憶された１または２以上のデータブロックがメモリ１２から削除される。削除するデータブロックの選択には、ＬＲＵアルゴリズムなどの所定のページ置換アルゴリズムが用いられる。ＬＲＵアルゴリズムは、メモリ１２上で最近最も使用されていないデータブロック（連続して使用されていない時間が最も長いデータブロック）を優先的に削除するものである。ただし、後述するように、所定条件を満たしたデータブロックが、通常のページ置換アルゴリズムによって選択されるデータブロックよりも優先的に削除されることがある。
【００２２】
制御部１３は、メモリ１２にロードされてアクセスされた２以上のデータブロック（第１のデータブロック）について、それらデータブロックの記憶装置１１上における位置関係に基づいて、所定の規則条件を満たすアクセスのストリーム１５を検出する。ストリーム１５は、例えば、２以上のデータブロックを物理アドレスの昇順または降順にアクセスするものであり、前回と今回のデータブロックの距離が閾値未満であるものである。ストリーム１５は、連続性のあるデータアクセスと言うこともできる。
【００２３】
例えば、データブロック１４ａがアクセスされた後にデータブロック１４ｂがアクセスされた場合、データブロック１４ａの近辺の２以上のデータブロックを物理アドレスの昇順にアクセスするストリーム１５が検出される。制御部１３は、検出したストリーム１５を示すストリーム情報１６を生成する。ストリーム情報１６は、メモリ１２に記憶されてもよい。ストリーム情報１６は、例えば、ストリーム１５の識別情報や、ストリーム１５によって最後にアクセスされたデータブロックの物理アドレスなどを含む。
【００２４】
制御部１３は、生成したストリーム情報１６に基づいて、要求を待たずに記憶装置１１からメモリ１２に２以上のデータブロック（第２のデータブロック）を先読みする（プリフェッチ）。例えば、制御部１３は、ストリーム１５によって最後にアクセスされたデータブロックよりも物理アドレスが大きく、最後にアクセスされたデータブロックからの距離が閾値以下であるデータブロックを、メモリ１２に先読みする。一例として、制御部１３は、データブロック１４ｃ，１４ｄを記憶装置１１からメモリ１２に先読みする。
【００２５】
また、制御部１３は、先読みしたデータブロックそれぞれに対して、記憶装置１１上におけるデータブロックの位置関係に応じたシーケンス情報を対応付ける。シーケンス情報は、記憶装置１１の物理アドレスでもよいし、物理アドレスとは異なるシーケンス番号でもよい。シーケンス番号は、先読みされたデータブロックに対して、物理アドレスの昇順または降順に付与される連番でもよい。例えば、制御部１３は、データブロック１４ｃにシーケンス情報１７ａを対応付け、データブロック１４ｄにシーケンス情報１７ｂを対応付ける。シーケンス情報１７ａ，１７ｂは、メモリ１２に記憶されてもよい。
【００２６】
メモリ１２に先読みされたデータブロックのうち一のデータブロックがアクセスされた場合、制御部１３は、シーケンス情報に基づいて、ストリーム１５によるアクセスの順序が当該一のデータブロックより前であると判断されるデータブロックを検索する。例えば、シーケンス情報が昇順のシーケンス番号である場合、制御部１３は、メモリ１２に記憶されたデータブロックのうち、アクセスされたデータブロックよりも小さいシーケンス番号をもつものを検索する。また、例えば、シーケンス情報が降順のシーケンス番号である場合、制御部１３は、メモリ１２に記憶されたデータブロックのうち、アクセスされたデータブロックよりも大きいシーケンス番号をもつものを検索する。
【００２７】
一例として、データブロック１４ｄがアクセスされた場合、制御部１３は、シーケンス情報１７ａ，１７ｂに基づいてデータブロック１４ｃを検索する。データブロック１４ｃは、データブロック１４ｄから見て、ストリーム１５の進行方向とは逆方向の物理アドレスをもつデータブロックである。データブロック１４ｃは、プリフェッチ時に予測されたアクセス順序がデータブロック１４ｄよりも前であり、ストリーム１５が既に通過したデータブロックであると言える。ただし、データブロック１４ｃはメモリ１２上でアクセスされた場合もあるしアクセスされなかった場合もある。プリフェッチに反して、ストリーム１５がデータブロック１４ｃへのアクセスをスキップする可能性があるためである。
【００２８】
そして、制御部１３は、上記の検索したデータブロックをメモリ１２から削除する。検索されたデータブロックは、通常のページ置換アルゴリズムによって選択されるデータブロックよりも優先的に削除される。ストリーム１５が通過したデータブロックをメモリ１２から削除するタイミングは、該当するデータブロックが検索されたときでもよいし、キャッシュされたデータブロックを入れ替えるときでもよい。一例として、制御部１３は、メモリ１２のキャッシュ用領域が不足したとき、検索されたデータブロック１４ｃを他のデータブロックよりも優先してメモリ１２から削除する。
【００２９】
第１の実施の形態の情報処理装置１０によれば、ストリーム１５を示すストリーム情報１６に基づいて先読みされたデータブロック１４ｃ，１４ｄに、記憶装置１１上における位置関係に応じたシーケンス情報１７ａ，１７ｂが対応付けられる。データブロック１４ｄがアクセスされた場合、シーケンス情報１７ａ，１７ｂに基づいて、ストリーム１５によるアクセスの順序がデータブロック１４ｄより前であると判断されるデータブロック１４ｃが検索され、メモリ１２から削除される。
【００３０】
ストリーム１５は、２以上のデータブロックを一定の方向性（記憶装置１１の物理アドレスの昇順または降順）に従ってアクセスし、その方向性が崩れることは少ない。このため、データブロック１４ｄがアクセスされると、ストリーム１５が既に通過したデータブロック１４ｃがその後にアクセスされる可能性は低い。アクセスされる可能性の低いデータブロック１４ｃを優先的にメモリ１２から削除することで、メモリ１２に空き領域を確保することができる。よって、アクセスされる可能性のある他のデータブロックがデータブロック１４ｃよりも先にメモリ１２から削除されてしまうことを抑制でき、メモリ１２のキャッシュ用領域の利用効率を向上させることができる。
【００３１】
［第２の実施の形態］
次に、第２の実施の形態を説明する。
図２は、情報処理装置のハードウェア例を示すブロック図である。
【００３２】
情報処理装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７は、バス１０８に接続されている。なお、情報処理装置１００は、第１の実施の形態の情報処理装置１０に対応する。ＣＰＵ１０１は、第１の実施の形態の制御部１３に対応する。ＲＡＭ１０２は、第１の実施の形態のメモリ１２に対応する。ＨＤＤ１０３は、第１の実施の形態の記憶装置１１に対応する。情報処理装置１００は、クライアントコンピュータなどのクライアント装置でもよいし、サーバコンピュータなどのサーバ装置でもよい。
【００３３】
ＣＰＵ１０１は、プログラムの命令を実行する演算回路を含むプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されたプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、情報処理装置１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列に実行してもよい。また、複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼んでもよい。
【００３４】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムやＣＰＵ１０１が演算に用いるデータを一時的に記憶する揮発性の半導体メモリである。なお、情報処理装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００３５】
ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。プログラムには、キャッシュ制御プログラムが含まれる。なお、情報処理装置１００は、フラッシュメモリやＳＳＤなどの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００３６】
画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、情報処理装置１００に接続されたディスプレイ１１１に画像を出力する。ディスプレイ１１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００３７】
入力信号処理部１０５は、情報処理装置１００に接続された入力デバイス１１２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス１１２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、情報処理装置１００に、複数の種類の入力デバイスが接続されていてもよい。
【００３８】
媒体リーダ１０６は、記録媒体１１３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体１１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０６は、例えば、記録媒体１１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３９】
通信インタフェース１０７は、ネットワーク１１４に接続され、ネットワーク１１４を介して他の装置と通信を行うインタフェースである。通信インタフェース１０７は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００４０】
次に、ＨＤＤ１０３に記憶されたデータのＲＡＭ１０２へのキャッシュを説明する。
図３は、キャッシュのページ管理の例を示す図である。
情報処理装置１００は、情報処理装置１００または他の情報処理装置のプロセスが発行したアクセス要求に応じて、データの読み出しまたは書き込みを行う。アクセス要求に応じたデータ処理は、ＲＡＭ１０２にキャッシュされたデータに対して行う。アクセス要求によって指定されたデータがＲＡＭ１０２にキャッシュされていない場合、情報処理装置１００は、ＨＤＤ１０３からＲＡＭ１０２にデータをロードする。ＨＤＤ１０３からＲＡＭ１０２へのデータのロードは、所定サイズのページ単位で行う。
【００４１】
ＲＡＭ１０２には、それぞれ１つのページを記憶できる複数の領域が予め確保されている。複数の領域それぞれについて、当該領域に記憶されたページを管理するための管理構造体が予め生成されてＲＡＭ１０２に記憶されている。複数の領域は、領域１２１ａ，１２１ｂ，１２１ｃを含む。ＲＡＭ１０２は、領域１２１ａに対応する管理構造体１３１ａと、領域１２１ｂに対応する管理構造体１３１ｂと、領域１２１ｃに対応する管理構造体１３１ｃとを記憶する。ＨＤＤ１０３は、ページ２１ａ（Ｐ１）、ページ２１ｂ（Ｐ２）、ページ２１ｃ（Ｐ３）、ページ２１ｄ（Ｐ４）を含む複数のページを記憶する。
【００４２】
ページ２１ａに属する物理アドレスを指定したアクセス要求が到着した場合、例えば、情報処理装置１００は、ページ２１ａをＨＤＤ１０３から領域１２１ａにロードする（ページイン）。このとき、情報処理装置１００は、管理構造体１３１ａを更新する。また、ページ２１ｂに属する物理アドレスを指定したアクセス要求が到着した場合、例えば、情報処理装置１００は、ページ２１ｂをＨＤＤ１０３から領域１２１ｂにロードする。このとき、情報処理装置１００は、管理構造体１３１ｂを更新する。また、ページ２１ｄに属する物理アドレスを指定したアクセス要求が到着した場合、例えば、情報処理装置１００は、ページ２１ｄをＨＤＤ１０３から領域１２１ｃにロードする。このとき、情報処理装置１００は、管理構造体１３１ｃを更新する。
【００４３】
図４は、連続性のあるデータアクセスとプリフェッチの例を示す図である。
１つのプロセスが行うデータアクセスには、ＨＤＤ１０３上の離れたページに対する散発的なデータアクセスと、ＨＤＤ１０３上の近接するページに対する連続性のあるデータアクセスとがある。第２の実施の形態では、連続性のあるデータアクセスとして、ＨＤＤ１０３の物理アドレスの昇順に複数のページが要求されるものを考える。連続性のあるデータアクセスの集合を「ストリーム」と言うことがある。
【００４４】
連続性のあるデータアクセスには、（Ａ）連続領域のアクセスと、（Ｂ）間欠的領域のアクセスとが含まれる。連続領域のアクセスは、あるページを要求した後に、当該ページより物理アドレスが大きい隣のページを要求するものである。複数のアクセス要求によって次々と隣のページが要求されることにより、一続きの連続領域が要求されることになる。間欠的領域のアクセスは、あるページを要求した後に、当該ページより物理アドレスが大きく当該ページの末尾からの距離が閾値Ｒ未満であるページを要求するものである。
【００４５】
例えば、連続領域のアクセスについて、あるページを要求するデータアクセス３１ａが発生する。次に、データアクセス３１ａの隣のページを要求するデータアクセス３１ｂが発生する。同様に、データアクセス３１ｂの隣のページを要求するデータアクセス３１ｃが発生する。データアクセス３１ｃの隣のページを要求するデータアクセス３１ｄが発生する。データアクセス３１ａ，３１ｂ，３１ｃ，３１ｄは、１つのストリームに属する。
【００４６】
また、例えば、間欠的領域のアクセスについて、あるページを要求するデータアクセス３２ａが発生する。次に、データアクセス３２ａの近くのページを要求するデータアクセス３２ｂが発生する。データアクセス３２ａの末尾とデータアクセス３２ｂの先頭との間の距離は、閾値Ｒ未満である。同様に、データアクセス３２ｂの近くのページを要求するデータアクセス３２ｃが発生する。データアクセス３２ｂの末尾とデータアクセス３２ｃの先頭との間の距離は、閾値Ｒ未満である。データアクセス３２ｃの近くのページを要求するデータアクセス３２ｄが発生する。データアクセス３２ｃの末尾とデータアクセス３２ｄの先頭との間の距離は、閾値Ｒ未満である。データアクセス３２ａ，３２ｂ，３２ｃ，３２ｄは、連続領域のアクセスの場合と同様に１つのストリームに属する。
【００４７】
ここで、連続性のあるデータアクセスについては、データアクセスに規則性があるため次に要求される可能性のあるページを絞り込むことが可能である。そこで、情報処理装置１００は、アクセスのストリームが検出されると、アクセス要求を待たずに、ＨＤＤ１０３からＲＡＭ１０２にページを先読みする（プリフェッチ）。
【００４８】
上記の連続領域のアクセスの場合、情報処理装置１００は、データアクセス３１ｄの後にプリフェッチ３１ｅを実行する。プリフェッチ３１ｅでは、情報処理装置１００は、データアクセス３１ｄのページより物理アドレスが大きくデータアクセス３１ｄの末尾から所定距離内にあるページを先読みする。上記の間欠的領域のアクセスの場合、情報処理装置１００は、データアクセス３２ｄの後にプリフェッチ３２ｅを実行する。プリフェッチ３２ｅでは、情報処理装置１００は、データアクセス３２ｄのページより物理アドレスが大きくデータアクセス３２ｄの末尾から所定距離内にあるページを先読みする。
【００４９】
図５は、ＬＲＵアルゴリズムの例を示す図である。
ＲＡＭ１０２の全ての領域がページを記憶しており、キャッシュされていない他のページが要求された場合、情報処理装置１００は、何れかの領域のページをＲＡＭ１０２から追い出すことになる。第２の実施の形態では、キャッシュされた複数のページの中から追い出すページを選択するページ置換アルゴリズムとして、ＬＲＵアルゴリズムを用いる。
【００５０】
情報処理装置１００は、ＲＡＭ１０２に記憶された複数のページを、例えば、図５に示すようなリストを用いて管理する。ＭＲＵ（Most Recently Used）ページは、直近に使用されたページである。ＬＲＵページは、最近最も使用されていないページである。ここでは、ページ２１ａ，２１ｂ，２１ｃ，２１ｄ、ページ２１ｅ（Ｐ５）、ページ２１ｆ（Ｐ６）がリストに登録されている。ページ２１ａはリストの先頭にあるページであり、ＭＲＵページである。ページ２１ｂはリストの２番目、ページ２１ｃはリストの３番目、ページ２１ｄはリストの４番目、ページ２１ｅはリストの末尾から２番目にあるページである。ページ２１ｆはリストの末尾にあるページであり、ＬＲＵページである。
【００５１】
このとき、キャッシュ済みのページ２１ｃが要求される（キャッシュヒットする）と、リスト上でページ２１ｃが先頭に移動してＭＲＵページになる。これに伴い、リスト上でページ２１ａ，２１ｂがＬＲＵ側にシフトする。キャッシュされていないページ２１ｇ（Ｐ７）が要求される（キャッシュミスヒットする）と、リスト上でページ２１ｇが先頭に追加されＭＲＵページになる。これに伴い、リスト上でページ２１ａ，２１ｂ，２１ｃ，２１ｄ，２１ｅがＬＲＵ側にシフトする。また、リストの末尾に登録されていたページ２１ｆ（ＬＲＵページ）が、リストから追い出される。
【００５２】
よって、通常のＬＲＵアルゴリズムによれば、ページ２１ｆがＲＡＭ１０２から削除され（ページアウト）、ページ２１ｇがＲＡＭ１０２にロードされる（ページイン）。すなわち、ページ２１ｆがページ２１ｇに置き換えられることになる。
【００５３】
しかし、プリフェッチによってロードされたページとそれ以外のページとを纏めて通常のＬＲＵアルゴリズムを適用すると、以降使用される可能性の低いページがＲＡＭ１０２に残りやすくなり、ＲＡＭ１０２の利用効率が低下するおそれがある。すなわち、ストリームによって要求されるページの順序には物理アドレスの昇順という規則性があるため、プリフェッチによってロードされたページのうちストリームが既に通過したページは以降使用される可能性が低い。そこで、情報処理装置１００は、ＬＲＵアルゴリズムによって選択されるページよりも、ストリームが通過した先読みページを優先的に削除する。
【００５４】
図６は、ストリームが通過したページの例を示す図である。
ここでは、１つのページのサイズが１０ｋＢ（キロバイト）であるとする。図６に記載されたアドレス範囲は、ＨＤＤ１０３の物理アドレスの範囲である。まず、プリフェッチ以外の方法により、３００〜３０９ｋＢのページ２２ｆがＲＡＭ１０２にロードされる。次に、プリフェッチによって、１００〜１０９ｋＢのページ２２ａ、１１０〜１１９ｋＢのページ２２ｂ、１２０〜１２９ｋＢのページ２２ｃ、１３０〜１３９ｋＢのページ２２ｄ、１４０〜１４９ｋＢのページ２２ｅが順にＲＡＭ１０２にロードされる。
【００５５】
先読みされたページ２２ａ，２２ｂ，２２ｃ，２２ｄ，２２ｅには、先読みされた順番、すなわち、ＨＤＤ１０３の物理アドレスの順に、昇順のシーケンス番号が付与される。ページ２２ａにはシーケンス番号「ＳＱ１」、ページ２２ｂにはシーケンス番号「ＳＱ２」、ページ２２ｃにはシーケンス番号「ＳＱ３」、ページ２２ｄにはシーケンス番号「ＳＱ４」、ページ２２ｅにはシーケンス番号「ＳＱ５」が付与される。
【００５６】
ストリームによってページ２２ａが要求されると、ページ２２ａがＭＲＵページになる。このとき、ページ２２ａのシーケンス番号「ＳＱ１」より小さいシーケンス番号をもつページは存在しないため、通過済みのページは存在しない。次に、ストリームによってページ２２ｂが要求されると、ページ２２ｂがＭＲＵページになる。このとき、情報処理装置１００は、ページ２２ｂのシーケンス番号「ＳＱ２」より小さいシーケンス番号をもつページ２２ａを検索し、ストリームがページ２２ａを通過済みであると判断する。この時点で、ページ２２ａはＲＡＭ１０２から削除可能である。
【００５７】
次に、ストリームによってページ２２ｄが要求されると、ページ２２ｄがＭＲＵページになる。このとき、情報処理装置１００は、ページ２２ｄのシーケンス番号「ＳＱ４」より小さいシーケンス番号をもつページ２２ｂ，２２ｃを検索し、ストリームがページ２２ｂ，２２ｃを通過済みであると判断する。ページ２２ｃはＲＡＭ１０２に先読みされてから使用されなかったものの、ストリームによってスキップされたと判断される。この時点で、ページ２２ｂ，２２ｃはＲＡＭ１０２から削除可能である。
【００５８】
なお、第２の実施の形態では、通過済みと判断されたページは、すぐにＲＡＭ１０２から削除されるのではなく、プリフェッチを行うときまたはキャッシュミスヒットが発生したときに削除される。通過済みのページがＲＡＭ１０２に残っている場合、ＬＲＵアルゴリズムによって選択されるページよりも優先的に通過済みのページが削除される。よって、ページ２２ａ，２２ｂ，２２ｃは、ページ２２ｆよりも優先的に削除される。
【００５９】
次に、情報処理装置１００の機能について説明する。
図７は、情報処理装置の機能例を示すブロック図である。
情報処理装置１００は、記憶部１３０、アクセス要求受付部１４１、プリフェッチ制御部１４２、置換ページ決定部１４３、キャッシュヒット判定部１４４、ストリーム通過判定部１４５および連続性検出部１４６を有する。記憶部１３０は、例えば、ＲＡＭ１０２またはＨＤＤ１０３に確保した記憶領域を用いて実装される。アクセス要求受付部１４１、プリフェッチ制御部１４２、置換ページ決定部１４３、キャッシュヒット判定部１４４、ストリーム通過判定部１４５および連続性検出部１４６は、例えば、ＣＰＵ１０１が実行するプログラムモジュールを用いて実装される。
【００６０】
記憶部１３０は、管理構造体群１３１、ハッシュテーブル１３２、シーケンスＩＤテーブル１３３、ＬＲＵ管理リスト１３４、優先置換ページリスト１３５およびストリームテーブル群１３６を記憶する。
【００６１】
管理構造体群１３１は、ＲＡＭ１０２にキャッシュされたページを管理するための管理構造体の集合である。１つの管理構造体は、１つのページを記憶できる１つの領域に対応する。ＲＡＭ１０２には複数の領域が予め確保されており、それら複数の領域に対応するように管理構造体群１３１が予め生成されている。管理構造体群１３１には、図３に示した管理構造体１３１ａ，１３１ｂ，１３１ｃが含まれる。
【００６２】
ハッシュテーブル１３２は、ストリームを識別するストリームＩＤのハッシュ値と、当該ストリームについて先読みされたページを管理するための管理構造体とを対応付けたテーブルである。ハッシュテーブル１３２を用いることで、あるストリームのストリームＩＤから、当該ストリームに関連する管理構造体を高速に検索することができる。
【００６３】
シーケンスＩＤテーブル１３３は、複数のストリームそれぞれについて、当該ストリームのストリームＩＤと、当該ストリームについて現在使用しているシーケンスＩＤの最大値とを対応付けたテーブルである。シーケンスＩＤテーブルを用いることで、あるストリームについて先読みした各ページに対し、シーケンスＩＤが付与される。
【００６４】
ＬＲＵ管理リスト１３４は、ＲＡＭ１０２にキャッシュされているページの使用状況を示すリストである。ＬＲＵ管理リスト１３４は、ＬＲＵアルゴリズムに用いられる。ＬＲＵ管理リスト１３４は、図５に示したようなページ間の順位（ＭＲＵページからＬＲＵページに至る順位）を示す。ＬＲＵ管理リスト１３４は、ページ管理が容易になるように、該当するページに対応する管理構造体へのポインタを含む。ＬＲＵ管理リスト１３４を用いることで、ページアウトさせるページを選択できる。なお、情報処理装置１００がＬＲＵアルゴリズム以外のページ置換アルゴリズムを使用する場合、ＬＲＵ管理リスト１３４に代えて、当該ページ置換アルゴリズムに応じた情報が記憶部１３０に記憶される。
【００６５】
優先置換ページリスト１３５は、ＬＲＵ管理リスト１３４に基づいて選択されるページ（ＬＲＵページ）よりも優先的にページアウトさせるページの候補を示すリストである。優先置換ページリスト１３５が示すページは、ストリームが通過したページであり、以降使用される可能性が低いページである。優先置換ページリスト１３５は、ページ管理が容易になるように、該当するページに対応する管理構造体へのポインタを含む。
【００６６】
ストリームテーブル群１３６は、ストリームを管理するためのストリームテーブルの集合である。１つのストリームテーブルは、１つのストリームに対応する。情報処理装置１００において検出可能なストリームの最大数に相当する数のストリームテーブルが、予め生成されている。ストリームテーブル群１３６に含まれるストリームテーブルの数は、多いことが好ましい。例えば、数千から１万程度のストリームテーブルが用意される。ストリームテーブル群１３６を用いることで、連続性のあるアクセスのストリームが検出され、検出されたストリームに対してストリームＩＤが付与される。
【００６７】
アクセス要求受付部１４１は、情報処理装置１００で実行されるアプリケーションプロセスが発行したアクセス要求、または、他の情報処理装置が送信したアクセス要求を受け付ける。アクセス要求は、読み出し要求または書き込み要求である。読み出し要求には、対象のデータが格納されているＨＤＤ１０３の領域を示すアドレス情報が含まれる。アドレス情報は、例えば、先頭の物理アドレスとデータ長を含む。書き込み要求には、書き込むデータと、当該データを格納すべきＨＤＤ１０３の領域を示すアドレス情報が含まれる。以下では、アクセス要求として主に読み出し要求を想定して説明することがある。
【００６８】
プリフェッチ制御部１４２は、連続性検出部１４６からの指示に応じてページのプリフェッチを行う。すなわち、プリフェッチ制御部１４２は、連続性検出部１４６から指定されたページをＨＤＤ１０３からＲＡＭ１０２にロードする。このとき、プリフェッチ制御部１４２は、ページを格納する領域を置換ページ決定部１４３に問い合わせる。プリフェッチ制御部１４２は、置換ページ決定部１４３によって決定された領域に、ＨＤＤ１０３から読み出したページを上書きする。また、プリフェッチ制御部１４２は、上書きした領域に対応する管理構造体を、先読みしたページに対応するように更新する。
【００６９】
置換ページ決定部１４３は、プリフェッチ制御部１４２またはキャッシュヒット判定部１４４からの問い合わせに応じて、ページを読み込むべき領域を決定する。これは、ＲＡＭ１０２にキャッシュされているページ（先読みされたものとそれ以外のものを含む）の中からページアウトさせるページを選択するという意味も含む。置換ページ決定部１４３は、優先置換ページリスト１３５が空でない場合、優先置換ページリスト１３５が示すページを優先的に選択する。一方、置換ページ決定部１４３は、優先置換ページリスト１３５が空である場合、ＬＲＵアルゴリズムに従ってページを選択する。後者の場合、置換ページ決定部１４３は、ＬＲＵ管理リスト１３４を参照および更新する。
【００７０】
キャッシュヒット判定部１４４は、アクセス要求受付部１４１が受け付けたアクセス要求に従って、要求されたデータの提供またはデータの書き込みを実行する。対象ページがＲＡＭ１０２にキャッシュされていない場合、キャッシュヒット判定部１４４は、対象ページを格納する領域を置換ページ決定部１４３に問い合わせる。キャッシュヒット判定部１４４は、置換ページ決定部１４３によって決定された領域に、ＨＤＤ１０３から読み出したページを上書きする。また、キャッシュヒット判定部１４４は、上書きした領域に対応する管理構造体を、格納したページに対応するように更新する。対象ページがＲＡＭ１０２にキャッシュされている場合、キャッシュヒット判定部１４４は、対象ページがＭＲＵページになるようにＬＲＵ管理リスト１３４を更新する。
【００７１】
そして、キャッシュヒット判定部１４４は、ＲＡＭ１０２上の対象ページに対してデータ処理を行う。アクセス要求が読み出し要求である場合、キャッシュヒット判定部１４４は、要求されたデータをアクセス要求の発行元に送信する。アクセス要求が書き込み要求である場合、キャッシュヒット判定部１４４は、ページを更新してその結果をアクセス要求の発行元に送信する。また、キャッシュヒット判定部１４４は、対象ページがＲＡＭ１０２にキャッシュされておりかつプリフェッチされたページである場合、ストリームに属するページが使用されたことをストリーム通過判定部１４５に通知する。
【００７２】
ストリーム通過判定部１４５は、キャッシュヒット判定部１４４からの通知に応じて、ストリームが既に通過したページを検索する。検索するページは、キャッシュヒット判定部１４４で使用されたページと同じストリームに属し、かつ、当該使用されたページよりも小さいシーケンスＩＤが付与されている先読みページである。ストリーム通過判定部１４５は、優先置換ページリスト１３５が示すページに検索されたページが追加されるように、優先置換ページリスト１３５を更新する。これにより、ストリームが通過したページが、他のページよりも優先的にＲＡＭ１０２から削除されることになる。
【００７３】
連続性検出部１４６は、アクセス要求受付部１４１が受け付けるアクセス要求を監視する。連続性検出部１４６は、ストリームテーブル群１３６を用いて連続性のあるアクセスを検出し、各アクセスの属するストリームを判定する。連続性検出部１４６は、ストリームの進行（指定される物理アドレスの増加）に応じて、先読みするページを決定し、プリフェッチ制御部１４２にプリフェッチを指示する。
【００７４】
図８は、管理構造体の例を示す図である。
管理構造体群１３１に管理構造体１３１ａが含まれる。管理構造体１３１ａは、ＲＡＭ１０２の領域１２１ａに対応する。管理構造体１３１ａは、ストリームフラグ、ストリームＩＤ、シーケンスＩＤ、キャッシュアドレスおよびディスクアドレスを含む。
【００７５】
ストリームフラグは、領域１２１ａに記憶されたページがストリームに基づいて先読みされたページであるかを示す。ストリームフラグが「ＯＮ」（または「１」）であることは、記憶されたページがストリームに基づく先読みページであることを示す。ストリームフラグが「ＯＦＦ」（または「０」）であることは、記憶されたページがストリームに基づく先読みページでないことを示す。ストリームフラグの初期値は「ＯＦＦ」である。
【００７６】
ストリームＩＤは、ストリームフラグが「ＯＮ」である場合に、プリフェッチの契機となったストリームを示す。ストリームフラグが「ＯＦＦ」である場合は、ストリームＩＤは「ＮＵＬＬ」または「０」でよい。シーケンスＩＤは、同じストリームＩＤが付与された複数のページの間で一意である昇順の識別番号である。シーケンスＩＤは、プリフェッチの順序、すなわち、ＨＤＤ１０３の物理アドレスの小さい順に付与される。ストリームフラグが「ＯＦＦ」である場合は、シーケンスＩＤは「ＮＵＬＬ」または「０」でよい。
【００７７】
キャッシュアドレスは、領域１２１ａを識別するＲＡＭ１０２の物理アドレスである。キャッシュアドレスは、例えば、領域１２１ａの先頭の物理アドレスである。管理構造体１３１ａは予め領域１２１ａに対応付けられているため、キャッシュアドレスは管理構造体１３１ａが生成されたときに固定される。ディスクアドレスは、領域１２１ａに記憶されたページが存在するＨＤＤ１０３の位置を示す物理アドレスである。ディスクアドレスは、例えば、当該ページの先頭の物理アドレスである。領域１２１ａにページが上書きされると、管理構造体１３１ａのディスクアドレスが更新される。
【００７８】
図９は、ハッシュテーブルの例を示す図である。
ハッシュテーブル１３２は、ハッシュ値と連結リストへのリンクとの組を複数含む。ハッシュテーブル１３２に登録されるハッシュ値は、所定のハッシュ関数を用いて算出したストリームＩＤのハッシュ値である。ハッシュ関数としては、異なるストリームＩＤから同じハッシュ値が算出される衝突の可能性が十分に小さいものを使用する。
【００７９】
ストリームＩＤのハッシュ値から、連結リストを参照することができる。連結リストは、１または２以上のポインタを連結したものである。連結リストに含まれる各ポインタは、管理構造体群１３１に含まれる何れかの管理構造体を指している。ポインタとして、管理構造体が記憶された位置を示すＲＡＭ１０２の物理アドレスを用いてもよいし、管理構造体に予め付与された構造体ＩＤを用いてもよい。
【００８０】
ハッシュテーブル１３２は、ストリームＩＤに対して、当該ストリームＩＤを含む管理構造体を対応付けたものと言うことができる。ハッシュテーブル１３２を用いることで、あるストリームに関連する全ての管理構造体を検索することができる。
【００８１】
図１０は、シーケンスＩＤテーブルの例を示す図である。
シーケンスＩＤテーブル１３３は、ストリームＩＤとシーケンスＩＤの組を複数含む。シーケンスＩＤテーブル１３３に登録されるストリームＩＤは、連続性検出部１４６によって各ストリームに付与されるものである。シーケンスＩＤテーブル１３３に登録されるシーケンスＩＤは、ストリームＩＤが示すストリームについて現在使用されているシーケンスＩＤ（管理構造体に含まれるシーケンスＩＤ）のうちの最大値である。次に先読みされるページに付与すべきシーケンスＩＤは、シーケンスＩＤテーブル１３３に登録されたものより１つ大きい値である。付与されるシーケンスＩＤの最小値は「１」であり、シーケンスＩＤテーブル１３３のシーケンスＩＤの初期値は「０」である。
【００８２】
図１１は、ＬＲＵ管理リストと優先置換ページリストの例を示す図である。
ＬＲＵ管理リスト１３４は、それぞれが管理構造体を指す複数のポインタを連結した連結リストである。前述のように、ポインタとして、管理構造体が記憶された位置を示す物理アドレスを用いてもよいし、管理構造体に予め付与された構造体ＩＤを用いてもよい。ＬＲＵ管理リストの先頭のポインタは、ＭＲＵページに対応する管理構造体を指す。ＬＲＵ管理リストの末尾のポインタは、ＬＲＵページに対応する管理構造体を指す。
【００８３】
あるページについてページヒットが発生すると、当該ページに対応する管理構造体を指すポインタがＬＲＵ管理リスト１３４の先頭に移動する。あるページについてページアウトが発生すると、同じ領域に他のページが読み込まれることになるため、当該ページに対応する管理構造体を指すポインタがＬＲＵ管理リスト１３４の先頭に移動する。ＬＲＵアルゴリズムに基づいて削除するページを選択する場合、ＬＲＵ管理リスト１３４の末尾にあるポインタが指す管理構造体に対応するページが選択される。
【００８４】
優先置換ページリスト１３５は、それぞれが管理構造体を指す１または２以上のポインタを連結した連結リストである。前述のように、ポインタとして、管理構造体が記憶された位置を示す物理アドレスを用いてもよいし、管理構造体に予め付与された構造体ＩＤを用いてもよい。ポインタが指す管理構造体に対応するページは、ストリーム通過判定部１４５によってストリームが通過したと判定されたページである。
【００８５】
ストリームが通過したページが検出されると、例えば、検出されたページに対応する管理構造体を指すポインタが優先置換ページリストの末尾に追加される。ストリームが通過したページをＲＡＭ１０２から削除するとき、優先置換ページリスト１３５から、削除するページに対応する管理構造体を示すポインタが削除される。優先置換ページリスト１３５に複数のポインタが含まれている場合、それら複数のポインタの選択順序は任意でよい。例えば、先頭のポインタから先に選択していく。
【００８６】
図１２は、ストリームテーブルの例を示す図である。
ストリームテーブル群１３６にストリームテーブル１３６ａが含まれる。ストリームテーブル１３６ａは、使用フラグ、ストリームＩＤ、アクセスアドレス（Ａlast）、プリフェッチアドレス（Ａpre）および連続カウンタ（Ｃ）を含む。
【００８７】
使用フラグは、ストリームテーブル１３６ａが使用されているか否かを示す。ストリームＩＤは、ストリームテーブル１３６ａによって管理されるストリームに付与された識別番号である。ストリームテーブル１３６ａによって管理されていた前のストリームが消滅し、その後に検出された新たなストリームを管理するためにストリームテーブル１３６ａが再利用されることがある。その場合、ストリームテーブル１３６ａに登録されたストリームＩＤが新たなストリームＩＤに書き換えられる。
【００８８】
アクセスアドレスは、ストリームテーブル１３６ａによって管理されるストリームが最後に指定したアドレス範囲の末尾を示す。すなわち、アクセスアドレスは、当該ストリームによって最後に使用されたデータの末尾を示すＨＤＤ１０３の物理アドレスである。プリフェッチアドレスは、ストリームテーブル１３６ａによって管理されるストリームについて最後に先読みしたページの末尾を示すＨＤＤ１０３の物理アドレスである。
【００８９】
連続カウンタは、所定条件を満たすアクセス要求が検出された回数を示す。連続カウンタは、ストリームテーブル１３６ａによって管理されるストリームに属する「連続性のあるアクセス」の数を示していると言うこともできる。所定条件は、アクセス要求によって指定されたアドレス範囲の先頭が、ＡlastとＡlast＋Ｒの間に存在することである。
【００９０】
次に、情報処理装置１００の処理手順について説明する。
図１３は、プリフェッチ制御の手順例を示すフローチャートである。
（Ｓ１０）プリフェッチ制御部１４２は、連続性検出部１４６からプリフェッチ要求を取得する。プリフェッチ要求は、先読みする１または２以上のページの先頭と末尾を示すディスクアドレスと、ストリームＩＤとを含む。
【００９１】
（Ｓ１１）プリフェッチ制御部１４２は、プリフェッチ要求に含まれるディスクアドレスに基づいて、先読みするページのページ数を算出する。プリフェッチ制御部１４２は、ページ数を含む決定要求を置換ページ決定部１４３に送信する。
【００９２】
（Ｓ１２）プリフェッチ制御部１４２は、ステップＳ１１で算出したページ数に相当する数の管理構造体のポインタを、置換ページ決定部１４３から受信する。プリフェッチ制御部１４２は、受信したポインタが指す管理構造体からキャッシュアドレスを取得する。プリフェッチ制御部１４２は、プリフェッチ要求に含まれるディスクアドレスが示すＨＤＤ１０３のページを、キャッシュアドレスが示すＲＡＭ１０２の領域にコピーする。２以上のページを先読みする場合、使用する管理構造体の順序は任意でよい。
【００９３】
（Ｓ１３）プリフェッチ制御部１４２は、シーケンスＩＤテーブル１３３から、プリフェッチ要求に含まれるストリームＩＤに対応するシーケンスＩＤの最大値（ストリームに対応するシーケンスＩＤの最大値）を検索する。
【００９４】
（Ｓ１４）プリフェッチ制御部１４２は、ステップＳ１３において該当するシーケンスＩＤが検索されたか、すなわち、プリフェッチ要求に含まれるストリームＩＤがシーケンスＩＤテーブル１３３に登録されていたか判断する。該当するシーケンスＩＤが検索された場合、ステップＳ１６に処理が進む。該当するシーケンスＩＤが検索されなかった（ストリームＩＤが登録されていなかった）場合、ステップＳ１５に処理が進む。
【００９５】
（Ｓ１５）プリフェッチ制御部１４２は、シーケンスＩＤテーブル１３３に、プリフェッチ要求に含まれるストリームＩＤを登録する。また、プリフェッチ制御部１４２は、当該ストリームＩＤに対応するシーケンスＩＤとして「０」を登録（初期化）する。
【００９６】
（Ｓ１６）プリフェッチ制御部１４２は、ステップＳ１２で受信したポインタが指す管理構造体のストリームＩＤ、シーケンスＩＤ、ディスクアドレスおよびストリームフラグを更新する。管理構造体に登録するストリームＩＤは、プリフェッチ要求に含まれるストリームＩＤである。管理構造体に登録するシーケンスＩＤは、ステップＳ１３で検索されたシーケンスＩＤの最大値または「０」に、管理構造体１つにつき「１」ずつ加算した値である。２以上のページを先読みした場合、２以上の管理構造体には互いに異なるシーケンスＩＤが登録される。シーケンスＩＤを付与する順序は、先読みしたページのディスクアドレスが小さい順（通常はページを先読みした順）とする。管理構造体に登録するディスクアドレスは、先読みしたページの先頭を示すＨＤＤ１０３の物理アドレスである。管理構造体に登録するストリームフラグは「ＯＮ」（または「１」）である。
【００９７】
（Ｓ１７）プリフェッチ制御部１４２は、所定のハッシュ関数を用いて、プリフェッチ要求に含まれるストリームＩＤのハッシュ値を算出する。プリフェッチ制御部１４２は、ハッシュテーブル１３２から、算出したハッシュ値に対応する連結リストを検索し、ステップＳ１２で受信したポインタを連結リストの末尾に追加する。
【００９８】
（Ｓ１８）プリフェッチ制御部１４２は、シーケンスＩＤテーブル１３３から、プリフェッチ要求に含まれるストリームＩＤに対応するシーケンスＩＤの最大値を検索する。プリフェッチ制御部１４２は、検索した最大値を更新する。具体的には、プリフェッチ制御部１４２は、検索した最大値に、ステップＳ１１で算出したページ数を加算する。
【００９９】
図１４は、置換ページ決定の手順例を示すフローチャートである。
（Ｓ２０）置換ページ決定部１４３は、プリフェッチ制御部１４２またはキャッシュヒット判定部１４４から、ページ数を含む決定要求を受信する。
【０１００】
（Ｓ２１）置換ページ決定部１４３は、優先置換ページリスト１３５が空であるか（ポインタが１つも登録されていないか）判断する。優先置換ページリスト１３５が空である場合、ステップＳ２３に処理が進む。優先置換ページリスト１３５が空でない（１つ以上のポインタが登録されている）場合、ステップＳ２２に処理が進む。
【０１０１】
（Ｓ２２）置換ページ決定部１４３は、優先置換ページリスト１３５から１つポインタ（例えば、先頭のポインタ）を抽出する。抽出したポインタは優先置換ページリスト１３５から削除される。置換ページ決定部１４３は、抽出したポインタを決定要求の送信元に返信する。また、置換ページ決定部１４３は、抽出したポインタと同じ管理構造体を指すポインタをＬＲＵ管理リスト１３４から検索し、検索したポインタをＬＲＵ管理リスト１３４から削除する。そして、ステップＳ２８に処理が進む。
【０１０２】
（Ｓ２３）置換ページ決定部１４３は、ＬＲＵアルゴリズムに従ってＬＲＵ管理リスト１３４を更新し、ＲＡＭ１０２から追い出すページに対応する管理構造体のポインタを１つ選択する。具体的には、置換ページ決定部１４３は、ＬＲＵ管理リスト１３４の末尾にあるポインタを先頭に移動し、先頭に移動したポインタを選択する。ただし、置換ページ決定部１４３が他のページ置換アルゴリズムを使用することも可能である。置換ページ決定部１４３は、選択したポインタを決定要求の送信元に返信する。
【０１０３】
（Ｓ２４）置換ページ決定部１４３は、ステップＳ２３で選択したポインタが指す管理構造体からストリームフラグを取得し、ストリームフラグが「ＯＮ」（または「１」）であるか判断する。ストリームフラグが「ＯＮ」である場合はステップＳ２５に処理が進み、「ＯＦＦ」（または「０」）である場合はステップＳ２８に処理が進む。
【０１０４】
（Ｓ２５）置換ページ決定部１４３は、ステップＳ２３で選択したポインタが指す管理構造体からストリームＩＤを取得し、ストリームＩＤのハッシュ値を算出する。置換ページ決定部１４３は、ハッシュテーブル１３２から、算出したハッシュ値に対応する連結リストを検索し、ステップＳ２３で選択したポインタと同じ管理構造体を指すポインタを検索する。置換ページ決定部１４３は、検索したポインタを削除する。
【０１０５】
（Ｓ２６）置換ページ決定部１４３は、ステップＳ２５で検索された連結リストに他のポインタが登録されているか、すなわち、ステップＳ２５で削除したポインタと同じストリームＩＤに対応付けられた他のポインタが存在するか判断する。他のポインタが存在する場合はステップＳ２８に処理が進み、存在しない場合はステップＳ２７に処理が進む。
【０１０６】
（Ｓ２７）置換ページ決定部１４３は、シーケンスＩＤテーブル１３３から、ステップＳ２５で取得したストリームＩＤを含むエントリを削除する。
（Ｓ２８）置換ページ決定部１４３は、決定要求で指定されたページ数に相当する数のポインタを返信したか判断する。指定された数のポインタを返信済みである場合は置換ページ決定が終了し、それ以外の場合はステップＳ２１に処理が進む。
【０１０７】
図１５は、キャッシュヒット判定の手順例を示すフローチャートである。
（Ｓ３０）キャッシュヒット判定部１４４は、アドレス情報を含むアクセス要求を、アクセス要求受付部１４１から受信する。アドレス情報は、例えば、読み出すデータの先頭を示すＨＤＤ１０３の物理アドレスとデータ長とを含む。
【０１０８】
（Ｓ３１）キャッシュヒット判定部１４４は、アクセス要求に含まれるアドレス情報に基づいて、１または２以上の対象ページを特定する。キャッシュヒット判定部１４４は、各管理構造体に含まれるディスクアドレスに基づいて、特定した対象ページがＲＡＭ１０２にキャッシュされているか判断する。対象ページがキャッシュされている場合（キャッシュヒットの場合）、ステップＳ３２に処理が進む。対象ページがキャッシュされていない場合（キャッシュミスヒットの場合）、ステップＳ３５に処理が進む。
【０１０９】
（Ｓ３２）キャッシュヒット判定部１４４は、ＬＲＵ管理リスト１３４から、対象ページのディスクアドレスを含む管理構造体を指すポインタを検索し、検索されたポインタをＬＲＵ管理リストの先頭に移動する。ただし、他のページ置換アルゴリズムが使用されている場合には、当該アルゴリズムに応じた処理が行われる。
【０１１０】
（Ｓ３３）キャッシュヒット判定部１４４は、対象ページのディスクアドレスを含む管理構造体から、ストリームフラグを取得する。キャッシュヒット判定部１４４は、ストリームフラグが「ＯＮ」であるか判断する。ストリームフラグが「ＯＮ」である場合はステップＳ３４に処理が進み、「ＯＦＦ」である場合はステップＳ３７に処理が進む。
【０１１１】
（Ｓ３４）キャッシュヒット判定部１４４は、対象ページのディスクアドレスを含む管理構造体から、ストリームＩＤとシーケンスＩＤを取得する。キャッシュヒット判定部１４４は、ストリームＩＤとシーケンスＩＤをストリーム通過判定部１４５に通知する。
【０１１２】
（Ｓ３５）キャッシュヒット判定部１４４は、ステップＳ３１で特定した対象ページのページ数を算出し、ページ数を含む決定要求を置換ページ決定部１４３に送信する。
（Ｓ３６）キャッシュヒット判定部１４４は、ステップＳ３５で算出したページ数に相当する数の管理構造体のポインタを、置換ページ決定部１４３から受信する。キャッシュヒット判定部１４４は、受信したポインタが指す管理構造体からキャッシュアドレスを取得する。キャッシュヒット判定部１４４は、ＨＤＤ１０３の対象ページを、キャッシュアドレスが示すＲＡＭ１０２の領域にコピーする。また、キャッシュヒット判定部１４４は、受信したポインタが指す管理構造体のストリームＩＤ、シーケンスＩＤ、ディスクアドレスおよびストリームフラグを更新する。管理構造体に登録するストリームＩＤおよびシーケンスＩＤは、「ＮＵＬＬ」または「０」である。管理構造体に登録するディスクアドレスは、対象ページの先頭を示すＨＤＤ１０３の物理アドレスである。管理構造体に登録するストリームフラグは「ＯＦＦ」（または「０」）である。
【０１１３】
（Ｓ３７）キャッシュヒット判定部１４４は、ＲＡＭ１０２にキャッシュされたページの中から、アクセス要求に含まれるアドレス情報が示すデータを抽出し、抽出したデータをアクセス要求の送信元に返信する。ただし、アクセス要求が書き込み要求である場合、書き込み要求に含まれるデータを用いて、ＲＡＭ１０２にキャッシュされたページを更新し、更新の成否をアクセス要求の送信元に通知する。なお、キャッシュされたページが更新された場合、更新された直後または当該ページがＲＡＭ１０２から追い出されるときに、当該ページがＨＤＤ１０３に書き戻される。
【０１１４】
図１６は、ストリーム通過判定の手順例を示すフローチャートである。
（Ｓ４０）ストリーム通過判定部１４５は、キャッシュヒット判定部１４４から、ストリームＩＤとシーケンスＩＤの通知を取得する。
【０１１５】
（Ｓ４１）ストリーム通過判定部１４５は、通知されたストリームＩＤのハッシュ値を算出する。ストリーム通過判定部１４５は、ハッシュテーブル１３２から、算出したハッシュ値に対応する連結リストを検索する。ストリーム通過判定部１４５は、連結リストに含まれるポインタが指す管理構造体それぞれからシーケンスＩＤを取得し、通知されたシーケンスＩＤより小さいシーケンスＩＤをもつ管理構造体を検索する。
【０１１６】
（Ｓ４２）ストリーム通過判定部１４５は、ステップＳ４１において該当する管理構造体が検索されたか判断する。該当する管理構造体が検索された場合はステップＳ４３に処理が進み、検索されなかった場合はストリーム通過判定が終了する。
【０１１７】
（Ｓ４３）ストリーム通過判定部１４５は、ステップＳ４１で検索された管理構造体を指すポインタを、優先置換ページリスト１３５に登録する。
（Ｓ４４）ストリーム通過判定部１４５は、ステップＳ４１で検索された連結リストから、ステップＳ４１で検索された管理構造体を指すポインタを削除する。
【０１１８】
図１７は、連続性検出の手順例を示すフローチャートである。
（Ｓ５０）連続性検出部１４６は、アクセス要求受付部１４１が受け付けるアクセス要求を監視し、アドレス範囲が［Ａ，Ａ＋Ｌ］であるアクセス要求（先頭の物理アドレスがＡでありデータ長がＬであるアクセス要求）を検出する。
【０１１９】
（Ｓ５１）連続性検出部１４６は、ストリームテーブル群１３６の中から、使用フラグが「ＯＮ」（または「１」）であるストリームテーブルを検索する。連続性検出部１４６は、該当するストリームテーブルが存在するか判断する。該当するストリームテーブルがある場合はステップＳ５３に処理が進み、ない場合はステップＳ５２に処理が進む。
【０１２０】
（Ｓ５２）連続性検出部１４６は、ストリームテーブル群１３６の中から、任意のストリームテーブルを１つ選択する。そして、ステップＳ５６に処理が進む。
（Ｓ５３）連続性検出部１４６は、使用フラグが「ＯＮ」であるストリームテーブルの中から、アクセスアドレス（Ａlast）がＡに最も近いストリームテーブルを検索する。
【０１２１】
（Ｓ５４）連続性検出部１４６は、ステップＳ５３で検索されたストリームテーブルのアクセスアドレス（Ａlast）が、Ａlast＜Ａ＜Ａlast＋Ｒの関係を満たすか判断する。上記関係における「Ｒ」は、図４のような連続性のあるアクセスと判断されるアクセスの間隔の閾値であり、予め決めておく。上記関係を満たす場合はステップＳ５８に処理が進み、満たさない場合はステップＳ５５に処理が進む。
【０１２２】
（Ｓ５５）連続性検出部１４６は、ストリームテーブル群１３６の中から、使用フラグが「ＯＦＦ」（または「０」）であるストリームテーブルを１つ選択する。ただし、ストリームテーブル群１３６の中に使用フラグが「ＯＦＦ」のストリームテーブルが存在しない場合、ステップＳ５３で検索されたストリームテーブルを選択する。
【０１２３】
（Ｓ５６）連続性検出部１４６は、ステップＳ５２またはステップＳ５５で選択したストリームテーブルのアクセスアドレス（Ａlast）、プリフェッチアドレス（Ａpre）、連続カウンタ（Ｃ）およびストリームＩＤを更新する。アクセスアドレスとプリフェッチアドレスは、アクセス要求によって指定されたアドレス範囲の末尾（Ａ＋Ｌ）とする。連続カウンタは、「０」に初期化する。ストリームＩＤは、新たな識別番号とする。
【０１２４】
（Ｓ５７）連続性検出部１４６は、選択したストリームテーブルの使用フラグを「ＯＮ」に更新する。そして、連続性検出が終了する。
（Ｓ５８）連続性検出部１４６は、ステップＳ５３で検索されたストリームテーブルを選択する。連続性検出部１４６は、選択したストリームテーブルのアクセスアドレス（Ａlast）と連続カウンタ（Ｃ）を更新する。アクセスアドレスは、アクセス要求によって指定されたアドレス範囲の末尾（Ａ＋Ｌ）とする。連続カウンタは、現在の連続カウンタをインクリメントしたもの（Ｃ＋１）とする。
【０１２５】
（Ｓ５９）連続性検出部１４６は、ステップＳ５８で更新した連続カウンタが閾値Ｎ以上であるか判断する。閾値Ｎは、ステップＳ５４の関係を満たすアクセスの集合がストリームであると判断されるためのアクセス回数の閾値である。閾値Ｎは、２以上の整数であり、予め決めておく。Ｃ≧Ｎの関係を満たす場合はステップＳ６１に処理が進み、この関係を満たさない場合はステップＳ６０に処理が進む。
【０１２６】
（Ｓ６０）連続性検出部１４６は、ステップＳ５８で選択したストリームテーブルのプリフェッチアドレス（Ａpre）を、アクセス要求によって指定されたアドレス範囲の末尾（Ａ＋Ｌ）に更新する。そして、連続性検出が終了する。
【０１２７】
（Ｓ６１）連続性検出部１４６は、プリフェッチ制御部１４２にプリフェッチ要求を送信する。プリフェッチ要求には、ステップＳ５８で選択したストリームテーブルのストリームＩＤが含まれる。また、プリフェッチ要求は、先読みするページ群の先頭のアドレスとしてＡpreを含み、先読みするページ群の末尾のアドレスとしてＡ＋Ｌ＋Ｐを含む。「Ｐ」は、１回のプリフェッチで読み込むデータの量であり、予め決めておく。
【０１２８】
（Ｓ６２）連続性検出部１４６は、ステップＳ５８で選択したストリームテーブルのプリフェッチアドレス（Ａpre）を、プリフェッチされたページの末尾を示すＨＤＤ１０３の物理アドレス（Ａ＋Ｌ＋Ｐ）に更新する。
【０１２９】
第２の実施の形態の情報処理装置１００によれば、先読みされたページに対して、ストリームを識別するストリームＩＤとストリーム内で一意なシーケンスＩＤとが対応付けられる。そして、ストリームＩＤとシーケンスＩＤに基づいて、ＲＡＭ１０２にキャッシュされたページの中から、ストリームが通過したページが検索される。ストリームが通過したページは、その後に使用される可能性が低いため、ＬＲＵアルゴリズムによって選択されるページよりも優先的にＲＡＭ１０２から削除される。これにより、ストリームが通過したページよりも使用される可能性の高い他のページをＲＡＭ１０２に残しつつ、ＲＡＭ１０２に空き領域を確保することができる。よって、ＬＲＵアルゴリズムのみを使用する場合と比べて、キャッシュ用領域の利用効率を向上させることができる。
【０１３０】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現できる。第２の実施の形態の情報処理は、情報処理装置１００にプログラムを実行させることで実現できる。
【０１３１】
プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体１１３）に記録しておくことができる。記録媒体として、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体から他の記録媒体（例えば、ＨＤＤ１０３）にプログラムをコピーして実行してもよい。
【符号の説明】
【０１３２】
１０  情報処理装置
１１  記憶装置
１２  メモリ
１３  制御部
１４ａ，１４ｂ，１４ｃ，１４ｄ  データブロック
１５  ストリーム
１６  ストリーム情報
１７ａ，１７ｂ  シーケンス情報
【図１】
2017072981.tif 000003
【図２】
2017072981.tif 000004
【図３】
2017072981.tif 000005
【図４】
2017072981.tif 000006
【図５】
2017072981.tif 000007
【図６】
2017072981.tif 000008
【図７】
2017072981.tif 000009
【図８】
2017072981.tif 000010
【図９】
2017072981.tif 000011
【図１０】
2017072981.tif 000012
【図１１】
2017072981.tif 000013
【図１２】
2017072981.tif 000014
【図１３】
2017072981.tif 000015
【図１４】
2017072981.tif 000016
【図１５】
2017072981.tif 000017
【図１６】
2017072981.tif 000018
【図１７】
2017072981.tif 000019