(57)【要約】  本願は、記憶装置を管理する方法およびシステムを含む。１つのインプリメンテーションでは、ホストまたは記憶装置に存在するストレージアロケータが、記憶装置の記憶領域にファイルを格納する要求を受け取る。ストレージアロケータは、記憶装置と関連付けられているファイルシステム構造においてファイルを廃棄可能とマーキングし、ファイルに割り当てられているクラスタチェーンをファイルと関連付けるためにプライマリファイルアロケーションテーブル（「ＦＡＴ」）を更新する。ストレージアロケータは、さらに、ファイルの物理的位置を表すように廃棄可能ＦＡＴまたはデータベースを更新するかあるいはファイルの物理的位置を記憶する１つ以上のロケーションファイルを生成することができる。ストレージアロケータは、その後、ＦＡＴと、ファイルの物理的位置を示す廃棄可能ＦＡＴ、データベース、または１つ以上のロケーションファイルとに基づいて記憶領域装置を管理する。
2012512460.tif 000002
【特許請求の範囲】
【請求項１】
記憶装置を管理する方法であって、
記憶装置が動作可能に結合されているホストにおいて、
プライマリファイルアロケーションテーブル（「ＦＡＴ」）と、さらに廃棄可能ＦＡＴとを包含する前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させるステップと、
前記記憶装置における前記第１のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させるステップと、
前記廃棄可能ＦＡＴに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記クラスタチェーンは、少なくとも前記第１のファイルの物理的位置をマスクする方法。
【請求項３】
請求項１記載の方法において、
ホストオペレーティングシステムが前記第１のファイルにアクセスすることを阻止することを前記第１のファイルと関連付けられている属性により可能にするステップをさらに含む方法。
【請求項４】
請求項１記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルおよび前記第２のファイルと関連付けられるクラスタチェーンを前記第２のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させるステップと、
前記第２のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させるステップと、
をさらに含む方法。
【請求項５】
請求項４記載の方法において、
前記クラスタチェーンは、前記第１のファイルおよび前記第２のファイルの物理的位置をマスクする方法。
【請求項６】
請求項１記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第２のファイルに割り当てられている第２のクラスタチェーンを前記第２のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させるステップと、
前記第２のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させるステップと、
をさらに含む方法。
【請求項７】
請求項１記載の方法において、
前記第１のファイルを非廃棄可能ファイルとマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルの物理的位置を表すように、前記記憶装置に前記プライマリＦＡＴを更新させるステップと、
前記第１のファイルの物理的位置を除去するために、前記記憶装置に前記廃棄可能ＦＡＴを更新させるステップと、
をさらに含む方法。
【請求項８】
請求項７記載の方法において、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別するステップをさらに含み、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていないことを示した後に、前記第１のファイルは非廃棄可能ファイルとマーキングされる方法。
【請求項９】
請求項１記載の方法において、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別するステップと、
前記第１のファイルと関連付けられている変換ロック識別子の値を識別して判定が前記第１のファイルがロックされていることを示した後に、前記第１のファイルを非廃棄可能とマーキングすることを禁じるステップと、
をさらに含む方法。
【請求項１０】
請求項１記載の方法において、
ユーザＩＤと、前記第１のファイルと関連付けられているプレビューファイルとに関連付けられているファイルパーミッションを識別するステップと、
前記識別されたファイルパーミッションに基づいて前記第１のファイルと関連付けられているプレビューファイルへのアクセスを管理するステップと、
をさらに含む方法。
【請求項１１】
請求項１０記載の方法において、
前記ユーザＩＤは、共有ユーザＩＤである方法。
【請求項１２】
請求項１記載の方法において、
前記プライマリＦＡＴのクラスタチェーンは、前記廃棄可能ＦＡＴ内の位置を指す方法。
【請求項１３】
請求項１記載の方法において、
前記第１のファイルを廃棄可能とマーキングするステップは、前記第１のファイルに廃棄優先レベルを割り当てることを含む方法。
【請求項１４】
請求項１３記載の方法において、
前記第１のファイルに廃棄優先レベルを割り当てることは、
対応する値を、前記第１のファイルに対応するプライマリＦＡＴエントリ内のｍ個の最上位ビットにセットすること、あるいは
対応する値を、前記第１のファイルに対応するファイルシステムエントリ内のデータフィールドにセットすることのうちの少なくとも１つを含む方法。
【請求項１５】
請求項１３記載の方法において、
前記廃棄優先レベルは、
前記第１のファイルの予想される使用、
前記第１のファイルの使用と関連付けられる予想される収益、
前記第１のファイルのファイルタイプ、
前記第１のファイルのサイズ、
前記記憶装置における前記第１のファイルの位置、および
前記第１のファイルの古さ、のうちのいずれか１つに従って前記第１のファイルに割り当てられる方法。
【請求項１６】
請求項１記載の方法において、
前記廃棄可能ＦＡＴに従って前記記憶装置の記憶領域を管理するステップは、
廃棄可能とマーキングされている１つ以上のファイルを選択的に除去することによってストレージ使用安全マージンを回復すること、
廃棄可能とマーキングされている全てのファイルを除去することによって記憶領域を解放すること、および
前記第１のファイルのクラスタをより低い性能の記憶モジュールへ再マッピングすることのうちのいずれか１つまたはこれらの組み合わせを含む方法。
【請求項１７】
記憶装置を管理する方法であって、
ホストに動作可能に結合されている記憶装置において、
プライマリファイルアロケーションテーブル（「ＦＡＴ」）と、さらに廃棄可能ＦＡＴとを包含する前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記プライマリＦＡＴを更新するステップと、
前記記憶装置内の前記第１のファイルの物理的位置を表すように、前記廃棄可能ＦＡＴを更新するステップと、
前記廃棄可能ＦＡＴに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項１８】
請求項１７記載の方法において、
前記クラスタチェーンは、少なくとも前記第１のファイルの物理的位置をマスクする方法。
【請求項１９】
請求項１７記載の方法において、
ホストオペレーティングシステムが前記第１のファイルにアクセスすることを阻止することを前記第１のファイルと関連付けられている属性により可能にするステップをさらに含む方法。
【請求項２０】
請求項１７記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルおよび前記第２のファイルと関連付けられるクラスタチェーンを前記第２のファイルと関連付けるために、前記プライマリＦＡＴを更新するステップと、
前記第２のファイルの物理的位置を表すように、前記廃棄可能ＦＡＴを更新するステップと、
をさらに含む方法。
【請求項２１】
請求項２０記載の方法において、
前記クラスタチェーンは、前記第１のファイルおよび前記第２のファイルの物理的位置をマスクする方法。
【請求項２２】
請求項１７記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第２のファイルに割り当てられている第２のクラスタチェーンを前記第２のファイルと関連付けるために、前記プライマリＦＡＴを更新するステップと、
前記第２のファイルの物理的位置を表すように、前記廃棄可能ＦＡＴを更新するステップと、
をさらに含む方法。
【請求項２３】
請求項１７記載の方法において、
前記第１のファイルを非廃棄可能ファイルとマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられている前記ファイルシステム構造において行われるステップと、
前記第１のファイルの物理的位置を表すように、前記プライマリＦＡＴを更新するステップと、
前記第１のファイルの物理的位置を除去するために、前記廃棄可能ＦＡＴを更新するステップと、
をさらに含む方法。
【請求項２４】
請求項２３記載の方法において、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別するステップをさらに含み、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていないことを示した後に、前記第１のファイルは非廃棄可能ファイルとマーキングされる方法。
【請求項２５】
請求項１７記載の方法において、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別するステップと、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていることを示した後に、前記第１のファイルを非廃棄可能とマーキングすることを禁じるステップと、
をさらに含む方法。
【請求項２６】
請求項１７記載の方法において、
ユーザＩＤと、前記第１のファイルと関連付けられているプレビューファイルとに関連付けられているファイルパーミッションを識別するステップと、
前記識別されたファイルパーミッションに基づいて前記第１のファイルと関連付けられているプレビューファイルへのアクセスを管理するステップと、
をさらに含む方法。
【請求項２７】
請求項１７記載の方法において、
前記ユーザＩＤは、共有ユーザＩＤである方法。
【請求項２８】
請求項１７記載の方法において、
前記プライマリＦＡＴのクラスタチェーンは、前記廃棄可能ＦＡＴ内の位置を指す方法。
【請求項２９】
請求項１７記載の方法において、
前記第１のファイルを廃棄可能とマーキングするステップは、前記第１のファイルに廃棄優先レベルを割り当てることを含む方法。
【請求項３０】
請求項２９記載の方法において、
前記第１のファイルに廃棄優先レベルを割り当てることは、
対応する値を、前記第１のファイルに対応するプライマリＦＡＴエントリ内のｍ個の最上位ビットにセットすること、あるいは
対応する値を、前記第１のファイルに対応するファイルシステムエントリ内のデータフィールドにセットすることのうちの少なくとも１つを含む方法。
【請求項３１】
請求項２９記載の方法において、
前記廃棄優先レベルは、
前記第１のファイルの予想される使用、
前記第１のファイルの使用と関連付けられる予想される収益、
前記第１のファイルのファイルタイプ、
前記第１のファイルのサイズ、
前記記憶装置における前記第１のファイルの位置、および
前記第１のファイルの古さ、のうちのいずれか１つに従って前記第１のファイルに割り当てられる方法。
【請求項３２】
請求項１７記載の方法において、
前記廃棄可能ＦＡＴに従って前記記憶装置の記憶領域を管理するステップは、
廃棄可能とマーキングされている１つ以上のファイルを選択的に除去することによってストレージ使用安全マージンを回復すること、
廃棄可能とマーキングされている全てのファイルを除去することによって記憶領域を解放すること、および
前記第１のファイルのクラスタをより低い性能の記憶モジュールへ再マッピングすることのうちのいずれか１つまたはこれらの組み合わせを含む方法。
【請求項３３】
記憶装置を管理するためのストレージアロケータであって、
記憶装置および前記記憶装置のホストとインターフェイスするための通信インターフェイスと、
前記記憶装置と関連付けられているファイルシステムを格納するためのストレージユニットと、
前記記憶装置と関連付けられているファイルシステムを管理するためのプロセッサと、を備え、
前記プロセッサは、
プライマリファイルアロケーションテーブル（「ＦＡＴ」）と、さらに廃棄可能ＦＡＴとを包含する前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取り、
前記第１のファイルの廃棄可能とのマーキングを、前記記憶装置と関連付けられているファイルシステム構造において行い、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させ、
前記記憶装置における前記第１のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させ、
前記廃棄可能ＦＡＴに従って前記記憶装置の記憶領域を管理するように構成されるストレージアロケータ。
【請求項３４】
請求項３３記載のストレージアロケータにおいて、
前記クラスタチェーンは、前記第１のファイルの物理的位置をマスクするストレージアロケータ。
【請求項３５】
請求項３３記載のストレージアロケータにおいて、
前記プロセッサは、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取り、
前記第２のファイルの廃棄可能とのマーキングを、前記記憶装置と関連付けられているファイルシステム構造において行い、
前記第１のファイルおよび前記第２のファイルと関連付けられるクラスタチェーンを前記第２のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させ、
前記第２のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させるようにさらに構成され、
前記廃棄可能クラスタチェーンは、前記第１のファイルおよび前記第２のファイルの物理的位置をマスクするストレージアロケータ。
【請求項３６】
請求項３３記載のストレージアロケータにおいて、
前記プロセッサは、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取り、
前記第２のファイルの廃棄可能とのマーキングを、前記記憶装置と関連付けられているファイルシステム構造において行い、
前記第２のファイルに割り当てられている第２のクラスタチェーンを前記第２のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させ、
前記第２のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させるようにさらに構成されるストレージアロケータ。
【請求項３７】
請求項３３記載のストレージアロケータにおいて、
前記プロセッサは、
前記第１のファイルの非廃棄可能ファイルとのマーキングを、前記記憶装置と関連付けられているファイルシステム構造において行い、
前記第１のファイルの物理的位置を表すように、前記記憶装置に前記プライマリＦＡＴを更新させ、
前記第１のファイルの物理的位置を除去するために、前記記憶装置に前記廃棄可能ＦＡＴを更新させるようにさらに構成されるストレージアロケータ。
【請求項３８】
請求項３７記載のストレージアロケータにおいて、
前記プロセッサは、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別するようにさらに構成され、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていないことを示した後に、前記第１のファイルは非廃棄可能ファイルとマーキングされるストレージアロケータ。
【請求項３９】
請求項３３記載のストレージアロケータにおいて、
前記プロセッサは、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別し、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていることを示した後に、前記第１のファイルを非廃棄可能とマーキングすることを禁じるようにさらに構成されるストレージアロケータ。
【請求項４０】
請求項３３記載のストレージアロケータにおいて、
前記プロセッサは、
ユーザＩＤと、前記第１のファイルと関連付けられているプレビューファイルとに関連付けられているファイルパーミッションを識別し、
前記識別されたファイルパーミッションに基づいて前記第１のファイルと関連付けられているプレビューファイルへのアクセスを管理するようにさらに構成されるストレージアロケータ。
【請求項４１】
請求項３３記載のストレージアロケータにおいて、
前記プライマリＦＡＴのクラスタチェーンは、前記廃棄可能ＦＡＴ内の位置を指すストレージアロケータ。
【請求項４２】
記憶システムであって、
通信インターフェイスと、
記憶装置と関連付けられているファイルシステムを管理するためのストレージアロケータであって、前記記憶装置の記憶領域における１つ以上のファイルの記憶を管理するためのプロセッサを含むストレージアロケータと、を備え、
前記プロセッサは、
プライマリファイルアロケーションテーブル（「ＦＡＴ」）と、さらに廃棄可能ＦＡＴとを包含する前記記憶装置の記憶領域に第１のファイルを格納する要求を前記通信インターフェイスを介して受け取り、
前記第１のファイルの廃棄可能とのマーキングを、前記記憶装置と関連付けられているファイルシステム構造において行い、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記記憶装置に前記プライマリＦＡＴを更新させ、
前記記憶装置における前記第１のファイルの物理的位置を表すように、前記記憶装置に前記廃棄可能ＦＡＴを更新させ、
前記廃棄可能ＦＡＴに従って前記記憶装置の記憶領域を管理するように構成される記憶システム。
【請求項４３】
請求項４２記載の記憶システムにおいて、
前記プロセッサは、
前記第１のファイルの非廃棄可能ファイルとのマーキングを、前記記憶装置と関連付けられているファイルシステム構造において行い、
前記第１のファイルの物理的位置を表すように、前記記憶装置に前記プライマリＦＡＴを更新させ、
前記第１のファイルの物理的位置を除去するために、前記記憶装置に前記廃棄可能ＦＡＴを更新させるようにさらに構成される記憶システム。
【請求項４４】
請求項４３記載の記憶システムにおいて、
前記プロセッサは、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別するようにさらに構成され、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていないことを示した後に、前記第１のファイルは非廃棄可能ファイルとマーキングされる記憶システム。
【請求項４５】
請求項４２記載の記憶システムにおいて、
前記プロセッサは、
前記第１のファイルが廃棄可能ファイルから非廃棄可能ファイルに変換され得るかを判定するために前記第１のファイルと関連付けられている変換ロック識別子の値を識別し、
前記第１のファイルと関連付けられている変換ロック識別子の値の判定が前記第１のファイルがロックされていることを示した後に、前記第１のファイルを非廃棄可能とマーキングすることを禁じるようにさらに構成される記憶システム。
【請求項４６】
請求項４２記載の記憶システムにおいて、
前記プロセッサは、
ユーザＩＤと、前記第１のファイルと関連付けられているプレビューファイルとに関連付けられているファイルパーミッションを識別し、
前記識別されたファイルパーミッションに基づいて前記第１のファイルと関連付けられているプレビューファイルへのアクセスを管理するようにさらに構成される記憶システム。
【請求項４７】
請求項４２記載の記憶システムにおいて、
前記記憶装置の記憶領域に第１のファイルを格納する要求を前記通信インターフェイスを介して受け取るために、前記プロセッサは、前記通信インターフェイスを介して受け取られた前記第１のファイルと関連付けられている１つ以上の書き込み要求に基づいて、前記第１のファイルを格納する要求を導出するように構成される記憶システム。
【請求項４８】
請求項４２記載の記憶システムにおいて、
前記ストレージアロケータは、ホストに埋め込まれている記憶システム。
【請求項４９】
請求項４２記載の記憶システムにおいて、
前記ストレージアロケータは、記憶装置に埋め込まれている記憶システム。
【請求項５０】
記憶装置を管理する方法であって、
記憶装置が動作可能に結合されているホストにおいて、
前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記記憶装置にファイルアロケーションテーブル（「ＦＡＴ」）を更新させるステップと、
前記記憶装置における前記第１のファイルの物理的位置を表すように、データベースを更新するステップと、
前記ＦＡＴおよび前記データベースに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項５１】
記憶装置を管理する方法であって、
ホストに動作可能に結合されている記憶装置において、
前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、ファイルアロケーションテーブル（「ＦＡＴ」）を更新するステップと、
前記記憶装置における前記第１のファイルの物理的位置を表すように、データベースを更新するステップと、
前記ＦＡＴおよび前記データベースに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項５２】
記憶装置を管理する方法であって、
記憶装置が動作可能に結合されているホストにおいて、
前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記記憶装置にファイルアロケーションテーブル（「ＦＡＴ」）を更新させるステップと、
前記記憶装置における前記第１のファイルの物理的位置を表すように、ロケーションファイルを更新するステップと、
前記ＦＡＴおよび前記ロケーションファイルに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項５３】
請求項５２記載の方法において、
前記ロケーションファイルは、テキストファイルである方法。
【請求項５４】
請求項５２記載の方法において、
前記ロケーションファイルは、バイナリファイルである方法。
【請求項５５】
記憶装置を管理する方法であって、
ホストに結合されている記憶装置において、
前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、ファイルアロケーションテーブル（「ＦＡＴ」）を更新するステップと、
前記記憶装置における前記第１のファイルの物理的位置を表すように、ロケーションファイルを更新するステップと、
前記ＦＡＴおよび前記ロケーションファイルに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項５６】
記憶装置を管理する方法であって、
記憶装置が動作可能に結合されているホストにおいて、
前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、前記記憶装置にファイルアロケーションテーブル（「ＦＡＴ」）を更新させるステップと、
前記ＦＡＴの中で前記第１のファイルと関連付けられているクラスタチェーンの２つ以上のクラスタの順序をスクランブルするステップと、
前記第１のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む前記ＦＡＴ内の第１のレンジファイルを作成するステップと、
前記ＦＡＴおよび前記第１のレンジファイルに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項５７】
請求項５６記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルおよび前記第２のファイルと関連付けられるクラスタチェーンを前記第２のファイルと関連付けるために、前記記憶装置に前記ＦＡＴを更新させるステップと、
前記ＦＡＴの中で前記第２のファイルと関連付けられているクラスタチェーンの２つ以上のクラスタの順序をスクランブルするステップと、
をさらに含む方法。
【請求項５８】
請求項５７記載の方法において、
前記第２のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含むように前記ＦＡＴ内の第１のレンジファイルを更新するステップをさらに含む方法。
【請求項５９】
請求項５６記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第２のファイルに割り当てられている第２のクラスタチェーンを前記第２のファイルと関連付けるために、前記記憶装置に前記ＦＡＴを更新させるステップと、
前記ＦＡＴの中で前記第２のファイルと関連付けられている第２のクラスタチェーンの２つ以上のクラスタの順序をスクランブルするステップと、
前記第２のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む前記ＦＡＴ内の第２のレンジファイルを作成するステップと、をさらに含み、
前記ＦＡＴおよび前記第１のレンジファイルに従って前記記憶装置の記憶領域を管理するステップは、前記ＦＡＴ、前記第１のレンジファイルおよび前記第２のレンジファイルに従って前記記憶装置の記憶領域を管理することを含む方法。
【請求項６０】
請求項５６記載の方法において、
前記第１のレンジファイルを含まない、前記第１のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む前記ＦＡＴ内の第２のレンジファイルを作成するステップをさらに含み、
前記ＦＡＴおよび前記第１のレンジファイルに従って前記記憶装置の記憶領域を管理するステップは、前記ＦＡＴ、前記第１のレンジファイルおよび前記第２のレンジファイルに従って前記記憶装置の記憶領域を管理することを含む方法。
【請求項６１】
記憶装置を管理する方法であって、
ホストに結合されている記憶装置において、
前記記憶装置の記憶領域に第１のファイルを格納する要求を受け取るステップと、
前記第１のファイルを廃棄可能とマーキングするステップであって、前記第１のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルに割り当てられているクラスタチェーンを前記第１のファイルと関連付けるために、ファイルアロケーションテーブル（「ＦＡＴ」）を更新するステップと、
前記ＦＡＴの中で前記第１のファイルと関連付けられているクラスタチェーンの２つ以上のクラスタの順序をスクランブルするステップと、
前記第１のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む前記ＦＡＴ内の第１のレンジファイルを作成するステップと、
前記ＦＡＴおよび前記第１のレンジファイルに従って前記記憶装置の記憶領域を管理するステップと、
を含む方法。
【請求項６２】
請求項６１記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられているファイルシステム構造において行われるステップと、
前記第１のファイルおよび前記第２のファイルと関連付けられるクラスタチェーンを前記第２のファイルと関連付けるために、前記ＦＡＴを更新するステップと、
前記ＦＡＴの中で前記第２のファイルと関連付けられているクラスタチェーンの２つ以上のクラスタの順序をスクランブルするステップと、
をさらに含む方法。
【請求項６３】
請求項６１記載の方法において、
前記第２のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含むように前記ＦＡＴ内の第１のレンジファイルを更新するステップをさらに含む方法。
【請求項６４】
請求項６１記載の方法において、
前記記憶装置の記憶領域に第２のファイルを格納する要求を受け取るステップと、
前記第２のファイルを廃棄可能とマーキングするステップであって、前記第２のファイルをマーキングするステップが前記記憶装置と関連付けられている前記ファイルシステム構造において行われるステップと、
前記第２のファイルに割り当てられている第２のクラスタチェーンを前記第２のファイルと関連付けるために、前記ＦＡＴを更新するステップと、
前記ＦＡＴの中で前記第２のファイルと関連付けられている第２のクラスタチェーンの２つ以上のクラスタの順序をスクランブルするステップと、
前記第２のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む前記ＦＡＴ内の第２のレンジファイルを作成するステップと、をさらに含み、
前記ＦＡＴおよび前記第１のレンジファイルに従って前記記憶装置の記憶領域を管理するステップは、前記ＦＡＴ、前記第１のレンジファイルおよび前記第２のレンジファイルに従って前記記憶装置の記憶領域を管理することを含む方法。
【請求項６５】
請求項６１記載の方法において、
前記第１のレンジファイルを含まない、前記第１のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む前記ＦＡＴ内の第２のレンジファイルを作成するステップをさらに含み、
前記ＦＡＴおよび前記第１のレンジファイルに従って前記記憶装置の記憶領域を管理するステップは、前記ＦＡＴ、前記第１のレンジファイルおよび前記第２のレンジファイルに従って前記記憶装置の記憶領域を管理することを含む方法。
【請求項６６】
廃棄可能ファイルと関連付けられている操作を管理する方法であって、
記憶装置が動作可能に結合されているホストにおいて、
オーナーユーザＩＤを廃棄可能ファイルと関連付けるステップであって、前記廃棄可能ファイルが前記記憶装置と関連付けられているファイルシステム構造において廃棄可能とマーキングされているファイルを含むステップと、
前記オーナーユーザＩＤと関連付けられているアプリケーションで、前記廃棄可能ファイルと関連付けられている追加のユーザＩＤのためのパーミッションのセットを定義するステップと、
前記追加のユーザＩＤと関連付けられているアプリケーションから、前記廃棄可能ファイルと関連付けられている操作を実行する要求を受け取るステップと、
前記パーミッションのセットに基づいて、前記追加のユーザＩＤと関連付けられているアプリケーションが前記操作を実行できるかを判定するステップと、
前記判定に基づいて、前記廃棄可能ファイルと関連付けられている操作を管理するステップと、
を含む方法。
【請求項６７】
請求項６６記載の方法において、
前記オーナーユーザＩＤと関連付けられているアプリケーションは、前記廃棄可能ファイルを前記記憶装置にダウンロードする方法。
【請求項６８】
請求項６６記載の方法において、
前記操作は、前記廃棄可能ファイルと関連付けられている属性を改変することを含む方法。
【請求項６９】
請求項６８記載の方法において、
前記属性は、変換ロック識別子、タイムスタンプ、消費意図ユニバーサルリソースインジケータ、および優先レベルのうちの少なくとも１つを含む方法。
【請求項７０】
請求項６６記載の方法において、
前記操作は、前記廃棄可能ファイルと関連付けられている属性を読み出すことを含む方法。
【請求項７１】
請求項７０記載の方法において、
前記属性は、変換ロック識別子、タイムスタンプ、消費意図ユニバーサルリソースインジケータ、および優先レベルのうちの少なくとも１つを含む方法。
【請求項７２】
請求項６６記載の方法において、
前記操作は、前記廃棄可能ファイルを読み出すことを含む方法。
【請求項７３】
請求項６６記載の方法において、
前記操作は、前記廃棄可能ファイルに書き込むことを含む方法。
【請求項７４】
請求項６６記載の方法において、
前記操作は、前記廃棄可能ファイルと関連付けられているプレビューデータを読み出すことを含む方法。
【請求項７５】
請求項７４記載の方法において、
前記廃棄可能ファイルは、前記プレビューデータを含む方法。
【請求項７６】
請求項７４記載の方法において、
前記廃棄可能ファイルは、前記プレビューデータとは別である方法。
【請求項７７】
請求項６６記載の方法において、
前記操作は、前記廃棄可能ファイルと関連付けられているプレビューデータを書き込むことを含む方法。
【請求項７８】
請求項６６記載の方法において、
前記追加のユーザＩＤは、多数のユーザと関連付けられる共有ユーザＩＤである方法。
【請求項７９】
請求項６６記載の方法において、
前記追加のユーザＩＤは、多数のアプリケーションと関連付けられる共有ユーザＩＤである方法。
【請求項８０】
請求項６６記載の方法において、
前記判定に基づいて、前記廃棄可能ファイルと関連付けられている操作を管理するステップは、前記追加のユーザＩＤと関連付けられているアプリケーションが前記廃棄可能ファイルと関連付けられている操作を実行することを禁じることを含む方法。
【請求項８１】
請求項６６記載の方法において、
前記判定に基づいて、前記廃棄可能ファイルと関連付けられている操作を管理するステップは、前記追加のユーザＩＤと関連付けられているアプリケーションが前記廃棄可能ファイルと関連付けられている操作を実行することを許可することを含む方法。
【請求項８２】
記憶システムであって、
通信インターフェイスと、
記憶装置と関連付けられているファイルシステムを管理するためのストレージアロケータであって、前記記憶装置に格納されている廃棄可能ファイルと関連付けられている操作を管理するためのプロセッサを含むストレージアロケータと、を備え、
前記プロセッサは、
オーナーユーザＩＤを、前記記憶装置と関連付けられているファイルシステム構造において廃棄可能とマーキングされているファイルを含む前記廃棄可能ファイルと関連付け、
前記オーナーユーザＩＤと関連付けられているアプリケーションで、前記廃棄可能ファイルと関連付けられている追加のユーザＩＤのためのパーミッションのセットを定義し、
前記追加のユーザＩＤと関連付けられているアプリケーションから、前記廃棄可能ファイルと関連付けられている操作を実行する要求を前記通信インターフェイスを介して受け取り、
前記パーミッションのセットに基づいて、前記追加のユーザＩＤと関連付けられているアプリケーションが前記操作を実行できるかを判定し、
前記判定に基づいて、前記廃棄可能ファイルと関連付けられている操作を管理するように構成される記憶システム。
【請求項８３】
請求項８２記載の記憶システムにおいて、
前記廃棄可能ファイルと関連付けられている操作を管理するために、前記プロセッサは、前記追加のユーザＩＤと関連付けられているアプリケーションが前記廃棄可能ファイルと関連付けられているプレビューデータを読み出すことを許可するように構成される記憶システム。
【請求項８４】
請求項８２記載の記憶システムにおいて、
前記追加のユーザＩＤは、多数のユーザと関連付けられる共有ユーザＩＤである記憶システム。
【請求項８５】
請求項８２記載の記憶システムにおいて、
前記追加のユーザＩＤは、多数のアプリケーションと関連付けられる共有ユーザＩＤである記憶システム。
【請求項８６】
記憶装置を管理する方法であって、
記憶装置が動作可能に結合されているホストにおいて、
前記記憶装置にプレビューデータを格納するステップと、
前記プレビューデータを、前記記憶装置と関連付けられているファイルシステム構造において廃棄可能とマーキングされているファイルを含む廃棄可能ファイルと関連付けるステップと、
アプリケーションが前記プレビューデータにアクセスすることを許可されるけれども前記廃棄可能ファイルにアクセスすることを許可されないように、前記プレビューデータおよび前記廃棄可能ファイルへのアクセスを管理するステップと、
を含む方法。
【請求項８７】
請求項８６記載の方法において、
前記廃棄可能ファイルは、前記プレビューデータを含む方法。
【請求項８８】
請求項８６記載の方法において、
前記廃棄可能ファイルは、前記プレビューデータとは別である方法。
【請求項８９】
請求項８６記載の方法において、
前記廃棄可能ファイルは映画を含み、前記プレビューデータは前記映画と関連付けられている映画予告編を含む方法。
【請求項９０】
請求項８６記載の方法において、
前記廃棄可能ファイルはテレビ番組を含み、前記プレビューデータは前記テレビ番組の一部を含む方法。
【請求項９１】
請求項８６記載の方法において、
前記廃棄可能ファイルは音楽データを含み、前記プレビューデータは前記音楽データの一部を含む方法。
【請求項９２】
請求項８６記載の方法において、
前記廃棄可能ファイルはプログラムを含み、前記プレビューデータは前記プログラムのデモ版を含む方法。
【請求項９３】
請求項８６記載の方法において、
アプリケーションが前記プレビューデータにアクセスすることを許可されるけれども前記廃棄可能ファイルにアクセスすることを許可されないように、前記プレビューデータおよび前記廃棄可能ファイルへのアクセスを管理するステップは、前記廃棄可能ファイルと関連付けられているリリース日の前の期間中にはアプリケーションが前記プレビューデータにアクセスすることを許可されるけれども前記廃棄可能ファイルにアクセスすることを許可されないように、前記プレビューデータおよび前記廃棄可能ファイルへのアクセスを管理することを含む方法。
【請求項９４】
請求項９３記載の方法において、
前記廃棄可能ファイルと関連付けられているリリース日の後の期間中にはアプリケーションが前記プレビューデータにアクセスすることを許可されると共に前記廃棄可能ファイルにアクセスすることを許可されるように、前記プレビューデータおよび前記廃棄可能ファイルへのアクセスを管理するステップをさらに含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には記憶装置に関し、特に記憶装置においてファイルを管理する方法および装置に関する。
【背景技術】
【０００２】
関連出願
本願は、２００８年１２月１６日に出願された継続中の米国特許出願第１２／３３６，０８９号（特許文献１）の一部継続出願であり、また２００９年３月１０日に出願された米国仮特許出願第６１／１５９，０３４号（特許文献２）の利益を主張し、その各々の全体が本願明細書において参照により援用されている。
【０００３】
不揮発性記憶装置の使用は、それらが携帯可能で物理的サイズが小さく記憶容量が大きいので、長年にわたって急速に拡大してきている。いろいろなデザインの記憶装置が存在する。或る記憶装置は「埋め込まれている」と見なされるが、それは、それらが協同するホスト装置からユーザによって取り外すことができないし、また取り外すように意図されてもいないということを意味する。他の記憶装置は取り外し可能であるが、それは、ユーザがそれらを１つのホスト装置から（例えば、デジタルカメラから）他のホスト装置へ移すことができるか、あるいは１つの記憶装置を他の記憶装置と取り替えることができるということを意味する。
【０００４】
記憶装置に格納されているデジタルコンテンツは、記憶装置のホストから生じたものであり得る。例えば、代表的なホストであるデジタルカメラは、画像を捉えて、それらを対応するデジタルデータに変換する。デジタルカメラは、次にそのデジタルデータを、そのデジタルカメラと協同する記憶装置に格納する。記憶装置に格納されているデジタルコンテンツは、リモートソースから生じたものでもあり、それは、例えばデータネットワーク（例えば、インターネット）または通信ネットワーク（例えば、セルラー電話ネットワーク）を介して記憶装置のホストに送られ、その後にホストによって記憶装置にダウンロードされ得る。リモートソースは、例えば、サービスプロバイダまたはコンテンツプロバイダであり得る。サービスプロバイダおよびコンテンツプロバイダは、以降、一まとめに「発行者」と称される。
【０００５】
記憶装置のユーザは、発行者からメディアコンテンツあるいは広告を要求することによってメディアコンテンツおよび広告を自発的にダウンロードすることができる。しかし、時には、発行者は、自分たちの収入を増やそうとして、ユーザの許可を求めずに、さらに時にはユーザがそのようなコンテンツが自分の記憶装置にダウンロードされたことに気づかずに、コンテンツをユーザに送る。発行者がユーザの同意を得ずにユーザに送るコンテンツは、ここでは「非請求コンテンツ」と称される。しばしば、非請求コンテンツは、発行者に料金を支払った後あるいは支払うと約束した後に、ユーザにより消費されるように意図される。
【０００６】
非請求コンテンツをユーザの記憶装置にダウンロードすることにより、発行者は、ユーザが結局その非請求コンテンツを料金と引き換えに消費し、自分たちの収入が増えることを望む。非請求コンテンツをユーザの同意を求めずに記憶装置に格納し、ユーザがそれらのコンテンツを料金と引き換えに消費することを望むという発行者は、メディア発行分野では「予測委託販売(predictive consignment)」として知られている概念である。しかし、非請求コンテンツは、記憶装置のユーザが、それが存在することを知らないで、それを消費することを望まないのに、記憶装置に格納されたままになることがある。非請求コンテンツを記憶装置に格納すれば、記憶装置上の利用可能な（すなわち、空いている）ユーザ記憶スペースが減り、それはユーザの見地からは望ましくない。他の誰か（すなわち、或る発行者）が記憶装置上の記憶スペースの一部を占拠したためにユーザ自身のコンテンツ（例えば、音楽ファイル）のための記憶装置内のスペースが少なくなっていること、あるいは非請求コンテンツを削除することによってそのように占拠されている記憶スペースを回収しなければならないかも知れないということにユーザが気づくかも知れない。
【０００７】
ユーザの記憶スペースの部分を占拠するという問題に対する１つの部分的な解決策として、発行者のウェブサイトをブロックすることなどにより、記憶装置への発行者のアクセスをブロックすることが挙げられる。この解決策は、ユーザには満足なものであるかも知れないけれども、発行者の見地からは、発行者の売り上げが減って潜在的な収入源を失うことになるから問題である。この問題に対する他の１つの部分的な解決策として、コンテンツをホストに発行し（すなわち、コンテンツファイルをこれらのホストの記憶装置に格納し）、コンテンツを、それが無意味になったら、除去することが挙げられる。換言すれば、コンテンツをもたらした発行者は、その格納されている非請求コンテンツを、コンテンツが無意味になったら、その記憶装置から除去する。非請求コンテンツは、その消費のための時間が経過したならば、あるいはユーザがそれを消費しそうもないという表示があるとき、無意味であると見なされる。
【０００８】
従って、別の言い方をすれば、非請求ファイルに伴う問題を処理する必要がある。具体的には、発行者は、自分のビジネスを行う過程で記憶装置への非請求コンテンツのダウンロードを遂行することを許されるべきであるが、そのダウンロードはユーザの体験を思いとどまらせるような決定的な影響を及ぼすべきではない。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】米国特許出願第１２／３３６，０８９号
【特許文献２】米国仮特許出願第６１／１５９，０３４号
【特許文献３】米国特許出願第１２／３３６，０８９号
【特許文献４】米国仮特許出願第６１／１５９，０３４号
【発明の概要】
【００１０】
従って、非請求ファイルを、それらを記憶装置に収容するために必要とされる記憶スペースがユーザのファイルのために必要とされない間、記憶装置に格納することができて、ユーザファイルのために最小サイズの空き記憶スペースを保証するために記憶装置から非請求ファイルを除去することができれば有益である。種々の実施形態が、そのようなファイル管理を実行するように設計され、その例がここに提供されている。
【００１１】
前述したことを処理するために記憶装置に格納されているファイルあるいは格納されるべきファイルは、記憶装置と関連付けられているファイルシステムの構造において非廃棄可能または廃棄可能とマーキングされる。各々のマーキングされたファイルは、廃棄優先レベルと関連付けられている。新しい発行者のファイル（すなわち、非請求ファイル）は、それを記憶装置に格納してもユーザファイルのために確保されているストレージ使用安全マージンが所望マージンを超えて狭まらない場合に限って、記憶装置に格納されることを許可される。一方、ユーザファイルは、それらを格納するとストレージ使用安全マージンが所望幅を超えて狭まるとしても、記憶装置に格納されることを許される。しかし、そのような場合には、ストレージ使用安全マージンの所望幅は、１つ以上の廃棄可能ファイルを記憶装置から除去することによって、回復される。廃棄可能ファイルは、その廃棄優先レベルが所定の廃棄しきい値と同等またはそれより高い（またはここで説明されるように、より低い）場合に、記憶装置から除去される。
【００１２】
或るインプリメンテーションでは、ホスト、記憶装置、あるいはその両方の組み合わせの中に存在するストレージアロケータは、記憶装置の記憶領域に廃棄可能ファイルを格納するためにプライマリファイルアロケーションテーブル（「ＦＡＴ」）および廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルを利用する。プライマリＦＡＴはクラスタチェーンと廃棄可能ファイルとの関連を記憶し、廃棄可能ＦＡＴ、データベース、または１つ以上のロケーションファイルのうちの１つはファイルの物理的位置を示す。廃棄可能ＦＡＴ、データベース、または１つ以上のロケーションファイルの中の情報は、廃棄可能ファイルに対応するプライマリＦＡＴ内のＦＡＴエントリをオーバーライドするために使用される。廃棄可能ＦＡＴ、データベース、または１つ以上のロケーションファイル内の情報でＦＡＴエントリをオーバーライドすることにより、ＦＡＴ３２ファイルシステム検査および修理ユーティリティは、廃棄可能ファイルと関連付けられているクラスタをデータフラグメント（オーファンクラスタとしても知られている）と見なすのではなくて割り当てられていると見なし、これによりユーティリティが廃棄可能ファイルを非廃棄可能ファイルに変えることを妨げる。ストレージアロケータは、プライマリＦＡＴおよび廃棄可能ＦＡＴ、データベース、または１つ以上のロケーションファイルに従って記憶装置の記憶領域を管理する。
【００１３】
廃棄可能ファイルシステムは、さらに、アプリケーションが廃棄可能ファイルと関連してどんな操作を実行できるかを、そのアプリケーションと関連付けられているユーザＩＤに基づいて制御する能力を提供する。ユーザＩＤは、廃棄可能ファイルを作成したアプリケーションまたはユーザを特定するオーナーユーザＩＤであり得る。通例、オーナーユーザＩＤと関連付けられているアプリケーションは、追加のユーザＩＤと関連付けられているどんなアプリケーションが廃棄可能ファイルにアクセスできるか、さらに、追加のユーザＩＤと関連付けられているアプリケーションが廃棄可能ファイルに関してどんなアクションを取り得るかを定義する能力を与えられる。追加のユーザＩＤを単一のアプリケーションまたは単一のユーザと関連付けることができ、あるいは追加のユーザＩＤは多数のアプリケーションまたは多数のユーザと関連付けられる共有ユーザＩＤであり得る。
【００１４】
種々の代表的な実施形態が、それらの例が限定的でないという意図を持って、添付の図面に示されている。図を簡略化することを目的として、以下で参照され、図に示されている構成要素は必ずしも一定比率で描かれていないということを理解すべきである。また、適切であると考えられる場合には、同様の、対応する、あるいは類似する構成要素を示すために参照数字が図で反復されることがある。添付図面は次のとおりである。
【図面の簡単な説明】
【００１５】
【図１】一実施形態に従う記憶システムのブロック図である。
【図２】他の実施形態に従う記憶システムのブロック図である。
【図３】一実施形態に従うストレージアロケータのブロック図である。
【図４】一実施形態に従ってファイルを管理する方法である。
【図５】一実施形態に従って記憶装置における廃棄可能ファイルの記憶を管理する方法である。
【図６】一実施形態に従ってＦＡＴ３２構造化ファイルシステムにおいて１つ以上の非請求ファイルをマーキングする方法である。
【図７】ＦＡＴ３２テーブルと関連付けられている代表的なディレクトリ領域である。
【図８】一実施形態に従うＦＡＴ３２テーブルである。
【図９】一実施形態に従うＮＴＦＳテーブルである。
【図１０】一実施形態に従うＦＡＴベースのファイルシステムの論理イメージである。
【図１１】本開示に従うファイルの記憶管理方法を示す。
【図１２ａ】代表的なプライマリＦＡＴを示す。
【図１２ｂ】代表的な廃棄可能ＦＡＴを示す。
【図１３】プライマリＦＡＴおよび廃棄可能ＦＡＴを用いて記憶装置を管理する方法のフローチャートである。
【図１４】ＦＡＴおよびデータベースを用いて記憶装置を管理する方法のフローチャートである。
【図１５】ＦＡＴおよびロケーションファイルを用いて記憶装置を管理する方法のフローチャートである。
【図１６】クラスタチェーンを含み、そのクラスタチェーンを構成する２つ以上のクラスタの順序がスクランブルされている代表的なＦＡＴを示す。
【図１７】代表的なＦＡＴおよび関連付けられているロケーションファイルを示し、そのＦＡＴはクラスタチェーンを含み、そのクラスタチェーンを構成するクラスタのうちの２つ以上の順序はスクランブルされている。
【図１８】クラスタチェーンを構成する２つ以上のクラスタの順序がスクランブルされているＦＡＴを用いて記憶装置を管理する方法のフローチャートである。
【図１９】プライマリＦＡＴおよび廃棄可能ＦＡＴを実現するファイルシステムにおいて廃棄可能ファイルがオープンであるときに、その廃棄可能ファイルの変換を阻止するために変換ロックを利用する方法のフローチャートである。
【図２０】ファイルシステムにおける代表的なビットマスクユーザＩＤを示す。
【発明を実施するための形態】
【００１６】
次の記述は代表的な実施形態の種々の詳細事項を提供する。しかし、この記述は、特許請求の範囲を限定するように意図されてはいなくて、本発明の種々の原理と、その実施方法とを説明するように意図されている。
【００１７】
非請求コンテンツおよび関連する問題を処理するために、ユーザファイルには他のファイルにまさるストレージ優先権が与えられ、その優先権を保証するためにストレージ使用安全マージンが維持される。「ユーザファイル」とは、記憶装置のユーザが進んで格納したか、あるいはそれを記憶装置に格納することを承認したファイルである。例えば、ユーザが自分の記憶装置にダウンロードする音楽ファイルはユーザファイルと考えられる。ユーザにより格納されるように要求されたかあるいは承認されているので、ユーザファイルは「請求」ファイルと考えられる。
【００１８】
「その他ファイル」は、ここでは「発行者ファイル」および「非請求ファイル」と称される。「発行者ファイル」は、ユーザがそれを要求していなくて、少なくとも暫時ではなくそれに気づいていないのに記憶装置に格納されているファイルである。ユーザは、非請求ファイルを使用することを望まないかも知れない。使用されない非請求ファイルは、ユーザの記憶装置の高価な記憶スペースを消費しがちである。従って、ここで開示される原理に従って、そのようなファイルは、それらを格納してもストレージ使用安全マージンが狭くならない場合に限って、記憶装置に格納されることを許される。ストレージ優先権は、将来のユーザのファイルのために確保される空き記憶スペース（すなわち、ストレージ使用安全マージン）を維持することによってユーザファイルに与えられる。ストレージ使用安全マージンは、必要なときあるいは望ましいときに常にユーザファイルを記憶装置に格納し得ることを保証するために、維持されなければならない。
【００１９】
何らかの理由でストレージ使用安全マージンが所望より狭くなったならば、ストレージ使用安全マージンを回復するために１つ以上の非請求ファイルが記憶装置から除去（すなわち、削除）される。ストレージ使用安全マージンを維持すれば、追加のユーザファイルが記憶装置にダウンロードされる場合に追加のユーザファイルのための記憶スペースが保証される。この目的のために、非請求ファイルは、ストレージファイルシステムの構造において「廃棄可能」とマーキングされ、必要ならば、少なくとも、ストレージ使用安全マージンを維持するために必要な空き記憶スペースを回収するために、後に除去される。
【００２０】
ユーザが種々の廃棄可能ファイルを使用する確度は廃棄可能ファイルごとに異なり得るので、各非請求ファイル（すなわち、各廃棄可能ファイル）に、そのファイルを使用する確率、そのファイルの使用と関連付けられた予想収益、そのファイルのサイズ、そのファイルのタイプ、そのファイルの位置、そのファイルの古さ（age ）などの１つ以上の基準に従って廃棄優先レベルが前もって割り当てられる。例えば、廃棄優先レベルは、収益の可能性により決定され得る。他の一例では、ユーザは普通は映画の予告編および広告を見たがらないので、映画の予告編あるいは広告は実際の映画より高い廃棄優先順位を有する。他の１つの例では、ユーザにより使用される可能性が最も高い１つ以上の廃棄可能ファイルには最低の廃棄優先レベルが割り当てられ、そのようなファイルは記憶装置から最も除去されそうもないファイルであることを意味する。換言すれば、廃棄可能ファイルの使用確率が高いほど、そのファイルに割り当てられる廃棄優先レベルのレベルは低い。１つ以上の廃棄可能ファイルが除去されても所望のストレージ使用安全マージンが充分に回復されなければ、所望のストレージ使用安全マージンが回復されるまで、さらなる廃棄可能ファイルが記憶装置から除去される。
【００２１】
簡単に言えば、ファイルシステムは、コンピュータファイルを格納し組織する方法を実行する。ファイルシステムは、データの格納、階層組織化、操作、ナビゲーション、アクセス、および検索のために実装される抽象データ型およびメタデータのセットを含む。抽象データ型およびメタデータは、それを通してコンピュータファイル（ここでは「データファイル」、あるいは簡単に「ファイル」とも称される）がアクセスされ、操作されおよび起動され得る「ディレクトリツリー」を形成する。「ディレクトリツリー」は、通例、ルートディレクトリとオプションのサブディレクトリとを含む。ディレクトリツリーは、１つ以上の「ディレクトリファイル」としてファイルシステムに格納される。ファイルシステムに含まれるメタデータおよびディレクトリファイルのセットは、ここでは「ファイルシステム構造」と称される。従って、ファイルシステムは、データファイルと、データファイルにアクセスすること、データファイルを操作すること、更新すること、削除すること、および起動することを容易にするファイルシステム構造とを含む。
【００２２】
ファイルアロケーションテーブル（「ＦＡＴ」）は、代表的なファイルシステムアーキテクチャである。ＦＡＴファイルシステムは、ＤＲ−ＤＯＳ、ＯｐｅｎＤＯＳ、ＭＳ−ＤＯＳ、Ｌｉｎｕｘ、Ｗｉｎｄｏｗｓ（登録商標）などを含む種々のオペレーティングシステムに用いられる。ＦＡＴ構造化ファイルシステムは、どの記憶領域が空いているかあるいは割り当てられているか、および各ファイルが記憶装置のどこに格納されているかに関する情報を集中させるテーブルを使用する。テーブルのサイズを制限するために、記憶スペースは、「クラスタ」と称される隣接するセクタのグループ内のファイルに割り当てられる。記憶装置が進化するにつれて、クラスタの最大数は大きくなり、クラスタを特定するために使われるビットの数は増大してきている。ＦＡＴフォーマットのバージョンは、テーブルのビットの数から導出される。ＦＡＴ１２は１２ビットを使用し、ＦＡＴ１６は１６ビットを使用し、ＦＡＴ３２は３２ビットを使用する。
【００２３】
他の１つのファイルシステムアーキテクチャはニューテクノロジーファイルシステム（（「ＮＴＦＳ」）として知られている。現在、ＮＴＦＳは、後のバージョンのＷｉｎｄｏｗｓ  ２０００、Ｗｉｎｄｏｗｓ  ＸＰ、Ｗｉｎｄｏｗｓ  Ｓｅｒｖｅｒ  ２００３、Ｗｉｎｄｏｗｓ  Ｓｅｒｖｅｒ  ２００８、およびＷｉｎｄｏｗｓ  Ｖｉｓｔａを含むＷｉｎｄｏｗｓ  ＮＴの標準的なファイルシステムである。ＦＡＴ３２およびＮＴＦＳは、記憶装置１００が備えることのできる代表的なファイルシステムである。
【００２４】
図１は、代表的な記憶装置１００を示す。記憶装置１００は種々のタイプのファイル（例えば、音楽ファイル、ビデオファイルなど）を格納するための記憶領域１１０を含み、そのうちのいくつかはユーザファイルであり、他は発行者ファイルであり得る。記憶装置１００は、データおよび制御線１３０を介して記憶領域１１０を管理するストレージコントローラ１２０も含む。ストレージコントローラ１２０は、ホストインターフェイス１５０を介してホスト装置１４０とも通信する。ホスト装置１４０は、専用ハードウェアあるいは汎用コンピューティングプラットフォームであり得る。
【００２５】
記憶領域１１０は、例えば、ＮＡＮＤフラッシュタイプのものであり得る。ストレージコントローラ１２０は、例えば「読み出し」、「書き込み」および「消去」操作、ウェアレベリング（損耗平滑化）などを制御することと、ホスト１４０との通信を制御することとにより、記憶領域１１０へ／記憶領域１１０からのデータ転送およびホスト装置１４０へ／ホスト装置１４０からのデータ転送の全てを制御する。記憶領域１１０は、例えば、ユーザファイルおよび発行者のファイルと、許可されたホスト装置だけによって使用されることが許される保護データと、ストレージコントローラ１２０によって、内部でだけ使用されるセキュリティデータとを含むことができる。ホスト（例えば、ホスト１４０）は、記憶領域１１０に直接アクセスすることはできない。すなわち、例えば、ホスト１４０が記憶装置１００からのデータを求めるかあるいは必要とするならば、ホスト１４０は、それをストレージコントローラ１２０から要求しなければならない。記憶装置１００に格納されているデータファイルへのアクセスを容易にするために、記憶装置１００はファイルシステム１６０を備えている。
【００２６】
記憶領域１１０は機能的に３つの部分、すなわちユーザ領域１７０、発行者領域１８０、および空き記憶スペース１９０に分けられている。ユーザ領域１７０は記憶領域１１０の中の、ユーザファイルが格納される記憶スペースである。発行者領域１８０は、記憶領域１１０の中の、発行者ファイルが格納される記憶スペースである。空き記憶スペース１９０は、記憶領域１１０の中の空の記憶スペースである。空き記憶スペース１９０は、ユーザファイルまたは発行者ファイルを収容するために使用され得る。ユーザファイルを空き記憶スペース１９０に格納すると、そのユーザファイルを収容している記憶スペースは、空き記憶スペース１９０から差し引かれてユーザ領域１７０に加えられる。同様に、発行者ファイルを空き記憶スペース１９０に格納すると、その発行者ファイルを収容している記憶スペースは、空き記憶スペース１９０から差し引かれて発行者領域１８０に加えられる。ユーザファイルまたは発行者ファイルが記憶領域１１０から除去（すなわち、削除）されると、その解放された記憶スペースは空き記憶スペース１９０に加えられる（戻る）。
【００２７】
空き記憶スペース１９０のサイズがそれを許すならば、記憶装置１００のユーザは、ユーザファイルをホスト１４０から記憶領域１１０にダウンロードすることができる。そのダウンロードされたユーザファイルは空き記憶スペース１９０に格納され、前に説明したように、そのファイルを収容している記憶スペースは、空き記憶スペース１９０から差し引かれてユーザ領域１７０に加えられる。前に説明したように、ユーザファイルは他の（例えば、発行者）ファイルにまさる優先権を有し、その優先権を保証するために、所望のストレージ使用安全マージンがセットされ、必要ならば、以下で記載される方法で、回復される。
【００２８】
ホスト１４０は、空き記憶スペース１９０の回復を容易にするためのストレージアロケータ１４４を含む。ストレージアロケータ１４４は、ハードウェア、ファームウェア、ソフトウェアまたはそれらの任意の組み合わせであり得る。一般的に、ストレージアロケータ１４４は、ホスト１４０に伝送されたファイル（例えば、ファイル１４２）がユーザファイルであるのか、それとも発行者ファイルであるのかを判定し、それに応じて、その伝送されたファイルをマーキングする（すなわち、非廃棄可能ファイルあるいは廃棄可能ファイルとマーキングする）。
【００２９】
ホスト１４０に伝送されたファイル（例えば、ファイル１４２）が、例えばそのファイルがユーザファイルであるので、非廃棄可能であるとストレージアロケータ１４４が判定すれば、ストレージアロケータ１４４はそのファイルを記憶領域１１０に正規の方法で格納する。前に説明したように、記憶領域１１０の中の、非廃棄可能ファイルを収容する記憶スペースは、ユーザ領域１７０に加えられるか、あるいはその一部になる。しかし、ホスト１４０に伝送されたファイルが、例えばそれが発行者ファイルであるので、廃棄可能であるとストレージアロケータ１４４が判定すれば、ストレージアロケータ１４４はそのファイルを廃棄可能とマーキングする。空き記憶スペース１９０が所望のストレージ使用安全マージンより大きければ、ストレージアロケータ１４４は、そのマーキングされた廃棄可能ファイルをも空き記憶スペース１９０に格納し、前に説明したように、空き記憶スペース１９０の中の廃棄可能ファイルを収容する記憶スペースは空き記憶スペース１９０から差し引かれて（すなわち、空き記憶スペースが減じられて）発行者領域１８０に加えられる（この追加は、廃棄可能ファイル１８２として論理的に示されている）。
【００３０】
前に説明したように、発行者ファイルがユーザにより使用される確度は発行者ファイルごとに異なり得るので、最小の使用確度を有する発行者ファイルは、記憶領域１１０からの除去についての第１の候補となる。従って、ファイルを非廃棄可能あるいは廃棄可能とマーキングするほか、ストレージアロケータ１４４は、廃棄可能ファイルが記憶領域１１０に格納される前に、それと同時に、あるいはその後に、各廃棄可能ファイルに廃棄優先レベルを割り当てる。
【００３１】
ファイルを非廃棄可能または廃棄可能とマーキングすることにより、ストレージアロケータ１４４により廃棄優先レベルを割り当て、記憶装置１００のファイルシステム１６０（またはそのイメージ）を使用することにより、ストレージアロケータ１４４は、記憶領域１１０内のユーザファイルおよび発行者ファイルの数、ならびにそれらのサイズおよび記憶領域１１０の中での論理位置も「認識する」。この情報（すなわち、ファイルの数、サイズおよび位置）を認識し、特に１つ以上のマーキングされているファイルに基づいて、ストレージアロケータ１４４は、記憶領域１１０と、記憶領域１１０における請求ファイルおよび非請求ファイルの記憶とを管理する。記憶領域１１０の管理あるいは記憶領域１１０におけるファイルの記憶の管理は、例えば、廃棄可能とマーキングされている１つ以上のファイルを選択的に除去することによるストレージ使用安全マージンの回復、廃棄可能とマーキングされている全てのファイルを除去することによる記憶領域の解放、およびより低い性能の記憶モジュールへのファイルのクラスタの再マッピングを含み得る。記憶領域１１０またはそれに格納されているファイルの管理は、記憶領域１１０またはそれに格納されているファイルの他の、追加の、あるいは代わりの態様の管理を含み得る。
【００３２】
ストレージアロケータ１４４は、各廃棄可能ファイルに割り当てられている廃棄レベルにより、将来のユーザファイルのために初めに確保されていた空き記憶スペースを回復するために（すなわち、所望のストレージ使用安全マージンを回復するために）廃棄可能ファイルが廃棄（すなわち、記憶領域１１０から削除または除去）され得るかあるいはされるべき順序をも認識する。従って、ユーザが新しいユーザファイルを記憶領域１１０に格納することを希望しているけれども、そのユーザファイルを収容する充分な空き記憶スペースがなければ（それは、ストレージ使用安全マージンが所望より狭いことを意味する）、ストレージアロケータ１４４は、所望のストレージ使用安全マージンが充分に回復されるまで、より大きな空き記憶スペースを取り戻すために（すなわち、空き記憶スペース１９０を拡張するために）廃棄可能ファイルを一つずつ反復して削除してゆくために、廃棄可能ファイルに割り当てられている廃棄優先レベルを使用する。前に説明したように、充分に回復されたストレージ使用安全マージンは、将来のユーザファイルのために充分な空き記憶スペースが確保されることを高い確率で保証する。格納されている廃棄可能ファイルをユーザがいつか使用することを望むかも知れないということが考慮され、従って廃棄可能ファイルは、そのファイルを収容している記憶スペースが新しいユーザファイルのために必要とされる場合に限って記憶装置から除去されるので、廃棄可能ファイルは、新しいユーザファイルを格納する要求を受け取ったことに応じて記憶装置１００から除去されるかあるいは削除されるに過ぎない。ストレージアロケータ１４４は、ホスト１４０に埋め込まれるかあるいは組み込まれてよく、あるいはホスト１４０の外に（破線のボックス１４４’として示されている）および記憶装置１００の外に存在してもよい。
【００３３】
ストレージアロケータ１４４は、記憶装置１００のファイルシステムあるいは記憶装置１００と関連付けられているファイルシステムの代表的なイメージを有する。ストレージアロケータ１４４は、ファイルを非廃棄可能あるいは廃棄可能とマーキングするため、かつ各廃棄可能ファイルに廃棄レベルを割り当てるために、記憶装置のファイルシステムイメージを使用する。一例では、ファイルシステムはＦＡＴを含み、この場合にはマーキングは、ファイルと関連付けられているＦＡＴエントリの未使用部分において１つ以上の未使用ビットをセットすることによって行われる。様々なファイルシステムが様々な構造を有するので、図６〜１と関連して以下で詳細に説明および記述するように、ファイルのマーキング（すなわち、非廃棄可能あるいは廃棄可能としての）および廃棄レベルの割り当ては、使用されるファイルシステム構造に適合させられる。
【００３４】
図２は、他の実施形態に従う携帯可能な記憶装置２００のブロック図である。ストレージコントローラ２２０はストレージコントローラ１２０と同様に機能し、ストレージアロケータ２４４はストレージアロケータ１４４と同様に機能する。ストレージアロケータ２４４はハードウェア、ファームウェア、ソフトウェアあるいはそれらの任意の組み合わせであり得る。ストレージアロケータ２４４は内部でストレージコントローラ２２０と協力する。ファイルを記憶領域２１０に格納する、そのファイルが廃棄可能ファイルであるか否かのインジケーションを含む、ストレージ要求をストレージコントローラ２２０がホスト２４０から受け取るたびに、ストレージコントローラ２２０は、そのストレージ要求を、さらにそのファイルが廃棄可能か否かを、ストレージアロケータ２４４に知らせる。ストレージアロケータ２４４は、その後、記憶装置２００と関連付けられているファイルシステムの構造においてそのファイルを非廃棄可能または廃棄可能とマーキングする。通例、ホスト２４０上で実行するアプリケーションは、ファイルを廃棄可能ファイルであると判定し、そのファイルが廃棄可能ファイルであることを示すフラグまたは他のインジケーションをストレージコントローラ２２０に送る。ホスト２４０上で実行するアプリケーションは、そのフラグまたは他のインジケーションを、ファイルを記憶装置に格納することを要求するためのストレージプロトコルの一部として送る。そのようなストレージプロトコルの例は、ＰＯＳＩＸファイルシステム機能あるいはｊａｖａ．ｉｏクラスツリーの使用を含む。
【００３５】
新しいファイルが廃棄可能であるとストレージアロケータ２４４が判定すると、ストレージアロケータ２４４は、その新しいファイルに、ファイルの使用確率に応じて廃棄優先レベルを割り当てる。その後、ストレージアロケータ２４４は、空き記憶スペース２９０の現在のサイズを評価し、その新しいファイルのための空間を作るために１つ以上の廃棄可能ファイルが記憶領域２１０から除去（すなわち、削除）されるべきかを決定する。１つまたは複数のファイルが記憶装置から除去されるべきであれば、ストレージアロケータ２４４は、どのファイルが除去についての現在の候補ファイルであるかを決定する。その後、ストレージアロケータ２４４は、記憶領域２１０から除去されるべき廃棄可能ファイルをストレージコントローラ２２０に知らせ、この知らせに応じて、ストレージコントローラ２２０は、ストレージアロケータ２４４により示された１つまたは複数の廃棄可能ファイルを除去する。携帯可能な記憶装置２２０の或る構成では、ストレージアロケータ２４４は機能的にストレージコントローラ２２０と記憶領域２１０との間に配置され得る。ストレージアロケータ２４４が機能的にストレージコントローラ２２０と記憶領域２１０との間に配置される構成では、ストレージアロケータ２４４または記憶領域２１０はストレージコントローラ２２０の機能のいくつかを引き受けなければならない。そのような構成では記憶領域２１０は、フラッシュＮＡＮＤプロトコルより高いレベルで通信するメモリユニットから構成される。
【００３６】
図３は、一実施形態に従うストレージアロケータ３００のブロック図である。ストレージアロケータ３００は、メモリユニット３１０、プロセッサ３２０、およびインターフェイス３３０を含む。メモリユニット３１０は、記憶装置（例えば、図２の記憶装置２００）と関連付けられているファイルシステム構造またはファイルシステム構造のイメージを収容することができる。プロセッサ３２０は、記憶装置と関連付けられているファイルシステムを管理する。インターフェイス３３０は、図１に示されているようにホストと、さらに記憶装置のストレージコントローラと、あるいは図２に示されているように記憶装置のストレージコントローラだけと協力するように適合させられ得る。
【００３７】
プロセッサ３２０は、記憶装置の記憶領域にファイルを格納する要求をインターフェイス３３０を介して受け取り、ストレージアロケータ３００と協同する記憶装置と関連付けられているファイルシステムの構造においてファイルを廃棄可能または非廃棄可能とマーキングするように構成されるかあるいは適合させられる。インターフェイス３３０が図２のストレージコントローラ２２０に機能的に付属させられているならば（従って、例えば、ファイルレベルのコマンドではなくてＳＣＳＩコマンドまたはラップされたＵＳＢ／ＭＳＣコマンドを受け取るならば）、受け取られた要求はファイルレベルより遥かに低いレベルにある。すなわち、受け取られた要求は、ホストにより適切に解釈されるとファイルに対応することになる論理ブロックアドレスにセクタを格納する要求である。ストレージコントローラ２２０がＮＶＭＨＣＩプロトコル、またはＮＦＳもしくは類似のプロトコルなどのネットワーキングファイルシステムプロトコルをサポートするならば、ストレージコントローラ２２０はファイルレベルの要求を受け取ることができる。従って、ストレージコントローラ２２０などのストレージコントローラとインターフェイス３３０などのインターフェイスとの間の通信は、ＮＶＭＨＣＩあるいはＮＶＭＨＣＩのようなインプリメンテーションに限定されない。通信インターフェイス３３０は、図３に示されているように、ストレージアロケータ３００に不可欠のものであり得る。
【００３８】
プロセッサ３２０は、マーキングされたファイルを記憶装置に送るようにさらに構成されるかあるいは適合させられ、ファイルを廃棄可能とマーキングすることは、そのファイルに廃棄優先レベルを割り当てることを含む。記憶装置により使用されるファイルシステムがＦＡＴベースであるならば、プロセッサ３２０は、マーキングされたファイルに廃棄優先レベルを、そのマーキングされたファイルに対応するＦＡＴ内のｍ個の最上（すなわち、最上位）のビット（例えば、ｍ＝４）に、対応する値をセットすることによって、割り当てる。ＦＡＴエントリ内の最上位ビットにセットされるその対応する値、あるいはＮＴＦＳディレクトリのエントリにセットされる値、もしくはそれは、ファイルの属性に関連付けられ得る。「属性」は、ＦＡＴテーブルまたはＮＴＦＳテーブルのヘッダの中の、テーブルに格納されているコンテンツのタイプに関係する情報を包含するメタデータタグあるいは何らかのデータ構造を意味する。「広告」、「プレミアムコンテンツ」、および「販売促進（無料）コンテンツ」は、ＦＡＴテーブルあるいはＮＴＦＳテーブルに格納され得るコンテンツの代表的なタイプである。廃棄レベルをセットするための代わりの基準は、例えば、最後にアクセスされたファイル、ファイルのサイズ、ファイルのタイプなどである。
【００３９】
ファイルをマーキングするために専用されるＦＡＴ３２エントリの最上位ビットの数ｍは４または４未満であり得る。なぜならば、これらのビットが使用されていないからである。さらに、より多くのビットが使用されれば、より多くの廃棄優先レベルが使用され得る。例えば、３ビット（すなわち、ｍ＝３）を使用すれば８（２3 ＝８）個の廃棄優先レベルが提供され、４ビット（すなわち、ｍ＝４）を使用すれば１６（２4 ＝１６）個の廃棄優先レベルが提供される（すなわち、廃棄優先レベル「０」を含み、これは非廃棄可能ファイルに割り当てられる）。換言すれば、プロセッサ３２０は、ｍ個の最上位ビットの値を、マーキングされるファイルが非廃棄可能であれば０にセットし、マーキングされるファイルが廃棄可能であれば１と２m −１との間の値にセットする。廃棄優先レベルは、マーキングされているファイルが記憶装置から廃棄され得るかあるいは廃棄されるべき優先順位を示す。例えば、インプリメンテーションによっては、値「１」は最低の優先順位あるいは最高の優先順位で廃棄可能であるファイルを示すことができ、値「２m −１」は最高の優先順位あるいは最低の優先順位で廃棄可能であるファイルをそれぞれ示すことができる。
【００４０】
プロセッサ３２０は、非請求ファイルが記憶装置のユーザによって使用されるであろう確度あるいは確率と関連して前に説明したように、マーキングされるファイルに、そのファイルの予想される使用に応じて、廃棄優先レベルを割り当てることができる。プロセッサ３２０は、マーキングされているファイルの廃棄優先レベルを、新しいファイルを記憶装置に格納する各要求を用いて、あるいはその各要求を受け取ったことに応答して、更新することができる。プロセッサ３２０は、所与のマーキングされているファイルの廃棄優先レベルを、記憶装置にファイルを格納する１つ以上の新しい要求とは無関係に、更新することができる。例えば、以前は高い優先順位のものであったファイルは、一定時間間隔後にその優先順位を下げられることができる。プロセッサ３２０は、記憶装置に格納されているファイルを、そのファイルが所定の廃棄しきい値と等しいかまたはそれより大きい廃棄優先レベルと関連付けられているならば、削除する。プロセッサ３２０は、ファイル書き込みまたは付加の数に基づいて、あるいは記憶装置上の空き記憶スペースの予想される使用または新しい発行者ファイルの可用性に依存して、廃棄しきい値をセット（リセット）することができる。
【００４１】
メモリユニット３１０は、記憶装置に格納されているファイルにプロセッサ３２０が割り当てている廃棄優先レベルを包含する割り当てテーブル３４０を収容することができる。さらに、割り当てテーブル３４０は、ファイルの識別子と、ファイルをファイルに割り当てられている廃棄優先レベルと関連付ける情報とを収容することができる。割り当てテーブル３４０は、さらに廃棄しきい値を収容することができる。割り当てテーブル３４０に収容されている情報により、プロセッサ３２０は所望のストレージ使用安全マージンを回復するためにどの１つまたは複数の廃棄可能ファイルを記憶装置から除去し得るかを特定することができる。
【００４２】
新しいファイルを記憶装置に格納する要求を受け取ったことに応答して、プロセッサ３２０は記憶装置上の空き記憶スペース（ｆ）のサイズを評価し、記憶装置上の空き記憶スペースの評価されたサイズが所定のサイズより大きければ新しいファイルを記憶装置に格納するが、それが所定のサイズより大きくなければ、プロセッサ３２０は記憶装置内の削除され得る１つ以上の廃棄可能ファイルを探し、そのような１つまたは複数のファイルを発見すると、プロセッサ３２０は、拡張された空き記憶スペースの総サイズがその所定のサイズに等しいかまたはそれより大きくなるように現在の空き記憶スペース（ｆ）を拡張するためにその１つまたは複数のファイルを削除する。その１つまたは複数の廃棄可能ファイルは、廃棄可能ファイルと関連付けられている廃棄優先レベルが所定の廃棄しきい値（例えば１から１５の間、例えば１５）に等しいかまたはそれより大きければ、記憶装置から削除され得る。
【００４３】
空き記憶スペースが充分に拡張された後、プロセッサ３２０は、その拡張された空き記憶スペースに新しいファイルが格納されることを許可する。「空き記憶スペースが充分に拡張される」とは、所望のストレージ使用安全マージンを狭めることなく総空き記憶スペースが新しいファイルを収容できるようになるまで、あるいは同等のことであるが、拡張された空き記憶スペースの総サイズが所定のサイズに等しくなるかまたはそれより大きくなるまで、もしくは全ての廃棄可能ファイルが除去されるまで、占拠されている記憶スペースを１つずつ解放することによって空き記憶スペースを広げることを意味する。
【００４４】
プロセッサ３２０は、標準的ないつでも買えるシステムオンチップ（「ＳｏＣ」）デバイス、またはシステムインパッケージ（「ＳｉＰ」）デバイス、あるいは実行時に本願明細書に記載されているステップ、操作および評価を行う専用ソフトウェアを有する汎用処理装置であり得る。代わりに、プロセッサ３２０は、本願明細書に記載されているステップ、操作および評価をハードウェアを用いることによって実行する特定用途向け集積回路（「ＡＳＩＣ」）であり得る。
【００４５】
図４は、一実施形態に従う廃棄可能ファイルを格納する方法である。図４は、図１と関連して記述される。ステップ４１０で、ホスト１４０は、ファイル１４２を記憶装置１００に格納する要求を受け取る。ステップ４２０でストレージアロケータ１４４はファイルを「廃棄可能」または「非廃棄可能」とマーキングし、空き記憶スペース１９０が充分に大きければ、ステップ４３０で、そのマーキングされたファイルを記憶装置１００のストレージコントローラ１２０に送る（すなわち、記憶領域１１０に格納するため）。ファイルは、廃棄優先レベルがファイルに割り当てられるという意味でもマーキングされる。ステップ４４０で、ストレージアロケータ１４４は、そのマーキングされたファイルに基づいて、さらに、任意的に、既にマーキングされている１つ以上のファイルに基づいて、記憶領域１１０（ストレージコントローラ１２０との通信を通して）あるいは記憶領域１１０に格納されているファイルを管理する。
【００４６】
図５は、一実施形態に従う記憶装置における廃棄可能ファイルの記憶を管理する方法である。図５は、図１と関連して記述される。新しいファイルは、記憶装置１００に格納される候補である。記憶装置１００のファイルシステム１６０の現在のイメージを認識して、ストレージアロケータ１４４は、ステップ５１０で、現在のサイズがｆである空き記憶スペース１９０がその新しいファイル（すなわち、格納されそうな候補であるファイル）を収容できるかを調べるために空き記憶スペース１９０の現在のサイズ「ｆ」を評価する。一般的に、ストレージアロケータ１４４が新しいファイルを処理する方法は、その新しいファイルがユーザファイルであるのか発行者ファイルであるのかによる。従って、ストレージアロケータ１４４は、まず、新しいファイルがユーザファイルであるのか発行者ファイルであるのかを判定する。
【００４７】
新しいファイルがユーザファイルである場合
ステップ５２０で、ストレージアロケータ１４４は、空き記憶スペース１９０が新しいユーザファイルを収容できるかを調べる。空き記憶スペース１９０が新しいユーザファイルを収容できるならば（ステップ５２０で「Ｙ」として示されている）、ストレージアロケータ１４４は、ステップ５６０で、その新しいユーザファイルを格納することにより所望のストレージ使用安全マージンが狭められるか否かに関わらず新しいユーザファイルを空き記憶スペース１９０に格納する。ストレージアロケータ１４４が新しいユーザファイルを空き記憶スペース１９０に格納した後に所望のストレージ使用安全マージンがより狭くなるとしても（すなわち、所望のストレージ使用安全マージンと比べて）、ストレージアロケータ１４４は、その新しいユーザファイルの格納に関してそれ以上の処置をとらない。
【００４８】
しかし、ストレージアロケータ１４４が新しいユーザファイルを空き記憶スペース１９０に格納した後に所望のストレージ使用安全マージンがより狭くなるならば、ステップ５５０は、所望のストレージ使用安全マージンを維持するために、どの格納されている廃棄可能ファイルが最初に削除されるべきか、どの廃棄可能ファイルが２番目に削除されるべきかなどをストレージアロケータ１４４が判定する追加のステップを含む。ストレージアロケータ１４４は、格納されている廃棄可能ファイルにストレージアロケータ１４４が割り当てた廃棄レベルに基づいて、どの廃棄可能ファイルが最初に削除されるべきか、どれが２番目に削除されるべきかなどを判定する。
【００４９】
空き記憶スペース１９０が新しいユーザファイルを収容できないとストレージアロケータ１４４がステップ５２０で判定すると（ステップ５２０で「Ｎ」として示されている）ストレージアロケータ１４４は、ステップ５３０で、空き記憶スペース１９０と、廃棄可能ファイルにより占拠されている記憶スペースとが結合されるとその新しいユーザファイルを格納するために充分であるかを判定する。その結合された記憶スペースが不十分であるならば（ステップ５３０で「Ｎ」として示されている）、どれだけ多くの廃棄可能ファイルが削除されても、その新しいユーザファイルは、そのサイズがより大きいために「非ユーザ」記憶領域に格納され得ないということを意味する。その結合された記憶スペースが充分であるならば（ステップ５３０で「Ｙ」として示されている）、ストレージアロケータ１４４は、その新しいユーザファイルのために充分な記憶スペースを解放するために、格納されている廃棄可能ファイルのうちのどの廃棄可能ファイルが削除され得るかをステップ５４０で調べる。前に説明したように、ストレージアロケータ１４４は記憶装置のファイルシステムにおいてファイルを非廃棄可能または廃棄可能とマーキングするので、ストレージアロケータ１４４は、記憶装置１００のファイルシステムを用いることによってこれらの廃棄可能ファイルを探す。さらに、マーキングされているファイルにストレージアロケータ１４４により割り当てられる廃棄レベルも、各廃棄レベルが対応するマーキングされたファイルと関連付けられるように、記憶装置のファイルシステムに埋め込まれる。
【００５０】
最初に廃棄されるべき廃棄可能ファイル（「ＤＦ」）（このファイルは、以降「ＤＦ１」と称される）を発見すると、ストレージアロケータ１４４は、その記憶スペース（この記憶スペースは、以降「ＳＰ１」と称される）を記憶スペース１９０に加えるためあるいは戻すために、ファイルＤＦ１を削除する。
【００５１】
その後、ステップ５５０でストレージアロケータ１４４は、拡張された空き記憶スペース１９０（すなわち、空き記憶スペース１９０＋最後に戻された記憶スペース、すなわちｆ＋ＳＰ１）がその新しいユーザファイルを収容できるかを調べる。拡張された空き記憶スペース１９０（すなわち、ｆ＋ＳＰ１）が依然としてその新しいユーザファイルを収容できなければ（ステップ５５０で「Ｎ」として示されている）、ストレージアロケータ１４４は、さらなる記憶スペースを空き記憶スペース１９０に戻すために（すなわち、削除されるべき次の廃棄可能ファイルを見つけて削除することにより）ステップ５５０を反復的に繰り返す（反復は５５５で示されている）。
【００５２】
２番目に高い廃棄優先順位を有する次の廃棄可能ファイルを見つけると（次の廃棄可能ファイルは、以降「ＤＦ２」と称される）、ストレージアロケータ１４４は、さらなる記憶スペース（このさらなる記憶スペースは、以降「ＳＰ２」と称される）を解放して空き記憶スペース１９０に加えるためにファイルＤＦ２を削除する。その後、ステップ５５０で、ストレージアロケータ１４４は、拡張された空き記憶スペース１９０（すなわち、空き記憶スペース１９０＋２つの最後に解放された記憶スペース、すなわちｆ＋ＳＰ１＋ＳＰ２）がその新しいファイルを収容できるかを再び調べる。その拡張された空き記憶スペース１９０（すなわち、ｆ＋ＳＰ１＋ＳＰ２）が依然としてその新しいファイルを収容できなければ（ステップ５４０で「Ｎ」として示されている）、ストレージアロケータ１４４は、削除されるべき次の廃棄可能ファイルを見つけるためにステップ５４０をもう一度繰り返す。ストレージアロケータ１４４は、累積された空き記憶スペース１９０がその新しいユーザファイルを収容できるようになるまで（ステップ５５０で「Ｙ」として示されている）ステップ５４０および５５０を反復する。その後、ステップ５６０で、ストレージアロケータ１４４は、その新しいユーザファイルを記憶領域１１０に格納する。
【００５３】
前述したように、ストレージアロケータ１４４が新しいユーザファイルを空き記憶スペース１９０に格納した後に実際のストレージ使用安全マージンが所望のストレージ使用安全マージンより狭くなるならば、ステップ５６０は、所望のストレージ使用安全マージンを回復するためにどの格納されている廃棄可能ファイルが最初に削除されるべきか、どの廃棄可能ファイルが２番目に削除されるべきかなどをストレージアロケータ１４４が判定する追加のステップを含むことができる。
【００５４】
新しいファイルが発行者ファイルである場合
新しいファイルが発行者ファイルであるならば、ストレージアロケータ１４４は、空き記憶スペース１９０が所望のストレージ使用安全マージンを狭めることなく新しい発行者ファイルを収容できる場合に限って、その新しい発行者ファイルを（ステップ５６０で）記憶領域１１０に格納する。すなわち、新しい発行者ファイルを格納すれば所望のストレージ使用安全マージンを狭める結果となるのであれば、ストレージアロケータ１４４はその新しい発行者ファイルを記憶領域１１０に格納しないと決定することができる。そのような場合、ストレージアロケータ１４４は、そのファイルに関しての処置を控え、その新しい発行者ファイルのための記憶スペースを解放するために記憶装置からファイルを削除しなくてもよい。代わりに、ストレージアロケータ１４４は、より低い廃棄優先順位を有する廃棄可能ファイルのための記憶スペースを解放するために１つ以上のより高い優先順位の廃棄可能ファイルをステップ５４０で削除することができる。前に述べたように、ファイルは記憶装置１００のファイルシステムにおいてマーキングされ、廃棄レベルは記憶装置１００のファイルシステムに埋め込まれ、ファイルがマーキングされ、廃棄レベルがファイルシステムに埋め込まれる方法は、その使用されるファイルシステムに依存し、あるいはその使用されるファイルシステムに適合させられ得る。
【００５５】
図６は、一実施形態に従うＦＡＴ３２構造化ファイルシステムにおいて非請求ファイルをマーキングする方法である。ＦＡＴ３２構造化ファイルシステムはクラスタを使用する。ＦＡＴ３２構造化ファイルシステムと関連して前に記載したように、ＦＡＴ３２クラスタを特定するために使用されるビットの数は３２である。図６は、図１と関連して記述される。
【００５６】
ステップ６１０で、ＦＡＴ３２の各クラスタの３２ビットのうちのｍ個の最上位ビット（ここで、ｍ≦４）が、状況に応じてファイルを非廃棄可能または廃棄可能とマーキングするために、および各廃棄可能ファイルに対応する廃棄レベルを保持するために割り当てられ、あるいは専用される。ファイルへの廃棄レベルの割り当ては、対応する値を、そのマーキングされたファイルに対応する割り当てられたｍビットにセットすることにより行われる。
【００５７】
ステップ６２０で、ストレージアロケータ１４４は、記憶装置１００のユーザがその非請求ファイルを使用する確度のレベルを評価する。そのファイルを使用する確度の評価は、委託ファイルの技術分野の当業者に知られている種々の方法で実行され得る。例えば、そのファイルを使用する確度の評価は、その記憶装置を使用する人の位置をモニタすること、および／またはモニタされるユーザの以前の経験および好みに基づくことができる。そのファイルを使用する確度の評価は、例えば、そのＦＡＴテーブルまたはＮＴＦＳテーブル内に格納されているコンテンツのタイプ（例えば、「広告コンテンツ」、「プレミアムコンテンツ」、「販売促進（無料）コンテンツ」など）に基づいてもよい。ストレージアロケータ１４４は、そのファイルが使用される確度を評価するために代わりのあるいは追加の基準を使用することができる。例えば、最後にアクセスされたファイル、ファイルのサイズ、ファイルのタイプなどであり得るか、あるいはそれらと関連付けられ得る、ファイルの属性または特徴を使用することができる。
【００５８】
ユーザがその非請求ファイルを使用する確度のレベルをストレージアロケータ１４４が評価した後、ストレージアロケータ１４４は、ステップ６３０で、非請求ファイルの使用の評価された確度レベルに対応する廃棄優先レベルを割り当てる。その非請求ファイルが記憶装置１００のユーザにより使用される確度が高ければ高いほど、廃棄レベルは低くなる。
【００５９】
ｍが４ビットに等しければ、これは、廃棄スケールは１（すなわち、０００１）から１５（すなわち、１１１１）までの１５個の廃棄レベルを提供する。すなわち、廃棄レベル０は全ての非廃棄可能ファイルに割り当てられ、廃棄レベル１は最低の廃棄優先順位を有する廃棄可能ファイルに割り当てられ、廃棄レベル１５は最高の廃棄優先順位を有する廃棄可能ファイルに割り当てられる。ストレージアロケータ１４４が非請求ファイルに対応する廃棄レベルを割り当てた後、ストレージアロケータ１４４は、ステップ６４０で、その非請求ファイルと関連付けられているクラスタの４個の最上位ビットに１と１５との間の対応する値をセットする。その非請求ファイルが２つ以上のクラスタと関連付けられているならば、各クラスタの４個の最上位ビットが同じ値にセットされる。
【００６０】
ステップ６５０で、その非請求ファイルは評価される必要のある最後のファイルであるか否かが調べられる。その非請求ファイルが評価される必要のある最後のファイルでなければ（ステップ６５０で「Ｎ」として示されている）、前に記載した方法で他のファイルが評価される。その非請求ファイルが評価される必要のある最後のファイルであるならば（ステップ６５０で「Ｙ」として示されている）、その非請求ファイルは、その値がステップ６４０でセットされた各々のためのｍ個のビットと共に記憶装置に送られる。
【００６１】
図７は、ＦＡＴ３２テーブルと関連付けられている代表的なディレクトリテーブル７００である。ディレクトリテーブル７００は説明のために使用される部分的テーブルであるので、テーブル７００はＦＡＴディレクトリエントリの全てのフィールドを示してはいない。ディレクトリ領域７００は、ファイル名、ファイルのサイズ、および関連する記憶スペースのどこから各ファイルが始まるかなど、関連するファイルシステムに格納されているファイルの細目を収容する。ファイルの細目は、次のフィールドに収容されている。フィールド７１０は、関連するファイルシステムに格納されているファイルのディスクオペレーティングシステム（「ＤＯＳ」）ファイル名を収容し、フィールド７２０はファイルの拡張子を収容し、フィールド７３０はファイルの種々の属性を収容し、フィールド７４０はファイルの第１のクラスタ番号（「ＦＣＮ」）の上位１６ビットワードを収容し、フィールド７５０はファイルの第１のクラスタ番号（「ＦＣＮ」）の下位部分を収容し、フィールド７６０はファイルのサイズを収容する。各ＦＣＮ番号は、ファイルが見出され得る第１の論理クラスタを示す。
【００６２】
ディレクトリ領域７００の第１のエントリは、「ＲＥＡＬＦＩＬＥ」（７７０のところに示されている）と称される代表的なファイルについての情報を収容する。ＲＥＡＬＦＩＬＥ７７０はファイル拡張子「ＤＡＴ」を有し、そのＦＣＮは「００００  ０００２」であり（７５５のところに示されている）、そのサイズは「００００  ２４Ｅ４」である。テーブル７００内の数字は十六進値で示されている。標準の一部として、属性値「００」（７８０のところに示されている）および「２０」（図７には示されていない）は「レギュラー」ファイルを指し、属性値「０２」は、ファイルシステムにおいて隠されているファイルを指す。ファイル名「＼ｘＥ５Ｃｏｎｓｉｇｎ」は、削除されたファイルを示し、ここで「＼ｘＥ５」は、そのファイル名の第１のバイトの値が１６進法のＥ５であることを意味する。例を挙げると、ＦＣＮ番号００００  ０００２（７５５のところに示されている）は、ファイルＲＥＡＬＦＩＬＥの第１のクラスタを示す。
【００６３】
図８は、一実施形態に従う代表的な部分的ＦＡＴ３２テーブル８００である。ＦＡＴ３２テーブル８００はダブルワード（「ＤＷＯＲＤ」）アレイとして示され、値は十六進値である。参照番号８１０はＦＡＴ３２テーブル８００を収容しているデバイスのタイプを示し、ここで「Ｆ８」はハードディスクを指す。ＦＡＴ３２テーブル８００は、クラスタ＃１（８２０のところに示されている）、クラスタ＃２（８２５のところに示されている）・・・クラスタ＃２３（８３０のところに示されている）と称される２３個のクラスタを含む。図８は、図７と関連して記述される。ＦＡＴ３２テーブル８００内のクラスタはファイルの第１のクラスタであることができ、あるいはファイルの次のリンクされているクラスタを指すことができ、あるいはファイルの終わり（「ＥＯＦ」）インジケーションであることができる。
【００６４】
ディレクトリ領域７００を再び参照すると、ファイルＲＥＡＬＦＩＬＥ（７７０のところに示されている）の第１のＦＣＮは「００００  ０００２」（７５５のところに示されている）であり、これは図８のテーブル８００のクラスタ＃２を指す。図８に示されているように、クラスタ＃２の値（すなわち、値「００００  ０００３」）は（８４０のところに示されている）クラスタ＃３を指し、これは次のファイルのクラスタである。同様に、クラスタ＃３の値（すなわち、「００００  ０００４」）はクラスタ＃４を指し、これは次のファイルのクラスタである。クラスタ＃４は値「０ＦＦＦ  ＦＦＦＦ」を有し（「Ｆ」は、十進値「１５」を表す十六進数字である）、ここで「ＦＦＦ  ＦＦＦＦ」（８５０のところに示されている）はファイルのＥＯＦインジケーションを示し、ゼロ値（８６０のところに示されている）は廃棄レベル０を示す。従って、ファイルＲＥＡＬＦＩＬＥは３つのクラスタ（すなわち、クラスタ＃２、クラスタ＃３、およびクラスタ＃４）と関連付けられている。
【００６５】
前に説明したように、廃棄レベル０は非廃棄可能ファイルに割り当てられる。特定のファイルの各クラスタの最上位十六進数字は、そのファイルに割り当てられた同じ廃棄優先レベルにセットされるということに留意すべきである。例えば、ファイルＲＥＡＬＦＩＬＥには廃棄レベル「０」が割り当てられ、従って、クラスタ＃２、＃３、および＃４の最上位十六進数字の各々はその値（すなわち、値「０」、これらの「０」値にはアンダーラインが付けられている）を有する。他の１つの例では、そのＦＣＮが（図７に示されているように）「００００  ０００５」であるファイル「Ｅ５Ｃｏｎｓｉｇｎ」には廃棄優先レベル「１」が割り当てられている。従って、そのファイルに属するクラスタ＃５〜１２の各々の最上位十六進数字は値「１」を有する（例えば、８７０のところに示されているように）。換言すれば、本願明細書における開示では特定の廃棄可能ファイルと関連付けられているクラスタの最上位十六進数字、あるいは同等に最上位４ビットは、その特定のファイルに割り当てられている廃棄優先レベルに対応する同じ値にセットされる。前に説明したように、廃棄優先レベルを示すために使われる最上位ビットの数ｍは４と異なっていてもよい（すなわち、ｍ≦４）。
【００６６】
図９は、一実施形態に従う代表的な部分的ＮＴＦＳテーブル９００である。ＮＴＦＳテーブル９００は、ファイル名、ファイルのサイズなどのファイルの細目を収容する。ＮＴＦＳテーブル９００は、「通常の」データフローに従って変化するファイルのための「レギュラー」データ（例えば、データ９２０）を収容するデータフィールド９１０を含む。本願明細書における開示では、ＮＴＦＳテーブル９００は、各々の評価されたファイルについての廃棄情報（例えば、廃棄情報９３０）を収容するための「廃棄情報」フィールド９１５をも含む。廃棄情報フィールド９１５は、廃棄優先レベル以外の情報も含むことができる。例えば、廃棄情報フィールド９１５は、そのファイルを供給したサーバと、その後にファイルが廃棄されなければならない満期時とに関する情報を含むことができる。ＦＡＴベースのファイルシステムとは違って、ＮＴＦＳベースのファイルシステムでは廃棄可能ファイルに割り当てられる廃棄値は、１セットのビットにより規定される最大数に限定されない。これは、廃棄値の範囲が自由に選択され得ることを意味する。例えば、廃棄値は１から２５までの範囲にわたり得る。ＮＴＦＳは、代表的な非ＦＡＴファイルシステムである。一般的に、対応する廃棄値は、マーキングされたファイルに対応する非ＦＡＴベースのファイルシステムのエントリ内のデータフィールドにセットされ得る。
【００６７】
図１０は、一実施形態に従う記憶装置のファイルシステム１０００の論理配置である。ストレージアロケータ（例えば、図１のストレージアロケータ１４４）は、自分と協同する記憶装置のファイルシステム１０００またはファイルシステム１０００のイメージを保持し得るか、あるいはストレージアロケータはファイルシステム１０００へのアクセスを持ち得る。
【００６８】
ファイルシステム１０００は、ブートセクション１０１０と、ファイルシステム１０００と関連付けられているＦＡＴ１０２０と、ディレクトリテーブル１０３０と、ファイル領域１０４０と、廃棄可能ファイル領域１０５０とを含む。ＦＡＴ１０２０は、廃棄可能ファイルの廃棄優先レベルを包含する廃棄可能ファイル割り当て領域１０２５を含む。ディレクトリテーブル１０３０は、記憶装置に格納されている全てのファイル（すなわち、廃棄可能ファイルおよび／または非廃棄可能ファイル）にアクセスするためのアクセス情報を含む。ファイル領域１０４０は、非廃棄可能ファイルを包含する。インデックスおよびデータベース領域１０４５は、廃棄可能ファイルのためのインデックスと、さらに、廃棄可能ファイルに関連付けられているメタデータとを収容する。インデックスおよびデータベース領域１０４５に収容されているインデックスおよびメタデータは、廃棄レベルを計算するために使用されるけれども、実際の廃棄プロセス中には必要とされない。廃棄可能ファイル領域１０５０は、廃棄可能ファイルを収容する。
【００６９】
図１１は、本願明細書における開示に従うファイル管理方法を示す。図１１は、図１と関連して記述される。時刻Ｔ０において２つのユーザファイル（すなわち、ファイル「Ｆ１」および「Ｆ２」）が初めに記憶領域１１０に格納されていると仮定される。ファイル「Ｆ１」および「Ｆ２」はユーザファイルなので、それらはユーザ領域１７０に格納され、ストレージアロケータ１４４によってそれらに割り当てられている廃棄レベルはゼロである。記憶領域１１０の総記憶容量はＴ（１１１０のところに示されている）であり、ファイルＦ１およびＦ２は記憶装置１００に格納されているので、残りの空き記憶スペース１９０のサイズ（図１を参照）はｆ（１１２０のところに示されている）である。発行者が３つの非請求ファイルを記憶領域１１０に格納することを望むと仮定される。前に記述したように、発行者のその３つの非請求ファイルを記憶領域１１０に格納すると、将来のユーザのファイルのために確保されている所望のストレージ使用安全マージン（１１３０のところに示されている）が狭くなるかどうかを判定するために、ストレージアロケータ１４４は記憶装置１００内の空き記憶スペース１９０のサイズ（すなわち、１１２０のところのｆ）を評価する。発行者の３つの非請求ファイルを格納するとストレージ使用安全マージン１１３０（すなわち、所望のストレージ使用安全マージン）が狭くなるならば、ストレージアロケータ１４４はそれらのファイルを格納するのを差し控える。
【００７０】
この例では、ストレージアロケータ１４４は、ストレージ使用安全マージン１１３０を減少させることなくその発行者の３つの非請求ファイルが記憶領域１１０に格納され得ると判定する。従って、時点Ｔ１で、ストレージアロケータ１４４は、ストレージコントローラ１２０がその発行者の３つの非請求ファイルを記憶領域１１０に格納することを許可する。その３つの発行者の非請求ファイルは「Ｐ１」、「Ｐ２」、および「Ｐ３」と称されている。ストレージアロケータ１４４は、さらにファイルＰ１、Ｐ２、およびＰ３が記憶装置１００のユーザにより使用される確率を判定し、対応する廃棄レベルをそれらのファイルの各々に割り当てる。ストレージアロケータ１４４は、その後、ファイルに割り当てられた廃棄レベルを、図８に示されているようにＦＡＴテーブルあるいは図９に示されているようにＮＴＦＳテーブルに格納する。
【００７１】
時点Ｔ２で、記憶装置１００のユーザは、もう２つのファイル（すなわち、ファイル「Ｆ３」および「Ｆ４」）を記憶領域１１０に格納することを望む。ストレージアロケータ１４４は、その追加のファイル（すなわち、ファイルＦ３およびＦ４）を格納するのに充分な記憶スペースが記憶領域１１０にあるかを判定するために記憶装置１００内の空き記憶スペース１９０のサイズ（すなわち、１１２０のところのｆ）を再び評価する。この例では、ストレージアロケータ１４４は、現在空いている記憶スペースはファイルＦ３およびＦ４を収容できると判定する。従って、時点Ｔ２で、ストレージアロケータ１４４は、ストレージコントローラ１２０がファイルＦ３およびＦ４を記憶領域１１０に格納することを許可する。
【００７２】
ファイルＦ３およびＦ４はユーザファイルであるため、ユーザがファイルＦ３およびＦ４を、使用するとしても、何回使用するかとは関係なく、ユーザファイルは発行者ファイルより高い記憶優先順位を有するので、ファイルＦ３およびＦ４が記憶装置１００のユーザにより使用される確率は重要ではない。従って、ストレージアロケータ１４４は、ファイルＦ３およびＦ４に廃棄レベル「０」を割り当て、その割り当てられた廃棄レベルを、図８に示されているようにＦＡＴテーブルあるいは図９に示されているようにＮＴＦＳテーブルに格納する。
【００７３】
時点Ｔ３で、記憶装置１００のユーザは、記憶領域１１０に他の１つのファイル（すなわち、ファイル「Ｆ５」）を格納することを望む。ストレージアロケータ１４４は、その追加のファイル（すなわち、ファイルＦ５）を格納するのに充分な記憶スペースが記憶領域１１０にあるかを判定するために記憶装置１００内の空き記憶スペース１９０のサイズ（すなわち、１１２０のところのｆ）を再び評価する。
【００７４】
この例では、ストレージアロケータ１４４は、現在空いている記憶スペースがファイルＦ５を収容できると判定する。従って、時点Ｔ３で、ストレージアロケータ１４４はストレージコントローラ１２０がファイルＦ５を記憶領域１１０に格納することを許可する。図１１に示されているように、ユーザファイルＦ５を格納するとストレージ使用安全マージンが狭まる。すなわち、ファイルＦ１〜Ｆ５およびＰ１〜Ｐ３が記憶領域１１０に格納された後に残っている記憶領域１１０内の空き記憶スペースｆは、ストレージ使用安全マージン１１３０より小さい。従って、ストレージアロケータ１４４は、発行者のファイル（すなわち、Ｐ１、Ｐ２、およびＰ３）のうちの１つを除去することによって、ストレージ使用安全マージンを復活させるかあるいは回復する。前に説明したように、ユーザファイルが最大の記憶優先順位を有するので、ストレージ使用安全マージンは、１つ以上の発行者ファイルを除去（すなわち、削除）することによって復活させられるかあるいは回復される。
【００７５】
前に記述したように、どの１つの発行者ファイルまたは複数の発行者ファイルが記憶領域１１０から除去されるべきかの決定は、ストレージアロケータ１４４が各々の格納されている廃棄可能ファイルに割り当てた廃棄優先レベルに基づいてストレージアロケータ１４４によって行われる。
【００７６】
再び図１１を参照して、格納されている発行者ファイルＰ１〜Ｐ３のうちで発行者ファイルＰ３に最高の廃棄優先レベル（例えば、１３）が割り当てられたと仮定される。従って、時点Ｔ４でファイルＰ３が記憶領域１１０から除去され、これにより空き記憶スペース１９０を大きくする。時点Ｔ４における空き記憶スペース１９０のサイズ（すなわち、１１２０のところのｆ）はストレージ使用安全マージン１１３０より大きいので、発行者ファイルをそれ以上除去する必要はない。
【００７７】
記憶装置１００のユーザは、１つ以上のユーザファイルを除去することを望むかもしれない。時点Ｔ５でユーザは自分のファイルのうちの２つ（すなわち、ファイルＦ４およびＦ５）を除去し、これにより空き記憶スペース１９０をさらに大きくした。ここで述べられたように、空き記憶スペースの再獲得あるいはストレージ使用安全マージンの回復は必要な数の廃棄可能ファイルを除去することによって行われるので、ファイルＦ４およびＦ５の除去は空き記憶スペース１９０のサイズまたはストレージ使用安全マージンとは無関係である。発行者が他の１つの非請求ファイルを記憶領域１１０に格納することを望むと想定される。前に記述したように、ストレージアロケータ１４４は、その発行者の非請求ファイルを記憶領域１１０に格納するとストレージ使用安全マージン１１３０が狭まらないかを判定するために空き記憶スペース１９０のサイズ（すなわち、１１２０のところのｆ）を評価する。その発行者の新しい非請求ファイルを格納するとストレージ使用安全マージン１１３０が狭まるのであれば、ストレージアロケータ１４４は、そのファイルを格納するのを差し控える。
【００７８】
この例では、ストレージアロケータ１４４は、発行者の新しい非請求ファイル（すなわち、ファイル「Ｐ４」）はストレージ使用安全マージン１１３０を減少させることなく記憶領域１１０に格納され得ると判定する。従って、時点Ｔ６でストレージアロケータ１４４はストレージコントローラ１２０が発行者のファイルＰ４を記憶領域１１０に格納するのを許可する。ストレージアロケータ１４４は、ファイルＰ４が記憶装置１００のユーザによって使用される確率も判定し、対応する廃棄レベルをこのファイルに割り当てる。ストレージアロケータ１４４は、その後、ファイルＰ４に割り当てられた廃棄レベルを、図８に示されているようにＦＡＴテーブルあるいは図９に示されているようにＮＴＦＳテーブルに格納する。新しいファイルが記憶領域１１０に加えられなければならないたびにストレージアロケータ１４４が空き記憶スペース１９０の現在のサイズを評価して、どの１つまたは複数の発行者ファイル（あるとすれば）が記憶領域１１０から除去されなければならないかを判定する間、新しい発行者のファイルおよび新しいユーザファイルを格納すると共に格納されているファイルを除去するプロセスが続行され得る。
【００７９】
廃棄可能ファイルへの廃棄レベルの割り当ては、ユーザの経験または選択、ユーザの全地球測位システム（「ＧＰＳ」）位置、および／または他の基準に基づくことができる。例えば、記憶装置のユーザが（以前のユーザの経験に基づいて）或るタイプの音楽を好みそうに思われるならば、ストレージアロケータは発行者のファイルに、そのファイルがユーザの気に入っているタイプのうちの１つの音楽である音楽を含んでいるならば、割合に低い廃棄優先レベル（例えば、１から１５までのスケールの中の３）を割り当てることができる。しかし、発行者の音楽がユーザに嫌われるならば（すなわち、以前のユーザの経験に基づいて）、ストレージアロケータは、その関連する発行者のファイルにより高い廃棄優先レベル（例えば、１から１５までのスケールの中の１２）を割り当てることができる。廃棄可能ファイルに廃棄レベルを割り当てるために使用される基準は、そのファイルの予想される使用法、そのファイルの使用と関連付けられた予想される収益、そのファイルのタイプ、そのファイルのサイズ、そのファイルの記憶装置の中での位置、そのファイルの古さ、およびここで明示される他の基準またはパラメータを含むことができる。他の基準を、単独でもあるいはここで言及された基準のうちのいずれかと組み合わされても、同様に使用することができ、廃棄レベルの割り当てを１つ以上の基準を用いて行うことができる。さらに、異なる廃棄可能ファイルに廃棄レベルを割り当てるために異なる基準が使用され得る。
【００８０】
他の１つの例において、発行者がユーザに位置依存型の広告（すなわち、特定の位置の中で提供される製品またはサービスに関連する広告）を送ることを望むならば、ストレージアロケータは、その発行者の広告に対して、ユーザの変化する位置に応じて変化する廃棄優先レベルを割り当てることができる。すなわち、ユーザが特定の位置から遠ざかるほど廃棄レベルは高くなるであろうが、それは、その特定の位置から離れるほど、ユーザはその特定の位置で提供されるその製品またはサービスを消費することに関心を持たなくなると想定され得るからである。
【００８１】
前に記載したように、廃棄可能ファイルのためのクラスタチェーンは、ＦＡＴ３２エントリと関連付けられたファイルを廃棄可能ファイルと特定するフラグと共にＦＡＴに記録される。通例、フラグは、各ＦＡＴ３２エントリの４つの最上位ビットに存在する。クラスタチェーンは、廃棄可能ファイルに割り当てられ得るけれども、それらと関連付けられた非廃棄可能ファイルをもたないので、ｃｈｋｄｓｋまたはｆｓｃｋ．ｖｆａｔなどのユーティリティが廃棄可能ファイルを、「リアル」ファイルとしても知られる非廃棄可能ファイルに転換させ、これによりファイルシステム１６０のセキュリティを低下させるということが起こり得る。さらに、何らかのＦＡＴリカバリユーティリティがＦＡＴ３２エントリ内の廃棄可能ファイルフラグをリセットする危険がある。ＦＡＴ３２ファイルシステムの検査および修理ユーティリティは、しばしば、ありふれたエラーを修正するためにファイルシステムをステップスルーしてルールを適用する。一般的に、これらのユーティリティは、ディレクトリテーブル内の第１のクラスタ番号（ＦＣＮ）コラム内に対応するエントリを持っていないＦＡＴ内のクラスタチェーンを探すことができる。ユーティリティは、ディレクトリあるいはファイルエントリを全く持っていないＦＡＴ内のクラスタ割当てを不明のデータフラグメント（オーファンクラスタとしても知られている）として扱い、ユーティリティは、これらのオーファンクラスタを削除するか、あるいは対応するファイルエントリをディレクトリテーブル内に作成することができる。本願明細書に記載されている廃棄可能ファイルシステムは、そうでなければオーファンクラスタと見なされるであろうものを使用することができるので、ユーティリティは、間違って廃棄可能ファイルを非廃棄可能ファイルに変えたり、あるいは廃棄可能ファイルを完全に除去したりすることがある。
【００８２】
これらの問題を処理するために、或るインプリメンテーションでは、ストレージアロケータ１４４は廃棄可能ファイルをプライマリＦＡＴ内のクラスタチェーンと関連付けることができ、そのクラスタチェーンは廃棄可能ファイルの物理的位置を隠し、ストレージアロケータ１４４はファイルの物理的位置を廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルに格納する。通例、その廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルはプライマリＦＡＴには不可視であり、或るインプリメンテーションでは、ホストオペレーティングシステムがその廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルにアクセスすることを阻止する、その廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルと関連付けられた属性がイネーブルされ得る。
【００８３】
前に記したように、ＦＡＴ３２内の各エントリは３２ビットであるけれども、下位２８ビットだけが使用される。通例、上位４ビットは使われずに残され、ゼロにセットされる。（ＦＡＴ３２の準拠インプリメンテーションは、上位４ビットを、たとえ割り当てられているクラスタにおいてセットされていても、無視し、新しいＦＡＴエントリを書き込む時には上位４ビットをゼロにセットするように要求される。）廃棄可能ファイルは、そのファイルと関連付けられている各クラスタチェーンのＦＡＴエントリの上位４ビットの中のフラグによって非廃棄可能ファイルから区別される。標準的ＦＡＴ３２ドライバは、廃棄可能ファイルを割り当てられているスペースと見なし、それらの上に書き込まない。しかし、ストレージアロケータ１４４は、記憶装置１１０において空きスペース割当てを維持するために、図５に関して前に記述したものなどの操作を定期的に実行することができ、廃棄可能ファイルに割り当てられているスペースを回復することができる。
【００８４】
プライマリＦＡＴと、廃棄可能ＦＡＴ、データベース、および１つ以上のロケーションファイルのうちの少なくとも１つとを利用することにより、プライマリＦＡＴは拡張され得る。拡張されたプライマリＦＡＴがファイル割り当てテーブルルックアップ論理のブランチと関連して使用されるときには、ＦＡＴエントリの上位４ビットが非ゼロであるならば、廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルの中の、廃棄可能ファイルの物理的位置を表す情報がプライマリＦＡＴのＦＡＴエントリの代わりに使用される。廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルの中の情報がプライマリＦＡＴのＦＡＴエントリの中の値をオーバーライドするので、ｃｈｋｄｓｋおよびｆｓｃｋ．ｖｆａｔなどのユーティリティは廃棄可能ファイルを非廃棄可能ファイルに変えないが、それは、ユーティリティが廃棄可能ファイルのクラスタを、廃棄可能ＦＡＴ、データベースあるいは１つ以上のロケーションファイルの中のディレクトリまたはファイルエントリと関連付けられていると見なすからである。さらに、ＦＡＴリカバリユーティリティは、ファイルが廃棄可能ファイルであることを示すＦＡＴ３２エントリ内のフラグをリセットしないが、それは、ｃｈｋｄｓｋおよびｆｓｃｋ．ｖｆａｔなどのユーティリティが、廃棄可能ファイルと関連付けられているクラスタを、空きスペースと見なすのではなくて、廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルの中のディレクトリまたはファイルエントリと関連付けられていると見なすからである。
【００８５】
ファイルシステム１６０が、廃棄可能ファイルとマーキングされているファイルを格納するためにプライマリＦＡＴ１２００と廃棄可能ＦＡＴ１２０１とを利用するとき、ストレージアロケータ１４４は、廃棄可能ファイルに割り当てられているクラスタチェーン１２０２をファイルと関連付けるために図１２ａに示されているようにプライマリＦＡＴ１２００を更新する。一般的に、クラスタチェーン１２０２は、クラスタチェーン１２０２と関連付けられている廃棄可能ファイルと同じか、あるいはそれより大きいサイズであり得る。或るインプリメンテーションでは、クラスタチェーン１２０２は、プライマリＦＡＴにおいて廃棄可能ファイルの物理的位置をマスクする。通例、図７および８に関して前に記述したように、エントリ１２０４から始まるクラスタチェーン内の各クラスタは、エントリ１２０６に示されている１ＦＦＦ  ＦＦＦＦなどの値がクラスタチェーン１２０２の終わりを示すまで、クラスタチェーン１２０２の次の連続クラスタを指す。しかし、他のインプリメンテーションでは、クラスタチェーンの各クラスタは、そのクラスタがクラスタチェーンの次の連続クラスタを指すのではなくて個別に割り当てられたクラスタであることを示す１ＦＦＦ  ＦＦＦＦなどの値を持つことができる。
【００８６】
図１２ｂに示されているように、クラスタチェーン１２０２の第１のエントリ１２０４は、廃棄可能ＦＡＴ１２０１内の対応するエントリ１２０８を指す。図７および８に関して前に記述したように、各ファイルについて、廃棄可能ＦＡＴ１２０１の中のクラスタチェーン１２０２内の各クラスタは、エントリ１２１０において示されている１ＦＦＦ  ＦＦＦＦなどの値がファイルのＥＯＦを示すまでファイルの次の順のクラスタを指す。
【００８７】
１つのクラスタチェーン１２０２は２つ以上のファイルと関連付けられ得るということを理解すべきである。例えば、図１２ｂに示されているように、クラスタチェーン１２０２は、第１のファイル１２１２のためのクラスタ＃６（エレメント１２０８）からクラスタ＃９（エレメント１２１０）までのクラスタの第１のセットを含み、第２のファイル１２１４のためのクラスタ＃１０からクラスタ＃１１までのクラスタの第２のセットを含む。
【００８８】
さらに、プライマリＦＡＴ１２００と対応する廃棄可能ＦＡＴ１２０１とは２つ以上のクラスタチェーンを含み得るということを理解すべきである。例えば、図１２ａおよび１２ｂに示されているように、プライマリＦＡＴは、クラスタ＃６からクラスタ＃１１までのクラスタチェーン１２０２を含むことができ、クラスタ＃２０からクラスタ＃２２までの第２のクラスタチェーン１２１６を含むことができる。
【００８９】
他のインプリメンテーションでは、プライマリＦＡＴ１２００と廃棄可能ＦＡＴ１２０１とを使用するのではなくて、ファイルシステムは、前述したように、１つ以上のファイルをクラスタチェーンと関連付けるためにプライマリＦＡＴ１２００を利用することができ、クラスタチェーンと関連付けられた１つ以上の廃棄可能ファイルの物理的位置を格納するために廃棄可能ＦＡＴの代わりにデータベースまたは１つ以上の別々のロケーションファイルを利用することができる。データベースまたはロケーションファイルは、ファイルシステムの非廃棄可能領域に格納されるテキストファイルまたはバイナリファイルであり得る。
【００９０】
図１３は、プライマリＦＡＴと廃棄可能ＦＡＴとを用いて記憶装置を管理する方法である。図１３は、図１と関連して記述される。ステップ１３１０で、ホスト１４０は、ファイル１４２を記憶装置１００に格納する要求を受け取る。或るインプリメンテーションでは、ストレージアロケータ１４４は、ファイル１４２を記憶装置１００に格納する要求を、ファイルと関連付けられている１つ以上の書き込み要求に基づいて導出する。
【００９１】
ステップ１３２０で、ストレージアロケータ１４４は、前に記述したように記憶装置１００と関連付けられているファイルシステム構造においてファイルを「廃棄可能」または「非廃棄可能」とマーキングする。ステップ１３２０で、ファイルは、廃棄優先レベルがファイルに割り当てられるという意味でもマーキングされる。
【００９２】
ステップ１３３０で、ファイルが廃棄可能ファイルであるとき、ストレージアロケータ１４４は、ファイルに割り当てられるクラスタチェーンをファイルと関連付けるためにプライマリＦＡＴを更新する。ステップ１３４０で、ストレージアロケータ１４４は、記憶装置１００におけるファイルの物理的位置を表すように廃棄可能ＦＡＴを更新する。ステップ１３５０で、ストレージアロケータ１４４は、（ストレージコントローラ１２０との通信を通して）記憶装置１００の記憶領域１１０を管理するか、あるいは記憶領域１１０に格納されているファイルをマーキングされているファイルに基づいて廃棄可能ＦＡＴに従って管理する。記憶領域の管理は、図５に関連して前に記述したものと同様である。
【００９３】
図１４は、ＦＡＴとデータベースとを用いて記憶装置を管理する方法である。図１４は、図１と関連して記述される。ステップ１４１０で、ホスト１４０は、ファイル１４２を記憶装置１００に格納する要求を受け取る。ステップ１４２０で、ストレージアロケータ１４４は、前に記述したように記憶装置１００と関連付けられているファイルシステム構造においてファイルを「廃棄可能」または「非廃棄可能」とマーキングする。ステップ１４２０で、ファイルは、廃棄優先レベルがファイルに割り当てられるという意味でもマーキングされる。
【００９４】
ステップ１４３０で、ファイルが廃棄可能ファイルであるとき、ストレージアロケータ１４４は、ファイルに割り当てられるクラスタチェーンをファイルと関連付けるためにＦＡＴを更新する。ステップ１４４０で、ストレージアロケータ１４４は、記憶装置１００におけるファイルの物理的位置を表すようにデータベースを更新する。ステップ１４５０で、ストレージアロケータ１４４は、（ストレージコントローラ１２０との通信を通して）記憶装置１００の記憶領域１１０を管理するか、あるいは記憶領域１１０に格納されているファイルをＦＡＴおよびデータベースに基づいて管理する。
【００９５】
図１５は、ＦＡＴとロケーションファイルとを用いて記憶装置を管理する方法である。図１５は、図１と関連して記述される。ステップ１５１０で、ホスト１４０は、ファイル１４２を記憶装置１００に格納する要求を受け取る。ステップ１５２０で、ストレージアロケータ１４４は、前に記述したように記憶装置１００と関連付けられているファイルシステム構造においてファイルを「廃棄可能」または「非廃棄可能」とマーキングする。ステップ１５２０で、ファイルは、廃棄優先レベルがファイルに割り当てられるという意味でもマーキングされる。
【００９６】
ステップ１５３０で、ファイルが廃棄可能ファイルであるとき、ストレージアロケータ１４４は、ファイルに割り当てられるクラスタチェーンをファイルと関連付けるためにＦＡＴを更新する。ステップ１５４０で、ストレージアロケータ１４４は、記憶装置１００におけるファイルの物理的位置を表すようにロケーションファイルを更新する。ステップ１５５０で、ストレージアロケータ１４４は、（ストレージコントローラ１２０との通信を通して）記憶装置１００の記憶領域１１０を管理するか、あるいは記憶領域１１０に格納されているファイルをＦＡＴおよびロケーションファイルに基づいて管理する。
【００９７】
さらに他のインプリメンテーションでは、セキュリティを強化し、ｄｏｓｆｓｃｋ（ｆｓｃｋ．ｖｆａｔとしても知られている）またはｃｈｋｄｓｋなどのファイルシステム完全性ユーティリティによってファイルシステムが破壊されたり損なわれたりしないように、ストレージアロケータ１４４は、廃棄可能ファイルの物理的位置を記憶している廃棄可能ＦＡＴ、データベース、あるいは１つ以上のロケーションファイルを読まなくてはクラスタチェーンが再構築され得ないことを保証するために、廃棄可能ファイル領域においてクラスタをクラスタチェーンにシーケンシャルに割り当てない。さらに、ｄｏｓｆｓｃｋなどのユーティリティが、廃棄可能ファイルを非廃棄可能ファイルに変えたり、ファイルが廃棄可能であることを示すファイルの上位ビットに存するフラグをリセットしたりしないように、クラスタチェーンのスクランブルされているクラスタのうちの１つ以上と関連付けられるレンジファイルがＦＡＴにおいて生成される。或るインプリメンテーションでは、ホストオペレーティングシステムがレンジファイルにアクセスすることを阻止するために、レンジファイルと関連付けられている隠し属性、システム属性、ディレクトリ属性、あるいはボリューム属性などの属性がイネーブルされ得る。
【００９８】
図１６は、クラスタチェーンを含んでいて、そのクラスタチェーンを構成する２つ以上のクラスタの順序がスクランブルされているＦＡＴを表すチャートである。図１６に示されているように、エントリ１６０２から始まるクラスタチェーンを構成するクラスタは連続していない。例えば、エントリ１６０２から始まるクラスタチェーンの順序はクラスタ＃１３、クラスタ＃９、クラスタ＃７、クラスタ＃１８、およびクラスタ＃２１である。このＦＡＴでは、図７および８に関して前に記述したように、各クラスタの値は、クラスタチェーン内の次のクラスタを指す。
【００９９】
１つ以上のファイルと関連付けられているクラスタチェーンを構成するクラスタの順序がスクランブルされていることに加えて、ファイルと関連付けられているクラスタチェーンの１つ以上のクラスタを含む１つ以上のレンジファイルがＦＡＴにおいて作成され得る。或るインプリメンテーションでは、各レンジファイルは、クラスタチェーンの一部であるクラスタの範囲の中の全てのクラスタを表すことができる。レンジファイルと、クラスタチェーンを構成するクラスタとが関連しているために、ｃｈｋｄｓｋまたはｆｓｃｋ．ｖｆａｔなどのユーティリティは廃棄可能ファイルを非廃棄可能ファイルに変えず、ＦＡＴリカバリユーティリティは、ファイルが廃棄可能ファイルであるというＦＡＴ３２エントリインジケーション内のフラグをリセットしない。
【０１００】
図１７は、ＦＡＴ内に作成された１つ以上のレンジファイルを示すチャートであり、その各々は、エントリ１６０２から始まるクラスタチェーンのうちの少なくとも１つのクラスタを記憶する。例えば、第１のレンジファイル１６０４は、エントリ１６０２から始まるクラスタチェーンからのクラスタ＃７およびクラスタ＃９を記憶し、第２のレンジファイル１６０６は、エントリ１６０２から始まるクラスタチェーンからのクラスタ＃１３、クラスタ＃１８、およびクラスタ＃２１を記憶する。
【０１０１】
レンジファイルは、２つ以上のクラスタチェーンからのクラスタを記憶することができる。例えば、エントリ１６０２から始まるクラスタチェーンからの上でリストされたクラスタのほかに、第１のレンジファイル１６０４は、エントリ１６０８から始まるクラスタチェーンからのクラスタ＃５およびクラスタ＃１０を記憶することができる。同様に、エントリ１６０２から始まるクラスタチェーンからの上でリストされたクラスタのほかに、第２のレンジファイル１６０６は、エントリ１６０８から始まるクラスタチェーンからのクラスタ＃１６、クラスタ＃１７、およびクラスタ＃２２を記憶することができる。
【０１０２】
図１８は、クラスタチェーンを構成する２つ以上のクラスタの順序がスクランブルされているＦＡＴを用いて記憶装置を管理する方法である。図１８は、図１と関連して記述される。ステップ１８１０で、ホスト１４０は、ファイル１４２を記憶装置１００に格納する要求を受け取る。ステップ１８２０で、ストレージアロケータ１４４は、前に記述したように記憶装置１００と関連付けられているファイルシステム構造においてファイルを「廃棄可能」または「非廃棄可能」とマーキングする。ステップ１８２０で、ファイルは、廃棄優先レベルがファイルに割り当てられるという意味でもマーキングされる。
【０１０３】
ステップ１８３０で、ファイルが廃棄可能ファイルであるとき、ストレージアロケータ１４４は、ファイルに割り当てられているクラスタチェーンをファイルと関連付けるためにＦＡＴを更新する。ステップ１８４０で、ファイルと関連付けられているクラスタチェーンの２つ以上のクラスタの順序は、記憶装置１００内のメモリの量、クラスタチェーンの総サイズ、クラスタチェーンの２つの連続するクラスタの間のクラスタの数、ならびに／または消去ブロックサイズ、割り当てられたブロック内の各論理アドレスの物理的ブロックアドレス、および／または物理的ブロックアドレスと関連付けられている各ページのためのウェアレベリングデータを考慮できるフラッシュメモリ管理アルゴリズムなどの要素に基づいてＦＡＴの中でスクランブルされる。或るインプリメンテーションでは、クラスタチェーンの２つ以上のクラスタの順序は、擬似乱数発生器またはエントロピック乱数発生器を用いてスクランブルされ、前もって割り当てられていない各クラスタについて１つの範囲内のオフセットを提供する。他のインプリメンテーションでは、クラスタチェーンの２つ以上のクラスタの順序は、ホストシステム１４０および／または記憶装置１００からの非決定論的な値を考慮に入れる単方向ハッシュ関数を用いてスクランブルされる。
【０１０４】
ステップ１８５０で、第１のファイルと関連付けられているクラスタチェーンの少なくとも１つのクラスタを含む第１のレンジファイルがＦＡＴにおいて作成される。ステップ１８６０で、ストレージアロケータ１４４は、（ストレージコントローラ１２０との通信を通して）記憶装置１００の記憶領域１１０を管理するか、あるいはＦＡＴおよびレンジファイルに基づいて記憶領域１１０に格納されているファイルを管理する。
【０１０５】
さらに他のインプリメンテーションでは、廃棄可能ファイルがオープンである間にその廃棄可能ファイルが非廃棄可能ファイルに変換されないことを保証するために変換ロックを実行することができる。例えば、廃棄可能ファイルが記憶装置１００にダウンロードされつつある期間中、あるいは廃棄可能ファイルと関連付けられている映画、歌、または番組と関連付けられているリリース日より前に廃棄可能ファイルが記憶装置１００にダウンロードされる時などの、廃棄可能ファイルと関連付けられているデータが公衆にリリースされる前の期間中、廃棄可能ファイルはオープンであり得る。一般的に、変換ロックは、変換ロックがセットされているときには廃棄可能ファイルが非廃棄可能ファイルに変換され得ないように働く。
【０１０６】
図１９は、廃棄可能ファイルの変換を、プライマリＦＡＴおよび廃棄可能ＦＡＴを実装するファイルシステムにおいて廃棄可能ファイルがオープンであるときに阻止するために変換ロックを利用する方法である。図１９は、図１と関連して記述される。ステップ１９１０で、ストレージアロケータ１４４は、廃棄可能ファイルを非廃棄可能ファイルに変換する要求を受け取る。ステップ１９２０で、ストレージアロケータ１４４は、廃棄可能ファイルと関連付けられている変換ロック識別子の値を識別する。ステップ１９３０で、ストレージアロケータ１４４は、変換ロック識別子の値に基づいて、廃棄可能ファイルが非廃棄可能ファイルに変換され得るかを判定する。通例、ストレージアロケータ１４４は、変換ロック識別子の値が廃棄可能ファイルがオープンであることを示しているときには廃棄可能ファイルは変換され得ないと判定し、ストレージアロケータ１４４は、変換ロック識別子の値が廃棄可能ファイルがオープンでないことを示しているときには廃棄可能ファイルは変換され得ると判定する。
【０１０７】
ステップ１９３０で廃棄可能ファイルが非廃棄可能ファイルに変換され得ないとストレージアロケータ１４４が判定すれば、ストレージアロケータ１４４はステップ１９４０で廃棄可能ファイルを非廃棄可能ファイルとマーキングすることを禁じる。しかし、廃棄可能ファイルが非廃棄可能ファイルに変換され得るとストレージアロケータ１４４がステップ１９３０で判定すれば、ストレージアロケータ１４４は先へ進み、ステップ１９５０で、ファイルを、記憶装置１００と関連付けられているファイルシステム構造において非廃棄可能ファイルとマーキングし、ステップ１９６０でファイルの物理的位置を表すようにプライマリＦＡＴを更新し、ステップ１９７０でファイルの物理的位置を除去するために廃棄可能ＦＡＴを更新する。
【０１０８】
前に記述した廃棄可能ＦＡＴの代わりにプライマリＦＡＴと共にデータベースまたはロケーションファイルが使用されるときに類似の方法が変換ロックで実行されるということを理解すべきである。
【０１０９】
或るインプリメンテーションでは、アプリケーションは、アプリケーションと関連付けられている識別子に基づいて、廃棄可能ファイルの非廃棄可能ファイルへの変換あるいは変換ロック識別子の値のチェックなどの操作を実行することを許され得る。通例、廃棄可能ファイルを作成するかあるいはダウンロードするアプリケーションは、ユーザ識別子（ＩＤ）を廃棄可能ファイルと関連付けることができる。ユーザＩＤは、その廃棄可能ファイルを作成したアプリケーションまたはユーザを特定するオーナーユーザＩＤであり得る。或るインプリメンテーションでは、オーナーユーザＩＤは４バイト値である。
【０１１０】
ファイルシステム１６０は、他のユーザまたはアプリケーションと関連付けられたどんな追加のユーザＩＤが廃棄可能ファイルにアクセスできるかを定義すると共に、追加のユーザＩＤが廃棄可能ファイルに関してどんなアクションを取り得るかを定義する能力をオーナーユーザＩＤに提供する。廃棄可能ファイルの使用法により、追加のユーザＩＤは単一のアプリケーションまたは単一のユーザと関連付けられることができ、あるいはその追加のユーザＩＤは多数のアプリケーションまたは多数のユーザと関連付けられる共有ユーザＩＤであることができるということを理解すべきである。
【０１１１】
或るインプリメンテーションでは、オーナーユーザＩＤは、追加のユーザＩＤと関連付けられているアプリケーションが、廃棄可能ファイルと関連付けられているプレビューデータにアクセスすることを許可することができる。プレビューデータは廃棄可能ファイルの一部であり得るけれども、他のインプリメンテーションでプレビューデータは、廃棄可能ファイルとは別個のものであるけれども廃棄可能ファイルと関連付けられる。或る代表的なインプリメンテーションでは、廃棄可能ファイルは映画であって、プレビューデータは映画と関連付けられた映画予告編を含むことができ、廃棄可能ファイルはテレビ番組であって、プレビューデータはテレビ番組の一部を含むことができ、廃棄可能ファイルは音楽データであって、プレビューデータは音楽データの一部を含むことができ、あるいは廃棄可能ファイルはソフトウェアプログラムであって、プレビューデータはソフトウェアプログラムのデモ版を含むことができる。他の代表的なインプリメンテーションでは、プレビューデータは、廃棄可能ファイルと関連付けられているリリース日の前に廃棄可能ファイルにはアクセスされ得ないけれども廃棄可能ファイルと関連付けられているプレビューデータはアクセスされ、そのリリース日の後は廃棄可能ファイルおよびプレビューデータの両方がアクセスされ得るように、利用され得る。他の１つの例では、オーナーユーザＩＤは、追加のユーザＩＤと関連付けられているアプリケーションが廃棄可能ファイルに、廃棄可能ファイルと関連付けられているユーザＩＤに基づいて、書き込むことを許可することができる。
【０１１２】
或るインプリメンテーションでは、ファイルシステムは、追加のユーザＩＤと関連付けられているアプリケーションが廃棄可能ファイルに関してどんな操作を実行できるかをオーナーユーザＩＤが定義するためのパーミッションビットマスクを提供することができる。代表的な使用シナリオのためのパーミッションビットマスクの一例が図２０に示されている。しかし、オーナーユーザＩＤが、図２０に示されているパーミッションをオーバーライドし、追加のユーザＩＤに任意のパーミッションを割り当てることができるということを理解すべきである。
【０１１３】
図２０に示されているパーミッションを参照すると、プロパティ書き込みパーミッションビット２００４がセットされているアプリケーションは、変換ロックをイネーブルあるいはディスエーブルする、タイムスタンプをセットするかあるいは消費意図ユニバーサルリソースインジケータ（「ＵＲＩ」）を書き込むなどの属性変更をすることができ、プロパティ読み出しパーミッションビット２００２がセットされているアプリケーションは変換ロック、タイムスタンプ、あるいは消費意図ＵＲＩなどの属性を読み出すことができる。優先順位パーミッションビット２００６がセットされているアプリケーションは、廃棄可能ファイルの優先レベルを変更することができる。プレビュー読み出しパーミッションビット２００８がセットされているアプリケーションは、廃棄可能ファイルと関連付けられているプレビューデータを読み出すことができ、プレビュー書き込みパーミッションビット２０１０がセットされているアプリケーションは、廃棄可能ファイルと関連付けられているプレビューデータを書き込むことができる。読み出しパーミッションビット２０１２がセットされているアプリケーションは廃棄可能ファイルを読み出すことができ、書き込みパーミッションビット２０１４がセットされているアプリケーションは廃棄可能ファイルに書き込むことができる。通例、廃棄可能ファイルと関連付けられているオーナーユーザＩＤと関連付けられているアプリケーションだけがこれらのパーミッションを有する。変換パーミッションビット２０１６がセットされているアプリケーションは、廃棄可能ファイルを非廃棄可能ファイルに変換することができる。
【０１１４】
ファイルをマーキングして、関連付けられているファイルシステムにおいてそれらに廃棄レベルを割り当てる、ここで開示された方法は多くの有益な応用例を持つことができて、その１つは、ユーザファイルのために充分な記憶スペースを保証するためにストレージ使用安全マージンを回復することであるということに留意すべきである。例えば、ファイルに割り当てられた廃棄レベルは、より性能の低いフラッシュモジュールにファイルクラスタを再マッピングするためあるいは要求があり次第クラスタをクリアするために使用され得る。
【０１１５】
冠詞は、ここでは、文脈に応じて冠詞の文法上の目的語の１つまたは２つ以上（すなわち、少なくとも１つ）に言及するために使用される。例を挙げると、文脈に応じて、「エレメント」は、１つのエレメントまたは２つ以上のエレメントを意味することができる。「・・・を含む」という用語は、ここでは、「・・・を含むが、・・・に限定されない」という句を意味するように用いられ、この句と交換可能に用いられている。「または」や「および」という用語は、文脈が明らかに別のことを示していない限り、「および／または」という用語を意味するように用いられ、これらの用語と交換可能に用いられている。「・・・など（のような）」という用語は、ここでは、「・・・など（のような）であるが、・・・に限定されない」という句を意味するように用いられ、この句と交換可能に用いられている。
【０１１６】
発明の代表的な実施形態をこのように記述して、開示された実施形態の改変形が発明の範囲内にあるということを当業者であれば理解できるはずである。従って、代替の実施形態は、より多くのモジュール、より少数のモジュールおよび／または機能的に同等のモジュールを含むことができる。本願明細書における開示は、ＳＤ駆動フラッシュメモリカード、フラッシュ記憶装置、非フラッシュ記憶装置、ユニバーサルシリアルバス（「ＵＳＢ」）インターフェイスを備える「ディスクオンキー」装置、ＵＳＢフラッシュドライブ（「ＵＦＤ」）、マルチメディアカード（「ＭＭＣ」）、セキュアデジタル（「ＳＤ」）、ミニＳＤ（ｍｉｎｉＳＤ）、およびマイクロＳＤ（ｍｉｃｒｏＳＤ）などの種々のタイプの大容量記憶装置に関連している。従って、添付の特許請求の範囲は、本願明細書における開示によって限定されない。
【図１】
2012512460.tif 000003
【図２】
2012512460.tif 000004
【図３】
2012512460.tif 000005
【図４】
2012512460.tif 000006
【図５】
2012512460.tif 000007
【図６】
2012512460.tif 000008
【図７】
2012512460.tif 000009
【図８】
2012512460.tif 000010
【図９】
2012512460.tif 000011
【図１０】
2012512460.tif 000012
【図１１】
2012512460.tif 000013
【図１２ａ】
2012512460.tif 000014
【図１２ｂ】
2012512460.tif 000015
【図１３】
2012512460.tif 000016
【図１４】
2012512460.tif 000017
【図１５】
2012512460.tif 000018
【図１６】
2012512460.tif 000019
【図１７】
2012512460.tif 000020
【図１８】
2012512460.tif 000021
【図１９】
2012512460.tif 000022
【図２０】
2012512460.tif 000023
【手続補正書】
【提出日】平成23年10月4日(2011.10.4)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図１９
【補正方法】変更
【補正の内容】
【図１９】
2012512460.tif 000024
【国際調査報告】
2012512460.tif 000025
2012512460.tif 000026
2012512460.tif 000027
2012512460.tif 000028
2012512460.tif 000029