JP4533956B2 - フラッシュメモリシステムのデータ記憶容量の解放 - Google Patents

Description

本発明は、半導体フラッシュメモリなどの再プログラム可能な不揮発性メモリシステムの動作に関し、より具体的には、ホストデバイスとメモリとの間のインターフェイスを管理することに関する。

ホストシステム、メモリシステムおよび他の電子システムの外部インターフェイスを介して伝達したデータのアドレス指定を行う技術として、主に２つの技術がある。そのうちの１つは、システムが生成したり、または受信したりしたデータファイルのアドレスを、そのシステム用に設定した連続する論理アドレス空間の別個の範囲に対してマッピングを行うことである。通常、アドレス空間の広さは、システムが処理可能なアドレスの全域をカバーするのに十分な広さである。一例として、磁気ディスク記憶装置のドライブは、このような論理アドレス空間を介して、コンピュータまたは他のホストシステムと通信を行う。このアドレス空間の広さは、ディスクドライブの全データ記憶容量のアドレス指定を行うのに十分な広さである。２つの技術のうちの２つ目は、電子システムが生成したり、または受信したりしたデータファイルを一意に識別し、ファイル内で、オフセットにより理論的にそれらのデータのアドレス指定を行う。このアドレス指定方法の形式を、コンピュータまたは他のホストシステムと、“スマートカード”として周知の取り外し可能なメモリカードとの間で用いる。通常、顧客がスマートカードを利用して、顧客識別、バンキング、販売時点購入、ＡＴＭアクセス等を行う。

初期世代の市販のフラッシュメモリシステムでは、メモリセルの矩形アレイを、多数のグループのセルに分割していた。それぞれの記憶データ量は、標準ディスクドライブセクタ、すなわち、５１２バイトであった。通常、各グループは、１６バイトといった追加のデータ量をさらに含んで、誤り訂正符号（ＥＣＣ）と、ユーザデータおよび／または対応づけられたユーザデータを記憶するメモリセルグループに関する、考えられ得る他のオーバーヘッドデータとが記憶可能である。このようなグループそれぞれのメモリセルは、同時に消去可能な最小数のメモリセルである。すなわち、消去単位は、１つのデータセクタと、含まれる任意のオーバーヘッドデータとを記憶するのに効率的なメモリセルの数である。この種のメモリシステムの例が、米国特許第５，６０２，９８７号（特許文献１）および第６，４２６，８９３号（特許文献２）に記載されている。データで再プログラミングを行う前にメモリセルを消去することが、フラッシュメモリの特徴である。

フラッシュメモリシステムは、パーソナルコンピュータ、カメラ等の様々なホストに取り外し可能に接続する、メモリカードまたはフラッシュドライブの形で最も一般に提供されているものであるが、このようなホストシステムに埋め込まれている場合もある。データをメモリに書き込む際に、ホストは通常、一意の論理アドレスをメモリシステムの連続する仮想アドレス空間内のセクタ、クラスタまたは他のデータ単位に割り当てる。ディスクオペレーティングシステム（ＤＯＳ）のように、ホストは、メモリシステムの論理アドレス空間内のアドレスにデータを書き込んだり、またアドレスからデータを読み出したりする。メモリシステム内のコントローラは、ホストから受け取った論理アドレスを、メモリアレイ内の物理アドレスに変換する。実際に、データをここに記憶し、次に、これらのアドレス変換を常に把握しておく。メモリシステムのデータ記憶容量は少なくとも、メモリシステムに対し定義した全論理アドレス空間についてアドレス指定可能なデータ量と同じである。

次世代のフラッシュメモリシステムでは、消去単位の大きさは、多数のデータセクタを記憶するのに十分なメモリセルブロックに増加した。メモリシステムが接続しているホストシステムが、セクタなどの小さな最小単位でデータのプログラミングを行ったり、また読み出しを行ったとしても、フラッシュメモリの１つの消去単位に多数のセクタが記憶してある。ホストが論理データセクタを更新したり、または置換したりすると、普通は、ブロック内のいくつかのデータセクタは使われなくなることがある。ブロック内に記憶してある任意のデータを上書きする前に全ブロックを消去する必要があるので、通常、前に消去が行われたもののデータ記憶容量がまだ残っている別のブロックに、新しいデータまたは更新データを記憶する。この処理により、メモリ内部の貴重な空間を占有する使われなくなったデータのある、もともとのブロックを空けるようにする。しかし、内部に有効なデータが残っている場合、そのブロックを消去することはできない。

従って、メモリの記憶容量をよりよく利用するために、有効な断片的データのコピー元のブロックを消去して、それらの全記憶容量を再利用できるように、これらの断片的データを消去ブロックにコピーすることにより、有効な断片的データを統合したり、または集めたりすることが一般的に行われている。論理アドレス順にブロック内部のデータセクタをグループ化するためにデータのコピーを行うことも望ましいのは、これにより、データ読み出し速度と、読み出したデータをホストに送信する速度とが向上するからである。このようなデータコピーがかなり頻繁に行われると、メモリシステムの動作性能が低下してしまう。このことは特に、メモリの記憶容量が、システムの論理アドレス空間を介してホストがアドレス指定可能なデータ量を若干上回っている場合に、メモリシステムの動作に影響を与える典型的な場合である。この場合、ホストがプログラミングを行ったコマンドを実行する前に、データの統合や収集が必要になることもある。そして、結果としてプログラミングを行う時間が長くなる。

任意の半導体領域に記憶するデータのビット数を増やすために、メモリシステムの世代を経るにつれて、ブロックサイズは大きくなっていった。２５６データセクタ以上を記憶するブロックが一般的になっている。さらに、データのプログラミングと読み出しとを行う際の並列処理の程度を上げるために、２つ、４つ、あるいはそれ以上のブロック数の異なるアレイまたはサブアレイを理論的に接続して、メタブロックを構成するようにすることがしばしば行われている。このように容量が大きい動作単位をともに効率的に動作させることが、課題となっている。

このようなメモリシステムのための一般的なホストインターフェイスは、ディスクドライブとともに一般的に用いられるものと同様な論理アドレスインターフェイスである。メモリが接続しているホストが生成したファイルには、インターフェイスの論理アドレス空間内の一意のアドレスが割り当てられている。次に、メモリシステムは通常、論理アドレス空間と、メモリの物理ブロックまたはメタブロックとの間でデータのマッピングを行う。メモリシステムは、物理メモリに対してどのように論理アドレス空間のマッピングを行うかを常に把握しているが、ホストはこのことを知る必要はない。ホストは、論理アドレス空間内のそのデータファイルのアドレスを常に把握しているが、メモリシステムの動作には、このマッピングについてわかっている必要はない。
米国特許第５，６０２，９８７号 米国特許第６，４２６，８９３号 米国特許出願第１０／９１５，０３９号 米国特許第５，５７０，３１５号 米国特許第５，７７４，３９７号 米国特許第６，０４６，９３５号 米国特許第６，３７３，７４６号 米国特許第６，４５６，５２８号 米国特許第６，５２２，５８０号 米国特許第６，７７１，５３６号 米国特許第６，７８１，８７７号 米国公開特許出願第２００３／０１４７２７８号 米国公開特許出願第２００３／０１０９０９３号 米国特許第６，７６３，４２４号 米国特許出願第１０／７４９，８３１号 米国特許出願第１０／７５０，１５５号 米国特許出願第１０／９１７，８８８号 米国特許出願第１０／９１７，８６７号 米国特許出願第１０／９１７，８８９号 米国特許出願第１０／９１７，７２５号 米国特許出願第１１／１９２，２２０号 米国特許出願第１１／１９２，３８６号 米国特許出願第１１／１９１，６８６号 米国特許出願第１０／７４９，１８９号 米国特許出願第１０／８４１，１１８号 米国特許出願第１１／０１６，２７１号 米国特許出願第１０／８９７，０４９号 米国特許出願第１１／０２２，３６９号 米国特許出願第１１／１９６，８６９号 米国特許出願第１１／３１６，５７７号 米国特許出願第１１／２５９，４２３号 米国特許出願第１１／３１２，９８５号

フラッシュメモリシステムのこのように大きな規模の消去ブロックの動作を効率的に行う際に、様々な度合いで確実に生じる問題を克服する技術が、たくさん開発されている。これに対して、本発明は、根本的な変更、すなわち、メモリとホストシステムとの間でデータを転送するインターフェイスの変更に基づいている。仮想アドレス空間内の論理アドレスを用いることにより、メモリとホストシステムとの間でデータ通信を行うことではなく、ホストが割り当てたファイル名によりデータファイルの識別を行い、ファイル内のアドレスのオフセットを行ってそれにアクセスする。メモリシステムは次に、各セクタまたは他の単位のデータが属するホストファイルのことがわかるようになる。ここで説明するファイル単位とは、連続オフセットアドレスなどにより順序づけられたデータセットであって、ホスト演算システム内で動作するアプリケーションプログラムが生成し、かつ一意に識別したデータセットである。

このことが、現在市販のメモリシステムの多くで用いられていないのは、ホストが現在では、ファイルを識別することなく、共通セットの論理アドレスにより、全てのファイル内のメモリシステムに対しデータの識別を行っているからである。論理アドレスを用いる代わりに、ファイルオブジェクトによってホストデータの識別を行うことにより、データの統合やガーベッジコレクションを頻繁に行う必要性を低減するように、メモリシステムのコントローラはデータを記憶することができる。従って、データのコピー動作の頻度と、コピーデータ量とが大幅に低減するので、これによりメモリシステムのデータのプログラミングと読み出し性能が向上する。さらに、メモリシステムのコントローラは、ホストファイルを記憶するメモリブロックのディレクトリおよびインデックステーブル情報を保持する。このため、現在、論理アドレスインターフェイスの管理に必要なファイルアロケーションテーブル（ＦＡＴ）を、ホストが保持する必要がなくなる。

ブロック解放動作は、ガーベッジコレクションおよびデータ統合を含み、一般に、十分に活用されていないブロックの有効なデータを他のブロックにともに集め、次に、十分に活用されていないブロックを消去し、新しいデータの受け入れに利用できるようにする。本発明の一態様によれば、メモリセルブロックを選択して、ブロックの内容に基づいて解放する。論理アドレスインターフェイスを利用するメモリシステムにおいて、典型的には、物理ブロックの内容に基づくのではなく、ホストが物理ブロックにマッピングを行う論理データブロックを閉じることに応答して、メモリセルブロックを解放する。ブロックの内容を選択基準に含めることにより、より効率的なメモリシステムの動作が可能になる。

特定の実施の形態において、含まれている有効なデータ量に基づいて、有効なデータで部分的に埋められているブロックを、解放動作のために選択する。別のブロックにコピーすべきデータが少ないので、有効なデータ量が最も少ないブロックを最も効率的に解放することができる。データのコピーを行うには、データのプログラミングまたは読み出しなどにより、他のメモリ動作よりも相当時間がかかるので、有効なデータ量が最も少ないブロックを選択して解放することは、例えば、システムの性能に最も悪影響を与えずに、このブロックを新しいデータを記憶するのに利用できるようにすることを意味している。小さい有効なデータ量を含んでいるブロックは、ブロックを解放する必要のない、データが書き込まれた消去した容量を含んでいるものもあるので、いくつかの実施形態では、解放すべきブロックを選択する際に、ブロック内の消去した容量の量を考慮に入れている。２つのブロックに記憶してある有効なデータ量は同じであるが、一方には消去した容量があり、もう一方にはない場合、例えば、利用できる容量が増えるので、消去した容量がないブロックをはじめに解放する。消去した容量のあるブロックには、書き込みが行われるデータ量に基づいて、新しいデータを記憶するための現在の値があるが、消去した容量のないブロックには値がない。

本発明の他の態様、利点、特徴および詳細については、添付の図面を参照して説明する、以下の例示の説明に含まれている。

ここで参照する特許、特許出願、論文、他の公報、文献および事柄は全て、事実上、その全体が本願明細書において参照により援用されている。定義上、または援用されている公報、文献または事柄と本願との間の用語のある程度の不一致または矛盾については、本願で用いる用語により明らかになるであろう。

フラッシュメモリシステムの概要
図１〜図８を参照して、一般的なフラッシュメモリシステムと、ホストデバイスとの典型的な動作とについて説明する。これは、本発明の様々な態様を実施するシステムである。図１のホストシステム１は、フラッシュメモリ２にデータを記憶し、フラッシュメモリ２からデータを検索する。フラッシュメモリをホストに埋め込むことが可能であるが、メモリ２については、より広く普及している形態のカードとし、機械的および電気的なコネクタである接続部分３および４を介してホストに取り外し可能に接続しているものとして例示する。現在、多くの異なるフラッシュメモリカードが市販されているが、一例として、コンパクトフラッシュ（ＣＦ）、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）、ミニＳＤ、マイクロＳＤ、メモリスティック、スマートメディアおよびトランスフラッシュという商標のもとで販売されている。これらのカードは、それらの標準化仕様により一意の機械的および／または電気的インターフェイスを有しているが、各カードに含まれるフラッシュメモリは非常に似通っている。これらのカードはすべて、本願の譲受人であるサンディスク コーポレイション(SanDisk Corporation) から入手できる。サンディスク コーポレイションは、クルーザー（Ｃｒｕｚｅｒ）という商標のもとで一連のフラッシュドライブも販売している。これは、ホストのＵＳＢコンセントに接続することによりホストに接続するユニバーサル・シリアル・バス（ＵＳＢ）プラグを有する、小形パッケージのハンドヘルド形メモリシステムである。これらのメモリカードおよびフラッシュドライブはそれぞれ、ホストとインターフェイスをとり、内部のフラッシュメモリの動作を制御するコントローラを含んでいる。

このようなメモリカードおよびフラッシュドライブを用いるホストシステムの数は多く、様々である。これらは、パーソナルコンピュータ（ＰＣ）、ラップトップや他の携帯用コンピュータ、携帯電話、個人用携帯情報端末（ＰＤＡ）、デジタル静止画カメラ、デジタル動画カメラや携帯用オーディオプレーヤを含む。ホストは典型的には、１つ以上の種類のメモリカードまたはフラッシュドライブ用の組み込みコンセントを含んでいるが、メモリカードを接続するアダプタを必要とするものもある。メモリシステムは通常、それ自体のメモリコントローラおよびドライバを備えているが、メモリシステムの中には、メモリが接続しているホストが実行するソフトウェアの制御しか受け付けないものもある。コントローラを備えるメモリシステムのうち、特にホストに埋め込まれているものは、メモリ、コントローラおよびドライバが１つの集積回路チップ上に構成されているものがよくある。

図１のホストシステム１は、メモリ２が接続する限り、２つの主な部分である、回路およびソフトウェアの組み合わせから構成されていると見なすこともできる。これらは、アプリケーション５と、メモリ２とインターフェイスをとるドライバ部分６とである。パーソナルコンピュータでは、例えば、アプリケーション５は、文書作成、グラフィック、制御または他の広く普及しているアプリケーションソフトウェアを実行するプロセッサを含むことができる。主に１つのセットの機能を専用に実行するカメラ、携帯電話または他のホストシステムでは、アプリケーション５は、カメラが画像の撮影および保存を行うように動作させたり、携帯電話が電話をかけたり、また受けたりするように動作させたりする等のソフトウェアを含んでいる。

図１のメモリシステム２は、フラッシュメモリ７と、カードと接続したホストとフラッシュメモリとのインターフェイスをとってデータのやりとりを行いメモリ７を制御する回路８とを含んでいる。コントローラ８は典型的には、データプログラミングや読み出しを行う間に、ホスト１が用いるデータの論理アドレスと、メモリ７の物理アドレスとの間で変換を行う。

図２を参照して、図１の不揮発性メモリ２として用いられる典型的なフラッシュメモリシステムの回路について説明する。通常、システムコントローラは、システムバス１３を介して、１つ以上の集積回路メモリチップと並列に接続している１つの集積回路チップ１１上で実現される。このような１つのメモリチップ１５を図２に示す。図に示されている特定のバス１３は、データを送る個別のセットの導体１７と、メモリアドレス用のセット１９と、制御信号、状態信号用のセット２１を含んでいる。あるいは、１つのセットの導体は、これらの３つの機能を時分割で実行するものであってもよい。さらに、２００４年８月９日出願の米国特許出願第１０／９１５，０３９号、現在公開されている公開特許出願第２００６／００３１５９３号である“リングバス構造およびフラッシュメモリシステムでのその用法(Ring Bus Structure and It's Use in Flash Memory Systems) ”（特許文献３）に記載のリングバスなどの、他の構成のシステムバスを用いることもできる。

典型的なコントローラチップ１１は、インターフェイス回路２５を介してシステムバス１３とインターフェイスをとるそれ自体の内部バス２３を有している。通常、バスに接続している主な機能は、（マイクロプロセッサまたはマイクロコントローラなどの）プロセッサ２７と、システムを初期化する（“立ち上げる”）コードを含む読み出し専用メモリ（ＲＯＭ）２９と、メモリとホストとの間での送信データのバッファを主に行うのに用いられるランダムアクセスメモリ（ＲＡＭ）３１と、メモリとホストとの間でコントローラを介してやりとりするデータ用の誤り訂正符号（ＥＣＣ）を計算し検証する回路３３とである。コントローラバス２３は、回路３５を介してホストシステムとインターフェイスをとる。これは、メモリカード内にある図２のシステムの場合、コネクタ４の一部であるカードの外部接点３７を介して行われる。コントローラ１１の他の構成部品それぞれが、クロック３９に接続し、これを用いる。

システムバス１３と接続している他の構成部品とともに、メモリチップ１５は典型的には、多数のサブアレイまたはプレーンとして構成されるメモリセルアレイを含んでいる。図を簡略化するために、このような２つのプレーン４１および４３を示しているが、このようなプレーンは４つまたは８つ用いられることもある。あるいは、チップ１５のメモリセルアレイを、プレーンに分割しなくてもよい。しかし、分割した場合、各プレーンは、たいてい互いに独立して動作可能な列制御回路４５および４７を有している。回路４５および４７は、システムバス１３のアドレス部１９からそれらのそれぞれのメモリセルアレイのアドレスを受け取り、これらのアドレスを復号して、特定の１つ以上の個別のビット線４９および５１に対しアドレス指定を行う。アドレスバス１９上で受け取ったアドレスに応じて、行制御回路５５を介してワード線５３のアドレス指定を行う。ソース電圧制御回路５７および５９は、Ｐウェル電圧制御回路６１および６３のように、それぞれのプレーンにも接続している。メモリチップ１５がメモリセルアレイを１つ有し、かつシステムにこのようなチップが２つ以上ある場合には、それぞれのチップのアレイは、前述したマルチプレーンチップ内のプレーンすなわちサブアレイと同じように動作することになる。

システムバス１３のデータ部分１７に接続しているデータ入出力回路６５および６７それぞれを介して、データをプレーン４１および４３とやりとりする。回路６５および６７は、列制御回路４５および４７それぞれを介して、プレーンに接続した線６９および７１を通じて、メモリセルにプログラミングを行うデータと、各々のプレーンのメモリセルから読み出すデータとを供給する。

コントローラ１１は、メモリチップ１５の動作を制御し、データのプログラミング、データの読み出し、消去および各種の段取りを行うが、各メモリチップはまた、コントローラ１１からのコマンドを実行し、このような機能を行う制御回路をいくつか含んでいる。インターフェイス回路７３は、システムバス１３の制御・状態部分２１に接続している。コントローラからのコマンドを状態マシーン７５に供給し、次にこれらのコマンドを実行するために、他の回路の特定の制御を行うようにする。図２に示すように、制御線７７〜８１は、状態マシーン７５をこれらの他の回路に接続している。状態マシーン７５からの状態情報を、線８３を介してインターフェイス７３に通信し、バス部２１を介してコントローラ１１に送信する。

ＮＯＲなどの他のアーキテクチャをかわりに用いることもできるが、メモリセルアレイ４１および４３のＮＡＮＤアーキテクチャが現在好適なものである。一例のＮＡＮＤフラッシュメモリおよびメモリシステムの一部としてのそれらの動作については、米国特許第５，５７０，３１５号（特許文献４）、第５，７７４，３９７号（特許文献５）、第６，０４６，９３５号（特許文献６）、第６，３７３，７４６号（特許文献７）、第６，４５６，５２８号（特許文献８）、第６，５２２，５８０号（特許文献９）、第６，７７１，５３６号（特許文献１０）および第６，７８１，８７７号（特許文献１１）ならびに米国公開特許出願第２００３／０１４７２７８号（特許文献１２）を参照することができる。

図３は、一例のＮＡＮＤアレイを示す回路図である。これは、図２のメモリシステムのメモリセルアレイ４１の一部分である。多数のグローバルビット線が形成されているが、説明を簡略化するために、図３にはこのような線９１〜９４を４本だけ示す。これらのビット線のうちの１本と基準電位との間には、多数の直列接続メモリセルストリング９７〜１０４が接続している。メモリセルストリング９９を代表例として用いると、複数の電荷蓄積メモリセル１０７〜１１０が、ストリングのいずれかの端部に、選択トランジスタ１１１および１１２と直列で接続している。１本のストリングの選択トランジスタが導電性である場合、そのビット線と基準電位との間にストリングが接続している。次に、そのストリング内のメモリセルに対し１つずつ、プログラミングを行ったり、または読み出しを行ったりする。

メモリセルの多数のストリングそれぞれのメモリセル１つの電荷蓄積素子に対して、図３のワード線１１５〜１１８が個別に延在し、ゲート１１９および１２０が、ストリングの各端部で、選択トランジスタの状態を制御する。共通ワード線とコントロールゲート線１１５〜１２０とを共有するメモリセルストリングにより、１度に消去するメモリセルのブロック１２３を構成するようにする。このセルブロックは、物理的に１度に消去可能な最小数のセルを含んでいる。ワード線１１５〜１１８のうちの１本に沿った１行のメモリセルに対し、１度にプログラミングを行う。典型的には、ＮＡＮＤアレイの行に対し、所定の順序でプログラミングを行う。この場合、接地電位または別の共通電位に接続したストリングの端部に最も近いワード線１１８に沿った行から開始している。ワード線１１７に沿ったメモリセルの行に対しプログラミングを行い、これを次々に繰り返して、ブロック１２３全体に行う。最後に、ワード線１１５に沿った行に対しプログラミングを行う。

第２のブロック１２５も同様である。そのメモリセルストリングは第１のブロック１２３のストリングと同じグローバルビット線に接続しているが、ワード線およびコントロールゲート線のセットが異なっている。行制御回路５５により、それらの適切な動作電圧でワード線およびコントロールゲートゲート線を駆動している。図２のプレーン１および２のようにシステムに２つ以上のプレーンすなわちサブアレイがある場合、一方のメモリアーキテクチャが、間に延在している共通ワード線を用いる。あるいは、共通ワード線を共有するプレーンすなわちサブアレイが３つ以上ある場合もある。他のメモリアーキテクチャでは、個別のプレーンすなわちサブアレイのワード線を別々に駆動する。

前に援用されているＮＡＮＤ特許および公開特許出願のいくつかに記載されているように、メモリシステムは、電荷蓄積素子または領域それぞれに３つ以上の検出可能なレベルの電荷を記憶するように動作し、これにより、それぞれ２つ以上のビットのデータを記憶する。メモリセルの電荷蓄積素子は大抵、一般的に導電性フローティングゲートであるが、あるいは、米国公開特許出願第２００３／０１０９０９３号（特許文献１３）に記載されているような非導電性誘電電荷補足材料とすることもできる。

図４は、一例として用いられるフラッシュメモリセルアレイ７（図１）の構成を示す概念図である。以下にさらに説明する。１つの集積メモリセルチップの上、２つのチップ（各チップに２つのプレーン）の上、または４つの別々のチップの上に、メモリセルの４つのプレーンすなわちサブアレイ１３１〜１３４を載置してもよい。以下の説明では、特定の配置は重要ではない。もちろん、１、２、８、１６またはそれ以上などの他の数のプレーンが、システムにあってもよい。それぞれのプレーン１３１〜１３４上にあるブロック１３７、１３８、１３９および１４０のように、プレーンを、図４に示す矩形のメモリセルブロックに個別に分割する。各プレーンを、数十または数百のブロックに分割可能である。前述したように、メモリセルブロックは、物理的に１度に消去可能な最小数のメモリセルの消去単位である。しかし、並列処理が増えているので、ブロックの動作は大きいメタブロック単位で行われている。各プレーンから１つのブロックが、論理的にともにリンクしてメタブロックを形成している。図に示されている４つのブロック１３７〜１４０が、１つのメタブロック１４１を形成している。典型的には、メタブロック内のセルをすべて、ともに消去する。ブロック１４５〜１４８から形成されている第２のメタブロック１４３からわかるように、メタブロックの形成に用いられるブロックは、それぞれのプレーン内で同じ相対位置である必要はない。通常、プレーンすべてにメタブロックを延在することは好ましいが、システム性能を高くするには、異なるプレーンの１つ、２つまたは３つのブロックのいずれか、またはすべてから動的にメタブロックを形成する機能により、メモリシステムの動作を行うことができる。これにより、メタブロックの大きさを、１回のプログラミング動作で記憶できるデータ量と、密接に一致させることが可能になる。

図５に示すように、個別のブロックを順に、動作を行うためにメモリセルのページに分割する。ブロック１３１〜１３４それぞれのメモリセルを例えば、８つのページＰ０〜Ｐ７に分割する。あるいは、ブロック内でそれぞれ１６、３２またはそれ以上のメモリセルのページに分割してもよい。ページは、ブロック内でデータのプログラミングと読み出しを行う単位であり、１度にプログラミングを行う最小のデータ量を含むものである。図３のＮＡＮＤアーキテクチャでは、ページは、ブロック内のワード線に沿ったメモリセルから形成されている。しかし、メモリシステム動作の並列処理を向上させるために、２つ以上のブロック内のこのようなページを、論理的にメタページにリンクしてもよい。図５にメタページ１５１を示す。これは、４つのブロック１３１〜１３４それぞれのうちの１つの物理ページから構成されている。メタページ１５１は例えば、４つのブロックそれぞれでページＰ２を含んでいるが、メタページのページは、それぞれのブロック内で必ずしも同じ相対位置にある必要はない。

４つのプレーンすべてで、並列に最大データ量のプログラミングと読み出しを行うことは好ましいが、システム性能を高くするには、異なるプレーンの別々のブロックにおける１つ、２つまたは３つのページのいずれかまたはすべてのメタページを形成するように、メモリシステムを動作させることもできる。これにより、プログラミングと読み出し動作を、並列に都合よく処理できるデータ量と適応可能なように一致させることができ、データのプログラミングを行わないメタページの一部が残ってしまうようなことを低減する。

図５に示すように、複数のプレーンの物理ページを構成するメタページは、それらの複数のプレーンのワード線の行に沿ってメモリセルを含んでいる。１本のワード線の行のセルすべてに対して同時にプログラミングを行うよりも、より一般には、２つ以上の交互に配置したグループで交互にプログラミングを行う。各グループは、（１つのブロック内の）１ページのデータ、または（複数のブロックにわたる）１つのメタページのデータを記憶してある。メモリセルに対し交互に１度にプログラミングを行うことにより、データレジスタおよびセンス増幅器を含む１単位の周辺回路を、ビット線ごとに配置する必要はなく、むしろ隣接するビット線の間で時分割で処理を行う。これにより、周辺回路に必要な基板空間の量を節約し、行に沿って高い密度でメモリセルを集積することが可能になる。あるいは、任意のメモリシステムで可能な並列処理を最大にするために、行に沿ったセル毎に同時にプログラミングを行うことが好ましい。

図３を参照すると、図に示されているように１つの行を配置するよりも、ＮＡＮＤストリングの少なくとも一方の端部に沿って２つの行の選択トランジスタ（図示せず）を配置することにより、行に沿ったメモリセルを１つおきにデータプログラミングが同時に行われることを、最も都合良く達成する。次に、１つの制御信号に応答して、一方の行の選択トランジスタを、ブロック内の他のストリングを１つおきにそれぞれのビット線に接続し、もう１つの制御信号に応答して、もう一方の行の選択トランジスタを、他のストリングを１つおきにはさまれるようにそれぞれのビット線に接続する。従って、２つのページのデータが、メモリセルの各行に書き込まれる。

典型的には、各論理ページのデータ量は、整数である１つ以上のデータセクタであり、従来では、各セクタは５１２バイトのデータを含んでいる。図６は、１ページまたは１メタページのデータの論理データページの２つのセクタ１５３および１５５を示す。各セクタには通常、記憶してある５１２バイトのユーザまたはシステムデータの部分１５７が含まれ、部分１５７のデータ、または物理ページ、またはこれを記憶しているブロックのいずれかに関するオーバーヘッドデータを別の数のバイト１５９として含んでいる。典型的には、オーバーヘッドデータのバイト数は１６バイトであり、それぞれのセクタ１５３および１５５に対し全部で５２８バイトである。オーバーヘッド部分１５９は、プログラミングを行う間にデータ部分１５７から算出したＥＣＣと、その論理アドレスと、ブロックの消去と再プログラミングを行った実際の回数と、１つ以上の制御フラグと、動作電圧レベルなどとともに、このようなオーバーヘッドデータ１５９から算出したＥＣＣとを含んでもよい。あるいは、オーバーヘッドデータ１５９またはその一部を、他のブロックの異なるページに記憶してもよい。

メモリの並列処理が増えるに従って、メタブロックのデータ記憶容量が増え、データページおよびメタページの大きさも結果として増えることになる。そして、データページは、３つ以上のデータセクタを含むことになる。データページの２つのセクタと、メタページ毎に２つのデータページとで、１メタページには４つのセクタが存在する。従って、各メタページは２，０４８バイトのデータを記憶する。これは高い度合いの並列処理であり、行のメモリセルの数が増えるに従って、さらに度合いが高くなる。この理由により、１ページおよび１メタページのデータ量を増やすために、フラッシュメモリの幅が広がっていくことになる。

前に識別した、物理的に小さい再プログラム可能な不揮発性メモリカードおよびフラッシュドライブは、５１２メガバイト（ＭＢ）、１ギガバイト（ＧＢ）、２ＧＢおよび４ＧＢのデータ記憶容量で市販され、容量はさらに大きくなっている。図７は、ホストとこのような大容量メモリシステムとの間の最も一般的なインターフェイスを示す。ホストは、アプリケーションソフトウェア、またはホストが実行するファームウェアプログラムが生成したりまたは用いたりするデータファイルを処理する。一例として、文書処理のデータファイルであり、別の例として、コンピュータ援用設計（ＣＡＤ）ソフトウェアの図面ファイルがあり、ＰＣ、ラップトップコンピュータ等の一般的なコンピュータホストに多く見受けられるものである。ｐｄｆフォーマットの文書もこのようなファイルである。スチルデジタルビデオカメラは、メモリカードに記憶する画像それぞれのデータファイルを生成する。携帯電話は、電話ディレクトリなどの内部メモリカード上のファイルからデータを利用する。ＰＤＡは、アドレスファイル、カレンダファイル等のいくつかの異なるファイルを記憶し、利用する。このようなアプリケーションのいずれにおいても、メモリカードは、ホストを動かすソフトウェアを含んでいる。

ホストシステムとメモリシステムとの間の、一般的な論理インターフェイスを図７に示す。連続する論理アドレス空間１６１は、メモリシステムに記憶する全データのアドレスを構成するのに十分な広さである。典型的には、ホストアドレス空間を、データクラスタの単位で分割する。任意のホストシステムが多数のデータセクタを含むように、各クラスタを設計してもよく、典型的には、４セクタから６４セクタの間である。標準的なセクタは５１２バイトのデータを含んでいる。

図７の例には、３つのファイル１、２、３が生成されている。ホストシステム上で実行するアプリケーションプログラムにより、順序づけられたデータセットとして各ファイルを生成し、一意の名称または他の基準により識別する。ホストにより、ファイル１に対して、他のファイルにまだ割り当てられていない十分に利用可能な論理アドレス空間が割り当てられている。図に示されているファイル１は、利用可能な論理アドレスの連続する範囲に割り当てられている。アドレス範囲は一般に、ホストの動作を行うソフトウェアの特定の範囲などの、特定の目的のために割り当てられているので、ホストが論理アドレスをデータに割り当てているときにこれらのアドレスが利用されていないとしても、データの記憶が行えないようになっている。

ホストがファイル２を後で生成する場合、図７に示すように、ホストは同様に、論理アドレス空間１６１内の連続するアドレスの２つの異なる範囲を割り当てる。ファイルを連続する論理アドレスに割り当てる必要はないが、他のファイルにすでに割り当てられたアドレス範囲の間でアドレスが断片化することがある。次に、この例について、ホストがさらに生成した別のファイル３を、ファイル１、２および他のデータに前に割り当てられていないホストアドレス空間の他の部分に割り当てていることからわかる。

ファイルアロケーションテーブル（ＦＡＴ）を保持することにより、ホストは、メモリ論理アドレス空間を常に把握している。これは、変換１６０を行って各種のホストファイルに対しホストが割り当てた論理アドレスを保持している。新しいファイルを記憶したり、他のファイルを削除したり、ファイルを変更したりする際等に、ホストは頻繁にＦＡＴ表の更新を行う。ＦＡＴ表は典型的には、時折更新が行われる不揮発性メモリに保存したコピーとともに、ホストメモリに記憶する。コピーに対しては典型的には、他のデータファイルのように、論理アドレス空間を介して不揮発性メモリにアクセスする。ホストファイルを削除する場合、ホストは次に、削除ファイルに前に割り当てられた論理アドレスの割り当てを解除して、ＦＡＴ表を更新することにより、他のデータファイルとともに利用可能であることを示す。

メモリシステムのコントローラが選択してファイルを記憶する物理位置について、ホストは無関係である。典型的なホストは、その各種のファイルに割り当てたその論理アドレス空間および論理アドレスについてのみわかっている。これに反して、メモリシステムは、典型的なホスト／カードインターフェイスを介して、データを書き込んだ論理アドレス空間の一部分についてだけわかっているが、特定のホストファイルに割り当てられた論理アドレス、またはホストファイルの数についてはわかっていない。メモリシステムのコントローラは、データの記憶または検索用にホストが提供した論理アドレスを、ホストデータを記憶してあるフラッシュメモリセルアレイ内の一意の物理アドレスに変換する。ブロック１６３は、これらの論理対物理アドレス変換の作業表を表し、これは、メモリシステムのコントローラが保持している。

メモリシステムのコントローラは、システム性能を高いレベルで維持するやり方で、メモリアレイ１６５のブロックおよびメタブロック内にデータファイルを記憶できるようにプログラミングが行われている。この図では、４つのプレーンすなわちサブアレイが用いられている。好ましくは、それぞれのプレーンのブロックから構成される全メタブロックにわたって、システムが実行可能な最大の度合いの並列処理で、データのプログラミングと読み出しが行われる。通常、メモリコントローラが用いる動作ファームウェアおよびデータを記憶するための保留ブロックとして、少なくとも１つのメタブロック１６７が割り当てられている。別のメタブロック１６９、または複数のメタブロックが、ホストを動かすソフトウェア、ホストＦＡＴ表等を記憶するために、割り当てられていることもある。大抵の物理記憶空間は、データファイルを記憶するために残されている。しかし、メモリコントローラは、その各種のファイルオブジェクト間でホストがどのように受信したデータを割り当てているかをわかっていない。典型的には、ホストと対話することによりメモリコントローラがわかっていることのすべては、ホストが特定の論理アドレスに書き込んだデータを、コントローラの論理対物理アドレス表１６３が保持する、対応する物理アドレスに記憶していることである。

典型的なメモリシステムでは、アドレス空間１６１に記憶するのに必要なデータ量以上に、余分なブロックの記憶容量が備えられている。１つ以上のこれらの余分なブロックを、メモリ寿命が経過する間に不良となる他のブロックと置換するための、冗長ブロックとして備えてもよい。個別のメタブロックに含まれるブロックの論理グループ化は、メタブロックにもともと割り当てられている不良ブロックと冗長ブロックを置換するというように、様々な理由で大抵行われる。典型的には、メタブロック１７１などの１つ以上の追加ブロックを、消去ブロックプールに保持する。ホストがデータをメモリシステムに書き込む場合、コントローラは、消去ブロックプールのメタブロック内の物理アドレスにホストが割り当てた論理アドレスを変換する。次に、論理アドレス空間１６１内のデータの記憶に用いられない他のメタブロックを消去し、次のデータ書き込み動作を行う間に用いる消去プールブロックとして指定する。好適な形態では、論理アドレス空間を、それぞれ物理メモリメタブロックの記憶容量と同じデータ量を含む論理グループに分割するので、メタブロックに対し論理グループの１対１マッピングが可能になる。

もともと記憶してあるデータが使われなくなったときは、特定のホスト論理アドレスに記憶してあるデータを新しいデータで頻繁に上書きする。これに対応して、メモリシステムのコントローラは、新しいデータを消去ブロックに書き込んで、次に、それらの論理アドレスの論理対物理アドレス表を変更して、それらの論理アドレスのデータを記憶してある新しい物理ブロックの識別を行う。次に、それらの論理アドレスのもともとのデータを含むブロックを消去し、新しいデータを記憶するのに利用できるようにする。書き込み開始時に消去ブロックプールからの前に消去したブロックの記憶容量が十分でない場合、現在のデータ書き込み動作が完了する前に、このような消去を頻繁に行う必要がある。これは、システムデータのプログラミング速度に悪影響を与えることになる。典型的には、メモリコントローラは、ホストが新しいデータをそれらの同じ論理アドレスに書き込むときに限って、ホストが任意の論理アドレスのデータを使わなくなったことを学習する。従って、メモリの多くのブロックが、このような無効なデータをある期間記憶していることになる。

集積回路メモリチップの領域を効率的に利用するために、ブロックおよびメタブロックの大きさが大きくなっている。このため、個別のデータ書き込みのかなりの部分が、メタブロックの記憶容量より小さい、多くの場合、ブロックの記憶容量よりも小さいデータ量を記憶することになる。通常、メモリシステムのコントローラは、新しいデータを消去プールメタブロックに向けるので、メタブロックの一部分に書き込みが行われなくなることになる。新しいデータが別のメタブロックに記憶してあるデータの更新である場合、望ましくは、それらの新しいデータメタページと隣接する論理アドレスを有する他のメタブロックからの残っている有効なメタページのデータについても、論理アドレス順で新しいメタブロックにコピーする。古いメタブロックを他の有効なデータメタページに保持してもよい。これは、時間の経過とともに個別のメタブロックの特定のメタページのデータが使われなくなって無効になり、このデータを、異なるメタブロックに書き込まれた同じ論理アドレスの新しいデータと置換することになる。

全論理アドレス空間１６１にわたってデータの記憶に十分な物理的メモリ空間を保持するために、このようなデータを定期的に圧縮したり、統合したりする（ガーベッジコレクションを行う）。できる限り実際に実行可能なように、メタブロック内のデータセクタをそれらの論理アドレスと同じ順序で保持することも望ましい。というのは、これにより、連続する論理アドレスデータの読み出しがより効率的になるからである。従って、典型的には、データ圧縮およびガーベジコレクションが、この追加の目的で行われる。部分ブロックデータの更新を受け取った際のメモリの管理およびメタブロックの利用の態様については、米国特許第６，７６３，４２４号（特許文献１４）にいくつか記載されている。

典型的には、データ圧縮は、処理において無効なデータのあるメタページを無視して、メタブロックからのすべての有効なデータメタページの読み出しと、新しいメタブロックへのそれらの書き込みを行う。有効なデータのあるメタページを、記憶してあるデータの論理アドレス順と一致する物理アドレス順で配列することも好ましい。新しいメタブロックを占有するメタページの数が、古いメタブロックを占有していた数よりも少なくなっている。というのは、無効なデータを含むメタページを新しいメタブロックにコピーしていないからである。次に、古いブロックを消去し、新しいデータの記憶に利用できるようにする。次に、統合で得た追加したメタページの容量を、他のデータの記憶に用いることができる。

ガーベッジコレクションを行う間、連続する論理アドレスまたはほぼ連続する論理アドレスのある有効なデータのメタページを、２つ以上のメタブロックから集め、別のメタブロックに書き換える。通常、消去ブロックプールに１つである。有効なデータメタページすべてをもともとの２つ以上のメタブロックからコピーする場合、これらを消去して後で用いる。

特に、ホストからのコマンドが実行可能になる前に、データ統合またはガーベッジコレクションを行う必要がある場合、データ統合およびガーベッジコレクションには時間がかかり、メモリシステムの性能に影響を与えることがある。通常、メモリシステムのコントローラによりこのような動作のスケジュールをたてて、できる限りバックグラウンドで実行するが、これらの動作を行わなければならないので、コントローラは、このような動作が完了するまで、ホストにビジー状態信号を送信しなければならなくなる。ホストコマンドの実行が遅延可能な一例として、ホストがメモリに書き込みを行いたいデータをすべて記憶するのに、消去ブロックプール内の前に消去したメタブロックが十分なく、データ統合またはガーベッジコレクションが必要なので、１つ以上のメタブロックの有効なデータをはじめにクリアし、次に、消去する例が挙げられる。従って、このような混乱を最小にするために、メモリ制御を管理することが注目される。多くのこのような技術について、２００３年１２月３０日出願の米国特許出願第１０／７４９，８３１号、現在公開されている公開特許出願第２００５／０１４４３５８号である“大容量消去ブロックを有する不揮発性メモリシステムの管理(Management of Non-Volatile Memory Systems Having Large Erase Blocks) ”（特許文献１５）、２００３年１２月３０日出願の米国特許出願第１０／７５０，１５５号“ブロック管理システムを用いた不揮発性メモリおよび方法(Non-Volatile Memory and Method with Block Management System) ”（特許文献１６）、２００４年８月１３日出願の米国特許出願第１０／９１７，８８８号、現在公開されている公開特許出願第２００５／０１４１３１３号である“メモリプレーン配列を用いた不揮発性メモリおよび方法（Non-Volatile Memory and Method with Memory Planes Alignment)”（特許文献１７）、現在公開されている公開特許出願第２００５／０１４１３１２号の２００４年８月１３日出願の米国特許出願第１０／９１７，８６７号（特許文献１８）、２００４年８月１３日出願の米国特許出願第１０／９１７，８８９号、現在公開されている公開特許出願第２００５／０１６６０８７号である“位相プログラム障害処理を用いた不揮発性メモリおよび方法(Non-Volatile Memory and Method with Phased Program Failure Handling) ”（特許文献１９）、２００４年８月１３日出願の米国特許出願第１０／９１７，７２５号、現在公開されている公開特許出願第２００５／０１４４３６５号である“制御データ管理を用いた不揮発性メモリおよび方法(Non-Volatile Memory and Method with Control Data Management) ”（特許文献２０）、２００５年７月２７日出願の米国特許出願第１１／１９２，２２０号“マルチストリーム更新トラックを用いた不揮発性メモリおよび方法(Non-Volatile Memory and Method with Multi-Stream Update Tracking)”（特許文献２１）、２００５年７月２７日出願の米国特許出願第１１／１９２，３８６号“スクラッチパッドおよび更新ブロックのための向上した索引付けを用いた不揮発性メモリおよび方法(Non-Volatile Memory and Method with Improved Indexing for Scratch Pad and Update Blocks) ”（特許文献２２）、２００５年７月２７日出願の米国特許出願第１１／１９１，６８６号“マルチストリーム更新を用いた不揮発性メモリおよび方法（Non-Volatile Memory and Method with Multi-Stream Updating)”（特許文献２３）に記載されている。

大容量消去ブロックを有するメモリアレイの動作を効率的に制御する課題の１つは、任意の書き込み動作の間に記憶が行われているデータセクタの数を、メモリのブロックの容量および境界と一致させ、調整することである。アプローチの１つは、全メタブロックを満杯にする量よりも少ないデータ量を記憶する必要がある場合、ホストからの新しいデータの記憶に用いられるメタブロックを、最大数のブロックよりも少ない数で構成することである。適応メタブロックの利用については、２００３年１２月３０日出願の米国特許出願第１０／７４９，１８９号、現在公開されている公開特許出願第２００５／０１４４３５７号である“適応メタブロック(Adaptive Metablocks) ”（特許文献２４）に記載されている。データブロック間の境界およびメタブロック間の物理境界のフィッティングについては、現在公開されている公開特許出願第２００５／０１４４３６３号の２００４年５月７日出願の米国特許出願第１０／８４１，１１８号（特許文献２５）、２００４年１２月１６日出願の米国特許出願第１１／０１６，２７１号、現在公開されている公開特許出願第２００５／０１４４３６７号である“データランプログラミング(Data Run Programming)”（特許文献２６）に記載されている。

メモリコントローラは、ＦＡＴ表からのデータも用いる。これは、ホストが不揮発性メモリに記憶したもので、メモリシステムの動作をより効率的に行う。このような利用の１つは、ホストが識別したデータが使われなくなって、それらの論理アドレスの割り当てを解除する際に、学習することである。これを知ることにより、通常、ホストが書き込みを行う新しいデータをそれらの論理アドレスに書き込むことにより学習する前に、メモリコントローラが、このような無効なデータを含むブロックを消去するスケジュールをたてることが可能になる。このことは、２００４年７月２１日出願の米国特許出願第１０／８９７，０４９号、現在公開されている公開特許出願第２００６／００２０７４４号である“不揮発性メモリシステム上のデータを保持する方法および装置(Method and Apparatus for Maintaining Data on Non-Volatile Memory Systems)”（特許文献２７）に記載されている。他の技術は、任意の書き込み動作を１つのファイルに行うのかどうかを推理するために、すなわち、複数のファイルの間に境界があるかどうかを推理するために、新しいデータをメモリに書き込むホストのパターンの監視を行うことを含んでいる。２００４年１２月２３日出願の米国特許出願第１１／０２２，３６９号、現在公開されている公開特許出願第２００６／００２０７４５号である“最適化順次クラスタ管理のためのＦＡＴ分析(FAT Analysis for Optimized Sequential Cluster Management)”（特許文献２８）に、このタイプの技術の利用について記載されている。

メモリシステムの動作を効率的に行うために、個別のファイルのデータにホストが割り当てた論理アドレスについて、できるだけ多くをコントローラがわかっていることが望ましい。次に、ファイル境界がわからない場合、多数のメタブロック間で分散するよりも、コントローラは、１つのメタブロックまたはメタブロックグループにデータファイルを記憶することが可能になる。結果として、データ統合およびガーベッジコレクション動作の回数と複雑さとが低減する。結果として、メモリシステムの性能が向上する。しかし、前述したように、ホスト／メモリインターフェイスが論理アドレス空間１６１（図７）を含んでいる場合、メモリコントローラがホストデータファイル構造について多く知ることは困難である。

図８を参照すると、図７にすでに示した典型的な論理アドレスホスト／メモリインターフェイスを別のやり方で示している。ホストが、ホストが生成したデータファイルを論理アドレスに割り当てている。次に、メモリシステムがこれらの論理アドレスを認識し、実際にデータを記憶してあるメモリセルブロックの物理アドレスに対してマッピングを行う。

ファイルベースのメモリインターフェイスおよび動作
ホストと、大容量のデータを記憶するメモリシステムとの間の、異なるタイプのインターフェイスにより、論理アドレス空間を用いなくていいようになる。そのかわり、ホストは、一意のファイルＩＤ（または他の一意の参照）と、ファイル内のデータ単位（バイトなど）のオフセットアドレスとにより、各ファイルに対し論理的にアドレス指定を行う。このファイルアドレスを、直接メモリシステムのコントローラに渡し、各ホストファイルのデータを物理的に記憶してあるそれ自体の表に保存する。図２〜図６に関連して前述した同じメモリシステムで、この新しいインターフェイスを実施することができる。前述したものとの主な違いは、メモリシステムがホストシステムと行う通信方法である。

図７の論理アドレスインターフェイスと比較を行うべき、このファイルベースのインターフェイスを、図９に示す。ファイル１、２および３のそれぞれの識別名と、図９のファイル内のデータオフセットを、直接メモリコントローラに渡す。次に、メモリコントローラ機能１７３により、この論理アドレス情報を、メタブロックの物理アドレスおよびメモリ１６５のメタページに変換する。ファイルディレクトリは、それぞれ記憶してあるセクタ、ページまたは他の単位のファイルデータが属するホストファイルを常に把握している。

図８の論理アドレスインターフェイスと比較を行うべき、ファイルベースのインターフェイスを、図１０にも示す。図８のＦＡＴ表に保持した論理アドレス空間およびホストについては、図１０に示していない。むしろ、ファイル番号と、ファイル内のデータオフセットとにより、メモリシステムに対して、ホストが生成したデータファイルの識別を行う。次に、メモリシステムのコントローラは、メモリセルアレイの物理ブロックに対して直接ファイルのマッピングを行い、ホストファイルを記憶してあるメモリブロックのファイルディレクトリおよびインデックステーブル情報を保持する。そして、ホストは、論理アドレスインターフェイスの管理に現在必要なファイルアロケーションテーブル（ＦＡＴ）を保持する必要はなくなる。

図１１は、そのプロセッサと、コントローラの他の回路とで実行するメモリシステムのファームウェアが実行する直接データファイルシステムの主な機能の概要のブロック図である。これは、以下で説明する特定のメモリ動作について想定した、全体的なフレームワークである。ファイルベースのインターフェイス６０１層が、メモリシステムと、外部ホストシステム、または同じメモリカードまたはフラッシュドライブ上で実行するホストアプリケーションとの間で、コマンドおよびデータのやりとりを行う。ホストアプリケーションは、メモリシステムの３つの主な機能、すなわち、ファイルの書き込み、ファイルの削除、およびファイルの読み出しを行う。フラッシュメモリアレイ６０３内に、データを記憶してある。

ファイルブロック管理機能６０５は、データを識別したファイルに基づいて、フラッシュメモリへのデータの記憶を整理し、データを記憶するブロックが２つ以上のファイルになることを最小限にする。メモリ６０３の物理メモリセルブロックが、データ管理の基本単位である。

個別のメタページが特定のファイル内で連続する論理オフセットアドレス範囲のデータを含むように、機能６０７により、データをメタページに整理して、メモリ６０３に書き込みを行う。機能６０９は、メモリ６０３へのアクセスを制御し、そこに記憶してあるデータの読み出しを行う。ホストからコマンドを受けた場合、ファイルのデータの消去を行うことにより、機能６１１に、機能６１３が保持しているファイル索引付け情報および機能６１５内のブロックのリストの更新を行わせる。

ファイルデータ索引付け６１３は、一意のファイル識別子と、ファイル内のデータのオフセットアドレスとにより、メモリ６０３に記憶してある個別のファイルの索引付けを行う。各ファイルのデータは、連続する論理オフセットアドレスを有するデータセットグループとして記憶してある。ファイルディレクトリは、個別のファイルに対し、データグループエントリセットのファイルインデックステーブル（ＦＩＴ）の位置の識別を行う。消去が行われたブロックのＩＤ、部分的にファイルデータのプログラミングが行われたブロック、または使われなくなったデータとともにファイルデータを含むブロックのいずれかのＩＤを、ブロックリスト機能６１５により保持する。

前述したガーベッジコレクションおよびデータ統合機能の主な目的は、使われていないメモリ空間を解放して、追加データの記憶に用いることである。ガーベッジコレクションでは、ソースブロックの有効なデータを、使われなくなったデータも含んでいるブロックから、少なくとも消去が行われた空間をある程度有する１つ以上の宛先ブロックにコピーする。これにより、有効なデータをより少ない数のブロックに統合するので、一旦もともとのソースブロックを消去したならば、使われなくなったデータが占有していた容量を解放することになる。データ統合では、消去されているが使われていない空間を含む、１つの部分的に埋められているブロックの有効なデータを、別の部分的に埋められているブロックの有効なデータと結合する。最も一般的には、部分的に埋められているブロックは、部分的に一部分だけが埋められている、最後に消去したブロックで閉じられている新しいファイルに書き込みを行うことに起因している。一旦、データを統合したならば、次に、複製のデータとなる、コピーしたてのデータを含むソースブロックを消去し、新しいデータを記憶するのに利用できるようにする。

ガーベッジコレクションおよびデータ統合動作は両方とも、ここではブロック解放として一緒に扱う。機能６１７は、プログラミングを行っていないメタページを有する物理ブロック、または使われなくなったデータを含む物理ブロックから、他のブロックへの有効なファイルデータのコピーを制御することにより、ブロックを解放する。これにより、もともとのブロックを消去して、ブロックにある使われていない空間を解放できるようにし、この空間を新しいファイルデータの記憶に利用できるようにする。機能６１９は、解放可能な容量と、消去ブロックの数とに基づいて、ブロック解放動作を行う回数および期間を適応可能なように制御する。全体的なメモリシステムの性能を良好に保つやり方で、新しいファイルデータの書き込みを行う速度に対して最適な速度で、ブロックの解放を行う。

図１１の機能図では、変換層６２１およびインターフェイス層６２３がファイルインターフェイス６０１の上位に位置し、フラッシュメモリのバックエンドシステムとインターフェイスをとり、その動作の制御を行う。この例では、インターフェイス層６２３は、３つの異なるプロトコルのうちの１つにより、ホストまたはそれ以外のものと、メモリシステム外部のデータの通信を行う機能を有している。ファイルインターフェイス６２５は、ここでの説明の中心となるものであり、一意のファイル識別子とファイル内の論理オフセットアドレスとにより、個別のファイルのデータの識別を行う。オブジェクトインターフェイス６２７は、電子装置間でデータファイルのやりとりをするのに主に用いられるものであり、ファイルの大きさは通常周知のものである。インターフェイス６２７の既存のプロトコルは、マイクロソフト コーポレイション(Microsoft Corporation) のメディアトランスファープロトコル（ＭＴＰ）およびピクチャトランスファープロトコル（ＰＴＰ）を含んでいる。この例では、後方互換性のある論理（ＬＢＡ）インターフェイス６２９も含んでいる。磁気ディスクドライブシステムのものと同様の、現在フラッシュメモリカードが用いているプロトコルにより、インターフェイス６２９を介してデータを送信して、ホストが、定義済みのメモリシステムの論理アドレス空間に対し、データのアドレス指定を行う。

変換層６２１は、プロトコルアダプタ６３１、６３３および６３５を含んでいる。これらアダプタの機能により、インターフェイスプロトコル６２５、６２７および６２９それぞれのプロトコルをファイルインターフェイス６０１との共通プロトコルに変換する。変換層により、コマンド、データフォーマット等を、異なるプロトコル間で変換する。ＬＢＡプロトコルアダプタ６３５はさらに、メモリシステムの論理アドレス空間をスタティックファイルに分割する。次に、ファイルインターフェイス６０１が同じやり方で、これらのファイルを、インターフェイス６２５および６２７を介して通信する別個のファイルとして扱う。ＬＢＡプロトコルアダプタ６３５の機能の詳細は、発明者Ｓ．Ａ．ゴロベッツ(S. A. Gorobets)による２００５年８月３日出願の米国特許出願第１１／１９６，８６９号（特許文献２９）を参照されたい。変換層６２１およびインターフェイス層６２３の情報についてはさらに、発明者アラン・シンクレア(Alan Sinclair) による２００５年１２月２１日出願の米国特許出願第１１／３１６，５７７号（特許文献３０）により得られる。

新しいデータファイルのプログラミングを行ってメモリに取り込む場合、データを消去したメモリセルブロックに書き込む。ブロック内の第１の物理位置から開始し、ブロックの位置を介して連続して順に書き込みを進める。ファイル内のそのデータのオフセットの順序に関係なく、ホストから受け取った順に、データのプログラミングを行う。ファイルのデータをすべてメモリに書き込むまで、プログラミングを継続する。ファイルのデータ量が１つのメモリブロックの容量を超える場合、第１のブロックが満杯になったときは、第２の消去ブロックにプログラミングを継続する。第１のブロックと同じやり方で、ファイルのデータすべてを記憶するまで、または第２のブロックが満杯になるまで、第１の位置から順に、第２のメモリブロックにプログラミングを行う。第３のブロックまたは追加付加ブロックに対し、ファイルに残っているデータのプログラミングを行ってもよい。１つのファイルのデータを記憶してある複数のブロックまたはメタブロックは、物理的または論理的に連続している必要はない。説明を簡単にするため、特に明記がない限り、ここで用いる用語“ブロック”とは、特定のシステムでメタブロックが用いられているかどうかにより、消去ブロック単位または複数のブロックである“メタブロック”のいずれかについて言うものである。

図１２の状態図は、図１１に示すメモリ動作の全体的な機能を示す。個別のメモリブロックを考察すると、３つの状態のうちの１つになる。これらは、解放可能な容量のない、有効なファイルデータの記憶が行われている消去ブロック６４１およびブロック６４３と、プログラミングが行われない消去ページおよび／または記憶してあるが使われなくなった（無効な）データから、解放可能な容量を有している、有効なファイルデータを含んでいるブロック６４５とである。機能６４７が、消去したメモリブロックにデータの書き込みを行うことにより、得られるプログラミングが行われたブロックが解放可能な容量を保持しているかどうかに基づいて、カテゴリ６４３または６４５のブロックになる。機能６４９で示すように、ファイルを消去する場合、ファイルのデータを含んでいるブロック６４３を、解放可能な容量を有するブロック６４５に変換する。機能６５１が、ブロック６４５の使われていない記憶容量を解放することにより、それらのブロックを、新しいデータの書き込みが行われる消去ブロック６４１の状態に復帰させることになる。

図１３Ａを参照すると、メモリシステムに行うデータファイルの書き込みを示している。この例では、データファイル１８１は、メモリシステムの１つのブロックまたはメタブロック１８３の記憶容量よりも大きい。これは、縦の実線の間に延びている。従って、データファイル１８１の部分１８４は、第２のブロック１８５に書き込まれる。これらのメモリセルブロックは物理的に連続して示しているが、必ずしも連続している必要はない。ファイルのデータすべてをメモリに書き込むまで、ホストからの受信ストリーミングとして、ファイル１８１からのデータの書き込みを行う。図１３Ａの例では、データ１８１はファイルの初期データである。

メモリシステムが、記憶してあるデータの管理を行い、状態を常に把握する好適なやり方は、大きさが可変のデータグループを用いることである。すなわち、完全なファイルを形成する定義済みの順序でつながっている複数のグループのデータとして、ファイルのデータを記憶する。好ましくは、しかし、ファイルインデックステーブル（ＦＩＴ）を用いることにより、メモリシステムのコントローラがファイル内のデータグループの順序を保持する。ホストからのデータストリームとして書き込みが行われている間、ファイルデータの論理オフセットアドレス、またはデータを記憶する物理空間に不連続性があると、必ず新しいデータグループが始まってしまう。このような物理的な不連続性の一例は、ファイルのデータが１つのブロックで満杯になり、別のブロックへの書き込みが始まる場合である。図１３Ａにこれを示す。第１のデータグループが第１のブロック１８３で満杯になり、第２のデータグループとしてのファイルの残っている部分１８４を第２のブロック１８５に記憶する。第１のデータグループを（Ｆ０，Ｄ０）で示す。Ｆ０がデータファイルが開始したときの論理オフセットであり、Ｄ０がファイルが始まるメモリ内部の物理位置である。第２のデータグループを（Ｆ１，Ｄ１）で示す。Ｆ１が第２のブロック１８５が始まるときに記憶してあるデータの論理ファイルオフセットであり、Ｄ１がデータを記憶してある物理位置である。

ホスト−メモリインターフェイスを介して転送するデータ量について、多数のバイト数のデータ、多数のデータセクタ、または他の細分性で述べる場合もある。現在の論理アドレスインターフェイスを介して大容量メモリシステムと通信を行う場合、ホストは大抵の場合、そのファイルのデータをバイト細分性で定義するが、次に、バイトを５１２バイト毎のセクタにグループ化を行ったり、または多数のセクタ毎のクラスタにグループ化を行ったりする。これは、メモリシステムの動作を簡略化するために通常行われている。ここで説明するファイルベースのホスト−メモリインターフェイスは他の単位のデータを用いる場合もあるが、もともとのホストファイルのバイト細分性が一般的には好ましい。すなわち、好ましくは、セクタ、クラスタ等ではなく、データオフセット、長さ等を、バイトで、最小の合理的な単位のデータで表現する。これにより、ここで説明する技術によるフラッシュメモリ記憶装置の容量をより効率的に利用することが可能になる。

次に、図１３Ａに示すやり方でメモリに書き込んだ新しいファイルを、この順で、データグループのインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１、Ｄ１）シーケンスとしてＦＩＴで表す。すなわち、ホストシステムが特定のファイルにアクセスしたい場合は必ず、ホストはそのファイルＩＤまたは他の識別名をメモリシステムに送信し、次に、そのＦＩＴにアクセスして、そのファイルを構成するデータグループの識別を行う。メモリシステムの動作の便宜上、これらの個別のエントリも個別のデータグループの長さ＜ｌｅｎｇｔｈ＞に含めてもよい。用いる際には、メモリコントローラは、データグループの長さを算出し、記憶する。

好ましくは、ホストが図１３Ａのファイルを開いている状態に保持している限り、ホストからさらにデータを受信してそのファイルに書き込みを行う位置を定義できるように、物理書き込みポインタＰについても保持する。ファイル内の新しいデータの論理位置に関わらず、物理メモリ内のファイルの終端にファイルの新しいデータの書き込みを行う。メモリシステムにより、４つまたは５つのファイルなどの複数のファイルを１度に開いたままにしておくことが可能になり、それぞれに対し書き込みポインタＰを保持する。異なるファイルの書き込みポインタは、異なるメモリブロック内の位置を指している。メモリシステムに、すでに存在する開いているファイルの数に制限があるときに、ホストシステムが新しいファイルを開きたい場合、開いているファイルのうちの１つをまず閉じて、次に、新しいファイルを開く。

図１３Ｂは、図１３Ａの前に書き込みが行われたもののまだ開いたファイルとなっているファイルの終端に、ホストがデータの追加を行うことを示す。ホストシステムが、ファイルの終端にデータ１８７を追加していることを示している。これは、そのファイルのデータの終端で、第２のブロック１８５に書き込みが行われている。追加データはデータグループ（Ｆ１，Ｄ１）の一部となるので、これでデータをさらに含むことになる。というのは、既存のデータグループ１８４と追加データ１８９との間に論理的にも物理的にもアドレス不連続性がないからである。従って、満杯になったファイルはやはり、ＦＩＴのインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ１）のシーケンスとして表される。ポインタＰのアドレスについても、記憶した追加データの終端のアドレスに変更する。

図１３Ａの前に書き込みを行ったファイルへのデータブロック１９１の挿入についての一例を図１３Ｃに示す。ホストがデータ１９１をファイルに挿入しているが、メモリシステムは、前に書き込みを行ったファイルデータの終端の位置１９３に挿入したデータを追加している。ホストがファイルを閉じた後で、バックグラウンドで後で行うこともあるが、開いているファイルにデータの挿入を行っている間、それらの論理の順序でファイルのデータの書き換えを行う必要はない。１つの新しいグループ（Ｆ１，Ｄ３）を形成する場合、挿入したデータをすべて、第２のメモリブロック１８５に記憶するからである。しかし、この挿入を行うことにより、図１３Ａの前のデータグループ（Ｆ０，Ｄ０）になり、挿入前のグループ（Ｆ０，Ｄ０）と、挿入後のグループ（Ｆ２，Ｄ１）との２つのグループに分割される。これは、挿入の始点Ｆ１と挿入の終点Ｆ２とで発生するようなデータの論理的な不連続性がある場合は必ず、新しいデータグループを形成する必要があるからである。グループ（Ｆ３，Ｄ２）は、第２のブロック１８５の始点である物理アドレスＤ２の結果である。たとえ同じメモリブロックに記憶してある場合であっても、グループ（Ｆ１，Ｄ３）および（Ｆ３，Ｄ２）を、別々に保持する。つまり、記憶してあるデータオフセットに不連続性があるからである。次に、データグループインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ３）、（Ｆ２，Ｄ１）、（Ｆ３，Ｄ２）の順で、挿入のもともとのファイルをメモリシステムＦＩＴに表す。メモリ内のデータを全部使って、新しいファイルまたは既存のファイルの新しいデータの書き込みを行うこともできることが、図１３Ａ、図１３Ｂおよび図１３Ｃの例からわかることに留意されたい。

図１３Ｃに示す既存のファイルへのデータの挿入に代えて、データを挿入したときは必ず、ホストが別個のファイルとしてメモリにファイルの書き換えを行ってもよい。次に、メモリシステムは、この別個のファイルを新しいファイルとして処理することもある。次に、ホストが古いファイルを削除し、メモリシステムは、データがもう使われなくなった古いファイルを記憶してある空間の解放に応答できる。

図１３Ｄは、図１３Ａに示すやり方でもともと書き込みを行ったデータのある一部分を更新する、別の例を示す。データファイルの部分１９５が更新部分である。更新を行ってメモリシステムの全ファイルの書き換えを行うのではなく、ファイルの更新部分１９７を、前に書き込みを行ったデータに追加する。前に書き込みを行ったデータの部分１９９は、今は使われなくなっている。更新を行った後、データグループインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ３）、（Ｆ２，Ｄ１）、（Ｆ３，Ｄ２）の順で、ファイルをメモリシステムＦＩＴに表す。図１３Ａの１つのデータグループ（Ｆ０，Ｄ０）を、図１３Ｄに示す部分に再度分割する。更新部分の前のグループと、更新部分と、更新部分の後のグループとである。使われなくなったデータが占有している空間１９９を解放することが望ましいが、メモリにファイルデータの書き込みを行う一部としてではなく、好ましくは、後で行う。典型的には、このような解放を行うことにより、記憶してある特定のファイルのデータのデータグループの数がより少なくなる。

好ましくは、各ファイルのデータのオフセットを、前の説明によるファイルの生成または変更を行った後で、正しい論理的順序で連続して保持する。従って、データをファイルに挿入する動作の一部として、例えば、ホストが行った挿入したデータのオフセットは、挿入の直前のオフセットから連続し、挿入後のすでにファイルに入っているデータを、挿入したデータ量で増分する。最も一般的には、既存のファイルの更新を行うと、類似量の更新データで置き換えられた既存のファイルの任意のアドレス範囲のデータになるので、通常、他のファイルのデータのオフセットを置き換える必要はない。

図１３に関連して前述した、データの割り当ておよび索引付け機能はすべて、メモリシステムのコントローラが行うことに留意されたい。適切なコマンドとともに、ホストは単に、ファイルＩＤおよびファイル内のデータのオフセットをメモリシステムに送る通信を行うだけでよい。残りはメモリシステムが行う。

前述したやり方でホストからのファイルデータを直接フラッシュメモリに書き込みを行う利点は、このように記憶してあるデータの細分性または分解を、ホストのデータと同じように保持することができることである。ホストアプリケーションが１バイトの細分性でファイルデータの書き込みを行う場合、例えば、そのデータについても、１バイト細分性でフラッシュメモリに書き込みを行う。次に、個別のデータグループ内のデータ量および位置を、バイト数で測定する。すなわち、ホストアプリケーションファイル内で別々にアドレス指定可能なデータの同じオフセット単位については、フラッシュメモリに記憶したときのそのファイル内でもやはり別々にアドレス指定可能である。次に、ブロック内の同じファイルのデータグループ間の境界はいずれも、最も近いバイトまたは他のホストオフセット単位に対し、インデックステーブルで指定されている。同様に、ブロック内の異なるファイルのデータグループ間の境界は、ホストのオフセット単位で定義されている。

用語“セクタ”とは、ここでは大きなブロックのメモリに用いられ、ＥＣＣが対応づけられている記憶してあるデータの単位を表している。セクタも、フラッシュメモリとやりとりするデータ転送の最小単位である。“ページ”は、ブロック内のメモリセルの単位を表すのに用いられ、プログラミングの最小単位である。“メタページ”とは、メタブロックの完全な並列処理を行うページを表すのに用いられる。メタページは、プログラミングの最大単位である。

ファイルブロックの管理
図１１のファイル対ブロックマッピング機能６０５の一例を以下に説明する。外部ホストまたはホスト内部処理のいずれかから、メモリシステムにデータの書き込みを行うか、またはデータ解放動作の一部として、メモリの他の位置からコピーする場合、特定の処理に基づいて、データを記憶する宛先ブロックを選択する。この処理では、記憶してあるファイルデータの構造に基づいて、特定のブロックの種類を認識する。次に、多数の状態のうちの１つとして、メモリシステムに記憶してある各ファイルに注記を行う。ファイルの状態はそれぞれ、ファイルのデータを記憶してあるブロックの数と種類とで定義済みである。ファイルにデータの書き込みを行う場合、その現在の状態と、ある状態から別の状態へ許可されている遷移とを制御して、１つ以上の他のファイルのデータも含んでいる特定のファイルのデータを含むブロックの数を制限する。これにより、メモリブロックの効率的な利用を促進し、新しいデータまたはコピーしたデータを受け入れるのに十分な消去ブロックを全メモリで保持するのに必要な、後で行う解放動作の頻度を低減する。

この例で認識される、ファイルデータを含むブロックの種類は以下の通りである。
“ファイルブロック”とは、完全にプログラミングが行われ、１つのファイルの有効なデータを含んでいる。使われなくなったデータをいくつか含んでいることもある。
“プログラムブロック”とは、部分的にプログラミングが行われ、１つのファイルにだけ有効なデータを含んでいる。消去した容量がいくらかブロックに残っている。使われなくなったデータをいくつか含んでいることもある。
“共有ブロック”とは、部分的にプログラミングが行われ、２つ以上のファイルに有効なデータを含んでいる。消去した容量がいくらか残っている。使われなくなったデータをいくつか含んでいることもある。
“フル共有ブロック”とは、プログラミングが完全に行われ、２つ以上のファイルに有効なデータを含んでいる。使われなくなったデータをいくつか含んでいることもある。
“フルプログラムブロック”とは、ファイルに直近に書き込まれたデータと使われなくなったデータとを含む場合、満杯になったプログラムブロックに対する一時指定であり、ファイルに対し存在するオフセットアドレスの範囲は、１つのブロックが収容可能ものである。ファイルに書き込む次のデータが、１つのブロックが収容可能なオフセットアドレスの範囲を超えている場合、フルプログラムブロックは次に、ファイルブロックとして指定を受ける。完全プログラムブロックは、既存の論理ブロックアドレス（ＬＢＡ）システムの完全な無秩序(Chaotic) ブロックに相当する。というのは、一旦有効なデータの指定を行って、使われなくなったデータを少なくとも別のときに１回指定したならば、このブロックにファイルの特定の論理オフセットの書き込みを複数回行うからである。

別のブロックの種類は、“消去ブロック”であり、ブロックの全容量のプログラミングを行わず、データを受け入れられるようにしたものである。メモリが満杯であったり、または全データ量に近かったりする場合、典型的には、使用されているブロック内に存在する使われていない容量を連続して解放することにより、指定の最小数の消去ブロックのプールを保持する。

“フラクタルブロック”とは、プログラムブロック、共有ブロックまたはフル共有ブロックのことを言う全体的な用語である。ファイルのフラクタルブロックは、プログラミングを行わないメモリ容量、他のファイルの有効なデータのいずれか、または両方とともに、有効なファイルのデータを含んでいる。ここで説明する技術の主な目的は、ファイルのデータを受け取ると指定されているアクティブブロックの種類を管理することにより、メモリシステム内のフラクタルブロックの数を最小限にすることである。これにより、指定の最小数の消去ブロックを保持するのに必要なガーベッジコレクションおよびデータ統合（ブロック解放動作）の原因を低減する。そして、データの内部コピーを行って、前にプログラミングを行ったブロック内の使われていない容量の断片を解放するのに時間がかからないので、メモリにデータの書き込みを行う速度が上がる。

ここで他の種類のブロックについて用いられる用語を、まとめて説明する。
“部分ブロック”とは、プログラミングを行わない容量、１つ以上のファイルの有効なデータを含むもので、使われなくなったデータを含む場合もある。プログラムブロックおよび共有ブロックが、部分ブロックの一例である。
“使われなくなったブロック”とは、使われなくなったデータを含むファイルブロックまたはフル共有ブロックである。使われなくなったブロックは、消去した容量を含まず、有効なデータおよび使われなくなったデータの両方を含んでいる。
“無効なブロック”とは、有効なデータを全く含まないものである。無効なブロックは、少なくとも使われなくなったデータを含み、有効なデータを含まない、消去した容量を含んでいる場合もある。

図１４Ａ〜図１４Ｅは、前に説明した種類のブロックを用いる例をいくつか示している。図１４Ａでは、ファイルＡのデータが、ブロック６６１および６６３に埋められ、第３のブロック６６５に部分的に埋められている。この例の各ブロックには、左から右へデータの書き込みを行う。まずブロック６６１を埋め、次に、ブロック６６３を埋め、その後、ブロック６６５の一部分に書き込みを行う。残っているブロック６６５の部分は、追加のデータを記憶可能な、プログラミングを行わない消去した容量である。ブロック６６１および６６３は、前の定義によるファイルブロックであり、ブロック６６５はプログラムブロックである。新しいデータがあれば、ブロック６６５に書き込みを行い、プログラムポインタＰから開始する。ブロックにデータの書き込みを行う際に、ポインタＰは左から右へ移動して、ブロックの次に利用可能な記憶位置を常に示している。プログラミングを行わない消去した容量を保持する個別のブロックに対して、現在アクティブであるかどうかをこのようなポインタが保持するので、ブロックに書き込みを行う他のデータの物理アドレスが常にわかるようになる。

一例として、図１４Ｂは、ファイルブロック６６２とフルプログラムブロック６６７とに記憶したファイルＡを示す。フルプログラムブロックに対する前の定義により、ブロック６６７は、ファイルＡの直近の書き込みデータと、使われなくなったデータとを含み、使われていない容量はない。また、前の定義により、２つのブロック６６２および６６７に記憶したファイルＡの全データ量は、１つのブロックの記憶容量に等しい。プログラムポインタＰが示すブロック６６７の終端に、ファイルＡの最後のデータが書き込まれている。さらにファイルＡのデータを受信した場合、別のブロックに対しプログラミングを行う。そのブロックが、ブロック６６７のファイルＡのデータを集めた別のブロックになる。というのは、使われなくなったデータが占有する空間を解放するからである。あるいは、完全に消去したブロックに、追加データの書き込みを行うことができる。いずれの場合も、ポインタＰは、追加したファイルＡのデータの開始位置の新しいブロックに移動する。次に、ブロック６６７がファイルブロックになる。従って、まさに図１４Ｂに示したときだけ存在するので、ブロック６６７は過渡的なものである。ファイルＡのデータですべて埋まってしまう直前のものがプログラムブロックであって、ファイルＡの新しいデータが書き込まれると直ちに、ファイルブロックになる。

図１４Ｃの例は、共有ブロックであるブロック６６９を含んでいる。というのは、別のファイルＢのデータとともに、現在のファイルＡのデータと、プログラミングを行わない容量とを含んでいるからである。ファイルＡの終端でブロック６６９に新しいデータの書き込みを行い、プログラムポインタＰが示すところから開始する。ブロック６６９は、ファイルＡのアクティブブロックである。プログラムポインタＰのところでファイルＡまたはＢの追加データの書き込みを行う場合には、ファイルＢのアクティブブロックである場合もある。あるいは、個別のブロック（図示せず）がファイルＢのアクティブブロックであってもよい。

この形態のプログラミングを行わない容量をうまく利用するために、消去ブロックではなく、別のファイルのデータをすでに含んでいる部分ブロックの消去した容量に直接ファイルのデータの書き込みを行ってもよい。これは特に、ファイルデータの量が満杯のブロックの容量より少ないとわかっているファイルデータの書き込みを行う場合に、有益である。既存の部分ブロックの検索を行って、書き込みを行うデータの量がわかっているデータに合う消去した容量の量を検出する。データのページの数（または、メタブロックを用いる場合はメタページ）を、部分ブロック内のプログラミングを行わない、消去した容量のページの数と比較する。このようにプログラムブロックの使われていない消去が行われた空間に対しプログラミングを行う場合、共有ブロックに変換する。

図１４Ｄでは、ファイルブロック６６１と、ブロック６７１の一部分と、ブロック６７３の一部分とにファイルＡを記憶してある。２つのファイルＡおよびＢのデータで満杯なので、ブロック６７１はフル共有ブロックである。ブロック６７３は、図１４Ａのブロック６６５と同様のプログラムブロックである。ブロック６７３はファイルのアクティブブロックであり、ポインタＰがブロック６７３内の使われていない容量の位置を指し、追加データの書き込みを開始するところである。

図１４Ｅの例では、フル共有ブロック６７１および共有ブロック６７５の一部分にファイルＡの書き込みを行う。ブロック６７５は、第３のファイルＣのデータを含んでいる。ポインタＰは、アクティブブロック６７５の使われていない部分の最初の位置を指し、追加データの書き込みを行うところである。

図１４Ａ〜図１４Ｅの例では、いくつかの異なる種類のブロックを説明するために、複数のブロックにファイルのデータを記憶してあるものを示しているが、多くの場合、ファイルを記憶するには、もっと少ない数のブロックで十分であって、１つのブロックでも十分である。ここで説明する技術は、このような小さいファイルにも適用可能である。また、大きいファイルは、４つ以上のブロックのページを占有することになる。

ブロック６６５、６６７、６６９、６７１、６７３および６７５は、フラクタルブロックであることに留意されたい。任意の１つのファイルのデータが占有するフラクタルブロックの数を最小限にすることが望ましい。というのは、それらブロックが存在することで、それらの使われていない容量を解放する必要性が増すので、システムの性能に悪影響を与えるからである。使われていない消去した容量は、部分ブロック６６５、６６９、６７３および６７５にあるが、ファイルの書き込みが行われていないデータ量がわかっていて、かつそのわかっている量が、これらのブロックのうちの１つの使われていない容量と一致していなければ、ホストからの新しいデータの書き込みをこの空間に直接行うことを効率的に行えない。最も一般的には、特定のファイルに対するホストからのデータ量がわかっていないので、これらのビットの容量をすぐには埋められない。従って、メモリ容量を効率的に利用するために、解放動作を行う間、別のブロックから使われていない空間へデータを移動する必要がある場合もある。ブロック６６９、６７１および６７５は２つ以上のファイルのデータを含み、このことは、ファイルのうちの１つを削除したり、または共有ブロックに記憶したそのデータが使われなくなったりした場合、データの解放を行って、使われなくなったデータが占有するブロックの容量を解放する可能性があることを意味している。

従って、データ解放動作に必要な時間を減らすために、１つ、２つまたは他の数のフラクタルブロックに限って１度に特定のファイルのデータを記憶できるようにする。ここで説明する具体例では、２つ以下のフラクタルブロックにしか任意の１つのファイルのデータを記憶しないようにする。新しいアクティブブロックを指定してファイルのデータを記憶する処理について考える。許可されているファイル状態のセットのうちの１つを、ファイルのデータを記憶してあるブロックの種類で定義済みの各ファイルに割り当てる。既存のブロックが満杯になった場合などで、特定のファイルのデータを受け取るのに新しいアクティブブロックに割り当てが必要な場合、ファイルの状態によりブロックの種類をこのように指定するが、多くの場合、他の要因も考えられる。

ここで説明するメモリ動作のコンセプトの具体的な実施例における、フラクタルブロックおよびファイルのデータを記憶してあるフルプログラムブロックの種類および組み合わせについて、１０の許可されているファイル状態０〜９の定義を図１５の表に示す。許可されているファイル状態のそれぞれにより、たった２つのフラクタルブロックまたは１つのフルプログラムブロックに対してデータの記憶が可能になる。ファイルに対応付けられているファイルブロックの数に、制限はない。メモリがホストからそのデータを受け取る場合と、解放動作を行う間メモリ内でデータを再配置する場合との２つの場合では、これらのファイル状態を用いて、ファイルデータを記憶するアクティブブロックを選択する。メモリシステムに記憶してある全ファイルの状態を監視して、他の情報とともに、ファイルのＦＩＴレコードのヘッダといったファイルインデックステーブル（ＦＩＴ）６１３（図１１）に、記録する。状態遷移が発生した場合は必ず、ＦＩＴエントリを更新して、新しいファイル状態に記録する。

図１５で定義済みのファイル状態０〜９の間の得られる主な遷移について、図１６の状態図を示し、図１７の表で説明する。これらの３つの図から、好適なメモリシステムの動作の詳細がわかり、この動作を行うのに十分であると考えられる。しかし、この動作のある態様について、さらに説明する。

図１５の表に示すように、フラクタルブロックにデータがないので、ファイルを状態０と指定する。他の種類のブロックがファイルブロックだけなので、ファイルのデータは１つ以上のファイルブロックにしか書き込まれないものか、ファイルのデータをどのブロックにも記憶していないものかのいずれかである。前者が、データ量とブロック容量との間で必要な正確さによる一時的条件である可能性が一番大きい。この後者の条件は、メモリシステムが新しいファイルの情報を受け取ったものの、そのファイルのデータの書き込みをまだ行っていない場合に発生する。いずれの場合も、アクティブブロックがデータを受信すると指定する必要がある。ホストから長さがわからないデータを受け取った場合、消去ブロックをアクティブブロックとして指定する。一旦、消去ブロックにデータの書き込みを行ったならば、このブロックがアクティブプログラムブロックになったので、状態０から状態２へファイルが遷移する（図１６を参照）。

しかし、ファイル状態０であり、ホストから受け取った新しいファイルのデータの長さがブロックの記憶容量より小さいとわかっている場合、消去した容量が、わかっているデータ量を記憶するのに十分に利用可能ならば、部分ブロックをアクティブブロックとして指定する。次に、ファイルは状態０から状態３へ遷移する（図１６を参照）。このような部分ブロックは、プログラムブロックまたは共有ブロックである。長さがわかっているデータと、利用可能な部分ブロックの残っている記憶容量との間で、考えられる最良適合となる。量がわかっているデータに対して十分な容量のある部分ブロックがまったくなければ、消去ブロックにデータの書き込みを行うことにより、状態０から状態２へファイルが遷移する。

状態２のファイルの特徴は、プログラムブロックが、ファイルの追加データの受け取りに割り当てられていることである。しかし、ファイルが十分大きければ、ブロックは最終的に満杯になり、次に、別のアクティブブロックを指定する必要がある。今はファイルブロックである満杯のブロックには、使われなくなったデータは含まれず、ファイルは状態０に戻る。ここでは、アクティブブロックと指定しない。次に、前述したように、追加データを記憶する量によるが、消去ブロックまたは部分ブロックを、新しいアクティブブロックとして指定する。しかし、満杯のブロックに使われなくなったデータが含まれていて、ファイルの最大オフセットが、１つのブロックが収容可能なオフセットアドレスの範囲より小さければ、前の定義により、フルプログラムブロックになる。次に、好ましくは、その有効なデータを消去ブロックにコピーすることにより、ブロックを圧縮し、もともとのブロックを消去する。得られるブロックは、この有効なデータと消去した容量とを含むので、部分ブロックになる。次に、この新しい部分ブロックがアクティブプログラムブロックになる。ファイルの状態は、状態２から状態１へ遷移して、状態２に戻る（図１６を参照）。しかし、状態１でファイルのデータを受け取って、そのオフセットアドレスが、１つのブロックが収容可能なアドレス範囲を超えている場合、フルプログラムブロックはファイルブロックになる。そして、ファイルは状態０に遷移する。

部分ブロックとして、解放動作を行う間、ファイルが状態２のときに存在するアクティブプログラムブロックを、ソースブロックからの別のファイルの量がわかっているデータの宛先ブロックとして選択する。プログラムブロックのＩＤを、リストのそれぞれのブロック内に利用可能な消去した容量を含んでいる部分ブロックのリストに保持する。ソースブロックからコピーするデータ量は、リストの部分ブロックの消去した容量と合っている。解放動作を行う間、現在のファイルのプログラムブロックを別のファイルのデータの宛先ブロックとして選択する場合、他のファイルのデータをその消去した容量にコピーした後で、プログラムブロックは、現在のファイルのアクティブ共有ブロックになる。そして、ファイルは、状態２から状態３へ遷移する（図１５および図１６参照）。

さらに、ファイルが状態２の間に、プログラムブロックを解放する動作一部として、ファイルのプログラムブロックに書き込んだデータを、別のファイルのデータを記憶してある部分ブロックである別のブロックにコピーする可能性がある。この状況で、解放動作の宛先ブロックがアクティブ共有ブロックになる。ファイルは状態２から状態４へ遷移する。これで、共有ブロックにファイルの別のデータの書き込みを行うことになり、ファイルのアクティブブロックになる。

状態２のファイルのアクティブ共有ブロックが満杯になった場合、フル共有ブロックとして指定する。そして、２つのフラクタルブロック、フル共有ブロックおよびプログラムブロックの限度まで、ファイルが入る。別のフラクタルブロックがファイルのデータの受け取りに割り当てられていないので、ファイルのデータをプログラムブロックから消去ブロックにコピーし、この新しいブロックをファイルのアクティブプログラムブロックとして指定する。ファイル状態遷移の一部として、このようなファイルデータのコピーを、ここでは“データ遷移”として識別し、図１６および図１７にそのように注記する。そして、ファイルは状態４から状態８へ遷移する。

状態遷移が完了したと見なす前に、すべてのデータ遷移を１つの動作として完了する。このことは、ファイルに、データの書き込みを行うアクティブブロックが必要な場合、データ遷移のデータコピー部分が完了するまで、メモリは他の動作を行うことができないことを意味している。従って、典型的には、このデータコピーを、時間の経過とともに他のメモリ動作と交互に行うことはできない。

ファイル状態４から状態３への遷移は、そのプログラムブロックを解放するブロックと指定する場合に発生する。解放動作の一部として、プログラムブロック内のファイルのデータを共有ブロックに移動する。その後、共有ブロックがファイルのアクティブブロックになる。さらに、一旦、状態４のファイルのアクティブ共有ブロックが満杯になったら、ファイルを２つのフラクタルブロックに記憶する。フラクタルブロックのうちの１つを削除するまで、別のブロックをアクティブブロックとして割り当てることはできない。従って、状態４から状態７への遷移の一部として、プログラムブロック内のデータを部分ブロックの消去した容量に移動し（データ遷移）、これにより、フラクタルプログラムブロックを削除する。そして、得られる共有ブロックがファイルのアクティブブロックになる。

状態３のときに、アクティブ共有ブロックにファイルのデータの書き込みを行う。解放動作を行う間、ファイルのデータをアクティブ共有ブロックから部分ブロックの消去した容量に移動する場合、宛先部分ブロックがファイルの別のデータを書き込むアクティブ共有ブロックになる。そして、ファイルは状態３から状態６へ遷移する。しかし、ソースプログラムブロックから移動するデータ量が、部分ブロックのリスト上の部分ブロックの容量とうまく適合しない場合、共有ブロック内のファイルデータを、そのブロックから消去ブロックへ移動するので、その消去ブロックがファイルのアクティブプログラムブロックになる。そして、ファイルは状態３から状態２へ遷移する。この状態遷移の途中で、アクティブブロックの割り当てが、もともとの共有ブロックから新しい消去ブロックへのデータ遷移を含んでいると、次に、ファイルのアクティブプログラムブロックになる。

ファイルが状態３にあるときの別の可能性は、ファイルのデータが書き込まれるアクティブ共有ブロックが満杯になることである。次に、ファイルには別のデータを書き込むアクティブブロックがなくなり、状態５へ遷移する。この状態は、ファイル状態０のときの動作と同様の状態で、ファイルのアクティブブロックはないが、ファイルが状態５のときに、フル共有ブロックにファイルのデータが含まれている点が異なっている。状態０のときには、ファイルのデータを含んでいるフラクタルブロックはない。通常、２つの状態０および５は一時的状態で、この状態から、ファイルの追加データの書き込みを行うと直ちに遷移が始まる。

状態５のとき、他のファイル状態への考えられる遷移は、状態５でかつ状態０ではないときに、共有ブロックにファイルのデータを記憶することを除いて、ファイルが状態０のときの遷移と同様である。データ量がわからない場合、消去ブロックをファイルの追加データに割り当てるので、アクティブプログラムブロックを生成し、ファイルが状態８へ遷移する。データ量がわかっている場合、部分ブロックの残っている容量に書き込みを行い、大きさがうまく適合したならば、これにより、部分ブロックがアクティブ共有ブロックになり、ファイルは状態５から状態７へ遷移する。状態８のときにフル共有ブロックにファイルのデータを記憶することと、ファイル状態２のときにこのようなブロックがないこととを除いて、ファイル状態８は状態２と同様である。ファイル状態７は、ファイル状態３に関連して同様である。

ファイル状態６で、アクティブ共有ブロックがデータで埋められている場合、フル共有ブロックおよび共有ブロックにファイルを記憶する。この実施形態における２つのフラクタルブロックの限度になったので、プログラムブロックまたは他のフラクタルブロックとして、別のブロックを割り当てることはできない。従って、データ遷移が発生しなければならない。データと部分ブロックの消去した容量とのふさわしい適合がなければ、共有ブロックのうちの１つからのファイルのデータを、部分ブロックに移動して（状態７へのファイルの遷移）、ファイルのアクティブ共有ブロックになるか、または消去ブロックに移動する（状態８へのファイルの遷移）。

ファイル状態７のときは、アクティブ共有ブロックは満杯にならない。ファイルを２つのフル共有ブロックに記憶して、状態９への遷移となる。

また、ファイルが状態７のときは、解放するブロックとして共有ブロックを指定するので、次に、ファイルのデータを再配置する必要がある。そして、データ遷移が発生する。ファイルのデータを共有ブロックから消去ブロックに移動し、その後、アクティブプログラムブロックになれば、ファイル状態８への遷移が発生したことになる。そうではなく、ファイルのデータを部分ブロックに移動したならば、部分ブロックは共有ブロックになり、ファイル状態は７のままである。

ファイルに追加データの書き込みを行う間、ファイルは２つのフル共有ブロックに残っているので、ファイル状態９は安定状態である。しかし、ファイルがその状態のときは、指定したアクティブブロックはない。２つのフラクタルブロックの限度があるので、ファイルに追加データの書き込みが可能になる前に、データ遷移は発生しなければならない。一例として、２つのフル共有ブロックのうちの一方のファイルのデータすべてを、消去ブロックに移動すると、このブロックが、ファイルの新しいデータを書き込むためのアクティブプログラムブロックになる。そして、ファイルは状態９から状態８へ遷移する。しかし、２つのフル共有ブロックのうちの一方のファイルのデータ量とファイルの追加データの全量がブロックの容量未満ならば、部分ブロック内の十分に消去が行われた空間を検索する。検出したならば、フル共有ブロックのうちの一方からのファイルのデータを部分ブロックに移動すると、ファイルの追加データの書き込みを行うためのアクティブ共有ブロックになる。これは、状態９から状態７への遷移となる。

ファイル状態８のときは、アクティブプログラムブロックにファイルのデータの書き込みが行われているが、他のファイルのデータは、フル共有ブロックに格納されたままになっている。プログラムブロックが満杯になった場合、ファイルブロックになり、ファイルのアクティブブロックはもうない。そして、状態は状態５に遷移する。さらにファイルが遷移することにより、前述したように、新しいアクティブブロックとして消去ブロックまたは部分ブロックを割り当てることになる。

しかし、状態８のときに、ファイルのアクティブプログラムブロックを解放動作のための宛先ブロックとして選択した場合、第１の場合では、ファイルの状態は、直接状態７に遷移する。これにより、ファイルの新しいデータを受け取るアクティブの共有ブロックを生成する。あるいは、状態８のときにファイルのアクティブプログラムブロックを解放動作のソースブロックとして指定した場合、ファイルのデータを部分ブロックに移動すると、ファイルに追加データを書き込むためのアクティブ共有ブロックになる。第２の場合では、ファイル状態は、やはり状態８から状態７へ遷移する。

図１６および図１７に示す主なファイル状態遷移の他に、発生する第２のファイルの遷移のセットがある。これらを図１８および図１９に示す。現在注目のファイルのこれらの第２の遷移は、現在のファイルのデータを含んでいるフラクタルブロック内に記憶した１つのファイルのデータすべてが使われなくなったときに発生する。使われなくなったデータは、現在のファイルのものであったり、または他のファイルのものであったりする。ホストがファイルを削除した結果として、ホストがファイルに前に書き込みを行ったデータを更新した結果として、または解放動作を行う間、ファイルのデータを再配置した結果として、データが使われなくなる。ファイルを更新する途中で、例えば、別のブロックに新しいデータの書き込みを行うことによりすべてを更新した場合、共有ブロックに記憶したファイルのデータすべてが使われなくなる。一例の解放動作では、現在注目のファイルではない、共有ブロック内のファイルのデータを別のブロックにコピーした場合、共有ブロック内の他のファイルのデータが使われないようにしておく。

これらの状況でデータを使わないようにすることにより、使われなくなったデータを記憶してあるブロックの種類を変更し、ファイルの状態が変わることになる。ファイルのデータ用に新しいアクティブブロックが必要な場合、新しいファイル状態に基づいて、図１６および図１７に関連して説明したやり方で選択する。

図１８の遷移と、発生する特定の遷移の図１９の識別名とが、これらのすべての説明になる。これらの遷移により、ファイルのデータを含んでいるフラクタルブロックの数が減る傾向にあるので、ファイル状態を簡素化することに留意されたい。これらの遷移により、ファイルの状態が、フラクタルブロックがない状態０に移行しやすくなる。

ファイルに対しデータのプログラミングを行うが、現在のファイルにアクティブブロックがない場合に、ファイル状態の情報を利用して、ファイルのアクティブブロックとして割り当てられたブロックの種類を判定する。図２０の表の右側の欄に、真ん中の欄で述べた条件下での状態０〜９の任意の１つでファイルに対するアクティブブロックの割り当てをまとめている。ブロックの種類は、図に示す順である。“最良適合部分ブロック”は、量がわかっているデータを効率的に利用できる量の消去した容量を有する部分ブロックを意味する。ふさわしい部分ブロックがない場合、最も一般的には消去ブロックを選択する。しかし、状態２または３のいずれかで、ファイルの最良適合の部分ブロックを識別できない場合、“最大部分ブロック”を割り当てる。これは、書き込まれる全データ量を十分処理できる消去した容量がないブロックであるが、そのデータの最大量を処理可能なブロックである。次に、ファイルの状態を変更し、新しい状態でブロックの選択を制御して、最大部分ブロックに適合しない残っているデータ量を受け付ける。しかし、データ量および部分ブロック内の利用可能な容量により、最大部分ブロックを利用してもデータを３つ以上のブロックに分割するようになる場合、消去ブロックをアクティブブロックとして割り当てる。

前述した動作を、図２に示す一例のメモリシステムに格納しているファームウェアを実行する、コントローラ１１のプロセッサ２７が実行してもよい。

ブロック容量の解放
前述したように、ブロック管理の一部には、ブロック内の使われていない容量を解放して新しいデータを記憶することが含まれている。メモリシステムに記憶するデータ量がその容量よりずっと少ない場合、これは、特に問題ではないが、好ましくは、メモリシステムを、データで満杯になっているように動作するように設計する。これは、使われなくなったデータだけを含んでいるブロックや、有効なデータを含んでいるが、使われなくなったデータおよび／または書き込みが行われていない消去ページもある他のブロックを、この使われていない容量を解放するように処理できることを意味している。この目的は、できるだけ余すところなくメモリシステムの記憶容量を利用することであり、同時に、システム性能への悪影響を最小限にすることである。ブロックの解放については、図１１の全体的なシステム動作図に６１７と記してある。

解放動作を行うと指定されたブロック（ソースブロック）内の有効なデータを、有効なデータを記憶するのに十分な消去した容量を有する１つ以上のブロック（宛先ブロック）にコピーする。前述したブロック管理技術に従って、宛先ブロックを選択する。ソースブロックに記憶した各ファイルのデータを、前述したように、ファイルの状態および他の要因に基づいて選択した種類のブロックにコピーする。解放動作の一部としての異なる種類のファイル間のデータコピーの一例を、図２１Ａ〜図２１Ｄに示す。

図２１Ａでは、２つの部分ブロック６８１および６８３の解放動作を、一例として示す。ブロック６８１は、ファイルＡの有効なデータを記憶してあるプログラムブロックであるが、データを記憶していない消去した容量も含んでいる。考えられる解放動作の１つは、ファイルＡの状態に基づいて、ブロック６８１のファイルＡのデータを、異なるファイルＢのデータをすでに含んでいる別の部分ブロック６８５の利用可能な消去した容量にコピーし、共有ブロックとすることである。次に、ＦＩＴでは、ブロック６８１内のデータグループをもう参照することはなく、このブロックには、使われなくなったという注記が付けられる。ブロック６８１内に記憶が行われる際に、ファイルＡは、プログラムブロックを含む、状態２、４または８（図１５を参照）のうちの１つになっている。次に、データを別のフラクタルブロックに移動することになるが、ファイルは、２つのフラクタルブロックの上限まで書き込まれたままである。ブロック６８５にコピーを行った後、ファイルＡは、状態３、４、６または７のうちの１つに遷移する。これは、他のファイルのデータを記憶してあるブロックの種類に基づいて共有ブロック内に記憶してある、ファイルのデータを含んでいる。

図２１Ａのブロック６８３は、ファイルＣおよびＤのデータに記憶してあるデータを、ファイルＥのデータを含んでいるプログラムブロック６８７の消去した容量にコピーすることにより、解放された共有ブロックであり、そして共有ブロックになる。ブロックそれ自体のように、ブロック６８３のファイルＣおよびＤのデータが使われなくなる。データをある共有ブロックから別の共有ブロックに移動したので、ファイルＣおよびＤそれぞれの状態は変わらない。しかし、ファイルＥの状態は、２から３、または８から７へのいずれかに変わっている。あるいは、ファイルＣおよびＤそれぞれのデータを互いに異なるブロックに移動することが可能であり、必ずしも共有ブロックの利用可能な空間にコピーする必要はない。そして、ファイルの状態はおそらく他の状態に遷移することになる。

図２１Ｂは、一例のブロック６８９および６９１の解放動作を示す。有効でかつ使われなくなったデータで満杯になっているので、これらのブロックはそれぞれ、使われなくなったブロックである。一部分が使われなくなり残りが有効な、ブロック６８９はファイルＦのデータを含んでいるファイルブロックである。これは、例えば、ファイルの終端に物理的に新しいデータの書き込みを行う、ファイルＦを更新する間に発生する。このファイルには、既存のファイルのデータとして同じ論理オフセットがあり、既存のデータが使われなくなる。この例では、ファイルＦのデータを、ファイルＧのデータを含んでいるプログラムブロック６９３の消去した容量にコピーし、ブロック６９３の種類が共有ブロックに変わることになる。あるいは、ファイルＦの有効なデータを消去ブロックに書き込むと、このブロックはプログラムブロックになる。

図２１Ｂのブロック６９１は、ファイルＨの無効なデータおよびファイルＩの有効なデータを含んでいるフル共有ブロックである。この例では、ファイルＩの有効なデータを、ブロック６９１から消去ブロック６９５にコピーする。そして、ブロック６９５がプログラムブロックになる。あるいは、良い適合があれば、ファイルＩのデータを、別のファイルのデータを含んでいる部分ブロックに書き込んでもよい。宛先ブロックは、解放動作を行ったときのファイルＩの状態に依存する。

図２１Ａおよび図２１Ｂに示す４つの具体的な一例の解放動作それぞれの結果として、２つの部分ブロックに記憶してあるデータを１つに結合すると、これにより、他の２つのブロックには使われなくなったデータだけが残ることになる。これらは無効なブロックになる。次に、図２１Ｃに示すように、ブロックの消去を行うことにより、もともとのブロック６８１、６８３、６８９および６９１それぞれの全空間を解放する。消去ブロックは、無効なブロックを解放した結果である。

図２１Ｄは、ファイルＪのデータを記憶してある一例のファイルブロック６９７を示す。ホストがファイルＪを削除した場合、ブロック６９７内のファイルＪのデータと、おそらく他のブロックのデータもまた、使われなくなる。そして、ブロック６９７は無効なものになる。無効なブロックを解放することにより、システムの消去ブロックプール用に、消去ブロックを生成する。

一般に、メモリからファイルの消去を行うと、共有ブロックまたはフル共有ブロックなどの１つ以上のフラクタルブロック内のファイルのデータも、使われなくなる。残っている別のファイルの有効なデータがブロックの記憶容量より少なく、小さい量となるので、そのブロックに対し解放動作を行う。

図２２のフローチャートに、一般的な解放動作を示す。ステップ７０１に示すように、具体的な実施形態に基づいて、１つ以上のリストを、部分ブロックと、使われなくなったブロックと、無効なブロックとに対し保持する。リストを、ブロックリスト６１５（図１１）の一部として保持してもよい。メモリ動作技術の１つにより、このブロックリストを、電源をはじめに入れたときなど、メモリシステムの開始時に形成する。このリストは、各ブロック内の有効なデータ量や各ブロック内の消去メモリ量といった、１度に１つずつ解放ブロックを選択可能な、ブロックの他の情報を含むことができる。典型的には、これらの量を、ブロックのページ数、またはメタブロックを用いる場合はメタページの数で測定する。好適な別の技術は、これらのリストを不揮発性メモリに保持して、その状態が変わったときは必ず、リストのブロックのエントリの追加または更新を行うことである。この技術により、メモリシステムを初期化する際に、ブロックを走査してリストを形成する必要がなくなる。リストの部分ブロックと、使われなくなったブロックと、無効なブロックとをすべて保持する代わりに、解放ブロックを選択する特徴の１つが、コピーする必要のある有効なデータがほとんどないもの、または全くないブロックなので、設定したしきい値量を下回る小さい量の有効なデータを有するブロックだけを含むようにする。非常に時間のかかる多くの解放動作で必要なことは、あるブロックから別のブロックにデータのコピーを行うことなので、通常、コピーするデータ量がより少ないブロックに対してはじめに行う。

データの書き込み、更新、移動、削除等を行うと、このようなブロックリストは常に変化する。種類が、部分ブロック、使われなくなったブロック、無効なブロックから変更したブロックになるという変化により、図２２のステップ７０１で保持するリストが変わることになる。このようなブロックに個別に記憶した有効なデータ量の変化と、消去した容量の量の変化とを、ブロックリスト６１５（図１１）にも注記を行う。

ステップ７０３において、好ましくは、解放するために、１つの解放ブロックを次のブロックとして更新したリストのものと識別する。部分ブロックまたは使われなくなったブロックならば、それが、宛先ブロックと呼ぶ別のブロックに有効なデータをコピーするソースである。ソースブロックの選択に用いられるいくつかの特定の技術について、以下に説明する。

次のステップ７０５で、ホストのコマンドに応答して、メモリ動作を行う必要があるかを考慮して、いま解放動作を行うことが妥当であるかどうかを判定する。ホストが、アイドルコマンド、または、ホストがメモリシステムに特定の動作を行わせるまで時間があることを示す、似たようなものをメモリシステムに送信した場合、メモリシステムは、解放動作を含むオーバーヘッド動作をフォアグラウンドで自由に実行する。メモリシステムが、メモリへのデータ書き込みでビジーであったり、またはホストコマンドに応答して、メモリからのデータ読み出しでビジーであったりしても、解放動作、特にそのデータコピーを、データ書き込み、読み出し動作と交互に配置して行うことができる。このような交互配置法については、アラン・シンクレアによる２００５年１０月２５日出願の米国特許出願第１１／２５９，４２３号（特許文献３１）、アラン・ベネットらによる２００５年１２月１９日出願の米国特許出願第１１／３１２，９８５号（特許文献３２）に記載されている。

ステップ７０５において、解放動作を実行すると判定した場合、識別した解放ブロックが有効なデータを含んでいるかどうかにより処理は異なり、その場合、２つ以上のファイルの有効なデータを含んでいるかどうかにより処理が異なる。部分ブロックまたは使われなくなったブロックの場合、定義により、有効なデータを含んでいるし、かつ共有ブロックまたはフル共有ブロックの場合、２つ以上のファイルに有効なデータを含んでいる。解放ブロック内に有効なデータがあるかどうか、ステップ７０７において判定する。移動する必要のある有効なデータがある場合、１つのファイルのデータを識別して、次のステップ７０９において、そのデータを受け取る宛先ブロックとして識別する。前述した処理により、（この例では）有効なデータが属するファイルのデータすべてを、２つ以下のフラクタルブロックに記憶して保持するために、図１５〜図１７に関連して、宛先ブロックを識別する。ステップ７１１で示すように、１つのファイルの有効なデータをソース解放ブロックから宛先ブロックへコピーすることを開始する。これらのデータをコピーした後、処理はステップ７０７に戻って、別のファイルのデータが残っているかどうかを判定する。残っている場合、追加データに対しステップ７０９および７１１の処理を繰り返す。異なるファイルのデータ用に前に選択したものとは別に、宛先ブロックを選択する。ステップ７１３を実行する毎に、ソースブロックの消去を行う場合、ステップ７０７において、ソースブロックには移動するデータがないと判定するまで、これを繰り返す。次に、このブロックを消去ブロックプールに移動して、新しいデータの記憶に用いる。

ステップ７０７に戻り、無効なブロックの場合であるが、ソースブロックに有効なデータが含まれていない場合、移動する有効なデータはない。ソースブロックを消去する必要があるだけである。従って、その場合の処理は、図２２に示すように、ステップ７０９および７１１をバイパスする。

図２２の処理の第１の実施形態では、ステップ７０１において、部分ブロックと、使われなくなったブロックと、無効なブロックとのリストを１つ保持する。ブロック内の有効なデータ量は、リストの個別のエントリに含まれている。ステップ７０３において、リストから解放ブロックとして選択されたブロックは、有効なデータが一番少ない。リストに無効なブロックが１つある場合、有効なデータがないので、そのブロックをはじめに選択する。リストに無効なブロックが多くある場合、データが最も長いブロックを選択する。リストに無効なブロックがない場合、有効なデータ量が最も少ないブロックを解放ブロックとして選択する。リストの全ブロックから有効なデータ量が最も少ないブロックを選択することにより、あるブロックから別のブロックにコピーする有効なデータがもっと多くある場合に比べて、解放動作にかかる時間が短くなる。結果として、メモリに対するデータの書き込み、読み出し速度などの、他のメモリシステムの動作を速い速度で維持する。新規の消去ブロックを、メモリ性能に対し、より少ないコストで得られる。

１つのリストのフラクタルブロック内の有効なデータ量に基づいてソースブロックを選択する、図２２の処理の第１の実施形態の利点は、実行するのに相対的に簡単なことである。しかし、部分ブロックの値についても考慮ことにより、この処理をさらに改良することもできる。部分ブロックにはデータを書き込む消去した容量があるが、使われなくなったブロックも無効なブロックもどちらも、消去した容量を含んでいない。使われなくなったブロックを新しいデータの記憶に用いる前に、有効なデータをそれらブロックから別のブロックに移動する必要があるので、それらブロックを消去して、新しいデータを記憶するのに利用できるようにする。しかし、部分ブロックは、解放動作のオーバーヘッドを行う必要のない、データを書き込む消去した容量を有している。例えば、データを書き込む消去した容量も大量に含む場合、有効なデータ量が最も少ないという理由だけで、部分ブロックを解放することは有益ではない。

従って、図２２の処理の他の実施形態において、有効なデータ量と、部分ブロックに存在する消去した容量の量との両方に基づいて、ソースブロックを解放する候補として部分ブロックを選択する。部分ブロック内のデータの構成要素を、図２３に示す。ブロック（メタブロックでもよい）は、有効なデータを含んでいるある数の１つ以上のページ（メタページでもよい）と、消去したもので、データを書き込む１つ以上の他のページとを有している。一例として図２３に示すように、部分ブロックは、使われなくなったデータがある１つ以上の他のページも含んでいることもある。

図２２の処理のこれらの他の実施形態において、好ましくは、ステップ７０１において、部分ブロックを、使われなくなったブロックおよび無効なブロックのリストとは別のリストに保持する。消去した容量がほとんどなく、（これは、それらの今の状態であまり役に立たないことを意味する）移動する必要のある有効なデータの量が小さい場合には、部分ブロックを、解放動作のためのそれらのリストの先頭に移動する。このようなブロックは主として、使われなくなったデータを含んでいる。逆に、消去した容量が大量で（場合によってはデータの記憶に役立つことを意味する）、移動する有効なデータ量が大きい部分ブロックを、解放ブロックの候補として識別する可能性は最も低い。使われなくなったブロックを解放することで行われるように、消去した容量がある部分ブロックを解放することで、同じ量の記憶容量をメモリシステムに追加することはない。有益な消去した容量がなく、有効なデータをコピーする必要がないので、無効なブロックは明らかに、解放するのに最も魅力的なブロックである。

図２２の解放ブロック識別ステップ７０３の第２の実施形態では、ステップ７０１において、部分ブロックと、使われなくなったブロックと、無効なブロックとのそれぞれに１つずつ、３つの別々のリストを保持している。無効なブロックがある場合、そのリストからブロックがなくなるまで、解放ブロックを無効なブロックリストから選択する。一番長くリストにある無効なブロックをはじめに選択するように、先入れ先出し（ＦＩＦＯ）を除いて、無効なブロックをリストに記載する順番は特にない。次に、無効なブロックがない場合、そのリストの全ブロックのうち、有効なデータ量が最も少ないブロックを、使われなくなったブロックリストから選択する。

無効なリストまたは使われなくなったリストのいずれにもブロックがない場合、ステップ７０３において、部分ブロックリストのブロックを解放ブロックとして選択する。部分ブロックを、有効なデータ量が最も少ないものとして選択することもできるが、それらの消去した容量の有益性がわかるように、部分ブロックの順位付けを行うことが好ましい。この目的のために、各部分ブロックに対し、以下のように“解放利得”を算出することができる。
解放利得＝（Ｓ−ｋＥ）／Ｖ （１）

Ｓは、データを記憶してあるページの総数としてのブロックの大きさであり、Ｅは、データを書き込む消去した容量のページの数であり、Ｖは、別のブロックに移動する必要のある有効なデータを含んでいるページの数である。ブロックの消去した容量の考えられる影響の重み付けを行うために、定数ｋを含んでいるが、１で設定可能である。ｋＥの値が増えると、得られる解放利得が低下していく。Ｖの値が増えていくと、解放利得も低下していく。ステップ７０３において、解放利得の値が最も高い部分ブロックを、解放ブロックとして選択する。他の数学的表現を交互に用いて、有効なデータを含むシステム動作と、消去した容量があることの利点とに対する妨げとなるものとのバランスをとるＥおよびＶに関して、解放利得を定義することができる。その消去した容量にデータを書き込む毎に、ファイルディレクトリまたはＦＩＴが保持する情報の一部として記憶する毎にというように、ブロックに変更がある毎に、解放利得を算出してもよい。

この第２の実施形態について、図２５に示す。別々の部分ブロックリストと、使われなくなったブロックリストと、無効なブロックリストとから（図２２のステップ７０１において保持するように）、解放ブロックを選択する方法（図２２のステップ７０３）を示している。ステップ７２１において、はじめに無効なブロックリストにブロックがあるかどうかを判定する。このようなブロックが複数ある場合、ステップ７２３において、リストにのっている最も長いブロックを、解放ブロックとして選択する。無効なブロックリストにブロックがない場合、ステップ７２５において、使われなくなったブロックリストにエントリがあるかどうかを判定する。２つ以上のブロックが使われなくなったブロックリストにある場合であるが、あれば、ステップ７２７において、有効なデータ量が最も少ないブロックを、解放ブロックとして選択する。ステップ７２５において、使われなくなったブロックリストにエントリがないと判定した場合、ステップ７２９において、部分ブロックリストを調べる。部分ブロックリストに２つ以上のブロックがある場合、解放利得が最も高いものを解放ブロックとして選択する。前述した式（１）を利用するといったように、解放利得は、ブロック内の有効なデータ量および消去した容量を考慮に入れている。部分ブロックリストに何もない場合、ステップ７２１に戻り、リストのうちの１つにブロックが現れるまで、処理を繰り返す。解放ブロックを選択した後で、処理は、図２２のステップ７０５に進む。

第３の実施形態を、図２４のフローチャートに示す。図２２のステップ７０１で保持している無効なブロックリストでエントリを検索するステップ７４１によっても、図２２のステップ７０３の実行を開始する。無効なブロックリストに２つ以上のエントリがある場合、図２５のステップ７４３において、最も古いものを選択して解放ブロックとする。無効なブロックリストにエントリがない場合、次のステップ７４５において、使われなくなったブロックリストにエントリがあるかどうかを判定する。あれば、次のステップは、図２４の実施形態とは異なる。部分ブロックリストに少なくとも１つのエントリがある場合、使われなくなったブロックまたは部分ブロックのリストから解放ブロックを選択することが一番いいかどうかを判定する。

ステップ７４７において、使われなくなったブロックリストで、有効なデータ量が最も少ないブロックの識別を行う。次に、ステップ７４９において、部分ブロックリストに少なくとも１つのブロックがあるかどうかを判定する。あれば、ステップ７５１において、有効なデータ量が最も少ないブロックを識別する。次のステップ７５３において、使われなくなったブロックリストから識別した１つのブロックと、部分ブロックリストから識別した１つのブロックとの間で選択を行う。この目的のために、ステップ７５１において、部分ブロックリストから識別したブロックについて数量（Ｖ＋ｋＥ）を算出する。Ｖ、Ｅおよびｋは前述したのと同じである。この数量を、ステップ７４７において使われなくなったブロックリストから識別したブロック内の有効なデータ量Ｖと比較する。部分ブロックの数量（Ｖ＋ｋＥ）が、使われなくなったブロックの数量Ｖより大きい場合、ステップ７５５において、使われなくなったブロックを解放ブロックとして選択する。しかし、使われなくなったブロックの数量Ｖが、識別した部分ブロックの数量（Ｖ＋ｋＥ）より大きい場合、ステップ７５７において、部分ブロックを解放ブロックとして選択する。

識別した使われなくなったブロックの有効なデータＶだけと比較する前に、識別した部分ブロックの消去した容量の数量ｋＥをその有効なデータＶに加算することにより、使われなくなったブロックを選択するように、処理にバイアスをかける。その消去した容量にデータを記憶するために用いられる可能性がまだあるので、識別した使われなくなったブロックと同じ有効なデータ量を有する識別した部分ブロックを保持する。実際、数量ｋＥだけ使われなくなったブロックより小さい有効なデータ量を有する部分ブロックを保持することになる。

図２５のステップ７４５に戻り、使われなくなったブロックリストにエントリがない場合、ステップ７５９において、部分ブロックリストにブロックが記載されているかどうかを判定する。なければ、３つのリストのうちの１つにブロックが記載されるまで、処理はステップ７４１に戻り、繰り返される。複数の部分ブロックが記載されていれば、ステップ７６１において、有効なデータ量が最も少ないブロックを解放ブロックとして選択する。あるいは、第２の実施形態のステップ７３１（図２４）に関連して説明したように、解放利得を用いて部分ブロックを選択してもよい。

一方、第３の実施形態では、２つのリストしか用いないこともある。第１のリストは、使われなくなったデータと、消去を行わないメモリ容量とを含むブロックのエントリを含む、使われなくなったブロックリストである。図２５に示すように、個別の無効なブロックリストを用いるのではなく、無効なブロックと使われなくなったブロックの両方を、１つの“使われなくなった”ブロックリストに記載する。オプションとして、ブロックは有効なデータを含むこともある。リストの各エントリは、関連するブロック内の有効なデータ量を定義する値を含むフィールドを有している。リストのエントリは、これらのフィールドの値に基づいて、順序づけられている。従って、使われなくなったデータがあり、有効なデータのないブロック（無効なブロック）を、この第１のリストの先頭にともにグループ化する。

第３の実施形態の別の形態である第２のリストは、消去が行われたメモリ容量を含むブロックのエントリを含んでいる、部分ブロックリストである。オプションとして、ブロックは有効なデータを含んでいることもある。リストの各エントリは、関連するブロック内の有効なデータ量を定義する値を含んでいるフィールドを有している。リストのエントリは、これらのフィールドの値に基づいて、順序づけられている。図２５のステップ７５３における手法により、第１のリストまたは第２のリストのいずれかの先頭から、ブロックを選択してもよい（無効なデータ量が最も少ないブロック）。

図２６の表に、第３の実施形態のこの変形例による、解放動作のための部分ブロックリストと、使われなくなったブロックリストとに記載したブロックの種類の詳細について記載している。部分ブロックリストに記載されるために、ブロックは、有効なデータと消去した容量とを両方とも含んでいる。ブロック内に使われなくなったデータがあってもなくてもよい。使われなくなったブロックリストに記載されるために、ブロックは、使われなくなったデータと、有効なデータまたは消去した容量のいずれかとを含んでいる。

図２２、図２４および図２５に関連して前に説明した処理を、図２に示す一例のメモリシステムに格納したファームウェアを実行する、コントローラ１１のプロセッサ２７が実行してもよい。

まとめ
例示の実施形態に関連して本発明の様々な態様を説明してきたが、本発明が添付の特許請求の範囲の全範囲内においてその権利が保護されるべきであることが理解できよう。

現在実施されているものとしてホストと接続している不揮発性メモリシステムとを概略的に示す。 図１の不揮発性メモリとして用いられる一例のフラッシュメモリシステムのブロック図である。 図２のシステムで用いられるメモリセルアレイの典型的な回路図である。 図２のシステムの一例の物理メモリ構成を示す。 図４の物理メモリの部分拡大図である。 図４および図５の物理メモリの別の部分拡大図である。 ホストと再プログラム可能なメモリシステムとの間の一般的な従来技術の論理アドレスインターフェイスを示す。 ホストと再プログラム可能なメモリシステムとの間の、図７に示すものとはやり方が異なる一般的な従来技術の論理アドレスインターフェイスを示す。 本発明によるホストと再プログラム可能なメモリシステムとの間の直接ファイル記憶インターフェイスを示す。 本発明によるホストと再プログラム可能なメモリシステムとの間の、図９に示すものとはやり方が異なる直接ファイル記憶インターフェイスを示す。 直接データファイル記憶インターフェイスと協働するメモリシステムの機能ブロック図である。 直接データファイルメモリの動作周期を示す。 ファイルのデータを直接メモリに書き込む例を示す。 ファイルのデータを直接メモリに書き込む他の例を示す。 ファイルのデータを直接メモリに書き込む他の例を示す。 ファイルのデータを直接メモリに書き込む他の例を示す。 各種の組み合わせが可能な種類のブロックにデータファイルを記憶する例を示す。 各種の組み合わせが可能な種類のブロックにデータファイルを記憶する例を示す。 各種の組み合わせが可能な種類のブロックにデータファイルを記憶する例を示す。 各種の組み合わせが可能な種類のブロックにデータファイルを記憶する例を示す。 各種の組み合わせが可能な種類のブロックにデータファイルを記憶する例を示す。 個別のファイルのデータを記憶してあるブロックの種類により許可されているファイル状態のリストである。 図１５に示すリストのファイル状態の間での許可されている主な遷移を示す状態図である。 図１６の状態図に示す主なファイル状態遷移を説明する表である。 図１５に示すリストのファイル状態の間で得られる第２の遷移を示す状態図である。 図１８の状態図に示す第２のファイル状態遷移を説明する表である。 図１５〜図２０の条件下で、アクティブブロックとして割り当てられるブロックの種類をリストアップした一覧表である。 一例のブロック解放動作を示す。 一例のブロック解放動作を示す。 一例のブロック解放動作を示す。 一例のブロック解放動作を示す。 一般的な解放動作を示すフローチャートである。 典型的な部分メモリセルブロックに記憶するデータの種類を示す。 図２２のフローチャートのステップの１つを実行する具体的な実施形態の詳細を示す。 図２２のフローチャートの同じステップを実行する別の実施形態の詳細を示す。 さらに別の実施形態の２つのブロックリストに記載したブロックの種類を定義する表である。

Claims (10)

1. 制御回路とメモリ回路とを備える不揮発性メモリシステムの動作方法であって、前記メモリ回路が再プログラミングを行う前に消去が行われるメモリセルのブロックにグループ化された記憶セルを含み、前記ブロックがメモリセルに接続可能な消去回路、読み出し回路、書き込み回路およびプログラミング回路のユニットであり、前記制御回路が前記メモリシステムと通信するホストと前記メモリ回路との間のデータ転送を制御するとともに、前記メモリ回路上でホストデータを記憶することも制御する前記方法において、
   有効なデータ量と、使われなくなったデータまたは消去したデータ記憶容量のいずれか、あるいはその両方とを個別に含むブロックを含んでいる少なくとも１つのリストを有する制御データを前記制御回路によって保持するステップと、
   前記制御回路により、管理データを保持する保持ステップであって、前記管理データは少なくとも一つのリストを含み、前記リストは、複数のブロックの各々が個々にその有効なデータ量と、使われなくなったデータまたは消去されたデータ記憶容量のいずれか、あるいはその両方と含むデータを保持してきる保持ステップと、
   有効なデータの相対量と、前記少なくとも１つのリスト上のブロックの消去したデータ記憶容量の両方を考慮に入れることにより、前記少なくとも１つのリストからブロックを前記制御回路の論理によって選択するステップと、
   前記読み出し回路および書き込み回路を使用することにより選択したブロックからの有効なデータを別のブロックにコピーするステップと、
   その後、前記選択したブロックを前記消去回路を使用することにより消去し、それによって前記消去したブロックが前記制御回路に対して他のデータを記憶するのに利用可能になるステップと、
   を含む方法。
2. 請求項１記載の方法において、
   前記選択するステップが、前記少なくとも１つのリスト上の他のブロックに対する低い有効なデータ量を有する選択したブロックと、前記少なくとも１つのリスト上の他のブロックに対する高い消去した記憶容量の量を有する選択したブロックとのトレードオフの利点を含む方法。
3. 請求項１記載の方法において、
   前記少なくとも１つのリストが、有効なデータ量と、使われなくなったデータを個別に含んでいるが消去したデータ記憶容量を含まないブロックすべてを含んでいる第１のリストを含み、
   前記方法が、１つ以上のブロックが前記第１のリスト上にあるかどうかを判定し、１つ以上のブロックが前記第１のリスト上にあれば、前記ブロックの有効なデータ量に基づいて、前記第１のリストから第１のブロックの識別を行うステップをさらに含み、
   前記少なくともさらに１つのリストが、有効なデータ量と、消去したデータ記憶容量を個別に含んでいるブロックすべてを含んでいる第２のリストを含み、
   前記方法が、１つ以上のブロックが前記第２のリスト上にあるかどうかを判定し、１つ以上のブロックが前記第２のリスト上にあれば、有効なデータ量および前記ブロックの消去した記憶容量の両方に基づいて、前記第２のリストから第２のブロックの識別を行うステップと、
   前記選択するステップが、メモリシステムの動作の値に基づいて、前記ブロック解放のために前記第１のブロックまたは第２のブロックのいずれかを選択することを含み、
   前記選択したブロックからの有効なデータを別のブロックにコピーするステップと、
   他のデータを記憶するのに利用可能な消去ブロックとして、前記選択し消去したブロックを解放する方法。
4. 請求項１記載の方法において、
   前記少なくとも１つのリストが、有効なデータ量と、使われなくなったデータを個別に含んでいるが消去したデータ記憶容量を含まないブロックすべてを含んでいる第１のリストを含み、
   前記方法が、１つ以上のブロックが前記第１のリスト上にあるかどうかを判定し、１つ以上のブロックが前記第１のリスト上にあれば、前記第１のリストから前記ブロックの有効なデータ量が最も少ない第１のブロックの識別を行うステップをさらに含み、
   前記少なくともさらに１つのリストが、有効なデータ量と、消去したデータ記憶容量を個別に含んでいるブロックすべてを含んでいる第２のリストを含み、
   前記方法が、１つ以上のブロックが前記第２のリスト上にあるかどうかを判定し、１つ以上のブロックが前記第２のリスト上にあれば、前記第２のリストから前記ブロックの有効なデータ量が最も少ない第２のブロックの識別を行うステップをさらに含み、
   前記選択するステップが、前記第２のブロック内の有効なデータ量を前記第２のブロック内の消去したデータ記憶容量の量に対して調整を行った後で、それらに含まれている有効なデータ量に基づいて、前記第１のブロックまたは第２のブロックのいずれかを選択することを含み、
   前記選択したブロックからの有効なデータを別のブロックにコピーするステップと、
   前記選択し消去したブロックが、他のデータを記憶するのに利用可能な消去ブロックとなる方法。
5. 請求項１記載の方法において、
   解放動作が行われるブロックを選択するステップをさらに含み、前記解放動作が行われるブロックを選択するステップが前記少なくともいくつかのブロックの個別のブロック内にデータを記憶するために残っている消去した容量の量に基づいて、そのような選択を行うことをさらに含む方法。
6. 請求項５記載の方法において、
   前記解放動作が行われるブロックを選択するステップが、それぞれ使われなくなったデータを含んでいない、少なくともいくつかのブロックの内容に基づいて、そのような選択を行うことをさらに含む方法。
7. 再プログラム可能な不揮発性メモリシステムであって、
   データの書き換えを行う前に消去が行われることを特徴とする不揮発性メモリセルのブロックと、
   前記不揮発性メモリセルのブロックに機能的に接続しているコントローラであって、
   有効なデータ量と、使われなくなったデータまたは消去したデータ記憶容量のいずれか、あるいはその両方とを個別に含むブロックのデータを含んでいる少なくとも１つのリストを保持し、
   有効なデータの相対量と、前記少なくとも１つのリスト上のブロックの消去したデータ記憶容量の両方を考慮に入れることにより、前記少なくとも１つのリストからブロックを選択し、
   選択したブロックからの有効なデータを別のブロックにコピーし、かつ
   その後、前記選択したブロックを消去し、それによって前記消去したブロックが他のデータを記憶するのに利用可能になるように配置される
   コントローラと、
   を備えるメモリシステム。
8. 請求項７記載のメモリシステムにおいて、
   前記コントローラは、前記少なくとも複数のブロックの個別のブロックに記憶している最も少ない有効なデータ量に基づいて、解放すべきブロックを選択するようにさらに配置されるメモリシステム。
9. 請求項７記載のメモリシステムにおいて、
   前記コントローラは、データを記憶するための前記少なくとも複数のブロックの個別のブロックに残っている消去した容量の最も少ない量に基づいて、解放すべきブロックを選択するようにさらに配置されるメモリシステム。
10. 再プログラム可能な不揮発性メモリシステムであって、
    同時に消去可能なメモリセルのブロックに構成された不揮発性メモリセルアレイと、
    コントローラであって、
    有効なデータ量と、使われなくなったデータを個別に含んでいるが消去したデータ記憶容量を含まないブロックすべてのデータを含んでいる第１のリストを保持し、
    １つ以上のブロックが前記第１のリスト上にあるかどうかを判定し、１つ以上のブロックが前記第１のリスト上にあれば、前記第１のリストから前記ブロックの有効なデータ量が最も少ない第１のブロックの識別を行い、
    有効なデータ量と、消去したデータ記憶容量を個別に含んでいるブロックすべてのデータを含んでいる第２のリストを保持し、
    １つ以上のブロックが前記第２のリスト上にあるかどうかを判定し、１つ以上のブロックが前記第２のリスト上にあれば、前記第２のリストから前記ブロックの有効なデータ量が最も少ない第２のブロックの識別を行い、
    前記第２のブロック内の有効なデータ量を前記第２のブロック内の消去したデータ記憶容量の量に対して調整を行った後で、それらに含まれている有効なデータ量に基づいて、前記第１のブロックまたは第２のブロックのいずれかを選択し、
    前記選択したブロックからの前記有効なデータを別のブロックにコピーし、
    その後、前記選択したブロックを消去するように動作する前記アレイと動作可能に接続している
    コントローラと、
    を備えるメモリシステム。

Images