(57)【要約】【課題】  データ記憶領域におけるデータの記録位置を効率的に管理する。【解決手段】  状態検出部１１６は、記録媒体におけるクラスタの使用状態を検出する。フリーリスト管理部１２０は、連続する同じ使用状態のクラスタをまとめた連続クラスタごとに、その論理アドレスを管理するフリーリストの要素を生成する。あふれフリーリスト管理部１３０は、フリーリストの要素の数がｍ個（ｍは自然数）を超えるとき、ｍ＋１個目からの連続クラスタごとに、その論理アドレスを管理するあふれフリーリストの要素を生成する。あふれフリーリスト管理部１３０は、あふれフリーリストの要素の数がｎ個（ｎは自然数）を超えるとき、いずれかのあふれフリーリストの要素に、複数の連続クラスタを包含する領域の論理アドレスを管理させる。【選択図】  図５
2005227855.tif 000002
【特許請求の範囲】
【請求項１】
記録媒体における、論理アドレスが連続した所定サイズの記憶領域により構成されるユニットごとに、データが記録されているユニットであるか否かについての使用状態を検出する状態取得部と、
連続する同じ使用状態のユニットをまとめた連続ユニットを検出する連続ユニット検出部と、
前記連続ユニットごとに、その論理アドレスを管理する第１アドレスオブジェクトを生成する第１オブジェクト生成部と、
前記第１アドレスオブジェクトの数がｍ個（ｍは自然数）を超えるとき、ｍ＋１個目からの連続ユニットごとに、その論理アドレスを管理する第２アドレスオブジェクトを生成する第２オブジェクト生成部と、
前記連続ユニットの検出を契機として、前記第１または第２オブジェクト生成部にそれぞれ前記第１または第２アドレスオブジェクトの生成を指示する生成制御部と、
前記第１および第２アドレスオブジェクトの双方または一方が管理する論理アドレスを参照して前記記録媒体におけるデータの記録位置を特定し、前記ユニットを単位としてデータを分割して記録するデータ記録部と、を備え、
前記第２オブジェクト生成部は、前記第２アドレスオブジェクトの数がｎ個（ｎは自然数）を超えるとき、いずれかの第２アドレスオブジェクトに、複数の連続ユニットを包含する合体領域の論理アドレスを管理させることを特徴とするデータ記憶領域管理装置。
【請求項２】
前記第２オブジェクト生成部は、前記第２アドレスオブジェクトに合体領域の論理アドレスを管理させるとき、複数の連続ユニットのうちもっとも近い関係にある連続ユニットを合体させることを特徴とする請求項１に記載のデータ記憶領域管理装置。
【請求項３】
前記連続ユニットのサイズを検出するサイズ検出部を更に備え、
前記生成制御部は、前記第２アドレスオブジェクトが管理する合体領域に含まれる連続ユニットのいずれかのサイズが、前記第１アドレスオブジェクトが管理する連続ユニットのいずれかのサイズを超えたとき、前記第１および第２アドレスオブジェクトの再生成を指示することを特徴とする請求項１または２に記載のデータ記憶領域管理装置。
【請求項４】
前記データ記録部が記録すべきデータを処理する外部装置の処理負荷量を検出する負荷検出部を更に備え、
前記生成制御部は、前記処理負荷量が所定の閾値以下となることを契機として、前記第１および第２アドレスオブジェクトの再生成を指示することを特徴とする請求項１から３のいずれかに記載のデータ記憶領域管理装置。
【請求項５】
前記第１アドレスオブジェクトが管理する連続ユニットのサイズの合計値を検出するサイズ計算部を更に備え、
前記生成制御部は、前記合計値が所定の閾値を超えたか否かを契機として、前記第１および前記第２アドレスオブジェクトの再生成を指示することを特徴とする請求項１から４のいずれかに記載のデータ記憶領域管理装置。
【請求項６】
記録媒体における、論理アドレスが連続した所定サイズの記憶領域により構成されるユニットごとに、データが記録されているユニットであるか否かについての使用状態を検出する機能と、
連続する同じ使用状態のユニットをまとめた連続ユニットを検出する機能と、
前記連続ユニットごとに、その論理アドレスを管理する第１アドレスオブジェクトを生成する機能と、
前記第１アドレスオブジェクトの数がｍ個（ｍは自然数）を超えるとき、ｍ＋１個目からの連続ユニットごとに、その論理アドレスを管理する第２アドレスオブジェクトを生成する機能と、
前記連続ユニットの検出を契機として、前記第１または第２アドレスオブジェクトの生成を指示する機能と、
前記第１および第２アドレスオブジェクトの双方または一方が管理する論理アドレスを参照して前記記録媒体におけるデータの記録位置を特定し、前記ユニットを単位としてデータを分割して記録する機能と、
前記第２アドレスオブジェクトの数がｎ個（ｎは自然数）を超えるとき、いずれかの第２アドレスオブジェクトに、複数の連続ユニットを合体させた合体領域の論理アドレスを管理させる機能と、
をコンピュータに発揮させることを特徴とするデータ記憶領域管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明はデータ記憶領域管理技術に関し、特に、データ記憶領域を管理するための情報量を低減するための技術に関する。
【背景技術】
【０００２】
近年、デジタルカメラをはじめとする情報機器が取り扱うデータ量は急激に増加しつつある。その理由として、メモリカードをはじめとする小型記録媒体の記憶容量が半導体製造技術の向上に伴って加速度的に増加していることが挙げられる。これらの記録媒体は、さまざまなデジタルデータを、一定サイズのユニットに分割して記録する。パーソナルコンピュータにおいて標準的な論理フォーマットであるＦＡＴ(File Allocation Table)において、クラスタ（cluster）がこのユニットに対応する。以降では、クラスタを論理的な単位の呼称とする。記録媒体は、大きなデータをクラスタ単位に分割して記録することにより、その記憶領域を効率的に活用する。以下、記録媒体がデータを記憶するための領域のことを、「データ記憶領域」とよぶ。
【０００３】
分割された各種データのデータ記憶領域における位置を示す論理アドレスは、通常、情報機器が内蔵するメモリによって管理される。以下、データ記憶領域に記憶されるデータの位置を管理するための情報を「データ管理情報」とよぶ。情報機器は内蔵メモリが記憶するこのデータ管理情報を参照し、データ記憶領域におけるアクセス位置を特定する。一般に内蔵メモリは高速アクセスが可能であるため、内蔵メモリがデータ管理情報を記憶することにより情報機器のデータアクセス速度は高速化される。
【特許文献１】特開２０００−２６７９０４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、大容量記録媒体のデータ記憶領域を管理するために内蔵メモリが記憶するデータ管理情報のサイズも増加しつつある。一般に内蔵メモリは高価であるため、デジタルカメラのような組み込み型の情報機器が大きなメモリを内蔵することは好ましくない。
【０００５】
本発明は、このような課題に鑑みてなされたものであり、その目的は、データ記憶領域を管理するためのデータ管理情報のサイズを低減するための技術を提供することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明のある態様のデータ記憶領域管理装置は、記録媒体における、論理アドレスが連続した所定サイズの記憶領域により構成されるユニットごとに、データが記録されているユニットであるか否かについての使用状態を検出する。そして、連続する同じ使用状態のユニットをまとめた連続ユニットを更に検出する。連続ユニットごとに、その論理アドレスを管理する第１アドレスオブジェクトを生成し、その第１アドレスオブジェクトの数がｍ個（ｍは自然数）を超えるとき、ｍ＋１個目からの連続ユニットごとに、その論理アドレスを管理する第２アドレスオブジェクトを生成する。この装置は、これらの第１や第２アドレスオブジェクトが管理する論理アドレスを参照して、データの記録位置を特定し、ユニット単位にデータを分割して記録する。また、この装置は、第２アドレスオブジェクトの数がｎ個（ｎは自然数）を超えるとき、いずれかの第２アドレスオブジェクトに、複数の連続ユニットを包含する合体領域の論理アドレスを管理させる。
【発明の効果】
【０００７】
本発明によれば、データ記憶領域を効率的に管理できる。
【発明を実施するための最良の形態】
【０００８】
まず、図１から図３に関連して従来のデータ記憶領域管理の方法について簡単に説明する。
図１は、記録媒体におけるデータ記憶領域２００においてデータが記録される態様を説明するための模式図である。同図に示すようにデータ記憶領域２００は複数のデータ領域に分割される。これらの分割されたデータ領域はクラスタとよばれる。各クラスタは、５１２×２ｋバイト（ｋは０以上の整数）で表される所定のサイズをもつ領域である。記録媒体はクラスタを単位に各種データを分割してデータ記憶領域２００に記憶させる。同図において、斜線で示したクラスタはデータが記録されているクラスタ（以下、「使用クラスタ」とよぶ）であり、斜線のないクラスタはデータが記録されていないクラスタ（以下、「空きクラスタ」とよぶ）である。また、各クラスタが使用クラスタであるか空きクラスタであるかについての状態情報を「使用状態」とよぶ。
【０００９】
各クラスタには、それぞれを識別するためのクラスタ番号が順に割り振られる。同図において各クラスタの上段の数字がこのクラスタ番号を示す。ＦＡＴにおいては、通常はクラスタ番号「０００」と「００１」は予約番号としてデータ記録の対象とはならない。同図では、データ記憶領域管理方法の説明を簡易にするため、クラスタ番号「０００」のクラスタからデータを記録可能であるとして説明する。クラスタ番号「０００」と「００１」は空きクラスタであり、クラスタ番号「００２」から「００４」は使用クラスタである。同じ使用状態で隣り合うクラスタを、以下、「連続クラスタ」とよぶ。連続クラスタ２０２は２つの空きクラスタを連続して含む。連続クラスタ２０４は、３つの使用クラスタを連続して含む。以下、クラスタ番号「００５」のように、隣に同じ使用状態のクラスタを有しないクラスタのことも、併せて「連続クラスタ」とよぶものとする。通常、データ記憶領域２００は使用連続クラスタと空き連続クラスタが交互に並ぶ態様となる。
【００１０】
使用クラスタは、その使用クラスタが記憶するデータに続くべきデータの位置をクラスタ番号（以下、このようなクラスタ番号のことを、特に「次クラスタ番号」とよぶ）により記憶する。同図においては各使用クラスタの下段の数字がこの次クラスタ番号を示す。たとえば、クラスタ番号「００２」のクラスタは、次クラスタ番号として「００３」を記憶する。すなわち、クラスタ番号「００２」のクラスタに記憶されているデータに続くべきデータは、クラスタ番号「００３」のクラスタに記憶されている。データの最終位置となるクラスタは次クラスタ番号としてＥＮＤ情報を記憶する。同図ではクラスタ番号「０４７」のクラスタが該当する。ここでは、データ記憶領域２００は、クラスタ番号「００２」、「００３」、・・・、「０４７」までの計１７個のクラスタにデータを分割して記憶している。このデータ記憶領域２００を管理するためのデータ記憶領域管理方法としては、一般的にはビットマップ形式による方法と、フリーリスト形式による方法、または、それらの組み合わせた方法が考えられる。
【００１１】
図２は、ビットマップ形式のデータ管理情報により、データ記憶領域２００においてデータが管理される態様を説明するための模式図である。データ管理領域２１０は、情報機器の内蔵メモリにおいてデータ記憶領域２００のデータ位置を管理するための領域である。同図に示すデータ記憶領域２００は、図１に関連して説明したデータ記憶領域２００と同じであるとする。データ管理領域２１０は、データ記憶領域２００における使用クラスタの位置をビットマップ形式で管理する。情報機器はデータ管理領域２１０を参照して、データ記憶領域２００における使用クラスタと空きクラスタの位置を特定する。たとえば、新規データをデータ記憶領域２００に記憶させるとき、情報機器はデータ管理領域２１０を参照することによりデータ記憶領域２００を直接走査しなくてもデータ記憶可能な空きクラスタを特定できる。データ記憶領域２００に対する様々なデータアクセス処理に伴い、データ管理領域２１０も適宜更新される。
【００１２】
図３は、フリーリスト形式のデータ管理情報により、データ記憶領域２００においてデータが管理される態様を説明するための模式図である。データ管理領域２１０は、情報機器の内蔵メモリにおいてデータ記憶領域２００のデータ位置を管理するための領域である。同図に示すデータ記憶領域２００も、図１に関連して説明したデータ記憶領域２００と同じであるとする。データ管理領域２１０は、データ記憶領域２００における空きクラスタの位置をフリーリスト形式で管理する。
【００１３】
要素２１８は、このフリーリストの要素である。要素２１８は空き連続クラスタごとに生成される。要素２１８のうち、先頭アドレス領域２１２は空き連続クラスタの先頭アドレスを示す。クラスタサイズ領域２１４は空き連続クラスタに含まれるクラスタ数を示す。ポインタ領域２１６は、次のオブジェクトのデータ管理領域２１０における位置を指すためのポインタである。なお、アドレス順に領域を管理する場合は、ポインタは必須ではない。情報機器はデータ管理領域２１０を参照して、データ記憶領域２００における使用クラスタと空きクラスタの位置を特定する。たとえば、新規データをデータ記憶領域２００に記憶させるとき、情報機器はデータ管理領域２１０を参照することによりデータ記憶領域２００を直接走査しなくてもデータ記憶可能な空きクラスタを特定できる。データ記憶領域２００に対する様々なデータアクセス処理に伴い、データ管理領域２１０も適宜更新される。同図では、連続クラスタはアドレス順に管理されているが、フリーリストによる管理はこれに限られない。たとえば、連続クラスタに含まれるクラスタ数が大きい順、あるいは小さい順にフリーリストを生成してもよい。
【００１４】
以上に示した、ビットマップ形式やフリーリスト形式によるデータ記憶領域管理方法によれば、情報機器のデータの記録処理が高速化される。情報機器はデータ記憶領域２００を直接走査して各クラスタの使用状態を検出しなくても、高速な内蔵メモリが有するデータ管理情報で各クラスタの使用状態を取得できるからである。しかし、これらいずれのデータ記憶領域管理方法であっても、データ記憶領域２００が記憶するデータ量が増大し、空き連続クラスタの数が増えるとデータ管理領域２１０が記憶するデータ管理情報も増大する。本実施例では、図３に関連して説明したフリーリスト形式のデータ管理情報に基づきつつも、データ管理情報の増加を抑制するための方法を示す。
【００１５】
図４は、本実施例におけるデータ記憶領域管理方法により、データ記憶領域２００においてデータが管理される態様を説明するための模式図である。データ管理領域２１０は、情報機器の内蔵メモリにおいてデータ記憶領域２００のデータ位置を管理するための領域である。同図に示すデータ記憶領域２００も、図１に関連して説明したデータ記憶領域２００と同じであるとする。
【００１６】
このデータ管理領域２１０も、データ記憶領域２００における空き連続クラスタの位置をフリーリスト形式で管理する。このとき、フリーリストに加えてあふれフリーリストとよばれるふたつの種類の異なるリストが空き連続クラスタを管理する。フリーリストは図３に関連して説明したフリーリストと同様のリストである。フリーリストの要素は、空き連続クラスタを管理する。ただし、フリーリストにおける要素の数は所定数（以下、「第１最大要素数」とよぶ）に制限される。
【００１７】
あふれフリーリストは、フリーリストの要素の数が第１最大要素数を超えたときに生成されるフリーリストである。あふれフリーリストの要素も空き連続クラスタを管理する。あふれフリーリストの要素は、一つで複数の空き連続クラスタを管理可能である点がフリーリストの要素と異なる。あふれフリーリストにおける要素の数も所定数（以下、「第２最大要素数」とよぶ）に制限される。
【００１８】
以下、フリーリストの要素が管理する空き連続クラスタのことをいうときには、特に、「第１領域」とよぶ。また、あふれフリーリストの要素が複数の空き連続クラスタを管理する場合も含め、あふれフリーリストの要素が管理するデータ記憶領域２００における領域のことを言うときには、特に「第２領域」とよぶ。これらの領域のサイズはクラスタ単位で計数される。
【００１９】
フリーリストの要素２２０は、先頭アドレス領域２２２、クラスタサイズ領域２２４およびポインタ領域２２６を含む。フリーリストの要素２２０のうち先頭アドレス領域２２２は第１領域の先頭アドレスを示す。クラスタサイズ領域２２４は第１領域に含まれるクラスタ数を示す。ポインタ領域２２６は、次のフリーリストの要素のデータ管理領域２１０における位置を指すためのポインタである。
【００２０】
あふれフリーリストの要素２３０は、先頭アドレス領域２３２、クラスタサイズ領域２３４、管理フラグ領域２３６およびポインタ領域２３８を含む。あふれフリーリストの要素２３０のうち先頭アドレス領域２３２は第２領域の先頭アドレスを示す。クラスタサイズ領域２３４は第２領域に含まれるクラスタ数を示す。ポインタ領域２３８は、次のあふれフリーリストの要素のデータ管理領域２１０における位置を指すためのポインタである。管理フラグ領域２３６は、第２領域に複数の空き連続クラスタが含まれているか否かを示すフラグ（以下、「管理フラグ」とよぶ）である。第２領域が複数の空き連続クラスタを含むときには管理フラグは「１」となる。そうでないときには管理フラグは「０」となる。
【００２１】
同図において、あふれフリーリストの要素２４０は複数の空き連続クラスタを管理している。あふれフリーリストの要素２４０が管理する第２領域の合計クラスタ数は１８である。すなわち、クラスタ番号「０２８」から「０４５」までの１８クラスタ分が、あふれフリーリストの要素２４０が管理する第２領域である。図１を参照すると、この第２領域には、クラスタ番号「０２８」から「０３１」までの空きクラスタ、クラスタ番号「０３２」の使用クラスタ、クラスタ番号「０３３」から「０４５」までの空きクラスタが含まれる。フリーリストの要素とあふれフリーリストの要素の数がそれぞれ第１最大要素数および第２最大要素数により制限されるため、データ管理情報が一定値以上増加しないよう制御される。フリーリストおよびあふれフリーリストによる詳細なデータ記憶領域管理方法については後述する。
【００２２】
図５は、データ記憶領域管理装置１００の機能ブロック図である。ここに示す各ブロックは、ハードウェア的には、コンピュータのＣＰＵをはじめとする素子や機械装置で実現でき、ソフトウェア的にはコンピュータプログラム等によって実現されるが、ここでは、それらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックはハードウェア、ソフトウェアの組合せによっていろいろなかたちで実現できることは、当業者には理解されるところである。
【００２３】
データ記憶領域管理装置１００は、ユーザインタフェース処理部１１０、生成制御部１１２、データ記録部１１４、状態検出部１１６、連続検出部１１８、データ取得部１２２、フリーリスト管理部１２０およびあふれフリーリスト管理部１３０を含む。ユーザインタフェース処理部１１０はユーザインタフェースに関する処理を実行する。ユーザインタフェース処理部１１０は、ユーザからの各種操作入力を受け付ける。また、ユーザインタフェース処理部１１０はユーザに対して各種情報を通知する。たとえば、ユーザによるフリーリストとあふれフリーリスト（以下、これらをまとめていうときには、単に「リスト」とよぶ）の生成や再生成指示を受け付ける。ユーザからの指示は生成制御部１１２に通知される。
【００２４】
生成制御部１１２は、データ記憶領域管理装置１００に含まれる各機能ブロックを統括的に制御する。フリーリスト管理部１２０はフリーリストを管理する。フリーリスト管理部１２０は、生成制御部１１２の指示によりフリーリストの要素の生成や削除を行う。また、フリーリスト管理部１２０は、フリーリストに関する情報そのものを格納する。あふれフリーリスト管理部１３０はあふれフリーリストを管理する。あふれフリーリスト管理部１３０は、生成制御部１１２の指示によりあふれフリーリストの要素の生成や削除を行う。また、あふれフリーリスト管理部１３０は、あふれフリーリストに関する情報そのものを格納する。
【００２５】
データ取得部１２２は、外部からデータ記憶領域２００に記録すべきデータを取得する。このデータはデータ記憶領域２００から読み出すことにより取得されてもよい。たとえば、デジタルカメラにおいてデータ記憶領域管理装置１００を実現するときには、撮像された画像データはデータ取得部１２２により取得される。データ記録部１１４は、データ記憶領域２００にデータを記録する。データ記録部１１４は、フリーリスト管理部１２０およびあふれフリーリスト管理部１３０がそれぞれ管理するフリーリストおよびあふれフリーリストに基づいて、データの記録位置を特定する。データ記録部１１４は、データをクラスタ単位に分割して記録する。データ記録部１１４がデータ記憶領域２００からデータを削除したときには、データ記録部１１４はその旨を生成制御部１１２に通知する。生成制御部１１２は、データの削除処理に基づきフリーリスト管理部１２０やあふれフリーリスト管理部１３０がそれぞれ管理するリストの内容を更新する。
【００２６】
状態検出部１１６は、各クラスタの使用状態を検出する。連続検出部１１８は、状態検出部１１６が検出した各クラスタの使用状態に基づいて、空き連続クラスタを検出する。フリーリスト管理部１２０や、あふれフリーリスト管理部１３０はこの空き連続クラスタに基づいて要素を生成する。
【００２７】
図６は、データアクセスに伴いデータ記憶領域管理装置１００がリストを更新する過程を示すフローチャートである。データ記録部１１４がデータ記憶領域２００からデータを削除したとき（Ｓ１０のＹ）、フリーリスト管理部１２０およびあふれフリーリスト管理部１３０の双方または一方は、生成制御部１１２からの指示に基づきクラスタ解放処理を実行する（Ｓ１４）。処理後、Ｓ１０に戻る。クラスタ解放処理については、図７に関連して後に詳述する。
【００２８】
データ削除ではなく（Ｓ１０のＮ）、データ記録部１１４がデータ記憶領域２００にデータを記録するときには（Ｓ１６のＹ）、フリーリスト管理部１２０およびあふれフリーリスト管理部１３０の双方または一方は、生成制御部１１２からの指示に基づきクラスタ獲得処理を実行する（Ｓ１８）。処理後、Ｓ１０に戻る。クラスタ獲得処理については、図９に関連して後に詳述する。
【００２９】
データ記録ではなく（Ｓ１６のＮ）、ユーザインタフェース処理部１１０がユーザからリスト再生成指示を受け付けたときには（Ｓ２０のＹ）、フリーリスト管理部１２０およびあふれフリーリスト管理部１３０の双方または一方は、生成制御部１１２からの指示に基づきリストの再生成を実行する（Ｓ２２）。リストの再生成処理については、図１０に関連して後に詳述する。リスト再生成指示がなければ（Ｓ２０のＮ）、Ｓ２２はスキップされる。電源停止などによる処理終了がなければ（Ｓ２４のＮ）、処理はＳ１０に戻る。ユーザが処理の終了を指示したときには（Ｓ２４のＹ）、以上の処理を終了する。なお、リスト再生成は、ユーザによる明示的な指示の他にも所定のタイミングで実行されてもよい。たとえば、記録媒体の空きクラスタの残り容量が予め定められた閾値を下回ったとき生成制御部１１２はリストの再生成を指示してもよい。また、あふれフリーリストの要素数が所定数以上になったとき、生成制御部１１２はリストの再生成を指示してもよい。あるいは、生成制御部１１２は周期的なタイミングでリストの再生成を指示してもよい。
【００３０】
また、たとえば、デジタルカメラなどの小型機器において本実施例におけるデータ記憶領域管理装置１００を実現する場合には、この装置は機器の処理負荷を検出する処理負荷検出部を備えてもよい。たとえば、撮影中でないときや充電時においては、デジタルカメラの処理負荷は通常小さい。処理負荷検出部は、メモリの使用率、ＣＰＵ（Central Processing Unit）の占有状態などの指標にもとづき処理負荷値を算定し、その値が所定値以下となったとき、あるいは、所定値以下の状態が所定時間継続したときに、生成制御部１１２にその旨の信号を送る。生成制御部１１２は、この信号に基づいてリストの再生成を指示する。処理負荷がかかっていないタイミングでリストの再生成処理を実行するため、機器の処理パフォーマンスをなるべく落とさないようにデータ記憶領域の管理を行うことができる。
【００３１】
図７は、図６のＳ１４の処理を更に詳細に示すフローチャートである。データ記録部１１４がデータ記憶領域２００からデータを削除すると、状態検出部１１６は使用クラスタから空きクラスタとなる領域を検出する（Ｓ３０）。連続検出部１１８はこの削除処理に伴い生成される空き連続クラスタ（以下、データ削除によって新たに生成される空き連続クラスタのことを「新生成空き連続クラスタ」とよぶ）を検出する。複数の新生成空き連続クラスタが生成される場合には、Ｓ３２以降の処理はこれら各新生成空き連続クラスタについて実行される。
【００３２】
フリーリスト管理部１２０がフリーリストを持たず、この新生成空き連続クラスタを管理するために新規にフリーリストを作成する必要がある場合には（Ｓ３２のＹ）、フリーリスト管理部１２０はこの新生成空き連続クラスタを管理するためのフリーリストの要素を生成する（Ｓ４６）。Ｓ３２のＹの場合の一例としては、データ記憶領域２００に全く空きクラスタが存在しない状態から、データが削除された場合が考えられる。
【００３３】
Ｓ３２において、フリーリスト管理部１２０が既にフリーリストを有するとき（Ｓ３２のＮ）、フリーリスト管理部１２０は新生成空き連続クラスタを既存のフリーリストの要素が管理する第１領域に連結可能か否かを判定する（Ｓ３４）。あるフリーリストの要素が管理する第１領域と新生成空き連続クラスタが隣り合う場合は、これらをまとめた空き連続クラスタが新たな第１領域となる。このとき、フリーリスト管理部１２０は該当する第１領域が新生成空き連続クラスタを含むよう連結する（Ｓ４４）。
【００３４】
図１に示す例では、クラスタ番号「０００」と「００１」のクラスタを第１領域として管理するフリーリストの要素が存在するとする。ここで、クラスタ番号「００２」と「００３」のクラスタのデータが削除され新生成空き連続クラスタが生成されると、このフリーリストの要素はクラスタ番号「０００」から「００３」までの４つの空きクラスタを第１領域として管理する。
【００３５】
あるいは、クラスタ番号「０００」と「００１」のクラスタを第１領域として管理するフリーリストの要素と、クラスタ番号「００５」のクラスタを第１領域として管理するフリーリストの要素が存在するとする。ここで、クラスタ番号「００２」から「００４」のクラスタのデータが削除され新生成空き連続クラスタが生成されると、このフリーリストの要素はクラスタ番号「０００」から「００５」までの６つの空きクラスタを第１領域として管理する。この場合には、フリーリストの要素の数が一つ減ることになる。
【００３６】
既存のフリーリストの要素へ新生成空き連続クラスタを連結不可能であれば（Ｓ３４のＮ）、フリーリスト管理部１２０は新たにフリーリストの要素を追加可能か否かを判定する（Ｓ３６）。既存のフリーリストの要素の数が先述の第１最大要素数以下であれば（Ｓ３６のＹ）、フリーリスト管理部１２０は新生成空き連続クラスタを第１領域として管理するフリーリストの要素を生成する（Ｓ４６）。既存のフリーリストの要素の数が第１最大要素数より大きければ（Ｓ３６のＮ）、フリーリスト管理部１２０は新生成空き連続クラスタのサイズが既存のフリーリストの要素のいずれかが管理する第１領域のサイズよりも大きいか否かを判定する（Ｓ３８）。大きくなければ（Ｓ３８のＮ）、あふれフリーリスト管理部１３０は新生成連続クラスタについてあふれフリーリストの要素を登録するための処理を実行する（Ｓ４２）。あふれフリーリストの要素を登録するための処理については図８に関連して後に詳述する。Ｓ３８において大きければ（Ｓ３８のＹ）、フリーリスト管理部１２０は新生成空き連続クラスタをフリーリストの要素として登録する（Ｓ４０）。また、フリーリスト管理部１２０はこの新生成空き連続クラスタのサイズよりも小さい第１領域を管理していたフリーリストの要素を削除する。この場合には、削除されたフリーリストの要素が管理していた第１領域を新生成空き連続クラスタとするあふれフリーリストの要素登録処理が実行される（Ｓ４２）。
【００３７】
なお、このフローチャートでは、フリーリストの要素は、その管理する第１領域のクラスタ数が大きい順にソーティングされることを前提としている。しかし、本発明は、これに限るものではなく、たとえば、クラスタ数が小さい順にフリーリストの要素を並べてもよい。また、第１領域のサイズが１００キロバイト以上の要素については小さい順にならべるというような、所定の条件に基づいて、フリーリストの要素を並べてもよい。これは後に示す図１０のＳ８４における処理判定についても同様である。すなわち、大きい順にソーティングされているときには大きいか否かの判定を行う。小さい順にソーティングされている場合には小さいか否かの判定を行う。ソーティングに上記のような条件設定がなされている場合には、所定の条件に基づいて判定される。
【００３８】
図８は、図７のＳ４２の処理を更に詳細に示すフローチャートである。あふれフリーリスト管理部１３０があふれフリーリストを有していない場合には（Ｓ５０のＹ）、あふれフリーリスト管理部１３０は図７の新生成空き連続クラスタを管理するためにあふれフリーリストの要素を新規生成する（Ｓ６０）。あふれフリーリストを有するとき（Ｓ５０のＮ）、あふれフリーリスト管理部１３０は新生成空き連続クラスタを既存のあふれフリーリストの要素が管理する第２領域に連結可能か否かを判定する（Ｓ５２）。連結可能であれば（Ｓ５２のＹ）、あふれフリーリスト管理部１３０は既存のあふれフリーリストの要素に新たな空き連続クラスタを連結する（Ｓ５８）。連結可否の判定方法および連結の方法は、図７のＳ３４およびＳ４４に関連して説明した方法と同様である。
【００３９】
また、Ｓ５２において、あふれフリーリストの所定の要素が管理する第２領域内の中に、新生成空き連続クラスタが包含される場合もＳ５８に処理が移行する。たとえば、図１におけるデータ記憶領域２００において、あふれフリーリストのある要素が、クラスタ番号「０００」から「００９」までの領域を第２領域として管理しているとする。新生成空き連続クラスタが、「００３」の場合、新生成空き連続クラスタは、この第２領域に包含される。この場合は、Ｓ５８において特に処理を行うことなくこのフローチャートを終了する。
【００４０】
既存のあふれフリーリストの要素へ新生成空き連続クラスタを連結不可能であれば（Ｓ５２のＮ）、あふれフリーリスト管理部１３０は新たにあふれフリーリストの要素を追加可能か否かを判定する（Ｓ５４）。あふれフリーリストの要素の数が先述の第２最大要素数以下であれば（Ｓ５４のＹ）、あふれフリーリスト管理部１３０は新生成空き連続クラスタを第２領域として管理するあふれフリーリストの要素を生成する（Ｓ６０）。追加不可能であれば、（Ｓ５４のＮ）、あふれフリーリスト管理部１３０は既存のあふれフリーリストの要素に複数の空き連続クラスタを管理させる（Ｓ５６）。すなわち、既存のあふれフリーリストの要素が管理する第２領域に新生成空き連続クラスタを含める。このとき、新生成空き連続クラスタにもっとも近い第２領域に、新生成空き連続クラスタが含まれる。第２領域が複数の空き連続クラスタを含むときには、あふれフリーリスト管理部１３０は管理フラグ領域２３６の管理フラグを「１」にする。
【００４１】
もっとも近い関係の候補が複数あるときは、連続ユニットのサイズによって合体させる優先順位を決定してもよい。たとえば、大きいサイズの連続ユニットを優先的にまとめて第２領域としてもよい。あるいは、小さいサイズの連続ユニットを優先的にまとめて第２領域としてもよい。また、若い論理アドレスの連続ユニットを優先的にまとめて第２領域としてもよい。あるいは、その逆でもよい。
【００４２】
あるいは、既存の二つのあふれフリーリストの要素を一つにまとめて、それらがそれぞれ管理する第２領域をまとめた領域を第２領域として管理するあふれフリーリストの要素を新たに生成してもよい。そして、あふれフリーリスト管理部１３０は、新生成空き連続クラスタを第２領域として管理するあふれフリーリストの要素を新規生成する。
【００４３】
図９は、図６のＳ１８の処理を更に詳細に示すフローチャートである。データ取得部１２２が取得したデータをデータ記録部１１４がデータ記憶領域２００に記録するとき、フリーリスト管理部１２０は第１領域に含まれる総空きクラスタ数が予め定められた閾値（以下、「再生成閾値」とよぶ）以下か否かを判定する（Ｓ７０）。再生成閾値より大きければ（Ｓ７０のＮ）、フリーリストが管理する空きクラスタ数は十分に多いと判断し、データ記録部１１４はフリーリストが管理する第１領域の位置をもとにデータを記録する（Ｓ７８）。Ｓ７０において、第１領域の総空きクラスタ数が、記録すべきデータが必要とするクラスタ数よりも大きければ、Ｓ７８の記録処理を実行するとしてもよい。
【００４４】
Ｓ７０において、再生成閾値以下であれば（Ｓ７０のＹ）、フリーリスト管理部１２０およびあふれフリーリスト管理部１３０は生成制御部１１２の指示により、各リストを再生成する（Ｓ７２）。リストの再生成処理は図１０に関連して後に詳述する。再生成後、第１領域に含まれる総空きクラスタ数が再生成閾値よりも大きくなればデータ記録可能と判定する。記録可能であれば（Ｓ７４のＹ）、データ記録部１１４はデータをデータ記憶領域２００に記録する（Ｓ７８）。記録不可能であれば（Ｓ７４のＮ）、ユーザインタフェース処理部１１０は記録不可の旨をユーザに警告して（Ｓ７６）、処理は終了する。ただし、フリーリストの総空きクラスタ数が要求されるクラスタ数よりも小さいときには、その旨をユーザに通知する。
【００４５】
図１０は、図６のＳ２２または図９のＳ７２の処理を更に詳細に示すフローチャートである。まず、生成制御部１１２からの再生成指示に伴い、あふれフリーリスト管理部１３０はあふれフリーリストの要素を一要素ずつ取得する（Ｓ８０）。次に、あふれフリーリスト管理部１３０は取得したあふれフリーリストの要素が管理する第２領域に含まれる空き連続クラスタを順次取得する（Ｓ８２）。例えば、図４に関連して説明したあふれフリーリストの要素２４０のように、複数の空き連続クラスタを管理しているような場合、Ｓ８２では、まず第１の空き連続クラスタが取得される。この場合には、クラスタ番号「００２８」から「００３１」までの連続クラスタが該当する。フリーリスト管理部１２０は、この空き連続クラスタがいずれかのフリーリストの要素が管理する第１領域の空き連続クラスタよりも大きければ（Ｓ８４のＹ）、Ｓ８２で取得した空き連続クラスタをフリーリストの要素に管理させる（Ｓ８６）。また、フリーリストの要素が管理していた第１領域の空き連続クラスタは、それにもっとも近いあふれフリーリストの要素にまとめて第２領域として管理させる。Ｓ８４において、大きくなければ（Ｓ８４のＮ）、Ｓ８６はスキップされる。
【００４６】
Ｓ８０において取得したあふれフリーリストの要素が管理する第２領域に含まれるすべての空き連続クラスタについてＳ８４、Ｓ８６に示した処理が完了していなければ（Ｓ８８のＮ）、処理はＳ８２に戻り、同じ第２領域に含まれる別の空き連続クラスタについて再び同様の処理を実行する。Ｓ８８において処理が完了すれば（Ｓ８８のＹ）、あふれフリーリスト管理部１３０はすべてのあふれフリーリストの要素についてＳ８２以降に示した処理が完了したか否かを判定する（Ｓ９０）。すべてのあふれフリーリストの要素について処理が完了すれば（Ｓ９０のＹ）、処理は完了する。Ｓ９０において完了していなければ（Ｓ９０のＮ）、処理はＳ８０にもどり、あふれフリーリスト管理部１３０は別のあふれフリーリストの要素を取得して同様の処理を実行する。
【００４７】
以上、実施の形態をもとに本発明を説明した。なお、上記実施の形態の「フリーリストの要素」、「フリーリスト管理部」、「あふれフリーリストの要素」、「あふれフリーリスト管理部」は、それぞれ、請求項に記載の「第１アドレスオブジェクト」、「第１オブジェクト生成部」、「第２アドレスオブジェクト」、「第２オブジェクト生成部」の一実施形態である。また、請求項に記載の「合体領域」とは、例えば図４のあふれフリーリストの要素２４０がこれの一実施形態に相当する。
【００４８】
また、本発明はこの実施の形態に限定されることなく、そのさまざまな変形例もまた、本発明の態様として有効である。例えば、上記実施の形態のデータ記憶領域管理装置１００は空き領域に関する情報に基づいて記憶領域管理を行うものであったが、これに代えて、使用領域に関する情報に基づいて記憶領域管理を行ってもいい。したがって、「空き連続クラスタ」に代えて、「使用連続クラスタ」もまた、請求項に記載の「連続ユニット」の一実施形態である。また、本発明の範囲は、ＦＡＴに限らずリライタブルな記録媒体用のフォーマットにおいて、その記録領域の管理に適用可能であることは当業者には理解されるところである。
【図面の簡単な説明】
【００４９】
【図１】記録媒体におけるデータ記憶領域においてデータが記録される態様を説明するための模式図である。
【図２】ビットマップ形式のデータ管理情報により、データ記憶領域においてデータが管理される態様を説明するための模式図である。
【図３】フリーリスト形式のデータ管理情報により、データ記憶領域においてデータが管理される態様を説明するための模式図である。
【図４】本実施例におけるデータ記憶領域管理方法により、データ記憶領域においてデータが管理される態様を説明するための模式図である。
【図５】データ記憶領域管理装置の機能ブロック図である。
【図６】データアクセスに伴いデータ記憶領域管理装置がリストを更新する過程を示すフローチャートである。
【図７】図６のＳ１４の処理を更に詳細に示すフローチャートである。
【図８】図７のＳ４２の処理を更に詳細に示すフローチャートである。
【図９】図６のＳ１８の処理を更に詳細に示すフローチャートである。
【図１０】図６のＳ２２または図９のＳ７２の処理を更に詳細に示すフローチャートである。
【符号の説明】
【００５０】
１００  データ記憶領域管理装置、１１０  ユーザインタフェース処理部、１１２  生成制御部、１１４  データ記録部、１１６  状態検出部、１１８  連続検出部、１２０  フリーリスト管理部、１２２  データ取得部、１３０  あふれフリーリスト管理部。
【図１】
2005227855.tif 000003
【図２】
2005227855.tif 000004
【図３】
2005227855.tif 000005
【図４】
2005227855.tif 000006
【図５】
2005227855.tif 000007
【図６】
2005227855.tif 000008
【図７】
2005227855.tif 000009
【図８】
2005227855.tif 000010
【図９】
2005227855.tif 000011
【図１０】
2005227855.tif 000012