(57)【要約】  ホストシステムデータファイルは、メモリの中間論理アドレスまたは仮想アドレス空間のいずれをも用いず、各ファイルの固有の識別子とファイル内のデータのオフセットとを用いて大規模な消去ブロックフラッシュメモリシステムに直接に書き込まれる。ファイルがメモリに記憶されたディレクトリ情報は、ホストによるよりはむしろ、メモリシステムコントローラによってメモリシステム内で維持される。ホストとメモリシステムとの間のファイルベースのインターフェイスによって、メモリシステムコントローラは、効率を増大してメモリ内のデータ記憶ブロックを利用することができる
2008530708.tif 000002
【特許請求の範囲】
【請求項１】
任意の新たなデータが書き込まれる前に消去され、少なくとも５１２バイトのデータを個々に含む複数のデータ単位を記憶する容量を個々に有するブロックに編成されたメモリセルを有する再プログラム可能な不揮発性大容量記憶システムを動作する方法であって、
固有のファイル識別子および前記識別されたファイル内のデータのオフセットを含む論理アドレスを有するデータを受信するステップと、
前記受信したデータをメモリセルの前記ブロック内の物理アドレスにプログラムするステップと、
前記ファイルを構成する可変量のデータのグループを識別し、前記グループ内のデータの連続的な論理オフセットアドレスおよび連続的な物理アドレスの双方を個々に有する前記個々のファイルの前記プログラムされたデータの複数のレコードを維持するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記複数のレコードを維持するステップは、前記グループ内の前記データの少なくとも開始論理オフセットアドレスおよび開始物理アドレスを前記個々のレコード内に供給するステップを含む方法。
【請求項３】
請求項２記載の方法において、
前記複数のレコードを維持するステップは、前記グループ内の前記データの長さを前記個々のレコード内に供給するステップをさらに含む方法。
【請求項４】
請求項３記載の方法において、
前記個々のファイルの前記レコードをグループ化することによって編成された前記複数のレコードのファイルマップを維持するステップをさらに含む方法。
【請求項５】
請求項１記載の方法において、
前記データをプログラムするステップは、消去済みブロックの第１の物理アドレスから開始し、必要に応じて物理順に前記消去済みブロックを経て、前記ファイルの前記受信したデータのすべてが１回のプログラム動作でプログラムされるまで他の消去済みブロックに継続することによって、新たなファイルの前記受信したデータをプログラムするステップを含む方法。
【請求項６】
請求項１記載の方法において、
前記データをプログラムするステップは、前記メモリシステム内に以前に記憶された既存ファイルの受信した追加のデータを、前記既存のファイルデータが前記ブロック内で終了した直後、ブロックの物理アドレスから開始し、必要に応じて物理順に前記ブロックの消去済み部分を経て、前記ファイルの前記追加のデータのすべてが１回のプログラム動作でプログラムされるまで他の消去済みブロックに継続することによってプログラムするステップを含む方法。
【請求項７】
請求項６記載の方法において、
前記追加のデータをプログラムするステップは、前記以前に記憶されたファイル内へ挿入するデータをプログラムするステップを含む方法。
【請求項８】
請求項７記載の方法において、
複数のレコードを維持するステップは、前記既存ファイルの前記既存のデータグループのレコードを変更し、少なくとも１つの他のデータグループの少なくとも１つの追加レコードを追加するステップを含む方法。
【請求項９】
請求項６記載の方法において、
前記追加のデータをプログラムするステップは、前記以前に記憶されたファイルの前記データの一部を更新し、これによって、前記以前に記憶されたファイルの前記データの一部が古くなるデータをプログラムするステップを含む方法。
【請求項１０】
請求項９記載の方法において、
複数のレコードを維持するステップは、前記既存ファイルの前記既存のデータグループのレコードを変更し、少なくとも１つの他のデータグループの少なくとも１つの追加レコードを追加するステップを含む方法。
【請求項１１】
請求項１記載の方法において、
前記個々の単位の少なくとも幾つかは、複数の前記データのグループを含む方法。
【請求項１２】
請求項１記載の方法において、
前記大容量記憶システムは、少なくとも２５６メガバイトのデータを記憶するのに充分な多数のメモリセルを含む方法。
【請求項１３】
請求項１記載の方法において、
前記個々のデータ単位は、少なくとも１，０２４バイトを含む方法。
【請求項１４】
請求項１記載の方法において、
少なくとも８つのデータ単位は、前記大容量記憶システムの個々のブロック内に書き込まれる方法。
【請求項１５】
ホストシステムと、同時に消去できるメモリセルのブロックに編成されたメモリセルを有する再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法であって、個々のブロックは、新たなデータが前記ブロック内に書き込まれる前に消去され、
前記ホストシステムは、前記ホストシステムが生成する個々のファイルのデータを固有のファイル識別子と前記個々のファイル内の所定サイズのデータ単位のオフセットとによって識別し、
前記大容量記憶システムは、前記個々のファイルのデータを、１つのファイル内に不連続のデータオフセットを有するデータのグループの間、または、前記ファイルオフセットアドレス単位の分解能に等しい物理アドレス分解能で指定された２つの異なるファイルのデータのグループ間に境界を有するメモリセルの少なくとも１つの予め消去されたブロック内に記憶する方法。
【請求項１６】
請求項１５記載の方法において、
前記所定サイズのデータ単位は、１バイトのデータを含む方法。
【請求項１７】
請求項１５記載の方法において、
前記データのグループは、前記データの連続的な論理オフセットおよび連続的な物理アドレスの双方を有する可変量のデータを個々に含む方法。
【請求項１８】
請求項１７記載の方法において、
前記大容量記憶システムは、前記個々のファイルを構成する前記グループのデータの複数のレコードを維持する方法。
【請求項１９】
請求項１８記載の方法において、
前記複数のレコードを維持することは、前記グループ内の前記データの少なくとも開始論理オフセットアドレスおよび開始物理アドレスを前記個々のレコード内に供給することを含む方法。
【請求項２０】
請求項１９記載の方法において、
前記複数のレコードを維持することは、前記グループ内の前記データの長さを前記個々のレコード内に供給することをさらに含む方法。
【請求項２１】
ホストシステムと一緒に再プログラム可能な不揮発性メモリシステムを動作する方法であって、前記メモリシステムは、新たなデータが書き込まれる前に消去されるメモリセルのブロックを有し、
固有のファイル識別子によってアドレス指定されたデータを受信するステップと、
前記受信したファイルデータを前記メモリシステムのブロックの１つ以上に記憶するステップと、
その後、前記記憶されたファイルデータの少なくとも幾つかを、その後の前記ホストからのコマンドに応答した結果として古い状態にするステップと、
その後、少なくとも１つの消去済みブロックを獲得してから、新たなデータを記憶するのに前記消去済みブロックの使用を必要とするデータをプログラムするコマンドを前記ホストが送信するように、前記古いファイルデータを含む１つ以上のブロックにガーベッジコレクションを行うステップと、
を含む方法。
【請求項２２】
請求項２１記載の方法において、
前記ブロックにガーベッジコレクションを行うステップは、前記ホストがアイドル状態にある期間中に生じる方法。
【請求項２３】
請求項２１記載の方法において、
前記ブロックにガーベッジコレクションを行うステップは、データを書き込むか、または読み出す前記メモリシステムの動作と交互に行われる期間中に生じる方法。
【請求項２４】
請求項２１記載の方法において、
前記ブロックにガーベッジコレクションを行うステップは、前記古いファイルのデータを含む前記１つ以上のブロックから有効データを、物理順序で少なくとも１つの他のブロック内にコピーするステップを含み、前記物理順序は、前記コピーされたデータの前記論理オフセットアドレス順序と同じである方法。
【請求項２５】
請求項２１記載の方法において、
前記固有のファイル識別子によってアドレス指定されたデータを受信するステップは、前記識別されたファイル内のオフセットを用いてアドレス指定されたデータを受信するステップを含む方法。
【請求項２６】
ホストシステムと、同時に消去できるメモリセルのブロックを有する再プログラム可能な不揮発性大容量記憶システムとの間でデータを転送する方法であって、個々のブロックは、前記ブロック内に新たなデータが書き込まれる前に消去され、
前記ホストシステムは、前記ホストシステムが生成する個々のファイルのデータを固有のファイル識別子と前記個々のファイル内の所定サイズのデータ単位のオフセットとによって識別し、前記ファイル識別子および前記オフセットを前記大容量記憶システムに送信し、
前記大容量記憶システムは、前記ホストシステムから受信した順で、前記ファイル内のデータオフセットから独立している連続的な物理アドレスを有するメモリセルの少なくとも１つの予め消去されたブロック内にファイルのデータ単位を書き込む方法。
【請求項２７】
請求項２６記載の方法において、
前記大容量記憶システムは、少なくとも１つのメモリブロックを満たすように前記ファイルのデータ単位をさらに書き込み、別のメモリブロックを満たすのに足りない量の任意の残留データが、異なるファイルの残留データも含む共通ブロック内に書き込まれる方法。
【請求項２８】
大容量記憶システムであって、
任意の新たなデータが書き込まれる前に消去され、少なくとも５１２バイトのデータを個々に含む受信した複数のデータ単位を記憶する容量を個々に有するブロックに編成された不揮発性電荷記憶半導体メモリセルのアレイと、
前記メモリセルアレイと接続され、固有のファイル識別子と、識別されたファイル内のデータのオフセットとを含む論理アドレスを有するデータを受信して、前記受信したデータをメモリセルの前記ブロック内の物理アドレスにプログラムするように適合され、前記ファイルを構成する可変量のデータのグループを識別する前記個々のファイルの前記プログラムされたデータの複数のレコードを維持するようにさらに動作するコントローラであって、前記グループ内のデータは連続的な論理オフセットアドレスおよび連続的な物理アドレスの双方を個々に有し、前記個々のレコードは、前記グループ内の前記データの少なくとも開始論理オフセットアドレスおよび開始物理アドレスを含むコントローラと、
を備える大容量記憶システム。
【請求項２９】
請求項２８記載の大容量記憶システムにおいて、
前記個々のレコードは、前記グループ内の前記データの長さをさらに含む大容量記憶システム。
【請求項３０】
請求項２８記載の大容量記憶システムにおいて、
前記メモリセルアレイは、少なくとも２５６メガバイトのデータを記憶するのに充分なメモリセルの数を含む方法。
【請求項３１】
請求項２８記載の大容量記憶システムにおいて、
前記個々のデータ単位は、少なくとも１，０２４バイトのデータを含む方法。
【請求項３２】
大容量記憶システムであって、
任意の新たなデータが書き込まれる前に消去され、少なくとも１，０２４バイトの受信したデータを記憶する容量を個々に有するブロックに編成された不揮発性電荷記憶半導体メモリセルのアレイと、
前記メモリセルアレイと接続され、固有のファイル識別子と、識別されたファイル内のデータのオフセットとを含む論理アドレスを有するデータを受信して、前記個々のメモリセルブロックの前記容量以下の大きさを個々に有し、連続的な論理アドレスおよび連続的な物理アドレスを有するデータを含む定義されたデータのグループとして、前記受信したデータをメモリセルの前記ブロック内の物理アドレスにプログラムするように適合されたコントローラと、
前記メモリセルアレイに記憶されたデータの個々のグループのレコードを記憶することができるテーブルであって、ファイルのデータの個々のデータレコードは、開始論理オフセットアドレス、開始物理アドレスおよび前記データのグループの長さを含むテーブルと、
を備える大容量記憶システム。
【請求項３３】
請求項３２記載の大容量記憶システムにおいて、
前記個々のデータレコードの前記開始物理アドレスは、メモリセルのブロックの識別子と、識別されたブロック内のバイト位置とを含む大容量記憶システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体フラッシュメモリのような再プログラム可能な不揮発性メモリシステムの動作に関し、特に、ホスト装置とメモリとの間のインターフェイスの管理に関する。本願明細書において参照される特許、特許出願、文献および他の資料、文書並びに事柄のすべては、あらゆる目的のためにその全体が本願明細書において参照により援用されている。
【背景技術】
【０００２】
商用フラッシュメモリシステムの初期世代では、長方形アレイのメモリセルは、標準のディスクドライブセクタのデータ量すなわち５１２バイトを各々記憶する多数のグループのセルに分割されていた。一般的に、誤り訂正符号（ＥＣＣ）と、場合によっては、ユーザデータおよび／またはユーザデータが記憶されるメモリセルグループに関する他のオーバーヘッドデータとを記憶するために１６バイトのような追加のデータ量も、各グループに含まれている。このような各グループのメモリセルは、同時に消去できる最小数のメモリセルである。すなわち、事実上、消去単位は、１つのデータセクタと、含まれている任意のオーバーヘッドデータとを記憶するメモリセルの数である。この種のメモリシステムの例は、米国特許第５，６０２，９８７号（特許文献１）および第６，４２６，８９３号（特許文献２）に記載されている。メモリセルをデータで再プログラムする前にメモリセルを消去する必要があるということがフラッシュメモリの特性である。
【０００３】
フラッシュメモリシステムは、パーソナルコンピュータおよびカメラなどのような様々なホストと取り外し可能に接続されるメモリカードまたはフラッシュドライブの形態で最も一般的に提供される。しかし、このようなホストシステム内にフラッシュメモリシステムを埋め込むこともできる。データをメモリに書き込むとき、一般的に、ホストは固有の論理アドレスをメモリシステムの連続的な仮想アドレス空間内のセクタ、クラスタまたは他のデータ単位に割り当てる。ディスクオペレーティングシステム（ＤＯＳ）のように、ホストはデータをメモリシステムの論理アドレス空間内のアドレスに書き込み、このアドレスからデータを読み出す。メモリシステム内のコントローラは、ホストから受信した論理アドレスを、データが実際に記憶されるメモリアレイ内の物理アドレスに変換し、その後、これらのアドレス変換を追跡し続ける。メモリシステムのデータ記憶容量は、メモリシステムに対して定義された論理アドレス空間全体にわたってアドレス指定可能なデータの量と少なくとも同じ大きさである。
【０００４】
後世代のフラッシュメモリシステムでは、消去単位の大きさは、複数のセクタのデータを記憶するのに充分なメモリセルのブロックまで増大された。メモリシステムが接続されているホストシステムがセクタのような小さい最小単位でデータをプログラムし読み出すことができるとしても、多数のセクタは、フラッシュメモリの単一の消去単位に記憶される。ホストが論理セクタのデータを更新または置き換えすると、ブロック内の幾つかのセクタのデータが古くなることは一般的である。ブロックに記憶された任意のデータを上書きできる前にブロック全体を消去する必要があるので、一般的に、新たなデータまたは更新されたデータは、このデータ用に残りの容量を有する消去済みの別のブロックに記憶される。この処理は、古いデータを有しメモリ内に貴重な空間を占有する元のブロックを残す。しかし、ブロック内に有効なデータが残っている場合、このブロックを消去することができない。
【０００５】
従って、メモリの記憶容量をより良く利用するため、有効な部分的ブロック量のデータを消去済みブロックへコピーし、これによって、これらデータがコピーされた（１つ以上の）ブロックをその後に消去し、それら全部の記憶容量を再使用できるように、これらデータを統合または収集するのが一般的である。データセクタを論理アドレスの順序にブロック内にグループ化するようにデータをコピーするのも望ましい。その理由は、このことが、データを読み出し、読み出したデータをホストに転送する速度を増大するためである。このようなデータのコピーがあまりに頻繁に行われる場合、メモリシステムの動作性能は劣化することがある。メモリの記憶容量が、システムの論理アドレス空間を介してホストによってアドレス指定可能なデータの量にすぎない場合、すなわち、一般的な例では、この劣化は、特にメモリシステムの動作に影響を及ぼす。この場合、ホストプログラミングコマンドを実行できる前にデータの統合または収集を必要とすることがある。その結果、プログラミング時間は増大する。
【０００６】
所定の半導体領域内に記憶することができるデータのビット数を増大させるため、メモリシステムの世代ごとにブロックの大きさは増大している。２５６個のデータセクタを記憶するブロックは、ますます一般的になってきている。さらに、データのプログラムおよび読み出しの並列性の度合いを増大させるため、異なるアレイまたはサブアレイの２，４またはそれ以上のブロックがメタブロック内に論理的に互いに結合されることが多い。このような大規模な容量に加えて、動作単位は、これらを効率良く動作するという点で問題を生じさせる。
【特許文献１】米国特許第５，６０２，９８７号
【特許文献２】米国特許第６，４２６，８９３号
【特許文献３】米国特許出願第１０／９１５，０３９号
【特許文献４】米国特許第５，５７０，３１５号
【特許文献５】米国特許第５，７７４，３９７号
【特許文献６】米国特許第６，０４６，９３５号
【特許文献７】米国特許第６，３７３，７４６号
【特許文献８】米国特許第６，４５６，５２８号
【特許文献９】米国特許第６，５２２，５８０号
【特許文献１０】米国特許第６，７７１，５３６号
【特許文献１１】米国特許第６，７８１，８７７号
【特許文献１２】米国公開特許出願第２００３／０１４７２７８号
【特許文献１３】米国公開特許出願第２００３／０１０９０９３号
【特許文献１４】米国特許第６，７６３，４２４号
【特許文献１５】米国特許出願第１０／７４９，８３１号
【特許文献１６】米国特許出願第１０／７５０，１５５号
【特許文献１７】米国特許出願第１０／９１７，８８８号
【特許文献１８】米国特許出願第１０／９１７，８６７号
【特許文献１９】米国特許出願第１０／９１７，８８９号
【特許文献２０】米国特許出願第１０／９１７，７２５号
【特許文献２１】米国特許出願第１０／７４９，１８９号
【特許文献２２】米国特許出願第１０／８４１，１１８号
【特許文献２３】米国特許出願第１１／０１６，２７１号
【特許文献２４】米国特許出願第１０／８９７，０４９号
【特許文献２５】米国特許出願第１１／０２２，３６９号
【発明の開示】
【０００７】
このような大規模な消去ブロックフラッシュメモリシステムを効率良く動作するという点で直面する問題を確信して様々な程度まで克服する多くの技術が開発されている。一方、本発明は、メモリとホストシステムとの間のデータ転送インターフェイスを変更することによってさらに基本的なアプローチをとる。現在行われているように仮想アドレス空間内の論理アドレスを用いてメモリとホストシステムとの間でデータをやり取りするよりはむしろ、データファイルは、ホストによって割り当てられたファイル名と、ファイル内のオフセットアドレスとによって識別される。従って、メモリシステムは、各セクタまたは他のデータ単位が属するホストファイルを識別する。本願明細書で説明されているファイル単位は、例えば、連続的なオフセットアドレスを有することによって順序付けられたデータセットであって、ホストコンピューティングシステム内で動作するアプリケーションプログラムによって生成され一意的に識別される。
【０００８】
現在、ホストは、ファイルを識別することなしに共通の論理アドレスセットによってメモリシステムへの全ファイル内のデータを識別するので、ファイル単位は、現在の商用メモリシステムによって用いられていない。論理アドレスを用いる代わりに、ファイルオブジェクトによってホストデータを識別することによって、メモリシステムコントローラは、このような頻繁なデータ統合および収集の必要性を減少させるようにデータを記憶することができる。従って、データコピー動作の頻度と、コピーされるデータの量とが著しく減少し、これによって、メモリシステムのデータプログラムおよび読み出し性能を増大させる。さらに、メモリシステムコントローラは、ホストファイルが記憶されているメモリブロックのディレクトリおよび索引テーブル情報を維持する。従って、現在、論理アドレスインターフェイスを管理するのに必要とされるファイル割り当てテーブル（ＦＡＴ）をホストが維持する必要はない。
【０００９】
単独または共同で用いられた場合に動作を改善する一因となる他の幾つかの技術を用いて、本発明のファイルベースのシステムを実施することができる。ホストからのデータは、データがホストによって供給された順に可変長データグループのメモリブロック内に書き込まれる。各データグループ内のデータは、ブロック内に連続的な論理オフセットおよび物理メモリアドレスを有する。すなわち、論理ファイルオフセットアドレス内で途切れが引き起こされるときはいつでも、新たなデータグループが開始される。これと同様に、データがメモリブロックを満たし、別のメモリブロック内に書き込まれ始めると、新たなデータグループも開始される。本システムでのようにホストではなくメモリシステムコントローラは、ホストファイルが記憶されるメモリブロックのディレクトリおよび索引テーブル情報を維持する。索引テーブル内の項目セットは、完全なファイルを形成するデータグループをリストする。
【００１０】
ガーベッジコレクションは、現在行われているメモリブロックごとよりはむしろファイルごとに開始され、従って、このような動作を必要とする所定のファイルのデータを記憶する全メモリブロックについて実行される。バックグラウンドで大部分のガーベッジコレクションを実行することができ、これによって、ホスト書き込みコマンドを実行することができる前に実行する必要があるガーベッジコレクションの頻度を著しく減少させる。
【００１１】
個々のファイルからのデータは、ファイル専用の１つ以上のメモリブロックに書き込まれる。オフセットアドレスの順序にかかわらず、ホストから受信した順にデータを書き込むことができる。ホストによって生成されたファイルデータの論理オフセット分解能と同じ物理メモリ分解能でもデータを書き込むことができる。整数のブロックが各ファイルからのデータでいっぱいになった後、使い残った２つ以上のファイルからの残留データを記憶する１つ以上の共通メモリブロックを維持することができる。
【００１２】
添付図面と併せて理解すべき本発明の例示的な実施形態の説明には、本発明の他の態様、利点、特徴および詳細が含まれる。
【発明を実施するための最良の形態】
【００１３】
フラッシュメモリシステムの概要
図１〜図８に関して、現在のフラッシュメモリシステムと、ホスト装置を用いる一般的な動作とを説明する。このようなシステムでは、本発明の様々な態様を実施することができる。図１のホストシステム１はデータをフラッシュメモリ２に記憶し、データをフラッシュメモリ２から取り出す。フラッシュメモリをホスト内に埋め込むことができるが、メモリ２は、機械的かつ電気的コネクタの嵌め合い部分３，４を介してホストに取り外し可能に接続されるカードの一般的な形態として示されている。現在、数多くの異なるフラッシュメモリカードが市販され、一例として、コンパクトフラッシュ（登録商標）（ＣＦ）カード、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）カード、ミニＳＤカード、メモリスティックカード、スマートメディアカードおよびトランスフラッシュカードが挙げられる。これらカードの各々は、その標準化仕様に従って固有の機械的および／または電気的インターフェイスを有するが、各々に含まれるフラッシュメモリは、ほとんど同じである。これらのカードはすべて、本願の譲受人であるサンディスク  コーポレーションから入手可能である。サンディスク  コーポレーションは、ホストのユニバーサルシリアルバス（ＵＳＢ）レセプタクルに差し込むことによってホストと接続するＵＳＢプラグを有する小形パッケージ内のハンドヘルドメモリシステムであるＣｒｕｚｅｒ（登録商標）下の一連のフラッシュドライブをも提供する。これらメモリカードおよびフラッシュドライブの各々は、ホストとインターフェイスをとり、それら内に、フラッシュメモリの動作を制御するコントローラを含む。
【００１４】
このようなメモリカードおよびフラッシュドライブを用いるホストシステムは、数多くあり様々である。ホストシステムは、パーソナルコンピュータ（ＰＣ）、ラップトップおよび他のポータブルコンピュータ、携帯電話、個人用携帯情報端末（ＰＤＡ）、デジタル静止カメラ、デジタル動画カメラおよびポータブルオーディオプレーヤを含む。一般的に、ホストは、１つ以上の種類のメモリカードまたはフラッシュドライブに対して組み込みレセプタクルを含むが、メモリカードが差し込まれるアダプタを必要とするものもある。
【００１５】
メモリ２が関与する限りにおいて、図１のホストシステム１を、回路およびソフトウェアの組み合わせで構成された２つの主要な部分を有すると見なすことができる。これらの部分は、アプリケーション部分５と、メモリ２とインターフェイスをとるドライバ部分６とである。パーソナルコンピュータでは、例えば、アプリケーション部分５は、プロセッサが実行するワード処理、グラフィックス、制御または他の一般的なアプリケーションソフトウェアを含むことができる。単一の機能セットを実行することを主に専用とするカメラ、携帯電話または他のホストシステムでは、アプリケーション部分５は、写真をとり記憶するようにカメラを動作するソフトウェアや、電話をかけ電話を受けるように携帯電話を動作するソフトウェアなどを含む。
【００１６】
図１のメモリシステム２は、フラッシュメモリ７と、データをやり取りするカードが接続されているホストとインターフェイスをとり、メモリ７を制御する回路８とを含む。一般的に、コントローラ８は、データをプログラムし読み出す間に、ホスト１によって用いられるデータの論理アドレスと、メモリ７の物理アドレスとの間で変換を行う。
【００１７】
図２に関して、図１の不揮発性メモリ２として用いることができる例示的なフラッシュメモリシステムの回路を説明する。一般的に、システムコントローラは、システムバス１３を介して１つ以上の集積回路メモリチップ、すなわち、図２に示されている単一のメモリチップ１５と並列に接続された単一の集積回路チップ１１上に実施されている。図に示す特定のバス１３は、データを搬送する別個のセットの導体１７と、メモリアドレス用のセット１９と、制御およびステータス信号用のセット２１とを含む。あるいはまた、単一セットの導体を、これら３つの機能の間で時分割にすることができる。さらに、「リングバス構造とフラッシュメモリシステムにおけるその使用法」という２００４年８月９日に出願された米国特許出願第１０／９１５，０３９号（特許文献３）に記載されている環状バスのような他の構成のシステムバスを用いることができる。
【００１８】
一般的なコントローラチップ１１は、それ自体の内部バス２３を有し、内部バス２３は、インターフェイス回路２５を介してシステムバス１３とインターフェイスをとる。一般的にバスに接続される主要な機能は、（マイクロプロセッサまたはマイクロコントローラのような）プロセッサ２７と、システム初期化（「ブート」）するコードを含む読み出し専用メモリ（ＲＯＭ）２９と、メモリおよびホスト間で転送されるデータをバッファリングするのに主に用いられるランダムアクセスメモリ（ＲＡＭ）３１と、コントローラを介してメモリおよびホスト間で受け渡すデータの誤り訂正符号（ＥＣＣ）を計算し検査する回路３３とである。コントローラバス２３は、回路３５を介してホストシステムとインターフェイスをとり、回路３５がメモリカード内に含まれている図２のシステムの場合、コネクタ４の一部であるカードの外部接点３７を介して行われる。クロック３９は、コントローラ１１の他の構成要素の各々と接続され、これら各々によって用いられる。
【００１９】
一般的に、メモリチップ１５は、システムバス１３と接続されている他の何らかのメモリチップと同様に、複数のサブアレイまたはプレーン、すなわち、図に示されているような２つのプレーン４１，４３に編成されているメモリセルのアレイを含む。説明を簡単にするために２つのこのようなプレーン４１，４３は示されているが、４または８つのような多くのこのようなプレーンを代わりに用いることもできる。あるいはまた、チップ１５のメモリセルアレイをプレーンに分割しなくてもよい。しかし、このように分割された場合、各プレーンは、それ自体の列制御回路４５，４７を有し、列制御回路４５，４７は互いに独立して動作することができる。回路４５，４７は、システムバス１３のアドレス部分１９からそれぞれのメモリセルアレイのアドレスを受信し、これらアドレスを復号化して、それぞれのビット線４９，５１の特定の１つまたはそれ以上にアドレス指定する。ワード線５３は、アドレスバス１９で受信したアドレスに応答する行制御回路５５を介してアドレス指定される。ｐウェル電圧制御回路６１，６３と同様にソース電圧制御回路５７，５９も、それぞれのプレーンと接続されている。メモリチップ１５が単一アレイのメモリセルを有する場合、かつ、２つ以上のこのようなチップがシステム内に存在する場合、前述したような複数プレーンチップ内のプレーンまたはサブアレイに類似して各チップのアレイを動作することができる。
【００２０】
データは、システムバス１３のデータ部分１７と接続されているそれぞれのデータ入力／出力回路６５，６７を介してプレーン４１，４３に転送され、プレーン４１，４３から転送される。回路６５，６７は、それぞれの列制御回路４５，４７を介してプレーンに接続された線６９，７１を介してデータをそれぞれのプレーンのメモリセルにプログラムし、メモリセルからデータを読み出すために設けられている。
【００２１】
コントローラ１１は、データをプログラムし、データを読み出し、消去し、様々なハウスキーピング問題に応えるようにメモリチップ１５の動作を制御するが、各メモリチップは、このような機能を実行するためにコントローラ１１からのコマンドを実行する何らかの制御回路をも含む。インターフェイス回路７３は、システムバス１３の制御およびステータス部分２１に接続されている。コントローラからのコマンドは状態マシン７５に与えられ、状態マシン７５は、これらコマンドを実行するために他の回路の特定制御を行う。制御線７７〜８１は、図２に示されているように、これらの他の回路と状態マシン７５とを接続する。状態マシン７５からのステータス情報は線８３を介してインターフェイス回路７３に伝達され、インターフェイス回路７３によってバス部分２１を介してコントローラ１１に伝送される。
【００２２】
メモリセルアレイ４１，４３のＮＡＮＤ構造は現在のところ好ましい。しかし、ＮＯＲのような他の構造も代わりに用いることができる。ＮＡＮＤフラッシュメモリおよびメモリシステムの一部としてのＮＡＮＤフラッシュメモリの動作の例は、米国特許第５，５７０，３１５号（特許文献４）、第５，７７４，３９７号（特許文献５）、第６，０４６，９３５号（特許文献６）、第６，３７３，７４６号（特許文献７）、第６，４５６，５２８号（特許文献８）、第６，５２２，５８０号（特許文献９）、第６，７７１，５３６号（特許文献１０）、および第６，７８１，８７７号（特許文献１１）、並びに米国公開特許出願第２００３／０１４７２７８号（特許文献１２）を参照することができる。
【００２３】
図２のメモリシステムのメモリセルアレイ４１の一部である図３の回路図によって例示的なＮＡＮＤアレイを示す。多数のグローバルビット線が設けられている。図３には、説明を簡単にするために４つだけのこのような線９１〜９４が示されている。多数の直列接続されたメモリセルストリング９７〜１０４は、これらのビット線の１つと基準電位との間で接続されている。代表するものとしてメモリセルストリング９９を参照すると、複数の電荷記憶メモリセル１０７〜１１０は直列に接続され、ストリングの両端には選択トランジスタ１１１，１１２を有する。ストリングの選択トランジスタが導通状態にされる場合、ストリングはビット線と基準電位との間で接続される。その後、このストリング内の１つのメモリセルは同時にプログラムまたは読み出される。
【００２４】
図３のワード線１１５〜１１８は個々にメモリセルの多数の各ストリング内の１つのメモリセルの電荷記憶素子にわたって延在し、ゲート１１９，１２０は、ストリングの各端にある選択トランジスタの状態を制御する。共通のワード線およびコントロールゲート線１１５〜１２０を共有するメモリセルストリングは、同時に消去されるメモリセルのブロック１２３を形成するように製造されている。セルのこのブロックは、物理的に同時に消去することができる最小数のセルを含む。ワード線１１５〜１１８の１つに沿っているメモリセルの１つの行は、同時にプログラムされる。一般的に、ＮＡＮＤアレイの行は、指示された順序でプログラムされ、この場合には、接地点または別の共通電位に接続されたストリングの端部に最も近いワード線１１８に沿っている行から始まる順序でプログラムされる。ワード線１１７に沿っているメモリセルの行が次にプログラムされ、その後、ブロック１２３を通じて次々にプログラムされる。ワード線１１５に沿っている行が最後にプログラムされる。
【００２５】
第２のブロック１２５は第１のブロック１２３と類似し、メモリセルのストリングが、第１のブロック１２３のストリングと同じグローバルビット線に接続されている。しかし、このブロック１２５は、異なるセットのワード線およびコントロールゲート線を有する。ワード線およびコントロールゲート線は、行制御回路５５によって適切な動作電圧に駆動される。システム内に図２のプレーン１およびプレーン２のような２つ以上のプレーンまたはサブアレイが存在する場合、１つのメモリ構造は、これらプレーンの間に延在する共通のワード線を用いる。あるいはまた、３つ以上のプレーンまたはサブアレイは共通のワード線を共有することができる。他のメモリ構造では、個々のプレーンまたはサブアレイのワード線は別々に駆動される。
【００２６】
前に援用されているＮＡＮＤに関する特許および公開特許出願の幾つかに記載されているように、３つ以上の検出可能な電荷レベルを各電荷記憶素子または領域に記憶し、これによって、２ビット以上のデータを各電荷記憶素子または領域に記憶するようにメモリシステムを動作することができる。メモリセルの電荷記憶素子は、最も一般的には導電性フローティングゲートであるが、米国公開特許出願第２００３／０１０９０９３号（特許文献１３）に記載されているような非導電性の誘電体電荷トラップ材料とすることもできる。
【００２７】
図４には、以下のさらなる説明において一例として用いられるフラッシュメモリセルアレイ７（図１）の編成を概念的に示す。メモリセルの４つのプレーンまたはサブアレイ１３１〜１３４を、単一の集積メモリセルチップ上、２つのチップ（各チップ上のプレーンのうちの２つ）上、または、４つの別個のチップ上に形成することができる。特定の配置は、以下の説明にとって重要ではない。１，２，８，１６またはそれ以上のような他の数のプレーンがシステム内に存在しうることもちろんである。プレーンは、図４に示されているように、それぞれのプレーン１３１〜１３４に配置されているブロック１３７，１３８，１３９，１４０のような長方形ごとにメモリセルのブロックに個々に分割される。各プレーンには、数十または何百ものブロックを形成することができる。前述したように、メモリセルのブロックは消去単位であり、最小数のメモリセルは物理的に同時に消去可能である。しかし、増大される並列性のため、ブロックは大規模なメタブロック単位で動作される。各プレーンからの１つのブロックは、メタブロックを形成するように論理的に互いに結合される。４つのブロック１３７〜１４０は１つのメタブロック１４１を形成することが示されている。一般的に、メタブロック内の全セルは同時に消去される。ブロック１４５〜１４８で構成された第２のメタブロック１４３に示されているように、メタブロックを形成するのに用いられるブロックを、それぞれのプレーン内の同じ相対位置に制限する必要はない。一般的に、すべてのプレーンにわたってメタブロックを延在するのが好ましいが、高度なシステム性能の場合、異なるプレーン内の１，２または３つのブロックの一部または全部からメタブロックを動的に形成する機能を用いてメモリシステムを動作することができる。これによって、メタブロックの大きさを、１回のプログラム動作で記憶するのに利用できるデータ量と厳密に一致させることができる。
【００２８】
次に、個々のブロックは、図５に示されているように、動作上の目的のためにメモリセルのページに分割される。例えば、各ブロック１３１〜１３４のメモリセルはそれぞれ８つのページＰ０〜Ｐ７に分割されている。あるいはまた、各ブロック内には、１６，３２またはそれ以上のページのメモリセルを形成することができる。ページは、同時にプログラムされる最小量のデータを含むブロック内にデータをプログラムし読み出す単位である。図３のＮＡＮＤ構造では、ページは、ブロック内のワード線に沿っているメモリセルの形態を成す。しかし、メモリシステムの動作の並列性を増大させるため、２つ以上のブロック内のこのようなページをメタページに論理的に結合することができる。４つの各ブロック１３１〜１３４から１つの物理ページの形態を成すメタページ１５１を図５に示す。例えば、メタページ１５１は４つの各ブロックのページＰ２を含むが、メタページのページは必ずしも各ブロック内で同じ相対位置を有する必要はない。最大量のデータを４つのすべてのプレーンにわたって同時にプログラムし読み出すのが好ましいが、高度なシステム性能の場合、異なるプレーン内の別個のブロックの１，２または３つのページの一部または全部からメタページを形成するようにもメモリシステムを動作することができる。これによって、プログラムおよび読み出し動作が、都合良く同時に処理できるデータ量と適応的に一致することができ、メタページの一部が、データでプログラムされずに残る事態を減少させる。
【００２９】
図５に示されているように、複数のプレーンの物理ページの形態を成すメタページは、これら複数のプレーンのワード線行に沿っているメモリセルを含む。１つのワード線行内の全セルを同時にプログラムするよりはむしろ、より一般的には、メモリセルは、２つ以上のインターリーブされたグループで交互にプログラムされる。各グループは、（単一ブロックの）１ページのデータまたは（複数のブロックにまたがる）メタページのデータを記憶する。交互になっているメモリセルを同時にプログラムすることによって、データレジスタおよびセンス増幅器を含む一ユニットの周辺回路をビット線ごとに設ける必要はなくむしろ、隣接するビット線間で時分割にする。このことは、周辺回路に必要とされる基板空間の量を節約し、増大した密度でメモリセルを行に沿って詰めることができる。そうでなければ、所定のメモリシステムから利用できる並列性を最大にするために、行に沿っている全セルを同時にプログラムするのが好ましい。
【００３０】
図３に関して、行に沿っている他のメモリセルごとのデータの同時プログラムは、図に示されている単一行の代わりに、ＮＡＮＤストリングの少なくとも一方の端部に沿って２つの行の選択トランジスタ（図示せず）を設けることによって最も好適に達成される。次に、一方の行の選択トランジスタは、１つの制御信号に応答してブロック内の他のすべてのストリングをそれぞれのビット線に接続し、他方の行の選択トランジスタは、もう１つの制御信号に応答して、介在する他のすべてのストリングをそれぞれのビット線に接続する。従って、２つのページのデータは、各行のメモリセルに書き込まれる。
【００３１】
一般的に、各論理ページ内のデータ量は整数の１つ以上のセクタのデータであり、慣例として各セクタは５１２バイトのデータを含む。図６には、ページまたはメタページの２つのセクタ１５３，１５５のデータの論理データページを示す。一般的に、各セクタは、記憶されているユーザまたはシステムデータの５１２バイトの部分１５７と、部分１５７内のデータに関連するか、または、データが記憶されている物理ページあるいはブロックに関連するオーバーヘッドデータ用の別のバイト数１５９とを含む。オーバーヘッドデータのバイト数は一般的に１６バイトであり、総計で、セクタ１５３，１５５ごとに５２８バイトになる。オーバーヘッド部分１５９は、プログラミング中にデータ部分１５７から計算されたＥＣＣ、論理アドレス、ブロックが消去され再プログラムされた回数の体験数、１つ以上の制御フラグ、動作電圧レベルおよび／またはその類と、このようなオーバーヘッドデータ１５９から計算されたＥＣＣとを含むことができる。あるいはまた、オーバーヘッドデータ１５９またはその一部を、他のブロックの異なるページに記憶することができる。
【００３２】
メモリの並列性が増大するにつれて、メタブロックのデータ記憶容量が増大し、結果として、データページおよびメタページの大きさも増大する。この場合、データページは３つ以上のセクタのデータを含むことができる。１メタページ当たりに２つのデータページがあり、データページ内には２つのセクタがある場合、メタページには４つのセクタが存在する。従って、各メタページは２，０４８バイトのデータを記憶する。このことは高度な並列性であり、行内のメモリセルの数が増大するにつれてさらに増大することができる。この理由のため、フラッシュメモリの幅は拡張されてページおよびメタページ内のデータ量を増大させる。
【００３３】
前に確認されている物理的に小さい再プログラム可能な不揮発性メモリカードおよびフラッシュドライブは、５１２メガバイト（ＭＢ）、１ギガバイト（ＧＢ）、２ＧＢおよび４ＧＢのデータ記憶容量を伴って市販され、データ記憶容量をそれ以上高くすることができる。図７には、ホストとこのような大容量メモリシステムとの間の最も一般的なインターフェイスを示す。ホストは、ホストによって実行されたアプリケーションソフトウェアまたはファームウェアプログラムによって生成されるか、または用いられるデータファイルに対応する。一例としてワード処理データファイルが挙げられ、別の例としてコンピュータ支援設計（ＣＡＤ）ソフトウェアの描画ファイルが挙げられ、これらは、主に、パーソナルコンピュータおよびラップトップコンピュータなどのような汎用コンピュータホストに見られる。ｐｄｆ形式の文書も、このようなファイルがある。デジタルスチルビデオカメラは、メモリカードに記憶された写真ごとのデータファイルを生成する。携帯電話は、電話帳のような内部メモリカード上のファイルからデータを用いる。ＰＤＡは、アドレスファイルおよびカレンダファイルなどのような幾つかの異なるファイルを記憶し用いる。任意のこのようなアプリケーションでは、メモリカードは、ホストを動作するソフトウェアをも含むこともできる。
【００３４】
図７には、ホストとメモリシステムとの間の一般的な論理インターフェイスを示す。連続的な論理アドレス空間１６１は、メモリシステムに記憶できるデータのすべてに対するアドレスを備えるほど充分大きい。一般的に、ホストアドレス空間はクラスタのデータの単位で分割されている。所定のホストシステムにおいて、４〜６４セクタくらいが一般的である多数のセクタのデータを含むように各クラスタを設計することができる。標準のセクタは５１２バイトのデータを含む。
【００３５】
図７の例には、生成された３つのファイル１、ファイル２およびファイル３が示されている。ホストシステム上で実行しているアプリケーションプログラムは、順序付けられたデータセットとして各ファイルを生成し、固有の名前または他の基準によって識別する。他のファイルにまだ割り当てられていない充分に利用可能な論理アドレス空間は、ホストによってファイル１に割り当てられる。ファイル１は利用可能な論理アドレスの連続的な範囲に割り当てられたことが示されている。一般的に、アドレスの範囲は、ホストオペレーティングソフトウェアに対する特定範囲のような特定の目的のためにも割り当てられる。ホストが論理アドレスをデータに割り当てている時点で、これらアドレスが用いられなかったとしても、これらアドレスの範囲は、データを記憶するために回避される。
【００３６】
後にファイル２がホストによって生成されると、図７に示されているように、ホストは、論理アドレス空間１６１内の連続的なアドレスの２つの異なる範囲を同様に割り当てる。ファイルを連続的な論理アドレスに割り当てる必要はなくむしろ、他のファイルに既に割り当てられたアドレス範囲の間内のアドレス部分に割り当てることができる。この例は、次に、ホストによって生成されたさらなる別のファイル３が、ファイル１、ファイル２および他のデータにまだ割り当てられていないホストアドレス空間の他の部分に割り当てられることを示す。
【００３７】
ホストが様々なホストファイルに割り当てる論理アドレスが維持されるファイルアロケーションテーブル（ＦＡＴ）を維持することによって、ホストはメモリ論理アドレス空間を追跡し続ける。一般的に、ＦＡＴテーブルは、ホストメモリだけでなく不揮発性メモリにも記憶され、新たなファイルが記憶されたり、他のファイルが削除されたり、ファイルが修正されたりするので、ホストによって頻繁に更新される。例えば、ホストファイルが削除されると、次に、ホストは、ＦＡＴテーブルを更新することによって、削除されたファイルに以前割り当てられた論理アドレスを割り当て解除して、これら論理アドレスが今では他のデータファイルで用いるために利用できることを示す。
【００３８】
ホストは、ファイルを記憶するのにメモリシステムコントローラが選択する物理位置について関心を持たない。一般的なホストは、論理アドレス空間、およびホストが様々なファイルに割り当てた論理アドレスだけを知っている。その一方で、メモリシステムは、一般的なホスト／カードインターフェイスを通じて、データが書き込まれた論理アドレス空間部分だけを知っているが、特定のホストファイルに割り当てられた論理アドレスを知らず、または、ホストファイルの数さえも知らない。メモリシステムコントローラは、データを記憶または取り出すためにホストによって供給された論理アドレスを、ホストデータが記憶されるフラッシュメモリセルアレイ内の固有の物理アドレスに変換する。ブロック１６３は、メモリシステムコントローラによって維持されるこれらの論理−物理アドレス変換の作業テーブルを表す。
【００３９】
メモリシステムコントローラは、システムの性能を高水準に維持するようにデータファイルをメモリアレイ１６５のブロックまたはメタブロック内に記憶するためにプログラムされる。４つのプレーンまたはサブアレイは、この図のように用いられる。各プレーンからブロックの形態を成すメタブロック全体にわたって、システムが許容できる限りの並列性でデータをプログラムし読み出すのが好ましい。一般的に、少なくとも１つのメタブロック１６７は、オペレーティングファームウェアと、メモリコントローラによって用いられるデータとを記憶する予約済みブロックとして割り当てられる。ホストオペレーティングソフトウェアおよびホストＦＡＴテーブルなどを記憶するために別のメタブロック１６９または複数のメタブロックを割り当てることができる。物理記憶空間の大部分は、データファイルを記憶するために残る。しかし、メモリコントローラは、受信したデータが様々なファイルオブジェクトのうちでホストによってどのように割り当てられたかを知らない。ホストによって特定の論理アドレスに書き込まれたデータが、コントローラの論理−物理アドレステーブル１６３によって維持されたような対応する物理アドレスに記憶されていることをすべてのメモリコントローラは一般的にホストとの対話から知る。
【００４０】
一般的なメモリシステムでは、アドレス空間１６１内にデータ量を記憶することが必要である数個の追加のブロックの記憶容量が設けられている。これら追加のブロックの１つ以上を、メモリの存続期間中に欠陥品になることがある他のブロックの代替とする冗長ブロックとして設けることができる。一般的に、最初はメタブロックに割り当てられた欠陥のあるブロックを冗長ブロックで代替することを含む様々な理由のために、個々のメタブロック内に含まれたブロックの論理グループを変更することができる。一般的に、メタブロック１７１のような１つ以上の追加のブロックは消去済みブロックプール内に維持される。ホストがデータをメモリシステムに書き込むと、コントローラは、ホストによって割り当てられた論理アドレスを消去済みブロックプール内のメタブロック内の物理アドレスに変換する。次に、データを論理アドレス空間１６１内に記憶するのに用いられていない他のメタブロックは消去され、その後のデータ書き込み動作中に用いるための消去済みプールブロックとして指定される。
【００４１】
特定のホスト論理アドレスに記憶されたデータは、最初に記憶されたデータが古くなると新たなデータによって頻繁に上書きされる。これに応答して、メモリシステムコントローラは新たなデータを消去済みブロックに書き込み、次に、これらの論理アドレスのデータが記憶される新たな物理ブロックを識別するためにこれらの論理アドレスに対して論理−物理アドレステーブルを変更する。次に、これらの論理アドレスの原データを含むブロックは消去され、新たなデータを記憶するために利用される。消去済みブロックプールからの事前消去済みブロック内の記憶容量が書き込みの開始で足りない場合、多くの場合、このような消去は、現在のデータ書き込み動作が完了できる前に行われる必要がある。このことは、システムデータプログラム速度に悪影響を及ぼすことがある。一般的に、メモリコントローラは、ホストが新たなデータを同一の論理アドレスに書き込むときだけ、所定の論理アドレスのデータが古くなったことがホストによって分かる。従って、メモリの多くのブロックにこのような無効なデータを一時的に記憶することがある。
【００４２】
集積回路メモリチップの領域を効率良く用いるためにブロックおよびメタブロックの大きさは増大している。この結果、個々のデータ書き込みの大部分が、メタブロックの記憶容量に満たないデータ量を記憶することになり、多くの場合、ブロックの記憶容量に満たないデータ量を記憶することさえある。一般的に、メモリシステムコントローラが新たなデータを消去済みプールメタブロックに誘導するので、このことによって、満たされない状態になるメタブロック部分が生じることがある。新たなデータが、別のメタブロックに記憶された一部のデータの更新情報である場合には、新たなデータのメタページの論理アドレスと隣接する論理アドレスを有するこの別のメタブロックから残りの有効なメタページのデータを論理アドレス順で新たなメタブロックへコピーするのも望ましい。古いメタブロックは、他の有効なデータメタページを保存することがある。この結果、長期にわたると、個々のメタブロックの特定のメタページのデータは古い状態にされ無効になり、異なるメタブロックに書き込まれた同一の論理アドレスを有する新たなデータによって置き換えられることになる。
【００４３】
論理アドレス空間１６１の全体にわたってデータを記憶するのに充分な物理メモリ空間を維持するため、このようなデータは周期的に圧縮または統合される（ガーベッジコレクション）。可能な限り論理アドレスと同じ順序でメタブロック内のセクタのデータを維持することも望ましい。その理由は、このことが、連続的な論理アドレスで効率良くデータを読み出させるためである。従って、この追加の目標を伴ってデータ圧縮およびガーベッジコレクションが一般的に実行される。一部のブロックデータの更新情報を受信するときにメモリを管理する幾つかの態様と、メタブロックの使用とについては、米国特許第６，７６３，４２４号（特許文献１４）に記載されている。
【００４４】
一般的に、データ圧縮は、処理中、無効データを有するメタページを無視して、すべての有効なデータメタページをメタブロックから読み出し、これらを新たなブロックに書き込むことを含む。また、有効データを有するメタページを、これらに記憶されたデータの論理アドレス順に一致する物理アドレス順で配置するのが好ましい。無効データを含むメタページが新たなメタブロックへコピーされないので、新たなメタブロックに占められるメタページの数は、古いメタブロックに占められるメタページに満たない。次に、古いブロックは消去され、新たなデータを記憶するために利用される。統合によって獲得された容量の追加のメタページをその後に他のデータを記憶するのに用いることができる。
【００４５】
ガーベッジコレクション中、連続的またはほぼ連続的な論理アドレスを有する有効データのメタページは２つ以上のメタブロックから収集され、別のメタブロック、一般的には、消去済みブロックプール内のメタブロックに再度書き込まれる。すべての有効なデータメタページが元の２つ以上のメタブロックからコピーされる場合、それらを将来使用するために消去することができる。
【００４６】
データの統合およびガーベッジコレクションは時間を取り、特に、ホストからのコマンドを実行できる前にデータの統合またはガーベッジコレクションを行う必要がある場合にはメモリシステムの性能に影響を及ぼすことがある。一般的に、このような動作は、可能な限りバックグラウンドで行われるようにメモリシステムコントローラによってスケジュールされるが、これらの動作を実行する必要性によって、コントローラは、このような動作が完了するまでビジーステート信号をホストに与えなければならない。ホストコマンドの実行を遅延する場合がある例として、ホストがメモリに書き込みたいと思う全データを記憶する事前消去済みメタブロックが消去済みブロックプール内に不足し、後で消去できる１つ以上のメタブロックの有効データをクリアするためにデータの統合またはガーベッジコレクションが最初に必要とされる場合が挙げられる。従って、このような混乱を最小限にするため、メモリの制御を管理することに注意が向けられた。多くのこのような技術は、「大きな消去ブロックを有する不揮発性メモリシステムの管理」という２００３年１２月３０日に出願された米国特許出願第１０／７４９，８３１号（特許文献１５）、「不揮発性メモリおよびブロック管理システムを伴う方法」という２００３年１２月３０日に出願された米国特許出願第１０／７５０，１５５号（特許文献１６）、「不揮発性メモリおよびメモリプレーン配列を伴う方法」という２００４年８月１３日に出願された米国特許出願第１０／９１７，８８８号（特許文献１７）、２００４年８月１３日に出願された米国特許出願第１０／９１７，８６７号（特許文献１８）、「不揮発性メモリおよびフェーズ化されたプログラム障害処理を伴う方法」という２００４年８月１３日に出願された米国特許出願第１０／９１７，８８９号（特許文献１９）、および「不揮発性メモリおよび制御データ管理を伴う方法」という２００４年８月１３日に出願された米国特許出願第１０／９１７，７２５号（特許文献２０）に記載されている。
【００４７】
極めて大規模な消去済みブロックを有するメモリアレイの動作を効率良く制御する１つの課題は、所定の書き込み動作中に記憶されるデータセクタの数をメモリのブロックの容量および境界と一致させ、位置合わせすることである。１つのアプローチは、最大数のブロックに満たないホストから新たなデータを記憶するのに用いられるメタブロックを構成し、必要に応じて、メタブロック全体を満たす量に満たないデータ量を記憶することである。適応メタブロックの使用については、「適応メタブロック」という２００３年１２月３０日に出願された米国特許出願第１０／７４９，１８９号（特許文献２１）に記載されている。データのブロック間の境界とメタブロック間の物理境界との適合については、２００４年５月７日出願の米国特許出願第１０／８４１，１１８号（特許文献２２）、および、「データ・ラン・プログラミング」という２００４年１２月１６日に出願された米国特許出願第１１／０１６，２７１号（特許文献２３）に記載されている。
【００４８】
メモリコントローラは、ホストによって不揮発性メモリに記憶されたＦＡＴテーブルからデータを使用しても、メモリシステムを効率良く動作することができる。このような使用の１つは、論理アドレスを割り当て解除することによって、データが古いとホストによって識別された時点を知ることである。この時点を知ることは、一般的に、ホストが新たなデータを論理アドレスに書き込むことによってメモリコントローラがそれを知る前に、このような無効データを含むブロックの消去をメモリコントローラにスケジュールさせることができる。このことについては、「不揮発性メモリシステム上のデータを保持するための方法および装置」という２００４年７月２１日に出願された米国特許出願第１０／８９７，０４９号（特許文献２４）に記載されている。他の技術には、所定の書き込み動作が単一ファイルであるかどうかを推定し、複数ファイルである場合、ファイル間の境界がどこに位置するかを推定するために、新たなデータをメモリに書き込むホストパターンを監視することが含まれる。この種類の技術の使用については、「最適化された一連のクラスタ管理のためのＦＡＴ解析」という２００４年１２月２３日に出願された米国特許出願第１１／０２２，３６９号（特許文献２５）に記載されている。
【００４９】
メモリシステムを効率良く動作するため、ホストによって個々のファイルのデータに割り当てられた論理アドレスについてコントローラができる限り良く分かることが望ましい。ファイル境界が分かっていない場合、データファイルが多数のメタブロックの間で分散されるというよりはむしろ、コントローラによってデータファイルを単一メタブロックまたはメタブロックグループに記憶することができる。この結果、データの統合およびガーベッジコレクション動作の数および複雑性を減少させる。結果としてメモリシステムの性能は改善する。しかし、ホスト／メモリインターフェイスが、前述したような論理アドレス空間１６１（図７）を含む場合、メモリコントローラがホストデータファイル構造を良く分かることは困難である。
【００５０】
図８に関して、図７に既に示されている一般的な論理アドレスホスト／メモリインターフェイスは、図８で異なるように示されている。ホストによって生成されたデータファイルは、ホストによって論理アドレスに割り当てられている。次に、メモリシステムはこれら論理アドレスを見て、データが実際に記憶されるメモリセルのブロックの物理アドレスにマッピングする。
【００５１】
例示的なファイルベースのインターフェイスの実施形態の説明
大容量のデータを記憶するため、ホストとメモリシステムとの間での改善されたインターフェイスは、論理アドレス空間の使用を削減する。代わりに、ホストは固有のファイルＩＤ（または、他の固有の基準）によって各ファイルを論理的にアドレス指定し、ファイル内の（バイトのような）データの単位のアドレスをオフセットする。このファイルアドレスはメモリシステムコントローラに直接に与えられ、メモリシステムコントローラは、各ホストファイルのデータが物理的に記憶されるメモリシステムコントローラ自体のテーブルを保持する。この新たなインターフェイスを、図２〜図６に関して前述したのと同じメモリシステムで実施することができる。前述したメモリシステムとの主な違いは、メモリシステムがホストシステムと通信する方法である。
【００５２】
このファイルベースのインターフェイスを図９に示す。図９のファイルベースのインターフェイスを、図７の論理アドレスインターフェイスと比較すべきである。ファイル１、ファイル２およびファイル３の各々の識別と、図９のファイル内のデータのオフセットとは、メモリコントローラに直接に受け渡される。次に、この論理アドレス情報は、メモリコントローラ機能１７３によってメモリ１６５のメタブロックおよびメタページの物理アドレスに変換される。
【００５３】
ファイルベースのインターフェイスを図１０にも示す。図１０のファイルベースのインターフェイスを、図８の論理アドレスインターフェイスと比較すべきである。図１０には、図８の論理アドレス空間と、ホストによって維持されるＦＡＴテーブルとは存在しない。それどころか、ホストによって生成されたデータファイルは、ファイル番号およびファイル内のデータのオフセットによってメモリシステムに識別される。次に、メモリシステムは、ファイルをメモリセルアレイの物理ブロックに直接マッピングする。
【００５４】
図１１に関して、本願明細書で説明されている例示的な大容量記憶システムの機能層が示されている。「直接ファイル記憶バックエンドシステム」は、主として本願明細書の主題である。直接ファイル記憶バックエンドシステムは、メモリシステムの動作に対して内側にあり、「直接ファイルインターフェイス」および「ファイルベースのフロントエンドシステム」を介してファイルベースのインターフェイスチャネル上のホストシステムと通信する。各ホストファイルは、例えばファイル名によって一意的に識別される。ファイル内のデータは、ファイルに固有の線形アドレス空間内のオフセットアドレスによって識別される。メモリシステムに対して論理アドレス空間を定義する必要はない。
【００５５】
コマンド
ホストシステムからの一連の直接ファイルインターフェイスコマンドは、メモリシステムの動作を支援する。このような一連のコマンドの一例を図１２Ａ〜１２Ｅに示す。本願明細書の残りの部分を通じて参照するため、本願明細書では、これらコマンドを簡単に要約するだけである。図１２Ａは、定義プロトコルに従ってデータをホストとメモリシステムとの間で転送させるのに用いられるホストコマンドをリストする。ファイル内の特定オフセット（＜ｏｆｆｓｅｔ＞）の指定されたファイル（＜ｆｉｌｅＩＤ＞）内のデータは、メモリシステムに書き込まれるか、またはメモリシステムから読み出される。Ｗｒｉｔｅ、ＩｎｓｅｒｔまたはＵｐｄａｔｅコマンドの伝送を行った後に、ホストからメモリシステムへのデータの伝送を行い、メモリシステムは、データをメモリアレイに書き込むことによって応答する。ホストによるＲｅａｄコマンドの伝送は、指定されたファイルのデータをホストに送信することによってメモリシステムに応答させる。メモリシステムが、ファイルの追加のデータを記憶できる次の記憶位置を識別するポインタを維持する場合、データオフセットをＷｒｉｔｅコマンドと一緒に送信する必要はない。しかし、Ｗｒｉｔｅコマンドが、既に書き込まれたファイル内にオフセットアドレスを含む場合、メモリ装置は、オフセットアドレスから開始するファイルデータを更新するコマンドであると解釈することができ、従って、別個のＵｐｄａｔｅコマンドの必要性を削減する。Ｒｅａｄコマンドに対して、ファイル全体が読み出される場合、ホストによってデータオフセットを指定する必要はない。図１２Ａに示されているデータコマンドのうち１つのデータコマンドの実行は、ホストシステムによる何か他のコマンドの伝送に応答して終了される。
【００５６】
別のデータコマンドはＲｅｍｏｖｅコマンドである。図１２Ａの他のデータコマンドとは異なって、Ｒｅｍｏｖｅコマンドの後にデータの伝送は行われない。その効果は、メモリシステムに、指定されたｏｆｆｓｅｔ１とｏｆｆｓｅｔ２との間のデータに古いとしてマークを付けさせることである。次に、これらのデータは、古いデータが存在するファイルまたはブロックの次のデータの圧縮またはガーベッジコレクション中に除去される。
【００５７】
図１２Ｂには、メモリシステム内のファイルを管理するホストコマンドをリストする。ホストが新たなファイルのデータをメモリシステムに書き込もうとしているとき、ホストは最初にＯｐｅｎコマンドを送出し、メモリシステムは、新たなファイルを開くことによって応答する。同時に開いたままでいられるファイルの数は一般的に指定される。ホストがファイルを閉じる場合、Ｃｌｏｓｅコマンドは、開いたファイルを維持するのに用いられるリソースを指定変更できることをメモリシステムに伝える。一般的に、メモリシステムは、このようなファイルをガーベッジコレクションのために直ちにスケジュールする。今、説明している直接ファイルインターフェイスを用いて、ガーベッジコレクションは、個々のメモリセルブロックを用いて物理的にではなく、論理的に管理され、主にファイルについて実行される。Ｃｌｏｓｅ＿ａｆｔｅｒコマンドは、ファイルが閉じられようとしているという先行通知をメモリシステムに与える。ファイルＤｅｌｅｔｅコマンドは、削除済みファイルからのデータを含むメモリセルブロックを、指定された優先規則に従って消去するようにメモリシステムに直ちにスケジュールさせる。Ｅｒａｓｅコマンドは、指定されたファイルのデータをメモリから直ちに消去すべきことを指定する。
【００５８】
ＤｅｌｅｔｅコマンドとＥｒａｓｅコマンドとの主な違いは、指定されたファイルデータを消去するために与えられた優先順位である。ホストは、Ｅｒａｓｅコマンドを用いて、最も早い実用的な時間で保護または機密データをメモリから除去することができ、その一方で、Ｄｅｌｅｔｅコマンドは、低い優先順位を付けてこのようなデータを消去させる。メモリシステムをパワーダウンするときのＥｒａｓｅコマンドの使用は、メモリ装置がホストから除去される前に機密データを除去し、従って、メモリ装置をその後に使用する間、このデータを他のユーザまたはホストシステムに拡散しないようにする。これらのコマンドの双方をバックグラウンドで実行し、すなわち、主なデータコマンド（図１２Ａ）の実行を減速させることなく実行するのが好ましい。いずれにしても、一般的に、ホストから別のコマンドを受信することによって、メモリコントローラはバックグラウンド動作を終了させることになる。
【００５９】
メモリシステム内のディレクトリに関連するホストコマンドを図１２Ｃにリストする。各ディレクトリコマンドは、コマンドが関連するディレクトリの識別子（＜ｄｉｒｅｃｔｏｒｙＩＤ＞）を含む。メモリシステムコントローラはディレクトリを維持するが、ディレクトリに関するコマンドおよびディレクトリの指定は、ホストシステムによって与えられる。メモリコントローラは、ホストによって与えられたディレクトリの指定と共にこれらのコマンドを、メモリシステムに記憶されたファームウェアに従って実行する。
【００６０】
＜ｆｉｌｅＩＤ＞パラメータを、ファイルの絶対パス名、または本願明細書ではｆｉｌｅ＿ｈａｎｄｌｅと称するファイルの何らかの省略表現識別子のどちらかとすることができる。ファイルパス名は、特定のコマンドと関連して図１１の直接ファイルインターフェイスに供給される。これによって、ファイルが初めて開かれたとき、充分に明白な項目をファイルディレクトリに生成することができ、既存のファイルが開かれたとき、ファイルディレクトリ内の正しい既存の項目にアクセスすることができる。ファイルパス名構文は、ＤＯＳファイルシステムによって用いられる規格に準拠することができる。パス名は、ディレクトリの階層とディレクトリの最下位のファイルとを記述する。パスセグメントを「＼」によって区切ることができる。「＼」が前に付いたパスは、ルートディレクトリに関連する。「＼」が前に付かないパスは、カレントディレクトリに関連する。「．．」のセグメントパスは、カレントディレクトリの親ディレクトリを示す。
【００６１】
あるいはまた、ファイルが最初に生成されたときに記憶装置によって割り当てられたｆｉｌｅ＿ｈａｎｄｌｅパラメータによって、開いたファイルを識別することができる。次に、ホストがファイルを開くたびに、記憶装置は、ホストに指定された省略表現ファイルと通信することができる。次に、ホストは、開いたファイルのＷｒｉｔｅ、Ｉｎｓｅｒｔ、Ｕｐｄａｔｅ、Ｒｅａｄ、ＣｌｏｓｅおよびＣｌｏｓｅ＿ａｆｔｅｒコマンドと共にｆｉｌｅ＿ｈａｎｄｌｅを用いることができる。ファイルディレクトリの階層をナビゲートする必要がないので、一般的に、ホストによるファイルへのアクセスは、絶対パス名が用いられる場合よりも速い。Ｏｐｅｎコマンドの使用によってファイルが最初に開かれる場合、メモリシステムによってこのファイルにｆｉｌｅ＿ｈａｎｄｌｅがまだ割り当てられてない可能性が高いので、一般的に絶対パス名が用いられる。しかし、既に利用可能である場合、ｆｉｌｅ＿ｈａｎｄｌｅを用いることができる。ｆｉｌｅＩＤを用いる図１２Ａおよび図１２Ｂの残りのＤｅｌｅｔｅおよびＥｒａｓｅコマンドに対して、完全なファイルパス名の使用は、ホストによって供給された誤ったｆｉｌｅ＿ｈａｎｄｌｅに対する安全対策とするのが好ましい。ホストが、意図的ではない既存のファイルの１つに一致する誤ったパス名を不注意で生成するのは困難である。
【００６２】
図１２Ｃのディレクトリコマンドは、これらが関連するディレクトリの＜ｄｉｒｅｃｔｏｒｙＩＤ＞識別子と共に図１１の直接ファイルインターフェイスによって同じように受信される。絶対パス名は、ディレクトリコマンドと共に受信されたｄｉｒｅｃｔｏｒｙＩＤとするのが好ましい。
【００６３】
ｆｉｌｅ＿ｈａｎｄｌｅは、直接ファイルインターフェイスにおいて大容量記憶装置によってＯｐｅｎコマンドに応答してホストに返信される簡易書式の識別子である。ファイルに対するディレクトリ項目に存在するＦＩＴへのポインタであるとしてｆｉｌｅ＿ｈａｎｄｌｅを定義するのが便利である。このポインタは、ファイルに対するブロック内の論理ＦＩＴブロック番号および論理ファイル番号を定義する。ポインタをｆｉｌｅ＿ｈａｎｄｌｅとして用いることによって、最初にファイルディレクトリ内のファイルを検索する必要なしにファイルＦＩＴ項目にアクセスすることができる。例えば、メモリ装置が６４個までのＦＩＴブロックを有することができる場合、各ＦＩＴブロックは６４個までのファイルに索引を付けることができ、この場合、ｆｉｌｅ＿ｈａｎｄｌｅ１１０７を有するファイルは、ＦＩＴブロック１１内の論理ファイル７に設定されたＦＩＴ内のデータグループ項目へのポインタを有する。ファイルに対するディレクトリおよびＦＩＴ項目がＯｐｅｎコマンドに応答して生成されと、このｆｉｌｅ＿ｈａｎｄｌｅはメモリシステムコントローラによって生成され、Ｃｌｏｓｅコマンドに応答して無効になる。
【００６４】
図１２Ｄには、ホストとメモリシステムとの間のインターフェイスの状態を管理するホストコマンドを示す。Ｉｄｌｅコマンドは、前もってスケジュールされたデータ消去およびガーベッジコレクションのような内部動作をメモリシステムが実行できることをメモリシステムに伝える。Ｓｔａｎｄｂｙコマンドの受信に応答して、メモリシステムは、ガーベッジコレクションおよびデータ消去のようなバックグラウンド動作の実行を停止する。Ｓｈｕｔ−ｄｏｗｎコマンドは、差し迫っている電源の損失について事前の警告をメモリコントローラに与え、これによって、揮発性コントローラバッファから不揮発性フラッシュメモリへデータを書き込むことを含む保留中のメモリ動作の完了を可能にする。
【００６５】
図１２Ｅに示されているＳｉｚｅコマンドは、一般的に、Ｗｒｉｔｅコマンドよりも前にホストによって送出される。これに応答して、メモリシステムは、書き込まれるさらなるファイルデータに利用できる容量をホストに報告する。この容量を、利用可能なプログラムされていない物理容量から、定義されたファイルデータ容量の記憶を管理するのに必要とされる物理容量を差し引くことによって計算することができる。
【００６６】
ホストがＳｔａｔｕｓコマンド（図１２Ｅ）を送出する場合、メモリ装置は現在の状況で応答する。この応答を、メモリ装置に関する情報の様々な特定の項目をホストに供給する異なるビット領域を有する１つ以上の２進ワードの形態とすることができる。例えば、１つの２ビット領域は、装置がビジー状態であるかどうかを報告し、装置がビジー状態である場合、メモリ装置が何をするためにビジー状態になっているのかに応じて２つ以上のビジーステータスを供給することができる。１つのビジーステータスは、ホストＷｒｉｔｅまたはＲｅａｄコマンドを実行してデータを転送すること、すなわちフォアグラウンド動作にメモリ装置が対応していることを示すことができる。第２のビジーステータスの指示を用いて、メモリシステムがデータの圧縮またはガーベッジコレクションのようなバックグラウンドハウスキーピング動作を実行しているときをホストに伝えることができる。ホストは、別のコマンドをメモリ装置に送信する前にこの第２のビジー状態の終わりまで待機するかどうかを決定することができる。ハウスキーピング動作が完了する前に別のコマンドが送信される場合、メモリ装置はハウスキーピング動作を終了し、コマンドを実行する。
【００６７】
ホストはＩｄｌｅコマンドと一緒に第２の装置ビジーを用いることができ、これによって、メモリ装置内でハウスキーピング動作を行うことができる。装置がハウスキーピング動作を行う必要性を生じさせる可能性が高いコマンドまたは一連のコマンドをホストが送信した後、ホストはＩｄｌｅコマンドを送信することができる。後で説明するように、ハウスキーピング動作を開始することによってＩｄｌｅコマンドに応答し、これと同時に、前述した第２のビジーを開始するようにメモリ装置をプログラムすることができる。例えば、Ｄｅｌｅｔｅコマンドは、以下で説明するアルゴリズムに従って、ガーベッジコレクションを実行する必要性を生じさせる。この場合、一連のＤｅｌｅｔｅコマンドを送出した後のホストからのＩｄｌｅコマンドは、メモリ装置が次のホストＷｒｉｔｅコマンドに応答できるために必要であるガーベッジコレクションを実行する装置時間を可能にする。そうでなければ、次のＷｒｉｔｅコマンドを受信した後で、このＷｒｉｔｅコマンドを実行することができる前にガーベッジコレクションを実行する必要があり、従って、このコマンドの実行を著しく減速せせることになる。
【００６８】
データの書き込み
新たなデータファイルがメモリにプログラムされるとき、ブロック内の第１の物理位置から始まって、ブロックの位置を連続的に順々に進行するように、データはメモリセルの消去済みブロックに書き込まれる。ファイル内のこのデータのオフセットの順序にかかわらず、データは、ホストから受信した順序でプログラムされる。ファイルの全データがメモリに書き込まれるまでプログラム動作は継続する。ファイルのデータ量が単一メモリブロックの容量を上回る場合、第１のブロックはいっぱいになり、プログラム動作は、消去済みの第２のブロックに継続する。第２のメモリブロックは、ファイルの全データが記憶されるまで、または、第２のブロックがいっぱいになるまで第１の位置から順々に第１のブロックと同様にプログラムされる。ファイルの残りのデータで第３または追加のブロックをプログラムすることができる。単一ファイルのデータを記憶する複数ブロックまたはメタブロックを物理的または論理的に連続にする必要はない。説明を容易にするため、他に特に指定がなければ、本願明細書で用いられる「ブロック」という用語は、特定のシステムにメタブロックが用いられているかどうかに応じて消去のブロック単位または複数ブロック「メタブロック」のどちらかを意味するものとする。
【００６９】
図１３Ａに関して、メモリシステムへのデータファイルの書き込みを示す。この例では、データファイル１８１は、垂直の実線間に延在すると示されたメモリシステムの１つのブロックまたはメタブロック１８３の記憶容量よりも大きい。従って、データファイル１８１の部分１８４は第２のブロック１８５にも書き込まれている。これらのメモリセルブロックは物理的に連続であるように示されているが、必ずしも連続である必要はない。ファイル１８１からのデータは、ホストから受信したストリーミングであるので、ファイルの全データがメモリに書き込まれるまで書き込まれる。図１３Ａの例では、データ１８１は、図１２ＡのＷｒｉｔｅコマンドの後にホストから受信したファイルの初期データである。
【００７０】
記憶されたデータを管理し追跡し続けるメモリシステムにとって好適な方法は、可変サイズのデータグループを用いることである。すなわち、ファイルのデータは、完全なファイルを形成するように、定義された順序で互いに連結できる複数のデータグループとして記憶される。しかし、好ましくは、ファイル内のデータグループの順序は、ファイル索引テーブル（ＦＩＴ）を用いてメモリシステムコントローラによって維持される。ホストからデータのストリームが書き込まれているとき、ファイルデータの論理オフセットアドレス、または、データが記憶される物理空間のどちらかに途切れがあるときはいつでも、新たなデータグループが開始される。このような物理的な途切れの一例として、ファイルのデータが１つのブロックを満たし、別のブロックに書き込まれ始めるときが挙げられる。このことは図１３Ａに示され、第１のデータグループが第１のブロック１８３を満たし、ファイルの残りの部分１８４は、第２のデータグループとして第２のブロック１８５内に記憶される。第１のデータグループを（Ｆ０，Ｄ０）によって表すことができ、ここで、Ｆ０は、データファイルの始まりの論理オフセットであり、Ｄ０は、ファイルが始まるメモリ内の物理位置である。第２のデータグループは（Ｆ１，Ｄ１）として表され、ここで、Ｆ１は、第２のブロック１８５の始まりで記憶されるデータの論理ファイルオフセットであり、Ｄ１は、データが記憶される物理位置である。
【００７１】
ホスト−メモリインターフェイスを介して転送されるデータの量をデータのバイトの数、データのセクタの数、または、何らかの他の粒度で表現することができる。ほとんどの場合、ホストはファイルのデータをバイト粒度で定義するが、その一方で、現在の論理アドレスインターフェイスを介して大容量メモリシステムと通信する場合、バイトをそれぞれ５１２バイトのセクタに、または、それぞれ複数セクタのクラスタにグループ化する。一般的に、このことは、メモリシステムの動作を簡単化するために行われる。本願明細書で説明されているファイルベースのホスト−メモリインターフェイスは何らかの他のデータ単位を用いることができるが、一般的に、最初のホストファイルのバイト粒度が好ましい。すなわち、データオフセットおよび長さなどを、（１つ以上の）セクタまたは（１つ以上の）クラスタなどによるよりはむしろ（１つ以上の）バイトすなわち最小の合理的なデータ単位で表現するのが好ましい。これによって、本願明細書で説明されている技術と共にフラッシュメモリ記憶の容量を効率良く用いることができる。
【００７２】
一般的な既存の論理アドレスインターフェイスでは、ホストは、書き込まれるデータの長さをも指定する。このことも、本願明細書で説明されているファイルベースのインターフェイスを用いて行うことができるが、Ｗｒｉｔｅコマンド（図１２Ａ）を実行する必要がないので、ホストは、書き込まれるデータの長さを供給しないことが好ましい。
【００７３】
図１３Ａに示されているようにメモリに書き込まれた新たなファイルは、次に、データグループに対して一連の索引項目（Ｆ０，Ｄ０），（Ｆ１，Ｄ１）としてこの順序でＦＩＴ内に表される。すなわち、ホストシステムが特定のファイルにアクセスしたいときはいつでも、ホストはｆｉｌｅＩＤまたは他の識別子をメモリシステムに送信し、メモリシステムはＦＩＴにアクセスして、このファイルを構成するデータグループを識別する。個々のデータグループの長さ＜ｌｅｎｇｔｈ＞も、メモリシステムの動作の都合上、個々の項目に含めることができる。使用時、メモリコントローラは、データグループの長さを計算し記憶する。
【００７４】
ホストが、開かれた状態で図１３Ａのファイルを維持する限りは、物理的な書き込みポインタＰも維持して、このファイルに対してホストから受信したさらなるデータを書き込む位置を定義するのが好ましい。ファイルの任意の新たなデータは、ファイル内の新たなデータの論理位置にかかわらず物理メモリのファイルの終わりに書き込まれる。メモリシステムは複数のファイル、例えば４または５個のファイルを同時に開いたままにさせることができ、ファイルごとの書き込みポインタＰを維持する。異なるファイルの書き込みポインタは、異なるメモリブロックの位置を指し示す。開いたファイルの数のメモリシステム限界が既に存在するときにホストシステムが新たなファイルを開きたい場合、開かれたファイルの１つが最初に閉じられ、新たなファイルが次に開かれる。ファイルが閉じられた後、このファイルに対して書き込みポインタＰを維持する必要はもはやない。
【００７５】
図１３Ｂには、以前に書き込まれたが依然として開いた状態の図１３Ａのファイルの終わりにホストによってデータを、Ｗｒｉｔｅコマンド（図１２Ａ）を用いて付加することを示す。このファイルのデータの終わりの第２のブロック１８５にも書き込まれているデータ１８７がホストシステムによってファイルの終わりに追加されると示されている。既存のデータグループ１８４と、付加されたデータ１８９との間で論理アドレスにも物理アドレスにも途切れが存在しないので、付加されたデータはデータグループ（Ｆ１，Ｄ１）の一部となり、従って、データグループ（Ｆ１，Ｄ１）は、より多くのデータを含むことになる。従って、完全なファイルは、ＦＩＴ内で一連の索引項目（Ｆ０，Ｄ０），（Ｆ１，Ｄ１）として依然として表される。また、ポインタＰのアドレスは、記憶された付加されたデータの終わりのアドレスに変更される。
【００７６】
以前に書き込まれた図１３Ａのファイルへデータ１９１のブロックを挿入する一例を図１３Ｃに示す。ホストは、データ１９１をファイルに挿入するが、メモリシステムは、挿入されたデータを、以前にデータが書き込まれたファイルの終わりにある位置１９３に付加する。データが、開いたファイルにデータが挿入されているとき、ファイルのデータを論理順に再度書き込む必要はない。しかし、このことを、ホストがファイルを閉じた後、バックグラウンドで行うことができる。挿入されたデータは、第２メモリブロック１８５内に完全に記憶されるので、単一の新たなグループ（Ｆ１，Ｄ３）を形成する。しかし、この挿入を行うことによって、結果として、図１３Ａの以前のデータグループ（Ｆ０，Ｄ０）は２つのグループ、すなわち、挿入前のデータグループ（Ｆ０，Ｄ０）と挿入後のデータグループ（Ｆ２，Ｄ１）とに分割される。その理由は、挿入の始まりＦ１と挿入の終わりＦ２とで生じるようなデータの論理的な途切れが存在するときはいつでも、新たなデータグループを形成する必要があるためである。グループ（Ｆ３，Ｄ２）は、第２のブロック１８５の始まりである物理アドレスＤ２の結果である。グループ（Ｆ１，Ｄ３）およびグループ（Ｆ３，Ｄ２）は、それらが同じメモリブロックに記憶されているとしても別々に維持される。その理由は、それらに記憶されたデータのオフセットに途切れがあるためである。挿入部分を有する原ファイルは、メモリシステムＦＩＴ内にデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ１，Ｄ３），（Ｆ２，Ｄ１），（Ｆ３，Ｄ２）によってこの順序で表される。図１３Ａ、図１３Ｂおよび図１３Ｃの例から、新たなファイルまたは既存のファイルの新たなデータを、メモリ内のデータのいずれをも古い状態にしないで書き込むことができることに留意すべきである。すなわち、ＷｒｉｔｅコマンドおよびＩｎｓｅｒｔコマンド（図１２Ａ）の実行によって、他のいかなるデータをも無効または古くさせることはない。
【００７７】
図１３Ｄには、別の例を示す。図１３Ａに示されているように最初に書き込まれたデータの特定部分は、Ｕｐｄａｔｅコマンド（図１２Ａ）を用いて更新される。データファイルの部分１９５は更新されたと示されている。更新情報を用いて全部のファイルをメモリシステムに再度書き込むよりはむしろ、ファイルの更新された部分１９７は、以前に書き込まれたデータに付加される。以前に書き込まれたデータの部分１９９は、もう古い。古いデータによって占められた空間を開放するため、一般的に、更新されたファイルを統合するのが望ましいが、ホストが、開かれたファイルを維持している間、一般的にファイルの統合が行われないのではなくむしろ、ファイルが閉じられた後にバックグラウンドで行うことができる。更新後、ファイルは、メモリシステムＦＩＴ内にデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ１，Ｄ３），（Ｆ２，Ｄ１），（Ｆ３，Ｄ２）によってこの順序で表される。図１３Ａの単一のデータグループ（Ｆ０，Ｄ０）は、図１３Ｄの部分、すなわち、更新された部分よりも前の部分と、更新された部分と、更新された部分よりも後の部分とにこの場合も分割される。
【００７８】
可変長のデータグループの使用をさらに示すため、同一のファイルを含む一連の幾つかの書き込み動作を、図１４〜図１４Ｅによって順々に示す。図１４Ａに示されているように最初に原ファイルデータＷ１は、Ｗｒｉｔｅコマンド（図１２Ａ）を用いてメモリシステムの２つのブロックに書き込まれる。次に、ファイルは２つのデータグループによって定義される。第１のグループは物理メモリブロックの始まりで開始し、第２のグループは物理メモリブロック境界の後で必要とされる。従って、図１４Ａのファイルは、一連のデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ１，Ｄ１）によって記述される。
【００７９】
図１４Ｂでは、図１４Ａにおいて書き込まれたファイルデータは、Ｕｐｄａｔｅコマンド（図１２Ａ）を用いて更新される。更新されたファイルデータＵ１は以前のグループ（Ｆ１，Ｄ１）の直後に書き込まれ、更新されたデータの前バージョンは古くなる。図１４Ａの以前のグループ（Ｆ０，Ｄ０）は、図１４Ｂの修正されたグループ（Ｆ０，Ｄ０）に短縮され、以前のグループ（Ｆ１，Ｄ１）は、グループ（Ｆ４，Ｄ２）に短縮される。更新されたデータは、それらがメモリブロックの境界に重なり合うので２つのグループ（Ｆ２，Ｄ３）および（Ｆ３，Ｄ４）に書き込まれる。データの一部は、第３のメモリブロックに記憶される。ファイルは、一連のデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ２，Ｄ３），（Ｆ３，Ｄ４），（Ｆ４，Ｄ２）によって記述されようになる。
【００８０】
図１４Ｂのファイルは、Ｉｎｓｅｒｔコマンド（図１２Ａ）を用いて新たなファイルデータＩ１の挿入によって図１４Ｃにおいてさらに変更される。挿入されたデータがメモリブロックの境界に重なり合うので、新たなデータＩ１は、図１４Ｂの以前のグループ（Ｆ４，Ｄ２）の直後に、図１４Ｃの新たなグループ（Ｆ５，Ｄ６）および（Ｆ６，Ｄ７）としてメモリに書き込まれる。第４のメモリブロックが用いられる。図１４Ｂの以前のグループ（Ｆ０，Ｄ０）は、新たなデータＩ１の挿入のため、図１４Ｃにおいて、短縮されたグループ（Ｆ０，Ｄ０）および（Ｆ７，Ｄ５）に分割される。ファイルは、一連のデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ５，Ｄ６），（Ｆ６，Ｄ７），（Ｆ７，Ｄ５），（Ｆ８，Ｄ３），（Ｆ９，Ｄ４），（Ｆ１０，Ｄ２）によって記述されるようになる。
【００８１】
図１４Ｄには、Ｗｒｉｔｅコマンド（図１２Ａ）を用いて新たなデータＷ２をファイルの終わりに付加する図１４Ｃのデータファイルのさらなる変更を示す。新たなデータＷ２は、図１４Ｄの新たなグループ（Ｆ１１，Ｄ８）として図１４Ｃの以前のグループ（Ｆ１０，Ｄ２）の直後に書き込まれる。ファイルは、一連のデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ５，Ｄ６），（Ｆ６，Ｄ７），（Ｆ７，Ｄ５），（Ｆ８，Ｄ３），（Ｆ９，Ｄ４），（Ｆ１０，Ｄ２），（Ｆ１１，Ｄ８）によって記述されるようになる。
【００８２】
開いたファイルの第２の更新を図１４Ｅに示す。更新されたファイルデータＵ２は、ホストがＵｐｄａｔｅコマンド（図１２Ａ）を送出することによって図１４Ｄのファイルに書き込まれる。図１４Ｅにおいて、更新されたデータＵ２は、図１４Ｄの以前のグループ（Ｆ１１，Ｄ８）の直後に書き込まれ、このデータの前バージョンは古くなる。図１４Ｄの以前のグループ（Ｆ９，Ｄ４）は、図１４Ｅの修正されたグループ（Ｆ９，Ｄ４）に短縮され、以前のグループ（Ｆ１０，Ｄ２）は完全に古くなり、以前のグループ（Ｆ１１，Ｄ８）は、新たなグループ（Ｆ１４，Ｄ９）を形成するように短縮される。ブロック境界に重なり合う更新されたデータは、図１４Ｅの新たなグループ（Ｆ１２，Ｄ１０）および（Ｆ１３，Ｄ１１）に書き込まれる。次に、第５のブロックはファイルを記憶するのに必要とされる。ファイルは、一連のデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ５，Ｄ６），（Ｆ６，Ｄ７），（Ｆ７，Ｄ５），（Ｆ８，Ｄ３），（Ｆ９，Ｄ４），（Ｆ１２，Ｄ１０），（Ｆ１３，Ｄ１１），（Ｆ１４，Ｄ９）によって記述されようになる。
【００８３】
前述した説明に従ってファイルを生成または変更した後、各ファイルのデータのオフセットを正しい論理順序で連続して維持するのが好ましい。従って、例えば、Ｉｎｓｅｒｔコマンドを実行する一部として、ホストによって供給された挿入されたデータのオフセットは、挿入の直前にあるオフセットと、挿入されたデータの量だけ挿入が増加された後のファイル内に既にあるデータとから連続する。一般的に、Ｕｐｄａｔｅコマンドは、同量の更新されたデータによって置き換えられる既存のファイルの所定のアドレス範囲内にデータを生じさせ、これによって、一般的に、ファイルの他のデータのオフセットを置き換える必要はない。別個のＵｐｄａｔｅコマンドの代わりに、Ｗｒｉｔｅコマンドを用いることによってもファイルのデータを更新することができる。その理由は、記憶されたファイルデータに既に存在するオフセットの範囲を有するホストからのデータの受信を、メモリシステムによって、このオフセットの範囲内でデータを更新する命令と解釈することができるためである。
【００８４】
図１３および図１４によって示されている前述したデータ割り当ておよび索引付け機能のすべてがメモリシステムのコントローラによって実行されることに留意すべきである。ホストは、図１２ＡのＷｒｉｔｅ、ＩｎｓｅｒｔまたはＵｐｄａｔｅコマンドの１つと一緒に、メモリシステムに送信されるｆｉｌｅＩＤおよびファイル内のデータのオフセットを伝達するだけである。メモリシステムは残りの部分を行う。
【００８５】
今述べたようにホストからフラッシュメモリにファイルデータを直接に書き込む利点は、このように記憶されたデータの粒度または分解能を、ホストにおけるデータの粒度または分解能と同じように維持できるということである。例えば、ホストアプリケーションがファイルデータを１バイトの粒度で書き込む場合、このデータを１バイトの粒度でフラッシュメモリにも書き込むことができる。次に、個々のデータグループのデータの量および位置はバイトの数で測定される。すなわち、ホストアプリケーションファイル内に別々にアドレス可能であるデータの同一オフセット単位は、フラッシュメモリ内に記憶されたときにもファイル内で別々にアドレス可能である。従って、ブロック内の同一ファイルのデータグループの間の境界は、索引テーブル内で、最も近いバイトまたは他のホストオフセット単位で指定される。これと同様に、ブロック内の異なるファイルのデータグループの間の境界は、ホストオフセットの単位で定義される。
【００８６】
Ｄｅｌｅｔｅコマンドはデータを書き込むのには用いられないが、Ｄｅｌｅｔｅコマンドの使用を考慮することは、ファイルの一部を削除することに関連する。その理由は、このような動作がＩｎｓｅｒｔコマンドの逆であるためである。以下のフォーマットすなわちＤｅｌｅｔｅ  ＜ｆｉｌｅＩＤ＞  ＜ｏｆｆｓｅｔ＞  ＜ｌｅｎｇｔｈ＞を用いてＤｅｌｅｔｅコマンドをファイルオフセットアドレスの範囲に適用することができる。＜ｏｆｆｓｅｔ＞から始まり、このアドレスから削除の＜ｌｅｎｇｔｈ＞の間継続するファイルの部分のデータは削除される。次に、削除後のファイルの残りのデータのオフセットアドレスは、ファイルを通じて連続するオフセットアドレスを維持するために、その値はホストによって減少される。このことは、ホストがデータをファイルの中間に追加し、挿入後に残りのファイルデータのオフセットの値を増加させ、これによって変更されたファイルのオフセットが連続するＩｎｓｅｒｔコマンドの逆である。
【００８７】
ガーベッジコレクション
図１４Ｂおよび図１４Ｅから留意すべきことは、Ｕｐｄａｔｅコマンドが、ファイルのデータ量よりも大きいファイルを記憶するのに必要な物理空間を生じさせるということである。その理由は、更新によって置き換えられたデータがメモリに記憶されたままであるためである。従って、古い無効なデータを削減することによってファイルのデータを少ない物理記憶空間に統合すること（ガーベッジコレクション）が極めて望ましい。従って、より多くの記憶空間が他のデータに利用可能になる。
【００８８】
図１４Ｂおよび図１４Ｅのファイルデータの更新に加えてさらに留意すべきことは、図１４Ｃのデータの挿入が、狂った順序で記憶されたファイルデータを生じさせるということである。すなわち、更新および挿入は、このことが行われる時点でメモリに記憶されたファイルの終わりに追加され、その一方で、ほとんど常に、ファイル内のどこかに論理的に配置される。このことは、図１４Ｂ、図１４Ｃおよび図１４Ｅの例の場合である。従って、ファイル内のオフセットの順序を一致させるように、メモリに記憶されたファイルのデータを再配列するのが望ましい。従って、このことは、ページおよびブロックを順序どおりに読み出すことがファイルのデータをオフセット順序に与えることになるので、記憶されたデータを読み出す速度を改善する。また、このことは、ファイルの最大可能なデフラグを行う。しかし、より効率良く読み出しを行うファイルデータの再配列は、他のデータを記憶するのに用いる１つ以上のメモリブロックを解放する可能性があるファイルデータの統合ほどメモリシステムの性能にとって重要ではない。従って、ファイル内のデータの再配列は、それ自体によって一般的に行われず、その利益は、動作オーバーヘッドを追加する価値がない。しかし、追加された動作オーバーヘッドをほとんど持たない多くのガーベッジコレクション動作の一部としてファイル内のデータの再配列を行うことができる。
【００８９】
２つのデータ更新Ｕ１，Ｕ２が行われたので、図１４Ｅのファイルは、メモリに記憶された古いデータグループ（ぼかし部分）を含む。結果として、図１４Ｅから明らかなように、ファイルを記憶するのに用いられるメモリ容量の量は、ファイルの大きさよりもかなり大きい。従って、ガーベッジコレクションは適している。図１５には、図１４Ｅのデータファイルのガーベッジコレクションの結果を示す。ガーベッジコレクション動作前、このファイルはほぼ５つのブロックの記憶容量を占め（図１４Ｅ）、ガーベッジコレクション動作後の同じファイルは、３つをわずかに上回るメモリセルブロック内に適合する（図１５）。ガーベッジコレクション動作の一部としてデータは、データが最初に書き込まれたブロックから他の消去済みブロックへコピーされ、次に、元のブロックは消去される。ファイル全体がデータ収集される場合、ファイル内のデータ論理オフセット順序と同じ物理順序を付けてデータを新たなブロックへコピーすることができる。例えば、更新Ｕ１，Ｕ２および挿入Ｉ１は、それらがホストファイルに現れるのと同じ順序でガーベッジコレクション（図１５）後に記憶される。
【００９０】
一般的に、ガーベッジコレクションは、ファイルが統合される新たな異なるデータグループの形成をも生じさせる。図１５の場合、ファイルは、新たな一連の新たなデータグループ索引項目（Ｆ０，Ｄ０），（Ｆ１，Ｄ１），（Ｆ２，Ｄ２），（Ｆ３，Ｄ３）によって記述される。これは、図１４Ｅに示されているファイルの状態で存在するデータグループの数よりもかなり少ない。ファイルのデータがコピーされたメモリセルブロックごとに１つのデータグループが存在するようになる。ガーベッジコレクション動作の一部として、ファイル索引テーブル（ＦＩＴ）は、ファイルを形成する新たなデータグループを反映するように更新される。
【００９１】
ファイルがガーベッジコレクションの候補である場合、このファイルのＦＩＴデータグループ項目は、ファイルがガーベッジコレクションの設定基準を満たすかどうかを決定するために検査される。また、ファイルのデータを含むメモリセルブロックのいずれも古いデータを含む場合、ガーベッジコレクションは開始する。メモリセルブロックのいずれかが古いデータを含まない場合、ガーベッジコレクションは必要とされない。図１４Ｅのファイルが古いデータを含むことは、前に示された一連のデータグループ索引項目から明らかである。例えば、ファイルデータが記憶された最初の２つのブロックに古いデータが存在する２つの連続するデータグループ（Ｆ７，Ｄ５）および（Ｆ８，Ｄ３）から見て分かる。物理アドレス位置Ｄ５とＤ３との差は、論理オフセットＦ７とＦ８との差よりもかなり大きい。データが論理オフセット順に記憶されなかったファイル索引データグループ項目からも明らかである。あるいはまた、ファイルの個々のＦＩＴ項目は、古いと参照が付けられたこのファイルの古いデータグループのレコードを保持することができる。従って、コントローラは、ファイルごとにＦＩＴ項目を簡単に走査して、いかなる古いデータグループおよびそれらが記憶されている物理ブロックをも識別することができる。
【００９２】
ホストは、さらなる古いデータを生成し、かつ／または、狂った論理オフセット順序でデータを記憶する更新または挿入をファイルに行い続けることがあるので、一般的に、開いたファイルについてガーベッジコレクションを実行すべきではない。従って、多くのこのようなガーベッジコレクション動作に帰着することがある。しかし、消去済みプールブロックの数が設定レベルを下回る場合には、開いたファイルのガーベッジコレクションは、新たなデータを記憶するため、または他の動作のために充分な消去済みブロックを備えるのに必要とされることがある。
【００９３】
ホストによってファイルを閉じることは、一般的に、このファイルに考慮すべきガーベッジコレクションを生じさせる。ファイルが閉じられた直後にガーベッジコレクションを実行するのではなくむしろ、閉じられたファイルが現在のメモリ動作と干渉しないとき、閉じられたファイルにバックグラウンドでガーベッジコレクションを行うように、閉じられたファイルをメモリコントローラによってスケジュールすることが好ましい。ガーベッジコレクション待ち行列を保持することができる。ファイルが閉じられた後にファイルが待ち行列に追加され、次に、行うべき優先順位の高いメモリシステム動作が他にない場合、待ち行列内で最も長いファイルは、メモリコントローラによって選択され、必要に応じてガーベッジコレクションが行われる。このような選択およびガーベッジコレクション動作を、例えば、ホストからのＩｄｌｅコマンド（図１２Ｄ）の受信に応答して行うことができる。
【００９４】
データのコピーは、ガーベッジコレクションの最も時間の要する部分であるので、大きいファイルの場合は特に、どの時点においても短いバーストでファイルのデータの一部分だけをコピーすることによってタスクを構成要素に分割することができる。次に、このような部分的ファイルコピーを他のメモリ動作と交互に行うことができ、ホストがデータをメモリシステムとの間でやり取りしている間でも行うことができる。ある指定された数を下回る消去済みブロックの数に応答して個々のコピーデータバーストの長さを増大させることもできる。
【００９５】
目標は、全体としてバックグラウンドで、ホストシステムとの間でデータを転送する主な動作と干渉することなしに、または、この主な動作を減速することなしにガーベッジコレクションを実行することである。しかし、このことは常に可能とは限らず、特に、新たなデータをプログラムするために消去済みブロックプール内で利用できる消去済みブロックの数が何らかの事前設定の最小値に満たなくなる場合には可能でない。従って、ガーベッジコレクションに優先順位が構成され、優先順位のとおりに待ち行列内のファイルにガーベッジコレクションをフォアグラウンドで行ってデータを統合し、これによって、新たなデータをホストシステムから受信するのに追加の消去済みブロックを利用することができる。待ち行列内にファイルがない場合、開いたファイルにガーベッジコレクションを行わなければならないことがある。ガーベッジコレクションが優先事項になると、一般的に、ホストはビジーステータス信号をメモリシステムから受信し、従って、適切な数の消去済みブロックが再び存在するまで、新たなデータのいかなるプログラミングも中断する。その一方で、充分な数以上の消去済みプールブロックがある場合、ガーベッジコレクション動作の頻度を減少させることができ、メモリシステムの性能に影響を及ぼすことがあるガーベッジコレクションを延期することができる。
【００９６】
ホストデータファイルにガーベッジコレクションが実行されることに留意すべきである。ファイルの状態に応答してファイルにガーベッジコレクションが開始される。ガーベッジコレクションが開始されると、ＦＩＴ内のファイルの全データグループの索引項目は、処理の一部として検査される。ファイルにガーベッジコレクションが行われると、データは、ファイルのデータグループ索引項目で指定された順序で既存のブロックから、新たに開かれたコピーブロックへ１つのデータグループで同時にコピーされる。このことは、全体として個々のメモリセルブロックの状況に基づく既存のフラッシュメモリガーベッジコレクションと対照をなしている。
【００９７】
しかし、古いデータをも含むファイルのデータを記憶する個々のブロックだけにガーベッジコレクションが行われることが原則である。つまり、ファイルのデータを記憶するブロックのすべてにガーベッジコレクションが行われるわけではない。例えば、ファイルが２つだけのブロックに記憶され、第１のブロックが古いデータを含み、第２のブロックが古いデータを含まない場合、第１のブロックにガーベッジコレクションが行われるが、第２のブロックのデータはそのままにされる。有効データは、第１のブロックから消去済みコピーブロックへコピーされ、従って、コピーブロックは、古いデータの量ぐらい使い残った幾つかの消去済みページまたは他の容量を有する。１つのブロックに満たない消去済み記憶容量の使用を以下で説明する。図１４Ｅの例では、ガーベッジコレクション動作前のメモリ空間は、ファイルのデータを含む５つのブロックのうち４つの各ブロックに古いデータ（ぼかし領域）を有する。
【００９８】
古いデータを含むブロックだけにガーベッジコレクションを行うという原則の変更例として、所定のファイルにガーベッジコレクションが行われるということが決定された後、部分的に満たされたブロック内のファイルのデータのいずれも、ガーベッジコレクション動作に含まれる。従って、図１４Ｅの第５のブロック内のＵ２データは、このブロックに古いデータがなくてもガーベッジコレクション動作に含まれる。５つのすべてのブロック内のデータは、４つの消去済みブロックへコピーされることによって同時に統合される。その理由は、第５のブロックにデータを含まないことで、結果として生じる４つのコピーブロックの２つは、部分的にだけデータで満たされることになるためである。図１５の場合、１つだけのコピーブロックが部分的に満たされたままである。メモリ性能は、部分的に用いられるブロックが少ないことによって改善される。
【００９９】
ホストシステムによって送出された図１２Ｂの特定のファイルコマンドはガーベッジコレクションを開始することができる。ファイルのＣｌｏｓｅコマンドの受信は既に説明した。閉じたファイルは、ガーベッジコレクションを行うために待ち行列に配置される。ＤｅｌｅｔｅおよびＥｒａｓｅコマンドもガーベッジコレクションを行うことになる。ファイルの削除によって、古いファイルデータを含むブロックをガーベッジコレクションの待ち行列に配置する。削除済みファイルにガーベッジコレクションを行う効果は、削除済みファイルに有効データがなく、従って、データを他のブロックへコピーすることは行われないということである。削除済みファイルのデータだけを含むブロックのすべては、ガーベッジコレクション処理の一部として単に消去される。消去済みファイルの古いデータだけを含むブロックのガーベッジコレクションを、例えば、ブロックをガーベッジコレクション待ち行列の先頭に配置することによって直ちにまたは優先的に行うことができること以外、Ｅｒａｓｅコマンドは類似の効果を有する。
【０１００】
今、説明している直接ファイル記憶システムの重要な利点は、ファイルを削除するためのＤｅｌｅｔｅコマンドがメモリシステムに直接送出されるため、ホストがファイルを削除する時点をメモリが直ちに分かるということである。次に、メモリコントローラは、メモリの他の動作に悪影響を及ぼすことなしに、削除済みファイルのデータを記憶するブロックを消去することができれば直ちに消去することができる。その後、消去済みブロックは、新たなデータを記憶することに利用される。
【０１０１】
説明している実施例では、ファイルを削除または消去するコマンドによって、直接応答としてこのファイルのデータを消去する。その一方で、一般的な論理ベースのインターフェイスでは、このようなコマンドはメモリコントローラに直接に到達しない。むしろ、ホストは、削除済みまたは消去済みファイルによって占有されたメモリ論理アドレス空間の特定のセグメントだけを解放する。ホストが後でデータをこれら同一の論理アドレスの１つ以上に書き込むときだけ、メモリシステムは、再使用された論理アドレスセグメントのデータが古くなっていることが分かる。メモリは、ファイルによって占有された他の論理アドレスセグメントのデータが削除または消去されたことを依然として分からない。メモリは、ホストがデータを他の論理アドレスに書き込むときだけ、論理セグメントに以前書き込まれたデータが古くなっているということが分かる。
【０１０２】
共通ブロック
ファイルが閉じられ、ファイルにガーベッジコレクションが行われると、ファイルデータの一部がメモリセルブロックの一部だけを占有することがあるのは、連続的なブロックを単一ファイルのデータで満たした結果である。さらに、小さいファイルのデータは、ブロック全体を満たさないことさえある。この結果、１つのファイルのデータを１つのブロックに記憶できるとしても、個々のブロックのかなりの量の空間が未使用となる。個々のブロック内のページの記憶容量は消去されたままであり、データを記憶するのに利用可能ではあるが、使用されない。
【０１０３】
従って、他のブロックがいっぱいになった後、幾つかのメモリセルブロックは、２つ以上の各ファイルから少量のデータ、すなわち、全体に小さいファイルおよび／または使い残った残留ファイルデータのどちらか一方を記憶するのが望ましい。残留ファイルデータは、ブロック全体を占有しない閉じられたファイルのデータであって、１つ以上のデータグループを含むことがある。ファイルマップは、ブロック内のすべてのデータグループが１つのファイルのすべてであるかのように単一メモリセルブロック内の２つ以上のファイルのデータグループを追跡し続けることができる。個々のデータグループのマップは、データグループが一部であるｆｉｌｅＩＤを含む。共通ブロックを用いる主な目的は、前述したようにファイルのデータをメモリに書き込むことによって生じることがある未使用の物理メモリ記憶容量を最小限にすることである。最も一般的には、ファイルのガーベッジコレクションによって生じる１つ以上のデータグループの残留データは、ガーベッジコレクションの一部として共通ブロックに書き込まれる。一例として、図１５のガーベッジコレクションが行われたファイルが挙げられ、最後のデータグループ（Ｆ３，Ｄ３）は、最後のブロックのごく一部だけを占有する。このようにデータが残留した場合、この最後のブロックの大部分は未使用になる。図１５のデータグループ（Ｆ３，Ｄ３）を、別の１つ以上のファイルから１つ以上のデータグループを含む共通ブロックに書き込むことができ、または、この最後のメモリブロックを共通ブロックとして指定することができる。後者の場合、１つ以上の他のファイルからのデータグループはこの同じブロックにその後書き込まれる。
【０１０４】
あるいはまた、指定された共通ブロックのうちの１つ内の消去済み空間に適合する量であると残留データの量が知られている場合、ガーベッジコレクション中、残留ファイルデータをホストから共通ブロックに直接に書き込むことができる。Ｃｌｏｓｅ＿ａｆｔｅｒコマンド（図１２Ｂ）を用いて残留ファイルデータを識別することができ、これによって、完全に満たされていない消去プールブロックに残留ファイルデータを書き込むというよりはむしろ、コマンドの一部として指定されたデータの量を記憶するのに充分な空間を有する開いた共通ブロックに残留ファイルデータを書き込むことができる。このことは、その後のガーベッジコレクション動作中、残留データをコピーする必要性を削減することができる。
【０１０５】
新たなデータファイルがメモリにプログラムされる場合、図１３Ａに示し、かつ前述したデータの書き込み方法に代わるものとして、１つ以上の他のファイルに対して残留データを含む開いた共通ブロックに、ブロック内の最初の利用可能な物理位置から始まってブロックの位置を連続的に順々に進行してデータを書き込むことができる。ホストがファイルに対してＯｐｅｎコマンドを送信し、その直後にＣｌｏｓｅ＿ａｆｔｅｒコマンドを送信し、その後にファイルのデータを送信する場合、ファイルの完全なデータが、開いた共通ブロック内に適合でき、開いた共通ブロックの終わりに達する前にファイルが閉じられることを決定することができる。また、ファイルデータの長さが未知であっても、新たなファイルのデータを、開いた共通ブロックに書き込むことができる。
【０１０６】
従って、２つ以上の異なるファイルの共通データグループを記憶するため、多くの共通ブロックをメモリシステムに維持するのが好ましい。共通データグループは、１バイトの粒度を有するブロックの記憶容量のデータまでの大きさを有することができる。共通ブロックの１つだけは所定のファイルのデータを含むのが好ましいが、ファイルの２つ以上のデータグループを含むことができる。しかも、共通データグループを、１つだけの共通ブロックに記憶し、記憶のために複数の共通ブロックに分割しないことが好ましい。このことは、データグループが古くなった場合、複数の共通ブロックにおけるガーベッジコレクションを回避する。共通ブロック内のデータグループが古くなると、共通ブロックにはガーベッジコレクションが課せられる。このような共通ブロック内の（１つ以上の）残りの有効データグループのいずれも、別の共通ブロック内の利用可能な消去済み空間、または消去済みプールブロックに書き込まれ、その後、共通ブロックは消去される。ガーベッジコレクションが行われる共通ブロックが、異なるファイルから２つ以上の有効データグループを含む場合、それらを同時に保持する必要はなくむしろ、異なるブロックへコピーすることができる。
【０１０７】
図１６には、３つの異なるデータファイルの各々から共通データグループでプログラムされた共通ブロックの一例を示す。データの書き込みが、ブロックの一端のページから他の端のページへ進行するように一般的なＮＡＮＤアレイにおいて制約されているので、データグループは、互いに隣接するように記憶される。ブロックの一端にある空白は、いかなるデータも書き込まれていないブロックのページを示す。利用可能なデータグループを完全に共通ブロック全体に適合させることは困難である。
【０１０８】
２つ以上のファイルの残留データを書き込むことができる開いた共通ブロックとしてメモリシステムによって指定されたブロックの数は、一般的にごくわずかであるが、ガーベッジコレクションが行われる多数のファイルが、任意の既存の開いた共通ブロック内の利用可能な空間に適合しない残留ファイルデータを有する場合には多くなることがある。残留ファイルデータは、メモリ容量全体を最も良く使用する開いた共通ブロックのうちの１つ内に書き込まれる。開いた共通ブロックのいずれかに充分でない消去済み空間が存在する場合、既存の共通ブロックのうちの１つは閉じられ、その代わりに別の共通ブロックが開かれる。あるいはまた、既存の開いた共通ブロックを閉じる必要がなく、開いた共通ブロックの数を増大させることができる。新たな共通ブロックは、消去済みプールブロックのうちの１つとして指定することができるが、好ましくは、利用可能な場合に、残留ファイルデータグループ（Ｆ３，Ｄ３）だけを含む図１５の最後のブロックのような一部の残留ファイルデータを既に含む不完全に書き込まれたブロックとする。しかし、共通ブロックのガーベッジコレクションの場合、消去済みプールブロックを、必要な場合に新たな共通ブロックとして指定するのが好ましい。
【０１０９】
図１７には、別のファイルから残留データの１つ以上のデータグループを既に含んでいる５つの残留または共通単位（各々異なるブロックまたはメタブロック）が存在する場合に残留ファイルデータを書き込む例示的な処理を示す。図１５のガーベッジコレクションが行われたファイルによって生じる最後のデータグループ（Ｆ３，Ｄ３）は、このような残留ファイルデータの一例である。しかし、このような残留ファイルデータは、単一ファイルから２つ以上のデータグループを含むことができる。３つの可能性を示す。残留単位２が、最も多くの利用可能な消去済み空間を有するので、第１の可能性（Ａ）は残留データを残留単位２に書き込む。残留単位５が５つの残留単位のうちで最も良く適合するので、第２の可能性（Ｂ）は残留ファイルデータのために残留単位５を選択する。残留ファイルデータは単位５をほとんど満たし、従って、単位２内で利用できる大容量空間を、大量のデータを将来受信するために残す。単位１、単位３または単位４のいずれにも、残留データを獲得するのに充分な空間が存在しないので、これらの単位は直ちに除外される。
【０１１０】
第３の可能性（Ｃ）は残留ファイルデータを消去プールからブロックまたはメタブロック単位に書き込む。残留ファイルデータが、完全に消去された単位に書き込まれた後、この単位は残留単位になり、後でメモリシステムコントローラによって共通ブロックとして開くことができる。図示の例では、残留単位２または残留単位５に残留ファイルデータのための空間があるので、一般的に可能性（Ｃ）は用いられない。
【０１１１】
あるいはまた、異なる共通ブロックに記憶するため、ファイルの残留データを２つ以上の部分に分割させることができる。例えば、既存の開いた共通ブロックのいずれも、特定のファイルの残留データを記憶するのに充分に利用可能な空間を持つことができず、消去済みブロックのいずれも、残留ファイルデータの新たな共通ブロックとして開けるために利用することができない。この場合、２つ以上の開いた共通ブロック間で残留ファイルデータを分割することができる。
【０１１２】
共通ブロックがデータでいっぱいになる前に共通ブロックを閉じることができる。前述したように、利用可能な最小量の消去済み空間を有する開いた共通ブロックは、一般的に、別の共通ブロックを開けてファイルの所定量の残留データを記憶することが必要とされるときに閉じられる。一部において、このことは、異なる共通ブロックに記憶するためにファイルの残留データが分割されない場合、好適な動作の結果である。メモリシステムが、Ｓｉｚｅコマンド（図１２Ｅ）に応答することによって新たなデータの利用可能なメモリ記憶空間の量をホストに報告する場合、閉じられた共通ブロックのこれらの少量の未使用容量は、それらが直ちに使用可能でないので含まれない。
【０１１３】
削除または消去された部分であるファイルが原因で、残留ファイルデータが古くなるので、共通ブロック内のデータも統合される。例えば、理由のいかんにかかわらず、共通ブロック内の残留ファイルデータが古いと指定されたときはいつでも、このブロックは、前述した古いファイルデータブロック待ち行列、または別の待ち行列に追加される。ファイルに対するホストＤｅｌｅｔｅコマンドのため、データが古くなった場合、共通ブロックは待ち行列の終わりに配置される。しかし、このことがＥｒａｓｅコマンドによって生じる場合、共通ブロックは待ち行列の先頭に入るか、さもなければ、ガーベッジコレクションの優先順位が与えられる。
【０１１４】
メモリシステムの動作中、コントローラによって維持される５つの異なるガーベッジコレクション待ち行列、すなわち、
（１）古いブロック、すなわち、ファイルに対するＥｒａｓｅコマンド（図１２Ｂ）の結果として古いデータだけを含むブロックの優先待ち行列、
（２）ファイルに対するＥｒａｓｅコマンドによって古い状態にされたデータを含み、しかも、幾つかの有効データを含む共通ブロックの優先待ち行列、
（３）ＵｐｄａｔｅまたはＤｅｌｅｔｅコマンド（図１２Ａおよび図１２Ｂ）の実行によって、または、ガーベッジコレクション中、すべての有効データが別のブロックへコピーされたために生じる古いブロック（古いデータだけを含むブロック）の待ち行列、
（４）Ｄｅｌｅｔｅコマンドまたは古いデータが共通ブロックに存在するというガーベッジコレクション中の検出に応答する、幾つかの古いデータを含み、しかも、有効データを含む共通ブロックの待ち行列、
（５）ＣｌｏｓｅまたはＣｌｏｓｅ＿ａｆｔｅｒコマンドが受信されるファイルの待ち行列を、単一の待ち行列の代わりにすることができ、最初の２つの待ち行列の項目には、優先順位が与えられる。これら５つの待ち行列に、前に挙げた順に優先順位を与えることができる。待ち行列（１）の全項目には、待ち行列（２）の項目よりも前にガーベッジコレクションが行われる。ブロックは、ＤｅｌｅｔｅコマンドによるよりはむしろＥｒａｓｅコマンドによってこれらブロックのデータの全部または一部が古い状態にされたため、優先待ち行列（１）および（２）にリストされる。ブロックおよびファイルは、メモリシステムの動作中に識別された順に各待ち行列に追加され、各待ち行列内の最も古いブロックおよびファイルに、最初にガーベッジコレクションが行われる（先入れ先出しすなわちＦＩＦＯ）。
【０１１５】
待ち行列（４）および（５）にリストされた項目の優先順位はほぼ同じであり、従って、逆にすることができる。あるいはまた、設定基準に従って、場合によっては、優先順位の高い待ち行列の１つ以上が空になる前であっても、ファイルおよびコマンドブロックが待ち行列（４）および（５）から選択されるさらに複雑な優先順位システムにすることができる。共通ブロックのガーベッジコレクションを管理する２つの目標がある。一方は、共通ブロック内のデータグループが古くなったときに共通ブロックのガーベッジコレクションによって生じるメモリシステムの正常な動作の中断を最小限にすることである。他方は、ブロックのガーベッジコレクション中、共通ブロックからのデータグループが再配置されるとき、更新の索引付けを最小限にすることである。
【０１１６】
共通ブロックのガーベッジコレクション中、ブロック内に残っている共通グループの有効データのすべては、空間を有する共通ブロックの１つに１つずつコピーされる。開かれた共通ブロックに、共通グループがコピーされる空間がない場合、共通グループは、消去プールからブロックに書き込まれ、このブロックを次に共通ブロックとして指定することができる。開かれた共通ブロックの１つは次に一般的に処理の一部として閉じられる。すべてのガーベッジコレクション動作でのように、ファイル索引テーブル（ＦＩＴ）は、コピーされたデータグループの新たな記憶位置を反映するように更新される。
【０１１７】
ガーベッジコレクション待ち行列を不揮発性メモリに記録する必要がある。待ち行列情報を含むページまたはメタページに対する読み出し−変更−書き込み動作を実行して、項目を追加または除去する必要がある。ガーベッジコレクション待ち行列情報を含むページを、専用のブロックまたはメタブロック内に入れることができ、または、ブロックまたはメタブロックを、スワップブロックのような他の種類のページと共有することができる。
【０１１８】
メタページのバッファリングおよびプログラミング中のメタページの使用
前述したものは、メモリセルブロックがメタブロックとして互いに結合されているかどうかを問わず、メモリシステムの動作について説明した。ホストとメモリシステムとの間のファイルベースのインターフェイスと、前述した関連のメモリシステム動作とは、メタブロックを用いるメモリシステム内でも、メタブロックを用いないメモリシステム内でも動作する。同時に書き込み、読み出されるデータの量（並列性の度合い）を増大させる傾向は間違いなくあり、その理由は、この並列性の度合いを増大させることがメモリ性能を直接に改善するためである。多数のデータビットで表す個々のメモリセルブロックの有効幅は、２つ以上のこのようなブロックの形態を成すメタブロックの使用によって増大される。
【０１１９】
図３に関して、例えば、単一ブロック内の各ワード線に沿っているメモリセルのすべてを、各行内の５１２バイトのユーザデータの幾つか、１，２，４またはそれ以上のセクタを記憶する可能性があるページとして同時にプログラムし読み出すことができる。２つ以上のブロックがメタブロックに論理的に結合されている場合、２つ以上の各ブロックの１つの行内の全メモリセルを同時にプログラムし読み出すことができる。同時にプログラムされ読み出される２つ以上のブロックからの２つ以上のページは、メタページを形成する。同時に多くのデータをプログラムする機能を用いると、メタページ内のデータのステージングを、この利用可能な並列性を充分に使用することに役立てることができる。
【０１２０】
図１８には、３つの各ホストファイルに対するデータの１つのメタページを示す。各メタページは、説明を簡単にするために２つだけのページを含むように示されている。メタページの各ページのデータは、メタブロックの異なるブロックにプログラムされる。
【０１２１】
ホストファイル１の場合、メタページは、単一のデータグループ０の一部として連続的なオフセット（論理アドレス）を有するデータで満たされているように図１８の（Ａ）に示されている。これらデータは、ファイル１のデータを受信するメタブロック内で順序が次にあるメタページに同時にプログラムされる。図１８の（Ｂ）では、この例のホストファイル２は、最初のページの一部が、連続的なオフセットを有するデータグループ１の部分を含み、メタページの残りの部分が、連続的なオフセットを有する別のデータグループ２の部分を含むという点で異なって示されている。２つのデータグループがファイル２のメタページ内で結合する箇所でデータのオフセットに途切れが存在するが、これらデータは単一メタページに同時にプログラムされる。前述したように、直接ファイル記憶インターフェイスは、ファイル内のデータのオフセットの順序にかかわらず、ホストファイルのデータを、ホストから受信されたとおりに書き込む。
【０１２２】
幾つかのフラッシュメモリは、データを消去済みページに２度以上プログラムすることができない。この場合、図１８の（Ｂ）のデータグループ１およびデータグループ２の双方は、同時にプログラムされる。しかし、メモリが部分的なページプログラミングを可能にする場合、ファイル２の２つのデータグループを不揮発性メモリの単一メタページに異なる時点でプログラムすることができる。この場合、ページ０は異なる時点でプログラムされ、最初にデータグループ１がプログラムされ、次に、データグループ２がページ０の残りの部分とページ１の全部とにプログラムされる。しかし、システム性能を増大させるため、データグループの双方を同時にプログラムするのが一般的に好ましい。
【０１２３】
図１８の（Ｃ）では、ファイル３のメタページに書き込まれた単一のデータグループ３の終わりが示されている。このような少量のデータが不揮発性メモリのメタページにプログラムされる一方で、メタページの残りの部分が消去されたままである場合、特定の状態が存在する。１つには、データグループ３がデータファイル３の残留ファイルであるファイルに対してＣｌｏｓｅコマンド（図１２Ｂ）をホストが送出するとき、ホストが、許容数を上回って多数のファイルを開こうとすれば、メモリコントローラによっても閉じることができ、ファイル３は選択されて閉じられ、これによって、代わりに別の追加のアクティブファイルを開けることができる。メモリコントローラは、開かれたファイルメタページバッファのすべてに対するバッファメモリ内の容量が不充分である場合にもファイル３を閉じることができる。これらの場合のいずれでも、ファイルバッファの部分的なデータ内容を不揮発性メモリに直ちに書き込む（ファイルバッファを「フラッシュする」）のが望ましい。ホストは、メモリへの電源が失った可能性があり、不揮発性メモリに直ちにプログラムされなければ、揮発性バッファメモリ内の全データは失われることを意味するＳｈｕｔ−ｄｏｗｎコマンド（図１２Ｄ）をも送信することができる。
【０１２４】
ファイル３の別のデータグループ４の始まりを図１８の（Ｃ）のメモリメタページに書き込むことが後で要求され、メモリによって部分的なページプログラミングが可能でない場合、データグループ４の最初のページは、図１８の（Ｄ）に示されているようにファイル３のメタページの第２のページに書き込まれる。この結果、不揮発性メモリメタページ内の図１８の（Ｄ）のデータグループ３とデータグループ４との間の空白部分によって示されるように、一部の未使用のメモリ容量を生じることがある。この未使用の容量を、ファイル３が閉じられた後に実行されるガーベッジコレクション動作によって回復することができ、または、この状況がまれに起こる可能性が高いので存続させることができる。
【０１２５】
本発明の直接ファイル記憶技術が、不揮発性メモリのブロック内のこのような満たされていない空隙を許容できることに留意すべきことが重要である。図７および図８によって示されているように、メモリシステムが論理アドレス空間を介してホストとインターフェイスをとる現在のシステムによって、このような空隙を容易に許容することはできない。論理データは同じ大きさをメモリブロックとしてグループ化し、または、メタブロックはこのようなブロックまたはメタブロックにマッピングされる。既存のメモリシステムのブロックまたはメタブロック内に記憶されたデータ内に空隙が存在することになる場合、空隙にマッピングされた論理データアドレスは、ホストによって効果的に使用不可能にされる。このような既存のインターフェイスでは、ホストは、それに利用可能な全部の論理アドレス空間を有すると仮定するが、仮に可能であったとしても、空隙を指定する論理アドレスに新たなデータを書き込むことは極めて困難である。
【０１２６】
図２のメモリ３１のようなシステムコントローラ内のバッファメモリの一部は、一般的にプログラミングデータバッファとして用いられる。このメモリ内のバッファ容量は、ホストによって書き込まれるアクティブファイルごとに存在する必要がある。このような「ファイルバッファ」の各々は、フラッシュメモリ内の少なくとも１つのメタページに等しい容量を有する必要がある。アクティブファイルは、ホストによってデータが最近書き込まれた開いた状態のファイルである。
【０１２７】
どの時点においてもメモリシステムが対応するアクティブホストファイルの数を、現在開いた状態のメモリシステムファイルの数に等しくすることができ、または、これよりも少ない数とすることができる。アクティブファイルの許容最大数は、開いたファイルの許容最大数よりも少ない場合、アクティブ状態と、開いた状態との間でファイルの状況を変更するため、プロビジョンを行う必要があり、逆の場合もまた同様である。このことを可能にするため、フラッシュメモリ内の一時的記憶ブロックはスワップブロックとして指定され、長さが１つのメタページを満たないデータをスワップバッファ内のファイルバッファからメタページに書き込むことができ、逆もまた同様である。有効なスワップされたファイルバッファの索引は、スワップブロックに維持される。ファイルバッファデータは、整数のページとしてスワップブロックへコピーされる。整数のページの後には、各々コピーされたファイルバッファの長さおよび位置の索引を備える単一ページと、それが関連するファイルとが続く。スワップブロックは周期的に圧縮され、いっぱいになったら消去済みブロックに書き込まれる。
【０１２８】
開いたファイルＡを、このファイルＡへのホスト書き込み動作の結果としてアクティブ状態にする必要がある場合、例えば、最も長い間書き込まれなかったアクティブファイルＢは識別され、ファイルバッファデータは、コントローラバッファメモリからスワップブロック内の次の利用可能なページへコピーされる。次に、ファイルＡのファイルバッファデータはスワップブロック内で識別され、以前にファイルＢに割り当てられたコントローラバッファメモリ内の利用可能な空間へコピーされる。
【０１２９】
図１８に示されている場合のうちの１つに従って、ファイルバッファからのデータを、フラッシュメモリ内のファイルの開いた書き込みブロックの次の利用可能なメタページに書き込むのが好ましい。図１８の（Ａ）では、ファイル１内に単一データグループ０の一部を形成する充分なデータがファイル１のバッファ内に存在する場合、このデータグループは単一動作でメタページ全体にプログラムされる。図１８の（Ｂ）では、ファイル２内にデータグループ１の終わりおよびデータグループ２の始まりを形成する充分なデータがファイル２のバッファ内に存在する場合、これらデータグループは単一動作でメタページ全体にプログラムされる。フラッシュメモリ装置が単一ページでの複数のプログラム動作（部分的なページプログラミング）を支援する場合、ファイル２内にデータグループ１の終わりを形成する充分なデータがファイル２のバッファ内に存在すれば、このデータグループをページ０の一部にプログラムすることができる。ファイル２内にデータグループ２の始まりを形成する充分なデータがファイル２のバッファ内で利用可能になると、次に、このデータグループを、別個のプログラム動作で同じメタページの残りの部分にプログラムすることができる。
【０１３０】
図１８の（Ｃ）に示されているように、ファイル３内にデータグループ３の終わりを形成するデータがファイル３のバッファに存在し、バッファフラッシュ動作を実行する必要がある場合、このデータグループはページ０の一部にプログラムされる。フラッシュメモリ装置が単一ページでの複数のプログラム動作（部分的なページプログラミング）を支援しない場合、ファイル３内のデータグループ４の始まりを形成する充分なデータがファイル３のバッファ内で利用可能になると、次に、このデータグループは、別個のプログラム動作で同じメタページ内のページ１にプログラムされる。
【０１３１】
メタページファイルバッファは、ガーベッジコレクション中にも用いられる。ファイルの有効データグループを不揮発性メモリから読み出し、このファイルのコントローラバッファメタページに書き込むことができる。ファイルが同時に再配列される場合、データグループは、ホストデータオフセットの順でバッファに書き込まれる。各データグループのデータが連続的な論理オフセットを有することはもちろんである。メタページバッファがいっぱいになった後、データは並行して不揮発性メモリの新たなブロックにプログラムされる。
【０１３２】
ファイル索引付け
メモリシステムに記憶された各ファイルは、特に、図１３〜図１６を参照して前に説明したようなそれ自体の一連の索引項目によって定義される。これら項目内でファイルのデータが付加、挿入または更新されるので、これらの項目は時間と共に変化し、また、ファイルにガーベッジコレクションが課せられると変化する。図１９には、幾つかの異なる各時点０，２，４および５での１つのファイルに対するファイル索引テーブル（ＦＩＴ）内の一連の索引項目を示す。これらはそれぞれ図１４Ａ、図１４Ｃ、図１４Ｅおよび図１５を参照して前に説明した一連の索引項目である。ＦＩＴ内のデータを書き込み、ホストシステムからの支援なしにメモリコントローラによって現行を保持するのが好ましい。ホストは、データグループ、または、データグループがメモリセルアレイに記憶される箇所を定義することに関与しないが、ホストシステムはデータをメモリシステムに書き込むとき、パス名、ファイル名およびファイル内のデータのオフセットを供給する。図１９の項目では、図１４および図１５のメモリセルブロックに左から、１から始まる番号が付けられる。従って、図１４Ｃに示されている状態のファイルの場合、例えば、３番目のデータグループ（Ｆ６，Ｄ７）は、図１９において、ブロックの先頭のアドレスからＤ７バイトであって、ブロック００４、すなわち左から４番目のブロックに記憶されていると示されている。テーブルの各項目に各データグループの長さも含めるのが好ましい。
【０１３３】
１つのファイルに対して図１９に示されている一連の索引項目は、ファイルの変更によってファイルのデータグループに変更が生じたとき、または、他の低い頻度の間隔でメモリコントローラによって再度書き込まれる。コントローラはメモリでのこのような変化を記憶することができ、次に、これら変化の多くをフラッシュメモリに同時に書き込むことができる。１つだけの有効な索引セットは、どの時点においても１つのファイルに対して存在する。図１９には、異なる時点にファイルを定義する４つのこのような索引セットを示す。次に、追加のデータをファイルにプログラムし、データをファイルから読み出し、ファイルのデータにガーベッジコレクションを行い、可能性がある他の動作を実行するため、必要に応じて、メモリシステムコントローラはファイルの現在の索引セットを用いる。従って、ＦＩＴは、個々のファイル索引項目がファイルオフセット（Ｆｘ）の順に記憶されている場合に使用しやすいが、そうでない場合、コントローラは論理順序で項目を確実に読み出すことができる。特定のファイルに対して索引項目を読み出すメモリコントローラの最も一般的な要因は、ホストコマンドを実行する過程にある。
【０１３４】
図２０には、ファイルマップの一部としてファイル索引テーブル（ＦＩＴ）を維持し用いる好適な技術を示す。一連のファイル索引付け構造は、指定されたパス名を有するファイル内に、指定されたオフセットアドレスを有するデータの物理位置を識別するのに用いられる。ファイルマップは、従来の論理アドレスインターフェイスと用いられる標準のディスクオペレーティングシステム（ＤＯＳ）のルートディレクトリおよびサブディレクトリ構造とほぼ同じ論理構造を有するディレクトリ２０１を含む。ファイルディレクトリ２０１を、メモリシステム内の１つ以上の専用のフラッシュブロックに記憶することができる。しかし、ファイルディレクトリ２０１を、ホストの代わりに記憶システムによって管理するのが好ましい。本願明細書では、図１２Ｃのホストディレクトリコマンドは、メモリシステムコントローラによって実行されるが、コントローラによって決定された時点で、かつ、決定されたように実行される。ホストにファイルディレクトリへ直接書き込ませないのが好ましい。
【０１３５】
ディレクトリまたはファイルを各々識別する一様にサイズ設定された項目は、ファイルディレクトリ２０１内で保持される。連続的な項目セットは、特定のディレクトリ内の要素を指定するのに用いられる。ディレクトリを指定する項目内のポインタ領域は、このディレクトリ内の要素を指定する他の連続的な項目の始まりを識別する。ファイルを指定する項目内のポインタ領域は、関連するファイル索引テーブル（ＦＩＴ）２０３内のブロック番号およびファイル番号を定義する。
【０１３６】
ＦＩＴ２０３は、データグループの一様にサイズ設定された項目を含む。各項目は、データグループの始まりのオフセットと、データグループのメモリシステム内の物理位置とを識別する。論理アドレスがバイト粒度で維持される場合、各ＦＩＴ項目のオフセットは、データグループの始まりを指定するファイルの始まりから指定された数のバイトを含む。これと同様に、データグループの始まりの物理位置をバイト粒度で指定することができる。異なる時点にある例示的なファイルに対するＦＩＴ項目の内容は、図１９を参照して前に説明した。別々の項目はデータグループごとに維持されている。各ファイルは、ファイル内のデータグループの一連の連続的な索引項目によって定義されている。１つのファイル当たりのこのような項目の数は一般的に異なる。
【０１３７】
ホストによって供給されたファイルのパス名は、ＦＩＴ内のブロック番号およびファイル番号を獲得するためにファイルディレクトリの階層を全検索するのに用いられる。一般的に、パス名は１、２またはそれ以上のディレクトリおよびサブディレクトリを含む。これらは、アクセスしようとするファイルを含むファイルディレクトリ２０１内のディレクトリにアクセスするのに用いられる。次に、ディレクトリ内のファイル名は、ホストによって供給されたファイル名に対する項目２０５を検出するために検索される。項目２０５が検出されると、項目２０５は、ポインタを、ファイルに対するＦＩＴ２０３内の連続的な項目グループに供給する。これら項目は、図１９を参照して説明した項目の性質を持っている。次に、これら項目のオフセットは、ホストによって供給されたオフセットアドレスと比較されて、正しい項目２０７、従って、正しいデータグループを識別する。オフセットの完全な一致がない場合は、項目に含まれるオフセットがデータグループの始まりのアドレスだけであるためにしばしば起こることがあり、項目にオフセットを含むデータグループを識別する項目が選択される。この例では、ＦＩＴ２０３の選択された項目２０７は、物理ブロックと、ホストによってアクセスしようとしているデータを含むメモリ位置のバイトとを含む。
【０１３８】
ファイルが最初に生成されたときに、または、ＦＩＴ２０３内のファイルのデータグループ項目の位置が変更されたときに、図２０のファイルに対するディレクトリ項目２０５のポインタはメモリシステムコントローラによって割り当てられる。このポインタは、前述したｆｉｌｅ＿ｈａｎｄｌｅの一例である。ファイルにアクセスするたびにホストがファイルディレクトリ２０１の階層を検討してファイルのＦＩＴ項目を検出するという必要性を回避するため、メモリシステムはｆｉｌｅ＿ｈａｎｄｌｅをホストに送信することができ、これによって、その後、ホストは、開かれたファイルのＦＩＴ項目に直接にアクセスすることができる。
【０１３９】
図２１には、ファイルディレクトリ２０１内の個々の項目を記憶するメモリシステム内のページを示す。ポインタをファイルディレクトリ２０１内のディレクトリに供給する項目もあれば、ＦＩＴ２０３内のデータに供給する項目もある。単一メモリページ内に記憶された多くの項目の１つである例示的な項目２０９は、各項目が４つの領域を有するように示されている。第１の領域は、ホストによって与えられたディレクトリまたはファイルの名前を含む。第２の領域は、ホストによって定義されたディレクトリまたはファイルの属性を含む。ディレクトリの項目の場合、第３の領域内のポインタはファイルディレクトリ内の別の項目を指す。ファイルの項目の場合、第３の領域は、項目２０７のようなＦＩＴ２０３内のファイル項目へのポインタを含む。「データグループ」と識別される第４の領域は、ディレクトリの項目では空であるが、ファイルの項目の場合、この領域は、ファイルのデータを含むデータグループの数、従って、ファイルに対するＦＩＴ２０３内の項目の数を指定する。
【０１４０】
図２１に示されているファイルディレクトリページが２つの区域を含むことに留意すべきである。最近書き込まれたページ２１１では、ディレクトリ項目（１つには、ページ２１３内で符号２０９が付されている項目）およびページポインタの双方が存在する。ページ２１３のような他のディレクトリページでは、ディレクトリ項目は存在するが、ページの一領域は、古いページポインタを含む。現在のページポインタは、最近書き込まれたページ、この場合ではページ２１１の同じ部分に維持されている。１つのページポインタはディレクトリブロック内の論理ページごとに存在し、メモリコントローラを、アクセスしている論理ページに対応する物理ページに指向する。最近書き込まれたディレクトリページ内のページポインタを維持することによって、ページポインタは、ディレクトリ項目と同時に、かつ、その後に別のページを更新する必要なしに更新される。この技術は、論理アドレス形のファイルシステムについて、ゴロベッツらによる２００４年８月１３日に出願された米国特許出願第１０／９１７，７２５号（特許文献２０）にさらに詳細に記載されている。
【０１４１】
特定の実施例では、ディレクトリブロックは、メモリセルブロック内の全ページのうちの指定された部分（例えば、５０％）である一定数の論理ページを含む。ディレクトリブロックを、ディレクトリページの記憶に専用とされるメタブロックとするのが好ましいが、単一消去ブロックとすることができる。ディレクトリブロックは、データグループを記憶するのに用いられるメタブロックと同じ並列性を有することができ、または、低い並列性を有することができる。ファイルディレクトリブロックはいっぱいになると、元のブロックを消去する前に各論理ページの有効部分を新たなブロックへコピーすることによって圧縮される。ディレクトリブロックが圧縮された直後、新たなコピーブロック内のページの（５０％のような）定義された部分だけがディレクトリ項目を用いて書き込まれる。残りのページは、更新された項目または新たな項目の書き込みを可能にする消去済み状態にある。
【０１４２】
ディレクトリまたはファイルの項目が生成、変更または削除されると、このディレクトリまたはファイルを含むディレクトリの項目セットは、ディレクトリブロック内の次の利用可能な消去済みページに再度書き込まれ、従って、ディレクトリの項目を連続しているように保持する。このことは、このディレクトリの項目を前もって含むページの読み出し／変更／書き込み動作によって行われる。従って、以前のページは古くなる。この論理ページのページポインタ項目も、新たな物理ページを識別するために更新される。このことを、ディレクトリの項目を書き込むために用いられたのと同じページプログラム動作で行うことができる。
【０１４３】
項目の生成によって、ディレクトリの項目セットがページをあふれさせる場合、その代わりとして、別のページの最初の項目として項目セットを書き込むことができる。必要に応じて、ディレクトリの項目セットをページの終わりに移動するように既存のページを再度書き込むこともできる。ディレクトリブロック内の論理ページ番号をページポインタに再度割り当てて、ディレクトリの項目を連続しているように保持することができる。
【０１４４】
図２０のファイル索引テーブル（ＦＩＴ）２０３は、装置内の全ファイルを構成するデータグループへの索引を記憶する。ＦＩＴは、メモリシステムの１つ以上の専用のＦＩＴブロックに記憶される。各ＦＩＴブロックは、最大数までのファイルの索引を記憶することができる。ＦＩＴは、テーブルによって索引付けられたファイルの１つを指定するファイルディレクトリから論理ポインタを用いてアクセスされる。ポインタは、最近書き込まれたＦＩＴページ２１７の一部として供給されたファイルポインタにアクセスすることによって間接アドレス指定を用い、これによって、索引がＦＩＴブロック内で更新され再度書き込まれるときにポインタは変化しない。
【０１４５】
項目２０５のようなファイルディレクトリ２０１内のファイル項目のＦＩＴポインタは、２つの主要な領域を有する。第１の領域は、ＦＩＴを構成する論理ＦＩＴブロックの１つを識別するＦＩＴブロック番号である。ＦＩＴブロック番号に割り当てられた実際の物理ブロックアドレスは、別々に管理される。ＦＩＴポインタの第２の領域は、識別されたＦＩＴブロック内の論理ファイル番号を識別するＦＩＴファイル番号である。論理ファイル番号は、ＦＩＴブロックの最近書き込まれたページ内に記憶された特定のファイルポインタによって物理ファイル項目位置に変更される。
【０１４６】
ＦＩＴは、予め定義された大きさを持たず、ＦＩＴブロックの数は、データが編成されたファイルの数およびデータグループの数の関数である。新たなＦＩＴブロックが生成され、装置の動作中、ＦＩＴブロックは削減される。
【０１４７】
図１９を参照して前に説明したように、図２２に関して、個々のＦＩＴページは、多数のデータグループ項目、すなわち、データグループごとの１つの項目２１９を有する。この特定の例では、各項目２１９は４つの領域を含む。ファイルオフセット領域は、項目によって識別されるデータグループの始まりのファイル内のオフセットアドレスを指定する。ブロックアドレス領域は、データグループを含むメモリシステム内のブロックまたはメタブロックの物理アドレスを指定する。バイトアドレス領域は、ブロックまたはメタブロック内のページのアドレスと、データグループが開始するページ内のバイトとを指定する。４番目の領域は、データグループの長さである。隣接した項目のデータからデータグループの長さを計算することができるので、すべての場合においてデータグループの長さを必要としなくてもよい。しかし、長さを維持することによって、この計算を、データグループの長さが求められるたびに行う必要はない。論理アドレスの順にデータグループ項目がＦＩＴ内に書き込まれていない場合、従って、計算がさらに困難になる場合、データグループの長さは、特に有益な情報である。
【０１４８】
ファイルを形成する順序付きデータグループを同時に定義する連続的なデータグループ項目セットによってホストファイルを定義するのが好ましい。図２２のページ２１５に示されている陰影付きの連続的なグループ項目は１つのファイルを定義し、ページ２１７内のグループ項目は別のファイルを定義する。ＦＩＴブロック内に維持された個々のファイルに対して、最後に書き込まれたＦＩＴページ２１７内には、ＦＩＴ内の個々のファイルごとに１つのファイルポインタ２２１がある。ファイルポインタ２２１は、ＦＩＴブロック内に特定のＦＩＴファイル番号を有するファイルのファイル項目の始まりを定義する。ファイルポインタ２２１は、２つの領域を含む。一方の領域は、データグループ索引項目が存在するページの物理番号であり、他方の領域は、このページ内の最初のグループ項目の番号である。ＦＩＴブロック内の実行可能なファイル番号ごとにファイルポインタが存在する。すなわち、ファイルポインタの数は、ＦＩＴブロック内のファイルの最大番号に等しい。ファイルポインタ項目内の予備コード（図示せず）は、特定のファイル番号がＦＩＴブロック内で未使用であることを示す。ファイルポインタは他のＦＩＴページ内に存在しうるが、それらは、ＦＩＴブロックの最近書き込まれたページのみで有効である。
【０１４９】
ＦＩＴブロックは、ＦＩＴページを記憶するのに専用とされるメタブロックであるのが好ましい。ＦＩＴブロックは、データグループを記憶するのに用いられるメタブロックと同じ並列性を有することができ、または、低い並列性を有することができる。その代わりに単一消去ブロックを用いることができる。ＦＩＴブロックが圧縮された直後、ブロック内のページの（５０％のような）定義された部分だけが項目を含む必要がある。残りのページは、更新された項目または新たな項目の書き込みを可能にする消去済み状態である必要がある。多数のファイルが維持される場合、２つ以上のＦＩＴブロックを必要とすることがある。
【０１５０】
ＦＩＴは、１つ以上の完全なファイルのデータグループ項目を、ＦＩＴブロックの次の利用可能なプログラムされていないページに書き込むことによって更新される。ファイルのファイルポインタ項目も、ファイル項目の新たな位置を識別するために更新される。ファイルデータグループ項目およびファイルポインタの双方は、同じページプログラム動作で書き込まれる。従って、ファイル項目の以前の位置は、ＦＩＴブロック内で古くなる。あるいはまた、ファイル項目を、異なるＦＩＴブロックまたは新たなＦＩＴブロックに書き込むことによってファイル項目を更新することができる。この場合、双方のブロック内のファイルポインタを更新する必要があり、ファイルディレクトリ内のファイルの論理ポインタを変更する必要がある。
【０１５１】
ＦＩＴブロックがいっぱいになると、有効なグループ項目は、圧縮された形態で、新たな消去済みブロックへコピーされ、以前のＦＩＴブロックは消去される。この動作によって論理ＦＩＴブロック番号および論理ファイル番号は変更される。ページの（５０％のような）定義された部分だけが、圧縮されたＦＩＴブロックにプログラムされるように、データグループ項目の数を制限する必要がある。必要に応じて、ファイル項目を他のＦＩＴブロックに移動する必要があり、ファイルディレクトリの論理ポインタを変更する。
【０１５２】
１つのページまたはメタページ内に個々のファイルのＦＩＴ項目のすべてを保持するのが望ましい。このことは、ファイルの項目のすべてを読み出すことを比較的容易にする。各ＦＩＴ項目内に次の物理アドレスを含めることによってファイルのＦＩＴ項目を互いにつなげることができるが、このことは、２つ以上のＦＩＴページまたはメタページを読み出すことを必要とする可能性が高い。ページ内でＦＩＴ項目を連続しているように保持することも望ましい。この結果として、ＦＩＴ項目の数が増大するにつれて、特に、閉じられたファイルが開かれ、このファイルにデータグループが追加されるときに、新たなページを頻繁に書き込むことができる。新たなＦＩＴ項目が新たなページに書き込まれると、既存の項目は別のページからコピーされ、新たな項目と一緒に新たなページに書き込まれる。既存の項目の以前のページ内の古いデータによって占められた空間は、ＦＩＴブロックが圧縮されるときに用いるために取り出される。
【０１５３】
前述したように、個々のデータグループは、単一ブロックまたはメタブロック内に含まれ、ブロック内の任意のバイト境界で開始することができ、任意の整数のバイトの長さを有することができる。データグループがメモリに書き込まれるとき、コントローラによって各データグループにヘッダを追加することができる。このようなヘッドは、２つの領域を含むことができる。第１の領域は、データグループの始まりを識別するコードを含む。このコードを、すべてのデータグループに対して同じにすることができ、このコードは、データグループの一部として記憶されたデータ内にまれに存在するがこのようなデータにコードが決して現れないとは限らないビットパターンとして選択される。メモリコントローラが、このコードに対して、記憶されたデータを走査し、次に、メモリコントローラがコードのビットパターンを検出したときに、それが本当にデータグループの始まりであるか、データグループ内のデータでないかを確認することによってデータグループの始まりを検出することができる。ヘッダの第２の領域によって、この確認を行うことができる。この第２の領域は、データグループを含むファイルに対するＦＩＴ２０３（図２０および図２２）内のファイル項目へのポインタである。第２の領域は、ＦＩＴブロック番号およびＦＩＴファイル項目を定義する。次に、コントローラはＦＩＴファイル項目を読み出して、ＦＩＴファイル項目が指し返すデータグループからコードが読み出されたかどうかを確かめる。そうである場合、コードは、データグループのヘッダ内に存在する指示であると確認される。そうでない場合、コードのビットパターンは、他のデータから読み出されたと確認され、従って、データグループヘッダとして無視される。
【０１５４】
このようなヘッダを、個々のデータグループに記憶されたデータの一部として含むことによって、メモリ内のいずれかのデータグループが属するファイルを、ヘッダを読み出し、ヘッダが指すＦＩＴ項目にアクセスすることによって決定することができる。ＦＩＴ項目２１９（図２２）は、ｆｉｌｅＩＤを含むことができる。本願明細書では、この機能を用いて、例えば、共通ブロックのガーベッジコレクション中、共通ブロック内のデータグループを識別する。共通ブロック内の１つ以上の他のデータグループが古いため、ガーベッジコレクションが行われる場合、残りの各有効データグループが属するファイルを識別できるのが望ましい。
【０１５５】
各データグループの一部を形成するヘッダの代わりに、１つのファイル当たり１つのヘッダを供給することができる。ファイル内のデータグループのＦＩＴ項目の位置が既知であり、ファイルヘッダがこのことを可能にする場合、ファイルの絶対パス名を識別できるのが有利である。このようなヘッダを、ファイルに対するＦＩＴ内の項目セットの始まり、または、ファイルディレクトリ内のディレクトリに対する項目セットの始まりとして供給することができる。
【０１５６】
このファイルヘッダは、それをＦＩＴファイルヘッダとして識別するコードと、ファイルヘッダを指しているディレクトリ項目への逆ポインタとを含む。ＦＩＴファイルヘッダは、ファイルの長さおよびデータグループの数のような追加の情報をも含むことができる。あるいはまた、ヘッダ項目は、１つ以上の通常の項目の空間を占有することができる。
【０１５７】
これと同様に、ディレクトリヘッダは、それをディレクトリヘッダとして識別するコードと、ディレクトリヘッダを指しているディレクトリ項目への逆ポインタとを含む。ルートディレクトリは、ヘッダ内で明白に識別される。ディレクトリヘッダは、ディレクトリ内の項目の数のような特定の追加情報をも含むことができる。
【０１５８】
このようなデータグループまたはファイルヘッダの使用に代わるものとして、索引を各共通ブロックの終わりに書き込んで、共通ブロック内の各データグループが関連するファイルを識別することができる。共通ブロックが閉じられると、このような索引を書き込むことができる。索引は、共通ブロック内の各データグループが開始する共通ブロック内の物理バイトアドレスと、このデータグループへのＦＩＴ項目へのポインタとを含むのが好ましい。従って、各共通ブロックデータグループが一部であるファイルを、データグループの索引項目に供給されたＦＩＴ項目を参照することによって決定することができる。
【０１５９】
これらの共通ブロック索引が用いられる場合であっても、メモリに記憶されたデータグループに対してファイル識別子の何らかの冗長部分を有することが望ましければ、前述したデータグループヘッダを依然として保持することができる。
【０１６０】
メモリ装置は、ファイルディレクトリおよびファイル索引付けを管理するので、その結果、ホストに報告される装置構成パラメータを制御することができる。一般的に、このことは、現在の商用システムでのように装置のファイルシステムがホストによって管理される場合には可能でない。メモリ装置は、報告される記憶容量、例えば、全装置の容量および、書き込まれていない利用可能な容量の双方を変更することができる。
【０１６１】
ファイルに対して直接ファイルインターフェイスで用いられるパス名は、記憶装置自体のＩＤと記憶装置内のパーティションとを識別することができる。メモリ装置にパーティションの大きさおよび数を変更させることができるのが有利である。パーティションがいっぱいになると、１つ以上の他のパーティションから未使用の容量を、いっぱいのパーティションに再割り当てすることができる。これと同様に、新たなパーティションが生成される場合、他のパーティションから未使用の容量を割り当てることができる。装置は、前述したように様々なパーティションの報告された容量を変更することができる。
【０１６２】
図２０および図２１に示されているディレクトリ構造は、ディレクトリ項目内のポインタを用いて、このディレクトリ内の要素に対する他の連続的な項目セットの始まりを識別する。このポインタはディレクトリブロック内の論理ページを指し、この論理ページに対応する物理ページが変更される場合にポインタは変わらないままである。しかし、ディレクトリ内の要素の数は頻繁に変更され、特定のディレクトリに対する項目セットを１つの論理ページから別の論理ページに移動する必要、または、現在の論理ページ内に移動する必要が頻繁にある。この結果として、ディレクトリブロック内のポインタ参照を更新する必要性が頻繁に起こることがある。図２１のディレクトリ構造に対して代わりとなるディレクトリ構造の項目索引付け技術を図２３に示す。図２３では、対応する要素に同一の符号が付されているが、この符号にダッシュ記号（’）が付加されている。
【０１６３】
図２３の構造は、図２２のＦＩＴの構造と同じであるが、ディレクトリに関して異なる技術を有する。図２１において行われたようなページだけというよりはむしろ特定の項目が指し示される。このことは、指定されたディレクトリの項目セットに対するディレクトリブロック内の間接アドレス指定方法であって、図２１を参照して前に説明した間接アドレス指定方法よりも効率良い方法を提供する。ディレクトリ（図２３）およびＦＩＴ（図２２）ブロックに対して同じ索引付け方法を用いるのが適切であり、その理由は、双方が極めて類似の特性および要件を有するためである。それらは各々、ディレクトリまたはファイルに関連する連続的な項目セットを記憶する。既存の項目の内容を変更するか、または、項目の数を変更することから、項目セットの更新を構成することができる。
【０１６４】
図２２を参照して説明したＦＩＴ項目の更新方法は、ブロックの圧縮後、消去済み状態で、ＦＩＴ項目を含む物理ブロック内にページの一部分（例えば、５０％）を残す。これによって、更新されたＦＩＴ項目を、圧縮されたブロックの残りの部分に書き込むことができる。ブロックによって索引付けられたいかなるファイルも実際に開いていないときでも、すべてのＦＩＴブロックは、この容量オーバーヘッドを組み入れる。従って、ＦＩＴは、望ましいメモリ容量よりも多くのメモリ容量を占有する。
【０１６５】
代わりのＦＩＴ更新方法は、更新されたＦＩＴ項目セットを、ＦＩＴ項目セットが最初に配置されたブロック内の利用可能な消去済み容量内というよりはむしろ別個のＦＩＴ更新ブロック内に書き込ませる。図２４および図２５は、更新ブロックを用いるファイルディレクトリおよびＦＩＴ用の索引付け技術をそれぞれ概説する。ディレクトリおよびＦＩＴに用いる用語だけが異なること以外、これらの技術は同一である。
【０１６６】
以下の説明は、図２５に示されているようなＦＩＴブロック内のグループ項目の更新に関するが、ファイルディレクトリ内のグループ項目の更新（図２４）に同様に適用することができる。
【０１６７】
前に説明したように、ＦＩＴブロックからグループ項目を読み出す。ＦＩＴポインタのＦＩＴブロック番号領域は、論理ＦＩＴブロックを定義する。ＦＩＴブロックリストは一瞬にデータ構造内に含まれ、ＦＩＴブロック番号を、ブロックが配置されているブロックの物理アドレスに変換する情報を供給する。圧縮または統合動作中、ＦＩＴブロックが移動されるときはいつでも、ＦＩＴブロックリスト内のブロックアドレスは更新される。
【０１６８】
このブロック内に最近書き込まれたページのファイルポインタ領域によって、ＦＩＴポインタ内のＦＩＴファイル番号値を、指定されたファイルに対するファイルグループ項目セットの始まりを指定するファイルポインタに変換することができる。従って、ファイルグループ項目をＦＩＴブロックから読み出すことができる。
【０１６９】
グループ項目の内容、またはファイルに対するグループ項目セットのグループ項目の数が更新されると、完全な項目セットは、消去済みページに再度書き込まれる。（このことは、ページがフラッシュメモリ内の最小プログラム単位であり、同じページへの複数の書き込み動作が消去動作間で禁止されているという仮定に基づく。）この項目セットは、必要に応じて複数のページを占有することができる。
【０１７０】
今、説明している技術では、このページは、ＦＩＴブロック内の次の利用可能なページである。修正された方式では、このページは、別個のＦＩＴ更新ブロック内の次の利用可能なページである。ＦＩＴ更新ブロックは、図２３に示されているようなＦＩＴブロックと同じページ構造を有する。その存在は、ＦＩＴ更新ブロックリスト内の対象とするＦＩＴブロック番号の存在によって識別される。また、ＦＩＴ更新ブロックリストは、更新ブロックの物理ブロックアドレスと、元のＦＩＴファイル番号に対応する更新ファイル番号とを含む。ＦＩＴブロックごとに別個のＦＩＴ更新ブロックを更新することができ、または、好ましくは、ＦＩＴ更新ブロックは複数のＦＩＴブロックに関連することができる。単一のＦＩＴブロックも、複数のＦＩＴ更新ブロックに関連することができる。
【０１７１】
ＦＩＴ更新ブロックがいっぱいになると、有効データを圧縮形態で消去済みブロックに書き込むことができ、この消去済みブロックは、新たなＦＩＴ更新ブロックになる。更新がほんの数ファイルにしか関連しない場合、単一ページの有効データほどしかないことがある。複数のＦＩＴ更新ブロックを単一ブロックに同時に圧縮することができる。更新ブロックが、依然として開いた状態であって、更新し続けることができる１つ以上のファイルに関連する場合、ブロック圧縮はブロック統合に好まれる。
【０１７２】
ＦＩＴ更新ブロック内でファイルのグループ項目が更新されると、元のＦＩＴブロック内のこのファイルの項目は古くなる。ある段階で、元のＦＩＴブロックはガーベッジコレクション動作を受けて、除去される必要がある。このことを、ＦＩＴブロックおよびＦＩＴ更新ブロック内の有効データを消去済みブロックに統合することによって行うことができる。
【０１７３】
項目の数が更新処理中に増大した場合、有効データを単一の消去済みブロックに統合することができず、このＦＩＴブロックに最初に割り当てられたファイルを２つ以上のＦＩＴブロックに再割り当てすることができ、２つ以上のブロックに対して統合を実行することができる。
【０１７４】
ＦＩＴ更新ブロックからの項目を、ＦＩＴブロックからの項目と共に統合することができ、従って、ＦＩＴ更新ブロックから削減することができ、その一方で、他のファイルの項目はＦＩＴ更新ブロック内にとどまることができる。
【０１７５】
さらなる代わりとして、ディレクトリ項目およびファイルグループ項目の双方を含むことができる単一の索引ブロック構造に、ディレクトリブロックおよびＦＩＴブロック構造を組み合わせることができる。別個のディレクトリブロックおよびＦＩＴブロック構造が存在するか、または、組み合わされた索引ブロック構造が存在する場合、索引更新ブロックは、ディレクトリ項目およびファイルグループ項目の双方の更新ブロックとして作用することができる。
【０１７６】
図２０〜図２５を参照して前に説明したファイルディレクトリおよびＦＩＴはＤＯＳシステムに則っていることが分かる。あるいはまた、ファイルディレクトリおよびＦＩＴは、Ｌｉｎｕｘ（登録商標）、Ｕｎｉｘ（登録商標）、ＮＴファイルシステム（ＮＴＦＳ）または何らかの他の既知のオペレーティングシステムに則ることができる。
【０１７７】
特定のメモリシステム動作の例
図２６〜図３２の動作フローチャートは、図２〜図６を参照して前に説明したように構成されているが、図９および図１０〜図２２を参照して説明した直接ファイルインターフェイス技術の特定の組み合わせを用いるメモリシステムの動作の一例を示す。図２６〜図３２のフローチャートに含まれる機能は、記憶されたファームウェアを実行するコントローラ１１（図２）によって主に行われる。
【０１７８】
システム動作全体が示されている図２６を最初に参照する。最初のステップ２５１では、メモリシステムを初期化する。このステップは、プロセッサ２７（図２）がＲＯＭ内のブートコード２９を実行して、ファームウェアを不揮発性メモリからＲＡＭ３１にロードすることを含む。初期化の後、このファームウェアの制御下、次に、ステップ２５３によって示されているようにメモリシステムはホストシステムからのコマンドを検索する。ホストコマンドが保留中である場合、図１２にリストされているコマンドのうちからコマンドを識別する。Ｒｅａｄコマンド（図１２Ａ）である場合、これをステップ２５５で識別し、ステップ２５７によって実行する。ステップ２５７を図２７を参照して以下に詳細に説明する。Ｒｅａｄコマンドでない場合、図２６のステップ２５９では、図１２ＡのＷｒｉｔｅ、ＩｎｓｅｒｔまたはＵｐｄａｔｅプログラムコマンドのいずれか１つを識別し、ステップ２６１によって実行する。ステップ２６１は、図２８の主題である。ＤｅｌｅｔｅまたはＥｒａｓｅコマンド（図１２Ｂ）である場合、これをステップ２６２で識別し、図３０に詳細に説明するようにステップ２６３で実行する。図２６のステップ２６４では、ホストからＩｄｌｅコマンド（図１２Ｄ）を識別し、その結果、図３１のフローチャートに示されているガーベッジコレクション動作２６５を生じる。図２６〜図３２のこの例を、前述したメタページおよびメタブロックと動作するメモリシステムについて説明するが、ページおよび／またはブロックで編成されたメモリシステムによっても実行することができる。
【０１７９】
ホストコマンドが、Ｒｅａｄ、Ｗｒｉｔｅ、Ｉｎｓｅｒｔ、Ｕｐｄａｔｅ、Ｄｅｌｅｔｅ、ＥｒａｓｅまたはＩｄｌｅ以外である場合、この特定の例では、このような別のコマンドを図２６のステップ２６７によって実行する。これらの他のコマンドのうち、図１２Ｂにリストし、かつ前述したＣｌｏｓｅおよびＣｌｏｓｅ＿ａｆｔｅｒコマンドのようなコマンドは、ガーベッジコレクション動作を待ち行列に追加させる。受信されたコマンドをステップ２５７，２６１，２６３，２６５または２６７のいずれかによって実行した後、次のステップ２６８は、ガーベッジコレクション優先待ち行列が空であるかどうかを問い合わせる。ガーベッジコレクション優先待ち行列が空である場合、処理はステップ２５３に戻って、保留中のコマンドが存在する場合、保留中のホストコマンドを実行する。ガーベッジコレクション優先待ち行列が空でない場合、別のホストコマンドの可能性を実現できるようにするよりはむしろ、処理はステップ２６５に戻ってガーベッジコレクションを継続する。図２６〜図３２のフローチャートを参照して説明する特定例の場合、前述した５つの異なるガーベッジコレクション待ち行列がある。すなわち、２つの優先待ち行列は、古いメタブロック（古いデータだけを有するメタブロック）と、古いデータを有する共通メタブロックとに対するものであり、古いデータはＥｒａｓｅコマンドによって生じる。２つの他の待ち行列は、古いメタブロックと、古いデータを有する共通メタブロックとに対するものであり、古いデータは、Ｅｒａｓｅコマンドの実行以外によって生じる。１つの待ち行列は、ガーベッジコレクションを行うべきファイルに対するものである。３つの非優先待ち行列にリストされたガーベッジコレクションに対して、別の保留中のホストコマンドには、リストされたガーベッジコレクション動作を行う優先順位が与えられる。しかし、優先待ち行列のガーベッジコレクション動作に対して、ガーベッジコレクションには、新たなホストコマンドの実行よりも上の優先順位が与えられる。すなわち、新たなホストコマンドを実行することができる前、優先ガーベッジコレクション動作のいずれも完了するまでホストを待機させることができる。その理由は、ホストが、Ｅｒａｓｅコマンドを用いることによって、メタブロック内のデータの消去に対して予め与えられた優先順位を優先待ち行列内に有するためである。優先ガーベッジコレクションは、結果として、比較的わずかな処理時間で生成される追加の消去済みメタブロックをも生じさせる。しかし、優先事項でない場合、ホストがアイドル状態にあるとき、ガーベッジコレクションはバックグラウンドで実行されるか、または、消去済みブロックプールを維持するのに必要なとき、他の動作と交互に行われる。いかなる優先ガーベッジコレクション動作も保留中にないことがステップ２６８によって決定された場合、次のステップはステップ２５３であって、新たなホストコマンドがあれば、これを実行する。
【０１８０】
図２６のステップ２５３に戻って、いかなるホストコマンドも保留中にない場合にガーベッジコレクション２６５を行い、所定の長さの時間中、ホストが非アクティブ状態またはアイドル状態にあること、または、最近受信されたホストコマンドがＩｄｌｅコマンドであったことがステップ２６９によって決定された場合、または、保留中のホストコマンドがＩｄｌｅコマンドであることがステップ２６４によって決定された場合、ガーベッジコレクション２６５は非優先ガーベッジコレクションを含む。これらの条件下で、ガーベッジコレクションは完全にバックグラウンドで実行される可能性が高い。
【０１８１】
図２６のステップ２５７におけるＲｅａｄコマンドの実行は、図２７のフローチャートの主題である。最初のステップ２７１は、図１９および図２２を参照して前に説明されたようにファイル索引テーブル（ＦＩＴ）を読み出すことである。ホストＲｅａｄコマンドは、読み出しが開始されるファイルのｆｉｌｅＩＤおよびファイル内のオフセットを含む（図１２Ａ参照）。一部のデータが不揮発性メモリから必要とされるごとに不揮発性メモリからＦＩＴを読み出す必要性を回避するために、読み出すべきファイルのＦＩＴ項目の全部または一部を不揮発性メモリからコントローラメモリ３１（図２）に読み出すのが好ましい。ステップ２７３では、データグループ番号カウンタを、開始オフセットが位置する要求されたファイルを構成するデータグループの数に初期化する。このことは、ホストによって指定された開始オフセットを、ホストによって指定されたファイルのＦＩＴ項目内のデータグループのオフセットと比較することによって行われる。次に、ステップ２７５では、データグループ長さカウンタを、ホストによって供給されたオフセットからデータグループの終わりまでの最初のデータグループ内のデータの量に初期化する。１つのデータグループは１度に読み出され、ステップ２７３およびステップ２７５は、最初のデータグループの読み出しを管理する２つのカウンタをセットアップする。読み出すべきデータの不揮発性メモリ内の最初の物理バイトアドレスを、最初のデータグループのＦＩＴ項目から決定する。グループ内のデータの論理オフセットおよび物理バイトアドレスは直線的に関連し、これによって、読み出しがデータグループの始まりで開始しない場合、開始バイトアドレスは、ホストから供給されたファイル内の開始オフセットから計算される。あるいはまた、データグループ長さカウンタの初期化を簡単にするため、各データグループの長さをＦＩＴのレコード２１９（図２２）に追加することができる。
【０１８２】
フローチャートのこの説明の残りの部分について、メモリシステムがメタブロックと動作し、前述したようにデータがメタページの単位で読み出されプログラムされると仮定される。ステップ２７７において、開始バイトアドレスを含む不揮発性メモリに記憶された最初のデータグループからデータメタページを読み出す。一般的に、読み出されたデータは、ホストに転送するためにコントローラバッファメモリ（例えば、図２のＲＡＭ３１）に書き込まれる。次に、ステップ２７９においてデータグループ長さカウンタを１つのメタページだけ減少させる。次に、ステップ２８１においてこのカウンタを読み出して、カウンタがゼロに達したかどうかを決定する。ゼロに達していない場合、読み出すべき最初のデータグループのデータがもっとある。しかし、ステップ２７７に戻って、順番に次のメタページのデータを読み出す前に、ステップ２８３は、ホストが別のコマンドを送出したかどうかを検査する。ホストが別のコマンドを送出した場合、読み出し動作を終了し、処理は、受信したコマンドを識別し、次にこのコマンドを実行するため、図２６のステップ２５３に戻る。ホストが別のコマンドを送出しなかった場合、図２７のステップ２７７およびステップ２７９において、次のメタページを読み出すことによって最初のデータグループの読み出しを継続する。この読み出しを、ステップ２８１によってデータグループ長さカウンタがゼロに到達したと決定されるまで継続する。
【０１８３】
データグループ長さカウンタがゼロに到達した場合、ステップ２８５においてこの場合もファイルのＦＩＴ項目を読み出して、ステップ２８７において、読み出すべき現在のファイルのデータグループがこれ以上あるかどうかを決定する。データグループがある場合、ステップ２８９において、次のデータグループを識別するためにデータグループ番号カウンタを更新し、ステップ２９１においてデータグループ長さカウンタを新たなグループ内のデータの長さに初期化する。ステップ２８３によって、保留中のホストコマンドが他にないと決定された場合、ステップ２７７において、新たなデータグループの最初のメタページを読み出す。次に、データのすべてを読み出すまで、新たなデータグループのメタページごとにステップ２７７およびステップ２７９を繰り返し、データのすべてを読み出した時点で、ステップ２８５およびステップ２８７は、さらなる別のデータグループが存在するかどうかを決定するなどである。ホストによって供給されたオフセットが読み出された後、ステップ２８７によって、ファイルのデータグループのすべてであると決定されると、処理は、別のホストコマンドを実行するために図２６のステップ２５３に戻る。
【０１８４】
ファイルが環状バッファとして用いられる特別な場合、図２６のステップ２５３に戻るよりはむしろ図２７のステップ２８７の後、ファイルの読み出しを繰り返すことができる。このことは、ステップ２８３において、データを同じファイルに書き込むホストコマンドに応答することによって、現在のファイルのデータが読み出し中にホストによってプログラムされる場合に生じうる。
【０１８５】
図２６のデータプログラム動作２６１の一例を図２８のフローチャートに示す。図１２Ａのデータプログラムコマンドの１つがホストから受信されるとき、このコマンドは、データが書き込まれるべきファイルのｆｉｌｅＩＤを含む。最初のステップ２９５は、プログラミングのため、指定されたファイルが現在開かれているかどうかを決定する。ファイルが開かれている場合、次のステップ２９７は、このファイルに対して（図２のＲＡＭ３１のような）コントローラバッファ内にデータがあるかどうかを決定する。データは、ホストシステムによってコントローラバッファメモリに転送され、次に、メモリシステムコントローラによってフラッシュメモリに転送される。
【０１８６】
しかし、ホストによって指定されたファイルが開かれていないとステップ２９５によって決定された場合、次のステップ２９９は、プログラミングのためにメモリシステムによって現在開かれたファイルの数が、メモリシステムによって許容されている同時に開くことができる最大数Ｎ１以上であるかどうかを問い合わせる。数Ｎ１はメモリシステム内で事前設定され、ファイルの５，８または何らかの他の数とすることができる。開かれたファイルの数がＮ１に満たない場合、次のステップ３０１は、データをプログラムするのに必要とされるシステムリソースをこのファイルに供給することによって新たなファイルを開かせ、処理はステップ２９７に進行する。しかし、ステップ２９９において、開いたファイルの数がＮ１以上であると決定された場合、ステップ３０３によって示されているように、現在開かれているファイルを最初に閉じる必要があり、その後、ステップ３０１において、新たなファイルを開くことができる。ステップ３０３において、開いたファイルを閉じるように選択する基準は変更することができるが、通常、ホストによってデータが最も長い間書き込まれなかった開かれたファイルである。このことから、ホストは、このファイルに近い将来データを書き込む可能性は低いということが推定される。しかし、このファイルにデータを書き込む場合、別の開いたファイルを閉じた後、必要ならば、そのとき、このファイルを再度開く。
【０１８７】
ステップ２９７において、現在のファイルの少なくとも１つのメタページのデータがコントローラバッファ内に存在すると決定されると、次のステップ３０５は、メモリアレイ内のメタブロックがプログラミングのために開かれているかどうかを決定する。メタブロックが開かれている場合、次に、ステップ３０７において、開いたメタブロックにコントローラバッファメモリからデータをプログラムする。メタブロックが開かれていない場合、ステップ３０８において、データをプログラムするのに必要とされるシステムリソースをメタブロックに供給することによって最初にメタブロックを開く。この例では、データは、開いたメモリメタブロックに１つのメタページの単位で一度に書き込まれる。この単位のデータを書き込んだ後、次のステップ３０９は、開かれた書き込みメタブロックがデータでいっぱいであるかどうかを決定する。書き込みメタブロックがデータでいっぱいでなければ、処理は一般的にステップ３１１およびステップ３１３を通過し、ステップ２９７に戻って、現在開かれているファイル内のデータの次のメタページをプログラムする処理を繰り返す。
【０１８８】
しかし、ステップ３０９によって、書き込みメタブロックがいっぱいであると決定される場合、ステップ３１５においてメタブロックを閉じ、ステップ３１７においてＦＩＴを更新し、ステップ３１７は、メモリメタブロック境界に達したので、現在のデータグループを閉じることを含む。次に、ステップ３１８において、優先順位の低い古いメタブロックガーベッジコレクション待ち行列のメタブロック項目を更新する。ステップ３１７においてＦＩＴを更新する間、書き込みメタブロックがいっぱいであることによって、現在のファイルの古いデータのすべてを含む別のメタブロックか、または、現在のファイルの古いデータを含む共通メタブロックである別のメタブロックが生成されたかどうかを決定する。別のメタブロックが生成された場合、ステップ３１８によって、このメタブロックを、ガーベッジコレクションのため、優先順位の低い適切なメタブロック待ち行列に追加する。次に、処理はステップ３１１に戻り、ステップ３１３を通過してステップ２９７に戻る。ステップ３０５およびステップ３０７を通過して今回は、以前のメタブロックがステップ３１５によって閉じられたばかりであるので、ステップ３０８は新たな書き込みメタブロックを開く。
【０１８９】
ステップ３０７を含む経路によって各メタページのデータが書き込まれた後、ステップ３１１は、消去済みメタブロックプール内に現在存在するメタブロックの数が、メモリシステムを効率良く動作するのに必要な決定された最小数Ｎ２を上回るかどうかを問い合わせる。メタブロックの数が最小数Ｎ２を上回る場合、ステップ３１３は、別のホストコマンドが受信されたかどうかを問い合わせる。保留中のホストコマンドが他にない場合、メモリにプログラムすべき次のメタページのデータについてステップ２９７を繰り返す。しかし、ホストコマンドが受信された場合、ステップ３１９においてＦＩＴを更新して、書き込まれたデータグループを閉じる。ステップ３２０において、（前述したステップ３１８に類似して）優先順位の低い古いメタブロックガーベッジコレクション待ち行列内のメタブロック項目を更新した後、処理は図２６のステップ２５３に戻る。
【０１９０】
しかし、図２８のステップ３１１において、データの記憶に対して消去済みメタブロックの不足がある（事前設定された数Ｎ２以下である）と決定された場合、フォアグラウンドでファイルまたは共通メタブロックにガーベッジコレクションを行うサブルーチンを実行して、消去済みメタブロックの数を増大させる。各メタページのデータがメモリに書き込まれた後ではなくむしろ、Ｎ３個ごとにメタページが書き込まれた後だけに、このようなガーベッジコレクションを実行するのが好ましい。書き込みメタブロックメタページプログラムカウンタは、プログラム動作の間でガーベッジコレクションなしに連続してプログラムされたホストデータのメタページの数のカウントを維持する。ガーベッジコレクションが実行されるたび、このカウンタはゼロにリセットされ、次に、メタページのデータがプログラムされるたびに１だけ増大する。ステップ３２１では、カウントが所定の数Ｎ３を上回るかどうかを決定する。プログラムカウンタのカウントが数Ｎ３を上回らない場合、ステップ３２３においてカウンタを１だけ増大して、ステップ３０７においてメタページがメモリに書き込まれたことを記録する。しかし、プログラムカウンタのカウントが数Ｎ３を上回る場合、ガーベッジコレクションはステップ３２５、ステップ３２７およびステップ３２９によって行われ、その後、ステップ３３１においてプログラムカウンタをゼロにリセットする。
【０１９１】
処理中のこの時点でのガーベッジコレクションの目的は、消去済みメタブロックプールに追加の消去済みメタブロックを生成することである。しかし、ステップ３２５、ステップ３２７およびステップ３２９を実行するたびにガーベッジコレクション動作の一部だけ実行するのが好ましい。コピー動作は、ホストがメモリを利用できない間隔の期間を最小限にし、従って、データプログラム性能に与える悪影響を最小限にするために長期にわたって展開される小規模な動作に分割される。これと同じ理由のため、部分的なガーベッジコレクション動作はＮ３個のプログラム周期ごとだけ実行される。システムにおいて数Ｎ２，Ｎ３を事前設定することができるが、遭遇することがある特定の条件に適合させるために、これらの数をメモリシステムの動作中でも決定することができる。
【０１９２】
１つ以上の追加の消去済みメタブロックを生成するため、ファイルまたは共通メタブロックに対する完全なガーベッジコレクション動作によって必要とされる時間の大部分が、有効データを１つ以上のコピーメタブロックへコピーすることによって要されるので、完全なガーベッジコレクション動作は、このコピー動作であって、このコピー動作は、図２８に示されているデータプログラムと主として交互に行われる。ステップ３２５は、図３１のフローチャートに関して説明されるガーベッジコレクション３２９にフォアグラウンドモードを選択する。次に、ガーベッジコレクションが行われたメタブロックから、予め消去されたコピーメタブロックへ特定の事前設定数のメタページのデータグループを連続してコピーする。ステップ３２７は、このように交互してコピーされたメタページのカウンタをリセットし、これによって、ステップ３２９において、事前設定数のメタページをコピーし、その後、動作は、ガーベッジコレクションステップからデータプログラムループへ戻る。次に、ステップ３２１によって参照される書き込みメタブロックメタページプログラムカウンタを、ガーベッジコレクション動作３２９ごとの後にステップ３３１によってリセットする。このことは、フォアグラウンドで別のガーベッジコレクション動作が行われ、従って、ガーベッジコレクションによって生じるデータプログラムの遅延を広げる前にＮ３個のメタページのデータをメモリに書き込ませる。
【０１９３】
ガーベッジ−プログラミングアルゴリズムの交互性を図２９の時刻表によって示す。ガーベッジコレクション動作の間で、Ｎ３個のメタページのデータはホストからメモリに連続して書き込まれる。各ガーベッジコレクション動作は、Ｎ４個のメタページのデータをコピーすることに限定され、その後、別のＮ３個のメタページのデータがプログラムされる。ガーベッジコレクション段階では、追加のメタページのデータをメモリシステムコントローラバッファに転送する前に、メモリシステムがガーベッジコレクションを完了するためにホストを待機させることができる。
【０１９４】
図２６の削除ファイルルーチン２６３の実行を図３０のフローチャートによって示す。削除ファイルルーチン２６３の主な目的は、削除されるファイルの古いデータを有する古いブロックおよび共通ブロックを識別し、次に、これらのブロックを適切なガーベッジコレクション待ち行列に配置することである。削除すべきファイルの名前または他の識別子と一緒にＤｅｌｅｔｅまたはＥｒａｓｅコマンド（図１２Ｂ）がメモリシステムによって受信されると、ステップ３３５は、データグループ番号カウンタをゼロに初期化する。ステップ３３７では、指定されたファイルを構成するメモリに記憶されているデータグループの識別子を獲得するためにファイルディレクトリおよびファイル索引テーブル（ＦＩＴ）を読み出す。次に、論理的に順々に各データグループを指すデータグループ番号カウンタの値を増大することによってファイルの各データグループを１つずつ検査する。
【０１９５】
データグループに対する最初の問い合わせ３３９は、データグループが共通メタブロック内に存在するかどうかを決定する。データグループが共通メタブロック内に存在する場合、ステップ３４１は、このメタブロックを共通ブロックガーベッジコレクション待ち行列の１つに追加する。ファイルがＥｒａｓｅコマンドによって削除される場合、メタブロックは共通メタブロック優先待ち行列に配置され、Ｄｅｌｅｔｅコマンドによる場合、他の共通メタブロック待ち行列に配置される。削除すべきファイルのデータグループを有する共通メタブロックのいずれも、ガーベッジコレクションを行うようにスケジュールされる。データグループが共通メタブロック内に存在しないことがステップ３３９によって決定された場合、次の問い合わせ３４３は、古いメタブロックガーベッジコレクション待ち行列に存在することによってガーベッジコレクションを行うようにメタブロック内でデータグループが既にスケジュールされたかどうかを決定する。ガーベッジコレクションを行うようにメタブロックが既にスケジュールされた場合、この同じ待ち行列にメタブロックを再度追加する必要はない。しかし、ガーベッジコレクションを行うようにメタブロックがまだスケジュールされていない場合、ステップ３４５によってメタブロックを古いメタブロックガーベッジコレクション待ち行列の１つに追加する。ファイルがＥｒａｓｅコマンドによって削除された場合、メタブロックは、古いメタブロック優先待ち行列に配置され、Ｄｅｌｅｔｅコマンドによる場合、他の古いメタブロック待ち行列に配置される。
【０１９６】
ステップ３４１またはステップ３４５が実行された後か、または、ステップ３４３の問い合わせが肯定応答であった場合、１つのデータグループの処理は完了する。次のステップ３４７は、データグループ番号カウンタの値を増大する。次に、問い合わせ３４９は、ファイルに別のデータグループが存在するかどうかを決定する。ファイルに別のデータグループが存在する場合、処理はステップ３３９に戻り、次のデータグループに対して繰り返される。ファイルに別のデータグループが存在しない場合、削除すべきファイルのデータを含むメタブロックのすべてが、古いメタブロックおよび共通メタブロックガーベッジコレクション待ち行列に入っていることが分かる。次に、ステップ３５１においてＦＩＴを更新し、削除すべきファイルのデータグループレコードを古くする。次に、ＦＩＴが圧縮されると、一般的に、古いデータグループのＦＩＴのレコードを削減する。最後のステップ３５３では、ファイルディレクトリ２０１（図２０）を更新して、そこから削除済みファイルを除去する。
【０１９７】
図３１のフローチャートには、図２６のガーベッジコレクション動作２６５および図２８のガーベッジコレクション動作３２９の特定例を示す。このアルゴリズムは、ホストがＩｄｌｅコマンドを送信する場合（図２６のステップ２６４）、または、ホストが一時アイドル状態であった場合、バックグラウンドで実行され（図２６のステップ２６５）、または、Ｎ２個に満たない消去済みメタブロックが消去済みメタブロックプールにとどまる場合、プログラム動作中、フォアグラウンドで実行される（図２８のステップ３２９）。最初の問い合わせ３５５は、まだ完了されていない進行中のガーベッジコレクション動作があるかどうかを決定する。図３１のこの説明から、処理は、ホストが別のコマンドを送出する場合、または、データのコピーが他の動作と交互に行われる場合のような特定の条件下、ガーベッジコレクションから生じるということが分かる。従って、保留中の未完成なガーベッジコレクション動作が存在する場合、保留中のガーベッジコレクションに優先順位が与えられているので、次のステップはステップ３５７である。しかし、保留中のガーベッジコレクション動作が存在しないことがステップ３５５によって決定された場合、次のステップ３５６は、様々なガーベッジコレクション待ち行列を検索して、これらの中に少なくとも１つの項目が存在するかどうかを確かめる。ガーベッジコレクション待ち行列に項目が存在する場合、次のステップ３５８は項目の１つを選択し、項目が２つ以上存在する場合、前述した優先順位に従って項目の１つを選択する。古いメタブロックブロック待ち行列において順序が次にあるメタブロックのガーベッジコレクションには、一般的に、共通メタブロック待ち行列のメタブロック、または、ガーベッジコレクションを行うべきファイルの待ち行列のファイルよりも上の優先順位が与えられる。その理由は、古いメタブロックをガーベッジコレクションすることによって、いかなるデータもコピーする必要がないのでさらに高速に消去済みメタブロックプールの大きさを増大させることができるためである。
【０１９８】
処理がファイル、共通メタブロックおよび古いメタブロックに対して異なるので、次の一連のステップ３６０、ステップ３６２およびステップ３６６は、選択された待ち行列項目に対してガーベッジコレクションの対象物を決定する。問い合わせ３６０は、対象が、ガーベッジコレクションを行うべきファイルであるかどうかを尋ねる。対象がファイルである場合、ステップ３７０およびステップ３７２においてファイルのＦＩＴ項目を順々に読み出して特定のカウンタおよびカウントを設定する。ステップ３７０において、第１のカウンタをファイル内のデータグループの数に設定し、第２のカウンタをファイルの最初のデータグループ内のデータのメタページの数（長さ）に設定する。データグループの長さが項目の一部でない場合、この長さをＦＩＴデータグループ項目から計算することができる。あるいはまた、図２０および図２２に示されているように、必要となるたびにデータグループの長さを計算する必要性を削減するため、各データグループの長さを項目の一部としてＦＩＴに含めることができる。ステップ３７２では、古いデータまたは他のファイルからのデータを含むメモリブロックに記憶された現在のファイルデータのメタページの数に第３のカウンタを設定する。これらのデータは、移動する必要がある現在のファイルのデータである。この第３のカウンタは、ファイル内のすべての古いデータグループおよび無効なデータグループを無視するのが好ましい。最後に、ファイルの有効データが整数のメタブロックに圧縮され満たされた場合に生じるデータの残留メタページの数のカウントを行う。すなわち、残留メタページカウントは、ガーベッジコレクションに含まれるファイルのデータをメタブロックのすべてが含めば、共通メタブロックまたは部分的に満たされたメタブロックを占有する必要があるメタブロック未満のファイルのデータの量である。これらの３つのカウンタを設定し、残留メタページカウントを行い記憶した後、次のステップ３５９は、ファイルのデータにガーベッジコレクションを開始する。
【０１９９】
ステップ３６０に戻り、ステップ３５８によって選択された項目がファイルでない場合、次の問い合わせ３６２は、選択された項目が、ガーベッジコレクションを行うべき共通メタブロックであるかどうかを決定する。選択された項目が共通メタブロックである場合、図３２の共通メタブロックガーベッジコレクション３６４を行う。選択された項目が共通メタブロックでない場合、問い合わせ３６６は、選択された項目が、図３０のステップ３４５によって古いメタブロック待ち行列に追加されたような古いメタブロックかどうかを決定する。選択された項目が古いメタブロックである場合、選択されたメタブロックをステップ３６８において消去する。共通メタブロックガーベッジコレクション３６４の後、メタブロック消去３６８の後、または、問い合わせ３６６が否定応答を生じた場合、処理は図２６のステップ２５３に戻る。ガーベッジコレクション動作が未完成のままである場合、次回、ガーベッジコレクションアルゴリズムが実行されたときに再開される。
【０２００】
ステップ３５５に戻り、保留中のガーベッジコレクションがある場合、これをさらに処理する。ガーベッジコレクション待ち行列から選択された新たな項目に対するステップ３６０のように、図３１のステップ３５７は、保留中の動作がファイルに対するものかどうかを決定する。保留中の動作がファイルに対するものでない場合、新たな項目に対して前に説明されたステップ３６２、ステップ３６４、ステップ３６６およびステップ３６８の処理を実行し、次に、図２６のステップ２５３に戻ることによってガーベッジコレクションを終了する。
【０２０１】
再開されたガーベッジコレクションがファイルに対するものであることが図３１のステップ３５７によって決定された場合、次に、問い合わせ３５９を行う。以下の処理は、（ステップ３５７を介して）ガーベッジコレクションが再開されるファイルに対するもの、または、カウンタおよび残留メタページカウントがステップ３７０およびステップ３７２によって設定される（ステップ３６０を介して）待ち行列から選択された新たなファイルに対するものとほぼ同じである。ファイルのガーベッジコレクションが進行中であり、ステップ３５７を介して再開されている場合、データグループ番号およびファイルメタページ番号カウンタ、並びに残留メタページカウントは、ファイルのガーベッジコレクションが最初に開始されたときに設定されている。データグループ番号およびメタページカウンタは、現在のファイルの以前の部分的なガーベッジコレクションによって最初に計算された値と異なる値に減少されている可能性が高い。ファイルのガーベッジコレクションが一時中断されるとき、４つすべてを記憶し、次に、同じファイルの再開された処理中にアクセスする。
【０２０２】
共通のステップ３５９は、まだコピーされていない現在のデータグループ内に１つ以上のメタページが存在するかどうかを問い合わせる。このことは、データグループ長さカウンタを参照することによって決定される。その後のステップによって有効データグループの１つのメタページを同時に検査しコピーする。ステップ３５９によって、保留中のデータグループに残っているデータが決定された場合、次の問い合わせ３６１は、コピーメタブロックが開いているかどうかを決定する。コピーメタブロックが開いている場合、ステップ３６３によって、ガーベッジコレクションが行われるファイルの現在のデータグループのデータのメタページを、記憶されたメタブロックから読み出し、ステップ３６５においてコピーメタブロックに書き込む。次に、ステップ３６７においてデータグループ長さカウンタを１つのメタページだけ減少し、ステップ３６９においてファイルメタページカウンタを１だけ減少する。
【０２０３】
コピーメタブロックが開かれていないことがステップ３６１によって決定された場合、次のステップ３７１は、ガーベッジコレクションが行われるファイルが、開いたファイルであるかどうかを決定する。ガーベッジコレクションが行われるファイルが開いたファイルである場合、次のステップ３７３は、コピーメタブロックを開き、次に、処理は、前述したステップ３６３に進行する。しかし、ガーベッジコレクションが行われるファイルが開いたファイルでない場合、次のステップ３７５は、ファイルメタページカウンタの減少されたカウントが残留メタページカウントに等しいかどうかを問い合わせる。ファイルメタページカウンタの減少されたカウントが残留メタページカウントに等しくない場合、ステップ３７３によってコピーメタブロックを開く。しかし、ファイルメタページカウンタの減少されたカウントが残留メタページカウントに等しい場合、コピーすべき現在のファイル内にメタブロックのデータが残っていないことを意味する。従って、ステップ３７７では、残留データを共通メタブロックへコピーするため、開いた共通メタブロックを識別する。次に、ステップ３６３およびそれ以外の処理はコピーであって、現在のファイルの現在のデータグループの残りのメタページは共通メタブロックへコピーされる。別のメタブロックが満たされる現在のファイルに他のデータグループを書き込むことができるので、ステップ３７１によって決定されるように、ガーベッジコレクションが行われるファイルが、開いたファイルである場合、この経路はとられない。開いたファイルが閉じられた後、閉じられたファイルをガーベッジコレクションの待ち行列に配置し、この時点で、ステップ３７７によって、いずれの残留データも共通ブロックへコピーする。
【０２０４】
追加のメタページのデータを書き込んだ後、図３１の問い合わせ３７９は、現在、コピーメタブロックがいっぱいであるかどうかを決定する。コピーメタブロックがいっぱいである場合、ステップ３８１においてコピーメタブロックを閉じ、このことを反映するようにステップ３８３によってＦＩＴを更新する。コピーメタブロックがいっぱいでない場合、またはステップ３８３の後、問い合わせ３８５は、ガーベッジコレクションが行われるメタブロックの全データが現在古い状態にされているかどうかを決定する。メタブロックの全データが現在古い状態にされている場合、ステップ３８７においてメタブロックを消去する。メタブロックの全データが現在古い状態にされていない場合、または、メタブロックを消去した後、問い合わせ３８９は、プログラム動作中、図２８のステップ３２５によってフォアグラウンドモードが設定されたかどうかを尋ねる。フォアグラウンドモードが設定されていない場合、図３１のステップ３９１は、ホストコマンドが保留中であるかどうかを決定する。ホストコマンドが保留中である場合、ステップ３９２によって決定されたように進行中のガーベッジコレクションが優先事項でなければ、ステップ３９３においてＦＩＴを更新することによってガーベッジコレクションを一時中断し、次に、図２６のステップ２５３に戻る。しかし、ステップ３９１によって決定されたようにホストコマンドが保留中でない場合、または、保留中のホストコマンドが存在し、ステップ３９２によって決定されたように進行中のガーベッジコレクションが優先事項でない場合、処理は問い合わせ３５９に戻って、次のメタページのデータを現在のファイルメタブロックからコピーメタブロックへコピーする。
【０２０５】
フォアグラウンドモードが設定されたことを図３１の問い合わせ３８９が決定した場合、次のステップ３９５は、図２８のステップ３２７によってリセットされたコピーメタブロックメタページカウンタの値を増大する。事前設定の数Ｎ４のメタページが連続してコピーされたことをステップ３９７が決定した場合、次のステップ３９９はフォアグラウンドモードをリセットし、ステップ３９３によってＦＩＴを更新する。しかし、数Ｎ４に達する前に、コピーすべきメタページがもっとある場合、保留中のホストコマンドがあることを問い合わせ３９１が決定しない限り、処理はステップ３５９を続ける。保留中のホストコマンドがない場合、コピー動作を中断し、処理を図２６のステップ２５３に戻す。
【０２０６】
問い合わせ３５９に戻り、データグループ長さカウントがゼロである場合、ファイルメタブロックからコピーメタブロックへの１つのデータグループのコピー動作が完了したことを意味する。この条件下、ステップ４０１は、この条件を反映するようにＦＩＴを更新する。次に、ステップ４０３において、データグループ番号カウンタを参照して、ガーベッジコレクションが行われる現在のファイルが別のデータグループを含むかどうかを決定する。ガーベッジコレクションが行われる現在のファイルが別のデータグループを含まない場合、ファイルのガーベッジコレクションは完了した。次に、処理をステップ３５６に戻して、待ち行列から順番に次のファイルまたはメタブロックにガーベッジコレクションを行う。現在のファイルのガーベッジコレクションの完了は、再開することができる進行中のファイルのガーベッジコレクションがもはや存在しないことを意味するので、処理はステップ３５５に戻らない。
【０２０７】
ステップ４０３から、コピーすべき現在のファイルのデータグループが少なくとももう１つ存在すると分かった場合、ステップ４０５において、この次のデータグループを含むメタブロックが、古い状態にある他のデータも含むかどうかを決定する。前述したように、ファイルの古いデータを含むメタブロックにガーベッジコレクションが行われるが、メタブロックが、ファイルの残留データを含む共通メタブロックまたは未完成なメタブロックでない限り、ファイルの古いデータを含まないメタブロックにガーベッジコレクションを行わないことが好ましい。従って、次のデータグループのメタブロック内に古いデータが存在することがステップ４０５によって決定された場合、ステップ４０７によってデータグループ番号カウンタを、順序が次にあるデータグループの数に更新し、ステップ４０９において、新たなデータグループ内のデータの量でデータグループ長さカウンタを初期化する。次に、処理はステップ３６１に進み、前述したように、ファイルの新たなデータグループから最初のメタページのデータを、コピーメタブロック内の次の消去済みメタページへコピーする。
【０２０８】
しかし、次のデータグループが存在するメタブロック内にいかなる古いデータも存在しないことがステップ４０５によって決定された場合でも、（１）次のデータグループが共通メタブロック内に存在するか、または、（２）未完成のメタブロック内に存在し、ファイルが、閉じられたファイルであれば、このメタブロック内のデータのガーベッジコレクションを依然として行いうる。最初に、現在のデータグループが共通メタブロック内に存在するかどうかについて問い合わせ４１１を行う。現在のデータグループが共通メタブロック内に存在する場合、次のステップ４１３は、後でガーベッジコレクションを行うため、共通メタブロックを共通メタブロックガーベッジコレクション待ち行列に追加するが、処理はステップ４０７およびステップ４０９について継続し、データグループ番号カウンタおよびデータグループ長さカウンタを、以下に参照されるステップ３６１によってコピーする次のメタブロックの数および長さに更新する。しかし、現在のデータグループが共通メタブロック内に存在しない場合、ステップ４１５は、現在のデータグループが未完成のメタブロック内に存在するかどうかを問い合わせる。すなわち、ステップ４１５は、現在のデータグループが、（図１５のデータグループＦ３，Ｄ３のような）少なくとも最小量の消去済み容量を依然として有するメタブロック内に存在するかどうかを決定する。現在のデータグループが未完成のメタブロック内に存在しない場合、現在のデータグループがコピーされるのではなくむしろ、処理がステップ４０３に戻って、ファイルの次のデータグループが存在する場合、これを処理する。しかし、現在のデータグループが未完成のメタブロック内に存在する場合、次の問い合わせ４１７は、未完成のメタブロックが、開いたファイルのデータを含むかどうかを尋ねる。未完成のメタブロックが開いたファイルのデータを含む場合、問い合わせ４０３に戻って、ファイルのさらなるデータグループについて継続することによって現在のデータグループのコピーもスキップする。しかし、次のデータグループが存在するメタブロックが、開いたファイルのデータを含まない場合、以下に参照されるステップ４０７、ステップ４０９およびステップ３６１を次のデータグループについて行う。
【０２０９】
図３１のステップ３５６に戻って、いかなるファイルまたはメタブロックもガーベッジコレクション待ち行列に存在しないと決定された場合であっても、ガーベッジコレクションを行うことができる。いかなるファイルまたはメタブロックもガーベッジコレクション待ち行列に存在しない場合、処理を終了するよりはむしろ、ステップ４２１が、Ｎ２を上回る消去済みメタブロックが消去済みメタブロックプール内に存在するかどうかを検査する。Ｎ２を上回る消去済みメタブロックが消去済みメタブロックプール内に存在する場合、ガーベッジコレクション処理を終了し、図２６のステップ２５３に戻る。しかし、Ｎ２を上回る消去済みメタブロックがシステム内に存在しない場合、ステップ４２１からガーベッジコレクションを実行する機会を得る。このようなガーベッジコレクションは、ステップ４２３によって示されているように、開いたファイルが存在する場合、これについて行うことができる。待ち行列内に何も存在しないので、プール内の消去済みメタブロックの数がＮ２以下である場合、さらなる消去済みメタブロックの潜在的なソースは他に何も存在しない可能性が高い。２つ以上の開いたファイルが存在する場合、ステップ４２５において、それらのうちの１つを選択する。次に、処理は、開かれたファイルについて、前述したようにステップ３７０、ステップ３７２およびステップ３５９を介して進行する。
【０２１０】
共通メタブロック内のデータグループに対して現在のガーベッジコレクション動作が行われることが図３１の問い合わせ３６２によって決定された場合、ガーベッジコレクション３６４は、前述した他のメタブロックの場合と多少異なる。図３２のフローチャートは、共通メタブロックのガーベッジコレクションを概説する。ステップ４３１は、ガーベッジコレクションが進行中であるかどうか、従って、再開されるかどうかを尋ねる。ガーベッジコレクションが進行中である場合、データグループ長さカウンタは、ガーベッジコレクションが一時中断されたときの最終値を保持する。ガーベッジコレクションが進行中でない場合、ステップ４３５において、処理の対象である最初のデータグループのＦＩＴを参照することによってデータグループ番号カウンタを最初に初期化し、次に、ステップ４３３によって、このデータグループの長さを決定する。
【０２１１】
データグループ長さカウンタがゼロを上回っていることがステップ４３３によって決定された場合、現在のデータグループのコピーを開始する。ステップ４３７によって、現在のデータグループのメタページを共通メタブロックから読み出し、ステップ４３９によって、開いた共通メタブロックにプログラムする。次に、ステップ４４１では、データグループ長さカウンタを１つのメタページだけ減少する。ステップ４４３によって示されているようにガーベッジコレクションをフォアグラウンドで行う場合、ステップ４４５によって、コピーメタブロックメタページカウンタを１だけ増大する。このカウンタは、連続してコピーされたデータのメタページの数を追跡し続ける。このカウントが所定の数Ｎ４を上回っていることをステップ４４７によって決定された場合、ステップ４４９において処理はフォアグラウンドモードを終了させる。その後、ステップ４５１において、ＦＩＴを更新し、次に、処理は図２６のステップ２５３に戻る。
【０２１２】
コピーメタブロックメタページカウンタがＮ４以下の値を有することが図３２のステップ４４７によって決定された場合、次のステップは、ホストコマンドが保留中であるかどうかを問い合わせる。ホストコマンドが保留中である場合、ステップ４５１においてＦＩＴを更新し、処理は図２６のステップ２５３に戻って、保留中のホストコマンドを実行することができる。ホストコマンドが保留中でない場合、処理は図３２のステップ４３３に戻って、現在のデータグループに別のデータメタページが存在するかどうかを問い合わせ、現在のデータグループに別のデータメタページが存在する場合、古い共通メタブロックからデータメタページを、開いた共通メタブロックへコピーするなどとなる。これと同様に、ステップ４４３において、ガーベッジコレクションがフォアグラウンドで実行されないことが決定された場合、次に、ステップ４５３を実行する。ステップ４５３によって決定されたように、ホストコマンドが保留中である場合を除いて、処理は、ステップ４４７を迂回したので、コピーメタブロックメタページカウンタがＮ４を上回っているかどうかにかかわらず、現在のデータグループ内のデータの次のメタページをコピーする可能性があるステップ４３３に戻る。この場合、ガーベッジコレクションはバックグラウンドで実行される。
【０２１３】
図３２のステップ４３３に戻って、データグループ長さカウントがゼロを上回っていない場合、現在のデータグループの全メタページがコピーされたことが分かる。次に、ステップ４５５においてＦＩＴを更新し、ステップ４５７によって、ガーベッジコレクションが行われる共通メタブロックに別のデータグループが存在するかどうかを決定する。共通メタブロックに別のデータグループが存在しない場合、ステップ４５９において、古い共通メタブロックを消去し、処理は図２６のステップ２５３に戻る。しかし、共通メタブロックに別のデータグループが存在する場合、ステップ４６１によってデータグループ番号カウンタを更新する。次に、ステップ４６３において、共通メタブロック索引からＦＩＴポインタを読み出し、ステップ４６５において、このポインタによって定義されたＦＩＴ項目を読み出す。ステップ４６７によって決定されたように、ＦＩＴ項目が現在のデータグループに一致する場合、問い合わせ４６８は、現在のデータグループが、既に識別された残留データの一部であるかどうかを決定する。現在のデータグループが既に識別された残留データの一部である場合、ステップ４６９によって、データグループ長さカウンタを、ＦＩＴから読み出されたデータグループの長さに初期化する。
【０２１４】
しかし、ステップ４６８において、現在のデータグループが既存の残留データ内に存在しないと決定された場合、ステップ４７０において、現在のデータグループが一部である新たな残留データを識別する。次に、ステップ４７１では、新たな残留データの全データを記憶するのに充分な空間を有する開いた共通ブロックを識別する。このことは、残留データが２つ以上のデータグループを含む場合、２つ以上の異なるメタブロックの間でファイルの残留データを分割しないようにする。残留データを分割することは、２つ以上のデータグループが独立してコピーされる場合にも生じることがある。この場合、第１のデータグループを記憶するのに充分な消去済み空間を有するが、第２のデータグループを記憶するのに充分な空間を持たない共通ブロックに第１のデータグループをコピーすることがある。次に、第２のデータグループを、異なる共通ブロックへコピーすることになる。このことは、ファイルの残留データを２つの異なるメタブロック間で分割すべきでないので望ましくない。ファイルの残留データがこのように分割される場合、ファイルのガーベッジコレクションまたは共通ブロックのガーベッジコレクションには、より多くの時間がかかる。
【０２１５】
次に、ステップ４６９によって、現在のデータグループのデータグループ長さカウンタを初期化する。ステップ４３７およびステップ４３９によって、現在のデータグループのデータの最初のメタページを共通メタブロックから、識別された開いた共通メタブロックへコピーする。しかし、ＦＩＴ項目が現在のデータグループに一致しないことがステップ４６７によって決定された場合、処理はステップ４５７に戻って、共通メタブロック内に別のデータグループが存在するかどうかを決定する。
【０２１６】
現在の共通メタブロックの有効データグループのすべてが、予め消去されたメタブロックへ、または、１つ以上の開いた共通メタブロックへコピーされるまで、図３２のフローチャートに示されているガーベッジコレクションは継続する。予め消去されたメタブロックは、コピー後、新たな共通メタブロックとなる。異なるファイルのデータグループを、異なる開いた共通メタブロックへコピーすることができる。共通メタブロックは古いデータグループを含んでいたので、ガーベッジコレクション待ち行列に前もって配置されていた。共通メタブロック内への各有効なデータグループのデータの全メタページの完全な転送は、図３２のステップを介して、このようなメタページごとに一回の受け渡しを要する。ガーベッジコレクションがフォアグラウンドで行われる場合、または、フォアグラウンドまたはバックグラウンドで動作しているときに新たなホストコマンドが受信されるとき、このコピー動作をＮ４個のメタページごとに中断することができる。
【０２１７】
数Ｎ３，Ｎ４を永続的に事前設定する代わりとして、ホストのデータプログラミングパターンに応答してメモリシステムコントローラによって数Ｎ３，Ｎ４を変更して、一様なデータプログラム速度を維持することができる。
【０２１８】
動作中のメモリブロックの様々な状態
図３３には、前述した種類の直接ファイル記憶メモリシステム内におけるシステムのメモリブロックまたはメタブロックの様々な個々の状態とこれら状態の遷移とを示す。
【０２１９】
左側の列では、ブロック５０１が、消去済みブロックプール内で消去済み状態であると示されている。
【０２２０】
次の列では、ブロック５０３，５０５，５０７は各々、何らかの有効データを含むが、ホストからのデータを書き込むことができる消去済み容量も有する。書き込みブロック５０３は単一ファイルの有効データで部分的に書き込まれ、ファイルのさらなるデータがホストによって供給されたとき、このブロックにファイルのさらなるデータを書き込む必要がある。コピーブロック５０５は単一ファイルの有効データで部分的に書き込まれ、ファイルのさらなるデータがファイルのガーベッジコレクション中にコピーされるとき、このブロックにファイルのさらなるデータを書き込む必要がある。開いた共通ブロック５０７は２つ以上のファイルの有効データで部分的に書き込まれ、ガーベッジコレクション中、任意のファイルの残留データグループをこのブロックに書き込むことができる。
【０２２１】
次の列のブロック５０９，５１１はファイルデータで満たされている。ファイルブロック５０９は、単一ファイルの有効データで満たされている。共通ブロック５１１は、２つ以上のファイルの有効データで満たされている。
【０２２２】
図３３の右側の列の１つ手前の列は、何らかの古いデータを各々含むブロック５１３，５１５，５１７，５１９，５２１を含む。古いファイルブロック５１３は、単一ファイルの有効データおよび古いデータの任意の組み合わせで満たされている。古い書き込みブロック５１５は、単一ファイルの有効データおよび古いデータの任意の組み合わせで部分的に書き込まれ、このファイルのさらなるデータがホストによって供給されたとき、ファイルのさらなるデータをこのブロックに書き込む必要がある。古いコピーブロック５１７は、単一ファイルの有効データおよび古いデータの任意の組み合わせで部分的に書き込まれている。古い開いた共通ブロック５１９は、２つ以上のファイルの有効データおよび古いデータの任意の組み合わせで部分的に書き込まれている。古い共通ブロック５２１は、２つ以上のファイルの有効データおよび古いデータの任意の組み合わせで部分的に満たされている。
【０２２３】
図３３の右側の列の古いブロック５２３は、古いデータだけを含む。
【０２２４】
図３３に示されているブロック状態間の個々のブロックの遷移も、小文字と共にラベル付けされた線によって示されている。これらの遷移は以下のとおりである。
ａ−消去済みブロック５０１から書き込みブロック５０３へ。すなわち、単一ホストファイルのデータは、消去済みブロックに書き込まれる。
ｂ−書き込みブロック５０３から書き込みブロック５０３へ。すなわち、ホストからの単一ファイルのデータは、このファイルの書き込みブロックに書き込まれる。
ｃ−書き込みブロック５０３からファイルブロック５０９へ。すなわち、ホストからの単一ファイルのデータは、このファイルの書き込みブロックをいっぱいにするために書き込まれる。
ｄ−ファイルブロック５０９から古いファイルブロック５１３へ。すなわち、ファイルブロックのデータの一部は、更新バージョンのデータがホストによってこのファイルの書き込みブロックに書き込まれた結果として古くなる。
ｅ−古いファイルブロック５１３から古いブロック５２３へ。すなわち、古いファイルブロック内のすべての有効データは、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｆ−書き込みブロック５０３から古い書き込みブロック５１５へ。すなわち、書き込みブロック内のデータの一部は、更新バージョンのデータがホストによって同じ書き込みブロックに書き込まれたか、または、ガーベッジコレクション中、このデータが別のブロックへコピーされた結果として古くなる。
ｇ−古い書き込みブロック５１５から古い書き込みブロック５１５へ。すなわち、ホストからの単一ファイルのデータは、このファイルの古い書き込みブロックに書き込まれる。
ｈ−古い書き込みブロック５１５から古いファイルブロック５１３へ。すなわち、ホストからの単一ファイルのデータは、このファイルの古い書き込みブロックをいっぱいにするために書き込まれる。
ｉ−古い書き込みブロック５１５から古いブロック５２３へ。すなわち、古い書き込みブロック内のすべての有効データは、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｊ−消去済みブロック５０１からコピーブロック５０５へ。すなわち、ガーベッジコレクション中、単一ファイルのデータは、別のブロックから消去済みブロックへコピーされる。
ｋ−書き込みブロック５０３からコピーブロック５０５へ。すなわち、ガーベッジコレクション中、単一ファイルのデータは、別のブロックからこのファイルの書き込みブロックへコピーされる。
ｌ−コピーブロック５０５からコピーブロック５０５へ。すなわち、ガーベッジコレクション中、単一ファイルのデータは、別のブロックからこのファイルのコピーブロックへコピーされる。
ｍ−コピーブロック５０５からファイルブロック５０９へ。すなわち、ガーベッジコレクション中、別のブロックから単一ファイルのデータは、このファイルのコピーブロックをいっぱいにするようにコピーされる。
ｎ−コピーブロック５０５から書き込みブロック５０３へ。すなわち、ガーベッジコレクション中、ファイルが再度開かれたとき、ホストからの単一ファイルのデータは、このファイルのコピーブロックに書き込まれる。
ｏ−コピーブロック５０５から古いコピーブロック５１７へ。すなわち、コピーブロック内のデータの一部または全部は、更新バージョンのデータがホストによってこのファイルの書き込みブロックに書き込まれたか、または、このファイルがホストによって削除された結果として古くなる。
ｐ−古いコピーブロック５１７から古いブロック５２３へ。すなわち、古いコピーブロック内のすべての有効データは、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｑ−書き込みブロック５０３から開いた共通ブロック５０７へ。すなわち、ガーベッジコレクション中、ファイルの残留データは、閉じられた異なるファイルの書き込みブロックに書き込まれる。
ｒ−コピーブロック５０５から開いた共通ブロック５０７へ。すなわち、ガーベッジコレクション中、ファイルの残留データは、異なるファイルの残留データを含むコピーブロックに書き込まれる。
ｓ−開いた共通ブロック５０７から開いた共通ブロック５０７へ。すなわち、ガーベッジコレクション中、ファイルの残留データは、異なるブロックから開いた共通ブロックへコピーされる。
ｔ−開いた共通ブロック５０７から古い開いた共通ブロック５１９へ。すなわち、開いた共通ブロック内の１つのファイルのデータの一部または全部は、更新バージョンのデータがホストによってこのファイルの書き込みブロックに書き込まれたか、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｕ−古い開いた共通ブロック５１９から古いブロック５２３へ。古い開いた共通ブロック内のすべての有効データは、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｖ−開いた共通ブロック５０７から共通ブロック５１１へ。すなわち、ファイルの残留データグループは、ガーベッジコレクション中、このファイルの開いた共通ブロックをいっぱいにするために別のブロックからコピーされる。
ｗ−共通ブロック５１１から古い共通ブロック５２１へ。すなわち、共通ブロック内の１つのファイルのデータの一部または全部は、更新バージョンのデータがホストによってこのファイルの書き込みブロックに書き込まれたか、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｘ−古い共通ブロック５２１から古いブロック５２３へ。すなわち、古い共通ブロック内のすべての有効データは、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ｙ−書き込みブロック５０３から古いブロック５２３へ。すなわち、書き込みブロック内の単一ファイルのすべての有効データは、このファイルがホストによって削除された結果として古くなる。
ｚ−コピーブロック５０５から古いブロック５２３へ。すなわち、コピーブロック内のすべての有効データは、ガーベッジコレクション中、このデータが別のブロックへコピーされたか、または、このファイルがホストによって削除された結果として古くなる。
ａａ−ファイルブロック５０９から古いブロック５２３へ。すなわち、ファイルブロック内の全データは、ファイルがホストによって削除された結果として古くなる。
ａｂ−古いブロック５２３から消去済みブロック５０１へ。すなわち、古いブロックは、ガーベッジコレクション中、消去される。
【０２２５】
結論
本発明の例示的な実施形態を参照して本発明の様々な態様を説明してきたが、当然のことながら、本発明は、特許請求の範囲の全範囲内においてその権利が保護されるべきであることが理解できよう。
【図面の簡単な説明】
【０２２６】
【図１】ホストと、現在の実施状況では接続された不揮発性メモリシステムとを示す概要図である。
【図２】図１の不揮発性メモリシステムとして用いる例示的なフラッシュメモリシステムを示すブロック図である。
【図３】図２のシステムに用いることができるメモリセルアレイの代表的な回路図である。
【図４】図２のシステムの物理メモリ編成例を示す。
【図５】図４の物理メモリの一部を示す拡大図である。
【図６】図４および図５の物理メモリの一部を示すさらなる拡大図である。
【図７】ホストと再プログラム可能なメモリシステムとの間の一般的な従来技術の論理アドレスインターフェイスを示す。
【図８】ホストと再プログラム可能なメモリシステムとの間の一般的な従来技術の論理アドレスインターフェイスを、図７とは異なるように示す。
【図９】本発明によるホストと再プログラム可能なメモリシステムとの間の直接ファイル記憶インターフェイスを示す。
【図１０】本発明によるホストと再プログラム可能なメモリシステムとの間の直接ファイル記憶インターフェイスを、図９とは異なるように示す。
【図１１】例示的なメモリシステムの機能的階層を示す。
【図１２Ａ】例示的な一連の直接ファイルインターフェイスコマンドを示す。
【図１２Ｂ】例示的な一連の直接ファイルインターフェイスコマンドを示す。
【図１２Ｃ】例示的な一連の直接ファイルインターフェイスコマンドを示す。
【図１２Ｄ】例示的な一連の直接ファイルインターフェイスコマンドを示す。
【図１２Ｅ】例示的な一連の直接ファイルインターフェイスコマンドを示す。
【図１３Ａ】データファイルをメモリに直接書き込む第１の例を示す。
【図１３Ｂ】データファイルをメモリに直接書き込む第２の例を示す。
【図１３Ｃ】データファイルをメモリに直接書き込む第３の例を示す。
【図１３Ｄ】データファイルをメモリに直接書き込む第４の例を示す。
【図１４Ａ】単一データファイルをメモリに直接書き込む一連の書き込みを示す。
【図１４Ｂ】単一データファイルをメモリに直接書き込む一連の書き込みを示す。
【図１４Ｃ】単一データファイルをメモリに直接書き込む一連の書き込みを示す。
【図１４Ｄ】単一データファイルをメモリに直接書き込む一連の書き込みを示す。
【図１４Ｅ】単一データファイルをメモリに直接書き込む一連の書き込みを示す。
【図１５】図１４Ｅに示されているデータファイルにガーベッジコレクションを行った結果を示す。
【図１６】共通ブロックの一例を示す。
【図１７】共通データグループを、幾つかの開いた共通ブロックのうちの１つにプログラムすることを示す。
【図１８】異なるファイルで不揮発性メモリにプログラムされたデータのメタページの幾つかの例を示す。
【図１９】図１４Ａ、図１４Ｃ、図１４Ｅおよび図１５の例からのファイル索引テーブル（ＦＩＴ）の構造および項目を示す。
【図２０】例示的なファイル索引付けデータ構造を概念的に示す。
【図２１】図２０のファイルディレクトリのページに対する構造を示す。
【図２２】図２０のファイル索引テーブルのページに対する構造を示す。
【図２３】図２１のファイルディレクトリの代わりとして図２０のファイルディレクトリのページに対する構造を示す。
【図２４】図２１および図２３のファイルディレクトリの動作を示す。
【図２５】図２２のファイル索引テーブルの動作を示す。
【図２６】本願明細書で説明されているメモリシステムの一連の動作全体を示すフローチャートである。
【図２７】図２６の「ファイルデータの読み出し」ブロックのフローチャートである。
【図２８】図２６の「ファイルデータのプログラム」ブロックのフローチャートである。
【図２９】図２８のフローチャートに含まれる２つの動作の相対的なタイミングを示す。
【図３０】図２６の「ファイルの削除」ブロックのフローチャートである。
【図３１】図２６の「ガーベッジコレクション」ブロックのフローチャートである。
【図３２】図３１の「共通ブロックガーベッジコレクション」ブロックのフローチャートである。
【図３３】本願明細書で説明された例示的なメモリシステムの動作中のメモリセルブロックの状態図である。
【図１】
2008530708.tif 000003
【図２】
2008530708.tif 000004
【図３】
2008530708.tif 000005
【図４】
2008530708.tif 000006
【図５】
2008530708.tif 000007
【図６】
2008530708.tif 000008
【図７】
2008530708.tif 000009
【図８】
2008530708.tif 000010
【図９】
2008530708.tif 000011
【図１０】
2008530708.tif 000012
【図１１】
2008530708.tif 000013
【図１２Ａ】
2008530708.tif 000014
【図１２Ｂ】
2008530708.tif 000015
【図１２Ｃ】
2008530708.tif 000016
【図１２Ｄ】
2008530708.tif 000017
【図１２Ｅ】
2008530708.tif 000018
【図１３Ａ】
2008530708.tif 000019
【図１３Ｂ】
2008530708.tif 000020
【図１３Ｃ】
2008530708.tif 000021
【図１３Ｄ】
2008530708.tif 000022
【図１４Ａ】
2008530708.tif 000023
【図１４Ｂ】
2008530708.tif 000024
【図１４Ｃ】
2008530708.tif 000025
【図１４Ｄ】
2008530708.tif 000026
【図１４Ｅ】
2008530708.tif 000027
【図１５】
2008530708.tif 000028
【図１６】
2008530708.tif 000029
【図１７】
2008530708.tif 000030
【図１８】
2008530708.tif 000031
【図１９】
2008530708.tif 000032
【図２０】
2008530708.tif 000033
【図２１】
2008530708.tif 000034
【図２２】
2008530708.tif 000035
【図２３】
2008530708.tif 000036
【図２４】
2008530708.tif 000037
【図２５】
2008530708.tif 000038
【図２６】
2008530708.tif 000039
【図２７】
2008530708.tif 000040
【図２８Ａ】
2008530708.tif 000041
【図２８Ｂ】
2008530708.tif 000042
【図２９】
2008530708.tif 000043
【図３０】
2008530708.tif 000044
【図３１Ａ】
2008530708.tif 000045
【図３１Ｂ】
2008530708.tif 000046
【図３１Ｃ】
2008530708.tif 000047
【図３１Ｄ】
2008530708.tif 000048
【図３２Ａ】
2008530708.tif 000049
【図３２Ｂ】
2008530708.tif 000050
【図３３Ａ】
2008530708.tif 000051
【図３３Ｂ】
2008530708.tif 000052
【国際調査報告】
2008530708.tif 000053
2008530708.tif 000054
2008530708.tif 000055