JPS62108342A - デイスクキヤツシユ制御方式 - Google Patents
デイスクキヤツシユ制御方式Info
- Publication number
- JPS62108342A JPS62108342A JP60248517A JP24851785A JPS62108342A JP S62108342 A JPS62108342 A JP S62108342A JP 60248517 A JP60248517 A JP 60248517A JP 24851785 A JP24851785 A JP 24851785A JP S62108342 A JPS62108342 A JP S62108342A
- Authority
- JP
- Japan
- Prior art keywords
- link
- lru
- data
- hit
- hash
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 claims description 7
- 238000013500 data storage Methods 0.000 abstract description 9
- 238000007726 management method Methods 0.000 description 7
- 238000010586 diagram Methods 0.000 description 3
Landscapes
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔概要〕
ディスクキャッシュ制御方式において、キャッシュメモ
リに格納されている各データを検索するためのハツシュ
テーブルと、このハツシュテーブルに連結されたハツシ
ュリンクと、キャッシュメモリに格納した各データのア
クセス頻度に関連づけて順次連結したＬＲＵリンクとを
備え、ハツシュテーブルおよびハツシュリンクを用いて
ヒツト／ミスを検索し、この結果に対応したＬＲＵリン
クをＬＲＬＩリンク群の先頭に連結するようにしている
。
リに格納されている各データを検索するためのハツシュ
テーブルと、このハツシュテーブルに連結されたハツシ
ュリンクと、キャッシュメモリに格納した各データのア
クセス頻度に関連づけて順次連結したＬＲＵリンクとを
備え、ハツシュテーブルおよびハツシュリンクを用いて
ヒツト／ミスを検索し、この結果に対応したＬＲＵリン
クをＬＲＬＩリンク群の先頭に連結するようにしている
。
本発明は、リンクを用いてキャッシュメモリを迅速に検
索し得るよう構成したディスクキャッシュ制御方式に関
するものである。
索し得るよう構成したディスクキャッシュ制御方式に関
するものである。
〔従来の技術と発明が解決しようとする問題点〕従来の
ディスクキャッシュ装置は、ミスした場合に１例えばア
クセス頻度の最も低いブロックに格納されていたデータ
をすて、新たなデータを当該すてたブロックに格納する
ようにしている。このアクセス頻度を管理（ＬＲＵ管理
）するために２キヤツシユメモリの各ブロックに対して
夫々度数管理テーブルを設け１例えばヒツトしたブロッ
クに対して＋１．それ以外の他のブロックに対して−１
を行って夫々のブロックの度数管理を行っていた。この
ため１アクセス頻度を管理するために。
ディスクキャッシュ装置は、ミスした場合に１例えばア
クセス頻度の最も低いブロックに格納されていたデータ
をすて、新たなデータを当該すてたブロックに格納する
ようにしている。このアクセス頻度を管理（ＬＲＵ管理
）するために２キヤツシユメモリの各ブロックに対して
夫々度数管理テーブルを設け１例えばヒツトしたブロッ
クに対して＋１．それ以外の他のブロックに対して−１
を行って夫々のブロックの度数管理を行っていた。この
ため１アクセス頻度を管理するために。
ヒットした毎（ミスした毎）に度数管理テーブルの全て
のブロックに対して度数を加算あるいは減算する必要が
あり１度数管理に多くの時間が必要となってしまうとい
う問題点があった。特に、１チツプＣＰＵを当該度数管
理に使用した場合には。
のブロックに対して度数を加算あるいは減算する必要が
あり１度数管理に多くの時間が必要となってしまうとい
う問題点があった。特に、１チツプＣＰＵを当該度数管
理に使用した場合には。
当該１チツプＣＰＵの処理速度が遅いことから。
度数管理のために他の処理が一層遅くなり、迅速にキャ
ノシェメそりをアクセスし難くなってしまうという問題
点があった。
ノシェメそりをアクセスし難くなってしまうという問題
点があった。
本発明は、前記問題点を解決するために、アクセス要求
のあったデータがキャッシュメモリに存在するか否かを
検索するのにハツシュテーブルおよびハツシュリンクを
使用する構成を採用し、かつアクセス頻度を管理するの
に、ＬＲＵリンクを使用する構成を採用することにより
、迅速にキャッシュメモリをアクセスし得るようにして
いる。
のあったデータがキャッシュメモリに存在するか否かを
検索するのにハツシュテーブルおよびハツシュリンクを
使用する構成を採用し、かつアクセス頻度を管理するの
に、ＬＲＵリンクを使用する構成を採用することにより
、迅速にキャッシュメモリをアクセスし得るようにして
いる。
第１図に示す本発明の１実施例構成図を用いて問題点を
解決するための手段を説明する。
解決するための手段を説明する。
第１図において、ｌチップＣＰＵ１は、プログラムを内
蔵した処理装置である。
蔵した処理装置である。
ヒツト／ミス検索手段３は、計算して算出したハツシュ
番号に対応するハツシュテーブル６中に格納されている
ポインタによって、リンクされるハツシュリンク７を検
索してアクセス要求のあったデータが、キャッシュメモ
リ５中のデータ格納域９に格納されている（ヒット）か
否か（ミス）を検索するものである。
番号に対応するハツシュテーブル６中に格納されている
ポインタによって、リンクされるハツシュリンク７を検
索してアクセス要求のあったデータが、キャッシュメモ
リ５中のデータ格納域９に格納されている（ヒット）か
否か（ミス）を検索するものである。
ＬＲＵリンク更新手段４は、ヒツトした場合に当該ヒツ
トしたデータを管理するＬＲＵリンクを先頭部分に連結
し、ミスした場合に最後尾のＬＲＵリンクをはずし、こ
のはずしたＬＲＵリンクを先頭部分に連結するものであ
る。
トしたデータを管理するＬＲＵリンクを先頭部分に連結
し、ミスした場合に最後尾のＬＲＵリンクをはずし、こ
のはずしたＬＲＵリンクを先頭部分に連結するものであ
る。
キャッシュメモリ５は、ハツシュテーブル６゜ハツシュ
リンク？、ＬＲＵリンク８およびデータ格納域９から構
成されている、ハッシュテーブル６およびハノソユリン
ク７は、後述するように。
リンク？、ＬＲＵリンク８およびデータ格納域９から構
成されている、ハッシュテーブル６およびハノソユリン
ク７は、後述するように。
データ格納域９にアクセス要求のあったデータが格納さ
れているか否かを迅速に検索するために準備されたもの
である。
れているか否かを迅速に検索するために準備されたもの
である。
ＥＣＣデバイス１０は、アクセスしたデータの誤りをチ
ェックするものである。
ェックするものである。
ＨＤコントローラ１１は、ディスク装置１２を制御する
ものである。
ものである。
制御部２は、各種制御を行うものである。
Ｃ作用〕
第１図を用いて説明した構成を採用し、ホスト１３から
アクセス要求がｌチップＣＰＵ１に通知された場合、ヒ
ツト／ミス検索手段３は、当該アクセス要求のあったデ
ータが、キャッシュメモリ５内のデータ格納域９に格納
されているが否がを検索する。この検索は、当該アクセ
ス要求のあったデータに対してハツシュ番号を計算し、
この計算したハ・ノシュ番号に対応するハツシュテーブ
ル６に格納されているポインタを読み出す。そして。
アクセス要求がｌチップＣＰＵ１に通知された場合、ヒ
ツト／ミス検索手段３は、当該アクセス要求のあったデ
ータが、キャッシュメモリ５内のデータ格納域９に格納
されているが否がを検索する。この検索は、当該アクセ
ス要求のあったデータに対してハツシュ番号を計算し、
この計算したハ・ノシュ番号に対応するハツシュテーブ
ル６に格納されているポインタを読み出す。そして。
この読み出したポインタによってリンクづけられている
ハツシュリンク７を順次検索し、アクセス要求のあった
データがデータ格納域９に格納されているか否かを検索
することによって行う。この検索の結果、アクセス要求
のあったデータが格納されていたと判明した場合（ヒッ
トした場合）には、当該検索したハツシュリンクに関連
づけて格納しであるアドレスを読み出し、このアドレス
に格納されているデータを読み出してホスト１３に転送
すると共に、当該検索したハツシュリンクに関連づけら
れているＬＲＵリンクをＬＲＵリンク群からはずし、先
頭に連結する。一方、格納されていなかったと判明した
場合（ミスした場合）には、ディスク装置１２からアク
セス要求のあったデータを読み出してホスト１３に転送
すると共に。
ハツシュリンク７を順次検索し、アクセス要求のあった
データがデータ格納域９に格納されているか否かを検索
することによって行う。この検索の結果、アクセス要求
のあったデータが格納されていたと判明した場合（ヒッ
トした場合）には、当該検索したハツシュリンクに関連
づけて格納しであるアドレスを読み出し、このアドレス
に格納されているデータを読み出してホスト１３に転送
すると共に、当該検索したハツシュリンクに関連づけら
れているＬＲＵリンクをＬＲＵリンク群からはずし、先
頭に連結する。一方、格納されていなかったと判明した
場合（ミスした場合）には、ディスク装置１２からアク
セス要求のあったデータを読み出してホスト１３に転送
すると共に。
最後尾のＬＲＵリンクをＬＲＵリンク群からはずし、こ
のはずしたＬＲＵリンクによってポイントされるデータ
格納域９に当該データを格納する。
のはずしたＬＲＵリンクによってポイントされるデータ
格納域９に当該データを格納する。
そして、このはずしたＬＲＵリンクを先頭に連結する。
ＬＲＵリンクをはずしたり、連結したりすることは、Ｌ
ＲＵリンク更新手段４が行う。
ＲＵリンク更新手段４が行う。
以上説明したように、ヒツト／ミスを検索するために、
ハツシュテーブル６およびハツシュリンク７を設け、か
つアクセス頻度を管理するために。
ハツシュテーブル６およびハツシュリンク７を設け、か
つアクセス頻度を管理するために。
ＬＲＵリンク８を設けているため、迅速にヒツト／ミス
の検索を行い、かつＬＲＵ管理を行うことができる。
の検索を行い、かつＬＲＵ管理を行うことができる。
第２図を用いて第１図図示本発明の１実施例構成図を説
明する。
明する。
第２図図中■は、ハツシュテーブル６の番号を求める状
態を示す。
態を示す。
図中■は、ハツシュリンク７を検索する状態を示す。こ
れは９図中■で求めたハツシュテーブル６の番号に対応
する位置に格納されているポインタによってリンクづけ
されているハツシュリンク７を順次検索して、アクセス
要求のあったデータが格納されているハツシュリンク７
を見つけることを意味している。
れは９図中■で求めたハツシュテーブル６の番号に対応
する位置に格納されているポインタによってリンクづけ
されているハツシュリンク７を順次検索して、アクセス
要求のあったデータが格納されているハツシュリンク７
を見つけることを意味している。
図中■は、ヒツト／ミスのいずれであるかを判別する状
態を示す。これは２図中■で検索した結果がヒツト／ミ
スのいずれであるかを判別することを意味している。ヒ
ットした場合には２図中■でＬＲＵリンクを更新し、終
了する。ミスした場合には１図中■以下を実行する。以
上説明した図中■ないし■の手順は、ヒツト／ミス検索
手段３が実行する。
態を示す。これは２図中■で検索した結果がヒツト／ミ
スのいずれであるかを判別することを意味している。ヒ
ットした場合には２図中■でＬＲＵリンクを更新し、終
了する。ミスした場合には１図中■以下を実行する。以
上説明した図中■ないし■の手順は、ヒツト／ミス検索
手段３が実行する。
図中■は、フリーエリアを獲得する状態を示す。
これは３図中■でミスしたので、最後尾のＬＲＵリンク
によってポイントされるキャッシュメモリ５内の領域を
フリーエリアとして獲得することを意味している。
によってポイントされるキャッシュメモリ５内の領域を
フリーエリアとして獲得することを意味している。
図中■は、ディスク装置１２からアクセス要求のあった
データをアクセスする状態を示す。そして、このアクセ
スした（読み出した）データをホスト１３に転送すると
共に、前記フリーエリアに書き込んでおく。
データをアクセスする状態を示す。そして、このアクセ
スした（読み出した）データをホスト１３に転送すると
共に、前記フリーエリアに書き込んでおく。
図中■は、ハツシュリンク７を更新する状態を示す。
図中■は、ＬＲＵリンク８を更新する壮ＯＥを禾す。こ
れは、既述したように、ヒツトした場合には、当該ヒツ
トしたＬ ＲＵ ＩＪンクをＬ ＲＵ ＩＪンク群から
はずし、先頭に連結する。ミスした場合には、最後尾の
ＬＲＵリンクをＬＲＵリンク群からはずし、先頭に連結
する。この際、この最後尾のＬＲＵリンクによってポイ
ントされるキャッシュメモリ５中にミスしたデータを書
き込んでお（。
れは、既述したように、ヒツトした場合には、当該ヒツ
トしたＬ ＲＵ ＩＪンクをＬ ＲＵ ＩＪンク群から
はずし、先頭に連結する。ミスした場合には、最後尾の
ＬＲＵリンクをＬＲＵリンク群からはずし、先頭に連結
する。この際、この最後尾のＬＲＵリンクによってポイ
ントされるキャッシュメモリ５中にミスしたデータを書
き込んでお（。
以上説明した手順によって、ハツシュテーブル６および
ハツシュリンク７を用いてヒツト／ミス ・を迅速に
検索することができると共に、該当するＬＲＵリンクを
ＬＲＵリンク群の先頭に連結することにより、迅速にア
クセス頻度を管理することができる。
ハツシュリンク７を用いてヒツト／ミス ・を迅速に
検索することができると共に、該当するＬＲＵリンクを
ＬＲＵリンク群の先頭に連結することにより、迅速にア
クセス頻度を管理することができる。
第３図（イ）はディスク装置の各ブロック（例えば各セ
クタ）毎にデータを管理するために卓備した情報例を示
し、第３図（ロ）はハツシュテーブル６およびハツシュ
リンク７の構成例を示す。
クタ）毎にデータを管理するために卓備した情報例を示
し、第３図（ロ）はハツシュテーブル６およびハツシュ
リンク７の構成例を示す。
第３図（ロ）において、左端に示すハツシュテーブル６
中の各位置は、計算して求めたハツシュ番号によって例
えば上から順にポイントされるものである。図中黒い丸
を用いてポイントされた位置に格納されているポインタ
によって、ハフシュリンク７が図示のように順次連結さ
れている。これらのハ・ノシュリンク７を順次検索する
ことにより、アクセス要求のあったデータがキャッシュ
メモリ５中に格納されているか否かが検索される。
中の各位置は、計算して求めたハツシュ番号によって例
えば上から順にポイントされるものである。図中黒い丸
を用いてポイントされた位置に格納されているポインタ
によって、ハフシュリンク７が図示のように順次連結さ
れている。これらのハ・ノシュリンク７を順次検索する
ことにより、アクセス要求のあったデータがキャッシュ
メモリ５中に格納されているか否かが検索される。
第４図（イ）はＬＲＵリンク構成例を示し、第４図（ロ
）はミスした場合のＬＲＵリンク更新例を示す。
）はミスした場合のＬＲＵリンク更新例を示す。
第４図（イ）において、ＬＲＵリンクの先頭部のものを
トップリンクと言い、ＬＲＵリンクの最後尾のものをボ
トムリンクと言う。両者ともにここでは固定である。こ
のため、当該両者によって直接に夫々ポイントされてい
るり、ＲＵリンク（Ｂ）。
トップリンクと言い、ＬＲＵリンクの最後尾のものをボ
トムリンクと言う。両者ともにここでは固定である。こ
のため、当該両者によって直接に夫々ポイントされてい
るり、ＲＵリンク（Ｂ）。
ＬＲＵリンク（Ｄ）に格納されているポインタによって
、夫々ポイントされるキャッシュメモリ５内に格納され
ているデータが、夫々アクセス頻度の最も大きいもの、
アクセス頻度の最も小さいものとなる。
、夫々ポイントされるキャッシュメモリ５内に格納され
ているデータが、夫々アクセス頻度の最も大きいもの、
アクセス頻度の最も小さいものとなる。
第４図（ロ）は、ミスした場合のＬＲＵリンクの更新例
を示す。この更新例は、最後尾のＬＲＵリンク（Ｄ）が
はずされ、かつ新たな情報がセントされた当該ＬＲＵリ
ンク（Ｄ′）がトップリンクとＬＲＵリンク（Ｂ）
との間に挿入されている。
を示す。この更新例は、最後尾のＬＲＵリンク（Ｄ）が
はずされ、かつ新たな情報がセントされた当該ＬＲＵリ
ンク（Ｄ′）がトップリンクとＬＲＵリンク（Ｂ）
との間に挿入されている。
以上ミスした場合について説明したけれども。
ヒットした場合にも、同様に９ ヒツトしたＬＲＵリン
クをはずし、先頭に挿入すればよい。
クをはずし、先頭に挿入すればよい。
以上説明したように３本発明によれば、ハツシュテーブ
ルおよびハツシュリンクを検索してヒツト／ミスを判別
すると共に、、ＬＲ［Ｊリンクによってアクセス頻度を
管理するよう制御しているため。
ルおよびハツシュリンクを検索してヒツト／ミスを判別
すると共に、、ＬＲ［Ｊリンクによってアクセス頻度を
管理するよう制御しているため。
迅速にキャッシュメモリをアクセスすることが可能とな
る。
る。
第１図は本発明の１実施例構成図、第２図は本発明の詳
細な説明するフローチャート、第３図はハツシュリンク
構成例、第４図はＬＲＵリンク構成および更新例を示す
。 図中、１はｌチップＣＰＵ、２は制御部、３はヒツト／
ミス検索手段、４はＬＲＵリンク更新手段、５はキャッ
シュメモリ、６はハツシュテーブル、７はハツシュリン
ク、８はＬＲＵリンク、９はデータ格納域、１０はＥＣ
Ｃデバイス、１１はＨＤコントローラ、１２はディスク
装置、１３はホストを表す。 特許出願人 アルプス電気株式会社 代理人弁理士 森１）寛（外３名） 条殉５朗５１カイ峯Σ４９しり胴ろフ叶ケヤート躬 ２
ｍ
細な説明するフローチャート、第３図はハツシュリンク
構成例、第４図はＬＲＵリンク構成および更新例を示す
。 図中、１はｌチップＣＰＵ、２は制御部、３はヒツト／
ミス検索手段、４はＬＲＵリンク更新手段、５はキャッ
シュメモリ、６はハツシュテーブル、７はハツシュリン
ク、８はＬＲＵリンク、９はデータ格納域、１０はＥＣ
Ｃデバイス、１１はＨＤコントローラ、１２はディスク
装置、１３はホストを表す。 特許出願人 アルプス電気株式会社 代理人弁理士 森１）寛（外３名） 条殉５朗５１カイ峯Σ４９しり胴ろフ叶ケヤート躬 ２
ｍ
Claims (1)
- 【特許請求の範囲】 ヒットした場合にキャッシュメモリをアクセスし、ミス
した場合にディスク装置から読み出したデータをキャッ
シュメモリに格納するよう制御するディスクキャッシュ
制御方式において、 キャッシュメモリに格納されている各データを検索する
ためのハッシュテーブルと、 このハッシュテーブルに連結されたハッシュリンクと、 キャッシュメモリに格納した各データのアクセス頻度に
関連づけて順次連結したＬＲＵリンクと、ハッシュテー
ブルの番号を求め、この番号にリンクされているハッシ
ュリンクを検索してヒット／ミスを検索するヒット／ミ
ス検索手段と、このヒット／ミス検索手段によって検索
した結果がヒットした場合にこのヒットしたデータを管
理するＬＲＵリンクをＬＲＵリンク群の先頭に連結し、
ミスした場合に最後尾のＬＲＵリンクをＬＲＵリンク群
からはずし、当該ミスしたデータを管理する新たな情報
がセットされたＬＲＵリンクをＬＲＵリンク群の先頭に
連結するＬＲＵリンク更新手段とを備え、 ハッシュテーブルおよびハッシュリンクを用いてヒット
／ミスを検索し、この結果に対応したＬＲＵリンクをＬ
ＲＵリンク群の先頭に連結するよう構成したことを特徴
とするディスクキャッシュ制御方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60248517A JPS62108342A (ja) | 1985-11-06 | 1985-11-06 | デイスクキヤツシユ制御方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP60248517A JPS62108342A (ja) | 1985-11-06 | 1985-11-06 | デイスクキヤツシユ制御方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS62108342A true JPS62108342A (ja) | 1987-05-19 |
Family
ID=17179362
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP60248517A Pending JPS62108342A (ja) | 1985-11-06 | 1985-11-06 | デイスクキヤツシユ制御方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS62108342A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008515112A (ja) * | 2004-10-01 | 2008-05-08 | イーエムシー コーポレイション | 仮想順序付け書き込み |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5696337A (en) * | 1979-12-28 | 1981-08-04 | Fujitsu Ltd | Resource control system |
| JPS57113477A (en) * | 1981-01-05 | 1982-07-14 | Toshiba Corp | Table searching device for cash buffer |
-
1985
- 1985-11-06 JP JP60248517A patent/JPS62108342A/ja active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5696337A (en) * | 1979-12-28 | 1981-08-04 | Fujitsu Ltd | Resource control system |
| JPS57113477A (en) * | 1981-01-05 | 1982-07-14 | Toshiba Corp | Table searching device for cash buffer |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008515112A (ja) * | 2004-10-01 | 2008-05-08 | イーエムシー コーポレイション | 仮想順序付け書き込み |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4593354A (en) | Disk cache system | |
| US9311014B2 (en) | Storage system and methods of mapping addresses of snapshot families | |
| US6216199B1 (en) | Hardware mechanism for managing cache structures in a data storage system | |
| US4575827A (en) | Self-archiving data recording | |
| CA1180465A (en) | Method and apparatus for limiting data occupancy in a cache | |
| EP0284663B1 (en) | Method of handling disk sector errors in dasd cache | |
| EP0284664B1 (en) | Method of rapidly opening disc files identified by path names | |
| US5586290A (en) | Cache system of external storage device | |
| JPS63186348A (ja) | １回書込み多数回読取記憶媒体の効用を高める装置および方法 | |
| JPS62108342A (ja) | デイスクキヤツシユ制御方式 | |
| US6487632B1 (en) | Emulation technique for variable-length disk system to access data in a fixed-length disk system | |
| JPH044617B2 (ja) | ||
| EP0665499A2 (en) | Hierarchic data storage system | |
| JP3335919B2 (ja) | ディスクキャッシュ制御装置 | |
| JP2854667B2 (ja) | ディスク・キャッシュ制御方式 | |
| JPH0198020A (ja) | 索引管理方式 | |
| JP2854668B2 (ja) | ディスク・キャッシュ制御方式 | |
| JPH02210561A (ja) | ディスクキャッシュの管理方式 | |
| JPH0991195A (ja) | ブロックメモリ管理装置 | |
| JPH04288647A (ja) | キャッシュメモリにおける置き換え制御装置 | |
| JPH04336340A (ja) | ディスクキャッシュアクセス制御方式 | |
| JPH01125639A (ja) | ディスクキャッシュ制御方式 | |
| JPH02197941A (ja) | ディスクキャッシュの制御方式 | |
| JPH0318215B2 (ja) | ||
| JPH0689228A (ja) | キャッシュメモリ制御装置 |