(57)【要約】  対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することを課題とする。例えば、図１の（１）に例示するように、エントリが使用される度に、そのエントリのＩＤを順次記憶してＬＲＵ情報を構成し、一番左側の位置に格納されている格納データ０が最終使用時の最も古い（つまり、ＬＲＵ）エントリのＩＤを示し、実施例１に係るＬＲＵ制御装置は、ＬＲＵ情報を参照して、ＬＲＵ情報の中から最終使用時の最も古いエントリのＩＤである格納データ０に基づいて、格納データ０に対応するエントリ（例えば、エントリ１）をＬＲＵ制御する候補として選択する。
2007097028.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御装置において、
前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手段と、
前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手段により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて前記ＬＲＵ情報を更新するＬＲＵ情報更新手段と、
前記ＬＲＵ情報記憶手段により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手段と、
を備えたことを特徴とするＬＲＵ制御装置。
【請求項２】
ＬＲＵ制御する候補として選択可能であるか否かを示す情報を前記複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶する選択可否情報記憶手段をさらに備え、
前記ＬＲＵ制御候補選択手段は、前記選択可否情報記憶手段に記憶されている選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択することを特徴とする請求項１に記載のＬＲＵ制御装置。
【請求項３】
前記ＬＲＵ候補選択手段は、前記ＬＲＵ情報記憶手段により記憶されている前記各識別情報の全てが、前記選択可否情報記憶手段おいて選択不可能であることを示す情報にそれぞれ対応付けられている場合には、当該選択可否情報記憶手段において選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択することを特徴とする請求項１に記載のＬＲＵ制御装置。
【請求項４】
前記ＬＲＵ情報更新手段は、ＬＲＵ情報記憶手段により記憶されている前記各識別情報の全てが、前記選択可否情報記憶手段において選択不可能であることを示す情報にそれぞれ対応付けられている場合には、選択可能なエントリの識別情報で前記ＬＲＵ情報を更新することを特徴とする請求項１に記載のＬＲＵ制御装置。
【請求項５】
記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択する方法をコンピュータに実行させるＬＲＵ制御プログラムにおいて、
前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手順と、
前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手順により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて更新するＬＲＵ情報更新手順と、
前記ＬＲＵ情報記憶手順により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手順と、
をコンピュータに実行させることを特徴とするＬＲＵ制御プログラム。
【請求項６】
記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御方法において、
前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶工程と、
前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶工程により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて前記ＬＲＵ情報を更新するＬＲＵ情報更新工程と、
前記ＬＲＵ情報記憶工程により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択工程と、
を含んだことを特徴とするＬＲＵ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御装置、ＬＲＵ制御方法およびＬＲＵ制御プログラムに関する。
【背景技術】
【０００２】
従来より、所定のプログラムに従って演算処理を行う装置（例えば、汎用コンピュータやスパーコンピュータ、サーバなど）内の記憶装置（例えば、メインメモリやキャッシュなど）に採用されるリプレースメントアルゴリズムの一つとしてＬＲＵ制御方式がある（例えば、特許文献１参照）。具体的には、このＬＲＵ制御方式は、メインメモリから追い出されたデータが再びＣＰＵ（Central  Processing  Unit）において参照される場合において、入出力頻度の増加による処理効率の低下を避けるため、メインメモリにおいて各データがどのように参照されたかという履歴を取っておき、その履歴に基づいて、今後最もＣＰＵによって参照されそうも無いデータをメインメモリから追い出すことを特徴とする方式である。【０００３】
例えば、図１５および図１６を用いて、対象エントリ（ウェイ）数が４である場合の従来のＬＲＵ制御を簡単に説明すると、図１５は、エントリ数４のＬＲＵ制御に必要な６ビットの意味付けを示しており（各エントリをＥｎｔｒｙ０，１，２，３で示し、Ａ＞ＢはＡが最近使用されたことを示す）、図１６は、ＬＲＵ制御の論理を示す（Ｐ＿は正極性、Ｍ＿は負極性を示し、〜はＮＯＴ、＆はＡＮＤ、｜はＯＲを示し、例えば、ＬＲＵビット０の信号をＰ＿ＬＲＵ［０］と示し、エントリ０が使用選択不可である信号をＰ＿ＤＥＬＥＴＥ＿ＥＮＴＲＹ[０]と示す）ものであり、図１５に示す６ビットからなる情報の信号を受け付けて、図１６に示す論理にあてはめることにより、どのエントリが最近最も使用されていなかったかを求めることができる。【０００４】
また、ＬＲＵ制御を多段階化した疑似ＬＲＵ制御では、例えば、図１７（ｂ）に示すように、上記のＬＲＵ制御に比べて、エントリ数を１６にした場合の必要ビット数を抑えることはできる。【０００５】
【特許文献１】特開平９−２８８６１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記した従来の技術は、以下に説明するように、ＬＲＵ制御の対象となるエントリ数が多い場合に現実的な制御が難しいという問題点があり、また、ＬＲＵ制御を多段階化した疑似ＬＲＵ制御では、そのＬＲＵ制御の結果に偏りが生じる場合があるという問題点があった。【０００７】
すなわち、この従来のＬＲＵ制御では、対象エントリ数を４程度にしてＬＲＵ制御を行うのが現実的であり、仮に、対象エントリ数を１６にした場合には必要ビット数が１２０となるので回路実装が複雑となり、現実的な制御が難しいという問題点があった。【０００８】
また、ＬＲＵ制御を多段階化した疑似ＬＲＵ制御では、図１２に示すような外部からのエントリ使用選択不可信号による制御を行った場合、使用選択不可エントリの指定の仕方によっては、ＬＲＵ制御の結果があるエントリ（あるいは下位のエントリのグループ）に偏ってしまう懸念が発生するという問題点があった。【０００９】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、対象エントリ数が多い場合のＬＲＵ制御の必要ビット数を抑えるとともに、完全なＬＲＵ制御を実現でき、使用不可エントリの選択の仕方によってＬＲＵ制御の結果に偏りが生じること防止することが可能なＬＲＵ制御装置、ＬＲＵ制御方法およびＬＲＵ制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、請求項１に係る発明は、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御装置において、前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手段と、前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手段により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて更新するＬＲＵ情報更新手段と、前記ＬＲＵ情報記憶手段により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手段と、を備えたことを特徴とする。【００１１】
また、請求項２に係る発明は、上記の発明において、ＬＲＵ制御する候補として選択可能であるか否かを示す情報を前記複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶する選択可否情報記憶手段をさらに備え、前記ＬＲＵ制御候補選択手段は、前記選択可否情報記憶手段に記憶されている選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択することを特徴とする。【００１２】
また、請求項３に係る発明は、上記の発明において、前記ＬＲＵ候補選択手段は、前記ＬＲＵ情報記憶手段により記憶されている前記識別情報の全てが、前記選択可否情報記憶手段おいて選択不可能であることを示す情報にそれぞれ対応付けられている場合には、当該選択可否情報記憶手段において選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択することを特徴とする。【００１３】
また、請求項４に係る発明は、上記の発明において、前記ＬＲＵ情報更新手段は、ＬＲＵ情報記憶手段により記憶されている前記各識別情報の全てが、前記選択可否情報記憶手段において選択不可能であることを示す情報にそれぞれ対応付けられている場合には、選択可能なエントリの識別情報で前記ＬＲＵ情報を更新することを特徴とする。【００１４】
また、請求項５に係る発明は、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択する方法をコンピュータに実行させるＬＲＵ制御プログラムにおいて、前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手順と、前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手順により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて更新するＬＲＵ情報更新手順と、前記ＬＲＵ情報記憶手順により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手順と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１５】
請求項１または５の発明によれば、複数のエントリのそれぞれを識別する識別情報（例えば、エントリごとに一意に付与されたＩＤなど）を最終使用時が古い順に並べてＬＲＵ情報として記憶し、複数のエントリの中のいずれかのエントリが使用された場合に、各識別情報の中から当該使用されたエントリの識別情報を取り出すとともに最後尾に移動させてＬＲＵ情報を更新し、記憶しているＬＲＵ情報を参照して、複数のエントリの中からＬＲＵ制御する候補を選択するので、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することが可能となる。【００１６】
また、請求項２の発明によれば、このＬＲＵ制御装置は、ＬＲＵ制御する候補として選択可能であるか否かを示す情報を複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶し、記憶している選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択するので、使用不可のエントリの選択の仕方によってＬＲＵ制御の結果に偏りが生じることを防止することができ、完全なＬＲＵ制御を実現することが可能となる。【００１７】
また、請求項３の発明によれば、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択するので、例えば、フリップフロップやラッチを用いてＬＲＵ情報を構成した場合と比較して、ＲＡＭを用いてＬＲＵ情報を構成した場合に発生しやすいＬＲＵ情報の参照エラーに対処することができ、デバイスにとらわれない完全なＬＲＵ制御が可能となる。【００１８】
また、請求項４の発明によれば、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能なエントリの識別情報（例えば、初期パターン）でＬＲＵ情報を更新するので、ＬＲＵ情報を正しく更新することで次回読み出したときにエントリを選択できない事態を防止することができ、完全なＬＲＵ制御が可能となる。
【図面の簡単な説明】
【００１９】
【図１】図１は、実施例１に係るＬＲＵ制御装置の概要を説明するための図である。
【図２】図２は、実施例１に係るＬＲＵ制御装置の構成を示すブロック図である。
【図３】図３は、１６エントリＬＲＵの構成例を示す図である。
【図４】図４は、任意のインデックスのＬＲＵ情報の例を示す図である。
【図５】図５は、更新によるＬＲＵ情報の遷移を示す図である。
【図６】図６は、実施例１に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。
【図７】図７は、実施例２に係るＬＲＵ制御装置の構成を示すブロック図である。
【図８】図８は、選択可否情報の例を示す図である。
【図９】図９は、実施例２に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。
【図１０】図１０は、実施例３に係るＬＲＵ制御装置の構成を示すブロック図である。
【図１１】図１１は、エラーしたＬＲＵ情報の例を示す図である。
【図１２】図１２は、エラーしたＬＲＵ情報の例を示す図である。
【図１３】図１３は、ＬＲＵ情報更新部で生成される整合情報の例を示す図である。
【図１４】図１４は、ＬＲＵ制御プログラムを実行するコンピュータを示す図である。
【図１５】図１５は、従来技術の４エントリＬＲＵの例を示す図である。
【図１６】図１６は、従来技術によるＬＲＵエントリの求め方を示す図である。
【図１７】図１７は、１６エントリの２段疑似ＬＲＵの例を示す図である。
【符号の説明】
【００２０】
１０  ＬＲＵ制御装置
１１  入出力制御部
１２  記憶部
１２ａ  ＬＲＵ情報記憶部
１３  制御部
１３ａ  ＬＲＵ情報格納制御部
１３ｂ  ＬＲＵ候補選択部
１３ｃ  ＬＲＵ情報更新部
２０  ＬＲＵ制御装置
２１  入出力制御部
２２  記憶部
２２ａ  ＬＲＵ情報記憶部
２２ｂ  選択可否情報記憶部
２３  制御部
２３ａ  ＬＲＵ情報格納制御部
２３ｂ  ＬＲＵ候補選択部
２３ｃ  ＬＲＵ候補予備選択部
２３ｄ  ＬＲＵ情報更新部
３０  ＬＲＵ制御装置
３１  入出力制御部
３２  記憶部
３２ａ  ＬＲＵ情報記憶部
３２ｂ  選択可否情報記憶部
３２ｃ  更新情報記憶部
３３  制御部
３３ａ  ＬＲＵ情報格納制御部
３３ｂ  ＬＲＵ候補選択部
３３ｃ  ＬＲＵ候補予備選択部
３３ｄ  ＬＲＵ情報更新部
４０  コンピュータ
４１  入出力制御部
４２  ＨＤＤ（Hard  disk  drive）
４３  ＲＡＭ（Random  access  memory）
４４  ＲＯＭ（Read  only  memory）
４５  ＣＰＵ（Central  processing  unit）
５０  バス
【発明を実施するための最良の形態】
【００２１】
以下に添付図面を参照して、この発明に係るＬＲＵ制御装置、ＬＲＵ制御方法およびＬＲＵ制御プログラムの実施例を詳細に説明する。なお、以下では、実施例１に係るＬＲＵ制御装置を説明した後に、この発明に含まれる他の実施例を説明する。
【実施例１】
【００２２】
以下の実施例１では、実施例１に係るＬＲＵ制御装置の概要および特徴、ＬＲＵ制御装置の構成および処理の流れを順に説明し、最後に実施例１による効果を説明する。【００２３】
［概要および特徴（実施例１）］
まず最初に、図１を用いて、実施例１に係るＬＲＵ装置の概要および特徴を説明する。図１は、実施例１に係るＬＲＵ制御装置の概要を説明するための図である。同図に示すように、実施例１に係るＬＲＵ制御装置は、記憶装置（例えば、メインメモリやキャッシュメモリ、ＲＡＭなど）に備えられた複数のエントリからＬＲＵ制御する（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ、つまり、最終使用時の最も古いエントリ内のデータを追い出す）エントリを選択することを概要とするが、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現する点に主たる特徴がある。【００２４】
この主たる特徴について具体的に説明すると、実施例１に係るＬＲＵ制御装置は、複数のエントリのそれぞれを識別する識別情報（例えば、エントリごとに一意に付与されたＩＤなど）を記憶している。この識別情報は、例えば、図１の（１）に例示するように、エントリの識別情報（例えば、ＩＤ）を最終使用時が古い順に並べて記憶することでＬＲＵ情報を構成し、一番左側の位置に格納されている格納データ０が最終使用時の最も古い（つまり、ＬＲＵ）エントリのＩＤを示し、一番右側の位置に格納されている格納データＮが最終使用時の最も新しい（つまり、ＭＲＵ：Ｍｏｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）エントリのＩＤを示す。【００２５】
そして、実施例１に係るＬＲＵ制御装置は、ＬＲＵ情報を参照して、ＬＲＵ情報の中から最終使用時の最も古いエントリのＩＤである格納データ０に基づいて、格納データ０に対応するエントリ（例えば、エントリ１）をＬＲＵ制御する候補として選択する。【００２６】
また、実施例１に係るＬＲＵ制御装置は、エントリの使用に応じてＬＲＵ情報を更新することで、最終使用時の最も古いエントリを常に把握できるようにＬＲＵ情報を構成する。具体的には、例えば、アクセス要求に対応するデータを格納したエントリの識別情報である格納データ１がＬＲＵ情報の中に存在し、ＬＲＵ情報に更新の必要がある場合には、実施例１に係るＬＲＵ制御装置は、まず、ＬＲＵ情報の中から格納データ１を取り出す（図１の（２）参照）。次に、実施例１に係るＬＲＵ制御装置は、格納データ１よりも最終使用時の新しいエントリのＩＤを示す格納データ２から格納データＮまでを左にシフトするとともに、シフトによって生成されたＭＲＵの位置に格納データ１を移動させる（図１の（３）参照）。以上で、実施例１に係るＬＲＵ制御装置は、ＬＲＵ情報の更新を完了する（図１の（４）参照）。【００２７】
このようなことから、実施例１に係るＬＲＵ制御装置は、上述した主たる特徴の如く、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することが可能となる。【００２８】
［ＬＲＵ制御装置の構成（実施例１）］
次に、図２を用いて、実施例１に係るＬＲＵ制御装置の構成を説明する。図２は、実施例１に係るＬＲＵ制御装置の構成を示すブロック図である。なお、同図においては、実施例１に係るＬＲＵ制御装置を実現するうえで必要となる処理部のみを示しており、その他の処理部の記載については省略している。【００２９】
同図に示すように、実施例１に係るＬＲＵ制御装置１０は、入出力制御部１１と、記憶部１２と、制御部１３とから構成される。このうち、入出力制御部１１は、各種の情報の入出力を制御する入出力制御手段であり、例えば、使用エントリ（更新にかかるエントリ）の識別情報（例えば、ＩＤ）の入力や、後述するＬＲＵ制御選択部１３ｂによりＬＲＵ制御候補として選択されたエントリの識別情報（例えば、ＩＤ）の外部モジュールへの出力を制御する。【００３０】
記憶部１２は、制御部１３による各種処理に必要なデータおよびプログラムを格納する格納手段（記憶手段）であり、特に本発明に密接に関連するものとしては、ＬＲＵ情報記憶部１２ａを備える。このＬＲＵ情報記憶部１２ａは、例えば、１６のエントリでＬＲＵ情報を構成する場合には、図３に例示するように、ＬＲＵ制御の候補となる１６の対象エントリの識別情報（例えば、ＩＤ）を最終使用時の古い順に１番目候補から１６番目候補まで４ビットでエンコード（例えば、００００〜１１１１）した状態で記憶して構成される。【００３１】
制御部１３は、所定の制御プログラム、各種の処理手順などを規定したプログラムおよび所要データを格納するための内部メモリを有し、これらによって種々の処理を実行する処理部であり、特に本発明に密接に関連するものとしては、ＬＲＵ情報格納制御部１３ａと、ＬＲＵ候補選択部１３ｂと、ＬＲＵ情報更新部１３ｃとを備える。【００３２】
このうち、ＬＲＵ情報格納制御部１３ａは、ＬＲＵ情報記憶部１２ａにＬＲＵ情報を格納する制御部であり、具体的には、例えば、入出力制御部１１から受け付けた使用エントリ（更新にかかるエントリ）のの識別情報（例えば、ＩＤ）をＬＲＵ情報記憶部１２ａに備えられた所定の格納位置に格納する。【００３３】
ＬＲＵ候補選択部１３ｂは、ＬＲＵ制御する候補を選択する処理部であり、具体的には、ＬＲＵ情報記憶部１２ａから読み出したＬＲＵ情報の中に、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）が存在しない場合には、最終使用時の最も古いエントリの識別情報（例えば、ＩＤ）に対応するエントリをＬＲＵ制御する候補として選択する。そして、ＬＲＵ候補選択部１３ｂは、ＬＲＵ制御する候補として選択したエントリの識別情報（例えば、ＩＤ）を、入出力制御部１１を介して、例えば、外部モジュールなどに出力する。【００３４】
ＬＲＵ情報更新部１３ｃは、ＬＲＵ情報記憶部１２ａに記憶されているＬＲＵ情報を更新する処理部であり、具体的には、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にある場合には、ＬＲＵ情報の更新を行う。例えば、図５に例示するように、アクセス要求に対応するデータを格納したエントリ２の識別情報がＬＲＵ情報の中に存在する場合には、ＬＲＵ情報記憶部１２ａに記憶されているＬＲＵ情報の任意のインデックス（例えば、Ｚ）における２ｎｄの格納場所からエントリ２の識別情報（例えば、０からＦまでの１６進数で表わされている情報、図４参照）を取り出して、３ｒｄから１６ｔｈの格納場所に格納されているデータ（例えば、各エントリのＩＤ）を順次左側へシフトし、空いた１６ｔｈの格納場所へ２ｎｄの格納場所から取り出したエントリ２に対応するエントリの識別情報を格納してＬＲＵ情報を更新する（図５の（ａ）および（ｂ）参照）。【００３５】
［ＬＲＵ制御装置による処理（実施例１）］
次に、図６を用いて、実施例１に係るＬＲＵ制御装置による処理を説明する。図６は、実施例１に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。同図に示すように、所定のデータに対してユーザなどからアクセス要求があると（ステップＳ６０１肯定）、ＬＲＵ制御装置１０のＬＲＵ候補選択部１３ｂは、ＬＲＵ情報記憶部１２ａからＬＲＵ情報を読み出す（ステップＳ６０２）。【００３６】
そして、ＬＲＵ情報に更新の必要がある場合には（Ｓ６０３否定）、ＬＲＵ情報更新部１３ｃは、ＬＲＵ情報の更新を行う（ステップＳ６０４）。具体的には、ＬＲＵ情報更新部１３ｃは、例えば、アクセス要求に対応するデータを格納したエントリ２の識別情報（例えば、ＩＤ）がＬＲＵ情報の中にある場合には、ＬＲＵ情報記憶部１２ａに記憶されているＬＲＵ情報の任意のインデックス（例えば、Ｚ）における２ｎｄの格納場所からエントリ２に対応するエントリの識別情報（例えば、０からＦまでの１６進数で表わされている情報、図４参照）を取り出して、３ｒｄから１６ｔｈの格納場所に格納されているデータ（例えば、各エントリのＩＤ）を順次左側へシフトし、空いた１６ｔｈの格納場所へ２ｎｄの格納場所から取り出したエントリ２に対応するエントリの識別情報を格納してＬＲＵ情報を更新する（図５の（ａ）および（ｂ）参照）。【００３７】
一方、ＬＲＵ情報に更新の必要がない場合（すなわち、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にない場合）には（Ｓ６０３否定）、ＬＲＵ候補選択部１３ｂは、ＬＲＵ情報の中から最終使用時の最も古いエントリをＬＲＵ制御する候補として選択する（ステップＳ６０５）。続いて、ＬＲＵ候補選択部１３ｂは、ＬＲＵ制御する候補として選択したエントリの識別情報を、入出力制御部１１を介して、例えば、外部モジュールなどに出力する（ステップＳ６０６）。【００３８】
［実施例１の効果］
上述してきたように、実施例１によれば、このＬＲＵ制御装置は、複数のエントリのそれぞれを識別する識別情報（例えば、エントリごとに一意に付与されたＩＤなど）を最終使用時が古い順に並べてＬＲＵ情報として記憶し、複数のエントリの中のいずれかのエントリが使用された場合に、各識別情報の中から当該使用されたエントリの識別情報を取り出すとともに最後尾に移動させてＬＲＵ情報を更新し、記憶しているＬＲＵ情報を参照して、複数のエントリの中からＬＲＵ制御する候補を選択するので、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することが可能となる。
【実施例２】
【００３９】
ところで、上記の実施例１では、ＬＲＵ情報を参照して、ＬＲＵ制御する候補を選択する場合を説明したが、本発明はこれに限定されるものではなく、ＬＲＵ制御する候補として選択可能であるか否かの情報を複数のエントリにそれぞれ対応付けて記憶し、ＬＲＵ情報の中から選択可能なエントリをＬＲＵ制御する候補として選択するようにしてもよい。そこで、以下では、ＬＲＵ情報の中から選択可能なエントリをＬＲＵ制御する候補として選択する場合を実施例２として説明する。【００４０】
なお、以下では、実施例２に係るＬＲＵ制御装置の構成および処理の流れを説明した後に、実施例２による効果を説明する。【００４１】
［ＬＲＵ制御装置の構成（実施例２）］
まず最初に、図７を用いて、実施例２に係るＬＲＵ制御装置の構成を説明する。なお、実施例２に係るＬＲＵ制御装置は、実施例１に係るＬＲＵ制御装置と基本的に同様の構成であるが、以下に説明する点が異なる。【００４２】
ＬＲＵ制御装置２０の選択可否情報記憶部２２ｂは、ＬＲＵ情報記憶部２２ａに記憶されているＬＲＵ情報の中からＬＲＵ制御する候補として選択可能であるか否かを示す情報を記憶する記憶手段であり、例えば、図８に例示するように、選択可能であるとする情報（例えば、０）や選択不可能であるとする情報（例えば、１）を各エントリＩＤ（例えば、０からＦの１６進数）にそれぞれ対応付けて記憶して構成される。【００４３】
ＬＲＵ制御装置２０のＬＲＵ候補予備選択部２３ｃは、ＬＲＵ候補選択部２３ｂにより選択されたＬＲＵ制御の候補が選択可能であるか否かを判別する処理部であり、具体的には、選択可否情報記憶部２２ｂから選択可否情報を読み出して、ＬＲＵ候補選択部２３ｂにより選択されたエントリがＬＲＵ制御の候補として選択可能であるかどうか判定し、判定結果をＬＲＵ候補選択部２３ｂに対して出力する。【００４４】
ＬＲＵ制御装置２０のＬＲＵ候補選択部２３ｂは、ＬＲＵ候補予備選択部２３ｃから選択可能である旨の判定結果を受け付けた場合には、選択したエントリをＬＲＵ制御の候補として最終的に選択する。一方、選択されたエントリが選択不可能である旨の判定結果を受け付けた場合には、ＬＲＵ候補選択部２３ｂは、読み出したＬＲＵ情報の中から次候補となるエントリを再選択する。具体的には、例えば、図４に示す１ｓｔの位置に格納されたエントリＣが選択不可能である場合には、２ｎｄの位置に格納されたエントリ２をＬＲＵ制御する次候補として選択する。【００４５】
［ＬＲＵ制御装置の処理（実施例２）］
次に、図９を用いて、実施例２に係るＬＲＵ制御装置の処理を説明する。図９は、実施例２に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。同図に示すように、所定のデータに対してユーザなどからリードアクセス要求があると（ステップＳ９０１肯定）、ＬＲＵ制御装置２０のＬＲＵ候補選択部２３ｂは、ＬＲＵ情報記憶部２２ａからＬＲＵ情報を読み出す（ステップＳ９０２）。【００４６】
そして、ＬＲＵ情報に更新がある場合（すなわち、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にある場合）には（Ｓ９０３）、ＬＲＵ情報更新部１３ｃは、上記の実施例１において説明したのと同様に、ＬＲＵ情報の更新を行う（ステップＳ９０４）。【００４７】
一方、ＬＲＵ情報に更新がない場合（すなわち、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にない場合）には（Ｓ９０３否定）、ＬＲＵ候補選択部１３ｂは、ＬＲＵ情報の中から最終使用時の最も古いエントリをＬＲＵ制御する候補として選択する（ステップＳ９０５）。【００４８】
続いて、ＬＲＵ候補予備選択部２３ｃは選択可否情報を読み出す（ステップＳ９０６）。選択可否情報の読み出し後、ＬＲＵ候補予備選択部２３ｃは、ＬＲＵ候補選択部２３ｂにより選択されたエントリがＬＲＵ制御の候補として選択可能であるか否かを判定する（ステップＳ９０７）。判定の結果、その候補が選択可能である場合には（ステップＳ９０７肯定）、ＬＲＵ候補選択部２３ｂは、選択したエントリをＬＲＵ制御の候補として最終的に選択する。そして、ＬＲＵ候補選択部２３ｂは、ＬＲＵ制御する候補として最終的に選択したエントリを、入出力制御部１１を介して、例えば、外部モジュールなどに出力する（ステップＳ９０６）。【００４９】
ここで、ステップＳ９０７の説明に戻ると、ＬＲＵ候補予備選択部２３ｃによる判定の結果、ＬＲＵ候補選択部２３ｂにより選択されたエントリがＬＲＵ制御の候補として選択不可能である場合には（ステップＳ９０７否定）、ＬＲＵ候補が決定されるまで上述したステップＳ９０５からステップＳ９０７に示す処理を繰り返し行う。【００５０】
［実施例２の効果］
上述してきたように、実施例２によれば、このＬＲＵ制御装置は、ＬＲＵ制御する候補として選択可能であるか否かを示す情報を複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶し、記憶している選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択するので、使用不可のエントリの選択の仕方によってＬＲＵ制御の結果に偏りが生じることを防止することができ、完全なＬＲＵ制御を実現することが可能となる。【００５１】
また、上記の実施例２において、ＬＲＵ候補選択部２３ｂによってＬＲＵ情報記憶部２２ａから読み出されたＬＲＵ情報に参照エラーが発生（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生）した場合には、ＬＲＵ候補予備選択部２３ｃは、選択可否情報の中から選択可能なエントリのいずれを選択するようにしてもよい。【００５２】
例えば、図１２に示すように、ＬＲＵ候補選択部２３ｂによってＬＲＵ情報記憶部２２ａから読み出された情報に参照エラーが発生（一意に付与されているはずのエントリＩＤＣ、６、Ｆなどが重なって読み出されている）して、例えば、図８に示す選択可否情報を参照して、読み出したＬＲＵ情報の中のエントリがＬＲＵ制御する候補として全て選択不可能である場合には、ＬＲＵ候補予備選択部２３ｃは、選択可否情報の中から選択可能なエントリ（例えば、２、３，４など）のいずれかを選択する。【００５３】
これにより、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択するので、例えば、フリップフロップやラッチを用いてＬＲＵ情報を構成した場合と比較して、ＲＡＭを用いてＬＲＵ情報を構成した場合に発生しやすいＬＲＵ情報の参照エラーに対処することができ、デバイスにとらわれない完全なＬＲＵ制御が可能となる。
【実施例３】
【００５４】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。【００５５】
（１）ＬＲＵ情報の更新
上記の実施例２において、ＬＲＵ候補選択部２３ｂによってＬＲＵ情報記憶部２２ａから読み出されたＬＲＵ情報に参照エラーが発生（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生）した場合には、ＬＲＵ候補予備選択部２３ｃは、選択可否情報の中から選択可能なエントリのいずれを選択する場合を説明したが、本発明はこれに限定されるものではなく、ＬＲＵ情報内のエントリの識別情報（例えば、ＩＤ）を選択可能なエントリの識別情報で更新するようにしてもよい。そこで、以下では、図１０、図１１および図１３を用いて、ＬＲＵ情報内のエントリの識別情報を更新する場合を説明する。【００５６】
図１０に示すように、ＬＲＵ制御装置３０は、上記の実施例において説明したＬＲＵ制御装置と基本的には同様の構成であるが、以下に説明する更新情報記憶部３２ｃ、ＬＲＵ候補選択部３３ｂおよびＬＲＵ情報更新部３３ｄが異なる。【００５７】
ＬＲＵ制御装置３０の更新情報記憶部３２ｃは、ＬＲＵ情報更新部３３ｄにおいて利用される更新情報を記憶する手段であり、例えば、参照エラーが発生したＬＲＵ情報内のデータを更新するための情報として、選択可能なエントリを含んだ情報（例えば、全てのエントリＩＤを含んだ初期パタンなどの整合情報）を記憶して構成される。【００５８】
ＬＲＵ制御装置３０のＬＲＵ候補選択部３３ｂは、ＬＲＵ情報記憶部３２ａから読み出したＬＲＵ情報の中に全てのエントリＩＤが含まれていない（例えば、図１１参照）場合には、参照エラーとして、ＬＲＵ情報更新部３３ｄにその旨の信号を出力する。【００５９】
ＬＲＵ制御装置のＬＲＵ情報更新部３３ｃは、ＬＲＵ候補選択部３３ｂから参照エラーである旨の信号を受け付けると、更新情報記憶部３２ｃから更新情報を読み出し、例えば、エントリ７の使用にかかるＬＲＵ情報の更新がある場合には、その更新を反映した形で整合情報を生成し（図１３参照）、ＬＲＵ情報記憶部３２ａに書き込むことでＬＲＵ情報内のデータを更新する。【００６０】
これにより、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能なエントリの識別情報（例えば、初期パターン）でＬＲＵ情報を更新するので、ＬＲＵ情報を正しく更新することで次回読み出したときにエントリを選択できない事態を防止することができ、完全なＬＲＵ制御が可能となる。【００６１】
（２）装置構成等
また、図２、図７および図１０示した各ＬＲＵ制御装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各ＬＲＵ制御装置の分散・統合の具体的形態は図示のものに限られず、例えば、ＬＲＵ制御装置１０のＬＲＵ情報格納制御部１３ａとＬＲＵ候補選択部１３ｂとを統合し、ＬＲＵ制御装置２０のＬＲＵ候補選択部２３ｂとＬＲＵ候補予備選択部２３ｃとを統合し、ＬＲＵ制御装置３０のＬＲＵ情報記憶部３２ａと選択可否情報記憶部３２ｂとを統合するなど、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各ＬＲＵ制御装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。【００６２】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。【００６３】
（３）ＬＲＵ制御プログラム
ところで、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することができる。そこで、以下では、図１４を用いて、上記の実施例１で説明したＬＲＵ制御装置１０の処理（ＬＲＵ制御処理）と同様の機能を有するＬＲＵ制御プログラムを実行するコンピュータの一例を説明する。図１４は、ＬＲＵ制御プログラムを実行するコンピュータを示す図である。【００６４】
同図に示すように、ＬＲＵ制御装置であるコンピュータ４０は、入出力制御部４１と、ＨＤＤ４２と、ＲＡＭ４３と、ＲＯＭ４４と、ＣＰＵ４５とを所定のバス５０で接続して構成される。ここで、入出力制御部４１は、図２に示した入出力制御部１１に対応する。【００６５】
まず、ＲＯＭ４４には、上記の実施例１に示したＬＲＵ制御装置１０と同様の機能を発揮するＬＲＵ制御プログラム、つまり、図１４に示すように、ＬＲＵ情報格納制御プログラム４４ａ、ＬＲＵ候補選択プログラム４４ｂおよびＬＲＵ情報更新プログラム４４ｃがあらかじめ記憶されている。なお、これらのプログラム４４ａ、４４ｂおよび４４ｃについては、図２に示したＬＲＵ制御装置１０の各構成要素と同様、適宜統合または分散してもよい。【００６６】
そして、ＣＰＵ４５が、これらのプログラム４４ａ、４４ｂおよび４４ｃをＲＯＭ４４から読み出して実行することで、図１４に示すように、各プログラム４４ａ、４４ｂおよび４４ｃは、ＬＲＵ情報格納制御プロセス４５ａ、ＬＲＵ候補選択プロセス４５ｂおよびＬＲＵ情報更新プロセス４５ｃとして機能するようになる。なお、各プロセス４５ａ、４５ｂおよび４５ｃは、図２に示したＬＲＵ制御装置１０のＬＲＵ情報格納制御部１３ａ、ＬＲＵ候補選択部１３ｂおよびＬＲＵ情報更新部１３ｃにそれぞれ対応する。【００６７】
また、ＨＤＤ４２には、図１４に示すように、ＬＲＵ情報テーブル４２ａが設けられる。このＬＲＵ情報テーブル４２ａは、図２に示したＬＲＵ制御装置１０のＬＲＵ情報記憶部１２ａに対応する。そして、ＣＰＵ４５は、ＬＲＵ情報テーブル４２ａからＬＲＵ情報データ４３ａを読み出してＲＡＭ４３に格納し、ＲＡＭ４３に格納されたＬＲＵ情報データ４３ａに基づいてＬＲＵ制御処理を実行する。【００６８】
なお、上記した各プログラム４４ａ、４４ｂおよび４４ｃは、必ずしも最初からＲＯＭ４４に記憶させておく必要はなく、例えば、コンピュータ４０に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータ４０の内外に備えられるＨＤＤなどの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４０に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ４０がこれらから各プログラムを読み出して実行するようにしてもよい。
【産業上の利用可能性】
【００６９】
以上のように、本発明に係るＬＲＵ制御装置、ＬＲＵ制御方法およびＬＲＵ制御プログラムは、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択する場合に有用であり、特に、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することに適する。
【図１】
2007097028.tif 000003
【図２】
2007097028.tif 000004
【図３】
2007097028.tif 000005
【図４】
2007097028.tif 000006
【図５】
2007097028.tif 000007
【図６】
2007097028.tif 000008
【図７】
2007097028.tif 000009
【図８】
2007097028.tif 000010
【図９】
2007097028.tif 000011
【図１０】
2007097028.tif 000012
【図１１】
2007097028.tif 000013
【図１２】
2007097028.tif 000014
【図１３】
2007097028.tif 000015
【図１４】
2007097028.tif 000016
【図１５】
2007097028.tif 000017
【図１６】
2007097028.tif 000018
【図１７】
2007097028.tif 000019
【手続補正書】
【提出日】平成20年5月1日(2008.5.1)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御装置において、
前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手段と、
前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手段により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて前記ＬＲＵ情報を更新するＬＲＵ情報更新手段と、
前記ＬＲＵ情報記憶手段により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手段と、
を備えたことを特徴とするＬＲＵ制御装置。
【請求項２】
ＬＲＵ制御する候補として選択可能であるか否かを示す情報を前記複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶する選択可否情報記憶手段をさらに備え、
前記ＬＲＵ制御候補選択手段は、前記選択可否情報記憶手段に記憶されている選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択することを特徴とする請求項１に記載のＬＲＵ制御装置。
【請求項３】
前記ＬＲＵ候補選択手段は、前記ＬＲＵ情報記憶手段により記憶されている前記各識別情報の全てが、前記選択可否情報記憶手段おいて選択不可能であることを示す情報にそれぞれ対応付けられている場合には、当該選択可否情報記憶手段において選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択することを特徴とする請求項２に記載のＬＲＵ制御装置。
【請求項４】
前記ＬＲＵ情報更新手段は、ＬＲＵ情報記憶手段により記憶されている前記各識別情報の全てが、前記選択可否情報記憶手段において選択不可能であることを示す情報にそれぞれ対応付けられている場合には、選択可能なエントリの識別情報で前記ＬＲＵ情報を更新することを特徴とする請求項２に記載のＬＲＵ制御装置。
【請求項５】
記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択する方法をコンピュータに実行させるＬＲＵ制御プログラムにおいて、
前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手順と、
前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手順により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて更新するＬＲＵ情報更新手順と、
前記ＬＲＵ情報記憶手順により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手順と、
をコンピュータに実行させることを特徴とするＬＲＵ制御プログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御装置およびＬＲＵ制御プログラムに関する。
【背景技術】
【０００２】
従来より、所定のプログラムに従って演算処理を行う装置（例えば、汎用コンピュータやスパーコンピュータ、サーバなど）内の記憶装置（例えば、メインメモリやキャッシュなど）に採用されるリプレースメントアルゴリズムの一つとしてＬＲＵ制御方式がある（例えば、特許文献１参照）。具体的には、このＬＲＵ制御方式は、メインメモリから追い出されたデータが再びＣＰＵ（Central  Processing  Unit）において参照される場合において、入出力頻度の増加による処理効率の低下を避けるため、メインメモリにおいて各データがどのように参照されたかという履歴を取っておき、その履歴に基づいて、今後最もＣＰＵによって参照されそうも無いデータをメインメモリから追い出すことを特徴とする方式である。
【０００３】
例えば、図１５および図１６を用いて、対象エントリ（ウェイ）数が４である場合の従来のＬＲＵ制御を簡単に説明すると、図１５は、エントリ数４のＬＲＵ制御に必要な６ビットの意味付けを示しており（各エントリをＥｎｔｒｙ０，１，２，３で示し、Ａ＞ＢはＡが最近使用されたことを示す）、図１６は、ＬＲＵ制御の論理を示す（Ｐ＿は正極性、Ｍ＿は負極性を示し、〜はＮＯＴ、＆はＡＮＤ、｜はＯＲを示し、例えば、ＬＲＵビット０の信号をＰ＿ＬＲＵ［０］と示し、エントリ０が使用選択不可である信号をＰ＿ＤＥＬＥＴＥ＿ＥＮＴＲＹ[０]と示す）ものであり、図１５に示す６ビットからなる情報の信号を受け付けて、図１６に示す論理にあてはめることにより、どのエントリが最近最も使用されていなかったかを求めることができる。
【０００４】
また、ＬＲＵ制御を多段階化した疑似ＬＲＵ制御では、例えば、図１７（ｂ）に示すように、上記のＬＲＵ制御に比べて、エントリ数を１６にした場合の必要ビット数を抑えることはできる。
【０００５】
【特許文献１】特開平９−２８８６１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記した従来の技術は、以下に説明するように、ＬＲＵ制御の対象となるエントリ数が多い場合に現実的な制御が難しいという問題点があり、また、ＬＲＵ制御を多段階化した疑似ＬＲＵ制御では、そのＬＲＵ制御の結果に偏りが生じる場合があるという問題点があった。
【０００７】
すなわち、この従来のＬＲＵ制御では、対象エントリ数を４程度にしてＬＲＵ制御を行うのが現実的であり、仮に、対象エントリ数を１６にした場合には必要ビット数が１２０となるので回路実装が複雑となり、現実的な制御が難しいという問題点があった。
【０００８】
また、ＬＲＵ制御を多段階化した疑似ＬＲＵ制御では、図１２に示すような外部からのエントリ使用選択不可信号による制御を行った場合、使用選択不可エントリの指定の仕方によっては、ＬＲＵ制御の結果があるエントリ（あるいは下位のエントリのグループ）に偏ってしまう懸念が発生するという問題点があった。
【０００９】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、対象エントリ数が多い場合のＬＲＵ制御の必要ビット数を抑えるとともに、完全なＬＲＵ制御を実現でき、使用不可エントリの選択の仕方によってＬＲＵ制御の結果に偏りが生じること防止することが可能なＬＲＵ制御装置およびＬＲＵ制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、請求項１に係る発明は、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択するＬＲＵ制御装置において、前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手段と、前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手段により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて更新するＬＲＵ情報更新手段と、前記ＬＲＵ情報記憶手段により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手段と、を備えたことを特徴とする。
【００１１】
また、請求項２に係る発明は、上記の発明において、ＬＲＵ制御する候補として選択可能であるか否かを示す情報を前記複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶する選択可否情報記憶手段をさらに備え、前記ＬＲＵ制御候補選択手段は、前記選択可否情報記憶手段に記憶されている選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択することを特徴とする。
【００１２】
また、請求項３に係る発明は、上記の発明において、前記ＬＲＵ候補選択手段は、前記ＬＲＵ情報記憶手段により記憶されている前記識別情報の全てが、前記選択可否情報記憶手段おいて選択不可能であることを示す情報にそれぞれ対応付けられている場合には、当該選択可否情報記憶手段において選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択することを特徴とする。
【００１３】
また、請求項４に係る発明は、上記の発明において、前記ＬＲＵ情報更新手段は、ＬＲＵ情報記憶手段により記憶されている前記各識別情報の全てが、前記選択可否情報記憶手段において選択不可能であることを示す情報にそれぞれ対応付けられている場合には、選択可能なエントリの識別情報で前記ＬＲＵ情報を更新することを特徴とする。
【００１４】
また、請求項５に係る発明は、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択する方法をコンピュータに実行させるＬＲＵ制御プログラムにおいて、前記複数のエントリのそれぞれを識別する識別情報を最終使用時が古い順に並べてＬＲＵ情報として記憶するＬＲＵ情報記憶手順と、前記複数のエントリの中のいずれかのエントリが使用された場合に、前記ＬＲＵ情報記憶手順により記憶されている各識別情報の中から当該使用されたエントリの識別情報を取り出し、当該使用されたエントリの識別情報を最後尾に移動させて更新するＬＲＵ情報更新手順と、前記ＬＲＵ情報記憶手順により記憶されている前記ＬＲＵ情報を参照して、前記複数のエントリの中からＬＲＵ制御する候補を選択するＬＲＵ制御候補選択手順と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１５】
請求項１または５の発明によれば、複数のエントリのそれぞれを識別する識別情報（例えば、エントリごとに一意に付与されたＩＤなど）を最終使用時が古い順に並べてＬＲＵ情報として記憶し、複数のエントリの中のいずれかのエントリが使用された場合に、各識別情報の中から当該使用されたエントリの識別情報を取り出すとともに最後尾に移動させてＬＲＵ情報を更新し、記憶しているＬＲＵ情報を参照して、複数のエントリの中からＬＲＵ制御する候補を選択するので、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することが可能となる。
【００１６】
また、請求項２の発明によれば、このＬＲＵ制御装置は、ＬＲＵ制御する候補として選択可能であるか否かを示す情報を複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶し、記憶している選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択するので、使用不可のエントリの選択の仕方によってＬＲＵ制御の結果に偏りが生じることを防止することができ、完全なＬＲＵ制御を実現することが可能となる。
【００１７】
また、請求項３の発明によれば、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択するので、例えば、フリップフロップやラッチを用いてＬＲＵ情報を構成した場合と比較して、ＲＡＭを用いてＬＲＵ情報を構成した場合に発生しやすいＬＲＵ情報の参照エラーに対処することができ、デバイスにとらわれない完全なＬＲＵ制御が可能となる。
【００１８】
また、請求項４の発明によれば、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能なエントリの識別情報（例えば、初期パターン）でＬＲＵ情報を更新するので、ＬＲＵ情報を正しく更新することで次回読み出したときにエントリを選択できない事態を防止することができ、完全なＬＲＵ制御が可能となる。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明に係るＬＲＵ制御装置およびＬＲＵ制御プログラムの実施例を詳細に説明する。なお、以下では、実施例１に係るＬＲＵ制御装置を説明した後に、この発明に含まれる他の実施例を説明する。
【実施例１】
【００２０】
以下の実施例１では、実施例１に係るＬＲＵ制御装置の概要および特徴、ＬＲＵ制御装置の構成および処理の流れを順に説明し、最後に実施例１による効果を説明する。
【００２１】
［概要および特徴（実施例１）］
まず最初に、図１を用いて、実施例１に係るＬＲＵ装置の概要および特徴を説明する。
図１は、実施例１に係るＬＲＵ制御装置の概要を説明するための図である。同図に示すように、実施例１に係るＬＲＵ制御装置は、記憶装置（例えば、メインメモリやキャッシュメモリ、ＲＡＭなど）に備えられた複数のエントリからＬＲＵ制御する（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ、つまり、最終使用時の最も古いエントリ内のデータを追い出す）エントリを選択することを概要とするが、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現する点に主たる特徴がある。
【００２２】
この主たる特徴について具体的に説明すると、実施例１に係るＬＲＵ制御装置は、複数のエントリのそれぞれを識別する識別情報（例えば、エントリごとに一意に付与されたＩＤなど）を記憶している。この識別情報は、例えば、図１の（１）に例示するように、エントリの識別情報（例えば、ＩＤ）を最終使用時が古い順に並べて記憶することでＬＲＵ情報を構成し、一番左側の位置に格納されている格納データ０が最終使用時の最も古い（つまり、ＬＲＵ）エントリのＩＤを示し、一番右側の位置に格納されている格納データＮが最終使用時の最も新しい（つまり、ＭＲＵ：Ｍｏｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）エントリのＩＤを示す。
【００２３】
そして、実施例１に係るＬＲＵ制御装置は、ＬＲＵ情報を参照して、ＬＲＵ情報の中から最終使用時の最も古いエントリのＩＤである格納データ０に基づいて、格納データ０に対応するエントリ（例えば、エントリ１）をＬＲＵ制御する候補として選択する。
【００２４】
また、実施例１に係るＬＲＵ制御装置は、エントリの使用に応じてＬＲＵ情報を更新することで、最終使用時の最も古いエントリを常に把握できるようにＬＲＵ情報を構成する。具体的には、例えば、アクセス要求に対応するデータを格納したエントリの識別情報である格納データ１がＬＲＵ情報の中に存在し、ＬＲＵ情報に更新の必要がある場合には、実施例１に係るＬＲＵ制御装置は、まず、ＬＲＵ情報の中から格納データ１を取り出す（図１の（２）参照）。次に、実施例１に係るＬＲＵ制御装置は、格納データ１よりも最終使用時の新しいエントリのＩＤを示す格納データ２から格納データＮまでを左にシフトするとともに、シフトによって生成されたＭＲＵの位置に格納データ１を移動させる（図１の（３）参照）。以上で、実施例１に係るＬＲＵ制御装置は、ＬＲＵ情報の更新を完了する（図１の（４）参照）。
【００２５】
このようなことから、実施例１に係るＬＲＵ制御装置は、上述した主たる特徴の如く、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することが可能となる。
【００２６】
［ＬＲＵ制御装置の構成（実施例１）］
次に、図２を用いて、実施例１に係るＬＲＵ制御装置の構成を説明する。図２は、実施例１に係るＬＲＵ制御装置の構成を示すブロック図である。なお、同図においては、実施例１に係るＬＲＵ制御装置を実現するうえで必要となる処理部のみを示しており、その他の処理部の記載については省略している。
【００２７】
同図に示すように、実施例１に係るＬＲＵ制御装置１０は、入出力制御部１１と、記憶部１２と、制御部１３とから構成される。このうち、入出力制御部１１は、各種の情報の入出力を制御する入出力制御手段であり、例えば、使用エントリ（更新にかかるエントリ）の識別情報（例えば、ＩＤ）の入力や、後述するＬＲＵ制御選択部１３ｂによりＬＲＵ制御候補として選択されたエントリの識別情報（例えば、ＩＤ）の外部モジュールへの出力を制御する。
【００２８】
記憶部１２は、制御部１３による各種処理に必要なデータおよびプログラムを格納する格納手段（記憶手段）であり、特に本発明に密接に関連するものとしては、ＬＲＵ情報記憶部１２ａを備える。このＬＲＵ情報記憶部１２ａは、例えば、１６のエントリでＬＲＵ情報を構成する場合には、図３に例示するように、ＬＲＵ制御の候補となる１６の対象エントリの識別情報（例えば、ＩＤ）を最終使用時の古い順に１番目候補から１６番目候補まで４ビットでエンコード（例えば、００００〜１１１１）した状態で記憶して構成される。
【００２９】
制御部１３は、所定の制御プログラム、各種の処理手順などを規定したプログラムおよび所要データを格納するための内部メモリを有し、これらによって種々の処理を実行する処理部であり、特に本発明に密接に関連するものとしては、ＬＲＵ情報格納制御部１３ａと、ＬＲＵ候補選択部１３ｂと、ＬＲＵ情報更新部１３ｃとを備える。
【００３０】
このうち、ＬＲＵ情報格納制御部１３ａは、ＬＲＵ情報記憶部１２ａにＬＲＵ情報を格納する制御部であり、具体的には、例えば、入出力制御部１１から受け付けた使用エントリ（更新にかかるエントリ）のの識別情報（例えば、ＩＤ）をＬＲＵ情報記憶部１２ａに備えられた所定の格納位置に格納する。
【００３１】
ＬＲＵ候補選択部１３ｂは、ＬＲＵ制御する候補を選択する処理部であり、具体的には、ＬＲＵ情報記憶部１２ａから読み出したＬＲＵ情報の中に、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）が存在しない場合には、最終使用時の最も古いエントリの識別情報（例えば、ＩＤ）に対応するエントリをＬＲＵ制御する候補として選択する。そして、ＬＲＵ候補選択部１３ｂは、ＬＲＵ制御する候補として選択したエントリの識別情報（例えば、ＩＤ）を、入出力制御部１１を介して、例えば、外部モジュールなどに出力する。
【００３２】
ＬＲＵ情報更新部１３ｃは、ＬＲＵ情報記憶部１２ａに記憶されているＬＲＵ情報を更新する処理部であり、具体的には、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にある場合には、ＬＲＵ情報の更新を行う。例えば、図５に例示するように、アクセス要求に対応するデータを格納したエントリ２の識別情報がＬＲＵ情報の中に存在する場合には、ＬＲＵ情報記憶部１２ａに記憶されているＬＲＵ情報の任意のインデックス（例えば、Ｚ）における２ｎｄの格納場所からエントリ２の識別情報（例えば、０からＦまでの１６進数で表わされている情報、図４参照）を取り出して、３ｒｄから１６ｔｈの格納場所に格納されているデータ（例えば、各エントリのＩＤ）を順次左側へシフトし、空いた１６ｔｈの格納場所へ２ｎｄの格納場所から取り出したエントリ２に対応するエントリの識別情報を格納してＬＲＵ情報を更新する（図５の（ａ）および（ｂ）参照）。
【００３３】
［ＬＲＵ制御装置による処理（実施例１）］
次に、図６を用いて、実施例１に係るＬＲＵ制御装置による処理を説明する。図６は、実施例１に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。同図に示すように、所定のデータに対してユーザなどからアクセス要求があると（ステップＳ６０１肯定）、ＬＲＵ制御装置１０のＬＲＵ候補選択部１３ｂは、ＬＲＵ情報記憶部１２ａからＬＲＵ情報を読み出す（ステップＳ６０２）。
【００３４】
そして、ＬＲＵ情報に更新の必要がある場合には（Ｓ６０３否定）、ＬＲＵ情報更新部１３ｃは、ＬＲＵ情報の更新を行う（ステップＳ６０４）。具体的には、ＬＲＵ情報更新部１３ｃは、例えば、アクセス要求に対応するデータを格納したエントリ２の識別情報（例えば、ＩＤ）がＬＲＵ情報の中にある場合には、ＬＲＵ情報記憶部１２ａに記憶されているＬＲＵ情報の任意のインデックス（例えば、Ｚ）における２ｎｄの格納場所からエントリ２に対応するエントリの識別情報（例えば、０からＦまでの１６進数で表わされている情報、図４参照）を取り出して、３ｒｄから１６ｔｈの格納場所に格納されているデータ（例えば、各エントリのＩＤ）を順次左側へシフトし、空いた１６ｔｈの格納場所へ２ｎｄの格納場所から取り出したエントリ２に対応するエントリの識別情報を格納してＬＲＵ情報を更新する（図５の（ａ）および（ｂ）参照）。
【００３５】
一方、ＬＲＵ情報に更新の必要がない場合（すなわち、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にない場合）には（Ｓ６０３否定）、ＬＲＵ候補選択部１３ｂは、ＬＲＵ情報の中から最終使用時の最も古いエントリをＬＲＵ制御する候補として選択する（ステップＳ６０５）。続いて、ＬＲＵ候補選択部１３ｂは、ＬＲＵ制御する候補として選択したエントリの識別情報を、入出力制御部１１を介して、例えば、外部モジュールなどに出力する（ステップＳ６０６）。
【００３６】
［実施例１の効果］
上述してきたように、実施例１によれば、このＬＲＵ制御装置は、複数のエントリのそれぞれを識別する識別情報（例えば、エントリごとに一意に付与されたＩＤなど）を最終使用時が古い順に並べてＬＲＵ情報として記憶し、複数のエントリの中のいずれかのエントリが使用された場合に、各識別情報の中から当該使用されたエントリの識別情報を取り出すとともに最後尾に移動させてＬＲＵ情報を更新し、記憶しているＬＲＵ情報を参照して、複数のエントリの中からＬＲＵ制御する候補を選択するので、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することが可能となる。
【実施例２】
【００３７】
ところで、上記の実施例１では、ＬＲＵ情報を参照して、ＬＲＵ制御する候補を選択する場合を説明したが、本発明はこれに限定されるものではなく、ＬＲＵ制御する候補として選択可能であるか否かの情報を複数のエントリにそれぞれ対応付けて記憶し、ＬＲＵ情報の中から選択可能なエントリをＬＲＵ制御する候補として選択するようにしてもよい。そこで、以下では、ＬＲＵ情報の中から選択可能なエントリをＬＲＵ制御する候補として選択する場合を実施例２として説明する。
【００３８】
なお、以下では、実施例２に係るＬＲＵ制御装置の構成および処理の流れを説明した後に、実施例２による効果を説明する。
【００３９】
［ＬＲＵ制御装置の構成（実施例２）］
まず最初に、図７を用いて、実施例２に係るＬＲＵ制御装置の構成を説明する。なお、実施例２に係るＬＲＵ制御装置は、実施例１に係るＬＲＵ制御装置と基本的に同様の構成であるが、以下に説明する点が異なる。
【００４０】
ＬＲＵ制御装置２０の選択可否情報記憶部２２ｂは、ＬＲＵ情報記憶部２２ａに記憶されているＬＲＵ情報の中からＬＲＵ制御する候補として選択可能であるか否かを示す情報を記憶する記憶手段であり、例えば、図８に例示するように、選択可能であるとする情報（例えば、０）や選択不可能であるとする情報（例えば、１）を各エントリＩＤ（例えば、０からＦの１６進数）にそれぞれ対応付けて記憶して構成される。
【００４１】
ＬＲＵ制御装置２０のＬＲＵ候補予備選択部２３ｃは、ＬＲＵ候補選択部２３ｂにより選択されたＬＲＵ制御の候補が選択可能であるか否かを判別する処理部であり、具体的には、選択可否情報記憶部２２ｂから選択可否情報を読み出して、ＬＲＵ候補選択部２３ｂにより選択されたエントリがＬＲＵ制御の候補として選択可能であるかどうか判定し、判定結果をＬＲＵ候補選択部２３ｂに対して出力する。
【００４２】
ＬＲＵ制御装置２０のＬＲＵ候補選択部２３ｂは、ＬＲＵ候補予備選択部２３ｃから選択可能である旨の判定結果を受け付けた場合には、選択したエントリをＬＲＵ制御の候補として最終的に選択する。一方、選択されたエントリが選択不可能である旨の判定結果を受け付けた場合には、ＬＲＵ候補選択部２３ｂは、読み出したＬＲＵ情報の中から次候補となるエントリを再選択する。具体的には、例えば、図４に示す１ｓｔの位置に格納されたエントリＣが選択不可能である場合には、２ｎｄの位置に格納されたエントリ２をＬＲＵ制御する次候補として選択する。
【００４３】
［ＬＲＵ制御装置の処理（実施例２）］
次に、図９を用いて、実施例２に係るＬＲＵ制御装置の処理を説明する。図９は、実施例２に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。同図に示すように、所定のデータに対してユーザなどからリードアクセス要求があると（ステップＳ９０１肯定）、ＬＲＵ制御装置２０のＬＲＵ候補選択部２３ｂは、ＬＲＵ情報記憶部２２ａからＬＲＵ情報を読み出す（ステップＳ９０２）。
【００４４】
そして、ＬＲＵ情報に更新がある場合（すなわち、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にある場合）には（Ｓ９０３）、ＬＲＵ情報更新部１３ｃは、上記の実施例１において説明したのと同様に、ＬＲＵ情報の更新を行う（ステップＳ９０４）。
【００４５】
一方、ＬＲＵ情報に更新がない場合（すなわち、アクセス要求に対応するデータを格納したエントリの識別情報（例えば、ＩＤ）がＬＲＵ情報の中にない場合）には（Ｓ９０３否定）、ＬＲＵ候補選択部１３ｂは、ＬＲＵ情報の中から最終使用時の最も古いエントリをＬＲＵ制御する候補として選択する（ステップＳ９０５）。
【００４６】
続いて、ＬＲＵ候補予備選択部２３ｃは選択可否情報を読み出す（ステップＳ９０６）。選択可否情報の読み出し後、ＬＲＵ候補予備選択部２３ｃは、ＬＲＵ候補選択部２３ｂにより選択されたエントリがＬＲＵ制御の候補として選択可能であるか否かを判定する（ステップＳ９０７）。判定の結果、その候補が選択可能である場合には（ステップＳ９０７肯定）、ＬＲＵ候補選択部２３ｂは、選択したエントリをＬＲＵ制御の候補として最終的に選択する。そして、ＬＲＵ候補選択部２３ｂは、ＬＲＵ制御する候補として最終的に選択したエントリを、入出力制御部１１を介して、例えば、外部モジュールなどに出力する（ステップＳ９０６）。
【００４７】
ここで、ステップＳ９０７の説明に戻ると、ＬＲＵ候補予備選択部２３ｃによる判定の結果、ＬＲＵ候補選択部２３ｂにより選択されたエントリがＬＲＵ制御の候補として選択不可能である場合には（ステップＳ９０７否定）、ＬＲＵ候補が決定されるまで上述したステップＳ９０５からステップＳ９０７に示す処理を繰り返し行う。
【００４８】
［実施例２の効果］
上述してきたように、実施例２によれば、このＬＲＵ制御装置は、ＬＲＵ制御する候補として選択可能であるか否かを示す情報を複数のエントリの各識別情報にそれぞれ対応付けて選択可否情報として記憶し、記憶している選択可否情報をさらに参照して、選択可能なエントリの中からＬＲＵ制御する候補を選択するので、使用不可のエントリの選択の仕方によってＬＲＵ制御の結果に偏りが生じることを防止することができ、完全なＬＲＵ制御を実現することが可能となる。
【００４９】
また、上記の実施例２において、ＬＲＵ候補選択部２３ｂによってＬＲＵ情報記憶部２２ａから読み出されたＬＲＵ情報に参照エラーが発生（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生）した場合には、ＬＲＵ候補予備選択部２３ｃは、選択可否情報の中から選択可能なエントリのいずれを選択するようにしてもよい。
【００５０】
例えば、図１２に示すように、ＬＲＵ候補選択部２３ｂによってＬＲＵ情報記憶部２２ａから読み出された情報に参照エラーが発生（一意に付与されているはずのエントリＩＤＣ、６、Ｆなどが重なって読み出されている）して、例えば、図８に示す選択可否情報を参照して、読み出したＬＲＵ情報の中のエントリがＬＲＵ制御する候補として全て選択不可能である場合には、ＬＲＵ候補予備選択部２３ｃは、選択可否情報の中から選択可能なエントリ（例えば、２、３，４など）のいずれかを選択する。
【００５１】
これにより、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能であることを示す情報に対応付けられたエントリのいずれかをＬＲＵ制御する候補として選択するので、例えば、フリップフロップやラッチを用いてＬＲＵ情報を構成した場合と比較して、ＲＡＭを用いてＬＲＵ情報を構成した場合に発生しやすいＬＲＵ情報の参照エラーに対処することができ、デバイスにとらわれない完全なＬＲＵ制御が可能となる。
【実施例３】
【００５２】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【００５３】
（１）ＬＲＵ情報の更新
上記の実施例２において、ＬＲＵ候補選択部２３ｂによってＬＲＵ情報記憶部２２ａから読み出されたＬＲＵ情報に参照エラーが発生（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生）した場合には、ＬＲＵ候補予備選択部２３ｃは、選択可否情報の中から選択可能なエントリのいずれを選択する場合を説明したが、本発明はこれに限定されるものではなく、ＬＲＵ情報内のエントリの識別情報（例えば、ＩＤ）を選択可能なエントリの識別情報で更新するようにしてもよい。そこで、以下では、図１０、図１１および図１３を用いて、ＬＲＵ情報内のエントリの識別情報を更新する場合を説明する。
【００５４】
図１０に示すように、ＬＲＵ制御装置３０は、上記の実施例において説明したＬＲＵ制御装置と基本的には同様の構成であるが、以下に説明する更新情報記憶部３２ｃ、ＬＲＵ候補選択部３３ｂおよびＬＲＵ情報更新部３３ｄが異なる。
【００５５】
ＬＲＵ制御装置３０の更新情報記憶部３２ｃは、ＬＲＵ情報更新部３３ｄにおいて利用される更新情報を記憶する手段であり、例えば、参照エラーが発生したＬＲＵ情報内のデータを更新するための情報として、選択可能なエントリを含んだ情報（例えば、全てのエントリＩＤを含んだ初期パタンなどの整合情報）を記憶して構成される。
【００５６】
ＬＲＵ制御装置３０のＬＲＵ候補選択部３３ｂは、ＬＲＵ情報記憶部３２ａから読み出したＬＲＵ情報の中に全てのエントリＩＤが含まれていない（例えば、図１１参照）場合には、参照エラーとして、ＬＲＵ情報更新部３３ｄにその旨の信号を出力する。
【００５７】
ＬＲＵ制御装置のＬＲＵ情報更新部３３ｃは、ＬＲＵ候補選択部３３ｂから参照エラーである旨の信号を受け付けると、更新情報記憶部３２ｃから更新情報を読み出し、例えば、エントリ７の使用にかかるＬＲＵ情報の更新がある場合には、その更新を反映した形で整合情報を生成し（図１３参照）、ＬＲＵ情報記憶部３２ａに書き込むことでＬＲＵ情報内のデータを更新する。
【００５８】
これにより、このＬＲＵ制御装置は、記憶している各識別情報の全てが、選択不可能であることを示す情報にそれぞれ対応付けられている場合（例えば、ＬＲＵ情報として不整合な情報が読み出されてしまうエラーが発生した場合）には、選択可能なエントリの識別情報（例えば、初期パターン）でＬＲＵ情報を更新するので、ＬＲＵ情報を正しく更新することで次回読み出したときにエントリを選択できない事態を防止することができ、完全なＬＲＵ制御が可能となる。
【００５９】
（２）装置構成等
また、図２、図７および図１０示した各ＬＲＵ制御装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各ＬＲＵ制御装置の分散・統合の具体的形態は図示のものに限られず、例えば、ＬＲＵ制御装置１０のＬＲＵ情報格納制御部１３ａとＬＲＵ候補選択部１３ｂとを統合し、ＬＲＵ制御装置２０のＬＲＵ候補選択部２３ｂとＬＲＵ候補予備選択部２３ｃとを統合し、ＬＲＵ制御装置３０のＬＲＵ情報記憶部３２ａと選択可否情報記憶部３２ｂとを統合するなど、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各ＬＲＵ制御装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００６０】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００６１】
（３）ＬＲＵ制御プログラム
ところで、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することができる。そこで、以下では、図１４を用いて、上記の実施例１で説明したＬＲＵ制御装置１０の処理（ＬＲＵ制御処理）と同様の機能を有するＬＲＵ制御プログラムを実行するコンピュータの一例を説明する。図１４は、ＬＲＵ制御プログラムを実行するコンピュータを示す図である。
【００６２】
同図に示すように、ＬＲＵ制御装置であるコンピュータ４０は、入出力制御部４１と、ＨＤＤ４２と、ＲＡＭ４３と、ＲＯＭ４４と、ＣＰＵ４５とを所定のバス５０で接続して構成される。ここで、入出力制御部４１は、図２に示した入出力制御部１１に対応する。
【００６３】
まず、ＲＯＭ４４には、上記の実施例１に示したＬＲＵ制御装置１０と同様の機能を発揮するＬＲＵ制御プログラム、つまり、図１４に示すように、ＬＲＵ情報格納制御プログラム４４ａ、ＬＲＵ候補選択プログラム４４ｂおよびＬＲＵ情報更新プログラム４４ｃがあらかじめ記憶されている。なお、これらのプログラム４４ａ、４４ｂおよび４４ｃについては、図２に示したＬＲＵ制御装置１０の各構成要素と同様、適宜統合または分散してもよい。
【００６４】
そして、ＣＰＵ４５が、これらのプログラム４４ａ、４４ｂおよび４４ｃをＲＯＭ４４から読み出して実行することで、図１４に示すように、各プログラム４４ａ、４４ｂおよび４４ｃは、ＬＲＵ情報格納制御プロセス４５ａ、ＬＲＵ候補選択プロセス４５ｂおよびＬＲＵ情報更新プロセス４５ｃとして機能するようになる。なお、各プロセス４５ａ、４５ｂおよび４５ｃは、図２に示したＬＲＵ制御装置１０のＬＲＵ情報格納制御部１３ａ、ＬＲＵ候補選択部１３ｂおよびＬＲＵ情報更新部１３ｃにそれぞれ対応する。
【００６５】
また、ＨＤＤ４２には、図１４に示すように、ＬＲＵ情報テーブル４２ａが設けられる。このＬＲＵ情報テーブル４２ａは、図２に示したＬＲＵ制御装置１０のＬＲＵ情報記憶部１２ａに対応する。そして、ＣＰＵ４５は、ＬＲＵ情報テーブル４２ａからＬＲＵ情報データ４３ａを読み出してＲＡＭ４３に格納し、ＲＡＭ４３に格納されたＬＲＵ情報データ４３ａに基づいてＬＲＵ制御処理を実行する。
【００６６】
なお、上記した各プログラム４４ａ、４４ｂおよび４４ｃは、必ずしも最初からＲＯＭ４４に記憶させておく必要はなく、例えば、コンピュータ４０に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータ４０の内外に備えられるＨＤＤなどの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４０に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ４０がこれらから各プログラムを読み出して実行するようにしてもよい。
【産業上の利用可能性】
【００６７】
以上のように、本発明に係るＬＲＵ制御装置およびＬＲＵ制御プログラムは、記憶装置に備えられた複数のエントリからＬＲＵ制御するエントリを選択する場合に有用であり、特に、対象エントリ数が多い場合のＬＲＵ制御に必要なビット数を抑えるとともに、完全なＬＲＵ制御を実現することに適する。
【図面の簡単な説明】
【００６８】
【図１】図１は、実施例１に係るＬＲＵ制御装置の概要を説明するための図である。
【図２】図２は、実施例１に係るＬＲＵ制御装置の構成を示すブロック図である。
【図３】図３は、１６エントリＬＲＵの構成例を示す図である。
【図４】図４は、任意のインデックスのＬＲＵ情報の例を示す図である。
【図５】図５は、更新によるＬＲＵ情報の遷移を示す図である。
【図６】図６は、実施例１に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。
【図７】図７は、実施例２に係るＬＲＵ制御装置の構成を示すブロック図である。
【図８】図８は、選択可否情報の例を示す図である。
【図９】図９は、実施例２に係るＬＲＵ制御装置の処理の流れを示すフローチャートである。
【図１０】図１０は、実施例３に係るＬＲＵ制御装置の構成を示すブロック図である。
【図１１】図１１は、エラーしたＬＲＵ情報の例を示す図である。
【図１２】図１２は、エラーしたＬＲＵ情報の例を示す図である。
【図１３】図１３は、ＬＲＵ情報更新部で生成される整合情報の例を示す図である。
【図１４】図１４は、ＬＲＵ制御プログラムを実行するコンピュータを示す図である。
【図１５】図１５は、従来技術の４エントリＬＲＵの例を示す図である。
【図１６】図１６は、従来技術によるＬＲＵエントリの求め方を示す図である。
【図１７】図１７は、１６エントリの２段疑似ＬＲＵの例を示す図である。
【符号の説明】
【００６９】
１０  ＬＲＵ制御装置
１１  入出力制御部
１２  記憶部
１２ａ  ＬＲＵ情報記憶部
１３  制御部
１３ａ  ＬＲＵ情報格納制御部
１３ｂ  ＬＲＵ候補選択部
１３ｃ  ＬＲＵ情報更新部
２０  ＬＲＵ制御装置
２１  入出力制御部
２２  記憶部
２２ａ  ＬＲＵ情報記憶部
２２ｂ  選択可否情報記憶部
２３  制御部
２３ａ  ＬＲＵ情報格納制御部
２３ｂ  ＬＲＵ候補選択部
２３ｃ  ＬＲＵ候補予備選択部
２３ｄ  ＬＲＵ情報更新部
３０  ＬＲＵ制御装置
３１  入出力制御部
３２  記憶部
３２ａ  ＬＲＵ情報記憶部
３２ｂ  選択可否情報記憶部
３２ｃ  更新情報記憶部
３３  制御部
３３ａ  ＬＲＵ情報格納制御部
３３ｂ  ＬＲＵ候補選択部
３３ｃ  ＬＲＵ候補予備選択部
３３ｄ  ＬＲＵ情報更新部
４０  コンピュータ
４１  入出力制御部
４２  ＨＤＤ（Hard  disk  drive）
４３  ＲＡＭ（Random  access  memory）
４４  ＲＯＭ（Read  only  memory）
４５  ＣＰＵ（Central  processing  unit）
５０  バス
【国際調査報告】
2007097028.tif 000020
2007097028.tif 000021
2007097028.tif 000022