(57)【特許請求の範囲】
【請求項１】
再利用される可能性が高いキャッシュバッファを管理する第一管理手段と、
再利用される可能性が低いキャッシュバッファを管理する第二管理手段と、
利用し終わったデータを利用した処理の種類に応じて、前記利用し終わったデータが入っているキャッシュバッファを前記第一管理手段と前記第二管理手段との何れに管理させるかを判断する判断手段と、
前記判断手段の判断結果に基づき、前記利用し終わったデータが入っているキャッシュバッファを、前記第一管理手段と前記第二管理手段との何れかに振り分ける振り分け手段と、
新たにデータを読み込むためのキャッシュバッファが足りないときに、データを破棄するキャッシュバッファとして、前記第二管理手段で管理されているキャッシュバッファを選択する選択手段と、
を有する情報処理装置。
【請求項２】
前記判断手段は、前記利用し終わったデータを利用した処理の種類がディレクトリの空き領域を探索する処理であって、空き領域があった場合、前記利用し終わったデータが入っているキャッシュバッファを前記第一管理手段で管理させると判断し、空き領域がなかった場合、前記利用し終わったデータが入っているキャッシュバッファを前記第二管理手段で管理させると判断する請求項１に記載の情報処理装置。
【請求項３】
前記判断手段は、前記利用し終わったデータを利用した処理の種類がFAT(File Allocation Table)の空きクラスタを探索する処理であって、空きクラスタがあった場合、前記利用し終わったデータが入っているキャッシュバッファを前記第一管理手段で管理させると判断し、空きクラスタがなかった場合、前記利用し終わったデータが入っているキャッシュバッファを前記第二管理手段で管理させると判断する請求項１に記載の情報処理装置。
【請求項４】
前記判断手段は、前記利用し終わったデータを利用した処理の種類がFAT(File Allocation Table)の空きクラスタの数を数え上げる処理である場合、前記利用し終わったデータが入っているキャッシュバッファを前記第二管理手段で管理させると判断する請求項１に記載の情報処理装置。
【請求項５】
情報処理装置が実行する情報処理方法であって、
再利用される可能性が高いキャッシュバッファを管理する第一管理ステップと、
再利用される可能性が低いキャッシュバッファを管理する第二管理ステップと、
利用し終わったデータを利用した処理の種類に応じて、前記利用し終わったデータが入っているキャッシュバッファを前記第一管理ステップと前記第二管理ステップとの何れに管理させるかを判断する判断ステップと、
前記判断ステップの判断結果に基づき、前記利用し終わったデータが入っているキャッシュバッファを、前記第一管理ステップと前記第二管理ステップとの何れかに振り分ける振り分けステップと、
新たにデータを読み込むためのキャッシュバッファが足りないときに、データを破棄するキャッシュバッファとして、前記第二管理ステップで管理されているキャッシュバッファを選択する選択ステップと、
を含む情報処理方法。
【請求項６】
コンピュータに、
再利用される可能性が高いキャッシュバッファを管理する第一管理ステップと、
再利用される可能性が低いキャッシュバッファを管理する第二管理ステップと、
利用し終わったデータを利用した処理の種類に応じて、前記利用し終わったデータが入っているキャッシュバッファを前記第一管理ステップと前記第二管理ステップとの何れに管理させるかを判断する判断ステップと、
前記判断ステップの判断結果に基づき、前記利用し終わったデータが入っているキャッシュバッファを、前記第一管理ステップと前記第二管理ステップとの何れかに振り分ける振り分けステップと、
新たにデータを読み込むためのキャッシュバッファが足りないときに、データを破棄するキャッシュバッファとして、前記第二管理ステップで管理されているキャッシュバッファを選択する選択ステップと、
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
ファイルシステムは、通常キャッシュバッファと呼ばれる記憶領域を利用する。アプリケーションからのファイル読み込み要求があった場合、ＣＰＵは、以下の処理を行う。つまり、ＣＰＵは、該当するファイルのデータをハードディスクやメモリカード等の二次記憶装置からセクタ単位でキャッシュバッファに転送し、次に要求されただけのデータをキャッシュバッファからアプリケーションの指定したメモリ領域に転送する。キャッシュバッファの内容はできるだけ保持され、アプリケーションから再び同じデータの読み込み要求があった場合、ＣＰＵは、二次記憶装置からの転送を省略し、キャッシュバッファのデータからアプリの指定するメモリ領域に転送する。これによって動作の遅い二次記憶装置へのアクセスを減らすことができ、速度向上に効果的である。
また、アプリケーションからファイルへの書き込み要求があった場合、ＣＰＵは、アプリケーションの指定したデータをキャッシュバッファに転送し、次に二次記憶装置に転送する。キャッシュバッファから二次記憶装置への実際のデータ転送は遅らせることができる。二次記憶装置へ転送する前にアプリケーションから同じデータの上書き要求があったときは、ＣＰＵは、キャッシュバッファのデータだけを変更し、最後の変更結果のみを二次記憶装置に転送することで二次記憶装置へのアクセスを減らすことができる。
また、ファイルシステムにはファイルにアクセスするために必要なディレクトリエントリ・ＦＡＴ・ｉｎｏｄｅといったメタデータが存在する。ＣＰＵは、メタデータを読み込んだり書き込んだりするときにも、一度、キャッシュバッファにメタデータを転送し、キャッシュバッファ上のメタデータにアクセスする。
このように、ＣＰＵは、キャッシュバッファに一度転送したデータはなるべく捨てずに保持しておき、キャッシュバッファを全て使い切って足りなくなったときに初めて古いデータを捨てる。そして、ＣＰＵは、空いたキャッシュバッファの領域を新しいデータの為に使うことで、ファイルアクセスを効率的に実現している。
このときに入れ替えるキャッシュバッファを選択するためによく使われているアルゴリズムがＬＲＵである。ＬＲＵは、最後に使われてから最も長い時間が経ったキャッシュバッファを選択する。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−１２２９２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ディスク全体の空き容量を計測する場合、スペースビットマップやアロケーションビットマップ、ファイルアロケーションテーブル等のディスク領域の割り当て状況を示すメタデータを先頭から末尾まで全部検査して空き領域の数を数える処理が行われる。ＣＰＵは、この処理を行うためにディスク領域の割り当て状況を示すメタデータを大量に読み込むが、後に同じメタデータが近い将来利用される可能性は低い。
また、ＣＰＵは、ファイルを書き込むためにディスク領域を新たに割り当てる場合も、空き領域を探すためにディスク領域の割り当て状況を示すメタデータを読み込む。しかしながら、空き領域がなかなか見つからない場合は空き領域が見つかるまで大量にメタデータの読み込みが発生する。この場合も、空き領域がなかったメタデータは近い将来再び利用される可能性は低い。
また、ファイルを作成するためにディレクトリの空き領域を探す場合、ＣＰＵは、ディレクトリを表すメタデータを先頭から順に参照して空き領域を探す。しかしながら、空き領域がなかなか見つからない場合は大量にメタデータの読み込みが発生する。この場合も空き領域がなかったメタデータは近い将来再び利用される可能性は低い。
このように再利用性の低いメタデータが大量に読み込まれると、それまでキャッシュバッファに入っていた再利用性の高いデータがキャッシュバッファから追い出されてしまい、キャッシュバッファの利用効率が下がる問題があった。
【０００５】
本発明はこのような問題点に鑑みなされたもので、再利用性の低いデータによってそれまでキャッシュバッファに入っていたデータが追い出されることを防ぎ、限られた資源であるキャッシュバッファを有効に活用することを目的とする。
【課題を解決するための手段】
【０００６】
そこで、本発明の情報処理装置は、再利用される可能性が高いキャッシュバッファを管理する第一管理手段と、再利用される可能性が低いキャッシュバッファを管理する第二管理手段と、利用し終わったデータを利用した処理の種類に応じて、前記利用し終わったデータが入っているキャッシュバッファを前記第一管理手段と前記第二管理手段との何れに管理させるかを判断する判断手段と、前記判断手段の判断結果に基づき、前記利用し終わったデータが入っているキャッシュバッファを、前記第一管理手段と前記第二管理手段との何れかに振り分ける振り分け手段と、新たにデータを読み込むためのキャッシュバッファが足りないときに、データを破棄するキャッシュバッファとして、前記第二管理手段で管理されているキャッシュバッファを選択する選択手段と、を有する。
【発明の効果】
【０００７】
本発明によれば、再利用性の低いデータによってそれまでキャッシュバッファに入っていた再利用性の高いデータが追い出されることを防ぎ、限られた資源であるキャッシュバッファを有効に活用することができる。
【図面の簡単な説明】
【０００８】
【図１】情報処理装置（コンピュータ）１のハードウェア構成の一例を示す図である。
【図２】キャッシュバッファと二つのＬＲＵとを表す概略図である。
【図３】キャッシュバッファ選択処理の一例を示すフローチャートである。
【図４】ＦＡＴファイルシステムにおいてディレクトリの空き領域を探す手順を示すフローチャートである。
【図５】ＦＡＴ１６ファイルシステムにおいてディスク上の全ての空きクラスタを数え上げる手順を示すフローチャートである。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態について図面に基づいて説明する。
【００１０】
＜実施形態１＞
図１は、情報処理装置（コンピュータ）１のハードウェア構成の一例を示す図である。図１に示されるように情報処理装置１は、ハードウェア構成として、ＣＰＵ１１を含む。ＣＰＵ１１が、記憶装置１３に記憶されているプログラムに基づき処理を行うことによって、ファイルシステムやＬＲＵの機能、又は後述するフローチャートに係る処理が実現される。
ＣＰＵ１１には、バス１０を介して、入力装置１２、記憶装置１３及び表示装置１４が接続されている。記憶装置１３は、例えば、ＲＯＭ及びＲＡＭ及びハードディスク装置等からなり、上述した各プログラム以外に、プログラムに基づく処理で用いられるデータを記憶する。なお、後述するキャッシュバッファ等は、ＲＡＭに実装されているものとする。表示装置１４は、情報を表示する例えばディスプレイ等である。入力装置１２は、情報を入力する例えば操作キー等である。
なお、入力装置１２及び表示装置１４は、情報処理装置１の必須の構成要素ではない。
以下では特に言及しない限り、ＣＰＵ１１が処理を実行するものとする。
【００１１】
図２は、キャッシュバッファと二つのＬＲＵとを表す概略図である。
第一ＬＲＵ１０１は、近い将来再利用される可能性の高いキャッシュバッファ、つまり、予め定められた時間内に再利用される可能性が、予め定められた値以上のキャッシュバッファ、を管理する。第一ＬＲＵ１０１は、第一管理手段の一例である。第二ＬＲＵ１０２は、近い将来再利用される可能性の低いキャッシュバッファ、つまり、予め定められた時間内に再利用される可能性が、予め定められた値未満のキャッシュバッファを管理する。第二ＬＲＵ１０２は、第二管理手段の一例である。キャッシュバッファ集合１０３は、キャッシュバッファの集合であり、１セクタ分のキャッシュバッファがＢ１からＢ８まで８個存在している。ＬＲＵは、それぞれのキャッシュバッファをリンクリストでつなげることで管理している。図２において、ＬＲＵにつながれているキャッシュバッファのうち、先頭にあるものが最近利用されたキャッシュバッファであり、末尾のものが最も長い間利用されていないキャッシュバッファである。第一ＬＲＵから辿れるリンクリストには近い将来再利用される可能性の高いものだけがつながれており、第二ＬＲＵから辿れるリンクリストには近い将来再利用される可能性の低いものだけがつながれている。
Ｂ１からＢ８までの全てのキャッシュバッファに何らかのデータが格納されている状態で、キャッシュバッファには存在しない新しいデータにアクセスする必要が生じた場合について説明する。新しいデータをキャッシュバッファに格納するためには既存のキャッシュバッファのどれかを選択してその内容を新しいデータに置き換える必要がある。
本実施形態では、ＣＰＵ１１は、第二ＬＲＵにつながれているキャッシュバッファが一つもないときには第一ＬＲＵの末尾のキャッシュバッファを選択するが、そうでないときには第二ＬＲＵの末尾にあるキャッシュバッファを選択する。選択されたバッファのそれまでの内容は破棄され、新しいデータで上書きされる。そしてそのキャッシュバッファは、それまで存在していたＬＲＵから取り除かれる。図２（Ａ）の例では、第二ＬＲＵの末尾にあるキャッシュバッファＢ８が選択される。
【００１２】
図３は、キャッシュバッファ選択処理の一例を示すフローチャートである。ファイルシステムがキャッシュバッファを必要としたとき、Ｓ４０１からキャッシュバッファ選択手順が開始される。Ｓ４０２では、ＣＰＵ１１は、指定されたセクタのキャッシュバッファが既に存在するかどうかを判断する。同じセクタのキャッシュバッファが存在していた場合（Ｓ４０２においてＹｅｓ）、ＣＰＵ１１は、Ｓ４０６に移り、そのバッファを選択する。指定されたセクタのキャッシュバッファが存在しない場合（Ｓ４０２においてＮｏ）、ＣＰＵ１１は、Ｓ４０３に移り、第二ＬＲＵが空かどうかを判断する。空でない場合（Ｓ４０３においてＮｏ）、ＣＰＵ１１は、Ｓ４０４で第二ＬＲＵの末尾のバッファを選択し、Ｓ４０７に移る。第二ＬＲＵが空の場合（Ｓ４０３においてＹｅｓ）、ＣＰＵ１１は、Ｓ４０５で第一ＬＲＵの末尾のバッファを選択し、Ｓ４０７に移る。Ｓ４０７では、ＣＰＵ１１は、選択したキャッシュバッファに入っている内容を破棄し、新しいセクタを読み込みキャッシュバッファに格納し、Ｓ４０８に移る。Ｓ４０８では、ＣＰＵ１１は、選択したキャッシュバッファをＬＲＵから取り除く。
次に、このキャッシュバッファＢ８を利用し終わったときの動きを図２（Ｂ）と図２（Ｃ）とを参照して説明する。Ｂ８を利用し終わった時点で、このデータが近い将来再利用される可能性が高いと判断された場合には、Ｂ８は第一ＬＲＵの先頭につながれる（図２（Ｃ））。一方、このデータが近い将来再利用される可能性が低いと判断された場合には、Ｂ８は第二ＬＲＵの先頭につながれる（図２（Ｂ））。
【００１３】
キャッシュバッファを利用し終わった時点でこのデータが近い将来再利用される可能性を判断する方法について、図４を用いて説明する。図４は、ＦＡＴファイルシステムにおいてディレクトリの空き領域を探す手順を示すフローチャートである。ファイルやディレクトリを作成する際にＳ５０１からディレクトリの空き領域を探す処理が開始される。Ｓ５０２で、ＣＰＵ１１は、セクタ番号を格納する変数ｓｅｃｔに対象ディレクトリの先頭セクタ番号を格納する。Ｓ５０３で、ＣＰＵ１１は、変数ｓｅｃｔに格納されているセクタ番号のキャッシュバッファを獲得する。Ｓ５０４で、ＣＰＵ１１は、変数ｐにキャッシュバッファの先頭アドレスを格納する。変数ｐは、ファイルやディレクトリ一つ分の領域であるディレクトリエントリの先頭アドレスを格納するポインタ変数である。
次にＳ５１３で、ＣＰＵ１１は、ｐが指す領域が空き領域かどうかを調べる。ｐが指す領域が空き領域であった場合（Ｓ５１３においてＹｅｓ）、ＣＰＵ１１は、処理をＳ５１０に移し、このキャッシュバッファを第一ＬＲＵに挿入する。第一ＬＲＵに挿入する理由は、この空き領域にファイルやディレクトリが近い将来作成されるはずであり、そのときにこのキャッシュバッファが再利用されるからである。Ｓ５１０の後は、ＣＰＵ１１は、処理をＳ５１１に移し、処理を終了する。
【００１４】
Ｓ５１３でｐが指す領域が空き領域でなかった場合（Ｓ５１３においてＮｏ）、ＣＰＵ１１は、Ｓ５０５でｐを３２バイト増加させる。次にＳ５０６で、ＣＰＵ１１は、ｐがセクタの終端かどうかを調べる。セクタの終端ではなかった場合（Ｓ５０６においてＮｏ）、ＣＰＵ１１は、処理をＳ５０４に移す。Ｓ５０６でｐがセクタの終端であった場合（Ｓ５０６においてＹｅｓ）、ＣＰＵ１１は、Ｓ５０７でこのキャッシュバッファを第二ＬＲＵに挿入する。第二ＬＲＵに挿入する理由は、このセクタには空き領域がなかったのでこのキャッシュバッファが近い将来再利用される可能性は少ないからである。
次にＳ５０８で、ＣＰＵ１１は、変数ｓｅｃｔの示すセクタがディレクトリの終端かどうかを調べる。終端であった場合（Ｓ５０８においてＹｅｓ）、ＣＰＵ１１は、ディレクトリの最後まで空き領域がなかったということなので、Ｓ５１２でこの処理を終了する。Ｓ５０８でディレクトリの終端でなかった場合（Ｓ５０８においてＮｏ）、ＣＰＵ１１は、当該ディレクトリにおいてｓｅｃｔが指すセクタの論理的に次のセクタ番号をｓｅｃｔに格納して、処理をＳ５０３に戻す。
以上の処理により、ディレクトリ内に空き領域を探す処理において、空き領域がなかったキャッシュバッファを第二ＬＲＵに挿入し、空き領域を発見したキャッシュバッファを第一ＬＲＵに挿入する。このことにより、キャッシュバッファを有効に活用することが可能となる。
【００１５】
また、本実施形態は、ディレクトリ中の空き領域を探す例であるが、別な実施形態としてディスク上に新たなデータを書き込むために空きクラスタを探す処理も同様に実現することができる。ディレクトリ中の空き領域を探す処理と違うのは、空きクラスタを探すのにディレクトリではなくＦｉｌｅ  Ａｌｌｏｃａｔｉｏｎ  Ｔａｂｌｅ（ＦＡＴ）を調べる点である。ＦＡＴの１エントリ分が空きを示していれば、それに対応するクラスタが空きということである。空きが見つかった場合、ＣＰＵ１１は、そのＦＡＴを含むキャッシュバッファを第一ＬＲＵに挿入する。その理由は、空きクラスタにはデータがかかれるはずで、その空きを示すＦＡＴが書き換えられるからである。また、ＣＰＵ１１は、空きを含まなかったＦＡＴを含むキャッシュバッファは、第二ＬＲＵに挿入する。その理由は、そのＦＡＴは近い将来書き換えられる可能性が低いからである。
【００１６】
＜実施形態２＞
次に図５を用いて上述した実施形態とは別の実施形態を説明する。図５は、ＦＡＴ１６ファイルシステムにおいてディスク上の全ての空きクラスタを数え上げる手順を示すフローチャートである。ＦＡＴ１６ファイルシステムでは、一つ一つのクラスタの状態を２バイトのＦＡＴエントリで表しており、空きクラスタ数を数え上げるには、全てのＦＡＴエントリを先頭から末尾まで２バイトごとに検査して、空きを示すエントリの数を数える。この処理の特徴は、ＦＡＴ領域の全てのセクタを読み込んで順にアクセスする必要があるが、この処理のために読み込んだキャッシュバッファのどれもがその後の処理において再利用される可能性が低い点である。したがって、本実施形態では、ＣＰＵ１１は、読み込んだ全てのキャッシュバッファを第二ＬＲＵに挿入する。これにより、この処理が始まる前の時点で第一ＬＲＵに入っているキャッシュバッファの方が有効活用される可能性を高めている。
【００１７】
より具体的な手順を、図５を用いて説明する。ファイルシステムが空きクラスタを数え上げる必要がある時にはＳ６０１から処理が始められる。Ｓ６０２で、ＣＰＵ１１は、セクタ番号を示す変数ｓｅｃｔにＦＡＴ領域の先頭セクタ番号を格納し、空きクラスタを数え上げた結果を示す変数ｃｎｔに０を格納する。次にＳ６０３で、ＣＰＵ１１は、ｓｅｃｔが示すセクタのキャッシュバッファを獲得する。Ｓ６０４とＳ６０５とＳ６０６とＳ６０７とＳ６０８とは、当該キャッシュバッファに入っている１セクタ分のＦＡＴが示す空きクラスタを数える部分であるが、本実施形態の本質ではないので説明は省略する。１セクタ分の処理が終わるとＳ６０９に到達し、ＣＰＵ１１は、ここで処理の終わったキャッシュバッファを第二ＬＲＵに挿入する。その後、Ｓ６１０で、ＣＰＵ１１は、ｓｅｃｔがＦＡＴ領域の終端かどうかを調べる。終端であった場合（Ｓ６１０においてＹｅｓ）、ＣＰＵ１１は、Ｓ６１２で処理を終了する。このときｃｎｔにはディスク上の空きクラスタの総数が入っている。Ｓ６１０でｓｅｃｔがＦＡＴ領域の終端ではなかった場合（Ｓ６１０においてＮｏ）、ＣＰＵ１１は、ｓｅｃｔに次のセクタ番号を格納し、処理をＳ６０３に戻す。
以上の処理により、キャッシュバッファを有効に活用することができる。
【００１８】
＜その他の実施形態＞
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【００１９】
以上、上述した各実施形態によれば、再利用性の低いデータによってそれまでキャッシュバッファに入っていたデータが追い出されることを防ぎ、限られた資源であるキャッシュバッファを有効に活用することができる。
【００２０】
以上、本発明の好ましい実施形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００２１】
１１  ＣＰＵ
１３  記憶装置
【図１】
0005697403.tif 000002
【図２】
0005697403.tif 000003
【図３】
0005697403.tif 000004
【図４】
0005697403.tif 000005
【図５】
0005697403.tif 000006