説明

ダイレクトデータファイルメモリシステムにおけるLBAインターフェイスの管理

物理メモリセルブロックを備える通常タイプのフラッシュメモリシステムの連続論理アドレス空間インターフェイス(LBAインターフェイス)の1つ以上の論理ブロックの中で、データファイルにアドレスを割り当てる。この割り当てはホスト装置で行うことができ、データファイルは通常ならばホスト装置によって生成されるが、必ずしもそうとは限らない。物理メモリブロックにおけるファイルデータの断片化の量を抑えて良好なメモリ性能を維持するため、いずれか1つのファイルのデータを収容する論理ブロックの数を規制する。ホストは、これに接続するメモリの物理的特性を学習し、これに応じてアドレス空間の論理ブロックを構成できる。

【発明の詳細な説明】
【技術分野】
【0001】
本願は、一般的にはデータを蓄積し、接続されたホスト装置とデータをやり取りする、再プログラム可能な半導体フラッシュメモリ等の不揮発性メモリシステムの操作に関し、より具体的にはそこでのデータファイルオブジェクトの管理に関する。
【背景技術】
【0002】
初期世代の商用フラッシュメモリシステムでは、矩形のメモリセルアレイが、標準ディスクドライブセクタのデータ量、すなわち512バイトを各々が蓄積する多数のセルグループに分割されていた。さらに通常ならば、誤り訂正符号(ECC)を蓄積するため、そしてことによるとユーザデータ、および/またはこれを蓄積するメモリセルグループに、関係する他のオーバーヘッドデータを蓄積するため、一定量のデータ、例えば16バイトが、各グループに加わる。それぞれのグループには、まとめて消去できる最低数のメモリセルがある。つまり、1データセクタ、さらにオーバーヘッドデータが含まれる場合はオーバーヘッドデータを蓄積するメモリセル数が事実上の消去単位となる。米国特許第5,602,987号(特許文献1)および第6,426,893号(特許文献2)には、この種のメモリシステムの例が記載されている。フラッシュメモリの特徴として、メモリセルにデータを再度プログラムするには事前にそのメモリセルを消去する必要がある。
【0003】
フラッシュメモリシステムは多くの場合、パーソナルコンピュータやカメラ等、様々なホストと取り外し可能な状態で接続するメモリカードやフラッシュドライブの形で提供されるが、ホストシステムの中に埋め込まれることもある。ホストは通例、メモリへデータを書き込む場合に、メモリシステムの連続する仮想アドレス空間の中でセクタ、クラスタ、あるいはその他のデータ単位に一意な論理アドレスを割り当てる。ホストは、ディスクオペレーティングシステム(DOS)のように、メモリシステムの論理アドレス空間の中のアドレスでデータを読み書きする。メモリシステム内のコントローラは、ホストから受け取った論理アドレスを、メモリアレイの中でデータを実際に蓄積する物理アドレスに翻訳し、これらのアドレス翻訳の経緯を把握する。メモリシステムのデータ蓄積容量は少なくとも、メモリシステム向けに設定される論理アドレス空間全体にわたってアドレスが指定されるデータの量に相当する。
【0004】
後続世代のフラッシュメモリシステムでは、消去単位のサイズが複数セクタのデータを十分に蓄積するメモリセルブロックまで拡大した。メモリシステムが接続されたホストシステムでセクタ等の小さな最小単位でデータのプログラミングや読み出しが行われるとしても、フラッシュメモリの1消去単位には多数のセクタが蓄積される。ホストが論理セクタのデータで更新や差し替えを行うときに、ブロックの中で何セクタかのデータが用済みになることは一般的なことである。ブロックに蓄積されたデータに上書きを行うには事前にブロック全体を消去しなければならないため、新規データや更新データは通常、それを受け入れる容量が残っている別の消去済みブロックに蓄積される。この過程で元のブロックには用済みデータが残り、メモリ内の貴重なスペースを取ることになる。しかし、このブロックの中に有効データが残っていると、このブロックを消去するわけにはいかない。
【0005】
そこでメモリ蓄積容量の有効利用を図るため、部分的に満たされたブロックの有効データを消去済みブロックにコピーすることによってこれを整理統合または回収するのが一般的であり、こうすることでデータのコピー元にあたるブロックは消去でき、その全蓄積容量を再利用できる。データをコピーしてブロック内のデータセクタを論理アドレス順に整理するのも望ましく、こうすることでデータの読み出し速度と読み出しデータをホストへ転送する速度が上がる。そのようなデータコピーがあまりにも頻繁に行われると、メモリシステムの動作性能が低下するおそれがある。これは特に、メモリの蓄積容量が、システムの論理アドレス空間を通じてホストによってアドレスが割り当てられるデータの量と大差ない場合、つまりよくある場合で、メモリシステムの動作に影響する。この場合は、ホストプログラミングコマンドの実行に先立ちデータの整理統合または回収が必要になる。その結果、プログラミングの時間が長引く。
【0006】
一定の半導体領域に蓄積できるデータのビット数を増やすため、ブロックのサイズはメモリシステムの世代交代を通じて拡大している。256以上のデータセクタを蓄積するブロックが一般的になりつつある。加えてデータのプログラミングと読み出しにあたって並列度を高めるため、異なるアレイまたはサブアレイからなる2つ、4つ、またはそれ以上のブロックがしばしばメタブロックとして論理的にリンクされる。そのような大容量操作単位には、メモリシステムを効率的に操作するという課題がともなう。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】米国特許第5,602,987号
【特許文献2】米国特許第6,426,893号
【特許文献3】米国公開特許出願第2006/0031593号
【特許文献4】米国特許第5,570,315号
【特許文献5】米国特許第5,774,397号
【特許文献6】米国特許第6,046,935号
【特許文献7】米国特許第6,373,746号
【特許文献8】米国特許第6,456,528号
【特許文献9】米国特許第6,522,580号
【特許文献10】米国特許第6,771,536号
【特許文献11】米国特許第6,781,877号
【特許文献12】米国公開特許出願第2003/0147278号
【特許文献13】米国特許第6,925,007号
【特許文献14】米国特許第6,763,424号
【特許文献15】米国公開特許出願第2005/0144358号
【特許文献16】米国特許第7,139,864号
【特許文献17】米国公開特許出願第2005/0141313号
【特許文献18】米国公開特許出願第2005/0141312号
【特許文献19】米国公開特許出願第2005/0166087号
【特許文献20】米国公開特許出願第2005/0144365号
【特許文献21】米国公開特許出願第2006/0161722号
【特許文献22】米国公開特許出願第2006/0155921号
【特許文献23】米国公開特許出願第2006/0155922号
【特許文献24】米国公開特許出願第2006/0155920号
【特許文献25】米国公開特許出願第2005/0144357号
【特許文献26】米国公開特許出願第2005/0144363号
【特許文献27】米国公開特許出願第2005/0144367号
【特許文献28】米国特許出願第10/897,049号
【特許文献29】米国特許出願第11/022,369号
【特許文献30】米国特許出願第11/259,423号
【特許文献31】米国特許出願第11/312,985号
【発明の概要】
【0008】
前に相互参照した特許出願では、ホストから提供されるデータファイルオブジェクトをフラッシュメモリに直接蓄積するメモリシステムが説明されている。これは、「背景技術」の欄で前述したホストとメモリシステムとのインターフェイスに連続論理アドレス空間が存在する現在の大部分の商用システムと異なる。「LBAインターフェイス」の場合は通常、個々のデータファイルオブジェクトのデータが多数のメモリセルブロックに存在する。メモリシステムは、通常ならば多数のデータセクタからなるクラスタでホストから提供されるファイルオブジェクトのデータを、個々のデータファイルオブジェクトに対応付けることをしない。ホストは、LBAインターフェイスの中で有効データに現在割り当てられていない未使用論理アドレスを、蓄積のためにメモリシステムへ提供されるデータに割り当てるだけである。メモリシステムは、自身が効率よく作動するようにメモリセルブロックを割り当て受信データを蓄積するが、クラスタがどのデータファイルオブジェクトのものなのかは認識しない。その結果、通常は個々のファイルオブジェクトのデータが断片化され、多数の異なるメモリセルブロックに蓄積される。
【0009】
他方、前に相互参照した特許出願の多くでは、メモリシステムがLBAインターフェイスを通さずホストから直接データファイルオブジェクトを受け取るため、メモリシステムは自身の性能を上げるように個々のファイルデータをメモリセルブロックに割り振ることができる。例えばデータがどのファイルのものなのかが分かるなら、メモリシステムはいずれか1つのデータファイルの蓄積に使うメモリセルブロックの数を制限できる。具体的に、メモリシステムはある1つのファイルオブジェクトのデータのほかに別のファイルオブジェクトのデータをも収容するメモリセルブロックの数を制限できる。その結果、ファイルデータの断片化は制御できる。このため、共通ブロックに蓄積された別のファイルのデータが削除されたり修正されたりするときに生じる用済みデータ領域の再生にあたって、共通ブロックから別の場所に移すことになる有効ファイルデータの量は最小限に抑えられる。その結果、フラッシュメモリシステムの寿命にわたって性能と耐久性が大幅に向上する。
【0010】
メモリシステムの代わりにホストでダイレクトデータファイル管理システムを実装する場合も、そのような性能・耐久性の向上を実現することができる。ホストとメモリシステムとの間には引き続きLBAインターフェイスが存在する。しかし、クラスタのファイルデータをこの単一連続論理アドレス空間に割り振るのではなく、メモリシステム内の物理ブロックに対応するこの空間内の論理アドレスブロックにファイルデータを割り振る。フラッシュメモリシステムの中で、物理メモリセルブロックに対して実施される、前に相互参照した特許出願のファイルデータ管理手法は、ホストの中で、ホスト/メモリシステムインターフェイスの論理アドレス空間の中で連続するアドレスの論理ブロックに対して実施される。この場合のメモリシステムは、現在商業的に普及しているLBAインターフェイスを備える従来のメモリシステムでよい。メモリシステムで作動するダイレクトデータファイルシステムによって、2つ以上のファイルのデータを収容する物理メモリセルブロック数が制限されるように、ホストの中で作動するダイレクトデータファイル管理システムによって、2つ以上のファイルのデータを収容する論理ブロック数は制限できる。物理メモリセルブロックにおける個々のファイルオブジェクトデータの断片化も同様に減少するが、これは物理メモリセルブロックにマップされる論理アドレス空間のブロックを管理することによって達成する。
【0011】
LBAインターフェイスの論理ブロックは、好ましくはデータ蓄積容量等が共通するメモリシステムの物理ブロックにマップされる。具体的に、ホストのダイレクトデータファイルシステムにとっては、ホストによって構成される論理ブロックが、メモリシステムの中でダイレクトデータファイルシステムが作動した場合の物理ブロックと同様に映る。物理メモリブロックの特性、すなわち通常ホストに提供されない情報は、メモリシステムの初期化のときにメモリシステムからホストに提供できる。そして、ホストは連続論理アドレス空間を、物理メモリのブロックに特性が一致するブロックに構成し、その後、それらの論理ブロックの中のアドレスにデータを書き込む。
【0012】
代案として、ダイレクトデータファイルシステムをホストで実装する代わりにメモリシステムで操作し、前述したのと同様に、メモリシステムのLBAインターフェイスの連続アドレス空間にわたって論理ブロックを設定することもできる。このダイレクトデータファイル操作は、メモリシステムの一部であっても、前に相互参照した特許出願で説明された例とは異なる。先行出願の例のように、メモリシステムのバックエンドを操作してLBAインターフェイスに代わってメモリシステムでファイルデータを受け付ける代わりに、メモリシステムのLBAインターフェイスの手前にダイレクトデータファイルシステムを追加し、これを前述したのと同じ要領で、あたかもホストのLBAインターフェイスの手前にあるかのごとく、操作することができる。そのようなメモリシステムにLBAインターフェイスとファイルオブジェクトインターフェイスの両方を設け、両タイプのインターフェイスのうち、いずれか一方のインターフェイスしかないホストと通信することもできる。これは特に、様々なタイプのホスト装置に取り外し可能な状態で接続するように作られたメモリカードの場合に便利である。
【0013】
さらなる代案として、処理能力を持つ取り外し可能なマザーカードに前述したダイレクトデータファイルシステムを設け、ダイレクトファイル機能はなくともダイレクトデータファイルインターフェイスはあるホストに、ダイレクトファイル機能を追加することもできる。ホストに接続されたマザーカードはその出力でLBAインターフェイスを提供し、カードの出力には、LBAインターフェイスを備える標準的なメモリカードを取り外し可能な状態で接続できる。
【0014】
この後に続く本発明の代表的な例の説明には本発明のさらなる態様と利点と特徴が記載されているが、この説明は添付の図面と併せて解釈するべきものである。
【0015】
ここで参照する特許、特許出願、記事、書籍、仕様書、その他の出版物、文書、事物はどれも、あらゆる目的のためにその全体が本願明細書において参照により援用されている。援用する出版物、文書、または事物のいずれかと本願明細書の本文との間で用語の定義または使用に矛盾や食い違いがある場合は、本願明細書における用語の定義または使用が優先するものとする。
【図面の簡単な説明】
【0016】
【図1】ホストおよび接続された不揮発性メモリシステムを概略的に示す。
【図2】図1の不揮発性メモリとして使用されるフラッシュメモリシステム例のブロック図である。
【図3】図2のシステムに使用できるメモリセルアレイの代表的な回路図である。
【図4】図2のシステムの物理メモリ編制例を示す。
【図5】図4の物理メモリの一部分の拡大図を示す。
【図6】図4および図5の物理メモリの一部分のさらなる拡大図を示す。
【図7A】再プログラム可能なメモリシステムを操作する3通りの方法の内のひとつを示し、対比する。
【図7B】再プログラム可能なメモリシステムを操作する3通りの方法の内のひとつを示し、対比する。
【図7C】再プログラム可能なメモリシステムを操作する3通りの方法の内のひとつを示し、対比する。
【図8A】図7A、図7B、および図7Cにそれぞれ見られる再プログラム可能なメモリシステムを操作する3通りの方法のひとつと、ホストシステムとのインターフェイスを示し、対比する。
【図8B】図7A、図7B、および図7Cにそれぞれ見られる再プログラム可能なメモリシステムを操作する3通りの方法のひとつと、ホストシステムとのインターフェイスを示し、対比する。
【図8C】図7A、図7B、および図7Cにそれぞれ見られる再プログラム可能なメモリシステムを操作する3通りの方法のひとつと、ホストシステムとのインターフェイスを示し、対比する。
【図9A】図8A、図8B、および図8Cにそれぞれ見られる再プログラム可能なメモリシステムを操作する3通りの方法のひとつと、ホストとのインターフェイスを示し、対比する。
【図9B】図8A、図8B、および図8Cにそれぞれ見られる再プログラム可能なメモリシステムを操作する3通りの方法のひとつと、ホストとのインターフェイスを示し、対比する。
【図9C】図8A、図8B、および図8Cにそれぞれ見られる再プログラム可能なメモリシステムを操作する3通りの方法のひとつと、ホストとのインターフェイスを示し、対比する。
【図10】図9Cの手法の遂行にあたって使用できる論理−物理ブロックマッピングの一例を示す。
【図11】図9Cおよび図10に示す手法の遂行にあたってパラメータを設定するためのホストおよびメモリシステム間のやり取りを示す。
【図12】ダイレクトデータファイルシステムの動作サイクルを示す。
【図13A】ファイルデータを書き込む4例中のひとつを示す。
【図13B】ファイルデータを書き込む4例中のひとつを示す。
【図13C】ファイルデータを書き込む4例中のひとつを示す。
【図13D】ファイルデータを書き込む4例中のひとつを示す。
【図14A】一連の単一データファイル書き込みを示す。
【図14B】一連の単一データファイル書き込みを示す。
【図14C】一連の単一データファイル書き込みを示す。
【図14D】一連の単一データファイル書き込みを示す。
【図14E】一連の単一データファイル書き込みを示す。
【図15】図14Eのブロックを再生した結果を示す。
【図16A】様々なブロックタイプの組み合わせで蓄積されるデータファイルの例を示す。
【図16B】様々なブロックタイプの組み合わせで蓄積されるデータファイルの例を示す。
【図16C】様々なブロックタイプの組み合わせで蓄積されるデータファイルの例を示す。
【図16D】様々なブロックタイプの組み合わせで蓄積されるデータファイルの例を示す。
【図17】具体例に従い許容ファイル状態を提示する表である。
【図18】プログラムデータに基づく許容ファイル状態遷移を示す状態図である。
【図19】図18に見られるファイル状態遷移を説明する表である。
【図20】用済みデータに基づく許容ファイル状態遷移を示す状態図である。
【図21】図20に見られるファイル状態遷移を説明する表である。
【図22】再生ブロックに基づく許容ファイル状態遷移を示す状態図である。
【図23】図22に見られるファイル状態遷移を説明する表である。
【図24】データファイルと論理ブロックとの整合の一実施形態を示す。
【図25】図24のデータ整合の実施形態で、様々な状況のもとでのアクティブブロック割り当てを示す表である。
【図26】データファイルと論理ブロックとの整合の代替の実施形態を示す。
【図27】図26のデータ整合の実施形態で、様々な状況のもとでのアクティブブロック割り当てを示す表である。
【図28A】ブロック再生操作の例を示す。
【図28B】ブロック再生操作の例を示す。
【図28C】ブロック再生操作の例を示す。
【図28D】ブロック再生操作の例を示す。
【図29】再生操作を一般的な用語で説明するフローチャートである。
【図30】典型的なパーシャルメモリセルブロックに蓄積されるデータのタイプを示す。
【図31】図29のフローチャートの1ステップを遂行する具体的な実施形態の詳細を提示する。
【図32】図29のフローチャートの同じステップを実行する代替の実施形態の詳細を提示する。
【図33】別の実施形態で2つのブロックリストに入るブロックタイプを明らかにする表である。
【発明を実施するための形態】
【0017】
フラッシュメモリシステムの概説
一般的なフラッシュメモリシステムを図1〜図6との関係で説明する。そのようなシステムで本発明の様々な態様を実装できる。図1のホストシステム1は、フラッシュメモリ2の中にデータを蓄積し、このフラッシュメモリからデータを引き出す。フラッシュメモリはホストの中に埋め込むこともできるが、メモリ2はより一般的なカードの形で図に示され、このカードは、機械的および電気的コネクタの嵌合部分3および4を通じて取り外し可能な状態でホストへ接続される。例えばコンパクトフラッシュ(CF)、マルチメディアカード(MMC)、セキュアデジタル(SD)、ミニSD、メモリスティック、スマートメディア、トランスフラッシュカード等、様々なフラッシュメモリカードが現在市販されている。これらのカードはいずれも、それぞれの規格化された仕様に従い特有の機械的および/または電気的インターフェイスを備えているが、それぞれに内蔵されたフラッシュメモリシステムはよく似ている。これらのカードはいずれも、本願の出願人であるサンディスク コーポレイションから入手できる。また、サンディスク コーポレイションは、Cruzerという商標のもとで一連のフラッシュドライブを提供し、このフラッシュドライブはユニバーサルシリアルバス(USB)プラグを備える小型の手持ち式メモリシステムで、これをホストのUSB差込口に差し込むことによりホストと接続する。これらのメモリカードとフラッシュドライブはコントローラを内蔵し、このコントローラがホストと連係し、内蔵されたフラッシュメモリの動作を制御する。
【0018】
そのようなメモリカードやフラッシュドライブを使用するホストシステムは数多くあり様々である。ここにはパーソナルコンピュータ(PC)、ラップトップをはじめとするポータブルコンピュータ、携帯電話機、個人用携帯情報端末(PDA)、デジタル静止画カメラ、デジタル動画カメラ、ポータブルオーディオプレイヤ等が含まれる。ホストは通常ならば1種類以上のメモリカードまたはフラッシュドライブのための一体化された差込口を内蔵するが、メモリカードを差し込むアダプタが必要なものもある。
【0019】
図1のホストシステム1は、メモリ2に関する限り、回路とソフトウェアとの組み合わせからなる2つの主要部分を備えるとみなすことができる。それらはアプリケーション部5と、メモリ2と連係するドライバ部6である。例えばパーソナルコンピュータの場合、アプリケーション部5はプロセッサを含み、ワープロ、グラフィック、コントロール等、一般的なアプリケーションソフトウェアを実行する。カメラや携帯電話機等、専ら1組の機能を遂行する専用ホストシステムの場合、アプリケーション部5は、カメラを操作しながら写真を撮影したり蓄積したりするソフトウェアや、携帯電話機を操作しながら電話をかけたり受けたりするソフトウェアを含む。
【0020】
図1のメモリシステム2はフラッシュメモリ7と回路8とを含み、この回路はカードが接続されるホストと連係しながらデータをやり取りし、メモリ7を制御する。コントローラ8は通常、データのプログラミングと読み出しのときにホスト1によって使用されるデータの論理アドレスとメモリ7の物理アドレスとの変換を行う。
【0021】
図2を参照すると、図1の不揮発性メモリ2として使用できる典型的なフラッシュメモリシステムの回路を説明する。システムコントローラは通常、システムバス13沿いに1つ以上の集積回路メモリチップと並列に接続される単一集積回路チップ11上に実装され、図2にはただひとつのそのようなメモリチップ15が示されている。図に示されたバス13は、データを搬送する1セットの導体17と、メモリアドレスのためのセット19と、制御および状態信号のためのセット21とを含む。代わりに、これらの3つの機能で1セットの導体を時分割共用することもできる。さらに、2004年8月9日に出願された「Ring Bus Structure and It's Use in Flash Memory Systems 」という米国特許出願第10/915,039号(米国公開特許出願第2006/0031593号)(特許文献3)で説明されているリングバス等、これとは別のシステムバス構成を使用できる。
【0022】
典型的なコントローラチップ11は、インターフェイス回路25を通じてシステムバス13と連係する独自の内部バス23を有する。このバスへ通常接続される主要機能には、プロセッサ27(マイクロプロセッサ、マイクロコントローラ等)と、システムの初期化(「ブート」)コードを収容する読み出し専用メモリ(ROM)29と、主にメモリとホストとの間で転送されるデータをバッファするために使われるランダムアクセスメモリ(RAM)31とがあり、コントローラを通じてメモリとホストの間を行き来するデータで誤り訂正符号(ECC)を計算し検査する回路33をバス23へ接続することもできる。コントローラを通過するデータを符号化し復号化する専用回路34を盛り込むこともできる。そのような符号化には圧縮やセキュリティ暗号化等があるが、ほとんどのデータ変換はこのやり方で果たすことができる。専用回路33および34を使用する場合は、ファームウェア制御のもとでプロセッサ27によって実行されるアルゴリズムが、これらの回路によって実行される。コントローラバス23は回路35を通じてホストシステムと連係し、メモリカードに内蔵される図2のシステムの場合に、コネクタ4の一部をなすカードの外部接点37を通じて果たされる。クロック39はコントローラ11の他のコンポーネントに接続され、それらのコンポーネントによって利用される。
【0023】
メモリチップ15と、システムバス13に接続される他のメモリチップは通常、複数のサブアレイまたはプレーンに編制されたメモリセルアレイを含み、簡潔を図るために2つのそのようなプレーン41および43が図に示されているが、これよりも多いプレーン、例えば4つ、または8つのプレーンを代わりに使用することもできる。あるいは、チップ15のメモリセルアレイはプレーンに分割しない場合もある。しかし、分割するなら、各プレーンは互いに独立して作動する独自の列制御回路45および47を有する。回路45および47は、システムバス13のアドレス部19からそれぞれのメモリセルアレイのアドレスを受け取り、それらを復号化して1つ以上のビット線49および51をアドレスする。ワード線53は、アドレスバス19で受け取るアドレスに応じて行制御回路55によりアドレスされる。ソース電圧制御回路57および59もそれぞれのプレーンに接続し、pウェル電圧制御回路61および63も同様である。メモリチップ15が単一のメモリセルアレイを有し、2つ以上のそのようなチップがシステムに存在する場合は、前述したマルチプレーンチップにおけるプレーンまたはサブアレイと同様に各チップのアレイを操作することができる。
【0024】
データは、システムバス13のデータ部17に接続されたデータ入出力回路65および67を通じてプレーン41および43を出入りする。回路65および67は、それぞれの列制御回路45および47を介してプレーンへ接続する線69および71を通じてそれぞれのプレーンのメモリセルにデータをプログラムし、メモリセルからデータを読み出すためにある。
【0025】
コントローラ11はデータをプログラムするため、データを読み出すため、消去するため、様々なハウスキーピング作業に対処するため、メモリチップ15の動作を制御するが、各々のメモリチップもコントローラ11からのコマンドを実行してそのような機能を遂行する制御回路を内蔵する。インターフェイス回路73はシステムバス13の制御・状態部21へ接続する。コントローラからのコマンドは状態マシン75へ提供され、この状態マシンは、これらのコマンドを実行するために他の回路を制御する。制御線77〜81は、状態マシン75を図2に見られるこれらの他の回路に接続する。状態マシン75からの状態情報は線83に沿ってインターフェイス73へ伝達され、バス部21に沿ってコントローラ11へ送信される。
【0026】
現在はメモリセルアレイ41および43のNANDアーキテクチャが好まれているが、NOR等、これとは別のアーキテクチャを代わりに使用することもできる。NANDフラッシュメモリと、メモリシステムの一部としてのこれの動作の例は、米国特許第5,570,315号(特許文献4)、第5,774,397号(特許文献5)、第6,046,935号(特許文献6)、第6,373,746号(特許文献7)、第6,456,528号(特許文献8)、第6,522,580号(特許文献9)、第6,771,536号(特許文献10)、および第6,781,877号(特許文献11)と米国公開特許出願第2003/0147278号(特許文献12)とで参照できる。
【0027】
図2のメモリシステムのメモリセルアレイ41の一部分にあたる図3の回路図に、NANDアレイの例を示す。多数のグローバルビット線が提供されるが、説明を簡潔にするため、図2には4つのそのような線91〜94だけが示されている。これらのビット線のうちの1ビット線と基準電位との間には、いくつかの直列接続メモリセルストリング97〜104が接続される。メモリセルストリング99を代表としてとりあげ、ストリング両端の選択トランジスタ111および112には複数の電荷蓄積メモリセル107〜110が直列で接続される。1ストリングの選択トランジスタが通電すると、そのビット線と基準電位との間でこのストリングが接続される。そして、そのストリングの中で一度に1つのメモリセルのプログラミングか読み出しが行われる。
【0028】
数あるメモリセルストリングの1メモリセルの電荷蓄積素子にわたって図3のワード線115〜118が延在し、ゲート119および120は、ストリングの末端にある選択トランジスタの状態を制御する。共通のワード線およびコントロールゲート線115〜120を共用するメモリセルストリングが、まとめて消去されるメモリセルのブロック123を形成する。このセルからなるブロックは、一度に物理的に消去できる最小数のセルを収容する。ワード線115〜118のうちの1ワード線沿いの1行のメモリセルが一度にプログラムされる。通常、NANDアレイの行は規定の順序でプログラムされ、この場合は、アース等の共通電位へ接続されたストリングの末端に最も近いワード線118沿いの行から始まる。次にワード線117沿いのメモリセル行がプログラムされ、ブロック123の全体を通じて同様に進む。最後にワード線115沿いの行がプログラムされる。
【0029】
第2のブロック125も類似し、そのメモリセルストリングは第1のブロック123のストリングと同じグローバルビット線へ接続されているが、ワード線とコントロールゲート線は異なる。ワード線とコントロールゲート線は、行制御回路55によって適切な作動電圧まで駆動される。図2のプレーン1および2等、2つ以上のプレーンまたはサブアレイがシステムに存在する場合は、それらの間に延在する共通のワード線を1つのメモリアーキテクチャで使用する。代わりに、3つ以上のプレーンまたはサブアレイが存在して共通のワード線を共用することもある。これとは別のメモリアーキテクチャでは、各プレーンまたはサブアレイのワード線を別々に駆動する。
【0030】
前に参照したいくつかのNAND特許および公開特許出願で説明されているように、3つ以上の検出可能な電荷レベルを各電荷蓄積素子または領域に蓄積することにより、2ビット以上のデータを各々蓄積するようメモリシステムを操作できる。メモリセルの電荷蓄積素子は一般的には導電性フローティングゲートだが、米国特許第6,925,007号(米国特許13)で説明されている非導電性誘電性電荷捕獲材であってもよい。
【0031】
図4は、以降のさらなる説明で一例として使用するフラッシュメモリセルアレイ7(図1)の編制を概念的に示すものである。4つのメモリセルプレーンまたはサブアレイ131〜134は、1つの集積メモリセルチップ上に存在することもあれば、2つのチップ(各チップ上に2プレーンずつ)または4つの別々のチップ上に存在することもある。具体的な配置は以降の論述にとって重要ではない。勿論、システムに存在するプレーンの数はこれに限らず、例えば1、2、8、16またはそれ以上のプレーンが存在することもある。プレーン131〜134に位置するブロック137、138、139、140等、プレーンは図4にて矩形で表示されたメモリセルブロックにそれぞれ分割される。各プレーンには何十、何百ものブロックが存在し得る。前述したように、メモリセルのブロックは消去の単位であって、物理的にまとめて消去できる最小数のメモリセルである。しかし、並列性を高めるためには、これよりも大きいメタブロック単位でブロックを操作する。メタブロックは、各プレーンの1ブロックを論理的にリンクすることによって形成される。4つのブロック137〜140によって1つのメタブロック141が形成される様子が図に示されている。通常ならば、1メタブロック内の全てのセルをまとめて消去する。ブロック145〜148からなる第2のメタブロック143に見られるように、メタブロックを形成するブロックの各プレーンにおける相対位置は同じでなくてもよい。システム性能を高めるため、通常は全てのプレーンにまたがって延在するメタブロックが好ましいが、別々のプレーンにある1ブロック、2ブロック、または3ブロックのいずれかまたは全部から動的にメタブロックを形成しながらメモリシステムを操作することもできる。この場合は、1回のプログラミング操作で蓄積するデータ量にメタブロックのサイズをより近づけることが可能となる。
【0032】
操作上の目的から、各ブロックはさらに図5に示すようにメモリセルページに分割される。例えばブロック131〜134のメモリセルは、それぞれ8つのページP0〜P7に分割されている。代わりに、16、32、またはそれ以上のメモリセルページが各ブロックに存在することもある。ページはブロックの中でデータをプログラムし読み出す単位であり、一度にプログラムされる最少量のデータを収容する。図3のNANDアーキテクチャでは、ブロックの中でワード線沿いのメモリセルからページが形成される。しかし、メモリシステム動作の並列性を高めるため、2つ以上のブロックにあるページをメタページとして論理的にリンクすることもできる。図5には、4つのブロック131〜134の各ブロックにつき1物理ページからなるメタページ151が示されている。例えばメタページ151は4つのブロックのページP2を含んでいるが、メタページのページは必ずしも各ブロック内で同じ相対位置を占めるとは限らない。システム性能を高めるためには、全4つのプレーンにわたって最大量のデータを並行してプログラムし読み出すのが望ましいが、別々のプレーンにあるブロックの1ページ、2ページ、または3ページのいずれかまたは全部からメタページを形成しながらメモリシステムを操作することもできる。この場合は、並列処理のデータ量に応じたプログラミング操作と読み出し操作が可能になるほか、メタページの一部にデータがプログラムされずに残る事態は少なくなる。
【0033】
図5に示す複数プレーンの物理ページからなるメタページは、それらの複数プレーンのワード線行沿いのメモリセルを含む。1ワード線行の全セルを同時にプログラムするよりは、2つ以上のインターリーブされたグループでそれらを交互にプログラムするほうが一般的であり、各グループは、(単一ブロック内の)1ページのデータか(複数ブロックにまたがる)1メタページのデータを蓄積する。交互のメモリセルを一度にプログラムすることにより、データレジスタやセンス増幅器を含むひとまとまりの周辺回路をビット線ごとに用意する必要はなくなり、それらの回路は隣接するビット線で時分割共用する。こうすることで周辺回路に要する基板スペースを節約し、行沿いのメモリセル実装密度を増すことができる。さもなくば、行沿いの全セルを同時にプログラムしてメモリシステムから最大限の並列性を引き出すのが望ましい。
【0034】
図3を参照すると、行沿いの互い違いのメモリセルへのデータの同時プログラミングを最も簡便に果たすには、NANDストリングの少なくとも一端に沿って2行の選択トランジスタ(図示せず)を、図に示された1行の代わりに、提供する。この場合、一方の行の選択トランジスタは、1つの制御信号に応じてブロック内の互い違いのストリングをそれぞれのビット線へ接続し、他方の行の選択トランジスタは、別の制御信号に応じて介在する互い違いのストリングをそれぞれのビット線へ接続する。その結果、メモリセルの各行には2ページ分のデータが書き込まれる。
【0035】
各論理ページのデータ量は通常、整数にして1セクタ数以上のデータであり、各セクタは慣例上512バイトのデータを収容する。図6は、2セクタ153および155分のページまたはメタページデータからなる論理データページを示す。各セクタは通常、512バイトのユーザまたはシステムデータを収容する部分157と、部分157のデータに関係する、またはこれを蓄積する物理ページまたはブロックに関係する、オーバーヘッドデータのため、さらなるバイト数159とを含む。オーバーヘッドデータのバイト数は通常ならば16バイトであり、セクタ153および155の各々につき合計528バイトになる。オーバーヘッド部分159には、プログラミング中にデータ部分157から算出されるECC、その論理アドレス、ブロックが消去され再プログラムされた回数の経験カウント、1つ以上の制御フラグ、作動電圧レベル、および/またはその他に加え、そのようなオーバーヘッドデータ159から算出されるECCを収容できる。あるいは、オーバーヘッドデータ159またはこれの一部分を別のブロックの異なるページに蓄積することもできる。
【0036】
メモリの並列性が高まるにつれメタブロックのデータ蓄積容量は増し、その結果、データページおよびメタページのサイズも増す。データページは3セクタ以上のデータを収容することがある。1データページ内に2セクタ、そして各メタページにつき2データページで、1メタページのセクタ数は4セクタになる。したがって、各メタページで2,048バイトのデータを蓄積することになる。これは高度な並列性であり、行内のメモリセル数の増加にともないさらに高めることができる。このような理由から、ページおよびメタページ内のデータ量を増やすためにフラッシュメモリの幅は拡大されつつある。
【0037】
前述した物理的に小さい再プログラム可能な不揮発性メモリカードおよびフラッシュドライブは市販され、データ蓄積容量は512メガバイト(MB)、1ギガバイト(GB)、2GB、4GBおよびそれ以上になる。
【0038】
ファイルオブジェクト操作手法
論理ブロック(LBA)メモリ/ホストインターフェイスによる操作
図7A、図8A、および図9Aには、ホストおよびメモリシステム間の一般的な論理インターフェイスがそれぞれ異なる形式で示されている。ホストによって生成されるデータファイルには、通常ならばマルチセクタデータからなるクラスタの単位で連続システムアドレス空間(LBAインターフェイス)の論理アドレスがホストによって割り振られる。そして、メモリシステムはこれらの論理アドレスを認識し、データが実際に蓄積されるメモリセルブロックの物理アドレスにマップする。
【0039】
具体的に図9Aを参照すると、連続する論理アドレス空間161には、メモリシステムに蓄積される全データにアドレスを提供するにあたって十分な大きさがある。通常、ホストアドレス空間はデータクラスタの単位に分割される。ホストシステムではいくつかのデータセクタを収容するように各クラスタを設計でき、4〜64セクタあたりが一般的である。標準的なセクタは512バイトのユーザデータに加え、オプションとして何バイトかのオーバーヘッドデータ、通常ならば16バイトのオーバーヘッドデータを、収容し、全部で528バイトになる。
【0040】
図9Aは、ホストと、メモリカードやフラッシュドライブに見られる大容量メモリシステムとの間の最も一般的なインターフェイスを示す。ホストで扱うデータファイルは、ホストによって実行されるアプリケーションソフトウェアかファームウェアプログラムによって生成または使用される。「ファイル」または「ファイルオブジェクト」は、何らかの用途または目的のためにホストにより所定の実体として認識されるひとまとまりのデータを意味する。ファイルオブジェクトのデータはひとつの単位として扱われる。ワープロファイルのデータはその一例であり、コンピュータ支援設計(CAD)ソフトウェアの描画ファイルのデータもこれにあたり、主にPC、ラップトップコンピュータ等、一般的なコンピュータホストに見られる。pdf形式文書のデータもそのようなファイルである。ファイルオブジェクトのデータはアプリケーションプログラムの実行中にホストによって生成されるか、別のところで生成されてホストに提供される。静止画デジタルビデオカメラは写真ごとにデータファイルを生成し、メモリカードに蓄積する。携帯電話機は、電話帳等、内蔵メモリカード上のファイルからデータを利用する。PDAは、住所ファイル、カレンダーファイル等、数通りのファイルのデータを蓄積し使用する。そのような用途においては、ホストを操作するソフトウェアがメモリカードに内蔵されることもある。
【0041】
図9Aの例では、3つのファイル1、2、および3が作成されたものとして示されている。ホストシステムで実行するアプリケーションプログラムは、整頓された1組のデータとして各ファイルを作成し、一意な名前かその他の参照符によってこれを識別する。ファイル1には、別のファイルにまだ割り振られていない十分な使用可能な論理アドレス空間がホストによって割り当てられる。ファイル1は、一連の使用可能な論理アドレス範囲が割り当てられた状態で図に示されている。このほかに、通常ならばホストオペレーティングソフトウェアのための特定のアドレス範囲等、特定の目的のためにアドレス範囲が割り振られ、それらは、たとえホストがデータに論理アドレスを割り当てるときにまだ使われていなくとも、データの蓄積には使われない。
【0042】
図9Aに見られるように、ホストは後ほどファイル2が作成されるときにも同様に、論理アドレス空間161の中の2つの別々の隣接アドレス範囲を割り当てる。隣接する論理アドレスをファイルに割り当てる必要はなく、既に他のファイルに割り振られているアドレス範囲の間にあるアドレスの断片であってもよい。この例はさらに、ホストによって作成されたもうひとつのファイル3に、ファイル1および2やその他のデータにまだ割り振られていないホストアドレス空間の別の部分を割り振る様子を示している。
【0043】
ホストは、ファイルアロケーションテーブル(FAT)を管理することによってメモリ論理アドレス空間を絶えず把握し、ホストが様々なホストファイルに割り当てる論理アドレスは、このファイルアロケーションテーブルの中で管理する。通常、FATテーブルは不揮発性メモリとホストメモリに蓄積され、新しいファイルが蓄積されるとき、他のファイルが削除されるとき、ファイルが修正されるとき等に、ホストによって頻繁に更新される。ホストは、例えばホストファイルが削除されるときにFATテーブルを更新することによって削除ファイルに割り振られていた論理アドレスを解除し、それらの論理アドレスが別のデータファイルに使用できることを明らかにする。
【0044】
ホストは、ファイルの蓄積にあたってメモリシステムコントローラが選択する物理位置を考慮しない。典型的なホストは、その論理アドレス空間と、ホストが種々のファイルに割り振った論理アドレスを、認識するにすぎない。他方、メモリシステムは、典型的なLBAホスト/カードインターフェイスを通じて、論理アドレス空間のうちのデータが書き込まれた部分だけを認識し、特定のホストファイルへ割り振られる論理アドレスは認識せず、ホストファイルの数すら認識しない。メモリシステムコントローラは、データの蓄積や引き出しのためにホストから提供される論理アドレスを、ホストデータを蓄積するフラッシュメモリセルアレイの中の一意な物理アドレスに変換する。ブロック163は、メモリシステムコントローラによって管理される論理−物理アドレス変換の作業テーブルを表している。
【0045】
メモリシステムコントローラは、高度なシステム性能を維持しながらメモリアレイ165のブロックおよびメタブロックの中でデータファイルを蓄積するようにプログラムされる。この例では4つのプレーンまたはサブアレイが使われている。データは好ましくは、各プレーンのブロックから形成されたメタブロック全体にわたってシステムが許す最大限の並列度でプログラムされ、読み出される。通常は、メモリコントローラによって使用されるオペレーティングファームウェアおよびデータを蓄積する予約ブロックとして、少なくとも1つのメタブロック167が割り振られる。ホストオペレーティングソフトウェアやホストFATテーブル等の蓄積のため、別のメタブロック169または複数のメタブロックを割り振ることができる。物理蓄積容量のほとんどはデータファイルの蓄積用として残る。しかし、メモリコントローラは、様々なファイルオブジェクトの中で受信データがホストによってどのように割り振られているかを認識しない。通常、メモリコントローラがホストとのやり取りを通じて知ることは、ホストによって特定の論理アドレスに書き込まれるデータが対応する物理アドレスに蓄積されるということだけであって、これはコントローラの論理−物理アドレステーブル163によって管理される。
【0046】
典型的なメモリシステムにおいて、アドレス空間161の中でデータを蓄積するのとは別に数ブロック分の蓄積容量を余分に用意する。メモリの寿命の中で別のブロックが故障した場合に代用される冗長ブロックとして、これらの余分のブロックを1つ以上用意することができる。当初メタブロックに割り当てられていた欠陥ブロックのための冗長ブロックを代用する等、個々のメタブロックにおけるブロックの論理的分類は通常、様々な理由から変化する。消去済みブロックのプールでは通例、メタブロック171等、1つ以上の追加ブロックを保守する。コントローラはホストがメモリシステムにデータを書き込むときに、ホストによって割り当てられた論理アドレスを、消去済みブロックプールにあるメタブロック内の物理アドレスに変換する。そして、論理アドレス空間161の中でデータ蓄積に使われていないほかのメタブロックは消去され、以降のデータ書き込み操作のときに使用するために消去済みプールのブロックとして指定される。
【0047】
特定のホスト論理アドレスに蓄積されたデータは、当初の蓄積データが用済みになると新規データによって頻繁に上書きされる。これに応じてメモリシステムコントローラは新規データを消去済みブロックに書き込み、論理アドレスのデータを蓄積する新たな物理ブロックを明らかにするためにこれらの論理アドレスに関し論理−物理アドレステーブルを変更する。そして、それらの論理アドレスのところで当初のデータを収容するブロックは消去され、新規データの蓄積に使えるようになる。書き込みが始まるときに消去ブロックプールの消去済みブロックに十分な蓄積容量がない場合は、データ書き込み操作を完了する前にこのような消去を頻繁に行わなければならない。このため、システムのデータプログラミング速度が損なわれるおそれがある。メモリコントローラは通常、ある特定の論理アドレスにあるデータがホストによって用済みとされていることを、ホストがそれと同じ論理アドレスに新しいデータを書き込むときになって初めて知る。したがって、メモリのブロックの多くは、そのような無効データを暫くの間蓄積することがある。
【0048】
集積回路メモリチップの領域を効率よく運用するため、商用メモリシステムに使われるブロックとメタブロックのサイズは拡大している。その結果、データ書き込みの大半で蓄積されるデータの量はメタブロックの蓄積容量に満たなく、多くの場合、ブロックの蓄積容量にすら満たない。メモリシステムコントローラは通常、新規データを消去済みプールのメタブロックへ誘導するため、メタブロックには埋まらない部分が生じる。新規データが別のメタブロックに蓄積されたデータの更新にあたる場合は、その別のメタブロックで論理アドレスが新規データメタページの論理アドレスと隣接する残りの有効データメタページもまた、望ましくは論理アドレスの順序で新しいメタブロックにコピーする。古いメタブロックは他の有効データメタページを保持することがある。その結果、メタブロックのいずれかのメタページのデータはいずれ用済み、無効となり、同じ論理アドレスにより異なるメタブロックに書き込まれる新規データで差し替えられる。
【0049】
論理アドレス空間161の全体にわたってデータ蓄積のための十分な物理メモリ空間を維持するため、データの圧縮または整理統合(ガーベッジコレクション)を定期的に行ってブロックを再生し、消去済みブロックのプールに加える。メタブロックの中でデータセクタをできる限り論理アドレスと同じ順序に保つことも望ましく、こうすることで連続する論理アドレスでデータの読み出し効率が上がる。そこで通常は、この目的のためにもデータの圧縮とガーベッジコレクションが行われる。米国特許第6,763,424号(特許文献14)には、部分的ブロックデータ更新を受け取るときのメモリ管理とメタブロック使用の態様がいくつか記載されている。
【0050】
データ圧縮では通常、メタブロックから有効データメタページを全て読み出して別のブロックに書き込み、その過程で無効データを含むメタページは無視する。また、有効データを含むメタページは、好ましくはそこに蓄積されたデータの論理アドレスの順序に一致する物理アドレス順に配置する。無効データを収容するメタページは新しいメタブロックへコピーされないため、新しいメタブロックに占めるメタページの数は古いメタブロックに占めるメタページの数を下回ることになる。そして、古いブロックを消去し、消去済みブロックプールへ加えて新規データの蓄積に使えるようにする。この整理統合によって得られる追加メタページ容量は、ほかのデータの蓄積に役立てることができる。
【0051】
ガーベッジコレクションのときには、2つ以上のメタブロックから論理アドレスが隣接するかほぼ隣接する有効データのメタページが回収され、別のメタブロック、通常ならば消去済みブロックプールのメタブロックに書き換えられる。当初の2つ以上のメタブロックから全ての有効データメタページをコピーすると、先々の使用に向けてそれらを消去できる。別々のブロックに蓄積されたファイルの断片化が増すにつれ、データの整理統合やガーベッジコレクションの回数も増える。
【0052】
データの整理統合とガーベッジコレクションには時間がかかり、ホストからのコマンドの実行に先立ちデータの整理統合やガーベッジコレクションを行う必要がある場合は特にメモリシステムの性能に影響する。メモリシステムコントローラは通常、そのような操作をできるだけバックグラウンドで行うようスケジュールを組むが、これらの操作の実行にあたっては、コントローラは操作が完了するまでビジー状態信号をホストに提供しなければならない。ホストコマンドの実行が遅れる一例として、ホストがメモリに書き込もうとする全データの蓄積にあたって十分な消去済みメタブロックが消去済みブロックプールにない場合は、事前にデータの整理統合かガーベッジコレクションで1つ以上のメタブロックから有効データを片づける必要があり、その後にメタブロックを消去する。これまで、そのような混乱を最小限に抑えるためにメモリ制御の管理に注意が払われてきた。そのような手法が、2003年12月30日に出願された「Management of Non-Volatile Memory Systems Having Large Erase Blocks 」という米国特許出願第10/749,831号(米国公開特許出願第2005/0144358号)(特許文献15)、2003年12月30日に出願された「Non-Volatile Memory and Method with Block Management System 」という米国特許出願第10/750,155号(米国特許第7,139,864号)(特許文献16)、2004年8月13日に出願された「Non-Volatile Memory and Method with Memory Planes Alignment 」という米国特許出願第10/917,888号(米国公開特許出願第2005/0141313号)(特許文献17)、2004年8月13日に出願された「Non-Volatile Memory and Method with Non-Sequential Update Block Management」という米国特許出願第10/917,867号(米国公開特許出願第2005/0141312号)(特許文献18)、2004年8月13日に出願された「Non-Volatile Memory and Method with Phased Program Failure Handling 」という米国特許出願第10/917,889号(米国公開特許出願第2005/0166087号)(特許文献19)、2004年8月13日に出願された「Non-Volatile Memory and Method with Control Data Management 」という米国特許出願第10/917,725号(米国公開特許出願第2005/0144365号)(特許文献20)、2004年12月16日に出願された「Scratch Pad Block 」という米国特許出願第11/016,285号(米国公開特許出願第2006/0161722号)(特許文献21)、2005年7月27日に出願された「Non-Volatile Memory and Method with Multi-Stream Update Tracking」という米国特許出願第11/192,220号(米国公開特許出願第2006/0155921号)(特許文献22)、2005年7月27日に出願された「Non-Volatile Memory and Method with Improved Indexing for Scratch Pad and Update Blocks 」という米国特許出願第11/192,386号(米国公開特許出願第2006/0155922号)(特許文献23)、および2005年7月27日に出願された「Non-Volatile Memory and Method with Multi-Stream Updating 」という米国特許出願第11/191,686号(米国公開特許出願第2006/0155920号)(特許文献24)で数多く説明されている。
【0053】
非常に大きな消去ブロックを持つメモリアレイの動作を効率的に制御するには、書き込み操作のときに蓄積されるデータセクタの数をメモリのブロックの容量に一致させ、ブロックの境界に揃えることがひとつの課題となる。それには、ホストからの新規データの蓄積に使うメタブロックを最大ブロック数未満で構成し、メタブロック全体を埋め尽くすまでには至らない一定量のデータを蓄積するようにする方法がある。適応メタブロックの使用は、2003年12月30日に出願された「Adaptive Metablocks 」という米国特許出願第10/749,189号(米国公開特許出願第2005/0144357号)(特許文献25)で説明されている。データブロック間の境界とメタブロック間の物理的境界の整合は、2004年5月7日に出願された「Data Boundary Management」という米国特許出願第10/841,118号(米国公開特許出願第2005/0144363号)(特許文献26)と、2004年12月16日に出願された「Data Run Programming」という米国特許出願第11/016,271号(米国公開特許出願第2005/0144367号)(特許文献27)で説明されている。
【0054】
メモリコントローラでは、ホストによって不揮発性メモリに蓄積されるFATテーブルのデータをメモリシステムの効率的作動に役立てることもできる。例えば、論理アドレスの解除によりホストによってデータが用済みと識別されたことを知るのに役立てる。メモリコントローラは、通常ならばホストがその論理アドレスに新規データを書き込むことから知るデータが用済みと識別されたことを、事前に知ることにより、そのような無効データを収容するブロックの消去スケジュールを組むことができる。これは、2004年7月21日に出願された「Method and Apparatus for Maintaining Data in Non-Volatile Memory Systems」という米国特許出願第10/897,049号(特許文献28)で説明されている。このほかの手法として、ホストがメモリに新規データを書き込むパターンを監視することにより、ある特定の書き込み操作が単一のファイルか否かを推定し、複数のファイルである場合にはファイル間の境界がどこにあるかを推定する。2004年12月23日に出願された「FAT Analysis for Optimized Sequential Cluster Management」という米国特許出願第11/022,369号(特許文献29)では、このタイプの手法の使用が説明されている。
【0055】
メモリシステムを効率よく操作するには、ホストによって各ファイルのデータに割り当てられる論理アドレスについて、コントローラができるだけ多くのことを知るのが望ましい。そうすればコントローラは、ファイルの境界が分からなければ多数のメタブロックに散在することになるデータファイルを、1つのメタブロックまたは1群のメタブロックに蓄積することができる。その結果、データの整理統合操作やガーベッジコレクション操作の回数と複雑さが抑えられる。結果的にメモリシステムの性能は向上する。しかし、前述したように、ホスト/メモリインターフェイスが論理アドレス空間161(図9A)を含む場合に、メモリコントローラがホストデータファイル構造について多くを知ることは困難である。
【0056】
ダイレクトデータファイル操作
図7B、図8B、および図9Bに見られるホストと大量データ蓄積用メモリシステムとの各種インターフェイスは、論理アドレス空間の使用を解消する。代わりにホストは、一意なファイルID(またはその他の一意な参照符)とファイル内でのデータ単位(バイト等)によるオフセットアドレスとによって各ファイルのデータを論理的にアドレスする。これらのアドレスはメモリシステムコントローラへ直接提供され、メモリシステムコントローラは、各ホストファイルのデータの物理的な蓄積位置について独自のテーブルを管理する。これは前に相互参照した特許出願の主題にあたる操作である。このファイルインターフェイスは、図2〜図6との関係で前述したものと同じメモリシステムで実装できる。図7B、図8B、および図9Bのファイル本位インターフェイスと図7A、図8A、および図9AのLBAインターフェイスとの主な違いは、メモリシステムがホストシステムと通信しファイルデータを蓄積する方法にある。
【0057】
図8Bのファイル本位インターフェイスと図8AのLBAインターフェイスとを比較した場合、図8Aの論理アドレス空間とホストによって保守されるFATテーブルは図8Bに存在しない。メモリシステムにとっては、ファイル番号とファイル内でのデータオフセットによってホスト生成データファイルが識別される。そして、メモリシステムは、ファイルをメモリセルアレイの物理ブロックに直接マップする。
【0058】
ダイレクトデータファイル蓄積法で新規データファイルをメモリにプログラムする場合は、メモリセルの消去済みブロックにデータが書き込まれ、この書き込みはこのブロック内の最初の物理位置から始まって残りの位置を順次進んでいく。データは、ファイルにおけるこのデータのオフセット順序にかかわりなく、ホストからの受信順序に沿ってプログラムされる。プログラミングは、ファイルの全データがメモリへ書き込まれるまで続く。ファイル内のデータ量が1メモリブロックの容量を上回る場合は、最初のブロックが一杯になった時点で第2の消去済みブロックでプログラミングが継続する。第2のメモリブロックは第1のメモリブロックと同様にプログラムされ、最初の位置からファイルの全データが蓄積されるか、第2のブロックが一杯になるまで続く。ファイルのデータが残っている場合は、3番目以降のブロックにプログラムする。1ファイルのデータを蓄積する複数のブロックまたはメタブロックが物理的または論理的に隣り合っているとは限らない。説明を平易にするため、ここで用いる用語「ブロック」は別段の断りがない限り、システムでメタブロックを使用するか否かに応じて、ブロック消去単位か多重ブロック「メタブロック」を指すものとする。
【0059】
図9Bを参照すると、ファイル1、2、および3の識別情報とファイル内でのデータオフセットはメモリコントローラへ直接引き渡される。この論理アドレス情報はメモリコントローラ機能173によってメモリ165のメタブロックおよびメタページの物理アドレスに翻訳される。ファイルデータは図9Aの論理アドレス空間161にマップされない。
【0060】
フラッシュ最適化ファイルシステムの原理
図7C、図8C、および図9Cは、図7B、図8B、および図9Bのダイレクトデータファイル手法に図7A、図8A、および図9Aに見られるタイプのLBAインターフェイスを組み合わせたオペレーティングシステムを、それぞれ異なる形式で示すものである。図7Cの「フラッシュ最適化ファイルシステム」の動作は図7Bの「ダイレクトファイル蓄積バックエンドシステム」と基本的に同じだが、ファイルデータは図7Cに見られるLBAインターフェイスの連続アドレス空間の中で論理ブロックにマップされ、図7Bに見られるNANDフラッシュの物理メモリセルブロックにはマップされない。図7CのLBAインターフェイスと「LBA−物理バックエンドシステム」は、図7Aのシステムと共通している。図7Cのシステムでは、LBAインターフェイスの前にダイレクトファイル−ブロックアドレス割り当てが行われるが、NANDフラッシュメモリの物理ブロックではなく、LBAインターフェイスの連続アドレス空間に含まれる論理ブロックアドレスを扱う。
【0061】
図8Cには同じ発想が異なる形式で示されている。ホストによって生成されるデータファイルは、蓄積装置の論理アドレス空間に含まれる論理ブロックアドレスに割り当てられる。次に、論理アドレス空間の論理ブロックが従来どおりメモリコントローラによって物理蓄積媒体のブロックにマップされる。図8Cには、ホストとメモリシステムとでこれらの機能を分割した場合の2通りの区分が描かれている。図のホスト1から分かるように、第1の実施形態ではホストの中でファイルを論理ブロックアドレスに割り振る。この場合のメモリ1は従来のメモリカードやその他の装置であって、ホストのLBAインターフェイスと接続するLBAインターフェイスを備える。これとは別に、図8Cのホスト2は、データファイルの識別情報とファイル内でのデータオフセットをメモリシステムとやり取りする。これらのファイルを論理ブロックアドレスに割り振るダイレクトデータファイル機能は、メモリ2の中で実行される。
【0062】
図8Cのメモリ2は、メモリカードやフラッシュドライブをはじめとする小型ポータブル装置の形が最も一般的で、蓄積装置の論理アドレス空間との外部接点を提供することによってLBAインターフェイスを追加することもできる。さらなる代案として、ファイルを論理ブロックアドレスに割り振る機能はマイクロプロセッサを内蔵するマザーカードで実行することもできる。この場合のマザーカードはホスト2と取り外し可能な状態で接続し、メモリ1はマザーカードと取り外し可能な状態で接続する。
【0063】
図9Cには、ファイルオブジェクトのデータを論理アドレス空間にマップする手法が異なる形式で示されている。機能173’は各ファイルのデータを、一意なファイル識別子とファイル内でのデータオフセットアドレスとからなる各論理アドレスと併せて、受信する。これらのファイルアドレスは、機能173’によって連続論理アドレス空間161の論理ブロックに含まれるアドレスに変換される。物理メモリでブロックとメタブロックのどちらの単位を使用するかに応じ、各論理ブロックのアドレス範囲はメモリアレイ165のブロックかメタブロックのデータ蓄積容量と同じになるように設定する。図9Cの機能173’は図9Bの機能173と基本的に同じだが、図9Cではアドレス空間161の論理ブロックにファイルをマップするのに対し、図9Bではファイルをメモリセルアレイ165に直接マップする。次に、論理アドレスブロックは図9Cの機能163によってメモリアレイ165に翻訳されるが、これは図9Aと基本的に同じである。機能163は、前に述べた米国特許第7,139,864号(特許文献16)や米国公開特許出願第2005/0141313号(特許文献17)、第2005/0141312号(特許文献18)、第2005/0166087号(特許文献19)、第2005/0144365号(特許文献20)、および第2006/0161722号(特許文献21)で説明されているもの等、従来のフラッシュメモリオペレーティングシステムであってよい。
【0064】
図9Cでは、アドレス空間161の各論理ブロックのアドレスが2つ以上のファイルのデータにまたがることがあることに気づく。各ファイルのデータに2つ以上の論理ブロックにまたがってアドレスが割り当てられることもある。例えば、データファイル2および3には2つ以上の論理ブロックにまたがってアドレスが割り当てられている。論理ブロックは2つの異なるファイルのデータを収容することもあり、図9Cの論理ブロック2はその例である。しかし、好ましくは、ある1のファイルのデータと他の何らかのファイルのデータを収容する論理ブロックの数には1つ以上の制限を設ける。制限は状況によって異なる。具体例として、ファイルのデータをアドレス空間161のいくつかの論理ブロックに割り振る場合に、いずれか1つのファイルが別のファイルのデータと共有する論理ブロックを2ブロックまでにする。ファイルオブジェクトのデータに論理ブロックアドレスを割り当てるときにこの制約を順守するには、ファイルデータで部分的にしか満たされていない論理ブロックの数を制限する。
【0065】
この制約により、例えば他のファイルのデータが用済みになった場合に必要となるデータ再配置量は少なくなる。通常、このような場合には別ファイルの用済みデータを含むブロックから別のブロックへファイルの有効データをコピーする。ある特定のファイルが別のファイルのデータと共有するブロックの数を制限することにより、このようなデータコピー操作の頻度は低くなる。その結果、メモリシステムの性能は向上する。
【0066】
図10を参照すると、論理ブロックと物理ブロックの両方でファイルデータの割り振りが示されている。例示するため、物理メモリセルブロックの例191は4つのページ195〜199に分割されているが、実際のシステムでは通常ブロック当たりのページ数がこれよりも多くなる。各ページは複数セクタのデータを蓄積する。ブロックの中では通常、195〜199の順序で一度に1ページずつデータをプログラムする。メタブロックを使用するメモリシステムの場合はブロック191がメタブロックとなり、ページ195〜199はメタページになる。
【0067】
物理ブロック191にマップされるのは、論理アドレス空間161の論理ブロック193である。論理ブロック193のデータ蓄積容量は物理ブロック191と同じに設定され、物理ブロック191と同数のページ201〜204に分割され、各論理ページのデータ蓄積容量は物理ページ195〜199のそれぞれと同じである。つまり、好ましくは、論理アドレス空間の粒度が物理メモリページまたはメタページのデータ蓄積容量に等しくなるようにする。論理ブロック193の中では、物理ブロック191にデータページを書き込むのと同じ順序で論理ページのアドレスをデータに割り当てる。論理ブロック193の第1のページ201の先頭におけるデータの書き込みは、物理ブロック191の第1のページ195の先頭で始まるようにする。
【0068】
このような論理・物理機能の連携を保つには、ファイル−論理ブロック翻訳を行うホストが相手方にあたるメモリの物理的特性を知る必要がある。例えばメタブロックを使用するメモリシステムでは、以下のパラメータによってこれらの特性が決まる。
1.蓄積データのセクタ数による物理ページサイズ
2.ともにリンクされ各メタページを形成するページ数によるメタページサイズ
3.1メタブロック当たりのページ数
4.物理メタブロックの第1のページへマップされる最下位論理アドレス
【0069】
ホストはこの情報をもとに論理アドレス空間161の論理ブロック構造を構成し、図10に示すように作動することができる。ホストに埋め込まれたメモリ等、ある特定のホストで使用するメモリが1種類だけならば、ただひとつのホスト論理アドレス空間構成を管理するだけでよい。しかし、物理的特性がそれぞれ異なるポータブルメモリ装置が取り外し可能な状態でホスト装置に接続される場合のほうが一般的であり、実際にはホスト装置も様々である。そこで、接続先にあたる特定のポータブルメモリ装置の物理ブロック構成に論理ブロック構成を適合させるための機能をホストの中に用意する。それには、前述したメモリパラメータのデータをメモリ装置そのものに蓄積し、ホストで読み出されるようにする。通常、論理ブロックに対応する物理ブロックはメモリシステムのコントローラによって変更されるが、ホストがこれを知ることはなく、論理ブロックへのファイルデータのアドレス割り当てには影響しない。
【0070】
図11は、これらのパラメータデータを不揮発性蓄積領域209に収容するメモリ装置207を示すものであり、ホスト211は相互接続バス213を通じてこれにアクセスする。ホストがこれらのパラメータを読み出す方法は数多くある。一例として、ベンダー固有のコマンドを設定し、これをメモリ装置207の初期化中にホスト211からメモリ装置へ発行する。作動したメモリ装置207は、蓄積されたパラメータ値をホストへ返す。もうひとつの例として、メモリ装置207がホスト211からの既存標準コマンドに応じてホストへ返す既存フィールドの未使用部分に、これらのパラメータを盛り込むこともできる。ドライブ識別コマンドはそのようなコマンドの一例である。
【0071】
代表的なフラッシュ最適化ファイルシステム
この節では、個々のファイルを連続論理アドレス空間の論理ブロックにマップする手法の代表的な実施例をさらに詳しく説明する。この手法のいくつかの態様は、基本的に同じ機能である図7Cの「フラッシュ最適化ファイルシステム」と、図8Cの「論理ブロックアドレスへのファイルの割り振り」と、図9Cの「ファイル/オフセット−論理アドレス変換」173’との関係で既に説明している。
【0072】
論理ブロックアドレスへのファイルマッピングについてこの節で説明する内容の大半は、前に相互参照した特許出願で説明されている物理メモリセルブロックアドレスにファイルをマップする手法と同じ手法を利用する。主な違いは、相互参照した先行特許出願に説明されているように、データファイルをそのまま物理メモリブロックにマップしてLBAインターフェイスを回避する代わりに、例えばホスト装置により、LBAインターフェイスにまたがってファイルマッピングを行うことにある。先行出願の物理メモリブロックマッピング手法を応用し、LBAアドレス空間の論理ブロックにデータファイルオブジェクトをマップすることも可能であり、ここではその例をいくつか説明する。
【0073】
ファイルオブジェクトの論理的マッピングに関するここでの説明では、LBAインターフェイスのブロックにデータが「書き込まれる」、または「プログラムされる」と言う。当然ながら、これらの論理ブロックは物理メモリブロックと違って実際にはデータを蓄積しないため、これは特定の論理ブロックに対してデータのアドレスを指定することを意味する。同様に、データが割り振られていない論理ブロックのことを「消去済み」と言う。「消去済み」論理ブロックはデータのアドレスがない論理ブロックであり、完全に空いていてデータのアドレスを割り当てることができる。「部分的に消去済み」の論理ブロックもあり、これはその論理ブロックの一部分が空いていて、データのさらなるアドレスを受け付け可能であることを意味する。
【0074】
フラッシュ最適化ファイルシステムの一般的動作
メモリに新規のデータファイルをプログラムするときには空いている論理ブロックにデータが書き込まれ、この書き込みはこのブロック内の最初の位置から始まって残りの位置を順次進んでいく。データは、ファイルにおけるこのデータのオフセット順序にかかわりなく、ホストからの受信順序に沿って論理ブロック内にプログラムされる。プログラミングは、ファイルの全データが書き込まれるまで続く。ファイル内のデータ量が1論理ブロックの容量を上回る場合は、最初のブロックが一杯になった時点で第2の空の(消去済み)ブロックでプログラミングを継続する。第2の論理ブロックは第1の論理ブロックと同様にプログラムされ、最初の位置からファイルの全データが割り振られるか、第2のブロックが一杯になるまで続く。ファイルのデータが残っている場合は、3番目以降のブロックにプログラムする。1ファイルのデータを蓄積する複数の論理ブロックまたはメタブロックが隣り合っているとは限らない。説明を平易にするため、ここで用いる用語、論理「ブロック」は別段の断りがない限り、システムでメタブロックを使用するか否かに応じて、メモリシステムにおける物理ブロックの最小消去単位と同じ容量を持つ論理ブロックか、通常まとめて消去される多重ブロック物理メタブロックに対応する多重ブロック論理「メタブロック」を指すものとする。
【0075】
図12は、フラッシュ最適化ファイルシステムの全体的な働きを示す。個々の論理ブロックは3つの状態のいずれか1つにあるとみなすことができる。3つの状態とは、消去済みブロック641と、有効ファイルデータを蓄積し再生可能な容量がないブロック643と、ある程度の有効ファイルデータのほかに再生可能な容量もあるブロック645であって、ブロック645の場合は、そこにある未プログラム(消去済み)ページおよび/または用済み(無効)データから容量を再生できる。機能647によって消去済み論理ブロックへデータが書き込まれると、プログラムされたブロックに再生可能な容量が残るか否かに応じて当該ブロックはカテゴリ643か645のブロックになる。機能649に表示されているようにファイルが削除されると、ファイルデータを収容しているブロック643は再生可能な容量を持つブロック645に変わる。機能650で再生可能なブロックから別のブロックへデータをコピーした後には、ブロック645の未使用蓄積容量が機能651によって再生され、その結果、ブロックは消去済みブロック641の状態に戻り、新たにデータを書き込むことができる。
【0076】
図13Aを参照すると、論理アドレス空間に対するデータファイルの書き込みが示されている。この例のデータファイル181は、垂直の実線間に広がる1ブロックまたはメタブロック183の蓄積容量より大きい。このため、データファイル181の部分184は第2のブロック185にも書き込まれる。これらの論理ブロックはアドレスが隣接するものとして図に示されているが、必ずしも隣接するとは限らない。ファイル181のデータはホストから受信されるにつれ書き込まれ、最終的にはファイルの全データが論理アドレス空間へ書き込まれる。図13Aの例で、データ181はファイルの最初のデータである。
【0077】
メモリシステムで蓄積データを管理し追跡するには、可変サイズのデータグループを使用するのが好ましい。つまり、所定の順序につなげて完全なファイルを形成する複数のデータグループとしてファイルのデータを蓄積する。ホストからのデータストリームを書き込むときに、ファイルデータの論理オフセットアドレスやデータを割り振る論理アドレス空間に途切れが生じると、新たなデータグループが始まる。例えば、ファイルのデータによってあるひとつの論理ブロックが一杯になり、別のブロックへの書き込みが始まると、そのような途切れが論理アドレス空間に生じる。これを示す図13Aでは、第1のブロック183が第1のデータグループで満たされ、ファイルの残りの部分184は第2のデータグループとして第2のブロック185に蓄積されている。第1のデータグループは(F0,D0)で表すことができ、F0はデータファイルの先頭の論理オフセットであり、D0は論理ブロック183の中でファイルが始まる位置である。第2のデータグループは(F1,D1)で表され、F1は第2のブロック185の先頭に蓄積されるデータのファイルオフセットであり、D1は第2のブロックの先頭の論理アドレスである。
【0078】
ホスト−メモリインターフェイスを通じて転送されるデータの量は、データのバイト数か、データのセクタ数か、他の何らかの粒度で表すことができる。ホストは通常、ファイルのデータをバイト粒度で定義するが、論理アドレスインターフェイスを通じて大容量メモリシステムと通信するときには、それぞれ512バイトのセクタか複数のセクタからなるクラスタにバイトをまとめる。これはメモリシステム動作を簡略化するために通常行われていることである。ここで説明するファイル本位のホスト−メモリインターフェイスでは別のデータ単位を使うこともできるが、通常は本来のホストファイルのバイト粒度が好ましい。つまり、データのオフセットや長さ等は、セクタやクラスタ等ではなく、データの最小分解単位であるバイト単位で表すのが好ましい。そうすれば、ここで説明する手法によりフラッシュメモリの蓄積容量をより有効利用できる。
【0079】
図13Aのやり方で論理アドレス空間に書き込まれた新規ファイルは、ファイルインデックステーブル(FIT)の中で(F0,D0)、(F1,D1)の順に並ぶ一連のデータグループインデックス項目によって表される。つまり、ホストシステムは、ある特定のファイルにアクセスする際にこのファイルのファイルIDやその他の識別情報を生成し、次にFITにアクセスし、このファイルを構成するデータグループを識別する。メモリシステムの操作を簡便にするため、各データグループの長さ<length>をそれぞれの項目に盛り込むこともできる。
【0080】
図13Aのファイルがホストによって開いた状態に保たれている間は、好ましくは書き込みポインタPも維持し、そのファイルとしてホストから受信するさらなるデータの書き込みにあたって論理アドレスを指定できるようにする。ファイルの新規データは、当該ファイルにおける新規データの論理位置にかかわりなく、論理ブロックの中ではファイルの末尾に書き込まれる。メモリシステムでは一度に複数のファイル、例えば4つのファイルまたは5つのファイルを開いておくことができ、ファイルごとに書き込みポインタPを維持する。ファイルごとの書き込みポインタは、論理ブロックにおけるファイルの位置を指し示すものである。既にシステムの開放ファイル数制限に達しているときに、ホストシステムで新たなファイルを開く場合は、開いているファイルのいずれか1つを先に閉じ、その後に新たなファイルを開く。
【0081】
図13Bは、既に図13Aで書き込まれ引き続き開いているファイルの末尾にホストがデータを付け加える様子を示している。ホストシステムによってファイルの末尾に追加されたデータ187が見られるが、これも第2のブロック185の中、このファイルのデータの末尾に、書き込まれる。追加されたデータはデータグループ(F1,D1)の一部になり、既存のデータグループ184と追加データ189との間にファイルや論理アドレスの途切れはないため、データグループ(F1,D1)のデータが増えたことになる。したがって、FITの中では引き続きファイル全体が一連のインデックス項目(F0,D0)、(F1,D1)で表される。ポインタPのアドレスも蓄積された追加データの末尾のアドレスに変更される。
【0082】
図13Cには、既に図13Aで書き込まれたファイルへデータブロック191を挿入する例が示されている。ホストはデータ191をファイルの中に挿入しているが、フラッシュ最適化ファイルシステムは、書き込み済みファイルデータの末尾にあたる位置193に挿入データを付け加える。開いているファイルの中にデータを挿入する場合でもファイルのデータを論理順に書き換える必要はないが、後ほどホストがファイルを閉じた後にバックグラウンドで書き換えを行うこともできる。挿入データは第2の論理ブロック185の中に完全に収まるため、新しい単独グループ(F1,D3)を形成する。しかし、この挿入により図13Aの以前のデータグループ(F0,D0)は2つのグループ、すなわち挿入箇所の前のグループ(F0,D0)と挿入箇所の後ろのグループ(F2,D1)とに分かれる。なぜなら、ファイルデータに途切れが生じると、例えば挿入箇所の先頭F1と挿入箇所の末端F2で途切れが生じると、新たなデータグループを形成する必要があるためである。グループ(F3,D2)は、論理アドレスD2が第2のブロック185の先頭になった結果である。グループ(F1,D3)とグループ(F3,D2)は同じ論理ブロックの中にあるが、そこに蓄積されたデータのファイルオフセットは途切れているために別扱いになる。FITの中では挿入が行われたファイルが(F0,D0)、(F1,D3)、(F2,D1)、(F3,D2)の順に並んだデータグループインデックス項目によって表される。図13A、図13B、および図13Cの例では、既存ファイルや新規ファイルの新規データ書き込みにともない、論理ブロックアドレスによって表されるデータが用済みになっていないことに気づく。
【0083】
図13Cに示された既存ファイルへのデータ挿入とは別に、データが挿入されたときにホストによってファイルが別個のファイルとして書き換えられることもある。この別個のファイルはメモリシステムによって新規ファイルとして扱われる。古いファイルがホストによって削除されると、これに応じてシステムは古いファイルに割り当てられた論理アドレス空間を再生し、そのデータは用済みになる。
【0084】
図13Dに示すもうひとつの例では、図13Aのやり方で当初書き込まれたデータの一部分が更新される。データファイルの一部分195が更新される様子が見られる。更新によりファイル全体を書き換えるのではなく、書き込み済みのデータにファイルの更新部分197を付け加えている。そして、書き込み済みのデータ部分199は用済みになる。更新後のファイルはシステムFITの中で(F0,D0)、(F1,D3)、(F2,D1)、(F3,D2)の順序に並んだデータグループインデックス項目によって表される。図13Aで1つだったデータグループ(F0,D0)は図13Dにおいても更新部分の前と、更新部分と、更新部分の後ろとに分割される。用済みデータで占められたアドレス空間199は再生するのが望ましいが、これはファイルデータの書き込みの一部として行うのではなく、後で行ったほうが好ましい。再生を後で行うことにより、通常ならばファイルの蓄積にともなうデータグループ数が少なくなる。
【0085】
可変長データグループの取り扱いをさらに例示するため、同一ファイルが関係する一連の書き込み操作を図14A〜図14Eに順次示す。図14Aに見られるように、当初のファイルデータW1はまず、連続アドレス空間の2つの論理ブロックに書き込まれる。ファイルは2つのデータグループによって画定され、第1のグループは論理ブロックの先頭から始まり、第2のグループは論理ブロック境界の後ろになる。ここで図14Aのファイルは、一連のデータグループインデックス項目(F0,D0)、(F1,D1)によって表される。
【0086】
図14Bでは、図14Aで書き込んだファイルデータがホストによって更新される。更新ファイルデータU1は以前のグループ(F1,D1)のすぐ後ろに書き込まれ、前回の更新データは用済みになる。図14Aの以前のグループ(F0,D0)は図14Bの修正されたグループ(F0,D0)まで短縮し、以前のグループ(F1,D1)はグループ(F4,D2)まで短縮する。更新データは論理ブロックの境界に重なっているために2つのグループ(F2,D3)および(F3,D4)に書き込まれる。そのデータの一部は第3の論理ブロックに蓄積される。このときファイルは、一連のデータグループインデックス項目(F0,D0)、(F2,D3)、(F3,D4)、(F4,D2)によって表される。
【0087】
図14Cでは図14Bのファイルがホストによってさらに修正され、新規ファイルデータI1が挿入される。挿入データは論理ブロックの境界に重なっているため、新規データI1は、図14Cの新規グループ(F5,D6)および(F6,D7)として、論理ブロックにおいて図14Bの以前のグループ(F4,D2)のすぐ後ろに書き込まれる。第4の論理ブロックが使われている。新規データI1の挿入のため、図14Bの以前のグループ(F0,D0)は図14Cで短縮グループ(F0,D0)および(F7,D5)に分割される。このときファイルは一連のデータグループインデックス項目(F0,D0)、(F5,D6)、(F6,D7)、(F7,D5)、(F8,D3)、(F9,D4)、(F10,D2)によって表される。
【0088】
図14Cのデータファイルに対するさらなる修正を示す図14Dでは、ファイルの末尾に新規データW2を付け加えている。新規データW2は、図14Dの新規グループ(F11,D8)として図14Cの以前のグループ(F10,D2)のすぐ後ろに書き込まれる。このときファイルは、一連のデータグループインデックス項目(F0,D0)、(F5,D6)、(F6,D7)、(F7,D5)、(F8,D3)、(F9,D4)、(F10,D2)、(F11,D8)によって表される。
【0089】
開いたファイルに対する第2の更新を示す図14Eでは、図14Dのファイルに更新ファイルデータU2を書き込んでいる。図14Eでは更新データU2が図14Dの以前のグループ(F11,D8)のすぐ後ろに書き込まれ、前の更新データは用済みになる。図14Eでは図14Dの以前のグループ(F9,D4)が修正されたグループ(F9,D4)まで短縮し、以前のグループ(F10,D2)は完全に用済みとなり、以前のグループ(F11,D8)は短縮して新たなグループ(F14,D9)を形成する。更新データは図14Eの新規グループ(F12,D10)および(F13,D11)に書き込まれ、論理ブロック境界に重なる。ここで第5の論理ブロックがファイルに必要になる。このときファイルは一連のデータグループインデックス項目(F0,D0)、(F5,D6)、(F6,D7)、(F7,D5)、(F8,D3)、(F9,D4)、(F12,D10)、(F13,D11)、(F14,D9)によって表される。
【0090】
各ファイルのデータのオフセットは、これまで説明したファイルの作成や修正の後に、好ましくは連続する正しい論理順序に保たれる。例えばファイルの中にデータを挿入する操作の一部としてホストによって提供される挿入データのオフセットは、挿入箇所の直前のオフセットから連続し、ファイル内の既存データは、挿入後に挿入データの分だけ増加する。既存ファイルの更新にあたってはほとんどの場合、既存ファイルの特定のアドレス範囲内にあるデータがほぼ同量の更新データで差し替えられるため、通常はファイルのそれ以外のデータのオフセットを差し替える必要はない。
【0091】
このようにして蓄積されるデータの粒度または分解能は、ホストのものと同じに保つことができる。例えばホストアプリケーションが1バイト粒度でファイルデータを書き込むなら、そのデータは論理ブロックの中でも1バイト粒度で表される。そして、データグループの中でのデータの位置と量はバイト数単位になる。つまり、ホストアプリケーションファイルの中で個別にアドレスされるオフセット単位のデータは、フラッシュメモリに蓄積されたときにもファイルの中で個別にアドレスされる。論理ブロックの中にある同一ファイルのデータグループ境界は、FITの中で最も近いバイトオフセット単位かその他のホストオフセット単位まで指定される。同様に、論理ブロックの中にある異なるファイルのデータグループ境界はホストオフセット単位で指定される。
【0092】
ここで使用する用語「セクタ」は、大きなブロックメモリでECCが関わる蓄積データの単位を意味する。つまり、セクタは、メモリシステムのコントローラによって誤り訂正符号が生成されデータとともに蓄積される場合に、フラッシュメモリを行き来するデータの最小転送単位である。物理メモリに言及する場合の「ページ」は、ブロック内の1単位のメモリセルを意味する。ページは最小のプログラミング単位である。論理ブロック内の論理「ページ」は、物理ページと同量のデータを収容する。用語「メタページ」は、完全並列メタブロックのページを意味する。メタページは最大のプログラミング単位である。
【0093】
図14Bおよび図14Eでは、更新コマンドの結果としてファイルによって占められる論理アドレス空間がファイルのデータ量を上回っていることが分かる。これは、更新によって差し替えられたデータの論理アドレスが残っているためである。そこで、用済みになった無効データを取り除いてファイルのデータをより小さい論理アドレス空間に整理統合(ガーベッジコレクション)することが強く望まれる。それによって、ほかのデータに使える論理アドレス空間が増える。
【0094】
図14Bおよび図14Eのファイルデータ更新に加え、図14Cのデータ挿入によってファイルデータのアドレス順序がずれることにも気づく。つまり、更新や挿入が行われるとファイルの末尾に追加されるが、ほとんどの場合、更新や挿入の位置はファイルの中である。図14B、図14C、および図14Eの例がこれに該当する。そこで、ファイル内のオフセット順序に合わせて論理アドレス空間にまたがるファイルデータを並べ替えるのが望ましい。こうすれば、ページやブロックを順次読み出すときにファイルデータがオフセット順に提供され、蓄積データの読み出し速度が向上する。ファイルの断片化も極力抑えることができる。しかし、読み出し効率を上げるファイルデータの並べ替えでも、メモリシステムの性能にとっては、ファイルデータの整理統合ほどには重要ではなく、ファイルデータの整理統合なら、場合によっては別のデータのアドレスのための1つ以上の論理ブロックを開放することができる。ファイルデータの並べ替えを単独で行うとオーバーヘッドの増加に見合うほどのメリットが得られないため、通常は並べ替えを単独で行うことはないが、ガーベッジコレクション操作の一部として行えばオーバーヘッドの増加は皆無かごく僅かですむ。
【0095】
図14Eのファイルには、2つのデータ更新U1およびU2が行われたことによって用済みのデータグループ(灰色の部分)がある。このファイルに割り振られた論理アドレス空間の量がファイルのサイズを大きく上回っていることは、図14Eから明らかである。したがって、ガーベッジコレクションが妥当である。図15は、図14Eのデータファイルでガーベッジコレクションを行った結果を示すものである。ガーベッジコレクションの前には5論理ブロック近くのアドレス空間(図14E)を占めていたファイルが、ガーベッジコレクションの後には3ブロック強以内(図15)で収まっている。ガーベッジコレクション操作の一部として、当初の書き込み論理ブロックから別の消去済み論理ブロックへデータをコピーした後に、当初のブロックを消去する。ファイル全体でガーベッジコレクションを行う場合は、ファイル内でのデータの論理オフセット順序と同じ論理順序でデータを別のブロックにコピーできる。例えば更新U1およびU2と挿入I1はガーベッジコレクション(図15)の後に、ホストファイル内での順序と同じ順序で蓄積される。
【0096】
また、ファイル単位のガーベッジコレクションでは通常、別の新しいデータグループが整理統合されているファイルの中で形成される。図15の場合は、一連の新規データグループインデックス項目(F0,D12)、(F1,D13)、(F2,D14)、(F3,D15)によってファイルが表される。データグループの数は、図14Eに見られるファイルの状態より遥かに少ない。ファイルデータをコピーした各ブロックにつきデータグループが1つずつある。FITは、ファイルを形成する新たなデータグループを反映するため、ガーベッジコレクション操作の一部として更新される。
【0097】
図14Eの状態でファイルデータを保持するブロックの再生は、同じファイルのデータを蓄積する複数のブロックではなくブロックごとに個別に行われる。例えばある一時点で再生操作の候補となるアドレス空間のブロックのうち、有効データ量が最も少ないブロックが図14Eの第2のブロック002なら、そこにある1データグループを別の消去済みブロックにコピーする。新しいブロックには1つのデータグループ(F8,D16)が入り、ブロックの残りの部分は新規データを書き込める消去済み容量である。この消去済み容量は、図14Eでデータを蓄積していたブロックから再生されたものである。このときファイルは、このファイルを構成するデータグループの一連のインデックス項目(F0,D0)、(F5,D6)、(F6,D7)、(F7,D5)、(F8,D16)、(F9,D4)、(F12,D10)、(F13,D11)、(F14,D9)によって表される。図14Eに見られる他のブロックは再生操作の条件をそれぞれが満たすまで変化しない。
【0098】
ファイルブロック管理
論理ブロックのタイプは、そこに蓄積されたファイルデータの構造に基づいて認識される。連続アドレス空間の中でアドレスを持つ各ファイルは、数ある状態のいずれか1つをとり、各ファイルの状態は、ファイルデータを蓄積するブロックの数とタイプによって決まる。ファイルデータの書き込みにあたっては、好ましくはファイルの現在状態とある状態から別の状態に至る許容遷移とを規制することにより、ある特定のファイルのデータのほかに1つ以上の別のファイルのデータも含むブロックの数を制限する。これにより論理ブロックの有効利用を促進し、新規データやコピーデータの受け付けにあたって十分な消去済みブロックを確保するために後ほど行われる再生操作の頻度を抑える。
【0099】
この例で認識され、ファイルデータを収容する、論理ブロックの主なタイプは次のとおりである。
・「ファイルブロック」は完全にプログラムされ、1ファイルの有効データを意味する。ある程度の用済みデータのアドレスを含むこともある。
・「プログラムブロック」は部分的にプログラムされ、単独ファイルのみの有効データを意味する。このブロックにはある程度の消去済み容量が残っている。ある程度の用済みデータのアドレスを含むこともある。
・「共通ブロック」は部分的にプログラムされ、2ファイル以上の有効データを意味する。ある程度の消去済み容量が残っている。ある程度の用済みデータのアドレスを含むこともある。
・「フル共通ブロック」は完全にプログラムされ、2ファイル以上の有効データを意味する。ある程度の用済みデータを意味することもある。
【0100】
ブロックタイプにはこのほかに「消去済みブロック」があり、このブロックにはデータアドレスがなく、その全容量をデータの受け付けに使用できる。LBAインターフェイスの論理アドレス空間がデータアドレスで満たされているかほぼ満たされている場合は通常、使用中の論理ブロックで使われていない容量を絶えず再生しながら所定の最小消去済みブロック数のプールを維持する。
【0101】
「フラクタルブロック」は、プログラムブロックと、共通ブロックと、フル共通ブロックとを指す総称である。ファイルのフラクタルブロックの中には、ある1つのファイルの有効データのほかに、プログラムされていない蓄積容量か、別のファイルの有効データか、その両方がある。ここで説明する手法の第1の目的は、ファイルデータを受け付けるよう指定されたアクティブブロックのタイプを管理しながら、アドレス空間の中でフラクタルブロックの数を最小限に抑えることにある。これにより、所定の最小消去済み論理ブロック数を維持するために論理アドレス空間で行われるガーベッジコレクションやデータの整理統合(ブロック再生操作)の回数を抑える。プログラム済みブロックで未使用容量の断片を再生するときにデータの内部コピーにかかる時間が短くなるため、メモリにデータを書き込む速度も向上する。
【0102】
ここでは各種ブロックを総称するためにさらに別の用語を使用する。
・「パーシャルブロック」はある程度の未プログラム容量と、1ファイル以上の有効データのアドレスを含み、ある程度の用済みデータを意味することがある。例えば、プログラムブロックや共通ブロックがパーシャルブロックにあたる。
・「用済みブロック」は、ある程度の用済みデータのアドレスを含むファイルブロックまたはフル共通ブロックである。用済みブロックには消去済み容量がなく、有効データと用済みデータの両方を意味する。
・「無効ブロック」の中に有効データはない。無効ブロックは少なくともある程度の用済みデータのアドレスを含むほか、消去済み容量を含むこともあるが、有効データは意味しない。
【0103】
図16A〜図16Dは、前に定義したタイプの論理ブロックの使用例を示す。図16Aでは、ファイルAのデータによってブロック661および663が満たされ、第3のブロック665は部分的に満たされている。データは左から右にかけてこの例の各ブロックに書き込まれ、まずはブロック661を満たし、次にブロック663を満たし、その後ブロック665の一部分に書き込まれる。ブロック665の残りの部分はプログラムされていない消去済み容量であって、さらなるデータを蓄積できる。前述した定義によるとブロック661および663はファイルブロックであり、ブロック665はプログラムブロックである。ブロック665には、プログラムポインタPのところから新規のデータが書き込まれる。ポインタPはブロックへのデータの書き込みにともない左から右へ進み、常にブロックの中で次に使用できる蓄積位置を指し示す。プログラムされていない消去済み容量を持つ各ブロックでは、それが現在アクティブであろうとなかろうと、そのようなポインタを管理し、ブロックに書き込まれる他のデータの論理アドレスを常に把握できるようにする。
【0104】
図16Bの例にあるブロック669は、現在のファイルAのデータとある程度の未プログラム容量のほかに、別のファイルBのデータを収容しているため、共通ブロックである。新規のデータは、ファイルAの末尾、プログラムポインタPが表示されているところから、ブロック669に書き込まれる。ブロック669はファイルAにとってのアクティブブロックである。ファイルBにとってのアクティブブロックになることもあり、その場合は、ファイルAまたはBのいずれかの追加データをプログラムポインタPのところに書き込むことができる。あるいは、これとは別のブロック(図示せず)がファイルBにとってのアクティブブロックになることもある。
【0105】
消去済みブロックではなく、既に別のファイルのデータを収容しているパーシャルブロックの消去済み容量にファイルデータを直接書き込めば、このような未プログラム容量を上手に利用することができる。これは特に、ブロック全体の容量に満たない既知量のファイルデータを書き込む場合に有益である。それには既存のパーシャルブロックを探査し、既知量の書き込みデータにフィットする消去済み容量を見つける。データのページ(メタブロックを使用する場合はメタページ)数を、パーシャルブロック内の未プログラム容量のページ数に比較する。このやり方でプログラムブロックの未使用消去済み領域がプログラムされると、そのプログラムブロックは共通ブロックに変わる。
【0106】
図16Cでは、ファイルブロック661と、ブロック671の一部分と、ブロック673の一部分とにファイルAが蓄積されている。2つのファイルAおよびBのデータで満たされているブロック671はフル共通ブロックである。図16Aのブロック665と同様、ブロック673はプログラムブロックである。ファイルにとってのアクティブブロックはブロック673であり、ポインタPは、ブロック673の中で未使用容量の位置を指し示し、追加のデータはこの位置から書き込まれることになる。
【0107】
図16Dの例では、フル共通ブロック671の一部分と共通ブロック675にファイルAが書き込まれている。ブロック675の中には第3のファイルCのデータがある。ポインタPはアクティブブロック675で未使用部分の先頭を指し示し、追加のデータはここに書き込まれることになる。
【0108】
図16A〜図16Dの例では、数通りのブロックを例示するために複数のブロックに蓄積されたファイルAのデータが示されているが、ファイルは多くの場合、これよりも少ないブロックに、ことによると1ブロックに、蓄積できるほど小さい。ここで説明する手法はそのような小さなファイルにも適用できる。大きなファイルが4ブロック以上にわたってページを占めることもある。
【0109】
論理ブロック665、669、671、673、および675がフラクタルブロックであることに気づく。いずれか1ファイルのデータを含むフラクタルブロックがあると、その中にある未使用容量を再生する必要が高まってシステム性能に悪影響がおよぶため、そのようなフラクタルブロックの数は最小限に抑えるのが望ましい。パーシャル論理ブロック665、669、673、および675には未使用の消去済み容量があるが、まだ書き込まれていないファイルデータの量が分かっていて、その既知量がこれらのブロックのうちの1つの未使用容量に一致しない限り、ホストからこの領域に新規データをそのまま書き込むのは効率的でない。ほとんどの場合、ホストから到来するファイルデータの量は分からないため、これらの断片的容量が容易に埋まることはない。そこでメモリ容量を有効利用するには、再生操作のときに別のブロックから未使用領域へデータを移す必要がある。ブロック669、671、および675には2ファイル以上のデータが入っているため、それらのファイルのいずれか1つが削除されたり、共通ブロックに蓄積されているデータが用済みになったりする場合はデータ再生を行い、用済みデータのアドレスで占められたブロックの容量を再生することになる。
【0110】
そこで、時間のかかるデータ再生操作の回数を減らすには、ある特定のファイルのデータを一度に蓄積するフラクタルブロックの数を1、2等の数にする。許容フラクタルブロック数の決定にあたっては、フラクタルブロックを使用する場合の利点とそれらを使用することの好ましくない影響とでバランスをとる。ここで説明する具体例では、1ファイルのデータを蓄積できるフラクタルブロックを2ブロックまでとする。これに応じて、ファイルデータの蓄積にあたって新規アクティブブロックを指定するプロセスには制約がかかる。各ファイルには1組の許容ファイル状態のいずれか1つを割り当てるが、これはファイルのデータを蓄積するブロックのタイプによって決まる。既存のブロックが一杯になる等、ある特定のファイルのデータを受け付けるための新規のアクティブブロックを指定する必要がある場合、アクティブブロックに指定されるブロックのタイプはファイルの状態に左右され、多くの場合はそれ以外の要因にも左右される。
【0111】
図17の表には、ある特定の実施例でファイルデータを収容するフラクタルブロックの組み合わせによる7通りの許容ファイル状態00〜20の定義が記載されている。どの許容ファイル状態でもデータを蓄積できるのは2フラクタルブロックまでである。ファイルデータを蓄積するファイルブロックの数に制限はない。ファイルのアクティブブロックとして使用するブロックの選択にあたっては、ファイルの状態をプロパティとして使用する。再生ブロックは一時的なものであって、その中にあるファイルデータはファイル状態の判断に寄与しないため、再生ブロックとして選ばれたブロックはフラクタルブロックとして扱わない。装置内に存在する全ファイルの状態を監視し、ファイルデータインデックス情報と併せてFITに記録する。記録されたファイルの状態は状態遷移のたびに更新される。
【0112】
ファイル状態遷移は、それらがプログラムデータに関係する状態遷移か、用済みデータに関係する状態遷移か、再生ブロックの選択に関係する状態遷移かによって、3つの部類に細分される。図18の状態図には、保留のデータプログラミング操作か完了したデータプログラミング操作に基づく許容ファイル状態遷移が描かれている。図17の表に記載されたファイル状態識別番号を囲む円により、7通りのファイル状態が示されている。
図18の状態遷移ラベルの意味は次のとおりである。
A−ファイルのアクティブブロックとして消去済みブロックが割り当てられる。
B−パーシャルブロックが満杯になった。
C−ファイルのアクティブブロックとしてパーシャルブロックが割り当てられる。
D−このファイルのパーシャルブロックが別のファイルのアクティブブロックとして割り当てられる。
E−アクティブブロックとして割り当てられた消去済みブロックに対しデータ遷移が行われる。
F−アクティブブロックとして割り当てられたパーシャルブロックに対しデータ遷移が行われる。
【0113】
ほとんどの状態遷移は、ブロックが割り当てられるかブロックが満杯になるときに自動的に生起する。しかし、定義した状態遷移によっては、ある1つのブロックから別のブロックにかけてのデータ再配置をともなうものもある。データの再配置は1回の連続操作で行われ、このデータ再配置が完了した場合に限り状態遷移が生起したとみなされる。このような遷移を「データ遷移」という。図19の表は、図18の状態図を参照しながら許容状態遷移の詳細を伝えるものである。
【0114】
書き込みデータの長さが分かっている場合は、アクティブブロックとしてパーシャルブロックを割り当てることができる。この場合は、装置内のパーシャルブロック群から「最適」なパーシャルブロックを選ぶ。「最適」とは、既知量の書き込みデータが有効利用できる消去済み容量を有するパーシャルブロックのことである。「最適」パーシャルブロックが存在しなければ、「最大」パーシャルブロックを代わりに選ぶ場合もある。これは、使用可能な未使用容量が最も大きいパーシャルブロックである。
【0115】
図20は状態図であり、用済みデータに基づくファイル状態遷移を示すものである。ファイルの状態遷移は、当該ファイルのデータを収容するフラクタルブロックの中で1ファイルの全データが用済みになるときに起こる。用済みになったデータのファイルは当該ファイルとは限らない。データは4つのイベントのいずれか1つによって用済みとなる。
1.ファイルがホストによって削除される。
2.ファイル内のデータがホストによって削除される。
3.書き込み済みのファイルデータがホストによって更新される。
4.再生操作中にファイルデータが再配置される。
図20の状態遷移ラベルの意味は次のとおりである。
G−パーシャルブロックの中でこのファイルの全データが用済みになった。
H−フル共通ブロックの中でこのファイルの全データか他の全てのファイルの全データが用済みになった。
I−パーシャルブロックの中で他の全てのファイルの全データが用済みになった。
【0116】
図21の表は、図20に描かれた用済みデータに基づくファイル状態遷移の詳細を伝えるものである。これらの経緯でデータが用済みになると、用済みデータが入っているブロックのタイプが変化し、それにともないファイル状態も変化する。
【0117】
再生ブロックとして選ばれたブロックは、そこにデータを蓄積するファイルにとってフラクタルブロックでなくなる。その結果、図22の状態図に示すファイル状態遷移が起こる。図22の状態遷移ラベルの意味は次のとおりである。
J−パーシャルブロックが再生ブロックとして選ばれる。
K−フル共通ブロックが再生ブロックとして選ばれる。
【0118】
再生ブロックの選択に基づくファイル状態遷移の詳細を図23の表に示す。
連続論理アドレス空間の論理ブロックにファイルデータを揃えるには2通りの方法がある。前に相互参照した特許出願で説明されている物理メモリセルブロック上で作動するダイレクトデータファイルシステムの場合は、好ましくは新規ファイルの先頭を消去済みメモリセルブロックの先頭に揃える。図24に示すように、ダイレクトデータファイルシステムで論理ブロックを扱う場合にもこれは可能である。3つのファイルA、B、およびCが論理ブロック1〜7に蓄積された状態で描かれている。図24から分かるように、これらのファイルのいずれか1つで全てのデータが書き込まれると、ファイルの最終部分はパーシャルブロックのごく一部分を占めることになる。
【0119】
図25の表には、ファイルデータを蓄積するアクティブブロックとして割り当てる論理ブロックのタイプを判断するための基準が記載されている。記載されているように、これは現行のファイル状態(図17の表で規定)とプログラムするデータの全般状況に左右される。この基準をもとに割り当てケースのいずれか1つが選ばれても、ブロックの有無に応じて、図25の右列に記載された一定の候補からブロックタイプを絞りこまなければならない。例えば割り当てケースBの場合に、長さが既知のデータを受け付けるブロックとして第1候補に登るのはパーシャルブロックである。そこで、まずはこの既知量のデータを蓄積するにあたって丁度いい使用可能(消去済み)な容量を持つパーシャルブロックを探す。これが見つからなければ、未プログラム領域が最も大きいパーシャルブロックの有無を確認する。これがなければ、第3の候補として完全に未使用の(消去済み)ブロックがデータを受け付けるブロックとして指定され、この例の割り当てケースBの場合、既知量の書き込みデータはブロック全体を満杯にする量には満たないため、このブロックはパーシャルブロックになる。
【0120】
図24のファイルA、B、またはC等で、最初に書き込まれたときと同じ状態を保つファイルが削除される場合は、それとは無関係のファイルのデータで再配置を行う必要はない。しかし、再生操作によってパーシャルブロックにある1ファイルのデータを別ファイルのデータと整理統合した場合に当該ファイルが削除されると、ただひとつのブロックで別ファイルのデータの再配置が必要になる。例えば、ブロック2のファイルAのデータがブロック7にあるファイルCのデータと整理統合された後に、ファイルAかファイルCが削除されると、ただひとつのブロックで、すなわちブロック7で、データの再配置が必要になる。
【0121】
ブロック再生は、ファイルデータの書き込みプロセスと交互に行われるプロセスであって、再生の対象となるブロックから別の場所に有効データを移し、このブロック(未使用と指定されたもの全容量)を消去することによってブロック内の未使用容量を再生する。ブロックが再生の対象として選ばれる理由には次の2つがある。
1.ファイルの削除か更新によってブロック内のデータが用済みになる、または
2.ブロックが未プログラム容量を持つパーシャルブロックである。
新規ファイルデータの書き込み速度を一定に保つため、再生プロセスにあてる時間はできるだけ一定であることが好ましい。ファイル書き込みプロセスで発生し再生プロセスで処理しなければならないパーシャルブロックの数は予測できないため、これを果たすのは困難である。
【0122】
図24に見られるファイル−ブロックマッピング方式には、最新の書き込みファイルデータを収容するパーシャルブロックが、再生操作のコピー元ブロックかコピー先ブロックに選択されるまで存続するという利点がある。このため、ファイルが先に削除され、共通ブロックの中にある当該ファイルのデータや無関係ファイルのデータで再配置を行わずにすむ見込みが高くなる。なぜなら、ファイルのデータはそのファイル専用のブロックに収容されるためである。再生操作が不要ならばデータをコピーする時間も不要となり、メモリシステム動作の効率が上がる。
【0123】
図24のマッピング方式の欠点として、通常は書き込みが行われる各ファイルにつきパーシャルブロックが1つずつ作成されるため、使用可能な未プログラム(消去済み)容量の再生にあたっては多数のパーシャルブロックでデータの整理統合が通常必要になる。さらに、図24のマッピング方式だと、物理メモリを管理するメモリコントローラが新たな消去済みブロック容量を再生するために部分的に書き込まれたブロックのデータを自動的に整理統合する場合に、時間のかかるデータコピーが大量に発生することになる。このため、図26の代替マッピング方式の実施が望ましい場合もある。この方式の第1の特徴として、新規ファイルの先頭のデータはパーシャルブロック内に既に存在する無関係ファイルのデータと隣接する。ほとんどの場合、1ファイルの全データが書き込まれると、その最終書き込みデータはパーシャルブロックのごく一部分を占めることになるが、これは一時的である。パーシャルブロックの未プログラム領域は、完了したファイルに隣接して書き込まれる新規ファイルデータによって直ちに埋まる。
【0124】
図27の表には、データの書き込みにあたって図26の方式を実施した場合のアクティブブロック割り当てが記載されている。図27の表では、新規ファイルの場合と既存ファイルの場合を分けて説明するため、図25の表に記載された割り当てケースAが割り当てケースA1およびA2に差し替えられている。
【0125】
図26では通常、ファイルの先頭とファイルの末尾のデータでブロックが無関係ファイルのデータと共有され、1ファイルが削除されると2つのブロックでデータの再配置が必要になる。例えばファイルBが削除されると、ブロック2から別の場所にファイルAのデータを移し、ブロック3から別の場所にファイルCのデータを移すことになる。次にブロック2および3を消去し、消去済み(未使用)ブロックのプールに加えることができ、プールのブロックには後ほど別のデータを書き込むことができる。
【0126】
図26のファイル−ブロックマッピング方式には、部分的にプログラムされたブロックをためこまずにすむという利点がある。書き込みが行われる新規ファイルのデータの先頭はパーシャルブロックの中に既に存在する無関係ファイルのデータと隣接するため、最新の書き込みファイルデータを含むパーシャルブロックが長時間にわたって存続することはなく、装置に存在するパーシャルブロックの数はごく僅かになる。その結果、再生操作でパーシャルブロックのデータを整理統合する機会が少なくなるほか、一定の再生レートを設定し、新規ファイルデータの書き込みで一定の速度を維持することが可能となる。
【0127】
しかし、図26のマッピング方式には、ファイルが削除されるときに無関係ファイルのデータで再配置が必要になる見込みが高くなるほか、毎回の再配置で移動するデータ量が増えるという欠点がある。図26の方式には、再生操作でパーシャルブロックのデータを整理統合する頻度を抑えるという図24の方式を凌ぐ利点があっても、その利点は、ファイルが削除されるときの再配置データ増大という欠点によって帳消しになる。
【0128】
ブロック容量の再生
前述したように、新規データ蓄積のためのブロックにおける未使用容量再生はブロック管理の一部として行われる。これは、メモリシステムに蓄積されたデータ量がメモリシステムの容量を遥かに下回る場合は特に問題にならないが、メモリシステムはデータで一杯の状態を想定して設計されることが好ましい。これは、未使用容量を再生しながら、用済みデータだけを含むブロックと、有効データのほかにある程度の用済みデータおよび/または未書き込みページを持つ他のブロックを処理することを意味する。目標は、メモリシステムの蓄積容量をできるだけ余すところなく利用すると同時に、システム性能への悪影響を最小限に抑えることにある。
【0129】
再生操作の対象として指定されたブロック(コピー元ブロック)に有効データがある場合は、その有効データを蓄積するにあたって十分な未使用(消去済み)容量を持つ1つ以上のブロック(コピー先ブロック)に有効データをコピーする。このコピー先ブロックは、前述したブロック管理手法に従って選択する。コピー元ブロックに蓄積された各ファイルデータは別のブロックへコピーされ、このコピー先ブロックは、前述したようにファイルの状態とその他の要因に基づいて選択する。再生操作の一部として各種ファイル間で行われるデータコピーの例を図28A〜図28Dに示す。
【0130】
図28Aには、2つのパーシャルブロック681および683に対する再生操作が例示されている。ブロック681はファイルAの有効データを蓄積するほか、データを蓄積しない消去済み容量も持つプログラムブロックである。ファイルAの状態しだいで決まる再生操作のひとつとして、ブロック681にあるファイルAのデータは別のパーシャルブロック685の使用可能な消去済み容量にコピーされ、パーシャルブロック685の中には既に別のファイルBのデータが入っているため、このパーシャルブロックは共通ブロックになる。FITの中ではブロック681のデータグループが参照されなくなり、このブロックは用済みブロックとして記録される。ブロック681に蓄積されていたときのファイルAは、プログラムブロック状態等、いずれか1つの状態(図17参照)をとっていた。その後このデータは別のフラクタルブロックへ移されるが、ファイルの書き込みは最大の2フラクタルブロック以内にとどまる。ファイルAはブロック685へコピーされた後、共通ブロックにファイルデータが蓄積されることを含む、いずれか1つの状態(図17参照)に遷移するが、これは別のファイルデータを蓄積するブロックのタイプしだいで決まる。
【0131】
図28Aのブロック683は共通ブロックであり、そこに蓄積されたファイルCおよびDのデータがプログラムブロック687の消去済み容量にコピーされることによって再生され、このコピーによってファイルEのデータが入っているプログラムブロック687は共通ブロックになる。そして、ブロック683のファイルCおよびDのデータは用済みになり、ブロックそのものも用済みになる。データはある1つの共通ブロックから別の共通ブロックへ移されたため、ファイルCおよびDの状態は変化していない。しかし、ファイルEの状態は変化している。これとは別に、ファイルCおよびDのデータをそれぞれ別々のブロックへ移すこともでき、必ずしも共通ブロックの空き領域にコピーする必要はない。そこでこれらのファイルの状態が別の状態に遷移する可能性もある。
【0132】
図28Bには、ブロックの例689および691に対する再生操作が示されている。これらのブロックはいずれも有効データと用済みデータの両方で埋まっているため、用済みブロックである。ブロック689はファイルFのデータを収容するファイルブロックであって、その一部分は用済みで、残りの部分は有効である。これは例えばファイルFの更新のときに、ファイルの既存データと同じ論理オフセットを持つ新規データがファイルの末尾のアドレスに書き込まれると生じ、既存データは用済みになる。この例では、ファイルGのデータが入っているプログラムブロック693の消去済み容量にファイルFのデータがコピーされることによって、ブロック693のタイプは共通ブロックに変化する。これとは別に、ファイルFの有効データを消去済みブロックに書き込むこともでき、書き込まれたブロックはプログラムブロックになる。
【0133】
図28Bのブロック691は、ファイルHの無効データとファイルIの有効データを収容するフル共通ブロックである。この例では、ブロック691からファイルIの有効データを消去済みブロック695にコピーしている。この場合、ブロック695はプログラムブロックになる。これとは別に、別のファイルのデータが入っているパーシャルブロックで適切なものが見つかるならば、そのパーシャルブロックにファイルIのデータを書き込むこともできる。コピー先ブロックは、再生操作のときのファイルIの状態しだいで決まる。
【0134】
図28Aおよび図28Bに見られる4つの再生操作の具体例の結果、2つのパーシャルブロックに蓄積されたデータは1つにまとまり、2ブロックのうちの一方には用済みデータだけが残る。それらのブロックは無効ブロックになる。元のブロック681、683、689、および691は図28Cのように消去され、全領域が再生される。消去済みブロックは、無効ブロックを再生した結果である。
【0135】
図28Dは、ファイルJのデータを蓄積するファイルブロック697の例を示す。ホストによってファイルJが削除されるとブロック697にあるファイルJのデータは用済みになり、場合によっては別のブロックにあるデータも用済みになる。そして、ブロック697は無効になる。無効ブロックの再生によって、システム消去済みブロックプールに消去済みブロックが提供される。
【0136】
メモリからファイルが削除されると、通常は共通ブロックやフル共通ブロックといった1つ以上のフラクタルブロックにある当該ファイルのデータも用済みになる。ファイルが異なる残りの有効データはブロックの蓄積容量に満たなく少量なので、このブロックは再生操作の対象となる。
【0137】
図29のフローチャートは再生操作を一般的な言葉で説明するものである。ステップ701に示すように、具体的な実施形態に応じてパーシャル、用済み、および無効ブロックのリストを1つ以上管理する。このブロックリストは、一手法によると、メモリシステムの起動時、例えば最初に電力が印加されるときに作成される。リストには、各ブロックの有効データ量や各ブロックの消去済み容量等、一度に1つの再生ブロックを選択するためのブロックの他の情報を盛り込むことができる。通常、これらの量はブロックのページ数単位で表され、メタブロックを使用する場合はメタページ数単位で表される。好適な代替手法では、これらのリストを不揮発性メモリで管理し、ブロックの状態が変化するたびにリストにブロックの項目を加えたり、リストのブロックの項目を更新したりする。この手法では、メモリシステムの初期化のときにブロックを走査しリストを作成する必要はない。コピーの必要がある有効データが皆無かごく僅かということが再生ブロックとして選ばれるひとつの特徴となるため、パーシャル、用済み、および無効の全ブロックをリストで管理する代わりに、有効データが少量で所定の限界量を下回るブロックだけをリストに入れる方法もある。多くの再生操作で必要となるのは、ある1つのブロックから別のブロックへのデータのコピーであって、それにはかなりの時間がかかるため、通常はコピーの必要があるデータが少ないブロックから先にコピーを行う。
【0138】
そのようなブロックのリストは、データの書き込み、更新、移動、削除等にともない絶えず変化する。パーシャル、用済み、無効の中でブロックタイプの変化を招くような変更があると、図29のステップ701で管理するリストも変化する。そのようなブロックに蓄積された有効データの量や消去済み容量の変化もブロックリストに記録される。
【0139】
ステップ703では、好ましくは再生する次のブロックとして更新済みリストのブロックから1つの再生ブロックを識別する。パーシャルブロックか用済みブロックならば、これが有効データのコピー元となり、そこからコピー先ブロックと呼ばれる別のブロックに有効データをコピーする。コピー元ブロックの選択に用いるいくつかの具体的な手法は後述する。
【0140】
図29の次のステップ705では、ホストのコマンドに応じて実行するメモリ操作を考慮に入れ、今ここで再生操作を実行することが適切か否かを判断する。ホストがアイドルコマンドやこれに類似するものを発行し、ある程度の期間にわたってメモリシステムによる操作の実行を見込まないことを伝えるなら、メモリシステムはフォアグラウンドで再生操作を含むオーバーヘッド操作を自由に実行できる。ホストがメモリシステムへのデータの書き込みやメモリシステムからのデータの読み出しでビジー状態にある場合でも、再生操作、特にそのデータコピーは、インターリーブ方式でデータの読み書き操作の合間に実行できる。2005年10月25日に出願されたAlan Sinclair の米国特許出願第11/259,423号(特許文献30)と2005年12月19日に出願されたAlan Bennettらの米国特許出願第11/312,985号(特許文献31)では、物理メモリセルブロックのためのインターリーブ操作が説明されている。
【0141】
再生操作を行ってよいことが図29のステップ705で判明した場合のプロセスは、識別された再生ブロックに有効データが入っているか否かに応じて、さらに有効データが入っている場合には、2つ以上のファイルの有効データが入っているか否かに応じて、異なる。パーシャルブロックか用済みブロックなら、必然的に有効データを収容していることになり、共通ブロックかフル共通ブロックなら、2つ以上のファイルの有効データを収容していることになる。再生ブロックにおける有効データの有無はステップ707で判断する。移動の必要がある有効データがある場合は、次のステップ709で1ファイルのデータを識別し、さらにそのデータを受け付けるコピー先ブロックを識別する。有効データを含むファイルの全データの蓄積を2フラクタルブロック以下(この例)に保つため、コピー先ブロックは図17〜図19との関係で前述したプロセスで識別する。そして、ステップ711に示すように、コピー元の再生ブロックからコピー先ブロックへの1ファイルの有効データのコピーを開始する。処理はこれらのデータをコピーした後にステップ707まで戻り、別のファイルのデータが残っているか否かを判断する。残っているなら、そのデータのためにステップ709および711のプロセスを繰り返す。そのコピー先ブロックは、別のファイルのデータのために先に選ばれるブロックとは別に選ばれる。これは、移動すべきデータがコピー元ブロックにそれ以上存在しないことがステップ707で判明するまで続き、存在しないことが判明する場合は、ステップ713に従ってコピー元ブロックを消去できる。次に、消去済みブロックプールの中にこのブロックを入れ、新規データの蓄積に使えるようにする。
【0142】
図29のステップ707に戻り、無効ブロックの場合のようにコピー元ブロックの中に有効データがなければ、移動すべき有効データもない。このコピー元ブロックは消去するだけでよい。図29に見られるように、この場合の処理はステップ709および711を迂回する。
【0143】
図29のプロセスの第1の実施形態では、ステップ701でパーシャル、用済み、および無効ブロックからなる単一のリストを管理する。リストの各項目にはブロック内の有効データ量を盛り込む。ステップ703で再生ブロックとしてリストから選ばれるブロックは、有効データが最も少ないブロックである。無効ブロックには有効データがないため、リストに無効ブロックが1つでもあるならば、そのブロックが最初に選ばれる。リストに多数の無効ブロックがあるなら、リストに登録されていた期間が最も長い無効ブロックが選ばれる。リストに無効ブロックがなければ、有効データ量が最も少ないブロックが再生ブロックに選ばれる。リスト上の全ブロックから有効データ量が最少のブロックを選ぶことで、再生操作にかかる時間は、あるブロックから別のブロックへコピーするより多くの有効データがある時よりも短くなる。その結果、メモリにおけるデータの読み書き速度等、再生操作以外のメモリシステム操作は高速に保たれる。メモリ性能への代償を抑えながら新たに消去されたブロックが手に入ることになる。
【0144】
単一リスト上でフラクタルブロックの有効データ量に基づきコピー元ブロックを選択する図29のプロセスの第1の実施形態には、実装が比較的簡単にすむという利点がある。しかし、パーシャルブロックの価値を考慮に入れて、このプロセスを改良することもできる。パーシャルブロックには消去済み容量があり、そこにはデータを書き込むことができるが、用済みブロックと無効ブロックには消去済み容量がない。用済みブロックを新規データの蓄積に使うには、事前にそこから別のブロックへ有効データを移し、用済みブロックを消去し、新規データの蓄積に使える状態にしなければならない。しかし、パーシャルブロックには消去済み容量があって、再生操作のオーバーヘッドを被ることなくデータを書き込むことができる。例えば、有効データ量が最も少ないという理由だけで、データの書き込みが可能な消去済み容量を大量に保有するパーシャルブロックを再生するのは得策でない。
【0145】
したがって、図29のプロセスの別の実施形態では、パーシャルブロックにある有効データの量と消去済み容量の両方を踏まえて、コピー元の再生ブロックの候補となるパーシャルブロックを選ぶ。図30は、パーシャルブロックの中にあるデータの構成要素を示す。このブロック(またはメタブロック)には、有効データを収容する1つ以上のページ(またはメタページ)のほかに、データを書き込める1つ以上の消去済みページがある。図30の例に見られるように、パーシャルブロックの1つ以上のページには用済みデータが入ることもある。
【0146】
図29のこれらのプロセスの実施形態では、好ましくは用済みブロックと無効ブロックのリストとは別のリストでパーシャルブロックをステップ701で管理する。消去済み容量がごく僅かで(現状ではさほど有用でないことを意味する)、移動を要する有効データが少ないパーシャルブロックは、再生操作リストの先頭寄りに移される。そのようなブロックの主な内容は用済みデータになる。逆に、再生ブロックの候補となる見込みが最も低いのは、大量の消去済み容量があり(データの蓄積に役立つ見込みがあることを意味する)、移動を要する有効データが大量にあるパーシャルブロックである。消去済み容量があるパーシャルブロックを再生しても、用済みブロックを再生した場合と同量の蓄積容量が論理アドレス空間に追加されるわけではない。役に立つ消去済み容量がなく、コピーを要する有効データもない無効ブロックは明らかに、再生の対象として最も魅力的なブロックなのである。
【0147】
図29の再生ブロック識別ステップ703の第2の実施形態では、パーシャルブロックと、用済みブロックと、無効ブロックのそれぞれに1つずつ、合わせて3通りのリストをステップ701で管理する。無効ブロックがあるなら、無効ブロックのリストでブロックがなくなるまでこのリストから再生ブロックを選択する。無効ブロックのリストに特別な順序はないが、先入れ先出し(FIFO)順にして、リストに登録された期間が最も長い無効ブロックが最初に選ばれるようにすることも可能である。次に無効ブロックがなければ、用済みブロックリストにある全ブロックで有効データ量が最も少ないブロックを選ぶ。
【0148】
ステップ703で無効ブロックリストか用済みブロックリストにブロックがなければ、パーシャルブロックリストのブロックを再生ブロックに選ぶ。有効データ量が最も少ないパーシャルブロックが選ばれるようにすることもできるが、好ましくは消去済み容量の有用性が分かる形でパーシャルブロックを格付けする。それには、各パーシャルブロックの「再生利得」を次のとおり計算する。
再生利得=(S−kE)/V (1)
式中、Sは合計データ蓄積ページ数によるブロックサイズであり、Eはデータを書き込める消去済み容量のページ数であり、Vは別のブロックへ移す必要がある有効データを含むページ数である。定数kはブロックの消去済み容量の有用性を重み付けするためのものであるが、1に設定することもできる。kEの値が増すにつれ再生利得は低下する。Vの値が増す場合も再生利得は低下する。ステップ703では、再生利得の値が最も高いパーシャルブロックが再生ブロックとして選ばれる。これとは別の数式で項EおよびVを使って再生利得を定義し、有効データを保持することのシステム動作にとってのデメリットと消去済み容量のメリットとでバランスをとることもできる。再生利得はブロックに変化があるたびに、例えばブロックの消去済み容量にデータが書き込まれるたびに、計算し、ファイルディレクトリやFITで管理する情報の一部として蓄積することができる。
【0149】
この第2の実施形態を示す図31は、パーシャルブロックリスト、用済みブロックリスト、および無効ブロックリストの3通りのリスト(図29のステップ701で管理)から再生ブロックを選択(図29のステップ703)する方法を説明するものである。ステップ721ではまず、無効ブロックリストに記載されたブロックの有無を判断する。そのようなブロックが多数存在する場合は、リストに登録された期間が最も長いブロックがステップ723で再生ブロックに選ばれる。無効ブロックリストにブロックがなければ、ステップ725で用済みブロックリストにおける項目の有無を判断する。その際、用済みブロックリストに2つ以上のブロックがある場合は、ステップ727で有効データ量が最も少ないブロックが再生ブロックに選ばれる。用済みブロックリストに項目がないことがステップ725で判明する場合は、ステップ729でパーシャルブロックリストをあたる。パーシャルブロックリストに2つ以上のブロックがある場合は、再生利得が最も高いブロックが再生ブロックに選ばれる。再生利得では、前述した式(1)を使用する等して、ブロック内の有効データ量と消去済み容量を考慮に入れる。パーシャルブロックリストに何もなければステップ721まで戻り、リストのいずれか1つでブロックが出現するまでプロセスを繰り返す。再生ブロックが選択された後、処理は図29のステップ705へ進む。
【0150】
図32のフローチャートに第3の実施形態を示す。ステップ741でも図29のステップ703の実行が始まり、図29のステップ701で管理する無効ブロックリストで項目を探す。無効ブロックリストに2つ以上の項目がある場合は、図32のステップ743で最も古いブロックが再生ブロックに選ばれる。無効ブロックリストに項目がなければ、次のステップ745により用済みブロックリストで項目の有無を判断する。項目がある場合の後続するステップは図31の実施形態と異なり、パーシャルブロックリストにも1つ以上の項目がある場合は、用済みブロックリストとパーシャルブロックリストのどちらで再生ブロックを選べばよいかを判断する。
【0151】
図32のステップ747では、有効データ量が最も少ないブロックを用済みブロックリストで識別する。次に、ステップ749でパーシャルブロックリストに1つ以上のブロックが存在するか否かを判断し、存在する場合は、有効データ量が最も少ないブロックをステップ751で識別する。次のステップ753では、用済みブロックリストで識別した1ブロックとパーシャルブロックリストで識別した1ブロックとで選択を行う。それには、前と同じ項V、E、およびkを使用し、ステップ751でパーシャルブロックリストから識別したブロックで量(V+kE)を計算する。この量をステップ747で用済みブロックリストから識別したブロックの有効データ量Vに比較する。パーシャルブロックの量(V+kE)が用済みブロックのVを上回るなら、ステップ755で用済みブロックが再生ブロックに選ばれる。しかし、用済みブロックのVが識別されたパーシャルブロックの量(V+kE)を上回るなら、ステップ757でパーシャルブロックが再生ブロックに選ばれる。
【0152】
識別されたパーシャルブロックの消去済み容量kEをこのブロックの有効データVに加えたものを、識別された用済みブロックの有効データVのみに比較すると、そのプロセスは用済みブロックが優先的に選ばれる形に偏る。識別された用済みブロックと同量の有効データを持つ識別されたパーシャルブロックには、その消去済み容量にデータを蓄積するという使い道が残っているため、選ばれずに残る。実際は、有効データ量が用済みブロックの有効データ量よりkE少ないパーシャルブロックが選ばれずに残る。
【0153】
図32のステップ745へ戻り、用済みブロックリストに項目がない場合は、パーシャルブロックリストに記載されたブロックの有無をステップ759で判断する。ブロックがなければプロセスはステップ741まで戻り、3つのリストのいずれか1つにブロックが登録されるまで繰り返される。リストに多数のパーシャルブロックがある場合は、ステップ761で有効データ量が最も少ないブロックを再生ブロックとして選択する。あるいは、第2の実施形態(図31)のステップ731との関係で説明したように、再生利得を用いてパーシャルブロックを選択することもできる。
【0154】
第3の実施形態では使用するリストを2つに絞ることもできる。第1のリストは用済みブロックリストで、このリストには、用済みデータを収容し消去済み容量がないブロックの項目が入る。図32に見られるように単独の無効ブロックリストを使用するのではなく、無効ブロックと用済みブロックの両方を1つの「用済み」ブロックリストに入れる。これらのブロックは有効データを収容することもある。リストの各項目にはフィールドがあり、このフィールドには該当するブロックの有効データ量を表す値が入る。リストの項目は、このフィールドの値の順に並べる。その結果、用済みデータがあって有効データはないブロック(無効ブロック)は、この第1のリストの先頭に集まる。
【0155】
この第3の実施形態の代案で、第2のリストはパーシャルブロックリストであり、このリストには、ある程度の消去済み蓄積容量を持つブロックの項目が入る。これらのブロックは有効データを収容することもある。リストの各項目にはフィールドがあり、このフィールドには該当するブロックの有効データ量を表す値が入る。リストの項目は、このフィールドの値の順に並べる。図32のステップ753の手法により、第1または第2のリストの先頭からブロック(有効データの量が最も少ないブロック)を選ぶことができる。
【0156】
図33の表は、この第3の実施形態の修正版による再生操作でパーシャルブロックリストと用済みブロックリストに入るブロックタイプの詳細を伝えるものである。パーシャルブロックリストに入るブロックは、有効データと消去済み容量の両方を含むブロックである。ブロックに用済みデータがあるかどうかは問題とされない。用済みブロックリストに入るブロックは、用済みデータを含み、かつ有効データと消去済み容量の両方ではなくいずれか一方を含むブロックである。
【0157】
結論
これまで本発明の様々な態様をその代表的な実施形態との関係で説明してきたが、本発明が添付の特許請求の範囲内で保護を受ける権利があることは理解される。

【特許請求の範囲】
【請求項1】
アドレスのブロックに分割された連続論理アドレス空間の中でファイルオブジェクトのデータにアドレスを割り当てる方法であって、
ブロックの容量に満たない一定量の有効データにアドレスを割り当てたブロックを含む少なくとも1つのリストを管理するステップと、
前記少なくとも1つのリストからブロックを選択するステップと、
選択されたブロックから別のブロックへ有効データをコピーするステップと、
その後、別のデータへのアドレス割り当てに選択されたブロックを利用するステップと、
を含む方法。
【請求項2】
請求項1記載の方法において、
前記ブロックを選択するステップは、前記少なくとも1つのリストから、リスト上の別ブロックの有効データアドレス量に対する有効データアドレス量に基づきブロックを選択するステップを含む方法。
【請求項3】
請求項1記載の方法において、
前記ブロックを選択するステップは、前記少なくとも1つのリストから、リスト上の別ブロックの有効データアドレス量に対する有効データアドレス量が最も少ないブロックを選択することを含む方法。
【請求項4】
請求項1記載の方法において、
前記少なくとも1つのリストからブロックを選択するステップは、前記少なくとも1つのリストから、前記少なくとも1つのリスト上の別ブロックの未使用蓄積容量に対する未使用蓄積容量に基づきブロックを選択するステップをさらに含む方法。
【請求項5】
インターフェイスで連続論理アドレス空間を管理する方法であって、
論理アドレス空間を個別アドレスからなるブロックに分割するステップと、
最初に、各ファイルオブジェクトのデータのアドレスを、ブロックのいずれかの中で指定するステップと、
その後、各ファイルオブジェクトのうちの少なくとも1つのファイルオブジェクトのデータの少なくとも一部分のアドレスを、最初の指定とは異なる少なくとも1つのブロックの中で再指定するステップと、
を含む方法。
【請求項6】
請求項5記載の方法において、
前記アドレスを再指定するステップは、各ファイルオブジェクトのうちの少なくとも1つのファイルオブジェクトのデータの前記少なくとも一部分を変えることなくアドレスを再指定するステップを含む方法。
【請求項7】
データ処理システムであって、
連続アドレス空間を有するインターフェイスと、
プロセッサであって、
インターフェイスを通じて転送されるファイルオブジェクトのデータに割り当てるため、論理アドレス空間を個別アドレスからなるブロックに分割する機能と、
ある特定のファイルオブジェクトのデータの少なくとも一部分のアドレスを、特定のファイルオブジェクトのデータの前記少なくとも一部分を変えることなく、少なくとも1つの指定ブロックからなる第1のセットの中から、少なくとも1つの指定ブロックからなる別のセットへ、再指定する機能と、を少なくとも実行するようにプログラムされるプロセッサと、
を備えるシステム。
【請求項8】
請求項7記載のシステムにおいて、
前記インターフェイスは、ファイルオブジェクトのデータを蓄積する再プログラム可能不揮発性メモリシステムとの接続にさらに適するシステム。
【請求項9】
データ処理システムであって、
インターフェイスを通じて転送されるファイルオブジェクトのデータに割り当てるため、個別アドレスからなるブロックに分割された連続アドレス空間を有するインターフェイスと、
プロセッサであって、
アドレスが割り当てられたファイルオブジェクトのデータの特徴に従って、少なくとも1つのブロックリストを管理する機能と、
アドレスが割り当てられた少なくとも1つのファイルオブジェクトのデータの特徴をもとに、リスト上で1つ以上のブロックを識別する機能と、
識別された1つ以上のブロックにある少なくとも1つのファイルオブジェクトに、1つ以上の異なるブロックのアドレスを再指定する機能と、
その後、識別された1つ以上のブロックを、いずれか1つの異なるファイルオブジェクトのデータの受け付けに使用できるものとして指定する機能と、を少なくとも実行するようにプログラムされるプロセッサと、
を備えるシステム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7A】
image rotate

【図7B】
image rotate

【図7C】
image rotate

【図8A】
image rotate

【図8B】
image rotate

【図8C】
image rotate

【図9A】
image rotate

【図9B】
image rotate

【図9C】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13A】
image rotate

【図13B】
image rotate

【図13C】
image rotate

【図13D】
image rotate

【図14A】
image rotate

【図14B】
image rotate

【図14C】
image rotate

【図14D】
image rotate

【図14E】
image rotate

【図15】
image rotate

【図16A】
image rotate

【図16B】
image rotate

【図16C】
image rotate

【図16D】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28A】
image rotate

【図28B】
image rotate

【図28C】
image rotate

【図28D】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate


【公表番号】特表2010−515163(P2010−515163A)
【公表日】平成22年5月6日(2010.5.6)
【国際特許分類】
【出願番号】特願2009−544200(P2009−544200)
【出願日】平成19年12月19日(2007.12.19)
【国際出願番号】PCT/US2007/088180
【国際公開番号】WO2008/083001
【国際公開日】平成20年7月10日(2008.7.10)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.コンパクトフラッシュ
【出願人】(506197901)サンディスク コーポレイション (175)
【Fターム(参考)】