JPH02197941A - ディスクキャッシュの制御方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、ディスク装置のアクセスの高速化を図ったデ
ィスクキャッシュの制御方式に関する。

（従来の技術） 情報処理装置の大容量記憶媒体として、磁気ディスクや
光ディスク等のディスク装置が広く使用されている。

ディスク装置は、データのリードライトを、読み書きヘ
ッドをスキャンさせながら実行することから、読み書き
速度がプロセッサの動作速度に比べて著しく遅い。この
ため、ディスクアクセスの高速化を図るべく、ディスク
キャッシュシステムが採用されている。

このシステムにおいては、キャッシュメモリ上に、ディ
スクに格納されたデータの一部を転記し、プロセッサは
キャッシュテーブルを参照しながらキャッシュメモリを
アクセスする。キャッシュメモリには、最新にアクセス
されたデータを優先して転記しておき、キャッシュメモ
リをアクセスする確率を高くする。キャッシュメモリへ
のデータの転記法は、先入れ先出しくＦＩＦＯ）法やＬ
ＲＵ法等が採用される。

また、キャッシュテーブルの構成及び参照方法に着目す
ると、次の２種の方式が挙げられる。

第２図に、従来のフルセットアソシアティブ方式の説明
図を示す。

先ず、図の右側部分に、ディスクのアドレス空間を示す
。

この例では、ディスクに格納されたデータをＰ個の論理
ブロック３に分割する。更に、各論理ブロック３をＱ個
のサブブロック５に分割する。

具体的には、例えば、サブブロックは２０４８バイト構
成とされ、１つの論理ブロック３は２５６個のサブブロ
ック５に分割する。

一方、キャッシュメモリ２１には、サブブロック単位で
データを転記するための領域２４をＭ個設ける。キャッ
シュメモリ２１には、最新にアクセスされたサブブロッ
ク５を優先して転記する。

これは、従来よりよく知られたＬＲＵ方式によって実行
される。

また、キャッシュテーブル２２には、キャッシュメモリ
２１に設けられた領域２４の数Ｍと同一数のエントリ２
６が格納される。各エントリ２６は、キャッシュメモリ
２１中の何れかの領域２４と１対１で対応するよう設け
られる。そして、エントリ２６には、サブブロック５を
アクセスするための情報、即ち、ディスク上のＰ個の論
理ブロック３のうち何れの論理ブロック３に含まれ、そ
の論理ブロック３の何番目のサブブロック５に含まれて
いるか等の情報が含められる。

このような方式では、プロセッサが何れかのサブブロッ
ク５をアクセスする場合、先ず、キャッシュテーブル２
２を参照し、該当するサブブロック５がキャッシュメモ
リ２１に格納されているかどうかを判断する。エントリ
２６に含まれた情報によってこれを判断し、キャッシュ
メモリ２１に格納されていれば、対応するキャッシュメ
モリ２１上の領域２４からサブブロックをアクセスする
。キャッシュテーブル２２を参照しても、該当するサブ
ブロックが見当たらない場合、そのサブブロックがディ
スクから新たに読出され、キャッシュメモリ２１に転記
される。キャッシュメモリ２１のすべての領域に、既に
他のサブブロックが転記されてしまっている場合、もっ
とも古く参照されたサブブロックがキャッシュメモリ２
１から追出され、最新にアクセスされたサブブロックが
キャッシュメモリ２１に格納される。

以上のようにして、アクセスされる確率の高いサブブロ
ックをキャッシュメモリ２１に格納し、高速アクセスを
図っている。

次に、第３図に、Ｎセットアソシアティブ方式の説明図
を示す。

尚、第３図の場合、Ｎ＝４即ち４セットアソシアティブ
方式の具体例を図示している。

この方式においては、第２図と同様に、ディスクのアド
レス空間をＰ個の論理ブロック３に分割し、更に各論理
ブロック３をＱ個のサブブロック５に分割する。

ここで、更にこの方式においては、各論理ブロック３の
対応する位置にある各サブブロック５をまとめてサブブ
ロック群７を設定する。このサブブロック群７は、即ち
、全体でＱ個設定される。

一方、キャッシュメモリ３１は、４セツトアソシアテイ
ブの場合、そのメモリ空間を４つの区域３７に分割する
。そして、各区域３７には、それぞれＱ個の領域３４を
設け、各領域３４にそれぞれサブブロック５が格納され
るよう設定する。

一方、キャッシュテーブル３２は、各サブブロック群毎
に４セット即ち、最大４個のエントリ３６を格納するよ
う構成する。即ち、キャッシュテーブル３２には、最大
４×Ｑ個のエントリが格納される。そして、各サブブロ
ック群７毎にこのキャッシュテーブルをみた場合、エン
トリは最新に参照されたものを優先して４個ずつ格納さ
れるよう設定されている。

以上の方式において、プロセッサがサブブロック５をア
クセスしようとする場合、先ず、キャッシュテーブル３
２を参照する。この場合、初めにアクセスしようとする
サブブロック５が、何れのサブブロック群７に含まれる
か判断し、図のキャッシュテーブル３２の行を選定する
。そして、その行に含まれる４つのエントリ３６を参照
し、該当するサブブロック５に対応するエントリ３６が
あるか否かを判断する。

ここで、各エントリ３６は、キャッシュメモリ３１の各
領域３４に対し、物理的に１対ｌで対応付けられており
、アクセスしようとするサブブロック５に対応するエン
トリ３６が、キャッシュテーブル３２上で見付かった場
合には、直ちにキャッシュメモリ３１上の対応領域３４
がアクセスできる。また、キャッシュテーブル３２上に
アクセスしようとするサブブロック５に対応するエント
リ３６が存在しない場合には、キャッシュメモリ３１上
の、対応するサブブロック群７のサブブロック５の１つ
を追出し、新たにアクセスされたサブブロックを転記す
る。

即ち、４セットアソシアティブ方式においては、ディス
クの１つのサブブロック群７に含まれる最大４つのサブ
ブロックが、キャッシュメモリ３１に転記され、サブブ
ロック群７毎に最新にアクセスされたサブブロック５を
優先して転記するＬＲＵ処理を行なう。キャッシュテー
ブル３２の参照は、先に述べたように、アクセスしよう
とするサブブロック５が何れのサブブロック群７に該当
するかを判断して、キャッシュテーブル３２上の行を特
定し、その後、キャッシュテーブル３２を列方向に参照
するといった手法をとる。従って、キャッシュテーブル
を端から順に参照して、該当するエントリを見つける第
２図に示したフルセットアソシアティブ方式に比べて、
キャッシュテーブルの参照速度が高速化される利点を有
している。

（発明が解決しようとする課題） ところが、以上のような構成の方式には、それぞれ次の
ような問題点があった。

先ず、第２′図に示したフルセットアソシアティブ方式
では、キャッシュテーブル２２を端から順に参照してい
くため、エントリ格納数が増えてキャッシュテーブル２
２が大きくなった場合、該当するエントリを見つけるた
めの時間が長くなるという欠点がある。

例えば、キャッシュメモリ２１上にアクセスしようとす
るサブブロックが転記されていないような場合には、キ
ャツシュテーブル２２全体を参照し、その後ディスクか
らアクセスすべきサブブロックをディスクキャッシュに
転記する作業を実行することになる。従って、例えば、
エントリの数が１０００個以上もある比較的大型のコン
ピュータシステムにおいては、アクセス時間が極めて長
時間になるという問題があった。

一方、第３図に示したＮセットアソシアティブ方式の場
合には、キャッシュテーブル３２を行方向と列方向に２
次元的に参照するため、そのセット数が４セツトという
ように少なければ、比較的短時間でエントリの参照が可
能である。

ところが、この場合、キャッシュメモリ３１には、１つ
のサブブロック群７に含まれるサブブロック５のうち、
そのセット数に相当する、例えば４個のサブブロックし
か転記することができない。従って、例えば、同一のサ
ブブロック群７にアクセスが集中した場合、キャッシュ
メモリ３１から頻繁にサブブロックが追出され、新たな
サブブロックが転記されるということになり、キャッシ
ュメモリ３１にアクセスすべきサブブロックか存在する
確率が低くなるという問題がある。

本発明は以上の点に着目してなされたもので、アクセス
すべきサブブロックが、キャッシュメモリ上に存在する
確率を向上させると共に、アクセス速度を向上させたデ
ィスクキャッシュの制御方式を提供することを目的とす
るものである。

（課題を解決するための手段） 本発明のディスクキャッシュの制御方式は、ディスクに
格納されたデータをＰ個の論理ブロックに分割し、さら
に前記論理ブロックをＱ個のサブブロックに分割して、
前記各論理ブロック中の対応する位置にある各サブブロ
ックをまとめてサブブロック群と呼び、合計Ｑ個のサブ
ブロック群を設定する一方、前記サブブロック単位で前
記データを転記するための領域をＭ個（但し、Ｍ＜Ｐ×
Ｑ）設け、最新にアクセスされたサブブロックを優先し
て転記するキャッシュメモリと、前記各サブブロック群
毎に、最大Ｎ個（但し、Ｎ＜Ｐ）のエントリを、最新に
参照されたエントリを優先して格納するよう設定したキ
ャシュテーブルとを設け、Ｎ×Ｑ＞Ｍとなるように前記
キャッシュテーブルの容量を選定し、前記エントリは、
前記サブブロックを前記キャッシュメモリに転記したと
き、各サブブロック毎に作成され、対応するサブブロッ
クの属する前記論理ブロックを特定する情報と、対応す
るサブブロックの転記された前記キャッシュメモリ上の
アドレス情報とを含むことを特徴とするものである。

（作用） 以上のディスクキャッシュの制御方式においては、第１
図に示すように、例えば、ディスクの論理ブロック３の
第１行のサブブロック群７にアクセスが集中したとき、
Ｎ個例えば３２個までのサブブロック５のデータを、キ
ャッシュメモリ１上のいずれかの領域４に残すことがで
きる。キャッシュメモリｌにある領域４は、キャッシュ
テーブル２のエントリ６により管理される。キャッシュ
テーブル２の各エントリ６は、対応するサブブロックの
属するディスクの論理ブロック３を特定している。また
、キャッシュテーブル２の各エントリ６には、キャッシ
ュメモリ１上にデータを転記した領域４のアドレスが記
憶される。これにより、キャッシュテーブル２のエント
リ６とキャッシュメモリ１の領域４が対応づけられる。

キャッシュメモリ１の領域数は、キャッシュテーブル２
のエントリ数より少ないが、アクセスが集中したサブブ
ロック７に対しては、最大Ｎ＝３２個までの多くの領域
が割り当てられ、アクセスが少ないサブブロック７に対
しては、より少なく領域４が割り当てられて調整が図ら
れる。

（実施例） 第１図は、本発明のディスクキャッシュの制御方式を適
用した装置の実施例を示す図、第４図は、第１図のキャ
ッシュテーブルの拡大図である。

第１図の装置は、キャッシュメモリ１と、キャッシュテ
ーブル２と、これらを制御するコントローラ８とから成
る。

この装置に接続されるディスクのアドレス空間は、従来
のＮセットアソシアティブ方式の場合と同様にして、Ｐ
　（ＩＩの論理ブロック３に分割され、かつ各論理ブロ
ックをＱ個のサブブロックに分割される。また、各論理
ブロック３の対応する位置にある各サブブロック５をま
とめ、サブブロック群７を設定する。

キャッシュメモリ１は、ＤＲＡＭまたはＳＲＡＭ等によ
り構成されるメモリである。このキャッシュメモリ１は
、Ｍ個（例えば、２５６Ｘ　４個）の領域４に分割され
ている。領域数Ｍは、ディスクのサブブロック総数Ｐ×
Ｑより小さい。

領域４の１つ当たりの大きさは、サブブロック５の大き
さと同一にされている。この大きさは、例えば、２０４
８バイトである。領域４には、コントローラ８により、
サブブロック単位でデータが転記される。データの転記
は、最新にアクセスされたサブブロック５を優先して行
なわれる。

［キャッシュテーブルの説明］ キャッシュテーブル２は、各サブブロック群ごとに、最
大Ｎ個（例えば、２５６Ｘ８個）のエントリ６を格納す
る。サブブロック群７ごとの最大エントリ数Ｎは、論理
ブロック総数Ｐより少なくなっている。これらのサブブ
ロック群７ごとのエントリは、最新に参照されたエント
リを優先してキャッシュテーブル２に格納される。

キャッシュテーブル２は、各エントリ６を、行方向及び
列方向に２次元的に配列するように格納する。第０〜２
５５行の各行のエントリ６は、それぞれディスクの論理
ブロック３の第０〜２５５行の各行のサブブロック群７
に含まれるサブブロック５に対応している。

第４図に、エントリ６の構成図を示す。

エントリ６は、まず、ディスクの論理ブロック番号４１
を含んでいる。この論理ブロック番号４１は、エントリ
がディスクのどの論理ブロック３に含まれるサブブロッ
ク５に対応するかを決めるものである。各エントリ６は
、サブブロック５をキャッシュメモリ１に転記したとき
、各サブブロックごとに作成される。

また、この外にエントリ６には、キャッシュメモリ１の
領域４の先頭アドレスを示すキャッシュ領域アドレス４
２が含まれている。

更に、エントリ同志を連鎖させるためのポインタ４３乃
至４８が格納されている。これらのポインタによりアク
セス時のエントリ６の参照順序が定められる。この結果
、エントリ６を参照のための優先順に、ソートしておか
なくても、ポインタを追いながら、ＬＲＵ順に参照する
ことができる。

［ポインタの具体的な説明］ 第５図は、第４図に示した全エントリについてのＬＲＵ
ポインタ４３．４４の具体的な説明図である。このポイ
ンタ４３．４４は、キャッシュテーブル２上に新たにエ
ントリが作成される際に、そのつと設定されるものであ
る。第５図はキャッシュテーブルの一部を示しており、
図中の数字は、現時点のディスクのアクセス順序を新し
い順に示すものである。

即ち、図中○印を付けて“１゛°と記入した第１列第１
行のエントリは、最新にアクセスされたもので、“２０
”と記入した第２行第２列のエントリは最古にアクセス
されたものとする。

従って、第１行第０列の三角形のマークを付けたエント
リに着目すると、このエントリの、全エントリについて
のＬＲＵ前ポインタ４３は、第１行第１列のエントリの
格納位置を指し、全エントリについてのＬＲＵ後ポイン
タ４４は、第１行第３１列のエントリの格納位置を指す
ことになる。

また、全エントリのうち最も古く作成されたエントリと
、最も新しく作成されたエントリとの格納位置を示すポ
インタは、コントローラ８（第１図参照）内のメモリ８
ａに格納される。

第６図は、第１図のコントローラの制御情報の内容を示
す図である。

この制御情報は、キャッシュテーブルの全エントリにつ
いてのＬＲＵ最古ポインタ８１と、キャッシュテーブル
の全エントリについてのＬＲＵ最新ポインタ８２と、キ
ャッシュメモリの空領域ポインタ８３と、キャッシュメ
モリの空領域数８４とから成る。

キャッシュテーブルの全エントリについてのＬＲＵ最古
ポインタ８１は、１番古いエントリ（２０）の格納位置
を示す。キャッシュテーブルの全エントリについてのＬ
ＲＵ最新ポインタ８２は、１番新しいエントリ（１）の
格納位置を示す。また、キャッシュメモリの空領域ポイ
ンタ８３は、キャッシュメモリ１の空領域のうち１番先
頭にあるもののアドレスを示す。キャッシュメモリの空
領域数８４は、キャッシュメモリ１の空領域の数を示す
ものである。

一方、Ｎセットアソシアティブ方式のディスクキャッシ
ュ制御においては、キャッシュテーブルをサブブロック
群ごと即ち行ごとに参照するため、行内の参照順序を示
すポインタが必要である。このポインタは、従来の装置
にも存在していたものである。

第７図は、キャッシュテーブルの行ごとのＬＲＵポイン
タの説明図である。このポインタは、ディスクのアクセ
ス時にエントリが参照される際に、設定されるものであ
る。第７図はキャッシュテーブルの１つの行を取出して
示したもので、図中の数字は、現時点のキャッシュテー
ブルの参照順序を新しい順に示すものである。即ち、こ
の行で○印を付けて“ｌ”と記入した第２９列のエント
リは最新にアクセスされたもので、３２°°と記入した
エントリは最古にアクセスされたものである。

第７図中三角形のマークを付けた第１列のエントリに着
目すると、行ごとのＬＲＵ前ポインタ４５は、第１５列
の°４゛と記入したエントリ（４）の格納位置を示す。

また、ＬＲＵ後ポインタ４６は、第１列の“６°゛と記
入したエントリ（６）の格納位置を示す。ＬＲＵ最新ポ
インタ４７は、１°゛と記入したエントリの格納位置を
示し、ＬＲＵ最古ポインタ４８は、“３１゛°と記入し
たエントリの格納位置を示す。

［アクセス動作の説明］ 以上の設定を行なった上で、図示しないプロセッサは、
次のようにディスクのアクセスを実行する。

ディスクのアクセスに先立って、コマンドによりアクセ
スすべきディスクアドレスを指定する。

このディスクアドレスは、２進数ないしは１６進数によ
り指定される。このディスクアドレスの上位桁により、
ディスクの論理ブロック３の行が特定される。また、こ
のディスクアドレスの下位桁により、ディスクの論理ブ
ロック番号が特定される。即ち、このディスクアドレス
により、参照の対象であるサブブロックが、２５６行の
サブブロック５のうちのどのサブブロックであり、その
サブブロックがディスクの論理ブロック３のうちのどの
ブロックに存在するかが特定される。そして、特定され
たサブブロック５の行位置に対応するキャッシュテーブ
ル２の行のエントリ６が参照される。この参照は、次の
ようにして行なわれる。

［キャッシュテーブルに参照対象のエントリがある場合
］ キャッシュテーブルに参照対象のエントリがある場合は
、該当行を列方向にサーチしていく途中で、参照対象で
あるエントリにヒツトする。サーチは、第７図に示すポ
インタを使ってＬＲＵ順に行なう。そして、ヒツトした
場合は、そのエントリからキャッシュ領域アドレスを取
出し、これにより、キャッシュメモリから対応するサブ
ブロックの読出しを行なう。

［キャッシュテーブルに参照対象のエントリがない場合
］ キャッシュテーブルに参照対象のエントリがない場合は
、該当行を列方向にサーチしていくが、参照対象である
エントリには、ヒツトしない。

サーチは、上述の場合と同様に、第７図に示すポインタ
を使ってＬＲＵ順に行なう。サーチ後、コントローラ８
は、キャッシュメモリの空領域数を読む。

キャッシュメモリに空領域がある場合、即ち、空領域数
が○でない場合には、キャッシュメモリの空領域ポイン
タ８３を読む。そして、このポインタ８３で示される領
域にディスクのサブブロック内のデータを転記する。そ
の後、キャッシュテーブルを更新する。

［キャッシュテーブルの更新］ ■同一行に格納できる最大数のエントリが格納済でない
場合、即ち同一行に空きがある場合は、空き位置にエン
トリを格納する。そして、行ごとのＬＲＵ最新ポインタ
４７を更新する。さらに、当該エントリ６の行ごとのＬ
ＲＵ前ポインタ４５と、行ごとのＬＲＵ後ポインタ４Ｇ
とにそれぞれ所定の格納位置を設定する。

■同一行に格納できる最大数のエントリが格納済の場合
、即ち同一行に空きがない場合は、行ごとのＬＲＵ最古
ポインタ４８の示す格納位置のエントリを追い出す。そ
して、その格納位置にエントリを新しく作成する。さら
に、行ごとのＬＲＵ最新ポインタ４７及び行ごとのＬＲ
Ｕ最古ポインタ４８をそれぞれ更新する。即ち、エント
リを追い出した格納位置を、行ごとのＬＲＵ最新ポイン
タ４７に設定し、２番目に古いエントリの格納位置を、
行ごとのＬＲＵ最古ポインタ４８に設定する。

一方、キャッシュメモリに空領域がない場合、即ち、空
領域数がＯの場合には、コントローラ８のキャッシュテ
ーブルの全エントリについてのＬＲＵ最古ポインタ８１
の示す格納位置のエントリを追い出す。その後、キャッ
シュテーブルのエントリを更新する。エントリの更新は
、上述した［キャッシュテーブルの更新］と同様にして
行なわれる。従って、キャッシュメモリが満杯になり、
キャッシュテーブル上の全エントリ数が、キャッシュメ
モリの領域数Ｍと等しくなったときは、それ以上エント
リが増やされない。このため、キャッシュメモリの同一
領域に対し、２以上のエントリが作成されるようなこと
はない。

そして、追い出したエントリのキャッシュ領域アドレス
４２が示す領域のデータを追い出し、ディスクから読出
したサブブロックを転記する。

その後、新しく作成したエントリのキャッシュ領域アド
レス４２に、サブブロックを転記した領域のアドレスを
格納する。

本発明のディスクキャッシュの制御装置は、以上の実施
例に限定されない。

即ち、キャッシュテーブル２の行数や列数は、行Ｘ列が
キャッシュメモリ１の領域４の数より多くなるように決
めれば、どのような数にしてもよい。しかしながら、周
知のメモリリードライト及び照合動作は、２の累乗のデ
ータを一体に処理しているから、ハードウェアの構成上
は、キャッシュテーブルの列数は２の累乗の数になるよ
うにするのが最も効率的で好ましい。

（発明の効果） 以上の構成の本発明のディスクキャッシュの制御方式は
、キャッシュテーブルなＮセットアソシアティブ形式に
したので、キャッシュテーブルの参照時間を短くするこ
とができる。

また、各サブブロック群ごとにキャッシュテーブルに格
納できるエントリ数の最大値を大きくしたので、アクセ
スそのサブブロック群に集中したときのヒツト率を低下
させないようにできる。

これらにより、ディスクのアクセス時間を従来より更に
短縮することができる。

【図面の簡単な説明】

第１図は本発明に係るディスクキャッシュ制御装置の構
成を示す説明図、第２図は従来のフルセットアソシアテ
ィブ方式の説明図、第３図は従来の４セットアソシアテ
ィブ方式の説明図、第４図は本発明に係るキャッシュテ
ーブルのエントリの構成図、第５図は全エントリについ
てのＬＲＵポインタの説明図、第６図は本発明に係るコ
ントローラの制御情報の説明図、第７図は行ごとのＬＲ
Ｕポインタの説明図である。 １・・・キャッシュメモリ、 ２・・・キャッシュテーブル、 ３・・・ディスクの論理ブロック、４・・・領域、５・
・・サブブロック、６・・・エントリ。 特許出願人　沖電気工業株式会社 本発明に係るキャッシュテーブルのエントリ第４図

Claims (1)

1. 【特許請求の範囲】 ディスクに格納されたデータをＰ個の論理ブロックに分
   割し、 さらに前記論理ブロックをＱ個のサブブロックに分割し
   て、 前記各論理ブロック中の対応する位置にある各サブブロ
   ックをまとめてサブブロック群と呼び、合計Ｑ個のサブ
   ブロック群を設定する一方、前記サブブロック単位で前
   記データを転記するための領域をＭ個（但し、Ｍ＜Ｐ×
   Ｑ）設け、最新にアクセスされたサブブロックを優先し
   て転記するキャッシュメモリと、 前記各サブブロック群毎に、最大Ｎ個（但し、Ｎ＜Ｐ）
   のエントリを、最新に参照されたエントリを優先して格
   納するよう設定したキャッシュテーブルとを設け、Ｎ×
   Ｑ＞Ｍとなるように前記キャッシュテーブルの容量を選
   定し、 前記エントリは、前記サブブロックを前記 キャッシュメモリに転記したとき、各サブブロック毎に
   作成され、対応するサブブロックの属する前記論理ブロ
   ックを特定する情報と、対応するサブブロックの転記さ
   れた前記キャッシュメモリ上のアドレス情報とを含むこ
   とを特徴とするディスクキャッシュの制御方式。