JPH03296841A - キャッシュ制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はキャッシュ制御方式に関し、特に計算機システ
ムのファイルシステムにおいてバッファキャッシュメモ
リおよび磁気ディスクキャッシュメモリの制御を行うキ
ャッシュ制御方式に関する。

〔従来の技術〕

計算機システムのファイルシステムには、メモリ間のデ
ータブロックの転送の速度と、磁気ディスク装置とメモ
リとの間のデータブロックの転送の速度との差を縮める
目的で、メモリの一部をバッファキャッシュメモリとし
て用い、さらにメモリの他の一部を磁気ディスクキャッ
シュメモリとして用いるものがある。

このようなファイルシステムにおいては、あるデータブ
ロックに対する読み込み要求に基づいて磁気ディスク装
置から利用者プログラムメモリ空間にデータブロックの
転送が行われる際には、磁気ディスク装置から読み込ま
れたデータブロックが一度磁気ディスクキャッシュメモ
リ上に保存され、さらにバッファキャッシュメモリ上に
格納されてから、利用者プログラムメモリ空間に転送さ
れていた。

これによって、再び同じデータブロックに対する読み込
み要求が発生した場合に、そのデータブロックがバッフ
ァキャッシュメモリ上に残っている場合（バソファキャ
ソシュヒソトの場合）またはバッファキャッシュメモリ
には残っていなくとも磁気ディスクキャッシュメモリ上
に残っている場合（ディスクキャッシュヒントの場合）
には、磁気ディスク装置から利用者プログラムメモリ空
間へのブロックデータの転送はバッファキャッシュメモ
リおよび磁気ディスクキャッシュメモリのどちらかから
利用者プログラムメモリ空間への転送で済み（磁気ディ
スク装置からの転送を必要とせず）、そのデータブロッ
クの転送（データ入出力）に要する時間の短縮が可能に
なっていた。

このようなファイルシステムにおいてバッファキャッシ
ュメモリおよび磁気ディスクキャッシュメモリの制御を
行うキャッシュ制御方式では、バッファキャッシュメモ
リの構成要素であるバッファキャッシュブロック（−船
釣に、データブロックの１つに割り当てられる領域）や
、磁気ディスクキャッシュメモリの構成要素であるディ
スクキャッシュブロック（−船釣に、データブロックの
正整数倍個に割り当てられる領域）は、その使用頻度が
考慮されて管理されている。

すなわち、バッファキャッシュメモリ上のバッファキャ
ッシュブロックの管理情報を持つバッファヘッダは、ハ
ツシュテーブルおよびフリーリストにより管理されてい
る（第２図＜ａ＞および（ｂ）参照）、ここで、フリー
リストにその時点で使用されていない（有効なデータブ
ロックが格納されていない）バッファキャッシュブロッ
クのバッファヘッダが接続されることにより、バッファ
キャッシュブロックの使用頻度が考慮されている。

なお、ハツシュテーブルの各エントリの値（第２図（ａ
）および（ｂ）における０−Ｎ　（Ｎは正整数））は、
そのエントリに接続されているバッファヘッダ（次のバ
ッファヘッダへのポインタを前のバッファヘッダまたは
エントリが持つことにより接続が形成されている）に対
応するバッファキャッシュブロックに格納されているデ
ータブロックのブロック番号を一定値で除したときの剰
余に該当する。

また、磁気ディスクキャッシュメモリ上のディスクキャ
ッシュブロックの管理情報を持つキャッシュフ゛ロンク
ヘソダは、プライオリティテーブルにより管理されてい
る（第３図（ａ）および（ｂ）参照）。ここで、プライ
オリティテーブルにおいては、磁気ディスクキャッシュ
メモリ上のディスクキャッシュブロックの使用頻度に応
じてそのディスクキャッシュブロックに対応するキャン
シュブロフクヘッダのプライオリティ　（第３図（ａ）
および（ｂ）における０〜Ｍ　（Ｍは正整数））が決め
られており、これによりディスクキャッシュブロックの
使用頻度が考慮されている。

従来、この種のキャッシュ制御方式では、実際のデータ
入出力要求（データブロックの転送要求）に起因した制
御（バッファキャッシュメモリまたは磁気ディスクキャ
ッシュメモリへのデータブロックの書き込みやバッファ
キャッシュメモリまたは磁気ディスクキャッシュメモリ
からのデータブロックの読み出しに関する制Ｗ）　Ｌ、
か行われていない。

したがって、ファイル制御手段の制御によっであるファ
イルが削除された際に、そのファイルで使用されていた
データブロックがバッファキャッシュメモリまたは磁気
ディスクキャッシュメモリ上に存在していた場合には、
バッファキャッシュメモリまたは磁気ディスクキャッシ
ュメモリ上の領域が足りなくなってそのデータブロック
に割り当てられていたノくツファキャッシュブロ・ツク
またはディスクキャッシュブロックが他のデータブロッ
クのために置き換えられるまではそのデータブロックが
バッファキャッシュブロックまたはディスクキャッシュ
フ゛ロックに割り当てられ続けていた。

〔発明が解決しようとする課題〕

上述した従来のキャッシュ制御方式では、ファイルが削
除された際にそのファイルで使用されていたデータブロ
ックがバッファキャッシュメモリまたは磁気ディスクキ
ャッシュメモリ上に存在していた場合に、すぐにはその
データブロックに割り当てられていたバッファキャッジ
エフ゛ロックまたはディスクキャッシュブロックに対す
る制御が行われないので、フリーリストにより管理され
ていないバンファヘソダに対応するバッファキャッシュ
ブロックやプライオリティテーブル中の高いプライオリ
ティを示すエントリに接続されているキャッシュブロッ
クヘッダに対応するディスクキャッシュブロックに格納
されているデータブロックに係るファイルが削除された
場合には、すてり−不要となったデータブロックが他の
データブロックよりも長くバッファキャッシュメモリや
磁気ディスクキャッシュメモリ上に残ることになり　（
有効なデータブロックが先に追い出されるという事態が
生じる）、バッファキャッシュメモリや磁気ディスクキ
ャッシュメモリにおけるキャッシュヒント率が悪くなる
という欠点がある。

本発明の目的は、上述の点に鑑み、あるファイルが削除
された際にそのファイルで使用されていたデータブロッ
クが格納されているバッファキャッシュブロックの全て
をフリーリストに接続し、そのようなデータブロックが
格納されているディスクキャッシュブロックの全てのプ
ライオリティを最も低くすることにより、有効なデータ
ブロックをなるべくバッファキャッシュメモリや磁気デ
ィスクキャッシュメモリ上に残してキャツシュヒツト率
の向上を図るキャッシュ制御方式を提供することにある
。

〔課題を解決するための手段〕

本発明のキャッシュ制御方式は、磁気ディスク装置上の
ファイルの作成および削除等の管理制御を行うファイル
制御手段と、このファイル制御手段により管理制御が行
われるファイルとそのファイルに使用されるデータブロ
ックとの対応を管理し利用者プログラムメモリ空間とバ
ッファキャッシュメモリとの間のデータブロックの転送
の制御を行うファイルブロック制御手段と、データブロ
ックの転送の際に未使用のバッファキャッシュブロック
を確保しファイルの削除に係る通知を受けた場合にその
ファイルに使用されていたデータブロックに割り当てら
れていたバッファキャッシュブロックのバッファヘフグ
をフリーリストに接続するフリーバッファ制御手段と、
ハフシュテーブル制御手段および前記フリーバッファ制
御手段による制御に基づきデータブロックの転送に使用
すべきバッファキャッシュブロックを選択して前記ファ
イルブロック制御手段に提供しバッファキャッシュメモ
リと磁気ディスクキャッシュメモリとの間のデータブロ
ックの転送の制御を行うバッファキャッシュ制御手段と
、ブライオリティテーブルにおいて管理されるディスク
キャッシュフロックのプライオリティを制御しファイル
の削除に係る通知を受けた場合にそのファイルに使用さ
れていたデータブロックに割り当てられていたディスク
キャッシュブロックのプライオリティを最も低くする制
御を行うキャッシュブロックプライオリティ制御手段と
、磁気ディスクキャッシュブロック制御手段および前記
キャッシュブロックプライオリティ制御手段による制御
に基づきデータブロックの転送に使用すべきディスクキ
ャッシュブロックを選択して前記バッファキャッシュ制
御手段に提供し磁気ディスク装置制御手段を用いて磁気
ディスクキャッシュメモリと磁気ディスク装置との間の
データブロックの転送の制御を行う磁気ディスクキャン
シュ制御手段と、前記ファイル制御手段によりファイル
が削除された場合にそのファイルの削除に係る通知を前
記フリーバッファ制御手段および前記キャッシュブロッ
クプライオリティ制御手段に提供するファイル管理情報
伝達手段とを有する。

〔作用〕

本発明のキャッシュ制御方式では、ファイル制御手段が
磁気ディスク装置上のファイルの作成および削除等の管
理制御を行い、ファイルブロック制御手段がファイル制
御手段により管理制御が行われるファイルとそのファイ
ルに使用されるデータブロックとの対応を管理し利用者
プログラムメモリ空間とバッファキャッシュメモリとの
間のデータブロックの転送の制御を行い、フリーバッフ
ァ制御手段がデータブロックの転送の際に未使用のバッ
ファキャッシュブロックを確保しファイルの削除に係る
通知を受けた場合にそのファイルに使用されていたデー
タブロックに割り当てられていたバッファキャンシュブ
ロックのバッファヘンダをフリーリストに接続し、バッ
ファキャッシュ制御手段がハツシュテーブル制御手段お
よびフリーバッファ制御手段による制御に基づきデータ
ブロックの転送に使用すべきバッファキャッシュフロ・
７りを選択してファイルブロック制御手段に提供しバッ
ファキャッシュメモリと磁気ディスクキ中フシュメモリ
との間のデータブロックの転送の制御を行い、キャッシ
ュブロックプライオリティ制御手段がプライオリティテ
ーブルにおいて管理されるディスクキャッシュブロック
のプライオリティを制御しファイルの削除に係る通知を
受けた場合にそのファイルに使用されていたデータブロ
ックに割り当てられていたディスクキャッシュブロック
のプライオリティを最も低くする制御を行い、磁気ディ
スクキャッシュ制御手段が磁気ディスクキャッシュブロ
ック制御手段およびキャッシュブロックプライオリティ
制御手段による制御に基づきデータブロックの転送に使
用すべきディスクキャッシュブロックを選択してバッフ
ァキャッシュ制御手段に提供し磁気ディスク装置制御手
段を用いて磁気ディスクキャッシュメモリと磁気ディス
ク装置との間のデータブロックの転送の制御を行い、フ
ァイル管理情報伝達手段がファイル制御手段によりファ
イルが削除された場合にそのファイルの削除に係る通知
をフリーバッファ制御手段およびキャッシュブロックプ
ライオリティ制御手段に提供する。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明のキャッシュ制御方式の一実施例の構
成を示すブロック図である０本実施例のキャッシュ制御
方式は、ファイル制御手段１と、ファイル管理情報伝達
手段２と、バッファキャッシュ制御手段３と、フリーバ
ッファ制御手段４と、磁気ディスクキャッシュ制御手段
５と、磁気ディスクキャッシュブロック制御手段６と、
キャッシュブロックプライオリティ制御手段７と、ハツ
シュテーブル制御手段８と、ファイルブロック制御手段
９と、磁気ディスク装置制御手段１０と、プライオリテ
ィテーブル１１と、ハツシュテーブル１２　（フリーリ
スト１２０が付設されている）と、バッファヘッダ群１
３と、キャッシュブロックヘッダ群１４と、利用者プロ
グラムメモリ空間１５と、バッファキャッシュメモリ１
６と、磁気ディスクキャッシュメモリ１７と、磁気ディ
スク装置１８とを含んで構成されている。

第２図（ａ）および（ｂ）は、ハツシュテーブル１２お
よびフリーリスト１２０によるバッファヘッダ群１３の
管理の態様の具体例を示す図である。第２図（ａ）中の
フリーリスト１２０に接続されているバッファヘッダＧ
およびＨに対応するバッファキャッシュブロックがフリ
ーな状Ｓ（使用されていない状ｊｌｉ）にあり、バッフ
ァキャッシュブロックの使用要求が発生するとこれらの
バッファキャッシュブロックから先に割り当てられる。

第３図（ａ）および（ｂ）は、プライオリティテーブル
１１によるキャッシュブロックヘッダ群１４の管理の態
様の具体例を示す図である。第３図（ａ）において、エ
ントリＯに接続されているキャッシュブロックヘッダＡ
′に対応するディスクキャッシュブロックのプライオリ
ティが最低であり、エントリＭに接続されているキャッ
シュフロックヘッダＥ′およびＦ′に対応するディスク
キャッシュブロックのプライオリティが最高であり、プ
ライオリティの低いものから順に他のデータブロックに
割り当てられていく。

次に、このように構成された本実施例のキャッシュ制御
方式の動作について説明する。

初めに、ファイル制御手段１およびファイルブロック制
御手段９の制御によって、ファイルの作成や既存のファ
イルに対するデータ入出力に基づいてデータブロックの
転送が行われる場合の動作について説明する。

ファイル制御手段１を介した利用者プログラムからのフ
ァイルの作成やファイルに対するデータ入出力の要求に
より、ファイルブロック制御手段９はバッファキャッシ
ュ制御手段３に対しである特定のデータブロックの転送
のために使用できるバッファキャッシュメモリ１６上の
バッファキャッシュブロックを要求する。

この要求を受けたバッファキャッシュ制御手段３は、ハ
ツシュテーブル制御手段８に制御を渡す。

ハツシュテーブル制御手段８は、すでにそのデータブロ
ックに割り当てられているバッファキャッシュブロック
があるか否かをハツシュテーブル１２およびハツシュテ
ーブル１２により管理されているバッファヘッダ群１３
を参照して探索する。

すでにそのデータブロックに割り当てられているバッフ
ァキャッシュブロックがあると判断した場合には、ハツ
シュテーブル制御手段８はバッファキャッシュ制御手段
３およびファイルブロック制御手段９（バッファキャッ
シュ制御手段３を介して）にそのバッファキャッシュブ
ロックに対応するバッファヘッダへのポインタを渡す。

まだそのデータブロックに割り当てられているバッファ
キャッシュブロックがないと判断した場合には、ハツシ
ュテーブル制御手段８はバッファキャッシュ制御手段３
を介してフリーバッファ制御手段４に制御を渡す。

フリーバッファ制御手段４は、フリーリスト１２０を参
照して１ノインフアキヤフシユメモリ１６上の未使用の
バッファキャッシュプロ、りに対応するバッファへ７ダ
へのポインタをバッファキャッシュ制御手段３およびフ
ァイルブロック制御手段９（バッファキャッシュ制御手
段３を介して）に渡す。

バッファへラダへのポインタを受は取ったファイルブロ
ック制御手段９は、そのバッファヘッダに対応するバッ
ファキャッシュブロックを使用して、利用者プログラム
メモリ空間１５とバッファキャッシュメモリ１６との間
のデータブロックの転送を制御する。

次に、バッファキャッシュ制御手段３は、磁気ディスク
キャッシュ制御手段５に対して、上述の特定のデータブ
ロックの転送のために使用できる磁気ディスクキャッシ
ュメモリ１７上のディスクキャッシュブロックを要求す
る。

この要求を受けた磁気ディスクキャッシュ制御手段５は
、磁気ディスクキャッシュブロック制御手段６に制御を
渡す。

磁気ディスクキャッシュブロック制御手段６は、キャッ
シュブロックプライオリティ制御手段７を介して、すで
にそのデータブロックに割り当てられているディスクキ
ャッシュブロックがあるか否かをプライオリティテーブ
ル１１により管理されているキャッシュブロックヘッダ
群１４を参照して探索する。

すでにそのデータフ゛口７りに割り当てられているディ
スクキャッシュブロックがあると判断した場合には、磁
気ディスクキャンシュブロック制御手段６は磁気ディス
クキ中ンシェ制御手段５およびバッファキャッシュ制御
手段３（磁気ディスクキャッシュ制御手段５を介して）
にそのディスクキャッシュブロックに対応するキャッシ
ュブロックヘッダへのポインタを渡す。

まだそのデータブロックに割り当てられているディスク
キャッシュブロックがないと判断した場合には、磁気デ
ィスクキャッシュブロック制御手段６はキャツシュプロ
７クブライオリテイ制御手段７の制御によりプライオリ
ティテーブル１１を参照して磁気ディスクキャッシュメ
モリ１７上の最もプライオリティの低いディスクキャッ
シュブロックに対応するキャッシュブロックヘッダへの
ポインタを磁気ディスクキャッシュ制御手段５およびバ
ッファキャッシュ制御手段３（Ｍ１気ディスクキャッシ
ュ制御手段５を介して）に渡す。

磁気ディスクキャッシュメモリ１７上のディスクキャッ
シュブロックのプライオリティは、キャッシュブロック
プライオリティ制御手段７によって制御されており、使
用頻度の高いディスクキャッシュブロックはプライオリ
ティが高くなり使用頻度の低いディスクキャッシュブロ
ックはプライオリティが低くなるように制御されている
。

キャッシュフ゛ロンクヘッダへのポインタを受は取った
バッファキャッシュ制御手段３は、そのキャッシュブロ
ックヘッダに対応するディスクキャッシュブロックおよ
び上述したようにハツシュテーブル制御手段８から受は
取ったバッファヘッダに対応するバッファキャッシュブ
ロックを使用して・バフファキャソシュメモリ１６と磁
気ディスクキャンシュメモリ１７との−のデータブロッ
クの転送を制御する。

また、キャッシュブロックヘッダへのポインタを受は取
った磁気ディスクキャッシュ制御手段５は、そのキャッ
シュブロックヘッダに対応するディスクキャッシュブロ
ックを使用して、磁気ディスクキャッシュメモリ１７と
磁気ディスク装置１８との間のデータブロックの転送（
磁気ディスクキャッシュメモリ１７から磁気ディスク装
置１８への非同期な書き込みおよび磁気ディスク装置［
１８から磁気ディスクキャンシュメモリ１７への読み出
し）を制御する（Ｗａ気ディスク装置制御手段１０によ
る制御を用いて行う）。

続いて、ファイル制御手段１の制御によって、あるファ
イルが削除された場合の動作について説明する。

この場合には、そのファイルに使用されていたデータブ
ロックには転送要求が起こらないために、上述のような
手順によってフリーバッファ制御手段４やキャッシュブ
ロックプライオリティ制御手段７を呼び出すことはでき
ない。

そこで、ファイル制御手段１は、ファイル管理情報伝達
手段２を介して、フリーバッファ制御手段４およびキャ
ッシュブロックプライオリティ制御手段７に対し、その
ファイルの削除に係る通知（削除されたファイルに使用
されていたデータブロックのブロック番号等）を提供す
る。

この通知を受けたフリーバッファ制御手段４は、そのデ
ータブロックに割り当てられているバッファキャッシュ
ブロックがある場合には（ここでは、第２図（ａ）中の
バッファヘッダＦに対応するパフファキャッシュフ゛ロ
ックが該当するものとする）、そのバッファキャッシュ
ブロックのバッファヘッダＦをフリーリスト１２０に接
続しく第２図（ｂ）参照）、そのバッファキャッシュブ
ロックをフリーな状態のバッファキャッシュブロックと
して他のデータブロックに割り当てることができるよう
にする。

上述の通知を受けたキャッシュブロックプライオリティ
制御手段７は、そのデータブロックに割り当てられてい
るディスクキャンシュフ゛ロンクがある場合には（ここ
では、第３図（ａ）中のキャッシュブロックヘッダＣ′
に対応するディスクキャッシュフロックが８亥当するも
のとする）、そのディスクキャッシュブロックのキャッ
シュブロックヘッダＣ′のプライオリティを最低にしく
第３図（ｂ）参照、キャンンユブロックヘッダＣ′は最
低のプライオリティのキャッシュブロックヘッダの接続
の先頭に挿入され、キャッシュブロックヘッダＣ′に対
応するディスクキャッシュブロックはキャッシュブロッ
クヘッダＡ′に対応するディスクキャッシュブロックよ
りも先に他のデータブロックに割り当てられる）、その
ディスクキャッシュブロックをすぐに他のデータブロッ
クに割り当てることができるようにする。

〔発明の効果〕

以上説明したように本発明は、ファイルの削除によって
不要となったデータブロックに割り当てられていたバッ
ファキャッシュブロックおよびディスクキャッシュブロ
ックをなるべく早く他のデータブロックに割り当てるた
めのキャッシュ制御を行うことにより、不要となったデ
ータブロックがまだバッファキャッシュメモリや磁気デ
ィスクキャッシュメモリ上に残っているうちに有効なデ
ータブロックがバッファキャッシュメモリや磁気ディス
クキャッシュメモリから追い出されてしまうという事態
を防ぐことができ、キャッシュヒント率を向上すること
ができ、データ入出力時間を短縮することができるとい
う効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例の構成を示すブロック図、 第２図（ａ）および（ｂ）は第１図中のハフシュテーブ
ルおよびフリーリストによるバッファヘッダ群の管理の
態様を説明するための図、第３図（ａ）および（ｂ）は
第１図中のプライオリティテーブルによるキャッシュブ
ロックヘッダ群の管理の態様を説明するための図である
。 図において、 １・・・ファイル制御手段、 ２・・・ファイル管理情報伝達手段、 ３・・・バッファキャッシュ制御手段、４・・・フリー
バッファ制御手段、 ５・・・磁気ディスクキャッシュ制御手段、６・・・磁
気ディスクキャッシュブロック制御手段、 ７・・・キャッシュブロックブライオリティ制御手段、 ８・・・ハツシュテーブル制御手段、 ９・・・ファイルブロック制御手段、 １０・・磁気ディスク装置制御手段、 １１・・プライオリティテーブル、 １２・・ハフシュテーブル、 １３・・バッファヘッダ群、 １４・・キャッシュブロックヘッダ群、１５・・利用者
プログラムメモリ空間、１６・・バッファキャッシュメ
モリ、 １７・・磁気ディスクキャッシュメモリ、１８・・磁気
ディスク装置、 １２０・フリーリストである。 第２図（Ｑ） 第２図（ｂ）

Claims (1)

1. 【特許請求の範囲】 磁気ディスク装置上のファイルの作成および削除等の管
   理制御を行うファイル制御手段と、このファイル制御手
   段により管理制御が行われるファイルとそのファイルに
   使用されるデータブロックとの対応を管理し利用者プロ
   グラムメモリ空間とバッファキャッシュメモリとの間の
   データブロックの転送の制御を行うファイルブロック制
   御手段と、 データブロックの転送の際に未使用のバッファキャッシ
   ュブロックを確保し、ファイルの削除に係る通知を受け
   た場合にそのファイルに使用されていたデータブロック
   に割り当てられていたバッファキャッシュブロックのバ
   ッファヘッダをフリーリストに接続するフリーバッファ
   制御手段と、ハッシュテーブル制御手段および前記フリ
   ーバッファ制御手段による制御に基づきデータブロック
   の転送に使用すべきバッファキャッシュブロックを選択
   して前記ファイルブロック制御手段に提供し、バッファ
   キャッシュメモリと磁気ディスクキャッシュメモリとの
   間のデータブロックの転送の制御を行うバッファキャッ
   シュ制御手段と、プライオリティテーブルにおいて管理
   されるディスクキャッシュブロックのプライオリティを
   制御し、ファイルの削除に係る通知を受けた場合にその
   ファイルに使用されていたデータブロックに割り当てら
   れていたディスクキャッシュブロックのプライオリティ
   を最も低くする制御を行うキャッシュブロックプライオ
   リティ制御手段と、磁気ディスクキャッシュブロック制
   御手段および前記キャッシュブロックプライオリティ制
   御手段による制御に基づきデータブロックの転送に使用
   すべきディスクキャッシュブロックを選択して前記バッ
   ファキャッシュ制御手段に提供し、磁気ディスク装置制
   御手段を用いて磁気ディスクキャッシュメモリと磁気デ
   ィスク装置との間のデータブロックの転送の制御を行う
   磁気ディスクキャッシュ制御手段と、 前記ファイル制御手段によりファイルが削除された場合
   にそのファイルの削除に係る通知を前記フリーバッファ
   制御手段および前記キャッシュブロックプライオリティ
   制御手段に提供するファイル管理情報伝達手段と を有することを特徴とするキャッシュ制御方式。