(57)【要約】【課題】特定のインデックスに対応するキャッシュブロックにアクセスが集中しても、ヒット率の低下を抑制すること。【解決手段】実施形態によれば、情報処理装置は、第１の記憶装置を第２の記憶装置のキャッシュとして使用するキャッシュ制御手段を具備する。前記キャッシュ制御手段は、複数の第１のキャッシュブロック内のキャッシュデータと、前記複数の第１のキャッシュブロックを管理するための各第１のキャッシュブロックにそれぞれ対応する複数の第１のブロック管理データとを前記第１の記憶装置内に格納して管理する。【選択図】    図２
2014071712.tif 000002
【特許請求の範囲】
【請求項１】
第１の記憶装置を１台以上の第２の記憶装置のキャッシュとして使用する情報処理装置において、
複数の第１のキャッシュブロック内のキャッシュデータと、前記複数の第１のキャッシュブロックを管理するための各第１のキャッシュブロックにそれぞれ対応する複数の第１のブロック管理データとを前記第１の記憶装置内に格納して管理するキャッシュ制御手段を具備し、
前記第１のブロック管理データは、前記複数の第１のキャッシュブロックの内の一つのキャッシュブロックを指すブロックポインタと、前記ブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のブロックのアドレスおよび設定数を用いて求められる位置情報を示すタグと、対応する第１のキャッシュブロックのアクセス順にブロック管理データをたどるための使用順情報を含む使用順リンクと、同一のインデックスに対応するブロック管理データをたどるためのインデックス情報とを含む
情報処理装置。
【請求項２】
前記キャッシュ制御手段は、前記使用順情報を含む使用順リンクヘッダと、前記インデックス情報を含む前記設定数の複数のインデックスリンクヘッダとを前記第１の記憶装置内に格納して管理する
請求項１に記載の情報処理装置。
【請求項３】
前記キャッシュ制御手段は、前記情報処理装置の稼働中に、前記キャッシュ容量を変更するキャッシュ容量変更手段を有する
請求項２に記載の情報処理装置。
【請求項４】
キャッシュ容量を元のキャッシュ容量より大きい容量に変更する場合、前記キャッシュ容量変更手段は、
前記増加されたキャッシュ容量に応じた数の第２のキャッシュブロックと、前記複数の第２のキャッシュブロックに対応する複数の第２のブロック管理データとを前記第１の記憶装置内に生成し、
前記複数の第２のブロック管理データ内のインデックス情報を無効にし、
前記使用順インデックスリンクヘッダ内の使用順情報から、各第２のブロック管理データの内の第３のブロック管理データ内の使用順情報が最古にアクセスされたキャッシュブロックに対応するブロック管理データとしてたどれるように、使用順インデックスリンクヘッダ内の使用順情報を変更し、
前記第３のブロック管理データ内の使用順情報から、前記複数の第２のブロック管理データから前記第３のブロック管理データを除いたブロック管理データ内の使用順情報にたどれるように、前記第２のブロック管理データ内の使用順情報を変更する
請求項３に記載の情報処理装置。
【請求項５】
キャッシュ容量を元のキャッシュ容量より小さい容量に変更する場合、前記キャッシュ容量変更手段は、
現在のキャッシュ容量および前記要求されたキャッシュ容量に応じた、前記複数の第１のキャッシュブロックから減少対象の複数の第４のキャッシュブロックを選択し、
前記複数の第４のキャッシュブロックの内の第５のキャッシュブロックが開放可能な場合、前記複数の第１のキャッシュブロックから前記第５のキャッシュブロックを除いたキャッシュブロックのアクセス順にたどれるように、前記第５のキャッシュブロックを除いた前記複数の第１のキャッシュブロックに対応するブロック管理データ内の使用順情報を変更し、
前記複数の第４のキャッシュブロックの全てが開放可能になった場合、前記複数の第４のキャッシュブロックと前記複数の第４のキャッシュブロックに対応するブロック管理データとを解放する
請求項３に記載の情報処理装置。
【請求項６】
前記キャッシュ制御手段からアクセス可能であり、前記キャッシュ容量を示す容量情報が書き込まれる記憶媒体と、
設定されたキャッシュ容量に応じた前記容量情報を前記記憶媒体に書き込む書き込み手段とを更に具備し、
前記キャッシュ制御手段は、前記記憶媒体内の容量情報に応じてキャッシュ容量を変更する
請求項３に記載の情報処理装置。
【請求項７】
前記書き込み手段は、前記容量情報を前記記憶媒体に書き込んだ後に、前記キャッシュ制御手段に通知し、
前記キャッシュ制御手段は、前記書き込み手段からの通知に応じて、前記記憶媒体内の容量情報に応じてキャッシュ容量を変更する
請求項６に記載の情報処理装置。
【請求項８】
前記記憶媒体は、不揮発性記憶装置であり、
前記情報処理装置の起動時に、前記前記キャッシュ制御手段は、前記容量情報に基づいて、前記複数のキャッシュブロックが格納される領域を前記第１の記憶装置内に確保する
請求項６に記載の情報処理装置。
【請求項９】
第１の記憶装置を１台以上の第２の記憶装置のキャッシュとして使用するキャッシュコントローラであって、
複数の第１のキャッシュブロック内のキャッシュデータと、前記複数の第１のキャッシュブロックを管理するための各第１のキャッシュブロックにそれぞれ対応する複数の第１のブロック管理データとを前記第１の記憶装置内に格納して管理するキャッシュ制御手段を具備し、
前記第１のブロック管理データは、前記複数の第１のキャッシュブロックの内の一つのキャッシュブロックを指すブロックポインタと、前記ブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のブロックのアドレスおよび設定数を用いて求められる位置情報を示すタグと、対応する第１のキャッシュブロックのアクセス順にブロック管理データをたどるための使用順情報を含む使用順リンクと、同一のインデックスに対応するブロック管理データをたどるためのインデックス情報とを含む
キャッシュコントローラ。
【請求項１０】
前記キャッシュ制御手段は、前記使用順情報を含む使用順リンクヘッダと、前記インデックス情報を含む前記設定数の複数のインデックスリンクヘッダとを前記第１の記憶装置内に格納して管理する
請求項９に記載のキャッシュコントローラ。
【請求項１１】
前記キャッシュ制御手段は、前記情報処理装置の稼働中に、前記キャッシュ容量を変更するキャッシュ容量変更手段を有する
請求項１０に記載のキャッシュコントローラ。
【請求項１２】
キャッシュ容量を元のキャッシュ容量より大きい容量に変更する場合、前記キャッシュ容量変更手段は、
前記増加されたキャッシュ容量に応じた数の第２のキャッシュブロックと、前記複数の第２のキャッシュブロックに対応する複数の第２のブロック管理データとを前記第１の記憶装置内に生成し、
前記複数の第２のブロック管理データ内のインデックス情報を無効にし、
前記使用順インデックスリンクヘッダ内の使用順情報から、各第２のブロック管理データの内の第３のブロック管理データ内の使用順情報が最古にアクセスされたキャッシュブロックに対応するブロック管理データとしてたどれるように、使用順インデックスリンクヘッダ内の使用順情報を変更し、
前記第３のブロック管理データ内の使用順情報から、前記複数の第２のブロック管理データから前記第３のブロック管理データを除いたブロック管理データ内の使用順情報にたどれるように、前記第２のブロック管理データ内の使用順情報を変更する
具備する請求項１０に記載のキャッシュコントローラ。
【請求項１３】
キャッシュ容量を元のキャッシュ容量より小さい容量に変更する場合、前記キャッシュ容量変更手段は、
現在のキャッシュ容量および前記要求されたキャッシュ容量に応じた、前記複数の第１のキャッシュブロックから減少対象の複数の第４のキャッシュブロックを選択し、
前記複数の第４のキャッシュブロックの内の第５のキャッシュブロックが開放可能な場合、前記複数の第１のキャッシュブロックから前記第５のキャッシュブロックを除いたキャッシュブロックのアクセス順にたどれるように、前記第５のキャッシュブロックを除いた前記複数の第１のキャッシュブロックに対応するブロック管理データ内の使用順情報を変更し、
前記複数の第４のキャッシュブロックの全てが開放可能になった場合、前記複数の第４のキャッシュブロックと前記複数の第４のキャッシュブロックに対応するブロック管理データとを解放する
請求項１１に記載のキャッシュコントローラ。
【請求項１４】
第１の記憶装置を１台以上の第２の記憶装置のキャッシュとして使用するキャッシュ制御方法であって、
キャッシュ制御手段によって、複数の第１のキャッシュブロック内のキャッシュデータと、前記複数の第１のキャッシュブロックを管理するための各第１のキャッシュブロックにそれぞれ対応する複数の第１のブロック管理データとを前記第１の記憶装置内に格納して管理し、
前記第１のブロック管理データは、前記複数の第１のキャッシュブロックの内の一つのキャッシュブロックを指すブロックポインタと、前記ブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のブロックのアドレスおよび設定数を用いて求められる位置情報を示すタグと、対応する第１のキャッシュブロックのアクセス順にブロック管理データをたどるための使用順情報を含む使用順リンクと、同一のインデックスに対応するブロック管理データをたどるためのインデックス情報とを含む
キャッシュ制御方法。
【請求項１５】
前記キャッシュ制御手段によって、前記使用順情報を含む使用順リンクヘッダと、前記インデックス情報を含む前記設定数の複数のインデックスリンクヘッダとを前記第１の記憶装置内に格納して管理する
請求項１４に記載のキャッシュ制御方法。
【請求項１６】
初期時、前記使用順情報によって、各ブロック管理データがリンクされ、各ブロック管理データのインデックスリンクは無効であり、各インデックスリンクヘッダは空である、
前記第２の記憶装置内のブロックに対するアクセスコマンドを受領した場合、前記キャッシュ制御手段によって、前記ハッシュ関数を使用して前記ブロックのアドレスに対応する第１のインデックスリンクヘッダを特定し、
前記キャッシュ制御手段によって、前記第１のインデックスリンクヘッダのインデックス情報からブロック管理データをたどることによって、前記ブロックのアドレスに対応するタグを含むブロック管理データがあるかを判定し、
前記キャッシュ制御手段によって、前記ブロックのアドレスに対応するタグを含むブロック管理データがない場合、前記使用順情報に基づいて、アクセスが古いキャッシュブロックに対応するブロック管理データから順にブロック管理データをたどることによって、キャッシュデータを割り当て可能な第２のキャッシュブロックを選択し、
前記キャッシュ制御手段によって、前記第２のキャッシュブロックに対応する第２のブロック管理データのインデックス情報が有効である場合、前記第２のブロック管理データのインデックス情報を削除し、
前記キャッシュ制御手段によって、前記第２のブロック管理データ内のタグを前記ブロックのアドレスに基づいたタグに書き換え、
前記キャッシュ制御手段によって、前記第２のインデックスリンクヘッダのインデックス情報から前記第２のブロック管理データをたどれるように、前記第２のインデックスリンクヘッダのインデックス情報を変更し、
前記キャッシュ制御手段によって、前記第２のブロック管理データ、または前記ブロックのアドレスに対応するタグを含む第３のブロック管理データが、前記使用順リンクヘッダ内の使用順情報から最新にアクセスされたキャッシュブロックに対応するブロック管理データとしてたどれるように、前記使用順リンクヘッダ内の使用順情報を変更し、
前記キャッシュ制御手段によって、前記第１のブロック管理データまたは前記第２のブロック管理データに対応するキャッシュブロックに対して前記アクセスコマンドに応じた処理を行う
請求項１５に記載のキャッシュ制御方法。
【請求項１７】
各インデックスリンクヘッダおよび前記インデックスリンクのインデックス情報に基づいて、同一のインデックスに対応するブロック管理データを対応するキャッシュブロックのアクセス順にたどることが可能であり、
前記キャッシュ制御手段によって、前記第２のブロック管理データ、または前記第３のブロック管理データが、前記インデックスリンクヘッダ内のインデックス情報から最新にアクセスされたキャッシュブロックに対応するブロック管理データとしてたどれるように、前記インデックスリンクヘッダ内のインデックス情報を変更する
請求項１６に記載のキャッシュ制御方法。
【請求項１８】
前記キャッシュ制御手段が有するキャッシュ容量変更手段によって、前記情報処理装置の稼働中に、前記キャッシュ容量を変更する
請求項１５に記載のキャッシュ制御方法。
【請求項１９】
前記変更されたキャッシュ容量が元のキャッシュ容量より大きい場合、
前記キャッシュ容量変更手段によって、前記増加されたキャッシュ容量に応じた数の第２のキャッシュブロックと、前記複数の第２のキャッシュブロックに対応する複数の第２のブロック管理データとを前記第１の記憶装置内に生成し、
前記キャッシュ容量変更手段によって、前記複数の第２のブロック管理データ内のインデックス情報を無効にし、
前記キャッシュ容量変更手段によって、前記使用順インデックスリンクヘッダ内の使用順情報から、各第２のブロック管理データの内の第３のブロック管理データ内の使用順情報が最古にアクセスされたキャッシュブロックに対応するブロック管理データとしてたどれるように、使用順インデックスリンクヘッダ内の使用順情報を変更し、
前記キャッシュ容量変更手段によって、前記第３のブロック管理データ内の使用順情報から、前記複数の第２のブロック管理データから前記第３のブロック管理データを除いたブロック管理データ内の使用順情報にたどれるように、前記第２のブロック管理データ内の使用順情報を変更する
請求項１８に記載のキャッシュ制御方法。
【請求項２０】
各ブロック管理データは、前記キャッシュブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のデータが格納されているアドレスを含み、
前記キャッシュ容量変更手段によって、前記設定されたキャッシュ容量および前記要求されたキャッシュ容量に応じた数の前記インデックスリンクヘッダを新たに前記第１の記憶装置内に用意し、
前記キャッシュ容量変更手段によって、前記インデックスリンクヘッダの数および前記ブロック管理データの前記第２の記憶装置のデータが格納されているアドレスを用いて前記ハッシュ関数によってインデックスを演算し、
前記キャッシュ容量変更手段によって、演算されたインデックスに基づいて、前記複数のブロック管理データおよび前記複数の第２のブロック管理データ内のインデックス情報を変更する
請求項１９に記載のキャッシュ制御方法。
【請求項２１】
前記変更されたキャッシュ容量が元のキャッシュ容量より小さい場合、
前記キャッシュ容量変更手段によって、現在のキャッシュ容量および前記要求されたキャッシュ容量に応じた、前記複数の第１のキャッシュブロックから減少対象の複数の第４のキャッシュブロックを選択し、
前記キャッシュ容量変更手段によって、前記複数の第４のキャッシュブロックの内の第５のキャッシュブロックが開放可能な場合、前記複数の第１のキャッシュブロックから前記第５のキャッシュブロックを除いたキャッシュブロックのアクセス順にたどれるように、前記第５のキャッシュブロックを除いた前記複数の第１のキャッシュブロックに対応するブロック管理データ内の使用順情報を変更し、
前記キャッシュ容量変更手段によって、前記複数の第４のキャッシュブロックの全てが開放可能になった場合、前記複数の第４のキャッシュブロックと前記複数の第４のキャッシュブロックに対応するブロック管理データとを解放する
請求項１８に記載のキャッシュ制御方法。
【請求項２２】
各ブロック管理データは、前記キャッシュブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のデータが格納されているアドレスを含み、
前記キャッシュ容量変更手段によって、前記複数の第４のキャッシュブロック、および前記複数の第３のブロック管理データを開放した場合、前記キャッシュ容量変更手段によって、前記変更されたキャッシュ容量に応じた数の複数の第２のインデックスヘッダを用意し、
前記キャッシュ容量変更手段によって、前記ブロック管理データ内の前記第２の記憶装置のデータが格納されているアドレス、および前記インデックスヘッダの数を用いて前記ハッシュ関数によってインデックスを演算し、
前記キャッシュ容量変更手段によって、演算されたインデックスに基づいて、前記複数の第３のブロック管理データを除いた前記複数の第１のブロック管理データ内の前記インデックス情報を変更する
請求項２１に記載のキャッシュ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、第１の記憶装置を第２の記憶装置のキャッシュとして用いる情報処理装置、キャッシュコントローラ、およびキャッシュ制御方法に関する。
【背景技術】
【０００２】
キャッシュブロックの管理方法として、固定ウェイセットアソシアティブが用いられている。固定ウェイセットアソシアティブでは、キャッシュブロックの数が例えば１２８個の場合、例えばインデックスの数が３２、ウェイの数が４個のディレクトリによって管理する。ディレクトリは、インデックス数×ウェイ数の表形式である。
【０００３】
ディレクトリの各ブロックはＬＲＵ（Least Recently Used）カウンタ、制御データと、タグ部を有する。ＬＲＵカウンタは０−３の値をとり、あるインデックス内の４つのブロックの相対的なアクセス時間を表している。０が最も最近アクセスされたブロックで、３が最も過去にアクセスされたブロックを表す。
【０００４】
キャッシュのヒットまたはミスを判定し、ミスした場合のキャッシュブロック割り当て方法を説明する。
【０００５】
１．キャッシュコントローラがコマンドを受領する。
【０００６】
２．ＨＤＤ識別子に対応するＨＤＤ  ＩＤを求め、要求ＬＢＡと結合して拡張ＬＢＡを生成する。
【０００７】
３．拡張ＬＢＡのオフセット部を除く上位２５ビットを、インデックス数（この例では３２）で割った商（タグ）と余り（インデックス）を計算する。
【０００８】
４．インデックスに相当するディレクトリを参照し、４つのいずれかのタグ部が上記商（タグ）と一致した場合はキャッシュヒット、いずれとも一致しない場合はキャッシュミスである。
【０００９】
５．キャッシュヒットした場合は、ヒットしたブロックのＬＲＵカウンタより小さい他のブロックのＬＲＵカウンタをインクリメントし、ヒットしたブロックのＬＲＵカウンタは０にする。
【００１０】
６．キャッシュミスした場合は、４つのブロックのうち、割り当て可能で、ＬＲＵカウンタが最も大きいブロックを割り当てる。ここで、割り当て可能とは、例えば当該ブロックが使用中でなく、Ｄｉｒｔｙでもないものを指す。割り当てたブロックのＬＲＵカウンタより小さい他のブロックのＬＲＵカウンタをインクリメントし、割り当てたブロックのＬＲＵカウンタは０にする。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】国際公開第２００８／０６８７９７号パンフレット
【特許文献２】特許第３４２６３８５号公報
【特許文献３】特開平６−３３２８０１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
特定のインデックスに対応するキャッシュブロックにアクセスが集中した場合、そのインデックス内で追い出しが発生し、ヒット率が低下することがある。
【００１３】
本発明の目的は、特定のインデックスに対応するキャッシュブロックにアクセスが集中しても、ヒット率の低下を抑制することが可能な情報処理装置、キャッシュコントローラ、およびキャッシュ制御方法を提供することにある。
【課題を解決するための手段】
【００１４】
実施形態によれば、情報処理装置は、第１の記憶装置と、前記第１の記憶装置を１台以上の第２の記憶装置のキャッシュとして使用する。情報処理装置は、第１の記憶装置と、キャッシュ制御手段とを具備する。キャッシュ制御手段は、複数の第１のキャッシュブロック内のキャッシュデータと、前記複数の第１のキャッシュブロックを管理するための各第１のキャッシュブロックにそれぞれ対応する複数の第１のブロック管理データとを前記第１の記憶装置内に格納して管理する。前記第１のブロック管理データは、前記複数の第１のキャッシュブロックの内の一つのキャッシュブロックを指すブロックポインタと、前記ブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のブロックのアドレスおよび設定数を用いて求められる位置情報を示すタグと、対応する第１のキャッシュブロックのアクセス順にブロック管理データをたどるための使用順情報を含む使用順リンクと、同一のインデックスに対応するブロック管理データをたどるためのインデックス情報とを有する。
【図面の簡単な説明】
【００１５】
【図１】実施形態の情報処理装置のシステム構成の一例を示すブロック図である。
【図２】キャッシュドライバによってメインメモリに格納されるデータの構成の一例を示す図。
【図３】ブロック管理データの構成の一例を示す図
【図４】使用順リンクの構成の一例を示す図。
【図５】使用順リンクヘッダの構成の一例を示す図。
【図６】インデックスリンクの構成の一例を示す図。
【図７】インデックスリンクヘッダの構成の一例を示す図。
【図８】初期状態の制御データを示す図。
【図９】キャッシュ処理が進んだ状態の制御データを示す図。
【図１０】使用順リンクヘッダおよび使用順リンクが変更された後のリンク状態を示す図。
【図１１】キャッシュヒットした場合にキャッシュドライバによって実行されるキャッシュ制御処理の手順を示すフローチャート。
【図１２】キャッシュミスした場合にキャッシュドライバによって実行されるキャッシュ制御処理の手順を示すフローチャート。
【図１３】第割り当て可能なキャッシュブロックが無い場合のキャッシュドライバ１２０が行う処理の手順を示すフローチャート。
【図１４】旧インデックスリンクから選択されたブロック管理データを取り外す前の状態を示す図。
【図１５】旧インデックスリンクから選択されたブロック管理データを取り外した後の状態を示す図。
【図１６】新インデックスリンクの先頭へ選択されたブロック管理データを接続する前の状態を示す図。
【図１７】新インデックスリンクの先頭へ選択されたブロック管理データを接続した状態を示す図。
【図１８】第２の実施形態のキャッシュドライバの構成を示すブロック図。
【図１９】キャッシュ容量を増加させる場合の、キャッシュドライバによってメインメモリに格納されるデータの構成を示す図。
【図２０】更にキャッシュ容量を増加させた場合の、キャッシュドライバ１２０によってメインメモリ１３に格納されるデータの構成を示す図。
【図２１】キャッシュ容量を増加させる場合の、キャッシュドライバの処理の手順の一例を示すフローチャート。
【図２２】キャッシュ容量を減少させる場合の、キャッシュドライバの処理の手順一例を示すフローチャート。
【発明を実施するための形態】
【００１６】
以下、実施の形態について図面を参照して説明する。  
（第１の実施形態）
図１は、実施形態に係る情報処理装置のシステム構成を示す図である。本実施形態の情報処理装置は、パーソナルコンピュータとして実現されている。
【００１７】
図１に示すように、パーソナルコンピュータ１０は、ＣＰＵ（Central processing unit）１１、ＭＣＨ（Memory controller hub）１２、メインメモリ（第１の記憶装置）１３、ＩＣＨ（I/o controller hub）１４、ＧＰＵ（Graphics processing unit）１５、ビデオメモリ（ＶＲＡＭ）１５Ａ、サウンドコントローラ１６、ＢＩＯＳ−ＲＯＭ（Read only memory）１７、ＨＤＤ（Hard disk drive）（第２の記憶装置）１８、ＯＤＤ（Optical disc drive）２０、各種周辺機器２１、ＥＥＰＲＯＭ（Electrically erasable programmable ROM）２２、ＥＣ／ＫＢＣ（Embedded controller/keyboard controller）２３等を備えている。
【００１８】
ＣＰＵ１１は、本情報処理装置の動作を制御するプロセッサであり、ＨＤＤ１８やＯＤＤ２０からメインメモリ１３にロードされる各種プログラムを実行する。このＣＰＵ１１によって実行される各種プログラムの中には、リソース管理を司るＯＳ１１０や、当該ＯＳ１１０の配下で動作する、キャッシュドライバ１２０、各種アプリケーションプログラム１３０、およびキャッシュ容量変更アプリケーション１３１等が存在する。キャッシュドライバ１２０は、ＨＤＤ１８を制御するプログラムである。本情報処理装置は、ＨＤＤ１８よりアクセス速度が速いメインメモリ１３をＨＤＤ１８のキャッシュとして利用することで、ＨＤＤ１８に対するアクセスの高速化を図る。キャッシュ容量変更アプリケーション１３１は、ユーザによって設定されたキャッシュ容量応じた容量情報をＢＩＯＳ−ＲＯＭ１７の所定の領域に書き込む。
【００１９】
また、ＣＰＵ１１は、ＢＩＯＳ−ＲＯＭ１７に格納されたＢＩＯＳも実行する。ＢＩＯＳは、ハードウェア制御のためのプログラムである。以下では、ＢＩＯＳ−ＲＯＭ１７の格納物であるＢＩＯＳ自体についてもＢＩＯＳ１７と表記することがある。
【００２０】
ＭＣＨ１２は、ＣＰＵ１１とＩＣＨ１４との間を接続するブリッジとして動作すると共に、メインメモリ１３をアクセス制御するメモリコントローラとして動作する。また、ＭＣＨ１２は、ＧＰＵ１５との通信を実行する機能を有している。
【００２１】
ＧＰＵ１５は、本情報処理装置に組み込まれ、または、外部接続される表示装置を制御する表示コントローラである。ＧＰＵ１５は、ＶＲＡＭ１５Ａを有し、また、各種プログラムが表示しようとする画像をＣＰＵ１１に代わって描画するアクセラレータを搭載している。
【００２２】
ＩＣＨ１４は、ＨＤＤ１８およびＯＤＤ２０を制御するためのＡＴＡ（AT Attachment）コントローラを内蔵する。ＩＣＨ１４は、ＰＣＩ（Peripheral component interconnect）バスに接続された各種周辺機器２１の制御も行う。また、ＩＣＨ１４は、サウンドコントローラ１６との通信機能も有している。
【００２３】
サウンドコントローラ１６は音源デバイスであり、各種プログラムが再生対象とするオーディオデータを、本情報処理装置に組み込まれ、または、外部接続されるスピーカ等に出力する。
【００２４】
ＥＥＰＲＯＭ２２は、例えば本情報処理装置の個体情報や環境設定情報などを格納するためのメモリデバイスである。そして、ＥＣ／ＫＢＣ２３は、電力管理を行うためのエンベデッドコントローラと、キーボードやポインティングデバイス等の操作によるデータ入力を制御するためのキーボードコントローラとが集積された１チップＭＰＵ（Micro processing unit）である。
【００２５】
図２は、キャッシュドライバ１２０によってメインメモリ１３に格納されるデータの構成を示す図である。
【００２６】
図２に示すように、キャッシュドライバ１２０は、使用順リンクヘッダ２００およびインデックスリンクヘッダポインタ３００が格納される領域、インデックスリンクヘッダ領域４００、ブロック管理領域５００、およびキャッシュ領域６００をメインメモリ１３に確保する。
【００２７】
インデックスリンクヘッダポインタ３００は、インデックスリンクヘッダ領域４００を指す。インデックスリンクヘッダ領域４００内には、８個のインデックスリンクヘッダが格納される。ブロック管理領域５００内には２５６個の管理ブロックデータが格納される。キャッシュ領域６００には、２５６個のキャッシュブロックが格納される。
【００２８】
キャッシュドライバ１２０は、ＨＤＤ１８へのアクセスコマンド（読出し、または書き込み要求）を取得した場合に、使用順リンクヘッダ、複数のインデックスリンクヘッダ、およびブロック管理データに基づいて、必要に応じて複数のキャッシュブロックの内の一つのキャッシュブロックを使用する。
【００２９】
キャッシュ領域６００内のキャッシュブロックの数は、レジストリに格納されているキャッシュ容量を示す容量情報に応じた数である。レジストリは、不揮発性記憶装置（記憶媒体）であるＨＤＤ１８内に格納されている。
【００３０】
ブロック管理領域５００内の各ブロック管理データは、それぞれキャッシュブロックに対応する。インデックスリンクヘッダの数は、キャッシュ容量に対してあらかじめ決められているものとする。装置１０の起動時に、キャッシュドライバ１２０は、容量情報に応じて、インデックスリンク領域４００、ブロック管理領域５００、およびキャッシュ領域６００をメインメモリ１３に確保する。
【００３１】
キャッシュ領域内の各キャッシュブロックは、例えば６４ＫＢといった固定長である。例えば、キャッシュ領域６００は、２５６個のキャッシュブロックによって構成される。各ブロックに、ブロック管理データ５００内のブロック管理データがそれぞれ割り当てられる。
【００３２】
各インデックスリンクヘッダは、ＨＤＤのＩＤとアドレスおよび前記設定数を用いて前記ハッシュ関数によって演算されるインデックスに対応する。例えば、拡張ＬＢＡのキャッシュブロック内オフセット部を除く上位ビットを、インデックス（インデックスヘッダ）の数で割った余りがインデックスである。拡張ＬＢＡは、ＨＤＤ識別子に対応するＨＤＤ  ＩＤと、要求ＬＢＡと結合して生成される。
【００３３】
使用順リンクヘッダ２００、インデックスリンクヘッダポインタ３００、ブロック管理データは、キャッシュブロックを管理するための制御データである。
【００３４】
図３は、ブロック管理データの構成を示す図である。  
ブロック管理データ７００ブロック管理データ７００は、管理データ７１０、インデックスリンク７２０、および使用順リンク７３０等を有する。
【００３５】
管理データ７１０は、タグ部７１１、制御フラグ７１２、ブロックポインタ７１３等を有する。  
制御フラグ７１２は、ブロック管理データに対応するキャッシュブロックが使用中であることを表すフラグや、当該キャッシュブロックに格納されているキャッシュデータと当該キャッシュデータに対応するＨＤＤ１８内のデータとが一致するかを示すフラグを含む。一致しない場合、ダーティーということもある。
【００３６】
ブロックポインタ７１３は、ブロック管理データ７００が対応するキャッシュブロックの先頭アドレスを指す。
【００３７】
位置情報を示すタグ部７１１は、ブロックポインタ７１３が指すキャッシュブロックに格納されているキャッシュデータに対応するＨＤＤ１８内のデータの先頭アドレスに対応する。タグ部７１１は、ＨＤＤ１８内のデータの先頭アドレスからオフセット部を除く上位ビットのデータを、インデックスの数で割った商である。ＨＤＤ１８のアドレスは、拡張ＬＢＡで示されるアドレスである。拡張ＬＢＡは、ＨＤＤ識別子に対応するＨＤＤ  ＩＤと、要求ＬＢＡと結合して拡張ＬＢＡとから生成される。なお、管理データ７００内にＨＤＤ１８内のデータの先頭アドレス、またはＨＤＤ１８内のデータの先頭アドレスからオフセット部を除く上位ビットのデータを格納しても良い。
【００３８】
使用順リンク７３０は、全ブロック管理データをキャッシュブロックへのアクセス順に接続するための情報を有する。また、使用順リンクヘッダ２００は、アクセス順にループ上に接続された全ブロック管理データをループ状に接続するための使用順情報を有する。
【００３９】
インデックスリンク７２０は、全ブロック管理データを対応するキャッシュブロックへのアクセス順にリンクするための情報を有する。インデックスリンクヘッダは、アクセス順にリンクされたブロック管理データをループ状に接続するための情報を有する。
【００４０】
図４は、使用順リンク７３０の構成を示す図である。  
図４に示すように、使用順リンク７３０は、全キャッシュブロックの内で、一つ後にアクセスされたキャッシュブロックに対応するブロック管理データを指す後使用リンクポインタ７３１と、一つ前にアクセスされたキャッシュブロックに対応するブロック管理データを指す前使用リンクポインタ７３２とを含む。
【００４１】
全キャッシュブロックの内で、最新にアクセスされたキャッシュブロックに対応するブロック管理データ内の後使用リンクポインタ７３１は使用順リンクヘッダ２００を指し、最古にアクセスされたキャッシュブロックに対応するブロック管理データ内の後使用リンクポインタは使用順リンクヘッダ２００を指す。
【００４２】
図５は、使用順リンクヘッダ２００の構成を示す図である。  
図５に示すように、使用順リンクヘッダ２００は、最古にアクセスされたキャッシュブロックに対応するブロック管理データを指す後使用リンクポインタ２０１と、最新にアクセスされたキャッシュブロックに対応するブロック管理データの先頭アドレスを指す前使用リンクポインタ２０２とを含む。
【００４３】
図６は、インデックスリンク７２０の構成を示す図である。  
インデックスリンク７２０は、インデックスが同じであるキャッシュブロックの内で、一つ後にアクセスされたキャッシュブロックに対応するブロック管理データを指す後インデックスリンクポインタ７２１と、インデックスが同じであるキャッシュブロックの内で、一つ前にアクセスされたキャッシュブロックに対応するブロック管理データを指す前インデックスリンクポインタ７２２とを含む。ブロック管理データに対応するキャッシュブロックに有効なデータが格納されていない場合は、前インデックスリンクポインタと後インデックスリンクポインタはＮｕｌｌである。
【００４４】
インデックスが同じであるキャッシュブロックの内で、最新にアクセスされたキャッシュブロックに対応するブロック管理データ内の後使用インデックスリンクポインタ７３１はインデックスリンクヘッダを指し、最古にアクセスされたキャッシュブロックに対応するブロック管理データ内の前使用インデックスリンクポインタ７３２はインデックスリンクヘッダを指す。
【００４５】
図７は、インデックスリンクヘッダの構成を示す図である。  
インデックスリンクヘッダは、インデックスが同じであるキャッシュブロックの内で、最古にアクセスされたキャッシュブロックに対応するブロック管理データを指す後インデックスリンクポインタ４０１と、最新にアクセスされたキャッシュブロックに対応するブロック管理データを指す前インデックスリンクポインタ４０２とを有する。各インデックスリンクの初期状態および空の状態は、後インデックスリンクポインタと前インデックスリンクポインタが自身のインデックスリンクヘッダを指す。
【００４６】
図８は、初期状態の制御データを示す図である。
【００４７】
初期状態では、全キャッシュブロックに対応するブロック管理データ７００１、７００２、７００３、…、７２５５、７２５６が使用順リンクによって順に接続され手いる。使用順リンクヘッダ２００内の前使用リンクポインタ２０２が指す使用リンクを含む先頭のブロック管理データ７００１の使用順リンク６３００１の後使用リンクポインタはブロック管理データ７００２の使用順リンクヘッダ６３００２を指している。使用順リンクヘッダ２００内の後使用リンクポインタ２０１が指す使用リンクを含む末尾のブロック管理データ７２５６の使用順リンク６３２５６の前使用リンクポインタは使用順リンクヘッダ２００を指している。使用順リンクヘッダ２００の後使用リンクポインタは末尾のブロック管理データ７２５６の使用順リンクを指している。使用順リンクヘッダ２００の前リンクポインタは先頭のブロック管理データ７００１の使用順リンク６３００１を指している。
【００４８】
図９は、キャッシュ処理が進んだ状態の制御データを示す図である。  
図９に示すように、使用順リンクヘッダ（使用順ＬＨ）内の後使用リンクポインタからアクセスが古いキャッシュブロックに対応するブロック管理データをたどることが可能である。使用順リンクヘッダ（使用順ＬＨ）内の前使用リンクポインタからアクセスが新しいキャッシュブロックに対応するブロック管理データをたどることが可能である。
【００４９】
同一のインデックスにおいて、インデックスリンクヘッダの後インデックスリンクポインタからアクセスが古いキャッシュブロックに対応するブロック管理データをたどることが可能である。同一のインデックスにおいて、インデックスリンクヘッダの前インデックスリンクポインタからアクセスが新しいキャッシュブロックに対応するブロック管理データをたどることが可能である。
【００５０】
キャッシュドライバ１２０がアクセスコマンドを受領した場合の処理を説明する。  
キャッシュドライバ１２０は、アクセスコマンドに含まれるデータブロックの先頭アドレスのオフセット部を除く上位ビットを、インデックス数（この例では３２）で割った商（タグ）と余り（インデックス）を計算する。
【００５１】
なお、キャッシュ滞納のＨＤＤが複数ある場合、キャッシュドライバ１２０は、ＨＤＤ識別子に対応するＨＤＤ  ＩＤを求め、要求ＬＢＡと結合して拡張ＬＢＡを生成する。キャッシュドライバ１２０へのコマンドは、コマンド種別（ＲｅａｄまたはＷｒｉｔｅ）、ＨＤＤ識別子、アクセス範囲（先頭ＬＢＡとセクタサイズ）の情報を含む。説明を簡略化するために、コマンドはひとつのブロックに対するものとする。ＨＤＤ識別子は、キャッシュの対象となるＨＤＤを識別するもので、キャッシュコントローラではＨＤＤ識別子に応じてユニークなＨＤＤ  ＩＤを割り当てる。拡張ＬＢＡは、上位にＨＤＤ  ＩＤ、下位にＬＢＡを配置したものである。ブロックサイズは６４ＫＢであるから、下位７ビットはブロック内のオフセットを表す。拡張ＬＢＡのＯｆｆｓｅｔ部を除く上位ビットを、インデックス数（この例では３２）で割った商（タグ）と余り（インデックス）を計算する。
【００５２】
計算されたインデックスに基づいて、インデックスリンクヘッダを特定する。特定したインデックスリンクヘッダ内の前インデックスリンクポインタ４０２が指すブロック管理データ内のタグ部が計算されたタグと一致するかを判定する。一致すればキャッシュヒットである。
【００５３】
キャッシュヒットの場合、全ブロック管理データが対応するキャッシュブロックのアクセス順にリンクされるように、各ブロック管理データ内の使用順リンクを適宜変更する。すなわち、使用順リンクヘッダ２００内の前使用リンクポインタ２０２がヒットしたブロック管理データを指すようにする。ヒットしたブロック管理データ内の前使用リンクポインタが使用順リンクヘッダを指すようにする。使用順リンクヘッダ２００内の後使用リンクポインタ２０１が最古にアクセスされたキャッシュブロックに対応するブロック管理データを指すようにする。最古にアクセスされたキャッシュブロックに対応するブロック管理データ内の前使用リンクポインタ７３２が、使用順リンクヘッダ２００を指すようにする。
【００５４】
インデックスが同じブロック管理データがアクセス順にリンクされるように、インデックスリンクを変更する。すなわち、インデックスが同じブロック管理データの内、インデックスリンクヘッダ内の前インデックスリンクポインタ４０２がヒットしたブロック管理データを指すようにする。ヒットしたブロック管理データ内の前インデックスリンクポインタがインデックスリンクヘッダを指すようにする。インデックスリンクヘッダ内の後インデックスリンクポインタ４０１が、インデックスが同じブロック管理データの内で最古にアクセスされたキャッシュブロックに対応するブロック管理データを指すようにする。インデックスが同じブロック管理データの内で最古にアクセスされたキャッシュブロックに対応するブロック管理データ内の後インデックスリンクポインタが、インデックスリンクヘッダを指すようにする。
【００５５】
そして、ブロック管理データ内のブロックポインタが指すキャッシュブロック内のキャッシュデータに対し、コマンドに対応するアクセスを行う。
【００５６】
インデックスが同じキャッシュ管理データ内に計算されたタグと一致するタグ部が無かった場合、即ちキャッシュミスの場合、使用順リンクヘッダ内の後リンクポインタ２０１が指すブロック管理データから使用順リンクに基づいて、アクセスの古い順からブロック管理データをたどり、キャッシュデータを割り当て可能なキャッシュブロックを探す。ここで、割り当て可能とは、例えば当該キャッシュブロックが使用中でなく、ダーティーでもないものを指す。
【００５７】
割り当て可能なキャッシュデータを探した後、全ブロック管理データが対応するキャッシュブロックのアクセス順にリンクされるように、使用順リンクを変更する。すなわち、使用順リンクヘッダ内の前リンクポインタ２０２が割り当て可能なキャッシュブロックに対応するブロック管理データを指すようにする。割り当て可能なキャッシュブロックに対応するブロック管理データ内の前使用リンクヘッダが使用順リンクヘッダを指すようにする。使用順リンクヘッダ内の後リンクポインタ２０１が最古にアクセスされたキャッシュブロックに対応するブロック管理データを指すようにする。最古にアクセスされたキャッシュブロックに対応するブロック管理データ内の後使用リンクポインタが、使用順リンクヘッダを指すようにする。
【００５８】
インデックスが同じブロック管理データがアクセス順にリンクされるように、インデックスリンクを変更する。すなわち、割り当て可能なキャッシュブロックに対応するブロック管理データの両インデックスポインタがＮｕｌｌ以外の値であれば対応するインデックスリンクから外し、新たに格納するデータに対応するインデックスリンクヘッダの先頭に接続する。
【００５９】
そして、アクセスに対応するデータを割り当て可能なキャッシュブロックに書き込む。
【００６０】
図１０は、キャッシュドライバ１２０によって実行されるキャッシュ制御処理の手順を示すブロック図である。  
ＨＤＤの第１のブロックへのアクセスが要求された場合、キャッシュドライバ１２０は、第１のブロックの先頭アドレスのオフセット部を除く上位２５ビットを、インデックス数（この例では３２）で割った商（タグ）と余り（インデックス）を計算する（ステップＢ１１）。
【００６１】
キャッシュドライバ１２０は、インデックスに基づいてインデックスリンクヘッダ（以下、第１のインデックスリンクヘッダ）を特定する（ステップＢ１２）。
【００６２】
キャッシュドライバ１２０は、ブロック管理データ内の後インデックスリンクポインタ（ＰＩＬポインタ）が第１のインデックスリンクヘッダ（第１のＩＬヘッダ）を指しているかを判定する（ステップＢ１３）。後インデックスリンクポインタが第１のインデックスリンクヘッダを指していると判定した場合（ステップＢ１３のＹｅｓ）、キャッシュドライバ１２０は、キャッシュミスと判定する(ステップＢ１７)。
【００６３】
後インデックスリンクポインタが第１のインデックスリンクヘッダを指していると判定した場合（ステップＢ１３のＮｏ）、キャッシュドライバ１２０は、後インデックスリンクポインタが指すブロック管理データを選択する（ステップＢ１４）。キャッシュドライバ１２０は、選択されたブロック管理データ内のタグ部と計算されたタグと一致するかを判定する（ステップＢ１５）。一致していると判定した場合（ステップＢ１５のＹｅｓ）、キャッシュドライバ１２０は、キャッシュヒットと判定する（ステップＢ１６）。一致していないと判定した場合（ステップＢ１５のＮｏ）、キャッシュドライバ１２０は、ステップＢ１３からの処理を順次実行する。
【００６４】
（キャッシュヒット）
図１１は、キャッシュヒットした場合にキャッシュドライバ１２０によって実行されるキャッシュ制御処理の手順を示すフローチャートである。  
キャッシュドライバ１２０は、キャッシュヒットしたキャッシュデータに対応するブロック管理データを第１のブロック管理データとする。
【００６５】
（ステップＢ２１：使用順リンクヘッダおよび使用順リンクの変更）  
キャッシュドライバ１２０は、使用順リンクヘッダおよび第１のインデックスリンクヘッダに対応するブロック管理データ内の使用順リンクを適宜つなぎ替える。
【００６６】
（ステップＢ２２：第１のインデックスリンクヘッダおよびインデックスリンクの変更）  
キャッシュドライバ１２０は、第１のインデックスリンクヘッダおよびインデックスリンクを適宜つなぎ替える。
【００６７】
（ステップＢ２３：キャッシュデータへのアクセス）  
キャッシュドライバ１２０は、第１のブロック管理データ内のブロックポインタが指すキャッシュブロックに対して、アクセスコマンドに応じたアクセスを行う。
【００６８】
以上で、キャッシュヒットした場合のキャッシュドライバ１２０の処理の説明を終了する。
【００６９】
（キャッシュミス）
図１２は、キャッシュミスした場合にキャッシュドライバ１２０によって実行されるキャッシュ制御処理の手順を示すフローチャートである。  
キャッシュドライバ１２０は、使用順リンクヘッダ２００を選択する（ステップＢ３１）。キャッシュドライバ１２０は、使用順リンクヘッダ２００内の後使用リンクポインタ２０１が使用順リンクヘッダ２００を指しているかを判定する（ステップＢ３２）。後使用リンクポインタ２０１が使用順リンクヘッダ２００を指していると判定した場合（ステップＢ３２のＹｅｓ）、キャッシュドライバ１２０は、割り付けに失敗したと判定する（ステップＢ４１）。後使用リンクポインタ２０１が使用順リンクヘッダ２００を指していないと判定した場合（ステップＢ３２のＮｏ）、キャッシュドライバ１２０は、後使用リンクポインタ２０１が指すブロック管理データを選択する（ステップＢ３３）。キャッシュドライバ１２０は、選択されたブロック管理データに対応するキャッシュブロックにキャッシュデータを割り当てることが可能であるかを判定する（ステップＢ３４）。
【００７０】
割り当て可能ではないと判定した場合（ステップＢ３４のＮｏ）、キャッシュドライバ１２０は、選択されたブロック管理データ内の後使用リンクポインタ７３１について、ステップＢ３２からの処理を順次実行する。
【００７１】
割り当て可能であると判定した場合（ステップＢ３４のＹｅｓ）、キャッシュドライバ１２０は、前インデックスリンクポインタおよび後インデックスリンクポインタがＮｕｌｌであるかを判定する（ステップＢ３５）。前インデックスリンクポインタおよび後インデックスリンクポインタがＮｕｌｌではないと判定した場合（ステップＢ３５のＮｏ）、キャッシュドライバ１２０は、選択されたブロック管理データが属しているインデックスリンクから選択されたブロック管理データを外す（ステップＢ４２）。
【００７２】
前インデックスリンクポインタおよび後インデックスリンクポインタがＮｕｌｌであると判定した場合（ステップＢ３５のＹｅｓ）、またはステップＢ４１の処理を行った場合、キャッシュドライバ１２０は、管理データ７１０内のデータを適宜変更する（ステップＢ３６）。キャッシュドライバ１２０は、選択されたブロック管理データ内のタグ部７１１にステップＢ１１で計算されたタグを格納する。また、アクセスがライトアクセスの場合、キャッシュドライバ１２０は、制御フラグをダーティーを示す値にする。
【００７３】
キャッシュドライバ１２０は、選択されたブロック管理データをステップＢ１１で計算されたインデックスに対応するインデックスリンクの先頭に接続する（ステップＢ３７）。キャッシュドライバ１２０は、選択されたブロック管理データを使用順リンクから取り外す（ステップＢ３８）。キャッシュドライバ１２０は、選択されたブロック管理データを使用順リンクの先頭に接続する（ステップＢ３９）。キャッシュドライバ１２０は、選択されたブロック管理データ内のブロックポインタ７１３が指すキャッシュブロックにアクセスに対応するデータを格納する（ステップＢ４０）。
【００７４】
（割り当て可能なキャッシュブロックが無い場合）
割り当て可能なキャッシュブロックが無いと判定された場合の処理の処理について説明する。  
図１３は、割り当て可能なキャッシュブロックが無い場合のキャッシュドライバ１２０が行う処理の手順を示すフローチャートである。
【００７５】
キャッシュドライバ１２０は、使用順リンクヘッダ２００を選択する（ステップＢ３１）。キャッシュドライバ１２０は、使用順リンクヘッダ２００内の後使用リンクポインタ２０１が指すブロック管理データを選択する（ステップＢ５２）。キャッシュドライバ１２０は、選択されたブロック管理データ内の制御フラグに基づいてキャッシュデータがダーティーであるかを判定する（ステップＢ５３）。ダーティーであると判定した場合（ステップＢ５３のＹｅｓ）、選択されたブロック管理データの後使用リンクポインタ７３１が指すブロック管理データを選択する（ステップＢ５２）。そして、キャッシュドライバ１２０は、ステップＢ５３からの処理を順次実行する。
【００７６】
ダーティーでないと判定した場合（ステップＢ５３のＮｏ）、キャッシュドライバ１２０は、キャッシュドライバ１２０は、選択されたブロック管理データが属しているインデックスリンクから選択されたブロック管理データを外す（ステップＢ５４）。キャッシュドライバ１２０は、管理データ７１０内のデータを適宜変更する（ステップＢ５５）。キャッシュドライバ１２０は、選択されたブロック管理データ内のタグ部７１１にステップＢ１１で計算されたタグを格納する。また、アクセスがライトアクセスの場合、キャッシュドライバ１２０は、制御フラグをダーティーを示す値にする。
【００７７】
キャッシュドライバ１２０は、選択されたブロック管理データをステップＢ１１で計算されたインデックスに対応するインデックスリンクの先頭に接続する（ステップＢ５６）。キャッシュドライバ１２０は、選択されたブロック管理データを使用順リンクから削除する（ステップＢ５７）。キャッシュドライバ１２０は、選択されたブロック管理データを使用順リンクの先頭に接続する（ステップＢ５８）。キャッシュドライバ１２０は、選択されたブロック管理データ内のブロックポインタ７１３が指すキャッシュブロックにアクセスに対応するデータを格納する（ステップＢ５９）。
【００７８】
（旧インデックスリンクからの取り外し）
ステップＢ４２およびステップＢ５４の旧インデックスリンクからの取り外しについて説明する。  
図１４は、旧インデックスリンクから選択されたブロック管理データを取り外す前の状態を示す図である。図１５は、旧インデックスリンクから選択されたブロック管理データを取り外した後の状態を示す図である。
【００７９】
図１４に示すように、第１のインデックスリンクヘッダ４００Ａに対応するインデックスリンクに第１のブロック管理データ７００Ａ、第２のブロック管理データ７００Ｂ、および第３のブロック管理データ７００Ｃが順番に接続されている。第２のブロック管理データ７００Ｂが新たなキャッシュデータが格納されるキャッシュブロックに対応するブロック管理データである。
【００８０】
第１のブロック管理データ７００Ａの前インデックスリンクポインタ７２２Ａと第２のブロック管理データ７００Ｂの後インデックスリンクポインタ７２１Ｂとによって、第１のブロック管理データ７００Ａと第２のブロック管理データ７００Ｂとが相互に接続されている。第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂと第３のブロック管理データ７００Ｃの後インデックスリンクポインタ７２１Ｃとによって、第２のブロック管理データ７００Ｂと第３のブロック管理データ７００Ｃとが相互に接続されている。
【００８１】
旧インデックスリンクから選択されたブロック管理データを取り外す場合、キャッシュドライバ１２０は、第２のブロック管理データ７００Ｂの後インデックスリンクポインタ７２１Ｂが指す第１のブロック管理データ７００Ａと、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂが指す第３のブロック管理データ７００Ｃとを接続する。接続するとは、第１のブロック管理データ７００Ａの前インデックスリンクポインタ７２２Ａが第３のブロック管理データ７００Ｃを指すようにし、第３のブロック管理データ７００Ｃの後インデックスリンクポインタ７２１Ｃが第１のブロック管理データ７００Ａを指すようにすることである。
【００８２】
なお、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂが第１のインデックスリンクヘッダ４００Ａを指す場合、キャッシュドライバ１２０は、第１のインデックスリンクヘッダ４００Ａと、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂが指す第３のブロック管理データ７００Ｃとを接続する。
【００８３】
また、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂが第１のインデックスリンクヘッダ４００Ａを指す場合、キャッシュドライバ１２０は、第１のインデックスリンクヘッダ４００Ａと、第２のブロック管理データ７００Ｂの後インデックスリンクポインタ７２１Ｂが指す第１のブロック管理データ７００Ａとを接続する。
【００８４】
（新インデックスリンクの先頭への接続）
ステップＢ３７およびステップＢ５６の旧インデックスリンクからの取り外しについて説明する。  
図１６は、新インデックスリンクの先頭へ選択されたブロック管理データを接続する前の状態を示す図である。図１７は、新インデックスリンクの先頭へ選択されたブロック管理データを接続した状態を示す図である。
【００８５】
図１６に示すように、第２のインデックスリンクヘッダ４００Ｂに対応するインデックスリンクの先頭に第４のブロック管理データ７００Ｄが接続されている。第２のインデックスリンクヘッダ４００Ｂに対応するインデックスルリンクの先頭に、第２のブロック管理データ７００Ｂが接続される。
【００８６】
第２のインデックスリンクヘッダ４００Ｂの前インデックスリンクポインタ４０２Ｂと第４のブロック管理データ７００Ｄの後インデックスリンクポインタ７２１Ｄとによって、第２のインデックスリンクヘッダ４００Ｂと第４のブロック管理データ７００Ｄとが相互に接続されている。
【００８７】
第２のインデックスリンクヘッダ４００Ｂの前インデックスリンクポインタ４０２Ｂと第４のブロック管理データ７００Ｄの後インデックスリンクポインタ７２１Ｄとによって、第２のインデックスリンクヘッダ４００Ｂと第４のブロック管理データ７００Ｄとが相互に接続されている。
【００８８】
図１７に示すように、第２のインデックスリンクヘッダ４００Ｂに対応するインデックスリンクの先頭に第２のブロック管理データ７００Ｂが接続される。
【００８９】
インデックスリンクの先頭に接続するとは、第２のインデックスリンクヘッダ４００Ｂの前インデックスリンクポインタ４０２Ｂが指していた第４のブロック管理データ７００Ｄの後インデックスリンクポインタ７２１Ｄが第２のブロック管理データ７００Ｂを指すようにし、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂが第４のブロック管理データ７００Ｄを指すようにし、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂの後インデックスリンクポインタ７２１Ｂが第２のインデックスリンクヘッダ４００Ｂを指すようにし、第２のインデックスリンクヘッダ４００Ｂの前インデックスリンクポインタ４０２Ｂが第２のブロック管理データを指すようにすることである。
【００９０】
なお、第２のインデックスリンクヘッダ４００Ｂの前インデックスリンクポインタ４０２Ｂが第２のインデックスリンクヘッダ４００Ｂを指している場合、第２のブロック管理データ７００Ｂの前インデックスリンクポインタ７２２Ｂが第２のインデックスリンクヘッダ４００Ｂを指すようにする。
【００９１】
なお、ステップＢ３８のステップＢ５７の使用順リンクからの取り外しは、インデックスリンクからの取り外しと同様である。また、ステップＢ３９のステップＢ５８の使用順リンクの先頭への接続は、インデックスリンクの先頭への接続と同様である。
【００９２】
本実施形態によれば、ブロック管理データ内の前記インデックスリンクは、前記ブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応する前記第２の記憶装置内のデータが格納されているアドレスおよび前記設定数を用いてハッシュ関数によって求められるインデックスが同じである第１のキャッシュブロックの内で、一つ前にアクセスされたキャッシュブロックに対応するブロック管理データを指す前インデックスリンクポインタと、一つ後にアクセスされたキャッシュブロックに対応するブロック管理データを指す後インデックスリンクポインタとを含み、前記使用順リンクが、全キャッシュブロックの内で、一つ前にアクセスされたキャッシュブロックに対応するブロック管理データを指す前使用リンクポインタと、一つ後にアクセスされたキャッシュブロックに対応するブロック管理データを指す後使用リンクポインタとを含むことで、インデックスに対応するブロック管理データを増減することが可能になるので、特定のインデックスに対応するキャッシュブロックにアクセスが集中しても、ヒット率の低下を抑制することが可能になる。
【００９３】
また、ブロック管理データをｎ個のインデックスに振り分けているため、ヒット／ミス判定を行うブロック管理データは、期待値で全ブロックの１／ｎで済む。キャッシュミスし、新たなブロックにキャッシュデータを割り当てるとき、ブロック管理データがキャッシュブロック全体の使用順にリンクされているため、キャッシュヒット率の向上が図れる。インデックスリンクヘッダに対応するブロック管理データがアクセス時間順にリンクされているため、ヒットしている場合の検索時間が早くなる。
【００９４】
（第２の実施形態）
キャッシュ容量変更アプリケーション１３１を用いて、装置の稼働中にキャッシュ容量を変更することが可能である。  
図１８は、第２の実施形態のキャッシュドライバ１２０の構成を示すブロック図である。キャッシュドライバ１２０は、キャッシュ容量変更モジュール１２０１を有する。キャッシュ容量変更モジュール１２０１は、稼働中に、キャッシュ容量変更アプリケーション１３１によって要求された、キャッシュ容量を変更する機能を有する。
【００９５】
従来、ディレクトリがインデックス数×Ｗａｙ数の表形式であり、キャッシュ容量を増減させる場合は、インデックス数あるいはＷａｙ数を増減させる必要がある。本実施形態の場合、ディレクトリがリスト構造であるため、キャッシュ容量の増減が容易である。
【００９６】
ヒット・ミス判定を行う対象ブロック数を最適化するために、小さいキャッシュ容量では少ないインデックス数、大きいキャッシュ容量では多いインデックス数への変更も可能とする。この場合、キャッシュブロック数とインデックス数の関係はあらかじめ決められているものとする。
【００９７】
キャッシュ容量変更アプリケーション１３１が、キャッシュコントローラの状態表示や、ユーザあるいは他のプログラムからのキャッシュ容量の変更要求を受け付ける。キャッシュ容量変更アプリケーション１３１が、変更要求されたキャッシュ容量に応じた容量情報をキャッシュドライバ１２０が参照可能な記憶媒体に書き込む。キャッシュ容量変更アプリケーション１３１が終了するとき、或いは容量情報を書き込んだ後、キャッシュ容量変更アプリケーション１３１は、キャッシュドライバ１２０に対して、容量情報の参照を要求するための通知を発行する。
【００９８】
キャッシュ容量変更モジュール１２０１は、アプリケーションプログラムからの通知を受け付けると、容量情報が書き込まれている領域を参照する。キャッシュ容量変更モジュール１２０１は、キャッシュ容量を変更する必要がある場合は、キャッシュ容量変更の処理を行う。
【００９９】
図１９は、６Ｍバイトのキャッシュ容量を増加させる場合の、キャッシュドライバ１２０によってメインメモリ１３に格納されるデータの構成を示す図である。  
図１９に示すように、メモリ１３内にインデックスリンクヘッダ領域４００Ｃ、ブロック管理領域５００Ｂ、およびキャッシュ領域６００Ｂが更に確保されている。インデックスリンクヘッダ領域４００Ｃには、１６個のインデックスリンクヘッダが格納される。ブロック管理領域５００Ｂは、新たに追加されるキャッシュ領域６００Ｂ内のキャッシュブロック数に応じて２５６個の管理ブロックデータを有する。キャッシュ領域６００Ｂ内は２５６個のキャッシュブロックを有する。インデックスリンクヘッダポインタ３００は、インデックスリンクヘッダ領域４００Ｃを指している。
【０１００】
インデックス数が８個から１６個に増えているので、キャッシュ容量変更モジュール１２０１は、既存のインデックスリンクヘッダ領域４００を空にし、使用順リンクヘッダ内の最新使用リンクポインタおよび使用順リンクに基づいてアクセスが新しいキャッシュブロックに対応するブロック管理データを順にアクセスする。キャッシュ容量変更モジュール１２０１は、アクセスしたブロック管理データ内のインデックスリンクを新たなインデックス数およびブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応するＨＤＤ内のデータのアドレスに基づいて変更する。
【０１０１】
図２０は、更に６Ｍバイトのキャッシュ容量を増加させた場合の、キャッシュドライバ１２０によってメインメモリ１３に格納されるデータの構成を示す図である。  
図２０に示すように、メモリ１３内にインデックスリンクヘッダ領域４００Ｄ、ブロック管理領域５００Ｃ、およびキャッシュ領域６００Ｃが更に確保されている。インデックスリンクヘッダ領域４００Ｃには、３２個のインデックスリンクヘッダが格納される。ブロック管理領域５００Ｃは、新たに追加されるキャッシュ領域６００Ｃ内のキャッシュブロック数に応じて２５６個の管理ブロックデータを有する。キャッシュ領域６００Ｃ内は２５６個のキャッシュブロックを有する。インデックスリンクヘッダポインタ３００は、インデックスリンクヘッダ領域４００Ｄを指している。
【０１０２】
なお、更に６Ｍバイトのキャッシュ容量を増加させた場合、インデックス数は増加させないで、インデックスリンクヘッダポインタ３００は、インデックスリンクヘッダ領域４００Ｄを指したままにする。
【０１０３】
図２１は、キャッシュ容量を増加させる場合の、キャッシュ容量変更モジュール１２０１の処理の手順を示すフローチャートである。
【０１０４】
キャッシュ容量を増加させる場合、キャッシュ容量変更モジュール１２０１は、増加後のキャッシュ容量と現在のキャッシュ容量との差に応じた数のキャッシュブロックと、増加数分のキャッシュブロックの増加数分のブロック管理データが格納される領域とをメインメモリ内に確保する（ステップＢ６１）。増加数は、増加後のキャッシュ容量と現在のキャッシュ容量との差に応じて決定される。なお、インデックス数も合わせて増加させる場合、キャッシュ容量変更モジュール１２０１は、追加のインデックスリンクヘッダが格納される領域をメインメモリに確保する。また、インデックス数が増加する場合、キャッシュ容量変更モジュール１２０１は、増加分のインデックスヘッダが格納される領域をメインメモリに確保する。
【０１０５】
インデックス数が増えた場合、キャッシュ容量変更モジュール１２０１は、既存のインデックスリンクヘッダを空にし、使用順リンクヘッダ内の最新使用リンクポインタおよび使用順リンクに基づいてアクセスが新しいキャッシュブロックに対応するブロック管理データを順にアクセスする。キャッシュ容量変更モジュール１２０１は、アクセスしたブロック管理データ内のインデックスリンクを新たなインデックス数およびブロックポインタが指すキャッシュブロックに格納されているキャッシュデータに対応するＨＤＤ内のデータのアドレスに基づいて変更する（ステップＢ６２）。
【０１０６】
これにより、インデックスリンクヘッダには最近アクセスされた順にブロック管理データがリンクされるようになる。新たに確保されたブロック管理データ内のインデックスリンク内の前・後インデックスリンクポインタをＮＵＬＬにし、使用順リンクを使用順リンクヘッダの末尾に順次接続する。
【０１０７】
（第３の実施形態）
図２２は、キャッシュ容量を減少させる場合の、キャッシュ容量変更モジュール１２０１の処理の手順を示すフローチャートである。
【０１０８】
キャッシュ容量変更モジュール１２０１は、減少するキャッシュ容量に応じた数のキャッシュブロックを選択する（ステップＢ７１）。このキャッシュブロックは、減少対象になる。
【０１０９】
減少対象のキャッシュブロックのあるキャッシュブロックが解放可能な場合、使用順リンクヘッダおよび使用順リンクによって構成される使用順リンク内のブロック管理データから解放可能なブロックに対応するブロック管理データを除いたブロック管理データが、対応するキャッシュブロックのアクセス順に、リンクされるように使用順リンクヘッダおよび使用順リンクを変更する（ステップＢ７２）。
【０１１０】
インデックスリンクヘッダおよびインデックスリンクによって構成されるインデックスリンク内のブロック管理データから解放可能なブロックに対応するブロック管理データを除いたブロック管理データが、対応するキャッシュブロックのアクセス順に、リンクされるようにインデックスリンクヘッダおよびインデックスリンクを変更する（ステップＢ７３）。
【０１１１】
新たなキャッシュブロックの割り当ては使用順リンクヘッダ内の最古使用リンクポインタおよび使用順リンクに基づいて対応するキャッシュブロックのアクセス順にブロック管理データをたどるので、削除対象のキャッシュブロックにキャッシュデータが割り当てられることがなくなる。
【０１１２】
減少対象のキャッシュブロックが解放不能な場合は、解放可能となった時点で、使用順リンクヘッダ、使用順リンク、インデックスリンクヘッダ、インデックスリンクを変更する。
【０１１３】
減少対象の全キャッシュブロックが開放可能になり、インデックス数も減少させる場合、キャッシュ容量変更モジュール１２０１は、既存のインデックスリンクヘッダを空にする（ステップＢ７４）。キャッシュ容量変更モジュール１２０１は、使用順リンクヘッダ内の最新使用リンクポインタおよび使用順リンクに基づいてアクセスが新しいキャッシュブロックに対応するブロック管理データに順にアクセスする。キャッシュ容量変更モジュール１２０１は、新たなインデックス数に基づいて、アクセスしたブロック管理データ内のインデックスリンクを使用してインデックスリンクの先頭に順次接続する。これにより、各インデックスヘッダには管理ブロックがアクセスされた順に接続される。（ステップＢ７５）。
【０１１４】
そして、キャッシュ容量変更モジュール１２０１は、減少対象のキャッシュブロックとブロック管理データを解放する（ステップＢ７５）。なお、インデックス数を減少させない場合、ステップＢ７４，６５の処理は、行わない。
【０１１５】
なお、本実施形態では、内蔵されたＨＤＤ内のデータをキャッシュ対象としていたが、ＵＳＢ（Universal Serial Bus）やＩＥＥＥ１３９４によって外部接続された記憶装置内のデータをキャッシュ対象とすることもできる。
【０１１６】
本実施形態のキャッシュ制御処理に係わる各種処理はキャッシュドライバ１２０によって実現されていたがハードウェア（キャッシュコントローラ）によって実現することも可能である。
【０１１７】
本実施形態のキャッシュ制御処理に係わる各種処理はコンピュータプログラムによって実現することができるので、このコンピュータプログラムを格納したコンピュータ読み取り可能な記憶媒体を通じてこのコンピュータプログラムを通常のコンピュータにインストールして実行するだけで、本実施形態と同様の効果を容易に実現することができる。
【０１１８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１１９】
１０…パーソナルコンピュータ（情報処理装置）、１１…ＣＰＵ、１３…メインメモリ（第１の記憶装置）、１７…ＨＤＤ１８（第２の記憶装置）、１７…ＲＯＭ、１７…ＢＩＯＳ、１２０…キャッシュドライバ、１３１…キャッシュ容量変更アプリケーション、２００…使用順リンクヘッダ、２０１…後使用リンクポインタ、２０１…後使用リンクポインタ、２０２…前使用リンクポインタ、３００…インデックスリンクヘッダポインタ、４００…インデックスリンクヘッダ領域、４０１…後インデックスリンクポインタ、４０２…前インデックスリンクポインタ、５００…ブロック管理領域、６００…キャッシュ領域、７００…ブロック管理データ、７１０…管理データ、７１１…タグ部、７１２…制御フラグ、７１３…ブロックポインタ、７２０…インデックスリンク、７２０Ａ…インデックスリンク、７２１…後インデックスリンクポインタ、７２２…前インデックスリンクポインタ、７３０…使用順リンク、７３１…後使用リンクポインタ、７３２…後使用リンクポインタ。
【図１】
2014071712.tif 000003
【図２】
2014071712.tif 000004
【図３】
2014071712.tif 000005
【図４】
2014071712.tif 000006
【図５】
2014071712.tif 000007
【図６】
2014071712.tif 000008
【図７】
2014071712.tif 000009
【図８】
2014071712.tif 000010
【図９】
2014071712.tif 000011
【図１０】
2014071712.tif 000012
【図１１】
2014071712.tif 000013
【図１２】
2014071712.tif 000014
【図１３】
2014071712.tif 000015
【図１４】
2014071712.tif 000016
【図１５】
2014071712.tif 000017
【図１６】
2014071712.tif 000018
【図１７】
2014071712.tif 000019
【図１８】
2014071712.tif 000020
【図１９】
2014071712.tif 000021
【図２０】
2014071712.tif 000022
【図２１】
2014071712.tif 000023
【図２２】
2014071712.tif 000024