段階的ガーベッジコレクション
不揮発性メモリ記憶システムを動作させる方法が提供される。この方法では、データを書き込む書き込みコマンドが受け取られる。書き込みコマンドは、書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられる。タイムアウト期間内に、ガーベッジコレクション動作の一部分が実行される。書き込みコマンドに関連付けられたデータは、不揮発性メモリ記憶システムに関連付けられたバッファに書き込まれる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にはメモリ動作に関し、特に段階的ガーベッジコレクション動作を実行する方法およびシステムに関する。
【背景技術】
【０００２】
不揮発性メモリ記憶システムでは、メモリに格納されているデータのブロックは、メモリの記憶容量を再生利用するために定期的にガーベッジコレクション（すなわち、圧縮または整理統合）される。代表的なガーベッジコレクション動作では、ブロックからの有効なデータが他のブロックにコピーされる。有効なデータが転送された後、オリジナルブロックは記憶容量を提供するために消去される。現在、書き込み動作は、不揮発性メモリ記憶システムをトリガしてガーベッジコレクション動作を実行させることができる。ホストは、書き込み動作の実行のために一定量の時間を許し、（トリガされたならば）ガーベッジコレクションを含む。例えば、セキュアデジタルプロトコルは、その時間量を２５０ミリ秒に制限する。不揮発性メモリ記憶システムが書き込み動作においてこの一定量の時間を越えれば、タイムアウトエラーに帰着する可能性がある。
【０００３】
メモリブロックのサイズは、増大する容量、より高度の並列性、およびダイサイズのスケーリングに起因して大きくなってきている。従って、より多くのデータが転送されるので書き込み動作の実行により長い時間がかかるようになっている。従って、ガーベッジコレクション動作は、書き込み動作に割り当てられた一定量の時間を容易に超える可能性がある。その結果として、ガーベッジコレクション動作を実行するための時間の量がその一定量の時間を超えるときにタイムアウトエラーを防止する必要がある。
【発明の概要】
【０００４】
本発明の種々の実施形態は、段階的ガーベッジコレクションの方法および／またはシステムを提供する。実施形態が、方法、回路、システム、あるいは装置を含む多くの仕方で実現され得ることが理解されるべきである。本発明のいくつかの実施形態が以下に記載される。
【０００５】
本発明の１つの実施形態に従って、不揮発性メモリ記憶システムを動作させる方法が提供される。この方法では、データを書き込むために書き込みコマンドが受け取られる。書き込みコマンドには、書き込みコマンドの実行を完了させるためのタイムアウト期間が割り当てられる。このタイムアウト期間内に、ガーベッジコレクション動作の一部が実行される。書き込みコマンドに関連付けられたデータは、不揮発性メモリ記憶システムに関連付けられたバッファに書き込まれる。
【０００６】
本発明の他の実施形態および利点は、本発明の原理を例を挙げて示す添付図面と関連して考慮される以下の詳細な記述から明らかである。
【０００７】
本発明は、添付図面と関連する以下の詳細な記述によって容易に理解されるであろう。同様の参照数字は同様の構造要素を示す。
【図面の簡単な説明】
【０００８】
【図１】本発明の１つの実施形態に従う、不揮発性メモリ記憶システムの例の簡略ブロック図である。
【図２】メモリセルアレイのプレーンへの編成の簡略ブロック図である。
【図３】メモリセルのページの簡略ブロック図である。
【図４】メモリセルのセクタの簡略ブロック図である。
【図５】ホストと不揮発性メモリ記憶システムとの間の論理インターフェイスの簡略ブロック図である。
【図６】本発明の１つの実施形態に従う、段階的ガーベッジコレクションのための動作の概略のフローチャート図である。
【図７】本発明の１つの実施形態に従う、複数の部分に分割された１つのガーベッジコレクション動作の簡略ブロック図を示す。
【図８】本発明の１つの実施形態に従う、段階的ガーベッジコレクションを実行するための詳細な動作のフローチャート図である。
【図９Ａ】本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図９Ｂ】本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ａ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｂ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｃ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｄ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｅ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１１】本発明の１つの実施形態に従う、書き込みバッファブロックへのアクセスを最適化する動作のフローチャート図である。
【図１２】本発明の１つの実施形態に従う、新しいデータをスクラッチパッドブロックに一時的に格納するための動作のフローチャート図である。
【図１３】本発明の１つの実施形態に従う、シングルセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。
【図１４】本発明の１つの実施形態に従う、マルチセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。
【発明を実施するための形態】
【０００９】
添付図面と共に１つ以上の実施形態の詳細な記述が以下に提供される。この詳細な記述は、そのような実施形態と関連して提供されるけれども、特定の実施形態に限定されない。範囲は特許請求の範囲のみにより限定され、多くの変形例、改変、および同等物が含まれる。完全な理解を提供するために以下の記述において多くの特定の細部が明らかにされる。これらの細部は例示を目的として提供され、記述された実施形態はこれらの細部の一部または全部を用いずに特許請求の範囲に従って実現され得る。明瞭性を目的として、記述を不必要に分かりにくくしないように、実施形態に関連する技術分野で知られている技術的事項は詳しくは記述されていない。
【００１０】
ここに記載されている実施形態は、段階的ガーベッジコレクションの方法および／またはシステムを提供する。一般的に、ガーベッジ動作は複数の段階に分割され得る。ガーベッジコレクション動作の段階（あるいは部分）は、複数のタイムアウト期間にわたって実行され得る。１つの実施形態では、以下でより詳しく説明されるように、ガーベッジコレクション動作の一部分は１タイムアウト期間内に実行され、書き込みコマンドから受け取られるデータはバッファに格納され得る。
【００１１】
図１は、本発明の１つの実施形態に従う、不揮発性メモリ記憶システムの例の簡略ブロック図である。ホストシステム（例えば、デスクトップコンピュータ、オーディオプレーヤ、デジタルカメラ、および他の計算装置）は、不揮発性メモリ記憶システム１０２にデータを書き込み、またそこからデータを読み出すことができる。不揮発性メモリ記憶システム１０２は、ホストに組み込まれるか、あるいはホストに取り外し可能に接続され得る。図１に示されているように、不揮発性メモリ記憶システム１０２は、メモリ１１８と通信するメモリコントローラ１１０を含む。一般に、メモリコントローラ１１０はメモリ１１８の動作を制御する。動作の例は、データを書き込む（あるいはプログラムする）動作、データを読み出す動作、データを消去する動作、データをベリファイする動作、ガーベッジコレクション動作を処理する動作、および他の動作を含む。メモリコントローラ１１０はホストインターフェイス１０４を通してシステムバス１２６とインターフェイスするバス１２４を含み、メモリコントローラはメモリインターフェイス１０８を通してメモリ１１８とインターフェイスする。ホストインターフェイス１０４、プロセッサ１０６（例えば、マイクロプロセッサ、マイクロコントローラ、および他のプロセッサ）、メモリインターフェイス１０８、ランダムアクセスメモリ（ＲＡＭ）１１２、誤り訂正符号（ＥＣＣ）回路１１４、および読み出し専用メモリ（ＲＯＭ）１１６は、バス１２４を通して通信する。ＲＯＭ１１６は、メモリ１１８の動作を制御するためのプログラム命令を含む記憶システムファームウェアを記憶することができる。プロセッサ１０６は、ＲＯＭ１１６からロードされたプログラム命令を実行するように構成される。記憶システムファームウェアはＲＡＭ１１２に一時的にロードされ、そして付加的に、ＲＡＭはホストとメモリ１１８との間で転送されるデータをバッファリングするために使用され得る。ＥＣＣ回路１１４は、ホストとメモリ１１８との間でメモリコントローラ１１０を通るエラーがないかを調べる。エラーが発見されたならば、ＥＣＣ回路１１４は数個のエラービットを訂正することができ、その個数は使用されるＥＣＣアルゴリズムによる。
【００１２】
メモリ１１８は、アレイロジック１２０、不揮発性メモリセルアレイ１２２、およびメモリセルアレイ１２３を含むことができる。不揮発性メモリセルアレイ１２２は、いろいろな不揮発性メモリ構造および技術を含むことができる。不揮発性メモリ技術の例として、フラッシュメモリ（例えば、ＮＡＮＤ、ＮＯＲ、マルチレベルセル（ＭＬＣ）、分割ビット線ＮＯＲ（ＤＩＮＯＲ）、ＡＮＤ、大容量結合比（ＨｉＣＲ）、非対称無接点トランジスタ（ＡＣＴ）、他のフラッシュメモリ）、消去可能でプログラム可能な読み出し専用メモリ（ＥＰＲＯＭ）、電気的に消去可能でプログラム可能な読み出し専用メモリ（ＥＥＰＲＯＭ）、読み出し専用メモリ（ＲＯＭ）、一回だけプログラム可能なメモリ（ＯＴＰ）、および他のメモリ技術を含むことができる。
【００１３】
１つの実施形態では、メモリ１１８は、付加的に、バッファを記憶するように構成されるメモリセルアレイ１２３を含むことができる。バッファは、段階的ガーベッジコレクション動作においてデータを記憶するように構成される。以下でより詳しく説明されるように、段階的ガーベッジコレクション動作では、書き込みコマンドから受け取られた新しいデータがバッファに格納され得る。本発明の実施形態に従って、バッファはＲＡＭ１１２および／または不揮発性メモリセルアレイ１２２に置かれてもよいということが理解されるべきである。不揮発性メモリセルアレイ１２２と同様に、メモリセルアレイ１２３はいろいろなメモリ構造および技術を含むことができる。メモリセルアレイ１２３はバッファリング動作のために構成されるので、メモリセルアレイは不揮発性メモリアレイ１２２より高速で、より経済的で、かつより信頼できる異なるメモリ構造を組み入れることができる。
【００１４】
アレイロジック１２０は、メモリコントローラ１１０を不揮発性メモリセルアレイ１２２およびメモリセルアレイ１２３とインターフェイスさせ、そして、例えばアドレス指定、データ転送およびセンシング、および他のサポートを不揮発性メモリセルアレイおよびメモリセルアレイに提供することができる。不揮発性メモリセルアレイ１２２およびメモリセルアレイ１２３をサポートするために、アレイロジック１２０は行デコーダ、列デコーダ、電荷ポンプ、ワード線電圧発生器、ページバッファ、入出力バッファ、アドレスバッファ、および他の回路を含むことができる。
【００１５】
図２は、メモリセルアレイのプレーンへの編成の簡略ブロック図である。１つ以上のメモリセルアレイは、複数のプレーンまたはサブアレイに分割され得る。図２の例では、１つのメモリセルアレイが４つのプレーン２０２〜２０５に分割されている。１，２，８，１６，あるいはそれ以上など、他の数のプレーンが不揮発性メモリ記憶システムに存在し得ることが理解されるべきである。各プレーン２０２，２０３，２０４，または２０５は、それぞれのプレーン２０２〜２０５内に位置するブロック２１０〜２１３および２２０〜２２３のようなメモリセルのブロックに分割され得る。メモリセルのブロックは、物理的に一緒に消去可能な最小数のメモリセルである。並列性を高めるために、ブロックはより大きなメタブロック単位で操作され、その場合各プレーン２０２，２０３，２０４，または２０５からの１ブロックが互いに論理的にリンクされて１つのメタブロックを形成する。例えば、４つのブロック２１０〜２１３が互いに論理的にリンクされて１つのメタブロックを形成することができる。さらに、メタブロックを形成するために使用されるブロックは、プレーン２０２〜２０５のようなそれぞれのプレーン内のいろいろな位置からのブロックであり得る。例えば、それぞれのプレーン２０２〜２０５内のいろいろな位置からの４つのブロック２２０〜２２３は、論理的に互いにリンクされて他の１つのメタブロックを形成することができる。メタブロックは不揮発性メモリ記憶システム内の４つの論理プレーン２０２〜２０５の全てにわたって広がることができ、あるいは不揮発性メモリ記憶システムは１つ以上の異なるプレーン内の１つ以上のブロックから動的にメタブロックを形成することができる。
【００１６】
図３は、メモリセルのページの簡略ブロック図である。ブロック２１０〜２１３のような各々のブロックは、メモリセルのページにさらに分割されている。図３に示されているように、各ブロック２１０，２１１，２１２，あるいは２１３は８ページＰ０〜Ｐ７に分割されている。代わりに、各ブロック２１０，２１１，２１２，あるいは２１３の中にメモリセルの１６ページ、３２ページ、あるいはもっと多くのページがあり得る。不揮発性メモリ記憶システムの動作並列性を高めるために、２つ以上のブロックの中のページが論理的にリンクされてメタページにされてもよい。例えば、４つのブロック２１０〜２１３の各々からの、Ｐ１のような１つずつのページでメタページが形成され得る。メタページは不揮発性メモリ記憶システム内の全てのプレーンにわたって広がることができ、あるいは不揮発性メモリ記憶システムは１つ以上の異なるプレーン内の１つ以上の別々のブロック内の１つ以上のページからメタページを動的に形成することができる。
【００１７】
図４は、メモリセルのセクタの簡略ブロック図である。ページは１つ以上のセクタにさらに分割され得る。各ページ内のデータの量は、整数個の１つ以上のセクタのデータであることができ、各セクタは５１２バイトのデータを記憶することができる。図４は、２つのセクタ４０２および４０４に分割されたページ４０１を示す。各セクタ４０２または４０４は、５１２バイトのサイズであり得るデータ４０６と、データに関連付けられたオーバーヘッドデータ４０５とを含む。オーバーヘッドデータ４０５のサイズは１６バイトであることができ、例えば、プログラミング中にデータ４０６から計算されたＥＣＣと、データに関連付けられた論理アドレスと、ブロックが消去され再プログラムされた総回数と、制御フラグと、動作電圧レベルと、データに関連付けられた他の情報とを記憶することができる。
【００１８】
図５は、ホストと不揮発性メモリ記憶システムとの間の論理インターフェイスの簡略ブロック図である。連続的論理アドレス空間５１２はメモリに格納され得るデータのためにアドレスを提供する。ホストに見られる論理アドレス空間５１２は、データのクラスタのインクリメントに分割され得る。各クラスタは、例えば４セクタと６４セクタとの間の数個のセクタのデータを含むことができる。
【００１９】
図５に示されているように、ホスト上で実行されるアプリケーションプログラムは３つのデータファイル１，２，および３を作る。ファイル１，２，および３は、データの順序集合であることができて、一意の名前または他のリファレンスにより識別される。ホストは、他のファイルに既に配置されていない論理アドレス空間をファイル１に割り当てる。ここで、ファイル１は１つの連続的範囲の利用可能な論理アドレスを割り当てられているように示されている。
【００２０】
ホストがファイル１の後にファイル２を作るとき、ホストは論理アドレス空間５１２の中の２つの異なる範囲の連続的アドレスを同様に割り当てる。ホストは、ファイル１,２，または３のようなファイルに連続的な論理アドレスを割り当てることはできず、既に他のファイルに割り当てられている論理アドレス範囲の間の論理アドレスのフラグメントを割り当てることができる。図５の例は、前にファイル１および２および他のデータに割り当てられていなかった論理アドレス空間５１２の中の１つの不連続的なアドレス範囲が他の１つのファイル３に割り当てられることを示している。
【００２１】
ホストはファイル割り当てテーブル（ＦＡＴ）を維持することによって論理アドレス空間５１２を追跡することができ、ここで変換によりファイル１〜３のような種々のデータファイルにホストによって割り当てられた論理アドレスが維持される。ホストはファイル１〜３を、不揮発性メモリ記憶システムがファイルを格納した物理的位置によってではなくて、それらの論理アドレスにより、参照する。一方、不揮発性メモリ記憶システムは、データが書き込まれている論理アドレスの部分によってファイル１〜３を参照するのであって、ファイルに割り当てられた論理アドレスによってファイルを参照するのではない。不揮発性メモリ記憶システムは、ホストにより提供された論理アドレスを、ホストからのデータが格納されるメモリセルアレイ５０２内の一意の物理アドレスに変換する。ブロック５０４は、これらの論理アドレス−物理アドレス変換のテーブルを表し、これは不揮発性メモリ記憶システムにより維持される。
【００２２】
図６は、本発明の１つの実施形態に従う、段階的ガーベッジコレクションのための動作の概略のフローチャート図である。特定のホスト論理アドレスに格納されたデータはオリジナルの格納されているデータが陳腐化したときに新しいデータで上書きされ得るということが理解されるべきである。不揮発性メモリ記憶システムは、これに応じて、その新しいデータを更新ブロックに書き込み、そしてその新しいデータが格納された新しい物理的ブロックを特定するためにこれらの論理アドレスについて論理アドレス−物理アドレステーブルを変更する。これらの論理アドレスに存するオリジナルデータを含むブロックはその後消去され、付加的なデータの格納のために利用可能にされる。そのような消去は、書き込み動作の前に実行され得る。その結果として、メモリコントローラは、所与の論理アドレスに存するデータが新データが同じ論理アドレスに書き込まれた後にホストによって陳腐化あるいは無効にされたことを知る。従って、メモリの多数のブロックがある期間にわたって無効のデータを記憶しているということがあり得る。
【００２３】
ブロックおよびメタブロックのサイズは増大しつつあり、この増大は、個々のデータ書込みの大きな部分が、１つのメタブロックの記憶容量より少ない、また多くの場合に１つのブロックのものよりも少ない量のデータを格納するという結果をもたらす。不揮発性メモリ記憶システムは、新しいデータを消去済みプールメタブロックに向け得るので、そのような向け方はブロックまたはメタブロックの部分が満たされないという結果をもたらし得る。新データが他の１つのメタブロックに格納されているあるデータの更新であるならば、他の１つのメタブロックからのデータの、新データメタページのものに連続する論理アドレスを有する残りの有効なメタページも新しいメタブロックに論理アドレス順にコピーされる。旧メタブロックは、他の有効なデータメタページを保つことができる。従って、個々のメタブロックのあるメタページのデータが陳腐化あるいは無効化され、同じ論理アドレスが異なるメタブロックに書き込まれて新データに取って代わられ得る。
【００２４】
論理アドレス空間にデータを格納するための充分な物理メモリ空間を維持するために、そのようなデータは定期的にガーベッジコレクション（すなわち、圧縮または整理統合）され得る。一般に、ガーベッジコレクション動作は、ブロックから有効なデータを読み出してその有効なデータを新しいブロックに書き込むことを含み、その過程で無効なデータを無視する。例えば、図５のブロック図では、新データファイル３の作成は旧データファイル３を陳腐化する。旧データファイル３は、旧データファイル３により使用されていた物理容量を再生利用するために、消去され得る。しかし、そのような消去動作は、ファイル２と旧ファイル３とが同じ物理的ブロックに格納されていたならば、ガーベッジコレクション動作をトリガする。
【００２５】
図６に戻って、不揮発性メモリ記憶システムは、書き込みコマンドに割り当てられたタイムアウト期間の中でガーベッジコレクション動作を実行することができる。ガーベッジコレクション動作が１タイムアウト期間内に完了され得なければ、本発明の１つの実施形態に従って、その１つのガーベッジコレクション動作は数個の異なる段階（または部分）に分割され得る。ここで、不揮発性メモリ記憶システムは、複数の書き込みコマンドに割り当てられたタイムアウト期間を用いてガーベッジコレクション動作の部分を実行する。換言すれば、不揮発性メモリ記憶システムは、１つのガーベッジコレクション動作の部分を実行するために、複数の書き込みコマンドに割り当てられたタイムアウト期間を利用する。
【００２６】
図６に示されているように、新しいデータを書き込む書き込みコマンドが動作６０２で受け取られる。本願明細書で使用される“新しいデータ”という用語は、メモリに書き込まれるべき書き込みコマンドから不揮発性メモリ記憶システムにより受け取られるデータとして定義される。書き込みコマンドには、書き込みコマンドの実行を完了させるためのタイムアウト期間が割り当てられる。換言すれば、タイムアウト期間は、書き込みコマンドの実行のために割り当てられた期間である。割り当てられるタイムアウト期間の一例は２５０ミリ秒である。書き込みコマンドは、シングルセクタ書き込みコマンドまたはマルチセクタ書き込みコマンドであり得る。以下でより詳しく説明されるように、シングルセクタ書き込みコマンドでは、新しいデータは単一セクタとしてメモリ中のランダムなアドレスに書き込まれ得る。マルチセクタ書き込みコマンドでは、連続的な論理アドレスを有する新しいデータの複数のセクタがメモリに書き込まれる。
【００２７】
１つのガーベッジコレクション動作がタイムアウト期間内に完了され得なければ、動作６０４に示されているように、ガーベッジコレクション動作の一部分が書き込みコマンドに割り当てられたタイムアウト期間内に実行される。ガーベッジコレクションの残りの部分は、後のタイムアウト期間に完了させられ得る。例えば、図７は、本発明の１つの実施形態に従う、複数の部分７８０および７８１に分割された１つのガーベッジコレクション動作の例の簡略ブロック図を示す。図７に示されているように、不揮発性メモリ記憶システムは、マルチセクタ書き込みコマンド７０４を受け取り、その後に新しいデータの複数のセクタ７６０〜７６２がメモリに格納されるべく受け取られる。データの各セクタ７６０，７６１，または７６２が受け取られた後にビジー信号７０２がアサートされる。不揮発性メモリ記憶システムは書き込みコマンドの実行を許すためにビジー信号７０２をアサートするが、それは（必要ならば）ガーベッジコレクション動作と他の動作とを含むことができる。ホストは、ビジー信号７０２がアサートされているときには他のコマンドまたは追加のデータを不揮発性メモリ記憶システムに送らない。ホストは書き込みコマンドの実行のために限られた一定量の時間（すなわち、タイムアウト期間７５０〜７５２）を与えるので、不揮発性メモリ記憶システムはデータの各セクタ７６０，７６１，または７６２が受け取られた後に限られた量の時間にわたってビジー信号７０２をアサートすることができる。ビジー信号がタイムアウト期間７５０，７５１，または７５２より長くアクティブであり続ければ、ホストは書き込みコマンドを反復するかあるいはプロセスをアボートすることができる。従って、不揮発性メモリ記憶システムは、タイムアウト期間７５０，７５１，または７５２より長くビジー信号７０２をアサートすることはできない。データの複数のセクタ７６０〜７６２の書き込みの完了後のビジー信号７０２の解除は、ホストが不揮発性メモリ記憶システムとさらに通信することを可能にする。
【００２８】
図７をなお参照すると、ガーベッジコレクションの部分７８０および７８１は複数のタイムアウト期間７５０〜７５２の間に割り当てられ得る。換言すれば、不揮発性メモリ記憶システムは、１つのガーベッジコレクション動作の各部分７８０または７８１を実行するために各タイムアウト期間７５０，７５１，または７５２を利用することができる。例えば、１つのガーベッジコレクションの第１の部分７８０は第１のタイムアウト期間７５０の間に実行される。ここで、有効なデータの部分が第１のタイムアウト期間７５０中に１ブロックから他の１ブロックにコピーされ得る。第２のタイムアウト期間７５１において、第１のタイムアウト期間に開始された前のガーベッジコレクション動作が続けられる。不揮発性メモリ記憶システムは、前のガーベッジコレクションが完了するまで、タイムアウト期間７５１の間に前のガーベッジコレクション動作の第２の部分７８１を実行する。前のガーベッジコレクションは、有効なデータの残りの部分または最後の部分を１ブロックから他の１ブロックにコピーすることによって完了させられ得る。前のガーベッジコレクション動作が第２のタイムアウト期間７５１内に完了させられ得なければ、不揮発性メモリ記憶システムはガーベッジコレクション動作を完了させるために、第３のタイムアウト期間７５２のような後のタイムアウト期間を使用することができる。マルチセクタ書き込みコマンド７０４の終わりに、不揮発性メモリ記憶システムは、ストップコマンド７０６が受け取られた後に、データの全てのセクタ７６０〜７６２がメモリセルアレイに書き込まれるまでビジー信号をアサートすることができる。図７はマルチセクタ書き込みコマンドに関連する動作を示しているということに留意するべきである。以下でより詳しく説明されるように、実行されるガーベッジコレクション動作は、シングルセクタ書き込みコマンドとマルチセクタ書き込みコマンドとについては異なり得る。例えば、以下でより詳しく説明されるように、新しいデータを格納するために使用されるバッファのタイプは、受け取られた書き込みコマンドがシングルセクタ書き込みコマンドであるのか、それともマルチセクタ書き込みコマンドであるのかによる。
【００２９】
図６に戻って、ガーベッジコレクション動作の一部分がタイムアウト期間内に実行された後、動作６０６で、書き込み動作から受け取られた新しいデータは不揮発性メモリ記憶システムに関連付けられたバッファに格納され得る。１つの実施形態では、バッファは不揮発性メモリセルアレイ（例えば、図１に示されている不揮発性メモリアレイ１２２）に関連付けられたデータ構造であり得る。データ構造の例は、書き込みバッファブロックのような不揮発性メモリセルアレイのブロックを含み、これは以下でより詳しく記載される。他の１つの実施形態では、バッファは揮発性メモリセルアレイのブロックであり得る。例えば、新しいデータは、不揮発性メモリ記憶システムに関連付けられたＲＡＭ（例えば、図１に示されているＲＡＭ１１２）に置かれたブロックに格納され得る。さらに他の１つの実施形態では、前に論じられたように、新しいデータは別のメモリセルアレイ（例えば、図１に示されているメモリセルアレイ１２３）に置かれたブロックに格納され得る。
【００３０】
図８は、本発明の１つの実施形態に従う、段階的ガーベッジコレクションを実行するための詳細な動作のフローチャート図である。図８に示されているように、新しいデータをメモリに書き込むために書き込みコマンドが動作８０２で受け取られる。１つの実施形態では、書き込みコマンドはシングルセクタ書き込みコマンドである。ある環境では、以下でより詳しく説明されるように、他の１つの実施形態に従って、書き込みコマンドはマルチセクタ書き込みコマンドでもあり得る。書き込みコマンドが受け取られた後、不揮発性メモリ記憶システムは動作８０４でビジー信号をアサートする。
【００３１】
書き込みコマンドが実行される前に、動作８０６でガーベッジコレクション期間の間にガーベッジコレクション動作の一部分が実行される。例えば、１つの実施形態では、１つ以上のブロックがガーベッジコレクション動作のために選択される。その１つ以上のブロックは有効なデータおよび／または無効なデータを含み得る。有効なデータは、ガーベッジコレクション期間中に第２のブロックにコピーされる。ガーベッジコレクション動作に割り当てられたガーベッジコレクション期間と、コピーされるべき有効なデータの量とにより、有効なデータの全部または有効なデータの一部分が第２のブロックにコピーされる。ガーベッジコレクション動作のために割り当てられたガーベッジコレクション期間は、
ガーベッジコレクション期間＝タイムアウト期間−Ｔｐｒｏｇ
と表現することができ、ここでタイムアウト期間は、前に論じられたように、固定された、限られた期間である。Ｔｐｒｏｇは、新しいデータをメモリに（例えば、バッファに）書き込むことに関連付けられた最大プログラミング時間であるか、あるいは不揮発性メモリ記憶システムが新しいデータをメモリに書き込むために必要とする最大時間である。その結果として、１つの実施形態では、不揮発性メモリ記憶システムは、有効なデータを１つ以上のブロックから第２のブロックにコピーするための時間の量を追跡する。不揮発性メモリ記憶システムは、時間がガーベッジコレクション期間を超える前にコピーをやめる。
【００３２】
ガーベッジコレクション動作がガーベッジコレクション期間により完了させられ得なければ、書き込みコマンドに関連付けられた新しいデータは動作８１０で書き込みバッファブロックに書き込まれ得る。不揮発性メモリ記憶システムは、ガーベッジコレクション動作の前に、間に、または後に、新しいデータを書き込みバッファブロックに書き込むことができる。以下でより詳しく説明されるように、ガーベッジコレクション動作が完了すると直ぐに新しいデータは書き込みバッファブロックから更新ブロックにコピーされ得る。書き込みバッファブロックは不揮発性メモリ記憶システムによってメモリ内に維持される。一般に、書き込みバッファブロックは、不揮発性メモリ記憶システムにおいて新しいデータをバッファリングする。１つの実施形態では、書き込みバッファブロックは複数の論理アドレスにわたって広がる。他の１つの実施形態では、書き込みバッファブロックは１つの論理アドレス空間全体にわたって広がる。論理アドレス空間全体にわたって広がることで、書き込みバッファブロックは、不揮発性メモリ記憶システム全体にわたって全ての論理アドレスと論理アドレスの全てのグループ（すなわち、全ての論理グループ）に書き込まれようとしているデータを記憶することができる。換言すれば、複数の異なる論理グループと関連付けられた新しいデータが書き込みバッファブロックに格納され得る。論理グループは、メタブロックのサイズと同等であり得るサイズを有する論理アドレスのグループである。新しいデータは、順次にあるいは非順次に（すなわち、カオス的またはランダムな順序で）書き込みバッファブロックに書き込まれ得る。以下でより詳しく説明されるように、書き込みバッファブロックに書き込まれた新しいデータは後に他のブロック（例えば、更新ブロック）にコピーされるので、書き込みバッファブロックは一時的バッファとして役立つ。本願明細書で使用される“書き込みバッファブロッククリーニング”という用語は、書き込みバッファブロックに格納された新しいデータが他のブロックにコピーされることを意味する。
【００３３】
１つの実施形態では不揮発性メモリ記憶システムが書き込みバッファブロックを段階的ガーベッジコレクション動作のために使用するということに留意するべきである。従って、書き込みバッファブロックは最も更新された新しいデータを記憶していないかもしれない。その結果として、新しいデータが後の読み出し動作で読み出されるならば、不揮発性メモリ記憶システムは、更新ブロックに格納されている新しいデータと書き込みバッファブロックに格納されている新しいデータとのどちらが最も新たに更新されたものであるかを調べる。読み出し動作は、その後、最も新たに更新された新しいデータにアクセスして戻す。他の１つの実施形態では、不揮発性メモリ記憶システムは、非段階的ガーベッジコレクション動作および段階的ガーベッジコレクション動作の両方のために書き込みバッファブロックを使用することができる。ここでは、書き込みバッファブロックは全ての書き込み動作のために使用される。換言すれば、非段階的ガーベッジコレクションおよび段階的ガーベッジコレクション動作からの新しいデータが書き込みバッファブロックに書き込まれる。従って、書き込みバッファブロックは、書き込みキャッシュのように動作し、従って最も新たに更新された新しいデータを包含する。
【００３４】
書き込みバッファブロックに関連付けられたインデックス情報は、別のデータ構造に、あるいは書き込みバッファブロック自体の一部として、格納され得る。そのデータ構造はメモリコントローラのＲＡＭに格納され得る。データ構造に格納されたインデックス情報は、書き込みバッファブロックに格納されたデータのトラッキングおよびアクセスを可能にする。インデックス情報は、例えば、書き込みバッファブロック内の位置への論理アドレスのマップまたは書き込みバッファブロックの有効な索引へのポインタを含むことができる。索引情報は、更新ブロックが閉じられた後あるいは書き込みバッファブロックへの数個の更新の後に、更新され得る。以下でより詳しく説明されるように、１つの実施形態では、書き込みバッファブロックはセクタレベルの索引のために構成され得る。他の１つの実施形態では、書き込みバッファブロックはページ境界索引のために構成され得る。書き込みバッファブロックは、満杯時に圧縮されることもできる。例えば、書き込みバッファブロックに格納されている有効なデータは新しいブロックにコピーされ、それは新しい書き込みバッファブロックとして参照されるべきあり、陳腐なエントリを有する既存の書き込みバッファブロックは消去される。本願明細書で使用される“書き込みバッファ圧縮”という用語は、書き込みバッファブロックに格納されている有効なデータが圧縮されることを意味する。
【００３５】
図８をなお参照すると、新しいデータが書き込みバッファブロックに書き込まれ、かつガーベッジコレクション動作がガーベッジコレクション期間中に実行された後、不揮発性メモリ記憶システムは動作８１２でタイムアウト期間の前にビジー信号を解除する。従って、１つのガーベッジコレクション動作または１つのガーベッジコレクション動作の一部分を含む書き込みコマンドを実行するための合計時間はタイムアウト期間を越えない。タイムアウト期間内にガーベッジコレクション動作の一部分が実行されるのであれば、残りの部分は後のタイムアウト期間で完了させられる。ガーベッジコレクション動作が完了すると、ガーベッジコレクションされた１つ以上のブロックが消去されて付加的なデータの格納のために利用可能にされる。
【００３６】
図９Ａおよび９Ｂは、本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。図９Ａに示されているように、オリジナルのブロックＡ９８０と、関連する順次更新ブロックＡ９８２とがガーベッジコレクションのために選択される。一般に、書き込みコマンドから受け取られたデータは更新ブロックに書き込まれ得る。その中でデータが更新される各々の論理グループのために更新ブロックとして専用のメタブロックが割り当てられ得る。データの論理セクタは論理的に連続するセクタのセットを含む論理グループに格納されるということに留意するべきである。更新ブロックは、データを順次にあるいはカオス的順序で（すなわち、非順次に）受け入れるように管理され得る。順次更新ブロックＡ９８２のような順次更新ブロックは、全ての有効なセクタが現在同じメタブロックに置かれている論理グループにおいて１つ以上の物理ページを満たすデータを書き込むために書き込みコマンドがホストから受け取られたときに割り当てられるメタブロックであるということが理解されるべきである。順次更新ブロックに書き込まれるデータのセクタは、セクタがオリジナルブロックに書き込まれている対応する論理セクタに取って代わるように論理的にアドレス指定されて順次に書き込まれる。この論理グループの中の更新されるセクタは、順次更新ブロックが閉じられるかあるいはカオス的更新ブロックに変換されるまで、この順次更新ブロックに書き込まれ得る。順次更新ブロックは順次更新ブロックの最後の物理セクタ位置が書き込みされたときに閉じられたと見なされるということに留意するべきである。換言すれば、順次更新ブロックの閉鎖は、ホストにより書き込まれるかあるいはオリジナルブロックからコピーされる更新されるセクタデータによって順次更新ブロックが完全に満たされることに起因し得る。以下でより詳しく説明されるように、カオス的更新ブロックは、ホストにより書き込まれるデータのセクタが、更新される論理グループ内の前に書き込まれたデータのセクタに論理的に連続していないときに順次更新ブロックからの変換によって作られ得る。
【００３７】
オリジナルブロックＡ９８０は無効なデータと有効なデータとを含むことができ、図９Ａではそれぞれハッチパターンおよびドットパターンで表されている。オリジナルブロックＡ９８０からコピーされた有効なデータに加えて、順次更新ブロックＡ９８２はガーベッジコレクション動作の前に順次更新ブロックＡに書き込まれた既存のデータ９８１を付加的に含むということに留意するべきである。新しいデータ９８３を書き込む書き込みコマンドが受け取られたとき、書き込みコマンドは順次更新ブロックＡ９８２の閉鎖を誘発し得るが、それは１種のガーベッジコレクション動作である。なぜならば、それは新しいデータが開いている更新ブロックを持っていない論理グループと関連付けられるかあるいは新しいデータがガーベッジコレクション動作を引き起こすからである。不揮発性メモリ記憶システムはビジー信号をアサートし、その後、第１のガーベッジコレクション期間９７０に達するまで有効なデータをオリジナルブロックＡ９８０から順次更新ブロックＡ９８２にコピーする。コピー中、不揮発性メモリ記憶システムは時間を追跡し、不揮発性メモリ記憶システムは第１のガーベッジコレクション期間９７０を超える前にコピー動作をやめる。図９Ａに示されているように、オリジナルブロックＡ９８０に有効なデータがなお残っているので、ガーベッジコレクション動作はガーベッジコレクション期間９７０内に完了させられ得ない。その結果として、有効なデータの部分が順次更新ブロックＡ９８２にコピーされた後、新しいデータ９８３は、第１のタイムアウト期間に達する前に許された残っている時間内に書き込みバッファブロック９０８に書き込まれる。
【００３８】
図９Ｂは、ガーベッジコレクション動作の残りの部分が第２のタイムアウト期間内に完了させられ得ることを示す。ここで、新しいデータ９８４を書き込む第２の書き込みコマンドが第１の書き込みコマンドの後に受け取られる。その結果として、第２の書き込みコマンドに第２のタイムアウト期間が割り当てられる。第２のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＡ９８０から順次更新ブロックＡ９８２にコピーされる。この例では、残っている有効なデータの全体（または有効なデータの最後の部分）が第２のガーベッジコレクション期間９７２内に順次更新ブロックＡ９８２にコピーされ得る。従って、ガーベッジコレクション動作は第２のタイムアウト期間内に完了させられ得る。順次更新ブロックＡ９８２は満杯にされているので、順次更新ブロックＡは新しいオリジナルブロックＡ９８５または非更新ブロックに変換される。ガーベッジコレクション動作はこの第２のタイムアウト期間内に完了させられるので、オリジナルブロックＡ９８０は消去され、付加的なデータの格納に利用可能にされ得る。オリジナルブロックＡ９８０が消去された後、更新ブロックＣ９８６が割り当てられ、第２の書き込みコマンドから受け取られた新しいデータ９８４は新たに割り当てられた更新ブロックＣに書き込まれる。更新ブロックＣ９８６は新しいオリジナルブロックＡ９８５に関連付けられるかもしれないしあるいは関連付けられないかもしれないということに留意するべきである。
【００３９】
第２のタイムアウト期間内にガーベッジコレクションが完了した後、第２のタイムアウト期間内に利用可能な時間があれば、不揮発性メモリ記憶システムは書き込みバッファブロッククリーニング動作を行うことができる。書き込みバッファブロック９０８は、書き込みバッファブロックに書き込まれた新しいデータ９８３のような新しいデータが後に他のブロック（例えば、更新されたブロックＣ９８６）にコピーされるので、一時的バッファとして役立つ。図９Ｂの例では、第２のタイムアウト期間内に書き込みバッファブロッククリーニング動作のための時間がある。書き込みバッファブロック９０８に格納されている新しいデータ９８３は、新しいデータ９８４と同じ論理グループの中にある。従って、新しいデータ９８３は、ガーベッジコレクション動作の完了後に更新ブロックＣ９８６にコピーされる。書き込みバッファブロック９０８に格納されている新しいデータ９８３は無効としてマークされ、従って、書き込みバッファブロック内の付加的なスペースは付加的な新しいデータの格納のために利用可能にされ得る。書き込みバッファブロッククリーニング動作は全てのガーベッジコレクションの完了後に実行されるわけではないかもしれないということに留意するべきである。書き込みバッファブロッククリーニングのタイミングは以下でより詳しく説明される。
【００４０】
図１０Ａ〜１０Ｅは、本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。図１０Ａに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４がガーベッジコレクションのために選択される。一般に、カオス的更新ブロックＡ９０４のようなカオス的更新ブロックは、データのセクタが１つの論理グループ内でランダムな順序で、個々のセクタの任意の反復を伴って、更新されることを可能にする。カオス的更新ブロックは、ホストにより書き込まれるデータのセクタが、更新される論理グループ内の前に書き込まれたデータのセクタに論理的に連続していないときに順次更新ブロックからの変換によって作成され得る。この論理グループにおいてその後に更新される全てのデータのセクタは、グループ内でのそれらの論理セクタアドレスが何であっても、カオス的更新ブロック内の次の利用可能なセクタ位置に書き込まれる。
【００４１】
ここで、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４は、図１０Ａにおいてハッチパターンおよびドットパターンでそれぞれ表される無効なデータおよび有効なデータを含む。新しいデータ９０１を書き込む書き込みコマンドが受け取られたとき、不揮発性メモリ記憶システムはビジー信号をアサートし、その後、第１のガーベッジコレクション期間９５０に達するまで有効なデータをオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーする。コピー中、不揮発性メモリ記憶システムは時間を追跡し、不揮発性メモリ記憶システムは第１のガーベッジコレクション期間９５０を超える前にコピー動作をやめる。図１０Ａに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４に有効なデータがなお残っているので、ガーベッジコレクション動作は第１のガーベッジコレクション期間９５０内に完了させられ得ない。その結果として、有効なデータの部分が新しいブロックＡ９０６にコピーされた後、ガーベッジコレクション動作が始まる前に受け取られた新しいデータ９０１は第１のタイムアウト期間に達する前に書き込みバッファブロック９０８に書き込まれる。
【００４２】
図１０Ｂは、その次のタイムアウト期間におけるガーベッジコレクション動作の続きを示す。ここで、第１の書き込みコマンドの後に第２の書き込みコマンドが受け取られ、第２のタイムアウト期間が第２の書き込みコマンドに割り当てられる。第２のタイムアウト期間の間に、残りの有効なデータが、第２のガーベッジコレクション期間９５１に達するまでオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーされる。図１０Ｂに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４に有効なデータがなお残っているので、ガーベッジコレクション動作は第２のガーベッジコレクション期間９５１内に完了させられ得ない。従って、有効なデータの部分が新しいブロックＡ９０６にコピーされた後、ガーベッジコレクション動作が始まる前に受け取られた新しいデータ９０５は書き込みバッファブロック９０８に書き込まれる。
【００４３】
図１０Ｃは、ガーベッジコレクション動作の残りの部分が第３のタイムアウト期間内に完了させられ得ることを示す。第２の書き込みコマンド後に第３の書き込みコマンドが受け取られる。その結果として、第３のタイムアウト期間が第３の書き込みコマンドに割り当てられる。第３のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーされる。ここで、全ての残りの有効なデータ（あるいは有効なデータの最後の部分）が第３のガーベッジコレクション期間９５３内に新しいブロックＡ９０６にコピーされ得る。従って、ガーベッジコレクション動作は第３のタイムアウト期間内に完了させられ得る。ガーベッジコレクション動作がこの第３のタイムアウト期間に完了させられるので、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４は消去されて付加的なデータの格納のために利用可能にされ得る。オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４が消去された後、新しい更新ブロックＢ９６２が割り当てられ、第３の書き込みコマンドから受け取られた新しいデータ９０９は新たに割り当てられた更新ブロックＢに書き込まれる。新しいデータ９０９は書き込みバッファブロック９０８に書き込まれないが、それは、ガーベッジコレクション動作が完了して、その次のタイムアウト期間まで新しいデータをバッファリングする必要がないからである。この例では、書き込みバッファブロッククリーニング動作が実行され、その動作で、新しいデータ９０１，９０５，および９０９が同じ論理グループに属すると仮定して、書き込みバッファブロック９０８に格納されている新しいデータ９０１および９０５が更新ブロックＢ９６２にコピーされる。
【００４４】
図１０Ｄは、第４のタイムアウト期間中に行われる他の１つのガーベッジコレクション動作を示す。図１０Ｄに示されているように、オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２がガーベッジコレクションのために選択される。カオス的更新ブロックに変換されている更新ブロックＢ９６２は、第１、第２、および第３の書き込みコマンドに関連する新しいデータ９０１，９０５，および９０９を含む。第４の書き込みコマンドが受け取られたとき、不揮発性メモリ記憶システムはビジー信号をアサートし、その後に有効なデータをオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２から新しいブロックＢ９６４にコピーする。図１０Ｄに示されているように、有効なデータがオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２になお残っているので、ガーベッジコレクション動作は第４のガーベッジコレクション期間９５２内に完了させられ得ない。有効なデータの部分が新しいブロックＢ９６４にコピーされた後、第４の書き込みコマンドから受け取られた新しいデータ９０３は書き込みバッファブロック９０８に書き込まれる。
【００４５】
図１０Ｅは、図１０Ｄのガーベッジコレクション動作の残りの部分が第５のタイムアウト期間に完了させられ得ることを示す。第４の書き込みコマンド後に第５の書き込みコマンドが受け取られる。その結果として、第５のタイムアウト期間が第５の書き込みコマンドに割り当てられる。第５のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２から新しいブロックＢ９６４にコピーされる。ここで、全ての残りの有効なデータ（あるいは有効なデータの最後の部分）が第５のガーベッジコレクション期間９５３内に新しいブロックＢ９６４にコピーされ得る。従って、始めに第４のタイムアウト期間中に実行されたガーベッジコレクション動作は第５のタイムアウト期間内に完了させられ得る。ガーベッジコレクション動作がこの第５のタイムアウト期間に完了させられるので、オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２は消去されて、付加的なデータの格納のために利用可能にされる。オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２が消去された後、更新ブロックＣ９６５が割り当てられ、第５の書き込みコマンドから受け取られた新しいデータ９０７は新たに割り当てられた更新ブロックＣに書き込まれる。更新ブロックＣ９６５は新しいブロックＢ９６４に関連付けられるかもしれないしあるいは関連付けられないかもしれないということに留意するべきである。ここで、書き込みバッファブロッククリーニング動作が実行され、従って、新しいデータ９０３および新しいデータ９０７が同じ論理グループに属すると仮定して、書き込みバッファブロック９０８に格納されている新しいデータ９０３は更新ブロックＣ９６５にコピーされる。
【００４６】
図１１は、本発明の１つの実施形態に従う、書き込みバッファブロックへのアクセスを最適化する動作のフローチャート図である。書き込みバッファブロックの維持は、あるオーバーヘッドを導入する。オーバーヘッドを減少させるために、１つの実施形態では、書き込みバッファブロックへの書き込みが最小にされ得る。図１１に示されているように、動作１００２で書き込みコマンドが受け取られる。その後、不揮発性メモリ記憶システムは動作１００４で実行時間を推定する。実行時間は、書き込みコマンドを実行する期間である。書き込みコマンドの実行は、例えば、新しいデータをメモリにプログラムする（すなわち、書き込む）ことと、ガーベッジコレクション動作を実行することと、他の動作の実行とを含み得る。例えば、実行時間は、有効なデータを１つ以上のブロックから他の１つのブロックにコピーするための期間と新しいデータを書き込む期間とを含み得る。
【００４７】
不揮発性メモリ記憶システムは、実行時間を即時に推定する。不揮発性メモリ記憶システムは、種々のパラメータに基づいて実行時間を推定することができる。パラメータの例として、ガーベッジコレクションのタイプ（例えば、ブロック閉鎖、整理統合、圧縮、および他のタイプ）、ガーベッジコレクションされるべきブロック（例えば、更新ブロックおよび他のブロック）に格納されている有効なデータの量、不揮発性メモリ記憶システムに関連するプログラミング時間、ガーベッジコレクションされるブロックのサイズ（例えば、メタブロックのサイズ）、プレパディング(pre-padding) が必要か否か、プレパディングされるべきデータの量、パイプライニング、キャッシング、周波数設定、プログラム破損、および他のパラメータを含む。実行時間を推定する１つの例では、最初の１つ以上のブロックは１２ページの有効なデータを含み、その１２ページの有効なデータが１つの第２のブロックにコピーされる。不揮発性メモリ記憶システムは、１２ページの有効なデータを読み出すために不揮発性メモリ記憶システムが必要とする時間の量とその有効なデータを第２のブロックに書き込むために不揮発性メモリ記憶システムが必要とする時間の量とを加えることによって実行時間を推定することができる。
【００４８】
不揮発性メモリ記憶システムが実行時間を推定した後、その実行時間は動作１００６でタイムアウト期間と比較される。動作１００８に示されているように、その推定された実行時間がタイムアウト期間より短ければあるいは動作がタイムアウト期間内に完了させられ得るならば、ガーベッジコレクション動作が、引き起こされたならば、実行されてタイムアウト期間内に完了させられ、新しいデータが更新ブロックに書き込まれる。一方、動作１０１０に示されているように、推定された実行時間がタイムアウト期間を超える（すなわち、タイムアウト期間より大きいかあるいはタイムアウト期間に等しい）ならば、新しいデータは書き込みバッファブロックに書き込まれ、割り当てられたガーベッジコレクション期間は、書き込みバッファブロッククリーニングのためにあるいはガーベッジコレクション動作（引き起こされたならば）の一部分を実行するために使用され得る。１つの実施形態では、以下でより詳しく説明されるように、書き込みバッファブロッククリーニングは、タイムアウト期間内に残っている時間の間に、書き込みバッファブロック内の第１の有効なエントリから始まることができる。推定された実行時間がタイムアウト期間を超えるときに書き込みバッファブロックに書き込むことによって、書き込みバッファブロックへの書き込みはより少数となり、従って、書き込みバッファブロックを維持することに関連するオーバーヘッドは低減され得る。
【００４９】
書き込みバッファブロック−ページ境界索引付け
１つの実施形態では、書き込みバッファブロックは複数のページを含むように構成され、書き込みバッファブロック内の各ページは索引付けされる。書き込みバッファブロックの各ページは、１セクタ以上の新しいデータを記憶するように構成される。従って、１ポインタが１ページを指すかあるいは参照し、１ページ内の複数のセクタは１ポインタにより参照され得るが、それは、ポインタが１つのページを指すのであってページ内の複数のセクタを指すのではないからである。ここで、同じメタページに属する新しいデータのセクタは、書き込みバッファブロックの同じメタページに書き込まれる。しかし、別々のメタページに属する新しいデータのセクタは書き込みバッファブロックの別々のメタページに書き込まれる。例えば、第１の書き込みコマンドに関連付けられた新しいデータの第１のセクタは書き込みバッファブロックの第１のページに書き込まれる。その後、新しいデータの第２のセクタが第２の書き込みコマンドから受け取られる。その新しいデータの第２のセクタが新しいデータの第１、第２と同じメタページに属するならば、第２のセクタは書き込みバッファブロックの第１のページに書き込まれる。一方、新しいデータの第２のセクタが別のメタページに属するならば、第２のセクタは書き込みバッファブロックの別のメタページに書き込まれる。
【００５０】
書き込みバッファブロック−セクタレベル索引付け
他の１つの実施形態では、書き込みバッファブロックは複数のセクタを含むように構成され、書き込みバッファブロック内の１つ以上のセクタは索引付けされ得る。例えば、１ポインタが複数のセクタ（例えば、４セクタ）を指すかあるいは参照することができる。他の１つの例では、１ポインタが１セクタを指すかあるいは参照することができる。書き込みバッファブロック内の各セクタが索引付けされる例では、新しいデータは書き込みバッファブロックの単一のセクタに書き込まれる。他の１つの書き込みコマンドに関連付けられたその次の新しいデータは書き込みバッファブロック内の次の利用可能なセクタに書き込まれる。例えば、複数の書き込みコマンドからの新しいデータのセクタは、書き込みバッファブロック内の同じページの別々のセクタに書き込まれ得る。従って、書き込みバッファブロックは複数のセクタを含むように構成されることができ、各セクタは新しいデータの１つのセクタを記憶するように構成される。
【００５１】
タイムアウトエラーなしでシングルセクタ書き込みを持続させるために、不揮発性メモリ記憶システムは、割り当てられたセクタが不揮発性メモリ記憶システムのメタブロックの総数より多いように数個のセクタを書き込みバッファブロックに割り当てることができる。書き込みバッファブロックが複数のメタブロックで構成され得るということが理解されるべきである。書き込みバッファブロックに割り当てられるセクタの数を計算するために、例えば、書き込みバッファブロックを構成するメタブロックの数Ｍは、
M=M1+(M1*M2)/(Metablock_Size-M2) (1.0)
と定義することができ、“Metablock_Size"は“メタブロックサイズ”を意味し、ここで、
M1=RoundUp.to.Nearest.Integer[(N-1)*(Total.Number.of.Metablocks.in.System)/(Mtablock_Size)]
であり、ここで“RoundUp.to.Nearest.Integer"は“最近の整数への切り上げ”を意味し、“Total.Number.of.Metablocks.in.System"は“システム内のメタブロックの総数”を意味し、
M2=RoundUp.to.Nearest.Integer[(N*Tgc)/(N*TO-Tgc)]
であり、
N=RoundDown.to.Nearest.Integer[(Tgc+TO)/TO]
であり、ここで“RoundDown.to.Nearest.Integer"は“最近の整数への切り下げ”を意味し、TOはタイムアウト期間であり、Tgc は１つの完全なガーベッジコレクション動作を実行するための時間である。書き込みバッファブロックに割り当てられるセクタの総数は、
セクタの総数=M*Metablock_Size （１．２）
として定義されることができ、ここでＭは方程式１．０で定義され、“Metablock_Size"は、５１２セクタ／メタブロック、１，０２４セクタ／メタブロック、２，０４８セクタ／メタブロックあるいは他のサイズのようなセクタ数で表した各メタブロックのサイズである。一般に、方程式１．０および１．２は、書き込みバッファブロックに割り当てられるセクタの総数を不揮発性メモリ記憶システム内のメタブロックの総数より大きく定義する。メタブロックの総数に加えて、方程式１．０は、書き込みバッファブロックに関連するオーバーヘッドを維持するための１つ以上のメタブロック（またはセクタ）（以降、“オーバーヘッドメタブロック”または“オーバーヘッドセクタ”）を割り当てる。例えば、オーバーヘッドメタブロックの数を定める方程式１．０の部分は(M1*M2)/(Metablock_size-M2) であり、ここでオーバーヘッドセクタはオーバーヘッドブロックをメタブロックサイズと乗じることによって計算され得る。
【００５２】
方程式１．２で定められる数のセクタを書き込みバッファブロックに割り当てることにより、連続的でランダムなシングルセクタ書き込みという最悪の場合のシナリオにおいてもタイムアウトエラーが回避され得る。タイムアウトエラーは、書き込みバッファブロックが満杯でガーベッジコレクション動作が完了させられ得ないときに生じ得る。最悪の場合のシナリオは、各シングルセクタ書き込みコマンドが別々の論理グループに書き込み、これによりどの書き込みでも１つの完全なガーベッジコレクション動作を引き起こすときに、生じる。この悪い場合のシナリオでは、セクタが蓄積されて書き込みバッファブロックに書き込まれる。この悪い場合のシナリオは、全てのタイムアウト期間で新しいデータの単一のセクタが書き込みバッファブロックに書き込まれると共に不揮発性メモリ記憶システムが１つの完全なガーベッジコレクション動作を実行するために必要な全ての時間（Ｔｇｃ）で１セクタが無効とマークされるかのように見られ得る。さらに、書き込みバッファブロックが満たされるかあるいは満杯であるとき、書き込みバッファブロックは、新しいセクタが受け取られるけれども書き込みバッファブロッククリーニング動作が実行され得ないように、圧縮される。従って、１つの悪い場合のシナリオでは、ガーベッジコレクション期間がタイムアウト期間より大きいときには書き込みバッファブロックは空にされるより速く満たされる。
【００５３】
しかし、書き込みバッファブロック内の複数のセクタが同じ論理グループに属するならば、１ガーベッジコレクション動作中に全てのセクタが整理統合され得る。充分なメタブロックＭを書き込みバッファブロックに割り当てることにより、不揮発性メモリ記憶システム内のメタブロックの総数より多くのセクタ（またはエントリ）が書き込みバッファブロックに存在することになり、従って、複数の有効なセクタが書き込みバッファブロックに書き込まれている論理グループが存在することになる。書き込みバッファブロックの１つのセクタがガーベッジコレクションされるあるいは整理統合されるとき、同じ論理グループに属する全てのセクタが１つの新しい更新ブロックに整理統合され、書き込みバッファブロックにおいて無効とマークされる。従って、書き込みバッファブロックを空にする速度は充填速度より大きくなり、これにより書き込みバッファブロックが満杯であるかあるいは満たされることを防止する。従って、前述した最悪の場合のシナリオについてもタイムアウトエラーの発生が防止され得るように、所与の全てのＴｇｃについて、不揮発性メモリ記憶システムは不揮発性メモリ記憶システム内のメタブロックの総数より大きい数のセクタを書き込みバッファブロックに割り当てる。
【００５４】
図１２は、本発明の１つの実施形態に従う、新しいデータをスクラッチパッドブロックに一時的に格納するための動作のフローチャート図である。不揮発性メモリ記憶システムがマルチレベルバッファリングまたは複数のバッファレベルを持つことができ、それがマルチレベルキャッシングの思想と類似し得るということが理解されるべきである。この実施形態では、書き込みバッファブロックは、多数のバッファレベルのうちの１つに関連付けられ得る。複数バッファレベルでは、新しいデータを書き込みバッファブロックに直ぐに書き込む代わりに、新しいデータは、書き込みバッファブロックに書き込まれる前に一時的に他の１つのバッファレベルに格納され得る。書き込みバッファブロックのバッファレベルと異なるバッファレベルでの新しいデータの一時的格納は、段階的ガーベッジコレクション動作における書き込みバッファブロックの使用に関連する複雑さ、オーバーヘッド、および待ち時間を低減することができる。バッファの１つの例はスクラッチパッドブロックである。スクラッチパッドブロックは、書き込みバッファブロックとは異なるバッファレベルに関連付けられ得る。例えば、スクラッチパッドブロックは第１のバッファレベルとして使用され、書き込みバッファブロックは第２のバッファレベルとして使用され得る。前に論じられたように、シングルセクタ索引付けでは、複数の書き込みコマンドからの新しいデータのセクタは、書き込みバッファブロック内の同じページの別々のセクタに書き込まれ得る。不揮発性メモリ記憶システムは部分的なページをプログラムできないかもしれないので、本発明の１つの実施形態に従って、新しいデータは、書き込みバッファブロックに転送される前に、スクラッチパッドブロックのような第１のバッファレベルに一時的に格納され得る。スクラッチパッドブロックはデータ更新ブロックの１つの形であって、その中では関連する１つの論理グループ内の論理セクタがランダムな順序で任意の量の反復を伴って更新され得る。スクラッチパッドブロックは、意図された論理セクタが終了したりあるいは物理ページ境界を越えたりしない書き込みコマンドにより作られる。スクラッチパッドブロックは部分的物理ページに相当するデータを包含することができるけれども部分的プログラム済みページデータは許されない。スクラッチパッドブロックは、不揮発性メモリ記憶システム内の各更新ブロックのために１つの有効なページのデータを保持することができる。不揮発性メモリ記憶システムは、例えば、８個の更新ブロックを割り当てられることができ、従って、スクラッチパッドブロックは９個の有効なページのデータを記憶することができる。
【００５５】
図１２に示されているように、書き込みコマンドから受け取られた新しいデータは始めに動作１１０２でスクラッチパッドブロックに書き込まれる。スクラッチパッドブロックは複数のページを含むことができ、各ページは複数のセクタを含む。新しいデータはスクラッチパッドブロックのセクタにコピーされる。動作１１０４で、新しいデータは、その後、書き込みバッファブロックに関連付けられているスクラッチパッドブロック内の１つのページが満杯であるとき、スクラッチパッドブロックから書き込みバッファブロックにコピーされる。従って、不揮発性メモリ記憶システムは、スクラッチパッドブロック内のページのセクタを、ページの全てのセクタが種々の書き込みコマンドからの新しいデータで満たされるまで、蓄積する。不揮発性メモリ記憶システムは、その後、そのページ全体(例えば、８セクタの新しいデータ)をスクラッチパッドブロックから書き込みバッファブロックに１プログラム動作でコピーする。書き込みバッファブロックはスクラッチパッドブロックより大きくてより多くの有効なデータを収容し得るので、スクラッチパッドブロックはより少量のガーベッジコレクションされるべきデータを有する。従って、スクラッチパッドブロックのガーベッジコレクションは書き込みバッファブロックのガーベッジコレクションより高速である。その結果として、新しいデータをスクラッチパッドブロックを経由して書き込みバッファブロックに書き込む動作は、新しいデータを書き込みバッファブロックに直接書き込む動作より速い。
【００５６】
オーディオ／ビデオデータ
不揮発性メモリ記憶システムに格納されているオーディオ／ビデオファイル（以降、“オーディオ／ビデオデータ”）に関連付けられたデータにアクセスするホストは、他のデータと比べて所定の速度でオーディオ／ビデオデータを書き込む必要があるかもしれない。ホストがオーディオ／ビデオデータを不揮発性メモリ記憶システムにおよび／または不揮発性メモリ記憶システムからストリーミングするとき、ストリームに割り当てられる帯域幅は、所定の速度と一致するかあるいはそれを超える。オーディオ／ビデオデータのアクセス中に行われるガーベッジコレクション動作は、オーディオ／ビデオデータの書き込み性能を低下させることがある。従って、１つの実施形態では、マルチセクタ書き込みコマンドがオーディオ／ビデオデータに関連付けられていないかあるいはマルチセクタ書き込みコマンドがオーディオ／ビデオ書き込みの始まりにあるときには段階的ガーベッジコレクションが行われる。
【００５７】
オーディオ／ビデオデータを他のデータから区別するために、１つの実施形態では、不揮発性メモリ記憶システムは、マルチセクタ書き込みコマンドに関連付けられたターゲット論理アドレスを参照することができる。オーディオ／ビデオデータは順次に書き込まれるので、逆方向ジャンプ(backwards jump)として解釈されるターゲット論理アドレスは、新しいデータがオーディオ／ビデオデータ（あるいはオーディオ／ビデオデータの始まり）ではないことを示すことができる。他の１つの実施形態では、不揮発性メモリ記憶システムは、新しいデータに関連付けられたセクタの数を参照することによってもオーディオ／ビデオデータを他のデータから区別することができる。オーディオ／ビデオデータは、記録単位(recording unit)と称される単位で格納され得る。オーディオ／ビデオデータに関連付けられる最小の記録単位の長さは３２セクタであり得る。従って、３２セクタの整数倍ではない新しいデータに関連付けられたセクタの数は、その新しいデータがオーディオ／ビデオデータではないことを示すことができる。記録単位に整列しないか、あるいは記録単位の始まりから始まらない受け取られた新しいデータも、その新しいデータがオーディオ／ビデオデータではないことを示すことができる。
【００５８】
その結果として、次の条件、すなわち（１）マルチセクタ書き込みコマンドがガーベッジコレクション動作を引き起こす、（２）ターゲット論理アドレスが逆方向ジャンプとして解釈される、（３）ターゲット論理アドレスが記録単位境界と整列させられていない、（４）新しいデータに関連付けられたセクタの数が３２の整数倍でなければ、ストップコマンドが受け取られた（すなわち、マルチセクタ書き込みコマンドの終わり）後、という条件のうちの１つが当てはまるならば、段階的ガーベッジコレクションが実行され得る。
【００５９】
シングルセクタ書き込み
図１３は、本発明の１つの実施形態に従う、シングルセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。新しいデータは、メモリセルアレイ全体の中でランダムなアドレスにシングルセクタとして書き込まれ得る。ホストアクティビティとカードフラグメンテーションとにより、ホストは複数のセクタを有する長いファイルをシングルセクタ書き込みコマンドを用いてランダムな位置に書き込むことができる。限られた数の割り当てられた更新ブロックがあるので、これらのシングルセクタ書き込みは、更新ブロックを速やかに用いることができ、これにより、その後の書き込み動作のためにブロックをクリアするガーベッジコレクション動作を実行するように不揮発性メモリ記憶システムを促すことができる。
【００６０】
図１３に示されているように、シングルセクタ書き込みコマンドが動作１２０２で受け取られる。その後、そのシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすか否かについて動作１２０４で判定が行われる。そのシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こさなければ、新しいデータは動作１２２０でメモリに書き込まれる。しかし、シングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすならば、ペンディングしている段階的ガーベッジコレクション(すなわち、既に始まっているけれども、ガーベッジコレクションが完了させられ得ないために段階的に実行されたガーベッジコレクション動作)があるか否かについて他の１つの判定が動作１２０６で行われる。段階的ガーベッジコレクションがあるならば、動作１２０８でその段階的ガーベッジコレクション動作が続行される。換言すれば、前のガーベッジコレクション動作からの残りの部分が続行される。動作１２１０に示されているように、ガーベッジコレクション期間（例えば、タイムアウト期間とプログラミング時間との差）まであるいは段階的ガーベッジコレクションが完了させられるまで、段階的ガーベッジコレクション動作が実行される。
【００６１】
段階的ガーベッジコレクション動作がガーベッジコレクション期間内に完了させられ得なければ、新しいデータは動作１２１８で書き込みバッファブロックに書き込まれる。ガーベッジコレクション期間に達していないかあるいは段階的ガーベッジコレクション動作がガーベッジコレクション期間の前に完了させられ得たならば、段階的ガーベッジコレクション動作を完了させた後であっても、シングルセクタ書き込みコマンドがなおガーベッジコレクション動作を引き起こすか否かについての他の１つの判定が動作１２１２で行われる。シングルセクタ書き込みコマンドがガーベッジコレクションを引き起こさなければ、新しいデータが動作１２２０でメモリに書き込まれる。一方、シングルセクタ書き込みコマンドがガーベッジコレクションを引き起こすならば、動作１２１６に示されているガーベッジコレクション期間まで動作１２１４でガーベッジコレクション動作が実行される。ガーベッジコレクション動作がガーベッジコレクション期間までに完了させられ得なければ、新しいデータは動作１２１８で書き込みバッファブロックに書き込まれる。そうでなければ、新しいデータは動作１２２０でメモリに書き込まれる。段階的ガーベッジコレクションがあってかつ現在の書き込みコマンドもガーベッジコレクション動作を引き起こすならば、動作１２１６に示されているガーベッジコレクション期間は動作１２１０に示されているガーベッジコレクション期間の続きであるということに留意するべきである。従って、段階的ガーベッジコレクションがあってかつ現在のシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすならば、両方の動作が総ガーベッジコレクション期間内に完了させられる。換言すれば、動作１２０８に示されている段階的ガーベッジコレクション動作と動作１２１４に示されているガーベッジコレクション動作との両方のために割り当てられる実行時間は、例えば、タイムアウト期間とプログラミング時間との差である。
【００６２】
新しいデータが動作１２２０でメモリに書き込まれた後、書き込みバッファブロックに有効なエントリがあるか否かについて、またタイムアウト期間に達しているか否かについて、動作１２２４で判定が行われる。書き込みバッファブロックに有効なエントリがないかあるいはタイムアウト期間に達しているならば、動作は終了する。一方、有効なエントリがあってかつタイムアウト期間に達していなければ、書き込みバッファブロッククリーニング動作が動作１２２６でタイムアウト期間まで実行される。書き込みバッファブロック圧縮動作も、この期間中にタイムアウト期間まで実行され得る。
【００６３】
マルチセクタ書き込み
図１４は、本発明の１つの実施形態に従う、マルチセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。メモリセルアレイに書き込まれる大抵の新しいデータは、連続した順次論理アドレス空間を占める大きなデータファイルである。ホストアクティビティにより、ホストは大きなデータファイルをマルチセクタ書き込みコマンドを用いて書き込むことができる。そのような新しいデータは、複数のタイムアウト期間を有する新しいデータの複数のセクタを含む。図７は、マルチセクタ書き込みコマンドの例を示す。一般に、複数のタイムアウト期間が利用可能なので、新しいデータは、書き込みバッファブロックの代わりに、割り当てられた更新ブロックに書き込まれ得る。従って、ガーベッジコレクションは、普通は、マルチセクタ書き込みコマンドに割り当てられた複数のタイムアウト期間内に完了させられ得るので、書き込みバッファブロックは普通は複数の書き込みコマンドで使用されない。
【００６４】
図１４に示されているように、マルチセクタ書き込みコマンドが動作１３０２で受け取られる。その後、動作１３０４で、新しいデータのセクタは格納され（あるいはバッファリングされ）、必要ならばガーベッジコレクション動作が実行され得る。ここで、複数のタイムアウト期間がマルチセクタ書き込みコマンドに割り当てられ、１ガーベッジコレクション動作は普通はマルチセクタ書き込みコマンドの終わりまでに完了させられ得るので、不揮発性メモリ記憶システムは書き込みバッファブロックを利用しないかもしれない。従って、書き込みバッファブロックの代わりに、不揮発性メモリ記憶システムは、新しいデータを不揮発性メモリ記憶システムに関連付けられているＲＡＭに、あるいは不揮発性メモリ記憶システムに関連付けられている他のメモリに格納することができるのと同時に、割り当てられたタイムアウト期間を用いてガーベッジコレクション動作を実行するために新しいデータのセクタとセクタとの間にビジー信号をアサートする。
【００６５】
ホストセクタがバッファリングされた後、新しいデータのＮ個未満のセクタが受け取られたのか否かについて動作１３０６で判定が行われる。前に論じられたように、ガーベッジコレクション動作は、普通は、マルチセクタ書き込み動作に割り当てられた複数のタイムアウト期間内に完了させられ得るので、マルチセクタ書き込みコマンドに関連付けられた新しいデータは書き込みバッファブロックに書き込まれないかもしれない。しかし、１つの実施形態では、ガーベッジコレクション動作を完了させるために充分なタイムアウト期間が割り当てられなければ、書き込みバッファブロックがマルチセクタ書き込みコマンドで使用され得る。従って、ガーベッジコレクション動作が引き起こされるか否かに関わらず、
N=round-down to nearest integer [(Tgc+TO)/TO] （２．０）
として定義された新しいデータの少なくともＮ個のセクタを伴うマルチセクタ書き込みコマンドが書き込みバッファブロックにではなくて更新ブロックに直接書き込まれ得る。ここで“round-down to nearest integer" は、“最近の整数への切り捨て”を意味する。方程式２．０は、書き込みコマンドがシングルセクタ書き込みコマンドであるときあるいは不揮発性メモリ記憶システムがマルチセクタ書き込みコマンドで新しいデータのＮ個未満のセクタを受け取ったときに、新しいデータが書き込みバッファブロックに書き込まれることを示す。
【００６６】
なお図１４を参照すると、Ｎ個未満のセクタが受け取られたならば、不揮発性メモリ記憶システムは、図１３に示されているシングルセクタ書き込みコマンド動作に従ってマルチセクタ書き込みコマンドを操作する。しかし、新しいデータのＮ個より多くのセクタが受け取られたならば、書き込みバッファブロッククリーニング動作が実行され得るか否かについて動作１３１０で判定が行われる。例えば、動作１３０２で受け取られた新しいデータがガーベッジコレクションを引き起こさなかったならば、あるいは新しいデータが割り当てられたガーベッジコレクション期間の前に完了させられたガーベッジコレクションを引き起こしたのであれば、書き込みバッファブロッククリーニング動作が実行され得る。しかし、新しいデータが記録単位境界に整列させられているならば、新しいデータはオーディオ／ビデオデータであるかもしれないので、書き込みバッファブロックリーニングは実行されない。書き込みバッファブロッククリーニング動作が実行され得なければ、新しいデータは動作１３１４でメモリに書き込まれる。書き込みバッファブロッククリーニング動作が実行され得るならば、マルチセクタ書き込みコマンド実行中に不揮発性メモリ記憶システムによりアサートされた合計のビジー期間がＴｇｃ−Ｔｐｒｏｇになるまで、動作１３１２で段階的ガーベッジコレクション動作および書き込みバッファブロッククリーニング動作が実行される。その後、新しいデータは動作１３１４で不揮発性メモリセルアレイに書き込まれる。この実施形態では、動作１３１２に示されている書き込みバッファブロッククリーニングは、Ｔｇｃ−Ｔｐｒｏｇの期間まで、４タイムアウト期間、５タイムアウト期間、および他の期間などのいろいろな期間の間にマルチセクタ書き込みコマンドから受け取られた始めの数個のセクタの中間（例えば、第２のセクタと第３のセクタとの間）に、実行され得る。
【００６７】
書き込みコマンドが実行された後、新しいデータが３２セクタの整数倍であるか否かについて動作１３１６で判定が行われる。新しいデータが３２セクタの整数倍であれば、新しいデータはオーディオ／ビデオ関連であるかも知れず、動作は終了する。一方、新しいデータが３２セクタの整数倍でなければ、動作１３１８で、書き込みバッファブロック内に有効なエントリがあるか否かについて、またタイムアウト期間に達しているか否かについて、判定が行われる。有効なエントリが書き込みバッファブロック内にないかあるいはタイムアウト期間に達していれば、動作は終了する。一方、有効なエントリがあってかつタイムアウト期間に達していなければ、動作１３２０でタイムアウト期間まで書き込みバッファブロッククリーニング動作が実行される。
【００６８】
前述した実施形態は、段階的ガーベッジコレクションのための方法および／またはシステムを提供する。ガーベッジコレクション動作は複数の段階に分割されることができ、その複数の段階は複数のタイムアウト期間にわたって実行される。ガーベッジコレクション動作を分割することにより、ガーベッジコレクション動作の各段階はタイムアウト期間内に完了させられることができ、これによりタイムアウトエラーを防止する。
【００６９】
前述した実施形態は明確な理解を目的としてある程度詳細に記載されているけれども、実施形態は提示された細目に限定されない。実施形態を実現する多くの代わりの方法がある。従って、開示された実施形態は実例となるものであって制限するものではないと見なされるべきであり、実施形態は本願明細書で与えられた細目に限定されるべきではなくて、添付されている特許請求の範囲の範囲および同等物の中で改変され得る。特許請求の範囲で明示的に述べられていない限り、特許請求の範囲において要素および／または動作は動作の特定の順序を示唆しない。
【技術分野】
【０００１】
本発明は、一般的にはメモリ動作に関し、特に段階的ガーベッジコレクション動作を実行する方法およびシステムに関する。
【背景技術】
【０００２】
不揮発性メモリ記憶システムでは、メモリに格納されているデータのブロックは、メモリの記憶容量を再生利用するために定期的にガーベッジコレクション（すなわち、圧縮または整理統合）される。代表的なガーベッジコレクション動作では、ブロックからの有効なデータが他のブロックにコピーされる。有効なデータが転送された後、オリジナルブロックは記憶容量を提供するために消去される。現在、書き込み動作は、不揮発性メモリ記憶システムをトリガしてガーベッジコレクション動作を実行させることができる。ホストは、書き込み動作の実行のために一定量の時間を許し、（トリガされたならば）ガーベッジコレクションを含む。例えば、セキュアデジタルプロトコルは、その時間量を２５０ミリ秒に制限する。不揮発性メモリ記憶システムが書き込み動作においてこの一定量の時間を越えれば、タイムアウトエラーに帰着する可能性がある。
【０００３】
メモリブロックのサイズは、増大する容量、より高度の並列性、およびダイサイズのスケーリングに起因して大きくなってきている。従って、より多くのデータが転送されるので書き込み動作の実行により長い時間がかかるようになっている。従って、ガーベッジコレクション動作は、書き込み動作に割り当てられた一定量の時間を容易に超える可能性がある。その結果として、ガーベッジコレクション動作を実行するための時間の量がその一定量の時間を超えるときにタイムアウトエラーを防止する必要がある。
【発明の概要】
【０００４】
本発明の種々の実施形態は、段階的ガーベッジコレクションの方法および／またはシステムを提供する。実施形態が、方法、回路、システム、あるいは装置を含む多くの仕方で実現され得ることが理解されるべきである。本発明のいくつかの実施形態が以下に記載される。
【０００５】
本発明の１つの実施形態に従って、不揮発性メモリ記憶システムを動作させる方法が提供される。この方法では、データを書き込むために書き込みコマンドが受け取られる。書き込みコマンドには、書き込みコマンドの実行を完了させるためのタイムアウト期間が割り当てられる。このタイムアウト期間内に、ガーベッジコレクション動作の一部が実行される。書き込みコマンドに関連付けられたデータは、不揮発性メモリ記憶システムに関連付けられたバッファに書き込まれる。
【０００６】
本発明の他の実施形態および利点は、本発明の原理を例を挙げて示す添付図面と関連して考慮される以下の詳細な記述から明らかである。
【０００７】
本発明は、添付図面と関連する以下の詳細な記述によって容易に理解されるであろう。同様の参照数字は同様の構造要素を示す。
【図面の簡単な説明】
【０００８】
【図１】本発明の１つの実施形態に従う、不揮発性メモリ記憶システムの例の簡略ブロック図である。
【図２】メモリセルアレイのプレーンへの編成の簡略ブロック図である。
【図３】メモリセルのページの簡略ブロック図である。
【図４】メモリセルのセクタの簡略ブロック図である。
【図５】ホストと不揮発性メモリ記憶システムとの間の論理インターフェイスの簡略ブロック図である。
【図６】本発明の１つの実施形態に従う、段階的ガーベッジコレクションのための動作の概略のフローチャート図である。
【図７】本発明の１つの実施形態に従う、複数の部分に分割された１つのガーベッジコレクション動作の簡略ブロック図を示す。
【図８】本発明の１つの実施形態に従う、段階的ガーベッジコレクションを実行するための詳細な動作のフローチャート図である。
【図９Ａ】本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図９Ｂ】本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ａ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｂ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｃ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｄ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１０Ｅ】本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。
【図１１】本発明の１つの実施形態に従う、書き込みバッファブロックへのアクセスを最適化する動作のフローチャート図である。
【図１２】本発明の１つの実施形態に従う、新しいデータをスクラッチパッドブロックに一時的に格納するための動作のフローチャート図である。
【図１３】本発明の１つの実施形態に従う、シングルセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。
【図１４】本発明の１つの実施形態に従う、マルチセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。
【発明を実施するための形態】
【０００９】
添付図面と共に１つ以上の実施形態の詳細な記述が以下に提供される。この詳細な記述は、そのような実施形態と関連して提供されるけれども、特定の実施形態に限定されない。範囲は特許請求の範囲のみにより限定され、多くの変形例、改変、および同等物が含まれる。完全な理解を提供するために以下の記述において多くの特定の細部が明らかにされる。これらの細部は例示を目的として提供され、記述された実施形態はこれらの細部の一部または全部を用いずに特許請求の範囲に従って実現され得る。明瞭性を目的として、記述を不必要に分かりにくくしないように、実施形態に関連する技術分野で知られている技術的事項は詳しくは記述されていない。
【００１０】
ここに記載されている実施形態は、段階的ガーベッジコレクションの方法および／またはシステムを提供する。一般的に、ガーベッジ動作は複数の段階に分割され得る。ガーベッジコレクション動作の段階（あるいは部分）は、複数のタイムアウト期間にわたって実行され得る。１つの実施形態では、以下でより詳しく説明されるように、ガーベッジコレクション動作の一部分は１タイムアウト期間内に実行され、書き込みコマンドから受け取られるデータはバッファに格納され得る。
【００１１】
図１は、本発明の１つの実施形態に従う、不揮発性メモリ記憶システムの例の簡略ブロック図である。ホストシステム（例えば、デスクトップコンピュータ、オーディオプレーヤ、デジタルカメラ、および他の計算装置）は、不揮発性メモリ記憶システム１０２にデータを書き込み、またそこからデータを読み出すことができる。不揮発性メモリ記憶システム１０２は、ホストに組み込まれるか、あるいはホストに取り外し可能に接続され得る。図１に示されているように、不揮発性メモリ記憶システム１０２は、メモリ１１８と通信するメモリコントローラ１１０を含む。一般に、メモリコントローラ１１０はメモリ１１８の動作を制御する。動作の例は、データを書き込む（あるいはプログラムする）動作、データを読み出す動作、データを消去する動作、データをベリファイする動作、ガーベッジコレクション動作を処理する動作、および他の動作を含む。メモリコントローラ１１０はホストインターフェイス１０４を通してシステムバス１２６とインターフェイスするバス１２４を含み、メモリコントローラはメモリインターフェイス１０８を通してメモリ１１８とインターフェイスする。ホストインターフェイス１０４、プロセッサ１０６（例えば、マイクロプロセッサ、マイクロコントローラ、および他のプロセッサ）、メモリインターフェイス１０８、ランダムアクセスメモリ（ＲＡＭ）１１２、誤り訂正符号（ＥＣＣ）回路１１４、および読み出し専用メモリ（ＲＯＭ）１１６は、バス１２４を通して通信する。ＲＯＭ１１６は、メモリ１１８の動作を制御するためのプログラム命令を含む記憶システムファームウェアを記憶することができる。プロセッサ１０６は、ＲＯＭ１１６からロードされたプログラム命令を実行するように構成される。記憶システムファームウェアはＲＡＭ１１２に一時的にロードされ、そして付加的に、ＲＡＭはホストとメモリ１１８との間で転送されるデータをバッファリングするために使用され得る。ＥＣＣ回路１１４は、ホストとメモリ１１８との間でメモリコントローラ１１０を通るエラーがないかを調べる。エラーが発見されたならば、ＥＣＣ回路１１４は数個のエラービットを訂正することができ、その個数は使用されるＥＣＣアルゴリズムによる。
【００１２】
メモリ１１８は、アレイロジック１２０、不揮発性メモリセルアレイ１２２、およびメモリセルアレイ１２３を含むことができる。不揮発性メモリセルアレイ１２２は、いろいろな不揮発性メモリ構造および技術を含むことができる。不揮発性メモリ技術の例として、フラッシュメモリ（例えば、ＮＡＮＤ、ＮＯＲ、マルチレベルセル（ＭＬＣ）、分割ビット線ＮＯＲ（ＤＩＮＯＲ）、ＡＮＤ、大容量結合比（ＨｉＣＲ）、非対称無接点トランジスタ（ＡＣＴ）、他のフラッシュメモリ）、消去可能でプログラム可能な読み出し専用メモリ（ＥＰＲＯＭ）、電気的に消去可能でプログラム可能な読み出し専用メモリ（ＥＥＰＲＯＭ）、読み出し専用メモリ（ＲＯＭ）、一回だけプログラム可能なメモリ（ＯＴＰ）、および他のメモリ技術を含むことができる。
【００１３】
１つの実施形態では、メモリ１１８は、付加的に、バッファを記憶するように構成されるメモリセルアレイ１２３を含むことができる。バッファは、段階的ガーベッジコレクション動作においてデータを記憶するように構成される。以下でより詳しく説明されるように、段階的ガーベッジコレクション動作では、書き込みコマンドから受け取られた新しいデータがバッファに格納され得る。本発明の実施形態に従って、バッファはＲＡＭ１１２および／または不揮発性メモリセルアレイ１２２に置かれてもよいということが理解されるべきである。不揮発性メモリセルアレイ１２２と同様に、メモリセルアレイ１２３はいろいろなメモリ構造および技術を含むことができる。メモリセルアレイ１２３はバッファリング動作のために構成されるので、メモリセルアレイは不揮発性メモリアレイ１２２より高速で、より経済的で、かつより信頼できる異なるメモリ構造を組み入れることができる。
【００１４】
アレイロジック１２０は、メモリコントローラ１１０を不揮発性メモリセルアレイ１２２およびメモリセルアレイ１２３とインターフェイスさせ、そして、例えばアドレス指定、データ転送およびセンシング、および他のサポートを不揮発性メモリセルアレイおよびメモリセルアレイに提供することができる。不揮発性メモリセルアレイ１２２およびメモリセルアレイ１２３をサポートするために、アレイロジック１２０は行デコーダ、列デコーダ、電荷ポンプ、ワード線電圧発生器、ページバッファ、入出力バッファ、アドレスバッファ、および他の回路を含むことができる。
【００１５】
図２は、メモリセルアレイのプレーンへの編成の簡略ブロック図である。１つ以上のメモリセルアレイは、複数のプレーンまたはサブアレイに分割され得る。図２の例では、１つのメモリセルアレイが４つのプレーン２０２〜２０５に分割されている。１，２，８，１６，あるいはそれ以上など、他の数のプレーンが不揮発性メモリ記憶システムに存在し得ることが理解されるべきである。各プレーン２０２，２０３，２０４，または２０５は、それぞれのプレーン２０２〜２０５内に位置するブロック２１０〜２１３および２２０〜２２３のようなメモリセルのブロックに分割され得る。メモリセルのブロックは、物理的に一緒に消去可能な最小数のメモリセルである。並列性を高めるために、ブロックはより大きなメタブロック単位で操作され、その場合各プレーン２０２，２０３，２０４，または２０５からの１ブロックが互いに論理的にリンクされて１つのメタブロックを形成する。例えば、４つのブロック２１０〜２１３が互いに論理的にリンクされて１つのメタブロックを形成することができる。さらに、メタブロックを形成するために使用されるブロックは、プレーン２０２〜２０５のようなそれぞれのプレーン内のいろいろな位置からのブロックであり得る。例えば、それぞれのプレーン２０２〜２０５内のいろいろな位置からの４つのブロック２２０〜２２３は、論理的に互いにリンクされて他の１つのメタブロックを形成することができる。メタブロックは不揮発性メモリ記憶システム内の４つの論理プレーン２０２〜２０５の全てにわたって広がることができ、あるいは不揮発性メモリ記憶システムは１つ以上の異なるプレーン内の１つ以上のブロックから動的にメタブロックを形成することができる。
【００１６】
図３は、メモリセルのページの簡略ブロック図である。ブロック２１０〜２１３のような各々のブロックは、メモリセルのページにさらに分割されている。図３に示されているように、各ブロック２１０，２１１，２１２，あるいは２１３は８ページＰ０〜Ｐ７に分割されている。代わりに、各ブロック２１０，２１１，２１２，あるいは２１３の中にメモリセルの１６ページ、３２ページ、あるいはもっと多くのページがあり得る。不揮発性メモリ記憶システムの動作並列性を高めるために、２つ以上のブロックの中のページが論理的にリンクされてメタページにされてもよい。例えば、４つのブロック２１０〜２１３の各々からの、Ｐ１のような１つずつのページでメタページが形成され得る。メタページは不揮発性メモリ記憶システム内の全てのプレーンにわたって広がることができ、あるいは不揮発性メモリ記憶システムは１つ以上の異なるプレーン内の１つ以上の別々のブロック内の１つ以上のページからメタページを動的に形成することができる。
【００１７】
図４は、メモリセルのセクタの簡略ブロック図である。ページは１つ以上のセクタにさらに分割され得る。各ページ内のデータの量は、整数個の１つ以上のセクタのデータであることができ、各セクタは５１２バイトのデータを記憶することができる。図４は、２つのセクタ４０２および４０４に分割されたページ４０１を示す。各セクタ４０２または４０４は、５１２バイトのサイズであり得るデータ４０６と、データに関連付けられたオーバーヘッドデータ４０５とを含む。オーバーヘッドデータ４０５のサイズは１６バイトであることができ、例えば、プログラミング中にデータ４０６から計算されたＥＣＣと、データに関連付けられた論理アドレスと、ブロックが消去され再プログラムされた総回数と、制御フラグと、動作電圧レベルと、データに関連付けられた他の情報とを記憶することができる。
【００１８】
図５は、ホストと不揮発性メモリ記憶システムとの間の論理インターフェイスの簡略ブロック図である。連続的論理アドレス空間５１２はメモリに格納され得るデータのためにアドレスを提供する。ホストに見られる論理アドレス空間５１２は、データのクラスタのインクリメントに分割され得る。各クラスタは、例えば４セクタと６４セクタとの間の数個のセクタのデータを含むことができる。
【００１９】
図５に示されているように、ホスト上で実行されるアプリケーションプログラムは３つのデータファイル１，２，および３を作る。ファイル１，２，および３は、データの順序集合であることができて、一意の名前または他のリファレンスにより識別される。ホストは、他のファイルに既に配置されていない論理アドレス空間をファイル１に割り当てる。ここで、ファイル１は１つの連続的範囲の利用可能な論理アドレスを割り当てられているように示されている。
【００２０】
ホストがファイル１の後にファイル２を作るとき、ホストは論理アドレス空間５１２の中の２つの異なる範囲の連続的アドレスを同様に割り当てる。ホストは、ファイル１,２，または３のようなファイルに連続的な論理アドレスを割り当てることはできず、既に他のファイルに割り当てられている論理アドレス範囲の間の論理アドレスのフラグメントを割り当てることができる。図５の例は、前にファイル１および２および他のデータに割り当てられていなかった論理アドレス空間５１２の中の１つの不連続的なアドレス範囲が他の１つのファイル３に割り当てられることを示している。
【００２１】
ホストはファイル割り当てテーブル（ＦＡＴ）を維持することによって論理アドレス空間５１２を追跡することができ、ここで変換によりファイル１〜３のような種々のデータファイルにホストによって割り当てられた論理アドレスが維持される。ホストはファイル１〜３を、不揮発性メモリ記憶システムがファイルを格納した物理的位置によってではなくて、それらの論理アドレスにより、参照する。一方、不揮発性メモリ記憶システムは、データが書き込まれている論理アドレスの部分によってファイル１〜３を参照するのであって、ファイルに割り当てられた論理アドレスによってファイルを参照するのではない。不揮発性メモリ記憶システムは、ホストにより提供された論理アドレスを、ホストからのデータが格納されるメモリセルアレイ５０２内の一意の物理アドレスに変換する。ブロック５０４は、これらの論理アドレス−物理アドレス変換のテーブルを表し、これは不揮発性メモリ記憶システムにより維持される。
【００２２】
図６は、本発明の１つの実施形態に従う、段階的ガーベッジコレクションのための動作の概略のフローチャート図である。特定のホスト論理アドレスに格納されたデータはオリジナルの格納されているデータが陳腐化したときに新しいデータで上書きされ得るということが理解されるべきである。不揮発性メモリ記憶システムは、これに応じて、その新しいデータを更新ブロックに書き込み、そしてその新しいデータが格納された新しい物理的ブロックを特定するためにこれらの論理アドレスについて論理アドレス−物理アドレステーブルを変更する。これらの論理アドレスに存するオリジナルデータを含むブロックはその後消去され、付加的なデータの格納のために利用可能にされる。そのような消去は、書き込み動作の前に実行され得る。その結果として、メモリコントローラは、所与の論理アドレスに存するデータが新データが同じ論理アドレスに書き込まれた後にホストによって陳腐化あるいは無効にされたことを知る。従って、メモリの多数のブロックがある期間にわたって無効のデータを記憶しているということがあり得る。
【００２３】
ブロックおよびメタブロックのサイズは増大しつつあり、この増大は、個々のデータ書込みの大きな部分が、１つのメタブロックの記憶容量より少ない、また多くの場合に１つのブロックのものよりも少ない量のデータを格納するという結果をもたらす。不揮発性メモリ記憶システムは、新しいデータを消去済みプールメタブロックに向け得るので、そのような向け方はブロックまたはメタブロックの部分が満たされないという結果をもたらし得る。新データが他の１つのメタブロックに格納されているあるデータの更新であるならば、他の１つのメタブロックからのデータの、新データメタページのものに連続する論理アドレスを有する残りの有効なメタページも新しいメタブロックに論理アドレス順にコピーされる。旧メタブロックは、他の有効なデータメタページを保つことができる。従って、個々のメタブロックのあるメタページのデータが陳腐化あるいは無効化され、同じ論理アドレスが異なるメタブロックに書き込まれて新データに取って代わられ得る。
【００２４】
論理アドレス空間にデータを格納するための充分な物理メモリ空間を維持するために、そのようなデータは定期的にガーベッジコレクション（すなわち、圧縮または整理統合）され得る。一般に、ガーベッジコレクション動作は、ブロックから有効なデータを読み出してその有効なデータを新しいブロックに書き込むことを含み、その過程で無効なデータを無視する。例えば、図５のブロック図では、新データファイル３の作成は旧データファイル３を陳腐化する。旧データファイル３は、旧データファイル３により使用されていた物理容量を再生利用するために、消去され得る。しかし、そのような消去動作は、ファイル２と旧ファイル３とが同じ物理的ブロックに格納されていたならば、ガーベッジコレクション動作をトリガする。
【００２５】
図６に戻って、不揮発性メモリ記憶システムは、書き込みコマンドに割り当てられたタイムアウト期間の中でガーベッジコレクション動作を実行することができる。ガーベッジコレクション動作が１タイムアウト期間内に完了され得なければ、本発明の１つの実施形態に従って、その１つのガーベッジコレクション動作は数個の異なる段階（または部分）に分割され得る。ここで、不揮発性メモリ記憶システムは、複数の書き込みコマンドに割り当てられたタイムアウト期間を用いてガーベッジコレクション動作の部分を実行する。換言すれば、不揮発性メモリ記憶システムは、１つのガーベッジコレクション動作の部分を実行するために、複数の書き込みコマンドに割り当てられたタイムアウト期間を利用する。
【００２６】
図６に示されているように、新しいデータを書き込む書き込みコマンドが動作６０２で受け取られる。本願明細書で使用される“新しいデータ”という用語は、メモリに書き込まれるべき書き込みコマンドから不揮発性メモリ記憶システムにより受け取られるデータとして定義される。書き込みコマンドには、書き込みコマンドの実行を完了させるためのタイムアウト期間が割り当てられる。換言すれば、タイムアウト期間は、書き込みコマンドの実行のために割り当てられた期間である。割り当てられるタイムアウト期間の一例は２５０ミリ秒である。書き込みコマンドは、シングルセクタ書き込みコマンドまたはマルチセクタ書き込みコマンドであり得る。以下でより詳しく説明されるように、シングルセクタ書き込みコマンドでは、新しいデータは単一セクタとしてメモリ中のランダムなアドレスに書き込まれ得る。マルチセクタ書き込みコマンドでは、連続的な論理アドレスを有する新しいデータの複数のセクタがメモリに書き込まれる。
【００２７】
１つのガーベッジコレクション動作がタイムアウト期間内に完了され得なければ、動作６０４に示されているように、ガーベッジコレクション動作の一部分が書き込みコマンドに割り当てられたタイムアウト期間内に実行される。ガーベッジコレクションの残りの部分は、後のタイムアウト期間に完了させられ得る。例えば、図７は、本発明の１つの実施形態に従う、複数の部分７８０および７８１に分割された１つのガーベッジコレクション動作の例の簡略ブロック図を示す。図７に示されているように、不揮発性メモリ記憶システムは、マルチセクタ書き込みコマンド７０４を受け取り、その後に新しいデータの複数のセクタ７６０〜７６２がメモリに格納されるべく受け取られる。データの各セクタ７６０，７６１，または７６２が受け取られた後にビジー信号７０２がアサートされる。不揮発性メモリ記憶システムは書き込みコマンドの実行を許すためにビジー信号７０２をアサートするが、それは（必要ならば）ガーベッジコレクション動作と他の動作とを含むことができる。ホストは、ビジー信号７０２がアサートされているときには他のコマンドまたは追加のデータを不揮発性メモリ記憶システムに送らない。ホストは書き込みコマンドの実行のために限られた一定量の時間（すなわち、タイムアウト期間７５０〜７５２）を与えるので、不揮発性メモリ記憶システムはデータの各セクタ７６０，７６１，または７６２が受け取られた後に限られた量の時間にわたってビジー信号７０２をアサートすることができる。ビジー信号がタイムアウト期間７５０，７５１，または７５２より長くアクティブであり続ければ、ホストは書き込みコマンドを反復するかあるいはプロセスをアボートすることができる。従って、不揮発性メモリ記憶システムは、タイムアウト期間７５０，７５１，または７５２より長くビジー信号７０２をアサートすることはできない。データの複数のセクタ７６０〜７６２の書き込みの完了後のビジー信号７０２の解除は、ホストが不揮発性メモリ記憶システムとさらに通信することを可能にする。
【００２８】
図７をなお参照すると、ガーベッジコレクションの部分７８０および７８１は複数のタイムアウト期間７５０〜７５２の間に割り当てられ得る。換言すれば、不揮発性メモリ記憶システムは、１つのガーベッジコレクション動作の各部分７８０または７８１を実行するために各タイムアウト期間７５０，７５１，または７５２を利用することができる。例えば、１つのガーベッジコレクションの第１の部分７８０は第１のタイムアウト期間７５０の間に実行される。ここで、有効なデータの部分が第１のタイムアウト期間７５０中に１ブロックから他の１ブロックにコピーされ得る。第２のタイムアウト期間７５１において、第１のタイムアウト期間に開始された前のガーベッジコレクション動作が続けられる。不揮発性メモリ記憶システムは、前のガーベッジコレクションが完了するまで、タイムアウト期間７５１の間に前のガーベッジコレクション動作の第２の部分７８１を実行する。前のガーベッジコレクションは、有効なデータの残りの部分または最後の部分を１ブロックから他の１ブロックにコピーすることによって完了させられ得る。前のガーベッジコレクション動作が第２のタイムアウト期間７５１内に完了させられ得なければ、不揮発性メモリ記憶システムはガーベッジコレクション動作を完了させるために、第３のタイムアウト期間７５２のような後のタイムアウト期間を使用することができる。マルチセクタ書き込みコマンド７０４の終わりに、不揮発性メモリ記憶システムは、ストップコマンド７０６が受け取られた後に、データの全てのセクタ７６０〜７６２がメモリセルアレイに書き込まれるまでビジー信号をアサートすることができる。図７はマルチセクタ書き込みコマンドに関連する動作を示しているということに留意するべきである。以下でより詳しく説明されるように、実行されるガーベッジコレクション動作は、シングルセクタ書き込みコマンドとマルチセクタ書き込みコマンドとについては異なり得る。例えば、以下でより詳しく説明されるように、新しいデータを格納するために使用されるバッファのタイプは、受け取られた書き込みコマンドがシングルセクタ書き込みコマンドであるのか、それともマルチセクタ書き込みコマンドであるのかによる。
【００２９】
図６に戻って、ガーベッジコレクション動作の一部分がタイムアウト期間内に実行された後、動作６０６で、書き込み動作から受け取られた新しいデータは不揮発性メモリ記憶システムに関連付けられたバッファに格納され得る。１つの実施形態では、バッファは不揮発性メモリセルアレイ（例えば、図１に示されている不揮発性メモリアレイ１２２）に関連付けられたデータ構造であり得る。データ構造の例は、書き込みバッファブロックのような不揮発性メモリセルアレイのブロックを含み、これは以下でより詳しく記載される。他の１つの実施形態では、バッファは揮発性メモリセルアレイのブロックであり得る。例えば、新しいデータは、不揮発性メモリ記憶システムに関連付けられたＲＡＭ（例えば、図１に示されているＲＡＭ１１２）に置かれたブロックに格納され得る。さらに他の１つの実施形態では、前に論じられたように、新しいデータは別のメモリセルアレイ（例えば、図１に示されているメモリセルアレイ１２３）に置かれたブロックに格納され得る。
【００３０】
図８は、本発明の１つの実施形態に従う、段階的ガーベッジコレクションを実行するための詳細な動作のフローチャート図である。図８に示されているように、新しいデータをメモリに書き込むために書き込みコマンドが動作８０２で受け取られる。１つの実施形態では、書き込みコマンドはシングルセクタ書き込みコマンドである。ある環境では、以下でより詳しく説明されるように、他の１つの実施形態に従って、書き込みコマンドはマルチセクタ書き込みコマンドでもあり得る。書き込みコマンドが受け取られた後、不揮発性メモリ記憶システムは動作８０４でビジー信号をアサートする。
【００３１】
書き込みコマンドが実行される前に、動作８０６でガーベッジコレクション期間の間にガーベッジコレクション動作の一部分が実行される。例えば、１つの実施形態では、１つ以上のブロックがガーベッジコレクション動作のために選択される。その１つ以上のブロックは有効なデータおよび／または無効なデータを含み得る。有効なデータは、ガーベッジコレクション期間中に第２のブロックにコピーされる。ガーベッジコレクション動作に割り当てられたガーベッジコレクション期間と、コピーされるべき有効なデータの量とにより、有効なデータの全部または有効なデータの一部分が第２のブロックにコピーされる。ガーベッジコレクション動作のために割り当てられたガーベッジコレクション期間は、
ガーベッジコレクション期間＝タイムアウト期間−Ｔｐｒｏｇ
と表現することができ、ここでタイムアウト期間は、前に論じられたように、固定された、限られた期間である。Ｔｐｒｏｇは、新しいデータをメモリに（例えば、バッファに）書き込むことに関連付けられた最大プログラミング時間であるか、あるいは不揮発性メモリ記憶システムが新しいデータをメモリに書き込むために必要とする最大時間である。その結果として、１つの実施形態では、不揮発性メモリ記憶システムは、有効なデータを１つ以上のブロックから第２のブロックにコピーするための時間の量を追跡する。不揮発性メモリ記憶システムは、時間がガーベッジコレクション期間を超える前にコピーをやめる。
【００３２】
ガーベッジコレクション動作がガーベッジコレクション期間により完了させられ得なければ、書き込みコマンドに関連付けられた新しいデータは動作８１０で書き込みバッファブロックに書き込まれ得る。不揮発性メモリ記憶システムは、ガーベッジコレクション動作の前に、間に、または後に、新しいデータを書き込みバッファブロックに書き込むことができる。以下でより詳しく説明されるように、ガーベッジコレクション動作が完了すると直ぐに新しいデータは書き込みバッファブロックから更新ブロックにコピーされ得る。書き込みバッファブロックは不揮発性メモリ記憶システムによってメモリ内に維持される。一般に、書き込みバッファブロックは、不揮発性メモリ記憶システムにおいて新しいデータをバッファリングする。１つの実施形態では、書き込みバッファブロックは複数の論理アドレスにわたって広がる。他の１つの実施形態では、書き込みバッファブロックは１つの論理アドレス空間全体にわたって広がる。論理アドレス空間全体にわたって広がることで、書き込みバッファブロックは、不揮発性メモリ記憶システム全体にわたって全ての論理アドレスと論理アドレスの全てのグループ（すなわち、全ての論理グループ）に書き込まれようとしているデータを記憶することができる。換言すれば、複数の異なる論理グループと関連付けられた新しいデータが書き込みバッファブロックに格納され得る。論理グループは、メタブロックのサイズと同等であり得るサイズを有する論理アドレスのグループである。新しいデータは、順次にあるいは非順次に（すなわち、カオス的またはランダムな順序で）書き込みバッファブロックに書き込まれ得る。以下でより詳しく説明されるように、書き込みバッファブロックに書き込まれた新しいデータは後に他のブロック（例えば、更新ブロック）にコピーされるので、書き込みバッファブロックは一時的バッファとして役立つ。本願明細書で使用される“書き込みバッファブロッククリーニング”という用語は、書き込みバッファブロックに格納された新しいデータが他のブロックにコピーされることを意味する。
【００３３】
１つの実施形態では不揮発性メモリ記憶システムが書き込みバッファブロックを段階的ガーベッジコレクション動作のために使用するということに留意するべきである。従って、書き込みバッファブロックは最も更新された新しいデータを記憶していないかもしれない。その結果として、新しいデータが後の読み出し動作で読み出されるならば、不揮発性メモリ記憶システムは、更新ブロックに格納されている新しいデータと書き込みバッファブロックに格納されている新しいデータとのどちらが最も新たに更新されたものであるかを調べる。読み出し動作は、その後、最も新たに更新された新しいデータにアクセスして戻す。他の１つの実施形態では、不揮発性メモリ記憶システムは、非段階的ガーベッジコレクション動作および段階的ガーベッジコレクション動作の両方のために書き込みバッファブロックを使用することができる。ここでは、書き込みバッファブロックは全ての書き込み動作のために使用される。換言すれば、非段階的ガーベッジコレクションおよび段階的ガーベッジコレクション動作からの新しいデータが書き込みバッファブロックに書き込まれる。従って、書き込みバッファブロックは、書き込みキャッシュのように動作し、従って最も新たに更新された新しいデータを包含する。
【００３４】
書き込みバッファブロックに関連付けられたインデックス情報は、別のデータ構造に、あるいは書き込みバッファブロック自体の一部として、格納され得る。そのデータ構造はメモリコントローラのＲＡＭに格納され得る。データ構造に格納されたインデックス情報は、書き込みバッファブロックに格納されたデータのトラッキングおよびアクセスを可能にする。インデックス情報は、例えば、書き込みバッファブロック内の位置への論理アドレスのマップまたは書き込みバッファブロックの有効な索引へのポインタを含むことができる。索引情報は、更新ブロックが閉じられた後あるいは書き込みバッファブロックへの数個の更新の後に、更新され得る。以下でより詳しく説明されるように、１つの実施形態では、書き込みバッファブロックはセクタレベルの索引のために構成され得る。他の１つの実施形態では、書き込みバッファブロックはページ境界索引のために構成され得る。書き込みバッファブロックは、満杯時に圧縮されることもできる。例えば、書き込みバッファブロックに格納されている有効なデータは新しいブロックにコピーされ、それは新しい書き込みバッファブロックとして参照されるべきあり、陳腐なエントリを有する既存の書き込みバッファブロックは消去される。本願明細書で使用される“書き込みバッファ圧縮”という用語は、書き込みバッファブロックに格納されている有効なデータが圧縮されることを意味する。
【００３５】
図８をなお参照すると、新しいデータが書き込みバッファブロックに書き込まれ、かつガーベッジコレクション動作がガーベッジコレクション期間中に実行された後、不揮発性メモリ記憶システムは動作８１２でタイムアウト期間の前にビジー信号を解除する。従って、１つのガーベッジコレクション動作または１つのガーベッジコレクション動作の一部分を含む書き込みコマンドを実行するための合計時間はタイムアウト期間を越えない。タイムアウト期間内にガーベッジコレクション動作の一部分が実行されるのであれば、残りの部分は後のタイムアウト期間で完了させられる。ガーベッジコレクション動作が完了すると、ガーベッジコレクションされた１つ以上のブロックが消去されて付加的なデータの格納のために利用可能にされる。
【００３６】
図９Ａおよび９Ｂは、本発明の実施形態に従う、段階的にガーベッジコレクションされる順次更新ブロックを伴うメモリブロックの簡略ブロック図である。図９Ａに示されているように、オリジナルのブロックＡ９８０と、関連する順次更新ブロックＡ９８２とがガーベッジコレクションのために選択される。一般に、書き込みコマンドから受け取られたデータは更新ブロックに書き込まれ得る。その中でデータが更新される各々の論理グループのために更新ブロックとして専用のメタブロックが割り当てられ得る。データの論理セクタは論理的に連続するセクタのセットを含む論理グループに格納されるということに留意するべきである。更新ブロックは、データを順次にあるいはカオス的順序で（すなわち、非順次に）受け入れるように管理され得る。順次更新ブロックＡ９８２のような順次更新ブロックは、全ての有効なセクタが現在同じメタブロックに置かれている論理グループにおいて１つ以上の物理ページを満たすデータを書き込むために書き込みコマンドがホストから受け取られたときに割り当てられるメタブロックであるということが理解されるべきである。順次更新ブロックに書き込まれるデータのセクタは、セクタがオリジナルブロックに書き込まれている対応する論理セクタに取って代わるように論理的にアドレス指定されて順次に書き込まれる。この論理グループの中の更新されるセクタは、順次更新ブロックが閉じられるかあるいはカオス的更新ブロックに変換されるまで、この順次更新ブロックに書き込まれ得る。順次更新ブロックは順次更新ブロックの最後の物理セクタ位置が書き込みされたときに閉じられたと見なされるということに留意するべきである。換言すれば、順次更新ブロックの閉鎖は、ホストにより書き込まれるかあるいはオリジナルブロックからコピーされる更新されるセクタデータによって順次更新ブロックが完全に満たされることに起因し得る。以下でより詳しく説明されるように、カオス的更新ブロックは、ホストにより書き込まれるデータのセクタが、更新される論理グループ内の前に書き込まれたデータのセクタに論理的に連続していないときに順次更新ブロックからの変換によって作られ得る。
【００３７】
オリジナルブロックＡ９８０は無効なデータと有効なデータとを含むことができ、図９Ａではそれぞれハッチパターンおよびドットパターンで表されている。オリジナルブロックＡ９８０からコピーされた有効なデータに加えて、順次更新ブロックＡ９８２はガーベッジコレクション動作の前に順次更新ブロックＡに書き込まれた既存のデータ９８１を付加的に含むということに留意するべきである。新しいデータ９８３を書き込む書き込みコマンドが受け取られたとき、書き込みコマンドは順次更新ブロックＡ９８２の閉鎖を誘発し得るが、それは１種のガーベッジコレクション動作である。なぜならば、それは新しいデータが開いている更新ブロックを持っていない論理グループと関連付けられるかあるいは新しいデータがガーベッジコレクション動作を引き起こすからである。不揮発性メモリ記憶システムはビジー信号をアサートし、その後、第１のガーベッジコレクション期間９７０に達するまで有効なデータをオリジナルブロックＡ９８０から順次更新ブロックＡ９８２にコピーする。コピー中、不揮発性メモリ記憶システムは時間を追跡し、不揮発性メモリ記憶システムは第１のガーベッジコレクション期間９７０を超える前にコピー動作をやめる。図９Ａに示されているように、オリジナルブロックＡ９８０に有効なデータがなお残っているので、ガーベッジコレクション動作はガーベッジコレクション期間９７０内に完了させられ得ない。その結果として、有効なデータの部分が順次更新ブロックＡ９８２にコピーされた後、新しいデータ９８３は、第１のタイムアウト期間に達する前に許された残っている時間内に書き込みバッファブロック９０８に書き込まれる。
【００３８】
図９Ｂは、ガーベッジコレクション動作の残りの部分が第２のタイムアウト期間内に完了させられ得ることを示す。ここで、新しいデータ９８４を書き込む第２の書き込みコマンドが第１の書き込みコマンドの後に受け取られる。その結果として、第２の書き込みコマンドに第２のタイムアウト期間が割り当てられる。第２のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＡ９８０から順次更新ブロックＡ９８２にコピーされる。この例では、残っている有効なデータの全体（または有効なデータの最後の部分）が第２のガーベッジコレクション期間９７２内に順次更新ブロックＡ９８２にコピーされ得る。従って、ガーベッジコレクション動作は第２のタイムアウト期間内に完了させられ得る。順次更新ブロックＡ９８２は満杯にされているので、順次更新ブロックＡは新しいオリジナルブロックＡ９８５または非更新ブロックに変換される。ガーベッジコレクション動作はこの第２のタイムアウト期間内に完了させられるので、オリジナルブロックＡ９８０は消去され、付加的なデータの格納に利用可能にされ得る。オリジナルブロックＡ９８０が消去された後、更新ブロックＣ９８６が割り当てられ、第２の書き込みコマンドから受け取られた新しいデータ９８４は新たに割り当てられた更新ブロックＣに書き込まれる。更新ブロックＣ９８６は新しいオリジナルブロックＡ９８５に関連付けられるかもしれないしあるいは関連付けられないかもしれないということに留意するべきである。
【００３９】
第２のタイムアウト期間内にガーベッジコレクションが完了した後、第２のタイムアウト期間内に利用可能な時間があれば、不揮発性メモリ記憶システムは書き込みバッファブロッククリーニング動作を行うことができる。書き込みバッファブロック９０８は、書き込みバッファブロックに書き込まれた新しいデータ９８３のような新しいデータが後に他のブロック（例えば、更新されたブロックＣ９８６）にコピーされるので、一時的バッファとして役立つ。図９Ｂの例では、第２のタイムアウト期間内に書き込みバッファブロッククリーニング動作のための時間がある。書き込みバッファブロック９０８に格納されている新しいデータ９８３は、新しいデータ９８４と同じ論理グループの中にある。従って、新しいデータ９８３は、ガーベッジコレクション動作の完了後に更新ブロックＣ９８６にコピーされる。書き込みバッファブロック９０８に格納されている新しいデータ９８３は無効としてマークされ、従って、書き込みバッファブロック内の付加的なスペースは付加的な新しいデータの格納のために利用可能にされ得る。書き込みバッファブロッククリーニング動作は全てのガーベッジコレクションの完了後に実行されるわけではないかもしれないということに留意するべきである。書き込みバッファブロッククリーニングのタイミングは以下でより詳しく説明される。
【００４０】
図１０Ａ〜１０Ｅは、本発明の実施形態に従う、段階的にガーベッジコレクションされるカオス的更新ブロックを伴うメモリブロックの簡略ブロック図である。図１０Ａに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４がガーベッジコレクションのために選択される。一般に、カオス的更新ブロックＡ９０４のようなカオス的更新ブロックは、データのセクタが１つの論理グループ内でランダムな順序で、個々のセクタの任意の反復を伴って、更新されることを可能にする。カオス的更新ブロックは、ホストにより書き込まれるデータのセクタが、更新される論理グループ内の前に書き込まれたデータのセクタに論理的に連続していないときに順次更新ブロックからの変換によって作成され得る。この論理グループにおいてその後に更新される全てのデータのセクタは、グループ内でのそれらの論理セクタアドレスが何であっても、カオス的更新ブロック内の次の利用可能なセクタ位置に書き込まれる。
【００４１】
ここで、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４は、図１０Ａにおいてハッチパターンおよびドットパターンでそれぞれ表される無効なデータおよび有効なデータを含む。新しいデータ９０１を書き込む書き込みコマンドが受け取られたとき、不揮発性メモリ記憶システムはビジー信号をアサートし、その後、第１のガーベッジコレクション期間９５０に達するまで有効なデータをオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーする。コピー中、不揮発性メモリ記憶システムは時間を追跡し、不揮発性メモリ記憶システムは第１のガーベッジコレクション期間９５０を超える前にコピー動作をやめる。図１０Ａに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４に有効なデータがなお残っているので、ガーベッジコレクション動作は第１のガーベッジコレクション期間９５０内に完了させられ得ない。その結果として、有効なデータの部分が新しいブロックＡ９０６にコピーされた後、ガーベッジコレクション動作が始まる前に受け取られた新しいデータ９０１は第１のタイムアウト期間に達する前に書き込みバッファブロック９０８に書き込まれる。
【００４２】
図１０Ｂは、その次のタイムアウト期間におけるガーベッジコレクション動作の続きを示す。ここで、第１の書き込みコマンドの後に第２の書き込みコマンドが受け取られ、第２のタイムアウト期間が第２の書き込みコマンドに割り当てられる。第２のタイムアウト期間の間に、残りの有効なデータが、第２のガーベッジコレクション期間９５１に達するまでオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーされる。図１０Ｂに示されているように、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４に有効なデータがなお残っているので、ガーベッジコレクション動作は第２のガーベッジコレクション期間９５１内に完了させられ得ない。従って、有効なデータの部分が新しいブロックＡ９０６にコピーされた後、ガーベッジコレクション動作が始まる前に受け取られた新しいデータ９０５は書き込みバッファブロック９０８に書き込まれる。
【００４３】
図１０Ｃは、ガーベッジコレクション動作の残りの部分が第３のタイムアウト期間内に完了させられ得ることを示す。第２の書き込みコマンド後に第３の書き込みコマンドが受け取られる。その結果として、第３のタイムアウト期間が第３の書き込みコマンドに割り当てられる。第３のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４から新しいブロックＡ９０６にコピーされる。ここで、全ての残りの有効なデータ（あるいは有効なデータの最後の部分）が第３のガーベッジコレクション期間９５３内に新しいブロックＡ９０６にコピーされ得る。従って、ガーベッジコレクション動作は第３のタイムアウト期間内に完了させられ得る。ガーベッジコレクション動作がこの第３のタイムアウト期間に完了させられるので、オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４は消去されて付加的なデータの格納のために利用可能にされ得る。オリジナルブロックＡ９０２およびカオス的更新ブロックＡ９０４が消去された後、新しい更新ブロックＢ９６２が割り当てられ、第３の書き込みコマンドから受け取られた新しいデータ９０９は新たに割り当てられた更新ブロックＢに書き込まれる。新しいデータ９０９は書き込みバッファブロック９０８に書き込まれないが、それは、ガーベッジコレクション動作が完了して、その次のタイムアウト期間まで新しいデータをバッファリングする必要がないからである。この例では、書き込みバッファブロッククリーニング動作が実行され、その動作で、新しいデータ９０１，９０５，および９０９が同じ論理グループに属すると仮定して、書き込みバッファブロック９０８に格納されている新しいデータ９０１および９０５が更新ブロックＢ９６２にコピーされる。
【００４４】
図１０Ｄは、第４のタイムアウト期間中に行われる他の１つのガーベッジコレクション動作を示す。図１０Ｄに示されているように、オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２がガーベッジコレクションのために選択される。カオス的更新ブロックに変換されている更新ブロックＢ９６２は、第１、第２、および第３の書き込みコマンドに関連する新しいデータ９０１，９０５，および９０９を含む。第４の書き込みコマンドが受け取られたとき、不揮発性メモリ記憶システムはビジー信号をアサートし、その後に有効なデータをオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２から新しいブロックＢ９６４にコピーする。図１０Ｄに示されているように、有効なデータがオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２になお残っているので、ガーベッジコレクション動作は第４のガーベッジコレクション期間９５２内に完了させられ得ない。有効なデータの部分が新しいブロックＢ９６４にコピーされた後、第４の書き込みコマンドから受け取られた新しいデータ９０３は書き込みバッファブロック９０８に書き込まれる。
【００４５】
図１０Ｅは、図１０Ｄのガーベッジコレクション動作の残りの部分が第５のタイムアウト期間に完了させられ得ることを示す。第４の書き込みコマンド後に第５の書き込みコマンドが受け取られる。その結果として、第５のタイムアウト期間が第５の書き込みコマンドに割り当てられる。第５のタイムアウト期間の間に、残りの有効なデータがオリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２から新しいブロックＢ９６４にコピーされる。ここで、全ての残りの有効なデータ（あるいは有効なデータの最後の部分）が第５のガーベッジコレクション期間９５３内に新しいブロックＢ９６４にコピーされ得る。従って、始めに第４のタイムアウト期間中に実行されたガーベッジコレクション動作は第５のタイムアウト期間内に完了させられ得る。ガーベッジコレクション動作がこの第５のタイムアウト期間に完了させられるので、オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２は消去されて、付加的なデータの格納のために利用可能にされる。オリジナルブロックＢ９６０およびカオス的更新ブロックＢ９６２が消去された後、更新ブロックＣ９６５が割り当てられ、第５の書き込みコマンドから受け取られた新しいデータ９０７は新たに割り当てられた更新ブロックＣに書き込まれる。更新ブロックＣ９６５は新しいブロックＢ９６４に関連付けられるかもしれないしあるいは関連付けられないかもしれないということに留意するべきである。ここで、書き込みバッファブロッククリーニング動作が実行され、従って、新しいデータ９０３および新しいデータ９０７が同じ論理グループに属すると仮定して、書き込みバッファブロック９０８に格納されている新しいデータ９０３は更新ブロックＣ９６５にコピーされる。
【００４６】
図１１は、本発明の１つの実施形態に従う、書き込みバッファブロックへのアクセスを最適化する動作のフローチャート図である。書き込みバッファブロックの維持は、あるオーバーヘッドを導入する。オーバーヘッドを減少させるために、１つの実施形態では、書き込みバッファブロックへの書き込みが最小にされ得る。図１１に示されているように、動作１００２で書き込みコマンドが受け取られる。その後、不揮発性メモリ記憶システムは動作１００４で実行時間を推定する。実行時間は、書き込みコマンドを実行する期間である。書き込みコマンドの実行は、例えば、新しいデータをメモリにプログラムする（すなわち、書き込む）ことと、ガーベッジコレクション動作を実行することと、他の動作の実行とを含み得る。例えば、実行時間は、有効なデータを１つ以上のブロックから他の１つのブロックにコピーするための期間と新しいデータを書き込む期間とを含み得る。
【００４７】
不揮発性メモリ記憶システムは、実行時間を即時に推定する。不揮発性メモリ記憶システムは、種々のパラメータに基づいて実行時間を推定することができる。パラメータの例として、ガーベッジコレクションのタイプ（例えば、ブロック閉鎖、整理統合、圧縮、および他のタイプ）、ガーベッジコレクションされるべきブロック（例えば、更新ブロックおよび他のブロック）に格納されている有効なデータの量、不揮発性メモリ記憶システムに関連するプログラミング時間、ガーベッジコレクションされるブロックのサイズ（例えば、メタブロックのサイズ）、プレパディング(pre-padding) が必要か否か、プレパディングされるべきデータの量、パイプライニング、キャッシング、周波数設定、プログラム破損、および他のパラメータを含む。実行時間を推定する１つの例では、最初の１つ以上のブロックは１２ページの有効なデータを含み、その１２ページの有効なデータが１つの第２のブロックにコピーされる。不揮発性メモリ記憶システムは、１２ページの有効なデータを読み出すために不揮発性メモリ記憶システムが必要とする時間の量とその有効なデータを第２のブロックに書き込むために不揮発性メモリ記憶システムが必要とする時間の量とを加えることによって実行時間を推定することができる。
【００４８】
不揮発性メモリ記憶システムが実行時間を推定した後、その実行時間は動作１００６でタイムアウト期間と比較される。動作１００８に示されているように、その推定された実行時間がタイムアウト期間より短ければあるいは動作がタイムアウト期間内に完了させられ得るならば、ガーベッジコレクション動作が、引き起こされたならば、実行されてタイムアウト期間内に完了させられ、新しいデータが更新ブロックに書き込まれる。一方、動作１０１０に示されているように、推定された実行時間がタイムアウト期間を超える（すなわち、タイムアウト期間より大きいかあるいはタイムアウト期間に等しい）ならば、新しいデータは書き込みバッファブロックに書き込まれ、割り当てられたガーベッジコレクション期間は、書き込みバッファブロッククリーニングのためにあるいはガーベッジコレクション動作（引き起こされたならば）の一部分を実行するために使用され得る。１つの実施形態では、以下でより詳しく説明されるように、書き込みバッファブロッククリーニングは、タイムアウト期間内に残っている時間の間に、書き込みバッファブロック内の第１の有効なエントリから始まることができる。推定された実行時間がタイムアウト期間を超えるときに書き込みバッファブロックに書き込むことによって、書き込みバッファブロックへの書き込みはより少数となり、従って、書き込みバッファブロックを維持することに関連するオーバーヘッドは低減され得る。
【００４９】
書き込みバッファブロック−ページ境界索引付け
１つの実施形態では、書き込みバッファブロックは複数のページを含むように構成され、書き込みバッファブロック内の各ページは索引付けされる。書き込みバッファブロックの各ページは、１セクタ以上の新しいデータを記憶するように構成される。従って、１ポインタが１ページを指すかあるいは参照し、１ページ内の複数のセクタは１ポインタにより参照され得るが、それは、ポインタが１つのページを指すのであってページ内の複数のセクタを指すのではないからである。ここで、同じメタページに属する新しいデータのセクタは、書き込みバッファブロックの同じメタページに書き込まれる。しかし、別々のメタページに属する新しいデータのセクタは書き込みバッファブロックの別々のメタページに書き込まれる。例えば、第１の書き込みコマンドに関連付けられた新しいデータの第１のセクタは書き込みバッファブロックの第１のページに書き込まれる。その後、新しいデータの第２のセクタが第２の書き込みコマンドから受け取られる。その新しいデータの第２のセクタが新しいデータの第１、第２と同じメタページに属するならば、第２のセクタは書き込みバッファブロックの第１のページに書き込まれる。一方、新しいデータの第２のセクタが別のメタページに属するならば、第２のセクタは書き込みバッファブロックの別のメタページに書き込まれる。
【００５０】
書き込みバッファブロック−セクタレベル索引付け
他の１つの実施形態では、書き込みバッファブロックは複数のセクタを含むように構成され、書き込みバッファブロック内の１つ以上のセクタは索引付けされ得る。例えば、１ポインタが複数のセクタ（例えば、４セクタ）を指すかあるいは参照することができる。他の１つの例では、１ポインタが１セクタを指すかあるいは参照することができる。書き込みバッファブロック内の各セクタが索引付けされる例では、新しいデータは書き込みバッファブロックの単一のセクタに書き込まれる。他の１つの書き込みコマンドに関連付けられたその次の新しいデータは書き込みバッファブロック内の次の利用可能なセクタに書き込まれる。例えば、複数の書き込みコマンドからの新しいデータのセクタは、書き込みバッファブロック内の同じページの別々のセクタに書き込まれ得る。従って、書き込みバッファブロックは複数のセクタを含むように構成されることができ、各セクタは新しいデータの１つのセクタを記憶するように構成される。
【００５１】
タイムアウトエラーなしでシングルセクタ書き込みを持続させるために、不揮発性メモリ記憶システムは、割り当てられたセクタが不揮発性メモリ記憶システムのメタブロックの総数より多いように数個のセクタを書き込みバッファブロックに割り当てることができる。書き込みバッファブロックが複数のメタブロックで構成され得るということが理解されるべきである。書き込みバッファブロックに割り当てられるセクタの数を計算するために、例えば、書き込みバッファブロックを構成するメタブロックの数Ｍは、
M=M1+(M1*M2)/(Metablock_Size-M2) (1.0)
と定義することができ、“Metablock_Size"は“メタブロックサイズ”を意味し、ここで、
M1=RoundUp.to.Nearest.Integer[(N-1)*(Total.Number.of.Metablocks.in.System)/(Mtablock_Size)]
であり、ここで“RoundUp.to.Nearest.Integer"は“最近の整数への切り上げ”を意味し、“Total.Number.of.Metablocks.in.System"は“システム内のメタブロックの総数”を意味し、
M2=RoundUp.to.Nearest.Integer[(N*Tgc)/(N*TO-Tgc)]
であり、
N=RoundDown.to.Nearest.Integer[(Tgc+TO)/TO]
であり、ここで“RoundDown.to.Nearest.Integer"は“最近の整数への切り下げ”を意味し、TOはタイムアウト期間であり、Tgc は１つの完全なガーベッジコレクション動作を実行するための時間である。書き込みバッファブロックに割り当てられるセクタの総数は、
セクタの総数=M*Metablock_Size （１．２）
として定義されることができ、ここでＭは方程式１．０で定義され、“Metablock_Size"は、５１２セクタ／メタブロック、１，０２４セクタ／メタブロック、２，０４８セクタ／メタブロックあるいは他のサイズのようなセクタ数で表した各メタブロックのサイズである。一般に、方程式１．０および１．２は、書き込みバッファブロックに割り当てられるセクタの総数を不揮発性メモリ記憶システム内のメタブロックの総数より大きく定義する。メタブロックの総数に加えて、方程式１．０は、書き込みバッファブロックに関連するオーバーヘッドを維持するための１つ以上のメタブロック（またはセクタ）（以降、“オーバーヘッドメタブロック”または“オーバーヘッドセクタ”）を割り当てる。例えば、オーバーヘッドメタブロックの数を定める方程式１．０の部分は(M1*M2)/(Metablock_size-M2) であり、ここでオーバーヘッドセクタはオーバーヘッドブロックをメタブロックサイズと乗じることによって計算され得る。
【００５２】
方程式１．２で定められる数のセクタを書き込みバッファブロックに割り当てることにより、連続的でランダムなシングルセクタ書き込みという最悪の場合のシナリオにおいてもタイムアウトエラーが回避され得る。タイムアウトエラーは、書き込みバッファブロックが満杯でガーベッジコレクション動作が完了させられ得ないときに生じ得る。最悪の場合のシナリオは、各シングルセクタ書き込みコマンドが別々の論理グループに書き込み、これによりどの書き込みでも１つの完全なガーベッジコレクション動作を引き起こすときに、生じる。この悪い場合のシナリオでは、セクタが蓄積されて書き込みバッファブロックに書き込まれる。この悪い場合のシナリオは、全てのタイムアウト期間で新しいデータの単一のセクタが書き込みバッファブロックに書き込まれると共に不揮発性メモリ記憶システムが１つの完全なガーベッジコレクション動作を実行するために必要な全ての時間（Ｔｇｃ）で１セクタが無効とマークされるかのように見られ得る。さらに、書き込みバッファブロックが満たされるかあるいは満杯であるとき、書き込みバッファブロックは、新しいセクタが受け取られるけれども書き込みバッファブロッククリーニング動作が実行され得ないように、圧縮される。従って、１つの悪い場合のシナリオでは、ガーベッジコレクション期間がタイムアウト期間より大きいときには書き込みバッファブロックは空にされるより速く満たされる。
【００５３】
しかし、書き込みバッファブロック内の複数のセクタが同じ論理グループに属するならば、１ガーベッジコレクション動作中に全てのセクタが整理統合され得る。充分なメタブロックＭを書き込みバッファブロックに割り当てることにより、不揮発性メモリ記憶システム内のメタブロックの総数より多くのセクタ（またはエントリ）が書き込みバッファブロックに存在することになり、従って、複数の有効なセクタが書き込みバッファブロックに書き込まれている論理グループが存在することになる。書き込みバッファブロックの１つのセクタがガーベッジコレクションされるあるいは整理統合されるとき、同じ論理グループに属する全てのセクタが１つの新しい更新ブロックに整理統合され、書き込みバッファブロックにおいて無効とマークされる。従って、書き込みバッファブロックを空にする速度は充填速度より大きくなり、これにより書き込みバッファブロックが満杯であるかあるいは満たされることを防止する。従って、前述した最悪の場合のシナリオについてもタイムアウトエラーの発生が防止され得るように、所与の全てのＴｇｃについて、不揮発性メモリ記憶システムは不揮発性メモリ記憶システム内のメタブロックの総数より大きい数のセクタを書き込みバッファブロックに割り当てる。
【００５４】
図１２は、本発明の１つの実施形態に従う、新しいデータをスクラッチパッドブロックに一時的に格納するための動作のフローチャート図である。不揮発性メモリ記憶システムがマルチレベルバッファリングまたは複数のバッファレベルを持つことができ、それがマルチレベルキャッシングの思想と類似し得るということが理解されるべきである。この実施形態では、書き込みバッファブロックは、多数のバッファレベルのうちの１つに関連付けられ得る。複数バッファレベルでは、新しいデータを書き込みバッファブロックに直ぐに書き込む代わりに、新しいデータは、書き込みバッファブロックに書き込まれる前に一時的に他の１つのバッファレベルに格納され得る。書き込みバッファブロックのバッファレベルと異なるバッファレベルでの新しいデータの一時的格納は、段階的ガーベッジコレクション動作における書き込みバッファブロックの使用に関連する複雑さ、オーバーヘッド、および待ち時間を低減することができる。バッファの１つの例はスクラッチパッドブロックである。スクラッチパッドブロックは、書き込みバッファブロックとは異なるバッファレベルに関連付けられ得る。例えば、スクラッチパッドブロックは第１のバッファレベルとして使用され、書き込みバッファブロックは第２のバッファレベルとして使用され得る。前に論じられたように、シングルセクタ索引付けでは、複数の書き込みコマンドからの新しいデータのセクタは、書き込みバッファブロック内の同じページの別々のセクタに書き込まれ得る。不揮発性メモリ記憶システムは部分的なページをプログラムできないかもしれないので、本発明の１つの実施形態に従って、新しいデータは、書き込みバッファブロックに転送される前に、スクラッチパッドブロックのような第１のバッファレベルに一時的に格納され得る。スクラッチパッドブロックはデータ更新ブロックの１つの形であって、その中では関連する１つの論理グループ内の論理セクタがランダムな順序で任意の量の反復を伴って更新され得る。スクラッチパッドブロックは、意図された論理セクタが終了したりあるいは物理ページ境界を越えたりしない書き込みコマンドにより作られる。スクラッチパッドブロックは部分的物理ページに相当するデータを包含することができるけれども部分的プログラム済みページデータは許されない。スクラッチパッドブロックは、不揮発性メモリ記憶システム内の各更新ブロックのために１つの有効なページのデータを保持することができる。不揮発性メモリ記憶システムは、例えば、８個の更新ブロックを割り当てられることができ、従って、スクラッチパッドブロックは９個の有効なページのデータを記憶することができる。
【００５５】
図１２に示されているように、書き込みコマンドから受け取られた新しいデータは始めに動作１１０２でスクラッチパッドブロックに書き込まれる。スクラッチパッドブロックは複数のページを含むことができ、各ページは複数のセクタを含む。新しいデータはスクラッチパッドブロックのセクタにコピーされる。動作１１０４で、新しいデータは、その後、書き込みバッファブロックに関連付けられているスクラッチパッドブロック内の１つのページが満杯であるとき、スクラッチパッドブロックから書き込みバッファブロックにコピーされる。従って、不揮発性メモリ記憶システムは、スクラッチパッドブロック内のページのセクタを、ページの全てのセクタが種々の書き込みコマンドからの新しいデータで満たされるまで、蓄積する。不揮発性メモリ記憶システムは、その後、そのページ全体(例えば、８セクタの新しいデータ)をスクラッチパッドブロックから書き込みバッファブロックに１プログラム動作でコピーする。書き込みバッファブロックはスクラッチパッドブロックより大きくてより多くの有効なデータを収容し得るので、スクラッチパッドブロックはより少量のガーベッジコレクションされるべきデータを有する。従って、スクラッチパッドブロックのガーベッジコレクションは書き込みバッファブロックのガーベッジコレクションより高速である。その結果として、新しいデータをスクラッチパッドブロックを経由して書き込みバッファブロックに書き込む動作は、新しいデータを書き込みバッファブロックに直接書き込む動作より速い。
【００５６】
オーディオ／ビデオデータ
不揮発性メモリ記憶システムに格納されているオーディオ／ビデオファイル（以降、“オーディオ／ビデオデータ”）に関連付けられたデータにアクセスするホストは、他のデータと比べて所定の速度でオーディオ／ビデオデータを書き込む必要があるかもしれない。ホストがオーディオ／ビデオデータを不揮発性メモリ記憶システムにおよび／または不揮発性メモリ記憶システムからストリーミングするとき、ストリームに割り当てられる帯域幅は、所定の速度と一致するかあるいはそれを超える。オーディオ／ビデオデータのアクセス中に行われるガーベッジコレクション動作は、オーディオ／ビデオデータの書き込み性能を低下させることがある。従って、１つの実施形態では、マルチセクタ書き込みコマンドがオーディオ／ビデオデータに関連付けられていないかあるいはマルチセクタ書き込みコマンドがオーディオ／ビデオ書き込みの始まりにあるときには段階的ガーベッジコレクションが行われる。
【００５７】
オーディオ／ビデオデータを他のデータから区別するために、１つの実施形態では、不揮発性メモリ記憶システムは、マルチセクタ書き込みコマンドに関連付けられたターゲット論理アドレスを参照することができる。オーディオ／ビデオデータは順次に書き込まれるので、逆方向ジャンプ(backwards jump)として解釈されるターゲット論理アドレスは、新しいデータがオーディオ／ビデオデータ（あるいはオーディオ／ビデオデータの始まり）ではないことを示すことができる。他の１つの実施形態では、不揮発性メモリ記憶システムは、新しいデータに関連付けられたセクタの数を参照することによってもオーディオ／ビデオデータを他のデータから区別することができる。オーディオ／ビデオデータは、記録単位(recording unit)と称される単位で格納され得る。オーディオ／ビデオデータに関連付けられる最小の記録単位の長さは３２セクタであり得る。従って、３２セクタの整数倍ではない新しいデータに関連付けられたセクタの数は、その新しいデータがオーディオ／ビデオデータではないことを示すことができる。記録単位に整列しないか、あるいは記録単位の始まりから始まらない受け取られた新しいデータも、その新しいデータがオーディオ／ビデオデータではないことを示すことができる。
【００５８】
その結果として、次の条件、すなわち（１）マルチセクタ書き込みコマンドがガーベッジコレクション動作を引き起こす、（２）ターゲット論理アドレスが逆方向ジャンプとして解釈される、（３）ターゲット論理アドレスが記録単位境界と整列させられていない、（４）新しいデータに関連付けられたセクタの数が３２の整数倍でなければ、ストップコマンドが受け取られた（すなわち、マルチセクタ書き込みコマンドの終わり）後、という条件のうちの１つが当てはまるならば、段階的ガーベッジコレクションが実行され得る。
【００５９】
シングルセクタ書き込み
図１３は、本発明の１つの実施形態に従う、シングルセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。新しいデータは、メモリセルアレイ全体の中でランダムなアドレスにシングルセクタとして書き込まれ得る。ホストアクティビティとカードフラグメンテーションとにより、ホストは複数のセクタを有する長いファイルをシングルセクタ書き込みコマンドを用いてランダムな位置に書き込むことができる。限られた数の割り当てられた更新ブロックがあるので、これらのシングルセクタ書き込みは、更新ブロックを速やかに用いることができ、これにより、その後の書き込み動作のためにブロックをクリアするガーベッジコレクション動作を実行するように不揮発性メモリ記憶システムを促すことができる。
【００６０】
図１３に示されているように、シングルセクタ書き込みコマンドが動作１２０２で受け取られる。その後、そのシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすか否かについて動作１２０４で判定が行われる。そのシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こさなければ、新しいデータは動作１２２０でメモリに書き込まれる。しかし、シングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすならば、ペンディングしている段階的ガーベッジコレクション(すなわち、既に始まっているけれども、ガーベッジコレクションが完了させられ得ないために段階的に実行されたガーベッジコレクション動作)があるか否かについて他の１つの判定が動作１２０６で行われる。段階的ガーベッジコレクションがあるならば、動作１２０８でその段階的ガーベッジコレクション動作が続行される。換言すれば、前のガーベッジコレクション動作からの残りの部分が続行される。動作１２１０に示されているように、ガーベッジコレクション期間（例えば、タイムアウト期間とプログラミング時間との差）まであるいは段階的ガーベッジコレクションが完了させられるまで、段階的ガーベッジコレクション動作が実行される。
【００６１】
段階的ガーベッジコレクション動作がガーベッジコレクション期間内に完了させられ得なければ、新しいデータは動作１２１８で書き込みバッファブロックに書き込まれる。ガーベッジコレクション期間に達していないかあるいは段階的ガーベッジコレクション動作がガーベッジコレクション期間の前に完了させられ得たならば、段階的ガーベッジコレクション動作を完了させた後であっても、シングルセクタ書き込みコマンドがなおガーベッジコレクション動作を引き起こすか否かについての他の１つの判定が動作１２１２で行われる。シングルセクタ書き込みコマンドがガーベッジコレクションを引き起こさなければ、新しいデータが動作１２２０でメモリに書き込まれる。一方、シングルセクタ書き込みコマンドがガーベッジコレクションを引き起こすならば、動作１２１６に示されているガーベッジコレクション期間まで動作１２１４でガーベッジコレクション動作が実行される。ガーベッジコレクション動作がガーベッジコレクション期間までに完了させられ得なければ、新しいデータは動作１２１８で書き込みバッファブロックに書き込まれる。そうでなければ、新しいデータは動作１２２０でメモリに書き込まれる。段階的ガーベッジコレクションがあってかつ現在の書き込みコマンドもガーベッジコレクション動作を引き起こすならば、動作１２１６に示されているガーベッジコレクション期間は動作１２１０に示されているガーベッジコレクション期間の続きであるということに留意するべきである。従って、段階的ガーベッジコレクションがあってかつ現在のシングルセクタ書き込みコマンドがガーベッジコレクション動作を引き起こすならば、両方の動作が総ガーベッジコレクション期間内に完了させられる。換言すれば、動作１２０８に示されている段階的ガーベッジコレクション動作と動作１２１４に示されているガーベッジコレクション動作との両方のために割り当てられる実行時間は、例えば、タイムアウト期間とプログラミング時間との差である。
【００６２】
新しいデータが動作１２２０でメモリに書き込まれた後、書き込みバッファブロックに有効なエントリがあるか否かについて、またタイムアウト期間に達しているか否かについて、動作１２２４で判定が行われる。書き込みバッファブロックに有効なエントリがないかあるいはタイムアウト期間に達しているならば、動作は終了する。一方、有効なエントリがあってかつタイムアウト期間に達していなければ、書き込みバッファブロッククリーニング動作が動作１２２６でタイムアウト期間まで実行される。書き込みバッファブロック圧縮動作も、この期間中にタイムアウト期間まで実行され得る。
【００６３】
マルチセクタ書き込み
図１４は、本発明の１つの実施形態に従う、マルチセクタ書き込みコマンドに関連付けられた不揮発性メモリ記憶システム動作のフローチャート図である。メモリセルアレイに書き込まれる大抵の新しいデータは、連続した順次論理アドレス空間を占める大きなデータファイルである。ホストアクティビティにより、ホストは大きなデータファイルをマルチセクタ書き込みコマンドを用いて書き込むことができる。そのような新しいデータは、複数のタイムアウト期間を有する新しいデータの複数のセクタを含む。図７は、マルチセクタ書き込みコマンドの例を示す。一般に、複数のタイムアウト期間が利用可能なので、新しいデータは、書き込みバッファブロックの代わりに、割り当てられた更新ブロックに書き込まれ得る。従って、ガーベッジコレクションは、普通は、マルチセクタ書き込みコマンドに割り当てられた複数のタイムアウト期間内に完了させられ得るので、書き込みバッファブロックは普通は複数の書き込みコマンドで使用されない。
【００６４】
図１４に示されているように、マルチセクタ書き込みコマンドが動作１３０２で受け取られる。その後、動作１３０４で、新しいデータのセクタは格納され（あるいはバッファリングされ）、必要ならばガーベッジコレクション動作が実行され得る。ここで、複数のタイムアウト期間がマルチセクタ書き込みコマンドに割り当てられ、１ガーベッジコレクション動作は普通はマルチセクタ書き込みコマンドの終わりまでに完了させられ得るので、不揮発性メモリ記憶システムは書き込みバッファブロックを利用しないかもしれない。従って、書き込みバッファブロックの代わりに、不揮発性メモリ記憶システムは、新しいデータを不揮発性メモリ記憶システムに関連付けられているＲＡＭに、あるいは不揮発性メモリ記憶システムに関連付けられている他のメモリに格納することができるのと同時に、割り当てられたタイムアウト期間を用いてガーベッジコレクション動作を実行するために新しいデータのセクタとセクタとの間にビジー信号をアサートする。
【００６５】
ホストセクタがバッファリングされた後、新しいデータのＮ個未満のセクタが受け取られたのか否かについて動作１３０６で判定が行われる。前に論じられたように、ガーベッジコレクション動作は、普通は、マルチセクタ書き込み動作に割り当てられた複数のタイムアウト期間内に完了させられ得るので、マルチセクタ書き込みコマンドに関連付けられた新しいデータは書き込みバッファブロックに書き込まれないかもしれない。しかし、１つの実施形態では、ガーベッジコレクション動作を完了させるために充分なタイムアウト期間が割り当てられなければ、書き込みバッファブロックがマルチセクタ書き込みコマンドで使用され得る。従って、ガーベッジコレクション動作が引き起こされるか否かに関わらず、
N=round-down to nearest integer [(Tgc+TO)/TO] （２．０）
として定義された新しいデータの少なくともＮ個のセクタを伴うマルチセクタ書き込みコマンドが書き込みバッファブロックにではなくて更新ブロックに直接書き込まれ得る。ここで“round-down to nearest integer" は、“最近の整数への切り捨て”を意味する。方程式２．０は、書き込みコマンドがシングルセクタ書き込みコマンドであるときあるいは不揮発性メモリ記憶システムがマルチセクタ書き込みコマンドで新しいデータのＮ個未満のセクタを受け取ったときに、新しいデータが書き込みバッファブロックに書き込まれることを示す。
【００６６】
なお図１４を参照すると、Ｎ個未満のセクタが受け取られたならば、不揮発性メモリ記憶システムは、図１３に示されているシングルセクタ書き込みコマンド動作に従ってマルチセクタ書き込みコマンドを操作する。しかし、新しいデータのＮ個より多くのセクタが受け取られたならば、書き込みバッファブロッククリーニング動作が実行され得るか否かについて動作１３１０で判定が行われる。例えば、動作１３０２で受け取られた新しいデータがガーベッジコレクションを引き起こさなかったならば、あるいは新しいデータが割り当てられたガーベッジコレクション期間の前に完了させられたガーベッジコレクションを引き起こしたのであれば、書き込みバッファブロッククリーニング動作が実行され得る。しかし、新しいデータが記録単位境界に整列させられているならば、新しいデータはオーディオ／ビデオデータであるかもしれないので、書き込みバッファブロックリーニングは実行されない。書き込みバッファブロッククリーニング動作が実行され得なければ、新しいデータは動作１３１４でメモリに書き込まれる。書き込みバッファブロッククリーニング動作が実行され得るならば、マルチセクタ書き込みコマンド実行中に不揮発性メモリ記憶システムによりアサートされた合計のビジー期間がＴｇｃ−Ｔｐｒｏｇになるまで、動作１３１２で段階的ガーベッジコレクション動作および書き込みバッファブロッククリーニング動作が実行される。その後、新しいデータは動作１３１４で不揮発性メモリセルアレイに書き込まれる。この実施形態では、動作１３１２に示されている書き込みバッファブロッククリーニングは、Ｔｇｃ−Ｔｐｒｏｇの期間まで、４タイムアウト期間、５タイムアウト期間、および他の期間などのいろいろな期間の間にマルチセクタ書き込みコマンドから受け取られた始めの数個のセクタの中間（例えば、第２のセクタと第３のセクタとの間）に、実行され得る。
【００６７】
書き込みコマンドが実行された後、新しいデータが３２セクタの整数倍であるか否かについて動作１３１６で判定が行われる。新しいデータが３２セクタの整数倍であれば、新しいデータはオーディオ／ビデオ関連であるかも知れず、動作は終了する。一方、新しいデータが３２セクタの整数倍でなければ、動作１３１８で、書き込みバッファブロック内に有効なエントリがあるか否かについて、またタイムアウト期間に達しているか否かについて、判定が行われる。有効なエントリが書き込みバッファブロック内にないかあるいはタイムアウト期間に達していれば、動作は終了する。一方、有効なエントリがあってかつタイムアウト期間に達していなければ、動作１３２０でタイムアウト期間まで書き込みバッファブロッククリーニング動作が実行される。
【００６８】
前述した実施形態は、段階的ガーベッジコレクションのための方法および／またはシステムを提供する。ガーベッジコレクション動作は複数の段階に分割されることができ、その複数の段階は複数のタイムアウト期間にわたって実行される。ガーベッジコレクション動作を分割することにより、ガーベッジコレクション動作の各段階はタイムアウト期間内に完了させられることができ、これによりタイムアウトエラーを防止する。
【００６９】
前述した実施形態は明確な理解を目的としてある程度詳細に記載されているけれども、実施形態は提示された細目に限定されない。実施形態を実現する多くの代わりの方法がある。従って、開示された実施形態は実例となるものであって制限するものではないと見なされるべきであり、実施形態は本願明細書で与えられた細目に限定されるべきではなくて、添付されている特許請求の範囲の範囲および同等物の中で改変され得る。特許請求の範囲で明示的に述べられていない限り、特許請求の範囲において要素および／または動作は動作の特定の順序を示唆しない。
【特許請求の範囲】
【請求項１】
不揮発性メモリ記憶システムを動作させる方法であって、
複数のデータを書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
前記タイムアウト期間内にガーベッジコレクション動作の一部分を実行するステップと、
前記複数のデータを前記不揮発性メモリ記憶システムに関連付けられているバッファに格納するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記バッファは、書き込みバッファブロックである方法。
【請求項３】
不揮発性メモリ記憶システムを動作させる方法であって、
複数のデータを書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
複数の論理アドレスにわたって広がるように構成された第３のブロックに前記複数のデータを書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、
を含む方法。
【請求項４】
請求項３記載の方法において、
前記不揮発性メモリ記憶システムにおいて前記第３のブロックを維持するステップをさらに含む方法。
【請求項５】
請求項３記載の方法において、
前記複数の有効なデータの一部分をコピーするステップは、
前記複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップのための時間を追跡するステップと、
前記時間が前記ガーベッジコレクション期間を超える前に前記複数の有効なデータの一部分をコピーするステップを止めるステップと、
を含む方法。
【請求項６】
請求項３記載の方法において、
前記複数の有効なデータの一部分をコピーするステップおよび前記複数のデータを第３のブロックに書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップをさらに含み、
前記実行時間が前記タイムアウト期間を越える場合、前記複数の有効なデータの一部分がコピーされかつ前記複数のデータが前記第３のブロックに書き込まれる方法。
【請求項７】
請求項３記載の方法において、
前記不揮発性メモリ記憶システムは複数のバッファリングレベルを含み、前記第３のブロックは前記複数のバッファリングレベルのうちの１つに関連付けられる方法。
【請求項８】
請求項３記載の方法において、
前記複数のデータを書き込むステップは、
前記複数のデータをスクラッチパッドブロックに書き込むステップと、
前記複数のデータを前記スクラッチパッドブロックから前記第３のブロックにコピーするステップと、
を含む方法。
【請求項９】
請求項８記載の方法において、
前記複数のデータは、前記スクラッチパッドブロックに関連付けられたセクタにコピーされる方法。
【請求項１０】
請求項８記載の方法において、
前記複数のデータは、前記スクラッチパッドブロックに関連付けられた、前記複数のデータを含むように構成されたページが満杯であるときに、前記スクラッチパッドブロックから前記第３のブロックにコピーされる方法。
【請求項１１】
請求項８記載の方法において、
前記スクラッチパッドブロックは第１のバッファレベルに関連付けられ、前記第３のブロックは第２のバッファレベルに関連付けられる方法。
【請求項１２】
請求項３記載の方法において、
前記複数のデータを書き込むステップは、
前記複数のデータを第１のバッファレベルに書き込むステップと、
前記複数のデータを前記第１のバッファレベルから前記第３のブロックにコピーするステップであって、前記第３のブロックが第２のバッファレベルに関連付けられるステップと、
を含む方法。
【請求項１３】
請求項３記載の方法において、
前記ガーベッジコレクション期間は、前記タイムアウト期間と前記複数のデータを書き込むステップに関連付けられたプログラミング時間との差である方法。
【請求項１４】
請求項３記載の方法において、
前記第３のブロックは、書き込みバッファブロックである方法。
【請求項１５】
請求項３記載の方法において、
前記第３のブロックは、論理アドレス空間全体にわたって広がるように構成される方法。
【請求項１６】
請求項３記載の方法において、
前記第３のブロックは複数のページを含み、前記複数のページの各々は索引付けされる方法。
【請求項１７】
請求項３記載の方法において、
前記第３のブロックは複数のセクタを含み、前記複数のセクタの各々は索引付けされる方法。
【請求項１８】
請求項３記載の方法において、
前記書き込みコマンドは、シングルセクタ書き込みコマンドである方法。
【請求項１９】
不揮発性メモリ記憶システムを動作させる方法であって、
第１の複数のデータを書き込む第１のシングルセクタ書き込みコマンドを受け取るステップであって、前記第１のシングルセクタ書き込みコマンドが前記第１のシングルセクタ書き込みコマンドの第１の実行を完了させるための第１のタイムアウト期間を割り当てられるステップと、
第１のビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの第１の部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックに前記第１の複数のデータを書き込むステップと、
前記第１のタイムアウト期間の前に前記第１のビジー信号を解除するステップと、
第２の複数のデータを書き込む第２のシングルセクタ書き込みコマンドを受け取るステップであって、前記第２のシングルセクタ書き込みコマンドが前記第１のシングルセクタ書き込みコマンドを受け取るステップの後に受け取られ、前記第２のシングルセクタ書き込みコマンドが前記第２のシングルセクタ書き込みコマンドの第２の実行を完了させるための第２のタイムアウト期間を割り当てられるステップと、
第２のビジー信号をアサートするステップと、
前記ガーベッジコレクション期間の間に前記複数の有効なデータの第２の部分を前記１つ以上の第１のブロックから前記第２のブロックにコピーするステップと、
前記第２のタイムアウト期間の前に前記第２のビジー信号を解除するステップと、
を含む方法。
【請求項２０】
請求項１９記載の方法において、
前記第２の複数のデータを前記書き込みバッファブロックに書き込むステップをさらに含む方法。
【請求項２１】
請求項１９記載の方法において、
前記第２の複数のデータを更新ブロックに書き込むステップをさらに含む方法。
【請求項２２】
請求項１９記載の方法において、
前記複数の有効なデータの前記第２の部分をコピーするステップの後に前記１つ以上の第１のブロックを消去するステップをさらに含む方法。
【請求項２３】
請求項２２記載の方法において、
前記複数の有効なデータの前記第２の部分が前記複数の有効なデータの最後の部分である場合、前記１つ以上の第１のブロックは消去される方法。
【請求項２４】
請求項１９記載の方法において、
前記第１の複数のデータを前記書き込みバッファブロックから更新ブロックにコピーするステップをさらに含む方法。
【請求項２５】
請求項１９記載の方法において、
前記第１の複数のデータを前記書き込みバッファブロックに書き込むステップは、
前記第１の複数のデータをスクラッチパッドブロックのセクタに書き込むステップであって、前記セクタに関連付けられたページが複数のセクタを含むステップと、
前記ページに関連付けられた前記複数のセクタが満たされたときに前記ページを前記書き込みバッファブロックにコピーするステップと、
を含む方法。
【請求項２６】
請求項１９記載の方法において、
前記書き込みバッファブロックは、セクタレベル索引のために構成される方法。
【請求項２７】
請求項１９記載の方法において、
前記書き込みバッファブロックは、ページ境界索引のために構成される方法。
【請求項２８】
請求項１９記載の方法において、
前記書き込みバッファブロックは複数のセクタと複数のオーバーヘッドセクタとを含み、前記複数のセクタは前記不揮発性メモリ記憶システム内のメタブロックの総数より大きい方法。
【請求項２９】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成されたメモリと、
バッファを維持するように構成された不揮発性メモリセルアレイと、
前記メモリおよび前記不揮発性メモリセルアレイと通信するプロセッサであって、前記メモリに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
複数のデータを前記不揮発性メモリセルアレイに書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
前記タイムアウト期間内にガーベッジコレクション動作の一部分を実行するステップと、
前記複数のデータを前記バッファに格納するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項３０】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成されたメモリと、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックを維持するように構成された不揮発性メモリセルアレイと、
前記メモリおよび前記不揮発性メモリセルアレイと通信するプロセッサであって、前記メモリに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
複数のデータを前記不揮発性メモリセルアレイに書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間にガーベッジコレクション動作の一部分を実行するステップと、
前記複数のデータを前記書き込みバッファブロックに書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項３１】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記ガーベッジコレクション期間の間にガーベッジコレクション動作の一部分を実行するステップを実行するための前記プログラム命令は、前記ガーベッジコレクション期間の間に複数の有効なデータの部分を１つ以上の第１のブロックから第２のブロックにコピーするステップを実行するためのプログラム命令を含む方法。
【請求項３２】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、
前記ガーベッジコレクション動作の一部分を実行するステップおよび前記複数のデータを前記書き込みバッファブロックに書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップを実行するためのプログラム命令をさらに含み、
前記実行時間が前記タイムアウト期間より大きければ、前記ガーベッジコレクション動作の一部分が実行されかつ前記複数のデータが前記書き込みバッファブロックに書き込まれる方法。
【請求項３３】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記複数のデータを前記書き込みバッファブロックに書き込むステップを実行するための前記プログラム命令は、
前記複数のデータをスクラッチパッドブロックに書き込むステップと、
前記複数のデータを前記スクラッチパッドブロックから前記書き込みバッファブロックにコピーするステップと、を実行するためのプログラム命令を含む方法。
【請求項３４】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のページを含み、前記複数のページの各々は索引付けされる方法。
【請求項３５】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のセクタを含み、前記複数のセクタの各々は索引付けされる方法。
【請求項３６】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、複数のブロックを含む方法。
【請求項３７】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成された読み出し専用メモリ（ＲＯＭ）と、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックを維持するように構成されたメモリセルアレイと、
不揮発性メモリセルアレイと、
前記ＲＯＭ、前記メモリセルアレイ、および前記不揮発性メモリセルアレイと通信するプロセッサであって、前記ＲＯＭに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
第１の複数のデータを前記不揮発性メモリセルアレイに書き込む第１の書き込みコマンドを受け取るステップであって、前記第１の書き込みコマンドは前記第１の書き込みコマンドの第１の実行を完了させるための第１のタイムアウト期間を割り当てられるステップと、
第１のビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの第１の部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
前記第１の複数のデータを前記書き込みバッファブロックに書き込むステップと、
前記第１のタイムアウト期間の前に前記第１のビジー信号を解除するステップと、
第２の複数のデータを前記不揮発性メモリセルアレイに書き込む第２の書き込みコマンドを受け取るステップであって、前記第２の書き込みコマンドは前記第１の書き込みコマンドを受け取るステップの後に受け取られ、かつ前記第２の書き込みコマンドの第２の実行を完了させるための第２のタイムアウト期間を割り当てられるステップと、
第２のビジー信号をアサートするステップと、
前記ガーベッジコレクション期間の間に前記複数の有効なデータの第２の部分を前記１つ以上の第１のブロックから前記第２のブロックにコピーするステップと、
前記第２のタイムアウト期間の前に前記第２のビジー信号を解除するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項３８】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記第２の複数のデータを前記書き込みバッファブロックに書き込むステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項３９】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記第２の複数のデータを更新ブロックに書き込むステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項４０】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記複数の有効なデータの前記第２の部分が前記複数の有効なデータの最後の部分である場合、前記１つ以上の第１のブロックを消去するステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項４１】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記第１の複数のデータを前記書き込みバッファブロックから更新ブロックにコピーするステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項４２】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のページを含み、前記第１の複数のデータは前記書き込みバッファブロックに関連付けられた第１のページに書き込まれ、前記第２の複数のデータは前記書き込みバッファブロックに関連付けられた第２のページに書き込まれる不揮発性メモリ記憶システム。
【請求項４３】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のセクタを含み、前記第１の複数のデータは前記書き込みバッファブロックに関連付けられた第１のセクタに書き込まれ、前記第２の複数のデータは前記書き込みバッファブロックに関連付けられた第２のセクタに書き込まれる不揮発性メモリ記憶システム。
【請求項４４】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記不揮発性メモリ記憶システムは複数のバッファリングレベルを含み、前記書き込みバッファブロックは前記複数のバッファリングレベルの１つに関連付けられる不揮発性メモリ記憶システム。
【請求項４５】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記第１の複数のデータを前記書き込みバッファブロックに書き込むステップを実行するための前記プログラム命令は、
前記第１の複数のデータをスクラッチパッドブロックのセクタに書き込むステップであって、前記セクタに関連付けられたページが複数のセクタを含むステップと、
前記ページに関連付けられた前記複数のセクタが満たされたときに前記ページを前記書き込みバッファブロックにコピーするステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項４６】
請求項４５記載の不揮発性メモリ記憶システムにおいて、
前記スクラッチパッドブロックは第１のバッファレベルに関連付けられ、前記書き込みバッファブロックは第２のバッファレベルに関連付けられる不揮発性メモリ記憶システム。
【請求項４７】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記複数のデータを書き込むステップを実行するための前記プログラム命令は、
前記複数のデータを第１のバッファレベルに書き込むステップと、
前記複数のデータを前記第１のバッファレベルから前記書き込みバッファブロックにコピーするステップであって、前記書き込みバッファブロックが第２のバッファレベルに関連付けられるステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項４８】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成されたメモリと、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックを維持するように構成された不揮発性メモリセルアレイと、
前記メモリおよび前記不揮発性メモリセルアレイと通信するプロセッサであって、前記メモリに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
複数のデータを前記不揮発性メモリセルアレイに書き込む書き込みコマンドを受け取るステップであって、前記不揮発性メモリセルアレイが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
前記複数のデータを前記書き込みバッファブロックに書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項４９】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記複数の有効なデータの一部分をコピーするステップを実行するための前記プログラム命令は、
前記複数の有効なデータの一部分を前記１つ以上の第１のブロックから前記第２のブロックにコピーするための時間を追跡するステップと、
前記時間が前記ガーベッジコレクション期間を超える前に前記複数の有効なデータの一部分をコピーするステップを止めるステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項５０】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、
前記複数の有効なデータをコピーするステップおよび前記複数のデータを書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップを実行するためのプログラム命令をさらに含み、
前記実行時間が前記タイムアウト期間を越える場合、前記複数の有効なデータの一部分がコピーされかつ前記複数のデータが前記書き込みバッファブロックに書き込まれる不揮発性メモリ記憶システム。
【請求項５１】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記複数のデータの一部分を書き込むステップを実行するための前記プログラム命令は、
複数のセクタを含むページを含むスクラッチパッドブロックを提供するステップと、
前記複数のデータを前記ページに関連付けられているセクタに書き込むステップと、
前記ページが満杯であるときに前記ページを前記スクラッチパッドブロックから前記書き込みバッファブロックにコピーするステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項５２】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記ガーベッジコレクション期間は、前記タイムアウト期間と前記複数のデータを書き込むステップに関連付けられたプログラミング時間との差である不揮発性メモリ記憶システム。
【請求項５３】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、論理アドレス空間全体にわたって広がるように構成される不揮発性メモリ記憶システム。
【請求項５４】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、セクタレベル索引のために構成される不揮発性メモリ記憶システム。
【請求項５５】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、ページ境界索引のために構成される不揮発性メモリ記憶システム。
【請求項５６】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは複数のセクタを前記書き込みバッファブロックに割り当てるステップを実行するためのプログラム命令をさらに含み、前記複数のセクタは前記不揮発性メモリ記憶システム内のメタブロックの総数より大きい不揮発性メモリ記憶システム。
【請求項１】
不揮発性メモリ記憶システムを動作させる方法であって、
複数のデータを書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
前記タイムアウト期間内にガーベッジコレクション動作の一部分を実行するステップと、
前記複数のデータを前記不揮発性メモリ記憶システムに関連付けられているバッファに格納するステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記バッファは、書き込みバッファブロックである方法。
【請求項３】
不揮発性メモリ記憶システムを動作させる方法であって、
複数のデータを書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
複数の論理アドレスにわたって広がるように構成された第３のブロックに前記複数のデータを書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、
を含む方法。
【請求項４】
請求項３記載の方法において、
前記不揮発性メモリ記憶システムにおいて前記第３のブロックを維持するステップをさらに含む方法。
【請求項５】
請求項３記載の方法において、
前記複数の有効なデータの一部分をコピーするステップは、
前記複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップのための時間を追跡するステップと、
前記時間が前記ガーベッジコレクション期間を超える前に前記複数の有効なデータの一部分をコピーするステップを止めるステップと、
を含む方法。
【請求項６】
請求項３記載の方法において、
前記複数の有効なデータの一部分をコピーするステップおよび前記複数のデータを第３のブロックに書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップをさらに含み、
前記実行時間が前記タイムアウト期間を越える場合、前記複数の有効なデータの一部分がコピーされかつ前記複数のデータが前記第３のブロックに書き込まれる方法。
【請求項７】
請求項３記載の方法において、
前記不揮発性メモリ記憶システムは複数のバッファリングレベルを含み、前記第３のブロックは前記複数のバッファリングレベルのうちの１つに関連付けられる方法。
【請求項８】
請求項３記載の方法において、
前記複数のデータを書き込むステップは、
前記複数のデータをスクラッチパッドブロックに書き込むステップと、
前記複数のデータを前記スクラッチパッドブロックから前記第３のブロックにコピーするステップと、
を含む方法。
【請求項９】
請求項８記載の方法において、
前記複数のデータは、前記スクラッチパッドブロックに関連付けられたセクタにコピーされる方法。
【請求項１０】
請求項８記載の方法において、
前記複数のデータは、前記スクラッチパッドブロックに関連付けられた、前記複数のデータを含むように構成されたページが満杯であるときに、前記スクラッチパッドブロックから前記第３のブロックにコピーされる方法。
【請求項１１】
請求項８記載の方法において、
前記スクラッチパッドブロックは第１のバッファレベルに関連付けられ、前記第３のブロックは第２のバッファレベルに関連付けられる方法。
【請求項１２】
請求項３記載の方法において、
前記複数のデータを書き込むステップは、
前記複数のデータを第１のバッファレベルに書き込むステップと、
前記複数のデータを前記第１のバッファレベルから前記第３のブロックにコピーするステップであって、前記第３のブロックが第２のバッファレベルに関連付けられるステップと、
を含む方法。
【請求項１３】
請求項３記載の方法において、
前記ガーベッジコレクション期間は、前記タイムアウト期間と前記複数のデータを書き込むステップに関連付けられたプログラミング時間との差である方法。
【請求項１４】
請求項３記載の方法において、
前記第３のブロックは、書き込みバッファブロックである方法。
【請求項１５】
請求項３記載の方法において、
前記第３のブロックは、論理アドレス空間全体にわたって広がるように構成される方法。
【請求項１６】
請求項３記載の方法において、
前記第３のブロックは複数のページを含み、前記複数のページの各々は索引付けされる方法。
【請求項１７】
請求項３記載の方法において、
前記第３のブロックは複数のセクタを含み、前記複数のセクタの各々は索引付けされる方法。
【請求項１８】
請求項３記載の方法において、
前記書き込みコマンドは、シングルセクタ書き込みコマンドである方法。
【請求項１９】
不揮発性メモリ記憶システムを動作させる方法であって、
第１の複数のデータを書き込む第１のシングルセクタ書き込みコマンドを受け取るステップであって、前記第１のシングルセクタ書き込みコマンドが前記第１のシングルセクタ書き込みコマンドの第１の実行を完了させるための第１のタイムアウト期間を割り当てられるステップと、
第１のビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの第１の部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックに前記第１の複数のデータを書き込むステップと、
前記第１のタイムアウト期間の前に前記第１のビジー信号を解除するステップと、
第２の複数のデータを書き込む第２のシングルセクタ書き込みコマンドを受け取るステップであって、前記第２のシングルセクタ書き込みコマンドが前記第１のシングルセクタ書き込みコマンドを受け取るステップの後に受け取られ、前記第２のシングルセクタ書き込みコマンドが前記第２のシングルセクタ書き込みコマンドの第２の実行を完了させるための第２のタイムアウト期間を割り当てられるステップと、
第２のビジー信号をアサートするステップと、
前記ガーベッジコレクション期間の間に前記複数の有効なデータの第２の部分を前記１つ以上の第１のブロックから前記第２のブロックにコピーするステップと、
前記第２のタイムアウト期間の前に前記第２のビジー信号を解除するステップと、
を含む方法。
【請求項２０】
請求項１９記載の方法において、
前記第２の複数のデータを前記書き込みバッファブロックに書き込むステップをさらに含む方法。
【請求項２１】
請求項１９記載の方法において、
前記第２の複数のデータを更新ブロックに書き込むステップをさらに含む方法。
【請求項２２】
請求項１９記載の方法において、
前記複数の有効なデータの前記第２の部分をコピーするステップの後に前記１つ以上の第１のブロックを消去するステップをさらに含む方法。
【請求項２３】
請求項２２記載の方法において、
前記複数の有効なデータの前記第２の部分が前記複数の有効なデータの最後の部分である場合、前記１つ以上の第１のブロックは消去される方法。
【請求項２４】
請求項１９記載の方法において、
前記第１の複数のデータを前記書き込みバッファブロックから更新ブロックにコピーするステップをさらに含む方法。
【請求項２５】
請求項１９記載の方法において、
前記第１の複数のデータを前記書き込みバッファブロックに書き込むステップは、
前記第１の複数のデータをスクラッチパッドブロックのセクタに書き込むステップであって、前記セクタに関連付けられたページが複数のセクタを含むステップと、
前記ページに関連付けられた前記複数のセクタが満たされたときに前記ページを前記書き込みバッファブロックにコピーするステップと、
を含む方法。
【請求項２６】
請求項１９記載の方法において、
前記書き込みバッファブロックは、セクタレベル索引のために構成される方法。
【請求項２７】
請求項１９記載の方法において、
前記書き込みバッファブロックは、ページ境界索引のために構成される方法。
【請求項２８】
請求項１９記載の方法において、
前記書き込みバッファブロックは複数のセクタと複数のオーバーヘッドセクタとを含み、前記複数のセクタは前記不揮発性メモリ記憶システム内のメタブロックの総数より大きい方法。
【請求項２９】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成されたメモリと、
バッファを維持するように構成された不揮発性メモリセルアレイと、
前記メモリおよび前記不揮発性メモリセルアレイと通信するプロセッサであって、前記メモリに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
複数のデータを前記不揮発性メモリセルアレイに書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
前記タイムアウト期間内にガーベッジコレクション動作の一部分を実行するステップと、
前記複数のデータを前記バッファに格納するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項３０】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成されたメモリと、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックを維持するように構成された不揮発性メモリセルアレイと、
前記メモリおよび前記不揮発性メモリセルアレイと通信するプロセッサであって、前記メモリに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
複数のデータを前記不揮発性メモリセルアレイに書き込む書き込みコマンドを受け取るステップであって、前記書き込みコマンドが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間にガーベッジコレクション動作の一部分を実行するステップと、
前記複数のデータを前記書き込みバッファブロックに書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項３１】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記ガーベッジコレクション期間の間にガーベッジコレクション動作の一部分を実行するステップを実行するための前記プログラム命令は、前記ガーベッジコレクション期間の間に複数の有効なデータの部分を１つ以上の第１のブロックから第２のブロックにコピーするステップを実行するためのプログラム命令を含む方法。
【請求項３２】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、
前記ガーベッジコレクション動作の一部分を実行するステップおよび前記複数のデータを前記書き込みバッファブロックに書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップを実行するためのプログラム命令をさらに含み、
前記実行時間が前記タイムアウト期間より大きければ、前記ガーベッジコレクション動作の一部分が実行されかつ前記複数のデータが前記書き込みバッファブロックに書き込まれる方法。
【請求項３３】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記複数のデータを前記書き込みバッファブロックに書き込むステップを実行するための前記プログラム命令は、
前記複数のデータをスクラッチパッドブロックに書き込むステップと、
前記複数のデータを前記スクラッチパッドブロックから前記書き込みバッファブロックにコピーするステップと、を実行するためのプログラム命令を含む方法。
【請求項３４】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のページを含み、前記複数のページの各々は索引付けされる方法。
【請求項３５】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のセクタを含み、前記複数のセクタの各々は索引付けされる方法。
【請求項３６】
請求項３０記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、複数のブロックを含む方法。
【請求項３７】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成された読み出し専用メモリ（ＲＯＭ）と、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックを維持するように構成されたメモリセルアレイと、
不揮発性メモリセルアレイと、
前記ＲＯＭ、前記メモリセルアレイ、および前記不揮発性メモリセルアレイと通信するプロセッサであって、前記ＲＯＭに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
第１の複数のデータを前記不揮発性メモリセルアレイに書き込む第１の書き込みコマンドを受け取るステップであって、前記第１の書き込みコマンドは前記第１の書き込みコマンドの第１の実行を完了させるための第１のタイムアウト期間を割り当てられるステップと、
第１のビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの第１の部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
前記第１の複数のデータを前記書き込みバッファブロックに書き込むステップと、
前記第１のタイムアウト期間の前に前記第１のビジー信号を解除するステップと、
第２の複数のデータを前記不揮発性メモリセルアレイに書き込む第２の書き込みコマンドを受け取るステップであって、前記第２の書き込みコマンドは前記第１の書き込みコマンドを受け取るステップの後に受け取られ、かつ前記第２の書き込みコマンドの第２の実行を完了させるための第２のタイムアウト期間を割り当てられるステップと、
第２のビジー信号をアサートするステップと、
前記ガーベッジコレクション期間の間に前記複数の有効なデータの第２の部分を前記１つ以上の第１のブロックから前記第２のブロックにコピーするステップと、
前記第２のタイムアウト期間の前に前記第２のビジー信号を解除するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項３８】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記第２の複数のデータを前記書き込みバッファブロックに書き込むステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項３９】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記第２の複数のデータを更新ブロックに書き込むステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項４０】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記複数の有効なデータの前記第２の部分が前記複数の有効なデータの最後の部分である場合、前記１つ以上の第１のブロックを消去するステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項４１】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、前記第１の複数のデータを前記書き込みバッファブロックから更新ブロックにコピーするステップを実行するためのプログラム命令をさらに含む不揮発性メモリ記憶システム。
【請求項４２】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のページを含み、前記第１の複数のデータは前記書き込みバッファブロックに関連付けられた第１のページに書き込まれ、前記第２の複数のデータは前記書き込みバッファブロックに関連付けられた第２のページに書き込まれる不揮発性メモリ記憶システム。
【請求項４３】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは複数のセクタを含み、前記第１の複数のデータは前記書き込みバッファブロックに関連付けられた第１のセクタに書き込まれ、前記第２の複数のデータは前記書き込みバッファブロックに関連付けられた第２のセクタに書き込まれる不揮発性メモリ記憶システム。
【請求項４４】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記不揮発性メモリ記憶システムは複数のバッファリングレベルを含み、前記書き込みバッファブロックは前記複数のバッファリングレベルの１つに関連付けられる不揮発性メモリ記憶システム。
【請求項４５】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記第１の複数のデータを前記書き込みバッファブロックに書き込むステップを実行するための前記プログラム命令は、
前記第１の複数のデータをスクラッチパッドブロックのセクタに書き込むステップであって、前記セクタに関連付けられたページが複数のセクタを含むステップと、
前記ページに関連付けられた前記複数のセクタが満たされたときに前記ページを前記書き込みバッファブロックにコピーするステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項４６】
請求項４５記載の不揮発性メモリ記憶システムにおいて、
前記スクラッチパッドブロックは第１のバッファレベルに関連付けられ、前記書き込みバッファブロックは第２のバッファレベルに関連付けられる不揮発性メモリ記憶システム。
【請求項４７】
請求項３７記載の不揮発性メモリ記憶システムにおいて、
前記複数のデータを書き込むステップを実行するための前記プログラム命令は、
前記複数のデータを第１のバッファレベルに書き込むステップと、
前記複数のデータを前記第１のバッファレベルから前記書き込みバッファブロックにコピーするステップであって、前記書き込みバッファブロックが第２のバッファレベルに関連付けられるステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項４８】
不揮発性メモリ記憶システムであって、
記憶システムファームウェアを記憶するように構成されたメモリと、
複数の論理アドレスにわたって広がるように構成された書き込みバッファブロックを維持するように構成された不揮発性メモリセルアレイと、
前記メモリおよび前記不揮発性メモリセルアレイと通信するプロセッサであって、前記メモリに格納されている前記記憶システムファームウェアを実行するように構成されたプロセッサと、を備え、
前記記憶システムファームウェアは、
複数のデータを前記不揮発性メモリセルアレイに書き込む書き込みコマンドを受け取るステップであって、前記不揮発性メモリセルアレイが前記書き込みコマンドの実行を完了させるためのタイムアウト期間を割り当てられるステップと、
ビジー信号をアサートするステップと、
ガーベッジコレクション期間の間に複数の有効なデータの一部分を１つ以上の第１のブロックから第２のブロックにコピーするステップと、
前記複数のデータを前記書き込みバッファブロックに書き込むステップと、
前記タイムアウト期間の前に前記ビジー信号を解除するステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項４９】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記複数の有効なデータの一部分をコピーするステップを実行するための前記プログラム命令は、
前記複数の有効なデータの一部分を前記１つ以上の第１のブロックから前記第２のブロックにコピーするための時間を追跡するステップと、
前記時間が前記ガーベッジコレクション期間を超える前に前記複数の有効なデータの一部分をコピーするステップを止めるステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項５０】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは、
前記複数の有効なデータをコピーするステップおよび前記複数のデータを書き込むステップの前に前記書き込みコマンドの実行のための実行時間を推定するステップを実行するためのプログラム命令をさらに含み、
前記実行時間が前記タイムアウト期間を越える場合、前記複数の有効なデータの一部分がコピーされかつ前記複数のデータが前記書き込みバッファブロックに書き込まれる不揮発性メモリ記憶システム。
【請求項５１】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記複数のデータの一部分を書き込むステップを実行するための前記プログラム命令は、
複数のセクタを含むページを含むスクラッチパッドブロックを提供するステップと、
前記複数のデータを前記ページに関連付けられているセクタに書き込むステップと、
前記ページが満杯であるときに前記ページを前記スクラッチパッドブロックから前記書き込みバッファブロックにコピーするステップと、を実行するためのプログラム命令を含む不揮発性メモリ記憶システム。
【請求項５２】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記ガーベッジコレクション期間は、前記タイムアウト期間と前記複数のデータを書き込むステップに関連付けられたプログラミング時間との差である不揮発性メモリ記憶システム。
【請求項５３】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、論理アドレス空間全体にわたって広がるように構成される不揮発性メモリ記憶システム。
【請求項５４】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、セクタレベル索引のために構成される不揮発性メモリ記憶システム。
【請求項５５】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記書き込みバッファブロックは、ページ境界索引のために構成される不揮発性メモリ記憶システム。
【請求項５６】
請求項４８記載の不揮発性メモリ記憶システムにおいて、
前記記憶システムファームウェアは複数のセクタを前記書き込みバッファブロックに割り当てるステップを実行するためのプログラム命令をさらに含み、前記複数のセクタは前記不揮発性メモリ記憶システム内のメタブロックの総数より大きい不揮発性メモリ記憶システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１０Ｄ】
【図１０Ｅ】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図１０Ａ】
【図１０Ｂ】
【図１０Ｃ】
【図１０Ｄ】
【図１０Ｅ】
【図１１】
【図１２】
【図１３】
【図１４】
【公表番号】特表２００９−５４５８１９（Ｐ２００９−５４５８１９Ａ）
【公表日】平成２１年１２月２４日（２００９．１２．２４）
【国際特許分類】
【出願番号】特願２００９−５２２９３４（Ｐ２００９−５２２９３４）
【出願日】平成１９年７月１９日（２００７．７．１９）
【特許番号】特許第４３６２５４９号（Ｐ４３６２５４９）
【特許公報発行日】平成２１年１１月１１日（２００９．１１．１１）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７３８９１
【国際公開番号】ＷＯ２００８／０１９２１８
【国際公開日】平成２０年２月１４日（２００８．２．１４）
【出願人】（５０６１９７９０１）サンディスク コーポレイション (175)
【Ｆターム（参考）】
【公表日】平成２１年１２月２４日（２００９．１２．２４）
【国際特許分類】
【出願日】平成１９年７月１９日（２００７．７．１９）
【特許番号】特許第４３６２５４９号（Ｐ４３６２５４９）
【特許公報発行日】平成２１年１１月１１日（２００９．１１．１１）
【国際出願番号】ＰＣＴ／ＵＳ２００７／０７３８９１
【国際公開番号】ＷＯ２００８／０１９２１８
【国際公開日】平成２０年２月１４日（２００８．２．１４）
【出願人】（５０６１９７９０１）サンディスク コーポレイション (175)
【Ｆターム（参考）】
[ Back to top ]