(57)【特許請求の範囲】
【請求項１】
オブジェクトのクラスが階層的にレベル分けされているデータ構造内のキャッシュすべきオブジェクトを選択する方法であって、
１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへ参照が生じたことに応答して、前記他のレベルに属するクラスを検出するステップと、
これまでにキャッシュされておらず且つ前記第１クラスの第１オブジェクト以降参照をたどることができ且つ前記他のレベルに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するステップと、
を含むキャッシュ対象オブジェクト選択方法。
【請求項２】
前記他のレベルに属するクラスのオブジェクト及びキャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ前記第１クラスの第１オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとして指定するステップと、
をさらに含む請求項１記載のキャッシュ対象オブジェクト選択方法。
【請求項３】
オブジェクトのクラスが階層的にレベル分けされており、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへの参照が生じる際に前記第１クラスの第１オブジェクトから直接又は間接的に参照をたどることができるオブジェクトのクラスであって前記他のレベルに属するクラスのグループが、前記第１クラス及び前記第２クラスの組ごとに定義されているデータ構造において、当該データ構造内のキャッシュすべきオブジェクトを選択する方法であって、
あるレベルに属する第３クラスの第３オブジェクトから他のレベルに属する第４クラスの第４オブジェクトへの参照が生じることに応答して、前記第３クラス及び前記第４クラスの組により定義されるグループを求めるステップと、
これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができ且つ前記第３クラス及び前記第４クラスの組により定義されるグループに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するステップと、
を含むキャッシュ対象オブジェクト選択方法。
【請求項４】
前記第３クラス及び前記第４クラスの組により定義されるグループに属するクラスのオブジェクト及びキャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとして指定するステップと、
をさらに含む請求項３記載のキャッシュ対象オブジェクト選択方法。
【請求項５】
オブジェクトのクラスが階層的にレベル分けされており、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへの参照が生じる際に前記第１クラスの第１オブジェクトから直接又は間接的に参照をたどることができるオブジェクトのクラスであって前記他のレベルに属するクラスのグループが、前記第１クラスごとに定義されているデータ構造において、当該データ構造内のキャッシュすべきオブジェクトを選択する方法であって、
あるレベルに属する第３クラスの第３オブジェクトから他のレベルに属する第４クラスの第４オブジェクトへの参照が生じることに応答して、前記第３クラスにより定義されるグループを求めるステップと、
これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができ且つ前記第３クラスにより定義されるグループに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するステップと、
を含むキャッシュ対象オブジェクト選択方法。
【請求項６】
オブジェクトのクラスが階層的にレベル分けされているデータ構造において、キャッシュされる順番でｎ番目のレベルｎ以降のレベルに属するクラスの、キャッシュされたオブジェクトを破棄する方法であって、
キャッシュされている順番でｎ−１番目のレベルに属するクラスのオブジェクトであって、前記レベルｎに属するクラスのオブジェクトへの参照を有する、前記レベルｎのキー・オブジェクトを検出するステップと、
検出された前記レベルｎのキー・オブジェクトの、前記レベルｎに属するクラスのオブジェクトへの参照を無効化するステップと、
前記レベルｎのキー・オブジェクトから参照をたどることができ且つ前記レベルｎ以上のレベルに属するオブジェクトを破棄するステップと、
を含むオブジェクト破棄方法。
【請求項７】
記憶装置に格納された、オブジェクトのクラスが階層的にレベル分けされているデータ構造内のキャッシュすべきオブジェクトを選択するコンピュータであって、
１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへ参照が生じたことに応答して、前記他のレベルに属するクラスを検出するクラス・デテクタと、
これまでにキャッシュされておらず且つ前記第１クラスの第１オブジェクト以降参照をたどることができ且つ前記他のレベルに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するオブジェクト指定プロセッサと、
を有するコンピュータ。
【請求項８】
前記オブジェクト指定プロセッサが、
前記他のレベルに属するクラスのオブジェクト及びキャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ前記第１クラスの第１オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとしてさらに指定する、請求項７記載のコンピュータ。
【請求項９】
オブジェクトのクラスが階層的にレベル分けされており、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへの参照が生じる際に前記第１クラスの第１オブジェクトから直接又は間接的に参照をたどることができるオブジェクトのクラスであって前記他のレベルに属するクラスのグループが、前記第１クラス及び前記第２クラスの組ごとに定義されているデータ構造を格納した記憶装置から、当該データ構造内のキャッシュすべきオブジェクトを選択するコンピュータであって、
あるレベルに属する第３クラスの第３オブジェクトから他のレベルに属する第４クラスの第４オブジェクトへの参照が生じることに応答して、前記第３クラス及び前記第４クラスの組により定義されるグループを検出するグループ・デテクタと、
これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができ且つ前記第３クラス及び前記第４クラスの組により定義されるグループに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するオブジェクト指定プロセッサと、
を有するコンピュータ。
【請求項１０】
前記オブジェクト指定プロセッサが、
前記第３クラス及び前記第４クラスの組により定義されるグループに属するクラスのオブジェクト及びキャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとしてさらに指定する、請求項９記載のコンピュータ。
【請求項１１】
オブジェクトのクラスが階層的にレベル分けされているデータ構造において、キャッシュされる順番でｎ番目のレベルｎ以降のレベルに属するクラスの、キャッシュされたオブジェクトを破棄するコンピュータであって、
キャッシュされている順番でｎ−１番目のレベルに属するクラスのオブジェクトであって、前記レベルｎに属するクラスのオブジェクトへの参照を有する、前記レベルｎのキー・オブジェクトを検出するキー・オブジェクト・デテクタと、
検出された前記レベルｎのキー・オブジェクトの、前記レベルｎに属するクラスのオブジェクトへの参照を無効化する参照無効化プロセッサと、
前記レベルｎのキー・オブジェクトから参照をたどることができ且つ前記レベルｎ以上のレベルに属するオブジェクトを破棄するオブジェクト破棄プロセッサと、
を有するコンピュータ。
【請求項１２】
オブジェクトのクラスが階層的にレベル分けされているデータ構造内のキャッシュすべきオブジェクトをコンピュータに選択させるプログラムを格納した記憶媒体であって、
前記プログラムは、前記コンピュータに、
１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへ参照が生じたことに応答して、前記他のレベルに属するクラスを検出するステップと、
これまでにキャッシュされておらず且つ前記第１クラスの第１オブジェクト以降参照をたどることができ且つ前記他のレベルに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するオブジェクト指定ステップと、
を実行させる、記憶媒体。
【請求項１３】
前記オブジェクト指定ステップが、
キャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ前記第１クラスの第１オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとして指定するステップを含む、請求項１２記載の記憶媒体。
【請求項１４】
オブジェクトのクラスが階層的にレベル分けされており、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへの参照が生じる際に前記第１クラスの第１オブジェクトから直接又は間接的に参照をたどることができるオブジェクトのクラスであって前記他のレベルに属するクラスのグループが、前記第１クラス及び前記第２クラスの組ごと又は前記第１クラスごとに定義されているデータ構造において、当該データ構造内のキャッシュすべきオブジェクトをコンピュータに選択させるためのプログラムを格納した記憶媒体であって、
前記プログラムは、前記コンピュータに、
あるレベルに属する第３クラスの第３オブジェクトから他のレベルに属する第４クラスの第４オブジェクトへの参照が生じることに応答して、前記第３クラス及び前記第４クラスの組又は前記第３クラスにより定義されるグループを求めるステップと、
これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができ且つ前記第３クラス及び前記第４クラスの組又は前記第３クラスにより定義されるグループに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するオブジェクト指定ステップと、
を実行させる、記憶媒体。
【請求項１５】
前記オブジェクト指定ステップが、
キャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ前記第３クラスの第３オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとして指定するステップを
含む、請求項１４記載の記憶媒体。
【請求項１６】
オブジェクトのクラスが階層的にレベル分けされているデータ構造において、キャッシュされる順番でｎ番目のレベルｎ以降のレベルに属するクラスの、キャッシュされたオブジェクトをコンピュータに破棄させるプログラムを記憶した記憶媒体であって、
前記プログラムは、前記コンピュータに、
キャッシュされている順番でｎ−１番目のレベルに属するクラスのオブジェクトであって、前記レベルｎに属するクラスのオブジェクトへの参照を有する、前記レベルｎのキー・オブジェクトを検出するステップと、
検出された前記レベルｎのキー・オブジェクトの、前記レベルｎに属するクラスのオブジェクトへの参照を無効化するステップと、
前記レベルｎのキー・オブジェクトから参照をたどることができ且つ前記レベルｎ以上のレベルに属するオブジェクトを破棄するステップと、
を実行させる、記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、オブジェクトのキャッシュ方法に関し、より詳しくは、オブジェクトのクラスが階層的にレベル分けされているデータ構造、及びそのデータ構造におけるオブジェクトのキャッシング、及びキャッシュされたオブジェクトの破棄に関する。
【０００２】
【従来の技術】
インターネットやイントラネットの普及に伴い、計算機の様々なアプリケーション・プログラムも分散環境で実行されるようになってきた。また、アプリケーション・システム開発で設計・分析段階からオブジェクト指向技術が用いられるようになり、実装上、様々なデータがオブジェクトとして表現され、分散計算機上に格納されている。さらに、ネットワーク・コンピュータ（ＮＣ）や携帯型簡易端末に代表されるような、主記憶や計算能力等のリソースに大きな制限を受ける計算機が広く用いられるようになってきた。
【０００３】
このような環境では端末から遠隔計算機に格納されたオブジェクトを使用するのが一般的な実行形態であるが、端末の能力やネットワークの速度を考えると、多数のオブジェクトを処理対象とするような処理プログラムでは、端末側に必要なオブジェクトをキャッシュするのがよい方策である。必要なオブジェクトは、１個のオブジェクトではなく、まとめてアクセスが発生するであろうオブジェクトにより構成されるネットワーク構造単位にキャッシュした方がよい。これは、オブジェクト指向プログラミングの特徴として、（１）オブジェクトに多量のメッセージを送ることによって処理が進められ、メッセージを受けたオブジェクトは自分に関連したオブジェクトにさらにメッセージを送ることが多いこと、（２）さらにこのような処理が繰り返されて、関連し合った多数のオブジェクトにアクセスが行われるためである。
【０００４】
また、データベース内のデータの一部をオブジェクトとして処理の対象とする場合を考えてみる。現実のプログラム開発では、特に過去のデータベース・システムとそのデータベースをそのまま使用する場合が多く、データベース内のデータをそのままオブジェクトとしてアクセスすることはできない。そこで、処理対象となる部分だけをアクセス可能なところへ変換・コピーして処理を行うこととなる。この場合、処理の対象となるのはただ１つのオブジェクトではなく、そのオブジェクトに関連した部分も必要となる。
【０００５】
このようにキャッシュするオブジェクトをどのように決定するかは、端末におけるパフォーマンスを大きく左右する問題である。以下、キャッシュされるオブジェクトの範囲の決定方法についての従来技術について説明する。
【０００６】
Ｊａｖａ（Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社の商標）のオブジェクト・シリアライゼイション（Ｏｂｊｅｃｔ  Ｓｅｒｉａｌｉｚａｔｉｏｎ）では、あるオブジェクトを一つ指定すると、基本的には、それから参照されているすべてのオブジェクトをシリアライズ（ｓｅｒｉａｌｉｚｅ）しようとする。その基本的アルゴリズムは、以下のようなものである。コピー処理の中で、オブジェクトの参照が出てきたときは、それが最初の出現であれば後に参照できるような番号を付した上で再帰的にコピー処理を繰り返す。２度以上出現したオブジェクトへの参照の場合は、最初の時に割り当てた番号をコピーする。このようにして、参照関係でたどられるオブジェクトで構成されるネットワークを完全に送ることができる。
【０００７】
これはもれがない方法であるが、転送量の予測・制御が難しく、大量に連結されたオブジェクトによるネットワーク構造を送る場合には注意が必要となる。Ｊａｖａ  ＲＭＩ（Ｒｅｍｏｔｅ  Ｍｅｔｈｏｄ  Ｉｎｖｏｃａｔｉｏｎ）等では、オブジェクトの参照のうちトランジエント（ｔｒａｎｓｉｅｎｔ）を指定することにより、ある程度の制御を可能にしている。しかし、これはプログラミング時に固定的に指定するものであり、実行時の状況に合わせて動的に変化させることができないので柔軟性に欠ける。
【０００８】
データベースの内容をオブジェクトとして実体化する場合は、データベース・システムのアーキテクチャにも影響されるが、クラスの定義においてローカル・ポインタとグローバル・ポインタを定義することにより、オブジェクトの転送範囲をあらかじめ制御する技術がある（例えば、コンテナ・オブジェクト（福田他，”関係データベース状に構築するオブジェクトサーバーのためのデータモデルとＣ＋＋インターフェース，”  情報処理学会第４５回大会（平成４年後期）（４），ｐ．４−１１１、Ｅｎｔｉｔｙ／Ｄｅｐｅｎｄｅｎｔ  （ＩＢＭ，”Ｓａｎ  Ｆｒａｎｃｉｓｃｏ  Ｐｒｏｊｅｃｔ  Ｔｅｃｈｎｉｃａｌ  Ｓｕｍｍａｒｙ，”  ｈｔｔｐ：／／ｗｗｗ．ｉｂｍ．ｃｏｍ／Ｊａｖａ／Ｓａｎｆｒａｎｓｉｓｃｏ  ）を参照のこと。）。しかし、処理の場面ごとに転送対象や転送範囲を動的に変更することは困難である。
【０００９】
また、クラスタ概念を用いて関連するクラスタ内のオブジェクトをすべてそのまま転送実体化するものもある（例えば、オブジェクトストア（Ｏｂｊｅｃｔ  Ｄｅｓｉｇｎ  Ｉｎｃ．  ”Ｕｓｅｒ  Ｇｕｉｄｅ  ＯｂｊｅｃｔＳｔｏｒｅ  Ｒｅｌｅａｓｅ  ３．０  Ｆｏｒ  ＯＳ／２  ａｎｄ  ＡＩＸ／ｘｌｃ  Ｓｙｓｔｅｍ，”  Ｊａｎ．  １９９４，  ｐｐ．４２−４４）を参照のこと）。この方式では、オブジェクトを２次記憶装置内に生成する場合にクラスタを指定しておく。実装では、２次記憶装置と主記憶のページをクラスタ単位とすることにより、オブジェクトの参照をたどるといった転送におけるＣＰＵの計算を不要にし、より効率的なキャッシュを目指している。しかし、クラスタ内のオブジェクトは無条件に転送されるため、クラスタの構成方法によっては無駄なオブジェクトが転送される可能性がある。特に分散環境で転送時間がかかる場合は通信量が増えてパフォーマンスが落ちる。また、クラスタ単位である程度の制御（キャッシュのポリシーの選択）はできるが、実行時に、特にオブジェクト生成後のオブジェクトのネットワークの変化等の動的な変更に動的に対応できないという欠点がある。
【００１０】
アプリケーション・プログラムやフレームワーク等では、キャッシュについても、それぞれのオブジェクトの設計者がプログラミングするという方法がとられてきた。これは、注意深くプログラミングすれば、かなり柔軟性もあり効果も期待できるものである。しかし、かなり高度なプログラミング技術を必要とし、特にキャッシュの解放では、キャッシュ内の参照関係の一貫性を保持するのは困難である。
【００１１】
先に述べたようなオブジェクトにより構成されるネットワーク構造をキャッシュしている時に、強制的なキャッシュの解放は、オブジェクトの解放そのものの違法、無効なオブジェクトへの違法な参照などを引き起こす原因となる。これは、オブジェクトにより構成されるネットワーク構造同士ではオブジェクトの共有も可能であり、また、あるネットワーク内から別のネットワーク内への参照も自由だからである。よって、一貫性を保持するような特別なガベージコレクションが必要である。
【００１２】
オブジェクトのキャッシュ外へのアクセスの検出については、ハードウエア的あるいはソフトウエア的にアクセスしたことをフックできるようなメカニズムを用いる場合が多い（例えば、オブジェクトストア（Ｏｂｊｅｃｔ  Ｄｅｓｉｇｎ  Ｉｎｃ．  ”Ｕｓｅｒ  Ｇｕｉｄｅ  ＯｂｊｅｃｔＳｔｏｒｅ  Ｒｅｌｅａｓｅ  ３．０  Ｆｏｒ  ＯＳ／２  ａｎｄ  ＡＩＸ／ｘｌｃ  Ｓｙｓｔｅｍ，”  Ｊａｎ．  １９９４，  ｐｐ．９−１１）を参照のこと）。これは、プログラムを実行しているプロセッサからは通常のオブジェクトへの参照を使ってアクセスするだけで特定のルーチンが起動できるもので、通常のプログラムとして特別な記述をする必要がない。
【００１３】
【発明が解決しようとする課題】
以上述べたような、キャッシュするオブジェクトの範囲を決定する手法では、様々な処理の場面に対応してキャッシュ対象オブジェクトを動的に変更することができない。
【００１４】
よって、本発明の目的は、処理の各場面に応じて、キャッシュ対象オブジェクトを動的に変更することができるような方法を提供することである。
【００１５】
また、キャッシュ対象オブジェクトの動的な変更に対してキャッシュ全体の一貫性を保持できるような方法を提供することも目的である。
【００１６】
さらに、キャッシュ対象オブジェクトの動的な変更を実施可能とするデータ構造を提供することも目的である。
【００１７】
また、アプリケーション・プログラムの性質に合わせてキャッシュ対象オブジェクトをカスタマイズすることを可能とすることも目的である。
【００１８】
さらに、キャッシュ対象オブジェクトの動的な計算のコストを、実装可能な範囲に抑えることも目的である。
【００１９】
【課題を解決するための手段】
最初に、キャッシュ対象オブジェクトの動的な変更を実施可能とするデータ構造について説明する。少なくとも、このデータ構造は、データ構造内のオブジェクトのクラスが階層的にレベル分けされている必要がある。このレベルごとにキャッシュするか否かを決定する。また、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへ参照が生じる際にキャッシュすべきオブジェクトを決定するための計算の起点となるルート・オブジェクトのクラスが、各レベルごとに定義される必要もある。
【００２０】
但し、ルート・オブジェクトは、参照元オブジェクトである、１のレベルに属する第１クラスの第１オブジェクト、又は参照先オブジェクトである、他のレベルに属する第２クラスの第２オブジェクトとすることもできる。この際には、キャッシュ対象オブジェクトを決定する際にルート・オブジェクトを検出する処理が簡略化される。
【００２１】
アプリケーション・プログラムを作成する者は、例えば、処理の内容の詳細度に基づき、階層的にレベル分けされたクラスを定義しつつプログラミングすることにより、オブジェクトのキャッシングをより効率化することができる。但し、このデータ構造は、アプリケーション・プログラムを作成する者以外の者が定義してもよい。以下で述べるキャッシュ処理は、アプリケーション・プログラム特有の情報は用いず、且つアプリケーション・プログラム特有のロジックとは独立にキャッシングを行うものである。
【００２２】
さらに、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへの参照が生じる際に第１クラスの第１オブジェクトから直接又は間接的に参照をたどることができるオブジェクトのクラスであって他のレベルに属するクラスのグループを、第１クラス及び第２クラスの組ごと又は第１クラスごとに定義するようにできる。単なるレベルのみならず、特定のクラスに属するオブジェクト間の参照に合わせた、クラスのグループを定義しているので、このグループごとにキャッシュすべきオブジェクトを決定できる。すなわち、よりオブジェクトの参照実態に合わせた、きめ細かいキャッシングを行うことが可能になる。
【００２３】
一方、レベルのみ定義されたデータ構造に基づくオブジェクトをキャッシュする場合には、１のレベルに属する第１クラスの第１オブジェクトから他のレベルに属する第２クラスの第２オブジェクトへ参照が生じたことに応答して、他のレベルに属するクラスを検出するステップと、これまでにキャッシュされておらず且つ第１クラスの第１オブジェクト以降参照をたどることができ且つ他のレベルに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するステップとを実施する。
【００２４】
加えて、他のレベルに属するクラスのオブジェクト及びキャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ第１クラスの第１オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとして指定するステップをさらに実施することも考えられる。キャッシュされるレベルの順番において降順のレベル間の参照が生じた場合のキャッシングを規定している。
【００２５】
さらに、グループ分けも実施されているデータ構造に基づくオブジェクトをキャッシュする場合には、あるレベルに属する第３クラスの第３オブジェクトから他のレベルに属する第４クラスの第４オブジェクトへの参照が生じることに応答して、第３クラス及び前記第４クラスの組又は第３クラスにより定義されるグループを求めるステップと、これまでにキャッシュされておらず且つ第３クラスの第３オブジェクト以降参照をたどることができ且つ第３クラス及び第４クラスの組又は第３クラスにより定義されるグループに属するクラスのオブジェクトを、キャッシュ対象オブジェクトとして指定するステップとを実施する。これにより、特定のクラスに属するオブジェクト間の参照に対応して、より実行状態に即したキャッシングを実行することができる。
【００２６】
加えて、第３クラス及び第４クラスの組又は第３クラスにより定義されるグループに属するクラスのオブジェクト及びキャッシュされるレベルの順番において昇順のレベル間の参照が生じる場合の参照先オブジェクトを除き、これまでにキャッシュされておらず且つ第３クラスの第３オブジェクト以降参照をたどることができるオブジェクトを、キャッシュ対象オブジェクトとして指定するステップをさらに実施することも考えられる。キャッシュされるレベルの順番において降順のレベル間の参照が生じた場合のキャッシングを規定している。
【００２７】
以上のキャッシング方法は、クラスのレベル分け及びグループ分けに基づいて行われる。また、同じクラスでも同一のオブジェクトがキャッシュされるとは限らない。よって、より実行状態又は使用状態に即した動的なキャッシングがなされる。
【００２８】
一方、キャッシュ内のオブジェクトの破棄の方法としては、キャッシュされている順番でｎ−１番目のレベルに属するクラスのオブジェクトであって、レベルｎに属するクラスのオブジェクトへの参照を有する、レベルｎのキー・オブジェクトを検出するステップと、検出されたレベルｎのキー・オブジェクトの、レベルｎに属するクラスのオブジェクトへの参照を無効化するステップと、レベルｎのキー・オブジェクトから参照をたどることができ且つレベルｎ以上のレベルに属するオブジェクトを破棄するステップとを含む。このように、キャッシュされる順番でｎ番目のレベルｎ以降のキャッシュを破棄する場合でも、キャッシュされている順番でｎ−１番目に属するクラスのオブジェクトであって、レベルｎに属するクラスのオブジェクトへの参照を有する、レベルｎのキー・オブジェクトを基準にオブジェクトの破棄を実施すれば、参照関係の一貫性を保つことができる。なお、この方法は、他のプログラムなどから命じられることにより実行される。
【００２９】
以上の述べた方法は、プログラムによって実現することも、専用の装置を用いて実現することも可能である。このように実現形態を変更することは、以下の説明を理解した当業者が通常行うことのできる事項である。さらに、このプログラム及び上記データ構造を、ＣＤ−ＲＯＭやフロッピー・ディスクなどの記憶媒体に格納することは当業者が通常行うことである。
【００３０】
【発明の実施の形態】
本発明が実施されるコンピュータ・システムの一例を図１に示す。このコンピュータ・システムでは、コンピュータ１及び５がネットワーク７にてサーバ９に接続されている。そして、コンピュータ１及びサーバ９にはディスク装置３及び１１が接続されている。コンピュータ１は、サーバ９に接続されたディスク装置１１内のオブジェクトを使用する際に、本発明により決定されるキャッシュ対象オブジェクトを、コンピュータ１内のメインメモリ（図示せず）又はディスク装置３に格納する。また、コンピュータ５のようにディスク装置を有しないコンピュータの場合には、メインメモリ（図示せず）にキャッシュする。また、コンピュータ１は自己に接続されているディスク装置３に格納されたオブジェクトをメインメモリに読み込む場合に本発明を実施してもよい。この際、コンピュータ１はネットワーク７に接続されている必要ない。さらに、コンピュータ１又は５のサーバ９に対する接続は、固定的なネットワークだけでなく、ワイアレスであってもよいし、必要に応じて電話回線にて接続する形式を用いてもよい。
【００３１】
次にサーバ９（コンピュータ１がディスク装置３に記憶されたデータ構造内のオブジェクトをキャッシュする場合にはコンピュータ１）が実行するアルゴリズム及びディスク装置１１（又はディスク装置３）が格納するオブジェクトのデータ構造について、概略を説明する。図２に示したようにオブジェクトのクラスはレベル分けがなされている。例えば、最下層のレベル１のクラスは、全体の中の概要の処理で使用されるオブジェクトのクラス、あるいは、処理全体で一様に広く用いられるオブジェクトのクラスが属するようにする。より上のレベルに属するクラスは、より詳細な処理で使用されるオブジェクトのクラスとする。
【００３２】
図３に示された同心円は処理対象のオブジェクトの集合をレベル別に円で表現したものである。中央の小さな円がレベル１で、順次レベルが上がるごとに外側の円で表される。円の大きさはそのレベルに含まれるオブジェクトの総数も直感的に表している。処理の一番最初の時点では、レベル１のオブジェクトだけがキャッシュされている。
【００３３】
同心円内部に描かれた小円は実際処理を行ったオブジェクトを表す。矢印はオブジェクト間の参照関係で、実際にオブジェクトが活性化されていった順番も表す。また、処理が進むにつれてキャッシュされるオブジェクトの集合をハッチングで表している。処理が進むと、レベル１のあるオブジェクトのさらに詳細な処理を行うためにレベル２の一部のオブジェクトが活性化される。同様に、レベル２のあるオブジェクトのさらに詳細な処理を行うためにレベル３の一部のオブジェクトが活性化される。
【００３４】
次の詳細な処理に移るタイミングを知るために、キーとなるオブジェクトが一つ前のレベルのキャッシュに存在している。これを、アクセスされるオブジェクトが属するレベルのキー・オブジェクトと呼ぶ。図３中においては、黒丸小円で表されている。ここでは、同時に次のレベル（アクセスされるオブジェクトが属するレベル）のキャッシュ対象を計算する際に出発点となるものでもある。この出発点となるオブジェクトをルート・オブジェクトと呼ぶが、一般的にはキー・オブジェクトとルート・オブジェクトは同一でなく、ルート・オブジェクトはアプリケーション・プログラム固有の意味情報を用いて設定することも可能である。
【００３５】
このキー・オブジェクトから次のレベルのオブジェクトへのアクセスが発生したときに、キャッシュ対象オブジェクトの計算が始まる。すなわち、ルート・オブジェクトからたどることができる、そのレベルのクラスのオブジェクトを収集する。図３の例では、レベル３のキー・オブジェクトであり且つルート・オブジェクトでもあるオブジェクトａからレベル３のオブジェクトｂへアクセスがあった場合には、オブジェクトａからたどることができるレベル３のオブジェクトｂ，ｃ，ｄ，ｅがキャッシュ対象オブジェクトとして指定される。
【００３６】
なお、オブジェクト間のアクセス・パターンによって、クラスの集合であるレベルをさらに細かく分けることも可能である。これは、同じレベルの処理であっても複数の種類が存在する場合に対応するためである。図３の例では、オブジェクトｂ，ｃ，ｄ，ｅをオブジェクトａ及びｂにより指定されたグループとして、レベル分けとは別に定義することができる。
【００３７】
キャッシュの一部を破棄する場合は、このレベル単位に行う。すなわち、あるレベルとそのレベルより大きいレベルに属するクラスのオブジェクトを解放する。あるレベルより上のレベルを残したまま、当該あるレベルを解放することはできない。これは、レベルが処理の詳細度を表していることを考えれば自然である。実際に破棄する場合には、あるレベルのキー・オブジェクトをすべて集め、そこからたどることができるオブジェクトで、このレベルより上のクラスのオブジェクトを全て解放すればよい。オブジェクトの解放による参照ポインタの無効化は、このレベルのキー・オブジェクトのみに注目すればよい。キャッシュ全体のガベージ・コレクションなどの処理は不要である。図３の例でレベル３以上を破棄する場合、レベル３のキー・オブジェクトａ，ｆ，ｇを集めて、これらのキー・オブジェクトａ，ｆ，ｇからたどることができるオブジェクトｂ，ｃ，ｄ，ｅを破棄する。さらに、キー・オブジェクトａ，ｆ，ｇの参照ポインタを無効化する。
【００３８】
以上の本発明の概要を踏まえて、以下、本発明の詳細を説明する。最初に、いくつかの定義及び表記法を述べる。
【００３９】
（１）クラスの表記
クラスはＣ、Ｃｉのように表す。ここで下付ｉはクラスの番号を表す。後で用いるが、上付文字はクラスが属するレベルの番号を表す。
（２）オブジェクトの表記
オブジェクトはＯ、Ｏｉのように表す。下付及び上付の意味はクラスと同じである。また、Ｏの属するクラスをＣｌａｓｓ（Ｏ）のように表す。
（３）その他
オブジェクトＯｉがＯｊへの参照を有する時、Ｏｉ→Ｏｊと表す。同じ表記でプログラム実行中にＯｉの中からＯｊを参照したというアクセス・パターンをも表す。クラスＣｉからクラスＣｊへ参照がある場合には、Ｃｉ→Ｃｊと表す。特に、Ｃｌａｓｓ（Ｏｉ）＝Ｃｉ，Ｃｌａｓｓ（Ｏｊ）＝Ｃｊならば、Ｏｉ→Ｏｊ⇔Ｃｉ→Ｃｊである。
さらに間接的に参照をたどることができる場合には、Ｃｉ→＊Ｃｊ（閉包：参照先を参照元が含む）、Ｃｉ→＋Ｃｊ（正の閉包：参照先を参照元が含まない）と表す。特に途中の経路を指定する場合には、Ｃｉ｛→Ｃｋ｝＊→Ｃｊ，Ｃｉ｛→Ｃｋ｝＋→Ｃｊなどと表す。
【００４０】
Ａ．データ構造の定義
では、キャッシュされるオブジェクトのデータ構造の定義を行う。
Ｌｅｖｅｌ（１）は、最初の処理でキャッシュされるオブジェクトのクラスの集合である。これをＬｅｖｅｌ（１）＝｛Ｃ１１，Ｃ２１，Ｃ３１，．．．｝と表す。ここで、レベル１のルート・オブジェクトをＯｒｏｏｔとすると、プログラム実行開始時にはＯｒｏｏｔからたどることができるＣｉ１（ｉ＝１，．．．．）のインスタンスすべてがキャッシュされる。どのクラスをＬｅｖｅｌ（１）に入れるかは、アプリケーション・プログラムの性質によってアプリケーション・プログラムの設計者が任意に指定することができる。
【００４１】
Ｌｅｖｅｌ（ｎ）はレベルｎに属するクラスの集合である。レベルｎ−１に属するクラスの中でレベルｎのオブジェクトへ参照を有するオブジェクトのクラスを、Ｋｅｙ（ｎ）とする。これを記号で表すと、以下のようになる。
【数１】
0003627055.tif 000002
このＫｅｙ（ｎ）のクラスのオブジェクトを、キー・オブジェクトという。
【００４２】
キー・オブジェクトからの任意のアクセス・パターンＣｉｎ−１→Ｃｊｎ（Ｃｉｎ−１はキー・オブジェクトのクラスであって、Ｃｊｎはレベル１からｎ−１のレベルに属するクラスではない）に対して、
Ｇｒｏｕｐ（Ｃｉｎ−１→Ｃｊｎ）＝｛Ｃｊｎ，Ｃｉｊ１ｎ，Ｃｉｊ２ｎ，．．．｝
関数ｆｇｅｔＲｏｏｔ（Ｃｉｎ−１→Ｃｊｎ）→Ｃｉｊ−ｒｏｏｔ
を設計・定義することもできる。これは、アクセス・パターンＣｉｎ−１→Ｃｊｎ（両クラスに属するオブジェクト間のアクセス）が実行時に起きた時に、ｆｇｅｔＲｏｏｔ関数で決まるルート・オブジェクトＣｉｊ−ｒｏｏｔからたどることができるＣｊｎ，Ｃｉｊ１ｎ，Ｃｉｊ２ｎ，．．．をＧｒｏｕｐとして定義している。ルート・オブジェクトは、Ｃｊｎ，Ｃｉｊ１ｎ，Ｃｉｊ２ｎ，．．．にたどることができ、且つレベルｎ−１に属するクラスのオブジェクト又はキー・オブジェクトから参照されるオブジェクトに限定される。これを記号で表すと、以下のようになる。
【数２】
0003627055.tif 000003
【数３】
0003627055.tif 000004
なお、Ｌｅｖｅｌ（ｎ）は以下のように定義し直すこともできる。
【数４】
0003627055.tif 000005
【００４３】
これをＫｅｙ（ｎ）＝φとなるまで繰り返すことにより、データ構造Ｌｅｖｅｌ（ｎ）（ｎ≧２）及び｛Ｌｅｖｅｌ（１），Ｇｒｏｕｐ（Ｃｉ１→Ｃｊ２），．．．Ｇｒｏｕｐ（Ｃｉｎ−１→Ｃｊｎ）｝及び関数ｆｇｅｔＲｏｏｔ及びＫｅｙ（ｎ）を設計・定義することができる。これらは、次に述べるキャッシュ対象オブジェクトを決定する際に用いられる。
【００４４】
なお、Ｇｒｏｕｐ（Ｃｉｎ−１→Ｃｊｎ）は実際のアプリケーション・プログラムでは、アクセス・パターンによらず一定のクラス集合にしたり（Ｇｒｏｕｐを定義しない）、キー・オブジェクトのクラスだけで与えること（Ｇｒｏｕｐ（Ｃｉｎ−１））なども考えられる。同様に、ｆｇｅｔＲｏｏｔ関数も、キー・オブジェクトやその参照先オブジェクトのクラスをそのまま値とするならば、後の処理は簡単化される。
【００４５】
ここで設計・定義されたデータ構造は、例えば図１のサーバ９のディスク装置１１又はコンピュータ１のディスク装置３に記憶される。さらに、携帯可能な記憶装置に記憶される場合もある。
【００４６】
Ｂ．キャッシュの制御アルゴリズム
キャッシュの制御アルゴリズムは、（１）処理の最初にＬｅｖｅｌ（１）をキャッシュする部分の処理、（２）レベルｎの処理中にキャッシュ内でアクセス・パターンＯｎ→Ｏｎ＋１が生じた時に新たにキャッシュを追加する部分の処理、（３）使わなくなったキャッシュを破棄する部分の処理、を含む。（１）の部分の処理は、レベル１のルート・オブジェクトをＯｒｏｏｔとすると、プログラム実行開始時にはＯｒｏｏｔからたどることができるＣｉ１（ｉ＝１，．．．．）のインスタンスすべてがキャッシュされることとして、説明を省略する。この他にキャッシュの一貫性管理のメカニズムも必要であるが、キャッシュ内容を元データへ更新する場合には、オブジェクト単位で行えばよく、従来の手法がそのまま使えるので説明は省略する。
【００４７】
（２）レベルｎの処理中にキャッシュ内でアクセス・パターンＯｎ→Ｏｎ＋１が生じた時に新たにキャッシュを追加する部分の処理
ここでは、既にレベルｎまではキャッシュされているとする。以下、Ｏｎ→Ｏｎ＋１というアクセスが発生した時、キャッシュ対象オブジェクトの決定アルゴリズムを図４及び図５を用いて説明する。
【００４８】
（イ）Ｏｎ→Ｏｎ＋１及びｆｇｅｔＲｏｏｔ関数を用いて、対応するルート・オブジェクトＯｒとキャッシュするクラスの集合Ｇｒｏｕｐ（Ｃｉｎ→Ｃｊｎ＋１）を求める（ステップ１１０）。なお、データ構造によっては、Ｇｒｏｕｐ（Ｃｉｎ→Ｃｊｎ＋１）が定義されておらず、Ｌｅｖｅｌ（ｎ＋１）又はＧｒｏｕｐ（Ｃｉｎ）が定義されている場合もあるが、その場合には定義してあるクラスの集合を使用する。また、アプリケーション・プログラム固有の性質を用いてＯｒを定義している場合はそれを用い、そうでない場合にはＯｒ＝Ｏｎ又はＯｒ＝Ｏｎ＋１であるからＯｒは簡単に求められる。
【００４９】
（ロ）Ｏｒから参照をたどっていって得られる、Ｇｒｏｕｐ（Ｃｉｎ→Ｃｊｎ＋１）のクラスのオブジェクトＯすべてを出発オブジェクトとしてｄｏＣｏｐｙ（Ｏ）を実行する（ステップ１２０）。ｄｏＣｏｐｙ（Ｏ）は図５を用いて説明する。Ｇｒｏｕｐ（Ｃｉｎ→Ｃｊｎ＋１）のクラスのオブジェクトであっても、Ｏｒから参照をたどっていかれないオブジェクトも一般的には存在するので、そのようなオブジェクトは出発オブジェクトではない。オブジェクトＯは以下のように定義される。
Ｃｌａｓｓ（Ｏｒ）＝Ｃｊｎ＋１の時
Ｏ＝Ｏｒ
それ以外の時Ｏは以下の式を満たすようなものである。すなわち、
Ｏｒ｛→Ｏ’｝＊→∀Ｏ且つＣｌａｓｓ（Ｏ’）∈Ｌｅｖｅｌ（ｎ）且つ
Ｃｌａｓｓ（Ｏ）∈Ｌｅｖｅｌ（Ｃｉｎ→Ｃｊｎ＋１）
【００５０】
なお、キャッシュ対象オブジェクトの集合をＡｃｔｉｖａｔｅｄｎ（Ｏｎ→Ｏｎ＋１）とし、最初はＡｃｔｉｖａｔｅｄｎ（Ｏｎ→Ｏｎ＋１）＝φとしておく。なお、ｄｏＣｏｐｙ（Ｏ）（図５）は再帰的に行われる。
【００５１】
（ハ）ｄｏＣｏｐｙ（Ｏ）では、最初にオブジェクトＯが既にキャッシュされるいるかどうか判断する（ステップ２１０）。オブジェクトＯが既にキャッシュされている場合には、元の処理に戻る（ステップ２７０）。一方、オブジェクトＯがまだキャッシュされていない場合には、オブジェクトＯをＡｃｔｉｖａｔｅｄｎ（Ｏｎ→Ｏｎ＋１）に追加する。そして、Ｏの参照先オブジェクトＯｄに対し、ステップ２４０以下を実施する（ステップ２３０）。よって、オブジェクトＯの参照先オブジェクトＯｄをすべて処理したか否か判断する。すべての参照先オブジェクトＯｄを処理したならば、元の処理に戻る。
【００５２】
もし、処理していない参照先オブジェクトＯｄがある場合には、（ａ）ＯｄのクラスはＧｒｏｕｐ（Ｃｉｎ→Ｃｊｎ＋１）のメンバであるか、又は（ｂ）ＯｄのクラスはＬｅｖｅｌ（ｋ）（１≦ｋ≦ｎ）に属しており且つ参照元オブジェクトＯがキー・オブジェクトではないか、ということが判断される（ステップ２４０）。もし、（ａ）又は（ｂ）の条件を満たす場合には、ｄｏＣｏｐｙ（Ｏｄ）を実行する（ステップ２５０）。そして、ＯからＯｄへの参照を記録しておく。なお、このｄｏＣｏｐｙ（Ｏｄ）は、参照先オブジェクトＯｄのさらに参照先オブジェクトについて処理していく点に注意が必要である。（ａ）の条件は、
【数５】
0003627055.tif 000006
（ｂ）の条件は、
【数６】
0003627055.tif 000007
と記載できる。（ｂ）の条件は、レベル間の参照が遡る形で生じた場合に過剰なキャッシュを防止するのに必要な条件である。
【００５３】
もし、ステップ２４０のいずれの条件をも満たしていない場合には、結果的に参照先オブジェクトＯｄのクラスがＬｅｖｅｌ（ｎ＋２）のメンバであるか又は参照元オブジェクトが１以上ｎ＋１以下のレベルのキー・オブジェクトであるから、Ｏｄ及びその先のオブジェクトをキャッシュ対象オブジェクトとして指定しない。但し、ＯからＯｄへのアクセスが生じた時には、図４及び図５の処理を起動できるように、ｄｏＳｅｔＰｒｏｘｙ（Ｏ→Ｏｄ）で、参照関係を登録しておく（ステップ２６０）。
【００５４】
このようにして、全ての出発オブジェクトＯについて再帰的にｄｏＣｏｐｙ（Ｏ）を実施すれば、図４の処理を終了する。そして、Ａｃｔｉｖａｔｅｄｎ（Ｏｎ→Ｏｎ＋１）のキャッシュ対象オブジェクトをキャッシュする。
【００５５】
ここで、ｄｏＣｏｐｙ（Ｏ）の処理の例を示しておく。Ｌｅｖｅｌ（２）＝｛Ａ，Ｂ｝，Ｌｅｖｅｌ（３）＝｛Ｃ｝であって、クラスＡのオブジェクトをａ１，ａ２，ａ３，．．．．、クラスＢのオブジェクトをｂ１，ｂ２，ｂ３，．．．．、クラスＣのオブジェクトをｃ１，ｃ２，ｃ３，．．．．とする。参照関係は図７に示したようにａ１→ｃ１→ｃ２→ｂ１→ａ２→ｂ２→．．．．となっているとする。ここで、ｋｅｙ（３）＝｛Ａ｝とする。最初に、図７のハッチング分、すなわちオブジェクトａ１がキャッシュされているとする。
【００５６】
その後、ａ１→ｃ１というアクセスが発生すると、図４の処理が起動され（ここではｃ１がルート・オブジェクトであるとする）、最初にｄｏＣｏｐｙ（ｃ１）が呼ばれる。
【００５７】
１．最初の実行（ｄｏＣｏｐｙ（ｃ１））
ｃ１がキャッシュ対象オブジェクトとされる（ステップ２２０）。そして、ｃ１の参照先オブジェクトｃ２はステップ２３０の最初の条件を満たすので、ｄｏＣｏｐｙ（ｃ２）が呼ばれる。
２．一度目の再帰実行（ｄｏＣｏｐｙ（ｃ２））
ｃ２がキャッシュ対象オブジェクトとされる。そして、ｃ２の参照先オブジェクトｂ１はクラスＢのオブジェクトであるのでＬｅｖｅｌ（３）のオブジェクトではなく、ステップ２３０の最初の条件を満たさない。しかし、クラスＢはｌｅｖｅｌ（２）のクラスであって、参照元オブジェクトｃ２のクラスＣがｋｅｙ（３）＝｛Ａ｝ではないので、二番目の条件を満たす。よって、ｄｏＣｏｐｙ（ｂ１）が呼ばれる。
【００５８】
３．ニ度目の再帰実行（ｄｏＣｏｐｙ（ｂ１））
ｂ１がキャッシュ対象オブジェクトとされる。そして、ｂ１の参照先オブジェクトａ２のクラスＡはＬｅｖｅｌ（２）であるので、Ｌｅｖｅｌ（３）のオブジェクトではなく、ステップ２３０の最初の条件を満たさない。しかし、クラスＡはＬｅｖｅｌ（２）のクラスであって、参照元オブジェクトｂ１のクラスＢがｋｅｙ（３）＝｛Ａ｝でないので、二番目の条件を満たす。よって、ｄｏＣｏｐｙ（ａ２）が呼ばれる。
４．三度目の再帰実行（ｄｏＣｏｐｙ（ａ２）
ａ２がキャッシュ対象オブジェクトとされる。そして、ａ２の参照先オブジェクトｂ２のクラスＢはＬｅｖｅｌ（２）であるので、Ｌｅｖｅｌ（３）のオブジェクトではなく、ステップ２３０の最初の条件を満たさない。加えて、クラスＢはＬｅｖｅｌ（２）のオブジェクトであるが、参照元オブジェクトａ２のクラスＡがｋｅｙ（３）＝｛Ａ｝であるから、二番目の条件も満たさない。よって、ステップ２６０に遷移してｄｏＳｅｔＰｒｏｘｙ（ａ２→ｂ２）がセットされてステップ２５０を終了する。
【００５９】
（１）及び（２）の処理は、図１のサーバ９が実行する処理である。但し、コンピュータ１がディスク装置３からキャッシュする場合には、コンピュータ１が実行する。
【００６０】
（３）使わなくなったキャッシュを破棄する部分の処理
キャッシュの破棄も、基本的にはレベルごとに行う。但し、レベルｎとそれより上位のレベルのオブジェクトを全て破棄することになる。破棄しようとするレベルより高いレベルをキャッシュに残したまま、そのレベルを破棄することは、参照の一貫性などの理由で不可能である。破棄するタイミング及びレベルの選択はアプリケーション・プログラムによって異なり、他のプログラムにて決定する。
【００６１】
ここではレベルｎ以上のオブジェクトを破棄する場合を説明する（図６）。最初に、レベルｎの全てのキー・オブジェクトＯｋｅｙｎ−１を求める（ステップ３１０）。ここでキー・オブジェクトの定義をおさらいしておくと、キー・オブジェクトは、レベルｎのオブジェクトに参照を有するレベルｎ−１のクラスのオブジェクトである。よって、レベルｎのキー・オブジェクトはレベルｎ−１のオブジェクトである。そして、Ｏｋｅｙｎ−１からレベルｎのオブジェクトへの参照をｄｏＳｅｔＰｒｏｘｙにセットする（ステップ３２０）。すなわち、次に、Ｏｋｅｙｎ−１からレベルｎのオブジェクトへの参照があった場合に、図４及び図５の処理を起動するように登録する。また、キャッシュ内の参照を無効にする。最後に、Ｏｋｅｙｎ−１からたどることができるすべてのオブジェクトでレベルｎ以上のものだけを解放する（ステップ３３０）。
【００６２】
以上のように、キー・オブジェクトからたどることのできる参照がきちんと処理されれば、キャッシュ内の参照関係の一貫性は保たれる。すなわち、有効なオブジェクトから解放されたオブジェクトへの参照が生じることはない。但し、どこからも参照されることのない、レベルｎ未満のオブジェクトが残る可能性はあるが、通常のガベージ・コレクションで問題なく処理できる。
【００６３】
（３）の処理は、コンピュータ１（又はコンピュータ３）が実行する。
【００６４】
ここまで定義してきたクラスは必ずしもプログラミング言語上のクラスに一致するとは限らない。本方式でいうクラスはあくまでもそのインスタンスの個数がキャッシュ対象として意味があるようなものを考えている。しかし、現実には、Ｌｅｖｅｌ（１）を除いて一般的なクラスと一致させても問題はないことが多い。Ｌｅｖｅｌ（１）に関しては、一般的なクラスとは別の指定方法を使用した方がよい場合もある。
【００６５】
【実施例】
図８のようなクラス階層を考える。クラスＡには１００個のオブジェクトが存在し、Ａのオブジェクト１つにＢのオブジェクト１００個、Ｂのオブジェクト１つにＣのオブジェクト１００個がつながっているとする。このようなクラス階層の全オブジェクト数は１００万個を超えるので、全てを一時にキャッシュするのは現実的ではない。ここで、キャッシュを必要とする処理として、Ａのオブジェクトのみを対象に処理するＰａ、Ａのオブジェクト１個とそれから得られる全てのＢのオブジェクトを処理するＰｂ、Ａ，Ｂのオブジェクト１個ずつとそれから得られるすべてのＣのオブジェクトを処理するＰｃという３つの処理を考える。
【００６６】
そうすると、以下のようなデータ構造を決定することができる。
Ｌｅｖｅｌ（１）＝｛Ａ｝
ｋｅｙ（２）＝｛Ａ｝，Ｌｅｖｅｌ（２）＝｛Ｂ｝，ｆｇｅｔＲｏｏｔ（ａ→ｂ）＝ａ
ｋｅｙ（３）＝｛Ｃ｝，Ｌｅｖｅｌ（３）＝｛Ｃ｝，ｆｇｅｔＲｏｏｔ（ｂ→ｃ）＝ｂ
（Ｃｌａｓｓ（ａ）＝Ａ，Ｃｌａｓｓ（ｂ）＝Ｂ，Ｃｌａｓｓ（ｃ）＝Ｃ）
【００６７】
実行時には、まずＰａ処理が行われるので、Ｌｅｖｅｌ（１）に相当するＡのオブジェクトがすべてキャッシュされる。すなわち１００個のＡのオブジェクトのみがキャッシュされる。処理がＰｂに移った時、あるＡのオブジェクトａがＢのオブジェクトｂにアクセスした場合、Ｌｅｖｅｌ（２）のキャッシュＡｃｔｉｖａｔｅｄ２（ａ→∀ｂ）が新たにキャッシュされる。同様にＰｃの処理に移った時もＡｃｔｉｖａｔｅｄ３（ｂ→∀ｃ）がキャッシュされる。この時点で、キャッシュに存在するオブジェクトの数は３００個であり適当な数である。
【００６８】
また図８のようなクラス階層で、まったく別のアクセス・パターンとなる処理を考える。すなわち、ＡのオブジェクトａからＢのオブジェクトｂをアクセスした時に始まる処理Ｐ’ｂは、ＢからたどることができるＣのクラスのオブジェクトをも処理対象とする。これは、最初の例が広さ優先のアクセス・パターンでオブジェクトのネットワークを処理していたのに対し、深さ優先のアクセス・パターンによる処理になったものである。このとき、データ構造は以下のように定義しなおされる。
【００６９】
Ｌｅｖｅｌ（１）＝｛Ａ｝
Ｋｅｙ（２）＝｛Ａ｝，Ｌｅｖｅｌ（２）＝｛Ｂ，Ｃ｝，ｆｇｅｔＲｏｏｔ（ａ→ｂ）＝ｂ
【００７０】
これによりｂをアクセスした時点で、ｂからたどることができるＣのオブジェクトがすべてキャッシュされる。これで、この処理で必要十分なオブジェクトがキッッシュされる。なお、Ｂのオブジェクトにアクセスした時点で、２０１個のオブジェクトがキャッシュされる。
【００７１】
さらに、別のキャッシュ方略として、ＡのオブジェクトからＢ，及びＢからＣはそれぞれ１つの処理の中では一つしかキャッシュしないとする。ＡからＢへアクセスした段階では、その先のＣオブジェクト１００個のうちどの一つをキャッシュすればよいかは、アプリケーション・プログラムの処理内容を解析せずに知るのは不可能である。よって、このアクセスではＢ一個のみのレベルがキャシュされる。ＢからＣへアクセスした時点では、次のレベルのキャッシュとしてＣのオブジェクトが１個キャッシュされる。このときのデータ構造は以下のとおりである。
【００７２】
Ｌｅｖｅｌ（１）＝｛Ａ｝
Ｋｅｙ（２）＝｛Ａ｝，Ｌｅｖｅｌ（２）＝｛Ｂ｝，ｆｇｅｔＲｏｏｔ（ａ→ｂ）＝  ｂ
Ｋｅｙ（３）＝｛Ｂ｝，Ｌｅｖｅｌ（３）＝｛Ｃ｝，ｆｇｅｔＲｏｏｔ（ａ→ｂ）＝  ｂ
【００７３】
Ｃがアクセスされた段階で、１０２個のオブジェクトがキャッシュされることになる。
【００７４】
これらの例において注目すべきは、アプリケーション・プログラム内容はもちろんのこと、キャッシュ・アルゴリズムを変更することなく、データ構造を変更することにより複数のキャッシュ方略を可能にしている点である。このことは、本発明を用いれば、アプリケーション固有の性質に合わせて自由にキャッシュ方式を設計可能であり、また、アプリケーション・プログラム開発後にパフォーマスンス・チューニングが容易に行うことができることができるということを意味している。
【００７５】
【効果】
処理の各場面に応じて、キャッシュ対象オブジェクトを動的に変更することができるような方法を提供することができた。
【００７６】
また、キャッシュ対象オブジェクトの動的な変更に対してキャッシュ全体の一貫性を保持できるような方法を提供することもできた。
【００７７】
さらに、キャッシュ対象オブジェクトの動的な変更を実施可能とするデータ構造を提供することもできた。
【００７８】
また、アプリケーション・プログラムの性質に合わせてキャッシュ対象オブジェクトをカスタマイズすることを可能とする方法を提供することもできた。
【００７９】
さらに、キャッシュ対象オブジェクトの動的な計算のコストを、実装可能な範囲に抑えることもできた。
【図面の簡単な説明】
【図１】本発明が実施されるコンピュータ・システムの一例である。
【図２】本発明の階層的なデータ構造の一例を示す図である。
【図３】本発明を用いたキャッシングの様子の一例を示す図である。
【図４】キャッシュ対象オブジェクトの選択アルゴリズムを表す図である。
【図５】図４の中で用いられるｄｏＣｏｐｙ（Ｏ）のアルゴリズムを表す図である。
【図６】キャッシュ破棄アルゴリズムを表す図である。
【図７】ｄｏＣｏｐｙ（Ｏ）のアルゴリズムの説明のためのデータ構造を表す図である。
【図８】実施例を説明するためのクラス階層を表す図である。
【符号の説明】
１  コンピュータ
３  ディスク装置
５  コンピュータ
７  ネットワーク
９  サーバ
１１  ディスク装置
【図１】
0003627055.tif 000008
【図２】
0003627055.tif 000009
【図３】
0003627055.tif 000010
【図４】
0003627055.tif 000011
【図５】
0003627055.tif 000012
【図６】
0003627055.tif 000013
【図７】
0003627055.tif 000014
【図８】
0003627055.tif 000015