(57)【要約】  （フラッシュメモリなどの）不揮発性メモリシステムにおいてデータを管理するための技法が開示される。コントローラが、ホストのファイルシステムに関する情報を利用することが可能となり、この情報はホストによって不揮発性メモリに格納され、１以上のクラスタ（またはクラスタを有するセクタ）が現在割り当てられているかどうかの判定が行われる。コントローラはホストのファイルシステムに関する情報を利用して、ホストが、次の未使用クラスタへデータを送信する時点を特定し、不揮発性メモリ内の別の記憶位置からデータをコピーすることによって、シーケンシャルなフォーマットでそのようなデータの格納を行うことが可能となる。
2008507756.tif 000002
【特許請求の範囲】
【請求項１】
コントローラと不揮発性メモリアレイとを備えたメモリシステムに適応性のある方法でデータ部分を格納する方法において、前記コントローラが、
前記不揮発性メモリアレイ内のファイルアロケーションテーブルまたはディレクトリ内の、ホストによって格納された情報から論理アドレス範囲の属性を取得するステップと、
前記論理アドレス範囲内に論理アドレスを含むデータ部分のための複数の格納方式のなかから、前記論理アドレス範囲の属性に従って格納方式を選択し、
前記選択された格納方式に従って前記データ部分を格納するステップと、
を備える方法。
【請求項２】
請求項１記載のデータ部分を格納する方法において、
前記論理アドレス範囲の属性は、前記論理アドレス範囲がホストデータの格納を行うための次の未使用の論理アドレス範囲である属性となる方法。
【請求項３】
請求項２記載のデータ部分を格納する方法において、
前記選択された格納方式は、シーケンシャルな更新ブロックでの前記データ部分の格納を含む方法。
【請求項４】
請求項１記載のデータ部分を格納する方法において、
前記論理アドレス範囲の属性は、前記論理アドレス範囲がホストデータの格納を行うための次の未使用の論理アドレス範囲ではない属性となる方法。
【請求項５】
請求項４記載のデータ部分を格納する方法において、
前記選択された格納方式は、カオス更新ブロックでの前記データ部分の格納を含む方法。
【請求項６】
請求項１記載のデータ部分を格納する方法において、
前記データ部分が前記不揮発性メモリアレイ内の第１の記憶位置に以前に格納され、前記論理アドレス範囲の属性は、前記論理アドレス範囲が前記ホストによって割り当てられる属性であり、前記選択された格納方式が、第１の記憶位置から第２の記憶位置へ前記データ部分を前記不揮発性メモリアレイにコピーすることを含む方法。
【請求項７】
請求項６記載のデータ部分を格納する方法において、
前記データ部分が前記不揮発性メモリアレイ内の第１の記憶位置に以前に格納されたものであり、前記論理アドレス範囲の属性は、前記論理アドレス範囲が前記ホストによって割り当てられる属性であり、前記選択された格納方式が、前記第１の記憶位置から第２の記憶位置へ前記データ部分をコピーすることなく、前記第１の記憶位置において前記データ部分の保守管理を行う方法。
【請求項８】
請求項１記載のデータ部分を格納する方法において、
前記属性は、前記ファイルアロケーションテーブルまたはディレクトリから導き出されたデータ属性格納部から取得される方法。
【請求項９】
ホストから受信したデータを不揮発性メモリアレイに格納する方法において、
１以上のアドレス可能なデータ単位を前記ホストから受け取るステップと、
前記ホストがデータの格納用として利用可能な複数の論理アドレス範囲を特定するために、前記ホストが前記不揮発性メモリアレイに格納した情報を分析するステップと、
前記１以上のアドレス可能なデータ単位が前記ホストにとって利用可能な論理アドレスの次の範囲へ割り当てられているかどうかを判定するために、前記ホストにとって利用可能な前記複数の論理アドレス範囲を前記１それ以上のアドレス可能なデータ単位の論理アドレスと比較するステップと、
前記判定に依存して、前記１以上のアドレス可能なデータ単位を格納するステップと、
を備える方法。
【請求項１０】
請求項９記載のホストから受信したデータを不揮発性メモリアレイに格納する方法において、
前記１以上のアドレス可能な単位が、利用可能な次のシーケンシャルな記憶位置に指定されていれば、前記１以上のアドレス可能な単位を格納する態様がシーケンシャルな態様となり、前記１以上のアドレス可能な単位が、利用可能な次のシーケンシャルな記憶位置に指定されていなければ、前記格納する態様が非シーケンシャルな態様となる方法。
【請求項１１】
請求項９記載のホストから受信したデータを不揮発性メモリアレイに格納する方法において、
前記１以上のアドレス可能なデータ単位を格納するステップは、前記１以上のアドレス可能なデータ単位の論理アドレスと、最後に書き込まれたアドレス可能なデータ単位の論理アドレスとの間の論理アドレスのギャップが所定量を上回るかどうかを含む追加要因に依存する態様で行われる方法。
【請求項１２】
請求項１１記載のホストから受信したデータを不揮発性メモリアレイに格納する方法において、
追加の要因とは、前記１以上のアドレス可能なデータ単位を格納するための更新ブロックが、所定量のデータよりも多くのデータをシーケンシャルな形で含むかどうかというものである方法。
【請求項１３】
アドレス可能なデータ単位でホストからデータを受け取る、不揮発性メモリにデータを格納するメモリデバイスにおいて、
ホストのファイルアロケーションテーブルのコピーを含む不揮発性メモリアレイと、
前記不揮発性メモリアレイとの通信時のメモリコントローラであって、前記ホストのファイルアロケーションテーブルのコピー内容をモニタし、前記ホストのファイルアロケーションテーブルのコピーから論理アドレス空間部分の割当て状態を判定し、前記論理アドレス空間部分内に論理アドレスを含むアドレス可能なデータ単位のためのデータ管理方式を前記割当て状態に応じて選択するメモリコントローラと、
を備えるメモリデバイス。
【請求項１４】
請求項１３記載の不揮発性メモリにデータを格納するメモリデバイスにおいて、
前記メモリデバイスは、コントローラと取り外し可能に接続された取り外し可能なメモリカードの一部を形成するメモリデバイス。
【請求項１５】
請求項１３記載の不揮発性メモリにデータを格納するメモリデバイスにおいて、
前記メモリコントローラは、前記論理アドレス空間部分の割当て状態をデータ属性格納部に記録するメモリデバイス。
【請求項１６】
請求項１３記載の不揮発性メモリにデータを格納するメモリデバイスにおいて、
前記不揮発性メモリアレイに格納するために、前記アドレス可能なデータ単位をホストから受け取り、前記論理アドレス空間部分が次の未使用部分であれば、前記データ管理方式がシーケンシャルなブロックに格納部を設け、前記論理アドレス空間部分が次の未使用部分でなければ、前記データ管理方式がカオスブロックに格納部を設けるメモリデバイス。
【請求項１７】
請求項１３記載の不揮発性メモリにデータを格納するメモリデバイスにおいて、
前記メモリデバイスがガーベッジコレクション処理を行うとき、前記アドレス可能なデータ単位が前記不揮発性メモリアレイ内の第１の記憶位置に格納され、前記論理アドレス空間部分が割り当てられていれば、前記データ管理方式は、前記アドレス可能なデータ単位を前記不揮発性メモリアレイ内の第２の記憶位置へコピーを行う処理となり、前記論理アドレス空間部分が割り当てられていなければ、前記データ管理方式は、コピーを行うことなく、第１の記憶位置において前記アドレス可能なデータ単位の保守管理を行う処理となるメモリデバイス。
【請求項１８】
不揮発性メモリ内のホストデータの格納用メモリコントローラにとって利用可能な代替の格納方式の間で選択を行うためのプログラムコードを含むコンピュータ可読媒体において、
複数の論理アドレス空間部分の割り当て状態をホストが前記不揮発性メモリに格納した情報から特定し、前記割り当て状態を前記メモリコントローラへ出力するコンピュータプログラムコードと、
ホストデータ部分の論理アドレスを含む論理アドレス空間部分の割り当て状態に従って、前記ホストデータ部分のためのデータ管理方式を選択するコンピュータプログラムコードと、
を含むコンピュータ可読媒体。
【請求項１９】
請求項１８記載のコンピュータ可読媒体において、
前記論理アドレス空間部分が割り当てられていない論理アドレス空間の次の部分であれば、前記データ部分をシーケンシャルなブロックに格納し、そうでなければ、前記データ部分をカオスブロックに格納するように、前記選択された管理方式に従って前記ホストデータ部分に対して動作するコンピュータプログラムコードをさらに含むコンピュータ可読媒体。
【請求項２０】
請求項１８記載のコンピュータ可読媒体において、
前記論理アドレス空間部分が割り当てられていれば、古い記憶位置から新しい記憶位置へ前記データ部分をコピーし、前記論理アドレス空間部分が割り当てられていなければ、新しい記憶位置へコピーを行うことなく、前記データ部分を前記古い記憶位置に残すように、前記選択された管理方式に従って前記ホストデータ部分に対して動作するコンピュータプログラムコードをさらに含むコンピュータ可読媒体。
【請求項２１】
請求項１８記載のコンピュータ可読媒体において、
前記複数の論理アドレス空間部分の割り当て状態を含むデータ属性格納部を設けたコンピュータプログラムコードをさらに含むコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、計算システムと共に用いられるデータ格納システムに関し、特に、不揮発性メモリ記憶装置においてデータの保守管理を行うための技法に関する。
【背景技術】
【０００２】
特に、小形の形状のファクタカードの形で今日使用されている商業的に成功した多くの不揮発性メモリ製品が存在する。これらの不揮発性メモリ製品には、１以上の集積回路チップ上に形成されたフラッシュＥＥＰＲＯＭアレイ（電気的に消去可能でプログラム可能なリードオンリメモリ）セルが使用されている。典型的には、個々のホストとのインターフェイスとして集積回路チップ上のメモリコントローラが提供される。ホストは、コントローラを使用して不揮発性メモリで（読み出し、書き込みなどの）種々の処理を行うことができる。コントローラには１以上の特別の回路が設けられ、そのような回路として、典型的には、マイクロプロセッサ、ある種の不揮発性リードオンリメモリ（ＲＯＭ）、揮発性ランダムアスセスメモリ（ＲＡＭ）、並びに、データがコントローラの中を通り抜けるとき、データのプログラミング中およびデータの読み出し中にデータから生じる誤り訂正符号（ＥＣＣ）の計算を行う回路などがある。市販のカードのいくつかとして、コンパクトフラッシュ（登録商標）（ＣＦ）カード、マルチメディアカード（ＭＭＣ）、セキュアデジタル（ＳＤ）カード、スマートメディアカード、個人用タグ (personnel tag)（Ｐ−Ｔａｇ）およびメモリスティックカードがある。ホストには、パーソナルコンピュータ、ノート形コンピュータ、携帯用個人情報端末（ＰＤＡ）、種々のデータ通信装置、デジタルカメラ、移動電話、携帯用オーディオプレーヤー、自動車用サウンドシステム、および、同種の機器が含まれる。メモリカードの実施構成以外にも、不揮発性メモリは種々のタイプのホストシステムの中へ組み込むことができる。
【０００３】
ほとんどすべての集積回路用アプリケーションにおける場合のように、フラッシュＥＥＰＲＯＭメモリセルアレイの場合にも、いくつかの集積回路機能の実現に必要なシリコン基板面積の縮小に対する圧力が存在する。所定のサイズのメモリカードと、別の種類のパッケージとの記憶容量を増やすために、所定の面積のシリコン基板に格納できるデジタルデータ量を増やすようにという、容量の増加とサイズの縮小化の双方を求める要望が継続的に存在する。データの記憶密度を高める１つの方法として、１個のメモリセル当たりおよび／または記憶素子または記憶ユニット当たり２ビット以上のデータを格納する方法がある。これは、記憶素子の電荷レベルの電圧範囲のウィンドウを３以上の状態に分割することにより達成される。このような４状態を利用することにより、個々のセルに２ビットのデータを格納することが可能となり、いずれの状態も、記憶素子当たり３ビットのデータ等々が格納されることになる。フローティングゲートを利用する多状態フラッシュＥＥＰＲＯＭ構造については、米国特許第５，０４３，９４０号（特許文献１）および第５，１７２，３３８号（特許文献２）に記載され、さらに、誘電体フローティングゲートを用いる構造については、前述した米国特許出願第２００３／０１０９０９３号（特許文献３）に記載されている。多状態メモリセルアレイの選択された部分は、米国特許第５，９３０，１６７号（特許文献４）および米国特許第６，４５６，５２８号（特許文献５）に記載されているように、種々の理由によって２状態（２進）での動作も可能となる。
【０００４】
典型的なフラッシュＥＥＰＲＯＭアレイのメモリセルは、一括消去される個別のセル“ブロック”に分割される。個々の消去ブロックは通常１以上のデータページを格納し、この１ページがプログラミングと読み出しとを行う最小単位であるが、同時に異なるサブアレイすなわちプレーンで２以上のページのプログラミングや読み出しを行うことも可能である。個々のページは通常１以上のデータセクタを格納し、このセクタサイズはホストシステムによって定義される。一つの例示のセクタには、磁気ディスク駆動装置に関して定義されている標準規格に準拠する５１２バイトのユーザデータが含まれ、これに加えて、ユーザデータおよび／またはユーザデータが格納されている消去ブロックに関する或るバイト数のオーバーヘッド情報も含まれている。このようなメモリは、一般に３２、１２８またはそれ以上のページを持つ個々の消去ブロック内に構成され、個々のページには１セクタまたはわずか数セクタのホストデータが格納される。ブロックに対してデータを再書き込みするためにブロックをまず消去することが望ましいことも留意されたい。
【０００５】
ユーザデータをプログラムしてメモリアレイの中へ入れ、このメモリアレイからユーザデータを読み出す間の並行性レベルを高めるために、このアレイはプレーンと呼ばれるサブアレイに通常分割され、これらのサブアレイは、並列処理が可能となるようにサブアレイ自身のデータレジスタ並びにその他の回路を備え、これによって、数個のプレーンまたはすべてのプレーンの各々に対してデータセクタを同時にプログラムしたり、数個のプレーンまたはすべてのプレーンの各々からデータセクタを同時に読み出したりすることができるようになる。単一の集積回路のアレイを物理的に分割してプレーンに変えることも可能であるし、あるいは、別々の１以上の集積回路チップから個々のプレーンを形成することも可能である。このようなメモリの実施構成の例については、米国特許第５，７９８，９６８号（特許文献６）および米国特許第５，８９０，１９２号（特許文献７）に記載されている。
【０００６】
メモリをさらに効率的に管理するために、消去ブロックを仮想ブロックすなわちメタブロックと一体に論理的にリンクすることも可能である。すなわち、個々のプレーンから得られる１つの消去ブロックを含むように個々のメタブロックは定義される。メタブロックの利用については、国際公開特許出願第０２／０５８０７４号（特許文献８）に記載されている。メタブロックは、データのプログラミングと読み出しのための宛先としてホストの論理ブロックアドレスにより特定される。同様に、メタブロックからなるすべての消去ブロックは一括消去される。このような大きなブロックおよび／またはメタブロックと共に動作するメモリシステム内のコントローラは、ホストから受信した論理ブロックアドレス（ＬＢＡ）と、メモリセルアレイ内の物理ブロック番号（ＰＢＮ）との間での変換を含む複数の機能を実行する。このブロック内の個々のページは、典型的には、このブロックアドレス内のオフセット値によって特定される。アドレス変換は、論理ブロック番号（ＬＢＮ）と論理ページの中間項の利用を含む場合が多い。したがって、メモリアレイ内のブロックは単一の消去ブロックから構成されるものであってもよいし、あるいは、メタブロックを形成するために論理的にリンクされる２以上の消去ブロックから構成されるものであってもよい。
【０００７】
ホストアプリケーションの視点から見れば、論理アドレス０を起点として論理アドレスＮで終る論理アドレス空間にフラッシュメモリを分割することができる。図１はホストの論理アドレス空間１０２を示し、この論理アドレス空間１０２は“論理セクタ”に分割されている。ホストは（４〜６４などの）いくつかの論理セクタをクラスタにグループ化する。図１に示されているように、ホストは、クラスタＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈを含むクラスタに論理アドレス空間１０２を分割してもよい。したがって、これらのクラスタの各々は、（クラスタ当たり４〜６４の論理セクタなどの）所定数のセクタを表わすことができることになる。いずれの場合にも、ホストは、“クラスタ”と呼ばれる論理データ単位でデータを割り当てることになる。例えば、クラスタＡ、Ｂ、Ｃを用いてファイル１を割り当てることが可能であり、これに対してクラスタＤを用いてファイル２が割り当てられる。ホストがクラスタの中にファイルを割り当てることに留意されたい。しかし、クラスタ内のすべての論理セクタがファイル用としてデータを含む必要があるわけではない。例えば、（唯一の論理セクタなどの）クラスタＣの一部だけがデータを含むようにすることも可能である。それでも、たとえクラスタ内のすべての論理セクタが必ずしも必要となるというわけではなくても、ホストは代表的にクラスタ全体を１つのファイルに割り当てることになる。
【０００８】
ホストはファイルアロケーションテーブル（ＦＡＴ）１０４を用いてファイルを追跡することができる。ファイルアロケーションテーブル（ＦＡＴ）１０４は論理的ファイル構造を効果的に表わし、ファイルの各々に関連して論理的ファイル構造の中にどのようなクラスタが割り当てられているかをもまた示すものである。ホストは、ファイルアロケーションテーブル（ＦＡＴ）１０４の更新によって論理的ファイル構造の保守管理を行う。例えば、新規ファイルが割り当てられると、ファイルアロケーションテーブル（ＦＡＴ）１０４が更新されて、特に、どのようなクラスタが新規ファイル用として割り当てられているかが示される。また、ファイルあるいはディレクトリが削除されると、ホストはファイルアロケーションテーブル（ＦＡＴ）１０４を更新する。クラスタは、更新の結果、ホストによって割当てが解除される場合もあることに留意されたい。例えば、ホストがファイル１を削除すると、更新されたファイルアロケーションテーブル（ＦＡＴ）１０６は、ファイル１を格納するためにホストが割り当てていたクラスタＡ、Ｂ、Ｃを効果的に解除するという結果を生み出すことができる。
【０００９】
ホストの論理アドレス空間とは対照的に、フラッシュメモリコントローラの論理アドレス空間は“論理ブロック”に分割される。言い換えれば、コントローラ用の同じ論理アドレス空間１０２を論理アドレス空間１０３として表わすことも可能である。論理アドレス空間１０２と論理アドレス空間１０３の双方の基本単位はこの例ではセクタである。図１に示されているように、論理アドレス空間１０３は、論理ブロック１と論理ブロック２とを含む種々の論理ブロックに分割することも可能であり、個々の論理ブロックには、メモリアレイの単一ブロックに対応づけられる複数のデータセクタが含まれる。これらの論理ブロックは、例えば、単一の消去ブロックやメタブロックのような単位として消去することができるメモリブロックに対応づけられる。したがって、論理ブロックとメモリアレイのブロックとの間に１対１の対応関係が存在することになり、その場合、論理ブロック内のすべてのセクタは単一ブロックに格納される。例えば、論理ブロック１を対応づけてブロック２にするようにしてもよいなどである。要するに、ホストとコントローラとが異なる論理メモリ単位を使用することになる。ホストが論理アドレス空間を分割してクラスタにするのに対して、コントローラは論理アドレス空間を分割して論理ブロックにする。典型的には、アプリケーション用データおよびサブディレクトリエントリのみに対して割り当てられる論理アドレス空間にホストクラスタが適用されることにも留意されたい。さらに、別のシステムタ用として割り当てられた論理アドレス空間をホストがクラスタとして管理しなくてもよくなる。通常、第１のクラスタは論理アドレス空間の冒頭に位置しなくてもよいことにも留意されたい。したがって、クラスタと論理ブロックとは互いに一直線にならなくてもよくなる。
【００１０】
これに対して、従来方式のコントローラはホストが利用する論理構成を認知するものではない。従来方式では、コントローラは、ホストが使用する論理アドレス１０２を単に論理アドレス１０３に対応づけ、次いで、物理アドレス１１０にするにすぎない。これは、従来方式のコントローラが、ホストの論理データ構成や、ホストの処理がデータに対して及ぼしたかもしれない悪い結果を考慮していないことを意味する。例えば、新規ファイルが割り当てられると、論理的ファイルシステム１０４は更新されて、特に、どのようなクラスタが新規ファイル用として割り当てられたかが示されることになる。また、ファイルやディレクトリが削除されると、ホストは論理的ファイルシステム１０４の更新を行う。さらに、１以上のクラスタがホストにより割当てを解除される場合もある。例えば、ホストがファイル１を削除すると、更新されたファイルアロケーションテーブル１０６によって、ファイル１を格納するために前回割り当てられたクラスタＡ、Ｂ、Ｃの割当てをホストが効果的に解除したことが示される（すなわち、ファイル１は更新されたファイルアロケーションテーブル１０６にはもはや表されない）。ホストによってクラスタＡ、Ｂ、Ｃが割当てを解除され、消去が可能になるとはいえ、従来方式のコントローラによって、割当て解除済みのクラスタＡ、Ｂ、Ｃに対応する当該データの“ガーベッジコレクション”は行われなくなる。これは、データがメモリにそのまま持続して存在することを意味する。ガーベッジコレクションとは、旧いデータセクタを含む原ブロックから更新ブロックへ有効なデータセクタのコピーを行う処理である。すべての有効なデータセクタがコピーされると、原ブロックは消去用としてマークすることができる。典型的には、データは２以上のブロックから単一ブロックへ統合され、それによってさらに効率的にデータが格納され、メモリアレイ内の空間が解放されることになる。ガーベッジコレクション中にデータの不必要なコピーを行うことはこのような処理の効率を下げることになる。さらに、２つのブロック内のデータが１つのブロックに統合される際、ガーベッジコレクション中にブロックの更新が行われると、割当て解除済みのデータが複数回コピーされる可能性がある。
【００１１】
例示によってさらに説明すると、原ブロック１２０が図１に描かれている。説明を簡略にするために、原ブロック１２０には、ファイル１と２を割り当てるためにホストが使用する論理クラスタＡ、Ｂ、Ｃ、Ｄに対応するデータが含まれていると想定する。また、別の想定として、ホストがファイル１（クラスタＡ、Ｂ、Ｃ）の割当てが遅れて解除されたと想定する。この想定によって、原ブロック１２０には、すべての論理クラスタＡ、Ｂ、Ｃ、Ｄがまだ含まれていることになる。というのは、コントローラには、ファイル１がホストによって割当てを解除されたことを知る方法がないからである。これに対して、ホストは、原ブロック１２０のデータ部分Ｄの更新をコントローラに要求している。言い換えれば、ある時点において、ホストは、ファイル２を変更し、それによって、１以上の論理セクタに対応するデータ用として更新すべきものであることがわかっている論理アドレスを用いて、書き込み要求の送信を望むことが可能となる。コントローラは、ホストによりアドレス指定されたこれらの論理セクタがホストによってすでに書き込まれたセクタ（すなわち、クラスタＤ）に対応するものであるため、更新ブロック１２２が部分的に用いられていると判定する。というのは、原ブロック１２０内のデータの上書きは不可能であるからである。このことは、更新ブロック１２２が“閉じられる”（すなわち、原ブロック１２０内のすべてのデータがブロック１２２へコピーされる）までのしばらくの間、２つのブロックを用いて論理ブロックを表わすことができることを意味する。例えば、ガーベッジコレクションサイクル中に原ブロック１２０と更新ブロック１２２とを組み合わせ、それによって更新ブロック１２２が“原”ブロック１２２になり、前の原ブロック１２０が消去され、利用可能なメモリブロックのプールへ戻されるようにすることも可能である。いずれの場合にも、割当てを解除されたクラスタ（Ａ、Ｂ、Ｃ）に対応するデータが更新ブロック１２２へ遅かれ早かれコピーされ、その結果更新ブロック１２２を閉じることが可能となり、原ブロック１２０を消去できるようになることに留意されたい。コントローラは、揮発性メモリや、論理データブロックへのメモリブロックの割当てを定義する不揮発性メモリ内のマッピングテーブルの保守管理を行うことも可能である。不揮発性メモリに格納されたデータのコピー処理にはかなりの量の時間とリソースとを必要とする。しかし、（割当て解除済みのクラスタＡ、Ｂ、Ｃなどの）割当てを解除されたデータのコピー処理を行う必要はなくなる。したがって、割当て解除済みのデータをコピーしなければ、システムパフォーマンスのさらなる改善が可能となる。一般に、広く利用されているアドレス規定に従いながらできるかぎりシステム性能の改善を図ることが望ましい。
【００１２】
したがって、代替の不揮発性メモリ管理技法は、有益なものとなる。
【特許文献１】米国特許第５，０４３，９４０号
【特許文献２】米国特許第５，１７２，３３８号
【特許文献３】米国特許出願第２００３／０１０９０９３号
【特許文献４】米国特許第５，９３０，１６７号
【特許文献５】米国特許第６，４５６，５２８号
【特許文献６】米国特許第５，７９８，９６８号
【特許文献７】米国特許第５，８９０，１９２号
【特許文献８】国際公開特許出願第０２／０５８０７４号
【特許文献９】米国特許出願第１０／７５０，１５５号
【特許文献１０】米国特許出願第１０／７４９，８３１号
【発明の開示】
【００１３】
概括的に言えば、本発明は、（フラッシュメモリなどの）不揮発性メモリシステムにおいてデータ管理を行うための技法に関する。本発明の１つの態様によれば、コントローラはホストのファイルシステムに関する情報を利用することが可能となり、この情報は、ホストによって不揮発性メモリに格納されて、１以上のクラスタ（または１以上のクラスタ内の１以上のセクタ）が現在割り当てられているかどうかの判定が行われることになる。理解されるように、コントローラを用いて、ホストのファイルシステムに関する情報を利用して、特に、１以上のクラスタ（または１以上のセクタ）が、例えば、ガーベッジコレクションサイクル中にメモリ内の１つの記憶位置から別の記憶位置へコピーされないようにすることを保証することが可能となる。この結果、従来行われた（データのコピーなどの）いくつかの不必要な処理の回避が可能となり、システム性能が改善されることになる。
【００１４】
コントローラは、以前に割り当てられた１以上のクラスタが割当てを解除されたかどうかの判定を行うために、ホストがファイルアロケーションテーブル（ＦＡＴ）に正常に書き込んだ情報を直接利用することが可能であることも理解できる。前述したのとは別に、コントローラは、ルートディレクトリ、サブディレクトリ並びにファイルアロケーションテーブル（ＦＡＴ）に書き込まれた情報を利用して、例えば、データアロケーションテーブル（ＤＡＴ）内のクラスタアロケーションに関するコントローラ自身の情報の生成および／または保守管理を行うことも可能である。しかし、本発明を実現して、ファイルアロケーションテーブル（ＦＡＴ）に正常に格納された情報の利用が可能となることは明らかである。したがって、コントローラがコントローラ自身の情報の保守管理を行ったり、（データアロケーションテーブルなどの）何らかの追加のデータ構造を生成したりすることは不要となる。しかし、以下説明するように、データアロケーションテーブル（ＤＡＴ）の保守管理を行うことによって、ファイルアロケーションテーブル（ＦＡＴ）から得られる情報に単に依拠するよりも多くの利益を得ることが可能となる。したがって、例えばデータアロケーションテーブル（ＤＡＴ）として実現できるデータ属性格納部（ＤＡＳ）についてさらに説明することにする。
【００１５】
一般に、データ属性格納部（ＤＡＳ）には、コントローラが不揮発性メモリの中で保守管理を行う１以上のデータ属性が含まれる。データ属性は、（割当て状態や割当て解除状態、サイズ、優先順位などの）データに関する有益情報を提供することができる。したがって、データ属性格納部（ＤＡＳ）を用いてさらにインテリジェントにデータ管理を行うことが可能となる。本発明の別の態様は、データ属性格納部（ＤＡＳ）を用いてデータの管理を行うための技法に関する。
【００１６】
１つの実施形態では、データ属性格納部（ＤＡＳ）は割当て格納部（ＡＳ）として実現される。割当て格納部（ＡＳ）は、例えばテーブル、すなわち個々のデータクラスタ（ホストの論理単位）の割当て状態を示すデータアロケーションテーブル（ＤＡＴ）として実現することができる。クラスタとは、論理的にデータを構成するためにホストが用いる論理単位を表わすものである。より良好なメモリ管理を達成するために、不揮発性メモリシステムのコントローラはデータアロケーションテーブル（ＤＡＴ）にアクセスを行うことができる。したがって、データアロケーションテーブル（ＤＡＴ）は、ホストが利用する論理構成とコントローラとの間の橋渡しを効果的に行うものである。こうすることによって、コントローラはホストの論理構成を効果的に理解することが可能となる。さらに、コントローラはホストの活動をモニタして、例えば、ホストがクラスタの割当てを解除されたかどうかの判定を行う。例えば、ＤＯＳ対応システムのルートディレクトリ、ファイルアロケーションテーブル（ＦＡＴ）およびサブディレクトリをモニタして、ホストによってデータのクラスタの割当て解除の検知を図ることが可能となる。例えば、ファイルまたはファイルの一部がホストによって削除された結果として、ルートディレクトリ、ファイルアロケーションテーブル（ＦＡＴ）あるいはサブディレクトリの変更が生じる場合がある。いずれの場合にも、１以上のデータクラスタの割当て解除が検知されると、コントローラはデータアロケーションテーブル（ＤＡＴ）を更新する。この結果、データアロケーションテーブル（ＤＡＴ）はデータに関する更新情報を提供できることになる。さらにインテリジェントなデータ管理のためにこの情報の利用が可能となる。例えば、ガーベッジコレクション中にデータのコピーを行うべきかどうかを判定するために割当て解除状態を利用することができる。割当てが解除されたデータのコピーは行う必要がない。この結果、従来方式で行われるいくつかの不必要な処理を回避することが可能となり、システム性能を改善することが可能となる。
【００１７】
別の実施形態では、ホストによってＦＡＴまたはＤＡＳに格納された情報を利用して、ホストが送信したデータの一部をどのように格納するのが望ましいかを決定することができる。どこか別の場所からデータをコピーすることによって、非シーケンシャルに受信したデータを非シーケンシャルに格納したり、シーケンシャルに格納したりして、何らかのギャップを受信したデータに充填するように図ることも可能である。このようなシーケンシャルな格納が利点を有する場合として、ホストが、利用可能な（未使用のあるいは割当てを解除された）（クラスタなどの）論理アドレス空間の一部へ書き込みを行う場合がある。データのこのような書き込みは、ホストが新しいデータを格納していることを示すものであり、非シーケンシャルにデータを格納する何らかの理由を示すものではない。ホストが送信するデータセクタの論理アドレスを未使用クラスタの論理アドレス範囲と比較することによって、コントローラは、ホストが次の未使用クラスタに対して書き込みを行っているかどうかを判定することが可能となる。この判定に基づいて、コントローラはセクタ用の格納方式を選択することも可能である。
【００１８】
１つの実施形態では、ホストが次の未使用クラスタへの書き込みを行っていることがホストから受信した単複のセクタによって示されているかどうかに関して判定が行われる。ホストが次の未使用クラスタへの書き込みを行っていれば、メモリアレイ内のどこか別の場所からコピーされたデータによって、データ内のいずれのギャップも満たされた状態で、データはシーケンシャルな形でブロックに書き込まれていることになる。ホストが次の未使用クラスタへの書き込みを行っていなければ、データをシーケンシャルにあるいは非シーケンシャルに格納すべきかどうかを判定するために追加の基準を考慮してもよい。例えば、セクタ間の論理アドレス内でジャンプしてホストからセクタを受信する場合、ジャンプのサイズによって格納方式を決定することができる。ジャンプが小さなものであれば、結果として生じるギャップはコピーされたデータで満たすことも可能であり、さらに、シーケンシャルなフォーマットで更新済みデータを保持するようにしてもよい。更新ブロックがシーケンシャルで、かつ、満たされるように近接している別の例では、更新ブロックをデータで満たして、非シーケンシャルに受信したセクタに書き込みを行うのではなく、更新ブロックをシーケンシャルに保つようにすることも可能である。不揮発性メモリ内のＦＡＴのコピーから直接取得した情報に基づいて格納方式を選択したり、ＤＡＳ内の、または、ＦＡＴから導き出された類似の構造内の情報に基づいて格納方式を選択したりすることも可能である。
【００１９】
方法、システム、デバイス、装置あるいはコンピュータ可読媒体として含まれる本発明は多くの態様で実現することが可能である。本発明の他の態様並びに利点は、本発明の原理を例示する添付図面と関連して行う以下の詳細な説明から明らかになる。
【発明を実施するための最良の形態】
【００２０】
同じ参照番号によって類似の要素が参照される添付図面を例示として本発明を示すが、これは本発明を限定するものではない。
【００２１】
本発明は、（フラッシュメモリなどの）不揮発性メモリシステムにおいてデータを管理するための技法に関する。本発明の１つの態様によれば、コントローラはホストのファイルシステムに関する情報を利用することが可能であり、この情報は、１以上のクラスタ（１以上のクラスタ内の１以上のセクタ）が現在割り当てられているかどうかを判定するために、ホストによって不揮発性メモリに格納されたものである。理解されるように、コントローラは、ホストのファイルシステムに関する情報を利用して、特に、例えば、ガーベッジコレクションサイクル中などに１以上のクラスタ（またはクラスタ内の１以上のセクタ）が、メモリ内の１つの記憶位置から別の記憶位置へコピーされないことを保証することができる。この結果、従来方式で行われる（データをコピーするなどの）いくつかの不必要な処理を回避することが可能となり、システム性能を改善することが可能となる。
【００２２】
１以上の予め割り当てられたクラスタが割当てを解除されたかどうかを判定するために、ファイルアロケーションテーブル（ＦＡＴ）にホストが正常に書き込んだ情報をコントローラが直接利用できることも理解できる。前述したのとは別に、コントローラは、ルートディレクトリ、サブディレクトリおよびファイルアロケーションテーブル（ＦＡＴ）に書き込まれた情報を利用して、例えば、データアロケーションテーブル（ＤＡＴ）の中でファイルアロケーションテーブル（ＦＡＴ）自身のクラスタアロケーションに関する情報の生成および／または保守管理を行うようにすることが可能となる。しかし、本発明を実現して、ファイルアロケーションテーブル（ＦＡＴ）に正常に格納された情報を利用できることは明らかである。したがって、コントローラがコントローラ自身の情報の保守管理を行ったり、（データアロケーションテーブル（ＤＡＴ）などの）何らかの追加のデータ構造を生成したりすることは不要となる。しかし、以下説明するように、データアロケーションテーブル（ＤＡＴ）の保守管理を行うほうが、ファイルアロケーションテーブル（ＦＡＴ）から得られる情報に単に依拠する場合よりも多くの利点を提供できることになる。したがって、例えばデータアロケーションテーブル（ＤＡＴ）として実装できるデータ属性格納部（ＤＡＳ）についてもさらに例示によって説明することにする。
【００２３】
一般に、１以上のデータ属性を含むデータ属性格納部（ＤＡＳ）の保守管理はコントローラによって不揮発性メモリの中で行うことが可能である。データ属性は、（割当て状態や割当て解除状態、サイズ、優先順位などの）データに関する有益情報を提供することができる。したがって、データ属性格納部（ＤＡＳ）を用いてさらにインテリジェントにデータ管理を行うことが可能となる。本発明の別の態様は、データ属性格納部（ＤＡＳ）を利用するデータ管理のための技法に関する。
【００２４】
１つの実施形態では、データ属性格納部（ＤＡＳ）は割当て格納部（ＡＳ）として実装される。割当て格納部（ＡＳ）は、例えば、テーブルとしてあるいはデータの個々のクラスタ（ホストの論理単位）の割当て状態を示すデータアロケーションテーブル（ＤＡＴ）として実装することができる。クラスタとは、ホストがデータを論理的に構成するために使用する論理単位を表わすものである。より好適なメモリ管理を行うために、不揮発性メモリシステムのコントローラはデータアロケーションテーブル（ＤＡＴ）にアクセスすることができる。したがって、データアロケーションテーブル（ＤＡＴ）は、ホストが利用する論理構成と、コントローラとの間での橋渡しを効果的に行うことになる。こうすることによって、コントローラはホストの論理構成を効果的に理解できることになる。さらに、コントローラはホストの活動をモニタして、例えば、ホストがクラスタの割当てを解除したかどうかの判定を行う。例えば、ルートディレクトリ、ファイルアロケーションテーブル（ＦＡＴ）およびＤＯＳ対応システムのサブディレクトリをモニタして、データのクラスタの割当て解除をホストが検知するように図ることも可能である。例えば、ファイルまたはファイルの一部がホストにより削除された結果として、ルートディレクトリ、ファイルアロケーションテーブル（ＦＡＴ）あるいはサブディレクトリの変更が生じる場合がある。いずれの場合にも、データの１以上のクラスタの割当て解除が検知されると、コントローラはデータアロケーションテーブル（ＤＡＴ）の更新を行うことになる。この結果、データアロケーションテーブル（ＤＡＴ）はデータに関する更新された情報を提供できることになる。この情報を利用して、さらにインテリジェントなデータ管理が行われることになる。例えば、割当て解除状態を利用して、ガーベッジコレクション中にデータをコピーすべきかどうかを判定することができる。割当てを解除されたデータのコピーを行う必要はない。その結果、従来方式で行われるいくつかの不必要な処理を回避することが可能となり、システム性能を改善することが可能となる。
【００２５】
図２Ａ〜図８を参照しながら以下本発明の実施形態について論ずることにする。しかし、当業者であれば容易に理解できるように、これらの図面によって本願明細書で行う以下の詳細な説明は、あくまで説明のためのものであって、本発明はこれらの限定された実施形態の範囲を越えて拡大するものである。例えば、この説明はフラッシュメモリに言及するものではあるが、別の種類の不揮発性メモリを使用することも可能である。別の種類の不揮発性メモリとしては、磁気抵抗ＲＡＭ（ＭＲＡＭ）、強誘電体ＲＡＭ、および（オボニクス単一化メモリ (Ovonics Unified Memory) すなわちＯＵＭとしても公知の）相変化メモリが含まれる。
【００２６】
前述したように、コントローラはホストのファイルシステムに関する情報を利用することが可能であり、この情報はホストよって不揮発性メモリに格納され、１以上のクラスタ（またはクラスタ内のセクタ）が現在割り当てられているかどうかの判定が本発明の１つの態様に従って行われる。コントローラは、ホストのファイルシステムに関する情報を利用して、特に、ガーベッジコレクションサイクル中にメモリ内の１つの記憶位置から別の記憶位置へ１以上のクラスタ（またはクラスタ内のセクタ）がコピーされないようにすることを保証することができる。例示によってさらに説明すると、本発明の１つの態様に基づくコピー管理方法（２５０）が図２Ａに描かれている。最初に、ホストは、不揮発性メモリデバイスを使用して、ファイルシステムが利用する情報を格納する（２５２）。次に、コントローラは、ホストが格納した情報を利用して（２５２）、１以上のクラスタ（または１以上のクラスタ内の１以上のセクタ）が何らかの有効なファイルに現在割り当てられているかどうかの判定を行う（２５４）。当業者であれば解るように、１以上のクラスタ（または１以上のクラスタ内の１以上のセクタ）が、何らかの有効なファイルに現在割り当てられているかどうかを判定する（２５４）ために、ファイルアロケーションテーブル（ＦＡＴ）にホストが正常に書き込んだ情報をコントローラは直接利用することができる。これとは別に、コントローラは、ホストによってデバイスへ書き込まれた一続きの論理セクタと一緒に、ルートディレクトリ、サブディレクトリおよびＦＡＴ内の書き込まれた情報を利用して、クラスタアロケーションに関するコントローラ自身の情報を生成し、この情報の保守管理を行うことを意図することも可能である。例えば、コントローラは、コントローラ自身のデータアロケーションテーブル（ＤＡＴ）の生成および／または保守管理を行うことが可能である。いずれの場合にも、コントローラは、現在割り当てられていないと判定された（２５４）任意のクラスタ（またはクラスタ内のセクタ）が、メモリ内でのガーベッジコレクション処理中に１つの記憶位置から別の記憶位置へコピーされないことを保証する（２５６）。言い換えれば、クラスタ（またはクラスタ内のセクタ）が現在割り当てられていると判定された場合には（２５４）、このクラスタ（またはクラスタ内のセクタ）は単にコピーされることになる。コピー管理方法（２５０）は後続の処理を終了させる（２５６）。
【００２７】
前述したように、データアロケーションテーブル（ＤＡＴ）の保守管理を行うステップは、単にファイルアロケーションテーブル（ＦＡＴ）から得られる情報に依拠する以外のさらに多くの利点を提供することができる。当業者には明らかなように、ＦＡＴは、クラスタが割当て解除されたことを必ずしも示すというわけではない場合がある。例えば、クラスタエントリのチェーンが、ディレクトリ内のいずれのファイル参照符号ともリンクされることなくＦＡＴの中に存在する場合がある。
【００２８】
ファイルが削除されると、ファイルのディレクトリエントリはホスト内のファイルシステムにより修正されて（ファイル名の第１の文字が０ｘＥ５へ変更される）、ファイルが削除されたことが示される。しかし、ＦＡＴ内のクラスタエントリは、あたかもクラスタエントリがまだファイルに割り当てられているかのような状態にこのクラスタエントリの連鎖情報を保持することも可能である。クラスタを再使用するための、および、未使用を示す“０ｘ００００”へＦＡＴクラスタエントリを更新するためのアルゴリズムとして、典型的には、ホストにおいて特定のファイルシステムを実現する機能がある。ＤＡＴは、ディレクトリ情報またはサブディレクトリ情報の変更を利用して、クラスタ属性が、ホストファイルシステムに依拠することなく、クラスタの現在の割当て状態をファイルに反映することを可能にすることができる。環境によっては、ＤＡＴの実施構成のほうが、単にＦＡＴに依拠するよりも安全である場合さえある。クラスタの割当て状態を確かめるために単にＦＡＴを利用する場合、ホストがファイルの終了時にＦＡＴを更新するまで、メモリシステムが、ファイルへのクラスタの割当てについて認知していない場合もある。したがって、すでに書き込まれているファイルの一部をＦＡＴに書き込みを行う以前にホストが修正を行う場合、まだ割当てを解除された状態を有するいくつかの有効なデータがコントローラによって破棄される場合もある。ＤＡＴの実施構成はこの問題点を効果的に処理することができる。
【００２９】
さらに、本発明の原理に従って提供されるデータアロケーションテーブル（ＤＡＴ）は、ＦＡＴが通常提供していない特徴も提供することができる。例えば、ＦＡＴはクラスタ用の単一の割当て状態を定義するものである。これに対して、例えば、１つのセクタあるいは１グループのセクタに対する割当て状態の分析をクラスタ内で可能にすることによって、マルチビット状態の保存を許可できるようにＤＡＴを実装することが可能である。こうすることによって、コントローラは、第１のファイルの最後のクラスタのみが部分的に使用されるファイル間で、割り当てられていないセクタのコピーを避けることが可能となる。ＤＡＴが提供できる利点および追加の特徴を示しながら、以下説明する実施形態では、（ＤＡＴなどの）データ属性格納部（ＤＡＳ）においてコントローラ自身の情報の保守管理を行うコントローラをさらに例示する。しかし、本発明の範囲と精神から逸脱することなく、コントローラが、単にＦＡＴに依拠して、ホストが使用する種々のファイルと関連づけられた割当て状態を判断できることは明らかである。
【００３０】
図２Ｂは、本発明の１つの実施形態に従う計算環境２００を描く図である。この計算環境２００では、フラッシュメモリコントローラ２０２はホストアプリケーション２０４の（フラッシュメモリ２０６などの）不揮発性メモリへのアクセスを可能にする。言い換えれば、ホストアプリケーション２０４は、フラッシュメモリ２０６へのインターフェイスとしてフラッシュメモリコントローラ２０２を利用する。したがって、ホストアプリケーション２０４は、フラッシュメモリコントローラ２０２が（書き込み、読み出しなどの）種々のアクセス処理をフラッシュメモリ２０６上で実行するように要求することができる。ホストアプリケーション２０４はデータのアドレス指定を行うために論理アドレス空間を利用することができる。フラッシュメモリコントローラは、ホストの論理アドレス空間を対応づけて、コントローラの論理アドレス空間の中へ入れ、ホストの論理アドレス空間はフラッシュメモリ２０６上の物理アドレス空間に順に対応づけられる。
【００３１】
さらに、フラッシュメモリはデータ属性格納部（ＤＡＳ）２０８の構築と保守管理とを行うことができる。ＤＡＳ２０８には、フラッシュメモリ２０６に格納されたデータと関連づけられた種々の属性に関する情報が含まれる。例えば、データ属性格納部（ＤＡＳ）２０８に格納されたデータ属性はデータの割当て状態、割り当てられたデータのサイズ、優先順位を含むものであってもよい。一般に、データ属性格納部（ＤＡＳ）２０８は、任意の望ましいデータ属性を格納でき、また１以上のビットの情報を有する属性を表わすこともできる。フラッシュメモリコントローラ２０４は、ホストアプリケーション２０４の活動をモニタするデータ属性モニタ部２０８を設けるものであることに留意されたい。データ属性モニタ部２０８は、フラッシュメモリ２０６に格納されたデータに関してホストアプリケーション２０４の活動を解釈することができる。このことは、データ属性モニタ部２０８がどこでデータ属性を変更すべきかを判断し、ＤＡＳ２０８の中でデータ属性を適宜更新できることを意味する。
【００３２】
例示によってさらに説明すると、図３Ａは本発明の１つの実施形態に従ってデータ属性格納部（ＤＡＳ）２０８を描く図である。この実施形態では、データ属性２０８はデータアロケーションテーブル（ＤＡＴ）３０８として実現される。したがって、ＤＡＴ３０８は不揮発性メモリシステムの種々のデータ部分の割当て状態／割当て解除状態に関する情報を提供する。理解されるように、これら種々のデータ部分は論理データ構成、すなわち、ホストアプリケーション２０４によって利用される論理データ構成に従って構成することができる。前述したように、ホストアプリケーションはデータを構成して、クラスタと呼ぶことができるホスト論理単位に変えることも可能である。ＤＡＴ３０８はこれらのクラスタを表わす単位に分割することができる。
【００３３】
このことは、ホストアプリケーションが利用する論理クラスタの各々をＤＡＴ３０８の中でエントリとして表わすことができることを意味する。例えば、クラスタ１は、第１のエントリによって、クラスタ１０は第１０のエントリによって表わすことができる等々となる。さらに、ＤＡＴ３０８の個々のエントリはクラスタの割当て状態／割当て解除状態を示すことができる。例えば、１ビットを用いて論理クラスタが現在割り当てられているか、あるいは割当てが解除されているかをＤＡＴ３０８の個々のエントリが示すようにすることができる。数ビットを用いて、属性に関するさらに多くの情報および／またはいくつかの属性に関する情報を示すことができることに留意されたい。いずれの場合にも、ＤＡＴ３０８によってデータのより良好な管理ができることになる。例えば、データ部分の割当て状態／割当て解除状態に基づいて、フラッシュメモリコントローラは、ホストアプリケーションにより割当てが解除されたデータのコピーを避けるようにすることも可能である。
【００３４】
さらに例示によって説明すると、図３Ｂは、本発明の１つの実施形態に従うＤＡＴ２０８のエントリ３０２を描く図である。テーブルエントリ３０２は４ビットを含み、その場合、第１のビット（ビット０）は割当て状態／割当て解除状態を示すことができ、３つの他のビットはまとめて、どのくらいの量のデータが割り当てられているか（半分を示す“１００”および満杯を示す“１１１”など）を示すことができる。同様に、さらに多くのビットを利用してクラスタの別の属性に関する情報を示すことができる。例えば、４ビットによって個々のクラスタを表わすことが可能であり、その場合１ビットは割当て解除状態を表わし、３ビットは、クラスタのどのような部分が割当てを解除されているかを示すことになる。当業者には明らかなように、多数の他の方法でクラスタ用の多ビットを定義することも可能である。例えば、極性（または順序）を尊重してもよいし、あるいは（６、８、１２などの）より多くのビットを使用してもよい。前述したのとは別に、“サブクラスタ”のセクタ番号を示すために、完全に割当てを解除されたすべてのビットを割り当てることが可能であり、完全に割り当てられたクラスタを例えばマークしてすべてのビットをゼロにセットすることも可能である。
【００３５】
前述したように、データ属性モニタ部２１０はホストアプリケーション２０４の活動をモニタするものである。このモニタに基づいて、データ属性モニタ部２５９はデータ属性格納部（ＤＡＳ）２０８を更新することができる。図２に示されているように、ホストアプリケーション２０４の活動を解釈するために、データ属性モニタ部２１０は、ホストが理解し、使用するデータの論理構成を実現する必要がある。例示によってさらに説明すると、図３Ｃは、ホストの論理データ構成を描く図であり、この論理データ構成は本発明の１つの実施形態に従うコントローラによって利用することができる。図３Ｃに示されているように、ホストは、論理アドレス空間を分割して、システム３１０とユーザ空間３１２にすることができる。システムデータ３１０は、ファイルアロケーションテーブル（ＦＡＴ１）と、ＦＡＴ２（ＦＡＴ１のコピー）と、ルートディレクトリ情報とを含むことが可能であり、これらすべてをシステムデータ３１０として格納してもよい。ユーザ空間はサブディレクトリに関する情報を含むことも可能である。データ属性モニタ部２１０は、ホストアプリケーション２０２が割当てを解除した（例えば、ファイルを除去したり、ファイルを短くしたりした）かどうかを判定するために、ＦＡＴ１、ＦＡＴ２、ルートディレクトリおよびサブディレクトリをモニタすることも可能である。データのモニタについても図６を参照しながら以下で説明する。
【００３６】
しかし、次に図４を参照しながら、フラッシュメモリに格納されたデータに関する情報をフラッシュメモリコントローラに提供する方法４００が本発明の１つの実施形態に従って描かれている。データに関する情報は、フラッシュメモリコントローラによって利用され、例えば、（ガーベッジコレクションなどの）データの保守管理中にデータについての決定を通知することが可能となる。方法４００は、例えば、図２のフラッシュメモリコントローラ２０２によって利用することができる。
【００３７】
最初に、フラッシュメモリ記憶装置のコントローラ用のデータ属性格納部（ＤＡＳ）が生成される（４０２）。データ属性格納部（ＤＡＳ）は、フラッシュメモリ記憶装置内の複数のデータ部分の各々に対して１以上の属性を提供する。データにアクセスするためにコントローラを使用するホストの活動がモニタされる（４０４）。次に、モニタ（４０４）に基づいて、フラッシュメモリ記憶装置のデータ部分に関連する属性を更新すべきかどうかが判定される（４０６）。したがって、フラッシュメモリ記憶装置の少なくとも１つのデータ部分に対する更新を行うべきであると判定された（４０６）場合、少なくとも１つのデータ部分に関連する少なくとも１つの属性が更新される（４０８）。更新（４０８）後、ホストの活動はモニタされる（４０４）。その後、方法（４００）は、データのモニタがそれ以上所望されなくなったり、必要とされなくなったりするまで、前述したのと同様に進行することができる。
【００３８】
前述したように、データ属性格納部（ＤＡＳ）を設け、フラッシュメモリコントローラによってこのデータ属性格納部を利用して、（ガーベッジコレクションなどの）保守管理処理を実施することができる。図５は、本発明の１つの実施形態に従うフラッシュメモリの保守管理方法（５００）を描く図である。最初に、フラッシュメモリ記憶装置に格納されたデータの一部に対してフラッシュメモリコントローラが保守管理処理を実施する必要があるかどうかの判定が行われる（５０２）。コントローラが保守管理処理を実施する必要がある旨が判定された（５０２）場合、データ属性格納部（ＤＡＳ）のどのような部分が、保守管理の対象となるデータ部分に関する情報を提供するかが判定される（５０４）。したがって、データ部分に関連する少なくとも１つの属性がデータ属性格納部（ＤＡＳ）から読み出される（５０６）。最後に、少なくとも１つのデータ属性に基づいて処理が実行される（５０８）。少なくとも１つのデータ属性により提供された情報に基づいて、保守管理処理をさらにインテリジェントに実行することができると理解すべきである。
【００３９】
図６は、本発明の１つの実施形態に従うモニタ方法６００を描く図である。モニタ方法（６００）は、図４に例示されているモニタ処理と更新処理（すなわち、図４の処理４０４、４０６、４０８）中に行うことができるいくつかの処理例を描く図である。モニタ方法６００はフラッシュメモリコントローラによって実行することができる。最初に、書き込み処理を求める要求が受信されたかどうかが判定される（６０２）。次に、書き込み処理が指定アドレス空間のアドレス指定を行うかどうかが判定される。例えば、この指定アドレス空間には、ＤＯＳ環境の中で動作するホストがアドレス指定を行う論理アドレス空間のＦＡＴ１、ＦＡＴ２、ルートディレクトリおよびサブディレクトリを含むことができる。ルートディレクトリ内のおよび別のサブディレクトリ内の情報からサブディレクトリ用の指定アドレス空間を決定することも可能である。一般に、指定アドレス空間とは、データが（例えば、ファイルのディレクトリの除去や修正、ファイルの編集などの）割当てを解除された処理であることをホスト活動が示すことができるアドレス空間を表わすものである。いずれの場合にも、書き込み処理が指定アドレス空間に対するものであると処理６０４時に判定された場合、指定アドレス空間に現在格納されているデータが読み出される（６０６）。次に、書き込み処理が実行される（６０８）。書き込み処理が実行された（６０８）後、以前に読み出された（６０６）古いデータは、書き込まれた（６０８）データと比較される（６１０）。したがって、データの変更が存在するかどうかが判定される（６１２）。データの変更が存在しないと判定された場合（６１２）、書き込み処理要求が受信されたかどうかが判定される（６０２）。
【００４０】
前述したのとは別に、更新済みデータが古いデータから別の記憶位置に書き込まれるフラッシュメモリシステムにおいて、前回の読み出しを行う（６０６）ことなく、古い記憶位置と新しい記憶位置とに位置するデータ間で直接の比較（６１０）を行うことが可能となる。
【００４１】
しかし、データに対する変更が検知されたと判定された（６１２）場合、この変更は解釈されて（６１４）、１以上のクラスタが割当てを解除されたかどうかの判定が行われる（６１６）ことになる。クラスタが割当てを解除されていないと判定された場合、書き込み処理要求が受信されたかどうかが判定される（６０２）。しかし、１以上のクラスタが割当てを解除されたと判定された（６１６）場合には、データアロケーションテーブル（ＤＡＴ）内での１以上のクラスタの状態が変更されて、“割当て解除済み”状態を示すようになることに留意されたい。したがって、指定アドレス空間内のデータの変更がデータの割当て解除を結果として生じたと知覚される（６１６）と、モニタ方法６００によってデータアロケーションテーブル（ＤＡＴ）の効果的な更新が行われる（６１８）。
【００４２】
一方、書き込み処理が指定アドレス空間に対するものではないと判定された（６０４）場合、書き込み処理が実行される（６２０）。さらに、書き込まれたクラスタが特定され（６２２）、その結果、１以上の特定したクラスタの状態を“割当て済み”にセットできる。理解されるように、この処理は、無指定のアドレス空間において書き込み処理を実行したとき、特定されたクラスタを表わすＤＡＴのエントリが“割当て済み”にセットされることを保証するものである。ＤＡＴ内で表わされるクラスタの状態を“割当て済み”にセットした（６２４）後、書き込み処理要求が受信されたかどうかの判定を行う（６０２）ことができる。
【００４３】
前述したように、データ属性格納部（ＤＡＳ）を例えば利用して、保守管理処理を実施することができる。例示によってさらに説明すると、図７は、本発明の１つの実施形態に従うガーベッジコレクション方法７００の例を描く図である。理解されるように、ガーベッジコレクション方法７００は、データアロケーションテーブル（ＤＡＴ）を利用して、更新処理中にブロックのより良好な更新を可能にするものである。最初に、更新ブロックを閉じるべきかどうかが初めに判定される（７０２）と、更新ブロックのすべてのセクタが書き込まれたかどうかの判定が行われる。更新ブロックのすべての論理セクタが書き込まれた場合、原ブロックが更新ブロックにより効果的に置き換えられることになる。したがって、更新ブロックが原ブロックとしてマークされ（７０６）、前の原ブロックは消去され（７０８）、その結果、この原ブロックは後で使用できることになる。
【００４４】
一方、更新ブロックのすべてのセクタが書き込まれなかったと判定された（７０２）場合、書き込まれなかったセクタに対応する論理セクタが特定される（７１０）。次いで、特定された論理セクタ（７１０）がクラスタへ対応づけられる（７１２）。クラスタはデータアロケーションテーブル（ＤＡＴ）の中でチェックされる（７１４）。したがって、特定されたクラスタのすべて（７１０）が割当てを解除されたことをＤＡＴが示すかどうかが判定される（７１６）。すべてのクラスタの割当て解除が行われたことがＤＡＴによって示された場合、更新ブロックは原ブロックとしてマークされ（７０６）、古いブロックは消去される（７０８）。
【００４５】
すべてのクラスタが割当てを解除されたことがＤＡＴによって示される（７１６）と、１以上のクラスタがコピーされなくなることに留意すべきである。１以上のクラスタがまだ割り当てられていることがＤＡＴテーブルによって示された場合にのみ、割り当てられた状態のままになっているデータは更新ブロックへコピーされる（７１８）。いずれの場合にも、更新ブロックをすぐに閉じたり、更新ブロックがいっぱいになったとき、後で閉じたりすることができることに留意すべきである。更新ブロックにマークをつけ（７０６）、前の原ブロック（古いブロック）を消去すること（７０８）はできるが、割り当てられていないデータの不必要なコピーは避けられることになる。ガーベッジコレクション方法（７００）は消去（７０８）の後終了する。
【００４６】
理解されるように、本発明の１つの実施形態に従って、フラッシュメモリを用いてデータ属性格納部（ＤＡＳ）を実現することができる。例示によってさらに説明すると、図８は本発明の１つの実施形態に従うデータアロケーションテーブル（ＤＡＴ）８００を描く図である。メモリ部分８０１を利用してデータアロケーションテーブル（ＤＡＴ）８００が実現される。メモリ部分８０１は単位として消去可能なブロックであってもよい。メモリ部分８０１はデータアロケーションテーブル（ＤＡＴ）８００を表わすのに必要とされるメモリよりも大きくなる。個々のセクションは１以上のページに配置されるものであってもよく、その場合ページはプログラミングメモリの最小単位となる。
【００４７】
図８に示されているように、データ属性格納部（ＤＡＳ）８００は、複数のセクション、すなわち、当初メモリ部分８０１の冒頭に書き込まれる原セクションＤＡＳ１（８０２）、ＤＡＳ２（８０４）、ＤＡＳ３（８０６）、ＤＡＳ４（８０８）に分割してもよい。これら原セクションの各々は、論理的にデータを構成するためにホストが使用する複数のクラスタを表わすことができる。クラスタと関連づけられたデータ属性の更新を行う必要があるとき、データ属性格納部（ＤＡＳ）８００の適当な原セクション用の更新セクションに書き込みを行うことによって、データ属性格納部（ＤＡＳ）８００の対応するセクションを更新することができる。この更新セクションは最後の原セクションすなわちＤＡＳ４（８０８）の後に書き込まれる。例えば、原ＤＡＳ３（８０６）は新たなセクション８１６に書き込みを行うことによって更新される。同様に、原ＤＡＳ１（８０２）を更新する必要があるとき、新たなセクション８１２に書き込みを行うことができる。原ＤＡＳ４（８１８）を表わすなどのために新たなセクション８１８の書き込みが行われる。
【００４８】
さらに、インデックス方式を用いてデータアロケーションテーブル（ＤＡＴ）８００の保守管理を行うことができる。図８に示されているように、メモリの個々のセクションにはインデックス部分（Ｉｉ−Ｕ）が含まれる。最後のエントリ（８０６）のこのインデックス部分はデータ属性格納部（ＤＡＳ）８００の最新のセクションを参照する。このことは、インデックス８２０、８３０、８４０、８５０がそれぞれデータ属性格納部（ＤＡＳ）８００の第１、第２、第３および第４の最新のセクション（ＤＡＳ１、ＤＡＳ２、ＤＡＳ３、ＤＡＳ４）を指すことを意味する。例えば、メモリ部分８０１がほぼいっぱいになったとき、原セクション（ＤＡＳ１、ＤＡＳ２、ＤＡＳ３、ＤＡＳ４）として最新のセクションが再生されるように、メモリ部分８０１のガーベッジコレクションを行うことができる。
【００４９】
データ属性格納部（ＤＡＳ）の利用が任意の利用となるように本発明を実施することができることも留意すべきである。例えば、データ属性格納部（ＤＡＳ）の利用は、ホストの実際のデータ論理構成が（ＤＯＳなどの）特定の動作環境用として予想されるデータ構成に従うことを保証するように、検証プロセスが決定するシステムコンプライアンスに依存するようにすることも可能である。前述したのとは別に、ホストによるコマンドの送信によってデータ属性格納部（ＤＡＳ）の利用を可能にして、データ属性格納部（ＤＡＳ）が特定の動作環境用のデータ構成に従うものであることを示すようにすることができる。割り当てられたクラスタの割当てが解除されるとすぐに、データアロケーションテーブル（ＤＡＴ）がクラスタ（またはクラスタ内のセクタ）の状態を変更する必要はないことに留意すべきである。言い換えれば、クラスタが割当てを解除されたとき、クラスタがまだ割り当てられていると信じることは、深刻な問題をもたらすものではない。したがって、割当て状態を割当て解除にセットすることが可能となる。理解されるように、異なる時刻に１つずつ行うのではなく、一度にクラスタグループに対する割当てが解除となるように割当て状態をセットすることによって、システム性能をさらに改善することが可能となる。一方、当業者であれば理解できるように、有効な、割当て済みのクラスタ用の状態情報は常に厳密に正確で、かつ、最新のものであることが望ましい（すなわち、割当て済みのクラスタは割り当てられたものとして常にマークを施すことが望ましい）。割当て済みのクラスタに正確にマークを施すことを保証するために、ホストがクラスタへデータを書き込む度に、割当て状態クラスタが割当て済みに自動的にセットされるようにしてもよい。データアロケーションテーブル（ＤＡＴ）内の情報をマッピングテーブル内の情報と同時刻に更新して、論理データブロックへの物理メモリブロックの割当てを定義し、最近書き込まれたセクタあるいはクラスタへ保存するようにしてもよいことも理解できる。
【００５０】
さらに、データ属性格納部（ＤＡＳ）を他の多くの保守管理処理用として利用できることが理解できる。例えば、データ属性格納部（ＤＡＳ）は、ブロックに対応するすべてのクラスタが割当てを解除されたことを示すと、ブロックを消去することができる。この消去は、例えばバックグラウンドとして実行され、性能のさらなる改善が図られることになる。
【００５１】
別の実施形態では、ホストによって不揮発性メモリに格納された情報を利用して、どのようにホストから受信したデータを格納すべきであるかを決定することができる。１つの例では、ホストがＦＡＴに格納した情報とディレクトリとを利用して、シーケンシャルにあるいは非シーケンシャルに（カオス的に）データを格納すべきかどうかの判定を行うことができる。
【００５２】
或る種のメモリシステムでは、データがシーケンシャルであるか非シーケンシャルであるかに応じて、ホストから受信したデータを格納するのに異なる格納方式が利用される。例えば、２００３年１２月３０日出願の“不揮発性メモリおよびブロック管理システムに関する方法”という米国特許出願第１０／７５０，１５５号（特許文献９）は、その全体が本願明細書において参照により援用されているものであるが、この特許出願には、ホストによって非シーケンシャルに送信されるデータを処理する或る技法について記載されている。特に、シーケンシャルな更新をシーケンシャルな更新ブロックに割り当て、その一方で、データを任意の順序に格納できるカオス更新ブロックに非シーケンシャルな更新を割り当てるようにすることができる。カオス更新ブロックへのデータの格納によって、或る種類のデータ更新に利点が生じる一方で、別の種類のデータ更新にとっては非効率を引き起こす原因になる場合もある。この理由のために、米国特許出願第１０／７５０，１５５号（特許文献９）には、所定の基準が満たされたシーケンシャルな方法で、或る非シーケンシャルに受信したデータを格納するための技法ついて記載されている。本発明の実施形態では、非シーケンシャルにデータを受信したとき、不揮発性メモリへデータをシーケンシャルに書き込むか、非シーケンシャルに書き込むかの判定基準は、不揮発性メモリにホストが格納した情報の分析から決定できる。２００３年１２月３０日出願の“大きな消去ブロックを含む不揮発性メモリシステムの管理”という米国特許出願第１０／７４９，８３１号（特許文献１０）には、不揮発性メモリアレイに格納するためにホストが送信するデータの管理のための追加の方法について記載されている。この特許出願は、その全体が本願明細書において参照により援用されている。特に、ホストが非シーケンシャルに更新するデータの管理方法について説明する。所定の判断基準に従うデータに対して様々な指定ブロックを使用することも可能である。
【００５３】
本発明の実施形態では、ＦＡＴ、ルートディレクトリおよびサブディレクトリ（または不揮発性メモリに格納されている同様のホストデータ）と、ホストにより書き込まれている（セクタなどの）データ部分の論理アドレスとを比較したり、ＤＡＳに格納された情報のような引き出された情報と比較したりして、書き込み中のデータ部分が次の未使用クラスタ内に論理アドレスを含んでいるかどうかの判定を行うようにしてもよい。データ部分が次の未使用クラスタ内にアドレスを含んでいれば、それは、ホストが次の利用可能な記憶位置に新しいデータを格納していることを示すことになる。このような格納パターンでは、シーケンシャルにデータを格納し、次いで、非シーケンシャルな順序でデータを格納するのではなく、不揮発性メモリにすでに格納されているデータをコピーし、それから、シーケンシャルに格納されている記憶位置へ後でデータをコピーすることによって、更新ブロック内のいずれかのギャップを満たすことができると好都合な場合がある。
【００５４】
図９Ａは、ＦＡＴテーブル９００の１例を示す。個々のクラスタ０〜８は、ファイル内の次のクラスタを示すＦＡＴテーブル内にエントリを有する。したがって、クラスタ０用のエントリは、このファイル用の次のクラスタがクラスタ１の中にあることを示す“１”になる。クラスタ１内のエントリは“５”であり、次のクラスタがクラスタ５であることを示している。クラスタ５内のエントリは“６”であり、次のクラスタがクラスタ６であることを示している。クラスタ６内のエントリは、“ファイルの最後”すなわちクラスタがそれ以上このファイル用のデータを含まないことを示す“ＥＯＦ”である。別のファイルがクラスタ３と４とに同様に格納される。クラスタ４、７および８は、“未使用”すなわち割当てを行わないように指定する。これは、例えば、ファイルが旧いものになっているホストによる割当て解除の結果である場合もある。ホストによるこの割当て解除は、不揮発性メモリの中でデータが消去されることを必ずしも意味するものではないことに留意すべきである。というのは、ファイルの格納に用いる論理アドレス範囲が新しいデータの格納用として単に利用できるようになるにすぎないからである。旧いデータは、将来の或る時点まで不揮発性メモリに物理的に格納された状態のまま残る場合もある。旧い制御情報を含むクラスタが割当てを解除される可能性もある。やはりホストによって不揮発性メモリの中に格納されたルートディレクトリやサブディレクトリがファイルの第１のクラスタを示す場合もある。
【００５５】
図９Ｂは、ルートディレクトリとサブディレクトリとに含まれる情報と共にＦＡＴ９００から導き出されるＤＡＴ９１０を示す。ＤＡＴ９１０には、クラスタが割り当てられているか、未使用であるかを示す個々のクラスタ用のエントリが含まれる。追加データは、前述したようにＤＡＴ９１０に格納することも可能である。ＤＡＴの保守管理を行って、ＤＡＴに格納された情報が、ＦＡＴおよびディレクトリ内の情報よりも最新の情報となるようにすることもできる。ホストが格納用の新しいデータを送信するとすぐに、更新されたＦＡＴまたはディレクトリ情報がホストによって書き込まれないうちにＤＡＴを更新することも可能である。同様に、ＤＡＳ内の他の情報の保守管理を行って、最新のものにするように図ることも可能である。
【００５６】
図９Ｃは、ＦＡＴ９００の論理アドレス範囲の一部用のセクタとクラスタとの間の対応関係を示す。この例では、１つのクラスタの中に４つのデータセクタが含まれている。異なるセクタ番号を有するクラスタを使用することも可能である。典型的には、クラスタには４〜６４個の間のセクタが含まれる。クラスタ４にはセクタＸ、セクタＸ＋１、セクタＸ＋２およびセクタＸ＋３が含まれている。ホストによる論理アドレス範囲の割当てが一般にクラスタ毎のベースで行われるのに対して、メモリコントローラは一般にセクタ内のデータを処理するものである。一般に、クラスタは単一の単位として割り当てられるが、これは、たとえクラスタの論理アドレス範囲全体がデータの格納用として使用されなかった場合でも、後で行われる別のデータの格納用としてクラスタの論理アドレス範囲全体を使用できないようにするためである。図９Ｃは、割当て済みのクラスタから得られるセクタ５と６とを示し、ホストがデータ格納用としてこれらの論理アドレスを利用できないことを示すために、これらのセクタにはシェードが施されている。
【００５７】
図９Ｄと図９Ｅは、非シーケンシャルにホストから受信したデータの格納を行うための２つの代替方式を示す。双方の図には、不揮発性メモリに格納するためにホストから受信されるセクタＸ〜Ｘ＋３並びにＸ＋１２〜Ｘ＋１５が示されている。これらのセクタは図９Ｃのクラスタ４と７に対応するセクタである。図９Ｄでは、受信したデータがカオス更新ブロック９２０へ書き込まれている。このブロックはカオスブロックである。というのは、セクタＸ＋１２がセクタＸ＋３の直後に書き込まれていて、セクタＸ＋３からセクタＸ＋１２までの論理アドレス範囲でジャンプが生じているからである。カオスブロック９２０は、セクタＸ〜Ｘ＋３を含むとき、シーケンシャルな更新ブロックになることを開始してもよく、さらに、ブロック９２０は、セクタＸ＋１２が格納されているとき、カオス更新ブロックへの変換を開始してもよい。一般に、ホストが非シーケンシャルにデータを送信する場合、カオス（非シーケンシャルな）ブロックが利用される。図９Ｄのカオスブロック９２０内の有効なデータはシーケンシャルなブロック９２２へ最終的に移転され、ブロック９２２において、別の記憶位置からコピーできるセクタＸ＋４〜Ｘ＋１１と共に格納される。これは一般に統合処理の一部として行われる。シーケンシャルなブロックは一般に長期の格納を行うためのものであることが望ましい。というのは、セクタが所定の方法で配列されるため、ブロック内でのセクタのインデックス作成が必要でない場合があるからである。カオスブロック９２０内の全ての有効なデータが別の記憶位置へコピーされた後、カオスブロック９２０は旧いものとしてマークされ、消去が可能となる。
【００５８】
図９Ｅは、セクタＸ〜Ｘ＋３並びにＸ＋１２〜Ｘ＋１５の非シーケンシャルなデータを示し、このデータはシーケンシャルなブロック９３０の中でシーケンシャルに更新される。ブロック９３０がこの時点でシーケンシャルなブロックとなるようにセクタＸ〜Ｘ＋３にまず書き込みを行うことができる。セクタＸ＋１２が受信されると、たとえデータが非シーケンシャルに受信されたものであっても、このデータをシーケンシャルに格納するために判定が行われる。原ブロックから（クラスタ５および６に対応する）セクタＸ＋４〜Ｘ＋１１をコピーして、ホストから受信したセクタ間の論理アドレス範囲を満たすことによってシーケンシャルな格納を行うことが可能となる。セクタＸ＋４〜Ｘ＋１１はパディングセクタと見なすことができる。というのは、これらのセクタを利用して、ホストが送信するセクタ内のギャップの充填すなわち“パッドアウト(pad out) ”が行われるからである。セクタＸ＋４〜Ｘ＋１１は別の記憶位置からコピーされた有効なデータセクタである。このようにして、受信されたセクタは、カオスブロック内の中間の格納段階を通ることなくシーケンシャルなブロック９３０に格納される。したがって、これら２つの技法間の主要な相違点として、セクタＸ〜Ｘ＋３並びにＸ＋１２〜Ｘ＋１５をカオスブロック９２０へ書き込み、次いでカオスブロック９２０を後で消去するステップが図９Ｅの例では不要になるという点が挙げられる。セクタＸ〜Ｘ＋３並びにＸ＋１２〜Ｘ＋１５は一度書き込まれ、セクタＸ＋４〜Ｘ＋１２はこの例ではそのままコピーされる。この処理は、８回の少ない回数のセクタ書き込みと、１回の少ない消去処理とを必要とし、その結果データ格納効率が改善されることになる。
【００５９】
受信したデータをシーケンシャルに格納すべきか、非シーケンシャルに格納すべきかに関する判定は種々の基準に基づいて行うことができる。或る種のデータ、特に、すぐに再更新が行われる可能性の大きいデータの場合、非シーケンシャルな格納のほうが適している場合がある。例えば、制御データや、更新頻度の高いホストデータの一部の場合、カオスブロックに格納するほうが効率が良くなる場合がある。或る種のデータ、特に、データがすぐに再更新される可能性が小さい場合、シーケンシャルな格納のほうが適している場合がある。非シーケンシャルに受信したデータは一般に非シーケンシャルに格納されると考えられるが、場合によっては、シーケンシャルにデータを書き込むと都合がよいこともある。カオスブロックへの中間格納が回避されるため、カオスブロックのガーベッジコレクションを行ってシーケンシャルなフォーマットでデータを取得する必要はない。これによって、図９Ｄに示されている統合処理が回避されることになり、その結果、オーバーヘッドが減り、性能の改善が図られることになる。ホストが次の未使用クラスタへ書き込みを行うとき、これはホストが次の利用可能な記憶位置に単に新しいデータを書き込んでいるという表示であり、一般に、論理アドレス範囲がすぐに再更新されるという表示ではない。したがって、図９Ｅに示されているようなシーケンシャルな更新方式を選択するほうが、図９Ｄに示されているようなカオス的な更新方式を選択するよりも効率のよいものとなる可能性がある。この結果、データが次の未使用クラスタから得られたものであるか否かに従って、使用する格納方式を決定することができる。データが、図９Ｅに示されているような次の未使用クラスタからのものである場合、シーケンシャルな格納部を選択することができる。したがって、図９Ｄの格納方式はこの例ではこのデータ用としては選択されないことになる。
【００６０】
図１０は、本発明の実施形態に従う格納方式の選択を示すフローチャートである。非シーケンシャルなデータがホストから受信されると、データが次の未使用クラスタ１０からのものであるか否かに関する決定がコントローラによって行われる。この決定は、ＦＡＴと、ホストが不揮発性メモリに格納したディレクトリ情報とを直接見ることによって、あるいは、ＤＡＳやＤＡＴに格納されているような情報のようなＦＡＴとディレクトリ情報とから導き出される情報を見ることによって行ってもよい。現在アドレス指定されているクラスタが次の未使用クラスタでなければ、データはデフォルトの方式１２に従って通常の方法で格納される。このことは、データが非シーケンシャルに格納されることを意味する場合がある。あるいは、いくつかの例では、データをシーケンシャルに書き込ませる別の基準が存在する場合もある。現在アドレス指定されているクラスタが次の未使用クラスタであれば、シーケンシャルな書き込みが選択される。この場合、データの有効なクラスタが原メタブロックから現在のシーケンシャルなメタブロック１４へコピーされて、最後に書き込まれたクラスタと現在アドレス指定されているクラスタとの間の論理アドレスのギャップのパッディングが行われることになる。次いで、現在アドレス指定されているクラスタから受信したデータは現在のシーケンシャルなメタブロックへ書き込まれる。この結果、現在のメタブロック１６はシーケンシャルな状態のまま残ることになる。
【００６１】
図１１は、１つの実施形態でホストから受信したセクタのための格納方式の選択を示すフローチャートである。同様の格納方式選択フローチャートが米国特許出願第１０／７５０，１５５号（特許文献９）に示されている。開かれた更新ブロックが存在する（２０）場合、更新ブロックはシーケンシャルなブロックになり（２２）、セクタは更新ブロックの最後のセクタまでシーケンシャルになり（２４）、次いで、セクタは更新ブロックへ書き込まれる（２６）。セクタが更新ブロックの最後のセクタまでシーケンシャルでなければ、シーケンシャルな強制書き込みを行うべきか否かに関する決定が行われる（２７）。更新ブロック内の最後のセクタから受信したセクタへのアドレスジャンプが所定量（ＣB ）よりも大きくなければ（２８）、最後のセクタと受信したセクタとの間のギャップはコピーされたセクタによりパッディングを行って（３０）、前述したようにシーケンシャルなブロックとして更新ブロックの保守管理を行うようにしてもよい。更新ブロック内の空の物理セクタ数が所定量（ＣB ）よりも大きくなければ（３２）、更新ブロックを閉じて（３４）、シーケンシャルなブロックとして更新ブロックの保守管理を行うことも可能であり、さらに、前述したように新たな更新ブロックを割り当てること（３６）も可能である。シーケンシャルな強制書き込みを引き起こす第３の場合として、ホストが次の利用可能なクラスタへの書き込みを行っている（４０）場合がある。このような書き込みが行われているとき、シーケンシャルなブロックとして更新ブロックの保守管理を行うことができるように、不揮発性メモリ内のどこか別の場所からコピーされたセクタによって、受信したセクタと更新ブロック内の最後のセクタとの間のギャップのパッディングを行う（３０）。シーケンシャルな形でデータの書き込みを行うためのこれら基準のいずれも満たされなければ、更新ブロックをカオス更新ブロックへ変換すること（４２）も可能である。したがって、この結果、格納方式を選択する選択基準は、ホストが不揮発性メモリに格納したデータから導き出された属性を含むことが可能となる。
【００６２】
図１２Ａは、更新ブロック５０においてシーケンシャルにデータを格納するメモリシステムによってホストから非シーケンシャルに受信したデータの１例を示す。クラスタ２のセクタＡが受信され、後続してクラスタ７のセクタＢが受信される。セクタＡは、受信されると、更新ブロック５０の第１のセクタとなることが可能であり、更新ブロック５０がセクタＡのみを含む場合、更新ブロック５０はシーケンシャルなブロックと見なされる。これとは別に、図１２Ａに示されているように、更新ブロック５０はシーケンシャルなブロックとすることも可能である。というのは、更新ブロック５０に前回格納されたセクタと共にセクタＡがシーケンシャルに格納されるからである。セクタＢの受信に先行して更新ブロック５０がシーケンシャルであると想定して、セクタＢを受信したとき、シーケンシャルな更新ブロックとして更新ブロック５０の保守管理を行うか、更新ブロック５０（セクタＡ）へ書き込まれた最後のセクタの後にセクタＢを直接格納し、それによってカオスブロックへ更新ブロック５０を変換するかに関する判定が行われる。この例では、クラスタ７はセクタＡに後続する次の未使用クラスタである。したがって、クラスタ７からセクタＢを受信したとき、シーケンシャルな強制書き込みが行われ、セクタが更新ブロック５０へコピーされ、セクタＡとセクタＢとの間のギャップが満たされることになる。この結果、データは、図１２Ａの更新ブロック５０にシーケンシャルに格納されることになる。
【００６３】
図１２Ｂは、更新ブロック５２に非シーケンシャルにデータを格納するメモリシステムによってホストから非シーケンシャルに受信したデータの１例を示す。セクタＡは図１２Ａのようにまず受信される。セクタＡはシーケンシャルに格納され、その結果、更新ブロック５２は、セクタＡがプログラムされるとシーケンシャルなブロックになる。次いで、セクタＸが受信される。セクタＸは次の未使用クラスタへは書き込まれない。セクタＸは割当て済みのクラスタへ書き込まれ、したがってシーケンシャルな強制書き込みを引き起こすものではない。セクタＸは非シーケンシャルに書き込みを行ってもよいし、あるいは、そのようにする何らかの別の理由（例えば、セクタＸとセクタＳとの間の論理的ギャップがしきい値未満であるなど）があれば、シーケンシャルに書き込みを行ってもよい。この例では、セクタＸは、更新ブロック５２内の次の利用可能な空間へ書き込みが行われているものとして示されている。この結果、更新ブロック５２はカオスブロックとなる。図１２Ｃ内の第２の例では、セクタＹはセクタＡの後で受信される。セクタＹの受信前には更新ブロック５４はシーケンシャルなブロックになる。セクタＹは次の未使用クラスタから得られたものではない。というのは、更新ブロック（セクタＡ）内の最後に書き込まれたセクタとセクタＹとの間に未使用クラスタ（クラスタ７）が存在するからである。したがって、セクタＹはシーケンシャルな強制書き込みを引き起こすものではなく、パディングを行うことなく更新ブロック５４へ書き込みを行って、更新ブロック５４をカオスブロックにするものである。図１２Ｄに示されている第３の例では、セクタＡの後にセクタＺが受信される。更新ブロック５６はセクタＺの受信に先行してシーケンシャルである。セクタＺはクラスタ０から得られるものであり、したがって、次の未使用クラスタから得られるものではない。というのは、クラスタ０はクラスタ２の前に存在するからである。したがって、図示の順序で示されているように、クラスタ０は次の未使用クラスタではない。したがって、セクタＺはクラスタＡの直後に書き込みを行うことが可能であり、これに起因して更新ブロック５６はカオスブロックとなる。
【００６４】
本発明の利点は非常に多い。異なる実施形態または実施構成は１以上の以下の利点を生み出すことができる。以下が網羅的なリストではないこと、および本願明細書に記載されていない他の利点が存在する可能性もあることに留意されたい。本発明の１つの利点として、不揮発性メモリシステムの性能の改善が可能であるいう点が挙げられる。本発明の別の利点として、広く使用されている規定を用いて本発明の実現が可能であるという点が挙げられる。本発明のさらに別の利点として、本発明はフラッシュメモリ内のテーブルとして相対的に小さな属性を実現することができるという点が挙げられる。他の実施構成ではテーブルは必要ではない。さらに別の利点として、任意の用途のために、および／または、バックグラウンドでの保守管理処理中に利用するために、本発明が実施可能であるという点が挙げられる。
【００６５】
前述した本発明の種々の態様または特徴は、単独で、あるいは、種々に組み合わせて利用することが可能である。本発明はハードウェアあるいはハードウェアとソフトウェアとの組み合わせによって実現可能である。本発明はコンピュータ可読媒体におけるコンピュータ可読コードとして具現化することも可能である。このコンピュータ可読媒体は、コンピュータシステムによって後で読み出すことができるデータを格納することが可能な任意のデータ記憶装置であってもよい。コンピュータ可読媒体の例として、リードオンリメモリ、ランダムアクセスメモリ、ＣＤ−ＲＯＭ、ＤＶＤ、磁気テープ、光データ記憶装置、並びに搬送波が含まれる。これらのコンピュータ可読媒体は、ネットワーク接続されたコンピュータシステムにわたって分散するので、コンピュータ可読コードを格納し、分散して実行するように図ることが可能である。
【００６６】
本発明の多くの特徴と利点とは前述した説明から明らかであり、したがって、本発明のこのようなすべての特徴並びに利点をカバーすることが添付の特許請求の範囲によって意図されている。さらに、多くの修正および変更が当業者の心に容易に浮かぶであろうことが考えられるため、本願明細書に例示し、記載したような構成および処理と同じ正確な構成および処理に本発明は限定されるものではない。したがって、すべての適切な修正並びに均等物は本発明の範囲内に属するものとなる。
【図面の簡単な説明】
【００６７】
【図１】いくつかの論理セクタに分割することができる論理アドレス空間を示す。
【図２Ａ】本発明の１つの実施形態に従うコピー管理方法を描く。
【図２Ｂ】本発明の１つの実施形態に従う計算環境を描く。
【図３Ａ】本発明の１つの実施形態に従うデータアロケーションテーブル（ＤＡＴ）を描く。
【図３Ｂ】本発明の１つの実施形態に従うデータアロケーションテーブル（ＤＡＴ）のエントリを描く。
【図３Ｃ】本発明の１つの実施形態に従うコントローラによって利用できるホストの論理データ構成を描く。
【図４】本発明の１つの実施形態に従う、フラッシュメモリに格納されたデータに関する情報をフラッシュメモリコントローラに提供する方法を描く。
【図５】本発明の１つの実施形態に従うフラッシュメモリの保守管理方法を示す。
【図６】本発明の１つの実施形態に従うモニタ方法を示す。
【図７】本発明の１つの実施形態に従う例示のガーベッジコレクション方法を描く。
【図８】本発明の１つの実施形態に従うデータアロケーションテーブル（ＤＡＴ）を描く。
【図９Ａ】ファイルアロケーションテーブル（ＦＡＴ）の１例を示す。
【図９Ｂ】図９ＡのＦＡＴから導き出されるＤＡＴを示す。
【図９Ｃ】ホストデータの一部に対するクラスタとセクタ間の対応関係の１例を示す。
【図９Ｄ】カオスブロックに格納され、シーケンシャルなブロックへ遅れてコピーされる非シーケンシャルなデータを示す。
【図９Ｅ】シーケンシャルなブロックに直接格納された非シーケンシャルなデータを示す。
【図１０】本発明の実施形態に従うホストデータの一部のための格納方式を選択するためのフローチャートを示す。
【図１１】本発明の別の実施形態に従うホストデータの一部のための格納方式を選択するためのフローチャートを示す。
【図１２Ａ】シーケンシャルに格納された非シーケンシャルなデータの１例を示す。
【図１２Ｂ】非シーケンシャルに格納された非シーケンシャルなデータの第１の例を示す。
【図１２Ｃ】非シーケンシャルに格納された非シーケンシャルなデータの第２の例を示す。
【図１２Ｄ】非シーケンシャルに格納された非シーケンシャルなデータの第３の例を示す。
【図１】
2008507756.tif 000003
【図２Ａ】
2008507756.tif 000004
【図２Ｂ】
2008507756.tif 000005
【図３Ａ】
2008507756.tif 000006
【図３Ｂ】
2008507756.tif 000007
【図３Ｃ】
2008507756.tif 000008
【図４】
2008507756.tif 000009
【図５】
2008507756.tif 000010
【図６】
2008507756.tif 000011
【図７】
2008507756.tif 000012
【図８】
2008507756.tif 000013
【図９Ａ】
2008507756.tif 000014
【図９Ｂ】
2008507756.tif 000015
【図９Ｃ】
2008507756.tif 000016
【図９Ｄ】
2008507756.tif 000017
【図９Ｅ】
2008507756.tif 000018
【図１０】
2008507756.tif 000019
【図１１】
2008507756.tif 000020
【図１２Ａ】
2008507756.tif 000021
【図１２Ｂ】
2008507756.tif 000022
【図１２Ｃ】
2008507756.tif 000023
【図１２Ｄ】
2008507756.tif 000024
【国際調査報告】
2008507756.tif 000025
2008507756.tif 000026