(57)【特許請求の範囲】
【請求項１】
コンピュータによって実施される、ユニバーサルディスクフォーマット（Universal Disk Format）（ＵＤＦ）ファイルシステムにおいて情報制御ブロック追跡ストリームを使用するための方法であって、前記コンピュータが、
情報制御ブロックを記憶するように構成された複数の論理ブロックを含むように、少なくとも１つの範囲をＵＤＦボリューム上に割り振るステップと、
前記ＵＤＦボリューム上の前記少なくとも１つの範囲に対応するビットを有するボリューム空きスペースビットマップにおいて、前記ボリューム空きスペースビットマップの中のビットを、該ビットが対応する前記ＵＤＦボリューム上の前記少なくとも１つの範囲の前記論理ブロックが、割振り済みであることを示すように設定するステップと、
前記ＵＤＦボリューム上の前記少なくとも１つの範囲に対応しているか否かを示す割振り記述子であって、前記ＵＤＦボリュームにおいて情報制御ブロックを記憶するのに利用できない論理ブロックで構成される範囲を示すこともある割振り記述子を有する、少なくとも１つの範囲を含む範囲コンテナストリームを生成するステップと、
前記範囲コンテナストリームの中の各論理ブロックに対応するビットを含むビットマップストリームを生成するステップと、
前記割振り記述子によって、前記ビットマップストリームの中の特定のビットに対応する前記範囲コンテナストリームの論理ブロックが、前記ＵＤＦボリューム上の情報制御ブロックを記憶している論理ブロックに対応していることが示される場合、対応する前記論理ブロックが情報制御ブロックを記憶していることを示すように、前記ビットマップストリームの中の前記特定のビットを設定するステップと
を含む各ステップを実行することを特徴とする方法。
【請求項２】
前記ビットマップストリームの中のビットが設定されていないクリアビットであるとき、前記コンピュータが、前記ビットマップストリームの中の前記ビットを設定し、該ビットが対応する論理ブロックを新しい情報制御ブロックを記憶するのに使用することによって、前記新しい情報制御ブロックを生成するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記コンピュータが、前記範囲コンテナストリームの中で新しい範囲を割り振ることによって前記範囲コンテナストリームを拡張するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記範囲コンテナストリームを拡張するステップは、さらに、前記コンピュータが、
前記ＵＤＦボリューム上で新しい範囲を割り振るステップと、
前記範囲コンテナストリームに関連する情報制御ブロックまたは割振り記述子連続範囲の中で、前記新しい範囲に対応する新しい割振り記述子を生成するステップと、
前記新しい範囲に対応するさらなるビットを前記ビットマップストリームの中で割り振るステップと
を含む各ステップを実行することを特徴とする請求項３に記載の方法。
【請求項５】
前記範囲コンテナストリームの前記少なくとも１つの範囲に対応する前記ビットマップストリームの中の前記ビットが、設定されていないクリアビットであるとき、前記コンピュータが、前記範囲コンテナストリームの前記少なくとも１つの範囲を前記ＵＤＦボリュームに取り戻すステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記範囲コンテナストリームの前記少なくとも１つの範囲を取り戻すステップは、さらに、前記コンピュータが、
前記範囲コンテナストリームの前記少なくとも１つの範囲に対応する前記ＵＤＦボリューム上の前記少なくとも１つの範囲が、情報制御ブロックを記憶するのに利用できないことを示すように、前記ビットマップストリームの中の前記ビットを設定するステップと、
前記範囲コンテナストリームの前記少なくとも１つの範囲が、情報制御ブロックを記憶している前記ＵＤＦボリューム上の少なくとも１つの範囲に対応していないことを示すように、前記範囲コンテナストリームの前記割振り記述子を更新するステップと、
前記少なくとも１つの範囲に対応する前記ボリューム空きスペースビットマップの前記ビットをクリアして、該ビットに対応する前記ＵＤＦボリュームの論理ブロックが割振り解除されたことを示すステップと
を含む各ステップを実行することを特徴とする請求項５に記載の方法。
【請求項７】
前記範囲コンテナストリームの前記少なくとも１つの範囲を取り戻すステップは、さらに、前記コンピュータが、
前記ビットマップストリームから前記少なくとも１つの範囲に対応するビットを除去し、その結果得られるより少ないビット数を反映するように前記ビットマップストリームの関連する情報長を更新することで、前記ビットマップストリームを切り捨てるステップと、
前記ビットマップストリームから除去された前記ビットに対応する論理ブロックを前記範囲コンテナストリームから除去し、その結果得られる、前記範囲コンテナストリームに関連するより少ない論理ブロック数を反映するように前記範囲コンテナストリームの関連する情報長を更新することで、前記範囲コンテナストリームを切り捨てるステップと
を含む各ステップを実行することを特徴とする請求項５に記載の方法。
【請求項８】
情報制御ブロックに対応するファイルが前記ＵＤＦボリュームから削除されたとき、前記コンピュータが、前記情報制御ブロックを割振り解除するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
情報制御ブロックを割振り解除するステップは、さらに、前記コンピュータが、
割振り解除される前記情報制御ブロックを記憶している論理ブロックの前記範囲コンテナストリーム内の位置を特定するオフセットであって、前記情報制御ブロックの中に記憶されているオフセットを検査するステップと、
前記範囲コンテナストリームの中の前記論理ブロックに対応する前記ビットマップストリームの中のビットをクリアするステップと
を含む各ステップを実行することを特徴とする請求項８に記載の方法。
【請求項１０】
第１および第２の構成要素を記録したコンピュータ可読な記録媒体であって、
前記第１の構成要素は、コンピュータによって実行されると、ユニバーサルディスクフォーマット（ＵＤＦ）ボリューム上に割り振られる、少なくとも１つの範囲に対応する範囲を含むように構成され、前記ＵＤＦボリューム上の前記少なくとも１つの範囲は、情報制御ブロックを記憶するための複数の論理ブロックを含み、前記第１の構成要素の前記範囲は、前記ＵＤＦボリューム上の前記複数の論理ブロックに対応する複数の論理ブロックを含むように構成され、
前記第２の構成要素は、コンピュータによって実行されると、各ビットが前記第１の構成要素の中の各論理ブロックに対応する、複数のビットを含むように構成され、前記複数のビットの各々は、第１の構成要素内の対応する論理ブロックによって参照される前記ＵＤＦボリューム上の論理ブロックが、情報制御ブロックを含んでいるときに設定される
ことを特徴とするコンピュータ可読な記録媒体。
【請求項１１】
前記第１の構成要素の中の前記範囲は、所定数の論理ブロックに対応するストリーム割振りユニットに従って構成され、前記ストリーム割振りユニットの第１の論理ブロックは、前記所定数の論理ブロックの整数の倍数であり前記ＵＤＦボリュームの前記論理ブロックを一意に識別する、論理ブロック番号を有することを特徴とする請求項１０に記載のコンピュータ可読な記録媒体。
【請求項１２】
符号化されたデータ構造を有するデータが記録されたコンピュータ可読な記録媒体であって、前記データ構造は、
コンピュータによって実行されると、少なくとも１つの範囲を含むように構成される範囲コンテナストリームであって、前記少なくとも１つの範囲がそれぞれ、情報制御ブロックを記憶するためにユニバーサルディスクフォーマット（ＵＤＦ）ボリューム上に割り振られる、所定数の論理ブロックに対応する所定数のブロックを含むように構成される、範囲コンテナストリームと、
コンピュータによって実行されると、前記範囲コンテナストリームの中の前記所定数のブロックに対応する所定数のビットを含むように構成されるビットマップストリームであって、前記所定数のビットはそれぞれ、前記範囲コンテナストリームの中の対応するブロックが、情報制御ブロックを記憶しているときに設定される、ビットマップストリームと
を含むことを特徴とするコンピュータ可読な記録媒体。
【請求項１３】
前記範囲コンテナストリームに関連する情報制御ブロックは、各範囲に関連する割振り記述子を含む割振り記述子連続範囲を参照することを特徴とする請求項１２に記載のコンピュータ可読な記録媒体。
【請求項１４】
前記割振り記述子は、前記範囲コンテナストリームの中の各範囲が情報制御ブロックを記憶するために割り振られているかどうかを示すことを特徴とする請求項１２に記載のコンピュータ可読な記録媒体。
【請求項１５】
前記範囲コンテナストリームに関連する情報制御ブロックは、各範囲に関連する割振り記述子を含むことを特徴とする請求項１２に記載のコンピュータ可読な記録媒体。
【請求項１６】
ユニバーサルディスクフォーマット（ＵＤＦ）ファイルシステムにおいて情報制御ブロック追跡ストリームを使用するためのコンピュータ実行可能命令を記録したコンピュータ可読な記録媒体であって、
前記命令は、コンピュータに、
各範囲がＵＤＦボリューム上の所定数の論理ブロックに対応する所定数のブロックを含む、少なくとも１つの範囲を含む範囲コンテナストリームを生成するステップと、
前記範囲コンテナストリームの中の前記少なくとも１つの範囲が前記ＵＤＦボリューム上の前記少なくとも１つの範囲に対応しているか否かを示し、前記範囲コンテナストリームの中の各範囲を識別するための割振り記述子を、前記範囲コンテナストリームの中の各範囲について生成するステップと、
前記ＵＤＦボリューム上の各範囲に対応するビットを有するボリューム空きスペースビットマップにおいて、該ビットに対応する前記ＵＤＦボリューム上の論理ブロックが割振り済みであることを示すように、前記ボリューム空きスペースビットマップの中の前記ビットを設定するステップと、
前記範囲コンテナストリームの中の前記所定数のブロックに対応する所定数のビットであって、それぞれ対応するブロックが情報制御ブロックを記憶しているか、または情報制御ブロックを記憶するのに利用できないときに設定される、所定数のビットを含むビットマップストリームを生成するステップと
を含む各ステップを実行させることを特徴とするコンピュータ可読な記録媒体。
【請求項１７】
前記ビットマップストリームの中のビットが、設定されていないクリアビットであり利用可能であるときに、前記ビットマップストリームの中の前記ビットを設定し、情報制御ブロックを記憶するのに前記所定数のブロックのうち該ビットに対応するブロックを使用することによって、新しい情報制御ブロックを識別するステップをさらに含むことを特徴とする請求項１６に記載のコンピュータ可読な記録媒体。
【請求項１８】
前記範囲コンテナストリームの中で新しい範囲を割り振ることによって前記範囲コンテナストリームを拡張するステップをさらに含むことを特徴とする請求項１６に記載のコンピュータ可読な記録媒体。
【請求項１９】
前記範囲コンテナストリームを拡張するステップは、さらに、
前記ＵＤＦボリューム上で新しい範囲を割り振るステップと、
前記範囲コンテナストリームに関連する情報制御ブロックまたは参照される割振り記述子連続範囲の中で、前記新しい範囲に対応する新しい割振り記述子を生成するステップと、
前記新しい範囲に対応するさらなるビットを前記ビットマップストリームに追加するステップと
を含むことを特徴とする請求項１８に記載のコンピュータ可読な記録媒体。
【請求項２０】
前記少なくとも１つの範囲に対応する前記ビットマップストリームの中のビットがクリアビットであるとき、前記ＵＤＦボリュームに、前記範囲コンテナストリームの中の範囲を取り戻すステップをさらに含むことを特徴とする請求項１６に記載のコンピュータ可読な記録媒体。
【請求項２１】
範囲を取り戻すステップは、さらに、
前記取り戻された範囲に対応する前記ビットマップストリームの中のビットを設定して、前記取り戻された範囲の論理ブロックが情報制御ブロックを記憶するのに利用できないことを示すステップと、
前記ボリューム空きスペースビットマップの前記ビットをクリアして、前記取り戻された範囲に対応する前記ＵＤＦボリューム上の対応する所定数の論理ブロックが割り振られていないことを示すステップと
を含むことを特徴とする請求項２０に記載のコンピュータ可読な記録媒体。
【請求項２２】
範囲を取り戻すステップは、さらに、
前記取り戻された範囲に対応するビットを前記ビットマップストリームから除去し、その結果得られるより少ないビット数を反映するように前記ビットマップストリームの関連する情報長を更新することで、前記ビットマップストリームを切り捨てるステップと、
前記ビットマップストリームから取り除かれた前記ビットに対応する論理ブロックを前期範囲コンテナストリームから除去し、その結果得られる前記範囲コンテナストリームに関連するより少ない論理ブロック数を反映するように、前記範囲コンテナストリームの関連する情報長と前記範囲コンテナストリームの割振り記述子とを更新することで、前記範囲コンテナストリームを切り捨てるステップと
を含むことを特徴とする請求項２１に記載のコンピュータ可読な記録媒体。
【請求項２３】
情報制御ブロックに対応するファイルが前記ＵＤＦボリュームから削除されたとき、前記情報制御ブロックを割振り解除するステップをさらに含むことを特徴とする請求項１６に記載のコンピュータ可読な記録媒体。
【請求項２４】
情報制御ブロックを割振り解除するステップは、さらに、
割振り解除される前記情報制御ブロックを記憶している論理ブロックの前記範囲コンテナストリーム内の位置に対応するオフセットであって、前記情報制御ブロックの中に記憶されているオフセットを検査するステップと、
前記範囲コンテナストリームの中の割振り解除される前記論理ブロックに対応する前記ビットマップストリームの中のビットをクリアするステップと
を含むことを特徴とする請求項２３に記載のコンピュータ可読な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ユニバーサルディスクフォーマット（ＵＤＦ）ファイルシステムのための情報制御ブロック（ＩＣＢ）追跡ストリームに関する。
【０００２】
【従来の技術】
ユニバーサルディスクフォーマット（ＵＤＦ）は、データの互換性および可搬性のために設計されたベンダ非依存のファイルシステム形式である。ＵＤＦにより、オペレーティングシステムが、別のオペレーティングシステムまたは別のデバイスによって生成されたデータにアクセスする（読み取る／書き込む／変更する）ことができるようになる。ＵＤＦは、ＩＳＯ  １３３４６として知られるデータの非順次記録（non-sequential recording）（ＮＳＲ）のための国際標準化機構（ＩＳＯ）互換性標準のサブセットであり、この標準に完全に準拠する。ＵＤＦは、コンピュータデータおよびコンピュータイメージの記憶のための書込み可能光学技術および書込み可能光学製品の使用を推進するための非営利の連合であるOptical Storage Technology Association（ＯＳＴＡ）によって定義されたＩＳＯ  １３３４６のサブセットである。ＵＤＦは、ＣＤ、ＤＶＤ、ＭＯ、ＷＯＲＭ、および磁気ディスクなどの多種多様な媒体技術をサポートする汎用ファイルシステムである。また、ＵＤＦは、ＣＤ−ＲＯＭなどの順次記録媒体のためのサポートを追加してＩＳＯ  １３３４６標準の上に構築されている。
【０００３】
ＵＤＦは、主に、光記憶媒体のために利用される。固定ディスクと比べたとき、光記憶デバイスに共通の特性は、光ドライブが、長いシーク時間および比較的低いスループットを有する可能性があることである。少数のファイルが探し出されるとき、このパフォーマンスの問題は、十分に小さいので、ユーザ体験は、劣悪ではない。しかし、非常に多数のファイルへのアクセスを必要とする何らかのアクションが行われるとき、ユーザ体験は、失望させられるものである可能性がある。例えば、従来のサイズのボリュームが、誤りに関して検査される場合（例えば、「ｃｈｋｄｓｋ」または「ｆｓｃｈｋ」）、そのボリューム上のすべてのファイルにアクセスが行われる。
【０００４】
【発明が解決しようとする課題】
本発明によれば、システムおよび方法が、ユニバーサルディスクフォーマット（ＵＤＦ）ファイルシステムにおいて使用するための情報制御ブロック（ＩＣＢ）追跡ストリームを提供する。このメタデータストリームにより、ＵＤＦ記憶媒体上でＩＣＢを追跡して、その媒体上のＩＣＢにアクセスする速度を高めることができる。本明細書では、ストリームを説明するが、本発明は、ストリームの代わりに隠しファイルまたはＥＡを使用して実施することも可能なことに留意されたい。
【０００５】
【課題を解決するための手段】
ＩＣＢが、ＵＤＦファイルシステムのスキャン中に探し出される。ＩＣＢが探し出されて、ＵＤＦファイルシステムのボリュームデータ構造が確認され、訂正される。すべてのＩＣＢにアクセスが行われて、ボリュームの整合性が完全に確認される。ＵＤＦに関する以前の標準の下では、ＩＣＢを探し出すのに、完全な階層ウォークまたは区画論理ブロック（partition logical block）のスキャンが必要とされた。というのは、ＩＣＢは、記憶媒体上のＵＤＦ区画全体で探し出されたからである。これに対して、本発明は、ＩＣＢが記憶されているボリュームの領域を追跡して、ＩＣＢを区画の中で容易に探し出すことができるようにする。
【０００６】
本発明においてＵＤＦファイルシステムによって利用される２つのストリームは、ＩＣＢ範囲コンテナストリーム（extent container stream）およびＩＣＢビットマップストリームである。これらのストリームは、媒体上のＩＣＢの場所を追跡するのに役立ち、また、ＩＣＢのクラスタ化を促進し、これにより、空きスペースの断片化が少なくなる可能性があり（ＩＣＢのサイズは、単一のブロックであるため）、したがって、一般的なファイルシステムパフォーマンスが向上する可能性がある。ＵＤＦファイルシステムの確認の速度は、すべてのＩＣＢを探し出し、アクセスするのに完全な階層ウォークおよび表面スキャンの必要性をほとんどなくすことにより、相当に向上する。
【０００７】
【発明の実施の形態】
簡単に述べると、本発明は、ユニバーサルディスクフォーマット（ＵＤＦ）ファイルシステムに従って構成された記憶媒体上のＩＣＢの場所を追跡するための２つの情報制御ブロック（ＩＣＢ）追跡ストリーム（tracking stream）を含む。ＵＤＦボリューム上のある範囲の連続する論理ブロックが、ＩＣＢを記憶するために割り振られる。ＩＣＢ範囲コンテナストリームが、その範囲に対応するストリーム割振りユニットを含む。したがって、ＵＤＦボリューム上のその範囲内に記憶されるＩＣＢはまた、ＩＣＢ範囲コンテナストリームの中に記憶される。各割振りユニットは、他の隣接する割振りユニットも含む可能性がある範囲を記述する割振り記述子に対応する。ＩＣＢビットマップストリームが、ＩＣＢ範囲コンテナストリームに割り振られた範囲内のどの論理ブロックが、ＩＣＢを含むかを記述するビットマップを含む。したがって、各ＩＣＢは、ＵＤＦボリュームの事前に割り振られた範囲内に記憶される。したがって、すべてのＩＣＢを探し出す必要があるとき、ボリューム全体を探索する、または階層をトラバースする必要がない。
【０００８】
本明細書および特許請求の範囲の全体で、以下の用語は、文脈により別の意味であることが明らかでない限り、以下で明確に関連付けられる意味を有する。
【０００９】
「ユニバーサルディスクフォーマット」および「ＵＤＦ」という用語は、記憶媒体上のデータ互換性を可能にするファイルシステムを定義するOptical Storage Technology Association（ＯＳＴＡ）によって開発された規格を指す。
【００１０】
「情報制御ブロック」および「ＩＣＢ」という用語は、ファイル、およびファイルのデータの場所を定義する属性の集合に対応するＵＤＦファイルシステム内の制御ノードを指す。
【００１１】
「範囲」という用語は、連続する昇順の数値識別子を有するグループの論理ブロックを指す（すなわち、論理ブロックは、ディスク上で連続である）。
【００１２】
「論理ブロック」という用語は、論理ボリュームの中で、またそのボリュームの区画内で割振りに使用されるディスクスペースのユニットを指す。
【００１３】
「論理ブロック番号」または「ＬＢＮ」という用語は、区画内の論理ブロックを一意的に特定するのに使用される指定されたサイズの符号なしの数を指す。
【００１４】
「割振りユニット（allocation unit）」という用語は、何らかの所定の「割振りユニットサイズ」の整数の倍数であるＬＢＮで始まり、長さが「割振りユニットサイズ」ブロックの整数の倍数であるＵＤＦ区画の中の範囲を指す。「割振りユニットサイズ」の通常の値は、該当する場合、基礎のデバイスのＥＣＣブロックサイズに一致する。例えば、割振りユニットサイズは、１６セクタのＥＣＣユニットサイズを有する一般的なＤＶＤ書換え可能媒体の場合、通常、１６ブロックである。
【００１５】
ＵＤＦにおいて、「区画」という用語は、ＵＤＦボリューム当り１つの物理区画が存在するＵＤＦボリュームの中の連続する論理セクタの集合を指す。
【００１６】
例としての動作環境
図１を参照すると、本発明を実施するための一例としてのシステムが、コンピューティングデバイス１００のようなコンピューティングデバイスを含む。非常に基本的な構成では、コンピューティングデバイス１００は、通常、少なくとも１つの処理ユニット１０２およびシステムメモリ１０４を含む。コンピューティングデバイスの厳密な構成およびタイプに依存して、システムメモリ１０４は、揮発性（ＲＡＭなどの）、不揮発性（ＲＯＭ、フラッシュメモリなどの）、または揮発性と不揮発性の何らかの組み合わせであることが可能である。システムメモリ１０４は、通常、オペレーティングシステム１０５、および１つまたは複数のプログラムモジュール１０６を含み、またプログラムデータ１０７を含むことが可能である。この基本構成を図１で、破線１０８で囲った構成要素によって示している。
【００１７】
コンピューティングデバイス１００は、さらなる機構または機能性を有することが可能である。例えば、コンピューティングデバイス１００は、例えば、磁気ディスク、光ストレージ１２０、またはテープなどの追加のデータ記憶デバイス（取外し可能なデバイスおよび／または取外し不可能なデバイス）も含むことが可能である。そのような追加のストレージを図１で取外し可能なストレージ１０９、光ストレージ１２０、および取外し不可能なストレージ１１０によって示している。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報の記憶に関する任意の方法または任意の技術で実装された揮発性媒体および不揮発性媒体、取外し可能な媒体および取外し不可能な媒体を含むことが可能である。システムメモリ１０４、取外し可能なストレージ１０９、光ストレージ１２０、および取外し不可能なストレージ１１０はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタルバーサタイルディスク（ＤＶＤ）または他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶デバイス、あるいは所望の情報を記憶するのに使用することができ、コンピューティングデバイス１００が、アクセスすることができる任意の他の媒体が含まれるが、以上には限定されない。あらゆるそのようなコンピュータ記憶媒体が、デバイス１００の一部であることが可能である。また、コンピューティングデバイス１００は、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなどの入力デバイス１１２も有することが可能である。ディスプレイ、スピーカ、プリンタなどの出力デバイス１１４も、含まれることが可能である。以上のデバイスは、当技術分野で周知であり、本明細書で詳述する必要はない。
【００１８】
また、コンピューティングデバイス１００は、このデバイスが、ネットワークを介するなどして、他のコンピューティングデバイス１１８と通信することができるようにする通信接続１１６も含むことが可能である。通信接続１１６は、通信媒体の一例である。通信媒体は、通常、コンピュータ可読命令、データ構造、プログラムモジュール、あるいは搬送波または他のトランスポート機構などの変調されたデータ信号における他のデータによって実現することができ、任意の情報配信媒体を含む。「変調されたデータ信号」という用語は、信号に情報を符号化するような仕方で特性の１つまたは複数が変更された信号を意味する。例として、限定としてではなく、通信媒体には、有線網または直接有線接続などの有線媒体、ならびに音響媒体、ＲＦ媒体、赤外線媒体、および他の無線媒体などの無線媒体が含まれる。コンピュータ可読媒体という用語は、本明細書では、記憶媒体と通信媒体をともに含むものとして使用する。
【００１９】
図２は、本発明によるＵＤＦファイルシステムを組み込んでいることが可能な光記憶媒体の一例を示している。前述したとおり、光記憶媒体には、コンパクトディスク（ＣＤ）、デジタルバーサタイルディスク（ＤＶＤ）、ＷＯＲＭ（Write-Once，Read-Many）媒体、光ジュークボックス、オートチェンジャ（autochanger）等が含まれる。光記憶媒体は、しばしば、関連する厚さを有する円形ディスクを一部として含む図示した物理プロファイル（２００）を有する。光媒体の物理プロファイルは、様々である可能性がある。また、光記憶媒体の記憶容量も、様々である可能性がある。ＵＤＦファイルシステムは、光記憶媒体でも、他の媒体タイプ（例えば、磁気ディスク等）でも使用することができる。光ディスクは、通常、他の媒体タイプと比べて容量が大きく、可搬性が高く、および耐久性が長続きすることで知られている。
【００２０】
図３は、本発明によるＩＣＢ追跡ストリームを含むＵＤＦファイルシステムのデータ構造を示す例としてのブロック図である。ＵＤＦファイルシステムに関連するデータ構造は、ボリューム空きスペースビットマップ３１０、区画３２０、ＩＣＢ範囲コンテナストリーム３３０、およびＩＣＢビットマップストリーム３４０を含む。
【００２１】
ボリューム空きスペースビットマップ３１０は、区画３２０の各論理ブロックに対応するビットを含むデータ構造である。本発明によれば、区画３２０上の所定数または所定範囲の連続する論理ブロックが、ＩＣＢを記憶するために割り振られる（すなわち、割振りユニット）。区画内で複数の範囲が、ＩＣＢを記憶するために割り振られることが可能である。これらの範囲は、連続している必要はない。この特定の例では、区画３２０の３２の連続する論理ブロックが、割振りユニットに対応する。区画３２０の所定数の連続する論理ブロックが、ＩＣＢを記憶するために割り振られ、ボリューム空きスペースビットマップ３１０が、割り振られた、または使用中の論理ブロック（例えば、０−３１、９５−１２７）に対応するビットを指定することによってその割振りを反映する（凡例を参照）。したがって、ボリューム空きスペースビットマップ３１０は、割り振られた連続する論理ブロックをリストするので、その論理ブロックが、ＩＣＢを記憶するために確保される。ボリューム空きスペースビットマップ３１０は、その連続する論理ブロックの中に他のタイプのデータが記憶されるのを防止するのに役立つ。
【００２２】
区画３２０は、論理ブロックから成り、ディスク上の実際のデータに対応する。前述したとおり、区画３２０上の所定数の連続する論理ブロックが、ＩＣＢを記憶するために割り振られる（例えば、０−３１）。各論理ブロックは、論理ブロック番号（ＬＢＮ）で指定される。各ＬＢＮは、ボリューム空きスペースビットマップ３１０の中で対応するビットを有する。論理ブロックは、ＩＣＢを記憶するために割り振られた連続する論理ブロックの１つの中にＩＣＢを含むことが可能である。区画３２０の他の論理ブロックは、ＩＣＢ追跡に関して未定義の内容を含む。未定義の内容には、区画３２０上に位置する任意の数のファイルに関連するデータが含まれることが可能である。
【００２３】
ＩＣＢ範囲コンテナストリーム３３０は、ＵＤＦ記憶媒体のボリュームの中でＩＣＢを追跡するのに役立つようにＵＤＦファイルシステムのために生成される２つのストリームのうちの１つである。ＩＣＢ範囲コンテナストリーム３３０は、順次割振り記述子（ＡＤ）に従って識別されるストリーム割振りユニットを含む。１つのＡＤが、複数の連続する割振りユニットを特定することが可能である。各ストリーム割振りユニットは、ＩＣＢを記憶するように割り振られている、または割り振られていた区画３２０の中の連続する論理ブロックの各範囲に対応する。このストリームに関するストリーム割振りユニットの最小サイズは、所定である。図示した例によれば、各ストリーム割振りユニットの最小サイズは、３２ブロックである。各ストリーム割振りユニットに関するＡＤは、ＩＣＢ範囲コンテナストリーム３３０のためのいくつかの異なる機能を提供する。疎でない範囲の場合、ＡＤは、ボリューム空きスペースビットマップ３１０の中で割振り済みとしてマークが付けられている論理ブロックを参照する。ＡＤは、「割り振られ、記録済み」タイプか、または「割り振られていない」タイプか、どちらかである。ＡＤは、ストリーム割振りユニットの整数の倍数である論理ブロックの数を記述する。各割振りユニットが、３２の論理ブロックから成る提供した例では、ＡＤを利用して区画３２０に関する３２の論理ブロック、６４の論理ブロック、１２８の論理ブロックなどを記述することができる。ＡＤは、範囲に追加する、または範囲から除去することができる。提供した例では、論理ブロック３２で開始し、長さが３２論理ブロックである範囲において追加する、または除去することができる。同様に、論理ブロック６４で開始し、長さ１２８論理ブロックである範囲においてＡＤを追加する、または除去することができる。各ＡＤは、区画３２０の中の連続する範囲の論理ブロックを参照し、範囲コンテナストリームＩＣＢ、または関連するＡＤ連続範囲の中に記憶される。
【００２４】
ＩＣＢビットマップストリーム３４０は、取外し可能な記憶媒体のボリュームの中でＩＣＢを追跡するのに役立つＵＤＦファイルシステムのために生成される２つのストリームのもう一方である。ＩＣＢビットマップストリーム３４０は、ＩＣＢ範囲コンテナストリーム３３０の中でブロックのどれが割り振られ、ＩＣＢを記憶しているかを記述するビットマップを含む。ＩＣＢビットマップストリーム３４０の各ビットは、ＩＣＢ範囲コンテナストリーム３３０の中のブロックに対応する。例えば、ＩＣＢビットマップストリーム３４０のビット０が、ＩＣＢ範囲コンテナストリーム３３０の中の第１のブロックに対応し、またビット１が、第２のブロックに対応する。ＩＣＢビットマップストリーム３４０の中のビットが、クリア（すなわち、ゼロ）である場合は、ＩＣＢ範囲コンテナストリーム３３０によって参照される区画３２０の対応する論理ブロックは、ＩＣＢによる使用に利用することができる。ＩＣＢビットマップストリームの中のビットが設定されている場合、ＩＣＢ範囲コンテナストリーム３３０によって参照される区画３２０の対応する論理ブロックは、ＩＣＢによって使用中であるか、またはＩＣＢ範囲コンテナストリーム３３０の疎な領域内にあり、したがって、どの論理ブロックにも対応しない。
【００２５】
ＩＣＢ範囲コンテナストリーム３３０およびＩＣＢビットマップストリーム３４０が最初に生成されるとき、範囲内の所定の論理ブロックが確保されて、ＩＣＢ範囲コンテナストリーム３３０およびＩＣＢビットマップストリーム３４０を表す。言い換えれば、区画上に位置するＩＣＢは、ＩＣＢ範囲コンテナストリーム３３０の属性を記述するＩＣＢ範囲コンテナストリーム３３０に関するＩＣＢである。別の実施形態では、区画上に位置するＩＣＢは、ＩＣＢビットマップストリーム３４０の属性を記述するＩＣＢビットマップストリーム３４０に関するＩＣＢである。
【００２６】
さらなる実施形態では、ＩＣＢ範囲コンテナストリーム３３０およびＩＣＢビットマップストリーム３４０は、関連する情報長を有する。関連する情報長は、ＩＣＢ範囲コンテナストリーム３３０およびＩＣＢビットマップストリーム３４０のバイトのサイズを示す。
【００２７】
さらに別の実施形態では、区画３２０上に記憶された各ＩＣＢが、ＩＣＢ範囲コンテナストリーム３３０の中のブロックのオフセットに対する参照エントリを含む。このオフセットは、ＩＣＢ範囲コンテナストリーム３３０の中のブロックのブロック番号に対応する。ＩＣＢの割振り解除中、このオフセットを利用して、ＩＣＢビットマップストリーム３４０の中で割振り解除されるＩＣＢに対応するビットを探し出す。ＩＣＢを割振り解除することに関する例としてのプロセスを、以下で図７に関連してさらに説明する。
【００２８】
図４は、本発明による新しいＩＣＢを割り振るための論理を示す流れ図である。このプロセスは、開始ブロック４０１で始まり、ＩＣＢ範囲コンテナストリームおよびＩＣＢビットマップストリームが、ＵＤＦファイルシステムのために前に生成されており、新しいＩＣＢが割り振られる。プロセス４００は、決定ブロック４０２に進む。
【００２９】
決定ブロック４０２で、ＩＣＢビットマップストリームの中でクリアビットが利用可能であるかどうかの判定が行われる。ＩＣＢビットマップストリームを探索し、ゼロ値を有するビットを探し出すことが、ＩＣＢ範囲コンテナストリームの中でブロックを探し出すことに対応する。ＩＣＢ範囲コンテナストリームの中で探し出されたブロックは、ＩＣＢとして割り振るのに利用可能である区画上の論理ブロックに対応する。ＩＣＢビットマップストリームの中でクリアビットが探し出された場合、プロセスは、ブロック４０３に進む。しかし、新しいＩＣＢを割り振るためにＩＣＢビットマップストリームの中で利用可能なクリアビットが存在しない場合、プロセスは、ブロック４０６に進む。
【００３０】
ブロック４０６で、図５で示したプロセス５００と同様のプロセスを利用してＩＣＢ範囲コンテナストリームが拡張されて、ＩＣＢを記憶するために利用することができる区画上のさらなる割り振られた論理ブロックが提供される。ＩＣＢを記憶するためにさらなる論理ブロックが利用可能になると、プロセスは、ブロック４０２に戻る。
【００３１】
ブロック４０３で、ＩＣＢビットマップストリームの中に位置するクリアビットが、「１」に設定される。このビットを「１」に設定することにより、この設定されたビットに対応するＩＣＢ範囲コンテナストリームブロックによって参照される区画の論理ブロックを新しいＩＣＢのために使用できることが示される。プロセスは、ブロック４０４に進む。
【００３２】
ブロック４０４で、新しいＩＣＢが、設定されたビットに対応する区画の論理ブロックの中に記憶される。そのＩＣＢを含む論理ブロックのＩＣＢコンテナストリームの中におけるオフセットが、そのＩＣＢの中に記憶される。処理は、ブロック４０５に進み、終了する。
【００３３】
図５は、本発明によるＩＣＢコンテナストリームを拡張するための論理を示す流れ図である。このプロセスは、開始ブロック５０１で始まり、ＩＣＢ範囲コンテナストリームが、ＵＤＦファイルシステムのために前に生成されている。プロセス５００は、決定ブロック５０２に進む。
【００３４】
決定ブロック５０２Ａで、割振りユニットに関して前述したサイズ要件および整列要件を満たすある範囲の割り振られていない論理ブロックが、区画の中で存在するかどうかの判定が行われる。そのような範囲が存在しない場合、プロセス５００は、失敗し、ブロック５０８に進んで終了する。割り振られていない範囲が存在する場合、プロセスは、５０２Ｂに進む。
【００３５】
決定ブロック５０２Ｂで、ＩＣＢ範囲コンテナストリームのＩＣＢまたは何らかの関連するＡＤ連続範囲の中で、別のＡＤのための十分なスペースが存在するかどうかの判定が行われる。範囲コンテナストリームＩＣＢおよび何らかの関連するＡＤ連続範囲は、ＩＣＢ範囲コンテナストリームの範囲を記述するＡＤを含む。新しいＡＤを追加するのに十分なスペースが利用可能である場合、プロセスは、ブロック５０４に進む。しかし、十分なスペースが利用可能ではない場合、プロセスは、ブロック５０３に進む。
【００３６】
ブロック５０３で、さらなるＡＤを記憶するための新しいＡＤ連続範囲が、ＩＣＢ範囲コンテナストリームの中で現在、利用可能なＡＤを超えて割り振られ、また新しい範囲を参照する「連続範囲（continuation extent）」タイプのＡＤが、ＩＣＢの中の既存のＡＤの終りに、または最後の既存のＡＤ連続範囲の終りに追加される。プロセスは、ブロック５０４に進む。
【００３７】
ブロック５０４で、ＩＣＢビットマップストリームが、必要とされる場合、ＩＣＢ範囲コンテナストリームの計画される拡張と一致するように拡張される。ＩＣＢビットマップストリーム割振りは、ＩＣＢ範囲コンテナストリームに追加されるブロックの数に対応するビットの数だけ増加される。ＩＣＢビットマップストリームに追加を行うことにより、ＩＣＢビットマップストリームの情報長が変化させられる。情報長は、追加のビットを加えた結果の、ＩＣＢビットマップストリームの増大したサイズに対応するように更新される。プロセスは、ブロック５０５に進む。
【００３８】
ブロック５０５で、ある連続する範囲の論理ブロックが、区画から、ＩＣＢ範囲コンテナストリームの追加されるＡＤ連続範囲に対応するように、ボリュームビットマップの中で対応するビットを割振り済みとしてマーク付けすることによって割り振る。この範囲は、割振りユニットに関して前に定義した制約を満たす。プロセスは、ブロック５０６に進む。
【００３９】
ブロック５０６で、新しい割振り記述子（ＡＤ）が、ＩＣＢ範囲コンテナストリームＡＤに追加される。新しいＡＤは、区画の中でＩＣＢを記憶するように新たに割り振られた論理ブロックの連続する範囲に対応し、この範囲を記述する。新しいＡＤをＩＣＢ範囲コンテナストリームに追加することにより、ＩＣＢ範囲コンテナストリームの情報長が変化させられる。情報長は、範囲を追加したことの結果の、ＩＣＢ範囲コンテナストリームの増大したサイズに対応するように更新される。プロセスは、ブロック５０７に進む。
【００４０】
ブロック５０７で、ＩＣＢ範囲コンテナストリームに追加された新しい範囲に対応するＩＣＢビットマップストリームのビットがクリアされる（すなわち、ゼロに設定される）。ビットをクリアすることは、区画内の対応する範囲の論理ブロックが、ＩＣＢのために使用されるように利用可能なことを意味する。適切なビットをクリアした後、プロセスは、ブロック５０８に進んで終了する。
【００４１】
図６は、本発明によるＩＣＢコンテナストリームから区画スペースを取り戻すための論理を示す流れ図である。プロセスは、ブロック６０１で始まり、ＩＣＢ範囲コンテナストリームの一部分をボリュームに取り戻す決定が前に行われている。一実施形態では、取り戻されるように利用可能なＩＣＢ範囲コンテナストリームの範囲は、現在、アクティブなＩＣＢを全く含んでいない範囲である。プロセス６００は、決定ブロック６０２に進む。
【００４２】
決定ブロック６０２で、ＩＣＢ範囲コンテナストリームの一部分を、ＩＣＢ範囲コンテナストリームを切り捨てることによって取り戻すかどうかの決定が行われる。ＩＣＢ範囲コンテナストリームを切り捨てる決定が行われた場合、プロセスは、ブロック６０５に進む。しかし、ＩＣＢ範囲コンテナストリームを切り捨てることなくＩＣＢ範囲コンテナストリームの一部分を取り戻す決定が行われた場合、プロセスは、ブロック６０３に進む。
【００４３】
ブロック６０３および６０４は、ＩＣＢ範囲コンテナストリームを切り捨てることなく、ＩＣＢ範囲コンテナストリームの一部分をボリュームに取り戻すための方法を提供する。ブロック６０３で、ＩＣＢ範囲コンテナストリームの範囲に対応するＩＣＢビットマップストリームのビットが、「１」に設定される。取り戻される範囲は、ＩＣＢを全く含んでいなかったので、この範囲の各ビットは、クリア状態（「０」）から設定状態（「１」）に変更される。それらのビットを「１」に設定することにより、それらのビットに対応する区画の論理ブロックが、ＩＣＢを記憶するのにもはや利用できないことが示される。プロセスは、ブロック６０４に進む。
【００４４】
ブロック６０４で、ＩＣＢ範囲コンテナストリームから取り戻される範囲の割振り記述子（ＡＤ）が書き込まれて、その範囲が、「疎」（論理ブロックを全く参照していない）として記述されるようになる。これは、ＡＤが、現時点で割振り解除された範囲と、他の連続しているが、まだ割り振られている範囲の両方を記述する場合、ＡＤを分割することを必要とする可能性がある。疎のＡＤにより、他のデータをボリューム上に記憶すること、ＩＣＢ範囲コンテナストリームの開放されたスペースの中に記憶することが可能になる。プロセスは、ブロック６０７に進む。
【００４５】
ブロック６０５および６０６が、ＩＣＢ範囲コンテナストリームを切り捨てることによってＩＣＢ範囲コンテナストリームの一部分をボリュームに取り戻すための方法を提供する。
【００４６】
ブロック６０５で、ＩＣＢビットマップストリームに関連する情報長が更新されて、ＩＣＢ範囲コンテナストリームの少なくとも１つのストリーム割振りユニットに対応するビットの一部分が除去される。情報長を更新することにより、ＩＣＢビットマップストリームが、基本的に短くされ、ＩＣＢビットマップストリームから所定数のビットが取り除かれる。プロセスは、ブロック６０６に進む。
【００４７】
ブロック６０６で、ＩＣＢ範囲コンテナストリームに関連する情報長が、ＩＣＢビットマップストリームに関連する情報長の変化に対応するように更新される。ＩＣＢビットマップストリームの各ビットは、ＩＣＢ範囲コンテナストリームのブロックに対応する。ＩＣＢビットマップストリームのビットが取り除かれると、ＩＣＢ範囲コンテナストリームの中でそれらのビットに対応する範囲のブロックも取り除かれる。ＩＣＢ範囲コンテナストリームに関連する情報長は、取り除かれた範囲に対応するように更新される。範囲コンテナストリームから切り捨てられた範囲を記述するＩＣＢコンテナストリームＡＤの部分が、取り除かれる。プロセスは、６０７に進む。
【００４８】
ブロック６０７で、ボリュームに取り戻された範囲のブロックに対応するボリューム空きスペースビットマップのビットが、クリアされる。このビットをクリアすることにより、ＵＤＦファイルシステムの中で、ＩＣＢ以外のタイプのデータを記憶するためにその論理ブロックが利用可能なことが示される。ボリューム空きスペースビットマップが、その範囲が割振り解除されたことを反映した後、プロセスは、ブロック６０８に進んで終了する。
【００４９】
図７は、本発明によるＩＣＢを割振り解除するための論理を示す流れ図である。このプロセスは、開始ブロック７０１で始まり、区画上に記憶されたＩＣＢが、割振り解除される。ＩＣＢを割振り解除することにより、ボリューム上の論理ブロックが、異なるＩＣＢを記憶するようにクリアされる。プロセス７００は、ブロック７０２に進む。
【００５０】
ブロック７０２で、ＩＣＢが生成された際にＩＣＢの中に記憶されたオフセット（図３の説明を参照）が検査されて、ＩＣＢ範囲コンテナストリームの中のＩＣＢに対応するブロックの場所が決定され、したがって、ＩＣＢビットマップストリームの中の対応するビットが決定される。プロセスは、ブロック７０３に進む。
【００５１】
ブロック７０３で、ＩＣＢ範囲コンテナストリームの中で探し出されたブロックに対応するＩＣＢビットマップストリームの中のビットがクリアされる（すなわち、ゼロに設定される）。そのビットをクリアすることにより、対応するブロックが、別のＩＣＢによる使用のために利用可能になる。プロセスは、ブロック７０４に進んで終了する。
【００５２】
以上の明細、例、およびデータにより、本発明の構成の製造および使用の完全な説明が提供される。本発明の趣旨および範囲を逸脱することなく、本発明の多数の実施形態を実施することができるので、本発明は、頭記の特許請求の範囲に存する。
【図面の簡単な説明】
【図１】本発明の一例としての実施形態で使用することができる例としてのコンピューティングデバイスを示す図である。
【図２】本発明によるＵＤＦファイルシステムを組み込むことが可能な光記憶媒体の例を示す図である。
【図３】本発明によるＩＣＢ追跡ストリームを含むＵＤＦファイルシステムのデータ構造を示す例としてのブロック図である。
【図４】本発明による新しいＩＣＢを割り振るための論理を示す流れ図である。
【図５】本発明によるＩＣＢコンテナストリームを拡張するための論理を示す流れ図である。
【図６】本発明によるＩＣＢコンテナストリームからスペースを取り戻すための論理を示す流れ図である。
【図７】本発明によるＩＣＢの割振り解除を行うための論理を示す流れ図である。
【符号の説明】
ＡＤ  割振り記述子
ＩＣＢ  情報制御ブロック
ＬＢＮ  論理ブロック番号
０、３１、３２、６３、６４、９５、１２７、１５９、１９１  論理ブロック
１００  コンピューティングデバイス
１０２  処理ユニット
１０４  システムメモリ
１０５  オペレーティングシステム
１０６  プログラムモジュール
１０７  プログラムデータ
１０９，１１０  ストレージ
１１２  入力デバイス
１１４  出力デバイス
１１６  通信接続
１１８  コンピューティングデバイス
１２０  光ストレージ
３１０  ボリューム空きスペースビットマップ
３２０  区画
３３０  ＩＣＢ範囲コンテナストリーム
３４０  ＩＣＢビットマップストリーム
【図１】
0004310120.tif 000002
【図２】
0004310120.tif 000003
【図３】
0004310120.tif 000004
【図４】
0004310120.tif 000005
【図５】
0004310120.tif 000006
【図６】
0004310120.tif 000007
【図７】
0004310120.tif 000008