(57)【特許請求の範囲】
【請求項１】
磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ装置であって、
前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素のみが連続して配置された一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるキャッシュ管理手段と、
前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御手段と
を備えたことを特徴とするＲＡＩＤ装置。
【請求項２】
前記キャッシュ管理手段は、前記リストから要素を削除する場合に、該要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、該要素の前後の要素を含む要素の一群であって、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素のみが連続して配置された一群の、両端の要素を接続するリンクを設けることを特徴とする請求項１に記載のＲＡＩＤ装置。
【請求項３】
前記キャッシュ管理手段は、前記リストへ要素を挿入する場合に、前記リストに属する要素を優先順位が低い順に探索し、挿入する要素に対応するデータブロックが書き出される磁気ディスク装置と同一の磁気ディスク装置へ書き出されるデータブロックに対応する要素の手前を挿入位置とすることを特徴とする請求項１または２に記載のＲＡＩＤ装置。
【請求項４】
磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ制御プログラムであって、
前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素のみが連続して配置された一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるキャッシュ管理手順と、
前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御手順と
をコンピュータに実行させることを特徴とするＲＡＩＤ制御プログラム。
【請求項５】
磁気ディスクへ書き出すべきデータブロックを一時記憶するキャッシュを管理するキャッシュ管理方法であって、
前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素のみが連続して配置された一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるリスト編成工程と、
前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御工程と
を含んだことを特徴とするキャッシュ管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ装置、ＲＡＩＤ制御プログラムおよびキャッシュ管理方法に関し、特に、大容量のキャッシュを備えた場合においても、キャッシュの管理に係る処理時間の増大を抑制することができるＲＡＩＤ装置、ＲＡＩＤ制御プログラムおよびキャッシュ管理方法に関する。
【背景技術】
【０００２】
ＲＡＩＤ（Redundant Arrays of Inexpensive Disks）装置等は、一般に、ホストからの要求に対する応答速度を向上させるためのキャッシュを備える。例えば、ホストからデータブロックの書き込み要求があった場合、ＲＡＩＤ装置は、書き込み要求のあったデータブロックをキャッシュに格納し、その段階でホストに対して、書き込みが完了した旨の応答を返し、その後、所定のタイミングで磁気ディスク装置への書き込み処理を実行する。
【０００３】
このように、ホストが備えるＣＰＵ（Central Processing Unit）等と比較して動作が低速な磁気ディスク装置への書き込みを遅延させ、キャッシュへの格納をもって書き込み完了の応答を返すことは、ホストの処理待ち時間を減少させ、システム全体の性能を向上させる。
【０００４】
キャッシュには、ホストからの読み取り要求に対する応答速度を向上させる効果もあり、性能向上のためには、なるべく多くのデータブロックをキャッシュに格納しておくことが好ましいが、キャッシュの容量は有限である。そこで、多くのＲＡＩＤ装置は、有限のキャッシュを有効活用するため、ＬＲＵ（Least Recently Used）論理に基づいてキャッシュに格納されたデータブロックを管理している（例えば、特許文献１および２を参照）。
【０００５】
ホスト上で動作する各種プログラムによるデータアクセスには、局所性があることが知られており、キャッシュに格納されてから時間が経っていないデータブロックほど、ホストから再びアクセス要求がなされる可能性が高い。ＬＲＵ論理を用いることにより、ホストからアクセス要求がある可能性の低いデータブロックを優先してキャッシュから追い出し、有限のキャッシュを効率よく活用することができる。
【０００６】
【特許文献１】特開２００３−２２８４６１号公報
【特許文献２】特開平１１−３３８７７５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、近年、ＲＡＩＤ装置の性能向上への要求が高まり、１００ギガバイト以上の大容量のキャッシュを搭載するＲＡＩＤ装置が出現している。ＬＲＵ論理に基づくデータブロックの管理に係る処理時間は、従来は、無視できるほどに小さいものであったが、このようにキャッシュが大容量化し、キャッシュに格納されるデータブロックの数が増大するにつれて、処理性能に大きく影響を与えるようになりつつある。
【０００８】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、大容量のキャッシュを備えた場合においても、キャッシュの管理に係る処理時間の増大を抑制することができるＲＡＩＤ装置、ＲＡＩＤ制御プログラムおよびキャッシュ管理方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、本発明の一つの態様では、磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ装置であって、前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるキャッシュ管理手段と、前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御手段とを備えたことを特徴とする。
【００１０】
また、本発明の他の態様では、磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ制御プログラムであって、前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるキャッシュ管理手順と、前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御手順とをコンピュータに実行させることを特徴とする。
【００１１】
また、本発明の他の態様では、磁気ディスクへ書き出すべきデータブロックを一時記憶するキャッシュを管理するキャッシュ管理方法であって、前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるリスト編成工程と、前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御工程とを含んだことを特徴とする。
【００１２】
この発明の態様によれば、磁気ディスクへの書き出しが必要なディスクブロックに対応する要素を優先順位順に配列したリストを探索して書き出し対象のデータブロックを選定する場合に、書き出し不能な磁気ディスクが書き出し先であるデータブロックに対応する要素にリンクがあれば、そのリンクを辿って、書き出し不能な磁気ディスクが書き出し先であるデータブロックに対応する要素の一群を一気に読み飛ばすことができるように構成したので、キャッシュの大容量化により、多数のデータブロックの管理が必要になった場合であっても、効率よくキャッシュを管理し、キャッシュの管理に係る処理時間の増大を抑制することができる。
【００１３】
また、本発明の他の態様では、上記の発明の態様において、前記キャッシュ管理手段は、前記リストから要素を削除する場合に、該要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、該要素の前後の要素を含む要素の一群であって、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群の、両端の要素を接続するリンクを設けることを特徴とする。
【００１４】
この発明の態様によれば、リストから要素を削除する場合に、削除する要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、それらを含む、データブロックの書き出し先が同一の磁気ディスク装置である要素の両端にリンクを設定するように構成したので、リンクが断片化することを防止し、キャッシュの管理に係る処理時間の増大を抑制することができる。
【００１５】
また、本発明の他の態様では、上記の発明の態様において、前記キャッシュ管理手段は、前記リストへ要素を挿入する場合に、前記リストに属する要素を優先順位が低い順に探索し、挿入する要素に対応するデータブロックが書き出される磁気ディスク装置と同一の磁気ディスク装置へ書き出されるデータブロックに対応する要素の手前を挿入位置とすることを特徴とする。
【００１６】
この発明の態様によれば、リストに要素を挿入する場合に、データブロックの書き出し先の磁気ディスク装置が同一である要素が連続することになる位置へ挿入するように構成したので、リンクが断片化することを防止し、キャッシュの管理に係る処理時間の増大を抑制することができる。
【発明の効果】
【００１７】
本発明の一つの態様によれば、磁気ディスクへの書き出しが必要なディスクブロックに対応する要素を優先順位順に配列したリストを探索して書き出し対象のデータブロックを選定する場合に、書き出し不能な磁気ディスクが書き出し先であるデータブロックに対応する要素にリンクがあれば、そのリンクを辿って、書き出し不能な磁気ディスクが書き出し先であるデータブロックに対応する要素の一群を一気に読み飛ばすことができるように構成したので、キャッシュの大容量化により、多数のデータブロックの管理が必要になった場合であっても、効率よくキャッシュを管理し、キャッシュの管理に係る処理時間の増大を抑制することができるという効果を奏する。
【００１８】
また、本発明の他の態様によれば、リストから要素を削除する場合に、削除する要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、それらを含む、データブロックの書き出し先が同一の磁気ディスク装置である要素の両端にリンクを設定するように構成したので、リンクが断片化することを防止し、キャッシュの管理に係る処理時間の増大を抑制することができるという効果を奏する。
【００１９】
また、本発明の他の態様によれば、リストに要素を挿入する場合に、データブロックの書き出し先の磁気ディスク装置が同一である要素が連続することになる位置へ挿入するように構成したので、リンクが断片化することを防止し、キャッシュの管理に係る処理時間の増大を抑制することができるという効果を奏する。
【発明を実施するための最良の形態】
【００２０】
以下に添付図面を参照して、本発明に係るＲＡＩＤ装置、ＲＡＩＤ制御プログラムおよびキャッシュ管理方法の好適な実施の形態を詳細に説明する。
【実施例】
【００２１】
まず、従来のＲＡＩＤ装置におけるキャッシュ管理方法の概要について説明する。図１７は、従来のキャッシュ管理方法の概要について説明するための説明図である。同図は、ホストから書き込み要求があったが、まだ磁気ディスク装置への書き出しが行われることなくキャッシュに格納されているデータブロック（以下。「Ｄｉｒｔｙブロック」という）の書き出し順序を管理するためのリスト（以下、「Ｄｉｒｔｙリンク」という）を示している。
【００２２】
同図に示すように、Ｄｉｒｔｙリンクは、各Ｄｉｒｔｙブロックに対応する管理ブロック２１〜２８をＮｅｘｔ  Ｄｉｒｔｙポインタ１とＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙポインタ２を用いて双方向に接続して構成される。そして、管理ブロック２１側の端は、ＭＲＵ（Most Recently Used）ポインタ１１と接続され、管理ブロック２８側の端は、ＬＲＵポインタ１２と接続される。
【００２３】
ＭＲＵポインタ１１は、ホストから最も近時にアクセス要求があったデータブロックに対応する管理ブロックをポイントするためのポインタであり、ＬＲＵポインタ１２は、ホストからアクセス要求があってから最も時間が経過しているデータブロックに対応する管理ブロックをポイントするためのポインタである。
【００２４】
管理ブロック２１〜２８は、対応するデータブロックの管理情報を記憶するブロックであり、対応するデータブロックに対してホストからアクセス要求があった時期が近い管理ブロックほどＭＲＵポインタ１１に近く配置された一列のリストを構成する。Ｎｅｘｔ  Ｄｉｒｔｙポインタ１は、ＬＲＵポインタ１２からＭＲＵポインタ１１の方向へ各管理ブロックを接続するためのポインタであり、Ｐｒｅｖｉｏｕｓ  Ｄｉｒｔｙポインタ２は、ＭＲＵポインタ１１からＬＲＵポインタ１２の方向へ各管理ブロックを接続するためのポインタである。
【００２５】
管理ブロック２１〜２８が記憶する管理情報には、対応するデータブロックの書き出し先の磁気ディスク装置を識別するためのディスク番号も含まれる。管理ブロック２１〜２８が記憶するディスク番号は、それぞれ、「３」、「２」、「２」、「１」、「２」、「２」、「２」、「１」となっている。なお、このディスク番号は、物理的な磁気ディスク装置を複数束ねて構成された仮想的な磁気ディスク装置を示すものであってもよい。
【００２６】
このＤｉｒｔｙリンクは、キャッシュの容量が逼迫した場合等に、磁気ディスク装置への書き出し処理を実行するデータブロックを選定するために使用される。具体的には、ＬＲＵポインタ１２に近く配置されている管理ブロックに対応するデータブロックほど高い優先順位で書き出し処理の対象として選定され、書き出し処理が実行されたデータブロックに対応する管理ブロックはＤｉｒｔｙリンクから削除される。
【００２７】
書き出し処理の対象となるデータブロックの選定においては、書き出し先の磁気ディスク装置の負荷状況が考慮される。すなわち、既に書き出し処理が集中して発生し、負荷が高まっている磁気ディスク装置が書き出し先であるデータブロックは、処理対象から除外される。
【００２８】
ここで、「２」というディスク番号に対応する磁気ディスク装置の負荷が高い状態にあるときに２つのデータブロックの書き出しを行う必要が生じたものとする。この場合、ＬＲＵポインタ１２に最も近い位置からＤｉｒｔｙリンクが走査され、まず、管理ブロック２８が選択される。管理ブロック２８が記憶するディスク番号「１」は、負荷に問題のない磁気ディスク装置のものなので、処理対象のデータブロックの１つ目は、管理ブロック２８に対応するデータブロックとなる。
【００２９】
続いて、管理ブロック２７が選択される。管理ブロック２７が記憶するディスク番号「２」は、負荷が高い状態にある磁気ディスク装置のものなので、この管理ブロックに対応するデータブロックは、処理対象とはならない。続いて選択される管理ブロック２６および２５が記憶するディスク番号も「２」であり、これらの管理ブロックに対応するデータブロックも、処理対象とはならない。
【００３０】
続いて、管理ブロック２４が選択される。管理ブロック２４が記憶するディスク番号「１」は、負荷に問題のない磁気ディスク装置のものなので、処理対象のデータブロックの２つ目は、管理ブロック２４に対応するデータブロックとなる。
【００３１】
この例では、ディスク番号「２」を有する管理ブロック２５〜２７が３個連続して存在し、これらを読み飛ばす分だけ余分な処理が必要となっているが、この程度の処理量の増加であれば、処理性能への影響はない。しかし、大容量のキャッシュをもつＲＡＩＤ装置において特定の磁気ディスク装置へのアクセスが集中して発生した場合には、同一のディスク番号を有する管理ブロックがＤｉｒｔｙリンク中に数千個連続して存在する場合があり、これらを読み飛ばす必要が生じた場合には、大きな性能低下が生じる。
【００３２】
次に、本実施例に係るＲＡＩＤ装置におけるキャッシュ管理方法の概要について説明する。図１は、本実施例に係るキャッシュ管理方法の概要について説明するための説明図である。同図に示すＤｉｒｔｙリンクにおいては、管理ブロック２１〜２８が図１７と同じ順序で配置されている。
【００３３】
同図に示すように、本実施例に係るキャッシュ管理方法では、個々の管理ブロックを双方向接続するＮｅｘｔ  Ｄｉｒｔｙポインタ１およびＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙポインタ２に加えて、同一のディスク番号を有する連続する管理ブロックの両端を双方向接続するＮｅｘｔ  Ｓｋｉｐポインタ３およびＰｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ４を用いる。
【００３４】
Ｎｅｘｔ  Ｓｋｉｐポインタ３は、同一のディスク番号を有する連続する管理ブロックの両端を、ＬＲＵポインタ１２からＭＲＵポインタ１１の方向へ接続するためのポインタであり、Ｐｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ４は、同一のディスク番号を有する連続する管理ブロックの両端を、ＭＲＵポインタ１１からＬＲＵポインタ１２の方向へ接続するためのポインタである。なお、以下の説明においては、Ｎｅｘｔ  Ｓｋｉｐポインタ３とＰｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ４による双方向接続をＳｋｉｐリンクと称する。
【００３５】
図１の例では、Ｎｅｘｔ  Ｓｋｉｐポインタ３は、管理ブロック２７と管理ブロック２５を接続し、また、管理ブロック２３と管理ブロック２２を接続している。そして、Ｐｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ４は、管理ブロック２５と管理ブロック２７を接続し、また、管理ブロック２２と管理ブロック２３を接続している。
【００３６】
ここで、図１７の場合と同様に、「２」というディスク番号に対応する磁気ディスク装置の負荷が高い状態にあるときに２つのデータブロックの書き出しを行う必要が生じたものとする。この場合、ＬＲＵポインタ１２に最も近い位置からＤｉｒｔｙリンクが走査され、まず、管理ブロック２８が選択される。管理ブロック２８が記憶するディスク番号「１」は、負荷に問題のない磁気ディスク装置のものなので、処理対象のデータブロックの１つ目は、管理ブロック２８に対応するデータブロックとなる。
【００３７】
続いて、管理ブロック２７が選択される。管理ブロック２７が記憶するディスク番号「２」は、負荷が高い状態にある磁気ディスク装置のものなので、この管理ブロックに対応するデータブロックは、処理対象とはならない。
【００３８】
本実施例に係るキャッシュ管理方法では、ある管理ブロックが記憶するディスク番号に対応する磁気ディスク装置の負荷が高い状態にあり、さらに、その管理ブロックのＮｅｘｔ  Ｓｋｉｐポインタ３が他の管理ブロックをポイントしている場合には、Ｎｅｘｔ  Ｓｋｉｐポインタ３を辿って次の管理ブロックとして選択する。
【００３９】
管理ブロック２７が記憶するディスク番号「２」に対応する磁気ディスク装置は、負荷が高い状態にあり、管理ブロック２７のＮｅｘｔ  Ｓｋｉｐポインタ３は、管理ブロック２５をポイントしているので、次に選択される管理ブロックは、管理ブロック２５のＮｅｘｔ  Ｄｉｒｔｙポインタ１がポイントしている管理ブロック、すなわち、管理ブロック２４となる。
【００４０】
こうして選択された管理ブロック２４が記憶するディスク番号「１」は、負荷に問題のない磁気ディスク装置のものなので、処理対象のデータブロックの２つ目は、管理ブロック２４に対応するデータブロックとなる。
【００４１】
このように、本実施例に係るキャッシュ管理方法では、Ｓｋｉｐリンクを利用して、同一のディスク番号を有する管理ブロックの塊をまとめて読み飛ばすことができる。このため、大容量のキャッシュをもつＲＡＩＤ装置において特定の磁気ディスク装置へのアクセスが集中し、同一のディスク番号を有する管理ブロックが連続する長大な塊が形成された場合であっても、Ｄｉｒｔｙリンクを高速に走査することができ、ＲＡＩＤ装置の性能低下を抑制することができる。
【００４２】
なお、図１では、同一のディスク番号を有する連続する管理ブロックの両端のみをＳｋｉｐリンクで接続する例を示したが、図２に示すように、前後の管理ブロックのいずれとも異なるディスク番号を有する管理ブロックに自身をポイントするＮｅｘｔ  Ｓｋｉｐポインタ５およびＰｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ６を設定することとしてもよい。
【００４３】
このように、同一のディスク番号を有する管理ブロックの塊に含まれない管理ブロックにもＮｅｘｔ  Ｓｋｉｐポインタ５およびＰｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ６を設定することにより、全ての管理ブロックがいずれかのＳｋｉｐリンクに関連することになり、Ｄｉｒｔｙリンクに新たに管理ブロックを追加する際の処理等を単純化することができる。
【００４４】
また、図３に示すように、同一のディスク番号を有する連続する管理ブロックの他方の端の次の管理ブロックをポイントするようにＮｅｘｔ  Ｓｋｉｐポインタ７およびＰｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ８を設定することとしてもよい。このように次の管理ブロックをポイントすることにより、Ｓｋｉｐリンクを辿ってＤｉｒｔｙリンクを探索する場合に、Ｎｅｘｔ  Ｄｉｒｔｙポインタ１もしくはＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙポインタ２を用いることなく、一工程省略して、塊の次の管理ブロックを選択することができる。
【００４５】
次に、図１に示したＤｉｒｔｙリンクに管理ブロックを追加する場合と削除する場合の動作の概要について説明する。図４は、Ｄｉｒｔｙリンクに管理ブロックを追加する場合の動作を示す図である。同図は、図１に示したＤｉｒｔｙリンクに、ディスク番号「３」を有する管理ブロック２９を追加する場合の動作を示している。
【００４６】
管理ブロック２９は、ＬＲＵ論理に従って、ＤｉｒｔｙリンクのＭＲＵポインタ１１に最も近い位置に追加される。この例の場合、管理ブロック２９が記憶するディスク番号「３」は、隣接する管理ブロック２１が記憶するディスク番号「３」と一致しているので、管理ブロック２９と管理ブロック２１の間にＳｋｉｐリンクが新たに設定される。
【００４７】
このように、Ｄｉｒｔｙリンクに追加される管理ブロックが記憶するディスク番号と、隣接する管理ブロックが記憶するディスク番号が一致する場合であって、隣接する管理ブロックにＳｋｉｐリンクが設定されていない場合には、Ｄｉｒｔｙリンクに追加される管理ブロックと隣接する管理ブロックの間にＳｋｉｐリンクが新たに設定される。
【００４８】
また、Ｄｉｒｔｙリンクに追加される管理ブロックが記憶するディスク番号と、隣接する管理ブロックが記憶するディスク番号が一致する場合であって、隣接する管理ブロックにＳｋｉｐリンクが設定されている場合には、そのＳｋｉｐリンクに対応する管理ブロックの塊に、追加される管理ブロックが含まれるようにＳｋｉｐリンクが再設定される。
【００４９】
例えば、図４において、管理ブロック２２が記憶するディスク番号が「３」であり、管理ブロック２１と管理ブロック２２の間にＳｋｉｐリンクが設定されていた場合、管理ブロック２９の追加後は、管理ブロック２２と管理ブロック２９の間にＳｋｉｐリンクが設定されることになる。
【００５０】
また、Ｄｉｒｔｙリンクに追加される管理ブロックが記憶するディスク番号と、隣接する管理ブロックが記憶するディスク番号が一致しない場合は、追加される管理ブロックにはＳｋｉｐリンクが設定されない。
【００５１】
ところで、本実施例に係るキャッシュ管理方法では、同じディスク番号を有する管理ブロックがＤｉｒｔｙリンク中に散在している場合よりも、連続して配置されている場合の方が、効率よくＤｉｒｔｙリンクを探索することができる。そこで、ＤｉｒｔｙリンクのＭＲＵポインタ１１に最も近い位置に新たな管理ブロックを追加する代わりに、同じディスク番号を有する管理ブロックが連続して配置されるように、新たな管理ブロックをＤｉｒｔｙリンクの途中に挿入することとしてもよい。
【００５２】
図５は、Ｄｉｒｔｙリンクに管理ブロックを挿入する場合の動作を示す図である。同図は、図１に示したＤｉｒｔｙリンクに、ディスク番号「２」を有する管理ブロック３０を挿入する場合の動作を示している。
【００５３】
Ｄｉｒｔｙリンクに管理ブロックを挿入する場合、ＤｉｒｔｙリンクをＭＲＵポインタ１１に近い側より走査し、同一のディスク番号を記憶する管理ブロックの手前が挿入位置となる。ただし、Ｄｉｒｔｙリンク全体を走査すると性能低下が生じる可能性があるため、走査は、ＭＲＵポインタ１１に近い側からＮ個目の管理ブロックまでに限定し、Ｎ個目の管理ブロックまでに同一のディスク番号を記憶する管理ブロックが発見されなかった場合は、図４の例と同様にＭＲＵポインタ１１に最も近い位置を挿入位置とする。
【００５４】
なお、上記のＮの値は、当該のＲＡＩＤ装置の負荷状況に応じて動的に変動させることとしてもよいし、当該のＲＡＩＤ装置に接続されている磁気ディスク装置の数等に応じて決定することとしてもよい。
【００５５】
図５の例では、Ｎ個の範囲内にディスク番号「２」を記憶する管理ブロック２２が存在するので、管理ブロック２２の手前が管理ブロック３０の挿入位置となり、ディスク番号「２」を記憶する管理ブロックの塊の両端となる管理ブロック２３と管理ブロック３０の間にＳｋｉｐリンクが設定されることになる。
【００５６】
図６は、Ｄｉｒｔｙリンクから管理ブロックを削除する場合の動作を示す図である。同図は、図１に示したＤｉｒｔｙリンクから、ディスク番号「２」を有する管理ブロック２６を削除する場合の動作を示している。
【００５７】
同図に示した例のように、同じディスク番号を有する管理ブロックの塊の内部に位置する管理ブロックの一つが削除された場合には、その塊の両端を接続するＳｋｉｐリンクはそのまま維持される。
【００５８】
また、同じディスク番号を有する３個以上の管理ブロックの塊の両端のいずれかの管理ブロックが削除された場合は、削除された管理ブロックを除いた塊の両端を接続するようにＳｋｉｐリンクが再設定される。また、同じディスク番号を有する２個の連続する管理ブロックのいずれが削除された場合は、それらの管理ブロック間に設定されていたＳｋｉｐリンクは削除される。
【００５９】
また、同じディスク番号を有する管理ブロックの塊に属さない管理ブロックが削除された場合は、通常は、既存のＳｋｉｐリンクはそのまま維持される。ただし、図７に示すように、削除された管理ブロックの前後の管理ブロックが記憶するディスク番号が同一の場合は、それらを含めた同じディスク番号を有する管理ブロックの塊の両端を接続するようにＳｋｉｐリンクが設定される。
【００６０】
このように、管理ブロックの削除後に、その前後の管理ブロックを連結した塊に対してＳｋｉｐリンクを設定することにより、Ｓｋｉｐリンクが断片化することを防止し、Ｄｉｒｔｙリンクを探索する場合の効率を向上させることができる。
【００６１】
次に、本実施例に係るキャッシュ管理方法を実装したＲＡＩＤ装置１００について説明する。図８は、本実施例に係るＲＡＩＤ装置１００の構成を示す機能ブロック図である。同図に示すように、ＲＡＩＤ装置１００は、ホストインターフェース部１１０1〜１１０kと、ディスクインターフェース部１２０1〜１２０mと、磁気ディスク装置１３０1〜１３０mと、制御部１４０と、記憶部１５０とを有する。
【００６２】
ホストインターフェース部１１０1〜１１０kは、ＲＡＩＤ装置に対してデータブロックの書き出しや読み込みを依頼するホストとの間で各種情報をやりとりするためのインターフェース部である。なお、ＲＡＩＤ装置とホストの接続は、ファイバーチャネル等の各種方式を用いて実現することができる。また、ホストインターフェース部１１０1〜１１０kの数は、いくつであってもよい。
【００６３】
ディスクインターフェース部１２０1〜１２０mは、磁気ディスク装置１３０1〜１３０mを接続するためのインターフェース部であり、磁気ディスク装置１３０1〜１３０mは、各種情報を記憶可能な記憶装置である。なお、ディスクインターフェース部１２０1〜１２０mおよび磁気ディスク装置１３０1〜１３０mの数は、いくつであってもよい。
【００６４】
制御部１４０は、ＲＡＩＤ装置１００を全体制御する制御部であり、ホストインターフェース部１１０1〜１１０k、ディスクインターフェース部１２０1〜１２０mおよび記憶部１５０と接続され、キャッシュ管理部１４１と、書き出し制御部１４２とを有する。
【００６５】
制御部１４０は、ＲＡＩＤ５等の各種のＲＡＩＤ方式に従って情報を読み書きするために必要な制御を実行する。また、記憶部１５０に設けられたキャッシュを有効に活用して、ホストからの要求に対する応答時間を短縮させるための制御も実行する。
【００６６】
キャッシュ管理部１４１は、記憶部１５０に設けられたキャッシュの状態を管理するための処理部であり、既に説明したＤｉｒｔｙリンクの管理も担当する。書き出し制御部１４２は、ホストから書き込み要求があったが、まだ磁気ディスク装置１３０1〜１３０mへの書き出しが行われることなくキャッシュに格納されているデータブロックの書き出し処理を実行する処理部である。
【００６７】
書き出し制御部１４２は、書き出し処理の対象となるデータブロックを選定するために、キャッシュ管理部１４１によって管理されているＤｉｒｔｙリンクの探索を行う。その際、負荷が高い状態にある磁気ディスク装置に対応する管理ブロックを読み飛ばすために、Ｓｋｉｐリンクを利用する。なお、書き出し制御部１４２による書き出し処理は、例えば、記憶部１５０に設けられたキャッシュの容量が逼迫した場合や、予めスケジュールされた時間間隔ごとに起動される。
【００６８】
記憶部１５０は、ＲＡＭ（Random Access Memory）等からなる高速な記憶装置であり、管理ブロック１５３1〜１５３n、ＭＲＵポインタ１５４およびＬＲＵポインタ１５５が格納される管理領域１５１と、データブロック１５６1〜１５６nが格納されるキャッシュ領域１５２とを有する。
【００６９】
データブロック１５６1〜１５６nは、磁気ディスク装置１３０1〜１３０mが保持すべきデータブロックの一時的な複製であり、管理ブロック１５３1〜１５３nは、データブロック１５６1〜１５６nと１対１で対応し、対応するデータブロックの管理情報を保持する。管理ブロック１５３1が保持する管理情報の一例を図９に示す。なお、管理ブロック１５３2〜１５３nも、管理ブロック１５３1と同様の情報を保持する。
【００７０】
同図に示した管理ブロック１５３1は、ディスク番号２０１と、ディスクブロック番号２０２と、Ｎｅｘｔ  Ｐｏｉｎｔｅｒ２０３と、Ｐｒｅｖｉｏｕｓ  Ｐｏｉｎｔｅｒ２０４と、Ｎｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５と、Ｐｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６と、Ｎｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７と、Ｐｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８といった項目を有する。
【００７１】
ディスク番号２０１は、当該の管理ブロックに対応するデータブロックが記憶されるべき磁気ディスク装置を識別するための番号が設定される項目である。ディスクブロック番号２０２は、ディスク番号２０１によって識別される磁気ディスク装置において、当該の管理ブロックに対応するデータブロックが記憶されるべき位置を識別するための番号が設定される項目である。
【００７２】
Ｎｅｘｔ  Ｐｏｉｎｔｅｒ２０３およびＰｒｅｖｉｏｕｓ  Ｐｏｉｎｔｅｒ２０４は、書き出し要求であるか読み込み要求であるかを問わず、ホストから最近アクセス要求があったデータブロック順に管理ブロック１５３1〜１５３nを配置するリストを構成するための項目であり、このリストにおいて前後に配置される管理ブロックを識別するための番号が設定される。Ｎｅｘｔ  Ｐｏｉｎｔｅｒ２０３およびＰｒｅｖｉｏｕｓ  Ｐｏｉｎｔｅｒ２０４によるリンクについては、周知技術であるので本明細書においては詳細な説明を省略する。
【００７３】
Ｎｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５およびＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６は、Ｄｉｒｔｙリンクを構成するための項目であり、Ｄｉｒｔｙリンクにおいて前後に配置される管理ブロックを識別するための番号が設定される。Ｄｉｒｔｙリンクにおける管理ブロックの配置の変更は、これらの項目の値を変更することにより実現される。
【００７４】
Ｎｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７およびＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８は、Ｄｉｒｔｙリンクにおいてディスク番号２０１に同一の値を保持する管理ブロックの塊の両端を接続するＳｋｉｐリンクを構成するための項目であり、Ｓｋｉｐリンクにおいて他方の端に位置する管理ブロックを識別するための番号が設定される。
【００７５】
次に、図８に示したＲＡＩＤ装置１００の動作について説明する。なお、以下の処理手順の説明においては、説明を簡単にするために、図２に示すように、同じディスク番号を有する他の管理ブロックと連続していない管理ブロックは、自身をポイントするＳｋｉｐリンクを有していることを前提とする。
【００７６】
図１０は、Ｄｉｒｔｙリンクに管理ブロックを追加する場合の処理手順を示すフローチャートである。同図に示すように、Ｄｉｒｔｙリンクに管理ブロックを追加することが必要になった場合、キャッシュ管理部１４１は、まず、ＭＲＵポインタ１５４が示す管理ブロック、すなわち、最も最近書き込み要求があったデータブロックに対応する管理ブロックを選択する（ステップＳ１０１）。
【００７７】
そして、選択した管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５に追加対象の管理ブロックの番号を設定し（ステップＳ１０２）、追加対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６に選択した管理ブロックの番号を設定する（ステップＳ１０３）。
【００７８】
こうして追加対象の管理ブロックをＤｉｒｔｙリンクに接続した後、追加対象の管理ブロックのディスク番号２０１の値が、選択した管理ブロックのディスク番号２０１の値と同一であれば（ステップＳ１０４肯定）、選択した管理ブロックに設定されているＳｋｉｐリンクを追加対象の管理ブロックに設定し直すための処理を行う。
【００７９】
すなわち、選択した管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８が示す管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７に追加対象の管理ブロックの番号を設定し（ステップＳ１０５）、追加対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８に選択した管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８の値を設定し（ステップＳ１０６）、選択した管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８の値をクリアする（ステップＳ１０７）。
【００８０】
一方、追加対象の管理ブロックのディスク番号２０１の値が、選択した管理ブロックのディスク番号２０１の値と同一でなければ（ステップＳ１０４否定）、追加対象の管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７に追加対象の管理ブロックの番号を設定し（ステップＳ１０８）、追加対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８に追加対象の管理ブロックの番号を設定する（ステップＳ１０９）。
【００８１】
なお、上記の処理手順は、ＭＲＵポインタ１５４が示す位置を追加対象の管理ブロックの追加位置とするものであるが、図５に示すように、Ｓｋｉｐリンクが設定される機会を増やすことを目的として、Ｄｉｒｔｙリンクの途中に管理ブロックを挿入する場合の処理手順は、図１０に示したステップＳ１０１を図１１に示す処理に置き換えることで実現することができる。
【００８２】
この場合、キャッシュ管理部１４１は、まず、カウンタｎの値を、同一のディスク番号をもつ管理ブロックを探索する最大の論理ブロック数であるＮに設定し（ステップＳ２０１）、ＭＲＵポインタ１５４が示す管理ブロック、すなわち、最も最近書き込み要求がったデータブロックに対応する管理ブロックを選択する（ステップＳ２０２）。
【００８３】
そして、カウンタｎの値が０よりも大きい場合は（ステップＳ２０３肯定）、選択した管理ブロックの位置が、追加対象の管理ブロックの挿入位置であるか否かを確認するため、追加対象の管理ブロックのディスク番号２０１の値と、選択した管理ブロックのディスク番号２０１の値とを比較する。
【００８４】
そして、２つの値が同一でない場合、すなわち、選択した管理ブロックの位置が、追加対象の管理ブロックの挿入位置でない場合は（ステップＳ２０４否定）、選択した管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６が示す管理ブロックを選択し（ステップＳ２０５）、カウンタｎの値を１だけ減算して（ステップＳ２０６）、ステップＳ２０３から処理を再開する。
【００８５】
一方、２つの値が同一である場合、すなわち、選択した管理ブロックの位置が、追加対象の管理ブロックの挿入位置である場合は（ステップＳ２０４肯定）、カウンタｎの値を確認する。ここで、カウンタｎの値が、初期値のＮのままである場合、すなわち、挿入位置がＭＲＵポインタ１５４側のＤｉｒｔｙリストの末端である場合は（ステップＳ２０７肯定）、特に処理をすることなく、ステップＳ１０２へ遷移する。
【００８６】
カウンタｎの値が、Ｎと異なる場合、すなわち、挿入位置がＤｉｒｔｙリストのＭＲＵポインタ１５４側の末端でない場合は（ステップＳ２０７否定）、選択した管理ブロックのＭＲＵポインタ側の管理ブロックと追加対象の管理ブロックを接続するために、選択した管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５が示す管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６に追加対象の管理ブロックの番号を設定し（ステップＳ２０８）、追加対象の管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５に選択した管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５の値を設定し（ステップＳ２０９）、その後、ステップＳ１０２へ遷移する。
【００８７】
また、ステップＳ２０３においてカウンタｎの値が０以下となった場合、すなわち、同一のディスク番号をもつ管理ブロックを発見できなかった場合は（ステップＳ２０３否定）、ＭＲＵポインタ１５４が示す管理ブロックを選択し（ステップＳ２１０）、その後、ステップＳ１０２へ遷移する。
【００８８】
図１２は、Ｄｉｒｔｙリンクから管理ブロックを削除する場合の処理手順を示すフローチャートである。同図に示すように、Ｄｉｒｔｙリンクから管理ブロックを削除することが必要になった場合、キャッシュ管理部１４１は、まず、削除対象の管理ブロックの前後の管理ブロックのディスク番号２０１の値を取得する（ステップＳ３０１）。
【００８９】
ここで、前後の管理ブロックのディスク番号２０１の値が同一であり（ステップＳ３０２肯定）、かつ、削除対象の管理ブロックのディスク番号２０１の値が前後の管理ブロックのディスク番号２０１の値と異なる場合は（ステップＳ３０３否定）、前後の管理ブロックを含むＳｋｉｐリンクを結合するために、後述するＳｋｉｐリンク結合処理を実行する（ステップＳ３０４）。一方、前後の管理ブロックのディスク番号２０１の値が異なる場合（ステップＳ３０２否定）、もしくは、削除対象の管理ブロックのディスク番号２０１の値が前後の管理ブロックのディスク番号２０１の値と同一の場合は（ステップＳ３０３肯定）、後述するＳｋｉｐリンク付替処理を実行する（ステップＳ３０５）。
【００９０】
その後、削除対象の管理ブロックをＤｉｒｔｙリンクから外すために、削除対象の管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５が示す管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６に削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６の値を設定し（ステップＳ３０６）、削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６が示す管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５に削除対象の管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５の値を設定する（ステップＳ３０７）。
【００９１】
図１３は、Ｓｋｉｐリンク結合処理の処理手順を示すフローチャートである。同図に示すように、キャッシュ管理部１４１は、削除対象の管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５が示す管理ブロックを選択し（ステップＳ４０１）、選択した管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７が示す管理ブロックをＭＲＵ側の末端の管理ブロックとして記憶した後（ステップＳ４０２）、選択した管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７の値をクリアする（ステップＳ４０３）。
【００９２】
そして、削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６が示す管理ブロックを選択し（ステップＳ４０４）、選択した管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８が示す管理ブロックをＬＲＵ側の末端の管理ブロックとして記憶した後（ステップＳ４０５）、選択した管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８の値をクリアする（ステップＳ４０６）。
【００９３】
そして、ＬＲＵ側の末端として記憶した管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７にＭＲＵ側の末端として記憶した管理ブロックの番号を設定し（ステップＳ４０７）、ＭＲＵ側の末端として記憶した管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８にＬＲＵ側の末端として記憶した管理ブロックの番号を設定する（ステップＳ４０８）。
【００９４】
図１４は、Ｓｋｉｐリンク付替処理の処理手順を示すフローチャートである。同図に示すように、キャッシュ管理部１４１は、削除対象の管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７に値が設定されており（ステップＳ５０１肯定）、かつ、そのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７が削除対象の管理ブロック以外の管理ブロックを示している場合は（ステップＳ５０２肯定）、削除対象の管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５が示す管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７に削除対象の管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７の値を設定し（ステップＳ５０３）、さらに、削除対象の管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７が示す管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８に削除対象の管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５の値を設定する（ステップＳ５０４）。
【００９５】
また、削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８に値が設定されており（ステップＳ５０５肯定）、かつ、そのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８が削除対象の管理ブロック以外の管理ブロックを示している場合は（ステップＳ５０６肯定）、削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６が示す管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８に削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８の値を設定し（ステップＳ５０７）、さらに、削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０８が示す管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７に削除対象の管理ブロックのＰｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０６の値を設定する（ステップＳ５０８）。
【００９６】
図１５は、書き出し処理の対象となるデータブロックを選定する場合の処理手順を示すフローチャートである。なお、同図は、書き出し処理の対象となるデータブロックを一つだけ選定する場合の処理手順を示している。
【００９７】
同図に示すように、書き出し処理の対象となるデータブロックを選定することが必要になった場合、書き出し制御部１４２は、まず、ＬＲＵポインタ１５５が示す管理ブロックを選択する（ステップＳ６０１）。
【００９８】
そして、選択した管理ブロックのディスク番号２０１の値を取得する（ステップＳ６０２）ここで、その番号に対応する磁気ディスク装置が、書き込み可能な状態にあるときは（ステップＳ６０３肯定）、選択した管理ブロックに対応するデータブロックを書き出し処理の対象として選定する（ステップＳ６０８）。
【００９９】
取得した番号に対応する磁気ディスク装置が、負荷の高さ等の理由で書き込み不可能な状態にあるときは（ステップＳ６０３否定）、選択した管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７が、選択した管理ブロック以外の管理ブロックを示していれば（ステップＳ６０４肯定）、選択した管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７が示す管理ブロックを選択し（ステップＳ６０５）、さらに、選択した管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５が示す管理ブロックを選択した後（ステップＳ６０６）、ステップＳ６０２から処理を再開する。
【０１００】
また、磁気ディスク装置が、負荷の高さ等の理由で書き込み不可能な状態にあるときであって（ステップＳ６０３否定）、選択した管理ブロックのＮｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ２０７が、選択した管理ブロック自身を示しているときは（ステップＳ６０４否定）、選択した管理ブロックのＮｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ２０５が示す管理ブロックを選択した後（ステップＳ６０７）、ステップＳ６０２から処理を再開する。
【０１０１】
なお、図８に示した本実施例に係るＲＡＩＤ装置１００の構成は、本発明の要旨を逸脱しない範囲で種々に変更することができる。例えば、図８に示したＲＡＩＤ装置１００の構成からホストインターフェース部１１０1〜１１０kおよび磁気ディスク装置１３０1〜１３０mを除外した構成を一枚の基板上に実装し、サーバ装置等に内臓可能なＲＡＩＤ制御装置として構成することができる。
【０１０２】
また、ＲＡＩＤ装置１００の制御部１４０の機能をソフトウェアとして実装し、いわゆる、ソフトウェアＲＡＩＤを実現することもできる。以下に、制御部１４０の機能をソフトウェアとして実装したＲＡＩＤ制御プログラム１０７２を実行するコンピュータの一例を示す。
【０１０３】
図１６は、ＲＡＩＤ制御プログラム１０７２を実行するコンピュータ１０００を示す機能ブロック図である。このコンピュータ１０００は、各種演算処理を実行するＣＰＵ１０１０と、ユーザからのデータの入力を受け付ける入力装置１０２０と、各種情報を表示するモニタ１０３０と、各種プログラム等を記録した記録媒体からプログラム等を読み取る媒体読取り装置１０４０と、ネットワークを介して他のコンピュータとの間でデータの授受を行うネットワークインターフェース装置１０５０と、各種情報を一時記憶するＲＡＭ１０６０と、磁気ディスク装置１０７０とをバス１０８０で接続して構成される。
【０１０４】
そして、磁気ディスク装置１０７０には、コンピュータ１０００の基本的な制御を行うオペレーティングシステム１０６１の実体であるカーネルプログラム１０７１と、図８に示した制御部１４０と同様の機能を有するＲＡＩＤ制御プログラム１０７２とが記憶される。なお、ＲＡＩＤ構成を実現するため、コンピュータ１０００は、図示した磁気ディスク装置１０７０以外にも複数の磁気ディスク装置を備える。
【０１０５】
そして、ＣＰＵ１０１０がカーネルプログラム１０７１を磁気ディスク装置１０７０から読み出してＲＡＭ１０６０に展開することにより、カーネルプログラム１０７１は、オペレーティングシステム１０６１として機能するようになる。そして、オペレーティングシステム１０６１は、ＲＡＩＤ機能を実現するため、磁気ディスク装置１０７０からＲＡＩＤ制御プログラム１０７２を読み出してＲＡＭ１０６０に展開し、自身の一部として機能させる。
【０１０６】
こうして、ＲＡＩＤ制御プログラム１０７２を自身に組み込んだオペレーティングシステム１０６１は、ＲＡＭ１０６０上に、図８に示した管理領域１５１に相当する管理領域１０６２と、キャッシュ領域１５２に相当するキャッシュ領域１０６３を設け、これらの領域を使用してＲＡＩＤ機能に係る各種データ処理を実行する。
【０１０７】
なお、上記のＲＡＩＤ制御プログラム１０７２は、必ずしも磁気ディスク装置１０７０に格納されている必要はなく、ＣＤ−ＲＯＭ等の記憶媒体に記憶されたこのプログラムを、コンピュータ１０００が読み出して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等を介してコンピュータ１０００に接続される他のコンピュータ（またはサーバ）等にこのプログラムを記憶させておき、コンピュータ１０００がこれらからプログラムを読み出して実行するようにしてもよい。
【０１０８】
上述してきたように、本実施例では、磁気ディスクへの書き出しが必要なディスクブロックに対応する管理ブロックを優先順位順に配列したＤｉｒｔｙリンクを探索して書き出し対象のデータブロックを選定する場合に、書き出し不能な磁気ディスクが書き出し先であるデータブロックに対応する管理ブロックにＳｋｉｐリンクがあれば、そのＳｋｉｐリンクを辿って、書き出し不能な磁気ディスクが書き出し先であるデータブロックに対応する管理ブロックを一気に読み飛ばすことができるように構成したので、キャッシュの大容量化により、多数のデータブロックの管理が必要になった場合であっても、効率よくキャッシュを管理し、キャッシュの管理に係る処理時間の増大を抑制することができる。
【０１０９】
なお、上記の実施例では、本発明に係るキャッシュ管理方法をＲＡＩＤ装置におけるキャッシュ管理に適用した例について説明したが、本発明に係るキャッシュ管理方法は、キャッシュを利用する各種の装置および方法に適用することが可能である。
【０１１０】
（付記１）磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ装置であって、
前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるキャッシュ管理手段と、
前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御手段と
を備えたことを特徴とするＲＡＩＤ装置。
【０１１１】
（付記２）前記キャッシュ管理手段は、前記リストから要素を削除する場合に、該要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、該要素の前後の要素を含む要素の一群であって、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群の、両端の要素を接続するリンクを設けることを特徴とする付記１に記載のＲＡＩＤ装置。
【０１１２】
（付記３）前記キャッシュ管理手段は、前記リストへ要素を挿入する場合に、前記リストに属する要素を優先順位が低い順に探索し、挿入する要素に対応するデータブロックが書き出される磁気ディスク装置と同一の磁気ディスク装置へ書き出されるデータブロックに対応する要素の手前を挿入位置とすることを特徴とする付記１または２に記載のＲＡＩＤ装置。
【０１１３】
（付記４）磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶するＲＡＩＤ制御プログラムであって、
前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるキャッシュ管理手順と、
前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御手順と
をコンピュータに実行させることを特徴とするＲＡＩＤ制御プログラム。
【０１１４】
（付記５）前記キャッシュ管理手順は、前記リストから要素を削除する場合に、該要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、該要素の前後の要素を含む要素の一群であって、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群の、両端の要素を接続するリンクを設けることを特徴とする付記４に記載のＲＡＩＤ制御プログラム。
【０１１５】
（付記６）前記キャッシュ管理手順は、前記リストへ要素を挿入する場合に、前記リストに属する要素を優先順位が低い順に探索し、挿入する要素に対応するデータブロックが書き出される磁気ディスク装置と同一の磁気ディスク装置へ書き出されるデータブロックに対応する要素の手前を挿入位置とすることを特徴とする付記４または５に記載のＲＡＩＤ制御プログラム。
【０１１６】
（付記７）磁気ディスクへ書き出すべきデータブロックを一時記憶するキャッシュを管理するキャッシュ管理方法であって、
前記キャッシュに一時記憶したデータブロックを前記磁気ディスク装置へ書き出す優先順位に従って、各データブロックに対応する要素を配列したリストを形成させ、該リストにおいて、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群が存在する場合に、その一群の両端の要素を接続するリンクを設けるリスト編成工程と、
前記磁気ディスクへの書き出しを実行する対象のデータブロックを選定する場合に、前記リストに属する要素を優先順位が高い順に探索し、書き込みを行うことができない磁気ディスクが書き込み先であるデータブロックに対応する要素に前記リンクが設定されていれば、該リンクを辿って次の要素の探索を行う書き出し制御工程と
を含んだことを特徴とするキャッシュ管理方法。
【０１１７】
（付記８）前記リスト編成工程は、前記リストから要素を削除する場合に、該要素の前後の要素に対応するデータブロックの書き出し先が同一の磁気ディスク装置であれば、該要素の前後の要素を含む要素の一群であって、同一の磁気ディスク装置へ書き出すべきデータブロックに対応する要素の一群の、両端の要素を接続するリンクを設けることを特徴とする付記７に記載のキャッシュ管理方法。
【０１１８】
（付記９）前記リスト編成工程は、前記リストへ要素を挿入する場合に、前記リストに属する要素を優先順位が低い順に探索し、挿入する要素に対応するデータブロックが書き出される磁気ディスク装置と同一の磁気ディスク装置へ書き出されるデータブロックに対応する要素の手前を挿入位置とすることを特徴とする付記７または８に記載のキャッシュ管理方法。
【産業上の利用可能性】
【０１１９】
以上のように、本発明に係るＲＡＩＤ装置、ＲＡＩＤ制御プログラムおよびキャッシュ管理方法は、磁気ディスクへ書き出すべきデータブロックをキャッシュに一時記憶する場合に有用であり、特に、大容量のキャッシュを備えた場合においても、キャッシュの管理に係る処理時間の増大を抑制することが必要な場合に適している。
【図面の簡単な説明】
【０１２０】
【図１】本実施例に係るキャッシュ管理方法の概要について説明するための説明図である。
【図２】本実施例に係るキャッシュ管理方法の変形例を示す図である。
【図３】本実施例に係るキャッシュ管理方法の変形例を示す図である。
【図４】Ｄｉｒｔｙリンクに管理ブロックを追加する場合の動作を示す図である。
【図５】Ｄｉｒｔｙリンクに管理ブロックを挿入する場合の動作を示す図である。
【図６】Ｄｉｒｔｙリンクから管理ブロックを削除する場合の動作を示す図である。
【図７】管理ブロックの削除にともなってＳｋｉｐリンクの結合を行う場合の動作を示す図である。
【図８】本実施例に係るＲＡＩＤ装置の構成を示す機能ブロック図である。
【図９】管理ブロックの構成の一例を示す図である。
【図１０】Ｄｉｒｔｙリンクに管理ブロックを追加する場合の処理手順を示すフローチャートである。
【図１１】Ｄｉｒｔｙリンクに管理ブロックを挿入する場合の処理手順を示すフローチャートである。
【図１２】Ｄｉｒｔｙリンクから管理ブロックを削除する場合の処理手順を示すフローチャートである。
【図１３】Ｓｋｉｐリンク結合処理の処理手順を示すフローチャートである。
【図１４】Ｓｋｉｐリンク付替処理の処理手順を示すフローチャートである。
【図１５】書き出し処理の対象となるデータブロックを選定する場合の処理手順を示すフローチャートである。
【図１６】ＲＡＩＤ制御プログラムを実行するコンピュータを示す機能ブロック図である。
【図１７】従来のキャッシュ管理方法の概要について説明するための説明図である。
【符号の説明】
【０１２１】
１  Ｎｅｘｔ  Ｄｉｒｔｙポインタ
２  Ｐｒｅｖｉｏｕｓ  Ｄｉｒｔｙポインタ
３、５、７  Ｎｅｘｔ  Ｓｋｉｐポインタ
４、６、８  Ｐｒｅｖｉｏｕｓ  Ｓｋｉｐポインタ
１１  ＭＲＵポインタ
１２  ＬＲＵポインタ
２１〜３０  管理ブロック
１００  ＲＡＩＤ装置
１１０１〜１１０ｋ  ホストインターフェース部
１２０１〜１２０ｍ  ディスクインターフェース部
１３０１〜１３０ｍ  磁気ディスク装置
１４０  制御部
１４１  キャッシュ管理部
１４２  書き出し制御部
１５０  記憶部
１５１  管理領域
１５２  キャッシュ領域
１５３１〜１５３ｎ  管理ブロック
１５４  ＭＲＵポインタ
１５５  ＬＲＵポインタ
１５６１〜１５６ｎ  データブロック
２０１  ディスク番号
２０２  ディスクブロック番号
２０３  Ｎｅｘｔ  Ｐｏｉｎｔｅｒ
２０４  Ｐｒｅｖｉｏｕｓ  Ｐｏｉｎｔｅｒ
２０５  Ｎｅｘｔ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ
２０６  Ｐｒｅｖｉｏｕｓ  Ｄｉｒｔｙ  Ｐｏｉｎｔｅｒ
２０７  Ｎｅｘｔ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ
２０８  Ｐｒｅｖｉｏｕｓ  Ｓｋｉｐ  Ｐｏｉｎｔｅｒ
１０００  コンピュータ
１０１０  ＣＰＵ
１０２０  入力装置
１０３０  モニタ
１０４０  媒体読取り装置
１０５０  ネットワークインターフェース装置
１０６０  ＲＡＭ
１０６１  オペレーティングシステム
１０６２  管理領域
１０６３  キャッシュ領域
１０７０  磁気ディスク装置
１０７１  カーネルプログラム
１０７２  ＲＡＩＤ制御プログラム
１０８０  バス
【図１】
0004792335.tif 000002
【図２】
0004792335.tif 000003
【図３】
0004792335.tif 000004
【図４】
0004792335.tif 000005
【図５】
0004792335.tif 000006
【図６】
0004792335.tif 000007
【図７】
0004792335.tif 000008
【図８】
0004792335.tif 000009
【図９】
0004792335.tif 000010
【図１０】
0004792335.tif 000011
【図１１】
0004792335.tif 000012
【図１２】
0004792335.tif 000013
【図１３】
0004792335.tif 000014
【図１４】
0004792335.tif 000015
【図１５】
0004792335.tif 000016
【図１６】
0004792335.tif 000017
【図１７】
0004792335.tif 000018