(57)【要約】【課題】記録装置上に配置された位置的に連続性がないデータへのアクセスを高速化すること。【解決手段】検索処理を制御する制御装置と、記録装置内蔵のキャッシュメモリに指定データを格納する先読みコマンドを実装した記録装置から検索システムを構成する。制御装置はデータを処理している間に、先読みコマンドを使用して次に必要となるデータの先読みを記録装置に指示し、記録装置は指定されたデータを記録媒体から読み出してキャッシュメモリに格納しておくことで、制御装置が次のデータを記録装置から読み出すときには、記録媒体へアクセスせずに記録装置内蔵のキャッシュメモリから高速にデータを読み出す。また、先読みコマンドで指示されて読み出した領域に優先度や保護フラグを付加してキャッシュメモリを効率的に管理することにより、キャッシュメモリのヒット率を向上させ読み出しを高速化する。【選択図】図３
2008146516.tif 000002
【特許請求の範囲】
【請求項１】
利用者の要求データの読み出し処理を行う処理プログラムと、内部キャッシュ機構を備えた記録装置であって、処理プログラムからの先読み要求を受け付ける手段と、先読み要求データを記録媒体から記録装置内部のキャッシュメモリに読み込む手段とを備えることを特徴とするデータの先読み処理方式。
【請求項２】
請求項1のデータの先読み処理方式において、利用者の指示する先読みが必要な複数のデータの先読み要求を受け付ける手段と、受け付けた要求を元に記録装置へ先読み指示を行う手段と、記録装置における先読み処理と並行して読み出し済みデータの処理を行う手段を備えることを特徴とするデータの先読み処理プログラム。
【請求項３】
請求項1のデータの先読み処理方式において、処理プログラムからの先読み指示を受け付け、先読み指示を受け付けた時点で記録媒体からの読み出し処理を開始すると同時に要求元への要求受け付け完了報告を行う手段と、要求のあったデータを要求元へは返却せず、記録媒体から記録装置内部キャッシュメモリへの読み出しのみを行う手段と、処理プログラムからの読み出し指示によりキャッシュメモリ上に読み出し済みのデータを要求元へ転送する手段を備えることを特徴とする記録装置。
【請求項４】
請求項３の記録装置において、要求されたデータの記録媒体からの読み出し処理を最適にするために要求の実行順序の並び替えを行う手段と、記録装置内部の記録媒体から満杯になっているキャッシュメモリにデータを読み込んで格納する際、格納済みデータのうち先読み指定により格納されたデータを他のデータよりもキャッシュメモリに優先的に残しておく手段と、記録装置内部キャッシュメモリへ読み込んだデータに対する実際の読み出し要求において通常のキャッシュ先読み制御を抑止する手段とを備えることを特徴とする記録装置制御方式。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記録装置上にデータを格納し、それを読み出す処理プログラムにおいて、データを事前に記録装置内部キャッシュメモリ上に読み込ませることにより、記録装置からのデータ読み出し時間を短縮可能にした処理プログラムと記録装置に関するものである。
【背景技術】
【０００２】
コンピュータシステムでは、一般にコンピュータ内部でのデータ処理に要する時間に比べ、記録装置とコンピュータ内部のメモリとの間のデータの読み出しおよび書き込みに要する時間が非常に大きい。関連性のあるデータを連続的に読み出すコンピュータシステムでは、このデータの読み出し処理を効率化することでシステムの処理性能を向上させることができる。
【０００３】
そのための方法として、記録装置内部のキャッシュメモリを効率的に利用し、読み出し要求への応答時間を短縮する手法と、コンピュータシステムにおいて、読み出し済みのデータに対する表示や検索などの処理を行っている間の空き時間に、後に必要となるデータを記録装置からあらかじめ読み出す手法がある。
【０００４】
図１は、このコンピュータシステムの概略を示すブロック構成図であり、利用者の検索指示を受付け、データの検索、加工および出力を制御する制御装置１０と、データを格納する記録装置１１から構成される。制御装置１０は、データの検索および加工などのデータ操作と、記録装置へのデータ入出力処理の制御を行うデータ処理部１０１、利用者からの検索指示を受け取る入力部１０２、データ処理部１０１で生成された情報を利用者に向けて出力する出力部１０３、記録装置１１から読み出したデータを一時的に蓄えるメモリ１０４から構成され、記録装置１１は、実際にデータを格納する記録媒体１１１、この記録媒体１１１から読み出したデータを保持するキャッシュメモリ１１２、記録媒体１１１からの読み出しとキャッシュメモリ１１２へのデータ格納を制御する入出力制御部１１３から構成される。
【０００５】
図２に一般的なキャッシュ機能を備えた記録装置１１でのデータ読み出し処理を示す。入出力制御部１１３は、指定データがキャッシュメモリ１１２上に格納されているかを確認し（ステップ２０１）、格納されていなければ記録媒体１１１から読み出し（ステップ２０２）、キャッシュメモリ１１２上に保持する（ステップ２０３）。このデータを要求元の制御システムに転送し（ステップ２０４）、読み出し処理は完了する（ステップ２０５）。ここで入出力制御部１１３は、記録媒体１１１上で最後にアクセスしたデータに位置的に連続したものが近い将来にアクセスされる可能性が高いことを利用して、要求されたデータだけでなくそれに位置的に連続するデータもあらかじめ記録媒体１１１から読み出し（ステップ２０２）、キャッシュメモリ１１２上に保持しておく（ステップ２０３）。このため、後続の読み出し要求では、取得対象データがキャッシュメモリ１１２上に保持されている場合は記録媒体１１１へアクセスせずに、読み出し要求に高速に応答することができる（ステップ２０１、２０４、および２０５）。例えば、文献管理システムなどでは、一連の文献データを記録媒体１１１上に物理的に連続格納することによって、記録装置１１の先読み効果を利用して検索性能を向上している。
【０００６】
カーナビゲーションシステムでは、目的地を設定したルート走行において自車の移動に従って移動先の地図データを読み出し、遅延なく地図画像を表示する必要がある。しかし、２次元的な広がりを持つ地図データを、あらかじめ予測できないルートに従って連続的に記録媒体１１１上に配置することはできないため、記録装置１１の先読み効果を利用することはできない。そこで、制御装置１０では、データ処理部１０１および出力部１０３が読み出し済みデータの処理および表示を行っている間の空き時間を利用して、以後必要とされる可能性のあるデータをあらかじめ記録装置１１から読み出し、メモリ１０４に保持しておく。この処理は記録媒体１１１からの読み出し（ステップ２０２）を伴うため処理時間がかかるが、データ処理部１０１が対象データを必要とした時点での記録装置１１へのアクセスが不要となり、速やかにデータの処理および表示を行うことができる。
【０００７】
なお、本発明に関連する公知技術文献としては下記の特許文献１がある。
【０００８】
【特許文献１】特開２００３−２６３３４８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
カーナビゲーションシステムの例のように、格納位置の連続性はないが関連性のある複数のデータを記録装置から読み出す処理を行うシステムにおいては、記録装置が持つ従来の先読みキャッシュの機能については効果が期待できない。そこで、記録装置上のデータをあらかじめ制御装置側のメモリ上に読み出す方式を使用することになるが、この方式には以下の問題がある。
（１）将来必要になるデータを事前に記録装置から読み出す処理では、対象データが記録装置の持つキャッシュメモリ上に存在せずに記録媒体からの読み出しを伴う可能性が高く、その完了を待つ必要があるため、制御装置の処理に十分な空き時間が必要である。
（２）記録装置から先読みしたデータを、使用されるまで制御装置のメモリ領域上に保持するため、その間はメモリ領域の一部が占有される。
【００１０】
本発明の目的は、上記問題点を解決した上で、格納位置に連続性のないデータの先読みを効率的に行うことができるデータの先読み処理方式を提供することにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明のデータの先読み処理方式は、利用者の要求データの読み出し処理を行う処理プログラムと、内部キャッシュ機構を備えた記録装置であって、処理プログラムからの先読み要求を受け付ける手段と、先読み要求データを記録媒体から記録装置内部のキャッシュメモリに読み込む手段とを備え、前記処理プログラムは、要求データの読み出し処理を行う処理プログラムであって、利用者の指示する先読みが必要な複数のデータの先読み要求を受け付ける手段と、受け付けた要求を元に記録装置へ先読み指示を行う手段と、記録装置が先読み処理を行うことと並行して読み出し済みデータの処理を行う手段を備え、前記記録装置は、処理プログラムからの先読み指示に従い、要求データの先読みを行う記録装置であって、先読み指示を受け付けた時点で記録媒体からの読み出し処理を開始すると同時に要求元への要求受け付け完了報告を行う手段と、要求のあったデータを要求元へは返却せず、記録媒体から記録装置内部キャッシュメモリへの読み出しのみを行う手段と、処理プログラムからの読み出し指示によりキャッシュメモリ上に読み出し済みのデータを要求元へ転送する手段を設けたものである。
【発明の効果】
【００１２】
本発明のデータの先読み処理方式によれば、次のような効果がある。
【００１３】
データがインデクス部とデータ部に分かれて管理されている、またはデータがチェイン構造で管理されているなどのように、記録媒体上の格納位置に連続性がなく、従来の記録装置の先読みキャッシュの効果が低いような配置でデータを格納するシステムにおいて、記録装置による先読み機能を利用できる。
【００１４】
記録媒体上の格納位置に連続性がない複数のデータの読み出し処理において、制御装置でのデータ処理と並列して記録装置内部で先読み処理を行うことにより、制御装置での処理時間を消費せずに先読み処理を実現し、高速なデータアクセスができる。
【００１５】
記録媒体上の格納位置に連続性がない複数のデータの読み出し処理において、記録装置内部のキャッシュメモリに先読みデータを保持することにより、制御装置のメモリ領域を使用せずに先読み処理を実現し、高速なデータアクセスができる。
【００１６】
記録装置において、利用者が指示した先読み要求に従いデータを記録媒体から読み出してキャッシュメモリに格納する際に、記録媒体からの読み出し順を最適に並べ替えることにより、利用者の指定した順で読み出しを行う方法よりも高速に記録媒体からの読み出しを完了する。
【００１７】
記録装置において、利用者が指示した先読み要求で読み出したデータについて、優先度をつけてキャッシュメモリ内に他のデータ領域より長く保持するか、実際に読み出されるまでキャッシュメモリ内に保持することにより、通常のキャッシュ管理方式よりもキャッシュヒット率を向上させることができる。
【発明を実施するための最良の形態】
【００１８】
以下、本発明を適用した検索システムの一実施の形態について説明する。
【００１９】
図３は、本発明の実施の形態の一例を示すシステム構成図であり、本検索システムは、地図データを格納した記録装置３１と、このデータに対する検索、表示処理を行う制御装置３０から構成されるカーナビゲーションシステムである。この制御装置３０はデータの検索、加工などの処理を行うデータ処理部３０１と、利用者からの操作やＧＰＳ(Global Positioning System)の位置情報を取得する入力部３０２と、地図画像を表示する出力部３０３と、データを一時的に保持するメモリ３０４から構成される。
【００２０】
記録装置３１には、地図データを格納した記録媒体３１１と、キャッシュメモリ３１２と、入出力制御部３１３と、先読み制御部３１４が内蔵されている。制御装置３０と記録装置３１との間のインタフェースは、必要ならば記録装置インタフェース回路を使用する。入出力制御部３１３は、記録媒体３１１からのデータの読み出しを行う読み出しコマンドを含む一般的なアクセス用コマンドを受け付け、記録媒体３１１とキャッシュメモリ３１２のデータ入出力処理を制御する。先読み制御部３１４は、記録媒体３１１からデータを読み出しキャッシュメモリ３１２へデータを格納するための先読みコマンドを受け付け、入出力制御部３１３と相互作用し、記録媒体３１１とキャッシュメモリ３１２のデータ入出力処理を制御する。
【００２１】
図４は、記録媒体３１１に格納された地図データの物理的な配置と、意味的な関連性を示す。地図データはインデクス部４３とデータ部４４に分かれて管理され、記録媒体３１１に格納されている。また、データ部４４は地図データを固定サイズ単位に分割した地図区画データで構成される。現在位置４１の近傍をあらわす地図区画データ４２１〜４２７は意味的には隣接した地図情報を表すが、記録媒体３１１上での物理的な配置には必ずしも連続性がない。
【００２２】
本システムの制御装置３０における検索処理のフローを図５に示し、先読み制御部３１４が先読みコマンドを受け付けた際のデータの先読み処理のフローを図６に示す。入出力制御部３１３が読み出しコマンドを受け付けた際のデータの読み出し処理は図２と同様である。
【００２３】
まず、データ処理部３０１は現在位置４１に対応する地図情報を検索し、該当する地図区画データ４２４を記録装置３１から読み出し、メモリ３０４に格納する（ステップ５０１）。このデータを元に地図画像を生成し、出力部３０３が表示処理を行う。
【００２４】
データ処理部３０１は入力部３０２の入力情報に従い、次に読み出すべき地図画像を決定する（ステップ５０２）。現在位置と進行方向の経路情報から、次に必要となるデータは地図区画４２２および４２５であると予測される。ここで、地図区画４２５は読み出し済みの地図区画４２４と記録媒体３１１上での格納位置が連続しているため、記録装置３１の先読みによりキャッシュメモリ３１２に格納されている可能性が高いが、地図区画４２２は格納位置が離れているため、その可能性は低い。
【００２５】
データ処理部３０１は、現在位置の近傍の地図区画データ４２１の範囲内の情報を表示している間に、記録装置３１に対して、地図区画４２２および４２５のデータを指定して先読みコマンドを発行する（ステップ５０３）。記録装置の先読み制御部３１４はコマンドを受け付けるとすぐに、要求元に受付完了の通知を行う（ステップ６０１）。このためデータ処理部３０１はコマンド発行後すぐに、メモリ３０４上に格納済みの現在位置近傍のデータを使用し、画像の生成および表示処理を続行できる（ステップ５０４）。
【００２６】
データ処理部３０１が処理を続行しているのに並行して、記録装置の先読み制御部３１４は先読みコマンドの処理を続行する。指定データがキャッシュメモリ３１２に格納されているかを確認し（ステップ６０２）、格納されていない場合は記録媒体３１１から対象データを読み出し（ステップ６０３）、キャッシュメモリ３１２に格納する（ステップ６０４）。この時点ではキャッシュメモリ３１２への読み出しのみを行い、要求元への転送は行わない。
【００２７】
ここで、連続して発行された先読みコマンドについて、先読み制御部３１４は要求されたデータの物理的な配置にしたがってその要求を並べ替え、記録媒体３１１へのアクセスを最適化してから、実際の読み出し処理を行う。コマンドの発行元では、先読みコマンドを発行する際に、対象データの配置およびコマンドの発行順序を意識する必要がない。
【００２８】
現在位置４１が遷移しデータ処理部３０１が地図区画４２２および２２５のデータを必要となったとき、データ処理部３０１は記録装置３１に対して読み出しコマンドを発行し、対象データを記録装置３１から読み出し、メモリ３０４に格納する（ステップ５０５）。この時点では、あらかじめ発行しておいた先読みコマンドは処理を完了しており、記録装置のキャッシュメモリ３１２に対象データが格納されている。したがって、読み出しコマンドを受け付けた入出力制御部３１３は、記録媒体３１１へアクセスせずにキャッシュメモリ３１２から制御装置のメモリ３０４へのデータ転送のみを行い、コマンドは短時間で完了する。これにより、データ処理部３０１および出力部３０３は現在位置４１の移動に伴う地図画像の表示を遅延なく行うことができる。
【００２９】
このように、記録装置３１に対して指定データをキャッシュメモリ３１２に格納する指示をあらかじめ出しておくことにより、制御装置３０におけるデータ処理と記録装置３１における記録媒体３１１からの読み出し処理が並列化され、記録媒体３１１上で位置的に分散して格納されているデータへのアクセスの高速化を図ることができる。この先読み処理方式は、インデクス管理のデータ構造だけではなく、チェーン管理のデータなど、読み出すデータを線形に並べづらく単純な先読みキャッシュでは効果が小さいようなデータへのアクセスを行う様々なシステムに適応することができる。
【００３０】
図７は、読み出し処理および先読み処理における、記録装置３１内蔵のキャッシュメモリ３１２へのデータ格納の処理を表す。これは読み出し処理のステップ２０３、および先読み処理のステップ６０４に相当する処理である。
【００３１】
まずキャッシュメモリ３１２に空き領域があるかを判定し（ステップ７０１）、空き領域があればそれをデータ格納領域とする（ステップ７０３）。空きがなければ格納済みデータの中でもっとも優先度の低いデータを破棄対象として選択し、その領域を新たなデータの格納領域とする（ステップ７０２）。このように選択したキャッシュメモリ３１２上の格納領域にデータを格納する（ステップ７０４）。
【００３２】
一般的な記録装置では、データ領域の読み出し頻度の高いものや、格納時期の新しいものなどを優先するというアルゴリズムに基づき格納データに優先度を設定し、キャッシュ満杯時には優先度の低いデータを破棄する処理を行う。本発明では、特に先読みコマンドを用いて読み出したデータ領域に対して、他のキャッシュ上のデータよりも高い優先度を設定する（ステップ７０５および７０６）ことで、破棄対象データの選択処理（ステップ７０２）において、先読みコマンドで読み出されたデータを他のデータよりも優先的に残すようにする。これにより、先読みコマンドで指定したデータが、通常の読み出し要求を受け付けた時点でキャッシュメモリ３１２に格納されている確率を上げることができる。
【００３３】
また、先読みコマンドを用いて読み出したデータ領域には、保護フラグを設定する（ステップ７０７）。キャッシュメモリ３１２が満杯になった際の破棄対象データの選択時（ステップ７０２）には、保護フラグが設定されている領域を破棄しないとすることにより、先読みコマンドを発行して（ステップ５０３）読み出したデータ領域が実際のデータ読み出し時点（ステップ５０５）までにキャッシュメモリ３１２から破棄されることを防ぐことができる。この保護フラグは、実際にキャッシュから該当データ領域が読み出された際に解除する。また、保護フラグが設定されたデータが読み出されないままキャッシュメモリ３１２上に蓄積され続けた場合は、その割合が閾値を超えた際に、優先度の最も低いものを選択し設定を解除する。
【００３４】
優先度によるキャッシュメモリ３１２の管理と、保護フラグによるキャッシュメモリ３１２の管理は、それぞれ単独で適用することも、両者を併用することもできる。
【００３５】
このように、記録装置３１の内蔵キャッシュメモリ３１２へ格納したデータ領域の管理方法を改良することにより、本発明の先読みコマンドを利用してキャッシュメモリ３１２の利用効率を向上させることができる。
【図面の簡単な説明】
【００３６】
【図１】従来の検索システムの概略構成図である。
【図２】記録装置でのデータ読み出し処理を示すフローチャートである。
【図３】本発明の一実施の形態例を示すシステム構成図である。
【図４】記録媒体上のデータの配置の具体例の説明図である。
【図５】検索システムのデータ処理を示すフローチャートである。
【図６】記録装置でのデータ先読み処理を示すフローチャートである。
【図７】記録装置でのキャッシュ格納処理を示すフローチャートである。
【符号の説明】
【００３７】
３０…制御装置、３０１…データ処理部、３０２…入力部、３０３…出力部、３０４…メモリ、３１…記録装置、３１１…記録媒体３１１…キャッシュメモリ、３１３…入出力制御部、３１４…先読み制御部。
【図１】
2008146516.tif 000003
【図２】
2008146516.tif 000004
【図３】
2008146516.tif 000005
【図４】
2008146516.tif 000006
【図５】
2008146516.tif 000007
【図６】
2008146516.tif 000008
【図７】
2008146516.tif 000009