JP2001051892A - キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体 - Google Patents
キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体Info
- Publication number
- JP2001051892A JP2001051892A JP11223996A JP22399699A JP2001051892A JP 2001051892 A JP2001051892 A JP 2001051892A JP 11223996 A JP11223996 A JP 11223996A JP 22399699 A JP22399699 A JP 22399699A JP 2001051892 A JP2001051892 A JP 2001051892A
- Authority
- JP
- Japan
- Prior art keywords
- cache
- level
- virtual
- virtual cache
- performance value
- 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.)
- Granted
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】 （修正有）
【課題】 要求性能を満たすキャッシュ容量を決定する
ために、実際のリクエスト列に基づいて、複数の異なる
容量における性能値を同時に算出すること。 【解決手段】 リクエストされたオブジェクトＡが、キ
ャッシュテーブルに存在しなければ、オブジェクト名、
サイズ、下限ラベル、キャッシュ置換アルゴリズムで決
定される順位の組をキャッシュテーブルに書き込み、存
在すれば、オブジェクトの新たな順位を決定し、キャッ
シュテーブルのオブジェクトの順位を更新し、下限ラベ
ル以上のレベルの仮想キャッシュにおいては、オブジェ
クトＡがヒットしたものとし、下限ラベル未満のレベル
の仮想キャッシュにおいてはヒットしなかったものとし
て性能値を計算し、エンドオブジェクトの中でオブジェ
クトＡの順位以下の最大の順位のものに、対応する仮想
キャッシュのレベルを設定し、オブジェクト追い出し処
理を行い、オブジェクトＡの下限ラベルを設定する。
ために、実際のリクエスト列に基づいて、複数の異なる
容量における性能値を同時に算出すること。 【解決手段】 リクエストされたオブジェクトＡが、キ
ャッシュテーブルに存在しなければ、オブジェクト名、
サイズ、下限ラベル、キャッシュ置換アルゴリズムで決
定される順位の組をキャッシュテーブルに書き込み、存
在すれば、オブジェクトの新たな順位を決定し、キャッ
シュテーブルのオブジェクトの順位を更新し、下限ラベ
ル以上のレベルの仮想キャッシュにおいては、オブジェ
クトＡがヒットしたものとし、下限ラベル未満のレベル
の仮想キャッシュにおいてはヒットしなかったものとし
て性能値を計算し、エンドオブジェクトの中でオブジェ
クトＡの順位以下の最大の順位のものに、対応する仮想
キャッシュのレベルを設定し、オブジェクト追い出し処
理を行い、オブジェクトＡの下限ラベルを設定する。
Description
【０００１】
【発明の属する技術分野】本発明は、キャッシュサーバ
性能値算出方法及び装置及びキャッシュサーバ性能値算
出プログラムを格納した記憶媒体に係り、特に、実際の
リクエスト列に基づいて、様々なキャッシュ容量におけ
る性能値を仮想的に求めることによって、適切なキャッ
シュ容量を設計するためのキャッシュサーバ性能値算出
方法及び装置及びキャッシュサーバ性能値算出プログラ
ムを格納した記憶媒体に関する。
性能値算出方法及び装置及びキャッシュサーバ性能値算
出プログラムを格納した記憶媒体に係り、特に、実際の
リクエスト列に基づいて、様々なキャッシュ容量におけ
る性能値を仮想的に求めることによって、適切なキャッ
シュ容量を設計するためのキャッシュサーバ性能値算出
方法及び装置及びキャッシュサーバ性能値算出プログラ
ムを格納した記憶媒体に関する。
【０００２】
【従来の技術】キャッシュサーバは、リクエストされた
オブジェクトがキャッシュ内に蓄積されている場合は、
当該オブジェクトをクライアントへ転送し、キャッシュ
置換アルゴリズムによって、当該オブジェクトの順位を
変更する。また、リクエストされたオブジェクトがキャ
ッシュ内に蓄積されていない場合は、当該オブジェクト
をオリジンサーバから取得してキャッシュ内に蓄積し、
キャッシュ置換アルゴリズムによって当該オブジェクト
の順位を決定する。その際、リクエストされたオブジェ
クトを蓄積しようとしたとき、キャッシュ容量を越える
場合は、キャッシュされたオブジェクトの中で順位の低
いものから削除することによって空き容量を作り、リク
エストされたオブジェクトをキャッシュ内に蓄積する。
オブジェクトがキャッシュ内に蓄積されている場合は、
当該オブジェクトをクライアントへ転送し、キャッシュ
置換アルゴリズムによって、当該オブジェクトの順位を
変更する。また、リクエストされたオブジェクトがキャ
ッシュ内に蓄積されていない場合は、当該オブジェクト
をオリジンサーバから取得してキャッシュ内に蓄積し、
キャッシュ置換アルゴリズムによって当該オブジェクト
の順位を決定する。その際、リクエストされたオブジェ
クトを蓄積しようとしたとき、キャッシュ容量を越える
場合は、キャッシュされたオブジェクトの中で順位の低
いものから削除することによって空き容量を作り、リク
エストされたオブジェクトをキャッシュ内に蓄積する。
【０００３】このような動作を行うキャッシュサーバの
キャッシュ容量の設計として、従来は、リクエストの発
生間隔に何らかの確率分布を仮定した上で、規定された
性能値の閾値を満たす容量を解析的に求める方法があ
る。
キャッシュ容量の設計として、従来は、リクエストの発
生間隔に何らかの確率分布を仮定した上で、規定された
性能値の閾値を満たす容量を解析的に求める方法があ
る。
【０００４】
【発明が解決しようとする課題】しかしながら、上記の
従来の方法は、仮定する確率分布の妥当性が不明であ
り、確率分布のパラメータをどのように設定すべきか不
明であるため、この方法によって設計された容量が実際
のリクエストに対して適切か否かを判断することができ
ない。従って、実際には少なく見積り過ぎることにより
性能の劣化、もしくは、多く見積り過ぎることによるコ
ストアップが生じうるという問題がある。
従来の方法は、仮定する確率分布の妥当性が不明であ
り、確率分布のパラメータをどのように設定すべきか不
明であるため、この方法によって設計された容量が実際
のリクエストに対して適切か否かを判断することができ
ない。従って、実際には少なく見積り過ぎることにより
性能の劣化、もしくは、多く見積り過ぎることによるコ
ストアップが生じうるという問題がある。
【０００５】本発明は、上記の点に鑑みなされたもの
で、要求性能を満たすキャッシュ容量を決定するため
に、実際のリクエスト列に基づいて、複数の異なる容量
における性能値を同時に算出することが可能なキャッシ
ュサーバ性能値算出方法及び装置及びキャッシュサーバ
性能値算出プログラムを格納した記憶媒体を提供するこ
とを目的とする。
で、要求性能を満たすキャッシュ容量を決定するため
に、実際のリクエスト列に基づいて、複数の異なる容量
における性能値を同時に算出することが可能なキャッシ
ュサーバ性能値算出方法及び装置及びキャッシュサーバ
性能値算出プログラムを格納した記憶媒体を提供するこ
とを目的とする。
【０００６】
【課題を解決するための手段】図１は、本発明の原理を
説明するための図である。本発明（請求項１）は、キャ
ッシュサーバにおいて、リクエストの列に基づいて、仮
想キャッシュ容量を持つ仮想キャッシュに対する性能値
を算出するキャッシュサーバ性能値算出方法において、
リクエストされたオブジェクトＡが、オブジェクト名、
オブジェクトサイズ、オブジェクトをキャッシュする仮
想キャッシュの中で最小のレベルである下限ラベル、及
び順位を記録するキャッシュテーブルに存在するかを判
定し（ステップ１）、存在しなければ、オブジェクト
名、サイズ、下限ラベル、キャッシュ置換アルゴリズム
で決定される順位の組をキャッシュテーブルに書き込み
（ステップ２）、存在すれば、キャッシュ置換アルゴリ
ズムでオブジェクトの新たな順位を決定し、キャッシュ
テーブルのオブジェクトの順位を更新し（ステップ
３）、オブジェクトＡの下限ラベルを読み取り（ステッ
プ４）、下限ラベル以上のレベルの仮想キャッシュにお
いては、オブジェクトＡがヒットしたものとして性能値
を計算し（ステップ５）、下限ラベル未満のレベルの仮
想キャッシュにおいては、オブジェクトＡがヒットしな
かったものとして性能値を計算し（ステップ６）、仮想
キャッシュに蓄積されているオブジェクトの中で最も順
位の低いオブジェクトであるエンドオブジェクトの中で
オブジェクトＡの順位以下の最大の順位のものを、仮想
キャッシュのレベル、エンドオブジェクト、及びその順
位を並べたエンドポインターテーブル上で探し、該エン
ドオブジェクトに対応する仮想キャッシュのレベルを設
定し（ステップ７）、所定のレベルのすべての仮想キャ
ッシュの各々に対して、オブジェクト追い出し処理を行
い（ステップ８）、オブジェクトＡの下限ラベルを設定
する（ステップ９）。
説明するための図である。本発明（請求項１）は、キャ
ッシュサーバにおいて、リクエストの列に基づいて、仮
想キャッシュ容量を持つ仮想キャッシュに対する性能値
を算出するキャッシュサーバ性能値算出方法において、
リクエストされたオブジェクトＡが、オブジェクト名、
オブジェクトサイズ、オブジェクトをキャッシュする仮
想キャッシュの中で最小のレベルである下限ラベル、及
び順位を記録するキャッシュテーブルに存在するかを判
定し（ステップ１）、存在しなければ、オブジェクト
名、サイズ、下限ラベル、キャッシュ置換アルゴリズム
で決定される順位の組をキャッシュテーブルに書き込み
（ステップ２）、存在すれば、キャッシュ置換アルゴリ
ズムでオブジェクトの新たな順位を決定し、キャッシュ
テーブルのオブジェクトの順位を更新し（ステップ
３）、オブジェクトＡの下限ラベルを読み取り（ステッ
プ４）、下限ラベル以上のレベルの仮想キャッシュにお
いては、オブジェクトＡがヒットしたものとして性能値
を計算し（ステップ５）、下限ラベル未満のレベルの仮
想キャッシュにおいては、オブジェクトＡがヒットしな
かったものとして性能値を計算し（ステップ６）、仮想
キャッシュに蓄積されているオブジェクトの中で最も順
位の低いオブジェクトであるエンドオブジェクトの中で
オブジェクトＡの順位以下の最大の順位のものを、仮想
キャッシュのレベル、エンドオブジェクト、及びその順
位を並べたエンドポインターテーブル上で探し、該エン
ドオブジェクトに対応する仮想キャッシュのレベルを設
定し（ステップ７）、所定のレベルのすべての仮想キャ
ッシュの各々に対して、オブジェクト追い出し処理を行
い（ステップ８）、オブジェクトＡの下限ラベルを設定
する（ステップ９）。
【０００７】本発明（請求項２）は、オブジェクト追い
出し処理として、リクエストされたオブジェクトＡを、
あるレベルＫの仮想キャッシュに蓄積しようとした時、
該仮想キャッシュの容量を越える場合には、該レベルＫ
の仮想キャッシュのエンドオブジェクトをエンドポイン
タテーブルで探し、順位の小さいものから順に、該オブ
ジェクトＡを蓄積できる空き容量ができるまで、オブジ
ェクトを該レベルＫの仮想キャッシュから追い出し、追
い出された残りのオブジェクトの中で順位が最も小さい
ものをエンドポインタテーブルのあるレベルＫの仮想キ
ャッシュのエンドオブジェクトとする。
出し処理として、リクエストされたオブジェクトＡを、
あるレベルＫの仮想キャッシュに蓄積しようとした時、
該仮想キャッシュの容量を越える場合には、該レベルＫ
の仮想キャッシュのエンドオブジェクトをエンドポイン
タテーブルで探し、順位の小さいものから順に、該オブ
ジェクトＡを蓄積できる空き容量ができるまで、オブジ
ェクトを該レベルＫの仮想キャッシュから追い出し、追
い出された残りのオブジェクトの中で順位が最も小さい
ものをエンドポインタテーブルのあるレベルＫの仮想キ
ャッシュのエンドオブジェクトとする。
【０００８】図２は、本発明の原理構成図である。本発
明（請求項３）は、キャッシュサーバにおいて、リクエ
ストの列に基づいて、仮想キャッシュ容量を持つ仮想キ
ャッシュに対する性能値を算出するキャッシュサーバ性
能値算出装置であって、オブジェクト名、オブジェクト
サイズ、オブジェクトをキャッシュする仮想キャッシュ
の中で最小のレベルである下限ラベル、及び順位の組と
を記録するキャッシュテーブル１３０と、仮想キャッシ
ュに蓄積されているオブジェクトの中で最も低い順位の
オブジェクトであるエンドオブジェクト、仮想キャッシ
ュのレベル、及びその順位を並べたエンドポインタテー
ブル１４０と、リクエストされたオブジェクトＡが、キ
ャッシュテーブル１３０に存在するかを判定し、存在し
なければ、オブジェクト名、サイズ、下限ラベル、キャ
ッシュ置換アルゴリズムで決定される順位の組をキャッ
シュテーブル１３０に書き込み、存在すれば、キャッシ
ュ置換アルゴリズムでオブジェクトの新たな順位を決定
し、キャッシュテーブルのオブジェクトの順位を更新す
るオブジェクト判定手段１１０と、オブジェクトＡの下
限ラベルを読み取り、下限ラベル以上のレベルの仮想キ
ャッシュにおいては、オブジェクトＡがヒットしたもの
として性能値を計算し、下限ラベル未満のレベルの仮想
キャッシュにおいては、オブジェクトＡがヒットしなか
ったものとして性能値を計算し、仮想キャッシュに蓄積
されているオブジェクトの中で最も順位の低いオブジェ
クトであるエンドオブジェクトの中でオブジェクトＡの
順位以下の最大の順位のものを、エンドポインターテー
ブル１４０上で探し、該エンドオブジェクトに対応する
仮想キャッシュのレベルを設定する性能値計算手段１２
０と、所定のレベルのすべての仮想キャッシュの各々に
対して、オブジェクト追い出し処理を行う追い出し手段
１５０と、オブジェクトＡの下限ラベルを設定するラベ
ル設定手段１６０とを有する。
明（請求項３）は、キャッシュサーバにおいて、リクエ
ストの列に基づいて、仮想キャッシュ容量を持つ仮想キ
ャッシュに対する性能値を算出するキャッシュサーバ性
能値算出装置であって、オブジェクト名、オブジェクト
サイズ、オブジェクトをキャッシュする仮想キャッシュ
の中で最小のレベルである下限ラベル、及び順位の組と
を記録するキャッシュテーブル１３０と、仮想キャッシ
ュに蓄積されているオブジェクトの中で最も低い順位の
オブジェクトであるエンドオブジェクト、仮想キャッシ
ュのレベル、及びその順位を並べたエンドポインタテー
ブル１４０と、リクエストされたオブジェクトＡが、キ
ャッシュテーブル１３０に存在するかを判定し、存在し
なければ、オブジェクト名、サイズ、下限ラベル、キャ
ッシュ置換アルゴリズムで決定される順位の組をキャッ
シュテーブル１３０に書き込み、存在すれば、キャッシ
ュ置換アルゴリズムでオブジェクトの新たな順位を決定
し、キャッシュテーブルのオブジェクトの順位を更新す
るオブジェクト判定手段１１０と、オブジェクトＡの下
限ラベルを読み取り、下限ラベル以上のレベルの仮想キ
ャッシュにおいては、オブジェクトＡがヒットしたもの
として性能値を計算し、下限ラベル未満のレベルの仮想
キャッシュにおいては、オブジェクトＡがヒットしなか
ったものとして性能値を計算し、仮想キャッシュに蓄積
されているオブジェクトの中で最も順位の低いオブジェ
クトであるエンドオブジェクトの中でオブジェクトＡの
順位以下の最大の順位のものを、エンドポインターテー
ブル１４０上で探し、該エンドオブジェクトに対応する
仮想キャッシュのレベルを設定する性能値計算手段１２
０と、所定のレベルのすべての仮想キャッシュの各々に
対して、オブジェクト追い出し処理を行う追い出し手段
１５０と、オブジェクトＡの下限ラベルを設定するラベ
ル設定手段１６０とを有する。
【０００９】本発明（請求項４）は、追い出し手段１５
０において、リクエストされたオブジェクトＡを、ある
レベルＫの仮想キャッシュに蓄積しようとした時、該仮
想キャッシュの容量を越える場合には、該レベルＫの仮
想キャッシュのエンドオブジェクトをエンドポインタテ
ーブルで探し、順位の小さいものから順に、該オブジェ
クトＡを蓄積できる空き容量ができるまで、オブジェク
トを該レベルＫの仮想キャッシュから追い出し、追い出
された残りのオブジェクトの中で順位が最も小さいもの
を該記エンドポインタテーブルのあるレベルＫの仮想キ
ャッシュのエンドオブジェクトとする手段を有する。
０において、リクエストされたオブジェクトＡを、ある
レベルＫの仮想キャッシュに蓄積しようとした時、該仮
想キャッシュの容量を越える場合には、該レベルＫの仮
想キャッシュのエンドオブジェクトをエンドポインタテ
ーブルで探し、順位の小さいものから順に、該オブジェ
クトＡを蓄積できる空き容量ができるまで、オブジェク
トを該レベルＫの仮想キャッシュから追い出し、追い出
された残りのオブジェクトの中で順位が最も小さいもの
を該記エンドポインタテーブルのあるレベルＫの仮想キ
ャッシュのエンドオブジェクトとする手段を有する。
【００１０】本発明（請求項５）は、キャッシュサーバ
において、リクエストの列に基づいて、仮想キャッシュ
容量を持つ仮想キャッシュに対する性能値を算出するキ
ャッシュサーバ性能値算出プログラムを格納した記憶媒
体であって、リクエストされたオブジェクトＡが、オブ
ジェクト名、オブジェクトサイズ、オブジェクトをキャ
ッシュする仮想キャッシュの中で最小のレベルである下
限ラベル、及び順位を記録するキャッシュテーブルに存
在するかを判定するプロセスと、存在しなければ、オブ
ジェクト名、サイズ、下限ラベル、キャッシュ置換アル
ゴリズムで決定される順位の組をキャッシュテーブルに
書き込むプロセスと、存在すれば、キャッシュ置換アル
ゴリズムでオブジェクトの新たな順位を決定し、キャッ
シュテーブルのオブジェクトの順位を更新するプロセス
と、オブジェクトＡの下限ラベルを読み取るプロセス
と、下限ラベル以上のレベルの仮想キャッシュにおいて
は、オブジェクトＡがヒットしたものとして性能値を計
算するプロセスと、下限ラベル未満のレベルの仮想キャ
ッシュにおいては、オブジェクトＡがヒットしなかった
ものとして性能値を計算するプロセスと、仮想キャッシ
ュに蓄積されているオブジェクトの中で最も順位の低い
オブジェクトであるエンドオブジェクトの中でオブジェ
クトＡの順位以下の最大の順位のものを、仮想キャッシ
ュのレベル、エンドオブジェクト、及びその順位を並べ
たエンドポインターテーブル上で探し、該エンドオブジ
ェクトに対応する仮想キャッシュのレベルを設定するプ
ロセスと、所定のレベルのすべての仮想キャッシュの各
々に対して、オブジェクト追い出し処理を行うプロセス
と、オブジェクトＡの下限ラベルを設定するプロセスと
を有する。
において、リクエストの列に基づいて、仮想キャッシュ
容量を持つ仮想キャッシュに対する性能値を算出するキ
ャッシュサーバ性能値算出プログラムを格納した記憶媒
体であって、リクエストされたオブジェクトＡが、オブ
ジェクト名、オブジェクトサイズ、オブジェクトをキャ
ッシュする仮想キャッシュの中で最小のレベルである下
限ラベル、及び順位を記録するキャッシュテーブルに存
在するかを判定するプロセスと、存在しなければ、オブ
ジェクト名、サイズ、下限ラベル、キャッシュ置換アル
ゴリズムで決定される順位の組をキャッシュテーブルに
書き込むプロセスと、存在すれば、キャッシュ置換アル
ゴリズムでオブジェクトの新たな順位を決定し、キャッ
シュテーブルのオブジェクトの順位を更新するプロセス
と、オブジェクトＡの下限ラベルを読み取るプロセス
と、下限ラベル以上のレベルの仮想キャッシュにおいて
は、オブジェクトＡがヒットしたものとして性能値を計
算するプロセスと、下限ラベル未満のレベルの仮想キャ
ッシュにおいては、オブジェクトＡがヒットしなかった
ものとして性能値を計算するプロセスと、仮想キャッシ
ュに蓄積されているオブジェクトの中で最も順位の低い
オブジェクトであるエンドオブジェクトの中でオブジェ
クトＡの順位以下の最大の順位のものを、仮想キャッシ
ュのレベル、エンドオブジェクト、及びその順位を並べ
たエンドポインターテーブル上で探し、該エンドオブジ
ェクトに対応する仮想キャッシュのレベルを設定するプ
ロセスと、所定のレベルのすべての仮想キャッシュの各
々に対して、オブジェクト追い出し処理を行うプロセス
と、オブジェクトＡの下限ラベルを設定するプロセスと
を有する。
【００１１】本発明（請求項６）は、オブジェクト追い
出しプロセスにおいて、リクエストされたオブジェクト
Ａを、あるレベルＫの仮想キャッシュに蓄積しようとし
た時、該仮想キャッシュの容量を越える場合には、該レ
ベルＫの仮想キャッシュのエンドオブジェクトをエンド
ポインタテーブルで探し、順位の小さいものから順に、
該オブジェクトＡを蓄積できる空き容量ができるまで、
オブジェクトを該レベルＫの仮想キャッシュから追い出
すプロセスと、追い出された残りのオブジェクトの中で
順位が最も小さいものをエンドポインタテーブルのある
レベルＫの仮想キャッシュのエンドオブジェクトとする
プロセスとを有する。
出しプロセスにおいて、リクエストされたオブジェクト
Ａを、あるレベルＫの仮想キャッシュに蓄積しようとし
た時、該仮想キャッシュの容量を越える場合には、該レ
ベルＫの仮想キャッシュのエンドオブジェクトをエンド
ポインタテーブルで探し、順位の小さいものから順に、
該オブジェクトＡを蓄積できる空き容量ができるまで、
オブジェクトを該レベルＫの仮想キャッシュから追い出
すプロセスと、追い出された残りのオブジェクトの中で
順位が最も小さいものをエンドポインタテーブルのある
レベルＫの仮想キャッシュのエンドオブジェクトとする
プロセスとを有する。
【００１２】上記のように、本発明では、複数の仮想キ
ャッシュを用いることにより、複数の異なるキャッシュ
容量における性能値を同時に計算することが可能とな
る。次に、オブジェクトに対して下限ラベルを定義する
ことにより、そのオブジェクトをキャッシュしていない
仮想キャッシュの集合（当該オブジェクトの下限ラベル
より小さいレベルを持つすべての仮想キャッシュ）が把
握できる。従って、リクエストされたオブジェクトがヒ
ットし仮想キャッシュの集合と、ヒットしなかった仮想
キャッシュの集合が、下限ラベルを参照することによ
り、容易に分離できるため、各仮想キャッシュ毎にヒッ
トしたかしなかったかの判定を行う必要がなく、より少
ない計算で複数の異なるキャッシュ容量における性能値
を計算することが可能となる。
ャッシュを用いることにより、複数の異なるキャッシュ
容量における性能値を同時に計算することが可能とな
る。次に、オブジェクトに対して下限ラベルを定義する
ことにより、そのオブジェクトをキャッシュしていない
仮想キャッシュの集合（当該オブジェクトの下限ラベル
より小さいレベルを持つすべての仮想キャッシュ）が把
握できる。従って、リクエストされたオブジェクトがヒ
ットし仮想キャッシュの集合と、ヒットしなかった仮想
キャッシュの集合が、下限ラベルを参照することによ
り、容易に分離できるため、各仮想キャッシュ毎にヒッ
トしたかしなかったかの判定を行う必要がなく、より少
ない計算で複数の異なるキャッシュ容量における性能値
を計算することが可能となる。
【００１３】また、リクエストされたオブジェクトの順
位以下の順位を持つエンドオブジェクトの中で、最大の
順位のものに対応する仮想キャッシュのレベルをＬB 、
リクエストされたオブジェクトの下限ラベルをＬとし
て、ＬB からＬ−１のレベルの全ての仮想キャッシュの
各々に対してのみ、オブジェクト追い出し処理を行うこ
とによって、オブジェクト追い出し処理を必要最低限に
抑えることができる。
位以下の順位を持つエンドオブジェクトの中で、最大の
順位のものに対応する仮想キャッシュのレベルをＬB 、
リクエストされたオブジェクトの下限ラベルをＬとし
て、ＬB からＬ−１のレベルの全ての仮想キャッシュの
各々に対してのみ、オブジェクト追い出し処理を行うこ
とによって、オブジェクト追い出し処理を必要最低限に
抑えることができる。
【００１４】更に、エンドポインタテーブルを用いるこ
とにより、各仮想キャッシュにおいて最小の順位のオブ
ジェクトをすぐに参照することができるため、新たなオ
ブジェクトをキャッシュする際に空き容量を作るために
順位の小さいものを新たに探索する必要がなく、オブジ
ェクトの追い出し処理を高速に行うことが可能となる。
とにより、各仮想キャッシュにおいて最小の順位のオブ
ジェクトをすぐに参照することができるため、新たなオ
ブジェクトをキャッシュする際に空き容量を作るために
順位の小さいものを新たに探索する必要がなく、オブジ
ェクトの追い出し処理を高速に行うことが可能となる。
【００１５】このようにして、実際のリクエスト列に基
づいて、複数の異なる容量における性能値を、少ない手
間で同時に算出することが可能となる。
づいて、複数の異なる容量における性能値を、少ない手
間で同時に算出することが可能となる。
【００１６】
【発明の実施の形態】図３は、本発明のキャッシュサー
バ性能値算出装置の接続構成を示し、図４は、本発明の
キャッシュサー性能値算出装置の構成を示す。キャッシ
ュサーバ性能値算出装置１００は、サーバ２００に接続
され、当該サーバ２００からリクエスト列が入力される
と、キャッシュサーバ性能値を算出し、入力されたリク
エスト列に対応する性能値を出力する。
バ性能値算出装置の接続構成を示し、図４は、本発明の
キャッシュサー性能値算出装置の構成を示す。キャッシ
ュサーバ性能値算出装置１００は、サーバ２００に接続
され、当該サーバ２００からリクエスト列が入力される
と、キャッシュサーバ性能値を算出し、入力されたリク
エスト列に対応する性能値を出力する。
【００１７】キャッシュサーバ性能値算出装置１００
は、オブジェクト判定部１１０、性能値計算部１２０、
キャッシュテーブル１３０、エンドポインタテーブル１
４０から構成される。キャッシュテーブル１３０は、オ
ブジェクト名、当該オブジェクトサイズ、当該オブジェ
クトをキャッシュする仮想キャッシュの中で最小のレベ
ル（以下、下限ラベルと記す）、及び順位の組を記録し
たテーブルである。
は、オブジェクト判定部１１０、性能値計算部１２０、
キャッシュテーブル１３０、エンドポインタテーブル１
４０から構成される。キャッシュテーブル１３０は、オ
ブジェクト名、当該オブジェクトサイズ、当該オブジェ
クトをキャッシュする仮想キャッシュの中で最小のレベ
ル（以下、下限ラベルと記す）、及び順位の組を記録し
たテーブルである。
【００１８】エンドポインタテーブル１４０は、仮想キ
ャッシュのレベル、当該仮想キャッシュに蓄積されてい
るオブジェクトの中で最も順位の低いもの（以下、エン
ドオブジェクトと記す）、及びその順位を並べたテーブ
ルである。オブジェクト判定部１１０は、リクエストさ
れたオブジェクトＡがキャッシュテーブル１３０にある
か否かを判定し、存在しなければ当該オブジェクト名、
サイズ、下限ラベル、キャッシュ置換アルゴリズムで決
定される順位の組を、キャッシュテーブル１３０に書き
込む。但し、下限ラベルは∞とする。一方、リクエスト
されたオブジェクトＡがキャッシュテーブル１３０に存
在すれば、キャッシュ置換アルゴリズムでその新たな順
位を決定し、キャッシュテーブル１３０のすべてのオブ
ジェクトの順位を更新する。
ャッシュのレベル、当該仮想キャッシュに蓄積されてい
るオブジェクトの中で最も順位の低いもの（以下、エン
ドオブジェクトと記す）、及びその順位を並べたテーブ
ルである。オブジェクト判定部１１０は、リクエストさ
れたオブジェクトＡがキャッシュテーブル１３０にある
か否かを判定し、存在しなければ当該オブジェクト名、
サイズ、下限ラベル、キャッシュ置換アルゴリズムで決
定される順位の組を、キャッシュテーブル１３０に書き
込む。但し、下限ラベルは∞とする。一方、リクエスト
されたオブジェクトＡがキャッシュテーブル１３０に存
在すれば、キャッシュ置換アルゴリズムでその新たな順
位を決定し、キャッシュテーブル１３０のすべてのオブ
ジェクトの順位を更新する。
【００１９】性能値計算部１２０は、性能値を計算する
計算部１２１と、仮想キャッシュに対してオブジェクト
の追い出しを行う追い出し処理部１２２から構成され
る。計算部１２１は、当該オブジェクトＡの下限ラベル
（Ｌとする）を読み取る。この下限ラベルＬ以上のレベ
ルの仮想キャッシュにおいては、オブジェクトＡがヒッ
トしたものとして性能値を計算する。一方、この下限ラ
ベル未満のレベルの仮想キャッシュにおいては、オブジ
ェクトＡがヒットしなかったものとして性能値を計算す
る。そして、オブジェクトＡの順位以下の順位を持つオ
ブジェクトの中で最大の順位のものをエンドポインタテ
ーブル１４０上で探し、そのエンドオブジェクトに対応
する仮想キャッシュのレベルをＬB とする。
計算部１２１と、仮想キャッシュに対してオブジェクト
の追い出しを行う追い出し処理部１２２から構成され
る。計算部１２１は、当該オブジェクトＡの下限ラベル
（Ｌとする）を読み取る。この下限ラベルＬ以上のレベ
ルの仮想キャッシュにおいては、オブジェクトＡがヒッ
トしたものとして性能値を計算する。一方、この下限ラ
ベル未満のレベルの仮想キャッシュにおいては、オブジ
ェクトＡがヒットしなかったものとして性能値を計算す
る。そして、オブジェクトＡの順位以下の順位を持つオ
ブジェクトの中で最大の順位のものをエンドポインタテ
ーブル１４０上で探し、そのエンドオブジェクトに対応
する仮想キャッシュのレベルをＬB とする。
【００２０】追い出し処理部１２２は、ＬB からＬ−１
のレベルのすべての仮想キャッシュの各々に対して、オ
ブジェクト追い出し処理を行い、オブジェクトＡの下限
ラベルをＬB とする。図５は、本発明のキャッシュサー
バ性能値算出方法の処理手順のフローチャートである。
のレベルのすべての仮想キャッシュの各々に対して、オ
ブジェクト追い出し処理を行い、オブジェクトＡの下限
ラベルをＬB とする。図５は、本発明のキャッシュサー
バ性能値算出方法の処理手順のフローチャートである。
【００２１】ステップ１０１） オブジェクト判定部１
１０において、リクエストされたオブジェクトＡがキャ
ッシュテーブル１３０に存在するかを判定する。存在す
る場合にはステップ１０２に移行し、存在しない場合に
はステップ１０３に移行する。 ステップ１０２） キャッシュ置換アルゴリズムでその
新たな順位を決定し、キャッテーブル１３０のすべての
オブジェクトの順位を更新し、ステップ１０４に移行す
る。
１０において、リクエストされたオブジェクトＡがキャ
ッシュテーブル１３０に存在するかを判定する。存在す
る場合にはステップ１０２に移行し、存在しない場合に
はステップ１０３に移行する。 ステップ１０２） キャッシュ置換アルゴリズムでその
新たな順位を決定し、キャッテーブル１３０のすべての
オブジェクトの順位を更新し、ステップ１０４に移行す
る。
【００２２】ステップ１０３） オブジェクトＡがキャ
ッシュテーブル１３０に存在しない場合には、以下の内
容をキャッシュテーブル１３０に書き込む。 当該オブジェクト名 サイズ 下限ラベル：∞ キャッシュ置換アルゴリズムで決定される順位 ステップ１０４） 性能値計算部１２０の計算部１２１
において、当該オブジェクトＡの下限ラベルＬを読み取
る。
ッシュテーブル１３０に存在しない場合には、以下の内
容をキャッシュテーブル１３０に書き込む。 当該オブジェクト名 サイズ 下限ラベル：∞ キャッシュ置換アルゴリズムで決定される順位 ステップ１０４） 性能値計算部１２０の計算部１２１
において、当該オブジェクトＡの下限ラベルＬを読み取
る。
【００２３】・この下限ラベルＬ以上のレベルの仮想キ
ャッシュにおいては、オブジェクトＡがヒットしたもの
として性能値を計算する。 ・一方、この下限ラベル未満のレベルの仮想キャッシュ
においては、オブジェクトＡがヒットしなったものとし
て、性能値を計算する。 ステップ１０５） オブジェクトＡの順位以下の順位を
持つエンドオブジェクトの中で最大の順位のものをエン
ドポインタテーブル１４０上で探し、そのエンドオブジ
ェクトに対応する仮想キャッシュのレベルＬB とする。
ャッシュにおいては、オブジェクトＡがヒットしたもの
として性能値を計算する。 ・一方、この下限ラベル未満のレベルの仮想キャッシュ
においては、オブジェクトＡがヒットしなったものとし
て、性能値を計算する。 ステップ１０５） オブジェクトＡの順位以下の順位を
持つエンドオブジェクトの中で最大の順位のものをエン
ドポインタテーブル１４０上で探し、そのエンドオブジ
ェクトに対応する仮想キャッシュのレベルＬB とする。
【００２４】ステップ１０６） レベルＫを、最大の順
位のものに対応する仮想キャッシュのレベルＬB とす
る。 ステップ１０７） 追い出し処理部１２２において、レ
ベルＬB の仮想キャッシュに対して、オブジェクト追い
出し処理（Discard ）を行う。詳細は図６で説明する。
位のものに対応する仮想キャッシュのレベルＬB とす
る。 ステップ１０７） 追い出し処理部１２２において、レ
ベルＬB の仮想キャッシュに対して、オブジェクト追い
出し処理（Discard ）を行う。詳細は図６で説明する。
【００２５】ステップ１０８） 追い出された各オブジ
ェクトの下限ラベルＫを１増加させる。 ステップ１０９） レベルＫが下限ラベルＬとなった場
合にはステップ１１０に移行し、そうでない場合にはス
テップ１０７に移行する。 ステップ１１０） オブジェクトＡの下限ラベルをＬB
にする。
ェクトの下限ラベルＫを１増加させる。 ステップ１０９） レベルＫが下限ラベルＬとなった場
合にはステップ１１０に移行し、そうでない場合にはス
テップ１０７に移行する。 ステップ１１０） オブジェクトＡの下限ラベルをＬB
にする。
【００２６】ステップ１１１） 次のオブジェクトの処
理に移行する。 次に、上記のステップ１０７におけるオブジェクト追い
出し処理について説明する。図６は、本発明のオブジェ
クト追い出し処理（Discard ）の手順のフローチャート
である。
理に移行する。 次に、上記のステップ１０７におけるオブジェクト追い
出し処理について説明する。図６は、本発明のオブジェ
クト追い出し処理（Discard ）の手順のフローチャート
である。
【００２７】ステップ２０１） 性能値計算部１２０の
追い出し処理部１２２は、オブジェクトＡをレベルＫの
仮想キャッシュに蓄積しようとしたとき、当該仮想キャ
ッシュ容量を越えるかを判定し、越える場合には当該処
理を終了する。 ステップ２０２） レベルＫの仮想キャッシュのエンド
オブジェクトをエンドポインタテーブル１４０で探し、
順位の小さいものから順に、以下の処理を行う。 ステ
ップ２０３） オブジェクトをレベルＫ仮想キャッシュ
から追い出す。つまり、各オブジェクトの下限ラベルを
１だけ増加させる。
追い出し処理部１２２は、オブジェクトＡをレベルＫの
仮想キャッシュに蓄積しようとしたとき、当該仮想キャ
ッシュ容量を越えるかを判定し、越える場合には当該処
理を終了する。 ステップ２０２） レベルＫの仮想キャッシュのエンド
オブジェクトをエンドポインタテーブル１４０で探し、
順位の小さいものから順に、以下の処理を行う。 ステ
ップ２０３） オブジェクトをレベルＫ仮想キャッシュ
から追い出す。つまり、各オブジェクトの下限ラベルを
１だけ増加させる。
【００２８】ステップ２０４） オブジェクトを蓄積で
きる空き容量があるかを判定し、ある場合には、ステッ
プ２０５に移行し、ない場合にはステップ２０３に移行
する。 ステップ２０５） 追い出された残りのオブジェクトの
中で順位が最も小さいものをエンドポインタテーブル１
４０のレベルＫ仮想キャッシュのエンドオブジェクトと
する。
きる空き容量があるかを判定し、ある場合には、ステッ
プ２０５に移行し、ない場合にはステップ２０３に移行
する。 ステップ２０５） 追い出された残りのオブジェクトの
中で順位が最も小さいものをエンドポインタテーブル１
４０のレベルＫ仮想キャッシュのエンドオブジェクトと
する。
【００２９】このように、キャッシュテーブル１３０と
して、動的ハッシュなどのデータ構造を用いることによ
り、オブジェクトがキャッシュテーブル１３０にあるか
否かを高速に判定することができる。また、オブジェク
トの順位を線形リスト構造やヒープ構造で管理すること
により、順位に関する操作を高速化することができる。
して、動的ハッシュなどのデータ構造を用いることによ
り、オブジェクトがキャッシュテーブル１３０にあるか
否かを高速に判定することができる。また、オブジェク
トの順位を線形リスト構造やヒープ構造で管理すること
により、順位に関する操作を高速化することができる。
【００３０】
【実施例】以下、図面と共に本発明の実施例を説明す
る。図７は、本発明の一実施例のリクエスト列の例を示
し、図８は、本発明の一実施例のキャッシュテーブルの
遷移を示し、図９は、本発明の一実施例のエンドポイン
タテーブルの遷移を示す。
る。図７は、本発明の一実施例のリクエスト列の例を示
し、図８は、本発明の一実施例のキャッシュテーブルの
遷移を示し、図９は、本発明の一実施例のエンドポイン
タテーブルの遷移を示す。
【００３１】以下、図７に示すリクエスト列の例に基づ
いて、キャッシュサーバ性能算出の手順を説明する。こ
こで、仮想キャッシュ容量５，１０（それぞれレベル
０，１）とし、性能値としてヒット率（キャッシュでヒ
ットしたオブジェクト数÷リクエストさたオブジェクト
総数）を用いるものとする。
いて、キャッシュサーバ性能算出の手順を説明する。こ
こで、仮想キャッシュ容量５，１０（それぞれレベル
０，１）とし、性能値としてヒット率（キャッシュでヒ
ットしたオブジェクト数÷リクエストさたオブジェクト
総数）を用いるものとする。
【００３２】また、キャッシュ置換アルゴリズムとし
て、ＬＲＵ(Least Recently Used）を用いることにす
る。これは、オブジェクトがリクエストされた際、当該
オブジェクトの順位を、キャッシュされているオブジェ
クトの中で最大の順位＋１とするものである。まず、時
刻Ｔ1 にオブジェクトＡがリクエストされたとき、キャ
ッシュテーブル１３０には何も載っていないので（ステ
ップ１０１）、オブジェクト判定部１１０は、「オブジ
ェクトＡ、サイズ２、下限ラベル∞、順位１」の組を書
き込む（ステップ１０３）（図８（Ａ））。エンドポイ
ンタテーブル１４０には「レベル０、オブジェクトＡ、
順位１」及び「レベル１、オブジェクトＡ、順位１」と
書き込む（図９（Ａ））。
て、ＬＲＵ(Least Recently Used）を用いることにす
る。これは、オブジェクトがリクエストされた際、当該
オブジェクトの順位を、キャッシュされているオブジェ
クトの中で最大の順位＋１とするものである。まず、時
刻Ｔ1 にオブジェクトＡがリクエストされたとき、キャ
ッシュテーブル１３０には何も載っていないので（ステ
ップ１０１）、オブジェクト判定部１１０は、「オブジ
ェクトＡ、サイズ２、下限ラベル∞、順位１」の組を書
き込む（ステップ１０３）（図８（Ａ））。エンドポイ
ンタテーブル１４０には「レベル０、オブジェクトＡ、
順位１」及び「レベル１、オブジェクトＡ、順位１」と
書き込む（図９（Ａ））。
【００３３】性能値計算部１２０の計算部１２１におい
て、下限ラベル未満のレベルの仮想キャッシュ、つま
り、レベル０およびレベル１仮想キャッシュにおいて、
オブジェクトＡがヒットしなかったものとして、性能値
であるヒット率を計算すると、容量５の場合（レベル
０）及び容量１０の場合（レベル１）ともに０である
（ステップ１０４）。
て、下限ラベル未満のレベルの仮想キャッシュ、つま
り、レベル０およびレベル１仮想キャッシュにおいて、
オブジェクトＡがヒットしなかったものとして、性能値
であるヒット率を計算すると、容量５の場合（レベル
０）及び容量１０の場合（レベル１）ともに０である
（ステップ１０４）。
【００３４】オブジェクトＡの順位以下の順位を持つエ
ンドオブジェクトの中で、最大の順位のものはオブジェ
クトＡ自身しかなく、その仮想キャッシュのレベルは０
である。従って、追い出し処理部１２２は、ＬB ＝０，
Ｌ−１＝∞なので、レベル０及びレベル１仮想キャッシ
ュに対して、オブジェクト追い出し処理を行う（ステッ
プ１０７）。しかし、いずれも、オブジェクトＡを蓄積
することで、容量を越えないので、オブジェクトをレベ
ル０及びレベル１仮想キャッシュから追い出さない。オ
ブジェクトＡの処理の最後にオブジェクトＡの下限ラベ
ルを０に更新する。
ンドオブジェクトの中で、最大の順位のものはオブジェ
クトＡ自身しかなく、その仮想キャッシュのレベルは０
である。従って、追い出し処理部１２２は、ＬB ＝０，
Ｌ−１＝∞なので、レベル０及びレベル１仮想キャッシ
ュに対して、オブジェクト追い出し処理を行う（ステッ
プ１０７）。しかし、いずれも、オブジェクトＡを蓄積
することで、容量を越えないので、オブジェクトをレベ
ル０及びレベル１仮想キャッシュから追い出さない。オ
ブジェクトＡの処理の最後にオブジェクトＡの下限ラベ
ルを０に更新する。
【００３５】次に、時刻Ｔ2 にオブジェクトＢがリクエ
ストされた時、キャッシュテーブル１３０にオブジェク
トＢは載っていないので（ステップ１０１）、オブジェ
クト判定部１１０は、「オブジェクトＢ、サイズ２、下
限ラベル∞、順位２」の組をキャッシュテーブル１３０
に書き込む（ステップ１０３）（図８（Ｂ））。性能計
算部１２０の計算部１２１において、下限ラベル未満の
レベルの仮想キャッシュ、つまり、レベル０及びレベル
１の仮想キャッシュにおいて、オブジェクトＢがヒット
しなかったものとして、性能値であるヒット率を計算す
ると、容量５の場合（レベル０）及び容量１０の場合
（レベル１）と共に０である（ステップ１０４）。
ストされた時、キャッシュテーブル１３０にオブジェク
トＢは載っていないので（ステップ１０１）、オブジェ
クト判定部１１０は、「オブジェクトＢ、サイズ２、下
限ラベル∞、順位２」の組をキャッシュテーブル１３０
に書き込む（ステップ１０３）（図８（Ｂ））。性能計
算部１２０の計算部１２１において、下限ラベル未満の
レベルの仮想キャッシュ、つまり、レベル０及びレベル
１の仮想キャッシュにおいて、オブジェクトＢがヒット
しなかったものとして、性能値であるヒット率を計算す
ると、容量５の場合（レベル０）及び容量１０の場合
（レベル１）と共に０である（ステップ１０４）。
【００３６】オブジェクトＢの順位以下の順位を持つエ
ンドオブジェクトの中で、最大の順位のものはオブジェ
クトＡである。また、その仮想キャッシュのレベルは０
である。従って、追い出し処理部１２２は、ＬB ＝０，
Ｌ−１＝∞なので、レベル０及びレベル１仮想キャッシ
ュに対して、オブジェクト追い出し処理を行う（ステッ
プ１０７）。しかし、いずれもオブジェクトＢを蓄積す
ることで容量を越えないので、オブジェクトをレベル０
及びレベル１仮想キャッシュから追い出さない。オブジ
ェクトＢの処理に最後にオブジェクトＢの下限ラベルを
０に更新する（図８（Ｂ））。
ンドオブジェクトの中で、最大の順位のものはオブジェ
クトＡである。また、その仮想キャッシュのレベルは０
である。従って、追い出し処理部１２２は、ＬB ＝０，
Ｌ−１＝∞なので、レベル０及びレベル１仮想キャッシ
ュに対して、オブジェクト追い出し処理を行う（ステッ
プ１０７）。しかし、いずれもオブジェクトＢを蓄積す
ることで容量を越えないので、オブジェクトをレベル０
及びレベル１仮想キャッシュから追い出さない。オブジ
ェクトＢの処理に最後にオブジェクトＢの下限ラベルを
０に更新する（図８（Ｂ））。
【００３７】時刻Ｔ3 にオブジェクトＣがリクエストさ
れた時、キャッシュテーブル１３０にオブジェクトＣは
載っていないので（ステップ１０１）、オブジェクト判
定部１１０は、「オブジェクトＣ，サイズ４、下限ラベ
ル∞、順位３」の組を書き込む（ステップ１０３）（図
８（Ｃ））。下限ラベル未満のレベルの仮想キャッシ
ュ、つまり、レベル０及びレベル１仮想キャッシュにお
いて、オブジェクトＣがヒットしなかったものとして、
性能値計算部１２０の計算部１２１において、性能値で
あるヒット率を計算すると、容量５の場合（レベル０）
及び容量１０の場合（レベル１）共に０である（ステッ
プ１０４）。
れた時、キャッシュテーブル１３０にオブジェクトＣは
載っていないので（ステップ１０１）、オブジェクト判
定部１１０は、「オブジェクトＣ，サイズ４、下限ラベ
ル∞、順位３」の組を書き込む（ステップ１０３）（図
８（Ｃ））。下限ラベル未満のレベルの仮想キャッシ
ュ、つまり、レベル０及びレベル１仮想キャッシュにお
いて、オブジェクトＣがヒットしなかったものとして、
性能値計算部１２０の計算部１２１において、性能値で
あるヒット率を計算すると、容量５の場合（レベル０）
及び容量１０の場合（レベル１）共に０である（ステッ
プ１０４）。
【００３８】オブジェクトＣの順位以下の順位を持つエ
ンドオブジェクトの中で、最大の順位のものはオブジェ
クトＡである。その仮想キャッシュのレベルは０であ
る。従って、ＬB ＝０，Ｌ−１＝∞なので、追い出し処
理部１２２は、レベル０及びレベル１仮想キャッシュに
対して、オブジェクト追い出し処理を行う（ステップ１
０７）。
ンドオブジェクトの中で、最大の順位のものはオブジェ
クトＡである。その仮想キャッシュのレベルは０であ
る。従って、ＬB ＝０，Ｌ−１＝∞なので、追い出し処
理部１２２は、レベル０及びレベル１仮想キャッシュに
対して、オブジェクト追い出し処理を行う（ステップ１
０７）。
【００３９】・レベル０仮想キャッシュにおいて：オブ
ジェクトＣを蓄積すると、オブジェクトＡ，Ｂ，Ｃのサ
イズの合計が２＋２＋４＝８＞５となるため、追い出し
処理部１２２において、レベル０からオブジェクトを追
い出す処理が必要となる。まず、レベル０仮想キャッシ
ュのエンドオブジェクトをエンドポインタテーブル１４
０で探すとオブジェクトＡである（図９（Ｂ））。追い
出し処理部１２２は、オブジェクトＡを追い出し（ステ
ップ１０７）、オブジェクトＡの下限ラベルを０から１
に更新し、レベル０仮想キャッシュの残されたオブジェ
クトの中で最も順位が小さいオブジェクトＢを、レベル
０仮想キャッシュのエンドオブジェクトとしてエンドポ
インタテーブル１４０を更新する（図９（Ｃ））。オブ
ジェクトＢ，Ｃのサイズの合計が２＋４＝６＞５となる
が、まだ十分な空き容量がないため、追い出し処理部１
２２は、オブジェクトＢを追い出し（ステップ１０
７）、オブジェクトＢの下限ラベルを０から１に更新し
（ステップ１０８）、レベル０仮想キャッシュの残され
たオブジェクトの中で最も順位が小さいオブジェクトＣ
を、レベル０仮想キャッシュのエンドオブジェクトとし
てエンドポインタテーブル１４０を更新する（図９
（Ｃ））。オブジェクトＣのサイズは４＜５なので、レ
ベル０仮想キャッシュに蓄積可能であり、追い出し処理
部１２２は、オブジェクトをレベル０仮想キャッシュか
ら追い出す処理を停止する。
ジェクトＣを蓄積すると、オブジェクトＡ，Ｂ，Ｃのサ
イズの合計が２＋２＋４＝８＞５となるため、追い出し
処理部１２２において、レベル０からオブジェクトを追
い出す処理が必要となる。まず、レベル０仮想キャッシ
ュのエンドオブジェクトをエンドポインタテーブル１４
０で探すとオブジェクトＡである（図９（Ｂ））。追い
出し処理部１２２は、オブジェクトＡを追い出し（ステ
ップ１０７）、オブジェクトＡの下限ラベルを０から１
に更新し、レベル０仮想キャッシュの残されたオブジェ
クトの中で最も順位が小さいオブジェクトＢを、レベル
０仮想キャッシュのエンドオブジェクトとしてエンドポ
インタテーブル１４０を更新する（図９（Ｃ））。オブ
ジェクトＢ，Ｃのサイズの合計が２＋４＝６＞５となる
が、まだ十分な空き容量がないため、追い出し処理部１
２２は、オブジェクトＢを追い出し（ステップ１０
７）、オブジェクトＢの下限ラベルを０から１に更新し
（ステップ１０８）、レベル０仮想キャッシュの残され
たオブジェクトの中で最も順位が小さいオブジェクトＣ
を、レベル０仮想キャッシュのエンドオブジェクトとし
てエンドポインタテーブル１４０を更新する（図９
（Ｃ））。オブジェクトＣのサイズは４＜５なので、レ
ベル０仮想キャッシュに蓄積可能であり、追い出し処理
部１２２は、オブジェクトをレベル０仮想キャッシュか
ら追い出す処理を停止する。
【００４０】・レベル１仮想キャッシュにおいて：オブ
ジェクトＡ，Ｂ，Ｃのサイズの合計が２＋２＋４＝８＜
１０であり、レベル１仮想キャッシュの容量を越えない
ので、追い出し処理部１２２は、仮想キャッシュから追
い出さない。オブジェクトＣの処理の最後に、オブジェ
クトＣの下限ラベルを０にする。
ジェクトＡ，Ｂ，Ｃのサイズの合計が２＋２＋４＝８＜
１０であり、レベル１仮想キャッシュの容量を越えない
ので、追い出し処理部１２２は、仮想キャッシュから追
い出さない。オブジェクトＣの処理の最後に、オブジェ
クトＣの下限ラベルを０にする。
【００４１】時刻Ｔ4 にオブジェクトＡがリクエストさ
れたとき、キャッシュテーブル１３０には、オブジェク
トＡが載っているので、オブジェクト判定部１１０は、
キャッシュ置換アルゴリムＬＲＵで新たな順位４に更新
する（図８（Ｄ））。オブジェクトＡの下限ラベルは１
なので、性能値計算部１２０の計算部１２１は、レベル
０仮想キャッシュにおいて、オブジェクトＡがヒットし
なかったものとして、ヒット率を計算すると０である。
一方、レベル１仮想キャッシュにおいては、オブジェク
トＡがヒットしたとしてヒット率を計算すると、１÷４
（ヒット数÷リクエスト総数）＝２５％である。
れたとき、キャッシュテーブル１３０には、オブジェク
トＡが載っているので、オブジェクト判定部１１０は、
キャッシュ置換アルゴリムＬＲＵで新たな順位４に更新
する（図８（Ｄ））。オブジェクトＡの下限ラベルは１
なので、性能値計算部１２０の計算部１２１は、レベル
０仮想キャッシュにおいて、オブジェクトＡがヒットし
なかったものとして、ヒット率を計算すると０である。
一方、レベル１仮想キャッシュにおいては、オブジェク
トＡがヒットしたとしてヒット率を計算すると、１÷４
（ヒット数÷リクエスト総数）＝２５％である。
【００４２】オブジェクトＡの順位４以下の順位を持つ
エンドポインタテーブル１４０のエンドオブジェクトの
中で、最大の順位のものは、順位３のオブジェクトＣで
あり、そのレベルは０である。従って、追い出し処理部
１２２は、ＬB ＝０、Ｌ−１＝０（オブジェクトＡの下
限ラベルＬは１）なので、レベル０仮想キャッシュに対
してのみ、オブジェクト追い出し処理を行う。
エンドポインタテーブル１４０のエンドオブジェクトの
中で、最大の順位のものは、順位３のオブジェクトＣで
あり、そのレベルは０である。従って、追い出し処理部
１２２は、ＬB ＝０、Ｌ−１＝０（オブジェクトＡの下
限ラベルＬは１）なので、レベル０仮想キャッシュに対
してのみ、オブジェクト追い出し処理を行う。
【００４３】・レベル０仮想キャッシュにおいて：オブ
ジェクトＡを蓄積すると、オブジェクトＡ，Ｃのサイズ
の合計が２＋４＝６＞５となるため、レベル０からオブ
ジェクトを追い出す処理が必要となる。まず、オブジェ
クト判定部１１０において、レベル０仮想キャッシュの
エンドオブジェクトをエンドポインタテーブル１４０で
探すと、オブジェクトＣである（図９（Ｃ））。追い出
し処理部１２２において、オブジェクトＣを追い出し
（ステップ１０７）、オブジェクトＣの下限ラベルを０
から１に更新し（ステップ１０８）、レベル０仮想キャ
ッシュの残されたオブジェクトの中で最も順位が小さい
オブジェクトＡを、レベル０仮想キャッシュのエンドオ
ブジェクトとしてエンドポインタテーブル１４０を更新
する（図９（Ｄ））。
ジェクトＡを蓄積すると、オブジェクトＡ，Ｃのサイズ
の合計が２＋４＝６＞５となるため、レベル０からオブ
ジェクトを追い出す処理が必要となる。まず、オブジェ
クト判定部１１０において、レベル０仮想キャッシュの
エンドオブジェクトをエンドポインタテーブル１４０で
探すと、オブジェクトＣである（図９（Ｃ））。追い出
し処理部１２２において、オブジェクトＣを追い出し
（ステップ１０７）、オブジェクトＣの下限ラベルを０
から１に更新し（ステップ１０８）、レベル０仮想キャ
ッシュの残されたオブジェクトの中で最も順位が小さい
オブジェクトＡを、レベル０仮想キャッシュのエンドオ
ブジェクトとしてエンドポインタテーブル１４０を更新
する（図９（Ｄ））。
【００４４】オブジェクトＡのサイズは２＜５であり、
レベル０仮想キャッシュの容量を越えないので、追い出
し処理部１２２は、レベル０仮想キャッシュに蓄積可能
であるため、オブジェクトの追い出し処理を停止する。
オブジェクトＡの処理の最後にオブジェクトＡの下限ラ
ベルを０にする（ステップ１１０）。
レベル０仮想キャッシュの容量を越えないので、追い出
し処理部１２２は、レベル０仮想キャッシュに蓄積可能
であるため、オブジェクトの追い出し処理を停止する。
オブジェクトＡの処理の最後にオブジェクトＡの下限ラ
ベルを０にする（ステップ１１０）。
【００４５】最終的に得られたヒット率は、、容量５の
場合は、０％、容量１０の場合は２５％であることが分
かる。このようにして、複数のことある容量におけるキ
ャッシュサーバの性能値を同時に算出することができ
る。また、上記の実施例では、図４の構成及び図５、図
６のフローチャートに基づいて説明したが、図４の構成
及び図５、図６のステップをプログラムとして構築し、
キャッシュサーバ性能値算出装置として利用されるコン
ピュータに接続されるディスク装置や、フロッピーディ
スク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、
本発明を実施する際にインストールすることにより、容
易に本発明を実現できる。
場合は、０％、容量１０の場合は２５％であることが分
かる。このようにして、複数のことある容量におけるキ
ャッシュサーバの性能値を同時に算出することができ
る。また、上記の実施例では、図４の構成及び図５、図
６のフローチャートに基づいて説明したが、図４の構成
及び図５、図６のステップをプログラムとして構築し、
キャッシュサーバ性能値算出装置として利用されるコン
ピュータに接続されるディスク装置や、フロッピーディ
スク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納しておき、
本発明を実施する際にインストールすることにより、容
易に本発明を実現できる。
【００４６】なお、本発明は、上記の実施例に限定され
ることなく、特許請求の範囲内において種々変更・応用
が可能である。
ることなく、特許請求の範囲内において種々変更・応用
が可能である。
【００４７】
【発明の効果】上述のように、本発明によれば、実際の
リクエスト列に基づいて、少ない処理で、複数の異なる
容量におけるキャッシュサーバの性能値を同時に算出す
ることができる。
リクエスト列に基づいて、少ない処理で、複数の異なる
容量におけるキャッシュサーバの性能値を同時に算出す
ることができる。
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明のキャッシュサーバ性能値算出装置の接
続構成図である。
続構成図である。
【図４】本発明のキャッシュサーバ性能値算出装置の構
成図である。
成図である。
【図５】本発明のキャッシュサーバ性能値算出方法の処
理手順のフローチャートである。
理手順のフローチャートである。
【図６】本発明のオブジェクト追い出し処理（Discard
）の手順のフローチャートである。
）の手順のフローチャートである。
【図７】本発明の一実施例のリクエスト列の例である。
【図８】本発明の一実施例のキャッシュテーブルの遷移
を示す図である。
を示す図である。
【図９】本発明の一実施例のエンドポインタテーブルの
遷移を示す図である。
遷移を示す図である。
１００ キャッシュサーバ性能値算出装置 １１０ オブジェクト判定手段、オブジェクト判定部 １２０ 性能値計算手段、性能値計算部 １２１ 計算部 １２２ 追い出し処理部 １３０ キャッシュテーブル １４０ エンドポインタテーブル １５０ 追い出し手段 １６０ ラベル設定手段
Claims (6)
- 【請求項１】 キャッシュサーバにおいて、リクエスト
の列に基づいて、仮想的なキャッシュ容量（以下、仮想
キャッシュ容量と記す）を持つ仮想的なキャッシュ（以
下、仮想キャッシュ）に対する性能値を算出するキャッ
シュサーバ性能値算出方法において、 リクエストされたオブジェクトＡが、オブジェクト名、
オブジェクトサイズ、オブジェクトをキャッシュする仮
想キャッシュの中で最小のレベルである下限ラベル、及
び順位を記録するキャッシュテーブルに存在するかを判
定し、 存在しなければ、オブジェクト名、サイズ、下限ラベ
ル、キャッシュ置換アルゴリズムで決定される順位の組
を前記キャッシュテーブルに書き込み、 存在すれば、キャッシュ置換アルゴリズムでオブジェク
トの新たな順位を決定し、前記キャッシュテーブルのオ
ブジェクトの順位を更新し、 前記オブジェクトＡの下限ラベルを読み取り、 前記下限ラベル以上のレベルの仮想キャッシュにおいて
は、前記オブジェクトＡがヒットしたものとして性能値
を計算し、 前記下限ラベル未満のレベルの仮想キャッシュにおいて
は、前記オブジェクトＡがヒットしなかったものとして
性能値を計算し、 前記仮想キャッシュに蓄積されているオブジェクトプロ
グラムの中で最も順位の低いオブジェクトであるエンド
オブジェクトの中で、オブジェクトＡの順位以下の最大
の順位のものを、該仮想キャッシュのレベル、エンドオ
ブジェクト、及びその順位を並べたエンドポインターテ
ーブル上で探し、該エンドオブジェクトに対応する仮想
キャッシュのレベルを設定し、 所定のレベルのすべての仮想キャッシュの各々に対し
て、オブジェクト追い出し処理を行い、 前記オブジェクトＡの下限ラベルを設定することを特徴
とするキャッシュサーバ性能値算出方法。 - 【請求項２】 前記オブジェクト追い出し処理として、 リクエストされた前記オブジェクトＡを、あるレベルＫ
の仮想キャッシュに蓄積しようとした時、該仮想キャッ
シュの容量を越える場合には、該レベルＫの仮想キャッ
シュのエンドオブジェクトを前記エンドポインタテーブ
ルで探し、順位の小さいものから順に、該オブジェクト
Ａを蓄積できる空き容量ができるまで、オブジェクトを
該レベルＫの仮想キャッシュから追い出し、 追い出された残りのオブジェクトの中で順位が最も小さ
いものを前記エンドポインタテーブルのあるレベルＫの
仮想キャッシュのエンドオブジェクトとする請求項１記
載のキャッシュサーバ性能値算出方法。 - 【請求項３】キャッシュサーバにおいて、リクエストの
列に基づいて、仮想キャッシュ容量を持つ仮想キャッシ
ュに対する性能値を算出するキャッシュサーバ性能値算
出装置であって、 オブジェクト名、オブジェクトサイズ、オブジェクトを
キャッシュする仮想キャッシュの中で最小のレベルであ
る下限ラベル、及び順位の組とを記録するキャッシュテ
ーブルと、 各仮想キャッシュに蓄積されているオブジェクトの中で
最も順位の低いオブジェクトであるエンドオブジェク
ト、仮想キャッシュのレベル、及びその順位を並べたエ
ンドポインタテーブルと、 リクエストされたオブジェクトＡが、前記キャッシュテ
ーブルに存在するかを判定し、存在しなければ、オブジ
ェクト名、サイズ、下限ラベル、キャッシュ置換アルゴ
リズムで決定される順位の組を該キャッシュテーブルに
書き込み、存在すれば、キャッシュ置換アルゴリズムで
オブジェクトの新たな順位を決定し、該キャッシュテー
ブルのオブジェクトの順位を更新するオブジェクト判定
手段と、 前記オブジェクトＡの下限ラベルを読み取り、前記下限
ラベル以上のレベルの仮想キャッシュにおいては、前記
オブジェクトＡがヒットしたものとして性能値を計算
し、前記下限ラベル未満のレベルの仮想キャッシュにお
いては、前記オブジェクトＡがヒットしなかったものと
して性能値を計算し、仮想キャッシュに蓄積されている
オブジェクトプログラムの中で最も順位の低いオブジェ
クトであるエンドオブジェクトの中で、オブジェクトＡ
の順位以下の最大の順位のものを、該仮想キャッシュの
レベル、エンドオブジェクト、及びその順位を並べたエ
ンドポインターテーブル上で探し、該エンドオブジェク
トに対応する仮想キャッシュのレベルを設定する性能値
計算手段と、 所定のレベルのすべての仮想キャッシュの各々に対し
て、オブジェクト追い出し処理を行う追い出し手段と、 前記オブジェクトＡの下限ラベルを設定するラベル設定
手段とを有することを特徴とするキャッシュサーバ性能
値算出装置。 - 【請求項４】 前記追い出し手段は、リクエストされた
前記オブジェクトＡを、あるレベルＫの仮想キャッシュ
に蓄積しようとした時、該仮想キャッシュの容量を越え
る場合には、該レベルＫの仮想キャッシュのエンドオブ
ジェクトを前記エンドポインタテーブルで探し、順位の
小さいものから順に、該オブジェクトＡを蓄積できる空
き容量ができるまで、オブジェクトを該レベルＫの仮想
キャッシュから追い出し、追い出された残りのオブジェ
クトの中で順位が最も小さいものを該記エンドポインタ
テーブルのあるレベルＫの仮想キャッシュのエンドオブ
ジェクトとする手段を有する請求項３記載のキャッシュ
サーバ性能値算出装置。 - 【請求項５】 キャッシュサーバにおいて、リクエスト
の列に基づいて、仮想キャッシュ容量を持つ仮想キャッ
シュに対する性能値を算出するキャッシュサーバ性能値
算出プログラムを格納した記憶媒体であって、 リクエストされたオブジェクトＡが、オブジェクト名、
オブジェクトサイズ、オブジェクトをキャッシュする仮
想キャッシュの中で最小のレベルである下限ラベル、及
び順位を記録するキャッシュテーブルに存在するかを判
定するプロセスと、 存在しなければ、オブジェクト名、サイズ、下限ラベ
ル、キャッシュ置換アルゴリズムで決定される順位の組
を前記キャッシュテーブルに書き込むプロセスと、 存在すれば、キャッシュ置換アルゴリズムでオブジェク
トの新たな順位を決定し、前記キャッシュテーブルのオ
ブジェクトの順位を更新するプロセスと、 前記オブジェクトＡの下限ラベルを読み取るプロセス
と、 前記下限ラベル以上のレベルの仮想キャッシュにおいて
は、前記オブジェクトＡがヒットしたものとして性能値
を計算するプロセスと、 前記下限ラベル未満のレベルの仮想キャッシュにおいて
は、前記オブジェクトＡがヒットしなかったものとして
性能値を計算するプロセスと、 前記仮想キャッシュに蓄積されているオブジェクトの中
で最も順位の低いオブジェクトであるエンドオブジェク
トの中でオブジェクトＡの順位以下の最大の順位のもの
を、仮想キャッシュのレベル、エンドオブジェクト、及
びその順位を並べたエンドポインターテーブル上で探
し、該エンドオブジェクトに対応する仮想キャッシュの
レベルを設定するプロセスと、 所定のレベルのすべての仮想キャッシュの各々に対し
て、オブジェクト追い出し処理を行うプロセスと、 前記オブジェクトＡの下限ラベルを設定するプロセスと
を有することを特徴とするキャッシュサーバ性能値算出
プログラムを格納した記憶媒体。 - 【請求項６】 前記オブジェクト追い出しプロセスは、 リクエストされた前記オブジェクトＡを、あるレベルＫ
の仮想キャッシュに蓄積しようとした時、該仮想キャッ
シュの容量を越える場合には、該レベルＫの仮想キャッ
シュのエンドオブジェクトを前記エンドポインタテーブ
ルで探し、順位の小さいものから順に、該オブジェクト
Ａを蓄積できる空き容量ができるまで、オブジェクトを
該レベルＫの仮想キャッシュから追い出すプロセスと、 追い出された残りのオブジェクトの中で順位が最も小さ
いものを前記エンドポインタテーブルのあるレベルＫの
仮想キャッシュのエンドオブジェクトとするプロセスと
を有する請求項５記載のキャッシュサーバ性能値算出プ
ログラムを格納した記憶媒体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22399699A JP3788121B2 (ja) | 1999-08-06 | 1999-08-06 | キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP22399699A JP3788121B2 (ja) | 1999-08-06 | 1999-08-06 | キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001051892A true JP2001051892A (ja) | 2001-02-23 |
| JP3788121B2 JP3788121B2 (ja) | 2006-06-21 |
Family
ID=16806963
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP22399699A Expired - Fee Related JP3788121B2 (ja) | 1999-08-06 | 1999-08-06 | キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3788121B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005285058A (ja) * | 2004-03-31 | 2005-10-13 | Hitachi Ltd | 記憶装置のキャッシュ管理方法 |
| CN102063462A (zh) * | 2010-10-29 | 2011-05-18 | 蓝汛网络科技（北京）有限公司 | 一种回收缓存服务器中存储资源的方法及装置 |
| JP2013540322A (ja) * | 2010-10-04 | 2013-10-31 | クアルコム，インコーポレイテッド | ワイヤレスハンドヘルドコンピューティングデバイスのメモリリソースを管理するためのシステムおよび方法 |
-
1999
- 1999-08-06 JP JP22399699A patent/JP3788121B2/ja not_active Expired - Fee Related
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005285058A (ja) * | 2004-03-31 | 2005-10-13 | Hitachi Ltd | 記憶装置のキャッシュ管理方法 |
| JP4631301B2 (ja) * | 2004-03-31 | 2011-02-16 | 株式会社日立製作所 | 記憶装置のキャッシュ管理方法 |
| JP2013540322A (ja) * | 2010-10-04 | 2013-10-31 | クアルコム，インコーポレイテッド | ワイヤレスハンドヘルドコンピューティングデバイスのメモリリソースを管理するためのシステムおよび方法 |
| JP2015135690A (ja) * | 2010-10-04 | 2015-07-27 | クアルコム，インコーポレイテッド | ワイヤレスハンドヘルドコンピューティングデバイスのメモリリソースを管理するためのシステムおよび方法 |
| CN102063462A (zh) * | 2010-10-29 | 2011-05-18 | 蓝汛网络科技（北京）有限公司 | 一种回收缓存服务器中存储资源的方法及装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3788121B2 (ja) | 2006-06-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11301394B2 (en) | Using a machine learning module to select one of multiple cache eviction algorithms to use to evict a track from the cache | |
| JP4246922B2 (ja) | 保護機能付き最近最低使用頻度置換方法 | |
| US7424577B2 (en) | Dynamic optimization of cache memory | |
| US8255630B1 (en) | Optimization of cascaded virtual cache memory | |
| US7360015B2 (en) | Preventing storage of streaming accesses in a cache | |
| US5778430A (en) | Method and apparatus for computer disk cache management | |
| US6385699B1 (en) | Managing an object store based on object replacement penalties and reference probabilities | |
| Liu et al. | Hybrid storage management for database systems | |
| US20160019000A1 (en) | Promotion of partial data segments in flash cache | |
| JP2008502965A (ja) | ルックアップ・キャッシュにオブジェクトを維持するためのシステム及び方法 | |
| US7469320B2 (en) | Adaptive replacement cache | |
| US9471253B2 (en) | Use of flash cache to improve tiered migration performance | |
| CN108228088B (zh) | 用于管理存储系统的方法和设备 | |
| CN109002400B (zh) | 一种内容感知型计算机缓存管理系统及方法 | |
| JP6394231B2 (ja) | データ配置制御プログラム、データ配置制御装置およびデータ配置制御方法 | |
| JP2001051892A (ja) | キャッシュサーバ性能値算出方法及び装置及びキャッシュサーバ性能値算出プログラムを格納した記憶媒体 | |
| US7529891B2 (en) | Balanced prefetching exploiting structured data | |
| JP2019020965A (ja) | 情報処理装置、プログラム及び情報処理方法 | |
| KR101976320B1 (ko) | 라스트 레벨 캐시 메모리 및 이의 데이터 관리 방법 | |
| US11977483B2 (en) | Maintaining data in a first level memory and buckets representing regions of memory devices to extend data cache | |
| US20210263648A1 (en) | Method for managing performance of logical disk and storage array | |
| CN117992366A (zh) | 一种缓存处理方法、装置、计算机设备及存储介质 | |
| CN118715511A (zh) | 将l3高速缓存数据逐出的数据重新找取到末级高速缓存中 | |
| CN116795878A (zh) | 数据处理方法及装置、电子设备及介质 | |
| KR19980047901A (ko) | 객체지향 데이터베이스 시스템을 위한 비용기반 객체 버퍼 교체 방법 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20051129 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060120 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060307 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20060320 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090407 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100407 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110407 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120407 Year of fee payment: 6 |
|
| LAPS | Cancellation because of no payment of annual fees |