(57)【要約】【課題】  本発明はキャッシュ制御装置のヒット／ミス判定方法及び装置に関し、キャッシュ管理テーブルを基本とし、テーブルを分割・動的に管理することで、テーブルサイズを小さくすることができるキャッシュ制御装置のヒット／ミス判定方法及び装置を提供することを目的としている。【解決手段】  論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブル３’と、該第１のテーブル３’からアクセスされる、キャッシュメモリ２のキャッシュページへのポインタ使用中エントリ数のカウンタを示す第２のテーブル４と、前記第１のテーブル３’には第２のテーブル４へのポインタを格納し、前記第２のテーブル４に対してミス領域にはテーブルを割り当てない制御手段と、を設けて構成する。【選択図】    図２
2005182185.tif 000002
【特許請求の範囲】
【請求項１】
論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルと、該第１のテーブルからアクセスされる、キャッシュメモリのキャッシュページへのポインタ使用中エントリ数のカウンタを示す第２のテーブルとを設け（ステップ１）、
前記第１のテーブルには第２のテーブルへのポインタを格納し、前記第２のテーブルに対してミス領域にはテーブルを割り当てない（ステップ２）、
ようにしたことを特徴とするキャッシュ制御装置のヒット／ミス判定方法。
【請求項２】
論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルと、
該第１のテーブルからアクセスされる、キャッシュメモリのキャッシュページへのポインタ使用中エントリ数のカウンタを示す第２のテーブルと、
前記第１のテーブルには第２のテーブルへのポインタを格納し、前記第２のテーブルに対してミス領域にはテーブルを割り当てない制御手段と、
を設けたことを特徴とするキャッシュ制御装置のヒット／ミス判定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はキャッシュ制御装置のヒット／ミス判定方法及び装置に関する。
【背景技術】
【０００２】
ＣＰＵのアクセスするデータを記憶しておくメモリをキャッシュメモリといい、ディスク装置からＣＰＵのキャッシュメモリに、よく使用されるデータを予め記憶しておくことが行なわれる。この時、所望のデータがキャッシュメモリ内に存在することをヒット、存在しないことをミスと呼ぶ。そして、キャッシュメモリのヒット率が高くなるような制御が行なわれる。
【０００３】
図７はＲＡＩＤ（レイド）装置の構成例を示すブロック図である。図において、１は複数の磁気ディスク、１０はこれら磁気ディスク１と接続されるコントローラ、２０は該コントローラ１０と接続される計算機である。図では、磁気ディスクは＃１〜＃４までの４台の場合を示すが、４台に限るものではなく任意の数の磁気ディスク１と接続することができる。
【０００４】
コントローラ１０において、１１は計算機２０と接続されるホストアダプタ、１２は磁気ディスク１と接続されるディスクアダプタ、１３は演算制御を行なうＣＰＵ、１４はその内部をキャッシュメモリとして使用するコントローラメモリである。ホストアダプタ１１はコントローラメモリ１４及びＣＰＵ１３と接続され、ディスクアダプタ１２はＣＰＵ１３及びコントローラメモリ１４と接続されている。また、ＣＰＵ１３はコントローラメモリ１４とも接続されている。
【０００５】
このように構成されたシステムにおいて、計算機２０は所定の処理を行なう場合に、磁気ディスク１からデータを読み出す。このようにして読み出したデータは、コントローラメモリ１４内のキャッシュメモリに格納される。このような一連の処理において、キャッシュメモリには、磁気ディスク１から読み出されたデータが格納されていく。このように、使用されたデータをキャッシュメモリに格納しておくことにより、計算機２０はキャッシュメモリに記憶されているデータについては、磁気ディスク１まで読み出しに行く必要はないので、処理速度を向上させることができる。ここで、キャッシュメモリに目的のデータが格納されいる場合をヒット、格納されていない場合をミスと呼ぶ。格納されていない場合には、磁気ディスク１を読みにいく必要がある。コントローラメモリ１４内のキャッシュメモリ１４ａに格納されているデータのヒット率が高い場合には、計算機２０の処理速度を向上させることができる。このような一連の処理において、ＣＰＵ１３は、コントローラメモリ１４の書き込み／読み出しを制御する。
【０００６】
図８はコントローラメモリの構成例を示すブロック図である。コントローラ１４は、キャッシュメモリ１４ａと、キャッシュ管理テーブル１４ｂと、コントローラ制御領域１４ｃから構成されている。
【０００７】
従来のこの種の装置としては、ハッシュ法を利用してキャッシュメモリの割り当てを高速にする技術が知られている（例えば特許文献１参照）。また、ジョブのタイプに応じて外部記憶制御装置のキャッシュメモリにアクセスするレコードを置く期間を変え、一定期間毎に繰り返すようなジョブがアクセスするレコードをキャッシュメモリに置き、アクセスが無くても、キャッシュメモリにレコードを置き、キャッシュヒットさせる技術が知られている（例えば特許文献２参照）。また、実行するプログラムの性質に応じて最も効率的にキャッシュメモリを利用することができる技術が知られている（例えば特許文献３参照）。
【０００８】
キャッシュメモリのヒット／ミス判定をシンプル且つ高速に実現するためには、以下に示すようにディスクの全アドレスに対応するキャッシュ管理テーブルを用意してやればよい。
【０００９】
図９は従来のキャッシュ管理方法の説明図である。図において、１はディスク、２はキャッシュメモリ、３はディスク１の全アドレスに対応するキャッシュ管理テーブルである。キャッシュ管理テーブル３はディスク１の全アドレスに対応するキャッシュ管理テーブルである。２はキャッシュメモリであり、キャッシュページＣに分割されている。ここで、キャッシュページとは、キャッシュメモリを管理する単位である。
【００１０】
キャッシュ管理テーブル３の各エントリにはキャッシュメモリ２内の各キャッシュページへのポインタを記憶し、ポインタが存在する場合はキャッシュヒットであり、存在しない場合はキャッシュミスである。図のキャッシュ管理テーブル３からキャッシュメモリ２への矢印は、エントリに対応するディスクアドレスのデータがキャッシュメモリ２内に存在することを示している。そして、キャッシュ管理テーブル３でアクセスされるキャッシュメモリはアドレスがキャッシュ管理テーブル３のエントリと１：１に対応している。
【特許文献１】特開平５−２２５０５９号公報（第２頁、第３頁、図１）
【特許文献２】特開平１１−２５９３６５号公報（第２頁、第３頁、図１）
【特許文献３】特開平８−２６３３７７号公報（第３頁、第４頁、図１）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
前述したように、キャッシュメモリのヒット／ミス判定をシンプル且つ高速に実現するには、ディスクの全アドレスに対応するキャッシュ管理テーブルを用意してやればよい。しかしながら、近年の爆発的なディスク容量の増加に伴い、ディスクサイズに対応するだけの巨大なテーブルを用意することは困難な状況となっている。例えば、キャッシュページサイズを５０ＫＢとし、キャッシュページへのポインタサイズを４Ｂとすると、１００ＴＢの論理ディスクに対応するキャッシュ管理テーブルのサイズは、
（１００ＴＢ／５０ＫＢ）×４Ｂ＝８０００ＭＢ
となり、８ＧＢを超える巨大なサイズとなってしまう。そのため、従来からハッシュを使用する方法がとられている。ハッシュとはハッシュ関数を用いてアドレスを圧縮して決定する方法であって、例えば３２ビットのアドレスを８ビットのアドレスに抑えるものである。ハッシュ関数はアドレスを圧縮する方法であるため、アドレスによっては同じ出力値が発生することがある（シノニムの発生）。このため、どちらのアドレスを用いるか判断に迷ってしまい、性能低下となる。このように、キャッシュ管理テーブルの容量とシノニムの発生はトレードオフの関係にある。
【００１２】
本発明はこのような課題に鑑みてなされものであって、図９に示すキャッシュ管理テーブルを基本とし、テーブルを分割・動的に管理することで、テーブルサイズを小さくすることができるキャッシュ制御装置のヒット／ミス判定方法及び装置を提供することを目的としている。
【課題を解決するための手段】
【００１３】
（１）請求項１記載の発明は、以下の通りである。図１は本発明方法の原理を示すフローチャートである。本発明は、論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルと、該第１のテーブルからアクセスされる、キャッシュメモリのキャッシュページへのポインタ使用中エントリ数のカウンタを示す第２のテーブルとを設け（ステップ１）、前記第１のテーブルには第２のテーブルへのポインタを格納し、前記第２のテーブルに対してミス領域にはテーブルを割り当てない（ステップ２）、ようにしたことを特徴とする。
（２）請求項２記載の発明は、論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルと、該第１のテーブルからアクセスされる、キャッシュメモリのキャッシュページへのポインタ使用中エントリ数のカウンタを示す第２のテーブルと、前記第１のテーブルには第２のテーブルへのポインタを格納し、前記第２のテーブルに対してミス領域にはテーブルを割り当てない制御手段と、を設けたことを特徴とする。
【発明の効果】
【００１４】
（１）請求項１記載の発明によれば、論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルでアクセスするキャッシュページへのポインタを示す第２のテーブルを設け、これら第１及び第２のテーブルを動的に変化させることにより、テーブルを分割・動的に管理することで、テーブルサイズを小さくすることができる。
（２）請求項２記載の発明によれば、論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルでアクセスするキャッシュページへのポインタを示す第２のテーブルを設け、これら第１及び第２のテーブルを動的に変化させる制御手段を設けることにより、テーブルを分割・動的に管理することで、テーブルサイズを小さくすることができる。
【発明を実施するための最良の形態】
【００１５】
以下、図面を参照して本発明の実施の形態例を詳細に説明する。
【００１６】
図２は本発明の動作の一例を示す図である。図９と同一のものは、同一の符号を付して示す。図において、１はデータが記憶されているディスク、３’はディスク１に記憶されている論理ディスクサイズのデータに対応する粒度の粗いアドレスからなる第１のテーブル（テーブルＡ）である。即ち、テーブルＡは論理ディスクサイズのアドレスが適宜間引かれたものが記憶されている。該テーブルＡの各エントリには、第２のテーブル４へのポインタが記憶されている。
【００１７】
４はテーブルＡからアクセスされる、キャッシュページへのポインタ使用中エントリ数のカウンタを示す第２のテーブル（テーブルＢ）である。テーブルＢには、キャッシュページへのポインタ使用中エントリ数のカウンタが記憶されている。テーブルＢには、未割り当てのテーブル４’も存在する。２はテーブルＢからアクセスされるキャッシュメモリである。該キャッシュメモリ２は、キャッシュページＣに分割されている。
【００１８】
テーブルの割り当てタイミングは、テーブルＡがディスク登録時であり、テーブルＢがキャッシュデータ操作時である。何れも、動的に割り当てられる。総テーブルサイズは、テーブルＡがディスクサイズに比例（図９の方式と同様にディスクサイズに比例するが、粒度が粗いためにディスクが巨大になっても図９に比べてはるかに小さいサイズですむ）するのに対し、テーブルＢはキャッシュサイズに比例する。なお、図示されていないが、全体の動作制御は制御手段が行なう。該制御手段としては、例えばマイクロコンピュータが用いられる。このように構成された装置の動作を説明すれば、以下の通りである。
【００１９】
図９に示したように、キャッシュ管理テーブルの中身はキャッシュページへのポインタである。そのため、ディスク（テーブル）が巨大であっても、テーブル内で有効なエントリ（キャッシュページへのポインタを持つエントリ）は最大でもキャッシュページ数分に限られる。それ以外の部分は、キャッシュミスを示すＮｕｌｌ（ゼロ）ポインタが入っているだけである。
【００２０】
そこで、本発明では、テーブルを分割し、階層的（テーブルＡとテーブルＢの２層構造）に管理することによって、これらのミス領域に対してテーブルを割り当てないことで、全体のテーブルサイズを削減している。テーブルＡのうち、広範囲キャッシュミスの領域は、テーブルＢが割り当てられない。一方、キャッシュヒット領域には、テーブルＢが割り当てられ、接続される。未割り当てのテーブルＢについては、キャッシュデータのステージング（キャッシュメモリにディスク１からデータをもってくること）に応じて、テーブルＢが割り当てられる。
【００２１】
テーブルＡは、装置へのディスク登録時にディスクサイズに対応した大きさのテーブルを用意する。この時点では、キャッシュメモリ上にディスクデータがないため、テーブルＡの全てのエントリはＮｕｌｌポインタである。各エントリは、ディスクデータのキャッシュメモリへのステージング処理時にテーブルＢへのポインタが登録される。また、テーブルＢ中のカウンタは、そのテーブル内での有効な（キャッシュページへのポインタが入っている）エントリ数を示し、テーブルの解放のための条件判断に利用される。
【００２２】
図３はテーブルＡとテーブルＢの構成例を示す図である。テーブルＡには、テーブルＢのポインタが記憶されている。テーブルＡのエントリ数であるｎはディスクサイズに対応した数値（ディスクサイズとテーブルＢのエントリ数であるｍにより決定される数値）となり、各エントリはディスクの比較的広い領域（図２中の粗い粒度に対応）に対して１：１に対応する。テーブルＢには、キャッシュメモリのキャッシュポインタが記憶されている。テーブルＢのエントリ数ｍは設定値であり、この値とディスクサイズ及びキャッシュメモリサイズにより総テーブルサイズが決定される。
【００２３】
このため、ディスクサイズとキャッシュサイズに応じて総テーブルサイズが小さくなるようにｎを設定する。ここで、ｎの決定方法について説明する。
ｎ＝ディスクサイズ／キャッシュページサイズ／ｍで表される。ここで、例としてキャッシュページサイズを５０ｋＢ、テーブルＢのエントリ数を１００（図３のｍに対応）とした時に、ディスクサイズをｘｋＢとすると、テーブルのエントリ数（図３のｎに対応）は次式となる。
【００２４】
テーブルＡのエントリ数＝ｘ／５０／１００
次にｍの決定方法について説明する。ポインタの大きさを４Ｂとすると、
テーブルＡの総テーブルサイズ＝ｎ×４Ｂ
＝（ディスクサイズ４Ｂ）／（キャッシュサイズｍ）
ここで、ｎ×４Ｂは１つのテーブルのサイズである。
テーブルＢの総テーブルサイズ＝ｍ×４Ｂ
×（キャッシュサイズ）／（キャッシュページサイズ）
ここで、ｍ×４Ｂは１つのテーブルのサイズである。また、
（キャッシュサイズ）／（キャッシュページサイズ）はキャッシュページ数（＝テーブル数）となる。
【００２５】
総テーブルサイズ＝テーブルＡの総テーブルサイズ＋テーブルＢの総テーブルサイズ
＝（ディスクサイズ×４Ｂ）／（キャッシュサイズ×ｍ）
＋（ｍ×４Ｂ×キャッシュサイズ）／（キャッシュページサイズ）
となる。これから、
（キャッシュサイズｍ2＋ディスクサイズ）／ｍ
が最小となるようにｍを決定すれば、総テーブルサイズが最小となる。
【００２６】
また、テーブルＢの先頭１バイトは、テーブル内の有効キャッシュポインタ数のカウンタであり、テーブルの解放制御（デステージング）に使用される。次の３バイトは制御情報として、高域領域の排他制御等で使用されるものである。それ以降のキャッシュポインタは、ディスクの比較的狭い領域に対して１：１で対応する。このような一連の制御動作は、図示しない制御手段が行なう。制御手段としては、例えばマイクロコンピュータが用いられる。
【００２７】
本発明によれば、以下のような特徴がある。
１．ハッシュ関数を用いていないので、シノニムが発生しない。
２．隣接したアドレスのデータが必ず隣接したテーブルエントリになるため、トラックやストライプ等の物理データに依存したサーチに都合がよい。
３．シノニムが発生しないため、ヒット／ミス判定の最悪検索時間が短い。
４．図９に示した従来技術に比較して、テーブルサイズが大幅に削減可能である。キャッシュに対してディスクが巨大であるほど削減可能になる。
【００２８】
以上、説明したように、本発明によれば、論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブルでアクセスするキャッシュページへのポインタを示す第２のテーブルを設け、これら第１及び第２のテーブルを動的に変化させる制御手段を設けることにより、テーブルを分割・動的に管理することで、テーブルサイズを小さくすることができる。
【００２９】
次に、テーブルサイズについて説明する。例としてテーブルＢのエントリ数（図３のｍを示す）を１２８とすると、テーブルＡのサイズは、図９に示すキャッシュ管理テーブルの１／１２８となる。また、テーブルＢの数については、キャッシュサイズに比例するため、ディスクサイズとキャッシュサイズとの差が大きくなっても（キャッシュサイズに対してディスクサイズがはるかに大きくてもテーブルサイズが小さくてすむの意味）、テーブルサイズは小さくてすみ、コントローラメモリ（図８参照）を有効に使用可能である。
【００３０】
次に、キャッシュヒット／ミス判定処理手順について説明する。
【００３１】
以下に、キャッシュ管理テーブルＡ及びテーブルＢを使用したヒット／ミス判定の手順を示す。本発明では、最初に判定対象データのディスクアドレスから対応するテーブルＡのエントリＡｉと、そこに接続されているテーブルＢのエントリＢｊを求める。例として、下記の条件でＡｉ及びＢｊを求めると以下のようになる。
【００３２】
対象データの先頭アドレス：ディスクの先頭から１８５４２０ＫＢ目の部分
キャッシュページのサイズ：５０ＫＢ
テーブルＢの総エントリ数：１００
以上の条件を基にＡｉとＢｊを求める。ここで、ｉの取り得る値は０〜ｎ−１になり、ｊの取り得る値は０〜ｍ−１になる。
Ａｉ＝１８５４２０／５０／１００＝３７
Ｂｊ＝（１８５４２０％（５０×１００））／５０＝８
ここで、記号「％」は、以下のような演算になる。例えば、「ｘ％１０」という算術式では、ある数ｘを１０で割算した時の余りが答となるような演算である。従って、上式は１８５４２０÷５０００＝３７余り４２０となるので、その答えは４２０となる。この４２０を５０で割ると、４２０／５０＝８となる。このようにして求めたＡｉ，Ｂｊにより以下の手順でヒット／ミス判定を行なう。
【００３３】
図４はキャッシュヒット／ミス判定処理手順を示すフローチャートである。処理動作は、本願発明の制御手段が行なう（以下同様）。先ず、テーブルＡのエントリＡｉの内容を読み取る（Ｓ１）。次に、Ａｉの内容は空かどうかチェックする（Ｓ２）。空であった場合には、キャッシュミスとなる。空でない場合、Ａｉのポインタが示すテーブルＢのエントリＢｊを読み取る（Ｓ３）。次に、Ｂｊの内容は空かどうかチェックする（Ｓ４）。空の場合には、キャッシュミスとなる。空でない場合には、キャッシュヒットとなる。
【００３４】
次に、キャッシュデータステージングについて説明する。ステージング処理では、キャッシュページのみを獲得する場合と、キャッシュページと共にテーブルＢを獲得する場合がある。最初にステージング対象データのディスクアドレスから対応するテーブルＡのエントリＡｉと、そこに接続されるテーブルＢのエントリＢｊを求める。求めたＡｉ及びＢｊより下記手順でステージング処理を行なう。
【００３５】
図５はキャッシュデータステージング処理手順を示すフローチャートである。先ず、テーブルＡのエントリＡｉの内容を読み取る（Ｓ１）。次に、読み取ったＡｉに対してＡｉの内容が空かどうかチェックする（Ｓ２）。空の場合には、テーブルＢを獲得し、Ａｉの内容を獲得したテーブルＢへのポインタとする（Ｓ３）。次に、キャッシュページを獲得し、Ｂｊの内容を獲得したキャッシュページへのポインタとする。そして、テーブルＢのカウンタを１だけ更新する（Ｓ４）。
【００３６】
ステップＳ２において、Ａｉの内容が空でない場合には、Ａｉの内容が示すテーブルＢのエントリＢｊを読み取る（Ｓ５）。そして、Ｂｊの内容が空かどうかチェックする（Ｓ６）。空であった場合には、前述したステップＳ４の処理を行なう。空でない場合には、Ｂｊの内容が示すキャッシュページにデータを書き込む（又は読み込む）（Ｓ７）。
【００３７】
次に、キャッシュデータ・デステージング処理手順について説明する。デステージング処理とは、キャッシュメモリからデータを追い出す処理を行なうことをいう。デステージング処理では、キャッシュページのみ解放する場合と、キャッシュページと共にテーブルＢを解放する場合がある。テーブルＢの解放を行なうための判断には、テーブルが持っているカウンタを使用する（図３に示すテーブルＢの構成参照）。最初に判定対象データのディスクアドレスから対応するテーブルＡのエントリＡｉと、そこに接続されるテーブルＢのエントリＢｊを求める。そして、求めたＡｉ及びＢｊにより下記手順でデステージング処理を行なう。
【００３８】
図６はキャッシュデータ・デステージング処理手順を示すフローチャートである。先ず、キャッシュページを解放し、Ｂｊの内容をクリアする。キャッシュページを解放したことに伴い、テーブルＢのカウンタを１だけ減算する（Ｓ１）。次に、テーブルＢのカウンタが０より大きいかどうかチェックする（Ｓ２）。０より大きい場合には、処理を終了する。０より大きくない場合には、テーブルＢを解放し、テーブルＡのエントリＡｉをクリアする（Ｓ３）。
【００３９】
このように、本発明によれば、論理ディスクサイズの全アドレスに対する粒度の粗い第１のテーブル（テーブルＡ）でアクセスするキャッシュページへのポインタを示す第２のテーブル（テーブルＢ）を設け、これら第１及び第２のテーブルを動的に変化させることにより、テーブルを分割・動的に管理することで、テーブルサイズを小さくすることができる。
【図面の簡単な説明】
【００４０】
【図１】本発明方法の原理を示すフローチャートである。
【図２】本発明の動作の一例を示す図である。
【図３】テーブルＡとテーブルＢの構成例を示す図である。
【図４】キャッシュヒット／ミス判定処理手順を示すフローチャートである。
【図５】キャッシュデータステージング処理手順を示すフローチャートである。
【図６】キャッシュデータ・デステージング処理手順を示すフローチャートである。
【図７】レイド装置の構成例を示すブロック図である。
【図８】コントローラメモリの構成例を示すブロック図である。
【図９】従来のキャッシュ管理方法の説明図である。
【符号の説明】
【００４１】
１    ディスク
２    キャッシュメモリ
３’  管理テーブル
４    テーブルＡ
４’  未割り当てテーブルＡ
【図１】
2005182185.tif 000003
【図２】
2005182185.tif 000004
【図３】
2005182185.tif 000005
【図４】
2005182185.tif 000006
【図５】
2005182185.tif 000007
【図６】
2005182185.tif 000008
【図７】
2005182185.tif 000009
【図８】
2005182185.tif 000010
【図９】
2005182185.tif 000011