(57)【要約】【課題】各処理に対応したキャッシュのパーティションに割り当てるべき容量を測定することなしに適正化し、記憶媒体に対するアクセス性能を高めること。【解決手段】キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定部と、キャッシュミスが発生したページが、キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、容量を削減可能なパーティションの容量を削減してキャッシュミスが発生したパーティションの容量に追加する容量制御部と、を備える。【選択図】  図１
2019168733.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定手段と、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御手段と、
を備える記憶制御装置。
【請求項２】
前記削減候補設定手段は、
前記所定時間を周期として、その間にアクセスされてないページを不要なページとして検出する不要ページ検出手段を有し、
前記不要なページを含むパーティションを、前記容量を削減可能なパーティションと設定する、請求項１に記載の記憶制御装置。
【請求項３】
前記不要ページ検出手段は、クロックアルゴリズムを用いて、前記所定時間にアクセスされてないページを検出する、請求項２に記載の記憶制御装置。
【請求項４】
前記不要ページ検出手段は、前記不要なページを検出する前記周期を調整する検出周期調整手段を含む、請求項２または３に記載の記憶制御装置。
【請求項５】
前記キャッシュメモリへのアクセスにおいて発生したキャッシュヒットを、アクセスの対象であるパーティションに関連付けて検出するキャッシュヒット検出手段と、
前記キャッシュヒットの検出結果から、パーティションに対するアクセス頻度の高いページの検出に要する時間を測定する検出時間測定手段と、をさらに備え、
前記検出周期調整手段は、前記測定された時間を基づいて、前記不要ページの検出周期を調整する、請求項４に記載の記憶制御装置。
【請求項６】
前記容量制御手段は、前記容量を削減可能なパーティションが複数ある場合、下位の記憶媒体に追い出される可能性の最も高いページを含むパーティションを、容量削減をするパーティションとする、請求項１乃至５のいずれか１項に記載の記憶制御装置。
【請求項７】
前記容量制御手段は、容量削減をするパーティションにおいて、下位の記憶媒体に追い出される可能性の最も高いページを削減する、請求項１乃至６のいずれか１項に記載の記憶制御装置。
【請求項８】
キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定ステップと、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御ステップと、
を含む記憶制御方法。
【請求項９】
キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定ステップと、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御ステップと、
をコンピュータに実行させる記憶制御プログラム。
【請求項１０】
記憶媒体と、
複数の処理からのアクセス要求に基づいて、前記記憶媒体へのアクセスを指示するアクセス手段と、
キャッシュメモリを有し、前記アクセス手段の前記記憶媒体へのアクセスを制御する記憶制御手段と、
を備えた情報処理システムであって、
前記記憶制御手段は、
前記キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定手段と、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の前記記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御手段と、
を備える情報処理システム。
【請求項１１】
複数の処理の各処理に対して、キャッシュメモリ内の少なくとも１つのページを含むパーティションを割り当てる割当ステップと、
前記キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定ステップと、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御ステップと、
前記削減候補設定ステップをバックグラウンドで実行しつつ、前記容量制御ステップを繰り返し、前記各処理に対するキャッシュ容量の配分を管理する配分管理ステップと、
を含むキャッシュ容量配分方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム、キャッシュ容量配分方法、記憶制御装置およびその方法とプログラムに関する。
【背景技術】
【０００２】
上記技術分野において、特許文献１には、キャッシュヒット頻度に基づいて配分する容量を調整する技術が開示されている。また、特許文献２には、キャッシュの容量をパーティションに分割して独立したキャッシュとして扱う際に、各パーティションの容量を計算する技術が開示されている。また、非特許文献３には、新規に格納されるデータと、一度ヒットしたデータを異なるＬＲＵキャッシュで管理し、各キャッシュ部に以前格納されていたデータがアクセスされた場合に、データがキャッシュ内でヒットするように他方のキャッシュから一定の容量を移動する技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】国際公開ＷＯ２０１４／１４２３３７号公報
【特許文献２】特開２００７−０４１９０４号公報
【非特許文献】
【０００４】
【非特許文献１】H. S. Stone, J. Turek and J. L. Wolf, "Optimal partitioning of cache memory," in IEEE Transactions on Computers, vol. 41, no. 9, pp. 1054-1068, Sep 1992.
【非特許文献２】G. E. Suh, L. Rudolph, and S. Devadas. 2004. Dynamic Partitioning of Shared Cache Memory. J. Supercomput. 28, 1 (April 2004), 7-26.
【非特許文献３】Nimrod Megiddo and Dharmendra S. Modha. 2003. ARC: A Self-Tuning, Low Overhead Replacement Cache. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST '03). USENIX Association, Berkeley, CA, USA, 115-130.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記文献に記載の技術では、キャッシュの各パーティションに割り当てる容量の適正化はキャッシュヒット率などの測定時間のある分配時に行なわれ、動作中に容量変更を行なう場合には測定時間がなく容量の適正化に対応できないため、アクセス性能を高めるには限界があった。
【０００６】
本発明の目的は、上述の課題を解決する技術を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するため、本発明に係る記憶制御装置は、
キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定手段と、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御手段と、
を備える。
【０００８】
上記目的を達成するため、本発明に係る記憶制御方法は、
キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定ステップと、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御ステップと、
を含む。
【０００９】
上記目的を達成するため、本発明に係る記憶制御プログラムは、
キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定ステップと、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御ステップと、
をコンピュータに実行させる。
【００１０】
上記目的を達成するため、本発明に係るシステムは、
記憶媒体と、
複数の処理からのアクセス要求に基づいて、前記記憶媒体へのアクセスを指示するアクセス手段と、
キャッシュメモリを有し、前記アクセス手段の前記記憶媒体へのアクセスを制御する記憶制御手段と、
を備えた情報処理システムであって、
前記記憶制御手段は、
前記キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定手段と、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の前記記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御手段と、
を備える。
【００１１】
上記目的を達成するため、本発明に係るキャッシュ容量配分方法は、
複数の処理の各処理に対して、キャッシュメモリ内の少なくとも１つのページを含むパーティションを割り当てる割当ステップと、
前記キャッシュメモリにおいて、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティションを、容量を削減可能なパーティションと設定する削減候補設定ステップと、
キャッシュミスが発生したページが、前記キャッシュメモリから下位の記憶媒体に追い出されたページの履歴に含まれている場合、前記容量を削減可能なパーティションの容量を削減して前記キャッシュミスが発生したパーティションの容量に追加する容量制御ステップと、
前記削減候補設定ステップをバックグラウンドで実行しつつ、前記容量制御ステップを繰り返し、前記各処理に対するキャッシュ容量の配分を管理する配分管理ステップと、
を含む。
【発明の効果】
【００１２】
本発明によれば、各処理に対応したキャッシュのパーティションに割り当てるべき容量を測定することなしに処理中に適正化し、記憶媒体に対するアクセス性能を高めることができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１実施形態に係る記憶制御装置の構成を示すブロック図である。
【図２】本発明の第２実施形態に係る記憶制御装置を含む情報処理システムの構成を示すブロック図である。
【図３】本発明の第２実施形態に係る記憶制御装置の機能構成を示すブロック図である。
【図４】本発明の第２実施形態に係るページ状態管理テーブルの構成を示す図である。
【図５】本発明の第２実施形態に係るパーティション容量設定テーブルの構成を示す図である。
【図６】本発明の第２実施形態に係る置換ページ履歴テーブルの構成を示す図である。
【図７】本発明の第２実施形態における記憶制御装置のハードウェア構成を示したブロック図である。
【図８】本発明の第２実施形態における記憶制御装置の処理手順を示したフローチャートである。
【図９】本発明の第２実施形態におけるアクセス処理の手順を示したフローチャートである。
【図１０】本発明の第２実施形態におけるキャッシュヒット時のアクセス処理の手順を示したフローチャートである。
【図１１Ａ】本発明の第２実施形態におけるキャッシュミス時のアクセス処理の手順を示したフローチャートである。
【図１１Ｂ】本発明の第２実施形態におけるキャッシュミス時のアクセス処理の手順を示したフローチャートである。
【図１２】本発明の第２実施形態におけるパーティションの設定容量調整処理の手順を示したフローチャートである。
【図１３】本発明の第２実施形態におけるパーティションの解放可能容量更新処理の手順を示したフローチャートである。
【図１４】本発明の第３実施形態に係る記憶制御装置の機能構成を示すブロック図である。
【図１５】本発明の第４実施形態に係る記憶制御装置の機能構成を示すブロック図である。
【図１６】本発明の第４実施形態における処理速度調整処理の手順を示したフローチャートである。
【図１７】本発明の第５実施形態に係る記憶制御装置を含む情報処理システムの構成を示すブロック図である。
【発明を実施するための形態】
【００１４】
以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素は単なる例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。なお、「ページ」とは、システムにおけるキャッシュへのアクセス単位であり、記憶媒体のアクセス単位は多くの場合にページより細かな単位となる。本明細書では、説明を分かりやすくするためにページ単位で全てのアクセスを行うよう記載しているが、実際はページよりも小さな単位でのアクセスが発生している。
【００１５】
［第１実施形態］
本発明の第１実施形態としての記憶制御装置１００について、図１を用いて説明する。記憶制御装置１００は、キャッシュメモリを含む記憶媒体へのアクセスを制御する装置である。
【００１６】
図１に示すように、記憶制御装置１００は、削減候補設定部１０１と、容量制御部１０２と、を含む。削減候補設定部１０１は、キャッシュメモリ１３０において、所定時間を超えてアクセスされていないページ、または、アクセス頻度が所定値を下回るページを含むパーティション１１１を、容量を削減可能なパーティション１２１と設定する。容量制御部１０２は、キャッシュミスが発生したページ１２２が、キャッシュメモリ１３０から下位の記憶媒体１４０に追い出されたページの履歴１２３に含まれている場合、容量を削減可能なパーティション１２１の容量を削減してキャッシュミスが発生したパーティション１２４の容量に追加する。
【００１７】
本実施形態によれば、アクセスの少ないページを含むパーティションを、容量を削減可能なパーティション設定して、追い出されたページでキャッシュミスが発生したパーティションに容量を移動する。これにより、各処理に対応したキャッシュのパーティションに割り当てるべき容量を測定することなしに処理中に適正化し、記憶媒体に対するアクセス性能を高めることができる。
【００１８】
［第２実施形態］
次に、本発明の第２実施形態に係るキャッシュメモリを制御する記憶制御装置について説明する。本実施形態の記憶制御装置は、アクセスの少ないページを含むパーティションを、容量を削減可能なパーティション設定して、追い出されたページでキャッシュミスが発生したパーティションへの容量の移動を繰り返す。
【００１９】
ここで、削減可能なパーティションの設定については、所定時間を周期として、その間にアクセスされていないページを不要なページとして検出する不要ページ検出に基づいて、不要なページを含むパーティションを、容量を削減可能なパーティションと設定する。この不要ページ検出は、例えば、クロックアルゴリズムを用いて行なわれる。また、容量の移動において、容量を削減可能なパーティションが複数ある場合、下位の記憶媒体に追い出される可能性の最も高いページを含むパーティションを容量削減するパーティションとする。そして、容量削減をするパーティションにおいて、容量の移動先のパーティションで新たにデータの格納が必要になった場合、下位の記憶媒体に追い出される可能性の最も高いページを削減する。また、本実施形態のキャッシュ容量配分方法は、複数の処理の各処理に対して、キャッシュメモリ内の少なくとも１つのページを含むパーティションを割り当てる割当処理と、削減候補設定処理をバックグラウンドで実行しつつ、容量制御処理を繰り返し、各処理に配分するキャッシュ容量の配分を管理する配分管理処理と、を含む。
【００２０】
《前提技術の説明》
近年、計算機の処理能力向上や記憶素子、記憶媒体の高密度化と共に、計算機において処理されるデータの容量が増加している。それに伴い、計算機の処理においてより大きな容量を持つ、低速な記憶媒体で構成された下位の記憶階層に対するアクセス量が増加している。例えば、処理で用いるデータ全体が計算機のメモリに収まらない場合、メモリより下位のＨＤＤ (Hard Disk Drive)やNANDフラッシュを用いたＳＳＤ (Solid State Drive)などの記憶媒体にデータを格納してアクセスを行う。また、多くの計算機においてプロセッサは自身に大きな記憶領域を持たず、大容量のデータを処理するためにＤＲＡＭ (Dynamic Random Access Memory)等で構成された下位のメモリを使用する。通常、計算機において下位の記憶階層は低速であるため、上位の記憶媒体でデータをキャッシュすることで処理性能の向上を図る。キャッシュの効果を十分に得るためには、増加したアクセス量に対応した十分な容量のキャッシュが必要となる。
【００２１】
一方で、近年の計算機で採用されるプロセッサでは、処理能力の向上を目的として同時に複数の処理を並列に実行するためにコア、スレッドと呼ばれる命令実行単位の数が増加している。これらのプロセッサの処理能力を活用して性能向上を図るには、各計算機上で並列に実行する処理数の増加が求められる。計算機上で実行される複数の処理は、通常異なるデータに対して異なる手順で処理を実行する。そのため、並列実行される各処理が利用可能なキャッシュ容量は処理数に反比例して減少する。
【００２２】
つまり、各処理に対して余分なキャッシュ容量を割り当てることなく、並列に実行される処理全体のキャッシュの効果を最大化するように容量を配分する必要がある。並列実行される処理数が増加すると、十分に性能が得られるように各処理で使用するデータ量に対して余裕を持った容量を割り当てることは困難である。また、並列実行数の増加によって、各処理がキャッシュしたデータ間で競合の発生する可能性が増加する。例えば、処理の一つが大量のデータを参照する場合、キャッシュの容量を多く消費することで並列実行される他の処理が頻繁に参照するデータ(ワーキングセット)が追い出される。複数の処理間でワーキングセットに含まれるデータの追い出しが互いに行われることで、各処理において下位の記憶階層に対するアクセスが増加して大幅な性能低下につながる。
【００２３】
この問題に対して、例えば、非特許文献１に示された技術では、処理ごとにキャッシュをパーティションと呼ばれる領域に分割することで処理間の競合発生を防止している。各パーティションはそれぞれ割り当てられた容量の独立したキャッシュとして動作する。そのためパーティションを使用することで、キャッシュしたデータが他の処理のデータを追い出す、処理間の競合を回避可能である。また、処理ごとに最適なパーティション容量を設定することで、キャッシュ容量に対するヒット数を向上させている。キャッシュに含まれる、各処理の最適なパーティション容量は、計算機やストレージシステムのメモリ容量だけではなく、並列に実行される処理の組み合わせに依存する。また、ワーキングセットは各処理の実行が進むと共に変化する。
【００２４】
そこで、例えば、非特許文献２に示された技術では、プロセッサのキャッシュにおいてアクセスの状況から動的に各パーティションの容量配分を最適化している。パーティション容量が変化した場合のヒット数をキャッシュの利用状況から予測し、パーティションに対してヒット数が最大化される容量配分を算出する。非特許文献２に示された技術では、容量変化時のヒット数を予測するために、各アクセスがヒットした際のパーティション内部における置換の優先順位を参照する。しかし、ＨＤＤやＳＳＤのような記憶媒体に対するキャッシュのように、容量が大きく多数のデータを含む環境において、各パーティションでヒットしたアクセスに対する置換の優先順位を調べることは困難である。例えば、キャッシュ置換のアルゴリズムとしてＬＲＵ(Least Recently Used)を用いる場合、優先順位を表すデータ構造が多くの場合にリストの形式であるため、キャッシュヒットしたデータの置換の優先順位を調べるために先頭からリストを辿る必要がある。そのため、キャッシュヒット時の応答時間が増加してアクセス性能の低下につながる。
【００２５】
また、非特許文献３では、キャッシュの部位毎の容量をアクセスに応じて動的に調整するキャッシュ置換アルゴリズムが示されている。このアルゴリズムでは、新規に格納されるデータと、一度ヒットしたデータを異なるＬＲＵキャッシュで管理しており、各キャッシュ部に以前格納されていたデータがアクセスされた場合に、データがキャッシュ内でヒットするように他方のキャッシュから一定の容量を移動する。そのため、非特許文献２に示された技術のような容量変化時のヒット数の予測は不要である。しかし、３つ以上のキャッシュ間の容量調整には対応しておらず、それぞれ異なる処理に対して割り当てられたキャッシュまたはパーティション間の容量を最適化することは想定されていない。
【００２６】
長期間アクセスされていないページを検出する動作自体は、キャッシュやメモリ管理において置換対象のデータを決定する一般的な技術において用いられるが、通常は検出されたページを直接置換の対象とするために用いられる。
【００２７】
（課題）
並列に実行される複数処理において高い性能を実現するために、共有キャッシュにおいて処理間のキャッシュの競合を防ぐと同時に、各処理に対してキャッシュの効果を最大化するように容量を配分することが求められる。そのために、各処理のワーキングセットを基に最適なパーティションの容量を求める必要がある。各処理のワーキングセットを動的に測定するために、対応するパーティション毎のデータアクセスを監視し、繰り返しアクセスされるデータの総容量を調べる必要がある。
【００２８】
しかし、一般的に各処理のワーキングセットを調べて、その結果が判明するまでに時間を要する。ワーキングセットに含まれる各データはアクセス頻度が高いほど、測定開始から早期にアクセスが検出される可能性が高いと言える。逆にワーキングセット内の相対的にアクセス頻度の低いデータは、測定開始から当該データに対するアクセスが検出されるまでに時間を要する可能性が高く、結果的にワーキングセット全体について漏れなく測定するために多くの時間を要する。
【００２９】
つまり、各処理のキャッシュのパーティションに割り当てる容量が決定するまでに時間を要することが課題である。例えば、計算機上で新たな処理の実行を開始、もしくは終了する際に、各処理のパーティションに対する最適な容量配分が変化する。また、多くの場合に各処理のワーキングセットは時間と共に変化する。しかし、ワーキングセットの確定に多くの時間を要することから、これらの容量配分変化への対応が困難である。特に、各パーティションにおける余剰分の容量を算出するために、ワーキングセットから外れたデータの検出が必要である。そのため、例えば、新たに実行を開始した処理のように即座にパーティションの容量追加が必要な場合に対応できず、性能が大きく低下する。
【００３０】
すなわち、前提技術においては、キャッシュの動作中の各動作に割り当てられたパーティションの容量を変更する場合であっても、キャッシュミスの発生を検知して容量追加を要求する処理と、アクセスが少なく容量が削減可能なパーティションを見つける処理とが関連付けられている。そのため、容量変更の時間短縮が制限されて、データアクセスの性能が低下してしまう。
【００３１】
《本実施形態の説明》
本実施形態においては、並列に実行される複数の処理において、記憶媒体に対する各処理のキャッシュパーティションの容量をキャッシュヒット率が最大となるように、各パーティションの容量を動的に調整する方法を提供する。そのために、各パーティションを割り当てられた処理による、キャッシュを通した記憶媒体に対するアクセスの情報を基に、パーティションの容量削減の可否を判断しておく。そして、各パーティションの容量追加が必要になると、容量追加が必要と判断されたパーティションに対して、あらかじめ準備された容量削減が可能なパーティションから容量を移動する。
【００３２】
本実施形態では、パーティションの容量削減の可否を判断する基準として、キャッシュに格納されているもののワーキングセットから外れたデータを検出する。また、各処理に対応するキャッシュパーティションを通した記憶媒体に対するアクセスの情報から、パーティションの容量追加の判断基準として、繰り返しアクセスされているにも関わらずキャッシュの容量不足により追い出されているデータを検出する。
【００３３】
まず、本実施形態では、キャッシュに含まれる各ページに対するアクセスの有無を監視し、長期間アクセスされていないページを検出する。長期間アクセスされていないページは、アクセス頻度が低い可能性が高く、ワーキングセットに含まれないページである可能性が高いと考えられる。そのため、検出されたページの容量を、当該ページを含むパーティションから解放可能な容量とする。
【００３４】
次に、本実施形態ではキャッシュから追い出された直近のページの履歴を保存し、各パーティションでキャッシュミスが発生した際に保存された履歴と照合する。キャッシュミスしたページが履歴に含まれている場合、キャッシュミスしたページは繰り返しアクセスされているもののキャッシュから追い出されたことが原因でミスになったと考えられる。そのため、アクセスを行った処理がキャッシュミスしたページをキャッシュに格納するために必要なパーティションの容量追加の要求を行う。
【００３５】
そして、容量追加の要求が行われたパーティションに対して、要求した容量を追加で割り当てる。一方で、容量の解放が可能なパーティションから１つのパーティションを選択し、選択されたパーティションに割り当てられた容量から追加を要求された分の容量を減算する。
【００３６】
容量が増加、減少した各パーティションでは、それぞれ増加後、減少後の容量に基づいてページの置き換えを行う。キャッシュミスに伴い新たなデータを格納する際に、データの格納先となるパーティションに含まれるページ数が容量よりも少ない場合、含まれるページ数が容量よりも多い他パーティションのページを置き換えて、パーティションのページ数を増加させる。以上の処理を繰り返すことで、各パーティションの容量を動的にキャッシュヒット率が最大となるように調整する。
【００３７】
本実施形態は、ページ状態管理機能と、パーティション容量設定機能と、置換対象ページ選択機能と、置換ページ履歴管理機能と、不要ページ容量解放機能と、容量追加判定機能と、追加容量取得元選択機能と、を備える。
【００３８】
ページ状態管理機能は、キャッシュ内の各ページに関する情報を管理する。すなわち、各処理に対応するキャッシュパーティションに対する容量削減、および、容量追加の判断を行い、パーティション間で容量の移動を行うことでキャッシュヒット率を最大化するために、各ページに対する最終アクセス時間、もしくは一定時間のアクセス有無、アクセス数を管理する。各ページを管理するための情報は、各ページに格納されたデータの記憶媒体における格納先アドレス等の識別子、置換の優先順位などの一般的なキャッシュが持つ管理情報以外に、各ページに対する最終アクセス時間、または一定時間内のアクセス有無、アクセス数に関する少なくともいずれか１つの情報を持つ。
【００３９】
パーティション容量設定機能は、各パーティションの容量を動作中に設定可能であり、キャッシュ内に定義された各パーティションに対して割り当てられた容量、および、解放可能な容量の指定を管理する。
【００４０】
置換対象ページ選択機能は、データを格納するための置換対象となるページの決定、もしくは置換対象となるページの優先順位を制御する。すなわち、キャッシュ内に定義された、仮想的な独立したキャッシュとして動作する各パーティションに対して、パーティションに含まれる各ページの置換に関する優先順位とパーティション容量設定機能から取得したパーティション容量を基に、キャッシュミスにより新規データの格納先となるページを決定する。また、置換結果を基に新規データが格納されるパーティションの各ページの置換に関する優先順位を更新する。
【００４１】
置換ページ履歴管理機能は、過去にキャッシュに格納されており、他のデータによって置換されたページの履歴を管理する。すなわち、各パーティションにおいて過去一定期間に新規に格納されるデータによって置換されたページについて、置換されたページに格納されていたデータの、記憶媒体におけるアドレス等の格納先を指定する識別子の情報を管理する。
【００４２】
不要ページ容量解放機能は、各ページに対応するアクセスの情報から一定時間アクセスが行われていないか、もしくはアクセス頻度の低い不要ページを検出し、不要ページが属するパーティションに割り当てられた容量に対して、解放可能な容量を計算する。すなわち、ページ状態管理機能で管理される各ページの情報を巡回して、最終アクセス時間、または一定時間内のアクセス有無、アクセス数の情報から一定時間アクセスが行われていない、もしくはアクセス頻度の低い不要ページを検出する。そして、不要ページが含まれるパーティションに対して、パーティション容量設定機能で管理される解放可能な容量に、不要ページの容量を加算する。
【００４３】
容量追加判定機能は、キャッシュ内で置換されたページの履歴と各パーティションに対応する処理のキャッシュミスの情報から、パーティションに対する容量追加が必要か判定する。すなわち、キャッシュミスとなった記憶媒体に対するアクセスについて、アクセス先のアドレス等の識別子を、置換ページ履歴管理機能によって管理される識別子と比較する。アクセス先と一致する識別子が存在する場合は、キャッシュヒット率増加のためにパーティションの容量追加が必要と判定し、アクセス要求を行った処理に対応するパーティションを特定して、特定されたパーティションに対する容量追加要求を行う。
【００４４】
追加容量取得元選択機能は、履歴管理機能が維持する履歴情報を参照してパーティションに対する容量追加、および容量の取得元となる解放可能な容量を持つパーティションを選択する。すなわち、容量追加判定機能によって行われた容量追加要求に対して、要求を満たすための追加容量を提供するパーティションを選択する。パーティションの選択条件は、パーティション容量設定機能において、追加要求を行った容量以上の解放可能な容量を持つパーティションである。選択条件を満たすパーティションが複数存在する場合は、例えばランダムで任意のパーティションを選択しても、その他の任意のアルゴリズムによって最適なパーティションを選択するものであってもよい。
【００４５】
《情報処理システム》
図２は、本実施形態に係る記憶制御装置としての記憶制御部２２０を含む情報処理システム２００の構成を示すブロック図である。
【００４６】
図２を参照すると、情報処理システム２００は、１台以上のホストコンピュータ２１０、記憶媒体２４０、および、ホストコンピュータ２１０と記憶媒体２４０とを接続するネットワーク２５０を含む。なお、記憶媒体２４０は、複数の記憶媒体に分散してネットワーク２５０に接続されていてもよい。
【００４７】
ホストコンピュータ２１０は、ＯＳ (Operating System)２１１およびＯＳ２１１上で動作する複数のコアやソフトウェアであるスレッド２１２と、本実施形態の記憶制御部２２０と、を備える。記憶制御部２２０は、キャッシュ２２１を有し、ＯＳ２１１および複数のコアやスレッド２１２の処理における、記憶媒体２４０へのReadおよびWriteを含むアクセス処理を制御する。
【００４８】
記憶媒体２４０は、NANDフラッシュを記憶素子として用いたＳＳＤやＳＭＲ(Shingled Magnetic Recording)を採用したＨＤＤなどの追記形式の記憶媒体である。なお、記憶媒体２４０は、媒体本体２４１とバッファなどとを有してもよい。また、ネットワーク２５０の形態は特に限定されず、ホストコンピュータ２１０と記憶媒体２４０とが直接接続される形態であってもよい。また、ホストコンピュータ２１０はネットワーク２５０によって接続された複数の装置、あるいは、システムで構成されてもよい。
【００４９】
《記憶制御装置の機能構成》
図３は、本実施形態に係る記憶制御装置としての記憶制御部２２０の機能構成を示すブロック図である。なお、図３において、図２と同様の構成要素には同じ参照番号を付している。
【００５０】
図３を参照すると、記憶制御部２２０は、ページプールとしてのキャッシュ２２１と、アクセス制御部３０１と、キャッシュヒット／ミス判定部３０２と、ページ状態管理テーブル３８１を有するページ状態管理部３０８と、パーティション容量設定テーブル３７１を有するパーティション容量管理部３０７と、を備える。また、記憶制御部２２０は、置換対象ページ選択部３０３と、置換ページ履歴テーブル３４１を有する置換履歴管理部３０４と、容量追加判定部３０５と、追加容量取得元選択部３０６と、不要ページ容量解放部３０９と、を備える。
【００５１】
なお、図３において、キャッシュヒット／ミス判定部３０２と、ページ状態管理部３０８と、パーティション容量管理部３０７と、置換対象ページ選択部３０３と、不要ページ容量解放部３０９と、が削減候補設定部として機能する。また、キャッシュヒット／ミス判定部３０２と、ページ状態管理部３０８と、パーティション容量管理部３０７と、置換対象ページ選択部３０３と、置換履歴管理部３０４と、容量追加判定部３０５と、追加容量取得元選択部３０６と、が容量制御部として機能する。
【００５２】
《キャッシュ》
ページプールとしてのキャッシュ２２１は、ホストコンピュータ２１０のコアやスレッドの記憶媒体２４０に対するアクセスについて、キャッシュされるデータをページ単位で格納する。
【００５３】
《アクセス制御部》
アクセス制御部３０１は、ホストコンピュータ２１０のソフトウェアからのアクセス要求を受け取り、記憶媒体２４０に対して必要なアクセス処理と、アクセス要求に対する結果の応答を行う。また、アクセス制御部３０１は、置換対象ページ選択部３０３の指示によって、記憶媒体２４０に対するアクセスの代わりにキャッシュ２２１の指定されたページにアクセス、もしくは、キャッシュ２２１に含まれるページのデータを記憶媒体２４０に書き込む。
【００５４】
《キャッシュヒット／ミス判定部》
キャッシュヒット／ミス判定部３０２は、アクセス制御部３０１の受け取ったアクセス要求における記憶媒体２４０のアクセス先アドレスの情報を受け取り、ページ状態管理テーブル３８１を参照して、アクセス先のデータがキャッシュ２２１に有るか否かを判定する。また、キャッシュヒット／ミス判定部３０２は、キャッシュヒットまたはキャッシュミスの判定結果を置換対象ページ選択部３０３に伝える。
【００５５】
《ページ状態管理部》
ページ状態管理部３０８は、ページ状態管理テーブル３８１を用いて、キャッシュ２２１に含まれる各ページについて、記憶媒体２４０に対するキャッシュ機能の実現に必要な管理情報、および、パーティションの容量調整に必要な情報を管理する。
【００５６】
（ページ状態管理テーブル）
図４は、本実施形態に係るページ状態管理テーブル３８１の構成を示す図である。
【００５７】
ページ状態管理テーブル３８１の各ページのエントリは、エントリに対応する当該ページが使用されていることを示す使用フラグ４０１と、記憶媒体２４０における当該ページのデータの格納先を示すアドレス４０２と、当該ページの所属するパーティションを示すパーティション番号４０３と、を有する。また、各ページのエントリは、各パーティションにおける置換の優先順位を示す置換優先順位４０４と、各ページがキャッシュヒットしたことを示すアクセスフラグ４０５と、を有する。さらに、各ページのエントリは、各ページがキャッシュ不要なページと判定されていることを示す不要候補フラグ４０６と、各ページが記憶媒体２４０の格納先に記録されたデータから更新されていることを示す更新フラグ４０７と、を有する。
【００５８】
なお、ページ状態管理テーブル３８１の各エントリに格納されるデータの形式は、図４に示した形式に限定されず、例えば、使用フラグ４０１を持つ代わりにアドレス４０２の値を記憶媒体２４０の記憶領域と対応しない特定の値に設定することで代用してもよい。また、置換優先順位４０４は、順位情報を数値で持つ代わりに例えばパーティション内のページの置換アルゴリズムとしてＬＲＵ(Least Recently Used)を用いる場合に、リンクリストの形式で表してもよい。加えて、例えば、不要ページ容量解放部３０９が各ページのアクセス時刻の情報を用いて不要なデータが格納されたページであるか判定を行う場合、各エントリにアクセスフラグ４０５の代わりに最終アクセス時刻の情報を持つようにしてもよい。
【００５９】
《パーティション容量管理部》
パーティション容量管理部３０７は、パーティション容量設定テーブル３７１を用いて、各パーティションをキャッシュ内に定義され独立したキャッシュとして動作させ、パーティションに設定された容量の情報を管理する。
【００６０】
（パーティション容量設定テーブル）
図５は、本実施形態に係るパーティション容量設定テーブル３７１の構成を示す図である。
【００６１】
パーティション容量設定テーブル３７１の各エントリは定義された個別のパーティションに対応しており、パーティションを識別するためのパーティション番号５０１と、エントリに対応する当該パーティションに割り当てられたページ数を示す設定容量５０２と、を有する。さらに、パーティション容量設定テーブル３７１の各エントリは、当該パーティションにおいて他パーティションに対して解放可能な容量を示す解放可能容量５０３と、実際にパーティションに含まれるページ数を表す実容量５０４と、を有する。
【００６２】
なお、パーティション容量設定テーブル３７１の各エントリに格納されるデータの形式は、図５に示した形式に限定されず、例えば、パーティション番号５０１を持つ代わりに先頭から数えたエントリの順番をパーティション番号として使用してもよい。また、設定容量５０２、解放可能容量５０３、および、実容量５０４をページ数ではなく、バイト単位の容量で示してもよい。さらに、容量追加判定部３０５における各パーティションの容量追加要求を１回ずつ処理せずに、複数回の要求をまとめて処理する場合には、各パーティションに対応するエントリに、容量追加要求の回数を格納してもよい。
【００６３】
《置換対象ページ選択部》
置換対象ページ選択部３０３は、キャッシュヒット／ミス判定部３０２によるキャッシュヒットまたはキャッシュミスの判定結果に基づき、アクセス制御部３０１に対してキャッシュ２２１または記憶媒体２４０に対する必要なアクセスの指示をする。そして、置換対象ページ選択部３０３は、ページ状態管理テーブル３８１に格納された各ページの置換優先順位４０４やデータに対応するアドレスの情報を更新する。また、置換対象ページ選択部３０３は、アクセス制御部３０１に対して、アクセス要求で指定されたアドレスに対応するページに対するアクセスを行い、応答するように指示する。
【００６４】
さらに、キャッシュミスが発生した場合に、置換対象ページ選択部３０３は、パーティション容量設定テーブル３７１の設定容量５０２を参照して、新しいデータを格納するために置換対象となるページを提供するパーティションを決定する。また、置換対象ページ選択部３０３は、置換対象となるページに既に格納されているデータのアドレス４０２を、置換履歴管理部３０４の置換ページ履歴テーブル３４１に追加する。そして、置換対象ページ選択部３０３は、置換対象となるページの更新フラグ４０７がセットされている場合、当該ページに格納されているデータを新しいデータで置き換える前に、あらかじめ記憶媒体２４０の格納先に書き込むように、アクセス制御部３０１に指示する。
【００６５】
《置換履歴管理部》
置換履歴管理部３０４は、置換ページ履歴テーブル３４１を用いて、各パーティションにおいて過去の一定期間に新規に格納されるデータによって置換されたページについて、当該ページに格納されていたデータに関する、記憶媒体２４０の格納先アドレスを管理する。また、置換履歴管理部３０４は、置換ページ履歴テーブル３４１に格納されたページのアドレスから一定の期間を経過したアドレスを削除する。
【００６６】
（置換ページ履歴テーブル）
図６は、本実施形態に係る置換ページ履歴テーブル３４１の構成を示す図である。
【００６７】
置換ページ履歴テーブル３４１は、パーティションごとに置換されたページの履歴である置換履歴６１０〜６３０を持ち、置換履歴６１０〜６３０はそれぞれ、置換された個別のページを表す置換アドレス６１１〜６３１を含む。なお、置換履歴６１０〜６３０のそれぞれに記憶される置換アドレス６１１〜６３１の数は、パーティションの容量変更を頻繁に行なうか否かを決定する要因となる。例えば、置換アドレス６１１〜６３１の数を多くするにつれて、キャッシュミス時にパーティションの容量追加の条件を満たす回数が増加する。
【００６８】
なお、置換ページ履歴テーブル３４１の各エントリに格納されるデータの形式は、図６に示した形式に限定されない。例えば、置換履歴６１０〜６３０は、置換アドレス６１１〜６３１を格納する代わりに、Bloomフィルタのように特定のアドレスが置換履歴６１０〜６３０の集合に含まれるか判定するためのデータ形式を用いてもよい。この場合、置換履歴６１０〜６３０を複数のBloomフィルタから形成し、一定期間の経過ごとに新しいBloomフィルタと古いBloomフィルタを入れ替えることで、過去の一定期間内に置換されたページを判定する処理に対応可能である。
【００６９】
《容量追加判定部》
容量追加判定部３０５は、キャッシュミスとなったアクセスについて、格納先のアドレスを置換ページ履歴テーブル３４１に格納された、アクセスを行った処理に対応するパーティションの置換履歴６１０〜６３０に含まれているか判定する。そして、容量追加判定部３０５は、格納先のアドレスが置換履歴６１０〜６３０に含まれており、かつ、容量追加要求が行われていない場合は、当該パーティションに対する容量追加が必要と判定し、追加容量取得元選択部３０６に対して１ページ分の容量の追加指示を行う。
【００７０】
なお、本実施形態においては、１ページ分の容量の追加を指示するが、複数ページ分の容量の追加であってもよい。追加するページ数を増加させるにつれて、１回のパーティションの容量変化が大きくなり容量適正化が迅速に進むが、逆に、容量の変化が激しく不安定になる傾向があり、キャッシュメモリの容量、パーティションの容量、アクセス頻度、などの条件を考慮して好適な数が設定されればよい。
【００７１】
《追加容量取得元選択部》
追加容量取得元選択部３０６は、容量追加判定部３０５からのパーティションに対する容量追加指示を受けて、パーティション容量設定テーブル３７１の各パーティションに関する解放可能容量５０３を参照し、解放可能な容量を持つパーティションを抽出する。そして、抽出されたパーティションから、容量追加指示に対して容量を提供するパーティションを選択する。追加容量取得元選択部３０６は、選択されたパーティションについて、パーティション容量設定テーブル３７１の解放可能容量５０３から１ページ分を減算し、容量追加指示の対象のパーティションについて、パーティション容量設定テーブル３７１の設定容量５０２を１ページ分加算する。
【００７２】
なお、容量追加判定部３０５が、複数ページの追加要求をする場合、追加容量取得元選択部３０６は、複数ページや複数パーティションからの減算をすることになる。
【００７３】
《不要ページ容量解放部》
不要ページ容量解放部３０９は、ページ状態管理テーブル３８１の各エントリを巡回し、アクセスフラグ４０５および不要候補フラグ４０６を確認する。エントリの巡回時にアクセスフラグ４０５がセットされている場合は、前回当該エントリを巡回した後に対応するページに対してアクセスがあったことを示すため、ワーキングセットに含まれるページと判断する。そして、アクセスフラグ４０５をリセットする。一方、エントリの巡回時にアクセスフラグ４０５がセットされてなく、かつ、不要候補フラグ４０６がセットされていない場合は、当該ページが一定期間アクセスされていないページ、つまりワーキングセットに含まれないページであると判断し、不要候補フラグ４０６をセットする。また、当該ページを含むパーティションについて、パーティション容量設定テーブル３７１の解放可能容量５０３に１ページ分を加算する。
【００７４】
なお、本実施形態においては、例えば、クロックアルゴリズムを用いて不要ページ容量の検出を行なうが、他のアルゴリズムを使用してもよい。
【００７５】
《記憶制御装置のハードウェア構成》
図７は、本実施形態における記憶制御装置としての記憶制御部２２０のハードウェア構成を示したブロック図である。なお、図７においては、記憶制御部２２０はホストコンピュータ２１０のソフトウェア処理として図示するが、記憶制御部２２０を、ホストコンピュータ２１０とは独立したワンチップのコンピュータで実現してもよい。
【００７６】
図７で、ＣＰＵ(Central Processing Unit)７１０は演算制御用のプロセッサであり、プログラムを実行することで図３の記憶制御部２２０の機能構成部を実現する。ＲＯＭ(Read Only Memory)７２０は、初期データおよびプログラムなどの固定データおよびプログラムを記憶する。また、キャッシュ２２１は、外部の記憶媒体２４０のアクセスにおいて頻繁にアクセスするデータを保持する。本実施形態では、各処理に対して少なくとも１つのページを含むパーティション単位に領域が割り当てられる。また、ネットワークインタフェース７３０は、ネットワーク２５０を介して記憶媒体２４０や他の装置と通信する。なお、ＣＰＵ７１０は１つに限定されず、複数のＣＰＵ（コア）であってもよい。また、ネットワークインタフェース７３０は、ＣＰＵ７１０とは独立したＣＰＵを有して、ＲＡＭ(Random Access Memory)７４０の領域に送受信データを書き込みあるいは読み出しするのが望ましい。また、ＲＡＭ７４０とストレージ７５０との間でデータを転送するＤＭＡＣ(Direct Memory Access Controller)を設けるのが望ましい（図示なし）。さらに、入出力インタフェース７６０は、ＣＰＵ７１０とは独立したＣＰＵを有して、ＲＡＭ７４０の領域に入出力データを書き込みあるいは読み出しするのが望ましい。したがって、ＣＰＵ７１０は、ＲＡＭ７４０にデータが受信あるいは転送されたことを認識してデータを処理する。また、ＣＰＵ７１０は、処理結果をＲＡＭ７４０に準備し、後の送信あるいは転送はネットワークインタフェース７３０やＤＭＡＣ、あるいは入出力インタフェース７６０に任せる。
【００７７】
ＲＡＭ７４０は、ＣＰＵ７１０が一時記憶のワークエリアとして使用するランダムアクセスメモリである。ＲＡＭ７４０には、本実施形態の実現に必要なデータを記憶する領域が確保されている。アクセスアドレス７４１は、ＯＳ２１１またはコアやスレッド２１２から記憶媒体２４０にアクセスしたアドレスである。キャッシュヒットアドレス７４２は、アクセスアドレス７４１の内、キャッシュヒットしたアドレスである。キャッシュヒミスアドレス７４３は、アクセスアドレス７４１の内、キャッシュミスしたアドレスである。容量追加パーティション７４４は、キャッシュミスしたアドレスが置換された（記憶媒体に押し出された）アドレスと一致して、容量追加を要求するパーティションである。容量削減パーティション７４５は、アクセスの無いあるいは頻度の低いページを含み、削減候補となったパーティションで、容量追加パーティション７４４に容量を移動するために選択されたパーティションである。アクセス情報７４６は、記憶媒体２４０に対するアクセス（Read、Writeを含む）内容およびデータである。入出力データ７４７は、入出力インタフェース７６０を介して入出力されるデータである。送受信データ７４８は、ネットワークインタフェース７３０を介して記憶媒体２４０に送受信されるデータである。アプリケーション使用領域７４９は、記憶制御以外の処理でアプリケーションが使用するエリアである。
【００７８】
ストレージ７５０には、データベースや各種のパラメータ、あるいは本実施形態の実現に必要な以下のデータまたはプログラムが記憶されている。ページ状態管理テーブル３８１は、図４に示した、キャッシュ２２１の各ページを管理するテーブルである。パーティション容量設定テーブル３７１は、図５に示した、各処理に割り当てられたキャッシュ２２１のパーティションを管理するテーブルである。置換ページ履歴テーブル３４１は、図６に示した、キャッシュ２２１から記憶媒体２４０に押し出されたページアドレスの履歴をパーティションごとに格納するテーブルである。解放容量算出アルゴリズム７５１は、使用してないあるいは使用頻度が低いキャッシュ内のページを検出して、容量を削減可能なパーティションを選定するアルゴリズムであって、本例ではクロックアルゴリズムを含む。ページ巡回周期（巡回速度）７５２は、クロックアルゴリズムによる巡回周期を格納する。
【００７９】
ストレージ７５０には、以下のプログラムが格納される。ＯＳ２１１は、本ホストコンピュータ２１０の全体を制御する基礎プログラムである。複数のスレッド２１２は、現在、本ホストコンピュータ２１０が実行中のプログラムにおける処理単位である。記憶制御プログラム７５３は、ＯＳ２１１や複数のスレッド２１２からの記憶媒体２４０へのアクセスを受けて、本実施形態のアクセス制御を実現するプログラムである。アクセス処理モジュール７５４は、ＯＳ２１１や複数のスレッド２１２からの記憶媒体２４０へのアクセスを処理するモジュールであり、キャッシュヒット時の制御を行なうキャッシュヒット制御モジュール７５５と、キャッシュミス時の制御を行なうキャッシュミス制御モジュール７５６と、を含む。設定容量制御モジュール７５７は、容量削減可能なパーティションから容量追加を要求するパーティションへの設定容量の移動を制御するモジュールである。解放容量算出モジュール７５８は、解放容量算出アルゴリズム７５１に従って、使用してないあるいは使用頻度が低いキャッシュ内のページを検出して、容量を削減可能なパーティションを選定するためのモジュールである。
【００８０】
入出力インタフェース７６０は、入出力機器との入出力データをインタフェースする。入出力インタフェース７６０には、表示部７６１、操作部７６２、が接続されるが、これに限定されない。
【００８１】
なお、図７のＲＡＭ７４０やストレージ７５０には、ホストコンピュータ２１０が有する汎用の機能や他の実現可能な機能に関連するプログラムやデータは図示されていない。
【００８２】
《記憶制御装置の処理手順》
図８は、本実施形態における記憶制御装置としての記憶制御部２２０の処理手順を示したフローチャートである。このフローチャートは、図７のＣＰＵ（コア）７１０がＲＡＭ７４０を使用して実行し、図３の機能構成部を実現する。
【００８３】
記憶制御部２２０は、ステップＳ８０１において、各テーブルの処理化などを含む初期化処理を行なう。記憶制御部２２０は、ステップＳ８０３において、ホストコンピュータ２１０における記憶媒体２４０へのアクセスを制御するための、アクセス処理をスタートさせる。また、記憶制御部２２０は、ステップＳ８０５において、キャッシュ２２１に各処理に対応して配分されたパーティションの設定容量を削減および追加するための、設定容量制御処理をスタートさせる。また、記憶制御部２２０は、ステップＳ８０７において、キャッシュ２２１に各処理に対応して配分されたパーティションから解放可能な容量（ページ数）を算出するための、解放容量算出処理をスタートさせる。
【００８４】
記憶制御部２２０は、ステップＳ８０９において、記憶制御処理の終了か否かを判定する。そして、記憶制御処理の終了と判定すれば、処理を終了する。なお、図８においては、アクセス処理と、設定容量制御処理と、解放容量算出処理と、は独立に並行して実行されるとして説明したが、それぞれを関連付けてシーケンスに実行してもよい。
【００８５】
（アクセス処理）
図９は、本実施形態におけるアクセス処理の手順を示したフローチャートである。本フローチャートにおいては、ホストコンピュータ２１０のソフトウェアからのアクセス要求の処理を行う手順である。
【００８６】
記憶制御部２２０のアクセス制御部３０１は、ステップＳ９０１において、ホストコンピュータ２１０のソフトウェアからのアクセス要求を受け取ると、キャッシュヒット／ミス判定部３０２に対してアクセス要求の情報を伝える。記憶制御部２２０のキャッシュヒット／ミス判定部３０２は、ステップＳ９０３において、ページ状態管理テーブル３８１を参照し、アドレス４０２がアクセス要求の記憶媒体２４０に対する格納先と一致するページが存在するか確認する。そして、キャッシュヒット／ミス判定部３０２は、ステップＳ９０５において、キャッシュヒットかキャッシュミスかによって分岐する。
【００８７】
アクセス要求の記憶媒体２４０に対する格納先に一致するデータを格納するページが存在する場合（ステップＳ９０５のＹｅｓ判定）、ステップＳ９０７において、キャッシュヒット／ミス判定部３０２は、アクセス要求のアドレス、および、アクセスがReadまたはWriteのいずれであるかの情報を置換対象ページ選択部３０３に伝える。そして、ステップＳ９０７において、記憶制御部２２０の置換対象ページ選択部３０３は、キャッシュヒット時の処理を実行し、実行が完了した後はステップＳ９１１以降の処理を実行する。
【００８８】
アクセス要求の記憶媒体２４０に対する格納先に一致するデータを格納するページが存在しない場合（ステップＳ９０５のＮｏ判定）、ステップＳ９０９において、キャッシュヒット／ミス判定部３０２は、アクセス要求のアドレス、および、アクセスがReadまたはWriteのいずれであるかの情報を置換対象ページ選択部３０３に伝える。そして、ステップＳ９０９において、置換対象ページ選択部３０３は、キャッシュミス時の処理を実行する。
【００８９】
ステップＳ９０７、または、ステップＳ９０９にて置換対象ページ選択部３０３から指示された、記憶媒体２４０、および／または、キャッシュ２２１に対するアクセスを完了すると、アクセス制御部３０１は、ステップＳ９１１において、ホストコンピュータ２１０のアクセス要求を行ったソフトウェアに結果を通知し、アクセス要求の処理を完了する。
【００９０】
（キャッシュヒット時のアクセス処理）
図１０は、本実施形態におけるキャッシュヒット時のアクセス処理（Ｓ９０７）の手順を示したフローチャートである。なお、本実施形態ではキャッシュ置換アルゴリズムとしてＬＲＵを想定するが、他の置換アルゴリズムを用いてもよい。
【００９１】
記憶制御部２２０の置換対象ページ選択部３０３は、ステップＳ１００１において、キャッシュヒットしたアドレスをページ状態管理テーブル３８１のアドレス４０２と比較して、キャッシュヒットしたアドレスと対応するページを特定する。置換対象ページ選択部３０３は、ステップＳ１００３において、アクセス制御部３０１に対して、ステップＳ１００１で特定したキャッシュ２２１のページにアクセス要求の実行を指示する。
【００９２】
置換対象ページ選択部３０３は、ステップＳ１００５において、ページ状態管理テーブル３８１における、キャッシュヒットしたページの置換優先順位４０４を最低値に更新する。また、置換対象ページ選択部３０３は、ステップＳ１００５において、ページに対応するアクセスフラグ４０５をセットし、不要候補フラグ４０６をリセットする。置換対象ページ選択部３０３は、ステップＳ１００７において、キャッシュヒットしたページと同一のパーティションに含まれる他の各ページについて、ページ状態管理テーブル３８１のキャッシュヒットしたページの置換優先順位４０４を１増加させる。
【００９３】
置換対象ページ選択部３０３は、ステップＳ１００９において、キャッシュヒットしたアクセスがReadであるかWriteであるかを判定する。キャッシュヒットしたアクセスがReadである場合（ステップＳ１００９のＹｅｓ判定）、置換対象ページ選択部３０３は、ステップ１０１１において、ページ状態管理テーブル３８１のキャッシュヒットしたページの更新フラグ４０７をリセットして処理を終了する。キャッシュヒットしたアクセスがWriteである場合（ステップＳ１００９のＮｏ判定）、置換対象ページ選択部３０３は、ステップＳ１０１３において、ページ状態管理テーブル３８１のキャッシュヒットしたページの更新フラグ４０７をセットして処理を終了する。
【００９４】
以上のステップＳ１００１からＳ１０１３までの処理を行い、図９のステップＳ９０７において、記憶制御部２２０の置換対象ページ選択部３０３がキャッシュヒット時の処理を行う動作が完了する。ステップＳ１００１からＳ１０１３の処理順序は、必ずしも図１０に示した順序である必要はない。例えば、ステップＳ１００３からＳ１０１３の処理は同時期に実行、あるいは、順序を入れ替えた実行が可能である。また、ステップＳ１００１において、ページ状態管理テーブル３８１のアドレス４０２と比較してキャッシュヒットしたアドレスと対応するページを特定する処理は、キャッシュヒット／ミス判定部３０２からキャッシュヒットの判定を行った際に特定されたページ情報を直接に受け取る処理であってもよい。さらに、ステップＳ１００５およびステップＳ１００７の置換優先順位４０４に対する処理は、置換優先順位４０４がリンクリスト形式で表される場合は、リンクリストにおけるキャッシュヒットしたページの位置を、置換の優先順位が最低となるように移動する操作によって実現する。
【００９５】
（キャッシュミス時のアクセス処理）
図１１Ａおよび図１１Ｂは、本実施形態におけるキャッシュミス時のアクセス処理（Ｓ９０９）の手順を示したフローチャートである。
【００９６】
記憶制御部２２０の置換対象ページ選択部３０３は、ステップＳ１１０１において、パーティション容量設定テーブル３７１にアクセスし、キャッシュミスが発生したアクセス要求を行った処理に対応するパーティションの設定容量５０２と実容量５０４とを取得して比較する。置換対象ページ選択部３０３は、ステップＳ１１０３において、比較結果に対応して分岐する。
【００９７】
比較の結果、パーティションの実容量５０４が設定容量５０２を下回る場合（ステップＳ１１０３のＹｅｓ判定）、置換対象ページ選択部３０３は、ステップＳ１１０５において、パーティション容量設定テーブル３７１にアクセスし、実容量５０４が設定容量５０２を上回るパーティションを抽出する。置換対象ページ選択部３０３は、ステップＳ１１０７において、ステップＳ１１０５で抽出したパーティションから、キャッシュミスに伴う新規データの格納に必要なページを提供する任意のパーティションを１つ選択する。そして、置換対象ページ選択部３０３は、ステップＳ１１０９において、ページ状態管理テーブル３８１を参照して、ステップＳ１１０７で選択されたパーティションに含まれるページのうち、置換優先順位４０４が最も高いページをキャッシュミスに伴う新規データの格納先として選択して、ステップＳ１１１３以降の処理を実行する。
【００９８】
ステップ１１０１での比較の結果、パーティションの実容量５０４が設定容量５０２以上である場合（ステップＳ１１０３のＮｏ判定）、置換対象ページ選択部３０３は、ステップＳ１１１１において、ページ状態管理テーブル３８１を参照する。そして、置換対象ページ選択部３０３は、ステップＳ１１１１において、キャッシュミスが発生した処理に対応するパーティションに含まれるページのうち、置換優先順位４０４が最も高いページをキャッシュミスに伴う新規データの格納先として選択する。
【００９９】
置換対象ページ選択部３０３は、ステップＳ１１１３において、アクセス制御部３０１に対して、キャッシュミスに伴う新規データの格納先として選択したページについて、ページ状態管理テーブル３８１の使用フラグ４０１および更新フラグ４０７を参照して、選択したページのデータを記憶媒体２４０に反映するべきか確認する。置換対象ページ選択部３０３は、ステップＳ１１１５において、記憶媒体２４０に反映するべきか否かにより分岐する。新規データの格納先として選択したページについて、使用フラグ４０１および更新フラグ４０７の少なくとも１つがセットされていない場合（ステップＳ１１１５のＮｏ判定）、置換対象ページ選択部３０３は図１１ＢのステップＳ１１１９以降の処理を実行する。
【０１００】
一方、新規データの格納先として選択したページについて、使用フラグ４０１および更新フラグ４０７の両方がセットされている場合（ステップＳ１１１５のＹｅｓ判定）、置換対象ページ選択部３０３は、ステップＳ１１１７において、ページ状態管理テーブル３８１のキャッシュミスしたページに対応するアドレス４０２を取得する。そして、アクセス制御部３０１に対して、キャッシュミスしたページに現在格納されているデータを、記憶媒体２４０のアドレス４０２が示す領域に対して書き込むように指示する。
【０１０１】
置換対象ページ選択部３０３は、ステップＳ１１１９において、キャッシュミスしたアクセス要求がReadかWriteかを判定する。ホストコンピュータ２１０のソフトウェアからのアクセス要求がReadである場合（ステップＳ１１１９のＹｅｓ判定）、置換対象ページ選択部３０３は、ステップＳ１１２１において、アクセス制御部３０１に対して、記憶媒体２４０に要求されたReadアクセスを実行する。そして、ステップＳ１１０９またはステップＳ１１１１で選択したキャッシュ２２１のページにRead結果を格納するように指示する。置換対象ページ選択部３０３は、ステップＳ１１２３において、ステップＳ１１２１で結果を格納したページについて、ページ状態管理テーブル３８１の更新フラグ４０７をリセットして、ステップＳ１１２９以降を実行する。
【０１０２】
ホストコンピュータ２１０のソフトウェアからのアクセス要求がWriteである場合（ステップＳ１１１９のＮｏ判定）、置換対象ページ選択部３０３は、ステップＳ１１２５において、アクセス制御部３０１に対して、Writeを要求されたデータを、ステップＳ１１０９またはステップＳ１１１１で選択した、キャッシュ２２１のページに格納するように指示する。置換対象ページ選択部３０３は、ステップＳ１１２７において、ステップＳ１１２５でWrite結果を格納したページについて、ページ状態管理テーブル３８１の、キャッシュヒットしたページの更新フラグ４０７をセットする。
【０１０３】
置換対象ページ選択部３０３は、ステップＳ１１２９において、ステップＳ１１０９またはステップＳ１１１１で選択したページについて、ページ状態管理テーブル３８１のパーティション番号４０３を、キャッシュミスが発生したアクセス要求を行った処理に対応するパーティションを表す番号で更新し、置換優先順位４０４を最低値に更新する。置換対象ページ選択部３０３は、ステップＳ１１３１において、ステップＳ１１０９またはステップＳ１１１１で選択したページについて、ページ状態管理テーブル３８１のアクセスフラグ４０５をセットし、不要候補フラグ４０６をリセットする。そして、置換対象ページ選択部３０３は、ステップＳ１１３３において、キャッシュミスが発生したアクセス要求を行った処理に対応するパーティションに含まれる他の各ページについて、ページ状態管理テーブル３８１の置換優先順位４０４を１増加させる。
【０１０４】
置換対象ページ選択部３０３は、ステップＳ１１３５において、容量追加判定部３０５に、新規データの格納先となったページに直前まで格納されていたデータのアドレスを伝えて、対応するパーティションの置換履歴６１０〜６３０に新たな置換アドレス６１１〜６３１として設定する。
【０１０５】
置換対象ページ選択部３０３は、ステップＳ１１３７において、ステップＳ１１０１での比較の結果に基づいて分岐する。パーティションの実容量５０４が設定容量５０２以上であった場合（ステップＳ１１３７のＹｅｓ判定）、処理を終了する。一方、パーティションの実容量５０４が設定容量５０２を下回っていた場合（ステップＳ１１３７のＮｏ判定）、置換対象ページ選択部３０３は、ステップＳ１１３９において、パーティション容量設定テーブル３７１にアクセスする。次に、キャッシュミスが発生したアクセス要求を行った処理に対応するパーティションの実容量５０４に１を加算する。そして、ステップＳ１１０９またはステップＳ１１１１で選択したページが含まれていたパーティションの実容量５０４から１を減算して、処理を終了する。
【０１０６】
以上のステップＳ１１０１からＳ１１３９までの処理を行い、図９のステップＳ９０９において、置換対象ページ選択部３０３がキャッシュミス時の処理を行う動作が完了する。ステップＳ１１０１からＳ１１３９の処理順序は、必ずしも図１１Ａおよび図１１Ｂに示した順序である必要はない。例えば、ステップＳ１１２９からＳ１１３９の処理は同時期に実行、あるいは、順序を入れ替えた実行が可能である。また、ステップＳ１１０７においてキャッシュミスに伴う新規データの格納に必要なページを提供するパーティションを、例えば、ページ状態管理テーブル３８１を参照して各パーティションの置換優先順位４０４が最も高いページについて不要候補フラグ４０６を調べる。そして、不要候補フラグ４０６がセットされているパーティションを優先的に選択するようにしてもよい。
【０１０７】
（設定容量調整処理）
図１２は、本実施形態におけるパーティションの設定容量調整処理の手順を示したフローチャートである。本フローチャートにおいては、容量追加判定部３０５がパーティションの容量追加の必要性を判定し、追加容量取得元選択部３０６によって容量追加が必要なパーティションに対して容量を提供するパーティションを決定して、パーティションの設定容量を調整する。
【０１０８】
記憶制御部２２０の容量追加判定部３０５は、置換対象ページ選択部３０３からキャッシュミスとなったアクセス要求のアドレスを受け取る。すると、ステップＳ１２０１において、置換履歴管理部３０４が有する置換ページ履歴テーブル３４１の、アクセス要求を行った処理に対応するパーティションの置換履歴６１０〜６３０に、アクセス要求のアドレスと一致する置換アドレス６１１〜６３１が含まれているかを判定する。
【０１０９】
容量追加判定部３０５は、ステップＳ１２０３において、アクセス要求のアドレスと一致する置換アドレス６１１〜６３１が含まれているか否かで分岐する。キャッシュミスとなったアドレスが処理に対応するパーティションの置換履歴６１０〜６３０に含まれていなかった場合（ステップＳ１２０３のＮｏ判定）、処理を終了する。
【０１１０】
キャッシュミスとなったアドレスが処理に対応するパーティションの置換履歴６１０〜６３０に含まれている場合（ステップＳ１２０３のＹｅｓ判定）は、容量追加判定部３０５は、ステップＳ１２０５において、追加容量取得元選択部３０６に対してキャッシュミスが発生したアクセス要求を行ったパーティションへの１ページ分の容量の追加指示を行う。記憶制御部２２０の追加容量取得元選択部３０６は、ステップＳ１２０７において、パーティション容量設定テーブル３７１の各パーティションに関する解放可能容量５０３を参照し、解放可能な容量を持つパーティションを抽出する。
【０１１１】
追加容量取得元選択部３０６は、ステップＳ１２０９において、解放可能な容量を持つパーティションが抽出されたか否かで分岐する。抽出されたパーティションが無い場合（ステップＳ１２０９のＮｏ判定）、追加容量取得元選択部３０６は、容量追加判定部３０５が指示したパーティションへの容量追加を行わずに処理を終了する。
【０１１２】
抽出されたパーティションが有る場合（ステップＳ１２０９のＹｅｓ判定）、追加容量取得元選択部３０６は、ステップＳ１２１１において、抽出したパーティションの中から、容量追加指示が行われたパーティションに１ページ分の容量を提供する任意のパーティションを１つ選択する。そして、追加容量取得元選択部３０６は、ステップＳ１２１１において、パーティション容量設定テーブル３７１における選択されたパーティションの設定容量５０２および解放可能容量５０３を１ページ分ずつ減算する。また、追加容量取得元選択部３０６は、ステップＳ１２１３において、パーティション容量設定テーブル３７１における、容量追加判定部３０５から容量の追加指示が行われたパーティションの設定容量５０２を１ページ分加算して処理を終了する。
【０１１３】
以上のステップＳ１２０１からＳ１２１３までの処理を行い、容量追加判定部３０５がパーティションの容量追加の必要性を判定し、追加容量取得元選択部３０６によって容量追加が必要な前記パーティションに対して容量を提供するパーティションを決定して、パーティションの設定容量を調整する動作を完了する。ステップＳ１２０１からＳ１２１３までの処理順序は、必ずしも図１２に示した手順である必要はない。例えば、ステップＳ１２１１とＳ１２１３の処理は同時期に実行、あるいは、順序を入れ替えた実行が可能である。また、ステップＳ１２１１において容量を提供するパーティションを、例えば、パーティション容量設定テーブル３７１を参照して解放可能容量５０３が最も多いパーティションから選択するようにしてもよい。
【０１１４】
なお、前述したように、パーティションの設定容量の調整が１ページ単位でなく複数ページ単位で行なわれてもよい。
【０１１５】
（解放可能容量算出処理）
図１３は、本実施形態におけるパーティションの解放可能容量算出処理の手順を示したフローチャートである。本フローチャートにおいては、不要ページ容量解放部３０９がキャッシュ上に定義された各パーティションに含まれるページから、ワーキングセットに含まれていないと推測されるページを抽出し、各パーティションの解放可能容量５０３を更新する。
【０１１６】
記憶制御部２２０の不要ページ容量解放部３０９は、ステップＳ１３０１において、ページ状態管理テーブル３８１の最初のエントリに着目する。
【０１１７】
不要ページ容量解放部３０９は、ステップＳ１３０３において、着目中のエントリにおけるアクセスフラグ４０５および不要候補フラグ４０６を参照する。そして、不要ページ容量解放部３０９は、ステップＳ１３０５において、アクセスフラグ４０５がセットされているか否かを判定する。
【０１１８】
アクセスフラグ４０５がセットされていた場合（ステップＳ１３０５のＹｅｓ判定）、不要ページ容量解放部３０９は、ステップＳ１３０７において、着目中のエントリのアクセスフラグ４０５をリセットして、ステップＳ１３１５以降の処理を実行する。一方、アクセスフラグ４０５がセットされていない場合（ステップＳ１３０５のＮｏ判定）、不要ページ容量解放部３０９は、ステップＳ１３０９において、不要候補フラグ４０６がセットされているか否かを判定する。
【０１１９】
不要候補フラグ４０６がセットされている場合（ステップＳ１３０９のＹｅｓ判定）は、ステップＳ１３１５以降の処理を実行する。不要候補フラグ４０６がセットされていない場合（ステップＳ１３０９のＮｏ判定）、不要ページ容量解放部３０９は、ステップＳ１３１１において、着目中のエントリの不要候補フラグ４０６をセットする。そして、不要ページ容量解放部３０９は、ステップＳ１３１３において、パーティション容量設定テーブル３７１の、着目中のエントリに対応するページが含まれるパーティションの解放可能容量５０３に１ページ分の容量を加算する。
【０１２０】
不要ページ容量解放部３０９は、ステップＳ１３１５において、着目中のエントリがページ状態管理テーブル３８１の末尾のエントリか否かを判定する。現在着目中のエントリがページ状態管理テーブル３８１の最後のエントリである場合（ステップＳ１３１５のＹｅｓ判定）、ステップＳ１３０１に戻って処理を繰り返す。現在着目中のエントリがページ状態管理テーブル３８１の最後のエントリではない場合（ステップＳ１３１７のＮｏ判定）、不要ページ容量解放部３０９は、ステップＳ１３１７において、着目中のエントリをページ状態管理テーブル３８１における次のエントリに変更して、ステップＳ１３０３に戻り処理を繰り返す。
【０１２１】
以上のステップＳ１３０１からＳ１３１７までの処理を行い、不要ページ容量解放部３０９がキャッシュ上に定義された各パーティションに含まれるページから、ワーキングセットに含まれていないと推測されるページを抽出し、各パーティションの解放可能容量５０３を更新する動作を実行する。ステップＳ１３０１からＳ１３１７までの処理順序は、必ずしも図１３に示した順序である必要はない。例えば、ステップＳ１３１１とＳ１３１３の各処理は同時期に実行、あるいは、順序を入れ替えた実行が可能である。また、ステップＳ１３０１からＳ１３１７までのページ状態管理テーブル３８１の各エントリに対して処理を順番に行っていく手順は、任意の順序で各エントリに着目する手順であってもよい。加えて、各エントリに対応するページがワーキングセットに含まれない、長期間アクセスされていないページであると判定する方法として、アクセスフラグ４０５がセットされているかを確認する代わりに、例えば、各ページに対応するページ状態管理テーブル３８１のエントリに、各ページの最終アクセス時刻を記録する。そして、現在時刻と比較して一定の時間が経過している場合にワーキングセットに含まれないページと判断して不要候補フラグ４０６をセットする手順であってもよい。
【０１２２】
本実施形態によれば、各処理に対応したキャッシュのパーティションに割り当てるべき容量を測定することなしに処理中に適正化し、記憶媒体に対するアクセス性能を高めることができる。
【０１２３】
すなわち、キャッシュを通した記憶媒体に対するアクセスの情報を基に、パーティションの容量削減の可否を判断し、各パーティションの容量追加が必要な場合に削減可能なパーティションのいずれかから容量を移動する処理を繰り返す。これにより、各処理に対応したキャッシュのパーティションに割り当てるべき容量を直接測定せずに、各パーティションに割り当てる容量の最適化を実現し、ホストコンピュータで実行される処理全体の、記憶媒体に対するアクセス性能を高めることが可能である。
【０１２４】
具体的には、検出されたページを直接置換対象とはせずにパーティションから解放可能な容量のみを計算しておき、実際に他のパーティションにおいて容量が不足した際に改めて置換するページを決定する。この動作により、本実施形態と任意のキャッシュ置換アルゴリズムの組み合わせも実現可能になる。加えて、各パーティションの容量の割り当てに変更が必要になるまでページの置換を遅らせることで、不要なページの誤検出に伴うキャッシュミスの発生を低減することが可能である。
【０１２５】
［第３実施形態］
次に、本発明の第３実施形態に係る記憶制御装置について説明する。本実施形態に係る記憶制御装置は、上記第２実施形態と比べると、不要ページ容量解放部３０９におけるページ巡回周期（巡回速度）を調整する機能を有する点で異なる。本実施形態において、不要ページ検出は、不要なページを検出する周期を調整する検出周期調整機能を含む、その他の構成および動作は、第２実施形態と同様であるため、同じ構成および動作については同じ符号を付してその詳しい説明を省略する。
【０１２６】
《記憶制御装置の機能構成》
図１４は、本実施形態に係る記憶制御装置としての記憶制御部１４２０の機能構成を示すブロック図である。なお、図１４において、図３と同様の機能構成部には同じ参照番号を付して、重複する説明は省略する。
【０１２７】
図１４を参照すると、図３で表される第２実施形態と比較して、新たにページ巡回速度調整部１４１０を備える。
【０１２８】
ページ巡回速度調整部１４１０は、不要ページ容量解放部３０９がページ状態管理テーブル３８１の各エントリを参照して、エントリに対応するページがワーキングセットに含まれているか判定する処理の速度を指示する。処理の速度は、各ページがワーキングセットに含まれるか判定する閾値に関係しており、速度を速く設定することで各エントリが一度巡回されてから再度巡回されるまでの時間が短くなり、ワーキングセットに含まれると判定されるページのアクセス頻度は高くなる。つまり、不要ページ容量解放部３０９によって積極的にワーキングセットに含まれない、不要である可能性の高いページが抽出される。逆に、処理速度を遅く設定することで、各エントリが再度巡回されるまでの時間が長くなり、不要ページ容量解放部３０９による不要なページの抽出が、より厳密に行われるように設定可能である。
【０１２９】
ページ巡回速度調整部１４１０による、不要ページ容量解放部３０９に対する処理速度の指示は、次の場合に用いることが可能である。例えば、キャッシュ内で定義されるパーティションにおいて解放可能容量５０３が不足しており、容量追加判定部３０５によるパーティションの容量追加の指示を満たせない場合に、処理速度を速くして不要ページを積極的に抽出し、解放可能容量５０３の不足を解消することができる。
【０１３０】
本実施形態によれば、さらに、キャッシュの容量やアクセス頻度などを考慮して、不要ページ容量解放部３０９による不要なページの抽出の頻度と厳密性との調整をすることができる。
【０１３１】
［第４実施形態］
次に、本発明の第４実施形態に係る記憶制御装置について説明する。本実施形態に係る記憶制御装置は、上記第２実施形態および第３実施形態と比べると、不要ページ容量解放部３０９におけるページ巡回周期（巡回速度）を調整するためのワーキングセットの検出時間を測定する機能を有する点で異なる。本実施形態においては、キャッシュメモリへのアクセスにおいて発生したキャッシュヒットを、アクセスの対象であるパーティションに関連付けて検出するキャッシュヒット検出機能と、キャッシュヒットの検出結果から、パーティションに対するアクセス頻度の高いページの検出に要する時間を測定する検出時間測定機能とを備える。そして、測定された時間に基づいて、不要ページの検出周期を調整する。その他の構成および動作は、第２実施形態と同様であるため、同じ構成および動作については同じ符号を付してその詳しい説明を省略する。
【０１３２】
《記憶制御装置の機能構成》
図１５は、本実施形態に係る記憶制御装置としての記憶制御部１５２０の機能構成を示すブロック図である。なお、図１５において、図３または図１４と同様の機能構成部には同じ参照番号を付して、重複する説明は省略する。
【０１３３】
図１５を参照すると、図１４で表される第３実施形態と比較して、新たにワーキングセット検出時間測定部１５１１を備える。
【０１３４】
ワーキングセット検出時間測定部１５１１は、キャッシュヒット／ミス判定部３０２から各アクセス要求のキャッシュヒットまたはキャッシュミスの判定結果を取得し、一定時間あたりのキャッシュヒット率を算出する。また、ワーキングセット検出時間測定部１５１１は、容量追加判定部３０５からパーティションの容量追加が必要と判定されたキャッシュミスの頻度を取得し、キャッシュミスが全アクセスにおいて発生している割合を算出する。加えて、ワーキングセット検出時間測定部１５１１は、算出したキャッシュヒット率と、パーティションの容量追加が必要と判定されたキャッシュミスの割合を比較して、パーティションの容量追加が必要と判定されたキャッシュミスの割合がキャッシュヒット率に比べて一定以上となるまでに要する時間を測定する。そして、ワーキングセット検出時間測定部１５１１は、不要ページ容量解放部３０９が各ページに対応するページ状態管理テーブル３８１のエントリを巡回する時間間隔が、測定結果の時間となるようにページ巡回速度調整部１４１０を通して速度を調整する。
【０１３５】
《処理速度調整処理》
図１６は、本発明の第４実施形態における処理速度調整処理の手順を示したフローチャートである。本フローチャートは、不要ページ容量解放部３０９の処理速度を、ページ巡回速度調整部１４１０を通して最適に維持する。
【０１３６】
記憶制御部２２０のワーキングセット検出時間測定部１５１１は、ステップＳ１６０１において、キャッシュヒット数、キャッシュミス数、および、パーティションの容量追加が必要と判定されたキャッシュミス数を計測するカウンタを０（ゼロ）にリセットする。ワーキングセット検出時間測定部１５１１は、ステップＳ１６０３において、事前に定められた一定の時間が経過するまで、キャッシュヒット／ミス判定部３０２から全てのアクセス要求のキャッシュヒット、キャッシュミスの判定結果を取得し、その頻度をカウンタで計測する。同様に、ワーキングセット検出時間測定部１５１１は、ステップＳ１６０３において、容量追加判定部３０５からパーティションの容量追加が必要と判定された全てのキャッシュミスの情報を取得して、その頻度をカウンタで計測する。
【０１３７】
ワーキングセット検出時間測定部１５１１は、ステップＳ１６０５において、ステップＳ１６０３で計測したキャッシュヒット、キャッシュミスの頻度からキャッシュヒット率ａを算出する。また、ワーキングセット検出時間測定部１５１１は、ステップＳ１６０７において、ステップＳ１６０３で計測した、パーティションの容量追加が必要と判定されたキャッシュミス数が、全アクセス要求に占める割合ｂを算出する。
【０１３８】
ワーキングセット検出時間測定部１５１１は、ステップＳ１６０９において、全アクセス要求に占める割合ｂが、キャッシュヒット率ａと比べて一定の割合を上回るか否かを判定する。全アクセス要求に占める割合ｂが、キャッシュヒット率ａと比べて一定の割合を上回る場合（ステップＳ１６０９のＹｅｓ判定）、ワーキングセット検出時間測定部１５１１は、キャッシュにおけるワーキングセットの検出が不十分であると判断して、ステップＳ１６０１からの処理を再実行する。
【０１３９】
全アクセス要求に占める割合ｂが、キャッシュヒット率ａと比べて一定の割合以下である場合（ステップＳ１６０９のＮｏ判定）、ワーキングセット検出時間測定部１５１１は、ステップＳ１６１１において、キャッシュにおけるワーキングセットの検出が十分に行われていると判断して、最初にステップＳ１６０１の処理を開始してからの経過時間を算出する。
【０１４０】
ワーキングセット検出時間測定部１５１１は、ステップＳ１６１３において、不要ページ容量解放部３０９がキャッシュに含まれるページに対応する、ページ状態管理テーブル３８１の全エントリを巡回する時間が、ステップＳ１６１１で算出した時間と等しくなるようなページ巡回速度を計算する。具体的には、ページ状態管理テーブル３８１のエントリ数をステップＳ１６１１において算出した時間で割ることで、一定時間あたりに巡回するべきページ状態管理テーブル３８１のエントリ数が算出される。
【０１４１】
ワーキングセット検出時間測定部１５１１は、ステップＳ１６１５において、ページ巡回速度調整部１４１０に対して、ステップＳ１６１３で算出されたエントリ数を不要ページ容量解放部３０９の処理速度として設定して処理を終了する。
【０１４２】
以上のステップＳ１６０１からＳ１６１５までの処理を行い、不要ページ容量解放部３０９の処理速度を、ページ巡回速度調整部１４１０を通して最適に維持する動作を完了する。ステップＳ１６０１からＳ１６１５までの処理順序は、必ずしも図１６に示した順序である必要はない。例えば、ステップＳ１６０５とＳ１６０７の各処理は同時期に実行、あるいは、順序を入れ替えた実行が可能である。
【０１４３】
本実施形態によれば、実際の動作におけるキャッシュヒットの状況を参照して、ページ巡回速度を調整するので、キャッシュおよび記憶媒体の使用状況に応じた適正化ができ、記憶媒体に対するアクセス性能をより高めることができる。
【０１４４】
［第５実施形態］
次に、本発明の第５実施形態に係る記憶制御装置について説明する。本実施形態に係る記憶制御装置は、上記第２実施形態乃至第４実施形態と比べると、記憶制御装置としての記憶制御部がホストコンピュータ内ではなく、ネットワークを介した外部に独立して、あるいは、記憶媒体に含まれる点で異なる。その他の構成および動作は、第２実施形態と同様であるため、同じ構成および動作については同じ符号を付してその詳しい説明を省略する。
【０１４５】
《情報処理システム》
図１７は、本実施形態に係る記憶制御装置としての記憶制御部１７２０、１７４２を含む情報処理システム１７００の構成を示すブロック図である。なお、図１７において、図２と同様の構成要素には同じ参照番号を付して、重複する説明は省略する。
【０１４６】
情報処理システム１７００は、記憶制御部を有しないホストコンピュータ１７１０と、キャッシュ２２１を有する独立した記憶制御部１７２０と、キャッシュ２２１を有する記憶制御部１７４２を含む記憶媒体１７４０と、がネットワーク２５０を介して接続されている。
【０１４７】
本実施形態によれば、第２乃至第４実施形態のようにホストコンピュータによる処理に限定されず、キャッシュをホストコンピュータ外で制御することで、ホストコンピュータの負荷を減らし記憶媒体へのアクセス性能の向上を図ることができる。
【０１４８】
［他の実施形態］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステムまたは装置も、本発明の範疇に含まれる。
【０１４９】
また、本発明は、複数の機器から構成されるシステムに適用されてもよいし、単体の装置に適用されてもよい。さらに、本発明は、実施形態の機能を実現する情報処理プログラムが、システムあるいは装置に直接あるいは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされるプログラム、あるいはそのプログラムを格納した媒体、そのプログラムをダウンロードさせるＷＷＷ(World Wide Web)サーバも、本発明の範疇に含まれる。特に、少なくとも、上述した実施形態に含まれる処理ステップをコンピュータに実行させるプログラムを格納した非一時的コンピュータ可読媒体（non-transitory computer readable medium）は本発明の範疇に含まれる。
【図１】
2019168733.tif 000003
【図２】
2019168733.tif 000004
【図３】
2019168733.tif 000005
【図４】
2019168733.tif 000006
【図５】
2019168733.tif 000007
【図６】
2019168733.tif 000008
【図７】
2019168733.tif 000009
【図８】
2019168733.tif 000010
【図９】
2019168733.tif 000011
【図１０】
2019168733.tif 000012
【図１１Ａ】
2019168733.tif 000013
【図１１Ｂ】
2019168733.tif 000014
【図１２】
2019168733.tif 000015
【図１３】
2019168733.tif 000016
【図１４】
2019168733.tif 000017
【図１５】
2019168733.tif 000018
【図１６】
2019168733.tif 000019
【図１７】
2019168733.tif 000020