(57)【要約】  各ファイルの一意の識別名およびファイル内のデータのオフセットを用いるが、メモリの中間論理アドレスまたは仮想アドレス空間のいずれも用いることなく、大容量の消去ブロックのフラッシュメモリシステムに直接ホストシステムのデータファイルの書き込みを行う。メモリのどこにファイルがあるかに関するディレクトリ情報を、ホストではなく、メモリシステムのコントローラが、メモリシステムに保持する。各データファイルを、ファイルディレクトリに一意に識別し、このディレクトリ情報が、ファイルを構成するデータグループのファイルインデックステーブル（ＦＩＴ）内のエントリと、メモリ内のそれらの物理記憶位置を指す。
2009503740.tif 000002
【特許請求の範囲】
【請求項１】
メモリシステムの外部から受け取ったファイルのデータで再プログラミングを行う前に消去が行われるメモリセルブロックにグループ化した記憶セルを有する、不揮発性メモリシステムの動作方法であって、
前記メモリブロックに、一意のファイル識別子を有するファイルのデータを記憶するステップと、
個別のファイルに対し、前記個別のファイルのデータの前記物理ブロックの位置のレコードを保持するステップと、
分類（１）近い将来修正を行う可能性がある、または分類（２）近い将来修正を行う可能性がない、のうちのいずれかとして、前記個別のファイルの分類を保持するステップと、
一意のファイル識別子により、（１）と分類されたファイルのレコードへの間接リンクと、（２）と分類されたファイルのレコードへの直接リンクとである、前記ファイルのレコードへのリンクのディレクトリを保持するステップと、
一意のファイル識別子を用いることにより、前記ディレクトリを介して前記レコードのうちの選択した１つにアクセスするステップと、
を含む方法。
【請求項２】
請求項１記載の方法において、
前記メモリシステムに接続しているホストシステムが前記個別のファイルを開くと指定する分類（１）にファイルを保持し、前記メモリシステムに接続しているホストシステムが前記個別のファイルを閉じると指定する分類（２）にファイルを保持する方法。
【請求項３】
請求項１記載の方法において、
前記メモリシステムに接続しているホストからの少なくとも１つの前記メモリブロック内へのファイルデータの書き込みに応答して、前記メモリシステムが前記ファイル分類を保持する方法。
【請求項４】
請求項１記載の方法において、
ファイルの前記間接リンクは、エントリを前記ファイル変更の前記レコードを含んでいる第２の位置として変更を行わない前記メモリ内の第１の位置のアドレスの前記ディレクトリに含んでいて、前記第１の位置は変更のある前記第２の位置のアドレスを含んでいて、ファイルの前記直接リンクは、エントリを前記第２の位置のアドレスの前記ディレクトリに含んでいる方法。
【請求項５】
請求項１記載の方法において、
（１）と分類されたファイルのレコードを他のファイルのレコードがない前記メモリブロック内の個別のページに保持し、（２）と分類されたファイルの複数のレコードを前記メモリブロック内の個別のページに保持する方法。
【請求項６】
請求項１記載の方法において、
（２）と分類されたファイルの多数のレコードを前記メモリブロックの第１のページにともにグループ化し、それらの数のレコードへの多数のリンクを、前記ディレクトリを構成する前記メモリブロックの第２のページにともにグループ化する方法。
【請求項７】
請求項６記載の方法において、
前記第１のページに記憶してある（２）と分類されたファイルのレコードの数を、そのリンクを前記第２のページに記憶してあるファイルに制限する方法。
【請求項８】
一意のファイル識別子が識別したファイルのデータで再プログラミングを行う前に消去が行われるメモリセルブロックにグループ化した記憶セルを有する、不揮発性メモリシステムの動作方法であって、
個別のファイルのデータを１つ以上のデータグループとして記憶するステップと、
前記ファイルのデータそれぞれのものを構成する前記データグループのレコードを保持するステップと、
前記一意のファイル識別子により、非アクティブファイルへの直接リンクと、アクティブファイルへの間接リンクとである、前記レコードへのリンクのディレクトリを保持するステップと、
を含む方法。
【請求項９】
請求項８記載の方法において、
アクティブファイルは近い将来それらの修正を行う可能性があり、非アクティブファイルは近い将来それらの修正を行う可能性がない方法。
【請求項１０】
請求項８記載の方法において、
アクティブファイルは、前記メモリシステムに接続しているホストが開いていると指定したファイルを含み、非アクティブファイルは、前記ホストが閉じていると指定したファイルを含んでいる方法。
【請求項１１】
請求項８記載の方法において、
前記メモリシステムは、前記メモリブロック内の前記ファイルの記憶の少なくとも１つのパターンを監視することにより、前記個別のファイルがアクティブまたは非アクティブであると識別を行う方法。
【請求項１２】
請求項８記載の方法において、
前記１つ以上のデータグループは、メモリセルブロック内の連続する論理ファイルオフセットアドレスおよび連続する物理アドレスにデータを含んでいる方法。
【請求項１３】
請求項８記載の方法において、
アクティブファイルのレコードを、他のファイルのレコードがない前記メモリブロック内の個別のページに保持し、非アクティブファイルの複数のレコードを、前記メモリブロック内の個別のページに保持する方法。
【請求項１４】
請求項８記載の方法において、
非アクティブファイルの多数のレコードを前記メモリブロックの第１のページにともにグループ化し、それらの数のレコードへの多数のリンクを、前記ディレクトリを構成する前記メモリブロックの第２のページにともにグループ化する方法。
【請求項１５】
ファイル内の一意のファイル識別子およびオフセットアドレスが識別したデータで、ブロックのページの再プログラミングを行う前に消去が行われるメモリセルブロックにグループ化した記憶セルを有する、不揮発性メモリシステムの動作方法であって、
個別のファイルのデータを、メモリセルブロック内の連続する論理ファイルオフセットアドレスおよび連続する物理アドレス内のデータを個別に指定する、１つ以上のデータグループとして記憶するステップと、
前記個別のファイルの前記データグループの表にエントリのセットを保持するステップと、
ファイルの一意の識別子により、閉じているファイルのデータへの直接リンクと、開いているファイルのデータへの間接リンクとである、前記ファイルのデータの前記表内のエントリに前記ファイルをリンクするファイルディレクトリを保持するステップと、
を含む方法。
【請求項１６】
請求項１５記載の方法において、
開いているファイルの表を、他のファイルの表を含まない前記メモリブロック内の個別のページに保持し、閉じられているファイルの複数のレコードを、前記メモリブロック内の個別のページに保持する方法。
【請求項１７】
請求項１５記載の方法において、
閉じられているファイルの多数のレコードを前記メモリブロックの第１のページにともにグループ化し、それらの数のレコードへの多数のリンクを、前記ディレクトリを構成する前記メモリブロックの第２のページにともにグループ化する方法。
【請求項１８】
ブロックのページ内のデータの再プログラミングを行う前に消去が行われるメモリセルブロックにグループ化した記憶セルを有する、不揮発性メモリシステムの動作方法であって、
第１の複数のページに、個別に一意のファイル識別子を有するファイルのデータを記憶するステップと、
少なくとも第２のページに、前記第１の複数のページに記憶している前記ファイルのデータの前記物理ページ位置のレコードを保持するステップと、
少なくとも第３のページに、少なくとも前記第２のページ内のレコードの前記位置を示すポインタを保持し、前記第２のページ内の前記レコードを、そのポインタを前記第３のページに記憶してある前記ファイルのものに制限するステップと、
を含む方法。
【請求項１９】
請求項１８記載の方法において、
少なくとも前記第２のページ内のレコードの位置を示すポインタが、前記レコードが関連する前記ファイルの一意の識別子に対応付けられている方法。
【請求項２０】
請求項１８記載の方法において、
前記第１の複数のページが、１つ以上のブロックの第１のグループに位置し、前記少なくとも第２のページが、１つ以上のブロックの第２のグループに位置し、前記少なくとも第３のページが、１つ以上のブロックの第３のグループに位置している方法。
【請求項２１】
請求項１８記載の方法において、
前記第１の複数のページが、１つ以上のブロックの第１のグループに位置し、前記少なくとも第２のページおよび前記少なくとも第３のページが、１つ以上のブロックの第２のグループの共有ブロックに位置している方法。
【請求項２２】
請求項１８記載の方法において、
前記第１の複数のページ、前記少なくとも第２のページおよび前記少なくとも第３のページが、１つ以上のブロックのグループの共有ブロックにともに位置している方法。
【請求項２３】
ブロックのページ内のデータの再プログラミングを行う前に消去が行われるメモリセルブロックにグループ化した記憶セルを有する、不揮発性メモリシステムの動作方法であって、
少なくとも第１のページに、データを記憶してある前記物理ページの位置のレコードを保持するステップと、
少なくとも第２のページに、少なくとも前記第１のページ内のレコードの前記位置を指すポインタを保持し、前記第１のページ内の前記レコードを前記第２のページに記憶してある前記ポインタが指すものに制限するステップと、
を含む方法。
【請求項２４】
ブロックのページ内のファイルのデータの再プログラミングを行う前に消去が行われるメモリセルブロックにグループ化した記憶セルを有する、不揮発性メモリシステムの動作方法であって、
前記メモリブロックに、一意のファイル識別子を有するファイルのデータを記憶するステップと、
個別のファイルに対し、前記個別のファイルのデータの前記物理ブロックの位置のレコードを保持するステップと、
一意のファイル識別子により、前記レコードの物理アドレスを含むメモリの１つ以上の位置へのリンクである、前記ファイルの前記レコードへのリンクのディレクトリを前記ディレクトリに保持するステップと、
一意のファイル識別子を用いることにより、前記ディレクトリを介して前記レコードのうちの選択した１つにアクセスし、個別のファイルのレコードを他のファイルのレコードがない個別のページに保持するステップと、
を含む方法。
【請求項２５】
データの再プログラミングを行う前にともに消去が行われるメモリセルブロックにグループ化した記憶セルを有する不揮発性メモリのメモリシステムであって、
前記メモリシステムの外部から受け取った一意のファイル識別子を有するファイルのデータを、それらのファイル識別子により、前記メモリブロックに記憶し、
データの前記物理ブロック位置のレコードを、前記個別のファイルに対し保持し、
分類（１）近い将来修正を行う可能性がある、または分類（２）近い将来修正を行う可能性がない、のうちのいずれかとして、前記個別のファイルの分類を保持し、
一意のファイル識別子により、（１）と分類されたファイルのレコードへの間接リンクと、（２）と分類されたファイルのレコードへの直接リンクとである、前記ファイルのレコードへのリンクのディレクトリを保持するメモリシステム。
【請求項２６】
請求項２５記載のメモリシステムにおいて、
さらに、前記メモリシステムに接続しているホストシステムが前記個別のファイルを開くと指定する分類（１）にファイルを保持し、前記メモリシステムに接続しているホストシステムが前記個別のファイルを閉じていると指定する分類（２）にファイルを保持するメモリシステム。
【請求項２７】
請求項２５記載のメモリシステムにおいて、
さらに、ファイルの前記間接リンクは、エントリを前記ファイル変更の前記レコードを含んでいる第２の位置として変更を行わない前記メモリ内の第１の位置のアドレスの前記ディレクトリに含んでいて、前記第１の位置は変更のある前記第２の位置のアドレスを含んでいて、ファイルの前記直接リンクは、エントリを前記第２の位置のアドレスの前記ディレクトリに含んでいるメモリシステム。
【請求項２８】
請求項２５記載のメモリシステムにおいて、
さらに、（１）と分類されたファイルのレコードを他のファイルのレコードがない前記メモリブロック内の個別のページに保持し、（２）と分類されたファイルの複数のレコードを前記メモリブロック内の個別のページに保持するメモリシステム。
【請求項２９】
請求項２５記載のメモリシステムにおいて、
さらに、（２）と分類されたファイルの多数のレコードを前記メモリブロックの第１のページにともにグループ化し、それらの数のレコードへの多数のリンクを、前記ディレクトリを構成する前記メモリブロックの第２のページにともにグループ化するメモリシステム。
【請求項３０】
請求項２９記載のメモリシステムにおいて、
さらに、前記第１のページに記憶してある（２）と分類されたファイルのレコードの数を、そのリンクを前記第２のページに記憶してあるファイルに制限するメモリシステム。
【請求項３１】
データのブロックのページへの再プログラミングを行う前にともに消去が行われるメモリセルブロックにグループ化した記憶セルを有する不揮発性メモリのメモリシステムであって、
第１の複数のページに記憶される一意のファイル識別子を個別に有するファイルのデータと、
少なくとも第２のページ内の前記一意に識別が行われたファイルのデータを保持している前記物理ページ位置のレコードと、
前記少なくとも第２のページ内のレコードの前記位置を示すポインタを、少なくとも第３のページに保持し、前記第２のページ内の前記レコードを、そのポインタを前記第３のページに記憶している前記ファイルのものに制限する、ポインタと、
を備えるメモリシステム。
【請求項３２】
請求項３１記載のメモリシステムにおいて、
さらに、前記第１の複数のページが、１つ以上のブロックの第１のグループに位置し、前記少なくとも第２のページが、１つ以上のブロックの第２のグループに位置し、前記少なくとも第３のページが、１つ以上のブロックの第３のグループに位置しているメモリシステム。
【請求項３３】
請求項３１記載のメモリシステムにおいて、
前記第１の複数のページが、１つ以上のブロックの第１のグループに位置し、前記少なくとも第２のページおよび前記少なくとも第３のページが、１つ以上のブロックの第２のグループの共有ブロックに位置しているメモリシステム。
【請求項３４】
請求項３１記載のメモリシステムにおいて、
前記第１の複数のページ、前記少なくとも第２のページおよび前記少なくとも第３のページが、１つ以上のブロックのグループの共有ブロックにともに位置しているメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、半導体フラッシュメモリなどの再プログラム可能な不揮発性メモリシステムの動作に関し、より具体的には、ホストデバイスとメモリとの間のインターフェイスを管理することに関する。
【０００２】
ホストシステム、メモリシステムおよび他の電子システムの外部インターフェイスを介して伝達したデータのアドレス指定を行う技術として、主に２つの技術がある。そのうちの１つは、システムが生成したり、または受信したりしたデータファイルのアドレスを、そのシステム用に設定した連続する論理アドレス空間の別個の範囲に対してマッピングを行うことである。通常、アドレス空間の広さは、システムが処理可能なアドレスの全域をカバーするのに十分な広さである。一例として、磁気ディスク記憶装置のドライブは、このような論理アドレス空間を介して、コンピュータまたは他のホストシステムと通信を行う。このアドレス空間の広さは、ディスクドライブの全データ記憶容量のアドレス指定を行うのに十分な広さである。２つの技術のうちの２つ目は、電子システムが生成したり、または受信したりしたデータファイルを一意に識別し、ファイル内で、オフセットにより理論的にそれらのデータのアドレス指定を行う。このアドレス指定方法の形式を、コンピュータまたは他のホストシステムと、“スマートカード”として周知の取り外し可能なメモリカードとの間で用いる。通常、顧客がスマートカードを利用して、顧客識別、バンキング、販売時点購入、ＡＴＭアクセス等を行う。
【０００３】
初期世代の市販のフラッシュメモリシステムでは、メモリセルの矩形アレイを、多数のグループのセルに分割していた。それぞれの記憶データ量は、標準ディスクドライブセクタ、すなわち、５１２バイトであった。通常、各グループは、１６バイトといった追加のデータ量をさらに含んで、誤り訂正符号（ＥＣＣ）と、ユーザデータおよび／または対応づけられたユーザデータを記憶するメモリセルグループに関する、考えられ得る他のオーバーヘッドデータとが記憶可能である。このようなグループそれぞれのメモリセルは、同時に消去可能な最小数のメモリセルである。すなわち、消去単位は、１つのデータセクタと、含まれる任意のオーバーヘッドデータとを記憶するのに効率的なメモリセルの数である。この種のメモリシステムの例が、米国特許第５，６０２，９８７号（特許文献１）および第６，４２６，８９３号（特許文献２）に記載されている。データで再プログラミングを行う前にメモリセルを消去することが、フラッシュメモリの特徴である。
【０００４】
フラッシュメモリシステムは、パーソナルコンピュータ、カメラ等の様々なホストに取り外し可能に接続する、メモリカードまたはフラッシュドライブの形で最も一般に提供されているものであるが、このようなホストシステムに埋め込まれている場合もある。データをメモリに書き込む際に、ホストは通常、一意の論理アドレスをメモリシステムの連続する仮想アドレス空間内のセクタ、クラスタまたは他のデータ単位に割り当てる。ディスクオペレーティングシステム（ＤＯＳ）のように、ホストは、メモリシステムの論理アドレス空間内のアドレスにデータを書き込んだり、またアドレスからデータを読み出したりする。メモリシステム内のコントローラは、ホストから受け取った論理アドレスを、メモリアレイ内の物理アドレスに変換する。実際に、データをここに記憶し、次に、これらのアドレス変換を常に把握しておく。メモリシステムのデータ記憶容量は少なくとも、メモリシステムに対し定義した全論理アドレス空間についてアドレス指定可能なデータ量と同じである。
【０００５】
次世代のフラッシュメモリシステムでは、消去単位の大きさは、多数のデータセクタを記憶するのに十分なメモリセルブロックに増加した。メモリシステムが接続しているホストシステムが、セクタなどの小さな最小単位でデータのプログラミングを行ったり、また読み出しを行ったとしても、フラッシュメモリの１つの消去単位に多数のセクタが記憶してある。ホストが論理データセクタを更新したり、または置換したりすると、普通は、ブロック内のいくつかのデータセクタは使われなくなることがある。ブロック内に記憶してある任意のデータを上書きする前に全ブロックを消去する必要があるので、通常、前に消去が行われたもののデータ記憶容量がまだ残っている別のブロックに、新しいデータまたは更新データを記憶する。この処理により、メモリ内部の貴重な空間を占有する使われなくなったデータのある、もともとのブロックを空けるようにする。しかし、内部に有効なデータが残っている場合、そのブロックを消去することはできない。
【０００６】
従って、メモリの記憶容量をよりよく利用するために、有効な断片的データのコピー元のブロックを消去して、それらの全記憶容量を再利用できるように、これらの断片的データを消去ブロックにコピーすることにより、有効な断片的データを統合したり、または集めたりすることが一般的に行われている。論理アドレス順にブロック内部のデータセクタをグループ化するためにデータのコピーを行うことも望ましいのは、これにより、データ読み出し速度と、読み出したデータをホストに送信する速度とが向上するからである。このようなデータコピーがかなり頻繁に行われると、メモリシステムの動作性能が低下してしまう。このことは特に、メモリの記憶容量が、システムの論理アドレス空間を介してホストがアドレス指定可能なデータ量を若干上回っている場合に、メモリシステムの動作に影響を与える典型的な場合である。この場合、ホストがプログラミングを行ったコマンドを実行する前に、データの統合や収集が必要になることもある。そして、結果としてプログラミングを行う時間が長くなる。
【０００７】
任意の半導体領域に記憶するデータのビット数を増やすために、メモリシステムの世代を経るにつれて、ブロックサイズは大きくなっていった。２５６データセクタ以上を記憶するブロックが一般的になっている。さらに、データのプログラミングと読み出しとを行う際の並列処理の程度を上げるために、２つ、４つ、あるいはそれ以上のブロック数の異なるアレイまたはサブアレイを理論的に接続して、メタブロックを構成するようにすることがしばしば行われている。このように容量が大きい動作単位をともに効率的に動作させることが、課題となっている。
【０００８】
このようなメモリシステムのための一般的なホストインターフェイスは、ディスクドライブとともに一般的に用いられるものと同様な論理アドレスインターフェイスである。メモリが接続しているホストが生成したファイルには、インターフェイスの論理アドレス空間内の一意のアドレスが割り当てられている。次に、メモリシステムは通常、論理アドレス空間と、メモリの物理ブロックまたはメタブロックとの間でデータのマッピングを行う。メモリシステムは、物理メモリに対してどのように論理アドレス空間のマッピングを行うかを常に把握しているが、ホストはこのことを知る必要はない。ホストは、論理アドレス空間内のそのデータファイルのアドレスを常に把握しているが、メモリシステムの動作には、このマッピングについてわかっている必要はない。
【特許文献１】米国特許第５，６０２，９８７号
【特許文献２】米国特許第６，４２６，８９３号
【特許文献３】米国特許出願第１１／０６０，２４８号
【特許文献４】米国特許出願第１０／９１５，０３９号
【特許文献５】米国特許第５，５７０，３１５号
【特許文献６】米国特許第５，７７４，３９７号
【特許文献７】米国特許第６，０４６，９３５号
【特許文献８】米国特許第６，３７３，７４６号
【特許文献９】米国特許第６，４５６，５２８号
【特許文献１０】米国特許第６，５２２，５８０号
【特許文献１１】米国特許第６，７７１，５３６号
【特許文献１２】米国特許第６，７８１，８７７号
【特許文献１３】米国公開特許出願第２００３／０１４７２７８号
【特許文献１４】米国公開特許出願第２００３／０１０９０９３号
【特許文献１５】米国特許第６，７６３，４２４号
【特許文献１６】米国特許出願第１０／７４９，８３１号
【特許文献１７】米国特許出願第１０／７５０，１５５号
【特許文献１８】米国特許出願第１０／９１７，８８８号
【特許文献１９】米国特許出願第１０／９１７，８６７号
【特許文献２０】米国特許出願第１０／９１７，８８９号
【特許文献２１】米国特許出願第１０／９１７，７２５号
【特許文献２２】米国特許出願第１１／１９２，２２０号
【特許文献２３】米国特許出願第１１／１９２，３８６号
【特許文献２４】米国特許出願第１１／１９１，６８６号
【特許文献２５】米国特許出願第１０／７４９，１８９号
【特許文献２６】米国特許出願第１０／８４１，１１８号
【特許文献２７】米国特許出願第１１／０１６，２７１号
【特許文献２８】米国特許出願第１０／８９７，０４９号
【特許文献２９】米国特許出願第１１／０２２，３６９号
【特許文献３０】米国特許出願第１１／１９６，８６９号
【特許文献３１】米国特許出願第１１／３１６，５７７号
【特許文献３２】米国特許出願第１１／３８２，２３２号
【特許文献３３】米国特許出願第１１／３８２，２２４号
【発明の開示】
【０００９】
フラッシュメモリシステムのこのように大きな規模の消去ブロックの動作を効率的に行う際に、様々な度合いで確実に生じる問題を克服する技術が、たくさん開発されている。これに対して、本発明は、根本的な変更、すなわち、メモリとホストシステムとの間でデータを転送するインターフェイスの変更に基づいている。仮想アドレス空間内の論理アドレスを用いることにより、メモリとホストシステムとの間でデータ通信を行うことではなく、ホストが割り当てたファイル名によりデータファイルの識別を行い、ファイル内のアドレスのオフセットを行ってそれにアクセスする。メモリシステムは次に、各セクタまたは他の単位のデータが属するホストファイルのことがわかるようになる。ここで説明するファイル単位とは、連続オフセットアドレスなどにより順序づけられたデータセットであって、ホスト演算システム内で動作するアプリケーションプログラムが生成し、かつ一意に識別したデータセットである。
【００１０】
このことが、現在市販のメモリシステムの多くで用いられていないのは、ホストが現在では、ファイルを識別することなく、共通セットの論理アドレスにより、全てのファイル内のメモリシステムに対しデータの識別を行っているからである。論理アドレスを用いる代わりに、ファイルオブジェクトによってホストデータの識別を行うことにより、データの統合やガーベッジコレクションを頻繁に行う必要性を低減するように、メモリシステムのコントローラはデータを記憶することができる。従って、データのコピー動作の頻度と、コピーデータ量とが大幅に低減するので、これによりメモリシステムのデータのプログラミングと読み出し性能が向上する。さらに、メモリシステムのコントローラは、ホストファイルを記憶するメモリブロックのディレクトリおよびインデックステーブル情報を保持する。このため、現在、論理アドレスインターフェイスの管理に必要なファイルアロケーションテーブル（ＦＡＴ）を、ホストが保持する必要がなくなる。
【００１１】
そうではなく、データグループによりファイルのデータの識別を行い、メモリ内のファイルのデータグループの位置をファイルインデックステーブル（ＦＩＴ）に保持する。前に援用されている特許出願、特に米国特許出願第１１／０６０，２４８号（特許文献３）で、より完全に記載されているように、データグループは、連続する連続オフセットアドレスおよび連続する物理メモリアドレスの両方を有するデータを含んでいる。前に援用されている特許出願にも記載されているように、各ファイルに対する有効なデータグループのインデックスを、それらのオフセットアドレスでＦＩＴに保持する。その一意のファイル識別子を用いることにより、ファイルディレクトリを介して任意のファイルにアクセスする。次に、ファイルのＦＩＴエントリへのアクセスが、ファイルのデータグループの物理位置となる。
【００１２】
典型的には、メモリシステムが接続するホストは、５つのファイルなどの、１度に開くあらかじめ設定した最大数のファイルとともに動作する。最大数のファイルがすでに開かれているときに、新しいファイルを開く必要があるというイベントでは、まず、ホストが現在開いているファイルを閉じる。追加データの書き込み、更新、または削除等を行うことによりファイルが変更する度に、開いているファイルのデータグループは頻繁に変わる。典型的には、ファイルのデータグループのＦＩＴリストの更新に必要なことは、ファイルのエントリを含んでいるページを読み出し、それらのエントリを修正し、次に、メモリの異なる位置に、修正したページの、あれば、典型的には同じメモリブロック内の消去ページの書き換えを行うことである。従って、そのページが変わる度に、ファイルディレクトリは、ファイルのＦＩＴエントリを含んでいる現在のページを示すことができなければならない。
【００１３】
ファイルディレクトリに入っているものすべての書き換えを行う必要なしに、アクティブファイルのデータグループのリストの更新を行うことが好ましい。開いているファイルのデータグループのアドレス指定を間接的に行う手法により、ファイルのＦＩＴエントリにアクセスする際に、ファイルディレクトリが、メモリの同じ位置を指したままにすることが可能になる。好ましくは、ファイルディレクトリが、ファイルの更新ＦＩＴエントリを含んでいるページのアドレスを含んでいるＦＩＴエントリの、書き込みが行われた最後のページに含まれる、論理ポインタのアドレス指定を行う。ファイルのＦＩＴエントリの更新を行う度に、論理ポインタは変化するが、ファイルのファイルディレクトリのアドレスが変わる必要はない。
【００１４】
しかし、小さいファイルを数多く記憶する際に発生するように、メモリシステムに多数のファイルを記憶してある場合、このような間接アドレス指定が、効率的ではない。というのは、もちろん、それらのデータ記憶容量によるが、ディレクトリおよびＦＩＴページは、非常に多くのファイルのエントリを１度に納めることができるからである。結果として、ホストが閉じていたので、現在アクティブではないファイルに対し、好ましくは、ファイルディレクトリにより、インデックスエントリに直接アドレス指定を行う。間接アドレス指定の論理アドレスポインタの特徴は用いない。
【００１５】
従って、開いているファイルなどの、近い将来変わることが考えられるファイルのＦＩＴエントリの間接アドレス指定と、閉じているファイルへの直接アドレス指定との組み合わせは、好適な動作モードである。すなわち、アクティブでデータの書き込みが行われていたり、または更新が行われていたりする開いたファイルに対し、ファイルディレクトリは、ファイルディレクトリを修正する必要なく、アクティブファイルのインデックスエントリのセットを修正するように、ファイルの一意の識別子が識別したインデックスエントリのセットのＦＩＴの位置を、間接的に定義する。具体例では、ファイルのインデックスエントリの実際の物理位置との参照を行う、メモリ内の任意の位置のアドレス指定を行うファイルディレクトリにより、これを達成する。インデックスエントリの更新を行って移動する度に、この参照は変わるが、ファイルディレクトリを更新する必要はない。同時に、閉じているファイルに対し、一意のファイル識別子が識別したインデックスエントリのセットのＦＩＴの位置を、ファイルディレクトリが直接定義する。閉じているファイルに対するインデックスエントリの再配置は、開いているファイルに対するものよりずっと可能性が低い。
【００１６】
さらに、直接アドレス指定で用いるために、好ましくは、ＦＩＴページのインデックスエントリを、ＦＩＴへのポインタがファイルディレクトリの同じページに含まれているファイルのデータグループに制限する。従って、そのディレクトリページに記載されているファイルの１つ以上のＦＩＴエントリの更新を行う場合、ファイルディレクトリの１ページだけを、更新すればよい。そうしないと、ファイルの１つ以上のＦＩＴエントリの更新を行う場合、複数のファイルディレクトリページを頻繁に更新しなければならなくなる。
【００１７】
本発明の他の態様、利点、特徴および詳細については、添付の図面を参照して説明する、以下の例示の説明に含まれている。
【００１８】
ここで参照する特許、特許出願、論文、他の公報、文献および事柄は全て、事実上、その全体が本願明細書において参照により援用されている。定義上、または援用されている公報、文献または事柄と本願との間の用語のある程度の不一致または矛盾については、本願で用いる用語により明らかになるであろう。
【発明を実施するための最良の形態】
【００１９】
フラッシュメモリシステムの概要
図１〜図８を参照して、一般的なフラッシュメモリシステムと、ホストデバイスとの典型的な動作とについて説明する。これは、本発明の様々な態様を実施するシステムである。図１のホストシステム１は、フラッシュメモリ２にデータを記憶し、フラッシュメモリ２からデータを検索する。フラッシュメモリをホストに埋め込むことが可能であるが、メモリ２については、より広く普及している形態のカードとし、機械的および電気的なコネクタである接続部分３および４を介してホストに取り外し可能に接続しているものとして例示する。現在、多くの異なるフラッシュメモリカードが市販されているが、一例として、コンパクトフラッシュ（ＣＦ）、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）、ミニＳＤ、マイクロＳＤ、メモリスティック、スマートメディアおよびトランスフラッシュという商標のもとで販売されている。これらのカードは、それらの標準化仕様により一意の機械的および／または電気的インターフェイスを有しているが、各カードに含まれるフラッシュメモリは非常に似通っている。これらのカードはすべて、本願の譲受人であるサンディスク  コーポレイション(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) による２００５年１２月２１日出願の米国特許出願第１１／３１６，５７７号（特許文献３１）により得られる。
【００７０】
新しいデータファイルのプログラミングを行ってメモリに取り込む場合、データを消去したメモリセルブロックに書き込む。ブロック内の第１の物理位置から開始し、ブロックの位置を介して連続して順に書き込みを進める。ファイル内のそのデータのオフセットの順序に関係なく、ホストから受け取った順に、データのプログラミングを行う。ファイルのデータをすべてメモリに書き込むまで、プログラミングを継続する。ファイルのデータ量が１つのメモリブロックの容量を超える場合、第１のブロックが満杯になったときは、第２の消去ブロックにプログラミングを継続する。第１のブロックと同じやり方で、ファイルのデータすべてを記憶するまで、または第２のブロックが満杯になるまで、第１の位置から順に、第２のメモリブロックにプログラミングを行う。第３のブロックまたは追加付加ブロックに対し、ファイルに残っているデータのプログラミングを行ってもよい。１つのファイルのデータを記憶してある複数のブロックまたはメタブロックは、物理的または論理的に連続している必要はない。説明を簡単にするため、特に明記がない限り、ここで用いる用語“ブロック”とは、特定のシステムでメタブロックが用いられているかどうかにより、消去ブロック単位または複数のブロックである“メタブロック”のいずれかについて言うものである。
【００７１】
図１２の状態図は、図１１に示すメモリ動作の全体的な機能を示す。個別のメモリブロックを考察すると、３つの状態のうちの１つになる。これらは、解放可能な容量のない、有効なファイルデータの記憶が行われている消去ブロック６４１およびブロック６４３と、プログラミングが行われない消去ページおよび／または記憶してあるが使われなくなった（無効な）データから、解放可能な容量を有している、有効なファイルデータを含んでいるブロック６４５とである。機能６４７が、消去したメモリブロックにデータの書き込みを行うことにより、得られるプログラミングが行われたブロックが解放可能な容量を保持しているかどうかに基づいて、カテゴリ６４３または６４５のブロックになる。機能６４９で示すように、ファイルを消去する場合、ファイルのデータを含んでいるブロック６４３を、解放可能な容量を有するブロック６４５に変換する。機能６５１が、ブロック６４５の使われていない記憶容量を解放することにより、それらのブロックを、新しいデータの書き込みが行われる消去ブロック６４１の状態に復帰させることになる。
【００７２】
図１３Ａを参照すると、メモリシステムに行うデータファイルの書き込みを示している。この例では、データファイル１８１は、メモリシステムの１つのブロックまたはメタブロック１８３の記憶容量よりも大きい。これは、縦の実線の間に延びている。従って、データファイル１８１の部分１８４は、第２のブロック１８５に書き込まれる。これらのメモリセルブロックは物理的に連続して示しているが、必ずしも連続している必要はない。ファイルのデータすべてをメモリに書き込むまで、ホストからの受信ストリーミングとして、ファイル１８１からのデータの書き込みを行う。図１３Ａの例では、データ１８１はファイルの初期データである。
【００７３】
メモリシステムが、記憶してあるデータの管理を行い、状態を常に把握する好適なやり方は、大きさが可変のデータグループを用いることである。すなわち、完全なファイルを形成する定義済みの順序でつながっている複数のグループのデータとして、ファイルのデータを記憶する。好ましくは、しかし、ファイルインデックステーブル（ＦＩＴ）を用いることにより、メモリシステムのコントローラがファイル内のデータグループの順序を保持する。ホストからのデータストリームとして書き込みが行われている間、ファイルデータの論理オフセットアドレス、またはデータを記憶する物理空間に不連続性があると、必ず新しいデータグループが始まってしまう。このような物理的な不連続性の一例は、ファイルのデータが１つのブロックで満杯になり、別のブロックへの書き込みが始まる場合である。図１３Ａにこれを示す。第１のデータグループが第１のブロック１８３で満杯になり、第２のデータグループとしてのファイルの残っている部分１８４を第２のブロック１８５に記憶する。第１のデータグループを（Ｆ０，Ｄ０）で示す。Ｆ０がデータファイルが開始したときの論理オフセットであり、Ｄ０がファイルが始まるメモリ内部の物理位置である。第２のデータグループを（Ｆ１，Ｄ１）で示す。Ｆ１が第２のブロック１８５が始まるときに記憶してあるデータの論理ファイルオフセットであり、Ｄ１がデータを記憶してある物理位置である。
【００７４】
ホスト−メモリインターフェイスを介して転送するデータ量について、多数のバイト数のデータ、多数のデータセクタ、または他の細分性で述べる場合もある。現在の論理アドレスインターフェイスを介して大容量メモリシステムと通信を行う場合、ホストは大抵の場合、そのファイルのデータをバイト細分性で定義するが、次に、バイトを５１２バイト毎のセクタにグループ化を行ったり、または多数のセクタ毎のクラスタにグループ化を行ったりする。これは、メモリシステムの動作を簡略化するために通常行われている。ここで説明するファイルベースのホスト−メモリインターフェイスは他の単位のデータを用いる場合もあるが、もともとのホストファイルのバイト細分性が一般的には好ましい。すなわち、好ましくは、セクタ、クラスタ等ではなく、データオフセット、長さ等を、バイトで、最小の合理的な単位のデータで表現する。これにより、ここで説明する技術によるフラッシュメモリ記憶装置の容量をより効率的に利用することが可能になる。
【００７５】
次に、図１３Ａに示すやり方でメモリに書き込んだ新しいファイルを、この順で、データグループのインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１、Ｄ１）シーケンスとしてＦＩＴで表す。すなわち、ホストシステムが特定のファイルにアクセスしたい場合は必ず、ホストはそのファイルＩＤまたは他の識別名をメモリシステムに送信し、次に、そのＦＩＴにアクセスして、そのファイルを構成するデータグループの識別を行う。メモリシステムの動作の便宜上、これらの個別のエントリも個別のデータグループの長さ＜ｌｅｎｇｔｈ＞に含めてもよい。用いる際には、メモリコントローラは、データグループの長さを算出し、記憶する。
【００７６】
好ましくは、ホストが図１３Ａのファイルを開いている状態に保持している限り、ホストからさらにデータを受信してそのファイルに書き込みを行う位置を定義できるように、物理書き込みポインタＰについても保持する。ファイル内の新しいデータの論理位置に関わらず、物理メモリ内のファイルの終端にファイルの新しいデータの書き込みを行う。メモリシステムにより、４つまたは５つのファイルなどの複数のファイルを１度に開いたままにしておくことが可能になり、それぞれに対し書き込みポインタＰを保持する。異なるファイルの書き込みポインタは、異なるメモリブロック内の位置を指している。メモリシステムに、すでに存在する開いているファイルの数に制限があるときに、ホストシステムが新しいファイルを開きたい場合、開いているファイルのうちの１つをまず閉じて、次に、新しいファイルを開く。
【００７７】
図１３Ｂは、図１３Ａの前に書き込みが行われたもののまだ開いたファイルとなっているファイルの終端に、ホストがデータの追加を行うことを示す。ホストシステムが、ファイルの終端にデータ１８７を追加していることを示している。これは、そのファイルのデータの終端で、第２のブロック１８５に書き込みが行われている。追加データはデータグループ（Ｆ１，Ｄ１）の一部となるので、これでデータをさらに含むことになる。というのは、既存のデータグループ１８４と追加データ１８９との間に論理的にも物理的にもアドレス不連続性がないからである。従って、満杯になったファイルはやはり、ＦＩＴのインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ１）のシーケンスとして表される。ポインタＰのアドレスについても、記憶した追加データの終端のアドレスに変更する。
【００７８】
図１３Ａの前に書き込みを行ったファイルへのデータブロック１９１の挿入についての一例を図１３Ｃに示す。ホストがデータ１９１をファイルに挿入しているが、メモリシステムは、前に書き込みを行ったファイルデータの終端の位置１９３に挿入したデータを追加している。ホストがファイルを閉じた後で、バックグラウンドで後で行うこともあるが、開いているファイルにデータの挿入を行っている間、それらの論理の順序でファイルのデータの書き換えを行う必要はない。１つの新しいグループ（Ｆ１，Ｄ３）を形成する場合、挿入したデータをすべて、第２のメモリブロック１８５に記憶するからである。しかし、この挿入を行うことにより、図１３Ａの前のデータグループ（Ｆ０，Ｄ０）になり、挿入前のグループ（Ｆ０，Ｄ０）と、挿入後のグループ（Ｆ２，Ｄ１）との２つのグループに分割される。これは、挿入の始点Ｆ１と挿入の終点Ｆ２とで発生するようなデータの論理的な不連続性がある場合は必ず、新しいデータグループを形成する必要があるからである。グループ（Ｆ３，Ｄ２）は、第２のブロック１８５の始点である物理アドレスＤ２の結果である。たとえ同じメモリブロックに記憶してある場合であっても、グループ（Ｆ１，Ｄ３）および（Ｆ３，Ｄ２）を、別々に保持する。つまり、記憶してあるデータオフセットに不連続性があるからである。次に、データグループインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ３）、（Ｆ２，Ｄ１）、（Ｆ３，Ｄ２）の順で、挿入のもともとのファイルをメモリシステムＦＩＴに表す。メモリ内のデータを全部使って、新しいファイルまたは既存のファイルの新しいデータの書き込みを行うこともできることが、図１３Ａ、図１３Ｂおよび図１３Ｃの例からわかることに留意されたい。
【００７９】
図１３Ｃに示す既存のファイルへのデータの挿入に代えて、データを挿入したときは必ず、ホストが別個のファイルとしてメモリにファイルの書き換えを行ってもよい。次に、メモリシステムは、この別個のファイルを新しいファイルとして処理することもある。次に、ホストが古いファイルを削除し、メモリシステムは、データがもう使われなくなった古いファイルを記憶してある空間の解放に応答できる。
【００８０】
図１３Ｄは、図１３Ａに示すやり方でもともと書き込みを行ったデータのある一部分を更新する、別の例を示す。データファイルの部分１９５が更新部分である。更新を行ってメモリシステムの全ファイルの書き換えを行うのではなく、ファイルの更新部分１９７を、前に書き込みを行ったデータに追加する。前に書き込みを行ったデータの部分１９９は、今は使われなくなっている。更新を行った後、データグループインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ３）、（Ｆ２，Ｄ１）、（Ｆ３，Ｄ２）の順で、ファイルをメモリシステムＦＩＴに表す。図１３Ａの１つのデータグループ（Ｆ０，Ｄ０）を、図１３Ｄに示す部分に再度分割する。更新部分の前のグループと、更新部分と、更新部分の後のグループとである。使われなくなったデータが占有している空間１９９を解放することが望ましいが、メモリにファイルデータの書き込みを行う一部としてではなく、好ましくは、後で行う。典型的には、このような解放を行うことにより、記憶してある特定のファイルのデータのデータグループの数がより少なくなる。
【００８１】
可変長データグループの利用をさらに説明するために、一連の同じファイルを含むいくつかの書き込み動作について、図１４Ａ〜図１４Ｅに順に示す。まず、図１４Ａに示すように、メモリシステムの２つのブロックに、もともとのファイルデータＷ１の書き込みを行う。次に、２つのデータグループ、物理メモリブロックの始点から始まる第１のグループと、物理メモリブロックの境界の後から開始しなければならない第２のグループとにより、ファイルを定義する。次に、図１４Ａのファイルを、データグループに対する以下の一連のインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ１，Ｄ１）により記述する。
【００８２】
図１４Ｂでは、ホストが、図１４Ａで書き込まれたファイルデータの更新を行う。更新データの前のバージョンが使われなくなっている前のグループ（Ｆ１，Ｄ１）のすぐ後に、更新したファイルデータＵ１の書き込みを行う。図１４Ａの前のグループ（Ｆ０，Ｄ０）が短くなって図１４Ｂの変更後のグループ（Ｆ０，Ｄ０）になり、前のグループ（Ｆ１，Ｄ１）が短くなって、グループ（Ｆ４，Ｄ２）になる。メモリブロックの境界で重複しているので、２つのグループ（Ｆ２，Ｄ３）および（Ｆ３，Ｄ４）に更新データの書き込みを行う。データのいくつかは、第３のメモリブロックに記憶する。これで、データグループに対する以下の一連のインデックスエントリ（Ｆ０，Ｄ０）、（Ｆ２，Ｄ３）、（Ｆ３，Ｄ４）、（Ｆ４，Ｄ２）により、ファイルを記述する。
【００８３】
ホストが新しいファイルデータＩ１の挿入を行う、図１４Ｂのファイルをさらに変更したものを図１４Ｃに示す。挿入したデータがメモリブロックの境界と重複しているので、図１４Ｃの新しいグループ（Ｆ５，Ｄ６）および（Ｆ６，Ｄ７）として、図１４Ｂの前のグループ（Ｆ４，Ｄ２）のすぐ次のメモリに、新しいデータＩ１の書き込みを行う。第４のメモリブロックを用いる。新しいデータＩ１の挿入により、図１４Ｂの前のグループ（Ｆ０，Ｄ０）を、図１４Ｃの短縮したグループ（Ｆ０，Ｄ０）および（Ｆ７，Ｄ５）に分割する。これで、データグループに対する以下のインデックスエントリシーケンス（Ｆ０，Ｄ０）、（Ｆ５，Ｄ６）、（Ｆ６，Ｄ７）、（Ｆ７，Ｄ５）、（Ｆ８，Ｄ３）、（Ｆ９，Ｄ４）、（Ｆ１０，Ｄ２）により、ファイルを記述する。
【００８４】
図１４Ｄは、新しいデータＷ２をファイルの終端に追加した、図１４Ｃのデータファイルの別の変更例を示す。図１４Ｄの新しいグループ（Ｆ１１，Ｄ８）として、図１４Ｃの前のグループ（Ｆ１０，Ｄ２）のすぐ次に新しいデータＷ２の書き込みを行う。これで、データグループに対する以下のインデックスエントリシーケンス（Ｆ０，Ｄ０）、（Ｆ５，Ｄ６）、（Ｆ６，Ｄ７）、（Ｆ７，Ｄ５）、（Ｆ８，Ｄ３）、（Ｆ９，Ｄ４）、（Ｆ１０，Ｄ２）、（Ｆ１１，Ｄ８）により、ファイルを記述する。
【００８５】
図１４Ｄのファイルに更新したファイルデータＵ２の書き込みを行う、開かれているファイルに対する第２の更新を図１４Ｅに示す。そのデータの前のバージョンが使われなくなっている、図１４Ｄの前のグループ（Ｆ１１，Ｄ８）のすぐ次に、図１４Ｅの更新データＵ２の書き込みを行う。図１４Ｄの前のグループ（Ｆ９，Ｄ４）が短くなって、図１４Ｅの変更後のグループ（Ｆ９，Ｄ４）になり、前のグループ（Ｆ１０，Ｄ２）が完全に使われなくなり、前のグループ（Ｆ１１，Ｄ８）が短くなって、新しいグループ（Ｆ１４，Ｄ９）を形成する。ブロックの境界と重複している図１４Ｅの新しいグループ（Ｆ１２，Ｄ１０）および（Ｆ１３，Ｄ１１）に、更新データの書き込みを行う。これで、第５のブロックには、ファイルを記憶する必要がある。これで、データグループに対する以下のインデックスエントリシーケンス（Ｆ０，Ｄ０）、（Ｆ５，Ｄ６）、（Ｆ６，Ｄ７）、（Ｆ７，Ｄ５）、（Ｆ８，Ｄ３）、（Ｆ９，Ｄ４）、（Ｆ１２，Ｄ１０）、（Ｆ１３，Ｄ１１）、（Ｆ１４，Ｄ９）により、ファイルを記述する。
【００８６】
好ましくは、各ファイルのデータのオフセットを、前の説明によるファイルの生成または変更を行った後で、正しい論理的順序で連続して保持する。従って、データをファイルに挿入する動作の一部として、例えば、ホストが行った挿入したデータのオフセットは、挿入の直前のオフセットから連続し、挿入後のすでにファイルに入っているデータを、挿入したデータ量で増分する。最も一般的には、既存のファイルの更新を行うと、類似量の更新データで置き換えられた既存のファイルの任意のアドレス範囲のデータになるので、通常、他のファイルのデータのオフセットを置き換える必要はない。
【００８７】
図１３に関連して前述した、データの割り当ておよび索引付け機能はすべて、メモリシステムのコントローラが行うことに留意されたい。適切なコマンドとともに、ホストは単に、ファイルＩＤおよびファイル内のデータのオフセットをメモリシステムに送る通信を行うだけでよい。残りはメモリシステムが行う。
【００８８】
前述したやり方でホストからのファイルデータを直接フラッシュメモリに書き込みを行う利点は、このように記憶してあるデータの細分性または分解を、ホストのデータと同じように保持することができることである。ホストアプリケーションが１バイトの細分性でファイルデータの書き込みを行う場合、例えば、そのデータについても、１バイト細分性でフラッシュメモリに書き込みを行う。次に、個別のデータグループ内のデータ量および位置を、バイト数で測定する。すなわち、ホストアプリケーションファイル内で別々にアドレス指定可能なデータの同じオフセット単位については、フラッシュメモリに記憶したときのそのファイル内でもやはり別々にアドレス指定可能である。次に、ブロック内の同じファイルのデータグループ間の境界はいずれも、最も近いバイトまたは他のホストオフセット単位に対し、インデックステーブルで指定されている。同様に、ブロック内の異なるファイルのデータグループ間の境界は、ホストのオフセット単位で定義されている。
【００８９】
用語“セクタ”とは、ここでは大きなブロックのメモリに用いられ、ＥＣＣが対応づけられている記憶してあるデータの単位を表している。セクタも、フラッシュメモリとやりとりするデータ転送の最小単位である。“ページ”は、ブロック内のメモリセルの単位を表すのに用いられ、プログラミングの最小単位である。“メタページ”とは、メタブロックの完全な並列処理を行うページを表すのに用いられる。メタページは、プログラミングの最大単位である。
【００９０】
図１４Ｂおよび図１４Ｅから、更新コマンドにより、ファイル内のデータ量より大きいファイルを記憶する必要のある物理空間となることがわかる。これは、更新により置き換えられたデータを、メモリに記憶したままになっているからである。従って、使われなくなった無効なデータを削除することにより、ファイルのデータをより小さい物理記憶空間に統合する（ガーベッジコレクションを行う）ことは、非常に望ましい。従って、他のデータがさらに記憶空間を利用できるようになる。
【００９１】
図１４Ｂおよび図１４Ｅのファイルデータの更新の他に、図１４Ｃのデータ挿入を行うことにより、順番が狂ってファイルデータを記憶することになることもわかる。すなわち、ほとんどいつも、ファイル内のいずれかに論理的に位置づけられるが、更新および挿入を行う際に、更新および挿入は、メモリに記憶してあるファイルの終端に加えられる。これは、図１４Ｂ、図１４Ｃおよび図１４Ｅに一例である。従って、メモリに記憶してあるファイルのデータを整理し直して、ファイル内のオフセットの順序に一致させることは望ましい。連続してページおよびブロックの読み出しを行うことにより、ファイルのデータがそれらのオフセットの順序になるので、記憶してあるデータの読み出し速度が向上することになる。これにより、可能なファイルの断片化を解消する(defragmentation) ことが最大になる。しかし、場合によっては１つ以上のメモリブロックを解放して他のデータを記憶に用いるようにするファイルデータ統合のように、ファイルデータを整理し直して読み出しをより効率的にすることは、メモリシステムの性能にはあまり重要ではない。従って、ファイル内のデータを整理し直すことは、工場管理費を追加したほどの価値のある恩恵が得られないので通常単独で行われないが、工場管理費がほとんど、あるいは全くかからないで、多くのガーベッジコレクション動作の一部として行うことができる。
【００９２】
図１４Ｅのファイルは、生成された２つのデータ更新Ｕ１およびＵ２により、メモリに記憶された使われなくなったデータグループ（グレー部分）を含んでいる。結果として、図１４Ｅからわかるように、ファイルの記憶に用いられるメモリ容量の量が、ファイルの大きさよりも相当大きい。従って、ガーベッジコレクションを行うことが適切である。図１５は、図１４Ｅのデータファイルのガーベッジコレクションを行った結果を示す。ガーベッジコレクションの前は、そのファイルは、ほぼ５つのブロックの記憶容量を占有しているが（図１４Ｅ）、ガーベッジコレクション後の同じファイルは、３つのメモリセルブロックを多少超えて納められている（図１５）。ガーベッジコレクション動作の一部として、データをブロックからコピーする。はじめに、他の消去ブロックに書き込みを行い、次に、もともとのブロックを消去する。全ファイルのガーベッジコレクションを行う場合、ファイル内のデータ論理オフセットの順序と同じ物理的順序で、新しいブロックにそのデータをコピーする。例えば、ガーベッジコレクションの後（図１５）、ホストファイル内の順序と同じ順序で、更新Ｕ１およびＵ２、挿入Ｉ１を記憶する。
【００９３】
通常、ファイルベースのガーベッジコレクションも、統合したファイル内に、新しい、異なるデータグループを形成することになる。図１５の場合、新しいデータグループに対する以下の新しいインデックスエントリシーケンス（Ｆ０，Ｄ１２）、（Ｆ１，Ｄ１３）、（Ｆ２，Ｄ１４）、（Ｆ３，Ｄ１５）により、ファイルを記述する。これは、図１４Ｅに示すファイルの状態で存在するものよりも、データグループの数はずっと少ない。ファイルのデータをコピーしたメモリセルブロック毎に１つのデータグループがある。ガーベッジコレクション動作の一部として、ファイルインデックステーブル（ＦＩＴ）の更新を行って、ファイルを構成する新しいデータグループを反映させる。
【００９４】
図１４Ｅのデータ分布から図１５のデータ分布へ移動するには、相当のデータ量のコピーを行うことが必要であることに留意されたい。図１４Ｅのそれぞれのブロックから有効なデータの読み出しを行って、次に、図１５の４つの消去ブロックに書き込みを行う。これにより、将来用いるファイルのデータグループを非常に簡略にするが、データのコピーに相当長い時間がかかる。従って、ファイルベースのデータのガーベッジコレクションを行わないで、その代わりに、ファイルとしてデータを直接メモリに記憶する場合であっても、ブロックベースで行う。最もデータ量が少ないブロックにガーベッジコレクションを行って、別のブロックにコピーすることにより、ブロックの使われていない容量を解放する。このことは、前に援用されている、２００６年５月８日出願の米国特許出願第１１／３８２，２３２号“フラッシュメモリのデータ記憶容量の解放(Reclaiming Data Storage Capacity in Flash Memories)”（特許文献３２）に記載されている。
【００９５】
従って、図１４Ｅの状態で、ファイルのデータを保持しているブロックの解放を、同じファイルのデータを記憶してある複数のブロックに行うのではなく、ブロックに対し個別に行う。例えば、任意のときに解放動作を行うように考えられているメモリシステムのブロックのうち、図１４Ｅの第２のブロック００２の有効なデータ量が最も少ない場合、次に、図１６に示すように、別の消去ブロック０１０にその１つのデータグループをコピーする。そして、新しいブロックは、１つのデータグループ（Ｆ８，Ｄ１６）と、新しいデータの書き込みが行われるブロックの残りの消去した容量とを含むことになる。図１４Ｅでデータを記憶してあるブロックから、その消去した容量を解放する。次に、ファイル（Ｆ０，Ｄ０）、（Ｆ５，Ｄ６）、（Ｆ６，Ｄ７）、（Ｆ７，Ｄ５）、（Ｆ８，Ｄ１６）、（Ｆ９，Ｄ４）、（Ｆ１２，Ｄ１０）、（Ｆ１３，Ｄ１１）、（Ｆ１４，Ｄ９）から構成される、以下のインデックスエントリシーケンスにより、データグループに対し、ファイルを記述する。ブロック解放処理に基づいて、解放動作のための基準を個別に満たすまでは、図１４Ｅに示す他のブロックを変更しない。
【００９６】
ファイルデータの索引付け
図１７は、いくつかのそれぞれ異なる時間０、２、４、ＸおよびＹでの１つのファイルのファイルインデックステーブル（ＦＩＴ）内のインデックスエントリシーケンスを示す。これらは、図１４Ａ、図１４Ｃ、図１４Ｅ、図１５および図１６それぞれに関連する前述したシーケンスである。好ましくは、ホストシステムからの支援を受けずに、メモリのコントローラにより、ＦＩＴのデータの書き込みを行って、現在の状態を保持する。メモリシステムにデータの書き込みを行う際に、ホストシステムは、パス名、ファイル名およびファイル内のデータのオフセットを供給するが、データグループの定義、またはメモリセルアレイのどこに記憶するかについては、ホストは行わない。図１７のエントリでは、図１４Ａ〜図１４Ｅのメモリセルブロックに、左から１で始まる番号を振る。従って、図１４Ｃに示す状態のファイルでは、例えば、その第３のデータグループ（Ｆ６，Ｄ７）にはブロック００４に記憶するように図１７に注記が付けられる。左から４つめのブロックで、そのブロックの初期アドレスからＤ７バイトである。好ましくは、表の各エントリに各データグループの長さも含む。
【００９７】
図１７に示す、ファイルの変更により、ファイルのデータグループに対する修正となる際に、またはあまり頻繁にではないが、メモリのコントローラが、１つのファイルに対するインデックスエントリシーケンスの書き換えを行う。コントローラは、このような変更をそのメモリに記憶し、フラッシュメモリに１度にその多くの書き込みを行うこができる。任意のある時間に、ファイル毎に有効なインデックスのセットが１つだけ存在する。これは、異なる時間でファイルを定義した図１７に示す５つのインデックスのセットである。時間ＸおよびＹのインデックスは、２つの異なる種類の解放動作の結果を示す。前述したように、一方はファイルベースのもので、もう一方はブロックベースのものである。ファイルへの追加データのプログラミング、ファイルからのデータ読み出し、そのデータを記憶してあるファイルまたはブロックのデータのガーベッジコレクションを行う必要があるときに、メモリシステムのコントローラは、ファイルの現在のインデックスのセットを用いる。他の動作に用いる場合もある。従って、それらのファイルオフセット（Ｆｘ）の順で個別のファイルのインデックスエントリを記憶している場合、ＦＩＴは使いやすいが、そうでない場合、コントローラは、まちがいなく論理的順序でエントリの読み出しを行うことができる。メモリコントローラが特定のファイルのインデックスエントリの読み出しを行う最も一般的な理由は、ホストコマンドの実行中にある。
【００９８】
具体的なファイル索引付けを行う第１の実施形態
図１８を参照して、連続するセット内の数値である一意のファイルＩＤ２０１で、直接データファイルインターフェイスとともに動作するメモリシステムに記憶してあるファイルの識別を行う。ディレクトリ２０３は、メモリ装置に記憶している有効なファイル毎に１つエントリを含んでいる。好ましくは、ディレクトリ２０３はフラットな階層で、サブディレクトリをサポートしていない。これにより、メモリの直接データファイルシステムが、ホストで用いられるオペレーティングシステムとは独立可能になる。特定のホストオペレーティングシステムプロトコルに従う階層ディレクトリについては、直接データファイルシステム外部のファームウェア層がサポートを行い、フラットなディレクトリ構造をやはりサポートしているファイルメタデータ（ファイル“属性”情報もわかっている）機能とともに利用する。
【００９９】
前の説明をまとめると、データセットグループとしてファイルのデータを記憶してある。それぞれ、ファイルオフセットアドレス空間と物理アドレス空間との両方で、１度に実行する連続するアドレス全域にわたっている。ファイルのセット内のデータグループは、互いに特定の物理アドレス関係を持つ必要はない。データグループは、ファイルの連続するオフセットアドレスを有するファイルデータのセットであり、１つのメモリブロックの連続する物理アドレスでプログラミングが行われる。通常、数多くのデータグループとして、ファイルに対しプログラミングを行う。データグループの長さは、１バイトから１ブロックの間とすることができる。ファイルインデックステーブル（ＦＩＴ）２０５により、オフセットアドレスの順で、識別すべきファイルの有効なデータグループの位置の記録を行う。ＦＩＴレコードとしてファイルのＦＩＴエントリのセットについてわかり、ディレクトリ２０３のエントリで指定されている。
【０１００】
ＦＩＴ２０５は、２つの構成要素、アクティブファイルインデックスブロック２０７および１つ以上の非アクティブファイルインデックステーブルブロック２０９を有している。直接データファイル装置内のアクティブファイルのＦＩＴレコードは、アクティブファイルインデックスブロック２０７に配置されている。以下に説明するように、このブロックに対し、ディレクトリ２０３が間接アドレス指定を行うことにより、それらのファイルのディレクトリ２０３のエントリの更新を行う必要なく、アクティブファイルのＦＩＴレコードを修正することが可能になる。非アクティブファイルに対して、ファイルディレクトリ２０３が直接、非アクティブファイルインデックスブロック２０９にＦＩＴレコードのアドレス指定を行う。いずれの場合も、ＦＩＴレコードにより、一意のファイルＩＤ２０１により個別に指定するファイルを構成するデータグループ２１１の位置を指定する。参照するために、部分的なファイルのファイルＩＤを含んでいるヘッダで、各データグループに対しプログラミングを行ってもよい。図１８の２１３に示すように、ファイルのデータを記憶してあるブロックを解放した後で必要になるといったように、ファイルのＦＩＴレコードを修正してもよい。
【０１０１】
共通の構成部品を同じ参照番号で識別した、図１８を多少拡張したものを図１９に示す。複数の非アクティブファイルインデックスブロック２０９を示す。非アクティブＦＩＴプログラムブロック２０９ａは、新規に書き込みが行われたデータファイルの新しいＦＩＴレコードの書き込みが行われる消去を行ったメモリページを有している。一旦、このブロックが満杯になると、非アクティブファイルＦＩＴブロック２０９ｂとして指定し、新しい消去ブロックを非アクティブＦＩＴプログラムブロックとして指定する。典型的には、ファイルディレクトリ２０３は、システムに保持している各ファイルＩＤに対して、ＦＩＴブロック２０７、２０９ａおよび２０９ｂすべてのＦＩＴレコードを指す。
【０１０２】
アクティブファイルインデックスブロック２０７、または非アクティブファイルインデックスブロック２０９のうちの１つに特定のファイルのＦＩＴレコードを記憶してあるかどうかは、近い将来、ファイルに修正を行う可能性が高いかどうかに依存する。高ければ、ブロック内２０７にそのＦＩＴレコードを保持してあるアクティブファイルであると考えられ、高くなければ、ブロック２０９のうちの１つにそのＦＩＴレコードを保持してある非アクティブファイルであると考えられる。メモリシステムが、“開いているファイル”および“閉じているファイル”コマンドを送信するホストシステムとともに動作している場合、メモリは、開いているファイルはすべてアクティブで、閉じているファイルはすべて非アクティブであると見なす。典型的には、これらのコマンドを用いるホストは、５つなどの所定の数を超えない多数の開いているファイルを保持する。従って、ホストがその開いているファイルに書き込みを行ったデータは、そのＦＩＴレコードがブロック２０７内に記憶してあり、閉じているファイルのＦＩＴレコードはブロック２０９のうちの１つに記憶してある。
【０１０３】
しかし、ホストのなかには、開いているファイルコマンドおよび閉じているファイルコマンドをメモリシステムに送信しないものもある。この場合、ホストのファイルへのデータの書き込みを監視することにより、メモリシステムが、近い将来、ファイルの修正を行う可能性が高いかどうかを判定する。記憶ブロックの始端と終端との間のどこかで、ホストが新しいデータグループの書き込みを終えた場合、可能性が一番大きいと考えられるのは、ホストが、少なくとも少しの間、そのファイルへのデータの書き込みを終えたということである。しかし、記憶ブロックの終端に一致して、新しいデータグループが終わっている場合、ホストには、ファイルへ書き込みを行うデータがもっとあるという可能性が高いと考えられる。この場合、メモリシステムは、データグループが記憶ブロックの終端に一致して終わっていると定義する可能性が一番大きいので、ホストがファイルのデータの書き込みを完了したことを示すものではない。
【０１０４】
直接データファイルインターフェイスシステムのファイルディレクトリ２０３は、システムがサポートしているファイルＩＤ毎に１つのエントリを含んでいる。装置がサポートしている連続するファイルＩＤ値に対応する連続するエントリのセットとして、ディレクトリを編成している。図２０に示すように、指定のファイルＩＤのエントリには、特定の論理ページ内の特定のエントリ番号として直接アクセスすることができる。指定のファイルＩＤのエントリを探すのに、ディレクトリサーチを行う必要はない。
【０１０５】
ディレクトリエントリは、ＦＩＴレコードを構成しているＦＩＴエントリの数とともに、ファイルのデータの索引付け情報を含んでいるＦＩＴレコードの位置を指定している。これを、フィールド２１７および２１９それぞれで図２０に示す。フィールド２１７の内容が非アクティブファイルのレコードを指している場合、ファイルのＦＩＴレコードを記憶しているブロック２０９のうちの１つの位置の物理アドレスを含んでいる。しかし、ファイルがアクティブの場合、フィールド２１７は、以下で説明する、ファイルのＦＩＴエントリの更新または変更を行ったのと同じままになっている中間位置を指す、論理アドレスを含んでいる。
【０１０６】
ディレクトリはＰページの論理ページから構成され、各ページはＥ個のディレクトリエントリから構成されている。従って、ディレクトリはＰ＊Ｅファイルの容量がある。専用の１つ以上のブロックに、ディレクトリを記憶している。Ｄ個のディレクトリブロックが存在する場合、それぞれＰ／Ｄ論理ページを含み、Ｐ／Ｄ＊Ｅファイルの容量がある。含んでいる論理ページの範囲に基づいて、ディレクトリブロックをＤＩＲ０からＤＩＲ（Ｄ−１）と指定する。装置に同時に存在した最大数のファイルから、ディレクトリブロックの数を求める。既存のブロックが割り当てられたファイルＩＤのエントリを含んでいない場合、ディレクトリブロックを加算する。しかし、サポートされているファイルの数が減る場合、ディレクトリを圧縮してもよい。
【０１０７】
論理ページの更新を行うディレクトリブロックに用いられる一例の物理構造について、図２１で説明する。（隣接する縦の点線の間の）各エントリは、ファイルＩＤのＦＩＴレコードの仕様、またはそのファイルＩＤのファイルが存在しないことを示すヌル値を含んでいる。ファイルのデータを含んでいるデータグループの数が、ＦＩＴレコードの許可されている最大数のＦＩＴエントリを超えている場合、継続ファイルＩＤをファイルに割り当てて、継続ＦＩＴレコードを利用できるようにする。継続ファイルＩＤを、ファイルに割り当てられた主ファイルＩＤのディレクトリエントリ内に指定する。ディレクトリは、専用の１つ以上のブロックに位置している。ディレクトリブロックの物理位置を、制御ブロックの制御ログ内のディレクトリブロックリストに定義する。
【０１０８】
図２１に、以下の４つのフィールドを含む、ディレクトリエントリ２２５の説明図を示す。
１）ＦＩＴ論理ブロック＃（２２７）：このフィールドにより、ターゲットファイルＩＤのＦＩＴレコードが位置するＦＩＴ論理ブロック番号の識別を行う。ディレクトリブロック内のＦＩＴブロックポインタの１つにより、対応する物理ブロックアドレスを定義している。一例の物理ポインタ２２９を、図２１に示す。フィールド２２７が、ＦＩＴブロックポインタの１つを指している。アクティブファイルインデックスブロック用に、ＦＩＴ論理ブロックＮを確保している。ＦＩＴ論理ブロック番号の０の値は、装置にファイルが存在しないことを意味している。
２）ＦＩＴ論理ページ＃（２３１）：このフィールドにより、ターゲットファイルＩＤのＦＩＴレコードが位置している、アクティブファイルインデックスブロック２０７または非アクティブＦＩＴブロック２０９（図１９）内の論理ページ番号の識別を行う。アクティブファイルインデックスブロック２０７に記憶しているＦＩＴレコードの位置は（図１９）、レコードが位置しているページの間接アドレスである。非アクティブＦＩＴプログラムブロック２０９ａまたは非アクティブＦＩＴブロック２０９ｂの場合、ページの直接物理アドレスである。
３）ＦＩＴページエントリ＃（２３３）：このフィールドにより、ターゲットファイルＩＤのＦＩＴレコードが始まるページ内の連続するエントリ番号の識別を行う。
４）ＦＩＴエントリ＃（２３５）：このフィールド内の先頭ビットがゼロの場合、このフィールドがターゲットファイルＩＤのＦＩＴレコード内のＦＩＴエントリの数を指定する。このフィールド内の先頭ビットが１の場合、ターゲットファイルＩＤのＦＩＴエントリの数は、ＦＩＴレコードで許可されているＦＩＴエントリの最大数を超えている。この場合、フィールドが、ファイルに用いられる継続ファイルＩＤを指定する。継続ファイルＩＤのディレクトリエントリでは、このフィールドが、ターゲットＩＤと継続ファイルＩＤとの両方のＦＩＴレコード内のＦＩＴエントリの総数を指定する。
【０１０９】
ポインタ２２９の一例である図２１のＦＩＴブロックポインタが、装置に存在するそれぞれのＦＩＴ論理ブロックを指定する。これらは、ディレクトリブロック内の最後にプログラミングが行われたページだけに有効なものである。装置に存在する各ＦＩＴ論理ブロック＃に対し、ＦＩＴブロックポインタが存在する。以下の３つのフィールドが、ＦＩＴブロックポインタに存在する。
１）ＦＩＴブロックアドレス（２３７）：このフィールドが、ディレクトリエントリ２２５のフィールド２２７のＦＩＴ論理ブロック＃に現在割り当てられている物理ブロックアドレスを指定する。
２）有効なＦＩＴレコード＃（２３９）：このフィールドが、ＦＩＴ論理ブロックに存在する有効なファイルの数を指定する。
３）使われなくなったＦＩＴエントリ＃（２４１）：このフィールドが、ＦＩＴ論理ブロックに存在する使われなくなったＦＩＴエントリの数を指定する。
【０１１０】
ディレクトリ論理ページポインタ２４３（図２１）は、ディレクトリブロックの論理対物理ページマッピングとして機能する。１つのポインタが、ブロック内の各論理ページに対して存在し、論理ページの現在の物理ページアドレスを指定する。ディレクトリページポインタエントリは、ディレクトリブロック内の直近にプログラミングを行った物理ページにだけ有効なものである。
【０１１１】
論理ページの単位で、ディレクトリの更新を行う。１つのプログラミング動作で、論理ページ内の任意の数のエントリの更新を行ってもよい。ページの読み出しを行って、１つ以上のエントリの更新を行い、ディレクトリブロックの次に利用可能な消去ページで再プログラミングを行ってもよい。ディレクトリページポインタおよびＦＩＴブロックポインタの再プログラミングを同時に行って、すべてのフィールドの現在の値を指定する。
【０１１２】
ディレクトリブロックの最後のページに対しプログラミングを行った場合、ブロックを圧縮し、消去ブロックに書き換えを行う。これが、新しいディレクトリブロックになる。使われなくなったディレクトリブロックを消去する前に、ディレクトリページポインタが定義するように、有効なページをすべて消去ブロックにコピーすることにより、圧縮を行う。
【０１１３】
ファイルディレクトリが指すファイルインデックステーブル（ＦＩＴ）は、ＦＩＴエントリストリングを含んでいる。各ＦＩＴエントリにより、ファイルオフセットアドレスおよびデータグループのフラッシュメモリ内の物理位置の識別を行う。好ましくは、ＦＩＴは、装置に記憶してあるファイルの有効なデータグループすべてのエントリを含んでいる。使われなくなったデータグループについては、ＦＩＴが索引付けを行う必要はない。ファイル内のデータグループのＦＩＴエントリのセットを、オフセットアドレスの順で、連続するエントリとしてファイルに保持する。ＦＩＴレコードとして、エントリのセットがわかっている。ＦＩＴを、アクティブファイルのインデックスブロックとともにＦＩＴブロックのセットに保持する。装置のデータグループの数により、ＦＩＴブロックの数は変化する。装置の動作の間に、新しいＦＩＴブロックを生成して、ＦＩＴブロックを削除する。
【０１１４】
ＦＩＴの論理構造の一例を、図２２に示す。ファイルのディレクトリエントリのＦＩＴブロックアドレス２３７およびＦＩＴ論理ページ＃２３１（図２１）により、特定のファイルのＦＩＴレコード２４７を検出する。ＦＩＴレコードはそれぞれ、ファイル内のデータグループの連続するＦＩＴエントリのセットを含んでいる。好ましくは、そのセットのエントリは、ファイルオフセットアドレスの順に連続している。
【０１１５】
好ましくは、ファイルの各ＦＩＴレコードは、ＦＩＴレコードの第１のエントリとして、ＦＩＴヘッダ２４９（図２２）を含んでいる。ＦＩＴヘッダの固定長は、整数のＦＩＴエントリに等しい。ＦＩＴヘッダの３つのフィールドは以下のとおりである。
１）ファイルＩＤ：ファイルＩＤにより、ディレクトリ内のファイルのエントリの識別を行う。
２）プログラムブロック：ＦＩＴに更新したバージョンのＦＩＴレコードの書き込みを行うときは必ず、ＦＩＴヘッダにファイルのプログラムブロックの現在の物理位置を記録する。ホストがファイルを再び開くときに、これを用いることにより、ファイルのプログラムブロックを検出する。プログラムブロックの統合に選択した、ＦＩＴレコードとファイルのプログラムブロックとの対応関係の検査を行うのに利用してもよい。
３）プログラムポインタ：ＦＩＴに更新したバージョンのＦＩＴレコードの書き込みを行うときは必ず、ＦＩＴヘッダにファイルのプログラムブロック内のプログラムポインタの現在の値を記録する。ホストがファイルを再び開くとき、あるいはプログラムブロック統合にプログラムブロックを選択したときに、これを用いることにより、ファイルのプログラムブロック内でデータのプログラミングを行う位置を定義する。
【０１１６】
典型的には、ファイルのＦＩＴレコードには、ファイルを構成するデータグループの物理位置を指定する多数のエントリがさらにある。一例のファイルに対する１つのＦＩＴエントリ２５１を、他のものとともに図２２に示す。各ＦＩＴエントリには以下の４つのフィールドがある。
１）オフセットアドレス：オフセットアドレスは、データグループの最初のバイトに関連する、ファイル内のバイト表示のオフセットである。
２）長さ：これにより、データグループ内のファイルデータ長さをバイト表示で定義する。完全なデータグループの長さは、データグループヘッダの長さの分だけ、この値よりも長い。
３）ポインタ：これは、データグループが始まるフラッシュブロック内の位置を示すポインタである。ポインタには、（１）データグループを含んでいる物理ブロックを定義するブロックアドレスと、（２）データグループが始まるブロック内のバイトオフセットを定義するバイトアドレスの２つのサブフィールドがある。このアドレスは、データグループヘッダを含んでいる。
４）ＥＯＦフラグ：ＥＯＦフラグは、データファイルの終端のデータグループの識別を行う１つのビットである。
【０１１７】
図２３は、アクティブファイルインデックスブロック２０７（図１８および図１９）の物理フォーマットを示す。アクティブファイル専用のインデックスブロック内で、アクティブファイルのＦＩＴレコードの更新が行われている。ブロックのページ毎に１つ以上のエントリのＦＩＴレコード１つだけ記憶し、論理ＦＩＴレコードの間接アドレス指定を行うことにより、アクティブファイルインデックスブロックに、ＦＩＴレコードの更新を容易に行うことが可能になる。論理ＦＩＴレコードの更新を行う際に、次に利用可能な消去ページの全体に書き換えを行って、この直近でプログラミングを行ったページのＦＩＴページポインタのセットにより、論理ページ対物理ページのマッピングを行う。システムで同時にアクティブとなるファイル毎に、１つの論理ＦＩＴレコードが存在する。
【０１１８】
前述したように、ディレクトリエントリ内の対応するＦＩＴ論理ブロック＃２２７がアクティブファイルインデックスブロックに関係する場合、ファイルのファイルディレクトリエントリ内のＦＩＴ論理ページ＃２３１（図２１）が、論理ＦＩＴレコードを指定する。ファイルのファイルディレクトリエントリの更新を行う必要なく、アクティブファイルインデックスブロックに、論理ＦＩＴレコードの更新および書き換えを行う。ＦＩＴ論理ページ＃２３１はＦＩＴレコードの間接アドレスであり、更新したＦＩＴレコードを含んでいるページの一部として、ＦＩＴ論理ページポインタ２５５のセットのうちの１つが更新および書き換えを行った物理ページに対し、マッピングを行う。
【０１１９】
アクティブファイルインデックスブロック２０７の直近にプログラミングが行われたページ内のＦＩＴページポインタ２５５のセット（図２３）は、有効なバージョンの論理ＦＩＴレコードが配置されている物理ページを指定する。ＦＩＴページポインタのヌル値は、アクティブファイルインデックスブロック内のＦＩＴ論理ページ＃が割り当てられていないことを意味している。装置に同時に存在するアクティブファイル毎に、ＦＩＴページポインタフィールドが１つ存在する。
【０１２０】
アクティブファイルインデックスブロックの最後のページに対しプログラミングを行う場合、ブロックを圧縮し、消去ブロックに書き換えを行うと、新しいアクティブファイルインデックスブロックになる。使われなくなったアクティブファイルプログラムブロックの消去を行う前に、ＦＩＴページポインタが定義したように、有効なページをすべて、消去ブロックにコピーすることにより、圧縮を行う。
【０１２１】
閉じることでアクティブファイルが非アクティブになったり、以下に説明する非アクティブＦＩＴプログラムブロックにそのＦＩＴレコードをコピーしたりすると、アクティブＦＩＴブロック内のＦＩＴレコードのデータが使われなくなる。
【０１２２】
非アクティブＦＩＴブロックが、現在アクティブであるファイルの他に、メモリシステムに記憶してあるデータファイルすべてのＦＩＴレコードの記憶領域となる。１つのＦＩＴプログラムブロックが、ＦＩＴブロック内のＦＩＴレコードのプログラミングを行う手段となる。図２４を参照して、非アクティブファイルＦＩＴプログラムブロック２０９ａ（図１９）の詳細を示す。非アクティブＦＩＴプログラムブロック内の全ページに対しプログラミングを行った場合、これが非アクティブＦＩＴブロック２０９ｂになり、消去ブロックを新しい非アクティブＦＩＴプログラムブロックとして割り当てる。
【０１２３】
図２４に示すように、ディレクトリから直接、非アクティブＦＩＴプログラムブロック内の各ＦＩＴレコードのアドレス指定を行う。ディレクトリエントリ内のＦＩＴ論理ページ＃２３１（図２１）が、非アクティブＦＩＴプログラムブロック内の物理ページを直接指し、ディレクトリエントリ内のＦＩＴページエントリ＃２３３が、ＦＩＴレコードの始点の識別を行う。複数のＦＩＴレコードを、非アクティブＦＩＴプログラムブロック内の１ページに記憶してもよい。
【０１２４】
好ましくは、図２０に示すように、図２４の非アクティブＦＩＴプログラムブロックのページ内のＦＩＴレコードすべてに、ディレクトリの同じ論理ページ内のディレクトリエントリがなければならないようにする。これにより、ディレクトリブロック内で１つのプログラム動作で、非アクティブＦＩＴプログラムブロックページ内のＦＩＴレコードすべてのディレクトリエントリの更新を行うことが可能になる。
【０１２５】
開くことでファイルがアクティブになったり、アクティブファイルインデックスブロック内でそのＦＩＴレコードを生成したり、またはファイルを削除したりする場合、非アクティブＦＩＴプログラムブロック内のＦＩＴレコードはすべて使われなくなる。
【０１２６】
図２４の非アクティブＦＩＴプログラムブロックの最後のページに対しプログラミングを行った場合、非アクティブＦＩＴブロック２０９ｂ（図１９）を生成する。
【０１２７】
図２５は、ＦＩＴレコードの一例の動作を示す。１つのこのような動作２６１により、アクティブファイルにデータの書き込みが行われる。アクティブファイルにデータの書き込みが行われているときに、時折、ファイルデータのプログラミングを行うアルゴリズムがＦＩＴの更新を要求する。アクティブファイルインデックスブロック２０７に、書き込みが行われているファイルの更新ＦＩＴレコードのプログラミングを行う。前述した図２３に示すように、アクティブファイルインデックスブロック内の論理ＦＩＴレコードに間接アドレス指定方法を用いているので、ファイルのディレクトリエントリの更新を行う必要はない。
【０１２８】
既存の非アクティブデータファイルまたは新しいデータファイルを開いたり、アクティブにしたりした場合、図２５に機能２６３として示すように、ブロック内のＦＩＴページポインタフィールドでそのポインタの書き込みを行うことにより（図２３を参照）、アクティブファイルインデックスブロック２０７に論理ＦＩＴレコードを割り当てる。ファイルが既存のファイルの場合、そのＦＩＴレコードも、アクティブファイルインデックスブロック２０７からＦＩＴブロック２０９ｂまたはＦＩＴプログラムブロック２０９ａ内のその既存の位置に移動する。アクティブファイルインデックスブロック２０７内の１回のページプログラミング動作で、ＦＩＴページポインタフィールドおよびＦＩＴレコードの書き込みを行ってもよい。開いているファイルまたはアクティブになっているファイルのディレクトリエントリを更新するためにはディレクトリ内で１ページだけ更新を行うだけでよい。
【０１２９】
図２５の２６５に、データファイルが閉じている状態を示す。ファイルを閉じて、アクティブファイルが非アクティブになった場合、アクティブファイルインデックスブロック２０７からＦＩＴプログラムブロック２０９ａにそのＦＩＴレコードを移動する。ＦＩＴプログラムブロック２０９ａに、このＦＩＴレコードを含んでいるページのプログラミングを行った場合、好ましくは、同じディレクトリページに関連するできるだけ多くのＦＩＴレコードを、ＦＩＴブロックからＦＩＴプログラムブロック２０９ａの同じページに移動する。これにより、使われなくなったＦＩＴエントリを含んでいるＦＩＴブロックのガーベッジコレクション機構となる。すでに含まれている使われなくなったＦＩＴエントリの数に基づいて、このようなＦＩＴレコードを移動するためのソースＦＩＴブロックを選択する必要がある。使われなくなったＦＩＴエントリの数が最も高いＦＩＴブロックに、最も高い優先順位を与える。好ましくは、定義済みの数の使われなくなったＦＩＴエントリより少ない数のＦＩＴブロックからは、ＦＩＴレコードを移動しない。
【０１３０】
最後にプログラミングが行われたディレクトリページ内のＦＩＴブロックポインタフィールドに、ＦＩＴブロック内の使われなくなったＦＩＴエントリの数を定義する。ディレクトリページに対しプログラミングを行って、移動したＦＩＴレコードのエントリの更新と、ＦＩＴブロックポインタおよびディレクトリページポインタフィールド内のパラメータの更新を行う必要がある。アクティブファイルインデックスブロックページに対しプログラミングを行って、ブロックから移動した論理ＦＩＴレコードのＦＩＴページポインタにヌルエントリを挿入する必要がある。
【０１３１】
ガーベッジコレクション動作２６７（図２５）は、ＦＩＴブロックのガーベッジコレクション、またはデータファイルやデータブロックのガーベッジコレクションのいずれかに関連することができる。まず、ＦＩＴブロック２０９ｂのうちの１つのガーベッジコレクションについて説明する。ＦＩＴブロックの消去動作は、使われなくなったＦＩＴエントリが占有する容量を回収するために、時折行う必要がある。ＦＩＴブロックの消去を行う前に、有効なＦＩＴレコードすべてを、ＦＩＴブロック２０９ｂからＦＩＴプログラムブロック２０９ａに移動する。ファイルを非アクティブにする前述した処理を行っても、有効なＦＩＴレコードすべてを移動することにはならない。従って、ＦＩＴガーベッジコレクション処理を行って、有効なＦＩＴレコードすべてを消去するＦＩＴブロックから移動することが望ましい。
【０１３２】
好ましくは、使われなくなったＦＩＴエントリの数が最も高いＦＩＴブロックを、ＦＩＴガーベッジコレクションブロックとして指定し、次に、有効なＦＩＴレコードすべてを移動するまで、このブロックにＦＩＴガーベッジコレクション動作を行う必要がある。次に、別のＦＩＴブロックを、ＦＩＴガーベッジコレクションブロックとして指定する。ＦＩＴガーベッジコレクションブロックのページを選択してＦＩＴプログラムブロックに移動し、利用可能ならば、同じディレクトリページに関連するＦＩＴガーベッジコレクションブロックからの他のＦＩＴレコードで、ページを埋める。プログラミングを行うページにまだ空間がある場合、他のＦＩＴブロックからのＦＩＴレコードでさらに埋めてもよい。関連するディレクトリページ内のエントリに基づいて、選択したページとともに移動する他のＦＩＴレコードの選択を行う必要がある。
【０１３３】
好ましくは、ディレクトリページに対しプログラミングを行って、移動したＦＩＴレコードのエントリの更新、ＦＩＴブロックポインタおよびディレクトリページポインタフィールド内のパラメータの更新を行う。望ましくは、ＦＩＴガーベッジコレクション動作のスケジュールをたてて、データガーベッジコレクション動作を行うのと同時に、定期的に行う。データガーベッジコレクションのページプログラム動作をＮ回行う毎に、ＦＩＴガーベッジコレクションのページプログラム動作を１回行う。
【０１３４】
ここで、データファイルまたはデータブロックのガーベッジコレクション２６７について説明する。データガーベッジコレクション動作により、閉じたファイルまたは非アクティブになったファイルのＦＩＴレコードの更新が必要となる。これを、必要な更新を組み込んで、ＦＩＴレコードをＦＩＴブロックからＦＩＴプログラムブロックに移動することにより実行する。好ましくは、ＦＩＴプログラムブロックにプログラミングが行われているページを、同じディレクトリページに関連する他のＦＩＴレコードで埋める。
【０１３５】
具体的なファイル索引付けを行う第２の実施形態
ファイルＩＤが識別したファイルオブジェクト内の直接データファイルメモリシステムに、データの書き込みを行って、論理オフセットアドレスにより、ファイルオブジェクト内にファイルのアドレス指定を行う。データを、データセットグループとして記憶する。グループはそれぞれ、連続する論理オフセットアドレスおよび連続する物理位置を有している。ファイル索引付けにより、ファイルＩＤおよび論理オフセットアドレスをデータグループの位置と関係付ける。
【０１３６】
ディレクトリにより、ファイルオブジェクトのインデックスエントリのファイルインデックステーブル（ＦＩＴ）内の位置を直接定義する。通常、直接索引付けを用いるが、間接索引付け方法も用いることにより、結果として行う必要があるファイルディレクトリの修正を行わずに、あるファイルのインデックスエントリが頻繁に修正可能になる。ファイル索引付けも、やはりファイルデータからの別々のファイル属性情報の記憶をサポートする。
【０１３７】
ＤＦＳ装置内のファイルは、１つの論理ＩＤを有するデータオブジェクトである。数値ファイルＩＤによりファイルの識別を行い、ファイル内のデータをオフセットアドレスで識別する。
【０１３８】
ホストからのコマンドに応答して、ＤＦＳ装置がファイルＩＤ値の割り当てを行って、ファイルオブジェクトを生成する。ＤＦＳシステムがファイル索引付けを行って、各ファイルオブジェクト内のデータの物理位置と、各ファイルオブジェクトの属性の物理位置とを追跡する。
【０１３９】
ファイル索引付けの階層を、図２６に示す。ファイルのディレクトリエントリは、３つの主なフィールドである、一意のファイルＩＤと、メモリ内の他のアドレスを示す２つのポインタとを含んでいる。ポインタ１は、ＦＩＴ内のそのファイルＩＤのあるファイルのＦＩＴレコードを指し、ポインタ２は、ファイルのファイル属性レコード（ＡＴＲ）を指す。好ましくは、ディレクトリ、ＦＩＴ、ＡＴＲを、フラッシュメモリ内の別々のセットのブロックに記憶する。
【０１４０】
ディレクトリは、装置に存在するファイルオブジェクト毎に１つエントリを含んでいる。範囲がそれぞれ別々のページに割り当てられた、ファイルＩＤ値の重複しない範囲に、エントリを記憶する。ファイルＩＤ値に基づいて、範囲内のエントリは順序づけられている。ページ内の１ページの読み出しと、バイナリサーチを行うことにより、目的とするファイルＩＤのディレクトリエントリを検出することができる。
【０１４１】
占有する空間を最小限にするために、エントリにより、それぞれディレクトリに直接ファイルインデックステーブル（ＦＩＴ）のアドレス指定を行う。これは、ページに編成したファイルオブジェクトを記述する、レコードの集まりから構成されている。同じまたは別のＦＩＴブロックのプログラミングを行わない位置にページを移動する、読み出し／修正／書き込み動作により、ＦＩＴ内の１ページのレコードの更新を行う。ＦＩＴ内の１ページのレコードはすべて、ディレクトリ内の同じページのエントリに関連しているので、ＦＩＴページの更新を行うと、結果として、１つのディレクトリページを１ページだけ修正することが必要になる。
【０１４２】
個別の一時ファイルインデックステーブル（ＴＦＩＴ）ブロックを用いて、近い将来修正することになるＦＩＴレコードを記憶することができる。ファイルオブジェクトのレコードをＴＦＩＴ内の論理ページに記憶して、ディレクトリエントリにより、間接アドレス指定を行う。ディレクトリの更新を行う必要なく、ＴＦＩＴ内のレコードを修正することが可能である。
【０１４３】
ファイルＩＤにより識別したファイルオブジェクトに対し、ファイル属性レコード（ＡＴＲ）を記憶する。属性レコードの内容はホストシステムが定義済みで、メモリシステムは解釈を行わない。一般に、ホストがメモリシステムとともに動作するのに重要または役に立つと考えられる場合は必ず、ホストはファイルオブジェクトの属性をＡＴＲに記憶することが可能である。ファイル属性の索引付け方法は、ファイルインデックステーブルを用いる場合と同じである。
【０１４４】
直接データファイルメモリシステムに用いられる一例のファイル索引付け構造のセットを、図２７に示す。ファイルディレクトリＤＩＲは、ファイルＩＤにより識別したファイルオブジェクトを記述しているエントリの集まりを含んでいる。メモリシステムに存在するファイルオブジェクト毎に１つ、ＤＩＲにエントリがある。ＤＩＲは、１つ以上の専用ＤＩＲブロックに含まれている。
【０１４５】
各ＤＩＲブロックは、固定数の論理ページを含んでいる。次に利用可能な物理ページに書き換えを行うことにより、それぞれの更新を行う。有効なＤＩＲエントリを含んでいるページを論理ページ番号に割り当てる。ＤＩＲブロック内の論理ページの数を、１ブロック内の物理ページの数の２５％となるように指定する。
【０１４６】
ＤＩＲブロックの最後のページの書き込みを行った後で、消去ブロックに有効なページすべての書き込みを行って、もともとのＤＩＲブロックの消去を行うことにより、ブロックを圧縮する。
【０１４７】
ＤＩＲページは、ファイルＩＤ値の順で、ＤＩＲエントリのセットを含んでいる。有効なＤＩＲエントリは、ＤＩＲページ内の連続するセットのエントリ位置を占有しているが、完全にページを埋める必要はない。セット内には使われなくなったエントリがなくなり、ファイルＩＤ値が連続している必要はない。ＤＩＲページ内のファイルＩＤ値の範囲は、他のＤＩＲページ内のファイルＩＤ値の範囲と重複していない。
【０１４８】
新しいファイルのエントリの挿入が必要な場合、新しいブロックのファイルＩＤ値を含むファイルＩＤ範囲があるＤＩＲページを、ＤＩＲインデックス内の情報から識別する。ファイルＩＤ範囲内の適切位置に新しいエントリを挿入し、ＤＩＲページの書き換えを行う。エントリの移動が必要な場合、エントリなしでＤＩＲページを圧縮して、書き換えを行う。
【０１４９】
満杯になったＤＩＲページにさらに追加を行う場合、フリーの論理ページを新しいＤＩＲページとして割り当て、満杯になったＤＩＲページのファイルＩＤ範囲を２つのほぼ等しい重複しない範囲に分割し、２つの利用可能なＤＩＲページに書き込みを行う。
【０１５０】
隣接するファイルＩＤ範囲がある２つのＤＩＲページの有効なエントリの総数が、ＤＩＲページ内のエントリ位置の数の７０％を下回る場合、２つのＤＩＲページの範囲を統合して、２つのＤＩＲページのうちの１つに書き込みを行う。そして、他の使われていないページがフリーの論理ページになる。
【０１５１】
図２７のＤＩＲブロックのＤＩＲエントリは、３つのフィールドを含んでいる。
１）ファイルＩＤ
２）ＦＩＴレコードを示すポインタ（ポインタにより、ＦＩＴレコードのＦＩＴページ論理識別子およびバイトオフセットを定義する。具体例では、ＦＩＴページ論理識別子が、同じＤＩＲページ内のエントリが参照する、１６ページまでの個別のＦＩＴページのうちの１つの識別を行う。これを、エントリを含んでいるＤＩＲページ内のＦＩＴインデックスフィールドにより、物理ブロックアドレスおよびページ番号に変換する。バイトオフセットにより、識別されたＦＩＴページ内のＦＩＴレコードの位置の識別を行う。あるいは、ポインタがＴＦＩＴを示してもよい。ＦＩＴレコードがＴＦＩＴにあることと、ポインタがＴＦＩＴ内の論理ページを定義することを示すように、ポインタ内の保留ビットを設定する。）
３）ファイル属性レコードを示すポインタ（ポインタが、ＡＴＲレコードのＡＴＲページ論理識別子およびバイトオフセットを定義する。具体例では、ＡＴＲページ論理識別子により、ＤＩＲページ内のエントリが参照する、１６ページまでの個別のＡＴＲページのうちの１つの識別を行う。これを、エントリを含んでいるＤＩＲページ内のＦＩＴインデックスフィールドにより、物理ブロックアドレスおよびページ番号に変換する。バイトオフセットにより、識別したＡＴＲページ内のＡＴＲレコードの位置の識別を行う。）
【０１５２】
有効なＤＩＲページごとに、有効なＦＩＴインデックスフィールドが個別に存在する。これを用いることにより、ＦＩＴページの論理識別子を、ＦＩＴページが位置する物理ブロックアドレスおよびページ番号に変換する。ＦＩＴレコードを示すページのエントリ内で用いられる論理識別子毎に、エントリを１つ含んでいる。
【０１５３】
有効なＤＩＲインデックスフィールドは、直近に書き込みが行われたＤＩＲページだけに存在する。前に書き込みが行われたＤＩＲページすべてのフィールド内の情報が使われなくなる。その目的は、ＤＩＲエントリの順序と、論理ページの物理ページへのマッピングとをサポートすることである。
【０１５４】
ＤＩＲインデックスは、論理ページ番号に基づいて順序づけられた考えられる論理ページ毎に、エントリを１つ含んでいる。各エントリには３つのフィールドがある。
１．論理ページの割り当て状態フラグ
２．ページ内の第１のエントリに関連するファイルＩＤ（これにより、各ＤＩＲページ内のファイルＩＤ値の範囲を設定してキャッシュを行うことが可能になる。）
３．論理ページのマッピングを行うＤＩＲ内の物理ページを示すポインタ
【０１５５】
図２７のＦＩＴは、レコードの集まりを含んでいる。それぞれ、制御データおよびファイルＩＤにより識別したファイルオブジェクトのファイルデータ索引付け情報を含んでいる。装置に存在するファイルオブジェクトのＦＩＴまたはＴＦＩＴ毎に、エントリが１つ存在する。ほとんどのファイルオブジェクトのＦＩＴレコードをＦＩＴに記憶し、ＴＦＩＴは、近い将来修正を行う確率が高いファイルオブジェクトだけのＦＩＴレコードを含んでいる。
【０１５６】
ＤＩＲエントリにより、直接ＦＩＴ内のＦＩＴレコードのアドレス指定を行い、ＦＩＴページを修正する際には、ＤＩＲページの修正を行う必要がある。
【０１５７】
ＦＩＴは、１つ以上の専用ＦＩＴブロックに含まれている。ＦＩＴレコードの書き込みが行われるプログラミングを行わないページを、ＦＩＴブロックが１つだけ含んでいる。このブロック内の次のプログラミングを行わないページの位置で、ＦＩＴレコード情報すべてのプログラミングを行い、ＦＩＴ書き込みポインタにより識別する。ブロック内の最後のページに対しプログラミングを行った場合、ＦＩＴ書き込みポインタを、消去ブロックの最初のページに移動する。ＦＩＴブロックは、書き換えられたＦＩＴページから得られる使われなくなったページと、取り除かれたＤＩＲエントリから得られる有効なＦＩＴページ内の使われなくなったＦＩＴレコードとを含んでいることもある。使われなくなった容量を、ＦＩＴブロックから解放してもよい。
【０１５８】
ＦＩＴページは、ＤＩＲエントリにより参照するＦＩＴレコードのセットを、ＤＩＲページ内のエントリとして、同じＤＩＲページに同じ順序で含んでいる。ＤＩＲページは、複数のＦＩＴページを参照することもある。従って、ＦＩＴページの修正を行うと、結果として、ＤＩＲページを１ページだけ修正することが必要になる。ページを読み出し、次に、更新を行ったり、または１つ以上のＦＩＴレコードを加えたりすることにより、ＦＩＴページを修正してもよい。ページを圧縮することにより、使われなくなったＦＩＴレコードを取り除き、次に、ＦＩＴ書き込みポインタにより識別した位置で、ページのプログラミングを行う。
【０１５９】
ＦＩＴページヘッダは、ＦＩＴページが対応づけられているＤＩＲページと、ＦＩＴページ内のＦＩＴレコード情報の長さとに対する参照を記憶している。ＦＩＴページヘッダは、ＦＩＴページの書き込みを行った際に、それぞれのＦＩＴブロックに存在する使われなくなったページの数の記録についても、記憶している場合もある。典型的には、この情報は、直近で書き込みが行われたＦＩＴページヘッダ内でだけ有効である。
図２７のＦＩＴブロックのＦＩＴレコードは、以下のフィールドを含んでいる。
１）ファイルＩＤ
２）ファイル状態（前に援用されている米国特許出願第１１／３８２，２２４号（特許文献３３）に記載されているように、これは０〜９の番号で、各状態は、ファイルのデータを含むことが許可されている物理ブロックの種類の、位置に定義した組み合わせを指定している。典型的には、ファイルの状態が変わる際に、そのファイルの１つ以上のデータグループが変わったために、ＦＩＴレコードの更新が必要になる。）
３）ファイルのアクティブブロックのアドレス
４）ファイル内のデータグループの数
５）以下を含む、ファイル内の各データグループ毎に１つのフィールド
ａ）ファイル内のバイト表示の論理オフセット
ｂ）バイト表示の長さ
ｃ）物理位置を示すポインタ
【０１６０】
図２７のＴＦＩＴブロックを用いることにより、一時的なＦＩＴレコード、すなわち、近い将来修正を行う確率が高いＦＩＴレコードを記憶することが可能になる。第１の実施形態で説明したように、例えば、これにより、開いているファイルコマンドおよび閉じているファイルコマンドを利用するシステムに、開いているファイルを組み込むことが可能になる。ＤＩＲエントリにより、間接的にＴＦＩＴ内のＦＩＴレコードのアドレス指定を行い、ＤＩＲを更新する必要なく、ＴＦＩＴエントリを修正することが可能になる。
【０１６１】
ＴＦＩＴは、固定数の論理ページを含んでいる１つの専用ＴＦＩＴブロックに含まれている。次に利用可能な物理ページに書き換えを行うことにより、各論理ページの更新を行う。有効なＴＦＩＴエントリを含んでいるページに、論理ページ番号を割り当てる。ブロック内の物理ページの数の２５％となるように、ＴＦＩＴブロック内の論理ページの数を指定する。
【０１６２】
ＴＦＩＴブロックの最後のページの書き込みが行われた後で、有効なページすべてを消去ブロックに書き込みを行って、もともとのＴＦＩＴブロックの消去を行うことにより、ブロックを圧縮する。ＦＩＴレコードは、ＦＩＴおよびＴＦＩＴの両方に、同時に存在することはない。
【０１６３】
ＴＦＩＴページは、ＦＩＴレコードを１つだけ含んでいる。ＴＦＩＴ内のＦＩＴレコードは、ＦＩＴブロックの前述したものと全く同じこともある。有効なＴＦＩＴインデックスフィールドは、直近に書き込みが行われたＴＦＩＴページだけに存在する。前に書き込みが行われたＴＦＩＴページすべてのフィールド内の情報が使われなくなる。その目的は、論理ページを物理ページにマッピングを行うことである。ＴＦＩＴインデックスは、論理ページ番号に基づいて順序づけられた考えられる論理ページ毎に、エントリを１つ含んでいる。各エントリには２つのフィールドがある。
１．論理ページの割り当て状態フラグ
２．論理ページのマッピングを行う、ＴＦＩＴ内の物理ページを示すポインタ
【０１６４】
図２７のＡＴＴＲブロックは、レコードの集まりであり、それぞれ、ファイルＩＤにより識別したファイルオブジェクトの属性を含んでいる。属性レコードの内容はホストシステムが定義済みで、メモリシステムが解釈を行わない。ホストが属性の書き込みを行うファイルオブジェクト毎に、ＡＴＲにエントリが１つ存在する。ＤＩＲエントリにより、直接ＡＴＴＲブロック内のＡＴＲレコードのアドレス指定を行い、ＡＴＲページを修正する際に、ＤＩＲページを修正する。
【０１６５】
ＡＴＲは、１つ以上の専用ＡＴＴＲブロックに含まれている。ＡＴＲブロック１つだけが、ＡＴＲレコードの書き込みが行われるプログラミングを行わないページを含んでいる。ＡＴＴＲブロックは、書き換えられたＡＴＲページから得られる使われなくなったページと、削除したファイルから得られる有効なＡＴＲページ内の使われなくなったＡＴＲレコードとを含むこともある。
【０１６６】
１ページのＡＴＴＲブロックは、ＤＩＲページのエントリと同じ順序で、同じＤＩＲページ内のＤＩＲエントリにより参照する、ＡＴＲレコードのセットを含んでいる。ＤＩＲページは、複数のＡＴＲページを参照してもよい。従って、ＡＴＲページの修正を行うと、結果として、ＤＩＲページを１ページだけ修正することが必要になる。
【０１６７】
ＡＴＲページのヘッダは、ＡＴＲページが対応づけられたＤＩＲページと、ＡＴＲページ内のＡＴＲレコード情報の長さとに対する参照を記憶している。ＡＴＲページのヘッダは、ＡＴＲページの書き込みが行われたときにＡＴＴＲブロックそれぞれに存在する使われなくなったページの数の記録を含んでいる場合もある。典型的には、この情報は、直近に書き込みが行われたＡＴＲページのヘッダにだけ有効である。ＡＴＲレコードは、以下のフィールドを含んでいる。
１）ファイルＩＤ
２）ＡＴＲレコードの長さ
３）ＡＴＲレコードの内容（属性レコードの内容は、ホストシステムが定義済みなので、ＤＦＳシステムが解釈することはない。）
【０１６８】
前述したように、データグループは、ファイル内の連続する論理オフセットアドレスを有するファイルデータのセットであり、１つのブロック内の連続する物理アドレスでプログラミングが行われる。複数のデータグループとして、ファイルのプログラミングを頻繁に行う。データグループは、１バイトから１ブロックの間の任意の長さであってよい。好ましくは、ヘッダで各データグループのプログラミングを行い、一部のファイルのファイルＩＤを含んでいる。
【０１６９】
ＦＩＴレコードは１つ以上のＦＩＴブロックに含まれ、ＤＩＲエントリにより、直接アドレス指定が行われる。１つだけのＦＩＴブロックが、新しいまたは更新したＦＩＴレコードのプログラミングを行うのに利用可能な消去ページを含んでいる。他のＦＩＴブロックすべてにおいて、ページすべてに対しプログラミングを行うが、ブロックは、完全に使われなくなったページまたは部分的に使われなくなったページを含む場合もある。
【０１７０】
１つのＦＩＴブロックを次に解放するブロックとして指定することにより、使われなくなったＦＩＴレコードが占有するこの容量を解放し、解放ブロックの消去を行う前に、この解放ブロックからＦＩＴ書き込みポインタが現在指定しているページへ、継続的にページコピーを行う。
【０１７１】
ＦＩＴブロックの前の解放処理が完了し、ブロックの消去を行う場合に、解放ブロックを選択する。使われなくなったページの数が最も大きいＦＩＴブロックを、解放ブロックとして選択する。直近に書き込みが行われたＦＩＴページのＦＩＴページヘッダ内のＦＩＴブロック毎に、この値を記録する。ＦＩＴ書き込みポインタを含んでいるＦＩＴブロックを選択して、解放する必要はない。解放処理が完了して、そのブロックを消去するまで、選択したＦＩＴブロックは、解放ブロックとして残る。
【０１７２】
使われなくなったページを含んでいるＦＩＴブロックを解放する処理には、スケジュールした間隔での個別のバーストで、このブロックからＦＩＴ書き込みポインタが指定するページに、有効なＦＩＴレコードを含んでいる小さい数のページのコピーを行うことが必要である。１回のバーストでのページの数は、メタページに含まれるページの数でなければならない。メタページの１回のプログラミング動作として、ＦＩＴ書き込みポインタの示すページのプログラミングを行う必要がある。
【０１７３】
４メタページに含まれるページの位置の数を介して、ＦＩＴ書き込みポインタの進行により、定義済みの間隔で、解放ブロック内のページのバーストコピー動作のスケジュールをたてる必要がある。バーストコピー動作のスケジュールをたてたときに、書き込みポインタが物理メタページ内の最初のページを指す。
【０１７４】
同じ解放処理を、ＡＴＴＲブロックに別々に行ってもよい。
【０１７５】
実施形態の変形例
前述した２つの具体的なファイル索引付けを行う実施形態それぞれにおいて、ホストからのデータのページと、ＦＩＴエントリと、ディレクトリエントリとをすべて、１つ以上のブロックの別々のグループに記憶してある。この構成の第１の変形例として、ディレクトリエントリを含んでいるページおよびＦＩＴレコードを含んでいるページが、同じブロックにともに存在していてもよい。図２０に示すように、ブロック内の複数の論理ページは、ディレクトリエントリを含んでいる。特定のファイルＩＤのディレクトリエントリは、ブロック内にわかっている論理アドレスがある。図２１に示すように、各論理ページは、論理ページポインタのセットも含んでいる。これらは、ブロック内のディレクトリページの論理対物理ページマッピングとして機能する。ブロック内の論理ページ毎に、ポインタは１つあり、論理ページの現在の物理ページアドレスを指定する。ＦＩＴレコードを含んでいるＦＩＴページは、ブロック内に存在することもある。ＦＩＴページを論理ページには割り当てないが、ディレクトリエントリにより、物理ページ位置で直接アドレス指定を行う。ＦＩＴページ内の１つ以上のＦＩＴレコードの更新を行う場合、ＦＩＴページの位置を関連するディレクトリエントリから識別して、ページの読み出しを行って、関連するレコードを修正し、ブロック内の次に利用可能なプログラミングが行われないページに更新したページの書き込みを行う。ディレクトリエントリを更新して、この新しいＦＩＴページ位置に直接アドレス指定を行うために、１つのディレクトリ論理ページの修正を行って、更新したＦＩＴページが占有する位置に続く物理ページ位置に、プログラミングを行う。このディレクトリページの論理ページポインタも、同じ動作で更新してプログラミングを行う。ブロック内の論理ページすべての論理ページポインタは、ブロック内の最後に書き込みが行われたディレクトリページ内でだけ有効であって、これは常に、ブロック内の最後に書き込みが行われたページである。
【０１７６】
あるいは、ＦＩＴページは論理ページポインタのセットを含んでいてもよいし、ＦＩＴページは、ブロック内の最後に書き込みが行われたページであってもよい。
【０１７７】
２つの具体的なファイル索引付けを行う実施形態で説明した構成のさらに別の変形例において、ディレクトリエントリを含んでいるページと、ＦＩＴレコードを含んでいるページと、ホストからのデータを含んでいるページとが、同じブロックにともに存在していてもよい。ホストからデータの書き込みを行う場合、データグループの形式で、ブロック内の複数の連続する物理ページにプログラミングを行う。このデータグループの位置を、更新したＦＩＴページ内の関連するＦＩＴレコードのフィールドにより識別する。これは、データグループの終端のすぐ次の物理ページにプログラミングを行う。ディレクトリページも、ＦＩＴページのすぐ後にプログラミングを行って、前述したように、更新したＦＩＴページ内のＦＩＴレコードすべてを示すポインタの更新を行う。
【０１７８】
データグループがブロック内の３番目の最後のページを超えないようにすることで、このすぐ後に、ＦＩＴページおよびディレクトリページのプログラミングを行うことが可能になる。
【０１７９】
まとめ
例示の実施形態に関連して本発明の様々な態様を説明してきたが、本発明が添付の特許請求の範囲の全範囲内においてその権利が保護されるべきであることが理解できよう。
【図面の簡単な説明】
【０１８０】
【図１】現在実施されているものとしてホストと接続している不揮発性メモリシステムとを概略的に示す。
【図２】図１の不揮発性メモリとして用いられる一例のフラッシュメモリシステムのブロック図である。
【図３】図２のシステムで用いられるメモリセルアレイの典型的な回路図である。
【図４】図２のシステムの一例の物理メモリ構成を示す。
【図５】図４の物理メモリの部分拡大図である。
【図６】図４および図５の物理メモリの別の部分拡大図である。
【図７】ホストと再プログラム可能なメモリシステムとの間の一般的な従来技術の論理アドレスインターフェイスを示す。
【図８】ホストと再プログラム可能なメモリシステムとの間の、図７に示すものとはやり方が異なる一般的な従来技術の論理アドレスインターフェイスを示す。
【図９】本発明によるホストと再プログラム可能なメモリシステムとの間の直接ファイル記憶インターフェイスを示す。
【図１０】本発明によるホストと再プログラム可能なメモリシステムとの間の、図９に示すものとはやり方が異なる直接ファイル記憶インターフェイスを示す。
【図１１】直接データファイル記憶インターフェイスと協働するメモリシステムの機能ブロック図である。
【図１２】直接データファイルメモリの動作周期を示す。
【図１３Ａ】ファイルのデータを直接メモリに書き込む例を示す。
【図１３Ｂ】ファイルのデータを直接メモリに書き込む他の例を示す。
【図１３Ｃ】ファイルのデータを直接メモリに書き込む他の例を示す。
【図１３Ｄ】ファイルのデータを直接メモリに書き込む他の例を示す。
【図１４Ａ】１つのデータファイルを直接メモリに書き込みを行うシーケンスを示す。
【図１４Ｂ】１つのデータファイルを直接メモリに書き込みを行うシーケンスを示す。
【図１４Ｃ】１つのデータファイルを直接メモリに書き込みを行うシーケンスを示す。
【図１４Ｄ】１つのデータファイルを直接メモリに書き込みを行うシーケンスを示す。
【図１４Ｅ】１つのデータファイルを直接メモリに書き込みを行うシーケンスを示す。
【図１５】図１４Ｅのブロックを解放した結果を示す。
【図１６】データグループ１つと、使われなくなったデータとを含んでいるブロックの解放を示す。
【図１７】図１４Ａ、図１４Ｃ、図１４Ｅ、図１５および図１６のデータグループのＦＩＴのエントリを示す。
【図１８】具体的なファイル索引付けを行う第１の実施形態の、アクティブおよび非アクティブファイルに異なるＦＩＴ構造を用いるファイル索引付けの原理を示す。
【図１９】図１８の説明を拡張して示す。
【図２０】図１８および図１９のファイルディレクトリの一例の論理構造を示す。
【図２１】図１８および図１９のファイルディレクトリを含んでいるメモリブロックの物理構造を示す。
【図２２】図１８および図１９のＦＩＴの論理構造を示す。
【図２３】アクティブファイルのＦＩＴエントリ（ＴＦＩＴ）を含んでいるブロックの物理構造を示す。
【図２４】非アクティブファイルのＦＩＴエントリを含んでいるブロックの物理構造を示す。
【図２５】図１９の一例のファイル索引付けにおけるＦＩＴレコードに実行する動作を示す。
【図２６】具体的なファイル索引付けを行う第２の実施形態による、ファイル索引付けの階層を示す。
【図２７】図２６の実施形態におけるファイル属性のファイルディレクトリ専用のメモリブロック、ＦＩＴおよび表の一例のデータ構造を示す。
【図１】
2009503740.tif 000003
【図２】
2009503740.tif 000004
【図３】
2009503740.tif 000005
【図４】
2009503740.tif 000006
【図５】
2009503740.tif 000007
【図６】
2009503740.tif 000008
【図７】
2009503740.tif 000009
【図８】
2009503740.tif 000010
【図９】
2009503740.tif 000011
【図１０】
2009503740.tif 000012
【図１１】
2009503740.tif 000013
【図１２】
2009503740.tif 000014
【図１３Ａ】
2009503740.tif 000015
【図１３Ｂ】
2009503740.tif 000016
【図１３Ｃ】
2009503740.tif 000017
【図１３Ｄ】
2009503740.tif 000018
【図１４Ａ】
2009503740.tif 000019
【図１４Ｂ】
2009503740.tif 000020
【図１４Ｃ】
2009503740.tif 000021
【図１４Ｄ】
2009503740.tif 000022
【図１４Ｅ】
2009503740.tif 000023
【図１５】
2009503740.tif 000024
【図１６】
2009503740.tif 000025
【図１７】
2009503740.tif 000026
【図１８】
2009503740.tif 000027
【図１９】
2009503740.tif 000028
【図２０】
2009503740.tif 000029
【図２１】
2009503740.tif 000030
【図２２】
2009503740.tif 000031
【図２３】
2009503740.tif 000032
【図２４】
2009503740.tif 000033
【図２５】
2009503740.tif 000034
【図２６】
2009503740.tif 000035
【図２７】
2009503740.tif 000036
【国際調査報告】
2009503740.tif 000037
2009503740.tif 000038