(57)【要約】【課題】従来のＦＡＴファイルシステムでは、外部フラグメンテーションや内部フラグメンテーションが大きい。また、従来は、記録媒体全体の使用状況がわからず、また２つのクラスタにまたがったファイルの配置ができない。【解決手段】記録媒体１００上の連続する記録領域を、一定サイズの基本ブロック１０１毎に分割し、基本ブロック１０１単位でデータを配置して管理する第１の管理方法と、任意の基本ブロックを同一サイズのサブブロック１０２で複数分割し、サブブロック単位でデータを配置して管理する第２の管理方法を、記録データのサイズに応じて選択使用する。これにより、内部フラグメンテーションを最小にして記録領域を効率良く使用できる。また、サイズの大きいファイルは基本ブロックに記録することによって、外部フラグメンテーションの発生を最悪の場合でも基本ブロック単位に抑えることができる。【選択図】　　　　　　図１
2004013276.tif 000002
【特許請求の範囲】
【請求項１】
メモリ上に格納されたデータを中央処理装置が制御するインタフェース回路を介して記録媒体上に書き込むためのファイルシステムにおいて、
前記記録媒体上の連続する記録領域を一定サイズの基本ブロック毎に分割し、前記基本ブロック単位でデータを配置して管理する第１の管理方法と、任意の前記基本ブロックを同一サイズのサブブロックで分割し、該サブブロック単位でデータを配置して管理する第２の管理方法のうち、選択した一方の管理方法、または両方の管理方法を組み合わせた方法で、前記データを前記記録媒体に記録する手段と、
前記記録領域内の前記基本ブロック毎の状態を表すフラグの集合とその管理情報が記録されている第１のビットマップテーブルを前記記録媒体上に配置し、前記サブブロックに分割された前記基本ブロックは、その基本ブロック内のサブブロック毎の状態を表すフラグの集合とその管理情報が記録されている第２のビットマップテーブルを、該当する基本ブロック毎に対応付けて前記記録媒体上に配置する配置手段と
を有することを特徴するファイルシステム。
【請求項２】
前記第１のビットマップテーブルにおける前記基本ブロック毎の状態を表すフラグは、ある基本ブロックが前記第１の方法で使用されているか、前記第２の方法で使用されているかを示す第１のフラグと、その基本ブロックが使用可能かどうかを示す第２のフラグを含むことを特徴とする請求項１記載のファイルシステム。
【請求項３】
前記第２のビットマップテーブルにおける前記サブブロック毎の状態を表すフラグは、あるサブブロックに空き領域があるか、そうでないか示すフラグを含むことを特徴とする請求項１記載のファイルシステム。
【請求項４】
前記第１のビットマップテーブルは、前記基本ブロック毎の状態を表すフラグの集合であるビットマップテーブル本体のほかに、テーブルの内容を管理するための情報を含み、少なくとも、該第１のビットマップテーブルであることを示す識別情報、該第１のビットマップテーブルのサイズ、該第１のビットマップテーブル内のテーブル本体部分のサイズ、前記基本ブロックのサイズ、前記基本ブロックの数、前記サブブロックに分割された前記基本ブロックの数を持つことを特徴とする請求項１記載のファイルシステム。
【請求項５】
前記第２のビットマップテーブルは、前記サブブロックに分割された前記基本ブロック内のサブブロック毎の状態を表すフラグの集合であるビットマップテーブル本体のほかに、テーブルの内容を管理するための情報を含み、少なくとも該第２のビットマップテーブルであることを示す識別情報、対応付けられた前記基本ブロックを特定するための情報、該第２のビットマップテーブルのサイズ、該第２のビットマップテーブル内のテーブル本体部分のサイズ、前記基本ブロックのサイズ、前記サブブロックのサイズ、前記サブブロックの数を持つことを特徴とする請求項１記載のファイルシステム。
【請求項６】
前記配置手段は、前記第２のビットマップテーブルのサイズが、論理セクタサイズより大きくて該論理セクタサイズの倍数でない場合は、それぞれのビットマップテーブルにダミーデータを付加して前記論理セクタサイズの倍数にすることによって、前記第２のビットマップテーブルを際間無く連結した一塊の第２のビットマットマップテーブル群として配置し、前記第２のビットマップテーブルのサイズが前記論理セクタサイズより小さい場合は、各ビットマップテーブルのサイズが２のべき乗の倍数のバイト数になるようにダミーデータを付加し、隙間無く連結した一塊の第２のビットマップテーブル群として配置し、前記第１のビットマップテーブルと前記第２のビットマップテーブル群は、複数の論理セクタにまたがって配置される場合、どちらも連続する論理セクタに隙間無く配置することを特徴とする請求項１記載のファイルシステム。
【請求項７】
記録に先だって、指定したサイズの記録領域を予約領域として予め確保可能なファイルシステムであって、前記第１及び第２のビットマップテーブル内で対応するブロックの状態を表すフラグとして、該当するブロックが予約領域かどうかを示すフラグを含むことを特徴とする請求項１記載のファイルシステム。
【請求項８】
前記第１及び第２のビットマップテーブルは、ファイルの管理情報として一時削除状態を表すフラグを持ち、ファイルを一時削除状態にする場合、前記第１及び第２のビットマップテーブルにおけるファイルの配置情報はそのまま変更せずに、前記一次削除状態を表すフラグを設定することによって一時削除状態を表し、ファイルを通常状態に復帰させる時には、前記一次削除状態を表すフラグを元に戻すことによって通常状態に復帰させることを特徴とする請求項１記載のファイルシステム。
【請求項９】
前記第１及び第２のビットマップテーブルは、ブロック毎の状態を表すフラグの一つとしてブロック内に使用禁止セクタが含まれることを示すフラグを持ち、前記基本ブロック内に前記使用禁止セクタが存在し、そのサイズが予め定めた閾値より大きい場合は、その基本ブロック全体を欠陥ブロックとして扱い、前記第１のビットマップテーブル内の前記使用禁止セクタの存在を示すフラグをセットし、そのサイズが予め定めた閾値以下の場合は、その基本ブロックをサブブロック単位に分割し、前記第２のビットマップテーブル内の前記使用禁止セクタを含むサブブロックに対応する、前記フラグをセットすることを特徴とする請求項１記載のファイルシステム。
【請求項１０】
欠陥セクタが交替セクタで代替されている場合、少なくとも交替セクタが前記基本ブロックと一致していない場合、前記交替セクタを含む基本ブロックは、前記サブブロック単位に分割して使用することを特徴とする請求項１記載のファイルシステム。
【請求項１１】
前記第１及び第２の管理方法は、前記記録媒体上で連続するデータの塊（エクステント）を開始位置とサイズの組み合わせで表し、ファイルデータの配置を複数のエクステントの連続するリストとして管理することを特徴とする請求項１記載のファイルシステム。
【請求項１２】
前記基本ブロックのサイズは６１４４バイトの倍数であり、前記サブブロックのサイズは２０４８バイトの倍数で、かつ、前記基本ブロックのサイズのｋ分の１（ｋは３以上の自然数）であることを特徴とする請求項１記載のファイルシステム。
【請求項１３】
前記記録媒体を複数の連続領域に分割し、その分割した領域を、前記第１の管理方法だけを用いる第１の領域、前記第２の管理方法だけを用いる第２の領域、ファイルの最終部分にのみ、その部分のサイズが予め定めた値より小さい時に前記第２の管理方法を用い、それ以外は前記第１の管理方法を用いる第３の領域のうち、それぞれどの領域として使用しているかを示す情報を前記記録媒体上に管理情報として保存することを特徴とする請求項１記載のファイルシステム。
【請求項１４】
音声データ及び映像データの少なくとも一方のデータを前記基本ブロック単位に前記記録媒体に記録し、その再生を補助するための管理情報データを前記サブブロック単位に記録することを特徴とする請求項１記載のファイルシステム。
【請求項１５】
連続する記録領域が一定サイズの基本ブロック毎に分割され、前記基本ブロック単位でデータを配置して管理する第１の管理方法と、任意の前記基本ブロックを同一サイズのサブブロックで分割し、該サブブロック単位でデータを配置して管理する第２の管理方法のうち、選択した一方の管理方法、または両方の管理方法を組み合わせた方法で、前記データが記録されると共に、前記記録領域内の前記基本ブロック毎の状態を表すフラグの集合とその管理情報が記録されている第１のビットマップテーブルと、前記サブブロックに分割された前記基本ブロック内のサブブロック毎の状態を表すフラグの集合とその管理情報が記録されている第２のビットマップテーブルとが、該当する基本ブロック毎に対応付けて記録されていることを特徴する記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はファイルシステム及び記録媒体に係り、特に記録媒体にデータを記録再生する際の管理構造や管理方式を規定するに際し、記録媒体上の記録領域をどのように使用するかを定めたファイルシステム及び記録媒体に関する。
【０００２】
【従来の技術】
ファイルシステムは、記録媒体にデータを格納し、取り出すために、記録媒体上の記録領域をどのように使用するかを規定する。これまで様々なＯＳ（オペレーションシステム）や組み込み機器のため多くのファイルシステムが開発されてきたが、その中でＦＡＴファイルシステムは、歴史的に殆どすべてのＯＳでサポートされてきた基本的なファイルシステムの一つで、汎用的でデータ交換性に優れることから、リムーバブルメディアのデファクトスタンダードとなっている。
【０００３】
詳しくは後述するが、その特徴はクラスタと呼ばれる固定ブロック単位のデータ配置方式、ファイル・アロケーション・テーブル（Ｆｉｌｅ　Ａｌｌｏｃａｔｉｏｎ　Ｔａｂｌｅ：ＦＡＴ）でのクラスタチェインを用いた配置管理、階層ディレクトリによるファイル管理などである。
【０００４】
このＦＡＴファイルシステムについて簡単に説明する。記録媒体は一般にセクタと呼ばれる固定サイズの連続領域を最小単位としてデータの記録再生を行っている。データは記録再生に伴うエラーを回避するため、誤り訂正用の情報やそのほかの管理情報等を付加して記録再生されるが、有効データ部分については一般にそのサイズは２のべき乗で規定される。
【０００５】
例えば、一般に用いられるサイズは、ハードディスクの場合５１２バイト（＝２９バイト）で、ＣＤＲＯＭやＤＶＤＲＯＭ等の光ディスクの場合は一般に２０４８バイト（＝２１１バイト）である（小容量のＭＯは５１２バイト）。ただし、ハードディスクの場合、５１２バイト以外の２のべき乗の論理セクタサイズをとることも可能だが、実質的に５１２バイト以外で用いられることは殆どない。
【０００６】
大容量化した記録媒体においては、この論理セクタ数は膨大になり、効率良く管理するには不利なので、いくつかのファイルシステムでは複数の論理セクタを一定個数まとめて記録媒体を管理する手法をとっている。ＮＴＦＳやＦＡＴファイルシステムはこのようなファイルシステムの例である。
【０００７】
図２０はＦＡＴファイルシステムの構造を説明するための図で、全体は図２０（ａ）に示すように、システム領域１、２つのＦＡＴ２、３、ルートディレクトリ領域４、データ領域５から構成される。
【０００８】
データ領域５はクラスタと呼ばれる連続する複数セクタ単位に分割して使用され、クラスタと１対１に対応するエントリを持つ管理テーブルであるＦＡＴを使ってファイルの配置情報を管理する。各クラスタには、順番に番号（クラスタ番号）が振られる。
【０００９】
図２０（ａ）に２及び３で示すように、ＦＡＴは２つあって、１つは予備である。また、システム領域１にはＯＳのブートコードやファイルシステム全体の管理情報などが格納されている。記録データはディレクトリ上でファイルとして記録され、ルートディレクトリを頂点とする任意の木構造からなる階層構造を構成する。
【００１０】
ルートディレクトリ４以下のディレクトリはサブディレクトリと呼ばれ、１つの特殊なファイルとして管理される。ディレクトリの構造はルートディレクトリもサブディレクトリも同じで、ディレクトリエントリのテーブルになっている。
【００１１】
１つのディレクトリエントリには、記録データの内容を表すファイル名等の情報とともに、データの先頭が格納されているクラスタのクラスタ番号をファイルのエントリ情報として記録する。
【００１２】
ＦＡＴはクラスタ番号のテーブルになっており、図２０（ｂ）に示すように、ファイルエントリで示されるクラスタ番号に対応するエントリには、ファイルデータの連結状態を示すために次のクラスタ番号が記録され、複数のクラスタに分散されたデータのつながり（クラスタチェイン）を管理することができる。ファイルの最後のクラスタには最終クラスタであることを示す識別子（ＦＡＴ１６の場合、ＦＦＦＦ）が記録される。このように、ＦＡＴファイルシステムにおいては、ファイルはディレクトリとＦＡＴの２つを用いて管理される。
【００１３】
なお、クラスタ内に欠陥セクタがあると、そのクラスタは使用不可能な領域であることを示す識別子がＦＡＴに記録されるので、このクラスタは使用しない。従って、たとえ１セクタでも不良の領域があった場合は、そのセクタが属するクラスタ全体が使用不可能となるため、クラスタサイズが大きいほど効率的な使用の妨げになる。
【００１４】
ＦＡＴ上のクラスタエントリの内容は、クラスタ番号を意味するので、そのエントリに与えるビット数によって、ファイルシステム全体で扱えるクラスタの数が決まる。ＦＡＴファイルシステムには、そのビット数の違いで幾つかのバージョンがあり、ＦＡＴ１２、ＦＡＴ１６、ＦＡＴ３２ファイルシステムと呼ばれることがある。
【００１５】
ＦＡＴ１２、ＦＡＴ１６、ＦＡＴ３２などの数字の部分はクラスタ番号のビット数を示し、それぞれ１２ビット、１６ビット、３２ビットを意味している。従って、各ファイルシステムが扱えるクラスタの総数は、それぞれおよそ２の１２乗、２の１６乗、２の３２乗個程度になる。実際には予約番号等があるためにこれらの数字より若干小さい値となる。図２０（ｂ）に示すＦＡＴは、ＦＡＴ１６の例である。
【００１６】
ＦＡＴファイルシステムの場合、クラスタサイズは記録媒体の容量によってある一定値に決定され、記録媒体の容量が大きくなるほど大きくなる。図２１は代表的なファイルシステムの容量とクラスタサイズの関係を示す。
【００１７】
しかし、上記のＦＡＴファイルシステムでは、クラスタと呼ぶ一定サイズの記録単位でファイルの記録再生を行うため、記録単位のサイズがファイルサイズにとって必ずしも最適とはならない。
【００１８】
これを解決するための手段として、従来は特開平８−１０１７８３号公報では、通常のクラスタサイズのほかに、クラスタをさらにサブクラスタに分割して、２種類のクラスタサイズを用意しているファイルシステムが開示されている。これによって、大きいファイルは通常のクラスタの領域に、小さいファイルはサブクラスタの領域に、ファイルサイズに応じて選択して記録する。
【００１９】
図２２は上記の特開平８−１０１７８３号公報記載の従来のファイルシステムの一例の構成図を示す。このファイルシステムは、映像情報やオーディオ情報処理用のコンピュータ７に、キャッシュメモリ８を介して直接アクセス装置９としての磁気ディスク装置を接続して構成されており、磁気ディスク装置内の制御部は磁気ディスクに対するヘッダ部の制御と共に、コンピュータ７からの命令に従って、所定のファイルの読み書き制御をする。このとき、制御部は、磁気ディスクを、先頭番地からファイル・アロケーション・テーブルを格納する５１２ｋバイトのシステム領域Ｒ１と、個々のデータファイルを格納するデータ領域Ｒ２に分割して管理する。
【００２０】
データ領域Ｒ２は、５１２ｋバイトの複数のクラスタＣ１、Ｃ２、・・・、Ｃｘに分割され、更にクラスタは１２８ｋバイトの複数のサブクラスタＳＣ１、ＳＣ２、・・・、ＳＣ５に細分割管理してあり、システム領域Ｒ１に設定されたファイル・アロケーション・テーブルにデータ領域Ｒ２に割り付けるべきファイル情報を格納して管理するようにされている。
【００２１】
すなわち、この従来のファイルシステムでは、ファイルサイズの違いによる使用効率やアクセス効率の改善を図るために、記録媒体を、ファイル・アロケーション・テーブルを格納するシステム領域Ｒ１と、個々のデータファイルを格納するデータ領域Ｒ２に分割し、データ領域Ｒ２を大容量の複数のクラスタＣ１、Ｃ２、・・・、Ｃｘに分割するとともに、このクラスタを複数のサブクラスタＳＣ１、ＳＣ２、・・・、ＳＣ５に細分割できるようにしている。さらに、サブクラスタの先頭領域には、システム領域に格納されたファイル・アロケーション・テーブルに関連付ける第２のファイル・アロケーション・テーブルを配置し、サブクラスタ内のファイルの配置を管理している。
【００２２】
従って、ＡＶデータ等の大容量ファイルデータは、システム領域のファイル・アロケーション・テーブルの管理に従って、大容量のクラスタに割り付け、テキストデータ等の小容量のファイルデータはサブクラスタに割り付けることにより、記録媒体の使用効率を向上する。また、上記のサブクラスタＳＣ１、ＳＣ２、・・・、ＳＣ５への分割は、取り扱うべき複数のテキストファイル等の容量に基づいて、システムの初期設定時に予め固定することにより、記録媒体の使用効率を向上する。
【００２３】
なお、特開平８−１０１７８３号公報に記載の用語「ファイル・アロケーション・テーブル」は、ＦＡＴファイルシステムにおけるＦＡＴの名称と同じであるが、内容は異なるので注意を要する。特開平８−１０１７８３号公報における「ファイル・アロケーション・テーブル」は、ファイル名とそのクラスタチェインのリスト構造であり、ＦＡＴファイルシステムのようなクラスタエントリのテーブルは存在しない。
【００２４】
【発明が解決しようとする課題】
しかし、前記ＦＡＴファイルシステムにおけるクラスタによる記録領域の管理方法には一般に次のような弊害がある。
【００２５】
（ａ）外部フラグメンテーション
ＦＡＴファイルシステムのように、クラスタ単位でデータ配置を管理する媒体の運用を続けていると、ファイルの削除、作成といったファイル操作の繰り返しによって、図２３にＡで示すように、媒体上のファイル配置がクラスタ単位でばらばらになっていく。これを外部フラグメンテーションと呼び、外部フラグメンテーションの発生個所では、機械構造を持つ記録デバイスにおいてはヘッドシークが発生するためアクセス速度の低下を招くという欠点がある。
【００２６】
機械構造を持たないフラッシュメモリなどの電気的デバイスにおいては、中央処理装置（ＣＰＵ）の処理能力やバスの転送速度などが十分な場合は、軽微な問題ではあるものの、データ転送手続きを分割する手間等の増加によるパフォーンスの低下という影響がある。
【００２７】
この問題の解消のために、一般にはデフラグというツールを用い、クラスタ単位のデータの並び替えを行ってデータの連続化を行う方法がある。しかしデフラグの実行は膨大な時間とリソースの消費を招くため、アプリケーション実行時の重大な妨げになる。
【００２８】
（ｂ）内部フラグメンテーション
クラスタ単位でデータを扱うため、クラスタサイズ未満のファイルを記録すると、図２３にＢで示すように最終クラスタ内に未使用領域が発生する。これを内部フラグメンテーションまたはクラスタギャップと呼び、記録媒体の使用効率の低下を招く。ここでは、（ａ）の外部フラグメンテーションと対比する意味で内部フラグメンテーションという用語を用いる。一般に、記録容量が大きいほどクラスタサイズが大きくなるため、内部フラグメンテーションが増大し、記録媒体の使用効率が下がるという欠点がある。
【００２９】
（ｃ）欠陥領域
従来のＦＡＴファイルシステムでは、たとえ１セクタでも不良の領域があった場合は、そのセクタが属するクラスタ全体が使用不可能となるため、クラスタサイズが大きいほど効率的な使用の妨げになる。
【００３０】
（ｄ）交替領域
ＤＶＤ−ＲＡＭのように、デバイスが欠陥領域を自動的に交替領域に割り当てるものがあるが、欠陥領域の管理単位がクラスタサイズと一致しないため、クラスタ内の論理アドレスが連続していても物理アドレスは不連続になり、実質的に外部フラグメンテーションが発生していることと同じ状況になってしまう場合がある。
【００３１】
（ｅ）テーブルサイズ
ＦＡＴのテーブルサイズの最大値は、ほぼクラスタに与えるエントリのビット数とクラスタの数の積になるため、記録媒体の容量が大きい場合は膨大なサイズとなる。例えば、２ＧＢのＦＡＴ１６ファイルシステムの場合、ＦＡＴのサイズは約１２０ｋバイトである。新しくファイルを記録する場合は、事前にＦＡＴを調査して未使用領域を探す必要がある。この場合、１２０ｋバイトものテーブルをサーチして空き領域を探す必要があるため効率が悪い。
【００３２】
また、大きいサイズのテーブルをメモリ上に保持することは、システムリソースを圧迫し、特に組み込み用機器等、リソースが貧弱な機器にとっては甚だしく不利である。かといってメモリ上にテーブルを持たないと、上記データが必要になる度に、記録媒体にアクセスする必要があるため効率が低下するという問題がある。
【００３３】
次に、特定用途に対する問題点について説明する。近年、ハードディスクドライブ（ＨＤＤ）を用いて、ＡＶストリームのリアルタイム記録再生を行う機器が発売されるようになった。このＡＶストリームは、高いビットレートでリアルタイムに伝送する必要があるため、外部フラグメンテーションによるアクセス効率の低下は、リアルタイムの記録再生に障害となる場合がある。
【００３４】
そこで、クラスタ内の領域は連続領域に記録されることから、外部フラグメンテーションの影響を少なくするために、クラスタサイズを大きくする方法が考えられる。これによって、データに連続的にアクセスできるようになるため、アクセス速度の保証が可能になり、ＡＶストリーム等のリアルタイム記録再生に有利である。たとえ、外部フラグメンテーションが発生しても、もともとクラスタサイズが大きいため、ヘッドシークによるアクセス速度の低下を無視できる程度に下げることができる。
【００３５】
このようにクラスタサイズを大きくすると、外部フラグメンテーションの影響を最小化することが可能だが、その反面、サイズの小さなファイルに対して内部フラグメンテーションが増大し、ハードディスクの使用効率が低下するという問題がある。
【００３６】
すなわち、ＡＶストリームは一般にファイルサイズが大きくなるため、外部フラグメンテーションに関する問題は少ないが、これを管理するためのファイルや一般のファイルは、ＡＶストリームと比較するとサイズが小さく、しかも数多く作成されるため、これらのファイルに対する内部フラグメンテーションがハードディスクの効率的な使用を妨げていた。
【００３７】
また、図２２に示した特開平８−１０１７８３号公報記載の従来のファイルシステムでは、次のような課題がある。
【００３８】
（ａ）階層ディレクトリをサポートしていない。
ファイルの一覧がシステム領域内に存在する唯一のファイル・アロケーション・テーブルにまとめて配置されるので、階層ディレクトリを構成できない。
【００３９】
（ｂ）記録媒体全体の使用状況を示すテーブルが存在しない。
ファイル毎にそのクラスタチェインのリストが記述されているため、未使用のクラスタが直ちにわからない。新しいファイルを記録する際には、未使用のクラスタを把握する必要があるが、全体の使用状況がわからないので、すべてのファイルエントリからクラスタチェインを抜き出し、使用しているクラスタ番号から全体の使用／未使用クラスタのマップを再構成する必要があり、非効率的である。また、同じ理由から、使用可能な空き容量も直ちに知る方法がない。
【００４０】
（ｃ）第２のファイル・アロケーション・テーブルが散在している。
第２のファイル・アロケーション・テーブルは、分割するクラスタ内の先頭サブクラスタに配置されるので、少なくとも大規模クラスタ単位で記録媒体上に散在する。従って、複数の第２のファイル・アロケーション・テーブルにアクセスするためには、多くのヘッドシークが発生し、パフォーマンスの著しい低下を招く。このような状況は、例えば、全体の正確な空き領域のサイズを知るために、サブクラスタに分割された領域の中の空き領域をサーチする場合などに発生する。
【００４１】
（ｄ）サブクラスタに分割された２つの大容量のクラスタにまたがってファイルを配置することができない。
サブクラスタ領域に配置されるファイルの配置管理構造が１つのテーブル内で閉じているため、他のテーブルとまたがった配置が不可能である。従って、一旦サブクラスタ領域に格納されたファイルが追記書きこみでサイズが大きくなった場合の対応が、そのままではできない。
【００４２】
（ｅ）大容量のクラスタとサブクラスタにまたがってファイルを配置することができない。
大容量のクラスタに記録するファイルは、すべて大容量クラスタを使用する必要があるので、最終クラスタのデータを効率良く格納できない。すなわち、内部フラグメンテーションが発生する。
【００４３】
（ｆ）サブクラスタに格納されたファイルは間接参照になる。
記録媒体全体を管理するメインのテーブルと、サブクラスタの集合として使用するクラスタに対する第２のテーブルが存在するため、例えばサブクラスタ内のファイルの配置情報を取得するには、メインのＦＡＴから該当ファイルのロケーションをサーチした上で、そのロケーションに対応する第２のテーブルをサーチするため、テーブルを２回読みこむ必要があり、１回のテーブル読み込みで済む大容量のファイルよりも、オーバーヘッドがより大きくなるという欠点がある。
【００４４】
（ｇ）特定の用途に対するクラスタサイズの指針がない。
ＡＶストリームの伝送方式としては、ＭＰＥＧ２（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ　２）で規定されるトランスポートストリーム（ＴＳ）やプログラムストリーム（ＰＳ）がある。前者は主に放送系に使用され、パケットサイズは１８８バイトであるが、パケットの到着時刻によってシステムクロックをリカバーする必要があることなどから、ＴＳの記録時にはその到着時刻をタイムスタンプとしてパケットと一緒に記録することがＤＶＨＳ（登録商標）等で一般に行われている。このような付加情報量を含めたパケットサイズとしては、一般に１９２バイトが使用される。
【００４５】
後者は主にＤＶＤ等の蓄積系に使用され、パケットサイズは可変であるが、ＤＶＤの場合、光ディスクのセクタサイズ（２０４８バイト）との親和性から２０４８バイトが一般に使用される。後者の場合は、光ディスク媒体との親和性が良いのは当然であるが、２０４８バイトはＨＤＤで一般に用いられるセクタサイズ５１２バイトの整数倍（４倍）であるため、ＨＤＤとも同様に親和性が良い。
【００４６】
しかし、前者は１９２＝２６×３より、因数に３を含んでいるため、ＨＤＤや光ディスクにパケットを記録すると、パケットが２つのセクタにまたがる場合が発生する。一つのパケットは連続して記録再生することが望ましいが、ＦＡＴファイルシステムでは、ここで外部フラグメンテーションが発生する可能性がある。また、光ディスクにおいてはクラスタという概念は無く、ディスク上の連続セクタ領域（エクステント）毎に記録しており、各エクステントのサイズには制約がないため、エクステントの境界でパケットの分割が発生する可能性がある。
【００４７】
特開平８−１０１７８３号公報記載の従来のファイルシステムでは、大きいファイルと小さいファイルに対する効率的な格納だけを考慮しており、ＡＶストリームの性質に特化した配慮を行っていないので、ＦＡＴファイルシステムと同様な状況が発生する。
【００４８】
（ｈ）欠陥領域に対する配慮がない。
欠陥領域への記録を避けるための手段が上記の従来のファイルシステムには用意されていない。
【００４９】
本発明は以上の点に鑑みなされたもので、内部フラグメンテーションを最小にして記録領域を効率良く使用し得るファイルシステム及び記録媒体を提供することを目的とする。
【００５０】
また、本発明の他の目的は、ヘッドシーク等によるアクセス効率の低下を最小限にし得るファイルシステム及び記録媒体を提供することにある。
【００５１】
また、本発明の他の目的は、目的に合ったブロックや使用可能なブロックの場所を高速に検索し得るファイルシステム及び記録媒体を提供することにある。
【００５２】
また、本発明の他の目的は、何らかの原因でビットマップテーブルの配置情報が破壊された場合でも、配置情報を再構築し得るファイルシステム及び記録媒体を提供することにある。
【００５３】
また、本発明の他の目的は、管理情報を用途に応じて任意の値に設定し、保存できると共に、記録媒体全体の統一した使い方が可能なファイルシステム及び記録媒体を提供することにある。
【００５４】
また、本発明の他の目的は、必要に応じて、基本ブロック毎に最適なサブブロックサイズを設定することが可能なファイルシステム及び記録媒体を提供することにある。
【００５５】
また、本発明の他の目的は、第２のビットマップテーブルと対応する基本ブロックの対応付け情報が失われることがなく、基本ブロックの開始セクタアドレスと終了セクタアドレス（またはサイズ）を直接用いることで直ちに位置を特定できるファイルシステム及び記録媒体を提供することにある。
【００５６】
また、本発明の他の目的は、最終基本ブロックの内部フラグメンテーションの発生を最小限にし得るファイルシステム及び記録媒体を提供することにある。
【００５７】
また、本発明の他の目的は、複数の予約領域を区別して管理することができると共に、既にある予約領域ファイルを参照することによって確保した予約領域を利用し得るファイルシステム及び記録媒体を提供することにある。
【００５８】
また、本発明の他の目的は、予約領域を一括して管理し得るファイルシステム及び記録媒体を提供することにある。
【００５９】
また、本発明の他の目的は、予約領域を開放して、媒体の空き領域を増やしたり、最初の予約領域サイズが不充分であっても、外部フラグメンテーションの発生を最小限に抑えながら、動的に対応できるファイルシステム及び記録媒体を提供することにある。
【００６０】
また、本発明の他の目的は、高速な消去が可能で、復活したいファイルの検索も容易なファイルシステム及び記録媒体を提供することにある。
【００６１】
また、本発明の他の目的は、欠陥セクタがあった場合も、基本ブロック単位で使用不可にならず、正常な領域をサブクラスタ単位で利用できるファイルシステム及び記録媒体を提供することにある。
【００６２】
また、本発明の他の目的は、交替セクタがある場合、交替に伴うヘッドシークを避けることができるファイルシステム及び記録媒体を提供することにある。
【００６３】
また、本発明の他の目的は、基本ブロック単位とサブブロック単位が混在している状態のファイルの場合であっても、同じように管理することが可能なファイルシステム及び記録媒体を提供することにある。
【００６４】
また、本発明の他の目的は、ＦＡＴのクラスタを基本ブロックとサブブロック単位で管理することによって、ＦＡＴファイルシステム上で配置構造が同じファイルシステムを実現することが可能なファイルシステム及び記録媒体を提供することにある。
【００６５】
また、本発明の他の目的は、領域毎にエラー発生時の対応条件と、配置するデータの性質を関係付けることが可能なファイルシステム及び記録媒体を提供することにある。
【００６６】
更に、本発明の他の目的は、ある領域はリアルタイム性が要求されるＡＶデータの記録再生専用の領域に用いることができ、別な領域はＡＶデータと比較すると小さいサイズで、しかも重要な管理情報などのデータを記録する領域として用いることが可能な記録媒体を提供することにある。
【００６７】
【課題を解決するための手段】
上記の目的を達成するため、第１の発明のファイルシステムは、メモリ上に格納されたデータを中央処理装置が制御するインタフェース回路を介して記録媒体上に書き込むためのファイルシステムにおいて、記録媒体上の連続する記録領域を一定サイズの基本ブロック毎に分割し、基本ブロック単位でデータを配置して管理する第１の管理方法と、任意の基本ブロックを同一サイズのサブブロックで分割し、サブブロック単位でデータを配置して管理する第２の管理方法のうち、選択した一方の管理方法、または両方の管理方法を組み合わせた方法で、データを記録媒体に記録する手段と、記録領域内の基本ブロック毎の状態を表すフラグの集合とその管理情報が記録されている第１のビットマップテーブルを記録媒体上に配置し、サブブロックに分割された基本ブロックは、その基本ブロック内のサブブロック毎の状態を表すフラグの集合とその管理情報が記録されている第２のビットマップテーブルを、該当する基本ブロック毎に対応付けて記録媒体上に配置する配置手段とを有することを特徴とする。
【００６８】
この発明では、記録するデータの性質に応じて、大きいクラスタや小さいクラスタサイズで記録再生できるように、記録領域全体を基本ブロックと呼ぶ複数の大きいブロックで分割し、更にその中をより小さくて、それぞれが同じサイズのサブブロックに分割するようにしたため、データの性質に応じて、ブロック全体を１つの単位として使用する場合と、サブブロックを１つの単位として使用する場合を選択できる。また、基本ブロック単位で記録する場合でも、ファイルの最後の部分はサブブロックに配置することで、さらに使用効率を上げることができる。また、第１及び第２のビットマップテーブルを用意することで、以上を効率良く管理することができる。
【００６９】
また、上記の目的を達成するため、第２の発明のファイルシステムは、第１のビットマップテーブルにおける基本ブロック毎の状態を表すフラグは、ある基本ブロックが第１の方法で使用されているか、第２の方法で使用されているかを示す第１のフラグと、その基本ブロックが使用可能かどうかを示す第２のフラグを含むことを特徴とする。
【００７０】
この発明では、各基本ブロックの状態を表す複数のフラグを用意し、これをまとめた第１のビットマップテーブルを持つようにしたため、上記の複数のフラグにより、（１）基本ブロック単位で使用するか、複数のサブブロックに分割して使用するか、（２）基本ブロック単位で使用する場合、その基本ブロックが未使用かどうか、（３）複数のサブブロックに分割して使用する場合、未使用のサブブロックがあるかどうか、（４）予約領域かどうか、（５）欠陥領域があるために使用できないかどうか、などの状態を表すことができる。
【００７１】
また、上記の目的を達成するため、第３の発明のファイルシステムは、第２のビットマップテーブルにおけるサブブロック毎の状態を表すフラグは、あるサブブロックに空き領域があるか、そうでないか示すフラグを含むことを特徴とする。
【００７２】
この発明では、各サブブロックの状態を表す複数のフラグを用意し、これをまとめた第２のビットマップテーブルを基本ブロック毎に持つようにしたため、上記の複数のフラグにより、（１）未使用かどうか、（２）予約領域かどうか、（３）欠陥領域があるために使用できないかどうかなどの状態を表すことができる。
【００７３】
また、上記の目的を達成するため、第４の発明のファイルシステムは、第１のビットマップテーブルが、基本ブロック毎の状態を表すフラグの集合であるビットマップテーブル本体のほかに、テーブルの内容を管理するための情報を含み、少なくとも、第１のビットマップテーブルであることを示す識別情報、第１のビットマップテーブルのサイズ、第１のビットマップテーブル内のテーブル本体部分のサイズ、基本ブロックのサイズ、基本ブロックの数、サブブロックに分割された基本ブロックの数を持つことを特徴とする。この発明では、用途に応じて基本ブロックのサイズや数を任意の値に設定して保存できる。
【００７４】
また、上記の目的を達成するため、第５の発明のファイルシステムは、第２のビットマップテーブルが、サブブロックに分割された基本ブロック内のサブブロック毎の状態を表すフラグの集合であるビットマップテーブル本体のほかに、テーブルの内容を管理するための情報を含み、少なくとも第２のビットマップテーブルであることを示す識別情報、対応付けられた基本ブロックを特定するための情報、第２のビットマップテーブルのサイズ、第２のビットマップテーブル内のテーブル本体部分のサイズ、基本ブロックのサイズ、サブブロックのサイズ、サブブロックの数を持つことを特徴とする。この発明では、用途に応じてサブブロックのサイズや数を任意の値に設定して、保存することができる。
【００７５】
また、上記の目的を達成するため、第６の発明のファイルシステムは、配置手段を、第２のビットマップテーブルのサイズが、論理セクタサイズより大きくて論理セクタサイズの倍数でない場合は、それぞれのビットマップテーブルにダミーデータを付加して論理セクタサイズの倍数にすることによって、第２のビットマップテーブルを際間無く連結した一塊の第２のビットマットマップテーブル群として配置し、第２のビットマップテーブルのサイズが論理セクタサイズより小さい場合は、各ビットマップテーブルのサイズが２のべき乗の倍数のバイト数になるようにダミーデータを付加し、隙間無く連結した一塊の第２のビットマップテーブル群として配置し、第１のビットマップテーブルと第２のビットマップテーブル群は、複数の論理セクタにまたがって配置される場合、どちらも連続する論理セクタに隙間無く配置することを特徴とする。
【００７６】
この発明では、第２のビットマップテーブルのサイズが論理セクタサイズより大きい場合、最後にダミーデータを付加することによって論理セクタサイズの倍数にしてすべての第２のビットマップテーブルを連結し、第２のビットマップテーブルのサイズが論理セクタサイズより小さい場合、２のべき乗の倍数になるようにダミーデータを付加してすべての第２のビットマップテーブルを連結するようにしたため、複数の第２のビットマップテーブルから特定の第２のビットマップテーブルを容易に検索できる。また、第１のビットマップテーブルの直後に第２のビットマップテーブル群を配置すれば、ファイルシステムのマウント時に配置情報を一度に取得できるため都合がよい。
【００７７】
また、上記の目的を達成するため、第７の発明のファイルシステムは、記録に先だって、指定したサイズの記録領域を予約領域として予め確保可能なファイルシステムであって、第１及び第２のビットマップテーブル内で対応するブロックの状態を表すフラグとして、該当するブロックが予約領域かどうかを示すフラグを含むことを特徴とする。
【００７８】
この発明では、媒体上でできるだけ連続してデータが配置されることを保証するために、記録領域を予約して、そこにデータを記録する。このため、この発明ではビットマップテーブルのフラグには、予約領域であることを示すフラグを用意し、予約領域はその管理情報に予約領域であることを示すフラグを持つ特別なファイル（予約領域ファイル）としてファイルの記録に先だって用意する。
【００７９】
予約領域ファイルには、そこに記録する予定のファイルを識別するための情報を書き込むことができるようにする。予約領域に記録するファイルには、予約領域ファイルの識別情報を書きこめるようにし、相互に参照できるようにする。予約領域のサイズが基本ブロックよりも大きいときは、予約領域として指定したサイズが基本ブロックの倍数でない場合でも、そうなるように切り上げる。予約領域ファイルは予め定めた特定めディレクトリをまとめて管理することによって、パーティション全体の予約領域の管理を容易にする。
【００８０】
また、上記の目的を達成するため、第８の発明のファイルシステムは、第１及び第２のビットマップテーブルは、ファイルの管理情報として一時削除状態を表すフラグを持ち、ファイルを一時削除状態にする場合、第１及び第２のビットマップテーブルにおけるファイルの配置情報はそのまま変更せずに、一次削除状態を表すフラグを設定することによって一時削除状態を表し、ファイルを通常状態に復帰させる時には、一次削除状態を表すフラグを元に戻すことによって通常状態に復帰させることを特徴とする。
【００８１】
この発明では、ファイルを一時的に削除する場合は、ビットマップのフラグはそのまま変更せずに、一時的に削除された状態を表すフラグをセットし、一時的に削除したファイルを復活させる場合は、一時削除フラグを元に戻すだけで通常の状態に復帰させるようにしたため、削除と復活を高速に実現できる。
【００８２】
また、全ての一時削除ファイルはパーティション内でまとめて参照できるように、全ての一時削除ファイルの識別情報を一つのテーブルで管理したり、同一ディレクトリ内の一時削除ファイルをまとめて参照できるように、少なくとも一時削除ファイルが存在するディレクトリについては、ディレクトリ毎に一時削除ファイルのテーブルで管理することも可能である。
【００８３】
また、上記の目的を達成するため、第９の発明のファイルシステムは、第１及び第２のビットマップテーブルは、ブロック毎の状態を表すフラグの一つとしてブロック内に使用禁止セクタが含まれることを示すフラグを持ち、基本ブロック内に使用禁止セクタが存在し、そのサイズが予め定めた閾値より大きい場合は、その基本ブロック全体を欠陥ブロックとして扱い、第１のビットマップテーブル内の使用禁止セクタの存在を示すフラグをセットし、そのサイズが予め定めた閾値以下の場合は、その基本ブロックをサブブロック単位に分割し、第２のビットマップテーブル内の使用禁止セクタを含むサブブロックに対応する、フラグをセットすることを特徴とする。
【００８４】
この発明は、欠陥領域がある場合、そのサイズが予め定めた閾値より大きい場合は、欠陥領域を含む基本ブロック全体を使用禁止セクタとして第１のビットマップテーブルの該当する基本ブロックの欠陥領域フラグをセットして、この基本ブロック全体を欠陥ブロックとして扱い、そのサイズが予め定めた閾値以下の場合は、その基本ブロックをサブブロック単位に分割し、欠陥領域を含むサブブロックに対する第２のビットマップテーブルの欠陥領域フラグをセットして、そのサブブロックを使用禁止とすることによって、その他のサブブロックが利用できるようにする。
【００８５】
また、上記の目的を達成するため、第１０の発明のファイルシステムは、欠陥セクタが交替セクタで代替されている場合、少なくとも交替セクタが基本ブロックと一致していない場合、交替セクタを含む基本ブロックは、サブブロック単位に分割して使用することを特徴とする。
【００８６】
また、上記の目的を達成するため、第１１の発明のファイルシステムは、第１及び第２の管理方法を、記録媒体上で連続するデータの塊（エクステント）を開始位置とサイズの組み合わせで表し、ファイルデータの配置を複数のエクステントの連続するリストとして管理することを特徴とする。
【００８７】
また、上記の目的を達成するため、第１２の発明のファイルシステムは、基本ブロックのサイズは６１４４バイトの倍数であり、サブブロックのサイズは２０４８バイトの倍数で、かつ、基本ブロックのサイズのｋ分の１（ｋは３以上の自然数）であることを特徴とする。
【００８８】
この発明では、基本ブロックのサイズが２０４８×３（＝６１４４バイト）になるように設定することによって、論理セクタサイズ５１２バイトのＨＤＤと２０４８バイトの光ディスク系のメディアのどちらのおいても、ＭＰＥＧ　ＴＳやＭＰＥＧ　ＰＳで伝送されるＡＶデータのパケットが基本ブロック境界で分断されるのを防ぐことができる。
【００８９】
また、上記の目的を達成するため、第１３の発明のファイルシステムは、記録媒体を複数の連続領域に分割し、その分割した領域を、第１の管理方法だけを用いる第１の領域、第２の管理方法だけを用いる第２の領域、ファイルの最終部分にのみ、その部分のサイズが予め定めた値より小さい時に第２の管理方法を用い、それ以外は第１の管理方法を用いる第３の領域のうち、それぞれどの領域として使用しているかを示す情報を記録媒体上に管理情報として保存することを特徴とする。この発明では、運用中の領域の過不足に応じて、領域の境界を移動したり、新たな領域を挿入したり、削除することによって、ダイナミックな運用を可能にする。
【００９０】
また、上記の目的を達成するため、第１４の発明のファイルシステムは、音声データ及び映像データの少なくとも一方のデータを基本ブロック単位に記録媒体に記録し、その再生を補助するための管理情報データをサブブロック単位に記録することを特徴とする。
【００９１】
また、上記の目的を達成するため、第１５の発明の記録媒体は、連続する記録領域が一定サイズの基本ブロック毎に分割され、基本ブロック単位でデータを配置して管理する第１の管理方法と、任意の基本ブロックを同一サイズのサブブロックで分割し、サブブロック単位でデータを配置して管理する第２の管理方法のうち、選択した一方の管理方法、または両方の管理方法を組み合わせた方法で、データが記録されると共に、記録領域内の基本ブロック毎の状態を表すフラグの集合とその管理情報が記録されている第１のビットマップテーブルと、サブブロックに分割された基本ブロック内のサブブロック毎の状態を表すフラグの集合とその管理情報が記録されている第２のビットマップテーブルとが、該当する基本ブロック毎に対応付けて記録されていることを特徴する。
【００９２】
また、本発明のファイルシステムは、サブブロックへの分割は必要に応じて行うものとし、最初から必要な場合はフォーマット時に行い、そうでなければ最初基本ブロックのみで使用し、必要に応じてサブブロックに分割するようにファイルシステムを運用するものとする。ある基本ブロックを初めてサブブロックに分割して使用する際は、基本ブロックのサイズと設定したいサブブロックのサイズを用いてサブブロックの数を決定し、これにサブブロック毎に必要なフラグのビット数を割り当てることによって、フラグのテーブル部分のサイズを求め、さらに前記管理情報部分をあわせて第２のビットマップテーブルの全体サイズを決定し、第２のビットマップテーブル用の管理情報を書き込む。
【００９３】
第１のビットマップテーブルに第２のビットマップテーブルの管理情報のデフォルト値があっても、これと異なる値を設定することもできるものとし、その場合は、第２のビットマップテーブルの管理情報を優先して参照する。
【００９４】
また、本発明は、第１のビットマップテーブルサイズが論理セクタサイズの倍数でない場合、最後にダミーデータを付加することによって論理セクタサイズの倍数にし、第１のビットマップテーブルの直後に第２のビットマップテーブル群を連続して配置する。
【００９５】
また、本発明は、記録するファイルのサイズが予約領域より小さかった場合、余った予約領域を破棄するかそのままにするかを指定するフラグを予約情報ファイルの管理情報として持つようにする。破棄する場合は、ファイルクローズ時に残った予約領域を解放する。
【００９６】
また、本発明は、予約領域ファイルの管理情報に、記録するファイルのサイズが予約領域より大きかった場合に予約領域を拡張する単位を格納する場所を設け、基本ブロック単位の予約領域である場合は、基本ブロックの倍数のサイズを格納し、サブブロック単位の予約領域である場合は、サブブロックの倍数のサイズを格納しておき、予約領域を越えてファイルを記録する場合、前記サイズを参照してこの単位で予約領域を拡張しながら記録を継続する。
【００９７】
また、本発明は、欠陥領域が欠陥管理機能によって交替領域に割り当てられている場合、交替領域が基本ブロックと一致している場合を除き、交替領域を含む基本ブロックをサブブロックに分割して使用する。ファイルの配置情報は、媒体上で連続するデータの塊（エクステント）を開始位置とサイズの組み合わせで表し、ファイルデータの配置を複数のエクステントの連続するリストとして管理する
【００９８】
【発明の実施の形態】
次に、本発明の実施の形態について図面と共に説明する。図１は本発明になるファイルシステムの一実施の形態の説明図を示す。本実施の形態は、記録媒体１００上の連続する記録領域を、一定サイズの基本ブロック１０１毎に分割し、基本ブロック１０１単位でデータを配置して管理する第１の管理方法と、任意の基本ブロックを同一サイズの、縦点線で区切られたブロックで示すサブブロック１０２で複数分割し、サブブロック単位でデータを配置して管理する第２の管理方法のうちの、両方又は選択した一方の管理方法に従いデータを記録又は再生するファイルシステムである。
【００９９】
また、記録媒体１００の全体（媒体がパーティションに分割されている場合はパーティション全体）に対して一つ、第１のビットマップテーブル１０３が記録配置されている。この第１のビットマップテーブル１０３は、記録媒体１００上の各基本ブロック１０１毎の状態を表すフラグの集合である第１のビットマップテーブル本体１０４と、その管理情報１０５とからなる。
【０１００】
また、サブブロック１０２に分割された基本ブロックは、その基本ブロック内のサブブロック毎の状態を表すフラグの集合である第２のビットマップテーブル本体１０７と、その管理情報１０８とからなる第２のビットマップテーブルが、記録配置されている。なお、基本ブロック１０１は記録媒体１００（又はパーティション）の先頭から始まらなくてもよい。また、先頭及び／又は最後の基本ブロックは、他の基本ブロック１０１と同一サイズでなくてもよい。更に、第２のビットマップテーブルは、連続して記録配置されなくてもよい。
【０１０１】
ここでは、ｎを２以上の自然数、ｍを任意の自然数とすると、複数の一定サイズの論理セクタで構成される記録媒体１００のデータ領域は、ｍｎセクタ毎の基本ブロック１０１に分割され、識別番号として先頭から順番にブロック番号を振る（ｍｎはｍ×ｎの意味）。各基本ブロック１０１は、連続するｍセクタからなる、ｎ個のサブブロック１０２に分割することができる。
【０１０２】
ここで、基本ブロック１０１のサイズは、後述するように、例えば、ＴＳパケット（１９２バイト）とＰＳパケット（２０４８バイト）とＨＤＤの論理セクタ（５１２バイト）と光ディスク媒体の論理セクタ（２０４８バイト）の最小公倍数６１４４バイトの倍数とされる。この場合は、基本ブロック１０１の境界においてＴＳパケットやＰＳパケットの分断が発生せず、ＡＶストリームデータの保存に適している。
【０１０３】
また、基本ブロック１０１のサイズを、３２ｋ×３＝９６ｋバイト（＝９８３０４バイト）の倍数にするようにしてもよい。この場合は、ＦＡＴ１２／ＦＡＴ１６／ＦＡＴ３２の最大クラスタサイズである３２ｋバイトとの整合性が良くなり、基本ブロックの境界とクラスタの境界を一致させることができる。
【０１０４】
また、サブブロック１０２のサイズは、例えば３２ｋバイト（＝３２７６８バイト）の倍数で、かつ、基本ブロック１０１のサイズのｋ分の１（ｋは３以上の自然数）に設定することにより、基本ブロック１０１だけでなくサブブロック１０２に格納されるファイルの配置もＦＡＴファイルシステムのクラスタで表現できる。このようにすれば、本ファイルシステムそのものを適用しない場合でも、ＦＡＴのクラスタを基本ブロックとサブブロック単位で管理することによって、ＦＡＴファイルシステム上で配置構造が同じファイルシステムを実現することができる。従って、ＦＡＴファイルシステムにコピーする場合に配置構造を保ったままコピーすることが可能になる。
【０１０５】
本発明では、メモリ上に格納されたデータを中央処理装置（ＣＰＵ）が制御するインタフェース（Ｉ／Ｆ）回路を介して記録媒体１００上に記録する場合、上記の基本ブロック１０１単位またはサブブロック１０２単位に上記のファイルシステムに従って記録する。また、本発明のファイルシステムによって記録媒体上に記録された記録済みのデータを、中央処理装置が制御するインタフェース回路を介して読み出し、メモリ上に格納する。
【０１０６】
記録媒体１００は、装置に内蔵された固定的なものでも、着脱可能なリムーバブルなものでもよい。また、媒体の種類は、ハードディスク、メモリカード、光ディスク等、Ｉ／Ｆ回路で対応可能なものなら何でもよい。メモリに格納するデータは、図示しない入出力回路によって入出力される、ＡＶデータやコンピュータの通常データ、ＣＰＵが生成したデータなど何でもよい。
【０１０７】
なお、基本ブロック１０１に配置するサイズの大きなファイルについて、ファイルの最終部分が格納される基本ブロックだけをサブブロックに分割することによって、最終基本ブロックの内部フラグメンテーションの発生を最小限にすることができる。
【０１０８】
サブブロック１０２に分割するかどうかは、予め閾値を設定しておき、その閾値以下の場合にサブブロック１０２に分割するようにすると、最終基本ブロックの使用率が高いときにサブブロック１０２に分割しなくてもよいので、分割の手続きを省略することができる。
【０１０９】
図２は本発明の記録媒体の記録領域の先頭付近の利用状況の一実施の形態を示す。同図において、各ブロックのサイズは前記ｍｎセクタ分のサイズであり、ブロック番号１，２，４が基本ブロック単位で使用され、ブロック番号０、３がｎ個のサブブロックに分割して使用されている。サブブロックへの分割は必要に応じて行うものとし、フォーマット時は分割されていない基本ブロックのみでもよい。
【０１１０】
記録媒体へのデータ配置をこのようにしておくことにより、一般に基本ブロックよりも大きいサイズのファイルは分割しないブロックにそのまま記録し、基本ブロックよりある程度小さいサイズのファイルは、サブブロックに記録することによって、２つのメリットが得られる。
【０１１１】
１つは、大きいファイルは基本ブロック単位でしか外部フラグメンテーションが発生しないので、ＨＤＤ等に適用した場合、ヘッドシークの発生を最小限にでき、アクセス効率が向上する点である。もう１つは、小さいファイルはサブブロックに配置するため、内部フラグメンテーションによって発生する可能性のある無駄な領域をサブブロックのサイズ以下に抑えることができる点である。
【０１１２】
サブブロックへ分割する際のサイズの基準は、任意に設定できるが、基本ブロックに占めるデータの割合が大きい場合に、基本ブロックとして使用するのが一般的にはよい。例えば、基本ブロックサイズの８０％を越える場合には基本ブロックとして扱い、そうでない場合はサブブロックに分割する。この設定によって、基本ブロックで発生する内部フラグメンテーションによる使用効率の低下は、最終基本ブロックサイズの２０％以下に抑えることができる。
【０１１３】
また、基本ブロックより大きいファイルは、複数の基本ブロックに書きこまれることになるが、最終ブロックについては基本ブロックより小さいファイルと同等の状況になるので、このようなファイルに対しては、最終ブロック以外は基本ブロック単位で扱い、最終ブロックについては、前記基準を適用して、場合によってはサブブロックに分割するようにしてもよい。
【０１１４】
なお、この基準は絶対的なものではなく、０％から１００％まで、システムやアプリケーションのポリシーによって自由に設定することができる。例えば、将来追加書き込みが予想されるファイルは、無条件に基本ブロックとして扱ったほうがよい。その理由は、サブブロックに分割した後で残りの領域に別なファイルが書き込まれた場合、追加書きこみデータを連続領域に書き込めないからである。逆に、アクセス性よりも使用効率の方が重要であるなら、サブブロックへの分割の優先度をあげ、必ず分割するようにしてもよい。
【０１１５】
次に、本発明において、前記２種類のデータ配置を効率良く管理する方法について説明する。
【０１１６】
本発明の特徴の１つは、データ領域の使用状況等を示す管理情報をデータの配置情報と分離して用意したことである。この管理情報は、データ領域の２種類の利用方法に対応した２種類のビットマップテーブルによって実現している。
各基本ブロックおよびサブブロックは、それぞれ自分のブロックに対応する数ビットのフラグを持ち、このフラグの組み合わせによって、ブロックの使用状態等を判断することができる。
【０１１７】
図３は本発明のファイルシステムにおけるブロック毎の管理情報を示すための各種フラグの定義例を示す。図３では、一つのブロックについて、ビット（ｂｉｔ）０〜３の４つのフラグを割り当てており、第１と第２のビットマップテーブルでほぼ共通に使用することができる。
【０１１８】
同図において、ビット０のスケール（ｓｃａｌｅ）フラグは、基本ブロックを基本ブロック全体として使用しているか、サブブロックに分割して使用しているかを示すフラグで、０のときサブブロックに分割して使用していることを示す。このフラグは、第１のビットマップテーブルで使用するときのみ有効で、第２のビットマップテーブルでは、使用しない。あるいは、ここでは解説しない別な用途に用いてもよい。
【０１１９】
ビット１のユーザブル（ｕｓａｂｌｅ）フラグは、そのブロックに利用可能な空き領域があるかどうかを示すフラグで、ｓｃａｌｅフラグの内容によって若干意味が異なり、ｓｃａｌｅフラグが１の時は、その基本ブロックが完全に未使用であるかどうかを示し、ｓｃａｌｅフラグが０の時は、完全に未使用なサブブロックが存在するかどうかを示す。すなわち、どちらの場合も利用可能なブロックがある場合に１にする。
【０１２０】
従って、ｓｃａｌｅフラグとｕｓａｂｌｅフラグの２つのビットを検索することによって、基本ブロック又はサブブロック単位で未使用なブロックがあるかどうか簡単に判断することができる。
【０１２１】
ビット２のプリアロケーテッド（ｐｒｅａｌｌｏｃａｔｅｄ）フラグは、そのブロックを記録に先だって予約しておくためのフラグであり、１のときにそのブロックが予約領域であることを示す。更に、ビット３のディフェクト（ｄｅｆｅｃｔ）フラグは、１のときはそのブロックに欠陥領域があって使用できないことを示し、０のときはそのブロックに欠陥領域がなく使用可能であることを示す。
【０１２２】
なお、図３は一例であって、予約領域をサポートしない場合は、プリアロケーテッドフラグはなくてもよい。また、欠陥領域をサポートしない場合は、ｄｅｆｅｃｔフラグはなくてもよい。また、図３に示す以外のその他の管理情報を示すフラグがあってもよい。
【０１２３】
また、第１のビットマップテーブルにおいては、ｓｃａｌｅフラグとｕｓａｂｌｅフラグの両方のビットが必要だが、第２のビットマップテーブルにおいては、ｕｓａｂｌｅフラグのビットのみ必要なので、ブロックに割り当てるビット数を前者は２ビット、後者は１ビットにしてもよい。構造を同じにすれば、処理を共通化できるメリットがあるので、同じビット数を割り当てて、第２のビットマップテーブルではｓｃａｌｅのフラグに相当するビットを使用せず、あるいは別な用途に用いるようにしてもよい。
【０１２４】
本実施の形態では、１つのブロックが持つ情報は図３に示すように高々数ビットであるため、ビットマップテーブル全体のサイズは極めて小さく、大容量の記録媒体であっても、媒体全体の使用状況等を高速に取得できる。また、サイズが小さいため、機器のメモリ上に読みこんでもシステムリソースを圧迫しないというメリットがある。
【０１２５】
例えばＦＡＴファイルシステムでは、データ領域の使用状況等とデータの配置情報が分離されず一体となっており、クラスタチェインを記録した１つの巨大なテーブルとなってしまう。このため、記録時には媒体の空き領域を探すのに時間と手間がかかる欠点があり、再生時もクラスタのリンク情報を辿らなければならず、やはり時間と手間がかかり、いずれも効率的でない。また、ＦＡＴのテーブルは、サイズが大きいためメモリ上でシステムのリソースを圧迫する。２ＧバイトのＦＡＴ１６ファイルシステムでは、ＦＡＴサイズは約１２０ｋバイトにもなる。
【０１２６】
これに対し、本実施の形態では、記録時はサイズの小さいビットマップテーブルをサーチして空き領域を探すだけなので、極めて高速に効率良く情報を取得でき、リソースも殆ど消費しない。また、再生時にはビットマップテーブルの参照は不要で、直接ファイルの管理情報から、配置状況を取得できる。
【０１２７】
前記２Ｇバイトの例で比較すると、基本ブロックサイズを１．５Ｍバイト、サブブロックサイズをＦＡＴ１６ファイルシステムと同じ３２ｋバイトとした場合、１つのブロックの状態を表すのに４ビット使用すると仮定すると、第１のビットマップテーブルの本体部分は僅か６８０バイト程度となり、ＦＡＴファイルシステムの１８０分の１である。第２のビットマップテーブルは、１つにつきテーブル部分が２４バイトと、これも非常に小さい。
【０１２８】
特開平８−１０１７８３号公報記載のファイルシステムでは、このようなテーブル自体が存在しないため、空き領域を把握するには、ファイル・アロケーション・テーブルを解析する必要がある。このテーブルはファイル毎にどのクラスタを使用しているかを示すだけになっているので、テーブル全体の使用状況、特に空き領域を調べるためには、全てのエントリをチェックして本当に空いているかどうかを知るための全体のテーブルを構築する必要がある。また、サブクラスタの使用状況を調べるには、各大容量クラスタの先頭部分に散在するサブクラスタの管理情報を集める必要があり、高速な処理は望めない。
【０１２９】
これに対して、本実施の形態においては、全体の使用状況を示すサイズの小さい第１のビットマップテーブルがあるため、全体の状況を素早く取得することが出来、必要に応じて参照される第２のビットマップテーブルは、まとめて配置することができるため、サブブロックの状況も素早く取得することができる。
【０１３０】
次に、本発明のファイルシステムの一実施の形態における第１及び第２のビットマップテーブルの一例について説明する。図４は第１のビットマップテーブルの一例を示し、図５は第２のビットマップテーブルの一例を示す。
【０１３１】
図４の第１のビットマップテーブルおいて、スペース・アロケーション・インフォメーション・デスクリプタ（Ｓｐａｃｅ＿Ａｌｌｏｃａｔｉｏｎ＿Ｉｎｆｏｒｍａｔｉｏｎ＿Ｄｅｓｃｒｉｐｔｏｒ）は、第１のビットマップテーブルの先頭に位置し、第１のビットマップテーブルであることを示す識別子の他、第１のビットマップテーブル全体のサイズなどの情報が格納されている。
【０１３２】
サイズオブＬＣ（Ｓｉｚｅ＿ｏｆ＿ＬＣ）は、基本ブロックのサイズ、サイズオブマップ（Ｓｉｚｅ＿ｏｆ＿ＭＡＰ）は、ビットマップ本体部分のサイズ、サイズオブＤＳＣ（Ｓｉｚｅ＿ｏｆ＿ＤＳＣ）は、デフォルトのサブブロックサイズ、サイズオブＤＳＣＭＡＰ（Ｓｉｚｅ＿ｏｆ＿ＤＳＣＭＡＰ）は、デフォルトの第２のビットマップテーブルのサイズ、ナンバー・オブ・ブロック（Ｎｕｍｂｅｒ＿ｏｆ＿Ｂｌｏｃｋ：ＮＢ）は、基本ブロックの数、ナンバー・オブ・スモールブロック（Ｎｕｍｂｅｒ＿ｏｆ＿Ｓｍａｌｌ＿Ｂｌｏｃｋ）は、基本ブロックのうち、サブブロックに分割されている基本ブロックの数、ＳＡＩアラインメント（ＳＡＩ＿Ａｌｉｇｎｍｅｎｔ）は、第１のビットマップテーブルをスタッフィングデータによって、５１２バイトの倍数のサイズにした場合のサイズ、ＳＡＩ＿Ｄアラインメント（ＳＢＩ＿ＤＡｌｉｇｎｍｅｎｔ）は、第２のビットマップテーブルをスタッフィングデータによって、５１２バイトの倍数のサイズにした場合のデフォルトサイズ、ベーシック・ブロック・ビットマップ（Ｂａｓｉｃ＿Ｂｌｏｃｋ＿Ｂｉｔｍａｐ）は、サイズがＮＢ／２バイトのビットマップ本体をそれぞれ示す。ベーシック・ブロック・ビットマップの要素の１つが、図３に示すフラグを表す。
【０１３３】
図５の第２のビットマップテーブルにおいて、スモール・ブロック・インフォメーション・デスクリプタ（Ｓｍａｌｌ＿Ｂｌｏｃｋ＿Ｉｎｆｏｒｍａｔｉｏｎ＿Ｄｅｓｃｒｉｐｔｏｒ）は、第２のビットマップテーブルの先頭に位置し、第２のビットマップテーブルであることを示す識別子の他、第２のビットマップテーブル全体のサイズなどの情報が格納されている。
【０１３４】
また、ベーシック・ブロック・ナンバー（Ｂａｓｉｃ＿Ｂｌｏｃｋ＿Ｎｕｍｂｅｒ）は、所属する基本ブロックの識別番号、ブロックアドレス（Ｂｌｏｃｋ＿Ａｄｄｒｅｓｓ）は先頭ブロックの論理ブロックアドレス（パーティション先頭を０番地とする論理セクタ単位のアドレス番号）、ＳＢＩアラインメント（ＳＢＩ＿Ａｌｉｇｎｍｅｎｔ）は、スタッフィングデータによって、５１２バイトの倍数のサイズにした場合のサイズで、第１のビットマップテーブルにおける、ＳＢＩ＿ＤＡｌｉｇｎｍｅｎｔと異なる場合、このＳＢＩ＿Ａｌｉｇｎｍｅｎｔの方を優先する。
【０１３５】
サイズオブＬＣ（Ｓｉｚｅ＿ｏｆ＿ＬＣ）は、対応する基本ブロックのサイズ、サイズオブＳＣ（Ｓｉｚｅ＿ｏｆ＿ＳＣ）はサブブロックサイズで、第１のビットマップテーブルにおけるサイズオブＤＳＣと異なる場合は、このサイズオブＳＣの方を優先する。サイズオブＳＣＭＡＰ（Ｓｉｚｅ＿ｏｆ＿ＳＣＭＡＰ）は、第２のビットマップテーブルのサイズで、第１のビットマップテーブルにおけるサイズオブＤＳＣＭＡＰと異なる場合は、このサイズオブＳＣＭＡＰの方を優先する。
【０１３６】
また、ナンバーオブＳＣ（Ｎｕｍｂｅｒ＿ｏｆ＿ＳＣ：ＮＳＣ）は、この基本ブロック内に含まれるサブブロックの数、スモール・クラスタ・ビットマップ（Ｓｍａｌｌ＿Ｃｌｕｓｔｅｒ＿Ｂｉｔｍａｐ）は、サイズがＮＳＣ／２バイトのビットマップ本体を示す。スモール・クラスタ・ビットマップの要素の１つ１つが、図３に示すフラグを表す。ただし、図３のＳｃａｌｅフラグは無効なフラグである。
【０１３７】
第１のビットマップテーブルは、媒体全体又は媒体がパーティションに分割されている場合はパーティション全体に対して１つ存在する。なお、安全性を高めるために、内容が同一なコピーを別に用意してもよい。第２のビットマップテーブルは、サブブロックに分割された基本ブロック毎に存在するので、０個から基本ブロックの個数までいろいろな場合がある。コピーを用意する場合は、コピーに応じた数だけ増加する。
【０１３８】
第１のビットマップテーブルには、第２のビットマップテーブルに関するデフォルトのサイズのパラメータがいくつか用意されており、サブブロックに分割する際のガイドラインとして使用することができる。第２のビットマップテーブルのパラメータを常にこのデフォルト値に従って作成することにより、第２のビットマップテーブルの管理がより容易になる。
【０１３９】
一方、すべてのパラメータをデフォルト値に合わせなくても、第２のビットマップテーブルのパラメータを優先するようにしたので、基本ブロック単位でサブブロックの利用方法を独自に設定することができ、記録するファイルの性質に応じたダイナミックな運用が可能である。例えば、ある基本ブロックと別な基本ブロックで、サブブロックのサイズを異なる値に設定することができる。どのような使い方をするかは、アプリケーションが自由に設定してよい。
【０１４０】
本発明によるファイルシステムは記録するデータを限定するものではないが、特定の用途のアプリケーションに関連するデータを記録するのに特に適している。このような例の１つとして、映像や音声をリアルタイムで記録し、プレイリストを使って通常再生し、サーチ情報を使って特殊再生するようなアプリケーションがある。
【０１４１】
ＡＶのストリームデータは、一般にサイズが大きく、リアルタイム性が要求されるため、本発明における基本クラスタ単位での記録再生に最適である。また、プレイリストやサーチのための情報など、ＡＶのストリーム以外のデータはＡＶデータと比較してサイズがはるかに小さいために、サブブロックに記録するのに最適である。また、基本ブロック単位に記録するファイルであっても、最終ブロックを有効に使用するため、最終ブロックのみサブブロックに分割してもよい。
【０１４２】
このようなアプリケーションでは、サイズの大きいデータと小さいデータが別に存在することが予めわかっているため、フォーマット時に記録媒体をいくつかの領域に分け、例えば基本ブロック単位で使用する領域とサブブロック単位で分割して使用する領域の２つに分けてもよい。
【０１４３】
このように、予め領域を定めて使用すると、基本ブロック中にサブブロックに分割されたエリアが存在しないため、混在した場合よりも基本ブロック単位の外部フラグメンテーションが発生しにくい。ただし、ファイルの最終部分が格納される基本ブロックについては、元々データ境界であるため、基本ブロックとして利用する領域であっても、例外的にサブブロックに分割し、空き領域を効率的に使用してもよい。
【０１４４】
このように、予め領域を定める場合は、使用中に領域の過不足が生じる可能性があるので、任意の領域を拡大、縮小、移動、挿入、削除、コピーなどの操作によってダイナミックに変更できるようにするとよい。
【０１４５】
ＡＶストリームデータは、データの信頼性よりもリアルタイム性が要求され、一方プレイリストやサーチのための情報などは、データの信頼性の方が重要なので、前記分割した領域に対して、予めエラー発生時のリカバリー方法を個別に設定するとよい。
【０１４６】
例えば、ＡＶストリームデータを記録再生する基本ブロック単位の領域は、エラー発生時のリトライを行わないものとし、プレイリストやサーチのためのデータを記録再生するサブブロック領域は、ある程度のリトライを許すことによって、データの性質に応じた最適な記録再生が行える。
【０１４７】
このようなエラー発生時の対応方法を設定した情報は、管理情報としてフォーマット時に記録媒体に保存しておくか、後から必要に応じて設定変更する。また、記録媒体がハードウェア的にそのような仕組みに対応している場合は、その仕組みに合わせた手続によって対応方法の設定もしくは参照を行うことにより、エラー発生に対応すればよい。
【０１４８】
次に、本発明におけるサブブロックの活用方法について説明する。サブブロックの活用方法には、サイズの小さいファイルへの適用のほか、欠陥領域への適用がある。記録媒体は、一般に初期不良あるいは使用中の不良発生によって欠陥領域が発生することがある。ＦＡＴファイルシステムにおいては、このような欠陥領域はクラスタ単位で欠陥であることを示し、使用しないようにする。従って、たとえ１セクタの不良であっても、クラスタ全体が使用不能になってしまう。このため、クラスタサイズが大きくなればなるほど、欠陥セクタのために無駄になる領域が増えてしまい、記録媒体の使用効率が下がってしまう。
【０１４９】
これに対して、本発明においては欠陥領域が存在する場合、これを含む基本ブロックをサブブロックに分割することで、無駄になる領域をサブブロック内にとどめることができる。さらに、サブブロックのサイズは基本ブロック毎に独自に設定することができるため、該当基本ブロックにおけるサブブロックのサイズを論理セクタサイズと等しくすることにより、無駄な領域を完全になくすことも可能である。
【０１５０】
また、基本ブロック全体が欠陥領域である場合は、その基本ブロックはサブブロックには分割せず、第１のビットマップテーブルの該当する基本ブロックに対応するｄｅｆｅｃｔフラグをセットする。
【０１５１】
また、サブブロックに分割すると正常なサブブロックがある場合は、その基本ブロックはサブブロックに分割して使用し、第２のビットマップテーブル内でサブブロック毎に欠陥領域があるかどうかをｄｅｆｅｃｔフラグに反映する。
【０１５２】
記録媒体によっては、ＤＶＤ−ＲＡＭのようにデバイスが欠陥管理機能を持っていて、欠陥領域を正常領域に自動的にマッピングし直すものがある。このように正常領域にマッピングされた領域のことを交替領域と呼ぶ。交替領域の存在は一般にアプリケーションからは見えないため、連続領域にアクセスしているつもりでも物理的には不連続にアクセスしていることがある。
【０１５３】
本発明では、基本ブロックを物理的に連続する領域で構成することによってＨＤＤなどにおけるヘッドシークを避け、ＡＶストリームなどのリアルタイムアクセスが必要な用途に最適に使用できることを可能にしている。従って、ＡＶストリームに使用する場合は、基本ブロック内に交替セクタが存在しない方がよい。サブブロックについては、そのような制約はないので交替領域があってもよい。
【０１５４】
従って、ＡＶストリームの記録再生を目的とする場合は、記録媒体上に交替セクタがある時は、前記交替セクタを含む基本ブロックをサブブロックに分割して使用することで、基本ブロック単位で使用する場合には交替セクタが存在しないことを保証することができる。なお、基本ブロック全体が交替セクタになっていて、交替領域が連続しているならそのまま基本ブロックとして使用してもよい。
【０１５５】
次に、予約領域を設定できるという本発明の特徴について説明する。予約した領域であることを示すために、第１、第２のビットマップテーブルともにブロックに対応したプリアロケーテッドフラグを持ち、このフラグがセットされていると、対応する基本ブロックまたはサブブロックが予約領域であることがわかる。従って、別なプロセスが同じ記録媒体を共有して使用している場合であっても、別なプロセスが予約領域を使用することがない。
【０１５６】
また、予約領域は一種の特別なファイル（予約領域ファイルと呼ぶことにする）として登録し、その管理情報にそこに記録するファイルの識別情報（ファイルシステムが使用するファイルの識別番号、あるいはファイル名など）を格納できるようにしておくと、その予約領域がどのファイルの記録のために予約してあるのか判断できる。この管理情報は、領域予約時に指定してもよいし、予約時には単に領域だけ確保し、実際に記録する段階で記録するファイルの識別子をセットしてもよい。
【０１５７】
また、予約領域ファイルは他の通常ファイルと区別できるように、その管理情報として予約領域ファイルであることを示す識別情報をもつようにする。予約領域はファイルとして管理するようにしたので、複数の予約領域を区別して管理することができる。また、予約した領域は予約領域ファイルとして参照できるので、予約する時点ではそこに記録するデータを特定せず領域の確保だけを行い、後で実際にデータを記録する際に、既にある予約領域ファイルを参照することによって確保した予約領域を利用することができる。
【０１５８】
また、予約領域に記録するファイルの管理情報には、予約領域ファイルを特定するための識別情報を格納できるようにする。これによって、予約領域ファイルとそこに記録するファイルの間で相互に参照できるようになる。
【０１５９】
あるファイルにおいて予約領域をセットして記録する場合、基本ブロック単位に記録するファイルの場合は、基本ブロック単位に予約領域を確保し、サブブロック単位に記録するファイルの場合は、サブブロック単位に予約領域を確保する。予約領域のサイズは、予約領域を確保する際に同時に指定するようにする。
【０１６０】
あるいは、指定したサイズが基本ブロックより大きいか小さいかによってどの単位で予約領域を確保するかを決めてもよい。例えば、指定したサイズが基本ブロックより大きい場合には基本ブロック単位の予約領域とし、小さい場合はサブブロック単位の予約領域としてもよい。この時、予約したブロックに対応するプリアロケーテッドフラグを予約領域としてセットする。この場合は、指定サイズが基本ブロックより大きくても、小さくてもビットマップ単位で予約領域かそうでないかを管理することができる。
【０１６１】
予約領域にデータを記録中に予約領域が足りなくなりそうな場合、予約領域の残りサイズが予め定めた量以下になると、予約領域を拡張する。予約領域を拡張する場合、拡張するサイズは予め定めたサイズ、または予約領域に作成時に決定したサイズ、または予約領域に記録するファイルをオープンした時点で決定したサイズのいずれかで拡張するものとし、そのサイズは基本ブロックまたはサブブロックの倍数とする。
【０１６２】
拡張する予約領域は、現在の予約領域の直後以降で利用可能な最初の基本ブロックまたはサブブロックから確保する。従って、基本ブロック単位で拡張する場合は、第１のビットマップテーブルを検索して、予約領域より後の利用可能な最初の基本ブロックを探す。
【０１６３】
サブブロック単位で拡張する場合は、予約領域が所属するサブブロックの第２のビットマップテーブル内に予約領域より後の利用可能なサブブロックがあるかを検索し、そこにない場合、あるいはそれでは不足する場合、次に利用可能な基本ブロックを第１のビットマップテーブルから検索し、そこをサブブロックに分割した上で先頭から順に予約領域として確保するか、サブブロックに分割した基本ブロックを第１のビットマップテーブルから探し、その中で利用可能な最初のサブブロックを探して確保する。
【０１６４】
もし、確保した領域よりも後に新たに確保する領域が見つからない場合は、媒体の先頭に戻って、空き領域を探す。予約領域ファイルは、後で予約領域を追加する場合の追加領域サイズを管理情報として持つことができる。追加領域サイズがない場合、あるいは特に指定しない場合は、基本ブロックまたはサブブロックの数倍のあらかじめ定めた単位で拡張するようにする。
【０１６５】
このように、本実施の形態では、予約領域にデータを記録している際に、予約領域が不足した場合、適切なサイズで予約領域を拡張できるようにしたので、最初の予約領域サイズが不充分であっても、外部フラグメンテーションの発生を最小限に抑えながら、動的に対応できる。
【０１６６】
他方、予約領域が余った場合、余った領域をそのまま残しておいてもよいし、解放してもよい。どちらにするかは、予め予約領域を作成する時点、あるいは、予約領域への記録を開始する時点で決めてもよいし、記録するファイルをクローズする時点で決めてもよい。
【０１６７】
解放する場合は、ビットマップ上のプリアロケーテッドフラグをリセットし、予約領域ファイルを削除する。そのまま残す場合は、ビットマップ上のプリアロケーテッドフラグと予約領域ファイルを残ったエリアに対応するように修正する。残った予約領域を利用して前記ファイルに追加書きこみをする場合は、前記ファイルには前記予約領域ファイルの識別情報があるので、これを参照することによって直ちに記録する場所の情報を取得できる。
【０１６８】
このように、本実施の形態では、予約領域にデータを記録している際に、記録終了時に予約領域が余った場合、その領域をそのまま予約領域として残しておくか、あるいは解放するかを、指定することができるので、例えば後から追加記録する可能性が大きい場合は、将来の記録に備えてそのまま予約領域を残し、追加記録する可能性が低い場合は、予約領域を開放して、媒体の空き領域を増やすような運用ができる。
【０１６９】
予約領域ファイルには、そこに記録する（または記録中の）ファイルを特定するための情報を持つことができるので、どのファイルを記録する予定なのか、あるいは、記録中なのかを判断することができる。これは、複数の予約領域が存在するときに、予約領域と記録するファイルを関係付けるのに特に有用である。
【０１７０】
予約領域に記録するファイルには、予約領域ファイルを特定するための識別情報を持つことができるようにしたので、記録を一旦終了し、後から記録を再開する場合に、予約領域が残っている場合は、これを直ちに参照することができる。領域確保だけを先に行って、後で記録するファイルを決めたい場合は、領域確保時は記録ファイルを指定せず、必要になった時点で記録ファイルを特定する情報を書くことができる。
【０１７１】
また、本実施の形態では、予約領域ファイルをまとめて１つの特定のディレクトリに配置するようにしているため、そこに記録するファイルが階層ディレクトリ上で散らばっていても、予約領域を一括して管理することができる。
【０１７２】
次に、本発明のＡＶストリームへの適用例として、ＭＰＥＧ２のトランスポートストリーム（ＴＳ）とプログラムストリーム（ＰＳ）の両方に適用可能な実施の形態について説明する。
【０１７３】
ＴＳは主に放送系に使用される１８８バイトのパケットサイズのストリームである。ＴＳはパケットの到着時刻によってデコーダのシステムクロックを管理するので、ＴＳパケットを記録する場合は、到着時刻におけるシステムのカウンタの値をタイムスタンプとしてパケットに付加して記録する方法がＤＶＨＳ等で一般に行われている。タイムスタンプやその他の付加情報を含めたパケットサイズは一般に１９２バイトである。
【０１７４】
一方、ＰＳは主にＤＶＤ等の蓄積系に使用され、パケットサイズは可変であるが、ＤＶＤの場合、光ディスクのセクタサイズ（２０４８バイト）との親和性から２０４８バイトが一般に使用される。このサイズはＨＤＤで一般に用いられるセクタサイズ５１２バイトの整数倍（４倍）であるため、ＨＤＤとも同様に親和性がよい。すなわち、光ディスクには１セクタに１パケット記録可能で、ＨＤＤには４セクタに１パケットを記録可能である。ＨＤＤの場合は４セクタをセットで扱うことによって容易に１パケットを扱うことが可能である。
【０１７５】
これに対し、ＴＳは１９２＝２６×３より、因数に３を含んでいるため、ＨＤＤや光ディスクにＴＳパケットを記録すると、パケットが２つのセクタにまたがる個所が発生する。一つのパケットは連続して記録再生することが望ましいが、一般にはパケットが分割される場所で外部フラグメンテーションが発生する可能性がある。
【０１７６】
例えば、ＦＡＴファイルシステムでは、連続しないクラスタにまたがってパケットが配置される可能性がある。ＦＡＴファイルシステム以外のファイルシステム、例えば光ディスクに用いられるＵＤＦ（Ｕｎｉｖｅｒｓａｌ　Ｄｉｓｋ　Ｆｏｒｍａｔ）などではクラスタという概念は無く、ディスク上の連続セクタ領域（エクステント）毎に記録しており、各エクステントのサイズには制約がないため、エクステントの境界で、パケットの分割が発生する可能性がある。
【０１７７】
これを避けるためには、ＰＳの場合は１個のパケットを複数個の連続するセクタで記録し、ＴＳの場合は複数個の連続するパケットを複数個の連続するセクタで記録するための制約を与える必要がある。
【０１７８】
そこで、ＴＳとＰＳで一般的に用いられるパケットサイズ１９２バイトと２０４８バイトの最小公倍数である６１４４バイト（＝６ｋバイト；１ｋバイトは１０２４バイト）の倍数を基本ブロックのサイズとすると、ＴＳ、ＰＳいずれのパケットを記録する場合でもパケットが２つの基本ブロックをまたがることがないので、基本ブロック単位の外部フラグメンテーションが発生しても問題ない。
【０１７９】
次に、配置されたデータ（ファイル）を配置方法に関わり無く、共通の構造で管理する方法について説明する。前述したように、２種類のブロックサイズ（すなわち、基本ブロックとサブブロックの各ブロックサイズ）に応じた２種類のビットマップテーブルを持つことは、これによって記録媒体の使用状況を効率良く検索できるので、特に記録時に必要なブロックサイズの空き領域を素早く取得するのに有効である。
【０１８０】
一方、特開平８−１０１７８３号公報記載の従来のファイルシステムに見られるように、単にディスクの使用効率やファイル配置だけを重視したファイルシステムの場合、特定のファイルにアクセスする場合、大容量クラスタに格納されたファイルと、小容量のサブクラスタに格納されたファイルでは、ファイルにアクセスする手続きが異なっている。
【０１８１】
後者は、マスターのファイル・アロケーション・テーブルに、第２のファイル・アロケーション・テーブルの場所と、エントリポイントが記されており、これを介した間接参照となっているため、ファイルの配置情報を取得するためには、前者と比較して１回多くの操作が必要である。特に、第２のファイル・アロケーション・テーブルは、大容量クラスタの先頭に配置されるため、そこへのアクセスはＨＤＤの場合ヘッドシークが発生することになり、アクセス効率がさらに低下する恐れがある。
【０１８２】
これに対し、本発明では、基本ブロックに格納されたファイルであっても、サブブロックに格納されたファイルであっても、あるいは、両者をどのように組み合わせて格納されたファイルであっても、同一の形式、手続きでアクセスすることができるため、サブブロックに格納されたファイルへのアクセスが不利になることはない。
【０１８３】
このため、本発明では、媒体上のデータを連続するセクタに配置されたデータの塊の集合として扱っている。このデータの一塊のことを一般にエクステントと呼び、一般に用いられているデータの管理形式の一つである。
【０１８４】
図６は本発明におけるファイル管理情報の一例を示す。ファイル管理情報は、ファイル本体と１対１に対応する一種のファイルである。同図において、ファイル・インフォメーション・ブロック・デスクリプタ（Ｆｉｌｅ＿Ｉｎｆｏｒｍａｔｉｏｎ＿Ｂｌｏｃｋ＿Ｄｅｓｃｒｉｐｔｏｒ）は、ファイル管理情報であることを示す識別子の他、ファイル管理情報全体のサイズなどの情報が格納されている。
【０１８５】
また、ファイル・インフォメーション（Ｆｉｌｅ＿Ｉｎｆｏｒｍａｔｉｏｎ）は、ファイル名、タイムスタンプ、アクセス属性などの各種属性、ファイルサイズ等が格納される。また、ナンバーオブエクステント（Ｎｕｍｂｅｒ＿ｏｆ＿Ｅｘｔｅｎｔ：ＮＥ）はエクステントの数、ファイルエクステント（Ｆｉｌｅ＿Ｅｘｔｅｎｔ）はＮＥ個のエクステントの並びである。
【０１８６】
エクステントの表現形式はいろいろあるが、基本的にはエクステント先頭データの媒体上のアドレスと、エクステントのサイズの組み合わせで表す。本発明の一実施の形態では、エクステントの先頭アドレスとしてパーティション先頭からの論理ブロックアドレスを用いているが、論理セクタアドレス等、媒体上の位置を特定できるアドレス情報であれば何を用いてもよい。また、エクステントサイズは、論理ブロック単位に丸めた値を用いているが、実際に使用しているバイト数を用いてもよい。論理ブロック単位に丸めた値を用いる場合は、ファイル・インフォメーションに格納されたファイルサイズから正確なバイト数を得ることができる。
【０１８７】
図７は本発明になる記録媒体の一実施の形態の記録情報の説明図を示す。同図において、記録媒体は同一サイズの基本ブロック毎に論理的に分割されており、データ領域の先頭から昇順に識別番号が割り当てられている。図７はその一部を取り出した例で、丸数字で示す４から１７までの基本ブロックと、その一部の拡大図を示している。基本ブロックのうち、丸数字の１３と１６はどちらも１２個の同一サイズのサブブロックに分割してある。
【０１８８】
なお、サブブロック数は１２個以外の数であってもよく、また基本ブロック毎に違う数であってもよい。また、サブブロックの取り扱いを容易にするために、基本ブロック内をすべて等サイズのサブブロックに分割することが望ましいが、基本ブロック内の最終ブロックのサイズが異なることを禁止するものではない。識別情報としては、基本ブロックの位置が特定できれば十分であり、上記のように基本ブロック毎に昇順につけられた識別番号を利用する場合は、基本ブロックのサイズと識別番号の積で、基本ブロックの開始位置が特定できる。基本ブロックの開始セクタアドレスと終了セクタアドレス（またはサイズ）を直接用いれば計算しなくても直ちに位置を特定できる。
【０１８９】
また、図７において、ファイルａとファイルｂは基本ブロック単位に記録した大きいサイズのデータである。このうち、ファイルａは３つの連続する基本ブロック（丸数字５、６、７）に配置されているため、１つのエクステントＥａ１で構成されているが、ファイルｂは２つのエクステントＥｂ１とＥｂ２に分かれており、ここで基本ブロック単位の外部フラグメンテーションが発生している。なお、ファイルｂの最終部分は、領域を有効活用するためにサブブロックに分割されている。
【０１９０】
ファイルｃとファイルｄは、サブブロック単位に記録した小さいサイズのデータである。ファイルｃは丸数字１３で示す基本ブロック中のサブブロックの識別番号７〜９の３つの連続するサブブロックに配置されているため、１つのエクステントＥｃ１で構成されている。これに対し、ファイルｄは丸数字１６で示す基本ブロック中の識別番号０〜３までの連続するサブブロックからなるエクステントＥｄ１と、識別番号７と８のサブブロックからなるエクステントＥｄ２の計２つのエクステントに分かれて配置されているため、ここでサブブロック単位の外部フラグメンテーションが発生している。以上をまとめると、表１に示すようになる。
【０１９１】
【表１】
2004013276.tif 000003
【０１９２】
なお、図７の例では説明のためにファイルを分割して媒体上にばらばらに配置したが、通常の使用時に空き領域がある場合は、できるだけ連続する領域に配置するように運用する。
【０１９３】
一つのファイルの配置情報はエクステントによって管理する。ファイルが媒体上で複数のエクステントに分かれている場合は、エクステント情報の並び（リスト）によって、その配置状態を表す。エクステントの情報は、エクステント先頭データの媒体上のアドレスと、エクステントのサイズの組み合わせで表す。一般に媒体へのアクセスは論理ブロック単位で行われるため、ファイルの先頭は論理ブロックの先頭から配置される。
【０１９４】
従って、通常、前記アドレスは論理ブロックアドレスなどのブロック単位のアドレスで表記される。また、サイズについても同じ理由から論理ブロック単位で指定されることが多い。論理ブロックのサイズは媒体によって異なり、一般にＨＤＤやメモリデバイス等では５１２バイト、光ディスク系では２０４８バイトが用いられる。実際のデータサイズは、論理ブロック以下の端数がでるため、最終論理ブロックについては、ファイル全体のサイズから有効データサイズを取得する。エクステントのサイズとしてバイト単位で指定するようにした場合は、全体のサイズ情報が無くても直接有効なデータサイズを取得することができる。
【０１９５】
図７において、４つのファイルａ〜ｄの配置情報を取り出してまとめると、表２に示すようになる。
【０１９６】
【表２】
2004013276.tif 000004
表２において、Ｓａ、Ｓｂ、Ｓｃ、Ｓｄはそれぞれファイルａ、ｂ、ｃ、ｄのファイルサイズ、Ｎａ、Ｎｂ、Ｎｃ、Ｎｄはエクステントの数、（Ａ＊，Ｅ＊）は１つのエクステント情報であり、Ａがエクステントの先頭論理ブロックアドレスを示し、Ｅがエクステントの論理ブロック単位のサイズを示す。＊はファイルの識別用に便宜的に付加したもので、ａ、ｂ、ｃ、ｄ　はそれぞれのファイルａ、ｂ、ｃ、ｄに対応する。数字はエクステントの番号である。
【０１９７】
図６と対応付けると、Ｓａ、Ｓｂ、Ｓｃ、Ｓｄはファイル・インフォメーション（Ｆｉｌｅ＿Ｉｎｆｏｒｍａｔｉｏｎ）内に格納される情報、Ｎａ、Ｎｂ、Ｎｃ、Ｎｄはナンバーオブエクステント（Ｎｕｍｂｅｒ＿ｏｆ＿Ｅｘｔｅｎｔ：ＮＥ）、（Ａ＊，Ｅ＊）はファイル・エクステント（Ｆｉｌｅ＿Ｅｘｔｅｎｔ）［ＮＥ］である。
【０１９８】
図６の別な例として、Ｆｉｌｅ＿Ｅｘｔｅｎｔ［ＮＥ］の最後の要素の後に、最後のエクステントであることを示すターミネイト識別子を置いてもよい。この場合、ナンバーオブエクステントがなくてもすべてのエクステントがわかるので、ナンバーオブエクステントを省略してもよい。また、ファイル・インフォメーション・ブロック・デスクリプタ内に、この管理情報全体のサイズを格納しておけば、ナンバーオブエクステントも前記ターミネイト識別子も省略することができる。あるいは、すべての情報を省略することなく格納することで、管理情報全体の信頼性を向上させることもできる。
【０１９９】
ターミネイト識別子を置く場合、通常のエクステント情報と同じ構造で、通常のエクステントと区別できるものを予め決めておけば何でもよい。例えば、エクステントのサイズが０のエクステントは存在しないので、Ｅ＊＝０のエクステント情報をターミネイト識別子とすることができる。あるいは、エクステント情報毎にフラグを用意して、最終エクステントかどうかを明示してもよい。
【０２００】
このようにファイルの配置情報は、ファイルの配置場所に関わり無く同じ形式で表現されるため、基本ブロックに配置されたファイルでも、サブブロックに配置されたファイルでも同じ手続きでアクセスすることができるため、どちらかのアクセス効率が不利になることはない。また再生時は、前記エクステント情報だけを用いてファイルの配置情報を取得でき、ビットマップテーブルを参照する必要はない。
【０２０１】
次に、配置済みのファイルが実際にどのように２つのビットマップテーブルで表現されているかを、図７の例を使って説明する。図８は図７に対応する第１のビットマップテーブルの例である。この例では、ブロックの状態を表す管理情報として、図３に示した例のうち、スケール（ｓｃａｌｅ）とユーザブル（ｕｓａｂｌｅ）の２ビットだけを用いた。この２ビットは第１のビットマップテーブルを構成するための最低必要な要素である。
【０２０２】
図８は各ブロックに対応する各フラグがどの状態になっているか分かり易いようにテーブルで表現してある。ｓｃａｌｅフラグは１の時に基本ブロック単体として使用していることを示し、０の時にサブブロックに分割してあることを示す。従って、図８のｓｃａｌｅフラグより、図７に丸数字１３と１６で示した２つの基本ブロックがサブブロックに分割してあることがわかる。また、図８のｕｓａｂｌｅフラグは、ｓｃａｌｅフラグに対応する未使用のブロックがあるかどうか（使用可能かどうか）を示すフラグであって、１のときｓｃａｌｅフラグに対応した未使用のブロックがあることを示す。
【０２０３】
従って、例えば、ブロック４は基本ブロックとして割り当ててあり１バイトも使用していない。ブロック５は基本ブロックとして使用中であることを示している。また、図７では、ブロック７は基本ブロックとして使用しており、まだ空き領域はあるが、この部分はもう基本ブロックとしては新たに使用できない（既にあるデータへの追記録しかできない）ので、ブロック５と同じように扱われる（ｕｓａｂｌｅ＝０）。
【０２０４】
一方、ブロック１３は基本ブロックに割り当てられたファイルｂの最終部分が格納されるブロックであるが、ブロック７と異なりサブブロックに分割してある。図７の拡大図を見ると、この部分はサブブロックの先頭の３ブロックしか使用していないため、ブロック７と異なり残りの９個のサブブロックを他のデータの記録用に使用することができる。
【０２０５】
図７の例では、実際にサイズＳｃのファイルｃを基本ブロック１３の中の７、８及び９番目のサブブロックに記録している。ファイルｃを記録した後でも、基本ブロック１３の中の３〜６番目と１０、１１番目のサブブロックは未使用なので、サブブロックとして利用可能なブロックが存在する（ｕｓａｂｌｅ＝１）。
【０２０６】
図９はサブブロックに分割した基本ブロック１３の第２のビットマップテーブル（ビットマップ本体のみ）を示す。図７に示したように、基本ブロック１３は、サブブロック０、１、２がファイルｂの最終部分によって使用され、サブブロック７、８、９がファイルｃによって使用されているので、図９に示す第２のビットマップテーブルは、サブブロック０、１、２、７、８、９が使用されていることを、ｕｓａｂｌｅ＝０で示している。
【０２０７】
図９ではサブブロックの状態を管理するフラグとしてはｕｓａｂｌｅの１ビットだけを示した。この１ビットが第２のビットマップテーブルを構成するための最低必要な要素である。同様に、図１０には基本ブロック１６の第２のビットマップテーブルを示す。図７では、基本ブロック１６は、サブブロック０〜３がファイルｄの１番目のエクステントＥｄ１によって使用され、サブブロック７、８がファイルｄの２番目のエクステントＥｄ２によって使用されているので、図１０に示す基本ブロック１６の第２ビットマップテーブルでは、サブブロック０〜３、７及び８が使用されていることを、ｕｓａｂｌｅ＝０で示している。
【０２０８】
ビットマップデータの実際のデータは、ブロック毎のフラグをブロック番号順に並べて求める。図１１は第１のビットマップのデータの求め方を示している。ブロック毎に（ｂｉｔ１，ｂｉｔ０）＝（ｕｓａｂｌｅ，ｓｃａｌｅ）とフラグを並べ、これを１バイトの中でＬＳＢ側からブロック順に詰めていってデータを作成する。図１１ではバイト内でブロック順に詰める操作は、左側をＭＳＢにしているため並べ替え操作になる。
【０２０９】
＃を１６進数を表すものとすると、最終的なデータは、順に♯ＦＦ，♯５７，♯ＤＦ，♯Ｆ９，♯ＦＥ，・・・となる。第２のビットマップテーブルも同様に求めると、ブロック１３は、♯７８，♯ＦＣ、ブロック１６は♯７０，♯ＦＥ　となる。なお２バイト目は下位４ビットのみ有効である。この例ではサブブロックは１２に分割してあり、管理情報のフラグがブロックにつき１ビットしかないので基本ブロック１つにつき１２ビットのテーブルサイズになる。
【０２１０】
図１２は基本ブロック１３、１６のビットマップデータを取得する手順を示す。図６に示したフィル管理情報内の情報の１つであるファイルインフォメーション（Ｆｉｌｅ＿Ｉｎｆｏｒｍａｔｉｏｎ）には、前記ファイルサイズ以外にもいくつかの情報がある。図１３は、このファイルインフォメーションの一例である。同図において、ファイルＩＤ（Ｆｉｌｅ＿ＩＤ）は、パーティション内でファイルまたはディレクトリに固有な識別番号である。本発明におけるファイルシステムは、ディレクトリはそのデータ構造が予め規定されたファイルとして扱うので、デイリクトリにもＦｉｌｅ＿ＩＤがある。
【０２１１】
ルートディレクトリのＦｉｌｅ＿ＩＤは予め定めた特定の値、例えば０に予約されているものとする。ルートディレクトリを初めとする、すべてのディレクトリには、そのディレクトリに所属するファイル又はディレクトリのＦｉｌｅ＿ＩＤが格納されているので、ルートディレクトリ以下の階層構造を、ディレクトリの内容を辿ることによって取得できる。
【０２１２】
また、図１３中、ディレクトリＩＤ（Ｄｉｒｅｃｔｏｒｙ＿ＩＤ）は、このファイルまたはディレクトリが所属しているディレクトリのＦｉｌｅ＿ＩＤを格納する。この情報を参照することによって、下位のディレクトリ階層にあるファイルからルートディレクトリまで逆に辿ることができる構造になっている。
【０２１３】
また、ターゲットＩＤ（Ｔａｒｇｅｔ＿ＩＤ）は、このファイルが予約領域ファイルである場合、この予約領域に記録するファイルのＦｉｌｅ＿ＩＤを格納する。また、このファイルが予約領域に記録する通常ファイルである場合、予約領域ファイルのＦｉｌｅ＿ＩＤを格納する。
【０２１４】
また、ファイルフラグ（Ｆｉｌｅ＿Ｆｌａｇｓ）は、後述するファイルの各種属性を表すフラグ群である。タイムスタンプ（Ｔｉｍｅ＿Ｓｔａｍｐ）は、このファイルに関する各種時刻情報であり、作成日時、最終更新日時、最終アクセス日時、削除した日時などを格納する。ファイルサイズ（Ｆｉｌｅ＿Ｓｉｚｅ）は前記ファイルサイズである。更に、ファイルネーム（Ｆｉｌｅ＿Ｎａｍｅ）は、このファイルを参照するための名称である。キャラクタコードやサイズについては本発明では特に規定しない。
【０２１５】
上記のＦｉｌｅ＿Ｆｌａｇｓには、少なくとも表３に示す３つのフラグを持つ。すなわち、バリッド（Ｖａｌｉｄ）、デリーテッドファイル（Ｄｅｌｅｔｅｄ　Ｆｉｌｅ）及びプリアロケーテッド・エリア（Ｐｒｅａｌｌｏｃａｔｅｄ　Ａｒｅａ）である。
【０２１６】
【表３】
2004013276.tif 000005
このほか、本発明では触れないが、ファイルの所有者やグループに対する、可視属性、書きこみ属性、実効属性などの各種ファイル属性などを持つ。
【０２１７】
表３に示したバリッドフラグは通常１で、そのファイルまたはディレクトリが有効であることを示す。あるファイルを消去する場合は、通常、そのエントリに対するファイル管理情報を完全に消去すると同時に、ビットマップテーブルで該当ファイルが占める領域を空き領域に変更する必要があるが、本発明では、ファイル管理情報を削除する際に、そのエントリを完全に消去してしまう以外の方法として、前記バリッドフラグを０にすることによって、この管理情報が無効であることを表すようにしている。これによって、管理情報のサイズが大きかった場合でも、前記フラグだけを０にすればよいので、ファイルの消去が容易に行える。
【０２１８】
また、ファイルを削除した後で削除を取り消したい場合があるので、表３に示したデリーテッドファイルというフラグをファイル管理情報に設け、一時削除／復活に対応できるようにした。すなわち、デリーテッドファイルが１の時は通常の状態のファイルだが、０にセットすることによって、このファイルが一時削除状態にあることを示す。
【０２１９】
一時削除状態にある場合は、このファイルに対するアクセスは禁止され、通常の手段では、その存在も見えないようにしておく。一時削除ファイルがあるかどうかは、専用のアクセス手段によってその存在が見えるようにしておき、専用の手段によって復活できるようにしておく。一時削除ファイルにアクセスしたい場合は、前記専用の手段によって、通常のファイルに復活してからアクセスするものとする。
【０２２０】
一時削除中のファイルは、それが占めている媒体上の記録スペースを他のファイルによって上書きされないように、その配置情報はそのまま保っておく必要がある。これは単に、第１と第２のビットマップテーブルを、一時削除前の状態のまま変更しないだけでよい。すなわち、一時削除前と後では、前記デリーテッドファイルフラグだけが変更されている。
【０２２１】
フラグを用いて永久に削除する場合の違いは、永久に削除する場合は、バリッドフラグの変更のほかに、ビットマップテーブルのファイル占有領域を開放する点である。ファイルが有効かどうかを表すバリッドフラグを用意することにより、エントリを完全に消去しなくてもこのバリッドフラグを０にするだけで永久削除と同じ効果が得られ、高速な消去が可能である。
【０２２２】
なお、バリッドフラグを用いた削除の場合でも、削除した直後など、データが上書きされていない場合には、専用の手段を設ければファイルを復活することも可能である。
【０２２３】
プリアロケーテッド・エリアフラグは、このファイルが予約領域ファイルであることを示す。予約領域ファイルは、特定のファイルあるいは、将来何らかのファイルを記録するために予め記録する領域を確保するために設けられた特別なファイルである。プリアロケーテッド・エリアフラグは通常ファイルの場合は０で予約領域ファイルの時に１に設定する。
【０２２４】
予約領域ファイルの配置された領域は予約領域そのものであり、予約領域ファイル自体はデータをもたないため、予約領域ファイル自体はデータを書き込まない。予約領域に書き込むファイルが決まったら、そのファイルＩＤ（Ｆｉｌｅ＿ＩＤ）を、図１３のターゲットＩＤに格納し、予約領域ファイルの先頭からファイルデータの記録を開始する。
【０２２５】
予約領域ファイルの作成は、実際に書き込むファイルをオープンする直前に行ってもよく、この場合は、予約領域ファイルの作成と同時にターゲットＩＤに記録するファイルのファイルＩＤを書き込んでおく。これは、ファイルを書き込みオープンするときに、予約領域サイズを指定してオープンする専用の手続きによって実現することができる。また、予約領域に書き込むファイルのターゲットＩＤには、予約領域ファイルのファイルＩＤを格納し、両者が相互に参照できるようにする。
【０２２６】
予約領域ファイルが占有する領域は、ビットマップテーブル上では、図３のプリアロケーテッドフラグで示され、基本ブロックまたはサブブロック単位で予約領域かどうかを調べることができる。複数の予約領域ファイルや複数の一時削除ファイルを管理するために、例えばルートディレクトリの直下に専用のディレクトリを設け、このディレクトリ内でこれらのファイルを管理すると効率良く管理することができる。
【０２２７】
図１４はディレクトリ内でファイルを管理する一例の説明図を示す。同図において、ルートディレクトリの直下に「ｐｒｅａｌｌｏｃ．ｄｉｒ」という予約領域ファイルを配置する専用のディレクトリがある。このディレクトリには「ａｒｅａ１．ｄａｔ」、「ａｒｅａ２．ｄａｔ」という２つの予約領域ファイルがある。これらはそれぞれ、／ａｖｄａｔａ．ｄｉｒ／ｓａｍｐｌｅ．ｄｉｒ／ａ．ｄｉｒというディレクトリにある「ａ１．ｄａｔ」と／ａｖｄａｔａ．ｄｉｒ／ｓａｍｐｌｅ．ｄｉｒ／ｂ．ｄｉｒというディレクトリにある「ｂ１．ｄａｔ」というファイルに対応している。
【０２２８】
すなわち、「ａｒｅａ１．ｄａｔ」は予約領域ファイルであることを示す、プリアロケーテッド・エリアフラグが１にセットされ、ターゲットＩＤとして、／ａｖｄａｔａ．ｄｉｒ／ｓａｍｐｌｅ．ｄｉｒ／ａ．ｄｉｒ／ａ１．ｄａｔを特定するための情報が格納されており、「ａ１．ｄａｔ」には「ａｒｅａ１．ｄａｔ」を特定するための情報が格納されている。
【０２２９】
また、「ａｒｅａ２．ｄａｔ」は予約領域ファイルであることを示す、プリアロケーテッド・エリアフラグが１にセットされ、ターゲットＩＤとして、／ａｖｄａｔａ．ｄｉｒ／ｓａｍｐｌｅ．ｄｉｒ／ｂ．ｄｉｒ／ｂ１．ｄａｔを特定するための情報が格納されており、「ｂ１．ｄａｔ」には「ａｒｅａ２．ｄａｔ」を特定するための情報が格納されている。
【０２３０】
一般に、階層ディレクトリ精造を持つファイルシステムでは、ファイルディレクトリの木構造の中で分散してしまうため、それぞれのファイルが予約領域を持つ場合、予約領域の一元管理が難しい。本発明では、予約領域を予約領域ファイルに対応付けることによって複数の予約領域を区別して管理でき、さらにこれを１つのディレクトリでまとめて管理できるようにしたので効率の良い管理が可能になった。
【０２３１】
また、図１４において、「ｄｅｌｆｉｌｅｓ．ｄａｔ」は、一時削除したファイルを特定するための情報をテーブルとして持ち、／ａｖｄａｔａ、ｄｉｒ／２００１．０２．０１．ｄｉｒディレクトリにある、「ｆｉｌｅ２．ｄａｔ」と「ｆｉｌｅ３．ｄａｔ」に関する識別情報が記録されている。「ｆｉｌｅ２．ｄａｔ」と「ｆｉｌｅ３．ｄａｔ」はデリーテッドファイルフラグが０になっており、一時削除状態にある。従って、通常の手続きで／ａｖｄａｔａ．ｄｉｒ／２００１．０２．０１．ｄｉｒディレクトリを見ると、「ｆｉｌｅ１．ｄａｔ」しか見えない。
【０２３２】
なお、この例では、「ｄｅｌｆｉｌｅｓ．ｄａｔ」は／ｄｅｌｅｔｅｄ．ｄｉｒというディレクトリにおいたが、他のディレクトリやルートディレクトリにおいてもよい。例えば、ディレクトリ毎に置くようにして、そのディレクトリ内の一時ファイルのみを管理するようにしてもよい。
【０２３３】
本発明では、このように一時削除ファイルをまとめて管理できるようにしたので、復活したいファイルを検索し、一時削除ファイルを永久に削除することによって記録領域を増やしたい場合など、簡単に一時ファイルを参照することができて都合がよい。
【０２３４】
一時削除したファイルを特定する識別情報のテーブルは、ディレクトリ毎に持ってもよい。図１４の例では、／ａｖｄａｔａ．ｄｉｒ／２００１．０２．０１．ｄｉｒに「ｄｅｌｆｉｌｅｓ．ｄａｔ」をおけばよい。
【０２３５】
着目しているディレクトリ内の一時削除ファイル情報を取得する場合、パーティション全体の一時削除ファイルのリストでは、一つ一つ該当ディレクトリのファイルかどうかをチェックする必要があるが、ディレクトリ毎に一時削除ファイル情報を用意しておけば、これを参照することによって直ちに取得することができる。なお、全体の一時削除ファイルとディレクトリ毎の削除ファイルが両方あってももちろんよい。
【０２３６】
次に、ビットマップテーブルのアラインメントについて説明する。
【０２３７】
図１５は第１のビットマップテーブルの記録媒体上の配置例を示す。第１のビットマップテーブル１５１は、その管理情報１５２とテーブル本体１５３から構成される。媒体上に記録する場合は、論理セクタ単位でアラインメントが取れるように、管理情報１５２の直後、またはテーブル本体１５３の直後にスタッフィングのためのダミーデータ１５４を挿入する。
【０２３８】
次に、第２のビットマップテーブルの記録媒体上の配置例について図１６及び図１７と共に説明する。第２のビットマップテーブルは、第１のビットマップテーブルよりサイズが小さく、複数個存在し、その数が使用時に変動するという特徴がある。
【０２３９】
図１６は、１つの第２のビットマップテーブルサイズが論理セクタサイズよりも大きい場合の例であり、第１のビットマップテーブルと同様に第２のビットマップテーブル毎に論理セクタ単位でアラインメントをとるためのダミーデータを付加している。
【０２４０】
また、各ビットマップテーブルは図１６（ａ）に示したように１個１個ばらばらに置いてもよいが、論理セクタ単位のアラインメントをとっているので、同図（ｂ）に示したように隙間無く詰めて配置することができる。この時、第１のビットマップテーブルでの配置の順番に従って第２のビットマップテーブルを順番に並べればサブブロックをまとめて管理するのに都合がよい。
【０２４１】
図１７は、第２のビットマップテーブルのサイズが論理セクタサイズより小さい場合の例で、（ａ）はその数が多くて合計のサイズが論理セクタサイズを超える場合、（ｂ）はその数が少なくて、合計サイズが論理セクタサイズに満たない場合の例である。図１７（ａ）、（ｂ）のどちらの場合も複数個のビットマップテーブルを隙間無く詰めて配置しているが、その際に各ビットマップテーブルが２のべき乗の倍数のバイト数になるようにしておくと、アドレッシングが容易になる。特に２のべき乗の同一サイズに設定すれば、ｎ個目のビットマップテーブルの位置をビットシフト演算だけで求めることができて効率が良い。
【０２４２】
次に、スタッフィングのためのダミーデータの配置方法について、図１８及び図１９と共に説明する。図１８のビットマップテーブルの管理情報１８１には、図４と図５で説明したように先頭のデスクリプタ（Ｄｅｓｃｒｉｐｔｏｒ）の中にビットマップテーブル全体のサイズ１８４が格納されている。また、ビットマップテーブル本体１８２のサイズも同様に格納されている。管理情報部分のサイズは固定なので、ビットマップテーブル本体１８２の後にダミーデータ１８３を付加し、全体のサイズにダミーデータ１８３を含めたサイズを格納すればよい。
【０２４３】
あるいは、管理情報を可変長とし、図１９に１９３で示すように管理情報内に管理情報部分のサイズを格納することにより、管理情報本体１９１の直後にダミーデータ１９２を付加することもできる。このようにすると、ビットマップテーブルの開始アドレスを都合のよい値に設定することができる。
【０２４４】
図１８と図１９の方法は組み合わせてもよく、この場合、ビットマップテーブルの開始アドレスを任意の値に設定すると同時に、ビットマップテーブルの全体サイズを論理セクタの倍数に設定することが可能になる。
【０２４５】
【発明の効果】
以上説明したように、本発明によれば、以下のような種々の特長を有するものである。
【０２４６】
（１）サイズが大きい基本ブロックにデータを配置管理する第１の管理方法とサイズが小さいサブブロックにデータを配置管理する第２の管理方法を、記録データのサイズに応じて選択使用するようにしたため、内部フラグメンテーションを最小にして記録領域を効率良く使用することができる。また、サイズの大きいファイルは基本ブロックに記録することによって、外部フラグメンテーションの発生を最悪の場合でも基本ブロック単位に抑えることができるため、ヘッドシーク等によるアクセス効率の低下を最小限にすることができる。
【０２４７】
特にＡＶデータなどリアルタイム性を要求されるデータを基本ブロック単位に記録することにより、ＡＶデータを欠落することなく記録再生することが可能になり、また、ＡＶデータを管理するための補助的な情報（プレイリスト、サーチのためのボインタ情報など）等、ＡＶデータと比較するとサイズが小さいファイルをサブブロックに記録することにより、これらのデータを効率良く配置できるため、このようなマルチメディア用途のアプリケーションへの適用に最適である。また、それぞれのブロックに対して使用状態を示すビットマップテーブルを持つため、ビットマップを検索するだけでブロックの状態を素早く参照することができ、記録開始時に次に録画可能な領域の検索が高速に行える。
【０２４８】
（２）基本ブロックの使用状態を示す第１のビットマップテーブルには、基本ブロック毎にサブブロックに分割して使用しているかどうかを示すフラグがテーブルになっているため、目的に合ったブロックを高速に検索するのに適している。また、そのブロックが基本ブロックとして使用している場合は基本ブロックとして使用可能かどうかがわかり、そのブロックがサブブロックに分割されている場合は、その基本ブロック内に使用可能なサブブロックがあるかどうかがわかるフラグも同時に取得できるので、どちらのブロックのタイプで使用したい場合でも使用可能なブロックの場所を高速に取得できる。
【０２４９】
（３）サブブロックに分割された基本ブロックの中で、実際にどのサブブロックが使用可能かを示すフラグのテーブルが第２のビットマップテーブルとして独立しているため、必要な場合にだけ参照するようにできる。また、基本ブロックを随時サブブロックに分割する際にも第２のビットマップテーブルは独立しているため、新しい第２のビットマップテーブルを追加するだけでよく、第１のビットマップテーブルの構成が変わらないため検索性能が低下することはない。
【０２５０】
（４）第１、第２のビットマップテーブルは、そのことを示す識別情報と全体のサイズをそれぞれ持っているため独立性が高く、ビットマップテーブルの配置情報を参照しなくてもビットマップテーブル全体の配置を取得できる。このため、何らかの原因でビットマップテーブルの配置情報が破壊された場合でも、識別情報を手がかりに記録媒体のサルベージを行えば、ビットマップテーブルの格納場所を検出することが可能で、配置情報を再構築することができる。
【０２５１】
（５）第１のビットマップテーブルの管理情報は、基本ブロックのサイズと数を持つので、用途に応じて任意の値に設定し、保存することができ、また、サブブロックに分割された基本ブロックの数を併せ持つので、基本ブロックのみで使用している領域の容量とサブブロックに分割して使用している領域の容量を計算して求めることができる。また、サブブロックのデフォルトサイズと第２のビットマップテーブルのデフォルトサイズを持つようにした場合は、これを簡単に参照できるので、サブブロックに分割する際の基準値をフォーマット時に指定することができ、記録媒体全体の統一した使い方ができる。
【０２５２】
（６）第２のビットマップテーブルの管理情報はサブブロックのサイズと数を持つので、用途に応じて任意の値に設定し、保存することができ、また、第２のビットマップテーブルは、サブブロックに分割された基本ブロック毎に存在するので、必要に応じて、基本ブロック毎に最適なサブブロックサイズを設定することが可能である。
【０２５３】
この第２のビットマップテーブルのサブブロックサイズの値は、第１のビットマップテーブルにデフォルトのサイズが設定してあっても、こちらが優先されるようにした場合は、独立に自由な設定が可能である。逆に、第２のビットマップテーブルのサブブロックサイズをデフォルトのサイズと同じ値を設定することで、すべてのサブブロックのサイズを共通にして、ドライバのハンドリングを容易にするような適用も可能である。
【０２５４】
（７）第２のビットマップテーブルの管理情報には、対応する基本ブロックの識別情報が格納されているので、第２のビットマップテーブルの情報からの逆引きで、配置情報を取得することができ、これにより第２のビットマップテーブルと対応する基本ブロックの対応付け情報が失われることがない。また、複数の第２のビットマップテーブルを必ずしも順番に並べなくても対応する基本ブロックを特定できるため、例えば、追記型の媒体において、新たに追加する第２のビットマップテーブルが存在しても、追加するテーブルだけを追記すればよく、すべての第２のビットマップテーブルを並べ直して書き直す必要がない。
【０２５５】
（８）第２のビットマップテーブルのサイズが小さい場合は、２のべき乗の倍数単位でアラインメントし、大きい場合はセクタ単位にアラインメントし、対応する基本ブロックの順番に連続して配置することにより、複数の第２のビットマップテーブルから、特定の第２のビットマップテーブルを容易に検索できる。特に、第２のビットマップテーブルのサイズをすべて同じにした場合は、ｋ番目（０，１，２，・・・）の第２のビットマップテーブルの位置は、ｋとサイズの積で簡単に計算できる。
【０２５６】
（９）記録に先立って予約領域を確保できるようにしたので、記録媒体上の連続する領域を特定データの記録用に確保することができ、外部フラグメンテーションの発生を避けることができる。また、確保した予約領域はビットマップテーブルのフラグで参照することができるため、同じ記録媒体をアクセスする他のプロセスがあっても、予約領域であることを知ることができ、他のプロセスで使用されるおそれがない。
【０２５７】
（１０）一時削除を表すフラグを用意するようにしたため、削除と復活を高速に実現でき、また、パーティション内の全ての一時削除ファイルを１つのテーブルで管理できるようにしたので、パーティション全体でどのくらいの一時削除ファイルがあるかを直ちに知ることができ、復活したいファイルを容易に検索できる。また、ディレクトリ毎に一時削除ファイルを管理できるようにしたので、特定のディレクトリに着目した場合に、そのディレクトリ内の一時削除ファイルを直ちに知ることができる。
【０２５８】
（１１）欠陥セクタがあった場合は、サブブロックに分割して欠陥セクタを含むサブブロックだけを使用禁止にするようにしたため、基本ブロック単位で使用不可にならず、正常な領域をサブクラスタ単位で利用できる。
【０２５９】
（１２）交替セクタがある場合、サブブロックに分割して使用するようにしたので、基本ブロック単位で記録する場合は、内部の一部に交替セクタを含むことがないので交替に伴うヘッドシークを避けることができる。
【０２６０】
（１３）基本ブロック単位で記録する場合もサブブロック単位で記録する場合も、どちらも同じエクステントを用いた管理構造でファイル配置を管理しているので、記録したファイルへのアクセス方法が同じになる。すなわち、サブブロックに記録されたファイルが、サブブロックに分割された複数の基本ブロックにまたがる場合や、基本ブロック単位とサブブロック単位が混在している状態のファイルの場合であっても、同じように管理することができる。
【０２６１】
また、最終部分だけがサブブロックに分割してあった場合でも、ファイルの配置情報には関係しないので、そのファイルをアクセスする際に効率が落ちることがない。更に、基本ブロックとサブブロックの間の変換する場合は、ビットマップの構造を変更するだけでよく、ファイルの配置情報は変更する必要がない。
【０２６２】
（１４）基本ブロックのサイズが、ＴＳパケット（１９２バイト）とＰＳパケット（２０４８バイト）とＨＤＤの論理セクタ（５１２バイト）と光ディスク媒体の論理セクタ（２０４８バイト）の最小公倍数６１４４バイトの倍数になっているので、基本ブロックの境界においてＴＳパケットやＰＳパケットの分断が発生せず、ＡＶストリームデータの保存に適している。
【０２６３】
また、基本ブロックのサイズを３２ｋ×３（＝９６ｋ＝９８３０４バイト）の倍数に設定することによって、基本ブロックの境界をＦＡＴファイルシステムにおけるクラスタ境界と一致させることを可能にする。サブブロックのサイズは、３２ｋバイト（＝３２７６８バイト）の倍数かつ、基本ブロックのｋ分の１（ｋは３以上の自然数）に設定するようにしたため、サブブロックに格納されるファイルの配置をＦＡＴファイルシステムのクラスタで表現できる。
【０２６４】
（１５）記録媒体をエラーに対する対応条件がそれぞれ設定してある複数の領域に分け、領域毎に、基本ブロック単位で記録する領域、サブブロック単位で記録する領域、ファイルの最終部分にのみサブブロックで記録し、それ以外を基本ブロック単位で記録する領域、どちらでも自由に利用できる領域のいずれかに設定することによって、領域毎にエラー発生時の対応条件と、配置するデータの性質を関係付けることができる。例えば、ある領域は基本ブロック単位だけで記録するものとし、エラー発生時のリトライ無し、またはリトライ回数を少なくすることによって、多少の信頼性を犠牲にしてもリアルタイム性が要求されるＡＶデータの記録再生専用の領域に用いることができる。
【０２６５】
一方、別な領域はサブブロック単位だけで記録するものとし、エラー発生時のリトライ回数を多く設定することによって、多少の即時性を犠牲にしても信頼性を向上させることができるので、ＡＶデータと比較すると小さいサイズで、しかも重要な管理情報などのデータを記録する領域として用いることができる。
【図面の簡単な説明】
【図１】本発明になるファイルシステムの一実施の形態の説明図である。
【図２】記録媒体の記録領域の先頭付近の利用状況の一実施の形態を示す図である。
【図３】本発明におけるブロック毎の管理情報を示すための各種フラグの定義例を示す図である。
【図４】第１のビットマップテーブルの一例を示す図である。
【図５】第２のビットマップテーブルの一例を示す図である。
【図６】本発明におけるファイル管理情報の一例を示す図である。
【図７】本発明になる記録媒体の一実施の形態の記録情報の説明図である。
【図８】図７に対応する第１のビットマップテーブルの例である。
【図９】サブブロックに分割した基本ブロック１３の第２のビットマップテーブル（ビットマップ本体のみ）を示す図である。
【図１０】図７中のブロック１６の第２のビットマップテーブルである。
【図１１】第１のビットマップのデータの求め方を示した図である。
【図１２】図７中の基本ブロック１３、１６のビットマップデータを取得する手順を示した図である。
【図１３】図６に示したフィル管理情報内の情報の１つであるファイルインフォメーションを示す図である。
【図１４】ディレクトリ内でファイルを管理する一例の説明図である。
【図１５】第１のビットマップテーブルの記録媒体上の配置例を示す図である。
【図１６】第２のビットマップテーブルサイズが論理セクタサイズよりも大きい場合の図である。
【図１７】第２のビットマップテーブルのサイズが論理セクタサイズより小さい場合の図である。
【図１８】スタッフィングのためのダミーデータの配置方法を説明するための図である。
【図１９】スタッフィングのためのダミーデータの配置方法を説明するための図である。
【図２０】ＦＡＴファイルシステムの構造を説明するための図である。
【図２１】代表的なファイルシステムの容量とクラスタサイズの関係を示す図である。
【図２２】特開平８−１０１７８３号公報記載の従来のファイルシステムの一例の構成図である。
【図２３】外部フラグメンテーションと内部フラグメンテーションを示す図である。
【符号の説明】
１００　記録媒体
１０１　基本ブロック
１０２　サブブロック
１０３、１５１　第１のビットマップテーブル
１０４、１５３　第１のビットマップテーブル本体
１０５、１５２　管理情報
１０６　第２のビットマップテーブル
１０７　第２のビットマップテーブル本体
１０８　管理情報
１８１　ビットマップテーブルの管理情報
１８２　ビットマップテーブル本体
１８３、１９２　ダミーデータ
１９１　管理情報本体
１９３　管理情報全体のサイズ
【図１】
2004013276.tif 000006
【図２】
2004013276.tif 000007
【図３】
2004013276.tif 000008
【図４】
2004013276.tif 000009
【図５】
2004013276.tif 000010
【図６】
2004013276.tif 000011
【図７】
2004013276.tif 000012
【図８】
2004013276.tif 000013
【図９】
2004013276.tif 000014
【図１０】
2004013276.tif 000015
【図１１】
2004013276.tif 000016
【図１２】
2004013276.tif 000017
【図１３】
2004013276.tif 000018
【図１４】
2004013276.tif 000019
【図１５】
2004013276.tif 000020
【図１６】
2004013276.tif 000021
【図１７】
2004013276.tif 000022
【図１８】
2004013276.tif 000023
【図１９】
2004013276.tif 000024
【図２０】
2004013276.tif 000025
【図２１】
2004013276.tif 000026
【図２２】
2004013276.tif 000027
【図２３】
2004013276.tif 000028