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